Research map / Graph learning / GNN architectures
Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes
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 complexes lifted from graphs using simple paths as cells, a Path Weisfeiler-Lehman test (PWL) and a message-passing realization (PCN/PIN), showing it generalizes simplicial and cell-complex WL tests without ring or clique assumptions.
Problem
Topological higher-order GNNs rely on graph substructures such as cliques, cycles, and rings, which imposes restrictive inductive biases; the paper asks whether simple paths can serve as a more general topological domain for expressive graph learning.
Approach
Lift graphs to path complexes whose basis elements are elementary simple paths, define a Path WL color refinement over boundary and upper-adjacency relations of paths, and realize it as a higher-order message-passing network (PCN, instantiated as PIN) that is at least as powerful as SWL and CWL(k-IC).
Key results
- PIN achieves 78.8 ± 4.4 on PROTEINS and 85.1 ± 1.5 on NCI1 on TUDataset, ranking top-3 in several benchmarks.
- On ZINC (with edge features), PIN achieves MAE 0.096 ± 0.006 at max lifting dimension 7, outperforming all baselines except CIN and CIN++.
- PCN with path lifting dimension 3 outperforms CWN(4-IC) and matches CWN(5-IC) on strongly regular graph distinguishing experiments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PIN instead of CIN++ | graph classification on PROTEINS · PROTEINS | accuracy: 80.5 ± 3.9 -> 78.8 ± 4.4 | Hurt |
| Use PIN instead of CIN++ | graph classification on NCI1 · NCI1 | accuracy: 85.3 ± 1.2 -> 85.1 ± 1.5 | Hurt |
| Use PIN instead of CIN++ | graph classification on NCI109 · NCI109 | accuracy: 84.5 ± 2.4 -> 84.0 ± 1.5 | Hurt |
| Use PIN instead of GSN | graph classification on IMDB-B · IMDB-B | accuracy: 77.8 ± 3.3 -> 76.6 ± 2.9 | Hurt |
| Use PIN instead of CIN | molecular graph regression without edge features · ZINC, no edge features | MAE: 0.115 ± 0.003 -> 0.139 ± 0.004 | Hurt |
| Use PIN instead of CIN++ | molecular graph regression with edge features · ZINC, with edge features | MAE: 0.077 ± 0.004 -> 0.096 ± 0.006 | Hurt |
| Use PIN instead of CIN | molecular graph classification · OGBG-MOLHIV test | ROC-AUC: 80.94 ± 0.57 -> 79.44 ± 1.40 | Hurt |
| Use PIN instead of GSN | molecular graph classification · OGBG-MOLHIV validation | ROC-AUC: 86.58 ± 0.84 -> 82.41 ± 0.96 | Hurt |
| Increase maximum lifting dimension from 2 to 7 (ablation) | PIN on ZINC with edge features · ZINC | test MAE: 0.160 ± 0.009 -> 0.096 ± 0.006 | Helped |
| Increase maximum lifting dimension from 3 to 7 (ablation) | PIN on NCI1 · NCI1 | accuracy: 84.9 ± 1.6 -> 85.1 ± 1.5 | No clear effect |
| Increase maximum lifting dimension from 3 to 7 (ablation) | PIN on ZINC · ZINC | test MAE: 0.126 ± 0.004 -> 0.096 ± 0.006 | Helped |
| Increase PIN message-passing layers | PIN(3) on strongly regular graph families · SRG Families | failure rate | Helped |
Surprising findings
- PIN underperforms CIN and CIN++ on ZINC and OGBG-MOLHIV, which the authors attribute to low path-complex dimensionality and shallow architectures.
- Training runs on ZINC with 6 message-passing layers occasionally show large performance deviations under identical seeds, attributed to nondeterministic parallel operations.
Limitations
- High time and space complexity for enumerating paths; PROTEINS, IMDB-B and SR(35,16,6,8) are expensive to lift.
- Underperforms CIN-family models on ZINC and OGBG-MOLHIV due to low dimensionality and shallow architectures.
- Risk of over-smoothing and over-squashing in high-dimensional path complexes.
Experimental setup
Datasets: PROTEINS NCI1 NCI109 IMDB-B ZINC OGBG-MOLHIV Strongly regular graph families
Benchmarks: PROTEINS NCI1 NCI109 IMDB-B ZINC OGBG-MOLHIV Strongly regular graphs
Metrics: accuracy MAE ROC-AUC failure rate on SRG distinguishing
Baselines: GIN PPGNs GSN pathGCN PathNN SIN CIN CAN CIN++ CWN PNA DGN
Builds on: simplicial WL test (SWL) cellular WL test (CWL) MPSN CIN GIN
Closest papers by meaning
- Topological Blindspots: Understanding and Extending Topological Deep Learning Through the Lens of Expressivity (ICLR 2025 · similarity 0.90)
- A Topological Perspective on Demystifying GNN-Based Link Prediction Performance (ICLR 2024 · similarity 0.90)
- TopoTune: A Framework for Generalized Combinatorial Complex Neural Networks (ICML 2025 · similarity 0.89)
- The Underappreciated Power of Vision Models for Graph Structural Understanding (NeurIPS 2025 · similarity 0.89)
- Beyond Message Passing: Neural Graph Pattern Machine (ICML 2025 · similarity 0.88)
- Improving Graph Neural Networks by Learning Continuous Edge Directions (ICLR 2025 · 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.