The paper presents a complete characterization of when two deep ReLU networks realize the same function, showing that this occurs iff one can be transformed into the other using a set of axioms from many‑valued logic. It introduces a symbolic calculus that maps networks to substitution graphs, proves a completeness theorem linking equivalent formulas, and provides an algorithm to reconstruct networks from these graphs. The framework yields a new compositional normal form for MV logic that preserves the algebraic structure of deep ReLU networks.
By Yani Zhang, Helmut B\"olcskei
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
The paper introduces recurrent Graph Neural Networks (GNNs) that use set-based aggregation and establishes conditions that can be verified directly from the network weights. It proves a two‑directional equivalence between these networks and the Boolean closure of reachability and safety properties, corresponding to the fragment BΣ◦₁ of the modal μ‑calculus. This equivalence allows for verifiable symbolic explanations of networks that satisfy the identified conditions, without relying on counting logic or external halting signals.
By Blai Bonet
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
AutoGraphForge is a computational pipeline designed to automate the discovery, refutation, formalization, and proving of graph-theoretic conjectures. It generates conjectures using a Graffiti3 generator, filters out known results with a novelty filter, tests candidates against a large dataset of graphs, and refines surviving conjectures through counterexample search. The pipeline then translates each conjecture into Lean 4, verifies proofs with neural provers, and integrates the results into a formal library.
By J\'an Pastorek
arXiv:2609.39768v1 Announce Type: cross
Abstract: Certifying a deployed neural network raises decision problems that the verification literature has not classified: whether the model carries a backdo...
By Adrian Wurm
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: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
The paper investigates the geometry and closure properties of function spaces realized by ReLU neural networks with fixed architecture. It proves that the minimal number of convex pieces in continuous piecewise-linear functions is lower semicontinuous under pointwise convergence, and uses this to show that shallow scalar ReLU realization spaces are closed in the weighted supremum norm, while providing a counterexample that demonstrates non-closedness for a specific architecture. The work also characterizes the role of a blow‑up residue in non‑closedness and offers new geometric and functional‑analytic tools for analyzing ReLU realization spaces.
By Kathryn A. Lindsey
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
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
arXiv:2606. 07728v1 Announce Type: new Abstract: It is well established that ReLU networks define continuous piecewise-linear functions, and that their linear regions are polyhedra in the input space.
By Blake B. Gaines, Jinbo Bi