A Gentle Introduction to Graph Neural Networks

在上图中，每一层都是一层网络，每一层的节点都受到下一层中自身节点和邻居节点的影响。如果网络比较深，是可以处理到一幅图中较大范围的节点。

前言

图神经网络在应用上还只是起步阶段，应用领域有药物发现、物理模拟、虚假新闻检测、车流量预测、推荐系统等。这篇文章是探索和解释现代图神经网络，第一部分是什么样的数据能表示成一张图，第二部分是图和别的数据有什么不同，第三部分是构建GNN的模块，第四部分是搭建一个GNN的playground

图是一个序列。图越深，上层的节点链接的下次节点越多

什么是图

把节点信息、边信息和全局信息做embedding，通俗地说就是把这些信息存储为向量的形式。所以图神经的核心就是，怎么样把我们想要的信息表示成向量，以及向量是否能通过数据学习到。

在图上使用机器学习的挑战是什么？
需要的是节点、边、全局信息、连接性四种类型的信息来做预测。
连接性是用邻接矩阵来存储，如果图非常大，比如Wikipedia，则存储不下来。由于是邻接矩阵很稀疏，所以用稀疏矩阵来存储会更好，而稀疏矩阵在GPU上训练一直是个技术难题。
邻接矩阵任意交换行列，会导致邻接矩阵改变，他们其实节点关系不变，文章给出了下面这个例子（动态图）表示不同样子的邻接矩阵都形成了连接性相同的图，而他们都是异构的。

那么想要存储高效且不受排序的影响应该如何存储呢？

上图中的节点、边和全局信息都可以用向量表示，而不一定只是标量。这个adjacency list能够用节点id把边的连接关系表示出来。

图神经网络

介绍完图的背景后，现在开始介绍图神经网络（GNNs）。
什么是GNNs？是对图上所有属性进行可以优化的变换，变换能保持图的对称信息（节点重新排序后，结果不变）。message passing neural network是一种GNNs的框架，当然GNN是可以用别的方式构建。
GNNs是“graph-in, graph-out”，他会对节点、边的信息进行变换，但是图连接性是不变的。
首先，对节点向量、边向量、全局向量分别构建一个MLP（多层感知机），MLP的输入输出的大小相同。

三个MLP组成GNN的一层，一个图经过MLP后仍然是一个图。对于顶点、边、全局向量 分别 找到对应的MLP，作为其更新函数（update function）。可以看到，输出后图的属性变化了，但是图的结构没有改变，符合我们的需求。MLP对每个向量独自作用，不会影响的连接性。

堆叠了多层上述的模型后得到了GNN，现在来到最后一层，对节点进行预测。

上图可以看到，经过GNN的最后一层，得到的也是一个图，然后在图后面接一个全连接层（分类的话神经元数量则是类别数，再套一个softmax，回归的话神经元数量则是1），所有节点共享一个全连接层。
考虑另一种情况，如果说某个节点是没有自己的属性（向量）的，应该怎么做？这里介绍到pooling

做法就是把节点相连的边向量拿出来，全局向量拿出来，然后将这些向量相加求和，最后经过一个节点共享的输出层得到节点预测结果。

假如没有边向量而只有节点的向量，则汇聚相连的节点的向量，如下图所示：

那如果没有全局向量，只有节点向量呢？就把全部的节点向量汇聚起来，经过最后的输出层得到全局的输出。

所以，不管缺哪类属性，我们都可以通过汇聚这个操作，得到最终的输出值。下图则是GNN流程的描述。

如上模型的局限性是很明显的，并没有用到图的结构，仅仅是点、边向量分别做MLP的过程。

解决方法：信息传递

在更新某个节点的向量时，会将自己的向量和邻居节点的向量进行聚合（相加）操作，然后再传入MLP更新节点的向量。作者说这个过程和标准卷积相似，但其实不完全是。下图则是GCN的架构涉及，通过聚集邻居节点来更新节点的表达。

学习边的表示

下图是信息传递层的原理，从节点到边、边到节点的传递。

边和顶点之间的信息传递，用于预测位置的属性。

下面是两种不同的聚集方式：先从节点到边/先从边到节点。现在对于哪种做法更好还没有定论，作者提出可以交替进行（下图种的weave layer），只是向量会更宽一些。

添加全局表示

如果说图很大，或者连接不够紧密，那聚合就需要走很远很远的路。这里介绍了一种解决方案：master node or context vector，这是一个虚拟的、抽象的 点，与所有的节点和边相连。

作者说这个其实可以认为是featurize-wise attention mechanism（特征级的注意力机制），因为将相近的节点聚集了过来。现在我们就知道了基于消息传递的图神经网络是怎么样工作的。