通过重新思考 Weisfeiler-Lehman 传说走向在 $O (n^2)$ 空间内任意表达的 GNNs

Jun, 2023

通过重新思考 Weisfeiler-Lehman 传说走向在 $O (n^2)$ 空间内任意表达的 GNNs

Towards Arbitrarily Expressive GNNs in $O(n^2)$ Space by Rethinking Folklore Weisfeiler-Lehman

Jiarui Feng, Lecheng Kong, Hao Liu, Dacheng Tao, Fuhai Li...

TL;DR本文提出了一种新的图神经网络的框架 $k$-FWL+，并探究其表达能力及其设计空间的灵活性，使用此框架设计的 N2-GNN 在 ZINC-Subset 和 ZINC-Full 两个数据集上显示了比之前最先进的结果更好的性能。

Abstract

message passing neural networks (MPNNs) have emerged as the most popular framework of graph neural networks (GNNs) in recent years. However, their expressive power is limited by the 1-dimensional Weisfeiler-Lehma

message passing neural networks graph neural networks k-fwl+expressiveness n2-gnn

发现论文，激发创造

邻居间通信：面向强大和可扩展的图神经网络

提出了一种基于 1-WL 和邻居之间的边缘考虑的 NC-1-WL 算法，实现了图同构测试，提高了图神经网络的可表达性；进一步提出了 NC-GNN 框架作为 NC-1-WL 的可微分神经版本，能够在各种基准测试中实现出色的性能。

Jun, 2022

可证明强大图网络

本文探讨了图同构、图神经网络的表达能力及其应用。作者提出了 k - 阶不变 / 本质等变图神经网络，并将此网络应用于图分类的任务中。实验表明，模型在数据集上表现的优异，证明了本文所提出的模型是有实用价值的。

May, 2019

图神经网络的细粒度表达能力

该研究探讨了基于图神经网络的表达能力，提出了一种连续化的方法来反映图之间的相似程度并给出了各种拓扑特征的理论框架来描述基于树距离的图表达能力。

Jun, 2023

突破消息传递图神经网络的限制

本文研究了基于图传递的神经网络（MPNNs），通过在频域设计非线性的自定义滤波器函数并使用任意大的感受野进行掩膜，其理论上比 1-WL 测试显得更加强大，且实际上具有与现有 3-WL 模型同样的性能，同时仍保持局部化。通过本方法可以实现 LOD 更新机制和输出谱复杂性，从而在许多下游任务中达到先进水平。

Jun, 2021

关于几何图神经网络表达能力的研究

本研究提出了符合物理对称性的几何图卷积神经网络测试 GWL，并使用 GWL 研究了符合物理对称性的几何图卷积神经网络的表达能力，发现等变层扩展了局部邻域之外的几何信息，高阶张量和标量化使几何图卷积神经网络具有最大的表达能力。

Jan, 2023

边缘上的 Weisfeiler-Leman：当更多的表达能力很重要

增强 Weisfeiler-Leman 算法和消息传递图神经网络的表达力的关系对于改进概括能力的条件是不明确的。通过引入子图信息和经典边界理论来探索这种表达力增强和概括能力改善的条件，并提出具有可证明概括性质的基于 $1$-WL 的核和消息传递图神经网络架构的变体。

Feb, 2024

Weisfeiler 和 Leman 进化为神经网络：高阶图神经网络

本文研究了图神经网络以及其理论背景并将其与 $1$-WL 算法相对比，提出了 $k$-dimensional GNNs 这一扩展方法，证明了它在处理社交网络和分子图像等高阶结构方面的有效性。

Oct, 2018

图神经网络的表达能力和逼近性质

使用张量语言以及 Weisfeiler-Leman 测试为模型分析提供了一种优雅的方法，通过索引和求和嵌套深度的简单分析得到了对 GNN 的分离能力的边界和某些类的普适性结果，并提供了一些提高 GNN 分离能力的见解。

Apr, 2022

利用本地化提高图神经网络的表达能力

本文提出局部 Weisfeiler-Leman（WL）算法以提高表达能力和降低计算复杂度，并解决所有 k 的局部 k-WL 的子图计数问题。研究证明，本地 k-WL 可以表达更多模式，但在表达能力上最多与 (k + 1) -WL 一样，比应用于整个图的 k-WL 更具有时间和空间效率。用局部 k-WL 等效的两个图的子图和诱导子图的计数是不变的。该算法也引入了局部和递归的 Layer k-WL 以及一个可扩展片段技术，可用于任意 k，以保证使用仅 1-WL 的确切计数，同时比 Papp 和 Wattenhofer（2022a）提到的 GNN 层次更具表达能力。

May, 2023

通过图二连通性重新思考 GNN 的表达能力

本文提出了一种基于图双连通性的表达能力度量方法，发现大多数常见 GNN 架构在此度量下缺乏表达能力，但 ESAN 框架具有可证明的表达能力。作者进一步引入 GD-WL 模型，该模型可通过 Transformer 与 Weisfeiler-Lehman 算法相结合来计算表达能力，并通过实验表明其在绝大多数数据集上效果显著优于现有 GNN 架构。

Jan, 2023