开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 人工智能 -> A Comprehensive Survey on Graph Neural Networks -> 正文阅读

[人工智能]A Comprehensive Survey on Graph Neural Networks

本文是对《A Comprehensive Survey on Graph Neural Networks》论文的一个翻译，主要针对文字部分，插图和表格不添加，需要请看原论文。

图神经网络综述

摘要

近年来，深度学习彻底改变了许多机器学习任务，从图像分类和视频处理到语音识别和自然语言理解。这些任务中的数据通常用欧几里德空间表示。然而，越来越多的应用程序从非欧几里德域生成数据，并将其表示为对象之间具有复杂关系和相互依存关系的图。图数据的复杂性对现有的机器学习算法提出了重大挑战。最近，出现了许多关于扩展图数据深度学习方法的研究。在本综述中，我们全面概述了数据挖掘和机器学习领域中的图神经网络（GNN）。我们提出了一种新的分类法，将最先进的图神经网络分为四类，即循环图神经网络、卷积图神经网络，图自动编码器和时空图神经网络。我们进一步讨论了图神经网络在各个领域的应用，并总结了图神经网的开源代码、基准数据集和模型评估。最后，我们提出了这一快速发展领域的潜在研究方向。

一、引言

最近神经网络的成功推动了模式识别和数据挖掘的研究。许多机器学习任务，如目标检测、机器翻译和语音识别，曾经严重依赖手工特征工程来提取信息特征集，最近已被各种端到端深度学习范式所彻底改变，例如卷积神经网络（CNN）、循环神经网络（RNN），和自动编码器。深度学习在许多领域的成功部分归功于快速发展的计算资源（如GPU）、大训练数据的可用性以及从欧几里德数据（如图像、文本和视频）中提取潜在表示的深度学习的有效性。以图像数据为例，我们可以将图像表示为欧几里德空间中的规则网格。卷积神经网络（CNN）能够利用图像数据的平移不变性、局部连通性和合成性。因此，CNN可以提取局部有意义的特征，这些特征与整个数据集共享，用于各种图像分析。

虽然深度学习有效地捕获了欧几里德数据的隐藏模式，但越来越多的应用程序将数据表示为图。例如，在电子商务中，基于图的学习系统可以利用用户和产品之间的交互，提出高度准确的推荐。在化学中，分子被建模为图，它们的生物活性需要被鉴定以用于药物发现。在引文网络中，论文通过引文系统相互链接，而且需要分为不同的组。图数据的复杂性对现有的机器学习算法提出了重大挑战。由于图可能是不规则的，图可能具有可变大小的无序节点，并且图中的节点可能具有不同数量的邻居，这导致一些重要操作（例如卷积）在图像域中易于计算，但难以应用于图域。此外，现有机器学习算法的一个核心假设是实例相互独立。这一假设不再适用于图数据，因为每个实例（节点）都通过各种类型的链接（如引用、关系和交互）与其他实例相关。

最近，人们对扩展图数据的深度学习方法越来越感兴趣。在深度学习的CNN、RNN和自动编码器的推动下，在过去几年中，重要操作的新概括和定义得到了快速发展，以处理图形数据的复杂性。例如，图卷积可以从2D卷积推广而来。如图1所示，可以将图像视为图的特例，其中像素由相邻像素连接。与2D卷积类似，可以通过对节点的邻域信息进行加权平均来执行图卷积。

关于图神经网络（GNN）的主题，现有的综述数量有限。Bronstein等人使用“几何深度学习”一词，概述了非欧几里德域中的深度学习方法，包括图和流形。虽然这是对GNN的第一次回顾，但本文主要回顾卷积GNN。Hamilton等人研究了有限数量的GNN，重点是解决网络嵌入问题。Battaglia等人将图网络定位为从关系数据学习的构建块，在统一框架下综述了部分GNN。Lee等人对应用不同注意力机制的GNN进行了部分研究。总之，现有的综述只包括一些GNN，并检查了有限数量的工作，因此错过了GNN的最新发展。我们的综述为希望进入这一快速发展领域的感兴趣的研究人员和希望比较GNN模型的专家提供了关于GNN的全面概述。为了涵盖更广泛的方法，本综述将GNN视为图数据有关的所有深度学习方法。

我们的贡献

我们的论文做出了如下显著贡献：

?新分类：我们提出了一种新的图形神经网络分类。图神经网络分为四类：循环图神经网络、卷积图神经网络，图自动编码器和时空图神经网络。

?全面回顾?我们提供了图数据现代深度学习技术的最全面概述。对于每种类型的图神经网络，我们提供了代表性模型的详细描述，进行了必要的比较，并总结了相应的算法。

?丰富的资源?我们收集了大量关于图神经网络的资源，包括最先进的模型、基准数据集、开源代码和实际应用。本综述可作为理解、使用和开发各种实际应用的不同深度学习方法的实践指南。

?未来方向?我们讨论了图神经网络的理论方面，分析了现有方法的局限性，并就模型深度、可扩展性权衡、异构性和动态性提出了四个可能的未来研究方向。

综述的组织结构?

本次综述的其余部分组织如下。第二节概述了图神经网络的背景，列出了常用的符号，并定义了与图相关的概念。第三节阐明了图神经网络的分类。第四节至第七节概述了图神经网络模型。第八节介绍了跨不同领域的应用集合。第九节讨论了当前的挑战并提出了未来的方向。第十节总结了本文。

二、背景和定义

在本节中，我们概述了图神经网络的背景，列出了常用的符号，并给出了图相关的概念。

A. 背景

图神经网络（GNN）的简史 Sperduti等人（1997）首次将神经网络应用于有向无环图，这激发了对GNN的早期研究。图神经网络的概念最初在Gori等人（2005）中概述，并在Scarselli等人（2009）和Gallicchio等人（2010）中进一步得到阐述。这些早期研究属于循环图神经网络（RecGNN）的范畴。他们通过以迭代方式传播邻居信息来学习目标节点的表示，直到达到稳定的状态。这一过程在计算上非常昂贵，最近人们越来越努力克服这些挑战。

在计算机视觉领域CNN成功的鼓舞下，并行开发了大量重新定义图数据卷积概念的方法。这些方法属于卷积图神经网络（ConvGNNs）。ConvGNNs分为两大主流，基于谱的方法和基于空间的方法。Bruna等人（2013）首次对基于谱的ConvGNNs进行了杰出的研究，开发了基于谱图理论的图卷积。自那时以来，基于谱的ConvGNNs得到了越来越多的改进、扩展和近似。基于空间的ConvGNNs的研究比基于谱的ConvGNNs早得多。2009年，Micheli等人首先通过架构复合非递归层解决了图的相互依赖性，同时继承了RecGNNS的消息传递思想。然而，这项工作的重要性被忽视了。直到最近，出现了许多基于空间的convGNNs。表2第一列显示了具有代表性的RecGNNS和ConvGNNs的时间线。除了RecGNNS和ConvGNNs外，在过去几年中还开发了许多替代GNNs，包括图自动编码器（GAEs）和时空图神经网络（STGNNs）。这些学习框架可以构建在RecGNNS、ConvGNNs或其他用于图建模的神经架构上。第三节详细介绍了这些方法的分类。

图神经网络与网络嵌入 GNN的研究与图嵌入或网络嵌入密切相关，这是数据挖掘和机器学习领域日益关注的另一个主题。网络嵌入旨在将网络节点表示为低维向量表示，同时保留网络拓扑结构和节点内容信息，以便使用简单的现成机器学习算法（例如，用于分类的支持向量机）轻松执行任何后续的图分析任务，如分类、聚类和推荐。与此同时，GNN是深度学习模型，旨在以端到端的方式处理与图相关的任务。许多GNN显式地提取高阶表示。GNN和网络嵌入的主要区别在于，GNN是一组为各种任务设计的神经网络模型，而网络嵌入涵盖了针对同一任务的各种方法。因此，GNNs可以通过图自动编码器框架解决网络嵌入问题。另一方面，网络嵌入包含其他非深度学习方法，如矩阵分解和随机游走。

图神经网络与图核方法 图核是解决图分类问题的历史主导技术。这些方法使用核函数来度量图对之间的相似性，因此基于核的算法（如支持向量机）可以用于图的监督学习。与GNN类似，图核可以通过映射函数将图或节点嵌入向量空间。不同之处在于，该映射函数是确定性的，而不是可学习的。由于采用成对相似度计算，图核方法的计算瓶颈严重。一方面，GNN直接基于提取的图表示执行图分类，因此比图核方法更有效。关于图核方法的进一步综述，我们请读者参阅[39]。

B. 定义

在本文中，我们使用粗体大写字符表示矩阵，粗体小写字符表示向量。除非特别说明，本文中使用的符号如表1所示。现在我们定义了理解本文所需的最小定义集。

定义1（图）：图表示为 $G=(V,E)$ ，其中V是顶点或节点集（我们将在本文中使用节点），E是边集。让 $v_i \in V$ 表示一个节点，同时 $e_{ij}=(v_i , v_j)\in E$ 表示一条边，从 $v_j$ 指向 $v_i$ 的边。节点v的邻域被定义为 $N(v)=\{u\in V | (v,u) \in E\}$ 。邻接矩阵A是一个 $n \times n$ 的矩阵，其中 $A_{ij}=1$ 如果 $e_{ij}\in E$ ，否则 $A_{ij}=0$ 如果 $e_{ij} \notin E$ 。图拥有节点属性 $X$ ，其中 $X \in \mathbb{R} ^{n \times d}$ 是一个节点特征矩阵， $x_v \in \mathbb{R}^d$ 表示的是节点v的特征向量。与此同时，一个图拥有边属性 $X^e$ ，其中 $X^e \in \mathbb{R}^{m \times c}$ 是一个边特征矩阵， $x^e_{v,u} \in \mathbb{R}^c$ 代表的是边 $(v,u)$ 的特征向量。

定义2（有向图）：有向图是所有边从一个节点指向另一个节点的图。无向图被视为有向图的一种特殊情况，其中如果两个节点连接，则存在一对反向边。图是无向的当且仅当邻接矩阵是对称的。

定义3（时空图）：时空图是节点属性随时间动态变化的属性图。时空图定义为 $G^{(t)}=(V,E,X^{(t)})$ ，其中 $X^{(t)} \in \mathbb{R} ^{n \times d}$ 。

三、分类和框架

在本节中，我们介绍了图神经网络（GNN）的分类，如表2所示。我们将图神经网络（GNN）分为循环图神经网络（RecGNNs）、卷积图神经网络（ConvGNNs）和时空图神经网络（STGNNs）。图2给出了各种模型架构的示例。下面，我们将简要介绍每一类。

A. 图神经网络（GNNs）分类

循环图神经网络（RecGNNs）是图神经网络的先驱。RecGNNs旨在学习具有循环神经结构的节点表示。他们假设图中的节点不断与其邻居交换信息/消息，直到达到稳定平衡。RecGNNs在概念上很重要，并启发了卷积图神经网络的后续研究。特别的是，基于空间的卷积图神经网络继承了消息传递的思想。

卷积图神经网络（ConvGNNs）将卷积运算从网格数据推广到图数据。其主要思想是通过聚合节点 $v$ 自身的特征 $x_v$ 和邻居的特征 $x_u$ 来生成节点的表示，其中 $u\in N(v)$ 。与RecGNNs不同，ConvGNNs堆叠多个图卷积层以提取高阶节点表示。ConvGNNs在构建许多其他复杂GNN模型中起着核心作用。图2a显示了用于节点分类的ConvGNN。图2b展示了用于图分类的ConvGNN。

图自动编码器（GAE）是无监督学习框架，它将节点/图编码到潜在向量空间中，并根据编码信息重建图数据。GAEs用于学习网络嵌入和图生成分布。对于网络嵌入，GAE通过重建图结构信息（如图邻接矩阵）来学习潜在节点表示。对于图生成，有些方法一步一步地生成图的节点和边，而其他方法一次输出一个图。图2c显示了网络嵌入的GAE。

时空图神经网络（STGNNS）旨在从时空图中学习隐藏模式，这在各种应用中变得越来越重要，如交通速度预测、驾驶员机动预测和人类动作识别。STGNNS的关键思想是同时考虑空间依赖和时间依赖。当前的许多方法将图卷积用来捕获空间依赖性，RNNs或CNNs建模时间依赖性。图2d说明了时空图预测的STGNN。

B. 框架

通过图形结构和节点内容信息作为输入，GNNs的输出可以通过以下机制之一专注于不同的图分析任务：

?节点级?输出与节点回归和节点分类任务有关。RecGNNs和ConvGNNs可以通过信息传播/图卷积提取高阶节点表示。通过使用多感知器或softmax层作为输出层，GNNs能够以端到端的方式执行节点级任务。

?边级输出与边缘分类和链路预测任务有关。利用GNNs中两个节点的隐藏表示作为输入，可以利用相似函数或神经网络来预测边的标记/连接强度。

?图形级输出 与图分类任务相关。为了获得图形级的紧凑表示，GNNs通常与池化和读出操作相结合。有关池化和读出的详细信息将在第V-C节中进行回顾。

训练框架。许多GNNs（例如ConvGNNs）可以在端到端学习框架内以（半）监督或纯无监督的方式进行训练，具体取决于手头的学习任务和标签信息。

?用于节点级分类的半监督学习。给定一个部分节点被标记而其他节点未标记的单一网络，ConvGNNs可以学习一个鲁棒模型，有效识别未标记节点的类标签。为此，可以通过堆叠多个图卷积层，然后是用于多类别分类的softmax层来构建端到端框架。

?图级分类的监督学习。图级分类旨在预测整个图的类标签。该任务的端到端学习可以通过图卷积层、图池化层和/或读出层的组合来实现。图卷积层负责精确的高阶节点表示，而图池化层则起到下采样的作用，每次都将每个图粗化为一个子结构。读出层将每个图的节点表示折叠为图表示。通过将多层感知器和softmax层应用于图表示，我们可以构建一个端到端的图分类框架。图2b给出了一个示例。

图嵌入的非监督学习。当图中没有可用的类标签时，我们可以在端到端框架中以纯无监督的方式学习图嵌入。这些算法以两种方式利用边级信息。一种简单的方法是采用自动编码器框架，其中编码器采用图卷积层将图嵌入潜在表示中，解码器在潜在表示中用于重建图结构。另一种流行的方法是利用负采样方法，该方法将一部分节点对采样为负对，而图中具有链接的现有节点对为正对。然后应用逻辑回归层来区分正对和负对。

在表III中，我们总结了具有代表性的RecGNNs和ConvGNNs的主要特征。比较了各种模型的输入源、池化层、读出层和时间复杂度。更详细地说，我们只比较了每个模型中消息传递/图卷积操作的时间复杂度。由于[19]和[20]中的方法需要特征值分解，因此时间复杂度为 $\mathcal{O}(n^3)$ 。由于节点成对最短路径计算，[46]的时间复杂度也是 $\mathcal{O}(n^3)$ 。其他方法产生等效的时间复杂度，如果图邻接矩阵是稀疏的，则时间复杂度为 $\mathcal{O}(m)$ ，否则时间复杂度是 $\mathcal{O}(n^2)$ 。这是因为在这些方法中，每个节点 $v_i$ 表示的计算涉及其 $d_i$ 邻居，所有节点 $d_i$ 之和正好等于边的数量。表III中缺少几种方法的时间复杂度。这些方法在他们的论文中缺乏时间复杂度分析，或报告了他们整体模型或算法的时间复杂度。

四、循环图神经网络

循环图神经网络（RecGNNs）主要是GNNs的先驱作品。它们在图中的节点上重复应用相同的参数集，以提取高阶节点表示。受计算能力的限制，早期的研究主要集中在有向无环图。

Scarselli等人提出的图神经网络（GNN*）扩展了先前的循环模型，以处理一般类型的图，如无环图、循环图、有向图和无向图。基于信息扩散机制，GNN通过反复交换邻域信息更新节点状态，直到达到稳定平衡。节点的隐藏状态由如下方式更新 $h_t^{(t)}=\sum_{u\in N(v)}f(x_v,x^e(v,u),x_u,h_u^{(t-1)}),$

其中 $f(\cdot )$ 是一个参数函数， $h_v^{(0)}$ 随机初始化。求和运算使GNN能够适用于所有节点，即使邻居的数量不同，并且不知道邻居排序。为了确保收敛，循环函数 $f(\cdot )$ 必须是一个收缩映射，它在将两点投影到潜在空间后收缩两点之间的距离。在 $f(\cdot )$ 是神经网络的情况下，必须对参数的雅可比矩阵施加惩罚项。当满足收敛准则时，最后一步节点隐藏状态被传递到读出层。GNN交替节点状态传播阶段和参数梯度计算阶段，以最小化训练目标。此策略使GNN能够处理循环图。在后续工作中，图回声状态网络（GraphESN）扩展了回声状态网络，以提高GNN的训练效率。GraphESN由编码器和输出层组成。编码器随机初始化并且不需要训练。它实现了一个收缩状态转移函数，以循环更新节点状态，直到全局图状态达到收敛。然后，通过将固定节点状态作为输入来训练输出层。

门控图神经网络（GGNN）采用门控循环单元（GRU）作为循环函数，将循环减少到固定的步数。其优点是不再需要约束参数以确保收敛。节点隐藏状态由其先前隐藏状态及其相邻隐藏状态更新，定义为： $h_v^{(t)}=GRU(h_v^{(t-1)},\sum_{u\in N(v)}Wh_u^{(t-1)}),$ ，其中 $h_v^{(0)}=x_v$ . 与GNN和GraphESN不同，GGNN使用时间反向传播（BPTT）算法学习模型参数。这对于大型图来说可能是个问题，因为GGNN需要在所有节点上多次运行循环函数，需要将所有节点的中间状态存储在内存中。

随机稳态嵌入（SSE）提出了一种学习算法，该算法更适合于大型图。SSE以随机和异步方式重复更新节点隐藏状态。它对一批节点进行采样以进行状态更新，并对一批结点进行梯度计算。为了维持稳定性，SSE的循环函数定义为历史状态和新状态的加权平均，其形式为： $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$ 是超参数， $h_v^{(0)}$ 随机被初始化。虽然在概念上很重要，但SSE在理论上无法证明节点状态将通过重复应用等式3逐渐收敛到不动点。

五、卷积图神经网络

卷积图神经网络（ConvGNNs）与循环图神经网络密切相关。ConvGNNS不使用压缩约束迭代节点状态，而是在体系结构上使用固定数量的层，每个层具有不同的权重，来解决循环相互依赖。这一关键区别如图3所示。由于图卷积更有效，更便于与其他神经网络组合，近年来，ConvGNNs的普及率迅速增长。ConvGNNS分为两类，基于谱的和基于空间的。基于谱的方法通过从图形信号处理的角度引入滤波器来定义图卷积，其中图卷积运算被解释为从图信号中去除噪声。基于空间的方法继承了RecGNNs的思想，通过信息传播定义图卷积。由于GCN弥补了基于光谱的方法和基于空间的方法之间的差距，基于空间的方式由于其具有吸引力的效率、灵活性和通用性，最近得到了快速发展。

A.基于谱的ConvGNNs

背景?基于谱的方法在图信号处理中具有坚实的数学基础。他们假设图是无向的。归一化的图拉普拉斯矩阵是无向图的数学表示，定义为 $L=I_n-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ ,其中D是节点度的对角阵， $D_{ii}=\sum_j(A_{i,j})$ .归一化的图拉普拉斯矩阵具有实对称半正定性质。利用此特性，归一化拉普拉斯矩阵可以分解为 $L=U\Lambda U^T$ ，其中 $U=[u_0,u_1,\cdots,u_{n-1}]\in R^{n\times n}$ 是按特征值排序的特征向量矩阵， $\Lambda$ 是特征值的对角矩阵（谱）， $\Lambda _{ii}=\lambda_i$ 。归一化的拉普拉斯矩阵的特征向量形成正交空间，用数学的话来说就是 $U^TU=I$ .在图信号处理中，一个图信号 $x\in R^n$ 是图中所有节点的特征向量，其中 $x_i$ 是第i个节点的值。对于信号x的图傅里叶变换定义为 $f(x)=U^Tx$ ,傅里叶逆变换定义为 $f^{-1}(x)=U\hat x$ ,其中 $\hat x$ 表示图傅里叶变换的结果信号。图傅里叶变换将输入图信号投影到正交空间，其中基由归一化图的拉普拉斯特征向量形成。变换信号的元素 $\hat x$ 是图信号在新空间中的坐标，因此输入信号可以表示为 $x=\sum_i\hat x_iu_i$ ,这正是图傅里叶逆变换。输入信号x与滤波器 $g\in R^n$ 的图卷积定义为 $x\ast _Gg=f^{-1}(f(x)\odot f(g))=U(U^Tx\odot U^Tg),$ 其中 $\odot$ 表示按元素乘积。如果我们将滤波器定义为 $g_\theta=diag(U^Tg)$ ，那么谱图卷积可以简化为 $x\ast _Gg_\theta=Ug_\theta U^Tx.$ 基于谱的ConvGNNs都服从这些定义。关键区别在于滤波器 $g_\theta$ 的选择。

谱卷积神经网络（谱CNN）假设滤波器 $g_\theta=\Theta ^{(k)}_{i,j}$ 是一组可学习的参数，并考虑具有多个通道的图信号。谱CNN的图卷积层定义为 $H^{(k)}_{:,j}=\sigma(\sum^{f_{k-1}}_{i=1}U\Theta^{(k)}_{i,j}U^TH^{(k-1)}_{:,i})(j=1,2,\cdots,f_k),$ 其中k是层编号， $H^{(k-1)}\in R^{n \times f_{k-1}}$ 是输入的图信号， $H^{(0)}=X$ , $f_{k-1}$ 是输入通道的数量， $f_k$ 是输出通道的数量， $\Theta^{(k)}_{i,j}$ 是可学习参数组成的对角矩阵。由于拉普拉斯矩阵的特征分解，谱CNN面临三个限制。首先，对图的任何扰动都会导致特征基的变化。其次，学习的过滤器是域相关的，这意味着它们不能应用于具有不同结构的图。第三，特征分解需要 $\mathcal{O}(n^3)$ 计算复杂度。在后续工作中，ChebNet和GCN通过进行多次近似和简化，将计算复杂度降低到 $\mathcal{O}(m)$ 。

切比雪夫谱CNN（ChebNet）通过特征值对角矩阵的切比雪夫多项式逼近滤波器 $g_\theta$ ,比如 $g_\theta=\sum^K_{i=0}\theta_iT_i(\hat \Lambda )$ ,其中 $\hat \Lambda =2\Lambda / \lambda_{max}-I_n$ , $\hat \Lambda$ 的值主要落在 $[-1,1]$ 之间。切比雪夫多项式递归定义如下 $T_i(x)=2xT_{i-1}(x)-T_{i-2}(x)$ ,其中 $T_0(x)=1$ , $T_1(x)=x$ .因此，图信号x与定义的过滤器 $g_\theta$ 的卷积为： $x\ast _Gg_\theta=U(\sum^K_{i=0}\theta_iT_i(\hat\Lambda ))U^Tx,$ 其中 $\tilde{L}=2L/\lambda_{max}-I_n$ .因为 $T_i(\tilde{L})=UT_i(\tilde{\Lambda })U^T$ ,这可以通过i的介绍来证明，ChebNet采用以下形式， $x\ast _Gg_\theta=\sum^K_{i=0}\theta_iT_i(\tilde{L})x,$ 作为对光谱CNN的一种改进，由ChebNet定义的滤波器在空间中局部化，这意味着滤波器可以独立于图的大小提取局部特征。ChebNet的频谱被线性映射到 $[-1,1]$ 。CayleyNet进一步应用Cayley多项式，该多项式是参数有理复函数，用于捕获窄带。CayleyNet的谱图卷积定义为： $x\ast _Gg_\theta=c_0x+2Re\{\sum^r_{j=1}c_j(hL-iI)^j(hL+iI)^{-j}x\},$ 其中 $Re(\cdot)$ 返回了复数的实部， $c_0$ 是实系数， $c_j$ 是复系数，i是虚数，h是控制Cayley滤波器频谱的参数。在保持空间局部性的同时，CayleyNet表明ChebNet可以被视为CayleyNet的特例。

图卷积网络（GCN）引入了ChebNet的一阶近似。假设 $K=1$ 而且 $\lambda_{max}=2$ ,等式8可以简化为 $x\ast_Gg_{\theta}=\theta_0x-\theta_1D^{-\frac{1}{2}}AD^{-\frac{1}{2}}x.$ 为了约束参数的数量同时避免过拟合，GCN假设 $\theta=\theta_0=-\theta_1$ ,引出了如下的图卷积定义， $x\ast_Gg_{\theta}=\theta(I_n+D^{-\frac{1}{2}}AD^{-\frac{1}{2}})x.$ 为了允许多通道的输入和输出，GCN修改了等式11成组合层，定义为 $H=X\ast_Gg_\Theta=f(\bar{A}X\Theta),$ 其中 $\bar A=I_n+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ ，而且 $f(\cdot)$ 是一个激活函数。使用 $I_n+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ 经验上可能导致GCN数值不稳定。为了解决这个问题，GCN使用了一个归一化技巧用 $\bar A=\tilde D^{-\frac{1}{2}}\tilde A\tilde D^{-\frac{1}{2}}$ 替换 $\bar A=I_n+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ ,其中 $\tilde A = A +I_n$ , $\tilde D_{ii}=\sum_j\tilde A_{ij}$ .作为基于谱的方法，GCN也可以解释为基于空间的方法。从基于空间的角度来看，GCN可以被视为从节点的邻域聚集特征信息。等式12可以表示为： $h_v=f(\Theta^T(\sum_{u\in\{N(v)\bigcup v\}}\bar A_{v,u}x_u)) \forall v \in V.$

最近的几项工作通过探索替代对称矩阵，对GCN进行了渐进式改进。自适应图卷积网络（AGCN）学习图邻接矩阵未指定的隐藏结构关系。它通过以两个节点的特征作为输入的可学习距离函数构造所谓的残差图邻接矩阵。对偶图卷积网络（DGCN）介绍了一种对偶图卷积结构，具有两个并行的图卷积层。虽然这两个层共享参数，但它们使用归一化邻接矩阵 $\bar A$ 和正逐点互信息（PPMI）矩阵，该矩阵通过从图中随机游走方式采样来捕获节点共现信息。PPMI矩阵定义为： $PPMI_{v_1,v_2}=max(\log (\frac{count(v_1,v_2)\cdot|D|}{count(v_1)count(v_2)}),0),$ 其中 $v_1,v_2 \in V,|D|=\sum_{v_1,v_2}count(v_1,v_2)$ 并且 $count(\cdot)$ 函数返回节点v和或节点u在采样随机游走中共同出现或者出现的频率。通过对来自对偶图卷积层的输出进行集成，DGCN对局部和全局结构信息进行编码，而无需堆叠多个图卷积层。

B.基于空间的ConvGNNs

类似于传统CNN对图像的卷积运算，基于空间的方法是基于节点的空间关系来定义图卷积。图像可以被视为一种特殊的图形式，每个像素代表一个节点。每个像素直接连接到其附近的像素，如图1a所示。通过取每个通道上中心节点及其相邻节点的像素值的加权平均值，将滤波器应用于3×3范围。类似地，基于空间的图卷积将中心节点的表示与其邻居的表示卷积，以导出中心节点的更新表示，如图1b所示。从另一个角度来看，基于空间的ConvGNNs与RecGNNs共享相同的信息传播/消息传递思想。空间图卷积运算基本上沿边传播节点信息。

与GNN并行提出的图神经网络（NN4G）是基于空间的ConvGNNs的第一项工作。与RecGNNs不同的是，NN4G通过在每一层具有独立参数的组合神经结构来学习图的相互依赖性。节点的邻域可以通过架构的增量构建来扩展。NN4G通过直接对节点的邻域信息求和来执行图卷积。它还应用残差连接和跳跃连接来记忆每一层上的信息。因此，NN4G通过以下方式导出其下一层节点状态： $h_v^{(k)}=f(W^{(k)^T}x_v+\sum_{i=1}^{k-1}\sum_{u\in N(v)}\Theta^{(k)^T}h_u^{(k-1)}),$ 其中 $f(\cdot)$ 是激活函数，并且 $h_v^{(0)}=0$ 。等式15也可以用矩阵的形式写成如下： $H^{(k)}=f(XW^{(k)}+\sum_{i=1}^{k-1}AH^{k-1}\Theta^{(k)}),$ 其类似于GCN的形式。一个不同之处在于，NN4G使用了非规范化的邻接矩阵，这可能会导致隐藏节点状态具有极为不同的尺度。上下文图马尔可夫模型（CGMM）提出了一种受NN4G启发的概率模型。在保持空间局部性的同时，CGMM具有概率可解释性的优点。

扩散卷积神经网络（DCNN）将图卷积视为扩散过程。它假设信息以一定的转移概率从一个节点转移到它的一个相邻节点，这样信息分布可以在几轮之后达到平衡。DCNN将扩散图卷积定义为： $H^{(k)}=f(W^{(k)}\odot P^kX),$ 其中是 $f(\cdot)$ 激活函数，概率转移矩阵 $P\in R^{n \times n}$ 是通过 $P=D^{-1}A$ 来计算的。在DCNN中，隐藏层的表示矩阵 $H^{(k)}$ 与输入特征矩阵X保持同一维度，而且它并不是之前隐藏表示矩阵 $H^{(k-1)}$ 的函数。DCNN将 $H^{(1)},H^{(2)},\cdots,H^{(K)}$ 拼接在一起作为模型最后的输出。由于扩散过程的平稳分布是概率转移矩阵幂级数的总和，扩散图卷积（DGC）将每个扩散步骤的输出相加，而不是拼接。它定义了扩散图卷积： $H=\sum^K_{k=0}f(P^kXW^{(k)}),$ 其中 $W^{(k)}\in R^{D\times F}$ 和 $f(\cdot)$ 是一个激活函数。使用转移概率矩阵的幂意味着远处的邻居对中心节点贡献的信息很少。PGC-DGCNN基于最短路径增加了远距离邻居的贡献。它定义了最短路径邻接矩阵 $S^{(j)}$ .如果从节点v到节点u的最短路径长度为j，则 $S^{(j)}_{v,u}=1$ ，否则为0。使用超参数r来控制感受野大小，PGC-DGCNN引入了图卷积运算，如下所示： $H^{(k)}=||^r_{j=0}f((\tilde D^{(j)})^{-1}S^{(j)}H^{(k-1)}W^{(j,k)}),$ 其中 $\tilde D^{(j)}_{ii}=\sum_l S^{(j)}_{i,j}$ , $H^{(0)}=X$ , $||$ 表示向量之间的拼接。最短路径邻接矩阵的计算可能是昂贵的，最大能达到 $\mathcal{O}(n^3)$ 。分区图卷积（PGC）基于不限于最短路径的某些标准将节点的邻居划分为Q组。PGC根据每个组定义的邻域构造Q个邻接矩阵。然后，PGC将具有不同参数矩阵的GCN应用于每个相邻组，并对结果求和： $H^{(k)}=\sum^Q_{j=1}\bar A^{(j)}H^{(k-1)}W^{(j,k)},$ 其中 $H^{(0)}=X,\bar A^{(j)}=(\tilde D^{(j)})^{-\frac{1}{2}}\tilde A^{(j)}(\tilde D^{(j)})^{-\frac{1}{2}}$ 并且 $\tilde A^{(j)}=A^{(j)}+I$ .

消息传递神经网络（MPNN）概述了基于空间的ConvGNNs的一般框架。它将图卷积视为一个消息传递过程，在该过程中，信息可以沿边从一个节点直接传递到另一个节点。MPNN运行K步消息传递迭代以使信息进一步传播。消息传递函数（即空间图卷积）定义为： $h^{(k)}_v=U_k(h^{(k-1)}_v,\sum_{u\in N(v)}M_k(h^{(k-1)}_v,h^{(k-1)}_u,x^e_{vu})),$ 其中 $h_v^{(0)}=x_v$ ， $U_k(\cdot)$ 和 $M_k(\cdot)$ 是具有可学习参数的函数。在推导出每个节点的隐藏表示之后， $h_v^{(K)}$ 可以传递到输出层以执行节点级预测任务，或者传递到读出函数以执行图级预测任务。读出函数基于节点隐藏表示生成整个图形的表示。它通常定义为： $h_G=R(h_v^{(k)}|v\in G),$ 其中 $R(\cdot)$ 是具有可学习参数的读出函数。MPNN可以通过假设 $U_k(\cdot),M_k(\cdot)$ 和 $R(\cdot)$ 的不同形式来覆盖许多现有GNN。然而，图同构网络（GIN）发现，以前基于MPNN的方法无法根据它们生成的图嵌入来区分不同的图结构。为了修正这个缺点，GIN通过一个可学习的参数 $\epsilon ^{(k)}$ 调整中心节点的权重。它通过以下方式执行图形卷积： $h_v^{(k)}=MLP((1+\epsilon^{(k)})h^{(k-1)}_v+\sum_{u\in N(v)}h_u^{(k-1)}),$ 其中 $MLP(\cdot)$ 代表一个多层感知机。

由于一个节点的邻居的数量可以从一个变化到一千个甚至更多，所以获取节点邻居的完整大小是低效的。GraphSage采用采样来获得每个节点的固定数量的邻居。它通过以下方式执行图形卷积： $h_v^{(k)}=\sigma(W^{(k)}\cdot f_k(h_v^{(k-1)},\{h_u^{(k-1)},\forall u\in S_{\mathcal{N}(v)}\})),$ 其中 $h_v^{(0)}=x_v$ , $f_k(\cdot)$ 是一个聚合函数， $S_{\mathcal{N}(v)}$ 是节点v邻居的随机取样。聚合函数应该对节点顺序的排列保持不变，如均值、求和或最大函数。

图注意力网络（GAT）假设相邻节点对中心节点的贡献既不像GraphSage那样相同，也不像GCN那样预先确定（这种差异如图4所示）。GAT采用注意力机制来学习两个连接节点之间的相对权重。根据GAT的图卷积运算被定义为， $h_v^{(k)}=\sigma(\sum_{u\in \mathcal{N}(v)\cup v}\alpha_{vu}^{(k)}W^{(k)}h_u^{(k-1)}),$ 其中 $h_v^{(0)}=x_v$ .这个注意力权重 $\alpha_{vu}^{(k)}$ 度量了节点v和它邻居u的连接强度： $\alpha_{vu}^{(k)}=softmax(g(a^T[W^{(k)}h_v^{(k-1)}||W^{(k)}h_u^{(k-1)}])),$ 其中 $g(\cdot)$ 是一个LeakyReLU激活函数，a是一个可学习参数的向量。softmax函数确保节点v的所有邻居注意力权重总和为1。GAT进一步执行多头注意力以增加模型的表达能力。这表明在节点分类任务上比GraphSage有了显著的改进。虽然GAT假设注意力头的贡献相等，但门控注意力网络（GAAN）引入了一种自注意力机制，为每个注意力头计算额外的注意力分数。除了在空间上应用图注意力，GeniePath还提出了一种类似LSTM的门控机制，以控制跨图卷积层的信息流。还有其他可能感兴趣的图注意力模型。但是，它们不属于ConvGNN框架。

混合模型网络（MoNet）采用不同的方法为节点的邻居分配不同的权重。它引入节点伪坐标来确定节点与其邻居之间的相对位置。一旦两个节点之间的相对位置已知，权重函数将相对位置映射为这两个节点间的相对权重。通过这种方式，可以在不同位置共享图过滤器的参数。在MoNet框架下，可以通过构造非参数权重函数将流形的几种现有方法（如测地线CNN（GCNN）、各向异性CNN（ACNN）、样条CNN和图（如GCN、DCNN）推广为MoNet的特殊实例。MoNet还提出了一种具有可学习参数的高斯核来自适应地学习权重函数。

另一个独特的工作路线是通过基于特定标准对节点的邻居进行排序，并将每个排序与可学习的权重相关联，实现不同位置的权重共享。PATCHY-SAN根据每个节点的图标签对其邻居进行排序，并选择前q个邻居。图标签本质上是节点得分，可以通过节点度、中心度和Weisfeiler Lehman颜色得出。由于每个节点现在都有固定数量的有序邻居，因此图结构数据可以转换为网格结构数据。PATCHY-SAN应用标准1维卷积滤波器来聚集邻域特征信息，其中滤波器的权重顺序对应于节点的邻域的顺序。PATCHY-SAN的排序标准只考虑图结构，这需要大量的数据处理计算。大规模图卷积网络（LGCN）基于节点特征信息对节点的邻居进行排序。对于每个节点，LGCN组合一个由其邻域组成的特征矩阵，并沿每列对该特征矩阵进行排序。排序特征矩阵的前q行作为中心节点的输入数据。

在训练效率方面的改进?训练ConvGNNs，如GCN，通常需要将整个图数据和所有节点的中间状态保存到内存中。ConvGNNs的全批训练算法严重存在内存溢出问题，特别是当一个图包含数百万个节点时。为了节省内存，GraphSage为ConvGNNs提出了一种批训练算法。它通过以固定的样本大小递归扩展根节点的邻域K步，对每个节点的根树进行采样。对于每个采样树，GraphSage通过从下到上分层聚合隐藏节点表示来计算根节点的隐藏表示。

使用图卷积网络的快速学习（FastGCN）为每个图卷积层采样固定数量的节点，而不是像GraphSage那样为每个节点采样固定数目的邻居。它将图卷积解释为概率测度下节点嵌入函数的积分变换。采用蒙特卡洛近似和方差缩减技术来促进训练过程。由于FastGCN为每层独立采样节点，层间连接可能稀疏。Huang等人提出了一种自适应分层采样方法，其中下层的节点采样以顶层为条件。与FastGCN相比，该方法实现了更高的精度，但代价是采用了更复杂的采样方案。

在另一项工作中，图卷积网络的随机训练（StoGCN）使用历史节点表示作为控制变量，将图卷积的感受野大小减小到任意小的规模。即使每个节点有两个邻居，StoGCN也能获得相当的性能。然而，StoGCN仍然必须保存所有节点的中间状态，这对于大型图来说是一种内存消耗。

Cluster-GCN使用图聚类算法对子图进行采样，并对采样子图内的节点执行图卷积。由于邻域搜索也限制在采样子图内，因此聚类GCN能够处理更大的图，同时使用更深的架构，时间更短，内存更少。ClusterGCN为现有的ConvGNN训练算法提供了时间复杂度和内存复杂度的直接比较。我们根据表IV分析其结果。

在表四中，GCN是进行全批次培训的基线方法。GraphSage以牺牲时间效率为代价节省内存。同时，GraphSage的时间复杂度和内存复杂度随着K和r的增加呈指数增长。StoGCN的时间复杂程度最高，内存瓶颈仍未解决。然而，Sto-GCN可以在非常小的r下实现令人满意的性能。Cluster-GCN的时间复杂度与基线方法相同，因为它不会引入冗余计算。在所有方法中，ClusterGCN实现了最低的内存复杂度。

谱模型和空间模型的比较?谱模型在图信号处理中具有理论基础。通过设计新的图信号滤波器（例如Cayleynets），可以构建新的ConvGNNS。然而，由于效率、通用性和灵活性问题，空间模型优于谱模型。首先，谱模型的效率低于空间模型。谱模型要么需要执行特征向量计算，要么同时处理整个图。空间模型对于大型图更具可扩展性，因为它们通过信息传播在图域中直接执行卷积。计算可以在一批节点而不是整个图中执行。其次，依赖于图傅里叶基的谱模型很难推广到新的图。它们假设一个固定图。对图的任何扰动都会导致特征基的变化。另一方面，基于空间的模型在每个节点上局部执行图卷积，其中权重可以容易地在不同位置和结构之间共享。第三，基于谱的模型仅限于对无向图进行操作。基于空间的模型更灵活地处理多源图输入，如边输入、有向图、有符号图和异构图，因为这些图输入可以很容易地合并到聚合函数中。

C.图池化模块

GNN生成节点特征后，我们可以将其用于最终任务。但直接使用所有这些特性在计算上可能具有挑战性，因此需要一种降采样策略。根据目标及其在网络中所起的作用，该策略有不同的名称：（1）池化操作旨在通过对节点进行下采样以生成更小的表示来减小参数的大小，从而避免过拟合、置换不变性和计算复杂性问题；（2）读出操作主要用于基于节点表示生成图级表示。它们的机制非常相似。在本章中，我们使用池化来指代应用于GNN的各种降采样策略。

在一些早期的工作中，图粗化算法使用特征分解根据图的拓扑结构对图进行粗化。然而，这些方法存在时间复杂性问题。Graclus算法是计算原始图聚类版本的特征分解的替代方法。最近的一些工作将其用作对图进行粗化的池操作。

如今，均值/最大值/求和池化是实现下采样的最原始和最有效的方法，因为在池化窗口中计算均值/最大数/求和很快： $h_G=mean/max/sum(h_1^{(k)},h_2^{(k)},\cdots,h_n^{(k)}),$ 其中K是最后一个图卷积层的序号。

Henaff等人表明，在网络开始时执行简单的最大/平均池化对于降低图域的维数和降低昂贵的图傅里叶变换操作的成本尤为重要。此外，一些工作还使用注意力机制来增强平均/求和池化。

即使使用注意力机制，缩减操作（如求和池化）也不令人满意，因为它使嵌入效率低下：无论图大小如何，都会生成固定大小的嵌入。Vinyals等人提出了Set2Set方法来生成随输入大小而增加的内存。然后，它实现了一个LSTM，该LSTM打算在缩减使用之前将依赖于顺序的信息集成到内存嵌入中，否则会破坏该信息。

Defferard等人通过以有意义的方式重新排列图的节点，以另一种方式解决了这个问题。他们在ChebNet方法中设计了一种有效的池化策略。首先通过Graclus算法将输入图粗化为多个层次。粗化后，输入图及其粗化版本的节点重新排列为平衡二叉树。从下到上任意聚合平衡二叉树将相似节点排列在一起。池化这种重新排列的信号比池化原始信号更有效。

Zhang等人提出了DGCNN，其具有类似的池策略，名为SortPooling，通过将节点重新排列到有意义的顺序来执行池化。与ChebNet不同，DGCNN根据节点在图中的结构角色对节点进行排序。来自空间图卷积的图的无序节点特征被视为连续WL颜色，然后用于对节点进行排序。除了对节点特征进行排序外，它还通过截断/扩展节点特征矩阵将图的大小统一为q。最后的n-q行会被删除，如果 $n>q$ ，否则添加q-n个零行。

上述池化方法主要考虑图的特征，而忽略图的结构信息。最近，提出了一种可微池化（DiffPool），它可以生成图的层次表示。与之前所有的粗化方法相比，DiffPool并不是简单地对图中的节点进行聚类，而是在第k层学习聚类分配矩阵S， $S^{(k)}\in R^{n_k\times n_{k+1}}$ ,其中 $n_k$ 是第k层的节点数量。矩阵 $S^{(k)}$ 中的概率值是基于节点特征和拓扑结构生成的，使用 $S^{(k)}=softmax(ConvGNN_k(A^{(k)},H^{(k)})).$ 其核心思想是学习综合节点分配，该分配考虑了图的拓扑和特征信息，因此等式28可以用任何标准ConvGNNs实现。然而，DiffPool的缺点是，它在池化后生成密集图，然后计算复杂度变为 $\mathcal{O}(n^2)$ 。

最近，提出了SAGPool方法，该方法考虑了节点特征和图拓扑，并以自注意力方式学习池化。

总的来说，池化是减少图大小的一个基本操作。如何提高池化的有效性和计算复杂性是一个有待研究的问题。

D.理论方面的讨论

我们从不同的角度讨论了图神经网络的理论基础。

感受野的大小?节点的感受野是有助于确定其最终节点表示的一组节点。当组合多个空间图卷积层时，一个节点的感受野每次都会朝着其遥远的邻居向前增长一步。Micheli证明存在有限数量的空间图卷积层，使得对于每个节点 $v\in V$ 节点V的感受野覆盖图中的所有节点。因此，ConvGNN能够通过堆叠局部图卷积层来提取全局信息。

VC维?VC维是模型复杂度的度量，定义为模型可以破坏的最大点数。关于GNN的VC维数分析的工作很少。给定模型参数的数量p和节点数量n，Scarselli等人推导出，如果使用sigmoid或正切双曲激活函数，GNN的VC维数为 $\mathcal{O}(p^4n^2)$ ，如果使用分段多项式激活函数，则为 $\mathcal{O}(p^2n)$ 。这一结果表明，GNN的模型复杂性会随p和n迅速增加，如果使用sigmoid或正切双曲线激活函数。

图同构?如果两个图拓扑相同，则它们同构。给定两个非同构图G1和G2，Xu等人证明，如果GNN将G1和G1映射到不同的嵌入，则这两个图可以通过Weisfeiler-Lehman（WL）同构测试识别为非同构。他们表明，常见的GNN（如GCN和GraphSage）无法区分不同的图结构。Xu等人进一步证明，如果GNN的聚合函数和读出函数是内射的，则GNN在区分不同图方面最多与WL测试一样强大。

等变和不变?当执行节点级任务时，GNN必须是等变函数，并且当执行图级任务时必须是不变函数。对于节点级任务，让 $f(A,X)\in R^{n\times d}$ 是一个GNN，Q可以是改变节点顺序的任何置换矩阵。当GNN是等变时需要满足 $f(QAQ^T,QX)=Qf(A,X)$ .对于图级任务，让 $f(A,X)\in R^d$ .GNN是不变的如果满足 $f(QAQ^T,QX)=f(A,X)$ .为了实现等变或不变性，GNN的组件必须对节点顺序保持不变。Maron等人从理论上研究了图数据的置换不变和等变线性层的特征。

全局逼近?众所周知，具有一个隐层的多感知前馈神经网络可以逼近任何Borel可测函数。GNNs的全局逼近能力鲜有研究。Hammer等人证明了级联相关可以近似具有结构化输出的函数。Scarselli等人证明，RecGNN可以逼近任何精度保持展开等价的函数。如果两个节点的展开树相同，则这两个节点是展开等价的，其中通过在某个深度迭代扩展节点的邻域来构造节点的展开树形图。Xu等人表明，消息传递框架下的ConvGN不是多集上定义的连续函数的通用近似。Maron等人证明了不变图网络可以逼近图上定义的任意不变函数。

六、图自编码器

图形自编码器（GAE）是一种深度神经结构，它将节点映射到潜在特征空间，并从潜在表示中解码图信息。GAEs可用于学习网络嵌入或生成新图。表V总结了所选GAEs的主要特征。下面，我们从网络嵌入和图生成两个角度简要回顾了GAEs。

A.网络嵌入

网络嵌入是节点的低维向量表示，它保留了节点的拓扑信息。GAEs学习网络嵌入，通过使用编码器提取网络嵌入并使用解码器执行网络嵌入以保留图形拓扑信息，如PPMI矩阵和邻接矩阵。

早期的方法主要使用多层感知器来构建用于网络嵌入学习的GAEs。图表示学习的深度神经网络（DNGR）使用栈式去噪自动编码器，通过多层感知器对PPMI矩阵进行编码和解码。同时，结构深度网络嵌入（SDNE）使用栈式自编码器来联合保持节点的一阶估计和二阶估计。SDNE分别在编码器输出和解码器输出上提出了一个损失函数。第一个损失函数通过最小化节点的网络嵌入与其邻居的网络嵌入之间的距离，使得学习的网络嵌入能够保持节点的一阶邻近性。第一损失函数 $L_{1st}$ 定义为： $L_{1st}=\sum_{(u,v)\in E}A_{v,u}||enc(x_v)-enc(x_u)||^2,$ 其中 $x_v=A_{v,:}$ ， $enc(\cdot)$ 是一个包含多层感知器的编码器。第二损失函数使学习的网络嵌入能够通过最小化节点输入与其重构输入之间的距离来保持节点的二阶估计。具体而言，第二损失函数 $L_{2nd}$ 定义为： $L_{2nd}=\sum_{v\in V}||(dec(enc(x_v))-x_v)\odot b_v||^2,$ 其中， $b_{v,u}=1$ 如果 $A_{v,u}=0$ , $b_{v,u}=\beta>1$ 如果 $A_{v,u}=1$ ，并且 $dec(\cdot)$ 是由多层感知器组成的解码器。

DNGR和SDNE仅考虑节点结构信息，即节点对之间的连通性。它们忽略了节点可能包含描述节点自身属性的特征信息。图自编码器（GAE）利用GCN同时编码节点结构信息和节点特征信息。GAE的编码器由两个图卷积层组成，其形式如下： $Z=enc(X,A)=Gconv(f(Gconv(A,X;\Theta_1));\Theta_2),$ 其中Z表示图的网络嵌入矩阵， $f(\cdot)$ 是一个ReLU激活函数， $Gconv(\cdot)$ 函数是由等式12定义的图卷积层。GAE的解码器旨在通过重建图邻接矩阵来解码嵌入的节点关系信息，该矩阵定义为： $\hat{A}_{v,u}=dec(z_v,z_u)=\sigma(z^T_vz_u),$ 其中 $z_v$ 是节点v的嵌入。给定真实邻接矩阵A和重构邻接矩阵 $\hat A$ ，通过最小化负交叉熵来训练GAE。

由于自编码器的容量，简单地重建图邻接矩阵可能会导致过拟合。变分图自编码器（VGAE）是GAE一个变分版本以了解数据的分布。VGAE优化了变分下界L： $L=E_{q(Z|x,A)}[\log p(A|Z)]-KL[q(Z|X,A)||p(Z)],$ 其中 $KL(\cdot)$ 是Kullback-Leibler散度函数，用于度量两个分布之间的距离， $p(Z)$ 是一个高斯先验 $p(Z)=\prod_{i=1}^np(z_i)=\prod_{i=1}^nN(z_i|0,I),$ $p(A_{ij}=1|z_i,z_j)=dec(z_i,z_j)=\sigma(z_i^Tz_j),$ $q(Z|X,A)=\prod_{i=1}^nq(z_i|X,A)$ 同时 $q(z_i|X,A)=N(z_i|\mu_i,diag(\sigma_i^2)).$ 均值向量 $\mu_i$ 是由等式31定义的编码器输出的第i行， $\log \sigma_i$ 的推导类似于另一个编码器 $\mu_i$ 的推导。根据等式33,VGAE假设经验分布 $q(Z|X,A)$ 尽可能接近先验分布 $p(Z)$ 。为了进一步使经验分布 $q(Z|X,A)$ 近似先验分布 $p(Z)$ ，对抗正则化变分图自编码器（ARVGA）采用了生成对抗网络（GAN）的训练方案。在训练生成模型时，GAN在生成器和鉴别器之间进行竞争博弈。生成器尝试生成尽可能真实的“假样本”，而鉴别器尝试区分“假样本”和真实样本。受GANs的启发，ARVGA努力学习一种编码器，该编码器产生与先验分布 $p(Z)$ 不可区分的经验分布 $q(Z|X,A)$ 。

?与GAE类似，GraphSage使用两个图卷积层对节点特征进行编码。GraphSage没有优化重建误差，而是显示了两个节点之间的关系信息可以通过带损失的负采样来保持： $L(z_v)=-\log (dec(z_v,z_u))-QE_{v_n\sim P_n(v)}\log (-dec(z_v,z_{v_n})),$ 其中节点u是节点v的邻居，节点 $v_n$ 是节点v的一个远节点，从负采样分布 $P_n(v)$ 采样，Q是负采样数。该损失函数本质上强制近节点具有相似的表示，而远节点具有不同的表示。DGI通过最大化局部互信息来驱动局部网络嵌入以捕获全局结构信息。它在实验上比GraphSage有明显的改进。

对于上述方法，它们基本上通过解决链路预测问题来学习网络嵌入。然而，图的稀疏性导致正节点对的数量远小于负节点对的数目。为了缓解学习网络嵌入中的数据稀疏问题，另外一系列工作通过随机排列或随机游走将图转换为序列。这样，适用于序列的深度学习方法可以直接用于处理图。深度递归网络嵌入（DRNE）假设节点的网络嵌入应近似于其邻域网络嵌入的聚合。它采用长短时记忆（LSTM）网络来聚合节点的邻居。DRNE的重建误差定义为： $L=\sum_{v\in V}||z_v-LSTM({z_u|u\in N(v)})||^2,$ 其中， $z_v$ 是通过字典查找获得的节点v的网络嵌入，LSTM网络将节点v的邻居按其节点度排序的随机序列作为输入。如等式35所示，DRNE通过LSTM网络隐式学习网络嵌入，而不是使用LSTM网络生成网络嵌入。它避免了LSTM网络对节点序列排列不变性的问题。具有对抗正则化自编码器（NetRA）的网络表示提出了一种具有一般损失函数的图编码器-解码器框架，定义为： $L=-E_{z\sim P_{data}(z)}(dist(z,dec(enc(z)))),$ 其中， $dist(\cdot)$ 是节点嵌入z和重构z之间的距离度量。NetRA的编码器和解码器是LSTM网络，每个节点 $v\in V$ 上都有随机游走作为输入。与ARVGA类似，NetRA通过对抗性训练将学习到的网络嵌入规则化到先验分布中。虽然NetRA忽略了LSTM网络的节点排列不变形问题，但实验结果验证了NetRA的有效性。

B.图生成

对于多个图，GAEs能够通过将图编码为隐藏表示并解码给定隐藏表示的图结构来学习图的生成分布。大多数用于图生成的GAEs设计用于解决分子图生成问题，在药物发现中具有很高的实用价值。这些方法或者以顺序方式或者以全局方式提出新的图。

顺序方法通过逐步提出节点和边来生成图。Gomez等人、Kusner等人和Dai等人分别以深CNN和RNN作为编码器和解码器，对名为SMILES的分子图的字符串表示的生成过程进行建模。虽然这些方法是特定于域的，但替代解决方案也适用于一般图，方法是迭代地向增长图添加节点和边，直到满足某个标准。图的深度生成模型（DeepGMG）假设图的概率是所有可能节点排列的总和： $p(G)=\sum_\pi p(G,\pi),$ 其中 $\pi$ 表示节点排序。它捕获图中所有节点和边的复杂联合概率。DeepGMG通过一系列决策生成图，即是否添加节点、添加哪个节点、是否添加边以及连接到新节点的节点。生成节点和边的决策过程取决于由RecGNN更新的增长图的节点状态和图状态。在另一项工作中，GraphRNN提出了图级RNN和边级RNN来建模节点和边的生成过程。图级RNN每次向节点序列添加一个新节点，而边级RNN生成一个二进制序列，指示新节点与序列中先前生成的节点之间的连接。

全局方法一次输出一个图。图变分自编码器（GraphVAE）将节点和边的存在建模为独立随机变量。通过假设编码器定义的后验分布 $q_\phi(z|G)$ 和解码器定义的生成分布 $p_\theta(G|z)$ ，GraphVAE优化了变分下界： $L(\phi,\theta;G)=E_{q_\phi(z|G)}[\log p_\theta(G|z)]+KL[q_\phi(z|G)||p(z)],$ 其中 $p(z)$ 遵循高斯先验，φ和θ是可学习的参数。GraphVAE以ConvGNN作为编码器，以简单的多层感知机作为解码器，输出生成图包含邻接矩阵、节点属性和边缘属性。控制生成图的全局属性是一项挑战，如图的连通性、有效性和节点兼容性。正则化图变分自编码器（RGVAE）进一步对图变分自编码器施加有效性约束，以正则化解码器的输出分布。分子生成对抗网络（MolGAN）集成了ConvGNNS、GANs和强化学习目标，以生成具有所需属性的图。MolGAN由生成器和鉴别器组成，它们相互竞争以提高生成器的真实性。在MolGAN中，生成器试图提出一个伪图及其特征矩阵，而鉴别器旨在从经验数据中区分伪样本。此外，还引入了与鉴别器并行的奖励网络，以鼓励生成的图根据外部评估器具有某些属性。NetGAN将LSTM与Wasserstein-GANs相结合，通过基于随机游走的方法生成图。NetGAN训练生成器通过LSTM网络产生可信的随机游走，并强制使用鉴别器从真实随机游走中识别假随机游走。训练后，通过对基于生成器生成的随机游走计算的节点的共现矩阵进行归一化，得到一个新的图。

简而言之，序列方法将图线性化为序列。由于周期的存在，它们可能会丢失结构信息。全局方法一次生成一个图。它们不能扩展到大型图，因为GAE的输出空间高达 $\mathcal{O}(n^2)$ .

七、时空图神经网络

在许多实际应用中，图在图形结构和图形输入方面都是动态的。时空图神经网络在捕捉图的动态性方面占有重要地位。该类别下的方法旨在对动态节点输入建模，同时假设连接节点之间的相互依赖性。例如，交通网络由安装在道路上的速度传感器组成，其中边权重由传感器对之间的距离确定。由于一条道路的交通路况可能取决于其相邻道路的路况，因此在进行交通速度预测时，有必要考虑空间相关性。作为解决方案，STGNNS可以同时捕获图的空间和时间依赖关系。STGNNS的任务可以是预测未来的节点值或标签，或者预测时空图标签。STGNNS遵循两个方向，基于RNN的方法和基于CNN的方法。

大多数基于RNN的方法通过使用图卷积过滤传递到循环单元的输入和隐藏状态来捕获时空相关性。为了说明这一点，假设一个简单的RNN采用以下形式： $H^{(t)}=\sigma(WX^{(t)}+UH^{(t-1)}+b),$ 其中 $X^{(t)}\in R^{n \times d}$ 是t时刻的节点特征矩阵。在插入图卷积后，公式变成： $H^{(t)}=\sigma(Gconv(X^{(t)},A;W)+Gconv(H^{(t-1)},A;U)+b),$ 其中 $Gconv(\cdot)$ 是图卷积层。图卷积循环网络（GCRN）将LSTM网络与ChebNet相结合。扩散卷积循环神经网络（DCRNN）将提出的扩散图卷积层（等式18）合并到GRU网络中。此外，DCRNN采用编码器-解码器框架来预测节点值的未来K步。

另一项并行工作使用节点级RNN和边级RNN来处理时间信息的不同方面。结构RNN提出了一个循环框架，用于预测每个时间步的节点标签。它包括两种RNN，即节点RNN和边RNN。每个节点和每个边的时间信息分别通过节点RNN和边RNN。为了整合空间信息，节点RNN将边RNN的输出作为输入。由于为不同的节点和边假设不同的RNN显著增加了模型的复杂性，因此它将节点和边拆分为语义组。同一语义组中的节点或边共享相同的RNN模型，这节省了计算成本。

基于RNN的方法存在耗时的迭代传播和梯度爆炸/消失问题。作为替代解决方案，基于CNN的方法以非循环方式处理时空图，具有并行计算、稳定梯度和低内存需求的优点。如图2d所示，基于CNN的方法将1D-CNN层与图卷积层交错，以分别学习时间和空间相关性。假设时空图神经网络的输入是一个向量 $\chi \in R^{T \times n \times d}$ ，一维CNN层沿时间轴在 $\chi_{[:,i,:]}$ 上滑动以聚集每个节点的时间信息，而图卷积层在 $\chi_{[i,:,:]}$ 上操作以聚集每个时间步的空间信息。CGCN将一维卷积层与ChebNet或GCN层集成。它通过按顺序堆叠门控的一维卷积层、图卷积层和另一门控的一维卷积层来构造时空块。ST-GCN使用一维卷积层和PGC层组成时空块（等式20）。

以前的方法都使用预定义的图结构。他们假设预定义的图结构反映了节点之间真正的依赖关系。然而，由于在时空环境中有许多图数据快照，因此可以从数据中自动学习潜在的静态图结构。为了实现这一点，Graph WaveNet提出了一种自适应邻接矩阵来执行图卷积。自适应邻接矩阵定义为： $A_{adp}=SoftMax(ReLU(E_1E_2^T)),$ 其中沿行维度计算SoftMax函数，E1表示源节点嵌入，E2表示具有可学习参数的目标节点嵌入。通过将E1乘以E2，可以得到源节点和目标节点之间的依赖权重。对于复杂的基于CNN的时空神经网络，Graph WaveNet在没有给定邻接矩阵的情况下表现良好。

学习潜在的静态空间相关性可以帮助研究人员发现网络中不同实体之间可解释且稳定的相关性。然而，在某些情况下，学习潜在的动态空间相关性可以进一步提高模型精度。例如，在交通网络中，两条道路之间的行驶时间可能取决于它们当前的交通状况。GaAN采用注意力机制，通过基于RNN的方法学习动态空间相关性。在给定当前节点输入的情况下，使用注意力函数更新两个连接节点之间的边权重。ASTGCN还包括空间注意力函数和时间注意力函数，以通过基于CNN的方法学习潜在的动态空间依赖性和时间依赖性。学习潜在空间相关性的常见缺点是，它需要计算每对节点之间的空间相关性权重，其代价为 $\mathcal{O}(n^2)$ 。

八、应用

由于图结构数据无处不在，GNN有着广泛的应用。在本节中，我们分别总结了基准图数据集、评估方法和开源实现。我们详细介绍了GNN在各个领域的实际应用。

A、数据集

我们主要将数据集分为四组，即引用网络、生化图、社交网络和其他。在表六中，我们总结了选定的基准数据集。更多细节见补充材料A。

B、评估和开源实现

节点分类和图分类是评估RecGNNs和ConvGNNs性能的常见任务。

节点分类?在节点分类中，大多数方法都遵循对基准数据集（包括Cora、Citeseer、Pubmed、PPI和Reddit）进行训练/验证/测试的标准划分。他们记录了多次测试数据集的平均准确度或F1分数。补充材料B中总结了各种方法的实验结果。应注意的是，这些结果不一定代表严格的比较。Shchur等人在评估GNN节点分类性能时发现了两个缺陷。首先，在所有实验中使用相同的训练/验证/测试分割低估了泛化误差。其次，不同的方法采用了不同的训练技术，如超参数调整、参数初始化、学习速率衰减和早停机制。为了进行相对公平的比较，我们请读者参考Shchur文章。

图分类?在图分类中，研究人员通常采用10折交叉验证（cv）进行模型评估。然而，正如[132]所指出的，实验设置是模糊的，并且在不同的任务中并不统一。特别是，[132]提出了模型选择与模型评估中数据分割的正确使用问题。一个经常遇到的问题是，每一折的外部测试集用于模型选择和风险评估。[132]在标准化和统一的评估框架中比较GNN。他们应用外部10折CV来估计模型的泛化性能，并应用内部留一技术，将90%/10%的训练/验证分割用于模型选择。另一种方法是双cv法，使用外部k折cv进行模型评估，使用内部k折cv选择模型。我们请读者参阅[132]，以详细和严格地比较用于图分类的GNN方法。

开源实现促进了深度学习研究中基线实验的工作。在补充材料C中，我们提供了本文回顾的GNN模型的开源实现的超链接。值得注意的是，Fey等人发布了一个基于PyTorch的名为PytTorch?Geometric 几何学习库，该库实现了许多GNN。最近，发布了深度图库（DGL），它在流行的深度学习平台（如PyTorch和MXNet）上提供了许多GNN的快速实现。

C、实际应用

GNN在不同的任务和领域有许多应用。尽管一般任务可由每类GNN直接处理，包括节点分类、图分类、网络嵌入、图生成和时空图预测，但其他一般图相关任务，如节点聚类、链路预测和图划分，也可由GNN处理。我们详细介绍了基于以下研究领域的一些应用。

计算机视觉?GNNs在计算机视觉中的应用包括场景图生成、点云分类和动作识别。

识别对象之间的语义关系有助于理解视觉场景背后的含义。场景图生成模型旨在将图像解析为由对象及其语义关系组成的语义图。另一个应用程序是逆过程，通过生成给定场景图的真实图像。由于自然语言可以被解析为语义图，其中每个词代表一个对象，因此合成给定文本描述的图像是一个很有前途的解决方案。

对点云进行分类和分割可以使激光雷达设备“看到”周围环境。点云是由激光雷达扫描记录的一组3D点。将点云转换为k-最近邻图或超点图，并使用ConvGNNs探索拓扑结构。

识别视频中包含的人类动作有助于从机器方面更好地理解视频内容。一些解决方案检测视频剪辑中人体关节的位置。由骨骼连接的人体关节自然形成图。给定人类关节位置的时间序列，应用STGNNS学习人类动作模式。

此外，GNN在计算机视觉中的应用方向仍在不断增加。它包括人机交互、小样本图像分类、语义分割、视觉推理和问答。

自然语言处理?GNNs在自然语言处理中的一个常见应用是文本分类。GNN利用文档或单词的相互关系来推断文档标签。

尽管自然语言数据表现出序列顺序，但它们也可能包含内部图结构，如语法依赖树。句法依存树定义句子中单词之间的句法关系。Marcheggiani等人提出了在CNN/RNN句子编码器上运行的语法GCN。句法GCN基于句子的句法依赖树聚合隐藏词表示。Bastings等人将句法GCN应用于神经机器翻译任务。Marcheggiani等人进一步采用了与Bastings等人相同的模型来处理句子的语义依赖图。

图到序列学习学习在给定抽象词的语义图（称为抽象意义表示）的情况下生成具有相同含义的句子。Song等人提出了一种图LSTM来编码图级语义信息。Beck等人将GGNN应用于图形序列学习和神经机器翻译。反向任务是序列到图学习。生成给定句子的语义图或知识图谱在知识发现中非常有用。

交通?准确预测交通网络中的交通速度、交通量或道路密度在智能交通系统中至关重要。使用STGNNS解决流量预测问题。他们将交通网络视为一个时空图，其中节点是安装在道路上的传感器，边由节点对之间的距离测量，每个节点具有窗口内的平均交通速度作为动态输入特征。另一个工业级应用是出租车需求预测。鉴于历史计程车需求、位置信息、天气数据和事件特征，Yao等人将LSTM、CNN和LINE训练的网络嵌入结合起来，形成每个位置的联合表示，以预测时间间隔内某个位置所需的计程车数量。

推荐系统?基于图的推荐系统将项目和用户作为节点。通过利用项目与项目、用户与用户、用户与项目以及内容信息之间的关系，基于图形的推荐系统能够生成高质量的推荐。推荐系统的关键是给项目对用户的重要性进行评分。因此，可以将其转换为链路预测问题。为了预测用户和项目之间缺失的链接，Van等人和Ying等人提出了一种GAE，使用ConvGNNS作为编码器。Monti等人将RNN与图卷积相结合，以学习生成已知评级的基本过程。

化学?在化学领域，研究人员应用GNN研究分子/化合物的图结构。在分子/化合物图中，原子被视为节点，化学键被视为边。节点分类、图分类和图生成是针对分子/化合物图的三项主要任务，以学习分子指纹、预测分子性质、推断蛋白质界面和合成化合物。

其他情况 GNN的应用不限于上述领域和任务。已经有人探索将GNN应用于各种问题，如程序验证、程序推理、社会影响预测、对抗性攻击预防、电子健康记录建模、大脑网络、事件检测和组合优化。

九、未来方向

尽管GNN已经证明了其在学习图数据方面的能力，但由于图的复杂性，仍然存在挑战。在本节中，我们提出了GNN的四个未来方向。

模型深度?深度学习的成功在于深度神经架构。然而，Li等人表明，随着图卷积层数量的增加，ConvGNN的性能显著下降。由于图卷积使相邻节点的表示更加接近，理论上，对于无限多的图卷积层，所有节点的表示都将收敛到一个点。这就提出了一个问题，即提高深度来学习图数据是否仍然是一个好策略。

可伸缩性权衡?GNNs的可伸缩性是以破坏图的完整性为代价的。无论是使用采样还是聚类，模型都会丢失部分图形信息。通过采样，节点可能会丢失其有影响力的邻居。通过聚类，图可能被剥夺了独特的结构模式。如何权衡算法的可扩展性和图的完整性可能是未来的研究方向。

异质性?目前大多数GNN都采用同构图。很难将当前的GNN直接应用于异构图，因为异构图可能包含不同类型的节点和边，或不同形式的节点和边输入，如图像和文本。因此，应该开发新的方法来处理异构图。

动态性 图本质上是动态的，节点或边可能出现或消失，节点/边输入可能随时间变化。需要新的图卷积来适应图的动态性。虽然STGNNS可以部分解决图的动态性问题，但很少有人考虑在动态空间关系的情况下如何执行图卷积。

十、结论

在本综述中，我们对图神经网络进行了全面概述。我们提供了一种分类法，将图神经网络分为四类：循环图神经网络、卷积图神经网络，图自编码器和时空图神经网络。我们对类别内或类别之间的方法进行了全面的回顾、比较和总结。然后介绍了图神经网络的广泛应用。总结了图神经网络的数据集、开源代码和模型评估。最后，我们提出了图神经网络的四个未来方向。