[Graph Embedding] DeepWalk 論文筆記
[Graph Embedding] DeepWalk
Introduction
圖表示學習是將圖(Graph/Network)中節點在一個低維的連續的向量空間中表示出來，這種表示能夠保留節點與鄰居的相似性、節點的社區成員屬性等。得到節點的向量表示就可以餵給下游的學習模型進行節點分類，邊預測等任務。
DeepWalk作爲圖表示學習的經典方法之一，核心方法就是通過對一定數量的節點做RandomWalk（隨機遊走），然後將得到的節點序列作爲頂點的向量輸入表示，通過使用skip-gram model 進行學習，得到最終的表示。下圖爲對一個空手道俱樂部成員的social relationship Graph表示到一個二維空間。
Random Walks
所謂隨機遊走（random walk）就是從一個節點開始隨機的選擇下一個與當前的節點相鄰的節點（提前設定隨機遊走結束的條件），最終形成一條節點序列。截斷隨機遊走（truncated random walks）就是指長度固定的隨機遊走。使用隨機遊走的好處有：
- 併發性。隨機遊走可以同時在圖上的多個節點上同時進行。
- 適應性。由於圖的結構是隨時間動態變化的，所以當圖變化的時候，不需要對所有節點重新進行隨機遊走，只需要對與圖中變化了的子圖有關的節點重新進行隨機遊走得到新的向量表示就可以。
Graph Embedding 與 NLP
作者發現了對graph上的節點進行隨機遊走的節點頻率與NLP（自然語言處理）中word在文章中的出現頻率都滿足一樣的power-law（冪律分佈）。如下圖所示：
既然網絡（Graph/Network）的特徵特性與自然語言處理那麼相近，那麼我們是否可以將NLP中的詞向量的模型用在Graph Embedding中，這就是本文的核心觀念。
要想了解DeepWalk的算法原理，需要提前瞭解NLP中Word Embedding 和 Word2Vec的基本內容，並且要理解其中的一種算法——SkipGram。
DeepWalk 算法原理
DeepWalk算法主要由2部分組成，第一部分是產生節點的隨機遊走序列，第二部分是參數的更新。算法的流程圖如下圖所示。
第2步是在構造Hierarchical Softmax（層次Softmax）所需的二叉樹，算法中使用到Hierarchical Softmax加速算法的學習，這裏不多加闡述。第3步是總的迭代次數，共γ次。每一次迭代（第4步到8步）中，對Graph中的每一個節點進行一次random walk，然後將生成的節點序列作爲輸入向量，輸入SkipGram算法中進行參數的學習。
參數更新如下圖所示：
第3步是需要優化的函數，即使得當頂點爲 v j v_j vj時，它所在的random walk序列中的 [ j − w : j + w ] [j - w : j + w] [j−w:j+w]中除了 v j v_j vj的頂點出現的條件概率最大化（這裏使用到的是NLP中的SkipGram算法）。
第4步採用SGD（隨機梯度下降）進行參數的迭代更新.
在計算 P r ( u k ∣ Φ ( v j ) ) P_r(u_k | \Phi(v_j)) Pr(uk∣Φ(vj))時，爲了減少算法的時間複雜度，作者使用到的是Hierarchical Softmax（層次Softmax），這也是NLP中詞向量用到的一個重要方法，這裏不做過多闡述，如果感興趣，可以閱讀原論文4.2.2節。