A Logical View of GNN-Style Computation and the Role of Activation Functions
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 20 of its 46 references that are in the map. First posted on arXiv 22 Dec 2025.
Builds on
20 of 46 references.
References · 20
- 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
- 2017Inductive Representation Learning on Large Graphscited by 6,284
- 2017Neural Message Passing for Quantum Chemistrycited by 3,460
- 2021Neural Algorithmic Reasoningcited by 92
- 2021The Logic of Graph Neural Networkscited by 84
- 2023The Descriptive Complexity of Graph Neural Networkscited by 26
- 2017On the expressive power of query languages for matricescited by 14
- 2017G-CORE: A Core for Future Graph Query Languagescited by 13
- 2024Decidability of Graph Neural Networks via Logical Characterizationscited by 13
- 2024Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floatscited by 13
- 2025Graph neural networks extrapolate out-of-distribution for shortest pathscited by 9
- 2022On the expressive power of message-passing neural networks as global feature map transformerscited by 8
8 more
- 2023On the power of graph neural networks and the role of the activation functioncited by 7
- 2024Graph Neural Networks and Arithmetic Circuitscited by 3
- 2025Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualizationcited by 3
- 2025Aggregate-Combine-Readout GNNs Are More Expressive Than Logic C2cited by 3
- 2025The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logicscited by 2
- 2019Boundedness of Conjunctive Regular Path Queriescited by 1
- 2022Semantic Tree-Width and Path-Width of Conjunctive Regular Path Queriescited by 1
- 2025Minimizing Conjunctive Regular Path Queriescited by 1
Built on by
Citing papers per year: 2026: 3.
3 papers.