基于雙視角的耦合網絡表示學習算法①

倪琦瑄,張 霞,卜 湛

1(南京財經大學 信息工程學院,南京 210003)

2(南京中醫藥大學 人工智能與信息技術學院,南京 210023)

3(南京財經大學 江蘇省電子商務重點實驗室,南京 210003)

1 引言

現實世界中許多的社會,物理和信息系統都是以復雜網絡的形式存在的[1].在這些網絡中,人們通過挖掘網絡的潛在信息可以解決許多實際的問題,例如鏈路預測[2],鏈路重構[3],節點分類[4],邊分類等.網絡表示學習將節點映射到潛在空間[5],并保留了豐富的結構信息,為這些下游數據挖掘任務提供了一種新的解決方法,已在許多論文中被證明能夠非常有效地解決上述任務[6-13].

近10年里,有很多能夠保持網絡的結構特性的方法被提出來.然而,以往的研究往往只注重節點視角下的網絡拓撲信息,而沒有充分考慮邊視角.現有的網絡表示學習算法可以分為兩大類:基于隨機游走的網絡表示學習算法和基于深度學習框架的網絡表示學習算法.基于隨機游走的網絡表示學習算法,例如DeepWalk[8]和Node2Vec[9],主要分為隨機游走和Skip-gram[10]算法兩部分,他們通過隨機游走以獲取節點視角下的網絡拓撲結構,再利用Skipgram 模型對每個節點進行更新學習,Node2Vec在DeepWalk的基礎上,加入了帶有偏置的隨機游走,使得其能以不同偏好的游走方式獲取節點的同質性和結構等價性.Line[11]也是一種基于鄰域相似假設的網絡表示學習算法,通過設置兩種鄰近性構造目標函數來獲取節點的局部相似性和鄰居相似性.然而,這些算法往往只關注了節點視角下網絡拓撲信息,而沒有充分考慮邊視角.基于深度學習的網絡表示算法,如SDNE[12],利用半監督的自動編碼器模型來學習網絡中每個節點的表示向量,DNGR[13]則通過Random Surfing 模擬隨機游走過程獲取網絡拓撲信息,再利用堆疊降噪自編碼器對節點表示向量進行訓練.GAE[14]通過圖卷積作為自編碼器的編碼方式,為每個節點聚合其鄰居的特征信息,再利用解碼器重構網絡的鄰接信息.這些基于深度學習架的網絡表示學習算法往往效果很好,但其涉及到許多復雜計算,其空間和時間復雜度隨著網絡規模的擴大面臨著巨大的挑戰,同時,這些算法也只關注了節點視角下的節點之間的連接信息,而沒有考慮過邊視角.而在已有的針對邊的一些研究中,大多考慮的是邊上的屬性或標簽信息[15,16].如NEES[15]通過邊計算節點之間關系的相似性,從而設置帶有偏好的隨機游走,使得節點的隨機游走的每一步都與上一步有盡可能相似的關系.ELAINE[16]則通過重構每種邊的標簽向量,使得最終學習得到的節點向量能夠同時包含邊的標簽信息和網絡結構信息.事實上,不同的視角會帶來不同的有效信息,比如不同的社區劃分.因此,本文將研究重點從節點轉移到邊.利用邊圖(line graph)[17]從邊的角度觀察網絡.在邊圖中,原始網絡的邊表現為邊圖中的節點,邊圖中的邊表示原始網絡中邊之間的連接關系.Ahn 等人[18]在對重疊社區發現問題的研究中就提出了邊社區的概念,他們通過邊而不是節點來劃分社區,并指出邊的層次結構與原始網絡中的節點層次結構有所不同,從邊的角度觀察目標網絡可以發現更多的特征.

一個好的網絡表示學習算法應該能夠有效地保存網絡中的社區結構[9],為了達到這一效果,現有的基于隨機游走的網絡表示學習方法如DeepWalk 主要采用隨機游走獲取網絡中每個節點的上下文信息,繼而采用Skip-gram 模型學習其低維表示,從而使得具有相似拓撲屬性的節點具有相似的低維表示.過往的研究表明[19],一個社區的內部連接應該多于其外部連接,由于社區內的連接密度應該比較高,所以隨機游走時停留在自己社區內節點上的概率要高于到外部的概率.為了進一步了解邊圖,本文選擇DBLP 數據集[20],分別在原始網絡和對應的邊圖上進行隨機游走.在設置相同的總采樣次數的情況下,在圖1中畫出了其不同視角下的節點采樣頻率分布,橫坐標表示原始網絡中的節點在不同視角下的采樣過程中的出現次數,縱坐標表示對應出現次數的節點數量,可以看到在兩種視角下隨機游走得到的節點頻率分布是不同的,這是因為邊圖可以為我們提供更多的連接信息,進而可以為我們更好地揭示原始網絡中的層次結構.

圖1 對DBLP 數據集進行隨機游走的節點采樣頻率分布

綜上所述,本文提出了一種融合節點視角和邊視角的耦合網絡表示學習算法DPBCNE (Dual Perspectives Based Coupled Network Embedding).分別從兩個視角下學習網絡拓撲信息,在這個耦合模型中,可以同時學習節點和邊的低維表示.通過使用節點-邊的耦合訓練機制,可以將節點和邊映射到相同的低維空間中.與大多數現有的網絡表示學習方法間接獲取邊的表示方法不同,DPBCNE 可以直接學習得到節點和邊的表示,更具有解釋性.本文在4 個真實復雜網絡中驗證了DPBCNE的性能,并通過節點分類,邊分類,鏈路預測和鏈路重構4 個任務來比較DPBCNE 與當下最先進的網絡表示學習方法的效果.在鏈路預測任務中,與基準方法相比,DPBCNE 取得了較好的結果,在合作者網絡中僅次于CN 算法.而在節點分類,邊分類和鏈路重構任務中,DPBCNE 均優于其他所有網絡表示學習基準方法.

2 基于雙視角的耦合網絡表示學習算法

本文提出了一種新的基于雙視角的耦合網絡表示學習算法.其主要模型框架如圖2所示,模型可以分為兩個部分:第1 部分,獲取兩種視角下的網絡結構信息,給定一個原始網絡,首先構建邊圖,在原始網絡和邊圖上分別進行隨機游走,得到不同視角下的節點采樣序列.第2 部分,耦合更新原始網絡中的節點向量和邊向量,根據節點和邊之間的對應關系以及不同視角下中心詞節點和其上下文節點的關系,將上述兩個視角結合起來進行耦合更新,在更新過程中共享節點和邊的向量表示,最終獲得融合兩種視角下網絡結構信息的節點向量和邊向量.

圖2 DPBCNE 模型框架示例

2.1 融合兩種視角的網絡表示學習

對于邊視角,本文首先根據原始網絡構建邊圖(line graph) 來獲取邊視角下的結構信息.給定的圖G(V,E),其中V表示節點集合,E表示邊集合.令圖G對應的邊圖為Glink.在邊圖Glink中,圖G的邊集合E映射為邊圖的節點集合Vlink,節點集合則映射為邊圖的邊集合Elink.通過這種轉化構建的邊圖記為Glink＜Vlink,Elink＞.

對于兩種視角下信息的獲取,本文采用DeepWalk的方法.通過對不同視角下的節點進行隨機游走得到語料庫,每一個隨機游走序列都可以看作是自然語言處理中的一個句子,然后用Skip-gram 算法最大化中心詞節點和其上下文的共現概率,從而得到不同視角下每個節點的表示向量,使得在同一視角下具有相似結構的節點具有相似的向量.

因此,雙視角下網絡結構信息獲取的目標函數分別為:

其中,N為節點網絡中節點的個數,S為隨機游走得到的節點序列集合,w表示窗口大小,v表示節點網絡中的節點.Slink為邊圖中隨機游走得到的序列集合,Nlink為邊圖中的節點個數即原始網絡中邊的數量,vlink表示邊圖中的節點也即原始網絡中的邊.

該部分總的目標函數為:

為了得到有效的網絡潛在特征,本文同時融合節點視角和邊視角進行網絡表示學習.介于節點與邊的一對多的關系,節點與其對應邊的向量應當更相似,通過不斷耦合更新得到包含兩種視角下網絡拓撲信息的節點向量和邊向量,將另一視角的網絡信息聚合到當前視角的節點向量學習上.節點和邊視角耦合關聯模型目標函數分別如下:

關聯部分總的目標函數為:

其中,Cnode(vi)表示原始網絡中與節點vi直接相連的所有邊的集合.表示原始網絡中與邊直接相連的所有節點的集合.

根據上述內容,DBPBCNE 算法的總目標函數如下:

其中,α ∈[0,1]是用來平衡不同視角重要性的一個參數,通過聯合優化使得在節點學習的過程中耦合邊視角下的信息,以得到更有效的節點表示,同時也能學習得到耦合兩個視角下信息的邊向量.

2.2 耦合訓練過程

本文使用隨機梯度上升(SGA)來訓練模型,通過Softmax 公式來計算上述公式中的概率公式,例如式(1)中使用的P(vi+j|vi),可以通過下列方式來計算:

為降低時間復雜度,本文采用負采樣的方法對公式(8)進行簡化.除了更新窗口中的已知鄰居節點外,為給定節點生成k個負樣本.在計算公式(1)中的梯度時,便不需要在每個梯度步驟中枚舉式(8)中的所有節點,只需要計算根據詞分布構建的負樣本和已知的正樣本.假設給定鄰居節點vi+j的負樣本集合為NEG(vi+j)={v1,v2,···,vk}則:

其中,表示待定參數,為這部分要更新得到的節點向量,指示函數對求導可以得出:

從而可以得到原始網絡中的節點在節點視角下通過上下文節點進行更新的公式如下:

對于節點-邊耦合關聯模型部分,本文通過用原始網絡中與邊相連的節點更新邊,用與節點相連的邊更新節點,從而使得最終得到的原始網絡的節點和邊向量同時學習得到兩個視角下的網絡信息.

對于節點向量更新部分,給定一個原始網絡中的節點vi和對應的一個相連邊,其負采樣得到的負樣本集合為同樣,對于邊向量更新部分,給定一個邊圖中的節點和他對應的一個原始網絡中的節點vc,其通過負采樣得到的負樣本集合為NEG(vc)={v1,v2,···,vk}

原始網絡中節點在關聯部分的向量更新公式如下:

原始網絡中的邊在關聯部分的向量更新公式如下:

為了更加詳盡地介紹本文提出的DPBCNE 算法的具體流程,本文給出了算法偽代碼如算法1所示.

算法1.基于雙視角的耦合網絡表示學習算法輸入:圖,窗口大小,向量維度,隨機游走次數,總迭代次數,游走長度,學習率,負采樣個數.Xv∈RN×dXvlink∈RNlink×d輸出:節點表示向量矩陣,邊表示向量矩陣.G(V,E) wd γ ITERl η k X Xlink 1.初始化,G(V,E) Glink＜Vlink,Elink＞2.根據 構建邊圖i=0 γ 3.For to:Ω=shu f fle(V)4.Ωlink=shu f fle(Vlink)5.6.For each do S=RandomWalk(G,vi,l)vi∈Ω 7.8.End for i ∈Ωlink 9.For each do vlink Slink=RandomWalk(Glink,vlink i,l)10.11.End for 12.End for iter=1,2,3,···,ITER 13.For do s∈S 14.For each do Xv X′v 15.根據式(13)和式(14)更新和Xv X′vlink 16.根據式(15)和式(16)更新和17.End for slink∈Slink 18.For each do Xvlink X′vlink 19.根據式(18)和式(17)更新和Xvlink X′v 20.根據式(19)和式(20)更新和21.End for 22.End for

算法可以分為第一步獲取雙視角下的網絡結構信息部分和第二步耦合更新部分.第2-10 行分別對節點視角和邊視角下的網絡進行隨機游走采樣獲取兩個視角下的網絡結構信息,第14-22 行表示耦合更新過程,第14-17 行對于第1 步在原始網絡中采樣得到的所有節點序列中的每個節點,分別用其對應的上下文節點和對應的邊進行耦合更新,同樣,第18-21 行是對于邊圖中的采樣得到的所有節點序列中的節點,也即原始網絡中的邊,分別用其上下文節點和對應的原始網絡中的關聯節點進行迭代耦合更新,最終得到融合兩個視角的原始網絡的節點向量和邊向量.

對于每一輪的迭代,第一部分的對原始網絡隨機游走的時間復雜度為Nrl,對邊圖的隨機游走時間復雜度為Nlinkrl,第二步耦合更新部分,對于節點的更新過程時間復雜度為Ngdk+Ndwrlk,其中g表示原始網絡中節點的平均度,對于邊的更新過程時間復雜度為2Nlinkdk+Nlinkdwrlk,其中,每個網絡的平均度通常都有一個最大值,其余的d,w,r,l,k均為可以設置的常數.

3 實驗分析

3.1 數據集

本文主要針對傳統的網絡表示學習研究只是通過節點視角這一單一的視角而沒有考慮邊視角的問題,提出了一種新的基于雙視角的耦合網絡表示學習算法(DPBCNE).本文在4 個真實的復雜網絡數據集中分別驗證了該方法的性能,分別為Facebook[21],GRQC[22],HEPTH[22]和DBLP[20]數據集.其中Facebook為社交網絡,總共有193 種節點標簽;GRQC和HEPTH為合作者網絡,數據集中沒有標簽信息;DBLP為引文網絡,總共有4 種節點標簽.

3.2 基準方法

在學習到節點的表示向量后,本文分別在4 個任務中與當下主流的網絡表示學習算法進行比較,其中,(1)-(3)項是基于隨機游走的網絡表示學習算法,(4)-(6)項是基于深度學習的網絡表示學習算法,此外,針對鏈路預測和鏈路重構任務,本文還選擇了一種效果良好的傳統鏈路預測方法Common Neighbor[23]作為對比方法,相關基準算法簡介如下:

(1)DeepWalk[8]:對節點采用隨機游走和Skip-gram模型以學習得到每個節點的表示向量.

(2)Node2Vec[9]:在DeepWalk的基礎上,引入了帶偏置的隨機游走,以選擇不同的搜索方式采樣節點.其中,偏置參數p=0.25,q=0.5.

(3)Line[11]:通過分別定義損失函數同時保存網絡中節點的一階鄰近度和二階鄰近度.

(4)SDNE[12]:使用自動編碼器通過聯合優化目標函數來保持節點一階和二階鄰近性.該方法采用高度非線性的函數對網絡的鄰接矩陣進行編碼.

(5)DNGR[13]:利用Random Surfing 策略生成概率共現矩陣,再作為疊加去噪自動編碼器的輸入進行節點表示的學習.

(6)GAE[14]:使用圖卷積網絡(GCN)編碼器和內積解碼器.該方法利用GCN 學習節點間的高階關系.

(7)Common Neighbor (CN)[20]:以每個節點對之間的公共鄰居數作為節點之間的相似度評分,以進行鏈路預測.

在實驗過程中,為保證公平比較,所有實驗的參數均統一設置.對于網絡表示學習算法,其維度為128,負采樣樣本數為5,窗口大小為5,每個節點的隨機游走次數為10,步長是40,邊圖的設置與原始網絡相同.學習率為0.01,最大迭代次數為200.

3.3 評價指標

為驗證DPBCNE的有效性,本文分別在鏈路預測,鏈路重構,節點分類和邊分類4 個任務上進行了對比實驗.

對于鏈路預測和鏈路重構,采用了AUC(Area Under Curve)和AP(Average Precision) 指標來驗證最終的效果.

AUC表示當隨機選擇一個正樣本和一個負樣本時,正樣本分數高于負樣本的概率.例如,在鏈路預測任務中,隨機挑選測試集中的一條邊和一條不存在的邊并進行比較,重復進行n次,其中有n′次測試集中邊的分數大于不存在的邊,有n′′次兩者獲得同樣的分數,那么最終得到的AUC計算公式如下:

AP表示平均準確率,其計算公式如下:

其中,Precision表示每個類別的準確率,M表示類別數.

對于節點分類和邊分類實驗,采用了Micro-F1和Macro-F1 來作為評價指標.定義如下:

其中,F1(A)表示標簽A的F1 得分,C表示所有的標簽集.Pr表示總的準確率,R表示總的召回率.

3.4 節點分類

節點分類是網絡表示學習中用以驗證算法有效性的一個重要任務.此任務在Facebook和DBLP 數據集上驗證了DPBCNE 算法,首先移除數據集中沒有標簽的節點,將數據集按照30%的比例劃分訓練集,剩余的節點作為測試集,將每個節點學習得到的表示向量作為邏輯回歸分類器的輸入進行訓練,通過計算Micro-F1和Macro-F1 來比較不同模型之間的效果,最終結果如表1所示.

表1 節點分類實驗結果

從表1中可以看到,DPBCNE 模型地結果在兩個數據集上都優于其他算法.在Facebook 數據集中,DPBCNE的Macro-F1 得分比其他算法中表現最好的DNGR 算法高出了0.99%,Micro-F1 得分則比DNGR算法高出了1.19%.這表明,通過融合兩種視角下的網絡表示學習能夠獲取比在單一視角下更豐富的節點采樣結果,也就是更豐富的網絡結構信息,使得其在節點的類別劃分上比只關注單一視角的效果更好.而在DBLP數據集中,DPBCNE 算法的Macro-F1和Micro-F1 得分比DNGR 分別高了0.3%和0.55%.DPBCNE 模型在Facebook 數據集中的提升效果比在DBLP 數據集中更好,這是因為Facebook 數據集中每個節點具有多個標簽,而DBLP 數據集的每個節點有且只有一個標簽,融合了邊視角的耦合網絡表示學習,也更能區分出節點的重疊社區.

3.5 邊分類

傳統的網絡表示學習算法通常使用兩個節點向量簡單相連或相加來作為兩個節點之間的邊的表示[9].在本任務中,對于所有的網絡表示學習基準算法,首先學習到每個節點的向量,再用(vi+vj)/2表示節點vi和節點vj之間的邊向量.而對于DPBCNE,通過耦合學習,可以直接得到每條邊的表示,使其更具解釋性.本任務采用Facebook 數據集進行驗證,聚合每對節點的標簽,作為其對應邊的標簽,按照1%～9%的比例對于網絡中的邊劃分出訓練集作為邏輯回歸分類器的輸入.本任務采用了Micro-F1和Macro-F1 指標來衡量最終的效果,具體結果如圖3所示.

圖3 邊分類實驗結果

圖3中,DeepWalk (Link) 方法通過直接對邊圖的節點進行隨機游走,不進行耦合訓練直接得到邊向量.DeepWalk (Link)在邊分類任務中也取得了比只在節點上進行DeepWalk 學習節點表示再拼接成邊向量更好的結果,這說明對于邊向量的計算,在邊圖上直接進行學習得到是有效的.同時,DPBCNE 始終高于其他所有方法包括效果良好的DeepWalk (Link),這說明融合兩個視角的耦合訓練學習得到的邊向量可以更好地保存網絡中的信息.

3.6 鏈路預測

在這個任務中,首先將網絡中所有的邊劃分為測試集和訓練集(比例為3:7),同時保持網絡的連通性,通過對訓練集進行網絡表示學習,得到網絡中每個節點的表示,再計算|vi-vj|作為vi和vj之間的邊的表示.本文認為兩個節點之間是否存在邊可以由節點對應向量的絕對差來決定[4].將測試集中的邊看作為正例,對每一個正例等比例地構建一條不存在的邊當作負例,將其作為邏輯回歸分類器的輸入.本任務用AUC和AP作為本任務的評價指標,具體結果如表2所示.

由表2可以看到,DPBCNE的AUC指標都在75%以上,這說明DPBCNE 可以有效地預測網絡中的未知邊.在Facebook 數據集以及DBLP 數據集中,DPBCNE 取得了最好的效果,在GRQC 與HEPTH 數據集中DPBCNE的效果僅次于CN 算法,這說明在合作者網絡中,節點之間的關系非常受共同鄰居的影響,復雜的學習反而沒有簡單的指標來得有效,但DPBCNE仍然高于其他所有基于隨機游走和深度學習的網絡表示學習,由于融合了兩種視角,DPBCNE 能夠更好地預測網絡中未知的邊.

表2 鏈路預測實驗結果

3.7 鏈路重構

鏈路重構任務類似于鏈路預測,不同的是鏈路重構所重構的是現有的邊,而不是去預測未知的邊.給定一個網絡,使用不同的鏈路重構方法來重構原始網絡的所有邊.在這個任務中,依舊使用兩個節點表示向量之間的絕對差作為每條邊的表示.同樣,采用AUC和AP作為評價指標.具體結果如表3所示.

表3 鏈路重構實驗結果

可以看到,DPBCNE 模型的AUC 結果都接近于1,這說明該方法能夠很好地保存網絡的鄰接關系.在4 個數據集中,DPBCNE 始終效果是最好的,相比于傳統的鏈路預測方法CN,DPBCNE在AUC指標上提升了1.03%～17.59%,在AP指標上提升了0.87%～17.16%,相比于效果最好的基于隨機游走的算法LINE,DPBCNE在AUC指標上提升了0.96%～19.05%,在AP指標上提升了0.69%～24.1%,對比效果最好的基于深度學習的算法DNGR,DPBCNE在AUC指標上提升了1.76%～5.3%,在AP指標上提升了1.7%～7.73%.

4 結論與展望

本文討論了兩種不同視角在社區結構和隨機游走方面的差異,通過經驗分析,本文得出邊視角和節點視角在隨機游走中出現的節點分布是不同的,這意味著通過不同的視角,可以獲得更多的網絡拓撲信息.因此,本文提出了一種新的網絡表示學習算法DPBCNE,可以同時考慮邊視角和節點視角,并通過耦合學習,學習得到節點向量和邊向量.本文在節點分類,邊分類,鏈路預測和鏈路重構4 個任務上驗證了該方法的效果.DPBCNE在4 個任務中都展現了其良好的性能.本文只在靜態網絡中進行了任務驗證,而在現實生活中,網絡是不斷變化的,因此,未來的研究 將該算法考慮擴展到動態網絡以及加入深度學習框架以獲得更好的效果[24].同時,鑒于DPBCNE 可以直接學習得到每條邊的表示,還將考慮將其擴展到知識圖譜的應用研究中[25].