之前介紹過DeepWalk，DeepWalk使用DFS隨機遊走在圖中進行節點採樣，使用word2vec在採樣的序列學習圖中節點的向量表示。

DeepWalk：演算法原理，實現和應用?

zhuanlan.zhihu.com圖標

LINE也是一種基於鄰域相似假設的方法，只不過與DeepWalk使用DFS構造鄰域不同的是，LINE可以看作是一種使用BFS構造鄰域的演算法。此外，LINE還可以應用在帶權圖中(DeepWalk僅能用於無權圖)。

之前還提到不同的graph embedding方法的一個主要區別是對圖中頂點之間的相似度的定義不同，所以先看一下LINE對於相似度的定義。

LINE 演算法原理

一種新的相似度定義

first-order proximity

1階相似度用於描述圖中成對頂點之間的局部相似度，形式化描述為若 u , v 之間存在直連邊，則邊權 w_{uv} 即為兩個頂點的相似度，若不存在直連邊，則1階相似度為0。 如上圖，6和7之間存在直連邊，且邊權較大，則認為兩者相似且1階相似度較高，而5和6之間不存在直連邊，則兩者間1階相似度為0。

second-order proximity

僅有1階相似度就夠了嗎？顯然不夠，如上圖，雖然5和6之間不存在直連邊，但是他們有很多相同的鄰居頂點(1,2,3,4)，這其實也可以表明5和6是相似的，而2階相似度就是用來描述這種關係的。 形式化定義為，令 p_u=(w_{u,1},...,w_{u,|V|}) 表示頂點 u 與所有其他頂點間的1階相似度，則 u 與 v 的2階相似度可以通過 p_u 和 p_v 的相似度表示。若u與v之間不存在相同的鄰居頂點，則2階相似度為0。

優化目標

1st-order

對於每一條無向邊 (i,j) ，定義頂點 v_i 和 v_j 之間的聯合概率為：

p_1(v_i,v_j)=frac{1}{1+exp(-vec{u}^T_i cdot vec{u}_j)} ， vec{u_i} 為頂點v_i的低維向量表示。（可以看作一個內積模型，計算兩個item之間的匹配程度）

同時定義經驗分布 hat{p_1}=frac{w_{ij}}{W} , W=sum_{(i,j)in E} w_{ij}

優化目標為最小化： O_1=d(hat{p}_1(cdot,cdot),p_1(cdot,cdot))

d(cdot,cdot) 是兩個分布的距離，常用的衡量兩個概率分布差異的指標為KL散度，使用KL散度並忽略常數項後有

O_1=-sum_{(i,j)in E}w_{ij}log{p_1(v_i,v_j)}

1st order 相似度只能用於無向圖當中。

2nd-order

這裡對於每個頂點維護兩個embedding向量，一個是該頂點本身的表示向量，一個是該點作為其他頂點的上下文頂點時的表示向量。

對於有向邊 (i,j) ，定義給定頂點 v_i 條件下，產生上下文(鄰居)頂點 v_j 的概率為 p_2(v_j|v_i)=frac{exp(vec{c}^T_jcdotvec{u}_i)}{sum_{k=1}^{|V|}{exp(vec{c}^T_kcdotvec{u}_i)}} ，其中 |V| 為上下文頂點的個數。

優化目標為 O_2=sum_{iin V}lambda_i d(hat{p}_2(cdot|v_i),p_2(cdot|v_i)) ，其中 lambda_i 為控制節點重要性的因子，可以通過頂點的度數或者PageRank等方法估計得到。

經驗分布定義為： hat{p}_2(v_j|v_i)=frac{w_{ij}}{d_i} , w_{ij} 是邊 (i,j) 的邊權， d_i 是頂點 v_i 的出度，對於帶權圖， d_i=sum_{kin N(I)}W_{ik}

使用KL散度並設 lambda_i = d_i ，忽略常數項，有 O_2=-sum_{(i,j)in E} w_{ij}log{p_2(v_j|v_i)}

優化技巧

Negative sampling

由於計算2階相似度時，softmax函數的分母計算需要遍歷所有頂點，這是非常低效的，論文採用了負採樣優化的技巧，目標函數變為：

log{sigma({vec{c}^T_jcdotvec{u}_i})}+sum_{i=1}^K{E_{v_nsim P_n(v)}[-log{sigma({vec{c}^T_ncdotvec{u}_i})}]} ， K 是負邊的個數。

論文使用 P_n(v)propto d_v^{3/4} ， d_v 是頂點 v 的出度

Edge Sampling

注意到我們的目標函數在log之前還有一個權重係數 w_{ij} ，在使用梯度下降方法優化參數時， w_{ij} 會直接乘在梯度上。如果圖中的邊權方差很大，則很難選擇一個合適的學習率。若使用較大的學習率那麼對於較大的邊權可能會引起梯度爆炸，較小的學習率對於較小的邊權則會導致梯度過小。

對於上述問題，如果所有邊權相同，那麼選擇一個合適的學習率會變得容易。這裡採用了將帶權邊拆分為等權邊的一種方法，假如一個權重為 w 的邊，則拆分後為 w 個權重為1的邊。這樣可以解決學習率選擇的問題，但是由於邊數的增長，存儲的需求也會增加。

另一種方法則是從原始的帶權邊中進行採樣，每條邊被採樣的概率正比於原始圖中邊的權重，這樣既解決了學習率的問題，又沒有帶來過多的存儲開銷。

這裡的採樣演算法使用的是Alias演算法，Alias是一種 O(1) 時間複雜度的離散事件抽樣演算法。具體內容可以參考

Alias Method:時間複雜度O(1)的離散採樣方法?

zhuanlan.zhihu.com圖標

其他問題

低度數頂點

對於一些頂點由於其鄰接點非常少會導致embedding向量的學習不充分，論文提到可以利用鄰居的鄰居構造樣本進行學習，這裡也暴露出LINE方法僅考慮一階和二階相似性，對高階信息的利用不足。

新加入頂點

對於新加入圖的頂點 v_i ，若該頂點與圖中頂點存在邊相連，我們只需要固定模型的其他參數，優化如下兩個目標之一即可：

-sum_{jin N(i)} w_{ji}log{p_1(v_j,v_i)} 或 -sum_{jin N(i)} w_{ji}log{p_1(v_j|v_i)}

若不存在邊相連，則需要利用一些side info，留到後續工作研究。

LINE核心代碼

模型和損失函數定義

LINE使用梯度下降的方法進行優化，直接使用tensorflow進行實現，就可以不用人工寫參數更新的邏輯了~

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

首先輸入就是兩個頂點的編號，然後分別拿到各自對應的embedding向量，最後輸出內積的結果。 真實label定義為1或者-1，通過模型輸出的內積和line_loss就可以優化使用了負採樣技巧的目標函數了~

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)

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])
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)

頂點負採樣和邊採樣

下面的函數功能是創建頂點負採樣和邊採樣需要的採樣表。中規中矩，主要就是做一些預處理，然後創建alias演算法需要的兩個表。

def _gen_sampling_table(self):

# create sampling table for vertex
power = 0.75
numNodes = self.node_size
node_degree = np.zeros(numNodes) # out degree
node2idx = self.node2idx

for edge in self.graph.edges():
node_degree[node2idx[edge[0]]
] += self.graph[edge[0]][edge[1]].get(weight, 1.0)

total_sum = sum([math.pow(node_degree[i], power)
for i in range(numNodes)])
norm_prob = [float(math.pow(node_degree[j], power)) /
total_sum for j in range(numNodes)]

self.node_accept, self.node_alias = create_alias_table(norm_prob)

# create sampling table for edge
numEdges = self.graph.number_of_edges()
total_sum = sum([self.graph[edge[0]][edge[1]].get(weight, 1.0)
for edge in self.graph.edges()])
norm_prob = [self.graph[edge[0]][edge[1]].get(weight, 1.0) *
numEdges / total_sum for edge in self.graph.edges()]

self.edge_accept, self.edge_alias = create_alias_table(norm_prob)

LINE應用

和之前一樣，還是用LINE在wiki數據集上進行節點分類任務和可視化任務。 wiki數據集包含 2,405 個網頁和17,981條網頁之間的鏈接關係，以及每個網頁的所屬類別。 由於1階相似度僅能應用於無向圖中，所以本例中僅使用2階相似度。

本例中的訓練，評測和可視化的完整代碼在下面的git倉庫中，

shenweichen/GraphEmbedding?

github.com圖標

G = nx.read_edgelist(../data/wiki/Wiki_edgelist.txt,create_using=nx.DiGraph(),nodetype=None,data=[(weight,int)])

model = LINE(G,embedding_size=128,order=second)
model.train(batch_size=1024,epochs=50,verbose=2)
embeddings = model.get_embeddings()

evaluate_embeddings(embeddings)
plot_embeddings(embeddings)

分類任務結果

micro-F1: 0.6403

macro-F1:0.5286

結果有一定隨機性，可以多運行幾次，或者稍微調整epoch個數。

可視化結果

參考資料

  • Tang J, Qu M, Wang M, et al. Line: Large-scale information network embedding[C]//Proceedings of the 24th International Conference on World Wide Web. International World Wide Web Conferences Steering Committee, 2015: 1067-1077.

推薦閱讀：

相关文章