arXiv Machine Learning August 14, 2026 By Pablo Barcel\'o, Floris Geerts, Matthias Lanzinger, Klara Pakhomenko, Jan Van den Bussche

The Boolean Power of ReLU

Read the original on arXiv Machine Learning →

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.

Summary generated by The Flow from the publisher's feed. The full article lives at arXiv Machine Learning.

arXiv Machine Learning

Jun 30

Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks

arXiv:2603. 14846v3 Announce Type: replace Abstract: We define an information-complexity property for aggregation functions, capturing a vast range of practical aggregations, and prove that any Message-Passing Graph Neural Network (MP-GNN) model with such aggregations induces only a polynomial number of equivalence classes on all graphs - while the number of non-isomorphic graphs is super-exponential (in number of vertices).

By Eran Rosenbluth

arXiv AI

Aug 3

Learning Lookahead Lemmas for Neural Network Verification

arXiv:2607. 29051v1 Announce Type: cross Abstract: State-of-the-art neural network verifiers use the branch-and-bound procedure as their core solving mechanism.

By Liam Davis, Haoze Wu

benchmarks

arXiv Machine Learning

Jul 7

Scaling Weisfeiler-Leman Expressiveness Analysis to Massive Graphs with GPUs

arXiv:2607. 02603v1 Announce Type: cross Abstract: The stable coloring of the Weisfeiler-Leman (1-WL) test is a cornerstone of Graph Neural Networks because it provides an upper bound to the expressive power of message-passing architectures.

By Filippo Biondi, Mirco Tribastone, Max Tschaikowski

arXiv Machine Learning

Jun 2

Statistical Guarantees for Reasoning Probes on Looped Boolean Circuits

arXiv:2602. 03970v3 Announce Type: replace-cross Abstract: We study the statistical behavior of reasoning probes in a stylized model of iterative computation inspired by neural algorithmic reasoning.

By Anastasis Kratsios, Giulia Livieri, A. Martina Neuman

rag

arXiv AI

Jul 8

ExplAIner: A Declarative Query Language for Explaining Classification Models

arXiv:2607. 06407v1 Announce Type: new Abstract: The XAI community has studied a wide range of queries and scores for explaining predictions of ML models.

By Marcelo Arenas, Pablo Barcel\'o, Diego Bustamante, Jose Caraball, Mar\'ia Alejandra Schild, Bernardo Subercaseaux

safety

arXiv AI

Jun 17

Structural Preservation and the Logical Expressiveness of Graph Neural Networks

arXiv:2606. 17882v1 Announce Type: new Abstract: Bridges between graph neural networks (GNNs) and logical formalisms have been established by fixing architectural choices, such as the types of aggregation, combination, and activation functions.

By Przemys{\l}aw Andrzej Wa{\l}\k{e}ga, Bernardo Cuenca Grau

rag

Related stories

Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks

Learning Lookahead Lemmas for Neural Network Verification

Scaling Weisfeiler-Leman Expressiveness Analysis to Massive Graphs with GPUs

Statistical Guarantees for Reasoning Probes on Looped Boolean Circuits

ExplAIner: A Declarative Query Language for Explaining Classification Models

Structural Preservation and the Logical Expressiveness of Graph Neural Networks