論文題目：

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 摘要

動態(tài)圖建模在理解 Web 圖中的復(fù)雜結(jié)構(gòu)方面至關(guān)重要，涉及社交網(wǎng)絡(luò)、推薦系統(tǒng)等多個應(yīng)用領(lǐng)域。現(xiàn)有方法主要注重結(jié)構(gòu)依賴性及其時序變化模式，但通常忽略詳細(xì)的時間信息或難以處理長期依賴問題。此外許多方法過于依賴復(fù)雜的模塊設(shè)計來捕捉動態(tài)圖的演變。

本研究充分利用 Transformer 的自注意機(jī)制在序列建模中處理長距離依賴的強(qiáng)大能力，提出了一個專為動態(tài)圖建模定制的簡單而有效的 Transformer 模型，無需復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)修改。

我們將動態(tài)圖重構(gòu)為序列建模任務(wù)，并引入創(chuàng)新的時間對齊技術(shù)，不僅捕捉了動態(tài)圖中固有的時間演變模式，還簡化了其演變過程的建模。所提方法靈活多樣，適用于各種應(yīng)用。通過在四個真實世界不同領(lǐng)域數(shù)據(jù)集上的實驗證明了模型的有效性。

02 研究背景

2.1 現(xiàn)有工作的不足

現(xiàn)有的動態(tài)圖建模工作主要分為兩類：

• 離散時間方法: （見圖 1a）將動態(tài)圖視為離散時間上的快照（snapshot）序列，采用結(jié)構(gòu)模塊（如 GNN）捕捉拓?fù)湫畔?，時序模塊（如 RNN）學(xué)習(xí)序列演變。缺點：丟失細(xì)粒度時間信息；
• 連續(xù)時間方法: （見圖 1b）專注于通過特定的時間模塊（如時間隨機(jī)游走或時間核函數(shù)）對連續(xù)時間模式建模。缺點：難以捕捉歷史圖的長期依賴。

此外， 大多數(shù)現(xiàn)有工作依賴消息傳遞 GNN 編碼動態(tài)圖結(jié)構(gòu)模式。盡管消息傳遞機(jī)制在圖建模中很強(qiáng)大，但它有一些局限性，如過度平滑和過度壓縮，隨著模型深度增加，阻礙了更深入和更有表現(xiàn)力的架構(gòu)的發(fā)展。

2.2 研究動機(jī)

為了應(yīng)對現(xiàn)有動態(tài)圖建模中的問題，我們借鑒了 Transformer 及其在 NLP 和 CV 領(lǐng)域的成功應(yīng)用。Transformer 架構(gòu)具有兩大優(yōu)勢：自然支持連續(xù)數(shù)據(jù)序列，無需離散快照；自注意力機(jī)制有助于捕捉長期依賴關(guān)系（見圖1(c)）。鑒于 Transformer 受過度平滑和過度壓縮問題的影響較小，我們自然地提出可否將Transformer 架構(gòu)用于動態(tài)圖建模? 有哪些挑戰(zhàn)? 如何解決?

2.3 挑戰(zhàn)及對策

?

保留歷史演變的計算成本問題：由于自注意力機(jī)制的計算成本較高，現(xiàn)有基于 Transformer 的圖模型僅適用于小型圖，限制了對大型動態(tài)圖的處理。我們引入一種新穎的策略，將每個節(jié)點的歷史交互圖看作 ego graph，大幅減小計算成本并保留完整的動態(tài)交互歷史。

通過將 ego graph tokenize 為適用于 Transformer 輸入的序列，我們實現(xiàn)了對整個時間線的信息保留，同時確保了可擴(kuò)展性，而無需修改原始 Transformer 架構(gòu)。

輸入序列之間的時間信息對齊問題：在動態(tài)圖中，不同 ego 節(jié)點的輸入序列享有一個共同的時間域, 然而在語言建?；蜢o態(tài)圖的序列中缺乏這樣的通用時間域，在很大程度上可以將它們視為相互獨立的。

如果不對原始序列進(jìn)行時間上的對齊，將無法區(qū)分不同時間間隔和頻率信息。為了解決這一挑戰(zhàn)，我們精心設(shè)計了特殊的時間 token，并將其巧妙地整合到輸入序列中，在實現(xiàn)全局對齊的同時，每個節(jié)點的局部序列仍然保留著時間順序。

03 方法介紹

我們提出了一種名為 SimpleDyG 的動態(tài)圖建模方法，采用原始 Transformer 架構(gòu)，充分發(fā)揮其在建模動態(tài)圖方面的潛力，整體框架如圖 2 所示，主要應(yīng)用于動態(tài)圖（見圖 2(a)）。

首先，針對每個節(jié)點，提取以其為中心的時序 ego-graph，涵蓋整個歷史交互（見圖 2(b)），將提取的 ego-graph 轉(zhuǎn)換為序列，同時保留時間順序。

其次，為了在不同 ego-graph 之間實現(xiàn)時間對齊，將時間線劃分為具有相同時間間隔的跨度，如圖 2(c) 所示。在 ego 序列中添加特殊的時間 token，使模型能夠識別不同時間跨度。

最后，將處理后的序列輸入到 Transformer 架構(gòu)中，用于執(zhí)行各種下游任務(wù)。

3.1 時序 ego-graph

?

對動態(tài)圖  中的每個ego節(jié)點 ，提取與  有過交互的節(jié)點，形成一個序列，作為 Transformer 的輸入 ，其中 是序列長度。為更好地建模輸入序列的模式，我們借鑒了 NLP 序列建模任務(wù)方法，引入一些為我們?nèi)蝿?wù)設(shè)計的特殊 token。最終構(gòu)建的輸入序列和輸出序列如下：

其中  和  是特殊 token，表示輸入歷史序列的開始和結(jié)束。 和  用于預(yù)測未來的鏈接節(jié)點。一旦生成了結(jié)束特殊 token，模型將停止預(yù)測，從而實現(xiàn)對未來交互數(shù)量的自動決策。

3.2 時序?qū)R

?

首先，將時間域  劃分為離散的、粗粒度的等間隔時間步長。注意，我們的方法與離散時間圖建模不同，因為在每個時間步內(nèi)部，我們考慮了不同鏈接的時間順序。

然后，我們引入了一種簡單而有效的策略，將動態(tài)圖中的時間對齊信息納入 Transformer 架構(gòu)的輸入序列中。我們設(shè)計特殊的時間 token，表示全局所有節(jié)點不同的時間步。

假設(shè)我們將時間域  分成  個時間步，時間步  中 ego 節(jié)點  的序列如下所示：

其中  表示節(jié)點  在時間步  的歷史序列，長度為 。是時間 token，用作時間對齊的指示器，使模型能夠識別和捕捉數(shù)據(jù)中的時間模式。

最后，我們將動態(tài)圖表示成序列，采用和 Transformer 架構(gòu)一樣的損失函數(shù)進(jìn)行訓(xùn)練。

04 實驗

我們在四個基準(zhǔn)數(shù)據(jù)集上進(jìn)行了全面的實驗，以評估所提出的  在動態(tài)圖鏈接預(yù)測任務(wù)上的有效性。

4.1 實驗對比

實驗結(jié)果見表 2，總體而言，我們的方法在所有數(shù)據(jù)集上均優(yōu)于對比方法，我們得出以下觀察：

首先，各種場景中連續(xù)時間方法通常優(yōu)于離散時間方法，突顯了時間信息在動態(tài)圖分析中的重要性。尤其是像 GraphMixer 等簡單的 MLP-Mixer 架構(gòu)表現(xiàn)出更高性能，其較低的復(fù)雜性有助于捕捉長期歷史序列。

相反，其他模型如 DyRep、TGAT 和 TGN 依賴于復(fù)雜的設(shè)計（如 GNN 和 GAT），表現(xiàn)較差，這可能因為它們在捕捉長距離依賴關(guān)系上的固有局限性。

其次，對于歸納場景（即測試集包含新節(jié)點，如 Hepth 數(shù)據(jù)集），采用基于 GNN 的骨干結(jié)構(gòu)的連續(xù)時間模型相比 GraphMixer 表現(xiàn)出更高的性能。這是因為為了能夠處理新節(jié)點，我們使用 word2vec 構(gòu)建初始節(jié)點特征，這可能相對粗糙。

由于 GraphMixer 主要依賴于基于 MLP 的架構(gòu)，使用粗粒度的初始特征可能會遇到挑戰(zhàn)。相比之下，基于 GNN 的方法將結(jié)構(gòu)信息與這些特征整合在一起，從而使它們在歸納場景中表現(xiàn)出色。然而，在我們基于 Transformer 的模型中，還有建模長距離依賴性的附加優(yōu)勢，因此 SimpleDyG 的性能始終更好。

4.2 額外token分析

?

4.2.1 特殊token分析

?

特殊 token 包括歷史序列的開始和結(jié)束（ 和 ），以及預(yù)測未來序列的開始和結(jié)束（ 和 ）。為全面評估它們在不同場景下的效果，我們在兩個模型變體上進(jìn)行了實驗：

• same special，對輸入和輸出使用相同的特殊 token
• no special，完全刪除每個樣本中的所有特殊 token

結(jié)果如表 3 所示，總體而言，特殊 token 可以增強(qiáng)不同數(shù)據(jù)集上的鏈接預(yù)測性能。此外，same special 和原始的 SimpleDyG 之間的差異往往較小。然而，在 Hepth 數(shù)據(jù)集上有一個有趣的發(fā)現(xiàn)，其 no special 模型性能更好，這是因為 Hepth 測試集中的 ego 節(jié)點都是新出現(xiàn)的節(jié)點（表示新發(fā)表的論文），因此輸入樣本缺乏歷史信息，區(qū)分歷史和未來序列預(yù)測之間的區(qū)分不太相關(guān)。

4.2.2 時間token分析

?

為了全面評估時間 token 的影響，我們將性能與兩個變體進(jìn)行了比較：

• same time，不區(qū)分特定的時間步，對每個時間步使用相同的時間 token
• no time，完全刪除每個樣本中的所有時間 token。

結(jié)果如表 4 所示，我們得出以下觀察：

令人驚訝且有趣的是，使用更簡單的設(shè)計進(jìn)行時間對齊會有性能的提升。這種現(xiàn)象在 MMConv 多輪對話數(shù)據(jù)集和 Hepth 論文引用數(shù)據(jù)集中最為明顯，這是因為不同 ego 節(jié)點之間的對話和論文引用關(guān)系并不嚴(yán)格遵循時間順序，使用相同的時間 token 或不使用時間 token 可以讓模型更自然地適應(yīng)這種時間順序。

對于 UCI 和 ML-10M 數(shù)據(jù)集，時間對齊起著重要的作用。然而他們在 same time 模型上的性能變化趨勢不同，原因在于 UCI 數(shù)據(jù)中不同用戶的通信習(xí)慣對于不同 time steps 的切分是敏感的，因此，same time，因為它將序列劃分為 time steps，但沒有不同時間 token 在序列之間進(jìn)行對齊，額外的相同時間 token 可能會使模型混淆。

另一方面，no time 仍然保留完整的時間順序，因此表現(xiàn)優(yōu)于 same time。

更多實驗分析詳見原始論文。

05 總結(jié)與展望

在這項工作中，我們深入研究了復(fù)雜的動態(tài)圖建模領(lǐng)域，利用 Transformer 自注意機(jī)制的優(yōu)勢，我們?yōu)閯討B(tài)圖建模量身定制了一種解決方案，避開了現(xiàn)有方法中常見的復(fù)雜設(shè)計。

我們的方法從序列建模的角度出發(fā)，對動態(tài)圖進(jìn)行重構(gòu)，并引入創(chuàng)新的時間對齊策略。這種設(shè)計不僅捕捉了動態(tài)圖中固有的時間演變模式，而且簡化了它們的建模過程。在四個不同領(lǐng)域的真實數(shù)據(jù)集上的實驗驗證了我們模型的有效性。在未來，我們將深入研究時間對齊策略，以進(jìn)行進(jìn)一步的優(yōu)化。此外，可以探索整合更先進(jìn)的注意力機(jī)制，以進(jìn)一步提升模型在捕捉動態(tài)演變方面的能力。

本文轉(zhuǎn)自 PaperWeekly ，作者：吳玉霞

原文鏈接:??https://mp.weixin.qq.com/s/14SCdRg52l0xShRW2jH9vQ??