融合動態圖表示和自注意力機制的級聯預測模型

張鳳荔，王雪婷，王瑞錦，湯啟友，韓英軍

(電子科技大學信息與軟件工程學院 成都 610054)

如今，Twitter、微博、Facebook、YouTube 和微信等在線社交平臺已成為熱點事件傳播的主要途徑。某一事件很快就能在社交網絡中通過新聞報道、論壇帖子[1]和視頻動態等各種形式被廣泛傳播。在事件傳播過程中，信息級聯是很重要的組成部分。信息級聯是指博客、電子郵件以及社交網站中識別到的用戶級聯轉發序列與網絡關系圖[2]。通過對信息級聯模型的研究，可以了解信息的傳播規律和特性，為事件演化下一步研究提供技術支持。

現今，在信息級聯預測領域中，基于特征工程方法的模型只適用于特定場景[3-4]；依賴于假設的點過程 (如泊松過程和霍克斯過程) 的生成式方法的模型無法同時捕獲級聯圖的基礎結構和擴散的不確定性[4]；基于深度學習技術的模型，可以對時間序列和靜態級聯圖結構進行建模。但現實生活中，信息級聯圖的結構是隨著時間動態變化的。在建模過程中，考慮級聯圖的動態變化性，捕獲級聯圖時序及結構特征，對于刻畫信息傳播過程有重要作用。

本文提出一個基于級聯圖的動態演化過程的模型。該模型考慮信息傳播過程中的不確定性，將圖的動態演化過程和自注意力機制相結合，實現對級聯圖的時序及結構特征的同時捕獲；且僅依賴級聯圖的結構和時序信息，利用深度學習技術以端到端的方式，實現級聯的潛在語義捕獲。實驗在新浪微博和APS 實際數據集上進行，相比傳統的級聯預測模型，提升了預測的準確性。

1 方法分析

信息級聯預測方法主要有以下3 類：

1) 基于特征建模的預測方法。特征建模方法基于特征工程，利用經典機器學習技術建模進行級聯預測。如文獻[5]發現加入與用戶相關的特征可以有效地預測用戶是否會參與級聯；文獻[6]驗證了在微博數據集中結構特征和時序特征的重要性。這些方法都需要某一特定領域的大量相關特征，具有特殊性，不能夠遷移至其他應用場景；且用戶個人信息和私有社交平臺特征信息具有私密性，難以得到。

2) 基于生成式的預測方法。生成式方法主要從轉發到達速率方面入手，對每條消息的到達強度函數獨立建模。如文獻[7]通過借鑒生存分析的思想來預測在線內容的流行程度；文獻[8]提出了一個生成概率模型，用增強泊松過程來預測科學論文的流行程度。文獻[9]將級聯轉換成一組擴散路徑，用自激勵霍克斯點過程對級聯進行建模。此類方法所觀測的數據是觀測時間窗口內的每個事件的發生，而不是未來要預測的增量流行度。

3) 基于深度學習的預測方法[10]。在深度學習級聯預測模型中，節點的嵌入方法對節點表示有著關鍵性的作用。節點表示的準確性，將直接影響模型預測結果。DeepCas[11]是基于圖表示學習的信息級聯預測方法，它在借鑒了DeepWalk[12]的基礎上，采用隨機游走對級聯圖采樣，然后將采樣后的級聯序列結合注意力機制傳入雙向門控遞歸單元 (Bi-GRU) ，最終得到節點的嵌入。基于注意力機制的預測模型，采用GloVe[13]對消息內容進行嵌入，并使用node2vec 對用戶圖進行編碼。基于深度學習的級聯預測方法，不需要在級聯圖上人工標記特征，預測準確性高。

現有的級聯模型都是針對擁有固定節點集和邊集的靜態圖。在現實生活中，級聯圖的本質是動態的，它的結構會隨著時間的變化而呈現一個動態演化的過程。這就要求在學習級聯圖節點表示時，不僅要保留結構上的臨近性，還要同時捕獲其時序演變特征[1]。文獻[14]將自注意力機制應用于動態圖表示；文獻[15]同時考慮到圖的異構性和動態性的特點，通過循環神經網絡結合自注意力機制實現節點動態嵌入；文獻[16]提出了一種能夠捕捉動態圖演化的動力學特征方法。上述方法針對的是廣泛的動態圖，在信息級聯領域還沒有相關應用。

因此本文提出DySatCas 模型，主要將級聯圖的動態性定義為一系列的快照子圖，融合自注意力機制捕獲級聯圖的結構和時序特征，從而學習到節點的動態表示。

2 問題定義及模型設計

2.1 問題定義

現有M條消息，每條消息轉發記錄對應一張級聯圖，如圖1 所示，深灰色節點為消息發送者，白色節點為表示觀測時間內轉發該消息的用戶，淺灰色節點為將會新增的轉發用戶，帶箭頭實線表示用戶間的轉發關系，虛線表示將會出現的轉發關系。

圖1 消息C i的級聯圖

圖2 消息Ci 的級聯演化圖

將信息級聯預測問題定義為：給定消息Ci的級聯圖Gi和在觀測時間 [0，T]內的級聯演化序列，預測此條消息在觀測窗口結束時，信息級聯的增長量代表級聯圖的大小。

2.2 級聯預測模型DySatCas

融合動態圖表示和自注意力機制的級聯預測模型DySatCas 如圖3 所示。整個模型分為4 個部分，分別是節點嵌入層、結構自注意力層、時序自注意力層、級聯增量預測層。以某一級聯圖Gi及其演變子圖為例：

圖3 融合動態圖表示和自注意力機制的級聯預測模型

1) 節點嵌入層：輸入級聯圖Gi和演變子圖，本層將采樣得到的演變子圖分別進行編碼，得到節點的向量表示矩陣xv。

2) 結構自注意力層：將節點嵌入層得到的向量矩陣xv輸入該層，計算節點以及其鄰居節點的注意力權重，并將該節點的鄰居節點的特征聚合到該節點，得到該節點新的向量表示。

3) 時序自注意力層：將結構自注意力層輸出的節點向量表示和該節點的位置嵌入pj求和后，傳入時序自注意力層。該層對每個節點在其歷史子圖上的狀態進行學習，得到每個節點的表示。

4) 級聯增量預測層：將時間T得到的每個節點的表示輸入到多層感知器中，最后得到級聯增量的預測結果Pi。

2.2.1 節點嵌入層

在級聯圖Gi的基礎上，以相同時間間隔T/N作為標準得到演變級聯子圖ζi(tN)}。然后將 ζi(tj)(1 ≤j≤N)中的節點嵌入到向量空間{∈RD,?v∈V},D是節點嵌入的維度，可調整。

2.2.2 結構自注意力層

結構自注意力層的主要作用是通過多層堆疊的自注意力機制對節點及其鄰居節點的特征進行學習，將學習到的特征聚合到該節點上，得到對該節點的空間結構特征表示。該層的輸入是演變級聯子圖ζi(tj)中 每個節點的D維向量表示{∈RD,?v∈V}。通過該層可捕獲到節點在級聯子圖的局部屬性，輸出為新的可調整的F維向量表示{∈RF,?v∈V,j∈[1,N]}。

式中，Nv={u∈V:(u,v)∈ε}為 節點v在 圖 ζi(tj)中直接鄰居的集合；WS∈RF×D是應用于圖中每個節點變換的共享權重；a∈R2D是注意力函數的加權向量參數化；‖表示拼接操作；σ(·)是非線性激活函數；是當前圖中邊 (u,v) 的 權重；αuv是通過softmax函數對在V中每個節點的鄰居節點進行歸一化操作后的學習參數，表示在當前圖中節點u對 于節點v的影響力；同時使用LeakyRELU 非線性激活函數來計算注意力權重，然后用指數線性單元(exponential linear unit, ELU)來激活，并將激活結果作為輸出表示。當 αuv為 0 時，節點u和v在圖ζi(tj)中是沒有連接的，使用稀疏矩陣可以有效的實現其鄰居節點所隱藏的自我注意力。

2.2.3 時序自注意力層

時序自注意力層同結構自注意力層類似，采用多個堆疊的時序自注意力模塊，充分考慮級聯圖的動態演化過程，捕捉多個時間段的節點的時序變化。該層的輸入是特定節點v在不同時間步長的一系列表示。采用文獻[18]所提出的位置嵌入方法，得到節點各子圖中絕對時序位置的嵌入序列然后結合結構注意力層的節點v在不同的時間步長下的向量表示得到該層的輸入，N是總時間步長。該層輸出是。節點的輸入及輸出分別結合時間步長合并表示為Xv∈RN×F和。節點v在 時間步長j的輸入表示為，且用作為該節點時間步長小于j的歷史狀態的查詢。和結構自注意力機制在其鄰居節點進行特征學習表示不同，時序自注意力機制更關注每個節點的歷史狀態。

通過對注意力按比例縮放的點積的形式來計算節點v在時間步長j的輸出表示，其中查詢、鍵和值的集合是節點的輸入表示。查詢、鍵和值首先分別通過線性投影矩陣Wq∈RF×F′,Wk∈RF×F′和Wv∈RF×F′轉換到不同空間。在計算時考慮所有小于j的時間步長，直到時間步長到達j，來保持其自回歸性。時序自注意力函數定義為：

式中，βv∈RN×N是通過乘法注意力函數得到的注意力權重矩陣；S∈RN×N是其每個子項Sij∈{?∞,0}擁有強自回歸屬性的掩碼矩陣。為了對時序進行編碼，將S定義為：

當Sij=?∞時，通過softmax 函數所得到的注意力權重為0，例如當=0時，時間步長i到j不使用注意力機制。

2.2.4 級聯增量預測層

2.3 模型訓練及算法描述

2.3.1 模型訓練

該模型的最終目標是對級聯增量大小進行預測，采用式(10)作為損失函數來對模型進行優化，在迭代中損失連續10 次不再減小時結束訓練：

式中，P是所有消息的總量；Pi是消息Ci的預測級聯增量；是實際增量。

2.3.2 算法描述

給定信息級聯圖Gi，經基于不同時間步的子圖算法采樣后，得到原始信息級聯的子圖快照集合ζi(tj)并 得到其對應的序列表示。將得到的序列表示輸入到結構自注意力機制層，對每個節點及其鄰居結構進行學習，得到。然后將與pj相加輸入到時序自注意力機制層得到。最后將各節點融合了動態演化的結構特征和時序特征的向量表示依次通過多層感知機，并輸出最終流行度增量預測值Pi。

整個算法流程與圖3 模型架構圖一致，主要分為節點嵌入、結構自注意力、時序自注意力和級聯增量預測4 部分。

算法： DySatCas

輸入：級聯圖Gi及其演化序列的集合、級聯圖數量M、時間步長N

輸出：級聯增量預測值Pi的集合

模型初始化，參數設置

3 實驗與分析

3.1 實驗數據集

本文主要基于兩個實際場景的公開數據集來對所提出模型的有效性進行評估，分別是預測新浪微博的轉發量和在數據集APS 上預測論文的引用量，如表1 所示。

表1 實驗數據集的詳細統計

Sina Weibo：每一個樣本對應一條微博消息的轉發路徑，其中包含轉發用戶的id 以及轉發的時間戳。

APS(American physical society)：該數據集包含了美國物理學會的期刊從1893?2009 年所發表的論文及其引用，每一篇論文及其引文都形成了一個引用級聯。

3.2 超參數設定

時間自注意力層單元數、結構自注意力層單元數和嵌入層單元數為128，多層感知層單元數為128×64，Adam 優化器的初始學習率為0.0005，迭代輪數2000 輪，時間步長度N為12。

3.3 評價指標

和文獻[17]相同，使用均方對數誤差MSLE 和平均絕對百分比誤差MAPE 來對所提出的模型進行評估，具體評估公式為：

3.4 對比分析

3.4.1 基線模型

1) Feature-Linear：基于特征的信息級聯預測模型是應用最廣泛的。本文基線模型提取如消息發送者/轉發者的特征、結構和時間特征，將此類特征輸入到線性回歸模型和MLP 模型中對信息級聯增長量進行預測。

2) DeepCas[11]：將深度學習應用于信息級聯預測的模型，級聯圖采樣方式為隨機游走，并采用雙向GRU 和注意力機制來預測端到端的信息級聯增量。

3) Topo-LSTM[19]：使用LSTM 來對圖中節點間關系進行建模。根據上一個節點狀態，得到下一個節點的預測結果。

4) DeepHawkes[9]：結合了深度學習和自激勵過程來進行信息級聯預測。

3.4.2 模型評價指標對比

為了檢驗DySatCas 模型的效果，分別從現在流行的3 類級聯預測方法中，選擇其中具有代表性的模型來進行比較，具體結果如表2 所示。通過對比有以下發現:

表2 兩種數據集下使用MSLE 和MAPE 兩種評價指標對不同模型及變體的評估表現

1) DySatCas 的預測效果優于基線。在微博數據集上，觀測時間為0.5 h ，MSLE 和MAPE 的結果分別比第一最佳基線 (DeepHawkes) 高出2.5%和3.4%；觀測時間為1 h，MSLE 和MAPE 均比其他基線效果好。在數據集APS 上，觀測時間為5 年，MSLE 和MAPE 的結果比第一最佳基線分別高出10%和4%，除觀測時間3 年，MAPE 略低于DeepHawkes 外，其他數據均優于基線，且隨著觀測時間增加，預測誤差逐漸減少，這表明了DySatCas模型的對級聯圖的動態演化過程學習的有效性。

2) 從實驗結果不難看出，在兩個數據集中，基于特征的基線模型的預測效果并不比基于深度學習的基線模型差。在微博數據集中，基于特征的基線模型預測準確性甚至高于傳統的基于深度學習的基線模型(DeepCas、Topo-LSTM) 。但該方法極大地依賴于人工提取特征，存在很大的不穩定性和不確定性。并且通過人工的方法，很難提取到較復雜信息中所隱含的特征，適用場景相對固定，推廣性差。

3) DeepCas 是基于圖表示學習的級聯預測模型。其主要使用隨機游走的方法對級聯圖進行采樣，但沒有考慮信息的實際傳播順序，同時忽略了傳播過程中的時序依賴性，使得預測效果較其他深度學習方法較差。這說明了在信息級聯預測中，級聯圖的結構特征和時序特征的重要性。

4) Topo-LSTM 是基于RNN 的級聯預測模型，采用擴散拓撲結構，但沒有考慮時間因素以及不確定的級聯效應，使得預測效果與DeepHawkes 及DySatCas 有一定的差距。

5) DeepHawkes 模型是一種結合了生成式方法和深度學習的模型。在級聯預測過程中，不考慮級聯的拓撲信息，依賴于時間序列進行建模，主要關注點在于自我激勵機制對級聯增量的影響。雖然相比DeepCas 和Topo-LSTM 預測準確性更高，但因為沒有考慮級聯的結構特征，且忽略了級聯的動態性，使得預測效果與DySatCas 相比不夠理想。從而說明了在級聯預測中，級聯圖的結構特征、時序特征及其傳播過程中的動態過程都是影響預測效果的關鍵因素。

3.5 模型分析

3.5.1 模型變體

為了更好地了解DySatCas 模型各組成部分對于模型整體預測效果的影響，引入兩種變體進行對比。

1) DySatCas-Temporal：在該變體中，忽略時序注意力層，直接將通過結構自注意力層的向量表示輸入到多層感知器進行預測。

2) DySatCas-Structural：在該變體中，忽略結構注意力層，直接將通過子圖采樣后的向量編碼輸入到時序自注意力層，然后將時序自注意力機層的表示輸入到多層感知器中。

從表2 中可以看出：與DySatCas 相比，在觀測時間為0.5 h 時，移除結構自注意力層的DySatCas-Structural 和移除時序自注意力層的DySatCas-Temporal 預測誤差分別增加了10%和17%，其中移除了時序自注意力層的變體誤差更大，說明了級聯預測過程中，時序特征對預測效果有更大的影響力，同時也證明了本文模型各組成部分的有效性。

3.5.2 時間步長

為了驗證時間步長在動態圖演化過程中的影響，在微博數據集上，分別將時間步長設置為2、3、4、5、6、7、8、9、10、11、12，得到預測結果如圖4 所示。由圖可知，隨著時間步數越長級聯預測效果越好，后期誤差出現變化不大的原因主要是時間步劃分過細，導致后期級聯圖變化不大，所學習到的節點表示相近。

圖4 不同步長性能預測比較

3.5.3 觀測窗口

觀測時間窗口也是DySatCas 模型中最重要的參數，如圖5 所示，在微博數據集和APS 數據集上，分別把觀測時間窗口設置為0.5、1、2、3、4 h和3、4、5、6、7、8 年，由實驗結果可知觀察時間窗口越長，DySatCas 的訓練數據越多，從而就能做出更準確的預測。

圖5 不同觀測窗口在不同數據集上的表現

4 結束語

本文融合動態圖學習和自注意力機制，提出了級聯預測模型DySatCas。該模型不嚴重依賴人工標記特征，充分考慮級聯傳播過程中的動態性和不確定性，根據級聯圖的結構特征和時序特征來進行級聯預測。更好地幫助人們了解信息傳播機制和規律，也為后續事件演化研究提供有力的技術支撐。未來考慮結合多任務、多視圖等概念，進一步對信息傳播特點進行研究。