Agreement in Spiking Neural Networks

Abstract

We study the problem of binary agreement in a spiking neural network (SNN). We show that binary agreement on n inputs can be achieved with $O (n)$ of auxiliary neurons. Our simulation results suggest that agreement can be achieved in our network in $O (log n)$ time. We then describe a subclass of SNNs with a biologically plausible property, which we call size-independence. We prove that solving a class of problems, including agreement and Winner-Take-All, in this model requires $Ω (n)$ auxiliary neurons, which makes our agreement network size-optimal.

1. Introduction

In many brain areas, neurons with homogeneous properties are organized in populations. Prominent examples are columns in the visual and somatosensory cortex (Mountcastle, 1957; Hubel and Wiesel, 1962) and neurons with “memory fields” in the prefrontal cortex (Goldman-Rakic, 1995). Neuronal activity patterns in these populations are believed to represent sensory variables or memory states that are relevant for perception and behavior (Kandel et al., 1991).

Computational neuroscience often treats these activity patterns as stationary solutions to state equations, describing average values of relevant neuronal variables such as neurons’ membrane potential or firing rate (Gerstner and Kistler, 2002; Shriki et al., 2003). The stationary solutions can be spatially inhomogeneous or homogeneous. An example of a useful inhomogeneous solution is an activity pattern in which only a small group of neurons are active.

Active neurons could represent a particular value of a variable encoded in the population. Homogeneous solutions, in which all neurons act in the same way, are the building blocks of event detectors or memory units. For example, a bistable population of binary units can signal whether an event has occurred in the input.

The two general classes of solutions (inhomogeneous and homogeneous) can be mapped to classical problems in distributed computing: leader election and agreement. In the problem of leader election, each of the processing units (or processes) should eventually converge to decide whether it is a leader or not, corresponding to a stationary network state with only one active unit. Lynch et al. (2017a), see also Lynch and Musco (2018); Su et al. (2019), studied the leader-election problem (also known as Winner-Take-All [WTA]) in a biologically inspired spiking neural network (SNN) model. It has been shown that WTA has an efficient neural circuit (Lynch et al., 2017a). Later, the results were formally restated in the novel stochastic SNN model (Lynch and Musco, 2018) and generalized to solving k-WTA (Su et al., 2019).

In this article, we address the class of agreement problems that appear complementary to WTA. In binary agreement, output neurons should eventually stabilize on 1 (all output neurons fire) or 0 (no output neurons fire), and the output should be the state of at least one input neuron.

Following the approach of Lynch et al. (2017a); Lynch and Musco (2018); Su et al. (2019), we treat a neural network as a distributed system, where neurons and synapses connecting them are modeled as a graph of finite-state automata. Neurons communicate by firing in discrete pulses. Each pulse is generated in stochastic response to a sufficiently strong input over the incoming graph edges.

We show that basic binary agreement on n inputs, where any input value can be chosen as a stable output, can be achieved by using $O (n)$ of auxiliary neurons. As experimentally shown, our network converges to the agreement state in nearly constant time, and we conjecture that the expected convergence time is $O (log n)$ .

We then prove that this is optimal for a class of biologically plausible SNNs that we call size-independent. More precisely, we assume that a network is composed of “off-the-shelf” neurons: The weights of their synapses and the activation function are constant in n, the number of input neurons. We show that any size-independent network serving n input neurons and solving a task in a large class including agreement and WTA must use $O (n)$ auxiliary neurons.¹

We believe that determining optimal networks implementing fundamental computing abstractions, such as leader election and agreement, may help explain how these tasks are solved in the brain. The general hypothesis of neural studies is that the brain tends to optimize information processing (Barlow, 1961), and one may expect that the network size could be a possible optimization goal.

The rest of the article is organized as follows. In Section 2, we sketch the basic definitions of the SNN model and define what it means for an SNN to solve a task and define the task of agreement. In Section 3, we describe our SNN solving agreement; in Section 4, we show that the SNN is optimal; and in Section 5, we present our experimental results. We conclude in Section 6.

2. Preliminaries

2.1. Model

An SNN is modeled as a weighted directed graph, where neurons are represented as vertices and synapses as edges. The vertices of the graph are partitioned into three subsets—input, auxiliary, and output neurons. Input neurons have no incoming edges. The bias function assigns a real number to each auxiliary and output neuron. In this article, we consider networks with the same number n of input and output neurons.

Computation on an SNN is performed in rounds. The state (we also say the firing pattern) of the network at the end of round t, denoted S^t, is a map of the vertices to ${0, 1}$ . A neuron fires at time t if it is mapped to 1 in S^t. An input I (resp., output O) is an assignment of network 0s and 1s to the input (resp., output) neurons. We consider the case when the input is clamped, that is the firing pattern for the input neurons is the same in each round. If $S^{t} (u) = 1$ (neuron u fires in S^t), slightly abusing notation, we also write $u \in S^{t}$ .

The evolution of the network is a Markov process—the state at time $t + 1$ depends only on the state at time t. In each round, we use a stochastic activation function of neuron potential to calculate the firing pattern.

Let $w e i g h t (u, m)$ denote the weight of the edge between neurons u and m (edge weights can be zero or negative). The neuron potential of a non-input neuron m at time $t + 1$ is

The non-input neuron m fires at time $t + 1$ with probability $P (m^{t + 1} = 1) = σ (p o t^{t + 1} (m)) = \frac{1}{1 + e^{- p o t^{t + 1} (m)}}$

We call $σ$ the activation function of the neural network.

Notice that in our model, the activation function of a neuron does not depend on n. In contrast, Lynch et al. (2017a) defined the activation function as $σ (x) = 1 ∕ (1 + e^{- x ∕ λ})$ , where $λ$ can be a function of n. In particular, the proposed WTA network assumes $λ (n) = 1 ∕ (c_{1} log n)$ for some large c₁.

2.2. Tasks and agreement

A task associates inputs to outputs. Formally a task is defined as a tuple $(ℐ, O, f)$ , where $ℐ \subseteq {0, 1}^{n}$ is the set of input vectors, $O \subseteq {0, 1}^{n}$ is a set of output vectors, and $f : ℐ \to 2^{O}$ is the task specification, mapping each input vector to a set of output vectors.

We say that the network solves the task at time T if for every input $I \in ℐ$ there is some $t \leq T$ such that the network reaches a state $O^{t} \in f (I)$ and stays in that state (the network remains stable) for n rounds with high probability (we also write w.h.p.; Lynch et al., 2017b; recall that n is the number of inputs). More precisely, if $t' \in [t, t + n]$ , then $O^{t'} = O^{t}$ with probability $Ω (1 - 1 ∕ n^{α})$ for some constant $α$ .

In the task of binary agreement, $ℐ = {0, 1}^{n}$ , $O = {{0}^{n}, {1}^{n}}$ . For $x \in {0, 1}^{n}$ and $i \in {0, 1}$ , let $∥ x ∥_{i}$ denote the number of times i appears in x.

Informally, the task of agreement requires that the output neurons agree on the value of one of the input neurons. We say that O is an agreement state for a given input I if $O \in f (I)$ .

In the WTA task, $ℐ = {0, 1}^{n}$ , $O = {{0}^{n}} \cup {x \in {0, 1}^{n} | ∥ x ∥_{1} = 1}$ , and the output should elect exactly one volunteering neuron:

In the rest of the article, we consider tasks defined for all system sizes, that is, for each $n \in N$ , the task has an instance $(ℐ^{n}, O^{n}, f^{n})$ . Clearly, this is the case for the tasks of WTA and agreement.

3. Solving Agreement

An SNN that solves the binary agreement task is depicted in Figure 1. Every input neuron u_i is connected to a dedicated auxiliary neuron m_i, with a positive weight $2 W$ . In turn, each m_i is connected to all output neurons ${v_{1}, \dots, v_{n}}$ with negative weight $- 2 W$ . The output neurons form a complete graph, where each edge carries weight $2 W$ . In addition, each input neuron u_i is connected to a corresponding output neuron v_i with positive weight $2 W$ . The bias is $- W$ for every auxiliary neuron m_i and 0 for every output neuron v_i.

FIG. 1.

The network solving the agreement task.

Informally, every auxiliary neuron “negates” the corresponding input and inhibits the output neurons from firing. The negative weights on the outgoing synapses of auxiliary neurons ensure that, when a sufficiently large fraction of them are firing, the output neurons will stop firing. Otherwise, firing output neurons will reinforce the other output neurons, causing them to fire as well.

Informally, as the contribution to the potential from each neuron is constant, we need a linear number of auxiliary neurons: This is required to ensure that the probability of agreement does not drop as the number of output neurons increases. Indeed, as n grows, the auxiliary neurons must be able to compensate for more output neurons firing by reducing the potential. Without this, the network may get stuck at a state where all output neurons fire in each round, even if no input neurons fire.

3.1. Correctness

Now we show that the proposed SNN, indeed, solves the agreement task.

At time $t + 1$ , the potential of an auxiliary neuron m_i in our network is $p o t^{t + 1} (m_{i}) = u_{i} \cdot w e i g h t (u_{i}, m_{i}) - b i a s (m_{i}) = - W (2 u_{i} - 1)$

and the potential of an output neuron v_i is

Notice that $p o t^{t + 1} (m_{i})$ does not depend on t: -W if u_i fires and W if u_i does not fire.

Let us express W as follows: $W = ln \frac{1 - δ}{δ}$

where the parameter $0 < δ \leq \frac{1}{3}$ can be varied to obtain a probability of agreement and stability as high as necessary.

The following property of the activation function will be instrumental in comparing networks of different sizes.

Lemma 1. If $x \geq 2 W$ , we have:

Proof. Consider the expressions $σ (x) = \frac{1}{1 + e^{- x}} a n d$

The function $1 + e^{- x} - (1 + 4 e^{- 2 x} + 6 e^{- 4 x} + 4 e^{- 6 x} + e^{- 8 x})$ is positive for all $x \geq 2$ , which leads to the inequality

As $W > 1$ for any $δ$ , this inequality is true for any $x \geq 2 W > 2$ .

Lemma 2. For the described SNN with n input neurons, the expected value and the variance of the number of firing auxiliary neurons $A (t)$ are: $E [A (t)] = n (1 - δ) - c (1 - 2 δ) a n d$ $V a r (A (t)) = n (1 - δ) δ,$

where c is the number of firing input neurons.

Proof. Consider an input I, such that $∥ I ∥_{1} = c$ .

Let $A_{0} (t)$ (resp., $A_{1} (t)$ ) denote the number of firing auxiliary neurons that are connected to input neurons with state 0 (resp., 1).

Recall that the only incoming edge for an auxiliary neuron m_i is $(u_{i}, m_{i})$ and u_i is clamped (does not change its state). Therefore, the probability distribution of the state of m_i does not depend on t.

Then $A_{0} (t)$ is a binomial random variable $B (n - c, σ (W))$ and $A_{1} (t)$ is a binomial random variable $B (c, σ (- W))$ . Thus: $E [A (t)] = E [A_{0} (t) + A_{1} (t)] = (n - c) σ (W) + c σ (- W) = (n - c) (1 - δ) + c δ = n (1 - δ) - c (1 - 2 δ)$

As $A_{0} (t)$ and $A_{1} (t)$ are independent, the variance of $A (t)$ is:

$V a r (A (t)) = V a r (A_{0} (t) + A_{1} (t)) = (n - c) σ (W) (1 - σ (W)) + c σ (- W) (1 - σ (- W)) = n (1 - δ) δ$

We show first that the network, once it reaches an agreement state, stays in this state for at least n rounds with high probability.

Lemma 3. For the described SNN with n input neurons, the number of firing auxiliary neurons $A (t)$ is close to the mean with high probability, or formally: $P (| A (t) - E [A (t)] | \geq \sqrt{n}) \leq (1 - δ) δ$

Proof. This follows directly from Lemma 2 after applying Chebyshev's inequality.

$P (| A (t) - E [A (t)] | \geq \sqrt{n}) \leq \frac{V a r (A (t))}{{(\sqrt{n})}^{2}} = \frac{n (1 - δ) δ}{n} = (1 - δ) δ$

Theorem 4. After agreement, the SNN for $n \geq 8$ is stable for n rounds with high probability.

Proof. Take a network with n output neurons.

Case 1: At least half the input neurons are firing ( $c \geq \frac{n}{2}$ ) and at time t all output neurons fire ( $V_{n} (t) = n$ ).

At time $t + 1$ , the potential of an output neuron is $2 W (n - A (t))$ if its corresponding input is firing and $2 W (n - 1 - A (t))$ otherwise. By Lemma 3, the number of auxiliary neurons is $n - c - \sqrt{n} \leq A (t) \leq n - c + \sqrt{n}$ , with probability at least $1 - (1 - δ) δ$ . Then, for the potential we have: $p o t^{t + 1} \geq 2 W (n - 1 - (n - c + \sqrt{n})) = 2 W (c - 1 - \sqrt{n}) \geq 2 W (\frac{n}{2} - 1 - \sqrt{n})$

If we take $n \geq 8$ and use the fact that the potential is an integer multiple of $2 W$ , we get $p o t^{t + 1} \geq 2 W$ and probability for all outputs firing

Taking $n = 8$ , we can adjust $δ$ to get the probability that all output neurons fire for n rounds as high as we need. We will prove that as the number of input neurons n increases, the probability that all output neurons fire for n rounds also increases.

Take an SNN with $2 n$ input neurons. Then, $P (V^{2 n} (t + 1) = 2 n) \geq {(σ ((\frac{2 n}{2} - 1 - \sqrt{2 n}) 2 W))}^{2 n} = {(σ (2 (\frac{n}{2} - \frac{1}{2} - \sqrt{\frac{n}{2}}) \cdot 2 W))}^{2 n}$

Choosing $x = \frac{n}{2} - 1 - \sqrt{n}$ , we see the potential is more than $2 x 2 W$ . Using Lemma 1, we have

We take into account that a network with n outputs is stable for n rounds. ${(P (V^{2 n} (t + 1) = 2 n))}^{2 n} \geq {(σ (2 x \cdot 2 W))}^{4 n^{2}} > {(σ (x \cdot 2 W))}^{n^{2}} = {(P (V_{n} (t + 1) = n))}^{n}$

The function $σ^{n}$ is a monotone function of n. Thus, the probability for stability increases as n grows. Moreover, as n approaches infinity, this probability approaches 1: ${lim}_{n \to \infty} {(σ (x \cdot 2 W))}^{n^{2}} = 1$

Thus, the network is stable for n rounds, with high probability.

Case 2: At most, half the input neurons are firing ( $c \leq \frac{n}{2}$ ) and no output neurons fire ( $V_{n} (t) = 0$ ).

We make the following observation: In the constructed network, there is a symmetry between firing and non-firing neurons. If we invert the firing pattern (each firing neuron will become non-firing and vice versa), the potential of each non-input neuron will change the sign but preserve its magnitude. Let S^t be a firing pattern in round t, and let ${\bar{S}}^{t}$ denote the inversion of S^t. For $i = 0, 1$ , given state S^t (resp., ${\bar{S}}^{t}$ ), let $P_{m, i}$ (resp., ${\bar{P}}_{m, i}$ ) denote the probability that the state of a non-input neuron in round $t + 1$ is i.

Then, we have $P_{m, i} = {\bar{P}}_{m, 1 - i}$ , that is, the probability that a non-input neuron fires in the next round is equal to the probability of the same neuron not firing on the next round with the inverted firing pattern.

Given this observation, the proof for Case 2 is analogous.

Theorem 5. The described SNN solves the agreement problem for $n \geq 8$ .

Proof. Take a network with $n \geq 8$ input neurons. Consider the evolution of the network from arbitrary time t to time $t + 1$ . The potential of an output neuron is the sum of a subset of the weights of incoming edges: n edges with weight $2 W$ and n edges with weight $- 2 W$ . The potential is, thus, bounded by: $- 2 n W \leq p o t^{t + 1} \leq 2 n W$

The bounds imply a lower bound for the probabilities that all output neurons fire and that no output neurons fire. Note that for any choice of n, we have

Let us denote this bound by p. Notice that $p > 0$ .

Now, consider the evolution of the network from arbitrary time t to time $t + k$ for some integer k. Taking a geometric random variable with probability of success p, we obtain an upper bound for the expected time to reach agreement state. Moreover, the probability to not reach agreement in k rounds is at most (1-p)^k. For a sufficiently big k, this probability approaches 0. This shows that for any input, the network reaches agreement state almost surely.

By Theorem 4, once the network reaches agreement state, it will remain in that state for n rounds with high probability. This proves that the network solves the agreement problem.

3.1.1. Time complexity

In Section 5, we show that our SNN with n inputs converges to an agreement state in nearly constant time; we conjecture it to be $O (log n)$ . The underlying intuition is the following.

Consider an execution of our SNN. Let $A (t)$ and $V (t)$ denote the number of firing auxiliary and output neurons at time t, respectively. Let $D (t) = V (t) - A (t)$ . Notice that, by Lemma 2, $A (t)$ tends to stabilize on $n (1 - δ) - c (1 - 2 δ)$ . That is, $D (t)$ represents the major factor of how close the system is to the agreement state.

One can consider the evolution of $D (t)$ over time as a random walk. After some time, the value of D will become large enough (or small enough, depending on the input) so that the number of firing output neurons V increases (or decreases), with high probability, and this process is faster the larger n is. Our conjecture states, in a way, that the time needed for the absolute value of D to become large enough is logarithmic in n. In future work, we hope to prove the conjecture.

4. Lower Bound

We show that, under the biologically plausible assumption that neurons in the network do not have access to global network parameters (such as the size of the network), a particular class of problems defined in the SNN model, including agreement and leader election, requires $Ω (n)$ auxiliary neurons. More precisely, we consider networks in which: (1)

weights and biases are constant (independent of n);

(2)

activation as a function of the potential is independent of n;

Further, we consider networks that are size-independent, in the following sense. A network with n input neurons can be considered a composition of $n + 1$ subnetworks, respecting the following properties:

Each subnetwork has a constant (in n) number of neurons.

There are n identical subnetworks $L^{1}, L^{2}, \dots, L^{n}$ , each containing one input neuron, one output neuron, and a constant number of auxiliary neurons.

There is one fixed subnetwork M consisting only of auxiliary neurons that are not part of subnetworks Lⁱ described earlier.

Let m₀ be any neuron in M. Suppose i, j, and k are three distinct integers. Let $l_{0}^{i}$ and $l_{0}^{j}$ be “identical” neurons from Lⁱ and L^j, respectively, and let $l_{p}^{k}$ be any neuron from L^k. Then,

\begin{matrix} w e i g h t (l_{0}^{i}, m_{0}) = w e i g h t (l_{0}^{j}, m_{0}) \\ w e i g h t (m_{0}, l_{0}^{i}) = w e i g h t (m_{0}, l_{0}^{j}) \\ w e i g h t (l_{0}^{i}, l_{p}^{k}) = w e i g h t (l_{0}^{j}, l_{p}^{k}) \\ w e i g h t (l_{p}^{k}, l_{0}^{i}) = w e i g h t (l_{p}^{k}, l_{0}^{j}) \end{matrix}

In other words, the n identical subnetworks are indistinguishable.

A network with $n + 1$ input and output neurons can be constructed from the network with n neurons by adding a new subnetwork $L^{n + 1}$ , indistinguishable from Lⁱ, $i = 1, \dots, n$ .

Note that networks with these properties cannot have non-constant sublinear number of auxiliary neurons.

Size-independence is a biologically plausible property, as in a biological neural network each neuron can only be aware of its surroundings. A neuron does not “know” the size of the entire network, therefore its weights and activation cannot depend on n. In addition, we are interested in network properties at large scale. Special cases for specific network sizes do not make sense in this context. In the context of the problems we consider in this article, permuting the inputs should not affect the behavior of the network, which further motivates the symmetry assumptions.

Theorem 6. Let N be a size-independent stochastic SNN solving a task . Suppose that the task has a set of inputs (one input for each system size $i \in N$ ) and two constants, k and $ℓ$ such that for each $I_{i} \in ℐ^{i}$ :

(1) the number of firing neurons in I_i is at most k;

(2) for each $O \in f^{i} (I_{i})$ , the number of firing neurons in O is at most $ℓ$ .

Then, N has $Ω (n)$ auxiliary neurons.

Proof. The potential of any output neuron is the sum of weights to that neuron from firing input, auxiliary, and output neurons. $p o t (v_{i}) = \sum j u_{j} \cdot w e i g h t (u_{j}, v_{i}) + \sum j a_{j} \cdot w e i g h t (a_{j}, v_{i}) + \sum j v_{j} \cdot w e i g h t (v_{j}, v_{i})$

Note that from size-independence each output neuron is connected either to all other output neurons or to no other output neurons.

Notice that the only case when a size-independent network has a sub-linear number of auxiliary neurons is when its identical subnetworks $L^{1}, L^{2}, \dots, L^{n}$ have no auxiliary neurons. Suppose, by contradiction, that this is the case, that is, the only auxiliary neurons in the network are those that belong to the subnetwork M. Then, the contribution of the auxiliary neurons to the potential of an output neuron is also bounded ( $A_{m i n} \leq \sum j a_{j} \cdot w e i g h t (a_{j}, v_{i}) \leq A_{m a x}$ ).

Consider the set of inputs $ℐ = {I_{i}}_{i = 1}^{\infty}$ from the statement of the theorem. For the sequence $ℐ$ , the number of firing input neurons is bounded so their contribution to the potential from the input neurons is also bounded ( $U_{m i n} \leq \sum j u_{j} \cdot w e i g h t (u_{j}, v_{i}) \leq U_{m a x}$ ). Take the round after the network has converged. The number of corresponding output neurons firing is also constant, and, thus, the contribution to the potential from the output neurons is bounded ( $V_{m i n} \leq \sum j v_{j} \cdot w e i g h t (v_{j}, v_{i}) \leq V_{m a x}$ ). Therefore, the potential for all output neurons is bounded: $U_{m i n} + A_{m i n} + V_{m i n} \leq p o t (v_{i}) \leq U_{m a x} + A_{m a x} + V_{m a x}$

Let $p_{m i n} = σ (U_{m i n} + A_{m i n} + V_{m i n})$ and $p_{m a x} = σ (U_{m a x} + A_{m a x} + V_{m a x})$ be, respectively, the lower and upper bound for the probability of an output neuron firing—note that both bounds are constants. For the network to be stable, after agreement, the output must not change from one round to the next (with high probability). Let $V (t)$ be the number of output neurons that fired at time t. Then, we have an upper bound for the probability of stability:

For sufficiently large n, this probability is less than $\frac{1}{2}$ —a contradiction. Thus, the number of auxiliary neurons cannot be constant, that is, each subnetwork L_i, $i = 1, \dots, n$ , must contain at least one auxiliary neuron, which gives at least n auxiliary neurons in total.

Notice that the theorem applies to the tasks of agreement and WTA. In the agreement task, the sequence of inputs $ℐ = 0, 00, 000, \dots$ converges to output with 0 firing output neurons. In WTA, any convergent output contains exactly 1 firing output neuron—choosing the sequence of inputs $ℐ = 1, 10, 100, 1000, \dots$ shows that the theorem applies to this task too.

5. Simulation

To support our complexity claims, we ran a series of simulated runs of the network described in Section 3. The source code of the simulation (in C) is available at https://gitlab.com/martinkunev/agreement-in-spiking-neural-networks.

5.1. Implementation

As the network is size-independent, we do not have to maintain all $Θ (n^{2})$ edges in the system state in the memory. Instead, we store a single copy of the n identical subnetworks L_i since each such subnetwork has the same structure, which requires $Θ (n)$ memory. The edges are split into 2 groups: those internal to a subnetwork and those connecting subnetworks (external).

If the subnetworks L_i consist of k neurons each, at any given time there are $2^{k}$ possible firing patterns. Therefore, instead of storing the firing pattern for each value of i, it is sufficient to store only the number of subnetworks that have the given firing pattern. The firing pattern is then stored as an array of $2^{k}$ integers and in practice the value of k is small ( $k = 3$ for the network solving agreement: one input, one output, and one auxiliary neuron).

The essential part of the input is the number of firing input neurons. The same goes for the output. With this in mind, we design an algorithm to test the network.

Running the SNN for one round is performed by looping through the firing patterns—a firing pattern in this context is a subset of firing vertices in a subnetwork L_i. The calculation of potential is identical for all subnetworks with any given firing pattern. For each subnetwork, the firing pattern on the next round is determined stochastically. As an optimization, the potential due to external edges for each neuron is precalculated since it is common to all subnetworks. The resulting simulation is described in Algorithm 1.

Assuming the number of edges in one subnetwork L_i is $O (n)$ (which is true for the proposed network), this algorithm uses memory $O (n)$ and runs in time $O (n \cdot 2^{k})$ , which for a constant k becomes $O (n)$ . The parameter $δ$ determines the weights and the biases of the network.

Algorithm 1. Testing Algorithm
1: for $v e r t e x \in v e r t i c e s (L)$ do
2: $v e r t e x . p o t e x t e r n a l \leftarrow - b i a s$
3: for $e d g e \in e x t e r n a l e d g e s (L)$ do
4: $(f r o m, t o) \leftarrow e d g e$
5: for $s u b s e t \in s u b s e t s (v e r t i c e s (L))$ do
6: if $f r o m \in s u b s e t$ then
7: $t o . p o t e x t e r n a l \leftarrow p o t e x t e r n a l + w e i g h t (e d g e) < s u p > * < ∕ s u p > s u b n e t w o r k s c o u n t (s u b s e t)$
8: for $s u b s e t \in s u b s e t s (v e r t i c e s (L))$ do
9: for $v e r t e x \in v e r t i c e s (L)$ do
10: $v e r t e x . p o t \leftarrow v e r t e x . p o t e x t e r n a l$
11: for $e d g e \in i n t e r n a l e d g e s (L)$ do
12: $(f r o m, t o) \leftarrow e d g e$
13: if $f r o m \in s u b s e t$ then
14: $v e r t e x . p o t \leftarrow v e r t e x . p o t + w e i g h t (e d g e)$
15: for subnetworks_count(subset) times do
16: $f i r i n g \leftarrow c h o o s e f i r i n g s u b s e t (v e r t i c e s (L))$
17: increment $s u b n e t w o r k s c o u n t (f i r i n g)$ by 1

5.2. Benchmark

We performed tests with $δ = 0.1$ and $δ = 0.33$ for different values of n, in particular, for $2^{3}, 2^{4}, 2^{5}, \dots, 2^{20}$ . For each of these values of n, we measured the convergence time for different inputs. Here, we used 4 categories of inputs:

0 input neurons firing

$\frac{n}{2}$ input neurons firing

n input neurons firing

random number of firing input neurons (uniform distribution)

For every experiment, multiple iterations were run with the same input.

Handling large values of n raises several technical challenges. First, floating point numbers in C have limited precision and for big potentials, errors start accumulating while calculating the activation function. Second, while calculating whether a neuron fires, a random number generator is used to obtain a floating point number between 0 and 1 with uniform distribution. When the firing probability is very close to 0 or to 1, the random numbers must be generated with a very high precision to not skew the results. For these reasons, we chose to bound our experiments by $n = 2^{20}$ .

5.3. Results

Figures 2 and 3 depict convergence times of the network for $δ = 0.33$ and $δ = 0.1$ , respectively, whereas numeric values are given in Table 1. The green line represents the expected convergence time, and the blue area spans one standard deviation around the expected value. The results indicate that the average convergence time remains quasi-constant, regardless of the system size. The variance, however, decreases quickly with n.

FIG. 2.

Results of the tests for $δ = 0.33$ .

FIG. 3.

Results of the tests for $δ = 0.1$ .

Table 1.

Mean Convergence Time and Its Variance for 1024 Tests (256 Per Input Category) for Different Values of n

n	$E [T]$	$v a r (T)$
8	2.1475	0.864
16	2.0088	0.3290
32	2.0059	0.0957
64	2.0107	0.0438
128	2.0088	0.0087
256	2.0049	0.0049
512	2.0029	0.0029
1024	2.002	0.0019
2048	2.0	0.0
4096	2.0	0.0
8192	2.001	0.001
16,384	2.0	0.0
32,768	2.0	0.0
65,536	2.0	0.0
131,072	2.0	0.0
262,144	2.0	0.0
524,288	2.0	0.0
1,048,576	2.0	0.0

n	$E [T]$	$v a r (T)$
8	2.0997	0.9159
16	1.7813	0.3174
32	1.7578	0.2187
64	1.751	0.2007
128	1.75	0.1895
256	1.7588	0.1830
512	1.7695	0.1774
1024	1.7900	0.1678
2048	1.8184	0.1506
4096	1.8691	0.1137
8192	1.9229	0.0712
16,384	1.9805	0.0191
32,768	1.9980	0.0019
65,536	2.0	0.0
131,072	2.0	0.0
262,144	2.0	0.0
524,288	2.0	0.0
1,048,576	2.0	0.0

Left: $δ = 0.33$ ; Right: $δ = 0.1$ .

Comparing the results for the two values of $δ$ , we see that reducing $δ$ slightly reduces the expected convergence time and increases its variance for smaller n. Altogether, the results suggest that $E [T]$ grows very slowly with n. In fact, as we conjectured in Section 3, we expect the (tight) upper bound for $E [T]$ to be $O (log n)$ .

6. Conclusion

We have shown that solving common problems such as agreement and WTA requires $Ω (n)$ auxiliary neurons in the biologically plausible model of size-independent SNNs. Compared with the models proposed earlier, for example, the SNN solving the WTA problem (Lynch et al., 2017a), our solution does not require individual neurons to use knowledge of the network size in their activation functions. Neither does it impose restrictions on the connectivity between output neurons. Earlier models often assume specific initial network states and/or do not show that the network is self-stabilizing, that is, converges from an arbitrary starting state, which appears to be necessary in a biological system.

The ideas described in this article can be further developed for solving other problems. These include multi-valued agreement (where each input can have more than two possible values) and set agreement (where the output is restricted to any element of a subset of given size, instead of a single value). It is also extremely interesting to determine conditions on the connectivity, for example, expressed as the number of synapses, necessary and sufficient to solve a given task.

Footnotes

Acknowledgments

The first version of article this has been presented at the 8th workshop on Biological Distributed Algorithms (BDA). The authors would like to thank the anonymous reviewers of BDA and JCB for their constructive reviews.

Author Disclosure Statement

The authors declare they have no competing financial interests.

Funding Information

The internship of Martin Kunev has been financially supported by the Department of Computer Science and Networking (INFRES) of Télécom Paris, Institut Polytechnique de Paris.

References

Barlow

H.B.

1961. Possible principles underlying the transformations of sensory messages. In Rosenblith, W.A. (ed.): Sensory Communication, 217–234. The MIT Press, Cambridge, Massachusetts, USA.

Gerstner

, and Kistler

2002. Spiking Neuron Models: Single Neurons, Populations, Plasticity. Cambridge University Press, Cambridge, Massachusetts, USA.

Goldman-Rakic

P.S.

1995. Cellular basis of working memory. Neuron. 14, 477–485.

Hubel

D.H.

, and Wiesel

T.N.

1962. Receptive fields, binocular interaction and functional architecture in the cat's visual cortex. J. Physiol. 160, 106–154.

Kandel

E.R.

, Schwartz

J.H.

, and Jessell

T.M.

1991. Principles of Neural Science, 3rd edition. Elsevier, New York, NY, USA.

Lynch

, and Musco

2018. A basic compositional model for spiking neural networks. arXiv, preprint, arXiv: 1808.03884.

Lynch

, Musco

, and Parter

2017a. Spiking neural networks: An algorithmic perspective (extended abstract). 2017. Available at: https://groups.csail.mit.edu/tds/papers/Musco/neuralBda.pdf Last viewed on March 15, 2022.

Lynch

N.A.

, Musco

, and Parter

2017b. Computational tradeoffs in biological neural networks: Self-stabilizing winner-take-all networks, 15:1–15:44. In Papadimitriou, C.H., ed. 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9–11, 2017, Berkeley, CA, USA. Volume 67 of LIPIcs. Schloss Dagstuhl—Leibniz-Zentrum für Informatik.

Mountcastle

V.B.

1957. Modality and topographic properties of single neurons of cat's somatic sensory cortex. J. Neurophysiol. 20, 408–434.

10.

Shriki

, Hansel

, and Sompolinsky

2003. Rate models for conductance-based cortical neuronal networks. Neural Computat. 15, 1809–1841.

11.

, Chia-Jung

, and Lynch

2019. Spike-based winner-take-all computation: Fundamental limits and order-optimal circuits. Neur. Comput. 31, 2523–2561.