专题解读 | 动态图计算技术研究进展

文摘   2024-12-05 10:01   安徽  

动态图计算技术研究进展

动态图(Dynamic Graph)计算是图数据处理的一个重要研究领域,近年来得到了广泛关注和研究。动态图计算主要关注随时间变化的图结构和属性,旨在从时间变化的图中学习和推断有用的信息。近年来动态图计算技术已日趋成熟。根据时间粒度和模型构建的方式,动态图学习方法由简单的离散时间动态图向连续时间动态图转变,连续时间动态图直接处理图中的事件序列,从而更精确地捕捉时序依赖。最新的一些连续动态图研究已经能够在单个预测任务下达到卓越的性能。另一方面,现有动态图方法在单一任务上的极致性能也让众多研究者开始将目光转向如何处理多个不同的下游任务上来。最新的一些工作开始借鉴通用静态图模型,使用“预训练+微调”的方式使训练有素的动态图预训练模型迁移到不同的下游任务上。基于上述两方面,本文将分别介绍近期最有代表性的动态图计算方法与动态图微调技术。

一、背景

1.1 连续时间动态图(Continuous-Time Dynamic Graph, CTDG)

动态图建模分为离散和连续两种方式:离散动态图将时间划分为多个时间片,每个时间片是一个静态图,方法简单但无法精确捕捉连续变化;连续时间动态图是一种精确建模图随时间变化的方式。与离散时间动态图(Discrete-Time Dynamic Graph, DTDG)相比,CTDG更关注时间的连续性,能够捕捉事件发生的精确时间戳和顺序。连续时间动态图由一个时间维度 t 和一组随时间变化的图元素(节点、边、属性)组成。每个事件都与一个时间戳相关联,表示事件发生的具体时刻。图的变化通常以事件流(event stream)的形式表示,如  (),表示节点 在时间 有交互

1.2 动态图预训练与图提示

最近的动态图方法采用预训练范式来通过迁移学习解决不同的任务。具体来说,他们使用监督链接预测任务对模型进行预训练。当面对各种下游任务时,他们冻结预训练模型的参数,并使用从预训练模型获得的节点时间嵌入重新训练下游任务分类器,以实现跨不同任务的迁移。

然而,如上所述,当前方法在预训练阶段主要依赖于标记的监督学习任务,其中节点时间嵌入携带特定的任务信息,导致其他任务的性能低下。因此,使用与任务无关的自监督信号来协助模型预训练至关重要。它不仅可以在各种下游任务中实现更好的性能,而且还可以在标签有限的场景中提供稳健性。

此外,为了使模型更好地适应不同的下游任务,最新的一些工作开始使用图提示调整来弥合动态图上下游任务和预训练模型之间的差距。它旨在冻结预训练模型参数的基础上,使用少量数据进一步针对特定的下游任务进行额外的少量参数的微调,使得预训练模型更好地在下游任务间进行迁移。这一训练范式在静态图中已经被证明有效并取得了巨大的成功。

二、Towards Better Dynamic Graph Learning: New Architecture and Unified Library(NIPS 2023)

本文提出了一种新的动态图学习架构DyGFormer,基于Transformer,仅通过学习节点的历史一跳交互来工作。DyGFormer包括邻居共现编码方案和序列分段技术,可以有效地利用更长的历史信息。同时,文章还介绍了DyGLib,这是一个具有标准化训练流程、可扩展编码接口和全面评估协议的统一库,以促进动态图学习研究的可重复性、可扩展性和可信度。通过在十三个数据集上进行详尽的实验,证明了DyGFormer在捕捉节点相关性和长期时间依赖性方面的有效性,并在大多数数据集上取得了最先进的表现。此外,基线的部分结果与前人报告不一致,可能是因为实现上的多样性和不够严格,这凸显了DyGLib的重要性。

2.1 DyGFormer: 基于Transformer的动态图学习架构

DyGFormer架构通过以下步骤学习节点历史交互序列:

1. 提取历史交互序列

  • 对于每个节点,DyGFormer提取它们在特定时间戳t之前的历史交互序列,这些序列只包含节点u和v的直接邻居(即一跳邻居)的交互,以及节点u和v自身作为源节点或目标节点的交互。这种方法简化了问题,使其成为更简单的序列学习问题。

2. 编码邻居、链接和时间间隔

  • DyGFormer对每个序列中的邻居、链接和时间间隔进行编码。邻居编码将邻居的节点特征转换为向量表示,链接编码将链接边缘特征转换为向量表示。
  • 时间间隔编码将时间间隔转换为向量表示,以捕捉时间序列中的周期性模式。

3. 邻居共现编码

  • DyGFormer使用邻居共现编码来捕捉节点u和v之间的相关性,这种编码考虑了邻居在节点u和v的序列中出现的频率,如果节点u和v有更多的共同邻居,那么它们之间在未来建立链接的可能性更大。
  • 邻居共现编码同样被转换为向量表示,以捕捉节点之间的相关性。

4. 分块技术

  • DyGFormer使用分块技术将编码后的序列分割成多个patch块,这些块是时间上相邻的交互序列的集合,并保留了局部时间邻近性。
  • 这种技术允许DyGFormer有效地利用更长的历史记录,同时保持计算复杂度不变。

最终DyGFormer将上述各个特征表示使用Transformer编码器来捕捉序列中的长期时间依赖关系,通过自注意力机制和前馈网络学习序列中的复杂模式,并获取时间感知节点表示。这些表示可以用于各种下游任务,例如动态链接预测和动态节点分类。

2.2 DyGLib: 连续时间动态图的统一仓库

DyGLib库是一个用于动态图学习的开源工具包,旨在促进研究的可重复性和可扩展性。DyGLib提供统一的训练流程,包括数据加载、模型训练、评估和结果可视化,这有助于确保不同研究之间的结果可重复性。DyGLib使用PyTorch实现,提供可扩展的编码接口,允许用户:

  • 添加新的数据集:用户可以轻松地将新的数据集集成到DyGLib中,并使用标准化的流程进行训练和评估。
  • 添加新的模型:用户可以轻松地将新的动态图学习模型集成到DyGLib中,并与其他模型进行比较。
  • 修改模型配置:用户可以轻松地修改模型的超参数,例如学习率、批大小和序列长度。

此外,DyGLib支持多种评估指标,例如平均精度、AUC-ROC和F1分数,用于评估动态链接预测和动态节点分类任务。

实验结果表明,DyGFormer在13个数据集上进行的动态链接预测实验表明,DyGFormer在大多数情况下都优于其他方法,在平均精度(AP)和AUC-ROC等指标上取得了最佳性能。DyGFormer通过邻居共现编码有效地捕捉了节点之间的相关性,从而提高了预测的准确性。分块技术和Transformer编码器使DyGFormer能够有效地学习序列中的长期时间依赖关系,从而提高了模型对时间变化的鲁棒性。此外,我们注意到目前模型在动态链路预测任务上的性能已经接近瓶颈,然而当模型直接迁移到其他任务时,其效果往往不佳。

三、Prompt Learning on Temporal Interaction Graphs

在面对不同的下游任务时,重复训练模型的开销是巨大的,如何将一个训练有素的模型在不同任务间以最小的代价进行迁移是一个重大的问题。本文研究了在时间交互图(TIGs)上进行表征学习的问题,并指出现有TIG模型在“预训练-预测”范式下存在两个主要挑战:时间差异和语义分歧。针对这些问题,文章提出了一种新的框架——时间交互图提示(TIGPrompt),该框架能够整合到TIG模型中,有效弥补时间和语义上的差距。具体而言,研究设计了一个时间提示生成器,为不同任务提供具有时间意识的提示,并且这些提示设计简洁,只需要少量监督数据进行调整。此外,文章还提出了一种扩展的“预训练-基于提示的微调”范式,以适应不同的计算资源需求。

作为首个在动态图上使用图提示的方法,TIGPrompt具有设计简洁的动态图提示,通过对预训练动态图模型进行微调,TIGPrompt能够一定程度上提示针对于单个任务的模型在不同任务下的性能。

3.1TProG: 时间提示生成器

论文中提出了三种不同的TProG实现方式用于生产不同的动态图prompt,分别对应不同的复杂度和表达能力:

1. Vanilla TProG:

  • 原理: 为每个节点分配一个可学习的向量作为提示,通过微调该向量来学习任务特定的知识。
  • 优点: 简单直观,易于实现,参数量少,线性增长。
  • 缺点: 表达能力有限,无法捕捉时序信息。

2. Transformer TProG:

  • 原理: 利用Transformer编码节点最近邻的时序信息,生成时序提示。
  • 步骤
  1. 获取目标节点在当前时间戳的最近邻节点集合。
  2. 为每个邻节点生成一个时序邻居token,包含节点嵌入、位置嵌入、边特征和时间编码。
  3. 使用Transformer对时序邻居token进行编码,生成时序提示。
  • 优点: 能够捕捉时序信息和节点最近邻的交互信息,表达能力更强。
  • 缺点: 时间效率较低,Transformer计算复杂度较高。
  • 3. Projection TProG:

    • 原理: 结合个性化向量和时间编码生成时序提示。
    • 步骤
    1. 为每个节点分配一个可学习的个性化向量。
    2. 根据节点最近一次交互的时间戳进行时间编码。
    3. 使用MLP融合个性化向量和时间编码,生成时序提示。
  • 优点: 能够捕捉节点历史状态和时序信息,表达能力较强。
  • 缺点: 表达能力不如Transformer TProG,时间效率略高于Vanilla TProG。
  • 论文在四个常用的动态图数据集上分别对两个不同的下游任务进行了实验。论文中的实验结果表明,TIGPrompt在多个数据集和任务上都取得了显著的性能提升,尤其是在时序链接预测任务中,能够有效地捕捉时序信息,提高模型的预测准确性。

    然而,对于首个动态图提示方法,论文提出的图提示设计仍有很大优化的空间。例如Transformer TProG 仅考虑最近K个交互,可能无法捕捉更长时间范围内的时序模式。且设计仍相对简单,在各个任务上可能仍存在较大的进步空间。

    四、总结

    本文介绍了动态图计算技术的研究进展,具体来说,目前的研究一方面还在关注于在单个任务上挖掘更佳的时间特征来提高性能,尽管他们的性能已经接近瓶颈。另一方面,由于通用模型的发展,开始逐渐出现了一些工作尝试解决不同任务上的迁移与泛化问题。目前针对动态图提示的设计仍有优化的空间,而面对大规模图,少样本场景的设置与图提示的可解释性在未来的研究中可能具有更大的潜力。


    北邮 GAMMA Lab
    北邮图数据挖掘与机器学习实验室
     最新文章