Complete Identification of Deep ReLU Neural Networks by Many-Valued Logic

• URL: http://arxiv.org/abs/2602.00266v1
• Date: Fri, 30 Jan 2026 19:39:55 GMT
• Title: Complete Identification of Deep ReLU Neural Networks by Many-Valued Logic
• Authors: Yani Zhang, Helmut Bölcskei,
• Abstract summary: Deep ReLU neural networks admit nontrivial functional symmetries.<n>We translate ReLU networks into Lukasiewicz logic formulae.<n>We show that for every functional equivalence class, all ReLU networks in that class are connected by a finite set of symmetries.
• Score: 1.917311746845434
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Deep ReLU neural networks admit nontrivial functional symmetries: vastly different architectures and parameters (weights and biases) can realize the same function. We address the complete identification problem -- given a function f, deriving the architecture and parameters of all feedforward ReLU networks giving rise to f. We translate ReLU networks into Lukasiewicz logic formulae, and effect functional equivalent network transformations through algebraic rewrites governed by the logic axioms. A compositional norm form is proposed to facilitate the mapping from Lukasiewicz logic formulae back to ReLU networks. Using Chang's completeness theorem, we show that for every functional equivalence class, all ReLU networks in that class are connected by a finite set of symmetries corresponding to the finite set of axioms of Lukasiewicz logic. This idea is reminiscent of Shannon's seminal work on switching circuit design, where the circuits are translated into Boolean formulae, and synthesis is effected by algebraic rewriting governed by Boolean logic axioms.

Related papers

• Quantifying The Limits of AI Reasoning: Systematic Neural Network Representations of Algorithms [10.292476979020522]
  We present a systematic meta-algorithm that converts essentially any circuit into a feedforward neural network (NN)<n>We show that, on any digital computer, our construction emulates the circuit exactly--no approximation, no rounding, modular overflow included--demonstrating that no reasoning task lies beyond the reach of neural networks.
  arXiv  Detail & Related papers  (2025-08-25T21:55:37Z)
• A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networks [0.0]
  We present a formal and constructive simulation framework for nondeterministic finite automata (NFAs) using time-shared, depth-unrolled feedforward networks (TS-FFNs)<n>Our formulation symbolically encodes automaton states as binary vectors, transitions as sparse matrix transformations, and nondeterministic branching-including $varepsilon$-closures-as compositions of shared thresholded updates.
  arXiv  Detail & Related papers  (2025-05-30T01:18:35Z)
• Universal Approximation Theorem for Deep Q-Learning via FBSDE System [2.1756081703276]
  This paper establishes a Universal Approximation Theorem for a class of Deep Q-Networks (DQNs)<n>We show that layers of a deep residual network, conceived as neural operators acting on function spaces, can approximate the action of the Bellman operator.
  arXiv  Detail & Related papers  (2025-05-09T13:11:55Z)
• Joint Group Invariant Functions on Data-Parameter Domain Induce Universal Neural Networks [14.45619075342763]
  We present a systematic method to induce a generalized neural network and its right inverse operator, called the ridgelet transform. Since the ridgelet transform is an inverse, it can describe the arrangement of parameters for the network to represent a target function. We present a new simple proof of the universality by using Schur's lemma in a unified manner covering a wide class of networks.
  arXiv  Detail & Related papers  (2023-10-05T13:30:37Z)
• Permutation Equivariant Neural Functionals [92.0667671999604]
  This work studies the design of neural networks that can process the weights or gradients of other neural networks. We focus on the permutation symmetries that arise in the weights of deep feedforward networks because hidden layer neurons have no inherent order. In our experiments, we find that permutation equivariant neural functionals are effective on a diverse set of tasks.
  arXiv  Detail & Related papers  (2023-02-27T18:52:38Z)
• Logical Message Passing Networks with One-hop Inference on Atomic Formulas [57.47174363091452]
  We propose a framework for complex query answering that decomposes the Knowledge Graph embeddings from neural set operators. On top of the query graph, we propose the Logical Message Passing Neural Network (LMPNN) that connects the local one-hop inferences on atomic formulas to the global logical reasoning. Our approach yields the new state-of-the-art neural CQA model.
  arXiv  Detail & Related papers  (2023-01-21T02:34:06Z)
• Towards Rigorous Understanding of Neural Networks via Semantics-preserving Transformations [0.0]
  We present an approach to the precise and global verification and explanation of Rectifier Neural Networks. Key to our approach is the symbolic execution of these networks that allows the construction of semantically equivalent Typed Affine Decision Structures.
  arXiv  Detail & Related papers  (2023-01-19T11:35:07Z)
• A Recursively Recurrent Neural Network (R2N2) Architecture for Learning Iterative Algorithms [64.3064050603721]
  We generalize Runge-Kutta neural network to a recurrent neural network (R2N2) superstructure for the design of customized iterative algorithms. We demonstrate that regular training of the weight parameters inside the proposed superstructure on input/output data of various computational problem classes yields similar iterations to Krylov solvers for linear equation systems, Newton-Krylov solvers for nonlinear equation systems, and Runge-Kutta solvers for ordinary differential equations.
  arXiv  Detail & Related papers  (2022-11-22T16:30:33Z)
• Discourse-Aware Graph Networks for Textual Logical Reasoning [142.0097357999134]
  Passage-level logical relations represent entailment or contradiction between propositional units (e.g., a concluding sentence) We propose logic structural-constraint modeling to solve the logical reasoning QA and introduce discourse-aware graph networks (DAGNs) The networks first construct logic graphs leveraging in-line discourse connectives and generic logic theories, then learn logic representations by end-to-end evolving the logic relations with an edge-reasoning mechanism and updating the graph features.
  arXiv  Detail & Related papers  (2022-07-04T14:38:49Z)
• Universal approximation property of invertible neural networks [76.95927093274392]
  Invertible neural networks (INNs) are neural network architectures with invertibility by design. Thanks to their invertibility and the tractability of Jacobian, INNs have various machine learning applications such as probabilistic modeling, generative modeling, and representation learning.
  arXiv  Detail & Related papers  (2022-04-15T10:45:26Z)
• Stability of Algebraic Neural Networks to Small Perturbations [179.55535781816343]
  Algebraic neural networks (AlgNNs) are composed of a cascade of layers each one associated to and algebraic signal model. We show how any architecture that uses a formal notion of convolution can be stable beyond particular choices of the shift operator.
  arXiv  Detail & Related papers  (2020-10-22T09:10:16Z)
• On transversality of bent hyperplane arrangements and the topological expressiveness of ReLU neural networks [0.0]
  We investigate how the architecture of F impacts the geometry and topology of its possible decision regions for binary classification tasks. We use this obstruction to prove that a decision region of a generic, ReLU network F: Rn -> R with a single hidden layer of dimension can have no more than one bounded connected component.
  arXiv  Detail & Related papers  (2020-08-20T16:06:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.