基于循環(huán)采樣聚合鄰居信息的動態(tài)網(wǎng)絡(luò)表征方法

高亞男， 劉 勇，惠 麗

(黑龍江大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，哈爾濱 150080)

0 引 言

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

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

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

1 相關(guān)工作

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

2 預(yù)備知識

2.1 基本定義

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

2.2 目標(biāo)

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

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

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

算法 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)絡(luò)

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

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

LSTM是一種特殊的RNN，可以有效防止梯度爆炸和梯度消失問題，同時(shí)克服了RNN無法處理遠(yuǎn)距離依賴的問題。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兩個(gè)模型。由于GraphSAGE[9]的歸納性，該方法不僅適用于小規(guī)模數(shù)據(jù)，也可以應(yīng)用在大規(guī)模動態(tài)網(wǎng)絡(luò)上，RSage架構(gòu)見圖1。由圖1所見，GCN模型指的是GraphSAGE[9](GraphSAGE模型如圖中所示)，同時(shí)采用常用的LSTM、GRU兩種RNN模型。在t時(shí)刻輸入快照，利用GCN學(xué)習(xí)拓?fù)潢P(guān)聯(lián)結(jié)構(gòu)，GCN通過采樣、聚合鄰居信息歸納出初步表征xt，用RNN學(xué)習(xí)到快照中隱含的時(shí)間信息，得到最終表征結(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 實(shí) 驗(yàn)

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

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

4.1.1 Stochastic Block Model(SBM)

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

4.1.2 UC Irvine message

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

4.1.3 Elliptic

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

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

4.2 對比方法

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

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

EvolveGCN[11]：利用RNN對GCN進(jìn)行了擴(kuò)展。在該模型中，GCN主要用來學(xué)習(xí)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特征，RNN用來學(xué)習(xí)時(shí)序特征并對GCN的權(quán)重進(jìn)行更新，同時(shí)GCN和RNN共同參與更新節(jié)點(diǎn)表征。

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

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

4.3 任務(wù)

4.3.1 節(jié)點(diǎn)分類

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

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

4.3.2 鏈路預(yù)測

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

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

5 結(jié) 論

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