高亞男， 劉 勇，惠 麗

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

0 引 言

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

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

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

1 相關工作

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

2 預備知識

2.1 基本定義

動態(tài)網(wǎng)絡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)網(wǎng)絡均為無向圖。

2.2 目標

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

2.3 圖卷積神經(jīng)網(wǎng)絡

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

算法 1: GraphSAGE 表征生成算法Input:圖Gt=V,Et,At ;深度K; 權(quán)重矩陣Wk,?k∈1,…,k ;非線性函數(shù)σ; 可微聚合函數(shù)AGGREGATEk,?k∈1,…,K ;鄰域函數(shù)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)神經(jīng)網(wǎng)絡

循環(huán)神經(jīng)網(wǎng)絡(RNN)是一種經(jīng)典基于時間序列建模的方法，常用在含有時序?qū)傩缘母鱾€領域的數(shù)據(jù)上建模。兩種經(jīng)典RNN方法為長短期記憶網(wǎng)絡(LSTM)和門循環(huán)單元(GRU)。

2.4.1 長短期記憶網(wǎng)絡(RNN)

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

(1)

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

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

(2)

圖1 RSage模型Fig.1 RSage model

3 方 法

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

3.1 RSage-LS方法

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

(3)

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

3.2 RSage-GRU方法

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

(4)

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

4 實 驗

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

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

4.1.1 Stochastic Block Model(SBM)

SBM是一種流行的隨機圖模型，用于模擬群落結(jié)構(gòu)和進化。遵循Goyal Dyn GEM[10]模型來生成綜合數(shù)據(jù)。

4.1.2 UC Irvine message

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

4.1.3 Elliptic

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

表1 數(shù)據(jù)集Table 1 Data sets

4.2 對比方法

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

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

EvolveGCN[11]：利用RNN對GCN進行了擴展。在該模型中，GCN主要用來學習網(wǎng)絡的拓撲結(jié)構(gòu)特征，RNN用來學習時序特征并對GCN的權(quán)重進行更新，同時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)越于其他方法，通過采樣、聚合鄰居信息來歸納表征，當網(wǎng)絡規(guī)模較大時，可以采樣到的信息和特征更多，效果就會更好。

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

4.3.2 鏈路預測

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

表3 鏈路預測結(jié)果Table 3 Results for link prediction

5 結(jié) 論

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