0

The Boolean Power of ReLU

We prove that, on finite simple undirected graphs equipped with a single Boolean node feature, the Boolean queries expressible in $Σ$-MPLang, for any collection $Σ$ of eventually constant activation functions and with arbitrary real coefficients, form a strict subclass of the…

Open
Preview
Year
2026
ArXiv
arxiv.org/abs/2608.12617
Hosting
Abstract onlyARXIV-DEFAULT

Cite

Notes

Only stored in your browser.

Attribution

Abstract & full text
arxiv.org/abs/2608.12617ARXIV-DEFAULT
TL;DR
Semantic Scholar
Attribution policy →

Abstract

We prove that, on finite simple undirected graphs equipped with a single Boolean node feature, the Boolean queries expressible in Σ-MPLang, for any collection Σ 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.