條件變分時(shí)序圖自編碼器

陳可佳 魯 浩 張嘉俊

1(南京郵電大學(xué)計(jì)算機(jī)學(xué)院 南京 210023)2(江蘇省大數(shù)據(jù)安全與智能處理重點(diǎn)實(shí)驗(yàn)室(南京郵電大學(xué)) 南京 210023)(chenkj@njupt.edu.cn)

許多現(xiàn)實(shí)世界的數(shù)據(jù)(如蛋白質(zhì)交互網(wǎng)絡(luò)[1]、社交網(wǎng)絡(luò)[2]、引文網(wǎng)絡(luò)[3]等)都可以抽象為圖的形式，以表示數(shù)據(jù)中對象之間的復(fù)雜關(guān)系.在傳統(tǒng)的復(fù)雜網(wǎng)絡(luò)分析中，網(wǎng)絡(luò)特征的提取需要專家手動(dòng)進(jìn)行，很大程度上依賴于網(wǎng)絡(luò)的類型、專家的經(jīng)驗(yàn)和特定的任務(wù)類型.網(wǎng)絡(luò)表示學(xué)習(xí)(也稱為圖嵌入)[4-5]旨在從網(wǎng)絡(luò)中學(xué)得有效的低維向量表示，已出現(xiàn)了許多有效的算法[6-8]來捕獲網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息.大多現(xiàn)有的網(wǎng)絡(luò)表示學(xué)習(xí)算法假設(shè)網(wǎng)絡(luò)中的節(jié)點(diǎn)和邊固定不變.然而，現(xiàn)實(shí)網(wǎng)絡(luò)通常是動(dòng)態(tài)的[9]，節(jié)點(diǎn)和邊會(huì)在不同的時(shí)刻出現(xiàn)或消失.例如引文網(wǎng)絡(luò)中論文的數(shù)量和引用關(guān)系均會(huì)隨時(shí)間不斷地累積.對動(dòng)態(tài)網(wǎng)絡(luò)進(jìn)行建模時(shí)，應(yīng)該考慮節(jié)點(diǎn)和邊隨時(shí)間的變化情況，通常的做法[10]是將動(dòng)態(tài)網(wǎng)絡(luò)表示為一系列的靜態(tài)網(wǎng)絡(luò)快照，分別計(jì)算每個(gè)快照網(wǎng)絡(luò)下的嵌入表示，然后將所有快照下的嵌入對齊并映射到相同的向量空間中.為此，需要設(shè)計(jì)一個(gè)聯(lián)合優(yōu)化函數(shù)找到共同的嵌入向量，進(jìn)行非凸和非線性優(yōu)化問題.

目前，深度神經(jīng)網(wǎng)絡(luò)已在計(jì)算機(jī)視覺、自然語言處理等領(lǐng)域展示了其優(yōu)秀的數(shù)據(jù)表示能力，并在靜態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)中取得了巨大的成功[11-12].與基于矩陣分解和基于隨機(jī)游走的方法相比，基于深度神經(jīng)網(wǎng)絡(luò)的方法更能有效擬合復(fù)雜的非線性目標(biāo)函數(shù)，因而更適用于解決動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)問題.Kipf等人[13]在變分自編碼器的框架中使用靜態(tài)的圖卷積作為編碼器、內(nèi)積作為解碼器指導(dǎo)隱層的表示學(xué)習(xí).受該工作的啟發(fā)，本文嘗試在條件變分自編碼器的框架下解決動(dòng)態(tài)圖嵌入問題，使用深度圖神經(jīng)網(wǎng)絡(luò)聚合網(wǎng)絡(luò)的結(jié)構(gòu)、節(jié)點(diǎn)的屬性和時(shí)序信息.我們首先使用邊的時(shí)序信息改進(jìn)傳統(tǒng)的圖卷積操作，得到時(shí)序圖卷積模型，然后加入到條件變分自編碼器框架中，訓(xùn)練得到網(wǎng)絡(luò)的動(dòng)態(tài)嵌入.其中，條件變分自編碼器也可換為自編碼器或變分自編碼器.

本文的主要貢獻(xiàn)包括4個(gè)方面：

1) 提出了一種能同時(shí)聚合網(wǎng)絡(luò)結(jié)構(gòu)、節(jié)點(diǎn)屬性和時(shí)間信息的時(shí)序圖卷積模型;

2) 時(shí)序圖卷積作為編碼器放置于自編碼器或變分自編碼器框架中，實(shí)現(xiàn)動(dòng)態(tài)圖嵌入;

3) 在此基礎(chǔ)上進(jìn)一步使用節(jié)點(diǎn)的鄰域時(shí)序信息，實(shí)現(xiàn)條件變分時(shí)序圖自編碼器模型;

4) 不同類型網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文提出的模型可以獲得更有效的動(dòng)態(tài)圖嵌入表示.

1 相關(guān)工作

動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)是一個(gè)具有挑戰(zhàn)的問題，需要考慮網(wǎng)絡(luò)隨時(shí)間的演化結(jié)構(gòu).根據(jù)所采用的技術(shù)，已有的動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)方法大致可分為4類：基于矩陣分解的方法、類skip-gram的方法、基于自編碼器的方法和基于圖卷積的方法.

基于矩陣分解的動(dòng)態(tài)網(wǎng)絡(luò)嵌入是將靜態(tài)網(wǎng)絡(luò)矩陣分解的思想引入動(dòng)態(tài)網(wǎng)絡(luò)，通過矩陣攝動(dòng)理論逐步更新網(wǎng)絡(luò)的嵌入表示.例如：DHPE模型[14]使用時(shí)間快照作為節(jié)點(diǎn)特征的采樣粒度，將廣義奇異值分解和矩陣攝動(dòng)理論運(yùn)用于鄰接矩陣上，在保證節(jié)點(diǎn)高階相似性的前提下，隨著邊的增加或刪除及時(shí)更新節(jié)點(diǎn)的表示.

類skip-gram的動(dòng)態(tài)網(wǎng)絡(luò)嵌入是將整個(gè)網(wǎng)絡(luò)視為語料，找到能表征網(wǎng)絡(luò)演化的方法對語料進(jìn)行采樣，最后使用skip-gram模型[15]對語料進(jìn)行訓(xùn)練.例如：CTDNE模型[16]將動(dòng)態(tài)網(wǎng)絡(luò)表示為一個(gè)連續(xù)時(shí)間網(wǎng)絡(luò)，在時(shí)間序列限制下進(jìn)行隨機(jī)游走，得到的隨機(jī)游走序列集合可視為靜態(tài)網(wǎng)絡(luò)下隨機(jī)游走序列集合的子集.通過捕獲連續(xù)時(shí)間下節(jié)點(diǎn)之間的依賴性，該模型有效解決了時(shí)間快照方法導(dǎo)致的精度損失問題.

基于自編碼器的動(dòng)態(tài)網(wǎng)絡(luò)嵌入大多是對靜態(tài)網(wǎng)絡(luò)中的SDNE模型[17](即基于半監(jiān)督深層自編碼器的網(wǎng)絡(luò)嵌入)的改進(jìn)和擴(kuò)展.例如：DynGEM[18]模型將動(dòng)態(tài)網(wǎng)絡(luò)拆分為不同的快照，對每個(gè)快照網(wǎng)絡(luò)使用SDNE學(xué)到該時(shí)刻下的網(wǎng)絡(luò)嵌入，后一時(shí)刻模型的初始化參數(shù)直接來自于前一時(shí)刻，從而加快了訓(xùn)練速度.隨后，Dyngraph2vec[19]模型對此進(jìn)行了改進(jìn)，將先前一組(而不僅僅是前一時(shí)刻)快照網(wǎng)絡(luò)的表示學(xué)習(xí)參數(shù)作為輸入，得到下一時(shí)刻的網(wǎng)絡(luò)嵌入，從而捕獲每個(gè)時(shí)刻中節(jié)點(diǎn)之間的非線性交互關(guān)系以及多個(gè)時(shí)刻之間的交互關(guān)系.

基于圖卷積的動(dòng)態(tài)網(wǎng)絡(luò)嵌入根據(jù)中心節(jié)點(diǎn)和鄰居的動(dòng)態(tài)關(guān)系，更新中心節(jié)點(diǎn)的表示.例如：DyRep[20]模型將網(wǎng)絡(luò)劃分為2個(gè)動(dòng)態(tài)過程，即通信過程和動(dòng)力學(xué)過程.通信過程描述的是2個(gè)節(jié)點(diǎn)之間的交互情況，越頻繁表明關(guān)系越密切.動(dòng)力學(xué)過程描述了網(wǎng)絡(luò)的結(jié)構(gòu)進(jìn)化，記錄新加入的節(jié)點(diǎn)和邊.該方法使用了注意力機(jī)制，一方面根據(jù)通信頻率衡量鄰居節(jié)點(diǎn)的貢獻(xiàn)度，另一方面捕獲與中心節(jié)點(diǎn)可能交互的所有節(jié)點(diǎn).HTNE[21]模型將Hawkes過程理論引入到模型之中，考慮到鄰居節(jié)點(diǎn)對中心節(jié)點(diǎn)的影響會(huì)隨時(shí)間衰減，來動(dòng)態(tài)學(xué)習(xí)節(jié)點(diǎn)的表示.M2DNE[22]模型是對HTDE的一個(gè)改進(jìn)，提出微觀和宏觀2個(gè)層次的動(dòng)態(tài)性，在微觀層利用注意力機(jī)制來更新中心節(jié)點(diǎn)的歷史鄰居節(jié)點(diǎn)的權(quán)重，在宏觀層次檢測圖在下一時(shí)刻產(chǎn)生邊的準(zhǔn)確性，結(jié)合2層動(dòng)態(tài)性學(xué)習(xí)節(jié)點(diǎn)的表示.

然而，大部分的動(dòng)態(tài)網(wǎng)絡(luò)嵌入方法是無監(jiān)督地學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)的動(dòng)態(tài)變化，得到了與任務(wù)無關(guān)的嵌入表示，該結(jié)果對于特定任務(wù)類型(如節(jié)點(diǎn)分類、鏈接預(yù)測等)可能并非最優(yōu).而且很多方法僅考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的嵌入而忽視了節(jié)點(diǎn)自身屬性對嵌入結(jié)果的影響.此外，采用劃分時(shí)間快照的動(dòng)態(tài)網(wǎng)絡(luò)嵌入方法也不可避免地造成了信息的損失.

受到靜態(tài)VGAE[13]模型的啟發(fā)，本文提出一種條件變分時(shí)序圖自編碼器(conditional variational time-series graph auto-encoder， TS-CVGAE)模型，以及它的自編碼器版本(TS-GAE)和變分自編碼器版本(TS-VGAE).該類模型使用圖卷積聚合了結(jié)構(gòu)、屬性、時(shí)序等多種信息，在連續(xù)時(shí)間網(wǎng)絡(luò)中學(xué)習(xí)節(jié)點(diǎn)的動(dòng)態(tài)嵌入.

2 基本定義

在詳細(xì)描述本文算法之前，我們先給出動(dòng)態(tài)網(wǎng)絡(luò)、動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)、自編碼器、變分自編碼器以及條件變分自編碼器的基本定義.

注意，在本文模型中節(jié)點(diǎn)的屬性是固定不變的.但在有些應(yīng)用領(lǐng)域中，節(jié)點(diǎn)的屬性也可能隨時(shí)間發(fā)生變化.此外，本文動(dòng)態(tài)網(wǎng)絡(luò)的定義中將節(jié)點(diǎn)之間的交互視為邊，時(shí)間戳記錄邊出現(xiàn)的時(shí)刻.

圖1的有向圖表示一個(gè)動(dòng)態(tài)網(wǎng)絡(luò)的局部.2個(gè)節(jié)點(diǎn)之間箭頭上的數(shù)值表示它們產(chǎn)生關(guān)系的時(shí)刻.例如節(jié)點(diǎn)v1和節(jié)點(diǎn)v2在時(shí)刻1交互，節(jié)點(diǎn)v2和節(jié)點(diǎn)v6在時(shí)刻4和時(shí)刻6均進(jìn)行了交互.

Fig. 1 Local area of an entire dynamic network圖1 動(dòng)態(tài)網(wǎng)絡(luò)的局部圖

定義3.自編碼器(auto-encoder， AE)[23].一種人工神經(jīng)網(wǎng)絡(luò)，可以自監(jiān)督地學(xué)習(xí)輸入數(shù)據(jù)的有效表示，包括編碼器(encoder)和解碼器(decoder)2個(gè)部分.編碼器的任務(wù)是通過訓(xùn)練神經(jīng)網(wǎng)絡(luò)來學(xué)習(xí)輸入數(shù)據(jù)的低維表示.解碼器的任務(wù)是通過定義重構(gòu)損失從隱層低維表示中生成一個(gè)盡可能接近輸入數(shù)據(jù)的原始表示.

定義4.變分自編碼器(variational auto-encoder， VAE)[24].VAE是AE的變種，假設(shè)隱變量服從高斯分布，編碼器分別學(xué)習(xí)出高斯分布下的均值和方差，并使用這兩者生成隱層向量表示Z，并采樣得到隱變量，用于還原目標(biāo)數(shù)據(jù)X.

變分自編碼器不僅可以捕獲結(jié)構(gòu)和屬性非線性相似性，還可以學(xué)習(xí)到數(shù)據(jù)的分布，適用于稀疏網(wǎng)絡(luò)表示學(xué)習(xí)任務(wù).但是VAE是一種自監(jiān)督模型，沒有考慮數(shù)據(jù)的額外信息.

定義5.條件變分自編碼器(conditional varia-tional auto-encoder， CVAE)[25].CVAE在編碼器和解碼器中可以加入數(shù)據(jù)的標(biāo)簽或者其他先驗(yàn)知識(shí)作為條件，在條件概率c下對隱變量Z和數(shù)據(jù)X建模.

3 條件變分時(shí)序圖自編碼器

本文提出的條件變分時(shí)序圖自編碼器(TS-CVGAE)主要包含2個(gè)部分：1)采用時(shí)序圖卷積作為編碼器在同時(shí)聚合多類信息；2)采用內(nèi)積(inner product)作為解碼器來重建鄰接矩陣.一般來說，序列化模型(如LSTM)能夠較好地捕捉到圖數(shù)據(jù)的動(dòng)態(tài)變化，而圖自編碼器則可以較好地學(xué)習(xí)到網(wǎng)絡(luò)節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)特性.

3.1 時(shí)序圖卷積

動(dòng)態(tài)網(wǎng)絡(luò)中往往同時(shí)存在拓?fù)浣Y(jié)構(gòu)信息、節(jié)點(diǎn)屬性信息和邊的時(shí)序信息.本文提出了一種時(shí)序圖卷積(time-series graph convolution network，TGCN)模型，即在圖卷積的過程中同時(shí)聚合這3類信息，作為TS-CVGAE的編碼器.

傳統(tǒng)的靜態(tài)圖卷積操作[10]是為中心節(jié)點(diǎn)聚合其鄰域節(jié)點(diǎn)的屬性(例如簡單的求均值操作)，忽略了中心節(jié)點(diǎn)和鄰域節(jié)點(diǎn)之間交互的時(shí)間信息.本文在圖卷積操作之前，將中心節(jié)點(diǎn)的所有邊按其出現(xiàn)的先后順序(時(shí)間戳)對另一測的鄰居節(jié)點(diǎn)進(jìn)行排序.通過這一約束融入鄰域的時(shí)序信息，作為模型的輸入.從信息論的角度來看，網(wǎng)絡(luò)中具有時(shí)序的節(jié)點(diǎn)序列集合是不含時(shí)序的節(jié)點(diǎn)序列集合的子集，即時(shí)序信息的加入將減少了嵌入的不確定性.

具體來說，TGCN分為3個(gè)步驟：

1) 根據(jù)網(wǎng)絡(luò)中邊的信息對每個(gè)中心節(jié)點(diǎn)的鄰居節(jié)點(diǎn)采樣，得到固定數(shù)量k-1個(gè)的鄰居節(jié)點(diǎn)(加上中心節(jié)點(diǎn)本身一共k個(gè)采樣點(diǎn)).目前，算法僅采樣一階鄰居節(jié)點(diǎn)，未采樣高階鄰居節(jié)點(diǎn).如果采樣數(shù)量達(dá)不到k-1，則放回后繼續(xù)采樣.如圖2所示，中心節(jié)點(diǎn)v2的鄰居節(jié)點(diǎn)有v1,v3,v4,v5,v6，其中v6被采樣了2次.

2) 按邊的時(shí)間戳對所有采樣節(jié)點(diǎn)進(jìn)行排序，使得新的鄰居節(jié)點(diǎn)排在后面.例如：節(jié)點(diǎn)v2的時(shí)序鄰居節(jié)點(diǎn)序列如圖2右側(cè)所示.

Fig. 2 Time-series neighborhood node sequence for node v2圖2 為節(jié)點(diǎn)v2生成時(shí)序鄰居節(jié)點(diǎn)序列

3) 將基于時(shí)序的鄰居節(jié)點(diǎn)序列以及中心節(jié)點(diǎn)一同送入處理時(shí)序信息的運(yùn)算模型(如本文使用LSTM[26]模型)，以此聚合鄰域的信息，得到中心節(jié)點(diǎn)的嵌入表示.

3.2 整體框架設(shè)計(jì)

本文使用條件變分自編碼器框架，將拓?fù)浣Y(jié)構(gòu)作為自監(jiān)督信息，將提取的時(shí)序信息作為條件，指導(dǎo)時(shí)序圖卷積更好地實(shí)現(xiàn)編碼，最終學(xué)習(xí)到節(jié)點(diǎn)的動(dòng)態(tài)嵌入.圖3為TS-CVGAE的整體框架圖.

輸入層包含了動(dòng)態(tài)網(wǎng)絡(luò)G中為每個(gè)節(jié)點(diǎn)采樣得到鄰居節(jié)點(diǎn)序列的集合.

編碼器使用深度時(shí)序圖卷積進(jìn)行編碼.本文模型采用了2層時(shí)序圖卷積，形式化定義如下.

在條件變分自編碼器中，編碼器生成隱層變量的公式為

(1)

其中，q(zi|A,X,c)為后驗(yàn)概率，服從條件高斯分布(c為條件)，即：

注意，在變分自編碼器中，我們用的后驗(yàn)分布是標(biāo)準(zhǔn)高斯分布.

μ=TGCNμ(A,X,c),

(3)

logσ2=TGCNσ2(A,X,c).

(4)

最終，編碼器使用了2層時(shí)序圖卷積，即

其中，Z是2層時(shí)序圖卷積學(xué)得的嵌入矩陣，即Z=TGCN(A,X).

重構(gòu)概率表示為

(7)

由于條件變分自編碼器希望學(xué)到的隱層表示滿足條件高斯分布，即：

相當(dāng)于數(shù)據(jù)加上了高斯噪聲，使得模型更加魯棒.

本文模型的損失函數(shù)最終形式化為

(9)

其中，KL [q(·)‖p(·)]計(jì)算q(·)和p(·)之間的KL散度.

算法1.TS-CVGAE模型的偽代碼.

輸出：嵌入矩陣Z.

④ 從G中得到節(jié)點(diǎn)v的一階鄰居集Nt(v)；

⑥ if |Nt(v)|

/*如果數(shù)量達(dá)不到，則進(jìn)行有放回抽樣，使得|Nt(v)|=k-1*/

⑧ end if

end for

end for

根據(jù)式(9)計(jì)算損失函數(shù);

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

我們將本文提出的動(dòng)態(tài)網(wǎng)絡(luò)嵌入方法與傳統(tǒng)靜態(tài)網(wǎng)絡(luò)嵌入方法、采用自編碼器或者圖卷積的動(dòng)態(tài)網(wǎng)絡(luò)嵌入方法進(jìn)行了鏈接預(yù)測實(shí)驗(yàn)，間接地比較各方法的嵌入效果.

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

實(shí)驗(yàn)采用了4個(gè)帶有邊的時(shí)間戳的現(xiàn)實(shí)網(wǎng)絡(luò)數(shù)據(jù)集，分別為：Bitcoin-OTC(1)http://snap.stanford.edu/data/soc-sign-bitcoin-otc.html,Bitcoin-Alpha(2)http://snap.stanford.edu/data/soc-sign-bitcoin-alpha.html,DBLP(3)http://konect.uni-koblenz.de/networks/dblp_coauthor和Facebook(4)http://konect.uni-koblenz.de/networks/facebook-wosn-wall.

Bitcoin-OTC和Bitcoin-Alpha數(shù)據(jù)集分別來自不同的比特幣交易平臺(tái)的用戶網(wǎng)絡(luò).由于在各類交易平臺(tái)上比特幣用戶是匿名的，為了降低交易風(fēng)險(xiǎn)和避免欺詐，網(wǎng)絡(luò)中的用戶之間需進(jìn)行信用評(píng)分(范圍從-10～10).這2個(gè)數(shù)據(jù)集的節(jié)點(diǎn)為用戶、邊為用戶之間的評(píng)分關(guān)系、評(píng)分時(shí)間跨度約為5年.其中，Bitcoin-OTC網(wǎng)絡(luò)含有5 881個(gè)用戶節(jié)點(diǎn)，共產(chǎn)生了27 373個(gè)評(píng)分關(guān)系；Bitcoin-Alpha網(wǎng)絡(luò)含有3 783個(gè)用戶節(jié)點(diǎn)，共產(chǎn)生了17 907個(gè)評(píng)分關(guān)系.

DBLP數(shù)據(jù)集為計(jì)算機(jī)領(lǐng)域的論文合作者網(wǎng)絡(luò).網(wǎng)絡(luò)中的節(jié)點(diǎn)為作者，邊為作者節(jié)點(diǎn)之間的合作發(fā)表關(guān)系.實(shí)驗(yàn)從2001—2016年之間的數(shù)據(jù)中采樣了5 000個(gè)作者節(jié)點(diǎn)，共產(chǎn)生了11 762個(gè)合作關(guān)系.

Facebook數(shù)據(jù)集包含了在線社交網(wǎng)絡(luò)中用戶的互動(dòng)行為.網(wǎng)絡(luò)中的節(jié)點(diǎn)為用戶，邊為用戶之間的留言關(guān)系.實(shí)驗(yàn)從2005—2009年之間的數(shù)據(jù)中采樣了5 000個(gè)用戶節(jié)點(diǎn)，共產(chǎn)生25 380個(gè)留言關(guān)系.

由于有些數(shù)據(jù)集的節(jié)點(diǎn)存在原始屬性而有些并不存在，為了公平比較，我們均使用單位矩陣I代替節(jié)點(diǎn)的屬性矩陣X.

4.2 比較方法

比較方法包括經(jīng)典的靜態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)方法(DeepWalk和node2vec)、采用自編碼器或者圖卷積的靜、動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)方法(SDNE,GAE,VGAE,CTDNE,HTNE和M2DNE)以及本文方法的變體(TS-GAE和TS-VGAE).

1) DeepWalk[6]是最經(jīng)典的靜態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)方法，先根據(jù)隨機(jī)游走產(chǎn)生若干節(jié)點(diǎn)序列，然后將序列送入到Skip-Gram模型學(xué)習(xí)節(jié)點(diǎn)的表示.

2) node2vec[7]是對DeepWalk的改進(jìn)，結(jié)合了深度優(yōu)先(DFS)和廣度優(yōu)先(BFS)2種搜索策略.基于DFS游走到達(dá)節(jié)點(diǎn)的概率和基于BFS游走到達(dá)節(jié)點(diǎn)的概率不同.

3) SDNE[17]使用深度自編碼器對節(jié)點(diǎn)間的一階和二階相似性進(jìn)行建模，采用重構(gòu)損失捕獲二階相似性，采用拉普拉斯特征圖計(jì)算直接相連節(jié)點(diǎn)表示的差值來捕獲一階相似性.

4) CTDNE[16]是動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)方法，按時(shí)間序列進(jìn)行隨機(jī)游走，即游走序列中下一條邊的時(shí)間大于當(dāng)前邊的時(shí)間，然后將得到的序列送入Skip-Gram模型學(xué)習(xí)節(jié)點(diǎn)的表示.

5) HTNE[21]方法按照時(shí)間順序選取一定數(shù)量的歷史鄰居信息，通過Hawkes過程理論計(jì)算不同時(shí)刻的歷史鄰居節(jié)點(diǎn)對當(dāng)前節(jié)點(diǎn)的影響力，學(xué)習(xí)節(jié)點(diǎn)的低維表示.

6) M2DNE[22]方法是對HTNE的改進(jìn)，通過引入注意力機(jī)制來計(jì)算不同的歷史鄰居對中心節(jié)點(diǎn)的影響，并結(jié)合下一時(shí)刻預(yù)測邊的準(zhǔn)確性，共同學(xué)習(xí)節(jié)點(diǎn)的低維表示.

7) GAE[13]是靜態(tài)圖自編碼器，使用圖卷積做編碼器，可以同時(shí)抽取網(wǎng)絡(luò)中拓?fù)浣Y(jié)構(gòu)信息和節(jié)點(diǎn)屬性信息，在解碼器中使用內(nèi)積運(yùn)算來預(yù)測網(wǎng)絡(luò)的關(guān)系.

8) VGAE[13]是GAE的變分自編碼器版本，兩者的不同在于GAE使用的是基礎(chǔ)自編碼器框架，而VGAE使用的是變分自編碼器框架.

9) TS-GAE是本文TS-CVGAE方法的自編碼器版本，使用了2層時(shí)序圖卷積作為編碼器，但未使用時(shí)序監(jiān)督信息.

10) TS-VGAE是本文TS-CVGAE方法的變分自編碼器版本，同樣使用了2層時(shí)序圖卷積作為編碼器，未使用時(shí)序監(jiān)督信息.

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

對于TS-CVGAE,TS-VGAE,TS-GAE,VGAE和GAE方法，實(shí)驗(yàn)使用Adam[27]優(yōu)化方法進(jìn)行200次迭代訓(xùn)練，學(xué)習(xí)率為0.01.這5種方法均使用2層圖卷積，每層的嵌入維度分別為32和16(即VGAE和GAE所在論文[13]中的設(shè)置).DeepWalk,node2vec和CTDNE方法使用各自論文中提供的標(biāo)準(zhǔn)設(shè)置，即每個(gè)節(jié)點(diǎn)進(jìn)行10次長度為80的隨機(jī)游走，窗口大小為10.SDNE方法也使用Adam優(yōu)化方法進(jìn)行200次迭代訓(xùn)練，學(xué)習(xí)率為0.01，2層的嵌入維度分別為1 000和16.HTNE和M2DNE方法的參數(shù)使用原文實(shí)驗(yàn)的設(shè)置，即負(fù)采樣數(shù)量為5，歷史鄰居數(shù)量為5，M2DNE方法的平衡因子為0.4，進(jìn)行學(xué)習(xí)率為0.01的200次迭代訓(xùn)練.為了公平比較，所有方法的最終輸出嵌入維度均設(shè)置為16.

本文在4個(gè)數(shù)據(jù)集上分別進(jìn)行了鏈接預(yù)測任務(wù)來評(píng)估各個(gè)模型的性能.比特幣網(wǎng)絡(luò)的預(yù)測目標(biāo)是2個(gè)用戶是否會(huì)產(chǎn)生信用評(píng)分，合作者網(wǎng)絡(luò)的預(yù)測目標(biāo)是2個(gè)作者是否會(huì)合作，社交網(wǎng)絡(luò)的預(yù)測目標(biāo)是2個(gè)用戶是否會(huì)留言互動(dòng).實(shí)驗(yàn)隨機(jī)選擇50%的數(shù)據(jù)集作為訓(xùn)練數(shù)據(jù)集，20%作為驗(yàn)證數(shù)據(jù)集，剩余做為測試數(shù)據(jù)集.

4.4 鏈接預(yù)測結(jié)果比較

當(dāng)模型學(xué)到節(jié)點(diǎn)的嵌入表示后，我們計(jì)算每個(gè)節(jié)點(diǎn)對的內(nèi)積并排序作為最后的預(yù)測結(jié)果.我們采用AUC(area under ROC)[28]和AP(average precision)[29]作為方法的評(píng)價(jià)指標(biāo).

表1和表2分別匯總了所有方法在4個(gè)數(shù)據(jù)集上的鏈接預(yù)測AUC值和AP值.其中，黑體數(shù)值表示對應(yīng)方法在當(dāng)前數(shù)據(jù)集下表現(xiàn)最優(yōu)，加下劃線的數(shù)值表示對應(yīng)方法在當(dāng)前數(shù)據(jù)集下表現(xiàn)次優(yōu).

Table 1 Link Prediction in AUC indicator表1 鏈接預(yù)測的AUC指標(biāo)值

Table 2 Link Prediction in AP indicator表2 鏈接預(yù)測的AP指標(biāo)值

實(shí)驗(yàn)結(jié)果表明:2種經(jīng)典的靜態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)方法DeepWalk和node2vec的性能是最低的.SDNE要優(yōu)于前兩者，驗(yàn)證了圖自編碼器的有效性，不過該方法將整個(gè)鄰接矩陣作為自編碼器的輸入，未能學(xué)到時(shí)序信息，因此總體性能要低于動(dòng)態(tài)圖表示學(xué)習(xí)方法.CTDNE在比特幣網(wǎng)絡(luò)和社交網(wǎng)絡(luò)中的表現(xiàn)較好，其AP值甚至高于本文的方法，但在DBLP合作者網(wǎng)絡(luò)中的表現(xiàn)較差，說明該方法對網(wǎng)絡(luò)的類型較為敏感.基于節(jié)點(diǎn)影響力的HTNE與M2DNE在DBLP數(shù)據(jù)集中表現(xiàn)較好，可能的解釋是，如果2個(gè)作者的共同合作者在某一個(gè)領(lǐng)域更具有影響力，那么2個(gè)作者合作的機(jī)會(huì)明顯增加.GAE和VGAE方法的鏈接預(yù)測結(jié)果要低于對應(yīng)的TS-GAE和TS-VGAE.例如在Bitcoin-Alpha數(shù)據(jù)集上，TS-VGAE的AUC值要比VGAE高出近4%.這驗(yàn)證了本章提出的時(shí)序圖卷積操作的有效性.在DBLP數(shù)據(jù)集上，TS-VGAE的AUC要比VGAE高出12.6%.這說明對于稀疏的網(wǎng)絡(luò)，基于時(shí)序的聚合對于節(jié)點(diǎn)嵌入的影響更大.VGAE和GAE方法的鏈接預(yù)測性能相當(dāng)，TS-VGAE和TS-GAE也沒有顯著差異.例如對于合作者網(wǎng)絡(luò)DBLP和社交網(wǎng)絡(luò)Facebook來說，TS-GAE的AUC值稍高于TS-VGAE，而在信用評(píng)價(jià)網(wǎng)絡(luò)Bitcoin-OTC和Bitcoin-Alpha上則是TS-VGAE的性能略好.這說明變分自編碼器未顯示出絕對的優(yōu)勢.TS-CVGAE方法在大部分的數(shù)據(jù)集中獲得了最優(yōu)的AUC值，除了在DBLP數(shù)據(jù)集上略低于TS-GAE方法，說明在學(xué)習(xí)中加入鄰域的時(shí)序監(jiān)督信息能夠改進(jìn)節(jié)點(diǎn)的嵌入結(jié)果.在AP指標(biāo)上的比較結(jié)果(如表2所示)也得到了類似的結(jié)論.

總體來說，本文方法在4個(gè)數(shù)據(jù)集中均取得較優(yōu)的預(yù)測性能，說明其受網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響更小，能夠適應(yīng)不同類型的網(wǎng)絡(luò).

4.5 超參數(shù)k分析

本文還分析了TS-CVGAE模型中時(shí)序圖卷積的輸入節(jié)點(diǎn)序列數(shù)k對最終鏈接預(yù)測結(jié)果的影響.我們分別測試了當(dāng)k=3,5,7,9時(shí)4個(gè)數(shù)據(jù)集上鏈接預(yù)測結(jié)果的AUC值,如圖4所示:

Fig. 4 AUC values of TS-CVGAE under different parameters k圖4 不同參數(shù)k下TS-CVGAE的鏈接預(yù)測AUC值

實(shí)驗(yàn)結(jié)果表明:盡管不同的網(wǎng)絡(luò)中節(jié)點(diǎn)的稀疏程度不同(Bitcoin-OTC的平均度為10.1,Bitcoin-Alpha的平均度為7.2,DBLP的平均度為4.7,Facebook的平均度為10.2)，但大多是在k=7的時(shí)候獲得較好的結(jié)果(除了Facebook數(shù)據(jù)集中，k=9比k=7的結(jié)果略高).這說明，本文模型在不同數(shù)據(jù)集下的表現(xiàn)是相對穩(wěn)定的.k值過小對于大部分節(jié)點(diǎn)無法充分地聚合鄰居信息，而k值過大則可能過采樣了鄰居節(jié)點(diǎn)而造成多余的噪聲.此外，從時(shí)序的角度來看，當(dāng)序列跨度過長時(shí)，時(shí)間過于久遠(yuǎn)的鄰居節(jié)點(diǎn)對信息聚合的作用過小，也會(huì)導(dǎo)致性能的下降.

4.6 嵌入維度d分析

由于本文TS-CVGAE模型采用了2層時(shí)序圖卷積，我們令每層的嵌入維度分別為d0和d1.

我們首先觀察d1=16時(shí)，d0的變化對TS-CVGAE的鏈接預(yù)測AUC值的影響.

如圖5所示，當(dāng)固定d1=16時(shí)，d0取值為128或者64時(shí)TS-CVGAE模型的性能更優(yōu).這說明加入時(shí)序信息后，模型的復(fù)雜度應(yīng)相應(yīng)提高，以充分學(xué)習(xí)網(wǎng)絡(luò)的動(dòng)態(tài)嵌入.

Fig. 5 Impact of embedding dimension d0 on AUC values圖5 嵌入維度d0對于AUC結(jié)果的影響

隨后，我們固定d0=128，觀察d1的變化對TS-CVGAE的鏈接預(yù)測AUC值的影響.如圖6所示，當(dāng)d1=32時(shí)TS-CVGAE模型的性能更優(yōu).

Fig. 6 Impact of embedding dimension d1 on AUC values圖6 嵌入維度d1對于AUC結(jié)果的影響

不過，為了和GAE和VGAE方法保持一致，本文在進(jìn)行比較實(shí)驗(yàn)時(shí)還是選用了d0=32,d1=16的設(shè)置.

4.7 運(yùn)行時(shí)間比較

本文還比較了各個(gè)方法在4個(gè)數(shù)據(jù)集上學(xué)得網(wǎng)絡(luò)嵌入結(jié)果時(shí)的運(yùn)行時(shí)間.由于DeepWalk,node2vec和CTDNE均是基于隨機(jī)游走策略生成序列輸入Skip-Gram模型進(jìn)行訓(xùn)練，在運(yùn)行時(shí)間上相差不多.SDNE是把整個(gè)圖輸入深度自編碼器訓(xùn)練，運(yùn)行時(shí)間與節(jié)點(diǎn)的個(gè)數(shù)、自編碼器的層數(shù)有直接的關(guān)系.HTNE與M2DNE是基于時(shí)間序列對歷史鄰居進(jìn)行采樣，所以鄰居節(jié)點(diǎn)的數(shù)量、負(fù)采樣的數(shù)量、時(shí)間戳的數(shù)量對模型的運(yùn)行時(shí)間均有影響.GAE和VGAE采用圖卷積作為編碼器，運(yùn)行時(shí)間低于SDNE，但要高于DeepWalk,node2vec及CTDNE.本文提出的3個(gè)模型均采用了時(shí)序圖卷積，與簡單圖卷積比需要更多的訓(xùn)練參數(shù)來學(xué)習(xí)時(shí)序信息，因此運(yùn)行時(shí)間略高于GAE和VGAE.總體來說，本文方法與SDNE方法的運(yùn)行時(shí)間相當(dāng)，但遠(yuǎn)低于HTNE和M2DNE的運(yùn)行時(shí)間.

Fig. 7 Running time comparison of all methods in 4 datasets圖7 4個(gè)數(shù)據(jù)集上所有方法的運(yùn)行時(shí)間比較

5 總 結(jié)

本文提出了一種基于時(shí)序圖卷積和條件變分自編碼器的動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)方法TS-CVGAE.該方法改進(jìn)了經(jīng)典的圖卷積模型使其能夠提取鄰域的時(shí)序信息，并將其作為編碼器加入條件變分自編碼器的框架中，實(shí)現(xiàn)了對動(dòng)態(tài)網(wǎng)絡(luò)的嵌入.在4個(gè)現(xiàn)實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的對比實(shí)驗(yàn)結(jié)果表明:與現(xiàn)有的經(jīng)典圖嵌入方法以及基于自編碼器的動(dòng)態(tài)圖嵌入方法相比，TS-CVGAE均取得了最優(yōu)的鏈接預(yù)測結(jié)果.