張雁操，趙宇海，史 嵐

東北大學 計算機科學與工程學院，沈陽110169

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

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

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

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

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

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

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

（1）局部性：對于目標鏈接，該方法通常考慮一跳或兩跳局部子圖，利用的特征如局部子圖的鄰接矩陣、局部子圖的DRNL 獨熱編碼標記矩陣和node2vec向量表示等。通過神經(jīng)網(wǎng)絡的學習，只能獲得低階啟發(fā)式特征。

（2）特征無效性：由于目標鏈接的局部子圖可能是不連通的，會導致DRNL 節(jié)點標記矩陣具有較強的特征無效性（見1.1 節(jié)）。

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

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

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

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

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

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

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

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

圖1 ADNSL 框架Fig.1 Framework of ADNSL

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

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

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

1.1 局部特征生成模塊

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

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

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

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

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

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

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

圖4 softmax 前圖注意力權重示意圖Fig.4 Graph attention weights before softmax

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

1.2 全局特征提取模塊

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

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

（1）度量結構相似性

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

對于圖=(,)，=||表示圖中的節(jié)點數(shù)。若有圖中的節(jié)點，R()定義為的第跳點集。對于?，()表示中節(jié)點的有序度序列。令為圖的直徑，指圖中任意兩個節(jié)點間距離的最大值。對于圖中任意兩節(jié)點、的跳子圖，=0,1,…,，考慮它們在層的結構距離定義為：

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

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

和的距離即為所有元素對距離之和。

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

（2）構建多層圖

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

此時構建的多層圖是層內(nèi)無向加權層間有向加權的。式（9）表示層內(nèi)權重，在第層，兩個點、的結構距離越遠，權重越小。只有當f(,)有意義時，、在層才有邊相連。

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

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

在多層圖中，每個節(jié)點與2×lb個節(jié)點相連，但是根據(jù)式（6）和式（9）可知，每一層的連接情況可能不同，因為當或在跳無鄰居時，f(,)無意義，此時,在層無邊相連。為了使每一層的連接情況完全相同，對于在第0 層有邊相連的節(jié)點對,，若它們在＞0 層無邊相連，則令w(,)=0。

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

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

圖6 聚合圖Fig.6 Agglomerative graph

若節(jié)點對(,)在層結構特征不相似，則在+1 層一定不相似，由多次小權值累積，可以得到更加精細的權重。

若節(jié)點對(,)在層結構特征相似，在+1 層也相似，低層的權重匯聚到高層降低了其影響力，傾向于依賴高層權重進行隨機游走。

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

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

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

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

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

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

2 實驗

本章在第1章的基礎上，將衍生出的模型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é)點嵌入算法還有神經(jīng)網(wǎng)絡模型在八個數(shù)據(jù)集上進行了全面的對比。本章接下來主要介紹數(shù)據(jù)集、評價指標、負注入、模型結構及超參數(shù)設置，并進行實驗對比分析。

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

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

表1 實驗數(shù)據(jù)集Table 1 Experiment datasets

2.2 評價指標

本文的實驗結果主要使用ACC（準確率）和AUC（ROC 曲線下面積）評估二分類的優(yōu)劣。每個實驗進行30 次，取平均值作為實驗結果。

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

2.3 負注入

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

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

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

2.4 模型結構及超參數(shù)設置

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

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

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

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

2.5 實驗結果及分析

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

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

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

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

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

WLNM 算法利用目標鏈接局部子圖的節(jié)點標記重構鄰接矩陣，輸入全連接神經(jīng)網(wǎng)絡鏈接預測。

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

ASEAL 是本文提出的結合雙向無參注意力機制的SEAL 算法鏈接預測模型。

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

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

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

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

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

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

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

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

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

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

3 結束語

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

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

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