构建 GNN 的「统一场」：从与 WL 算法、组合优化算法的联系看 GNN 的表达能力

雷锋网 (公众号：雷锋网) AI科技评论按： 近年来，图神经网络（GNN）领域內可谓百家争鸣。然而，真正要想在图神经网络的设计上有革命性的创新，不可避免地要对图论的本质问题进行深入探究。

本文是一篇来自京都大学的图神经网络表达能力综述，从GNN、WL 算法、组合优化问题之间的联系入手，进行了深入的归纳和分析。内容涉及计算机网络通信、网络算法，组合数学、可计算性分析等方面，内容非常丰富，其融会贯通的能力令人叹为观止！ 

原文链接： https://arxiv.org/pdf/2003.04078v1.pdf

一、引言

对于各种各样的图学习问题来说，图神经网络（GNN）是非常有效的机器学习模型。这些问题包括化学信息学、推荐系统、问答系统、以及组合优化问题。Hamilton、Zhou、Wu 等人分别于 2017、2018、2019 年对 GNN 做了全面的综述。

尽管在许多领域中，GNN 在实验中都取得了成功，但是 Xu 等人和 Morris 等人却指出，GNN 不能够区分一些图对。这说明 GNN 不能使用任何参数正确地对这些图进行分类，除非这些图的标签是相同的。这样的结果与多层感知机的通用近似能力形成了鲜明的对比。

此外，Sato 等人指出了 GNN 最多能像分布式局部算法（Distributed Local Algorithm）一样强大。因此，除了图同构问题，还有许多 GNN 无法解决的组合优化问题。所以，研究人员提出了各种各样可证明的强大的 GNN 模型，从而克服 GNN 的局限性。

针对 GNN 的表达能力和各种各样为了克服这些局限性而设计的 GNN 模型，本文给出了一个全面的概述。与其它关于 GNN 的综述（介绍 GNN 的架构和应用）不同，本文重点关注 GNN 的理论特性。

本文的组织结构如下：在本章的其余部分中，我们将介绍本文使用的数学符号并简要回顾标准的 GNN 模型。在第 2 章中，我们看到 GNN 不能使用基本的参数和具体的示例来区分某些图。在第 3 章中，我们介绍了 GNN 和 WL 算法之间的联系。在第 4 章中，我们根据 GNN 与分布式局部算法的联系，介绍了 GNN 可以/不可以求解的组合优化问题。在第 5 章中，我们将 GNN、WL 算法，以及分布式局部算法之间的关系总结为「XS 一致性」（XS correspondence）。

1、数学符号

表一为本文中使用到的数学符号：

表 1：数学符号

{...} 表示一个集合，{{...}} 表示一个多重集。 在多重集之中，同一个元素可以出现多次。例如，{3,3,4} = {3,4}，但是{{3,3,4}} ≠ {3,4}。有时，我们将一个集合看做一个多重集，反之亦然。

对于每个正数             ，[n] 代表集合 {1,2,...,n}。诸如 a,b 和 c 这样的小写字母代表一个标量，一个加粗的小写字母（如 a,b 和 c）代表一个向量。诸如 A,B 和 C 这样的加粗大写字母，代表一个矩阵或一个张量。A^T 代表 A 的转置。对于向量              以及             ，              代表 a 和 b 的串联。         表示点集 V 和边集 E 组成的对。n 代表节点的数量，m 代表图与上下文无关时边的数量。

对于每个节点 v 来说，N(v) 代表 v 的邻居节点的集合，deg(v) 代表 v 的邻居节点的个数。如果一张图包含节点特征向量             ，图可以被表征为一个元组 G=(V,E,X)。        代表节点 v 在第 l 层中的嵌入（详见公式 2）；             代表第 l 层的聚合函数（详见公式 1）；             代表第 l 层的更新函数（详见公式 2）；             为读出函数（详见公式 3）；             为输入图中度的最大值；b(k) 代表第 k 个贝尔数；H(k) 为第 k 个调和数             。

2、 问题设定

本文重点关注以下的节点分类问题和图分类问题。

1）节点分类问题

输入： 一张图 G=(V，E，X)，其中每个节点 v∈V

输出： v 的标签 y_v

2）图分类问题

输入： 一张图 G=(V，E，X)

输出： 图 G 的标签 y_G

具体来说，我们考虑的是 GNN 可以计算的函数             以及             的类别。因为 GNN 不能对图上所有的函数建模（详见本文后续部分）。

3、图神经网络

再简要介绍标准的 GNN 模型。

1）GNN 发展史

Sperduti 和 Starita 以及 Baskin 于 1997 年首次提出类似于 GNN 的模型。他们使用神经网络从图数据中抽取出特征，而不是使用手动设计的图特征。Sperduti 和 Starita 于 1997 年递归地应用了一种线性聚合操作以及非线性激活函数，而 Baskin 等人则于 1997 年使用了参数共享机制对节点和边特征的不变性变换进行了建模。

这些特性在现代 GNN 中非常普遍。Gori 等人于 2005 年、Scarselli 等人于 2009 年分别提出了新型的图学习模型，它们使用了递归的聚合技术并且将这些模型称为图神经网络。

值得注意的是，在本文中，GNN 不仅仅代表这类模型，GNN 是代表这类模型的后续变体的通用术语。

Li 等人于 2016 年将 Gori 等人（2015）和 Scarselli 等人（2009）的思想扩展到了门控图神经网络上。分子图网络（Merkwirth 和 Lengauer，2005）是一种具有相似架构的图神经网络的并行模型，其层数为一个常数。

Duvenaud 等人于 2015 年构建了一种受圆形指纹启发的 GNN 模型。受核消息传递算法（Song 等人于 2010、2011 年提出）的启发，Dai 等人于 2016 年提出了一种新的 GNN 模型。Gilmer 等人于 2017 年使用消息传递机制提供了一种对 GNN 的统一视角，从而表征 GNN。

在本文中，我们并不考虑  GNN 模型的频域变体（例如 Bruna 等人于 2014年发表的论文「 Spectral networks and locally connected networks on graphs」，以及 Defferrard 等人于 2016 年发表的论文「 Convolutional neural networks on graphs with fast localized spectral fifiltering」），仅仅考虑基于消息传递机制的空域方法。

             

图 1：单层消息传递图神经网络。

             

图 2：双层消息传递图神经网络。

2）消息传递机制

根据消息传递机制，L 层的 GNN 可以被形式化定义如下：

             

 

其中，             和             都是参数化函数。在这里，             可以被看做节点 u 在第 k 个消息传递阶段中的「消息」。每个节点将聚合它们邻居节点的消息，从而计算出下一个消息或嵌入。GNN 基于最终的嵌入             对节点 v 进行分类。

当没有可用的节点特征             时，根据 Xu 等人于 2019 年发表的论文「How powerful are graph neural networks?」以及 Knyazev 等人于 2019 年发表的论文「Understanding attention and generalization in graph neural networks」，我们使用独热的度向量作为初始的嵌入。

图 1 和图 2 对这种方案进行了说明，其中颜色代表特征和嵌入。相同的颜色代表相同的向量。

在本例中，图 1 中的单层 GNN 无法区分出左下角用嵌入 3 表示的节点。这说明这些节点拥有不同的类标签，单层 GNN 往往不能正确对这些节点进行分类，这是因为 GNN 仅仅基于最终的嵌入对接点进行分类。相反，如图 2 所示，双层 GNN 就可以将所有节点区分开来。

除了结构上的限制，一般而言，             和并不一定要是单射函数。例如，             可能是成立的。这就对 GNN 施加了更多的限制。本文旨在确定 GNN 可以/无法识别的图的特性。

在图分类问题中，GNN 使用读出函数计算图嵌入             ：

             

其中，             是一个参数化的函数。GNN 基于图嵌入             对图 G 进行分类。典型的 GNN 模型可以通过如下所示的消息传递框架形式化定义。

GraphSAGE-mean（详见 Hamilton 等人于 2017 年发表的论文「Inductive representation learning on large graphs」）

             

其中             是一个参数矩阵，而σ是一个激活函数（如 sigmoid 和 ReLU）。

图卷积网络（GCN，详见 Kipf 和 Welling 等人于 2017 年发表的论文「Deep models of interactions across sets」）

               

图注意力网络（GAT，详见 Velickovic 等人于 2018 年发表的论文「Weak models of distributed computing, with connections to modal logic」）

               

严格来说，在这些模型中，             并不仅仅是关于             的函数，它还用到了邻居节点的度以及注意力权重这些边信息。然而，这些信息可以被认为被包含在了消息             中。因此，这里使用的数学符号并不会影响这些模型可以计算的函数的类别。

Gilmer 等人于 2017 年发表的论文「Neural message passing for quantum chemistry」介绍了许多其它的消息传递 GNN 的示例。

二、 GNN 无法区分的图

             

图 3：GNN 不能区分上面两种分子，因为它们都是包含 20 个节点的 3-正则图。

本章讨论朴素的 GNN 无法通过基本参数和具体示例区分的图。

K-正则图是一种每个节点都恰好有 k 个邻居节点的图。如图 3 所示，「Decaprismane C_20H_20」和「Dodecahedrane C_20H_20」都是 3-正则图。显然，消息传递 GNN 无法区分具有相同尺寸和节点特征的 k-正则图。

我们在图 4 中说明了这种现象。由于右边的图包含三角形，而左边的图并不包含三角，所以这两个图并不是同构的。然而，左图和右图中所有节点中的所有的消息是相同的。因此，最终通过 GNN 计算得到的所有嵌入都是相同的。这种结果并不尽如人意，因为如果两个正则图（例如，「Decaprismane C_20H_20」和「Dodecahedrane C_20H_20」）有不同的类标签，无论模型参数如何，消息传递 GNN 往往无法区分它们。

除了正则图意外，还有许多非正则、非同构的图是 GNN 无法区分的。图 5 列举出了一些 GNN 无法区分的非正则、非同构的图的示例。图 5(a) 和 (b) 是通过为图 4 中正则图中的节点附上一个「叶子」结点生成的（就像附上一个氢原子一样）。图 5(e) 和 (f) 包含除度特征之外的节点特征，但是 GNN 不能区分它们。

图 6 中的十氢化萘 C_10H_18 和双环戊烷 C_10H_18 是 GNN 无法区分的现实世界中的图，同理图 5(c) 和 (d) 也是 GNN 无法区分的。同样的，这也说明如果两个分子有不同的类标签，无论模型参数如何，GNN 往往无法区分他们。似乎 GNN 无法区分的图是无穷无尽的。

那么，我们能归纳出这类 GNN 无法区分的图的特点吗？下一章将介绍 Xu 等人和 Morris 的研究成果，它们通过「Weisfeiler-Lehman」算法描述了这类图。

             

图 4：消息传递 GNN 并不能将任何一对具有相同的度和尺寸的正则图区分开来（即使他们并不是同构的）。

             

图 5：尽管这些图并不是同构的，但是 GNN 也无法将 a 和 b、c 和 d、e 和 f 区分开来。

             

图 6：GNN 无法将这两种分子区分开来，即使这些图不是同构或正则的。 

三、GNN 与「Weisfeiler-Lehman」算法的联系

在本章中，我们将介绍 GNN 与 Weisfeiler-Lehman 算法之间的联系

1、Weisfeiler-Lehman 算法

图同构问题，是一种确定一对图是否同构的决策问题。

输入：一对图 G=（V，E，X）和 H=（U，F，Y）

输出：确定是否存在一种双射             使得                          且             当且仅当               

若两图同构，则我们认为这两个图相等，GNN 应该输出相同的嵌入。

Weisfeiler-Lehman（WL）算法是一种被用来解决图同构问题的算法。WL 算法有许多种变体：

1）1-维 WL（1-WL）算法（也称「color refinement」）：是最常用的变体，我们有时直接将其称为 WL 算法。该算法为每个节点赋予一种标签（颜色），并不断聚合邻居节点信息、修改节点的标签（颜色），直到标签不再变化（收敛）。

输入： 一对图 G=（V，E，X）和 H=（U，G，Y）

       

其中 HASH 是一种单射哈希函数。如果 1-WL 算法输出「非同构」，那么 G 和 H 就不是同构的图，但即使 1-WL 算法输出「可能同构」，G 和 H 仍有可能非同构。例如，对于图 4 中的图，1-WL 算法将输出「可能同构」，然而它们并非同构。1-WL 算法可以保证在时间复杂度为             的迭代过程之内完成。

2）K-维 WL 算法： 1-维 WL 的推广。k-维 WL 为每 k 个节点组成的元组赋予一种颜色。

输入： 一对图 G=（V，E，X）和 H=（U，F，Y）

           

               

其中，             是第 i 个邻居节点，它使用 G 中的每个节点替换 k 元组中的第 i 个元素。「HASH」是一种单射的哈希函数，它为相同的同构型赋予相同的颜色。换而言之，             当且仅当             ；             当且仅当             ∈             。这种限制对于             和             ，以及             和             同样成立。

3）K-维 folklore WL（k-FWL）算法：是 1 维 WL 算法的另一种推广。

             

其中             。K-WL 和 K-FWL 仍然存在不足。如果 K-WL 和 K-FWL 输出「非同构」，那么 G 和 H 则不是同构图，但即使 K-WL 和 K-FWL 输出「可能同构」，G 和 H 仍然可能不是同构图。

WL 算法的变体的能力具有如下关系：

• 1-WL 与 2-WL 能力相当。换句话说，对于任意一对图，这两种算法的输出相同。

• 对于任意的 k≥2，k-FWL 的能力与 (k+1)-WL 相当。

• 对于任意的 k≥2，(k+1)-WL 一定比 k-WL 能力更强。换句话说，存在一对非同构图（G，H），使得 k-WL 输出「可能同构」，但 (k+1)-WL 输出「非同构」。

 

             

图 7：WL 算法相关变体的层次

研究者们已经大量研究了 WL 算法可以/无法区分的图所具备的性质。值得注意的是：

• 如果两图都是随机抽取的，那么随着图的尺寸趋向与无限大，1-WL 算法失效的概率趋近于 1。

• 当 k≥2 时，存在一对尺寸为 O(k) 的非同构图（G，H），使得 k-WL 的输出为「可能同构」。

• 对任意一对非同构树 S 和 T，1-WL 算法输出 S 和 T 都是「非同构的」。

• 对于任意的正整数     以及一对有 n 个顶点的 k 正则图 G 和 H，1-WL 算法输出的 G 和 H 是「可能同构」 。

• 在准线性时间内，1-WL 算法可以将图与和它非同构图的区分开来。

2、GNN 和 WL 算法之间的联系

本节介绍 GNN 与 WL 算法之间的联系。

定理 1： 对于任意的消息传递 GNN 和任意的图 G 和 H，如果 1-WL 算法输出 G 和 H 是「可能同构」的，那么由 GNN 计算出的嵌入 h_G 和 h_H 是相同的。

换而言之，消息传递 GNN 并没有 1-WL 那样强大。这是因为聚合函数和更新函数可以被看做 1-WL 算法的哈希函数，而聚合函数和更新函数并不一定是单射的。在这种 GNN 和 1-WL 的对应关系的启发下，Xu 等人于 2019 年发表的论文「How powerful are graph neural networks? 」通过使聚合函数和更新函数限制为单射函数，提出了一种与 1-WL 一样强大的 GNN——图同构网络（GIN）：

             

其中，    是一个标量参数，MLP 是一个多层感知机。根据深度多重集理论（GIN 的聚合函数在某些假设下是单射函数），GIN 与 1-WL 一样强大。

定理 2： 对于所有的    ，存在 L 层 GIN 的参数使得：若节点的度以一个常数为上界，且节点特征的支撑集的大小有限，那么对于任意的 G 和 H，如果 1-WL 算法在 L 次迭代内输出 G 和 H 是「非同构」的，则由 GIN 计算出的嵌入 h_G 和 h_H 是不同的。

推论 3： 对于任意的图 G 和 H，如果 1-WL 算法输出 G 和 H 是「非同构」的，那么存在 GIN 的参数使得由 GIN 计算出的嵌入 h_G 和 h_H 是不同的。

由于 1-WL 算法定义了消息传递 GNN 表达能力的上界，GIN 也有时被称为最强大的消息传递 GNN。那么，我们如何才能构建比 1-WL 算法更加强大的 GNN 呢？

Morris 等人于 2019 年基于 k-WL 算法的一种变体提出了一种更为强大的模型。他们用「集合 k-WL」算法替代了「k-WL」算法，从而减小内存开销。

1）「集合 k-WL」算法

令                   为 V 的包含 k 个节点的子集。                 。「集合 k-WL」算法为每个由 k 个节点组成的集合赋予一种颜色。

               

其中，   是一种单射哈希函数，它为由 S 划分的子图赋予一种颜色。集合 3-WL 算法可以区分三角形（1-WL 无法做到这一点）。因此，集合 3-WL 算法可以区分图 5 中的 a 和 b、c 和 d、e 和 f，而 1-WL 算法则无法区分。由于三角形的个数（即聚类系数）在各种网络中有着很重要的作用，所以集合 3-WL 的这种特性是迫切需要的。

然而，集合 3-WL 算法无法区分图 8 中的 a 和 b，因为 3-WL 算法无法将其区分。需要注意的是，集合 k-WL 算法一定弱于 k-WL 算法。例如，3-WL 可以区分图 9 中的 a 和 b（因为 3-WL 可以检测出 4 联通分量的数目），而集合 3-WL 算法无法做到这一点。

Morris 等人于 2019 年基于集合 k-WL 算法提出了 k-维 GNN（k-GNN）。k-GNN 为每 k 个节点组成的集合赋予一种嵌入。

 

2）k-维 GNN（k-GNN）

             

其中，   根据 S 划分的子图赋予一个特征向量。k-GNN 可以被看做在拓展图             上进行操作的消息传递 GNN，此时节点的集合为   ，存在   和    之间的一条边，当且仅当  。k-GNN 与集合 k-WL 算法能力相当。

             

图 8：尽管这些图是非同构的，3-维 WL 算法和 3-GNN 也不能区分 a 和 b。

             

图 9: 3-维 WL 算法可以区分这些图，但是集合 3-维 WL 算法无法做到这一点。

定理 4： Morris 等人于 2019 年提出，对于任意的图 G 和 H，当 k≥2 时，如果集合 k-WL 算法输出 G 和 H 是「非同构」的，那么存在 k-GNN 的参数使得由 k-GNN 计算得到的嵌入 h_G 和 h_H 不同。

k-GNN 需要维护  个嵌入，因此其内存开销相当大。在 Maron 等人 2019 年发表的论文「Provably powerful graph networks」中，他们基于 2-FWL 算法提出了一种与 3-WL 能力相当，但只用维护           个嵌入的 GNN 模型，从而缓解了内存开销的问题。为了介绍该模型，读者需要了解高阶不变和等变 GNN。

3、高阶图神经网络

本章介绍高阶不变和等变 GNN。首先形式化定义不变性和等变性。令     为集合 [n] 上的对称群。

对于一个张量   以及一种排列  ，我们定义   为               。

对于一个张量 以及一种排列  ，我们定义   为       。

定义 5（不变性）： 若对于任意     和    ，    成立，则会函数         是不变的。若对于任意   和     ，     成立，则函数    是不变的。

定义 6（等变性）： 若对于任意   和    ，     成立，则函数      是等变的。若对于任意             和          ，          成立，则        是等变的。

不变性是 l=0 时的等变性的特例。我们可以很自然地想到，图学习模型应该具备不变性和等变性，因为图不会由于任何节点扰动而改变。

Maron 等人推广了 Zaheer、Kondor、Hartford 等人的思想，列举出了所有不变和等变的线性变换。他们发现，不变和等变线性变换的基的大小与维度 n 无关。具体而言，线性不变变换             的基的大小为 b(k)，             的基的大小为 b(k+l)，其中 b(k) 是第 k 个贝尔数（即集合 [k] 的划分的数量）。

定理 7：     构成了线性不变性变换    的一组正交基。

定理 8：      构成了线性等变性变换  的一组正交基。

因此，任意的线性不变和等变变换可以分别通过大小为 b(k) 和 b(k+l) 的基向量的线性组合进行建模。Maron 等人于 2019 年提出使用这种变换作为非消息传递 GNN 的构建模块。Maron 等人通过揭示高阶 GNN 和 高阶 WL 算法之间的关系，并提出了一种新的基于高阶 FWL 算法的高阶 GNN 模型，缓解了参数过多、内存开销过大的问题。首先，Maron 等人说明使用 k 阶张量的高阶 GNN 与 k-WL 的能力相当。

定理 9： 对于任意的图 G 和 H，如果 k-WL 算法输出「非同构」，则存在最多带有 k 阶（ ）张量的高阶 GNN ，使得由高阶 GNN 计算得到的嵌入 h_G 和 h_H 是不同的。

这说明在一般情况下， n 阶张量是充分且必要的。必要性： 存在一对大小为 O(k) 的非同构图，使得 k-WL 算法无法区分。充分性：n-WL 可以区分所大小为 n 的图。

接着，Maron 等人提出了一个与 2-FWL 算法能力相当的 GNN 模型。

定理 10： 对于任意的图 G、H，如果 2-FWL 算法输出「非同构」，存在二阶 folklore GNN 的参数，使得由二阶 folklore GNN 计算得到的嵌入 h_G 和 h_H 是不同的。

4、关系池化

本节将介绍另一种 Murphy 等人于 2019 年在论文「Relational pooling for graph representations」中提出的构建强大的 GNN 的方法。这种思路非常直接，关系池化层取所有可能的排列的平均（如 Jannosy 池化）。

也就是说，令 f 为一种消息传递 GNN，A 为 G=（V，E，X）的邻接矩阵，      为单位矩阵，       为 V 上的对称群。由此，关系池化 GNN（RP-GNN）可以被定义为：

             

换句话说，RP-GNN 串联了节点索引的独热编码和节点特征，然后对所有可能的排列取平均。RP-GNN 的强大之处在于，它在构造上具有明显的排列不变性，比 GIN 和 1-WL 算法更加强大。

定理 11： RP-GNN 比原始的消息传递 GNN  f 更加强大。尤其是当 f 是通过 GIN 建模时，以及图带有离散属性时，RP-GNN 比 1-WL 算法要更加强大。

四、GNN 与组合优化问题的联系

至此，我们已经探讨了图同构问题。本章将讨论其它的组合优化问题，例如：最小顶点覆盖问题、最小支配集问题、最大匹配问题，并通过计算 GNN 的算法效率评估 GNN 的表达能力。具体而言将介绍 GNN 和分布式局部算法（Distributed Local Algorithms）之间的关系。

值得注意的是，在本章中，对于建模组合优化算法而言，GNN 并不一定需要具备不变性或等变性。

1、分布式局部算法

分布式局部算法是在恒定时间内运行的分布式算法。具体而言，一个分布式局部算法解决了计算机网络领域中本身存在的一个问题：每台计算机运行相同的程序，每台计算机与相邻计算机进行一定数量的同步通信后，再决定输出。

例如，假设移动设备与附近的设备组成了一个通信网络。通信网络必须包含中心节点来控制通信，这个中心节点必须形成网络的一个顶点覆盖（即每条边至少被一个中心节点覆盖）。中心节点的数目需要尽可能的小，但是每个移动设备必须要在 5 轮通信之内被声明为中心节点。

那如何才能设计满足要求的算法呢？该问题的示意图如图 10 所示。

             

图 10：分布式局部算法示意图。左：与邻居计算机的通信。右：在一定次数的通信后，每个节点的应答。

目前，已经有多种分布式算法的计算模型。在分布式局部算法的计算模型中，标准计算模型使用端口编号策略。在该模型中，每个节点 v 都有 deg(v) 个端口，每条与 v 关联的边都与其中一个端口相连。只有一条边可以连接到一个端口。在每一轮通信中，每个节点同时向每个端口发送一条消息。

通常，不同的消息被发送到不同的端口。然后，每个节点同时接收消息。每个节点都知道相邻节点提交消息的端口号和消息传来的端口号。每个节点都会基于这些消息计算接下来的消息和状态。在一定轮数的通信之后，每个节点都会基于状态和接收到的信息输出一个应答（例如，声明成为一个中心节点）。这种模型被称为局部模型或矢量一致模型（VV_C（1）模型）。

在这里，（1）代表该模型在一定轮数的通信后会停止运行。Hella 等人研究了一些比 VV_C（1）模型能力弱的模型。多重集广播模型（MB（1））没有使用端口编号策略，但是会将消息发送给所有的邻居节点（即广播）。集合广播（SB（1））模型也没有使用端口编号策略，SB（1）模型以集合形式接受消息，而且不能对重复的消息进行计数。Hella 等人说明，VV_C（1）一定能比 MB（1）处理更广泛的问题，MB（1）一定能比 SB（1）处理更广泛的问题。

2、GNN 与局部算法的联系

本节介绍 Sata 等人在论文「Approximation ratios of graph neural networks for combinatorial problems」中指出的 GNN 和分布式局部算法之间的关系。首先，Sata 等人根据分布式局部算法的计算模型对 GNN 模型进行了分类。

1）MB-GNN

MB-GNN 是标准的消息传递 GNN。它对应于 MB（1） 模型。

 

             

GraphSAGE-mean、GCN、GAT 都是 MB-GNN 的实例。尽管 GAT 的消息是通过注意力加权的，每个节点都会将当前的嵌入广播给所有的邻居节点，每个节点可以计算注意力权值和加权求和结果。因此，GAT 也是 MB-GNN。

2）SB-GNN

SB-GNN 是一类受限的 GNN，它们将嵌入聚合为一个集合。它对应于 SB（1） 模型。

             

GraphSAGE-pool 是 SB-GNN 的一种实例。

3）VV_C-GNN

VV_C-GNN 使用了一种端口编码策略。VV_C-GNN 首先计算一个任意的端口编号 p，然后通过如下所示的方法计算节点的嵌入。             

其中 p(v,u) 是 v 的端口编号，边 {v,u} 与这些端口相连。VV_C-GNN 可以向不同的邻居节点传递不同的消息，而 MB-GNN 总是向所有邻居节点传递相同的消息。VV_C-GNN 和 MB-GNN 如图 11 所示。Sato 等人指出，这些 GNN 模型与其相对应的局部算法的计算模型能力相当。

             

图 11：（a）端口编码的示意图（b）MBGNN 向所有邻居节点传递相同的消息。（c）VV_C-GNN 向邻居节点传递不同的消息。

4）CPN-GNN

CPN-GNN 将邻居节点的嵌入按照端口编码顺序串联起来。

其中，△是输入图的最大度，             是与 v 的第 i 个端口相连的邻居节点，             是科学系的参数。当度数小于 △ 时，CPNGNN 适当地进行补零填充，它是最强大的 VV_C-GNN。

在组合优化问题中，若搜索出的解更接近最优解（即近似比更小），则算法性能越好。为了探究 CPNGNN 在组合优化问题中的性能，可以计算通过 CPNGNN 算法搜索到的解的近似比。在论文「Approximation ratios of graph neural networks for combinatorial problems」中，Sato 等人考虑了以下三种问题：

1）最小顶点覆盖问题

输入： 图 G=（V，E）

输出： 节点集合  ，其尺寸为满足下列性质的最小值：对于任意边  ，u或 v 在 U 中。

2）最小支撑集问题

输入： 图 G=（V，E）

输出： 节点集合   ，其尺寸为满足下列性质的最小值：对于任意的节点   ，节点 v 或者至少一个 v  的邻居节点在 V 中。

3）最大匹配问题

最小支撑集问题

输入： 图 G=（V，E）

输出： 边的集合   ，其尺寸为满足下列性质的最小值：对于任意的节点    ，节点 v 或者至少一个 v  的邻居节点在 V 中。

Sato 等人注意到，添加度特征以外的特征可以减小上述三个问题的近似比。

             

图 12：一种简单的 2-着色问题。每个绿色（0）节点与最少一个红色节点相连，每个红色（1）节点与至少一个绿色节点相连。

具体而言，他们考虑了一个简单的 2-着色问题。一个 2-着色问题是为图中的节点赋予 2 种颜色，使得图中每一个几点至少有一个颜色不同的邻居。图 12 是这种简单的 2-着色问题的示意图。2-着色问题可以在线性时间内通过广度优先搜索（BFS）算法完成计算。Sato 等人指出，将这种简单的 2 着色问题增加到节点特征中可以使 GNN 获取更多关于输入图的信息，并且得到更好的近似比。

3、随机特征增强 GNN

本章介绍的是，将随机特征添加到每个节点中，可以使 GNN 区分更多类别的图，并且建模出更高效的算法。

Sata 等人提出了带有随机特征的 GIN（rGIN）。rGIN 在每次程序被调用时赋予一个随机特征。具体而言，rGIN 获取一个图 G=（V，E，X）作为输入，从一个离散分布 μ 中为每个节点以独立同分布的方式取样得到随机特征  ，并且使用带有随机特征的图    计算节点或图的嵌入，其中    且     。

需要注意的是，尽管 rGIN 在训练和测试时赋予不同的随机特征，但是 rGIN 也可以在测试时泛化到模型没有见过的图上。

             

图 13：（a）当节点特征向同时，消息传递  GNN 无法区分两个三角形和六边形。（b）当具有随机节点特征时，消息传递 GNN 可以区分两个三角形和六边形。

表 2：最小支撑集问题（MDS）和最大匹配问题（MM）的近似比的总结。*代表这些近似比达到了下界。△代表最大度，H(k) 代表第 k 个调和数，      是一个任意的常量，C是一个固定的常量。除常数项外，rGIN 的近似比与多项式算法的最佳近似比相匹配，除无关项外，rGIN 的近似比与多项式算法的最佳近似比相匹配。

               

五、XS 一致性

正如第三章和第四章所提到的，GNN 与 WL 算法和分布式局部算法息息相关。本章将根据 GNN、WL算法、分布式局部算法之间的关系总结 GNN 的表达能力。我们将它们的关系称作「XS 一致性」（根据 Xu 等人和 Sato 等人的名字命名）。

Xu 等人和 Sato 等人的研究结果给出了 GNN、WL 算法以及分布式局部算法的要素之间的一致性。表 3 总结了这种一致性。

表 3：XS 一致性给出了 GNN、WL 算法，以及分布式局部算法的要素之间的具体联系。

               

例如，分布式算法领域也研究了求解组合优化问题所需的通信轮数。Astrand 等人指出，             轮通信足以解决 2-近似问题，其中 △ 是最大度。Babai 等人指出，1-WL 算法在 2 轮迭代之内有很大概率可以确定出一个足够大的随机图。根据 XS 一致性，这样的结论可以被用来设计 GNN 的层数。

此外，WL 算法和分布式局部算法在很多领域内都有联系。例如，k-WL 算法与带有计数量词的一阶逻辑、组合数学中的跳卵石游戏、线性规划、Sherali-Adams 松弛都有联系（这些问题也可以通过组合优化方式求解）。分布式局部算法与模态逻辑、常数时间算法都有关。具体而言：

• 对于任意的 k≥2，存在一个带有计数量词的  k 个变量的一阶逻辑语句   ，使得     且  当且仅当 k-WL 算法输出 G 和 H 是「非同构」的。

• 在游戏    中，玩家 2 在 G 和 H 上有一个获胜策略，当且仅当 k-WL 算法输出 G 和 H是「可能同构」的。

• 令 A 和 B 是 G 和 H 的邻接矩阵。存在双随机实值矩阵 X 使得 AX=XB，当且仅当 1-WL 算法输出 G 和 H 是「可能同构」的。

• 令 A 和 B 是 G 和 H 的邻接矩阵。如果 （k+2）-WL 算法输出  G 和 H 是「可能同构」的，则对于任意的 k≥2，存在 AX=XB 的秩-k Sherali-Adams 松弛的解，使得 X 是双随机的。

• 令 A 和 B 是 G 和 H 的邻接矩阵。只有 （k+1）-WL 算法输出  G 和 H 是「可能同构」的，则对于任意的 k≥2，才存在 AX=XB 的秩-k Sherali-Adams 松弛的解，使得 X 是双随机的。

• 在相应的Kripke模型上，VV_C（1） 模型可以识别梯度多模态逻辑的逻辑公式，而在VV_C（1）模型上，梯度多模态逻辑可以模拟任意算法。

• 一个分布式局部算法可以被转化为一个常量时间算法。

得益于 XS 一致性，我们可以使用该领域的结论推导出许多 GNN 的理论特性。例如，Barcelo 等人利用 WL 算法和一阶逻辑之间的关系构建了更加强大的 GNN。

六、结语

本文中，我们介绍了图神经网络的表达能力。换而言之，我们介绍了消息传递 GNN 的能力最多与一维 WL 算法相当，以及如何将 GNN 推广到 k 维 WL 算法上。

接着，我们介绍了 GNN 和分布式算法之间的联系，指出了 GNN 在 GNN 可以计算的组合优化算法近似比方面的局限性。 雷锋网雷锋网雷锋网

不仅如此，我们还指出了将随机特征添加到每个节点中会显著提升近似比。

最后，我们将 GNN、WL 算法，以及分布式局部算法之间的关系总结为「XS 一致性」。

。