宋光鑫，王麗平

南京航空航天大學(xué) 理學(xué)院，南京 211106

1 引言

在計(jì)算機(jī)科學(xué)中，網(wǎng)絡(luò)通常是指一幅節(jié)點(diǎn)或連邊具有語(yǔ)義的圖，它可以挖掘社交網(wǎng)絡(luò)上的人際關(guān)系[1]，電商網(wǎng)站中用戶對(duì)商品的偏好或生物化學(xué)領(lǐng)域蛋白質(zhì)之間的相互作用。對(duì)這樣的數(shù)據(jù)結(jié)構(gòu)進(jìn)行數(shù)據(jù)挖掘時(shí)，傳統(tǒng)的數(shù)據(jù)挖掘算法通常只考慮網(wǎng)絡(luò)的節(jié)點(diǎn)屬性，并將數(shù)據(jù)中的每個(gè)節(jié)點(diǎn)視為從某個(gè)分布中采樣得到的獨(dú)立同分布個(gè)體。這樣簡(jiǎn)單的假設(shè)通常會(huì)對(duì)算法結(jié)果造成誤導(dǎo)，因此研究節(jié)點(diǎn)之間的連邊模式變得尤為必要。

在大多數(shù)情況下，被觀測(cè)到的網(wǎng)絡(luò)結(jié)構(gòu)信息是不完整的，預(yù)測(cè)網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間是否存在連邊將是一個(gè)令人感興趣的問(wèn)題。另一方面，某些網(wǎng)絡(luò)中的連邊隨著時(shí)間表現(xiàn)出動(dòng)態(tài)的特性，這樣的網(wǎng)絡(luò)中人們可能會(huì)關(guān)心某條連邊在未來(lái)是否會(huì)出現(xiàn)。由已觀測(cè)到的網(wǎng)絡(luò)結(jié)構(gòu)推測(cè)未觀測(cè)到的網(wǎng)絡(luò)結(jié)構(gòu)通常被稱(chēng)為靜態(tài)鏈接預(yù)測(cè)，而由過(guò)去時(shí)刻的網(wǎng)絡(luò)結(jié)構(gòu)推測(cè)未來(lái)時(shí)刻的網(wǎng)絡(luò)結(jié)構(gòu)被稱(chēng)為動(dòng)態(tài)鏈接預(yù)測(cè)。目前針對(duì)靜態(tài)鏈接預(yù)測(cè)提出的預(yù)測(cè)算法主要包括基于節(jié)點(diǎn)相似度[2]、基于最大似然估計(jì)[3]和基于概率模型[4]的三大類(lèi)別。其中最常見(jiàn)的是基于相似度的算法，例如Preferential Attachment Index（PA）、Common Neighbours（CN）、Adamic-Adar（AA）、Katz 等算法[5-6]，這些算法在靜態(tài)鏈接預(yù)測(cè)中顯示出了強(qiáng)大的效果，常被用于基準(zhǔn)算法。對(duì)于靜態(tài)鏈接預(yù)測(cè)的研究還在持續(xù)，如伍杰華[7]引入樹(shù)狀數(shù)據(jù)結(jié)構(gòu)來(lái)計(jì)算合著者網(wǎng)絡(luò)結(jié)構(gòu)，并聯(lián)合樸素貝葉斯算法和節(jié)點(diǎn)相似度實(shí)現(xiàn)鏈接預(yù)測(cè)；張昱等人[8]提出了一種融合網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)屬性的鏈接預(yù)測(cè)方法；程華等人[9]關(guān)注節(jié)點(diǎn)的鄰域相似性和依賴(lài)關(guān)系，提出了基于Attention機(jī)制的靜態(tài)鏈接預(yù)測(cè)算法；Pech 等人[10]建立了基于魯棒PCA（principal component analysis）的矩陣補(bǔ)全模型并應(yīng)用于靜態(tài)鏈接預(yù)測(cè)；Mohtashemi 等人[11]提出了對(duì)數(shù)正態(tài)矩陣補(bǔ)全模型來(lái)求解鏈接預(yù)測(cè)問(wèn)題。相較之下，動(dòng)態(tài)鏈接預(yù)測(cè)加入了時(shí)間維度，考慮網(wǎng)絡(luò)結(jié)構(gòu)隨著時(shí)間的演變，它的預(yù)測(cè)難度更大。早期的動(dòng)態(tài)鏈接預(yù)測(cè)方法主要是將靜態(tài)問(wèn)題的算法進(jìn)行一定的推廣。近年來(lái)，隨著人工智能的興起，許多機(jī)器學(xué)習(xí)的方法被應(yīng)用于動(dòng)態(tài)網(wǎng)絡(luò)鏈接預(yù)測(cè)[12-14]。安琛等人[15]將主動(dòng)學(xué)習(xí)應(yīng)用于動(dòng)態(tài)網(wǎng)絡(luò)鏈接預(yù)測(cè)，充分利用了網(wǎng)絡(luò)中未鏈接節(jié)點(diǎn)的信息。Chen 等人[16]提出監(jiān)督學(xué)習(xí)對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)的結(jié)構(gòu)進(jìn)行建模以預(yù)測(cè)未來(lái)時(shí)刻可能出現(xiàn)的鏈接。陳陽(yáng)等人[17]將集成學(xué)習(xí)引入動(dòng)態(tài)鏈接，把鏈接預(yù)測(cè)看作一個(gè)分類(lèi)問(wèn)題，通過(guò)訓(xùn)練多個(gè)分類(lèi)器來(lái)提高類(lèi)別預(yù)測(cè)效果，使得網(wǎng)絡(luò)演變的動(dòng)態(tài)信息得到充分的利用。Xu等人[18]利用監(jiān)督學(xué)習(xí)和特征工程的方法關(guān)注動(dòng)態(tài)圖變化的特征信息，有效提高了預(yù)測(cè)準(zhǔn)確度。Li 等人[19]利用深度學(xué)習(xí)的方法以及梯度提升樹(shù)模型挖掘動(dòng)態(tài)鏈接中隱藏的模式關(guān)系。目前，絕大多數(shù)動(dòng)態(tài)鏈接預(yù)測(cè)論文中提出的動(dòng)態(tài)鏈接預(yù)測(cè)方法主要關(guān)注網(wǎng)絡(luò)圖隨時(shí)間演化的特征信息和節(jié)點(diǎn)相似性，很少考慮網(wǎng)絡(luò)結(jié)構(gòu)的稀疏性和在原始空間中難以學(xué)習(xí)到的非線性鏈接關(guān)系。近年來(lái)，稀疏學(xué)習(xí)和壓縮感知得到了深入的研究和應(yīng)用，Liu等人將其應(yīng)用到協(xié)同過(guò)濾當(dāng)中，并加入核方法來(lái)獲得在原始空間中不能夠?qū)W習(xí)到的非線性關(guān)系[20]。受此啟發(fā)，本文將矩陣補(bǔ)全方法應(yīng)用于動(dòng)態(tài)鏈接預(yù)測(cè)，并借鑒Liu等人為協(xié)同過(guò)濾構(gòu)造核矩陣分解模型的方法，為動(dòng)態(tài)鏈接預(yù)測(cè)構(gòu)造了核矩陣補(bǔ)全模型，通過(guò)將原始數(shù)據(jù)映射到高維Hilbert空間，再應(yīng)用矩陣補(bǔ)全模型來(lái)學(xué)習(xí)到更多的鏈接信息，提高模型的預(yù)測(cè)效果。

2 鏈接預(yù)測(cè)問(wèn)題

2.1 靜態(tài)鏈接預(yù)測(cè)

靜態(tài)鏈接預(yù)測(cè)問(wèn)題是在已知網(wǎng)絡(luò)的節(jié)點(diǎn)和連邊的條件下預(yù)測(cè)未觀測(cè)到的連邊。設(shè)已觀測(cè)網(wǎng)絡(luò)G=(V,E)，其中V代表所有節(jié)點(diǎn)的集合，E代表已觀測(cè)到的連邊的集合，用N和M分別代表網(wǎng)絡(luò)中節(jié)點(diǎn)和連邊的數(shù)目。網(wǎng)絡(luò)的鄰接矩陣用A∈{0,1}N×N表示，Aij=1代表節(jié)點(diǎn)對(duì)(i,j)上存在一條連邊（從i指向j），即(i,j)∈E。記所有的節(jié)點(diǎn)對(duì)構(gòu)成的集合為U=V×V，鏈接預(yù)測(cè)問(wèn)題就是要對(duì)一開(kāi)始未觀測(cè)到連邊的節(jié)點(diǎn)對(duì)(i,j)∈UE，給出其實(shí)際存在鏈接的可能性。靜態(tài)鏈接預(yù)測(cè)的算法為每一個(gè)節(jié)點(diǎn)對(duì)(i,j)∈UE給出一個(gè)存在鏈接的得分值score(i,j)，然后對(duì)每一個(gè)得分值進(jìn)行排序，得分越高的節(jié)點(diǎn)處越有可能存在鏈接。常用的靜態(tài)鏈接預(yù)測(cè)算法大多根據(jù)節(jié)點(diǎn)之間的相似度來(lái)排序得到最可能存在鏈接的節(jié)點(diǎn)對(duì)，具有代表性的算法如引言中所述，有CN、AA、PA 等。其中，CN 算法統(tǒng)計(jì)網(wǎng)絡(luò)圖中每個(gè)節(jié)點(diǎn)的鄰接節(jié)點(diǎn)，并計(jì)算每對(duì)節(jié)點(diǎn)的公共鄰接節(jié)點(diǎn)的數(shù)量作為它們可能產(chǎn)生鏈接的分?jǐn)?shù)。AA 算法則在CN算法的基礎(chǔ)上添加了節(jié)點(diǎn)權(quán)重系數(shù)。PA算法認(rèn)為節(jié)點(diǎn)x產(chǎn)生新的節(jié)點(diǎn)的概率與它的鄰接節(jié)點(diǎn)數(shù)量| |Γ(x) 成正比，那么節(jié)點(diǎn)x與節(jié)點(diǎn)y存在鏈接的概率則正比于。

2.2 動(dòng)態(tài)鏈接預(yù)測(cè)

對(duì)于動(dòng)態(tài)鏈接預(yù)測(cè)問(wèn)題，已觀測(cè)數(shù)據(jù)通常是網(wǎng)絡(luò)在一段時(shí)間T內(nèi)的演變序列{G1,G2,…,GT}。其中Gt=(V,Et)是網(wǎng)絡(luò)在t時(shí)刻的鏈接狀態(tài)，V是前T個(gè)時(shí)間序列中出現(xiàn)過(guò)的節(jié)點(diǎn)集合，Et則是t時(shí)刻網(wǎng)絡(luò)中連邊的集合。網(wǎng)絡(luò)序列的鄰接矩陣A∈{0,1}N×N×T是單幅網(wǎng)絡(luò)鄰接矩陣在第三個(gè)維度上疊加得到的。即Aijt=1表示節(jié)點(diǎn)對(duì)(i,j)在t時(shí)刻具有鏈接。動(dòng)態(tài)鏈接預(yù)測(cè)問(wèn)題需要根據(jù)前T個(gè)時(shí)刻的網(wǎng)絡(luò)序列Gt(t=1,2,…,T)的鄰接矩陣At來(lái)預(yù)測(cè)T+1 時(shí)刻的鄰接矩陣At+1，從而得到Gt+1。許多如CN、PA、AA等基于鄰域的算法可以簡(jiǎn)單地推廣到動(dòng)態(tài)鏈接預(yù)測(cè)問(wèn)題上。推廣方法為視AT為一個(gè)靜態(tài)鄰接矩陣而直接對(duì)AT應(yīng)用相應(yīng)的算法，更常用的方法是定義網(wǎng)絡(luò)Gtotal的鄰接矩陣Atotal，Atotal在任意時(shí)刻出現(xiàn)過(guò)的連邊均視為在Atotal上存在，再對(duì)Atotal應(yīng)用靜態(tài)鏈接預(yù)測(cè)算法得到At+1。這種直接將靜態(tài)鏈接算法推廣到動(dòng)態(tài)中的方法雖然簡(jiǎn)單，但實(shí)驗(yàn)表明，往往具有很好的效果[1]。此外，Chakrabarti等人建立了一種根據(jù)鄰域相似性的非參數(shù)估計(jì)模型[21]來(lái)求解動(dòng)態(tài)鏈接預(yù)測(cè)。該方法對(duì)某個(gè)節(jié)點(diǎn)和其他節(jié)點(diǎn)產(chǎn)生連邊的概率展開(kāi)研究，并認(rèn)為具有相似鄰域的節(jié)點(diǎn)產(chǎn)生連邊的概率相等，通過(guò)同時(shí)利用時(shí)間和空間上的拓?fù)浣Y(jié)構(gòu)對(duì)鏈接出現(xiàn)的可能性進(jìn)行預(yù)測(cè)。出于相同的目的，Hisano提出了半監(jiān)督圖嵌入的方法[14]，通過(guò)定義在時(shí)間序列上的監(jiān)督損失和網(wǎng)絡(luò)狀態(tài)上的無(wú)監(jiān)督損失，來(lái)獲得時(shí)間和空間上的信息，以達(dá)到動(dòng)態(tài)鏈接預(yù)測(cè)的目的。

3 矩陣補(bǔ)全與核化矩陣補(bǔ)全

3.1 標(biāo)準(zhǔn)矩陣補(bǔ)全算法

2.2節(jié)所述的動(dòng)態(tài)鏈接預(yù)測(cè)算法雖然考慮了時(shí)間維度的變化信息，但卻忽略了鄰接矩陣的結(jié)構(gòu)特征。一般地，真實(shí)世界中的一幅大規(guī)模的網(wǎng)絡(luò)鄰接矩陣，在某個(gè)時(shí)間段內(nèi)節(jié)點(diǎn)與節(jié)點(diǎn)之間的互動(dòng)是非常有限的，而節(jié)點(diǎn)與節(jié)點(diǎn)之間產(chǎn)生鏈接又具有較強(qiáng)的相關(guān)性，因此網(wǎng)絡(luò)圖的鄰接矩陣具有低秩性和稀疏性。矩陣補(bǔ)全是指，對(duì)一個(gè)大小為n1×n2的矩陣，在采樣得到矩陣中m個(gè)元素的情況下，根據(jù)一定的假設(shè)條件和優(yōu)化方法來(lái)計(jì)算出其他未觀測(cè)到的元素的數(shù)值。近年來(lái)，有部分學(xué)者將矩陣補(bǔ)全應(yīng)用于靜態(tài)鏈接預(yù)測(cè)問(wèn)題，如Pech等人將魯棒PCA的矩陣補(bǔ)全求解方法用于靜態(tài)鏈接預(yù)測(cè)[10]，Gao 等人則提出交替迭代的矩陣補(bǔ)全模型求解靜態(tài)鏈接預(yù)測(cè)[22]。動(dòng)態(tài)鏈接預(yù)測(cè)是根據(jù)圖Gt預(yù)測(cè)圖Gt+1，一個(gè)自然的想法是把Gt和Gt+1疊加看作一張完整的圖G，而Gt作為已觀測(cè)到的網(wǎng)絡(luò)結(jié)構(gòu)，定義增加矩陣Ft+1=Mt+1-Mt,M表示網(wǎng)絡(luò)鏈接預(yù)測(cè)中的鄰接矩陣，那么Mt表示t時(shí)刻網(wǎng)絡(luò)的鄰接矩陣。在已知矩陣Mt時(shí)對(duì)Gt+1的預(yù)測(cè)就是對(duì)Ft+1的預(yù)測(cè)，即根據(jù)已觀測(cè)到的元素來(lái)預(yù)測(cè)G中隱藏的鏈接，這等價(jià)于靜態(tài)鏈接預(yù)測(cè)。靜態(tài)鏈接預(yù)測(cè)與動(dòng)態(tài)鏈接預(yù)測(cè)的這種相似關(guān)系啟發(fā)本文將矩陣補(bǔ)全應(yīng)用于動(dòng)態(tài)鏈接預(yù)測(cè)問(wèn)題。

定義某個(gè)網(wǎng)絡(luò)結(jié)構(gòu)在時(shí)刻t的鄰接矩陣為Mt，為了預(yù)測(cè)下一時(shí)刻的鄰接矩陣，建立動(dòng)態(tài)網(wǎng)絡(luò)鏈接預(yù)測(cè)的矩陣補(bǔ)全模型：

式中，PΩ(·)是采樣算子，將不在采樣集Ω中的矩陣元素置為0，其他元素不變。在鏈接預(yù)測(cè)問(wèn)題中，令采樣集為鄰接矩陣中已存在鏈接的位置集合，這里不考慮鏈接權(quán)重，則設(shè)Mij=1,(i,j)∈Ω,PΩ(Mt)視為在時(shí)刻t的鄰接矩陣，動(dòng)態(tài)鏈接預(yù)測(cè)問(wèn)題往往關(guān)注新產(chǎn)生的鏈接位置，那么不妨認(rèn)為從時(shí)刻t到時(shí)刻t+1 在觀測(cè)集內(nèi)的鏈接依然存在，并根據(jù)t時(shí)刻鏈接結(jié)構(gòu)推測(cè)t+1 時(shí)刻在觀測(cè)集Ω外哪些位置會(huì)發(fā)生鏈接。由（1）求出的矩陣X就是對(duì)采樣集外所有位置產(chǎn)生鏈接可能性的打分，數(shù)值越大代表越有可能產(chǎn)生鏈接。λ是需要手動(dòng)設(shè)置的參數(shù)，λ越大代表越重視矩陣的低秩約束[23]。

模型（1）是一個(gè)關(guān)于X的矩陣LASSO 問(wèn)題，目前求解無(wú)約束最優(yōu)化模型的優(yōu)化算法已非常豐富，本文使用加速近端梯度下降法[24]求解矩陣補(bǔ)全模型。另外，為了更多地利用以往時(shí)刻網(wǎng)絡(luò)的結(jié)構(gòu)信息，不妨將以往多個(gè)時(shí)間片段的鄰接矩陣進(jìn)行疊加來(lái)作為待補(bǔ)全矩陣，則（1）可以寫(xiě)為如下形式：

式中，T表示要使用的過(guò)去的歷史時(shí)刻數(shù)量，用T個(gè)鄰接矩陣來(lái)預(yù)測(cè)下一時(shí)刻的鄰接矩陣。這里將T個(gè)鄰接矩陣相加，因?yàn)楸疚牟豢紤]鏈接權(quán)重，所以將鏈接產(chǎn)生的位置數(shù)值設(shè)為1，使用符號(hào)函數(shù)sign(·)對(duì)做相應(yīng)處理。為了符號(hào)表述的整潔，將（2）改寫(xiě)為更一般的形式：

式中，A(·)：Rm×n→Rp是將所有在采樣集Ω中的矩陣元素按列展開(kāi)拉成一個(gè)列向量的算子，Ω={(i,j)|加速近端梯度下降算法的工作原理已得到充分的研究[24]，調(diào)用相應(yīng)的優(yōu)化算法包即可完成運(yùn)算。在此簡(jiǎn)單列出它的迭代公式：

將模型（3）代入框架（4）中，則框架中會(huì)出現(xiàn)如下子問(wèn)題：

子問(wèn)題（5）存在閉式解[25]，該解可以通過(guò)奇異值分解求得。若A的奇異值分解為A=UΣVT,Σ=diag(σi),則其閉式解為X=U[diag(σi-λ)+]VT，即將所有奇異值都減去λ，被減后小于0 的置為0。這相當(dāng)于給奇異值設(shè)定了一個(gè)閾值，所有小于這個(gè)閾值的奇異值被消減為0，這樣就使得矩陣中的非零奇異值數(shù)量減少，從而得到降低矩陣的秩的目的。以下給出了求解的完整步驟。由于使用加速近端梯度下降法求解網(wǎng)絡(luò)鏈接預(yù)測(cè)的矩陣補(bǔ)全模型，本文將該算法稱(chēng)為APG（Accelerated Proximal Gradient）算法。

算法1 APG 算法：用加速近端梯度下降算法求解矩陣LASSO問(wèn)題（3）

輸入：采樣算子A(·)、采樣集b、系數(shù)λ、步長(zhǎng)μ、最大迭代次數(shù)k_max。

輸出：Xopt。

初始化：X0=X-1=0m×n,t0=t-1=1,k=0,1,2,…,k_max

1.

2.Ak=Yk-μkA*(A(Yk)-b),其中A*是A的逆算子

3.A奇異值分解，得到U,diag(σ),V

4.Xk+1=U[diag(σi-μkλ)+]VT

5.

6.k=k+1,若滿足收斂條件則輸出Xk,否則回到步驟1。

由APG算法得到的X是對(duì)增加矩陣FT+1的預(yù)測(cè)，由MT+1=MT+FT+1，就得到了對(duì)下一時(shí)刻鄰接矩陣的預(yù)測(cè)。

3.2 核化矩陣補(bǔ)全

網(wǎng)絡(luò)鏈接預(yù)測(cè)關(guān)注節(jié)點(diǎn)之間的相似性，而真實(shí)世界的網(wǎng)絡(luò)鏈接具有稀疏性和相關(guān)性，由矩陣分解的知識(shí)可以將網(wǎng)絡(luò)的一個(gè)鄰接矩陣看作兩個(gè)低秩矩陣內(nèi)積的形式，即X≈UTV，這種分解需要保證在已觀測(cè)位置(i,j)∈Ω上信息相似，則（2）可轉(zhuǎn)化為如下形式：

式中，U,V∈Rk×n為分解得到的兩個(gè)低秩矩陣，M表示上一時(shí)刻的鄰接矩陣。則模型（6）表示用兩個(gè)低秩矩陣來(lái)補(bǔ)全矩陣M。傳統(tǒng)的矩陣分解方法通常假設(shè)相關(guān)鏈接數(shù)據(jù)分布在一個(gè)線性超平面上。然而，隨著真實(shí)世界中網(wǎng)絡(luò)結(jié)構(gòu)愈發(fā)復(fù)雜，許多網(wǎng)絡(luò)鄰接矩陣不滿足低秩性要求，很難通過(guò)線性矩陣分解的模型來(lái)預(yù)測(cè)未來(lái)的鏈接結(jié)構(gòu)。為了克服這一困難，本文將核方法引入矩陣補(bǔ)全模型中。核方法考慮把鏈接數(shù)據(jù)嵌入一個(gè)更高維的特征空間，在這個(gè)空間中鏈接數(shù)據(jù)可以分布在一個(gè)線性超平面上，這使得鄰接矩陣可以被表示為兩個(gè)特征矩陣內(nèi)積的形式。為了引入核方法，首先令φ(x)為將某個(gè)向量x映射到高維特征空間后對(duì)應(yīng)的特征向量，內(nèi)積＜x,y ＞相應(yīng)地變?yōu)椋鸡?x),φ(y)＞，進(jìn)一步引入核函數(shù)：

核方法將鏈接數(shù)據(jù)嵌入到高維特征空間H 中，這個(gè)嵌入映射是隱式的，但可以由核函數(shù)定義。假設(shè)某個(gè)核函數(shù)對(duì)應(yīng)的特征空間映射為φ:X→H，其中X 是原始空間，H 是Hilbert空間，則特征空間中的特征矩陣內(nèi)積可以通過(guò)核函數(shù)，利用原空間中的向量計(jì)算。引入核技巧后，使用Hilbert 空間中向量構(gòu)成的矩陣φ(U) 和φ(V)代替原特征空間中的U、V，將問(wèn)題（6）改寫(xiě)為：

矩陣U、V是需要求解的目標(biāo)，而非觀測(cè)到的數(shù)據(jù)，無(wú)法通過(guò)核函數(shù)直接求解φ(U)Tφ(V)。為此本文通過(guò)引入字典向量來(lái)代替直接求解U、V。因?yàn)樵跓o(wú)限維Hilbert 空間中，特征矩陣被映射到線性超平面中，鏈接數(shù)據(jù)之間的非線性關(guān)系被轉(zhuǎn)化為線性關(guān)系，根據(jù)泛函分析的知識(shí)可知，任何一個(gè)Hilbert空間都有一族標(biāo)準(zhǔn)正交基，則特征矩陣可以由一組基線性表示[26]。受字典學(xué)習(xí)相關(guān)理論的啟發(fā)[27]，本文使用φ(di)的線性組合來(lái)逼近矩陣φ(U)，通過(guò)建立形如的帶正則化項(xiàng)的字典學(xué)習(xí)模型來(lái)求得最優(yōu)的φ(di)，從而求得φ(U)Tφ(V)。具體地，給定k個(gè)d維字典向量d={d1,d2,…,dk}，di∈Rd，那么可以假設(shè)低秩矩陣U的每一列uj對(duì)應(yīng)的特征向量φ(uj)均可被字典向量d在特征空間中線性表示為如下形式：

其中，aij為每個(gè)字典向量的權(quán)重系數(shù)，φ(di)為字典向量d的第i個(gè)分量di在特征空間中對(duì)應(yīng)的特征向量，ai=(ai1,ai2,…,aik)T,Φ=(φ(d1),φ(d2),…,φ(dk)) 。同樣，將矩陣V的每一列vj表示為：

同樣，bij為每個(gè)特征向量的權(quán)重系數(shù)，bi=(bi1,bi2,…,bik)T。將權(quán)重向量a和b按行疊成矩陣A、B，記：

由于無(wú)法直接求解φ(U)Tφ(V) ，通過(guò)引入字典向量，將特征矩陣φ(U)、φ(V)轉(zhuǎn)化為字典矩陣Φ的表達(dá)式，這樣可以得到ΦTΦ，也就構(gòu)造出了核矩陣。

同時(shí)注意到：

根據(jù)式（9）～式（12），可以將模型（8）重寫(xiě)為：

其中，K=ΦTΦ是字典向量導(dǎo)出的核矩陣。為了求解模型（13），本文采用交替最小二乘法，其收斂性可以參考文獻(xiàn)[28]。算法的具體步驟是，首先固定U，即保持矩陣A不變，可以將（13）按列分解為n個(gè)子問(wèn)題：

其中，Ωj={i|(i,j)∈Ω}表示原矩陣M在第j列上觀測(cè)到的行i元素組成的集合。約定算子PΩj僅對(duì)行進(jìn)行操作，即PΩj(X)將保留X的所有i∈Ωj行整行，其余元素設(shè)為0。類(lèi)似的用Ωi={j|(i,j)∈Ω}表示在矩陣R第i行上觀測(cè)到的列j元素組成的集合，PΩi(X)將保留X的所有j∈Ωi行整行。m:,j、vj分別表示矩陣M、V的第j列。

問(wèn)題（14）是一個(gè)類(lèi)似嶺回歸的問(wèn)題，其閉式解為：

其中，A:,Ωj為保留矩陣A的i∈Ωj列得到的子矩陣，m:.Ωj表示由原矩陣M的Ωj個(gè)元素構(gòu)成的列向量。將n個(gè)按列的方向組成矩陣對(duì)應(yīng)地可以獲得，其中為：

其中，B:,Ωi=PΩi(BT)T為矩陣B的j∈Ωi列構(gòu)成的子矩陣。m:.Ωj表示由M的Ωi個(gè)元素構(gòu)成的列向量。

交替使用式（15）、（16）迭代更新B、A直至收斂，最終得到A*、B*后，即可通過(guò)X*=A*TKB*得到X*作為矩陣補(bǔ)全的結(jié)果。以下給出了算法流程，為了敘述方便，將該算法命名為KMC（Kernelized Matrix Completion）算法。

算法2 KMC算法：求解模型（13）

輸入：待補(bǔ)全矩陣M，字典向量d，核函數(shù)κ。

輸出：M≈X=ATKB。

隨機(jī)初始化A、B

計(jì)算核矩陣Kij=κ(di,dj)

Repeat

根據(jù)（15）更新B

根據(jù)（16）更新A

Until收斂條件滿足或達(dá)到最大迭代次數(shù)

ReturnX=ATKB

許多研究常使用奇異值閾值法求解矩陣補(bǔ)全問(wèn)題，如將問(wèn)題（1）中的矩陣X寫(xiě)為奇異值分解的形式：

其中，σi是矩陣X的按降序排列的奇異值，Σ為其構(gòu)成的奇異值矩陣。奇異值閾值法通過(guò)近端梯度下降法，在使得X能近似M的前提下，不斷通過(guò)奇異值閾值算子將X較小的奇異值置為0 來(lái)保證X的低秩性[25]。將式（17）的核范數(shù)進(jìn)行變形得：

省略系數(shù)整理得：

不難看出，KMC 模型（13）與（19）具有一定的相似性。事實(shí)上，若設(shè)問(wèn)題（19）的最優(yōu)解為U*、Σ*、V*，對(duì)模型（13），若核矩陣K恰為Σ*時(shí)，則可表示為：

這說(shuō)明KMC模型符合一般的矩陣補(bǔ)全模型。對(duì)于矩陣分解模型（6），若取矩陣-Σ∈Rk×n，令：

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

4.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)信息

為了檢測(cè)本文提出的算法的效果，挑選了三個(gè)真實(shí)世界的動(dòng)態(tài)網(wǎng)絡(luò)鏈接數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)中使用PA、CN 兩種靜態(tài)鏈接算法和Pech 等人提出的魯棒PCA 的矩陣補(bǔ)全模型法做對(duì)比。本文實(shí)驗(yàn)代碼由作者使用Matlab2018a 編寫(xiě)。運(yùn)行環(huán)境為Win10，Intel?Core? i7-4510U CPU@2.0 GHz，8 GB內(nèi)存。

表1給出了實(shí)驗(yàn)數(shù)據(jù)集的特征信息。WorldTrade記錄了58 個(gè)國(guó)家的國(guó)際貿(mào)易情況的數(shù)據(jù)，記錄時(shí)間為1981—2000年，若對(duì)每年所有國(guó)家之間的貿(mào)易額度進(jìn)行排序，取貿(mào)易額前10%國(guó)家，視為兩國(guó)之間存在鏈接，這樣可以通過(guò)數(shù)據(jù)集建立20 個(gè)58×58 的鄰接矩陣。表中總鏈接數(shù)是20 個(gè)鄰接矩陣所有產(chǎn)生鏈接的個(gè)數(shù)總和，時(shí)期平均鏈接數(shù)是單位時(shí)間矩陣中存在鏈接數(shù)的平均值。EmailEu-core 是歐洲某個(gè)大型研究會(huì)的郵件系統(tǒng)，記錄了研究會(huì)1 005名成員的郵件往來(lái)。本文選取研究會(huì)中兩個(gè)部門(mén)的核心成員在550 天內(nèi)的郵件往來(lái)記錄進(jìn)行實(shí)驗(yàn)，其中每50天作為一個(gè)時(shí)間單位，則可得到11個(gè)n×n的動(dòng)態(tài)網(wǎng)絡(luò)（n為部門(mén)核心成員數(shù)量）。

表1 數(shù)據(jù)集信息

本文采用AUC（Area Under ROC Curve）作為評(píng)價(jià)指標(biāo)。假設(shè)正類(lèi)樣本數(shù)量和負(fù)類(lèi)樣本數(shù)量分別為M和N，首先按照輸出值對(duì)所有樣本從低到高排序并對(duì)每個(gè)樣本賦予一個(gè)排名rank，輸出值最低的元素rank為1，輸出值最高的元素rank為M+N，然后AUC可以通過(guò)以下公式計(jì)算：

4.2 實(shí)驗(yàn)參數(shù)設(shè)置

對(duì)于APG和KMC算法，二者都用到了平衡低秩約束與采樣約束的正則項(xiàng)系數(shù)，即目標(biāo)函數(shù)（3）和（13）中的λ，這類(lèi)參數(shù)的選取已得到較詳細(xì)的研究，本文按文獻(xiàn)[24]所得出的結(jié)論將其設(shè)置為。

4.2.1 使用到的歷史時(shí)刻長(zhǎng)度T

首先可能會(huì)對(duì)算法產(chǎn)生影響的參數(shù)是算法所使用的時(shí)間序列長(zhǎng)度T。直觀上，利用越多的歷史時(shí)刻可以獲得越多的網(wǎng)絡(luò)結(jié)構(gòu)變化的信息，數(shù)值實(shí)驗(yàn)也基本符合這一推斷，圖1展示了本文提出的核矩陣補(bǔ)全算法分別在三個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)效果。三條折線的整體趨勢(shì)是上升的，標(biāo)準(zhǔn)矩陣補(bǔ)全算法（APG）的實(shí)驗(yàn)結(jié)果與圖1類(lèi)似。因?yàn)閿?shù)據(jù)集能提供的網(wǎng)絡(luò)隨時(shí)間的變化信息總是有限的，所以當(dāng)選取過(guò)多的歷史時(shí)刻進(jìn)行訓(xùn)練時(shí)可能會(huì)造成信息的冗余而產(chǎn)生過(guò)擬合，AUC 分?jǐn)?shù)并不會(huì)隨著時(shí)刻數(shù)量線性增長(zhǎng)。為了盡量少地使用歷史時(shí)刻長(zhǎng)度以節(jié)省計(jì)算開(kāi)銷(xiāo)，KMC算法建議采用3～5個(gè)歷史時(shí)刻。

圖1 時(shí)間序列T 對(duì)結(jié)果的影響

4.2.2 字典向量維度d

圖2 字典向量維度d 對(duì)結(jié)果的影響

字典向量的維度d是本文提出的KMC算法需要用到的超參數(shù)之一。圖2展示了KMC算法在三組數(shù)據(jù)集上AUC 隨d的變化情況。一般認(rèn)為，字典向量的維度越高，越能得到更多的鏈接信息，但是圖2 在三組數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，AUC分?jǐn)?shù)在小范圍內(nèi)波動(dòng)，算法對(duì)參數(shù)的選取不敏感。這是由于字典向量被嵌入到高維Hilbert空間當(dāng)中，算法總是能捕捉到高維空間中的鏈接信息，使得對(duì)d的選取不敏感。最終在三組數(shù)據(jù)集上選取d=200 來(lái)進(jìn)行數(shù)值實(shí)驗(yàn)。

4.2.3 矩陣A、B 的秩k

對(duì)于KMC 算法在初始化時(shí)設(shè)置低秩矩陣A、B的秩k。由圖3結(jié)果可知，對(duì)于WorldTrade和EmailEu_Dep2的實(shí)驗(yàn)，結(jié)果基本穩(wěn)定在一個(gè)較高的得分，在k值選取很小時(shí)，符合矩陣的低秩假設(shè)和矩陣補(bǔ)全的要求，當(dāng)k增大時(shí)，低秩矩陣A、B的秩并不會(huì)隨著k的增加而線性增長(zhǎng)，這是因?yàn)檎齽t化項(xiàng)的約束作用，所以預(yù)測(cè)結(jié)果仍然維持在最優(yōu)的水平。對(duì)于EmailEu_Dep1出現(xiàn)了在k=2～6 時(shí)分?jǐn)?shù)較低的現(xiàn)象，可能是因?yàn)榫W(wǎng)絡(luò)結(jié)構(gòu)存在低秩特征矩陣難以捕捉的信息。

圖3 參數(shù)k 對(duì)結(jié)果的影響

4.2.4 核函數(shù)的選取

KMC 算法中將數(shù)據(jù)嵌入更高維度的空間，而高維空間由核函數(shù)隱式地確定，因此選取不同的核函數(shù)就確定了鏈接數(shù)據(jù)不同的嵌入方式，即從不同的角度體現(xiàn)數(shù)據(jù)的分布規(guī)律。表2中MC算法是不使用任何核函數(shù)的矩陣補(bǔ)全算法，其余為使用線性核、高斯核、拉普拉斯核的矩陣補(bǔ)全算法。

表2 不同核函數(shù)在數(shù)據(jù)集上的AUC分?jǐn)?shù)

從表2可知，拉普拉斯核的算法在所有實(shí)驗(yàn)中分?jǐn)?shù)均高于不使用核函數(shù)的MC算法，這驗(yàn)證了使用核技巧的有效性。部分實(shí)驗(yàn)中也出現(xiàn)了高斯核與線性核算法的效果不如不使用核技巧算法的情況，這可能是由于不合適的核函數(shù)不能體現(xiàn)該數(shù)據(jù)集的分布規(guī)律，在映射到高維空間后損失了原始空間中的有效信息，使得核技巧的效果較差。由于每組數(shù)據(jù)上KMC（Laplacian）的分?jǐn)?shù)均高于MC，這表明Laplacian 核函數(shù)能有效地刻畫(huà)數(shù)據(jù)的分布規(guī)律，確定的高維空間能夠更有效地將非線性鏈接關(guān)系轉(zhuǎn)化為線性關(guān)系。因此在對(duì)比實(shí)驗(yàn)中選取Laplacian核作為默認(rèn)參數(shù)。

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

綜合以上實(shí)驗(yàn)參數(shù)的分析，將三組實(shí)驗(yàn)的最優(yōu)參數(shù)的結(jié)果列入表3，作為比較實(shí)驗(yàn)時(shí)的推薦參數(shù)。

表3 KMC算法的參數(shù)設(shè)置

在比較實(shí)驗(yàn)結(jié)果時(shí)，本文使用靜態(tài)鏈接預(yù)測(cè)中常用作基準(zhǔn)算法的PA、CN 作為參照，其中CN、PA 是指只使用前一時(shí)刻網(wǎng)絡(luò)結(jié)構(gòu)的算法，CN-all、PA-all是指使用所有歷史時(shí)刻片段進(jìn)行預(yù)測(cè)的算法，它們都是將靜態(tài)鏈接預(yù)測(cè)算法直接應(yīng)用于動(dòng)態(tài)鏈接預(yù)測(cè)。RPCA（Robust PCA）是由Pech提出的基于魯棒PCA的矩陣補(bǔ)全算法。APG 是指本文提出的利用加速近端梯度下降法求解矩陣補(bǔ)全的算法，KMC是本文提出的核矩陣補(bǔ)全算法（默認(rèn)使用Laplacian核）。

表4表示所有算法在三組數(shù)據(jù)集上的AUC分?jǐn)?shù)，本文提出的KMC算法在前兩組實(shí)驗(yàn)中的AUC得分最高，APG也有較好的表現(xiàn)。在第三組實(shí)驗(yàn)中CN_all的AUC得分最高，KMC略弱于基準(zhǔn)算法，但CN_all需要使用以往所有歷史時(shí)刻的網(wǎng)絡(luò)鄰接矩陣，計(jì)算存儲(chǔ)要求較高，不適合處理大規(guī)模鏈接預(yù)測(cè)問(wèn)題。RPCA 通過(guò)建立噪聲矩陣和原始矩陣求解鏈接預(yù)測(cè)，本質(zhì)上屬于矩陣補(bǔ)全模型，因此預(yù)測(cè)效果與APG相差不大。但由于KMC在矩陣補(bǔ)全模型的基礎(chǔ)上加入核函數(shù)，能夠?qū)W習(xí)到鏈接之間的非線性關(guān)系，因此KMC效果略好于RPCA，實(shí)驗(yàn)結(jié)果也驗(yàn)證了使用核方法的有效性。

表4 多種算法在三組數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

5 結(jié)束語(yǔ)

針對(duì)傳統(tǒng)矩陣補(bǔ)全解決鏈接預(yù)測(cè)的局限性，本文提出了KMC 算法，以解決動(dòng)態(tài)鏈接預(yù)測(cè)問(wèn)題。詳細(xì)介紹了矩陣補(bǔ)全和核矩陣補(bǔ)全優(yōu)化模型，并推導(dǎo)了核矩陣補(bǔ)全方法與基于奇異值閾值的矩陣補(bǔ)全方法之間的關(guān)系。在三組公開(kāi)的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果表明，KMC算法優(yōu)于傳統(tǒng)的鏈接預(yù)測(cè)算法和矩陣補(bǔ)全算法，通過(guò)與MC、RPCA算法進(jìn)行對(duì)比，驗(yàn)證了引入核函數(shù)的有效性。

本文將拉普拉斯核作為核矩陣補(bǔ)全模型中的核函數(shù)，優(yōu)于基于其他常用核函數(shù)的預(yù)測(cè)效果。未來(lái)考慮將如何自適應(yīng)地選取核函數(shù)和提高核函數(shù)對(duì)非線性關(guān)系的刻畫(huà)能力作為下一步的工作。