基于對(duì)偶圖正則化非負(fù)矩陣分解的鏈路預(yù)測

陳廣福，閻兵早

(1.武夷學(xué)院 數(shù)學(xué)與計(jì)算機(jī)學(xué)院,福建 武夷山 354300；2.認(rèn)知計(jì)算與智能信息處理福建省高校重點(diǎn)實(shí)驗(yàn)室,福建 武夷山 354300)

大量真實(shí)世界復(fù)雜系統(tǒng)均可抽象為復(fù)雜網(wǎng)絡(luò)，例如航空網(wǎng)、電力網(wǎng)和在線社交網(wǎng)等，其節(jié)點(diǎn)表示實(shí)體，鏈接表示為實(shí)體間關(guān)聯(lián)程度.大部分情況下，由于受噪聲和冗余鏈接等因素影響，所收集的網(wǎng)絡(luò)數(shù)據(jù)是缺失和不完整的.因此，預(yù)測缺失鏈接是網(wǎng)絡(luò)分析關(guān)鍵任務(wù)之一，而鏈路預(yù)測目標(biāo)是通過已知網(wǎng)絡(luò)結(jié)構(gòu)去預(yù)測缺失鏈接形成可能性[1].因此，鏈路預(yù)測不僅有巨大理論價(jià)值且有廣泛應(yīng)用價(jià)值.例如社交網(wǎng)為不同用戶推薦新朋友，獲得更好的用戶體驗(yàn)[2]；在生物網(wǎng)，預(yù)測蛋白質(zhì)之間未知的相互作用，顯著降低實(shí)驗(yàn)成本[3].

當(dāng)前，大量基于不同理論的鏈路預(yù)測算法涌現(xiàn)出來，其中基于結(jié)構(gòu)相似度和基于減維方法最受關(guān)注.基于相似度算法根據(jù)已知網(wǎng)絡(luò)結(jié)構(gòu)、節(jié)點(diǎn)屬性和節(jié)點(diǎn)聚類等信息計(jì)算尚未鏈接節(jié)點(diǎn)分?jǐn)?shù).基于相似度算法又可劃分為局部相似度、半局部和全局相似度，其中局部相似度利用局部結(jié)構(gòu)及聚類等信息去統(tǒng)計(jì)節(jié)點(diǎn)共同鄰居數(shù)量，計(jì)算未鏈接節(jié)點(diǎn)間預(yù)測分?jǐn)?shù)，共同鄰居(common neighbors，CN)[4]、資源分配(resource allocation，RA)[5]和adamic-adar(AA)[6]指標(biāo)是其中代表.另外，Zhou等[7]將節(jié)點(diǎn)三階路徑信息與CN、AA和RA相融合捕獲更多網(wǎng)絡(luò)節(jié)點(diǎn)信息，上述方法缺點(diǎn)是敏感于稀疏網(wǎng)絡(luò).全局相似度考慮節(jié)點(diǎn)高階路徑信息獲得節(jié)點(diǎn)預(yù)測分?jǐn)?shù).例如顧秋陽等[8]提出高階相似度預(yù)測算法，該算法以高階路徑信息為判別特征，并懲罰節(jié)點(diǎn)有效長路徑；Pech等[9]提出線性最優(yōu)化(linear optimization，LO)算法用于多類型網(wǎng)絡(luò).半局部相似度克服了全局相似度不足，能夠調(diào)節(jié)算法性能與時(shí)間復(fù)雜度的平衡關(guān)系.Rafiee等[10]提出共同鄰居度懲罰預(yù)測方法，通過泛化CN、AA和RA局部相似度獲得統(tǒng)一的預(yù)測框架，并與節(jié)點(diǎn)聚類系數(shù)相融合提高預(yù)測準(zhǔn)確度；還有劉樹新等[11]融合節(jié)點(diǎn)間二階和三階路徑拓?fù)湫畔⑻岣哔Y源分配能力.基于減維方法可劃分為網(wǎng)絡(luò)表示和非負(fù)矩陣分解的方法，下面重點(diǎn)介紹非負(fù)矩陣分解的方法，該類方法將任意網(wǎng)絡(luò)鄰接矩陣映射到低維潛在空間去探索網(wǎng)絡(luò)潛在結(jié)構(gòu)信息.例如Wang等[12]提出基于非負(fù)矩陣分解的擾動(dòng)框架去探索網(wǎng)絡(luò)結(jié)構(gòu)信息；Chen等[13]將圖正則化和稀疏學(xué)習(xí)與魯棒非負(fù)矩陣分解相融合去保持網(wǎng)絡(luò)結(jié)構(gòu)信息；陳廣福等[14]將聚類信息與非負(fù)矩陣分解融合去保持網(wǎng)絡(luò)局部結(jié)構(gòu)信息，上述方法缺點(diǎn)是僅考慮部分網(wǎng)絡(luò)結(jié)構(gòu)信息.

針對(duì)以上不足，將解決以下2個(gè)問題:① 如何捕獲網(wǎng)絡(luò)的一階、局部和全局結(jié)構(gòu)信息；② 啟用對(duì)偶圖正則化如何同時(shí)保持局部和全局結(jié)構(gòu).針對(duì)以上2個(gè)問題，首先，使用隨機(jī)游走方法捕獲網(wǎng)絡(luò)全局結(jié)構(gòu)，再利用杰卡爾德系數(shù)捕獲網(wǎng)絡(luò)局部結(jié)構(gòu)；其次，將無向無權(quán)網(wǎng)絡(luò)鄰接矩陣映射到低維潛在空間保持原始網(wǎng)絡(luò)可觀察鏈接，并啟用對(duì)偶圖正則化方法同時(shí)保持局部和全局結(jié)構(gòu)；最后，融合一階、局部和全局結(jié)構(gòu)提出基于對(duì)偶正則化非負(fù)矩陣分解(dual graph-regularized nonnegative matrix factorization，DRNMF)預(yù)測模型.此外，利用拉格朗日更新法則學(xué)習(xí)參數(shù)模型，并用最小誤差重構(gòu)原始網(wǎng)絡(luò)獲得最優(yōu)預(yù)測分?jǐn)?shù)矩陣.在6個(gè)真實(shí)世界網(wǎng)絡(luò)上，運(yùn)用AUC和AUPR度量評(píng)估所提模型性能.

1 方法的提出

1.1 問題描述

1.2 隨機(jī)游走和杰卡爾德相似度

(1)

令k=3,式(1)轉(zhuǎn)換為三階相似度，有

(2)

杰卡爾德相似度即Jaccard相似度節(jié)點(diǎn)間共同鄰居數(shù)與所有節(jié)點(diǎn)間鄰居數(shù)的比，可以更好反映網(wǎng)絡(luò)局部結(jié)構(gòu)信息.因此，利用Jaccard相似度去捕獲網(wǎng)絡(luò)局部結(jié)構(gòu)，定義如下：

(3)

其中Γ(x)表示節(jié)點(diǎn)x的鄰居數(shù).

1.3 DRNMF模型構(gòu)建

(4)

Tr(WTD3W)-Tr(WTT3W)=Tr(WTLwW),

(5)

其中，Tr(·)表示矩陣的跡，D3是對(duì)角矩陣且Lw=D3-S3是S3的拉普拉斯矩陣.

其次，對(duì)偶圖正則化方法將特征矩陣H與式(3)相結(jié)合去保持局部結(jié)構(gòu)信息，定義如下：

Tr(HTDJaccardH)-Tr(HTSJaccardH)=Tr(HTLhH),

(6)

其中，DJaccard是對(duì)角矩陣且Lh=DJaccard-SJaccard是SJaccard的拉普拉斯矩陣.

通過融合式(4)(5)(6)共同構(gòu)建統(tǒng)一鏈路預(yù)測模型DRNMF，其執(zhí)行框圖如圖1所示.

圖1 DRNMF框架Fig.1 DRNMF framework

由圖1所示，DRNMF的損失函數(shù)為

(7)

使用拉格朗日乘法規(guī)則學(xué)習(xí)所提模型參數(shù).首先，重寫式(7)，有

J(W,H)=Tr(AAT-2AHTWT+WHHTWT)+αTr(WTLwW)+βTr(HTLhH),

(8)

引入拉格朗日乘子矩陣Φ=[φ]nk和Ψ=[ψnk]，然后再重寫式(8)，有

J(W,H)=Tr(AAT-2AHTWT+WHHTWT)+αTr(WTLwW)+βTr(HTLhH)+Tr(ΦHT)+Tr(ΨWT)，

(9)

固定W,更新H.刪除式(9)中與H無關(guān)項(xiàng)，有

J(W,H)=Tr(-2AHTWT+WHHTWT)+βTr(HTLhH)+Tr(ΦHT),

求J(H)關(guān)于H的偏導(dǎo),有以下等式成立

由KKT(Karush-Kuhn-Tucker)條件且φnkhnk=0，有

-AWT+WTWH-αLhH=0,

因此，更新規(guī)則如下：

(10)

固定W,更新H.刪除式(9)中與W無關(guān)項(xiàng),有

J(W,H)=Tr(-2AHTWT+WHHTWT)+αTr(WTLwW)+Tr(ΨWT),

求J(W)關(guān)于W的偏導(dǎo)，有

由KKT條件及ψnkwnk=0，有

-AWT+WHHT+βLwW=0,

因此，得到以下更新規(guī)則：

(11)

通過以上公式迭代更新所提模型參數(shù)，因此，所提算法DRNMF描述如表1所示.

表1 DRNMF算法Tab.1 DRNMF algorithm

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

2.1 評(píng)價(jià)度量

利用AUC[16]和AUPR[17]2個(gè)度量去評(píng)估所用方法的性能，其中AUPR是綜合性指標(biāo).2個(gè)度量的值越高表示該方法預(yù)測準(zhǔn)確度越高，定義如下.

1) AUC是ROC曲線與坐標(biāo)軸圍成的面積，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) AUPR是召回率(recall)和準(zhǔn)確率(precision)圍成的面積.設(shè)TP(true positive)表示真正例，F(xiàn)N(false negative)表示假反例，F(xiàn)P(false positive)表示假正例和TN(true negative)表示真反例，那么Recall和Precision定義如下：

再利用復(fù)合梯形面積法近似求AUPR，定義：

AUPR=trapz(Recall，Precision),

其中，trapz是直接調(diào)用Matlab的梯形數(shù)值積分函數(shù).

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

下面介紹6種無向無權(quán)網(wǎng)絡(luò)，其拓?fù)涮卣鹘y(tǒng)計(jì)在表2中，6個(gè)數(shù)據(jù)集具體說明如下：

1) 論文引用網(wǎng)絡(luò)(SmaGr，SG)[18]是關(guān)于網(wǎng)絡(luò)理論與實(shí)驗(yàn)的引用網(wǎng)絡(luò).它由1 024個(gè)節(jié)點(diǎn)和4 916條鏈接組成.鏈接方向表示引用關(guān)系.

表2 6個(gè)真實(shí)網(wǎng)絡(luò)的結(jié)構(gòu)特征Tab.2 Stuctural features of six real networks

2) EPA[18]是信息網(wǎng)絡(luò)，它由4 471個(gè)節(jié)點(diǎn)和8 890條鏈接組成.

3) 美國航空運(yùn)輸網(wǎng)絡(luò)(USAir，USA)[18]由332個(gè)節(jié)點(diǎn)和2 126個(gè)節(jié)點(diǎn)組成鏈接.節(jié)點(diǎn)是機(jī)場，鏈接表示2個(gè)機(jī)場間距離.

4) 歐洲電子郵件核心子集網(wǎng)(Email，EMA)[18]由1 005個(gè)節(jié)點(diǎn)和32 770條鏈接組成.節(jié)點(diǎn)表示成員，鏈接表示成員間所有傳入和傳出的電子郵件.

5) 腦網(wǎng)絡(luò)(Nb-Fly，NF)[18]由1 781個(gè)節(jié)點(diǎn)和8 911條鏈接組成.節(jié)點(diǎn)表示纖維束，鏈接表示纖維束之間的關(guān)系.

6) Router是路由層次網(wǎng)[18]，它由5 022個(gè)節(jié)點(diǎn)和6 258條鏈接構(gòu)成.節(jié)點(diǎn)表示路由器，鏈接表示路由器間數(shù)據(jù)交換關(guān)系.

2.3 基準(zhǔn)方法

為評(píng)估所提模型性能，啟用8個(gè)代表性方法與本文所提模型進(jìn)行比較，具體介紹如下.

1) 基于3長度路徑(3-length-based，L3)指標(biāo)融合CN、AA和RA，包含3個(gè)指標(biāo)包括CN-L3、AA-L3和RA-L3[7]，定義如下：

2) 線性最優(yōu)化(linear optimization，LO)[9]指標(biāo)用相鄰節(jié)點(diǎn)貢獻(xiàn)的線性求和分解表示節(jié)點(diǎn)形成的概率分?jǐn)?shù)，其定義如下：

SLO=αA3-α2A5+α3A7-α4A9+…,

其中,0<α<1.

3) 共同鄰居度懲罰(common neighbors degree penalization，CNDP)指標(biāo)[10]表示共同鄰居數(shù)與節(jié)點(diǎn)聚類系數(shù)關(guān)聯(lián)程度，定義如下：

其中，|Cz|是共同鄰居數(shù).

4) 非負(fù)矩陣分解擾動(dòng)模型(non-negative matrix factorization via deletion perturbation 1，NMFD1)[11]是基于非負(fù)矩陣分解的擾動(dòng)框架預(yù)測缺失鏈接.

5) 融合共同鄰居的概率矩陣分解模型(fusing probability matrix factorization via common neighbors，F(xiàn)PMF-CN)[19]，該模型融合鄰接矩陣和局部結(jié)構(gòu)，與概率矩陣分解模型共同構(gòu)建統(tǒng)一鏈路預(yù)測模型.

6) 節(jié)點(diǎn)和鏈接聚類指標(biāo)(node and link clustering，NLC)[20]，該指標(biāo)利用局部節(jié)點(diǎn)和鏈接聚類揭示節(jié)點(diǎn)與鏈接關(guān)聯(lián)程度，NLC定義如下：

2.4 結(jié)果分析

實(shí)驗(yàn)硬件平臺(tái)為Intel Core i5-6500 CPU臺(tái)式電腦，主頻 3.20 GHz，內(nèi)存8 GB，操作系統(tǒng)為Windows 10，所有算法均由Matlab R2016b實(shí)現(xiàn).另外，所提模型包括參數(shù)α、β及潛在空間維數(shù)K和最大迭代次數(shù).為公平比較所有的方法，所有數(shù)據(jù)集設(shè)α=0.5、β=0.5、K=70和最大迭代次數(shù)為70次.對(duì)于LO方法的參數(shù)設(shè)0.1和CNDP的參數(shù)設(shè)1.5.

首先，采用AUC和AUPR度量評(píng)估所用方法性能，其實(shí)驗(yàn)結(jié)果報(bào)告在表3.可觀察到以下一些現(xiàn)象.

1) DRNMF在6個(gè)網(wǎng)絡(luò)上均獲得高質(zhì)量預(yù)測準(zhǔn)確度.具體地，AUC度量，在USA、SG、BF、EMA、EPA和Router中，所提模型與第2優(yōu)秀預(yù)測者相比較，AUC值分別提升了2.5%、2.9%、2.2%、0.5%、1.3%和3.1%；AUPR度量，在USA、SG、BF、EMA、EPA和Router中，所提模型與第2優(yōu)秀預(yù)測者相比較，AUPR值分別提升了2.1%、2.1%、1.7%、2.6%、4.7%和8.9%.

2) CN-L3、AA-L3和RA-L3依賴于三階路徑信息.當(dāng)網(wǎng)絡(luò)稀疏時(shí)無法獲取更多網(wǎng)絡(luò)節(jié)點(diǎn)信息導(dǎo)致預(yù)測精度下降，NLC在EPA和Router上均獲得較差預(yù)測準(zhǔn)確度.主要原因是EPA和Router是高度稀疏網(wǎng)絡(luò)，而CNDP和LO是全局指標(biāo)，性能顯著優(yōu)于上述3個(gè)指標(biāo).FPMF-CN和NMFD1模型是基于非負(fù)矩陣分解理論的，性能均優(yōu)于三階及全局方法.DRNMF獲得高質(zhì)量性能的主要原因是同時(shí)保持一階、局部和全局結(jié)構(gòu)，從而在稀疏網(wǎng)絡(luò)上保持較高魯棒性.

表3 基準(zhǔn)方法與DRNMF在6個(gè)網(wǎng)絡(luò)上的預(yù)測準(zhǔn)確性Tab.3 Prediction accuracies of baseline methods and DRNMF on six networks

其次，測試DRNMF魯棒性，由于空間有限僅選取CDNP、LO、NLC、CN-L3和DRNMF 5個(gè)方法在USA和EMA上進(jìn)行對(duì)比，其結(jié)果報(bào)告在圖2.可觀察到DRNMF在不同比率訓(xùn)練集下均獲得最優(yōu)AUC和AUPR值，當(dāng)訓(xùn)練集為40%時(shí)意味著測試集占60%，網(wǎng)絡(luò)處于高度稀疏狀態(tài)，DRNMF性能優(yōu)于其他指標(biāo)且AUC和AUPR值未顯著波動(dòng)，表明DRNMF在稀疏網(wǎng)絡(luò)上保持較高魯棒性.

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

下面討論DRNMF主要參數(shù)對(duì)性能影響.DRNMF包含4個(gè)重要參數(shù)分別為：α、β、潛在空間維數(shù)K和最大迭代次數(shù).設(shè)α、β變化范圍分別為{0.05，0.5，5，50，500}、{0.05，0.5，5，50，500}，K變化范圍{10，20，30，…，100}，迭代次數(shù)變化范圍{10，20，30，…，100}.研究1個(gè)參數(shù)變化，則需要固定其余3個(gè)參數(shù).

3.1 參數(shù)α變化

參數(shù)α是約束全局結(jié)構(gòu)對(duì)DRNMF性能影響，實(shí)驗(yàn)結(jié)果報(bào)告在圖3中.可觀察到當(dāng)α>0.5時(shí)，AUC和AUPR

圖2 5個(gè)不同預(yù)測方法在不同比率下對(duì)應(yīng)的AUC和AUPR值Fig.2 Corresponding AUC and AUPR values of five different prediction methods under different ratios

圖3 不同參數(shù)α在6個(gè)網(wǎng)絡(luò)上對(duì)應(yīng)不同AUC和AUPR值Fig.3 Different parameters α correspond to different AUC and AUPR values on six networks

值逐漸下降直到α=500時(shí)預(yù)測準(zhǔn)確度最低.主要原因是α值過大則DRNMF損失函數(shù)誤差增大導(dǎo)致預(yù)測分?jǐn)?shù)矩陣不準(zhǔn)確.而當(dāng)α≥0.05時(shí)，AUC和AUPR值開始逐漸上升直到獲得最優(yōu)性能.因此，當(dāng)α=0.5時(shí)，6個(gè)網(wǎng)絡(luò)上AUC和AUPR值最優(yōu).

3.2 參數(shù)β變化

參數(shù)β是約束網(wǎng)絡(luò)局部結(jié)構(gòu)貢獻(xiàn)，實(shí)驗(yàn)結(jié)果報(bào)告在圖4中.可觀察當(dāng)β>0.5時(shí)，AUC和AUPR值逐漸下降，直到β=500時(shí)性能最差，表明β取值過大影響DRNMF捕獲局部結(jié)構(gòu).當(dāng)β≥0.05時(shí)AUC和AUPR值開始顯著提高.因此，當(dāng)β=0.5時(shí)，6個(gè)網(wǎng)絡(luò)上AUC和AUPR值最優(yōu).

圖4 不同參數(shù)β在6個(gè)網(wǎng)絡(luò)上對(duì)應(yīng)不同AUC和AUPR值Fig.4 Different parameters β correspond to different AUC and AUPR values on six networks

3.3 參數(shù)K變化

參數(shù)K大小直接影響到所提模型性能，其結(jié)果報(bào)告在圖5中.可觀察到當(dāng)K=10時(shí)，AUC和AUPR值最小，表明潛在空間無法保持更多網(wǎng)絡(luò)結(jié)構(gòu)信息.隨著K逐漸增大，AUC和AUPR值增大，直到K=70時(shí)開始保持穩(wěn)定.因此，當(dāng)K=70時(shí)，AUC和AUPR值最優(yōu).

圖5 不同參數(shù)K在6個(gè)網(wǎng)絡(luò)上對(duì)應(yīng)不同AUC和AUPR值Fig.5 Different parameters K correspond to different AUC and AUPR values on six networks

3.4 迭代次數(shù)變化

迭代次數(shù)直接反映收斂速度，其結(jié)果報(bào)告在圖6中.當(dāng)?shù)螖?shù)達(dá)到40次時(shí)，AUC和AUPR值開始保持穩(wěn)定，表明所提算法在較短時(shí)間內(nèi)獲得收斂.因此，迭代次數(shù)為40次時(shí)，DRNMF性能最優(yōu)且快速收斂.

圖6 不同迭代次數(shù)在6個(gè)網(wǎng)絡(luò)上對(duì)應(yīng)不同AUC和AUPR值Fig.6 Different numbers of iterations correspond to different AUC and AUPR values on six networks

4 結(jié)語

如何融合網(wǎng)絡(luò)結(jié)構(gòu)信息去提高鏈路預(yù)測的準(zhǔn)確度是當(dāng)前研究的熱點(diǎn)之一.因此，提出對(duì)偶圖正則化非負(fù)矩陣分解鏈路預(yù)測模型，該模型通過杰卡爾德相似度捕獲網(wǎng)絡(luò)局部結(jié)構(gòu)信息，利用隨機(jī)游走方法捕獲網(wǎng)絡(luò)全局結(jié)構(gòu)信息，再使用對(duì)偶圖正則化技術(shù)融合局部和全局結(jié)構(gòu)，與非負(fù)矩陣分解共同組成統(tǒng)一鏈路預(yù)測目標(biāo)函數(shù).在6個(gè)真實(shí)世界網(wǎng)絡(luò)上利用AUC和AUPR度量與現(xiàn)存具有代表性算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明所提模型性能獲得顯著改善.