論文題目：

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

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

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

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

02 研究背景

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

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

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

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

2.2 研究動(dòng)機(jī)

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

2.3 挑戰(zhàn)及對(duì)策

?

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

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

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

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

03 方法介紹

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

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

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

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

3.1 時(shí)序 ego-graph

?

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

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

3.2 時(shí)序?qū)R

?

首先，將時(shí)間域  劃分為離散的、粗粒度的等間隔時(shí)間步長。注意，我們的方法與離散時(shí)間圖建模不同，因?yàn)樵诿總€(gè)時(shí)間步內(nèi)部，我們考慮了不同鏈接的時(shí)間順序。

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

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

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

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

04 實(shí)驗(yàn)

我們?cè)谒膫€(gè)基準(zhǔn)數(shù)據(jù)集上進(jìn)行了全面的實(shí)驗(yàn)，以評(píng)估所提出的  在動(dòng)態(tài)圖鏈接預(yù)測(cè)任務(wù)上的有效性。

4.1 實(shí)驗(yàn)對(duì)比

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

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

相反，其他模型如 DyRep、TGAT 和 TGN 依賴于復(fù)雜的設(shè)計(jì)（如 GNN 和 GAT），表現(xiàn)較差，這可能因?yàn)樗鼈冊(cè)诓蹲介L距離依賴關(guān)系上的固有局限性。

其次，對(duì)于歸納場(chǎng)景（即測(cè)試集包含新節(jié)點(diǎn)，如 Hepth 數(shù)據(jù)集），采用基于 GNN 的骨干結(jié)構(gòu)的連續(xù)時(shí)間模型相比 GraphMixer 表現(xiàn)出更高的性能。這是因?yàn)闉榱四軌蛱幚硇鹿?jié)點(diǎn)，我們使用 word2vec 構(gòu)建初始節(jié)點(diǎn)特征，這可能相對(duì)粗糙。

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

4.2 額外token分析

?

4.2.1 特殊token分析

?

特殊 token 包括歷史序列的開始和結(jié)束（ 和 ），以及預(yù)測(cè)未來序列的開始和結(jié)束（ 和 ）。為全面評(píng)估它們?cè)诓煌瑘?chǎng)景下的效果，我們?cè)趦蓚€(gè)模型變體上進(jìn)行了實(shí)驗(yàn)：

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

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

4.2.2 時(shí)間token分析

?

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

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

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

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

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

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

更多實(shí)驗(yàn)分析詳見原始論文。

05 總結(jié)與展望

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

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

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

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