基于循環(huán)神經(jīng)網(wǎng)絡(luò)的在線動態(tài)網(wǎng)絡(luò)嵌入算法

黃海威 何慧敏 呂勝飛

(中國科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 安徽 合肥 230027)

0 引 言

在日常的生活和研究中有著許多網(wǎng)絡(luò)型的數(shù)據(jù)，例如社交網(wǎng)絡(luò)和購物網(wǎng)絡(luò)。但通常這些現(xiàn)實(shí)世界的網(wǎng)絡(luò)規(guī)模較大且復(fù)雜，很難在相關(guān)應(yīng)用中直接使用。現(xiàn)在通用的方法是將網(wǎng)絡(luò)嵌入到一個(gè)可以度量和計(jì)算的稠密空間。

網(wǎng)絡(luò)嵌入是為網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)學(xué)習(xí)一個(gè)低維表示，其他使用節(jié)點(diǎn)特征作為輸入的算法可直接在對應(yīng)的低維空間進(jìn)行。網(wǎng)絡(luò)嵌入在一些傳統(tǒng)的任務(wù)上有著良好的表現(xiàn)，例如鏈路預(yù)測、推薦系統(tǒng)及節(jié)點(diǎn)分類。

目前主要有兩種方式來實(shí)現(xiàn)網(wǎng)絡(luò)嵌入：第一種是基于矩陣分解的方法[1]，它通過分解網(wǎng)絡(luò)的鄰接矩陣或者拉普拉斯矩陣等來獲取節(jié)點(diǎn)的低維表示；第二種是基于深度學(xué)習(xí)的方法，大部分深度學(xué)習(xí)方法都嘗試去綜合節(jié)點(diǎn)所在的結(jié)構(gòu)信息來獲得其低維表示[2～5]。

但上述提及的算法大多是適用于節(jié)點(diǎn)和邊均為已知且固定的靜態(tài)網(wǎng)絡(luò)。然而，現(xiàn)實(shí)中許多的網(wǎng)絡(luò)有著高度的動態(tài)特性，例如社交網(wǎng)絡(luò)、金融交易網(wǎng)絡(luò)和電話網(wǎng)絡(luò)。這些網(wǎng)絡(luò)會頻繁發(fā)生改變并且在演變過程中留下豐富的歷史信息。當(dāng)網(wǎng)絡(luò)發(fā)生改變時(shí)，靜態(tài)網(wǎng)絡(luò)嵌入算法需要重新在新的網(wǎng)絡(luò)上運(yùn)行一次，這通常會消耗掉大量的時(shí)間和計(jì)算資源。

動態(tài)網(wǎng)絡(luò)通常有兩類：一種是隨著時(shí)間推移其拓?fù)鋱D的節(jié)點(diǎn)和邊會增加或者減少；第二類則是網(wǎng)絡(luò)的邊會包含時(shí)間信息，例如電話網(wǎng)絡(luò)。其學(xué)習(xí)與訓(xùn)練屬于動力學(xué)系統(tǒng)學(xué)習(xí)的范疇[6-7]，可以使用多種方法進(jìn)行學(xué)習(xí)，如基于集成學(xué)習(xí)[6-9]和統(tǒng)計(jì)模型[7,10-11]的方法，以及基于靜態(tài)網(wǎng)絡(luò)嵌入的方法。它們或多或少會遇到以下幾個(gè)方面的挑戰(zhàn)：

(1) 保持網(wǎng)絡(luò)結(jié)構(gòu)特征。一些算法通過傳播節(jié)點(diǎn)的信息[12]或者優(yōu)化衡量相鄰節(jié)點(diǎn)距離的損失函數(shù)[13-14]來學(xué)習(xí)節(jié)點(diǎn)表示；還有一些則是直接學(xué)習(xí)一個(gè)從節(jié)點(diǎn)特征到節(jié)點(diǎn)表示的一個(gè)映射[15]。但這些算法在生成新的節(jié)點(diǎn)的表示時(shí)都無法保持復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)特征。

(2) 不斷變化的網(wǎng)絡(luò)。為保持網(wǎng)絡(luò)結(jié)構(gòu)特性，SDNE[2]和DepthLGP[16]使用了深度神經(jīng)網(wǎng)絡(luò)模型來學(xué)習(xí)網(wǎng)絡(luò)的低維表示。但SDNE無法處理網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的變化，而DepthLGP則無法處理網(wǎng)絡(luò)中邊的變化。基于矩陣分解的算法也同樣存在這種問題。增量SVD方法[17-18]可以通過先前的SVD結(jié)果來更新節(jié)點(diǎn)的嵌入表示，因而不需要重新運(yùn)行算法。但它也只能處理網(wǎng)絡(luò)邊的變化，并且在錯(cuò)誤累積到一定程度的時(shí)候，需要重新運(yùn)行算法來消除這些錯(cuò)誤。

(3) 網(wǎng)絡(luò)的演化信息。DynGem[19]使用了一個(gè)可以動態(tài)擴(kuò)展的自編碼器來保持網(wǎng)絡(luò)結(jié)構(gòu)特征和處理變化的網(wǎng)絡(luò)規(guī)模。然而，它只是在舊的網(wǎng)絡(luò)參數(shù)上訓(xùn)練當(dāng)前的網(wǎng)絡(luò)而拋棄了網(wǎng)絡(luò)演變過程的歷史信息。

為了提高動態(tài)網(wǎng)絡(luò)嵌入的效果，本文提出了循環(huán)網(wǎng)絡(luò)嵌入(Recurrent Neural Network Embedding，RNNE)。該算法基于深度學(xué)習(xí)網(wǎng)絡(luò)，其流程和結(jié)構(gòu)如圖1所示。針對現(xiàn)有算法面臨的以上三點(diǎn)挑戰(zhàn)，RNNE在算法的三個(gè)主要組成部分(預(yù)處理、訓(xùn)練窗口和訓(xùn)練模型)中采取如下處理方式：

(a) RNNE網(wǎng)絡(luò)單元示意圖

(b) RNNE整體結(jié)構(gòu)示意圖圖1 RNNE的網(wǎng)絡(luò)單元與整體結(jié)構(gòu)示意圖

(1) 保持網(wǎng)絡(luò)結(jié)構(gòu)。RNNE在預(yù)處理部分中使用了多步概率轉(zhuǎn)移矩陣來計(jì)算節(jié)點(diǎn)的特征，比起僅僅使用鄰接矩陣，可以保持節(jié)點(diǎn)更大的鄰居范圍的特征。并且在訓(xùn)練模型中，RNNE的損失函數(shù)也同時(shí)考慮節(jié)點(diǎn)之間的一階和高階相似度。一階相似度表示節(jié)點(diǎn)間是否有直接的邊相連,高階相似度則表示節(jié)點(diǎn)的鄰居的相似度。

(2) 適應(yīng)變化的網(wǎng)絡(luò)。RNNE會根據(jù)網(wǎng)絡(luò)的變化，靈活地添加虛擬點(diǎn)來維持網(wǎng)絡(luò)結(jié)構(gòu)。當(dāng)有新的節(jié)點(diǎn)產(chǎn)生時(shí)，RNNE就用該新的節(jié)點(diǎn)替代掉虛擬點(diǎn)，當(dāng)有節(jié)點(diǎn)被刪除時(shí)，RNNE會用虛擬點(diǎn)來替代這些被刪除的點(diǎn)。

(3) 儲存網(wǎng)絡(luò)的演化。訓(xùn)練模型的整體結(jié)構(gòu)采用循環(huán)神經(jīng)網(wǎng)絡(luò)(RNN)。在該算法中，先前的節(jié)點(diǎn)表示會作為RNNE單元的隱藏狀態(tài)被輸入，因此在嵌入表示的過程中能夠使用更多的網(wǎng)絡(luò)演化信息。同時(shí)，考慮到假如一個(gè)節(jié)點(diǎn)的性質(zhì)沒有發(fā)生改變，那么其在不同時(shí)間點(diǎn)的表示應(yīng)當(dāng)是相似的，所以在訓(xùn)練模型的損失函數(shù)中加入了衡量網(wǎng)絡(luò)穩(wěn)定性的部分。

本文所提的RNNE算法主要有以下三方面的特點(diǎn)和貢獻(xiàn)：(1) RNNE在訓(xùn)練的時(shí)候同時(shí)考慮了網(wǎng)絡(luò)的一階和高階相似度，因此可以在嵌入空間中更好地保持網(wǎng)絡(luò)原本的結(jié)構(gòu)特征。(2) 通過添加虛擬點(diǎn)，RNNE可以統(tǒng)一網(wǎng)絡(luò)在不同時(shí)間點(diǎn)的規(guī)模，并且可以很容易提取網(wǎng)絡(luò)改變的部分。(3) RNNE使用圖序列作為輸入，在嵌入時(shí)能夠整合不同時(shí)間點(diǎn)的信息，有助于消除由網(wǎng)絡(luò)波動導(dǎo)致的噪聲的影響。

1 RNNE算法與模型

1.1 問題定義

給定一個(gè)由節(jié)點(diǎn)集合V和邊集合E構(gòu)成的動態(tài)網(wǎng)絡(luò)G(V,E)，及其在一段時(shí)間序列中各個(gè)時(shí)間點(diǎn)的狀態(tài)G1(V1,E1)，G2(V2,E2)，…，Gt(Vt,Et)，對Vt中的每個(gè)節(jié)點(diǎn)v，學(xué)習(xí)一個(gè)映射f:v→RK，其中K是一個(gè)事先給定的正整數(shù)并且K<<|Vt|。

1.2 模型描述

網(wǎng)絡(luò)在每個(gè)時(shí)刻的固定狀態(tài)稱之為快照，例如定義中的G1(V1,E1)，RNNE使用離散的網(wǎng)絡(luò)快照序列來表達(dá)動態(tài)網(wǎng)絡(luò)，網(wǎng)絡(luò)的動態(tài)變化相當(dāng)于不斷有新的快照產(chǎn)生。

RNNE模型基于兩個(gè)基本假設(shè)：(1) 目標(biāo)網(wǎng)絡(luò)是穩(wěn)定的，也就是說，在短時(shí)間內(nèi)不會有太多的節(jié)點(diǎn)和邊的性質(zhì)發(fā)生改變；(2) 網(wǎng)絡(luò)的規(guī)模是有限的，因?yàn)槿魏我粋€(gè)系統(tǒng)都不能接受沒有規(guī)模上限的輸入。

在具體實(shí)現(xiàn)過程中，RNNE不會將整個(gè)網(wǎng)絡(luò)序列作為輸入，一方面是因?yàn)檫^舊的時(shí)間點(diǎn)的網(wǎng)絡(luò)狀態(tài)可能已經(jīng)過時(shí)，另一方面則是太長的輸入會消耗較多的計(jì)算資源。因此，RNNE利用一個(gè)固定長度的窗口來放置最新部分網(wǎng)絡(luò)快照，同時(shí)會對極有可能發(fā)生性質(zhì)改變的節(jié)點(diǎn)進(jìn)行檢測，并將其從訓(xùn)練節(jié)點(diǎn)中剔除。

僅通過一個(gè)時(shí)刻的狀態(tài)來表示動態(tài)網(wǎng)絡(luò)節(jié)點(diǎn)將會損失部分網(wǎng)絡(luò)信息，因此RNNE在訓(xùn)練過程中會同時(shí)考慮節(jié)點(diǎn)的當(dāng)前狀態(tài)和此前的若干個(gè)狀態(tài)。鑒于循環(huán)神經(jīng)網(wǎng)絡(luò)(RNN)[20]對前序信息的記憶能力，RNNE使用一個(gè)隱藏狀態(tài)來表示一個(gè)節(jié)點(diǎn)先前的信息。

總體而言，RNNE首先會選擇出合適的節(jié)點(diǎn)，然后使用模型的隱藏狀態(tài)和節(jié)點(diǎn)的特征作為輸入來優(yōu)化節(jié)點(diǎn)的各項(xiàng)相似度。

1.3 預(yù)處理

每個(gè)節(jié)點(diǎn)都會預(yù)設(shè)置一個(gè)“state”屬性，并且初始化為“normal”，用來表示該節(jié)點(diǎn)為一個(gè)普通節(jié)點(diǎn)。為了保持輸入規(guī)模的統(tǒng)一，本文定義了一類虛擬節(jié)點(diǎn)，其為不與任何其他的點(diǎn)相連的孤立點(diǎn)，作用是為了幫助統(tǒng)一不同時(shí)刻網(wǎng)絡(luò)的規(guī)模。當(dāng)有新的節(jié)點(diǎn)產(chǎn)生時(shí)，RNNE就用該新的節(jié)點(diǎn)替代掉虛擬點(diǎn)，當(dāng)有節(jié)點(diǎn)被刪除時(shí)，RNNE會用虛擬點(diǎn)來替代這些被刪除的點(diǎn)。虛擬點(diǎn)的“state”被設(shè)置為“virtual”。如果Gk的節(jié)點(diǎn)數(shù)目|Vk|沒有達(dá)到規(guī)定的上限N，就在Gk中添加虛擬點(diǎn)直到|Vk|=N。

在訓(xùn)練之前，將需要訓(xùn)練的網(wǎng)絡(luò)快照逐個(gè)添加到訓(xùn)練窗口中。當(dāng)新的快照到達(dá)時(shí)，如果它屬于第一種動態(tài)網(wǎng)絡(luò)的類型，即隨著時(shí)間推移其拓?fù)鋱D的節(jié)點(diǎn)和邊會增加或者減少的網(wǎng)絡(luò)，可以直接將其加入訓(xùn)練窗口，否則將其與上一個(gè)快照的增量部分放入訓(xùn)練窗口。如果訓(xùn)練窗口達(dá)到上限，就將最早的快照移出，并且檢查所有的節(jié)點(diǎn)來剔除那些性質(zhì)可能發(fā)生改變的點(diǎn)。

為了在訓(xùn)練時(shí)更好地保持節(jié)點(diǎn)的高階相似度，采用下面的方式來計(jì)算節(jié)點(diǎn)的特征。

首先，定義函數(shù)normalized表示矩陣A中每一個(gè)元素都會除以所在行的最大值，以此得到矩陣元素的規(guī)范化表示,其表達(dá)式為：

(1)

基于normalized函數(shù)，假設(shè)Pk∈RN×N是Gk的單步概率轉(zhuǎn)移矩陣，矩陣網(wǎng)絡(luò)的特征矩陣Xk計(jì)算如下：

(2)

1.4 模型訓(xùn)練

假設(shè)在訓(xùn)練窗口中已經(jīng)有n個(gè)網(wǎng)絡(luò)快照，分別為Ga+1,Ga+2,…,Ga+n，表1展示了下文出現(xiàn)的符號的含義。

表1 符號解釋

RNNE單元的整體結(jié)構(gòu)是一個(gè)自編碼器。其中編碼器E由多層非線性全連接層組成，用于將輸入數(shù)據(jù)映射到嵌入空間。解碼器D也同樣由多層非線性全連接層組成，用于將節(jié)點(diǎn)的表示進(jìn)行重構(gòu)。給定輸入數(shù)據(jù)后，每個(gè)RNNE單元將會進(jìn)行如下計(jì)算：

(3)

自編碼器的目標(biāo)是為了最小化輸入和輸出的重構(gòu)誤差，其損失函數(shù)計(jì)算如下：

(4)

正如文獻(xiàn)[23]里描述的，雖然最小化重構(gòu)誤差不能確保樣本在嵌入后的相似度，但其可以讓嵌入過程的數(shù)據(jù)流型更加平滑，而這一點(diǎn)可以有助于保持樣本嵌入后的相似度。也就是說，對于相似的輸入會容易有相似的輸出，即兩個(gè)節(jié)點(diǎn)擁有相似的特征，那么其嵌入表示也會相似。同時(shí)，如果自編碼器可以有效地從節(jié)點(diǎn)嵌入表示重構(gòu)節(jié)點(diǎn)的特征，則可以說明嵌入表示中含有代表節(jié)點(diǎn)特征的足夠信息。

盡管在Mk和xui,k中有大量的0元素，但實(shí)際上更關(guān)心的是其中的非0元素。因?yàn)?元素不一定表示兩個(gè)節(jié)點(diǎn)之間沒有關(guān)聯(lián)，而非0元素以明確表示兩個(gè)節(jié)點(diǎn)確實(shí)有一定程度的關(guān)聯(lián)，在學(xué)習(xí)過程中過度關(guān)注0元素可能會導(dǎo)致隱含的節(jié)點(diǎn)關(guān)系難以被挖掘。因此，本文借鑒SDNE的方法，在計(jì)算重構(gòu)誤差時(shí)，賦予0元素和非0元素不同的權(quán)重。得到新的損失函數(shù)如下所示：

(5)

式中：⊙表示哈德瑪積;Wui,k={wui,j,k}j=1N+d，如果mui,j,k∈Mk=0,wui,j,k=1,否則wui,j,k=β>1。通過最小化損失函數(shù)，擁有相似鄰居結(jié)構(gòu)的節(jié)點(diǎn)得到的表示結(jié)果在嵌入空間中會更加靠近。

除了考慮節(jié)點(diǎn)的鄰居結(jié)構(gòu)，也對節(jié)點(diǎn)之間直接相連的邊予以關(guān)注。由邊直接相連的節(jié)點(diǎn)，其聯(lián)系也更緊密，在嵌入空間中的距離應(yīng)該更接近。使用一階相似度來衡量這種關(guān)系，其計(jì)算方式如下：

(6)

如果mui,uj,k>0，表示節(jié)點(diǎn)vui,k和vuj,k有相連的邊。

在上面的部分中只考慮了每個(gè)網(wǎng)絡(luò)快照各自的特征。假如網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)在演化過程中性質(zhì)沒有發(fā)生改變，傾向于將它映射到嵌入空間的同一個(gè)位置。在選取訓(xùn)練樣本節(jié)點(diǎn)時(shí)，所有樣本的“state”屬性均為“normal”，即這些點(diǎn)的性質(zhì)大概率沒有發(fā)生改變，所以這些點(diǎn)的在不同時(shí)刻的表示應(yīng)盡量接近。其損失函數(shù)為：

(7)

綜上所述，為了保持節(jié)點(diǎn)的一階相似度、高階相似度和穩(wěn)定性，結(jié)合式(5)-式(7)得到了最終的損失函數(shù)為：

(8)

式中：α、γ、Wui,k中的β均為模型的超參數(shù)。

最后整個(gè)模型的參數(shù)θ可以通過梯度下降法來更新，即：

(9)

式中：η為模型的學(xué)習(xí)率。

1.5 復(fù)雜度分析

通過式(8)可知，在一次迭代中，RNNE的訓(xùn)練時(shí)間復(fù)雜度是O(nb(N+d)D)，其中n為訓(xùn)練窗口的容量，b為批(batch)的大小，N是網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模上限，d為嵌入空間的維數(shù)，D是模型中間層規(guī)模的最大值。通常n、b和d為預(yù)設(shè)的常數(shù)值，N與網(wǎng)絡(luò)的實(shí)際規(guī)模線性相關(guān)，D取決于d而與節(jié)點(diǎn)數(shù)目無關(guān)。由此可將RNNE在一次迭代訓(xùn)練的時(shí)間復(fù)雜度表示為O(N)，其與網(wǎng)絡(luò)的實(shí)際規(guī)模線性相關(guān)。

2 實(shí)驗(yàn)過程

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

實(shí)驗(yàn)采取了5個(gè)數(shù)據(jù)集，分別為Wiki、email-Eu-core、blogCatalog、CA-CondMat和CA-HepPh，經(jīng)過調(diào)整和選取每個(gè)數(shù)據(jù)集中網(wǎng)絡(luò)序列的長度均為14。其節(jié)點(diǎn)和邊的范圍如表2所示，由于網(wǎng)絡(luò)的動態(tài)性，網(wǎng)絡(luò)節(jié)點(diǎn)和邊數(shù)可能在不斷發(fā)生改變，因此使用其改變范圍來進(jìn)行表示：

表2 不同數(shù)據(jù)集節(jié)點(diǎn)和邊的信息

(1) Wiki：該數(shù)據(jù)集為Wiki上的引用網(wǎng)絡(luò)，并且每個(gè)節(jié)點(diǎn)都有類別信息，共有17個(gè)不同的類別。

(2) blogCatalog[24]、email-Eu-core[25]：這2個(gè)對應(yīng)社交網(wǎng)絡(luò)。其中blogCatalog網(wǎng)絡(luò)節(jié)點(diǎn)有39個(gè)類別，email-Eu-core網(wǎng)絡(luò)節(jié)點(diǎn)有42個(gè)類別。

(3) CA-CondMat、CA-HepPh[25]:數(shù)據(jù)集對應(yīng)arXiv上的引用網(wǎng)絡(luò)。由于其沒有類別信息，所以在實(shí)驗(yàn)中這2個(gè)數(shù)據(jù)集不參與節(jié)點(diǎn)分類任務(wù)。

2.2 基準(zhǔn)算法及參數(shù)設(shè)置

本文實(shí)驗(yàn)將使用以下算法作為基準(zhǔn)算法進(jìn)行對比。對于其中的靜態(tài)網(wǎng)絡(luò)嵌入算法，將會在數(shù)據(jù)集的每個(gè)快照上都執(zhí)行一次計(jì)算過程。

(1) SDNE[2]：該算法使用了自編碼器結(jié)構(gòu)的模型，并且通過最小化一階相似度和二階相似度的損失函數(shù)來訓(xùn)練模型，將其自編碼器規(guī)模設(shè)置為encoder_layer_list=[1 000,128]，一階相似度權(quán)重設(shè)置為α=10-6，非0元素權(quán)重設(shè)置為β=5。

(2) Line[4]：與嘗試學(xué)習(xí)映射規(guī)則不同，該算法直接對從節(jié)點(diǎn)特征到嵌入空間的一一映射進(jìn)行學(xué)習(xí)，其損失函數(shù)同時(shí)考慮了一階和二階相似度。

(3) GraRep[26]：該算法考慮了節(jié)點(diǎn)的高階相似度，然后使用SVD獲得網(wǎng)絡(luò)的嵌入表示。將其高階相似度計(jì)算上限設(shè)置為Kstep=4。

(4) Hope[27]：該算法從鄰接矩陣構(gòu)造了一個(gè)非對稱關(guān)系矩陣，然后通過JDGSVD[28]獲得節(jié)點(diǎn)的低維表示。

對于本文提出的RNNE模型，自編碼器的規(guī)模大小在不同數(shù)據(jù)集上有所不同。自編碼器的規(guī)模由組成其的各個(gè)全連接層的規(guī)模來描述,前面的數(shù)字表示編碼器的規(guī)模，最后一個(gè)數(shù)字表示輸出的節(jié)點(diǎn)表示的維數(shù)，解碼器則與編碼器規(guī)模對稱。例如2 128-128表示共有三層，其規(guī)模分別為2 128、128和2 128。具體設(shè)置如表3所示。其中的超參數(shù)α、β、γ通過網(wǎng)格搜索來調(diào)整:α∈[10-6,1],β∈[1,10],γ∈[0,10]。在搜索過程中，由于α表示損失函數(shù)中一階相似度和高階相似度的比重，其影響最大，故優(yōu)先對α進(jìn)行搜索，其次是β，最后是γ。并且先通過大步長搜索確定合適的范圍，有必要的話，再通過小步長搜索優(yōu)化結(jié)果，以此盡可能減少搜索次數(shù)和計(jì)算量。

表3 RNNE模型在不同數(shù)據(jù)集上的自編碼器規(guī)模

2.3 評估方式

本文實(shí)驗(yàn)測試了算法在三種任務(wù)上的表現(xiàn)，分別為重構(gòu)、節(jié)點(diǎn)分類和鏈路預(yù)測。

在重構(gòu)和鏈路預(yù)測中，使用precision@k來衡量算法的效果，對于網(wǎng)絡(luò)G(V,E)，其定義如下：

(10)

式中：index(e)表示e在預(yù)測結(jié)果中的序號。

在節(jié)點(diǎn)分類中，使用micro-F1和macro-F1來衡量算法的效果。對于一個(gè)給定的標(biāo)簽L，TP(L)、FP(L)和FN(L)分別表示樣本中被正確預(yù)測為L、被錯(cuò)誤預(yù)測為L和是L但沒有被預(yù)測為L的數(shù)目，C為所有標(biāo)簽的集合，則micro-F1和macro-F1的計(jì)算過程如下所示：

(11)

考慮到每個(gè)數(shù)據(jù)集有14個(gè)網(wǎng)絡(luò)快照，部分算法需要在每個(gè)快照上都運(yùn)行一次，因此取precision@k、micro-F1和macro-F1在各個(gè)快照上的平均值作為最后的結(jié)果。

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

3.1 重 構(gòu)

重構(gòu)表示試圖從節(jié)點(diǎn)的表示中恢復(fù)原本的網(wǎng)絡(luò)結(jié)構(gòu)。本文實(shí)驗(yàn)通過計(jì)算節(jié)點(diǎn)在嵌入空間的距離來衡量它們的一階相似度并進(jìn)一步推測是否有邊相連。不同方法對應(yīng)的結(jié)果如圖2所示。

(a) CA-Condmat

(b) CA-HepPh圖2 數(shù)據(jù)集CA-Condmat和CA-HepPh上的平均precision@k

可以看出，RNNE在這兩個(gè)數(shù)據(jù)集上的表現(xiàn)比SDNE、Hope和Line有更好的重構(gòu)效果。在k不太大的情況下，RNNE同樣比Grarep表現(xiàn)得更好。值得注意的是，在五種算法中，RNNE、SDNE、Grarep和Line均考慮了一階相似度或者高階相似度，而Hope則欠缺了這方面的考量。可以看出，Hope的實(shí)驗(yàn)表現(xiàn)明顯比其他四個(gè)算法更差，這說明一階和高階相似度對保持網(wǎng)絡(luò)原始結(jié)構(gòu)有著明顯幫助。更進(jìn)一步地，在考慮了節(jié)點(diǎn)相似度的四個(gè)算法中，RNNE和Grarep考慮節(jié)點(diǎn)的高階相似度，而Line和SDNE至多只考慮到了二階相似度，觀察結(jié)果可以發(fā)現(xiàn)RNNE和Grarep的表現(xiàn)要優(yōu)于Line和SDNE，在一定程度上可以說明高階相似度的表達(dá)能力比二階相似度的表達(dá)能力更加豐富。

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

本文實(shí)驗(yàn)將節(jié)點(diǎn)的低維表示作為特征，對分類器進(jìn)行訓(xùn)練，將分類器預(yù)測的類別和真實(shí)類別進(jìn)行比較。特別地，使用LIBLINEAR[28]作為分類器，然后分別選取10%到90%的數(shù)據(jù)作為訓(xùn)練，其余的作為測試。不同算法在三個(gè)數(shù)據(jù)集上的分類結(jié)果如圖3所示。

(a) blogCatalog

(b) Wiki

(c) email-Eu-mail圖3 當(dāng)訓(xùn)練樣本比例變化時(shí)，三個(gè)數(shù)據(jù)集上的micro-F1和macro-F1

可以看出，RNNE在整體上比其他四個(gè)算法表現(xiàn)更優(yōu)。RNNE單元采用了自編碼器結(jié)構(gòu)，自編碼器一個(gè)重要特性即對于相似的輸入會容易有相似的輸出，因此對于同類節(jié)點(diǎn)，RNNE產(chǎn)生的相似低維表示也更容易讓它們被分類器分成同一類。另外，RNNE和Grarep都取得了不錯(cuò)的表現(xiàn)，它們有一個(gè)很重要的共同點(diǎn)就是考慮了較高階的節(jié)點(diǎn)相似度，很顯然高階相似度比起鄰接矩陣，對節(jié)點(diǎn)的特征有著更為準(zhǔn)確的刻畫，也更容易區(qū)分開相似的節(jié)點(diǎn)和不相似的節(jié)點(diǎn)，對于節(jié)點(diǎn)分類有著非常大的幫助。

3.3 鏈路預(yù)測

鏈路預(yù)測嘗試從網(wǎng)絡(luò)中去尋找那些可能有關(guān)聯(lián)但沒有邊相連的節(jié)點(diǎn)。在進(jìn)行實(shí)驗(yàn)之前，將測試數(shù)據(jù)集中15%的網(wǎng)絡(luò)邊進(jìn)行隱藏，通過節(jié)點(diǎn)的低維表示來預(yù)測這些被隱藏的邊。在計(jì)算precision@k時(shí)，忽略那些被預(yù)測出來但已經(jīng)存在于網(wǎng)絡(luò)中的邊。CA-Condmat和CA-HepPh數(shù)據(jù)集上不同算法的預(yù)測結(jié)果如圖4所示。

(a) CA-Condmat

(b) CA-HepPh圖4 數(shù)據(jù)集CA-Condmat和CA-HepPh上的平均precision@k

可以看出，在這兩個(gè)數(shù)據(jù)集的表現(xiàn)中，RNNE和Grarep相比于其他三個(gè)算法有明顯的優(yōu)勢，進(jìn)一步說明了高階相似度對于網(wǎng)絡(luò)表示學(xué)習(xí)的重要性。在數(shù)據(jù)集CA-Condmat中，RNNE的表現(xiàn)要一直優(yōu)于Grarep；在數(shù)據(jù)集CA-HepPh中，起初RNNE比其他算法有著更高的準(zhǔn)確率，當(dāng)k逐漸變大，Grarep的準(zhǔn)確率超過了RNNE。但是在實(shí)際生活和研究的任務(wù)中，人們通常只會關(guān)心那些最有可能相關(guān)的結(jié)果。一方面是由于隨著預(yù)測的邊的增多，準(zhǔn)確率的下降是不可避免的；另一方面，人們通常更關(guān)心的是那些最有可能存在聯(lián)系的節(jié)點(diǎn)。所以在k較小時(shí)擁有高準(zhǔn)確率是非常重要的。

4 結(jié) 語

本文提出了一種循環(huán)網(wǎng)絡(luò)嵌入算法(Recurrent Neural Network Embedding，RNNE)來提高動態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)的效果。一方面，RNNE通過一階相似度和高階相似度維持了網(wǎng)絡(luò)的靜態(tài)特征；另一方面，為了適應(yīng)動態(tài)網(wǎng)絡(luò)的變化性，RNNE使用了虛擬點(diǎn)來維持網(wǎng)絡(luò)的結(jié)構(gòu)。RNNE使用循環(huán)神經(jīng)網(wǎng)絡(luò)來處理網(wǎng)絡(luò)序列，通過傳遞信息來盡可能地對網(wǎng)絡(luò)的真實(shí)狀態(tài)進(jìn)行嵌入，而不僅僅考慮網(wǎng)絡(luò)在局部時(shí)間的狀態(tài)。將RNNE與其他算法在不同的數(shù)據(jù)集和任務(wù)上進(jìn)行了對比實(shí)驗(yàn)，結(jié)果說明RNNE在動態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)上能夠取得較好的結(jié)果。

為了提高網(wǎng)絡(luò)嵌入的效率，使網(wǎng)絡(luò)狀態(tài)可以得到快速的更新，在未來工作中會嘗試使用注意力機(jī)制等其他方式來進(jìn)行動態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)。同時(shí)，也會考慮從空間轉(zhuǎn)換的角度[30-31]來解決此類問題。