LINE

Abstract

LINE 是一種將大規(guī)模網(wǎng)絡結點表征成低維向量的算法，可很方便用于網(wǎng)絡可視化梗搅，結點分類社裆，鏈路預測，推薦双仍。
source code

Advantage

LINE相比于其他算法來說有如下幾點優(yōu)勢：

1. 適用于大規(guī)模網(wǎng)絡枢希。
2. 有明確的目標函數(shù)（這一點DEEPWALK是沒有的，DW沒有提出一個明確的目標函數(shù)來告知什么網(wǎng)絡屬性被保留下來朱沃，直觀上講苞轿，DW更偏向于結點間有更高的二階相似度的有相似的表征）該目標函數(shù)既反映了局部結構又反映了全局結構。LINE同時考慮了一階相似度和二階相似度

• 局部結構：頂點間的一階相似性（由觀察到的頂點間的鏈接強度表示逗物，鏈接強度大的兩結點有相似的向量表示搬卒，不足以反映圖的全局結構，因此引入二階相似度）
• 全局結構：頂點間的二階相似性（由頂點間的共享鄰域來決定翎卓，具有共享鄰居的結點更可能是相似的）

用一張圖來直觀理解

image

關聯(lián)圖中6,7結點的是一條強邊契邀，因此結點6,7的向量表示應該相似（一階相似度）；而結點5,6因為共享了相似的鄰居失暴，因此5,6的向量表示也應該相似（二階相似度）坯门。

3. 提出一種新穎的邊采樣的方法解決了隨機梯度下降算法的局限性。（由于現(xiàn)實網(wǎng)絡中邊權的方差往往是非常大的逗扒，SGD可能導致梯度爆炸古戴，損害性能）

ps：具體措施：以正比于邊權大小的概率來采樣邊，將被采樣的邊作為二值邊（0 無邊缴阎，1有邊）進行模型更新允瞧。
在這種采樣過程中，目標函數(shù)保持不變，邊的權重不再影響梯度述暂。

4. LINE可適用于任何類型的網(wǎng)絡：有向無向痹升，有權無權（DW只能適用于無權網(wǎng)絡）

Definition

• 一階相似度：兩個結點u，v之間的邊權代表u與v之間的一階相似度畦韭。若u疼蛾，v之間無邊，則一階相似度為0.

  
  
  image

• 二階相似度：兩個結點u艺配，v的二階相似度由兩個結點共同鄰居的個數(shù)決定察郁。
  image

Model Description

LINE with First-order Proximity

首先，了解一下KL散度和一階相似度的概念

KL散度Dkl（p转唉，q):指用q分布來近似p分布的信息損失皮钠。

一階相似度：對于兩個有邊鏈接的頂點，其邊的強度越大赠法，則該兩頂點關系越密切麦轰，即越相似。

模型大體過程：

1. 首先計算兩個結點的聯(lián)合概率密度

   
   
   image

2. 其次計算兩結點經(jīng)驗分布概率

   
   
   image

3. 最小化下列目標函數(shù)
   image
   
   
   這里的d砖织，兩個分布的距離可以用KL散度來計算款侵，最終目標函數(shù)如下：
   image
   
   即對圖中每條邊，計算相關聯(lián)兩頂點的kl散度侧纯，求各個結點向量表示ui新锈，使得該目標函數(shù)達到最小。

（個人理解PS：但是為什么使得聯(lián)合概率分布近似經(jīng)驗分布的信息損失最小就是保留一階相似度眶熬？經(jīng)驗分布妹笆，邊權除以邊權總和一定程度上體現(xiàn)了邊權的重要性，而邊權的大小又是描繪一階相似度的重要信息聋涨，因此可以將該經(jīng)驗分布理解成保留了一階相似度的分布晾浴，而求各個結點的向量表示，使得兩節(jié)點的聯(lián)合分布近似于經(jīng)驗分布的信息損失最小牍白，即該組向量表示就是體現(xiàn)一階相似度的最優(yōu)的向量表示）

上述一階相似度只適用于無向圖脊凰，而不適用于有向圖。

LINE with Second-order Proximity

首先要理解二階相似度的相關概念

1. 二階相似度既適用于有向圖也適用于無向圖茂腥。
2. 二階相似度即指狸涌，有相同上下文（鄰居）的頂點越相似。

模型大體過程

1. 首先最岗，每個頂點由兩個向量表示帕胆，ui表示該頂點i本身的向量表示，當頂點i被當做是其他頂點的上下文來考慮時般渡，ui’為其向量表示懒豹。
2. 其次計算在頂點i出現(xiàn)的條件下芙盘，下一個頂點是j的概率（條件概率）
   image
   利用該公式，我們可以算出頂點i的條件分布脸秽，即
   image
   儒老。
   因此 根據(jù)二階相似度的定義，我們不難推出记餐，具有相似條件分布的頂點彼此相似驮樊。

3. 因此，類似于一階相似度片酝，為了更好保留二階相似度囚衔，我們需要使得每個結點i的條件分布近似于自身條件經(jīng)驗分布的信息損失最小。即最小化下述目標函數(shù)
   image
   
   

   其中λi為每個結點在網(wǎng)絡中的權重（考慮到每個結點在網(wǎng)絡中的重要性可能不同）雕沿。該權重可以通過度來衡量练湿，或者一些算法來計算，比如PageRank算法晦炊。

• 條件經(jīng)驗分布如下計算

  
  
  image

4. 最后仍然使用kl散度來衡量兩分布的距離鞠鲜。
   最終目標函數(shù)如下：

   
   
   image

通過學習每個結點i的兩個向量表示ui，ui’來最小化上述目標函數(shù)断国，最終可以得到每個結點的向量表示。

Combining first-order and second-order proximities

那么如何同時結合一階相似度和二階相似度呢榆苞？這篇論文提出時涉及了兩種方案：

1. 分別訓練基于一階相似度的和基于二階相似度的稳衬，得到每個結點的兩種向量表示，
   再連接該兩種向量表示坐漏。
2. 同時優(yōu)化兩個目標函數(shù)（3）和（6）來學習向量表示薄疚。留待未來研究。

Model Optimization

ps：個人對這部分理解不夠成熟赊琳，可能有誤街夭。

優(yōu)化上述目標函數(shù)（6）需要很大的計算開銷（需要對每一條邊進行采樣來訓練模型）。這里使用負采樣來解決問題躏筏。

• Optimization via Edge Sampling

負采樣：根據(jù)一定的策略選取部分更重要的邊來進行訓練板丽，每次訓練只對神經(jīng)網(wǎng)絡的部分權重進行更新，大大減少了SGD過程中的計算量趁尼。

（ps：正比于邊的權重作為概率進行邊的采樣埃碱。一般來說，邊權越大的應該被采樣的概率要越高酥泞，在語言學領域：出現(xiàn)單詞對頻率越高的應該被采樣的概率越大）
上述這種邊采樣策略提高了隨機梯度下降的效率砚殿。

• 時間復雜度

LINE 時間復雜度是邊的線性函數(shù)，與頂點個數(shù)V無關芝囤。如下：

image

Discussion

1. 低度頂點的嵌入表示

由于低度頂點鄰居數(shù)目極少似炎，原網(wǎng)絡中提供的信息有限辛萍，尤其在基于二階相似度的LINE算法中是非常依賴于頂點的鄰居數(shù)目的，那么如何確定低度頂點的向量表示呢羡藐？

一種直觀的方法：添加更高階的鄰居（如鄰居的鄰居）來作為該低度結點的直接鄰居贩毕。 與新添鄰居邊的權重如下：

image

2. 如何找到網(wǎng)絡中新添加頂點的向量表示

image

之后通過最小化目標函數(shù)（3）或（6）可得到新加頂點i的向量表示

image

6.Conclusion

LINE 適用于大規(guī)模網(wǎng)絡店印；既保留了一階相似度，又保留了二階相似度倒慧；提出邊采樣算法按摘，只采樣部分且只更新神經(jīng)網(wǎng)絡部分權值，并且將采樣的邊處理成二進制邊纫谅，解決了加權邊梯度下降的局限性（即梯度爆炸----邊權直接乘以梯度炫贤，且若邊權方差過大 可能導致梯度爆炸），加快了效率付秕。

未來的拓展：一階二階以外更高階的相似度以及在異構網(wǎng)絡中的應用兰珍。