Towards Understanding the Expressive Power of GNNs with Global Readout

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 Wał{\k e}ga (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.

More from arXiv cs.AI

Avionic Main Fuel Pump Simulation and Fault-Diagnosis Benchmark

arXiv cs.AI·4

Probing Visual Planning in Image Editing Models

arXiv cs.AI·4

IntrAgent: An LLM Agent for Content-Grounded Information Retrieval through Literature Review

arXiv cs.AI·4

MAE-Based Self-Supervised Pretraining for Data-Efficient Medical Image Segmentation Using nnFormer

arXiv cs.AI·4

SwarmDrive: Semantic V2V Coordination for Latency-Constrained Cooperative Autonomous Driving

arXiv cs.AI·4

Structure Guided Retrieval-Augmented Generation for Factual Queries

arXiv cs.AI·4