異質(zhì)網(wǎng)中基于圖卷積神經(jīng)網(wǎng)絡的鏈路預測方法

蔣宗禮，張文婷，張津麗

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

0 引 言

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

目前信息網(wǎng)絡的鏈路預測方法主要分為基于相似度和基于網(wǎng)絡表征學習的方法?；谙嗨贫鹊姆椒ㄔ诓煌W(wǎng)絡中的預測準確度差異明顯，通用性較差；基于網(wǎng)絡表征學習的方法大多數(shù)是針對同質(zhì)信息網(wǎng)絡提出的，無法應用于更為復雜的異質(zhì)信息網(wǎng)絡。由于異質(zhì)網(wǎng)絡的復雜性和異質(zhì)性特點，導致在異質(zhì)網(wǎng)中的鏈路預測研究依然較少?？紤]到異質(zhì)網(wǎng)中節(jié)點類型的不同，本文在經(jīng)典圖卷積神經(jīng)網(wǎng)絡算法的基礎上進行改進，提出一種改進的逐層傳遞規(guī)則，有效處理不同類型的節(jié)點，對節(jié)點表征進行學習，并融合對抗學習優(yōu)化節(jié)點表征。通過基于梯度提升樹的二分類算法預測鏈路是否存在，為異質(zhì)網(wǎng)中的鏈路預測提供了新思路，有效提升了鏈路預測的準確性和穩(wěn)定性。

1 相關研究

目前常用的鏈路預測方法主要為基于相似性指標的方法，CN指標通過衡量兩個節(jié)點之間的共同鄰居的數(shù)量作為相似性指標，共同鄰居越多，則連邊存在的可能性越大。PA指標基于兩個節(jié)點的度數(shù)作為相似性指標，連邊存在的可能性與節(jié)點度成正比。此外，其它的相似度指標還有基于路徑的KatZ指標、LP指標等，基于隨機游走的ACT指標、SimRank指標等[3]?；谙嗨菩灾笜说逆溌奉A測方法主要的局限是對于不同的網(wǎng)絡，其預測性能并不穩(wěn)定。另一類鏈路預測方法是基于最大似然估計的方法，主要有層次結(jié)構(gòu)模型和隨機分塊模型，層次結(jié)構(gòu)模型的問題是計算復雜度太高[4]，隨機分塊模型的整體表現(xiàn)比層次結(jié)構(gòu)模型好，但是對于大規(guī)模網(wǎng)絡，其性能依然較差。

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

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

2 問題定義

2.1 異質(zhì)信息網(wǎng)絡

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

圖1 異質(zhì)信息網(wǎng)絡

2.2 異質(zhì)網(wǎng)中的鏈路預測

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

3 異質(zhì)網(wǎng)絡鏈路預測模型

本文提出的鏈路預測模型如圖2所示。首先通過HeGCN層、對抗學習層對節(jié)點的表征進行學習，通過損失函數(shù)的最小化對模型進行更新、優(yōu)化，最后構(gòu)造連邊表征并預測網(wǎng)絡中的鏈路。

圖2 異質(zhì)網(wǎng)絡鏈路預測模型

3.1 逐層傳遞規(guī)則

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

3.1.1 GCN逐層傳遞規(guī)則

圖卷積神經(jīng)網(wǎng)絡GCN的逐層傳遞規(guī)則如下

(1)

(2)

(3)

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

3.1.2 改進的HeGCN逐層傳遞規(guī)則

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

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

表1 符號表示

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

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

對于VN， 逐層傳遞規(guī)則為

(4)

對于VM， 逐層傳遞規(guī)則為

(5)

其中，A表示鄰接矩陣，AT表示鄰接矩陣的轉(zhuǎn)置。DA是A的度數(shù)矩陣，DAT是AT的度數(shù)矩陣，即

(6)

3.2 HeGCNE模型設計

HeGCNE的模型結(jié)構(gòu)如圖3所示，下文將分別說明每部分的具體細節(jié)。

圖3 HeGCNE模型結(jié)構(gòu)

3.2.1 HeGCN層

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

(7)

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

(8)

(9)

(10)

(11)

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

3.2.2 對抗學習層

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

3.3 HeGCNE模型優(yōu)化

(12)

(13)

(14)

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

(15)

3.4 連邊表征構(gòu)造與二分類

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

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

(16)

圖4 連邊表征構(gòu)造

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

4 實驗與分析

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

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

表2 數(shù)據(jù)集的具體信息

4.2 評價指標

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

4.3 基準算法與參數(shù)設置

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

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

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

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

4.4 實驗結(jié)果與分析

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

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

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

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

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

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

圖7 不同迭代次數(shù)的AP值

圖8 不同迭代次數(shù)的AUC值

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

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

5 結(jié)束語

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