高亞男， 劉 勇，惠 麗

(黑龍江大學 計算機科學技術學院，哈爾濱 150080)

0 引 言

信息網絡是信息的重要表達形式，隨著大數據和深度學習技術的突飛猛進，人工智能研究正面臨新一輪的爆發(fā)式發(fā)展，能否對信息網絡做出有效合理的數據分析是當今學術研究的熱門話題。從宏觀意義上講，基于網絡的特征學習目的是尋找一種途徑可以有效探索整合網絡結構?；趫D的特征學習旨在將圖表示為微觀意義上的低維向量，同時保持圖結構。圖形分析旨在從圖形數據中挖掘有用的信息。表示學習了獲取數據表示。在構建分類器和其他預測變量時，容易提取有用的信息。有效的特征學習分析對于許多應用程序(例如節(jié)點分類和鏈接預測)很有用。通過分析社交網絡的用戶交互(例如微博中的評論/關注)情況，可以為用戶推薦朋友。

關于信息網絡的研究大都是在靜態(tài)網絡基礎上，而現(xiàn)實生活中不僅網絡拓撲會變化，網絡中的節(jié)點也會發(fā)生交互動作，這兩種動態(tài)的變化過程對網絡的表示學習有很重要意義，動態(tài)信息網絡表示學習問題近來越來越受關注。網絡的拓撲結構隨時間而變化，不斷建立新的關系，生成新的內容，并反映在節(jié)點屬性中[1]。同時，節(jié)點之間可能會頻繁發(fā)生交互，例如在社交網中節(jié)點之間通過邊的交互可理解為一次信息的傳達。生活中還有其他的很多交互模式，而這些動態(tài)的變化以及特征和屬性是靜態(tài)網絡不曾包含的，相比之下動態(tài)網絡更切合于實際，并且包含更多的網絡信息以及特性，更有力于模型的學習。因此，如何有效地建模和分析這些動態(tài)信息網是一個非常重要的研究課題。

基于動態(tài)信息網提出一種新穎的方法RSage，將RNN與GCN相結合，通過GCN對鄰居節(jié)點采樣、聚合來學習網絡的拓撲結構，而后利用RNN來學習網絡的時間序列屬性。得到的表征結果在3個真實數據集上實驗，得到較優(yōu)越的結果。

1 相關工作

深度學習浪潮引入了大量未經監(jiān)督和監(jiān)督的表征學習方法。動態(tài)表征方法的熱門之一是時間點過程，它利用時序點建模來學習動態(tài)網絡的時間屬性。Know-Evolve和DyRep將邊緣建模為點，使用神經網絡將節(jié)點作為輸入嵌入并參數化強度函數[2-3]。HTNE通過Hawkes時序點過程對網絡中節(jié)點進行時序建模，利用歷史節(jié)點對當前影響作用，來預測當前節(jié)點的表征，距離當前節(jié)點越遠的歷史節(jié)點影響力越小[4]。同時，它使用注意力機制來學習歸納歷史節(jié)點對當前節(jié)點的影響，該方法具有時間上的連續(xù)性，更有利于動態(tài)網絡表征學習。另一個動態(tài)表征方法的熱門類別是圖神經網絡(GNN)和循環(huán)神經網絡(RNN)的組合，利用GNN捕獲網絡拓撲結構，用RNN學習網絡中的時序特征。GNN通常使用的是圖卷積神經網絡(GCN)。GCRN提出兩種模型:①將網絡作為GCN輸入，得到初步節(jié)點表征，然后將其送入長短期記憶網絡(LSTM)中得到最終表征；②將GCN、LSTM進行融合，利用GCN來擴展LSTM，用GCN替換完全連接層，通過該方法直接得到最終結果[5]。在WD-GCN/CD-GCN和RgCNN中類似地探索了第一個想法[6-7]。STGCN提出由ST-Conv塊組成的復雜架構。這種結構被應用在時空交通數據(命名為STGCN和ST-Conv)上，其中使用圖卷積處理空間信息[8]。

2 預備知識

2.1 基本定義

動態(tài)網絡G可以表示為一組快照，既{G1,…,GT}，Gt=(V,Et,At)(t∈[1,T]) 為t時刻的快照，V為所有節(jié)點的集合且|V|=n，Et為t時的邊集合，At∈Rn×n為Gt在t時的鄰接矩陣，At(i,j)=1為vi和vj在t時刻有邊相連，反之At(i,j)=0為沒有邊。為了更好計算，默認本文所有動態(tài)網絡均為無向圖。

2.2 目標

給定一個動態(tài)網絡G，通過捕獲網絡的結構和演化來獲取動態(tài)網絡表征，即在得到低維節(jié)點表征向量ht：V→Rdh，ht∈Rn×dh。將ht向量用于節(jié)點分類、鏈路預測等任務。

2.3 圖卷積神經網絡

GraphSAGE[9]方法是在GCN基礎上擴展并改進，解決了GCN的局限性，并具有歸納性，它主要利用采樣鄰居節(jié)點信息、聚合鄰居節(jié)點信息來更新相應節(jié)點的表征，隨著周邊節(jié)點的改變，表征結果也可以學習到相應的變化。

算法 1: GraphSAGE 表征生成算法Input:圖Gt=V,Et,At ;深度K; 權重矩陣Wk,?k∈1,…,k ;非線性函數σ; 可微聚合函數AGGREGATEk,?k∈1,…,K ;鄰域函數N:v→2vOutput:表征向量 xv,所有v∈V1z0v←At,?v∈V;2fork =1…K do3forv∈V do4z0Nv ←AGGREGATEk zk-1u,?u∈Nv 5zkv←σWk·CONCATzk-1v,zkNv 6end7 zkv←zkv/zkv2,?∈V8end9 xv←zKv,?v∈V

2.4 循環(huán)神經網絡

循環(huán)神經網絡(RNN)是一種經典基于時間序列建模的方法，常用在含有時序屬性的各個領域的數據上建模。兩種經典RNN方法為長短期記憶網絡(LSTM)和門循環(huán)單元(GRU)。

2.4.1 長短期記憶網絡(RNN)

LSTM是一種特殊的RNN，可以有效防止梯度爆炸和梯度消失問題，同時克服了RNN無法處理遠距離依賴的問題。LSTM具體公式為

(1)

2.4.2 門循環(huán)單元(GRU)

GRU同樣很大程度上解決了RNN中的梯度消失問題，是LSTM的一種變體。GRU與LSTM在許多方面效果相近，但是結構相對更加簡單，具體公式為

(2)

圖1 RSage模型Fig.1 RSage model

3 方 法

提出了一種新方法RSage，分為RSage-LS和RSage-GRU兩個模型。由于GraphSAGE[9]的歸納性，該方法不僅適用于小規(guī)模數據，也可以應用在大規(guī)模動態(tài)網絡上，RSage架構見圖1。由圖1所見，GCN模型指的是GraphSAGE[9](GraphSAGE模型如圖中所示)，同時采用常用的LSTM、GRU兩種RNN模型。在t時刻輸入快照，利用GCN學習拓撲關聯(lián)結構，GCN通過采樣、聚合鄰居信息歸納出初步表征xt，用RNN學習到快照中隱含的時間信息，得到最終表征結果ht。

3.1 RSage-LS方法

將LSTM與GraphSAGE[9]結合。LSTM見式(1)，GraphSAGE[9]模型核心算法見算法1。RSage-LS公式為

(3)

其中，鄰接矩陣At為輸入；x(t)為GraphSAGE[9]得到的結果，后通過LSTM模型得到最終表征ht。

3.2 RSage-GRU方法

將GRU與GraphSAGE[9]模型結合。GRU見式(2)，GraphSAGE[9]模型核心算法見算法1。RSage-GRU公式為

(4)

其中，鄰接矩陣At為輸入；x(t)為GraphSAGE[9]得到的結果，后經過GRU模型得到最終表征ht。

4 實 驗

4.1 數據集

在3個可獲得公共的真實數據集上實驗(表1)。

4.1.1 Stochastic Block Model(SBM)

SBM是一種流行的隨機圖模型，用于模擬群落結構和進化。遵循Goyal Dyn GEM[10]模型來生成綜合數據。

4.1.2 UC Irvine message

UCI是一個來自加利福尼亞大學歐文分校學生的在線社區(qū)，其中該社交網絡的鏈接指示用戶之間發(fā)送的消息。

4.1.3 Elliptic

Elliptic是比特幣交易的網絡，其中每個節(jié)點代表一個交易，邊緣表示支付流量。 大約有20%的交易已映射到屬于合法類別而非非法類別的真實實體。目的是對未貼標簽的交易進行分類。

表1 數據集Table 1 Data sets

4.2 對比方法

本文將RSage方法與以下5種方法作對比。

DynGEM[10]：基于圖自動編碼器的無監(jiān)督節(jié)點嵌入方法，可減少重建損失以及嵌入節(jié)點之間的距離空間，它的一個特點是架構的深度適應圖的大??；同時利用歷史學習到的參數對當前模型初始化訓練。以加快學習速度。

EvolveGCN[11]：利用RNN對GCN進行了擴展。在該模型中，GCN主要用來學習網絡的拓撲結構特征，RNN用來學習時序特征并對GCN的權重進行更新，同時GCN和RNN共同參與更新節(jié)點表征。

GCN-GRU[12]：GCN模型與節(jié)點嵌入的遞歸模型(GRU)共同訓練。將這種方法稱為GCN-GRU，它在概念上與文獻[12]的方法1相同，只是它們的GNN是ChebNet[13],而遞歸模型是LSTM，用GCN、GRU分別替換原文中GNN、LSTM方法。

GCN[13]：采用沒有任何時間建模的GCN。對于所有時間步長，使用一個單一的GCN模型，并且損失沿時間軸累積。

4.3 任務

4.3.1 節(jié)點分類

由表2可見，RSage-LS方法在節(jié)點分類任務上的表現(xiàn)略優(yōu)越于其他方法，通過采樣、聚合鄰居信息來歸納表征，當網絡規(guī)模較大時，可以采樣到的信息和特征更多，效果就會更好。

表2 節(jié)點分類結果

4.3.2 鏈路預測

由表3可見，RSage在兩個小規(guī)模數據集上的表現(xiàn)一般。小規(guī)模網絡一般比較稀疏，對于鄰居信息來說可用的信息較少，本文方法在兩個小規(guī)模網絡上得到的結果并非十分理想。

表3 鏈路預測結果Table 3 Results for link prediction

5 結 論

提出的方法主要針對邊增加、邊減少情況的信息網，將GCN和RNN結合，利用了2種方法各自的特點來學習節(jié)點表征，首先將動態(tài)網絡分割成多個快照，以快照的形式作為輸入，利用GCN捕獲快照的拓撲信息，用RNN學習網絡的時間維度。在3個真實數據集上實驗，實驗結果顯示，該方法在大規(guī)模數據上具有較好的表現(xiàn)。