图神经⽹络（GraphNeuralNetworks，GNN）综述作者：苏⼀
本⽂仅供学术交流、如有侵权，可联系删除。
本篇⽂章是对论⽂“Wu Z , Pan S , Chen F , et al. A Comprehensive Survey on Graph Neural Networks[J]. 2019.“”的翻译与笔记
⽬录
⼀、什么是图神经⽹络
⼆、有哪些图神经⽹络
三、图神经⽹络的应⽤
⼀、什么是图神经⽹络？
在过去的⼏年中，神经⽹络的成功推动了模式识别和数据挖掘的研究。许多机器学习任务，如⽬标检测、机器翻译和语⾳识别，曾经严重依赖⼿⼯的特征⼯程来提取信息特征集，最近被各种端到端的深度学习范式（例如卷积神经⽹络（CNN）、长短期记忆（LSTM）和⾃动编码器）彻底改变了。在许多领 域中，深度学习的成功部分归因于快速发展的计算资源（如GPU）和⼤量训练数据的可⽤性，部分归因于深度学习从欧⽒空间数据中提取潜在表⽰的有效性。 尽管深度学习在欧⽒空间中的数据⽅⾯取得了巨⼤的成功，但在许多实际的应⽤场景中的数据是从⾮欧式空间⽣成的，同样需要进⾏有效的分析。例如，在电⼦商务中，⼀个基于图的学习系统能够利⽤⽤户和产品之间的交互来做出⾮常准确的推荐。图数据的复杂性对现有的机器学习算法提出了重⼤挑战，这是因为图数据是不规则的。每个图都有⼀个⼤⼩可变的⽆序节点，图中的每个节点都有不同数量的相邻节点，导致⼀些重要的操作（例如卷积）在图像上很容易计算，但不再适合直接⽤于图域。此外，现有机器学习算法的⼀个核⼼假设是实例彼此独⽴。然⽽，对于图数据来说，情况并⾮如此，图中的每个实例（节点）通过⼀些复杂的链接信息与其他实例（邻居）相关，这些信息可⽤于捕获实例之间的相互依赖关系。 近年来，⼈们对深度学习⽅法在图数据上的扩展越来越感兴趣。在深度学习的成功推动下，研究⼈员借鉴了卷积⽹络、循环⽹络和深度⾃动编码器的思想，定义和设计了⽤于处理图数据的神经⽹络结构，由此⼀个新的研究热点——“图神经⽹络（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
在⼤学⾥学过《数字信号处理》这门课程的朋友应该会记得，在这门课上我们通过引⼊傅⾥叶变换将时域信号转换到频域进⾏分析，进⽽我们完成⼀些我们在时域上⽆法完成的操作，基于频谱的图卷积⽹络的核⼼思想正是来源于此。
在基于频谱的图神经⽹络中，图被假定为⽆向图，⽆向图的⼀种鲁棒数学表⽰是正则化图拉普拉斯矩阵，即
其中，A为图的邻接矩阵，D为对⾓矩阵且
正则化图拉普拉斯矩阵具有实对称半正定的性质。利⽤这个性质，正则化拉普拉斯矩阵可以分解为
，其中
U是由L的特征向量构成的矩阵， 是对⾓矩阵，对⾓线上的值为L的特征值。正则化拉普拉斯矩阵的特征向量构成了⼀组正交基。
在图信号处理过程中，⼀个图的信号
是⼀个由图的各个节点组成的特征向量， 代表第i个节点。
对图X的傅⾥叶变换由此被定义为
傅⾥叶反变换则为
其中 为傅⾥叶变换后的结果。
为了更好地理解图的傅⾥叶变换，从它的定义我们可以看出，它确实将输⼊图信号投影到正交空间，在正交空间中，基由正则化图拉普拉斯的特征向量构成。
转换后得到的信号 的元素是新空间中图信号的坐标，因此原来的输⼊信号可以表⽰为
正是傅⾥叶反变换的结果。
现在我们可以来定义对输⼊信号X的图卷积操作了
其中， 是我们定义的滤波器； 表⽰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的图卷积运算定义为：
其中α（·）是⼀个注意⼒函数，它⾃适应地控制相邻节点j对节点i的贡献。为了学习不同⼦空间中的注意⼒权重，GAT还可以使⽤多注意⼒：
2.2 Gated Attention Network (GAAN)
门控注意⼒⽹络（GAAN）还采⽤了多头注意⼒机制来更新节点的隐藏状态。然⽽，GAAN并没有给每个head部分配相等的权重，⽽是引⼊了⼀种⾃注意机制，该机制为每个head计算不同的权重。更新规则定义为，
其中 是反馈神经⽹络，⽽ 是第k个注意⼒head的注意⼒权重
2.3 Graph Attention Model (GAM)
图形注意⼒模型（GAM）提供了⼀个循环神经⽹络模型，以解决图形分类问题，通过⾃适应地访问⼀个重要节点的序列来处理图的信息。GAM模型被定义为
其中 是⼀个LSTM⽹络，fs是⼀个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中，⽣成器试图提出⼀个伪图及其特征矩阵，⽽鉴别器的⽬标是区分伪样本和经验数据。此外，还引⼊了⼀个与鉴别器并⾏的奖励⽹络，以⿎励⽣成的图根据外部评价器具有某些属性。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议