李艷麗，周 濤

(電子科技大學(xué)復(fù)雜性科學(xué)實驗室 成都611731)

鏈路預(yù)測的核心任務(wù)是預(yù)測兩個沒有連接關(guān)系的節(jié)點產(chǎn)生鏈接的可能性[1-4]。該研究方向最初的興起是為了輔助萬維網(wǎng)用戶從海量的網(wǎng)頁中尋找感興趣的網(wǎng)頁[5-6]。后來逐漸在朋友關(guān)系預(yù)測[7]、恐怖分子的發(fā)現(xiàn)[8]、潛在的學(xué)術(shù)合作關(guān)系預(yù)測[9]、生物學(xué)相互作用關(guān)系的揭示[10-11]、商品推薦[12]、網(wǎng)絡(luò)生成機制探索[13-14]和網(wǎng)絡(luò)可預(yù)測性[15-17]等問題上發(fā)揮了巨大價值。其預(yù)測類型囊括了根據(jù)觀測到的網(wǎng)絡(luò)結(jié)構(gòu)預(yù)測可能存在的缺失連邊(missing link)，未來可能產(chǎn)生的連邊(future links)以及甄別虛假連邊(spurious link)等[1,18]。其研究對象涵蓋了簡單網(wǎng)絡(luò)、有向網(wǎng)絡(luò)、二分網(wǎng)絡(luò)、異構(gòu)網(wǎng)絡(luò)和時序網(wǎng)絡(luò)等[19]。其方法論涉及了基于相似性的鏈路預(yù)測算法(similarity-based algorithms)[9,20]、概率模型(probabilistic models)[21-23]、最大似然模型(maximum likelihood methods)[8,18,24]、網(wǎng)絡(luò)嵌入模型(network embedding)[25-28]和其他方法[29-31]。

基于相似性的鏈路預(yù)測算法尤其是局部相似性指標(biāo)可應(yīng)用領(lǐng)域最為廣泛。因為它設(shè)計簡潔、可解釋性強、運算時間低、靈活可擴展，同時其預(yù)測準(zhǔn)確度有時甚至優(yōu)于相對復(fù)雜的概率模型、最大似然模型和網(wǎng)絡(luò)嵌入模型[31-33]。該類算法的基本思路是利用節(jié)點的局部拓?fù)浣Y(jié)構(gòu)信息為每一條候選連邊分配一個相似性得分，得分越高的連邊被認(rèn)為有更大可能是缺失邊，因此在預(yù)測列表中排序更靠前。這些算法中最具代表性的幾個工作分別是文獻(xiàn)[9]總結(jié)的純粹基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的一系列局部相似性指標(biāo)的工作、文獻(xiàn)[34]提出AA指標(biāo)的工作和文獻(xiàn)[20]提出RA指標(biāo)(resource allocation)的工作。文獻(xiàn)[9]首次明確提出了基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的相似性定義框架，同時一個非常簡單且符合直覺的相似性指標(biāo)——共同鄰居指標(biāo)(common neighbors,CN)也是在該文中被明確強調(diào)，即兩個節(jié)點如果擁有越多的共同鄰居，則越相似。定義 Γx為 節(jié)點x的鄰居集合，則網(wǎng)絡(luò)中節(jié)點x和 節(jié)點y的共同鄰居指標(biāo)可定義為：

不同于CN指標(biāo)，AA指標(biāo)不僅考慮兩個節(jié)點擁有的共同鄰居數(shù)目，而且考慮共同鄰居的角色差異。具體定義如下：

式中，kz表示節(jié)點z的度。該指標(biāo)大大削弱了共同鄰居中大度節(jié)點的貢獻(xiàn)。RA是眾多局部相似性指標(biāo)中少有的包含物理過程的指標(biāo)[35]。由資源分配的物理過程出發(fā)，兩個節(jié)點的相似性由從其中一個節(jié)點傳遞到另一個節(jié)點的資源量決定。節(jié)點x的每一個鄰居都擁有一個單位的資源，并將各自擁有的資源平均分配給它們的鄰居，節(jié)點y從中接收到的資源量即為兩者的相似性值，即：

從數(shù)學(xué)形式上看，CN、AA和RA指標(biāo)的區(qū)別在于是否考慮共同鄰居的角色差異。在CN指標(biāo)中，所有共同鄰居的貢獻(xiàn)相同，AA和RA則都是削弱了大度共同鄰居的貢獻(xiàn)，只是一個從物理過程出發(fā)設(shè)計，一個從信息論角度出發(fā)設(shè)計。從預(yù)測效果上看，三者在節(jié)點度相差不大的網(wǎng)絡(luò)，即有較小的度異質(zhì)性的網(wǎng)絡(luò)中，預(yù)測效果不會有顯著差異。但在度異質(zhì)性大，且平均度較大的網(wǎng)絡(luò)，CN、AA和RA指標(biāo)在預(yù)測效果上差異顯著。在大多數(shù)網(wǎng)絡(luò)中，RA預(yù)測效果最好，AA次之，CN最差。原因有三：一是大多數(shù)真實網(wǎng)絡(luò)的度分布呈長尾特性，度異質(zhì)性較強[36-37]；二是大度節(jié)點成為共同鄰居比較常見，難以體現(xiàn)節(jié)點間的相似性，因此懲罰大度節(jié)點可以更好刻畫大度共同鄰居與小度共同鄰居不同的角色；最后，CN簡并度高，很多候選邊的CN值相同，而AA和RA的區(qū)分度遠(yuǎn)勝于CN。

這些工作可用相同且堅實的理論和實證依據(jù)進(jìn)行解釋，包括社會學(xué)中的同質(zhì)性原理[38]，即兩個相似的節(jié)點更大概率產(chǎn)生連邊。三角閉包理論[39]，即“朋友的朋友就是朋友”和物理學(xué)中的聚集性原理[40]，即兩個擁有更多共同鄰居的節(jié)點更大概率產(chǎn)生連邊。這一系列暗含同一內(nèi)涵的理論早在2001年的合作演化網(wǎng)絡(luò)[40]和2006年的郵件通信演化網(wǎng)絡(luò)[41]中得到了驗證。同時也被證實在一些非社交網(wǎng)絡(luò)中同樣成立[42]。

至此，大多數(shù)局部相似性指標(biāo)的研究工作都在上述理論框架中開展。通過更精細(xì)的刻畫共同鄰居節(jié)點以及候選節(jié)點對的自身拓?fù)浣Y(jié)構(gòu)差異，引入并更好地利用節(jié)點的屬性信息。研究人員發(fā)展出了一系列局部相似性指標(biāo)，并一次又一次地刷新了預(yù)測效果[1,19,43-45]。一般而言，在如此簡單的理論框架下很難產(chǎn)生突破，但最近的若干工作跳出了該框架的約束，提出了新的連邊理論并對原始基于共同鄰居的局部相似性指標(biāo)設(shè)計框架發(fā)起了挑戰(zhàn)。這些工作的出現(xiàn)將使我們對節(jié)點間局部連接模式的理解進(jìn)入一個新的階段。

1 LCP和Cannistraci-Hebb理論

在社團結(jié)構(gòu)明顯的網(wǎng)絡(luò)中，同一社團內(nèi)部產(chǎn)生連邊的概率要大于社團之間產(chǎn)生連邊的概率。基于該思想，只要增加同一社團內(nèi)部連邊產(chǎn)生的概率，預(yù)測性能便可以提高。最直接的做法是使用一些現(xiàn)成的社團識別算法先識別社團，再區(qū)分對待社團內(nèi)部和社團之間的節(jié)點連邊概率[46-47]，但這樣做并不能為我們理解和利用上述思想提供更深刻的洞見和啟發(fā)。針對沒有顯式社團標(biāo)簽的網(wǎng)絡(luò)，有沒有可能設(shè)計出一套考慮節(jié)點間社團連接模式的高效且性能良好的鏈路預(yù)測指標(biāo)呢？

2013年，文獻(xiàn)[48]做出了非常有價值的嘗試和推動，如果把最近十年局部相似性指標(biāo)發(fā)展史上有推動意義的工作收錄成榜，這一貢獻(xiàn)絕對名列前茅。受到以邊為研究對象對社團進(jìn)行劃分的啟發(fā)[48]，文獻(xiàn)[49]提出了兩個節(jié)點之間由邊構(gòu)成的局部社團內(nèi)部連接越緊密，兩個節(jié)點越容易產(chǎn)生連邊的局部社團范式(local-community-paradigm,LCP)。LCP指由共同鄰居及其之間的連邊形成的局部結(jié)構(gòu)，展示的是一種不依賴于節(jié)點標(biāo)簽和邊標(biāo)簽的局部社團描述方法。盡管也有少量工作有類似的出發(fā)點[47,50]，但并沒有形成一種堅實清晰且干凈利落的方法論。LCP作為一種簡單獨立的結(jié)構(gòu)，很容易作為一種性能增強插件融入到過去已有的局部相似性指標(biāo)中。如針對CN指標(biāo)，LCP融入后形成的CAR指標(biāo)表示如下：

式中， γz表 示在節(jié)點x和 節(jié)點y形成的LCP結(jié)構(gòu)中，節(jié)點z的節(jié)點度，亦即節(jié)點z與x和y的其他共同鄰居的連邊數(shù)。類似地，針對RA指標(biāo)，LCP融入后形成的CRA指標(biāo)可表示為：

從數(shù)學(xué)表達(dá)形式上來看，相對于CN和RA等指標(biāo)，基于LCP的局部相似性指標(biāo)對連邊相似度有更強的區(qū)分度。但這些LCP增強指標(biāo)存在一個明顯的缺陷，在共同鄰居之間連邊稀疏甚至沒有連邊的網(wǎng)絡(luò)中，它們的預(yù)測性能將差于原始的RA指標(biāo)，甚至CN指標(biāo)。

LCP的核心思想與著名的“赫布律”(Hebb Theory)一致[51]。赫布律的核心思想是知識、學(xué)習(xí)過程或記憶痕跡存儲于由神經(jīng)元(可視作網(wǎng)絡(luò)中的節(jié)點)和突觸(可視作網(wǎng)絡(luò)中的邊)構(gòu)成的突觸集合中，而非神經(jīng)元個體。文獻(xiàn)[52]在2018年指出網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)所起的關(guān)鍵作用便是將不同功能的“突觸集合”隔離開，每個“突觸集合”中的神經(jīng)元通過在集合內(nèi)部加強或者產(chǎn)生新的突觸來完成信息的局部處理過程。這也就意味著連邊更大概率產(chǎn)生于由邊構(gòu)成的隔離度良好的局部社團內(nèi)部，這恰與前文提到的LCP范式一致。基于CRA進(jìn)行微調(diào)后的Cannistraci-Hebb指標(biāo)可表示為：

LCP和Cannistraci-Hebb理論是局部相似性指標(biāo)研究歷程重要且令人印象深刻的系列研究成果，該工作僅僅是對局部社團連接范式的初步嘗試，就已獲得卓越的預(yù)測效果，它必將為我們理解節(jié)點對之間的局部連接模式、刻畫無標(biāo)簽依賴的局部社團結(jié)構(gòu)以及設(shè)計出更優(yōu)美有效的相似性指標(biāo)帶來靈感。

2 路徑越短價值越高？

長久以來研究人員一個不證自明的認(rèn)識是節(jié)點間較短連邊的數(shù)目要比較長連邊的數(shù)目更能刻畫節(jié)點之間產(chǎn)生連邊的似然。因為節(jié)點之間的互動關(guān)系和相互影響會隨著連邊距離的增大而衰減[53-54]。該現(xiàn)象在眾多的基于2階路徑設(shè)計的相似性指標(biāo)上可見一斑。即便考慮了較長路徑連邊數(shù)目的相似性指標(biāo)(如Katz[55]和LP[56])，短路徑也永遠(yuǎn)扮演主要角色，路徑長度越長，貢獻(xiàn)越小。這些長路徑的加入主要起到增加連邊似然分辨率的作用。然而2018年之后連續(xù)出現(xiàn)了一系列工作表明3階路徑比2階路徑能更有效地預(yù)測未知鏈路[52,57-58]。這非常反直覺甚至令人生疑，如果這一發(fā)現(xiàn)存在于大多數(shù)網(wǎng)絡(luò)中，將會是對過去認(rèn)知的巨大挑戰(zhàn)。

文獻(xiàn)[57]假定節(jié)點x和 節(jié)點y的連邊似然可以由x的所有鄰居貢獻(xiàn)值的線性求和表示，即：

式中，Z為一個待求解的矩陣。通過最小化Z與觀測到的鄰接矩陣A的差異得到以下優(yōu)化函數(shù)：

該優(yōu)化問題有一個閉合解，即

式中，I為單位矩陣。從而，節(jié)點x和 節(jié)點y的LO連邊似然可表示為：

LO算法的預(yù)測效果顯著優(yōu)于當(dāng)前一些利用全局信息的代表性算法，包括SPM[15]和Katz[55]等。令人驚奇的是LO的退化指標(biāo)——直接計算節(jié)點3階路徑數(shù)目的A3指標(biāo)也優(yōu)于CN指標(biāo)。

同時期，在專門針對蛋白質(zhì)相互作用網(wǎng)絡(luò)(protein-protein interaction,PPI)進(jìn)行關(guān)系預(yù)測的研究中，文獻(xiàn)[58]從蛋白質(zhì)相互作用網(wǎng)絡(luò)的結(jié)構(gòu)和演化證據(jù)出發(fā)，指出相互作用的兩個蛋白質(zhì)大多數(shù)情況下需要互補的界面表征(interface)。共享大量相同蛋白質(zhì)的兩個蛋白質(zhì)界面表征大概率相似或者相同，而非互補。他們進(jìn)一步通過實證分析表明傳統(tǒng)的基于共同鄰居的相似性指標(biāo)與連邊概率呈負(fù)相關(guān)性。為了迎合PPI網(wǎng)絡(luò)的結(jié)構(gòu)特性，他們啟發(fā)式地設(shè)計了一個名為L3的3階路徑指標(biāo)，其數(shù)學(xué)形式如下：

該指標(biāo)顯著提升了PPI網(wǎng)絡(luò)中潛在相互作用關(guān)系的預(yù)測準(zhǔn)確度。

文獻(xiàn)[57]是針對一般性網(wǎng)絡(luò)，通過抽象理論分析自動得到衍生指標(biāo)A3；文獻(xiàn)[58]則從一個具體的網(wǎng)絡(luò)出發(fā)，基于對網(wǎng)絡(luò)本身的連邊結(jié)構(gòu)特征的深刻理解啟發(fā)式地提出L3指標(biāo)。兩種完全不同的方法論，在幾乎相同的時間獲得幾乎一致的結(jié)果！文獻(xiàn)[52]迅速關(guān)注了該項研究，并敏銳地認(rèn)為有必要提出一個一般性的理論框架將該重要發(fā)現(xiàn)推廣到已有的局部相似性指標(biāo)和n階路徑上?；趲缀纹骄鶖?shù)思想，即n個變量的幾何平均為這n個變量連乘的n次方根，RA指標(biāo)在n階路徑上的推廣可自然而然的表示為：

式中，L(n)為 連接節(jié)點x和 節(jié)點y的n階路徑上的n–1個中間節(jié)點集合。不難發(fā)現(xiàn)，前文提到的L3指標(biāo)即為RA指標(biāo)在3階路徑上的推廣。同時他們也進(jìn)一步通過實證表明基于3階路徑的局部相似性指標(biāo)不僅在蛋白質(zhì)相互作用網(wǎng)絡(luò)，而且在國際貿(mào)易網(wǎng)絡(luò)和食物鏈網(wǎng)絡(luò)上都優(yōu)于基于2階路徑的局部相似性指標(biāo)。

如果說上述發(fā)現(xiàn)所考慮的網(wǎng)絡(luò)太少并不足以挑戰(zhàn)我們對局部連邊模式的傳統(tǒng)認(rèn)知，接下來兩個大規(guī)模實驗的結(jié)果促使我們不得不回看最開始的局部相似性指標(biāo)的設(shè)計原理，并斟酌它是否絕對適合所有網(wǎng)絡(luò)。首先文獻(xiàn)[59]基于137個來自16個領(lǐng)域的真實網(wǎng)絡(luò)進(jìn)行的一次大規(guī)模實證[59]。該實證研究對比了CN、AA、RA、Cannistraci-Hebb指標(biāo)和它們在3階路徑上的推廣指標(biāo)的預(yù)測性能。結(jié)果發(fā)現(xiàn)，3階路徑指標(biāo)在相當(dāng)大一部分網(wǎng)絡(luò)中表現(xiàn)占優(yōu)，但并不存在一類指標(biāo)可以在所有領(lǐng)域絕對占優(yōu)，即有些領(lǐng)域是基于2階路徑的相似性指標(biāo)表現(xiàn)更好，而有些領(lǐng)域是基于3階路徑的相似性指標(biāo)表現(xiàn)更好。如果把不同領(lǐng)域的網(wǎng)絡(luò)放到一起綜合評價，基于3階路徑的相似性指標(biāo)在AUC指標(biāo)(即ROC曲線下面積)上優(yōu)于基于2階路徑的相似性指標(biāo)，即在超過50%的網(wǎng)絡(luò)中，基于3階路徑的相似性指標(biāo)預(yù)測效果更好。而在Precision指標(biāo)上，兩者表現(xiàn)相當(dāng)。該實證研究一個意外的發(fā)現(xiàn)就是驗證了LCP理論和赫布律的價值：在涉及的4個系列的算法中，Cannistraci-Hebb系列指標(biāo)成為表現(xiàn)最好的指標(biāo)。文獻(xiàn)[32]進(jìn)一步基于1 371個來自14個領(lǐng)域的真實網(wǎng)絡(luò)進(jìn)行了又一次大規(guī)模實證分析，結(jié)果再一次表明，在以AUPR為評價指標(biāo)的實驗中，網(wǎng)絡(luò)所屬領(lǐng)域不同，表現(xiàn)占優(yōu)的算法類別也不同。

針對基于2階路徑的相似性指標(biāo)和基于3階路徑相似性指標(biāo)預(yù)測性能的爭議的意義并不在于選出一個表現(xiàn)更好的相似性指標(biāo)，而是重塑我們對于節(jié)點間局部連接模式的認(rèn)識，鼓勵并啟發(fā)我們設(shè)計出更有效的局部相似性指標(biāo)。

3 結(jié)束語

在鏈路預(yù)測興起的最初幾年，得益于網(wǎng)絡(luò)科學(xué)關(guān)于節(jié)點連邊模式和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特點的豐碩成果，產(chǎn)生了一系列在同一框架下的經(jīng)典的局部相似性指標(biāo)。然而想要在該框架下進(jìn)一步大幅度提升預(yù)測性能更多地需要借助拓?fù)湟酝獾墓?jié)點或邊的屬性信息。本文總結(jié)了近十年有別于傳統(tǒng)框架的新理論和新發(fā)現(xiàn)，其中必將孕育新的預(yù)測算法。在以應(yīng)用為導(dǎo)向追求無限刷新預(yù)測效果的同時，鏈路預(yù)測研究的另一個重要使命是探索網(wǎng)絡(luò)的形成和演化機制[13-14,60]，理解網(wǎng)絡(luò)的組織結(jié)構(gòu)以及節(jié)點連邊范式。如果能夠?qū)W(wǎng)絡(luò)背后的組織邏輯精確理解，對應(yīng)的鏈路預(yù)測效果自然水到渠成。從這個角度而言，局部相似性指標(biāo)便是以此目標(biāo)為驅(qū)動發(fā)展形成的一個重要分支。該分支對應(yīng)的算法簡潔、易用、時間復(fù)雜度和空間消耗低、預(yù)測性能也具有競爭力，且每一個算法的提出都對應(yīng)著對一般網(wǎng)絡(luò)或特定網(wǎng)絡(luò)節(jié)點連邊模式的一個新的理解，在豐富了具體網(wǎng)絡(luò)先驗知識的同時，也可以進(jìn)一步推廣到利用全局信息的概率模型和網(wǎng)絡(luò)嵌入等模型中，從而激發(fā)更多的后續(xù)研究。因此，即便在機器學(xué)習(xí)技術(shù)蓬勃發(fā)展的今天，局部相似性指標(biāo)在鏈路預(yù)測研究的方法論中仍然有很大的不可替代性，且作為眾多研究領(lǐng)域的技術(shù)基礎(chǔ)，其科研價值和應(yīng)用價值都不容小覷。