動態圖的鏈接預測模型

唐晨，趙杰煜，葉緒倫，鄭陽，俞書世

寧波大學 信息科學與工程學院，浙江 寧波315211

互聯網的普及產生了大量的圖結構數據，其中蘊含著豐富的信息。雖然這些信息很難直接獲取，但是蘊含很高的商業價值和社會價值。鏈接預測作為圖領域的典型問題，體現在現實生活的方方面面。例如在社交領域中，鏈接預測可以預測新朋友關系的產生，或是給用戶推薦新的朋友。在電子商務領域，鏈接預測可以為用戶提供個性化的商品推薦。在生物學領域，鏈接預測可以預測蛋白質在交互作用的過程中可能發生的反應，亦可發現基因序列中導致疾病的異常基因。

目前，靜態圖的鏈接預測模型已經取得了非常好的效果，但是在現實世界中，圖的節點和鏈接通常是隨著時間變化的，靜態模型難以保留時域上的特征。比如在社交網絡中，任何時刻用戶都有可能因為部分屬性發生改變導致新鏈接的產生或者舊鏈接的消失。如圖1 所示，在-1 時刻，節點2 與節點1僅有一個共同鄰居節點3。在時刻，節點1 和節點5 之間新增了一條鏈接，則節點2 和節點1 的共同鄰居增長到兩個，即節點3 和節點5。雖然時刻節點1、2、4 都有相同的鄰居節點，但是從時域的角度看，節點1 和節點2、4 共同鄰居的數量呈現增加的趨勢，因此在+1 時刻，節點1 和節點2、4 之間建立鏈接的可能性較大，而節點2 和節點4 雖然共同鄰居也是節點3 和節點5，但是在時域上，兩者的鄰居節點的數量比較穩定，在+1 時刻建立鏈接的可能性較小。由此可見靜態圖的鏈接預測模型在動態圖上的表現非常有限，無法捕捉圖在時間維度上變化的規律性，這更加凸顯了研究動態圖鏈接預測模型的必要性。

圖1 動態圖演變示意圖Fig.1 Schematic diagram of dynamic diagram evolution

針對動態圖的鏈接預測問題，傳統的基于隨機游走和矩陣分解的模型具有計算效率高的優點，但其無法利用深層次的特征，而且大部分模型最終會采用線性的方法進行預測。目前比較主流的基于深度學習的做法是將圖神經網絡（graph neural network，GNN）與循環神經網絡（recurrent neural network，RNN）相結合。先利用GNN 學習靜態圖的節點嵌入，然后將節點嵌入作為時間序列信息輸入到RNN 模型。

然而，上述方法沒有考慮節點分類任務和鏈接預測任務的區別。分類任務更關注的是圖局部特征，鏈接預測問題更加關注的是圖全局特征。全局特征代表了圖的整體表現特性，一般屬于統計的范疇，而局部特征更加關注個體的細節，一般屬于組合的范疇。圖在時間維度的演化，是全局特征和局部特征共同作用的結果，全局特征包含了局部特征的成分，局部特征又在其某一方面反映了全局的信息。在動態圖的鏈接預測問題上，則更應該關注不同時刻的圖的共性。不可否認，全局特征是多個局部特征歸一化的結果。因此，在鏈接預測任務中，提取特征這一部分需要一個合適的損失函數去均衡全局特征和局部特征。受到Hjelm 等人和Velickovic 等人工作的啟發，本文將利用圖卷積（graph convolutional network，GCN）和互信息（mutual information，MI）的優點去構造特征提取模塊。同時，為此模塊設計新的損失函數，該損失能在保證潛在特征更多地保留原始數據的概率特性的情況下，獲取有效的全局特征表示，這是其他動態圖鏈接預測模型沒有考慮的。

全局特征是所有節點特征聚合的結果，如果其中某些節點特征發生異常，將會嚴重影響全局特征的提取。因此本文將全局特征表示為向量的形式，并將其本身視為隨機變量，其演化過程視為寬平穩隨機過程，那么它將存在兩個概率性質，即在一個時間窗口內，全局特征的期望為常數，自相關函數只和時間差有關。依照上述規則，本文設計了一個感知模塊，約束全局特征在時域維度上以一個寬平穩隨機過程的方式演化。

為了探索圖在時域上的演化規律，之前的研究是將所有節點特征作為長短期記憶網絡（long shortterm memory networks，LSTM）的輸入，但是模型的學習能力有限，它無法用一組參數捕捉到所有節點在時域上的演化規律。雖然本文采用LSTM 來捕捉時域上的特征，但是不同的是本文用全局特征代替所有節點特征作為LSTM 的輸入。最后利用預測得到的全局特征構造鏈接，與真實的鏈接進行對抗訓練，使預測值更加接近真實值。

本文的創新有以下兩點：

（1）設計了一個新穎的全局特征提取模塊，用于挖掘全局特征在動態圖上的演變規律。該模塊以GCN 模型為基礎，利用全局特征和局部特征的互信息構造對比損失函數，采用對抗的方式訓練，保證了全局特征在時域上的傳遞。

（2）設計了感知模塊，對全局特征的平滑性做了約束。該模塊從寬平穩隨機過程獲得靈感，通過對均值和自相關函數進行限制，達到規范全局特征的演化過程，是個全局的概念。

1 相關工作

1.1 傳統的動態圖鏈接預測模型

傳統的動態圖鏈接預測模型大部分是先學習節點嵌入，然后利用傳統機器學習方法進行分類。節點嵌入學習主要分為基于隨機游走和基于矩陣分解兩種。自從Perozzi 等人和Grover 等人分別提出DeepWalk 模型和node2vec 模型以來，基于隨機游走的方法廣泛應用于圖的特征提取。比如在動態圖上，Nguyen 等人關注時間的重要性，給每條鏈接的存在時間定義一個區間，剔除隨機游走產生的不合理的序列。Yu等人認為如果圖不發生實質性的變化，那么只需要在一個連續的時間段中重新采樣一些隨機游走序列即可。Ahmed 等人利用隨機游走為每個節點構造子圖，在該節點周圍的子圖內計算節點與其鄰居之間的相似度分數，整合局部和全局拓撲信息。基于矩陣分解的方法通常是根據特征值將一個大矩陣拆分成幾個小矩陣相乘的形式。比如Li 等人和Zhu 等人提出的動態屬性網絡嵌入（dynamic attributed networks embedding，DANE）模型和動態高階鄰近保留嵌入（dynamic high-order proximity preserved embedding，DHPE）模型，都是基于廣義奇異值分解（generalized singular value decomposition，GSVD）和矩陣攝動理論（matrix perturbation theory，MPT），在保留高階相似性的同時，動態更新動態網絡的節點表示。Ma 等人設計了一種新的矩陣分解規則，并從理論和實驗上證明了算法的收斂性和準確性。

1.2 基于圖神經網絡的動態圖鏈接預測模型

由于圖卷積神經網絡在靜態圖上的強大性能，一些研究者將GCN 應用于動態圖的鏈接預測任務上，并取得了階段性的研究成果。比如Seo 等人提出了圖卷積循環網絡模型（graph convolutional recurrent network，GCRN），該模型有兩種形式：第一種是利用Defferrard 等人提出的GCN 模型提取靜態圖的特征，然后將特征作為LSTM 的輸入；第二種是在第一種的基礎上將LSTM 中的矩陣乘法替換成GCN 的操作。Manessi 等人引入殘差網絡的思想，將GCN 和LSTM 結合提出了瀑布動態圖卷積神經網絡（waterfall dynamic graph convolutional neural network，WD-GCN）和級聯動態圖卷積神經網絡（concatenate dynamic graph convolutional neural network，CD-GCN）模型，并成功地將模型從節點任務拓展到了圖任務上，在真實數據集上取得了很好的分類效果。Narayan 等人先利用PATCHY-SAN（PATCHY select-assemble-normalize）提取圖的空間特征，然后結合LSTM 提取時域特征，提出循環圖卷積神經網絡（recurrent neural network on graph convolutional neural network，RgCNN）模型并在真實數據集上取得了優于Manessi 等人的效果。Pareja 等人將關注點聚焦在模型本身的適應性上而不是節點的嵌入上，提出了演化圖卷積神經網絡（evolving graph convolutional network，EvolveGCN）模型，該模型不訓練GCN 的參數，而是去訓練RNN 模型的參數，使模型參數不會隨時間增長而增長。Lei 等人考慮到動態圖在演化過程中的非線性特征，引入生成對抗網絡（generative adversarial networks，GAN），結合GCN和LSTM提出了GCN-GAN模型。

2 動態圖鏈接預測模型

2.1 問題定義

2.2 整體架構

本文提出了一種新的非線性時序預測模型LPMDG（link prediction model for dynamic graphs），解決動態圖的鏈接預測問題。模型整體架構如圖2所示，主要由四部分組成：（1）結構特征提取模塊；（2）全局特征約束模塊；（3）時域特征提取模塊；（4）對抗網絡訓練模塊。

圖2 LPMDG 整體框架圖Fig.2 LPMDG overall framework diagram

首先，選取一個合適的時間窗口大小，利用GCN 模型分別提取這個靜態圖的節點特征，通過優化本文設計的損失函數，獲取圖的全局特征。再將個全局特征輸入到全局特征約束模塊，保證全局特征在時域上表現為寬平穩隨機過程。接著，將全局特征輸入到時域特征提取模塊，抓取時域上的非線性特征。最后，將（1）（2）（3）視為一個生成器，另外設計一個全連接網絡作為判別器，利用GAN 的訓練策略生成高質量的鄰接矩陣。下面將詳細介紹LPMDG 模型的四部分。

由于靜態圖原始的節點特征通常是按照一定的主觀模式提取的，過于冗余，文中提出了結構特征提取模塊，該模塊是利用GCN 和對抗訓練方式，對原始特征進行編碼，以獲取節點的潛在表示以及圖的全局特征。其中，GCN 是卷積神經網絡（convolutional neural network，CNN）在非歐數據上的擴展，自Kpif利用GCN 在半監督節點分類任務上取得卓越成果后，GCN 被廣泛應用于提取圖的結構特征，本文亦通過GCN 提取節點特征中最關鍵的成分。對抗訓練方式能協助GCN 模型挖掘特征不同維度之間的非線性關系。假設存在一個節點數為的圖，GCN 模型需要先得到圖的鄰接矩陣∈R和節點的特征矩陣∈R，然后利用式（2）進行相鄰層之間的更新迭代。

為了得到全局特征，本文假設存在單射函數:R→R，該函數能將節點特征映射成全局特征。眾所周知，最優的全局特征應該滿足兩點要求：（1）能最大程度地保留圖的信息；（2）節點特征通過神經網絡學習后依然能保留全局特征的成分。為了保證GCN 模型提取的全局特征能滿足要求（1），本文引入互信息理論加以分析，互信息是度量兩個隨機變量之間的關聯程度，它表示一個隨機變量中包含另一個隨機變量的信息量（本文將節點特征和全局特征視為兩個隨機變量），值越大則兩個隨機變量相關性越強，互相包含的信息量也越多。形式上可以表示成：

其中，(*,*)表示互信息量，表示KL 散度。下面本文將從概率的角度分析為什么互信息能增強全局特征和節點特征的聯系。

互信息本身難以優化，但是注意到，如果將兩個變量分開考慮（樣本來自()()）和綜合考慮（樣本來自(,)）導致結果差別很大，那么就可以說明這兩個變量、的關系很緊密。因此，為了優化問題，本文通過固定樣本來源（(,)），以計算模型錯誤分類的概率值之和，并將其命名為關聯距離（correlation distance，CD）。

（關聯距離）假設存在兩個集合、，并且滿足||≤||，{(,)}表示從聯合分布(,)采樣得到的樣本，則分類器將采樣的樣本判定為邊緣分布()()的概率之和被定義為關聯距離，形式上可寫成：

其中，Ω={Gs|Fs=(Gs)}。據此可以進一步得到關聯距離的上界：

由此，可以得到定理1。

假設兩個集合、存在單射的關系，則最小化兩者關聯距離的誤差上界等同于最大化兩者的互信息。

上式可作如下理解，當、之間的互信息逼近上界時，(|)向1 逼近，這與、一一對應等價。因此得出最小化關聯距離等同于最大化互信息的結論。

因為=()，并且具有反函數，所以可逆推=()，進而可得：

從形式上看，全局特征和高階特征的關系滿足定理1 的條件，同理可得：最小化全局特征和高階特征的關聯距離等價于最大化兩者的互信息，即：

綜合上述結論，可以總結出這樣一條規律：一定條件下，全局特征的學習，在滿足Infomax 準則時達到最優，即輸入和輸出的互信息最大時。為此，本文采用如下損失函數進行對抗訓練：

其中，表示判別器，X表示潛在特征，表示負樣本的特征。

雖然動態圖的演化主要表現在時間維度上，但是內在驅動卻是靜態圖的規律性。平穩過程是統計特性不隨時間變化而改變的隨機過程，是時序分析中尋找共性特征的重要工具，最常見的可分為嚴平穩過程（strictly stationary process，SSP）和寬平穩過程（weakly stationary process，WSP）。SSP 要求一切概率性質都固定，這在統計上無法驗證，而WSP 要求相對寬松，只需要期望和自相關函數不隨時間變化而改變即可。因此，本文假設全局特征在時域上是一個寬平穩隨機過程，并設計與之對應的感知模塊，該模塊收集一個時間窗口的全局特征，并且將這些特征作為采樣點去擬合整個時域演化曲線的概率特性，以此逼近真正的寬平穩隨機過程。

若用{ε|∈}表示隨機過程，則WSP 的兩個性質在形式上可以表示成：

為了讓上述兩個公式具有現實意義，給出定理2：

若存在集合={ε|∈}，且關系：(ε,ε)=(-)成立，則的子集也滿足關系。

顯然，在一個時間窗口中的全局特征{(-+1),(-+2),…,()}，其自相關函數滿足定理2：

同理，可得期望的表現形式：

其中，表示期望，(*,*)表示自相關函數，表示期望函數，表示隨機變量，表示函數，()表示時刻GCN 提取的全局特征。若自相關函數可逆，則由上述式（12）、式（13）和定理2，可以進一步構造損失函數：

其中，⊙表示哈達瑪積，表示時間窗口的大小，-表示時間差，將-進行one-hot 編碼后作為標簽，與全連接網絡MLP 的輸出構造優化目標。

RNN 系列的模型是解決時域問題的有效方法，LSTM 是一種特殊的RNN，它通過利用門機制解決了RNN 在訓練過程中梯度消失和梯度爆炸的問題。為了捕獲圖序列在時間維度上的長短依賴關系，本文將GCN 提取的全局特征{(-+1),(-+2),…,()}作為LSTM 的輸入數據。通常標準的LSTM 包含三個門（遺忘門、輸入門、輸出門）和一個記憶細胞。例如在時刻，LSTM將-1 時刻的細胞狀態向量c和隱狀態向量h和時刻的輸入向量()同時作為輸入，然后輸出當前時刻的狀態向量h：

LSTM 具體的更新步驟如下所示：

其中，i、o、f、c和h分別表示輸入門、輸出門、遺忘門、細胞狀態、隱狀態；{θ,θ,θ,θ,b,b,b,b}分別表示對應的網絡參數；⊙表示哈達瑪積。激活函數如下：

當()經過LSTM 模型之后，得到預測的+1 時刻隱狀態h。本文在LSTM 之后另設計一個全連接神經網絡，該網絡以h作為輸入，輸出維度為×，即預測的鄰接矩陣ˉ。為了訓練LSTM，本文構造均方差損失函數：

為了探索動態圖在時域上演化規律的一致性，本文利用GAN 來提高LSTM 的性能。經典的GAN由一個生成器和一個判別器組成，其優化過程采用極小極大的策略。一方面，生成器生成偽數據欺騙判別器，讓判別器無法區分數據的真偽；另一方面，判別器一直優化性能，盡可能地區分真數據和偽數據。形式上表示為：

其中，和表示生成器和判別器的網絡參數。但是難以直接訓練，通常是采用控制變量法將生成器和判別器分開訓練，先訓練判別器，然后訓練生成器，如此反復迭代直至模型收斂，兩者的優化目標如下所示：

總結上述各部分，可得模型LPMDG 的訓練過程，如算法1 所示。

LPMDG 算法

3 實驗

3.1 數據集

為了驗證LPMDG 模型的有效性，本文在三個常用數據集上進行了實驗，這三個數據集的具體情況如表1 所示。

表1 數據集的具體情況Table 1 Details of dataset

USCB是衡量無線網狀網絡中鏈接質量的數據集，圖中的節點表示電腦主機，圖中的鏈接權重表示某個時間片內兩個主機之間的流量或者鏈接存在的質量。為了構造無權無向圖，本文設置一個質量的閾值，權重大于閾值設為1，否則設為0。SBM是隨機圖模型生成的圖，它按一定的規則構成社區并模擬社區的演化。AS是一個由路由器組成的通信網絡，圖中節點表示路由器，圖中鏈接表示路由器之間的流量交換，與處理USCB 數據集的方法相同，本文將AS 數據集設計成無權無向圖的演化序列。

本文采用MSE（mean square error）和AUC（area under the curve）兩個標準來評價模型的性能。MSE是最常見的評價指標之一，它通過逐點比較預測值和真實值的距離得到模型性能的量化結果。AUC 是ROC（receiver operating characteristic curve）曲線下的面積，而ROC 曲線的橫縱坐標是由真陽性率（true positive rate，TPR）和偽陽性率（false positive rate，FPR）構成。AUC 值越大表示當前的分類器越有可能將正樣本排在負樣本的前面，從而說明模型的分類效果更好。

為了驗證模型的泛化能力，本文將提出的模型和下面四個模型進行比較：

（1）GCN：第一個對比的模型是靜態的GCN 模型，該模型沒有任何針對時域信息的處理，僅對每一個時間片的靜態圖進行建模。

（2）GCN-GRU：是在GCN 模型的基礎上，對每個節點的嵌入利用GRU（gated recurrent unit）遞歸模型進行聯合訓練。

（3）EnvolveGCN：利用RNN去更新GCN的參數，達到捕捉圖序列動態性的目的，其中EnvolveGCN-h和EnvolveGCN-o 的區別在于RNN 的選取上，前者采用GRU，后者采用LSTM。

（4）GCN-GAN：將GAN、GCN、LSTM 進行組合設計，利用GCN 提取靜態圖的特征，LSTM 捕捉時域信息，GAN 優化模型的性能，充分發揮各個模塊的優勢，直接生成圖的鄰接矩陣。

3.2 實驗設置

為了驗證LPMDG 模型的有效性，本文的實驗都是在統一的實驗環境下進行的，具體如表2 所示。另外，用于對比的模型均采用原論文的實驗配置，而LPMDG 則采用如表3 所示的參數設置，并且在訓練過程，本文使用Adam 優化器進行優化，學習率設置為0.001。

表2 實驗設置Table 2 Experimental setup

表3 模型參數設置Table 3 Setting of model parameters

3.3 結果與分析

實驗結果如表4～表6 所示，通過觀察對比可以發現，LPMDG 的效果在大多數情況下優于上述四種模型，這是因為LPMDG 不僅考慮了時間的全局性，還考慮了空間的全局性。反觀另外幾個模型，GCN 并未考慮時間的因素，只是將參數更新過程視為圖在時域上的演化過程；GCN-GRU 雖然考慮了時間的影響，但是將每個節點看作一個單獨演化的過程，忽視了全局信息的作用；EnvolveGCN-h 和EnvolveGCN-o認為圖的演化過程蘊含在模型參數中，因此更加關注模型參數而不是單個節點，但是這種想法假設性太強，并且沒有關注圖本身的演化趨勢；GCN-GAN結合了GCN、LSTM 和GAN，但是依舊將節點單獨考慮，沒有考慮圖的整體性。

表4 USCB 的預測結果Table 4 Prediction results of USCB

表5 SBM 的預測結果Table 5 Prediction results of SBM

表6 AS 的預測結果Table 6 Prediction results of AS

本文的基準模型是GCN-GAN，為了驗證所提創新點的作用，本文構造了LPMDG*模型。LPMDG*對應于創新點1，比基準模型更加注重全局特征，但是缺少WSD 的約束。LPMDG 則是本文的完整模型，由于創新點2 是基于創新點1 的，在實驗部分不需要單獨驗證創新點2 對于基準模型的作用。從GCNGAN、LPMDG*和LPMDG 的實驗結果來看，AUC 指標都有不同程度的提升，MSE 在大多數情況下也是有所減小的，這足以說明全局特征對重構任務的重要作用。另外LPMDG 在三個數據集上的表現都是優于LPMDG*的，這也反映了寬平穩隨機過程確實能約束圖在時域上的演化進程。

本小節給出SBM 在訓練過程中損失函數值的變化曲線，如圖3 所示。其中橫坐標是迭代次數，縱坐標是函數值。可以看出，損失值雖然在局部有些許的波動，但是其整體趨勢是下降的，并且隨著迭代次數的增多，它的值逐漸收斂。由此，可間接證明本文模型在一定程度上是收斂的。

圖3 SBM 訓練損失Fig.3 SBM training loss

超參數是影響神經網絡性能的重要部分，比如LPMDG 模型中的時間窗口和隱空間的特征維度。據此，在USCB 和SBM 上做了進一步的實驗，觀察這些參數對本文模型的影響。首先，為了驗證不同時間窗口的影響，將USCB 隱空間的特征維度定義成64，SBM 的設為32，時間窗口取值分別為{2，3，4，5，6，7，8，9，10}，得出圖4 和圖5 的實驗結果。然后，為了驗證潛在特征維度的影響，本文將USCB 的時間窗口定義為6，SBM 的時間窗口定義為10，潛在特征維度的取值為{16，32，64，128，256}，得出圖6 和圖7的實驗結果。

圖4 AUC 實驗結果（固定d）Fig.4 AUC experimental results(fixed d)

圖5 MSE 實驗結果（固定d）Fig.5 MSE experimental results(fixed d)

圖6 AUC 實驗結果（固定w）Fig.6 AUC experimental results(fixed w)

圖7 MSE 實驗結果（固定w）Fig.7 MSE experimental results(fixed w)

從實驗結果來看，當=6，=64和=10，=32時，模型分別在USCB 和SBM 上的表現是最佳的。這是因為USCB 的節點個數相對較小，需要在隱空間增加維度，提高特征的表現力，而SBM 節點個數相對較多，原始的特征維度很容易造成信息冗余，在隱空間進行適當的特征降維，能提高潛在特征的質量。另外，同樣的改變，對于小的圖來說可能發生了大的變化，但是對于大的圖來說可能變化很小，因此節點少的數據集會更加注意短期的演變趨勢，節點多的數據集會更加關注長期的變化方向。

4 結束語

針對動態圖的鏈接預測問題，本文提出了LPDMG模型，該模型利用GCN、LSTM 和GAN 的優勢，耦合局部特征和全局特征的關系，學習高質量的全局特征表示。此外LPDMG 模型還考慮了全局特征在時域上的規律性，通過設計寬平穩感知模塊，從而約束全局特征演化的平滑性。本文在三個動態圖的數據集上對模型的性能進行了驗證，實驗結果表明，全局特征的高質量和平滑性對鏈接預測模型有著重要作用。在未來，會嘗試將本文算法思想應用于解決多關系圖和異構圖的相關問題。