融合權重和結構的加權非負矩陣分解的鏈路預測

陳廣福，劉奇，李曉飛

（1.武夷學院數學與計算機學院,福建武夷山 354300；2.福建省茶產業大數據應用與智能化重點實驗室,福建武夷山 354300）

當前，復雜網絡已是在日常生產生活中無處不在，如交通運輸網絡、在線社交網絡、生物網絡和電力網絡等。復雜網絡的分析和挖掘變得非常重要和有價值。作為復雜網絡分析的研究熱點之一，鏈路預測越來越受到研究者的關注。鏈路預測的目標是根據網絡可觀測結構信息來推斷網絡中缺失的或新的鏈接[1]。鏈路預測在現實世界中有著廣泛的應用，例如：識別生物網絡中潛在的蛋白質—蛋白質相互作用[2]、在在線商業系統中推薦商品[3]、預測書目網絡中的引用關系[4]等。

真實世界網絡存在大量加權網絡，例如科學家合作網、生物網和交通運輸網等。不同加權網絡鏈接權重蘊含著不同含義，例如：科學家合作網中鏈接權重表示引用次數；食物網中鏈接權重代表物種之間的碳流量。鏈接權重是加權網絡最原始結構信息。目前，加權網絡的鏈路預測可歸納為2類：基于結構相似度和非負矩陣分解。其中基于結構相似度的主要思想是利用鏈接權重信息去計算節點相似度。例如：文獻[5]將共同鄰居(common neighbors，CN)、資源分配(resource allocation，RA)和Adamic-Adar(AA)指標擴展到加權網絡中構成加權局部相似度方法，分別是加權共同鄰居（weightedcommon neighbors，WCN）、加權Adamic-Adar（weighted Adamic-Adar，WAA）和加權資源分配（weighted resource allocation，WRA），其結果表明考慮自然權重可顯著改善預測準確度；文獻[6]提出基于信息論的加權局部相似度方法，同理也證實弱鏈接理論作用；袁榕等[7]同時考慮網絡中鏈接的聚類和擴散性信息與WCN、WAA和WRA相融合，以改善加權網絡預測精度；王曦等[8]將網絡結構相似度與節點行為同步指數相融合，提出用戶行為同步的加權網絡鏈路預測算法。以上方法盡管改善了算法性能，然而僅考慮自然權重或拓撲權重，卻無法同時保持自然權重和拓撲權重信息。

基于非負矩陣分解[9]方法是將鄰接矩陣映射到低維潛在空間，保持結構信息，再重構原始網絡獲得最小誤差預測分數矩陣。當前，現有大部分基于非負矩陣分解的鏈路預測算法僅適用于無向無權網絡，例如：Chen等[10]提出在非負矩陣分解框架中融合圖則化和稀疏學習，保持網絡局部和全局結構；Ma等[11]提出在非負矩陣分解框架中融合多標簽信息提取網絡特征。上述算法忽略了網絡鏈接權重無法處理加權網絡鏈路問題。隨著非負矩陣分解在鏈路預測研究深入，一些研究者將非負矩陣分解方法擴展到加權網絡，例如：文獻[12]首次利用非負矩陣分解技術處理加權網絡鏈路預測問題，該方法假設所有鏈接權重服從泊松分布，其結果表明該方法考慮鏈接權重后性能有所提高；Chen等[13]提出在非負矩陣分解框架中融合聚類與自然權重，保持加權網絡結構。上述方法缺點是僅考慮自然權重鏈接及局部結構。

針對以上方法的不足，本文提出了一種融合自然權重鏈接和多類型局部結構的加權非負矩陣分解(weight nonnegative matrix factorization，WNMF)模型。它保持多類型局部結構。首先將加權網絡鄰接矩陣映射到低維潛在空間，去保持網絡鏈接權重信息；然后，將加權網絡3個經典基于局部結構相似度作為指示矩陣指派到低維潛在空間，保持多類型局部結構；接著，融合上述信息提出3個鏈路預測模型，分別是WNMF-WCN、WNMF-WAA和WNMF-WRA，再利用更新法則去學習所提模型的參數并從理論上證明所提算法收斂性；最后，在6個加權網絡上將現有加權網絡方法與本文模型相比較，驗證本文所提模型的性能。

1 融合自然權重和結構的加權非負矩陣分解的鏈路預測模型

1.1 相關概念

考慮一個無向加權網絡G(V,E,W)，其中V=是節點集，E表示鏈接集，W表示自然權重。每條邊e∈E是一個有序對e=(υi,υj)，并與權重Wυiυj>0相關聯。本文不考慮多個鏈接和自循環存在，利用X=[xij]N×N來表示G的鄰接矩陣。若G是無向加權網絡，如果節點υi和υj之間存在鏈接，則否則xij=0。

U表示所有可能的鏈接，并且U?E是不存在的鏈接集。鏈路預測的目標是從集合U?E中尋找缺失鏈接。為評估所提模型性能，將可觀察鏈接集E隨機劃分為2部分：訓練集ET和測試集EP。顯然,ET∩EP=φ和ET∪EP=E。本文中：運算符〈·〉表示內積；AT表示矩陣A的轉置；Tr(A)表示矩陣A的跡；‖A‖F表示F范數；I表示單位矩陣。

1.2 融合自然權重和結構的加權非負矩陣分解的預測模型

加權非負矩陣分解（weighted non-negative matrix factorization，WNMF）[14]是非負矩陣分解變形。它的優點是引入指示矩陣改善預測缺失鏈接能力。具體地，設任意網絡的鄰接矩陣A，將A映射到低維潛在空間，其損失函數為

式（1）僅適用無向無權網絡無法處理加權網絡。本文擴展式（1）到加權網絡，需要修改S。權重拓撲是加權網絡重要組成部分?，F有的加權網絡3個經典局部結構相似度是加權共同鄰居（weighted common neighbors，WCN）、加權Adamic-Adar（weighted Adamic-Adar，WAA）和加權資源分配（weighted resource allocation，WRA），它們的定義如表1所示。

表13 個加權網絡局部相似度

將式（2）—（4）替換式（1）中S，則其表達式分別為：

將加權網絡局部結構相似度替換原有的指示矩陣S有2方面的優點：1）適用于加權網絡并預測缺失權重鏈接；2）同時保持局部結構和自然權重鏈接適用于不同類型加權網絡。為防止目標函數過度擬合化，將式（5）—（7）中因子矩陣W和H正則化約束，目標函數為：

式中：⊙為哈達瑪積（Hadamard Product）；α是防止過度擬合化。將上述3個損失函數歸納為一個統一的目標損失函數，為

采用拉格朗日乘法規則學習所提模型參數。根據矩陣跡性質有：Tr(A+B)=Tr(B+A)和Tr(AB)=Tr(BA)。再重寫式（11），為

引入拉格朗日乘子矩陣Φ=[φ]nk和Ψ=[ψnk]，有

1）固定W，更新H。

刪除式（13）中與H無關項，有

對J(H)求H的偏導，有

由 KKT（Karush-Kuhn-Tucker）條件且φnkhnk=0，有

因此，得到更新規則為

2）固定H，更新W。

刪除式（13）中與W無關項，有

對J(W)求W的偏導，有

由 KKT（Karush-Kuhn-Tucker）條件且ψnkwnk=0，有

因此，得到更新規則，為

目標函數中所有的變量因子矩陣都獲得更新，然后以最小誤差重構原始加權網絡獲得鏈路預測概率矩陣，再將預測概率矩陣按降序排列構成有序列表，并將有序列表的分數插入訓練集中，計算評價度量PCC和Precision值。

1.3 本文算法流程

本文算法的具體執行過程如下。

輸入：A為加權網絡的鄰接矩陣；α為超級參數；K為潛在空間；最大迭代次數為maxiter。

輸出：平均PCC和Precision。

步驟1，加權網絡鄰接矩陣劃分為：訓練集ET和測試集EP。

步驟2，初始化W和H。

步驟3，式（5）—（7）保持自然權重和局部結構。

步驟4，Fort=1:maxiterdo

步驟5，根據式(14)，更新H//更新因子矩陣H。

步驟6，根據式(15)，更新W//更新因子矩陣W。

步驟7，|Jt+1?Jt|<10?6直到收斂為止//收斂終止條件。

步驟8，Endfor。

步驟9，計算鏈路預測概率矩陣：S=WHT//預測分數矩陣。

步驟10，將S按降序排序構成有序表。

步驟11，將有序表分數插入訓練集ET。

步驟12，計算PCC和Precision。

步驟13，獲得最終平均預測準確度，即平均PCC和Precision值。

2 算法的收斂性

本章通過理論方法證明所提算法收斂性。具體證明過程如下。

定理目標函數J在更新規則式(14)下是非單調遞增的。

證明定理成立，需要以下輔助定理。

定義對任意的x和x′，若M(x,x′)是F(x)的輔助函數，那么必須滿足條件：M(x,x′)≥F(x),M(x,x)=F(x)。

引理1若M(x,x′)是F(x)的輔助函數，F(x)在更新規則下單調遞減。

首先，刪除式（12）中與H無關項，有

求F(H)對H的一次和二次偏導數，為：

證明Fnk(Hnk)泰勒展開式為

定理得證。同理可證目標函數J在更新規則式(15)下是非單調遞增的，本文省略。

3 實驗結果

3.1 評價度量

采用PCC和Precision 2個指標[15]評價所提模型性能。

1）PCC(pearson correlation coefficient)是衡量預測向量與實際向量的線性關系。其定義為

2）Precision是預測排名靠前鏈接的能力。若按分數排序的前L個鏈接中，有m個鏈接屬于測試集，則Precision計算公式為

3.2 數據集

6個真實世界加權網絡作為測試所提性能數據集。其拓撲結構如表1所示。表中：|V|是節點數；|E|是鏈接數；Cw表示節點平均聚類系數；Density代表網絡稀疏程度。

表16 個真實世界加權網拓撲結構

1)神經元網絡（CELegans，CEL）[16]是由306個節點和4296個鏈接構成秀麗隱桿線蟲的神經網絡。節點表示神經元，鏈接權重表示2個神經元之間的突觸數量。

2)期刊和雜志網（JOUrnals，JOU）[16]是由124個節點和11944條鏈接構成期刊和雜志網絡。節點表示期刊和雜志，鏈接權重表示讀者數量。

3)USA1[16]是美國的航空運輸網絡。該網絡由332個節點和2126條鏈路組成。節點表示機場，鏈接表示路線。鏈接的權重是2個機場之間的航班數量的頻率。

4）USA2[17]是美國500個最繁忙的商業機場網絡。該網絡由500個節點和5960條鏈路組成。

5）信息交換論壇網（MESsage，MES）[17]是由899個節點和11萬2168鏈接構成的在線信息交換網。節點表示用戶，鏈接權重表示用戶發布到主題的消息或字符數關系。

6）CEGT[18]是由923個節點和6470鏈接構成的生物網。節點表示基因，鏈接權重表示基因相互作用。

3.3 基準算法

為評估所提3個模型的預測準確度，選擇10個現有的加權網絡鏈路預測方法與本文模型進行對比。10個現有的加權網絡鏈路預測方法說明如下。

1)加權共同鄰居(WCN)[5]、加權AA((WAA)[5]、加權資源分配指標RA(WRA)[5]。3個指標是在基于局部相似度基礎上考慮鏈接權重信息，其定義為：

式中z∈Oxy表示節點x和y的共同鄰居。

2)WMI-WCN[6]、WMI-WAA[6]和WMI-WRA[6]。基于信息論框架下融合網絡局部結構信息。

3)rWCN、rWAA和rWRA[15]是局部權重拓撲結構與可靠路徑相融合的加權網絡預測指標。

式中z∈Oxy表示節點x和y的共同鄰居。

4）線性最優化(linear optimization，LO)[19]。該指標假設2個節點之間存在鏈接的可能性，可以通過相鄰節點貢獻的線性求和來展開，其定義為

式中 α為超級參數。

3.4 實驗結果分析

本文采用PCC和Precision度量指標去評估所提模型性能。由于所提模型中包含有3個重要的參數α、潛在空間維數K和迭代次數需要進行預設，因此對所有數據集設置參數α=3，潛在空間維數K=60，最大迭代次數為60。在6個加權網絡上實驗結果如表2所示。

1）所提模型WNMF-WCN、WNMF-WAA和WNMF-WRA在6個加權網絡上，PCC和Precision值均獲得最優，表明所提模型獲得高質量性能。所提模型獲得高預測準確度的主要原因是可同時保持自然權重和多類型局部結構，獲得了更多結構信息。具體地，所提模型與第二優秀方法相比，在CEL、JOU、MES和CEGT加權網絡上PCC分別提高了4.9%、0.4%、22.8%和3.1%，在CEL、JOU、USA1、USA2、MES和CEGT網絡上Precision分別提高了4.3%、6%、0.7%、7%、23.5%和5%。在PCC度量方面，第二優秀方法分別指：在CEL數據集中是LO；在JOU數據集中是WMI-WAA；在MES數據集中是WRA；在CEGT數據集中是WRA。在Preecision度量方面，第二優秀方法分別指：在CEL數據集中是LO；在JOU數據集中是WRA；在USA1數據集中是WAA；在USA2數據集中是rWRA；在MES數據集中是LO；在CEGT數據集中是WAA。

2)3個基于局部結構相似度指標WCN、WAA和WRA，以及基于可靠路徑rWCN、rWAA和rWRA在6個加權網絡上均獲得較差預測準確度。主要原因是該類指標僅考慮自然權重鏈接，無法捕獲更多結構信息。基于信息論的3個預測指標WMI-WCN、WMI-WAA和WMI-WRA啟用互信息捕獲網絡結構在6個加權網絡上預測，其準確度與上述方法有提高。

3）LO在本質上與非負矩陣分解類似，采用節點鄰居貢獻線性和分解獲得最優解，在6個加權網絡上獲得較優性能。然而，與所提模型相比較，LO獲得較低預測準確度的原因是該指標僅捕獲節點三階路徑信息。所提模型最優預測者與LO相比較，在CEL、JOU、USA1、USA2、MES和CEGT網絡上Precision分別提高了4.3%、7.8%、15.2%、18.5%、23.5%和5%。

4）所提模型WNMF-WCN、WNMF-WAA和WNMF-WRA本質上都是在WNMF框架融合加權網絡局部結構。然而它們最大區別是從不同角度捕獲加權網絡局部結構。例如：WNMF-WCN是統計節點間共同鄰居數量方式獲得加權網絡結構，與WCN相比較預測準確度顯著提高；WNMF-WAA是以懲罰節點共同鄰居權重較大節點形式捕獲加權網絡結構；WNMF-WRA是通過共同鄰居間資源分配去捕獲網絡結構。由表2可知：WNMF-WCN性能最優的主要原因是6個加權網絡的聚類系數都較高，表明WNMF-WCN捕獲更多節點間共同鄰居數量；WNMF-WAA在JOU網絡上獲得最優預測準確度，其原因是JOU聚類系數最大，表明存在權重較大節點，通過懲罰機制獲得最優性能；WNMF-WRA在CEGT網絡（稀疏率0.0076）獲得最優性能，其主要原因是通過資源分配改善了稀疏性。因此，3個模型適用不同類型加權網絡。

本文還通過設置不同比率改變網絡稀疏性，以測試所提模型魯棒性。設訓練集比率范圍為40%、50%、···、90%。由于空間有限，本實驗僅選取WCN、rWCN、WMI-WCN、NMF和WNMFWCN 5個模型，其實驗結果如圖1所示。由圖可知，在不同比率下本文所提模型獲得最優性能，當訓練集40%時，意味著網絡稀疏率達到60%，在6個加權網絡上所提模型均獲得最優性能，表明所提模型魯棒于稀疏網絡。

圖1 不同訓練集下對應Precision值

4 參數敏感性分析

本章討論所提模型主要參數對性能的影響。所提模型包含3個重要參數：α、潛在空間K和最大迭代次數。設 α變化范圍為{0，0.03，0.3，3，30}，潛在空間K變化范圍為{10，20，30，···，100}以及最大迭代次數變化范圍為{10，20，30，···，100}。研究一個參數對性能影響，固定其他2個參數。由于空間有限，本文僅討論WNMF-WCN模型與3個參數的變化關系，WNMF-WAA和WNMF-WRA類似WNMF-WCN。

4.1 參數α變化

參數 α約束因子矩陣預防模型過度擬合，其結果如圖2所示。當α=0時，所提模型退化為融合多類局部結構的加權非負矩陣分解模型，PCC和Precision值較高，表明該模型以最小誤差重構原始網絡。隨著 α增加，直到α=3時，PCC和Precision值最優，而當α>3時，PCC和Precision值顯著下降，表明 α取較大值時影響算法收斂速度。因此，α=3時，所提模型獲得最優預測準確度。

圖2 參數α變化對應PCC和Precision值

4.2 參數K變化

所提模型性能直接受參數K影響：K過小導致預測準確度下降；K太大導致時間復雜度增加。其實驗結果如圖3所示。當K=10時，PCC和Precision值最小，表明潛在空間無法捕獲更多加權網絡結構和自然權重鏈接。當K值逐漸增加，PCC和Precision值隨之改善，直到K=60，PCC和Precision獲得最優預測準確度，表明所提模型的潛在空間獲得足夠網絡結構。當K>60時，PCC和Precision值開始穩定。因此K=60時，所提模型性能最優。

圖3 參數K變化對應PCC和Precision值

4.3 最大迭代次數變化

最大迭代次數直接影響所提模型的收斂速度，其實驗結果如圖4所示。僅MES網絡在開始時處于波動而其他5個加權網絡波動不明顯，當迭代次數為60時，在6個加權網絡上的PCC和Precision值基本保持穩定。

圖4 最大迭代次數變化對應PCC和Precision值

5 結束語

現有大量的鏈路預測算法僅考慮無向無權網絡而忽略權重貢獻。如何將非負矩陣分解模型擴展到加權網絡的鏈路預測方法中是一種挑戰。針對現有大部分非負矩陣分解算法僅適用于無向無權網絡，本文提出一個融合自然權重和多類結構的加權非負矩陣分解的鏈路預測模型。該模型將3個經典加權局部相似度作為指示矩陣分配給非負矩陣分解模型，構建加權非負矩陣分解的鏈路預測模型。此外，提供拉格朗日乘法法則優化模型和學習模型的參數，并重構原始網絡獲得鏈路預測分數矩陣。在6個真實加權網絡上，將該模型與現有代表性加權網絡方法比較，其實驗結果表明該模型的預測性能獲得明顯改善。