从数据结构到算法：图网络方法初探
论文《Graph Neural Networks: A Review of Methods and Applications》
木牛马论文阅读笔记https://www.cnblogs.com/ydcode/p/11050417.html
https://zhuanlan.zhihu.com/p/102994627?utm_source=wechat_session

文章目录

图神经网络（Graph Neural Networks，GNN）
- 1. GNN起源
- - 1.1 动机一：CNN的缺陷
  - 1.2 动机二：图嵌入的缺陷
- 2. 什么是GNN？
- - 简介
  - 与传统NN的区别（GNN优点）
- 3. GNN分类
- 4. GNN模型
- - 4.1 The framework of GNN
  - 4.2 How to learn the parameters of f and g
  - 4.3 GNN模型的局限性
- 5. GNN的变体
- - 5.1 图类型（Graph Type）
  - 5.2 传播类型（Propagation Type）
  - - 5.2.1 卷积(Convolution)
    - 5.2.2 注意力机制(Attention)
    - 5.2.3 门机制(Gate)
    - 5.2.4 跳跃连接(Skip connection)
    - 5.2.5 分层池化(Hierarchical Pooling)
  - 5.3 训练方法（Training Method）
- 6. 通用框架
- - 6.1 Message Passing Neural Networks
  - 6.2 Non-local Neural Networks
  - 6.3 Graph Networks
- 7. GNN应用
- - 7.1 结构化场景(Structural Scenarios)
  - 7.2 非结构化场景(Non-structural Scenarios)
  - 7.3 其他场景
- 8. 开放性问题

图神经网络（Graph Neural Networks，GNN）

1. GNN起源

1.1 动机一：CNN的缺陷

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

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

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

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

在这里插入图片描述

1.2 动机二：图嵌入的缺陷

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

在这里插入图片描述

图嵌入和GNN的区别👆

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

2. 什么是GNN？

简介

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

在这里插入图片描述

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

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

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

与传统NN的区别（GNN优点）

节点
- CNN和RNN等都需要节点的特征按照一定的顺序进行排列
- 但对于图结构，并没有天然的顺序。所以，GNN采用*在每个节点上分别传播(propagate)*的方式进行学习，由此忽略了节点的顺序，相当于GNN的输出会随着输入的不同而不同。
边（图结构的边表示节点之间的依存关系）
- 传统的神经网络不是显式地表达中这种依存关系，而是通过不同节点特征来间接地表达节点之间的关系，这些依赖信息只是作为节点的特征。
- GNN 可以通过图形结构进行传播，而不是将其作为节点特征的一部分，通过邻居节点的加权求和来更新节点的隐藏状态
推理
- 推理是高级人工智能的一个非常重要的研究课题，人脑中的推理过程几乎都是基于从日常经验中提取的图形。标准神经网络已经显示出通过学习数据分布来生成合成图像和文档的能力，同时它们仍然无法从大型实验数据中学习推理图。然而，GNN 探索从场景图片和故事文档等非结构性数据生成图形，这可以成为进一步高级 AI 的强大神经模型。

3. GNN分类

图卷积网络(Graph convolutional networks)和图注意力网络(graph attention networks)，因为涉及到传播步骤(propagation step)。
图的空域网络(spatial-temporal networks)，因为该模型通常用在动态图(dynamic graph)上。
图的自编码(auto-encoder)，因为该模型通常使用无监督学习(unsupervised)的方式。
图生成网络(generative networks)，因为是生成式网络。

4. GNN模型

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

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

在这里插入图片描述

4.1 The framework of GNN

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

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

假设 $f(\cdot)$ 是带有参数的函数，叫做局部转移函数(local transition function)，这个函数在所有节点中共享，并根据邻居节点的输入来更新节点状态
假设 $g(\cdot)$ 为局部输出函数(local output function)，这个函数用于描述输出的产生方式。

$h_v=f(x_v,x_{co[v]},h_{ne[v]},x_{ne[v]})\tag{1}$

$\large o_v=g(h_v,x_v)\tag{2}$

$x_v$ 表示节点v的特征向量， $x_{co[v]}$ 表示与节点v关联的边的特征向量， $h_{ne[v]}$ 表示节点v的邻居节点的状态向量， $x_{ne[v]}$ 表示节点v的邻居节点特征向量。

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

$O=G(H,X_N)\tag{4}$

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

在这里插入图片描述

4.2 How to learn the parameters of f and g

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

状态 $h_v^t$ 按照方公式 $(1)$ 迭代更新个 $T$ 轮次，直到到达接近公式（3）的定点解的时刻 $T$ ，这时得到的 $H$ 会接近不动点的解 $H^T\approx H$ 。
权重 $W$ 的梯度从loss计算得到。
权重 $W$ 根据上一步中计算的梯度更新。

4.3 GNN模型的局限性

对不动点使用迭代的方法来更新节点的隐藏状态，效率并不高。
原始的GNN 在迭代中使用相同的参数，而其他比较著名的模型在不同的网络层采用不同的参数来进行分层特征提取，使得模型能够学习到更加深的特征表达，而且，节点隐藏层的更新是顺序流程，可以利用 RNN 内核，如 GRU 和 LSTM，来进一步优化。
一些边(edges)上可能会存在某些信息特征不能被有效地考虑进去。（例如，知识图中的边具有关系类型，并且通过不同边的消息传播应根据其类型而不同）。此外，如何学习边的隐藏状态也是一个重要问题。
如果我们需要学习节点的向量表示而不是图的表示，则不适合使用固定点，因为固定点中的表示分布将在值上非常平滑并且用于区分每个节点的信息量较少。

5. GNN的变体

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

5.1 图类型（Graph Type）

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

有向图(Directed Graphs)：即图中的边是存在方向的。有向边可以带来比无向边更多的信息。
异构图(Heterogeneous Graphs)：即图中存在多种类型的节点。处理异构图的最简单方法是将每个节点的类型转换为与原始特征连接的 One-hot 特征向量。(其中，论文《Deep Collective Classification in Heterogeneous Information Networks》提出将元路径(meta path)概念用在异质图的信息传播上，根据节点类型和距离来对局部范围内节点进行分组，对于每一组，Graph Inception将它作为异构图的一个子图，然后在子图内进行传播，并将不同异构图得到的结果进行连接得到综合的节点表示。)
带有边信息的图(Graphs with Edge Information)：即图中的每条边也存在权重或类型等信息。这种类型的图有两种解决办法：
- 一种是将图形转化为二部图(bipartite graph)，将原始的边转化为一个节点以及两条新的边（原始边也作为节点，两条新的边分别连接原始边的两端节点）。(论文G2S)
- 第二种方法是在不同种类的边上，使用不同的权重矩阵来进行传播，就是说每一种边类型都关联一个权重矩阵，显然，对于边类型很多时参数量非常大。(论文R-GCN减少参数)
动态图(Dynamic Graphs)：动态图类型有静态的图结构，并且能够处理动态的输入信号。
- DCRNN和STGCN首先使用GNN获空间结构信息，然后将outputs馈入到一个序列模型（如sequence-to-sequence或者CNN）
- 与此相反的是，Structural-RNN和ST-GCN同时获取时间信息和空间信息

5.2 传播类型（Propagation Type）

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

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

在这里插入图片描述

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

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

5.2.1 卷积(Convolution)

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

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

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

(详细了解)

5.2.2 注意力机制(Attention)

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

(详细了解)

5.2.3 门机制(Gate)

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

(详细了解)

5.2.4 跳跃连接(Skip connection)

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

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

(详细了解)

5.2.5 分层池化(Hierarchical Pooling)

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

(详细了解)

5.3 训练方法（Training Method）

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

采样(Sampling)：GraphSAGE将full graph Laplacian替换为可学习的聚合函数(aggregationfunction)。在学习到聚合函数和传播函数后，GraphSAGE能够对未⻅过的节点产生embedding。另外，GraphSAGE使用邻居节点采样(neighbor sampling)的方法来缓和感受野扩展的扩展速度。
感受野控制(Receptive Field Control)
数据增强(Data Augmentation)：论文考虑到GCN需要许多额外的标签数据集用于验证，以及卷积核局部化问题，为了解决这些问题，这篇论文提出Co-Training GCN和Self-Training GCN来扩充训练数据集。
无监督训练(Unsupervised Training)

6. 通用框架

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

6.1 Message Passing Neural Networks

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

6.2 Non-local Neural Networks

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

6.3 Graph Networks

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

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

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

定向：单向边缘
属性：可以编码为矢量、集合甚至其他图形的属性。
属性化：边和顶点具有与其关联的属性。
全局属性：图形级属性。
多图：顶点之间可以有多个边，包括自边。图2显示了与我们可能感兴趣的建模实际数据相对应的各种不同类型的图，包括物理系统、分子、图像和文本。

7. GNN应用

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

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

应用的总结见下表👇（可以看出，还是非结构化场景场景居多）
在这里插入图片描述

7.1 结构化场景(Structural Scenarios)

物理系统应用(Physics)

GNN可以用于对现实世界中的物理系统建模，将物体表示为节点，将物体之间的关系表示为边，由此可以使用GNN模型对目标、关系进行推理。有如下一些论文研究相关内容：
- Interaction Networks”：该模型对各种物理系统进行预测和推理。模型输入objects和relations，然后对它们的interaction进行推理，并预测出新的系统状态。
- Visual Interaction Networks：该模型实现像素级的预测。
化学和生物学应用(Chemistry and Biology)

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

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

7.2 非结构化场景(Non-structural Scenarios)

图像任务(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的任务。
- 首先就是文本分类任务，GNN将一个document或者sentence表示为一个以字(或词)为节点的图结构，然后使用Text GCN来学习词汇或者文本的embedding向量，用于下游任务。
- 其次就是序列标注任务，对于图中的每一个节点都有一个隐藏状态，因此，可以使用这个隐藏状态来对每一个节点进行标注。
- GNN还可以用于机器翻译任务，原始的机器翻译是sequence-to-sequence的任务，但是使用GNN可以将语法和语义信息编码进翻译模型中。
- GNN用在关系抽取任务中，就是在文本中抽取出不同实体的语义关系，有一些系统将这个任务看作是两个单独的任务：命名实体识别和关系抽取。
- GNN用于事件抽取任务，就是从文本中提取出事件关键的信息，有论文通过dependency tree来实现event detection。GNN还被用于其他应用，比如文本生成任务，关系推理任务等等。

7.3 其他场景

生成模型(Generative Models)

生成模型对于社会关系建模、新型化学结构发现以及构建知识图谱也有重要作用，有如下相关的研究论文：
- NetGAN：模型使用随机漫步原理来产生图，该模型将graph generation问题转化为walkgeneration问题，它使用来自于特定图结构的random walks作为输入，并使用GAN的结构来训练一个产生式模型。
- MolGAN：该模型一次性预测离散的图结构，并采用permutation-invariant discriminator来解决node variant问题。
组合优化(Combinatorial Optimization )

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

8. 开放性问题

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矩阵也是不可行的。此外，我们需要指出缩放确定算法是否能够应用于实际应用。