Characterizing the Discrete Geometry of ReLU Networks
Authors: Blake B. Gaines
Jinbo Bi
Venue: ICLR 2026 Oral (2026)
Keywords: Polyhedrons
Geometry
ReLU
Activations
Primary area: learning theory
TL;DR: We describe the geometry of the polyhedral complexes defined by the linear regions of ReLU networks, both by theoretically bounding their connectivity and diameter and by empirically characterizing it using experiments on trained networks.

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.

Published as a conference paper at ICLR 2026
CHARACTERIZING RELU NETWORKS
THE DISCRETE GEOMETRY OF
Blake B. Gaines
Jinbo Bi*
Department of Computer Science University of Connecticut bl lakee ga hes@uconn..ee edu
Department of Computer Science University of Connecticut j inbbo bi www.uuuuuc @uconu edu
ABSTRACT
is well established that ReLU networks define continuous piecewise-lines fune- tions, 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 together is fundamental to the behavior of the network, 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 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 re- gions connected by 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 net- work, 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 ht https::// // /gi hub. com/ /b1 /ICRR- 2206.
INTRODUCTION
Fully-connected networks with Rectified Linear Unit (ReLU) activations have become ubiquitous in recent years. These networks realize piecewise linear functions, with each "piece" defined on a poly- hedron in the input space illustrated in Fig. la (Grigsby & Lindsey, 2022; Grigsby et al., 2024). These functions can be incredibly complex and have universal approximation power if sufficiently wide or deep (Huang, 2020). Even work bounding the maximum number of regions defined by a given architecture acchtecture--alraddyy spans over a decade (Montufar al., 2014; Goujon et al., 2024). Since that work began, it has generated signif- icant interest in other topics related to how ReLU networks divide the input space. The geometry of ReLU networks is defined both by the number of polyhedral regions and the way they connect to each other to form a polyhedral complex (Fig. lb). Existing work that focuses on the number of regions does not describe their arrangement (Pascanu al., 2014; Montúfar et al., 2022: Goujon et al., 2024). These works show that investigating specific properties of the complex (e.g., defining the boundaries of individual regions, calculating paths from one region another) can be intractable because the number of regions grows exponentially with respect to the input dimension and network size (Hanin& Rolnick, 2019b). Here we attempt to fill the gap the middle and establish general properties about the arrangement of these regions that hold regardless of network size and the actual values of network weights.
of the more basic questions about these networks
This work is motivated by the wide variety of research areas that leverage the polyhedral geom- etry of neural networks. These include explainability (Zhu et al., 2023; Hu, 2021), expressivity (Raghu et al., 2017), error prediction (Ji et al., 2022; Lehmann & Ebner, 2022; Daróczy, 2020),
"Corresponding Author

---

Published as a conference paper at ICLR 2026
Average: 3.27
Number Regions
LLL
8
f xt.)
6
#2
4
2
37
222
0
3
4
(a) ReLU Network Oulput
(b) Polyhedral Complex
(c) Connectivity Graph
(d) Degree Distribution
Figure I: (a) An example ReLU network with a 2-dimensional input. (b) The corresponding polyhe- dral complex where region has neighbors B, C, D, and E. (c) The connectivity graph where nodes represent regions and edges link neighboring regions (so region A has degree 4). (d) A histogram of the number of neighbors for each region, or equivalently the degrees of the connectivity graph.
robustness (Tran et al., 2019; Yang et al., 2020; Jamil et al., 2022), and even toxicity in large lan- guage models (Balestriero al., 2024). It also allows the networks to be encoded as mixed-intees programs for verification (Botoeva et al., 2020; Cheng et al., 2017; Bunel et al., 2018) and inverse de- sign (Ansari et al., 2022). The relationship between polyhedral regions and network activation states has also been applied to data compression (He et al., 2021), representation and clustering (Craighero al., 2020), and open set detection (Jamil al., 2023). A more detailed review of related work can be found in Appendix A.
Our analysis builds on the topological perspective of ReLU network geometry, and follows the same assumptions as Masden (2025). Our results are best expressed in terms of the complex's 's connectiv- ity graph (Fig. Ic). where nodes correspond to polyhedral regions and edges exist between regions that have a shared face (Liu et al., 2023b). The degree of node in the graph corresponds to the number faces of its region, each which connects to unique neighboring region. Fig. 1d plots histogram of the node degrees and shows the average degree of the connectivity graph in Fig. Ic. The diameter of this graph (the longest shortest-pale patte distance between any pair nodes in the graph) corresponds to the number of faces one has cross reach polyhedron from any other polyhedron. Our work provides fundamental links between network architecture and connectivity graph topology. Recent work has analyzed the connectivity graph to characterize network properties such as VC-Dimension and the distribution of region volumes (Dhayalkar, 2025). Notably, the work in (Fan al., 2024) includes several results bounding the average number of faces of the polyhedra from above, but with crucial assumptions for the ReLU networks (c.g., no bias terms or low rank in the first hidden layer's weight matrix) and their bounds are asymptotic with respect to the size of the network. In this work, we will bound the same quantity for networks regardless of architecture, both from above and (for networks with least d neurons in any configuration) below. We will then further characterize the complex by deriving similar bounds for the intersections of the regions, and bound the connectivity graph diameter from above and below, which provides additional insight into how the activation regions fit together. Our main contributions are follows:
Theoretical Properties
Empirical Observations
A fully-connected ReLU network with input dimension maximum layer width m, and depth & creates polyhedral complex C in Rd that, with probability (almost everywhere) over all possible network weights, satisfies:
Experimental results with networks of different sizes trained on synthetic data and three bench- mark datasets show that:
1. The average degree of the connectivity graph quickly approaches the upper bound the size of the network increases.
1. The average degree of the connectivity graph is at most 2d.
2. The number of neighbors for every polyhe- dral region follows unimodal distribution that skews right and peaks just below 2d.
2. This average approaches the upper bound as the size of the network increases.
3. The diameter of the connectivity graph is bounded above by (m 1) regardless of the value of d.
Regions that contain data points tend to be more connected on average compared those that do not.
2

---

Published as a conference paper at ICLR 2026
2 PRELIMINARIES
Sign Sequences: Let f: == Rat be a fully-connected feedforward ReLU network in which each hidden neuron i performs an affine transformation w/ x + by on its input x and then applies the ReLU activation, where x.h is the output of the previous layer, and w; and b, are the trainable parameters of this neuron. Let n denote the total number of hidden neurons in f. We start by intro- ducing how, with probability 1 over possible network weights, the activation states of the neurons in network can be uniquely represented by sign sequences (Masden, 2025). For a point æ in the input space, when passing through the network and reaching the ith neuron, if w x + b, > O, then the sign of this neuron S(x); = and the ReLU function outputs the value of w x + b;; the affine function is equal to or less than 0, then S(x); = 0 or -1 respectively, and the ReLU outputs Thus, x receives a sign sequence S(x) E {-1, 0, 1)", a vector of length n indicating the sign of each neuron's 's output before applying the activation function.
Bent Hyperplanes: If i in the first hidden layer, then x.: is the network's input, and all inputs x with S(x), = 0 lie on the hyperplane {x E H w x + b; = =O.. When i is neuron from a later layer, the set of inputs with w/ =h - b, = 0 (i.e., S(x); = 0) is more complex, because x will have been computed by the continuous piecewise- the input points for which S(r); O form a level set of this function. We call this set the neuron's 's Bent Hyperplane (BH) following convention (Hanin & Rolnick, 2019b; Masden, 2025), although unlike a hyperplane, a BH can intersect itself and even be disconnected.
function represented by the previous layers, and
Fig. 2 shows an example of BHs created by a network with an input of cl = 2 and 2 hidden ReLU layers where 3 neurons are in layer 1 (corresponding to hyperplanes, which we also call BHs 1-3 for notational convenience) and 1 neuron in layer 2 (cor- responding to BH 4). Each blue arrow in Fig. 2 indicates the orientation of BH; pointing towards the of the neuron i is positive (i.e., S(x); = 1). BHs 1-3 intersect to form 7 regions. BH 4 intersects 6 of them, and in each area, BH 4 is a segment of a hyperplane. Whenever BH 4 crosses a BH j in the first layer, one of the entries of its input x changes its activation state (switching between w/ + b, and 0). This causes the BH to bend. In this example, it eventually intersects itself.
(1,11,1,1)
where the output
(0, O1 0)
1
(1. -1,11110)
Figure 2: A polyhedral complex.
The BH of neuron (where S(x); = 0) forms a boundary that divides the input space into two parts where S(r); 1 and S(x), = -1 Thus, the sign sequence of a region can also be interpreted as a list describing which "side" of each BH it lies on. All of the BHs of neurons in previous layers partition the input space into disjoint regions, in each of which, w/ p: + b, collapses into an affine function in the input space (say DT'x= x 33 for some &; E Rd and B, E R), the segment of the BH within an area lies a hyperplane in the input space o. x + 3g = 0. This hyperplane subdivides the regions it intersects into two smaller regions that differ in the activation state of neuron i. For instance, Fig. shows that BH 4 divides the 6 regions formed by intersections of BHs 1-3 into 12 smaller regions.
From this point forward, all statements about ReLU networks will make the same assumptions as in (Masden, 2025) to avoid degenerate weight assignments. These will ensure that at most d BHs intersect at a point, and that the sections of BHs are never perfectly parallel each other. As proven in that work, these assumptions will hold on all but a measure-zero set of parameter assignments for a given architecture. Appendix B provides rigorous definitions of these assumptions.
A polyhedral complex is set of polyhedra (cells) that is closed under in- tersection (e.g., the complex Fig. includes not only the polygons as elements but also the line segments where pairs of polyhedra intersect and the vertices where four polygons intersect), and taking faces (c.g., the complex in Fig. includes the line segments enclosing each polyhedron and the vertices enclosing each line segment). A k-cell is an element of polyhedral complex with affine span Is S d, that is, a polyhedral set whose elements span a k-dimensional affine subspace of Rd. BHs of neural network form the boundaries of the network's 's d-cells (the maximal regions in which the network's 's mapping is affine). which intersect to generate the polyhedral complex C of the network (Grigsby& & Lindsey, 2022). Within each cell of C, the network's behavior is affine. When
Polyhedral Complex:
3

---

Published as a conference paper at ICLR 2026
k < d, the k-celll of this complex are each contained by the intersection of d dd-K BHs. For the com- plex in Fig. 2, the orange 2-cell is not contained in any BHs because d k = 0, a 1-cell is contained by BH (e.g., the orange line segment is part of BH 4) and a O-cell is contained in the intersection of two BHs (e.g., the highlighted vertex is the intersection of BHs 1 and 4). Accordingly, the BH of neuron i can be considered as the union of the (d 1)-cells with single 0 in the ith position of their sign sequences. For example, in Fig. 2, BH 4 is formed by the ring of six line segments (I-cells) with a in position of their sign sequences. We define the "faces" of a k-cell as the (k: 1)-cllls it contains (these are often called "facets" in the relevant literature). In the connectivity graph, the k-cells of C are represented by (d k) >>yperruee subgraphs, and the collection of edges corresponding to the 1-cells of each BH form cut.
An important property of network's canonical polyhedral complex is that if it restricted to the cells lying in or on one side of single neuron's BH (or equivalently, an element of the sign sequences is fixed), the resulting substructure is still polyhedral complex. Although it no longer corresponds to ReLU network, we still call it ReLU complex because it is still polyhedral complex with cells defined by BHs, so several of the results in the next section will still apply. In the following discussion, the dimension of ReLU (sub)complex will refer to the maximum dimension of its cells instead of the dimension of the ambient space in which it is embedded (e.g. a BH of a 2-dimensional ReLU complex is a I-dimensional ReL.U complex).
The polyhedral complex can be described in terms of sign sequences, be- cause in the interior of any k-cell, the sign sequence of every point is exactly the same. Furthermore, the sign sequences of a k-cell contain exactly d - A zero elements corresponding to the d - k BHs whose intersection contains the cell as a subset and & nonzero elements corresponding to BHs that either contain a single face of the cell or do not intersect the cell at all. For example, in Fig. 2, the orange 1-cell with sign sequence (1, -1, 1, 0) is contained by BH 4 so it has 0 in this position, its faces are the vertices on each end contained by BHs 2 and 3 respectively, and BH 1 does not intersect the cell at all, so all three are nonzero in the sign sequence. With the aforementioned basic assump- tions on the network weights, the work in (Masden, 2025) proves that every cell of a ReL.U complex has a unique sign sequence, that is, the mapping from cells to sign sequences S: + {-1,0, 0, 13" is well-defined and injective. The connectivity graph can be equivalently defined in terms of the sign sequence complex, with nodes for the sign sequences of d-cells (the ones with no zeros) and edges between sequences that differ by one element.
Sign Sequence Complex:
3 THEORETICAL RESULTS ON NETWORK GEOMETRY
We examine how the cells in a ReLU complex are connected with each other, how many neighbors cell can have average, and whether or not the number of neighbors varies with respect to the depth and width of the network. Proof outlines are given here while detailed proofs are in Appendix B. The cells in a ReLU complex and the number of their faces may depend on the specific network architecture and values of the network weights However, we prove that the average number of neighbors for any polyhedral region can be upper bounded by 2d regardless of the depth and width of the network. In ReLU complex, counting the faces of cells is the same as counting their neighbors. For d-cell, each face is contained in a unique BH, and across each face unique neighboring polyhedron that has the same sign sequence except that the sign corresponding to the crossed BH is flipped. More generally, we prove the following theorem for any k-cells of a ReLU complex.
Theorem 3.1. For a ReLU complex in d-dimensional input space, the average number faces of k--ell is at most 2k for l 1,2.....4
An earlier work proves this theorem for hyperplane arrangements (Fukuda et al., 1991), which only applies to the polyhedral complexes of single-layer networks, but the proof does not generalize to deep ReI.U network complexes formed by BH arrangements. We employ the 1-1 mapping between cells and sign sequences to prove that the theorem also holds true for complexes of deep ReLU networks.
Let C be ReLU complex corresponding to a network f. Denote the BH of neuron by h;s which contains a set of k-cells of l < d. specifically h, = {c E C: S(c), = 03. Then, we use C h, to denote the complex that results from removing all cells contained in the BH of neuron and joining all pairs of cells sharing one of the faces that were removed. Fig. 3a illustrates C - h; with C from Fig. 2 and BH 4 as hy- The connectivity graph of C h2 can be obtained by contracting every edge
4

---

Published as a conference paper at ICLR 2026
3
3
2
(1),-1,1
(0, L.,1
(,1,
1
(a) C h4
(b) Cells Categorized with
(c) Connectivity Graph
Figure 3: (a) The complex in Fig. 2 with BH 4 removed. (b) BH 4 is added and cells are categorized according to Lemma 3.2 with those in Categories I, 2, and shown in blue, green, and red. respec- tively. (c) Connectivity graph with nodes and edges colored according to their corresponding cells.
corresponding to (d - 1)-llll contained in h, (i.e., removing each edge and combining the two end nodes into one, keeping their connections to other nodes in the graph). As a result, every two k-cells previously split by h2 now fused into single new k-cell. Any cells that do not intersect h; remain the same in the new complex C -hi-
Lemma 3.2. For any neuron i in S, each k-cell of C falls into exactly one of the following cate- gories:
Category 1: e is a cell of h;
Category 2: e a cell of - h;
Category 3: is one of the two k--elll formed when k-cell in C h; is separated by h;
We outline our full proof here. the sign sequence of e, the element S(c); is either zero or nonzero. If it is zero, then can only be in Category 1. If it is nonzero, we need to check if e intersects h;. This the case if changing the cell's sign sequence so that S(c), = yields new sign sequence that matches Category I cell in C. Then, flipping S(c); yields the sign sequence of k-cell neighbor of c, so is in Category 3. Otherwise, if the new sign sequence not an element of C, then h; does not contain
form a face of c, is in Category 2.
Fig. 3b and Fig. 3e show the categorization of k-cells (k = 0, 1, 2) in the polyhedral complex from Fig. 2 when h, corresponds BH 4. The blue line segments and vertices in Fig. 3b are the Category 1- and O-cells respectively. and the 4th element of their sign sequences is 0. The green 2-, 1- and O-cells are in C h4 because they do not change when h, removed. For such cell, if we zero out the 4th element of their sign sequence (e.g., the 2-cell in the center with a sequence 10,0), 0)) does not exist in S(C). The red
the resulting sequence (e.g., (-1,-1, 11,,,11,000 2- and 1-cells are in Category 3 because h4 contains one face of each of those cells. As an example, the leftmost 2-cell has the sign sequence (-1, 11, 1. 1), and after setting S(c), 0, -,,,,,1,,,, corresponds to the line segment of h; forming its right boundary. Note that the proof of Lemma 3.2 also works for ReI.U subcomplexes formed by fixing one of the sign sequence elements, and these subcomplexes cannot include only half of pair of Category 3 cells since their sign sequences can only differ at the position the removed BH i. Alternate colorings for the same complex based on different choices of i and restrictions to different subcomplexes are included in Appendix C.
(-1,-1,-1,-1))
h, is a neuron from the last ReLU layer, the complex C- h1 corresponds to another ReLU network, but directly removing neuron from an early layer may not result in complex corresponding to any ReLU network. As a result, we can break down the problem of counting cells (including faces) in the ReLU complex by iteratively removing neurons starting from the last layer and counting the number cells that disappear. Let N₂ (C) be the total number of k-cells in C. Based on Lemma 3.2, first count
(C) equals the sum of the numbers of k-cells in each category. To evaluate (C), the k-cells in h; and C - h; separately, and then double count those in C - h4 that are split by h;- To count the split cells, we can just count (k 1)-cells in h; which each divide one of them. For example, compare Fig. 3a and Fig. 3b. The six 1-cells in h4 split the six 2-cells in Fig. 3a to add six more 2-cells in Fig. 3b. Similarly, the six O-cells in hy also split six 1-cells.
Lemma 3.3. For = 1,2,....d. d.
(C Na(hs) + NN(C h.) N (14)
5

---

Published as a conference paper at ICLR 2026
The first term in the sum accounts for the Category k-cells in C, the second term accounts for all the Category 2 cells and half the Category 3 cells, and the third term accounts for the other half of the Category 3 cells. There are no Category d-cells in C because h2 by definition only contains cells up dimension d - 1, when k = d, the first term Nu (h,) is always O. The two lemmas lead to the following special case of Theorem 3.1 for k =
Theorem 3.4. [Upper Bound] The average number faces of d-cell of C in R (i.e., the average degree of the connectivity graph) is at most 2d.
Here provide an outline of proof (see Appendix B for detailed proof). Each (d 1) cell forms a face between two d-cells because the single 0 in its corresponding sign sequence can be set to -1 to get the sign sequences of the two d-cells. Thus, the sum of the numbers of faces of all d-cells is just twice the total count of (d-1l)s in C, so the average number of faces of a d-cell 2N²-1(C).
Na(C) Using Lemma 3.3, prove 2Nz-1(C) 2d by mathematical induction the number Na(C)
of BHs n in the complex and d. By assuming that the upper bound holds for (n - 1, d - 1) and (n - d)) we prove that the upper bound holds for any complex with (n, d). The proof of Theorem 3.1 then follows by applying the lemmas to groups k-cells whose sign sequences have exactly d
zeros the same positions, that is, restricting the complex to the intersections of d k BHs and applying the lemmas to the resulting subcomplex.
It is straightforward establish the following lower bound the degree of individual nodes, which then bounds the overall average degree of the ReLU complex graph.
Theorem 3.5. [Lower Bound] If ReLU network has nh neurons in the first hidden layer, every d-cell of C has at least min(n1, d) neighbors, and thus the average degree of the connectivity graph least min(n1, d).
3.1 ASYMPTOTIC BEHAVIOR
To study how connectivity properties change network size increases, we can create sequences of networks by adding new ReLU neurons to the last layer or a new layer after it. We use C., to denote the complex after n neurons have been added. We characterize these sequences with the following theorems, which show that the average number of faces grows monotonically and that the bound in Theorem 3.1 is tight respectively.
Theorem 3.6. The average number of faces of d-cells in Cn increases monotonically in terms of n. Theorem 3.7. Let f be shullow network that has only one hidden layer with nodes. When goes to infinity. the average number of faces of its d-cells converges exactly to 2d. That is
2Na-1(Cn) 2d.
lim 12-000
Na(C.)
In our experiments in Section 5, we observe that the average number of faces also appears to ap- proach 2d the depth of the network increases.
3.2 BOUNDS ON CONNECTIVITY GRAPH DIAMETER
Let be the total number of hidden layers (depth), my be the number of nodes in layer j. j 1,...,e, and m max maxx,,,.... .me} (width). We find that,
Theorem 3.8. The diameter D of the connectivity graph is Ω (In(Na(C)) and O (m.)
The lower bound (in Q) agrees with the intuition that diameter increases with the number of regions in the complex. Although it appears as though increasing the number of neurons in the network might reduce diameter by increasing (n),, actually In (C)) grows much faster with n regardless of architecture, so the In(n) term is just attenuating the growth of this lower bound. The upper bound (in O) may rarely be reached in practice, but it interesting in that does not have to depend on the input dimension d, even though the number of the network's 's regions increases exponentially with d. We also find that this is empirically true in Section 5, as when we fix network architecture and only change the input dimension, the diameter of the resulting complexes grows almost identically.

---

Published as a conference paper at ICLR 2026
4 ALGORITHM FOR CALCULATING POLYHEDRON BOUNDARIES
To define the complex, it will be necessary to map sign sequences to their polyhedra defined by intersections of half-spaces, i.e,, systems of linear inequalities of the form 0 x + B S for i E f- We only concerned with the sign sequences of d-cells, which do not contain any zeros, that each neuron provides exactly one inequality to our system defining the polyhedron. Let s be such a sign sequence and the column vector g be the portion of that contains only signs for the neurons in layer j. Let W R and 8(3) E R denote the weights and biases in layer j of the network with input dimension Jin and output dimension Jour. We can define our polyhedron by using the following formulas to calculate the inequalities layer by layer.
Half-spaces current layer
Picking half- half-space signs
Mask for inactive neurons the previous layer
T (5) =
diag s
(i)
W
diag
ReLU و
(s(-11)
s ((i-1)
(2)
Current layer's weights
Half Half-spaces for the previous layer
360) diag (s(1) (Wolding (ReL.U (sU-11) 36-11 + ((0))
(3)
At the initial stage, (0))- Ia. b(0) = (dx 1). and ( = 1ax1. The first term on the right-hand side ensures that the inequality of each half-space is always in the same direction, regardless of whether
the neuron is active or inactive. This allows to concatenate 4(1) and (06) from each layer to get the full linear system, 4x + 3 S O.
4.1 ENUMERATING POLYHEDRA
To enumerate the maximal polyhedra and ob- tain their connectivity graph G = (V, E), we
Algorithm 1 Construction of the Connectivity Graph
will employ breadth-firs first search (BFS). We de- scribe our exact method in Algorithm 1. Start-
1: Input: Trained network f. sign sequence s
2:
Q. V. F < {s), {s}, 0
ing with valid sign sequence 8, which can be found by passing any point through the net- work, we enumerate its neighbors and add them to our graph. Neighbors are polyhedra that can be reached by crossing single BH, so their sign sequences have the opposite sign from the original polyhedron in exactly one position i, denoted as 8.4. To find the neighbors, we can calculate &. and G, as described the previous section and determine which inequalities actu- ally form the boundary of the polyhedron. We check the redundancy of each inequality by solving an LP,, performed by the SOLVELP subroutine line 6, which is given the arguments 4, for the constraint coefficient matrix, S. + e; (3, with added to the ith element to relax this constraint) for the constraint offset, and 2.. for the objective function coefficients maximize in the direction of the relaxed constraint. This LP is explained further in Appendix D. Non-redundant constraints will be violated by the optimal solution to this LP, i.e., $ x Ba,, meaning that s., gives the sign s,
3: while Q is not empty do
4:
< pQp(()
5:
for i E (O......1) ..) do 2. B. +es) 2 8_g then
6:
if SOLVELP add (s. s.,) to E
7:
8:
if s.; & V then add to Q and V end if end
9:
10: end for
11:
end while
12: return (V
quence of the neighbor of s across the BH of neuron i. For each neighbor, we add the edge between and s., the graph (line 7), and if we have not reached s. before, we add to both the graph and the search queue (line 8). In the next iteration, we can pop a new sign sequence from the queue and repeat the same process.
This traversal of polyhedra is similar to several previous works (Xu et al., 2022; Liu et al., 2023a;b), specifically the BFS in (Xu et al., 2022), but we take the additional step building up the connec- tivity graph of the polyhedral complex over the course of the search by recording when faces are polyhedra. Furthermore, when determining whether or not an element
shared with already- of sign sequence can be flipped to produce another valid sign sequence, we follow (Zhang & Wu, 2019; Fukuda, 2004) and slightly relax the corresponding inequality to reduce errors arising from insufficient numerical precision.
7

---

Published as conference paper at ICLR 2026
Hidden Layers
10
Width:
Average Number of Neighton
Number of Polyhedrons
Sannuuunaae $ Tooysoonng
10k
100
IM
10k
100
5
10
10 15 20 10 20
30
Number Neighbors
Number of ReLU Neurons
Figure 4: (Left) Distributions for the number of faces of polyhedra in ReLU networks trained on synthetic data. Each colored bar shows the number of polyhedra with a given number of faces in complexes of networks with specific width, depth, and input dimension, averaged across initializations of network weights for 5 different training datasets with standard deviation shown by the black bars. (Right) The mean of each distribution versus the number of neurons in the network, colored by dimension. Dotted lines represent upper bounds for the networks with different d.
EXPERIMENTS
To further understand the structure of ReLU complexes, we use Algorithm enumerate polyhedra for number of neural networks and construct their connectivity graphs. We then discuss how data tends to be distributed across the complex of networks after training. Additional details about the experimental setup and trained networks can be found in Appendix F. Code, data, and models used all experiments can be found at https: /github.......gg com/blmcc///c//ooo hanmbblake// Atl-aaa/IICIR-22222 ICLR-2026.
5.1 UNDERSTANDING THE BOUNDS
We start by training number networks on clustering problems generated from three isotropic Gaussians with unit variance and centers selected uniformly at random within hypercube around the origin with side length 10. We vary input dimension d, the number of hidden layers, and the width of each hidden layer. For each combination of hyperparameters, with newly generated datasets, and perform an exhaustive search compute the full complex of the network and obtain information about every region. Summary statistics for the polyhedra can be found in Table 1, and the distributions neighbor counts are visualized Fig. 4. The average number of neighbors in every complex is below the upper bound of 2d, with the overall distribution being unimodal and skewed right. We also plot the estimated connectivity graph diameter versus the upper bound from Section 3.2 in Fig. 5. We estimate the actual diameter of the complexes
perform five experiments
120
60
Dual Grophs Diameter
2
80
40
15
30
4
20
40
5
10
100 10
100
1000
100
1050
10k
Pept
Figure 5: Connectivity graph diameter vs theoretical upper bound. At each distinct value of the theoretical upper bound (abscissa), the actual diameter of 5 network complexes was estimated as described in Section 5.1. Each pair of dotted lines also encloses all (non-cstimated) values of the connectivity graph diameters from every experiment. Each subfigure shows networks with fixed width m and depth & < 4. The widths are 4 (left), 8 (middle), and 16 (right).
8

---

Published as a conference paper at ICLR 2026
Table 1: Summary statistics for the distributions in Fig. 4 with four dimensions (left) and five dimen- sions (right). Diameter for each complex is estimated as described in Section 5.1. Non-degenerate depth-1 networks always have the same number of polyhedra because their BHs are all just hyper- planes (Buck, 1943).
Dapoi
Wiith
Polytiedions
Average Degree
Diameter
Polyticdions
Average Degree
Diameter
16. 0:00
4.00:10.00
5.50:::0000
16, 1:00
4:00::0:00
5.50=
163.00:2:0000
6:28:20000
10 42
219 119.00220.00
7:23:20:00
10.75:::0.0 265
16
2517 2517000000000
7.32:40.00
22,50:0.355
6884 07--577700.. 35
9.022:0000
23,174:0141
72.60 22.70
321:10.11
19.75
5.3430025
0.30::0.53
63
1.
20:4::::44
1802.60::: 1146
8.772:0.27
21:75::: 1.06
16
42243.00 8608.12
7.72:1:006
41.10:0665
2.69 x 10 1-48766.0
9.61
42.574: 1.53
56520016
389.00E
5A52041
14.65122.22
93.00.00 3325.88
7.47:10.17
27.60:1:2.25
36591 20 12085.54
8.54:::.93
31.50
16
2.23 10 -7214281
7.22:0004
57,70:12-46
1.78 10 1,96x 10
9,78:10004
57,44:1:144 1,47
119.44
6.17::0.12
15.90:11.19
1206.70
5.50:50.75
35767 201727901-999988
7.70:20.06
37.40:1
L 10 797668.5
8.25-11.38
48,35-1:12.25
6.24 10
7.85
76.35-44.56
5.03x 10
9,80-9-0:33
by bounding each one above and below using the corresponding algorithms from (Magnien et al., 2009) and taking the midpoint. To be clear, the asymptotic bounds derived in Section 3.2 were not used to make this estimate. Across all experiments. the diameter estimates for networks with the same depth and width were almost identical across different input dimensions. Although the upper bound is rarely reached, the logic that it should be independent of input dimension appears to hold in practice. Furthermore, when width is fixed, the diameter appears to grow logarithmically with respect to our theoretical upper bound. Additional summary metrics for the complexes and results for d E [2.3] can be found in Appendix G.
5.2 TRAINING DATA AND POLYTEEDRA
We observe a difference in the distributions of neighbor counts between polyhedra that contain data and those that do not. We test networks trained on three datasets: California Housing (CC Li- cense) (Kelley Pace & Barry, 1997), MNIST (CC BY-SA 3.0 License) (Deng, 2012), and CIFARIO (MIT License) (Krizhevsky, 2009), and achieve reasonable performance for each (AUC above 0.9 or R2 above 0.6). We examine the last 3 layers of 8 neurons for MNIST and 2 layers of 64 neurons for CIFAR 10 on a diwer-dimensional hidden representation rather than the input, 5 dimensions for MNIST and 10 for CIFARIO. For California Housing, work. Details about the datasets and networks can be found in Appendix F. Algorithm 1 was used to identify all polyhedra in the complex for MNIST. For the California Housing and CIFAR10 datasets, complete enumeration of the network complex was intractable, so the search was terminated after traversing 8 million polyhedra. We then randomly sample 10,000 points from the training data. If data point does not lie in one of the polyhedra found in the initial search, we calculate the new poly- hedron that contains the point and add the 8 million that were already found. The distributions of neighbor counts for these complexes can be found in Fig. 6. Across all datasets, the neighbor counts for polyhedra containing training data tend to be higher than the upper bound for the average neighbor count of all polyhedra. Since the number of faces of any polyhedron is bounded above by n, this necessarily reduces the rightward skew of the distribution as well.
calculate the complex of the entire net-
10k
IM
1M
Number of Points
100k
1000
10k
10L
625
1000
1000
125
100
100
100
25
10
10
10
14
18
30
40
50
60
70
10
15
20
25
30
45
50
55
(a) MNIST (d=5, 24=
(b) CIFAR 10 (d=10, 1=128)
(c) CA Housing (d=8, n==128)
Figure 6: Histograms of polyhedron neighbor counts (i.e., the number of polyhedra that have a specific number of neighbors) for polyhedra that do not contain training data (gray) and ones that do (colored by total number of data points contained in those polyhedra).

---

Published as a conference paper at ICLR 2026
We also examine how neighbor counts vary according to whether polyhedra are bounded bounded, with results shown in Fig. 7. In all three experiments, we observe that polyhedra with higher numbers of neighbors each histogram, with the exception of polyhedra with d neighbors shown by the leftmost bars, which always unbounded). In addition, containing regions is higher than the overall proportion for both classification tasks (the top two histograms show darker bars than the corresponding bottom figures) but lower for the regression task (the top histogram bars have lighter colors than the bottom). For the classification tasks, the network may have to focus its complexity on the spaces between classes of data points where has to draw the decision boundary, leaving more of the data points themselves regions of the complex. On the other hand, for regression, the model focused on fitting the data points, so data points tend to lie more on bounded regions with finite function values. Additional results from these experiments are included in Appendix G.
more likely to be unbounded (darker colors toward the right of
find that the proportion of unhounded polyhedra in data-
the outer (unbounded)
100k
100k
Percent Bounded
With Data
1000
1000
1000
100
10
10
10
80%
10k
100k
100k
60%
Without Data
1000
40%
1000
1000
100
20%
10
10
10
0%
10
14
16
18
20
40
10
20
30
40
50
Number Neighboes
(a) MNIST
(b) CIFAR1O
(c) CH Reg
Figure 7: Histograms of polyhedron neighbor counts, separated into those that contain data points (top) and those that do not (bottom). The vertical axis gives the number of polyhedra and each bar is colored by the percentage of polyhedra among those with the same neighbor count that are bounded.
DISCUSSION AND FUTURE WORK
This work characterizes general geometric properties of the polyhedral complexes defined by ReLU networks. For the first time, we place bounds on both the average connectivity of this complex and its graph-theoretic diameter. We also conduct empirical studies that visualize the distributions of polyhedron connectivity, and show that training data tends to lie on polyhedra with higher-than- average connectivity.
There are several limitations to the work presented here. Further investigation is needed to fully explain why training tends to put data points in regions with higher numbers faces, and how this phenomenon is related to the network's 's behavior. Additionally, more specific network structures like convolutional layers and skip connections affect the network's geometry. Another limitation comes from the fact that results only apply to ReLU activations, and while they could be extended to other piecewise-linees activation functions, there are no imme- diate implications for networks that use nonlinear activation functions.
not yet able to describe how
Our results have implications for several active areas of study that involve the polyhedral geometry of ReLU networks. For example, the work by Ji al. (2022) places bound on empirical training error based on the spatial relationships between the regions containing the train and test data. They use Hamming distance between the sign sequences of two polyhedra as distance metric between them. However, this metric will not reflect the case where a bent hyperplane may have to be crossed multiple times when moving from one polyhedron to another. Thus, the length of the shortest path between two polyhedra in the connectivity graph is more suitable metric. If path length is used, Theorem 3.8 allows us to bound the empirical error based on the network architecture and independently of the input dimension.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Ross Anderson, Joey Huchette, Christian Tjandraatmadja, and Juan Pablo Vielma. Strong Mixed- Integer Programming Formulations for Trained Neural Networks. In Andrea Lodi and Viswanath Nagarajan (eds.), Integer Programming and Combinatorial Optimization, pp. 27-42.7222 Cham, 2019. Springer International Publishing. ISBN 978-3-030-17953-3.
Navid Ansari, Hans-Peter Seidel, and Vahid Babaei. Mixed integer neural inverse design. ACM doi: 10. 145//5
Transactions on Graphics, 41(4):15111155::44 July 2022. ISSN 0730-0301,
28223.3530083 URL https: /d1. a.m. orq/ / /te//oi///t /00i/10... 110..11555.1 1145/352822 3530083. GSCC: 0000268 4 citations (Semantic Scholar/DOI) [2024-05-300 0 citations (Crossref) [2024- 05-30].
Randall Balestriero and Richard Baraniuk. Mad Max: Affine Spline Insights Into Deep Learning. Proceedings of the IEEE, 109:704-727, 2018. URL /tttps://apaee
oxq/CorpusID: 49901088.
Randall Balestriero and richard baraniuk. A Spline Theory of Deep Learning. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 374-383. PMLR, July 2018. URL https: fitts::/proceett /ttp://pocceeeeeeooo iig.eeiddnnn......ooo ngs ml press vv80 www.saareeerrrrr 1 18b. html.
Randall Balestriero, Romain Cosentino, Behnaam Aazhang, and Richard Baraniuk. The Geometry of Deep Networks: Power Diagram Subdivision. In Neural Information Processing Systems, 2019. URL https::////
Randall Balestriero, Romain Cosentino, and Sarath Shekkizhar. Characterizing Large Language Model Geometry Helps Solve Toxicity Detection and Generation. In Forty-first International Conference on Machine Learning, 2024. URL https: http:///pperevieeeee glfcwSaks8.
Arturs Berzins. Polyhedral Complex Extraction from ReLU Networks using Edge Subdivision. In Proceedings of the 40th International Conference on Machine Learning, pp. 2234-2244, PMLR, July 2023. URL https: / http//oocceeiioeoooo ngs m press/ v202. www.bernnne..2 html.
Elena Botoeva, Panagiotis Kouvaros, Jan Kronqvist, Alessio Lomuscio, and Ruth Misener. Efficient
Verification of ReLU- Neural Networks via Dependency Analysis. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04):3291-3299 April 2020. ISSN 2374-3468, 2159- 5399. doi: 10. 10.1609/aiii http9//aai.v34iii0/ w34004.544440 5,529. URL https: //ojs aaai. org index.nexx.. php/AAA I/article/vee
5729. GSCC: 0000170 102 citations (Semantic Scholar/DOI) [2024-05- 30) 60 citations (Crossref) [2024-05-30].
R. C. Buck. Partition of Space. The American Mathematical Monthly, 50(9)5541-544 November 1943. ISSN 0002-9890, 1930-0972. doi: 10.1088000009989019443... 199999999999999111999999999 URL https: / //www.c.. www.taanndooonnnnooo com/ htc///oi//// htt////iifffooooo//////
1943.1199144)
Rudy R Bunel, IIker Turkaslan, Philip Torr, Pushmeet Kohli, and Pawan K Mudigonda. A Unified View of Piecewise Linear Neural Network Verification. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-
and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL / s. cc ctc.c//ppe_a.. http//apperrlll filffielssle ee meilesspappere pwwpppppppp///ee / fileeelll//// htt.:e/eeeeee2e33000222222200050
2 2-Paper. paf. GSCC: 0000413.
Vasileios Charisopoulos and Petros Maragos. A Tropical Approach to Neural Networks with Piece- wise Linear Activations, January 2019. URL http:://axxt..rr//bbbs...ee 08749. GSCC: 0000048 arXiv:1805.08744 [cs, stat].
Chih-Hong Cheng, Georg Nührenberg, and Harald Ruess. Maximum Resilience of Artificial Neural Networks. In Deepak D' Souza and K. Narayan Kumar (eds.), Automated Technology for Verifi- cation and Analysis, pp. 251-268, Cham, 2017. Springer International Publishing. ISBN 978-3- 319-68167-2, doi: 10. 00.10007778-... 3-11--68167----1 18. GSCC: 0000334 92 citations (Crossref) [2024-05-30] 255 citations (Semantic Scholar/DOO) [2024-05-30).
11

---

Published as a conference paper at ICLR 2026
Francesco Craighero, Fabrizio Angaroni, Alex Graudenzi, Fabio Stella, and Marco Antoniotti. In- vestigating the Compositional Structure of Deep Neural Networks. In Giuseppe Nicosia, Varun Ojha, Emanuele La Malfa, Giorgio Jansen, Vincenzo Sciacca, Panos Pardalos, Giovanni Giuf- frida, and Renato Umeton (eds.), Machine Learning, Optimization,, and Data Science, pp. 322- 334, Cham, 2020. Springer International Publishing. ISBN 778-3--030-64883-0.
Bálint Daróczy. Tangent Space Sensitivity and Distribution of Linear Regions in ReLU Net- works, June 2020. URL http: http://arxiv..ogg/ abs /2c./ 06780. GSCC: 0000000 arXiv:2006.06780 [es, stat].
Li Deng. The MNIST Database Handwritten Digit Images for Machine Learning Research [Best of the Web]. IEEE Signal Processing Magazine, 1911114 November 2012. ISSN 1558- 0792. doi: 10. 10000//M220...2211477, URL https: /tt/eeeeeeeeeeeeeeeeeeeeeeeeeeee ieee. org/ /dcu docu ment/ 6296535,
Sahil Rajesh Dhayalkar. The Geometry of ReLU Networks through the ReLU Transition Graph, May 2025. UtL:ttp:// http:////aaiii.../aa//////////// wtt../rrggab//.....//// 11692. arXiv:2505.1162.
Reinhard Diestel. Graph theory. Springer Berlin Heidelberg, New York, NY, 6 edition, 2017. ISBN
9783662536216.
Feng-Lei Fan, Wei Huang, Xiangru Zhong, Lecheng Ruan, Tieyong Zeng, Huan Xiong, and Fei Wang. Deep ReLU Networks Have Surprisingly Simple Polytopes, November 2024. http: 09145. urXiv:2305.09145.
Gregoire Fournier. A tropical approach to neural networks. Master's thesis, University of Lille, September 2019. URL httpss www. semanticscoolee...ooo..cccccccoe ar httpp//aarrrrppppe//ttt/rroo
1 http:///eeeetrr......ee/eroe/e/e 24135afdff6d7c66. GSCC: 0000164.
Komei Fukuda. Frequently Asked Questions in Polyhedral Computation, August 2004. URL http wtt.:eifff.fh...cmmmmmmmm
s: s://people. inf www.ttt............ cttpt//..ccffuuuaaaaaaaa pttpkk///olla/../ooo//
Komei Fukuda, Shigemasa Saito, Akihisa Tamura, and Takeshi Tokuyama. Bounding the number of k-faces arrangements of hyperplanes. Discrete Applied Mathematics, 31(2):151-165, April 1991. ISSN 0166218X. doi: 10. 12111160066-218x(911990000666 .elsevier cwm/ cttp://etiieeeeeaaa//////le/eee/
URL https: ptctts://linkinge
Alexis Goujon, Arian Etemadi, and Michael Unser. On the number of regions of piecewise linear neural networks. Journal of Computational and Applied Mathematics, 441:1 156617, May 2024. ISSN 0377-0427. doi: (..1016/..am.22223..
URL https: /wwww sciencedirec
t. w.coo//cciince http:///wwnna.tteeeeeo//////////
Elisenda Grigsby and Kathryn Lindsey. On Transversality of Bent Hyperplane Arrangements and the Topological Expressiveness of ReI.U Neural Networks. SIAM Journal Applied Algebra and Geometry, 6(2):216242, June 2022. ISSN 2470-6566. doi: 10.1137/20M136899 URL
ht http:///epbb.. siw. orgi/aam.rr.//..e.oeeeee /ttp////......1///11300000000000 GSCC: 0000020.
J. Elisenda Grigsby, Kathryn Lindsey, and Marissa Masden. Local and global topological complexity measures OF ReLU neural network functions, April 2024. URL http: http::ttt://tteee http:://axivv..vr.. 2204. 66062. GSCC: 0000006 arXiv:2204.06062 [cs, math].
Boris Hanin and David Rolnick. Complexity of Linear Regions in Deep Networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1596-2600 PMLR, June 2019a. URL https: http:////ree///eee/eee/ee/eeeeee www.mlr.prre... wal...press//e sivess/v97, htt.aaannnnn htm 1.
Boris Hanin and David Rolnick. Deep ReLU networks have surprisingly few activation patterns. In Proceedings of the 33rd International Conference on Neural Information Processing Systems. Curran Associates Inc., Red Hook, NY, USA, 2019b. GSCC: 0000237.
12

---

Published as a conference paper at ICLR 2026
Fengxiang He, Shiye Lei, Jianmin Ji, and Dacheng Tao. Neural networks behave as hash encoders: An empirical study, January 2021. URL http: http:://axxv.vvooo 0000004 arXiv:2101.05490 [cs, stat].
05490. GSCC:
Xia Hu. Understanding deep neural networks from the perspective of piecewise linear property. PhD thesis, Simon Fraser University, 2021. Publisher: Simon Fraser University.
Changeun Huang. ReLU Networks Are Universal Approximators via Piecewise Linear or Constant Functions. Neural Computation, 32(1 32(11))2249-2273 November 2020. ISSN 0899-7667, 1530- 888X. doi: 10.1162/neco.a.l A.01316. URL https: /ttp::///drreteteeeeeeeeeeeeette wwt. wetiit.edureeeoo////eooo articee// 32/11/2249 2279/25633..
Joey Huchette and Juan Pablo Vielma. Nonconvex Piecewise Linear Functions: Advanced For- mulations and Simple Modeling Tools. Operations Research, 71(5):1835-1866 September 2023. ISSN 0030-364X, 1526-5463. doi: 10. 200..///p.......19999 / //pubsonnln ine. nfrrss...... org/ doi /10. . 287 opre 201 9. 1973.
URL https:
Joey Huchette, Gonzalo Muñoz, Thiago Serra, and Calvin Tsay. When Deep Learning Meets Poly- hedral Theory: A Survey, April 2023. URL https:
org/
22840. GSCC: 0000025.
Huma Jamil, Yajing Liu, Christina Cole, Nathaniel Blanchard, Emily J. King, Michael Kirby, and Christopher Peterson. Dual Graphs of Polyhedral Decompositions for the Detection of Adver- sarial Attacks. In 2022 IEEE International Conference on Big Data (Big Data), pp. 2913- 2921, December 2022. doi: 10. 10.11 (0.1109//igDaata5566/ 20...6...2..1100 10020880. URL https: / //ieeexplore. i feee. wwtp:/oor///ooooooeeeoe /10020880.
Huma Jamil, Yajing Liu, Turgay Caglar, Christina M. Cole, Nathaniel Blanchard, Christopher Pe- terson, and Michael Kirby. Hamming Similarity and Graph Laplacians for Class Partitioning and Adversarial Image Detection, May 2023, URL http: /trtt://arxii..../ org/ abs /2055. 01808. [cs, math].
GSCC: 0000006 arXiv:2305.01 208
Xu Ji, Razvan Pascanu, R. Devon Hjelm, Balaji Lakshminarayanan, and Andrea Vedaldi. Test Sample Accuracy Scales with Training Sample Density in Neural Networks. In Sarath Chandar, Razvan Pascanu, and Doina Precup (eds.), Proceedings The 1st Conference on Lifelong Learn- ing Agents, volume 199 of Proceedings of Machine Learning Research, pp. 629-646. PMLR, August 2022. URL https::/p//... http://poocceddeeeee mlr press http///99////// ji2aa..2..... html. GSCC: 0000081.
R. Kelley Pace and Ronald Barry. Sparse spatial autoregressions. Statistics & Probability Letters, 33(3):291-297, May 1997. ISSN 0167-7152. doi: 10. 10.1016/50111-71555000000000 URL https: //t:://www.... www.:esciiinecccceeeeeeeeee com/ http:///ccaaaaaaaaaaaaa///////// 40x.
Alex Krizhevsky. Learning Multiple Layers of Features from Tiny Images. PhD thesis, University of Toronto, 2009, URL httpt::t///... hwwp//wwcccoooo cs. torotto.......... wwwrontoeedb/txrii/eeeeeea res 2009-00.0..0 pdf.
featu
Daniel Lehmann and Mare Ebner. Calculating the Credibility of Test Samples at Inference by Layer-wise Activation Cluster Analysis of Convolutional Neural Networks. In Proceedings of the 3rd International Conference on Deep Learning Theory and Applications - DeLTA, pp. 34- doi: 10.5220/001 127400000327, GSCC:
43. SciTePress, 2022. ISBN 778-989-758-558 0000001 Backup Publisher: INSTICC ISSN: 2184-9277.
Paul Lezeau, Thomas Walker, Yueqi Cao, Shiy Bhatia, and Anthea Monod. Tropical Expressiv- ity of Neural Networks, October 2024. URL arXiv:2405.20174.
org/ abs// 2405/2445.00 20174.
Yajing Liu, Turgay Caglar, Christopher Peterson, and Michael Kirby. Integrating geometries of ReLU feedforward neural networks. Frontiers in Big Data, 6:1274831, November 2023a. ISSN 2624-909X. doi: f0.3389/flataa.222322222 articles 3 fdata 2023 017233122831111 ful GSCC: 0000030.
URL https: /tww//wwww////////////////////// frontiersin...
13

---

Published as a conference paper at ICLR 2026
Yajing Liu, Christina M. Cole, Chris Peterson, and Michael Kirby. ReLU Neural Networks, Poly- hedral Decompositions, and Persistent Homology. In Proceedings of 2nd Anmual Workshop on Topology, Algebra, and Geometry in Machine Learning (TAG-ML), pp. 455-468 PMLR, Septem- ber 2023b. URL https: proceed ngs. ml press / 221 u23 html.
Clémence Magnien, Matthieu Latapy, and Michel Habib. Fast computation of empirically tight bounds for the diameter of massive graphs. ACM Journal of Experimental Algorithmics, 13, February 2009. ISSN 1084-6654, 1084-6654. doi: 10. 1111//411222..... 14552664 URL https:
//dl. acm. wtrgg/d... /10. 1145/ 1412228. 1455266.
Marissa Masden. Algorithmic Determination of the Combinatorial Structure of the Linear Regions of ReLU Neural Networks. SIAM Journal Applied Algebra and Geometry, 9(2):774-404 June 2025. ISSN 2470-6566. doi: 11.37/24M1646999 URL https: eeubs.....................e..... s am. org// oi/10. 1137 /
4M1 646996.
Guido Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the Number of Lin- Regions of Deep Neural Networks. In Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014. URL ht 2-on-the number of Sif--inearr-ee -tw.o-i----eeiiosoeeeeee-e----e- wwwee-eee----a-eeeeeeeeeeeee--ee 0002803.
nips ct/ cctps//apppppp..pppppppppppepp 542
GSCC:
Guido Montúfar, Yue Ren, and Leon Zhang. Sharp Bounds for the Number of Regions of Maxout Networks and Vertices of Minkowski Sums. SIAM Journal on Applied Algebra and Geometry, 6(4):618-64) December 2022. ISSN 2470-6566. doi: 10. 10.1137/1MM1416699 URL https: //epubs. siam. 1tt.:////........111///111111130
Razvan Pascanu, Guido Montufar, and Yoshua Bengio. On the number of response regions of deep feed forward networks with piece-wise linear activations, February 2014. URL http: //arxiv. org/ wwt.a////.............ttttttttta 111./11111166 6098.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the Expressive Power of Deep Neural Networks. In Doina Precup and Yee Whye Teh (eds.), Pro- ceedings of the 34th International Conference on Machine Learning, volume 70 of Proceed- ings of Machine Learning Research, pp. 2847-2854. PMLR, August 2017. URL https: / //proceedings.o ml....m.r...... wttp://nn.......p.ssss///////// wtt.pp/sss////rrauullaaa html. GSCC: 0000949.
David Rolnick and Konrad Kording. Reverse-engineeriig deep ReLU networks. In Proceedings of the 37th International Conference on Machine Learning, pp. 8178-8187. PMLR, November 2020. URL https::////..........tt http:////coccceces.ooooo mlr. www.mml........mmmmmmmmmmmm.. rtt//ooooncckccmmm html. GSCC: 0000110.
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and Counting Lin- ear Regions of Deep Neural Networks. In Proceedings of the 35th International Conference on PMLR, July 2018. URL https: http:://poccceddeeee mlr.
Machine Learming, pp. press/v80/ eerralll Bb. html.
Hoang-Dung Tran, Diago Manzanas Lopez, Patrick Musau, Xiaodong Yang, Luan Viet Nguyen, Weiming Xiang. and Taylor T. Johnson. works. In Maurice H. Ter Beek, Annabelle McIver, and José N. Oliveira (eds.), Formal Meth- ods - The Next 30 Years, volume 11800, pp. 670-686. Springer International Publishing, Cham, doi: 10. 00000/9977833000-09422222
Reachability Analysis of Deep Neural Net-
2019. ISBN 978303030941 9783030309428. http: /tt///iink... wirkks..piiigreeeee com wtt.c//....00/....1.00101000 09000000777880 030- 30942-888882 8 39.
URL
Martin Trimmel, Henning Petzka, and Cristian Sminchisescu. TropEx: An Algorithm for Extracting Linear Terms in Deep Neural Networks. In International Conference Learning Representa- tions, 2021. URL https: http://ppeeeviiieeeee 0000014.
/ttpps::://ppeeeiiiii net httt:/forummii-IIttooooee
GSCC:
Calvin Tsay, Jan Kronqvist, Alexander Thebelt, and Ruth Misener. Partition-Bel -asiod Formulations for Integer Optimization of Trained ReLU Neural Networks. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https:/// htttps://pperreview net met/forum// forum?i derrrmmmddhhhhhh jhd KzRuj.
14

---

Published as a conference paper at ICLR 2026
Shaojie Xu, Joel Vaughan, Jie Chen, Aijun Zhang, and Agus Sudjianto. Traversing the Local Poly- topes of ReLU Neural Networks. In The AAAI-22 Workshop on Adversarial Machine Learning and Beyond, 2022. URL httpt:h/ /ttp:////ppeeeiee.....m net /ttp://w.......oooooo//////////2
Xiaodong Yang, Hoang-Dung Tran, Weiming Xiang, and Taylor Johnson. Reachability Analysis for Feed-Forward Neural Networks using Face Lattices, March 2020. URL http::/arxixy or g/ 1/abs/224 /bbs/2003. 01226. arXivv2003.01226.
Liwen Zhang, Gregory Naitzat, and Lek- Bek-Heng Lim. Tropical Geometry of Deep Neural Networks. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Leurning Reseurch, pp. 5824-5832. PMLR. July 2018. URL https: http://ppoceeeiieneee www.inggsmm........mmm.m...mm.m. www..ppees//ba.. https///v///haaggi/ iaatnngg....ml...... GSCC: 0000164.
Xiao Zhang and Dongrui Wu. Empirical Studies on the Properties of Linear Regions in Deep Neural Networks. In International Conference on Learning Representations, September 2019. URL
https:// httpp/////ppneeeew..... net. fott:/rrmmmmiidee 11H.rr.
Tan Zhu, Fei Dou, Xinyu Wang, Jin Lu, and Jinbo Bi. Polyhedron Attention Module: Learning Adaptive-order Interactions. A. Oh, Naumann, A. Globerson, K. Saenko, Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 9213- 9225. Curran Associates, Inc., 2023, URL https: /ttppptt//prrrredn.....eerrrpppp filees///// fills//pppeee /ttes//ppr/////eeeeeeeee /tteerr22222 20233/22////// 2tt.11/8888877711111144333353312 enference.pdf. GSCC: 0000000.
cc/pppr
15

---

Published as a conference paper at ICLR 2026
APPENDIX
A DETAILED RELATED WORK
Several works have established lower and upper bounds on the maximum possible number of poly- hedra (the regions in Fig. I(b)) in ReLU-type networks (networks with piecewise-linear activation functions) in terms of input dimension, depth and width of the network (Pascanu et al., 2014: Montu- far et al., 2014; Montúfar et al., 2022; Serra et al., 2018; Montúfar et al., 2022: Goujon et al.. 2024). For example, when the hidden layer width always larger than the input dimension, the number of linear regions grows exponentially with respect to both the input dimension and the number of hidden layers (Montufar et al., 2014). Another direction bounds from above the expected number of polyhedra over all networks of the same architecture (Hanin & Rolnick, 2019b). These bounds have been compared a recent survey (Huchette et al., 2023), which summarizes how lower bounds found by constructing networks with many polyhedral regions while upper bounds are found by determining the effect of adding additional layers of various sizes to existing networks. The number of polyhedra affects how the network transforms trajectory in the input space after each layer of mapping (Hanin& & Rolnick, 2019a), and the length of the transformed trajectory reflects the network expressivity (Raghu et al., 2017).
Several theoretical studies characterize the polyhedral structure of ReLU-like networks. A number of them have established links to tropical geometry (Zhang al., 2018; Fournier, 2019; Charisopou- los& & Maragos, 2019; Trimmel et al., 2021; Lezeau et al., 2024), which can be used to bound the total number of polyhedra and provide implicit formulas for the networks' decision boundaries. Analy- sis of ReLU networks as max-affine spline operators (Balestriero & Baraniuk, 2018; Balestriero & baraniuk, 2018; Balestriero et al., 2019) has identified a correspondence between the boundaries of the network's polyhedral regions as roots of a polynomial. Although this does not provide direct way to see how the polyhedra fit together, this theory has been successfully applied in detecting tox- icity in large language models by analyzing them individually (Balestricro et al., 2024). Topology has been essential for describing how the architecture of a network affects its geometry and mea- suring its complexity in terms of Betti numbers (Grigsby & Lindsey, 2022; Grigsby et al., 2024). An activation state is a sign vector indicating whether the ReLU in the corresponding hidden neuron has been activated for input. A topological approach proves that there is 1-1 correspondence between the network's s activation states and its polyhedral regions and can calculate the polyhedron boundaries using this description of its combinatorial structure (Masden, 2025). This paper builds on top of this work, which constructs the robust theoretical framework we use to study ReLU geometry (see Section for more details). A more efficient method for computing the boundaries developed later on (Berzins, 2023), which builds on previous method that can determine the architecture and parameters of ReLU networks via sampling (Rolnick & Kording, 2020). These works all provide tools for deeper analysis of network geometry, but they have not examined the connectivity of the polyhedra, a fundamental property of the complex.
There are also empirical studies that calculate the polyhedral complex and demonstrate a number of practical applications. Due to the intractability of enumerating all polyhedra, existing methods iteratively solve linear programs (LPs) that locally search confined regions of the input space (Liu et al., 2023a; Xu et al., 2022; Liu et al., 2023b) to count polyhedra or perform reachability analy- sis (Tran et al., 2019; Yang al., 2020). The behavior of ReLU networks on bounded input spaces can also be exactly described with mixed-integer LPs with decision variables representing activa- tion states, leading to a significant body of work improving the formulations of the networks with constraints (Huchette & Vielma, 2023; Tsay et al., 2021; Anderson et al., 2019) and applying them to problems such as verification (Botoeva et al., 2020: Cheng et al., 2017: Bunel et al., 2018) and inverse design (Ansari et al.. 2022). Network architecture has been shown to influence the volume and distribution of the polyhedra (Zhang& & Wu, 2019), which are then applied to quantify how the network generalizes to new data (Ji et al., 2022; Lehmann & Ebner, 2022; Daróczy, 2020). ReLU networks can be modified at the polyhedral level with the aim of improving explainability (Zhu et al., 2023; Hu, 2021). Other works study their geometric structure through the lens of activation states of the network on various inputs. For instance, a few methods use the Hamming distance between activation states proxy for similarity between the data points in different polyhedra, with various downstream applications ranging from data compression (He et al., 2021) to open set detection (Jamil et al., 2023) and clustering (Craighero al., 2020). However, empirical studies
16

---

Published as a conference paper at ICLR 2026
have not examined the connectivity of the polyhedral complex and how it relates to the distribution of training data.
B PROOFS OF THEORETICAL RESULTS
Definition B.1 (Hypercube Graph). A k-hypercube graph is a graph formed from the vertices and edges of k-hypercube. It can also be constructed as a graph with nodes corresponding to every string of & bits and edges between nodes with strings that differ by one bit.
Definition B.2 (Polyhedron).
polyhedron is (possibly unbounded) intersection of halfspaces, or
equivalently, the set of solutions to system of linear inequalities of the form {ar IR Ør+ s 0} for some real (n, mmatixx & and some 3 E g"
Definition B.3 (Polyhedral Complex). Polyhedral Complex a set of polyhedra satisfying the following properties:
1. Closure under intersection, that is, C1, C2 E C implies c1 nie E C. Note that this can be the empty set.
2. Closure under taking faces. That is, if e e C and c' is face of c, then e' C
We restrict our discussion to ReLU networks with the following two properties:
Genericity (Grigsby& & Lindsey (2022), Definition 2.4): A hyperplane arrangement in R is called generic if all sets of l hyperplanes intersect in affine space of dimension d for 1 < k d. In a ReLU network, each activation region is the intersection of half-spaces created by each neuron in the network, the boundaries of which form hyperplane arrangement in the layer's input space. A neural network is generic if the hyperplane arrangements corresponding to each of its regions are generic.
Supertransversality (Masden (2025), Definition 11): Let f be ReLU network with complex C and denote by fe: gm.-1 + R the output of the last L i layers of f with complex C₁ C Rm--1 Denote by H; the polyhedral complex in m created by the hyperplane arrangement {i E Rm 1: T. (W x + b) = 0} where f the projection onto the j-th coordinate for some 1 S I m,, Suppose for each layer < i < l and each S k S d that the restriction of Se to the interior of every k-cell of the complex H;-1 transverse to the interior of all cells of C,. Then, the network is called supertransversal.
Define (C) be the number of k--elll in the polyhedral complex
Theorem 3.4. The average number faces of a d-cell of C in R2 (i.e., the average degree of the connectivity graph) is at most 2d.
Proof. A sign sequence that has exactly one 0 in its elements corresponds to a (d - ce-cell Each (d (d-1) id-ell forms boundary of exactly two d-cells in the polyhedral complex C, and the single 0 in its corresponding sign sequence can be set to -1 or to obtain the sign sequences the two d-cells it separates. Thus, the sum of the numbers of faces of every d-cell is just twice the number of (d - 1)-cells, and the average number of faces of d-cell
(N)-1(C) We want to show that Ne(C)
2Na (C)
Na(C) < 2d, or equivalently, NC) < d.Na(C). We perform mathematical induction on both
the dimension of the (sub)complex d and the number of neurons in the network
Base Case
If d = 1, each d-cell is 1-cell, which can have either 0, 1, or faces. Thus, the average number of faces of d-cells is at most 2.
If n 1 (the network only consists of single neuron), the arrangement consists of a single hyper- plane, so the average number of faces of a d'cell 1 and the lemma holds regardless of the value of d.
17

---

Published as a conference paper at ICLR 2026
Inductive Step
We now prove that the statement holds for complexes of ReLU networks with n neurons in dimen- sions if holds for both n 1 neurons in dimensions and n 1 neurons in d - dimensions.
Assume for any ReLU complex C' with n - 1 neurons (or n - BHs) in d dimensions, we have
Na-1 Σ dN&(CC)..
and for any ReLU complex C' with neurons in d dimensions, have
Na-2(C") S (d - 1)'a-1(C'..
(5)
Let C be a ReLU complex of a network f with n neurons in d dimensions. Let h2 be the BH corresponding to particular neuron in the last layer of f. By Lemma 3.3 where d.
Na(C) Na(C h,) NN-1(h;))
(6)
Because C - h; is complex with n BHs in d dimensions, (4) holds. Substituting Eq.(4) into (6. yields
Na(C)= 2 d Na-1(C - h2) ) Na-1
Lemma 3.3 also applies to Na-1(C - h;) where k = d - 1. Substituting it into Eq.(7) yields
Na(C)2 2 à [Na-1(C) Na-1(h)) No-2(he) N
which can be equivalently written as:
1 Na(C) J Nc) 1 (Na-((1)) Na-2 + Na.1
(8)
To prove that NC-1(C) < dCN,CC) it is equivalent to prove that Na(C) 2 (C).-((C.. and so it is sufficient to show that the remaining terms the right-hand side of (8) least O. That is,
Na-1(ha) 2 d [Na-1(h)) + No-2(h)))
Multiplying this inequality by on both sides yields
dNa-1(h.) 2 Na,1 + Na-2(h:).
Then, subtracting Wa-1(h)) from both sides yields
(d - ( 2 2h-2(h:)
Since h; is ReLU complex in - dimensions with n neurons (its sign sequence contains only one 0), the strict form of this inequality guaranteed by Eq.(5).
Theorem 3.1. For ReLU complex in d-dimensional input space, the average number of faces of k-cell is at most 2k for 1,2.....d.
Proof. For k 1, I.... 1. each k-cell of a polyhedral complex C corresponds a sign sequence that has exactly d - k zeros, so the points in the k-cell are contained in the intersection of these BHs. Each k-cell belongs to a unique subcomplex of sign sequences where the elements corresponding to these BHs (neurons) are fixed to O. Therefore, calculating the average number of faces a k-cell involves examining the average number of faces of the k-cells contained in the subcomplexes restricted to every combination of d - k neurons (i.e., every intersection of BHs and its corresponding subset of sign sequences with in the corresponding positions). These intersections are k-dimensional ReLU complexes themselves. Thus, Theorem 3.4 guarantees that the average number of faces for the k-cells in each intersection is at most 2k. Together, the average number of faces of the k-cells contained in all different intersections of d BHs is most 2k. D
18

---

Published as a conference paper at ICLR 2026
Figure 8: ReLU complex illustrating Theorem 3.5 with = 3 and n1 = 2, when there are vertices in the complex. The first layer neuron's ' hyperplanes are shown in red, and the space orthogonal to their intersection (R(Wi)) is shown in gray. A second layer BH is also shown in blue. Regardless of how we translate the gray plane, its intersection with all the BHs will be identical, and the blue second layer BH will never intersect the intersection of the two first-layer hyperplanes. The proof works by showing that as you move in a direction orthogonal to the intersection of the first-layer hyperplanes (shown in orange), the distance to the first layer hyperplanes stays the same, and so the output of the first layer (and thus, the remaining layers) stays the same.
Previous work gives a lower bound on the connectivity of the complex as follows:
Lemma B.1 (Grigsby et al. (2024), Version 1, Corollary 5.29). If a ReLU network has at least d neurons in the first hidden layer, then every cell of contains a vertex.
If the condition of having at least d neurons in the first layer met, the minimum degree can be lower. We generalize the previous result as follows:
Theorem 3.5. If a ReLU network has Ty neurons in the first hidden layer, every d-cell of C has least min(mi,d) neighbors, and thus the average degree of the connectivity graph is at least min(n1,d)
Proof. If 2 d. then Lemma B.1 implies every cell of C contains vertex. Equivalently, every node in the connectivity graph is part of d-hypercube graph, and the graph has minimum degree d. On the other hand, assume that nı d. By the assumption of genericity, W1 R x R has rank n2. Thus, the space spanned by its row vectors R(W1) (the normal vectors of the first layer's hyperplanes) has dimension n1 and its null space V (Wi) has dimension d-n1. Since the null space and row space of W, are orthogonal complements, every point x E Rd can be written uniquely as R(W,) ) and l N.Wi). However, since W k
+ k for really have that W 2 + = Wi + k) + = Wie+ + Wik + b = Wi + b. This shows that for fixed v. (x) = [u + k) remains constant for all E NWW1. It then immediately follows that no polyhedron boundaries are ever crossed when & varies. Thus, to count the number of faces of d-cells in C, we can count the number of faces of the corresponding di ne-cells of the complex Cn,, created by restricting the network to R(W)). Applying Lemma B. every ni ni-cell in Co, contains a vertex (0-cell). Every O-cell in Cn, corresponds to a (d ny ceel in C, which means every d-cell in C contains (d ni -cell. A (d n1 ) node in the connectivity graph belongs to hypercube subgraph, which implies that the minimum degree of the connectivity graph at least n when ny < d.
for all k (W1),, ))
Theorem 3.6. The average number faces of d-cells in Cn increases monotonically in terms of n.
Proof. To prove this, it is equivalent to prove that adding new BH h, to the complex (i.c., adding a new neuron to the network) creates more (d - 1)-cells than d-cells, Na-1(C) N h, > Na(C) (C h.). Lemma 3.3 with h = d - shows that the left-hand side Na- Na-1 - hn, (h-1(ha) + 2am2(hm). Applying the lemma with = d shows that the right- hand side Na(C)- Na(C - hhn) = Na(h,) Nh,,, but Na(h,, 0, so the right-hand side of the equation just equals Na-1(hn). Substituting these equations into the inequality on both sides yields Na-1(h,)) (N,)(h,,)
(h,) Then. subtracting Na-1(h,) shows the inequality is equivalent to Na-2(h,) > O. Since (d- -)-llls are created whenever h, intersects other BHs the complex, which must happen at least once if any d-cells are created, so this inequality is true. Since
19

---

Published as a conference paper at ICLR 2026
after the d-th term the sequence is monotonically increasing and bounded below and above by d and 2d respectively, the average number of faces must converge to a value between these bounds.
Theorem 3.7. Let f be shallow network that has only one hidden layer with a nodes. When goes to infinity, the average number faces of its d-cells converges exactly to 2d. That is,
2Nd-1(CCn) = 2d.
lim 11-000 Na(C.)
Proof. If the network is shallow, the BHs of the neurons form a generic hyperplane arrangement. According to Buck (1943), the number of k-cells in the generic hyperplane arrangement C in dimensions is given by Nx(C)= = - (?) (a-x) Intuitively, the first term in the sum counts subsets of hyperplanes that intersect in at least & dimensions, and the second term counts the number of subsets in each of these sets intersect form k-face. Therefore, we have that
2Nd-1(Cnn
()())) EL
Na(Cn)
As c0, the numerator is dominated by d(H) and the denominator is dominated by (2) There- fore, the expression converges to 2d.
Let E be the total number of hidden layers (depth), my be the number of nodes in layer j. j 1,...,f, and m max(m1," .me} (width).
Theorem 388. The diameter D of a ReLU complex's connectivity graph is 2 [I((a((C)) 0 (m²)
and
In(x)
use the fact that the maximum degree of the connectivity graph the number of hidden neurons n, as a single BH cannot form more than one face of polyhedron. The Moore bound (Diestel, 2017) implies that the number of vertices in the connectivity graph is at most 1+ + 1))n - (..l))))..(((().... +n 1 1) 1)D-1 < n(n P) We can rearrange this inequality as follows: In(N.(C))
Proof. For the lower bound,
Na(C) < n(n 1) becomes In(Na(C)) < In(n(n 1), and n, D 2 1, so D In(x(n-1))
To get the upper bound, consider two d-cells pl, P2 E C. If the network only consists of one layer, we can easily find a path of polyhedra from P1 to P2 in this hyperplane arrangement by drawing a straight line from a point within P1
point within P2 and flipping the sign of each element in ((P)) every time we cross its BH. Each flip then yields the sign sequence of the next polyhedron on the path, and since the BHs are just hyperplanes, the line is guaranteed to cross each of the BHs on the path and flip the corresponding sign only once. For deeper networks, the problem is more difficult because BHs are not necessarily hyperplanes, and we may have to cross the same one more than once to get from one polyhedron to another. For a neural network with 2 layers, consider the BHs of the second layer as subdivisions of the polyhedra of the hyperplane arrangement created by the first layer. While walking along path between two of these layer-1 polyhedra, we have to cross some of these subdivisions. Now, if we want to find a path between two polyhedra P1 and p2 in this network, can ignore the second layer and find a path between the polyhedra from the first layer's hyperplane arrangement that contains Pi and p2- Inside each of the mi polyhedra created from only the first layer's 's BHs, the segments of each BH from the second layer are contained by hyperplane. Recursively treating them as their own hyperplane arrangement, we know we can get from one side of first-layer polyhedron to the other by crossing each second-layer hyperplane at most once. Thus, the total number first and second layer BHs we must pass through to get from P1 to P2 bounded above by (mi + 1) m2, For deeper networks, we can continue this recursion for each layer. Then, the maximum number of faces we would have to pass through to get from one to any other is upper
still find one that only crosses each first-layer BH at most once, because
bounded by Hissse (m, + 1) < (m + 1)f. The dominant term of (m + 1) as m, l + oc is m which shows that the connectivity graph diameter is O (m²).
20

---

Published as a conference paper at ICLR 2026
This diameter upper bound is the tightest asymptotic bound possible without factoring in the di- mension of the complex. For z E R, the following equations give non-degenerate I-dimensional network with width of layer with I i o and j E (1,2).
depth and more than m linear regions. Denote by fi, the jth neuron
(1,(()) max(# + 1,0)
f1.2(z) max(2r 1,0)
3j 2
f(z(x) -11
4'-1
ft,(2)) -
See an interactive demonstration of this network here:
https: http:://wwwwddemmc..cmm http://///occoooaoo////eebbeeaaa
C ADDITIONAL CATEGORIZATION EXAMPLES
3
3
3
2
2
4
4
4
1
1
(b) Coloring subcomplex where S(c)a = -1
the
(c) Coloring with for subcomplex where S(c)
(a) Coloring with
Figure 9: Alternate categorizations for Fig. with different choices of and restrictions different subcomplexes of C. Cells in Categories 1, 2, and are shown in blue, green, and red, respectively. Cells that not included in the complex shown in gray. In Fig. 9c, the only h; cells the blue vertices, and each one splits a pair of 1-cells in the subcomplex.
D ALGORITHMIC DETAILS
In this section, describe and further explain the role of the subroutine SOLVELPO in Algorithm 1, which was executed by Gurobi during our experiments. The SOLVELPO function takes in inputs T h. and 3g e;, which calculated based the affine functions forming the boundary of the corresponding polyhedron. To check if a linear inequality is redundant we solve the following LP for the best x" and we evaluate whether " x* + B. < O.
according to Eq. 2 and Eq. determine
hhttps://ww.ggrrr
21

---

Published as a conference paper at ICLR 2026
SOLVELP(- 2. +...+ee)
maximize
subject to
of S -31
0f - -
4 i-1 S -3,-1
D x < 33 +1
Relaxed Constraint
4 - 1 S -3411
T _ - -3
$ x < - 3n
Let p E C. be a d-cell with sign sequence Our goal is to find the neighbors of p. which correspond to d-cells with sign sequences that differ from s in one position. If p is separated by a face from the neighbor differing in sign sequence position i, this face will be contained by the BH of the neuron i in the network. Therefore, to find the neighbors of p. we can equivalently determine which neurons have BHs that contain the faces of p. which we can do by checking each neuron individually. As described in Section 2, when 8 is fixed and the network defines an affine function, the neuron i defines half-space (a linear inequality of the form "", x + Br, I 0) where the sign of its affine function is indicated by st. This half half-space contains p by definition, and the intersection of the half- spaces of all of the neurons in f is exactly p. However, not all of the half-spaces contain faces of p. as some may be redundant. To test whether a specific neuron i's BH forms a face of p. we push the boundary hyperplane of i's half-space backwards along its normal vector and check whether that allows us to walk further in that direction before we leave one of the half-spaces. That is, following (Fukuda, 2004), we relax the less-than inequality corresponding to neuron by adding a small value to the hand side and find the point a in the new system of inequalities that maximizes T,,,, where -6" is the opposite direction of the normal vector of the hyperplane bounding the half-space. If x² violates the original inequality D", x + B,, S O, then it is outside of p. so that half-space is not redundant and the face of p contained by its boundary is a (d 1)-cell of ht, which we can cross (equivalently, flip sy's sign) to get to a new polyhedron. If x does not violate the original constraint, then the half-space defined by neuron i is redundant and its BH does not contain a face of so flipping the sign of 8; does not yield a neighbor of and may not even correspond to any element of C.
E ADDING BENT HYPERPLANES TO THE DUAL GRAPH
Here we describe how the process of adding a new neuron to the network, going from C, to C,+1 via the addition of BH h,+ be represented in the connectivity graph. Each step is visualized in Fig. 10. When a new neuron's BH is added to an existing complex, it splits each of a connected set of existing d-cells in C., (the red nodes identified in step 1) in half. We first disconnect the nodes representing d-cells getting split from the rest of the graph, which form a vertex cut (step 2). Then, we duplicate the induced subgraph of the vertex cut, with each copy representing the Category d-cells in Cz+1 formed on either side of the new neuron's 's BH (step 3). After that, we add new edge between each corresponding node the two copies, representing the Category 1 (d - 1) cell between each of those d-cells (step 4). Together, this set of new edges represents the added neuron's 's BH. We now have to add back the edges we deleted between the vertex cut and the rest the graph, which represent Category 2 (d - (d-1)-cell) -cells that separated the d-cells that got split from the d-cells that did not (step 5). For each edge we removed in the second step. we add a new edge from its original outside-the-cus node one of the two copies of its original in-the-cut node, the copy representing the polyhedron in 1 that is on the same side of the new BH as the original outside-ther theeee-hhetttttee node. This demonstrates the monotonicity of the average number of faces network size increases (Theorem
22

---

Published as a conference paper at ICLR 2026
3.6), since every added node uniquely corresponds to at least new added edge regardless of the value d.
000
000
Figure 10: Connectivity graph modification when adding another final-layer neuron to a neural network with 3. Red nodes represent the d-cells that are split in half by neuron's 's BH. Note that the complex before and after is made up of cube graphs, and the subcomplex of split 3- cells is made up of square graphs (2-hypercubes).
F EXPERIMENTAL DETAILS
For all experiments, datasets were randomly split into 80% train and 20% test. Models were trained using vanilla SGD with a fixed learning rate. Data from all real datasets was normalized, and labels were normalized for the regression task. All networks were trained on a single GPU. Calculating the polyhedra in their complexes was distributed across 32 processors, and took up twelve hours for the largest networks.
For the experiments on synthetic data, networks were trained for 10 epochs with batch size of 64 and learning rate of 0.01. The datasets used in these experiments were generated using Scikit- Learn?. For the experiments with real data, setup information and performance metrics are listed in Table 2.
Table Architecture, training hyperparameters, and performance of networks trained on real-world data. For the regression task, we report coefficient of determination R² and Mcan Squared Error (MSE), while for the classification tasks, we report accuracy and Receiver Operating Characteristic Area Under the Curve (AUC) on the test set.
Dataset Name
CA Housing
CIFARIO
MNIST
Dataset Size
20640
60000
70000
Task
Regression
Classification
Classification
Classes
NA
10.00
10.00
Batch Size
64
4
64
Epochs
60
30
50
Learning Rate
0.00
0.01
0.10
Input Dimension
8
10
5
Hidden Layer Sizes
(128)
(64, 64)
(8, 8, 8)
Test Accuracy
NA
0.64
0,90
Test AUC
NA
0.94
0.99
Test I
0.65
NA
NA
Test MSE
0.34
NA
NA
For MNIST and CIFARIO, split the trained networks into two parts and regard the first part as a feature extractor. Our experiments are then performed on the second part, classifier, which has smaller input dimension. The California Housing dataset only has features, full network as the classifier. We report the input dimension and hidden layer sizes of the classifier
regard the
htttss:/scikitt-eeaa
23

---

closely Published as a conference paper at ICLR 2026
networks in Table 2. Working with the lower input dimension allows us calculate larger portion of the polyhedral complex associated with the network, which gives us a more complete picture of its structure. For the MNIST network, the feature extractor consists of a single fully connected layer with a ReLU activation. For the CIFARIO network, the feature extractor consists of two convolutional layers with 5 5 kernels computing 6 and 16 features, both followed by max-pooling layer and a ReLU layer, before a final fully-connected layer with ReLU activation.
G EXTENDED EXPERIMENTAL RESULTS
We performed additional experiments and included the related results here. Fig. 11 illustrates the same results in Fig. but with the theoretically computed lower diameter bound on the x-axis instead of the upper bound.
Fig. 12 expands our results in Fig. 4 to include results for networks with input dimension equal to 2 and 3 and display the average number of neighbors for each combination of width, depth, and dimension averaged over the 5 trials.
Table 3 provides more detailed results for the number of polyhedra, the average degree, the average volume of each bounded polyhedron, the percentage of bounded regions among regions, and the graph diameter for different networks with input dimension between and 5, numbers of hidden layers between and 4, and width in {4, 8, 16). We do observe that the number of polyhedra exponentially increases with the number of hidden layers (depth) and with the number of neurons in each layer (width). However, the average degree quickly approaches the upper bound for each dimension.
Fig. 13 shows how the volume and inradius bounded polyhedra in the MNIST complex are related to their numbers of neighbors and whether not they contain data. Although inradius has been previously used to estimate the volumes of polyhedra in higher-dimensional complexes where exact calculations intractable, this shows example of correlated. Note that unbounded polyhedra are not included in this figure.
where the values
Fig. 14 shows how the distribution of neighbor counts in Fig. 6a changes over the course of training. After each epoch, we recalculate the entire complex and check the positions of the same 10,000 data points. In this instance, we observe that as the network trains, the data gradually surrounded by higher numbers of polyhedra with relatively many neighbors.
120
Dual Graph Diameter
d
100
+
80
+
60
-
40
20
1.4
1.6
1.8
2
2.2
2.4
2.6
2.8
3
3.2
3.4 3.6 3.8
4
Lower Diameter Bound
Figure 11: The same plot as Fig. but with the lower bound from Theorem 3.8 on the --axis and experiments from all widths plotted together.
24

---

Published as a conference paper at ICLR 2026
# Hidden Layers
3
Width: 4
Width: 8
Width: 16
1M
3.67 +
3,85 4
3.94
3,46
3.84
3,91 +
Dimension:
10k
3.40
3.76
3.87
2.91
3.39
3.75
100
IM
5.29
5.77 +
5.91
4.99
5.72
5.88
Dimension:
Number of Polyhedrons
10k
4.70
5,59
5,80
3.73
5.01
5.55
100
1
6.16
7.71
7.85
1M
5.89
7.52
7.83
Dimension: 4
10k
5.38 4
7.29
7.73
4.00 +
6.28 +
7.32 4
100
1M
6.81
9.03
9.81
6.53 4
9.07 +
9.78 4
Dimension: 5
10k
5,84 4
8.86
9.62
4.00
7.23
9.02
100
5
10 15 5
10 15 20
10 Number of Neighbors
25 5
15 20
25
30
Figure 12: Distributions for the number of faces polyhedra in the decompositions of trained ReLU networks with varying input dimension (row), width (column), and depth (color). Each colored bar shows the average number of polyhedra with given number of faces created by a certain archi- tecture across 5 runs, with error bars representing the standard deviation. Diamonds represent the average number of faces in each network.
25

---

Published as a conference paper at ICLR 2026
Table Summary statistics for the distributions in Fig. 12. Diameter for each complex is estimated as described in Section 5.1.
Regions
Avg Facets
Average Volume
Finite
Diameter
Hidden
Width
2
4
11.00=0.00
2.91+00.00
0.63=0.11
0.27+00.00
4.50:10.00
8
37.00=00.00
3.46++0.00
1.45=0.99
0.57+00.00
9.10++0.22
16
137.00++0.00
3.74+00.00
3.34-4.48
0.77+00.00
19.20--0.76
30.80=4..15 4
3.37110099
33.75167.33
0.37:10.05
8.70
135.20=1.88 8
3.75
13.19:11.50
0.78110.03
18,5011.46
16
541.20--26.81
3.87100011
4.81=3.16
0.88110011
41.80:1..83
3
4
38.20=14.555
3.52+0.10
116.74:114794
0.67
11.70=E
8
275.20=51.57
3.82+0002
45.21##33008
0.84+0.02
27.10+3.445
16
1141.20+:5699
3.91+0.01
11.43+3.63
0.92+0.01
60.40+1.008
4
87.80=22.86
3.63+00.9
153.521121.53
0.8110.03
14.40112.22
8
148.22
3.85.10.33
109.09
0.86100.33
37.00.15.72
16
2128.40-42287
3.9410.01
28.05:428.37
0.9410.01
80.90
3
15.00-00.00
3.7310000
0,49=0.65
0.07
5.00EE0:00
93.00=0.00 8
4.99:0.00
3.17=4.20
0.38
10.10:1.44
696.80=0:45 16
5.55+0000
3.08=2.35
0.65+10.00
21:00:00227
62.00-9.77 4
4.68+0.17
5.07=5.18
0.45+0005
8.80++0.45
8
710.00+141.76
0.56+0006
20.26+
0.68+0.03
20.20++1.66
16
4628.400-482.33
5.80+0.01
13.79++4.92
0.82+00011
41.80+1..35
118.80149.34
4.91
60.281677119
0.60110.07
11.0011.17
8
1806.8011572.0
5.70110.08
56.18:121:47
0.7610007
26.90112.46
16
2.00x 10 1287
5,8810.01
30.68-12.559
0.8910.01
59.00
145.40145..4
5.1310.33
314.421119.10
0.66.10.18
14.90.3.111
8
1073.40+1122..22
5.76+00.6
204.91499.20
0.8240.06
34.20-5.775
16
5.49 10xxx10*+-00000 +4259.65
5.91+00.2
91.56++49.71
0.91+0.02
81.70+66.45
16.00=00.00 4
4.00
0.00=E0.00
0.00
5.50
163.00-10.00
6.28110.00
4.78.19.59
0.21110.00
10.60-10.42
16
2517.0010..00
7.32-10.00
4.3311261
0.54110.00
22.50-10.35
2
4
72.60
5.2110.31
16.851337.67
0.3310.18
8.70.10.76
8
2244.80
7.25
36.18:211.01
0.56+0..11
20.40:10.74
16
4.22 10 $6008.
7.7240.06
43.07
0.78+0.05
41.10:10.65
4
227.60+42.22
5.85#0.16
31.39+36.889
0.63
12.50+00.61
8
9340.80
7.47+0.17
143.79-168.06
0.69
27.60+12.22
16
2.2.210
7.82-10.04
49.91119.37
0.85
57.70-1..44
4
#48.00=119.11
6.17E0.12
62.72:441.8
0.72:00.07
13.90%1.119
8
3.58x 1.59310'-
49493.85
7.70
233.75=172.31
0.85+0.02
37.40+1.22
16
6.24x10"9.63x
7.85+00.3
107,33420.93
0.86+0.02
76.35+4.56
5
16.00-00.00 4
4.000
0.00:E0.00
0.00
5,50
219.00+-0.00 8
7.23+0.00
6.80+19.551
0.10+10.00
10.75+10.26
6884.87+0.35. 16
9.02+40.00
4.35-12..9
0.44+10.00
23.17-+0.41
19,50 8
3.34:10.25
0.00
0.3120.11
9,30-1..3
1102.6011146..11
8.77:1.22
62,26:132.43
0.45:0.111
21.75
16
2.69 4,8 1
9.61+0.05
10.59
0.71+0004
42.57=1.553
4
389.60 188.02
5.65
2,11=44.00
0.55+00.0
14.65+2..32
8
3.66x 10 1.21 1
8.54
156.80+75.65
0.68++0.12
31.50+2..3
16
1.78 1.94 10a
9.78-10.04
39.91411.83
0.8210004
17,44+
4
1206.70:1114.000
5.50
1.38
0.7710.16
18.6013.98
8
1.82x10 4
8,25+1.38
192.28+100.15
0.84
48.25
16
5.03 1.00 8
9.80-40.03
152.544158.24
0.84-10.03
70.88
26

---

Published as a conference paper at ICLR 2026
10k
Volume
(b) Inradius
Average
Averago
100
Volume 35
1000
Data Points
Inradius
0.6
10
30
10
0.5
0.4
10k
20
AN mi/ Suint
0.3
1000
1000
15
0.2
100
100
10
0.1
10
10
10
14
18
6
10
12
14
16
18
20
Number Neighbors
Figure 13: Histograms of bounded polyhedron neighbor counts for all d-cells in the MNIST net- work's complex, colored according to volume (left) and inradius (right).
Number of Points
No Training
Epoch
2 Epochh
3 Epochs
10k
1000
100
10
3125
4 Epochs
5 Epochs
6 Epocch
7 Epochs
10k
Number of Polyhedoons
1000
625
100
10
8 Epochs
9 Epochs
10 Epochs
11 Epochs
125
10k
1000
100
10
25
12 Epochs
13 Epochs
14 Epochs
15 Epochs
10k
1000
100
10
5
10
15
5
10
10 Number of Neighbors
15
5
15
5
10
15
Figure 14: Face count distributions for network trained the MNIST dataset. These are con- structed in the same way as in Fig. 6, but with one for each training Epoch.
27


Reviews:
[{"review_id": "zNbdUfRsK0", "reviewer": "Reviewer_MKyy", "summary": "ReLU networks partition a $d$-dimensional input space into linear regions and therefore have an associated canonical *polyhedral complex* in which the $d$-cells correspond to individual linear regions and lower-dimensional cells arise from their iterative intersections.\nBy considering only top level polyhedra ($d$-cells) as nodes and their faces ($(d-1)$-cells) as edges, the polyhedral complex can be simplified into a *connectivity graph*, retaining information of neighoring linear regions.\nThe core contributions of the paper are to prove theoretical results: (1) an upper bound on the average number of neighbors of $k-cells$ in the complex, (2) a convergence result towards this upper bound for $d-cells$ with the increase of network size (number of neurons) and (3) lower and upper bounds on the diameter of the connectivity graph.\nEmpirical experiments confirm these results and, in addition, reveal an intriguing observation: linear regions that contain data points tend to be more connected i.e. have more neighboring regions, than those that do not.", "questions": "1. **Neighbor Count Distribution and Training Data** One of the most intriguing findings is the shift in the distribution of neighbor counts between regions that contain training data and those that do not. Do the authors have an intuition (or theoretical explanation in simple cases) for why regions containing data tend to have higher connectivity? (see also my comment above)\n1. **Expressivity and Local Degree** To what extent could the number of neighbors in the connectivity graph be interpreted as a local measure of expressivity? On one hand more neighboring regions suggest finer partition of the input space, but on the other hand a simplicial partition of the input space would have maximal connectivity graph degree $d+1$ while still being able to be a good approximation (e.g. 3D meshes).\n1. **Bounded vs unbounded regions** There is no discussion of bounded vs unbounded (peripheral) linear regions and while it does not change theoretical results they coexist implicitly throughout the paper. Moreover the unbounded regions can have less neighoring regions as you note in the proof of Theorem 3.4 in appendix for the base case, so I was curious to know if you had some general comment on this distinction and whether it is a useful framing.\n1. **Diameter Bound and Implicit Dependence on Input Dimension** One of the hypothesis of theorem 3.6 is \"as many first-layer neurons as input dimensions\" and the derived upper bound is in $O(m^l)$. In the limit $d\\mapsto \\infty$ this implies $m=m_1\\geq d$, which seems to be inconsistent with the claim of line 309 (also in the abstract) that the upper bound does not depend at all on the input dimension d. Could you clarify this point ?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper appears technically sound and is written in a clear, engaging style, with informative and visually appealing figures and illustrations (except Figure 6; see my specific comment below).\nThe overall structure and section breakdown are logical, and the paper’s main message is conveyed smoothly. Experimental details are provided in the appendix, and code availability supports reproducibility.\n\nThe work contributes new theoretical results in an active research area. It complements existing studies on counting linear regions by considering instead their adjacency relations.\nThis perspective has ties with other work branches such as tropical geometry of ReLU networks and error bounds.\nWhile the immediate actionable implications of the theoretical results are not obvious, they could inform studies on expressivity or serve as guideline to use quantities like degree of the connectivity graph as features. \nEach claim is well supported both by proofs and empirical validation and the paper never overreaches.\n\nWhile not new the polyhedra search method is interesting on its own.", "weaknesses": "The paper feels somewhat incomplete on one point.\nThe observation that polyhedra containing data tend to have, on average, more neighbors than those that do not is intriguing and calls for further exploration.\nIt would be helpful to confirm this finding with additional experiments to confirm it is not an artifact.\nIntuitively, one might expect that regions containing data are more constrained and thus require higher expressivity and more complex boundaries to better fit the data.\nWhile a theoretical explanation may be out of reach, additional empirical checks would, in my opinion, strengthen the paper, for instance:\n- Check that this distribution difference emerge gradually during training by measuring the same statistics as in Fig. 6 at multiple training steps (including initialization).\n- If region sizes can be estimated, are data-containing regions systematically smaller (indicating higher flexibility) ?\n- Equivalently, is the spatial density of regions correlated with data density ? For example by taking a representative point by linear regions and measuring overlap with train/test data.\n- Could the observed difference partly reflect the presence of peripheral, unbounded regions that would tend to be empty?\n\n## Minor and additional feedback\n- the links don't work\n- line 76: unclear definition of the diameter\n- typo missing \"to\" line 216\n- line 825 lemma 3.4 does not exist in the paper\n- strange syntax line 316\n- vizualizing the lower bound or the number of regions $N_d(\\mathcal C)$ would be nice on fig 5\n- Fig 6 is a bit confusing: if the gray bars represent polyhedra traversed by BFS and colored bars are the subset of these polyhedra containing at least 1 data point, why is are gray bars below the colored ones on the right tail of plots (b) and (c) ?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VYjBIjeMVR", "reviewer": "Reviewer_6xrb", "summary": "This paper provides new results on the geometric characterisation of the polyhedral complex generated by the linear regions of ReLU neural networks.  The theoretical results provide, in some sense, a universality result in that the bound on the degree of the connectivity graph does not depend on depth and width of the network.  Experimental results are provided alongside.", "questions": "What can be said about the computational complexity of the approach versus some recent work, e.g., by Stargalla et al. \"The Computational Complexity of Counting Linear Regions in ReLU Neural Networks\"?  Also to other existing work, e.g., by Lezeau et al. \"Tropical Expressivity of Neural Networks\" that gives the exact linear region count as well as discusses geometry of the linear regions?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is very well written.  The presentation is very nice and the ideas and concepts are presented very well.", "weaknesses": "- Limitations of the work were not discussed.\n- Although there is quite a number of references cited and a further detailed section on related work in the appendix, I still felt that there wasn't a strong connection between the contributions of the submission and previous work.  For example, the cited work by Zhang et al. on the tropical geometry of neural networks provides a theoretical upper bound on the number of linear regions.  I think that the submission could have done some computational comparisons on the proposed approach versus this existing well-known tropical geometry paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kg6Ov5RBNM", "reviewer": "Reviewer_5Du1", "summary": "The paper studies the geometry of piecewise-linear regions induced by ReLU networks, focusing on how these regions connect to each other rather than merely counting them. The authors define and analyze the connectivity graph, where nodes correspond to linear regions and edges represent shared facets between adjacent regions. They prove two main structural results. First, the average degree of this graph is at most $2d$, where $d$ is the input dimension, independent of network depth and width. Second, its diameter is upper-bounded by a quantity that depends only on the network’s width and depth, but not on input dimension. These bounds reveal a type of geometric regularity that holds across architectures.\n\nOn the algorithmic side, the paper proposes a method to enumerate regions and reconstruct the adjacency graph using linear programming feasibility checks. Experiments on small networks empirically validate the theoretical results and suggest that regions containing data points tend to have higher connectivity. Overall, the paper contributes new geometric understanding of ReLU networks, extending previous work.", "questions": "- Is the connectivity graph the 1-skeleton of the sign sequence complex, which under the weight assumptions forms a cubical complex? Would your results hold more generally for graphs that are the 1-skeleton of a cubical complex? Have you checked the literature for related results on 1-skeleta of cubical complexes?  \n- How exactly do you define a ``face''? It seems that you mean a codimension-1 face, which is usually called a facet.  \n- Can you say anything about the non-generic case? Understanding the class of possible connectivity graphs for networks with 2 hidden layers would be very interesting.  \n- The observation that data points lie in cells with more neighbors is interesting. Do you have any idea why this might be the case? It has also been observed that data points tend not to lie close to the boundaries of cells after successful training (e.g., https://openreview.net/forum?id=NpufNsg1FP). Do you see any connection between these observations?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "The paper provides clear and rigorous geometric insights into the structure of ReLU networks by analyzing the connectivity of linear regions. The results are conceptually interesting, mathematically clean, and supported by both proofs and experiments. They are well presented and also lay a solid foundation for future work.", "weaknesses": "- The paper should explicitly state the basic assumption adapted from Masden (2022). Although it holds for a full-measure set, combinatorially it is arguably a strong restriction.  \n- While the paper gives helpful intuition and pictorial explanations, including a rigorous definition of the canonical polyhedral complex (at least in the appendix) would improve clarity.  \n- The results are not particularly deep; nonetheless, they are conceptually interesting, clean, and provide meaningful insights into neural network structure.  \n\nMinor: \n- In the proof of Theorem 3.1, Lemma 3.4 is referenced but does not appear in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5tVdXbIHzu", "reviewer": "Reviewer_drEY", "summary": "This paper establishes fundamental results about the geometry of ReLU networks. It shows that the number of neighbors a linear region has is always upper bounded by 2 times the input dimension of the network. This is somewhat surprising because using a deep architecture can sometimes produce an exponential number of these regions, yet the configuration still obeys this graph property. The other main result is that the diameter of the connectivity graph has upper bounds that are independent of the input dimension, which is again surprising given the role the input dimension played in the first result.", "questions": "One thing that confuses me about the proof of Theorem 3.4 (appendix A) is that it says it inducts over the ‘input dimension’ of the network, rather than the dimension of the ReLU complex. It establishes the base case as d=1, where all the 1-cells lie along a single line with two unbounded end segments, which is true of input dimension 1, but not generally true of an arbitrary 1-d ReLU complex, which could have multiple loops (such as the blue line in Figure 3b). It seems like it ought to be inducting over the ReLU complex dimension, since inductively adding neurons would need to check that the intersections of the existing BHs onto the new BH obey (d-2 cells) < (d-1)*(d-1 cells), which is different from having one less input dimension. Are you maybe using ‘input dimension’ to describe restriction onto a d-1 dimensional set of input space where the new neuron’s pre-activation output is 0? I guess I’m confused because the body of the paper makes the point that the dimension of the ReLU complex is more about the highest dimensional cells it has rather than the space it’s embedded in, but the induction seems to be over the embedding space. Some clarification here would be helpful.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Excellent presentation. This paper has great figures and clearly and concisely explains a lot of mathematical concepts.\n\n2. Theoretical results were thought-provoking and intriguing, providing the reader with new ways to think about ReLU configurations.\n \n3. Empirical results are well connected to the paper and make sense in light of the theory.\n\n4. Theorem 3.6’s reasoning about connecting regions with lines does a good job explaining why the graph diameter really isn’t about the input dimension.\n\n5. I was wondering about the connection with dividing space into cubes when I read the abstract and saw connectivity = 2d, it was cool to see that connection in Theorem 3.5", "weaknesses": "1. Line 80, missing the word ‘and’ \n2. 147, 169 ‘exactly’ should be ‘at least’ since a line can lie in the intersection of as many bent hyperplanes as it wants. It seems that most of the time we’re supposed to assume the BHs are in generic configuration though, mentioning that sooner could also fix it\n3. 216 corresponding ‘to’ a network. ‘To’ is missing.\n4. 269 ‘two d-ells’ typo\n5. 316 ‘On a polyhedral region where the network’s behavior is affine.’ \n6. 408 complexes complexes\n7. 825 appendix, is Lemma 3.4 supposed to be Theorem 3.4?\n8. 839 ‘at once of the d-cells’ \n9. 863 did you mean to say each neuron adds d times more d-1 cells than d cells?\n10. 936 contain should be contains\n\nFor Theorem 3.5, if the subgraph from the vertex cut has minimum degree d-1, doesn’t that mean that the number of new edges is only at least (d-1)/2 times the number of new vertices rather than (d-1)? I think this might affect the correctness of this proof. It would seem that if average degree (d-1) rather than 2(d-1) were all it took for a new (d-1) complex to contribute d times as many (d-1)-cells as d-cells to a d complex, that that would break the induction in theorem 3.4.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)