網路嵌入(2)LINE

10-04

網路嵌入(2)LINE

這篇論文同樣是做網路嵌入，文章的主要特點是：

適合任意尺寸的網路，不論是有向圖還是無向圖還是帶權圖。
本文提出的目標函數（objective function）同時考慮了網路局部特徵和全局特徵。
提出一種邊採樣的演算法，可以很好地解決SGD的效率問題。（這部分沒怎麼看懂，因此沒寫出來，感興趣的可以去看看原文）
本文提出的網路表示方法十分高效，可以在小時範圍內的單機節點上學習百萬級頂點網路的表示。

簡介

Introduction介紹了什麼是網路表示，可以用在哪些方面，然後談及前人在網路表示任務的一些嘗試等等。

本文將下面兩種情況的兩個頂點歸結為相似頂點：

如果兩個頂點之間有一條強連接的邊（權重很大的邊），那麼這兩個頂點就是相似的。圖中頂點6與7就是這種相似。
如果兩個頂點共享了很多相同的鄰居頂點，那麼這兩個頂點也是相似的。圖中頂點5和6雖然沒有直接相連，但是他們同時連接到了頂點1234，所以頂點5和6也是相似的。

這兩種相似性在文中被描述成了1階相似性和2階相似性。1階相似性認為兩個頂點的邊權重越大，兩個頂點越相似。2階相似性認為兩個頂點的共同鄰居越多，兩個頂點越相似。

問題定義

這部分定義了後面要用到的幾個概念，這裡摘抄了知乎中一篇文章的翻譯：

1.信息網路

2.一階相似性

3.二階相似性

4.大規模信息網路嵌入

演算法部分

首先來看1階相似性，前面說到1階相似性是用來衡量兩個直接相連的頂點的相似性的，邊的權值越大相似性越高。那麼怎麼將這樣的概念用可計算的形式表示出來呢？文中給出的公式是這樣的：

其實p1就是兩個頂點的向量表示乘積的simoid函數。為什麼是這種形式文中也沒給出詳細的解釋。接下來考慮1階相似性的先驗概率，其實就是 $(i,j)$ 這條邊的權重 $w_{ij}$ 占所有權重之和的比例。從變化趨勢來分析， $w_{ij}$ 越大， $p_1$ 越大，與1階相似性的變化趨勢相同，反之亦然。先驗概率的公式如下：

如何將兩個概率聯繫在一起？文中定義了一個函數表示兩個概率分布的距離：

定義了這個函數後，優化的目標就是縮小兩個概率分布的距離，形象化來說就是，使得兩個概率分布盡量相似，即將左圖的概率分布優化成右邊概率的分布的形式。這個距離在文中被定義成兩個概率分布的KL散度。帶入公式後得到最終的距離函數為：

接下來看2階相似性的計算，2階相似性描述了兩個頂點的鄰居相似度，文中定義2階相似度的公式如下：

熟悉NLP的話會發現其實這就是計算詞向量時用到的公式之一。這個公式會用到兩個向量，一個是要求的頂點表示向量，另一個是頂點作為上下文時的表示向量，這跟計算詞向量的過程是一樣的。同樣需要為這個概率分布找到一個先驗概率：

這個概率可以理解為當前節點是 $v_i$ 的情況下，連接到它的鄰居 $v_j$ 的概率，分子是 $(v_i,v_j)$ 這條邊的權值，分母是從這個頂點出去的所有邊的權值之和。為什麼這個先驗概率可以代表2階相似性呢？我是這樣理解的，回顧一下2階相似性的定義，鄰居頂點越多越相似，並且還跟邊的權值有關，考慮下面這個圖，對於i和j，他們共同的鄰居有3個，那麼可以對應地寫出頂點i和j的先驗概率序列，如果這兩個序列越相似，則頂點i和j就越相似。