江苏龙网

  1. 首页 > 资讯 > 科技 > >

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


本文插图


具有 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 。


推荐阅读


上一篇：中年|电动车越严管越受车主排斥，这说明了什么？看看是不是这些原因

下一篇：互联网|无债一身轻，贾跃亭这一次真要回国了吗？