# The Geometry of ReLU Networks through the ReLU Transition Graph

arXiv: https://arxiv.org/abs/2505.11692 · HTML: https://mlsanity.com/paper/2505.11692/

## 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 (most cited first, 14 of 14)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [On the Expressive Power of Deep Neural Networks](https://mlsanity.com/paper/1606.05336/) (2016)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Exponential expressivity in deep neural networks through transient chaos](https://mlsanity.com/paper/1606.05340/) (2016)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [Sensitivity and Generalization in Neural Networks: an Empirical Study](https://mlsanity.com/paper/1802.08760/) (2018)
- [Complexity of Linear Regions in Deep Networks](https://mlsanity.com/paper/1901.09021/) (2019)
- [Bounding and Counting Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1711.02114/) (2017)
- [Approximating Continuous Functions by ReLU Nets of Minimal Width](https://mlsanity.com/paper/1710.11278/) (2017)
- [On Characterizing the Capacity of Neural Networks using Algebraic Topology](https://mlsanity.com/paper/1802.04443/) (2018)

## Built on by (most cited first, 4 of 4)

- [A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networks](https://mlsanity.com/paper/2505.24110/) (2025)
- [Symbolic Feedforward Networks for Probabilistic Finite Automata: Exact Simulation and Learnability](https://mlsanity.com/paper/2509.10034/) (2025)
- [Characterizing the Discrete Geometry of ReLU Networks](https://mlsanity.com/paper/2606.07728/) (2026)
- [Discrete Functional Geometry of ReLU Networks via ReLU Transition Graphs](https://mlsanity.com/paper/2509.03056/) (2025)

## 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.