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