图神经网络系列之序章

一、为什么需要图神经网络？

随着机器学习、深度学习的发展，语音、图像、自然语言处理逐渐取得了很大的突破，然而语音、图像、文本都是很简单的序列或者网格数据，是很结构化的数据，深度学习很善于处理该种类型的数据（图1）。

然而现实世界中并不是所有的事物都可以表示成一个序列或者一个网格，例如社交网络、知识图谱、复杂的文件系统等（图2），也就是说很多事物都是非结构化的。
相比于简单的文本和图像，这种网络类型的非结构化的数据非常复杂，处理它的难点包括：

1. 图的大小是任意的，图的拓扑结构复杂，没有像图像一样的空间局部性
2. 图没有固定的节点顺序，或者说没有一个参考节点
3. 图经常是动态图，而且包含多模态的特征

那么对于这类数据我们该如何建模呢？能否将深度学习进行扩展使得能够建模该类数据呢？这些问题促使了图神经网络的出现与发展。

二、图的定义

1.图的定义和种类

图可以用$G=(V,E)$来表示，
其中

• $V$是顶点或节点的集合，
• $E$是边的集合，
• $e_{ij}=(v_i,v_j)\in E$则表示从$v_i$指向$v_j$的边（有向图），或仅表示$v_i$和$v_j$之间的边（无向图）
• N ( v ) = { u ∈ V ∣ ( v , u ) ∈ E } N(v) = \left\{ u∈V|(v,u)∈E \right\} N(v)={u∈V∣(v,u)∈E}表示节点$v$的邻域

图的种类主要包括有向图、无向图，再往下细分这两类又包括简单图、多重图、完全图
简单图：
①不存在重复边;②不存在顶点到自身的边

简单有向图（图左）；简单无向图（图右）
多重图：
和简单图相对，图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联（即有自环）

完全图：
任意两个顶点之间都存在边

完全有向图（图左）；完全无向图（图右）

2.一些关于图的重要概念

2.1 子图

设有两个图G=(V, E)和G’=(V’, E’)，若V’是V的子集， E’是E的子集，则称G’为G的子图，若满足V(G’)=V(G)的子图G’，则称其为G的生成子图。

2.2 连通图

指的是一个图中的每对顶点之间都存在至少一条路径，即从图中的任意一个顶点出发，都可以通过边的连通性到达图中的任何其他顶点。
连通图可以分为以下几种类型：

• 强连通图（Strongly Connected Graph）：在一个有向图中，如果对于图中的任意两个顶点 u 和 v 都存在从 u 到 v 和从 v 到 u 的有向路径，那么该图是强连通图
• 无向连通图（Connected Graph）：在一个无向图中，如果对于图中的任意两个顶点 u 和 v 都存在一条无向路径，那么该图是无向连通图
• 弱连通图（Weakly Connected Graph）：在一个有向图中，如果将有向边的方向忽略，将其视为无向边后，得到的无向图是连通图，那么该图是弱连通图。
• 生成树（Tree）：生成树是针对无向图的，它没有回路（环路）。连通图的生成树就是包含图中全部顶点的一个极小连通子图。
• 生成森林（Forest）：生成森林是针对非连通图的，非连通图可分解为多个连通分量，而每个连通分量又各自对应多个生成树。

强连通图；无向连通图；强连通图；弱连通图

有向树：一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树（右图）

非连通图（左图）；生成森林（右图）

2.3 顶点的度、入度和出度

图中每个顶点的度定义为以该项点为一个端点的边的数目。

• 对于无向图，顶点v的度是指依附于该顶点的边的条数，记为TD(v)
• 对于有向图,顶点v的度分为入度和出度,入度是以顶点v vv为终点的有向边的数目，记为ID(v); 而出度是以顶点v为起点的有向边的数目，记为OD(v)。顶点v的度等于其入度和出度之和

2.4 边的权和网

在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称网

2.5 稠密图、稀疏图

边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。一般当图G满足$|E|<|V|log|V|$时，可以将G视为稀疏图；当图G满足$|E|$接近$|V^2|$时，可以将G视为稠密图

3.图的存储结构

图的表示包括邻接表、邻接矩阵、边集数组、邻接多重表、十字链表、链式前向星等，每种图的表示都有不同的用处，需要根据实际需求选择。
其中，比较标准和常规的表示方法有，邻接表、邻接矩阵和边集数组，这三种表示法都即可以表示无向图，也可以表示有向图。特殊一点的包括邻接多重表、十字链表和链式前向星。

• 邻接链表通常用来表示稀疏图，而邻接矩阵通常用来表示稠密图，另外，如果需要快速判断任意两个结点之间是否有边相连，可能也需要使用邻接矩阵表示法
• 邻接表
  • 存各种图都很适合，除非有特殊需求（如需要快速查询一条边是否存在，且点数较少，可以使用邻接矩阵）。尤其适用于需要对一个点的所有出边进行排序的场合。
  • 邻接表的一个潜在缺陷是无法快速判断一条边(u, v)是否是图中的一条边，唯一的办法是在邻接链表Adj[u]中搜索结点v。
  • 邻接表还衍生出了一种逆邻接表，因为邻接表统计出度的效率较高，而入度需要遍历整个表才可以统计出来，而逆邻接表不需要遍历，直接就可以统计出每个结点的出度，这正好和邻接表相反。
• 邻接矩阵
  • 邻接表的一个缺陷是无法快速判断一条边(u, v)是否是图中的一条边。而邻接矩阵克服了这个缺点，但付出的代价是更高的空间复杂度。
  • 邻接矩阵只适用于没有重边（或重边可以忽略）的情况。其最显著的优点是可以$O(1)$查询一条边是否存在。由于邻接矩阵在稀疏图上效率很低（尤其是在点数较多的图上，空间无法承受），所以一般只会在稠密图上使用邻接矩阵。
  • 空间复杂度高
• 边集数组
  • 由于直接存边的遍历效率低下，一般不用于遍历图。主要见到的就是在，最小生成树的 Kruskal 算法中，由于需要将边按边权排序，需要直接存边。在有时候，有可能需要多次建图（如建一遍原图，建一遍反图），此时既可以使用多个其它数据结构来同时存储多张图，也可以将边直接存下来，需要重新建图时利用直接存下的边来建图。
• 邻接多重表
  • 邻接多重表用于表示无向图
  • 邻接表虽然已经能够很好地表示无向图了，但是无向图访问或者删除一条边(Vi,Vj)时需要同时访问两个链表i和j并分别找到对应的边结点，这给针对图的边的操作（标记或删除）带来不便利。邻接多重表因此而演变过来的。当一个无向图需要频繁的修改时，邻接表表示法需要修改边两侧的结点对应的信息，而多重邻接表可以只修改一次，计算量节省了一半。
• 十字链表
  • 十字链表用来表示有向图
  • 十字链表是结合了邻接表和逆邻接表于一体的表示方法，用来表示有向图，综合了两种表示方法的优点，缺点是表示起来更加复杂。
• 链式前向星
  • 链式前向星是一种静态链表存储，用边集数组和邻接表相结合，可以快速访问一个顶点的所有邻接点，在算法竞赛中广泛使用。

3.1 邻接矩阵

图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息
下图是一个无向图和它的邻接矩阵

下图是一个有向图和它的邻接矩阵

下图是一个有向带权图和它的邻接矩阵

3.2 邻接表

邻接表（链表）表示由一个包含V条链表的数组Adj所构成，每个结点都有一条链表，存储与其相连的节点
无向图的邻接表的实例如下图所示

有向图的邻接表的实例如下图所示

带权图的邻接表的实例如下图所示

3.3 边集数组

使用一个数组来存边，数组中的每个元素都包含一条边的起点与终点（带边权的图还包含边权）。或者使用多个数组分别存起点，终点和边权。

3.4 邻接多重表

邻接多重表中，无向图中的每一个顶点分配一个顶点结点，所有顶点结点构成一个顶点数组$adjmultiList[num]$。另外每条边也分配一个边节点。
以下是顶点数组的展示：

以下是边节点的展示：

以下是邻接多重表实例的展示：

3.5 十字链表

十字链表是为了便于求得图中顶点的度（出度和入度）而提出来的。它是综合邻接表和逆邻接表形式的一种链式存储结构。其存储方式和邻接多重表类似。
以下是顶点数组的展示：

以下是边节点的展示：

3.6 链式前向星

链式前向星是一种静态链表存储，用边集数组和邻接表相结合，可以快速访问一个顶点的所有邻接点，在算法竞赛中广泛使用。

三、图神经网络类别

目前，最先进的图神经网络分为四类，即递归图神经网络、卷积图神经网络、图自动编码器和时空图神经网络

递归图神经网络（Recurrent Graph Neural Networks, RecGNN）大多是图神经网络的先驱作品。RecGNN旨在学习具有递归神经结构的节点表示。他们假设图中的一个节点不断地与其邻居交换信息/消息，直到达到稳定的平衡，RecGNN在概念上很重要，并启发了后来对卷积图神经网络的研究。特别是，基于空间的卷积图神经网络就继承了消息传递的思想。

卷积图神经网络（Convolutional Graph Neural Networks, ConvGNNs）将卷积运算从网格数据推广到图数据。主要思想是通过聚合节点$v$自身的特征$x_v$和邻居的特征$x_u$来生成节点v的表示，其中$u\in N（v）$。与RecGNN不同，ConvGNN堆叠多个图卷积层来提取高级节点表示。ConvGNN在建立许多其他复杂的GNN模型中发挥着核心作用，可用于节点分类和图分类，如下图所示：

（右图）具有多个图卷积层的ConvGNN。图卷积层通过聚合来自其邻居的特征信息来封装每个节点的隐藏表示。在特征聚合之后，将非线性变换应用于结果输出。
通过堆叠多层，每个节点的最终隐藏表示从另一个邻域接收消息
（左图）图卷积层之后是池化层，以将图粗化成子图，使得粗化图上的节点表示表示表示更高的图级表示。读出层通过取子图的隐藏表示的和/均值来总结最终的图表示

图自动编码器（Graph Autoencoders, GAE）是一种无监督的学习框架，它将节点/图编码到潜在向量空间中，并根据编码的信息重建图数据。GAE用于学习网络嵌入和图生成分布。对于网络嵌入，GAE通过重构图的结构信息（如图的邻接矩阵）来学习潜在节点表示。对于图生成，一些方法一步一步地生成图的节点和边，而另一些方法一次输出图。下图展示了用于网络嵌入的GAE。

编码器使用图卷积层来获得每个节点的网络嵌入。解码器计算给定网络嵌入的成对距离。
在应用非线性激活函数之后，解码器重建图邻接矩阵。通过最小化真实邻接矩阵和重构邻接矩阵之间的差异来训练网络

时空图神经网络（Spatial-temporal Graph Neural Networks, STGNN）旨在从时空图中学习隐藏模式，这在交通速度预测、驾驶员机动预期和人类动作识别等各种应用中变得越来越重要。STGNN的关键思想是同时考虑空间依赖性和时间依赖性。当前的许多方法将图卷积与RNN或CNNs集成以捕获空间依赖性，从而对时间依赖性进行建模。下图展示了用于时空图预测的STGNN。

用于时空图预测的STGNN。图卷积层之后是1D-CNN层。图卷积层对A和X(t)进行运算以捕获空间相关性，而1D-CNN层沿时间轴X滑动以捕获时间相关性。
输出层是线性变换，为每个节点生成预测，例如其在下一时间步长的未来值。