A Logical View of GNN-Style Computation and the Role of Activation Functions
Open Access
- 12 May 2026
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (2) , 1-19
Abstract
We study the numerical and Boolean expressiveness of MPLang, a declarative language that captures the computation of graph neural networks (GNNs) through linear message passing and activation functions. We begin with A-MPLang, the fragment without activation functions, and give a characterization of its expressive power in terms of walk-summed features. For bounded activation functions, we show that (under mild conditions) all eventually constant activations yield the same expressive power—numerical and Boolean—and that it subsumes previously established logics for GNNs with eventually constant activation functions but without linear layers. Finally, we prove the first expressive separation between unbounded and bounded activations in the presence of linear layers: MPLang with ReLU is strictly more powerful for numerical queries than MPLang with eventually constant activation functions, e.g., truncated ReLU. This hinges on subtle interactions between linear aggregation and eventually constant non-linearities, and it establishes that GNNs using ReLU are more expressive than those restricted to eventually constant activations and linear layers.Keywords
All Related Versions
Funding Information
- ANID - Millennium Science Initiative Program (ICN17002)
- National Center for Artificial Intelligence CENIA (FB210017)
- Fonds Wetenschappelijk Onderzoek (G019222N)
- Flanders AI Program (-)
- Vienna Science and Technology Fund ([10.47379\/ICT2201, 10.47379\/VRG18013])
This publication has 22 references indexed in Scilit:
- On the Expressive Power of Message-Passing Neural Networks as Global Feature Map Transformers2022
- Neural algorithmic reasoningPatterns, 2021
- Semiring Provenance for Guarded Logics2021
- Regular Queries on Graph DatabasesTheory of Computing Systems, 2016
- Expressiveness and static analysis of extended conjunctive regular path queriesJournal of Computer and System Sciences, 2013
- Querying graph databases2013
- Expressive Languages for Path Queries over Graph-Structured DataACM Transactions on Database Systems, 2012
- The Graph Neural Network ModelIEEE Transactions on Neural Networks, 2008
- Finding Regular Simple Paths in Graph DatabasesSIAM Journal on Computing, 1995
- On the Computational Power of Neural NetsJournal of Computer and System Sciences, 1995