前言

标题： A Comprehensive Survey on Graph Neural Networks

会议： IEEE Transactions on Neural Networks and learning systems(TNNLS)

论文地址：A Comprehensive Survey on Graph Neural Networks

本文的内容较多，在最开始时先大致总结一下：

1. 第1节Introduction简要介绍了本文内容，总结了本文奉献。
2. 第2节中简略介绍了GNN的开展前史，给出了GNN中的一些界说（需求区别特征向量和状况向量），然后对GNN和图嵌入进行了区别和联络。
3. 第3节中给出了一个GNN的分类原则，将GNN分为四类：recurrent GNN (RecGNN，循环GNN)、convolutional GNN(ConvGNN，卷积GNN)、graph autoencoder(GAE，图自编码器)和spatial-temporal GNN (STGNN，时空GNN)。第3节还从Node Level、Edge Level和Graph Level三个方面来介绍了GNN的输出办法，一起探讨了GNN的（半）监督学习和无监督学习结构。
4. 第4节介绍了RecGNN的相关常识。在之前的一篇博客图神经网络（GNN）的基本原理 中我对GNN的原始论文进行了解读，实践上这便是一种RecGNN。RecGNN的中心是音讯传递机制：经过不断交换邻域信息来更新节点状况，直到到达安稳均衡（相互衔接的节点间交换信息，GNN中心）。在本节中作者介绍了门控GNN（Gated GNN，GGNN）和随机稳态嵌入（SSE）两种RecGNN。
5. 第5节介绍了ConvGNN的相关常识。之前的一篇博客图解GNN：A Gentle Introduction to Graph Neural Networks里实践上现已对ConvGNN的大致原理进行了解说。与RecGNN运用相同的图循环层(Grec)来更新节点的标明不同的是，ConvGNN运用不同的图卷积层(Gconv)来更新节点标明。ConvGNN分为依据频域的ConvGNN和依据空间域的ConvGNN。依据频域的ConvGNN借助图的拉普拉斯矩阵的特征值和特征向量来研讨图的卷积，而依据空间域的ConvGNN则是依据节点的空间联络来界说图卷积。依据频域的ConvGNN首要介绍了Spectral CNN、ChebNet、CayleyNet和AGCN等，依据空间域的ConvGNN首要介绍了NN4G、DCNN、PGC-DGCNN。此外，本节还探讨了GNN中的Pooling，常见的Pooling操作有：sum、max以及mean，此外还介绍了SortPooling和DiffPool等一些变种。
6. 第6节介绍了GAE的相关常识。GAE是一种将节点映射到潜在特征空间并从其潜在标明中解码图形信息的深层神经网络。简略来说，需求先学习节点的状况向量，然后再从其间解码出图信息。因而，GAE一般用于学习网络嵌入标明或许来生成新的图。用于学习网络嵌入的GAE，作者介绍了DNGR、SDNE和VGAE。用于图生成的GAE，作者介绍了DeepGMG和GraphRNN。
7. 第7节介绍了STGNN的相关常识。在许多实在世界的运用程序中，图在图结构和图输入方面都是动态的。STGNN在图的动态捕捉中占有重要的方位，这类办法的方针是在假定衔接节点之间相互依靠的情况下，对动态节点输入进行建模。STGNN一起捕获图的空间和时刻依靠性，其使命可所以猜测未来的节点值或标签，也可所以猜测时空图标签。 STGNN有两个方向：依据RNN的办法和依据CNN的办法。依据RNN的STGNN，作者介绍了GCRN和DCRNN。依据CNN的STGNN，作者介绍了CGCN和ST-GCN。
8. 第8节介绍了GNN的一些运用。关于GNN，有两个比较盛行的结构：PyTorch Geometric和DGL。GNN在实践生活中的运用首要包括：CV范畴（场景图生成、点云分类和动作辨认）、NLP范畴（文本分类和机器翻译）、交通范畴（猜测交通网络中的交通速度、交通量或道路密度，出租车需求猜测）、引荐系统、化学范畴（分子指纹图谱、猜测分子性质、揣度蛋白质结构以及组成化合物）、其他范畴（如程序验证、程序推理、社会影响猜测、对立进犯防备、脑网络、事情检测、组合优化等）。
9. 第9节作者给出了GNN未来或许的4个研讨方向：深化学习图表数据是否是一个好的战略？怎么权衡算法的可扩展性和图的完整性？异质图怎么有用地处理？动态图中怎么进行有用卷积？
10. 第10节为总结。

Abstract

近年来，深度学习现已彻底改变了许多机器学习使命，如图画分类和视频处理以及语音辨认和自然语言了解。这些使命中的数据通常是欧几里得数据。但现在在越来越多的运用程序中，数据由非欧几里德域生成，并标明为具有复杂联络和方针间相互依靠联络的图结构。图数据的复杂性对现有的机器学习算法提出了严重挑战。

GNN作为一种处理方案，是近年来比较热门的一个方向。本文对图神经网络(GNN)在数据发掘和机器学习范畴进行了全面地概述。

本文将当时最前沿的GNN划分为4类：循环GNN、卷积GNN、图自编码器和时空GNN。一起本文评论了GNN在各个范畴的运用，总结了GNN的开源代码、基准数据集和模型点评。最后，提出了GNN未来或许的研讨方向。

I. Introduction

近年来神经网络的成功促进了方式辨认和数据发掘的研讨，如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. 未来研讨方向：分析了现有办法的局限性，并从模型深度、可扩展性权衡、异质性和动态性四个方面提出了未来或许的研讨方向。

II. Background And Definition

A. Background

（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直接依据提取的图标明进行图分类，因而比图核办法效率高得多。

B. Definition

本文中粗体大写字符标明矩阵，粗体小写字符标明向量。各种界说如表1所示：

挑一些简略解释下：

$A\odot B$标明两个矩阵对应元素相乘；邻接矩阵$A$：一个$nn$的矩阵，Aij=1if∃eij∈EelseAij=0A_{ij}=1 \ \ if\ \ \exists e_{ij} \in E \ \ else\ \ A_{ij}=0Aij​=1if∃eij​∈EelseAij​=0；$D$标明度矩阵，度矩阵是对角阵，对角上的元素为各个顶点的度；X∈RndX \in R^{n \times d}X∈Rnd：每一行为一个节点的$d$维特征向量；同理有边的特征矩阵Xe∈RmcX^e \in R^{m \times c}Xe∈Rmc：每一行为一条边的$c$维特征向量。

Spatial-Temporal Graph：时空图。时空图是一种特点图，其间节点特点随时刻动态改变。 时空图界说为：

III. Categorization And Frameworks

本节将介绍GNN的分类。

如表2所示：

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

A. Taxonomy of Graph Neural Networks

（1）Recurrent Graph Neural Networks： GNN的前驱，其目的是学习具有循环神经结构的节点标明，RecGNN假定图中的一个节点不断地与它的街坊交换信息/音讯，直到到达安稳的均衡。

（2）Convolutional Graph Neural Networks： ConvGNN将网格数据的卷积运算推广到Graph数据。首要思维：聚合节点$v$自身的特征xvx_vxv​和其街坊的特征xux_uxu​来生成节点$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：

B. Frameworks

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，比较了各种模型的输入层、池化层、读出层和时刻复杂度：

IV. Recurrent Graph Neural Networks

第四节叙述RecGNN的相关常识。

因为核算能力限制，前期RecGNN首要研讨有向无环图。Scarselliet提出的GNN* 扩展了以前的循环模型来处理一般类型的图，例如，无环图、循环图、有向图和无向图。依据信息分散机制，GNN*经过不断交换邻域信息来更新节点状况，直到到达安稳均衡（相互衔接的节点间交换信息，GNN中心）。节点的躲藏状况由以下函数来进行周期性更新：

节点$v$最初的状况向量为hv(0)h_v^{(0)}hv(0)​，随机初始化。$u$是$v$的街坊节点，xvx_vxv​和xux_uxu​是两个节点的特征向量，xv,uex_{v,u}^exv,ue​是边的特征向量，hu(t−1)h_u^{(t-1)}hu(t−1)​是$u$上一时刻的状况向量。

能够看一下RNN的结构：

RNN的躲藏层当时状况不仅和当时输入有关，也和上一时刻的状况有关，这与RecGNN是一致的。

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

GGNN中，一个节点躲藏状况由其之前的躲藏状况和街坊的躲藏状况（RNN中为之前躲藏状况和当时输入）更新：

这儿hv(0)=xvh_v^{(0)}=x_vhv(0)​=xv​，GGNN运用反向传播时刻（BPTT）算法来学习模型参数，GGNN对大图的核算不太友好，这是因为GGNN需求在一切节点上多次运转递归函数，需求将一切节点的中间状况存储在内存中。

随机稳态嵌入(SSE)提出了一种学习算法，可扩展到更大的图：关于比较大的图，能够采样一个batch，然后别离做节点上状况的更新和梯度的核算。为了坚持安稳性，将SSE的递归函数界说为前史状况和新状况的加权均匀值，其办法为：

\alpha是超参数，hv(0)h_v^{(0)}hv(0)​随机初始化。

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

V. Convolutional Graph Neural Networks

本节叙述ConvGNN的相关常识。

RecGNN运用相同的图循环层(Grec)来更新节点的标明，而ConvGNN运用不同的图卷积层(Gconv)来更新节点标明。

前面讲到，ConvGNN分为两种：依据频域的和依据空间域的。其间依据频域的办法经过从图信号处理的角度引进过滤器（卷积核的调集）来界说图卷积，其间图卷积运算被解释为从图信号中去除噪声。 依据空间域的ConvGNN承继了RecGNN的思维，经过音讯传递来界说图卷积运算。

A. Spectral-Based ConvGNN

依据频域的ConvGNN：假定图是无向的。无向图的归一化图拉普拉斯矩阵界说为： L=In−D−(1/2)AD−(1/2)L=I_n-D^{-(1/2)}AD^{-(1/2)}L=In​−D−(1/2)AD−(1/2) 其间$D$是一个对角阵，对角上的元素标明对应节点的度。归一化图拉普拉斯矩阵具有实对称半正定的性质，因而能够被分解为： L=UUTL=U\Lambda U^TL=UUT 其间U=[u0,u1,…,un]∈RnnU=[u_0, u_1,…,u_n] \in R^{n \times n}U=[u0​,u1​,…,un​]∈Rnn是特征值排序的特征向量矩阵，\Lambda是特征值对角矩阵，线代基础常识了。归一化图拉普拉斯矩阵的特征向量构成正交空间，即UTU=IU^TU=IUTU=I。

对图进行处理时，x∈Rnx \in R^nx∈Rn标明为一切节点的特征向量，xix_ixi​为第$i$个节点的特征向量。$x$的图傅里叶变换为：ℑ(x)=UTx\Im(x)=U^Txℑ(x)=UTx，逆图傅里叶变换为：ℑ−1(x)=Ux\Im^{-1}(\hat{x})=U\hat{x}ℑ−1(x)=Ux，其间x\hat{x}x标明傅里叶变换的结果信号。

由以上界说可知，图傅里叶变换将输入图信号投影到标准化空间，其间空间基由标准化图拉普拉斯算子的特征向量构成。原始输入信号能够被标明为：x=∑ixiuix= \sum_{i}\hat{x}_iu_ix=∑i​xi​ui​（逆图傅里叶变换）。

有了以上界说后，输入信号与过滤器g∈Rbg \in R^bg∈Rb间的卷积运算被界说为：

假如将过滤器标明为：g=diag(UTg)g_{\theta}=diag(U^Tg)g​=diag(UTg)，则图卷积能够简化为：

依据频域的ConvGNN都遵从以上界说，只是过滤器或许有所不同。

Spectral CNN假定过滤器g=i,j(k)g_{\theta}=\Theta_{i, j}^{(k)}g​=i,j(k)​是一组可学习的参数，Spectral CNN的图卷积层界说为：

其间$k$是层索引，H(k−1)∈Rnfk−1H^{(k-1)} \in R^{n \times f_{k-1}}H(k−1)∈Rnfk−1​是输入图信号，H0=XH_0=XH0​=X，fk−1f_{k-1}fk−1​为输入通道数，fkf_kfk​为输出通道数。

其他的一些依据频域的ConvGNN，如ChebNet、CayleyNet和AGCN等，这儿就不再具体介绍了。

B. Spatial-Based ConvGNN

依据空间域的ConvGNN：依据节点的空间联络来界说图卷积。

Image能够被视为Graph的特殊办法，每个像素代表一个节点，每个像素直接衔接到其附近的像素：

关于3×3窗口，每个节点的邻域便是其周围8个像素点。 相似地，依据空间域的图卷积将中心节点的标明与相邻节点的标明进行卷积，得到中心节点的更新标明。

图的神经网络（NN4G）是依据空间域的ConvGNN的第一个工作，它经过直接汇总节点的邻域信息来履行图卷积，NN4G导出的下一层的节点状况公式为：

$f$是激活函数，hv(0)h_v^{(0)}hv(0)​初始化为零向量。上式的矩阵办法为：

分散CNN (DCNN)以为图的卷积是一个分散进程。它假定信息以一定的搬运概率从一个节点搬运到它的一个相邻节点，使信息散布在几轮后到达均衡。DCNN将分散图卷积界说为：

其间$f$是激活函数，概率搬运矩阵P=D−1AP=D^{-1}AP=D−1A。因为分散的平稳散布是概率搬运矩阵幂级数的总和，因而DGC能够界说如下：

这儿W(k)∈RDFW^{(k)} \in R^{D \times F}W(k)∈RDF。需求注意的是，这儿运用了概率搬运矩阵的幂，这意味着远处的街坊对中心节点更新的奉献很少。

PGC-DGCNN依据最短途径增加了远处街坊的奉献。PGC-DGCNN界说了最短途径邻接矩阵S(j)S^{(j)}S(j)：假如节点$v$到结节点$u$的最短途径长度为$j$，则Sv,u(j)=1S_{v,u}^{(j)}=1Sv,u(j)​=1，不然为0。PGC-DGCNN中的图卷积运算界说如下：

式中D~ii(j)=∑lSi,l(j)\tilde{D}_{ii}^{(j)}=\sum_{l}S_{i,l}^{(j)}D~ii(j)​=∑l​Si,l(j)​，H(0)=XH_{(0)}=XH(0)​=X，$||$标明向量的衔接。

其他的一些变种不再具体了解了。

C. Graph Pooling Modules

在GNN生成了节点的状况向量之后，咱们能够将它们用于最后的猜测使命。但是，直接运用一切这些特征在核算上具有挑战性，因而，需求一种下采样战略。依据方针和它在网络中扮演的人物，这个战略有不同的名称：pooling或许readout。

其间：

1. pooling操作的目的是经过下降节点采样以生成更小的标明，然后削减参数的巨细，来避免过拟合和核算复杂性问题。
2. readout操作首要用于依据节点标明生成图级标明，与pooling操作相似。

现在较为常见的Pooling操作有：sum、max以及mean：

Henaff等人标明：在GNN开始时进行一个简略的max/mean pooling操作关于下降图域的维数和下降昂贵的图傅里叶变换操作的价值尤为重要。此外，还有一些论文中运用Attention机制来增强mean/sum pooling。

但是，即使在Attention机制下，池化操作也不能令人满意，因为它使嵌入效率低下：不管图形巨细怎么，都会生成固定巨细的嵌入。鉴于此，Vinyalset等人提出了Set2Set办法来生成一个随输入巨细增加而增大的内存。然后，完成了一个LSTM，该LSTM打算在运用还原之前将依靠于次序的信息集成到内存嵌入中，不然，就会损坏该信息。

Defferrardet等人经过以一种有意义的办法重新摆放图的节点，以另一种办法处理了这个问题。他们在ChebNet中规划了一个有用的池化战略：输入图首先经过Graclus算法粗化成多个层次；粗化后，输入图及其粗化版本的节点被重新摆放成一个平衡二叉树；然后从下到上任意聚合平衡二叉树，将相似的节点摆放在一起。他们的结果标明：池化这样一个重新摆放的信号比池化原始信号要有用得多。

Zhanget等人在DGCNN中提出了具有相似的一种池化战略SortPooling。它经过将节点按有意义的次序重新摆放来履行池化。与ChebNet不同，DGCNN依据节点在图中的结构人物对节点进行排序。将空间图卷积中图的无序节点特征视为接连的WL颜色，然后运用这些特征对节点进行排序。在对节点特征进行排序的一起，经过切断/扩展节点特征矩阵来统一图的巨细。

上述几种池化办法首要考虑图的特征，忽略了图的结构信息。最近，提出了一种可微池化(DiffPool)，它能够生成图的层次标明。与之前一切的粗化办法比较，DiffPool不是简略地将图中的节点聚类，而是在第k层学习到一个聚类分配矩阵S，记为S(k)∈Rnknk+1S^{(k)} \in R^{n_k \times n_{k+1}}S(k)∈Rnk​nk+1​，其间nkn_knk​为第k层的节点数。矩阵S(k)S^{(k)}S(k)中的概率值是依据节点的特征和拓扑结构来生成的：

最近提出的SAGPool办法考虑了节点特征和图拓扑，并以自注意的办法学习池化操作。

总的来说，池化是减小图巨细的基本操作。怎么提高池化的有用性是一个有待研讨的问题。

VI. Graph Autoencoders

第六节叙述图自编码器的相关常识。

阅览前主张先了解一下自编码器的常识：DL入门(2)：自编码器(AutoEncoder)

GAE是一种将节点映射到潜在特征空间并从其潜在标明中解码图形信息的深层神经网络。

简略来说，需求先学习节点的状况向量，然后再从其间解码出图信息。因而，GAE一般用于学习网络嵌入标明或许来生成新的图。

下面将从网络嵌入和图生成两个方面来回忆GAE。

A. Network Embedding

GAE用于学习网络嵌入时的机理为：运用编码器来提取网络嵌入，并运用解码器来加强网络嵌入，以保存图的拓扑信息（如PPMI矩阵和邻接矩阵）。

前期的办法首要是运用多层感知器构建用于网络嵌入学习的GAE，下面解说一些具体的实例。

用于图标明的深度神经网络(DNGR)运用堆叠降噪自编码器，经过多层感知器对PPMI矩阵进行编码和解码。

此外，结构深度网络嵌入(structural deep network embedding, SDNE)选用堆叠式自编码器，一起坚持节点的一阶附近度和二阶附近度。

DNGR和SDNE只考虑节点结构信息，即节点对之间的连通性。它们忽略了或许包括描绘节点自身特点的特征信息的节点。GAE* 运用GCN对节点结构信息和节点特征信息一起进行编码。GAE*的编码器由两个图卷积层组成，其办法为:

这儿$Z$标明图的网络嵌入矩阵，$f$为ReLU，Gconv为图卷积。

GAE* 的解码器旨在经过重构图邻接矩阵，将节点联络信息从其嵌入中解码出来，其界说为：

这儿zvz_vzv​标明节点$v$的嵌入标明。GAE*经过给定实邻接矩阵A和重构邻接矩阵A\hat{A}A最小化负交叉熵进行练习。

因为自编码器的容量，简略地重构图邻接矩阵或许会导致过拟合。Variational GAE (VGAE)是一种学习数据散布的变分GAE。关于变分图自编码器这儿不再具体阐明。

B. Graph Generation

关于多个图，GAE能够经过将图编码成躲藏标明，并将给定躲藏标明的图结构解码来学习图的生成散布。大多数用于图生成的GAE都是为了处理分子图生成问题而规划的，在药物发现中具有很高的实用价值。 这些办法要么以次序的办法提出一个新的图，要么以全局的办法提出一个新的图。

这儿的要害在于：将给定躲藏标明的图结构解码来学习图的生成散布。

次序办法经过逐渐提出节点和边来生成图。Gmez-Bombarelliet和Kusneret等人别离以深度CNN和RNN作为编码器和解码器，对名为SMILES的分子图串标明的生成进程进行建模。尽管这些办法都是运用于特定范畴的，但经过迭代地向增加的图中添加节点和边，直到满意某个条件，也能够运用于一般的图。

图的深度生成模型(DeepGMG)假定一个图的概率是一切或许的节点摆放的总和：

其间\pi标明节点排序。DeepGMG经过一系列决议计划来生成图，即是否增加一个节点，增加哪个节点，是否增加一条边，以及哪个节点衔接到新的节点。 生成节点和边的决议计划进程是依据节点状况和由RecGNN更新的增加图的图状况。

GraphRNN提出了一种图级RNN和一种边级RNN，对节点和边的生成进程进行建模。图级RNN每次在一个节点序列中添加一个新节点，而边际级RNN生成一个二进制序列，标明新节点与序列中从前生成的节点之间的衔接。

VII. Spatial–Temporal GNN

在许多实在世界的运用程序中，图在图结构和图输入方面都是动态的。STGNN在图的动态捕捉中占有重要的方位。这类办法的方针是在假定衔接节点之间相互依靠的情况下，对动态节点输入进行建模。

STGNN一起捕获图的空间和时刻依靠性。STGNN的使命可所以猜测未来的节点值或标签，也可所以猜测时空图标签。 STGNN有两个方向:依据RNN的办法和依据CNN的办法。

大多数依据RNN的办法经过运用图卷积过滤输入和传递到循环单元的躲藏状况来捕获时空相关性。为了阐明这一点，假定一个简略的RNN选用这种办法：

其间X(t)X_{(t)}X(t)​是$t$时刻的节点特征。刺进图卷积后，上式变成：

其间Gconv()为图卷积层。

图卷积循环网络(Graph convolutional recurrent network, GCRN)结合了LSTM网络和ChebNet。分散卷积RNN (DCRNN)[72]将一个提议的分散图卷积层纳入GRU网络。此外，DCRNN选用编码器-解码器结构猜测未来K个step节点值。

依据RNN的办法存在耗时的迭代传播和梯度爆炸/消失问题。作为代替处理方案，依据CNN的办法以非递归的办法处理时空图，具有可并行核算、安稳梯度和低内存需求的长处。

如下图所示：

依据CNN的STGNN将一维CNN卷积层与图卷积层交错在一起，别离学习时刻依靠和空间依靠。

CGCN将一维卷积层与ChebNet或GCN层进行集成。该算法经过次序叠加一个门控一维卷积层、一个图形卷积层和另一个门控一维卷积层来构建时空块。ST-GCN运用一维卷积层和PGC层构成时空块。

VIII. Applications

因为图形结构数据的普遍存在，GNN具有广泛的运用。在本节中，将别离总结基准图数据集、点评办法和开源完成，然后具体介绍了GNN在各个范畴的实践运用。

A. Data Sets

本文首要将数据集分为四类，别离是引文网络、生化图、社交网络和其他。

B. Evaluation and Open-Source Implementations

节点分类和图分类是点评RecGNN和ConvGNN功能的常用使命。

（1）节点分类：在节点分类中，大多数办法遵从基准数据集上的练习/验证/测试的标准切割，包括Cora、Citeseer、Pubmed、PPI和Reddit，他们报告了多次运转测试数据集的均匀准确性或F1得分。

（2）图分类：在图分类中，研讨人员经常选用十倍交叉验证(cv)进行模型点评。

（3）开源完成：Fey等人在PyTorch中发布了一个名为PyTorch Geometric的库，它完成了许多GNN。DGL在盛行的深度学习平台(如PyTorch和MXNet)上也供给了许多GNN的快速完成。

C. Practical Applications

这部分给出了GNN的一些实践运用，比较重要。

一般使命如节点分类、图分类、网络嵌入、图生成和时空图猜测等能够由GNN处理。其他与图相关的使命，如节点聚类、链接猜测和图划分等，也可由GNN处理。

（1）Computer Vision GNN在CV中的运用场景包括：场景图生成、点云分类和动作辨认。

场景图生成模型的效果是将图画解析为由方针及其语义联络组成的语义图，另一种运用是经过生成给定场景图的实在图画来逆转这一进程。因为自然语言能够被解析为语义图（其间每个单词代表一个方针），因而在给出文本描绘的情况下组成图画是一种很有出路的处理方案。

点云是激光雷达扫描记载的一组三维点，对点云进行分类和切割，能使激光雷达设备能够“看到”周围的环境。许多文献中将点云转换为最近邻图或上点图，并运用ConvGNN来研讨拓扑结构。

动作辨认：辨认视频中包括的人类动作有助于从机器角度更好地了解视频内容。一些处理方案检测视频片段中人体关节的方位。人类由骨骼衔接的关节自然会构成一个图形。考虑到人类关节方位的时刻序列，一些文献运用STGNN学习人类的动作方式。

此外，GNN在CV中的运用方向还在不断增加。包括人机交互、少镜头图画分类、语义切割、视觉推理、问答等。

（2）Natural Language Processing GNN在nlp中最常见的一个运用是文本分类，GNN能够运用文档或单词之间的相互联络来揣度文档标签。

自然语言数据中也或许包括图结构，如句法依存树，其界说了语句中单词之间的句法联络。Marcheggiani和Titov提出了运转在CNN/RNN语句编码器之上的句法GCN：句法型GCN依据语句的句法依存树聚合躲藏词标明。Bastingset等将句法GCN运用到神经机器翻译使命中。

Graph-to-sequence是经过给定笼统单词的语义图(称为笼统意义标明)来生成具有相同意义的语句。Songet等提出了一种graph-LSTM来编码图级语义信息。Becket等将GGNN运用于图到序列学习和神经机器翻译。与之相反的使命是序列到图的学习：在常识发现进程中，依据语句生成语义图或常识图十分有用。

（3）Traffic GNN在交通范畴运用也比较广泛：准确猜测交通网络中的交通速度、交通量或道路密度对智能交通系统至关重要。Zhanget和Liet等运用STGNN处理流量猜测问题：他们将交通网络视为一个时空图，其间节点是安装在道路上的传感器，节点对之间的间隔为边，每个节点以一个窗口内的均匀交通速度作为动态输入特征。另一个工业级运用是出租车需求猜测：在给定前史出租车需求、方位信息、天气数据和事情特征的情况下，yao等结合LSTM、CNN和LINE练习的网络嵌入，构成每个地址的联合标明，以猜测某一时刻段内某一地址的出租车需求量。

（4） Recommender Systems 引荐系统中的图以项和用户为节点：经过运用物品与物品、用户与用户、用户与物品以及内容信息之间的联络，能够产生高质量的引荐。引荐系统的要害是为一个项对用户的重要性打分。 因而，它能够被转换为一个链接猜测问题。为了猜测用户和商品之间缺失的链接，Berget等人和Yinget等人提出了一种运用ConvGNN作为编码器的GAE。

（5） Chemistry 在化学范畴，研讨者运用GNN来研讨分子/化合物的图结构。在分子/化合物图中，原子被视为节点，化学键被视为边。化学范畴中节点分类、图分类和图生成是分子/化合物图的三大首要使命，常见的运用有：学习分子指纹图谱、猜测分子性质、揣度蛋白质结构以及组成化合物。

（6）Others GNN的运用并不局限于上述范畴，其他的一些范畴如程序验证、程序推理、社会影响猜测、对立进犯防备、脑网络、事情检测、组合优化等，GNN也在其间发挥了效果。

IX. Future Directions

尽管GNN在学习图数据方面现已证明了其强大的能力，但因为图的复杂性，仍存在挑战。在本节中，作者给出了GNN未来的四个开展方向。

A. Model Depth

深度学习的成功在于深度神经架构，但是，Liet标明，跟着图卷积层数量的增加，ConvGNN的功能急剧下降。跟着图卷积将相邻节点的标明推向互相更近，理论上，在无限个图卷积层中，一切节点的标明将收敛到单个点。这就提出了一个问题：深化学习图数据是否是一个好的战略？

B. Scalability Tradeoff

GNN网络的可扩展性是以损坏图完整性为价值的。不管运用抽样仍是聚类，模型都会丢失部分图信息。经过抽样，一个节点或许会错过它有影响的街坊。经过聚类，一个图能够被剥夺一个明显的结构方式。因而，怎么权衡算法的可扩展性和图的完整性是未来的研讨方向。

C. Heterogenity

现在大多数GNN都是运用于同质图，当时的GNN算法很难直接运用于异质图，因为异质图或许包括不同类型的节点和边际，或许节点和边际输入办法不同，如图画和文本。因而，需求开发新的办法来处理异质图。

D. Dynamicity

图在本质上是动态的，节点或边或许出现或消失，节点/边输入也或许跟着时刻的推移而改变。为了习惯图的动态性，需求进行新的图卷积。尽管STGNN能够部分处理图的动态性问题，但很少有人考虑在动态空间联络的情况下怎么进行图的卷积。

X. Conclusion

本文中对GNN进行了全面的概述：供给了一种分类办法，将GNN分为四类：RecGNN、ConvGNN、GAE和STGNN，并对这几类GNN进行了全面的回忆、比较和总结。然后介绍了GNN的广泛运用：总结了GNN的数据集、开源代码和模型点评。最后，提出了GNN未来的四个开展方向。