張雁操，趙宇海，史 嵐

東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽110169

鏈接預(yù)測是復(fù)雜網(wǎng)絡(luò)研究工作中重要研究方向之一，是指通過已知的部分網(wǎng)絡(luò)結(jié)構(gòu)預(yù)測網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)是否存在鏈接。這些鏈接可能是缺失的或未被觀察到的，也可能是未來網(wǎng)絡(luò)演變過程中可能產(chǎn)生的。因此鏈接預(yù)測可以幫助人們更好地補(bǔ)全網(wǎng)絡(luò)或理解網(wǎng)絡(luò)結(jié)構(gòu)生成及演化的機(jī)制。

作為一個(gè)典型的交叉學(xué)科，鏈接預(yù)測已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域重要的研究方向之一，其應(yīng)用場景涉及許多領(lǐng)域。例如，在生物領(lǐng)域，可用于預(yù)測蛋白質(zhì)之間的相互作用，在Yeast網(wǎng)絡(luò)中，大部分細(xì)胞間相互作用尚不為人知；在社交領(lǐng)域，可用于預(yù)測社交活動(dòng)的產(chǎn)生或消失；在交通領(lǐng)域，可以用于交通線路規(guī)劃、城市道路規(guī)劃；在推薦領(lǐng)域，可以進(jìn)行商品推薦、好友推薦等。

目前有一類簡單的鏈接預(yù)測方法是基于相似函數(shù)的鏈接預(yù)測，也稱作啟發(fā)式方法。該類方法假設(shè)：節(jié)點(diǎn)傾向于與其相似的節(jié)點(diǎn)形成鏈接。通過定義相似性函數(shù)計(jì)算兩個(gè)節(jié)點(diǎn)的相似性，然后將節(jié)點(diǎn)對(duì)的相似性得分按遞減順序排列，位于排序頂部的鏈接更有可能為丟失鏈接或者未來可能相連的鏈接。

基于計(jì)算相似性所需節(jié)點(diǎn)的距離可將啟發(fā)式方法分為三種：一階、二階及高階。一階啟發(fā)式僅僅涉及兩個(gè)目標(biāo)鏈接節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)，例如共同鄰居（common neighbors，CN）、Jaccard 指數(shù)（JA）、優(yōu)先連接指數(shù)（preferential attachment index，PA）等。二階啟發(fā)式是通過目標(biāo)鏈接節(jié)點(diǎn)的兩跳鄰居計(jì)算相似性的，例如Adamic-Adar 指數(shù)（AA）、資源分配指數(shù)（resource allocation index，RA）等。還有需要更大范圍甚至是整個(gè)網(wǎng)絡(luò)的相似性度量方法，稱為高階啟發(fā)式，例如PageRank（PR）、Katz指數(shù)（Katz index，KI）、SimRank（SR）、隨機(jī)游走（random walks，RW）等。盡管這類方法實(shí)踐效果良好，但是對(duì)于鏈接的存在性有很強(qiáng)的人為假設(shè)。對(duì)于不同類型的數(shù)據(jù)集，相似性函數(shù)往往有著不同的定義。例如，CN 假設(shè)若兩節(jié)點(diǎn)有更多的共同鄰居，則它們更有可能相連，這種假設(shè)在社交網(wǎng)絡(luò)中可能是正確的，但是在蛋白質(zhì)交互網(wǎng)絡(luò)（protein-protein interaction networks，PPI）中被證明是無效的；JA 通過計(jì)算兩個(gè)節(jié)點(diǎn)的完整鄰居集合中共同鄰居的比例度量節(jié)點(diǎn)相似性；PA 假設(shè)兩個(gè)節(jié)點(diǎn)之間形成鏈接的概率隨著節(jié)點(diǎn)度的增加而增加。

另一類近年來被用于鏈接預(yù)測任務(wù)的是節(jié)點(diǎn)嵌入算法。本文按節(jié)點(diǎn)嵌入算法獲取向量表示的過程將其分為兩類：第一類是通過保留節(jié)點(diǎn)的局部鄰域信息，用于特征提取、節(jié)點(diǎn)分類、鏈接預(yù)測等任務(wù)的算法，例如DeepWalk、LINE、N2V（node2vec）等。第二類算法從全局角度挖掘每個(gè)節(jié)點(diǎn)的潛在特征信息，通過保留節(jié)點(diǎn)的結(jié)構(gòu)特征相似性、社區(qū)信息、全局排序信息等生成節(jié)點(diǎn)嵌入向量，例如struc2vec、M-NMF（modularized nonnegative matrix factorization）、NECS（network embedding with community structural information）、PRUNE（proximity and ranking-preserving unsupervised network embedding）等。

node2vec 節(jié)點(diǎn)嵌入算法第一次將鏈接預(yù)測作為下游任務(wù)評(píng)估算法性能。它從廣度優(yōu)先和深度優(yōu)先兩個(gè)角度，使用有偏隨機(jī)游走最大限度地保留節(jié)點(diǎn)的鄰域信息，并利用低維向量表示進(jìn)行鏈接預(yù)測等任務(wù)。PRUNE 設(shè)計(jì)了保留多種特征信息的目標(biāo)函數(shù)，使用孿生神經(jīng)網(wǎng)絡(luò)進(jìn)行無監(jiān)督學(xué)習(xí)，將得到的向量表示用于鏈接預(yù)測等任務(wù)。另外由網(wǎng)絡(luò)的同質(zhì)性原理，同一社區(qū)中的節(jié)點(diǎn)比不同社區(qū)間的節(jié)點(diǎn)更相似。M-NMF 和NECS 節(jié)點(diǎn)嵌入算法利用矩陣分解，以學(xué)習(xí)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)、保留節(jié)點(diǎn)的社區(qū)信息為目的，在鏈接預(yù)測任務(wù)中取得了良好的效果。但是節(jié)點(diǎn)嵌入算法不具有任務(wù)特定性——不是針對(duì)鏈接預(yù)測任務(wù)設(shè)計(jì)的，被用于特征提取、節(jié)點(diǎn)分類、鏈接預(yù)測等多個(gè)下游任務(wù)，無法捕獲對(duì)鏈接預(yù)測最有效的信息。

在監(jiān)督學(xué)習(xí)中幾乎所有的分類器都可以用于鏈接預(yù)測。Lichtenwalter 等人提到將多種分類器用于鏈接預(yù)測，包括決策樹、支持向量機(jī)、近鄰算法、多層感知器、樸素貝葉斯等。Cukierski等人利用隨機(jī)森林取得了良好的結(jié)果。針對(duì)啟發(fā)式方法和節(jié)點(diǎn)嵌入算法的缺陷，Zhang 和Chen 首次提出將啟發(fā)式看作預(yù)定義的圖啟發(fā)式特征，利用神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)合適的啟發(fā)式進(jìn)行鏈接預(yù)測，并據(jù)此提出了WLNM（Weisfeiler-Lehman neural machine）算法。首先提取包含指定節(jié)點(diǎn)數(shù)的局部子圖，然后利用啟發(fā)于Weisfeiler-Lehman算法提出的PALETTE-WL標(biāo)記方法獲得子圖節(jié)點(diǎn)標(biāo)記，最后根據(jù)節(jié)點(diǎn)標(biāo)記重構(gòu)子圖鄰接矩陣，輸入到全連接神經(jīng)網(wǎng)絡(luò)中訓(xùn)練。進(jìn)一步的，Zhang和Chen提出了目前表現(xiàn)最優(yōu)異的鏈接預(yù)測算法SEAL（learning from subgraphs，embeddings and attributes for link prediction），其中使用的圖神經(jīng)網(wǎng)絡(luò)DGCNN（deep graph convolutional neural network），具有更好的圖特征學(xué)習(xí)能力，且該算法允許從節(jié)點(diǎn)特征中學(xué)習(xí)，包括DRNL（double-radius node labeling）節(jié)點(diǎn)標(biāo)記和node2vec 節(jié)點(diǎn)嵌入特征。但是SEAL 算法具有以下幾個(gè)問題：

（1）局部性：對(duì)于目標(biāo)鏈接，該方法通?？紤]一跳或兩跳局部子圖，利用的特征如局部子圖的鄰接矩陣、局部子圖的DRNL 獨(dú)熱編碼標(biāo)記矩陣和node2vec向量表示等。通過神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)，只能獲得低階啟發(fā)式特征。

（2）特征無效性：由于目標(biāo)鏈接的局部子圖可能是不連通的，會(huì)導(dǎo)致DRNL 節(jié)點(diǎn)標(biāo)記矩陣具有較強(qiáng)的特征無效性（見1.1 節(jié)）。

（3）節(jié)點(diǎn)無偏性：在圖卷積的過程中，未考慮到不同節(jié)點(diǎn)對(duì)于鏈接存在性的影響應(yīng)該不同，因此對(duì)于局部子圖中節(jié)點(diǎn)信息的聚合過程應(yīng)該是有偏的（見1.1 節(jié)）。

針對(duì)SEAL 算法存在的問題，本文提出了融合圖注意力的多特征鏈接預(yù)測算法ADNSL（learning from double-radius node labeling，node2vec and struc2vec for link prediction with attention mechanism），主要貢獻(xiàn)如下：

（1）針對(duì)上述問題（1），提出了一種支持不同類型特征輸入的鏈接預(yù)測算法。在局部特征生成模塊中，該模型將局部角度的節(jié)點(diǎn)嵌入特征輸入到圖神經(jīng)網(wǎng)絡(luò)，學(xué)習(xí)預(yù)定義的啟發(fā)式特征。在全局特征提取模塊中，利用struc2vec 從全局角度提取節(jié)點(diǎn)的結(jié)構(gòu)特征，通過重構(gòu)圖上的隨機(jī)游走生成游走序列，并得到節(jié)點(diǎn)嵌入向量，進(jìn)而提升鏈接預(yù)測性能。

（2）針對(duì)上述問題（2）和（3），在局部特征生成模塊中提出雙向無參注意力圖卷積，可以有效彌補(bǔ)特征無效性和節(jié)點(diǎn)無偏性（見1.1 節(jié)）。

（3）為了降低模型復(fù)雜度，在全局特征提取模塊中提出了有效的迭代公式，將struc2vec的重構(gòu)多層圖轉(zhuǎn)化為聚合圖，在保留結(jié)構(gòu)特征相似性的同時(shí)，可以有效減少I/O 時(shí)間、內(nèi)存消耗及磁盤消耗（見1.2 節(jié)）。

（4）在八個(gè)不同領(lǐng)域公開經(jīng)典數(shù)據(jù)集上的實(shí)驗(yàn)表明，ADNSL 相比于多個(gè)基準(zhǔn)模型，ACC 和AUC 值有十分明顯的提升。對(duì)于平均度較小的數(shù)據(jù)集NS、Power 和Router，AUC可有10個(gè)百分點(diǎn)以上的提升（見2.5 節(jié)）。

1 融合圖注意力的多特征鏈接預(yù)測算法

本章將詳細(xì)介紹融合圖注意力的多特征鏈接預(yù)測算法模型ADNSL。首先，針對(duì)SEAL 算法的局部性，給出了ADNSL 的整體框架圖（圖1）；然后，給出了局部特征生成模塊的介紹，針對(duì)SEAL 的特征無效性和節(jié)點(diǎn)無偏性，給出了雙向無參注意力圖卷積過程；接著，介紹了全局特征提取模塊，并針對(duì)重構(gòu)多層圖的特性，提出迭代公式用于生成聚合圖。

圖1 ADNSL 框架Fig.1 Framework of ADNSL

如圖1 所示，針對(duì)SEAL 算法的局部性，ADNSL框架主體分為兩部分，上方為局部特征生成模塊，下方為全局特征提取模塊。局部特征生成模塊利用局部子圖的DRNL 節(jié)點(diǎn)標(biāo)記矩陣和node2vec 節(jié)點(diǎn)嵌入矩陣作為特征輸入，經(jīng)過多次圖注意力卷積得到多感受野的節(jié)點(diǎn)特征向量，然后將每一層圖卷積的輸出結(jié)果拼接，并通過排序池化層和一維卷積層，生成局部特征向量，詳細(xì)過程在圖2 中展示。全局特征提取模塊使用全局角度struc2vec 方法提取節(jié)點(diǎn)嵌入向量，根據(jù)多跳度序列計(jì)算輸入圖中節(jié)點(diǎn)間的結(jié)構(gòu)距離，并利用結(jié)構(gòu)距離重構(gòu)原圖生成多層圖，再利用迭代公式得到聚合圖，通過聚合圖上的隨機(jī)游走，提取目標(biāo)節(jié)點(diǎn)的全局特征向量，詳細(xì)過程在圖3 中展示。之后，將兩個(gè)模塊得到的特征表示融合，輸入到全連接層預(yù)測鏈接是否存在。整個(gè)框架通過有效的多特征融合，可以合理地利用節(jié)點(diǎn)嵌入特征，明顯地提升鏈接預(yù)測的性能。

圖2 局部特征生成模塊Fig.2 Local feature generation module

圖3 DRNL 特征無效性Fig.3 Ineffectivity of DRNL features

1.1 局部特征生成模塊

給定無向無權(quán)圖=(,)，=||，表示節(jié)點(diǎn)的集合，表示邊的集合，表示節(jié)點(diǎn)個(gè)數(shù)。對(duì)圖，有鄰接矩陣和特征矩陣∈R，其中由DRNL節(jié)點(diǎn)標(biāo)記矩陣和node2vec 節(jié)點(diǎn)嵌入矩陣拼接而成。如圖2 所示，利用圖注意力卷積生成局部特征。

其 中，=d+d，=min(d,d)，d=(,) 和d=(,)分別表示節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)和的距離，(/2)和(%2)分別是除以2 的整數(shù)商和余數(shù)。特別地，f()=f()=1；若(,)=∞或(,)=∞，則 f()=0 。需要注意的是，在計(jì)算距離(,)和(,)時(shí)，路徑不可通過目標(biāo)節(jié)點(diǎn)和。

式（1）所示的DRNL 節(jié)點(diǎn)標(biāo)記哈希函數(shù)具有如下特性：對(duì)于局部子圖中的任意兩個(gè)節(jié)點(diǎn)、及目標(biāo)節(jié)點(diǎn)、，當(dāng)(,)+(,)≠(,)+(,)時(shí)，(,)+(,)＜(,)+(,)?f()＜f()；當(dāng)(,)+(,)=(,)+(,) 時(shí)，(,)(,)＜(,)(,)?f()＜f() 。因此子圖中的節(jié)點(diǎn)到兩個(gè)目標(biāo)節(jié)點(diǎn)的距離之和越小，則標(biāo)記值越??；子圖中的節(jié)點(diǎn)到兩個(gè)目標(biāo)節(jié)點(diǎn)的距離之和相等時(shí)，距離之積越小，標(biāo)記值越小。

利用式（1）計(jì)算得到的節(jié)點(diǎn)標(biāo)記如圖3 所示。菱形節(jié)點(diǎn)表示目標(biāo)節(jié)點(diǎn)和。除了標(biāo)記為0 的節(jié)點(diǎn)外，局部子圖中標(biāo)記越小的節(jié)點(diǎn)，對(duì)于目標(biāo)鏈接的存在性越重要。由于計(jì)算距離時(shí)，路徑不可通過目標(biāo)節(jié)點(diǎn)，局部子圖中可能含有大量標(biāo)記為0 的節(jié)點(diǎn)。這些節(jié)點(diǎn)的標(biāo)記值對(duì)于鏈接的存在性是無意義的，因此DRNL 節(jié)點(diǎn)標(biāo)記矩陣具有較強(qiáng)的特征無效性。

啟發(fā)于圖注意力網(wǎng)絡(luò)（graph attention networks，GAT），在上述兩個(gè)問題的基礎(chǔ)上，提出融合注意力機(jī)制的圖卷積過程，可以更加注重有效的特征信息，更好地捕捉節(jié)點(diǎn)特征的差異性。對(duì)于圖中的任意兩相鄰節(jié)點(diǎn)、，在+1 層，有注意力系數(shù)：

其中，＜*,*＞表示向量的內(nèi)積。本文ADNSL 中注意力系數(shù)的計(jì)算過程與GAT 有兩點(diǎn)不同：（1）特征矩陣H是子圖中的節(jié)點(diǎn)聚合鄰居節(jié)點(diǎn)的特征后得到的，在計(jì)算某兩個(gè)節(jié)點(diǎn)的注意力系數(shù)時(shí)，除了考慮這兩個(gè)節(jié)點(diǎn)的特征外，還考慮了它們所有鄰居節(jié)點(diǎn)的特征，這顯然更合理。（2）在得到特征矩陣H后，采用式（3）計(jì)算注意力系數(shù)，該過程不涉及可訓(xùn)練參數(shù)，可以有效降低計(jì)算復(fù)雜度。

在歸一化前，圖注意力權(quán)重見圖4。隨著圖注意力卷積層數(shù)的加深，節(jié)點(diǎn)和節(jié)點(diǎn)對(duì)于、之間鏈接存在性的影響逐漸增大，而節(jié)點(diǎn)對(duì)于鏈接的存在性的影響降到最小。在此基礎(chǔ)上，對(duì)應(yīng)于圖2 中排序池化層所展示的，可以更果斷地將節(jié)點(diǎn)的特征向量去除。

圖4 softmax 前圖注意力權(quán)重示意圖Fig.4 Graph attention weights before softmax

在得到歸一化后的雙向注意力權(quán)重后，第+1層的輸出為：

1.2 全局特征提取模塊

本模塊利用struc2vec 節(jié)點(diǎn)嵌入算法提取結(jié)構(gòu)特征。該算法利用圖中每對(duì)節(jié)點(diǎn)不同鄰域范圍的結(jié)構(gòu)距離構(gòu)建多層圖，并利用迭代公式將多層圖轉(zhuǎn)化為聚合圖，然后利用隨機(jī)游走和SkipGram 生成節(jié)點(diǎn)序列和節(jié)點(diǎn)嵌入向量。具體過程見圖5，可分為四步。

圖5 全局特征提取模塊Fig.5 Global feature extraction module

（1）度量結(jié)構(gòu)相似性

度量結(jié)構(gòu)相似性時(shí)不使用節(jié)點(diǎn)或邊的屬性信息，也不基于任何特定的相似性度量。此處的相似性僅僅依賴于節(jié)點(diǎn)的度，這種相似性是分層的，隨著鄰域范圍不斷增加，可以捕獲更精確的結(jié)構(gòu)特征相似性。對(duì)于兩個(gè)節(jié)點(diǎn)，如果它們的度相同，它們是結(jié)構(gòu)相似的，而若它們的鄰居具有相同的度序列，則它們更加結(jié)構(gòu)相似。

對(duì)于圖=(,)，=||表示圖中的節(jié)點(diǎn)數(shù)。若有圖中的節(jié)點(diǎn)，R()定義為的第跳點(diǎn)集。對(duì)于?，()表示中節(jié)點(diǎn)的有序度序列。令為圖的直徑，指圖中任意兩個(gè)節(jié)點(diǎn)間距離的最大值。對(duì)于圖中任意兩節(jié)點(diǎn)、的跳子圖，=0,1,…,，考慮它們?cè)趯拥慕Y(jié)構(gòu)距離定義為：

其中，=0，且|R()|,|R()|＞0，度量了兩個(gè)有序度序列的距離。注意只有當(dāng)節(jié)點(diǎn)和均有跳鄰居時(shí)，f(,)才有意義，當(dāng)或不存在跳鄰居時(shí)，與在多層圖的第層無邊相連，見式（9）。

采用動(dòng)態(tài)時(shí)間歸整（dynamic time warping，DTW）算法計(jì)算度序列的距離。對(duì)于兩個(gè)有序度序列、，匹配它們中的每一個(gè)元素、，每一對(duì)元素的距離定義為：

和的距離即為所有元素對(duì)距離之和。

另外，為了降低DTW 算法計(jì)算結(jié)構(gòu)距離的時(shí)間復(fù)雜度，令′、′分別為度序列、的壓縮形式，=(,)，=(,)分別是′、′中的元組，元組中和表示度值，和對(duì)應(yīng)和出現(xiàn)的次數(shù)。式（7）調(diào)整為：

（2）構(gòu)建多層圖

利用結(jié)構(gòu)距離構(gòu)建多層圖。由于多層圖內(nèi)存消耗較大，為了降低復(fù)雜度，在度量結(jié)構(gòu)相似性時(shí)沒有必要計(jì)算每個(gè)節(jié)點(diǎn)與其他-1 個(gè)節(jié)點(diǎn)的相似性，即多層圖的每一層并非完全圖。將原始圖中的節(jié)點(diǎn)度按序排列，對(duì)每個(gè)節(jié)點(diǎn)，在度序列前后各選取lb個(gè)節(jié)點(diǎn)與其連接。另外當(dāng)多層圖的層數(shù)接近時(shí)，跳鄰居數(shù)較少，度序列的長度相對(duì)較短，f(,)與f(,)差別不大。故對(duì)于層數(shù)，選取一個(gè)固定值′＜，能有效降低構(gòu)建多層圖的計(jì)算和內(nèi)存需求。

此時(shí)構(gòu)建的多層圖是層內(nèi)無向加權(quán)層間有向加權(quán)的。式（9）表示層內(nèi)權(quán)重，在第層，兩個(gè)點(diǎn)、的結(jié)構(gòu)距離越遠(yuǎn)，權(quán)重越小。只有當(dāng)f(,)有意義時(shí)，、在層才有邊相連。

（3）生成節(jié)點(diǎn)序列

進(jìn)一步地，為了降低I/O 時(shí)間、內(nèi)存消耗以及磁盤消耗，利用式（12）的層間權(quán)重將多層圖中的信息匯聚到同一層，生成聚合圖。為此要求每一層節(jié)點(diǎn)間的連接情況完全相同。

在多層圖中，每個(gè)節(jié)點(diǎn)與2×lb個(gè)節(jié)點(diǎn)相連，但是根據(jù)式（6）和式（9）可知，每一層的連接情況可能不同，因?yàn)楫?dāng)或在跳無鄰居時(shí)，f(,)無意義，此時(shí),在層無邊相連。為了使每一層的連接情況完全相同，對(duì)于在第0 層有邊相連的節(jié)點(diǎn)對(duì),，若它們?cè)冢? 層無邊相連，則令w(,)=0。

在保證每層節(jié)點(diǎn)間連接情況相同后，提出迭代公式（14），利用多層圖中的信息生成聚合圖。

根據(jù)式（6）、式（9）和式（11）可知，在低層結(jié)構(gòu)特征不相似的節(jié)點(diǎn)對(duì)在高層一定不相似；兩個(gè)節(jié)點(diǎn)結(jié)構(gòu)特征越相似，節(jié)點(diǎn)間邊的權(quán)值越大，轉(zhuǎn)移概率越大。因此，如圖6 所示，對(duì)于節(jié)點(diǎn)(,)在信息聚合過程中有三種情形：

圖6 聚合圖Fig.6 Agglomerative graph

若節(jié)點(diǎn)對(duì)(,)在層結(jié)構(gòu)特征不相似，則在+1 層一定不相似，由多次小權(quán)值累積，可以得到更加精細(xì)的權(quán)重。

若節(jié)點(diǎn)對(duì)(,)在層結(jié)構(gòu)特征相似，在+1 層也相似，低層的權(quán)重匯聚到高層降低了其影響力，傾向于依賴高層權(quán)重進(jìn)行隨機(jī)游走。

若節(jié)點(diǎn)對(duì)(,)在層結(jié)構(gòu)特征相似，在+1 層不相似，通過迭代公式減小從層獲得的權(quán)值，傾向于利用+1 層的權(quán)重與情形2 區(qū)分。

綜上，利用式（14）生成的聚合圖具有三個(gè)顯而易見的特性：低層的權(quán)重匯聚到高層降低了其影響力；結(jié)構(gòu)特征越相似的節(jié)點(diǎn)對(duì)之間的權(quán)重越大；聚合圖上的有偏隨機(jī)游走不存在層的切換，相較于多層圖，聚合圖的內(nèi)存和磁盤占用更少。

（4）生成節(jié)點(diǎn)嵌入向量

在聚合圖上通過有偏隨機(jī)游走得到節(jié)點(diǎn)序列后，利用自然語言處理模型SkipGram 生成嵌入向量。給定一個(gè)節(jié)點(diǎn)，SkipGram 的目標(biāo)是最大化其上下文出現(xiàn)在序列中的概率，其中節(jié)點(diǎn)的上下文由以其為中心的大小為的窗口得到。

對(duì)于這一任務(wù)，采用分層softmax 優(yōu)化策略，通過霍夫曼二叉樹計(jì)算條件概率。對(duì)于窗口內(nèi)的節(jié)點(diǎn)∈，在霍夫曼二叉樹中有一條由樹節(jié)點(diǎn)構(gòu)成的路徑,,…,b，其中為根節(jié)點(diǎn)，b即為節(jié)點(diǎn)，有：

其中，是二元分類器邏輯回歸。

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

本章在第1章的基礎(chǔ)上，將衍生出的模型ASEAL（learning from subgraphs，embeddings and attributes for link prediction with attention mechanism）、DNSL（learning from double-radius node labeling，node2vec and struc2vec for link prediction）以及最終模型ADNSL與啟發(fā)式方法、節(jié)點(diǎn)嵌入算法還有神經(jīng)網(wǎng)絡(luò)模型在八個(gè)數(shù)據(jù)集上進(jìn)行了全面的對(duì)比。本章接下來主要介紹數(shù)據(jù)集、評(píng)價(jià)指標(biāo)、負(fù)注入、模型結(jié)構(gòu)及超參數(shù)設(shè)置，并進(jìn)行實(shí)驗(yàn)對(duì)比分析。

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

實(shí)驗(yàn)包括八個(gè)真實(shí)數(shù)據(jù)集：USAir（美國航空線路網(wǎng)絡(luò)）、NS（網(wǎng)絡(luò)科學(xué)研究人員協(xié)作網(wǎng)絡(luò)）、PB（美國政治博客網(wǎng)絡(luò)）、Yeast（蛋白質(zhì)交互網(wǎng)絡(luò)）、C.ele（秀麗隱桿線蟲的神經(jīng)網(wǎng)絡(luò)）、Power（美國西部電網(wǎng)）、Router（路由器級(jí)因特網(wǎng)）和E.coli（大腸桿菌代謝產(chǎn)物成對(duì)反應(yīng)網(wǎng)絡(luò)）。八個(gè)數(shù)據(jù)集涉及的領(lǐng)域有交通網(wǎng)絡(luò)、社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)等。它們的具體信息見表1，其中||為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量，||為網(wǎng)絡(luò)中邊的數(shù)量。

表1 實(shí)驗(yàn)數(shù)據(jù)集Table 1 Experiment datasets

2.2 評(píng)價(jià)指標(biāo)

本文的實(shí)驗(yàn)結(jié)果主要使用ACC（準(zhǔn)確率）和AUC（ROC 曲線下面積）評(píng)估二分類的優(yōu)劣。每個(gè)實(shí)驗(yàn)進(jìn)行30 次，取平均值作為實(shí)驗(yàn)結(jié)果。

對(duì)于每個(gè)數(shù)據(jù)集，將網(wǎng)絡(luò)中存在的鏈接隨機(jī)分為訓(xùn)練正例和測試正例，并選取等量的不存在鏈接的節(jié)點(diǎn)對(duì)作為訓(xùn)練負(fù)例和測試負(fù)例。在實(shí)驗(yàn)中，考慮了50%和90%的鏈接作為訓(xùn)練正例兩種情況。另外，在生成節(jié)點(diǎn)嵌入特征之前，需將測試正例從網(wǎng)絡(luò)中移除以防止測試集泄露。

2.3 負(fù)注入

假設(shè)給定網(wǎng)絡(luò)=(,)，有訓(xùn)練集正例?，以及訓(xùn)練集負(fù)例?=?。在網(wǎng)絡(luò)上利用節(jié)點(diǎn)嵌入算法得到的嵌入向量作為節(jié)點(diǎn)特征。若該過程記錄了網(wǎng)絡(luò)中某些邊的存在信息，即，則在神經(jīng)網(wǎng)絡(luò)訓(xùn)練過程中，僅僅對(duì)這部分信息進(jìn)行擬合就能得到很好的訓(xùn)練效果，但是這會(huì)導(dǎo)致模型的泛化性能很差。因此，對(duì)于存在這一問題的節(jié)點(diǎn)嵌入算法，通過負(fù)注入將訓(xùn)練集負(fù)例加入網(wǎng)絡(luò)中，即在′=(,?E)上學(xué)習(xí)節(jié)點(diǎn)嵌入向量，可以有效地提高泛化性能。

在局部特征提取中，特征矩陣包含節(jié)點(diǎn)標(biāo)記矩陣和節(jié)點(diǎn)嵌入矩陣兩部分。如果直接在上利用node2vec 提取節(jié)點(diǎn)嵌入向量，由于隨機(jī)游走過程依賴于網(wǎng)絡(luò)中存在的邊，該過程會(huì)記錄邊的存在信息，圖神經(jīng)網(wǎng)絡(luò)只需要對(duì)這部分信息進(jìn)行擬合即能得到很好的訓(xùn)練效果，但是在測試時(shí)模型的泛化性能很差。因此node2vec 需要在負(fù)注入后的′=(,?E)上學(xué)習(xí)節(jié)點(diǎn)嵌入向量。

與node2vec 不同，在利用struc2vec 提取全局結(jié)構(gòu)特征時(shí)，使用負(fù)注入是不合理的。struc2vec 在生成向量表示過程中，僅僅利用了節(jié)點(diǎn)度信息，且隨機(jī)游走是在重構(gòu)的聚合圖上進(jìn)行的，未涉及原圖中任何邊信息。若struc2vec 在負(fù)注入的圖上生成節(jié)點(diǎn)嵌入向量，反而會(huì)對(duì)節(jié)點(diǎn)度和節(jié)點(diǎn)結(jié)構(gòu)特征產(chǎn)生較大影響，嚴(yán)重影響性能。經(jīng)過實(shí)驗(yàn)發(fā)現(xiàn)，不使用負(fù)注入的struc2vec 可以保留更有效的結(jié)構(gòu)特征相似性，對(duì)鏈接預(yù)測的效果有顯著提高。

2.4 模型結(jié)構(gòu)及超參數(shù)設(shè)置

局部特征生成模塊的輸入為目標(biāo)鏈接一跳或兩跳子圖，∈{1,2}。對(duì)于SEAL 和DNSL，為了適應(yīng)內(nèi)存，數(shù)據(jù)集PB 和E.coli 選擇=1，其余數(shù)據(jù)集=2。對(duì) 于ASEAL 和ADNSL，數(shù) 據(jù) 集NS 和Power 選 擇=2，由于加入了雙向注意力機(jī)制，為了適應(yīng)內(nèi)存，其余數(shù)據(jù)集=1。另外，對(duì)于E.coli，限制子圖中最大節(jié)點(diǎn)數(shù)為150。特征矩陣中node2vec生成的節(jié)點(diǎn)嵌入向量為128 維，node2vec 有偏隨機(jī)游走參數(shù)=1，=1，游走路徑數(shù)為10，路徑長度為80，SkipGram 中窗口大小為10。

局部特征生成模塊采用四個(gè)圖卷積層，通道數(shù)分別為32、32、32、1。為了方便起見，僅使用最后一層通道排序，排序后，截取行，其中值使得60%的子圖的節(jié)點(diǎn)數(shù)大于。接下來是兩個(gè)一維卷積層，輸出通道數(shù)分別為16 和32。第一個(gè)卷積層的輸入維度為97×1，卷積核大小為97×1，卷積核個(gè)數(shù)為16，步長為97，輸出維度為×16，之后的最大池化層的卷積核大小為2，步長為2。第二個(gè)卷積層的卷積核大小為5×16，卷積核個(gè)數(shù)為32，步長為1。圖卷積層使用tanh 作為非線性函數(shù)，在其他層中使用ReLU 作為激活函數(shù)。

全局特征提取模塊中，struc2vec 將′=6 的多層圖的信息匯聚到單層圖，生成32 維的節(jié)點(diǎn)嵌入向量，并將64 維的目標(biāo)鏈接節(jié)點(diǎn)向量表示輸入到全連接層。與node2vec 相同，對(duì)于聚合圖上的隨機(jī)游走，每個(gè)節(jié)點(diǎn)的游走路徑數(shù)為10，路徑長度為80，SkipGram中窗口大小為10。

局部特征生成和全局特征提取模塊的輸出維度均固定為64 維。全連接層的隱藏單元數(shù)為128，dropout比率為0.5。

2.5 實(shí)驗(yàn)結(jié)果及分析

表2 和表3 分別是50%和90%的鏈接作為訓(xùn)練正例的情況下，模型性能的對(duì)比，其中帶下劃線的AUC為次優(yōu)的，加粗的AUC 為最優(yōu)的。

表2 模型AUC 對(duì)比（50%訓(xùn)練鏈接）Table 2 AUC comparison of different approaches(50%training links) %

表3 模型AUC 對(duì)比（90%訓(xùn)練鏈接）Table 3 AUC comparison of different approaches(90%training links) %

表中前六個(gè)方法為引言中提到的鏈接預(yù)測啟發(fā)式方法。

LINE 和N2V 為經(jīng)典的節(jié)點(diǎn)嵌入算法，它們利用源節(jié)點(diǎn)周圍的節(jié)點(diǎn)信息生成向量表示，進(jìn)而用于鏈接預(yù)測。

WLNM 算法利用目標(biāo)鏈接局部子圖的節(jié)點(diǎn)標(biāo)記重構(gòu)鄰接矩陣，輸入全連接神經(jīng)網(wǎng)絡(luò)鏈接預(yù)測。

SEAL 算法是表現(xiàn)十分優(yōu)異的鏈接預(yù)測算法，利用圖神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)局部啟發(fā)式信息，進(jìn)行端到端的鏈接預(yù)測。

ASEAL 是本文提出的結(jié)合雙向無參注意力機(jī)制的SEAL 算法鏈接預(yù)測模型。

DNSL 是本文提出的鏈接預(yù)測模型，其中圖卷積用于局部特征生成，struc2vec用于全局特征提取。

ADNSL 是本文提出的鏈接預(yù)測模型最終版本，結(jié)合多特征和圖注意力卷積，可以顯著提升鏈接預(yù)測的性能。

在八個(gè)數(shù)據(jù)集兩種情況下，結(jié)合表2 和表3，可以看出：

（1）ASEAL 相較于SEAL 有一定程度的性能提升，說明融合雙向無參注意力機(jī)制的圖卷積模型，可以在一定程度上彌補(bǔ)特征無效性和節(jié)點(diǎn)無偏性。

（2）DNSL 模型利用圖卷積作為局部特征生成模塊，struc2vec 作為全局特征提取模塊，可以有效結(jié)合局部和全局特征，很好地針對(duì)SEAL 的局部性獲得圖卷積部分無法學(xué)到的特征信息。

（3）ADNSL 模型相較于其他所有模型，均有非常顯著的性能提升。相較于SEAL，尤其對(duì)于NS、Power和Router這三個(gè)數(shù)據(jù)集，ADNSL 的提升尤為明顯，在表2 中AUC 值提升分別有10 個(gè)百分點(diǎn)、17 個(gè)百分點(diǎn)和10 個(gè)百分點(diǎn)左右。即使在表3 中，數(shù)據(jù)集中90%的邊作為訓(xùn)練正例時(shí)，其他方法的AUC 表現(xiàn)良好，ADNSL 仍能有進(jìn)一步提升。

對(duì)于NS、Power 和Router 提升十分明顯的原因，分析認(rèn)為：ADNSL 等模型對(duì)于平均度較小的數(shù)據(jù)集，可以更好地捕捉式（7）所示節(jié)點(diǎn)度序列的差異，進(jìn)而區(qū)分節(jié)點(diǎn)結(jié)構(gòu)特征。例如，度為1 和2 的節(jié)點(diǎn)之間的距離為1，要遠(yuǎn)遠(yuǎn)大于度為101 和102 的節(jié)點(diǎn)之間的距離1/101。

圖7 為SEAL、ASEAL、DNSL 和ADNSL 四個(gè)模型在NS、Power 和Router 三個(gè)數(shù)據(jù)集，50%訓(xùn)練鏈接情況下，訓(xùn)練過程中LOSS 和ACC 值變化對(duì)比。

圖7 收斂性分析（50%訓(xùn)練鏈接）Fig.7 Convergence analysis(50%training links)

可以很明顯地看出，相較于SEAL，本文提出的模型訓(xùn)練起始值優(yōu)于SEAL，且可以達(dá)到更優(yōu)狀態(tài)。對(duì)于Power 數(shù)據(jù)集，次優(yōu)模型SEAL 在訓(xùn)練過程中的損失略有下降后，很快開始上升，而本文的模型可以較好地學(xué)習(xí)并達(dá)到穩(wěn)定狀態(tài)。另外目前基于圖神經(jīng)網(wǎng)絡(luò)的鏈接預(yù)測算法一般可以在50 輪以內(nèi)達(dá)到最優(yōu)值，而WLNM 等基于全連接神經(jīng)網(wǎng)絡(luò)的算法往往需要100～150 輪才能得到穩(wěn)定的結(jié)果。

3 結(jié)束語

在啟發(fā)式方法和節(jié)點(diǎn)嵌入算法研究的基礎(chǔ)上，利用神經(jīng)網(wǎng)絡(luò)自動(dòng)學(xué)習(xí)啟發(fā)式特征進(jìn)行鏈接預(yù)測表現(xiàn)出優(yōu)越的性能。本文在表現(xiàn)優(yōu)異的算法SEAL 的基礎(chǔ)上，提出了融合圖注意力的多特征鏈接預(yù)測算法ADNSL。ADNSL 分為局部特征生成和全局特征提取兩個(gè)模塊，第一個(gè)模塊利用雙向無參注意力圖卷積學(xué)習(xí)啟發(fā)式特征，第二個(gè)模塊利用聚合圖提取目標(biāo)節(jié)點(diǎn)的結(jié)構(gòu)特征，然后將兩個(gè)模塊輸出的特征向量利用全連接層融合。

兩個(gè)模塊的特征融合可以有效解決基準(zhǔn)算法SEAL 的局部性。圖注意力卷積中的雙向無參注意力可以在一定程度上彌補(bǔ)特征無效性和節(jié)點(diǎn)無偏性。利用迭代公式生成的聚合圖可以有效減少有偏隨機(jī)游走的時(shí)間，降低內(nèi)存消耗和磁盤消耗。

實(shí)驗(yàn)表明，本文提出的ADNSL 模型性能遠(yuǎn)超傳統(tǒng)的啟發(fā)式算法，優(yōu)于SEAL、WLNM 等表現(xiàn)優(yōu)異的神經(jīng)網(wǎng)絡(luò)算法。對(duì)于之前的工作中表現(xiàn)不理想的數(shù)據(jù)集，ADNSL 的表現(xiàn)有了巨大的提升。在未來的工作中，可以考慮更多更豐富的全局信息，例如社區(qū)信息（M-NMF、NECS 等）作為全局特征，進(jìn)一步提高鏈接預(yù)測的性能。