HyperAIHyperAI

Command Palette

Search for a command to run...

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

Jiarui Feng; Lecheng Kong; Hao Liu; Dacheng Tao; Fuhai Li; Muhan Zhang; Yixin Chen

摘要

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


用 AI 构建 AI

从创意到上线——通过免费 AI 协同编码、开箱即用的环境和最优惠的 GPU 价格,加速您的 AI 开发。

AI 协同编码
开箱即用的 GPU
最优定价

HyperAI Newsletters

订阅我们的最新资讯
我们会在北京时间 每周一的上午九点 向您的邮箱投递本周内的最新更新
邮件发送服务由 MailChimp 提供