LINE 出自論LINE: Large-scale Information Network Embedding，與 DeepWalk 相比，比較明顯的區別在于：

DeepWalk 使用的深度優先搜索策略，而 LINE 使用了廣度優先搜索策略。

DeepWalk 僅適用于無權圖，而LINE模型適用于帶權圖與無權圖。

下圖展示了一個簡單的圖，圖中的邊既可以是有向的，也可以是無向的，并且邊的粗細程度也代表了權重的大小：

一階相似度

作者認為可以用一階相似度描述圖中成對頂點之間的局部相似度，連接兩個節點的邊權重越大，則一階相似度越高。若兩個節點之間不存在邊，則認為一階相似度為 0。例如圖中的節點６、７在低維空間中應該是比較靠近的，因為連接二者的邊具有很大的權重，而5、6之間則的一階相似度則為0。

為了能夠通過節點的低維向量表示一階相似度，我們還需要定義一個優化目標。假設用 $u_i,u_j$ 作為節點的低維向量表示(Embedding向量)，那么一階相似度的計算就轉換為學習一種函數映射 $f(u_i,u_j)$，使得其映射結果可以表示邊的權重。對于每一條無向邊 $(i,j)$，定義頂點 $v_i,v_j$ 的聯合概率密度為：
$$p_1(v_i,v_j)=\frac{1}{1+exp(?u_i^T?u_j)}$$
如果兩個向量相似，則內積的結果也相對比較大，將內積結果作為 sigmoid 函數的輸入，最終得到兩個節點的聯合概率分布 $p_1(v_i,v_j)$。

在得到聯合概率分布之后，還需要一個“參照物”來指導它的學習，論文中將兩個節點之間邊的權重占比視為經驗分別，并將它作為學習目標：
$$\begin{gathered} {\hat{p}}_1(i,j)=\frac{w_{ij}}{W} \\ W=\sum _{(i,j)\in E}{w}_{ij} \end{gathered}$$
于是最終的優化目標是使得聯合概率分布盡量接近經驗分布，而K-L散度可以表示數據原始分布p和近似分布q之間的對數差值的期望，因此只要優化 $p_1(v_i,v_j)$ 與 ${\hat{p}}_1$ 的K-L散度(忽略常數項)，就能使二者的分布盡可能相似：
$$O_1=?\sum _{(i,j)\in E}{w}_{ij}log(p_1(v_i,v_j))$$

二階相似度

一階相似度固然可以直接表示節點之間的相似性，但是在真實環境下的信息網絡往往存在大量的信息缺失，而許一階相似度為0的節點，他們本質上相似度也很高。

仔細觀察節點5、6，發現他們具有非常相似的鄰居節點(1，2，3，4)，這其實也表明5、6兩個節點應該是相似的，作者使用二階相似度來描述這樣的關系，若兩個節點不存在共同的鄰居節點，則二階相似度為0。這意味著，如果節點5的低維向量表示同時與節點1，2，3，4的低維向量表示相似，并且節點6的低維向量表示同時與節點1，2，3，4的低維向量表示相似，那么節點5與6的低維向量表示也就是相似的。

根據一階相似度的理論，我們可以將兩個節點的向量內積 用sigmoid函數轉換為概率 來表示兩個節點間邊的權重。但是在二階相似度的表示問題中，我們需要表示一個節點與周圍多個context節點的相似度，那么就可以使用 softmax 函數將某個節點與周圍節點向量內積的結果轉換為概率。給定節點 $v_i$ 產生節點 $v_j$ 的概率為：
$$p_2(v_j|v_i)=\frac{exp(u_j^{{}^{\prime }T}?u_i)}{{\sum }_{k=1}^{|V|}exp(u_k^{{}^{\prime }T}?u_i)}$$

其中，$u_i,u_j^{\prime }$ 為節點 $i,j$ 低維向量表示，且 $u_j^{\prime }$ 為節點 j 表示為上下文時的向量表示。$|V|$ 表示圖中所有節點的個數。當節點 $k,i$ 之間沒有鄰接關系時，二者向量的內積也就比較小，在理想情況下當兩個節點沒有邊相連時，$exp(u_k^{{}^{\prime }T}?u_i)\to 0$，此時 $p_2(v_j|v_i)$ 僅僅受到節點 $i$ 周圍鄰居節點的影響。 不難發現，這個公式將節點 $i$ 與鄰居節點的相似度轉換為條件概率。

再定義經驗分布為：
$${\hat{p}}_2(v_j|v_i)=\frac{w_{ij}}{d_i}$$
其中，$w_{ij}$ 是邊 $(i,j)$ 的權重，$d_i={\sum }_{k\in N(i)}{w}_{ik}$，$N(i)$ 為節點之間與節點 $i$ 相連的鄰居節點集合。對于無權圖而言，$d_i$ 是節點 $v_i$ 的出度。

現在的目標是讓條件概率$p_2(v_j|v_i)$盡可能的與經驗分布${\hat{p}}_2(v_j|v_i)$相似：
$$O_2=?\sum _{i\in V}{\lambda }_{i}d({\hat{p}}_2(?|v_i),p_2(?|v_i))$$
其中，${\lambda }_i$ 是表示節點重要性的因子，可以通過預先計算節點的度數或者PageRank算法來得到。$d(?,?)$ 用于度量兩個分布之間的差距。

更具體的，假設 ${\lambda }_i=d_i$，使用忽略常數項的 KL 散度公式，則有：
$$O_2=?\sum _{(i,j)\in E}{w}_{ij}log(p_2(v_j|v_i))$$
對比一階和二階相度的概率函數，我們可以發現其實兩者是非常相似的，只不過是二階相似性每個節點有兩個embedding，一個作為中心點的embeding和一個作為context時候的embeding。最終二階使用的是作為中心點的embeding。實際使用的時候，對一階近鄰和二階近鄰分別訓練，然后將兩個向量拼接起來作為節點的向量表示。

優化技巧

負采樣：

計算二階相似度時，softmax 函數的分母計算需要遍歷所有頂點，計算量太大了，論文采用了與 word2vec 論文類似的負采樣優化的技巧，對邊進行抽樣生成負樣本，每條邊被抽中的概率為邊的權重。于是，將每一條邊$(i,j)$對應的目標函數變為：
$$log\sigma (u_j^{{}^{\prime }T}?u_i)+\sum _{i=1}^K{E}_{v_n～P_n(v)}[log\sigma (?u_n^{{}^{\prime }T}?u_i)]$$

其中，$\sigma$ 為sigmoid函數，K 為負樣本的個數。負采樣的好處在于：梯度下降的過程中只需要更新節點 $i,j$ 以及 K 個負采樣的節點的向量即可。

以下是個人對公式的理解，不一定準確，如果有錯還請指正：

感覺論文中的公式似乎表達的有點別扭，個人認為用下面的公式比較好理解：
$$O_2=log\sigma (u_j^{{}^{\prime }T}?u_i)+\sum _{k=1}^K{E}_{v_k～P_n(v)}[log\sigma (?u_k^{{}^{\prime }T}?u_i)]$$
其中$E_{v_k～P_n(v)}$ 表示取出 $v_k$ 的期望值，而$P_n(v)$ 表示采樣時用的概率分布，可以是：
$$P_n(v)=\frac{(d_v{)}^{3/4}}{{\sum }_{j=1}^{|V|}(d_j{)}^{3/4}}$$
這個取 3/4 次冪的運算會產生一個效果，就是稍微增加低頻節點的采樣概率，降低高節點的采樣概率。

可根據下圖（google 的搜索欄中輸入 “plot y = x^(3/4) and y = x” 可以快速畫圖）的對比看出來：

引入負采樣后，最終得到的目標函數為：
$$O_2=?\sum _{(i,j)\in E}{w}_{ij}(log\sigma (u_j^{{}^{\prime }T}?u_i)+\sum _{i=1}^K{E}_{v_n～P_n(v)}[log\sigma (?u_n^{{}^{\prime }T}?u_i)])$$
邊采樣：

從上面的公式可以看到，每個樣本都有一個權重 $w_{ij}$，有的樣本w很高，有的樣本w很低。在進行反向傳播的時候，如果學習率過高，會導致w很大的樣本梯度爆炸，如果學習率設置很小，會導致w很低的樣本訓練緩慢。為了解決這個問題，文中提出了邊緣采樣(Edge Sampling)的方法，將所有樣本的系數都置為1，對圖中的邊重復采樣來構造多個相同的正樣本，采樣率與權重 $w_{ij}$ 成正比。

擴充鄰居：

對于一些頂點由于其鄰接點非常少會導致embedding向量的學習不充分，論文提到可以利用鄰居的鄰居構造樣本進行學習。為了解決這個問題，論文中提出了一個擴展鄰居的辦法，添加二階鄰居。所謂二階鄰居，就是從該節點到鄰居節點之間存在兩跳。

節點{1,2,3,4}就是節點7的二階鄰居，節點{8,9,10}就是節點6的二階鄰居。二階鄰居的權重計算方法如下：
$$w_{ij}=\sum _{k\in N(i)}{w}_{ik}\frac{w_{kj}}{d_k}$$

核心代碼

這部分參考了淺夢的博客：【Graph Embedding】LINE：算法原理，實現和應用。

首先輸入就是兩個頂點的編號，然后分別拿到各自對應的embedding向量，最后輸出內積的結果。 真實 label 定義為1或者-1。最終模型輸出內積，然后可以對內積結果進行優化。

這里的實現中把1階和2階的方法融合到一起了，可以通過超參數order控制是分開優化還是聯合優化，論文推薦分開優化。

# 損失函數 def line_loss(y_true, y_pred):return -K.mean(K.log(K.sigmoid(y_true*y_pred)))# 構造模型 def create_model(numNodes, embedding_size, order='second'):v_i = Input(shape=(1,))v_j = Input(shape=(1,))first_emb = Embedding(numNodes, embedding_size, name='first_emb')second_emb = Embedding(numNodes, embedding_size, name='second_emb')context_emb = Embedding(numNodes, embedding_size, name='context_emb')# 一階相似度v_i_emb = first_emb(v_i)v_j_emb = first_emb(v_j)# 二階相似度v_i_emb_second = second_emb(v_i)v_j_context_emb = context_emb(v_j)# 節點 i,j 的內積first = Lambda(lambda x: tf.reduce_sum(x[0]*x[1], axis=-1, keep_dims=False), name='first_order')([v_i_emb, v_j_emb])# 節點 i 與 節點j上下文表示 的內積second = Lambda(lambda x: tf.reduce_sum(x[0]*x[1], axis=-1, keep_dims=False), name='second_order')([v_i_emb_second, v_j_context_emb])if order == 'first':output_list = [first]elif order == 'second':output_list = [second]else:output_list = [first, second]model = Model(inputs=[v_i, v_j], outputs=output_list)

參考文章：

Graph Embedding：從DeepWalk到SDNE - 知乎

Graph Embedding之探索LINE

推薦系統的中 Embedding 的應用實踐 | 盧明冬的博客

總結

以上是生活随笔為你收集整理的【图嵌入】Graph Embedding 方法之 LINE 原理解读的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。