A survey of dynamic graph neural networks

动态图神经网络综述

https://link.springer.com/article/10.1007/s11704-024-3853-2

摘要：

图神经网络（GNNs）已成为有效挖掘和学习图结构数据的强大工具，其应用覆盖众多领域。然而，大多数研究聚焦于静态图，忽视了现实世界网络中拓扑结构和属性随时间演变的动态特性。通过将序列建模模块整合进传统GNN架构，动态GNN旨在弥合这一差距，捕捉动态图固有的时间依赖性，从而更真实地刻画复杂网络。本文对动态GNN的基本概念、关键技术及前沿模型进行了全面综述。我们详细介绍了主流动态GNN模型，并根据时间信息的融入方式对模型进行了分类。同时，我们还探讨了大规模动态GNN及预训练技术。尽管动态GNN已展现出优越性能，但在可扩展性、异构信息处理及多样化图数据集缺乏等方面仍面临挑战。本文亦讨论了可能的未来研究方向，例如自适应与记忆增强模型、归纳学习及理论分析。

关键词：图神经网络，动态图，时序建模，大规模

1 引言

随着深度学习在各应用领域的显著进展，图神经网络（GNNs）已稳步成为解决复杂图结构数据问题的主流方案。在现实世界中，关键信息常以图的形式呈现，例如社交网络中的关系、交通系统中的道路与交叉口、以及生物信息学中的蛋白质相互作用网络。与静态图相比，动态图能够更真实地反映现实世界系统和网络，因为它可以建模随时间演化的结构与属性信息[1]。

动态图的节点和边可能随时间变化，使得传统静态GNN难以直接应用，这为动态图的分析与学习带来了新的挑战。近期，研究人员将GNN与序列学习相结合，开发出动态GNN模型，如广为人知的TGAT[2]、TGN[3]和ROLAND[4]。这些模型从邻近节点聚合特征，并引入时间序列模块，从而能够同时建模动态图中的结构特征与时间依赖性。因此，动态GNN可生成随时间演化的节点表示，准确捕捉时间进程。

尽管已有部分工作对动态图表示学习方法进行了综述[1,5,6]，但随着新方法和应用的不断涌现，现有综述内容已显陈旧，无法反映最新的研究进展与技术趋势。因此，本文对动态GNN模型的最新发展进行全面回顾，涵盖动态图的表示与建模技术，并对现有模型进行比较。现有方法的分类体系如图1所示。我们还探讨了新的研究方向，包括大规模应用和预训练策略，总结当前研究现状，并展望未来趋势。

受现有公开数据集的影响，节点分类和链接预测目前被广泛用作动态GNN的评估任务。它们是传统静态图学习任务在动态图上的扩展，其特征和标签可能涉及时间维度的变化。部分研究亦聚焦于特定领域的图数据，以完成诸如知识图谱补全[7]、股价预测[8]和交通流预测[9]等任务。需注意的是，文献中存在一类动态图，其图结构保持静态，但节点属性随时间变化。此类图被称为时空图，不在本综述的讨论范围之内。

本文主要贡献总结如下：

● 我们全面回顾了动态GNN的基本概念与特性，构建了动态GNN的知识体系，并系统性地研究了关键技术与模型。

● 我们详细介绍了当前主流的动态GNN模型，并深入分析了它们各自的优缺点。

● 我们探讨了该领域所面临的挑战，重点指出了潜在的未来研究方向与技术趋势。

本文其余部分组织如下：第2节首先介绍动态图的重要定义与背景知识；第3节阐述动态图表示学习的问题定义，并依据图1所示的分类体系全面回顾动态GNN；第4节聚焦于为大规模动态图设计的模型与系统；第5节总结常用数据集、预测任务与基准测试；我们发现，迁移学习与预训练等新技术近期正被应用于动态图学习问题，第6节对此进行了简要回顾；第7节讨论可能的未来研究方向；第8节对全文进行总结。

2 符号与背景

2.1 符号

2.2 动态图

动态图是指涉及时间演化的复杂图结构。在这些图中，图中的节点、边以及属性均表现出持续变化的状态。动态图在多个领域中常见，包括社交网络[10]、引文网络[11]、生物网络[12]等。以社交网络为例，新用户的注册会导致图中新增节点，而现有用户的停用则导致节点减少。此外，当一个用户关注或取消关注另一个用户时，这代表图中边的创建或消失。另外，诸如用户的年龄、位置和兴趣爱好等属性也可能随时间变化，表明节点属性也在动态演化。根据时间步长的粒度，动态图可分为离散时间动态图（DTDGs）和连续时间动态图（CTDGs）。

2.3 Hawkes processes

霍克斯过程由霍克斯在1971年提出[13]，是一种用于时间序列事件的数学模型。基于过去事件影响当前事件的假设，霍克斯过程模拟了一种具有潜在自激励模式的点过程。它适用于建模离散序列的演变。给定所有历史事件直到时间 t，在时间 t 的短时间内发生事件的概率可以通过霍克斯过程的条件强度函数来定义，表示为

最初，霍克斯过程被用于序列建模[14,15]。随着图表示学习的不断发展，HTNE[16]首次将霍克斯过程引入动态图表示学习中。它模拟了历史行为对当前行为的进化激励，从而模拟图生成过程。Lu等人[15]提出了一种动态图表示模型，该模型结合了宏观图演化与微观节点边预测，从而捕捉图结构的动态特性和图规模的上升趋势。

3 图表示学习

图表示学习的目标是构建节点的低维向量表示，同时保留结构、演化或语义特征等重要信息[17]。这已成为近年来图数据挖掘和分析中的关键问题。学习到的表示在各种任务中都有广泛的应用，包括节点分类、链接预测和推荐。

它作为原始图数据与图分析任务之间的桥梁，通过将每个节点编码到向量空间中。这种方法将图学习任务转化为机器学习应用中的相应问题。例如，我们可以通过使用学习到的表示作为传统机器学习算法的输入特征，来有效且高效地解决这些图分析挑战。此外，我们可以通过利用合适的分类和聚类技术来进一步增强这一过程，以完成节点分类和社区检测等任务。

近年来，图表示学习得到了广泛研究。早期方法试图将数据矩阵分解为低维形式，同时保留原始矩阵中固有的流形结构和拓扑属性。这种方法的突出例子包括局部线性嵌入（LLE）[18]和拉普拉斯特征映射（LE）[19]。这些基于矩阵分解的方法进一步发展为结合高阶邻接矩阵，从而保留图的结构信息，例如GraRep[20]和HOPE[21]。图嵌入的另一种策略是通过从随机初始节点遍历创建多条路径，以捕获关于全局和局部结构信息的上下文信息，即随机游走方法。概率模型如Skip-gram[22]和Bag-of-Words[23]随后被用来随机采样这些路径并学习节点表示，典型例子包括DeepWalk[24]和Node2vec[25]。深度学习技术的成功为基于深度神经网络的图表示学习技术铺平了道路。基于深度学习的图嵌入方法通常直接将深度神经网络应用于整个图（或其邻接矩阵），将其编码到低维空间中。在此领域，著名方法包括SDNE[26]、DNGR[27]、ChebNet[28]、GCN[29]、GAT[30]和GraphSAGE[31]。

3.1 动态图模型

根据定义1和2中描述的不同类型的动态图，动态图表示学习模型可以分为两个主要类别：离散时间动态图表示学习和连续时间动态图表示学习。前者将动态图划分为多个快照，这些快照可以被视为多个静态图。因此，为静态图设计的方法可以用来学习每个快照的表示，同时也分析不同快照之间的相互关系和演化趋势。在连续时间动态图中，图节点之间的交互被标记有时间戳，有效地根据其时间戳区分每条边。

连续时间动态图表示学习指的是利用边信息及其伴随的时间戳来学习表示的方法。

通过引入矩阵扰动理论，为静态图设计的基于矩阵分解的表示学习方法可以扩展到动态图的学习中。一些假设和操作构成了矩阵扰动理论的基础。首先，假设当前时间步的邻接矩阵是前一时间步矩阵的扰动版本。然后，对这两个矩阵进行常见的低秩分解，确保当前时间步的表示矩阵从前一时间步平滑更新。通过限制扰动的大小，可以在时间步之间调节表示的平滑度[32,33]。然而，这种方法更适合处理DTDGs，因为它可能面临高计算复杂性、实时更新困难以及在频繁变化的CTDGs中捕捉时间依赖性的不足等挑战。

通过要求在图上的随机游走严格遵循时间戳的顺序，可以在动态图上执行时间游走，特别适合CTDGs。例如，CTDNE[34]在采样过程中结合了一种具有时间信息的偏差采样机制，确保在较小时间间隔内采样边的概率更高。EvoNRL[35]则设计了针对动态图中不同场景的策略，即图中边或节点的添加和删除，每次变化时更新节点表示。

传统方法更频繁地依赖于手动设计的特定特征和定制模型，导致学习效率和适应性有限。基于深度学习原理，图神经网络（GNNs）在静态图中表现出显著的能力，能够学习复杂模式和特征，展现出改进的表示学习性能以及优越的泛化能力。因此，最近在动态图学习领域中，利用GNN启发的方法的兴趣日益增长。这些方法利用GNN的强大学习能力来增强对具有复杂时间演化模式的动态图的理解，这些模式被称为动态图神经网络（Dynamic GNNs）。最近，关于设计动态GNNs的工作激增。因此，我们在第3.2节和3.3节中介绍了处理DTDGs和CTDGs的动态GNNs。这两种方法捕捉了各种动态图中的典型演化模式，并在几个动态图分析任务中取得了优异的性能。为了突出每种方法的优势和劣势，我们在表2中提供了深入的比较，重点关注使用的模型基础、支持的类型以及处理的图事件类型。

3.2 用于DTDGs的动态GNNs

DTDGs由多个按时间顺序排列的快照组成，可以建模为序列数据，如定义1所述。因此，DTDGs中的时间模式通过不同快照之间的顺序关系来衡量。当前的研究方法涉及使用静态图神经网络模型来分别表示每个图快照。这些快照随后按时间顺序组织，并作为序列数据输入到序列模型中，以全面确定不同图快照之间的相互关系并学习时间模式。作为一种代表性的序列模型，递归神经网络（RNNs）通常与GNNs结合使用，形成DTDGs的主流动态GNNs。根据它们的组合方式，可以广泛地将其分类为堆叠架构或集成架构。

堆叠动态GNNs以模块化方式结合空间GNNs和时间RNNs来建模动态图的离散序列。如图3(a)所示，不同的组件分别用于空间和时间建模。具体来说，这些模型使用不同的GNNs在每个图快照上单独聚合空间信息。然后，来自不同时间步的输出被馈送到时间模块进行序列建模。因此，给定时间 t 的图 ，表示计算如下：

3.3 用于CTDGs的动态GNNs

如定义2所述，CTDGs不是以固定间隔存储的快照，而是每个事件记录为一个三元组（节点、事件类型、时间戳），例如，表示在时间 t 节点 u 和 v 之间的边插入事件。因此，连续动态图中的每个事件都有一个时间戳，这可以平滑地跟踪图结构的演变，并允许更准确地分析事件之间的时间关系和依赖性。此外，离散图同步聚合时间切片信息，无法区分事件的顺序，而连续图则指定了事件的时间顺序，并支持建模异步时间间隔。学习连续动态图的方法围绕如何有效地捕获和表征图结构随时间的演变展开，如图3(c)所示。目前，针对连续型动态图神经网络有三类方法：（1）基于时间点过程的方法，其中时间点过程由神经网络参数化；（2）基于RNN的方法，其中节点表示由基于RNN的架构维护；（3）基于时间随机游走的方法，其本质是通过时间随机游走捕获图的时间和结构属性。

基于时间点过程的方法。Know-Evolve[47]将知识图谱建模为交互网络，其中时间点过程用于建模事件的发生。它定义了一个双线性关系函数来表示节点之间的多关系交互。该方法的核心是将事实的发生建模为多变量时间点过程，其条件强度函数由相关关系得分调节。这种关系得分来源于动态演化的节点嵌入。此外，基于类似策略，Trivedi等人提出了DyRep[48]，一种用于建模多种图的方法。DyRep开发了一个成对强度函数，用于量化节点之间关系强度。它进一步采用自注意力机制来构建时间点过程，使模型能够优先考虑当前任务的相关信息，过滤掉不相关的细节。因此，节点 u 的结构嵌入定义为：

潜在动态图（LDG）[49]是DyREP[48]的增强版本，它整合了神经关系推理（NRI）[66]来编码时间交互，从而优化注意力机制并提高性能。图霍克斯神经网络（GHNN）[50]和图霍克斯变换器（GHT）[51]使用霍克斯过程建模节点之间的时间依赖性，并使用连续时间LSTM和Transformer分别估计强度函数来学习时间演化的节点表示。TREND[52]还设计了一个基于霍克斯过程的GNN来学习CTDGs的表示，其中每个节点嵌入的动态变化通过全连接层（FCL）学习，特征级线性调制（FiLM）用于学习FCL的参数。

基于RNN的方法。这些模型使用RNNs以连续方式维护节点嵌入，从而允许它们实时响应图变化并更新受影响节点的表示。具体来说，这些模型定义了一个RNN单元来跟踪每个节点嵌入的演变。当图发生变化时，RNN单元可以根据当前输入和前一时刻的隐藏状态计算当前时间 t 的新隐藏状态。因此，这些方法之间的一个主要区别在于它们如何定义嵌入函数和定制RNN。

DGNN[53]由更新组件和传播组件组成。在引入新边时，更新组件通过捕获边添加的顺序和交互之间的时间间隔来保持节点信息的新鲜度，由LSTM模型实现。传播组件通过考虑影响的强度将新的交互信息传播到受影响的节点。

JODIE[54]由两个操作组成：更新操作和投影操作。前者用于更新节点的嵌入信息，后者用于预测未来的嵌入轨迹。此外，每个节点都有一个静态嵌入来表示其固定属性，以及一个动态嵌入来反映其当前状态。JODIE专注于交互网络数据。在更新操作中，用户节点 u 和项目节点 i 的嵌入由两个具有相同结构但不同参数的RNNs更新：

受Time2Vec[67]的启发，TGAT[2]引入了一种基于Bochner定理[68]的时间编码函数，该函数可以将连续时间映射到向量空间。这种方法为自注意力机制内的位置编码提供了可行的替代方案，有效地利用时间信息。通过利用改进的自注意力框架，TGAT[2]提出了一种时间图注意力机制。

TGN[3]通过整合TGAT[2]、JODIE[54]和DyREP[48]的方法框架，提出了一种统一的方法，由五个核心模块组成：记忆、消息函数、消息聚合器、记忆更新器和嵌入。记忆模块存储有关节点的历史信息，嵌入模块生成实时表示。每当发生涉及节点的事件时，相应的记忆就会更新。此更新函数可以是学习模型，如RNNs或非学习模型，如平均或聚合，从而利用先前消息在训练期间刷新记忆，促进节点嵌入的生成。此外，TGN通过巧妙地架构每个模块，可以封装各种模型，包括JODIE[54]、DyRep[48]和TGAT[2]等。

在线训练期间，无法保证图更新事件按时间戳顺序到达，这将使RNNs生成的嵌入不稳定。ASPAN[55]通过采用异步传播机制解决了这一问题。它允许通过指定传播步骤的数量异步地在图中传播消息，从而确保事件按时间戳顺序存储。

基于时间随机游走的方法。受DeepWalk[24]和Node2vec[25]等模型的启发，Nguyen等人[34]首次提出了一种基于动态图属性的时间随机游走，其中随机游走由一系列具有非递减时间戳的边组成。因此，从一个顶点到另一个顶点的移动不仅由节点的邻接性决定，还由时间约束决定，确保游走与图的结构和时间序列一致。

从感兴趣的链接开始，因果匿名游走（CAW）[56]回溯几个邻近链接以编码网络动态中的潜在因果关系。在游走过程中，CAW[56]移除节点身份，而是根据其在一组采样游走中的频率对节点身份进行编码。这种相对节点识别方法确保在移除节点身份后保留模式结构及其相关性，实现基于集合的匿名性。为了预测两个节点之间的时间链接，提出了CAW-Network（CAW-N）模型。它采样与这两个节点相关的一些CAWs，分别对这些CAWs进行编码和聚合，以进行预测。

4 大规模动态图的处理与学习

对于管理大规模静态图，有几种策略。首先，为了提高处理效率，可以通过将图划分到多个设备上同时处理来实现分布式并行训练，这确保了数据完整性。其次，为了提高吞吐量和优化资源使用，广泛采用流水线并行、数据并行和模型并行等技术。第三，为了解决计算复杂性，同时保留关键数据的完整性，使用采样方法和邻居截断。同时，通常实施高效的通信方法，如点对点交换，以减少数据传输时间。

然而，在处理动态图时，管理大规模图变得更加具有挑战性。例如，如果我们采用小批量训练技术，模型必须保持足够的历史范围，优化节点的记忆更新机制，并在划分为子图后通过记忆同步传递信息。对于时间序列处理，主要方法包括使用时间编码捕获时间信息，按时间顺序生成数据批次，并确保所有数据以整体顺序遍历。总体而言，这些方法和基本前提有助于增强大规模动态图的并行性、可扩展性和高效处理能力。

现有方法可以分为两条主要路线。一种方法在设计动态GNNs时优先考虑可扩展性，从而产生各种旨在高效学习动态图的算法。第二种方法侧重于开发可扩展的训练框架，使现有算法能够适应大规模动态图。

4.1 动态图的可扩展GNNs

与其调整训练框架以适应大规模动态图学习中的现有算法，一些研究建议开发专门针对大规模动态图的算法。为了确保模型的效率和可扩展性，通常集成采样和并行训练等技术进行优化。按照此框架，SEIGN[45]采用无参数消息策略进行预处理，并使用Inception架构获取多尺度节点表示。与EvolveGCN[44]类似，SEIGN使用GRU模块更新每个图快照的卷积核权重以保持其新鲜度。然而，与演化整个GNN模型不同，SEIGN仅优化卷积核的参数，从而增强方法的可扩展性。此外，SEIGN引入了节点表示的演化，提高了最终节点表示的表达能力。此外，它促进了高效的图小批量训练，进一步提高了模型的可扩展性。

kkkEARLY[58]通过仅更新最容易受到事件影响的前k个节点来降低计算成本，以应对CTDGs中的频繁变化。这些顶级节点的选择由两个主要指标指导：局部和全局分数。局部分数强调图卷积网络的理论分析，解决节点更新的影响和随机游走概率的变化。另一方面，全局分数强调节点影响。最终，信息增益函数整合这些分数以识别最具影响力的顶级节点。

受静态图上可扩展GNNs[69]的启发，Zheng等人[59]提出了一种解耦GNN模型，将图传播过程与下游任务的训练过程分开，其中统一的动态传播过程可以高效处理连续和离散动态图。通过利用图传播过程的身份方程，模型定位受影响的节点并量化图变化对其表示的影响。其他节点表示在下一步中进行调整。这种方法允许从先前结果进行增量更新，避免昂贵的重新计算。此外，由于与图结构相关的计算仅在传播期间发生，因此后续的下游任务训练可以单独进行，而不涉及昂贵的图操作。因此，可以插入任意序列学习模型。同样，SDG[60]采用基于个性化PageRank的动态传播矩阵，替换APPNP[70]的静态概率转移矩阵。具体来说，SDG首先使用模型无关神经网络提取隐藏节点特征。然后，这些特征与动态传播矩阵相乘，以传播邻域节点信息。动态传播矩阵使用推出和加回算法跟踪图拓扑变化后随机游走的稳态分布，消除动态图中的冗余传播计算。

4.2 动态GNNs的可扩展训练框架

为DTDGs设计的框架 为了支持高效的模型并行性，内存管理优化是增强GNNs在DTDGs上训练效果的普遍方法。为了优化单个GPU上动态图神经网络的端到端训练性能，PiPAD[71]引入了流水线执行框架和多快照并行处理方式。此外，它采用基于切片的图表示来高效提取图的重叠部分，从而实现多个快照的同时并行计算。DGNNBooster[72]使用现场可编程门阵列（FPGA）来提高单个机器设置中动态图神经网络的推理速度。它还引入了两种不同的数据流设计来支持主流DGNN模型。Chakravarthy等人[73]采用梯度检查点和基于图差异的CPU-GPU数据传输等优化技术，以增强单节点多GPU系统上的动态GNN训练。此外，他们引入了一种使用快照分区训练大规模动态GNNs的算法，以在分布式多节点多GPU系统上高效训练。实验结果表明，与传统方法相比，该方法提供了显著的改进。

为CTDGs设计的框架 为了克服单机配置的限制并进一步提高动态图神经网络模型处理大规模动态图的可扩展性，更普遍的策略涉及将图划分到多个设备上进行并行训练。在此背景下，经常采用随机划分和基于顶点的分区。TGL[74]提出了一个通用框架来训练不同的动态GNNs，包括基于快照的、基于时间编码的和基于记忆的方法。设计了时间CSR数据结构以实现对时间边的快速访问，而并行采样器支持有效实现各种时间邻居采样算法。为了克服使用大批量训练时节点记忆的及时性问题，提出了一种随机块调度技术，从而实现大规模动态图上的高效多GPU训练。许多动态GNNs维护节点级记忆向量以总结每个节点的历史信息。为了有效维护和更新这些节点记忆，TGL设计了邮箱来缓存最新消息。在每个训练迭代中，从邮箱中读取最新消息，并通过某种组合器进行聚合。然后，节点的记忆状态通过GRU等序列模型进行更新。这种设计避免了使用最近的记忆状态直接生成邮件，有效避免了潜在的信息泄露。

此外，它还结合了异步机制来更新节点状态，使其更好地与流式或批处理训练过程对齐。

为了进一步提高效率，DistTGL[75]实现了一种机制，其中记忆操作被序列化并通过单独的守护进程异步执行，避免了复杂的同步要求。DistTGL[75]在动态GNNs中结合了额外的静态节点记忆，这不仅提高了模型的准确性，还加速了其收敛速度。还提出了两种新的训练方法，即时间段并行和记忆并行。这两种方法使在多个GPU上捕获与单GPU训练相当的图事件依赖性成为可能。利用预取和流水线技术来减轻与批处理形成相关的成本，并促进与GPU训练的重叠。DistTGL[75]框架在收敛速度和训练吞吐量方面提供了显著的增强，与TGL[74]相比。这使得基于记忆的动态GNNs训练能够在分布式GPU集群上高效扩展，实现了接近线性的加速比。通过采用针对特定数据集和硬件属性量身定制的各种并行化算法，提供了识别最有效训练配置的指导。

相比之下，SPEED[76]框架引入了一种流式边分区模块，通过指数衰减技术整合时间信息。此外，它通过调节共享节点的数量有效最小化了复制比率。还采用了基于区间属性的顶点分区方法，结合了小批量之间的联合和异步流水线技术。这确保了大规模动态图在多个GPU上的高效并行训练。设计显著加快了训练速度并减少了单个GPU上的内存消耗。

Liu等人[77]提出了一种强调分层流水线并行的方法，集成了数据预取、跨小批量的联合流水线和异步流水线。此外，为了提高通信效率，他们引入了一种图和顶点分区策略以消除冗余。另一个框架STEP[78]为大规模动态图提供了一种无监督修剪方法。在每次图更新后，通过自监督对抗学习获取节点和边表示。此外，它根据其重要性选择边进行采样，从而生成一个称为底层图的图。STEP利用提供的图来训练一个基本修剪网络。这使得STEP框架能够有效管理从动态图中删除不必要的元素的过程，特别是在训练和推理阶段，特别关注新添加的边。

总体而言，这些先进的方法共同增强了动态图神经网络在分布式环境中的有效并行训练，每种方法都有其独特的优势和潜在用例，如表3所示。

5 数据集和基准测试概述

5.1 数据集

近年来，公开提供给公众的动态图数据集的数量和种类显著增加。这些数据集为研究人员验证和比较算法提供了宝贵的资源，从而促进了新研究方向的探索。表4包含了常用动态图数据集的基本特征。我们可以根据数据集的收集和存储方法将这些数据集分为连续时间动态图（CTDGs）和离散时间动态图（DTDGs）。然而，通过适当的处理，它们可以相互转换。从这些数据集中，我们可以观察到以下特征：

● 领域和应用。这些数据集涵盖了各种实际应用，识别或定义适当的特征也可能具有挑战性。

总体而言，目前可用的公共数据集为动态图的表示学习提供了多样化的资源。然而，这些数据集也表现出一些共同特征，例如缺乏节点和边特征，这为研究人员带来了挑战和机遇。这是因为在现实世界应用中收集特征通常成本高昂，仅从图结构变化中学习模式可以提高模型的泛化能力。如果未来出现具有广泛特征的新高质量公共数据集，将非常令人鼓舞，因为这将促进更多的研究项目。

5.2 预测问题

图学习任务包括三个层次：节点级、边级和图级[11]。在节点级任务中，主要关注单个节点的属性，包括节点分类、回归、聚类等。边级任务强调边的信息。例如，链接预测确定两个节点之间是否存在边，而链接分类识别边的类型或属性。图级任务分析整个结构，如对图进行分类（图分类）或预测其连续值（图回归）。图生成任务旨在生成新图。此外，还有专门的任务，如图生成，其目标是基于现有数据中观察到的特定标准或模式生成全新的图结构。

这三个层次的任务也存在于动态图中。与静态环境的主要区别在于图随时间变化，导致节点、边和整个图的属性同时发生变化。对于节点级任务，节点的属性和连接模式可能会发生变化，可能影响分类或回归分析的结果。在边级任务中，边的存在和属性可能随时间变化，例如，新的连接可能出现，而旧的连接消失。对于图级任务，随着新节点和边的添加，图的拓扑结构可能变得更加复杂，从而影响图分类、回归和生成的结果。接下来，我们将以链接预测、异常检测和社区发现为例，探讨动态图分析的具体应用场景。

动态图中的链接预测旨在基于先前时间步的连接预测未来图中的潜在边，也称为时间链接预测。这不仅需要当前图的结构特征，还需要识别其动态变化中的趋势。链接预测有广泛的应用。在引文网络中，通过检查作者不断演变的引用行为和研究重点的变化，我们可以预测他们可能在未来出版物中引用的作者。

动态图中的异常检测可以分为边异常检测和节点异常检测。边异常检测旨在识别动态图中偏离历史演变模式的边。这种不规则性可能源于恶意用户引入或操纵的连接。相反，节点异常检测侧重于识别与同行明显不同或表现出非典型行为的节点。异常检测有广泛的应用，特别是在欺诈检测和电子商务中。例如，在电子商务网站上，用户可能通过反复点击特定产品来操纵系统，人为地提高其受欢迎程度。他们还可以同时点击一个产品和另一个流行项目，欺骗推荐系统高估两者之间的相似性。这些连接被视为异常边，欺骗性用户被视为异常节点。

社区发现是理解复杂图的基本任务。社区结构通常在涵盖各种领域的现实世界网络中观察到，如社交、生物或技术领域。基于节点之间连接的密度，图可以划分为各种社区。通常，社区内的节点具有更密集的连接，而来自不同社区的节点之间的连接则较少。这种社区结构也存在于动态图中，但随着图结构的变化，社区配置可能会演变。识别和理解动态社区结构及其演变模式可以更深入地理解图及其社区形成，从而促进对图中潜在变化的预测。以社交网络为例，具有相似喜好和关注点的用户可以被分组到相同的兴趣群组中。通过识别这些群组，系统能够推荐符合他们兴趣的新连接或内容。

归纳/演绎设置。在归纳设置中，模型尝试在其最初训练的图上进行准确预测。它在图的特定部分上训练，同时完全了解整个结构，包括未标记的部分。相比之下，在演绎设置中，模型从指定的训练图学习，以便对独立的、完全未知的图进行可靠预测。在动态图中，节点和边随时间频繁变化，演绎设置的本质是模型有效地泛化到未见过的节点和动态演变的结构。

5.3 基准测试

过去，不同的方法有自己的配置和实现，这使得模型性能的直接比较变得复杂。最近的工作试图建立统一的训练和评估框架来纠正这一点。通过提供标准化数据集、同步预处理阶段和公平的训练策略，这些框架确保所有方法以相同的方式进行测试。然后，研究人员可以轻松地比较同一任务的不同模型，更清晰地指出每种方法的优点和缺点。这些努力表明，动态图领域的标准化趋势日益增强，这有利于不同方法的评估和比较。表5提供了这些基准测试的链接。

6 图处理中的高级技术

6.1 动态迁移学习

迁移学习利用在一个任务（称为源任务）上训练的模型的知识来促进另一个不同但相关任务（称为目标任务）的学习。核心思想是在源任务和目标任务之间共享特定知识。这一概念基于观察到各种任务经常共享潜在特征或模式。因此，一个任务的见解可能会使另一个任务受益[101,102]。动态迁移学习是为源域和目标域都演化的情景提出的迁移学习设置。在此背景下，目标域的当前状态依赖于其历史状态，不能直接转移。因此，动态迁移学习需要对源域和目标域中不断变化的数据分布进行持续的实时调整。它还要求将源域中不断演化的相关知识及时转移到同时变化的目标域，旨在优化目标任务的性能。主要挑战在于有效建模跨域演化并管理不同时间步长之间的时间相互依赖性。

动态迁移学习最初被引入以解决计算机视觉和自然语言处理领域的各种实际挑战。最近，研究人员试图探索其在图学习中的潜力。目前，图的动态迁移学习研究仍处于早期阶段。它主要涉及应用图以外的领域的想法，如使用LSTM或注意力机制来建模图的时间模式[103]。在图论领域之外，已经对动态源域非平稳性、目标域概念漂移和相关主题进行了大量研究。未来的研究应深入探讨图数据的特定属性，旨在设计更合适的动态迁移学习方法。这将进一步使动态迁移学习成为解决各种时间敏感的实际挑战的关键工具。

6.2 动态GNNs的预训练技术

通常，预训练模型在大规模数据集上训练以获得通用特征表示，然后在特定下游任务上进行微调以提高性能。起源于计算机视觉和自然语言处理领域，预训练模型在许多任务中取得了显著成功，如语义解析、图像分类和图像分割。随着图数据量的增加，最近将预训练模型引入图学习领域。相关工作通常采用自监督策略来设计预训练任务，如边生成[104]、属性掩蔽[104]和子图比较[105]。由于动态图中的节点和边随时间变化，这些模型面临描述时间依赖性的问题。因此，PT-DGNN[106]使用基于时间的掩蔽策略来预测最近的边或属性，学习图的时间演化规律。另一方面，CPDG[107]对比正负样本对。CPDG通过增强正样本之间的相似性和减少负样本之间的相似性来捕获时间和结构模式。此外，CPDG存储来自不同时间步的记忆状态，以帮助模型保留长期演化信息，进一步支持后续的下游任务。

然而，仍有许多挑战需要进一步研究。可扩展性是该领域的一个主要问题，关键问题是如何预先训练模型，以便它们能够有效地处理不同时间粒度的动态图，并仍然足够灵活以执行许多不同的下游任务。此外，动态图包含长期稳定性模式和短期变异性模式，这意味着模型需要进行调整。此外，每个节点的结构邻居信息至关重要，因此模型需要有效保留这些结构信息。在实际应用中，大规模动态图的预训练需要高效的采样和训练机制。同时，预训练模型学习到的时间模式应及时整合到后续任务中。

总之，当前的研究和应用主要集中在为动态图设计适当的预训练任务、采样策略和对比学习方法。目标是实现具有弹性的时间和结构描述，提高模型对各种任务的适应性。同时，重要的是有效包含持久和即时趋势，然后提高模型训练和迁移的效率。

7 未来趋势和挑战

7.1 更复杂的动态图

尽管近年来出现了一些大规模动态图数据集，但与静态图数据集相比，动态图数据集仍然缺乏多样性。这可能导致在多样化、真实世界的动态图应用中模型性能不足。

  • 首先，EdgeBank[100]的结果表明，在某些情况下，仅使用历史信息就能取得良好的结果。这表明当前数据集的复杂性可能不足以显著区分不同模型。因此，我们需要构建更具挑战性的数据集，包含更丰富的结构信息和时间演变模式，以更好地评估模型的建模能力。

  • 其次，像用户取关这样的操作在实际应用中很常见，但目前缺乏包含此类边删除数据的真实世界数据集。扩展数据集可能涉及收集和整合具有真实边删除操作的数据，以模拟现实世界中图数据的动态性。这有助于评估模型在处理边删除时的鲁棒性和性能。

  • 最后，当前工作中很少提到一些特殊图，如动态有向图[108]和动态异构图。未来，可以构建包含不同网络拓扑结构（例如小世界、无标度）的动态图数据集，并生成更多特殊图。

总之，需要更大规模、更丰富内容和更复杂结构的数据集，以促进动态图学习向处理真实世界复杂网络的发展。

7.2 动态GNNs的可解释性

与深度模型可解释性相关的框架和方法旨在帮助用户理解和信任这些模型，使它们能够更有效地应用。在静态GNN模型[109]的可解释性领域已经取得了一些进展，而动态GNNs的可解释性研究似乎仍处于早期阶段。Xie等人[110]提出了DGExplainer，旨在为动态GNNs提供可靠的解释。DGExplainer将动态GNN的输出激活分数重新分配给前一层的神经元，以计算输入神经元的相关性分数，从而识别链接预测和节点回归任务中的重要节点。DynBrainGNN[111]模型旨在提供预测和解释，包含用于精神疾病分析的动态全连接组（FCs）的内置可解释GNNs。这些研究表明，尽管动态GNNs的可解释性是一个相对较新且讨论较少的领域，但已经有一些研究试图解决这个问题。

7.3 动态图学习的LLMs

最近，大型语言模型（LLMs）在自然语言处理方面表现出显著的能力，在许多方面取得了突破，如文本生成[112]、问答[113]和对话任务[114]。研究人员试图将LLMs适应到更多领域，以利用其强大的预训练语言理解能力。LLM具有强大的少样本、上下文学习能力，通过精心设计提示技术，可以帮助动态图学习模型更好地理解空间和时间信息。例如，LLM4DyG[115]研究了仅提供一个示例可以显著提高LLM在多个动态图任务（如“何时链接”、“何时连接”、“何时关闭”、“周期性邻居”和“邻居”）的准确性。另一方面，LLM可以在给定上下文中执行推理并解决动态图相关任务。这一见解激发了LLM在动态图学习任务中的新应用，并可能改变相关领域的现有方法。尽管LLMs在动态图任务上表现出鼓舞人心的理解能力，但仍然面临以下挑战：

  • 处理大规模图。随着图尺寸的增长，LLM的性能显著下降[116]。原因可能是图尺寸的增加导致上下文信息激增，使得LLM难以捕捉关键信息。LLMs对大规模动态图的建模能力仍有待验证。

  • 计算效率。当前LLMs大多庞大且计算成本高昂。如何提高LLMs的计算速度并提高其学习动态图的效率是一个需要解决的问题。

  • 缺乏结构建模。LLMs缺乏明确建模图结构的能力，与GNNs相同。仅仅依赖上下文描述来获取信息可能不够充分和直接。因此，需要进一步研究以提高LLMs对图拓扑建模的能力。

8 结论

动态图神经网络是表示学习的最新发展，可以处理随时间演变的图结构，并在各个领域具有潜在应用。在本文中，我们对动态GNNs的关键问题进行了全面调查，包括预测任务、时间建模方法和大规模动态图的处理。我们总结了当前研究的主要进展，并指出了一些有希望的关键方向，例如扩展现有模型的范围和研究动态GNNs的表达能力。动态GNNs仍然面临挑战，如可扩展性、理论指导和数据集构建。我们希望本文能为该领域的研究人员提供有价值的参考，并促进与动态GNNs相关的理论和方法的进一步发展。未来研究的一个重要方向是继续扩大动态图表示学习的适用性，处理更复杂和多样化的动态图结构和演变模式，并使其成为一个具有广度和深度的统一表示学习框架。随着更多和更实际的应用涉及动态图分析，动态GNNs无疑将成为一个持续活跃且越来越重要的研究领域。

原文链接：https://link.springer.com/article/10.1007/s11704-024-3853-2