Research map / Graph learning / GNN architectures
Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces r-loopy Weisfeiler-Leman (r-ℓWL) and the GNN r-ℓGIN, which aggregate messages from simple paths between distinct neighbors, enabling cycle counting up to length r+2 and homomorphism counting of cactus graphs.
Problem
Standard MPNNs are bounded by 1-WL and cannot count cycles or homomorphisms beyond trees; higher-order k-WL models are computationally infeasible on sparse real-world graphs.
Approach
Augment each node's direct neighborhood with simple paths of length r connecting two distinct neighbors, run color refinement over these path neighborhoods, and implement it as a GIN-based MPNN (r-ℓGIN) whose cost scales with the number of paths rather than k-tuples.
Key results
- 5-ℓGIN achieves test MAE 0.072 on ZINC12K and 0.022 on ZINC250K, the best among reported baselines in the paper's table.
- 4-ℓGIN distinguishes 257 of 400 BREC pairs, versus 233/400 for ProvablyPowerfulGNN (3-WL equivalent) and 166/400 for Nested GNN, and distinguishes all strongly regular pairs where 3-WL fails.
- On SUBGRAPHCOUNT, r-ℓGIN attains test MAE between 0.0003 and 0.009 across hom and sub count targets, lower than Local 2-FGNN (0.003 to 0.020).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase r from 0 to 5 in ℓGIN (ablation) | ℓGIN · ZINC12K | test MAE: 0.209\pm0.007 -> 0.072\pm0.002 | Helped |
| Set r=1 rather than r=0 (ablation) | ℓGIN · ZINC12K | test MAE: 0.209\pm0.007 -> 0.201 \pm 0.004 | Helped |
| Set r=2 rather than r=0 (ablation) | ℓGIN · ZINC12K | test MAE: 0.209\pm0.007 -> 0.198 \pm 0.008 | Helped |
| Set r=3 rather than r=0 (ablation) | ℓGIN · ZINC12K | test MAE: 0.209\pm0.007 -> 0.184 \pm 0.007 | Helped |
| Set r=4 rather than r=0 (ablation) | ℓGIN · ZINC12K | test MAE: 0.209\pm0.007 -> 0.077 \pm 0.001 | Helped |
| Increase r from 5 to 6 (ablation) | ℓGIN · ZINC12K | test MAE: 0.072\pm0.002 -> 0.077 \pm 0.000 | Hurt |
| Use 5-ℓGIN instead of the strongest listed baseline | Graph regression models · ZINC12K | test MAE: 0.077 \pm 0.002 -> 0.072 \pm 0.002 | Helped |
| Use 5-ℓGIN instead of the strongest listed baseline | Graph regression models · QM9 α | normalized test MAE: 0.222 -> 0.217 | Helped |
| Use 5-ℓGIN instead of the strongest listed baseline | Graph regression models · QM9 μ | normalized test MAE: 0.244 -> 0.350 | Hurt |
| Use 5-ℓGIN instead of the strongest listed baseline | Graph regression models · QM9 U₀ | normalized test MAE: 0.0427 -> 0.0418 | No clear effect |
Surprising findings
- Smaller r already distinguishes 3-WL-equivalent pairs such as the Shrikhande and 4x4 rook graphs, despite 6-ℓWL not being less powerful than 3-WL only in theory.
- Increasing r improves generalization on ZINC12K, with 4-ℓGIN and 5-ℓGIN yielding a clear drop in test MAE compared with 0-ℓGIN.
Limitations
- Path enumeration scales as O(N d^r), which becomes infeasible for dense graphs.
- Expressivity is only loosely bounded for homomorphism counting; a tight characterization of the homomorphism class of r-ℓWL is left open.
- Real-world results are reported with only 4 seeds on large datasets and hyperparameters are tuned by grid search.
Experimental setup
Datasets: ZINC12K ZINC250K QM9 GRAPH8C EXP EXP_ISO CEXP CSL COSPECTRAL10 SR16622 BREC SUBGRAPHCOUNT
Benchmarks: ZINC12K ZINC250K QM9 GRAPH8C EXP_ISO COSPECTRAL10 SR16622 BREC EXP CEXP CSL SUBGRAPHCOUNT
Metrics: MAE AP accuracy number of distinguished pairs L1 distance of embeddings
Baselines: GIN 3-WL ProvablyPowerfulGNN (Maron et al.) Nested GNN PathNN DropGNN GSN I²-GNN SIN DE+GNN Subgraph GNN Local 2-GNN
Builds on: 1-WL k-WL GIN Path Neural Networks Subgraph GNNs
Closest papers by meaning
- Homomorphism Counts for Graph Neural Networks: All About That Basis (ICML 2024 · similarity 0.89)
- Homomorphism Expressivity of Spectral Invariant Graph Neural Networks (ICLR 2025 · similarity 0.89)
- Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them (NeurIPS 2026 · similarity 0.88)
- Weisfeiler-Leman at the margin: When more expressivity matters (ICML 2024 · similarity 0.88)
- On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters (ICLR 2024 · similarity 0.88)
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.