What Expressivity Theory Misses: Message Passing Complexity for GNNs

• URL: http://arxiv.org/abs/2509.01254v2
• Date: Wed, 22 Oct 2025 15:49:43 GMT
• Title: What Expressivity Theory Misses: Message Passing Complexity for GNNs
• Authors: Niklas Kemper, Tom Wollschläger, Stephan Günnemann,
• Abstract summary: We argue that higher expressivity is not necessary for most real-world tasks as they rarely require expressivity beyond the basic WL test.<n>We propose Message Passing Complexity (MPC), a measure that quantifies the difficulty for a GNN architecture to solve a given task through message passing.<n>MPC captures practical limitations like over-squashing while preserving the theoretical impossibility results from expressivity theory.
• Score: 51.20749443004513
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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.

Related papers

• Beyond Message Passing: A Symbolic Alternative for Expressive and Interpretable Graph Learning [12.70345169123999]
  We propose SymGraph, a symbolic framework for self-explainable Graph Neural Networks (GNNs)<n>By replacing continuous message passing with discrete structural hashing and topological role-based aggregation, our architecture theoretically surpasses the 1-WL barrier.<n>We show that SymGraph achieves state-of-the-art performance, outperforming existing self-explainable GNNs.
  arXiv  Detail & Related papers  (2026-02-18T23:25:25Z)
• Do It for HER: First-Order Temporal Logic Reward Specification in Reinforcement Learning (Extended Version) [49.462399222747024]
  We propose a novel framework for the logical specification of non-Markovian rewards in Decision Processes (MDPs) with large state spaces.<n>Our approach leverages Linear Temporal Logic Modulo Theories over finite traces (LTLfMT)<n>We introduce a method based on reward machines and Hindsight Experience Replay (HER) to translate first-order logic specifications and address reward sparsity.
  arXiv  Detail & Related papers  (2026-02-05T22:11:28Z)
• GLOW: Graph-Language Co-Reasoning for Agentic Workflow Performance Prediction [51.83437071408662]
  We propose GLOW, a unified framework for AW performance prediction.<n>GLOW combines the graph-structure modeling capabilities of GNNs with the reasoning power of LLMs.<n>Experiments on FLORA-Bench show that GLOW outperforms state-of-the-art baselines in prediction accuracy and ranking utility.
  arXiv  Detail & Related papers  (2025-12-11T13:30:46Z)
• Demystifying MPNNs: Message Passing as Merely Efficient Matrix Multiplication [4.002604752467421]
  Graph Neural Networks (GNNs) have achieved remarkable success, their design largely relies on empirical intuition rather than theoretical understanding.<n>We present a comprehensive analysis of GNN behavior through three fundamental aspects.<n>We demonstrate that gradient-related issues, rather than just over-smoothing, can significantly impact performance in sparse graphs.<n>We also analyze how different normalization schemes affect model performance and how GNNs make predictions with uniform node features.
  arXiv  Detail & Related papers  (2025-01-31T19:48:03Z)
• Towards Bridging Generalization and Expressivity of Graph Neural Networks [11.560730203511111]
  We study the relationship between expressivity and generalization in graph neural networks (GNNs) We introduce a novel framework that connects GNN generalization to the variance in graph structures they can capture. We uncover a trade-off between intra-class concentration and inter-class separation, both of which are crucial for effective generalization.
  arXiv  Detail & Related papers  (2024-10-14T00:31:16Z)
• Rethinking GNN Expressive Power from a Distributed Computational Model Perspective [21.723600297533835]
  We argue that using well-defined computational models, such as a modified CONGEST model with clearly specified preprocessing and postprocessing, offers a more sound framework for analyzing GNN expressiveness.<n>We show that allowing unrestricted preprocessing or incorporating externally computed features, while claiming that these precomputations enhance the expressiveness, can sometimes lead to problems.<n>Despite these negative results, we also present positive results that characterize the effects of virtual nodes and edges from a computational model perspective.
  arXiv  Detail & Related papers  (2024-10-02T08:01:50Z)
• Uncertainty in Graph Neural Networks: A Survey [47.785948021510535]
  Graph Neural Networks (GNNs) have been extensively used in various real-world applications.<n>However, the predictive uncertainty of GNNs stemming from diverse sources can lead to unstable and erroneous predictions.<n>This survey aims to provide a comprehensive overview of the GNNs from the perspective of uncertainty.
  arXiv  Detail & Related papers  (2024-03-11T21:54:52Z)
• Hierarchical Invariance for Robust and Interpretable Vision Tasks at Larger Scales [54.78115855552886]
  We show how to construct over-complete invariants with a Convolutional Neural Networks (CNN)-like hierarchical architecture. With the over-completeness, discriminative features w.r.t. the task can be adaptively formed in a Neural Architecture Search (NAS)-like manner. For robust and interpretable vision tasks at larger scales, hierarchical invariant representation can be considered as an effective alternative to traditional CNN and invariants.
  arXiv  Detail & Related papers  (2024-02-23T16:50:07Z)
• Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness [35.409017863665575]
  Homomorphism expressivity measures the ability of GNN models to count graphs under homomorphism. By examining four classes of prominent GNNs as case studies, we derive simple, unified, and elegant descriptions of their homomorphism expressivity. Our results provide novel insights into a series of previous work, unify the landscape of different subareas in the community, and settle several open questions.
  arXiv  Detail & Related papers  (2024-01-16T17:23:23Z)
• Expressivity of Graph Neural Networks Through the Lens of Adversarial Robustness [42.129871250427016]
  We use adversarial robustness as a tool to uncover a significant gap between their theoretically possible and empirically achieved expressive power. We develop efficient adversarial attacks for subgraph counting and show that more powerful GNNs fail to generalize even to small perturbations to the graph's structure.
  arXiv  Detail & Related papers  (2023-08-16T07:05:41Z)
• Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth [57.10183643449905]
  Graph Neural Networks (GNNs) have been studied from the lens of expressive power and generalization. We study the dynamics of GNNs by studying deep skip optimization. Our results provide first theoretical support for the success of GNNs.
  arXiv  Detail & Related papers  (2021-05-10T17:59:01Z)
• Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
  It is known that the current graph neural networks (GNNs) are difficult to make themselves deep due to the problem known as over-smoothing. Multi-scale GNNs are a promising approach for mitigating the over-smoothing problem. We derive the optimization and generalization guarantees of transductive learning algorithms that include multi-scale GNNs.
  arXiv  Detail & Related papers  (2020-06-15T17:06:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.