異質網中基于圖卷積神經網絡的鏈路預測方法

蔣宗禮，張文婷，張津麗

(北京工業大學 計算機學院，北京 100124)

0 引 言

隨著信息網絡的快速發展，對信息網絡進行鏈路預測已成為數據挖掘領域中的研究熱點。在社交網絡中，對于任意兩個還未互相關注的用戶，通過鏈路預測可以判斷他們是否是潛在的好友；在引文網絡中，鏈路預測能夠預測作者是否可能在未來進行合作。將網絡中的對象和關系分別簡化為節點和連邊，則在社交網絡和引文網絡中，節點和連邊類型都僅有一種，這樣的網絡稱為同質信息網絡。但是現實中網絡的節點或連邊類型往往不只一種[1]，這樣的網絡稱為異質信息網絡[2]。

目前信息網絡的鏈路預測方法主要分為基于相似度和基于網絡表征學習的方法。基于相似度的方法在不同網絡中的預測準確度差異明顯，通用性較差；基于網絡表征學習的方法大多數是針對同質信息網絡提出的，無法應用于更為復雜的異質信息網絡。由于異質網絡的復雜性和異質性特點，導致在異質網中的鏈路預測研究依然較少。考慮到異質網中節點類型的不同，本文在經典圖卷積神經網絡算法的基礎上進行改進，提出一種改進的逐層傳遞規則，有效處理不同類型的節點，對節點表征進行學習，并融合對抗學習優化節點表征。通過基于梯度提升樹的二分類算法預測鏈路是否存在，為異質網中的鏈路預測提供了新思路，有效提升了鏈路預測的準確性和穩定性。

1 相關研究

目前常用的鏈路預測方法主要為基于相似性指標的方法，CN指標通過衡量兩個節點之間的共同鄰居的數量作為相似性指標，共同鄰居越多，則連邊存在的可能性越大。PA指標基于兩個節點的度數作為相似性指標，連邊存在的可能性與節點度成正比。此外，其它的相似度指標還有基于路徑的KatZ指標、LP指標等，基于隨機游走的ACT指標、SimRank指標等[3]。基于相似性指標的鏈路預測方法主要的局限是對于不同的網絡，其預測性能并不穩定。另一類鏈路預測方法是基于最大似然估計的方法，主要有層次結構模型和隨機分塊模型，層次結構模型的問題是計算復雜度太高[4]，隨機分塊模型的整體表現比層次結構模型好，但是對于大規模網絡，其性能依然較差。

近年來的網絡表示學習為鏈路預測提供了新方法，網絡表示學習將信息網絡簡化為圖的形式，將圖中的節點嵌入到一個低維空間中[5]。通過網絡表示學習得到節點的低維特征表示，便可以根據節點表征進行鏈路預測。DeepWalk通過隨機游走和SkipGram算法得到節點的特征向量[6]。node2Vec[7]使用兩個參數p、q控制隨機游走的策略，使隨機游走在寬度優先策略和深度優先策略中保持平衡。LINE[8]考慮了節點的一階相似度和二階相似度，在稀疏網絡和稠密網絡中都有良好的表現。圖卷積神經網絡GCN[9]結合網絡結構和節點屬性，學習到的節點特征有效融合了其鄰居節點的特征。上述研究都是針對同質網的，而現實中的許多網絡是包含不同類型節點或關系的異質信息網絡。目前，異質網上的網絡表示學習方法仍然較少，且絕大部分是基于元路徑[10]的。Metapath2Vec[11]通過預先定義的元路徑模式進行隨機游走，生成符合元路徑模式的節點序列，最后使用基于異質網的SkipGram算法學習節點的特征向量。Hin2vec[12]同時學習節點和元路徑的特征向量，根據自動生成的多種元路徑對節點特征進行聯合學習。基于元路徑的方法主要的局限在于元路徑的選擇，往往需要預先進行大量的實驗和比較，才能在多種元路徑模式中找到較優的模式。

針對以上問題，本文提出異質網中基于圖卷積神經網絡的鏈路預測方法。通過對圖卷積神經網絡GCN進行改進，解決了GCN算法只適用于同質網的問題。改進后的方法能充分利用異質網絡的拓撲信息和屬性信息，學習不同類型節點的表征。為進一步提高節點表征的效果，融合對抗學習對節點表征進行優化。獲得節點的表征向量后，將鏈路預測問題轉換為二分類問題，根據兩個節點表征向量的Hadamard積構造節點之間連邊的表征向量，并結合基于GBDT算法的二分類器進行鏈路預測。

2 問題定義

2.1 異質信息網絡

對于一個信息網絡G(V,E,Tv,Te)，V表示節點集合，E表示連邊集合，Tv表示節點類型集合，Te表示連邊類型集合。每個節點v∈V都對應著其節點類型φ(v)∈Tv， 每條連邊e∈E也都對應著其連邊類型ψ(e)=Te。 當節點類型或連邊類型大于1時，即 |Tv|>1或 |Te|>1時，稱G為異質信息網絡。圖1所示的異質信息網絡包含User和Store兩種類型的節點。

圖1 異質信息網絡

2.2 異質網中的鏈路預測

鏈路預測的目標是根據節點間已知連邊及節點的屬性，預測節點間未知連邊存在的可能性[13]。例如，在異質信息網絡G中，節點v1的類型為φ(v1)=a1， 節點v2的類型為φ(v2)=a2， 節點類型a1和a2之間存在連邊類型r1， 但節點v1和v2之間尚未觀測到連邊。鏈路預測的目標就是通過網絡中已知的拓撲信息和節點的屬性信息，預測節點v1和v2之間是否存在連邊。例如，預測User1和Store1是否相連接。

3 異質網絡鏈路預測模型

本文提出的鏈路預測模型如圖2所示。首先通過HeGCN層、對抗學習層對節點的表征進行學習，通過損失函數的最小化對模型進行更新、優化，最后構造連邊表征并預測網絡中的鏈路。

圖2 異質網絡鏈路預測模型

3.1 逐層傳遞規則

圖卷積神經網絡GCN是一種強大的網絡表示學習方法，它結合網絡的拓撲結構和節點的屬性信息，將網絡中的節點表示為低維稠密的特征向量，僅通過兩層GCN得到的節點表征就能夠十分有效地對原始網絡進行表示。但是GCN的逐層傳遞規則只適用于同質信息網絡，針對這一不足，本文提出一種改進的HeGCN逐層傳遞規則，可以同時處理兩種不同類型的節點。

3.1.1 GCN逐層傳遞規則

圖卷積神經網絡GCN的逐層傳遞規則如下

(1)

(2)

(3)

由式(2)、式(3)可知，GCN只能接受N×N的方陣作為鄰接矩陣輸入，而異質信息網絡中不同類型節點的個數并不相同，所以GCN的逐層傳遞規則不能直接用于異質信息網絡。

3.1.2 改進的HeGCN逐層傳遞規則

由于GCN處理的是相同類型的節點，令節點vi的鄰居節點表示為 {vj|Aij=1,j∈[1,N]}， 則vi的所有鄰居節點vj的類型與vi相同，由此可知在同質信息網絡中，全部節點的鄰居節點集合Vneighbor?V。 因此在式(2)中的屬性矩陣X是由集合V中節點的屬性向量構成的。而在異質信息網絡中，鄰居節點的類型不同。表1給出了異質網絡中節點的相關符號表示，令節點vi∈VN的鄰居節點表示為 {vj|Aij=1,vj∈VM,j∈[1,M]}， 可以看出vi的所有鄰居節點vj的類型與vi不同，即圖中所有節點的鄰居節點的集合Vneighbor∩V=?。

本文在GCN的基礎上進行改進，提出了適用于異質網的HeGCN逐層傳遞規則。對于所有vi∈VN， 其鄰居節點vneighbor∈VM， 對于所有vj∈VM， 其鄰居節點vneighbor∈VN。 由于每個節點的表征與其鄰居節點的表征相關聯，因此在改進的逐層傳遞規則中，令vi∈VN對應的屬性矩陣為XM； 同理，vj∈VM對應的屬性矩陣為XN， 如式(4)、式(5)所示。由于鄰居節點的類型不同，在對鄰接矩陣A的預處理方面，HeGCN應當做如下改變：

表1 符號表示

(1)節點與其自身無連邊。因此不應將初始鄰接矩陣與維度為N×N的單位矩陣相加；

綜上，得到HeGCN中的兩條逐層傳遞規則：

對于VN， 逐層傳遞規則為

(4)

對于VM， 逐層傳遞規則為

(5)

其中，A表示鄰接矩陣，AT表示鄰接矩陣的轉置。DA是A的度數矩陣，DAT是AT的度數矩陣，即

(6)

3.2 HeGCNE模型設計

HeGCNE的模型結構如圖3所示，下文將分別說明每部分的具體細節。

圖3 HeGCNE模型結構

3.2.1 HeGCN層

將改進的逐層傳播公式應用到HeGCN層中，通過兩層HeGCN結構，生成節點表征的高斯分布，如式(7)所示

(7)

假設節點的先驗分布和變分后驗分布都服從高斯分布[14]，則有

(8)

(9)

(10)

(11)

由于在使用后向傳播算法對參數進行優化時，需要滿足可微條件，因此通過重參數化[14]將節點表征的高斯分布qφ1(ZN|A,XN) 和qφ2(ZM|A,XM) 轉換為確定且可微的ZN和ZM。 其中，ZN的維度為N×D，ZM的維度為M×D， 即節點的表征向量都是D維。

3.2.2 對抗學習層

為進一步優化學習到的節點表征，在HeGCN層的基礎上進行對抗學習[15]。生成對抗模型一般由兩部分組成，分別是生成模型和判別模型。HeGCN層可以看作是生成模型，生成節點的特征分布qφ1(ZN|A,XN) 和qφ2(ZM|A,XM)。 判別模型對輸入的樣本進行判斷，當樣本來自先驗分布p(ZN) 或p(ZM) 時，將其判斷為真樣本；當樣本來自生成的節點特征分布qφ1(ZN|A,XN) 或qφ2(ZM|A,XM) 時，將其判斷為假樣本。判別模型的目標是不斷提高判斷的準確度，也就是要盡可能準確的對真假樣本進行區分；而生成模型的目標是生成盡可能混淆判別模型的樣本。在兩方博弈的過程中，判別模型和生成模型的能力都得到了提高，生成的節點特征分布更接近真實的節點特征分布，因此優化了學習到的節點表征。

3.3 HeGCNE模型優化

(12)

(13)

(14)

在對抗學習的過程中，一方面需要提高判別模型D準確判斷的能力，即提高z～p(Zi)[log(D(ZN))] 和z～p(Zj)[log(D(ZM))]， 對于從節點特征的先驗分布中采樣的樣本，判別模型D要將其判斷為真；對于從生成的節點特征分布中采樣的樣本，判別模型D要將其判斷為假。另一方面需要提高生成模型G生成假樣本的能力，即提高XN[log(1-D(G(XN,A)))] 和XM[log(1-D(G(XM,A)))]， 使其盡可能混淆判別模型D，令判別模型D判斷失誤。因此，損失函數的第3部分為

(15)

3.4 連邊表征構造與二分類

通過3.3節對模型進行訓練，得到了節點表征ZN和ZM，本文沒有直接根據重建的鄰接矩陣或通過計算節點表征的余弦相似度進行鏈路預測，而是將鏈路預測問題轉化為二分類問題，先構造連邊表征，如圖4所示。然后將連邊表征與梯度提升樹(gradient boosting decide tree，GBDT)算法相結合進行二分類，若節點對有連邊存在，則其對應的標簽為1，否則標簽為0。通過對兩個節點表征做hadamard積可以有效融合節點表征，構造出連邊表征，如式(16)所示。其中，⊙表示hadamard積， 表示節點vi與節點vj之間的邊，vi∈VN，vj∈VM

Feature()=Feature(vi)⊙Feature(vj)

(16)

圖4 連邊表征構造

使用梯度提升樹進行二分類時，在算法的每一步都會通過一棵決策樹對分類器當前的殘差進行擬合，訓練出一個新的弱分類器，將所有的決策樹綜合起來，就可以得到一個強分類器。使用梯度提升樹分類的優點主要有3點：①在每一棵決策樹對殘差的計算中，被正確分類的樣本所占的權重減小，分類錯誤的樣本所占的權重增大，即著重考慮那些被錯誤分類的樣本，使得泛化能力得到增強。②梯度提升樹中的非線性變化較多，分類能力強。③梯度提升樹可以對每一維特征的重要程度排序，高效且自動地進行特征組合。

4 實驗與分析

4.1 數據集

本文采用DBLP和YELP兩個真實數據集進行實驗。在DBLP數據集中，有論文和作者兩種類型的節點，表示論文的節點共有14 376個，表示作者的節點共有14 475個，實驗對“論文-作者”進行鏈路預測，即判斷論文是否被作者所寫。在YELP數據集中，有商店和用戶兩種類型的節點，表示商店的節點共有2614個，表示用戶的節點共有1286個，實驗對“商店-用戶”進行鏈路預測，即判斷用戶是否去過商店。數據集的信息見表2。

表2 數據集的具體信息

4.2 評價指標

鏈路預測任務的常用評價指標為AUC和AP指標。AUC指標是ROC曲線下的面積，表示隨機抽取一個正例和負例，分類器將正例排在負例前面的概率。AUC值越大，意味著分類器越有可能將正例排在負例前面，因此分類器的表現越好，AUC值越接近1，而一個純隨機分類器的AUC值為0.5。在鏈路預測任務中，AUC值越大，表示越有可能從所有的節點對中，選出有連邊存在的節點對。AP指標是PR曲線下的面積，在鏈路預測任務中，AP指標也可以用來衡量預測的整體表現。

4.3 基準算法與參數設置

為了驗證本文方法的有效性，分別與PA、DeepWalk、Hin2vec進行對比。HeGCNE的參數設置如下，HeGCN層的維度分別設置為64和32，對抗學習層的維度分別設置為32和64，迭代次數設置為200，學習率為0.01，采用Adam 算法進行模型的更新優化。

(1)PA指標：基于節點度數作為鏈路預測的指標，其思想是連邊存在的概率與節點度數成正比，因此節點x和節點y之間連邊的存在概率與兩節點度數的乘積成正比。分別用k(x)、k(y) 表示節點x和節點y的度數，則PA的相似度計算公式為Sxy=k(x)·k(y)；

(2)DeepWalk：通過一系列的隨機游走生成固定長度的由節點構成的隨機游走序列，將SkimGram算法應用到隨機游走序列中學習節點表征。得到節點表征后，通過重建鄰接矩陣進行鏈路預測；

(3)Hin2vec：同時學習節點和元路徑的表征，結合多個元路徑的信息，通過多任務學習生成節點的表征。得到節點表征后，通過重建鄰接矩陣進行鏈路預測。

4.4 實驗結果與分析

在DBLP和YELP數據集上，隨機去掉20%的邊作為測試集，剩余80%的邊作為訓練集，將HeGCNE和3種基準算法進行對比，實驗結果見表3。

表3 不同算法的鏈路預測性能對比/ %

從表3的數據可以看出，在DBLP和YELP數據集上，HeGCNE相對于3種基準算法的性能均有所提升，且AUC、AP評價指標均達到83%以上，說明本文提出方法可以有效地對異質信息網絡中的鏈路進行預測。在DBLP數據集上，HeGCNE的AUC指標比PA、DeepWalk、Hin2vec分別提高了25.6%、16.4%、9.8%；HeGCNE的AP指標比PA、DeepWalk、Hin2vec分別提高了17.3%、4.5%、3.8%。在YELP數據集上，HeGCNE的AUC指標比PA、DeepWalk、Hin2vec分別提高了12.4%、5.0%、4.0%；HeGCNE的AP指標比PA、DeepWalk、Hin2vec分別提高了9.9%、4.6%、1.4%。分析在不同數據集上4種算法的表現，可以發現在YELP數據集上4種算法的表現整體都優于DBLP數據集，這是因為YELP數據集的網絡稠密程度相對更高，所以預測的準確性更高。而DBLP數據集的網絡極為稀疏，在這種情況下，PA算法的準確性明顯降低，說明了PA算法對于不同網絡的預測性能并不穩定。本文方法在稀疏的網絡中依然能夠取得良好的表現，驗證了本文方法的有效性和穩定性。

上述實驗結果表明，本文方法能夠有效提高鏈路預測的性能，而訓練集與測試集的劃分比例、學習節點特征時的迭代次數也會對鏈路預測的結果產生影響，因此采用控制變量法，分別改變訓練集的比例、迭代次數進行實驗，并對實驗結果進行比較，如圖5～圖8所示。

圖5 不同訓練集比例的AP值

圖6 不同訓練集比例的AUC值

圖7 不同迭代次數的AP值

圖8 不同迭代次數的AUC值

首先，固定訓練次數為200次，將訓練集的比例分別設置為10%、30%、50%、70%、90%。從圖5、圖6可以看出，在數據集YELP和DBLP上，AUC指標和AP指標均隨著訓練集比例的增加而增大，且增長幅度呈逐漸減弱的趨勢。當訓練集的比例為70%時，在兩個數據集上都有著不錯的預測效果，AUC指標和AP指標都在0.8以上，在YELP數據集上，兩個指標可以達到0.9左右。另外，當訓練集比例為30%時，在YELP數據集上兩個指標接近0.8，這說明對于較為稠密的網絡，僅已知小部分的拓撲信息，也可以達到良好的預測效果。

其次，固定訓練集的比例為80%，將訓練次數分別設置為50、100、200、500、1000次。從圖7、圖8可以看出，當迭代次數在200次左右時，AUC指標和AP指標達到較高水平，之后隨著迭代次數的增加，呈現持平或下降趨勢，這是因為當模型訓練的迭代次數過多時，會出現過擬合現象，因此迭代次數并不是越多越好，選取合適的迭代次數即可。對于本文所提方法，較少的迭代次數即可獲得不錯的預測結果。

5 結束語

本文提出了一種異質網中基于圖卷積神經網絡的鏈路預測方法，綜合異質網絡的結構信息和語義信息，學習不同類型節點的表征，并融合對抗學習來優化節點表征。獲得節點表征后，通過求Hadamard積構造連邊表征，使用基于梯度提升樹的二分類方法進行鏈路預測。在數據集DBLP和YELP上，將本文方法與PA、DeepWalk、Hin2Vec這3種基準算法進行對比。實驗結果表明，本文方法使異質網絡中鏈路預測的準確性和穩定性都有所提升。但本文方法只能同時處理具有兩種類型節點的異質信息網絡，在未來研究中，可以從多類型節點的輸入和并行性方面進行改進。