融合拓?fù)浜蛯傩缘膭?dòng)態(tài)網(wǎng)絡(luò)鏈路預(yù)測方法

羅世杰，呂文韜，李 凡，崔家熙，相 潔

太原理工大學(xué) 信息與計(jì)算機(jī)學(xué)院，山西 晉中 030600

隨著基于大數(shù)據(jù)深度學(xué)習(xí)的發(fā)展，鏈路預(yù)測成為了當(dāng)前數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)之一。大多現(xiàn)實(shí)問題均可以用復(fù)雜網(wǎng)絡(luò)表示，并借助鏈路預(yù)測來表達(dá)、分析和挖掘其中存在的重要模式。如生物工程中分子間酶轉(zhuǎn)化可能性[1]、協(xié)作網(wǎng)絡(luò)中學(xué)者間合作可能性[2]、交通網(wǎng)絡(luò)中事故評估[3]和社交網(wǎng)絡(luò)中人際關(guān)系預(yù)測[4]等。目前，該領(lǐng)域主要分為靜態(tài)和動(dòng)態(tài)兩種主流[5]。

傳統(tǒng)靜態(tài)鏈路預(yù)測方法其核心思想是利用各種指標(biāo)的分值計(jì)算邊存在的概率。如共同鄰居（common neighbor，CN）、Admaic-Ada（rAA）、局部路徑（local path，LP）、優(yōu)先鏈接（preferential attachment，PA）等局部相似性指標(biāo)來預(yù)測[6-8]。除此之外，還有大量網(wǎng)絡(luò)嵌入的方法，如矩陣分解DNMF[9]、隨機(jī)游走DeepWalk[10]、node2vec[11]和圖自編碼VGAE[12]。

而在現(xiàn)實(shí)世界中，網(wǎng)絡(luò)本質(zhì)上是動(dòng)態(tài)的，其結(jié)構(gòu)和屬性會(huì)隨時(shí)間而變化。同時(shí)現(xiàn)實(shí)世界網(wǎng)絡(luò)在快速增長，動(dòng)態(tài)鏈路預(yù)測在各種場景中得到了應(yīng)用[13]。如預(yù)測未來一段時(shí)間內(nèi)的交通流量[14]、企業(yè)間未來合作可能性[15]等。在動(dòng)態(tài)方法中，其目的是學(xué)習(xí)網(wǎng)絡(luò)隨時(shí)間的復(fù)雜變化，預(yù)測未來存在的邊[5]。目前主流方法是圖表示學(xué)習(xí)，如DynGEM算法[16]用之前時(shí)刻的嵌入初始化當(dāng)下的嵌入，但無法捕獲長時(shí)間動(dòng)態(tài)變化。Dyngraph2vec算法[17]把每個(gè)節(jié)點(diǎn)不同時(shí)刻下的拓?fù)湫畔⑼ㄟ^循環(huán)神經(jīng)網(wǎng)絡(luò)（recurrent neural network，RNN）學(xué)習(xí)嵌入，但該方法難以聚集節(jié)點(diǎn)鄰域信息。為此THS-GWNN算法[18]利用對多個(gè)時(shí)間步下鄰居采樣提取節(jié)點(diǎn)時(shí)空特征，DTINE算法[19]利用node2vec去豐富二階、三階等高階信息、DYSAT算法[20]通過結(jié)構(gòu)自注意方法聚合節(jié)點(diǎn)鄰域特征，但這類算法缺點(diǎn)是僅學(xué)習(xí)網(wǎng)絡(luò)拓?fù)湫畔?dǎo)致預(yù)測效果有限。和之前研究相比，EvolveGCN算法[21]通過GCN提取網(wǎng)絡(luò)拓?fù)浜蛯傩蕴卣鳌⒂肦NN演化GCN參數(shù)來捕捉動(dòng)態(tài)變化；SLIDE算法[22]考慮底層屬性網(wǎng)絡(luò)動(dòng)態(tài)變化；CDAN算法[23]通過變分自編碼嵌入、聚合節(jié)點(diǎn)的擾動(dòng)特征和屬性關(guān)聯(lián)來描述動(dòng)態(tài)變化；但這類算法都不能很好融合拓?fù)浜蛯傩孕畔⒂糜趧?dòng)態(tài)鏈路預(yù)測。

通過對近幾年動(dòng)態(tài)鏈路預(yù)測的觀察，發(fā)現(xiàn)大部分鏈路預(yù)測模型不能有效挖掘高階拓?fù)浜凸?jié)點(diǎn)屬性信息，且捕獲網(wǎng)絡(luò)演化能力有限，從而導(dǎo)致鏈路預(yù)測精度不足等問題。

針對上述問題，本文受Dyngraph2vec模型啟發(fā)，提出了一種融合網(wǎng)絡(luò)結(jié)構(gòu)和屬性的動(dòng)態(tài)鏈路預(yù)測方法（link prediction of dynamic network for fusion topology and attributes，DTA-LP）。Dyngraph2vec模型運(yùn)用自編碼和長短期記憶網(wǎng)絡(luò)（long short-term memory，LSTM）兩個(gè)模塊分別學(xué)習(xí)圖的拓?fù)湫畔⒑脱莼畔ⅰ１疚哪Ｐ褪且宰跃幋a為整體框架融合拓?fù)浜蛯傩赃M(jìn)行動(dòng)態(tài)鏈路預(yù)測。為挖掘結(jié)構(gòu)信息降低融合難度，模型借鑒重啟隨機(jī)游走（random walk with restart，RWR）算法[24]和自編碼神經(jīng)網(wǎng)絡(luò)對拓?fù)湎蛄壳度耄@兩種方法在圖嵌入已經(jīng)大量運(yùn)用，并取得了理想的效果[16，23，25-26]。為更好地融合屬性特征，利用注意力機(jī)制能從大量信息中篩選出重要信息的特點(diǎn)[26-27]，模型設(shè)計(jì)注意層對拓?fù)浜蛯傩匀诤稀椴东@時(shí)間演化信息，模型將歷史節(jié)點(diǎn)序列輸入到深度循環(huán)神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)演化，最后利用解碼器重構(gòu)網(wǎng)絡(luò)拓?fù)洌?jì)算損失反向優(yōu)化參數(shù)。本文設(shè)計(jì)實(shí)驗(yàn)在鏈路預(yù)測任務(wù)上進(jìn)行評估，并與當(dāng)前先進(jìn)的算法相比較，結(jié)果表明DTA-LP模型優(yōu)于對比算法。本文主要貢獻(xiàn)如下：

（1）提出了一種新的動(dòng)態(tài)鏈路預(yù)測方法DTA-LP，該模型可以有效地捕獲節(jié)點(diǎn)隨時(shí)間變化的屬性和拓?fù)湫畔ⅰ?/p>

（2）本文的實(shí)驗(yàn)數(shù)據(jù)中，論證了節(jié)點(diǎn)屬性信息可以作為動(dòng)態(tài)鏈路預(yù)測的補(bǔ)充。

（3）真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明DTA-LP模型優(yōu)于其余幾種對比算法。

1 問題描述

本文中的主要符號和定義如表1所示。t時(shí)刻下網(wǎng)絡(luò)可表示為Gt=(V,At,Xt)，其中V是圖中所有節(jié)點(diǎn)的集合，At∈Rn×n為鄰接矩陣表示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，Xt∈Rn×d為屬性矩陣。本文考慮無向無權(quán)圖，如果(i,j)∈E，aij=1，否則為0。

表1 符號及其含義Table 1 Symbols and meanings

定義1（動(dòng)態(tài)屬性網(wǎng)絡(luò)）一個(gè)動(dòng)態(tài)屬性網(wǎng)絡(luò)G可以看作是由多個(gè)屬性網(wǎng)絡(luò)快照組成，記G={G1,…,Gt,Gt+1}，其中每個(gè)網(wǎng)絡(luò)快照可表示為Gt=(V,At,Xt)。每個(gè)網(wǎng)絡(luò)快照有相同的節(jié)點(diǎn)集合，而網(wǎng)絡(luò)拓?fù)洌ㄟ吋┖凸?jié)點(diǎn)屬性會(huì)隨著時(shí)間而發(fā)生演變。因此，對于動(dòng)態(tài)網(wǎng)絡(luò)中的每個(gè)時(shí)刻網(wǎng)絡(luò)的邊可表示為atij∈At，指代t時(shí)刻下的節(jié)點(diǎn)i和j之間的邊。相應(yīng)的節(jié)點(diǎn)屬性表示為xit={u1,u2,…,ud}∈Xt，指代t時(shí)刻下節(jié)點(diǎn)i的屬性。

動(dòng)態(tài)網(wǎng)絡(luò)中的鏈路預(yù)測任務(wù)主要是利用歷史時(shí)間內(nèi)的網(wǎng)絡(luò)信息預(yù)測未來時(shí)刻下網(wǎng)絡(luò)中可能存在的鏈路[28]。因此動(dòng)態(tài)屬性網(wǎng)絡(luò)的鏈路預(yù)測問題可如下定義：

定義2（動(dòng)態(tài)鏈路預(yù)測）給定一個(gè)動(dòng)態(tài)屬性網(wǎng)絡(luò)G={G1,…,Gt,Gt+1}，其中節(jié)點(diǎn)的邊和屬性隨時(shí)間變化。動(dòng)態(tài)鏈路預(yù)測目的是用t時(shí)間（根據(jù)步長決定t的取值范圍）拓?fù)浜蛯傩匀ヮA(yù)測t+1時(shí)刻的拓?fù)湫畔ⅰ?/p>

如圖1所示，給定一個(gè)在t-1、t和t+1不同時(shí)刻的動(dòng)態(tài)屬性網(wǎng)絡(luò)，網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)屬性都發(fā)生了變化，算法可預(yù)測在t+1時(shí)刻可能出現(xiàn)的邊。相比基于動(dòng)態(tài)拓?fù)渚W(wǎng)絡(luò)而言，引入了用戶的屬性信息（如興趣、愛好等，圖中用u表示）用于鏈路預(yù)測。如隨時(shí)間變化，在t時(shí)刻當(dāng)用戶A和D之間有相同興趣愛好u1和u5時(shí)，可以預(yù)測在t+1時(shí)刻二者可能相識(shí)。

圖1 基于網(wǎng)絡(luò)拓?fù)浜蛯傩缘膭?dòng)態(tài)鏈路預(yù)測圖解Fig.1 Illustration of dynamic link prediction based on network topology and attributes

2 動(dòng)態(tài)鏈路預(yù)測模型結(jié)構(gòu)

本文旨在解決動(dòng)態(tài)屬性網(wǎng)絡(luò)中拓?fù)浜蛯傩韵嗷ト诤弦约半S時(shí)序演化的問題，提出的模型采用監(jiān)督性學(xué)習(xí)，模型借鑒圖表示性學(xué)習(xí)方法將網(wǎng)絡(luò)拓?fù)溆成涞降途S向量空間R，并設(shè)計(jì)注意力機(jī)制對屬性和拓?fù)溥M(jìn)行自適應(yīng)加權(quán)融合，通過LSTM和解碼器捕獲每個(gè)時(shí)間步和跨多個(gè)時(shí)間步節(jié)點(diǎn)之間的高度非線性關(guān)聯(lián)。模型由如下三部分組成：

（1）結(jié)構(gòu)嵌入層：在原始網(wǎng)絡(luò)中，鄰接矩陣維度大且稀疏，為有效分析和學(xué)習(xí)數(shù)據(jù)特征，必須轉(zhuǎn)換到低維空間并保留關(guān)鍵信息[29]。因此本層使用RWR挖掘高階拓?fù)湫畔⒓熬幋a器映射降維，完成對網(wǎng)絡(luò)拓?fù)鋵W(xué)習(xí)和嵌入，方便后續(xù)特征學(xué)習(xí)。

（2）屬性融合層：網(wǎng)絡(luò)拓?fù)浜蛯傩酝皇窍嗷オ?dú)立的，可能會(huì)相互影響[22]。為使拓?fù)浜蛯傩韵嗷パa(bǔ)充從中提取有效信息，本層采用注意力機(jī)制學(xué)習(xí)權(quán)重參數(shù)，完成拓?fù)浜蛯傩匀诤稀Ｏ啾绕渌椒ǎ⒁饬拥膮?shù)較少、解釋性較強(qiáng)、直觀簡潔且有利于后續(xù)統(tǒng)一處理時(shí)間特征。

（3）時(shí)間捕獲層：兩層LSTM網(wǎng)絡(luò)通過門控單元保存節(jié)點(diǎn)融合向量所有時(shí)刻的歷史信息，捕獲時(shí)間演化模式提高預(yù)測能力。

DTA-LP模型框架如圖2所示，在預(yù)測At+1之前，首先RWR和編碼器得到拓?fù)湎蛄壳度難s，然后用拓?fù)淝度牒蛯傩韵蛄縴a進(jìn)行融合生成yt，用LSTM捕獲時(shí)間的變化生成最終嵌入y，最后通過解碼器預(yù)測下一時(shí)刻的拓?fù)湫畔t+1。實(shí)驗(yàn)表明，在網(wǎng)絡(luò)邊和節(jié)點(diǎn)屬性不斷變化的過程中，本文模型可以有效學(xué)習(xí)其中模式，從而提高鏈路預(yù)測精度。

模型具體步驟如算法1中所示，第2~6行用于從鄰域中提取網(wǎng)絡(luò)拓?fù)浜蛯傩蕴卣鳎坏?行特征融合，有效保存拓?fù)浜蛯傩孕畔ⅲ坏?行用雙層LSTM捕獲網(wǎng)絡(luò)演化；第9~11行通過迭代訓(xùn)練模型；最終預(yù)測下一時(shí)刻拓?fù)浣Y(jié)構(gòu)。

算法1融合拓?fù)浜蛯傩缘膭?dòng)態(tài)網(wǎng)絡(luò)鏈路預(yù)測方法

輸入：動(dòng)態(tài)屬性網(wǎng)絡(luò)GT={G1,…,Gt,Gt+1}

輸出：t+1時(shí)刻下鄰接矩陣A

1.對原始數(shù)據(jù)構(gòu)建拓?fù)溧徑泳仃嘇和節(jié)點(diǎn)屬性向量X

2.輸入A，根據(jù)公式（1）、（2）得到節(jié)點(diǎn)的拓?fù)湎蛄勘硎維

3.將S和X分別標(biāo)準(zhǔn)化

4.fori←1 toNdo

5.forGtinGTdo

6.根據(jù)公式（3）~（5）嵌入得到y(tǒng)s

7.根據(jù)公式（6）~（8）融和得到y(tǒng)t

8.end for

9.根據(jù)公式（15）、（16）得到y(tǒng)

10.根據(jù)公式（3）、（4）反向計(jì)算得到L

11.根據(jù)公式（17）計(jì)算損失

12.利用Adma優(yōu)化器和反向傳播算法最小化Loss函數(shù)，更新模型參數(shù)

13.end for

2.1 基于自編碼的結(jié)構(gòu)嵌入層

本層主要作用是捕獲鄰域信息和嵌入節(jié)點(diǎn)拓?fù)湎蛄浚鐖D2第一行所示，從網(wǎng)絡(luò)拓?fù)涞洁徑泳仃囘M(jìn)而生成拓?fù)湎蛄浚罱K得到節(jié)點(diǎn)嵌入。本層以節(jié)點(diǎn)級別向量作為輸入，采用經(jīng)典RWR算法來豐富向量表示，該方法相比node2vec時(shí)間復(fù)雜度更低且所需要學(xué)習(xí)參數(shù)更少，同時(shí)在網(wǎng)絡(luò)數(shù)據(jù)挖掘中表現(xiàn)出了良好效果。

圖2 鏈路預(yù)測框架DTA-LP的工作流程Fig.2 Workflow of proposed link prediction framework DTA-LP

給定一個(gè)時(shí)間演化網(wǎng)絡(luò)G，對于每個(gè)時(shí)間t下有Gt=(V,At,Xt)，對鄰接矩陣At，對應(yīng)一個(gè)轉(zhuǎn)移矩陣T，T定義為從當(dāng)前節(jié)點(diǎn)游走到其他鄰居節(jié)點(diǎn)的概率，對于T中每一個(gè)行向量ti=ti di，di為第i個(gè)節(jié)點(diǎn)的度數(shù)，用α表示繼續(xù)游走的概率，1-α為重啟游走的概率，那么經(jīng)過K次游走之后到達(dá)每個(gè)節(jié)點(diǎn)的概率ptk可以由公式（1）計(jì)算：

因此在t時(shí)刻經(jīng)過K次游走之后，節(jié)點(diǎn)的拓?fù)渖舷挛南蛄慷x表示為：

at仿照自編碼的encoder部分，如公式（3）~（5）所示，計(jì)算過程中使用多個(gè)并行的編碼器，將其與動(dòng)態(tài)圖所關(guān)注時(shí)間長度關(guān)聯(lián)，簡稱之為回看（lookback，l）。對于每一個(gè)回看都存在一個(gè)編碼器，由不同維度的稠密層連接構(gòu)成。

其中，fa為激活函數(shù)（Leaky ReLU），W是權(quán)重矩陣，at∈N×N，p表示編碼器的層數(shù)，得到y(tǒng)t(p)為t時(shí)刻結(jié)構(gòu)嵌入，多個(gè)并行encoder最終得到結(jié)構(gòu)嵌入ys=為拓?fù)湎蛄壳度氲诫[式空間維度的大小，是一個(gè)重要的超參數(shù)。

2.2 基于注意力機(jī)制的拓?fù)浜蛯傩匀诤蠈?/h3>

由結(jié)構(gòu)嵌入層可以得到低維拓?fù)湎蛄縴s，本層是實(shí)現(xiàn)拓?fù)浜蛯傩匀诤稀Ｈ鐖D2第二行所示，拓?fù)浜蛯傩酝ㄟ^注意層生成嵌入，其中屬性數(shù)據(jù)Xt維度較低，不需要嵌入可以直接用于融合。不同時(shí)間下屬性信息，將結(jié)構(gòu)嵌入ys和ya作為輸入，通過公式（6）~（8）計(jì)算出融合嵌入yt。

2.3 基于LSTM的時(shí)間捕獲層

由注意層生成融合嵌入yt，特征中包含未處理時(shí)序信息，為捕獲網(wǎng)絡(luò)中時(shí)間變化模式，最終得到融合時(shí)間特征的嵌入。由圖2中時(shí)間捕獲層所示，構(gòu)建LSTM層，處理數(shù)據(jù)長時(shí)間依賴問題。第一個(gè)單層LSTM網(wǎng)絡(luò)的定義如下：

其中，yt是當(dāng)前時(shí)刻的輸入，ht-1是上一時(shí)刻的輸出，Wf為權(quán)重矩陣，b為偏置向量，σ為sigmoid函數(shù)輸出為0到1之間，公式（9）中ft為遺忘門，公式（12）中用ft?Ct-1控制Ct-1的通過，趨近于0時(shí)表示流入不能通過遺忘門，趨近于1時(shí)表示流入完全通過遺忘門。公式（10）、（11）為輸入門，為Ct-1添加當(dāng)前時(shí)刻新的輸入信息，對于it采用和遺忘門相同的原理，用sigmoid函數(shù)控制輸入信息，公式（11）使用tanh作為激活函數(shù)對輸入信息處理生成Ct，tanh函數(shù)控制輸出在?1到1之間，然后在公式（12）中用it?Ct控制輸入信息多少，并更新Ct-1成為當(dāng)前時(shí)刻的狀態(tài)。公式（13）、（14）為輸出門，公式（13）同樣采用sigmoid函數(shù)控制輸出信息，經(jīng)過公式（14）最終生成當(dāng)前輸出ht。經(jīng)過LSTM遺忘門、輸入門和輸出門能夠有效的防止了RNN梯度爆炸和梯度消失問題。

本文模型設(shè)計(jì)了兩層LSTM層來捕獲時(shí)序信息，第一層輸入為帶時(shí)序信息的融合嵌入yt，輸出為h=LSTM1(yt)，其中h={h1,h2,…,ht}∈Rt×d1作為第二層的輸入，即y=LSTM2(h)，其中y∈Rt×d2為最后一個(gè)時(shí)刻的輸出，d1、d2分別為第一層和第二層LSTM輸出維度，y為結(jié)構(gòu)、屬性和時(shí)序信息的融合嵌入，具體由公式（15）、（16）計(jì)算。

最后，由LSTM網(wǎng)絡(luò)生成的隱藏表示y被傳遞給一個(gè)由稠密層組成的解碼器，decoder完全按照encoder采用反向結(jié)構(gòu)設(shè)計(jì)得到，如圖2綠色解碼器所示最終得到At+1。

2.4 損失函數(shù)設(shè)計(jì)

對于動(dòng)態(tài)圖的鏈路預(yù)測而言，其目的是預(yù)測在下一時(shí)刻存在的邊。因此將損失函數(shù)設(shè)計(jì)為預(yù)測拓?fù)湎蛄縇和實(shí)際拓?fù)湎蛄縇的差值，為了增加預(yù)測概率，引用加權(quán)矩陣B對差值加權(quán)。B是通過鄰接矩陣At+1來構(gòu)造，與其不同之處在于At+1中aij=1時(shí)B中bij=β，其中β為懲罰項(xiàng)，損失函數(shù)設(shè)計(jì)為如下形式[30]：

在訓(xùn)練過程中，通過學(xué)習(xí)t時(shí)間段內(nèi)嵌入來預(yù)測在t+1時(shí)刻的邊。通過最小化上述損失函數(shù)來反向優(yōu)化模型參數(shù)，最終準(zhǔn)確預(yù)測未來的邊。

3 實(shí)驗(yàn)配置

所有實(shí)驗(yàn)均在64位16.04.1-Ubuntu系統(tǒng)上進(jìn)行，配置為Intel?Xeon?Gold 6240 CPU@2.60 GHz，RAM為256 GB，GUP為2×GeForce RTX 2080TI。

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

使用四個(gè)真實(shí)世界的數(shù)據(jù)集，相關(guān)信息如表2所示。DataBase systems and Logic Programming（DBLP-5）和Epinions用于基于結(jié)構(gòu)和屬性的動(dòng)態(tài)鏈路預(yù)測實(shí)驗(yàn)，Autonomous Systems（AS）和High Energy Physics Theory conference（Hep-TH）用于基于結(jié)構(gòu)的動(dòng)態(tài)鏈路預(yù)測實(shí)驗(yàn)。

表2 數(shù)據(jù)集的描述Table 2 Description of datasets

DBLP-5是一個(gè)研究者協(xié)作網(wǎng)絡(luò)數(shù)據(jù)集，作者來自五個(gè)研究領(lǐng)域。其中節(jié)點(diǎn)表示作者，網(wǎng)絡(luò)快照中的節(jié)點(diǎn)屬性是通過word2vec從通訊作者某一時(shí)間段的出版物標(biāo)題和摘要中提取出來的。

Epinions數(shù)據(jù)來自一個(gè)產(chǎn)品評論網(wǎng)站，根據(jù)用戶之間構(gòu)建的圖來尋求他人的建議。節(jié)點(diǎn)表示用戶，如果其中一個(gè)節(jié)點(diǎn)向另一個(gè)節(jié)點(diǎn)尋求建議，則兩個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)快照中存在邊，節(jié)點(diǎn)屬性由word2vec從評論中生成，考慮實(shí)驗(yàn)比對的公平性，從這個(gè)數(shù)據(jù)集中抽取2 000個(gè)節(jié)點(diǎn)進(jìn)行訓(xùn)練和測試。

AS數(shù)據(jù)來自BGP（邊界網(wǎng)關(guān)協(xié)議）日志對話的通信網(wǎng)絡(luò)，原始數(shù)據(jù)集時(shí)間從1997年11月8日到2000年1月2日，采用了時(shí)間最近的20個(gè)快照，從這個(gè)數(shù)據(jù)集中抽取2 000個(gè)節(jié)點(diǎn)的子圖。

Hep-TH是高能物理理論會(huì)議上作者的協(xié)作網(wǎng)絡(luò)，原始數(shù)據(jù)集包含1993年1月至2003年4月期間高能物理理論會(huì)議的論文摘要，采取一個(gè)月為一個(gè)時(shí)間跨度，提取了最近20個(gè)快照，同樣從這個(gè)數(shù)據(jù)集中抽取2 000個(gè)節(jié)點(diǎn)的子圖。

3.2 對比方法

將DTA-LP模型與當(dāng)前先進(jìn)的鏈路預(yù)測方法Dyn-AERNN和SLIDE比較。

DynAERNN是Dyngraph2vec中性能最好的鏈路預(yù)測模型，它是基于拓?fù)渚W(wǎng)絡(luò)的鏈路預(yù)測，使用t時(shí)刻之前的網(wǎng)絡(luò)拓?fù)鋪眍A(yù)測t+1時(shí)刻的邊。

SLIDE[22]是基于動(dòng)態(tài)屬性網(wǎng)絡(luò)的鏈路預(yù)測，使用t時(shí)刻之前的拓?fù)浜蛯傩孕畔眍A(yù)測t+1時(shí)刻的邊。

3.3 評價(jià)指標(biāo)

實(shí)驗(yàn)中，使用t+1時(shí)刻的圖來評估鏈路預(yù)測模型，使用平均精度（mean average precision，MAP）[30]作為衡量模型效果的指標(biāo)，MAP是對所有節(jié)點(diǎn)精度進(jìn)行平均之后的結(jié)果。

模型預(yù)測的邊用Epred表示，真實(shí)存在的邊用Etrue表示，P@k定義為正確預(yù)測前k條邊的得分，定義如下：

對于MAP的計(jì)算如下：

其中，Δi(j)表示頂點(diǎn)i到j(luò)存在邊，V是頂點(diǎn)集，MAP值越高，表明該模型對絕大多數(shù)節(jié)點(diǎn)的預(yù)測效果越好。

4 實(shí)驗(yàn)結(jié)果及分析

為了便于驗(yàn)證本文提出算法的有效性，進(jìn)行了三類實(shí)驗(yàn)：（1）基于拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)鏈路預(yù)測；（2）基于節(jié)點(diǎn)屬性的動(dòng)態(tài)鏈路預(yù)測；（3）基于拓?fù)浜蛯傩匀诤系膭?dòng)態(tài)鏈路預(yù)測。

4.1 基于拓?fù)鋽?shù)據(jù)的動(dòng)態(tài)鏈路預(yù)測

在基于拓?fù)浣Y(jié)構(gòu)的實(shí)驗(yàn)下，為探索不同嵌入維度對預(yù)測效果的影響，選取DBLP-5和Epinions兩個(gè)數(shù)據(jù)集，使用DynAERNN算法和所提算法進(jìn)行實(shí)驗(yàn)對比。結(jié)果如圖3所示，DTA-LP模型整體性能隨維度的增加而增 加。與DynAERNN算法相比，DTA-LP在DBLP-5數(shù)據(jù)集上性能提升50%，在Epinions數(shù)據(jù)集上性能提升1.2%。另一個(gè)發(fā)現(xiàn)是，在DBLP-5數(shù)據(jù)集上嵌入維度很低時(shí)，DTA-LP算法也有良好的性能，能夠很好地表達(dá)原始拓?fù)湫畔ⅲ档湍Ｐ蛷?fù)雜度。因此在DBLP-5數(shù)據(jù)集中選取嵌入維度最低的32作為后續(xù)實(shí)驗(yàn)參數(shù)，考慮到Epinions數(shù)據(jù)集的整體效果穩(wěn)定，選定最好性能256作為Epinions后續(xù)實(shí)驗(yàn)參數(shù)。

圖3 嵌入維度對性能的影響Fig.3 Impact of embedding dimensions on performance

此外，時(shí)間步長也是序列分析的一個(gè)重要參數(shù)，回看數(shù)據(jù)量變化在預(yù)測未來能發(fā)揮不同的作用。為了分析回看值lookback對MAP影響，回看值取值范圍從2到6，實(shí)驗(yàn)結(jié)果如圖4所示。與DynAERNN算法相比，DTA-LP模型在DBLP-5數(shù)據(jù)集上性能提升78%，隨著回看值不斷增加，DTA-LP算法預(yù)測精度呈正態(tài)分布，因此在選擇回看值參數(shù)時(shí)一般不會(huì)太小或太大，不同數(shù)據(jù)集也應(yīng)當(dāng)選擇適當(dāng)?shù)幕乜粗怠９试贒BLP-5和Epinions數(shù)據(jù)集上，分別選取回看值3和2作為后續(xù)實(shí)驗(yàn)的參數(shù)。

為測試迭代次數(shù)對性能的影響，在DBLP-5數(shù)據(jù)集上參數(shù)設(shè)置為lookback=3、embedding=32、Epoch步長為10。Epinions數(shù)據(jù)集上參數(shù)設(shè)置為lookback=2、embedding=256、Epoch步長為10。實(shí)驗(yàn)結(jié)果如圖5所示，由（a）、（c）子圖可知在兩個(gè)數(shù)據(jù)集上，DTA-LP算法MAP曲線一直位于DynAERNN上方，由（b）、（d）子圖可知Loss曲線一直處于DynAERNN下方，表明本文模型性能在結(jié)構(gòu)實(shí)驗(yàn)優(yōu)于DynAERNN。對比（b）、（d）損失函數(shù)曲線可以發(fā)現(xiàn)隨著Epoch不斷增加，DTA-LP算法取得了更快的下降效果及更小的Loss值。與此同時(shí)對應(yīng)DTA-LP算法MAP曲線有更快的上升效果及更高的MAP值。值得一提的是，在Epinions數(shù)據(jù)上，只將訓(xùn)練集固定為圖中的節(jié)點(diǎn)數(shù)，相比DynAERNN模型這是DTA-LP訓(xùn)練速度更快的原因之一。為節(jié)省模型訓(xùn)練時(shí)間，將DBLP-5和Epinions上Epoch參數(shù)分別設(shè)置為30和200。

圖5 Epoch對性能的影響1Fig.5 Impact of Epoch on performance

為進(jìn)一步說明DTA-LP模型的有效性，設(shè)計(jì)實(shí)驗(yàn)采用和DynAERNN論文中相同的數(shù)據(jù)集和模型參數(shù)，驗(yàn)證所提方法在結(jié)構(gòu)上的有效性。按照DynAERNN模型中設(shè)置參數(shù)embedding=128，sample=2 000，length=20，不同lookback下的結(jié)果如圖4（c）、（d）子圖所示。在AS數(shù)據(jù)集上DTA-LP模型和DynAERNN模型MAP值大致相同，在Hep數(shù)據(jù)集上雖然DTA-LP模型比起Dyn-AERNN模型的MAP標(biāo)準(zhǔn)差較大，但是卻有著最優(yōu)的MAP值。

圖4 回看值對性能的影響1Fig.4 Impact of lookback values on performance

綜上所有基于拓?fù)鋽?shù)據(jù)的實(shí)驗(yàn)表明，DTA-LP鏈路預(yù)測性能超過當(dāng)前先進(jìn)的動(dòng)態(tài)鏈路預(yù)測方法。

4.2 基于節(jié)點(diǎn)屬性的動(dòng)態(tài)鏈路預(yù)測

采用和拓?fù)鋵?shí)驗(yàn)相同設(shè)計(jì)思路，本實(shí)驗(yàn)進(jìn)行屬性上的動(dòng)態(tài)鏈路預(yù)測。對DBLP-5和Epinions數(shù)據(jù)集分別設(shè)計(jì)嵌入維度為64和16，探索以往時(shí)間步長對于之后結(jié)構(gòu)預(yù)測的影響，回看值取值范圍為2到6，測試屬性數(shù)據(jù)的動(dòng)態(tài)鏈路預(yù)測效果，結(jié)果如圖6所示。DynAERNN在屬性鏈路預(yù)測實(shí)驗(yàn)中，MAP值隨著回看值增加而呈現(xiàn)下降趨勢，而DTA-LP有增漲趨勢并呈現(xiàn)正態(tài)分布，且平均MAP值都明顯高于DynAERNN算法。在兩個(gè)數(shù)據(jù)集上MAP值分別提升82%和195%。在lookback=6時(shí)DynAERNN和DTA-LP算法MAP都顯著下降，分析原因是數(shù)據(jù)集只有11個(gè)時(shí)間步，lookback=6時(shí)由于訓(xùn)練集不足導(dǎo)致模型效果下降，這一點(diǎn)在結(jié)構(gòu)數(shù)據(jù)預(yù)測時(shí)也存在。為更好地捕獲屬性信息，在DBLP-5和Epinions數(shù)據(jù)集上將回看值分別設(shè)置為3和4。

圖6 回看值對性能的影響2Fig.6 Impact of lookback values on performance

實(shí)驗(yàn)同樣考慮DTA-LP模型在訓(xùn)練中MAP值和損失函數(shù)隨Epoch增加的變化，在DBLP-5和Epinions數(shù)據(jù)集上回看值分別設(shè)置為3和4，結(jié)果如圖7所示。總體來看DTA-LP比DynAERNN算法MAP值更高，Loss值更低，表明DTA-LP算法能夠很好地捕獲網(wǎng)絡(luò)屬性信息用于鏈路預(yù)測。由子圖（a）、（b）可知，在DBLP-5數(shù)據(jù)集上DTA-LP算法在Epoch=50時(shí)就能夠很好地完成，DynAERNN算法Epoch至少要70次才能夠收斂。從子圖（c）、（d）中看出DTA-LP算法比DynAERNN有更高的MAP值，DTA-LP算法在Epoch=1 400時(shí)趨于穩(wěn)定。

圖7 Epoch對性能的影響2Fig.7 Impact of Epoch on performance

綜上可說明，在動(dòng)態(tài)鏈路預(yù)測中屬性數(shù)據(jù)的有效性；可用t時(shí)刻之前節(jié)點(diǎn)的屬性來推測t+1時(shí)刻存在的邊；同時(shí)DTA-LP模型可以很好地捕獲動(dòng)態(tài)網(wǎng)絡(luò)的屬性信息。

4.3 基于拓?fù)浜蛯傩匀诤系膭?dòng)態(tài)鏈路預(yù)測

基于前面實(shí)驗(yàn)，本實(shí)驗(yàn)是運(yùn)用DTA-LP模型融合拓?fù)浜蛯傩赃M(jìn)行動(dòng)態(tài)鏈路預(yù)測，實(shí)驗(yàn)借鑒前兩部分探索得到的超參數(shù)來進(jìn)行。DBLP-5數(shù)據(jù)集上設(shè)置參數(shù)embedding=32，Epoch=30，Epinions數(shù)據(jù)集上設(shè)置embedding=256，Epoch=500。特別指出，在Epinions數(shù)據(jù)集上實(shí)驗(yàn)時(shí)，結(jié)構(gòu)嵌入和屬性向量采用拼接的方式進(jìn)行特征融合，實(shí)驗(yàn)結(jié)果由圖8和表3所示。

表3 DTA-LP、DynAERNN在Epinions數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果Table 3 Experimental results of DTA-LP and DynAERNN on Epinions dataset

圖8 DTA-LP、DynAERNN在DBLP數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果Fig.8 Experimental results of DTA-LP and DynAERNN in DBLP dataset

可以看出，在兩個(gè)數(shù)據(jù)集上DTA-LP融合實(shí)驗(yàn)的平均MAP得分最高，DTA-LP和DynAERNN拓?fù)鋵?shí)驗(yàn)結(jié)果次之。DTA-LP融合實(shí)驗(yàn)相比自身結(jié)構(gòu)實(shí)驗(yàn)，在DBLP-5和Epinions數(shù)據(jù)集上分別提升7.7%和1.1%，DTA-LP整體優(yōu)于DynAERNN算法。可以證明DTA-LP融合算法的優(yōu)越性，以及將拓?fù)浜蛯傩赃M(jìn)行融合方法的有效性。特別指出，考慮與其他算法比對的便捷性，DTA-LP融合實(shí)驗(yàn)沒有探索最優(yōu)的embedding、lookback和Epoch參數(shù)。僅參考前面的實(shí)驗(yàn)結(jié)果和參數(shù)，便可以得到比DynAERNN算法更優(yōu)的MAP值，足以說明DTA-LP算法在注意力融合機(jī)制的巨大能力和潛力。

為進(jìn)一步體現(xiàn)DTA-LP算法性能，在DBLP-5和Epinions數(shù)據(jù)集上對DTA-LP和SLIDE算法進(jìn)行了對比，結(jié)果如表4所示。DTA-LP能夠有效預(yù)測未來時(shí)刻的邊，取得較高的MAP值。可以說明DTA-LP在處理屬性和拓?fù)湫畔⑸舷啾萐LIDE取得了較大的進(jìn)步。

表4 DTA-LP、SLIDE融合實(shí)驗(yàn)的平均MAP值Table 4 Mean MAP values of DTA-LP，SLIDE fusion experiment

綜上，DTA-LP相比目前先進(jìn)的方法有了顯著提升。DTA-LP在結(jié)構(gòu)上優(yōu)于DynAERNN方法，并可以有效引入屬性信息，進(jìn)一步提升鏈路預(yù)測性能。通過與SLIDE方法對比，體現(xiàn)DTA-LP在動(dòng)態(tài)屬性圖上鏈路預(yù)測的高效性。

5 結(jié)論與展望

本文提出一種基于動(dòng)態(tài)屬性圖的鏈路預(yù)測方法，利用原始時(shí)序網(wǎng)絡(luò)中的拓?fù)浜蛯傩孕畔ⅲA(yù)測在下一時(shí)刻網(wǎng)絡(luò)可能存在的邊。提出了一種注意力融合機(jī)制，驗(yàn)證了模型在四個(gè)真實(shí)數(shù)據(jù)集上的有效性和可行性，說明了在動(dòng)態(tài)鏈路預(yù)測中節(jié)點(diǎn)屬性信息可以作為有效補(bǔ)充。融合模型效果優(yōu)于目前基于結(jié)構(gòu)以及屬性融合的鏈路預(yù)測算法。

在接下來的工作中，需要在更多的數(shù)據(jù)集上驗(yàn)證算法的可行性，需要通過注意力權(quán)重考慮節(jié)拓?fù)浜蛯傩詫︽溌奉A(yù)測的不同貢獻(xiàn)。之后研究不僅是融合屬性信息，還可以豐富更多網(wǎng)絡(luò)信息。