mlsanityData to 7 Oct 2026

Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks

arXiv 2603.14846 ↗First posted 16 Mar 2026cs.LG cs.CCcited by 0

Not on the map. Why?

Abstract (arXiv)

We define an information-complexity property for aggregation functions, capturing a vast range of practical aggregations, and prove that any Message-Passing Graph Neural Network (MP-GNN) model with such aggregations induces only a polynomial number of equivalence classes on all graphs - while the number of non-isomorphic graphs is super-exponential (in number of vertices). Adding a familiar perspective, we observe that merely 2 iterations of Color Refinement (CR) induce at least an exponential number of equivalence classes, making the aforementioned MP-GNNs relatively infinitely weaker. Previous studies state that sum-aggregation MP-GNNs match full CR however they consider a weak, 'non-uniform', notion of distinguishing-power where each graph size may require a different MP-GNN to distinguish graphs up to that size. Our results concern both distinguishing between non-equivariant vertices and distinguishing between non-isomorphic graphs.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 17 of its 37 references that are in the map. First posted on arXiv 16 Mar 2026.

Builds on

17 of 37 references.

References · 17

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2018How Powerful are Graph Neural Networks?cited by 4,355
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  5. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  6. 2020A Generalization of Transformer Networks to Graphscited by 653
  7. 2020Principal Neighbourhood Aggregation for Graph Netscited by 477
  8. 2021QA-GNN: Reasoning with Language Models and Knowledge Graphs for Question Answeringcited by 386
  9. 2021The Logic of Graph Neural Networkscited by 84
  10. 2022One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfactioncited by 27
  11. 2023The Descriptive Complexity of Graph Neural Networkscited by 26
  12. 2023Some Might Say All You Need Is Sumcited by 21
5 more
  1. 2022Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networkscited by 20
  2. 2015Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinementcited by 16
  3. 2023On the power of graph neural networks and the role of the activation functioncited by 7
  4. 2025Learning from Algorithm Feedback: One-Shot SAT Solver Guidance with GNNscited by 4
  5. 2024Are Targeted Messages More Effective?cited by 1

Built on by

Not cited yet.