【Graph Embedding】LINE:演算法原理,實現和應用 之前介紹過DeepWalk,DeepWalk使用DFS隨機遊走在圖中進行節點採樣,使用word2vec在採樣的序列學習圖中節點的向量表示。DeepWalk:演算法原理,實現和應用?zhuanlan.zhihu.comLINE也是一種基於鄰域相似假設的方法,只不過與DeepWalk使用DFS構造鄰域不同的是,LINE可以看作是一種使用BFS構造鄰域的演算法。此外,LINE還可以應用在帶權圖中(DeepWalk僅能用於無權圖)。之前還提到不同的graph embedding方法的一個主要區別是對圖中頂點之間的相似度的定義不同,所以先看一下LINE對於相似度的定義。 LINE 演算法原理 一種新的相似度定義 first-order proximity 1階相似度用於描述圖中成對頂點之間的局部相似度,形式化描述為若 , 之間存在直連邊,則邊權 即為兩個頂點的相似度,若不存在直連邊,則1階相似度為0。 如上圖,6和7之間存在直連邊,且邊權較大,則認為兩者相似且1階相似度較高,而5和6之間不存在直連邊,則兩者間1階相似度為0。 second-order proximity 僅有1階相似度就夠了嗎?顯然不夠,如上圖,雖然5和6之間不存在直連邊,但是他們有很多相同的鄰居頂點(1,2,3,4),這其實也可以表明5和6是相似的,而2階相似度就是用來描述這種關係的。 形式化定義為,令 表示頂點 與所有其他頂點間的1階相似度,則 與 的2階相似度可以通過 和 的相似度表示。若與之間不存在相同的鄰居頂點,則2階相似度為0。 優化目標 1st-order 對於每一條無向邊 ,定義頂點 和 之間的聯合概率為: , 為頂點的低維向量表示。(可以看作一個內積模型,計算兩個item之間的匹配程度)同時定義經驗分布 , 優化目標為最小化: 是兩個分布的距離,常用的衡量兩個概率分布差異的指標為KL散度,使用KL散度並忽略常數項後有 1st order 相似度只能用於無向圖當中。 2nd-order 這裡對於每個頂點維護兩個embedding向量,一個是該頂點本身的表示向量,一個是該點作為其他頂點的上下文頂點時的表示向量。對於有向邊 ,定義給定頂點 條件下,產生上下文(鄰居)頂點 的概率為 ,其中 為上下文頂點的個數。優化目標為 ,其中 為控制節點重要性的因子,可以通過頂點的度數或者PageRank等方法估計得到。經驗分布定義為: , 是邊 的邊權, 是頂點 的出度,對於帶權圖, 使用KL散度並設 ,忽略常數項,有 優化技巧 Negative sampling 由於計算2階相似度時,softmax函數的分母計算需要遍歷所有頂點,這是非常低效的,論文採用了負採樣優化的技巧,目標函數變為: , 是負邊的個數。論文使用 , 是頂點 的出度 Edge Sampling 注意到我們的目標函數在log之前還有一個權重係數 ,在使用梯度下降方法優化參數時, 會直接乘在梯度上。如果圖中的邊權方差很大,則很難選擇一個合適的學習率。若使用較大的學習率那麼對於較大的邊權可能會引起梯度爆炸,較小的學習率對於較小的邊權則會導致梯度過小。對於上述問題,如果所有邊權相同,那麼選擇一個合適的學習率會變得容易。這裡採用了將帶權邊拆分為等權邊的一種方法,假如一個權重為 的邊,則拆分後為 個權重為1的邊。這樣可以解決學習率選擇的問題,但是由於邊數的增長,存儲的需求也會增加。另一種方法則是從原始的帶權邊中進行採樣,每條邊被採樣的概率正比於原始圖中邊的權重,這樣既解決了學習率的問題,又沒有帶來過多的存儲開銷。這裡的採樣演算法使用的是Alias演算法,Alias是一種 時間複雜度的離散事件抽樣演算法。具體內容可以參考Alias Method:時間複雜度O(1)的離散採樣方法?zhuanlan.zhihu.com 其他問題 低度數頂點 對於一些頂點由於其鄰接點非常少會導致embedding向量的學習不充分,論文提到可以利用鄰居的鄰居構造樣本進行學習,這裡也暴露出LINE方法僅考慮一階和二階相似性,對高階信息的利用不足。 新加入頂點 對於新加入圖的頂點 ,若該頂點與圖中頂點存在邊相連,我們只需要固定模型的其他參數,優化如下兩個目標之一即可: 或 若不存在邊相連,則需要利用一些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.comG = 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.6403macro-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. 推薦閱讀: 相关文章 {{#data}} {{title}} {{/data}}