融合模體圖神經網絡和自編碼器的鏈路預測

魯富榮，原之安，錢宇華+

1.山西大學大數據科學與產業研究院，太原030006

2.山西大學計算智能與中文信息處理教育部重點實驗室，太原030006

3.山西大學計算機與信息技術學院，太原030006

網絡是對現實世界對象及其相互作用關系的抽象表示，其中節點代表實體對象，鏈接表示實體間的成對關系。如生物蛋白質相互作用網絡、科學研究中的引文合作網絡以及社交網路中朋友關系網絡。這些網絡中包含豐富的節點屬性信息、結構信息以及網絡演化信息。在網絡的演化過程中，某些鏈接可能出現或消失，需要對缺失數據進行補全以及對未來可能出現或消失的鏈接做出預測。同時作為數據挖掘領域的一個重要分支，鏈路預測具有很重要的現實意義。例如，生物網絡分析[1]中，鏈路預測可以對生物數據進行挖掘和補全。科學合作者[2]及朋友推薦[3]中，鏈路預測可以推薦相關的新的朋友和科研合作者。

鏈路預測問題作為數據挖掘領域的經典問題，已有很多相關的模型和方法。目前鏈路預測的方法大多基于節點表示的相似性假設，也即節點對的表示越相似，則產生鏈接的可能性越大，因此問題就歸結為尋找高質量的節點表示，使得節點的表示保留原網絡的拓撲特征，也即原網絡有邊相連的節點，在節點的表示中較為相似。

近年來，由于圖結構的網絡嵌入方法和圖神經網絡的迅速發展，進一步提升了模型對網絡節點的表示能力。然而大部分模型都利用節點的直接鄰居的信息進行卷積操作，并未充分利用網絡的結構信息且較少考慮網絡的高階拓撲信息。

為提高節點的表示能力且兼顧計算效率，本文提出了基于模體的圖神經網絡鏈路預測模型，主要貢獻包括三方面：

（1）在自編碼器框架下，提出一種模體圖神經網絡模型為編碼器的鏈路預測模型，該模型提取了網絡的高階拓撲特征。

（2）構建了基于同質網絡的模體圖神經網絡模型，根據指定的模體結構構建節點的鄰域，進而聚合鄰居信息得到節點的表示。

（3）不同數據集上的實驗結果表明本文的模型有效提高了鏈路預測的準確率。

1 相關工作

傳統的鏈路預測方法主要分為兩大部分：基于拓撲指標的方法和基于機器學習的方法。第一類方法又可分為基于局部拓撲的方法和基于全局拓撲的方法。此類方法通常假設節點間的共同鄰居越多則越相似。如共同鄰居CN（common neighbour）[4]和AA（adamic-adar）[5]指標以及基于資源分配的RA（resource allocation）[6]指標等，這類方法的優點是計算效率高且可并行，但缺點是準確率相對較低，尤其當網絡比較大而且稀疏時。基于全局的方法利用全局的拓撲信息來計算節點間的相似性，準確度有一定的提升，但由于利用了全局的拓撲信息，計算復雜度偏高。另一大類方法是基于機器學習的模型，包括基于機器學習的分類方法、基于概率似然函數的方法和矩陣分解方法，其中分類方法將節點對標記為0 或1，0表示不存在鏈接，1 代表存在鏈接，進而將鏈路預測轉化為二分類問題。該類方法用的是監督學習中一些常用的分類算法（如決策樹、K 近鄰法、支持向量機）對缺失的連邊進行預測。基于概率的模型主要包括層次結構模型，這類方法假設網絡有一定的先驗的分層結構或分塊的結構[7]，給出了網絡的結構特征的定量刻畫。基于矩陣分解的方法將鏈路預測視為鄰接矩陣的填充問題，基于非負矩陣或者譜分解等方法，給出節點的向量表示，進而計算節點的相似性，預測節點間鏈接的存在性。這類方法的學習參數較少，但計算復雜度較高。

隨著深度學習的深入發展以及深度學習和網絡數據挖掘的融合，進一步提高了模型的表達能力，國內外學者提出了一系列基于圖嵌入和圖神經網絡的鏈路預測方法。網絡嵌入的方法是自動從原始網絡結構信息中抽取局部的和全局的特征，將網絡節點映射到低維的向量空間。這類方法包括DeepWalk[8]、node2vec[9]、LINE[10]以及struc2vec[11]。相比傳統方法，這類方法達到了較高的鏈路預測準確率。然而這類方法也存在一定的局限性：首先，訓練過程中缺乏監督信息，使得節點的表示與任務的關聯性不足。其次，在運算過程中要多次用到基于全局拓撲結構的隨機游走方法，因此計算復雜度較高。

由于深度學習在圖像分類和自然語言處理方向的成功應用，推動了深度學習方法在圖網絡方向的遷移。借鑒卷積神經網絡的思想，圖卷積網絡（graph convolutional networks，GCN）[12]結合網絡的全局拓撲信息和節點的屬性信息，對節點的鄰居信息進行聚合，最終基于節點分類任務給出了節點的表示。在此基礎上，Velickovic 等提出了圖注意力網絡（graph attention network，GAT）[13]，基于網絡的節點一階鄰居信息和屬性信息，將任意兩個節點的信息進行拼接作為連邊信息，得到節點j相對于節點i的注意力權重，進而按鄰居節點的注意力權重不同，對鄰居信息進行加權聚合，得到節點的最終表示。圖神經網絡模型得到了更好的節點表示，進而達到更高的節點分類和鏈路預測準確度。同時也存在如下缺陷：（1）聚合函數采用最大或平均的方法，不能很好地對網絡進行區分。（2）在網絡增長或遭受攻擊時，網絡結構會發生改變，此時要得到節點表示，只能重新用GCN展開計算。（3）在網絡表示的過程中用到了節點鄰居信息，但并未用到網絡的高階信息，也即GCN 對網絡的拓撲信息利用不充分。

對于第一個問題，Graph Isomorphism Network[14]進行了初步的嘗試，聚合過程采用MLP+sumpooling，在多個任務上準確率達到目前最好的結果。在第二個問題上，圖神經網絡模型GraphSage[15]在迭代過程中固定采樣尺寸，然后采取一種特殊的聚合策略，對不斷增長的網絡的表示提供了很好的解決方案。對于第三個問題，Zhang 等人[16]提出了SEAL（learning from subgraphs，embeddings and attributes for link prediction）模型，該模型從原網絡中提取包含待預測節點對的特定子圖結構，得出一系列拓撲指標作為節點對的向量表示，進而學習出兩個節點存在鏈接的可能性。然而利用子圖結構進行學習時，對于每一對待預測節點u、v，需要構建以u、v為中心的子圖，同時計算該子圖對應的拓撲指標，進而利用神經網絡進行相應的訓練，計算成本較高。由于網絡由一些基本的子圖結構（motif）構成，有很多研究者試圖將圖神經網絡和模體信息結合起來執行下游的任務。

Wang 等人[17]提出了基于motif 的深度特征學習模型，利用正則表達式和圖自編碼器模型保留網絡的模體特征，最后獲得節點的表示。該模型僅利用了三階模體的信息而且并未真正將模體信息和圖神經網絡進行融合。Sankar 在2019 年給出了基于異質網絡模體結構的圖神經網絡模型Meta-GNN[18]，將異質模體結構嵌入圖卷積網絡，并結合圖注意力模型，對異質網絡的節點進行了分類。然而對于同質網絡，該模型并沒有給出相應將高階結構和圖神經網絡相結合的解決方案。

本文提出的基于模體圖神經網絡的鏈路預測方法，將網絡的模體結構和圖神經網絡模型結合，融合了網絡的高階拓撲特征，增強了圖神經網絡的表示能力。在復雜網絡的鏈路預測驗證了模型的有效性，可運用到后續其他任務中。

2 預備知識

2.1 基本定義

本節列舉了文章中的預備性知識和記號，如表1所示。設G=(V;E)表示一個圖網絡，V表示節點集，E表示邊集，若兩個節點vi、vj有邊相連，則(vi,vj)∈E。模體M是指由網絡的少量節點構成的圖G的子圖，定義如下：

表1 文中使用的符號和變量Table 1 Variables and notations in text

定義1（模體）[18]設M是圖G=(V;E) 的連通子圖，且滿足對任意(vi,vj)∈EM,(vi,vj)∈E，則稱M為G的模體，其中EM表示子圖M的邊集。

不同三階模體和四階模體如圖1 所示（表示為M3.、M4.，每個模體Mij的第一個下標i代表節點數，第二個下標j是指定排序），在科研合作網中模體M31代表兩個作者和另外一位都有合作，但他們彼此并沒有合作。往往這種情況發生在普通科研人員和科研名人的合作中。M32代表的則是接近同類一水平的科研人員的合作，三位作者彼此之間都有合作。

圖1 所有的三模體和四模體Fig.1 All tri-motifs and quad-motifs

定義2（模體的實例）[18]設Su=(VS，ES)是模體S的包含節點u實例，如果Su是圖G的一個子圖，且有VS∈V,ES∈E，使得對任意的x,y∈VS,(x,y)∈ES存在一個雙射ψ：S→M滿足 (x,y)∈ES當且僅當(ψS(x),ψS(y))∈EM。

定義3(模體鄰居）對于指定的模體類型M，節點vi的一階鄰居中，與vi位于同一類型模體中的節點稱為節點vi基于模體M的鄰居。

圖2 中的兩個模體(v,v1,v2)以及(v,v3,v4)是模體M32的兩個實例，同時v1、v2、v3、v4也是v的模體鄰居。在不同的網絡中，有隸屬于網絡的不同特征模體，其發生頻率遠大于隨機圖中該子圖的發生頻率。在計算過程中，為提取網絡的模體特征，需要從網絡中搜索與不同類型模體同構的所有模體，該過程計算成本較高。為降低計算的復雜度，本文僅考慮三階和四階模體，首先利用軟件mfinder[19]對網絡所包含的不同類型模體比例進行計算，給出每個網絡的模體分布情況。

圖2 節點v的接受域包含v1、v2、v3、v4Fig.2 Receptive field around node v contains v1,v2,v3,v4

2.2 圖卷積網絡

傳統的圖卷積網絡模型結合了網絡的拓撲信息和屬性信息，在網絡的每一層中將節點的鄰居信息進行聚合，然后進行非線性變換得到節點的表示，具體的形式如下：

輸入是網絡的鄰接矩陣A∈RN×N和節點的屬性矩陣X∈RN×D，V是圖G的節點集，N是網絡的節點數，是鄰接矩陣A對應的標準化拉普拉斯矩陣，WD×F是對應的權重矩陣，σ表示激活函數（這里指Softmax），H是一次迭代的輸出，即原網絡節點的低維表示。在神經網絡的一次迭代過程中，節點vi的表示聚合了其一階鄰居的信息，最后通過激活函數得到節點的低維表示，對于每個節點，上述過程可表示為：

一個節點v的接受域是節點的一階鄰居構成的鄰域。在本文中一個節點v的接受域是指和v包含在同一類型模體中的節點，如圖2 所示。類似于鄰接矩陣，這里也定義了同質網絡的模體鄰接矩陣。

式（3）是模體S到AM的一個映射，AM是一個矩陣。IS(u)是一個示性函數，如果u∈S,則IS(u)=1,否則為0。定義對角矩陣DM∈RN×N，對角線上的第i元素是包含第i個節點的模體M的個數，也即。通常對于一個給定的機器學習任務，需要綜合考慮多個相關的模體結構，一類模體代表一種結構特征，然而對給定的數據挖掘任務通常需要多個方面的特征，本文采用多類模體的信息構建神經網絡。

3 基于模體圖神經網絡的鏈路預測模型

3.1 模體圖神經網絡

本文引入一個基于模體的空間卷積操作來提取節點的特征[18]。給定模體M以及目標節點vi，設輸入節點的是1 維向量，經過映射之后的節點的維度F=1。定義節點vi權重矩陣w0及其鄰居節點vj的權重wj，則節點v處的卷積可定義為與節點vi基于模體M的模體鄰居的加權和，即：

其中，xi、xj表示節點vi、vj的屬性向量。hM(vi)表示節點vi的卷積輸出，σ(·)表示激活函數，例如ReLU(·)或Softmax(·)，權重共享過程就是賦予節點vi的模體鄰居相同的權重。進而可將上式的情況推廣到一般情形：節點的屬性矩陣X為N×D維的矩陣，輸出維度為F，則有：

其中，WM是權重矩陣，HM是在模體M下的卷積輸出。由于在表示每個節點的過程中，單類模體的特征信息不能充分地表示節點，有必要綜合多類模體的信息。但在聚合的過程中不同類型的模體對每個節點的重要性各不相同，為了體現卷積過程中各類模體對節點表示的不同影響，本文加入模體的注意力機制[18]。

式中，U是模體的個數，ek,i=α(hk(vi))=W·hk(vi)是關于hk(vi)的一維卷積，注意力系數αk,i反映了模體Mk對于節點vi的重要性，hk(vi)是節點vi在Mk下的卷積輸出。本文將模體圖神經網絡模型簡稱為MGNN（motif-based graph neural network），其網絡架構如圖3 所示。經過對不同類模體的卷積的聚合，在激活層連接注意力網絡，這兩部分構成一個基本神經網絡單元，進而逐層迭代。最后對卷積層聚合各類模體的卷積輸出之后，通過全連接網絡得到最終節點的表示。

圖3 MGNN 的深度圖神經網絡框架Fig.3 Deep graph neural network framework MGNN

3.2 圖自編碼器

本文的模型采用了自編碼器VGAE（variational graph auto-encoders）[20]結構，自編碼器是通過編碼器和解碼器結構對節點進行表示的一種無監督學習方式，以網絡鄰接矩陣A和屬性矩陣X作為輸入，編碼器采用的是模體圖神經網絡模型（MGNN），對編碼以后的向量做內積運算作為解碼器，給出連邊的預測值，最后選取交叉熵作為損失函數進行梯度反傳（結構如圖4 所示）。本文的算法流程如下：

圖4 圖自編碼器的結構框架Fig.4 Architecture of GAE

算法1結合圖自編碼器的模體圖卷積網絡模型

3.3 復雜度分析

4 實驗與結果

本文提出了基于同質網絡的MGNN 的鏈路預測模型，并且在幾個實際網絡數據集驗證了方法的有效性。訓練過程中，數據集的部分鏈接（正類邊）已被刪除，而所有節點特征保持不變。用移除的邊和相同數量的隨機抽樣的未連接節點對（負類邊）形成驗證集和測試集。根據模型正確區分正類邊和負類邊的能力來比較模型。驗證集和測試集分別包含5%和10%的引文鏈接，剩余作為訓練集。驗證集用于優化超參數。用glorot 方法初始化神經網絡權重，學習率為0.001，神經網絡的層數為3 層，一次實驗訓練200輪，每個數據集訓練20次，計算平均值和方差。

4.1 度量標準

本文使用的鏈路預測的度量指標為AUC（area under the curve of ROC）和AP（average precision）。AUC 是ROC 曲線下方的面積，AP 是平均準確率。AUC 值至少大于0.5，AUC 的值越高，算法的精確度越高，但AUC 的值最高不超過1。AP 是在不同召回率下準確率的加權平均，取值越高表明算法精度越高，同樣不超過1。

4.2 數據集

本文將在Cora、CiteSeer、PubMed 3 個數據集上測試提出的方法。下面從數據集大小和數據特點等方面分別介紹這3 個數據集。

Cora 數據集共2 708 個樣本點，每個樣本點都是一篇科學論文，每篇論文都由一個1 433 維的詞向量表示。

CiteSeer 數據集是從CiteSeer 數字論文圖書館中選取的一部分論文，整個語料庫共有3 327 篇論文，在詞干提取和刪除停止詞之后，只剩下3 703個單詞。

PubMed 數據集包括來自PubMed 數據庫的19 717 篇關于糖尿病的科學出版物。引文網絡由44 338 個鏈接組成。數據集中的每個出版物都由一個由500 個唯一單詞組成的字典中的TF/IDF 加權詞向量來描述。

用mfinder 軟件給出每個網絡的模體分布情況（如表2 所示）。為進一步提高計算效率，選取網絡中包含3 個節點和4 個節點的模體。

表2 3 個數據集各類模體的比例Table 2 Proportion of various motifs in 3 datasets 單位：%

4.3 結果

本節選取幾個算法進行對比實驗，分別是MGNN、VGAE[2]、node2vec[9]、LINE[10]、DeepWalk[8]、DeepLinker[22]，MGNN 表示本文結合自編碼器的方法，VMGNN 表示本文方法與變分自編碼器結合的方法，(*)表示網絡輸入僅考慮拓撲信息而不包含屬性信息。Deep-Walk、LINE、node2vec 是基于拓撲結構的網絡嵌入的方法，結合隨機游走和Skip-gram 的思想給出節點的表示。VGAE 是結合圖卷積網絡和自編碼器的模型，在鏈路預測上取得了較好的效果。DeepLinker 是基于圖注意力網絡的鏈路預測模型，在鏈路預測上取得了較好的表現。在此情況下，網絡的輸入矩陣包括鄰接矩陣和維度為節點數的單位矩陣，實驗過程中主要選取模體M31、M32、M42構建模型。

4.4 實驗描述和總結

實驗結果如表3 所示，在兩個數據集上結合高階結構信息之后本文方法在大部分網絡上能夠得到網絡節點的更好的表示，鏈路預測的結果較傳統方法提升了1%～4%。同時在PubMed 數據集上的預測結果略低于VGAE，由于考慮了節點的模體結構信息，模體的數目未必服從正態分布，因此自編碼器在某些情況下的實驗結果會低于變分自編碼器對應的結果。

表3 基于MGNN 的鏈路預測實驗結果Table 3 Experimental results of link prediction modes based on MGNN 單位：%

4.5 消融實驗

本節將本文方法和VGAE 以及MGNN+MLP（全連接網絡）進行了對比，VGAE 將圖卷積網絡GCN 和自編碼器相結合，在鏈路預測任務中取得了很好的效果。MGNN+MLP 是在MGNN 網絡之后鏈接了全連接網絡MLP，以說明本文的模型MGNN+Attention的有效性。結果如圖5 所示。

圖5 MGNN+Attention、MGNN+MLP、VGAE對比實驗Fig.5 Comparison of results on MGNN+Attention,MGNN+MLP and VGAE

實驗結果表明，本文模型在大部分情形下優于其他兩類模型，進一步說明模型中融入模體結構可有效提高神經網絡的預測能力。同時MGNN+MLP與MGNN+Attention 的對比，也驗證了MGNN 網絡中鏈接注意力網絡的有效性，說明在節點表示的過程中，需要考慮不同模體的重要性。

4.6 實驗效率對比

本節給出了各個模型在網絡Cora 和CiteSeer 上鏈路預測任務的運行時間對比，本文采用的實驗環境是Ubuntu 16.04，CPU 為Intel?Xeon CPU E5-2620 v2@2.10 GHz，內存容量48 GB，圖6 給出了6 個相應算法的運行效率對比圖。

圖6 在Cora 和CiteSeer兩個數據集上算法效率對比Fig.6 Efficiency comparison of algorithms on Cora and CiteSeer datasets

如圖6 所示，基于圖表示學習的淺層網絡模型運行效率較高，但此類模型很難學習到網絡中節點的復雜結構信息。本文方法結合了多層的神經網絡結構以及高階的模體信息，盡管計算成本較高，但在鏈路預測的指標上較圖表示學習的方法取得了較大幅度提升。同時由于模型采用了自編碼器框架，運行時間與圖自編碼器（VGAE）等模型的運行時間接近。

5 結束語

本文提出了一種基于同質網絡的模體圖神經網絡鏈路預測模型，在圖卷積網絡的基礎上結合了網絡的高階結構-模體的信息，結合每一種模體結構給出了節點的表示，并進一步考慮了各類模體對于節點的注意力權重，最后利用節點的表示重構網絡。在幾個常規的引文數據集的鏈路預測任務上驗證了算法的有效性。在大規模的網絡中計算效率和準確度有待進一步改善。

在模型的訓練過程中，MGNN 用到了節點的高階模體信息，模型的計算成本有一定的增加，后續的研究考慮采取適當的采樣方法來降低模型的復雜度。