What Expressivity Theory Misses: Message Passing Complexity for GNNs

2025/09/01 by Niklas Kemper, Kemper, Niklas, Tom Wollschläger +3
Computer Science · Engineering · Psychology · #Advanced Graph Neural Networks #FOS: Computer and information sciences #Ferroelectric and Negative Capacitance Devices #Machine Learning (cs.LG) #Mental Health via Writing

paper · pdf · doi:10.48550/arxiv.2509.01254

openalex publication_date 2025/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Expressivity theory, characterizing which graphs a GNN can distinguish, has become the predominant framework for analyzing GNNs, with new models striving for higher expressivity. However, we argue that this focus is misguided: First, higher expressivity is not necessary for most real-world tasks as these tasks rarely require expressivity beyond the basic WL test. Second, expressivity theory's binary characterization and idealized assumptions fail to reflect GNNs' practical capabilities. To overcome these limitations, we propose Message Passing Complexity (MPC): a continuous measure that quantifies the difficulty for a GNN architecture to solve a given task through message passing. MPC captures practical limitations like over-squashing while preserving the theoretical impossibility results from expressivity theory, effectively narrowing the gap between theory and practice. Through extensive validation on fundamental GNN tasks, we show that MPC's theoretical predictions correlate with empirical performance, successfully explaining architectural successes and failures. Thereby, MPC advances beyond expressivity theory to provide a more powerful and nuanced framework for understanding and improving GNN architectures.

Citations

• Is uniform expressivity too restrictive? Towards efficient expressivity of graph neural networks
• Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness
• PlanE: Representation Learning over Planar Graphs
• How does over-squashing affect the power of GNNs?
• Fine-grained Expressivity of Graph Neural Networks
• CIN++: Enhancing Topological Message Passing
• Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman
• On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology
• On the Connection Between MPNN and Graph Transformer
• Rethinking the Expressive Power of GNNs via Graph Biconnectivity
• LRGB: Long Range Graph Benchmark
• How Powerful are Spectral Graph Neural Networks
• Theory of Graph Neural Networks: Representation and Learning
• Message passing all the way up
• 1-WL Expressiveness Is (Almost) All You Need
• Weisfeiler-Lehman meets Gromov-Wasserstein
• Weisfeiler and Leman go Machine Learning: The Story so far
• Understanding over-squashing and bottlenecks on graphs via curvature
• Weisfeiler and Lehman Go Cellular: CW Networks
• Weisfeiler and Lehman Go Topological: Message Passing Simplicial\n Networks
• On the Bottleneck of Graph Neural Networks and its Practical Implications
• Directional Message Passing for Molecular Graphs
• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• What Can Neural Networks Reason About?
• Fast Graph Representation Learning with PyTorch Geometric
• Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks
• How Powerful are Graph Neural Networks?
• Representation Learning on Graphs with Jumping Knowledge Networks
• Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• Deep Sets
• Semi-Supervised Classification with Graph Convolutional Networks
• Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift

Related

• Message Passing on the Edge: Towards Scalable and Expressive GNNs
• Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness
• Rethinking the Expressive Power of GNNs via Graph Biconnectivity
• On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry
• Rethinking GNN Expressive Power from a Distributed Computational Model Perspective