'Si'multaneous 'S'patial-'T'emporal Message Passing for Dynamic Graph Representation Learning

本文介绍了 SiST-GNN，这是一种新颖的动态图神经网络，它通过引入跨时间边来增强图结构，将空间与时间消息传递统一为单一操作，从而在多种基准测试中实现了链接预测和节点分类的顶尖性能。

要点

想象一下，你正在尝试预测在一个庞大且不断变化的社交网络中，谁会与谁成为朋友。要做到这一点，你需要了解网络中每个人的两件事：

1. 他们此刻是谁：他们的当前档案、兴趣，以及他们在这一确切时刻正在与谁交谈（空间信息）。
2. 他们曾经是谁：他们在过去几个月里的整个友谊、争吵和互动历史（时间信息）。

长期以来，计算机科学家构建了“动态图神经网络”（DGNNs）来解决这个问题。然而，该论文指出，几乎所有现有方法都犯了一个关键错误：它们按顺序查看这两部分信息，就像一页一页地读书一样。

旧方法：装配线瓶颈

该论文描述了这些旧模型工作的两种常见方式，两者都存在“信息瓶颈”：

• “时间优先”工厂：想象一个工厂，一名工人首先阅读一个人的完整人生故事（历史）并写下一份简短的摘要笔记。只有在写下该笔记之后，第二名工人才会查看这个人此刻正在与谁交谈。
  • 问题：第二名工人无法问：“嘿，这个人正在和他以前的老朋友交谈，但他的当前档案显示他讨厌对方。”在看到当前语境之前，历史已经被锁在摘要笔记里了。
• “空间优先”工厂：想象相反的情况。一名工人首先查看这个人此刻正在与谁交谈并将他们分组。只有在完成该分组之后，第二名工人才会查看这个人的历史。
  • 问题：第二名工人无法说：“等等，这群人看起来很可疑，因为从历史上看，这个人从未与他们混在一起。”在查阅历史之前，当前的分组已经完成了。

在这两种情况下，模型都被迫基于过去或现在的“压缩”版本做出决定，错失了实时权衡它们的机会。

新方法：SiST-GNN（同时时空）

作者提出了一种名为SiST-GNN的新架构。与其说是装配线，不如想象一场圆桌讨论，每个人都可以同时发言。

以下是 SiST-GNN 的工作原理，使用一个简单的类比：

1. 孪生概念：对于网络中的每个人，模型创建一个“孪生体”。
   • 孪生体 A 持有该人的当前档案和当前朋友。
   • 孪生体 B 持有该人的完整历史（其过去的运行摘要）。
2. 增强图：模型构建了一个特殊的、更大的地图。在这张地图上，孪生体 A 和孪生体 B 相互连接。此外，孪生体 A 连接到孪生体 B 的邻居，孪生体 B 连接到孪生体 A 的邻居。
3. 同时聊天：现在，模型运行单个“消息传递”步骤。在这一步中，每个人（及其孪生体）同时与他们的邻居交谈。
   • 因为大家都在一起交谈，模型可以决定：“对于这个特定的预测，我应该更多地倾听孪生体 B（历史），因为当前的对话令人困惑”，或者“我应该更多地倾听孪生体 A（当前状态），因为历史已经过时了”。

模型不必先选择保留哪种信息；它可以同时权衡两者，就像法官在做出判决之前同时听取当前证词和过往记录一样。

结果：巨大的飞跃

作者在 9 个不同的真实世界数据集（包括比特币信任网络、大学留言板和 Reddit）上，将这种新的“圆桌”方法与 14 种不同的现有模型进行了测试。

• 链接预测（预测未来连接）：

  • 在“固定”测试（一次性查看整体情况）中，SiST-GNN 比之前的最佳方法提高了 109% 到 277%。
  • 在“实时”测试（随着新数据到来而更新，就像实时馈送一样）中，它提高了 68% 到 194%。
  • 类比：如果旧模型是以 50% 的准确率猜测天气，那么 SiST-GNN 就是以近乎完美的准确率进行猜测。

• 节点分类（发现异常）：

  • 该模型还接受了在连续数据流中识别“不良行为者”（如被禁止的用户）的测试。即使 SiST-GNN 必须将数据分组为时间块（就像将电子邮件放入每日文件夹中），它仍然比最好的“离散时间”模型高出 7% 到 22%。
  • 值得注意的是，它的表现与最先进的“连续时间”模型一样好，后者根本不需要将数据分组为块。

为什么这很重要（根据论文）

论文声称，这种巨大改进的原因不仅仅是模型更“聪明”或拥有更多的计算能力。而是因为架构终于允许模型将一个人的历史和他们的当前情况视为可以直接相互交谈的邻居。

通过消除“装配线”瓶颈，模型终于可以这样说：“我看到你现在正在和一个陌生人交谈，但你的历史显示你总是信任像这样的陌生人，所以我会信任这次互动。”或者相反：“你正在和一个朋友交谈，但你的历史显示你们刚刚闹翻了，所以我会持怀疑态度。”

该论文得出结论，这种“同时”方法是一个根本性的升级，适用于不同类型的网络和任务，为如何教导计算机理解不断变化的关系设定了新标准。

技术摘要

技术摘要：用于动态图表示学习的 SiST-GNN

问题陈述

在图快照序列上运行的动态图神经网络（DGNN）目前面临一个根本性的架构限制：由刚性顺序处理引起的信息瓶颈。现有方法普遍采用以下两种范式之一：

1. 时间优先（T→S）： 首先通过循环或注意力模块编码节点特征轨迹，生成时间摘要，随后将其输入图神经网络（GNN）进行空间聚合。
2. 空间优先（S→T）： 首先在单个快照内聚合邻居特征，然后将生成的结构嵌入交由时间模块（如 GRU、LSTM）处理。

在这两种情况下，第二阶段必须消耗第一阶段生成的预压缩摘要。这种顺序阻碍了对拓扑结构和演变的联合推理。具体而言，空间优先模型无法将其消息传递算子条件化于邻居的历史轨迹，因为该信息尚未计算；反之，时间优先模型无法将其循环单元条件化于当前的结构邻域。这种刚性迫使模型在结构信号和时间信号之间做出选择，而不是根据每个邻居的具体上下文动态地加权它们。

方法论：SiST-GNN

作者提出了SiST-GNN（同时空间 - 时间 GNN），这是一种在单次消息传递操作中融合空间和时间信号的第三种范式。

核心架构

SiST-GNN 不再串联模块，而是在每个快照 $t$ 构建一个时间增强图（$\hat{G}_t$）：

1. 节点扩展： 对于包含 $N$ 个节点的图，增强图包含 $2N$ 个节点。前 $N$ 个节点携带当前空间特征（$X_t$），随后的 $N$ 个节点携带循环隐藏状态（$H_t$），总结每个节点直到 $t-1$ 的历史。
2. 边增强：
   • ** intra-time 边（同时间边）：** 原始边 $E_t$ 连接空间节点。
   • 跨时间边： 对于每条原始边 $(u, v) \in E_t$，添加新边，将 $u$ 的时间副本（节点 $u+N$）连接到空间节点 $v$ 以及空间节点 $u$ 本身。
   • 这种结构允许节点在单次图卷积步骤中，同时从其邻居的当前特征和历史摘要接收消息。
3. 消息传递： 标准 GNN（如 GCN、GraphSAGE）在 $\hat{G}_t$ 上运行。消息传递算子学习为每个邻居的空间消息（当前特征）和时间消息（历史轨迹）分配独立的权重。
4. 输出： 下一层的表示源自 GNN 输出的前 $N$ 个节点。循环状态通过在所有节点间共享的 LSTM 单元进行更新，保持置换等变性。

理论性质

论文提供了形式化证明，确立了以下性质：

• 严格泛化： SiST-GNN 是 T→S 和 S→T 两种范式的严格泛化。通过设置特定的门控参数（例如将跨时间边置零），SiST-GNN 可以模拟任一种顺序范式。然而，它也能表示这两种顺序范式都无法表示的函数，特别是那些需要对邻居的当前状态与其历史进行不同加权的函数。
• 消息多样性： 在单层中，SiST-GNN 每个节点传播 $2|N(u)| + 1$ 条消息（空间邻居、跨时间邻居和自身），而顺序模型最多传播 $|N(u)| + 1$ 条复合消息。
• 复杂度： 与空间优先基线相比，计算开销仅为常数倍。增强图包含 $2N$ 个节点和大约 $2|E| + N$ 条边，且 LSTM 成本与标准时间基线相同。

主要贡献

1. 瓶颈识别： 作者指出，空间和时序计算的严格顺序是快照式 DGNN 中共享的架构限制，阻碍了自适应消息加权。
2. SiST-GNN 架构： 他们实例化了一个可堆叠层，将循环单元与时间增强图上的图卷积融合，实现了空间和时间信号的同时交互。
3. 广泛的实证验证： 该模型在固定划分和实时更新协议下，针对 9 个公开基准测试，与 14 种基线（包括静态 GNN、时间优先、空间优先和元学习方法）进行了评估。
4. 动态节点分类： 该架构通过将连续时间事件流离散化为固定宽度的快照，被适配用于动态节点分类，证明了同时融合方法弥合了离散时间模型与连续时间模型之间的性能差距。

实验结果

动态链接预测

SiST-GNN 在所有数据集和评估模式下均实现了最先进（SOTA）的性能：

• 固定划分设置： 在平均倒数排名（MRR）上，比最强的先前方法（ROLAND-GRU）高出109% 至 277%。在密集信任网络（Bitcoin-OTC、Bitcoin-Alpha）上观察到了最大的提升。
• 实时更新设置： 在 MRR 上，比最强的先前方法高出68% 至 194%。该设置模拟了在线部署，模型必须在观察到新的真实标签之前进行预测。
• 鲁棒性： 该模型在所有数据集上均能高效地在单个 GPU 上运行，避免了 BPTT 训练的基线在大型、长视界数据集（如 AS-733 和 Reddit）上遇到的内存溢出（OOM）错误。

动态节点分类

该模型在 JODIE 基准测试（Wikipedia、Reddit、MOOC）上进行了测试，这些基准原本是连续时间流，被离散化为 6 小时的快照：

• 与离散时间（DTDG）基线相比： SiST-GNN 将测试 AUC 提高了7% 至 22%，优于领先的离散时间基线（如 EvolveGCN、ROLAND）。
• 与连续时间（CTDG）基线相比： 尽管 SiST-GNN 运行在离散化快照上而非原始事件流上，但其结果与消耗原生事件流的 CTDG 模型（如 TGN、TGAT）相当。这表明性能提升源于同时融合架构，而非时间接口。

意义与主张

论文声称，SiST-GNN 代表了动态图处理方式的根本性转变。通过将节点的时间状态及其空间邻域视为单个增强图中的“邻居”，该模型允许消息传递算子学习一种数据依赖的、针对每个邻居和每种模态的权衡。

• 自适应加权： 当当前特征信息量不足时，模型可以动态选择更多地关注邻居的近期历史；而当时间上下文过时，则依赖当前结构。
• 通用构建： 作者提出，这种“时间增强图”构建是一种结合演变信息和结构信息的通用技术，适用于所评估任务之外的场景。
• 局限性与未来工作： 作者承认，当前方法需要对连续时间数据进行离散化以进行节点分类，这丢弃了细粒度的事件排序。他们建议未来的工作可以涉及学习跨时间边上的稀疏掩码以扩展到更大的图，并将该构建扩展到原生连续时间流。他们还指出，他们的监督流程与最近的预训练和提示微调方法不可直接比较，这仍是一个开放方向。