劉 超,韓 銳,劉小洋,黃賢英

(重慶理工大學 計算機科學與工程學院，重慶 400054)

0 引言

微博、微信、Facebook等在線社交平臺的出現(xiàn)，為信息的傳遞與共享提供了巨大的便利，從而促進了信息的快速傳播，并因此產(chǎn)生了信息級聯(lián)現(xiàn)象。這種現(xiàn)象普遍存在于: 論文與博客引用[1-2]，電子郵件轉(zhuǎn)發(fā)[3]，以及各種社交平臺推文的轉(zhuǎn)發(fā)(如新浪微博[4]和Twitter[5])中。信息級聯(lián)預測能夠預測信息級聯(lián)的大小和廣度，并可以控制(或加速)各種場景中的信息傳播，可應用于企業(yè)的病毒式營銷[6]、社交網(wǎng)絡影響力最大化[7]、媒體定點投放廣告[8]和虛假新聞檢測[9-10]等領域。因此，信息級聯(lián)預測已成為社交網(wǎng)絡分析領域的研究熱點。

目前信息級聯(lián)預測方法可歸納為四類: 基于擴散的方法[11-12]，基于特征的方法[13]，基于生成建模的方法[4]和基于深度學習的方法[5,14]?；谏疃葘W習的方法是目前預測最高效的方法，該方法通常將數(shù)據(jù)通過嵌入表示學習提取節(jié)點的特征，再利用神經(jīng)網(wǎng)絡自動學習節(jié)點的特征，最后進行預測輸出。DeepCas[5]是第一個基于深度學習的信息級聯(lián)模型，通過隨機游走將級聯(lián)圖轉(zhuǎn)換為節(jié)點序列，并自動學習各個圖的表示，然后使用循環(huán)神經(jīng)網(wǎng)絡學習級聯(lián)的時序信息。DeepHawkes[4]將級聯(lián)圖轉(zhuǎn)換為擴散路徑，然后使用Hawkes過程學習級聯(lián)特征，使模型具有高度可解釋性。Topo-LSTM[15]利用動態(tài)有向無環(huán)圖DAG以及每個節(jié)點生成拓撲感知的嵌入來進行預測。CasCN[14]模型利用圖卷積[16]網(wǎng)絡嵌入級聯(lián)子圖的空間結構信息，再使用循環(huán)神經(jīng)網(wǎng)絡提取時序信息，再進行輸出預測。

雖然上述模型能夠預測信息級聯(lián)，但是這些模型對級聯(lián)數(shù)據(jù)時序特征和空間拓撲結構利用不全面。文獻[4-5]利用了信息級聯(lián)的時序特征，忽略了空間特征;文獻[15]考慮了信息級聯(lián)的空間拓撲結構，但卻忽略了時序信息。文獻[14]因考慮了信息級聯(lián)的時序信息和空間拓撲結構，故實驗效果優(yōu)于文獻[4-5,15]，但在捕獲時序信息時會丟失部分空間拓撲結構，因而對最終的預測精度產(chǎn)生影響。由此可見，現(xiàn)有預測模型沒有實現(xiàn)時序信息與空間拓撲結構的有效耦合，制約了模型的預測效果。

針對以上不足，本文提出一個端到端的深度學習模型，為了有效地捕獲級聯(lián)信息的時序和空間拓撲結構特征，先捕獲信息級聯(lián)的空間拓撲結構，然后在時序信息的傳播過程中同時演變空間拓撲結構，最后利用注意力機制將時序信息和空間結構信息輸出的特征進行耦合。因為級聯(lián)圖的大小不同，容易忽略一些邊緣信息，而且各個邊緣的權重不一致，導致對全局結構的嵌入不全面，采用注意力機制實現(xiàn)特征耦合，有偏重地提取邊緣特征信息。

本文主要貢獻如下:

(1) 引入了時空注意力機制，實現(xiàn)了級聯(lián)圖的時序信息與空間結構信息捕獲后的耦合，使模型適用于不同的圖結構、時序信息。

(2) 在利用雙向循環(huán)神經(jīng)網(wǎng)絡捕獲時序信息的同時，采用圖卷積網(wǎng)絡捕獲級聯(lián)信息的空間結構信息，能更好地捕獲時序特征和空間結構特征。

(3) 提出一種新的面向社交網(wǎng)絡的信息級聯(lián)預測模型，與傳統(tǒng)基于循環(huán)網(wǎng)絡的信息級聯(lián)預測模型相比，ICP模型的級聯(lián)預測精度更高。

1 相關工作

1.1 圖卷積網(wǎng)絡

圖卷積網(wǎng)絡(GCN[16])通過計算圖的拉普拉斯特征分解，從節(jié)點間的信息傳遞或等效的某些鄰域聚合功能中提取高級特征再進行傅立葉域中的卷積運算，提升各種圖任務的執(zhí)行效果。隨著圖卷積網(wǎng)絡的發(fā)展，先前的一些工作將圖卷積網(wǎng)絡應用于信息級聯(lián)，利用其特性挖掘級聯(lián)信息的空間拓撲結構信息。在文獻[14,17]中，利用圖卷積網(wǎng)絡提取級聯(lián)信息的空間拓撲信息，用于預測信息級聯(lián)。

1.2 注意力機制

注意力機制在許多機器學習任務中都展示了顯著的效果，如圖像字幕[18]、視頻字幕[19]和機器翻譯[20]。注意力機制對重點關注鄰域分配更多的注意力資源以獲取更多所需要的特征信息，抑制其他的無用信息，從而取得更好的效果。文獻[5]中，采用注意力機制計算級聯(lián)序列的權重，更準確地預測級聯(lián)信息。文獻[21]采用注意力機制探索用戶與用戶間隱式的級聯(lián)擴散，從而實現(xiàn)預測級聯(lián)信息。注意力的關鍵思想是學習一組分配注意權重(將總和求歸一化): 較高(較低)的權重表示相應的功能對于最終任務提供較多(較少)的信息。

2 模型介紹

本文提出一個端到端的深度學習面向社交網(wǎng)絡的ICP模型，采用級聯(lián)子圖Ci(t)作為輸入，預測推文pi在Δt時間內(nèi)傳播的增量ΔSi。ICP模型由4個組件組成，首先，從級聯(lián)圖中對子圖節(jié)點進行采樣并生成鄰接矩陣序列；然后，將觀察時間窗口內(nèi)的鄰接矩陣序列和級聯(lián)圖的結構信息輸入到Bi-LSTM網(wǎng)絡；再將Bi-LSTM得到的表示輸入到注意力機制，耦合時間序列和空間結構特征，再輸入衰減函數(shù)，得到符合時間衰減效應的特征表示；最后，使用全連接層輸出進行預測。

2.1 問題定義

圖1 級聯(lián)圖

表1 符號定義表

2.2 節(jié)點嵌入層

推文pi觀察到的級聯(lián)圖Ci(t)，將其表示為鄰接矩陣形式，并為每個節(jié)點加入自環(huán)，如圖2所示。然后根據(jù)級聯(lián)圖Ci(t)中每個節(jié)點的到達時刻進行獨熱編碼(One-Hot Code)表示節(jié)點特征。將觀察窗口[0,T)劃分為l個不相交的細粒度時間間隔{[t0=0,t1),[t1,t2),…,[tl-1,tl=T)}，然后再對每個時間間隔進行編碼。

圖2 級聯(lián)子圖序列的采樣表示

(1)

為了捕獲級聯(lián)信息在傳播過程中的空間結構信息，采用圖卷積網(wǎng)絡來學習嵌入[22]。信息擴散過程類似于馬爾科夫過程，即經(jīng)擴散一段時間后會收斂于一個穩(wěn)定的分布，類似于分布[23]。因此，設級聯(lián)的拉普拉斯矩陣Δc，符合級聯(lián)圖的隨機游走特征，設馬爾科夫狀態(tài)轉(zhuǎn)移概率矩陣P=D-1A，且存在φi={φ1,φ2,…,φn}滿足φTP=φT。根據(jù)圖卷積網(wǎng)絡[16]公式:

(2)

可得拉普拉斯矩陣Δc:

(3)

其中，D表示級聯(lián)圖的度矩陣，K表示捕獲的鄰域?qū)訑?shù)，

2.3 圖卷積與雙向循環(huán)神經(jīng)網(wǎng)絡層

圖3 模型框架圖

(6)

(7)

(8)

2.4 注意力機制

(11)

2.5 輸出預測層

先前研究發(fā)現(xiàn)，信息級聯(lián)存在著時間衰減效應，即一個節(jié)點對其他節(jié)點的影響會隨著時間的推移而減小[24]。本文采用非參數(shù)化時間衰減函數(shù)λf(T-ti)，根據(jù)文獻[4]得:

(12)

ICP模型最后一部分是由全連接層(MLP)組成。根據(jù)前面計算得到的h′t，可計算出ΔSi，如式(13)所示。

ΔSi=MLP(h′t)

(13)

最終任務是預測指定時間間隔內(nèi)信息傳播的增量，引入均方對數(shù)誤差(Mean Square Log-Transformed Error, MSLE)，即:

(14)

作為損失函數(shù)loss，使用Adam優(yōu)化器優(yōu)化loss值，使其達到最優(yōu)(最小)。

算法1 ICP算法

2: repeat3: for鄰接矩陣序列ATi和對應的拉普拉斯矩陣Δci do4: 根據(jù)式(6) ～ 式(8)得ht←Bi-LSTM(*G(ATi,Δci))5: 根據(jù)式(9) ～ 式(11)得hat←Attention(ht)6: 根據(jù)式(12)得h't←Aggregate(λf(T-tji)hat)7: 根據(jù)式(13)得ΔSi←MLP(h't)8: 根據(jù)式(14)得使用Adam優(yōu)化器對參數(shù)進行優(yōu)化9: end for10: until convergence;

3 實驗

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

為了評估ICP模型在信息級聯(lián)預測中的有效性和擴展性，本文使用公開數(shù)據(jù)集進行實驗并與先前的研究進行比較。數(shù)據(jù)集的數(shù)據(jù)信息統(tǒng)計見表2。

表2 數(shù)據(jù)集信息統(tǒng)計表

Weibo[4]: 此數(shù)據(jù)集是選取新浪微博在2016年6月1日生成的所有原始帖子，并跟蹤接下來24小時內(nèi)每個帖子的所有轉(zhuǎn)發(fā)，總共包括119 313條貼文。圖4(a)顯示了級聯(lián)大小的分布情況；圖5(a)展示了級聯(lián)的流行情況，顯示24h后，流行達到飽和。本文遵循與CasCN[14]相似的設置，即觀察時間窗口T=1, 2, 3h。最后，根據(jù)預處理后的層疊時間對層疊進行排序，并為層疊選擇前70%的層疊為訓練集，剩下的平均分為驗證集和測試集。

HEP-PH[25]: HEP-PH數(shù)據(jù)集(高能物理現(xiàn)象學數(shù)據(jù)集)來自電子版arXiv論文引用網(wǎng)絡，數(shù)據(jù)涵蓋了1993年1月至2003年4月(124個月)期間的論文，其中有34 546篇論文的所有引文。如果論文i引用論文j，則論文引用圖包含從i到j的有向邊。如果論文引用了數(shù)據(jù)集之外的論文或被其引用，則該圖將不包含有關此信息。圖4(b)顯示了級聯(lián)大小的分布情況,圖5(b)展示了級聯(lián)的流行情況。對于觀察窗口，選擇T=3, 5, 7a，分別對應流行度達到最終規(guī)模的50%，60%和70%，如圖5(b)所示。然后，收集70%的級聯(lián)用于訓練，其余平均拆分為驗證集和測試集。

圖4 級聯(lián)尺寸分布圖X軸為級聯(lián)大小，Y軸表示不同級聯(lián)大小對應的數(shù)量

圖5 時間和級聯(lián)數(shù)之間的百分比分布

3.2 實驗環(huán)境和參數(shù)設置

本文所有實驗在Ubuntu 16操作系統(tǒng)，Intel Core I9-9980XE CPU，128GB內(nèi)存和NVIDIA TiTan RTX(24GB)顯卡上進行。

對于DeepCas、DeepHawkes、Topo-LSTM和CasCN，參照DeepCas[5]設置用戶的嵌入維度是50，循環(huán)神經(jīng)網(wǎng)絡每層的隱藏單元數(shù)是32，全連接層的隱藏單元數(shù)分別是32和16，用戶學習率為5×10-4，其他學習率為5×10-3。每次迭代的批處理大小為32，當連續(xù)50次迭代，驗證集的loss沒有下降，模型訓練過程將停止。Weibo數(shù)據(jù)集的時間間隔設置為10min，HEP-PH的時間間隔設置為2個月。

本文采用Tensorflow來實現(xiàn)ICP模型，并使用Adam優(yōu)化器通過梯度下降來優(yōu)化參數(shù)。除圖表示學習的嵌入鄰域?qū)硬捎肒=2外，其余模型參數(shù)設置與上述模型保持一致。

3.3 評估指標

根據(jù)現(xiàn)有的工作，在實驗中選擇標準評估指標——MSLE[見式(14)]來評估鏈接準確性。請注意，MSLE越小，其預測性能越好。

3.4 模型對比

3.4.1 基準版性能對比

將用本文所提出ICP模型的基準版，在真實的數(shù)據(jù)集上與先前級聯(lián)預測模型進行實驗對比。

DeepCas[5]是第一個用于信息級聯(lián)預測的深度學習體系結構，其表示級聯(lián)圖為一組隨機行走路徑，并通過雙向GRU神經(jīng)網(wǎng)絡通過管道傳輸，并帶有注意力機制來預測級聯(lián)的大小。它主要利用結構和節(jié)點身份的信息進行預測。

DeepHawkes[4]模型將端到端深度學習的預測能力集成到Hawkes過程的可解釋因素中，以進行流行度預測。深度學習方法與級聯(lián)動力學建模過程之間的結合彌合了信息級聯(lián)預測和理解之間的鴻溝。該方法既屬于生成方法又屬于基于深度學習的方法。

Topo-LSTM[15]是有向無環(huán)圖結構(DAG結構)RNN，將動態(tài)DAG作為輸入，并為DAG中的每個節(jié)點生成拓撲感知的嵌入作為輸出，從而預測下一個節(jié)點。

CasCN[14]模型結合了結構和時間的深度學習框架，利用圖卷積網(wǎng)絡捕獲網(wǎng)絡空間結構信息，通過循環(huán)神經(jīng)網(wǎng)絡合并了時間衰減函數(shù)實現(xiàn)時間信息的更有效利用。該模型是一種深度學習的方法。

表3總結了Weibo和HEP-PH數(shù)據(jù)集上ICP模型和其他模型基準版之間的性能比較。ICP模型與DeepCas對比，證明僅嵌入節(jié)點作為圖表示是不夠的，不能將圖表示為一組隨機路徑。因DeepCas未能考慮時序信息和級聯(lián)圖的拓撲結構，導致其性能比其他基于深度學習方法要差。Topo-LSTM也缺乏對時序信息的處理，導致其性能也較差。DeepHawkes雖然以生成方式對級聯(lián)進行建模，但由于其學習結構信息的能力較弱，因此無法發(fā)揮最佳性能。CasCN考慮了時序信息與空間拓撲結構，但忽略了二者特征之間的融合。最后，本文提出的ICP模型在兩個數(shù)據(jù)集上的信息級聯(lián)預測(推文轉(zhuǎn)發(fā)和論文引用)，效果明顯優(yōu)于其他模型。如在Weibo數(shù)據(jù)集中觀察1、2、3h，MSLE值分別為2.123,2.012,1.776；在HEP-PH數(shù)據(jù)集中觀察3、5、7a，MSLE值分別為0.939, 0.843, 0.812，取得了較好的預測效果。與CasCN相比，本文提出的ICP模型預測誤差分別降低了5.31%,1.18%,7.31%和6.47%,8.07%,8.46%，從而證實了模型的有效性。

表3 性能對比表(MSLE)

3.4.2 時空注意力對信息級聯(lián)的影響

首先驗證注意力機制的有效性，設計消融實驗。構建一個ICP的刪減版ICP-LSTM，即將基準版中的Bi-LSTM替換為LSTM，然后與CasCN進行比較，等價于ICP-LSTM是在CasCN模型的基礎上添加了注意力機制。在實驗過程中，二者參數(shù)一致，驗證采樣的鄰域?qū)訑?shù)K=1,2時的實驗效果如表4所示。

表4 注意力機制影響級聯(lián)預測性能對比表(MSLE)

表4中給出了嵌入層K=1,2與CasCN模型K=2的性能對比。根據(jù)表4可以看出，當K=2時，本文提出的ICP模型優(yōu)于CasCN模型，這是因為添加了注意力機制，能夠耦合時序信息與空間結構信息。當K=1時，在Weibo中觀察2h，ICP-LSTM的MSLE大于CasCN，是由于K=1，采取的空間結構信息不足，導致結果略低。

然后，驗證時序信息對級聯(lián)預測的影響，將ICP的變體ICP-BiLSTM與CasCN進行對比分析(ICP-BiLSTM為本文提出的ICP模型去掉注意力機制，也等價于將CasCN模型中LSTM網(wǎng)絡替換為BiLSTM網(wǎng)絡所產(chǎn)生的模型)。通過表5數(shù)據(jù)可以看出，當K=2時，Weibo觀察3h的MSLE=1.783和HEP-PH觀察7a的MSLE=0.84，優(yōu)于CasCN的MSLE，從而證實時序信息在信息級聯(lián)中的重要性。

表5 時序網(wǎng)絡影響級聯(lián)預測性能對比表(MSLE)

最后，驗證時序信息和空間信息對級聯(lián)預測的影響，在CasCN的基礎上使用Bi-LSTM并添加注意力機制，再調(diào)整嵌入的鄰域?qū)訑?shù)K分別與CasCN進行比較。通過表6的數(shù)據(jù)可以看出，在Weibo和HEP-PH數(shù)據(jù)集上K=1,2時，MSLE值均小于CasCN的MSLE值，表明本文提出的模型優(yōu)于CasCN，對時序信息和空間拓撲信息的捕獲更全面，從而提升了模型的效率，降低了損失率。

表6 時序空間影響級聯(lián)預測性能對比表(MSLE)

上述實驗表明，時序信息和空間結構信息對信息級聯(lián)預測效果有重要影響。二者結合，能更好地保證預測的準確率。使用注意力機制耦合二者數(shù)據(jù)，使模型對時序信息和空間結構信息的捕獲更加全面，也使模型更具有泛化力。

3.5 模型優(yōu)化

本文注意力機制的主要思想源自于自注意力機制，可采用比自注意力機制耦合效果更優(yōu)的方法。例如，可以采用多頭注意力機制來替換文中的注意力機制，提出了ICP的變體ICP-Mhead。表7給出了在相同參數(shù)下CasCN、ICP與ICP-Mhead實驗對比結果。可以得出，ICP-MHead模型的MSLE值均小于CasCN模型和ICP模型的MSLE值，表明使用多頭注意力的效果明顯優(yōu)于CasCN模型。因為多頭注意力機制采用多個頭部去捕獲特征信息，從而可以捕獲更多的邊緣信息(被忽略的時序信息和空間拓撲結構)，使得提取的特征更加全面，故ICP-MHead模型優(yōu)于ICP模型。

表7 多頭注意力機制影響級聯(lián)預測性能對比表(MSLE)

3.6 模型收斂性

本節(jié)對ICP-LSTM，ICP-BiLSTM，ICP-MHead與ICP的收斂性進行分析，實驗結果如圖6所示。

圖6中，可以看出，ICP-LSTM經(jīng)過100輪迭代之后基本擬合，平均用時約7h；ICP-BiLSTM經(jīng)過80次迭代之后基本擬合，平均用時約8h；ICP-MHead經(jīng)過120輪迭代之后基本擬合，平均用時約12h。ICP經(jīng)過50輪迭代之后基本擬合，平均用時約9h。ICP-MHead與ICP所采用Bi-LSTM和注意力機制導致訓練時間較長，但模型的預測指標更高且訓練時間在可接受范圍內(nèi)。

圖6 ICP模型驗證集Loss

圖6 (續(xù))

4 總結

本文提出端到端的深度學習ICP模型實現(xiàn)信息級聯(lián)預測。在深度學習框架下，首先利用圖卷積網(wǎng)絡提取級聯(lián)信息的空間結構特征，再利用雙向循環(huán)神經(jīng)網(wǎng)絡提取時序特征，然后使用注意力機制耦合空間結構特征和時序特征，最后，在結合級聯(lián)的時間衰減效應進一步提高模型的預測準確性。本文在兩個公開數(shù)據(jù)集上進行實驗，結果表明，本文提出的基于時空注意力的社交網(wǎng)絡ICP模型預測精度高于先前的方法。

下一步在空間結構與時序信息相結合的基礎上，引入點過程建模，使得模型更具有可解釋性，提高模型的預測能力。