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

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

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

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

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

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

1 問題定義

1.1 超圖

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

1.2 超鏈路預(yù)測

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

1.3 下采樣

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

2 方法

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

2.1 節(jié)點(diǎn)對的相似性

2.1.1 帶重啟的隨機(jī)游走指標(biāo)

帶重啟的隨機(jī)游走是鏈路預(yù)測里的一個經(jīng)典方法, 該方法基于圖上的帶重啟隨機(jī)游走, 并將節(jié)點(diǎn)對之間的平穩(wěn)互達(dá)概率作為鏈路預(yù)測分?jǐn)?shù)[11]． 為將上述指標(biāo)擴(kuò)展到超圖, 需要先定義超圖上的隨機(jī)游走． 假設(shè)游走者在時刻t(t=0, 1, …)位于節(jié)點(diǎn)vi, 考慮一種無偏的情況, 游走者首先隨機(jī)游走到包含該節(jié)點(diǎn)的任意一條超邊上, 并在t+1時刻隨機(jī)游走到關(guān)聯(lián)該超邊的節(jié)點(diǎn)vj． 這里定義的超圖隨機(jī)游走可簡單表述為上述過程的迭代． 該游走者在t到t+1期間, 從節(jié)點(diǎn)vi轉(zhuǎn)移到節(jié)點(diǎn)vj的概率為:

(1)

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

(2)

DvE∈Rn×n,DeV∈Rm×m, 均為對角陣, 對角線元素分別為各節(jié)點(diǎn)所關(guān)聯(lián)的超邊數(shù)和各超邊所包含的節(jié)點(diǎn)數(shù)．

(3)

需要注意的是, 并未限制在每一步隨機(jī)游走的過程中游走者不能跳回上一步節(jié)點(diǎn), 這是為了使?fàn)顟B(tài)轉(zhuǎn)移矩陣P能分解為式(2)所示的矩陣運(yùn)算． 在此基礎(chǔ)上添加重啟機(jī)制, 即在每步游走時, 有一定可能跳回到初始節(jié)點(diǎn)vi, 跳回概率為c(0

(4)

(5)

因此, 可以定義節(jié)點(diǎn)對vi,vj的平穩(wěn)解RWR分?jǐn)?shù):

(6)

式(6)將隨機(jī)游走者從初始節(jié)點(diǎn)vi出發(fā)并到達(dá)vj的平穩(wěn)概率作為節(jié)點(diǎn)對的相似性分?jǐn)?shù), 其大小表征了從vi到vj的可達(dá)性, 內(nèi)在編碼了超圖的拓?fù)浣Y(jié)構(gòu)． 很明顯, 該分?jǐn)?shù)并不具有對稱性, 即RWR(vi,vj)≠RWR(vj,vi)．

2.1.2 基礎(chǔ)方法擴(kuò)展

受普通圖鏈路預(yù)測方法和已有超圖研究的啟發(fā), 本文設(shè)計(jì)了一些超圖上刻畫節(jié)點(diǎn)對相似性的方法, 以下列舉這些基礎(chǔ)方法基于節(jié)點(diǎn)對輸入的定義．

1) 共同鄰居指標(biāo)(Common Neighbors, 簡稱CN)． 共同鄰居指標(biāo)是傳統(tǒng)鏈路預(yù)測中最簡單也是最經(jīng)典的指標(biāo)． 該指標(biāo)基于“共同鄰居越多的節(jié)點(diǎn)對越相似”這一思想, 計(jì)算公式為[13]:

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

(7)

式中Nvi是節(jié)點(diǎn)vi的鄰居集合, 在超圖中, 它是指與節(jié)點(diǎn)vi共存于同一超邊內(nèi)的其他所有節(jié)點(diǎn)．

2) 共存超邊指標(biāo)(Coexist Edge, 簡稱CE)． 不同于普通圖, 在超圖環(huán)境中, 由于邊大小的任意性, 兩個節(jié)點(diǎn)往往會被多個超邊同時包含． 統(tǒng)計(jì)包含節(jié)點(diǎn)對的超邊個數(shù)便得到共存超邊指標(biāo), 其計(jì)算公式為:

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

(8)

式中Evi是包含節(jié)點(diǎn)vi的超邊集合．

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

(9)

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

(10)

指標(biāo)名稱的第一個和第二個字母分別代表共同鄰居和共同鄰居的鄰居的性質(zhì)． 例如,VEAA表示節(jié)點(diǎn)對的共同鄰居為“點(diǎn)鄰居”, 而共同鄰居的鄰居為“邊鄰居”, 也即計(jì)算與節(jié)點(diǎn)對均為鄰居的節(jié)點(diǎn)權(quán)重, 權(quán)重由該鄰居所關(guān)聯(lián)的超邊數(shù)量計(jì)算所得．kvV(z)、kvE(z)統(tǒng)計(jì)了節(jié)點(diǎn)z的鄰居節(jié)點(diǎn)個數(shù)和關(guān)聯(lián)超邊個數(shù), 而keV(z)、keE(z)則統(tǒng)計(jì)了超邊z所包含的節(jié)點(diǎn)個數(shù)及超邊z所相交的超邊個數(shù), 一般將kvE和keV看作節(jié)點(diǎn)和超邊的度[16]．

5)α階局部游走指標(biāo)．α階局部游走指標(biāo)定義在游走的基礎(chǔ)之上, 將節(jié)點(diǎn)對之間α階游走的數(shù)量作為分?jǐn)?shù)． 在普通圖中, 形如vi0,vi1, …,viα-1這樣, 節(jié)點(diǎn)個數(shù)為α且相鄰節(jié)點(diǎn)在圖中互為鄰居的節(jié)點(diǎn)序列被稱之為一次α階游走． 擴(kuò)展到超圖上[17], 超圖上的一次α階游走可定義為一個節(jié)點(diǎn)、 超邊交替出現(xiàn)的序列:

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

(11)

其長度等于α, 即超邊出現(xiàn)的次數(shù)． 同樣, 序列中的相鄰元素在對應(yīng)超圖中相互關(guān)聯(lián)． 節(jié)點(diǎn)對之間的α階游走數(shù)量, 即α階局部游走指標(biāo)可表示為:

(12)

2.2 節(jié)點(diǎn)組的相似性

(13)

(14)

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

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

3.1 數(shù)據(jù)集

本文引入了9個真實(shí)超圖, 其領(lǐng)域覆蓋了食譜、 生物、 合作、 社交等方面． 各數(shù)據(jù)集的詳細(xì)統(tǒng)計(jì)信息見表1． 表1 由真實(shí)數(shù)據(jù)構(gòu)建的超圖拓?fù)浣Y(jié)構(gòu)性質(zhì), 其中n,m, 〈kvE〉, 〈kvV〉, 〈|e|〉,d(H), |E2|, |E3|, |E4|, |E5|, 分別表示超圖的節(jié)點(diǎn)數(shù), 超邊數(shù), 節(jié)點(diǎn)超度的平均值, 節(jié)點(diǎn)一階鄰居數(shù)的平均值, 超邊大小的平均值, 密度[18], 超邊大小分別為2,3,4,5的超邊數(shù)量．

表1 各數(shù)據(jù)集的詳細(xì)統(tǒng)計(jì)信息和超圖拓?fù)浣Y(jié)構(gòu)性質(zhì)

1)chuancai[1]: 菜譜數(shù)據(jù)集, 節(jié)點(diǎn)由食材構(gòu)成, 一道川菜所需的一組食材構(gòu)成一條超邊．

2)iAB_RBC_283,iJO1366[1]: 人類、 大腸桿菌代謝反應(yīng)數(shù)據(jù)集． 超邊表示生物體內(nèi)的代謝反應(yīng), 邊內(nèi)的節(jié)點(diǎn)表示參與該反應(yīng)的反應(yīng)物．

3)CoreComplex: 本文構(gòu)建了人類蛋白質(zhì)相互作用數(shù)據(jù)集． 超邊代表人體內(nèi)的蛋白質(zhì)相互作用, 其包含的節(jié)點(diǎn)表示參與相互作用的蛋白質(zhì)．

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

5)DBLP-Co-authorship[20]: 這是一個計(jì)算機(jī)領(lǐng)域的論文合作數(shù)據(jù)集． 節(jié)點(diǎn)表示論文作者, 超邊連接了同一篇文章的所有作者．

6)cat-edge-music-blues-reviews[21]: 這是一個共評論數(shù)據(jù)集． 節(jié)點(diǎn)是亞馬遜購物網(wǎng)上的用戶, 在一個月內(nèi)評論過相同布魯斯音樂產(chǎn)品的用戶組成一條超邊．

7)email-Eu[6, 22-23]: 線上社交數(shù)據(jù)集． 節(jié)點(diǎn)表示歐洲科研機(jī)構(gòu)的電子郵箱, 超邊是一次郵件發(fā)送, 由郵件發(fā)送者和所有接收者所組成． 原始數(shù)據(jù)集中,email-Eu圖的超邊帶有時間戳, 這里將多個帶時間戳的超邊合并成一個超邊以靜態(tài)化原始數(shù)據(jù)集．

3.2 方法有效性驗(yàn)證與超圖結(jié)構(gòu)探索

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

如何驗(yàn)證第2章所列舉的鏈路預(yù)測方法在超圖環(huán)境下的有效性, 即指標(biāo)f是否有能力將有潛力形成超邊的節(jié)點(diǎn)組和普通節(jié)點(diǎn)組區(qū)分開來． 一個自然的想法是: 隨機(jī)選取一條超邊, 同時從超圖節(jié)點(diǎn)集中隨機(jī)選取一個相同大小且無重復(fù)元素的節(jié)點(diǎn)組, 前者的f指標(biāo)分?jǐn)?shù)大于后者的概率越大, 指標(biāo)f就有效．

3.2.1 分?jǐn)?shù)分布分析

紅色為超邊節(jié)點(diǎn)組, 藍(lán)色為任意節(jié)點(diǎn)組．

圖2 各數(shù)據(jù)集CE分?jǐn)?shù)分布的誤差棒圖

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

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

3.2.2 結(jié)構(gòu)分析

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

3.3 超鏈路預(yù)測

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

3.3.1 預(yù)測結(jié)果分析

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

橫坐標(biāo)為方法, 縱坐標(biāo)為統(tǒng)計(jì)特征, 該圖表征了真實(shí)數(shù)據(jù)集的統(tǒng)計(jì)特征與方法預(yù)測性能的相關(guān)性．

表2 各方法在不同數(shù)據(jù)集上的AUC對比

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

圖4 精確率曲線

3.3.2 分組評估

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

4 總結(jié)與展望

本文給出了將鏈路預(yù)測方法擴(kuò)展到超圖環(huán)境的一般方式, 并基于此方式擴(kuò)展了11種方法． 對所擴(kuò)展的方法在真實(shí)超圖上進(jìn)行分?jǐn)?shù)抽樣并生成了對應(yīng)的分?jǐn)?shù)抽樣分布, 驗(yàn)證了擴(kuò)展方法的有效性, 發(fā)現(xiàn)了不同數(shù)據(jù)集的超邊演化規(guī)律, 認(rèn)為演化良好的超圖其超邊內(nèi)部的聯(lián)系強(qiáng)度隨節(jié)點(diǎn)數(shù)增加而增加, 由此推論超鏈接預(yù)測的主要難點(diǎn)在于對小尺寸超邊的預(yù)測． 然后, 將所擴(kuò)展方法直接應(yīng)用于真實(shí)超圖的超鏈路預(yù)測, 鏈路預(yù)測結(jié)果表明, 不同方法適用于不同的超圖環(huán)境, 但在局部精確率和召回率上, RWR有著更好的性能． 還根據(jù)節(jié)點(diǎn)組大小對預(yù)測效果分別進(jìn)行評估, 結(jié)果表明在同一數(shù)據(jù)集內(nèi), 擴(kuò)展方法的性能隨著節(jié)點(diǎn)組節(jié)點(diǎn)數(shù)的增加而增加．

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