迈向更好的动态图学习：新的模型框架和统一的模型库

©PaperWeekly 原创 · 作者 | 于乐

单位 | 北京航空航天大学

研究方向 | 动态图表示学习

论文题目：

Towards Better Dynamic Graph Learning: New Architecture and Unified Library

论文链接：

https://arxiv.org/abs/2303.13047

代码链接：

https://github.com/yule-BUAA/DyGLib

背景和动机

动态图由于在各类现实场景中的广泛存在，已引起了许多学者的关注。动态图可分为离散时间型和连续时间型两种。由于后者具有更强的灵活性，本工作研究面向连续时间型的动态图方法。动态图表示学习方法至今虽然已取得了较大的发展，但仍存在以下两个缺陷：

缺乏节点间的关系刻画以及难以建模长时依赖。现有方法独立地学习各节点的表示，而忽略了节点之间的相关性，而这些关联通常对于未来的交互具有提示作用。同时，现有方法遵循 interaction-level 的学习范式，因复杂的模型计算量以及在优化中的梯度问题等而导致无法处理较长的节点交互序列，故难以建模长时依赖关系。
缺乏统一的动态图模型库。大多数动态图表示学习方法重点关注于模型的设计，而模型训练、模型实现和模型评估等并不统一，这大大增加了研究人员的学习与使用成本。虽然已有一些动态图模型库，但它们的研究重点是面向动态网络的 embedding 方法、面向离散时间型动态图的学习方法或是如何在大规模动态图上进行训练的工程化技巧，并非本工作所研究的连续时间型动态图。

对于以上两个挑战，本工作提出了：1）一个基于 Transformer 的新型动态图学习框架，旨在同时刻画节点间的关系以及建模节点历史交互中存在的长期时序依赖；2）一个统一的动态图模型库，用以促进可复现、易扩展和更可信的动态图学习研究。

新的模型框架和统一的模型库

2.1 模型框架介绍

本工作提出的 DyGFormer 模型基于 Transformer 架构，仅需在节点的历史一阶交互序列进行学习，将动态图表示学习问题转化为一个更简单的序列学习任务，模型架构如图 1 所示。

给定某个交互中的源节点 u 和目标节点 v，首先提取两个节点的历史一阶交互序列。而后除了对序列中的邻居、连边以及时间信息进行编码，本工作设计了一个邻居共现频率编码方法来刻画节点间的相关性。此外，本工作利用了 patching 技术，将各序列划分为多个 patches 后再输入 Transformer 模型，使模型能更有效且更高效地处理较长的序列。

▲ 图1 DyGFormer模型架构图

邻居共现频率编码方法。本工作的研究者认为一个邻居在节点历史交互序列中出现的频率反映了其重要性，而在 u和 v 历史序列中同一邻居的共现频率揭示了 u 和 v 之间的相关性。换言之，如果 u 和 v 有更多共同的历史邻居,则这两个节点更有可能在未来发生交互。

基于此，研究者首先为每个历史邻居统计出其在 u 和 v 两个序列中分别出现的次数（即二维的向量），而后通过如下函数 f 对于该向量进行编码。函数 f 计算了每个邻居在 u 和 v 序列中的出现信息，有助于刻画 u 和 v 序列之间的相关性。同时该编码方法具有通用性，可以整合至现有的动态图学习方法来提升性能。

Patching 技术。相较于现有方法 interaction-level 的学习范式，本工作将节点的历史序列划分为多个不重叠的 patches（每个 patch 包含多个在时间上相邻的 interactions），从而在 patch-level 进行学习。所提出的 patching 技术有如下优势：保持每个 patch 内的时间局部邻近性来帮助模型更好地从序列中挖掘有效信息；将模型的计算复杂度降低到与输入序列长度无关的常数级别，使模型可以更高效地处理较长的序列。

经过上述的步骤，可以分别为节点 u 和v得到四个 patches 序列（包括邻居特征、连边特征、时间特征以及邻居共现频率特征）。在将这些序列经过特征维度对齐、特征级联后输入到 Transformer，最终得到 u 和 v 的表征。

2.2 模型库介绍

本工作提出的统一模型库 DyGLib 具有标准的训练流程、易扩展的编码接口和全面的评估策略，总体流程如图 2 所示。

▲ 图2 DyGLib模型库流程图

标准的训练流程。DyGLib 统一了数据格式和数据加载过程，使用相同的流程训练所有模型。标准的训练流程保证了结果的可复现性，帮助用户快速发现模型的关键设计。研究人员只需关注模型架构的设计，而无需考虑其他无关的实现细节。

易扩展的编码接口。DyGLib 基于 PyTorch 为数据集和算法提供可扩展的编码接口，使得用户能根据自身需求添加新的数据集与模型。这大大减少了初学者的使用难度，并使专业人员更方便地验证新想法。目前，DyGLib 整合了来自各个领域的 13 个数据集和 9 种连续时间型动态图表示学习方法。

全面的评估策略。DyGLib 支持动态图学习中常见的动态链接预测（transductive和 inductive）和动态节点分类任务。此外，DyGLib 内置了多种评估策略（random、historical、inductive 负采样策略），使各模型能被更全面地评估，以提供更可信的对比结果。

实验结果

本工作使用的 13 个数据集的统计信息如表 1 所示。

▲ 表1 数据集统计信息

3.1 与现有模型的性能对比

DyGFormer 在动态链接预测（表2）和动态节点分类任务（表3）上的表现均优于现有模型，这表明了 DyGFormer 在动态图学习任务上的优越性，也揭示了所提出的邻居共现频率编码方法与 patching 技术的有效性。

此外，实验中的某些观察与先前工作的结论有所不同。例如通过设置合适的超参数，某些基准方法的性能会显著提高；在修复了基准方法在模型实现中存在的问题后，其结果会变差。这些现象说明使用统一模型库的必要性，验证了引入 DyGLib 的意义。

▲ 表2 动态链接预测任务实验结果

▲ 表3 动态链接预测任务实验结果

3.2 邻居共现频率编码方法通用性

为验证所提出的邻居共现频率编码方法的通用性,本工作将该编码方法与基于序列学习的动态图模型（TCL 和 GraphMixer）相结合，结果如表 4 所示。实验结果显示当采用邻居共现频率编码时，TCL 和 GraphMixer 通常可以获得更好的结果，验证了该编码方法的有效性和通用性，同时也突出了刻画节点之间关系的重要性。

▲ 表4 现有方法在整合邻居共现频率编码方法后的实验结果

3.3 Patching技术的优势

本节旨在验证 patching 技术的两个优势。

1）保持每个 patch 内的时间局部邻近性来帮助 DyGFormer 更有效地利用较长的序列。各模型在不同输入长度下的表现如图 3 所示。结果显示大多数基准方法在输入变长时性能会下降，说明它们缺乏捕捉长期时间依赖关系的能力。

同时，基准方法在更长序列上会面临昂贵的计算成本。尽管基于记忆网络的方法能以可负担的计算成本处理更长的历史，但由于梯度消失/爆炸等问题,它们无法从更长的历史中获益。DyGFormer 能持续地从更长的序列中取得提升，证明 patching 技术在维持时间局部邻近性和处理更长序列方面的优势。

▲ 图3 在不同输入长度下各模型的表现

2）降低模型的计算复杂度使其能更高效地处理较长的序列。表 5 比较了 DyGFormer 在训练过程中是否使用 patching 技术下的运行时间和内存使用情况。可以观察到，patching 技术能有效降低模型的计算成本，使得 DyGFormer 可以处理更长的历史序列。此外，随着输入序列长度的增加，模型计算成本减少得更加明显。