李慧博，趙云霄，白 亮*

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

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

0 引言

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

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

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

1）提出了一種新的動態(tài)網(wǎng)絡學習方法——DynAEGRU，該方法可以有效捕獲節(jié)點的結構和時態(tài)特征信息；

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

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

1 相關工作

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

1.1 圖表示學習

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

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

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

1.2 自編碼器

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

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

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

1.3 門控循環(huán)單元

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

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

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

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

2 DynAEGRU結構

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

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

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

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

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

2.1 編碼器

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

2.1.1 結構層

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

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

2.1.2 時態(tài)層

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

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

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

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

2.2 解碼器

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

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

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

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

算法1 動態(tài)網(wǎng)絡節(jié)點嵌入計算算法。

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

3 實驗與分析

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

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

3.1 實驗數(shù)據(jù)集

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

表1 實驗中的數(shù)據(jù)集Tab.1 Datasets in experiments

Email-uci［24］：該數(shù)據(jù)集包含的內容是在加州大學歐文分校的在線社交網(wǎng)絡平臺上，用戶之間在六個月時間內發(fā)送的私人信息?？煺帐鞘褂闷渫ㄐ艢v史創(chuàng)建的，時間窗口為10天。

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

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

3.2 實驗設置

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

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

3.3 評價指標

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

3.4 基線模型

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

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

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

3.5 實驗結果

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

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

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

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

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

圖4 Email-uci數(shù)據(jù)集上的ROCFig.4 ROC on Email-uci dataset

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

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

4 結語

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

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