超圖環境下鏈路預測問題的探究

佘美富， 王逸偉， 張建章， 詹秀秀， 劉闖

1. 杭州師范大學 阿里巴巴復雜科學研究中心，杭州 311121；2. 合肥綜合性國家科學中心數據空間研究院，合肥 230088

“關系”普遍存在于現實生活中的各實體之間, 如人們之間的合作或社交、 有機物之間的生化反應等． 數學上, 人們習慣將上述各實體看作節點, 實體間的關系看作節點對的連邊, 從而將其表達成統一而簡潔的符號形式——圖(亦稱網絡), 并輔之以嚴密的數學工具來分析和解決現有問題． 然而, 相較于成對實體, 現實中更多存在的是成群實體間的關系, 如合作或社交小組、 多個有機物共同參與的生化反應等． 邊所連接節點的數量限制成為圖表達能力的桎梏, 使其只能展現成對實體之間的關系． 作為圖的自然擴展, 超圖將邊所連接的節點數量放松至任意, 從而形成了不同于普通邊的“超邊”． 這種結構上的突破使得超圖能呈現任意數量的實體間關系, 進而獲得大大強于普通圖的表達能力． 超圖在表達能力上的優勢吸引人們的關注并日益成為研究熱點．

在構建圖的過程中, 由于觀測手段、 數據丟失等問題, 不能保證實體間所有存在的關系都已被描述． 隨著圖的演化, 節點之間會產生新的關系, 預測缺失或未來即將出現的超邊被稱之為超圖的鏈路預測, 為了與普通圖的鏈路預測問題進行區分, 將其簡稱為“超鏈路預測”． 由于關系的重要性, 超鏈路預測日益成為人們的研究重點． 然而, 超邊大小的任意性導致人們在進行超鏈路預測時遇到了一些阻礙, 首當其沖的便是候選超邊數量的暴增． 具體來說, 超邊連接節點數量的放松導致候選超邊數量的規模從O(n2)暴增至O(2n), 鏈路預測方法的輸入節點數從固定值2變為任意值． 關于候選超邊數量暴增的問題, 對原始的候選超邊集進行下采樣是一個通用方法． Zhang等[1]對原始的候選超邊集按領域知識對各數據集進行采樣, 并定義了基于采樣后的候選超邊集的超鏈路預測問題． Patil等[2]在完全隨機采樣和依超邊大小分布采樣的基礎上, 提出了基于motif和clique的抽樣方法, 并對這些方法所抽取的樣本進行了可預測性研究． 另一種手段是根據啟發式方法直接得到待預測超邊的大小． Kumar等[3]認為超邊的產生應該遵循原始超圖的結構規則, 將原始超圖的超邊大小分布的采樣值作為待預測超邊的大小． Srinivasan等[4]直接將大小的預測值嵌入生成對抗圖中, 利用對抗學習的機制來擬合最佳預測參數． 除候選超邊數量暴增的問題外, 超鏈路預測方法的輸入節點數不固定也是一個棘手的問題, 解決該問題的方式依賴于超鏈路預測方法本身的設計模式, 偏重于機器學習、 矩陣分解模型的方法通常會將待評分的候選超邊編碼成固定長度的特征向量, 將其作為標準分類器的輸入． 例如, Srinivasan等[4]提出了一種新的特征聚合方法, 該方法將節點與超邊置于同等地位以進行對稱式的卷積運算, 證明了使用所提出方法進行特征學習, 同一等價類的節點或超邊之間有相同的特征表示, 所學習到的特征在下游的鏈路預測任務上有著十分優異的表現． Yuan等[5]提出一種基于張量的聯合圖嵌入方法, 將成對鏈接和超鏈接同時編碼到潛在空間上, 該方法捕獲并編碼了高階連接的依賴關系, 并據此推斷未觀察到的超邊． 而偏重于復雜圖的方法則更加啟發式地解決該問題, Benson等[6]認為超邊的相似性是所包含節點之間相似性的整體表現, 提出了基于節點對計算候選超邊相似性的一般方法． Kumar等[3]則提出了一個迭代式算法, 在每次迭代中進行尋找最優匹配節點并將所預測的超邊大小作為迭代次數, 最終輸出符合預期的預測超邊．

作為鏈路預測的延伸, 人們會很自然地關注經典鏈路預測方法應用到超圖上的可行性． 傳統鏈路預測的理論已日趨成熟, 諸如Lorrain[7]、 Ou[8]、 Katz[9]、 Liu[10]等的方法足以覆蓋大部分場景． 在長時間的探索后, 人們普遍認為一個優秀的鏈路預測方法應具有這樣的特征: 在可解釋性強、 計算復雜度相對較低的情況下依然擁有較好的預測效果[11]． 依托成熟的鏈路預測理論, 將鏈路預測方法應用到超圖環境下是一個很自然的想法． 然而, 圖與超圖之間巨大的拓撲結構差異使得將此方法移植至超圖上時舉步維艱． 近年來有極少數的研究基于經典鏈路預測方法的思想去開發對應的超鏈路預測版本． Pan等[12]延伸了普通圖的環思想, 在超圖上定義了節點環路與超邊環路, 對不同長度的環路進行加權求和作為邏輯回歸的輸入, 從而對各候選超邊進行概率預測． Srinivasan等[4]受傳統鏈路預測領域內RA算法的影響, 提出了HRA算法以用于超鏈路預測．

基于上述研究, 在探索的起點上, 本文討論了一個經典鏈路預測方法——帶重啟的隨機游走(random walk with restart, 簡稱RWR)指標, 如何擴展并應用于輸入節點數可變的超鏈路預測場景中, 以該方式為藍本, 擴展了其他傳統鏈路預測指標, 并以此作為基礎方法． 引入了9個不同領域、 不同規模的真實超圖, 并對這些超圖的節點組進行抽樣以生成部分基礎方法的分數抽樣分布, 通過生成的抽樣分布驗證了所引入方法在解決超鏈路預測問題上的有效性, 發現并解釋了不同方法的分數分布在不同大小節點組上的差異． 然后, 使用上述方法在所有真實超圖上進行了標準的超鏈路預測實驗, 按照Zhang等[1]所提及的方式進行下采樣以減少候選超邊數量． 結果表明, 帶重啟的隨機游走指標在精確率和召回率上要明顯優于其他指標, 雖然沒有一個方法在接收者操作特征曲線下面積(AUC)性能上對所有數據集表現一致優越, 但各方法分組AUC的性能變化曲線卻與對應的分數分布變化類似, 且均呈現出隨節點組大小遞增的驚人一致性． 上述所有結果都暗示著大超邊內部節點的連接強度要遠遠大于小超邊．

1 問題定義

1.1 超圖

給定超圖H=〈V,E〉, 其中V={v1, …,vn}, 是n個節點組成的節點集,E={e1, …,em}, 是由m個超邊組成的超邊集． 每一條超邊ej由若干個節點組成, 表示節點之間的相互作用, 用|ej|表示超邊ej的大小, 即其所包含的節點數．V的所有節點組合構成了該節點集的冪集2V, 取節點組e∈2V, 則e的大小可取值1, 2, 3, …,n． 因此有超圖的超邊集E?2V． 數學上, 使用關聯矩陣B=(bij)n×m表示超圖, 其行表示節點, 列表示超邊, 當且僅當節點vi屬于(亦稱關聯)超邊ej時, 對應元素bij=1, 否則bij=0．

1.2 超鏈路預測

對于上述超圖, 想象因“某種原因”使得部分超邊丟失, 導致其僅有部分超邊能夠被觀察到． 則E被分為已觀察超邊集Eo(亦稱正邊集)和遺失超邊集Euo, 且有Euo=EEo, 這些遺失超邊與不能夠形成超邊的節點組(亦稱負邊集)混雜在一起組成了候選集D, 記負邊集合為En, 且有D=Euo∪En,Φ=Euo∩En． 基于此定義超圖上的鏈路預測任務: 利用正邊集Eo, 從候選集D中盡可能多地尋找到屬于Euo的邊． 該任務等價于一個二分類問題, 在實施過程中, 首先利用鏈路預測方法對D中所有樣本進行評分, 根據評分結果設立一個閾值, 將評分高于閾值的樣本判定為正樣本, 否則為負樣本．

1.3 下采樣

這里, 候選樣本集Es的選取也值得討論． 在超圖鏈路預測的環境下, 超邊大小的任意性導致了候選集(所有未形成邊的節點組)2VEo的大小呈O(2|V|)上升, 即所謂的“極端類不平穩問題”(extreme class imbalance, 簡稱ECI)[2]． 從大量的候選邊中尋找各個遺失超邊無異于大海撈針． 為此, 需要對候選集進行下采樣以減小推斷空間的大小． 而下采樣所采樣出的候選樣本需要符合“實際情況”, 這里將“實際情況”理解為候選樣本的大小分布應該與已觀察超邊集合的大小分布一致[2]． 為此, 根據已觀察超邊集Eo的超邊大小分布, 對候選樣本空間2VEo進行下采樣以生成候選樣本集Es, 從而保證候選樣本集Es的大小分布與Eo一致．

2 方法

超鏈路預測問題考慮的是超圖中一組節點是否能形成超邊, 因此首先研究節點對之間的相似性． 本文提出用超圖上帶重啟的隨機游走來定義節點對之間的相似性, 還拓展了基于普通圖的一些節點對相似性方法來定義超圖中節點對的相似性． 基于節點對的相似性再刻畫節點組的相似性, 以此作為超鏈路的預測方法．

2.1 節點對的相似性

2.1.1 帶重啟的隨機游走指標

帶重啟的隨機游走是鏈路預測里的一個經典方法, 該方法基于圖上的帶重啟隨機游走, 并將節點對之間的平穩互達概率作為鏈路預測分數[11]． 為將上述指標擴展到超圖, 需要先定義超圖上的隨機游走． 假設游走者在時刻t(t=0, 1, …)位于節點vi, 考慮一種無偏的情況, 游走者首先隨機游走到包含該節點的任意一條超邊上, 并在t+1時刻隨機游走到關聯該超邊的節點vj． 這里定義的超圖隨機游走可簡單表述為上述過程的迭代． 該游走者在t到t+1期間, 從節點vi轉移到節點vj的概率為:

(1)

式(1)計算了從vi到vj的單步轉移概率, 其前一項和后一項分別描述了“游走到超邊”和“游走到節點”的過程． 由于超圖中有n個節點, 相應地有n2個單步轉移概率, 將這些概率值組織成概率轉移矩陣P=(pij)n×n． 依式(1)可將該矩陣進行分解:

(2)

DvE∈Rn×n,DeV∈Rm×m, 均為對角陣, 對角線元素分別為各節點所關聯的超邊數和各超邊所包含的節點數．

(3)

需要注意的是, 并未限制在每一步隨機游走的過程中游走者不能跳回上一步節點, 這是為了使狀態轉移矩陣P能分解為式(2)所示的矩陣運算． 在此基礎上添加重啟機制, 即在每步游走時, 有一定可能跳回到初始節點vi, 跳回概率為c(0

(4)

(5)

因此, 可以定義節點對vi,vj的平穩解RWR分數:

(6)

式(6)將隨機游走者從初始節點vi出發并到達vj的平穩概率作為節點對的相似性分數, 其大小表征了從vi到vj的可達性, 內在編碼了超圖的拓撲結構． 很明顯, 該分數并不具有對稱性, 即RWR(vi,vj)≠RWR(vj,vi)．

2.1.2 基礎方法擴展

受普通圖鏈路預測方法和已有超圖研究的啟發, 本文設計了一些超圖上刻畫節點對相似性的方法, 以下列舉這些基礎方法基于節點對輸入的定義．

1) 共同鄰居指標(Common Neighbors, 簡稱CN)． 共同鄰居指標是傳統鏈路預測中最簡單也是最經典的指標． 該指標基于“共同鄰居越多的節點對越相似”這一思想, 計算公式為[13]:

CN(vi,vj)=|Nvi∩Nvj|

(7)

式中Nvi是節點vi的鄰居集合, 在超圖中, 它是指與節點vi共存于同一超邊內的其他所有節點．

2) 共存超邊指標(Coexist Edge, 簡稱CE)． 不同于普通圖, 在超圖環境中, 由于邊大小的任意性, 兩個節點往往會被多個超邊同時包含． 統計包含節點對的超邊個數便得到共存超邊指標, 其計算公式為:

CE(vi,vj)=|Evi∩Evj|

(8)

式中Evi是包含節點vi的超邊集合．

3) Jaccard指標(簡稱JC)． Jaccard指標[14]最初用來計算兩集合之間的相似性． 在超圖中, 用該指標計算節點對之間的相似性定義如下:

(9)

4) Adamic-Adar指標(簡稱AA)． Adamic-Adar指標[15]在CN的基礎上考慮了共同鄰居的權重, 權重是共同鄰居的鄰居數對數的倒數． 在超圖中, 對于節點, 可以將共存于同一超邊的其他節點看作“點鄰居”, 將節點所關聯的超邊看作“邊鄰居”． 對于超邊, 可以將所包含的節點看作點鄰居, 將具有共同關聯節點(即相交)的超邊看作邊鄰居． 由于鄰居可分為點鄰居和邊鄰居, 點鄰居、 邊鄰居的不同組合對應4種不同的AA指標, 分別為VVAA、VEAA、EVAA、EEAA． 計算公式如下:

(10)

指標名稱的第一個和第二個字母分別代表共同鄰居和共同鄰居的鄰居的性質． 例如,VEAA表示節點對的共同鄰居為“點鄰居”, 而共同鄰居的鄰居為“邊鄰居”, 也即計算與節點對均為鄰居的節點權重, 權重由該鄰居所關聯的超邊數量計算所得．kvV(z)、kvE(z)統計了節點z的鄰居節點個數和關聯超邊個數, 而keV(z)、keE(z)則統計了超邊z所包含的節點個數及超邊z所相交的超邊個數, 一般將kvE和keV看作節點和超邊的度[16]．

5)α階局部游走指標．α階局部游走指標定義在游走的基礎之上, 將節點對之間α階游走的數量作為分數． 在普通圖中, 形如vi0,vi1, …,viα-1這樣, 節點個數為α且相鄰節點在圖中互為鄰居的節點序列被稱之為一次α階游走． 擴展到超圖上[17], 超圖上的一次α階游走可定義為一個節點、 超邊交替出現的序列:

vi0,ei0,vi1,ei1, …,eiα-1,viα

(11)

其長度等于α, 即超邊出現的次數． 同樣, 序列中的相鄰元素在對應超圖中相互關聯． 節點對之間的α階游走數量, 即α階局部游走指標可表示為:

(12)

2.2 節點組的相似性

(13)

(14)

在社交領域, 式(14)所蘊含的思想直觀且有效: 若一組成員之間兩兩關系親密, 那么他們更有可能組成一個團體．

3 實驗

3.1 數據集

本文引入了9個真實超圖, 其領域覆蓋了食譜、 生物、 合作、 社交等方面． 各數據集的詳細統計信息見表1． 表1 由真實數據構建的超圖拓撲結構性質, 其中n,m, 〈kvE〉, 〈kvV〉, 〈|e|〉,d(H), |E2|, |E3|, |E4|, |E5|, 分別表示超圖的節點數, 超邊數, 節點超度的平均值, 節點一階鄰居數的平均值, 超邊大小的平均值, 密度[18], 超邊大小分別為2,3,4,5的超邊數量．

表1 各數據集的詳細統計信息和超圖拓撲結構性質

1)chuancai[1]: 菜譜數據集, 節點由食材構成, 一道川菜所需的一組食材構成一條超邊．

2)iAB_RBC_283,iJO1366[1]: 人類、 大腸桿菌代謝反應數據集． 超邊表示生物體內的代謝反應, 邊內的節點表示參與該反應的反應物．

3)CoreComplex: 本文構建了人類蛋白質相互作用數據集． 超邊代表人體內的蛋白質相互作用, 其包含的節點表示參與相互作用的蛋白質．

4)Cora-Co-citation,Cora-Co-reference[19]: 這兩個是引文數據集, 兩者的節點均表示機器學習論文． 在Cora-Co-citation超圖中, 超邊連接了被同一篇論文所引用的所有論文． 而在Cora-Co-reference中, 引用了同一篇論文的論文組成一條超邊．

5)DBLP-Co-authorship[20]: 這是一個計算機領域的論文合作數據集． 節點表示論文作者, 超邊連接了同一篇文章的所有作者．

6)cat-edge-music-blues-reviews[21]: 這是一個共評論數據集． 節點是亞馬遜購物網上的用戶, 在一個月內評論過相同布魯斯音樂產品的用戶組成一條超邊．

7)email-Eu[6, 22-23]: 線上社交數據集． 節點表示歐洲科研機構的電子郵箱, 超邊是一次郵件發送, 由郵件發送者和所有接收者所組成． 原始數據集中,email-Eu圖的超邊帶有時間戳, 這里將多個帶時間戳的超邊合并成一個超邊以靜態化原始數據集．

3.2 方法有效性驗證與超圖結構探索

算法1: 指標分數抽樣算法輸入: 超圖: H=, 指標: f, 節點組大小: b輸出: 任意節點組分數樣本集: Sarb, 超邊節點組分數樣本集: Sedge1. Sarb, Sedge←[], [];2. //獲得指定大小的超邊子集3. Eb←E.get_subset(b);4. for e in Eb do5. //從節點集中不放回抽取 |e| 個節點6. e =V.random_choice(|e|);7. Sarb.append(fH(e ));8. H' ← ;9. Sedge.append(fH'(e));10. end do Result: Sarb, Sedge

如何驗證第2章所列舉的鏈路預測方法在超圖環境下的有效性, 即指標f是否有能力將有潛力形成超邊的節點組和普通節點組區分開來． 一個自然的想法是: 隨機選取一條超邊, 同時從超圖節點集中隨機選取一個相同大小且無重復元素的節點組, 前者的f指標分數大于后者的概率越大, 指標f就有效．

3.2.1 分數分布分析

紅色為超邊節點組, 藍色為任意節點組．

圖2 各數據集CE分數分布的誤差棒圖

各數據集任意節點組的分數分布都極其類似, 其分數嚴重集中在低分值, 且均值方差幾乎沒有變化, 本文將其作為對照組來觀察同尺寸的超邊節點組分數分布． 在生物代謝圖上, 超邊節點組所有分數抽樣分布的變化都十分統一: 開始時節點組的分數基本集中于低分值上, 隨著節點數的增加, 其樣本分數的取值范圍逐漸增大且更加均勻地分布于各個區間． 觀察iAB_RBC_283的CE分數分布(圖1a), 該數據集的節點組CE分數表示節點組內各反應物平均共同參與的反應數． 可以看到, 2,3-超邊節點組的分數并未顯著大于同尺寸任意節點組(p>0.05), 而4-超邊節點組相當一部分超邊節點組的分數落在了10左右, 當節點組大小為5時, 超邊節點組的分數更均勻地落在了大分數上, 這表明多反應物的代謝反應顯著依賴于反應物兩兩之間的可反應程度, 且依賴程度隨代謝反應規模的增加而增加． 蛋白質代謝圖CoreComplex的各分數分布也有類似變化, 但并未表現得像前兩者顯著．

cat-edge-music-blues-reviews和DBLP-Co-authorship圖的超邊分別以“興趣”和“合作”關系將代表各用戶的相關節點相連． 這兩個圖的構成具有一定的相似性, 即由代表人的節點因為共同事件所聯系到一起,CE、CN分別表征了人們之間共同參與事件及共同參與者的數量． 而兩者超邊節點組分數分布也比較類似． 以cat-edge-music-blues-reviews圖為例, 超邊節點組在CN與CE上的分數分布表明: 節點組增大時, 雖然人們之間共同購買的產品并未顯著變化, 但用CN所統計的用戶的共同興趣者卻大大增加． 對于郵件收發圖email-Eu, 除2-超邊節點組外,email-Eu圖各方法分數分布在其余大小的節點組上幾乎沒有差別, 即均表現為均值類似的正態分布(圖1b)． 且各方法分數分布的均值總體先上升后保持平穩(略有上升或下降), 造成這種現象的一個解釋是“朋友在工作中產生”, 工作環境下的多次群發促成了日后代表親密關系的“一對一溝通”．

3.2.2 結構分析

總體上看, 由于超邊形成機理相同, 同一領域數據集的超邊節點組分數分布相似． 而不同數據集超邊節點組的各方法分數抽樣分布與均值方差變化呈現兩種趨勢, 要么沒有明顯變化, 要么初始時顯著上升． 這說明兩點: 第一, 各方法以多視角衡量了節點組之間節點對的親密程度． 第二, 超圖的“派系閉合假說”認為, 大關系在形成前, 其內部節點之間的聯系已經非常緊密． 基于此, 演化良好的超圖, 大尺度超邊節點組內部節點對的親密程度必然大于2-超邊節點組． 如若不然, 超邊節點組內的各個親密節點對更傾向于生成各種細密的2-超邊而沒有繼續擴張的趨勢． 甚至于在大部分數據集中, 2-超邊節點組和2-任意節點組之間分數分布幾乎沒有差異． 一般認為, 方法對超邊節點組和任意節點組的評分差異越大, 該方法預測能力越強． 上述情況會使得各方法很難將大小為2的超邊節點組和其他節點組區分開來從而導致誤判． 例如, 兩個引文圖Cora-Co-citation和Cora-Co-reference的所有方法的超邊節點組分數抽樣分布幾乎不受節點組大小的影響, 由于沒有明顯的演化規律和超邊節點組與任意節點組之間的分數差異不明顯, 所提出的方法對這兩個圖的鏈路預測效果將不會太理想． 總的來說, 通過抽樣及之后的分析, 在驗證了已抽樣方法的有效性——即它們的確能區分正負樣本的同時, 還發現在大多數情況下, 這種區分能力和節點組的大小有關, 即對大尺寸節點組的區分能力要遠遠強于小尺寸節點組． 由于真實超圖的超邊大小分布往往展現為冪律, 即小尺寸超邊占絕大多數, 因此, 對小尺寸、 甚至于2-節點組的無力是制約超鏈路預測方法性能的主要桎梏．

3.3 超鏈路預測

本文使用經典的二分類全局指標——接收者操作特征曲線下面積(AUC), 與局部指標——精確率(precision@k)和召回率(recall@k), 來評估第2節所列舉方法在各真實圖上的表現． 對單個數據集及特定指標的每次實驗, 采用五折交叉驗證的方式進行并重復若干次, 記錄每次實驗的交叉驗證平均值． 參數設置上,RWR的游走重啟概率c固定為0.15．

3.3.1 預測結果分析

預測結果的AUC評價展示在表2, 可以看到, 并未有任何一種方法在所有數據集上表現得最好, 這便是超鏈路預測環境下的“天下沒有午餐定律”[24]． 令人驚喜的莫過于CE, 該方法定義十分簡單, 卻在iAB_RBC_283、iJO1366、CoreComplex、Cora-Co-reference、DBLP-Co-authorship上表現優異． 將CE應用于這些數據集還能得到更加直觀的物理解釋, 例如, 對于合作圖DBLP-Co-authorship, 以CE方法的視角來看, 當一群作者相互之間合作過很多次時, 他們更有可能組團進行合作． 在數據集chuancai和email-Eu上,CN方法有著不錯的性能表現． 以email-Eu為例,CE方法計算了節點組內節點對之間的平均郵件收發事件數, 而CN方法計算了各自參與的郵件收發事件的其他共同參與者數量, 這表明, 有著更多工作伙伴關系的成員組之間更有可能產生郵件收發事件． 在普通圖的鏈路預測中, 奇數步局部游走指標在代謝圖上效果良好[25], 如果將CE看作“WK1”, 其效果在生物數據集上表現最優也就不足為奇了．JC作為CE的加權, 整體上前者的表現不如后者, 這也說明了鏈路預測方法的準確度并非與其計算復雜度呈正比． 對于在超圖環境中所擴展的4類AA方法, 若分別將VVAA、VEAA看作CN的改進,EVAA、EEAA看作CE的改進, 則這兩組方法內部之間的性能表現都十分接近． 且將點鄰居個數看作共同鄰居或共存超邊的權重時(VVAA之于CN、 EVAA之于CE), 整體有著更為明顯的性能提升, 這可能是由于點鄰居的數量相對于邊鄰居更多, 致使其權重的粒度更加細致從而有著很好的區分度．RWR在各數據集上的AUC表現似乎與鄰域方法、 特別是CE的表現正相反, 如前者在chuancai、cat-edge-music-blues-reviews、email-Eu上具有較優秀的預測效果, 而后者在除這些以外的其他數據集上有著較好的表現, 這表明在超鏈路預測任務中, 節點間的全局特征與局部特征都能提供有效信息． 同時本文對某一方法作用于所有數據集上的鏈路預測性能(AUC分數)與所有數據集的某一特定統計特征進行了相關性計算, 熱力圖見圖3． 總體上看, 超圖的“規模”越大, 其可預測性越好, 注意到〈kvE〉, 即所謂超圖的平均超度[26]與方法的預測性能之間呈顯著正相關, 這意味著該指標的大小直接展示了數據集可利用信息的多少．

橫坐標為方法, 縱坐標為統計特征, 該圖表征了真實數據集的統計特征與方法預測性能的相關性．

表2 各方法在不同數據集上的AUC對比

預測結果的精確率及召回率曲線分別展示在圖4、 圖5, 兩者的閾值上限取各數據集測試集樣本數量的一半． 不同于在AUC表現上的“百家爭鳴”, 精確率及召回率曲線上擴展的RWR方法在所有數據集上均取得了不錯的效果, 說明所引入超圖隨機游走方式的有效性, 即該過程確實能夠捕捉到超圖的拓撲結構． 局部游走指標(WK2、 WK3)效果普遍較差, 兩者的效果隨著閾值k的增加而快速下降, 這可能是因為在擴展局部游走時并未考慮“游走寬度”[17], 從而丟失了超邊的“高階特性”． 總的來說, 各方法雖然在性能上有所差異, 但正如本章第2節所言, 所擴展的方法在應用于超鏈路環境中時, 都能夠對正負樣本有效地進行預測．

圖4 精確率曲線

3.3.2 分組評估

延續抽樣時的方式, 在鏈路預測完成后, 對各方法應用于各數據集的表現分節點組大小進行評估, 評估結果見圖6． 與抽樣類似的是, 各方法2-節點組上的鏈路預測效果明顯低于其他節點組． 例如, 對于iAB_RBC_283, 2-超邊節點組的CE、 CN分數分布并未顯著大于任意節點組, 相對應, 很多方法對該數據集2-節點組進行鏈路預測的AUC效果甚至低于0.5． 對于大尺寸節點組, 各方法在整體上表現一致． 這一現象不僅與抽樣結果相吻合, 還從鏈路預測角度體現了大超邊內部節點的強鏈接程度． 與抽樣不同的是, AUC的效果評估曲線在絕大部分數據集上呈現絕對遞增的趨勢, 即隨著節點組節點數的增加, 各方法在數據集上的鏈路預測效果越來越好．

4 總結與展望

本文給出了將鏈路預測方法擴展到超圖環境的一般方式, 并基于此方式擴展了11種方法． 對所擴展的方法在真實超圖上進行分數抽樣并生成了對應的分數抽樣分布, 驗證了擴展方法的有效性, 發現了不同數據集的超邊演化規律, 認為演化良好的超圖其超邊內部的聯系強度隨節點數增加而增加, 由此推論超鏈接預測的主要難點在于對小尺寸超邊的預測． 然后, 將所擴展方法直接應用于真實超圖的超鏈路預測, 鏈路預測結果表明, 不同方法適用于不同的超圖環境, 但在局部精確率和召回率上, RWR有著更好的性能． 還根據節點組大小對預測效果分別進行評估, 結果表明在同一數據集內, 擴展方法的性能隨著節點組節點數的增加而增加．

在未來的研究中, 希望引入除式(13)外更多的擴展方式以達到性能的進一步提升． 對于具體的鏈路預測方法, 在普通鏈路預測指標的基礎上, 希望加入更多超圖獨有的高階性質, 如“寬度”[17]、 “高階隨機游走”[27]等, 另外, 更希望所設計的方法能有效地應對當前方法在預測小尺寸超邊上的無力． 最后, 關于超邊下采樣算法的討論正如火如荼[2, 28-29], 期待在未來, 使用最新的下采樣算法所得到更加“仿真”的負樣本能更好地評估方法的性能．