基于圖卷積與長短期記憶網(wǎng)絡(luò)的動態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)模型

張?jiān)x，張曦煌

（江南大學(xué)人工智能與計(jì)算機(jī)學(xué)院，江蘇無錫 214002）

0 引言

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

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

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

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

針對近年來動態(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ò)表示學(xué)習(xí)模型dynGAELSTM。該模型利用GCN［5］提取圖的特征向量作為dAE 的編碼層輸入，編碼層的輸出進(jìn)入長短期記憶（Long Short-Term Memory，LSTM）網(wǎng)絡(luò)采集時(shí)空依賴特征，最后輸入dAE 的解碼層得到下一個時(shí)刻拓?fù)鋱D的預(yù)測，并加入懲罰參數(shù)和真實(shí)拓?fù)鋱D進(jìn)行對比得到損失函數(shù)，以此來構(gòu)建鏈路預(yù)測［2］。將dyngraph2vecAE 模型在SBM、Hep-th、AS 三個數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果表明該模型在提高鏈路預(yù)測的精度和降低參數(shù)復(fù)雜度上有顯著效果。

本文的主要工作如下：

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

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

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

1 相關(guān)工作

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

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

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

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

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

1.1 降噪自編碼器

dynGAELSTM 模型采用了降噪自編碼器（dAE）的框架，通過重建網(wǎng)絡(luò)與輸入網(wǎng)絡(luò)進(jìn)行對比，反向傳播更新參數(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é)點(diǎn)鏈接之間設(shè)置一個斷開率，防止干擾因素過多，避免過擬合現(xiàn)象；解碼器則是將隱藏層的特征信息重建至輸出層，和輸入數(shù)據(jù)進(jìn)行對比，使用梯度下降算法優(yōu)化模型。此模型的組件利用其編碼層的隨機(jī)斷開率降低模型復(fù)雜度。

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

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

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

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

dynGAELSTM 模型利用長短期記憶（LSTM）網(wǎng)絡(luò)采集時(shí)空依賴特征。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個輸入的信息，通過當(dāng)前的輸入xt和上一層神經(jīng)網(wǎng)絡(luò)的狀態(tài)ht-1建模，隱藏狀態(tài)ht和輸出y的表達(dá)為：

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

由于RNN 存在梯度彌散和梯度爆炸問題，學(xué)習(xí)能力有限，往往達(dá)不到預(yù)期的效果，于是李衛(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來計(jì)算ht，只不過對內(nèi)部的結(jié)構(gòu)進(jìn)行了優(yōu)化設(shè)計(jì)，加入了輸入門it、遺忘門ft、和輸出門ot三個門和一個內(nèi)部記憶單元ct。輸入門控制當(dāng)前的新狀態(tài)以多大程度更新到記憶單元中，遺忘門控制前一步記憶單元中的信息以多大程度被遺忘，而輸出門控制記憶單元在當(dāng)前輸出中的程度。多個此組件組合成的LSTM 網(wǎng)絡(luò)模塊可以保留動態(tài)圖的長時(shí)間跨度的演化信息。

2 dynGAELSTM模型

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

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

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

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

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

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

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

3 實(shí)驗(yàn)與分析

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

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

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

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

3.2 基準(zhǔn)模型

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

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

3.3 評價(jià)標(biāo)準(zhǔn)

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

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

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

3.4 節(jié)點(diǎn)社區(qū)預(yù)測可視化

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

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

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

3.5 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

3.6 模型復(fù)雜度分析

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

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

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

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

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

4 結(jié)語

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

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