图神经网络（GNN）入门学习笔记（直观且简单）

本篇文章参考发表于Distill上的图神经网络入门博客： A Gentle Introduction to Graph Neural Networks。同时，所有的图片也都来源于该博客。本文主要是记录本人自己的学习体会与心得，帮助其他初学者能够更快入门图神经网络而无需看冗长的英文原文。

图的定义和表示

图可以用三个符号进行表示：

• 顶点集（V）：图中的所有顶点构成一个顶点集；
• 边集（E）：图中的所有边构成一个边集；
• 图整体（U）：完整考虑一个图的所有顶点和边以及对应的拓扑结构，图的整体被称为U。

在计算机中，无论是顶点集、边集或者图整体都可以使用向量进行表示。顶点向量中的各个值表示顶点的属性；边向量中的各个值表示边的属性；图向量同理。

另外，一张图也可以使用离散数学中的邻接矩阵进行表示，具体内容可以参见离散数学课程教材。

很多现实中的问题，都可以把问题中的实体转化为图的顶点，把实体之间的关系转换为图中的边，从而使用图来表示该现实问题。

可以使用图数据结构的问题

可以使用图数据结构的问题可以分为三个类型，分别是图层面的问题、顶点层面的问题和边层面的问题。

• 图层面的问题：找出含有两个环的图；
  

• 顶点层面的问题：将图中的所有顶点划分为两类；
  

• 边层面的问题：给图中的所有边判定类型。
  

将图结构用于机器学习的挑战

将图结构应用于机器学习领域的最大挑战是如何表示图结构，使得其能够与搭建的神经网络兼容，并被计算机计算和处理。

图结构中包含有四类信息：顶点集信息、边集信息、图整体信息和连接性信息。前面三种类型的信息都可以通过向量或矩阵的方式进行表示，但是连接性信息的表示会更加麻烦。

表示连接性的最直观方法就是使用邻接矩阵，但是很多情况下邻接矩阵都是稀疏的，因此会无意义地占用非常大的存储空间。即使通过稀疏化的方式表示邻接矩阵也会有计算机难以处理的问题。

为此，可以通过邻接表的形式表示邻接矩阵。邻接表的大小与边的数量成正比，其中的每一个元素记录了哪两个顶点之间存在一条边。

下面将正式开始介绍图神经网络。

最基本的图神经网络概述

图神经网络本质上就是一个特用于图模型的神经网络。

图神经网络的基本思路如下：由于上面我们已经提到，图中除了连通性信息外，其他的三个属性（顶点集、边集和整体）都可以用能够代入神经网络进行计算的向量来进行表示，因此，我们对于三类属性，分别构造一个神经网络。

也就是说，一个神经网络以顶点集向量作为输入，一个神经网络以边集向量作为输入，另一个神经网络以整体向量作为输入。这样的三个网络组合在一起，就构成了图神经网络的一个层。多个图神经网络层叠加在一起，就构成了完整的图神经网络。

需要注意的有两点：首先，是每一个图神经网络层中的神经网络的输出形状都与输入形状相同，也就是说，输入的向量长度和输出的向量长度相同；其次，对于图的连通性，图神经网络不会对其进行修改，也就是说，一张图经过了图神经网络，其连通性不会发生改变：原来相连的两个顶点仍然相互连接。

面对分类任务，只需要在最后一层输出加上全连接层和softmax分类即可。基本原理也如下图所示：

汇聚操作

有时在实际问题中会遇到一些特殊的情况，使得无法同时获得顶点集的向量、边集的向量和整体的向量，这个时候，就可以使用汇聚的思想来补充生成当前没有的向量。下面将以缺失顶点集为例进行说明，其他情况可以类比推理。

当顶点集缺失时，每一个顶点连接了多条边，因此可以把每个顶点连接的多条边的向量进行叠加，最后再加上整体的向量，即可替代该顶点的向量。

基于信息传递的改进图神经网络

上面所提到的基本图神经网络存在一个问题，那就是没有利用图的连通性，从而损失了图中的一部分信息。

为了能够利用连通性，下面将给出一种基于信息传递的改进的图神经网络。

以顶点集为例。在改进的网络中，当一个顶点的向量需要准备待入顶点对应的神经网络进行更新时，并不是直接将该点的结果代入，而是将该顶点以及与该顶点直接相连的顶点的向量相加后进行代入，从而利用上之前未被利用的连通性信息。

边集的信息传递改进图神经网络原理类似。

全局向量信息的利用

之前的介绍中，我们只是说了全局向量是需要计算的以及其计算方法，但是并没有介绍其使用过程，下面将进行介绍。

全局向量可以抽象为一个虚拟的顶点（被称为master node），该顶点与图中的所有顶点相连，同时与图中的所有边相连（点如何与边相连？这是因为这个顶点是抽象的，也可以把这个虚拟顶点想象为一个又是顶点又是边的东西）。

基于上面介绍的信息传递的原理，每次该虚拟顶点在经过全局神经网络更新之前，需要叠加图中当前状态其他所有顶点和边的向量信息。通过这样的方式，就成功利用了图的全局信息。