利用變分自編碼器進(jìn)行網(wǎng)絡(luò)表示學(xué)習(xí)*

張 蕾，錢 峰，趙 姝，陳 潔，張燕平

1.安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥230601

2.銅陵學(xué)院 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，安徽 銅陵244061

+通訊作者E-mail:zhaoshuzs2002@hotmail.com

1 引言

網(wǎng)絡(luò)表示學(xué)習(xí)（network representation learning，NRL）[1]是機(jī)器學(xué)習(xí)領(lǐng)域中一個(gè)重要部分，主要任務(wù)是學(xué)習(xí)能夠保持原始網(wǎng)絡(luò)結(jié)構(gòu)的低維節(jié)點(diǎn)表示，使得較大相似度的節(jié)點(diǎn)具有類似的向量表示。NRL不僅可解決與網(wǎng)絡(luò)數(shù)據(jù)相關(guān)的高維和稀疏性問題，還可通過應(yīng)用基于向量的機(jī)器學(xué)習(xí)方法，在新的向量空間中有效地解決下游應(yīng)用任務(wù)，例如節(jié)點(diǎn)分類[2]、鏈接預(yù)測(cè)[3]、社團(tuán)挖掘[4]、信息推薦[5]。

目前，主流的NRL 方法有隨機(jī)游走方法（例如DeepWalk[6]、UPP-SNE（user profile preserving social network embedding）[7]）、矩陣分解方法（例如HOPE（high order proximity preserved embedding）[8]、DNE（discrete network embedding）[9]）、深度學(xué)習(xí)方法等。深度學(xué)習(xí)方法包括基于自編碼器（auto encoder，AE）[10]（例如DNGR[11]（deep neural graph representations）、SDNE（structural deep network embedding）[12]）和圖卷積網(wǎng)絡(luò)（graph convolutional network，GCN）[13]（例如GraphSage[14]）的方法。這些方法根據(jù)拓?fù)浣Y(jié)構(gòu)或結(jié)合節(jié)點(diǎn)屬性，從不同角度出發(fā)，最終得到網(wǎng)絡(luò)節(jié)點(diǎn)在低維、密集空間中的向量表示。

經(jīng)典的NRL 方法（例如Node2Vec[15]、LINE（large scale information network embedding）[16]、GraRep[17]）僅依賴拓?fù)浣Y(jié)構(gòu)捕獲節(jié)點(diǎn)間的一階、二階甚至高階相似性，進(jìn)而學(xué)習(xí)到網(wǎng)絡(luò)的節(jié)點(diǎn)表示。然而，在許多實(shí)際場(chǎng)景中，純粹依賴拓?fù)浣Y(jié)構(gòu)學(xué)習(xí)期望的節(jié)點(diǎn)表示是不充分的。例如，在社交網(wǎng)絡(luò)中，用戶的興趣可能非常相似，但是他們之間沒有交互并且沒有共同的朋友，因此他們的興趣相似性無法被基于結(jié)構(gòu)的NRL 方法有效地捕獲。在這種情況下，應(yīng)該利用其他外部信息作為補(bǔ)充，幫助學(xué)習(xí)到更好的節(jié)點(diǎn)表示。通常，真實(shí)世界網(wǎng)絡(luò)中的節(jié)點(diǎn)擁有與之相關(guān)聯(lián)的屬性信息。例如，社交網(wǎng)絡(luò)中每個(gè)用戶的配置文件和引文網(wǎng)絡(luò)中每篇論文的元數(shù)據(jù)。節(jié)點(diǎn)屬性不僅可衡量屬性間的相似性，而且還影響節(jié)點(diǎn)間的關(guān)系的形成。因此節(jié)點(diǎn)屬性對(duì)于衡量節(jié)點(diǎn)間的相似性很重要，將它們結(jié)合到表示學(xué)習(xí)過程中可望獲得更好的節(jié)點(diǎn)特征表示。

通過結(jié)合屬性NRL 方法（例如TADW（text associated deep walk）[18]、UPP-SNE[7]、GraphSage[14]）的研究表明，融合結(jié)構(gòu)和節(jié)點(diǎn)屬性學(xué)習(xí)到的節(jié)點(diǎn)表示有助于增強(qiáng)許多下游應(yīng)用任務(wù)的性能。TADW首先提出通過矩陣分解將節(jié)點(diǎn)的文本特征結(jié)合到NRL 中，顯示出優(yōu)于DeepWalk 的性能。還有一些半監(jiān)督的NRL[19-20]方法，不僅結(jié)合節(jié)點(diǎn)屬性，還考慮到節(jié)點(diǎn)標(biāo)簽的可用性。本文工作重點(diǎn)是無監(jiān)督的NRL 方法，因此不使用節(jié)點(diǎn)標(biāo)簽信息。

盡管現(xiàn)有結(jié)合結(jié)構(gòu)和節(jié)點(diǎn)屬性的NRL方法在不同應(yīng)用場(chǎng)景中充分展示方法的有效性，但依然面臨以下兩個(gè)主要挑戰(zhàn)。

（1）異構(gòu)性：網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和屬性信息是兩個(gè)異構(gòu)的信息源，位于兩個(gè)不同的特征空間，存在差異是不可避免的。而且兩者之間并不總是表現(xiàn)出強(qiáng)烈的線性相關(guān)性。這種差異為表示學(xué)習(xí)增加額外的困難。如何選取適當(dāng)?shù)姆绞綄?duì)拓?fù)浣Y(jié)構(gòu)和屬性信息進(jìn)行融合，使得學(xué)習(xí)到的節(jié)點(diǎn)表示對(duì)下游應(yīng)用的性能是增強(qiáng)而不是惡化具有挑戰(zhàn)性。

（2）非線性：拓?fù)浣Y(jié)構(gòu)和屬性信息都是高度非線性的，如何捕獲這種高度非線性的特性是困難的。大多數(shù)現(xiàn)有的方法采用淺模型，無法有效捕獲高度非線性的特性。雖然使用深度學(xué)習(xí)模型能夠捕獲數(shù)據(jù)中的非線性結(jié)構(gòu)，但輸出的表示向量分布是未知和模糊的。因此，有效地捕獲網(wǎng)絡(luò)結(jié)構(gòu)和屬性的高度非線性結(jié)構(gòu)仍具有挑戰(zhàn)性。

針對(duì)上述問題，本文提出基于變分自編碼器[21]的無監(jiān)督NRL（variational auto-encoder based network representation learning，VANRL）方法，能夠在網(wǎng)絡(luò)表示學(xué)習(xí)中融入屬性特征獲得更好的網(wǎng)絡(luò)表示。具體來說，使用變分自編碼器進(jìn)行特征提取，捕獲網(wǎng)絡(luò)數(shù)據(jù)中潛在的高非線性特征。此外，為從結(jié)構(gòu)和屬性信息中學(xué)習(xí)一致和互補(bǔ)的表示，提出一種結(jié)合這兩種信息的靈活策略。

本文的主要貢獻(xiàn)有如下三點(diǎn)。

（1）提出一種結(jié)構(gòu)和屬性的組合方法，面對(duì)不同的應(yīng)用場(chǎng)景，可靈活調(diào)整結(jié)構(gòu)和屬性的結(jié)合方式。

（2）通過變分自編碼器獲取節(jié)點(diǎn)的低維表示，不僅能夠捕獲網(wǎng)絡(luò)數(shù)據(jù)中的高度非線性特征，還能學(xué)習(xí)到網(wǎng)絡(luò)數(shù)據(jù)的分布。

（3）公開數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，VANRL方法能夠得到更加穩(wěn)健的節(jié)點(diǎn)表示。

本文組織結(jié)構(gòu)如下：第2 章介紹相關(guān)工作；第3章介紹網(wǎng)絡(luò)節(jié)點(diǎn)高維向量表示的獲取方法和結(jié)構(gòu)和屬性信息的融合方法；第4章介紹變分自編碼器的相關(guān)知識(shí)；第5章介紹本文方法VANRL的主要流程；第6章在多個(gè)公開數(shù)據(jù)集上從不同方面對(duì)VANRL的有效性進(jìn)行驗(yàn)證；第7章總結(jié)全文。

2 相關(guān)工作

本章針對(duì)基于結(jié)構(gòu)、基于結(jié)構(gòu)和屬性融合，分別介紹幾種有代表性的NRL方法。

2.1 基于結(jié)構(gòu)的NRL方法

基于結(jié)構(gòu)的NRL方法指僅依賴拓?fù)浣Y(jié)構(gòu)學(xué)習(xí)節(jié)點(diǎn)表示。Perozzi 等提出DeepWalk[6]，由此開啟NRL的研究熱潮。DeepWalk首先通過隨機(jī)游走將網(wǎng)絡(luò)結(jié)構(gòu)編碼為一組節(jié)點(diǎn)序列，然后使用SkipGram[22]模型基于節(jié)點(diǎn)上下文相似性學(xué)習(xí)結(jié)構(gòu)的節(jié)點(diǎn)表示。Grover等提出Node2Vec[15]，通過引入兩個(gè)超參數(shù)平衡廣度優(yōu)先采樣和深度優(yōu)先采樣生成節(jié)點(diǎn)序列，然后通過最大化保留節(jié)點(diǎn)網(wǎng)絡(luò)鄰域的可能性學(xué)習(xí)節(jié)點(diǎn)表示。Tang等提出LINE[16]，優(yōu)化大規(guī)模網(wǎng)絡(luò)中邊的聯(lián)合和條件概率學(xué)習(xí)節(jié)點(diǎn)表示。Cao等提出GraRep[17]，進(jìn)一步擴(kuò)展LINE，通過對(duì)節(jié)點(diǎn)及其k步鄰居之間的關(guān)系進(jìn)行建?？紤]高階相似性。Wang 等提出M-NMF（modularized nonnegative matrix factorization）[23]，通過社區(qū)內(nèi)相似來補(bǔ)充局部結(jié)構(gòu)相似性，學(xué)習(xí)具有社區(qū)感知的節(jié)點(diǎn)表示。Cao等提出DNGR[11]，首先通過Random Surfing 方法獲得高維結(jié)構(gòu)保持的節(jié)點(diǎn)表示，然后利用棧式去噪自編碼器（stacked denoising auto-encoder，SDAE）[24]學(xué)習(xí)低維的節(jié)點(diǎn)表示。Wang等提出SDNE[12]，采用深度自編碼器學(xué)習(xí)高度非線性節(jié)點(diǎn)表示，通過重構(gòu)節(jié)點(diǎn)鄰接矩陣表示保持二階相似性并懲罰連通節(jié)點(diǎn)的表示差異以保持一階相似性。

利用拓?fù)浣Y(jié)構(gòu)學(xué)習(xí)節(jié)點(diǎn)表示，由于忽略節(jié)點(diǎn)屬性信息，在鏈接稀疏的情況下，這些方法不能產(chǎn)生令人滿意的結(jié)果。

2.2 基于結(jié)構(gòu)和屬性融合的NRL方法

基于結(jié)構(gòu)和屬性融合的NRL方法指在網(wǎng)絡(luò)表示學(xué)習(xí)中融入節(jié)點(diǎn)屬性信息以獲得更好的網(wǎng)絡(luò)節(jié)點(diǎn)表示。Yang 等提出TADW[18]，第一次嘗試將節(jié)點(diǎn)屬性信息納入NRL。TADW證明DeepWalk與矩陣分解公式之間的等價(jià)性，然后將節(jié)點(diǎn)文本特征編碼到矩陣分解過程中，得到融入文本信息的網(wǎng)絡(luò)節(jié)點(diǎn)表示。Zhang等提出HSCA[25]（homophily，structure，and content augmented network representation learning）強(qiáng)制執(zhí)行具有一階相似性的TADW 獲得更多信息的網(wǎng)絡(luò)節(jié)點(diǎn)表示。Zhang等提出UPP-SNE[7]，在DeepWalk框架下生成隨機(jī)游走捕獲節(jié)點(diǎn)的相似性，并通過非線性映射將用戶配置文件嵌入到潛在空間學(xué)習(xí)節(jié)點(diǎn)表示。Tu等提出CANE（context aware network embedding）［26]，通過在連通節(jié)點(diǎn)的屬性上應(yīng)用相互注意機(jī)制學(xué)習(xí)上下文節(jié)點(diǎn)表示。Yang 等提出MVC-DNE（multi-view correlation learning based deep network embedding）[27]，應(yīng)用深 度多視圖學(xué)習(xí)技術(shù)將屬性信息融合到節(jié)點(diǎn)表示中。Hamilton 等提出GraphSage[14]，首先將節(jié)點(diǎn)內(nèi)容特征作為節(jié)點(diǎn)表示，然后通過聚合相鄰節(jié)點(diǎn)的表示迭代地更新節(jié)點(diǎn)表示。Huang 等提出AANE（accelerated attributed network embedding）[28]，采用對(duì)稱矩陣分解獲得屬性親和性的節(jié)點(diǎn)表示，同時(shí)懲罰連接節(jié)點(diǎn)間的表示差異。Zhang等提出SINE（scalable incomplete network embedding）[29]，通過使用節(jié)點(diǎn)表示同時(shí)預(yù)測(cè)上下文節(jié)點(diǎn)和節(jié)點(diǎn)內(nèi)容屬性來學(xué)習(xí)大規(guī)模不完全屬性網(wǎng)絡(luò)的節(jié)點(diǎn)表示。

除了上述無監(jiān)督NRL方法外，還有一些關(guān)于監(jiān)督NRL 的研究工作，如LANE（label informed attributed network embedding）[19]、TriDNR（tri-party deep network representation）[20]。監(jiān)督NRL方法將標(biāo)簽信息編碼到表示學(xué)習(xí)過程中。不僅很好地尊重網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)屬性，而且還具有判別力，可以實(shí)現(xiàn)更準(zhǔn)確的節(jié)點(diǎn)分類。本文專注于無監(jiān)督的NRL，僅利用拓?fù)浣Y(jié)構(gòu)或節(jié)點(diǎn)屬性學(xué)習(xí)節(jié)點(diǎn)表示。

3 問題定義及預(yù)處理

本文提出基于變分自編碼器的NRL方法VANRL，主要任務(wù)是使用正逐點(diǎn)互信息（positive pointwise mutual information，PPMI）[30-31]矩陣作為輸入，通過深度神經(jīng)網(wǎng)絡(luò)架構(gòu)將網(wǎng)絡(luò)節(jié)點(diǎn)表征到低維向量空間。本章首先介紹NRL的基本定義，然后介紹PPMI矩陣的計(jì)算過程。

3.1 問題定義

定義1（網(wǎng)絡(luò)）給定一個(gè)網(wǎng)絡(luò)G=(V,E,W)，其中V是節(jié)點(diǎn)的集合，E?V×V是邊的集合。節(jié)點(diǎn)之間的關(guān)系用鄰接矩陣表示，A∈Rn×n，假設(shè)研究的對(duì)象是無權(quán)圖，那么當(dāng)節(jié)點(diǎn)vi與節(jié)點(diǎn)vj之間存在邊時(shí)，Aij=1，否則Aij=0。矩陣W∈Rm×n存儲(chǔ)節(jié)點(diǎn)屬性信息，節(jié)點(diǎn)vi∈V對(duì)應(yīng)的屬性向量表示為wi∈Rm，其中m是屬性維度，n=|V|是節(jié)點(diǎn)數(shù)。NRL 的目標(biāo)是基于拓?fù)浣Y(jié)構(gòu)或結(jié)合節(jié)點(diǎn)屬性，學(xué)習(xí)一個(gè)映射函數(shù)Φ(·)，將網(wǎng)絡(luò)節(jié)點(diǎn)映射到一個(gè)低維的潛在空間，最終獲得節(jié)點(diǎn)Φ(vi)∈Rd在潛在空間的向量表示。

學(xué)習(xí)的節(jié)點(diǎn)表示Φ(vi)應(yīng)具有以下特性：（1）低維，Φ(vi)的維度d應(yīng)遠(yuǎn)小于原始鄰接矩陣的維度n；（2）結(jié)構(gòu)保持，結(jié)構(gòu)相似的節(jié)點(diǎn)在潛在空間中會(huì)非常靠近；（3）性能保持，融合節(jié)點(diǎn)屬性的網(wǎng)絡(luò)節(jié)點(diǎn)表示應(yīng)增強(qiáng)后續(xù)的網(wǎng)絡(luò)應(yīng)用任務(wù)性能，而不是惡化。

3.2 PPMI矩陣

PPMI矩陣是一個(gè)反映節(jié)點(diǎn)成對(duì)相互作用的密集矩陣。在自然語言處理中，用來衡量提取詞匯的相關(guān)程度，在本文中，PPMI矩陣的行被視為節(jié)點(diǎn)的高維向量表示。構(gòu)造方法如下：

其中，P是一個(gè)共現(xiàn)概率矩陣，c表示對(duì)應(yīng)單詞w的上下文。

針對(duì)PPMI 矩陣，沿用DNGR 中利用Random Surfing模型[11]獲得共現(xiàn)概率矩陣P。相對(duì)隨機(jī)游走方法，Random Surfing模型具有如下優(yōu)勢(shì)：

（1）游走的長(zhǎng)度的限制。隨機(jī)游走方法在計(jì)算共現(xiàn)矩陣時(shí)，會(huì)丟失范圍超出長(zhǎng)度的節(jié)點(diǎn)。

（2）數(shù)據(jù)集規(guī)模的限制。針對(duì)不同的數(shù)據(jù)集，隨機(jī)游走方法必須正確設(shè)置兩個(gè)超參數(shù)，游走長(zhǎng)度和游走次數(shù)。

Random Surfing 模型使用一個(gè)轉(zhuǎn)移矩陣M通過k步迭代計(jì)算共現(xiàn)矩陣P，迭代公式如下：

其中，P0是節(jié)點(diǎn)vi的初始獨(dú)熱向量。通過一個(gè)n×n的單位矩陣獲得。節(jié)點(diǎn)每次跳轉(zhuǎn)到下一個(gè)節(jié)點(diǎn)的概率為α，重啟概率是1-α。

3.3 結(jié)構(gòu)-屬性聯(lián)合轉(zhuǎn)移矩陣

本節(jié)介紹轉(zhuǎn)移矩陣M的計(jì)算過程。本文使用線性的方式將節(jié)點(diǎn)的結(jié)構(gòu)信息和屬性信息基于轉(zhuǎn)移矩陣融合到一起，這種方法簡(jiǎn)單有效。

定義2（基于拓?fù)涞墓?jié)點(diǎn)轉(zhuǎn)移矩陣）給定一個(gè)網(wǎng)絡(luò)G的鄰接矩陣A∈Rn×n，基于拓?fù)涞墓?jié)點(diǎn)轉(zhuǎn)移矩陣MA∈Rn×n構(gòu)造方法如下：

定義3（基于屬性的節(jié)點(diǎn)轉(zhuǎn)移矩陣）給定一個(gè)網(wǎng)絡(luò)G的屬性矩陣W∈Rm×n，通過求解余弦相似度將W轉(zhuǎn)換成屬性相似度矩陣S∈Rn×n，構(gòu)造方法如下：

通過S計(jì)算基于屬性的節(jié)點(diǎn)轉(zhuǎn)移矩陣Mw∈Rn×n，對(duì)于矩陣S，為提升后期矩陣運(yùn)算性能，只保留行向量中的前l(fā)個(gè)值，其余都置為0，構(gòu)造方法如下：

定義4（結(jié)構(gòu)-屬性聯(lián)合轉(zhuǎn)移矩陣）給定一個(gè)網(wǎng)絡(luò)G，結(jié)構(gòu)-屬性聯(lián)合轉(zhuǎn)移矩陣M∈Rn×n的構(gòu)造方法如下：

其中，參數(shù)λ的取值范圍是0～1間的實(shí)數(shù)。通過調(diào)整λ的值平衡兩個(gè)異構(gòu)信息源對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)表示的影響程度。當(dāng)λ=1，表示只考慮拓?fù)浣Y(jié)構(gòu)，λ=0，表示只考慮節(jié)點(diǎn)屬性。λ值越低，最終的低維節(jié)點(diǎn)表示受到節(jié)點(diǎn)屬性的影響越重。

在獲得網(wǎng)絡(luò)節(jié)點(diǎn)的高維表示后，需要對(duì)其進(jìn)行降維操作，獲得網(wǎng)絡(luò)節(jié)點(diǎn)的低維特征表示。通?？墒褂镁仃嚪纸夥椒ǎ捎跍\層模型很難捕獲到高度非線性的網(wǎng)絡(luò)結(jié)構(gòu)，本文使用變分自編碼器對(duì)PPMI矩陣進(jìn)行降維。

4 變分自編碼器

VANRL 方法采用變分自編碼器（variational auto encoder，VAE）[21]對(duì)PPMI矩陣X進(jìn)行特征提取，得到低維的向量矩陣，VAE 結(jié)構(gòu)如圖1 所示。其中，編碼器是參數(shù)為θ的神經(jīng)網(wǎng)絡(luò)，表示為qθ(z|x)。編碼器將輸入映射到潛在向量。解碼器是參數(shù)為ψ的神經(jīng)網(wǎng)絡(luò)，表示為，它將向量z作為輸入生成一個(gè)近似原始輸入的輸出。通過優(yōu)化度量輸入x和輸出之間距離的損失函數(shù)訓(xùn)練自編碼器。

Fig.1 Structure of variational auto-encoder圖1 變分自編碼器結(jié)構(gòu)

VAE 和普通自編碼器區(qū)別在于，編碼器不直接將輸入映射到潛在空間，而是輸出用于采樣潛在向量z的均值μz和方差σz。然后，從具有均值μz和對(duì)角協(xié)方差diag(σz)矩陣的高斯分布中生成z。最后，采樣向量z被傳遞到解碼器用于產(chǎn)生輸出。VAE不是試圖精確地逼近輸出，而是定義一個(gè)近似于輸入的基礎(chǔ)連續(xù)分布的條件分布。

VAE 的損失函數(shù)通常由兩部分組成：重構(gòu)損失和KL-散度損失。針對(duì)矩陣中第i個(gè)向量輸入的損失函數(shù)定義如下：

式（7）的第二項(xiàng)是一個(gè)正則化項(xiàng)，由KL 散度進(jìn)行約束。公式推導(dǎo)如下：

第一項(xiàng)是自編碼重構(gòu)誤差，該項(xiàng)不能求得解析解，通常通過蒙特卡洛抽樣的方式求得近似解，本文使用X和間的平方差損失來定義，也可以用交叉熵。最后將兩種損失值放在一起，通過Adam的隨機(jī)梯度下降方法實(shí)現(xiàn)在訓(xùn)練中的優(yōu)化參數(shù)。

潛在向量通過“重參數(shù)技巧”采樣[32]，z=μ+ε?σ，使得從正態(tài)分布N(μ,σ2)采樣z轉(zhuǎn)換為從分布N(0,1)中采樣ε，保證采樣結(jié)果可導(dǎo)，使得整個(gè)模型可以訓(xùn)練。

本文構(gòu)建的變分自編碼器的目標(biāo)函數(shù)如下：

其中，超參數(shù)β是懲罰因子，引入β使得潛在向量的每個(gè)分量代表原始輸入的不同特征[33]。通過調(diào)整β減少KL-散度損失的權(quán)重。使VAE 朝著更高質(zhì)量的重構(gòu)方向推進(jìn)，降低隨機(jī)性。

5 VANRL方法

本章介紹基于變分自編碼器的NRL方法VANRL，主要包括3 個(gè)步驟：計(jì)算網(wǎng)絡(luò)-屬性聯(lián)合概率轉(zhuǎn)移矩陣M；使用Random Surfing 模型計(jì)算共生矩陣M?，并獲得PPMI 矩陣X；構(gòu)建變分自編碼器對(duì)矩陣X進(jìn)行特征提取，獲取網(wǎng)絡(luò)的低維特征向量表示矩陣Z。具體的方法流程見算法1。

算法1VANRL

輸入：網(wǎng)絡(luò)G的鄰接矩陣A，屬性矩陣W以及設(shè)置相關(guān)參數(shù)。

輸出：特征向量矩陣Z。

1.基于式（3）～式（6）計(jì)算M；

2.初始化矩陣P0、M?、P；

3.fori=1 tokdo

5.M?=M?+P；

6.end for

7.X=PPMI(M?)；/*生成PPMI矩陣*/

8.變分自編碼器建模；

9.fori=1 tomdo

10.輸入PPMI矩陣X；

11.通過式（9）訓(xùn)練變分自編碼器；

12.end for

13.returnZ

首先，VANRL 方法的輸入包括三部分：網(wǎng)絡(luò)G的鄰接矩陣A∈Rn×n，節(jié)點(diǎn)屬性矩陣W∈Rm×n；計(jì)算PPMI 矩陣階段所需要的參數(shù)，包括控制屬性相似度矩陣非0 元素個(gè)數(shù)的參數(shù)l，調(diào)節(jié)結(jié)構(gòu)和屬性比重的參數(shù)λ，Random Surfing 模型中的跳轉(zhuǎn)概率α，迭代次數(shù)k；變分自編碼器特征提取階段，包括潛在空間的維度d，神經(jīng)網(wǎng)絡(luò)的層數(shù)t和訓(xùn)練次數(shù)m。

算法1 的第1 行～第7 行，首先通過矩陣A和W聯(lián)合生成轉(zhuǎn)移矩陣M；接著初始化矩陣P0、M?、P，其中P0和P都是n×n的單位矩陣，M?是n×n的全0 矩陣，用以保存每次迭代的結(jié)果；接下來使用Random Surfing模型捕獲節(jié)點(diǎn)間的高階相似性，通過k次迭代后輸出矩陣M?，由于矩陣M?的稀疏性，通過捕獲節(jié)點(diǎn)共現(xiàn)信息重建一個(gè)更密集的PPMI矩陣X。

算法1 的第8 行～第12 行，構(gòu)建一個(gè)變分自編碼器，將矩陣X作為輸入送入編碼器，對(duì)X進(jìn)行降維操作，循環(huán)執(zhí)行m次，最終得到低維的特征矩陣Z∈Rn×d。變分自編碼器不僅能夠?qū)W習(xí)數(shù)據(jù)背后的高度非線性規(guī)律，還能學(xué)習(xí)到數(shù)據(jù)的分布，使得學(xué)習(xí)的潛在表示更加健壯。

6 實(shí)驗(yàn)結(jié)果與分析

本章使用4個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集對(duì)VANRL方法進(jìn)行性能評(píng)價(jià)。首先介紹實(shí)驗(yàn)環(huán)境、數(shù)據(jù)集和典型的比較方法，然后進(jìn)行節(jié)點(diǎn)分類實(shí)驗(yàn)、鏈接預(yù)測(cè)實(shí)驗(yàn)和參數(shù)λ對(duì)VANRL方法影響實(shí)驗(yàn)。

6.1 實(shí)驗(yàn)準(zhǔn)備

本文的實(shí)驗(yàn)環(huán)境設(shè)置為：Windows 10操作系統(tǒng)，Intel i7-4790 3.6 GHz CPU，8 GB 內(nèi)存。本文提出的方法及實(shí)驗(yàn)基于Python語言和TensorFlow編碼實(shí)現(xiàn)。

（1）數(shù)據(jù)集

使用4個(gè)真實(shí)數(shù)據(jù)集Cora、Citeseer、BlogCatalog、Flickr 進(jìn)行實(shí)驗(yàn)。Cora 是一個(gè)引文網(wǎng)絡(luò)，由2 708 篇出版物及其引用關(guān)系組成，出版物分為7組。每個(gè)出版物的屬性用二進(jìn)制向量表示，“0”表示相應(yīng)單詞存在，“1”表示不存在。Citeseer 也是一個(gè)引文網(wǎng)絡(luò)，由3 312 篇論文及其引用關(guān)系組成，論文有6 個(gè)類別。每篇論文的屬性用二進(jìn)制向量表示，描述對(duì)應(yīng)單詞是否出現(xiàn)。BlogCatalog 網(wǎng)絡(luò)是一個(gè)社交網(wǎng)絡(luò)，由5 196個(gè)博主和博主間的交互關(guān)系組成，博主根據(jù)個(gè)人興趣分為6 組。博客的關(guān)鍵詞用于構(gòu)建用戶的屬性特征。用二進(jìn)制向量表示對(duì)應(yīng)關(guān)鍵字的出現(xiàn)狀態(tài)。Flickr是一個(gè)在線照片共享平臺(tái)，網(wǎng)絡(luò)包括7 575個(gè)用戶和239 738個(gè)跟隨者-關(guān)注者關(guān)系，這些用戶加入9個(gè)預(yù)定義組。用戶的功能由其圖像的標(biāo)簽描述，根據(jù)相應(yīng)標(biāo)簽的出現(xiàn)或缺失，每個(gè)用戶由12 047 維二進(jìn)制向量表示。對(duì)于上述網(wǎng)絡(luò)，忽略鏈接的方向。詳細(xì)信息見表1。

Table 1 Datasets for real networks表1 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集

（2）比較方法

將本文提出的方法與已有的典型方法進(jìn)行比較，其中DeepWalk[6]、Node2Vec[15]、GraRep[17]、DNGR[11]是基于結(jié)構(gòu)的NRL方法，AANE[28]和TADW[18]是結(jié)構(gòu)和屬性融合的NRL方法。比較方法詳細(xì)信息如下：

DeepWalk：通過隨機(jī)游走和SkipGram[22]模型學(xué)習(xí)節(jié)點(diǎn)表示。

Node2Vec：通過有偏的隨機(jī)游走和SkipGram[22]模型學(xué)習(xí)節(jié)點(diǎn)表示。

GraRep：通過將LINE[16]擴(kuò)展到更高階相似性并使用SVD訓(xùn)練模型學(xué)習(xí)節(jié)點(diǎn)表示。

DNGR：通過深度神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)網(wǎng)絡(luò)節(jié)點(diǎn)表示的方法，與本文工作類似。

AANE：通過聯(lián)合矩陣分解從網(wǎng)絡(luò)鏈接和內(nèi)容信息中學(xué)習(xí)節(jié)點(diǎn)表示。

TADW：通過矩陣分解將節(jié)點(diǎn)文本特征融入網(wǎng)絡(luò)表示學(xué)習(xí)過程。

（3）參數(shù)設(shè)置

對(duì)于所有方法，為公平比較，針對(duì)節(jié)點(diǎn)分類和鏈接預(yù)測(cè)任務(wù)，所有方法的參數(shù)都是固定的。其中，最終輸出的節(jié)點(diǎn)向量表示的維度均設(shè)置為128。針對(duì)基于隨機(jī)游走的方法，DeepWalk 和Node2Vec，將游走次數(shù)、游走長(zhǎng)度和窗口大小統(tǒng)一設(shè)置為10、80、10。Node2Vec的參數(shù)p和q均設(shè)置為0.5。對(duì)于GraRep，kStep設(shè)置為4。對(duì)于AANE，正則化參數(shù)λ設(shè)置為0.05，懲罰參數(shù)ρ設(shè)置為5，最大迭代次數(shù)設(shè)置為10。對(duì)于TADW，參數(shù)λ設(shè)置為0.2，最大迭代次數(shù)設(shè)置為10。DNGR 和VANRL 具有一些相同的參數(shù)，設(shè)置相同。其中，α設(shè)置為0.98，k設(shè)置為4，神經(jīng)網(wǎng)絡(luò)模型層數(shù)設(shè)為3層，通過Adam優(yōu)化器訓(xùn)練，迭代次數(shù)設(shè)置為400，學(xué)習(xí)率為0.002。針對(duì)本文方法VANRL，參數(shù)λ設(shè)置為0.7。

Table 2 Node classification performance on Cora表2 Cora數(shù)據(jù)集上的節(jié)點(diǎn)分類性能

6.2 節(jié)點(diǎn)分類

節(jié)點(diǎn)分類是網(wǎng)絡(luò)分析中的一項(xiàng)典型任務(wù)，用于評(píng)價(jià)NRL方法的性能。本文采用Macro-F1[37]和Micro-F1[37]評(píng)價(jià)方法的性能。Micro-F1 是所有不同類別標(biāo)簽上F1 值的加權(quán)平均值。Macro-F1 是所有輸出類標(biāo)簽的F1 值的算術(shù)平均值。值越高，分類性能越好。在得到節(jié)點(diǎn)表示形式后，隨機(jī)抽取一定比率標(biāo)記的節(jié)點(diǎn)進(jìn)行訓(xùn)練，其余的用于測(cè)試。將訓(xùn)練比率從10%變?yōu)?0%，步長(zhǎng)為20%。重復(fù)這個(gè)過程10 次，并報(bào)告Micro-F1和Macro-F1的平均性能。表2～表5顯示VANRL和比較方法在4個(gè)給定數(shù)據(jù)集中的性能。

最優(yōu)結(jié)果進(jìn)行加粗顯示，實(shí)驗(yàn)結(jié)果顯示，針對(duì)引文網(wǎng)絡(luò)Cora，AANE 的性能最差，利用節(jié)點(diǎn)屬性對(duì)于提高節(jié)點(diǎn)分類的性能似乎沒有太大幫助。針對(duì)Citeseer、BlogCatalog、Flickr，結(jié)合節(jié)點(diǎn)屬性信息的方法顯示出明顯的優(yōu)勢(shì)。本文提出的VANRL方法在4個(gè)數(shù)據(jù)中的性能取得令人滿意的表現(xiàn)。在Cora、Citeseer 和Flickr中的性能是最好的，在BlogCatalog中的性能也接近最優(yōu)結(jié)果。節(jié)點(diǎn)分類任務(wù)的結(jié)果表明，在NRL的過程中，如果利用節(jié)點(diǎn)的屬性信息，往往可以提高節(jié)點(diǎn)分類的性能。

Table 3 Node classification performance on Citeseer表3 Citeseer數(shù)據(jù)集上的節(jié)點(diǎn)分類性能

Table 4 Node classification performance on BlogCatalog表4 BlogCatalog數(shù)據(jù)集上的節(jié)點(diǎn)分類性能

6.3 鏈接預(yù)測(cè)

Fig.2 Link prediction performance on Cora圖2 Cora數(shù)據(jù)集上的鏈接預(yù)測(cè)性能

Table 5 Node classification performance on Flickr表5 Flickr數(shù)據(jù)集上的節(jié)點(diǎn)分類性能

鏈接預(yù)測(cè)是網(wǎng)絡(luò)分析中的另一項(xiàng)典型任務(wù)，目的是預(yù)測(cè)兩個(gè)節(jié)點(diǎn)之間是否存在邊。針對(duì)鏈接預(yù)測(cè)任務(wù)，從輸入網(wǎng)絡(luò)中移除一定比率的已有鏈接。移除鏈接中的節(jié)點(diǎn)對(duì)被視為正樣本。隨機(jī)采樣相同數(shù)量的未連接的節(jié)點(diǎn)對(duì)作為負(fù)樣本。正樣本和負(fù)樣本形成平衡數(shù)據(jù)集。將鏈接移除比率從10%變?yōu)?0%，步長(zhǎng)為10%。基于剩余網(wǎng)絡(luò)，運(yùn)行不同的NRL方法學(xué)習(xí)節(jié)點(diǎn)表示。曲線下面積（area under curve，AUC）[38]用于評(píng)價(jià)標(biāo)簽之間的一致性和樣本的相似性得分。給定樣本中的節(jié)點(diǎn)對(duì)，根據(jù)它們的表示向量計(jì)算余弦相似度得分。較高的AUC值表示更好的性能。圖2～圖5顯示VANRL與比較方法在給定數(shù)據(jù)集中的性能。

Fig.3 Link prediction performance on Citeseer圖3 Citeseer數(shù)據(jù)集上的鏈接預(yù)測(cè)性能

Fig.4 Link prediction performance on BlogCatalog圖4 BlogCatalog數(shù)據(jù)集上的鏈接預(yù)測(cè)性能

結(jié)果顯示，針對(duì)引文網(wǎng)絡(luò)Cora 和Citeseer，在基于結(jié)構(gòu)的NRL方法中，當(dāng)鏈接移除比率低于50%時(shí)，GraRep 表現(xiàn)最佳；而當(dāng)鏈接移除比率超過50%時(shí)，GraRep與DeepWalk、Node2Vec和DNGR相比沒有顯示出顯著的優(yōu)勢(shì)。在基于結(jié)構(gòu)-屬性融合的NRL方法中，融合屬性的NRL 比僅保留結(jié)構(gòu)的NRL 方法表現(xiàn)要好得多。這證明節(jié)點(diǎn)屬性可以在很大程度上有助于學(xué)習(xí)更多信息的節(jié)點(diǎn)表示。當(dāng)訓(xùn)練比率為50%時(shí)，AANE 的表現(xiàn)優(yōu)于TADW。而當(dāng)鏈接移除比率超過50%時(shí)，TADW 的性能急劇下降。在引文網(wǎng)絡(luò)中，VANRL 取得令人滿意的表現(xiàn)。針對(duì)社交網(wǎng)絡(luò)Blog-Catalog，基于結(jié)構(gòu)-屬性融合的NRL表現(xiàn)不如基于結(jié)構(gòu)的NRL 方法，GraRep 與DNGR 表現(xiàn)突出。結(jié)果表明對(duì)于BlogCatalog 上的鏈接預(yù)測(cè)任務(wù)，融入屬性反而會(huì)導(dǎo)致結(jié)果的惡化。對(duì)于VANRL，由于參數(shù)λ值為0.7，表示只融入了少量的節(jié)點(diǎn)屬性信息，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)仍對(duì)最終的節(jié)點(diǎn)表示起到?jīng)Q定性的作用，針對(duì)鏈接預(yù)測(cè)任務(wù)，VANRL 性能較好。針對(duì)社交網(wǎng)絡(luò)Flickr，基于結(jié)構(gòu)-屬性融合的NRL表現(xiàn)優(yōu)于基于結(jié)構(gòu)的NRL方法。VANRL表現(xiàn)不令人滿意，雖然當(dāng)鏈接移除比例增大到60%時(shí)，VANRL性能有所回升。

6.4 λ 的影響

本節(jié)測(cè)試參數(shù)λ對(duì)VANRL 方法的影響。λ的取值范圍是0～1之間的任何實(shí)數(shù)，用于調(diào)整屬性信息在最終的向量表示中的重要程度。λ設(shè)置為0 表示純粹利用屬性學(xué)習(xí)節(jié)點(diǎn)表示，值越大表示屬性的重要性越低。

Fig.5 Link prediction performance on Flickr圖5 Flickr數(shù)據(jù)集上的鏈接預(yù)測(cè)性能

針對(duì)Cora、Citeseer、BlogCatalog、Flickr 數(shù)據(jù)集，其他參數(shù)設(shè)置不變，將λ的值從0.1 調(diào)整到0.9，間隔為0.1。通過節(jié)點(diǎn)分類和鏈接預(yù)測(cè)任務(wù)觀察不同的λ值對(duì)VANRL 的影響。針對(duì)鏈接預(yù)測(cè)，移除10%鏈接。針對(duì)節(jié)點(diǎn)分類，訓(xùn)練集比率是10%。評(píng)價(jià)方法與之前相同。圖6顯示給定環(huán)境下VANRL在節(jié)點(diǎn)分類和鏈接預(yù)測(cè)中性能。

針對(duì)Cora 和Flickr 數(shù)據(jù)集，λ的范圍調(diào)整對(duì)VANRL 的影響不是特別明顯。VANRL 在鏈接預(yù)測(cè)和節(jié)點(diǎn)分類任務(wù)上，隨著λ取值范圍的調(diào)整，VANRL性能穩(wěn)定，沒有出現(xiàn)較大幅度的波動(dòng)。針對(duì)Blog-Catalog 和Flickr 數(shù)據(jù)集，λ的調(diào)整對(duì)VANRL 的性能影響較大，針對(duì)不同的任務(wù)出現(xiàn)兩極分化。具體而言，當(dāng)設(shè)置較低的λ的值，對(duì)于節(jié)點(diǎn)分類任務(wù)，VANRL性能有明顯的提升；但是對(duì)于鏈接預(yù)測(cè)任務(wù)，相同的設(shè)置卻導(dǎo)致VANRL性能惡化。

7 結(jié)束語

本文提出一種基于變分自編碼器的NRL 方法VANRL。通過轉(zhuǎn)移矩陣將結(jié)構(gòu)信息和節(jié)點(diǎn)屬性結(jié)合到一起，利用Random Surfing模型計(jì)算共現(xiàn)矩陣進(jìn)而生成PPMI 矩陣，為學(xué)習(xí)到高質(zhì)量節(jié)點(diǎn)表示，使用變分自編碼器提取高維向量矩陣中的特征。針對(duì)四個(gè)真實(shí)數(shù)據(jù)集（兩個(gè)社交網(wǎng)絡(luò)和兩個(gè)引文網(wǎng)絡(luò)），通過節(jié)點(diǎn)分類和鏈接預(yù)測(cè)兩個(gè)典型任務(wù)，評(píng)估VANRL和典型方法的性能。實(shí)驗(yàn)結(jié)果表明，VANRL 能夠?qū)W習(xí)節(jié)點(diǎn)和屬性的信息和高質(zhì)量表示，并且在多數(shù)環(huán)境中明顯優(yōu)于最典型的方法。至于未來的工作，目標(biāo)是將VANRL推廣到異構(gòu)網(wǎng)絡(luò)中。