WWW 2024 | 简单却强大：揭秘Transformer在动态图建模中的魔法

©PaperWeekly 原创 · 作者 | 吴玉霞单位 | 新加坡管理大学博士后研究方向 | 图数据挖掘

论文题目：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/

摘要

动态图建模在理解 Web 图中的复杂结构方面至关重要，涉及社交网络、推荐系统等多个应用领域。现有方法主要注重结构依赖性及其时序变化模式，但通常忽略详细的时间信息或难以处理长期依赖问题。此外许多方法过于依赖复杂的模块设计来捕捉动态图的演变。本研究充分利用 Transformer 的自注意机制在序列建模中处理长距离依赖的强大能力，提出了一个专为动态图建模定制的简单而有效的 Transformer 模型，无需复杂的网络结构修改。我们将动态图重构为序列建模任务，并引入创新的时间对齐技术，不仅捕捉了动态图中固有的时间演变模式，还简化了其演变过程的建模。所提方法灵活多样，适用于各种应用。通过在四个真实世界不同领域数据集上的实验证明了模型的有效性。

研究背景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，并将其巧妙地整合到输入序列中，在实现全局对齐的同时，每个节点的局部序列仍然保留着时间顺序。

方法介绍

我们提出了一种名为 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 架构一样的损失函数进行训练。

实验我们在四个基准数据集上进行了全面的实验，以评估所提出的在动态图链接预测任务上的有效性。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。

更多实验分析详见原始论文。

总结与展望在这项工作中，我们深入研究了复杂的动态图建模领域，利用 Transformer 自注意机制的优势，我们为动态图建模量身定制了一种解决方案，避开了现有方法中常见的复杂设计。我们的方法从序列建模的角度出发，对动态图进行重构，并引入创新的时间对齐策略。这种设计不仅捕捉了动态图中固有的时间演变模式，而且简化了它们的建模过程。在四个不同领域的真实数据集上的实验验证了我们模型的有效性。在未来，我们将深入研究时间对齐策略，以进行进一步的优化。此外，可以探索整合更先进的注意力机制，以进一步提升模型在捕捉动态演变方面的能力。

更多阅读