張元鈞，張曦煌

（江南大學人工智能與計算機學院，江蘇無錫 214002）

0 引言

隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)信息急劇增加，而且各種數(shù)據(jù)之間存在千絲萬縷的關(guān)系，因此復雜信息網(wǎng)絡(luò)普遍被用來存儲實體間復雜的關(guān)系信息，而事物之間的聯(lián)系可以自然地用圖數(shù)據(jù)的形式表示。比如學術(shù)論文之間的引用和被引用關(guān)系可以看作網(wǎng)絡(luò)中的邊，各類論文便是網(wǎng)絡(luò)中的各個節(jié)點，由此學術(shù)論文之間的引用關(guān)系就可以用圖數(shù)據(jù)集的形式表示成相應(yīng)的復雜網(wǎng)絡(luò)；社交媒體［1］中的用戶可以看作網(wǎng)絡(luò)中的節(jié)點，用戶之間的聯(lián)系是相對應(yīng)的邊，由此形成了社交網(wǎng)絡(luò)；城市交通中的城市即為網(wǎng)絡(luò)中的節(jié)點，道路的通暢情況可作為網(wǎng)絡(luò)中的邊，由此形成了交通網(wǎng)絡(luò)。上述三個復雜網(wǎng)絡(luò)案例都是經(jīng)典的動態(tài)網(wǎng)絡(luò)，隨著時間的推移，邊之間的聯(lián)系也會不斷變化。鏈路預測的主要目的是預測未來網(wǎng)絡(luò)中丟失的邊，或者可能出現(xiàn)的邊。近年來，大數(shù)據(jù)和深度學習技術(shù)日漸成熟，上述交通網(wǎng)絡(luò)中可以通過分析前段時間的道路擁堵情況來判斷未來時刻交通的暢通情況，類似此種應(yīng)用的廣泛增加，因此復雜信息網(wǎng)絡(luò)的鏈路預測［2］已經(jīng)成為一個熱門的研究課題。

大數(shù)據(jù)時代下，網(wǎng)絡(luò)被用來存儲事物間復雜的關(guān)系信息，將復雜的網(wǎng)絡(luò)信息表示成相應(yīng)的拓撲圖結(jié)構(gòu)，提取拓撲圖的信息與時間之間的聯(lián)系，來預測未來時刻節(jié)點之間的鏈路關(guān)系。以圖1 所示的簡單社交網(wǎng)絡(luò)為例，模擬鏈路預測模型提取特征的一些方法。

圖1 社交關(guān)系網(wǎng)絡(luò)演變圖Fig.1 Social network evolution diagram

圖1中，A、B、C、D分別代表四名用戶，用戶之間出現(xiàn)的連線表示用戶之間相互認識，沒有連線則彼此不認識。在初始狀態(tài)t時刻：用戶A只認識用戶B，用戶B只認識用戶C，用戶C只認識用戶D；進入下一個時刻即t+1時刻，就可能因為在t時刻用戶A認識用戶B，用戶B把用戶C介紹給用戶A，導致用戶A認識用戶C，即A和C兩個節(jié)點之間產(chǎn)生連線；在t+2 時刻，可能因為t時刻用戶C與用戶D認識和t+1 時刻用戶A認識了用戶C，導致用戶A認識了用戶D，即A和D兩個節(jié)點之間產(chǎn)生連線。本文在進行鏈路預測時提取特征的部分手段就與上述舉例方法類似，即通過學習不同時刻的鏈路演化信息對未來時刻節(jié)點之間的鏈路信息進行預測。目前大多數(shù)網(wǎng)絡(luò)表示學習算法都能有效學習靜態(tài)網(wǎng)絡(luò)［3］中節(jié)點的向量表示，然而現(xiàn)實世界的網(wǎng)絡(luò)大部分都是動態(tài)的，網(wǎng)絡(luò)中的節(jié)點和邊會隨著時間的推移而變化。近年來網(wǎng)絡(luò)表示學習的算法［4］在處理動態(tài)網(wǎng)絡(luò)時，往往收效甚微，存在不能保留動態(tài)圖的長時間跨度的演化信息，面對復雜的動態(tài)網(wǎng)絡(luò)時存在預測精度較低、模型的復雜度較高等問題。

針對近年來動態(tài)網(wǎng)絡(luò)中存在的問題，受Kipf 等［5］提出的圖卷積網(wǎng)絡(luò)（Graph Convolutional Network，GCN）和Goyal 等［6］提出的dyngraph2vecAE 模型啟發(fā)，本文提出了一種以降噪自編碼器（denoising AutoEncoder，dAE）［7］為框架的動態(tài)網(wǎng)絡(luò)表示學習模型dynGAELSTM。該模型利用GCN［5］提取圖的特征向量作為dAE 的編碼層輸入，編碼層的輸出進入長短期記憶（Long Short-Term Memory，LSTM）網(wǎng)絡(luò)采集時空依賴特征，最后輸入dAE 的解碼層得到下一個時刻拓撲圖的預測，并加入懲罰參數(shù)和真實拓撲圖進行對比得到損失函數(shù)，以此來構(gòu)建鏈路預測［2］。將dyngraph2vecAE 模型在SBM、Hep-th、AS 三個數(shù)據(jù)集上進行實驗，結(jié)果表明該模型在提高鏈路預測的精度和降低參數(shù)復雜度上有顯著效果。

本文的主要工作如下：

1）提出了一種鏈路預測的動態(tài)網(wǎng)絡(luò)表示學習模型——dynGAELSTM，該模型可以學習動態(tài)圖節(jié)點之間的結(jié)構(gòu)信息和時空依賴特征來預測鏈路，同時也實現(xiàn)了動態(tài)網(wǎng)絡(luò)預測圖的可視化；

2）dynGAELSTM 模型的節(jié)點采樣端加入了GCN 進行高階圖鄰域結(jié)構(gòu)特征的提取，并利用LSTM 網(wǎng)絡(luò)來獲取動態(tài)圖的長時間跨度的演化信息，在面對復雜的動態(tài)圖時，預測結(jié)果更加準確；

3）dynGAELSTM 模型以節(jié)點隨機斷開的dAE 為框架，能有效降低模型的復雜度，提高運算效率。

1 相關(guān)工作

動態(tài)網(wǎng)絡(luò)數(shù)據(jù)在本文中表示成一系列隨時間變化的靜態(tài)圖像，實驗時也是將此類動態(tài)數(shù)據(jù)集β={G1，G2，…，Gt} 轉(zhuǎn)化為靜態(tài)圖G=(V，E)進行輸入，其中：V代表節(jié)點的集合，E代表邊的集合。

近年來的動態(tài)網(wǎng)絡(luò)表示學習模型主要是通過施加一個時間正則化來增強相鄰動態(tài)網(wǎng)絡(luò)鏡像中節(jié)點表示的平滑性。比如，2018 年Goyal 等［6］提出了使用自編碼器（AutoEncoder，AE）將輸入數(shù)據(jù)映射到高度非線性空間來捕捉當前時刻網(wǎng)絡(luò)連通性的dynGEM［8］模型，并通過PropSize［8］來動態(tài)擴展模型；雖然該模型能學習到動態(tài)網(wǎng)絡(luò)的演化依賴信息和網(wǎng)絡(luò)的結(jié)構(gòu)信息，但只用了前一個時間的網(wǎng)絡(luò)信息進行預測，不能保留動態(tài)圖的長時間跨度的演化信息。2018 年Zhou 等［9］提出的DynamicTriad 模型假設(shè)動態(tài)圖的時空演化持續(xù)時間很短，僅有兩個時間步長，模型采用的時間節(jié)點表示僅限于一階鄰近度的建模，忽略了高階圖鄰域的結(jié)構(gòu)。2019 年，Goyal 等［6］提出的dyngraph2vecRNN 模型如圖2 所示。該模型利用自編碼器（AE）結(jié)合循環(huán)神經(jīng)網(wǎng)絡(luò)（Rerrent Neural Network，RNN）學習復雜網(wǎng)絡(luò)的動態(tài)信息，可以有效提取有權(quán)圖的長時間跨度演化信息；但dyngraph2vecRNN 模型的高階圖鄰域結(jié)構(gòu)特征提取不完善，且與其他基準模型相比復雜度較高。此外，Luo等［10］提出的OptimalSVD 模型和Taheri 等［11］提出的RerunSVD模型都基于鄰接矩陣的奇異值分解表示圖中的各個節(jié)點，但獲取高階圖鄰域結(jié)構(gòu)特征的能力都較差。

圖2 dyngraph2vecRNN模型結(jié)構(gòu)Fig.2 Structure of dyngraph2vecRNN model

上述近年來動態(tài)網(wǎng)絡(luò)表示學習模型的不足之處總結(jié)如下：1）不能保留動態(tài)圖的長時間跨度的演化信息；2）忽略了高階圖鄰域的結(jié)構(gòu)，在面對復雜的動態(tài)網(wǎng)絡(luò)時預測精度較低；3）動態(tài)網(wǎng)絡(luò)模型的復雜度較高。本文針對上述問題給出了相應(yīng)的改進方法，提出了dynGAELSTM模型。

本文dynGAELSTM 模型的鏈路預測主要從動態(tài)圖節(jié)點之間的特征和時空依賴特征這兩方面著手。該模型受Kipf 等［5］改進的K階多項式代替?zhèn)鹘y(tǒng)卷積神經(jīng)網(wǎng)絡(luò)（Convolutional Neural Network，CNN）上的卷積核的啟發(fā)，并結(jié)合Bengio 等［12］提出的基于圖的標簽傳播算法，以此抽取動態(tài)圖中心節(jié)點k步范圍內(nèi)節(jié)點的局部結(jié)構(gòu)特征；時空依賴特征的提取以Sathasivam 等［13］提出的RNN 為基礎(chǔ)，通過歷史信息的保留和輸入信息來處理和預測序列數(shù)據(jù)。下面具體介紹dynGAELSTM模型的三個基本構(gòu)成組件。

1.1 降噪自編碼器

dynGAELSTM 模型采用了降噪自編碼器（dAE）的框架，通過重建網(wǎng)絡(luò)與輸入網(wǎng)絡(luò)進行對比，反向傳播更新參數(shù)優(yōu)化模型。自編碼器（AE）是在2006 年由Hinton 等［14］提出的一種無監(jiān)督神經(jīng)網(wǎng)絡(luò)模型，dAE 在在自編碼器的隱藏層上設(shè)置了一個斷開率，獲得輸入圖的低維特征。dAE 的結(jié)構(gòu)如圖3所示。

圖3 降噪自編碼器結(jié)構(gòu)Fig.3 Structure of dAE

dAE 由編碼器和解碼器兩個部分組成：編碼器就是將輸入層映射到隱藏層，并在映射過程中的節(jié)點鏈接之間設(shè)置一個斷開率，防止干擾因素過多，避免過擬合現(xiàn)象；解碼器則是將隱藏層的特征信息重建至輸出層，和輸入數(shù)據(jù)進行對比，使用梯度下降算法優(yōu)化模型。此模型的組件利用其編碼層的隨機斷開率降低模型復雜度。

1.2 圖卷積網(wǎng)絡(luò)

dynGAELSTM 模型編碼器的前端加入了圖卷積網(wǎng)絡(luò)（GCN），相應(yīng)的圖卷積框架如圖4 所示，其目的是從輸入的復雜的拓撲結(jié)構(gòu)中提取圖的特征信息，并精簡進入到dAE 的編碼器的輸入，其中σ(x)為圖卷積層的激活函數(shù)。傳統(tǒng)的CNN可以提取空間特征，在圖像處理和語言處理等應(yīng)用上效果顯著，但在面對由頂點和邊建立相應(yīng)關(guān)系的拓撲網(wǎng)絡(luò)時，由于每個頂點相鄰點的數(shù)目不同，使用共享權(quán)值來進行卷積運算無法準確提取特征。研究圖信號處理的學者基于拉普拉斯矩陣［15］的圖譜分解，把拉普拉斯算子的特征函數(shù)e-iwt轉(zhuǎn)變?yōu)閳D對應(yīng)的拉普拉斯矩陣的特征向量。Kipf 等［5］在GCN［5］中加入一階Chebyshev多項式作為卷積核，克服了傳統(tǒng)的離散卷積在拓撲結(jié)構(gòu)上無法保持平移不變性的缺點，GCN 中結(jié)合Bengio等［12］提出的基于圖的標簽傳播算法抽取中心節(jié)點的局部結(jié)構(gòu)特征，相較于傳統(tǒng)的離散卷積神經(jīng)網(wǎng)絡(luò)，算法的復雜度從O(N2)降低到了O(N)，其中N表示節(jié)點的個數(shù)，圖數(shù)據(jù)集特征提取精度提高。此模型的組件提取了高階圖鄰域的結(jié)構(gòu)特征信息，解決了復雜動態(tài)網(wǎng)絡(luò)預測精度較低的問題。

圖4 圖卷積網(wǎng)絡(luò)結(jié)構(gòu)Fig.4 Structure of GCN

1.3 長短期記憶網(wǎng)絡(luò)

dynGAELSTM 模型利用長短期記憶（LSTM）網(wǎng)絡(luò)采集時空依賴特征。LSTM 網(wǎng)絡(luò)是基于RNN［13］的一種變種，RNN 的結(jié)構(gòu)如圖5所示。

圖5 RNN結(jié)構(gòu)Fig.5 Structure of RNN

一個長度為T的序列用RNN 建模，展開之后是一個T層的前饋神經(jīng)網(wǎng)絡(luò)。其中，第t層的隱含狀態(tài)ht編碼了序列中前t個輸入的信息，通過當前的輸入xt和上一層神經(jīng)網(wǎng)絡(luò)的狀態(tài)ht-1建模，隱藏狀態(tài)ht和輸出y的表達為：

其中：f和g為激活函數(shù)；U為輸入層到隱含層的權(quán)重矩陣；U1為隱藏層到輸出層的權(quán)重矩陣；W為隱含層從上一時刻到下一個時刻的狀態(tài)轉(zhuǎn)移的權(quán)重矩陣。

由于RNN 存在梯度彌散和梯度爆炸問題，學習能力有限，往往達不到預期的效果，于是李衛(wèi)疆等［16］在RNN 的基礎(chǔ)上給出了如圖6所示的LSTM網(wǎng)絡(luò)框架。

圖6 LSTM網(wǎng)絡(luò)結(jié)構(gòu)Fig.6 Structure of LSTM network

與傳統(tǒng)的RNN 相比，LSTM 網(wǎng)絡(luò)仍然是基于輸入xt和隱含狀態(tài)ht-1來計算ht，只不過對內(nèi)部的結(jié)構(gòu)進行了優(yōu)化設(shè)計，加入了輸入門it、遺忘門ft、和輸出門ot三個門和一個內(nèi)部記憶單元ct。輸入門控制當前的新狀態(tài)以多大程度更新到記憶單元中，遺忘門控制前一步記憶單元中的信息以多大程度被遺忘，而輸出門控制記憶單元在當前輸出中的程度。多個此組件組合成的LSTM 網(wǎng)絡(luò)模塊可以保留動態(tài)圖的長時間跨度的演化信息。

2 dynGAELSTM模型

針對第1 章總結(jié)的近年來鏈路預測模型的三個不足之處，在面對復雜的動態(tài)網(wǎng)絡(luò)時預測精度較低、高階圖鄰域的特征信息提取不完善的問題時，F(xiàn)u 等［17］利用GCN［8］完成靜態(tài)網(wǎng)絡(luò)的節(jié)點聚類，能較好地提取高階圖的結(jié)構(gòu)特征，模型的節(jié)點聚類能力強。受此啟發(fā)，本文將GCN 作為dynGAELSTM 模型的前端模型來采集動態(tài)圖的特征信息。面對不能保留動態(tài)圖的長時間跨度的演化信息時，由于李衛(wèi)疆等［16］提出的LSTM網(wǎng)絡(luò)可以通過上一個時刻的信息來預測下一個時刻的信息，雖然可以提取部分時空依賴度，但無法保存大跨度時間的信息，于是將多個LSTM 網(wǎng)絡(luò)層組合成LSTM 網(wǎng)絡(luò)模塊可以接收多個時間的動態(tài)圖信息，因此選擇LSTM 網(wǎng)絡(luò)模塊來采集動態(tài)圖長時間跨度的演化信息。面對動態(tài)網(wǎng)絡(luò)模型復雜度較高的問題時，利用dAE的編碼層的隨機斷開率，能減少模型的節(jié)點參數(shù)，降低模型復雜度。

下面將詳細闡述dynGAELSTM 模型結(jié)構(gòu)和損失函數(shù)的定義。輸入該模型的三個數(shù)據(jù)集都是動態(tài)圖的數(shù)據(jù)集，將其劃分為不同時刻的有權(quán)圖G=(V，E)，其中：V代表節(jié)點的集合；E代表邊的集合，?eij∈E(i，j=1，2，3，…)，eij表示邊的權(quán)重。

dynGAELSTM 模型通過學習輸入的t+lb時刻之前的網(wǎng)絡(luò)演化信息，根據(jù)第t個時刻至第t+lb時刻的輸入圖去預測t+lb+1 時刻的輸出圖。該模型以dAE 為框架，前端加入了GCN 來提煉動態(tài)圖節(jié)點之間的高階相似特征，將獲得的拓撲圖的節(jié)點向量作為dAE 的輸入向量，使用隨機斷開的特性進一步獲得相應(yīng)的低維向量表示，將第t至第t+lb個時刻獲得的低維向量輸入LSTM 網(wǎng)絡(luò)中獲取其相應(yīng)的低維時空依賴特征向量，并將低維向量輸入解碼器進行解碼，重構(gòu)預測圖，并引入懲罰參數(shù)將預測圖與真實圖對比構(gòu)建損失函數(shù)，以隨機梯度下降的方法不斷優(yōu)化模型。本文dynGAELSTM 模型的結(jié)構(gòu)如圖7所示。

圖7 dynGAELSTM模型結(jié)構(gòu)Fig.7 Structure of dynGAELSTM model

GCN 層的輸出進入dAE 后，輸入進LSTM 網(wǎng)絡(luò)層。LSTM網(wǎng)絡(luò)是在RNN 中加入輸入門it、遺忘門ft、和輸出門ot三個門和一個內(nèi)部記憶單元ct。三個門的記憶單元及節(jié)點v在t時刻的第一層LSTM網(wǎng)絡(luò)層的定義式為：

dAE 的解碼器層提取LSTM 網(wǎng)絡(luò)層輸出的時空依賴特征的有效信息，重建動態(tài)輸入的網(wǎng)絡(luò)，即為預測的t+lb+1 時刻的圖。

上述為模型的GCN 層和LSTM 網(wǎng)絡(luò)層的輸出，以此為基準構(gòu)建模型的損失函數(shù)。引入懲罰參數(shù)γ對圖在t+lb+1 時刻不正確的重構(gòu)就進行糾正，利用均方誤差（Mean Square Error，MSE）的概念，將得到的預測結(jié)果與實際結(jié)果建立損失函數(shù)為：

3 實驗與分析

本章將描述所使用的數(shù)據(jù)集并闡述比較基準模型的基本原理和參數(shù)設(shè)置；此外，為實驗結(jié)果設(shè)置評價指標。所有實驗的環(huán)境配置均在64位Ubuntu16.04.1LTS系統(tǒng)上進行，該系統(tǒng)使用型號為intel Core i7-9700KF 的CPU，具有8 個CPU 內(nèi)核，主頻為3.60 GHz；顯卡型號為GeForce RTX 2080Ti，顯存容量為11 GB。

3.1 實驗數(shù)據(jù)集

本文采用了一個模擬數(shù)據(jù)集SBM（Stochastic Block Model）［6］和兩個真實數(shù)據(jù)集（Hep-th［19］和AutonomousSystems（AS）［20］）對dynGAELSTM 模型進行實驗，這三個數(shù)據(jù)集為Goyal 等［6］在測試dyngraph2vecAERNN 模型鏈路預測能力時使用的三個公共數(shù)據(jù)集，能有效評估該模型鏈路預測的綜合能力。這三個數(shù)據(jù)集中的節(jié)點數(shù)量均不隨時間的變化增加或減少，隨時間改變的只有現(xiàn)有時間節(jié)點之間的鏈接關(guān)系?，F(xiàn)將SBM、Hep-th和AS三個數(shù)據(jù)集的信息匯總于表1。

表1 數(shù)據(jù)集匯總Tab.1 Summary of datasets

SBM：該模擬數(shù)據(jù)集用Wang 等提出的隨機模型，該模型可生成相應(yīng)的SBM 數(shù)據(jù)集，擁有兩個社區(qū)，每個社區(qū)包含500個節(jié)點，最多可以生成56 016 條鏈路，經(jīng)歷每個時間步長時，其社區(qū)間的移動概率為0.01，社區(qū)內(nèi)的移動概率為0.1，該數(shù)據(jù)集隨時間的不斷推移，節(jié)點由一個社區(qū)逐步遷移到另一個社區(qū)，每個時間步長平均都有10至20個節(jié)點進行遷移。

Hep-th：該真實數(shù)據(jù)集是第一個用來測試動態(tài)網(wǎng)絡(luò)模型綜合能力的數(shù)據(jù)集，描述了高能物理理論會議上各作者之間合作關(guān)系的復雜網(wǎng)絡(luò)。原始數(shù)據(jù)集包含1993 年1 月至2003年4 月期間在高能物理理論會議上的作者合作關(guān)系，每次統(tǒng)計其時間步長為一個月。模型實驗選用該數(shù)據(jù)集從2000年4月以后的有權(quán)圖。

AS：該真實數(shù)據(jù)集是基于邊界網(wǎng)關(guān)協(xié)議（Border Gateway Protocol）日志中“與誰通話”的通信網(wǎng)絡(luò)。數(shù)據(jù)集包含從1997年11月8日到2000年1月2日的733個實例，其時間步長為一個月。對數(shù)據(jù)集進行整理，使用該數(shù)據(jù)集的一個子集，包含最新的100個快照，共4 154個節(jié)點進行訓練與測試。

3.2 基準模型

本節(jié)具體介紹與dynGAELSTM 模型做對比的其他6 種基準模型的參數(shù)設(shè)置，如表2。這6個模型主要使用的模型原理及在動態(tài)網(wǎng)絡(luò)鏈路預測應(yīng)用中存在的不足已經(jīng)在相關(guān)工作進行了介紹。

表2 模型參數(shù)設(shè)置Tab.2 Model parameter setting

3.3 評價標準

本文中引入前k個節(jié)點的精確率［21］（Precision@k，P@k）和平均精確率均值（mean Average Precision，mAP）兩個指標評估dynGAELSTM 模型在鏈路預測的綜合性能，P@k測試模型的最高預測性能，mAP 反映模型的綜合性性能。將預測為正類實際也為正類的個數(shù)記為TP（True Positive）；將預測為負類實際為正類的個數(shù)記為FP（False Positive）；將預測為正類實際為負類的個數(shù)記為TN（True Negative），在此基礎(chǔ)上給出精確率Pr（precision）和召回率Re（recall）的定義式為：

其中：Y為鏈路集合。精確率反映鏈路預測的正確比例，召回率反映能預測出來的比例，并以節(jié)點數(shù)量進行分批實驗，記為P@k，直觀反映網(wǎng)絡(luò)重構(gòu)的精確率。在精確率的基礎(chǔ)上融入召回率，設(shè)置k個召回率的閾值列表，并實驗出相應(yīng)的精確率，以橫軸為召回率，縱軸為精確率，繪制P-R 曲線。由此平均精確率（Average Precision，AP）和mAP［22］的定義式為：

其中：SPR為在不同的召回率閾值上精確率與召回率構(gòu)成的圖形的面積；APi表示第i個召回率閾值的平均精確率。

3.4 節(jié)點社區(qū)預測可視化

SBM數(shù)據(jù)集由兩個社區(qū)組成，在兩個社區(qū)中共選取320個節(jié)點，使用OptimalSVD［10］、dynGEM［8］、dyngraph2vecAERNN［6］、dynGAELSTM 四個模型（為方便表示在圖8 中分別簡稱為OSVD、dGEM、dAER和本文模型）通過學習前t-1個時刻的動態(tài)圖進行訓練，將訓練好的四個模型預測t、t+1、t+2和t+3這4個時刻的預測圖并在二維平面上表示出來，與真實時刻的拓撲圖8（a）進行對比，結(jié)果如圖8（b）～（e）所示。由于點數(shù)過多，使用不同顏色標記動態(tài)圖中的10個節(jié)點，直觀比較這10個節(jié)點的分布位置來比較各模型節(jié)點轉(zhuǎn)移和所有節(jié)點在社區(qū)中聚類的預測性能。

圖8 SBM數(shù)據(jù)集上的節(jié)點社區(qū)預測可視化Fig.8 Node community prediction visualization on SBM dataset

圖8（b）、（c）為OptimalSVD 和dynGEM 兩個模型在4 個不同時刻的預測圖，與真實圖（a）相比，可以觀察出兩個模型的預測圖社區(qū)分類相對明顯，但dynGEM 的后兩張預測圖社區(qū)分類的兩種點互相摻雜，并且一部分紅點的分布位置不在相應(yīng)的社區(qū)內(nèi)。圖8（d）、（e）為dyngraph2vecAERNN 和dynGAELSTM 兩個模型在4 個不同時刻的預測圖，社區(qū)分類的區(qū)分度較高，紅點的分布位置大致準確，預測精度相較于OptimalSVD 和dynGEM 兩個模型的預測圖有了明顯的提高，但在圖（d）的第一張圖（t時刻）中可以觀察有一個紅點不在所屬的社區(qū)內(nèi)，圖（e）的第二張圖（t+1時刻）可以觀察出有一個紫色節(jié)點在黃色節(jié)點所屬的社區(qū)內(nèi)，兩相比較，可較為直觀地判斷dynGAELSTM 模型捕捉動態(tài)網(wǎng)絡(luò)時空演化特征的能力略勝一籌。由于可視化中只取了一部分節(jié)點可視化出來做比較差異并不明顯，下述實驗中將采用三個不同的數(shù)據(jù)集進行實驗比較。

3.5 實驗結(jié)果

本節(jié)在SBM、Hep-th 和AS 三個數(shù)據(jù)集進行測試，GCN 上的第一層神經(jīng)元個數(shù)設(shè)置為256，第二層設(shè)置為128；LSTM 網(wǎng)絡(luò)的隱藏層單元個數(shù)為128；CNN 層第一層設(shè)置為128，第二層設(shè)置為64；dAE的斷開率設(shè)置為0.1。

在SBM 數(shù)據(jù)集上的實驗結(jié)果如圖9 所示。為表示方便，后面的實驗結(jié)果圖中均用d2vAERNN、d2vAERNN 分別表示dyngraph2vecRNN、dyngraph2vecAERNN。由圖9 可以得出除dynamicTriad 模型的鏈路預測效果較差外，其他模型在SBM數(shù)據(jù)集上前1 000 個節(jié)點的普遍精度都可以達到0.95 以上，說明dynGAELSTM 模型適合動態(tài)圖的鏈路預測。由于SBM數(shù)據(jù)集的節(jié)點個數(shù)較少，數(shù)據(jù)信息的復雜情況一般，模型在提取特征時更偏向于對時空依賴特征的提取，因此可以說明dynGAELSTM 模型中的LSTM 網(wǎng)絡(luò)模塊能夠有效提取動態(tài)圖長時間的跨度演化信息。

圖9 SBM數(shù)據(jù)集上的P@k性能Fig.9 P@k performance on SBM dataset

在Hep-th 數(shù)據(jù)集上的實驗結(jié)果如圖10 所示。在Hep-th數(shù)據(jù)集上可以明顯觀察出dynGAELSTM 模型在前2 000 個節(jié)點的精確率在k為100，800，1 200，2 000 時都要略高于精度第二的dyngraph2vecAERNN，且前2 000 個節(jié)點的精確率都可以達到0.99 以上，dynGAELSTM 模型的鏈路預測能力比dyngraph2vecAERNN 模型以外的模型明顯要高。Hep-th 數(shù)據(jù)集取了前2 000個節(jié)點，節(jié)點數(shù)多，鏈路較多，此動態(tài)圖數(shù)據(jù)集的預測對時空的依賴特征和高階圖鄰域結(jié)構(gòu)特征的提取要求較高，dynGAELSTM 模型比其他基準模型的精度都高，足以說明模型中的LSTM 網(wǎng)絡(luò)模塊能夠有效提取動態(tài)圖長時間的跨度演化信息，且GCN 對高階圖鄰域結(jié)構(gòu)特征的信息獲取能力較強。

圖10 Hep-th數(shù)據(jù)集上的P@k性能Fig.10 P@k performance on Hep-th dataset

在節(jié)點和鏈路較多的AS 數(shù)據(jù)集上的實驗結(jié)果如圖11 所示。在AS 數(shù)據(jù)集上可以明顯觀察出dynGAELSTM 模型在前2 000個節(jié)點的精確率都高于精度第二的dyngraph2vecAERNN模型，且前2 000 個節(jié)點的精確率都可以達到0.97 以上。AS數(shù)據(jù)集相較于SBM 和Hep-th 數(shù)據(jù)集的節(jié)點數(shù)更多，鏈路的權(quán)重因素更復雜，模型在面對更加復雜的動態(tài)圖數(shù)據(jù)集AS 時，dynGAELSTM 模型鏈路預測的競爭力明顯強于其他基準模型，可以說明dynGAELSTM 模型的GCN 在面對關(guān)系復雜的數(shù)據(jù)集時可以高效地提取高階圖鄰域結(jié)構(gòu)特征信息。

圖11 AS數(shù)據(jù)集上的P@k性能Fig.11 P@k performance on AS dataset

dynGAELSTM 模型在SBM、Hep-th 和AS 三個數(shù)據(jù)集進行mAP 性能的測試，結(jié)果如表3。由表3 可得，dynGAELSTM 模型在SBM、Hep-th 兩個數(shù)據(jù)集上的mAP 性能略高于dyngraph2vecAERNN 模型，提高了7.9和1.19個百分點，而且遠高于其他基準模型。在復雜的AS 數(shù)據(jù)集上dynGAELSTM模型的mAP 性能比dyngraph2vecAERNN 模型高出3.13 個百分點，實驗結(jié)果可以說明模型前端的GCN 提取了拓撲圖的高階特征，第t至第t+lb個時刻的LSTM 網(wǎng)絡(luò)層獲取了數(shù)據(jù)集的時空依賴特征，提升了dynGAELSTM 模型鏈路預測的綜合性能。

表3 SBM、Hep-th和AS數(shù)據(jù)集上的mAP性能Tab.3 mAP performance on SBM，Hep-th and AS datasets

3.6 模型復雜度分析

為驗證dynGAELSTM 模型的復雜度較低，將它與基準模型在復雜度上進行對比。首先與鏈路預測綜合性能第二的dyngraph2vecAERNN 模型在模型結(jié)構(gòu)上進行對比，可以看出，dyngraph2vecAERNN 模型采用了AE 的框架，編碼層之間采用全連接層，節(jié)點參數(shù)并未減少；而dynGAELSTM 模型采用了dAE 的框架，節(jié)點之間設(shè)置隨機斷開率為0.1，在dAE 的編碼層的參數(shù)量將會變?yōu)樵瓉淼?.9，后續(xù)的解碼層兩者都為全連接重建，參數(shù)量接近。由此可以認為：與鏈路預測綜合性能第二的dyngraph2vecAERNN 模型相比，dynGAELSTM 模型的參數(shù)復雜程度有所下降，訓練效率提高，并且預測精度更高。

復雜度的對比還借鑒了文獻［23］中研究的復雜度對比方法。該方法在相同的實驗環(huán)境配置下將所提出的模型作為基準，其相應(yīng)的訓練時間記為1×，基準模型和對比模型同時進行訓練，得出對比模型的訓練時間與基準訓練時間的對比度，以此判斷模型的時間復雜度。本次實驗中，上述實驗環(huán)境配置不變，在SBM 數(shù)據(jù)集取前200 個點和前300 個點進行兩次實驗，dynGAELSTM 模型與6 個對比模型在相同環(huán)境同時進行訓練，將dynGAELSTM 模型的訓練時間設(shè)為基準（記為1×），其余6個基準模型的訓練時間與基準的訓練時間進行對比，相應(yīng)的對比度記為A×，A為相應(yīng)的比值。其實驗結(jié)果如表4所示。

由表4 可得出模型鏈路預測綜合性能排名前三的模型分別是dynGAELSTM 模型、dyngraph2vecRNN 模型和dynGEM 模型，其他四個模型在三個數(shù)據(jù)集上的mAP 性能均比前三個模型下降較多，即使在表3 中dynamicTraid 模型的運行時間比dynGAELSTM 模型短，但dynGAELSTM 模型的鏈路預測綜合性能要遠高于dynamicTraid 模型，在精度相差較大的情況下不再做運行時間的對比，以精度優(yōu)先。由表4 還可以看出，dynGAELSTM 模型的運行時間最短，相比預測性能第二的dyngraph2vecAERNN 模型在SBM 數(shù)據(jù)集的前200 個點上運行時間降低了0.92%，在前300 個點上的運行時間降低了1.73%。

表4 網(wǎng)絡(luò)表示學習模型在SBM數(shù)據(jù)集上的運行時間對比Tab.4 Running time comparison of network representation learning models on SBM dataset

綜上所述，dynGAELSTM 模型與6 個基準模型相比，參數(shù)復雜度降低，運行效率提升，而且鏈路預測綜合性能最高。

4 結(jié)語

本文提出了一種用于鏈路預測的動態(tài)網(wǎng)絡(luò)表示學習模型dynGAELSTM。針對相關(guān)工作中總結(jié)出的鏈路預測模型的三個不足之處，該模型分別用了降噪自編碼器（dAE）節(jié)點之間的隨機斷開率來降低模型的復雜度，利用圖卷積網(wǎng)絡(luò)（GCN）來提取高階圖鄰域結(jié)構(gòu)的特征信息，第t至第t+lb個時刻的LSTM 網(wǎng)絡(luò)層提取動態(tài)圖的長時間跨度的演化信息。在三個數(shù)據(jù)集上進行鏈路預測實驗的結(jié)果顯示，dynGAELSTM 模型在SBM、Hep-th 和AS 數(shù)據(jù)集上的精確率高，說明該模型適合動態(tài)圖的鏈路預測，可以有效提取動態(tài)圖長時間的跨度演化信息；在Hep-th 和AS 數(shù)據(jù)集上的實驗結(jié)果表明，dynGAELSTM 模型在面對節(jié)點之間關(guān)系復雜的動態(tài)圖時，預測精確率明顯優(yōu)于其他基準模型，說明它可以高效地提取網(wǎng)絡(luò)的高階圖鄰域結(jié)構(gòu)特征信息。在SBM 數(shù)據(jù)集上的復雜度實驗結(jié)果也表明，dynGAELSTM 模型的復雜度低于其他基準模型，運行效率更高。綜上所述，dynGAELSTM 模型適合處理結(jié)構(gòu)復雜和時間跨度較長的動態(tài)圖的鏈路預測任務(wù)。

在未來的研究中，我們將針對回溯參數(shù)（LSTM 網(wǎng)絡(luò)的層數(shù)）進行研究，探索回溯參數(shù)的設(shè)置與時空依賴特征提取之間的關(guān)聯(lián)，并用復雜的數(shù)據(jù)集對模型復雜度的對比作進一步研究。