【論文翻譯】DeepWalk: Online Learning of Social Representations（論文翻譯網(wǎng)）

背景介紹

文章目錄

背景介紹

零、Abstract

一、Introduction

二、Problem Definition

三、Learning Social Representions

3.1 Random Walks

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

3.3 Language Modeling

四、Method

4.1 Overview

4.2 Algorithm:deepWalk

（1）SkipGram

（2）Hierarchical Softmax

（3）Optimization

4.3 Parallelizability并行性

4.4 Algorithm Variants

（1）Streaming

（2）Non-random walks

五、Experimential Design

5.1 Datasets

5.2 Baseline Methods

六、Experiments

6.1 Multi-Label Classification

（1）BlogCatalog

（2）Flickr

（3）YouTube

6.2 Parameter Sensitivity

（1）Effect of Dimensionality

（2）Effect of sampling frequency

七、Related Work

7.1 Relational Learning

7.2 Unsupervised Feature Learning

八、Conclusion

九、Reference

零、Abstract

本文提出deepWalk算法——一種用于學(xué)習(xí)網(wǎng)絡(luò)中頂點(diǎn)的潛在表示的新方法，這些潛在表示將社會關(guān)系編碼到連續(xù)的向量空間中，以至于能容易地用到統(tǒng)計模型中。DeepWalk將語言建模和無監(jiān)督特征學(xué)習(xí)（或深度學(xué)習(xí)）的最近進(jìn)展，從單詞序列推廣到圖中。

DeepWalk將隨機(jī)游走得到的節(jié)點(diǎn)序列作為句子，從截斷的隨機(jī)游走序列中得到網(wǎng)絡(luò)的局部信息，通過這些局部信息來學(xué)習(xí)節(jié)點(diǎn)的潛在表示。為了證實(shí)DeepWalk得到的節(jié)點(diǎn)的潛在表示的效果，本文對幾個社交網(wǎng)絡(luò)（如BlogCatalog，F(xiàn)lickr和YouTuBe等）進(jìn)行了多標(biāo)簽分類任務(wù)。我們的結(jié)果顯示，DeepWalk算法能夠?qū)W(wǎng)絡(luò)進(jìn)行全局的觀察，特別是在缺失信息的情況下，也能比baselines強(qiáng)。當(dāng)標(biāo)記數(shù)據(jù)稀疏（很少）時，DeepWalk的表示得到的F1分?jǐn)?shù)比同類方法高出10%。在一些實(shí)驗(yàn)中，當(dāng)訓(xùn)練數(shù)據(jù)少于60%時，DeepWalk算法能夠勝過所有對比算法。

DeepWalk也是可擴(kuò)展的，它是一種可以建立有用的增量（incremental）結(jié)果的在線學(xué)習(xí)算法，而且是平行的。這些特性使其適用于廣泛的實(shí)際應(yīng)用，如網(wǎng)絡(luò)分類和異常檢測。

一、Introduction

首先介紹了網(wǎng)絡(luò)嵌入是什么，以社交網(wǎng)絡(luò)為例，網(wǎng)絡(luò)嵌入是將網(wǎng)絡(luò)中的點(diǎn)用一個低維的向量表示（這些向量要能反應(yīng)原網(wǎng)絡(luò)的某些特性，比如如果在原網(wǎng)絡(luò)中兩個點(diǎn)的結(jié)構(gòu)相似，則兩個點(diǎn)表示成的向量也應(yīng)該類似）。

過去：普通的鄰接矩陣當(dāng)存儲很多關(guān)系時，維度將變得很高，而矩陣分解非常費(fèi)時且復(fù)雜，所以通過矩陣分解的方法進(jìn)行網(wǎng)絡(luò)的表示學(xué)習(xí)，目前沒有應(yīng)用在大規(guī)模數(shù)據(jù)集的方案中。

在NLP任務(wù)中，word2vec是一種常用的word embedding方法，它通過語料庫的句子序列來描述詞與詞之間的共現(xiàn)關(guān)系，進(jìn)而學(xué)習(xí)詞語的向量表示。

本文是第一次引入深度學(xué)習(xí)的無監(jiān)督特征學(xué)習(xí)，通過將NLP模型word2vec應(yīng)用到網(wǎng)絡(luò)的表示上，做到了無需進(jìn)行矩陣分解即可表示出網(wǎng)絡(luò)中的節(jié)點(diǎn)的關(guān)系。文中提出了一種網(wǎng)絡(luò)嵌入的方法DeepWalk——

它的輸入是一張圖或網(wǎng)絡(luò)，輸出是網(wǎng)絡(luò)中頂點(diǎn)的潛在向量表示

（將社交關(guān)系編碼成維度較小的連續(xù)向量空間）。下圖是將DeepWalk用于學(xué)習(xí)好的Karate網(wǎng)絡(luò)的效果，我們

DeepWalk通過一串截斷隨機(jī)游走（truncated random walk）類似word2vec中對單詞的上下文，作為word2vec算法的輸入，進(jìn)而把節(jié)點(diǎn)表示成向量，從而學(xué)習(xí)出一個網(wǎng)絡(luò)的社交表示（social representation），在網(wǎng)絡(luò)標(biāo)注頂點(diǎn)很少的情況也能得到較好效果。輸出的結(jié)果能被作為多種分類算法作為輸入應(yīng)用。該算法具有可擴(kuò)展性的有點(diǎn)，能夠適應(yīng)網(wǎng)絡(luò)的變化。

DeepWalk思想類似word2vec，使用圖中節(jié)點(diǎn)之間的共現(xiàn)關(guān)系來學(xué)習(xí)節(jié)點(diǎn)的向量表示。那么問題關(guān)鍵就是如何描述節(jié)點(diǎn)之間的共現(xiàn)關(guān)系——DeepWalk的方法是使用隨機(jī)游走（Random Walk）的方式在圖中進(jìn)行節(jié)點(diǎn)采樣。

Random Walk是一種可重復(fù)訪問已訪問節(jié)點(diǎn)的DFS算法。給定當(dāng)前訪問起始節(jié)點(diǎn)，從其鄰居中隨機(jī)采樣節(jié)點(diǎn)作為下一個訪問節(jié)點(diǎn)，重復(fù)該過程，直到訪問序列長度滿足預(yù)設(shè)要求。

本文的三點(diǎn)主要貢獻(xiàn)有：

使用深度學(xué)習(xí)去分析圖，建立了一個適合統(tǒng)計建模的健壯表征方法。DeepWalk根據(jù)短距離的隨機(jī)游走學(xué)習(xí)結(jié)構(gòu)化表示。

在社會網(wǎng)絡(luò)的多標(biāo)簽分類任務(wù)上評估我們的表征方法，顯示：在標(biāo)簽的出現(xiàn)次數(shù)稀疏情況下，算法在指標(biāo)Micro F1值上提高了5%-10%；在一些栗子上，即使提取40%的訓(xùn)練數(shù)據(jù)，DeepWalk算法的representations仍然能獲得很好的效果。

二、Problem Definition

將社交網(wǎng)絡(luò)的成員分類問題考慮為一個或多個類別。

給定部分標(biāo)記的社交網(wǎng)絡(luò) 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是標(biāo)簽集，是一個節(jié)點(diǎn)個數(shù)x標(biāo)簽個數(shù)的矩陣，代表每個節(jié)點(diǎn)都有一個自己的標(biāo)簽。

任務(wù)是將社交網(wǎng)絡(luò)中的結(jié)點(diǎn)進(jìn)行分類，但該分類問題和普通分類不同。在傳統(tǒng)的機(jī)器學(xué)習(xí)分類設(shè)置中，目標(biāo)是學(xué)習(xí)一個假設(shè) H H H，它將 X X X的元素映射到標(biāo)簽集 Y Y Y。

但對于一個圖，需要利用到節(jié)點(diǎn)在圖中嵌入的信息，即節(jié)點(diǎn)鄰居等。這部分信息常常是隱藏的，不體現(xiàn)在 X X X當(dāng)中，需要結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)來進(jìn)行分類[37]，單個節(jié)點(diǎn)的分類不是獨(dú)立的任務(wù)，而是與其它節(jié)點(diǎn)的分類相關(guān)。這被稱作集體分類(Collective Classification)或關(guān)聯(lián)分類(Relational Classification)。

DeepWalk從關(guān)聯(lián)分類任務(wù)中提取除了上游子任務(wù)——學(xué)習(xí)所有結(jié)點(diǎn)的嵌入表示 X E ∈ R ∣ V ∣ × d X_E \in \mathbb{R}^{|V| \times d} XE ∈R∣V∣×d，其中 d d d是一個較小的維度數(shù)， X E X_E XE 可用于捕捉節(jié)點(diǎn)的結(jié)構(gòu)信息。

三、Learning Social Representions

學(xué)習(xí)一個網(wǎng)絡(luò)表示時需要注意的幾個性質(zhì)：

適應(yīng)性。網(wǎng)絡(luò)表示需要適應(yīng)網(wǎng)絡(luò)的變化（不斷會有新節(jié)點(diǎn)和邊添加進(jìn)來）。

社群性。網(wǎng)絡(luò)中往往會出現(xiàn)一些特征相似的點(diǎn)構(gòu)成的團(tuán)狀結(jié)構(gòu)，這些節(jié)點(diǎn)表示成向量后必須相似。

低維性。低維度的表示可以在少量標(biāo)注數(shù)據(jù)上獲得更好的泛化性能，過高會有過擬合的風(fēng)險，對網(wǎng)絡(luò)中有缺失數(shù)據(jù)的情況處理能力較差。

連續(xù)性。低維的向量應(yīng)該是連續(xù)的。連續(xù)的表示在區(qū)分社區(qū)邊界上更加平滑，使得分類結(jié)果更加魯棒。

網(wǎng)絡(luò)嵌入和NLP的word2vec即詞嵌入類似，前者是將網(wǎng)絡(luò)節(jié)點(diǎn)用向量表示，后者是將單詞用向量表示。

3.1 Random Walks

隨機(jī)游走（random walk），在網(wǎng)絡(luò)上不斷重復(fù)隨機(jī)選擇游走路徑，最終形成一條貫穿網(wǎng)絡(luò)的路徑。從某個特定的端點(diǎn)開始，每次從當(dāng)前節(jié)點(diǎn)相連的邊中隨機(jī)選擇一條，沿著選定的邊移動到下一個頂點(diǎn)，不斷重復(fù)該過程。階段隨機(jī)游走（truncated random walk）實(shí)際是長度固定的隨機(jī)游走。

隨機(jī)游走的兩個好處：

并行性：隨機(jī)游走是局部行為，在大網(wǎng)絡(luò)中，可以同時在不同的點(diǎn)開始截斷隨機(jī)游走，從而減少采樣的時間。

適應(yīng)性：適應(yīng)網(wǎng)絡(luò)的局部變化，因?yàn)榫W(wǎng)絡(luò)的演化（如局部的點(diǎn)和邊的變化）對只會部分的隨機(jī)游走路徑產(chǎn)生影響，因此在網(wǎng)絡(luò)的演化過程中不需要每一次都重新計算整個網(wǎng)絡(luò)的隨機(jī)游走。

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

自然語言已被證明是符合冪次定律，只要證明圖的數(shù)據(jù)的也符合冪次定律就可以對圖的表示應(yīng)用對自然語言表示的方法。下圖比較了對圖進(jìn)行短隨機(jī)游走中向量出現(xiàn)的頻率與單詞在文本信息中出現(xiàn)的頻率。可見對圖的短隨機(jī)游走也是大致滿足冪次定律的：

3.3 Language Modeling

語言模型主要是學(xué)詞序列：

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個單詞預(yù)測第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 )但是論文的目的是要學(xué)習(xí)一個隱表示，因此引入一個映射函數(shù)： Φ : 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 ))但是如果隨機(jī)游走的長度變大，會降低該條件概率估計的效率，NLP中針對這個問題給出以下幾個方案：

（1）將上下文預(yù)測一個單詞的問題，轉(zhuǎn)為根據(jù)一個單詞預(yù)測上下文的問題；

（2）在一個給定單詞的左邊和右邊都會出現(xiàn)上下文內(nèi)容

（3）去掉單詞出現(xiàn)的順序約束

于是問題變成了如下最優(yōu)化問題。因?yàn)轫樞虮缓雎粤耍员容^適合圖學(xué)習(xí)。

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）隨機(jī)游走序列生成器；（2）向量更新。

隨機(jī)游走：對圖G均勻地隨機(jī)采樣一個節(jié)點(diǎn) v i v_i vi ，并作為random walk的根結(jié)點(diǎn) W v i W_{v_{i}} Wvi ，然后一直向周圍鄰居采樣，直到達(dá)到最大路徑長度 t t t。

隨機(jī)游走的長度沒有限制，但是在實(shí)驗(yàn)中設(shè)置最大步長是固定的。

輸出：一個頂點(diǎn)表示矩陣 Φ \Phi Φ，大小為 ∣ V ∣ × d |V|\times d ∣V∣×d

第二行：構(gòu)建Hierarchical Softmax

第三行：對每個節(jié)點(diǎn)做 γ \gamma γ次隨機(jī)游走

第四行：打亂網(wǎng)絡(luò)中的節(jié)點(diǎn)

第五行：以每個節(jié)點(diǎn)為根結(jié)點(diǎn)生成長度為 t t t的隨機(jī)游走

第七行：根據(jù)生成的隨機(jī)游走使用skip-gram模型利用梯度的方法對參數(shù)進(jìn)行更新。

其中SkipGram參數(shù)更新的細(xì)節(jié)如下：

（1）SkipGram

SkipGram參數(shù)更新的細(xì)節(jié)如下：

SkipGram算法是語言模型中，最大化窗口 w w w中出現(xiàn)的詞的概率的方法（梯度下降），外層for循環(huán)是對這個序列中的每個詞進(jìn)行操作，內(nèi)層for循環(huán)是對每個詞的窗口大小為 w w w的詞序列進(jìn)行操作。具體操作是用一個似然函數(shù) J ( Φ ) J(\Phi) J(Φ)表示 Φ \Phi Φ，通過梯度下降（對 J ( Φ ) J(\Phi) J(Φ)求導(dǎo)）更新參數(shù)（ α \alpha α是學(xué)習(xí)速率）。

從詞向量學(xué)習(xí)的角度看，基于神經(jīng)網(wǎng)絡(luò)語言模型的預(yù)訓(xùn)練方法存在缺點(diǎn)：當(dāng)對t時刻詞進(jìn)行預(yù)測時，模型只利用了歷史詞序列作為輸入，而損失了與“未來”上下文之間的共現(xiàn)信息。于是大佬們提出更強(qiáng)的詞向量預(yù)訓(xùn)練模型Word2Vec，其中包括CBOW(Continuous Bag-of-Words)模型以及Skip-gram模型。

（2）Hierarchical Softmax

更進(jìn)一步，還可以結(jié)合節(jié)點(diǎn)出現(xiàn)頻率，使用

霍夫曼編碼

，為更頻繁出現(xiàn)的節(jié)點(diǎn)分配稍短的路徑，再次降低計算復(fù)雜度。

（3）Optimization

模型參數(shù)集是 { Φ , T } \{\Phi, T\} {Φ,T}，使用隨機(jī)梯度下降算法 S G D SGD SGD（一次訓(xùn)練一個樣本）進(jìn)行優(yōu)化參數(shù)。通過方向傳播計算損失函數(shù)關(guān)于參數(shù)的偏導(dǎo)數(shù)，SGD的學(xué)習(xí)率初始設(shè)置為2.5%，然后隨著訓(xùn)練過程中看到的頂點(diǎn)數(shù)量的增加而線性減少。

4.3 Parallelizability并行性

上面的Figure 2 顯示了社交網(wǎng)絡(luò)中的隨機(jī)游走的頂點(diǎn)和語言模型中的詞的頻率分布都符合冪律分布。這導(dǎo)致產(chǎn)生罕見的頂點(diǎn)的長尾效應(yīng)，因此更新 Φ \Phi Φ將是稀疏的，并且沒有獲得一個鎖來訪問模型共享參數(shù)，ASGD將獲得一個最優(yōu)的收斂速度[36]。當(dāng)使用多線程在一臺機(jī)器上運(yùn)行實(shí)驗(yàn)時，可得該技術(shù)具有很高擴(kuò)展性（可用于大規(guī)模的機(jī)器學(xué)習(xí)[8]）。

Figure 4 顯示了并行化DeepWalk的效果，當(dāng)將worker的數(shù)量增加至8個，處理BlogCatalog和Flickr網(wǎng)絡(luò)的速度是一致的（圖4a）。它還表明，與連續(xù)運(yùn)行DeepWalk相比，預(yù)測性能沒有損失（圖4b）。

4.4 Algorithm Variants

（1）Streaming

本文方法的一個有趣的變體是流方法，它可以在不了解整個圖的情況下實(shí)現(xiàn)。在這種變體中，圖中的small walks直接傳遞給表示學(xué)習(xí)代碼，并直接更新模型。

對學(xué)習(xí)過程也需要做一定的修改：

（1）使用衰減的學(xué)習(xí)率將不再可能，相反可以初始化學(xué)習(xí)速率 α \alpha α為小常數(shù)值。這將花費(fèi)更多的時間來學(xué)習(xí)，但是在某些應(yīng)用程序中可能是值得的。

（2）不能再構(gòu)建參數(shù)樹了。如果 V V V的基數(shù)已知（或可以有界），就可以為該最大值構(gòu)建層次結(jié)構(gòu)的Softmax樹（Hierarchical Softmax）。當(dāng)頂點(diǎn)第一次被看到時，可以將它們分配給剩余的葉子之一。如果有能力估計頂點(diǎn)頻率，還可以使用霍夫曼編碼來減少頻繁元素的訪問時間。

（2）Non-random walks

某些圖是由agent與一些列元素（如用戶在網(wǎng)站上的頁面導(dǎo)航）交互的副產(chǎn)品而創(chuàng)建的。當(dāng)這樣的非隨機(jī)游走創(chuàng)建圖時，我們可以使用此過程直接為建模階段提供數(shù)據(jù)。以這種方式采樣的圖形不僅能捕獲與網(wǎng)絡(luò)結(jié)構(gòu)有關(guān)的信息，而且還將捕獲與遍歷路徑的頻率有關(guān)的信息。

五、Experimential Design

5.1 Datasets

數(shù)據(jù)集分別為

Flickr [39]：一個圖片分享網(wǎng)站，用戶之間進(jìn)行聯(lián)系的網(wǎng)絡(luò)。labels代表了用戶的興趣分組，例如“l(fā)ack and white

photos”

YouTube [40]：視頻分享網(wǎng)站，用戶之間構(gòu)成一個網(wǎng)絡(luò)。labels代表了喜歡相同視頻的用戶的分組。

5.2 Baseline Methods

和下面的baseline進(jìn)行對比：

SpectralClustering

Modularity

EdgeCluster

wvRN

Majority

六、Experiments

本節(jié)對許多多標(biāo)簽分類任務(wù)進(jìn)行徹底評估，并分析其在多個參數(shù)中的敏感度。

6.1 Multi-Label Classification

為了便于我們的方法與相關(guān)基準(zhǔn)方法之間的比較，我們使用與[39，40]中完全相同的數(shù)據(jù)集和實(shí)驗(yàn)程序。 具體來說，我們隨機(jī)采樣標(biāo)記節(jié)點(diǎn)的一部分（TR），并將其用作訓(xùn)練數(shù)據(jù)。 其余節(jié)點(diǎn)用作測試。 我們重復(fù)此過程10次，并報告Macro-F1和Micro-F1的平均性能。 如果可能，我們直接在此處報告原始結(jié)果[39，40]。

對于所有模型，我們使用由LibLinear 擴(kuò)展實(shí)現(xiàn)的一對一邏輯對數(shù)回歸，以返回最可能的標(biāo)簽，如[39]所示。 我們提供（γ= 80，w = 10，d = 128）的Deep-Walk結(jié)果。 （SpectralClustering，Modularity，EdgeCluster）的結(jié)果使用了Tang和Liu的首選維數(shù)d = 500。

（1）BlogCatalog

（2）Flickr

在此實(shí)驗(yàn)中，我們將Flickr網(wǎng)絡(luò)上的訓(xùn)練率（TR）從1％更改為10％。 這相當(dāng)于在整個網(wǎng)絡(luò)中大約有800至8,000個節(jié)點(diǎn)被標(biāo)記為分類。 表3給出了我們的結(jié)果，與先前的實(shí)驗(yàn)一致。 相對于Micro-F1，DeepWalk優(yōu)于所有基準(zhǔn)方法至少3％。 此外，當(dāng)僅標(biāo)記了圖表的3％時，其他方法已經(jīng)有了10％的數(shù)據(jù)，Micro-F1性能也優(yōu)于其他所有方法。 換句話說，DeepWalk的訓(xùn)練數(shù)據(jù)不到60％，表現(xiàn)就優(yōu)于基準(zhǔn)方法。 它在Macro-F1中的性能也相當(dāng)好，最初的性能接近SpectralClustering，但差距僅達(dá)到1％。

（3）YouTube

YouTube網(wǎng)絡(luò)比我們之前嘗試過的網(wǎng)絡(luò)要大得多，并且它的規(guī)模使我們無法運(yùn)行兩種基準(zhǔn)方法（Spectral Clustering和Modularity）。 它比我們之前考慮的更接近真實(shí)世界的圖。

表4中列出了將訓(xùn)練比率（TR）從1％更改為10％的結(jié)果。它們表明，DeepWalk在創(chuàng)建圖形表示形式EdgeCluster方面明顯優(yōu)于基準(zhǔn)方法。 當(dāng)使用1％的標(biāo)記節(jié)點(diǎn)進(jìn)行測試時，Micro-F1可以提高14％。Macro-F1顯示相應(yīng)的10％的增加。 隨著訓(xùn)練數(shù)據(jù)的增加，這種領(lǐng)先優(yōu)勢逐漸縮小，但是DeepWalk在Micro-F1中領(lǐng)先3％，而在Macro-F1中令人印象深刻的5％改善。

此實(shí)驗(yàn)展示了使用社交表示學(xué)習(xí)進(jìn)行多標(biāo)簽分類可能帶來的性能優(yōu)勢。 DeepWalk可以縮放到大圖，并且在這種稀疏標(biāo)記的環(huán)境中表現(xiàn)出色。

6.2 Parameter Sensitivity

為了評估DeepWalk的參數(shù)化更改如何影響其對分類任務(wù)的性能，我們對兩個多標(biāo)簽分類任務(wù)（Flickr和BlogCatalog）進(jìn)行了實(shí)驗(yàn)。 為了簡潔起見，我們已固定窗口大小和步行長度以強(qiáng)調(diào)局部結(jié)構(gòu)（w = 10，t = 40）。 然后，我們更改潛在維數(shù)（d），每個頂點(diǎn)開始的遍歷數(shù)（γ）以及可用的訓(xùn)練數(shù)據(jù)量（TR），以確定它們對網(wǎng)絡(luò)分類性能的影響。

（1）Effect of Dimensionality

參數(shù)說明：

文中使用固定的window size和walk length： w = 10 , t = 40 w = 10,t = 40 w=10,t=40

d : 維 度 d:維度 d:維度

γ \gamma γ：每個頂點(diǎn)開始的walk數(shù)量

T R T_R TR ：學(xué)習(xí)率

實(shí)驗(yàn)說明：

圖5a1和5a3測試了改變維度和學(xué)習(xí)率的效果。Flickr和BlogCatalog的性能相當(dāng)一致，表明模型的最佳維數(shù)取決于訓(xùn)練實(shí)例的數(shù)量。

圖5a2和5a3研究了改變每個頂點(diǎn)的維數(shù)和游走次數(shù)的影響。維度之間的相對性能在不同的 γ \gamma γ值下是相對穩(wěn)定的。

（2）Effect of sampling frequency

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

七、Related Work

7.1 Relational Learning

關(guān)系分類（或集體分類）方法[15、25、32]使用數(shù)據(jù)項(xiàng)之間的鏈接作為分類過程的一部分。 集體分類問題中的精確推論是NP-Hard的，解決方案集中在近似推論算法的使用上，這可能無法保證收斂。

與我們工作最相關(guān)的關(guān)系分類算法通過學(xué)習(xí)集群[33]，在附近節(jié)點(diǎn)之間添加邊緣[14]，使用PageRank [24]或通過擴(kuò)展關(guān)系分類以將其他特征考慮在內(nèi)來整合社區(qū)信息[43] 。 我們的工作采用了截然不同的方法。 代替新的近似推理算法，我們提出了一種學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)表示的過程，然后可以將其用于現(xiàn)有的推理過程（包括迭代過程）。

我們還提出了許多用于從圖形生成特征的技術(shù)[13、17、39-41]。 與這些方法相比，我們將特征創(chuàng)建過程構(gòu)架為表示學(xué)習(xí)問題。

已經(jīng)提出了Graph Kernels [42]作為使用關(guān)系數(shù)據(jù)作為分類過程的一部分的方法，但是除非近似[20]，否則它會非常緩慢。 我們的方法是互補(bǔ)的； 我們將學(xué)習(xí)將其直接用作任何分類方法的特征，而不是將結(jié)構(gòu)編碼為內(nèi)核函數(shù)的一部分。

7.2 Unsupervised Feature Learning

已經(jīng)提出了分布式表示來建模概念之間的結(jié)構(gòu)關(guān)系[18]。 這些表示通過反向傳播和梯度下降進(jìn)行訓(xùn)練。 計算成本和數(shù)值不穩(wěn)定導(dǎo)致這些技術(shù)被放棄了將近十年。 最近，分布式計算允許訓(xùn)練更大的模型[4]，并且出現(xiàn)了無監(jiān)督學(xué)習(xí)算法的數(shù)據(jù)增長[10]。 分布式表示通常通過神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，這些網(wǎng)絡(luò)在諸如計算機(jī)視覺[22]，語音識別[8]和自然語言處理[1，7]的各個領(lǐng)域都取得了進(jìn)步。

八、Conclusion

DeepWalk是學(xué)習(xí)潛在社交結(jié)點(diǎn)表征的新方法，算是network embedding的開山之作——借鑒NLP中詞向量的思想來做網(wǎng)絡(luò)節(jié)點(diǎn)表示，后面有幾篇論文也是利用隨機(jī)游走構(gòu)建概率模型，用詞向量中的Negative Sampling（負(fù)采樣）解決相應(yīng)問題。

DeepWalk從一個簡單的角度切入，用現(xiàn)有的NLP中的skip-gram模型結(jié)合，在一個全新的且尚未成為主流的問題中得到一個行之有效的解。DeepWalk利用截斷隨機(jī)游走的局部信息作為輸入，學(xué)習(xí)了一種能編碼網(wǎng)絡(luò)結(jié)構(gòu)信息的表示方法。然后用該方法挑戰(zhàn)多標(biāo)簽分類任務(wù)中表現(xiàn)有效。

作為一種在線學(xué)習(xí)算法，DeepWalk也是可擴(kuò)展的，它能夠?yàn)橐蛱蠖鵁o法運(yùn)行譜方法的圖創(chuàng)建有效的表示。DeepWalk明顯優(yōu)于其他設(shè)計用于稀疏操作的方法；文中還展示該方法是可并行的，運(yùn)行works同時更新模型的不同部分。

九、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）圖神經(jīng)網(wǎng)絡(luò)—基于隨機(jī)游走的早期研究（一）：DeepWalk & Node2Vec

機(jī)器翻譯 深度學(xué)習(xí)

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。