背景介紹

這幾年圖神經網路模型（如譜聚類的GCN、GAT等等）都挺火的，這些圖神經網路即將節點或圖映射到一個低維空間（稱為圖嵌入）；而除了GNN還有很多圖嵌入方法（在GNN之前圖嵌入的概念常出現在流行學習和網路分析的研究中），這類圖嵌入方法可以分為【基于矩陣分解的圖嵌入方法】和【基于隨機游走的圖嵌入方法】，后者方法就是來自本篇論文，即第一個將NLP的思想用在網路嵌入（Networking Embedding，NE）的，

論文：《DeepWalk: Online Learning of Social Representations》
論文作者：B. Perozzi, R. Al-Rfou, and S. Skiena
論文來源：KDD, 2014
論文鏈接：https://arxiv.org/abs/1403.6652
發在KDD上的最終版本：https://dl.acm.org/doi/10.1145/2623330.2623732
github鏈接：https://github.com/phanein/deepwalk

零、Abstract

本文提出DeepWalk演算法——一種用于學習網路中頂點的潛在表示的新方法，這些潛在表示將社會關系編碼到連續的向量空間中，以至于能容易地用到統計模型中，DeepWalk將語言建模和無監督特征學習（或深度學習）的最近進展，從單詞序列推廣到圖中，

DeepWalk將隨機游走得到的節點序列作為句子，從截斷的隨機游走序列中得到網路的區域資訊，通過這些區域資訊來學習節點的潛在表示，為了證實DeepWalk得到的節點的潛在表示的效果，本文對幾個社交網路（如BlogCatalog，Flickr和YouTuBe等）進行了多標簽分類任務，我們的結果顯示，DeepWalk演算法能夠對網路進行全域的觀察，特別是在缺失資訊的情況下，也能比baselines強，當標記資料稀疏（很少）時，DeepWalk的表示得到的F1分數比同類方法高出10%，在一些實驗中，當訓練資料少于60%時，DeepWalk演算法能夠勝過所有對比演算法，

DeepWalk也是可擴展的，它是一種可以建立有用的增量（incremental）結果的在線學習演算法，而且是平行的，這些特性使其適用于廣泛的實際應用，如網路分類和例外檢測，

一、Introduction

首先介紹了網路嵌入是什么，以社交網路為例，網路嵌入是將網路中的點用一個低維的向量表示（這些向量要能反應原網路的某些特性，比如如果在原網路中兩個點的結構相似，則兩個點表示成的向量也應該類似），

過去：普通的鄰接矩陣當存盤很多關系時，維度將變得很高，而矩陣分解非常費時且復雜，所以通過矩陣分解的方法進行網路的表示學習，目前沒有應用在大規模資料集的方案中，

在NLP任務中，word2vec是一種常用的word embedding方法，它通過語料庫的句子序列來描述詞與詞之間的共現關系，進而學習詞語的向量表示，

本文是第一次引入深度學習的無監督特征學習，通過將NLP模型word2vec應用到網路的表示上，做到了無需進行矩陣分解即可表示出網路中的節點的關系，文中提出了一種網路嵌入的方法DeepWalk——它的輸入是一張圖或網路，輸出是網路中頂點的潛在向量表示（將社交關系編碼成維度較小的連續向量空間），下圖是將DeepWalk用于學習好的Karate網路的效果，我們

DeepWalk通過一串截斷隨機游走（truncated random walk）類似word2vec中對單詞的背景關系，作為word2vec演算法的輸入，進而把節點表示成向量，從而學習出一個網路的社交表示（social representation），在網路標注頂點很少的情況也能得到較好效果，輸出的結果能被作為多種分類演算法作為輸入應用，該演算法具有可擴展性的有點，能夠適應網路的變化，

• DeepWalk思想類似word2vec，使用圖中節點之間的共現關系來學習節點的向量表示，那么問題關鍵就是如何描述節點之間的共現關系——DeepWalk的方法是使用隨機游走（Random Walk）的方式在圖中進行節點采樣，
• Random Walk是一種可重復訪問已訪問節點的DFS演算法，給定當前訪問起始節點，從其鄰居中隨機采樣節點作為下一個訪問節點，重復該程序，直到訪問序列長度滿足預設要求，

本文的三點主要貢獻有：

• 使用深度學習去分析圖，建立了一個適合統計建模的健壯表征方法，DeepWalk根據短距離的隨機游走學習結構化表示，
• 在社會網路的多標簽分類任務上評估我們的表征方法，顯示：在標簽的出現次數稀疏情況下，演算法在指標Micro F1值上提高了5%-10%；在一些栗子上，即使提取40%的訓練資料，DeepWalk演算法的representations仍然能獲得很好的效果，
• 作者通過采用并行的方法構建web-scale graphs（例如youtube）的representations表明了演算法的可擴展性，

二、Problem Definition

將社交網路的成員分類問題考慮為一個或多個類別，

• 給定部分標記的社交網路 G L = ( V , E , X , Y ) G_L=(V,E,X,Y) GL?=(V,E,X,Y) 的形式表示，其中屬性 X ∈ R ∣ V ∣ × S X \in \mathbb{R}^{|V| \times S} X∈R∣V∣×S ( S S S是每個屬性向量的特征空間的大小)，
• Y ∈ R ∣ V ∣ × ∣ Y ∣ Y \in \mathbb{R}^{|V| \times |Y|} Y∈R∣V∣×∣Y∣ ， Y Y Y是標簽集，是一個節點個數x標簽個數的矩陣，代表每個節點都有一個自己的標簽，

任務是將社交網路中的結點進行分類，但該分類問題和普通分類不同，在傳統的機器學習分類設定中，目標是學習一個假設 H H H，它將 X X X的元素映射到標簽集 Y Y Y，
但對于一個圖，需要利用到節點在圖中嵌入的資訊，即節點鄰居等，這部分資訊常常是隱藏的，不體現在 X X X當中，需要結合網路結構來進行分類[37]，單個節點的分類不是獨立的任務，而是與其它節點的分類相關，這被稱作集體分類(Collective Classification)或關聯分類(Relational Classification)，

DeepWalk從關聯分類任務中提取除了上游子任務——學習所有結點的嵌入表示 X E ∈ R ∣ V ∣ × d X_E \in \mathbb{R}^{|V| \times d} XE?∈R∣V∣×d，其中 d d d是一個較小的維度數， X E X_E XE?可用于捕捉節點的結構資訊，

三、Learning Social Representions

學習一個網路表示時需要注意的幾個性質：

• 適應性，網路表示需要適應網路的變化（不斷會有新節點和邊添加進來），
• 社群性，網路中往往會出現一些特征相似的點構成的團狀結構，這些節點表示成向量后必須相似，
• 低維性，低維度的表示可以在少量標注資料上獲得更好的泛化性能，過高會有過擬合的風險，對網路中有缺失資料的情況處理能力較差，
• 連續性，低維的向量應該是連續的，連續的表示在區分社區邊界上更加平滑，使得分類結果更加魯棒，

網路嵌入和NLP的word2vec即詞嵌入類似，前者是將網路節點用向量表示，后者是將單詞用向量表示，

3.1 Random Walks

隨機游走（random walk），在網路上不斷重復隨機選擇游走路徑，最終形成一條貫穿網路的路徑，從某個特定的端點開始，每次從當前節點相連的邊中隨機選擇一條，沿著選定的邊移動到下一個頂點，不斷重復該程序，階段隨機游走（truncated random walk）實際是長度固定的隨機游走，

隨機游走的兩個好處：

• 并行性：隨機游走是區域行為，在大網路中，可以同時在不同的點開始截斷隨機游走，從而減少采樣的時間，
• 適應性：適應網路的區域變化，因為網路的演化（如區域的點和邊的變化）對只會部分的隨機游走路徑產生影響，因此在網路的演化程序中不需要每一次都重新計算整個網路的隨機游走，

3.2 Connection:Power laws（連接：冪律）

自然語言已被證明是符合冪次定律，只要證明圖的資料的也符合冪次定律就可以對圖的表示應用對自然語言表示的方法，下圖比較了對圖進行短隨機游走中向量出現的頻率與單詞在文本資訊中出現的頻率，可見對圖的短隨機游走也是大致滿足冪次定律的：

3.3 Language Modeling

語言模型主要是學詞序列：
W 1 n = ( w 0 , w 1 , ? ? , w n ) W_{1}^{n}=\left(w_{0}, w_{1},\cdots, w_{n}\right) W1n?=(w0?,w1?,?,wn?)我們需要用前n個單詞預測第n個單詞，即將 Pr ? ( w n ∣ w 0 , w 1 , ? ? , w n ? 1 ) \operatorname{Pr}\left(w_{n} \mid w_{0},w{1},\cdots,w_{n-1}\right) Pr(wn?∣w0?,w1,?,wn?1?)但是論文的目的是要學習一個隱表示，因此引入一個映射函式： Φ : v ∈ V ? R ∣ V ∣ × d \Phi: v \in V \mapsto \mathbb{R}^{|V| \times d} Φ:v∈V?R∣V∣×d，所以問題就變成了估計 Pr ? ( v n ∣ Φ ( v 0 ) , Φ ( v 1 ) , ? ? , Φ ( v n ? 1 ) ) \operatorname{Pr}\left(v_{n} \mid \Phi\left(v_{0}\right), \Phi\left(v_{1}\right), \cdots, \Phi\left(v_{n-1}\right)\right) Pr(vn?∣Φ(v0?),Φ(v1?),?,Φ(vn?1?))但是如果隨機游走的長度變大，會降低該條件概率估計的效率，NLP中針對這個問題給出以下幾個方案：
（1）將背景關系預測一個單詞的問題，轉為根據一個單詞預測背景關系的問題；
（2）在一個給定單詞的左邊和右邊都會出現背景關系內容
（3）去掉單詞出現的順序約束
于是問題變成了如下最優化問題，因為順序被忽略了，所以比較適合圖學習，
minimize ? Φ ? log ? Pr ? ( { v i ? w , ? ? , v i ? 1 , v i + 1 , ? ? , v i + w } ∣ Φ ( v i ) ) \underset{\Phi}{\operatorname{minimize}}-\log \operatorname{Pr}\left(\left\{v_{i-w}, \cdots, v_{i-1}, v_{i+1}, \cdots, v_{i+w}\right\} \mid \Phi\left(v_{i}\right)\right) Φminimize??logPr({vi?w?,?,vi?1?,vi+1?,?,vi+w?}∣Φ(vi?))

四、Method

4.1 Overview

4.2 Algorithm:DeepWalk

演算法由兩部分組成：（1）隨機游走序列生成器；（2）向量更新，
隨機游走：對圖G均勻地隨機采樣一個節點 v i v_i vi?，并作為random walk的根結點 W v i W_{v_{i}} Wvi??，然后一直向周圍鄰居采樣，直到達到最大路徑長度 t t t，
隨機游走的長度沒有限制，但是在實驗中設定最大步長是固定的，

• 輸出：一個頂點表示矩陣 Φ \Phi Φ，大小為 ∣ V ∣ × d |V|\times d ∣V∣×d
• 第二行：構建Hierarchical Softmax
• 第三行：對每個節點做 γ \gamma γ次隨機游走
• 第四行：打亂網路中的節點
• 第五行：以每個節點為根結點生成長度為 t t t的隨機游走
• 第七行：根據生成的隨機游走使用skip-gram模型利用梯度的方法對引數進行更新，

其中SkipGram引數更新的細節如下：

（1）SkipGram

SkipGram引數更新的細節如下：

SkipGram演算法是語言模型中，最大化視窗 w w w中出現的詞的概率的方法（梯度下降），外層for回圈是對這個序列中的每個詞進行操作，內層for回圈是對每個詞的視窗大小為 w w w的詞序列進行操作，具體操作是用一個似然函式 J ( Φ ) J(\Phi) J(Φ)表示 Φ \Phi Φ，通過梯度下降（對 J ( Φ ) J(\Phi) J(Φ)求導）更新引數（ α \alpha α是學習速率），

從詞向量學習的角度看，基于神經網路語言模型的預訓練方法存在缺點：當對t時刻詞進行預測時，模型只利用了歷史詞序列作為輸入，而損失了與“未來”背景關系之間的共現資訊，于是大佬們提出更強的詞向量預訓練模型Word2Vec，其中包括CBOW(Continuous Bag-of-Words)模型以及Skip-gram模型，

（2）Hierarchical Softmax

在計算 Pr ? ( u k ∣ Φ ( v i ) ) \Pr(u_k|\Phi(v_i)) Pr(uk?∣Φ(vi?)) 時，可以利用Hierarchical Softmax二叉樹[29, 30]加速，作者將所有節點作為二叉樹的葉子節點，就可以用從根節點到葉子節點的路徑來表示每個節點，二叉樹若有 ∣ V ∣ |V| ∣V∣個葉子節點，則深度至多為 log ? ∣ V ∣ \log|V| log∣V∣，這樣就會有：
Pr ? ( u k ∣ Φ ( v j ) ) = ∏ l = 1 ? log ? ∣ V ∣ ? Pr ? ( b l ∣ Φ ( v j ) ) \Pr(u_k|\Phi(v_j))=\prod_{l=1}^{\lceil\log|V|\rceil}\Pr(b_l|\Phi(v_j)) Pr(uk?∣Φ(vj?))=l=1∏?log∣V∣??Pr(bl?∣Φ(vj?))其中 b 0 , b 1 , . . . , b ? log ? ∣ V ∣ ? b_0, b_1, ..., b_{\lceil\log|V|\rceil} b0?,b1?,...,b?log∣V∣??是一系列二叉樹中的非葉子節點，這樣就可以用較少的分類器完成這個任務，將計算復雜度由 O ( ∣ V ∣ ) O(|V|) O(∣V∣)降低至 O ( log ? ∣ V ∣ ) O(\log|V|) O(log∣V∣)，

更進一步，還可以結合節點出現頻率，使用霍夫曼編碼，為更頻繁出現的節點分配稍短的路徑，再次降低計算復雜度，

（3）Optimization

模型引數集是 { Φ , T } \{\Phi, T\} {Φ,T}，使用隨機梯度下降演算法 S G D SGD SGD（一次訓練一個樣本）進行優化引數，通過方向傳播計算損失函式關于引數的偏導數，SGD的學習率初始設定為2.5%，然后隨著訓練程序中看到的頂點數量的增加而線性減少，

4.3 Parallelizability并行性

上面的Figure 2 顯示了社交網路中的隨機游走的頂點和語言模型中的詞的頻率分布都符合冪律分布，這導致產生罕見的頂點的長尾效應，因此更新 Φ \Phi Φ將是稀疏的，并且沒有獲得一個鎖來訪問模型共享引數，ASGD將獲得一個最優的收斂速度[36]，當使用多執行緒在一臺機器上運行實驗時，可得該技術具有很高擴展性（可用于大規模的機器學習[8]），

Figure 4 顯示了并行化DeepWalk的效果，當將worker的數量增加至8個，處理BlogCatalog和Flickr網路的速度是一致的（圖4a），它還表明，與連續運行DeepWalk相比，預測性能沒有損失（圖4b），

4.4 Algorithm Variants

（1）Streaming

本文方法的一個有趣的變體是流方法，它可以在不了解整個圖的情況下實作，在這種變體中，圖中的small walks直接傳遞給表示學習代碼，并直接更新模型，
對學習程序也需要做一定的修改：
（1）使用衰減的學習率將不再可能，相反可以初始化學習速率 α \alpha α為小常數值，這將花費更多的時間來學習，但是在某些應用程式中可能是值得的，
（2）不能再構建引數樹了，如果 V V V的基數已知（或可以有界），就可以為該最大值構建層次結構的Softmax樹（Hierarchical Softmax），當頂點第一次被看到時，可以將它們分配給剩余的葉子之一，如果有能力估計頂點頻率，還可以使用霍夫曼編碼來減少頻繁元素的訪問時間，

（2）Non-random walks

某些圖是由agent與一些列元素（如用戶在網站上的頁面導航）互動的副產品而創建的，當這樣的非隨機游走創建圖時，我們可以使用此程序直接為建模階段提供資料，以這種方式采樣的圖形不僅能捕獲與網路結構有關的資訊，而且還將捕獲與遍歷路徑的頻率有關的資訊，

作者認為將這種方法與流式變體結合使用，以不斷發展的網路上訓練要素，而不需要明確構造整個圖，用該方法來建立和更新表示可以實作網路規模（ w e b ? s c a l e web-scale web?scale）分類，而不需要處理網路規模圖，

五、Experimential Design

本節概述了實驗中使用的資料集和方法，本文代碼和資料將在第一作者的網站上公布，

5.1 Datasets

資料集分別為

• BlogCatalog [39]：blogger作者之間的社交關系網路，labels代表了bolg的主題分類，
• Flickr [39]：一個圖片分享網站，用戶之間進行聯系的網路，labels代表了用戶的興趣分組，例如“lack and white
  photos”
• YouTube [40]：視頻分享網站，用戶之間構成一個網路，labels代表了喜歡相同視頻的用戶的分組，
  

5.2 Baseline Methods

和下面的baseline進行對比：
SpectralClustering
Modularity
EdgeCluster
wvRN
Majority

六、Experiments

本節對許多多標簽分類任務進行徹底評估，并分析其在多個引數中的敏感度，

6.1 Multi-Label Classification

為了便于我們的方法與相關基準方法之間的比較，我們使用與[39，40]中完全相同的資料集和實驗程式， 具體來說，我們隨機采樣標記節點的一部分（TR），并將其用作訓練資料， 其余節點用作測驗， 我們重復此程序10次，并報告Macro-F1和Micro-F1的平均性能， 如果可能，我們直接在此處報告原始結果[39，40]，

對于所有模型，我們使用由LibLinear 擴展實作的一對一邏輯對數回歸，以回傳最可能的標簽，如[39]所示， 我們提供（γ= 80，w = 10，d = 128）的Deep-Walk結果， （SpectralClustering，Modularity，EdgeCluster）的結果使用了Tang和Liu的首選維數d = 500，

（1）BlogCatalog

（2）Flickr

在此實驗中，我們將Flickr網路上的訓練率（TR）從1％更改為10％， 這相當于在整個網路中大約有800至8,000個節點被標記為分類， 表3給出了我們的結果，與先前的實驗一致， 相對于Micro-F1，DeepWalk優于所有基準方法至少3％， 此外，當僅標記了圖表的3％時，其他方法已經有了10％的資料，Micro-F1性能也優于其他所有方法， 換句話說，DeepWalk的訓練資料不到60％，表現就優于基準方法， 它在Macro-F1中的性能也相當好，最初的性能接近SpectralClustering，但差距僅達到1％，

（3）YouTube

YouTube網路比我們之前嘗試過的網路要大得多，并且它的規模使我們無法運行兩種基準方法（Spectral Clustering和Modularity）， 它比我們之前考慮的更接近真實世界的圖，

表4中列出了將訓練比率（TR）從1％更改為10％的結果，它們表明，DeepWalk在創建圖形表示形式EdgeCluster方面明顯優于基準方法， 當使用1％的標記節點進行測驗時，Micro-F1可以提高14％，Macro-F1顯示相應的10％的增加， 隨著訓練資料的增加，這種領先優勢逐漸縮小，但是DeepWalk在Micro-F1中領先3％，而在Macro-F1中令人印象深刻的5％改善，

此實驗展示了使用社交表示學習進行多標簽分類可能帶來的性能優勢， DeepWalk可以縮放到大圖，并且在這種稀疏標記的環境中表現出色，

6.2 Parameter Sensitivity

為了評估DeepWalk的引數化更改如何影響其對分類任務的性能，我們對兩個多標簽分類任務（Flickr和BlogCatalog）進行了實驗， 為了簡潔起見，我們已固定視窗大小和步行長度以強調區域結構（w = 10，t = 40）， 然后，我們更改潛在維數（d），每個頂點開始的遍歷數（γ）以及可用的訓練資料量（TR），以確定它們對網路分類性能的影響，

（1）Effect of Dimensionality

引數說明：

• 文中使用固定的window size和walk length： w = 10 , t = 40 w = 10,t = 40 w=10,t=40
• d : 維 度 d:維度 d:維度
• γ \gamma γ：每個頂點開始的walk數量
• T R T_R TR?：學習率

實驗說明：

• 圖5a1和5a3測驗了改變維度和學習率的效果，Flickr和BlogCatalog的性能相當一致，表明模型的最佳維數取決于訓練實體的數量，
• 圖5a2和5a3研究了改變每個頂點的維數和游走次數的影響，維度之間的相對性能在不同的 γ \gamma γ值下是相對穩定的，

（2）Effect of sampling frequency

圖5顯示了增加 γ \gamma γ的影響，從每個節點開始的random walks數：最初增加 γ \gamma γ有很大影響，但很快減慢影響（ γ > 10 \gamma > 10 γ>10），這些只有在少量的random walks才能學習有意義的頂點的潛在表示，

七、Related Work

7.1 Relational Learning

關系分類（或集體分類）方法[15、25、32]使用資料項之間的鏈接作為分類程序的一部分， 集體分類問題中的精確推論是NP-Hard的，解決方案集中在近似推論演算法的使用上，這可能無法保證收斂，

• 與我們作業最相關的關系分類演算法通過學習集群[33]，在附近節點之間添加邊緣[14]，使用PageRank [24]或通過擴展關系分類以將其他特征考慮在內來整合社區資訊[43] ， 我們的作業采用了截然不同的方法， 代替新的近似推理演算法，我們提出了一種學習網路結構表示的程序，然后可以將其用于現有的推理程序（包括迭代程序），
• 我們還提出了許多用于從圖形生成特征的技術[13、17、39-41]， 與這些方法相比，我們將特征創建程序構架為表示學習問題，
• 已經提出了Graph Kernels [42]作為使用關系資料作為分類程序的一部分的方法，但是除非近似[20]，否則它會非常緩慢， 我們的方法是互補的； 我們將學習將其直接用作任何分類方法的特征，而不是將結構編碼為內核函式的一部分，

7.2 Unsupervised Feature Learning

已經提出了分布式表示來建模概念之間的結構關系[18]， 這些表示通過反向傳播和梯度下降進行訓練， 計算成本和數值不穩定導致這些技術被放棄了將近十年， 最近，分布式計算允許訓練更大的模型[4]，并且出現了無監督學習演算法的資料增長[10]， 分布式表示通常通過神經網路進行訓練，這些網路在諸如計算機視覺[22]，語音識別[8]和自然語言處理[1，7]的各個領域都取得了進步，

八、Conclusion

DeepWalk是學習潛在社交結點表征的新方法，算是network embedding的開山之作——借鑒NLP中詞向量的思想來做網路節點表示，后面有幾篇論文也是利用隨機游走構建概率模型，用詞向量中的Negative Sampling（負采樣）解決相應問題，

DeepWalk從一個簡單的角度切入，用現有的NLP中的skip-gram模型結合，在一個全新的且尚未成為主流的問題中得到一個行之有效的解，DeepWalk利用截斷隨機游走的區域資訊作為輸入，學習了一種能編碼網路結構資訊的表示方法，然后用該方法挑戰多標簽分類任務中表現有效，

作為一種在線學習演算法，DeepWalk也是可擴展的，它能夠為因太大而無法運行譜方法的圖創建有效的表示，DeepWalk明顯優于其他設計用于稀疏操作的方法；文中還展示該方法是可并行的，運行works同時更新模型的不同部分，

作者關于該領域的未來作業將集中在研究這種對偶性，利用DeepWalk的結果改進語言建模，并加強該方法的理論證明，

九、Reference

（1）https://dl.acm.org/doi/10.1145/2623330.2623732
（2）https://blog.csdn.net/yyl424525/article/details/100575405
（3）https://blog.csdn.net/StarfishCu/article/details/108049055
（4）https://www.cnblogs.com/lavi/p/4323691.html
（5）DeepWalk論文精讀：（2）核心演算法
（6）https://zhuanlan.zhihu.com/p/104731569
（7）圖神經網路—基于隨機游走的早期研究（一）：DeepWalk & Node2Vec