深度非負(fù)矩陣分解的鏈路預(yù)測(cè)方法研究

蔡 菲，張 鑫，牟曉慧，陳 杰，蔡 珣

1.山東建筑大學(xué) 測(cè)繪地理信息學(xué)院，濟(jì)南 250101

2.山東大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，濟(jì)南 250101

1 引言

鏈路預(yù)測(cè)是近年來復(fù)雜網(wǎng)絡(luò)中的研究熱點(diǎn)之一，它能夠幫助探索和理解復(fù)雜網(wǎng)絡(luò)的演化機(jī)制。目前，復(fù)雜網(wǎng)絡(luò)中，現(xiàn)有鏈路預(yù)測(cè)方法可分為兩大類。第一類基于節(jié)點(diǎn)相似性的方法，認(rèn)為兩個(gè)節(jié)點(diǎn)之間相似性越大，它們之間存在鏈接的可能性就越大[1-3]。這類方法均依賴于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，雖比傳統(tǒng)鏈路預(yù)測(cè)方法提高了預(yù)測(cè)精度，但在稀疏網(wǎng)絡(luò)中預(yù)測(cè)能力仍然有限。第二類方法是基于統(tǒng)計(jì)分析和概率論，如概率關(guān)系模型[4]、層次結(jié)構(gòu)模型[5]和隨機(jī)塊模型[6]。這些方法通常假設(shè)網(wǎng)絡(luò)有一個(gè)已知的結(jié)構(gòu)，通過構(gòu)建模型并使用統(tǒng)計(jì)方法估計(jì)模型參數(shù)，進(jìn)而計(jì)算每個(gè)沒有觀測(cè)到的節(jié)點(diǎn)之間連邊的形成概率?；诟怕屎徒y(tǒng)計(jì)的方法在網(wǎng)絡(luò)分析中有許多優(yōu)點(diǎn)，但是參數(shù)學(xué)習(xí)和推理卻使計(jì)算復(fù)雜性大大增加，使得基于概率和統(tǒng)計(jì)的方法在應(yīng)用領(lǐng)域受到很大局限。

目前的鏈路預(yù)測(cè)研究也越來越關(guān)注從網(wǎng)絡(luò)節(jié)點(diǎn)的隱特征信息出發(fā)構(gòu)建鏈路預(yù)測(cè)方法。非負(fù)矩陣分解方法能夠提取隱特征，其本身也是一種降維方法，因此，非負(fù)矩陣分解也成為了隱特征模型的實(shí)現(xiàn)基礎(chǔ)[7-8]，例如文獻(xiàn)[9]提出了一種帶有圖正則非負(fù)矩陣分解的鏈路預(yù)測(cè)方法。文獻(xiàn)[10]提出了將圖通信性和非負(fù)矩陣分解相結(jié)合進(jìn)行時(shí)序網(wǎng)絡(luò)鏈路預(yù)測(cè)并取得了良好的預(yù)測(cè)效果。但現(xiàn)有的非負(fù)矩陣分解方法在稀疏網(wǎng)絡(luò)中鏈路預(yù)測(cè)能力仍然有限。

在矩陣分解中，系數(shù)矩陣和原始數(shù)據(jù)矩陣之間的映射包含了相當(dāng)?shù)姆蔷€性結(jié)構(gòu)信息[11]。因此，本文針對(duì)非負(fù)矩陣分解直接將原始網(wǎng)絡(luò)映射到隱空間中，不能充分挖掘復(fù)雜網(wǎng)絡(luò)的深層隱結(jié)構(gòu)信息，導(dǎo)致在稀疏網(wǎng)絡(luò)中預(yù)測(cè)能力有限，提出一種新穎的融合網(wǎng)絡(luò)多層結(jié)構(gòu)信息的深度非負(fù)矩陣分解預(yù)測(cè)方法（Deep NMF，DNMF）。首先通過對(duì)系數(shù)矩陣多次分解，得到一組基矩陣和一個(gè)系數(shù)矩陣相乘，進(jìn)而構(gòu)建深度隱特征模型的目標(biāo)函數(shù)。然后，采用兩階段法去調(diào)整訓(xùn)練參數(shù)，即在預(yù)訓(xùn)練階段通過逐層分解作為預(yù)分解結(jié)果，在微調(diào)階段整體微調(diào)訓(xùn)練參數(shù)，從而實(shí)現(xiàn)逐層學(xué)習(xí)策略。逐層學(xué)習(xí)策略可以使深度非負(fù)矩陣分解不同層級(jí)間的參數(shù)進(jìn)行“剖分”式學(xué)習(xí)，可以大大節(jié)省計(jì)算存儲(chǔ)資源和時(shí)間，提高方法的泛化性能。因此，該方法可以在保證真實(shí)網(wǎng)絡(luò)的深層隱結(jié)構(gòu)信息表達(dá)的同時(shí)使其獲得更加豐富和全面的網(wǎng)絡(luò)結(jié)構(gòu)信息，從而進(jìn)一步提高鏈路預(yù)測(cè)的預(yù)測(cè)精度。

2 問題描述

網(wǎng)絡(luò)由節(jié)點(diǎn)和邊組成，給定一個(gè)無向無權(quán)網(wǎng)絡(luò)G=(V,E)，V和E分別表示網(wǎng)絡(luò)中的節(jié)點(diǎn)和邊的集合。N=|V|和M=|E|分別代表網(wǎng)絡(luò)的節(jié)點(diǎn)和邊的數(shù)量。A代表網(wǎng)絡(luò)的鄰接矩陣，如果節(jié)點(diǎn)i和節(jié)點(diǎn)j之間有連邊，則Aij=Aji=1，如果節(jié)點(diǎn)i和節(jié)點(diǎn)j之間沒有連邊，則Aij=Aji=0。

針對(duì)鏈路預(yù)測(cè)問題，將網(wǎng)絡(luò)的邊劃分為訓(xùn)練集和測(cè)試集，表示為Etrain和Etest。顯然Etrain?Etest=E并且Etrain?Etest=。使用Atrain和 Atest分別表示訓(xùn)練集的鄰接矩陣和測(cè)試集的鄰接矩陣。鄰接矩陣中元素值為1或0，并且 Atrain+Atest=A。L=|Etest|是測(cè)試集中的邊數(shù)。因此，訓(xùn)練集邊的數(shù)量為|Etrain|=M-L。在訓(xùn)練集之外，將網(wǎng)絡(luò)中的所有可能邊作為候選集。從訓(xùn)練集Etrain中學(xué)習(xí)模型，然后計(jì)算候選集中節(jié)點(diǎn)間每個(gè)可能邊的分?jǐn)?shù)值，將分?jǐn)?shù)值從大到小排列，并根據(jù)不同評(píng)價(jià)指標(biāo)對(duì)測(cè)試集Etest的結(jié)果進(jìn)行驗(yàn)證。

3 基于深度非負(fù)矩陣分解的鏈路預(yù)測(cè)

3.1 非負(fù)矩陣分解

非負(fù)矩陣分解（NMF）是一種矩陣分解算法，它是一種使數(shù)據(jù)的隱結(jié)構(gòu)更加顯式化和減小其維數(shù)的方法。因此，它可以進(jìn)一步應(yīng)用于鏈路預(yù)測(cè)[12]。給定一個(gè)網(wǎng)絡(luò)鄰接矩陣A∈RN×N，可近似為W∈RN×K和H∈RK×N。

為了量化近似的質(zhì)量，用歐氏距離平方的代價(jià)函數(shù)可以寫成如下：

其中，W和H分別表示基矩陣和系數(shù)矩陣。根據(jù)文獻(xiàn)[13]提出的迭代更新算法，該算法最小化目標(biāo)函數(shù)如下：

3.2 深度非負(fù)矩陣分解

在非負(fù)矩陣分解的基礎(chǔ)上，本文提出了一種深度非負(fù)矩陣分解的算法（Deep Non-negative Matrix Factorization，DNMF）。

通過對(duì)NMF分解的系數(shù)矩陣H進(jìn)行m次分解，從而進(jìn)一步融合了網(wǎng)絡(luò)的多層結(jié)構(gòu)信息，其分解示意圖如圖1所示。

圖1 NMF與深度NMF的對(duì)比示意圖

DNMF通過對(duì)系數(shù)矩陣的多重分解形成多層網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)模型H的分解步驟如下：

步驟1分解網(wǎng)絡(luò)鄰接矩陣A≈W1H1，W1∈RN×k1和 H1∈Rk1×N的最小整數(shù)；R表示實(shí)數(shù)域。

步驟2步驟1后，系數(shù)矩陣H1可以分解H1≈W2H2，其中W2∈Rk1×k2和H1∈Rk2×N

步驟3以此類推，m次分解后，網(wǎng)絡(luò)鄰接矩陣A≈W1W2W3…WmHm，并且W1,W2,…,Wm,Hm非負(fù)，

在系數(shù)矩陣H上進(jìn)行m次分解后，矩陣A可以用m+1個(gè)因子表示，包括m個(gè)基矩陣和一個(gè)系數(shù)矩陣。每一次添加的基矩陣等價(jià)于添加一個(gè)額外的抽象層，去自動(dòng)學(xué)習(xí)網(wǎng)絡(luò)層次結(jié)構(gòu)信息，進(jìn)而更準(zhǔn)確、更全面地探索隱特征。深度非負(fù)矩陣分解的損失函數(shù)可以表示為：

在公式（5）中，讓 Λl=[λik]l和 M=[ujk]分別作拉格朗的拉格朗乘數(shù)（W≥0，H≥0），其中l(wèi)=1,2,…,m,λik≥0,ujk≥0 。

拉格朗日函數(shù)可以表示為：

基于非負(fù)矩陣分解的優(yōu)化目標(biāo)函數(shù)是一個(gè)非凸優(yōu)化問題，及其預(yù)測(cè)結(jié)果依賴于基矩陣W和系數(shù)矩陣H的初始值。傳統(tǒng)的非負(fù)矩陣分解方法往往隨機(jī)初始化W和H，但很容易進(jìn)入局部最優(yōu)解，這也可能導(dǎo)致欠擬合現(xiàn)象。為了減少鏈路預(yù)測(cè)模型的訓(xùn)練時(shí)間，提高模型的泛化能力，因此采用了預(yù)訓(xùn)練和微調(diào)兩階段進(jìn)行鏈路預(yù)測(cè)。

（1）預(yù)訓(xùn)練的階段

步驟1分解網(wǎng)絡(luò)鄰接矩陣A≈W1H1，其中W1∈。

步驟2系數(shù)矩陣H1可以分解為H1≈W2H2，其中。

步驟3繼續(xù)上述步驟，直到所有的層都經(jīng)過了預(yù)訓(xùn)練，網(wǎng)絡(luò)鄰接矩陣A≈W1W2W3…WmHm，其中W1～Wm，H1～Hm是非負(fù)的。

（2）微調(diào)階段

對(duì)公式（6）的目標(biāo)函數(shù)求Wm和Hm的偏導(dǎo)數(shù)，其過程如下：

使用KTT條件0和ujkhjk=0，得到以下方程：

根據(jù)文獻(xiàn)[14]，可以對(duì)Wm和Hm進(jìn)行以下乘法更新規(guī)則：

其中，H?為第m層系數(shù)矩陣的重構(gòu)。

3.3 基于DNMF的鏈路預(yù)測(cè)算法

在輸入網(wǎng)絡(luò)數(shù)據(jù)時(shí)，本文提出的鏈路預(yù)測(cè)算法有三個(gè)步驟。首先通過預(yù)訓(xùn)練對(duì)系數(shù)矩陣多次分解，得到一組基矩陣和一個(gè)系數(shù)矩陣相乘，進(jìn)而構(gòu)建深度非負(fù)矩陣分解的目標(biāo)函數(shù)。在分解過程中，確定每層隱特征的數(shù)量。然后，通過逐層分解作為預(yù)分解結(jié)果，再整體微調(diào)訓(xùn)練參數(shù)，從而實(shí)現(xiàn)逐層學(xué)習(xí)策略。最后，根據(jù)微調(diào)訓(xùn)練后的基矩陣和系數(shù)矩陣重構(gòu)網(wǎng)絡(luò)，計(jì)算網(wǎng)絡(luò)相似矩陣，從而構(gòu)建出基于深度非負(fù)矩陣分解的鏈路預(yù)測(cè)方法。

算法1基于深度非負(fù)矩陣隱特征模型鏈路預(yù)測(cè)算法流程：

input：給定網(wǎng)絡(luò)鄰接矩陣A和訓(xùn)練集f的比例，層數(shù)m

output：網(wǎng)絡(luò)的相似矩陣A?

Procedure計(jì)算W,H

根據(jù)訓(xùn)練集比例f將A分為Atrain，Atest

forr=1：mdo

獲得每層隱特征的數(shù)量Kr

until損失函數(shù)值小于容差

計(jì)算給定網(wǎng)絡(luò)的相似矩陣A?

根據(jù)A?=W1W2…WmHm，計(jì)算相似度矩陣A*

end procedure

4 仿真實(shí)驗(yàn)

4.1 評(píng)價(jià)指標(biāo)

為了驗(yàn)證該方法的性能，采用三種評(píng)價(jià)指標(biāo)對(duì)所提出的方法和基本線方法的性能進(jìn)行了比較。三個(gè)評(píng)價(jià)指標(biāo)包括AUC，精度和預(yù)測(cè)能力（PP），定義如下：

（1）AUC[15]。AUC指標(biāo)（Area Under the receiver operating characteristic Curve，AUC）是從整體上衡量算法的準(zhǔn)確度。AUC可以理解為在測(cè)試集中隨機(jī)選擇一條邊的存在可能性估計(jì)值大于不存在邊集隨機(jī)選擇一條邊的存在可能性估計(jì)值的概率。AUC的具體計(jì)算方法如公式所示：

在這里，n表示獨(dú)立比較的次數(shù)，n′表示n′次測(cè)試集中隨機(jī)選擇一條邊的存在可能性估計(jì)值大于不存在邊集隨機(jī)選擇一條邊的存在可能性估計(jì)值，n″表示n″次測(cè)試集Etrain中隨機(jī)選擇一條邊的存在可能性估計(jì)值等于不存在邊集E隨機(jī)選擇一條邊的存在可能性估計(jì)值。

顯然，如果所有的存在可能性估計(jì)值都是隨機(jī)產(chǎn)生的，那么AUC≈0.5。所以，AUC>0.5顯示了在多大程度上方法比隨機(jī)選擇性能好。

（2）精度[16]。精確度Precision指標(biāo)定義為算法給出的最有可能存在的前L條預(yù)測(cè)邊中預(yù)測(cè)正確的比值，其定義如下：

在這里，L是預(yù)測(cè)可能邊的前L條邊的數(shù)量，一般L取為測(cè)試集的邊數(shù)。Lr是在前L條預(yù)測(cè)邊中預(yù)測(cè)正確的數(shù)量。因此，可以看出精度值Precision越高，其算法的預(yù)測(cè)準(zhǔn)確度越高。

（3）預(yù)測(cè)能力（PP）[17]。為了刻畫預(yù)測(cè)算法和隨機(jī)預(yù)測(cè)之間的差別，文獻(xiàn)[17]提出了預(yù)測(cè)能力評(píng)價(jià)指標(biāo)，其也被用于評(píng)價(jià)鏈路預(yù)測(cè)方法的整體預(yù)測(cè)效果。Prediction-Power指標(biāo)值越大，說明其預(yù)測(cè)效果越好。預(yù)測(cè)能力Prediction?Power（PP）被定義為：

在這里，PrecisionRandom是隨機(jī)預(yù)測(cè)的精度值，也就是隨機(jī)對(duì)預(yù)測(cè)邊進(jìn)行排列，其前L條邊預(yù)測(cè)準(zhǔn)確的比例，其平均隨機(jī)預(yù)測(cè)的精度值約等于其中N為網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量，M為網(wǎng)絡(luò)中邊的數(shù)量。

4.2 常用算法的相似性指標(biāo)

為了驗(yàn)證本文提出的算法的性能，9個(gè)典型的相似性指標(biāo)用于性能比較，包括Katz[18]、ACT[19]、CN[20]、AA[21]、CRA[17，22]、RA[23]、LP[23]、PA[24]和 Jaccard[25]。這些相似性指標(biāo)的詳細(xì)描述如表1所示。

4.3 實(shí)驗(yàn)數(shù)據(jù)

為了驗(yàn)證本文提出的方法的性能，考慮以下10個(gè)真實(shí)世界的網(wǎng)絡(luò)：爵士音樂家合作網(wǎng)絡(luò)（Jazz）[26]、網(wǎng)絡(luò)理論科學(xué)家合作網(wǎng)絡(luò)（NS）[27]、美國政治博客網(wǎng)絡(luò)（PB）[28]、電力網(wǎng)絡(luò)（Power）[29]、路由器網(wǎng)絡(luò)（Router）[30]、論文引用網(wǎng)絡(luò)（SmaGri）[31]、蛋白質(zhì)相互作用網(wǎng)絡(luò)（Yeast）[32]、俱樂部網(wǎng)絡(luò)（Karate）[33]、高校社交網(wǎng)絡(luò)（School）[34]。表2提供了以上10個(gè)真實(shí)網(wǎng)絡(luò)的拓?fù)涮卣鳌?/p>

表2中|V|和|E|分別表示節(jié)點(diǎn)總數(shù)和邊的總數(shù)；LD表示邊密度，其定義為網(wǎng)絡(luò)中實(shí)際存在的邊數(shù)與網(wǎng)絡(luò)中最大可能的邊數(shù)之比；表示網(wǎng)絡(luò)節(jié)點(diǎn)的平均度（average degree），即所有節(jié)點(diǎn)的度的平均值；表示網(wǎng)絡(luò)的平均最短距離（average shortest distance）；C表示網(wǎng)絡(luò)的所有節(jié)點(diǎn)的接近中心性的平均值；CC表示網(wǎng)絡(luò)的聚類系數(shù)，其等于所有節(jié)點(diǎn)簇系數(shù)的平均值；r表示網(wǎng)絡(luò)度-度Pearson相關(guān)系數(shù)，也稱為網(wǎng)絡(luò)的同配系數(shù)；LCP-corr是LCP-correlation的縮寫，其表示局部社區(qū)范例（Local Community Paradigm，LCP）和CN指標(biāo)的相關(guān)系數(shù)[17]；H表示網(wǎng)絡(luò)的度的異質(zhì)性[23]。

表1 9個(gè)典型相似性指標(biāo)

表2 10個(gè)真實(shí)網(wǎng)絡(luò)的拓?fù)涮卣?/p>

表3 不同方法在10個(gè)真實(shí)網(wǎng)絡(luò)上的AUC值

4.4 實(shí)驗(yàn)結(jié)果

為了測(cè)試DNMF方法的性能，將該方法在10個(gè)真實(shí)網(wǎng)絡(luò)中與10個(gè)經(jīng)典方法進(jìn)行了比較。首先，觀察到的邊被隨機(jī)分為訓(xùn)練集和測(cè)試集。這里，訓(xùn)練集被用于構(gòu)建預(yù)測(cè)模型，而測(cè)試集僅用于驗(yàn)證在復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)的準(zhǔn)確性。

將方法（DNMF）與其他10個(gè)網(wǎng)絡(luò)數(shù)據(jù)集的方法的AUC、Precision、PP進(jìn)行了比較，AUC值、Precision值、PP值分別是運(yùn)行100次的平均值。在實(shí)驗(yàn)中，LP方法的參數(shù)α為0.000 1，Katz方法的參數(shù)α為0.01，DNMF參數(shù)m為2。表3、表4、表5中分別給出了不同方法在10個(gè)真實(shí)網(wǎng)絡(luò)上的AUC值、Precision值和PP值，每一列的最高值用黑色粗體表示，其訓(xùn)練集比例均為90%。

如表3所示，DNMF優(yōu)于傳統(tǒng)的NMF。此外，DNMF在3個(gè)真實(shí)的網(wǎng)絡(luò)中擁有最高的AUC值，包括PB、SmaGri和Yeast。在 Jazz、NS、USAir和Karate這幾個(gè)網(wǎng)絡(luò)中，提出的方法DNMF的AUC值也非常接近于最高值。

如表4所示，DNMF比傳統(tǒng)的NMF更具有更好的Precision值。DNMF在Jazz、PB、Power、Router、SmaGri、USAir和Yeast這幾個(gè)網(wǎng)絡(luò)中擁有最好的Precision值，在Karate和School網(wǎng)絡(luò)中僅次于CRA方法的精度值?？傮w來說，它表明，DNMF優(yōu)于傳統(tǒng)的非負(fù)矩陣分解和其他經(jīng)典方法，特別是在稀疏網(wǎng)絡(luò)上，如Router、PB、Yeast等。

如表5所示，在所有網(wǎng)絡(luò)中，每個(gè)方法的PP的平均值（mean值）在最后一列顯示，其也被用于反映方法的整體性能。不同的方法按平均PP值大小倒序排列，由PP的mean值可以看出DNMF的整體性能在11種方法中表現(xiàn)最好。

為了準(zhǔn)確測(cè)試DNMF方法的性能，分別比較了在6個(gè)網(wǎng)絡(luò)中不同的訓(xùn)練集下的11種方法的AUC值、Precision值、PP值，訓(xùn)練集的比例f從0.3變換到0.9，其結(jié)果分別顯示在圖2、圖3和圖4中。在圖2、圖3、圖4中這6個(gè)網(wǎng)絡(luò)分別是Yeast、Jazz、PB、SmaGri、USAir和School。

表4 不同方法在10個(gè)真實(shí)網(wǎng)絡(luò)上的Precision值

表5 不同方法在10個(gè)真實(shí)網(wǎng)絡(luò)上的PP值

從結(jié)果可以看出，DNMF方法在大多數(shù)網(wǎng)絡(luò)上比其他方法具有競(jìng)爭(zhēng)力的性能。綜上所述，對(duì)于大多數(shù)網(wǎng)絡(luò)來說，所提出的方法DNMF比其他10種典型的預(yù)測(cè)方法具有更高的預(yù)測(cè)精度和魯棒性。

4.5 參數(shù)分析

為了分析參數(shù)層數(shù)m對(duì)算法DNMF的影響，選取已被廣泛使用的Precision精度作為評(píng)價(jià)指標(biāo)，并分別測(cè)試了在6個(gè)網(wǎng)絡(luò)中不同訓(xùn)練集比例下m分別取為1、2、3、4時(shí)的DNMF的精度，其結(jié)果如圖5所示。這6個(gè)網(wǎng)絡(luò)分別是Yeast、Jazz、PB、SmaGri、USAir和School。

從圖5可以看出，在大多數(shù)情況下，當(dāng)m等于2時(shí)，DNMF的精度會(huì)比m為1、3、4時(shí)的DNMF的精度更高。因此，在通常情況下的實(shí)驗(yàn)中設(shè)置m=2。

5 結(jié)論

真實(shí)網(wǎng)絡(luò)往往是稀疏的，傳統(tǒng)的單層非負(fù)矩陣分解不能完全描述復(fù)雜網(wǎng)絡(luò)的深層結(jié)構(gòu)，為了解決此問題，本文基于非負(fù)矩陣分解和網(wǎng)絡(luò)的隱特征提出了一個(gè)新穎的基于深度非負(fù)矩陣分解的鏈路預(yù)測(cè)方法。作為非負(fù)矩陣分解隱特征模型的擴(kuò)展，提出的鏈路預(yù)測(cè)方法DNMF不僅繼承了其優(yōu)點(diǎn)，也充分利用了多層分解獲取網(wǎng)絡(luò)多組織結(jié)構(gòu)信息。為了驗(yàn)證該方法的性能，本文選取了三個(gè)評(píng)價(jià)指標(biāo)，分別為AUC、Precision和預(yù)測(cè)能力（PP）。對(duì)10個(gè)真實(shí)網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果表明，該模型方法比經(jīng)典方法具有更高的精度。當(dāng)然，本文所提出的方法也有一些局限性和改進(jìn)研究，如何設(shè)置參數(shù)m在不同網(wǎng)絡(luò)上進(jìn)行自適應(yīng)，以及如何優(yōu)化算法時(shí)間復(fù)雜度，將是下一步的工作。

圖2 不同訓(xùn)練集下各方法AUC值對(duì)比

圖3 不同訓(xùn)練集下各方法Precision值對(duì)比

圖4 不同訓(xùn)練集比例下各方法PP值對(duì)比

圖5 DNMF在不同層數(shù)參數(shù)m下的精度值對(duì)比