Expressivity of Spiking Neural Networks
The synergy between spiking neural networks and neuromorphic hardware holds
promise for the development of energy-efficient AI applications. Inspired by
this potential, we revisit the foundational aspects to study the capabilities
of spiking neural networks where information is encoded in the firing time of
neurons. Under the Spike Response Model as a mathematical model of a spiking
neuron with a linear response function, we compare the expressive power of
artificial and spiking neural networks, where we initially show that they
realize piecewise linear mappings. In contrast to ReLU networks, we prove that
spiking neural networks can realize both continuous and discontinuous
functions. Moreover, we provide complexity bounds on the size of spiking neural
networks to emulate multi-layer (ReLU) neural networks. Restricting to the
continuous setting, we also establish complexity bounds in the reverse
direction for one-layer spiking neural networks.
Manjot Singh, Adalbert Fono, Gitta Kutyniok
# Expressivity of Spiking Neural Networks

###### Abstract

This article studies the expressive power of spiking neural networks where information is encoded in the firing time of neurons. The implementation of spiking neural networks on neuromorphic hardware presents a promising choice for future energy-efficient AI applications. However, there exist very few results that compare the computational power of spiking neurons to arbitrary threshold circuits and sigmoidal neurons. Additionally, it has also been shown that a network of spiking neurons is capable of approximating any continuous function. By using the Spike Response Model as a mathematical model of a spiking neuron and assuming a linear response function, we prove that the mapping generated by a network of spiking neurons is continuous piecewise linear. We also show that a spiking neural network can emulate the output of any multi-layer (ReLU) neural network. Furthermore, we show that the maximum number of linear regions generated by a spiking neuron scales exponentially with respect to the input dimension, a characteristic that distinguishes it significantly from an artificial (ReLU) neuron. Our results further extend the understanding of the approximation properties of spiking neural networks and open up new avenues where spiking neural networks can be deployed instead of artificial neural networks without any performance loss.

## 1 Introduction

The development and the implementation of learning algorithms [10] coupled with the advancement in computational power -- GPUs and highly parallelized hardware -- have contributed to the recent empirical success of (deep) artificial neural networks [1]. Deep neural networks, nowadays, are used in a wide range of numerous real-world applications such as image recognition [14], natural language processing [21], [3], [15], [16], drug discovery [17], and game intelligence [18]. The downside of training and inferring on large deep neural networks implemented on classical digital hardware is the consumption of an enormous amount of time and energy [15].

At the same time, rapid advancement in the field of neuromorphic computing allows for both analog and digital computation, energy efficient and highly parallelized computational operations, and faster inference [20], [22]. Neuromorphic computers are electronic devices consisting of (artificial) neurons and synapses that aim to mimic the structure and certain functionalities of the human brain [19]. Unlike traditional von Neumann computers, which consist of separate processing and memory units, neuromorphic computers utilize neurons and synapses for both processing and memory tasks. In practice, a neuromorphic computer is typically programmed by deploying a network of spiking neurons [20], i.e., programs are defined by the structure and parameters of the neural network rather than explicit instructions. The computational model of a spiking neuron models the neural activity in the brain much more realistically as compared to other computational models of a neuron, thus making them well-suited for creating brain-like behaviour in these computers.
In this work, we adopt the shorthand notation "SNNs" for spiking neural networks and "ANNs" for other types of traditional artificial neural networks. In ANNs, both inputs and outputs are analog-valued. However, in SNNs, neurons transmit information to other neurons in the form of an _action-potential_ or a _spike_[10]. These spikes can be considered as point-like events in time, where incoming spikes received via a neuron's synapses trigger new spikes in the outgoing synapses. This asynchronous information transmission in SNNs stands in contrast to ANNs, where information is propagated synchronously through the network. Hence, a key difference between ANNs and SNNs lies in the significance of timing in the operation of SNNs. Moreover, the (typically analog) input information needs to be encoded in the form of spikes, necessitating a spike-based encoding scheme.

Different variations of encoding schemes exist, but broadly speaking, the information processing mechanisms can be classified into rate coding and temporal coding [14]. Rate coding refers to the number of spikes in a given time period ("firing frequency") whereas, in temporal coding, one is interested in the precise timing of a spike [15]. The notion of firing rate adheres to earlier neurobiological experiments where it was observed that some neurons fire frequently in response to some external stimuli ([16], [10]). The latest experimental results from neurobiology indicate that the firing time of a neuron is essential in order for the system to respond faster to more complex sensory stimuli ([17], [18], [19]). The firing rate results in higher latency and is computationally expensive due to extra overhead related to temporal averaging. With the firing time, each spike carries a significant amount of information, thus the resulting signal can be quite sparse. While there is no accepted standard on the correct description of neural coding, in this work, we assume that the information is encoded in the firing time of a neuron. The event-driven nature and the sparse information propagation through relatively few spikes, provided for instance by the time-to-first-spike encoding [10], facilitate system efficiency in terms of reduced computational power and improved energy efficiency. Due to the sporadic nature of spikes, a significant portion of the network remains idle while only a small fraction actively engages in performing computations. This efficient resource utilization allows SNNs to process information effectively while minimizing energy consumption.

It is intuitively clear that the described differences in the processing of the information between ANNs and SNNs should also lead to differences in the computations performed by these models. For ANNs, several groups have analyzed the expressive power of (deep) neural networks ([13], [15], [16], [17]), and in particular provided explanations for the superior performance of deep networks over shallow ones ([18], [13]). In the case of ANNs with ReLU activation function, the number of linear regions into which the input space is partitioned into by the ANN is another property that highlights the advantages of deep networks over shallow ones. Unlike shallow networks, deep networks divide the input space into exponentially more number of linear regions if there are no restrictions placed on the depth of the network ([12], [15]). This capability enables deep networks to express more complex functions. There exists further approaches to characterize the expressiveness of ANNs, e.g., the concept of VC-dimension in the context of classification problems ([1], [10], [11]). However, in this work, we consider the problem of expressiveness from the perspective of the approximating theory and by quantifying the number of the linear regions.

At the same time, very few attempts have been made that aim to understand the computational power of SNNs. By employing suitable encoding mechanisms to encode information through spikes, it has been shown that spiking neurons can emulate Turing machines, arbitrary threshold circuits, and sigmoidal neurons ([15], [16]). Similarly, [15] shows that continuous functions can be approximated to arbitrary precision using SNNs. In [15], biologically relevant functions are depicted that can be computed by a single spiking neuron but require ANNs with a significantly larger number of neurons to achieve the same task. A common theme is that the model of the spiking neurons and the description of their dynamics varies, in particular, it is often chosen and adjusted with respect to a specific goal or task. For instance, in [14], the authors delve into the theoretical exploration of self-connection spike neural networks, analyzing their approximation capabilities and computational efficiency. [17] aims at generating highly performant SNNs for image classification. The method applied, known as FS-conversion, involves a modified version of the standard spiking neuron model and entails configuring spiking neurons to emit only a limited number of spikes, while considering the precise spike timing. Hence, the results may not generalize to SNNs established via a different, more general neuronal model.
The primary challenge in advancing the domain of spiking networks has revolved around devising effective training methodologies. Optimizing spiking neural networks using gradient descent algorithm is hindered by discrete and non-differentiable nature of spike generation function. One way is to use approximate gradients to enable gradient descent optimization within such networks ([12], [13]). By using more elaborate schemes, ([3], [14]) are able to train networks using exact gradients. Due to the difficulty of effectively training SNNs from scratch, another line of research focuses on converting a trained ANN to an SNN performing the same task ([15], [16], [17], [18], [19], [18]). These works have primarily concentrated on the conversion of ANNs with ReLU activation function and effectively studied the algorithmic construction of SNNs approximating or even emulating given ANNs.

In an attempt to follow up along the lines of previous works, in particular, the expressivity of SNNs [10], the linear region property of ANNs [13] as well as first strides in that direction in SNNs [12], and the conversion of ReLU-ANNs into SNNs with time-to-first-spike encoding [14], we aim to extend the theoretical understanding that characterizes the differences and similarities in the expressive power between a network of spiking and artificial neurons employing a piecewise-linear activation function, which is a popular choice in practical applications [1]. Specifically, we aim to determine if SNNs possess the same level of expressiveness as ANNs in their ability to approximate various function spaces and in terms of the number of linear regions they can generate. This study does not focus on the learning algorithms for SNNs; however, we wish to emphasize that through a comprehensive examination of the computational power of SNNs, we can assess the potential advantages and disadvantages of their implementation in practical applications, primarily from a theoretical perspective. By exploring their capabilities, we gain valuable insights into how SNNs can be effectively utilized in various real-world scenarios.

ContributionsIn this paper, to analyze SNNs, we employ the noise-free version of the Spike Response Model (SRM) [1]. It describes the state of a neuron as a weighted sum of response and threshold functions. We assume a linear response function, where additionally each neuron spikes at most once to encode information through precise spike timing. This in turn simplifies the model and also makes the mathematical analysis more feasible for larger networks as compared to other neuronal models where the spike dynamics are described in the form of differential equations. In the future, we aim to expand our investigation to encompass multi-spike responses and refractoriness effects, thus, the selection of this model is appropriate and comprehensive. The main results are centered around the comparison of expressive power between SNNs and ANNs:

* **Equivalence of Approximation:** We prove that a network of spiking neurons with a linear response function outputs a continuous piecewise linear mapping. Moreover, we construct a two-layer spiking neural network that emulates the ReLU non-linearity. As a result, we extend the construction to multi-layer neural networks and show that an SNN has the capacity to effectively reproduce the output of any deep (ReLU) neural network. Furthermore, we present explicit complexity bounds that are essential for constructing an SNN capable of realizing the output of an equivalent ANN. We also provide insights on the influence of the encoding scheme and the impact of different parameters on the above approximation results.
* **Linear Regions:** We demonstrate that the maximum number of linear regions that a one-layer SNN generates scales exponentially with the input dimension. Thus, SNNs exhibit a completely different behaviour compared to ReLU-ANNs.

ImpactDue to the theoretical nature of this work, the results provided in this paper deepen our understanding of the differences and similarities between the expressive power of ANNs and SNNs. In theory, our findings indicate that the low-power neuromorphic implementation of spiking neural networks is an energy-efficient alternative to the computation performed by (ReLU-)ANNs without loss of expressive power. It serves as a meaningful starting point for exploring potential advantages that SNNs might have over ANNs. It also enhances our understanding of performing computations where time plays a critical role. Having said that, SNNs can represent and process information with precise timing, making them well-suited for tasks involving time-dependent patterns and events. We anticipate that the advances in event-driven neuromorphic computing will have a tremendous impact, especially for edge-computing applications such as robotics, autonomous driving, and many more. This is accomplished while prioritizing energy efficiency -- a crucial factor in modern computing
landscapes. Furthermore, one can also envision the possibility of interweaving ANNs and SNNs for obtaining maximum output in specific applications [14].

OutlineIn Section 2, we introduce necessary definitions, including the Spike Response Model and spiking neural networks. We present our main results in Section 3. In Section 4, we discuss related work and conclude in Section 5 by summarizing the limitations and implications of our results. The proofs of all the results are provided in the Appendix A.

## 2 Spiking neural networks

In [13], Maass described the computation carried out by a spiking neuron in terms of firing time. We use a similar model of computation for our purposes. First, we list the basic components and assumptions needed for constructing spiking neural networks followed by a description of the computational model, which then yields a mathematically sound definition.

In neuroscience literature, several mathematical models exist that describe the generation and propagation of action-potentials. Action-potentials or spikes are short electrical pulses that are the result of electrical and biochemical properties of a biological neuron [1]. The Hodgkin-Huxley model describes the neuronal dynamics in terms of four coupled differential equations and is the most realistic and accurate model in describing the neuronal dynamics ([12], [13]). This bio-chemical behaviour is modelled using electric circuits comprising of capacitors and resistors. Interested readers can refer to [13] for a comprehensive and detailed introduction to the dynamics of spiking neurons. To study the expressivity of SNNs, the main principles of a spiking neuron are condensed into a (simplified) mathematical model, where certain details about biophysics of a biological neuron are neglected. In this work, we consider the Spike Response Model (SRM) [1] as a formal model for a spiking neuron. It effectively captures the dynamics of the Hodgkin-Huxley model and is a generalized version of the leaky integrate and fire model [1]. The SRM leads to the following definition of an SNN [13].

**Definition 1**.: _A spiking neural network \(\Phi\) is a (simple) finite directed graph \((V,E)\) and consists of a finite set \(V\) of spiking neurons, a subset \(V_{\text{in}}\subset V\) of input neurons, a subset \(V_{\text{out}}\subset V\) of output neurons, and a set \(E\subset V\times V\) of synapses. Each synapse \((u,v)\in E\) is associated with_

* _a synaptic weight_ \(w_{uv}\geq 0\)_,_
* _a synaptic delay_ \(d_{uv}\geq 0\)_,_
* _and a response function_ \(\varepsilon_{uv}:\mathbb{R}^{+}\rightarrow\mathbb{R}\)_._

_Each neuron \(v\in V\setminus V_{\text{in}}\) is associated with_

* _a firing threshold_ \(\theta_{v}>0\)_,_
* _and a membrane potential_ \(P_{v}:\mathbb{R}\rightarrow\mathbb{R}\)_,_

_which is given by_

\[P_{v}(t)=\sum_{(u,v)\in E}\sum_{t_{u}^{f}\in F_{u}}w_{uv}\varepsilon_{uv}(t-t_{ u}^{f}), \tag{1}\]

_where \(F_{u}=\{t_{u}^{f}:1\leq f\leq n\text{ for some }n\in\mathbb{N}\}\) denotes the set of firing times of a neuron \(u\), i.e., times \(t\) whenever \(P_{u}(t)\) reaches \(\theta_{u}\) from below._

In general, the membrane potential includes an additional term \(\Theta_{v}:\mathbb{R}^{+}\rightarrow\mathbb{R}^{+}\), (aka _threshold function_), that models the refractoriness effect. That is, if a neuron \(v\) emits a spike at time \(t_{v}^{f}\), \(v\) cannot fire again for some time immediately after \(t_{v}^{f}\), regardless of how large its potential might be. However, we additionally assume that the information is encoded in single spikes, i.e., each neuron fires just once. Thus, the refractoriness effect can be ignored and we can effectively model the contribution of \(\Theta_{v}\) by the constant \(\theta_{v}\) introduced in the definition. Moreover, the single spike condition simplifies (1) to

\[P_{v}(t)=\sum_{(u,v)\in E}w_{uv}\varepsilon_{uv}(t-t_{u}),\quad\text{ where }t_{u}=\inf_{t\geq\min\limits_{(z,u)\in E}\{t_{u}+d_{zu}\}}P_{u}(t)\geq\theta_{u}. \tag{2}\]
The _response function_\(\varepsilon_{uv}(t)\) models the membrane potential of a postsynaptic neuron \(v\) as a result of a spike from a presynaptic neuron \(u\)[1]. A biologically realistic approximation to the response function \(\varepsilon_{uv}\) is a delayed \(\alpha\) function [1], which in particular is non-linear and leads to intractable problems when analyzing the propagation of spikes through an SNN. Hence, following [13], we only require \(\varepsilon_{uv}\) to satisfy the following condition:

\[\varepsilon_{uv}(t)=\begin{cases}0,&\text{if }t\notin[d_{uv},d_{uv}+\delta],\\ s\cdot(t-d_{uv}),&\text{if }t\in[d_{uv},d_{uv}+\delta],\end{cases} \tag{3}\]

where \(s\in\{+1,-1\}\) and \(\delta>0\) is some constant assumed to be the length of a linear segment of the response function. The _synaptic delay_\(d_{uv}\) is the time required for a spike to travel from \(u\) to \(v\). The variable \(s\) refers to the fact that biological synapses are either _excitatory_ or _inhibitory_. An excitatory postsynaptic potential increases, whereas an inhibitory postsynaptic potential decreases the membrane potential of a postsynaptic neuron \(v\).

Thus, inserting the condition (3) in (2) gives

\[P_{v}(t)=\sum_{(u,v)\in E}\mathbf{1}_{0<t-t_{u}-d_{uv}\leq\delta}\cdot w_{uv} \cdot s\cdot(t-t_{u}-d_{uv}),\quad\text{where }t_{u}=\inf_{t\geq\min\limits_{(s,u)\in E}\{t_{s}+d_{uv} \}}P_{u}(t)\geq\theta_{u}. \tag{4}\]

In the remainder, we set \(w_{uv}:=s\cdot w_{uv}\) and allow \(w_{uv}\) to take arbitrary values in \(\mathbb{R}\).

### Computation in terms of firing time

Using (4) enables us to iteratively compute the firing time \(t_{v}\) of each neuron \(v\in V\setminus V_{\text{in}}\) if we know the firing time \(t_{u}\) of each neuron \(u\in V\) with \((u,v)\in E\) by solving for \(t\) in

\[\inf_{t\geq\min\limits_{(u,v)\in E}\{t_{u}+d_{uv}\}}P_{v}(t)=\inf_{t\geq\min \limits_{(u,v)\in E}\{t_{u}+d_{uv}\}}\sum_{(u,v)\in E}\mathbf{1}_{0<t-t_{u}-d _{uv}\leq\delta}\cdot w_{uv}(t-t_{u}-d_{uv})=\theta_{v}. \tag{5}\]

In particular, \(t_{v}\) satisfies

\[\theta_{v}=\sum_{(u,v)\in E}\mathbf{1}_{0<t-t_{u}-d_{uv}\leq\delta}\cdot w_{uv }(t_{v}-t_{u}-d_{uv})=\sum_{(u,v)\in E(\mathbf{t}_{U})}w_{uv}(t_{v}-t_{u}-d_{uv }), \tag{6}\]

where \(E(\mathbf{t}_{U}):=\{(u,v)\in E:d_{uv}+t_{u}<t_{v}\leq d_{uv}+t_{u}+\delta\}\) and \(\mathbf{t}_{U}:=(t_{u})_{(u,v)\in E}\) is a vector containing the given firing times of the presynaptic neurons. In other words, \(E(\mathbf{t}_{U})\) identifies the presynaptic neurons that actually have an effect on \(t_{v}\) based on \(\mathbf{t}_{U}\). For instance, if \(t_{w}>t_{v}\) for some synapse \((w,v)\in E\), then \(w\) certainly did not contribute to the firing of \(v\) since the spike from \(w\) arrived after \(v\) already fired so that \((w,v)\notin E(\mathbf{t}_{U})\). Finally, the firing time of \(t_{v}\) is then explicitly given by

\[t_{v}=\frac{\theta_{v}}{\sum_{(u,v)\in E(\mathbf{t}_{U})}w_{uv}}+\frac{\sum_{( u,v)\in E(\mathbf{t}_{U})}w_{uv}(t_{u}+d_{uv})}{\sum_{(u,v)\in E(\mathbf{t}_{U})}w_{uv }}. \tag{7}\]

The dynamic of a simple network in this model is depicted in Figure 1.

**Remark 1**.: _Equation (7) shows that \(t_{v}\) is a weighted sum (up to a positive constant) of the firing times of neurons \(u\) with \((u,v)\in E(\mathbf{t}_{U})\). Flexibility in this model is provided through \(E(\mathbf{t}_{U})\). Depending on the firing time of the presynaptic neurons \(\mathbf{t}_{U}\) and the associated parameters (weights, delays, threshold), \(E(\mathbf{t}_{U})\) contains a set of different synapses so that the expression in (7) varies accordingly. We will further study this property in Section 3.4._

**Remark 2**.: _Subsequently, we will employ (7) to analyze and construct SNNs. In particular, we simply assume that the length \(\delta\) of the linear segment of the response function introduced in (3) is large enough so that (7) holds. Informally, a small linear segment requires incoming spikes to have a correspondingly small time delay to jointly affect the potential of a neuron. Otherwise, the impact of the earlier spikes on the potential may already have vanished before the subsequent spikes arrive. Consequently, incorporating \(\delta\) as an additional parameter in the SNN model leads to additional complexity since the same firing patterns may result in different outcomes. However, an in-depth analysis of this effect is left as future work._
The final model provides a highly simplified version of the dynamics observed in biological neural systems. Nevertheless, we attain a theoretical model that, in principle, can be directly implemented on neuromorphic hardware and moreover, enables us to analyze the computations that can be carried out by a network of spiking neurons. When the parameter \(\delta\) is arbitrarily large, then the simplified Spike Response Model, stemming from the linear response function and the constraint of single-spike dynamics, exhibits similarities to the integrate and fire model. Conversely, if \(\delta\) is arbitrarily small, it resembles leaky integrate and fire model.

### Input and output encoding

By restricting our framework of SNNs to acyclic graphs, we can arrange the underlying graph in layers and equivalently represent SNNs by a sequence of their parameters. This is analogous to the common representation of feedforward ANNs via a sequence of matrix-vector tuples ([1], [2]).

**Definition 2**.: _Let \(d,L\in\mathbb{N}\). A spiking neural network \(\Phi\) with input dimension \(d\) and \(L\) layers associated to the acyclic graph \((V,E)\) is a sequence of matrix-matrix-vector tuples_

\[\Phi=((W^{1},D^{1},\Theta^{1}),(W^{2},D^{2},\Theta^{2}),\dots,(W^{L},D^{L}, \Theta^{L}))\]

_where \(N_{0}=d\) and \(N_{1},N_{2},\dots,N_{L}\in\mathbb{N}\), and where each \(W^{l}\) and each \(D^{l}\) is an \(N_{l-1}\times N_{l}\) matrix, and \(\Theta^{l}\in\mathbb{R}_{+}^{N_{l}}\). \(N_{0}\) is the input dimension and \(N_{L}\) is the output dimension of the network. The matrix entry in \(W^{l}_{uv}\) and \(D^{l}_{uv}\) represents the weight and delay value associated with the synapse \((u,v)\in E\), and the entry \(\Theta^{l}_{v}\) is the firing threshold associated with node \(v\). We call \(N(\Phi):=d+\sum_{j=1}^{L}N_{j}\) the number of neurons of the network \(\Phi\), and \(L(\Phi):=L\) denotes the number of layers of \(\Phi\)._

**Remark 3**.: _In an ANN, each layer performs some non-linear transformation on their inputs and then the information is propagated through the layers in a synchronized manner. However, in an SNN, information is transmitted through the network in the form of spikes. Spikes from neurons in layer \(l-1\) influence the membrane potential of neurons in layer \(l\) and ultimately trigger them to spike (according to the framework described in the previous paragraph). Hence, spikes are propagated through the network asynchronously since the firing times of the individual neurons vary._

The (typically analog) input information needs to be translated into the input firing times of the employed SNN, and similarly, the output firing times of the SNN need to be translated back to an

Figure 1: (a) A single layer spiking network with one output neuron \(v\). Neuron \(v\) receives inputs from five input neurons \(u_{1},\dots,u_{5}\) that fire at times \(t_{u_{1}},\dots,t_{u_{5}}\) respectively. (b) The trajectory in black shows the evolution of the membrane potential \(P_{v}(t)\) of neuron \(v\) as a result of spikes from input neurons that arrive at times \(t_{u_{i}v}+d_{u_{i}v}\) (vertical arrows). Neurons \(u_{1}\) and \(u_{2}\) generate excitatory postsynaptic potentials with distinct strengths represented by \(w_{u_{i}v}\), while neurons \(u_{3}\) and \(u_{5}\) produce inhibitory postsynaptic potentials with varying strengths (dashed lines). Neuron \(v\) fires at time \(t_{v}\) once \(P_{v}(t_{v})=\theta\). The spike from neuron \(u_{4}\) does not influence the firing time of \(v\) since \(t_{v}<t_{u_{4}}+d_{u_{4}v}\).
appropriate target domain. We will refer to this process as input encoding and output decoding. In general, the applied encoding scheme certainly depends on the specific task at hand. For tasks that involve modelling complex time patterns or a sequence of events with multiple spikes, sophisticated encoding schemes may be required. However, we can formulate some guiding principles for establishing the encoding scheme. The firing times of input and output neurons should encode analog information in a consistent way so that different networks can be concatenated in a well-defined manner. This enables us to construct suitable subnetworks and combine them appropriately to solve more complex tasks. Second, our focus in this work lies on exploring the intrinsic capabilities of SNNs, rather than the specifics of the encoding scheme. In the extreme case, the encoding scheme might directly contain the solution to a problem, underscoring the need for a sufficiently simple and broadly applicable encoding scheme to avoid this. The potential power and suitability of different encoding schemes is a topic that warrants separate investigation on its own.

**Remark 4**.: _Based on these considerations and our setting, we fix an appropriate encoding scheme. However, we will point out occasionally the effect of adjusting the scheme in certain ways. Analog input information is encoded in the firing times of the input neurons of an SNN \(\Phi\) in the following manner: For any \(x\in[a,b]^{d}\), \(d\in\mathbb{N}\), \(a,b\in\mathbb{R}\), we set the firing times of the input neurons \(u_{1},\ldots,u_{d}\) of \(\Phi\) to \((t_{u_{1}},\ldots,t_{u_{d}})^{T}=T_{in}+x\), where \(T_{in}\in\mathbb{R}^{d}\) is some constant reference time, e.g., \(T_{in}=(a,\ldots,a)^{T}\). The bounded input domain ensures that an appropriate reference time can be fixed. The firing times of the non-input neurons of \(\Phi\) are then determined based on (7). Finally, the firing times of the output neurons \(v_{1},\ldots,v_{n}\) encode the target \(y\in\mathbb{R}^{n}\) via \((t_{v_{1}},\ldots,t_{v_{d}})^{T}=T_{out}+y\), where \(T_{out}\in\mathbb{R}^{n}\) is some constant reference time. For simplicity and with a slight abuse of notation, we will sometimes refer to \(T_{in},T_{out}\) as one-dimensional objects, i.e., \(T_{in},T_{out}\in\mathbb{R}\) which is justified as the corresponding vectors contain the same element in each dimension (see Figure 2). Additionally, note that the introduced encoding scheme translates analog information into input firing times in a continuous manner._

For the discussion ahead, we point out the difference between a network and the target function it realizes. A network is a structured set of weights, delays and thresholds as defined in Definition 2, and the target function it realizes is the result of the asynchronous propagation of spikes through the network.

**Definition 3**.: _On \([a,b]^{d}\) with \(a,b\in\mathbb{R}\), the realization of an SNN \(\Phi\) with input reference time \(T_{in}\in\mathbb{R}\) and \(N_{L}\in\mathbb{N}\) output neurons \(v_{1},\ldots,v_{N_{L}}\) is defined as the map \(\mathcal{R}_{\Phi}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{N_{L}}\) such that_

\[\mathcal{R}_{\Phi}(x)=(-T_{out}+t_{v_{1}},\ldots,-T_{out}+t_{v_{N_{L}}})^{T},\]

_where the firing times of the output neuron provide the realization \(\mathcal{R}_{\Phi}(x)\) of \(\Phi\) in temporal coding, i.e., \(v_{1},\ldots,v_{N_{L}}\) fire at time \((T_{out},\ldots,T_{out})^{T}+\mathcal{R}_{\Phi}(x)\) for some fixed output reference time \(T_{out}>T_{in}\)._

Next, we give a corresponding definition of an ANN and its realization.

Figure 2: Computation graph associated with a spiking neural network \(\Phi\) with input-output dimension \(d\), width \(d\) and \(L-1\) hidden layers. The synapses in between the layers are labelled with synaptic weight matrices \(W\) and delay matrices \(D\). Each node in the network \(\Phi\) is associated with a threshold parameter \(\theta\). Analog input and output values are encoded in the firing time \(t_{u_{i}}=T_{\text{in}}+x_{i}\) (respectively \(t_{v_{i}}=T_{\text{out}}+y_{i}\)) of a neuron.
**Definition 4**.: _Let \(d,L\in\mathbb{N}\). An artificial neural network \(\Psi\) consisting of \(d\) input neurons and \(L\) layers is a sequence of matrix-vector tuples_

\[\Psi=((W^{1},B^{1}),(W^{2},B^{2}),\ldots,(W^{L},B^{L}))\]

_where \(N_{0}=d\) and \(N_{1},\ldots,N_{L}\in\mathbb{N}\), and where each \(W^{l}\) is an \(N_{l-1}\times N_{l}\) matrix, and \(B^{l}\in\mathbb{R}^{N_{l}}\). \(N_{0}\) is the input dimension and \(N_{L}\) is the output dimension of the network. We call \(N(\Psi):=\sum_{j=0}^{L}N_{j}\) the number of neurons of the network \(\Psi\), \(L(\Psi):=L\) the number of layers of \(\Psi\) and \(N_{l}\) the width of \(\Psi\) in layer \(l\). The realization of \(\Psi\) is defined as the map \(\mathcal{R}_{\Psi}:\mathbb{R}^{N_{0}}\rightarrow\mathbb{R}^{N_{L}}\),_

\[\mathcal{R}_{\Psi}(x)=y_{L},\]

_where \(y_{L}\) results from_

\[y_{0} =x,\] \[y_{l} =\sigma(W^{l}y_{l-1}+B^{l}),\text{ for }l=1,\ldots,L-1,\] \[y_{L} =W^{L}y_{L-1}+B^{L}, \tag{8}\]

_where \(\sigma:\mathbb{R}\rightarrow\mathbb{R}\) is acting component-wise and is called the activation function._

**Remark 5**.: _From now on, we will always employ ReLU, i.e., \(\sigma(x)=\max(0,x)\) as the activation function of an ANN. Finally, we assume that the realization is defined on some bounded domain \([a,b]^{d}\subset\mathbb{R}^{d}\)._

One can perform basic actions on neural networks such as concatenation and parallelization to construct larger networks from existing ones. Adapting a general approach for ANNs as defined in ([11], [2]), we formally introduce the concatenation and parallelization of networks of spiking neurons in the Appendix A.1.

## 3 Main results

In the first part, we prove that SNNs generate **C**ontinuous **P**iecewise **L**inear (CPWL) mappings, followed by realizing a ReLU activation function using a two-layer SNN. Subsequently, we provide a general result that shows that SNNs can emulate the realization of any multi-layer ANN employing ReLU as an activation function. Lastly, we analyze the number of linear regions generated by SNNs and compare the arising pattern to the well-studied case of ReLU-ANNs. If not stated otherwise, the encoding scheme introduced in Remark 4 is applied and the results need to be understood with respect to this specific encoding.

### Spiking neural networks realize continuous piecewise linear mapping

A broad class of ANNs based on a wide range of activation functions such as ReLU generate CPWL mappings [10], [12]. In other words, these ANNs partition the input domain into regions, the so-called linear regions, on which an affine function represents the neural network's realization. We show that SNNs also express CPWL mappings under very general conditions. The proof of the statement can be found in the Appendix A.2.

**Theorem 1**.: _Any SNN \(\Phi\) realizes a CPWL function provided that the sum of synaptic weights of each neuron is positive and the encoding scheme is a CPWL function._

**Remark 6**.: _Note that the encoding scheme introduced in Remark 4 is a CPWL mapping (in input as well as output encoding)._

**Remark 7**.: _The positivity of the sum of weights ensures that each neuron in the network emits a spike. In general, if this condition is not met by a neuron, then it does not fire for certain inputs. Therefore, the case may arise where an output neuron does not fire and the realization of the network is not well-defined. Via the given condition we prevent this behaviour. For a given SNN with an arbitrary but fixed input domain it is a sufficient but not necessary condition to guarantee that spikes are emitted by the the output neurons. Instead, one could also adapt the definition of the realization of an SNN, however, the CPWL property described in the theorem may be lost._

Despite the fact that ReLU is a very basic CPWL function, it is not straightforward to realize ReLU via SNNs; see Appendix A.3 for the proof.
**Theorem 2**.: _Let \(a<0<b\). There does not exist a one-layer SNN that realizes \(\sigma(x)=\max(0,x)\) on \([a,b]\). However, \(\sigma\) can be realized by a two-layer SNN on \([a,b]\)._

**Remark 8**.: _We note that the encoding scheme that converts the analog values into the time domain plays a crucial role. In the proof of the Theorem 2, an SNN is constructed that realizes \(\sigma\) via the encoding scheme \(T_{\text{in}}+\cdot\) and \(T_{\text{out}}+\cdot\). At the same time, the encoding scheme \(T_{\text{in}}-\cdot\) and \(T_{\text{out}}-\cdot\) fails in the two-layer case. Moreover, utilizing an inconsistent input and output encoding enables us to construct a one-layer SNN that realizes \(\sigma\). This shows that not only the network but also the applied encoding scheme is highly relevant. For details, we refer to Appendix A.3._

**Remark 9**.: _Note that in a hypothetical real-world implementation, which certainly includes some noise, the constructed SNN that realizes ReLU is not necessarily robust with respect to input perturbation. Analyzing the behaviour and providing error estimations is an important future task._

### Expressing ReLU-network realizations by spiking neural networks

In this subsection, we extend the realization of a ReLU neuron to the entire network, i.e., realize the output of any ReLU network using SNNs. The proof of the following statement can be found in the Appendix A.4.

**Theorem 3**.: _Let \(L,d\in\mathbb{N}\), \([a,b]^{d}\subset\mathbb{R}^{d}\) and let \(\Psi\) be an arbitrary ANN of depth \(L\) and fixed width \(d\) employing a ReLU non-linearity, and having one-dimensional output. Then, there exists an SNN \(\Phi\) with \(N(\Phi)=N(\Psi)+L(2d+3)-(2d+2)\) and \(L(\Phi)=3L-2\) that realizes \(\mathcal{R}_{\Psi}\) on \([a,b]^{d}\)._

Sketch of proof.: Any multi-layer ANN with ReLU activation is simply an alternating composition of affine-linear functions and a non-linear function represented by ReLU. To realize the mapping generated by some arbitrary ANN, it suffices to realize the composition of affine-linear functions and the ReLU non-linearity and then extend the construction to the whole network using concatenation and parallelization operations. 

**Remark 10**.: _The aforementioned result can be generalized to ANNs with varying widths that employ any type of piecewise linear activation function._

**Remark 11**.: _In this work, the complexity of neural networks is assessed in terms of the number of computational units and layers. However, the complexity of an SNN can be captured in different ways as well. For instance, the total number of spikes emitted in an SNN is related to its energy consumption (since emitting spikes consumes energy). Hence, the minimum number of spikes to realize a given function class may be a reasonable complexity measure for an SNN (with regard to energy efficiency). Further research in this direction is necessary to evaluate the complexity of SNNs via different measures with their benefits and drawbacks._

### Equivalence of approximation

It is well known that ReLU-ANNs not only realize CPWL mappings but that every CPWL function in \(\mathbb{R}^{d}\) can be represented by ReLU-ANNs if there are no restrictions placed on the number of parameters or the depth of the network [1], [3]. Therefore, ReLU-ANNs can represent any SNN with a CPWL encoding scheme. On the other hand, our results also imply that SNNs can represent every ReLU-ANN and thereby every CPWL function in \(\mathbb{R}^{d}\). The key difference in the realization of arbitrary CPWL mappings is the necessary size and complexity of the respective ANN and SNN.

Recall that realizing the ReLU activation via SNNs required more computational units than the corresponding ANN (see Theorem 3). Conversely, we demonstrate using a toy example that SNNs can realize certain CPWL functions with fewer number of computational units and layers compared to ReLU-based ANNs.

**Example 1**.: _For \(\theta>0\), \([a,b]\subset\mathbb{R}\), consider the CPWL function \(f:[a,b]\rightarrow\mathbb{R}\) given by_

\[f(x)=\begin{cases}x,&x\leq-\theta\\ \frac{x-\theta}{2},&-\theta<x<\theta\\ 0,&x\geq\theta\end{cases}=-\frac{1}{2}\sigma(-x-\theta)-\frac{1}{2}\sigma(-x+ \theta), \tag{9}\]

_where \(\sigma\) is the ReLU activation. A one-layer SNN with one output unit and two input units can realize \(f\). However, to realize \(f\), any ReLU-ANN requires at least two layers and four computational units; see Appendix A.5 for the proof._
These observations illustrate that the computational structure of SNNs differs significantly from that of ReLU-ANNs. While neither model is clearly beneficial in terms of network complexity to express all CPWL functions, each model has distinct advantages and disadvantages. To gain a better understanding of this divergent behaviour, in the next section, we study the number of linear regions that SNNs generate.

### Number of linear regions

The number of linear regions can be seen as a measure for the flexibility and expressivity of the corresponding CPWL function. Similarly, we can measure the expressivity of an ANN by the number of linear regions of its realization. The connection of the depth, width, and activation function of a neural network to the maximum number of its linear regions is well-established, e.g., with increasing depth the number of linear regions can grow exponentially in the number of parameters of an ANN ([14], [1], [1]). This property offers one possible explanation for why deep networks tend to outperform shallow networks in expressing complex functions. Can we observe a similar behaviour for SNNs?

To that end, we first analyze the properties of a spiking neuron. For the proof, we refer to Appendix A.2.

**Theorem 4**.: _Let \(\Phi\) be a one-layer SNN with a single output neuron \(v\) and \(d\) input neurons \(u_{1},\ldots,u_{d}\) such that \(\sum_{i=1}^{d}w_{u_{i}v}>0\). Then \(\Phi\) partitions the input domain into at most \(2^{d}-1\) linear regions. In particular, for a sufficiently large input domain, the maximal number of linear regions is attained if and only if all synaptic weights are positive._

**Remark 12**.: _By examining the parameters of \(\Phi\), one can assess the number of linear regions into which the input domain is divided by \(\Phi\). For instance, if a single input neuron \(u_{j}\) causes the firing of \(v\), then the corresponding synaptic weight \(w_{u_{j}v}\) is necessarily positive. Thus, if \(w_{u_{j}v}\leq 0\), then \(u_{j}\) could not have caused the firing of \(v\) and \(\Phi\) can under no circumstances achieve the maximal number of linear regions. Similarly, one can derive via (7) that any subset of input neurons {\(u_{j_{1}},\ldots,u_{j_{k}}\)} with \(\sum_{i}w_{u_{j_{i}}v}\leq 0\) did not cause a firing of \(v\). The condition \(\sum_{i=1}^{d}w_{u_{i}v}>0\) simply ensures that the notion of linear region is applicable. Otherwise, the input domain is still partitioned into polytopes by the SNN but there exists a region where the realization of the network is not well-defined (see Remark 7). Finally, to ensure that the linear region corresponding to a subset of input neurons with a positive sum of weights is actually realized, the input domain simply needs to be chosen suitably large._

**Remark 13**.: _One-layer ReLU-ANNs and one-layer SNNs with one output neuron both partition the input domain into linear regions. Nevertheless, the differences are noteworthy. A one-layer ReLU-ANN will partition the input domain into at most two linear regions, independent of the dimension of the input. In contrast, for a one-layer SNN the maximum number of linear regions scales exponentially in the input dimension. One may argue that the distinct behaviour arises due to the fact that the 'non-linearity' in the SNN is directly applied on the input, whereas the non-linearity in the ANN is applied on the single output neuron. By shifting the non-linearity and applying it instead on the input, the ANN would exhibit the same exponential scaling of the linear regions as the SNN. However, this change would not reflect the intrinsic capabilities of the ANN since it has rather detrimental effect on the expressivity and, in particular, the partitioning of the input domain is fixed and independent of the parameters of the ANN. In contrast, for SNNs one can also explicitly compute the boundaries of the linear regions. This is exemplarily demonstrated for a two-dimensional input space in Appendix A.2. It turns out that only specific hyperplanes are eligible as boundaries of the linear region in this simple scenario. Hence, the flexibility of the SNN model to generate arbitrary linear regions is to a certain extent limited, albeit not entirely restricted as in the adjusted ANN._

Although we established interesting differences in the structure of computations between SNNs and ANNs, many questions remain open. In particular, the effect of depth in SNNs needs further consideration. The full power of ANN comes into play with large numbers of layers. Our result in Theorem 4 suggests that a shallow SNN can be as expressive as a deep ReLU network in terms of the number of linear regions required to express certain types of CPWL functions. In ([15]; Lemma 3), the authors showed that a deep neural network employing any piecewise linear activation function cannot span all CPWL functions with the number of linear regions scaling exponentially in the number of parameters of the network. Studying these types of functions and identifying (or excluding) similar behaviour for SNNs requires a deeper analysis of the capabilities of SNNs, providing valuable insights into their computational power. This aspect is left for future investigation.
Related work

The inherently complex dynamics of spiking neurons complicate the analysis of computations carried out by an SNN. In this section, we mention the most relevant results that investigate their computational or expressive power. One of the central results in this direction is the Universal Approximation Theorem for SNNs [14]. The author showed the existence of SNNs that approximates arbitrary feedforward ANNs employing sigmoidal activation function and thus, approximating any continuous function. The result is based on temporal coding by single spikes and under the presence of some additional assumptions on the response and threshold functions. In contrast, we show that an SNN can realize the output of an arbitrary ANN with CPWL activation and further specify the size of the network to achieve the associated realization, which has not been previously demonstrated. Moreover, we also study the expressivity of SNNs in terms of the number of linear regions and provide new insights on realizations generated by SNNs. [13] shows that continuous functions can be approximated to arbitrary precision using SNNs in temporal coding. In another direction, the author in [14] constructed SNNs that simulate arbitrary threshold circuits, Turing machines and a certain type of random access machines with real-valued inputs.

In [15], the authors delve into the theoretical exploration of self-connection spike neural networks (scSNNs), analyzing their approximation capabilities and computational efficiency. The theoretical findings demonstrate that scSNNs, when equipped with self-connections, can effectively approximate discrete dynamical systems with a polynomial number of parameters and within polynomial time complexities. Our approach centers on precise spike timing, while theirs hinges on firing rates and includes a distinct model featuring self-connections, further setting their approach apart from ours. The study by [10] presents convergence theory that rigorously establishes the convergence of firing rates to solutions corresponding to LASSO problems in the Locally Competitive Algorithms framework.

Another line of research focuses on converting (trained) ANNs, in particular with ReLU activation, into equivalent SNNs and, thereby avoiding or facilitating the training process of SNNs. This has been studied for various encoding schemes, spike patterns and spiking neuron models ([17], [18], [19], [20], [15], [21], [22], [23]). By introducing a general algorithmic conversion from ANNs to SNNs, one also establishes approximation and/or emulation capabilities of SNNs in the considered setting. Most related to our analysis of the expressivity of SNNs are the results in [12]. The authors define a one-to-one neuron mapping that converts a trained ReLU neural network to a corresponding SNN consisting of integrate and fire neurons by a non-linear transformation of parameters. This is done under the assumption of having access to a trained ReLU network, weights and biases of the trained model and the input data on which the model was trained. We point out that the underlying idea of representing information in terms of spike time and apply choosing the parameters of an SNN model such that the output is encoded in the firing time is similar to ours. However, significant distinctions exist between our approach and theirs, particularly in terms of the chosen model, objectives, and methodology. Our choice of the model is driven by our intention to better understand expressivity outcomes. In terms of methodology, we introduce an auxiliary neuron to ensure the firing of neurons even when a corresponding ReLU neuron exhibits zero activity. This diverges from their approach, which employs external current and a special parameter to achieve similar outcomes. Moreover, our work involves a fixed threshold for neuron firing, whereas their model incorporates a threshold that varies with time. Lastly, we study the differences in expressivity and structure of computations between ANNs and SNNs, whereas in [12], only the general conversion of ANNs to SNNs is examined and not vice versa.

Finally, we would like to mention that a connection between SNNs and piecewise linear functions was already noted in [16]. The author shows that a spiking network consisting of non-leaky integrate and fire neurons, employing exponentially decaying synaptic current kernels and temporal coding, exhibits a piecewise linear input-output relation after a transformation of the time variable. This piecewise relation is continuous unless small perturbations influences the spiking behaviour, specifically concerning whether the neuron fires or remains inactive.

## 5 Discussion

The central aim of this paper is to study and compare the expressive power of SNNs and ANNs employing any piecewise linear activation function. In an ANN, information is propagated across
the network in a synchronized manner. In contrast, in SNNs, spikes are only emitted once a subset of neurons in the previous layer triggers a spike in a neuron in the subsequent layer. Hence, the imperative role of time in biological neural systems accounts for differences in computation between SNNs and ANNs. We show that a one-layer SNN with one output neuron can partition the input domain into an exponential number of linear regions with respect to the input dimension. The exact number of linear regions depends on the parameters of the network. Our expressivity result in Theorem 3 implies that SNNs can essentially approximate any function with the same accuracy and (asymptotic) complexity bounds as (deep) ANNs employing a piecewise linear activation function, given the response function satisfies some basic assumptions. Rather than approximating some function space by emulating a known construction for ReLU networks, one could also achieve optimal approximations by leveraging the intrinsic capabilities of SNNs instead. The findings in Theorem 4 indicate that the latter approach may indeed be beneficial in terms of the complexity of the architecture in certain circumstances. However, we point out that finding optimal architectures for approximating different classes of functions is not the focal point of our work. The significance of our results lies in investigating theoretically the approximation and expressivity capabilities of SNNs, highlighting their potential as an alternative computational model for complex tasks. The insights obtained from this work can further aid in designing architectures that can be implemented on neuromorphic hardware for energy-efficient applications.

Extending the model of a spiking neuron by incorporating, e.g., multiple spikes of a neuron, may yield improvements on our results. However, by increasing the complexity of the model the analysis also tends to be more elaborate. In the aforementioned case of multiple spikes the threshold function becomes important so that additional complexity when approximating some target function is introduced since one would have to consider the coupled effect of response and threshold functions. Similarly, the choice of the response function and the frequency of neuron firings will surely influence the approximation results and we leave this for future work.

LimitationsIn theory, we prove that SNNs are as expressive as ReLU-ANNs. However, achieving similar results in practice heavily relies on the effectiveness of the training algorithms employed. The implementation of efficient learning algorithms with weights, delays and thresholds as programmable parameters is left for future work. However, there already exists training algorithms such as the SpikeProp algorithm [1], [22], which consider the same programmable parameters as our model and may be a reasonable starting point for future implementations. In this work, our choice of model resides on theoretical considerations and not on practical considerations regarding implementation. However, there might be other models of spiking neurons that are more apt for implementation purposes -- see e.g. [23] and [24]. Furthermore, in reality, due to the ubiquitous sources of noise in the spiking neurons, the firing activity of a neuron is not deterministic. For mathematical simplicity, we perform our analysis in a noise-free case. Generalizing to the case of noisy spiking neurons is important (for instance with respect to the aforementioned implementation in noisy environments) and may lead to further insights in the model.

M. Singh is supported by the DAAD programme Konrad Zuse Schools of Excellence in Artificial Intelligence, sponsored by the Federal Ministry of Education and Research. M. Singh also acknowledges support from the Munich Center for Machine Learning (MCML).

G. Kutyniok acknowledges support from LMUexcellent, funded by the Federal Ministry of Education and Research (BMBF) and the Free State of Bavaria under the Excellence Strategy of the Federal Government and the Lander as well as by the Hightech Agenda Bavaria. Further, G. Kutyniok was supported in part by the DAAD programme Konrad Zuse Schools of Excellence in Artificial Intelligence, sponsored by the Federal Ministry of Education and Research. G. Kutyniok also acknowledges support from the Munich Center for Machine Learning (MCML) as well as the German Research Foundation under Grants DFG-SPP-2298, KU 1446/31-1 and KU 1446/32-1 and under Grant DFG-SFB/TR 109, Project C09 and the German Federal Ministry of Education and Research (BMBF) under Grant MaGriDo.