Characterizing the Discrete Geometry of ReLU Networks

• URL: http://arxiv.org/abs/2606.07728v1
• Date: Fri, 05 Jun 2026 17:36:19 GMT
• Title: Characterizing the Discrete Geometry of ReLU Networks
• Abstract summary: ReLU networks define continuous piecewise-linear functions and their linear regions are polyhedra in the input space.<n>We show that the way these regions fit together is fundamental to the behavior of the network.<n>We prove new theoretical results about these complexes that hold for all fully-connected ReLU networks.
• Score: 4.716880809392674
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: It is well established that ReLU networks define continuous piecewise-linear functions, and that their linear regions are polyhedra in the input space. These regions form a complex that fully partitions the input space. The way these regions fit together is fundamental to the behavior of the network, as nonlinearities occur only at the boundaries where these regions connect. However, relatively little is known about the geometry of these complexes beyond bounds on the total number of regions, and calculating the complex exactly is intractable for most networks. In this work, we prove new theoretical results about these complexes that hold for all fully-connected ReLU networks, specifically about their connectivity graphs in which nodes correspond to regions and edges exist between each pair of regions connected by a face. We find that the average degree of this graph is upper bounded by twice the input dimension regardless of the width and depth of the network, and that the diameter of this graph has an upper bound that does not depend on input dimension, despite the number of regions increasing exponentially with input dimension. We corroborate our findings through experiments with networks trained on both synthetic and real-world data, which provide additional insight into the geometry of ReLU networks. Code to reproduce our results can be found at https://github.com/bl-ake/ICLR-2026.

Related papers

• Expressivity Saturation: Reduced Affine Region Usage Under Increasing Task Complexity [5.366707531676941]
  Piecewise-affine neural networks implement continuous piecewise-affine maps.<n>We study the gap between theoretical region capacity and the affine regions realized after training.
  arXiv  Detail & Related papers  (2026-06-19T18:55:46Z)
• SAND: Spatially Adaptive Network Depth for Fast Sampling of Neural Implicit Surfaces [91.71563221166417]
  Implicit neural representations are powerful for geometric modeling, but their practical use is often limited by the high computational cost.<n>We propose an efficient neural implicit geometry representation framework with spatially adaptive network depth.
  arXiv  Detail & Related papers  (2026-04-15T14:14:17Z)
• The Inductive Bias of Convolutional Neural Networks: Locality and Weight Sharing Reshape Implicit Regularization [57.37943479039033]
  We study how architectural inductive bias reshapes the implicit regularization induced by the edge-of-stability phenomenon in gradient descent.<n>We show that locality and weight sharing fundamentally change this picture.
  arXiv  Detail & Related papers  (2026-03-05T04:50:51Z)
• The Computational Complexity of Counting Linear Regions in ReLU Neural Networks [9.31624649785042]
  There exist many different definitions of what a linear region actually is.<n>We analyze the computational complexity of counting the number of such regions for the various definitions.<n>On the algorithmic side, we demonstrate that counting linear regions can at least be achieved in space for some common definitions.
  arXiv  Detail & Related papers  (2025-05-22T14:25:12Z)
• Defining Neural Network Architecture through Polytope Structures of Dataset [53.512432492636236]
  This paper defines upper and lower bounds for neural network widths, which are informed by the polytope structure of the dataset in question. We develop an algorithm to investigate a converse situation where the polytope structure of a dataset can be inferred from its corresponding trained neural networks. It is established that popular datasets such as MNIST, Fashion-MNIST, and CIFAR10 can be efficiently encapsulated using no more than two polytopes with a small number of faces.
  arXiv  Detail & Related papers  (2024-02-04T08:57:42Z)
• Data Topology-Dependent Upper Bounds of Neural Network Widths [52.58441144171022]
  We first show that a three-layer neural network can be designed to approximate an indicator function over a compact set. This is then extended to a simplicial complex, deriving width upper bounds based on its topological structure. We prove the universal approximation property of three-layer ReLU networks using our topological approach.
  arXiv  Detail & Related papers  (2023-05-25T14:17:15Z)
• Algorithmic Determination of the Combinatorial Structure of the Linear Regions of ReLU Neural Networks [0.0]
  We determine the regions and facets of all dimensions of the canonical polyhedral complex. We present an algorithm which calculates this full canonical structure. The resulting algorithm is numerically stable, time in the number of intermediate neurons, and obtains accurate information across all dimensions.
  arXiv  Detail & Related papers  (2022-07-15T18:36:12Z)
• On the Number of Regions of Piecewise Linear Neural Networks [16.78532039510369]
  Many feedforward neural networks (NNs) generate continuous and piecewise-linear (CPWL) mappings. The number of these so-called linear regions offers a natural metric to characterize the expressiveness of CPWL NNs. We introduce a complementary framework to estimate the average number of linear regions produced by a CPWL NN.
  arXiv  Detail & Related papers  (2022-06-17T08:17:28Z)
• On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias [50.84569563188485]
  We show that gradient flow converges in direction when labels are determined by the sign of a target network with $r$ neurons. Our result may already hold for mild over- parameterization, where the width is $tildemathcalO(r)$ and independent of the sample size.
  arXiv  Detail & Related papers  (2022-05-18T16:57:10Z)
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks [56.084798078072396]
  We take a step towards closing the gap between theory and practice by significantly improving the known theoretical bounds on both the network width and the convergence time. We show that convergence to a global minimum is guaranteed for networks with quadratic widths in the sample size and linear in their depth at a time logarithmic in both. Our analysis and convergence bounds are derived via the construction of a surrogate network with fixed activation patterns that can be transformed at any time to an equivalent ReLU network of a reasonable size.
  arXiv  Detail & Related papers  (2021-01-12T00:40:45Z)
• A General Computational Framework to Measure the Expressiveness of Complex Networks Using a Tighter Upper Bound of Linear Regions [13.030269373463168]
  The upper bound of regions number partitioned by a rec-tifier network, instead of the number itself, is a more practical measurement ofexpressiveness of a DNN. We propose a new and tighter up-per bound regions number for any network structures. Our experiments show our upper bound is tighterthan existing ones, and explain why skip connections and residual structures can improve network performance.
  arXiv  Detail & Related papers  (2020-12-08T14:01:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.