mlsanityData to 7 Oct 2026

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

arXiv 2207.07696 ↗First posted 15 Jul 2022cs.LG cs.CG math.ATcited by 21

Not on the map. Why?

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.

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

Builds on

14 of 34 references.

References · 14

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  2. 2014On the Number of Linear Regions of Deep Neural Networkscited by 378
  3. 2019Complexity of Linear Regions in Deep Networkscited by 166
  4. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
  5. 2019Deep ReLU Networks Have Surprisingly Few Activation Patternscited by 160
  6. 2017Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activationscited by 104
  7. 2018Tropical Geometry of Deep Neural Networkscited by 92
  8. 2019The Geometry of Deep Networks: Power Diagram Subdivisioncited by 53
  9. 2018On Characterizing the Capacity of Neural Networks using Algebraic Topologycited by 37
  10. 2020Empirical Studies on the Properties of Linear Regions in Deep Neural Networkscited by 36
  11. 2020On transversality of bent hyperplane arrangements and the topological expressiveness of ReLU neural networkscited by 34
  12. 2020Finding the Homology of Decision Boundaries with Active Learningcited by 12
2 more
  1. 2022Local and global topological complexity measures OF ReLU neural network functionscited by 8
  2. 2018Hyperplane Neural Codes and the Polar Complexcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 4; 2024: 5; 2025: 6; 2026: 5.

21 papers.

Sort:

  1. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  2. 2023Hidden symmetries of ReLU networkscited by 38
  3. 2022Functional dimension of feedforward ReLU neural networkscited by 20
  4. 2023ReLU Neural Networks, Polyhedral Decompositions, and Persistent Homologcited by 10
  5. 2023Topological Data Analysis for Neural Network Analysis: A Comprehensive Surveycited by 9
  6. 2025The Computational Complexity of Counting Linear Regions in ReLU Neural Networkscited by 7
  7. 2025Convexity in ReLU Neural Networks: beyond ICNNs?cited by 6
  8. 2026Most ReLU Networks Admit Identifiable Parameterscited by 5
  9. 2024Defining Neural Network Architecture through Polytope Structures of Datasetcited by 2
  10. 2025Relating Piecewise Linear Kolmogorov Arnold Networks to ReLU Networkscited by 2
  11. 2025Topological Signatures of ReLU Neural Network Activation Patternscited by 2
  12. 2026A Complete Symmetry Classification of Shallow ReLU Networkscited by 2
9 more
  1. 2026The Symmetries of Three-Layer ReLU Networkscited by 2
  2. 2024A rank decomposition for the topological classification of neural representationscited by 1
  3. 2024A Computational Tropical Geometry Framework for Neural Networkscited by 1
  4. 2024On Functional Dimension and Persistent Pseudodimensioncited by 1
  5. 2026Characterizing the Discrete Geometry of ReLU Networkscited by 1
  6. 2024Combinatorial Regularity for Relatively Perfect Discrete Morse Gradient Vector Fields of ReLU Neural Networkscited by 0
  7. 2025A Quotient Homology Theory of Representation in Neural Networkscited by 0
  8. 2025Maxout Polytopescited by 0
  9. 2026Affine Geometry of Gaussian ReLU Networks via Conditional Kac-Rice Formulascited by 0