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

黃海威 何慧敏 呂勝飛

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

0 引 言

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

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

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

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

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

(1) 保持網(wǎng)絡(luò)結(jié)構(gòu)特征。一些算法通過傳播節(jié)點的信息[12]或者優(yōu)化衡量相鄰節(jié)點距離的損失函數(shù)[13-14]來學(xué)習(xí)節(jié)點表示；還有一些則是直接學(xué)習(xí)一個從節(jié)點特征到節(jié)點表示的一個映射[15]。但這些算法在生成新的節(jié)點的表示時都無法保持復(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é)點數(shù)量的變化，而DepthLGP則無法處理網(wǎng)絡(luò)中邊的變化。基于矩陣分解的算法也同樣存在這種問題。增量SVD方法[17-18]可以通過先前的SVD結(jié)果來更新節(jié)點的嵌入表示，因而不需要重新運行算法。但它也只能處理網(wǎng)絡(luò)邊的變化，并且在錯誤累積到一定程度的時候，需要重新運行算法來消除這些錯誤。

(3) 網(wǎng)絡(luò)的演化信息。DynGem[19]使用了一個可以動態(tài)擴展的自編碼器來保持網(wǎng)絡(luò)結(jié)構(gòu)特征和處理變化的網(wǎng)絡(luò)規(guī)模。然而，它只是在舊的網(wǎng)絡(luò)參數(shù)上訓(xùn)練當前的網(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)有算法面臨的以上三點挑戰(zhàn)，RNNE在算法的三個主要組成部分(預(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)移矩陣來計算節(jié)點的特征，比起僅僅使用鄰接矩陣，可以保持節(jié)點更大的鄰居范圍的特征。并且在訓(xùn)練模型中，RNNE的損失函數(shù)也同時考慮節(jié)點之間的一階和高階相似度。一階相似度表示節(jié)點間是否有直接的邊相連,高階相似度則表示節(jié)點的鄰居的相似度。

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

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

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

1 RNNE算法與模型

1.1 問題定義

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

1.2 模型描述

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

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

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

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

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

1.3 預(yù)處理

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

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

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

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

(1)

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

(2)

1.4 模型訓(xùn)練

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

表1 符號解釋

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

(3)

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

(4)

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

盡管在Mk和xui,k中有大量的0元素，但實際上更關(guān)心的是其中的非0元素。因為0元素不一定表示兩個節(jié)點之間沒有關(guān)聯(lián)，而非0元素以明確表示兩個節(jié)點確實有一定程度的關(guān)聯(lián)，在學(xué)習(xí)過程中過度關(guān)注0元素可能會導(dǎo)致隱含的節(jié)點關(guān)系難以被挖掘。因此，本文借鑒SDNE的方法，在計算重構(gòu)誤差時，賦予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é)點得到的表示結(jié)果在嵌入空間中會更加靠近。

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

(6)

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

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

(7)

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

(8)

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

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

(9)

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

1.5 復(fù)雜度分析

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

2 實驗過程

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

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

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

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

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

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

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

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

(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é)點特征到嵌入空間的一一映射進行學(xué)習(xí)，其損失函數(shù)同時考慮了一階和二階相似度。

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

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

對于本文提出的RNNE模型，自編碼器的規(guī)模大小在不同數(shù)據(jù)集上有所不同。自編碼器的規(guī)模由組成其的各個全連接層的規(guī)模來描述,前面的數(shù)字表示編碼器的規(guī)模，最后一個數(shù)字表示輸出的節(jié)點表示的維數(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)先對α進行搜索，其次是β，最后是γ。并且先通過大步長搜索確定合適的范圍，有必要的話，再通過小步長搜索優(yōu)化結(jié)果，以此盡可能減少搜索次數(shù)和計算量。

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

2.3 評估方式

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

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

(10)

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

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

(11)

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

3 實驗結(jié)果分析

3.1 重 構(gòu)

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

(a) CA-Condmat

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

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

3.2 節(jié)點分類

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

(a) blogCatalog

(b) Wiki

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

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

3.3 鏈路預(yù)測

鏈路預(yù)測嘗試從網(wǎng)絡(luò)中去尋找那些可能有關(guān)聯(lián)但沒有邊相連的節(jié)點。在進行實驗之前，將測試數(shù)據(jù)集中15%的網(wǎng)絡(luò)邊進行隱藏，通過節(jié)點的低維表示來預(yù)測這些被隱藏的邊。在計算precision@k時，忽略那些被預(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

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

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使用了虛擬點來維持網(wǎng)絡(luò)的結(jié)構(gòu)。RNNE使用循環(huán)神經(jīng)網(wǎng)絡(luò)來處理網(wǎng)絡(luò)序列，通過傳遞信息來盡可能地對網(wǎng)絡(luò)的真實狀態(tài)進行嵌入，而不僅僅考慮網(wǎng)絡(luò)在局部時間的狀態(tài)。將RNNE與其他算法在不同的數(shù)據(jù)集和任務(wù)上進行了對比實驗，結(jié)果說明RNNE在動態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)上能夠取得較好的結(jié)果。

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