Research map / Graph learning / GNN architectures
The Expressive Power of Path-Based Graph Neural Networks
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.
Proposes PATH-WL, a family of color refinement tests based on path multisets with shortest-path distance encodings, analyzes its expressivity relative to 1-WL, k-WL and GNN variants, and implements it as the PAIN GNN.
Problem
The expressive power of path-based graph neural networks, which aggregate paths and shortest-path distances, has not been characterized theoretically despite strong empirical results.
Approach
Defines PATH-WL, a color refinement procedure that aggregates multisets of all paths up to length l with optional distance encodings up to depth d, proves it is strictly more expressive than 1-WL, incomparable to k-WL, and able to count cycles; implements this as the PAIN architecture (paths embedded with LSTM, summed over paths).
Key results
- Untrained 0-PAIN with path length 5 distinguishes all 600 EXP pairs (0 failures vs 600 for GIN).
- On CSL, 1-layer 0-PAIN reaches 50% accuracy at path length 5 while 0-PAIN to 1-PAIN/2-PAIN distance encoding reaches 100% (2-PAIN, path length 5).
- On ZINC, PAIN achieves 0.148 MAE, worse than pathNN (0.090) and CIN (0.079); on OGBG-MOLHIV PAIN gets 78.50 ROC-AUC vs pathNN 79.17.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PAIN with path length 5 instead of GIN | EXP graph-pair discrimination · EXP | indistinguishable graph pairs: 600 -> 0 | Helped |
| Use 1-PAIN with path length 3 instead of GIN | ZINC · ZINC | MAE: 0.387 ± 0.015 -> 0.148 ± 0.003 | Helped |
| Use 1-PAIN with path length 3 instead of GCN | ZINC · ZINC | MAE: 0.278 ± 0.003 -> 0.148 ± 0.003 | Helped |
| Use 1-PAIN with path length 3 instead of CIN | ZINC · ZINC | MAE: 0.079 ± 0.006 -> 0.148 ± 0.003 | Hurt |
| Use 1-PAIN with path length 3 instead of pathNN | ZINC · ZINC | MAE: 0.090 ± 0.004 -> 0.148 ± 0.003 | Hurt |
| Use 1-PAIN with path length 2 instead of GIN | OGBG-MOLHIV · OGBG-MOLHIV | ROC-AUC: 75.58 ± 1.40 -> 78.50 ± 1.4 | Helped |
| Use 1-PAIN with path length 2 instead of CIN | OGBG-MOLHIV · OGBG-MOLHIV | ROC-AUC: 80.94 ± 0.57 -> 78.50 ± 1.4 | Hurt |
| Increase distance encoding depth from 0 to 5 (ablation) | PAIN, 1 layer, path length 5 on CSL · CSL | accuracy: 50 ± 0 -> 100 ± 0 | Helped |
| Increase distance encoding depth from 0 to 5 (ablation) | PAIN, 2 layers, path length 5 on CSL · CSL | accuracy: 46 ± 5 -> 100 ± 0 | Helped |
| Increase the number of layers from 1 to 2 (ablation) | 1-PAIN, path length 2 on CSL · CSL | accuracy: 20 ± 0 -> 64 ± 8 | Helped |
| Increase the number of layers from 1 to 2 (ablation) | 2-PAIN, path length 2 on CSL · CSL | accuracy: 20 ± 0 -> 70 ± 9 | Helped |
| Increase path length from 2 to 5 (ablation) | 0-PAIN, 1 layer on CSL · CSL | accuracy: 12 ± 4 -> 50 ± 0 | Helped |
Surprising findings
- Considering all paths in PAIN did not outperform state-of-the-art real-world baselines on ZINC and OGBG-MOLHIV.
- Distance encoding gives a large accuracy boost on CSL without increasing time complexity.
Limitations
- Enumerating all paths is intractable for dense or large-degree graphs.
- PAIN does not beat state-of-the-art on real-world benchmarks (ZINC, OGBG-MOLHIV).
Experimental setup
Datasets: EXP SR CSL ZINC OGBG-MOLHIV
Benchmarks: EXP SR CSL ZINC OGBG-MOLHIV
Metrics: failure rate (pairs not distinguished) accuracy MAE ROC-AUC
Baselines: GIN GCN GAT CIN ESAN pathNN GSN Graphormer 3-WL
Builds on: 1-WL color refinement pathNN k-WL hierarchy Graph Isomorphism Network
Closest papers by meaning
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.87)
- Homomorphism Expressivity of Spectral Invariant Graph Neural Networks (ICLR 2025 · similarity 0.87)
- Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes (AAAI 2024 · similarity 0.86)
- How Hard Is It for Message-Passing GNNs to Simulate One Weisfeiler-Lehman Color-Refinement Step? (NeurIPS 2026 · similarity 0.86)
- On the Expressive Power of Spectral Invariant Graph Neural Networks (ICML 2024 · similarity 0.86)
- Pruning for GNNs: Lower Complexity with Comparable Expressiveness (ICML 2025 · similarity 0.86)
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.