Algorithmic Determination of the Combinatorial Structure of the Linear Regions of ReLU Neural Networks
Authors: Marissa Masden
Venue: Submitted to ICLR 2023 (2023)
Keywords: ReLU networks
algebraic topology
linear regions
computational geometry

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

ALGORITHMIC DETERMINATION OF THE COMBINATO- RIAL STRUCTURE OF THE LINEAR REGIONS OF RELU NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We algorithmically determine the regions and facets of the canonical polyhedral complex, the universal object into which a ReLU network decomposes its input space. We show that the locations of the vertices of the canonical polyhedral com- plex along with their signs with respect to layer maps determine the full facet structure across all dimensions. Our algorithm which implements this approach makes use of our theorems that the dual complex to the canonical polyhedral com- plex is cubical, and possesses a multiplication compatible with its facet struc- ture. The resulting algorithm is numerically stable, polynomial time in the number intermediate neurons, and obtains accurate information across all dimensions. This permits us obtain, for example, the true topology of the decision bound- aries of networks with low-dimensional inputs for binary classification tasks. We run empirics on such networks at initialization, finding that width alone does not increease observed topology, but width in the presence of depth does.
INTRODUCTION
For fully-connected ReLU networks (Nair & Hinton 2010), the canonical polyhedral complex of the network, defined by Grigsby & Lindsey (2020). encodes its decomposition of input space into linear regions and determines key structures such as the decision boundary for binary classi- fication task. Investigation of properties and characterizations of this decomposition of input space are ongoing. in particular with respect to counting the top-dimensional linear regions (Serra et al.
2018 Hanin & Rolnick 2019a Montufar et al.) 2014 Serra & Ramalingami 2020) Xiong et al. 2020). since these bounds give one measure of the expressivity of the associated network archi- Tecture. However, theoretical understanding of adjacency between regions and more generally the connectivity of lower-dimensional facets are to our knowledge generally undocumented, Un- derstanding the face relations in the canonical polyhedral complex-for example, for tiled surfaces, understanding all inclusions between vertices (0-faces), edges (1-faces) and polygons (2-faces) -is necessary to relate combinatorial properties of the polyhedral complex of a network to the topology of regions into which the decision boundary partitions input space, geometric measurements such as the presence of critical points (Grigsby et al. 2022). or other notions topological expressivity, as explored by Guss & Salakhutdinov (2018); Bianchini & Scarselli (2014).
is common to describe lincar regions of the imput space, R" using "activation patterns" or "neural codes" recorded as vectors in {0, 1 (Itskov et al. 2020 Unfortunately, having a list of which activation patterns are present in the interiors of the linear regions does not determine their pairwise intersection properties (Theorem [55, and computing the intersections of these regions directly is not numerically stable. Furthermore, the polyhedra comprising the linear regions appear, at first glance, arbitrarily complicated, In this work, we establish a simpler representation by proving the theorem that the geometric dua any network's 's canonical polyhedral complex is a union of rn-ddimensional cubes (see Figure [p. Inspired by the theory of oriented matroids and hyperplane arrangements (Anders et al. 2000 Aguiar & Mahajan, 2017). we demonstrate how the notion of "sign vectors" from oriented matroids, which are vectors with entries in (-1, 0, 1), can serve as a labeling scheme for vertices, edges, and nigher-dimensional regions. These sign vectors have properties that track
Recall, for example, that the dual of the icosahedron is the dodecahedron.

---

AهA
Figure I: An illustration of a canonical polyhedral complex and its geometric dual. Left: C(F) for a specific neural network function F' R RS + R. The three straight lines and the solid colored regions together form R(), which is also C(Fi). Middle: Fi RR + R3 is piecewise linear on cells of ((F).. The hyperplane RR is the hyperplane associated with A :R + R. and this hyperplane together with the two halfspaces on either side of it form R(2), The cells of C(F) on the left are mathematically determined by taking one region R of R(2), considering its preimage FT (R)) and taking the intersection of this preimage with a cell of C(Fi). Right: The geometric dual sign sequence complex S(F)) is superimposed in white over C(F), with one vertex for each region of C(F). As we prove in general, S(F) is cubical, with each two-cube (quadrilateral) containing unique vertex of C(F).
face relations and intersections between all linear regions in input space. We show that with full probability, computing only the vertices present in the polyhedral complex and recording their sign vectors gives enough information to determine all face relations in the polyhedral complex. The ability to compute the explicit decision boundary of network provides a new means to evaluate topological expressivity of network functions.
Our main contributions are:
Mathematically, we prove the existence of combinatorial description of the geometric dual of the canonical polyhedral complex of a ReLU neural network which consists of generalization of activation patterns, which we call the sign sequence complex. Further- more, using product structure adapted from the theory of oriented matroids which we prove to be well-defined, we show that the only information needed to determine the face poset structure of the sign sequence complex is the sign sequences corresponding to the vertices of the polyhedral complex.
We implement an algorithm for obtaining these sign sequences which is numerically stable and, on average at initialization, runs in polynomial time in the total number of neurons, and exponential time in the input dimension.
We show that the sign sequence complex can be naturally restricted particular substruc- tures of the polyhedral complex of a ReLU network. In particular, a chain complex com- puting the homology of the decision boundary can be obtained with simple operations on subset of the vertices of the polyhedral complex, together with their sign sequences.
We demonstrate the usefulness of this characterization of network by obtaining the statis- ties of ReLU networks' binary decision boundaries' topological properties initialization, dependent on architecture. These experiments provide empiries suggesting that depth of a network plays stronger role in topological expressivity, at least at initialization, than the number of intermediate neurons.
In this work, our primary aim is understand C(F) more completely. We do this by demonstrating how to use sign sequences to record all information about the adjacency of linear regions without needing to separately list all edges, faces, and higher-dimensional cells. Sign sequences have a geo- metric interpretation as cubical complex, and an algebraic structure which is useful in proofs. It is also computationally tractable to treat these sign sequences as a data structure which provides a key for translating between local geometric and analytic information about C(F) (vertex locations and function behavior at those locations) and global topological and combinatorial information about the linear regions, including the serriissly-inaccessiie topology of binary decision boundaries.
2

---

Figure 2: Left: C(F) for a Its decision boundary is in solid red and has nontrivial 31. Middle: The graph of the function : R2 + R. with the decision boundary as its zero level set. Right: In red, the decision boundary of neural network with architecture (3, 15, 8, 1). The network was trained using stochastic gradient descent to distinguish a points sampled from a torus from points sampled from an annulus at its center.
initialized neural network F with architecture 12,15,15,1).
RELATED WORK
The seminal paper by Grigsby Lindsey (2020) establishes a high-level view the cellular struc- ture of the canonical polyhedral complex, but does not establish explicit low-dimensional informa- tion. Under weak assumptions, they show the canonical polyhedral complex's 's (nu - 1k-skelltton (the set of no 1-dimensional polyhedra) may be described the preimages of hyperplanes from each layer map, but arbitrary kssseletoons are unexamined for l < (mn- - 1), as are general face relations. The subsequent work (Grrigsby al. 2022) establishes local models for the polyhedral structure the intersection of hyperplanes, but does not address deeper network structures as we do here.
Hyperplane arrangements used by Hanin & Rolnick (2019a b) to study linear regions, but pri- marily for computing volumes and counting top-dimensional regions, and not obtaining adjacency relations. In particular, these works properties of hyperplane arrangements are used to establish statistical properties of the canonical polyhedral complex. While our work does rely on properties of hyperplane arrangements
similar way, we focus on encoding the full face poset. In addition, others who approach explicit computation of linear regions in /Zhang & Wu 2020) do so using halfspace intersections, and we use vertices. While in theory one could intersect top-dimensional regions pairwise to obtain their shared faces, this is not numerically stable, especially when the lin- car equations involved arise from matrix multiplication. Our algorithm tracks known equalities and uses discrete signs to track face relations, avoiding issues potentially arising from numerical error in polyhedral intersection. Furthermore, in contrast to approaches by Curto et al. (2019) and other neuroscientific and biological applications where boundary structure is not clearly defined, in the context of artificial networks the boundary intersections are in fact computable.
Other characterizations of the combinatorics of ReLU networks' polyhedral complexes exist, but lack explicit implementation or applicability to deeper networks. [Balestriero et al. (2019) describe the regions of the canonical polyhedral complex according the roots of a polynomial, but no algorithm is presented on how to obtain these roots, nor how to explicitly determine whether two polyhedra are connected by shared face. Zhhag al. (2018) provide a tropical characterization of the polyhedral complex including its face relations, but rely on the translation of network functions to tropical rational functions with integer coefficients, which is discontinuous operation. In contrast, we conjecture that the signs of vertices present in the sign sequence cubical complex are stable in open sets of parameter space and could therefore be recorded to track changes a network's topology during training. The subsequent application of tropical geometry by Alfarra et al. (2020) appears limited to networks with single hidden layers. Additionally, [Iskov et al. (2020) establish characterization of the regions of single-layer hyperplane networks which relies similar sign labelings, but the methods do not apply to deeper networks.
Some reachability analysis algorithms using polyhedral methods such as those by Yang et al. (0200) 2021) use signs to determine how polyhedra have been "split" by a layer map, tracking the face lattices of the output polyhedra of each layer. In theory, this approach could plausibly record which
3

---

polytopes in the imput space intersect in shared regions, but these papers consider polytopes inde- pendently from another in the next layer for purposes of parallelization. is unclear whether enough information is retained store which "splits" line up between polytopes, their applications. Additionally, this approach requires storing all faces for the face lattice in each polytope, whereas show this information is fully contained in the sign sequences of the vertices.
this is not needed in
THE SIGN SEQUENCE CUBICAL COMPLEX
We define the sign sequence cubical complex and justify its importance before describing an algo- rithm for its computation in section 4.1 For readability, most terms are defined in prose, with fully precise definitions available in Appendix A.
3.1 PRELIMINARIES
We work with fully-con fully-connected, feedforward ReL.U networks, following the framework by Grigsby & Lindsey (2020). In this framework, a network F is expressed as Am Fm-1 o F2 Fi, where each F. = ReLU o A for an affine map A, : IR= + R", and the last affine map Am has image in I and is not followed by the ReLU function (Definition 3). We refer to the activity of each individual neuron of the network before the ReLU function applied as the (i,j)t j)th node map:
Definition (Fis Grigsby & Lindsey (020), Definition 8.1 ). If F is ReLU neural network, the
node map Fig defined by:
T A, Fi-1 o... F1 R IR
Note that Ty is projection on to the jth coordinate, i indexes layers, and j indexes neurons.
For fixed i, the solutions to πT o A, = 0 are hyperplanes in R which together form hyperplane arrangement (Aguiar & Mahajan 2017). These hyperplane arrangements are equipped naturally with the structure of a polyhedral complex, which is an arrangement vertices, edges, polygons, and generally k-dimensional polyhedra for 0 < k S 7i-1 (Definition] T]. We denote the polyhedral complex associated to A; by R(()) (Definition 3 'he canonical polyhedral complex C(F) consists precisely of the polyhedra in Tho which may be described by selecting one polyhedron R2 C TR. from each hyperplane arrangement R(O,, considering the preimages (F;-1 o... Fo)- in R""", and then taking the intersection of the resulting polyhedra (Definition ever, while this defines C(F) mathematically, this does not describe a tractable algorithm for its computation.
7 or see Figure [8). How-
established by Grigsby Lindsey (2200) and Grunert (2017) that each intermediate complex C(F2 o... o Fi) is polyhedral complex which subdivides the previous one, and resultingly F is affine linear on each cell of C(F).
Our results apply certain subsets of ReLU neural networks, called generic (Definition 10 and supertransversal (Definition IT), additional technical conditions which are nonrestrictive in light of the following lemma that almost all networks
supertramsversal.
Lemma 12 Supertransversality is full measure in IR.", where P is the set of network parameters. Additionally, it is fiberwise generic. That is, with fixed network weights, the set of biases corre- sponding to supertransversal networks is open and full measure.
That almost all networks are, additionally, generic, was established by Grigsby & Lindsey 2020) As result, in all but a measure zero subset of networks, the theory developed below will hold.
3.2 THE SIGN SEQUENCE CUBICAL COMPLEX GEOMETRICALLY DUAL TO C(F)
For networks with N neurons, binary strings of length N (which we will denote using -1 and 1) may serve as a labeling scheme to describe which neurons are active at a point in ReLU network's input space [Itskov et al. 2020) the interior of cells of C(F). However, this binary labeling is insuffi- cient to encode all face relationships and the topology of a network's 's canonical polyhedral complex, which we prove in the appendix in Theorem [S] We propose instead to use sign sequences, defined below, as a means to label all polyhedral faces of C(F) and thereby fully encode the combinatorial properties of network's 's canonical polyhedral complex.
4

---

Define C(F) (-1,0,1} by sty (C) sign(Fiy(C9)), We call s(C) the sign sequence of the cell C.
Definition 13
Sign sequences are sufficent to list the cells C(F). Though this proven various forms else- where (Jordan et al. (019)) we provide different proof.
Theorem
14
The function s is well-defined and injective.
Furthermore, the sign sequence of cell is determinative under conditions of supertransversality and genericity. For example, encodes the dimension of the cell.
Lemma 16 Let F be generic and supertransversal. Let C' be k-cell of C(F). Then s(C) has exactly To entries which are zero.
This leads to key geometrically dual relationship between the canonical polyhedral complex of supertransversal network and subcomplex of [-1, sending k-cells in C(F) to (no k--faces of the cube. will call this subcomplex S(F). Recall that a pure (su))complex is complex where every face is contained in some polytope of uniform top dimension.
Theorem 20 For each generic, supertransversal neural network F, the image of the map S C(P) - 1,, 0,1] gives a geometric duality between C(F) and pure subcomplex S(F) of the
hypercube 1], endowed with the product CW structure.
In particular, vertices of ((F) correspond to no-cells of S(F). Since the complex S(F) is pure and no di-dmmnniional, knowing which ne-lells are present is sufficient determine all face relations in the subcomplex of the hypercube. A corollary is:
Corollary. The sign sequences of the vertices of C(F) determine the face poset of the polyhedral complex C(F).
3.3
BINARY OPERATION ON SIGN SEQUENCES ENCODES THE FACE RELATIONS OF C(F)
The sign sequence complex has only one combinatorial type, cubes. This uniformity is related to package of formal properties which will be crucial in algorithmic implementation, with the existence of multiplicative "composition" derived from oriented matroid theory (Anders et 2000) being particularly helpful.
Lemma
18
If C and D are two polyhedra in C(F), the product S(C) S(D) given by:
S(())) S(D)g otherwise
if S(C) #0
(S(C) S(D)),
well-defined binary operation between sign sequences C(F). That is, there exists cell E in C(F) such that S(C) SDD) = =S(E) for all cells C and D. Thus, sign sequences of C(F) form a semigroup.
Following from similar constructions in hyperplane arrangements (Aguiar & Mahajan 2017 obtain the following:
Lemma 19 For all supertransversal networks, the following relations hold for all and in C(F), where S is the relation "is a face of":
S D if and only if S(C) S(D) S(D)
S(C) S(D) S(D) S(C) if and only if there is cell E with D S E and C C-C E. -(C)) S(C) if and only if C contained in the intersection of the maximal of bent hyperplanes which contain D.
These characterizations are primarily useful for using code to track face relations via discrete structure. As implemented in Section 4.2, the decision boundary network using sign sequences. These properties can seen illustrated in Figure
these to compute the topological properties of
5

---

Haa
H1,2
H2,1
H1,3
E E
Figure 3: "Multiplication" of polyhedra the sign sequence cubical complex, pictured geometri- cally. Under one possible co-orientation of hyperplanes, these cells have the sign sequences indicted in Table The product computed and pictured for certain pairs of cells.
Table 1: The sign sequence of the cells in Figure together with some computed products.
Cell
Sign Sequence
U
(1,1, 0, 0)
E
(1, -1, 0)
C
(1,1, -1
v. C
(1, 1,-1)
v. E
(1,2,-1, 0)
4 USING PROPERTIES OF S(F) TO COMPUTE C(F) AND ITS TOPOLOGY
The properties the sign sequence complex make it straightforward compute the combinatorial properties of the polyhedral complex of network across all dimensions upon obtaining the sign sequences of the vertices of C(F). Moreover, these sign sequences follow from locating potential vertices, thus knowing locations of the 0 entries in its sign sequence, and then evaluating the network to obtain its remaining signs. We summarize the process here, and provide the locations in the appendix for more precise statements of each lemma.
4.1 OBTAINING THE VERTICES OF C(F) BY CONSIDERING SIGN SEQUENCES
Grigsby & Lindsey (020) define the canonical polyhedral complex C(F) iteratively through layers. Letting R(() be the polyhedral complex associated with the hyperplane arrangement in layer k, the complex C(F& o ... Fi) is given precisely the intersection complex of C(Fk-1 (Fk-1 ... F1) ((R())) (See Definition 77 To obtain the vertices of particular network's canonical polyhedral complex, we may therefore begin by obtaining the vertices corresponding to C(Fi), first layer's canonical polyhedral complex. The exact computations needed are provided in Lemma 22
Fi) and
The sign sequences the top-dimensional regions which are present in C(Fi) can be determined by the sign sequences of the vertices of C(Pi), ignoring signs corresponding to neurons in later layers. The exact coboundary operation defining how to obtain these sign sequences is described by Lemma
21
Following the computation the first layer, subsequent layers' vertices may be found by analyzing the preimage of each bent hyperplane for additional intersections of & bent hyperplanes from the new layer together with no k bent hyperplanes from the previous layers. Since Fx-1 o... o Fj is affine each region of C C(Fk-1 this recursive step, see Lemma 23
Fi), restricted to each region, F.y (x) is affine. For details
We may therefore proceed iteratively through layers in order to obtain the full polyhedral complex. In summary,

---

Computing Sign Sequences. To obtain the vertices of C(F), and thus the ny-cells of S(F):
Compute the intersections of the hyperplanes from the first layer, as Lemma 22 Ob- tain their sign sequences by evaluating Fij on each intersection. Restricting these sign sequences to the signs of Fiş obtains (F)).
2. To compute C(F:), loop through regions C in C(Fi-1). On each region C,
(a) For 1 S k S no, compute the intersections of k bent hyperplanes from the new layer with no - k bent hyperplanes from previous layers, the latter of which are selected so that their intersection forms an Ro k-face of C.
(b) Evaluate Fig(x)) for each computed intersection x. Then keep x as a vertex C(F) if and only Faj (2) = FC)(C) for S k followiig Lemma 23
4.2 OBTAINING DECISION BOUNDARY TOPOLOGY FROM THE SIGN SEQUENCE COMPLEX
We next produce a chain complex enabling us to compute Betti numbers of the decision boundary. Readers unfamiliar with algebraic topology may appreciate the overview by Ghrist (2014), sections 4-6. The characterization of C(F) as dual to cubical complex permits us to define straightfor- ward mod-two cellular coboundary, which is the transpose of the boundary operation on the cubical complex.
Lemma 21 The face poset of C(F) the opposite poset of the face poset of S(F), and the (mod- fwo) cellular boundary map of S (FF) is dual to the (mod-two) cellular boundary map of C(F).
In other words, if C is a polyhedron in C(F), then replacing one location for which S(C);; 0 with +1 gives the sign sequence of a polyhedron containing C, and doing this operation for all locations computes all terms in the cellular coboundary of C ögnoring orientation). We recover the decision boundary of a network by noting that the decision boundary is the subcomplex of cells C' in C(F) whose faces D. including vertices, all satisfy F(D) O. By locating the vertices in S(F)) which have a O as the last entry in their sign sequence, this coboundary operation, with image restricted to those cells whose last sign sequence entry is zero, gives cochain complex of cells of the decision boundary, for example pictured in Figure 2
In general, the presence of unbounded cells makes this map not quite correspond to cellular chain complex. In particular, not every edge has two vertices. By adding single "vertex at infinity" to unbounded edges, the corresponding cochain complex has a straightforward interpretation as the cochain complex of the one-point compactification of the decision boundary.
4.3 NUMERICAL STABILITY AND ALGORITHMIC COMPLEXITY
Naively, if we compute a solution x to (x) = 0, and then numerically evaluate the node map However, we show in Lemma 23 (and the subsequent discussion) that machine epsilon-level errors obtained when solving for the
(c)) the result may not be exactly due to floating point
location of vertex will generally lead errors in computing the sign sequence of a vertex. When determining the sign sequence of a vertex, which of its signs are zero is determined by which hyperplanes were intersected, and the remaining signs are stable to small perturbations, since the sets F5 > 0 and F.j < ( are open sets. As long as the error in computing solutions to linear equations is small compared to the size of the cells in the polyhedral complex, the proposed algorithm will find the correct sign sequence of each vertex, and as result the correct combinatorics of the polyhedral complex.
Furthermore, as deep ReLU networks only have polynomially many regions in the number of hid- den units, at least on average at initialization (Hamin & Rolnick 2019a). and the number of possible combinations of A neurons from neurons together with no A neurons from no + ... + 7 neurons is also polynomial in the total number of hidden units, it is possible to obtain the canoni- cal polyhedral complex C(F) in polynomial expected time in the number of hidden units (Lemma 24). Further discussion of our algorithm's 's expected performance related to algorithms discussed in section 2 can be found in the appendix, in the discussion following this lemma.
7

---

5 APPLICATIONS TO NETWORK DECISION BOUNDARIES AT INITIALIZATION
We use this theoretical framework to make experimental observations. We obtain statistics about the decision boundaries of binary classification networks, and find stark differences in the behaviors of shallow and deeper network architectures. To our knowledge, this is the first experimental de- termination of the exact topology of large collection of decision boundaries with input dimension greater than two while having more than one hidden layer.
2-1-1
3-1-1
4-2-1
Averzyee B
Br
12
17
14
13
11
16
2:0-1:1
3-a-1
4 1-n-1
Average B
Bu
B:
B.
B.
Figure 4: Average Betti numbers of the network decision boundary at initialization for range of networks of shallow architecture (top) with deep architecture (bottom), together with standard error. The distribution of topological properties of the decision boundaries at initialization is surprisingly constant for shallow networks, and more variable for deeper networks.
5.1 EXPERIMENTAL DESIGN
We randomly initialize 50 networks of fully-connected architectures (k, n, 1) and (k, n, n, 1) for 2 < k S with standard normal weights and biases (See Figure 2 We will call the networks of architecture (k, n, 1) "shallow" and those of architecture (k, n, n, 1) "deep" for the purposes of comparison in this section. We compute the canonical polyhedral complex C(F) for each network using an implementation of the algorithm described in Section 4.1 using Pytorch linear algebra solver (Paszke et al.) 2019). We then obtain the Betti numbers B, for < sis k: of the decision boundary of the network at initialization, by constructing the boundary map determined in Lemma 2I] with additional point at infinity. The Betti numbers were obtained using Sage implementation of general chain complexes (The Sage Developers) 2018). The resulting Betti numbers provide measure of topological complexity of the decision boundary at initialization.
5.2 RESULTS
We observe that the topology of the decision boundary for shallow networks, regardless of input dimension, remains constant over the range of dimensions investigated. (See Figure 4 In contrast, for deep networks, there is both greater variability in the distribution of the topology of the decision boundary, and increasing width seems to, at least for Ro > 2, lead to the the topological properties of the decision boundary appearing change in distribution ture that a plausible explanation is that deep networks appear to require greater width before their network functions converge to Gaussian processes in distribution (de G. Matthews et al. 2018).
the width increases. We conjec-
The Betti numbers of the decision boundary, compactified with distinguished point at infinity, mea- sures the number of bounded and unbounded components of the decision boundary. Since all un-
8

---

bounded components are compactified by attaching them to the same point, in the compactification they correspond to (mu - 1)-cylles belonging to the same connected component, which are counted by 3no- 1. So the number of bounded and unbounded components can be computed by Po 1 and png-1 - 30 + 1, respectively
We observe that bounded connected components of the decision boundary initialization are rare, with frequency decreasing with input dimension in both shallow and deep networks: For exam- ple, 8.1% of networks of the form (2, n. 1) contain at least one bounded component, whereas only 0.05% of networks of the form (4, n1 1) contain as much at initialization. Furthermore, regarding the number of unbounded components, across all shallow networks investigated, the largest number of unbounded components observed at initialization was 3. with mode of I (average 1.0, 1.03 and 1.04, for no = 2,3, and 4 respectively). In deeper networks, in contrast, the number of unbounded components at initialization appears to be on average greater (1.1, 1 1.4, 1.4, respectively) reaching maximum observed values of 5, 7 and 12 for no = 2,3, and respectively. However, the most com- mon observation is still that a network at initialization has one unbounded connected component, and whether there is any trend associated with width is unclear. These observations lend additional credence to the notion that depth has stronger influence than width the topological complexity that a network can be easily trained to express.
6 CONCLUSION AND FURTHER DIRECTIONS
We have presented a new combinatorial characterization of ReLU network functions, and demon- strate its usefulness for obtaining topological information about networks which was previously difficult to access. The experiments illustrate the utility of this characterization for driving further experimental research on the properties of ReLU networks in different conditions. Furthermore, we believe this framework proposed could be used to derive additional properties of ReLU networks, as theoretically, we have provided a foundation to study the structure of the canonical polyhedral complex across all dimensions. In practice, a drawback to using this algorithm in empirical work that the algorithm is still an exponential process in the input dimension, so realistically only low- dimensional slices of the true decision boundary of a network can be investigated empirically.
We primarily believe that this tool can be useful to theoreticians by providing local characterization of vertices of C(F) which can be used to obtain geometric properties of ReL.U functions. For exam- ple, access to solid angles would allow for extensions to work such as [alestriero et al. (2019) on distributional properties of local curvature of decision boundaries. This local characterization addi- tionally makes piecewise linear Morse theory as in Grigsby et al. (2022): ;; Grumert (2017) applicable to C(F). Morse theory describes local extrema and saddle points by diagonalizing second deriva- tive matrix. Replacing a with +1 in a vertex's 's sign sequence identifies opposite edges incident to vertex, giving axes for a "piecewise linear second derivative."
Another possible future application of this work is to analyze topological generalization of networks. A key indicator of network's generalizability is whether its sublevel sets have the appropriate topological properties (Bianchini & Scarselli 2014). In addition, the architecture of a classifica- tion network influences the topology of the expressible decision boundaries of that network (Guss) & Salakhutdinov 2018). Empirically, topological data analysis provides practical approximation for low-dimensional features of high dimensional data. While approximations exist to obtain the topological properties of a network's 's decision boundaries using topological data analysis (Li et al.) 2020), these properties are dependent on the geometry of the network function. In places where the network's decision boundary has high curvature, the approximation methods may lead to inaccuracy between the true topology of a network's s decision boundary and the topology which is approximated by persistent homology methods, but it is precisely those locations where network is vulnerable to adversarial examples (Fawzi et al. 2018). A measure of the true topology of the decision boundary could provide metric for comparison.
We lastly believe it is possible to obtain an explicit understanding of the evolution of a network's s decision boundary through a training path. We conjecture that the changes in the facet structure of C(F) should be "discrete" in that they would only change at finitely many locations in a general training path, which would thus open an avenue for tracking the vertices of C(F)) as the network trains in parameter space, and establishing theoretical limits on the possible discrete changes that may occur to the set of vertices of C(F) during training.
9

---

REPRODUCIBILITY STATEMENT
We have provided source code and examples in the supplementary materials which can be used to reproduce our computational algorithms. The proofs of all numbered claims the body of the paper may be found in the appendix.
REFERENCES
Marcelo Aguiar and Swapneel Mahajan. Topics in Hyperplane Arrangements. American Mathe- matical Society, Providence, RI, 2017.
Motasem Alfarra, Adel Bibi, Hasan Hammoud, Mohamed Gaafar, and Bernard Ghanem On the decision boundaries of deep neural networks: A tropical geometry perspective. CoRR, abs/2002.08838, 2020. URL
abss///b//// http://aab//0...00/// 08838
Björner Anders, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Gunter M. Ziegler. Oriented Matroids (Encyclopedia of Mathematics and its Applications, Series Number 46). Cambridge University Press, paperback edition, 2000. ISBN 978-0521177506. URL https://lead.
to/ amazon/
Randall Balestriero, Romain Cosentino, Behnaam Aazhang, and Richard Baraniuk. The geometry of deep networks: Power diagram subdivision. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buch E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Sys- tems, volume 32. Curran Associates, Inc., 2019. URL
ngs neurips pdd
cC/
Monica Bianchini and Franco Scarselli. On the complexity of neural network classifiers: com- parison between shallow and deep architectures. IEEE Transactions Neural Networks and Learning Systems, 2533) August 2014. doi: 10. 2.110 URL
/ttts:///oo..rr/00011000
2013. 2013.2293631 2293637
Carina Curto, Alan Veliz-Cuba, and Nora Youngs. Analysis of Combinatorial Neural Codes:
An Algebraic Approach, pp. 213-240. 01 2019. ISBN 9780128140666,
doi: 10.1016/
B978-0- 10--1112--1166660 4066-6.00007-66
Alexander G. de G. Matthews, Jiri Hron, Mark Rowland, Richard E. Turner, and Zoubin Ghahra- mani. Gaussian process behaviour in wide deep neural networks. In International Confer- ence on Learning Representations, 2018. URL http:s::/oppereriiieeeeee net/ www.:ner/foommmttoo forum? i 1l-nGgwc-]
Alhussein Fawzi, Seyed-Mohsen Moosavi- Deosavi-Dezfoolli Pascal Frossard, and Stefano Soatto. Empirical study of the topology and geometry deep networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
Robert Ghrist. Elementary applied topology. Createspace Independent Publishing Platform, North Charleston, SC, September 2014.
J. Elisenda Grigsby and Kathryn Lindsey. On transversality of bent hyperplane arrangements and the topological expressiveness of relu neural networks, 2020. Available at htttps://axxvz. htt//bb//2000 09052
J. Elisenda Grigsby, Kathryn Lindsey, and Marissa Masden. Local and global topologica complexity measures of relu neural network functions. arXiv, 2022. doi: 10.485.0/ARXIV2200..000 URL
hittp:://arxiv http:xi.wrg/abs/////// 200p:///22220..62222.
Romain Grunert. Piecewise Linear Morse Theory. PhD thesis, 2017. URL httttt::s///rfbbiiii
fu-ber1: http:rireeeeeaaae/eei/ieaeaee
V. Guillemin, V.W. Guillemin, A. Pollack, V.A. GUILLERMIN, and P. Alan. Differential Topology.
Mathematies Series. Prentice-Hall, 1974. ISBN 9780132 16652.
10

---

William H. Guss and Ruslan Salakhutdinov. On characterizing the capacity of neural networks using algebraic topology. CoRR, abs/1802.04443, 2018. URL http: /tt///axiiii. org abs www.aasss.10 1802. 04443
Boris Hanin and David Rolnick. Deep relu networks have surprisingly few activation pat- terns. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019a. URL 9766527 2
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. ArXiv, abs/1901. 0ts//191..0021, 2019b.
Vladimir Itskov, Alexander Kumin, and Zvi Rosen. Hyperplane neural codes and the polar complex. In Nils A. Baas, Gunnar E. Carlsson, Gereon Quick, Markus Szymik, and Marius Thaule (eds.), Topological Data Analysis, pp. 343-369, Cham, 2020. Springer International Publishing. ISBN 978-3-030-43408-1
Matt Jordan, Justin Lewis, and Alexandros G Dimakis. Provable certificates for adversarial exam- ples: Fitting a ball in the union of polytopes. In H. Wallach, H. Larochelle, Beygelzimer, F. d'Alché- Buch E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Sys- tems, volume 32. Curran Associates, Inc., 2019. UtL/ neurins. cc
Weizhi Li, Gautam Dasarathy, Karthikeyan Natesan Ramamurthy, and Visar Berisha. Finding the homology of decision boundaries with active learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances Neural Information Processing Systems, volume 33, pp. 8355 8365. Curran Associates, Inc., 2020. URL https::/ neurs neurips. CC/
Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. Advances in neural information processing systems, 27, 2014.
Vinod Nair and Geoffrey E. Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th International Conference on International Conference Machine Learning. ICML' (C, pp. 807-814, Madison, WI, USA, 2010. Omnipress. ISBN 9781605589077.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. Curran Associates, Inc., 2019. URL http: /tett://paaaee htwppaapppppsaaaaeeeeeeeeeeeee.. wwwr cttps/scceerprp...ppprpr.rrrr 9015 wwwppyy-oa-a--.o. mperat ve httt://een-hg-errrrmmmmeeeeeeeee pdf
librar.r
Thiago Serra and Srikumar Ramalingam. Empirical bounds on linear regions of deep rectifier net- works. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5628- 5635, 2020.
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. In ICML, 2018.
The Sage Developers. SageMath, the Sage Mathematics Software System (Version 9.0), 2018. https:/ /www//ww...ooo//...o www.saaa.......... org.
Huan Xiong. Lei Huang, Mengyang Yu, Li Liu, Fan Zhu, and Ling Shao. On the number of linear regions of convolutional neural networks. In International Conference on Machine Learning, pp. 10514-10523. PMLR, 2020.
Xiaodong Yang, Hoang-Dune Tran, Weiming Xiang, and Taylor Johnson. Reachability analysis for feed-forward neural networks using face lattices. 2020.

---

Xiaodong Yang, Tomoya Yamaguchi, Hoang- Hoang-Dung Tran, Bardh Hoxha, Taylor T Johnson, and Danil Prokhorov. Reachability analysis of convolutional neural networks. 2021.
Liwen Zhang, Gregory Naitzat, and Lek-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 Learning Research, pp. 3824-5832, PMLR, 10-15 Jul 2018. URL https::/prroceddingg ml hatpaa/aaaa.....pppp///////aaaaa
html
Xiao Zhang and Dongrui Wu. Empirical studies on the properties of linear regions in deep neural networks. In International Conference on Learning Representations, 2020. URL https://
openreview net/
A APPENDIX
A.1 MATHEMATICAL BACKGROUND
summary of relevant results and definitions about polyhedral complexes and complexes arising from affine hyperplane arrangements found in Grigsby & Lindsey (2020). Sections 2-3, and [rrnner (017)) Sections 1-2, with the most relevant information repeated below. Namely, we make repeated use of polyhedral geometry:
Definition (Polyhedra, Polyhedral Complex, cf. Grigsby & Lindsey (0200).
A polyhedron is an intersection the form Nisism H for some set of (codimension 1) hyperplanes HI...., Hm C RR. Here H is the half-space of RR consisting of the union of the hyperplane H; and one of the connected components of R HH
We will say a point on the interior of a polyhedron P if it on the interior of P with respect to the subspace topology of the affine span of P, except when P is point, in which case by convention its interior is nonempty. We use the notation pe to denote the interior of P.
A face of polyhedron P embedded in TR set of the form H I P. where H is codimension 1 hyperplane in R" and H O P does not contain any interior point of P. (The empty set face of any polyhedron.) A hyperplane which intersects P in a nonempty face is called a supporting hyperplane of P. All other hyperplanes which intersect P are called cutting hyperplanes of P. We denote the relation "C is a face of with C < D.
A polyhedral complex embedded in IR' is a set of polyhedra contained in R" which is (a) closed under taking faces, (b) closed under intersection, in that the intersection P1 n P2 is the (unique) maximal common face of P1 and Ps,, which may be empty.
Under this definition, polyhedra may not be bounded, but they are always closed. As a result, an affine hyperplane arrangement induces natural polyhedral decomposition on its ambient space. We use the following notation for consistency with previous work, providing a notation for affine hyperplane arrangement R(O) associated to an affine map A;-
Definition 2 (T, R(,, cf. Grigsby & Lindsey 2020), Definition 6.7). Let A; R - R2 be an affine function for 1 < n. Then, we define:
Jj is the linear projection onto the jth coordinate in R
R(0) is the polyhedral complex associated to the hyperplane arrangement in IR 1, induced by the hyperplanes given by the solution set to Hij = {xr E IR" T A((x) =).
Continuing the framework in Grigsby & Lindsey 2020). we investigate the following class of neural network functions.
Definition 3 (Grigsby & Lindsey 2020)) Definition 2.1). Let np...., Rem E N. A fullyy-coneettd
ReLU neural network with architecture (no, Dom 1) collection N {Ai) of affine maps
12

---

: - R for i 0, ..., m. Such collection determines function Fx Ro associated neural network map, given by the composite
R, the
Re00 Fi=RoLUOAi
Ag
R Ps=
G=Am+1
R
where ReLU refers the function max applied pointwise Nair & Hinton 2010 this network has depth m + 1 and width max Res 13. The maps Fy are called the kth layer maps.
We say that
As piccewise-afline linear function, Ex, which we simplify to F, defines an obvious polyhedral decomposition input space, namely into the (largest) polyhedra on which it is affine-linear. How- ever Grigsby & Lindsey (2020) show the utility of considering not only the decomposition which F itself defines, but the common refinement of decompositions by intermediate composites.
Definition 4. F oo Fm denote:
Fi is ReLU neural network with F. R + R. then
(()) = Fx F1
and write that this is F ending at the kth layer. Likewise, we denote
(E)) G o... Fi
and call (K) PR----1 - T by F starting at the kth layer.
Thus F F(K) o F(k-1) 1) for any k. definition for the canonical polyhedral complex C(F) through universal property can be given the common refinement of the polyhedral decomposition of input space such that all F(c) are affine linear on cells. For implementation, we prefer a definition through explicit identification of cells, using further language from Grigsby & Lindsey (2020):
Definition (Fig Grigsby & Lindsey (020), Definition 8.1 ). If F is a ReL. neural network, the node map Fig defined by:
J. o A A Fi
R.0 - RR
In particular, the locus in input space where Pij O is of particular interest, and to draw analogies hyperplane arrangements, we the phrase "bent hyperplane."
Definition 6 (Grigsby& & Lindsey 2020). Definition 6.1 ). A bent hyperplane oFF is the preim- age of under node map, that is. F.j (0) for fixed i,j-
bent hyperplane can contain polyhedral regions with codimension less than one, but this occurs with zero probability. The conditions under which the bent hyperplanes' maximal cells are always codimension are listed by Grigsby & Lindsey (2020).
The original definition of the canonical polyhedral complex C(F) uses the notion of "level set complex," " defined by Grunert (2017). We streamline the definition, working more directly in two ways, as needed below.
Definition (Canonical Polyhedral Complex C(F), ef. Grigsby & Lindsey 2020)) Definition 6.7).
Let F T no
R be ReLU neural network with layers. Define C(F) ) as follows:
1. (Forward Construction) Define ((F()) by R()) (Definition) 2.. Then let C(F()) be defined in terms of C(F(k-1)) as the polyhedral complex consisting of the following cells:
C(F(s) = (CnET- : C(F(k-1)) R(()
Then C(F) is given by C(F(m))-
13

---

2. (Backwards Construction) Define C(F(m) by R(m), Then C(F(k=1)) can be defined from C(F(R) as the polyhedral complex consisting of the following cells:
C(F(R-1)) = R (C RE R( D C
Then C(F) is given by C(F()).
That the two are equivalent follows from the distributivity of function preimage over set intersection (or, more generally, associativity of pullbacks). That the resulting construction is indeed a polyhedral complex discussed thoroughly by Grigsby & Lindsey (2020) and Grunert (2017). In particular,
we make use of the following lemma regarding boundary relations, rewritten so as to not require additional notation.
Lemma 8 (cf. Grunert (207)) Lemma 2.4). Let M T. and N C R" be polyhedral complexes and f IM] + IR' be continuous and affine on cells of M. Let S denote face relations in the respective polyhedral complexes. C S C' are polyhedra in M, and S D' are polyhedra N, then
CD
is a face relation in the polyhedral complex consisting of the cells (CnF=!(D) : M).
The notion of transversality on cells will be critical for the next section. Function transversality is discussed in textbooks such as Guillemin et al. (1974).
Definition (Grggsby Lindsey (2020), Definition 4.5), Let X be a polyhedral complex of dimen- sion d in R"," let I:: [ Re be map which is smooth on all cells of X and let Z be smoothly embedded submanifold (without boundary) of TR". We say f is transverse on cells of X to and write f thx Z if the restriction of f the interior C of every k-cell C of X is transverse Z when 0 < k k d
Lastly, we will need the following notions of generic regarding hyperplane arrangements and neural networks, respectively.
Definition 10 (Grigsby & Lindsey (2020) Definitions 2.7, 2.9). A hyperplane arrangement in R is called generic if each all sets of hyperplanes intersect in an affine space of dimension n. A neural network is called generic if all of its affine maps A, have generic corresponding hyperplane arrangements, R(())
Grigsby & Lindsey (2020) also established that the union of bent hyperplanes of C(F) form the (No faces of C(F) with probability 1. In the next section we expand on this characterization
for lower-dimensional subcomplexes.
The reader is referred to Ghrist (2014) for a brief background in algebraic topology, especially the notions of homology and cohomology, chain complexes, and duality (sections 4-6).
A.2 NEW DEFINITIONS AND PROOFS
We begin by defining key additional condition on neural networks, which is necessary for many of the results in this section to hold.
Definition 11. Let F be ReLU neural network of depth m. Let F(-1)) 1R + IR be the neural network defined by the last m i layers of F as in definition 4 Suppose, for all
n, F; is
transverse on cells of R( to the interior of all cells of ((F((+1) neural network.
Then we call F supertransversal
The condition of network supertransversaliiyy is stronger than the notion of network transversality in Grigsby & Lindsey (2020) (Definition 8.2), but it still holds on a full-measure subset of parameter space, we show here.
Lemma 12. Supertransversalityy full measure in TRP,, where P is the set of network parameters.
14

---

Proof. First, single-layer neural network F(m) RRnm - R is trivially supertransversal,; R has one cell which is already full dimension.
Next suppose that F(k) is supertransversal, and let F6-1 R
RR be a network layer.
Suppose it the case that Fk-1 is nontransverse on some cell of R(+-1) to some cell C ((F())) If so, it must be the case that (R) n C' is nonempty and T( @ T(C) * R Call (((F-1(()) @ T() by TR.C. If TR, o IR then it is instead a vector subspace of less than full rank, and an affine translation of C ((F()) by any vector in R -R.Cc will ensure (R) subsequently empty, since I' is affine on R and C' contained in affine subspace of R
Let ôn be the minimum distance between pairs of points in F and C. Since these cells are closed (though not necessarily compact), this is well defined, and furthermore if R C 0, then OR. > O. Let ò = {min OR ( n C = 0}. Then > 0.
Since there are finitely many cells R and C, the
R Rk-1
UTC. R2C
is generic in RT--1,, where the union is taken over only those cells where TR,C is not full rank. An affine translation of C(F(R) by any vector in this set with magnitude greater than 0 but less than 8 yields a supertransversal network.
Since this can be performed regardless of the weights and biases of Fk. and an affine translation of the input space of ((k) does not change its supertransversality properties, the network Fk-1 o F()) supertransversal on full-measure subset of parameter space, which completes our inductive step.
The combinatorial characterization of C(F) is through the following combinatorial construction called sign sequences. The primary use of these sign sequences is to track face relations.
Definition 13. Define C(F) + f 1,1 by sty (C) = sgn (C))()))). We call s(C) the sign sequence of the cell C.
This refers to the sign of the function Fiy when restricted to the interior of C. To see that this is actually a function on cells, we will see that for any points z, y on the interior of C, Fiy(z) = sgn(Fi
This construction used in the theory of oriented matroids and hyperplane arrangements, cf. Aguiar & Mahajan (2017), and in particular the construction may be used to identify polyhedra in affine hyperplane arrangement by denoting which halfspaces and hyperplanes were intersected to form that region. However, any analogous properties for ReLU networks must be proven, as many of the properties below fail to hold for arbitrary PL manifold arrangements. We must show that the construction still provides combinatorial description of the polyhedra of the network:
Theorem 14. The function is well-defiedd and injective on cells C(F).
Proof. To see that s is well-defined, suppose F1, 22 E Ro are such that sgn (g((F((21)) + (gn(F for some i,j. We wish show that æi and 22 are not the same cell of C(F). However, we see that the images F;-1 o o... Fi (z1) and F; o Fi F2(2) cannot be in the same cell of of ((()) (the induced polyhedral decomposition of IR--11 by A,). because they differ in their
location relative to the jth hyperplane. Thus 2 and 22 are in different cells of C(F()). As C(F) is further polyhedral subdivision of C(F()), I1 and 22 are in different cells of C(F). So, is well defined.
Next, suppose Co and Ci are cells such that sCC) sCi). Le Co and æ1 C.. We wish to show Co = C₁. We proceed by induction on layers in the forward direction.
We show first that, base case for induction, 20 and xi are in the same cell in C(Fi).
Indeed since s(Co) s(C1), zo and xı are contained in the same cell of R()), following the corresponding fact for hyperplane arrangements, this immediately means that 2n and क are in the same cell of C(Fi).
15

---

Now suppose an inductive hypothesis that Zy and 21 in the same cell of ((F())) Call yo F(g) (ao) and this implies that yo and Y/1 are in the same intersection of halfspaces and hyperplanes in the co- oriented hyperplane arrangement A1+1, that is, the same cell of R(++1), Therefore, as 21 and 22 are in the same cell C of ((F()) and their image in the same cell C' of [((k+1) conclude wg and di in the same cell in C ((((+1)) given by
((a)(21) Because sgn( (gn(Fe=1))(m1)
sgn( (1 for all 0 I S ni.
CD(FA+H))
That this is a unique polyhedral cell in ((((x+))): follows the work in Grunert (017)) Lemma 2.5. By induction, as composed finitely many layers, 20 and v are in the same cell of C(F). O
Figure 5: Even if M; are codimension-l connected co-orientable PL manifolds embedded in IR" whose intersection subdivides I into polyhedral regions, and the resulting polyhedral subdivision dual to cubical complex, it is possible that labeling each region by its location relative to the co-orientation of those manifolds fails be injective. This example depicts 3 PL submanifolds in R² whose embedding has the aforementioned properties, but there are too many cells (14 vertices, 30 edges, and 17 2-gons) to be labeled by the 27 possible labelings {-1.0, 0,
The injectivity of s is special to constructions arising from hyperplane arrangements, and not general manifold arrangements. Indeed, even a set codimension-1 PL submanifolds subdivide R" in way which this injectivity fails; see Figure 5
Below we show that C(F) can be reconstructed from vertices and sign sequences. It is more tradi- tional to work "top down," considering the top dimensional polytopes and their facets. But unlike theories such as hyperplane arrangements and oriented matroids, there no guarantee that know- ing the sign sequences of the top-dimensional regions allows one to deduce the sign sequences of the zero-dimensional regions (circuit-cocircuit duality does not hold). The following example is an explicit illustration of this fact.
There exists a pair of networks F, and F2 such that the set of strings encoding the activation patterns in the interiors of the cells of C(Fi) and C(F2) are equal, but the polyhedral complexes C(Fi) and C( ((2z) are not combinatorially equivalent.
Theorem 15.
Proof. We provide example in Figure 6 Two neural networks Fi 1R2 - R2 - R and Fg R² + R4 + R have the pictured canonical polyhedral complexes. One has a bounded decision boundary, whereas the other is unbounded. However, both have identical sign sequences of their top-dimensional regions, given by:
(.1,1, -,,,,,-L--1,,, 11,11,,,, (1,-1,1,-111 1,, 1,, (1,1,-1,1.
1,11).
(1,1,1,-11 11,1),111-11,, 1,,1) 11,-1,1,111)
1,
(1,11,111-1)) (1,11,1,1111,,,
1,,
16

---

Figure 6: The canonical polyhedral complexes pictured below have differing combinatorics and differing topology of their decision boundaries, but the set of sign sequences of the top dimensional regions equal (see Theorem [5]. Explicit weights and biases for this construction are available in the code provided with the supplemental material.
That these canonical polyhedral complexes have the same sign sequences of their top-dimensional regions is more easily seen by looking at the differences between the two pictures, which only depend the blue "decision boundary." Each region which is subdivided into regions by the blue bent hyperplane in the left image is also subdivided by the blue bent hyperplane in the right image.
As illustrated in Grigsby & Lindsey (2020), it is not always the case that the preimages (0) are 72 dimensional. In order to establish dimension, supertransversality and genericity are key.
Lemma 16. Let be generic and supertransversal. Let C be a k-cell of C(F). Then s(C) has exactly no - k entries which zero. That is, C is contained in the intersection of no k bent hyperplanes.
Proof. This is certainly true for any neural network of the form G o Fm satisfying the condition that Fm is generic as a layer map, as the bent hyperplane arrangement is equal to the hyperplane arrangement, which is generie hyperplane arrangement (Definition I0
We proceed via induction, using the backwards construction of C(F) (Definition
Suppose by way of induction F()) G o F. o F;, and that C(F(#) satisfies the condition that C' E C(F()) is a k-cell if and only if C' is contained exactly n, - bent hyperplanes.
Now, suppose F--1 is transverse on the cells ( to C for all C: in ((F)). Consider (i-1) Go Fm o... F, e F,-1-
Let C' be cell in C(F(-11). Note that by definition, C' is given by (C) D for some C C(F()) and some minimal (by inclusion) cell D of R(f-1), particular, we may assume C" is not contained in any proper face of D. If D has codimension é, then D is in the intersection of exactly e hyperplanes in (i-1) by the genericity of F. Because F1 is transverse on cells of R(i-1) C, codim(C') (C") in the interior of D is equal to codim(C) k. with total codimension l +
As C' is contained in the intersection of exactly & bent hyperplanes in C(F()), C" is contained in the intersection of the preimage of precisely those same bent hyperplanes in B(F((-))). Furthermore C' is contained in the intersection of the hyperplanes in R((-1) which intersect to form D, and no additional hyperplanes C" is not contained in any proper face of D. Thus C" is contained in the intersection of precisely k + f bent hyperplanes in C(F(i-1) and has codimension A f. The number of zeros in s(C") must be equal to the number bent hyperplanes it is contained in, by definition. This completes the inductive step.
17

---

In order to establish additional properties regarding the existence of cells satisfying certain relations in supertransversal networks, we rely on the following lemma.
Lemma 17. Let f M IR be a PL map affine on cells of an embedded polyhedral complex M C IRm Let N be a polyhedral complex embedded in R Suppose f is transverse on cells of M the interior of all cells of N.
If C S. C² is a face relation in M, D D' is a face relation in N, and f(C%) D is nonempty, then f(C²)) i D nonempty.
Proof. First we show that ((C²) n D is nonempty. If D consider f(C), which is the image of the polyhedron C' under an affine map. If the affine span A of f(C) does not intersect the interior of D', then A n D' is contained in proper face E' of D'. In this case, T(f(C) e T(E) & Rh, and f is not transverse on to E'. Therefore, A i D is nonempty.
D' then we are done. Otherwise,
Within A we have a(A n D') S Ana(D"). As a result letting x E C and f(x) E D', every open neighborhood of ((x) in A must have nontrivial intersection with the interior of D'. Take open neighborhood N of x in C We note that f C + A is a submersion (locally a surjective linear map). Thus f(V) is open A. and N n D must be nonempty, so CP f n nonempty.
To see that D is nonempty, take z E C with f(z) E D If is a neighborhood of f(x) in D then (N) must be an open neighborhood of æ in M, containing æ C. As C C a0' (N) C" is nonempty, so f(C") n D' is nonempty.
Now we can define a key algebraic structure which will lead us to be able to deduce the structure of C(F) in general, in particular an algebraic structure which allows to generate all sign sequences which are present from the sign sequences of the vertices. The following holds for all supertransver- sal networks (and does not rely on the layer maps being generic).
Lemma 18. Let F be supertransversal neural network.
C and D are two cells of C(F), the product S(C) S(D) given by:
S((C) S(C) +0 S(D)g
(S(C) S(D))
otherwise
well-defined as product between sign sequences. That is, there exists cell E in C(F) such that S(C) S(D) = =SEE) for all such cells C and D.
Furthermore, C < E, that is, C a face of E or equal E.
Thus, sign sequences of supertransversal network form a semigroup.
First, this is true for any single- layer network F 2m + R. since it is true for hyperplane arrangements; see Aguiar & Mahajan 2017), Section 1.4 for treatment.
Proof.
Now, suppose these properties hold for any supertransversal k-layer neural network and inductively, using the backwards construction of C(F), let F be a k + 1-layer supertransversal neural network. Then ((2) = G o F6+1 c... F2 is a k-layer supertransversal network and our inductive hypothesis holds for C(F(2)). We will denote the sign sequences of cells with respect to C(F(2)) ( by (C).
Let O' and D be cells of C(F)- = C(F(2) o Fi). Then C = Rí (C") and D = R2 n FA (D"), for cells R1, Rg in R(!) and cells C², D' E C(F(2)), by the definition of C(F). Now, by inductive hypothesis 5t2) (C") ((2) (D' 5(2) (LE) for some cell E" in C(F(2)), and C" is a face of E".
Denote the sign sequences with respect to R(1) as St. Since R(11) is a polyhedral complex induced by an affine hyperplane arrangement, (R() (R2) = S1 (Ra) for R3 a region in R(1, and R is face of R3 equal R3-
Let E = R3 n FT (E'). We wish to show that S(C) S(D = S(E), and that C is a face of E or equal to it. Now, S(C) is obtained by S, (R,) concatenated with S(2) (C"). and likewise for the other cells. Since Si (R1) (R2) (Rs) by the corresponding hyperplane arrangement and
18

---

(C)) (()) (D") S(E)) by inductive hypothesis, by concatenation this gives S(C) S(D) S(E).
To see that E is nonempty must note that since F' is supertransversal, Fi is transverse on Rı to
C", and apply Lemma 17 to obtain that R3 n FT (E") is nonempty.
Lastly, we recall from Lemma that C' S E' and R1 I R3 implies that (FT n R1) (FT (E") n R3), that is, C S E.
The following properties of the product defined above are analogous to the same properties in hy- perplane arrangements.
Lemma 19. For all supertransversal networks, the following relations hold for all C and D in C(F), where the relation & denotes "is a face of":
1. C & D and only if i(C) -(()) S(D)
2. S(C) S(D) = S(D) S(C) if and only if there a cell E with S and S
3. S(C) S(D) = S(C) if and only if all bent hyperplanes which contain D also contain C.
Proof.
1. We have already shown if S(C) S(D = S(D) then C < D. -(D) # S(D) then there is some index where Stg (C) =1 and Siy (D) - (Sy(())) If so, then C and D are sent to opposite sides of some hyperplane in some layer; this cannot occur if C s D.
2. Immediate from the previous statement and Lemma 18
3. S(C) -S(D) S(C) if and only if for all node maps for which (C) 0, also have (D) = 0. But this true and only if all bent hyperplanes which contain C' also contain D).
We now assemble these ideas present duality between the canonical polyhedral complex of generic, supertransversal neural network and a pure cubical complex, providing a surprising amount of new structure the combinatorics of the canonical polyhedral complex.
Theorem 20. For each generic, supertrunsversal neural network
with least no hidden units in the first layer, the image of the map S C(F) - (-1,0, 13" uniquely defines a pure no -iddenensional subcomplex of the hypercube [-1, 1} endowed with the product CW structure. We will call this subcomplex S(F). In the image, the vertices in S(F)) correspond to no no-cells in C(F), and in general the k-cells of S(F) correspond to codimension-k cells of C(F).
0,
Proof. Recall that cubical faces of [-1, (with its product CW structure) can be identified by sequences of 1,1,0,1}
First if F has least no hidden units the first layer and it is generic, then C(F) contains vertices as some of its cells, since the intersection of nu hyperplanes in general position in R is point. Since C(F) is connected polyhedral complex, if any of its polyhedra have vertices, then all of them do (see Grigsby et al. (2022). Corollary 5.29).
For any C C(F) there is a vertex v S C. There are no coordinates where S(v) by Lemma 16 Furthermore Sw) S(C) S(C') by Lemma 18 Thus S(C) is equal to S(v) except those places where S(x) = 0. But this is equivalent to the condition that the cell Suv) E S(F) has S(C') on its boundary. So, every in the image of S(F) is contained in an ng-cube which is also in the image of S(F). (There are no nop + l-cubes in the image of S(F) by Lemma 16) Thus the image of S(F) is "pure dimdiiensio in the sense that every cube in S(F) is a face of nu-e in S(F).
Next we show that for a given cube in the image of S(F). all its faces are in the image of S(F). Our strategy is to show that there exists edge corresponding each possible sign sequence
19

---

incident to the corresponding vertex. Then we may apply the sign sequence multiplication in Lemma 18 to obtain all remaining faces. This is equivalent to establishing that a vertex v of C(F) has 2no neighboring edges, each of which have 1 or -1 replacing single 0 from S(v). Of course, any vertex must be incident to at least no edges since it belongs to a polyhedral complex with domain R"o, so we show that if there exists an edge incident to e with S.y (F) 1 while Siy(v) 0, then there also exists an edge with (b)) = -1 (and, by symmetry, vice versa).
Suppose that this not the case for some v. Then without loss of generality there exists an earliest (i,j) node map satisfying that (vy(u) = 0 but for all edges E neighboring in C(P)), Fay 2 0, since for each edge E. SEE) differs from S(v) only in one location. Since the edge set of is nonempty, this implies that Fly cannot be affine on any affine subspace of R containing unless
Fij = 0 on that subspace.
As cannot be vertex of ((F()))), since it is contained in the intersection of fewer than no bent hyperplanes before Fij. it is contained in the interior of a larger cell C in ((F As a result, Fiy is affine on the interior of C. But by the previous paragraph, this means that (C)(C) = 0, and thus F(s) is not transverse on C' to a cell contained in R and cannot be transverse on C' to any polyhedral subdivision (including C(F())). This implies that there is a layer of F(-11) which fails to be transverse on cells, which is a contradiction.
So, if is vertex of C(F), then for each node map F. such that (t)(t) = 0, has incident edge with (E) = and an incident edge with (B) = -1 by the same argument, We note by supertransversality that S(E) must have no entries which are zero. Also, since v is incident to E. by Lemma 19 S(E) E') must have the same entries as S(V) except possibly where S(v) = 0. This means S(E) S(v) except for the (i.j) coordinate, as required. Since this occurs at all node maps for which Fay = 0, we are done.
Once the existing cells in S(F) have been located, we only need to establish an explicit duality. The majority of the work has already been done.
Lemma 21. The face poset of C(F) is the opposite poset of the face poset of S(F), and the (mod- rwo) cellular boundary map of (F)) is dual to the (mod-two -two cellular boundary map of C(F).
Proof. In [-1, the cells consist of cubes which are uniquely defined by their center, at points given by sequences in 1-1, 0, 13.a. The dimension of each cube is given by the number of 0 entries in this sequence. The cellular boundary of this cube consists of cells one dimension lower, with
1 or -1 replacing a 0 in the sign sequence, providing the (mod two) boundary in S(C). In C(
if s(C)) is related to s(D) ((D by replacing one zero entry of C with 1 or 11, by Lemmas 19 and 16
that this is equivalent to C S D and (C) + = dim( DD), which is equivalent to C' being in the (mod two) cellular boundary of D.
Lastly, we prove that the process of computing C(F') can be done iteratively through layers, begin- ning with the first layer:
Lemma 22. Let F be a supertransversal, generic neural network.
The O-cells of ((F()) are given by the solutions to
(War x = ba : C [m1] & |a| = nu}
where W is the weight matrix of the network and a denotes a subset of the nı vertices.
A vertex obtained by solving Wax ba satisfies sı(v) 0 iff i
Proof. These are the vertices of a generic, affine hyperplane arrangement.
In order to compute the vertices of C(F) corresponding to bent hyperplanes from further layers, we loop through regions C' of ((F(k=1)) and solve systems of linear equations arising from no bent hyperplanes on that region, at least one of which corresponds to a new bent hyperplane Fej- The following lemma guarantees that if we select these combinations of Fú corresponding to earlier layers from only those which intersect to form cells on the boundary of C, we are guaranteed to obtain all new vertices in ((F())).
20

---

Lemma 23. Let F be a generic, supertransversal neural network with at least ng hidden units in its first layer.
If C is cell of C(Fk-1 o F1), then (C)(C) is affine for all i S k. Call the corresponding affine map Aij"
2 + R. Then,
1. All O-cells of C(F& already in (F o... o Fi) are the solution to a system of no affine equations, of which
Fi) which are contained in the closure of C and which are not
1 S i no are of the form:
Akm (x) 0
and 0 S no - L no - equations are of the form:
A,,()) = 0;
Here, the Auy of the no equations from earlier layers selected such that there exists a vertex of C in the intersection of the corresponding bent hyperplanes. In other words, the remaining no l equations describe the affine span of a face of C.
2. A solution to the system of equations described in (1) corresponds to a O-cell of C(Fx Fi) contained in the closure of C if and only if, for all remaining (i.5) pairs with
i S k - 1, we have that 81)(1) =8i; (C).
Proof. For statement (1), suppose that is in the closure of C, where C is cell of C( Fi). and e' is a vertex of C(F) o F.). By Theorem 20, v is the solution to F (xy(x) = 0 for exactly no node maps. Since Fiylc Aey. then (v)
for those no node maps. If node maps Fij, then in fact v is O-cell of C( F and not vertex of C(F&-1 o ... Fi). least one of the Fiy must be a node map with i == k. Thus, any vertex of C(F₁ o Fi) which is contained in the closure of C' must be a solution to a system of equations of this form. For any solution of this form to be nonempty when intersecting with the closure of C, the the Aij corresponding to this system of equations must satisfy the condition that Cnn(=: (x) = 0f is nonempty. Since none of the Ay from earlier layers intersect the interior of C. the intersection of the A, describing the linear span of face of C, which must contain vertex of C.
for all of these o F2). So if v is vertex of C(F; o... o Fi)
For statement (2), of course if is solution the system of equations described in (1) and also is in the closure of C, then by Lemma 19, (1)(v) = (Cy(C)) when < k - 1, except for where s;y(v) = O, which by Theorem 20 occurs for precisely the bent hyperplanes which were intersected to obtain 8ij.
In the other direction, if i is solution the above system of equations but is not 0-cell of C(F), it must not be contained in the closure of C. Then x is contained in the interior of some other cell of C(Fx-1 o ... Fi). call it D, such that D) is a face of C (Figure A.2 If there is some bent hyperplane corresponding to one of the remaining (i, pairs such that s;y (D) o sty(C)) then we are done. Otherwise we will see a contradiction. If S(D) S(C)) except at (i, pairs corresponding to some of the Aij, then by our selection of equations earlier, there is face E of C' which has the sign sequence equal to zero at these coordinates (contained the intersection of the solution of Azzæ 0). If E D, then D is a face of C' and we have a contradiction. The only other option that is a proper face of D by Lemma [9 The intersection of the solutions to Aij = O contains the affine span of E, so the intersection of these with the closure of D is contained in proper face of D. and so r, an element of this intersection, cannot be in the interior D. This contradicts our assumption that is in the interior of D.
This shows that if is a solution to the above system of equations but is not a O-cell of C(F), then there exists some (i.j) pair with i k-1 such that siy (I) # (C) and which does not correspond to the hyperplanes which were intersected.
21

---

S(C) (+....,
[Aem]
{Ag) =0
Wu1
S(D)
Figure 7: When determining if solution x to the system equations in Lemma 23 vertex of (()())) we look at its sign sequence. However, its sign relative to [Aij] is numerically unstable. We would like to guarantee belongs to the closure of by evaluating the node maps which do not include Asj. A concern is that it is contained in different cell D with identical signs to C in ((F(x11) except possibly the locations of the Aij which we intersected, which would make this task impossible. The argument in part (2) shows this does not occur, and the situation pictured above impossible.
A note on numerical stability: Suppose that in step (1) we only find an approximate intersection ã instead of an exact intersection æ, with - x| determined by machine precision. According to the above lemma, if do locate the exact intersection x, determining whether this point is ver- tex the polyhedral complex C(F) relies only on determining the sign Fo (x) for indices (i,j) corresponding to the bent hyperplanes which were not intersected. Under the supertransversality sumptions, Fiy (x) is strictly nonzero these (i. j) coordinates. We also note that F5y is continuous, there is open neighborhood N containing where, for all ă E N, have F.y (ã) Fiy (x) for all relevant i.j. We can therefore expect that, despite possible numerical error in computing G, the computation of the sign sequence of the corresponding vertex stable under these perturba- tions, since by recording which bent hyperplanes were intersected via signs we have eliminated the unstable operation of determining which signs were O.
We finally discuss the question of algorithmic complexity.
Lemma 24. Let F T + be a randomly-initialized ReLU neural network satisfying the conditions in (Hanin & Rolnick 2019a)
If N Em= n, the number of hidden units of F, then the average number of linear equations and sign sequence evaluations required for the computation of S(F) is ((N2no11).
Proof. The first step in Lemma 22 involves solving (*)) equations, which is Onn")). Then in the the recursive step in Lemma 23 in each subsequent layer > 2, there are an average of ((n + +...
11-1)" m regions iterate through (Hanin Rolnick 2019a). In each region, there are fewer than (11 +n) new equations solve. This yields the following big-O upper bound for the average no computational complexity of this algorithm:
m
n1
(n)
11--1) nn + +2) < Ao
No
Since N n1 +.. am, and each of the n, 2 1, it must be the case that the depth N, so this expression
((V2n011)
This is polynomial in N and exponential in no-
Compare some possible naïve approaches to computing the face relations of C(F). First, sider the approach computing which regions are present and then computing their intersections. First, naïve search for all regions" activation patterns in 1M would require determining if there
22

---

solutions to 2 linear inequalities in N variables, which would then define highly redundant descriptions of polyhedral regions. This can be done more optimally than checking each set of inequalities (Serra et al. 2018 Zhang & Wu 2020). However, without having tracked sign informa- tion, following this search, to determine if two polyhedra share a face, and find the dimension that face, requires finding whether the union of sets of N linear inequalities is consistent, with the expectation that there will be cancellation of redundancies by the exact equality of some linear com- binations of these linear incqualities in order observe the existence of lower-dimensional faces. Numerical error in the expression of these linear inequalities can thus lead to catastrophic failure identifying shared lower-dimensional faces, especially the dimension of those faces. Alternative methods of tracking which vertices are present in a way which could hypothetically allow for track- ing pairwise intersection between cells, in contrast, currently track the full face poset Yang et al. 2020 2021), and are thus storage-intensive.
B
ADDITIONAL EXPERIMENTAL OBSERVATIONS
Here we report additional distributional information about the topology of decision boundaries of randomly initialized ReLU networks with different architectures. Table summarizes distributional information about the Betti numbers of the decision boundary, and Table 3 summarizes information about the connected components of the decision boundary. Figure g gives additional distributional information for selected architectures. While shallow architectures again have very constant dis- tribution of the number of unbounded components even across input dimension, the number of unbounded components seen initialization in deeper architectures is much greater, and the distri- butional variability with width is apparent.
Betti numbers of the compactified decision boundary dependent on architecture, across the range of widths studied (50 networks of each architecture). In Bng-1. deeper architectures exhibit greater variability and greater apparent change with width across the range of widths studied.
Table 2:
Shallow Architectures
Bg
Png-1
Average
SE
Average
SE
(2, 5, 1)
1.06
0.034
1.06
0.059
(2, 15, 1)
1.16
0.052
1.04
0.075
(3, 1) (3, 1,,15
1.02
0.019
L.04
0.048
1.04
0.027
1.04
0.040
(4,5,
1.00
0.000
0.98
0.020
(4, 4,15,1)
1.02
0.020
1.12
0.046
Deep Architectures
Bng
Average
SE
Average
SE
(2, 1,
1.16
0.05
1.14
0.13
15, 15,
1.14
0.05
1.00
0.10
5,
1.00
0.00
1.52
0.14
(3, 13, 13,1)
1.04
0.028
1.34
0.15
(4, 5,5,
1.00
0.00
0.82
0.07
1.04
0.03
1.88
0.30
23

---

Table 3: Average number of bounded and unbounded components of the decision boundary depen- dent on architecture.
Shallow Architectures
Unbounded
Bounded
Average
SE
Average
SE
(2 1)
1.00
0.070
0.06
0.034
[2, 15, 1)
0.88
0.073
0.16
0.052
(3,5, 1)
1.02
0.053
0.02
0.020
(3, 15
1.00
0.040
0.04
0.023
(4,5,
0.98
0.020
0.00
0.00
1,
1.10
0.042
0.02
0.020
Deep Architectures
Unbounded
Bounded
Average
SE
Average
SE
(2, 5,
0.98
0.140
0.16
0.052
(2, 15, 15, 1)
0.86
0.100
0.14
0.049
5,
1.52
0.142
0.00
0.000
(3, 10,1)
1.38
0.155
0.04
0.027
(,5,5,1)
0.82
0.0730
0.00
0.000
8, 1.84
0.301
0.04
0.040
C LICENSE INFORMATION
PyTorch Paszke al. 2019) is under Modified BSD license, permitting in other projects and requiring its licensing information repackaged when its source code is redistributed. We do not redistribute its source code in our work.
Sage The Sage Developers) 2018) is licensed under the GNU General Public License (GPL). It is free and distribute. We do not redistribute its source code in work, but it necessary run the decision boundary topology computations.
24

---

2-5-1
3-5-1
45-1
Count
2115-1
315-1
4-15-1
Caunt
Number of unbounded components
2-5-5-1
3-5---1
4-5--11
Count
2-15-15-1
3-13-13-1
4-8-8-1
Number unbounded components
Figure 8: Distribution of the total number of connected components of the decision boundary for selected architectures.
25


Reviews:
[{"review_id": "mpJHUH3x_A", "reviewer": "Reviewer_Pp96", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors deal with the problem of identifying the different regions of space as they are partitioned by the parameters of a ReLU neural network, specifically identifying what combinatorial properties govern the induced partition.\n\nThe authors provide a combinatorial description of the canonical polyhedral complex of ReLU nets and its dual. They rely on something called the \"sign sequence complex\" and use it to determine the facets relations and the locations of vertices of the complex.\n\nHaving established these theoretical insights, they proceed by implementing and cheking an algorithm to obtain the sign sequence complex. The algorithm appears to work for small values of input dimension, and to be polynomial in the #neurons. Furthermore, the algorithm is numerically well-behaved.\n\nThe theory developed also is used to understand some topological properties of ReLU networks and points to the fact that depth is more important than width. (see quick question below too)", "summary_of_the_review": "Overall, the paper looks at an interesting theoretical question regarding how the different linear regions of a ReLU network are positioned into space, how they intersect or not, what is their boundary. The main result is a characterization and an algorithm that finds the different linear regions. Then this is used to understand topological properties of small networks. I believe the algorithm is nice, and perhaps the one that is the natural algorithm to run in order to obtain the boundaries. (looping over intersections and how they are passed through the net).", "strength_and_weaknesses": "Strengths are:\n+ the paper builds upon the theory of fully-connected ReLU feedforward networks and yield interesting insights about the geometry of neural nets\n+ the theory is then used to understand different types of networks, e.g., shallow vs deep, and to identify the exact topology of the linear regions.\n+ the paper can serve as further evidence of the benefits of depth in neural nets\n\nWeaknesses/Unclear things to clarify/Questions:\n- in terms of theory, I am not convinced about the necessity of exponential dependence in the dimension. Is there an example or counterexample that shows the true dependence should behave like this? (maybe there is a simple example that I am missing out)\n- in terms of experiments, I would like to have seen a comparison of the algorithm with simpler algorithms like naive searching of the input space and how it is mapped, or random sampling and tweaking of a starting point moving along some curve or sth. I know these may be trivial baselines, but it's always nice to see \"failure\" cases too.\n-in terms of experiments, can the theory developed be used to learn something interesting about MNIST let's say? or even ImageNET? about the topological properties of the networkds used?\n- I am confused about the 4th bullet in the contributions part of the intro (page 2). The statement that at initialization depth seems to be more important than the #aparams of intermediate neurons, isn't is contradicting recent work of Hanin and Rolnick that is cited in the paper (end of section 4.3)? Can there be a clarification please? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "j1HjujMgPr", "reviewer": "Reviewer_6J8n", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper presents the mathematical theory and corresponding methods for computing a full characterization of all the linear regions of a neural network with ReLU activations. In other words, it provides the structure of the polyhedron associated with each of the linear regions defined by a rectifier network and its lower-dimensional faces, which I understand as a generalization of the face lattice that would describe a single polyhedron (i.e., one linear region). They further show that the union of the vertices across all such polyhedra along with a sign characterization of those vertices with respect to each neuron (-1, 0, +1) is sufficient to determine the facial structure of the same polyhedra. Whereas this can be combinatorially explosive, the authors argue that this can be used to evaluate the linear regions of a neural network with respect to the low-dimensional subspaces of the input.\n\nIn full disclosure, I have previously reviewed this paper when it was submitted to NeurIPS 2022. I do bid to review the same papers when I see potential in them, since I believe this would make the process easier for the authors than starting all over again. Consequently, the wording in my review is very similar to what I wrote before, but I did compare the two versions side by side to make sure my assessment remains the same.", "summary_of_the_review": "I anticipate other reviewers objecting to the usefulness of a computationally expensive characterization such as the one studied by the authors, but I do believe this is a necessary step if we want to understand what neural networks represent.\n\nWith that said, I was hoping for deeper changes that could potentially make this paper more accessible to the machine learning community at large, and I cannot say that the current submission is at the stage yet.", "strength_and_weaknesses": "On the one hand, the authors are boldly approaching a rather intractable problem, and one which I believe would help us understand what neural networks encode across all their linear regions. In terms of presentation, I liked how the theorems from the appendix were brought in at the point that they would be helpful to continue the discussion. Moreover, the authors included some missing references that overlapped with their contribution and corrected some issues that I spotted when I reviewed their work previously.\n\nOn the other hand, it is still my impression that this paper expects too much from the reader and cannot be read on its own. I understand that it is hard to do justice to this work in so few pages, but I believe that would have helped to informally explain the main ideas and how they relate before going very technical (even if that means sending more of the theory to the appendix). One interesting example of that done in practice is Boris & Hanin (2019b). I was really hoping that the authors would have altered their paper to be a little more like that.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "BH0xwqXWaJ", "reviewer": "Reviewer_3fLq", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper studies linear regions of a ReLU neural network, which naturally form a \"canonical polyhedral complex\". They introduce a dual complex, the so-called \"sign sequence complex\", which is also a generalization of activation patterns. They prove that the sign sequences of the vertices of the canonical complex is sufficient to determine the facet poset structure of the sign sequence complex. They develop and implement algorithms for computing sign sequences and the canonical polyhedral complex, which can be used to obtain topological information of the decision boundary.", "summary_of_the_review": "The paper describes a very interesting approach to study linear regions of ReLU networks. It is very nicely written, and even closer inspection revealed no mathematical errors in the proofs.\n\nHowever, the claims that advocate for the superiority of the approach in terms of numerical stability and algorithmic are unfounded. This does not mean that the claims are wrong, just that the paper lacks proof or evidence. Additionally, the main part of the paper restricts to decision boundaries of binary classification tasks without ever mentioning it explicitly in the introduction.", "strength_and_weaknesses": "Strengths\n-------------\n\nThe strengths of the paper is its clarity and its novel approach. They introduce a generalization of activation patterns, which is very elegant due to its simplicity and in the sense that they induce a polyhedral complex that is dual to the canonical polyhedral complex formed by the linear regions. The authors provide code for computing the objects they introduced, and clear instructions on how to use it.\n\nWeaknesses\n-----------------\n\nThe biggest weakness of the paper is that it does not clearly answer the following question: What is the advantage of working with the sign sequence approach and the sign complex S(F) over working with the canonical polyhedral complex C(F)?\nIn detail:\n\n   * There doesn't seem to be an algorithm for computing S(F) without computing C(F). Section 4.1 is titled \"Obtaining the sign sequence complex\", but the algorithm works by computing C(F).\n\n   * The point about the numerical stability is unclear. Section 4.3 states: \"As long as the error in computing solutions to linear equations is small compared to the size of the cells in the polyhedral complex, the proposed algorithm will find the correct sign sequence [...], and [...] the correct combinatorics of the polyhedral complex\". But under the same assumptions shouldn't an approximately computed C(F) also have the same combinatorial structure as the exact C(F)?\n\n   * The point about the algorithmic complexity is unclear. Section 4.3 states: \"the number of possible combinations [...] is also polynomial in the total number of hidden units\". But does that really mean that the algorithm is \"polynomial expected time in the number of hidden units\"? For each combination one still needs to compute the intersection points, and it is not clear whether the expected number of intersection points is polynomial in the number of hidden units?\n\nAdditionally, the paper talks about \"decision boundaries\", however it only considers networks with a single output dimension, i.e., decision boundaries of binary classification tasks. It would be good if the authors could comment how their work can be applied to decision boundaries of non-binary classification tasks. If the work is only restricted to decision boundaries of binary classification tasks, then this should be clearly stated.\n\nA few very minor comments:\n\n   * Section 3.2, first paragraph: double \"a\" in \"may serve as a a labeling scheme\"\n\n   * Section 3.2, first paragraph: missing \"the\" in \"encode all face relationships and [] topology of a network's canonical polyhedral complex\"\n\n   * Section 4.1, computing sign sequences: In Point 1., \"F_ij\" should be \"F_1j\"\n\n   * Appendix A.1, Definition 1: The definition for polyhedron is wrong, it is for open polyhedra and not closed polyhedra. H_i^+ needs to be the euclidean closure of a connected component of RR^n \\ H_i.\n\n   * Appendix A.1, Definition 5: Mention that \\pi_j denotes the projection onto the j-th coordinate\n\n   * Appendix A.2, Definition 11: Some of the indices are wrong:\n     - F^i maps from RR^{n_{i-1}} (by Definition 4)\n     - F_i maps to RR^{n_i} (by Definition 4)\n     - R^(i-1) lives in RR^{n_{i-2}} (by Definition 2)\n\n   * Appendix A.2, Definition 13: Mention that sgn(F_ij(C)) denotes the sign of the linear function restricted to C (and not the sign of the points in the image of C under F_ij)\n\n   * Appendix A.2, Lemma 18 onwards: sign sequences are denoted with a capital \"S\", and not a small \"s\" anymore.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject