# Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman

arXiv: https://arxiv.org/abs/2306.03266 · HTML: https://mlsanity.com/paper/2306.03266/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 52 references that are in the map.
- First posted on arXiv 5 Jun 2023.

## Builds on (most cited first, 30 of 44)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness](https://mlsanity.com/paper/2110.03753/) (2021)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [Relational Pooling for Graph Representations](https://mlsanity.com/paper/1903.02541/) (2019)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [Nested Graph Neural Networks](https://mlsanity.com/paper/2110.13197/) (2021)
- [Rethinking the Expressive Power of GNNs via Graph Biconnectivity](https://mlsanity.com/paper/2301.09505/) (2023)
- [DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks](https://mlsanity.com/paper/2111.06283/) (2021)
- [Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries](https://mlsanity.com/paper/2206.11140/) (2022)
- [Specformer: Spectral Graph Neural Networks Meet Transformers](https://mlsanity.com/paper/2303.01028/) (2023)
- [Breaking the Limits of Message Passing Graph Neural Networks](https://mlsanity.com/paper/2106.04319/) (2021)
- [Expressive Power of Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/2006.15646/) (2020)

## Built on by (most cited first, 13 of 13)

- [One for All: Towards Training One Graph Model for All Classification Tasks](https://mlsanity.com/paper/2310.00149/) (2023)
- [GOFA: A Generative One-For-All Model for Joint Graph Language Modeling](https://mlsanity.com/paper/2407.09709/) (2024)
- [Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness](https://mlsanity.com/paper/2401.08514/) (2024)
- [The Expressive Power of Graph Neural Networks: A Survey](https://mlsanity.com/paper/2308.08235/) (2023)
- [TAGLAS: An atlas of text-attributed graph datasets in the era of large graph and language models](https://mlsanity.com/paper/2406.14683/) (2024)
- [Plain Transformers Can be Powerful Graph Learners](https://mlsanity.com/paper/2504.12588/) (2025)
- [MoSE: Unveiling Structural Patterns in Graphs via Mixture of Subgraph Experts](https://mlsanity.com/paper/2509.09337/) (2025)
- [How Hard Is It for Message-Passing GNNs to Simulate One Weisfeiler-Lehman Color-Refinement Step?](https://mlsanity.com/paper/2410.01308/) (2024)
- [Theoretical Insights into Line Graph Transformation on Graph Learning](https://mlsanity.com/paper/2410.16138/) (2024)
- [What Expressivity Theory Misses: Message Passing Complexity for GNNs](https://mlsanity.com/paper/2509.01254/) (2025)
- [Connectivity-Guided Sparsification of 2-FWL GNNs: Preserving Full Expressivity with Improved Efficiency](https://mlsanity.com/paper/2511.12838/) (2025)
- [Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them](https://mlsanity.com/paper/2605.23446/) (2026)
- [On the Expressive Power of Implicit Line-Graph Higher-Order Weisfeiler--Leman](https://mlsanity.com/paper/2609.16412/) (2026)

## Abstract (arXiv)

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-Lehman (1-WL) test. Some works are inspired by k-WL/FWL (Folklore WL) and design the corresponding neural versions. Despite the high expressive power, there are serious limitations in this line of research. In particular, (1) k-WL/FWL requires at least O(nk) space complexity, which is impractical for large graphs even when k=3; (2) The design space of k-WL/FWL is rigid, with the only adjustable hyper-parameter being k. To tackle the first limitation, we propose an extension, (k,t)-FWL. We theoretically prove that even if we fix the space complexity to O(nk) (for any k≥ 2) in (k,t)-FWL, we can construct an expressiveness hierarchy up to solving the graph isomorphism problem. To tackle the second problem, we propose k-FWL+, which considers any equivariant set as neighbors instead of all nodes, thereby greatly expanding the design space of k-FWL. Combining these two modifications results in a flexible and powerful framework (k,t)-FWL+. We demonstrate (k,t)-FWL+ can implement most existing models with matching expressiveness. We then introduce an instance of (k,t)-FWL+ called Neighborhood2-FWL (N2-FWL), which is practically and theoretically sound. We prove that N2-FWL is no less powerful than 3-WL, and can encode many substructures while only requiring O(n2) space. Finally, we design its neural version named N2-GNN and evaluate its performance on various tasks. N2-GNN achieves record-breaking results on ZINC-Subset (0.059), outperforming previous SOTA results by 10.6%. Moreover, N2-GNN achieves new SOTA results on the BREC dataset (71.8%) among all existing high-expressive GNN methods.