AI RESEARCH
Towards Understanding the Expressive Power of GNNs with Global Readout
arXiv CS.LG
•
ArXi:2604.22870v1 Announce Type: new 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.