图神经网络（GNN）

引言

图神经网络（Graph Neural Networks，GNNs）是一种专为图数据设计的深度学习模型。它们能够直接在图结构上操作，捕捉节点间的复杂关系和图的全局结构特征。图神经网络在多种任务中表现出色，包括节点分类、图分类、链接预测和图生成等。在图神经网络中，图被定义为一组节点和连接节点的边。每个节点和边可以拥有它们的属性。GNN的目标是学习图中节点的低维向量表示（嵌入），这些向量捕获了节点的特征信息以及它们在图结构中的位置。

GNN工作原理基于邻域聚合（或消息传递）策略，其中每个节点通过聚合和转换其邻居节点的信息来更新自己的表示。这个过程通常包括以下几个步骤：

1.消息聚合：对于给定的节点，从其邻居收集信息。这涉及到对邻居节点的特征向量进行聚合操作，如求和、平均或最大化。

2.更新：结合当前节点的特征和聚合来自邻居的信息来更新节点的表示。这个更新过程通常通过一个神经网络（如全连接层）实现。

3.重复：上述过程可以重复多次，每一次迭代允许信息传递更远的距离，从而捕获更宽范围内的图结构特征。

4.输出：最终，对节点的嵌入可以通过各种方式被利用，如直接用于节点级任务，或者通过汇总所有节点的表示来用于图级任务。

GNN在多个领域都有广泛的应用，如社交网络分析、推荐系统、蛋白质结构预测、化学分子性质预测、知识图谱推理以及交通网络优化等。下面我们将进行详细的介绍。

消息传递神经网络

本章节我们将描述使用图神经网络（GNN）来解决图预测任务。GNN是对图的所有属性（节点、边、全局背景）的一种可优化的转换，它保留了图的对称性（permutation invariances）。笔者将使用Gilmer等人提出的“消息传递神经网络（message passing neural network）”框架来构建GNNs。

GNNs采用“图进图出”的架构，意味着这些模型类型接受一个图作为输入，将信息加载到其节点、边和全局上下文中，并逐步转化这些嵌入，而不改变输入图的连接性。

从最简单的GNN架构开始，为所有的图属性（节点、边、全局）学习新的向量表示，但目前还没有使用图的连接性。

如图9-27所示，GNN在图的每个图属性上使用一个单独的多层感知器（MLP）；称之为GNN层。具体来说，对于每个节点向量，应用MLP并得到一个新的映射后的节点向量。对每条边做同样的工作，学习每条边的向量表示。也对全局背景向量做同样的工作，为整个图学习一个向量表示。

GNN不更新输入图的连接性，因此可以用与输入图相同的邻接列表和相同数量的特征向量来描述GNN的输出图。但是，输出图的每个节点、边缘和全局背景的向量表示实际上已经经过了MLP的多次映射。

至此，一个简单的GNN建立完成，接着我们讨论如何用GNN的输出结果来进行预测。

以二元分类的问题进行举例，因为这个情况可以很容易地扩展到多类或回归情况。如果任务是对节点进行二元预测，而图中已经包含了节点信息，那么方法就很简单了，对于每个节点的向量，应用一个线性分类器即可，如图9-28所示。

然而，实际上没有那么简单。例如关系的分类信息可能存储在边向量中，而不是存储在节点向量中。这时，仅仅依靠节点向量进行分类预测就显得有些单薄，我们需要一种方法来收集边上的信息，可以通过池化来做到这一点。池化分两步进行：首先对于每个要汇聚的属性，收集它们的向量表示，并将它们串联成一个矩阵。然后，对这个矩阵进行某种池化操作，通常是通过一个求和的操作。

如图9-29所示，通过求和操作，可以把两个边向量的信息和当前节点向量的信息汇聚在一起映射成一个新的汇聚向量。

同样的思想也可以运用在边向量和全局向量上, 如图 9-30 所示, 其中 \(\rho\) 表示池化操作,例如 \(\rho_{E_n \rightarrow V_n}\) 表示把边向量的信息汇聚到节点向量中。

现在，我们可以建立一个简单的GNN模型，如图9-31所示，并通过汇聚图中不同属性的信息进行二分类预测。其中，汇集操作将作为构建更复杂的GNN模型的基石。

请注意，在这个最简单的GNN表述中，在GNN层内根本没有使用图的连接性（邻接矩阵/列表）。每个节点都是独立处理的，每条边也是如此，还有全局环境。只在汇集信息进行预测时使用连接性。

考虑连接性的图神经网络

上述小节是最简单的图神经网络的实现，并没有把图的连接性考虑在内。那么应该如何融入邻接矩阵的信息呢？可能很直接地可以想到，将邻接矩阵和特征合并在一起应用在深度神经网络上，如图9-32所示，直接将一个节点的邻接矩阵+特征合起来作为一个观测。

但是，这种方法的问题在于：

（1）需要O|V|的参数复杂度；

（2）不适用于不同大小的图；

（3）对节点顺序敏感。

解决方法是将卷积神经网络的思想泛化到图神经网络上。具体来说，就是局部相关性和层级结构，先从宏观上来观察一下，CNN的结构如图9-33(a)所示，GNN的结构如图9-33(b)所示。

需要注意的是，卷积处理的图片数据是规则的，因此在定义局部相关性时，可以通过定义一个卷积核来实现，卷积核的尺寸决定着局部的范围大小。而图数据的不规则的，因此不能采用卷积核的方式来实现局部相关性。这里采用的是聚合邻居节点的方式，即根据邻接矩阵的信息，在每个GNN层中融合节点邻居的信息。如图9-33所示，Layer 0的一个节点，在Layer 1中，可以跟它相邻的两个节点之间进行信息的汇聚；在Layer 2中，就可以间接的与全局节点之间进行信息的汇聚；有点类似于卷积神经网络中，“感受野”的概念。GNN还可以通过多层堆叠方式获得更大的感受野，获得近乎全局的信息交互。如果实际任务还是需要很多层GNN网络，那么可以在GNN模型中增加skip connections。这个想法来源于CNN算法中的ResNet模型。通过skip connections可以解决因网络层加深而带来的网络退化问题。

另一方面，融合节点邻居信息这一思想，与神经网络的分层结构是非常相似的，如图9-34所示。

从本质上讲，GNN中的消息传递和CNN中的卷积核操作都是处理一个元素的邻居的信息，以便更新该元素的值。在图中，元素是一个节点，而在图像中，元素是一个像素。不同的是，图中相邻节点的数量可以是可变的，不像图像中，每个像素都有固定数量的相邻元素（8个）。

最后，GNN的层数往往不会太深，这与图数据的性质有关，读者还记得那个地球村有趣的说法吗？只需通过六个人，就可以找到世界上任何一个你不认识的人。如果把全球人的关系绘制成一个巨大的社交图，这意味着在一个只有6层的GNN中，一个节点最终就可以纳入整个图的信息。

接下来的问题是，根据邻接矩阵对节点的信息进行汇聚之后的操作是什么？如图9-35所示。

这个问题的答案是“神经网络”，在9.1.5节中有过介绍，GNN在图的每个组成部分上（节点、边、全局）都分别使用一个单独的多层感知器（MLP）进行映射，如图9-36所示。

值得注意的是，这个MLP是应用在单独的节点、边或全局向量上的，这意味着节点和边之间不能通过这个MLP进行信息的交互，这肯定是不合理的。其实解决办法也很简单，就是在向量输入MLP之前，先进行在节点和边之间进行汇聚操作。

如图 9-37 所示, 在向量信息送入 \(M L P(f)\) 之前, 先进行边到节点 \(\left(\rho_{E_n \rightarrow V_n}\right)\) 和节点到边 \(\left(\rho_{E_n \rightarrow V_n}\right)\) 的信息汇聚，来完成边和节点之间的信息交互。
同理，边、节点和全局向量三者之间也可以相互之间进行信息的交互，如图 9-38 所示。

图神经网络模型的训练

GNN的训练流程如下，流程图如下图所示。

（1）输入数据；

（2）用GNN训练数据；

（3）得到节点向量；

（4）送入Predictor（本质是一个MLP，将节点向量转换为最终需要的预测向量）；

（5）得到预测向量；

（6）选取损失函数和标签计算损失；

（7）根据损失更新模型参数直到收敛；

（8）选取评估指标测试模型；

（9）使用模型解决实际问题。

Predictor 其实就算一个 MLP, 用来改变向量维度的, 目的是变化成想要的预测向量的形状。这里解释一些不同粒度任务下的 Predictor。假设 GNN 得到的节点是 \(d\) 维的, 如果是节点级别的预测任务, 例如在 \(k\) 个类别之间做分类, 可以直接用节点向量做 Predictor 的输入， Predictor 将 \(\mathrm{d}\) 维的节点向量映射到 \(k\) 维输出即可。
如果是边级别的预测任务, 如下图所示, 预测节点 \(u, v\) 之间是否有边。

这时候可以将节点向量 \(\boldsymbol{u}\) 和 \(\boldsymbol{v}\) 进行拼接, 拼接后的向量在送入 Predictor 进行维度变化即可, 即 \(\hat{y}_{u v}={MLP}\left({Concat}\left(h_u^{(L)}, \mathrm{h}_v^{(L)}\right)\right)\) 。

此外, 在边级别的任务上, Predictor 除了可以是 MLP 之外, 还可以替换成没有任何可训练参数的点积操作 (dot product)。因为两个向量的点积结果意味着两个向量的相关程度,是一个常数。当两个向量的点积结果大时, 意味着这两个节点之间有很大可能存在边。即 \(\hat{y}_{l v}=\left(h_u^{(L)}\right)^{\wedge} \mathrm{T}, \mathrm{h}_v^{(L)} 。\)

如果是图级别的任务, 可以聚合图中所有节点 (global pooling) 的节点向量来做预测,即 \(\hat{y}_G={Head}_{\text {graph }}\left(h_v^{(L)} \in R^d, \forall v \in G\right)\) 。
其中 Head graph graph 有很多可选方式, 常见的聚合方式如下:
(1) global mean pooling: \(\hat{y}_G={Mean}\left(h_v^{(L)} \in R^d, \forall v \in G\right)\);
(2) global max pooling: \(\hat{y}_G={Max}\left(h_v^{(L)} \in R^d, \forall v \in G\right)\);
(3) global sum pooling: \(\hat{y}_G={Sum}\left(h_v^{(L)} \in R^d, \forall v \in G\right)\) 。

这些聚合方式其实有一定的选择技巧，例如，如果想比较不同大小的图，mean方法可能比较好，因为结果不受节点数量的影响；如果关心图的大小等信息，sum方法可能比较好，因为可以体现图的节点数量。如果关心图的某些重要特征，max方法会好一些，因为可以体现图中最重要的节点信息。这些方法都在小图上表现很好。但是在大图上的global pooling方法可能会面临丢失信息的问题。举例：G₁的节点嵌入为 { − 1 , − 20 , 0 , 1 , 20 }； G₂的节点嵌入为 { − 10 , − 20 , 0 , 10 , 20 } ，显然两个图的节点嵌入差别很大，图结构很不相同。但是经过global sum pooling后：不管是求平均，还是求最大，还是求和。这两个图的表示向量一样了，无法做出区分，这是不行的。

为了解决这一问题，解决方法是分层聚合节点向量（hierarchical global pooling）。具体来说，可以使用ReLU(Sum(·)) 做聚合，先分别聚合前两个节点和后三个节点的嵌入，然后再聚合这两个嵌入。举例：

G1 :

• 第一轮聚合: \(\hat{y}_a={ReLU}({Sum}(\{-1,-20\}))=0, \hat{y}_b={ReLU}({Sum}(\{0,1,20\}))=21\)
• 第二轮聚合: \(\hat{y}_G={ReLU}\left({Sum}\left(\left\{y_a, y_b\right\}\right)\right)=21\)

G2:

• 第一轮聚合: \(\hat{y}_a={ReLU}({Sum}(\{-10,-20\}))=0, \hat{y}_b={ReLU}({Sum}(\{0,10,20\}))=30\)
• 第二轮聚合: \(\hat{y}_G={ReLU}\left({Sum}\left(\left\{y_a, y_b\right\}\right)\right)=30\)

这样就可以将G1​和G2​作出区分了。其实，这种分层聚合得到图级别预测结果的方式，某种程度上非常类似于CNN处理图像识别问题的层级结构，如下图所示：

两种方法的区别在于上图中CNN处理图像识别问题的模型架构是用来训练的，是一个模型。而GNN的层次聚合是一个操作，不是一个模型。具体来说，是对GNN模型的计算结果进行分成池化操作，其中没有任何可学习参数。将池化后的结果送入Predictor中进行结果向量的预测，在Predictor中才存在可学习参数。

以上解释的是不同粒度的预测任务，接下来解释一些不同的训练方法，GNN的训练方式分为两种：

（1）有监督学习（supervise learning）：直接给出标签（如一个分子图的药理活性）

（2）无监督学习（unsupervised learning / self-supervised learning）：使用图自身的信号（例如：预测两节点间是否有边）

有监督学习：按照实际情况而来，不同任务下，标签是不同的，以下是具体的应用例子。

（1）节点级别预测——引用网络中，节点（论文）属于哪一学科；

（2）边级别预测——交易网络中，边（交易）是否有欺诈行为；

（3）图级别预测——分子图的药理活性。

无监督学习：在没有外部标签时，可以使用图自身的信号作为有监督学习的标签。举例来说，GNN可以预测：

（1）节点级别：节点统计量（如clustering coefficient, PageRank等）；

（2）边级别：链接预测（隐藏两节点间的边，预测此处是否存在链接）；

（3）图级别：图统计量（如预测两个图是否同构）。

图数据的数据增强

图数据的数据增强（Graph Augmentation for GNNs）简称图增强，可以从特征层面或结构层面进行展开。主要解决的问题是现实生活中很多图数据不规范，不能直接适用GNN进行处理，要进行一定的数据预处理。

节点特征层面

现实生活中，图数据往往体量很庞大，很多节点是没有特征的，或者只有一小部分节点存在特征。没有特征的话怎么聚合节点信息呢？这里主要有两种简单的直接给每个节点加上特征的方法：

（1）直接给每个节点加上同样的值，也就是给每个节点赋常数特征，如图9-39所示。

虽然这种方法看起来好像没什么用，但实际应用是有效的。也可以通过聚合的方式对未知的节点向量赋值，举例：假设图9-39中各个节点采样两层的邻居节点：A节点的一阶邻居是BCD，二阶邻居是AC、AEF、A。所以如果使用加法作为聚合信息的方法的话，而且还有聚合其本身的话，最后的结果就是（1+1+1）+（1+1+1+1+1）+（1+1）+ 1 = 11。这个数值有点像是节点度数，是根据图结构信息聚合得到的。

（2）独热编码：给每个节点赋唯一ID，将ID转换为独热编码向量的形式，如图9-40所示。

相比于赋值常量，独热编码方法的表达性更强，在最开始时就能体现不同的节点。但是，一个难以处理的地方是输入one-hot的维度是取决于输入图的节点数量，如果有新节点加入，可能会改变之前所有节点的向量长度。

对比这两种方法可得，赋值相同的常数这种方法更加通用，适用于所有图；时间复杂度也更低；表达性中等，可以学到图结构信息。相反，one-hot这种方法只适用于小图，大图会导致节点向量的长度过长；表达性更强，但是时间复杂度与图数据大小成正比。

除了上面两种简单的方法，也可以根据图的各种属性来进行节点向量的初始化。这些属性在之前的博文都有介绍，例如节点的度（Node degree）、度中心性 （Degree Centrality）、特征向量中心性（Eigenvector Centrality）、中介中心性（Betweenness Centrality）和接近中心性（Closeness Centrality）等等。这些属性可以让节点更好的表示图的结构信息。值得注意的是，一些特定的结构难以被GNN学习，如图9-41所示，v1的度数都是2，但是所在的图完全不同，这就导致输入基本特征难以学习到这个特性。

这种问题的解决方法也很简单：具体问题具体对待。在循环图9-41中，可以通过环计数来区分上面的两个 v1，图9-41(a)的环计数为3，图9-41(b)的环计数为4，将3和4这两个常量作为特征分别添加到 v1节点的特征向量中即可。这个方法可以扩展到其它具体问题中，例如，在蛋白质分子模型中，每个节点代表一个原子，可以把原子的电荷数量、质量、体积等都作为特征向量的元素，当然也可以包含节点的度（Node degree）、度中心性 （Degree Centrality）、特征向量中心性（Eigenvector Centrality）、中介中心性（Betweenness Centrality）和接近中心性（Closeness Centrality）这些图的结构属性。这样向量化的节点不仅包含分子的结构信息还包含当前分子的属性信息，表征能力更强。

图结构层面

图结构层面的数据增强主要是用来解决图结构过于稀疏或过于稠密的问题。图结构过度稀疏可能导致信息传递效率低，因为边太少了，很有可能出现图中两个节点相距太远，信息交互困难。反之，图过度稠密则会导致信息传递的计算代价太高，每次计算都需要对好几个节点做运算，因为图稠密意味着邻接节点多。

针对图稀疏问题，可以为两个跳邻居和目标节点之间增加一个虚拟边，如图9-42所示。

当然，也可以增加虚拟点，如图9-43所示。

不管是增加边，还是增加节点，都可以提升在稀疏图中的信息传递能力。

对于过于稠密的图数据，如果聚合所有的邻居节点的话，最后计算的成本可能较高。为了解决这种情况，可以使用采样方法，即每次只随机采样 N 个邻居，然后开始聚合。这个想法在图模型Graph Sample and Aggregate Network（GraphSAGE）就有应用。优点是可以每次抽样不同的邻居，以增加模型鲁棒性，并且可以控制参数 N，来控制计算量；缺点也很明显，可能会损失重要信息，因为有的邻居直接不使用。