GNN —— 李沐老师论文跟读

标签：跟读可以信息我们李沐 GNN 节点向量

原博客地址：https://staging.distill.pub/2021/gnn-intro/?ref=https://githubhelp.com
由于该博客发表在distill上，具有许多交互性的图片，可以很好对原文作出解释，故本博客截取了较多原文中的图片。建议去原博客体验交互效果方便更好地理解。

引言

该博客发表在distill上，是一篇关于入门GNN的科研文。该文探讨并解释了现代图神经网络，作者将其分为四部分：

哪些数据经常被表述为图；
图与其他数据类型有什么不同；
构建一个GNN，研究模型的每个部分；
作者提供了一个playground，用户可以自己选择参数构建GNN模型。

正文

图的定义

图形表示为实体（节点）集合之间的关系（边）。
可以注意到，图的不同部位的属性同样非常重要，比如相邻节点，边的权重，节点数，最长路径等等。

对于图形的不同部位，可以使用不同长度，不同大小的向量去存储信息，图中我们可以看到三个部分的向量表示，小长方形的个数表示向量的长度，高度表示向量的大小，通过这种方式可以将各部分的属性储存起来。
如何把数据表示成图
- 图像转换为图：
  一般情况下，对于一个RGB(244 x 244 x 3)三通道的图片，我们会将其表示为一个有三个维度的tensor；从另一个角度来说，当我们把图片的每一个像素点当作一个节点，对于有邻接关系的点，连一条边，通过这种方式我们就可以把图像转换为图的形式了。下图为图像像素点，邻接矩阵及转换后的图。
- 文本转换为图：
  可以将输入文本的每一个词或者说token作为一个节点，由于文本的有序性，将每个词之间加上一条有向边从而将文本表示成图。
- 其他情况：
  作者还给出了除文本和图像之外的其他数据转换为图。将分子结构转换为图，令每个原子作为一个节点，连接每个相邻的原子作为边；将人的社交网络转换为图，作者以戏剧“Othello”中的人物关系为例，令不同人物作为节点，通过边与其他人物联系起来；引文网络也可以转换为图，当科学家发表论文时经常引用其他人的文章，可以将每篇论文看作一个节点，当论文之间有引用关系时，做一条表示引用的有向边。
图形结构化数据存在的问题
- 图形级任务
  
  我们的目标是预测整个图形的属性，例如，对于一个表示为图的分子，我们希望能够预测分子闻起来是什么样子，或者它是否与某种疾病有关，对于文本类任务，我们希望对文字做出情感分析。在该任务中我们输入一张图，输出的是该图的label（例如，图形中是否含有两个环）
- 节点级任务
  
  节点级的任务与预测图中的每个节点的身份有关。
  一个典型案例是Zach的空手道俱乐部，当原来较为单一的社交网络图，政治分裂为每个俱乐部成员宣布效忠两位俱乐部创始人之一时，每个节点的label只能是两种情况，“John A” 或者 “Mr.Hi” 。
  
  对于图像，节点级预测问题更加类似于图像分割，我们需要标注每个图像中每个像素的角色；对于文本，类似的任务是预测每个词的词性。
- 边级任务
  
  边级任务的一个例子是图像场景理解，通过分析图像中的人物行为，标注每条边的属性。
在机器学习中使用图的挑战

在机器学习应用中，我们需要考虑如何让图与神经网络兼容。图上有四种信息，分别是顶点的属性，边的属性，全局的属性和连接性，对于顶点，边和全局的属性我们可以使用向量的形式去存储。另外对于连接性的存储，由于邻接矩阵过大，稀疏矩阵存储又会导致空间效率极低，同时改变节点顺序也会改变邻接矩阵的形状，这会使得相同的矩阵有许多不同的表现形式，这意味着我需要训练我的神经网络使他在不同形式的邻接矩阵上得到相同的连接性信息，这无疑是相当复杂的。
为了解决连接性的存储问题，作者提出了可以使用邻接列表进行存储。在邻接列表中第i项存储着第i条边连接的两个顶点，当边的顺序发生变化或者节点顺序发生变化时，我只需要更新邻接列表中对应的变化即可。
Graph Neural Networks(GNN)

GNN是对图的所有属性的（节点，边，全局上下文）的可优化变换，它保留了图的对称性。GNN采用“图进图出”的架构，模型接收图作为输入将信息加载到属性中，并逐步转换这些嵌入，而不改变图的连通性。
- 最简单的GNN
  
  对于顶点状态向量、边状态向量还有全局的状态向量，我们分别构造一个输入大小等于输出大小的MLP，分别得到三个学习后的状态向量，这三个MLP构成了一个GNN层。与神经网络一样，我们可以将这些GNN层堆叠起来。
  由于各个属性向量被分别送入MLP得到输出，每个向量得到相应的更新而图的结构是不发生变化的，同时由于图的连通性没有发生变化，可以使用相同的邻接列表去描述输出图。
- Pooling
  
  首先思考如何在GNN上进行预测。对于一个简单的二分类问题，任务是对每个节点进行二元检测，并且图形已经包含节点信息，我们可以搭建一个输出为2的全连接层，然后再经过一个Softmax就可以得到结果，多分类问题我们只需要将2改为n即可。
  
  但是如果节点信息缺失，我们仍想对节点信息进行预测，就可以用到pooling（汇聚或者叫池化），以节点为例，将与目标节点相关的边向量和全局向量相加得到该节点向量。
  
  同样，对于只有顶点向量和全局向量，我们可以求得对应的边向量，全局向量同理。
  总的来说，我们可以得到一个最简单的GNN进行预测的流程图。我们需要注意到的是当图缺失信息的时候，我们需要加入对应的Pooling层去得到缺失值，同时GNN blocks也会删掉缺失部分对应的MLP。
  
  在这个最简单的GNN中，我们并没有在GNN内部使用图的连通性，每个节点，边，全局都是独立处理的，我们仅在池化信息时用到连通性。下面我们将学习如何进行改进。
- 信息传递
  - 只做节点更新
    不同于最简单的GNN直接对节点信息进行MLP，采用信息传递的方式，将节点与它相邻的节点向量通过聚合函数更新自身节点，然后再进入MLP。这个过程有些类似于卷积，不同的是，GNN的信息传递被没有权重的区分，节点与相邻节点之间聚合的权重是相同的，这样经过多层GNN的消息堆叠之后，节点最终可以整合来自整个图的信息；在三层以后，一个节点拥有距离它三步远的节点的信息。
  - 加入边更新
    我们可以将边连接的两个节点向量聚合到边向量更新边，然后将与该节点相连的边聚合到节点向量更新节点。当然我们可以交换这个过程，先把边的信息传递给顶点，再把顶点信息传递给边。在这个过程中，如果向量维度不一样的话，我们最多会进行两次投影。
    
    同样我们也可以进行交替更，同时把边的信息传递给节点，把节点的信息传递给边，达到一种你中有我，我中有你的效果。
  - 全局表示
    对于一个非常大的图来说，即使我们经过多次的信息传递，我们也很·难将两个相距很远的连联系起来，我们可以加入 master node 或者叫做 context vector，这是一个虚拟的点，它可以跟图上所有的点和所有的边相连，我们把它看做之前很少解释的全局向量U，这样当我们进行节点或边更新时，加入U，就可以保证所有的节点和边都能传递信息。
实验
作者在网页内部用JS写了一个可以自己调整超参数的GNN演示程序，我们可以自己调节GNN层数，Pooling方式，节点，边和全局的维度信息，并且有着不错的响应速度。