# A Logical View of GNN-Style Computation and the Role of Activation Functions

arXiv: https://arxiv.org/abs/2512.19332 · HTML: https://mlsanity.com/paper/2512.19332/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 46 references that are in the map.
- First posted on arXiv 22 Dec 2025.

## Builds on (most cited first, 20 of 20)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Neural Algorithmic Reasoning](https://mlsanity.com/paper/2105.02761/) (2021)
- [The Logic of Graph Neural Networks](https://mlsanity.com/paper/2104.14624/) (2021)
- [The Descriptive Complexity of Graph Neural Networks](https://mlsanity.com/paper/2303.04613/) (2023)
- [On the expressive power of query languages for matrices](https://mlsanity.com/paper/1709.08359/) (2017)
- [Decidability of Graph Neural Networks via Logical Characterizations](https://mlsanity.com/paper/2404.18151/) (2024)
- [G-CORE: A Core for Future Graph Query Languages](https://mlsanity.com/paper/1712.01550/) (2017)
- [Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats](https://mlsanity.com/paper/2405.14606/) (2024)
- [Graph neural networks extrapolate out-of-distribution for shortest paths](https://mlsanity.com/paper/2503.19173/) (2025)
- [On the expressive power of message-passing neural networks as global feature map transformers](https://mlsanity.com/paper/2203.09555/) (2022)
- [On the power of graph neural networks and the role of the activation function](https://mlsanity.com/paper/2307.04661/) (2023)
- [Graph Neural Networks and Arithmetic Circuits](https://mlsanity.com/paper/2402.17805/) (2024)
- [Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization](https://mlsanity.com/paper/2506.13911/) (2025)
- [Aggregate-Combine-Readout GNNs Are More Expressive Than Logic C2](https://mlsanity.com/paper/2508.06091/) (2025)
- [The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics](https://mlsanity.com/paper/2505.11930/) (2025)
- [Boundedness of Conjunctive Regular Path Queries](https://mlsanity.com/paper/1904.00850/) (2019)
- [Semantic Tree-Width and Path-Width of Conjunctive Regular Path Queries](https://mlsanity.com/paper/2212.01679/) (2022)
- [Minimizing Conjunctive Regular Path Queries](https://mlsanity.com/paper/2504.00612/) (2025)

## Built on by (most cited first, 3 of 3)

- [How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?](https://mlsanity.com/paper/2601.21882/) (2026)
- [Neuro-Relational Programs: Unifying Queries and Neural Computation over Structured Data](https://mlsanity.com/paper/2606.11946/) (2026)
- [The Boolean Power of ReLU](https://mlsanity.com/paper/2608.12617/) (2026)

## 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.