# The Boolean Power of ReLU

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 4 references that are in the map.
- First posted on arXiv 12 Aug 2026.

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

- [Decidability of Graph Neural Networks via Logical Characterizations](https://mlsanity.com/paper/2404.18151/) (2024)
- [On the expressive power of message-passing neural networks as global feature map transformers](https://mlsanity.com/paper/2203.09555/) (2022)
- [Dimension Reduction via Colour Refinement](https://mlsanity.com/paper/1307.5697/) (2013)
- [A Logical View of GNN-Style Computation and the Role of Activation Functions](https://mlsanity.com/paper/2512.19332/) (2025)

## Abstract (arXiv)

We prove that, on finite simple undirected graphs equipped with a single Boolean node feature, the Boolean queries expressible in Sigma-MPLang, for any collection Sigma of eventually constant activation functions and with arbitrary real coefficients, form a strict subclass of the Boolean queries expressible in ReLU-MPLang. We thereby settle a recently posed open problem: whether ReLU-MPLang is more powerful than trReLU-MPLang when it comes to Boolean queries. In particular, this implies that ReLU-GNNs are strictly more expressive than TrReLU,id-GNNs with respect to Boolean queries on Boolean-featured graphs.