Research map / Graph learning / GNN architectures
What Expressivity Theory Misses: Message Passing Complexity for GNNs
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 Message Passing Complexity (MPC), a continuous, task- and graph-specific measure of how hard a task is for an MPNN, based on a probabilistic lossy WL test, to replace binary iso expressivity analysis.
Problem
Isomorphism-based expressivity theory is binary, idealized (lossless propagation, unbounded depth), and task-agnostic, so it fails to explain real-world MPNN performance differences between architectures of equal expressivity.
Approach
Define MPC = -log probability that the output of a lossy WL test (each message survives with probability given by the random-walk influence matrix) lets one deduce the task output; it is infinite exactly when WL-style expressivity says the task is impossible, and grows with over-squashing, under-reaching and task-specific difficulty.
Key results
- On the retaining-features task, simulated MPC shows perfect negative Spearman correlation (rho_s = -1) with accuracy, whereas WLC is constant zero regardless of depth.
- MPC bounds show a virtual node changes propagation complexity from O(D) to O(log n), matching GCN-VN's advantage on long-range tasks; all models except GCN-VN fail at distance D=5 with L=5 layers.
- For ring detection, MPC is negatively Spearman correlated with average precision, with CIN and FragNet achieving O(log(sr)) complexity versus at least s log(r) for standard MPNNs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use simulated MPC complexity instead of WL-based WLC to characterize feature retention as depth increases | GCN, GIN, GraphSage, GSN, FragNet, and CIN · Initial node-feature retention on random 3-regular graphs | test accuracy: ρ_s = -1 | Mixed |
| Add a virtual node | GCN (GCN-VN) · Source-to-target feature propagation at D=5 | accuracy | Helped |
| Add a virtual node | GCN (GCN-VN) · Long-range feature propagation | message-passing complexity: O(D) to O(log n) | Helped |
| Use cycle-oriented inductive biases | GSN, CIN, and FragNet · Cycle-label identification on random 4-regular graphs | average precision | Helped |
| Use cycle-oriented inductive biases | CIN and FragNet · Cycle-label identification | message-passing complexity: O(log(sr)) vs. ≥ s log(r) for all others | Helped |
| Use architectures with lower ring-detection complexity | GNN architectures on ZINC · ZINC molecular regression | performance | Helped |
| Increase the number of message-passing layers | Most tested MPNN architectures · Initial node-feature retention | test accuracy | Hurt |
| Increase source-target distance | Most MPNNs · Source-to-target feature propagation | accuracy | Hurt |
| Use higher-order architecture without a task-aligned propagation bias | GSN, FragNet, and CIN · Source-to-target feature propagation | accuracy | Hurt |
| Use lossy, task-specific MPC rather than binary WL-based WLC | MPNN architecture comparisons · Initial node-feature retention | correlation with test accuracy: ρ_s = -1 | Helped |
| Use GCN with a virtual node rather than standard MPNNs | GCN-VN vs. standard MPNNs · Long-range graph benchmark | accuracy | Helped |
Surprising findings
- Only CIN and GraphSage maintain perfect accuracy on the retaining-features task at all depths, despite the over-smoothing complexity growing with depth.
- Almost all graphs in ZINC (>99.99% for ZINC-full) are already distinguished by the basic WL test, so higher-order gains are not explained by iso expressivity.
Limitations
- Abstracts away from update/aggregation parametrization and optimization, so values indicate trends rather than absolute learnability.
- Exact complexity is hard to compute for sophisticated tasks; theoretical bounds are used instead.
- Does not cover attention-based models in the main framework; exact target functions in real applications are unknown and proxy tasks are used.
Experimental setup
Datasets: random 3-regular graphs random 4-regular graphs ZINC Long Range Graph Benchmark (LRGB)
Benchmarks: ZINC Long Range Graph Benchmark
Metrics: test accuracy average precision Spearman correlation
Baselines: WLC (WL-based complexity) GCN GIN GraphSage GCN-VN GSN FragNet CIN
Builds on: Weisfeiler-Leman test over-squashing theory GIN CIN
Closest papers by meaning
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.91)
- An Empirical Study of Realized GNN Expressiveness (ICML 2024 · similarity 0.90)
- Towards Bridging Generalization and Expressivity of Graph Neural Networks (ICLR 2025 · similarity 0.89)
- On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry (NeurIPS 2026 · similarity 0.89)
- Weisfeiler-Leman at the margin: When more expressivity matters (ICML 2024 · similarity 0.89)
- Reconsidering Faithfulness in Regular, Self-Explainable and Domain Invariant GNNs (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.