融合高階路徑和非負(fù)矩陣分解的鏈路預(yù)測

陳廣福 陳 浩

(1. 武夷學(xué)院 數(shù)學(xué)與計(jì)算機(jī)學(xué)院， 福建 武夷山 354300；2. 認(rèn)知計(jì)算與智能信息處理福建省高校重點(diǎn)實(shí)驗(yàn)室， 福建 武夷山 354300；3. 江蘇大學(xué)京江學(xué)院 電子信息工程學(xué)院， 江蘇 鎮(zhèn)江 212013)

0 前 言

現(xiàn)實(shí)世界中存在大量的復(fù)雜系統(tǒng)，如交通運(yùn)輸系統(tǒng)、生物系統(tǒng)和電力系統(tǒng)等。為刻畫和研究抽象的復(fù)雜系統(tǒng)，常使用復(fù)雜網(wǎng)絡(luò)對其進(jìn)行描述，其中節(jié)點(diǎn)表示實(shí)體，鏈接表示實(shí)體間的交互關(guān)系。如何分析和挖掘復(fù)雜網(wǎng)絡(luò)是網(wǎng)絡(luò)科學(xué)的研究熱點(diǎn)之一，而鏈路預(yù)測為分析和挖掘復(fù)雜網(wǎng)絡(luò)提供了重要的理論支持。鏈路預(yù)測的目的是根據(jù)已知結(jié)構(gòu)信息來預(yù)測缺失鏈接或?qū)硇纬蛇B邊的可能性[1]。鏈路預(yù)測在多種領(lǐng)域有著廣泛的應(yīng)用價(jià)值，如預(yù)測新增航線[2]、提供完整的中醫(yī)藥知識(shí)圖譜[3]和藥物組合推薦[4]。

加權(quán)網(wǎng)絡(luò)廣泛存在于現(xiàn)實(shí)世界中，但不同加權(quán)網(wǎng)絡(luò)中的鏈接權(quán)重蘊(yùn)含著不同含義，如用戶信任/不信任網(wǎng)絡(luò)中的正鏈接權(quán)重表示信任，在二部圖語言網(wǎng)絡(luò)中的鏈接權(quán)重代表給定語言和國家的人口比例。因此，鏈接權(quán)重用來表示加權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)間鏈接的強(qiáng)弱關(guān)系。目前，大部分鏈路預(yù)測的研究僅針對無向無權(quán)網(wǎng)絡(luò)，忽略了鏈接權(quán)重信息，因此如何捕獲鏈接權(quán)重信息是值得思考的問題。一些研究人員開始探索加權(quán)網(wǎng)絡(luò)的鏈路預(yù)測問題。學(xué)者們將共同鄰居(common neighbors，CN)、資源分配(resource allocation，RA)和adamic-adar(AA)等指標(biāo)與加權(quán)社交網(wǎng)絡(luò)融合構(gòu)建為加權(quán)共同鄰居(weighted common neighbors，WCN)、加權(quán)資源分配(weighted resource allocation，WRA)和加權(quán)adamic-adar(weighted adamic-adar，WAA)[5-8]。De等人將局部路徑(local path，LP)擴(kuò)展到加權(quán)網(wǎng)絡(luò)，考慮二階和三階邊權(quán)強(qiáng)度，構(gòu)建加權(quán)局部路徑(weigthed local path，WLP)[9]。Zhu等人將加權(quán)互信息(weighted mutual information，WMI)與WCN、WAA和WRA等3個(gè)局部指標(biāo)融合構(gòu)建為WMIWCN、WMIWAA和WMIWRA，以保持自然權(quán)重和局部結(jié)構(gòu)信息[10]。郭景峰等人考慮了加權(quán)網(wǎng)絡(luò)二階和三階路徑信息，提高了預(yù)測準(zhǔn)確度[11]。袁榕等人提出基于耦合邊聚類和擴(kuò)散性的拓?fù)錂?quán)重鏈路預(yù)測框架，提高了預(yù)測精度[12]。傅馨玉等人通過耦合加權(quán)局部相似度指標(biāo)(WCN、WAA和WRA)與節(jié)點(diǎn)重要性特征(度中心性、介數(shù)中心性、接近中心性和特征向量中心性)，構(gòu)建適用于小型加權(quán)網(wǎng)絡(luò)的預(yù)測指標(biāo)[13]。

Wind等人首次利用非負(fù)矩陣分解的低秩性和非負(fù)性等特點(diǎn)構(gòu)建模型，以預(yù)測缺失鏈接權(quán)重[14]。Pech 等人利用線性優(yōu)化(linear optimization，LO)指標(biāo)，對節(jié)點(diǎn)三階路徑求解最優(yōu)值[15]。Chen等人基于加權(quán)非負(fù)矩陣分解框架融合自然權(quán)重和節(jié)點(diǎn)聚類[16]。上述加權(quán)預(yù)測指標(biāo)都只考慮了自然權(quán)重和局部結(jié)構(gòu)信息，而忽略了全局結(jié)構(gòu)信息的重要性。為此，本次研究提出了融合高階路徑和非負(fù)矩陣分解的鏈路預(yù)測模型(nonnegative matrix factorization via high-order path，NMF-HP)。

1 方法

1.1 相關(guān)概念

給定一個(gè)不考慮自環(huán)鏈接的無向加權(quán)網(wǎng)絡(luò)G(V,E,W)，其中V表示網(wǎng)絡(luò)節(jié)點(diǎn)集；E={(vi,vj)|vi,vj∈V}，表示節(jié)點(diǎn)間鏈接集；W表示鏈接權(quán)重集。A表示G的鄰接矩陣，A=[aij]n×n，如果節(jié)點(diǎn)vi和vj之間存在鏈接，則aij=wij，否則aij=0。

為了驗(yàn)證模型性能，將可觀測鏈接集E隨機(jī)劃分為訓(xùn)練集ET和測試集EP，ET∩EP=φ，ET∪EP=E。

1.2 加權(quán)網(wǎng)絡(luò)高階路徑

權(quán)重結(jié)構(gòu)是加權(quán)網(wǎng)絡(luò)的重要特征，如何捕獲權(quán)重結(jié)構(gòu)是加權(quán)網(wǎng)絡(luò)鏈路預(yù)測的關(guān)鍵一環(huán)。本次研究通過計(jì)算鏈接權(quán)重強(qiáng)度來獲取并擴(kuò)展節(jié)點(diǎn)二階路徑信息，以保持高階路徑信息。節(jié)點(diǎn)強(qiáng)度是加權(quán)網(wǎng)絡(luò)的基本拓?fù)湫畔?，反映?jié)點(diǎn)與鄰居之間的關(guān)聯(lián)強(qiáng)度，節(jié)點(diǎn)強(qiáng)度越大，節(jié)點(diǎn)鄰域權(quán)重占加權(quán)網(wǎng)絡(luò)權(quán)重的比例越大。

計(jì)算加權(quán)網(wǎng)絡(luò)任意節(jié)點(diǎn)vi的權(quán)重強(qiáng)度Si，如式(1)所示：

(1)

式中：ni—— 節(jié)點(diǎn)vi的鄰域集；

wij—— 節(jié)點(diǎn)vi和vj的權(quán)重。

利用鏈接權(quán)重強(qiáng)度(link weighted strength，LWS)衡量加權(quán)網(wǎng)絡(luò)的局部相似度，LWS越大，節(jié)點(diǎn)相似的可能性越高。LWS的計(jì)算如式(2)所示:

(2)

將式(2)擴(kuò)展成任意節(jié)點(diǎn)的k階相似度，如式(3)所示：

(3)

本次研究僅考慮k=2和k= 3的情況，通過融合二階和三階路徑來構(gòu)建最終相似度[17]，以同時(shí)保持權(quán)重局部和全局結(jié)構(gòu)，如式(4)所示：

(4)

1.3 NMF-HP鏈路預(yù)測模型構(gòu)建

非負(fù)矩陣分解能夠有效捕獲原始網(wǎng)絡(luò)的鏈接權(quán)重。設(shè)任意加權(quán)網(wǎng)絡(luò)鄰接矩陣A的損失函數(shù)如式(5)所示：

(5)

由于式(5)僅能捕獲原始網(wǎng)絡(luò)自然權(quán)重鏈接而無法捕獲加權(quán)網(wǎng)絡(luò)結(jié)構(gòu)，因此將圖正則化技術(shù)與式(4)相融合，同時(shí)保持權(quán)重拓?fù)浣Y(jié)構(gòu)。

設(shè)hi和hj是任意節(jié)點(diǎn)的特征向量，如式(6)所示：

=tr(HTDH)-tr(HTSH)

=tr(HTLH)

(6)

式中：tr() —— 矩陣跡；

D—— 對角矩陣；

L——S的拉普拉斯矩陣，L=D-S。

耦合式(5)和式(6)，構(gòu)建統(tǒng)一鏈路預(yù)測模型，模型損失函數(shù)如式(7)所示：

(7)

式中：α—— 控制局部和高階路徑權(quán)重的參數(shù)；

β—— 約束因子，用于預(yù)防模型過度擬合。

為學(xué)習(xí)模型參數(shù)，使用拉格朗日乘法規(guī)則求解模型最優(yōu)解，重寫式(7)得到：

J(F,H)=tr(AAT-2AFHT+FHTHFT)+

αtr(HTLH)+βtr(HTH)+

βtr(FTF)

(8)

引入拉格朗日乘子矩陣Φ=(φnk)和Ψ=(ψnk)，重寫式(8)得到：

J(F,H)=tr(AAT-2AFHT+FHTHFT)+

αtr(HTLH)+βtr(HTH)+βtr(FTF)+

tr(ΦHT)+tr(ΨFT)

(9)

(1) 固定F,更新H。

首先, 刪除式(9)中與H無關(guān)項(xiàng),得到：

J(H)=tr(-2AFHT+FHTHFT)+αtr(HTLH)+βtr(HTH)+tr(ΦHT)

(10)

其次，對式(10)求偏導(dǎo)得到：

βH+Φ

(11)

然后，根據(jù) KKT(karush-kuhn-tucker)條件且φnkhnk=0，得到：

-AF+HFTF-α(D-S)H+βH=0

(12)

最后,得到以下更新規(guī)則：

(13)

(2) 固定H,更新F。

首先，刪除式(9)中與F無關(guān)項(xiàng),得到：

J(F)=tr(-2AFHT+FHTHFT)+

βtr(FTF)+tr(ΨFT)

(14)

其次，對式(14)求偏導(dǎo)得到：

(15)

然后，根據(jù) KKT條件且ψnkfnk=0，得到：

-ATH+FHTH+βF=0

(16)

最后，得到以下更新規(guī)則:

(17)

2 實(shí)驗(yàn)結(jié)果分析

2.1 評價(jià)度量

(1) AUC(areas under curve)[17]是ROC曲線與坐標(biāo)軸圍成的面積，AUC的計(jì)算如式(18)所示：

(18)

式中：Auc—— AUC；

n—— 比較次數(shù)；

n1—— 測試集中節(jié)點(diǎn)分?jǐn)?shù)大于不存在集中節(jié)點(diǎn)分?jǐn)?shù)的次數(shù)；

n2—— 測試集中節(jié)點(diǎn)分?jǐn)?shù)等于不存在集中節(jié)點(diǎn)分?jǐn)?shù)的次數(shù)。

(2) PCC(pearson correlation coefficient)[18]用于評價(jià)預(yù)測向量和實(shí)際向量的線性關(guān)系，PCC的計(jì)算如式(19)所示：

(19)

式中：CPC—— PCC；

wij—— 預(yù)測向量；

rij—— 實(shí)際向量；

(3) 精確度(Precision)[19]僅考慮前M個(gè)鏈接是否預(yù)測準(zhǔn)確，若有m個(gè)鏈接屬于測試集，則精確度的計(jì)算如式(20)所示：

(20)

式中：P—— 精確度。

2.2 數(shù)據(jù)集

本次研究選取6個(gè)加權(quán)網(wǎng)絡(luò)來測試NMF-HP模型性能。論壇網(wǎng)絡(luò)(FORUM)包括899個(gè)用戶和522個(gè)主題，節(jié)點(diǎn)表示用戶，鏈接權(quán)重表示交換信息數(shù)量；食物網(wǎng)絡(luò)(BAYdry，BAY)是由128個(gè)節(jié)點(diǎn)和2 106條鏈接構(gòu)成的干旱季節(jié)南佛羅里達(dá)州柏樹濕地的碳交換食物網(wǎng)；美國航空運(yùn)輸網(wǎng)絡(luò)(USAir，USA)中的節(jié)點(diǎn)和鏈接分別代表機(jī)場和路線，鏈接權(quán)重表示航班數(shù)量；秀麗隱桿線蟲網(wǎng)絡(luò)(CELegans，CEL)包括297個(gè)節(jié)點(diǎn)和2 148條鏈接，節(jié)點(diǎn)表示神經(jīng)元，鏈接表示突觸聯(lián)系，鏈接權(quán)重表示2個(gè)神經(jīng)元之間的突觸數(shù)量；生物網(wǎng)1(CEGN)包括2 219個(gè)節(jié)點(diǎn)和107 352條鏈接，節(jié)點(diǎn)表示基因，鏈接權(quán)重表示細(xì)菌和古細(xì)菌直系同源基因的領(lǐng)域關(guān)聯(lián)程度；生物網(wǎng)2(SCLC)包括2 003個(gè)節(jié)點(diǎn)和40 898條鏈接，節(jié)點(diǎn)表示蛋白質(zhì)，鏈接權(quán)重表示中小型蛋白質(zhì)的相互作用[20]。

2.3 基準(zhǔn)方法

本次研究選取9個(gè)主流的加權(quán)網(wǎng)絡(luò)鏈路預(yù)測方法與NMF-HP模型進(jìn)行對比分析。

(1) 基于加權(quán)局部相似度的鏈路預(yù)測。WCN、WAA、WRA[5]的定義如式(21)所示：

(21)

式中：z∈Oxy表示節(jié)點(diǎn)x和y的共同鄰居。

(2) 基于互信息和加權(quán)局部結(jié)構(gòu)相似度耦合的鏈路預(yù)測。WMIWCN、WMIWAA和WMIWRA[9]的定義如式(22)所示：

(22)

式中：I(Lxy;z) —— 節(jié)點(diǎn)x和y的共同鄰居互信息。

(3) 加權(quán)優(yōu)先連接(weigthed preferential attachment，WPA)[11]是任意節(jié)點(diǎn)乘積度，其定義如式(23)所示：

(23)

式中：Γ(x)表示節(jié)點(diǎn)x的鄰居集。

(4) 加權(quán)局部路徑(weigthed local path，WLP)[11]融合了加權(quán)網(wǎng)絡(luò)二階和三階路徑信息，其定義如式(24)所示：

(24)

式中：γ—— 超級參數(shù)；

l—— 路徑長度。

(5) 線性優(yōu)化(linear optimization，LO)[15]通過相鄰節(jié)點(diǎn)貢獻(xiàn)的線性最優(yōu)化計(jì)算節(jié)點(diǎn)未鏈接相似度，其定義如式(25)所示：

SL0=αA(αATA+I)-1ATA

(25)

2.4 實(shí)驗(yàn)結(jié)果分析

NMF-HP模型包括4個(gè)重要參數(shù)：α、β、迭代次數(shù)和K。設(shè)α=5，β=0.5，K=70，迭代次數(shù)為70。利用AUC、PCC和Precision度量來評價(jià)基準(zhǔn)指標(biāo)和NMF-HP模型性能。由實(shí)驗(yàn)結(jié)果(見表1、圖1和圖2)可知：

圖1 不同方法在加權(quán)網(wǎng)絡(luò)上的PCC值

圖2 不同方法在加權(quán)網(wǎng)絡(luò)上的Precision值

表1 不同方法在加權(quán)網(wǎng)絡(luò)上的AUC值

(1) AUC度量，NMF-HP模型在除USA之外的5個(gè)加權(quán)網(wǎng)絡(luò)上均獲得了最優(yōu)預(yù)測準(zhǔn)確度；NMF-HP模型在CEL上的AUC值比WMIWRA提高了3.9%，在BAY上的AUC值比LO提高了0.9%，在FORUM上的AUC值比WRA提高了4.5%，在CEGN和SCLC上的AUC值分別比WLP提高了3.7%和0.5%。PCC度量，NMF-HP模型在CEL、BAY、CEGN和SCLC上的PCC值分別比LO提高了24.0%、12.6%、10.4%和14.7%，在FORUM上的PCC值比WMIWAA提高了51.8%。Precision度量，NMF-HP模型在CEL、BAY、FORUM和CEGN上的Precision值分別比LO提高了3.8%、10.2%、42.8%和4.3%。

(2) WCN、WAA和WRA僅考慮了網(wǎng)絡(luò)鏈接權(quán)重信息，在大部分加權(quán)網(wǎng)絡(luò)上的預(yù)測準(zhǔn)確度較低，主要原因在于其只獲得了部分網(wǎng)絡(luò)結(jié)構(gòu)信息。WMIWCN、WMIWAA和WMIWRA在CEL和BAY上的預(yù)測準(zhǔn)確度優(yōu)于WCN、WAA和WRA，主要原因在于其同時(shí)考慮了自然權(quán)重和加權(quán)局部結(jié)構(gòu)。

(3) WLP和LO考慮了三階路徑信息，在BAY、CEGN和SCLC上的預(yù)測準(zhǔn)確度顯著高于其他基準(zhǔn)方法。NMF-HP模型考慮了多路徑信息，其AUC和PCC值顯著高于WLP和LO，表明考慮多路徑信息的加權(quán)網(wǎng)絡(luò)性能優(yōu)于二階或三階路徑。

(4) PCC用來衡量實(shí)際鏈接權(quán)重與預(yù)測權(quán)重間的線性關(guān)系。PCC值越大，預(yù)測權(quán)重越接近實(shí)際權(quán)重。NMF-HP模型在大部分加權(quán)網(wǎng)絡(luò)上獲得了最優(yōu)性能，表明融合自然權(quán)重和高階路徑信息的網(wǎng)絡(luò)更接近于原始網(wǎng)絡(luò)。

由于篇幅有限，在此僅利用AUC來測試NMF-HP模型的魯棒性。由實(shí)驗(yàn)結(jié)果(見圖3)可知，NMF-HP模型在不同的訓(xùn)練集占比下均能獲得最優(yōu)性能，表明附加高階路徑信息可以捕獲足夠的網(wǎng)絡(luò)結(jié)構(gòu)，并對稀疏網(wǎng)絡(luò)具有魯棒性。其他基準(zhǔn)方法在不同的訓(xùn)練集占比下波動(dòng)明顯，表明僅依靠網(wǎng)絡(luò)自然權(quán)重和局部結(jié)構(gòu)是不夠的，尤其是當(dāng)訓(xùn)練集占比為40%～50%時(shí)，缺失鏈接占比達(dá)到50%～60%，在網(wǎng)絡(luò)十分稀疏的情況下NMF-HP模型的AUC值優(yōu)于其他基準(zhǔn)方法。

圖3 不同訓(xùn)練集占比下的AUC值

3 參數(shù)敏感性分析

NMF-HP模型通過調(diào)節(jié)α、β、K和迭代次數(shù)等4個(gè)參數(shù)來獲得最優(yōu)預(yù)測精度。設(shè)α、β的取值范圍為{0，0.05，0.5， 5，50，500}，K的取值范圍為{10，20，30，…，100}，迭代次數(shù)的取值范圍為{10，20，30，…，100}。由于篇幅有限，在此僅分析AUC度量隨參數(shù)的變化情況。

3.1 參數(shù)α的變化

參數(shù)α是控制二階路徑和三階路徑權(quán)重的貢獻(xiàn)，不同參數(shù)α下的AUC值如圖4所示。當(dāng)α=0時(shí)，NMF-HP模型退化為非負(fù)矩陣分解基礎(chǔ)模型和預(yù)防過度擬合的正則化項(xiàng)，在6個(gè)加權(quán)網(wǎng)絡(luò)上的預(yù)測準(zhǔn)確度較低，進(jìn)一步說明融合二階路徑和三階路徑信息的必要性。AUC值隨著α的增加而增加，直到α=5時(shí)，AUC值最大。當(dāng)α>5時(shí)，AUC值開始逐漸下降，表明α取較大值會(huì)影響NMF-HP模型捕獲多路徑信息。因此，當(dāng)α=5時(shí)，NMF-HP模型性能最優(yōu)。

圖4 不同參數(shù)α值下的AUC值

3.2 參數(shù)β的變化

參數(shù)β用于防止NMF-HP模型過度擬合，不同參數(shù)β下的AUC值如圖5所示。當(dāng)β=0時(shí)，NMF-HP模型退化為非負(fù)矩陣分解基礎(chǔ)模型和多階路徑信息，在6個(gè)加權(quán)網(wǎng)絡(luò)上的預(yù)測準(zhǔn)確度較低，表明NMF-HP模型存在過度擬合。AUC值隨著β的增加而增加，直到β=0.5時(shí)，AUC值最大。當(dāng)β>0.5時(shí)，AUC值開始逐漸下降，表明β取較大值時(shí)無法有效抑制過度擬合。因此，當(dāng)β=0.5時(shí)，NMF-HP模型性能最優(yōu)。

圖5 不同參數(shù)β值下的AUC值

3.3 參數(shù)K的變化

參數(shù)K的變化直接影響著NMF-HP模型性能，不同參數(shù)K下的AUC值如圖6所示。當(dāng)K=10時(shí)，AUC值最小，表明潛在空間較小的情況下NMF-HP模型無法挖掘更多網(wǎng)絡(luò)結(jié)構(gòu)。當(dāng)K逐漸增加時(shí)， AUC值開始上升，直到K≥70時(shí)，AUC值趨于穩(wěn)定。因此，當(dāng)K=70時(shí)，NMF-HP模型性能最優(yōu)。

圖6 不同參數(shù)K值下的AUC值

3.4 迭代次數(shù)的變化

迭代次數(shù)的大小直接影響著NMF-HP模型的預(yù)測精度，迭代次數(shù)過大會(huì)導(dǎo)致運(yùn)行時(shí)間增加、預(yù)測精度下降，不同迭代次數(shù)下的AUC值如圖7所示。當(dāng)?shù)螖?shù)為10時(shí)，AUC值最小，表明迭代次數(shù)過小不利于捕獲多階節(jié)點(diǎn)路徑信息。隨著迭代次數(shù)的增加，AUC值開始逐漸上升，直到迭代次數(shù)大于70時(shí)，AUC值開始保持穩(wěn)定。因此，當(dāng)?shù)螖?shù)為70時(shí)，NMF-HP模型性能最優(yōu)。

圖7 不同迭代次數(shù)下的AUC值

4 結(jié) 語

本次研究提出了融合高階路徑和非負(fù)矩陣分解的鏈路預(yù)測。首先，根據(jù)加權(quán)網(wǎng)絡(luò)點(diǎn)強(qiáng)度計(jì)算邊權(quán)強(qiáng)度，以保持加權(quán)網(wǎng)絡(luò)局部結(jié)構(gòu)；其次，將任意加權(quán)網(wǎng)絡(luò)鄰接矩陣映射到低秩隱特征空間，以捕獲一階權(quán)重鏈接；然后，擴(kuò)展加權(quán)強(qiáng)度為二階路徑和三階路徑信息，采用圖正則化技術(shù)融合多階路徑信息，同時(shí)保持網(wǎng)絡(luò)局部和全局結(jié)構(gòu)，并通過更新規(guī)則學(xué)習(xí)模型參數(shù)；最后，通過實(shí)驗(yàn)證明NMF-HP模型性能優(yōu)于現(xiàn)有的主流基準(zhǔn)方法。