你有没有这样的一种感觉，图深度学习就是一堆启发式的东西，有时会起作用，但没有人知道为什么。在本文中，作者讨论了图同构问题，图同构测试的 Weisfeiler-Lehman 启发式，以及如何用它来分析图神经网络的表达能力。这是关于图神经网络表达能力的系列三篇文章中的第一篇。在第二部分中，他将讨论如何脱离 Weisfeiler-Lehman 层次结构；在第三部分中，他将建议为什么重温整个图同构框架可能是个好主意。

本文最初发表在 TowardsDataScience 博客，经原作者 Michael Bronstein 授权，InfoQ 中文站翻译并分享。

前文回顾：《图深度学习：成果、挑战与未来》

传统的前馈网络（多层感知器）是已知的通用逼近器：它们可以将任何平滑函数近似到任何所需的精度。对于相对最近才出现的图神经网络，其表示特性还不是很了解。人们在实验中经常会观察到，图神经网络在某些数据集上表现出色，但同时在其他数据集上的表现却令人失望。为找到这种行为的根源，我们必须回答这样一个问题：图神经网络有多强大？

其中挑战之一是，应用程序中遇到的图是乱序和离散结构（分别是节点和边缘特征以及连通性）的组合，因此，这个问题可以用不同的方式提出。一种可能的表述是图神经网络是否能够区分不同类型的图结构。这是图论中的一个经典问题，称为图同构问题，目的是确定两个图在拓扑上是否等价【1】。两个同构图具有相同的连通性，不同之处只是它们节点的排列。

令人惊讶的是，图同构问题的精确复杂度类别是未知的。我们不知道它在多项式时间内是可解的，也不知道它是 NP 完全（ NP-complete）的，有时被归因于一种特殊的“GI 类”【2】

Weisfeiler-Lehman 测试。Boris Weisfeiler 和 Andrey Lehman【3】在 1968 年发表的具有开创性意义的论文中提出了一种有效的启发式方法，即 Weisfeiler-Lehman 测试。最初被认为是图同构问题的多项式时间解【4】。一年后发现了一个反例；然而，从概率意义上看，Weisfeiler-Lehman 测试似乎适用于几乎所有的图【5】。

对两个同构图上执行 Weisfeiler-Lehman 测试的示例。花括号表示多组。算法在颜色不变后停止，并生成输出（颜色直方图）。这两个图的输入相等表明它们可能是同构的。

Weisfeiler-Lehman 测试基于迭代图重新着色【6】（图论中的“颜色”是指一个离散节点标签），并从所有颜色相同的节点开始。在每一步中，该算法将节点及其邻域的颜色聚合为多集【7】，并将聚合的颜色多集散列为唯一的新颜色。当达到稳定的着色时，算法即停止。如果在这一点上两个图的着色不同，则认为这两个图是非同构的。但是，如果着色是相同的，这些图可能（但不一定）是同构的。换句话说，Weisfeiler-Lehman 测试是图同构的一个必要但不充分的条件。有一些非同构图的 Weifeiler-Lehman 测试可以产生相同的着色，因此认为它们“可能是同构的”；据说在这种情况下，测试失败了。下图就显示了一个这样的例子：

Weisfeiler-Lehman 图同构测试失败的两个非同构图，从它产生的相同着色可以明显看出。在化学中，这些图代表两种不同化合物的分子结构，十氢化萘（左）和双环戊基（右）。图摘自【14】。

图同构网络。Keyulu Xu【9】和 Christopher Morris【10】（至少在两年前，Thomas Kipf 在他的博客中曾提到）注意到，Weisfeiler-Lehman 测试与图消息传递神经网络【8】有着惊人的相似之处，后者是一种对图进行类似卷积运算的方式。在消息传递层中，通过聚合相邻节点的特征来更新每个节点的特征。聚合和更新操作的选择至关重要：只有多集内射函数才能使其等同于 Weisfeiler-Lehman 算法。一些文献中常用的聚合器选择，例如，最大值或均值，实际上严格来说没有 Weisfeiler-Lehman 强大，并且无法区分非常简单的图结构：

图结构的示例，不能用最大值来区分，但可以用均值聚合器（第一和第二）来区分，并且既不能用最大值也不能用均值（第一和第三）来区分。原因在于，以这种方式从黑色节点的邻居聚合的特征将是相同的。图改编自【9】。

Xu 提出了一种聚合和更新函数的选择，使消息传递神经网络与 Weisfeiler-Lehman 算法等价，称之为图同构网络（Graph Isomorphism Networks，GIN）。这和标准的消息传递神经网络一样强大。但是，比起一个新的架构，主要的影响是在一个简单的设置中系形成表达能力的问题，这可能与图论中的一个景点问题有关。这一想法已经激发了许多后续研究。

Weisfeiler-Lehman 层次结构。对 Xu 和 Morris 的结果进行扩展的一个方向是使用更强大的图同构测试。由 László Baba 提出的 k-WL 测试是 Weisfeiler-Lehman 算法的高阶扩展，该算法适用于 k 元组而不是单个节点。除了等价的 1-WL 和 2-WL 测试之外，对于任何 k≥2，(k+1)-WL 严格强于 k-WL，即存在 k-WL 失败而 (k+1)-WL 成功的图的例子，但反之则不然。因此，k-WL 是一个层次结构或越来越强大的图同构测试，有时被称为 Weisfeiler-Lehman 层次结构【10】。

设计遵循 k-WL 测试的图神经网络是可能的，因此严格来说，比消息传递架构更强大。其中一个这样的第一个架构，k-GNN，是由 Morris【11】提出的。传统消息传递神经网络和高阶 GNN 之间的关键区别在于它们是非局部的，因为 k-WL 算法是在节点的 k 元组上进行操作的。这对算法的实现及其计算和内存复杂性都有重要的影响：k-GNN 需要 𝒪(nᵏ) 内存。作为一种降低复杂性的方法，Morris 设计了一种基于局部邻域聚集的 k-GNN 局部版本，但它的表现能力不如 k-WL。

在 2019 年 9 月，我有幸参与了 Haggai Maron 在魏茨曼科学研究学院（Weizmann Institute）的博士论文答辩，他提出了略有不同的高阶图架构。Maron 基于 k 阶张量【12】定义了一类不变图网络（Invariant Graph Network，IGN），并证明了它们与 k-WL 一样强大。IGN 源自 k-WL 的不同变体【10】，并且就其复杂性而言，与 k-GNN 相比更有优势。尤其是，等价于 3-WL 的 IGN“只有”二次元的复杂度，这可能是唯一一种实用的图神经网络架构，严格的说，它比消息传递更强大，但与前者的线性复杂度仍相去甚远【16】。

从理论的角度来看，可证明功能强大的图神经网络提供了一个严格的数学框架，可以帮助解释和比较不同的算法。已经有很多后续工作使用图论和分布式局部算法的方法扩展了这些结果【14】。

然而，从实践的角度来看，这些新的架构几乎没有什么重大影响：例如，最新的基准测试【15】表明，最近被证明功能强大的算法实际上性能并不如旧的技术。这在机器学习中并不少见，因为理论和实践之间往往存在很大差距。其中一个解释可能是基准本身的缺陷。但也许更为深刻的原因是，更好的表达能力并不一定提供更好的泛化（有时恰恰相反），此外，图同构模型可能无法正确地捕捉特定应用程序中图相似性的实际概念，我想在下一篇文章中讨论这一点。可以肯定的是，这一领域的研究工作是卓有成效的，它为其他学科搭建了桥梁，并带来了以前在图深度学习领域未使用过的方法。

参考文献

【1】即在两个图的节点之间存在一个保边双射（edge-preserving bijection）。

【2】因此，图同构可能是NP-中间复杂度类。对于一些特殊的图族（如树、平面图或有界最大度图），存在多项式时间算法。

【3】《图的标准型化简及其代数》（The reduction of a graph to canonical form and the algebra which appears therein），B. Weisfeiler、A. Lehman，1968 年，Nauchno-Technicheskaya Informatsia 2(9):12–16。英文版、俄文版：文中包含了一个双关语，以一种不寻常的西里尔字母（Операция „Ы“）的形式出现，指的是三年前前苏联的同名电影。另请参阅这篇博文中一个流行的论述。Lehman 有时也被拼写成“Leman”，然而，鉴于这个姓氏的日耳曼起源，我更喜欢前者更准确的变体。

【4】 I. Ponomarenko，Weisfeiler Lehman 写的原始论文。提供了这篇经典论文的历史背景。他指出，这项研究的动机来自于化学应用。

【5】《随机图同构》（Random graph isomorphism），L. Babai 等人，1980 年，SIAM J. Computing 9(3):628–635。

【6】 Weisfeiler 和 Lehman 的原始论文实际上描述了 2-WL 变体，但它等价于 1-WL，也被称为色彩细化算法。作为一个历史性的注释，这样的算法早在 20 世纪计算化学中就已为人所知，参见 H.L.Morgan。《为化学结构生成独特的机器描述——化学文摘社（Chemical Abstracts Service，CAS）开发的一种技术》（The generation of a unique machine description for chemical structures — a technique developed at chemical abstracts service ），1965 年， J. Chem，Doc. 5(2):107–113，这是摩根分子指纹在化学中广泛应用的基础。

【7】多集是一个集合，其中，同一个元素可能出现多次，但元素的顺序并不重要。

【8】《量子化学中的神经信息传递》（Neural message passing for quantum chemistry），Gilmer 等人，2017 年，Proc. ICML。

【9】《图神经网络有多强大？》（How powerful are graph neural networks?），K. Xu 等人，2019 年，Proc. ICLR。

【10】 Weisfeiler-Lehman 测试存在多重变体，它们具有不同的计算和理论特性，而且属于相当混乱：建议读者清楚地理解不同作者对“k-WL”一词的确切含义。有些作者，路 Sato 和 Maron，就区分了 WL 和“民俗”WL（FWL）测试，这两种测试的主要不同之处在于色彩细化步骤。k-FWL 测试等价于(k+1)-WL。Morris 使用的集合 k-WL 算法是另一种变体，具有较低的内存复杂度，但严格弱于 k-WL 算法。

【11】《Weisfeiler 和 Leman Go 神经网络：高阶图神经网络》（Weisfeiler and Leman go neural: Higher-order graph neural networks），C. Morris 等人，2019 年，Proc. AAAI。

【12】《不变图网络和等变图网络》（Invariant and equivariant graph networks），H. Maron，2019 年，Proc. ICLR.

【13】《可证明功能强大的图神经网络》（Provably powerful graph neural networks），H. Maron 等人，Proc. NeurIPS。另请参阅作者的博文。

【14】《图神经网络表达能力研究综述》（A survey on the expressive power of graph neural networks），R. Sato，2020 年，arXiv: 2003.04078。提供了有关不同 Weisfeiler-Lehman 测试和等价图神经网络结构的一个非常全面的回顾，并提供了与分布式计算算法的链接。

【15】《基准图神经网络》（Benchmarking graph neural networks），V. P. Dwivedi 等人，2020 年，arXiv: 2003.00982。

【16】更准确地说，消息传递的复杂性与边数呈线性关系，而不是与节点数呈线性关系。在稀疏图中，情况大致相同。在稠密图中，边数可以是 𝒪(n²)。出于这一原因，Maron 认为他的架构可以用于稠密图。

【17】从历史上讲，Weisfeiler-Lehman 的形式主义在机器学习社区中并不新鲜。《图的快速子树核》（Fast subtree kernels on graphs），N. Shervashidze 和 K. M. Borgwardt 合著的开创性论文，2009 年，Proc. NIPS，就我所知，在深度神经网络的复苏之前，该论文是第一个使用这种架构的，比本文所讨论的工作早了近十年。

作者介绍：

Michael Bronstein，伦敦帝国理工学院教授，Twitter 图机器学习研究负责人，CETI 项目机器学习领导、Twitter 图机器学习负责人、研究员、教师、企业家和投资者。

原文链接：

https://towardsdatascience.com/expressive-power-of-graph-neural-networks-and-the-weisefeiler-lehman-test-b883db3c7c49

创作场景

图神经网络的表达能力与 Weisfeiler-Lehman 测试