# Towards Understanding the Expressive Power of GNNs with Global Readout

arXiv: https://arxiv.org/abs/2604.22870 · HTML: https://mlsanity.com/paper/2604.22870/

## 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 (most cited first, 13 of 13)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [Graph Neural Network-Based Anomaly Detection in Multivariate Time Series](https://mlsanity.com/paper/2106.06947/) (2021)
- [Graph Neural Network for Traffic Forecasting: A Survey](https://mlsanity.com/paper/2101.11174/) (2021)
- [Modeling polypharmacy side effects with graph convolutional networks](https://mlsanity.com/paper/1802.00543/) (2018)
- [The Descriptive Complexity of Graph Neural Networks](https://mlsanity.com/paper/2303.04613/) (2023)
- [Distinguished In Uniform: Self Attention Vs. Virtual Nodes](https://mlsanity.com/paper/2405.11951/) (2024)
- [Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats](https://mlsanity.com/paper/2405.14606/) (2024)
- [On the Correspondence Between Monotonic Max-Sum GNNs and Datalog](https://mlsanity.com/paper/2305.18015/) (2023)
- [The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic](https://mlsanity.com/paper/2505.08021/) (2025)
- [Logical Characterizations of GNNs with Mean Aggregation](https://mlsanity.com/paper/2507.18145/) (2025)
- [On Algorithms Based on Finitely Many Homomorphism Counts](https://mlsanity.com/paper/2111.13269/) (2021)
- [How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?](https://mlsanity.com/paper/2601.21882/) (2026)

## 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.