mlsanityData to 14 Oct 2026

Towards Understanding the Expressive Power of GNNs with Global Readout

arXiv 2604.22870 ↗First posted 23 Apr 2026cs.LG cs.AI cs.LOcited by 0

Not on the map. Why?

Abstract (arXiv)

We study the expressive power of message-passing aggregate-combine-readout graph neural networks (ACR-GNNs). Particularly, we focus on the first-order (FO) properties expressible by this formalism. While a tight logical characterisation remains a difficult open question, we make two contributions towards answering it. First, we show that sum aggregation and readout suffice for GNNs to capture FO properties that cannot be expressed in the logic C2 on both directed and undirected graphs. This strengthens known results by Hauke and Walk ega (2026) where aggregation and readout functions are specially crafted for the task. Second, we identify two natural ways of restoring characterisability (with regard to C2) for ACR-GNNs. One option is to limit local aggregation (without imposing restrictions on global readout), whilst the second is to run ACR-GNNs over graphs of bounded degree (but unbounded size). In both cases, the FO properties captured by GNNs are exactly those definable by a formula in graded modal logic with global counting modalities. Our results thus establish an innate lower- and upper-bound in terms of how far (fragments of) C2 can be taken to characterise GNNs, and imply that is indeed the unbounded interaction of aggregation and readout that pushes the logical expressive power of GNNs above C2.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 13 of its 31 references that are in the map. First posted on arXiv 23 Apr 2026.

Builds on

13 of 31 references.

References · 13

  1. 2018How Powerful are Graph Neural Networks?cited by 4,393
  2. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 754
  3. 2021Graph Neural Network-Based Anomaly Detection in Multivariate Time Seriescited by 301
  4. 2021Graph Neural Network for Traffic Forecasting: A Surveycited by 261
  5. 2018Modeling polypharmacy side effects with graph convolutional networkscited by 237
  6. 2023The Descriptive Complexity of Graph Neural Networkscited by 26
  7. 2024Distinguished In Uniform: Self Attention Vs. Virtual Nodescited by 20
  8. 2024Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floatscited by 13
  9. 2023On the Correspondence Between Monotonic Max-Sum GNNs and Datalogcited by 12
  10. 2025The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logiccited by 6
  11. 2025Logical Characterizations of GNNs with Mean Aggregationcited by 6
  12. 2021On Algorithms Based on Finitely Many Homomorphism Countscited by 2
1 more
  1. 2026How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?cited by 1

Built on by

Not cited yet.