[Graph Embedding] LINE

在上一篇文章中，我們介紹了Graph Embedding的經典方法DeepWalk。DeepWalk沒有明確提供闡明保留哪些網絡屬性的目標函數，DeepWalk使用隨機遊走來擴展節點的領域，類似dfs（深度優先搜索）；而LINE使用的是bfs（廣度優先搜索）的思想來擴展節點的領域。此外，DeepWalk只能用在無權圖上，而LINE可以使用在各種網絡上：無向圖、有向圖、無權圖和有權圖。

Introduction

LINE提出了一種新的對圖中節點相似性的定義：

• first-order proximity

  一階相似度描述的是圖中存在邊相連接的2個節點 ( u , v ) (u,v) (u,v)相似的程度，可以用邊的權值 w u , v w_{u,v} wu,v​來定義2個節點的一階相似度。如上圖中，節點6和節點7的邊是最粗的，表示他們的一階相似度是最高的（文中規定一階相似度 ≥ 0 \geq0 ≥0），所以他們通過Graph Embedding後的表示向量在該向量空間中應該最接近；節點5和節點6直接按不存在邊，所以他們的一階相似度爲0。

• second-order proximity

  僅用一階相似度並不能表示整個網絡的結構信息，在一個真實世界的信息網絡（real world information network）中，能夠觀察到的邊只佔一小部分，因爲很多其他的邊丟失了。比如上圖中，節點5和節點6之間並沒有邊相連接，但是他們有很多公共的鄰居節點，這表明節點5和節點6應該具有很高的相似度的。

  一個網絡中的一對節點 ( u , v ) (u,v) (u,v)之間的二階相似度是它們的鄰域網絡結構之間的相似性，通俗的講就是2個節點擁有越多相同的鄰居節點，則他們的二階相似度越高。數學上定義 p u   =   ( w u , 1 , ⋅ ⋅ ⋅ , w u , ∣ V ∣ ) p_u \:= \:(w_{u,1},···,w_{u,|V|}) pu​=(wu,1​,⋅⋅⋅,wu,∣V∣​)爲 u u u的一階相似度，則 u u u和 v v v之間的二階相似度定義爲 p u p_u pu​和 p v p_v pv​的相似性。如果兩個節點之間沒有共同的鄰居節點，則他們的二階相似度爲0。

LINE算法原理

1. LINE with First-order Proximity

一階相似度值適用於無向圖，不適用於有向圖。對於任意無向邊 ( i , j ) (i,j) (i,j)，我們定義節點 v i v_i vi​和 v j v_j vj​的聯合概率爲下式（1）
p 1 ( v i , v j ) = 1 1 + e x p ( − u i T ⃗ ⋅ u j ⃗ ) (1) p_1(v_i,v_j) = {{1 \over 1+exp(-\vec{{u_i}^T} \cdot \vec{u_j})}} \tag1 p1​(vi​,vj​)=1+exp(−ui​T ​⋅uj​ ​)1​(1)
上式的 u i ⃗ ∈ R d \vec{u_i} \in R^d ui​ ​∈Rd 是節點 v i v_i vi​在低維空間中的向量表示（這正是Graph Embedding所想要學習到的東西）。

同時定義經驗分佈 p 1 ^ = w i , j W \hat{p_1} = {w_{i,j}\over W} p1​^​=Wwi,j​​，其中 W = ∑ ( i , j ) ∈ E w i , j W = \displaystyle \sum_{(i,j)\in E}{w_{i,j}} W=(i,j)∈E∑​wi,j​

優化的目標是最小化KaTeX parse error: \tag works only in display equations

其中函數 d ( ⋅ , ⋅ ) d(·,·) d(⋅,⋅)是2個概率分佈之間的距離，用KL散度代替 d ( ⋅ , ⋅ ) d(·,·) d(⋅,⋅)並移除一些常數項，得到我們最終的一階相似度的優化目標：
O 1 = − ∑ ( i , j ) ∈ E w i , j   l o g   p 1 ( v i ,   v j ) (3) O_1 = -\displaystyle \sum_{(i,j)\in E}{w_{i,j}\ log\ p_1(v_i,\ v_j)} \tag3 O1​=−(i,j)∈E∑​wi,j​ log p1​(vi​, vj​)(3)

2. LINE with Second-order Proximity

二階相似性都適用於無向圖和有向圖。我們定義兩種類型的向量， u i ⃗ \vec{u_i} ui​ ​表示當 v i v_i vi​被當作節點時候的表示向量（這是最終想要求得的二階相似性的向量表示）； u i ′ ⃗ \vec{{u_i}^{'}} ui​′ ​表示的是當 v i v_i vi​作爲其他節點的上下文頂點時的表示向量。

對於任一有向邊 ( i , j ) (i,j) (i,j)，我們首先定義在給定頂點 v i v_i vi​的條件下，產生上下文節點（鄰居節點） v j v_j vj​的概率爲：
p 2 ( v j ｜ v i ) = e x p ( u j ′ T ⃗ ⋅ u i ⃗ ) ∑ k = 1 ∣ V ∣ e x p ( u k ′ T ⃗ ⋅ u i ⃗ ) (4) p_2(v_j｜v_i) = {{exp(\vec{{u_j^{'}}^T} \cdot \vec{u_i}) \over \displaystyle \sum^{|V|}_{k=1}exp(\vec{{u_k^{'}}^T} \cdot \vec{u_i})}} \tag4 p2​(vj​｜vi​)=k=1∑∣V∣​exp(uk′​T ​⋅ui​ ​)exp(uj′​T ​⋅ui​ ​)​(4)
其中 ∣ V ∣ |V| ∣V∣爲上下文節點（鄰居節點）的數量

如何理解式(3)： p 2 ( ⋅ ∣ v i ) p_2(·|v_i) p2​(⋅∣vi​)定義的是節點 v i v_i vi​關於它的上下文節點（鄰居節點）的條件分概率分佈。如果2個節點二階相似性高，那麼他們擁有更多的鄰居節點，即他們關於上下文節點的條件概率分佈會更加相似，最終學習到的向量表示就會更加接近。

同時定義經驗分佈 p 2 ^ ( v j   ∣   v i ) = w i , j d i \hat{p_2}(v_j\ |\ v_i) = {w_{i,j}\over d_i} p2​^​(vj​ ∣ vi​)=di​wi,j​​，其中 w i , j w_{i,j} wi,j​是邊 ( i , j ) (i,j) (i,j)的權重， d i d_i di​是節點 v i v_i vi​的出度，在有權圖中，$d_i=\displaystyle \sum_{k\in N(i)}{w_{i,k}} $

優化的目標是最小化KaTeX parse error: \tag works only in display equations

其中函數 d ( ⋅ , ⋅ ) d(·,·) d(⋅,⋅)是2個概率分佈之間的距離， λ i \lambda_i λi​表示的是節點的重要度，可以通過節點的度或者PageRank算法來衡量。爲了簡便，我們令 λ i = d i \lambda_i = d_i λi​=di​，並且仍然用KL散度代替 d ( ⋅ , ⋅ ) d(·,·) d(⋅,⋅)和移除一些常數項，得到我們最終的二階相似度的優化目標：
O 2 = − ∑ ( i , j ) ∈ E w i , j   l o g   p 2 ( v j ∣ v i ) (6) O_2 = -\displaystyle \sum_{(i,j)\in E} w_{i,j} \ log\ p_2(v_j|v_i) \tag6 O2​=−(i,j)∈E∑​wi,j​ log p2​(vj​∣vi​)(6)

3. Combining first-order and second-order proximities

如何將一階相似度的優化目標與二階相似度的優化目標合併呢？作者採用的是分別以一階和二階相似度爲優化目標，學習出節點的表示向量，然後將每個節點的2種表示向量進行拼接。

如何將一階相似度與二階相似度相結合是作者留給讀者接下來的任務（這是2015年的論文，這一任務相必已經有各種idea了，感興趣的去查查）。

優化方法

Negative Sampling

由於在式（6）中，計算條件概率分佈需要遍歷圖上所有的點，計算開銷很大，所以作者採用了NLP（自然語言處理）中的負採樣的方法，該方法根據每條邊 ( i , j ) (i,j) (i,j)的一些噪聲分佈對多條負邊進行採樣。 更具體地說，它爲每條邊 ( i , j ) (i,j) (i,j)指定以下目標函數：
l o g   σ ( u j ′ T ⃗ ⋅ u i ⃗ ) + ∑ i = 1 K E v n ～ P n ( v ) [ l o g   σ ( − u n ′ T ⃗ ⋅ u i ⃗ ) ] (7) log\ \sigma(\vec{{u_j^{'}}^T} \cdot \vec{u_i}) +\displaystyle \sum^{K}_{i=1} E_{v_n}～P_n(v) [log\ \sigma(\vec{{-u_n^{'}}^T} \cdot \vec{u_i})] \tag7 log σ(uj′​T ​⋅ui​ ​)+i=1∑K​Evn​​～Pn​(v)[log σ(−un′​T ​⋅ui​ ​)](7)
其中 σ ( x ) = 1 / ( 1 + e x p ( − x ) ) \sigma(x) = 1/(1 + exp(-x)) σ(x)=1/(1+exp(−x))是一個sigmoid函數， P n ( v ) ∝ d v 3 / 4 P_n(v) \propto {d_v}^{3/4} Pn​(v)∝dv​3/4，其中的 d v d_v dv​爲節點v的出度。對於式（7）採用異步隨機梯度下降（asynchronous stochastic gradient algorithm）的方法進行參數的更新。

關於負採樣，這裏不多加贅述，想要了解的可以在原文4.2節中進行了解。

Edge Sampling

主要到目標函數式（3）和式（6）前都要乘邊的一個權重係數 w i , j w_{i,j} wi,j​，因爲邊與邊之間的 w i , j w_{i,j} wi,j​的差異很大，所以會出現梯度爆炸和梯度消失的情況，學習率很難進行選擇。

第一種方法是將一條邊拆解爲多條邊，比如將一條權重爲 w w w的邊拆解爲 w w w條權重爲1的邊，這樣所有的邊都具有相同的權重。但是這樣做會顯著的增加存儲圖所需的內存大小，尤其是當邊的權重很大的時候。

第二種方法就是從原始的邊的集合中採樣一定數量的邊，採樣的概率正比與邊的權重，然後按照上面所說的第一種方法，對邊進行拆解。採樣所使用到的是alias table method，它僅需要 O ( 1 ) O(1) O(1)的時間複雜度進行採樣。

其他問題

Low degree vertices

對於如何準確對度很小的節點做Embedding，尤其是在計算二階相似性的時候，十分依賴於節點的上下文節點（鄰居節點）。作者提出可以利用鄰居的鄰居節點構造樣本進行學習。

New vertices

當有新的邊加入時，如果知道了它和已經存在的節點之間的連接關係，則可以直接獲得它的經驗分佈 p 1 ^ ( ⋅ , v i ) \hat{p_1}(·,v_i) p1​^​(⋅,vi​)和 p 2 ^ ( ⋅ ∣ v i ) \hat{p_2}(·|v_i) p2​^​(⋅∣vi​)，然後優化下面的兩個目標函數之一
− ∑ j ∈ N ( i ) w j , i   l o g   p 1 ( v j ,   v i ) ,   o r − ∑ j ∈ N ( i ) w j , i   l o g   p 2 ( v j ∣ v i ) , (8) -\displaystyle \sum_{j\in N(i)}{w_{j,i}\ log\ p_1(v_j,\ v_i)}, \ or -\displaystyle \sum_{j\in N(i)} w_{j,i} \ log\ p_2(v_j|v_i), \tag8 −j∈N(i)∑​wj,i​ log p1​(vj​, vi​), or−j∈N(i)∑​wj,i​ log p2​(vj​∣vi​),(8)
如果節點與其他的節點都不相連的話，就需要使用到節點的特徵信息，並且作者將這個問題作爲接下來研究的方向。

 
論文原文：LINE: Large-scale Information Network Embedding