mlsanityData to 14 Oct 2026

The Geometry of ReLU Networks through the ReLU Transition Graph

arXiv 2505.11692 ↗First posted 16 May 2025cs.LG cs.AI cs.NEcited by 4

Not on the map. Why?

Abstract (arXiv)

We develop a novel theoretical framework for analyzing ReLU neural networks through the lens of a combinatorial object we term the ReLU Transition Graph (RTG). In this graph, each node corresponds to a linear region induced by the network's activation patterns, and edges connect regions that differ by a single neuron flip. Building on this structure, we derive a suite of new theoretical results connecting RTG geometry to expressivity, generalization, and robustness. Our contributions include tight combinatorial bounds on RTG size and diameter, a proof of RTG connectivity, and graph-theoretic interpretations of VC-dimension. We also relate entropy and average degree of the RTG to generalization error. Each theoretical result is rigorously validated via carefully controlled experiments across varied network depths, widths, and data regimes. This work provides the first unified treatment of ReLU network structure via graph theory and opens new avenues for compression, regularization, and complexity control rooted in RTG analysis.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 14 of its 20 references that are in the map. First posted on arXiv 16 May 2025.

Builds on

14 of 20 references.

References · 14

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  2. 2018The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networkscited by 2,262
  3. 2014On the Number of Linear Regions of Deep Neural Networkscited by 381
  4. 2014In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learningcited by 342
  5. 2016On the Expressive Power of Deep Neural Networkscited by 306
  6. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  7. 2016Exponential expressivity in deep neural networks through transient chaoscited by 261
  8. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 257
  9. 2016Benefits of depth in neural networkscited by 250
  10. 2018Sensitivity and Generalization in Neural Networks: an Empirical Studycited by 189
  11. 2019Complexity of Linear Regions in Deep Networkscited by 167
  12. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
2 more
  1. 2017Approximating Continuous Functions by ReLU Nets of Minimal Widthcited by 122
  2. 2018On Characterizing the Capacity of Neural Networks using Algebraic Topologycited by 38

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 1.

4 papers.

  1. 2025A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networkscited by 2
  2. 2025Symbolic Feedforward Networks for Probabilistic Finite Automata: Exact Simulation and Learnabilitycited by 1
  3. 2026Characterizing the Discrete Geometry of ReLU Networkscited by 1
  4. 2025Discrete Functional Geometry of ReLU Networks via ReLU Transition Graphscited by 0