题目： A Comprehensive Survey on Graph Neural Networks 会议： IEEE Transactions on Neural Networks and learning systems(TNNLS) 论文地址：A Comprehensive Survey on Graph Neural Networks

本文内容较多，一开始大致总结:

近年来，深度学习彻底改变了图像分类、视频处理、语音识别和自然语言理解等许多机器学习任务。这些任务中的数据通常是欧几里得数据。但现在，在越来越多的应用程序中，数据是由非欧几里德域生成的，并表示为图形结构，具有复杂的关系和对象之间的相互依赖。图形数据的复杂性对现有的机器学习算法提出了重大挑战。

GNN作为一种解决方案，是近年来比较热门的一个方向。本文对图神经网络(GNN)全面概述了数据挖掘和机器学习领域。

本文将是目前最前沿的GNN分为四类：循环GNN、卷积GNN、图自编码器和时空GNN。同时，本文进行了讨论GNN总结了各领域的应用GNN开源代码、基准数据集和模型评估。GNN未来可能的研究方向。

近年来，神经网络的成功促进了模型识别和数据挖掘等研究CNN、RNN和AE(自编码器)等应用广泛。

许多领域深度学习的成功部分归功于：

1. 快速发展的计算资源(如GPU)
2. 大量数据
3. 从欧几里德数据(如图像、文本和视频)中提取潜在表达的有效性。

上述嵌入算法属于第三种。

图数据对现有的机器学习算法提出了以下挑战：

1. 由于Graph可以是不规则的，一个Graph同时可能会有大小可变的无序节点Graph中间的节点可能有不同数量的邻居，导致一些重要的操作（如卷积）Image域内很容易计算，但Graph但是域内很难应用。
2. 现有机器学习算法的核心假设是例子是相互独立的，这种假设不再适用于图数据，因为每个例子(节))会通过各种类型的链接(如引用、友谊和交互)与其他实例(节点)相关联。

在CNN、RNN和AE的推动下，GNN逐渐发展起来。例如图卷积可以看作是二维卷积推广而来： 如上所示，可以将Image（左）看作是Graph（右）的一种特殊形式：Image中像素点和像素点之间通过边相连，二维卷积中我们在图像上移动卷积核，与此类似，在Graph中我们可以通过取一个节点的邻域信息的加权平均来执行图卷积。

本文贡献：

1. 提出了一种新的GNN分类方法，将GNN分为：recurrent GNN (RecGNN，循环GNN)、convolutional GNN(ConvGNN，卷积GNN)、graph autoencoder(GAE，图自编码器)和spatial-temporal GNN (STGNN，时空GNN)。
2. 全面的概述：对于每种类型的GNN，都对其中具有代表性的模型进行了详细的描述，并进行了必要的比较，总结了相应的算法。
3. 收集了大量关于GNN的资源，包括最先进的模型、基准数据集、开源代码和实际应用。本文可以作为实践指南，帮助读者理解、使用和开发针对各种实际应用程序的不同深度学习方法。
4. 未来研究方向：分析了现有方法的局限性，并从模型深度、可扩展性权衡、异质性和动态性四个方面提出了未来可能的研究方向。

（1）GNN简史： 这部分讲了GNN的大致发展历史：1997年Sperduti和Starita的一篇论文首先将神经网络应用于有向无环图，这拉开了GNN的序幕。GNN的概念最初由M. Gori等于2005年提出，早期的研究都属于RecGNN范畴。由于CNN在计算机视觉领域的成功，许多重新定义图形数据卷积概念的方法被提了出来，ConvGNN被分为两大类：频域方法（spectral-based method ）和空间域方法（spatial-based method）。2009年，Micheli在继承了来自RecGNN的消息传递思想的同时，在架构上复合非递归层，首次解决了图的相互依赖问题。在过去的几年里还开发了许多替代GNN，包括GAE和STGNN。

简单来说：RecGNN->ConvGNN->GAE和STGNN。

（2）GNN Versus Network Embedding： GNN的研究与图嵌入或网络嵌入密切相关，前面总结了几篇关于图嵌入的文章，有兴趣的可以看一看：

1. TKDE 2018 | 图嵌入综述
2. KDD 2014 | DeepWalk
3. KDD 2016 | node2vec
4. node2vec代码实现及详细解析
5. 节点聚类分析：DeepWalk + K-means

网络嵌入的目的是将网络节点表示为低维向量，同时保留网络拓扑结构和节点内容信息。 有了嵌入表示后，后续的如分类、聚类和推荐等，都可以使用现成的机器学习算法(如SVM)轻松实现。

GNN与网络嵌入的区别与联系： GNN是针对各种任务设计的一组神经网络模型，而网络嵌入是针对同一任务（将图表示成低维向量）的各种方法。联系：GNN可以通过GAE框架解决网络嵌入问题。当然除了GNN，网络嵌入还包含了其他非深度学习方法，如矩阵分解和随机漫步。

（3）GNN Versus Graph Kernel Methods： 图核用于解决图分类问题，图核使用一个核函数来度量图对之间的相似性，因此基于核的算法，如支持向量机，可以用于图的监督学习。与GNN类似，图核可以通过映射函数将图或节点嵌入到向量空间中。不同之处在于，图核中映射函数是确定的，而不是可学习的。图核方法由于需要进行两两相似度计算，因此存在很大的计算瓶颈，相比之下，GNN直接根据提取的图表示进行图分类，因此比图核方法效率高得多。

本文中粗体大写字符表示矩阵，粗体小写字符表示向量。各种定义如表1所示： 挑一些简单解释下：

A ⊙ B A \odot B A⊙B表示两个矩阵对应元素相乘；邻接矩阵 A A A：一个 n × n n \times n n×n的矩阵， A i j = 1    i f    ∃ e i j ∈ E    e l s e    A i j = 0 A_{ij}=1 \ \ if\ \ \exists e_{ij} \in E \ \ else\ \ A_{ij}=0 Aij​=1  if  ∃eij​∈E  else  Aij​=0； D D D表示度矩阵，度矩阵是对角阵，对角上的元素为各个顶点的度； X ∈ R n × d X \in R^{n \times d} X∈Rn×d：每一行为一个节点的 d d d维特征向量；同理有边的特征矩阵 X e ∈ R m × c X^e \in R^{m \times c} Xe∈Rm×c：每一行为一条边的 c c c维特征向量。

Spatial-Temporal Graph：时空图。时空图是一种属性图，其中节点属性随时间动态变化。 时空图定义为：

需要区分特征向量和状态向量： 建议阅读图神经网络（GNN）的基本原理

本节将介绍GNN的分类。

如表2所示： GNN被分为RecGNN、ConvGNN(频域+空间域)、GAE以及STGNN，表的右边给出了对应的参考文献。

（1）Recurrent Graph Neural Networks： GNN的先驱，其目的是学习具有循环神经结构的节点表示，RecGNN假设图中的一个节点不断地与它的邻居交换信息/消息，直到达到稳定的均衡。

（2）Convolutional Graph Neural Networks： ConvGNN将网格数据的卷积运算推广到Graph数据。主要思想：聚合节点 v v v自身的特征 x v x_v xv​和其邻居的特征 x u x_u xu​来生成节点 v v v的表示。与RecGNN不同，ConvGNN通过堆叠多个图卷积层来提取节点表示，如下所示： (a)是用于节点分类的ConvGNN，(b)是用于图分类的ConvGNN。

（3）Graph Autoencoders： 图自编码器，GAE将节点/图编码到一个潜在的向量空间中，然后从编码信息中重构图数据。 GAE一般用于学习网络嵌入和图生成：在网络嵌入方面，GAE通过重构图结构信息(如图邻接矩阵)来学习潜在节点表示。对于图的生成，有些方法是逐步生成图的节点和边，而另一些方法是一次性输出一个图。 下图是用于网络嵌入的GAE：

（4）Spatial–Temporal Graph Neural Networks： 时空GNN，旨在从时空图中学习隐藏模式，如交通速度预测、驾驶员机动预测和人类行为识别。STGNN的关键思想：同时考虑空间依赖性和时间依赖性。 目前许多方法将图卷积与RNN或CNN结合以捕获空间依赖性来建模时间依赖性。下图是用于时空图预测的STGNN：

GNN的输出分为： （1）Node Level： 输出与节点回归和节点分类任务相关。RecGNN和ConvGNN可以通过消息传递/图卷积提取高级节点表示，然后利用多感知器或Softmax层作为输出层，GNN能够以端到端方式执行节点级任务。 （2）Edge Level： 输出涉及到边缘分类和链接预测任务。比如以GNN中两个节点的状态作为输入，利用相似函数或神经网络来预测边缘的标记/连接强度。 （3）Graph Level： 输出与图分类任务相关。为了在图级别上获得较为有效的表示，GNN通常与池化和读出操作相结合。

训练框架：许多GNN(例如ConvGNN)可以在端到端学习框架中以(半)监督或纯粹无监督的方式进行训练，这取决于现有的学习任务和标签信息。 （1）Semisupervised Learning for Node-Level Classification： 节点级别分类的半监督学习，给定一个部分节点被标记而其余节点未标记的网络，ConvGNN可以有效地识别未标记节点的类标签。ConvGNN可以通过堆叠两个图卷积层和一个softmax层来实现多类分类。

（2）Supervised Learning for Graph-Level Classification： 图级别分类的监督学习，预测整个图的类标签。如下所示： 可以通过图卷积层(Gconv)、图池层(Pooling)和/或读出层(Readout)的组合来实现。Gconv负责精确高层次的节点表示，Pooling下采样，每次都将每个图粗化为子结构。Readout将每个图的节点表示折叠为一个图表示。最后通过将多层感知器MLP和softmax层应用于图的表示，可以建立一个端到端的图分类框架。

（3）Unsupervised Learning for Graph Embedding： 图嵌入的无监督学习，当图中没有可用的类标签时，我们可以在端到端框架中以完全无监督的方式学习图的嵌入。一种简单的方法是采用自编码器框架，其中编码器使用图卷积层将图嵌入到潜在表示中，在此基础上使用解码器重构图结构。另一种流行的方法是利用负抽样方法，将部分节点对作为负对进行抽样，而图中已有的具有链接的节点对是正对，然后应用逻辑回归层来区分正对和负对。

表3总结了具有代表性的RecGNN和ConvGNN，比较了各种模型的输入层、池化层、读出层和时间复杂度：

第四节讲述RecGNN的相关知识，实际上在之前的图神经网络（GNN）的基本原理中已经对RecGNN的原理进行了推导。

由于计算能力限制，早期RecGNN主要研究有向无环图。Scarselliet提出的GNN* 扩展了以前的循环模型来处理一般类型的图，例如，无环图、循环图、有向图和无向图。基于信息扩散机制，GNN*通过不断交换邻域信息来更新节点状态，直到达到稳定均衡（相互连接的节点间交换信息，GNN核心）。节点的隐藏状态由以下函数来进行周期性更新： 节点 v v v最初的状态向量为 h v ( 0 ) h_v^{(0)} hv(0)​，随机初始化。 u u u是 v v v的邻居节点， x v x_v xv​和 x u x_u xu​是两个节点的特征向量， x v , u e x_{v,u}^e xv,ue​是边的特征向量， h u ( t − 1 ) h_u^{(t-1)} hu(t−1)​是 u u u上一时刻的状态向量。

可以看一下RNN的结构： RNN的隐藏层当前状态不仅和当前输入有关，也和上一时刻的状态有关，这与RecGNN是一致的。

Gated GNN (GGNN)，即门控GNN，其使用门控循环单位（GRU）作为递归函数。它的优势在于它不再需要用于协调参数以确保收敛。

GGNN中，一个节点隐藏状态由其之前的隐藏状态和邻居的隐藏状态（RNN中为之前隐藏状态和当前输入）更新： 这里 h v ( 0 ) = x v h_v^{(0)}=x_v hv(0)​=xv​，GGNN使用反向传播时间（BPTT）算法来学习模型参数，GGNN对大图的计算不太友好，这是因为GGNN需要在所有节点上多次运行递归函数，需要将所有节点的中间状态存储在内存中。

随机稳态嵌入(SSE)提出了一种学习算法，可扩展到更大的图：对于比较大的图，可以采样一个batch，然后分别做节点上状态的更新和梯度的计算。为了保持稳定性，将SSE的递归函数定义为历史状态和新状态的加权平均值，其形式为： α \alpha α是超参数， h v ( 0 ) h_v^{(0)} hv(0)​随机初始化。

值得一提的是，SSE并没有证明收敛性，即稳定节点状态的收敛标准未说明。

本节讲述ConvGNN的相关知识。 RecGNN使用相同的图循环层(Grec)来更新节点的表示，而ConvGNN使用不同的图卷积层(Gconv)来更新节点表示。

前面讲到，ConvGNN分为两种：基于频域的和基于空间域的。其中基于频域的方法通过从图信号处理的角度引入过滤器（卷积核的集合）来定义图卷积，其中图卷积运算被解释为从图信号中去除噪声。 基于空间域的ConvGNN继承了RecGNN的思想，通过消息传递来定义图卷积运算。

基于频域的ConvGNN：假设图是无向的。无向图的归一化图拉普拉斯矩阵定义为： L = I n − D − ( 1 / 2 ) A D − ( 1 / 2 ) L=I_n-D^{-(1/2)}AD^{-(1/2)} L=In​−D−(1/2)AD−(1/2) 其中 D D D是一个对角阵，对角上的元素表示对应节点的度。归一化图拉普拉斯矩阵具有实对称半正定的性质，因此可以被分解为： L = U Λ U T L=U\Lambda U^T L=UΛUT 其中 U = [ u 0 , u 1 , . . . , u n ] ∈ R n × n U=[u_0, u_1,...,u_n] \in R^{n \times n} U=[u0​,u1​,...,un​]∈Rn×n是特征值排序的特征向量矩阵， Λ \Lambda Λ是特征值对角矩阵，线代基础知识了。归一化图拉普拉斯矩阵的特征向量形成正交空间，即 U T U = I U^TU=I UTU=I。

对图进行处理时， x ∈ R n x \in R^n x∈Rn表示为所有节点的特征向量， x i x_i xi​为第 i i i个节点的特征向量。 x x x的图傅里叶变换为： ℑ ( x ) = U T x \Im(x)=U^Tx ℑ(x)=UTx，逆图傅里叶变换为： ℑ − 1 ( x ^ ) = U x ^ \Im^{-1}(\hat{x})=U\hat{x} ℑ−1(x^)=Ux^，其中 x ^ \hat{x} x^表示傅里叶变换的结果信号。

由以上定义可知，图傅里叶变换将输入图信号投影到标准化空间，其中空间基由标准化图拉普拉斯算子的特征向量形成。原始输入信号可以被表示为： x = ∑ i x ^ i u i x= \sum_{i}\hat{x}_iu_i x=∑i​x^i​ui​（逆图傅里叶变换）。

有了以上定义后，输入信号与过滤器 g ∈ R b g \in R^b g∈Rb间的卷积运算被定义为： 如果将过滤器表示为： g θ = d i a g ( U T g ) g_{\theta}=diag(U^Tg) gθ​=diag(U