Research map / Graph learning / GNN architectures
Weisfeiler-Leman expressivity hierarchies
Characterize GNN expressive power with WL-style hierarchies.
66 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2020–2026) · an approach in GNN architectures, keyword cluster “wl · expressive · power”
State History Tried Checklist Preprints Who Export
Where it stands
Not enough benchmark data Fewer than four papers report the same benchmark, so there is no record to follow.
20 papers in 2023–24 and 32 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic grew, from 4.2% to 6.3%.
How this is decided
A benchmark is tracked when at least four papers of this approach report their own method on the same dataset and metric in at least two different years. Its record is the best number reported up to 2024 compared with the best reported in 2025–26: still improving means at least 1% better, flat means at most 0.2% better with at least two papers from 2025–26 trying. Numbers on a different scale from the rest (a fraction among percentages) and far outliers are left out. Results come from different papers with different setups, so they are signals, not head-to-head comparisons. The share of papers is counted at ICML, NeurIPS, ICLR, CVPR and AAAI.
How it got here
Most cited paper of each year
- 2020 · The Logical Expressiveness of Graph Neural Networks (ICLR 2020 · 95 citations)
- 2021 · Analyzing the Expressive Power of Graph Neural Networks in a Spectral Perspective (ICLR 2021 · 42 citations)
- 2022 · Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries (NeurIPS 2022 · 21 citations)
- 2023 · Rethinking the Expressive Power of GNNs via Graph Biconnectivity (ICLR 2023 · 15 citations)
- 2024 · Logical characterizations of recurrent graph neural networks with reals and floats (NeurIPS 2024 · 4 citations)
- 2025 · Learning Efficient Positional Encodings with Graph Neural Networks (ICLR 2025 · 1 citation)
- 2026 · Enhancing Logical Expressiveness in Graph Neural Networks via Path-Neighbor Aggregation (AAAI 2026 · 1 citation)
Earliest papers here
- The Logical Expressiveness of Graph Neural Networks (ICLR 2020 · 95 citations)
- Graph Representations for Higher-Order Logic and Theorem Proving (AAAI 2020 · 69 citations)
- Analyzing the Expressive Power of Graph Neural Networks in a Spectral Perspective (ICLR 2021 · 42 citations)
What has been tried
36 papers here report 294 measured changes (a component added, removed or swapped, compared with a baseline): helped 66%, no clear effect 8%, hurt 17%, mixed 9%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| replace general graph canonization with universal graph canonization (UGC) on GIN | Mayo, RosMap, Cancer, fMRI-ABIDE · accuracy | Mayo 0.483 (GC) -> 0.624 (UGC); RosMap 0.486 -> 0.701; Cancer 0.539 -> 0.714; fMRI-ABIDE 0.610 -> 0.648 | Helped | Rethinking the Power of Graph Canonization in Graph Representation Learning with Stability (ICLR 2024 · 3 citations) |
| Increase the selected subgraph count from T=2 to T=5 | ZINC-12k test · MAE | 0.120±0.003 -> 0.109±0.005 | Helped | Efficient Subgraph GNNs by Learning Effective Selection Policies (ICLR 2024 · 2 citations) |
| Use multiple magnetic potentials instead of the best single potential | Directed acyclic graphs · spd RMSE | 0.124 (± 0.002) -> 0.016 (± 0.000) | Helped | What Are Good Positional Encodings for Directed Graphs? (ICLR 2025 · 1 citation) |
| add training | BREC total · pairs distinguished | 80 -> 222 | Helped | An Empirical Study of Realized GNN Expressiveness (ICML 2024 · 1 citation) |
| add RRWP positional encodings | Zinc (12K) · MAE | 0.062 ±0.004 -> 0.059 ±0.004 | Helped | Towards Principled Graph Transformers (NeurIPS 2024 · 1 citation) |
| Vary the number of message-passing layers from 1 to 8 | tgbl-wiki · MRR | Helped | Expressive Power of Temporal Message Passing (AAAI 2025 · 0 citations) | |
| add t=1 composition atoms to R-GNN | Logistics · coverage | 45 % -> 100 % | Helped | Learning More Expressive General Policies for Classical Planning Domains (AAAI 2025 · 0 citations) |
| add l1-normalization in the last layer | graph classification benchmarks · generalization gap | Helped | Towards Bridging Generalization and Expressivity of Graph Neural Networks (ICLR 2025 · 0 citations) | |
| Pre-train (2,1) + LPE rather than train from scratch | Alchemy (12K) · MAE | 0.124 ± 0.001 -> 0.101 ± 0.001 | Helped | Aligning Transformers with Weisfeiler-Leman (ICML 2024 · 0 citations) |
| add Tinhofer individualization to EGONN ego-nets | C4, C5, and K2,3 induced-subgraph identification on 3-regular graphs · test accuracy | 73.6 ±10.2 -> 99.6 ±0.5; 89.4 ±1.5 -> 99.6 ±0.8; 74.2 ±2.2 -> 100.0 ±0.0 | Helped | On the Expressivity and Sample Complexity of Node-Individualized Graph Neural Networks (NeurIPS 2024 · 0 citations) |
| prune K-Path | MUTAG · accuracy | 91.7±1.7 -> 92.6 ±3.3 | Helped | Pruning for GNNs: Lower Complexity with Comparable Expressiveness (ICML 2025) |
| Increase distance encoding depth from 0 to 5 | CSL · accuracy | 50 ± 0 -> 100 ± 0 | Helped | The Expressive Power of Path-Based Graph Neural Networks (ICML 2024) |
What reviewers will expect
Datasets and baselines named in the 16 papers of this approach from 2025–2026 that have a full-text summary. Leaving out the common ones is a frequent review question.
Datasets
- MUTAG · 3 of 16 papers
- PROTEINS · 3 of 16 papers
- ZINC · 3 of 16 papers
- QM9 · 2 of 16 papers
- Cora · 2 of 16 papers
- Citeseer · 2 of 16 papers
- Pubmed · 2 of 16 papers
- ENZYMES · 2 of 16 papers
Baselines
- GIN · 4 of 16 papers
- GCN · 4 of 16 papers
- GraphSAGE · 2 of 16 papers
- GAT · 2 of 16 papers
- SignNet · 2 of 16 papers
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 52 papers; from OpenAlex and the papers' affiliations).
- Peking University · 7 papers
- RWTH Aachen University · 3 papers
- Microsoft · 3 papers
- NVIDIA · 3 papers
- Rheinisch Westfälische Technische Hochschule Aachen · 2 papers
- University of Siena · 2 papers
Use it
Download BibTeX of 35 key papersOpen the topic in the interactive map
Get alerts. Describe your idea in scime atlas and save it (free scime account): you get a weekly email when new preprints land close to it.
Related approaches
Same keyword cluster
- Subgraph and distance-aware GNNs (46 papers)
- Substructure-aware GNN expressivity (50 papers)
Elsewhere in the topic
- Graph structure learning (201 papers)
- GNN generalization theory (187 papers)
- Simple and scalable GNNs (131 papers)
- Expressive equivariant message passing (109 papers)
- Robustness, privacy, and fairness of GNNs (94 papers)
- Theory of graph convolutional networks (83 papers)
- Deep graph convolution and simplification (82 papers)
- Physics-inspired GNNs (81 papers)
Benchmark numbers, ablations and baseline numbers are extracted by AI from each paper's full text and can be wrong; the paper is the authority. Data: results index of 2026-11-02, citation counts from OpenAlex (2026-10-09).