回顾

图论的基本概念
图的表示和存储方式
同构图和异构图的分类
几个基础的图论算法
图机器学习的发展

六. 图神经网络（Graph Neural Networks）

结合论文：A Comprehensive Survey on Graph Neural Networks——Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, Philip S. Yu学习现在图神经网络的发展现状。

一、 什么是图神经网络

在过去的几年中，神经网络的兴起与应用成功推动了模式识别和数据挖掘的研究。许多曾经严重依赖于手工提取特征的机器学习任务（如目标检测、机器翻译和语音识别），如今都已被各种端到端的深度学习范式（例如卷积神经网络（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，GCNs）

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

GCN方法分类：两类

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

基于谱的方法：从图信号处理的角度引入滤波器来定义图卷积，其中图卷积操作被解释为从图信号中去除噪声。

基于空间的方法：将图卷积表示为从邻域聚合特征信息，当图卷积网络的算法在节点层次运行时，图池化模块可以与图卷积层交错，将图粗化为高级子结构。如下图所示，这种架构设计可用于提取图的各级表示和执行图分类任务。

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

1.1 基于谱的GCNs方法

在大学里学过《数字信号处理》这门课程的朋友应该会记得，在这门课上我们通过引入傅里叶变换将时域信号转换到频域进行分析，进而我们完成一些我们在时域上无法完成的操作，基于谱的图卷积网络的核心思想正是来源于此。

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

1.2 基于空间的GCNs方法

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

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

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

基于谱的模型缺点：

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

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

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

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

1.3 基于组合的空间GCNs方法——MPNNs和GraphSage

假设在第$t^{th}$-hop取样的邻居个数是$s_t$，GraphSage一个batch的时间复杂度是$O({\prod }_{t=1}^T{s}_t)$。因此随着ttt的增加计算量呈指数增加，这限制了GraphSage朝深入的框架发展。但是实践中，作者发现$t=2$已经能够获得很高的性能。

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

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

2.1 图注意力网络（Graph Attention Network，GAT）

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

2.2 门控注意力网络（Gated Attention Network，GAAN）

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

2.3 图形注意力模型（Graph Attention Model ，GAM）

图形注意力模型（GAM）提供了一个循环神经网络模型，以解决图形分类问题，通过自适应地访问一个重要节点的序列来处理图的信息。GAM模型被定义为
除了在聚集特征信息时将注意力权重分配给不同的邻居节点，还可以根据注意力权重将多个模型集合起来，以及使用注意力权重引导随机行走。尽管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作为构建基块，要么使用不同的架构。

基于GAN的图生成网络主要有:
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

三、 图神经网络的应用

1. 计算机视觉领域（Computer Vision）

图形神经网络的最大应用领域之一是计算机视觉。研究人员在场景图生成、点云分类与分割、动作识别等多个方面探索了利用图结构的方法。

在场景图生成中，对象之间的语义关系有助于理解视觉场景背后的语义含义。给定一幅图像，场景图生成模型检测和识别对象，并预测对象对之间的语义关系。另一个应用程序通过生成给定场景图的真实图像来反转该过程。自然语言可以被解析为语义图，其中每个词代表一个对象，这是一个有希望的解决方案，以合成给定的文本描述图像。

在点云分类和分割中，点云是激光雷达扫描记录的一组三维点。此任务的解决方案使激光雷达设备能够看到周围的环境，这通常有利于无人驾驶车辆。为了识别点云所描绘的物体，将点云转换为k-最近邻图或叠加图，并利用图论进化网络来探索拓扑结构。

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

此外，图形神经网络在计算机视觉中应用的可能方向也在不断增加。这包括人-物交互、少镜头图像分类、语义分割、视觉推理和问答等。

2. 推荐系统（Recommender Systems）

基于图的推荐系统以项目和用户为节点。通过利用项目与项目、用户与用户、用户与项目之间的关系以及内容信息，基于图的推荐系统能够生成高质量的推荐。推荐系统的关键是评价一个项目对用户的重要性。因此，可以将其转换为一个链路预测问题。目标是预测用户和项目之间丢失的链接。为了解决这个问题，有学者提出了一种基于GCN的图形自动编码器。还有学者结合GCN和RNN，来学习用户对项目评分的隐藏步骤。

3. 交通（Traffic）

交通拥堵已成为现代城市的一个热点社会问题。准确预测交通网络中的交通速度、交通量或道路密度，在路线规划和流量控制中至关重要。有学者采用基于图的时空神经网络方法来解决这些问题。他们模型的输入是一个时空图。在这个时空图中，节点由放置在道路上的传感器表示，边由阈值以上成对节点的距离表示，每个节点都包含一个时间序列作为特征。目标是预测一条道路在时间间隔内的平均速度。另一个有趣的应用是出租车需求预测。这有助于智能交通系统有效利用资源，节约能源。

4. 生物化学（Chemistry）

在化学中，研究人员应用图神经网络研究分子的图结构。在分子图中，原子为图中的节点，化学键为图中的边。节点分类、图形分类和图形生成是分子图的三个主要任务，它们可以用来学习分子指纹、预测分子性质、推断蛋白质结构、合成化合物。

5. 其他

除了以上四个领域外，图神经网络还已被探索可以应用于其他问题，如程序验证、程序推理、社会影响预测、对抗性攻击预防、电子健康记录建模、脑网络、事件检测和组合优化。

参考文献

1. 图神经网络（Graph Neural Networks，GNN）综述：https://zhuanlan.zhihu.com/p/75307407?from_voters_page=true
2. 论文翻译-A Comprehensive Survey on Graph Neural Networks《图神经网络GNN综述》https://blog.csdn.net/weixin_35479108/article/details/86308808
3. 深度学习时代的图模型，清华发文综述图网络https://www.jiqizhixin.com/articles/122304
4. 斯坦福大学新课CS224W-2019-图网络机器学习算法-视频及ppt资源分享https://zhuanlan.zhihu.com/p/98372970