图综述

A Comprehensive Survey on Graph Neural Networks

文献地址

摘要

传统深度学习任务中的数据通常在欧几里德空间中表示。然而越来越多的数据从非欧几里得域生成，并表示为具有复杂关系和对象之间相互依赖关系的图形。图数据的复杂性给现有的机器学习算法带来了重大挑战。

提出了新的分类方法，将最先进的GNN模型分为四类：递归图神经网络（RecGNNs）、卷积图神经网络（ConvGNNs）、图自动编码器（GAEs）和时空图神经网络（STGNNs）。

探讨了GNN在各种领域中的应用，如推荐系统、化学分子分析和引文网络分类。

总结了开源代码、基准数据集和模型评估方法。

提出了GNN领域的潜在研究方向，如模型深度、可扩展性、异质性和动态性等。

简介

深度学习在欧几里得空间成功

深度学习在图像分类、视频处理、语音识别和自然语言理解等领域的成功，这些领域的数据通常表示在欧几里得空间中。然而，越来越多的应用中，数据来自非欧几里得领域，并表示为图，这些图数据具有复杂的关系和依赖性。这种复杂性对现有的机器学习算法提出了重大挑战。

图数据的复杂性

与欧几里得数据不同，图数据是非结构化的。具体表现为：

• 图的大小和节点的数量是可变的。
• 节点之间的连接关系（邻接关系）也不固定。
• 图中节点和边的特征可以是高维的，且节点之间的依赖关系使得常规的机器学习方法难以直接应用。

例如

• 在电子商务中，基于图形的学习系统可以利用用户和产品之间的交互来做出高度准确的推荐。
• 在化学中，分子被建模为图形，需要确定它们的生物活性以发现药物。
• 在引文网络中，论文通过引文相互链接，需要将它们归类为不同的组。

现有方法的局限性

传统的机器学习方法在处理图数据时面临以下挑战：

• 图数据的非欧几里得特性使得卷积操作不再像在图像数据中那样简单有效。
• 现有方法假设数据实例是相互独立的，这在图数据中并不成立，因为每个节点（实例）都通过各种类型的边与其他节点相关联。

深度学习在图数据上的扩展

近年来，许多研究致力于将深度学习方法扩展到图数据上。受到卷积神经网络（CNNs）、递归神经网络（RNNs）和自动编码器（Autoencoders）成功的启发，研究者们开发了多种方法来处理图数据的复杂性。例如，图卷积可以从2D卷积推广到图卷积，通过加权平均节点的邻居信息来实现。

图神经网络的概述

本文对图神经网络（GNNs）在数据挖掘和机器学习领域的研究进行了全面综述。作者提出了一种新的分类方法，将最先进的GNN模型分为四类：递归图神经网络（RecGNNs）、卷积图神经网络（ConvGNNs）、图自动编码器（GAEs）和时空图神经网络（STGNNs）。

综述的贡献

本文的主要贡献包括：

• 新分类方法：提出了一种新的图神经网络分类方法，将GNN分为四类。
• 全面综述：提供了对现代深度学习技术在图数据上应用的最全面综述，包括代表性模型的详细描述、必要比较和相应算法的总结。
• 丰富资源：收集了关于GNN的丰富资源，包括最先进的模型、基准数据集、开源代码和实际应用。
• 未来方向：讨论了GNN的理论方面，分析了现有方法的局限性，并提出了模型深度、可扩展性、异质性和动态性四个方面的潜在研究方向。

背景与定义

背景

图神经网络的简史（A Brief History of Graph Neural Networks）

早期研究：图神经网络的概念最早由 Sperduti et al. (1997) 提出，他们将神经网络应用于有向无环图，激发了对图神经网络的早期研究。Gori et al. (2005) 和 Scarselli et al. (2009) 进一步定义了图神经网络的概念，这些早期研究被归类为递归图神经网络（RecGNNs）。

递归图神经网络（RecGNNs）：这些网络通过迭代传播节点之间的信息，直到达到稳定的固定点。这种方法计算开销大，最近有越来越多的研究致力于克服这些挑战。

卷积图神经网络（ConvGNNs）：受卷积神经网络（CNNs）在计算机视觉领域成功的启发，研究者们开发了许多重新定义图卷积的方法。这些方法分为频谱方法和空间方法。

图神经网络与图嵌入（Graph Neural Networks vs. Network Embedding）

图嵌入：旨在将网络节点表示为低维向量表示，保留网络拓扑结构和节点内容信息，以便使用简单的机器学习算法（如支持向量机）进行分类、聚类和推荐等图分析任务。

图神经网络：是设计用于处理各种任务的深度学习模型，能够通过端到端的方式解决图相关任务。许多GNNs通过图自动编码器框架显式提取高层次表示。

主要区别：GNNs 是一组用于处理各种任务的神经网络模型，而图嵌入包括各种针对同一任务的方法。因此，GNNs 可以通过图自动编码器框架解决图嵌入问题，而图嵌入还包含其他非深度学习方法，如矩阵分解和随机游走。

图神经网络与图核方法（Graph Neural Networks vs. Graph Kernel Methods）

图核方法：历史上是解决图分类问题的主要技术，通过核函数测量图对之间的相似性，从而使用支持向量机等核算法进行监督学习。图核方法可以将图或节点嵌入到向量空间，但映射函数是确定性的而非可学习的。

图神经网络的优势：直接基于提取的图表示进行图分类，比图核方法更高效。此外，图核方法计算相似性时存在计算瓶颈，而GNNs通过直接对图表示进行分类克服了这一问题。

定义（Definition）

图的基本定义

• 图（Graph）：一个图表示为 $G = (V, E)$，其中 $V$ 是节点集合，$E$ 是边集合。节点 $v_i \in V$ ，边 $e_{ij} = (v_i, v_j) \in E$ 表示从节点 $v_j$ 指向节点 $v_i$ 的边。
• 邻居（Neighborhood）：节点 $v$ 的邻居定义为 $N(v) = { u \in V | (v, u) \in E }$。
• 邻接矩阵（Adjacency Matrix）：$A$ 是 $n \times n$ 的矩阵，其中 $A_{ij} = 1$ 如果 $e_{ij} \in E$，否则 $A_{ij} = 0$。
• 节点属性矩阵（Node Feature Matrix）：$X \in \mathbb{R}^{n \times d}$，表示节点特征矩阵，其中 $x_v \in \mathbb{R}^d$ 表示节点 $v$ 的特征向量。
• 边属性矩阵（Edge Feature Matrix）：$X_e \in \mathbb{R}^{m \times c}$，表示边特征矩阵，其中 $x_{e_{v,u}} \in \mathbb{R}^c$ 表示边 $(v, u)$ 的特征向量。

有向图和无向图

• 有向图（Directed Graph）：所有边都是有向的。
• 无向图（Undirected Graph）：如果图是无向的，那么对于连接的两个节点存在一对具有相反方向的边。无向图的邻接矩阵是对称的。

时空图（Spatial-Temporal Graph）

• 定义：节点属性随时间动态变化的图。表示为 $G(t)=(V,E,X(t))$,其中 $X(t)∈R$ 是图在时间 t 的节点特征矩阵。

符号说明（Notations）

文中使用了一些常见的符号来表示图神经网络中的概念，这些符号在文献中列出了详细的说明，如表格中的节点数量 n、边数量 m、节点特征维度 d、边特征维度 c 等。

分类与框架（Categorization and Frameworks）

图神经网络的分类（Taxonomy of Graph Neural Networks, GNNs）

作者提出了一种新的图神经网络分类方法，将现有的GNN模型分为以下四类：

递归图神经网络（Recurrent Graph Neural Networks, RecGNNs）

• 基本思想：这些是图神经网络的早期工作，通过递归神经网络的架构来学习节点表示。假设图中的一个节点不断与其邻居交换信息，直到达到稳定的平衡点。
• 代表性模型：
  • GNN*（2009）：由Scarselli等人提出，通过信息扩散机制递归更新节点状态。
  • GGNN（2015）：使用门控循环单元（GRU）作为递归函数，减少了迭代次数。
  • SSE（2018）：引入了一种更具扩展性的学习算法，以异步方式更新节点状态。

卷积图神经网络（Convolutional Graph Neural Networks, ConvGNNs）

• 基本思想：将卷积操作从网格数据扩展到图数据，通过聚合节点及其邻居的特征来生成节点表示。
• 分类：
  • 频谱方法（Spectral Methods）：基于图信号处理理论，通过图拉普拉斯矩阵的特征分解来定义卷积操作。
  • 空间方法（Spatial Methods）：直接在图的邻域上进行卷积操作，类似于传统卷积神经网络中的卷积核操作。
• 代表性模型：
  • GCN（2017）：通过一阶近似简化了Cheb Net的计算，提出了图卷积层的基本公式。
  • GAT（2017）：使用注意力机制来为邻居节点赋予不同的权重。

图自动编码器（Graph Autoencoders, GAEs）

• 基本思想：无监督学习框架，将节点或图编码为潜在空间表示，并从中重构图数据。用于网络嵌入和图生成。
• 代表性模型：
  • Variational Graph Autoencoder（VGAE, 2016）：通过变分推断进行图结构的生成和重构。

时空图神经网络（Spatial-Temporal Graph Neural Networks, STGNNs）

• 基本思想：学习时空图中的隐藏模式，适用于如交通速度预测、驾驶员行为预测和人类动作识别等应用。
• 代表性模型：
  • ST-GCN（2018）：结合图卷积和时间卷积来捕捉空间和时间依赖关系。

图神经网络的框架（Frameworks）

图神经网络的输出可以针对不同的图分析任务，采用以下机制之一：

节点级别输出（Node-Level Outputs）

• 相关任务：节点回归和节点分类任务。
• 方法：通过信息传播或图卷积提取高层次的节点表示，使用多层感知器（MLP）或softmax层作为输出层，实现端到端的节点级任务。

边级别输出（Edge-Level Outputs）

• 相关任务：边分类和链接预测任务。
• 方法：使用两个节点的隐藏表示作为输入，通过相似性函数或神经网络来预测边的标签或连接强度。

图级别输出（Graph-Level Outputs）

• 相关任务：图分类任务。
• 方法：结合图卷积层、图池化层和/或读出层，获取紧凑的图表示。通过应用多层感知器和SoftMax层实现端到端的图分类任务。

训练框架（Training Frameworks）

GNNs的训练可以是（半）监督或完全无监督的，取决于任务和标签信息的可用性：

半监督学习（Semi-Supervised Learning）

• 节点级分类：在一个部分节点已标记的单一网络中，通过图卷积层和SoftMax层构建端到端框架，学习分类模型。

监督学习（Supervised Learning）

• 图级分类：预测整个图的类别标签。通过结合图卷积层、图池化层和读出层，构建端到端的学习框架。

无监督学习（Unsupervised Learning）

• 图嵌入：当图中没有可用的类别标签时，可以在端到端框架中学习图嵌入。使用图自动编码器框架，通过编码器提取图的潜在表示，并通过解码器重构图结构。

代表性模型和方法的总结（Summary of Representative Models and Methods）

表格中总结了递归图神经网络（RecGNNs）和卷积图神经网络（ConvGNNs）的主要特征，如输入源、池化层、读出层和时间复杂度。详细比较了不同模型的时间和内存复杂度，以帮助研究者选择合适的模型。

统计表格

递归图神经网络（Recurrent Graph Neural Networks, RecGNNs）

概述（Overview）

递归图神经网络（RecGNNs）是最早的图神经网络模型，通过递归应用相同的一组参数在图的节点上来提取高层次的节点表示。早期的研究主要集中在有向无环图（DAGs）上。

代表性模型（Representative Models）

图神经网络（GNN*，2009）

• 核心思想：基于信息扩散机制，节点的隐藏状态通过与其邻居节点的信息交换进行递归更新，直到达到稳定的固定点。
• 公式：$h_v^{(t)} = \sum_{u \in N(v)} f(x_v, x_{e_{v,u}}, x_u, h_u^{(t-1)})$
  其中, $f(·)$ 是一个参数化函数，$h_v^{(0)}$初始为随机值。通过反复应用该公式，节点的隐藏状态最终收敛到稳定点。
• 特点：适用于有向、无向、循环和无循环的图。为了确保收敛，递归函数$f(·)$必须是收缩映射。

图回声状态网络（Graph Echo State Network, GraphESN, 2010）

• 核心思想：通过扩展回声状态网络来提高GNN*的训练效率。GraphESN 由编码器和输出层组成，编码器随机初始化且不需要训练，通过收缩状态转移函数递归更新节点状态直到全局图状态收敛。
• 公式：类似于GNN*，但编码器固定，输出层通过节点的固定状态进行训练。

门控图神经网络（Gated Graph Neural Network, GGNN, 2015）

• 核心思想：采用门控循环单元（GRU）作为递归函数，减少了迭代次数，不再需要对参数进行约束以确保收敛。

• 公式：$h_v^{(t)} = \text{GRU}(h_v^{(t-1)}, \sum_{u \in N(v)} W h_u^{(t-1)})$
  其中，$h_v^{(0)} = x_v$ ，使用时间反向传播算法（BPTT）来学习模型参数。

  随机稳态嵌入（Stochastic Steady-state Embedding, SSE, 2018）

• 核心思想：引入了一种更具扩展性的学习算法，以异步方式更新节点状态。采用随机和异步方式来交替采样节点进行状态更新和梯度计算。

• 公式：$h_v^{(t)} = (1 - \alpha) h_v^{(t-1)} + \alpha W_1 \sigma(W_2 [x_v, \sum_{u \in N(v)} [h_u^{(t-1)}, x_u]])$
  其中，$alpha$是超参数。

总结与讨论（Summary and Discussion）

RecGNNs 在概念上很重要，并启发了后续的卷积图神经网络（ConvGNNs）的研究。特别是，消息传递的思想被空间卷积图神经网络所继承。RecGNNs 的训练通常计算开销较大，尤其是在大规模图上，因为它们需要多次在所有节点上运行递归函数，并存储所有节点的中间状态。表格中总结了不同RecGNNs的主要特征和复杂度，帮助读者理解这些模型的异同和适用场景。