# Algorithmic Determination of the Combinatorial Structure of the Linear Regions of ReLU Neural Networks

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 34 references that are in the map.
- First posted on arXiv 15 Jul 2022.

## Builds on (most cited first, 14 of 14)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [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)
- [Deep ReLU Networks Have Surprisingly Few Activation Patterns](https://mlsanity.com/paper/1906.00904/) (2019)
- [Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations](https://mlsanity.com/paper/1708.02691/) (2017)
- [Tropical Geometry of Deep Neural Networks](https://mlsanity.com/paper/1805.07091/) (2018)
- [The Geometry of Deep Networks: Power Diagram Subdivision](https://mlsanity.com/paper/1905.08443/) (2019)
- [On Characterizing the Capacity of Neural Networks using Algebraic Topology](https://mlsanity.com/paper/1802.04443/) (2018)
- [Empirical Studies on the Properties of Linear Regions in Deep Neural Networks](https://mlsanity.com/paper/2001.01072/) (2020)
- [On transversality of bent hyperplane arrangements and the topological expressiveness of ReLU neural networks](https://mlsanity.com/paper/2008.09052/) (2020)
- [Finding the Homology of Decision Boundaries with Active Learning](https://mlsanity.com/paper/2011.09645/) (2020)
- [Local and global topological complexity measures OF ReLU neural network functions](https://mlsanity.com/paper/2204.06062/) (2022)
- [Hyperplane Neural Codes and the Polar Complex](https://mlsanity.com/paper/1801.02304/) (2018)

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

- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Hidden symmetries of ReLU networks](https://mlsanity.com/paper/2306.06179/) (2023)
- [Functional dimension of feedforward ReLU neural networks](https://mlsanity.com/paper/2209.04036/) (2022)
- [ReLU Neural Networks, Polyhedral Decompositions, and Persistent Homolog](https://mlsanity.com/paper/2306.17418/) (2023)
- [Topological Data Analysis for Neural Network Analysis: A Comprehensive Survey](https://mlsanity.com/paper/2312.05840/) (2023)
- [The Computational Complexity of Counting Linear Regions in ReLU Neural Networks](https://mlsanity.com/paper/2505.16716/) (2025)
- [Convexity in ReLU Neural Networks: beyond ICNNs?](https://mlsanity.com/paper/2501.03017/) (2025)
- [Most ReLU Networks Admit Identifiable Parameters](https://mlsanity.com/paper/2605.03601/) (2026)
- [A Complete Symmetry Classification of Shallow ReLU Networks](https://mlsanity.com/paper/2604.14037/) (2026)
- [The Symmetries of Three-Layer ReLU Networks](https://mlsanity.com/paper/2605.18319/) (2026)
- [Defining Neural Network Architecture through Polytope Structures of Dataset](https://mlsanity.com/paper/2402.02407/) (2024)
- [Relating Piecewise Linear Kolmogorov Arnold Networks to ReLU Networks](https://mlsanity.com/paper/2503.01702/) (2025)
- [Topological Signatures of ReLU Neural Network Activation Patterns](https://mlsanity.com/paper/2510.12700/) (2025)
- [A rank decomposition for the topological classification of neural representations](https://mlsanity.com/paper/2404.19710/) (2024)
- [A Computational Tropical Geometry Framework for Neural Networks](https://mlsanity.com/paper/2405.20174/) (2024)
- [On Functional Dimension and Persistent Pseudodimension](https://mlsanity.com/paper/2410.17191/) (2024)
- [A Quotient Homology Theory of Representation in Neural Networks](https://mlsanity.com/paper/2502.01360/) (2025)
- [Characterizing the Discrete Geometry of ReLU Networks](https://mlsanity.com/paper/2606.07728/) (2026)
- [Combinatorial Regularity for Relatively Perfect Discrete Morse Gradient Vector Fields of ReLU Neural Networks](https://mlsanity.com/paper/2412.18005/) (2024)
- [Maxout Polytopes](https://mlsanity.com/paper/2509.21286/) (2025)
- [Functional Similarity Metric for Neural Networks: Overcoming Parametric Ambiguity via Activation Region Analysis](https://mlsanity.com/paper/2604.16426/) (2026)
- [Affine Geometry of Gaussian ReLU Networks via Conditional Kac-Rice Formulas](https://mlsanity.com/paper/2609.32695/) (2026)

## Abstract (arXiv)

We algorithmically determine the regions and facets of all dimensions of the canonical polyhedral complex, the universal object into which a ReLU network decomposes its input space. We show that the locations of the vertices of the canonical polyhedral complex along with their signs with respect to layer maps determine the full facet structure across all dimensions. We present an algorithm which calculates this full combinatorial structure, making use of our theorems that the dual complex to the canonical polyhedral complex is cubical and it possesses a multiplication compatible with its facet structure. The resulting algorithm is numerically stable, polynomial time in the number of intermediate neurons, and obtains accurate information across all dimensions. This permits us to obtain, for example, the true topology of the decision boundaries of networks with low-dimensional inputs. We run empirics on such networks at initialization, finding that width alone does not increase observed topology, but width in the presence of depth does. Source code for our algorithms is accessible online at https://github.com/mmasden/canonicalpoly.