劉 超,韓 銳,劉小洋,黃賢英
(重慶理工大學(xué) 計算機(jī)科學(xué)與工程學(xué)院,重慶 400054)
微博、微信、Facebook等在線社交平臺的出現(xiàn),為信息的傳遞與共享提供了巨大的便利,從而促進(jìn)了信息的快速傳播,并因此產(chǎn)生了信息級聯(lián)現(xiàn)象。這種現(xiàn)象普遍存在于: 論文與博客引用[1-2],電子郵件轉(zhuǎn)發(fā)[3],以及各種社交平臺推文的轉(zhuǎn)發(fā)(如新浪微博[4]和Twitter[5])中。信息級聯(lián)預(yù)測能夠預(yù)測信息級聯(lián)的大小和廣度,并可以控制(或加速)各種場景中的信息傳播,可應(yīng)用于企業(yè)的病毒式營銷[6]、社交網(wǎng)絡(luò)影響力最大化[7]、媒體定點(diǎn)投放廣告[8]和虛假新聞檢測[9-10]等領(lǐng)域。因此,信息級聯(lián)預(yù)測已成為社交網(wǎng)絡(luò)分析領(lǐng)域的研究熱點(diǎn)。
目前信息級聯(lián)預(yù)測方法可歸納為四類: 基于擴(kuò)散的方法[11-12],基于特征的方法[13],基于生成建模的方法[4]和基于深度學(xué)習(xí)的方法[5,14]?;谏疃葘W(xué)習(xí)的方法是目前預(yù)測最高效的方法,該方法通常將數(shù)據(jù)通過嵌入表示學(xué)習(xí)提取節(jié)點(diǎn)的特征,再利用神經(jīng)網(wǎng)絡(luò)自動學(xué)習(xí)節(jié)點(diǎn)的特征,最后進(jìn)行預(yù)測輸出。DeepCas[5]是第一個基于深度學(xué)習(xí)的信息級聯(lián)模型,通過隨機(jī)游走將級聯(lián)圖轉(zhuǎn)換為節(jié)點(diǎn)序列,并自動學(xué)習(xí)各個圖的表示,然后使用循環(huán)神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)級聯(lián)的時序信息。DeepHawkes[4]將級聯(lián)圖轉(zhuǎn)換為擴(kuò)散路徑,然后使用Hawkes過程學(xué)習(xí)級聯(lián)特征,使模型具有高度可解釋性。Topo-LSTM[15]利用動態(tài)有向無環(huán)圖DAG以及每個節(jié)點(diǎn)生成拓?fù)涓兄那度雭磉M(jìn)行預(yù)測。CasCN[14]模型利用圖卷積[16]網(wǎng)絡(luò)嵌入級聯(lián)子圖的空間結(jié)構(gòu)信息,再使用循環(huán)神經(jīng)網(wǎng)絡(luò)提取時序信息,再進(jìn)行輸出預(yù)測。
雖然上述模型能夠預(yù)測信息級聯(lián),但是這些模型對級聯(lián)數(shù)據(jù)時序特征和空間拓?fù)浣Y(jié)構(gòu)利用不全面。文獻(xiàn)[4-5]利用了信息級聯(lián)的時序特征,忽略了空間特征;文獻(xiàn)[15]考慮了信息級聯(lián)的空間拓?fù)浣Y(jié)構(gòu),但卻忽略了時序信息。文獻(xiàn)[14]因考慮了信息級聯(lián)的時序信息和空間拓?fù)浣Y(jié)構(gòu),故實驗效果優(yōu)于文獻(xiàn)[4-5,15],但在捕獲時序信息時會丟失部分空間拓?fù)浣Y(jié)構(gòu),因而對最終的預(yù)測精度產(chǎn)生影響。由此可見,現(xiàn)有預(yù)測模型沒有實現(xiàn)時序信息與空間拓?fù)浣Y(jié)構(gòu)的有效耦合,制約了模型的預(yù)測效果。
針對以上不足,本文提出一個端到端的深度學(xué)習(xí)模型,為了有效地捕獲級聯(lián)信息的時序和空間拓?fù)浣Y(jié)構(gòu)特征,先捕獲信息級聯(lián)的空間拓?fù)浣Y(jié)構(gòu),然后在時序信息的傳播過程中同時演變空間拓?fù)浣Y(jié)構(gòu),最后利用注意力機(jī)制將時序信息和空間結(jié)構(gòu)信息輸出的特征進(jìn)行耦合。因為級聯(lián)圖的大小不同,容易忽略一些邊緣信息,而且各個邊緣的權(quán)重不一致,導(dǎo)致對全局結(jié)構(gòu)的嵌入不全面,采用注意力機(jī)制實現(xiàn)特征耦合,有偏重地提取邊緣特征信息。
本文主要貢獻(xiàn)如下:
(1) 引入了時空注意力機(jī)制,實現(xiàn)了級聯(lián)圖的時序信息與空間結(jié)構(gòu)信息捕獲后的耦合,使模型適用于不同的圖結(jié)構(gòu)、時序信息。
(2) 在利用雙向循環(huán)神經(jīng)網(wǎng)絡(luò)捕獲時序信息的同時,采用圖卷積網(wǎng)絡(luò)捕獲級聯(lián)信息的空間結(jié)構(gòu)信息,能更好地捕獲時序特征和空間結(jié)構(gòu)特征。
(3) 提出一種新的面向社交網(wǎng)絡(luò)的信息級聯(lián)預(yù)測模型,與傳統(tǒng)基于循環(huán)網(wǎng)絡(luò)的信息級聯(lián)預(yù)測模型相比,ICP模型的級聯(lián)預(yù)測精度更高。
圖卷積網(wǎng)絡(luò)(GCN[16])通過計算圖的拉普拉斯特征分解,從節(jié)點(diǎn)間的信息傳遞或等效的某些鄰域聚合功能中提取高級特征再進(jìn)行傅立葉域中的卷積運(yùn)算,提升各種圖任務(wù)的執(zhí)行效果。隨著圖卷積網(wǎng)絡(luò)的發(fā)展,先前的一些工作將圖卷積網(wǎng)絡(luò)應(yīng)用于信息級聯(lián),利用其特性挖掘級聯(lián)信息的空間拓?fù)浣Y(jié)構(gòu)信息。在文獻(xiàn)[14,17]中,利用圖卷積網(wǎng)絡(luò)提取級聯(lián)信息的空間拓?fù)湫畔?,用于預(yù)測信息級聯(lián)。
注意力機(jī)制在許多機(jī)器學(xué)習(xí)任務(wù)中都展示了顯著的效果,如圖像字幕[18]、視頻字幕[19]和機(jī)器翻譯[20]。注意力機(jī)制對重點(diǎn)關(guān)注鄰域分配更多的注意力資源以獲取更多所需要的特征信息,抑制其他的無用信息,從而取得更好的效果。文獻(xiàn)[5]中,采用注意力機(jī)制計算級聯(lián)序列的權(quán)重,更準(zhǔn)確地預(yù)測級聯(lián)信息。文獻(xiàn)[21]采用注意力機(jī)制探索用戶與用戶間隱式的級聯(lián)擴(kuò)散,從而實現(xiàn)預(yù)測級聯(lián)信息。注意力的關(guān)鍵思想是學(xué)習(xí)一組分配注意權(quán)重(將總和求歸一化): 較高(較低)的權(quán)重表示相應(yīng)的功能對于最終任務(wù)提供較多(較少)的信息。
本文提出一個端到端的深度學(xué)習(xí)面向社交網(wǎng)絡(luò)的ICP模型,采用級聯(lián)子圖Ci(t)作為輸入,預(yù)測推文pi在Δt時間內(nèi)傳播的增量ΔSi。ICP模型由4個組件組成,首先,從級聯(lián)圖中對子圖節(jié)點(diǎn)進(jìn)行采樣并生成鄰接矩陣序列;然后,將觀察時間窗口內(nèi)的鄰接矩陣序列和級聯(lián)圖的結(jié)構(gòu)信息輸入到Bi-LSTM網(wǎng)絡(luò);再將Bi-LSTM得到的表示輸入到注意力機(jī)制,耦合時間序列和空間結(jié)構(gòu)特征,再輸入衰減函數(shù),得到符合時間衰減效應(yīng)的特征表示;最后,使用全連接層輸出進(jìn)行預(yù)測。
圖1 級聯(lián)圖
表1 符號定義表
推文pi觀察到的級聯(lián)圖Ci(t),將其表示為鄰接矩陣形式,并為每個節(jié)點(diǎn)加入自環(huán),如圖2所示。然后根據(jù)級聯(lián)圖Ci(t)中每個節(jié)點(diǎn)的到達(dá)時刻進(jìn)行獨(dú)熱編碼(One-Hot Code)表示節(jié)點(diǎn)特征。將觀察窗口[0,T)劃分為l個不相交的細(xì)粒度時間間隔{[t0=0,t1),[t1,t2),…,[tl-1,tl=T)},然后再對每個時間間隔進(jìn)行編碼。
圖2 級聯(lián)子圖序列的采樣表示
(1)
為了捕獲級聯(lián)信息在傳播過程中的空間結(jié)構(gòu)信息,采用圖卷積網(wǎng)絡(luò)來學(xué)習(xí)嵌入[22]。信息擴(kuò)散過程類似于馬爾科夫過程,即經(jīng)擴(kuò)散一段時間后會收斂于一個穩(wěn)定的分布,類似于分布[23]。因此,設(shè)級聯(lián)的拉普拉斯矩陣Δc,符合級聯(lián)圖的隨機(jī)游走特征,設(shè)馬爾科夫狀態(tài)轉(zhuǎn)移概率矩陣P=D-1A,且存在φi={φ1,φ2,…,φn}滿足φTP=φT。根據(jù)圖卷積網(wǎng)絡(luò)[16]公式:
(2)
可得拉普拉斯矩陣Δc:
(3)
其中,D表示級聯(lián)圖的度矩陣,K表示捕獲的鄰域?qū)訑?shù),
圖3 模型框架圖
(6)
(7)
(8)
(11)
先前研究發(fā)現(xiàn),信息級聯(lián)存在著時間衰減效應(yīng),即一個節(jié)點(diǎn)對其他節(jié)點(diǎn)的影響會隨著時間的推移而減小[24]。本文采用非參數(shù)化時間衰減函數(shù)λf(T-ti),根據(jù)文獻(xiàn)[4]得:
(12)
ICP模型最后一部分是由全連接層(MLP)組成。根據(jù)前面計算得到的h′t,可計算出ΔSi,如式(13)所示。
ΔSi=MLP(h′t)
(13)
最終任務(wù)是預(yù)測指定時間間隔內(nèi)信息傳播的增量,引入均方對數(shù)誤差(Mean Square Log-Transformed Error, MSLE),即:
(14)
作為損失函數(shù)loss,使用Adam優(yōu)化器優(yōu)化loss值,使其達(dá)到最優(yōu)(最小)。
算法1 ICP算法
2: repeat3: for鄰接矩陣序列ATi和對應(yīng)的拉普拉斯矩陣Δ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ù)進(jìn)行優(yōu)化9: end for10: until convergence;
為了評估ICP模型在信息級聯(lián)預(yù)測中的有效性和擴(kuò)展性,本文使用公開數(shù)據(jù)集進(jìn)行實驗并與先前的研究進(jìn)行比較。數(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后,流行達(dá)到飽和。本文遵循與CasCN[14]相似的設(shè)置,即觀察時間窗口T=1, 2, 3h。最后,根據(jù)預(yù)處理后的層疊時間對層疊進(jìn)行排序,并為層疊選擇前70%的層疊為訓(xùn)練集,剩下的平均分為驗證集和測試集。
HEP-PH[25]: HEP-PH數(shù)據(jù)集(高能物理現(xiàn)象學(xué)數(shù)據(jù)集)來自電子版arXiv論文引用網(wǎng)絡(luò),數(shù)據(jù)涵蓋了1993年1月至2003年4月(124個月)期間的論文,其中有34 546篇論文的所有引文。如果論文i引用論文j,則論文引用圖包含從i到j(luò)的有向邊。如果論文引用了數(shù)據(jù)集之外的論文或被其引用,則該圖將不包含有關(guān)此信息。圖4(b)顯示了級聯(lián)大小的分布情況,圖5(b)展示了級聯(lián)的流行情況。對于觀察窗口,選擇T=3, 5, 7a,分別對應(yīng)流行度達(dá)到最終規(guī)模的50%,60%和70%,如圖5(b)所示。然后,收集70%的級聯(lián)用于訓(xùn)練,其余平均拆分為驗證集和測試集。
圖4 級聯(lián)尺寸分布圖X軸為級聯(lián)大小,Y軸表示不同級聯(lián)大小對應(yīng)的數(shù)量
圖5 時間和級聯(lián)數(shù)之間的百分比分布
本文所有實驗在Ubuntu 16操作系統(tǒng),Intel Core I9-9980XE CPU,128GB內(nèi)存和NVIDIA TiTan RTX(24GB)顯卡上進(jìn)行。
對于DeepCas、DeepHawkes、Topo-LSTM和CasCN,參照DeepCas[5]設(shè)置用戶的嵌入維度是50,循環(huán)神經(jīng)網(wǎng)絡(luò)每層的隱藏單元數(shù)是32,全連接層的隱藏單元數(shù)分別是32和16,用戶學(xué)習(xí)率為5×10-4,其他學(xué)習(xí)率為5×10-3。每次迭代的批處理大小為32,當(dāng)連續(xù)50次迭代,驗證集的loss沒有下降,模型訓(xùn)練過程將停止。Weibo數(shù)據(jù)集的時間間隔設(shè)置為10min,HEP-PH的時間間隔設(shè)置為2個月。
本文采用Tensorflow來實現(xiàn)ICP模型,并使用Adam優(yōu)化器通過梯度下降來優(yōu)化參數(shù)。除圖表示學(xué)習(xí)的嵌入鄰域?qū)硬捎肒=2外,其余模型參數(shù)設(shè)置與上述模型保持一致。
根據(jù)現(xiàn)有的工作,在實驗中選擇標(biāo)準(zhǔn)評估指標(biāo)——MSLE[見式(14)]來評估鏈接準(zhǔn)確性。請注意,MSLE越小,其預(yù)測性能越好。
3.4.1 基準(zhǔn)版性能對比
將用本文所提出ICP模型的基準(zhǔn)版,在真實的數(shù)據(jù)集上與先前級聯(lián)預(yù)測模型進(jìn)行實驗對比。
DeepCas[5]是第一個用于信息級聯(lián)預(yù)測的深度學(xué)習(xí)體系結(jié)構(gòu),其表示級聯(lián)圖為一組隨機(jī)行走路徑,并通過雙向GRU神經(jīng)網(wǎng)絡(luò)通過管道傳輸,并帶有注意力機(jī)制來預(yù)測級聯(lián)的大小。它主要利用結(jié)構(gòu)和節(jié)點(diǎn)身份的信息進(jìn)行預(yù)測。
DeepHawkes[4]模型將端到端深度學(xué)習(xí)的預(yù)測能力集成到Hawkes過程的可解釋因素中,以進(jìn)行流行度預(yù)測。深度學(xué)習(xí)方法與級聯(lián)動力學(xué)建模過程之間的結(jié)合彌合了信息級聯(lián)預(yù)測和理解之間的鴻溝。該方法既屬于生成方法又屬于基于深度學(xué)習(xí)的方法。
Topo-LSTM[15]是有向無環(huán)圖結(jié)構(gòu)(DAG結(jié)構(gòu))RNN,將動態(tài)DAG作為輸入,并為DAG中的每個節(jié)點(diǎn)生成拓?fù)涓兄那度胱鳛檩敵?,從而預(yù)測下一個節(jié)點(diǎn)。
CasCN[14]模型結(jié)合了結(jié)構(gòu)和時間的深度學(xué)習(xí)框架,利用圖卷積網(wǎng)絡(luò)捕獲網(wǎng)絡(luò)空間結(jié)構(gòu)信息,通過循環(huán)神經(jīng)網(wǎng)絡(luò)合并了時間衰減函數(shù)實現(xiàn)時間信息的更有效利用。該模型是一種深度學(xué)習(xí)的方法。
表3總結(jié)了Weibo和HEP-PH數(shù)據(jù)集上ICP模型和其他模型基準(zhǔn)版之間的性能比較。ICP模型與DeepCas對比,證明僅嵌入節(jié)點(diǎn)作為圖表示是不夠的,不能將圖表示為一組隨機(jī)路徑。因DeepCas未能考慮時序信息和級聯(lián)圖的拓?fù)浣Y(jié)構(gòu),導(dǎo)致其性能比其他基于深度學(xué)習(xí)方法要差。Topo-LSTM也缺乏對時序信息的處理,導(dǎo)致其性能也較差。DeepHawkes雖然以生成方式對級聯(lián)進(jìn)行建模,但由于其學(xué)習(xí)結(jié)構(gòu)信息的能力較弱,因此無法發(fā)揮最佳性能。CasCN考慮了時序信息與空間拓?fù)浣Y(jié)構(gòu),但忽略了二者特征之間的融合。最后,本文提出的ICP模型在兩個數(shù)據(jù)集上的信息級聯(lián)預(yù)測(推文轉(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,取得了較好的預(yù)測效果。與CasCN相比,本文提出的ICP模型預(yù)測誤差分別降低了5.31%,1.18%,7.31%和6.47%,8.07%,8.46%,從而證實了模型的有效性。
表3 性能對比表(MSLE)
3.4.2 時空注意力對信息級聯(lián)的影響
首先驗證注意力機(jī)制的有效性,設(shè)計消融實驗。構(gòu)建一個ICP的刪減版ICP-LSTM,即將基準(zhǔn)版中的Bi-LSTM替換為LSTM,然后與CasCN進(jìn)行比較,等價于ICP-LSTM是在CasCN模型的基礎(chǔ)上添加了注意力機(jī)制。在實驗過程中,二者參數(shù)一致,驗證采樣的鄰域?qū)訑?shù)K=1,2時的實驗效果如表4所示。
表4 注意力機(jī)制影響級聯(lián)預(yù)測性能對比表(MSLE)
表4中給出了嵌入層K=1,2與CasCN模型K=2的性能對比。根據(jù)表4可以看出,當(dāng)K=2時,本文提出的ICP模型優(yōu)于CasCN模型,這是因為添加了注意力機(jī)制,能夠耦合時序信息與空間結(jié)構(gòu)信息。當(dāng)K=1時,在Weibo中觀察2h,ICP-LSTM的MSLE大于CasCN,是由于K=1,采取的空間結(jié)構(gòu)信息不足,導(dǎo)致結(jié)果略低。
然后,驗證時序信息對級聯(lián)預(yù)測的影響,將ICP的變體ICP-BiLSTM與CasCN進(jìn)行對比分析(ICP-BiLSTM為本文提出的ICP模型去掉注意力機(jī)制,也等價于將CasCN模型中LSTM網(wǎng)絡(luò)替換為BiLSTM網(wǎng)絡(luò)所產(chǎn)生的模型)。通過表5數(shù)據(jù)可以看出,當(dāng)K=2時,Weibo觀察3h的MSLE=1.783和HEP-PH觀察7a的MSLE=0.84,優(yōu)于CasCN的MSLE,從而證實時序信息在信息級聯(lián)中的重要性。
表5 時序網(wǎng)絡(luò)影響級聯(lián)預(yù)測性能對比表(MSLE)
最后,驗證時序信息和空間信息對級聯(lián)預(yù)測的影響,在CasCN的基礎(chǔ)上使用Bi-LSTM并添加注意力機(jī)制,再調(diào)整嵌入的鄰域?qū)訑?shù)K分別與CasCN進(jìn)行比較。通過表6的數(shù)據(jù)可以看出,在Weibo和HEP-PH數(shù)據(jù)集上K=1,2時,MSLE值均小于CasCN的MSLE值,表明本文提出的模型優(yōu)于CasCN,對時序信息和空間拓?fù)湫畔⒌牟东@更全面,從而提升了模型的效率,降低了損失率。
表6 時序空間影響級聯(lián)預(yù)測性能對比表(MSLE)
上述實驗表明,時序信息和空間結(jié)構(gòu)信息對信息級聯(lián)預(yù)測效果有重要影響。二者結(jié)合,能更好地保證預(yù)測的準(zhǔn)確率。使用注意力機(jī)制耦合二者數(shù)據(jù),使模型對時序信息和空間結(jié)構(gòu)信息的捕獲更加全面,也使模型更具有泛化力。
本文注意力機(jī)制的主要思想源自于自注意力機(jī)制,可采用比自注意力機(jī)制耦合效果更優(yōu)的方法。例如,可以采用多頭注意力機(jī)制來替換文中的注意力機(jī)制,提出了ICP的變體ICP-Mhead。表7給出了在相同參數(shù)下CasCN、ICP與ICP-Mhead實驗對比結(jié)果。可以得出,ICP-MHead模型的MSLE值均小于CasCN模型和ICP模型的MSLE值,表明使用多頭注意力的效果明顯優(yōu)于CasCN模型。因為多頭注意力機(jī)制采用多個頭部去捕獲特征信息,從而可以捕獲更多的邊緣信息(被忽略的時序信息和空間拓?fù)浣Y(jié)構(gòu)),使得提取的特征更加全面,故ICP-MHead模型優(yōu)于ICP模型。
表7 多頭注意力機(jī)制影響級聯(lián)預(yù)測性能對比表(MSLE)
本節(jié)對ICP-LSTM,ICP-BiLSTM,ICP-MHead與ICP的收斂性進(jìn)行分析,實驗結(jié)果如圖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和注意力機(jī)制導(dǎo)致訓(xùn)練時間較長,但模型的預(yù)測指標(biāo)更高且訓(xùn)練時間在可接受范圍內(nèi)。
圖6 ICP模型驗證集Loss
圖6 (續(xù))
本文提出端到端的深度學(xué)習(xí)ICP模型實現(xiàn)信息級聯(lián)預(yù)測。在深度學(xué)習(xí)框架下,首先利用圖卷積網(wǎng)絡(luò)提取級聯(lián)信息的空間結(jié)構(gòu)特征,再利用雙向循環(huán)神經(jīng)網(wǎng)絡(luò)提取時序特征,然后使用注意力機(jī)制耦合空間結(jié)構(gòu)特征和時序特征,最后,在結(jié)合級聯(lián)的時間衰減效應(yīng)進(jìn)一步提高模型的預(yù)測準(zhǔn)確性。本文在兩個公開數(shù)據(jù)集上進(jìn)行實驗,結(jié)果表明,本文提出的基于時空注意力的社交網(wǎng)絡(luò)ICP模型預(yù)測精度高于先前的方法。
下一步在空間結(jié)構(gòu)與時序信息相結(jié)合的基礎(chǔ)上,引入點(diǎn)過程建模,使得模型更具有可解釋性,提高模型的預(yù)測能力。