图神经网络

图神经网络简介

神经网络与图这种数据结构相结合（结构和属性），构成了图神经网络。
如何构建一个图神经网络？图神经网络的背后思想是什么？

图神经网络（GNN）已经被用在各种领域，如医学、物理、新闻检测、流量预测和推荐系统
• 什么数据最适合用图结构来表达
• 图结构与其他数据结构之间的区别，使用图的时候，我们需要注意一些什么
• 从头到尾构建一个GNN，并说明每一个细节
• 提供一个GNN交互模块，基于真实词语任务和数据集去领悟GNN模型中每一个部分对整个模型是如何影响的

什么数据可以用图结构来表示

---

我们当然可以想到用图来存储我们的社交网络数据，比较facebook就是这么做的。我们也可以用图结构来构建我们的知识图谱，这都很符合我们的直觉。但是，图像和文本也可以用图结构来进行建模。有点反直觉不是？但我们确实可以通过对图像和文本这两种数据用图结构来进行大脑中的构建，理清它们内在的对称性和结构性，建立一种关键的直觉——非网格状的数据与图结构的联系。

图像与图结构
在CV领域，我们通常都认为一张图像是通过（长，宽，通道）三个维度去构建的，于是在图像识别领域，我们自然地会将图像用一个三维矩阵去存储，例如一个（32×32×3）的彩色图像，于是我们就构建了“图像——矩阵”的映射。然而，我们无法通过这种方式去构建每个像素点与其邻近像素点之间的关系。如果要表示每个像素点与其邻近节点之间的关系，自然而然地，可以想到邻接矩阵这种存储结构。

文本与图结构
通过对字符、单词、token构建索引（节点），然后对索引进行序列化（关系）来对文本进行数字化。最后，我们将地道一个简单地有向图，节点即为索引，关系即为索引节点之间的顺序。

还有一些数据，天生就只能用图来进行表示。例如分子结构、社会网络、引文网络、机器学习中的数据流图。

什么问题的图结构化的问题？

---

针对图的预测任务可以分为三个层级：图、节点、关系/边
• 图：对一整个图去预测图的单一属性（图的特征？），目标是预测图的属性/特征，分类任务，每一个输入的图样本对应哪一个label
• 节点：预测每个节点的属性，预测节点在途中的身份或角色。一个很经典的案例就是Zach空手道俱乐部。预测小范围社交网络中的两个派系问题。节点预测问题类似与图像分割任务与词性识别任务。
• 关系：预测关系的属性或预测是否存在关系。具体示例如图像场景理解，除了识别图像中的对象以外，还能预测它们之间的关系。可以首先构建完全图，然后基于实体之间的预测值修剪边，得到稀疏图

GNN中的难点是什么？

---

如何使用神经网络来解决这些图任务呢？
首先应该考虑如何表示与神经网络兼容的图，机器学习模型通常采用矩阵或网格状的数组作为输入。而一张图里面蕴含的信息有四种：节点、边、全局上下文信息和连通性。如何将这些信息编码成机器学习模型所需要的矩阵或网格数组，显然这不是一个很符合我们直觉的任务。对于前面的三种信息（节点、边、全局）的编码可能相对简单一些，对于节点，我们可以通过为节点建立索引，然后存储在矩阵里面。
然而，要对图的连通性进行表示显然不是一件容易的事情。你可能会想到用邻接矩阵去存储，毫无疑问，这是可以的。但是假设图中的结点数很多，高达数百万，而节点之间的边数很少，可能只有几十条，那么这会导致我们建立的邻接矩阵变得非常稀疏，造成空间资源的浪费。另外就是在机器学习中，用稀疏矩阵作为输入也会产生很多问题。
另一个问题是，一张图的连同属性可以用很多邻接矩阵去编码。但是把这么多的表示同一连同性的矩阵feed给神经网络，没有谁能保证我们的神经网络会输出同样的结果。（换句话说，这一堆表示同一张图同一连同性的矩阵，不是包络不变的）

用邻接列表来对图进行编码，能够解决上面提到的各种问题。这种方式对图进行编码，可以分为三个list，第一个list为节点表，第二个list为边表，第三个list为我们说的邻接列表（Adjacency List）。邻接列表中存储节点对，边表中与邻接列表中对应的索引位置，就是节点对对应的边的权重信息，邻接列表中的节点对，是基于节点表中构建的索引来进行表示的。

图神经网络

---

既然图的描述是以排列不变的矩阵格式来表示，我们可以试着使用图神经网络来解决图预测任务。GNN是对图的各种属性（节点、边、全局上下文）进行的可优化变换，也就是说这回保留图的对称性（置换不变性）。以下使用“消息传递神经网络”框架构建GNN（Gilmer等人）。图网络架构设计沿用Battaglia等人的工作。本文的GNN采用“图进图出”架构，这可以使模型接受图作为输入（将信息加载道其节点、边和全局上下文中，并逐步转换这些嵌入而不会改变输入图形的连通性）

一个简单的GNN

通过对图中的每一个组成部分（节点、边、全局）使用单独的多层感知机（MLP）——GNN layer。最终每一个部分都会返回一个学习后的embedding（节点、边、全局）。
因为当前的GNN没有对图的连通性进行学习更新，所以这种情况下我们可以用同样的邻接列表和同样数目的特征向量来编码我们的图。唯一改变的就是每一个节点、边、全局上下文的表示，因为这就是我们当前的GNN所做的事情。

通过Pooling Information来做GNN预测

在当前简单的GNN中，如何在最后一层做预测任务呢？假设当前的任务是一个简单的二分类任务，最后一层中我们显然得到了每个节点、边、全局上下文的updated embedding，我们可以用一个线性分类器来做二分类任务。当然，如果是N分类任务，那么在最后建立一个输出维度为N的全连接层，最后链接softmax就可以进行N分类。

但是事实往往并没有这么简单。例如，我们的图里面没有顶点的信息，任务仍然要求我们对顶点进行预测。如此一来，我们需要找到一个方法，从边上面学习信息，进而用来指导节点的预测。这一步叫做Pooling，分为两个步骤：
• 对于要进行pool的item，手机它们每一个embedding并将它们连接成一个矩阵
• 然后通过sum操作，对收集到的embedding进行aggregate

可以通过pooling函数+分类器C预测节点、边、甚至是全局图信息

pooling作为构建复杂GNN模型的基石，当一个新的图属性过来，我们要做的只是去定义如何将信息从一个属性传递到另一个属性。这一层的最简单的GNN设计中，我们没有在GNN内部使用图的连通性。可以看到我们对每个节点、边以及全局上下文都是独立处理的，只在为预测而进行pooling的时候使用了一点连通性。

在图中的不同结构中传递信息

我们也当然可以在GNN层内使用pooling来进行更复杂的预测，对图的连通属性也构建出embedding。这都可以通过消息传递（message passing）来左到这一点，消息传递的设想是让相邻节点或相邻边交换信息并影响彼此的embedding。
消息传递分为以下三个步骤：
• 对于图中的每一个节点，收集所有相邻节点的嵌入（或消息）。
• 通过aggregate函数对汇聚过来的消息进行汇聚
• 所以被池化的消息均通过update函数进行更新
消息的传递可以发生在节点或边之间，就好像池化可以应用于节点或边一样。

这有点像卷积，只不过这里的aggregate中的核函数不会去考虑权重。
通过将传递给GNN层的消息堆叠在一起，节点最终可以合并整个图形中的信息，在三层堆叠之后，一个节点可以拥有三跳的节点信息。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6peItOpv-1638861627437)(https://distill.pub/2021/gnn-intro/arch_gcn.40871750.png)]

学习边的表示

如何通过顶点和全局去预测边呢？毕竟我们的数据集中也不是常常都会包含全部信息。
前面使用了pooling，在模型的最终预测步骤中，将信息从边路由到节点中，达到用边和全局信息预测节点的结果。类似的，我们当然可以通过合并边的消息，然后使用update函数对其进行转换并存储。但是，节点消息的大小或形状跟边的消息的大小或形状未必相同，若要aggregate它们，则需要构建边空间道节点空间的映射。以上都是在最后一层pooling中的操作，或者，我们可以尝试在update函数之前就将它们（边和节点）连接在一起。
• 将节点的信息传递给边，得到接受节点信息的边，再将边的信息传递到节点。
• 将边的信息传递给节点，得到接受边的信息的节点，再将节点的信息传递给边

全局表示

为什么要全局信息？因为在我们描述的网络中，彼此相距很远的节点可能永远无法有效地相互传递信息。对于一个节点，如果我们有K层，那么信息将至多传递K步。对于预测任务依赖相距很远的节点或节点集合的情况下，这就是一个问题。有一种解决方案是让所有节点都能够相互传递信息，那开销必然会变得很大。
对于这个问题还有一个解决方案是使用图（U），或者说Master节点，一个连接全局的虚拟节点，它是一个抽象的节点，连接着图中的任一顶点和边，以构建消息传递的桥梁。

最后进行一个总结，关于图中所有属性的学习，我们可以调整相邻属性的信息并在池化中进行属性预测。例如，对于一个节点预测，我们可以考虑它相邻节点、相邻边甚至是全局的信息。可以将它们简单地相加或通过线性映射构建到同一空间再相加或应用特征调制层，这有点像注意力机制（考虑预测节点的所有相关属性）

图神经网络的约束——图的对称性，不改变图的结构