# Polyhedral Complex Extraction from ReLU Networks using Edge Subdivision

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 39 references that are in the map.
- First posted on arXiv 12 Jun 2023.

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

- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [Why ReLU networks yield high-confidence predictions far away from the training data and how to mitigate the problem](https://mlsanity.com/paper/1812.05720/) (2018)
- [On the Expressive Power of Deep Neural Networks](https://mlsanity.com/paper/1606.05336/) (2016)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [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)
- [On the number of response regions of deep feed forward networks with piece-wise linear activations](https://mlsanity.com/paper/1312.6098/) (2013)
- [Representation Benefits of Deep Feedforward Networks](https://mlsanity.com/paper/1509.08101/) (2015)
- [Reverse-Engineering Deep ReLU Networks](https://mlsanity.com/paper/1910.00744/) (2019)
- [Mad Max: Affine Spline Insights into Deep Learning](https://mlsanity.com/paper/1805.06576/) (2018)
- [The Geometry of Deep Networks: Power Diagram Subdivision](https://mlsanity.com/paper/1905.08443/) (2019)
- [On transversality of bent hyperplane arrangements and the topological expressiveness of ReLU neural networks](https://mlsanity.com/paper/2008.09052/) (2020)
- [SplineCam: Exact Visualization and Characterization of Deep Network Geometry and Decision Boundaries](https://mlsanity.com/paper/2302.12828/) (2023)
- [Provable Certificates for Adversarial Examples: Fitting a Ball in the Union of Polytopes](https://mlsanity.com/paper/1903.08778/) (2019)
- [POLICE: Provably Optimal Linear Constraint Enforcement for Deep Neural Networks](https://mlsanity.com/paper/2211.01340/) (2022)
- [Analytic Marching: An Analytic Meshing Solution from Deep Implicit Surface Networks](https://mlsanity.com/paper/2002.06597/) (2020)
- [Max-Affine Spline Insights into Deep Generative Networks](https://mlsanity.com/paper/2002.11912/) (2020)
- [Locally Linear Attributes of ReLU Neural Networks](https://mlsanity.com/paper/2012.01940/) (2020)
- [Learning and Meshing from Deep Implicit Surface Networks Using an Efficient Implementation of Analytic Marching](https://mlsanity.com/paper/2106.10031/) (2021)
- [Batch Normalization Explained](https://mlsanity.com/paper/2209.14778/) (2022)
- [WarpCore: A Library for fast Hash Tables on GPUs](https://mlsanity.com/paper/2009.07914/) (2020)

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

- [Convexity in ReLU Neural Networks: beyond ICNNs?](https://mlsanity.com/paper/2501.03017/) (2025)
- [Marching Neurons: Accurate Surface Extraction for Neural Implicit Shapes](https://mlsanity.com/paper/2509.21007/) (2025)
- [Defining Neural Network Architecture through Polytope Structures of Dataset](https://mlsanity.com/paper/2402.02407/) (2024)
- [Exact Upper and Lower Bounds for the Output Distribution of Neural Networks with Random Inputs](https://mlsanity.com/paper/2502.11672/) (2025)
- [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)
- [Polyhedral Complex Derivation from Piecewise Trilinear Networks](https://mlsanity.com/paper/2402.10403/) (2024)
- [Training-Time Batch Normalization Reshapes Local Partition Geometry in Piecewise-Affine Networks](https://mlsanity.com/paper/2605.04946/) (2026)
- [AffineLens: Capturing the Continuous Piecewise Affine Functions of Neural Networks](https://mlsanity.com/paper/2605.06218/) (2026)
- [Region Seeding via Pre-Activation Regularization: A Geometric View of Piecewise Affine Neural Networks](https://mlsanity.com/paper/2605.06300/) (2026)
- [Characterizing the Discrete Geometry of ReLU Networks](https://mlsanity.com/paper/2606.07728/) (2026)
- [Implicit Hypersurface Approximation Capacity in Deep ReLU Networks](https://mlsanity.com/paper/2407.03851/) (2024)
- [TetraSDF: Analytic Isosurface Extraction with Multi-resolution Tetrahedral Grid](https://mlsanity.com/paper/2511.16273/) (2025)
- [Expressivity Saturation: Reduced Affine Region Usage Under Increasing Task Complexity](https://mlsanity.com/paper/2606.21687/) (2026)

## Abstract (arXiv)

A neural network consisting of piecewise affine building blocks, such as fully-connected layers and ReLU activations, is itself a piecewise affine function supported on a polyhedral complex. This complex has been previously studied to characterize theoretical properties of neural networks, but, in practice, extracting it remains a challenge due to its high combinatorial complexity. A natural idea described in previous works is to subdivide the regions via intersections with hyperplanes induced by each neuron. However, we argue that this view leads to computational redundancy. Instead of regions, we propose to subdivide edges, leading to a novel method for polyhedral complex extraction. A key to this are sign-vectors, which encode the combinatorial structure of the complex. Our approach allows to use standard tensor operations on a GPU, taking seconds for millions of cells on a consumer grade machine. Motivated by the growing interest in neural shape representation, we use the speed and differentiability of our method to optimize geometric properties of the complex. The code is available at https://github.com/arturs-berzins/relu_edge_subdivision .