陳晉音,徐軒桁,吳洋洋,陳一賢,鄭海斌

(浙江工業(yè)大學 信息工程學院,杭州 310023)

1 引 言

復(fù)雜網(wǎng)絡(luò)的動態(tài)鏈路預(yù)測廣泛應(yīng)用于各個領(lǐng)域,包括社交網(wǎng)絡(luò)[1]、經(jīng)濟學[2]、生物學[3],及工業(yè)系統(tǒng)[4]等.絕大多數(shù)實際網(wǎng)絡(luò)的結(jié)構(gòu)隨時間推移而演變(節(jié)點或連邊隨著時間的推移而添加和刪除),這類網(wǎng)絡(luò)的鏈路預(yù)測稱為動態(tài)網(wǎng)絡(luò)鏈路預(yù)測[5-8].動態(tài)網(wǎng)絡(luò)鏈路預(yù)測已經(jīng)廣泛應(yīng)用于各種現(xiàn)實世界的網(wǎng)絡(luò)[9,10],包括社交網(wǎng)絡(luò)中預(yù)測朋友關(guān)系[11]、通信網(wǎng)絡(luò)中預(yù)測未來通信關(guān)系[12]、科學合作網(wǎng)絡(luò)中預(yù)測未來的同事關(guān)系[13]、社交安全網(wǎng)絡(luò)中定位犯罪分子并預(yù)測犯罪時間[14]、疾病傳染[15]、蛋白質(zhì)相互作用[16],及其他許多領(lǐng)域的演化模式.

動態(tài)網(wǎng)絡(luò)的鏈路隨時間的增加而變化,連邊使其預(yù)測比靜態(tài)網(wǎng)絡(luò)更具挑戰(zhàn)[17],如何準確地預(yù)測動態(tài)網(wǎng)絡(luò)中潛在的或未來的鏈路已經(jīng)受到了廣泛地關(guān)注.現(xiàn)有的許多動態(tài)網(wǎng)絡(luò)鏈路預(yù)測方法[14-18]利用歷史網(wǎng)絡(luò)信息并將其壓縮成一個網(wǎng)絡(luò)來預(yù)測下一時刻的網(wǎng)絡(luò)結(jié)構(gòu).最典型的方法是基于相似性的動態(tài)鏈路預(yù)測,最常見的比如共同鄰居CN等.基于機器學習的方法也應(yīng)用于計算鏈路預(yù)測的最佳相似性[19-23],但通常優(yōu)化方法的計算復(fù)雜度較高,容易受到現(xiàn)有的相似性指標的限制.網(wǎng)絡(luò)嵌入的方法也通常用于鏈路預(yù)測,比如DeepWalk[24],Node2vec[25],LINE[26]等.

然而,這些方法是從靜態(tài)網(wǎng)絡(luò)鏈路預(yù)測任務(wù)中演變而來,通常只是把先前時刻的網(wǎng)絡(luò)拓撲信息看作一個整體,而不考慮先前時刻網(wǎng)絡(luò)的動態(tài)演變過程.

除了只是利用動態(tài)網(wǎng)絡(luò)空間特征的動態(tài)鏈路預(yù)測方法之外,也有許多方法提出通過學習動態(tài)網(wǎng)絡(luò)的時間信息來提高動態(tài)鏈路預(yù)測性能.大部分方法通過將結(jié)構(gòu)信息和時間信息集成在一起來模擬動態(tài)演化過程.由于在動態(tài)網(wǎng)絡(luò)的演化過程中,最近的網(wǎng)絡(luò)對于未來的鏈路預(yù)測更加可靠,Nahla Mohamed Ahmed[8,30,31]等提出了利用阻尼系數(shù)對T個時刻的網(wǎng)絡(luò)的全局拓撲信息進行集合,從而得到更好的預(yù)測性能.也有不少研究者開始將時間信息集成到網(wǎng)絡(luò)嵌入中[32-36],在不同的時間步驟中學習每個頂點的表示向量,使其能夠捕獲動態(tài)演化模式.但是這些方法通常只關(guān)注未來新添加連邊,而忽略其他消失或者一直不變的連邊.在動態(tài)鏈路預(yù)測任務(wù)中,新添加的鏈路以及消失或者不變的鏈路分別反應(yīng)不同的網(wǎng)絡(luò)演化模型,所以需要關(guān)注所有的鏈路(存在或不存在的)并學習相應(yīng)的演化模式.

為了有效提高動態(tài)網(wǎng)絡(luò)鏈路預(yù)測的性能,大部分方法嘗試同時學習動態(tài)網(wǎng)絡(luò)的時序以及網(wǎng)絡(luò)特征,可是還存在著許多挑戰(zhàn).因此,本文提出了一種能夠處理時空數(shù)據(jù)的基于時空注意力的深度模型(GLAT),分別在時間以及空間上關(guān)注更多與預(yù)測任務(wù)息息相關(guān)的輸入特征,通過提取動態(tài)網(wǎng)絡(luò)的時空特征,實現(xiàn)端到端(end-to-end)的動態(tài)網(wǎng)絡(luò)的鏈路預(yù)測.GLAT模型的主要思想是充分利用GCN-attention模型學習隱藏狀態(tài)和單元節(jié)點的網(wǎng)絡(luò)結(jié)構(gòu),并通過LSTM-attention模型學習網(wǎng)絡(luò)的時間特征,將注意力集中在所學習的時空特征中與任務(wù)最相關(guān)的部分,從而提高動態(tài)鏈路預(yù)測性能.GLAT可以有效地處理高維、時間依賴、稀疏結(jié)構(gòu)的序列數(shù)據(jù).在四個真實數(shù)據(jù)集上進行了大量實驗.結(jié)果表明,GLAT模型明顯優(yōu)于當前其他先進方法.

本文的主要貢獻如下:

1)提出基于端到端的動態(tài)網(wǎng)絡(luò)鏈路預(yù)測模型(GLAT),有效的提取網(wǎng)絡(luò)的時空特征.其中,通過注意力圖卷積(GCN-attention)提取每個網(wǎng)絡(luò)的空間特征,重點關(guān)注鄰居節(jié)點的影響;通過注意力長短時記憶網(wǎng)絡(luò)(LSTM-attention)提取動態(tài)網(wǎng)絡(luò)的時序特征,關(guān)注每個節(jié)點在各個時刻的變化,從而提高預(yù)測模型的預(yù)測性能.

2)針對現(xiàn)有大部分方法只能預(yù)測部分網(wǎng)絡(luò)的鏈路,無法準確預(yù)測整體網(wǎng)絡(luò)的鏈路的缺陷,本文提出的GLAT通過計算整個網(wǎng)絡(luò)所有鏈路(存在的和不存在的)的概率分數(shù),實現(xiàn)整體網(wǎng)絡(luò)的鏈路預(yù)測.

3)通過大量不同的實驗,在多個動態(tài)網(wǎng)絡(luò)數(shù)據(jù)集上驗證了提出的方法的有效性,在AUC、GMAUC以及錯誤率等指標上,我們的模型明顯優(yōu)于目前的先進方法.

2 相關(guān)工作

近年來已提出許多動態(tài)網(wǎng)絡(luò)鏈路預(yù)測方法,其中大多數(shù)方法利用歷史網(wǎng)絡(luò)信息并將其壓縮成一個網(wǎng)絡(luò)來預(yù)測下一時刻的網(wǎng)絡(luò)結(jié)構(gòu).最典型的方法是基于相似性的動態(tài)鏈路預(yù)測[14],通過計算節(jié)點相似度判定是否存在連邊關(guān)系,即節(jié)點相似性越大,存在連邊的可能性越大.這類方法通常利用網(wǎng)絡(luò)的拓撲信息來定義節(jié)點的相似性,稱為結(jié)構(gòu)相似性指標,一般分為局部和全局的相似性指數(shù).局部相似性指數(shù)只需要節(jié)點的鄰域信息,例如共同鄰居(CN)[18],使用兩個節(jié)點的共同鄰居數(shù)量作為指標,簡單有效.其他常見的局部相似度指標包括JA、AA、RA、Salton指標等[14].全局相似度指標需要利用網(wǎng)絡(luò)的全局拓撲信息,常見的包括Katz、SimRank 、LHNI及MFI指標等[14].

方法[19-23]提出了基于機器學習進行動態(tài)鏈路預(yù)測,通過計算網(wǎng)絡(luò)的最佳相似性來提高鏈路預(yù)測的性能.Catherine A等[19]提出協(xié)方差矩陣自適應(yīng)演化策略(CMA-ES)進行優(yōu)化權(quán)重,從而實現(xiàn)了16個鄰域和節(jié)點相似性指標的線性組合,提高鏈路預(yù)測的精度.Chen等[20]提出了一種監(jiān)督的動態(tài)網(wǎng)絡(luò)鏈路預(yù)測方法,為每個屬性訓(xùn)練一個分類器,并集成所有分類器的結(jié)果進行鏈路預(yù)測.通常優(yōu)化方法的計算復(fù)雜度較高,易受到現(xiàn)有相似性指數(shù)的限制.

為了更深層次地考慮網(wǎng)絡(luò)的結(jié)構(gòu)相似性以及同質(zhì)性,提出了許多用于動態(tài)網(wǎng)絡(luò)鏈路預(yù)測的網(wǎng)絡(luò)嵌入方法.受word2vec的啟發(fā)而提出了DeepWalk[24]和node2vec[25],通過抽樣節(jié)點生成游走序列并利用skip-gram模型獲得節(jié)點和連邊的向量.其他基于隨機游走的方法,比如大規(guī)模信息網(wǎng)絡(luò)嵌入(LINE)[26],以類似的方式學習節(jié)點表征,但具有不同的游走策略.這樣的方法將網(wǎng)絡(luò)映射到低維向量空間以獲得每個連邊的特征向量,訓(xùn)練分類器來預(yù)測連邊(二分類:存在或不存在).

上述動態(tài)鏈路預(yù)測方法都基于網(wǎng)絡(luò),即根據(jù)給定時間內(nèi)網(wǎng)絡(luò)的結(jié)構(gòu)信息來預(yù)測未來時刻的鏈路關(guān)系.然而,這些方法僅考慮先前時刻的網(wǎng)絡(luò)拓撲信息作為一個整體,而忽略先前時刻網(wǎng)絡(luò)的動態(tài)演變過程.

除了學習動態(tài)網(wǎng)絡(luò)空間特征之外,也有方法通過學習動態(tài)網(wǎng)絡(luò)的時間信息來提高動態(tài)鏈路預(yù)測性能.人們開始利用先前的網(wǎng)絡(luò)序列來預(yù)測未來的鏈路,通過將結(jié)構(gòu)信息和時間信息集成在一起以模擬動態(tài)演化過程[8,27-31].Sina Sajadmanesh等[27]引入了非參數(shù)廣義線性模型(NP-GLM),根據(jù)鏈路出現(xiàn)時間的特征推斷出時間的潛在概率分布.由于網(wǎng)絡(luò)的動態(tài)特性,最近的對于未來的鏈路預(yù)測更可靠,Nahla Mohamed Ahmed等[8,30,31]提出了一種阻尼系數(shù)計算方式,對T(窗口尺寸)個時刻的網(wǎng)絡(luò)的全局拓撲信息進行集合,從而得到更好的結(jié)果.Xiaoyi Li等[29]提出了一種基于條件時間受限玻爾茲曼機(ctRBM)的深度模型框架,根據(jù)個體過渡方差以及局部鄰居的影響來預(yù)測鏈接.

由于現(xiàn)有的網(wǎng)絡(luò)嵌入方法直接應(yīng)用于動態(tài)圖的每個網(wǎng)絡(luò),很大程度上忽略了網(wǎng)絡(luò)的時間動態(tài)信息,因此不少研究[32-36]開始將時間信息集成到網(wǎng)絡(luò)嵌入中,使其能夠捕獲動態(tài)演化的動態(tài)演變.Giang Hoang Nguyen等[34]提出了從連續(xù)時間動態(tài)網(wǎng)絡(luò)學習時間約束的嵌入方法.Lekui Zhou等[35]提出了一種新的表征學習方法,即動態(tài)三元組學習法(DynamicTriad),保存給定網(wǎng)絡(luò)的結(jié)構(gòu)信息和演化模式,從而使模型能夠捕捉網(wǎng)絡(luò)動態(tài),并學習每個節(jié)點在不同的時間步驟中的表征向量.這些方法通常只關(guān)注未來新添加的連邊,而忽略其他消失或者不變的連邊.

長短時記憶網(wǎng)絡(luò)(LSTM)[37]最初由Sepp Hochreiter和Jrgen Schmidhuber于1997年提出,是RNN的一種特殊變種,可以處理長期依賴的時序數(shù)據(jù).LSTM已成功應(yīng)用于各個領(lǐng)域,比如圖像領(lǐng)域[38]、視頻處理領(lǐng)域[39]、語言模型[40]、語音識別[41]和機器翻譯等[42].最近,在動態(tài)網(wǎng)絡(luò)中,LSTM模塊用于自適應(yīng)地捕獲每個時間下表征的多維交互之間的依賴性[43].

大多數(shù)現(xiàn)實世界的網(wǎng)絡(luò)數(shù)據(jù)不具有規(guī)則的空間結(jié)構(gòu),導(dǎo)致在圖像領(lǐng)域中廣泛使用的卷積神經(jīng)網(wǎng)絡(luò)不能處理這些網(wǎng)絡(luò)數(shù)據(jù).因此,Joan Bruna[44]最早于2014年提出了圖形卷積網(wǎng)絡(luò)(GCN)來處理網(wǎng)絡(luò)數(shù)據(jù).最近,一些工作采用GCN來學習網(wǎng)絡(luò)數(shù)據(jù)的結(jié)構(gòu)特征,從而實現(xiàn)各種任務(wù),比如網(wǎng)絡(luò)表示學習和節(jié)點分類[45].

在許多基于序列的任務(wù)中,注意力機制(attention)已經(jīng)得到了廣泛的研究.注意機制的優(yōu)勢是幫助深度模型集中關(guān)注輸入中與任務(wù)最相關(guān)的部分,做出更好的決策.Mnih等[46]使用注意力更加關(guān)注輸入圖像對應(yīng)于圖像分類任務(wù)的相關(guān)部分.Xu等[47]使用注意力集中于圖像描述任務(wù)的關(guān)鍵圖像信息.Bahdanau D等[48]通過在輸出句子中生成相應(yīng)單詞時分配權(quán)重來反映機器翻譯任務(wù)的注意力,該權(quán)重反映了輸入句子中不同單詞的重要性.Ma等[49]提出了單個注意力模型在醫(yī)療診斷預(yù)測中的應(yīng)用,并提出了多種通用的注意力分數(shù)的計算公式.Wang等[50]把注意力模型應(yīng)用于新聞推薦/篩選領(lǐng)域,根據(jù)新聞的文本和種類信息,同時考慮新聞的時效性和時間特征來完成新聞篩選.此外,注意力模型還廣泛應(yīng)用于問答系統(tǒng)[51-53],根據(jù)問題發(fā)現(xiàn)哪一部分輸入和這個問題相關(guān),從而能生成更加相關(guān)的答案.總之,基于注意力機制的深度模型已在計算機視覺和自然語言處理領(lǐng)域中實現(xiàn)重要應(yīng)用.

注意力機制的深度模型在網(wǎng)絡(luò)領(lǐng)域也有成功應(yīng)用[54-56].Choi等[54]提出了基于注意力模型的醫(yī)學本體圖分析,他們的模型僅針對有向無環(huán)圖(DAG),而不是有向(無向)有權(quán)(無權(quán))網(wǎng)絡(luò).Velickovic等[55]提出了一種新的圖注意網(wǎng)絡(luò)(GAT)來執(zhí)行圖結(jié)構(gòu)數(shù)據(jù)的節(jié)點分類任務(wù),其思想是計算圖中每個節(jié)點的隱藏表示,通過遵循自我注意力策略來關(guān)注鄰居節(jié)點.Lee[56]研究了基于注意力的圖分類問題,提出了一種新的RNN模型,即圖注意模型(GAM),通過自適應(yīng)地選擇信息節(jié)點序列處理子圖.使用注意力機制幫助模型專注于圖中較小但信息豐富的部分,提高了模型的處理效率.

3 GLAT模型

本節(jié)介紹用于動態(tài)網(wǎng)絡(luò)鏈路預(yù)測的GLAT模型.它能夠根據(jù)時空注意力機制關(guān)注與任務(wù)相關(guān)的關(guān)鍵特征,為未來添加或刪除的連邊學習動態(tài)網(wǎng)絡(luò)的空間和時間特征.

3.1 總體框架

GLAT模型的核心思想是將注意力圖卷積(GCN-attention)和注意力長短時記憶網(wǎng)絡(luò)(LSTM-attention)的組合作為一個編碼器,放置在模型的輸入端用于學習結(jié)構(gòu)序列網(wǎng)絡(luò)的時空特征,利用注意力長短時記憶網(wǎng)絡(luò)(LSTM-attention)關(guān)注每個節(jié)點的多個時刻的隱藏表征并學習每個節(jié)點的連邊狀態(tài)的時序特征,同時利用(GCN-attention)通過更加關(guān)注每個節(jié)點的鄰居信息來學習每個時刻網(wǎng)絡(luò)的結(jié)構(gòu)特征.最后利用全連接層網(wǎng)絡(luò)作為解碼器來將提取的特征轉(zhuǎn)換回原始空間,輸出預(yù)測的網(wǎng)絡(luò)數(shù)據(jù),并以統(tǒng)一的方式實現(xiàn)動態(tài)網(wǎng)絡(luò)鏈路預(yù)測.模型系統(tǒng)框架如圖1所示.

3.2 模型設(shè)計

GLAT模型分成三個模塊:LSTM-attention模塊、GCN-attention模塊和解碼模塊.

圖1 GLAT模型的系統(tǒng)框圖Fig.1 Overall framework of GLAT

3.2.1 LSTM-attention模塊

首先將動態(tài)網(wǎng)絡(luò)里每一個時刻的網(wǎng)絡(luò)對應(yīng)的鄰接矩陣A作為輸入,利用所提出的LSTM-attention模型從結(jié)構(gòu)序列數(shù)據(jù){At-T,…,At-1}中提取相應(yīng)的時間特征{ht-T,…,ht-1},并通過時間注意力機制關(guān)注T個時刻的隱藏層向量h來計算上下文向量at.

LSTM-attention模塊主要依賴于兩個狀態(tài)值,即用于提取輸入信息的隱藏層狀態(tài)h,以及用于保存長期信息的細胞層狀態(tài)c.GLAT的關(guān)鍵在于它的細胞層狀態(tài)c貫穿整個前向過程中,導(dǎo)致信息在細胞層上傳遞可以保持長時間不變.在動態(tài)連邊預(yù)測任務(wù)中,由于細胞層狀態(tài)和隱藏層狀態(tài)分別反映不同的信息,我們建議使用兩個GCN模型分別對細胞層狀態(tài)和隱藏層狀態(tài)執(zhí)行卷積運算.

在LSTM-attention模型中,第一步是確定先前細胞層狀態(tài)的信息丟失量.這個決定通過遺忘門ft∈[0,1]d來完成,其中0表示完全遺忘,1表示完全保留,定義如下:

ft=σ(WfAt+Ufht-1+bf)

(1)

其中At∈RN×N定義為t時刻的輸入數(shù)據(jù),ht-1∈RN×d定義為t-1時刻的隱藏層狀態(tài),Wf∈RN×d、Uf∈Rd×d和bf∈Rd分別對應(yīng)遺忘門的權(quán)重和偏置矩陣,σ(·)表示sigmoid函數(shù),N表示輸入維度,d表示模型隱藏層維度.

(2)

其中Wi,c∈RN×d、Ui,c∈Rd×d和bi,c∈Rd分別對應(yīng)輸入門的權(quán)重和偏置矩陣.

這樣更新后的細胞層不僅可以保存長時間的信息,而且可以選擇性的過濾掉一些無用的信息.最后,我們需要決定把哪些更新后的細胞層信息輸出,次任務(wù)由輸出門來完成:

ot=σ(WoAt+Uoht-1+bo),ht=ot⊙tanh(ct)

(3)

其中,Wo∈RN×d、Uo∈Rd×d以及bo∈Rd分別對應(yīng)輸出門的權(quán)重和偏置矩陣.

在動態(tài)網(wǎng)絡(luò)鏈路預(yù)測任務(wù)中,最終目標是根據(jù)T個時刻的連邊矩陣的信息來預(yù)測下個時刻可能出現(xiàn)的鏈路狀態(tài).而{ht-T,…,ht-1}∈RN×d是經(jīng)過模型提取的每個時刻的網(wǎng)絡(luò)所有節(jié)點的特征矩陣,對于每個時刻的特征矩陣來說,它都可能包含預(yù)測需要的部分信息.因此,本文利用一個時間注意力機制來計算一個上下文向量ct,來捕獲時間下的相關(guān)信息,關(guān)注各個時間的特征向量來幫助實施預(yù)測任務(wù).時間注意機制僅根據(jù)每個時刻的隱藏層狀態(tài)來計算各個時刻對應(yīng)的注意力系數(shù),計算如下:

eti=Wtahi+bta

(4)

其中Wta∈RN×d和bta∈RN分別表示時間注意機制的權(quán)重和偏置矩陣.eti∈RN表示i時刻每個節(jié)點隱藏層向量對應(yīng)的注意力系數(shù).為了使注意力系數(shù)在不同時間之間易于比較,使用softmax函數(shù)對所有時刻對應(yīng)的eti進行標準化:

(5)

根據(jù)獲得的歸一化后的權(quán)重向量和T個時刻的隱藏層向量計算上下文向量:

(6)

最后獲得的上下文向量at∈RN×d作為LSTM-attention模塊最后輸出的時間特征向量.

3.2.2 GCN-attention模塊

在LSTM-attention模型中,每個時刻提取的時間特征h可以看成當前時刻所有節(jié)點向量的集合h={h1,h2,…,hN},hi∈Rd.本文把當前時刻所有節(jié)點向量的集合作為GCN-attention模型,通過空間注意力機制關(guān)注鄰居節(jié)點來更新每個節(jié)點的隱藏層向量.

首先,隱藏層向量與一個濾波器相乘,輸出新的隱藏層向量:

(7)

值得注意的是,本文采用K階的切比雪夫多項式來近似濾波器gθ,可以利用距離中心節(jié)點最大K階的節(jié)點信息,因此K是一個非常重要的超參數(shù).如圖2所示,當K=1,只考慮節(jié)點6本身的信息;當K=2,會考慮到1階節(jié)點(1,5,7)信息對節(jié)點6的影響;當K=3,會額外考慮到1階節(jié)點(1,5,7)以及2階節(jié)點(2,4,8,12)的信息.當K越大,可以考慮更大更廣的領(lǐng)域節(jié)點與中心節(jié)點的關(guān)系,但是會大大增加計算量.一般情況下,選擇K=3.

圖2 GCN的階數(shù)K的說明Fig.2 An illustration of K of GCN

當更新了隱藏層向量后,本文利用一個簡單的圖注意層作為空間注意力機制應(yīng)用于每個時刻的網(wǎng)絡(luò),如圖3所示.

本文在節(jié)點上執(zhí)行自我注意,即一個共享的注意力機制a:Rd×Rd→R來計算注意力系數(shù):

eij=a(hi,hj)

(8)

在實驗中,注意力機制a是一個簡單的單層前饋神經(jīng)網(wǎng)絡(luò):

eij=LeakyReLU(Wga1hi+Wga2hj)

(9)

其中,Wga1,Wga2∈Rd是相應(yīng)的權(quán)重矩陣,然后利用LeakyReLU(負值非零斜率=0.2)作為最后的非線性激活函數(shù).在圖注意層里,eij表明節(jié)點j的特征對于節(jié)點i的相似度.在最通用的表述中,注意力模型允許每個節(jié)點與其他所有節(jié)點之間計算注意力系數(shù),而丟棄所有結(jié)構(gòu)信息.通過執(zhí)行鄰域注意將網(wǎng)絡(luò)結(jié)構(gòu)加入到注意力機制中-我們只計算節(jié)點i與節(jié)點j∈Ni之間的注意力系數(shù)eij,其中Ni表示圖中節(jié)點i的鄰居節(jié)點集合.在所有的實驗中,這些將是i的1階鄰居節(jié)點集合(包括節(jié)點i本身).為了使注意力系數(shù)在不同節(jié)點之間易于比較,使用softmax函數(shù)在節(jié)點j的所有選項中對對應(yīng)的eij進行標準化:

(10)

歸一化后的注意力系數(shù)將用于計算與它們對應(yīng)的特征的線性組合,以用作每個節(jié)點的最終輸出特征:

(11)

更新后的隱藏層向量作為下一個時刻LSTM-attention模型的輸入.這樣LSTM-attention模型與GCN-attention模型構(gòu)成了GLAT的整個時間序列下的前向過程.最后獲得的上下文向量作為編碼器的最后輸出的時空特征向量.

圖3 圖注意層的整個框架Fig.3 Overall framework of graph attention layer

3.2.3 解碼器

為了輸出最終的預(yù)測網(wǎng)絡(luò),使用全連接層網(wǎng)絡(luò)作為解碼器,將編碼器最后輸出的特征向量轉(zhuǎn)換為最終的概率矩陣:

(12)

其中Wd∈Rd×N和bd∈RN分別表示解碼器的權(quán)重和偏置矩陣,L表示全連接層的層數(shù),并且每個隱藏層中的單元數(shù)量可以根據(jù)輸入數(shù)據(jù)的變化而變化,以獲得更好的性能.Pt∈RN×N表示最后的輸出鏈路概率矩陣,每一個Pt(i,j)=[0,1]表示節(jié)點i到節(jié)點j存在鏈路的概率,Pt(i,j)的值越大,鏈路存在的概率越大.

3.3 模型訓(xùn)練

訓(xùn)練整個GLAT模型的目的是為了讓動態(tài)網(wǎng)絡(luò)鏈路預(yù)測的準確率提高,使得預(yù)測輸出的概率矩陣Pt與t時刻的連邊矩陣At越相似越好,采用L2距離來衡量預(yù)測值與真實值之間的相似程度.

(13)

但是,由于網(wǎng)絡(luò)的稀疏性,導(dǎo)致連邊矩陣中零元素的數(shù)量要遠遠大于非零元素的數(shù)量,如果僅僅將L2范數(shù)作為所提出的級聯(lián)模型的Loss函數(shù),容易導(dǎo)致Loss函數(shù)更偏向于保證零元素的預(yù)測準確率,從而導(dǎo)致過擬合.為了保證模型能在一定程度上避免過擬合,添加正則化損失函數(shù)Lreg.本文通過計算GLAT模型中所有權(quán)重的F范數(shù)的平方和,來計算正則化損失:

(14)

訓(xùn)練過程中總的Loss定義為:

L=L2+βLreg

(15)

其中,β用于調(diào)整L2與Lreg的權(quán)重比例.在訓(xùn)練過程中,采用Adam優(yōu)化器來訓(xùn)練GLAT模型的參數(shù).

4 實驗與分析

4.1 實驗設(shè)計

本文在四個動態(tài)網(wǎng)絡(luò)數(shù)據(jù)集:CONTACT[57]、HYPERTEXT09[58]、ENRON和RADOSLAW[59]上實驗,并與CN[18]、node2vec[25]、LINE[26]和TNE[36]方法做結(jié)果對比.

表1 動態(tài)網(wǎng)絡(luò)數(shù)據(jù)和統(tǒng)計
Table 1 Dynamic network data and statistics

Dataset|V||ET| ddmaxTimespan(days)CONTACT27428.2K206.220923.97HYPERTEXT0911320.8K368.514832.46ENRON15150.5K669.851771137.55RADOSLAW16782.9K993.19053271.19

本文選擇AUC、GMAUC[17]以及錯誤率ErrorRate作為基準評價指標.

AUC:如果在n個獨立的比較中,如果存在n′次存在的連邊比不存在的連邊具有更高的分數(shù),以及n″次存在的連邊與不存在的連邊具有相同的分數(shù),則AUC定義為:

(16)

GMAUC:用于測量動態(tài)鏈接預(yù)測性能的度量標準.它通過幾何平均來結(jié)合PRAUC和AUC這兩個指標,因此GMAUC被定義為:

(17)

其中LA和LR分別表示增加連邊和移除連邊的數(shù)量,PRAUCnew表示在新出現(xiàn)連邊里計算的PRAUC分數(shù),AUCprev表示已經(jīng)存在的鏈路計算的AUC分數(shù).

ErrorRate:錯誤率被定義為錯誤預(yù)測鏈接的數(shù)量(由Nfalse表示)與真實存在的鏈接的總數(shù)(由Ntrue表示)的比值,具體表示為:

(18)

與僅計算兩個網(wǎng)絡(luò)中鏈接的絕對差的SumD不同,錯誤率考慮了真正存在的鏈接總數(shù)量來避免被欺騙.

特別的,本文將ErrorRate分為兩部分作為有效補充:ErrorRate+和ErrorRate-.ErrorRate+表示真實存在鏈接中錯誤預(yù)測鏈接數(shù)與所有鏈接總數(shù)之比.ErrorRate-表示真正不存在的鏈接中錯誤預(yù)測鏈接的數(shù)量與所有鏈接總數(shù)的比率.

4.2 實驗結(jié)果

在模型的訓(xùn)練過程中,把10個連續(xù)的網(wǎng)絡(luò){Gt-10,…,Gt-1}作為一個樣本輸入到GLAT中來預(yù)測Gt.對于TNE模型,和我們的GLAT模型具有相同的輸入.對于那些傳統(tǒng)的無法處理時間依賴性的方法CN、node2vec以及LINE來說,一般有以下兩種典型的處理方法:(1)只利用Gt-1的信息來預(yù)測Gt[60];(2)把先前10個網(wǎng)絡(luò)整合成一個靜態(tài)網(wǎng)絡(luò)來預(yù)測Gt[61].由于單單只利用上一個時刻網(wǎng)絡(luò)的信息來進行鏈路預(yù)測可能會出現(xiàn)信息量不足的情況,而且GLAT模型把10個連續(xù)的網(wǎng)絡(luò)作為輸入,為了保證輸入數(shù)據(jù)信息的相似性,本文選擇了第二種方法.

由于網(wǎng)絡(luò)的演化模式可能隨著時間而改變,選擇前20個測試樣本和全部80個樣本的三個性能指標的平均值來反應(yīng)預(yù)測模型的短期和長期預(yù)測性能.結(jié)果如表2所示,無論是密集還是稀疏的網(wǎng)絡(luò),GLAT模型的短期和長期預(yù)測能力幾乎在所有情況下都優(yōu)于其他方法.由于CN、node2vec和LINE方法的效果一般,表明這些為靜態(tài)網(wǎng)絡(luò)設(shè)計的方法并不適用于動態(tài)鏈路預(yù)測.相反,TNE和GLAT由于其捕捉動態(tài)特性的能力,在動態(tài)鏈路預(yù)測中獲得更好的性能.相比之下,GLAT模型在大多數(shù)情況下比TNE表現(xiàn)更好,特別是在能體現(xiàn)添加和刪除連邊的動態(tài)鏈路預(yù)測性能的GMAUC指標上.

此外,針對每個時刻的測試樣本,將預(yù)測的網(wǎng)絡(luò)與真實的網(wǎng)絡(luò)的鏈路差與真實存在的連邊進行比較來計算錯誤率.預(yù)測網(wǎng)絡(luò)和真實網(wǎng)絡(luò)之間的錯誤率的顯著差異表明該度量是對AUC的良好補充,以全面地測量動態(tài)鏈路預(yù)測的性能.如表2所示,大部分對比方法可能預(yù)測出比真正存在的鏈路數(shù)更多的無效連邊,從而導(dǎo)致了相對較大的錯誤率.傳統(tǒng)的網(wǎng)絡(luò)嵌入的方法node2vec以及LINE在錯誤率方面效果較差,錯誤地預(yù)測出大量無效鏈路,是真正存在鏈路數(shù)的10倍甚至70倍.這是因為動態(tài)網(wǎng)絡(luò)的鏈路隨時間演化,而網(wǎng)絡(luò)嵌入的方法利用的預(yù)訓(xùn)練的線性回歸模型無法捕捉鏈路的動態(tài)變化,從而對鏈路進行錯誤分類.TNE在錯誤率上效果也理想,這可能是因為TNE采用的矩陣分解方法在稀疏鄰接矩陣上無法平衡正負樣本,導(dǎo)致無法很好的處理我們給出的稀疏動態(tài)網(wǎng)絡(luò).而GLAT在錯誤率上明顯優(yōu)于其他所有對比算法,結(jié)果再次證明了GLAT模型在動態(tài)鏈路預(yù)測準確性方面具有更好性能.這是因為其他對比算法直接基于前10個網(wǎng)絡(luò)來預(yù)測下一個網(wǎng)絡(luò),GLAT需要根據(jù)前240個樣本中來預(yù)訓(xùn)練模型,可以更加有效地學習動態(tài)網(wǎng)絡(luò)的演化模式.同時,GLAT模型不僅使用LSTM來學習序列網(wǎng)絡(luò)的時序特性,還使用GCN來了解每個時刻的網(wǎng)絡(luò)特征,而且提出了一個時空注意力機制,可以有效的關(guān)注與任務(wù)息息相關(guān)的信息.因此,在測試過程中,我們的模型可以更準確地預(yù)測未來的連邊,具有較低的預(yù)測誤差.在這四個數(shù)據(jù)集中,ENRON數(shù)據(jù)集在時間序列上的演化過程中發(fā)生了較大的變化,導(dǎo)致所有方法在該數(shù)據(jù)集上的表現(xiàn)都有所下降.因此我們預(yù)先訓(xùn)練好的GLAT模型在測試集上的評估結(jié)果相對較差.從表2還可以得出,我們的模型在錯誤率方面的優(yōu)勢要遠遠大于AUC和GMAUC指標.這也從側(cè)面反應(yīng),與傳統(tǒng)的性能指標AUC和GMAUC相比,我們新定義的錯誤率度量在評估動態(tài)鏈路預(yù)測時更具可辨性.

表2 動態(tài)鏈路預(yù)測性能AUC、GMAUC以及誤差率
Table 2 Dynamic link prediction performances on AUC,GMAUC,Error Rate

評價指標方法CONTACTHYPERTEXT09ENRONRADOSLAW2080208020802080AUCCN0.85410.84570.66960.72660.72470.81020.83420.8408node2vec0.52120.51260.63480.65910.76590.68060.61030.7676LINE0.60640.42390.54160.53570.52940.50420.52920.5231TNE0.94420.93710.90760.85170.80960.83140.90530.8801GLAT0.99000.98730.95850.97370.88790.87110.98750.9862GMAUCCN0.84450.83300.60100.67490.68180.79290.82790.8343node2vec0.18050.13980.48910.51630.40690.54170.72410.7203LINE0.45020.38750.46860.37240.26420.23580.33410.3105TNE0.90830.89580.88560.83920.82330.79740.82820.8251GLAT0.99270.98840.98870.92170.91070.88310.99740.9978ErrorRateCN0.85960.78363.77635.26742.11113.30254.88805.6093node2vec29.34325.20724.39812.82668.80831.97120.71317.113LINE11.32711.42516.6906.78823.25712.1581.54883.0576TNE1.81691.66561.64531.96752.04682.93354.76354.3204GLAT0.21080.31150.21420.24340.37470.44310.17400.1882ER+CN0.28850.30510.56100.34190.53510.33880.25280.2201node2vec0.30010.29890.40870.35950.17430.34930.22250.2867LINE0.21190.22910.27300.34830.21170.19580.37600.2655TNE0.94360.94370.75980.58000.67020.45180.17950.1829GLAT0.15950.18580.18990.18840.15670.17780.10350.1175ER-CN0.57110.47853.21534.92551.57602.96374.63515.3892node2vec29.04324.90823.99012.46668.63331.62220.49016.826LINE11.11511.19616.4176.43923.04611.9621.17292.7921TNE0.87330.72190.88551.38741.37662.48174.58414.1375GLAT0.05130.12570.02440.05500.09710.10400.07050.0707

有趣的是,在大多數(shù)情況下,對比方法的ErrorRate-要遠遠大于ErrorRate+,尤其是node2vec和LINE.他們更有可能將不存在的鏈路預(yù)測為存在的鏈路.由于我們實驗的動態(tài)網(wǎng)絡(luò)數(shù)據(jù)基本上都是稀疏網(wǎng)絡(luò),因此嵌入式方法中的預(yù)訓(xùn)練分類器無法有效地對稀疏網(wǎng)絡(luò)進行分類.對于我們的GLAT方法,雖然ErrorRate+略大于ErrorRate-,但我們的方法的ErrorRate+仍然是所有比較實驗中最小的.進一步表明,我們的方法不僅在不存在的鏈路上具有很高的預(yù)測精度,而且在現(xiàn)有鏈路上具有更好的預(yù)測性能,可以更好地預(yù)測網(wǎng)絡(luò)的動態(tài)鏈路.

從表2可以看出,ErrorRate+的預(yù)測效果非常顯著,并且ErrorRate+可以很好地應(yīng)用于基因調(diào)控網(wǎng)絡(luò)中的聯(lián)合預(yù)測.在基因調(diào)控網(wǎng)絡(luò)中,節(jié)點代表基因,有向連邊表示基因之間的調(diào)節(jié)關(guān)系.我們的模型可以應(yīng)用于基因調(diào)控網(wǎng)絡(luò)的連邊預(yù)測,一方面可以進一步探索已知調(diào)控網(wǎng)絡(luò)的潛在調(diào)控關(guān)系,另一方面,它可以為未知基因調(diào)控提供研究方向.另外,在研究合作網(wǎng)絡(luò)中,一般會預(yù)測哪些研究人員會一起工作,但是不能錯誤地預(yù)測.因此,ErrorRate-在研究合作網(wǎng)絡(luò)中非常重要,誤差率越小,預(yù)測模型的性能越好.

表3 前10%重要鏈路的預(yù)測錯誤率
Table 3 Prediction error rate of the top 10% important links

評價指標方法CONTACTHYPERTEXT09ENRONRADOSLAW2080208020802080DCCN0.37800.44940.52880.58060.41300.41480.49100.5466node2vec0.59740.59760.43970.48370.62960.49910.49310.5037LINE0.73820.75200.42970.42300.39830.37890.51860.4691TNE0.82350.78430.28690.33600.24110.21380.23420.2450GLAT0.05100.07950.05780.08070.12530.13650.03570.0491EBCCN0.48680.53740.68650.41980.44330.40880.53470.5076node2vec0.63750.62950.56020.50640.51740.49630.50320.5361LINE0.81650.79520.71950.78740.72370.80490.90790.8541TNE0.97460.98460.66550.47050.64020.46690.36580.3543GLAT0.29290.41180.22660.27410.27900.30450.15490.1737

此外,在大多數(shù)情況下,GLAT模型在短期的預(yù)測性能上要優(yōu)于長期的預(yù)測性能,這是因為在測試集中,后半段的演化模式發(fā)生了變化,而我們的模型更傾向于擬合前半段的演化模式.

接著,針對80個測試樣本,其中Gt從1變化到80,繪制GLAT模型在四個數(shù)據(jù)集上獲得的AUC、GMAUC以及錯誤率這三個度量隨著時間變化而變化的曲線,作為時間t的函數(shù)來反應(yīng)動態(tài)鏈路預(yù)測性能.

圖4 在AUC、GMAUC以及錯誤率隨著時間變化而變化的曲線Fig.4 Curves of AUC,GMUUC,and Error rate as a function of time t

從圖4所示可以得到:隨著時間的增加,AUC和GMAUC在逐漸減小,而錯誤率在逐漸增加,這表明由于長時間下動態(tài)網(wǎng)絡(luò)演化的不確定性,針對動態(tài)網(wǎng)絡(luò)鏈路長時間預(yù)測相對困難.有趣的是,對于RADOSLAW數(shù)據(jù)集,預(yù)測性能相對穩(wěn)定,這可能是因為它的網(wǎng)絡(luò)結(jié)構(gòu)的演化模式呈現(xiàn)周期性,擁有很好的長時預(yù)測性能.為了進一步解釋這一現(xiàn)象,本文研究了四個網(wǎng)絡(luò)中兩個最常見的結(jié)構(gòu)特性(即平均度和平均聚類系數(shù))隨著時間增加的變化趨勢.結(jié)果如圖5所示,我們可以看到CONTACT、HYPERTEXT09和ENRON數(shù)據(jù)集里平均度和平均聚類系數(shù)隨著時間變化而發(fā)生了顯著變化,而RADOSLAW則相對穩(wěn)定.這些結(jié)果反映了本文提出的GLAT可以在動態(tài)網(wǎng)絡(luò)上可以實現(xiàn)較好的長期預(yù)測性能.

綜上所述,盡管一些方法在AUC這個統(tǒng)計指標上具有較優(yōu)的性能,但是它們在錯誤率上卻不盡人意,還是錯誤地預(yù)測了許多無效鏈路.但是在大多數(shù)現(xiàn)實場景中,我們可能只關(guān)心那些最重要的連邊是否預(yù)測正確.因此,進一步評價了所有模型在特別重要的部分鏈路上得預(yù)測性能.本文使用兩個度量來衡量每個連邊的重要性:度中心性(DC)和鏈路介數(shù)中心性(EBC).度中心性DC起初是根據(jù)鄰居的數(shù)量來衡量節(jié)點的重要性,本文利用源節(jié)點和目標節(jié)點的度中心性之和來衡量該條鏈路的重要性.當根據(jù)DC和EBC選出前10%重要鏈路后,計算這些重要鏈路的預(yù)測錯誤率,結(jié)果如表3所示.在大部分情況下,GLAT在四個數(shù)據(jù)集上具有最低的錯誤率,不管是短期還是長期預(yù)測.這進一步證明了GLAT在預(yù)測重要鏈路的方面仍然表現(xiàn)十分出色.此外,比較表2和表3的結(jié)果,發(fā)現(xiàn)前10%重要鏈路上的錯誤率要遠小于所有鏈路上的錯誤率率.這表明,GLAT在那些重要的鏈路上比不重要的鏈路的預(yù)測性能更加優(yōu)異.

圖5 網(wǎng)絡(luò)結(jié)構(gòu)屬性(平均度值和平均聚類系數(shù))隨著時間增加的變化趨勢Fig.5 Trends curves over time of network structure attributes(average value and average cluster coefficient)

5 結(jié) 論

本文提出了一種能夠處理時空數(shù)據(jù)的基于時空注意力的深度模型GLAT,用于動態(tài)鏈路預(yù)測.整個GLAT模型主要利用GCN-attention模型學習隱藏狀態(tài)和單元節(jié)點的網(wǎng)絡(luò)結(jié)構(gòu),并通過LSTM-attention模型學習網(wǎng)絡(luò)的時間特征,將注意力集中在所學習的時空特征中與任務(wù)最相關(guān)的部分,從而提高動態(tài)鏈路預(yù)測性能.最后利用全連接層網(wǎng)絡(luò)作為解碼器來將提取的時空特征轉(zhuǎn)換回原始空間,輸出預(yù)測的網(wǎng)絡(luò)數(shù)據(jù),從而實現(xiàn)動態(tài)網(wǎng)絡(luò)鏈路預(yù)測.GLAT不僅能捕捉連續(xù)網(wǎng)絡(luò)間的時間依賴性,還考慮到了網(wǎng)絡(luò)結(jié)構(gòu)的影響.因此,它可以更好地捕獲網(wǎng)絡(luò)演化的模式.最后,進行了大量實驗,與其他鏈路預(yù)測方法在各種動態(tài)網(wǎng)絡(luò)數(shù)據(jù)集上進行比較.結(jié)果表明,GLAT不僅在AUC、GMAUC以及錯誤率這幾個整體指標上明顯優(yōu)于其他模型,而且在重要鏈路預(yù)測任務(wù)上體現(xiàn)了優(yōu)異的性能.

未來的研究將側(cè)重于大規(guī)模的動態(tài)網(wǎng)絡(luò)的鏈路預(yù)測,盡可能降低所提出的GLAT模型的計算復(fù)雜度,使其能適應(yīng)其他各種應(yīng)用.此外,還需要研究并改進新的時空注意力機制來提高模型的性能.