在本文中，作者将讨论如何设计局部的、计算效率高的、可证明的图神经网络，这种网络不是基于 Weisfeiler-Lehman 测试层次结构。本文是图神经网络表达能力系列文章的第二部分。

前文回顾：

《图深度学习：成果、挑战与未来》
《图神经网络的表达能力与 Weisfeiler-Lehman 测试》

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

最近的开创性论文【1】【2】建立了图神经网络和图同构测试之间的联系，并观察了消息传递机制与 Weisfeiler-Lehman（WL）测试之间的相似性【3】。Weisfeiler-Lehman 测试是图论多项式时间迭代算法的层次结构的总称，用于确定图的同构性。k-WL 测试在每一步根据邻域聚集规则对图的顶点的 k 元组进行重新着色，并在着色达到稳定后停止。如果两个图的颜色直方图不同，则认为这两个图不是同构的；否则，这两个图（但不一定）是同构的。

消息传递神经网络最多只能和 1-WL 测试（也称为节点颜色细化）一样强大，因此，即使是非常简单的不同构图实例也无法区分。例如，消息传递神经网络不能计算三角形【4】，这是已知在社交网络中扮演重要角色的模式，它与表示用户“紧密结合”程度的聚类系数有关【5】。设计出表达力更强的图神经网络来复制越来越强大的 k-WL 测试是可以实现的【2】【6】。然而，这样的架构会导致很高的复杂性，并带来大量的参数，但最重要的是，通常需要非局部操作，这使得它们不切实际。

因此，基于 Weisfeiler-Lehman 层次结构的可证明功能强大的图神经网络，要么功能不强但实用，要么功能强大但不切实际【7】。我们在与 Giorgos Bouritsas 和 Fabrizio Frasca【8】的合作的一篇新论文中提出，我认为有一种不同的简单方法可以设计出高效且可证明功能强大的图神经网络。

图子结构网络（Graph Substructure Networks）。这个想法实际上非常简单，在概念上类似于位置编码或图元描述符（graphlet descriptors）【9】：我们使消息传递机制了解局部图结构，允许根据端点节点之间的拓扑关系以不同方式计算消息。这是通过向消息传递函数传递与每个节点【10】相关联的附加结构描述符来实现的，这些描述符是通过子图同构计数构造的。通过这种方式，我们可以将图中的节点划分成不同的等价类，这些等价类反映了每个图中的节点之间以及不同图之间共享的拓扑特征。

我们将这种架构成为图子结构网络（Graph Substructure Network，GSN）。它具有与标准消息传递神经网络相同的算法设计、存储和计算复杂度，并增加了构造结构描述符的预计算步骤。计数子结构的选择对于 GSN 的表达能力和预计算步骤的计算复杂度都是至关重要的。

在具有 n 个节点的图中，对大小为 k 的子结构进行计数的最坏情况复杂度为 𝒪(nᵏ)。因此，它类似于高阶图神经网络模型或 Morris【2】和 Maron【6】。然而，与这些方法相比，GSN 有几个优点。首先，对于某些类型的子结构，例如道路和环，计数的复杂度可以大大降低。其次，计算成本高的步骤作为预处理只做一次，因此不影响保持线性的网络训练和推理，这与消息传递神经网络中的方式相同。训练和推理的记忆复杂度也是线性的。第三，也是最重要的一点，GSN 的表达能力不同于 k-WL 测试，在某些情况下更强。

GSN 有多强大？ 与标准的消息传递网络相比，子结构计数赋予了 GSN 更强的表达能力。首先，必须澄清的是，GSN 的表达能力取决于所使用的图子结构。正如我们有一个 k-WL 测试的层次结构一样，我们可能会有基于对一个或多个结构的技术来获得不同的 GSN 变体。使用比星图更复杂的结构，GSN 可以严格地比 1-WL（或等效的 2-WL）更强大，因此也比标准消息传递架构更强大。对于 4-clique，GSN 的能力至少不低于 3-WL，如下面的强正则图示例所示，其中，GSN 成功，而 3-WL 失败：

具有 16 个顶点和 6 个节点度的非同构强正则图的示例，其中，每两个相邻顶点有两个相邻的邻居，并且每两个不相邻的顶点也有两个相邻的邻居。在本例中，3-WL 测试失败，而 4-clique 结构的 GSN 可以区分它们。在左侧图（称为 Rook 图）中，每个节点恰好参与一个 4-clique。右侧图（Shrikhande 图）具有大小为3的最大团（三角形）。图源【8】。

更一般地说，对于 𝒪(1) 大小的各种子结构，只要它们不能被 3-WL 计数，就存在 GSN 成功切 3-WL 失败的图【11】。虽然我们找不到相反的例子，但原则上他们可能是存在的：这就是为什么我们关于 GSN 的力量的说法是弱形式的，“至少力量不弱”。

这也适用于较大的 k；上图中强正则图的一般化，称为 k-等正则图，是 (k+1)-WL 测试失败的实例【12】。这些示例也可以通过具有适当结构的 GSN 来区分。因此，GSN 的表达能力可以通过下图来体现：

原则上来说，GNS 能有多强大？这仍然是一个悬而未决的问题。图重构猜想【13】假设了从所有节点删除的子结构中恢复图的可能性。因此，如果重构猜想是正确的，那么具有大小为 n-1 的子结构的 GSN 将能够正确地测试任何图的同构。n-1 将能够正确的测试任何图的同构。然而，重构猜想目前只能证明大小为 n≤11 的图，其次，如此大的结构是不切实际的。

更有趣的问题是，对于“小”结构（𝒪(1) 大小与节点数 n 无关）是否存在类似的结果。我们的经验结果表明，具有小子结构（如环、道路和团）的 GSN 对强正则图有效，而强正则图是 Weisfeiler-Lehman 测试的一个难题。

最重要的是，GSN 构建在标准消息传递架构之上，因此继承了其局部性和线性复杂性。该方法的超参数包括为构造结构描述符而计数的结构。实际应用很可能会以所需的表达力、能保证表达力的结构大小和计算的复杂性之间的权衡为指导。

在我们的实验中，我们观察到不同的问题和数据集受益于不同的子结构，因此，这种选择很可能是特定于问题的。幸运的是，我们经常知道那些子结构在某些应用程序中很重要。例如，在社交网络中，三角形和高阶的团很常见，并且有一个明确的“社会学”解释。在化学中，环是一种非常常见的模式，例如，在大量有机分子中出现的五元芳环和六元芳环。下图显示了一个我们大多数人都熟悉的例子：咖啡因分子，它在我们血液中的含量低得惊人。现在听起来是写完这篇文章，给自己沏一杯咖啡的好时机。

参考文献

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

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

【3】《图的标准型化简及其代数》（The reduction of a graph to canonical form and the algebra which appears therein)，B. Weisfeiler、A. Lehman，1968 年，英译本。

【4】因此，两个三角形数量不同的图，将被 1-WL 测试认为可能是同构的，或者等价于一个消息传递神经网络所构造的相同嵌入。已经有实质性的新结果扩展了我们对什么结构在 Weisfeiler-Lehman 测试下是不变的理解，例如，《关于 Weisfeiler-Lehman 不变性：子图计数及相关图性质》（On Weisfeiler-Leman invariance: subgraph counts and related graph properties），V. Arvind 等人，2018 年，arXiv:1811.04801。以及《图神经网络能对子结构进行计数吗？》（Can graph neural networks count substructures?），Z. Chen 等人，2020 年，arXiv:2002.04025。

【5】图子结构在复杂网络中的应用已有十几年的历史。在生物信息学方面的开创性论文有：《网络模式：复杂网络的简单构建构建块》（Network motifs: simple building blocks of complex networks），R. Milo 等人，2002 年，Science 298 (5594):824–827。以及《交互式建模：无尺度还是几何？》（Modeling Interactome: Scale-free or geometric?），N. Pržulj 等人，2004 年，Bioinformatics 20(18):3508–3515，该论文介绍了用于生物相互作用网络分析的图模式和图元。在这叫网络中，对三角形模式的研究至少可以追溯到《社交网络中的局部结构》（Local structure in social networks），P. W. Holladn 和 S. Leinhardt，1976 年， Sociol. Methodol. 1–45。

【6】《可证明功能强大的图神经网络》（Provably powerful graph neural networks），H. Maron 等人，2019 年，Proc. NeurIPS。

【7】 Morris 的 3-WL 等价图神经网络结构具有 𝒪(n³) 空间复杂度和 𝒪(n⁴) 时间复杂度。Maron 的架构具有稍微好一些的 𝒪(n²) 空间复杂度和 𝒪(n³) 时间复杂度。对于一个只有 1M 节点的中等大小的图来说，这仍然可以转化为巨大的 1TB 内存和百万万亿次计算。

【8】《利用子图同构计数提高图神经网络的表达能力》（Improving graph neural network expressivity via subgraph isomorphism counting），G. Bouritsas 等人，2020 年，arXiv:2006.09252。

【9】基于子结构计数的图分析方法显然遭遇最近关于图深度学习的研究工作。值得注意的例子包括 T. Milenkoviæ 和 N. Pržulj 于 2008 年在 Cancer Inform. 6:257–273 发表的论文《利用图元度签名揭示生物网络功能》（Uncovering biological network function via graphlet degree signatures）中提出的生物信息学中的图元签名。或图元核（graphlet kernels），《用于大型图比较的高效图元核》（Efficient graphlet kernels for large graph comparison），N. Shervashidze 等人，2009 年，Proc. AISTATS。

【10】我们也展示了用于边的相同机制，为简洁起见，我省略了这些。

【11】 3-WL 的子结构计数方面似乎相当薄弱。例如，它可以计算多大 7 个节点的模式环，但不能计算有道的 4 个环或长度为 4 的道路。目前尚不清楚通过在 WL 层次结构中向上可获得什么样的子结构计数能力。

【12】《Weisfeiler-Lehman 方法和图同构测试》（The Weisfeiler-Lehman method and graph isomorphism testing），B. L. Douglas，2011 年，arXiv:1101.5211。请注意，在不同的参考文献所称的“k-WL”之间存有一定程度的混淆。Douglas 使用 k-WL 这一术语来报时其他人所说的 (k-1)-FWL（“民间”WL）。在我们的术语中，k-WL 在（k-1）等正则图上失败。强正则图是 2-等正则图。

【13】《树的同余定理》（A congruence theorem for trees），P. J. Kelly，1957 年， Pacific J. Math. 7:961–968。

【14】《小图是可重构的》（Small graphs are reconstructible），B. D. McKay，1997 年，Australasian J. Combinatorics 15:123–126。

作者介绍：

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

原文链接：

https://towardsdatascience.com/beyond-weisfeiler-lehman-using-substructures-for-provably-expressive-graph-neural-networks-d476ad665fa3

创作场景

如何设计局部的、计算效率高的、可证明的图神经网络？