图神经网络（Graph Neural Networks，GNN）综述

date

Nov 15, 2021

Last edited time

Mar 27, 2023 08:42 AM

status

Published

slug

图神经网络（Graph_Neural_Networks，GNN）综述

一、什么是图神经网络？

在过去的几年中，神经网络的兴起与应用成功推动了模式识别和数据挖掘的研究。许多曾经严重依赖于手工提取特征的机器学习任务（如目标检测、机器翻译和语音识别），如今都已被各种端到端的深度学习范式（例如卷积神经网络（CNN）、长短期记忆（LSTM）和自动编码器）彻底改变了。曾有学者将本次人工智能浪潮的兴起归因于三个条件，分别是：

计算资源的快速发展（如 GPU）

大量训练数据的可用性

深度学习从欧氏空间数据中提取潜在特征的有效性

尽管传统的深度学习方法被应用在提取欧氏空间数据的特征方面取得了巨大的成功，但许多实际应用场景中的数据是从非欧式空间生成的，传统的深度学习方法在处理非欧式空间数据上的表现却仍难以使人满意。例如，在电子商务中，一个基于图（Graph）的学习系统能够利用用户和产品之间的交互来做出非常准确的推荐，但图的复杂性使得现有的深度学习算法在处理时面临着巨大的挑战。这是因为图是不规则的，每个图都有一个大小可变的无序节点，图中的每个节点都有不同数量的相邻节点，导致一些重要的操作（例如卷积）在图像（Image）上很容易计算，但不再适合直接用于图。此外，现有深度学习算法的一个核心假设是数据样本之间彼此独立。然而，对于图来说，情况并非如此，图中的每个数据样本（节点）都会有边与图中其他实数据样本（节点）相关，这些信息可用于捕获实例之间的相互依赖关系。

近年来，人们对深度学习方法在图上的扩展越来越感兴趣。在多方因素的成功推动下，研究人员借鉴了卷积网络、循环网络和深度自动编码器的思想，定义和设计了用于处理图数据的神经网络结构，由此一个新的研究热点——“图神经网络（Graph Neural Networks，GNN）” 应运而生，本篇文章主要对图神经网络的研究现状进行简单的概述。

需要注意的是，图神经网络的研究与图嵌入或网络嵌入密切相关，图嵌入或网络嵌入是数据挖掘和机器学习界日益关注的另一个课题。图嵌入旨在通过保留图的网络拓扑结构和节点内容信息，将图中顶点表示为低维向量，以便使用简单的机器学习算法（例如，支持向量机分类）进行处理。许多图嵌入算法通常是无监督的算法，它们可以大致可以划分为三个类别，即矩阵分解、随机游走和深度学习方法。同时图嵌入的深度学习方法也属于图神经网络，包括基于图自动编码器的算法（如 DNGR 和 SDNE）和无监督训练的图卷积神经网络（如 GraphSage）。下图描述了图嵌入和图神经网络在本文中的区别。

二、有哪些图神经网络？

在本文中，我们将图神经网络划分为五大类别，分别是：图卷积网络（Graph Convolution Networks，GCN）、图注意力网络（Graph Attention Networks）、图自编码器（ Graph Autoencoders）、图生成网络（ Graph Generative Networks）和图时空网络（Graph Spatial-temporal Networks）。

符号定义

1、图卷积网络（Graph Convolution Networks，GCN）

图卷积网络将卷积运算从传统数据（例如图像）推广到图数据。其核心思想是学习一个函数映射，通过该映射图中的节点可以聚合它自己的特征与它的邻居特征来生成节点的新表示。图卷积网络是许多复杂图神经网络模型的基础，包括基于自动编码器的模型、生成模型和时空网络等。下图直观地展示了图神经网络学习节点表示的步骤。

GCN 方法又可以分为两大类，基于谱（spectral-based）和基于空间（spatial-based）。

基于谱的方法从图信号处理的角度引入滤波器来定义图卷积，其中图卷积操作被解释为从图信号中去除噪声。基于空间的方法将图卷积表示为从邻域聚合特征信息，当图卷积网络的算法在节点层次运行时，图池化模块可以与图卷积层交错，将图粗化为高级子结构。如下图所示，这种架构设计可用于提取图的各级表示和执行图分类任务。

在下面，我们分别简单介绍了基于谱的 GCN 和基于空间的 GCN。

1.1 Spectral-based Graph Convolutional Networks

在基于谱的图神经网络中，图被假定为无向图，无向图的一种鲁棒数学表示是正则化图拉普拉斯矩阵，即

其中，为图的邻接矩阵，为对角矩阵, 是顶点的度矩阵且

💡

常用的拉普拉斯矩阵实际有三种：

Combinatorial Laplacian:

Symmetric normalized Laplacian:

Random walk normalized Laplacian:

正则化图拉普拉斯矩阵具有实对称半正定的性质。利用这个性质，正则化拉普拉斯矩阵可以分解为

，其中

是由的特征向量构成的矩阵，是对角矩阵，对角线上的值为的特征值。正则化拉普拉斯矩阵的特征向量构成了一组正交基。

在图信号处理过程中，一个图的信号是一个由图的各个节点组成的特征向量，代表第个节点。

对图的傅里叶变换由此被定义为

傅里叶反变换则为

其中为傅里叶变换后的结果。

为了更好地理解图的傅里叶变换，从它的定义我们可以看出，它确实将输入的图信号投影到正交空间，而这个正交空间的基（base）则是由正则化图拉普拉斯的特征向量构成。

转换后得到的信号的元素是新空间中图信号的坐标，因此原来的输入信号可以表示为

这正是傅里叶反变换的结果。

现在我们可以来定义对输入信号的图卷积操作了

其中，是我们定义的滤波器；表示 Hadamard product, 为逐点相乘。

假如我们定义这样一个滤波器 ,那么我们的图卷积操作可以简化表示为

基于谱的图卷积网络都遵循这样的模式，它们之间关键的不同点在于选择的滤波器不同。

现有的基于谱的图卷积网络模型有以下这些：Spectral CNN、Chebyshev Spectral CNN (ChebNet)、Adaptive Graph Convolution Network (AGCN)

基于谱的图卷积神经网络方法的一个常见缺点是，它们需要将整个图加载到内存中以执行图卷积，这在处理大型图时是不高效的。

1.2 Spatial-based Graph Convolutional Networks

基于空间的图卷积神经网络的思想主要源自于传统卷积神经网络对图像的卷积运算，不同的是基于空间的图卷积神经网络是基于节点的空间关系来定义图卷积的。

为了将图像与图关联起来，可以将图像视为图的特殊形式，每个像素代表一个节点，如下图 a 所示，每个像素直接连接到其附近的像素。通过一个 3×3 的窗口，每个节点的邻域是其周围的 8 个像素。这八个像素的位置表示一个节点的邻居的顺序。然后，通过对每个通道上的中心节点及其相邻节点的像素值进行加权平均，对该 3×3 窗口应用一个滤波器。由于相邻节点的特定顺序，可以在不同的位置共享可训练权重。同样，对于一般的图，基于空间的图卷积将中心节点表示和相邻节点表示进行聚合，以获得该节点的新表示，如图 b 所示。

一种共同的实践是将多个图卷积层叠加在一起。根据卷积层叠的不同方法，基于空间的 GCN 可以进一步分为两类：recurrent-based 和 composition-based 的空间 GCN。recurrent-based 的方法使用相同的图卷积层来更新隐藏表示，composition-based 的方法使用不同的图卷积层来更新隐藏表示。下图说明了这种差异。

1.3 Comparison Between Spectral and Spatial Models

作为最早的图卷积网络，基于谱的模型在许多与图相关的分析任务中取得了令人印象深刻的结果。这些模型在图信号处理方面有一定的理论基础。通过设计新的图信号滤波器，我们可以从理论上设计新的图卷积网络。然而，基于谱的模型有着一些难以克服的缺点，下面我们将从效率、通用性和灵活性三个方面来阐述。

在效率方面，基于谱的模型的计算成本随着图的大小而急剧增加，因为它们要么需要执行特征向量计算，要么同时处理整个图，这使得它们很难适用于大型图。基于空间的模型有潜力处理大型图，因为它们通过聚集相邻节点直接在图域中执行卷积。计算可以在一批节点中执行，而不是在整个图中执行。当相邻节点数量增加时，可以引入采样技术来提高效率。

在一般性方面，基于谱的模型假定一个固定的图，使得它们很难在图中添加新的节点。另一方面，基于空间的模型在每个节点本地执行图卷积，可以轻松地在不同的位置和结构之间共享权重。

在灵活性方面，基于谱的模型仅限于在无向图上工作，有向图上的拉普拉斯矩阵没有明确的定义，因此将基于谱的模型应用于有向图的唯一方法是将有向图转换为无向图。基于空间的模型更灵活地处理多源输入，这些输入可以合并到聚合函数中。因此，近年来空间模型越来越受到关注。

2、图注意力网络（Graph Attention Networks）

注意力机制如今已经被广泛地应用到了基于序列的任务中，它的优点是能够放大数据中最重要的部分的影响。这个特性已经被证明对许多任务有用，例如机器翻译和自然语言理解。如今融入注意力机制的模型数量正在持续增加，图神经网络也受益于此，它在聚合过程中使用注意力，整合多个模型的输出，并生成面向重要目标的随机行走。在本节中，我们将讨论注意力机制如何在图结构数据中使用。

2.1 Graph Attention Network (GAT)

图注意力网络（GAT）是一种基于空间的图卷积网络，它的注意机制是在聚合特征信息时，将注意机制用于确定节点邻域的权重。GAT 的图卷积运算定义为：

其中是一个注意力函数，它自适应地控制相邻节点对节点的贡献。为了学习不同子空间中的注意力权重，GAT 还可以使用多注意力：

2.2 Gated Attention Network (GAAN)

门控注意力网络（GAAN）还采用了多头注意力机制来更新节点的隐藏状态。然而，GAAN 并没有给每个 head 部分配相等的权重，而是引入了一种自注意机制，该机制为每个 head 计算不同的权重。更新规则定义为:

其中和是反馈神经网络，而是第个注意力 head 的注意力权重

2.3 Graph Attention Model (GAM)

图形注意力模型（GAM）提供了一个循环神经网络模型，以解决图形分类问题，通过自适应地访问一个重要节点的序列来处理图的信息。GAM 模型被定义为

其中是一个 LSTM 网络，是一个 step network，它会优先访问当前节点优先级高的邻居并将它们的信息进行聚合。

除了在聚集特征信息时将注意力权重分配给不同的邻居节点，还可以根据注意力权重将多个模型集合起来，以及使用注意力权重引导随机行走。尽管 GAT 和 GAAN 在图注意网络的框架下进行了分类，但它们也可以同时被视为基于空间的图形卷积网络。GAT 和 GAAN 的优势在于，它们能够自适应地学习邻居的重要性权重。然而，计算成本和内存消耗随着每对邻居之间的注意权重的计算而迅速增加。

3、Graph Autoencoders

图自动编码器是一类图嵌入方法，其目的是利用神经网络结构将图的顶点表示为低维向量。典型的解决方案是利用多层感知机作为编码器来获取节点嵌入，其中解码器重建节点的邻域统计信息，如 positive pointwise mutual information （PPMI）或一阶和二阶近似值。最近，研究人员已经探索了将 GCN 作为编码器的用途，将 GCN 与 GAN 结合起来，或将 LSTM 与 GAN 结合起来设计图自动编码器。我们将首先回顾基于 GCN 的 AutoEncoder，然后总结这一类别中的其他变体。

目前基于 GCN 的自编码器的方法主要有：Graph Autoencoder (GAE) 和 Adversarially Regularized Graph Autoencoder (ARGA)

图自编码器的其它变体有：

Network Representations with Adversarially Regularized Autoencoders (NetRA)

Deep Neural Networks for Graph Representations (DNGR)

Structural Deep Network Embedding (SDNE)

Deep Recursive Network Embedding (DRNE)

DNGR 和 SDNE 学习仅给出拓扑结构的节点嵌入，而 GAE、ARGA、NetRA、DRNE 用于学习当拓扑信息和节点内容特征都存在时的节点嵌入。图自动编码器的一个挑战是邻接矩阵 A 的稀疏性，这使得解码器的正条目数远远小于负条目数。为了解决这个问题，DNGR 重构了一个更密集的矩阵，即 PPMI 矩阵，SDNE 对邻接矩阵的零项进行惩罚，GAE 对邻接矩阵中的项进行重加权，NetRA 将图线性化为序列。

4、Graph Generative Networks

图生成网络的目标是在给定一组观察到的图的情况下生成新的图。图生成网络的许多方法都是特定于领域的。例如，在分子图生成中，一些工作模拟了称为 SMILES 的分子图的字符串表示。在自然语言处理中，生成语义图或知识图通常以给定的句子为条件。最近，人们提出了几种通用的方法。一些工作将生成过程作为节点和边的交替形成因素，而另一些则采用生成对抗训练。这类方法要么使用 GCN 作为构建基块，要么使用不同的架构。

基于 GCN 的图生成网络主要有

Molecular Generative Adversarial Networks (MolGAN)：将 relational GCN、改进的 GAN 和强化学习（RL）目标集成在一起，以生成具有所需属性的图。GAN 由一个生成器和一个鉴别器组成，它们相互竞争以提高生成器的真实性。在 MolGAN 中，生成器试图提出一个伪图及其特征矩阵，而鉴别器的目标是区分伪样本和经验数据。此外，还引入了一个与鉴别器并行的奖励网络，以鼓励生成的图根据外部评价器具有某些属性。

Deep Generative Models of Graphs (DGMG)：利用基于空间的图卷积网络来获得现有图的隐藏表示。生成节点和边的决策过程是以整个图的表示为基础的。简而言之，DGMG 递归地在一个图中产生一个节点，直到达到某个停止条件。在添加新节点后的每一步，DGMG 都会反复决定是否向添加的节点添加边，直到决策的判定结果变为假。如果决策为真，则评估将新添加节点连接到所有现有节点的概率分布，并从概率分布中抽取一个节点。将新节点及其边添加到现有图形后，DGMG 将更新图的表示。

其它架构的图生成网络主要有

GraphRNN：通过两个层次的循环神经网络的深度图生成模型。图层次的 RNN 每次向节点序列添加一个新节点，而边层次 RNN 生成一个二进制序列，指示新添加的节点与序列中以前生成的节点之间的连接。为了将一个图线性化为一系列节点来训练图层次的 RNN，GraphRNN 采用了广度优先搜索（BFS）策略。为了建立训练边层次的 RNN 的二元序列模型，GraphRNN 假定序列服从多元伯努利分布或条件伯努利分布。

NetGAN：Netgan 将 LSTM 与 Wasserstein-GAN 结合在一起，使用基于随机行走的方法生成图形。GAN 框架由两个模块组成，一个生成器和一个鉴别器。生成器尽最大努力在 LSTM 网络中生成合理的随机行走序列，而鉴别器则试图区分伪造的随机行走序列和真实的随机行走序列。训练完成后，对一组随机行走中节点的共现矩阵进行正则化，我们可以得到一个新的图。

5、Graph Spatial-Temporal Networks

图时空网络同时捕捉时空图的时空相关性。时空图具有全局图结构，每个节点的输入随时间变化。例如，在交通网络中，每个传感器作为一个节点连续记录某条道路的交通速度，其中交通网络的边由传感器对之间的距离决定。图形时空网络的目标可以是预测未来的节点值或标签，或者预测时空图标签。最近的研究仅仅探讨了 GCNs 的使用，GCNs 与 RNN 或 CNN 的结合，以及根据图结构定制的循环体系结构。

目前图时空网络的模型主要有

Diffusion Convolutional Recurrent Neural Network (DCRNN)

CNN-GCN

Spatial Temporal GCN (ST-GCN)

Structural-RNN