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: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
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
The paper extends the Strong Expressive Lottery Ticket Hypothesis to relational and temporal graph neural networks by proving that sufficiently large RGNNs contain sparse subnetworks preserving 1‑relational Weisfeiler‑Leman expressivity. It derives a probabilistic lower bound for random pruning to achieve such subnetworks and shows that common TGNNs and cross‑graph message passing can be reformulated as RGNNs to inherit these guarantees. Experiments validate the bound, compare it to empirical probabilities on synthetic data, and explore the relationship between pre‑training expressivity, optimization behavior, and prediction quality on temporal and molecular benchmarks.
By Lorenz Kummer, Samir Moustafa, Anatol Ehrlich, Franka Bause, Marco Nennstiel, Przemys{\l}aw Andrzej Wa{\l}\c{e}ga, Nils Morten Kriege
The paper introduces a logic-based framework that extracts global logical rules for node classification in Simple Graph Convolution (SGC) networks. It uses minimal abductive explanations—small sets of node-feature pairs that preserve a node’s predicted class—as an intermediate step. Decision trees trained on these explanations yield compact global rules that retain high fidelity to the original SGC model, as demonstrated on benchmark datasets.
By Bryan Lima Cavalcante, Thiago Alves Rocha