Research
The Boolean Power of ReLU
arXiv:2608.12617v1 Announce Type: new Abstract: We prove that, on finite simple undirected graphs equipped with a single Boolean node feature, the Boolean queries expressible in Sigma-MPLang, for any
arXiv:2608.12617v1 Announce Type: new Abstract: 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.
Related
- Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them
- Explicit integral representations and quantitative bounds for two-layer ReLU networks
- Full-Spectrum Graph Neural Networks: Expressive and Scalable
- Weisfeiler and Leman Follow the Arrow of Time: Expressive Power of Message Passing in Temporal Event Graphs
Source: arXiv cs.LG | 2026-08-14