Topological Expressivity of ReLU Neural Networks
We study the expressivity of ReLU neural networks in the setting of a binary
classification problem from a topological perspective. Recently, empirical
studies showed that neural networks operate by changing topology, transforming
a topologically complicated data set into a topologically simpler one as it
passes through the layers. This topological simplification has been measured by
Betti numbers, which are algebraic invariants of a topological space. We use
the same measure to establish lower and upper bounds on the topological
simplification a ReLU neural network can achieve with a given architecture. We
therefore contribute to a better understanding of the expressivity of ReLU
neural networks in the context of binary classification problems by shedding
light on their ability to capture the underlying topological structure of the
data. In particular the results show that deep ReLU neural networks are
exponentially more powerful than shallow ones in terms of topological
simplification. This provides a mathematically rigorous explanation why deeper
networks are better equipped to handle complex and topologically rich data
sets.
Ekin Ergen, Moritz Grillo
# Topological Expressivity of ReLU Neural Networks

###### Abstract

We study the expressivity of ReLU neural networks in the setting of a binary classification problem from a topological perspective. Recently, empirical studies showed that neural networks operate by changing topology, transforming a topologically complicated data set into a topologically simpler one as it passes through the layers. This topological simplification has been measured by Betti numbers, which are algebraic invariants of a topological space. We use the same measure to establish lower and upper bounds on the topological simplification a ReLU neural network can achieve with a given architecture. We therefore contribute to a better understanding of the expressivity of ReLU neural networks in the context of binary classification problems by shedding light on their ability to capture the underlying topological structure of the data. In particular the results show that deep ReLU neural networks are exponentially more powerful than shallow ones in terms of topological simplification. This provides a mathematically rigorous explanation why deeper networks are better equipped to handle complex and topologically rich datasets.

## 1 Introduction

Neural networks are at the core of many AI applications. A crucial task when working with neural networks is selecting the appropriate architecture to effectively tackle a given problem. Therefore, it is of fundamental interest to understand the range of problems that can be solved by neural networks with a given architecture, i.e., its _expressivity_.

In recent years, many theoretical findings have shed light on the expressivity of neural networks. Universal approximation theorems (Cybenko, 1989)(Hornik, 1991) state that one hidden layer is already sufficient to approximate any continuous function with arbitrary accuracy. On the other hand, it is known that deep networks can represent more complex functions than their shallow counterparts, see e.g. (Telgarsky, 2016; Eldan and Shamir, 2016; Arora et al., 2018).

The measure of expressivity of a neural network should always be related to the problem it has to solve. A common scenario in which neural networks are employed is the binary classification problem, where the network serves as a classifier for a binary labeled dataset. Since topological data analysis has revealed that data often has nontrivial topology, it is important to consider the topological structure of the data when dealing with a binary classification problem. Naitzat et al. (2020) show through empirical methods that neural networks operate topologically, transforming a topologically complicated dataset into a topologically simple one as it passes through the layers. Given a binary labeled dataset, they assume that the positively labeled and the negatively labeled points are sampled from topological spaces \(M_{a}\) and \(M_{b}\) respectively that
are entangled with each other in a nontrivial way. Their experiments show that a well-trained neural network gradually disentangles the topological spaces until they are linearly separable in the end, i.e, the space \(M_{b}\) is mapped to the positive real line and \(M_{a}\) to the negative real line. From a theoretical point of view, it is of interest to determine the extent of "topological change" that can be achieved by neural networks of a particular architecture. The topological expressivity of a neural network can therefore be measured by the complexity of the most complex topological spaces it can separate and is directly related to the complexity of the binary classification problem.

In this paper we investigate the topological expressivity of ReLU neural networks, which are one of the most commonly used types of neural networks (Glorot et al., 2011; Goodfellow et al., 2016). A \((L+1)\)_-layer neural network (NN)_ is defined by \(L+1\) affine transformations \(T_{\ell}\colon\mathbb{R}^{n_{\ell-1}}\to\mathbb{R}^{n_{\ell}}\), \(x\mapsto A_{\ell}x+b_{\ell}\) for \(A_{\ell}\in\mathbb{R}^{n_{\ell-1}\times n_{\ell}},b_{\ell}\in\mathbb{R}^{n_{ \ell}}\) and \(\ell=1,\ldots,L+1\). The tuple \((n_{0},n_{1},\ldots,n_{L},n_{L+1})\) is called the _architecture_, \(L+1\) the _depth_, \(n_{\ell}\) the _width of the \(\ell\)-layer_, \(\max\{n_{1},\ldots,n_{L}\}\) the _width_ of the NN and \(\sum_{\ell=1}^{L}n_{\ell}\) the _size_ of the NN. The entries of \(A_{\ell}\) and \(b_{\ell}\) for \(\ell=1,...,L+1\) are called _weights_ of the NN and the vector space of all possible weights is called the _parameter space_ of an architecture. A ReLU neural network computes the function

\[F=T_{L+1}\circ\sigma_{n_{L}}\circ T_{L}\circ\cdots\circ\sigma_{n_{1}}\circ T_ {1},\]

where \(\sigma_{n}\colon\mathbb{R}^{n}\to\mathbb{R}^{n}\) is the _ReLU function_ given by \(\sigma_{n}(x)=(\max(0,x_{1}),\ldots,\max(0,x_{n}))\).

Note that the function \(F\) is piecewise linear and continuous. In fact, it is known that any continuous piecewise linear function \(F\) can be computed by a ReLU neural network (Arora et al., 2018). However, for a fixed architecture \(A\), the class \(\mathcal{F}_{A}\) of piecewise linear functions that is representable by this architecture is not known (Hertrich et al., 2021; Haase et al., 2023). Conveniently, in the setting of a binary classification problem we are merely interested in the _decision regions_, i.e., \(F^{-1}((-\infty,0])\) and \(F^{-1}((0,\infty))\) rather than the continuous piecewise linear function \(F\) itself.

A common choice to measure the complexity of a topological space \(X\) is the use of algebraic invariants. Homology groups are the essential algebraic structures with which topological data analysis analyzes data (Dey and Wang, 2022) and hence Betti numbers as the ranks of these groups are the obvious measure of topological expressivity. Intuitively, the \(k\)-th Betti number \(\beta_{k}(X)\) corresponds to the number of \((k+1)\)-dimensional holes in the space \(X\) for \(k>0\) and \(\beta_{0}(X)\) corresponds to the number of path-connected components of \(X\). Thus, one can argue that when a space (the support of one class of the data) has many connected components and higher dimensional holes, it is more difficult to separate this space from the rest of the ambient space, e.g., mapping it to the negative line. In Appendix 5.1.2 we present a brief introduction to homology groups. For an in-depth discussion of the aforementioned concepts, we refer to (Hatcher, 2002).

In order to properly separate \(M_{a}\) and \(M_{b}\), the sublevel set \(F^{-1}((-\infty,0])\) of the function \(F\) computed by the neural network should have the same topological complexity as \(M_{a}\). Bianchini and Scarselli (2014) measured the topological complexity of the decision region \(F^{-1}((-\infty,0])\) with the sum of all its Betti numbers. This notion of topological expressivity does not differentiate between connected components and higher dimensional holes. On the other hand, if an architecture is not capable of expressing the Betti numbers of different dimensions of the underlying topological space of the dataset, then for every \(F\in\mathcal{F}_{A}\) there is a set of data points \(U\) such that \(F\) misclassifies every \(x\in U\)(Guss and Salakhutdinov, 2018). Therefore it is of fundamental interest to understand each Betti number of the decision regions and hence we propose the following definition:

**Definition 1**.: _The topological expressivity of a ReLU neural network \(F\colon\mathbb{R}^{d}\to\mathbb{R}\) is defined as the vector \(\beta(F)=(\beta_{k}(F))_{k=0,\ldots,d-1}=(\beta_{k}(F^{-1}((-\infty,0]))_{k=0, \ldots,d-1}\)._
### Main results

Our main contribution consists of lower and upper bounds on the topological expressivity for ReLU NNs with architectures. These bounds demonstrate that the growth of Betti numbers in neural networks depends on their depth. With an unbounded depth, Betti numbers in every dimension can exhibit exponential growth as the network size increases. However, in the case of a shallow neural network, where the depth remains constant, the Betti numbers of the sublevel set are polynomially bounded in size. This implies that increasing the width of a network while keeping the depth constant prevents exponential growth in the Betti numbers. Consequently, if a dataset possesses exponentially high Betti numbers (parameterized by some parameter \(p\)), accurate modeling of the dataset requires a deep neural network when the size of the neural network is constrained to be polynomial in parameter \(p\) since the topological expressivity serves, as discussed above, as a bottleneck measure for effective data representation.

In Theorem 36, the lower bounds for the topological expressivity are given by an explicit formula, from which we can derive the following asymptotic lower bounds:

**Corollary 2**.: _Let \(A=(d,n_{1},\ldots,n_{L},1)\) with \(n_{L}\geq 4d\) and \(M=2\cdot\prod_{\ell=1}^{L-1}\left\lfloor\frac{n_{\ell}}{2d}\right\rfloor\), then there is a ReLU NN \(F\colon\mathbb{R}^{d}\mapsto\mathbb{R}\) with architecture \(A\) such that_

1. \(\beta_{0}(F)\in\Omega(M^{d}\cdot n_{L})\)__
2. \(\beta_{k}(F)\in\Omega(M^{k}\cdot n_{L})\) _for_ \(0<k<d\)_._

_In particular, given \(\textbf{v}=(v_{1},\ldots,v_{d})\in\mathbb{N}^{d-1}\), there is a ReLU NN \(F\) of size \(O\left(\log\left(\sum_{k=1}^{d-1}v_{k}\right)\right)\) such that \(\beta_{k}(F)\geq v_{k+1}\) for all \(k\in\{0,\ldots,d-1\}\)._

Corollary 2 provides a proof for a conjecture on lower bounds for the zeroth Betti number of the decision region given in (Guss and Salakhutdinov, 2018); in fact, it generalizes the statement to arbitrary dimensions. Furthermore, we observe that \(L=2\) hidden layers are already sufficient to increase the topological expressivity as much as we want at the expense of an increased width due to the above lower bound.

**Corollary 3**.: _Given \(v\in\mathbb{N}^{d}\), there exists an NN \(F\colon\mathbb{R}^{d}\to\mathbb{R}\) of depth 2 such that \(\beta_{k}(F)\geq v_{k+1}\) for all \(k\in\{0,\ldots,d-1\}\)._

We obtain the lower bound by making choices for the weights of the NN, nevertheless, we show that our construction is robust with respect to small perturbations. In fact, in Proposition 12 we prove that we actually have an open set in the parameter space such that the respective functions all have the same topological expressivity.

Using an upper bound on the number of linear regions (Serra et al., 2017), we obtain an explicit formula for an upper bound on \(\beta_{k}(F)\) for an arbitrary architecture in Proposition 14. This gives rise to the following asymptotic upper bounds:

**Corollary 4**.: _Let \(F\colon\mathbb{R}^{d}\to\mathbb{R}\) be a neural network of architecture \((d,n_{1},\ldots,n_{L},1)\). Then it holds that \(\beta_{k}(F)\in O\left(\left(\prod_{i=1}^{L}n_{i}\right)^{d^{2}}\right)\) for \(k\in[d-2]\) and \(\beta_{0},\beta_{d-1}\in O\left(\left(\prod_{i=1}^{L}n_{i}\right)^{d}\right)\)._

By combining Corollary 2 and Corollary 4, we can conclude that there is an exponential gap in the topological expressivity between shallow and deep neural networks. This aligns with other popular measures of expressivity, such as the number of linear regions, where similar exponential gaps are known (Serra et al., 2017; Montufar et al., 2014; Montufar, 2017).
### Related Work

#### 1.2.1 Topology and Neural Networks

Recently, there is a vast stream of research studying neural networks by means of topology using empirical methods (Petri and Leitao, 2020; Guss and Salakhutdinov, 2018; Naitzat et al., 2020; Li et al., 2020) as well as from a theoretical perspective (Basri and Jacobs, 2017; Melodia and Lenz, 2020; Grigsby and Lindsey, 2022; Bianchini and Scarselli, 2014; Grigsby et al., 2022; Hajji and Istvan, 2020). Bianchini and Scarselli (2014) were the first that used Betti numbers as a complexity measure for decision regions of neural networks. Their work studies NNs with sigmoidal activation functions and shows that there is an exponential gap with respect to the sum of Betti numbers between deep neural networks and neural networks with one hidden layer. However, there are no insights about distinct Betti numbers. In Guss and Salakhutdinov (2018), the decision regions of ReLU neural networks are studied with empirical methods and an exponential gap for the zeroth Betti number is conjectured. Our results prove the conjecture and extend the results of Bianchini and Scarselli (2014) for the ReLU case (see Section 3 and Appendix). Furthermore topological characteristics such as connectivity or boundedness of the decision regions are also investigated in (Fawzi et al., 2018; Grigsby and Lindsey, 2022; Grigsby et al., 2022; Nguyen et al., 2018).

#### 1.2.2 Expressivity of (ReLU) neural networks

In addition to the universal approximation theorems (Cybenko, 1989; Hornik, 1991), there is a significant amount of research on the expressivity of neural networks, e.g., indicating that deep neural networks can be exponentially smaller in size than shallow ones. For ReLU neural networks, the number of linear regions is often used as a measure of complexity for the continuous piecewise linear (CPWL) function computed by the network. It is well established that deep ReLU neural networks can compute CPWL functions with exponentially more linear regions than shallow ones, based on various results such as lower and upper bounds on the number of linear regions for a given architecture (Montufar, 2017; Serra et al., 2017; Montufar et al., 2014; Arora et al., 2018). We partially use techniques from their works to establish our bounds on topological expressivity, which offers the advantage of being directly related to the complexity of binary classification problems.

### Notation and Definitions

A function \(F\colon\mathbb{R}^{d}\to\mathbb{R}^{d}\) is continuous piecewise linear (CPWL) if there is a polyhedral complex covering \(\mathbb{R}^{d}\), such that \(F\) is affine linear over each polyhedron of this complex. A linear region of \(f\) is a maximal connected convex subspace \(R\) such that \(f\) is affine linear on \(R\), i.e., a full-dimensional polyhedron of the complex.1 For a survey on polyhedral theory in deep learning see Huchette et al. (2023), and for a general introduction to polyhedra we refer to Schrijver (1986).

Footnote 1: In the literature there exists also a slightly different definition of a linear region leaving out the necessity of the region being convex, but the bounds we use are all applicable to this definition of a linear region.

We denote by \([n]\) the set \(\{1,\ldots,n\}\) and by \([n]_{0}\) the set \(\{0,\ldots,n\}\). We denote by \(\pi_{j}\colon\mathbb{R}^{d}\to\mathbb{R}\) the projection onto the \(j\)-th component of \(\mathbb{R}^{d}\) and by \(p_{j}\colon\mathbb{R}^{d}\to\mathbb{R}^{j}\) the projection onto the first \(j\) components.

A crucial part of our construction is decomposing a unit cube into a varying number of small cubes. Thereby, given \(\mathbf{m}=(m_{1},\ldots,m_{L})\in\mathbb{N}^{L}\) and \(M=\left(\prod_{\ell=1}^{L}m_{\ell}\right)\), the set \(W_{i_{1},\ldots,i_{d}}^{(L,\mathbf{m},d)}\) is defined as the cube of volume \(\frac{1}{M^{d}}\) with "upper right point" \(\frac{1}{M}\cdot(i_{1},\ldots,i_{d})\), i.e., the cube
\(\prod_{k=1}^{d}[\frac{(i_{k}-1)}{M},\frac{i_{k}}{M}]\subset[0,1]^{d}\). The indices \((L,\mathbf{m},d)\) are omitted whenever they are clear from the context.

We denote by \(D^{k}=\{x\in\mathbb{R}^{k}\colon\|x\|<1\}\) the \(k\)-dimensional standard (open) disk and by \(S^{k}=\{x\in\mathbb{R}^{k+1}\colon\|x\|=1\}\) the \(k\)-dimensional standard sphere. We consider these sets as "independent" topological spaces. Therefore, it is justified to abstain from picking a specific norm, since all norms on \(\mathbb{R}^{k}\) are equivalent.

For \(k,m\in\mathbb{N}\) with \(m\leq k\), the _(\(j\)-dimensional open) \(k\)-annulus_ is the product space \(S^{k}\times D^{j-k}\). Note that since \(S^{k}\) has one connected component and a \((k+1)\)-dimensional hole, it holds that \(\beta_{0}(S^{k})=\beta_{k}(S^{k})=1\) and the remaining Betti numbers equal zero. The \(j\)-dimensional \(k\)-annulus is an \(j\)-dimensional manifold that can be thought as a thickened \(k\)-sphere and hence its Betti numbers coincide with the ones from the \(k\)-sphere. In Appendix 5.1.2 the reader can find a more formal treatment of the latter fact.

In contrast to \(D^{k}\) and \(S^{k}\), which are only seen as spaces equipped with a topology, we also consider neighborhoods around certain points \(x\in\mathbb{R}^{d}\) as subsets of \(\mathbb{R}^{d}\). To make a clear distinction, we define the space \(B^{d}_{r}(x)\) as the _\(d\)-dimensional open \(r\)-ball around \(x\) with respect to the \(1\)-norm_, i.e., the space \(\{y\in\mathbb{R}^{d}\colon\|x-y\|_{1}<r\}\). Note that for \(r<r^{\prime}\), the set \(B^{k}_{r}(x)\setminus\overline{B^{k}_{r^{\prime}}(x)}\) is homeomorphic to a \(k\)-dimensional \((k-1)\)-annulus and we will refer to them as \((k-1)\)-annuli as well. These annuli will be the building blocks of our construction for the lower bound.

The rest of the paper is devoted to proving the lower and upper bounds. Most of the statements come with an explanation or an illustration. In addition, formal proofs for these statements are also provided in the appendix.

## 2 Lower Bound

In this section, our aim is to construct a neural network \(F\colon\mathbb{R}^{d}\to\mathbb{R}\) of depth \(L+2\) such that \(\beta_{k}(F)\) grows exponentially in the size of the neural network for all \(k\in[d-1]_{0}\).

We propose a construction that is restricted to architectures where the widths \(n_{1},\ldots,n_{L+1}\) of all hidden layers but the last one are divisible by \(2d\). This construction, however, is generalized for any architecture where the dimension of all hidden layers is at least \(2d\) by inserting at most \(2d\) auxiliary neurons at each layer at which a zero map is computed. Correspondingly, one obtains a lower bound by rounding down the width \(n_{\ell}\) at each layer to the largest possible multiple of \(2d\). In particular, a reduction to the case in Theorem 35 does not have an effect on the asymptotic size of the NN.

The key idea is to construct \(F=f\circ h\) as a consecutive execution of two neural networks \(f\) and \(h\), where the map \(h\colon\mathbb{R}^{d}\to\mathbb{R}^{d}\) is an ReLU NN with \(L\) hidden layers that identifies exponentially many regions with each other. More precisely, \(h\) cuts the unit cube of \(\mathbb{R}^{d}\) into exponentially many small cubes \(W_{i_{1},\ldots,i_{d}}\in[0,1]^{d}\) and maps each of these cubes to the whole unit cube by scaling and mirroring. The one hidden layer ReLU NN \(f\) then cuts the unit cube into pieces so that \(f\) on the pieces alternatingly takes exclusively positive respectively negative values. Since \(h\) maps all \(W_{i_{1},\ldots,i_{d}}\) to \([0,1]^{d}\) by scaling and mirroring, every \(W_{i_{1},\ldots,i_{d}}\) is cut into positive-valued and negative-valued regions by the composition \(f\circ h\) in the same way as \([0,1]^{d}\) is mapped by \(f\), up to mirroring. The cutting of the unit cube and the mirroring of the small cubes in the map to \([0,1]^{d}\) are chosen in such a way that the subspaces on which \(F\) takes negative values form \(k\)-annuli for every \(k\in[d-1]\). Since \(h\) cuts the unit cube into exponentially many small cubes, we obtain exponentially many \(k\)-annuli for every \(k\in[d-1]\) in \(F^{-1}((-\infty,0))\). We will then argue that \(F^{-1}((-\infty,0))\) is homotopy equivalent to \(F^{-1}((-\infty,0])\).

The idea of constructing a ReLU neural network that folds the input space goes back to Montufar et al. (2014), where the construction was used to show that a deep neural network with ReLU activation function can have exponentially many linear regions. Using their techniques,
we first build a \(1\)-hidden layer NN \(h^{(1,m,d)}\colon\mathbb{R}^{d}\to\mathbb{R}^{d}\) for \(m\in\mathbb{N}\) even that folds the input space, mapping \(m^{d}\) many small cubes \(W^{(1,m,d)}_{i_{1},\ldots,i_{d}}\subset[0,1]^{d}\) by scaling and mirroring to \([0,1]^{d}\). More precisely, the NN \(h^{(1,m,d)}\) has \(m\cdot d\) many neurons in the single hidden layer, who are partitioned into \(m\) groups. The weights are chosen such that the output of the neurons in one group depends only on one input variable and divides the interval \([0,1]\) into \(m\) subintervals of equal length, each of which is then mapped to the unit interval \([0,1]\) by the output neuron. Figure 2 illustrates this construction. In Appendix 5.2.1 or in Montufar et al. (2014), the reader can find an explicit construction of \(h^{(1,m,d)}\).

The map \(h^{(1,m,d)}\) identifies only \(O(m^{d})\) many cubes with each other. To subdivide the input space into exponentially many cubes and map them to the unit cube, we need a deep neural network. For this purpose, we utilize a vector \(\mathbf{m}\) of folding factors instead of a single number \(m\). Let \(\mathbf{m}=(m_{1},\ldots,m_{L})\in\mathbb{N}^{L}\) with \(m_{\ell}\) even for all \(\ell\in[L]\) and define the neural network \(h^{(L,\mathbf{m},d)}\) with \(L\) hidden layers as \(h^{(L,\mathbf{m},d)}=h^{(1,m_{L},d)}\circ\cdots\circ h^{(1,m_{1},d)}\). Since each of the \(m_{1}^{d}\) cubes that results from the subdivision by the first layer is mapped back to \([0,1]^{d}\), each cube is subdivided again into \(m_{2}^{d}\) cubes by the subsequent layer. Thus, after \(L\) such layers, we obtain a subdivision of the input space into \(\left(\prod_{\ell=1}^{L}m_{\ell}\right)^{d}\) cubes.

In the following, we define variables that are fixed but arbitrary: \(L\in\mathbb{N}\), \(\mathbf{m}=(m_{1},\ldots,m_{L})\in\mathbb{N}^{L}\) and \(M=\left(\prod_{\ell=1}^{L}m_{\ell}\right)\) with \(m_{\ell}>1\) even for all \(\ell\in[L]\). The following lemma states that \(h^{(L,\mathbf{m},d)}\) actually enjoys the aforementioned properties.

**Lemma 5**.: _(cf. Montufar et al. (2014)) Let \(d\in\mathbb{N}\), then:_

1. \(h^{(L,\mathbf{m},d)}(W^{(L,\mathbf{m},d)}_{(i_{1},\ldots,i_{d})})=[0,1]^{d}\)__
2. \(\pi_{j}\circ h^{(L,\mathbf{m},d)}_{|W^{(L,\mathbf{m},d)}_{(i_{1},\ldots,i_{d} )}}(x_{1},\ldots,x_{d})=\left\{\begin{array}{ll}M\cdot x_{j}-(i_{j}-1)&i_{j }\text{ odd}\\ -M\cdot x_{j}+i_{j}&i_{j}\text{ even}\end{array}\right.\)__

_for all \((i_{1},\ldots,i_{d})\in[M]^{d}\)._

We now define cutting points as the points that are mapped to the point \((1,1,1,\ldots.,1,0)\) by the map \(h^{(L,\mathbf{m},d)}\) since they will play a central role in counting the annuli in the sublevel set of \(F\).

**Definition 6**.: _We call a point \(x\in[0,1]^{d}\) a cutting point if it has coordinates of the form \(x_{i}=\frac{x_{i}^{\prime}}{M}\) for all \(i\in\{1,\ldots,d\}\), where the \(x_{i}^{\prime}\) are odd integers for \(1\leq i\leq d-1\) and \(x_{d}^{\prime}\) is an even integer._

Figure 1: The graph of the function \(\pi_{j}\circ h^{(1,2,d)}\) that folds the unit interval, i.e., mapping the interval \([0,0.5]\) and \([0.5,1]\) to the unit interval. This function is realised by a hidden layer with \(2\) hidden neurons.
Next, for \(w\geq 2\), we build a 1-hidden layer neural network \(\hat{g}^{(w,d)}\colon\mathbb{R}^{d}\to\mathbb{R}\) that cuts the d-dimensional unit cube into \(w\) pieces such that \(\hat{g}^{(w,d)}\) maps the pieces alternatingly to \(\mathbb{R}_{\geq 0}\) and \(\mathbb{R}_{\leq 0}\), respectively. We omit the indices \(w\) and \(d\) whenever they are clear from the context.

In order to build the neural network, we fix \(w\) and \(d\) and define the maps \(\hat{g}_{q}\colon\mathbb{R}^{d}\to\mathbb{R}\), \(q=0,\ldots,w+1\) by

\[\hat{g}_{q}(x)=\left\{\begin{array}{ll}\max\{0,\mathbf{1}^{T}x\}&q=0\\ \max\{0,\mathbf{1}^{T}x-\frac{1}{4}\}&q=w+1\\ \max\{0,2(\mathbf{1}^{T}x-(2q-1)/8w)\}&\text{else}\end{array}\right.\]

Later in this section, we will iteratively construct \(k\)-annuli in the sublevel set of \(F\) for all \(k\in[d-1]\). In order to ensure that these annuli are disjoint, it is convenient to place them around the cutting points. To achieve this, we mirror the map \(\hat{g}\) before precomposing it with \(h\). The mirroring transformation that maps the origin to the point \((1,\ldots,1,0)\) is an affine map \(t:[0,1]^{d}\to[0,1]^{d}\) defined by \(t(x_{1},x_{2},\ldots,x_{d})=(1-x_{1},1-x_{2},\ldots,1-x_{d-1},x_{d})\). We define the neural network \(g=\hat{g}\circ t\) as the consecutive execution of \(\hat{g}\) and \(t\).

**Lemma 7**.: _Let \(d,w\in\mathbb{N}\) with \(w\) odd and_

\[R_{q}=\{x\in[0,1]^{d}:\frac{q}{4w}<\|(1,1,\ldots,1,0)-x\|_{1}<\frac{q+1}{4w}\}.\]

_Then there exists a 1-hidden layer neural network \(g^{(w,d)}\colon\mathbb{R}^{d}\to\mathbb{R}\) of width \(w+2\) such that \(g^{(w,d)}(R_{q})\subseteq(-\infty,0)\) for all odd \(\in[w-1]_{0},g^{(w,d)}(R_{q})\subseteq(0,\infty)\) for all even \(q\in[w-1]_{0}\) and \(g^{(w,d)}(x)=0\) for all \(x\in[0,1]^{d}\) with \(\|(1,1,\ldots,1,0)-x\|_{1}\geq\frac{1}{4}\)._

Lemma 31 in the appendix characterizes the regions around cutting points that admit positive respectively negative values under the map \(g^{(w,d)}\circ h^{(L,\mathbf{m},d)}\). We focus on the regions that admit negative values, i.e., the space \(Y_{d,w}\coloneqq(g^{(w,d)}\circ h^{(L,\mathbf{m},d)})^{-1}((-\infty,0))\) and observe that we obtain \(d\)-dimensional \((d-1)\)-annuli around each cutting point.

Combining Lemma 31 and further observations about the number of cutting points (cf. Observation 32 in the appendix), we can finally describe \(Y_{d,w}\) as a topological space.
**Proposition 8**.: _The space \(Y_{d,w}\) is homeomorphic to the disjoint union of \(p_{d}=\frac{M^{(d-1)}}{2^{d-1}}\cdot\left(\frac{M}{2}-1\right)\cdot\left\lceil \frac{w}{2}\right\rceil\) many \((d-1)\)-annuli and \(p^{\prime}_{d}=\frac{M^{(d-1)}}{2^{d-2}}\cdot\left\lceil\frac{w}{2}\right\rceil\) many disks, that is,_

\[Y_{d,w}\cong\coprod_{k=1}^{p_{d}}(S^{d-1}\times[0,1])\sqcup\coprod_{k=1}^{p^{ \prime}_{d}}D^{d}.\]

In order to obtain exponentially many \(k\)-annuli for all \(k\in[d-1]\), we follow a recursive approach: At each step, we start with a \(k\)-dimensional space that has exponentially many \(j\)-annuli for all \(j\in[k-1]\). We then cross this space with the interval \([0,1]\), transforming the \(k\)-dimensional \(j\)-annuli into \((k+1)\)-dimensional \(j\)-annuli. Finally, we "carve" \((k\!+\!1)\)-dimensional \(k\)-annuli in this newly formed product space. To allow us flexibility with respect to the numbers of annuli carved in different dimensions, we fix an arbitrary vector \(\mathbf{w}=(w_{1},\ldots,w_{d-1})\in\mathbb{N}^{d-1}\) such that \(\sum_{i=1}^{d-1}(w_{i}+2)=n_{L+1}\). We iteratively define the \(1\)-hidden layer neural network \(f^{(w_{1},\ldots,w_{k-1})}\colon\mathbb{R}^{k}\to\mathbb{R}\) of width \(n_{L+1}\) by \(f^{(w_{1})}=g^{(w_{1},2)}\) and

\[f^{(w_{1},\ldots,w_{k-1})}=f^{(w_{1},\ldots,w_{k-2})}\circ p_{k-1}+g^{(w_{k-1},k)}\]

for \(k\leq d\). Roughly speaking, the following lemma states that the carving map does not interfere with the other maps, i.e., there is enough space in the unit cubes to place the \(k\)-annuli after having placed all \(k^{\prime}\)-annuli (\(k^{\prime}<k\)) in the same, inductive manner.

**Lemma 9**.: _For \(k\leq d\) and \(\mathbf{w}=(w_{1},\ldots,w_{d-1})\in\mathbb{N}^{d-1}\) it holds that_

1. \(f^{(w_{1},\ldots,w_{k-2})}\circ p_{k-1}(x)\neq 0\implies g^{(w_{k-1},k)}(x)=0\) _and_
2. \(g^{(w_{k-1},k)}(x)\neq 0\implies f^{(w_{1},\ldots,w_{k-2})}\circ p_{k-1}(x)=0\)__

_for all \(x\in[0,1]^{k}\)._

Using Lemma 9 and the fact that the folding maps \(h^{(L,\mathbf{m},k)}\) are compatible with projections (cf. Lemma 33 in Appendix), we can make sure that we can construct the cuts iteratively so that we obtain \(k\)-annuli for every \(k\in[d-1]\), which is stated in the following lemma.
**Lemma 10**.: _For \(2\leq k\leq d\), the space \(X_{k}\coloneqq(f^{(w_{1},\ldots,w_{k-1})}\circ h^{(L,\mathbf{m},k)})^{-1}((- \infty,0))\) satisfies_

\[X_{k}=(X_{k-1}\times[0,1])\sqcup Y_{k,w_{k-1}}\]

_with \(X_{1}\coloneqq\emptyset\)._

Lemma 10, Proposition 8 and the disjoint union axiom (Proposition 23 in Appendix 5.1.2) allow us to compute the Betti numbers of the decision region of \(F\coloneqq f^{(w_{1},\ldots,w_{d-1})}\circ h^{(L,\mathbf{m},d)}\) as stated in Theorem 35 in the appendix. One can easily generalize this statement by rounding down the widths \(n_{1},\ldots,n_{L}\) to the nearest even multiple of \(d\):

**Theorem 11**.: _Given an architecture \(A=(d,n_{1},\ldots,n_{L},1)\) with \(n_{\ell}\geq 2d\) for all \(\ell\in[L]\) and numbers \(w_{1},\ldots,w_{d-1}\in\mathbb{N}\) such that \(\sum_{k=1}^{d-1}(w_{k}+2)=n_{L}\), there is a neural network \(F\in\mathcal{F}_{A}\) such that_

1. \(\beta_{0}(F^{-1}((-\infty,0)))=\sum_{k=2}^{d}\frac{M^{(k-1)}}{2^{k-1}}\cdot \left(\frac{M}{2}+1\right)\cdot\left\lceil\frac{w_{k}}{2}\right\rceil\)__
2. \(\beta_{k}(F^{-1}((-\infty,0)))=\frac{M^{(k-1)}}{2^{k-1}}\cdot\left(\frac{M}{2}- 1\right)\cdot\left\lceil\frac{w_{k-1}}{2}\right\rceil\) _for_ \(0<k<d\)_,_

_where \(M=\prod_{\ell=1}^{L-1}2\cdot\lfloor\frac{n_{\ell}}{2d}\rfloor\)._

In Appendix 5.2.7 we modify the construction slightly by adding a small constant \(b\) to the output layer, such that we obtain in Theorem 36 the same lower bounds for \(\beta_{k}(F)=\beta_{k}(F^{-1}((-\infty,0])\). The special case \(\left\lfloor\frac{w_{1}}{2}\right\rfloor=\ldots=\left\lfloor\frac{w_{d}}{2}\right\rfloor\) then corresponds precisely to Corollary 2.

In order to obtain the lower bound we choose the weights explicitly, but the construction is robust to small perturbations. Basically this relies on the fact that since we have finitely many linear regions and no hyperplanes of non-linearity introduced at different applications of the ReLU function that coincide, one can perturb the weights slightly, such that the combinatorial structure of the polyhedral complex is preserved. From this we easily conclude the maintenance of the existence of all the annuli. In fact, if we denote by \(\Phi\colon\mathbb{R}^{D}\to C(\mathbb{R}^{d})\) the map that assigns a vector of weights to the function computed by the ReLU neural network with this weights, in Section 5.3 we prove the following:

**Proposition 12**.: _There is an open set \(U\subseteq\mathbb{R}^{D}\) in the parameter space of the architecture \(A=(d,n_{1},\ldots,n_{L},1)\) such that \(\Phi(u)\) restricted to the unit cube has at least the same topological expressivity as \(F\) in Theorem 36 for all \(u\in U.\)_

As mentioned previously, the sum of Betti numbers, the notion of topological expressivity used in Bianchini and Scarselli (2014), does not provide us with an understanding of holes of different dimensions. On the other hand, our bounds are clearly an extension of this result. In addition, the dimension-wise lower bound allows further implications, one of them being a lower bound on the _Euler characteristic_, which is the alternating sum \(\chi(X)=\sum_{k=1}^{d}\beta_{k}(X)\) of the Betti numbers.

**Corollary 13**.: _Let \(A\) be the architecture as in Theorem 36, then there is a ReLU NN \(F\colon\mathbb{R}^{d}\mapsto\mathbb{R}\) with architecture \(A\) such that \(\chi(F^{-1}((-\infty,0]))\in\Omega\left(M^{d}\cdot\sum\limits_{i=1}^{d-1}w_{i}\right)\), where \(\chi(F^{-1}((-\infty,0]))\) denotes the Euler characteristic of the space \(F^{-1}((-\infty,0])\)._
Upper Bound

In this section we derive an upper bound for \(\beta_{k}(F)\) for a ReLU neural network \(F\colon\mathbb{R}^{d}\to\mathbb{R}\) for all \(k\in[d-1]\), showing that they are polynomially bounded in the width using an upper bound on the linear regions of \(F\). A linear region \(R\) of \(F\) contains at most one maximal convex polyhedral subspace where \(F\) takes on exclusively non-negative function values. Intuitively, every such polyhedral subspace can be in the interior of at most one \(d\)-dimensional hole of the sublevel set \(F^{-1}((-\infty,0])\) and thus the number of linear regions is an upper bound for \(\beta_{d-1}(F)\). In the following proposition we will formalize this intuition and generalize it to \(\beta_{k}(F)\) for all \(k\in[d-1]_{0}\).

**Proposition 14**.: _Let \(F\colon\mathbb{R}^{d}\to\mathbb{R}\) be a neural network of architecture \((d,n_{1},\ldots,n_{L},1)\). Then it holds that \(\beta_{0}(F)\leq\sum_{(j_{1},\ldots,j_{L})\in J}\quad\prod_{\ell=1}^{L}\binom {n_{\ell}}{j_{\ell}}\) and for all \(k\in[d-1]\) that_

\[\beta_{k}(F)\leq\binom{\sum_{(j_{1},\ldots,j_{L})\in J}\quad\prod_{\ell=1}^{L }\binom{n_{\ell}}{j_{\ell}}}{d-k-s},\]

_where \(J=\big{\{}(j_{1},\ldots,j_{L})\in\mathbb{Z}^{L}\colon 0\leq j_{\ell}\leq \min\{d,n_{1}-j_{1},\ldots,n_{\ell-1}-j_{\ell-1}\}\) for all \(\ell=1,\ldots,L\big{\}}\) and \(s\in[d]\) is the dimension of the lineality space of a refinement of the canonical polyhedral complex of \(F\)._

Proof sketch.: Theorem 1 in [Serra et al., 2017] states that \(F\) has at most \(r\coloneqq\sum_{(j_{1},\ldots,j_{L})\in J}\prod_{l=1}^{L}\binom{n_{l}}{j_{l}}\) linear regions. In Section 5.4 we will provide a formal proof for the statement that we sketch here. Let \(\mathcal{P}\) be the canonical polyhedral complex of \(F\), i.e, \(F\) is affine linear on all polyhedra in \(\mathcal{P}\) (c.f Definition 38 in the appendix) and \(\mathcal{P}^{-}\) be a subcomplex of a refinement of \(\mathcal{P}\) such that \(F\) takes on exclusively non-positive values on all polyhedra in \(\mathcal{P}^{-}\). Therefore, the support \(|\mathcal{P}^{-}|\) of \(\mathcal{P}^{-}\) equals \(F^{-1}((-\infty,0])\) and we then proceed by showing the chain of inequalities

\[\beta_{k}(F)=\beta_{k}(|\mathcal{P}^{-}|)\leq\#\mathcal{P}_{k+1-\ell}\leq \binom{r}{d-k-\ell}\]

using cellular homology and polyhedral geometry, where \(\mathcal{P}_{k+1}\subseteq\mathcal{P}\) is the set of \((k+1)\)-dimensional polyhedra in \(\mathcal{P}\). This concludes the proof, since it also holds that \(\beta_{0}(|\mathcal{P}^{-}|)\leq\#\mathcal{P}_{d}=r\).

This implies that we obtain an upper bound that is polynomial in the width:

**Corollary 4**.: _Let \(F\colon\mathbb{R}^{d}\to\mathbb{R}\) be a neural network of architecture \((d,n_{1},\ldots,n_{L},1)\). Then it holds that \(\beta_{k}(F)\in O\left(\left(\prod_{i=1}^{L}n_{i}\right)^{d^{2}}\right)\) for \(k\in[d-2]\) and \(\beta_{0},\beta_{d-1}\in O\left(\left(\prod_{i=1}^{L}n_{i}\right)^{d}\right)\)._

## 4 Conclusion, Limitations and Outlook

Since it is widely accepted that data sets often have nontrivial topologies, investigating a neural network's ability to capture topological properties, as characterized by all Betti numbers, is an exciting and essential question that yields insight into the nature of ReLU networks. In an attempt to shed light on this question, we proved lower and upper bounds for the topological expressivity of ReLU neural networks with a given architecture. Our bounds give a rough estimate on how the architecture needs to be in order to be at least theoretically able to capture the topological complexity of the data set in these dimensions; in particular, in the first few dimensions where Betti numbers are computable in practice.
As a byproduct of our analysis we saw that two hidden layers are sufficient to increase the topological expressivity as much as we want at the expense of an increased width. Even though Betti numbers are a common complexity measure for topological spaces in data analysis, they only provide a coarse classification, i.e., two spaces can have the same Betti numbers but still look very different. Although there are finer topological invariants such as cohomology rings or homotopy groups, from a computational point of view, Betti numbers are a good trade-off between the ability to capture differences of spaces and tractability. Nevertheless, it might be interesting to find further topological or geometrical invariants to investigate the expressivity of neural networks in the setting of classification tasks.

Even though our lower bounds apply under certain restrictions of neural network architecture, this does not pose a big limitation for our purposes. Since our results are of a theoretical and mostly asymptotic nature, a constant factor (in the hidden layers resp. in the last hidden layer) is negligible. Besides, since our layers merely consists of many small layers put in parallel, one could also concatenate the layers in order to achieve a smaller width maintaining all the asymptotic results.

It seems straightforward that the construction in Section 2 can be adapted to neural networks with sigmoidal activation functions in a "smoothed" way. Therefore we conjecture that the same lower bound holds for the topological expressivity of neural networks with sigmoidal activation function, which would generalise the lower bound for the zeroth Betti number given in Bianchini and Scarselli (2014) to all Betti numbers.

AcknowledgementsThe authors would like to thank Christoph Hertrich and Martin Skutella for many valuable discussions and their careful proofreading. Moreover, we thank the various anonymous referees for their remarks.
