WWW 2024 | 簡單卻強大：揭秘Transformer在動態圖建模中的魔法
論文題目：
On the Feasibility of Simple Transformer for Dynamic Graph Modeling
論文鏈接：
??https://arxiv.org/pdf/2401.14009.pdf??
代碼鏈接：
??https://github.com/YuxiaWu/SimpleDyG??
論文錄用：
The WebConference 2024 Main Conference
作者主頁：
??https://yuxiawu.github.io/??
01 摘要
動態圖建模在理解 Web 圖中的復雜結構方面至關重要，涉及社交網絡、推薦系統等多個應用領域。現有方法主要注重結構依賴性及其時序變化模式，但通常忽略詳細的時間信息或難以處理長期依賴問題。此外許多方法過于依賴復雜的模塊設計來捕捉動態圖的演變。
本研究充分利用 Transformer 的自注意機制在序列建模中處理長距離依賴的強大能力，提出了一個專為動態圖建模定制的簡單而有效的 Transformer 模型，無需復雜的網絡結構修改。
我們將動態圖重構為序列建模任務，并引入創新的時間對齊技術，不僅捕捉了動態圖中固有的時間演變模式，還簡化了其演變過程的建模。所提方法靈活多樣，適用于各種應用。通過在四個真實世界不同領域數據集上的實驗證明了模型的有效性。
02 研究背景
2.1 現有工作的不足
現有的動態圖建模工作主要分為兩類：
- 離散時間方法: （見圖 1a）將動態圖視為離散時間上的快照（snapshot）序列，采用結構模塊（如 GNN）捕捉拓撲信息，時序模塊（如 RNN）學習序列演變。缺點：丟失細粒度時間信息；
- 連續時間方法: （見圖 1b）專注于通過特定的時間模塊（如時間隨機游走或時間核函數）對連續時間模式建模。缺點：難以捕捉歷史圖的長期依賴。
此外， 大多數現有工作依賴消息傳遞 GNN 編碼動態圖結構模式。盡管消息傳遞機制在圖建模中很強大，但它有一些局限性，如過度平滑和過度壓縮，隨著模型深度增加，阻礙了更深入和更有表現力的架構的發展。
2.2 研究動機
為了應對現有動態圖建模中的問題，我們借鑒了 Transformer 及其在 NLP 和 CV 領域的成功應用。Transformer 架構具有兩大優勢：自然支持連續數據序列，無需離散快照；自注意力機制有助于捕捉長期依賴關系（見圖1(c)）。鑒于 Transformer 受過度平滑和過度壓縮問題的影響較小，我們自然地提出可否將Transformer 架構用于動態圖建模? 有哪些挑戰? 如何解決?
2.3 挑戰及對策
?
保留歷史演變的計算成本問題：由于自注意力機制的計算成本較高，現有基于 Transformer 的圖模型僅適用于小型圖，限制了對大型動態圖的處理。我們引入一種新穎的策略，將每個節點的歷史交互圖看作 ego graph，大幅減小計算成本并保留完整的動態交互歷史。
通過將 ego graph tokenize 為適用于 Transformer 輸入的序列，我們實現了對整個時間線的信息保留，同時確保了可擴展性，而無需修改原始 Transformer 架構。
輸入序列之間的時間信息對齊問題：在動態圖中，不同 ego 節點的輸入序列享有一個共同的時間域, 然而在語言建模或靜態圖的序列中缺乏這樣的通用時間域，在很大程度上可以將它們視為相互獨立的。
如果不對原始序列進行時間上的對齊，將無法區分不同時間間隔和頻率信息。為了解決這一挑戰，我們精心設計了特殊的時間 token，并將其巧妙地整合到輸入序列中，在實現全局對齊的同時，每個節點的局部序列仍然保留著時間順序。
03 方法介紹
我們提出了一種名為 SimpleDyG 的動態圖建模方法，采用原始 Transformer 架構，充分發揮其在建模動態圖方面的潛力，整體框架如圖 2 所示，主要應用于動態圖（見圖 2(a)）。
首先，針對每個節點，提取以其為中心的時序 ego-graph，涵蓋整個歷史交互（見圖 2(b)），將提取的 ego-graph 轉換為序列，同時保留時間順序。
其次，為了在不同 ego-graph 之間實現時間對齊，將時間線劃分為具有相同時間間隔的跨度，如圖 2(c) 所示。在 ego 序列中添加特殊的時間 token，使模型能夠識別不同時間跨度。
最后，將處理后的序列輸入到 Transformer 架構中，用于執行各種下游任務。
3.1 時序 ego-graph
?
對動態圖 中的每個ego節點 ，提取與 有過交互的節點，形成一個序列，作為 Transformer 的輸入 ，其中 是序列長度。為更好地建模輸入序列的模式，我們借鑒了 NLP 序列建模任務方法，引入一些為我們任務設計的特殊 token。最終構建的輸入序列和輸出序列如下：
其中 和 是特殊 token，表示輸入歷史序列的開始和結束。 和 用于預測未來的鏈接節點。一旦生成了結束特殊 token，模型將停止預測，從而實現對未來交互數量的自動決策。
3.2 時序對齊
?
首先，將時間域 劃分為離散的、粗粒度的等間隔時間步長。注意，我們的方法與離散時間圖建模不同，因為在每個時間步內部，我們考慮了不同鏈接的時間順序。
然后，我們引入了一種簡單而有效的策略，將動態圖中的時間對齊信息納入 Transformer 架構的輸入序列中。我們設計特殊的時間 token，表示全局所有節點不同的時間步。
假設我們將時間域 分成 個時間步，時間步 中 ego 節點 的序列如下所示：
其中 表示節點 在時間步 的歷史序列，長度為 。是時間 token，用作時間對齊的指示器，使模型能夠識別和捕捉數據中的時間模式。
最后，我們將動態圖表示成序列，采用和 Transformer 架構一樣的損失函數進行訓練。
04 實驗
我們在四個基準數據集上進行了全面的實驗，以評估所提出的 在動態圖鏈接預測任務上的有效性。
4.1 實驗對比
實驗結果見表 2，總體而言，我們的方法在所有數據集上均優于對比方法，我們得出以下觀察：
首先，各種場景中連續時間方法通常優于離散時間方法，突顯了時間信息在動態圖分析中的重要性。尤其是像 GraphMixer 等簡單的 MLP-Mixer 架構表現出更高性能，其較低的復雜性有助于捕捉長期歷史序列。
相反，其他模型如 DyRep、TGAT 和 TGN 依賴于復雜的設計（如 GNN 和 GAT），表現較差，這可能因為它們在捕捉長距離依賴關系上的固有局限性。
其次，對于歸納場景（即測試集包含新節點，如 Hepth 數據集），采用基于 GNN 的骨干結構的連續時間模型相比 GraphMixer 表現出更高的性能。這是因為為了能夠處理新節點，我們使用 word2vec 構建初始節點特征，這可能相對粗糙。
由于 GraphMixer 主要依賴于基于 MLP 的架構，使用粗粒度的初始特征可能會遇到挑戰。相比之下，基于 GNN 的方法將結構信息與這些特征整合在一起，從而使它們在歸納場景中表現出色。然而，在我們基于 Transformer 的模型中，還有建模長距離依賴性的附加優勢，因此 SimpleDyG 的性能始終更好。
4.2 額外token分析
?
4.2.1 特殊token分析
?
特殊 token 包括歷史序列的開始和結束（ 和 ），以及預測未來序列的開始和結束（ 和 ）。為全面評估它們在不同場景下的效果，我們在兩個模型變體上進行了實驗：
- same special，對輸入和輸出使用相同的特殊 token
- no special，完全刪除每個樣本中的所有特殊 token
結果如表 3 所示，總體而言，特殊 token 可以增強不同數據集上的鏈接預測性能。此外，same special 和原始的 SimpleDyG 之間的差異往往較小。然而，在 Hepth 數據集上有一個有趣的發現，其 no special 模型性能更好，這是因為 Hepth 測試集中的 ego 節點都是新出現的節點（表示新發表的論文），因此輸入樣本缺乏歷史信息，區分歷史和未來序列預測之間的區分不太相關。
4.2.2 時間token分析
?
為了全面評估時間 token 的影響，我們將性能與兩個變體進行了比較：
- same time，不區分特定的時間步，對每個時間步使用相同的時間 token
- no time，完全刪除每個樣本中的所有時間 token。
結果如表 4 所示，我們得出以下觀察：
令人驚訝且有趣的是，使用更簡單的設計進行時間對齊會有性能的提升。這種現象在 MMConv 多輪對話數據集和 Hepth 論文引用數據集中最為明顯，這是因為不同 ego 節點之間的對話和論文引用關系并不嚴格遵循時間順序，使用相同的時間 token 或不使用時間 token 可以讓模型更自然地適應這種時間順序。
對于 UCI 和 ML-10M 數據集，時間對齊起著重要的作用。然而他們在 same time 模型上的性能變化趨勢不同，原因在于 UCI 數據中不同用戶的通信習慣對于不同 time steps 的切分是敏感的，因此，same time，因為它將序列劃分為 time steps，但沒有不同時間 token 在序列之間進行對齊，額外的相同時間 token 可能會使模型混淆。
另一方面，no time 仍然保留完整的時間順序，因此表現優于 same time。
更多實驗分析詳見原始論文。
05 總結與展望
在這項工作中，我們深入研究了復雜的動態圖建模領域，利用 Transformer 自注意機制的優勢，我們為動態圖建模量身定制了一種解決方案，避開了現有方法中常見的復雜設計。
我們的方法從序列建模的角度出發，對動態圖進行重構，并引入創新的時間對齊策略。這種設計不僅捕捉了動態圖中固有的時間演變模式，而且簡化了它們的建模過程。在四個不同領域的真實數據集上的實驗驗證了我們模型的有效性。在未來，我們將深入研究時間對齊策略，以進行進一步的優化。此外，可以探索整合更先進的注意力機制，以進一步提升模型在捕捉動態演變方面的能力。
本文轉自 PaperWeekly ，作者：吳玉霞
