标签： Review，GNN

1. Introduction

图是一种可以建模实体（Node）和关系（Edge）的数据结构，能够在很多领域中得到应用——比如社交网络、物理模型系统、蛋白质结构、知识图谱等等，这些都属于非欧式（non-Euclidean）的数据，即不能通过欧式距离来表示实体之间的关系。
图分析用于：节点分类、连接关系预测、聚类等

使用GNN的动机一：源于CNN。CNN能够通过局部连接、共享权重、多层卷积（这三点对图结构特征提取也很重要）等方式提取多尺度的局部空间特征、并组合成具有丰富表达能力的表征（representation），但这只能用于欧式空间（2D图像、1D文本序列等，可以看作特殊的图），所以需要引入图结构的特征提取。

使用GNN的动机二：源于图嵌入（graph embedding）。graph embedding是指将图的结点、边或者子图表示成低维向量，用于图结构数据的分析。传统方式通常采用人工设计特征，显然这不够灵活也很费力。受启发于表示学习（representation learning）和词嵌入（word embedding）的成功，第一个图embedding方法DeepWalk被提出——在生成的随机游走（random walks）上应用SkipGram模型。类似的方法还有node2vec、LINE、TADW等，不过这些方法都有两个缺点：结点间的参数不共享，导致计算复杂度很高；这种直接的embedding方法缺乏泛化能力，不能处理动态图或生成新图。

基于CNN和graph embedding，提出了图神经网络GNN，用于从图结构中聚合信息。
why need GNN？

CNN和RNN不能合适地处理图的输入，因为他们无法按照图拓扑结构的顺序来处理节点——若用CNN、RNN来强行处理则需要遍历所有可能路径上的节点顺序。这是很浪费算力的。为解决该问题，GNN对每个节点分别进行传播计算，而不管输入顺序，这也就是说GNN的输出与图输入节点的顺序无关。
图中的一条边是用来表示两个节点间的依赖关系（dependency），在以往的神经网络中，这种依存信息通常被当作节点特征。但在GNN中，依存信息可以用来指导传播过程，比如用作更新节点信息的聚合权重。
推理（reasoning）是高级AI的一个重要研究领域，人脑推理过程基本也可以抽象为从日常经验中提取知识的图结构关系。以往的神经网络展示了通过学习distribution来生成图和文档的能力，而GNN能从非结构化数据中挖掘出graph，从而达到进一步的推理AI。

2. Models

2.1 Graph Neural Networks

这节先给出一些基本描述和符号定义。

传播步 + 输出步

在一个图中，每个节点node由它自身的特征feature和相关的节点定义。GNN的目的是学习一个状态嵌入（state embedding，能够包括邻居节点的信息，并且由hv可以产生输出ov （比如节点的标签）。

定义 f 是局部转移函数（local transition function），根据邻居节点信息来更新当前节点状态，并且该函数在所有节点间共享。
定义g是局部输出函数（local output function），用来描述节点输出是如何产生的。
则hv和ov可以表示成：

其中f里的四项分别是节点v的特征、与其相连的边的特征、邻居节点的隐状态和特征。

从全局角度来看，定义F是全局转移函数（global transition function），G是全局输出函数（global output function），即f和g的全局表示。
H是图中所有状态、O是所有输出、X是所有特征，XN是所有节点特征，则H和O可以表示成：

根据F是压缩映射（contraction map）的假设，H是(3)的不动点。又根据Banach不动点理论，GNN采用以下迭代方式来计算状态：

Ht是H的第t步迭代结果。

有了如上的定义，接下来的问题是如何学习f和g。与其他网络一样需要监督目标（比如每个节点的目标信息），可以定义loss函数：

其中p是监督节点的数量，同样，按照如下梯度下降策略来训练网络。

LImitations

尽管上述的GNN在很多实验结果上展现出建模结构数据的强大性能，但原版GNN有一些缺陷。

将隐状态迭代更新到不动点是很低效的。若放宽不动点假设，我们可以通过设计一个多层GNN（即固定的迭代次数）来得到节点及其邻居相对稳定的representation。
GNN在迭代过程中使用同样的参数，参照其他网络我们也可以在GNN的不同层中使用不同的参数，即一种层次化的特征抽取方法。更进一步，节点隐状态的更新也可以加入序列处理的方式，比如GRU、LSTM等。
边的信息在原版GNN中也没有被很好利用。比如知识图谱具有带类型的关系，而通过不同类型的边进行信息传播应该是不同的。
若我们关注于节点的representaiton，其实使用不动点是不太合适的。因为不动点方式学出来的representation分布会过于平滑、可能不具有节点区分性。
2.2 Variants of GNNs
本节介绍几种GNN的变种模型，这些变种模型能够提升GNN的表示能力。
2.2.1 Graph Types
原版GNN处理的图是有标签的节点+无向边组成，下面介绍几种其他类型的图。
有向图 即边是有方向的，由一个节点指向另一个节点，有向边能表示更多的信息。无向边可以看成两个有向边。
异构图 即包含多种类型的节点，最简单的方法是将类型转换成one-hot特征拼在原节点特征上。或者将图按照节点类型和距离分成一个个同构子图，以及最新提出的可以直接处理异构图的GNN网络。
带有边信息的图 即边具有类型或权重。处理方式一是将图变成二分图，边也视作节点，将原来的节点-有类型边-节点拆成节点-边-节点-边-节点的形式。二是对不同类型的边在传播时使用不同的权重矩阵。
动态图 即静态图结构和动态输入。
2.2.2 Propagation Types
GNN根据传播步的不同有若干种变体，它们使用不同的聚合器和更新器来更新节点隐状态。
如下表所示：

这里提到多跳（hop），即更深层的GNN并不一定能提高模型性能，这是因为在多层传播中噪声信息也被增大了，可以考虑残差连接的方式来改进，但在GCN中2层可能已经足够。
2.2.3 Training Method
Sampling
Receptive Field Control
Data Augmentation
Unsupervised Training

2.3 General Framework

除了GNN的不同变体外，还提出了几个通用的框架，旨在将不同的模型集成到一个单一的框架中。

2.3.1 Message Passing Neural Network (MPNN)

2.3.2 Non-local Neural Networks (NLNN)

2.3.3 Graph Networks

3 Application

图神经网络在很多问题上可以应用，包括监督的、半监督的、无监督的以及强化学习等。按应用领域主要划分为三个场景：

结构化场景，数据具有显式的关系结构，比如物理系统、分子结构、知识图谱。
非结构化场景，数据的结构关系并不显式，比如图像、文本等。
其他应用场景，比如生成模型和组合优化问题等。

3.1 Structural Scenarios

本节介绍在结构化数据场景下GNN的应用。

3.1.1 Physics

建模真实世界的物理系统，实体作为节点，关系作为边。

3.1.2 Chemistry and Biology

分子指纹 对分子（包括结构）构建一个表征向量。传统方法是通过手工设计的特征，这显然不够充分，通过GNN可以得到更好的表征。
蛋白质表面预测 同样也是基于结构来预测蛋白质表面，从而进一步分析。

3.1.3 Knowledge graph

GNN可以用来解决知识库中的库外知识实体（out-of-knowledge-base，OOKB）问题。OOKB实体被直接连接到已知实体上，它的embedding可以由已知实体来聚合。
GNN还可以用来解决跨语言知识图谱的对齐问题，模型将不同语言的实体在统一embedding空间下进行表示并根据embedding相似度来对齐。

3.2 Non-structural Scenarios

本节介绍非结构化数据场景的应用，一般有两种做法：① 从其他域中引入结构信息来提升性能，比如引入知识图谱来减轻图像任务中的zero-shot问题；② 推断或者假设关系结构并自定义图，比如某些文本任务。

3.2.1 Images

图像分类 在大数据的支持下，很多模型对于图像分类任务都能达到很好效果，但对于zero-shot和few-shot learning来说，模型的性能仍受限于数据量。于是在图像分类任务中，有些方法是通过引入知识图谱来指导zero-shot的识别分类。比如建立一个知识图谱，每个节点与一个实体类别对应，将节点的word embedding作为预测分类的输入。
除了知识图谱外，图像的相似度也可以帮助few-shot learning。比如基于相似度构建一个权重全连接的图像网络，在该图中进行信息传递来进行few-shot识别；还有可以选择一些相关实体来构建子图，用GNN抽取相关图像信息进行类别预测等等。
视觉推理 CV里面也需要根据空间和语义信息做一些推理任务，一个典型的推理任务是视觉问答（VQA），有做法是分别构建图像场景图和问题语法图，然后用GGNN来训练embedding预测答案，这其中也用到知识图谱。其他应用包括对象检测、交互检测和区域分类。
语义分割 这是面向图像理解的经典任务，该任务是对图像中的每个像素点假设一个标签，然后当作一个密度分类问题。由于图像中的区块并不总是网格化的、需要非局部信息（意思是某些分割可能需要关注其他远距离部分），因此传统CNN可能不适用，有些研究是使用Graph-LSTM等方法在空间域连接上建模长期依存关系。以及处理其他3D语义分割、3D点云分割等问题。

3.2.2 Texts

文本上使用GNN包括句子级别和词级别等。
文本分类 用GNN建模文本结构信息，按文档建图、句子建图以及词建图，提出了Text GCN、Sentence LSTM、Tree-LSTM等方法。
序列标注 将句子中的每个词当作一个节点，学习词的隐状态，从而预测标注（POS、NER任务）；还有构建带标签边的有向图来进行语义角色标注，提出Syntactic GCN根据语法依存树学习词的潜在表征。
机器翻译 NMT通常被看成seq2seq任务，大部分通过注意力机制来做，而Transformer其实就是一种全连接的图结构。所以同样可以通过引入语法语义信息来构建图，这里提到一种从语法依存图提出的Levi图，它将边当作额外的节点也具有embedding。
关系抽取
事件抽取
其他应用

GNN图神经网络

综述 paper 阅读：Graph Neural Networks: A Review of Methods and Applications