基于深度神經網絡和門控循環單元的動態圖表示學習方法

李慧博，趙云霄，白 亮*

（1.計算機智能與中文信息處理教育部重點實驗室（山西大學），太原 030006；2.山西大學計算機與信息技術學院，太原 030006）

（?通信作者電子郵箱bailiang@sxu.edu.cn）

0 引言

基于圖結構數據的表示學習已經成為一項重要的機器學習任務，在諸如社交網絡［1］、合作網絡［2］、蛋白質網絡［3］等各種結構中普遍適用。圖表示學習的基本思想是學習節點的低維向量表示，要求該向量盡可能地保留節點在圖中的結構信息、屬性信息等。目前多數靜態圖表示學習［4-6］已經能有效學習到節點的向量表示，但生活中大量的真實數據表現出復雜的時間特性。例如學術合作網絡中，研究人員周期性地更換合作對象；蛋白質之間的相互作用導致結構體時刻在發生變化；電子郵件通信網絡的結構也會隨著時間的推移不斷發生變化，這些信息說明了圖結構及其屬性隨時間的動態演變過程。在這種情況下，動態網絡建模對于準確預測節點屬性和未來鏈接非常重要。

本文的工作是對一系列動態圖的學習，捕獲到節點的各種信息，進而預測下一時刻的網絡。之前一些工作［7-9］試圖學習圖的結構信息和節點的時態信息，但是他們的方法存在對鄰居節點信息提取不完善、不能有效保留歷史節點信息、預測精度較低等問題。

本文受Sankar 等［10］的提出的DySAT 模型的啟發，提出了DynAEGRU 方法。DySAT模型是通過兩個注意力模塊分別學習圖的結構信息和節點的時態信息。本文方法DynAEGRU以自編碼器為框架，首先編碼器使用深度神經網絡來學習網絡的結構特征，然后輸入遞歸層來學習網絡中的時間動態性，最后在解碼器重構網絡與真實網絡對比構建損失。本文將實驗用在鏈路預測任務上進行評估，與經典的圖表示學習算法進行比較，結果表明DynAEGRU 在鏈路預測任務上優于對比算法。本文的主要工作如下：

1）提出了一種新的動態網絡學習方法——DynAEGRU，該方法可以有效捕獲節點的結構和時態特征信息；

2）展示了DynAEGRU 方法的各種變體，以顯示主要的優勢和差異；

3）通過對比實驗驗證了DynAEGRU 方法在鏈路預測任務上的有效性和優勢。

1 相關工作

圖表示學習算法以圖的結構是否會發生變化可以分為兩類：1）靜態圖表示學習，通過訓練一個固定網絡來獲取圖中節點的向量表示；2）動態圖表示學習，它通常考慮圖的多個快照，并獲得每個節點向量表示的時間序列。考慮到真實世界網絡的動態性，近幾年的工作多致力于動態圖的學習。

1.1 圖表示學習

靜態圖表示學習方法的目標是在嵌入空間中盡可能地保持原始圖中的某些屬性信息。一部分工作旨在保持圖中的結構信息［5-6］；另一部分旨在保持嵌入空間中節點的距離［11-13］；還有一些基于深度學習的方法［14-15］，它們使用深度自編碼器保留圖中節點的屬性和結構信息。

目前動態圖表示學習的多數工作是學習多個快照圖，目的是減小模型復雜度并保證嵌入的穩定性。DynamicTriad［7］是通過在動態網絡中預測三角閉合的概率來學習每個節點的向量表示，但此算法僅收集前兩個時間步的信息，不能有效捕捉動態網絡的結構變化模式；DynGEM［8］通過最小化一階和二階相似度學習節點信息，但僅保留了前一個時間步的網絡信息，忽略了動態網絡長時間的演化模式；DynAERNN［9］是以編碼器-解碼器為架構，將網絡中歷史節點組成序列用長短期記憶（Long Short-Term Memory，LSTM）網絡［16］進行學習，模型缺點是不能有效提取鄰域結構。

通過對近幾年動態圖表示學習的觀察，發現大多數模型存在對鄰域節點特征信息提取不完善、因保留時間步數較少而無法有效獲取動態圖的時間演化模式等問題。

1.2 自編碼器

自編碼器（Auto-Encoder，AE）［17］分為編碼器-解碼器兩部分結構，是前饋非循環神經網絡，具有非常好的提取數據特征表示的能力，在圖像重構［18］、聚類［19］、機器翻譯［20］等方面有著廣泛的應用。編碼器負責接收輸入x，并通過函數h變換為信號y，表達為：

解碼器將信號y作為輸入，通過函數f重構信號r表達為：

解碼器定義誤差損失為原始輸入x與重構信號r之差，網絡訓練的目標是減小兩者之間的誤差，并通過反向傳播更新隱藏層。自編碼器可以進行權值共享，即解碼器和編碼器的權值彼此互為轉置，目的是減少訓練參數，提高網絡學習的速度。

1.3 門控循環單元

2014 年Cho 等［21］提出門控循環單元（Gated Recurrent Unit，GRU）。GRU是循環神經網絡（Recurrent Neural Network，RNN）［22］的一種變體，RNN 結構如圖1所示。對于一個長度為T的序列，使用RNN 建模后是一個長度為T的前饋神經網絡，第t層的隱藏狀態聚集了前t次的信息，是用當前輸入xt和上一層隱藏狀態的輸出ht-1進行建模。

圖1 GRU的結構示意圖Fig.1 Schematic diagram of GRU structure

由于RNN 存在梯度彌散和梯度爆炸問題，往往和預期的效果相差甚遠，因此提出GRU 網絡。RNN 和GRU 網絡同樣是使用前一隱藏狀態和當前輸入進行建模，不同的是后者在其內部結構使用了重置門和更新門，GRU 結構如圖2 所示。直觀來看，重置門決定了如何將新的輸入信息與歷史信息相結合，更新門定義了前面記憶保存到當前時間步的信息量。單個GRU網絡的隱藏狀態表示定義為：

其中：rt和zt分別為控制信息傳遞的重置門和更新門；Wr、Wz、Wh'、Wo為學習的參數矩陣；(1-zt)?ht-1表示對隱藏狀態中選擇性地丟棄上個時間步輸出ht-1維度中不重要的信息；則表示對當前隱藏狀態選擇性地保留，保留當前時間步h't中一些重要的信息；因此ht就是保留上一時間步中相關的信息，并把當前時間步中相關信息加入其中；yt是當前時間步的輸出，其信息不會再改變。GRU 的優勢就在于使用一個門控zt就可以同時丟棄和保留維度中的信息，并且效率高，更易于計算。

2 DynAEGRU結構

本文旨在解決上述動態圖網絡中的復雜性和動態性問題，本文提出的方法DynAEGRU 采用經典的無監督自編碼器框架學習，它使用編碼器對輸入圖A進行編碼生成特征X，并將特征X使用解碼器生成，通過最小化A與重構鄰接矩陣的距離，在編碼器將輸入圖映射到向量空間的同時讓解碼器學習到預測圖的能力。

1）編碼器部分，本文分別使用聚合函數和分段GRU 來學習圖的結構和時態特征信息。其中聚類函數采用兩層神經網絡，每層使用聚集鄰居特征，這樣在保留所有鄰居信息的同時，更加準確地學習到局部鄰域結構，并使圖的計算更加簡便，效率更高；分段GRU 則通過保留每個節點出現的所有時刻的歷史信息來提高節點之間邊的預測能力。

2）解碼器可以重構原始圖并與原始圖對比來構建損失，這樣可以更加準確地學習到節點之間的鏈接關系。

本文方法DynAEGRU 的結構如圖2 所示：圖中左側編碼器（Encoder）部分采用聚合函數和分段GRU 對每個時間步網絡圖進行編碼；右邊解碼器（Decoder）部分完成圖的預測，并使用交叉熵損失函數來描述預測與真實網絡之間的差距，最后使用反向傳播實現網絡的訓練。實驗表明，本文在學習隨時間推移節點和邊不斷增加的網絡圖時，可以有效地學習節點信息并提高鏈路預測能力。

圖2 DynAEGRU的結構Fig.2 Structure of DynAEGRU

2.1 編碼器

本文將深度神經網絡和GRU 拼接到一個層中構成編碼器。在結構層，使用兩層神經網絡來捕捉節點的鄰域結構信息；在時態層，通過GRU 網絡分段學習節點的時態特征，并將結果拼接得到編碼器的嵌入輸出。

2.1.1 結構層

本文在結構層引入了一個簡單靈活的聚合函數f(X，A)用于圖的信息傳播。通過輸入一個t時刻的特征矩陣X和對稱的鄰接矩陣A，f(X，A)能夠輸出當前時刻的向量表示。t時刻的聚合函數定義為：

其中：i和j分別表示節點所在的行、列，代表圖中的兩個節點；X∈?n×k為節點輸入特征，n和k分別為t時刻圖中節點數和輸入特征維度；A∈?n×n是圖的鄰接矩陣，若i，j兩節點之間有邊，Ai，j=1，否則Ai，j=0。ReLU(x)=max(0，x)為激活函數，W0∈?k×m，W1∈?m×f分別為可學習參數矩陣，m和f分別為隱藏層、輸出層的特征維度；b1∈?m，b2∈?f分別為兩層神經網絡的偏置。

2.1.2 時態層

在動態圖中，一些交互存在長期依賴關系，這種依賴關系無法被全連接的神經網絡層捕捉到。因此在結構層輸出節點嵌入后，將其和過去節點的嵌入共同輸入到序列模型GRU 網絡中進行學習。

考慮到每一個時間步的節點數都在增加，因此在進行訓練網絡時根據每個時間步節點的數量分段執行GRU 網絡。通過定義一個函數：GRU(·)函數表示GRU 神經網絡，旨在學習每個時刻節點的時態信息，t時刻的時態層函數表達為：

其中：t表示當前時間步，Gt為t時刻的拓撲圖，Gti表示第ti個子圖，yVi表示第i個時間步所增加節點的向量表示。

此結構在每個時間步對每個新增節點進行GRU 訓練，目的是保留每個時間步的信息，并且通過更新門和重置門可以保留更有效的信息。

2.2 解碼器

解碼器通過編碼器學習到的前t個時間步的信息重建鄰接矩陣，即為預測t+1 時刻的拓撲圖。解碼器使用點積來重構原始圖，解碼過程表達為：

鄰接矩陣直接決定了圖的拓撲結構，所以此模型的目標就是使重構鄰接矩陣與原始鄰接矩陣盡可能地相似，將兩者對比構建損失函數，反向傳播更新參數，從而學習隱藏層節點的表示。將t時刻的損失定義為交叉熵損失函數：

其中：y表示t時刻原鄰接矩陣的標簽值，表示重構鄰接矩陣預測值，k表示元素個數，w0表示正例的權重。

在DynAEGRU 中，編碼器第一部分設計一個聚合函數f(X，A)通過使用At?Xt來聚集目標節點的鄰域信息；第二部分對網絡中節點分段使用GRU 網絡學習每個時間步新增節點的時態特征，并將結果拼接得到嵌入；最后在解碼器重構鄰接矩陣，與原鄰接矩陣對比構建損失最終學習節點向量表示。

算法1 動態網絡節點嵌入計算算法。

輸入 隨機值矩陣X1，時間步數T，每個時間步的鄰接矩陣{A1，A2，…，AT}，每個時間步增加節點數{V1，V2，…，VT}；輸出T時刻圖中的節點嵌入ZT。

3 實驗與分析

本文將在動態鏈路預測的基本任務上評估DynAEGRU學習節點表示好壞的能力，動態鏈路預測已被廣泛使用在評估動態網絡表示學習的算法［8，23］上。在此實驗中，將DynAEGRU 測試的性能與各種靜態和動態圖表示學習基線進行比較。

本文所進行的實驗與對比算法針對的數據集皆是無屬性圖，本文方法通過式（8）可以很容易地推廣到屬性圖上，簡單來說，本文方法采用的是隨機值作為嵌入初始化，屬性圖初始化嵌入同樣是通過隨機矩陣作為映射函數進行降維，最后得到的矩陣將作為節點嵌入，因此兩者達到的效果是一樣的。本文實驗更想突出的是圖的結構和時態信息，采用嵌入向量作為頂點的特征，在三個公開可用數據集上的實驗結果表明，DynAEGRU相比其他模型獲得了較高的性能提升。

3.1 實驗數據集

實驗使用的三個動態圖數據集詳細情況如表1 所示。由于動態圖通常包含連續的時間戳，本文實驗使用合適的時間窗口將數據分割成多個快照，這樣每個快照都有公平且合理的交互次數。

表1 實驗中的數據集Tab.1 Datasets in experiments

Email-uci［24］：該數據集包含的內容是在加州大學歐文分校的在線社交網絡平臺上，用戶之間在六個月時間內發送的私人信息。快照是使用其通信歷史創建的，時間窗口為10天。

Yelp［25］：該數據集使用第11 輪的Yelp 數據集挑戰賽，選擇評級數量最多的亞利桑那州的所有企業和一組選定的餐館類別。此外，只保留至少有15 個評級的用戶和企業。最后，此數據集使用6 個月的時間窗口提取2009 年至2015 年期間的12個快照。

ML_10M［26］：該數據集描述了電影用戶的標簽行為，以及用戶對其分級電影應用的標簽，用戶標簽鏈接將用戶與他們在某些電影上應用的標簽聯系起來。本文實驗中數據集使用3個月的時間窗口來提取3年中的13個快照。

3.2 實驗設置

實驗在動態圖中的鏈接預測任務上進行評估，學習多個快照圖上的動態節點表示{G1，G2，…，GT}，并在評估期間使用Gt預測Gt+1時的鏈接。將三個數據集中每個節點對正確分類為鏈接和非鏈接來比較它們。該模型使用前一個時間步的嵌入作為初始化當前時刻快照圖的向量表示，執行梯度訓練。

通過訓練動態鏈接預測的邏輯回歸分類器來評估不同模型的性能［7］。本文設置初始學習率為0.000 1，根據Gt+1中的鏈路和相等數量隨機抽樣的未連接節點對創建評估示例。本文使用20%的鏈接作為驗證集來調整模型的超參數，20%的鏈接進行訓練，剩下的60%作為本實驗的測試集。

3.3 評價指標

本文使用受試者工作特征（Receiver Operating Characteristic，ROC）曲線和ROC 曲線下方面積（Area Under ROC Curve，AUC）評分來評估鏈路預測的性能［6］。ROC 曲線是反映敏感性與特異性之間關系的曲線，可以直觀地判斷學習效果的好壞。AUC評分是衡量二分類模型優劣的一種評價指標，表示預測的準確性，AUC 值越高，即曲線越接近左上角說明預測準確率越高。該方法簡單、直觀，通過圖示能夠分析方法的準確性。

3.4 基線模型

將本文方法DynAEGRU 與幾種靜態圖和動態圖表示學習的算法進行比較，分析了使用時間信息進行動態鏈路預測的好處。為了與靜態圖表示學習算法進行公平的比較，通過構建一個直到時間t的聚合圖來提供對整個歷史快照圖的訪問。本文對所有基線使用原論文中作者提供的參數，并設置最終嵌入維數d=128。

第一，首先和幾種無監督靜態嵌入方法進行了比較：如node2vec、GraphSage［27］等。按照GraphSage原論文中的實驗設置，對鄰域信息使用平均、池化、LSTM 等聚合器，并報告每個數據集中評價最高的聚合器的性能。基于本文的動機，對比算法中使用同樣可以聚集鄰域結構信息的圖注意力機制（Graph Attention neTwork，GAT）［28］作為聚合器進行實驗，稱為GraphSage-GAT；并把GAT 作為自編碼器中的編碼器來進行實驗對比，表示為GAT-AE。

第二，與動態圖表示學習的最新研究做了比較。DynamicTriad 利用三元閉合過程生成一個圖的嵌入表示；DynGEM 利用深度編碼器模型，僅使用t-1時刻的快照圖，在t時刻生成動態圖的嵌入；DynAERNN 使用編碼器-解碼器結構，用LSTM 來編碼歷史信息；DySAT 模型是在每個快照圖上使用兩個注意力模塊分別學習結構嵌入和時態嵌入，最終通過二元交叉熵損失函數實現對圖中節點的學習。

3.5 實驗結果

本文用T個時間步中出現的節點對模型進行評估。從實驗結果中觀察到，與所有數據集的最佳基線相比，DynAEGRU實現了1～7 個百分點的AUC 評分增益。本文將DynAEGRU的性能調整為比其他算法相對更穩定，這種對比在所有數據集中都表現明顯。本文實驗在pytorch 中實現了DynAEGRU測試，并使用Adam優化器［29］進行訓練，實驗結果如表2所示。

表2 各算法在三個數據集上進行鏈路預測任務的實驗結果比較 單位：%Tab.2 Comparison of experimental results of different algorithms performing link prediction task on three datasets unit：%

此外，為了驗證本文提出的聚合函數和分段門控神經網絡兩部分的有效性，并了解它們分別學習了節點的哪方面信息，對DynAEGRU 進行了消融實驗，做法是獨立地去除編碼器中的結構層和時態層，從而創建更簡單的結構，稱DynAE為變體一，DynGRU 為變體二。分別對兩種變體使用和DynAEGRU 相同的損失函數、相同的數據集和相同的參數設置以準確比較兩種變體的學習能力。實驗對比了DynAEGRU、DynAE 和DynGRU 在三種數據集上做鏈路預測任務的AUC評分，結果如圖3所示。

圖3 DynAEGRU及兩種變體的AUC性能Fig.3 AUC performance of DynAEGRU and two variants

DynAEGRU、DynAE 和DynGRU 在三個數據集上的ROC曲線如圖4 所示。DynAEGRU 預測性能對變體一實現了3～9個百分點的AUC 增益效果。這表明本文提出的聚合函數可以很好地捕獲節點的鄰域結構信息，在變體一結構上加入GRU 網絡可以有效提取動態圖的時間演化信息，提高動態圖的鏈路預測性能。DynAE 模型結果表明隨著圖中節點的增加，變體一相對DynAEGRU 的增益效果逐漸降低，可以判斷節點數越多時，結構特征信息在目標節點信息中占據越來越大的比重。

圖4 Email-uci數據集上的ROCFig.4 ROC on Email-uci dataset

在實驗中選用上一個快照圖的嵌入表示作為當前節點向量表示的初始化值進行學習，因此學習到的向量表示更加穩定。DynGRU 模型用隨機值作為初始化向量表示，后期沒有用聚合器來捕獲鄰域特征，這導致節點幾乎不包含任何信息，因此在三個數據集上的AUC評分值均在0.7以下。這個結果表明圖中節點自身和鄰域屬性特征包含了大量信息，若缺少這部分信息，可能會導致學習預測能力降低，直接使用價值很低。

在Email-uci 和Yelp 數據集上發現，DynAEGRU 在面對網絡較稠密的情況時，有更好的表示學習能力，鏈路預測能力明顯強于其他基準模型，能高效地提取節點的結構特征信息。在ML_10M 數據集節點數較多的情況，DynAEGRU 的鏈路預測能力比其他兩個數據集提高很多；而DySAT 模型采用了雙自我注意力機制，在節點數較多但是更稀疏的數據集上可以取得更好的性能。可以觀察到DynAE 模型在節點數量較少但數據信息較為復雜的情況下，依然可以很好地學習節點的鄰域特征。

4 結語

本文提出了一種新的動態網絡表示學習方法DynAEGRU。針對對比算法在鏈路預測上的不足，DynAEGRU 方法在編碼器結構層使用深度神經網絡捕獲節點周圍的鄰域特征信息，時態層通過GRU 學習節點的時態依賴特征，并使用增量式的方法進行學習。本文在三個數據集上通過鏈路預測任務結果證明，本文定義的聚合函數可以準確捕捉節點的結構信息，而GRU 可以很好地聚集到節點的時態信息。實驗結果表明，DynAEGRU 在較稠密復雜的網絡中能很好地學習節點的嵌入。

雖然實驗是在沒有節點特征的圖上進行的，但是DynAEGRU 可以很容易地推廣到特征豐富的屬性圖上。在未來的研究中，將使用更復雜的數據集來使本文框架的連續時間一般化，并將其運用到解決更細粒度的時間變化上。