Research map / Graph learning / GNN architectures
How Hard Is It for Message-Passing GNNs to Simulate One Weisfeiler-Lehman Color-Refinement Step?
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.
Theoretical analysis of how many resources (depth, message width, precision, random bits) message-passing GNNs need to simulate one 1-WL color-refinement step, separating oblivious (input-independent) from instance-dependent simulation, with matching-ish upper and lower bounds.
Problem
Message-passing GNNs are said to match 1-WL color refinement, but the resource cost (depth, message bandwidth, precision, randomness) of realizing one refinement step with a single input-independent parameter choice across graphs is unquantified.
Approach
Shows the exact global relabeling of WL-types is the hard part: oblivious deterministic/zero-error MPGNNs need depth Omega(D + m/(wp)) via reduction from Equality communication complexity; bounded-error hashing with large color sets gives one-layer simulation with logarithmic bandwidth and randomness; instance-dependent parameters allow depth one but adaptation needs many rounds.
Key results
- Deterministic and zero-error oblivious simulation requires depth d = Omega(D + m/(wp)) on the hard graph family when log C = o(m) (Thm. deterministic lower bound).
- With C >= 3n^2/(2p_f), a one-layer MPGNN with wp = Theta(log C) and R = Theta(log(n log C / p_f)) random bits simulates one refinement step with probability at least 1 - p_f.
- Instance-dependent representation: a depth-one MPGNN with wp >= ceil(log2 n) suffices for any fixed instance, while instance-dependent adaptation needs r = Omega(D/d + m/(dwp)) rounds.
Surprising findings
- Even a single WL refinement step can require depth growing with the diameter and edge count under oblivious deterministic simulation, despite the locality of WL-types.
- With small color sets (C = Theta(n)), constant depth with logarithmic bandwidth is ruled out for bounded-error randomized simulation.
Limitations
- Deterministic upper bound is proven only in a rooted, port-aware relaxation, not the fully anonymous MPGNN model.
- Intermediate color-set regime between Theta(n) and Theta(n^2/p_f) is not fully characterized.
- Upper bounds allow large local memory and expressive local computation not implementable by standard neural architectures.
Experimental setup
Baselines: Aamand et al. construction
Builds on: 1-WL color refinement Xu et al. GIN expressivity Aamand et al. hashing-based WL simulation Equality communication complexity CONGEST model
Closest papers by meaning
- Higher-Order Graphon Neural Networks: Approximation and Cut Distance (ICLR 2025 · similarity 0.86)
- Spatio-Spectral Graph Neural Networks (NeurIPS 2024 · similarity 0.86)
- The Expressive Power of Path-Based Graph Neural Networks (ICML 2024 · similarity 0.86)
- Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Tasks (NeurIPS 2025 · similarity 0.86)
- On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspective (NeurIPS 2025 · similarity 0.86)
- Accurate and Scalable Graph Neural Networks via Message Invariance (ICLR 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.