通过重新思考 folklore Weisfeiler-Lehman 扩展图神经网络的设计空间

消息传递神经网络（MPNNs）近年来已成为图神经网络（GNNs）中最流行的框架。然而，它们的表达能力受到一维 Weisfeiler-Lehman（1-WL）测试的限制。一些研究工作受到 $k$-WL/FWL（Folklore WL）的启发，设计了相应的神经版本。尽管这些方法具有较高的表达能力，但存在严重的局限性。具体而言，(1) $k$-WL/FWL 至少需要 $O(n^k)$ 的空间复杂度，这在 $k=3$ 时对于大型图来说也是不切实际的；(2) $k$-WL/FWL 的设计空间较为僵化，唯一的可调超参数是 $k$。为了解决第一个局限性，我们提出了一种扩展方法 $(k,t)$-FWL。我们从理论上证明，即使在 $(k,t)$-FWL 中将空间复杂度固定为 $O(n^k)$（对任何 $k \geq 2$），也可以构建一个表达层次结构，直至解决图同构问题。为了应对第二个问题，我们提出了 $k$-FWL+ 方法，该方法考虑任何等变集作为邻居而不是所有节点，从而大大扩展了 $k$-FWL 的设计空间。结合这两种改进，我们得到了一个灵活且强大的框架 $(k,t)$-FWL+。我们展示了 $(k,t)$-FWL+ 可以实现大多数现有模型，并且其表达能力相当。然后，我们介绍了一个名为 Neighborhood$^2$-FWL（N$^2$-FWL）的 $(k,t)$-FWL+ 实例，该实例在实践和理论上都是合理的。我们证明了 N$^2$-FWL 的表达能力不低于 3-WL，并且可以在仅需 $O(n^2)$ 空间的情况下编码许多子结构。最后，我们设计了其神经版本 N$^2$-GNN，并对其在各种任务上的性能进行了评估。N$^2$-GNN 在 ZINC 子集上取得了破纪录的结果（0.059），比之前的最先进结果提高了 10.6%。此外，在所有现有的高表达力 GNN 方法中，N$^2$-GNN 在 BREC 数据集上也取得了新的最先进结果（71.8%）。