[人工智能]图神经网络简述(A Brief Description of Graph Neural Network)

写在前面
最近使用图神经网络写了一些东西，觉得图神经网络还是挺有意思的，所以撰写一下学习记录，免得后面自己忘了。主要参考的内容放在最后了。由于本人小菜鸡一个，所以本文中尽量避免公式以及数学相关的内容

背景

自从AlexNet掀起深度学习浪潮之后，卷积神经网络(Convolution Neural Network, CNN)、深度神经网络(Deep Neural Network, DNN)、循环神经网络(Recurrent Neural Network, RNN)等网络结构均在计算机视觉、自然语言处理等领域大放异彩。这些模型大多是端到端的模型，非常方便科研技术人员使用。当然，深度学习的高速发展也离不开GPU算力的不断提升。
但是，以上模型只能使用在 欧氏空间 中的数据，但是实际应用场景中很多方面都不是欧氏空间中的数据。举个例子，比如在电子商务中，一个基于图（Graph）的学习系统能够利用用户和产品之间的交互来做出非常准确的推荐，但图的 复杂性 使得现有的深度学习算法在处理时面临着巨大的挑战。这是因为图是不规则的，每个图都有一个 大小可变 的无序节点，图中的每个节点都有 不同数量 的相邻节点，导致一些重要的操作（例如卷积）在图像（Image）上很容易计算，但不再适合直接用于图。此外，现有深度学习算法的一个核心假设是数据样本之间 相互独立 。然而，对于图来说，情况并非如此，图中的每个数据样本（节点）都会有边与图中其他实数据样本（节点）相关，这些信息可用于捕获实例之间的相互依赖关系。
因此，需要在深度学习领域建立一种新的模型，使得模型可以尽可能多的学习到“图”的特征。当前，图神经网络主要应用于抗菌发现、物理模拟、假新闻检测、交通预测和推荐系统等领域。

简介

图神经网络(Graph Neural Networks, GNNs)是深度学习领域一种模型，目的是为了尽可能多的提取“图”(graph)中潜在的表征信息。与传统的数据结构不太一样的地方是，图 没有一个固定的结构 ，不像是图像，可以表示成一个矩阵（张量），或者是语句（嵌入向量）等。就像背景部分介绍的例子，我们不知道一个用户对多少商品感兴趣，也不知道一个商品被多少用户接受。这时候，利用“图”进行表示就是再合适不过的了。然后将图转化为机器可以处理的结构，给GNN，就可以得到图潜在的表征信息。

图 Graph

构成图的要素

学过离散数学的读者应该对图的概念比较熟悉。图(graph)是由 顶点(Vertex, V) 和 边(Edge, E) 组成的，但是对于GNN，我们还需要一个 全局特征(Global, U) 表示整个图的某一种特征或者属性。如下图：

图的原始特征表示(Embedding)

对于每一个要素，都可以使用一个向量保存当前要素（某一个点，某一条边或全局属性）的属性特征。如下图所示：

上图中，左侧表示一个图的结构，右侧表示图中高亮元素的特征向量(Embedding)，使用了类似于柱状图的方式表示不同维度上特征的大小，不同类型要素的特征向量维度可以不同。其中，边既可以是有向边也可以是无向边。

图结构的表示

数据结构中，有向图和无向图可以使用 邻接矩阵(adjacency matrix) 表示。
邻接矩阵是使用矩阵表示图的一种方法。首先将图中所有的顶点标上序号（这个序号是自己定义的），假设图中由$N$个顶点，那么邻接矩阵就是一个$N\times N$的二维矩阵，矩阵中的元素$a_{ij}$是一个布尔值，表示顶点$i$和$j$是否有边直接相连，如果是无向图，那么邻接矩阵是一个对称矩阵，否则不是对称矩阵。
实际上常见的图像(image)和句子也可以使用图进行表示，进而转变为邻接矩阵。
下图是一个社交网络的邻接矩阵表示：

上图中，中间是邻接矩阵表示，蓝色表示对应两个顶点之间有边直接相连，右侧图像就是图的直观表示。

图神经网络

前向传播 forward

根据上面的表述，一个图$G=?V,E,U?$中，三要素直接的特征属性可以使用向量表示，那么我们可以对三类元素的所有特征分别使用一种映射，将其映射到下一层，如下图所示：

在一个GNN中，第$N$层向第$N+1$层传播的时候，所有边特征、所有顶点特征以及全局特征都会分别经过一个映射$f$映射到下一层网络中的对应位置。这个映射$f$可以是单独的多层感知机，也可以是其他的可微分模型。
然后可以将多个类似于这样的层堆到一起，形成了一个简单的GNN。

对要素未知特征的预测——汇聚(Pooling)

考虑最简单的二分类问题，如果需要根据顶点特征预测顶点类别，那么根据上面我们知道这就是一个类似于简单的多层感知机的二分类模型。但是如果我们只知道边的特征，而还想对顶点进行预测，传统方法肯定是不行了。因此我们需要进行如下两个步骤：

1. 对于每个要汇聚的项目， 收集(gather) 它们的每个嵌入，并将它们连接成一个矩阵；
2. 然后，收集的嵌入被 汇总(aggregated) ，通常是通过一个总和操作。
   如下图所示：
   

上图中对粗圆圈进行了特征汇聚。也就是三个要素中，一个不知道可以用其余两个对其进行汇聚得到其特征。对于其他的情况也是类似于上面的操作，这样，我们就可以根据图给出的信息对任意的要素进行预测。

在图的各部分之间传递信息

在一个图中，不同顶点之间的连接关系也可能包含重要的信息，相邻的顶点之间也可能具有某种潜在关系。根据上面汇聚的思路，可以对一个顶点的相邻顶点进行汇聚，得到该顶点的邻居特征，这些特征应该在某方面具有更强相似性（或者说是影响）。
进行顶点的汇聚一般可以使用加和，也可以对邻居顶点进行加权等。如下图所示：

上图中，以左上角的顶点为例，进行了一层的正向传播。也有做法将邻居顶点的特征同时（或分别）乘上一个小于1的常数（可学习参数），非常灵活。这也有些类似于标准卷积操作。

利用汇聚得到未知要素特征进行训练

训练数据集中可能就只包含三要素中的两个，所以在训练的时候，可以在每一层先进行汇聚，然后进行正向传播、反向传播。类似于如下过程：

上图中，首先将顶点的信息汇聚给了未知的边，然后将边的信息汇聚到了顶点。同时，我们也可以加入全局特征，如下图：

这样，所有的图属性都有学习过的表征，所以我们可以在汇聚过程中通过调节我们感兴趣的属性与其他属性的信息来利用它们。例如，对于一个顶点，我们可以考虑来自邻居顶点、边和全局特征。为了对所有这些可能的信息来源的新节点嵌入进行调节，我们可以简单地将它们连接(concatenate)起来。此外，我们还可以通过线性图将它们映射到同一空间，并将它们加在一起，或者应用一个特征调制层，这可以被认为是一种feature-wise的注意力机制。

写在后面

本文主要参考的是distill的博客，就是参考资料的第一个，想要细致了解的可以点进去看看，这个博客的一大特点也在于有大量可交互的图。读了这个博客感觉还是比较不错的，没有像其他博客一样列公式讲定义，最后看的一头雾水，反而这样子的更加可以给我一个直观上的感受，知道了GNN这东西是干啥的，所以觉得还是有必要记录一下的。

参考资料

• A Gentle Introduction to Graph Neural Networks
• 图神经网络（Graph Neural Networks，GNN）综述