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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Aggregate-Combine-Readout GNNs Are More Expressive Than Logic C2
In recent years, there has been growing interest in understanding the expressive power of graph neural networks (GNNs) by relating them to logical languages. This research has been been initialised by an influential resu…
Twin Weisfeiler-Lehman: High Expressive GNNs for Graph Classification
The expressive power of message passing GNNs is upper-bounded by Weisfeiler-Lehman (WL) test. To achieve high expressive GNNs beyond WL test, we propose a novel graph isomorphism test method, namely Twin-WL, which simult…
ClassificationGraph ClassificationVocal Bursts Intensity PredictionConnectivity-Guided Sparsification of 2-FWL GNNs: Preserving Full Expressivity with Improved Efficiency
Higher-order Graph Neural Networks (HOGNNs) based on the 2-FWL test achieve superior expressivity by modeling 2- and 3-node interactions, but at $\mathcal{O}(n^3)$ computational cost. However, this computational burden i…
Calibrate and Boost Logical Expressiveness of GNN Over Multi-Relational and Temporal Graphs
As a powerful framework for graph representation learning, Graph Neural Networks (GNNs) have garnered significant attention in recent years. However, to the best of our knowledge, there has been no formal analysis of the…
Graph Representation LearningNode ClassificationRepresentation LearningExpressive Power of Temporal Message Passing
Graph neural networks (GNNs) have recently been adapted to temporal settings, often employing temporal versions of the message-passing mechanism known from GNNs. We divide temporal message passing mechanisms from literat…