TL；DR：在这篇文章中，我讨论了如何设计局部的、计算效率高的、可证明强大的、不基于Weisfeiler-Lehman测试层次结构的图神经网络。这是关于图形神经网络表达能力的系列文章中的第二篇。

---

---

最近的突破性论文^[1–2]建立了图神经网络与图同构检验的联系，观察了信息传递机制与Weisfeiler-Lehman（WL）检验的相似性^[3]. WL检验是确定图同构的一系列图论多项式时间迭代算法的总称。这个k公司-WL试验k公司-图的顶点的元组在每一步根据邻域聚合规则进行聚集，并在达到稳定着色时停止。如果两个图的颜色直方图不同，则认为这两个图不同构；否则，这两个图可能（但不一定）同构。

消息传递神经网络的功能最多与1-WL测试（也称为节点颜色细化）一样强大，因此即使是非常简单的非同构图实例也无法区分。例如，消息传递神经网络不能计算三角形^[4]，一个已知在社交网络中扮演重要角色的基序，在社交网络中，它与表示用户“紧密联系”程度的聚类系数相关联^[5]. 有可能设计出更具表现力的图形神经网络来复制越来越强大的功能k公司-WL试验^[2,6].然而，这种架构导致高复杂性和大量参数，但最重要的是，通常需要非本地操作，使它们不切实际。

---

因此，基于Weisfeiler-Lehman层次结构的可证明强大的图神经网络不是非常强大但实用，就是强大但不切实际^[7].我认为，设计有效和可剥夺强大的图形神经网络存在不同的简单方法，我们用Giorgos Bouritsas和Fabrizio Frasca建议^[8].

图形子结构网络

这个想法其实非常简单，概念上与位置编码或Graphlet描述符^[9]：我们使消息传递机制意识到本地图形结构，允许根据端点节点之间的拓扑关系来不同地计算消息。这是通过传递给传递与每个节点相关联的附加结构描述符的消息来完成的^[10]，通过子图同构计数构造。通过这种方法，我们可以将图中的节点划分为不同的等价类，这些等价类反映了每个图中的节点之间以及不同图之间共享的拓扑特征。

我们调用此架构图形子结构网络（GSN）。它具有与通过神经网络的标准消息相同的算法设计和存储器和计算复杂度，其中构建了结构描述符的附加预计算步骤。对计数的副结构的选择对于GSN的表现力以及预计算步骤的计算复杂性至关重要。

计算大小子结构的最坏情况复杂性k公司在具有不节点是O(nᵏ）。因此，它类似于高阶图形神经网络模型或莫里斯^[2]和制造商^[6]. 然而，GSN比这些方法有一些优点。首先，对于某些类型的子结构，例如路径和循环，可以以显著较低的复杂度进行计数。第二，计算昂贵的步骤只做一次预处理，因此不影响保持线性的网络训练和推理，与消息传递神经网络中的方法相同。训练和推理的记忆复杂度也是线性的。第三，也是最重要的一点，GSN的表现力不同于其他语言k公司-WL测试，在某些情况下更强。

GSN有多强大？

计数计数的子结构与标准消息传递神经网络具有比标准消息传递更具表现力的功率赋予GSN。首先，重要的是澄清GSN的表现力取决于所使用的图形子结构。与我们有一个层次的方式一样k公司-在WL测试中，我们可能会根据一个或多个结构的计数得到不同的GSN变体。使用比星形图更复杂的结构，gsn可以严格地比1-WL（或等效的2-WL）更强大，因此也比标准的消息传递体系结构更强大。对于4-团，GSN至少不比3-WL弱，如下面的强正则图示例所示，GSN成功而3-WL失败：

---

更一般地说，对于O（1） 大小，只要它们不能被3-WL计数，就存在GSN成功而3-WL失败的图^[11]. 虽然我们找不到相反的例子，但它们原则上可能存在——这就是为什么我们关于GSN力量的陈述是一种弱形式，“至少不弱”。

这适用于较大的k公司上图中强正则图的一个推广，称为k公司-等规，是(k公司+1）-wl测试失败^[12]. 这些例子也可以通过具有适当结构的GSN来区分。因此，GSN的表现力可以通过下图来体现：

---

GSN原则上有多强大？这仍然是一个悬而未决的问题。这个图重构猜想^[13]假定有可能从图的所有删除节点的子结构中恢复图。因此，如果重建猜想是正确的，那么具有大小子结构的GSN不−1将能够正确测试任何图的同构。然而，重构猜想目前仅被证明适用于大小图n≤11^[14]第二，这样的大型建筑是不切实际的。

更有趣的问题是，对于“小”结构（例如O（1） 大小与节点数无关不). 我们的实验结果表明，GSN具有较小的子结构，例如周期,路径，和派系为强烈普通的图表工作，已知是Weisfeiler-Lehman测试的坚固螺母。

最重要的是，GSN构建在标准消息传递体系结构之上，从而继承其局部性和线性复杂性。该方法的超参数包括计数用于结构描述符的结构。实际应用可能将在所需的表现力，可以保证它的结构的大小和计算它们的复杂性之间的权衡指导。

---

在我们的实验中，我们观察到不同的问题和数据集受益于不同的子结构，因此这种选择很可能是针对具体问题的。幸运的是，在某些应用程序中，我们经常知道子结构的重要性。例如，在社交网络中，三角形和高阶派系很常见，并有明确的“社会学”解释。在化学中，循环是一种非常频繁的模式，例如5-和6-成员芳香环出现在大量有机分子中。下图显示了一个我们大多数人都熟悉的例子，即咖啡因在我的血液中的含量低得惊人。这听起来是完成这篇文章，给自己冲杯咖啡的好时机。

---

注释和参考文献

[1] K.Xu等。图形神经网络有多强大？（2019）。Proc。ICLR。

[2] C.Morris等人。Weisfeiler和Leman-go神经网络：高阶图神经网络（2019）。Proc。Aaai。

[3] B.Weisfeiler，A.Lehman，将图形的减少到规范形式和出现在其中的代数，1968（英译）

[4] 因此，具有不同三角形数的两个图可能被1-WL测试认为是同构的，或者等效地，将具有由消息传递神经网络构造的相同嵌入。有大量的新结果扩展了我们对WL测试下什么样的结构是不变的的的理解，见V.Arvind等人。关于Weisfeiler-Leman Invariance：子图计数和相关图形属性(2018) arXiv:1811.04801和Z、 Chen等人。图神经网络能计算子结构吗？(2020) 附件十四：2002.04025。

[5] 图子结构在复杂网络中的应用已有几十年的历史。在生物信息学中，R.Milo等人的开创性论文《网络基序：复杂网络的简单构建块》（2002）。科学298（5594）：824–827。和N.Pržulj等人。建模互联术：无垢或几何？（2004）生物信息学20（18）：3508–3515介绍了用于分析生物相互作用网络的图形基序和图形。在社交网络中，对三角母题的研究至少可以追溯到P.W.Holland和S.Leinhardt的《社交网络中的局部结构》（1976）。社会学家。方法。1–45.

[6] H.Maron等人。可证强图神经网络(2019). 过程。神经突。

[7]莫里斯的3-WL同等图形神经网络架构具有O(不（3）空间——和O(不⁴）时间复杂性。马龙的建筑风格稍好一些O(不²）空间-和O(不（3）时间复杂性。对于一个有1M个节点的中等大小的图，这仍然转化为巨大的1TB内存和exaflop计算。

[8] G.Bouritsas等人。通过子图同样计数提高图形神经网络的表征（2020）。arxiv：2006.09252。

[9]基于子结构计数的图分析方法显然预测了近期图形深度学习的作品。值得注意的实例包括在T.Milenkoviæ和N.Pržulj中的生物信息学中提出的石墨符号，利用graphlet度特征揭示生物网络功能(2008). 癌症报告。6： 257–273，或graphlet kernels N.Shervashidze等人。用于大图比较的高效graphlet核(2009). 过程。艾斯塔斯。

[10] 我们也展示了同样的边机制，为了简洁起见，我在这里省略了它。

[11] 3-WL在亚结构计数方面显得相当弱。例如，它可以计算多达7个节点的基序周期，但无法计算诱导的4个周期或长度为4的路径。目前尚不清楚通过在WL层次结构中上升获得了什么子结构计数能力。

[12] B.L.道格拉斯，Weisfeiler-Lehman方法和图形同构测试(2011). 附件十四：1101.5211。请注意，不同的参考文献所称的“信息”之间存在一定程度的混淆k公司-WL”。道格拉斯用这个词k公司-其他人怎么说(k公司−1）-FWL（“民俗”WL）。用我们的术语来说，k公司-WL在上失败(k公司-1）-1Sooregular图表。强烈的常规图是2-Isoregular。

[13] P.J.凯利，树的同余定理(1957). 太平洋数学杂志。7:961–968.

[14] B.D.McKay，小图是可重构的（1997）。澳大利亚组合学杂志15:123-126。

致谢

我非常感谢卢卡·贝利、乔治·布里萨斯和法布里齐奥·弗拉斯卡在校对这篇文章时给予的帮助。看到了吗其他帖子关于图形深度学习。

这篇文章最初发表了关于数据科学的。