融合拓撲和屬性的動態(tài)網(wǎng)絡(luò)鏈路預(yù)測方法

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

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

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

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

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

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

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

（1）提出了一種新的動態(tài)鏈路預(yù)測方法DTA-LP，該模型可以有效地捕獲節(jié)點隨時間變化的屬性和拓撲信息。

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

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

1 問題描述

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

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

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

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

定義2（動態(tài)鏈路預(yù)測）給定一個動態(tài)屬性網(wǎng)絡(luò)G={G1,…,Gt,Gt+1}，其中節(jié)點的邊和屬性隨時間變化。動態(tài)鏈路預(yù)測目的是用t時間（根據(jù)步長決定t的取值范圍）拓撲和屬性去預(yù)測t+1時刻的拓撲信息。

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

圖1 基于網(wǎng)絡(luò)拓撲和屬性的動態(tài)鏈路預(yù)測圖解Fig.1 Illustration of dynamic link prediction based on network topology and attributes

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

本文旨在解決動態(tài)屬性網(wǎng)絡(luò)中拓撲和屬性相互融合以及隨時序演化的問題，提出的模型采用監(jiān)督性學(xué)習(xí)，模型借鑒圖表示性學(xué)習(xí)方法將網(wǎng)絡(luò)拓撲映射到低維向量空間R，并設(shè)計注意力機制對屬性和拓撲進行自適應(yīng)加權(quán)融合，通過LSTM和解碼器捕獲每個時間步和跨多個時間步節(jié)點之間的高度非線性關(guān)聯(lián)。模型由如下三部分組成：

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

（2）屬性融合層：網(wǎng)絡(luò)拓撲和屬性往往不是相互獨立的，可能會相互影響[22]。為使拓撲和屬性相互補充從中提取有效信息，本層采用注意力機制學(xué)習(xí)權(quán)重參數(shù)，完成拓撲和屬性融合。相比其他方法，注意力層的參數(shù)較少、解釋性較強、直觀簡潔且有利于后續(xù)統(tǒng)一處理時間特征。

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

DTA-LP模型框架如圖2所示，在預(yù)測At+1之前，首先RWR和編碼器得到拓撲向量嵌入ys，然后用拓撲嵌入和屬性向量ya進行融合生成yt，用LSTM捕獲時間的變化生成最終嵌入y，最后通過解碼器預(yù)測下一時刻的拓撲信息At+1。實驗表明，在網(wǎng)絡(luò)邊和節(jié)點屬性不斷變化的過程中，本文模型可以有效學(xué)習(xí)其中模式，從而提高鏈路預(yù)測精度。

模型具體步驟如算法1中所示，第2~6行用于從鄰域中提取網(wǎng)絡(luò)拓撲和屬性特征；第7行特征融合，有效保存拓撲和屬性信息；第8行用雙層LSTM捕獲網(wǎng)絡(luò)演化；第9~11行通過迭代訓(xùn)練模型；最終預(yù)測下一時刻拓撲結(jié)構(gòu)。

算法1融合拓撲和屬性的動態(tài)網(wǎng)絡(luò)鏈路預(yù)測方法

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

輸出：t+1時刻下鄰接矩陣A

1.對原始數(shù)據(jù)構(gòu)建拓撲鄰接矩陣A和節(jié)點屬性向量X

2.輸入A，根據(jù)公式（1）、（2）得到節(jié)點的拓撲向量表示S

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）反向計算得到L

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

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

13.end for

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

本層主要作用是捕獲鄰域信息和嵌入節(jié)點拓撲向量，如圖2第一行所示，從網(wǎng)絡(luò)拓撲到鄰接矩陣進而生成拓撲向量，最終得到節(jié)點嵌入。本層以節(jié)點級別向量作為輸入，采用經(jīng)典RWR算法來豐富向量表示，該方法相比node2vec時間復(fù)雜度更低且所需要學(xué)習(xí)參數(shù)更少，同時在網(wǎng)絡(luò)數(shù)據(jù)挖掘中表現(xiàn)出了良好效果。

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

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

因此在t時刻經(jīng)過K次游走之后，節(jié)點的拓撲上下文向量定義表示為：

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

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

2.2 基于注意力機制的拓撲和屬性融合層

由結(jié)構(gòu)嵌入層可以得到低維拓撲向量ys，本層是實現(xiàn)拓撲和屬性融合。如圖2第二行所示，拓撲和屬性通過注意層生成嵌入，其中屬性數(shù)據(jù)Xt維度較低，不需要嵌入可以直接用于融合。不同時間下屬性信息，將結(jié)構(gòu)嵌入ys和ya作為輸入，通過公式（6）~（8）計算出融合嵌入yt。

2.3 基于LSTM的時間捕獲層

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

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

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

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

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

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

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

3 實驗配置

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

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

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

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

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

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

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

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

3.2 對比方法

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

DynAERNN是Dyngraph2vec中性能最好的鏈路預(yù)測模型，它是基于拓撲網(wǎng)絡(luò)的鏈路預(yù)測，使用t時刻之前的網(wǎng)絡(luò)拓撲來預(yù)測t+1時刻的邊。

SLIDE[22]是基于動態(tài)屬性網(wǎng)絡(luò)的鏈路預(yù)測，使用t時刻之前的拓撲和屬性信息來預(yù)測t+1時刻的邊。

3.3 評價指標(biāo)

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

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

對于MAP的計算如下：

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

4 實驗結(jié)果及分析

為了便于驗證本文提出算法的有效性，進行了三類實驗：（1）基于拓撲結(jié)構(gòu)的動態(tài)鏈路預(yù)測；（2）基于節(jié)點屬性的動態(tài)鏈路預(yù)測；（3）基于拓撲和屬性融合的動態(tài)鏈路預(yù)測。

4.1 基于拓撲數(shù)據(jù)的動態(tài)鏈路預(yù)測

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

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

此外，時間步長也是序列分析的一個重要參數(shù)，回看數(shù)據(jù)量變化在預(yù)測未來能發(fā)揮不同的作用。為了分析回看值lookback對MAP影響，回看值取值范圍從2到6，實驗結(jié)果如圖4所示。與DynAERNN算法相比，DTA-LP模型在DBLP-5數(shù)據(jù)集上性能提升78%，隨著回看值不斷增加，DTA-LP算法預(yù)測精度呈正態(tài)分布，因此在選擇回看值參數(shù)時一般不會太小或太大，不同數(shù)據(jù)集也應(yīng)當(dāng)選擇適當(dāng)?shù)幕乜粗?。故在DBLP-5和Epinions數(shù)據(jù)集上，分別選取回看值3和2作為后續(xù)實驗的參數(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。實驗結(jié)果如圖5所示，由（a）、（c）子圖可知在兩個數(shù)據(jù)集上，DTA-LP算法MAP曲線一直位于DynAERNN上方，由（b）、（d）子圖可知Loss曲線一直處于DynAERNN下方，表明本文模型性能在結(jié)構(gòu)實驗優(yōu)于DynAERNN。對比（b）、（d）損失函數(shù)曲線可以發(fā)現(xiàn)隨著Epoch不斷增加，DTA-LP算法取得了更快的下降效果及更小的Loss值。與此同時對應(yīng)DTA-LP算法MAP曲線有更快的上升效果及更高的MAP值。值得一提的是，在Epinions數(shù)據(jù)上，只將訓(xùn)練集固定為圖中的節(jié)點數(shù)，相比DynAERNN模型這是DTA-LP訓(xùn)練速度更快的原因之一。為節(jié)省模型訓(xùn)練時間，將DBLP-5和Epinions上Epoch參數(shù)分別設(shè)置為30和200。

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

為進一步說明DTA-LP模型的有效性，設(shè)計實驗采用和DynAERNN論文中相同的數(shù)據(jù)集和模型參數(shù)，驗證所提方法在結(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

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

4.2 基于節(jié)點屬性的動態(tài)鏈路預(yù)測

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

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

實驗同樣考慮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時就能夠很好地完成，DynAERNN算法Epoch至少要70次才能夠收斂。從子圖（c）、（d）中看出DTA-LP算法比DynAERNN有更高的MAP值，DTA-LP算法在Epoch=1 400時趨于穩(wěn)定。

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

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

4.3 基于拓撲和屬性融合的動態(tài)鏈路預(yù)測

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

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

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

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

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

表4 DTA-LP、SLIDE融合實驗的平均MAP值Table 4 Mean MAP values of DTA-LP，SLIDE fusion experiment

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

5 結(jié)論與展望

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

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