動(dòng)態(tài)圖的鏈接預(yù)測(cè)模型

唐晨，趙杰煜，葉緒倫，鄭陽(yáng)，俞書世

寧波大學(xué) 信息科學(xué)與工程學(xué)院，浙江 寧波315211

互聯(lián)網(wǎng)的普及產(chǎn)生了大量的圖結(jié)構(gòu)數(shù)據(jù)，其中蘊(yùn)含著豐富的信息。雖然這些信息很難直接獲取，但是蘊(yùn)含很高的商業(yè)價(jià)值和社會(huì)價(jià)值。鏈接預(yù)測(cè)作為圖領(lǐng)域的典型問題，體現(xiàn)在現(xiàn)實(shí)生活的方方面面。例如在社交領(lǐng)域中，鏈接預(yù)測(cè)可以預(yù)測(cè)新朋友關(guān)系的產(chǎn)生，或是給用戶推薦新的朋友。在電子商務(wù)領(lǐng)域，鏈接預(yù)測(cè)可以為用戶提供個(gè)性化的商品推薦。在生物學(xué)領(lǐng)域，鏈接預(yù)測(cè)可以預(yù)測(cè)蛋白質(zhì)在交互作用的過程中可能發(fā)生的反應(yīng)，亦可發(fā)現(xiàn)基因序列中導(dǎo)致疾病的異?；颉?/p>

目前，靜態(tài)圖的鏈接預(yù)測(cè)模型已經(jīng)取得了非常好的效果，但是在現(xiàn)實(shí)世界中，圖的節(jié)點(diǎn)和鏈接通常是隨著時(shí)間變化的，靜態(tài)模型難以保留時(shí)域上的特征。比如在社交網(wǎng)絡(luò)中，任何時(shí)刻用戶都有可能因?yàn)椴糠謱傩园l(fā)生改變導(dǎo)致新鏈接的產(chǎn)生或者舊鏈接的消失。如圖1 所示，在-1 時(shí)刻，節(jié)點(diǎn)2 與節(jié)點(diǎn)1僅有一個(gè)共同鄰居節(jié)點(diǎn)3。在時(shí)刻，節(jié)點(diǎn)1 和節(jié)點(diǎn)5 之間新增了一條鏈接，則節(jié)點(diǎn)2 和節(jié)點(diǎn)1 的共同鄰居增長(zhǎng)到兩個(gè)，即節(jié)點(diǎn)3 和節(jié)點(diǎn)5。雖然時(shí)刻節(jié)點(diǎn)1、2、4 都有相同的鄰居節(jié)點(diǎn)，但是從時(shí)域的角度看，節(jié)點(diǎn)1 和節(jié)點(diǎn)2、4 共同鄰居的數(shù)量呈現(xiàn)增加的趨勢(shì)，因此在+1 時(shí)刻，節(jié)點(diǎn)1 和節(jié)點(diǎn)2、4 之間建立鏈接的可能性較大，而節(jié)點(diǎn)2 和節(jié)點(diǎn)4 雖然共同鄰居也是節(jié)點(diǎn)3 和節(jié)點(diǎn)5，但是在時(shí)域上，兩者的鄰居節(jié)點(diǎn)的數(shù)量比較穩(wěn)定，在+1 時(shí)刻建立鏈接的可能性較小。由此可見靜態(tài)圖的鏈接預(yù)測(cè)模型在動(dòng)態(tài)圖上的表現(xiàn)非常有限，無(wú)法捕捉圖在時(shí)間維度上變化的規(guī)律性，這更加凸顯了研究動(dòng)態(tài)圖鏈接預(yù)測(cè)模型的必要性。

圖1 動(dòng)態(tài)圖演變示意圖Fig.1 Schematic diagram of dynamic diagram evolution

針對(duì)動(dòng)態(tài)圖的鏈接預(yù)測(cè)問題，傳統(tǒng)的基于隨機(jī)游走和矩陣分解的模型具有計(jì)算效率高的優(yōu)點(diǎn)，但其無(wú)法利用深層次的特征，而且大部分模型最終會(huì)采用線性的方法進(jìn)行預(yù)測(cè)。目前比較主流的基于深度學(xué)習(xí)的做法是將圖神經(jīng)網(wǎng)絡(luò)（graph neural network，GNN）與循環(huán)神經(jīng)網(wǎng)絡(luò)（recurrent neural network，RNN）相結(jié)合。先利用GNN 學(xué)習(xí)靜態(tài)圖的節(jié)點(diǎn)嵌入，然后將節(jié)點(diǎn)嵌入作為時(shí)間序列信息輸入到RNN 模型。

然而，上述方法沒有考慮節(jié)點(diǎn)分類任務(wù)和鏈接預(yù)測(cè)任務(wù)的區(qū)別。分類任務(wù)更關(guān)注的是圖局部特征，鏈接預(yù)測(cè)問題更加關(guān)注的是圖全局特征。全局特征代表了圖的整體表現(xiàn)特性，一般屬于統(tǒng)計(jì)的范疇，而局部特征更加關(guān)注個(gè)體的細(xì)節(jié)，一般屬于組合的范疇。圖在時(shí)間維度的演化，是全局特征和局部特征共同作用的結(jié)果，全局特征包含了局部特征的成分，局部特征又在其某一方面反映了全局的信息。在動(dòng)態(tài)圖的鏈接預(yù)測(cè)問題上，則更應(yīng)該關(guān)注不同時(shí)刻的圖的共性。不可否認(rèn)，全局特征是多個(gè)局部特征歸一化的結(jié)果。因此，在鏈接預(yù)測(cè)任務(wù)中，提取特征這一部分需要一個(gè)合適的損失函數(shù)去均衡全局特征和局部特征。受到Hjelm 等人和Velickovic 等人工作的啟發(fā)，本文將利用圖卷積（graph convolutional network，GCN）和互信息（mutual information，MI）的優(yōu)點(diǎn)去構(gòu)造特征提取模塊。同時(shí)，為此模塊設(shè)計(jì)新的損失函數(shù)，該損失能在保證潛在特征更多地保留原始數(shù)據(jù)的概率特性的情況下，獲取有效的全局特征表示，這是其他動(dòng)態(tài)圖鏈接預(yù)測(cè)模型沒有考慮的。

全局特征是所有節(jié)點(diǎn)特征聚合的結(jié)果，如果其中某些節(jié)點(diǎn)特征發(fā)生異常，將會(huì)嚴(yán)重影響全局特征的提取。因此本文將全局特征表示為向量的形式，并將其本身視為隨機(jī)變量，其演化過程視為寬平穩(wěn)隨機(jī)過程，那么它將存在兩個(gè)概率性質(zhì)，即在一個(gè)時(shí)間窗口內(nèi)，全局特征的期望為常數(shù)，自相關(guān)函數(shù)只和時(shí)間差有關(guān)。依照上述規(guī)則，本文設(shè)計(jì)了一個(gè)感知模塊，約束全局特征在時(shí)域維度上以一個(gè)寬平穩(wěn)隨機(jī)過程的方式演化。

為了探索圖在時(shí)域上的演化規(guī)律，之前的研究是將所有節(jié)點(diǎn)特征作為長(zhǎng)短期記憶網(wǎng)絡(luò)（long shortterm memory networks，LSTM）的輸入，但是模型的學(xué)習(xí)能力有限，它無(wú)法用一組參數(shù)捕捉到所有節(jié)點(diǎn)在時(shí)域上的演化規(guī)律。雖然本文采用LSTM 來(lái)捕捉時(shí)域上的特征，但是不同的是本文用全局特征代替所有節(jié)點(diǎn)特征作為L(zhǎng)STM 的輸入。最后利用預(yù)測(cè)得到的全局特征構(gòu)造鏈接，與真實(shí)的鏈接進(jìn)行對(duì)抗訓(xùn)練，使預(yù)測(cè)值更加接近真實(shí)值。

本文的創(chuàng)新有以下兩點(diǎn)：

（1）設(shè)計(jì)了一個(gè)新穎的全局特征提取模塊，用于挖掘全局特征在動(dòng)態(tài)圖上的演變規(guī)律。該模塊以GCN 模型為基礎(chǔ)，利用全局特征和局部特征的互信息構(gòu)造對(duì)比損失函數(shù)，采用對(duì)抗的方式訓(xùn)練，保證了全局特征在時(shí)域上的傳遞。

（2）設(shè)計(jì)了感知模塊，對(duì)全局特征的平滑性做了約束。該模塊從寬平穩(wěn)隨機(jī)過程獲得靈感，通過對(duì)均值和自相關(guān)函數(shù)進(jìn)行限制，達(dá)到規(guī)范全局特征的演化過程，是個(gè)全局的概念。

1 相關(guān)工作

1.1 傳統(tǒng)的動(dòng)態(tài)圖鏈接預(yù)測(cè)模型

傳統(tǒng)的動(dòng)態(tài)圖鏈接預(yù)測(cè)模型大部分是先學(xué)習(xí)節(jié)點(diǎn)嵌入，然后利用傳統(tǒng)機(jī)器學(xué)習(xí)方法進(jìn)行分類。節(jié)點(diǎn)嵌入學(xué)習(xí)主要分為基于隨機(jī)游走和基于矩陣分解兩種。自從Perozzi 等人和Grover 等人分別提出DeepWalk 模型和node2vec 模型以來(lái)，基于隨機(jī)游走的方法廣泛應(yīng)用于圖的特征提取。比如在動(dòng)態(tài)圖上，Nguyen 等人關(guān)注時(shí)間的重要性，給每條鏈接的存在時(shí)間定義一個(gè)區(qū)間，剔除隨機(jī)游走產(chǎn)生的不合理的序列。Yu等人認(rèn)為如果圖不發(fā)生實(shí)質(zhì)性的變化，那么只需要在一個(gè)連續(xù)的時(shí)間段中重新采樣一些隨機(jī)游走序列即可。Ahmed 等人利用隨機(jī)游走為每個(gè)節(jié)點(diǎn)構(gòu)造子圖，在該節(jié)點(diǎn)周圍的子圖內(nèi)計(jì)算節(jié)點(diǎn)與其鄰居之間的相似度分?jǐn)?shù)，整合局部和全局拓?fù)湫畔ⅰ；诰仃嚪纸獾姆椒ㄍǔＪ歉鶕?jù)特征值將一個(gè)大矩陣拆分成幾個(gè)小矩陣相乘的形式。比如Li 等人和Zhu 等人提出的動(dòng)態(tài)屬性網(wǎng)絡(luò)嵌入（dynamic attributed networks embedding，DANE）模型和動(dòng)態(tài)高階鄰近保留嵌入（dynamic high-order proximity preserved embedding，DHPE）模型，都是基于廣義奇異值分解（generalized singular value decomposition，GSVD）和矩陣攝動(dòng)理論（matrix perturbation theory，MPT），在保留高階相似性的同時(shí)，動(dòng)態(tài)更新動(dòng)態(tài)網(wǎng)絡(luò)的節(jié)點(diǎn)表示。Ma 等人設(shè)計(jì)了一種新的矩陣分解規(guī)則，并從理論和實(shí)驗(yàn)上證明了算法的收斂性和準(zhǔn)確性。

1.2 基于圖神經(jīng)網(wǎng)絡(luò)的動(dòng)態(tài)圖鏈接預(yù)測(cè)模型

由于圖卷積神經(jīng)網(wǎng)絡(luò)在靜態(tài)圖上的強(qiáng)大性能，一些研究者將GCN 應(yīng)用于動(dòng)態(tài)圖的鏈接預(yù)測(cè)任務(wù)上，并取得了階段性的研究成果。比如Seo 等人提出了圖卷積循環(huán)網(wǎng)絡(luò)模型（graph convolutional recurrent network，GCRN），該模型有兩種形式：第一種是利用Defferrard 等人提出的GCN 模型提取靜態(tài)圖的特征，然后將特征作為L(zhǎng)STM 的輸入；第二種是在第一種的基礎(chǔ)上將LSTM 中的矩陣乘法替換成GCN 的操作。Manessi 等人引入殘差網(wǎng)絡(luò)的思想，將GCN 和LSTM 結(jié)合提出了瀑布動(dòng)態(tài)圖卷積神經(jīng)網(wǎng)絡(luò)（waterfall dynamic graph convolutional neural network，WD-GCN）和級(jí)聯(lián)動(dòng)態(tài)圖卷積神經(jīng)網(wǎng)絡(luò)（concatenate dynamic graph convolutional neural network，CD-GCN）模型，并成功地將模型從節(jié)點(diǎn)任務(wù)拓展到了圖任務(wù)上，在真實(shí)數(shù)據(jù)集上取得了很好的分類效果。Narayan 等人先利用PATCHY-SAN（PATCHY select-assemble-normalize）提取圖的空間特征，然后結(jié)合LSTM 提取時(shí)域特征，提出循環(huán)圖卷積神經(jīng)網(wǎng)絡(luò)（recurrent neural network on graph convolutional neural network，RgCNN）模型并在真實(shí)數(shù)據(jù)集上取得了優(yōu)于Manessi 等人的效果。Pareja 等人將關(guān)注點(diǎn)聚焦在模型本身的適應(yīng)性上而不是節(jié)點(diǎn)的嵌入上，提出了演化圖卷積神經(jīng)網(wǎng)絡(luò)（evolving graph convolutional network，EvolveGCN）模型，該模型不訓(xùn)練GCN 的參數(shù)，而是去訓(xùn)練RNN 模型的參數(shù)，使模型參數(shù)不會(huì)隨時(shí)間增長(zhǎng)而增長(zhǎng)。Lei 等人考慮到動(dòng)態(tài)圖在演化過程中的非線性特征，引入生成對(duì)抗網(wǎng)絡(luò)（generative adversarial networks，GAN），結(jié)合GCN和LSTM提出了GCN-GAN模型。

2 動(dòng)態(tài)圖鏈接預(yù)測(cè)模型

2.1 問題定義

2.2 整體架構(gòu)

本文提出了一種新的非線性時(shí)序預(yù)測(cè)模型LPMDG（link prediction model for dynamic graphs），解決動(dòng)態(tài)圖的鏈接預(yù)測(cè)問題。模型整體架構(gòu)如圖2所示，主要由四部分組成：（1）結(jié)構(gòu)特征提取模塊；（2）全局特征約束模塊；（3）時(shí)域特征提取模塊；（4）對(duì)抗網(wǎng)絡(luò)訓(xùn)練模塊。

圖2 LPMDG 整體框架圖Fig.2 LPMDG overall framework diagram

首先，選取一個(gè)合適的時(shí)間窗口大小，利用GCN 模型分別提取這個(gè)靜態(tài)圖的節(jié)點(diǎn)特征，通過優(yōu)化本文設(shè)計(jì)的損失函數(shù)，獲取圖的全局特征。再將個(gè)全局特征輸入到全局特征約束模塊，保證全局特征在時(shí)域上表現(xiàn)為寬平穩(wěn)隨機(jī)過程。接著，將全局特征輸入到時(shí)域特征提取模塊，抓取時(shí)域上的非線性特征。最后，將（1）（2）（3）視為一個(gè)生成器，另外設(shè)計(jì)一個(gè)全連接網(wǎng)絡(luò)作為判別器，利用GAN 的訓(xùn)練策略生成高質(zhì)量的鄰接矩陣。下面將詳細(xì)介紹LPMDG 模型的四部分。

由于靜態(tài)圖原始的節(jié)點(diǎn)特征通常是按照一定的主觀模式提取的，過于冗余，文中提出了結(jié)構(gòu)特征提取模塊，該模塊是利用GCN 和對(duì)抗訓(xùn)練方式，對(duì)原始特征進(jìn)行編碼，以獲取節(jié)點(diǎn)的潛在表示以及圖的全局特征。其中，GCN 是卷積神經(jīng)網(wǎng)絡(luò)（convolutional neural network，CNN）在非歐數(shù)據(jù)上的擴(kuò)展，自Kpif利用GCN 在半監(jiān)督節(jié)點(diǎn)分類任務(wù)上取得卓越成果后，GCN 被廣泛應(yīng)用于提取圖的結(jié)構(gòu)特征，本文亦通過GCN 提取節(jié)點(diǎn)特征中最關(guān)鍵的成分。對(duì)抗訓(xùn)練方式能協(xié)助GCN 模型挖掘特征不同維度之間的非線性關(guān)系。假設(shè)存在一個(gè)節(jié)點(diǎn)數(shù)為的圖，GCN 模型需要先得到圖的鄰接矩陣∈R和節(jié)點(diǎn)的特征矩陣∈R，然后利用式（2）進(jìn)行相鄰層之間的更新迭代。

為了得到全局特征，本文假設(shè)存在單射函數(shù):R→R，該函數(shù)能將節(jié)點(diǎn)特征映射成全局特征。眾所周知，最優(yōu)的全局特征應(yīng)該滿足兩點(diǎn)要求：（1）能最大程度地保留圖的信息；（2）節(jié)點(diǎn)特征通過神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)后依然能保留全局特征的成分。為了保證GCN 模型提取的全局特征能滿足要求（1），本文引入互信息理論加以分析，互信息是度量?jī)蓚€(gè)隨機(jī)變量之間的關(guān)聯(lián)程度，它表示一個(gè)隨機(jī)變量中包含另一個(gè)隨機(jī)變量的信息量（本文將節(jié)點(diǎn)特征和全局特征視為兩個(gè)隨機(jī)變量），值越大則兩個(gè)隨機(jī)變量相關(guān)性越強(qiáng)，互相包含的信息量也越多。形式上可以表示成：

其中，(*,*)表示互信息量，表示KL 散度。下面本文將從概率的角度分析為什么互信息能增強(qiáng)全局特征和節(jié)點(diǎn)特征的聯(lián)系。

互信息本身難以優(yōu)化，但是注意到，如果將兩個(gè)變量分開考慮（樣本來(lái)自()()）和綜合考慮（樣本來(lái)自(,)）導(dǎo)致結(jié)果差別很大，那么就可以說明這兩個(gè)變量、的關(guān)系很緊密。因此，為了優(yōu)化問題，本文通過固定樣本來(lái)源（(,)），以計(jì)算模型錯(cuò)誤分類的概率值之和，并將其命名為關(guān)聯(lián)距離（correlation distance，CD）。

（關(guān)聯(lián)距離）假設(shè)存在兩個(gè)集合、，并且滿足||≤||，{(,)}表示從聯(lián)合分布(,)采樣得到的樣本，則分類器將采樣的樣本判定為邊緣分布()()的概率之和被定義為關(guān)聯(lián)距離，形式上可寫成：

其中，Ω={Gs|Fs=(Gs)}。據(jù)此可以進(jìn)一步得到關(guān)聯(lián)距離的上界：

由此，可以得到定理1。

假設(shè)兩個(gè)集合、存在單射的關(guān)系，則最小化兩者關(guān)聯(lián)距離的誤差上界等同于最大化兩者的互信息。

上式可作如下理解，當(dāng)、之間的互信息逼近上界時(shí)，(|)向1 逼近，這與、一一對(duì)應(yīng)等價(jià)。因此得出最小化關(guān)聯(lián)距離等同于最大化互信息的結(jié)論。

因?yàn)?()，并且具有反函數(shù)，所以可逆推=()，進(jìn)而可得：

從形式上看，全局特征和高階特征的關(guān)系滿足定理1 的條件，同理可得：最小化全局特征和高階特征的關(guān)聯(lián)距離等價(jià)于最大化兩者的互信息，即：

綜合上述結(jié)論，可以總結(jié)出這樣一條規(guī)律：一定條件下，全局特征的學(xué)習(xí)，在滿足Infomax 準(zhǔn)則時(shí)達(dá)到最優(yōu)，即輸入和輸出的互信息最大時(shí)。為此，本文采用如下?lián)p失函數(shù)進(jìn)行對(duì)抗訓(xùn)練：

其中，表示判別器，X表示潛在特征，表示負(fù)樣本的特征。

雖然動(dòng)態(tài)圖的演化主要表現(xiàn)在時(shí)間維度上，但是內(nèi)在驅(qū)動(dòng)卻是靜態(tài)圖的規(guī)律性。平穩(wěn)過程是統(tǒng)計(jì)特性不隨時(shí)間變化而改變的隨機(jī)過程，是時(shí)序分析中尋找共性特征的重要工具，最常見的可分為嚴(yán)平穩(wěn)過程（strictly stationary process，SSP）和寬平穩(wěn)過程（weakly stationary process，WSP）。SSP 要求一切概率性質(zhì)都固定，這在統(tǒng)計(jì)上無(wú)法驗(yàn)證，而WSP 要求相對(duì)寬松，只需要期望和自相關(guān)函數(shù)不隨時(shí)間變化而改變即可。因此，本文假設(shè)全局特征在時(shí)域上是一個(gè)寬平穩(wěn)隨機(jī)過程，并設(shè)計(jì)與之對(duì)應(yīng)的感知模塊，該模塊收集一個(gè)時(shí)間窗口的全局特征，并且將這些特征作為采樣點(diǎn)去擬合整個(gè)時(shí)域演化曲線的概率特性，以此逼近真正的寬平穩(wěn)隨機(jī)過程。

若用{ε|∈}表示隨機(jī)過程，則WSP 的兩個(gè)性質(zhì)在形式上可以表示成：

為了讓上述兩個(gè)公式具有現(xiàn)實(shí)意義，給出定理2：

若存在集合={ε|∈}，且關(guān)系：(ε,ε)=(-)成立，則的子集也滿足關(guān)系。

顯然，在一個(gè)時(shí)間窗口中的全局特征{(-+1),(-+2),…,()}，其自相關(guān)函數(shù)滿足定理2：

同理，可得期望的表現(xiàn)形式：

其中，表示期望，(*,*)表示自相關(guān)函數(shù)，表示期望函數(shù)，表示隨機(jī)變量，表示函數(shù)，()表示時(shí)刻GCN 提取的全局特征。若自相關(guān)函數(shù)可逆，則由上述式（12）、式（13）和定理2，可以進(jìn)一步構(gòu)造損失函數(shù)：

其中，⊙表示哈達(dá)瑪積，表示時(shí)間窗口的大小，-表示時(shí)間差，將-進(jìn)行one-hot 編碼后作為標(biāo)簽，與全連接網(wǎng)絡(luò)MLP 的輸出構(gòu)造優(yōu)化目標(biāo)。

RNN 系列的模型是解決時(shí)域問題的有效方法，LSTM 是一種特殊的RNN，它通過利用門機(jī)制解決了RNN 在訓(xùn)練過程中梯度消失和梯度爆炸的問題。為了捕獲圖序列在時(shí)間維度上的長(zhǎng)短依賴關(guān)系，本文將GCN 提取的全局特征{(-+1),(-+2),…,()}作為L(zhǎng)STM 的輸入數(shù)據(jù)。通常標(biāo)準(zhǔn)的LSTM 包含三個(gè)門（遺忘門、輸入門、輸出門）和一個(gè)記憶細(xì)胞。例如在時(shí)刻，LSTM將-1 時(shí)刻的細(xì)胞狀態(tài)向量c和隱狀態(tài)向量h和時(shí)刻的輸入向量()同時(shí)作為輸入，然后輸出當(dāng)前時(shí)刻的狀態(tài)向量h：

LSTM 具體的更新步驟如下所示：

其中，i、o、f、c和h分別表示輸入門、輸出門、遺忘門、細(xì)胞狀態(tài)、隱狀態(tài)；{θ,θ,θ,θ,b,b,b,b}分別表示對(duì)應(yīng)的網(wǎng)絡(luò)參數(shù)；⊙表示哈達(dá)瑪積。激活函數(shù)如下：

當(dāng)()經(jīng)過LSTM 模型之后，得到預(yù)測(cè)的+1 時(shí)刻隱狀態(tài)h。本文在LSTM 之后另設(shè)計(jì)一個(gè)全連接神經(jīng)網(wǎng)絡(luò)，該網(wǎng)絡(luò)以h作為輸入，輸出維度為×，即預(yù)測(cè)的鄰接矩陣ˉ。為了訓(xùn)練LSTM，本文構(gòu)造均方差損失函數(shù)：

為了探索動(dòng)態(tài)圖在時(shí)域上演化規(guī)律的一致性，本文利用GAN 來(lái)提高LSTM 的性能。經(jīng)典的GAN由一個(gè)生成器和一個(gè)判別器組成，其優(yōu)化過程采用極小極大的策略。一方面，生成器生成偽數(shù)據(jù)欺騙判別器，讓判別器無(wú)法區(qū)分?jǐn)?shù)據(jù)的真?zhèn)危涣硪环矫?，判別器一直優(yōu)化性能，盡可能地區(qū)分真數(shù)據(jù)和偽數(shù)據(jù)。形式上表示為：

其中，和表示生成器和判別器的網(wǎng)絡(luò)參數(shù)。但是難以直接訓(xùn)練，通常是采用控制變量法將生成器和判別器分開訓(xùn)練，先訓(xùn)練判別器，然后訓(xùn)練生成器，如此反復(fù)迭代直至模型收斂，兩者的優(yōu)化目標(biāo)如下所示：

總結(jié)上述各部分，可得模型LPMDG 的訓(xùn)練過程，如算法1 所示。

LPMDG 算法

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

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

為了驗(yàn)證LPMDG 模型的有效性，本文在三個(gè)常用數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，這三個(gè)數(shù)據(jù)集的具體情況如表1 所示。

表1 數(shù)據(jù)集的具體情況Table 1 Details of dataset

USCB是衡量無(wú)線網(wǎng)狀網(wǎng)絡(luò)中鏈接質(zhì)量的數(shù)據(jù)集，圖中的節(jié)點(diǎn)表示電腦主機(jī)，圖中的鏈接權(quán)重表示某個(gè)時(shí)間片內(nèi)兩個(gè)主機(jī)之間的流量或者鏈接存在的質(zhì)量。為了構(gòu)造無(wú)權(quán)無(wú)向圖，本文設(shè)置一個(gè)質(zhì)量的閾值，權(quán)重大于閾值設(shè)為1，否則設(shè)為0。SBM是隨機(jī)圖模型生成的圖，它按一定的規(guī)則構(gòu)成社區(qū)并模擬社區(qū)的演化。AS是一個(gè)由路由器組成的通信網(wǎng)絡(luò)，圖中節(jié)點(diǎn)表示路由器，圖中鏈接表示路由器之間的流量交換，與處理USCB 數(shù)據(jù)集的方法相同，本文將AS 數(shù)據(jù)集設(shè)計(jì)成無(wú)權(quán)無(wú)向圖的演化序列。

本文采用MSE（mean square error）和AUC（area under the curve）兩個(gè)標(biāo)準(zhǔn)來(lái)評(píng)價(jià)模型的性能。MSE是最常見的評(píng)價(jià)指標(biāo)之一，它通過逐點(diǎn)比較預(yù)測(cè)值和真實(shí)值的距離得到模型性能的量化結(jié)果。AUC 是ROC（receiver operating characteristic curve）曲線下的面積，而ROC 曲線的橫縱坐標(biāo)是由真陽(yáng)性率（true positive rate，TPR）和偽陽(yáng)性率（false positive rate，F(xiàn)PR）構(gòu)成。AUC 值越大表示當(dāng)前的分類器越有可能將正樣本排在負(fù)樣本的前面，從而說明模型的分類效果更好。

為了驗(yàn)證模型的泛化能力，本文將提出的模型和下面四個(gè)模型進(jìn)行比較：

（1）GCN：第一個(gè)對(duì)比的模型是靜態(tài)的GCN 模型，該模型沒有任何針對(duì)時(shí)域信息的處理，僅對(duì)每一個(gè)時(shí)間片的靜態(tài)圖進(jìn)行建模。

（2）GCN-GRU：是在GCN 模型的基礎(chǔ)上，對(duì)每個(gè)節(jié)點(diǎn)的嵌入利用GRU（gated recurrent unit）遞歸模型進(jìn)行聯(lián)合訓(xùn)練。

（3）EnvolveGCN：利用RNN去更新GCN的參數(shù)，達(dá)到捕捉圖序列動(dòng)態(tài)性的目的，其中EnvolveGCN-h和EnvolveGCN-o 的區(qū)別在于RNN 的選取上，前者采用GRU，后者采用LSTM。

（4）GCN-GAN：將GAN、GCN、LSTM 進(jìn)行組合設(shè)計(jì)，利用GCN 提取靜態(tài)圖的特征，LSTM 捕捉時(shí)域信息，GAN 優(yōu)化模型的性能，充分發(fā)揮各個(gè)模塊的優(yōu)勢(shì)，直接生成圖的鄰接矩陣。

3.2 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證LPMDG 模型的有效性，本文的實(shí)驗(yàn)都是在統(tǒng)一的實(shí)驗(yàn)環(huán)境下進(jìn)行的，具體如表2 所示。另外，用于對(duì)比的模型均采用原論文的實(shí)驗(yàn)配置，而LPMDG 則采用如表3 所示的參數(shù)設(shè)置，并且在訓(xùn)練過程，本文使用Adam 優(yōu)化器進(jìn)行優(yōu)化，學(xué)習(xí)率設(shè)置為0.001。

表2 實(shí)驗(yàn)設(shè)置Table 2 Experimental setup

表3 模型參數(shù)設(shè)置Table 3 Setting of model parameters

3.3 結(jié)果與分析

實(shí)驗(yàn)結(jié)果如表4～表6 所示，通過觀察對(duì)比可以發(fā)現(xiàn)，LPMDG 的效果在大多數(shù)情況下優(yōu)于上述四種模型，這是因?yàn)長(zhǎng)PMDG 不僅考慮了時(shí)間的全局性，還考慮了空間的全局性。反觀另外幾個(gè)模型，GCN 并未考慮時(shí)間的因素，只是將參數(shù)更新過程視為圖在時(shí)域上的演化過程；GCN-GRU 雖然考慮了時(shí)間的影響，但是將每個(gè)節(jié)點(diǎn)看作一個(gè)單獨(dú)演化的過程，忽視了全局信息的作用；EnvolveGCN-h 和EnvolveGCN-o認(rèn)為圖的演化過程蘊(yùn)含在模型參數(shù)中，因此更加關(guān)注模型參數(shù)而不是單個(gè)節(jié)點(diǎn)，但是這種想法假設(shè)性太強(qiáng)，并且沒有關(guān)注圖本身的演化趨勢(shì)；GCN-GAN結(jié)合了GCN、LSTM 和GAN，但是依舊將節(jié)點(diǎn)單獨(dú)考慮，沒有考慮圖的整體性。

表4 USCB 的預(yù)測(cè)結(jié)果Table 4 Prediction results of USCB

表5 SBM 的預(yù)測(cè)結(jié)果Table 5 Prediction results of SBM

表6 AS 的預(yù)測(cè)結(jié)果Table 6 Prediction results of AS

本文的基準(zhǔn)模型是GCN-GAN，為了驗(yàn)證所提創(chuàng)新點(diǎn)的作用，本文構(gòu)造了LPMDG*模型。LPMDG*對(duì)應(yīng)于創(chuàng)新點(diǎn)1，比基準(zhǔn)模型更加注重全局特征，但是缺少WSD 的約束。LPMDG 則是本文的完整模型，由于創(chuàng)新點(diǎn)2 是基于創(chuàng)新點(diǎn)1 的，在實(shí)驗(yàn)部分不需要單獨(dú)驗(yàn)證創(chuàng)新點(diǎn)2 對(duì)于基準(zhǔn)模型的作用。從GCNGAN、LPMDG*和LPMDG 的實(shí)驗(yàn)結(jié)果來(lái)看，AUC 指標(biāo)都有不同程度的提升，MSE 在大多數(shù)情況下也是有所減小的，這足以說明全局特征對(duì)重構(gòu)任務(wù)的重要作用。另外LPMDG 在三個(gè)數(shù)據(jù)集上的表現(xiàn)都是優(yōu)于LPMDG*的，這也反映了寬平穩(wěn)隨機(jī)過程確實(shí)能約束圖在時(shí)域上的演化進(jìn)程。

本小節(jié)給出SBM 在訓(xùn)練過程中損失函數(shù)值的變化曲線，如圖3 所示。其中橫坐標(biāo)是迭代次數(shù)，縱坐標(biāo)是函數(shù)值?？梢钥闯?，損失值雖然在局部有些許的波動(dòng)，但是其整體趨勢(shì)是下降的，并且隨著迭代次數(shù)的增多，它的值逐漸收斂。由此，可間接證明本文模型在一定程度上是收斂的。

圖3 SBM 訓(xùn)練損失Fig.3 SBM training loss

超參數(shù)是影響神經(jīng)網(wǎng)絡(luò)性能的重要部分，比如LPMDG 模型中的時(shí)間窗口和隱空間的特征維度。據(jù)此，在USCB 和SBM 上做了進(jìn)一步的實(shí)驗(yàn)，觀察這些參數(shù)對(duì)本文模型的影響。首先，為了驗(yàn)證不同時(shí)間窗口的影響，將USCB 隱空間的特征維度定義成64，SBM 的設(shè)為32，時(shí)間窗口取值分別為{2，3，4，5，6，7，8，9，10}，得出圖4 和圖5 的實(shí)驗(yàn)結(jié)果。然后，為了驗(yàn)證潛在特征維度的影響，本文將USCB 的時(shí)間窗口定義為6，SBM 的時(shí)間窗口定義為10，潛在特征維度的取值為{16，32，64，128，256}，得出圖6 和圖7的實(shí)驗(yàn)結(jié)果。

圖4 AUC 實(shí)驗(yàn)結(jié)果（固定d）Fig.4 AUC experimental results(fixed d)

圖5 MSE 實(shí)驗(yàn)結(jié)果（固定d）Fig.5 MSE experimental results(fixed d)

圖6 AUC 實(shí)驗(yàn)結(jié)果（固定w）Fig.6 AUC experimental results(fixed w)

圖7 MSE 實(shí)驗(yàn)結(jié)果（固定w）Fig.7 MSE experimental results(fixed w)

從實(shí)驗(yàn)結(jié)果來(lái)看，當(dāng)=6，=64和=10，=32時(shí)，模型分別在USCB 和SBM 上的表現(xiàn)是最佳的。這是因?yàn)閁SCB 的節(jié)點(diǎn)個(gè)數(shù)相對(duì)較小，需要在隱空間增加維度，提高特征的表現(xiàn)力，而SBM 節(jié)點(diǎn)個(gè)數(shù)相對(duì)較多，原始的特征維度很容易造成信息冗余，在隱空間進(jìn)行適當(dāng)?shù)奶卣鹘稻S，能提高潛在特征的質(zhì)量。另外，同樣的改變，對(duì)于小的圖來(lái)說可能發(fā)生了大的變化，但是對(duì)于大的圖來(lái)說可能變化很小，因此節(jié)點(diǎn)少的數(shù)據(jù)集會(huì)更加注意短期的演變趨勢(shì)，節(jié)點(diǎn)多的數(shù)據(jù)集會(huì)更加關(guān)注長(zhǎng)期的變化方向。

4 結(jié)束語(yǔ)

針對(duì)動(dòng)態(tài)圖的鏈接預(yù)測(cè)問題，本文提出了LPDMG模型，該模型利用GCN、LSTM 和GAN 的優(yōu)勢(shì)，耦合局部特征和全局特征的關(guān)系，學(xué)習(xí)高質(zhì)量的全局特征表示。此外LPDMG 模型還考慮了全局特征在時(shí)域上的規(guī)律性，通過設(shè)計(jì)寬平穩(wěn)感知模塊，從而約束全局特征演化的平滑性。本文在三個(gè)動(dòng)態(tài)圖的數(shù)據(jù)集上對(duì)模型的性能進(jìn)行了驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，全局特征的高質(zhì)量和平滑性對(duì)鏈接預(yù)測(cè)模型有著重要作用。在未來(lái)，會(huì)嘗試將本文算法思想應(yīng)用于解決多關(guān)系圖和異構(gòu)圖的相關(guān)問題。