鏈路預測中的局部相似性指標

李艷麗，周 濤

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

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

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

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

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

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

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

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

1 LCP和Cannistraci-Hebb理論

在社團結構明顯的網絡中，同一社團內部產生連邊的概率要大于社團之間產生連邊的概率?；谠撍枷?，只要增加同一社團內部連邊產生的概率，預測性能便可以提高。最直接的做法是使用一些現成的社團識別算法先識別社團，再區分對待社團內部和社團之間的節點連邊概率[46-47]，但這樣做并不能為我們理解和利用上述思想提供更深刻的洞見和啟發。針對沒有顯式社團標簽的網絡，有沒有可能設計出一套考慮節點間社團連接模式的高效且性能良好的鏈路預測指標呢？

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

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

從數學表達形式上來看，相對于CN和RA等指標，基于LCP的局部相似性指標對連邊相似度有更強的區分度。但這些LCP增強指標存在一個明顯的缺陷，在共同鄰居之間連邊稀疏甚至沒有連邊的網絡中，它們的預測性能將差于原始的RA指標，甚至CN指標。

LCP的核心思想與著名的“赫布律”(Hebb Theory)一致[51]。赫布律的核心思想是知識、學習過程或記憶痕跡存儲于由神經元(可視作網絡中的節點)和突觸(可視作網絡中的邊)構成的突觸集合中，而非神經元個體。文獻[52]在2018年指出網絡的拓撲結構所起的關鍵作用便是將不同功能的“突觸集合”隔離開，每個“突觸集合”中的神經元通過在集合內部加強或者產生新的突觸來完成信息的局部處理過程。這也就意味著連邊更大概率產生于由邊構成的隔離度良好的局部社團內部，這恰與前文提到的LCP范式一致?；贑RA進行微調后的Cannistraci-Hebb指標可表示為：

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

2 路徑越短價值越高？

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

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

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

該優化問題有一個閉合解，即

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

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

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

該指標顯著提升了PPI網絡中潛在相互作用關系的預測準確度。

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

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

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

針對基于2階路徑的相似性指標和基于3階路徑相似性指標預測性能的爭議的意義并不在于選出一個表現更好的相似性指標，而是重塑我們對于節點間局部連接模式的認識，鼓勵并啟發我們設計出更有效的局部相似性指標。

3 結束語

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