基于鄰域采樣的異質網絡鏈接預測算法*

劉 臣 謝寧靜 周立欣

（上海理工大學管理學院 上海 200093）

1 引言

圖作為一種常用的抽象數據結構，包含著豐富的內容信息和復雜的結構信息。現實世界中許多場景都可以用圖來表示，如知識圖譜［1］、開放學術網絡［2］、交通網絡［3］等。圖卷積網絡（Graph Convolution Network，GCN）在學習圖表示方面表現優異，已經受到各個領域的廣泛關注［4］。然而，隨著大數據時代的到來，數據量爆炸式增長，導致圖的規模日益擴大。傳統圖卷積模型在大規模圖上很難直接有效訓練。因此，如何高效處理大規模圖成為一個急需解決的問題。

面對規模日益增長的圖數據，采樣成為提高模型訓練速度，節約計算資源的常用方法。采樣方法根據特定規則選擇圖中的部分節點作為輸入樣本，從而適當調整輸入數據的大小和構成。采樣模塊通過靈活地構建輸入模型中的數據，可以很好地緩解傳統圖卷積訓練的鄰域爆炸問題。其中，鄰域爆炸是指圖卷積計算過程中鄰居節點數隨著卷積層深度的增加而呈指數增長。同時，采樣模塊避免圖卷積過程一直存儲并處理圖中每個節點的鄰居，保證了信息傳播的順利進行，降低GCN訓練的計算和存儲成本。

現有采樣方法主要用于同質圖處理，按照采樣對象選擇的角度不同，可簡單分為基于節點采樣、基于分層采樣以及基于子圖采樣三類。Graph-SAGE［5］是一種典型的基于節點采樣方法，該方法通過對訓練圖中每個節點的鄰居進行固定數量的采樣，學習了一個利用鄰域采樣和聚合生成節點嵌入的歸納過程，達到了減少計算成本的目的。但該方法估計方式存在著偏差，并且收斂性無法保證。隨后，有學者通過添加某些獨特采樣機制提出了新的節點采樣方法。Ying等［6］通過模擬隨機行走過程遍歷節點，計算訪問計數，為每個節點選取最具影響力的鄰居。Dai等［7］提出通過添加交替采樣策略對單跳鄰居進行采樣以更新嵌入和函數。VR-GCN［8］則通過方差減少技術將采樣鄰居的大小限制為任意小的數字，并利用歷史激活來近似嵌入，避免了遞歸計算。這些方法已經取得了不錯的效果，但除了SSE［7］方法外，其他方法仍然面臨著鄰居爆炸問題。

為了減輕節點采樣方法中鄰居節點數隨著層數增長呈指數擴展帶來的昂貴計算，有學者提出分層采樣方法。分層采樣的思想是在一個抽樣步驟中對一定數量的節點進行抽樣，避免鄰居爆炸并降低采樣過程的時間開銷。基于分層采樣的代表性工作之一是FastGCN［9］，其采用蒙特卡洛方法，根據預先設定的概率分布，在每一層獨立采樣一定數量的節點，避免了對多跳鄰居的遞歸采樣。然而該采樣方法可能導致采樣節點產生的鄰接矩陣是稀疏的，無法實現高精度。因此Huang等［10］在FastGCN的基礎上做出改進，AS-GCN通過自上而下對每層固定數量的節點進行抽樣，保證了較高的準確性。上述采樣方法避免了鄰域爆炸，提高了模型的訓練速度，但當訓練圖的規模很大時，這些方法在加速訓練時并不能優化內存成本。

面對訓練過程中的內存成本問題，有學者提出基于子圖的采樣方法。基于子圖的采樣方法在形式上是對GCN訓練中的每個小批進行一個或多個子圖抽樣，而不是在完整的圖上進行節點采樣或邊采樣。Cluster-GCN［11］使用圖聚類算法將原始圖劃分為多個簇，再隨機抽樣固定數量的聚類構造子圖。但在實際操作簇的大小很難控制。Graph-SAINT［12］通過使用隨機游走策略對根節點集中一個節點的鄰居進行采樣，并利用所選的鄰居和根節點集生成子圖。J.Bai等提出的Ripple Walk Training［13］考慮圖結構數據的隨機性和連通性，通過紋波行走采樣器采樣高質量子圖，用于后續模型訓練。

目前，上述三類采樣方法已經在同質網絡中取得了相多的應用。但相較于同質網絡，異質網絡［14］結構更加復雜。異質網絡是一種包括多種節點類型以及多種關系類型的特殊網絡。關于異質網絡的研究有很多數據挖掘任務，其中鏈接預測能夠有效挖掘網絡中的丟失信息，在實際生活中具有重要的使用價值，如好友推薦［15］、電影推薦［16］、知識圖譜完善［17］、新陳代謝網絡重建［18］等。Schlichtkrull等［19］提出的關系圖卷積網絡（RGCN）是學習異質網絡表示的強大模型，能夠有效解決鏈接預測任務。但當面臨真實世界中的大規模網絡結構時，關系圖卷積模型的使用成本、計算復雜度太高，因此迫切需要引入采樣方法以保證大規模圖的可擴展性。

本文提出了基于鄰域采樣的異質網絡鏈接預測小批量訓練算法，我們將鄰域采樣和批處理結合起來，可用于大規模異質網絡。算法的主要思想是通過小批量訓練的方式，對全圖進行采樣得到鄰域子圖。通過每次只構建一個批量的子圖進行更新參數，從而減少訓練過程的計算開銷。簡單來說，就是在訓練過程中，隨機打亂訓練圖數據，確定固定大小的小批量數據。然后以每個批量數據為中心，對訓練圖進行采樣，得到每個批量對應的鄰域子圖。最后將子圖輸入關系圖卷積模型中，進行圖卷積操作，得到對應的低維節點表征。并且由于DistMult［20］是一個簡單有效的因式分解，其在鏈接預測任務中有著良好表現。因此，在得到節點嵌入后，本文將DistMult模型作為評分函數處理后續異質網絡鏈接預測任務。

本文主要工作如下：

1）本文提出了一種針對大規模異質網絡的鄰域采樣方法。該采樣方法能夠更好地保留異質網絡的結構信息，并且在保持子圖的連通性和隨機性上具有明顯優勢。因此，該算法不僅提高了RGCN在大圖上的訓練速度，還能減少訓練過程的計算內存。

2）本文通過小批量訓練的方式實現了鄰域采樣方法。對全圖進行采樣得到批量鄰域子圖。RGCN模型在子圖內執行小批量隨機梯度下降，梯度計算不依賴于子圖之外的節點。

3）本文選擇多個基線方法，在規模不同的數據集進行鏈接預測任務的實驗，實驗結果證明了本文提出的采樣方法的有效性。實驗表明，大規模圖中鏈接預測準確率提高了30.67%。

2 相關研究

本文提出基于鄰域采樣的異質網絡鏈接預測小批量訓練算法，該算法利用鄰域采樣獲得子圖，并利用關系圖卷積模型對子圖進行編碼，捕獲異質網絡的結構和語義信息。本文將相關研究分為了兩類：圖卷積網絡的訓練技術和關系圖卷積模型。

1）圖卷積網絡的訓練技術

為了提高圖卷積的計算效率以及減少內存成本，一個簡單的解決措施是通過子圖采樣構建淺領域。通過將全局視角轉化到局部視角，即整個消息傳遞的步驟不是在全圖上進行的，而是在局部子圖上執行的，這樣我們能夠解決表達和計算的問題。Cluster-GCN［11］是一種基于子圖采樣的典型方法，該方法通過對全圖聚類構造子圖，但實際上聚類的大小是很難控制的，而且在大規模圖上聚類的空間和時間的開銷是不可忽略。于是Zeng等［12］以在大規模上訓練GCN模型為動機提出GraphSAINT，該方法在訓練過程中構建小批量的隨機漫步采樣器，模型性能優于先前工作。此外，Zhang等［21］提出的SEAL鏈接預測框架通過提取k階封閉子圖進行鏈接預測，并獲得了不錯的效果，證實了使用局部子圖來代替全局網絡的可行性。Zeng等［22］分析了深度圖神經網絡面臨著鄰居爆炸和過度平滑的缺點，并據此提出打破傳統的分層采樣思想，使用多種子圖采樣器，將在全圖上進行的圖卷積操作轉向局部子圖。實驗證明，這種基于子圖的采樣方法提高了推理精度和計算效果。因此，我們考慮通過采樣，使用局部子圖代替全局網絡進行訓練。

為了提高模型鏈接預測能力與訓練速率，基于以上研究，本文提出一種針對大規模網絡的鄰域采樣方法。該方法結合k階采樣器［22］對異質圖進行采樣，在保留網絡的結構信息的基礎上，獲取局部子圖，后續卷積操作都在小批量子圖上進行。

2）關系圖卷積模型

目前有多個研究利用圖卷積神經網絡（GCN）［4］處理圖數據，作為GCN模型的擴展，關系圖卷積模型（RGCN）［19］在處理多關系圖上的優秀表現也受到了各個研究領域的廣泛關注。該模型通過計算邊緣的方向和分別處理不同關系的消息傳遞將圖卷積擴展到多關系圖上。實驗結果表明，RGCN作為一個學習多關系圖潛在特征的消息傳遞框架，可以有效應用于多關系數據的建模。然而，盡管RGCN在處理異質網絡數據上性能較好，但它仍然面臨挑戰。對于圖卷積操作來說，節點的鄰域結構信息影響著該節點的特征表示，在消息傳遞過程中起著至關重要的作用。在RGCN訓練過程中，模型會在整個網絡中隨機采樣邊，并在采樣的邊緣上執行消息傳遞，生成節點嵌入。在此過程，大規模異質網絡的結構信息很容易丟失，而且并不能保證目標節點的鄰域結構信息被充分保留，因此，RGCN模型在大規模異質圖上并不能得到有效擴展。

基于以上研究，本文將使用關系圖卷積模型對采樣得到的子圖進行編碼以獲取各節點的特征表示。該部分能夠充分考慮異質圖中的關系類型，有利于鏈接預測任務的完成。

3 基于鄰域采樣的異質網絡鏈接預測算法

3.1 問題描述

其中，Vt表示通過在訓練圖上進行批量處理確定的種子節點集合。子圖G[v]表示以節點v為初始節點對訓練圖G進行采樣得到的子圖。G'm表示批量m對應的子圖。此基礎上我們探究了異質網絡鏈接預測任務。異質網絡鏈接預測研究的是異質網絡中的兩個節點之間是否存在鏈接［21］，即判斷節點vi和節點vj之間的邊(vi,vj)是否存在，以及存在邊的關系類型r。

3.2 基于k階采樣器的鄰域采樣

本節將介紹基于k階采樣器［22］的鄰域采樣方法，該方法對全圖進行采樣得到批量鄰域子圖，將圖的規模控制在可計算的范圍內。我們將采樣方法分成三個步驟：確定種子節點、k階采樣、子圖節點重排序。鄰域子圖的構建過程如圖1所示。

圖1 鄰域子圖的構建

3.2.1 確定種子節點

輸入異質圖G，將圖G中的N個三元組隨機打亂來構建M個批次，每個批次內固定b條數據。通過計算批次內數據源節點和終節點的并集確定種子節點。由于種子節點集合的結果依賴于分批的隨機性，這在一定程度上考慮到數據的多樣性，使得不同類型的節點能夠被收集，進而減少了網絡信息的損失。

3.2.2k階采樣

利用k階采樣器對每個批次中的種子節點進行采樣，將相同批次中所有種子節點的k階鄰域子圖連接得到采樣結果圖。其中，k階采樣器的實現方式是從種子節點出發尋找與其自身的最短路徑為k跳的節點集合，并從該集合中隨機選取b個節點作為采樣的結果。在該過程中，采樣器能夠捕捉到原始輸入圖一些有意義的全局結構特征。同時，SEAL框架［21］證明了局部網絡能夠表示全局網絡。因此，我們采樣得到的子圖包含自身和輸入原始圖的結構信息。使得節點嵌入中蘊含的信息更為豐富。此外，與隨機采樣的方式不同，本文所使用的采樣方法在保證隨機性的同時，還考慮了鄰域子圖的連接性。使得采樣結果子圖更好地保留了異質網絡中的領域結構信息。

3.2.3 子圖節點重排序

將每個批次中采樣得到的子圖分別重新編號得到最終的采樣結果圖。重新編號能夠清除原始輸入圖中的鏈接關系，避免模型學習到無關信息。通過這樣的方式能夠提升計算效率，消除采樣結果子圖中的冗余信息，提升模型的泛化性能。上述采樣方法的總體流程的偽代碼如算法1所示。

算法1基于k階采樣器的鄰域采樣算法

輸出：每個批量構建的子圖｛G'}={G1'…GM'}，每個批量對應的訓練樣本

3.3 鏈接預測任務

本節介紹鏈接預測總框架。先通過采樣模塊對異質圖進行采樣，獲得各批量對應的子圖，再使用關系圖卷積模型編碼器對鄰域子圖進行特征提取，并采用解碼器處理下游鏈接預測任務的過程。具體來說，先利用關系圖卷積模型的學習能力和泛化能力對各鄰域子圖進行編碼，學習子圖中各節點和關系的低維嵌入，再利用DistMult解碼器對這些嵌入進行學習。鏈接預測整體結構如圖2所示。

圖2 鏈接預測框架

3.3.1 鄰域子圖的特征提取

本文采用Schlichtkrull等［19］提出的關系圖卷積（RGCN）的方法在多關系鄰域子圖上執行消息傳遞來獲得各節點和關系的低維嵌入。該方法是獲得異質圖表征的一個有效方法，其在基于GCN的聚合鄰居的操作之上，對關系維度也進行了一次聚合，從而使得節點的聚合操作成為鄰居、關系維度上的雙重聚合。其核心公式表達如下：

其中，ci,r是通過預先學習或者選擇的特定的標準化常數，一般可選為表示與節點vi具有r關系的鄰居集合。為可學習參數，是節點自身對應的權重參數。

如圖2所示，RGCN模型的輸入是鄰域子圖。經過兩層關系卷積神經計算之后，編碼器會生成鄰域子圖各節點的特征向量，并將其輸入解碼器中。

3.3.2 預測評分

鏈接預測通常是指預測一個實體與另一個給定實體之間有特定關系的任務，包括實體排名［23～24］和關系預測［25］。具體來說，實體排名是給定(r,vj)預測實體vi或給定（vi，r）預測實體vj。前者表示為（?,r,vj），后者表示為（vi,r,?）。關系預測是預測兩個給定實體之間的關系，表示為（vi,?,vj）。這里我們僅考慮采用異質網絡關系預測任務。DistMult評分函數可用于計算關系存在可能性分數值。

預測兩個給定節點之間的關系（vi,?,vj）時，對于給定的三元組，模型通過使用以下函數對所有可能的三元組打分來訓練：

其中⊙為哈達瑪積，evi，evi表示關系r和節點vi的嵌入。表示可能的關系類型嵌入。本文利用交叉熵損失進行優化，使模型的正三元組評分高于負三元組，通過最小化交叉熵損失來得到知識圖譜中實體與關系的嵌入，損失函數公式如下：

其中T是該批次內正負三元組的全部集合，l是激活函數，y是一個指示符，當y=1時表示正三元組，y=0時表示負三元組。f(vi,r,vj)包括來自RGCN編碼器的實體嵌入和來自DistMult解碼器的關系嵌入。

3.4 空間算法復雜度分析

與以往的圖卷積操作不同，基于領域采樣的異質網絡鏈接預測算法考慮構建一種內存友好的方式。該算法只需要存儲鄰域子圖的節點特征向量矩陣與關系向量矩陣。其空間開銷如下：

對于傳統的關系圖卷積來說，在計算過程中通常依賴于全局網絡，其內存開銷為

其中|G|v表示整個網絡的節點數量，|G|r表示整個網絡的關系類型數量，K為RGCN設置層數。

由3.2節算法介紹可知，鄰域子圖是從大規模網絡中采樣得到，其規模遠小于原網絡，領域子圖中節點遠小于原網絡中的節點數，即因此，顯然本文提出算法空間開銷遠小于以往訓練方法，即S1＜S2。這使得模型能夠在大規模圖上高效地進行訓練。

4 實驗

4.1 實驗數據集及評價指標

為了證明提出的鄰域采樣算法框架的通用性及有效性，本文實驗針對三種規模不同的異質網絡進行鏈接預測對比，主要包括知識圖譜Freebase中的子集FB15k-237［19］，FB-Toy［26］以及詞匯數據庫WordNet中的子集WN18［19］。上述數據集的各項指標統計如表1所示。

表1 數據集描述

鑒于WN18數據集中存在一個影響實驗結果的缺陷：存在反向三元組對（vi,r,vj）和（vj,r-1,vi），其中（vi,r,vj）存在于訓練集，（vj,r-1,vi）存在于測試集。這在很大程度上影響了RGCN模型在異質網絡中鏈接預測任務的準確性。因此我們選擇FB15k-237與FB-Toy作為我們的主要評估數據集。

本文主要采用了準確率（Accuracy）評估指標，判斷關系類型的預測與標簽是否一致，公式如下：

其中，TP代表預測正確的正例樣本數，TN表示預測正確的負例樣本數，R為總樣本數。準確率越高，說明模型鏈接預測越準確。

4.2 對比模型

為了驗證鄰域采樣算法的有效性，我們將結合鄰域采樣進行訓練的RGCN模型與原始RGCN模型以及其他添加本文提出的鄰域采樣機制的GCN［4］、GAT［27］、GraphSAGE［5］模型進行比較。

1）RGCN：該模型將圖卷積應用到異質網絡中，能夠處理圖中不同的邊關系類型對節點嵌入的影響，適用于解決異質網絡鏈接預測以及實體分類問題。

2）RGCN+：添加了本文提出的鄰域采樣機制的RGCN模型。原始RGCN模型通過隨機邊采樣構建訓練圖，考慮對高度多關系數據的建模。

3）GCN+：該模型將GCN與本文提出的鄰域采樣機制相融合。原始GCN是在訓練中對整個圖進行操作的半監督方法，在學習圖表示方面表現優異。

4）GAT+：添加了本文提出的鄰域采樣機制的GAT模型。原始GAT在傳播過程引入自注意力（self-attention）機制，每個節點的隱藏狀態通過為其鄰居節點分配權重來計算。

5）GraphSAGE+：添加本文提出的鄰域采樣機制的GraphSAGE模型。GraphSAGE是一個利用節點特征信息為未知節點生成有效嵌入的通用歸納框架。

4.3 實驗參數設置

經過多次實驗，針對不同數據集，本文模型的超參數設置不同，具體如下。

默認設置RGCN模型層數為兩層。設置FB15k-237數據集在RGCN模型隱藏層的大小為256，學習率為0.0001，迭代次數為5；設置WN18數據集在RGCN模型隱藏層的大小為200，學習率為0.0005，迭代次數為25；對于FB-Toy數據集，其模型隱藏層的大小設為200，學習率設為0.0001，迭代次數為30。為了防止過擬合，上述三個數據集都使用了dropout［28］技術，統一設置為0.2，并且都選擇ADAM［29］作為優化器。經過多次實驗比較，本文鄰域采樣機制中采樣參數k,B選擇為k=1,B=7時，模型效果最好。

本文所使用的對比模型的超參數設置如下：對比模型默認層數為兩層。原始RGCN模型在不同數據集上超參數設置不同，FB-Toy數據集及WN18數據集的嵌入維度設為200，迭代次數為10000；FB15k-237數據集隱藏層的大小為500，迭代次數為10000；其余參數遵循原始論文設置。GCN+、GAT+、Graph SAGE+模型的超參數設置與本文模型在不同數據集上參數設置相同。

4.4 實驗結果與分析

4.4.1 鏈接預測任務評估指標對比

本文在不同數據集上的實驗結果如表2和圖3所示，其中表2中加粗的表示最好的結果。根據實驗結果，我們總結出如下重要發現。

圖3 鏈接預測準確率對比結果

表2 模型在各數據集的評估指標對比

隨著數據集規模的增大，添加了本文提出的鄰域采樣算法的模型性能基本上都在不斷地提升。與小規模數據集FB-Toy對比，RGCN+模型在大規模數據集FB15k-237數據集上性能提升了14.68%。而在GCN+模型上對應的數據為16.73%。此外，由于WN18數據集本身存在缺陷，導致了在RGCN+、GAT+和SAGE+模型上的表現并未與數據規模同步遞增。但是，在主要評估數據集FB-Toy以及FB15k-237上，數據規模越大，GAT+和SAGE+表現也越好。與小數據集FB-Toy相比，GAT+、SAGE+模型在大數據集FB15k-237上的鏈接預測準確率分別提升了7.63%、9.93%。綜上所述，本文提出的采樣方法有效且在大規模數據集上優勢明顯。

綜合考慮異質圖的關系類型有益于提升鏈接預測的準確性。在不同數據集上，RGCN+模型與基線模型相比，效果基本上都是最優的。在FB-Toy，Wn18，FB15k-237數據集上，RGCN+模型性能與其他基準模型相比平均提升了12.84%，15.69%，23.19%。其中，由于FB-Toy數據集過小，導致RGCN+與RGCN效果差異不大。這也說明了采樣方法在大規模數據集中才更加凸顯優勢。此外，在添加了采樣方法的GCN+，GAT+，SAGE+，RGCN+中，由于RGCN+額外考慮了異質圖中的關系類型，而其他模型忽略了這一因素，使得它們的表現不如RGCN+。

4.4.2 模型效率分析

我們通過在實驗中記錄模型訓練所需要的時間，證明了本文提出的采樣方法能夠減少模型訓練時間。具體數據如表3所示。結果表明在不同數據集上，添加本文提出的鄰域采樣算法能夠提高模型的訓練速度。在三個數據集上，RGCN+模型比RGCN模型運行時間平均減少了32281s。在RGCN上使用鄰域采樣算法不僅需要較少的內存空間，而且可以加快訓練過程的收斂速度。這是因為每個訓練階段涉及的空間和計算復雜度都較小。在每次批處理中，基于鄰域采樣的異質網絡鏈接預測算法模型在GUP加載的每個子圖內執行小批量隨機梯度下降。并在算法的后續運行過程中，前向傳播和后向傳播都在小而完整的鄰域子圖上進行，而不是對原始圖進行處理。綜上所述，本文提出的采樣方法能夠提升模型的運行效率。

表3 訓練時間對比（單位：s）

4.4.3 采樣參數敏感性分析

為了驗證采樣過程中鄰居數量對模型的影響，本文在三種數據集上對采樣參數B進行了敏感性分析。實驗結果如圖4所示，隨著采樣鄰居數量的遞增，在小規模數據集FB-Toy以及規模較大但存在缺陷的WN18數據集上，鏈接預測準確率整體呈上升趨勢，但幅度較小。而在大規模數據集FB15k-237，采樣鄰居數量越多，模型的性能也更佳，鄰居數量到達一定的值后，模型的性能趨于平穩。因此，綜合考慮訓練時間和模型性能，本文將參數b設為7進行對比實驗。

5 結語

本文提出了一種基于鄰域子圖采樣的訓練框架，該框架通過小批量訓練的方式實現了一種針對大規模異質圖的領域采樣方法。該方法采樣得到的子圖很好地保留了異質圖的結構信息，而且子圖內依然保持著良好的連通性。這樣就使得模型能夠在大規模圖上高效地進行訓練。此外，通過在子圖內進行小批量的隨機梯度下降的方式解決了梯度爆炸的問題。本文通過將采樣方法應用于鏈接預測問題來驗證其有效性。在多個真實網絡上的實驗表明，添加該采樣算法的關系圖卷積模型與基線相比能夠顯著提升鏈接預測的準確率。同時，模型的訓練速度也得到了顯著的提升。未來的研究方向是將該采樣方法與不同的模型結合應用到更多的實際問題中。