基于改進TADW的鏈路預測算法

陳東明, 孫政平, 于開帥, 王冬琦

(東北大學 軟件學院, 遼寧 沈陽 110169)

鏈路預測(link prediction)是指根據已有的網絡狀態去預測網絡中未產生連邊的節點之間未來時刻產生連邊的可能性[1].它所要處理的是網絡缺失信息的還原和網絡未來信息的預測.所謂還原,指的是網絡中實際存在但尚未被發現的鏈路,這種鏈路被稱為未知鏈接(unknown links);所謂預測,指的是網絡中當前不存在但未來有可能存在的鏈路,這種鏈路被稱為未來鏈接(future links).鏈路預測可以有效解決數據缺失和冗余問題,例如噪聲數據的處理、虛假連邊識別等;也可用于因網絡規模過大、計算能力不足而進行的預測和篩選,如蛋白質相互作用網絡藥物分子與靶細胞的結合預測、社交網絡中的事件檢測[2]等.因此,鏈路預測研究具有十分重要的理論意義和實際應用價值.

在鏈路預測研究中,基于相似性的鏈路預測方法使用較多.該類方法最為簡單高效,適用于網絡規模較大的情況.基本假設如下:如節點之間的相似度越高,那么此節點之間產生連邊的可能性就越大[3].目前主要分為三類:第一類是基于網絡節點的屬性信息,例如合作者網絡中論文的題目、發表日期等信息.Lin[4]依據信息論提出了相似性的普遍定義.傅穎斌等[5]使用微博網絡數據集,采用隨機森林的方法,進而提出鏈路預測算法.許爍娜等[6]提出的鏈路預測方法基于Skyline查詢處理網絡,將經典方法預測得到的值作為節點屬性值,把Skyline點作為候選節點返回給目標用戶.但是,在實際研究中,節點的屬性信息大多是保密的,獲取難度比較大,因此這類方法受到了一定限制.第二類是基于網絡的拓撲結構信息,相比于網絡節點的屬性信息,網絡拓撲結構信息相對容易獲取而且可靠性高,復雜度也低.劉冶等[7]使用低秩和稀疏矩陣分解的方法,融合多個數據源提出了具有健壯性的鏈路預測算法.在經典的基于網絡結構信息的方法中,基于局部信息相似性的算法因其時間復雜度較低且預測準確率高,受到越來越多的關注[8],例如,經典的共同鄰居(common neighbors,CN)算法[9].Yin等[10]基于網絡局部信息,使用回歸模型和決策樹方法進行鏈路預測,分析不同結構特性下用戶間產生關注關系的可能性.基于網絡結構的算法充分利用了網絡的結構信息,在靜態網絡鏈路預測中獲得了良好的預測精度.黃立威等[11]通過元路徑(一組關系連接了多種節點類型的路徑),組合對象之間在不同元路徑上建立連接的概率來進行鏈路預測.第三類是基于網絡結構與節點屬性融合的鏈路預測方法.Popescul等[12]使用結構回歸法建立預測模型,使用CiteSeer搜索引擎中的數據進行實驗.Backstrom等[13]基于有監督隨機游走的算法,將網絡結構中的節點和連邊屬性信息有效地融合起來.Ahmed等[14]獲得網絡結構并抽取用戶的屬性信息,對用戶的社交關系進行建模,進而提出鏈路預測算法.綜上所述,研究者對復雜網絡中的鏈路預測研究不再僅僅從單方面考慮網絡的拓撲結構或者屬性信息,而是綜合考慮這兩方面的信息.

現實世界中有許多節點多而連邊數量卻不多的網絡,這樣的網絡稱為稀疏網絡.網絡的稀疏性問題給網絡分析和預測帶來許多困難,需要得到有效解決[15].近幾年來,使用深度學習的方式學習特征表示得到了越來越多的應用[16].其中,使用基于深度學習的Word2vec詞嵌入模型[17]處理文本的方式獲得了很好的效果,這也啟發了研究者們在圖嵌入方面的研究.圖嵌入是將網絡數據映射為低維向量的方法,該方法能夠有效地將網絡數據輸入到機器學習算法中.例如,經典的Deepwalk模型,它是學習網絡中節點表示的代表性方法之一[18].該模型參考Word2vec模型的思想,首先通過隨機游走得到節點的序列,然后從隨機游走的序列中獲得網絡的信息,進而通過獲取到的網絡信息學習網絡的節點表示.其中,隨機游走得到的節點序列相當于文本表示學習中的句子,然后參考文本表示的方法處理網絡中的數據.但是,Deepwalk僅僅針對網絡的結構信息進行表示學習,未考慮到網絡的屬性信息.文獻[19]證明了深度隨機游走算法等同于矩陣分解,同時提出了一種融合網絡屬性信息的網絡學習方法TADW(text-associated deep walk).

本文基于詞嵌入模型Word2vec提出一種改進的TADW算法,在此基礎上提出一種融合網絡拓撲結構和節點屬性信息的鏈路預測算法,可以有效提升包含語義信息的鏈路預測方法的準確性,且具有較強的魯棒性.

1 問題描述

針對無向網絡G(V,E), 其中V={v1,v2,…,vn},表示該網絡中的節點集合,E={,vx,vy∈V},表示該網絡中的連邊的集合.令|V|=n,n表示節點數量;|E|=m,m表示連邊數量.令U表示網絡G中所有節點對組成的邊的全集,則|U|=n(n-1)/2.使用某種鏈路預測算法,計算每對沒有連邊的節點對(vx,vy)的聯系.接著,將所有未連接的節點對按照計算值的大小降序排序,那么排在前面的節點對比排在后面的節點對相互連接的概率要大.

如果想要判斷給定預測方法的準確性,通常情況下將網絡中現有的邊E分為訓練集ET和測試集Et, 顯然E=ET∪Et, 并且ET∩Et=?.其中,訓練集用來計算節點對的值,測試集用來衡量算法的性能.

定義1已知邊:訓練集ET中的邊.

定義2不存在的邊:屬于U但不屬于E中的邊.

定義3未知邊:測試集Et中的邊和不存在的邊的并集.

使用訓練集訓練網絡G, 得到網絡中所有節點對的值.如果給定的鏈路預測方法性能較好,則網絡G的“未知邊”中測試集Et中絕大多數節點對的值應大于“不存在的邊”中節點對的值.

圖1給出了一個劃分網絡數據集的例子.圖1a是完整的網絡,該網絡中有5個節點,8條邊.隨機選擇6條邊作為該網絡的訓練集ET,如圖1b所示.剩余的兩條邊作為測試集Et,如圖1c所示.該網絡中不存在的邊為網絡的全集U與網絡現有的邊E的差, 即2條,如圖1d所示.使用某種鏈路預測算法,計算得到所有未知節點對的相似度值,其中包括測試集的2條邊和不存在的邊2條.之后將這4條邊按照值從大到小排序,如果更多的測試集中的邊排在“不存在的邊”的前面,則表示該方法的預測效果較好.

圖1 網絡數據集的劃分

2 算法設計與分析

2.1 算法提出

針對現實世界網絡的大量外部信息和數據稀疏的特點,本文提出以圖嵌入的方法將網絡結構和外部信息融合,進而得到網絡中每個節點的向量表示,基于這種向量表示,提出鏈路預測的相似性指標.

圖嵌入的方法旨在對每個節點進行向量表示,這種方法慢慢被認為是網絡分析里很重要的一部分,大多數方法都通過探討網絡結構來進行圖嵌入.事實上,網絡節點也包含了很多信息,但是卻沒有在典型的圖嵌入中得到很好的利用.同時,使用圖嵌入的方法可以解決數據稀疏的問題,它把每個節點表示為一個低維空間中的向量,從而能夠進行有效的計算.TADW是基于矩陣分解的方法將節點的文本信息引入到圖嵌入中,TADW模型示意圖如圖2所示.

圖2 TADW模型

該模型的目標函數如式(1)所示,

(1)

模型把矩陣M分解成W,H,T這三個矩陣的乘積.其中,W和H表示參數矩陣,T表示文本的特征矩陣,使用梯度下降的方法迭代更新參數矩陣W和H.TADW的目標是融合文本特征來獲得整個網絡信息的表示.

TADW算法的外部信息部分使用TF-IDF算法表示文本特征,由于TF-IDF算法僅以詞頻度量詞的重要性,缺少對詞位置信息的考慮,因此無法反映序列信息,難以有效挖掘深層語義信息,這就造成了網絡中語義信息的大量丟失.

本文對TADW中的特征矩陣T進行改進,使用詞嵌入模型對外部信息進行計算.使用網絡節點特征作為語料,訓練得到Word2vec模型,獲得模型中單詞的向量表示,從而計算特征矩陣.然后使用TADW模型框架進行訓練,得到節點的向量表示后進行多分類評價,使用節點向量提出鏈路預測的相似性指標.

2.2 相似性指標的計算

通過改進TADW算法,得到網絡中每個節點的向量表示.在空間中,兩個向量之間距離越近,它們之間的相似度就越高.本文中使用歐氏距離衡量兩個向量間的距離大小.下面定義的相似性指標為基于Word2vec訓練模型.

定義4WTADW相似性指標:使用Word2vec模型訓練特征矩陣.用SWTADW表示節點為vx和vy的相似性值,定義如公式(2)所示,

(2)

2.3 算法過程描述

基于2.2節定義的WTADW指標,提出了基于改進TADW的鏈路預測算法(link prediction algorithm based on improved TADW, LPIT).為了使算法具有普適性,本文算法使用無向無權靜態社交網絡,見算法1.

算法1

輸入:無向無權網絡G(V,E)

輸出:評價指標值

1) 讀取網絡G(V,E),構建網絡鄰接矩陣N;

2) 將E劃分為訓練集ET和測試集Et.使用K折交叉驗證的方式劃分數據集,其中K取10;

3) 對于訓練集和測試集中的節點對,計算圖嵌入得到節點對之間的歐氏距離,進而得到節點對的相似性指標.對比的相似性指標names={‘WTADW’, ‘CN’, ‘JC’, ‘AA’, ‘RA’, ‘PA’, ‘SR’};

4) 構建節點對的相似性矩陣S;

5) 計算算法的評價指標AUC(接受者操作特性曲線下方的面積)的值.

3 實驗分析

本文研究選取3個真實網絡數據集.

1) DBLP(digital bibliography & library project)[20].DBLP數據集是計算機類英文文獻的集成數據庫系統,它按照年代列出了作者的科研成果.儲存的相關元數據有:作者、標題、發表日期等.本文選取DBLP數據集中的前三個類型的期刊數據.

2) Cora[21].Cora數據集包括2 708條科學出版物,分為7類.引文網絡由5 429條鏈接組成.數據集中的每個出版物都由一個0/1值的單詞向量來描述,該向量表示字典中相應單詞是否存在.

3) CiteSeer[22].CiteSeer數據集包括3 312條科學出版物,分為6類.引文網絡由4 732條鏈接組成.與Cora數據集相同,CiteSeer數據集中的每個出版物都由一個0/1值的單詞向量來描述,該向量表示字典中相應單詞是否存在.表1為上述三個數據集的統計特征.

表1 數據集的統計特征

3.1 圖嵌入實驗

選擇節點的多分類問題去評價圖嵌入的質量,選擇SVM用于監督學習和測試.以節點的向量表示作為特征來訓練分類器,用不同的訓練率來評估分類的準確性,訓練率從10%到90%不等.對于每個訓練率,隨機選擇文檔作為訓練集,其余的文檔作為測試集.重復實驗10次,最后得到平均準確度.

表2～表4分別展示了所提出算法在DBLP，Cora和CiteSeer三個數據集上的分類表現.其中,WTADW表示使用Word2vec模型訓練特征矩陣得到向量表示.

表2 DBLP數據集的評價結果

表3 Cora數據集的評價結果

表4 CiteSeer數據集的評價結果

由表2～表4看出,本文提出的算法在DBLP和Cora數據集上的分類結果大幅領先TADW,在CiteSeer數據集上相比TADW也有一定提升,在三個數據集上的表現均優于TADW算法.這些實驗結果驗證了本文提出的WTADW算法對網絡節點的高質量表示.

3.2 圖嵌入實驗參數靈敏度分析

對本實驗中兩個超參數維數k和正則化項的權重λ,在此討論超參數設置對本實驗的影響程度.用不同的k和λ對分類精度進行測試,設置k從40到120不等,λ從0.1到1不等.

圖3表示在DBLP,Cora和CiteSeer數據集上使用Word2vec模型訓練特征矩陣的準確度(參數靈敏度)折線.

圖3 參數靈敏度折線圖

從圖3可以看出,當k值不變時,λ從0.1到1的范圍內變化的F1值浮動較小;當λ不變,k≥80時,本文提出方法的準確度較高.因此,當k和λ在合理范圍內變化時,WTADW可以保持穩定,具有較強的魯棒性.

3.3 鏈路預測實驗結果分析

在保證了本文提出的圖嵌入方法的有效性和魯棒性后,接著進行本文提出的WTADW指標與改進前的TADW及經典的相似性指標的鏈路預測對比實驗.其中,鏈路預測的評價指標AUC的計算方法[23]為,若測試集中的邊的分數值大于不存在的邊的分數值,加1分,若兩個分數相等,加0.5分,如公式(3)所示,

(3)

其中:n為獨立比較次數;n′為測試集中的邊的分數值大于不存在的邊的分數值的次數;n″為分數相等的次數.

表5是本文提出的鏈路預測的相似性指標與TADW及經典的鏈路預測相似性指標的對比實驗結果.

表5 三個數據集上不同指標的AUC比較

由表5可知,在DBLP,Cora和CiteSeer數據集中,本文提出的WTADW指標都優于經典的CN,JC,AA,RA,PA和SR指標,且優于改進前的TADW.在Cora數據集上,WTADW相較TADW有約10%的提升,在TADW的AUC值已經達到90%以上的DBLP和CiteSeer數據集上,WTADW相較TADW仍有提升.在三個數據集上,TADW均已經達到了較高的AUC值,而本文所提出的WTADW指標相比TADW仍能夠有所提升,AUC值接近100%,這應當與節點標簽的屬性信息有關,由于節點標簽的相似性為算法的高準確率提供了保障,因此使用TADW即可獲得較高的AUC值,而WTADW相較TADW能夠更加有效地學習網絡特征,因此獲得了更高的AUC值.

通過與經典相似性指標的對比實驗,可以看出，使用網絡拓撲結構和網絡節點屬性相融合的方式能更加充分地學習到網絡中的信息.同時,使用圖嵌入方法對網絡進行表征學習也更有效地表示了網絡信息,解決了網絡數據的稀疏性問題.

3.4 特征擾動實驗結果分析

為了進一步驗證本文所提出算法的魯棒性,對本文所提出算法進行特征擾動實驗,比較兩組結果在節點分類和鏈路預測任務上的差異.特征擾動策略為隨機修改或刪除部分節點的屬性信息,擾動范圍為0到0.95不等.實驗結果如圖4～圖6所示.

圖4 DBLP數據集上擾動比例靈敏度折線圖

圖5 Cora數據集上擾動比例靈敏度折線圖

圖6 CiteSeer數據集上擾動比例靈敏度折線圖

由圖4～圖6可知,在DBLP數據集上,隨著擾動比例的增加,WTADW和TADW的F1值與AUC值均逐漸下降,而WTADW表現始終優于TADW,且AUC值的變化更加平穩,當擾動比例趨近100%時,WTADW與TADW表現也漸漸趨同;在Cora和CiteSeer數據集上,分類任務的F1值變化規律與DBLP數據集上表現相同,WTADW的變化更加平穩,而在鏈路預測任務上的表現,WTADW與TADW均未因特征擾動受到較大影響,WTADW表現始終優于TADW.在三個真實網絡數據集上,WTADW的表現始終優于TADW,且在特征擾動下的變化更加平穩,證明了本文所提出算法的魯棒性.

4 結 語

針對基于矩陣分解的圖嵌入算法TADW存在的缺點,提出一種融合網絡拓撲結構信息和節點屬性信息的圖嵌入方法,設計一種相似性指標WTADW,基于所提出的相似性指標提出了鏈路預測算法.在三個真實網絡數據集上的實驗結果驗證了本文提出的鏈路預測算法比TADW算法具有更好的預測效果,證明了融合網絡拓撲信息和節點屬性信息可以提高預測精度,并且使用圖嵌入方法解決了網絡數據的稀疏性問題.