查看原文
其他

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

吴玉霞 PaperWeekly
2024-08-23


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

更多阅读



#投 稿 通 道#

 让你的文字被更多人看到 



如何才能让更多的优质内容以更短路径到达读者群体,缩短读者寻找优质内容的成本呢?答案就是:你不认识的人。


总有一些你不认识的人,知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁,促使不同背景、不同方向的学者和学术灵感相互碰撞,迸发出更多的可能性。 


PaperWeekly 鼓励高校实验室或个人,在我们的平台上分享各类优质内容,可以是最新论文解读,也可以是学术热点剖析科研心得竞赛经验讲解等。我们的目的只有一个,让知识真正流动起来。


📝 稿件基本要求:

• 文章确系个人原创作品,未曾在公开渠道发表,如为其他平台已发表或待发表的文章,请明确标注 

• 稿件建议以 markdown 格式撰写,文中配图以附件形式发送,要求图片清晰,无版权问题

• PaperWeekly 尊重原作者署名权,并将为每篇被采纳的原创首发稿件,提供业内具有竞争力稿酬,具体依据文章阅读量和文章质量阶梯制结算


📬 投稿通道:

• 投稿邮箱:hr@paperweekly.site 

• 来稿请备注即时联系方式(微信),以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信(pwbot02)快速投稿,备注:姓名-投稿


△长按添加PaperWeekly小编



🔍


现在,在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧


·
·
·

继续滑动看下一个
PaperWeekly
向上滑动看下一个

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存