CNN的核心特点在于：局部连接(local connection)，权重共享(shared weights)和多层叠加(multi-layer)

这些同样在图问题中非常试用，因为图结构是最典型的局部连接结构，其次，共享权重可以减少计算量，另外，多层结构是处理分级模式(hierarchical patterns)的关键。

传统的深度学习方法被应用在提取欧氏空间数据的特征方面取得了巨大的成功，但许多实际应用场景中的数据是从非欧式空间生成的，传统的深度学习方法在处理非欧式空间数据上的表现却仍难以使人满意。

CNN只能在欧几里得数据(Euclideandata)，比如二维图片和一维文本数据上进行处理，而这些数据只是图结构的特例而已，对于一般的图结构，则很难使用

图嵌入大致可以划分为三个类别：矩阵分解、随机游走和深度学习方法

图嵌入和GNN的区别👆

​ 图嵌入常⻅模型有DeepWalk，Node2Vec等，然而，这些方法方法有两种严重的缺点，首先就是节点编码中权重未共享，导致权重数量随着节点增多而线性增大，另外就是直接嵌入方法缺乏泛化能力，意味着无法处理动态图以及泛化到新的图

图(graph)是一种数据结构，常⻅的图结构包含节点(node)和边(edge)，GNN是深度学习在图结构上的一个分支。

GNN是一种连接模型，通过网络中节点之间的信息传递的方式来获取图中的依存关系，GNN通过从节点任意深度的邻居来更新该节点状态，这个状态能够表示状态信息。

第一次在论文 The graph neural network model 中提出

后面几节，对于 GNN 模型，我们引入了按图类型，传播类型和训练类型分类的变体。此外，我们还总结了几个统一表示不同变体的一般框架。在应用程序分类方面，我们将 GNN 应用程序划分为结构场景，非结构场景和其他场景，然后对每个场景中的应用程序进行详细介绍。最后，我们提出了四个开放性问题，指出了图神经网络的主要挑战和未来研究方向，包括模型深度，可扩展性，处理动态图和非结构场景的能力。

下面模型的原理部分只是体现了主要思想，如果想详细了解证明的话，可以看一下这一篇GNN原理详解

论⽂通⽤的符号表⽰以及对应含义说明：

在一个图结构中，每一个节点由它自身的特征以及与其相连的节点特征来定义该节点。

GNN 的目的就是为每个节点学习到一个状态嵌入向量 h v ∈ R s h_v∈R^s hv​∈Rs，这个向量包含每个节点的邻居节点的信息。 h v h_v hv​表示节点的状态向量，这个向量可以用于产生输出 o v o_v ov​。

假设 f ( ⋅ ) f(\cdot) f(⋅)是带有参数的函数，叫做局部转移函数(local transition function)，这个函数在所有节点中共享，并根据邻居节点的输入来更新节点状态

假设 g ( ⋅ ) g(\cdot) g(⋅)为局部输出函数(local output function)，这个函数用于描述输出的产生方式。

h v = f ( x v , x c o [ v ] , h n e [ v ] , x n e [ v ] ) (1) h_v=f(x_v,x_{co[v]},h_{ne[v]},x_{ne[v]})\tag{1} hv​=f(xv​,xco[v]​,hne[v]​,xne[v]​)(1)

o v = g ( h v , x v ) (2) \large o_v=g(h_v,x_v)\tag{2} ov​=g(hv​,xv​)(2)

​ x v x_v xv​表示节点v的特征向量， x c o [ v ] x_{co[v]} xco[v]​表示与节点v关联的边的特征向量， h n e [ v ] h_{ne[v]} hne[v]​表示节点v的邻居节点的状态向量， x n e [ v ] x_{ne[v]} xne[v]​表示节点v的邻居节点特征向量。

假设将所有的状态向量，所有的输出向量，所有的特征向量和所有的节点特征而得到的向量叠加起来，分别用 H , O , X , X N H,O,X,X_N H,O,X,XN​表示，那么可以得到更加紧凑的表示： H = F ( H , X ) (3) H=F(H,X)\tag{3} H=F(H,X)(3)

O = G ( H , X N ) (4) O=G(H,X_N)\tag{4} O=G(H,XN​)(4)

其中， F F F 和 G G G 分别称为全局转移函数和全局输出函数，是图中针对所有节点的 f f f 和 g g g 的堆叠版本。根据Banach的不动点定理，GNN使用如下的传统迭代方法来计算状态参量： H t + 1 = F ( H t , X ) (5) H^{t+1}=F(H^t,X)\tag{5} Ht+1=F(Ht,X)(5) 其中， H t H^t Ht 表示 H H H 的第 t t t 个迭代周期的张量。对于任意的初始值 H 0 H_0 H0​，公式（5）能通过快速收敛来得到公式（3）最终的固定点的解。

使用目标信息来进行监督学习，可以将损失函数定义为如下形式： l o s s = ∑ i = 1 p ( t i − o i ) (6) loss=\sum_{i=1}^p{(t_i-o_i)}\tag{6} loss=i=1∑p​(ti​−oi​)(6) p p p 表示监督节点的数目， t i t_i ti​ 和 o i o_i oi​ 分别表示节点的真实值和预测值。损失函数的学习基于梯度下降策略，由以下步骤组成：

主要是从图类型、传播类型和训练方法三个方面来对图神经网络的一些变体进行探讨。

原始的GNN输入的图结构包含带有标签信息的节点和无向边，这是最简单的图结构，但在现实生活中，存在多种图的变体👇，主要有有向图、异质图、带有边信息图和动态图：

​ 论文中的传播(propagation)指的是汇集从邻居节点和连接的边的信息，来对节点进行更新的过程，对于获取节点或者边的隐藏状态，神经网络中的传播步骤(propagation step)和输出步骤(output step)至关重要。在传播步骤方面的改进主要有卷积、注意力机制、门机制和跳跃连接（skip connection），而在输出步骤通常遵循**简单的前馈神经网络设置。

传播步骤主要的模型如下图👇

不同模型Aggregator计算方法和Updater计算方法如下表👇

(注：aggregator：聚合节点 i i i周围节点的信息，学习节点 i i i的嵌入，对应最开始的(1)式，updater：在学习过程中迭代更新节点 i i i的嵌入表示，对应最开始的（5式)

这方面的进展通常分为谱方法(Spectral Methods) 和非谱方法(Non-Spectral Methods)

Spectral Method 希望使用谱分解的方法，应用图的拉普拉斯矩阵分解进行节点的信息收集。

Non-Spectral Methods 直接使用图的拓扑结构，根据图的邻居信息进行信息收集。直接在图上定义卷积操作，也就是在空域上相邻的邻居节点上进行操作。

(详细了解)

图注意力网络(Graph Attention Network，GAT)致力于将注意力机制应用在图中的信息收集阶段。注意力机制在很多基于序列任务(sequence-based tasks)比如机器翻译、机器阅读理解等等上都产生了非常好的效果。

(详细了解)

这些变体将门机制应用于节点更新阶段。目前在信息传播步骤中使用的⻔机制类似于GRU和LSTM模型，这种机制可以减小原始GNN模型的约束，并提升在图结构中的⻓期的信息传播。Gated graph neural network 将 GRU 机制应用于节点更新。 LSTM ，根据具体情境的不同，可以分为 Tree LSTM、Graph LSTM 和 Sentence LSTM 等。

(详细了解)

多应用都会将图神经网络层进行叠加，来实现更好的结果，因为更多的层意味着每一个节点能够从更多的邻居节点中获取信息。但是，更深的模型反而可能表现更坏，主要因为随着指数个数上升的相邻节点数量，更多的层可能会汇集到更多的噪声信息。

很多工作将残差网络(residual network)应用于图神经网络中（但是，即使有残差网络，具有更多层的GCN在许多数据集上的性能不如2层GCN）。

(详细了解)

在计算机视觉中，一个卷积层后通常会接一个池化层，来得到更加一般的特征。类似的是，在图结构中，一种分层池化层也能够起到类似的效果，复杂的和大规模的图通常会包含丰富的分层结构，这种结构对于节点层次(node-level)和图层次(graph-level)的分类任务非常重要。

(详细了解)

原始的图卷积神经网络在训练和优化方法上有一些缺点，比如，GCN需要计算整个图拉普拉斯矩阵，这个操作对于大型的图计算量非常大，另外，在第 L L L层的节点的embedding，是通过第 L − 1 L-1 L−1层其周围所有邻居节点的embedding递归循环得到的，因此，单个节点的感知域（receptive field）相对于层数呈指数增长，单个节点的计算梯度成本很高。另外，GCN是对固定的图结构进行训练，缺乏归纳学习的能力。有以下几种改进的方法

除了提出图神经网络的不同变体之外，一些研究人员从神经网络的框架入手，提出了一些通用框架，旨在将不同模型集成到一个单一框架中。主要包括 Message Passing Neural Networks（MPNN）、Non-local Neural Networks（NLNN）以及 Graph Network（GN）等。

针对图结构的监督学习框架，MPNN[框架抽象了几种最流行的图形结构数据模型（如图卷积中的光谱方法和非光谱方法，门控神经网络，交互网络，分子图卷积，深度张量神经网络等）之间的共性，

该NLNN模型用于使用神经网络获取⻓远依赖信息，是对非局部平均运算的一种泛化，一个位置的non-local操作(非局部运算)使用所有位置的特征向量的加权和来作为该位置的信息。

GN结合MPNN和NLNN以及其它一些GNN变体

GN被提出来泛化和扩展多种图神经网络，以及 MPNN 和 NLNN 方法。本文主要介绍了图的定义、GN block、核心 GN 计算单元、计算步骤和基本设计原则。详细的内容扩展会另外写到专门针对该文献的阅读笔记当中。

论文《Relational inductive biases, deep learning, and graph networks》中对图的定义

GNN的应用大体分为以下几种：

应用的总结见下表👇（可以看出，还是非结构化场景场景居多）

物理系统应用(Physics)

GNN可以用于对现实世界中的物理系统建模，将物体表示为节点，将物体之间的关系表示为边，由此可以使用GNN模型对目标、关系进行推理。有如下一些论文研究相关内容：

化学和生物学应用(Chemistry and Biology)

GNN能够用于计算分子指纹(molecular fingerprints)，即使用特征向量来表示分子，用于下游任务，比如computer-aided drug design。另外，GNN也可以用于protein interface prediction，有助于药物研究。

知识图谱应用(Knowledge graph)

有论文采用GNN来解决基于out-of-knowledge-base的实体问题。也有论文采用GCN来解决跨语言的知识图谱对⻬任务，论文模型将不同语言的实体嵌入到向量空间，然后使用相似度进行实体对⻬。

图像任务(Image)

目前的图像分类任务由于大数据和GPU的强大并行计算能力获得很大的突破，但是zero-shot andfew-hot learning在图像领域仍然非常重要。有一些模型采用GNN结合图像的结构化信息来进行图像分类，比如，知识图谱可以用于额外的信息来指导zero-shot recognition classification。

GNN也可以用于visual reasoning，计算机视觉系统通常需要结合空间信息和语义信息来实现推理，因此，很自然地想到使用Graph来实现推理任务。一个典型的任务是visual questionanswering，该任务需要分别构建图像的场景图(scene graph)以及问题句法图(syntacticgraph)，然后使用GGNN来训练以及预测最终的结果。visual reasoning的其他应用还有objectdetection，interaction detection和region classification。

GNN还可以用于semantic segmentation，语义分割的任务在于对图像每一个像素预测出一个label，由于图像的区域往往不是网格形状的，并且需要全局信息，因此使用传统的CNN会有一些局限性，有一些论文采用图结构数据来解决这种问题。

文本任务(Text)

GNN能够应用到多个基于文本的任务上，既可以用于sentence-level的任务，也可以用于word-level的任务。

生成模型(Generative Models)

生成模型对于社会关系建模、新型化学结构发现以及构建知识图谱也有重要作用，有如下相关的研究论文：

组合优化(Combinatorial Optimization )

GNN能够应用于解决在graph上的NP-hard的优化问题，比如旅行商问题(TSP)，最小生成树问题(MSP)。

GNN模型目前仍然存在一些问题，我们将陈述一些开放性问题以供进一步研究。

浅层结构（Shallow Structure）

​ 传统的深度神经网络可以堆叠数百层以获得更好的性能，因为更深的结构具有更多的参数，从而能够显著提高表示能力。而实验显示，GCN叠加过多的层或导致over-smoothing问题，也就是说，最终所有的节点会收敛于相同的值图神经网络通常都很浅，所以图神经网络都很浅，大多数不超过三层。

​ 设计真正的深度 GNN 对于未来的研究来说是一个令人兴奋的挑战，并将对理解 GNN 做出相当大的贡献。

动态图结构（Dynamic Graphs）

​ 静态图是稳定的，因此比较好灵活地进行建模，但是动态图是动态的结构，建模较难（当边和节点出现或消失时，GNN 无法自适应地更改）。

​ 动态 GNN 正在积极研究中，我们认为它是一般 GNN 的稳定性和适应性的重要里程碑。

非结构性场景（Non-Structural Scenarios）

​ 虽然我们已经讨论了 GNN 在非结构场景中的应用，但我们发现没有最佳方法可以从原始数据生成图形。因此，找到最佳图形生成方法将提供 GNN 可以做出贡献的更广泛的领域。

可扩展性（Scalability）

​ 如何在社交网络或推荐系统(recommendation systems)等网络规模条件下应用embedding方法对于几乎所有图形嵌入算法来说都是一个致命的问题，而 GNN 也不例外。扩展 GNN 很困难，因为许多核心步骤在大数据环境中的计算成本都十分高。

​ 关于这种现象有几个例子：首先，图形数据不是规则的欧几里德，每个节点都有自己的邻域结构，因此不能应用批量(batches)。然后，当存在数百万个节点和边缘时，计算图Laplacian矩阵也是不可行的。此外，我们需要指出缩放确定算法是否能够应用于实际应用。