← Back to all news
arXiv AI

Complete Identification of Deep ReLU Networks through {\L}ukasiewicz Logic

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.

Related stories

arXiv AI
Sep 15

Certifiably Interpretable Training of ReLU-MLPs for Boolean Tasks with Guaranteed Truth-Table Generalization

The paper introduces MACCHIATO, a training algorithm that builds a ReLU‑MLP from partial truth‑table data while simultaneously constructing an explicit Boolean circuit over AND, OR, and XOR gates that certifies the network’s computation. The method iteratively projects residuals onto low‑dimensional Boolean classes, compiles the resulting circuit into a ReLU‑MLP, and uses logic minimization and influence‑based variable selection to achieve a six‑layer network with provable truth‑table error bounds. Experiments on synthetic random‑junta tasks show that these certified networks outperform Adam‑trained MLPs in data‑sparse or projection‑aligned regimes and complete faster than flat ESPRESSO in certain settings.

By Hrad Ghoukasian, Anastasis Kratsios
safety
More like this →
arXiv Machine Learning
Aug 14

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 collection $\Sigma$ of eventually constant activation functions and with arbitrary real coefficients, form a strict subclass of the Boolean queries expressible in ReLU-MPLang.

By Pablo Barcel\'o, Floris Geerts, Matthias Lanzinger, Klara Pakhomenko, Jan Van den Bussche
More like this →
arXiv AI
Sep 15

Recurrent GraphNeural NetworkswithSet-BasedAggregation

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
safety
More like this →
arXiv Machine Learning
5d ago

The Geometry of Limits in ReLU Function Spaces

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
More like this →
arXiv AI
Aug 19

Neuro-symbolic learning over OWL 2 DL via consequence-based compilation to differentiable circuits

Baobab compiles an OWL 2 DL (ΣROIQ) ontology with a finite ABox into a Sentential Decision Diagram (SDD), saturating a propositional core and instantiating remaining DL features over the active domain. The resulting evidence‑conditioned weighted model count trains a perception network to recognize real images under partial ABox supervision, enabling a CNN to recover latent ontology concepts that an independent perception would miss. When supervision allows multiple ontology‑consistent completions, Baobab’s mixture indexed by query justifications represents the calibrated posterior, achieving Bayes‑optimal performance on a real‑image MNIST task where single‑WMC and learned mixtures fail, thereby characterizing and mitigating reasoning shortcuts in a non‑Horn description logic.

By Olga Mashkova, Asaad Mohammedsaleh, Fernando Zhapa-Camacho, Robert Hoehndorf
More like this →
arXiv Machine Learning
Sep 15

Neuron Activation-based Computation of Logical Explanations for Deep Neural Networks

The paper introduces a flexible symbolic framework that efficiently computes logical explanations for deep neural networks by parameterizing explanations with internal neuron activations and leveraging general-purpose logical engines like SMT solvers. Unlike previous methods that rely on specialized verifiers or are limited to individual input features, this approach is not restricted in shape and can scale to deep architectures. Experiments on image recognition and medical benchmarks demonstrate improved computational efficiency and the ability to explain networks that were previously intractable for logic-based methods.

By Tom\'a\v{s} Kol\'arik, Faezeh Labbaf, Fabrizio Leopardi, Grigory Fedyukovich, Michael Wand, Natasha Sharygina
computer-visionbenchmarks
More like this →