Towards Understanding the Expressive Power of GNNs with Global Readout
Maurice Funk, Daumantas Kojelis · 2026
Read Towards Understanding the Expressive Power of GNNs with Global Readout by Maurice Funk, Daumantas Kojelis (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-22870.txt.
Introduction
Funk and Kojelis study how much first-order logic a message-passing graph neural network with global readout can express. They show that sum aggregation and readout already capture first-order properties that the logic C2 cannot express, on directed and undirected graphs alike. That strengthens earlier results built on specially crafted aggregation and readout functions. They also give two ways to restore a clean C2 characterization: limit local aggregation, or run the networks on graphs of bounded degree but unbounded size.
Catalog record
| CREATOR | Maurice Funk, Daumantas Kojelis |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 96711 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.22870
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Towards Understanding the Expressive Power of GNNs with Global Readout Maurice Funk, Daumantas Kojelis Abstract 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 C 2 \text{C}^{2} on both directed and undirected graphs. This strengthens known results by Hauke and Wałęga 2026 where aggregation and readout functions are specially crafted for the task. Second, we identify two natural ways of restoring characterisability (in regards to C 2 \text{C}^{2} ) 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) C 2 \text{C}^{2} 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 C 2 \text{C}^{2} . 1 Introduction Message-passing graph neural networks (GNNs) ( Scarselli et al. 2009 ) are popular machine learning models for graph structured data and are by design permutation-invariant. They have found applications in diverse areas that involve graph data such as analysis of molecules ( Duvenaud et al. 2015 ) , medicine ( Zitnik, Agrawal, and Leskovec 2018 ) , fraud detection ( Deng and Hooi 2021 ) , and traffic forecasting ( Jiang and Luo 2022 ) . Many different variants of GNNs are used in practice, but they all share central features. They associate each vertex of a graph with an embedding vector and update this embedding layer-by-layer. In each layer, every vertex sends messages containing its current embedding to other vertices, and receives such messages themselves. These received messages are then aggregated and combined with the current vertex embedding to form the new embedding. The main differences between GNN variants lie in which vertices receive a message and how these messages are aggregated and combined. Commonly, messages are only passed along edges of the graph. Other variants are equipped with global readout functionality – the ability to aggregate messages from all vertices regardless of their connection in the graph. Popular choices of functions used for processing the messages in aggregation and readout are dimension-wise sum, max, or mean. The combination function, which forms the new vertex embeddings from the aggregated messages, is typically a trainable feed-forward neural network (FFNN). To understand the limitations and relationships of all these possible choices, a growing body of literature is dedicated to characterising the expressive power of the GNN variants using logical formalisms. One main direction of recent research is finding which vertex (or graph) properties can be expressed by GNNs. The central result in this area is by Barceló et al. 2020 , who show that GNNs with only local aggregation can express exactly the first-order (FO) vertex properties that are formulas of graded modal logic ( GML ), and that sum aggregation suffices for this. In the same paper, the authors also show that GNNs with both local aggregation and global readout can express all formulas of the logic \text{C}^{2} , that is, the two-variable fragment of first-order logic with counting quantifiers. The question whether \text{C}^{2} exactly corresponds to GNNs with aggregation and readout was left open. Surprisingly, the questions was later answered negatively by Hauke and Wałęga 2026 . They show that there is an FO vertex property that can be expressed by certain aggregate-combine-readout GNN (ACR-GNN) architectures, but cannot be expressed by \text{C}^{2} . In light of this unexpected expressive power, it is an open question what logics can be used to characterise GNNs with readout. More is known when the aggregation and readout functions of ACR-GNNs are not arbitrary functions, but are bounded in the sense that they are only sensitive to messages up to a certain multiplicity. Cuenca Grau, Feng, and Walega 2026 show that ACR-GNNs with bounded readout and bounded aggregation correspond exactly to GML extended with a global counting modality. This holds for all vertex properties, not just the ones expressible in FO. Unfortunately, common aggregation and readout functions such as sum and mean are not bounded. Likewise, it is not known whether these specific aggregation functions allow ACR-GNNs to express FO properties outside of \text{C}^{2} . This leaves a gap in the understanding of the expressive power of GNNs, as the known upper and lower bounds are relatively far apart. We make two contribution towards closing this gap. First, we show that simple ACR-GNNs which only use (unbounded) sum for aggregation and readout can express FO properties outside of \text{C}^{2} . We show this for both directed (Theorem 1 ) and undirected graphs (Theorem 5 ). This strengthens the mentioned result by Hauke and Wałęga 2026 , which relies on specialized aggregation, readout and combination functions. In fact, for directed graphs we use the same FO property as Hauke and Wałęga 2026 (strict linear orders), but use a new characterisation in terms of homomorphism counts to show that this property is expressible using only sum aggregation and readout. For undirected graphs, we also follow a similar approach as Hauke and Wałęga 2026 and simulate directed edges via undirected gadgets. Compared to the paper above, we use a different directed graph gadgetisation for technical reasons. As our second contribution, we identify two relevant cases that each result in ACR-GNNs capturing exactly the FO vertex properties expressible in GML extended a global counting modality on both directed and undirected graphs. The first case is the restriction to only graphs in which the degree of vertices is bounded by some constant (Theorem 10 ). This is a natural assumption for many graph datasets, for example, those that originate from molecules or road networks. The second, closely related, case is the case of ACR-GNNs in which the aggregation functions are bounded but the readout functions can be arbitrary (Proposition 11 ). This, for FO vertex properties, generalizes the result by Cuenca Grau, Feng, and Walega 2026 , where both aggregation and readout functions are taken to be bounded. It is quite surprising that allowing unbounded readout functions does not increase the expressive power relative to FO. This reveals that it is indeed the unbounded interaction of readout and aggregation that moves GNNs outside of \text{C}^{2} in terms of expressivity. Our characterisation result relies on the combination of first-order model theory and architectural properties of GNNs. The constructions used may be of independent interest in the study of finite model theory. The rest of this paper is structured as follows. Section 2 gives the necessary definitions used throughout the work. In Section 3 , we show that ACR-GNNs that use only sum for aggregation, readout and combination can express a first-order property that is outside of \text{C}^{2} . In Section 4