图神经网络基础：图论-点头深度学习网站

引言

图在我们身边随处可见；现实世界中的物体通常是以它们与其它事物的联系来定义的。一组物体以及它们之间的联系，都可以自然地表达为一个图。十多年来，研究人员已经开发了在图数据上操作的神经网络（称为图神经网络，或GNNs）。最近，深度学习的发展提高了图神经网络的表达能力。我们开始看到它在医学领域、药物设计、物理学模拟、流量预测和推荐系统等领域的实际应用。

相比较于卷积神经网络、循环神经网络等深度学习模型，图神经网络的发展是落后的。原因是因为图神经网络所处理的图数据，本身就比图像和文本数据更加的难以处理。具体来说，图数据不像一维的文本数据拥有左右的语义相关性，也不像二维的图片数据像拥有上下左右元素的相关性，其本身是一个不规则的可变结构的三维数据，因此对它的建模要更难。

本章探讨并解释了现代图神经网络。首先补充一些图的基本知识。其次分析了什么样的数据最自然地被表述为图，以及一些常见的例子。最后探讨了基于图的数据结构都可以处理哪些问题。

图的节点，边和全局

首先让我们确定什么是图，图代表了一组实体（节点）之间的关系（边）。用于表示图的主要属性有三个：

（1）Vertex/Node 顶点（或节点）属性。例如，节点的身份、邻居的数量等。

（2）Edge/Link 边（或链接）属性。例如，边的身份、节点的关系等。

（3）Global 全局（或主节点）属性。例如，节点的数量、最长的路径等，表示整张图的主要特征。

为了进一步描述每个节点、边或整个图，可以用向量的形式来存储信息，即把点、边和全局都用向量进行表示，如图9-1所示。

Vertex(or node) embedding: 顶点（或节点）编码

Edge(or Link) attributes and embedding: 边（或链接）属性编码

Global(or master node) embedding: 全局（或主节点）编码

有向图和无向图(Directed/Undirected）

为了更清晰的解释图数据的各个属性，以三国时期的人物关系为例子进行说明。根据图结构中的边是否有方向，可以把图数据分成两类。边没有方向的图称为无向图，如图9-2(a)所示；反之则为有向图，如图9-2(b)所示。

节点的度（Node degree）

（1）无向图节点的度为：与该节点相关联边的数目；

（2）有向图节点的出度为：由该节点发出的边的数目；

（3）有向图的节点的入度为：以该节点为终点的边的数目；

如图9-2(a)所示，节点“刘备”的度等于5；如图9-2(b)所示，节点“刘备”的出度等于2，入度等于3。

邻接矩阵（Adjacency Matrix/List）

邻接矩阵 (Adjacency Matrix) 是表示顶点之间相邻关系的矩阵, 如图 9-3 所示。设 $G=(V, E)$ 是一个图, 其中 $V=\left\{v_1, v_2, \cdots, v_n\right\} \circ G$ 的邻接矩阵是一个 $n$ 阶方阵且具有以下性质。
(1) 对无向图而言, 邻接矩阵一定是对称的, 而且主对角线一定为零, 副对角线不一定为 0 , 有向图则不一定如此。
(2) 在无向图中, 任一顶点 $i$ 的度为第 $i$ 列（或第 $i$ 行）所有非零元素的个数, 在有向图中顶点 $i$ 的出度为第 $i$ 行所有非零元素的个数, 而入度为第 $i$ 列所有非零元素的个数。
(3) 用邻接矩阵法表示图共需要 $n^2$ 个空间, 由于无向图的邻接矩阵一定具有对称关系,所以扣除对角线为零外, 仅需要存储上三角形或下三角形的数据即可, 因此仅需要 $n(n-1) / 2$ 个空间。即便如此，当图结构太大时，邻接矩阵存储的资源占用依然是一个问题。

此外，除了使用0、1来表示节点之间是否存在关系以外，也可以用权重的方法进行节点关系的表示，如果关系强，则赋予更高的数值，反之亦然。如图9-4所示，周瑜和小乔是夫妻，所以可以拥有更高的权重。

但是，一个问题值得注意的问题是，有许多邻接矩阵可以表示相同的连接。如图9-5所示，同一个社交网络，将邻接矩阵中人物的排列顺便变一下，可以得到两个完全不一样的邻接矩阵。英语的专业说法是，they are not permutation invariant。神经网络模型不能保证学习到这种 permutation invariant。

表示稀疏矩阵的一种优雅而有效的记忆方式是邻接列表（adjacency list）。例如, 如果节点 $n_i$ 和 $n_j$ 之间的边 $e_k$ 存在连通性, 那么把元组 $(i, j)$ 作为邻接列表的第 $k$ 个条目。这样可以避免在图的不连接部分进行计算和存储无效信息。为了使这一概念具体化, 请读者观察邻接列表的表示示例，如图 9-6 所示。
$$
[1,2],[2,3],[3,7],[4,5],[4,6],[4,8],[5,6]
$$

图的连通性（Connectivity of Graphs）

在图论中, 连通图基于连通的概念。在一个无向图 $G$ 中, 若从顶点 $i$ 到顶点 $j$ 有路径相连 (当然从 $j$ 到 $i$ 也一定有路径)，则称 $i$ 和 $j$ 是连通的。如果 $G$ 是有向图，那么连接 $i$ 和 $j$的路径中所有的边都必须同向。如果图中任意两点都是连通的, 那么图被称作连通图; 如果此图是有向图, 则称为强连通图。无向图的非连通图和连通图如图 9-7(a)和图 9-7(b) 所示,有向图的连通图和非连通图如图 9-7(c) 和 9-7(d) 所示。

图的直径和最短路径

图中任意两节点的相连方式有很多，可能直接相连，也可能通过其它节点间接相连。而图的最短路径（Shortest Path）指的是所以连接方式中，最短的那种方式。图的直径（Graph Diameter）定义为图中最长的最短路径的长度。

如图9-8所示，刘备和关羽两节点之间可以直接相连，也可以通过张飞相连。此图的最短路径有三个，分别是张飞–>关羽，关羽–>刘备，刘备–>张飞，而图的直径是刘备–>黄忠。

图的度中心性

度中心性（Degree Centrality）是在网络分析中刻画节点中心性（Centrality）的最直接度量指标。一个节点的节点度越大就意味着这个节点的度中心性越高，该节点在网络中就越重要。通常，为了便于比较或者进行其它计算，需要将度中心性进行标准化。标准化的方式通常是每个顶点的度除以图中可能的最大度数，即 N-1，其中 N 表示图中的顶点个数，标准化公式为：

$$
\text { norm }(\text { degree })=\frac{\text { degree }}{N-1}
$$

如图9-9所示，节点刘备的中心性等于5/6，节点于禁的中心性等于0，节点关羽的中心性等于2/6。

图的特征向量中心性

图的节点、边和全局信息都可以用向量来表示。现在用一个长度为5的向量 x 来表示节点的信息, A 来表示临界矩阵，如图9-10所示。

当 A和 x 相乘时，邻接矩阵做的事情是将相邻节点的求和值重新分配给每个点。这样做的结果就是“扩散了”点度中心性。

$$
\boldsymbol{A} \times \boldsymbol{x}=\left[\begin{array}{lllll}
0 & 1 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 \\
0 & 0 & 1 & 0 & 1 \\
0 & 0 & 1 & 1 & 0
\end{array}\right]\left[\begin{array}{l}
x_1 \\
x_2 \\
x_3 \\
x_4 \\
x_5
\end{array}\right]=\left[\begin{array}{l}
0 \cdot x_1+1 \cdot x_2+0 \cdot x_3+0 \cdot x_4+0 \cdot x_5 \\
1 \cdot x_1+0 \cdot x_2+0 \cdot x_3+0 \cdot x_4+0 \cdot x_5 \\
0 \cdot x_1+0 \cdot x_2+0 \cdot x_3+1 \cdot x_4+1 \cdot x_5 \\
0 \cdot x_1+0 \cdot x_2+1 \cdot x_3+0 \cdot x_4+1 \cdot x_5 \\
0 \cdot x_1+0 \cdot x_2+1 \cdot x_3+1 \cdot x_4+0 \cdot x_5
\end{array}\right]
$$

根据线性代数中关于特征值和特征向量的知识, 可以求解 $\boldsymbol{A} * \boldsymbol{x}=\lambda * \boldsymbol{x}$ 。假设图结构如图 9-11 所示, 解得的特征值和特征向量分别如下所示:

特征值为: $\left[\begin{array}{lllll}2.4811943 & -2 . & -1.17008649 & -0 . & 0.68889218\end{array}\right]$
特征向量为:
$$
\left[\begin{array}{ccccc}
{[-0.5298991} & -0.5 & -0.43248663 & 0.5 & 0.68889218] \\
{[-0.35775124} & 0.5 & 0.19929465 & 0.5 & 0.1793384] \\
{[-0.35775124} & -0.5 & 0.19929465 & -0.5 & -0.57645095] \\
{[-0.42713229} & 0 . & 0.73923874 & 0 . & 0.52065737] \\
{[-0.5298991} & 0.5 & -0.43248663 & -0.5 & 0.1793384]
\end{array}\right]
$$

取特征值最大的特征向量作为节点的特征向量中心性, 即
$$
\left\{\text { node }_1: 0.53, \text { node }_2: 0.358, \text { node }_3: 0.358, \text { node }_4: 0.427, \text { node }_5: 0.53\right\}
$$

对照图9-11解释此结果，由于node1和5的度数最大，都为3，所以它们的特征向量中心性也相同。node3和4虽然度数相等，但是它们的特征向量中心性不同，原因是node3相连的两个节点一个度数是3，另一个是2；而node4相连的两个节点度数都是3。也就是说特征向量中心性不仅仅考虑自身的度数，还考虑了邻居节点的度数。

图的中介中心性

中介中心性（Betweenness Centrality）的思想是：如果一个成员位于其它成员的多条最短路径上，那么该成员就是核心成员，就具有较大的中介中心性。它是指网络中经过某点并连接这两点的最短路径占这两点之间的最短路径线总数之比。以经过某个节点的最短路径数目来刻画节点的重要性指标，公式如下：

$$
B C=\sum_{s, t \in i} \frac{d_{s t}(i)}{d_{s t}}
$$

其中 $d_{s t}$ 表示 $s$ 到 $t$ 的最短路径数量, $d_{s t}(i)$ 表示从 $s$ 到 $t$ 最短路径中经过 $i$ 节点的数量。

举例计算图9-12节点刘备的中介中心性：节点张飞分别到其它五个节点的最短路径一共有五条，其中有四条都经过节点刘备（即，只有张飞–>关羽这条不经过）。同理计算其它四个节点的情况，它们的情况相同，都是分别到其它五个节点的最短路径一共有五条，其中全部都需要经过节点刘备。所以节点刘备的中介中心性等于：

$$
\frac{4+5+5+5+5}{5+5+5+5+5}=\frac{24}{25}
$$

图的接近中心性

图的接近中心性（Closeness Centrality）反映在网络中某一节点与其它节点之间的接近程度。如果节点到图中其它节点的最短距离都很小，那么它的接近中心性就很高。相比中介中心性，接近中心性更接近几何上的中心位置。

如果进行归一化处理，就是求这个节点到其它所有节点的平均最短距离，公式如下：

$$
d_i=\frac{\sum_{j \in i} d_{i j}}{n-1}
$$

一个节点的平均最短距离越小, 那么这个进行的接近中心性就越大。如果节点 $i$ 和节点 $j$ 之间没有路径可达, 则定义 $d_{i j}$ 为无穷大, 其倒数为 0 。
$$
C C_i=\frac{1}{d_i}=\frac{n-1}{\sum_{j \in i} d_{i j}}
$$

其中 $C C_i$ 表示 $i$ 节点的接近中心性, $d_{i j}$ 表示 $i$ 到 $j$ 的最短距离。 $C C_i$ 值越大, $i$ 点的接近中心性越大。

生活中的图

读者可能已经熟悉了某些类型的图数据，比如社交网络、分子结构等等。然而，图是一种极其强大和普遍的数据表示方法，接下来笔者将展示两种读者可能认为不可以用图来建模的数据类型：图像和文本。虽然是反直觉的，但通过将图像和文本看作是图，可以更多地了解它们的对称性和结构，并建立一种直觉，这将有助于理解其它不太像网格的图数据。

1. 把图像看作一种图

通常认为图像是具有图像通道的矩形网格，并将它们表示为数组（例如，224x224x3 的矩阵）。另一种思考图像的方式是具有规则结构的图，以 224x224x3 的图片举例，其中每个像素代表一个节点，并通过边缘与相邻的像素相连。每个非边界像素正好有8个邻居，每个节点存储的信息是一个代表像素RGB值的3维向量。

通过邻接矩阵来可视化一个图形的连通性的方法。首先对节点进行排序, 在这种情况下,在一个简单的 $5 \times 5$ 的笑脸图像中, 每个节点有 25 个像素, 如果两个节点共享一条边, 就用一个数值填充对应的 $n_{\text {nodes }} \times n_{\text {nodes }}$ 矩阵。请注意, 如图 9-13 所示, 这三种表示方法都是对同一份数据（这张笑脸图像）的不同表示方法。

2. 把文本看作一种图

我们可以通过为每个字符、词关联一个索引来数字化文本，并将文本表示为这些索引的一个序列。这就形成了一个简单的有向图，其中每个字符或索引都是一个节点，并通过一条边与后面的节点相连，如图9-14所示。

当然，在实践中，GNN通常不是处理文本和图像的最佳算法。因为文本和图像都是规则数据，例如，图像的像素只与周边像素相关，文本中每个词只与前一个词和后一个词相连接，从邻接矩阵的表示上就可以看出明显的规律。针对这些规律明显的数据，有更好的算法可以处理它们，如卷积神经网络和循环神经网络等。

GNN更擅长处理不规则的数据，更专业的说法是异质化的数据（heterogeneously structure），例如社交网络、分子结构这种，在这些例子中，每个节点的邻居数量是可变的（与图像和文本的固定邻居大小相反）。这种数据除了用图来表达外，很难用其它方式来表达，举例如下。

3. 把分子结构看作一种图

分子是物质的组成部分，由三维空间中的原子和电子构成。所有的粒子都是相互作用的，但是当一对原子彼此卡在一个稳定的距离上时，我们说它们有一个共价键。不同的原子对和键有不同的距离（如单键、双键）。把这个三维物体描述成一个图，其中节点是原子、边是共价键，这是一个非常方便和常见的抽象概念，如图9-15所示。

4. 把社交网络看作一种图

社会网络是研究人们、机构和组织的集体行为模式的工具。可以通过将个人建模为节点，将他们的关系建模为边来建立一个代表人群的图，如图9-16所示的人物关系图。

其实，生活中能表示成图结构的数据远不止如此。图的灵活性决定了它在数据表示中的重要地位，对图的研究是必要且意义重大的。

图能解决的问题

我们已经描述了一些常见图的例子，但是我们想在这些数据上执行什么任务呢？图上的预测任务主要有三种类型：全图级别的预测、节点级别的预测和边缘级别的预测。

在全图层面的任务中，主要对整个图的单一属性进行预测。对于节点层面的任务，主要预测图中每个节点的一些属性。而对于边缘层面的任务，要预测图中边缘的属性或存在。

1. Graph-level task

在全图层面的任务中，目标是预测整个图的属性，如图9-17所示。对于一个以图表示的分子，我们可能想预测该分子的气味，或者预测它是否具有某些特殊的药理性质可以用来治疗某些疾病。这与MNIST和CIFAR的图像分类问题类似，我们想把一个标签与整个图像联系起来。对于文本，一个类似的问题是情感分析，我们想一次性地识别整个句子的情绪或情感。

2. Node-level task

节点级任务关注的是预测图中每个节点的身份或角色，如图9-18所示。按照图像的类比，节点级的预测问题类似于图像分割，试图标记图像中每个像素的作用。对于文本，类似的任务是预测一个句子中每个词的语音部分（如名词、动词、副词等）。

节点级预测问题的一个典型例子是Zach的空手道俱乐部。该数据集是一个单一的社会网络图，问题是两名教员决裂了，学生们必须选择其中一人效忠。正如故事所言，Hi先生（教练）和John H（管理员）之间的争执在空手道俱乐部中造成了分裂。节点代表空手道练习者个人，边则代表这些成员在空手道之外的互动关系。预测问题是对一个给定的成员是否会效忠于Hi先生或John H进行分类。在这种情况下，两个节点之间的距离表示两人之间关系的远近。

另一个例子是近期非常火热的蛋白质三维结构预测模型：AlphaFold，如图9-19所示。这个例子里，我们把蛋白质中的每个氨基酸看作节点，如果两个氨基酸相连则连一条边。由于蛋白质是会折叠的，所以模型AlphaFold的目的是预测每个节点在三维空间中的位置，解决了人类在这个领域50年没有解决的问题：蛋白质三维结构预测。

3. Edge-level task

边缘级别任务的一个例子是在图像场景理解中。除了识别图像中的物体，深度学习模型还可以用来预测它们之间的关系。可以将其表述为边缘级分类：给定代表图像中物体的节点，希望预测这些节点中哪些节点共享一条边缘，或者该边缘的价值是什么。如图9-20所示，原始图像（左上角）已经被分割成五个实体：两个拳手、裁判、观众和垫子。