Graph rules for recurrent neural network dynamics: extended version

Carina Curto¹ and Katherine Morrison²
¹The Pennsylvania State University ²The University of Northern Colorado
January 29 2023

\@starttoc

toc

1 Introduction

Neurons in the brain are constantly flickering with activity, which can be spontaneous or in response to stimuli [Luczak-Neuron]. Because of positive feedback loops and the potential for runaway excitation, real neural networks often possess an abundance of inhibition that serves to shape and stabilize the dynamics [Yuste-inhibition, Karnani-inhibition, Yuste-CPG]. The excitatory neurons in such networks exhibit intricate patterns of connectivity, whose structure controls the allowed patterns of activity. A central question in neuroscience is thus: how does network connectivity shape dynamics?

For a given model, this question becomes a mathematical challenge. The goal is to develop a theory that directly relates properties of a nonlinear dynamical system to its underlying graph. Such a theory can provide insights and hypotheses about how network connectivity constrains activity in real brains. It also opens up new possibilities for modeling neural phenomena in a mathematically tractable way.

Here we describe a class of inhibition-dominated neural networks corresponding to directed graphs, and introduce some of the theory that has been developed to study them. The heart of the theory is a set of parameter-independent graph rules that enables us to directly predict features of the dynamics from combinatorial properties of the graph. Specifically, graph rules allow us to constrain, and in some cases fully determine, the collection of stable and unstable fixed points of a network based solely on graph structure.

Stable fixed points are themselves static attractors of the network, and have long been used as a model of stored memory patterns [Hopfield1982, Hopfield1984]. In contrast, unstable fixed points have been shown to play an important role in shaping dynamic (non-static) attractors, such as limit cycles [core-motifs]. By understanding the fixed points of simple networks, and how they relate to the underlying architecture, we can gain valuable insight into the high-dimensional nonlinear dynamics of neurons in the brain.

For more complex architectures, built from smaller component subgraphs, we present a series of gluing rules that allow us to determine all fixed points of the network by gluing together those of the components. These gluing rules are reminiscent of sheaf-theoretic constructions, with fixed points playing the role of sections over subnetworks.

First, we review some basics of recurrent neural networks and a bit of historical context.

Basic network setup.

A recurrent neural network is a directed graph $G$ together with a prescription for the dynamics on the vertices, which represent neurons (see Figure 1A). To each vertex $i$ we associate a function $x_{i}(t)$ that tracks the activity level of neuron $i$ as it evolves in time. To each ordered pair of vertices $(i,j)$ we assign a weight, $W_{ij}$ , governing the strength of the influence of neuron $j$ on neuron $i$ . In principle, there can be a nonzero weight between any two nodes, with the graph $G$ providing constraints on the allowed values $W_{ij}$ , depending on the specifics of the model.

Refer to caption — Figure 1: (A) Recurrent network setup. (B) A Ramón y Cajal drawing of real cortical neurons.

The dynamics often take the form of a system of ODEs, called a firing rate model [Dayan-Abbott, ErmentroutTerman, AppendixE]:

	$\displaystyle\tau_{i}\dfrac{dx_{i}}{dt}$	$\displaystyle=$	$\displaystyle-x_{i}+\varphi\left(\sum_{j=1}^{n}W_{ij}x_{j}+b_{i}\right),$
		$\displaystyle=$	$\displaystyle-x_{i}+\varphi(y_{i}),$

for $i=1,\ldots,n.$ The various terms in the equation are illustrated in Figure 1, and can be thought of as follows:

•

$x_{i}=x_{i}(t)$ is the firing rate of a single neuron $i$ (or the average activity of a subpopulation of neurons);
•

$\tau_{i}$ is the “leak” timescale, governing how quickly a neuron’s activity exponentially decays to zero in the absence of external or recurrent input;
•

$W$ is a real-valued matrix of synaptic interaction strengths, with $W_{ij}$ representing the strength of the connection from neuron $j$ to neuron $i$ ;
•

$b_{i}=b_{i}(t)$ is a real-valued external input to neuron $i$ that may or may not vary with time;
•

$y_{i}=y_{i}(t)=\sum_{j=1}^{n}W_{ij}x_{j}(t)+b_{i}(t)$ is the total input to neuron $i$ as a function of time; and
•

$\varphi:\mathbb{R}\to\mathbb{R}$ is a nonlinear, but typically monotone increasing function.

Of particular importance for this article is the family of threshold-linear networks (TLNs). In this case, the nonlinearity is chosen to be the popular threshold-linear (or ReLU) function,

\varphi(y)=[y]_{+}=\max\{0,y\}.\vspace{-.05in}

TLNs are common firing rate models that have been used in computational neuroscience for decades [AppendixE, Tsodyks-JN-1997, Seung-Nature, Fitzgerald2022]. The use of threshold-linear units in neural modeling dates back at least to 1958 [Hartline-Ratliff-1958]. In the last 20 years, TLNs have also been shown to be surprisingly tractable mathematically [XieHahnSeung, HahnSeungSlotine, net-encoding, pattern-completion, CTLN-preprint, book-chapter, fp-paper, stable-fp-paper, seq-attractors], though much of the theory remains under-developed. We are especially interested in competitive or inhibition-dominated TLNs, where the $W$ matrix is non-positive so the effective interaction between any pair of neurons is inhibitory. In this case, the activity remains bounded despite the lack of saturation in the nonlinearity [CTLN-preprint]. These networks produce complex nonlinear dynamics and can possess a remarkable variety of attractors [CTLN-preprint, book-chapter, seq-attractors, core-motifs].

Firing rate models of the form (1) are examples of recurrent networks because the $W$ matrix allows for all pairwise interactions, and there is no constraint that the architecture (i.e., the underlying graph $G$ ) be feedforward. Unlike deep neural networks, which can be thought of as classifiers implementing a clustering function, recurrent networks are primarily thought of as dynamical systems. And the main purpose of these networks is to model the dynamics of neural activity in the brain. The central question is thus:

Question 1.

Given a firing rate model defined by (1) with network parameters $(W,b)$ and underlying graph $G$ , what are the emergent network dynamics? What can we say about the dynamics from knowledge of $G$ alone?

We are particularly interested in understanding the attractors of such a network, including both stable fixed points and dynamic attractors such as limit cycles. The attractors are important because they comprise the set of possible asymptotic behaviors of the network in response to different inputs or initial conditions (see Figure 2).

Note that Question 1 is posed for a fixed connectivity matrix $W$ , but of course $W$ can change over time (e.g., as a result of learning or training of the network). Here we restrict ourselves to considering constant $W$ matrices; this allows us to focus on understanding network dynamics on a fast timescale, assuming slowly varying synaptic weights. Understanding the dynamics associated to changing $W$ is an important topic, currently beyond the scope of this work.

Historical interlude: memories as attractors.

Attractor neural networks became popular in the 1980s as models of associative memory encoding and retrieval. The best-known example from that era is the Hopfield model [Hopfield1982, Hopfield1984], originally conceived as a variant on the Ising model from statistical mechanics. In the Hopfield model, the neurons can be in one of two states, $s_{i}\in\{\pm 1\}$ , and the activity evolves according to the discrete time update rule:

s_{i}(t+1)=\operatorname{sgn}\left(\sum_{j=1}^{n}W_{ij}s_{j}(t)-\theta_{i}\right).

Hopfield’s famous 1982 result is that the dynamics are guaranteed to converge to a stable fixed point, provided the interaction matrix $W$ is symmetric: that is, $W_{ij}=W_{ji}$ for every $i,j\in\{1,\ldots,n\}$ . Specifically, he showed that the “energy” function,

E=-\dfrac{1}{2}\sum_{i,j}W_{ij}s_{i}s_{j}+\sum_{i}\theta_{i}s_{i},

decreases along trajectories of the dynamics, and thus acts as a Lyapunov function [Hopfield1982]. The stable fixed points are local minima of the energy landscape (Figure 2A). A stronger, more general convergence result for competitive neural networks was shown in [CohenGrossberg1983].

These fixed points are the only attractors of the network, and they represent the set of memories encoded in the network. Hopfield networks perform a kind of pattern completion: given an initial condition $s(0)$ , the activity evolves until it converges to one of multiple stored patterns in the network. If, for example, the individual neurons store black and white pixel values, this process could input a corrupted image and recover the original image, provided it had previously been stored as a stable fixed point in the network by appropriately selecting the weights of the $W$ matrix. The novelty at the time was the nonlinear phenomenon of multistability: namely, that the network could encode many such stable equilibria and thus maintain an entire catalogue of stored memory patterns. The key to Hopfield’s convergence result was the requirement that $W$ be a symmetric interaction matrix. Although this was known to be an unrealistic assumption for real (biological) neural networks, it was considered a tolerable price to pay for guaranteed convergence. One did not want an associative memory network that wandered the state space indefinitely without ever recalling a definite pattern.

Twenty years later, Hahnloser, Seung, and others followed up and proved a similar convergence result in the case of symmetric inhibitory threshold-linear networks [HahnSeungSlotine]. Specifically, they found a Lyapunov-like function

L=\dfrac{1}{2}x^{T}(I-W)x-b^{T}x,

following the notation in (1) with $\varphi(y)=[y]_{+}$ . For fixed $b$ , it can easily be shown that $L$ is strictly decreasing along trajectories of the TLN dynamics, and minima of $L$ correspond to steady states – provided $W$ is symmetric and $I-W$ is copositive [HahnSeungSlotine, Theorem 1]. More results on the collections of stable fixed points that can be simultaneously encoded in a symmetric TLN can be found in [flex-memory, net-encoding, pattern-completion], including some unexpected connections to Cayley-Menger determinants and classical distance geometry.

In all of this work, stable fixed points have served as the model for encoded memories. Indeed, these are the only types of attractors that arise for symmetric Hopfield networks or symmetric TLNs. Whether or not guaranteed convergence to stable fixed points is desirable, however, is a matter of perspective. For a network whose job it is to perform pattern completion or classification for static images (or codewords), as in the classical Hopfield model, this is exactly what one wants. But it is also important to consider memories that are temporal in nature, such as sequences and other dynamic patterns of activity. Sequential activity, as observed in central pattern generator circuits (CPGs) and spontaneous activity in hippocampus and cortex, is more naturally modeled by dynamic attractors such as limit cycles. This requires shifting attention to the asymmetric case, in order to be able to encode attractors that are not stable fixed points (Figure 2B).

Beyond stable fixed points.

When the symmetry assumption is removed, TLNs can support a rich variety of dynamic attractors such as limit cycles, quasiperiodic attractors, and even strange (chaotic) attractors. Indeed, this richness can already be observed in a special class of TLNs called combinatorial threshold-linear networks (CTLNs), introduced in Section 3. These networks are defined from directed graphs, and the dynamics are almost entirely determined by the graph structure. A striking feature of CTLNs is that the dynamics are shaped not only by the stable fixed points, but also the unstable fixed points. In particular, we have observed a direct correspondence between certain types of unstable fixed points and dynamic attractors (see Figure 3) [core-motifs]. This is reviewed in Section 4.

Despite exhibiting complex, high-dimensional, nonlinear dynamics, recent work has shown that TLNs – and especially CTLNs – are surprisingly tractable mathematically. Motivated by the relationship between fixed points and attractors, a great deal of progress has been made on the problem of relating fixed point structure to network architecture. In the case of CTLNs, this has resulted in a series of graph rules: theorems that allow us to rule in and rule out potential fixed points based purely on the structure of the underlying graph [fp-paper, book-chapter, seq-attractors]. In Section 5, we give a novel exposition of graph rules, and introduce several elementary graph rules from which the others can be derived.

Inhibition-dominated TLNs and CTLNs also display a remarkable degree of modularity. Namely, attractors associated to smaller networks can be embedded in larger ones with minimal distortion [core-motifs]. This is likely a consequence of the high levels of background inhibition: it serves to stabilize and preserve local properties of the dynamics. These networks also exhibit a kind of compositionality, wherein fixed points and attractors of subnetworks can be effectively “glued” together into fixed points and attractors of a larger network. These local-to-global relationships are given by a series of theorems we call gluing rules, given in Section 6.

2 TLNs and hyperplane arrangements

For firing rate models with threshold-nonlinearity $\varphi(y)=[y]_{+}=\max\{0,y\},$ the network equations (1) become

	$\displaystyle\dfrac{dx_{i}}{dt}$	$\displaystyle=$	$\displaystyle-x_{i}+\left[\sum_{j=1}^{n}W_{ij}x_{j}+b_{i}\right]_{+}$
		$\displaystyle=$	$\displaystyle-x_{i}+[y_{i}]_{+},$

for $i=1,\ldots,n.$ We also assume $W_{ii}=0$ for each $i$ . Note that the leak timescales have been set to $\tau_{i}=1$ for all $i$ . We thus measure time in units of this timescale.

For constant $W$ matrix and input vector $b$ , the equations

y_{i}=\sum_{j=1}^{n}W_{ij}x_{j}+b_{i}=0,

define a hyperplane arrangement $\mathcal{H}=\mathcal{H}(W,b)=\{H_{1},\ldots,H_{n}\}$ in $\mathbb{R}^{n}$ . The $i$ -th hyperplane $H_{i}$ is defined by $y_{i}=\vec{n}_{i}\cdot x+b_{i}=0$ , with normal vector $\vec{n}_{i}=(W_{i1},\ldots,W_{in}),$ population activity vector $x=(x_{1},\ldots,x_{n})$ , and affine shift $b_{i}$ . If $W_{ij}\neq 0$ , then $H_{i}$ intersects the $j$ -th coordinate axis at the point $x_{j}=-b_{i}/W_{ij}$ . $H_{i}$ is parallel to the $i$ -th axis.

The hyperplanes $\mathcal{H}$ partition the positive orthant $\mathbb{R}^{n}_{\geq 0}$ into chambers. Within the interior of any chamber, each point $x$ is on the plus or minus side of each hyperplane $H_{i}$ . The equations thus reduce to a linear system of ODEs, with the equation for each $i=1,\ldots,n$ being either

\dfrac{dx_{i}}{dt}=-x_{i}+y_{i}=-x_{i}+\sum_{j=1}^{n}W_{ij}x_{j}+b_{i},\text{ if }y_{i}>0,

\dfrac{dx_{i}}{dt}=-x_{i},\text{ if }y_{i}\leq 0.

In particular, TLNs are piecewise-linear dynamical systems with a different linear system, $L_{\sigma}$ , governing the dynamics in each chamber [CTLN-preprint].

A fixed point of a TLN (2) is a point $x^{*}\in\mathbb{R}^{n}$ that satisfies $dx_{i}/dt|_{x=x^{*}}=0$ for each $i\in\{1,\ldots,n\}$ . In particular, we must have

x_{i}^{*}=[y_{i}^{*}]_{+}\text{ for all }i=1,\ldots,n,

(3)

where $y_{i}^{*}$ is $y_{i}$ evaluated at the fixed point. We typically assume a nondegeneracy condition on $(W,b)$ [fp-paper, CTLN-preprint], which guarantees that each linear system is nondegenerate and has a single fixed point. This fixed point may or may not lie within the chamber where its corresponding linear system applies. The fixed points of the TLN are precisely the fixed points of the linear systems that lie within their respective chambers.

Figure 4 illustrates the hyperplanes and chambers for a TLN with $n=2$ . Each chamber, denoted as a region $R_{\sigma}$ , has its own linear system of ODEs, $L_{\sigma},$ for $\sigma=\emptyset,\{1\},\{2\},$ or $\{1,2\}$ . The fixed point corresponding to each linear system is denoted by $x^{*}$ , in matching color. Note that only chamber $R_{\{2\}}$ contains its own fixed point (in red). This fixed point, $x^{*}=[0,b_{2}]^{T}$ , is thus the only fixed point of the TLN.

Figure 5 shows an example of a TLN on $n=3$ neurons. The $W$ matrix is constructed from a $3$ -cycle graph and $b_{i}=\theta=1$ for each $i$ . The dynamics fall into a limit cycle where the neurons fire in a repeating sequence that follows the arrows of the graph. This time, the TLN equations define a hyperplane arrangement in $\mathbb{R}^{3}$ , again with each hyperplane $H_{i}$ defined by $y_{i}=0$ (Figure 5C). An initial condition near the unstable fixed point in the all + chamber (where $y_{i}>0$ for each $i$ ) spirals out and converges to a limit cycle that passes through four distinct chambers. Note that the threshold nonlinearity is critical for the model to produce nonlinear behavior such as limit cycles; without it, the system would be linear. It is, nonetheless, nontrivial to prove that the limit cycle shown in Figure 5 exists. A recent proof was given for a special family of TLNs constructed from any $k$ -cycle graph [Horacio-paper].

The set of all fixed points $\boldsymbol{\operatorname{FP}(W,b)}$ .

A central object that is useful for understanding the dynamics of TLNs is the collection of all fixed points of the network, both stable and unstable. The support of a fixed point $x^{*}\in\mathbb{R}^{n}$ is the subset of active neurons,

\operatorname{supp}{x^{*}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\{i\mid x^{*}_{i}>0\}.\vspace{-.075in}

Our nondegeneracy condition (that is generically satisfied) guarantees we can have at most one fixed point per chamber of the hyperplane arrangement $\mathcal{H}(W,b)$ , and thus at most one fixed point per support. We can thus label all the fixed points of a given network by their supports:

	$\displaystyle\operatorname{FP}(W,b)$	$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}$	$\displaystyle\{\sigma\subseteq[n]\mid\sigma=\operatorname{supp}{x^{*}},\text{ for some }$		(4)
	$\displaystyle\text{fixed pt }x^{*}\text{ of the TLN }(W,b)\},$

where

[n]\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\{1,\ldots,n\}.

For each support $\sigma\in\operatorname{FP}(W,b)$ , the fixed point itself is easily recovered. Outside the support, $x_{i}^{*}=0$ for all $i\not\in\sigma$ . Within the support, $x^{*}$ is given by:

x_{\sigma}^{*}=(I-W_{\sigma})^{-1}b_{\sigma}.\vspace{-.075in}

Here $x_{\sigma}^{*}$ and $b_{\sigma}$ are the column vectors obtained by restricting $x^{*}$ and $b$ to the indices in $\sigma$ , and $W_{\sigma}$ is the induced principal submatrix obtained by restricting rows and columns of $W$ to $\sigma$ .

From (3), we see that a fixed point with $\operatorname{supp}{x^{*}}=\sigma$ must satisfy the “on-neuron” conditions, $y_{i}^{*}>0$ for all $i\in\sigma$ , as well as the “off-neuron” conditions, $y_{k}^{*}\leq 0$ for all $k\notin\sigma$ , to ensure that $x_{i}^{*}>0$ for each $i\in\sigma$ and $x_{k}^{*}=0$ for each $k\notin\sigma$ . Equivalently, these conditions guarantee that the fixed point $x^{*}$ of $L_{\sigma}$ lies inside its corresponding chamber, $R_{\sigma}.$ Note that for such a fixed point, the values $x_{i}^{*}$ for $i\in\sigma$ depend only on the restricted subnetwork $(W_{\sigma},b_{\sigma})$ . Therefore, the on-neuron conditions for $x^{*}$ in $(W,b)$ are satisfied if and only if they hold in $(W_{\sigma},b_{\sigma})$ . Since the off-neuron conditions are trivially satisfied in $(W_{\sigma},b_{\sigma})$ , it follows that $\sigma\in\operatorname{FP}(W_{\sigma},b_{\sigma})$ is a necessary condition for $\sigma\in\operatorname{FP}(W,b)$ . It is not, however, sufficient, as the off-neuron conditions may fail in the larger network. Satisfying all the on- and off-neuron conditions, however, is both necessary and sufficient to guarantee $\sigma\in\operatorname{FP}(G)$ [book-chapter, fp-paper].

Conveniently, the off-neuron conditions are independent and can be checked one neuron at a time. Thus,

\sigma\in\operatorname{FP}(W,b)\Leftrightarrow\sigma\in\operatorname{FP}(W_{\sigma\cup k},b_{\sigma\cup k})\text{ for all }k\notin\sigma.\vspace{-.05in}

When $\sigma\in\operatorname{FP}(W_{\sigma},b_{\sigma})$ satisfies all the off-neuron conditions, so that $\sigma\in\operatorname{FP}(W,b)$ , we say that $\sigma$ survives to the larger network; otherwise, we say $\sigma$ dies.

The fixed point corresponding to $\sigma\in\operatorname{FP}(W,b)$ is stable if and only if all eigenvalues of $-I+W_{\sigma}$ have negative real part. For competitive (or inhibition-dominated) TLNs, all fixed points – whether stable or unstable – have a stable manifold. This is because competitive TLNs have $W_{ij}\leq 0$ for all $i,j\in[n]$ . Applying the Perron-Frobenius theorem to $-I+W_{\sigma}$ , we see that the largest magnitude eigenvalue is guaranteed to be real and negative. The corresponding eigenvector provides an attracting direction into the fixed point. Combining this observation with the nondegeneracy condition reveals that the unstable fixed points are all hyperbolic (i.e., saddle points).

3 Combinatorial threshold-linear
networks

Combinatorial threshold-linear networks (CTLNs) are a special case of competitive (or inhibition-dominated) TLNs, with the same threshold nonlinearity, that were first introduced in [CTLN-preprint, book-chapter]. What makes CTLNs special is that we restrict to having only two values for the connection strengths $W_{ij}$ , for $i\neq j$ . These are obtained as follows from a directed graph $G$ , where $j\to i$ indicates that there is an edge from $j$ to $i$ and $j\not\to i$ indicates that there is no such edge:

W_{ij}=\left\{\begin{array}[]{ll}\phantom{-}0&\text{ if }i=j,\\ -1+\varepsilon&\text{ if }j\rightarrow i\text{ in }G,\\ -1-\delta&\text{ if }j\not\rightarrow i\text{ in }G.\end{array}\right.\quad\quad\quad\quad

(5)

Additionally, CTLNs typically have a constant external input $b_{i}=\theta$ for all $i$ in order to ensure the dynamics are internally generated rather than inherited from a changing or spatially heterogeneous input.

A CTLN is thus completely specified by the choice of a graph $G$ , together with three real parameters: $\varepsilon,\delta,$ and $\theta$ . We additionally require that $\delta>0$ , $\theta>0$ , and $0<\varepsilon<\dfrac{\delta}{\delta+1}$ . When these conditions are met, we say the parameters are within the legal range. Note that the upper bound on $\varepsilon$ implies $\varepsilon<1$ , and so the $W$ matrix is always effectively inhibitory. For fixed parameters, only the graph $G$ varies between networks. The network in Figure 5 is a CTLN with the standard parameters $\varepsilon=0.25$ , $\delta=0.5$ , and $\theta=1$ .

We interpret a CTLN as modeling a network of $n$ excitatory neurons, whose net interactions are effectively inhibitory due to a strong global inhibition (Figure 6). When $j\not\to i$ , we say $j$ strongly inhibits $i$ ; when $j\to i$ , we say $j$ weakly inhibits $i$ . The weak inhibition is thought of as the sum of an excitatory synaptic connection and the background inhibition. Note that because $-1-\delta<-1<-1+\varepsilon$ , when $j\not\to i$ , neuron $j$ inhibits $i$ more than it inhibits itself via its leak term; when $j\to i$ , neuron $j$ inhibits $i$ less than it inhibits itself. These differences in inhibition strength cause the activity to follow the arrows of the graph.

The set of fixed point supports of a CTLN with graph $G$ is denoted as:

	$\displaystyle\operatorname{FP}(G,\varepsilon,\delta)$	$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}$	$\displaystyle\{\sigma\subseteq[n]\mid\sigma=\operatorname{supp}{x^{*}}\text{ for some }$
			$\displaystyle\text{fixed pt }x^{*}\text{ of the associated CTLN}\}.$

$\operatorname{FP}(G,\varepsilon,\delta)$ is precisely $\operatorname{FP}(W,b)$ , where $W$ and $b$ are specified by a CTLN with graph $G$ and parameters $\varepsilon$ and $\delta$ . Note that $\operatorname{FP}(G,\varepsilon,\delta)$ is independent of $\theta$ , provided $\theta$ is constant across neurons as in a CTLN. It is also frequently independent of $\varepsilon$ and $\delta$ . For this reason we often refer to it as $\operatorname{FP}(G)$ , especially when a fixed choice of $\varepsilon$ and $\delta$ is understood.

The legal range condition, $\varepsilon<\dfrac{\delta}{\delta+1},$ is motivated by a theorem in [CTLN-preprint]. It ensures that single directed edges $i\to j$ are not allowed to support stable fixed points $\{i,j\}\in\operatorname{FP}(G,\varepsilon,\delta)$ . This allows us to prove the following theorem connecting a certain graph structure to the absence of stable fixed points. Note that a graph is oriented if for any pair of nodes, $i\to j$ implies $j\not\to i$ (i.e., there are no bidirectional edges). A sink is a node with no outgoing edges.

Theorem 3.1.

[CTLN-preprint, Theorem 2.4] Let $G$ be an oriented graph with no sinks. Then for any parameters $\varepsilon,\delta,\theta$ in the legal range, the associated CTLN has no stable fixed points. Moreover, the activity is bounded.

The graph in Figure 5A is an oriented graph with no sinks. It has a single fixed point, $\operatorname{FP}(G)=\{123\}$ , irrespective of the parameters (note that we use “ $123$ ” as shorthand for the set $\{1,2,3\}$ ). This fixed point is unstable and the dynamics converge to a limit cycle (Figure 5C).

Even when there are no stable fixed points, the dynamics of a CTLN are always bounded [CTLN-preprint]. In the limit as $t\to\infty$ , we can bound the total population activity as a function of the parameters $\varepsilon,\delta,$ and $\theta$ :

\dfrac{\theta}{1+\delta}\leq\sum_{i=1}^{n}x_{i}\leq\dfrac{\theta}{1-\varepsilon}.

(6)

In simulations, we observe a rapid convergence to this regime. Figure 7 depicts four solutions for the same CTLN on $n=100$ neurons. The graph $G$ was generated as a directed Erdos-Renyi random graph with edge probability $p=0.2$ ; note that it is not an oriented graph. Since the network is deterministic, the only difference between simulations is the initial conditions. While panel A appears to show chaotic activity, the solutions in panels B, C and D all settle into a fixed point or a limit cycle within the allotted time frame. The long transient of panel B is especially striking: around $t=200$ , the activity appears as though it will fall into the same limit cycle from panel D, but then escapes into another period of chaotic-looking dynamics before abruptly converging to a stable fixed point. In all cases, the total population activity rapidly converges to lie within the bounds given in (6), depicted in gray.

Fun examples.

Despite their simplicity, CTLNs display a rich variety of nonlinear dynamics. Even very small networks can exhibit interesting attractors with unexpected properties. Theorem 3.1 tells us that one way to guarantee that a network will produce dynamic – as opposed to static – attractors is to choose $G$ to be an oriented graph with no sinks. The following examples are of this type.

The Gaudi attractor. Figure 8 shows two solutions to a CTLN for a cyclically symmetric tournament¹¹1A tournament is a directed graph in which every pair of nodes has exactly one (directed) edge between them. graph on $n=5$ nodes. For some initial conditions, the solutions converge to a somewhat boring limit cycle with the firing rates $x_{1}(t),\ldots,x_{5}(t)$ all peaking in the expected sequence, $12345$ (bottom middle). For a different set of initial conditions, however, the solution converges to the beautiful and unusual attractor displayed at the top.

Symmetry and synchrony. Because the pattern of weights in a CTLN is completely determined by the graph $G$ , any symmetry of the graph necessarily translates to a symmetry of the differential equations, and hence of the vector field. It follows that the automorphism group of $G$ also acts on the set of all attractors, which must respect the symmetry. For example, in the cyclically symmetric tournament of Figure 8, both the Gaudi attractor and the “boring” limit cycle below it are invariant under the cyclic permutation $(12345)$ : the solution is preserved up to a time translation.

Another way for symmetry to manifest itself in an attractor is via synchrony. The network in Figure 9A depicts a CTLN with a graph on $n=5$ nodes that has a nontrivial automorphism group $C_{3}$ , cyclically permuting the nodes $2,3$ and $4$ . In the corresponding attractor, the neurons $2,3,4$ perfectly synchronize as the solution settles into the limit cycle. Notice, however, what happens for the network in Figure 9B. In this case, the limit cycle looks very similar to the one in A, with the same synchrony among neurons $2,3$ and $4$ . However, the graph is missing the $4\to 5$ edge, and so the graph has no nontrivial automorphisms. We refer to this phenomenon as surprise symmetry.

On the flip side, a network with graph symmetry may have multiple attractors that are exchanged by the group action, but do not individually respect the symmetry. This is the more familiar scenario of spontaneous symmetry breaking.

Emergent sequences. One of the most reliable properties of CTLNs is the tendency of neurons to fire in sequence. Although we have seen examples of synchrony, the global inhibition promotes competitive dynamics wherein only one or a few neurons reach their peak firing rates at the same time. The sequences may be intuitive, as in the networks of Figures 8 and 9, following obvious cycles in the graph. However, even for small networks the emergent sequences may be difficult to predict.

The network in Figure 10A has $n=7$ neurons, and the graph is a tournament with no nontrivial automorphisms. The corresponding CTLN appears to have a single, global attractor, shown in Figure 10B. The neurons in this limit cycle fire in a repeating sequence, 634517, with 5 being the lowest-firing node. This sequence is highlighted in black in the graph, and corresponds to a cycle in the graph. However, it is only one of many cycles in the graph. Why do the dynamics select this sequence and not the others? And why does neuron 2 drop out, while all others persist? This is particularly puzzling given that node 2 has in-degree three, while nodes 3 and 5 have in-degree two.

Indeed, local properties of a network, such as the in- and out-degrees of individual nodes, are insufficient for predicting the participation and ordering of neurons in emergent sequences. Nevertheless, the sequence is fully determined by the structure of $G$ . We just have a limited understanding of how. Recent progress in understanding sequential attractors has relied on special network architectures that are cyclic like the ones in Figures 8 and 9 [seq-attractors]. Interestingly, although the graph in Figure 10 does not have such an architecture, the induced subgraph generated by the high-firing nodes 1, 3, 4, 6, and 7 is isomorphic to the graph in Figure 8. This graph, as well as the two graphs in Figure 9, have corresponding networks that are in some sense irreducible in their dynamics. These are examples of graphs that we refer to as core motifs [core-motifs].

4 Minimal fixed points, core motifs, and attractors

Stable fixed points of a network are of obvious interest because they correspond to static attractors [HahnSeungSlotine, net-encoding, pattern-completion, stable-fp-paper]. One of the most striking features of CTLNs, however, is the strong connection between unstable fixed points and dynamic attractors [book-chapter, core-motifs, seq-attractors].

Question 2.

For a given CTLN, can we predict the dynamic attractors of the network from its unstable fixed points? Can the unstable fixed points be determined from the structure of the underlying graph $G$ ?

Throughout this section, $G$ is a directed graph on $n$ nodes. Subsets $\sigma\subseteq[n]$ are often used to denote both the collection of vertices indexed by $\sigma$ and the induced subgraph $G|_{\sigma}$ . The corresponding network is assumed to be a nondegenerate CTLN with fixed parameters $\varepsilon,\delta,$ and $\theta$ .

Figure 11 provides two example networks to illustrate the relationship between unstable fixed points and dynamic attractors. Any CTLN with the graph in panel A has three fixed points, with supports $\operatorname{FP}(G)=\{4,123,1234\}$ . The collection of fixed point supports can be thought of as a partially ordered set, ordered by inclusion. In our example, $4$ and $123$ are thus minimal fixed point supports, because they are minimal under inclusion. It turns out that the corresponding fixed points each have an associated attractor (Figure 11B). The one supported on $4$ , a sink in the graph, yields a stable fixed point, while the $123$ (unstable) fixed point, whose induced subgraph $G|_{123}$ is a $3$ -cycle, yields a limit cycle attractor with high-firing neurons $1$ , $2$ , and $3$ . Figure 11C depicts all three fixed points in the state space. Here we can see that the third one, supported on $1234$ , acts as a “tipping point” on the boundary of two basins of attraction. Initial conditions near this fixed point can yield solutions that converge either to the stable fixed point or the limit cycle.

Figure 11D-F provides another example network, called “baby chaos,” in which all fixed points are unstable. The minimal fixed point supports, $125,235,345$ and $145$ , all correspond to core motifs (embedded $3$ -cycles in the graph). The corresponding attractors are chaotic, and are depicted as firing rate curves (panel E) and trajectories in the state space (panel F). Note that the graph has an automorphism group that exchanges core motifs and their corresponding attractors.

Not all minimal fixed points have corresponding attractors. In [core-motifs] we saw that the key property of such a $\sigma\in\operatorname{FP}(G)$ is that it be minimal not only in $\operatorname{FP}(G)$ but also in $\operatorname{FP}(G|_{\sigma})$ , corresponding to the induced subnetwork restricted to the nodes in $\sigma$ . In other words, $\sigma$ is the only fixed point in $\operatorname{FP}(G|_{\sigma})$ . This motivates the definition of core motifs.

Definition 4.1.

Let $G$ be the graph of a CTLN on $n$ nodes. An induced subgraph $G|_{\sigma}$ is a core motif of the network if $\operatorname{FP}(G|_{\sigma})=\{\sigma\}$ .

When the graph $G$ is understood, we sometimes refer to $\sigma$ itself as a core motif if $G|_{\sigma}$ is one. The associated fixed point is called a core fixed point. Core motifs can be thought of as “irreducible” networks because they have a single fixed point which has full support. Since the activity is bounded and must converge to an attractor, the attractor can be said to correspond to this fixed point. A larger network that contains $G|_{\sigma}$ as an induced subgraph may or may not have $\sigma\in\operatorname{FP}(G)$ . When the core fixed point does survive, we say refer to the embedded $G|_{\sigma}$ as a surviving core motif, and we expect the associated attractor to survive. In Figure 11, the surviving core motifs are $G|_{4}$ and $G|_{123}$ , and they precisely predict the attractors of the network.

The simplest core motifs are cliques. When these survive inside a network $G$ , the corresponding attractor is always a stable fixed point supported on all nodes of the clique [fp-paper]. In fact, we conjectured that any stable fixed point for a CTLN must correspond to a maximal clique of $G$ – specifically, a target-free clique [fp-paper, stable-fp-paper].

Up to size $4$ , all core motifs are parameter-independent. For size $5$ , $37$ of $45$ core motifs are parameter-independent. Figure 12 shows the complete list of all core motifs of size $n\leq 4$ , together with some associated attractors. The cliques all correspond to stable fixed points, the simplest type of attractor. The $3$ -cycle yields the limit cycle attractor in Figure 5, which may be distorted when embedded in a larger network (see Figure 11B). The other core motifs whose fixed points are unstable have dynamic attractors. Note that the $4$ -cycu graph has a $(23)$ symmetry, and the rate curves for these two neurons are synchronous in the attractor. This synchrony is also evident in the $4$ -ufd attractor, despite the fact that this graph does not have the $(23)$ symmetry. Perhaps the most interesting attractor, however, is the one for the fusion $3$ -cycle graph. Here the $123$ $3$ -cycle attractor, which does not survive the embedding to the larger graph, appears to “fuse” with the stable fixed point associated to $4$ (which also does not survive). The resulting attractor can be thought of as binding together a pair of smaller attractors.

Figure 13A depicts a larger example of a network whose fixed point structure $\operatorname{FP}(G)$ is predictive of the attractors. Note that only four supports are minimal: $48$ , $189$ , $236$ , and $345$ . The first two correspond to surviving cliques, and the last two correspond to $3$ -cycles with surviving fixed points. An extensive search of attractors for this network reveals only four attractors, corresponding to the four surviving core motifs. Figure 13B shows trajectories converging to each of the four attractors. The cliques yield stable fixed points, as expected, while the $3$ -cycles correspond to dynamic attractors: one limit cycle, and one strange or chaotic attractor.

We have performed extensive tests on whether or not core motifs predict attractors in small networks. Specifically, we decomposed all 9608 non-isomorphic directed graphs on $n=5$ nodes into core motif components, and used this to predict the attractors [n5-github]. We found that 1053 of the graphs have surviving core motifs that are not cliques; these graphs were thus expected to support dynamic attractors. The remaining 8555 graphs contain only cliques as surviving core motifs, and were thus expected to have only stable fixed point attractors. Overall, we found that core motifs correctly predicted the set of attractors in 9586 of the 9608 graphs. Of the 22 graphs with mistakes, 19 graphs have a core motif with no corresponding attractor, and 3 graphs have no core motifs for the chosen parameters [n5-github].

Across the 1053 graphs with core motifs that are not cliques, we observed a total of 1130 dynamic attractors. Interestingly, these fall into distinct equivalence classes determined by (a) the core motif, and (b) the details of how the core motif is embedded in the larger graph. In the case of oriented graphs on $n=5$ nodes, we performed a more detailed analysis of the dynamic attractors to determine a set of attractor families [core-motifs]. Here we observed a striking modularity of the embedded attractors, wherein the precise details of an attractor remained nearly identical across large families of non-isomorphic graphs with distinct CTLNs. Figure 14 gives a sampling of these common attractors, together with corresponding graph families. Graph families are depicted via “master graphs,” with solid edges being shared across all graphs in the family, and dashed edges being optional. Graph counts correspond to non-isomorphic graphs. See [core-motifs] for more details.

5 Graph rules

We have seen that CTLNs exhibit a rich variety of nonlinear dynamics, and that the attractors are closely related to the fixed points. This opens up a strategy for linking attractors to the underlying network architecture $G$ via the fixed point supports $\operatorname{FP}(G)$ . Our main tools for doing this are graph rules.

Throughout this section, we will use greek letters $\sigma,\tau,\omega$ to denote subsets of $[n]=\{1,\ldots,n\}$ corresponding to fixed point supports (or potential supports), while latin letters $i,j,k,\ell$ denote individual nodes/neurons. As before, $G|_{\sigma}$ denotes the induced subgraph obtained from $G$ by restricting to $\sigma$ and keeping only edges between vertices of $\sigma$ . The fixed point supports are:

	$\displaystyle\operatorname{FP}(G)$	$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}$	$\displaystyle\{\sigma\subseteq[n]\mid\sigma=\operatorname{supp}{x^{*}}\text{ for some }$
			$\displaystyle\text{fixed pt }x^{*}\text{ of the associated CTLN}\}.\vspace{-.05in}$

The main question addressed by graph rules is:

Question 3.

What can we say about $\operatorname{FP}(G)$ from knowledge of $G$ alone?

For example, consider the graphs in Figure 15. Can we determine from the graph alone which subgraphs will support fixed points? Moreover, can we determine which of those subgraphs are core motifs that will give rise to attractors of the network? We saw in Section 4 (Figure 12) that cycles and cliques are among the small core motifs; can cycles and cliques produce core motifs of any size? Can we identify other graph structures that are relevant for either ruling in or ruling out certain subgraphs as fixed point supports? The rest of Section 5 focuses on addressing these questions.

Note that implicit in the above questions is the idea that graph rules are parameter-independent: that is, they directly relate the structure of $G$ to $\operatorname{FP}(G)$ via results that are valid for all choices of $\varepsilon,\delta,$ and $\theta$ (provided they lie within the legal range). In order to obtain the most powerful results, we also require that our CTLNs be nondegenerate. As has already been noted, nondegeneracy is generically satisfied for TLNs [fp-paper]. For CTLNs, it is satisfied irrespective of $\theta$ and for almost all legal range choices of $\varepsilon$ and $\delta$ (i.e., up to a set of measure zero in the two-dimensional parameter space for $\varepsilon$ and $\delta$ ).

5.1 Examples of graph rules

We’ve already seen some graph rules. For example, Theorem 3.1 told us that if $G$ is an oriented graph with no sinks, the associated CTLN has no stable fixed points. Such CTLNs are thus guaranteed to only exhibit dynamic attractors. Here we present a set of eight simple graph rules, all proven in [fp-paper], that are easy to understand and give a flavor of the kinds of theorems we have found.

We will use the following graph theoretic terminology. A source is a node with no incoming edges, while a sink is a node with no outgoing edges. Note that a node can be a source or sink in an induced subgraph $G|_{\sigma}$ , while not being one in $G$ . An independent set is a collection of nodes with no edges between them, while a clique is a set of nodes that is all-to-all bidirectionally connected. A cycle is a graph (or an induced subgraph) where each node has exactly one incoming and one outgoing edge, and they are all connected in a single directed cycle. A directed acyclic graph (DAG) is a graph with a topological ordering of vertices such that $i\not\to j$ whenever $i>j$ ; such a graph does not contain any directed cycles. Finally, a target of a graph $G|_{\sigma}$ is a node $k$ such that $i\to k$ for all $i\in\sigma\setminus\{k\}$ . Note that a target may be inside or outside $G|_{\sigma}$ .

The graph rules presented here can be found, with detailed proofs, in [fp-paper]. We also summarize them in Table 1 and Figure 16.

Examples of graph rules:

Rule 1 (independent sets): If $G|_{\sigma}$ is an independent set, then $\sigma\in\operatorname{FP}(G)$ if and only if each $i\in\sigma$ is a sink in $G$ .

Rule 2 (cliques): If $G|_{\sigma}$ is a clique, then $\sigma\in\operatorname{FP}(G)$ if and only if there is no node $k$ of $G$ , $k\notin\sigma$ , such that $i\to k$ for all $i\in\sigma.$ In other words, $\sigma\in\operatorname{FP}(G)$ if and only if $G|_{\sigma}$ is a target-free clique. If $\sigma\in\operatorname{FP}(G)$ , the corresponding fixed point is stable.

Rule 3 (cycles): If $G|_{\sigma}$ is a cycle, then $\sigma\in\operatorname{FP}(G)$ if and only if there is no node $k$ of $G$ , $k\notin\sigma$ , such that $k$ receives two or more edges from $\sigma$ . If $\sigma\in\operatorname{FP}(G)$ , the corresponding fixed point is unstable.

Rule 4 (sources): (i) If $G|_{\sigma}$ contains a source $j\in\sigma$ , with $j\to k$ for some $k\in[n]$ , then $\sigma\notin\operatorname{FP}(G)$ . (ii) Suppose $j\notin\sigma$ , but $j$ is a source in $G$ . Then $\sigma\in\operatorname{FP}(G|_{\sigma\cup j})$ if and only if $\sigma\in\operatorname{FP}(G|_{\sigma})$ .

Rule 5 (targets): (i) If $\sigma$ has target $k$ , with $k\in\sigma$ and $k\not\to j$ for some $j\in\sigma$ ( $j\neq k$ ), then $\sigma\notin\operatorname{FP}(G|_{\sigma})$ and thus $\sigma\notin\operatorname{FP}(G)$ . (ii) If $\sigma$ has target $k\not\in\sigma$ , then $\sigma\notin\operatorname{FP}(G|_{\sigma\cup k})$ and thus $\sigma\notin\operatorname{FP}(G)$ .

Rule 6 (sinks): If $G$ has a sink $s\notin\sigma$ , then $\sigma\cup\{s\}\in\operatorname{FP}(G)$ if and only if $\sigma\in\operatorname{FP}(G)$ .

Rule 7 (DAGs): If $G$ is a directed acyclic graph with sinks $s_{1},\ldots,s_{\ell}$ , then $\operatorname{FP}(G)=\{\cup s_{i}\mid s_{i}\text{ is a sink in }G\}$ , the set of all $2^{\ell}-1$ unions of sinks.

Rule 8 (parity): For any $G$ , $|\operatorname{FP}(G)|$ is odd.

Rule name	$G\|_{\sigma}$ structure	graph rule
Rule 1	independent set	$\sigma\in\operatorname{FP}(G\|_{\sigma}),$ and $\sigma\in\operatorname{FP}(G)\Leftrightarrow\sigma$ is a union of sinks
Rule 2	clique	$\sigma\in\operatorname{FP}(G\|_{\sigma}),$ and $\sigma\in\operatorname{FP}(G)\Leftrightarrow\sigma$ is target-free
Rule 3	cycle	$\sigma\in\operatorname{FP}(G\|_{\sigma}),$ and $\sigma\in\operatorname{FP}(G)\Leftrightarrow$ each $k\notin\sigma$
		receives at most one edge $i\to k$ with $i\in\sigma$
Rule 4(i)	$\exists$ a source $j\in\sigma$	$\sigma\notin\operatorname{FP}(G)$ if $j\to k$ for some $k\in[n]$
Rule 4(ii)	$\exists$ a source $j\not\in\sigma$	$\sigma\in\operatorname{FP}(G\|_{\sigma\cup j})\Leftrightarrow\sigma\in\operatorname{FP}(G\|_{\sigma})$
Rule 5(i)	$\exists$ a target $k\in\sigma$	$\sigma\notin\operatorname{FP}(G\|_{\sigma})$ and $\sigma\notin\operatorname{FP}(G)$ if $k\not\to j$ for some $j\in\sigma$
Rule 5(ii)	$\exists$ a target $k\not\in\sigma$	$\sigma\not\in\operatorname{FP}(G\|_{\sigma\cup k})$ and $\sigma\notin\operatorname{FP}(G)$
Rule 6	$\exists$ a sink $s\notin\sigma$	$\sigma\cup\{s\}\in\operatorname{FP}(G)\Leftrightarrow\sigma\in\operatorname{FP}(G)$
Rule 7	DAG	$\operatorname{FP}(G)=\{\cup s_{i}\mid s_{i}\text{ is a sink in }G\}$
Rule 8	arbitrary	$\|\operatorname{FP}(G)\|$ is odd

Table 1: Graph rules connect properties of a graph

G

to the fixed point supports,

\operatorname{FP}(G),

of the associated CTLN. Each rule refers to the structure of the induced subgraph

G|_{\sigma}

in order to determine whether

\sigma\in\operatorname{FP}(G|_{\sigma})

and/or

\sigma\in\operatorname{FP}(G)

In many cases, particularly for small graphs, our graph rules are complete enough that they can be used to fully work out $\operatorname{FP}(G)$ . In such cases, $\operatorname{FP}(G)$ is guaranteed to be parameter-independent (since the graph rules do not depend on $\varepsilon$ and $\delta$ ). As an example, consider the graph on $n=5$ nodes in Figure 15A; we will show that $\operatorname{FP}(G)$ is completely determined by graph rules. Going through the possible subsets $\sigma$ of different sizes, we find that for $|\sigma|=1$ only $3,4\in\operatorname{FP}(G)$ (as those are the sinks). Using Rules 1, 2, and 4, we see that the only $|\sigma|=2$ elements in $\operatorname{FP}(G)$ are the clique $15$ and the independent set $34$ . A crucial ingredient for determining the fixed point supports of sizes $3$ and $4$ is the sinks rule, which guarantees that $135$ , $145$ , and $1345$ are the only supports of these sizes. Finally, notice that the total number of fixed points up through size $|\sigma|=4$ is odd. Using Rule 8 (parity), we can thus conclude that there is no fixed point of full support – that is, with $|\sigma|=5$ . It follows that $\operatorname{FP}(G)=\{3,4,15,34,135,145,1345\}$ ; moreover, this result is parameter-independent because it was determined purely from graph rules. Although the precise values of the fixed points will change for different choices of the parameters $\varepsilon,\delta$ and $\theta$ , the set of supports $\operatorname{FP}(G)$ is invariant.

We leave it as an exercise to use graph rules to show that $\operatorname{FP}(G)=\{134\}$ for the graph in Figure 15B, and $\operatorname{FP}(G)=\{4,12,124\}$ for the graph in Figure 15C. For the graph in C, it is necessary to appeal to a more general rule for uniform in-degree subgraphs, which we review next.

Rules 1-7, and many more, all emerge as corollaries of more general rules. In the next few subsections, we will introduce the uniform in-degree rule, graphical domination, and simply-embedded subgraphs. Then, in Section 5.5, we will pool together the more general rules into a complete set of elementary graph rules from which all others follow.

5.2 Uniform in-degree rule

It turns out that Rules 1, 2, and 3 (for independent sets, cliques, and cycles) are all corollaries of a single rule for graphs of uniform in-degree.

Definition 5.1.

We say that $G|_{\sigma}$ has uniform in-degree $d$ if every node $i\in\sigma$ has $d$ incoming edges from within $G|_{\sigma}$ .

Note that an independent set has uniform in-degree $d=0$ , a cycle has uniform in-degree $d=1$ , and an $n$ -clique is uniform in-degree with $d=n-1$ . But, in general, uniform in-degree graphs need not be symmetric. For example, the induced subgraph $G|_{145}$ in Figure 15A is uniform in-degree, with $d=1$ .

For CTLNs, a fixed point $x^{*}$ with support $\sigma$ satisfies:

(I-W_{\sigma})x_{\sigma}^{*}=\theta 1_{\sigma},

where $1_{\sigma}$ is a vector of all $1$ ’s restricted to the index set $\sigma$ . If $G|_{\sigma}$ has uniform in-degree $d$ , then the row sums of $I-W_{\sigma}$ are identical, and so $1_{\sigma}$ is an eigenvector. In particular,

x_{\sigma}^{*}=\dfrac{\theta}{R}1_{\sigma},

where $R$ is the (uniform) row sum for the matrix $I-W_{\sigma}$ . For in-degree $d$ , we compute

R=1+d(1-\varepsilon)+(|\sigma|-d-1)(1+\delta).

Uniform in-degree fixed points with support $\sigma$ thus have the same value for all $i\in\sigma$ :

\displaystyle x_{i}^{*}=\dfrac{\theta}{|\sigma|+\delta(|\sigma|-d-1)-\varepsilon d}.

(7)

(See also [fp-paper, Lemma 18].) From the derivation, it is clear that this formula holds for all uniform in-degree graphs, even those that are not symmetric.

We can use the formula (7) to verify that the on-neuron conditions, $x_{i}^{*}>0$ for each $i\in\sigma$ , are satisfied for $\varepsilon,\delta,\theta$ within the legal range. Using it to check the off-neuron conditions, we find that for $k\notin\sigma$ ,

$\displaystyle y_{k}^{*}$	$\displaystyle=$	$\displaystyle\sum_{i\in\sigma}W_{ki}x_{i}^{*}+\theta,$
	$\displaystyle=$	$\displaystyle\sum_{i\to k}(-1+\varepsilon)x_{i}^{}+\sum_{i\not\to k}(-1-\delta)x_{i}^{}+\theta,$
	$\displaystyle=$	$\displaystyle\theta\left(\dfrac{d_{k}(-1+\varepsilon)+(\|\sigma\|-d_{k})(-1-\delta)}{\|\sigma\|+\delta(\|\sigma\|-d-1)-\varepsilon d}+1\right),$

where $d_{k}=|\{i\in\sigma\mid i\to k\}|$ . From here, it is not difficult to see that the off-neuron condition, $y_{k}^{*}\leq 0$ , will be satisfied if and only if $d_{k}\leq d$ . This gives us the following theorem.

Theorem 5.2 ([fp-paper]).

Let $G|_{\sigma}$ be an induced subgraph of $G$ with uniform in-degree $d$ . For $k\notin\sigma$ , let $d_{k}$ denote the number of edges $i\to k$ for $i\in\sigma$ . Then $\sigma\in\operatorname{FP}(G|_{\sigma})$ , and

\sigma\in\operatorname{FP}(G|_{\sigma\cup k})\;\Leftrightarrow\;d_{k}\leq d.\vspace{-.075in}

In particular, $\sigma\in\operatorname{FP}(G)$ if and only if there does not exist $k\notin\sigma$ such that $d_{k}>d$ .

Figure 17 gives examples of uniform in-degree graphs and illustrates the survival condition in Theorem 5.2.

5.3 Graphical domination

We have seen that uniform in-degree graphs support fixed points that have uniform firing rates (equation (7)). More generally, fixed points can have very different values across neurons. However, there is some level of “graphical balance” that is required of $G|_{\sigma}$ for any fixed point support $\sigma$ . For example, it can be shown that if $\sigma$ contains a pair of neurons $j,k$ that have the property that all neurons sending edges to $j$ also send edges to $k$ , and $j\to k$ but $k\not\to j$ , then $\sigma$ cannot be a fixed point support. Intuitively, this is because $k$ is receiving a strict superset of the inputs to $j$ , and this imbalance rules out their ability to coexist in the same fixed point support. This property motivates the following definition.

Definition 5.3.

We say that $k$ graphically dominates $j$ with respect to $\sigma$ in $G$ if the following three conditions all hold:

1.

For each $i\in\sigma\setminus\{j,k\}$ , if $i\to j$ then $i\to k$ .
2.

If $j\in\sigma$ , then $j\to k$ .
3.

If $k\in\sigma$ , then $k\not\to j$ .

We refer to this as “inside-in” domination if $j,k\in\sigma$ (see Figure 18A). In this case, we must have $j\to k$ and $k\not\to j$ . If $j\in\sigma$ , $k\notin\sigma$ , we call it “outside-in” domination (Figure 18B). On the other hand, “inside-out” domination is the case where $k\in\sigma$ , $j\notin\sigma$ , and “outside-out” domination refers to $j,k\notin\sigma$ (see Figure 18C-D).

What graph rules does domination give us? Intuitively, when inside-in domination is present, the “graphical balance” necessary to support a fixed point is violated, and so $\sigma\notin\operatorname{FP}(G)$ . When $k$ outside-in dominates $j$ , with $j\in\sigma$ and $k\notin\sigma$ , again there is an imbalance, and this time it guarantees that neuron $k$ turns on, since it receives all the inputs that were sufficient to turn on neuron $j$ . Thus, there cannot be a fixed point with support $\sigma$ since node $k$ will violate the off-neuron conditions. We can draw interesting conclusions in the other cases of graphical domination as well, as Theorem 5.4 shows.

Theorem 5.4 ([fp-paper]).

Suppose $k$ graphically dominates $j$ with respect to $\sigma$ in $G$ . Then the following all hold:

1.

(inside-in) If $j,k\in\sigma$ , then $\sigma\notin\operatorname{FP}(G|_{\sigma})$ and thus $\sigma\notin\operatorname{FP}(G)$ .
2.

(outside-in) If $j\in\sigma$ , $k\notin\sigma$ , then $\sigma\notin\operatorname{FP}(G|_{\sigma\cup k})$ and thus $\sigma\notin\operatorname{FP}(G)$ .
3.

(inside-out) If $k\in\sigma$ , $j\notin\sigma$ , then $\sigma\in\operatorname{FP}(G|_{\sigma})\;\Rightarrow\;\sigma\in\operatorname{FP}(G|_{\sigma\cup j})$ .
4.

(outside-out) If $j,k\not\in\sigma$ , then $\sigma\in\operatorname{FP}(G|_{\sigma\cup k})\;\Rightarrow\;\sigma\in\operatorname{FP}(G|_{\sigma\cup j})$ .

The four cases of Theorem 5.4 are illustrated in Figure 18. This theorem was originally proven in [fp-paper]. Here we provide a more elementary proof, using only the definition of CTLNs and ideas from Section 2.

Proof.

Suppose that $k$ graphically dominates $j$ with respect to $\sigma$ in $G$ . To prove statements 1 and 2 in the theorem, we will also assume that there exists a fixed point $x^{*}$ of the associated CTLN with support $\operatorname{supp}(x^{*})=\sigma$ . This will allow us to arrive at a contradiction.

If $x^{*}$ is a fixed point, we must have $x_{i}^{*}=[y_{i}^{*}]_{+}$ for all $i\in[n]$ (see equation (3) from Section 2). Recalling that $W_{jj}=W_{kk}=0$ , and that $x_{i}^{*}=0$ for $i\notin\sigma$ , it follows that for any $j,k\in[n]$ , we have:

	$\displaystyle y_{j}^{*}$	$\displaystyle=$	$\displaystyle\sum_{i\in\sigma\setminus\{j,k\}}W_{ji}x^{}_{i}+W_{jk}x^{}_{k}+\theta,$
	$\displaystyle y_{k}^{*}$	$\displaystyle=$	$\displaystyle\sum_{i\in\sigma\setminus\{j,k\}}W_{ki}x^{}_{i}+W_{kj}x^{}_{j}+\theta.$

Since $k$ graphically dominates $j$ with respect to $\sigma$ , we know that $W_{ji}\leq W_{ki}$ for all $i\in\sigma~{}\setminus~{}\{j,k\}$ . This is because the off-diagonal values $W_{\ell i}$ are either $-1+\varepsilon$ , for $i\to\ell$ , or $-1-\delta$ , for $i\not\to\ell$ ; and $-1+\varepsilon>-1-\delta$ . It now follows from the above equations that $y_{j}^{*}-W_{jk}x^{*}_{k}\leq y_{k}^{*}-W_{kj}x^{*}_{j}$ . Equivalently,

y_{j}^{*}+W_{kj}x^{*}_{j}\leq y_{k}^{*}+W_{jk}x^{*}_{k}.

(8)

We will refer frequently to (8) in what follows. There are four cases of domination to consider. We begin with the first two:

1.

(inside-in) If $j,k\in\sigma$ , then $x^{*}_{j}=y_{j}^{*}>0$ and $x^{*}_{k}=y_{k}^{*}>0$ , and so at the fixed point we must have $(1+W_{kj})x^{*}_{j}\leq(1+W_{jk})x^{*}_{k}.$ But domination in this case implies $j\to k$ and $k\not\to j$ , so that $W_{kj}=-1+\varepsilon$ and $W_{jk}=-1-\delta$ . Plugging this in, we obtain $\varepsilon x^{*}_{j}\leq-\delta x^{*}_{k}$ . This results in a contradiction, since $x^{*}_{j},x^{*}_{k}>0$ and $\varepsilon,\delta>0$ . We conclude that $\sigma\notin\operatorname{FP}(G)$ . More specifically, since the contradiction involved only the on-neuron conditions, it follows that $\sigma\notin\operatorname{FP}(G|_{\sigma})$ .
2.

(outside-in) If $j\in\sigma$ and $k\notin\sigma$ , then $x^{*}_{j}=y_{j}^{*}>0$ and $x^{*}_{k}=0,$ with $y_{k}^{*}\leq 0$ . It follows from (8) that $(1+W_{kj})x^{*}_{j}\leq~{}0$ . Since this case of domination also has $j\to k$ , we obtain $(1+W_{kj})x^{*}_{j}=\varepsilon x_{j}^{*}\leq 0$ , a contradiction. Again, we can conclude that $\sigma\notin\operatorname{FP}(G)$ , and more specifically that $\sigma\notin\operatorname{FP}(G|_{\sigma\cup k})$ .

This completes the proof of statements 1 and 2.

To prove statements 3 and 4, we assume only that $\sigma\in\operatorname{FP}(G|_{\sigma})$ , so that a fixed point $x^{*}$ with support $\sigma$ exists in the restricted network $G|_{\sigma}$ , but does not necessarily extend to larger networks. Whether or not it extends depends on whether $y_{i}^{*}\leq 0$ for all $i\notin\sigma$ .

3.

(inside-out) If $j\not\in\sigma$ and $k\in\sigma$ , then $x^{*}_{j}=0$ and $x^{*}_{k}=y_{k}^{*}>0$ , and so (8) becomes $y_{j}^{*}\leq(1+W_{jk})x^{*}_{k}.$ Domination in this case implies $k\not\to j$ , so we obtain $y_{j}^{*}\leq-\delta x^{*}_{k}<0$ . This shows that $j$ is guaranteed to satisfy the required off-neuron condition. We can thus conclude that $\sigma\in\operatorname{FP}(G|_{\sigma\cup j})$ .
4.

(outside-out) If $j,k\notin\sigma$ , then $x^{*}_{j}=x^{*}_{k}=0$ , and so (8) tells us that $y_{j}^{*}\leq y_{k}^{*}$ . This is true irrespective of whether or not $j\to k$ or $k\to j$ (and both are optional in this case). Clearly, if $y_{k}^{*}\leq 0$ then $y_{j}^{*}\leq 0$ . We can thus conclude that if $\sigma\in\operatorname{FP}(G|_{\sigma\cup k})$ , then $\sigma\in\operatorname{FP}(G|_{\sigma\cup j})$ .

∎

Rules 4, 5, and 7 are all consequences of Theorem 5.4. To see how, consider a graph with a source $j\in\sigma$ that has an edge $j\to k$ for some $k\in[n]$ . Since $j$ is a source, it has no incoming edges from within $\sigma$ . If $k\in\sigma$ , then $k$ inside-in dominates $j$ and so $\sigma\notin\operatorname{FP}(G)$ . If $k\notin\sigma$ , then $k$ outside-in dominates $j$ and again $\sigma\notin\operatorname{FP}(G)$ . Rule 4(i) immediately follows. We leave it as an exercise to prove Rules 4(ii), 5(i), 5(ii), and 7.

5.4 Simply-embedded subgraphs and covers

Finally, we introduce the concept of simply-embedded subgraphs. This is the last piece we need before presenting the complete set of elementary graph rules.

Definition 5.5 (simply-embedded).

We say that a subgraph $G|_{\tau}$ is simply-embedded in $G$ if for each $k\notin\tau$ , either

(i)

$k\to i$ for all $i\in\tau$ , or
(ii)

$k\not\to i$ for all $i\in\tau$ .

In other words, while $G|_{\tau}$ can have any internal structure, the rest of the network treats all nodes in $\tau$ equally (see Figure 19A). By abuse of notation, we sometimes say that the corresponding subset of vertices $\tau\subseteq[n]$ is simply-embedded in $G$ .

We allow $\tau=[n]$ as a trivial case, meaning that $G$ is simply-embedded in itself. At the other extreme, all singletons $\tau=\{i\}$ and the empty set $\tau=\emptyset$ are simply-embedded in $G$ , also for trivial reasons. Note that a subset of a simply-embedded set, $\omega\subset\tau$ , need not be simply-embedded. This is because nodes in $\tau\setminus\omega$ may not treat those in $\omega$ equally.

Now let’s consider the CTLN equations for neurons in a simply-embedded subgraph $G|_{\tau}$ , for $\tau\subset[n]$ . For each $i\in\tau$ , the equations for the dynamics can be rewritten as:

\dfrac{dx_{i}}{dt}=-x_{i}+\left[\sum_{j\in\tau}W_{ij}x_{j}+\sum_{k\not\in\tau}W_{ik}x_{k}+\theta\right]_{+},

where the term $\sum_{k\not\in\tau}W_{ik}x_{k}$ is identical for all $i\in\tau$ . This is because $W_{ik}=-1+\varepsilon$ , if $k\to i$ , and $W_{ik}=-1-\delta$ if $k\not\to i$ ; so the fact that $k$ treats all $i\in\tau$ equally means that the matrix entries $\{W_{ik}\}_{i\in\tau}$ are identical for fixed $k$ . We can thus define a single time-varying input function,

\mu_{\tau}(t)=\sum_{k\not\in\tau}W_{ik}x_{k}(t)+\theta,\;\;\text{for }\;i\in\tau,

that is the same independent of the choice of $i\in\tau$ . This gives us:

\dfrac{dx_{i}}{dt}=-x_{i}+\left[\sum_{j\in\tau}W_{ij}x_{j}+\mu_{\tau}(t)\right]_{+},\text{ for each }i\in\tau.

In particular, the neurons in $\tau$ evolve according to the dynamics of the local network $G|_{\tau}$ in the presence of a time-varying input $\mu_{\tau}(t)$ , in lieu of the constant $\theta$ .

Suppose we have a fixed point $x^{*}$ of the full network $G$ , with support $\sigma\in\operatorname{FP}(G)$ . At the fixed point,

\mu_{\tau}^{*}=\sum_{k\not\in\tau}W_{ik}x_{k}^{*}+\theta=\sum_{k\in\sigma\setminus\tau}W_{ik}x_{k}^{*}+\theta,

which is a constant. We can think of this as a new choice of the CTLN input parameter, $\widetilde{\theta}=\mu_{\tau}^{*}$ , with the caveat that we may have $\widetilde{\theta}\leq 0$ . It follows that the restriction of the fixed point to $\tau$ , $x_{\tau}^{*}$ , must be a fixed point of subnetwork $G|_{\tau}$ . If $\widetilde{\theta}\leq 0$ , this will be the zero fixed point corresponding to $\emptyset$ support. If $\widetilde{\theta}>0$ , this fixed point will have nonempty support $\sigma\cap\tau\in\operatorname{FP}(G|_{\tau})$ . From these observations, we have the following key lemma (see Figure 19B):

Lemma 5.6.

Let $G|_{\tau}$ be simply-embedded in $G$ . Then for any $\sigma\subseteq[n]$ ,

\sigma\in\operatorname{FP}(G)\;\Rightarrow\;\sigma\cap\tau\in\operatorname{FP}(G|_{\tau})\cup\{\emptyset\}.\vspace{-.05in}

What happens if we consider more than one simply-embedded subgraph? Lemma 5.7 shows that intersections of simply-embedded subgraphs are also simply-embedded. However, the union of two simply-embedded subgraphs is only guaranteed to be simply-embedded if the intersection is nonempty. (It is easy to find a counterexample if the intersection is empty.)

Lemma 5.7.

Let $\tau_{1},\tau_{2}\subseteq[n]$ be simply-embedded in $G$ . Then $\tau_{1}\cap\tau_{2}$ is simply-embedded in $G$ . If $\tau_{1}\cap\tau_{2}\neq\emptyset,$ then $\tau_{1}\cup\tau_{2}$ is also simply-embedded in $G$ .

Proof.

If $\tau_{1}\cap\tau_{2}=\emptyset$ , then the intersection is trivially simply-embedded. Assume $\tau_{1}\cap\tau_{2}\neq\emptyset$ , and consider $k\notin\tau_{1}\cap\tau_{2}$ . If $k\notin\tau_{1}$ , then $k$ treats all vertices in $\tau_{1}$ equally and must therefore treat all vertices in $\tau_{1}\cap\tau_{2}$ equally. By the same logic, if $k\notin\tau_{2}$ then it must treat all vertices in $\tau_{1}\cap\tau_{2}$ equally. It follows that $\tau_{1}\cap\tau_{2}$ is simply-embedded in $G$ .

Next, consider $\tau_{1}\cup\tau_{2}$ for a pair of subsets $\tau_{1},\tau_{2}$ such that $\tau_{1}\cap\tau_{2}\neq\emptyset.$ Let $j\in\tau_{1}\cap\tau_{2}$ and $k\notin\tau_{1}\cup\tau_{2}$ . If $k\to j$ , then $k\to i$ for all $i\in\tau_{1}$ since $k\notin\tau_{1}$ ; moreover, $k\to\ell$ for all $\ell\in\tau_{2}$ since $k\notin\tau_{2}$ . If, on the other hand, $k\not\to j$ , then by the same logic $k\not\to i$ for any $i\in\tau_{1}$ and $k\not\to\ell$ for any $\ell\in\tau_{2}$ . It follows that $\tau_{1}\cup\tau_{2}$ is simply-embedded in $G$ . ∎

If we have two simply-embedded subgraphs, $G|_{\tau_{i}}$ and $G|_{\tau_{j}}$ , we know that for any $\sigma\in\operatorname{FP}(G)$ , $\sigma$ must restrict to a fixed point $\sigma_{i}=\sigma\cap\tau_{i}$ and $\sigma_{j}=\sigma\cap\tau_{j}$ in each of those subgraphs. But when can we glue together such a $\sigma_{i}\in\operatorname{FP}(G|_{\tau_{i}})$ and $\sigma_{j}\in\operatorname{FP}(G|_{\tau_{j}})$ to produce a larger fixed point support $\sigma_{i}\cup\sigma_{j}$ in $\operatorname{FP}(G|_{\tau_{i}\cup\tau_{j}})$ ?

Lemma 5.8 precisely answers this question. It uses the following notation:

\operatorname{\widehat{FP}}(G)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\operatorname{FP}(G)\cup\{\emptyset\}.

Lemma 5.8 (pairwise gluing).

Suppose $G|_{\tau_{i}},G|_{\tau_{j}}$ are simply-embedded in $G$ , and consider $\sigma_{i}\in\operatorname{\widehat{FP}}(G|_{\tau_{i}})$ and $\sigma_{j}\in\operatorname{\widehat{FP}}(G|_{\tau_{j}})$ that satisfy $\sigma_{i}\cap\tau_{j}=\sigma_{j}\cap\tau_{i}$ (so that $\sigma_{i},\sigma_{j}$ agree on the overlap $\tau_{i}\cap\tau_{j}$ ). Then

\sigma_{i}\cup\sigma_{j}\in\operatorname{\widehat{FP}}(G|_{\tau_{i}\cup\tau_{j}})

if and only if one of the following holds:

(i)

$\tau_{i}\cap\tau_{j}=\emptyset$ and $\sigma_{i},\sigma_{j}\in\operatorname{\widehat{FP}}(G|_{\tau_{i}\cup\tau_{j}}),$ or
(ii)

$\tau_{i}\cap\tau_{j}=\emptyset$ and $\sigma_{i},\sigma_{j}\notin\operatorname{\widehat{FP}}(G|_{\tau_{i}\cup\tau_{j}}),$ or
(iii)

$\tau_{i}\cap\tau_{j}\neq\emptyset.$

Parts (i-ii) of Lemma 5.8 are essentially the content of [fp-paper, Theorem 14]. Part (iii) can also be proven with similar arguments.

5.5 Elementary graph rules

In this section we collect a set of elementary graph rules from which all other graph rules can be derived. The first two elementary rules arise from general arguments about TLN fixed points stemming from the hyperplane arrangement picture. They hold for all competitive/inhibition-dominated nondegenerate TLNs, as does Elem Rule 3 (aka Rule 8). The last three elementary graph rules are specific to CTLNs, and recap results from the previous three subsections. As usual, $G$ is a graph on $n$ nodes and $\operatorname{FP}(G)$ is the set of fixed points supports.

There are six elementary graph rules:

Elem Rule 1

(unique supports): For a given $G$ , there is at most one fixed point per support $\sigma\subseteq[n]$ . The fixed points can therefore be labeled by the elements of $\operatorname{FP}(G)$ .

Elem Rule 2

(restriction/lifting): Let $\sigma\subseteq[n]$ . Then

	$\displaystyle\sigma\in\operatorname{FP}(G)$	$\displaystyle\Leftrightarrow$	$\displaystyle\sigma\in\operatorname{FP}(G\|_{\sigma})\text{ and }$
			$\displaystyle\sigma\in\operatorname{FP}(G\|_{\sigma\cup k})\text{ for all }k\notin\sigma.$

Moreover, whether $\sigma\in\operatorname{FP}(G|_{\sigma})$ survives to $\sigma\in\operatorname{FP}(G|_{\sigma\cup k})$ depends only on the outgoing edges $i\to k$ for $i\in\sigma$ , not on the backward edges $k\to i$ .

Elem Rule 3

(parity): The total number of fixed points, $|\operatorname{FP}(G)|,$ is always odd.
Elem Rule 4
(uniform in-degree): If $G|_{\sigma}$ has uniform in-degree $d$ , then
1. (a)
  
  $\sigma\in\operatorname{FP}(G|_{\sigma})$ , and
2. (b)
  
  $\sigma\in\operatorname{FP}(G|_{\sigma\cup k})\;\Leftrightarrow\;d_{k}\leq d$ in $G|_{\sigma\cup k}.$
In particular, $\sigma\in\operatorname{FP}(G)\;\Leftrightarrow\;$ there does not exist $k\notin\sigma$ that receives more than $d$ edges from $\sigma$ .
Elem Rule 5
(domination): Suppose $k$ graphically dominates $j$ with respect to $\sigma$ .
1. (a)
  
  (inside-in) If $j,k\in\sigma$ , then $\sigma\notin\operatorname{FP}(G|_{\sigma})$ and thus $\sigma\notin\operatorname{FP}(G)$ .
2. (b)
  
  (outside-in) If $j\in\sigma$ , $k\notin\sigma$ , then
  $\sigma\notin\operatorname{FP}(G|_{\sigma\cup k})$ and thus $\sigma\notin\operatorname{FP}(G)$ .
3. (c)
  
  (inside-out) If $k\in\sigma$ , $j\notin\sigma$ , then
  $\sigma\in\operatorname{FP}(G|_{\sigma})\;\Rightarrow\;\sigma\in\operatorname{FP}(G|_{\sigma\cup j})$ .
4. (d)
  
  (outside-out) If $j,k\not\in\sigma$ , then
  $\sigma\in\operatorname{FP}(G|_{\sigma\cup k})\;\Rightarrow\;\sigma\in\operatorname{FP}(G|_{\sigma\cup j})$ .
Elem Rule 6
(simply-embedded): Suppose that $G|_{\tau_{i}},G|_{\tau_{j}}$ are simply-embedded in $G$ , and recall the notation $\operatorname{\widehat{FP}}(G)=\operatorname{FP}(G)\cup\{\emptyset\}.$ We have the following restriction and gluing rules:
1. (a)
  
  (restriction) $\sigma\in\operatorname{FP}(G)\Rightarrow\sigma\cap\tau_{i}\in\operatorname{\widehat{FP}}(G|_{\tau_{i}}).$
2. (b)
  (pairwise gluing) If $\sigma_{i}\in\operatorname{\widehat{FP}}(G|_{\tau_{i}})$ , $\sigma_{j}\in\operatorname{\widehat{FP}}(G|_{\tau_{j}}),$ and $\sigma_{i}\cap\tau_{j}=\sigma_{j}\cap\tau_{i}$ (so that $\sigma_{i},\sigma_{j}$ agree on the overlap $\tau_{i}\cap\tau_{j}$ ), then $\sigma_{i}\cup\sigma_{j}\in\operatorname{\widehat{FP}}(G|_{\tau_{i}\cup\tau_{j}})$ if and only if one of the following holds:
  1. i.
    
    $\tau_{i}\cap\tau_{j}=\emptyset$ and $\sigma_{i},\sigma_{j}\in\operatorname{\widehat{FP}}(G|_{\tau_{i}\cup\tau_{j}}),$
  2. ii.
    
    $\tau_{i}\cap\tau_{j}=\emptyset$ and $\sigma_{i},\sigma_{j}\notin\operatorname{\widehat{FP}}(G|_{\tau_{i}\cup\tau_{j}}),$
  3. iii.
    
    $\tau_{i}\cap\tau_{j}\neq\emptyset.$
  Moreover, if $\tau_{i}\cap\tau_{j}\neq\emptyset,$ we are also guaranteed that $G|_{\tau_{i}\cup\tau_{j}}$ and $G|_{\tau_{i}\cap\tau_{j}}$ are simply-embedded in $G$ . Thus, $\sigma_{i}\cap\sigma_{j}\in\operatorname{\widehat{FP}}(G|_{\tau_{i}\cap\tau_{j}})$ . If, additionally, $\sigma_{i}\cap\sigma_{j}\neq\tau_{i}\cap\tau_{j}$ , then $\sigma_{i},\sigma_{j}\in\operatorname{\widehat{FP}}(G|_{\tau_{i}\cup\tau_{j}}).$
3. (c)
  
  (lifting) If $\{\tau_{1},\ldots,\tau_{N}\}$ is a simply-embedded cover of $G$ and $\sigma\cap\tau_{i}\in\operatorname{FP}(G|_{\tau_{i}})$ for each $i\in[N]$ , then
  
  $\sigma\in\operatorname{FP}(G)\;\Leftrightarrow\;\sigma\in\operatorname{FP}(G|_{\sigma}).$

Elem Rule 6 is illustrated in Figure 20. It collects several results related to simply-embedded graphs. Elem Rule 6(a) is the same as Lemma 5.6, while Elem Rule 6(b) is given by Lemmas 5.7 and 5.8. Note that this rule is valid even if $\sigma_{i}$ or $\sigma_{j}$ is empty. Elem Rule 6(c) applies to simply-embedded covers of $G$ , a notion we will define in the next section (see Definition 6.1, below). The forward direction, $\sigma\in\operatorname{FP}(G)\Rightarrow\sigma\in\operatorname{FP}(G|_{\sigma})$ , follows from Elem Rule 2. The backwards direction is the content of [fp-paper, Lemma 8].

6 Gluing rules

So far we have seen a variety of graph rules and the elementary graph rules from which they are derived. These rules allow us to rule in and rule out potential fixed points in $\operatorname{FP}(G)$ from purely graph-theoretic considerations. In this section, we consider networks whose graph $G$ is composed of smaller induced subgraphs, $G|_{\tau_{i}}$ , for $i\in[N]=\{1,\ldots,N\}$ . What is the relationship between $\operatorname{FP}(G)$ and the fixed points of the components, $\operatorname{FP}(G|_{\tau_{i}})$ ?

It turns out we can obtain nice results if the induced subgraphs $G|_{\tau_{i}}$ are all simply-embedded in $G$ . In this case, we say that $G$ has a simply-embedded cover.

Definition 6.1 (simply-embedded covers).

We say that $\mathcal{U}=\{\tau_{1},\ldots,\tau_{N}\}$ is a simply-embedded cover of $G$ if each $\tau_{i}$ is simply-embedded in $G$ , and for every vertex $j\in[n],$ there exists an $i\in[N]$ such that $j\in\tau_{i}$ . In other words, the $\tau_{i}$ ’s are a vertex cover of $G$ . If the $\tau_{i}$ ’s are all disjoint, we say that $\mathcal{U}$ is a simply-embedded partition of $G$ .

Every graph $G$ has a trivial simply-embedded cover, with $N=n$ , obtained by taking $\tau_{i}=\{i\}$ for each $i\in[n]$ . This is also a simply-embedded partition. At the other extreme, since the full set of vertices $[n]$ is a simply-embedded set, we also have the trivial cover with $N=1$ and $\tau_{1}=[n]$ . These covers, however, do not yield useful information about $\operatorname{FP}(G)$ . In contrast, nontrivial simply-embedded covers can provide strong constraints on, and in some cases fully determine, the set of fixed points $\operatorname{FP}(G)$ . Some of these constraints can be described via gluing rules, which we explain below.

In the case that $G$ has a simply-embedded cover, Lemma 5.6 tells us that all “global” fixed point supports in $\operatorname{FP}(G)$ must be unions of “local” fixed point supports in the $\operatorname{FP}(G|_{\tau_{i}})$ , since every $\sigma\in\operatorname{FP}(G)$ restricts to $\sigma\cap\tau_{i}\in\operatorname{FP}(G|_{\tau_{i}})\cup\{\emptyset\}$ . But what about the other direction?

Question 4.

When does a collection of local fixed point supports $\{\sigma_{i}\}$ , with each nonempty $\sigma_{i}\in\operatorname{FP}(G|_{\tau_{i}})$ , glue together to form a global fixed point support $\sigma=\cup\sigma_{i}\in\operatorname{FP}(G)$ ?

To answer this question, we develop some notions inspired by sheaf theory. For a graph $G$ on $n$ nodes, with a simply-embedded cover $\mathcal{U}=\{\tau_{1},\ldots,\tau_{N}\}$ , we define the gluing complex as:

	$\displaystyle\mathcal{F}_{G}(\mathcal{U})$	$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}$	$\displaystyle\{\sigma=\cup_{i}\sigma_{i}\mid\sigma\neq\emptyset,\sigma_{i}\in\operatorname{FP}(G\|_{\tau_{i}})\cup\{\emptyset\},$
			$\displaystyle\text{ and }\sigma_{i}\cap\tau_{j}=\sigma_{j}\cap\tau_{i}\text{ for all }i,j\in[N]\}.$

In other words, $\mathcal{F}_{G}(\mathcal{U})$ consists of all $\sigma\subseteq[n]$ that can be obtained by gluing together local fixed point supports $\sigma_{i}\in\operatorname{FP}(G|_{\tau_{i}})$ . Note that in order to guarantee that $\sigma_{i}=\sigma\cap\tau_{i}$ for each $i$ , it is necessary that the $\sigma_{i}$ ’s agree on overlaps $\tau_{i}\cap\tau_{j}$ (hence the last requirement). This means that $\mathcal{F}_{G}(\mathcal{U})$ is equivalent to:

\mathcal{F}_{G}(\mathcal{U})=\{\sigma\neq\emptyset\mid\sigma\cap\tau_{i}\in\operatorname{\widehat{FP}}(G|_{\tau_{i}})\;\forall\>\tau_{i}\in\mathcal{U}\},

using the notation $\operatorname{\widehat{FP}}(G|_{\tau_{i}})=\operatorname{FP}(G|_{\tau_{i}})\cup\{\emptyset\}.$

It will also be useful to consider the case where $\sigma\cap\tau_{i}$ is not allowed to be empty for any $i$ . In this case, we define

\mathcal{F}^{*}_{G}(\mathcal{U})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\{\sigma\subseteq[n]\mid\sigma\cap\tau_{i}\in\operatorname{FP}(G|_{\tau_{i}})\;\forall\>\tau_{i}\in\mathcal{U}\}.

Translating Lemma 5.6 into the new notation yields the following:

Lemma 6.2.

A CTLN with graph $G$ and simply-embedded cover $\mathcal{U}$ satisfies

\operatorname{FP}(G)\subseteq\mathcal{F}_{G}(\mathcal{U}).

The central question addressed by gluing rules (Question 4) thus translates to: What elements of $\mathcal{F}_{G}(\mathcal{U})$ are actually in $\operatorname{FP}(G)$ ?

Some examples. Before delving into this question, we make a few observations. First, note that although $\mathcal{F}_{G}(\mathcal{U})$ is never empty (it must contain $\operatorname{FP}(G)$ ), the set $\mathcal{F}^{*}_{G}(\mathcal{U})$ may be empty.

For example, in Figure 21A, $\mathcal{F}^{*}_{G}(\mathcal{U})=\emptyset$ , because the only option for $\sigma\cap\tau_{1}$ is $\{123\}$ , and this would imply $3\in\sigma\cap\tau_{2}$ ; but there is no such option in $\operatorname{FP}(G|_{\tau_{2}}).$ On the other hand, if we are allowed $\sigma\cap\tau_{i}=\emptyset$ , we can choose $\sigma=\{4\}$ and satisfy both $\sigma\cap\tau_{1}\in\operatorname{\widehat{FP}}(G|_{\tau_{1}})$ and $\sigma\cap\tau_{2}\in\operatorname{\widehat{FP}}(G|_{\tau_{2}})$ . In fact, this is the only such choice and therefore $\mathcal{F}_{G}(\mathcal{U})=\{4\}$ . Since $|\operatorname{FP}(G)|\geq 1$ , it follows from Lemma 6.2 that $\operatorname{FP}(G)=\{4\}$ . In this case, $\operatorname{FP}(G)=\mathcal{F}_{G}(\mathcal{U})$ .

Figure 21B displays another graph, $G$ , that has a simply-embedded cover $\mathcal{U}$ with three components, $\tau_{1},\tau_{2},$ and $\tau_{3}$ . Each set of local fixed point supports, $\operatorname{FP}(G|_{\tau_{i}})$ (shown at the bottom of Figure 21B), can easily be computed using graph rules. Applying the definitions, we obtain:

	$\displaystyle\mathcal{F}^{*}_{G}(\mathcal{U})$	$\displaystyle=$	$\displaystyle\{12346,123456\},$
	$\displaystyle\mathcal{F}_{G}(\mathcal{U})$	$\displaystyle=$	$\displaystyle\{12346,123456,1234,12345,56,5,6\}.$

Since $\operatorname{FP}(G)\subseteq\mathcal{F}_{G}(\mathcal{U})$ , this narrows down the list of candidate fixed point supports in $\operatorname{FP}(G)$ . Using Elem Rule 5 (domination), we can eliminate supports $56$ and $5$ , since $6$ dominates $5$ with respect to every $\sigma\subseteq[n]$ . On the other hand, Elem Rule 4 (uniform in-degree) allows us to verify that $1234,12345,$ and $123456$ are all fixed point supports of $G$ , while Rule 1 and Rule 6 (sinks) tell us that $6,12346\in\operatorname{FP}(G)$ . We can thus conclude that $\operatorname{FP}(G)=\{12346,123456,1234,12345,6\}\subsetneq\mathcal{F}_{G}(\mathcal{U}).$

Note that for both graphs in Figure 21, we have $\mathcal{F}^{*}_{G}(\mathcal{U})\subseteq\operatorname{FP}(G)\subseteq\mathcal{F}_{G}(\mathcal{U})$ . While the second containment is guaranteed by Lemma 6.2, the first one need not hold in general.

As mentioned above, the central gluing question is to identify what elements of $\mathcal{F}_{G}(\mathcal{U})$ are in $\operatorname{FP}(G)$ . Our strategy to address this question will be to identify architectures where we can iterate the pairwise gluing rule, Lemma 5.8 (a.k.a. Elem Rule 6(b)). Iteration is possible in a simply-embedded cover $\mathcal{U}=\{\tau_{i}\}$ provided the unions at each step, $\tau_{1}\cup\tau_{2}\cup\cdots\cup\tau_{\ell},$ are themselves simply-embedded (this may depend on the order). Fortunately, this is the case for several types of natural constructions, including connected unions, disjoint unions, clique unions, and linear chains, which we consider next. Finally, we will examine the case of cyclic unions, where pairwise gluing rules cannot be iterated, but for which we find an equally clean characterization of $\operatorname{FP}(G)$ . All five architectures result in theorems, which we call gluing rules, that are summarized in Table 2.

6.1 Connected unions

Recall that the nerve of a cover $\mathcal{U}=\{\tau_{i}\}_{i=1}^{N}$ is the simplicial complex:

\operatorname{\mathcal{N}}(\mathcal{U})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\{\alpha\subseteq[N]\mid\bigcap_{i\in\alpha}\tau_{i}\neq\emptyset\}.

The nerve keeps track of the intersection data of the sets in the cover. We say that a vertex cover $\mathcal{U}=\{\tau_{i}\}_{i=1}^{N}$ of $G$ is connected if its nerve is a connected simplicial complex. This means one can “walk” from any $\tau_{i}$ to any other $\tau_{j}$ through a sequence of steps between $\tau_{i}$ ’s that overlap. (Note that a connected nerve does not imply a connected $G$ , or vice versa.)

Any graph $G$ admits vertex covers that are connected. Having a connected cover that is also simply-embedded, however, is quite restrictive. We call such architectures connected unions:

Definition 6.3.

A graph $G$ is a connected union of induced subgraphs $\{G|_{\tau_{i}}\}$ if $\{\tau_{1},\ldots,\tau_{N}\}$ is a simply-embedded cover of $G$ that is also connected.

If $G$ has a connected simply-embedded cover, then without loss of generality we can enumerate the sets $\tau_{1},\ldots,\tau_{N}$ in such a way that each partial union $\tau_{1}\cup\tau_{2}\cup\cdots\cup\tau_{\ell}$ is also simply-embedded in $G$ , by ensuring that $\tau_{\ell}\cap(\tau_{1}\cup\cdots\cup\tau_{\ell-1})\neq\emptyset$ for each $\ell$ (see Lemma 5.7). This allows us to iterate the pairwise gluing rule, Elem Rule 6(b)iii. In fact, by analyzing the different cases with the $\sigma_{i}$ empty or nonempty, we can determine that all gluings of compatible fixed points supports $\{\sigma_{i}\}$ are realized in $\operatorname{FP}(G)$ . This yields our first gluing rule theorem:

Theorem 6.4.

If $G$ is a connected union of subgraphs $\{G|_{\tau_{i}}\}_{i=1}^{N}$ , with $\mathcal{U}=\{\tau_{i}\}_{i=1}^{N}$ , then

\operatorname{FP}(G)=\mathcal{F}_{G}(\mathcal{U}).

It is easy to check that this theorem exactly predicts $\operatorname{FP}(G)$ for the graphs in Figure 20E,F and Figure 21A.

Example.

To see the power of Theorem 6.4, consider the graph $G$ on $n=8$ nodes in Figure 22. $G$ is a rather complicated graph, but it has a connected, simply-embedded cover $\{\tau_{1}=123,\tau_{2}=345,\tau_{3}=5678\}$ with subgraphs $G|_{\tau_{i}}$ given in Figure 22A. Note that for this graph, the simply-embedded requirement automatically determines all additional edges in $G$ . For example, since $2\to 3$ in $G|_{\tau_{1}}$ , and $3\in\tau_{2}$ , we must also have $2\to 4,5$ . In contrast, $1\not\to 3$ in $G|_{\tau_{1}}$ , and hence we must have $1\not\to 4$ and $1\not\to 5$ .

Using simple graph rules, it is easy to compute $\operatorname{FP}(G|_{\tau_{1}})=\{123\},$ $\operatorname{FP}(G|_{\tau_{2}})=\{34,5,345\},$ and $\operatorname{FP}(G|_{\tau_{3}})=\{567,678,5678\},$ as these are small graphs. It would be much more difficult to compute the full network’s $\operatorname{FP}(G)$ in this way. However, because $G$ is a connected union, Theorem 6.4 tells us that $\operatorname{FP}(G)=\mathcal{F}_{G}(\mathcal{U}).$ By simply checking compatibility on overlaps of the possible $\sigma_{i}=\sigma\cap\tau_{i}\in\operatorname{FP}(G|_{\tau_{i}})$ , we can easily compute:

	$\displaystyle\operatorname{FP}(G)\;=\;\mathcal{F}_{G}(\mathcal{U})$	$\displaystyle=$	$\displaystyle\{1234,1234678,1234567,$
			$\displaystyle 12345678,567,5678,678\}.$

Note that the minimal fixed point supports, $1234,567,$ and $678,$ are all core motifs: $G|_{1234}$ is a $4$ -ufd graph, while the others are $3$ -cycles. Moreover, they each have corresponding attractors, as predicted from our previous observations about core motifs [core-motifs]. The attractors are shown in Figure 22C.

6.2 Disjoint unions, clique unions, cyclic unions, and linear chains

Theorem 6.4 gave us a nice gluing rule in the case where $G$ has a connected simply-embedded cover. At the other extreme are simply-embedded partitions. If $\mathcal{U}=\{\tau_{i}\}_{i=1}^{N}$ is a simply-embedded partition, then all $\tau_{i}$ ’s are disjoint and the nerve $\operatorname{\mathcal{N}}(\mathcal{U})$ is completely disconnected, consisting of the isolated vertices $1,\ldots,N$ .

The following graph constructions all arise from simply-embedded partitions.

Definition 6.5.

Consider a graph $G$ with induced subgraphs $\{G|_{\tau_{i}}\}$ corresponding to a vertex partition $\mathcal{U}=\{\tau_{1},\ldots,\tau_{N}\}$ . Then

–

$G$ is a disjoint union if there are no edges between $\tau_{i}$ and $\tau_{j}$ for $i\neq j$ . (See Figure 23A.)
–

$G$ is a clique union if it contains all possible edges between $\tau_{i}$ and $\tau_{j}$ for $i\neq j$ . (See Figure 23B.)
–

$G$ is a linear chain if it contains all possible edges from $\tau_{i}$ to $\tau_{i+1}$ , for $i=1,\ldots,N-1$ , and no other edges between distinct $\tau_{i}$ and $\tau_{j}$ . (See Figure 23C.)
–

$G$ is a cyclic union if it contains all possible edges from $\tau_{i}$ to $\tau_{i+1}$ , for $i=1,\ldots,N-1$ , as well as all possible edges from $\tau_{N}$ to $\tau_{1}$ , but no other edges between distinct components $\tau_{i}$ , $\tau_{j}$ . (See Figure 23D.)

Note that in each of these cases, $\mathcal{U}$ is a simply-embedded partition of $G$ .

s-e architecture	fixed point supports	$\|\operatorname{FP}(G)\|$	theorem
connected union	$\operatorname{FP}(G)=\mathcal{F}_{G}(\mathcal{U})$	depends on overlaps	Thm 6.4
disjoint union	$\operatorname{FP}(G)=\mathcal{F}_{G}(\mathcal{U})$	$\prod_{i=1}^{N}(\|\operatorname{FP}(G\|_{\tau_{i}})\|+1)-1$	Thm 6.6
	= $\{\cup_{i}\,\sigma_{i}\mid\sigma_{i}\in\operatorname{\widehat{FP}}(G\|_{\tau_{i}})\;\forall i\}\setminus\{\emptyset\}$
clique union	$\operatorname{FP}(G)=\mathcal{F}^{*}_{G}(\mathcal{U})$	$\prod_{i=1}^{N}\|\operatorname{FP}(G\|_{\tau_{i}})\|$	Thm 6.7
	= $\{\cup_{i}\,\sigma_{i}\mid\sigma_{i}\in\operatorname{FP}(G\|_{\tau_{i}})\;\forall i\in[N]\}$
linear chain	$\operatorname{FP}(G)=\operatorname{FP}(G\|_{\tau_{N}})$	$\|\operatorname{FP}(G\|_{\tau_{N}})\|$	Thm 6.8
cyclic union	$\operatorname{FP}(G)=\mathcal{F}^{*}_{G}(\mathcal{U})$	$\prod_{i=1}^{N}\|\operatorname{FP}(G\|_{\tau_{i}})\|$	Thm 6.7
	= $\{\cup_{i}\,\sigma_{i}\mid\sigma_{i}\in\operatorname{FP}(G\|_{\tau_{i}})\;\forall i\in[N]\}$

Table 2: Summary of gluing rules. For each simply-embedded architecture,

\operatorname{FP}(G)

is given in terms of the

\operatorname{FP}(G|_{\tau_{i}})

’s for component subgraphs.

Since the simply-embedded subgraphs in a partition are all disjoint, Lemma 5.8(i-ii) applies. Consequently, fixed point supports $\sigma_{i}\in\operatorname{FP}(G|_{\tau_{i}})$ and $\sigma_{j}\in\operatorname{FP}(G|_{\tau_{j}})$ will glue together if and only if either $\sigma_{i}$ and $\sigma_{j}$ both survive to yield fixed points in $\operatorname{FP}(G)$ , or neither survives. For both disjoint unions and clique unions, it is easy to see that all larger unions of the form $\tau_{1}\cup\tau_{2}\cup\cdots\cup\tau_{\ell}$ are themselves simply-embedded. We can thus iteratively use the pairwise gluing Lemma 5.8. For disjoint unions, Lemma 5.8(i) applies, since every $\sigma_{i}\in\operatorname{FP}(G|_{\tau_{i}})$ survives in $G$ . This yields our first gluing theorem. Recall that $\operatorname{\widehat{FP}}(G)=\operatorname{FP}(G)\cup\{\emptyset\}$ .

Theorem 6.6.

[fp-paper, Theorem 11] If $G$ is a disjoint union of subgraphs $\{G|_{\tau_{i}}\}_{i=1}^{N}$ , with $\mathcal{U}=\{\tau_{i}\}_{i=1}^{N}$ , then

	$\displaystyle\operatorname{FP}(G)$	$\displaystyle=$	$\displaystyle\mathcal{F}_{G}(\mathcal{U})$
		$\displaystyle=$	$\displaystyle\{\cup_{i=1}^{N}\sigma_{i}\mid\sigma_{i}\in\operatorname{\widehat{FP}}(G\|_{\tau_{i}})\>\forall\>i\in[N]\}\setminus\{\emptyset\}.$

Note that this looks identical to the result for connected unions, Theorem 6.4. One difference is that compatibility of $\sigma_{i}$ ’s need not be checked, since the $\tau_{i}$ ’s are disjoint, so $\mathcal{F}_{G}(\mathcal{U})$ is particularly easy to compute. In this case the size of $\operatorname{FP}(G)$ is also the maximum possible for a graph with a simply-embedded cover $\mathcal{U}$ :

|\operatorname{FP}(G)|=\prod_{i=1}^{N}(|\operatorname{FP}(G|_{\tau_{i}})|+1)-1.

On the other hand, for clique unions, we must apply Lemma 5.8(ii), which shows that only gluings involving a nonempty $\sigma_{i}$ from each component are allowed. Hence $\operatorname{FP}(G)=\mathcal{F}^{*}_{G}(\mathcal{U})$ . Interestingly, the same result holds for cyclic unions, but the proof is different because the simply-embedded structure does not get preserved under unions, and hence Lemma 5.8 cannot be iterated. These results are combined in the next theorem.

Theorem 6.7.

[fp-paper, Theorems 12 and 13] If $G$ is a clique union or a cyclic union of subgraphs $\{G|_{\tau_{i}}\}_{i=1}^{N}$ , with $\mathcal{U}=\{\tau_{i}\}_{i=1}^{N}$ , then

	$\displaystyle\operatorname{FP}(G)$	$\displaystyle=$	$\displaystyle\mathcal{F}^{*}_{G}(\mathcal{U})$
		$\displaystyle=$	$\displaystyle\{\cup_{i=1}^{N}\sigma_{i}\mid\sigma_{i}\in\operatorname{FP}(G\|_{\tau_{i}})\>\forall\>i\in[N]\}.$

In this case, $|\operatorname{FP}(G)|=\prod_{i=1}^{N}|\operatorname{FP}(G|_{\tau_{i}})|.$

Finally, we consider linear chain architectures. In the case of a linear chain (Figure 23C), the gluing sequence must respect the ordering $\tau_{1},\ldots,\tau_{N}$ in order to guarantee that the unions $\tau_{1}\cup\tau_{2}\cup\cdots\cup\tau_{\ell}$ are all simply-embedded. (In the case of disjoint and clique unions, the order didn’t matter.) Now consider the first pairwise gluing, with $\tau_{1}$ and $\tau_{2}$ . Each $\sigma_{1}\in\operatorname{FP}(G|_{\tau_{1}})$ has a target in $\tau_{2}$ , and hence does not survive to $\operatorname{FP}(G|_{\tau_{1}\cup\tau_{2}})$ (by Rule 5(ii)). On the other hand, any $\sigma_{2}\in\operatorname{FP}(G|_{\tau_{2}})$ has no outgoing edges to $\tau_{1}$ , and is thus guaranteed to survive. Elem Rule 6(b) thus tells us that $\sigma_{1}\cup\sigma_{2}\notin\operatorname{FP}(G|_{\tau_{1}\cup\tau_{2}})$ unless $\sigma_{1}=\emptyset$ . Therefore, $\operatorname{FP}(G|_{\tau_{1}\cup\tau_{2}})=\operatorname{FP}(G|_{\tau_{2}})$ . Iterating this procedure, adding the next $\tau_{i}$ at each step, we see that $\operatorname{FP}(G|_{\tau_{1}\cup\cdots\cup\tau_{\ell}})=\operatorname{FP}(G|_{\tau_{\ell}})$ . In the end, we obtain our fourth gluing theorem:

Theorem 6.8.

[seq-attractors] If $G$ is a linear chain of subgraphs $\{G|_{\tau_{i}}\}_{i=1}^{N}$ , then

\operatorname{FP}(G)=\operatorname{FP}(G|_{\tau_{N}}).

Clearly, $|\operatorname{FP}(G)|=|\operatorname{FP}(G|_{\tau_{N}})|$ in this case.

Table 2 summarizes the gluing rules for connected unions, disjoint unions, clique unions, cyclic unions, and linear chains.

6.3 Applications of gluing rules to core motifs

Using the above results, it is interesting to revisit the subject of core motifs. Recall that core motifs of CTLNs are subgraphs $G|_{\sigma}$ that support a unique fixed point, which has full-support: $\operatorname{FP}(G|_{\sigma})=\{\sigma\}$ . We denote the set of surviving core motifs by

\operatorname{FP_{core}}(G)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\{\sigma\in\operatorname{FP}(G)~{}|~{}G|_{\sigma}\text{ is a core motif of }G\}.

For small CTLNs, we have seen that core motifs are predictive of a network’s attractors [core-motifs]. We also saw this in Figure 22, with attractors corresponding to the core motifs in a CTLN for a connected union.

What can gluing rules tell us about core motifs? Consider the architectures in Table 2. In the case of disjoint unions, we know that we can never obtain a core motif, since $|\operatorname{FP}(G)|=|\mathcal{F}_{G}(\mathcal{U})|\geq 3$ whenever there is more than one component subgraph. In the case of connected unions, however, we have a nice result in the situation where all components $\tau_{i}$ are core motifs. In this case, the additional compatibility requirement on overlaps forces $\operatorname{FP}(G)=\mathcal{F}_{G}(\mathcal{U})=\{[n]\}$ .

Corollary 6.9.

If $G$ is a connected union of core motifs, then $G$ is a core motif.

Proof.

Let $G|_{\tau_{1}},\ldots,G|_{\tau_{N}}$ be the component core motifs for the connected union $G$ , a graph on $n$ nodes. Since $\mathcal{U}=\{\tau_{i}\}$ is a connected cover, and each component has $\operatorname{FP}(G|_{\tau_{i}})=\{\tau_{i}\}$ , the only possible $\sigma\in\mathcal{F}_{G}(\mathcal{U})$ arises from taking $\sigma_{i}=\tau_{i}$ in each component, so that $\sigma=[n]$ . (By compatibility, taking an empty set in any component forces choosing an empty set in all components, yielding $\sigma=\cup\sigma_{i}=\emptyset$ , which is not allowed in $\mathcal{F}_{G}(\mathcal{U})$ .) Applying Theorem 6.4, we see that $\operatorname{FP}(G)=\mathcal{F}_{G}(\mathcal{U})=\{[n]\}$ . Hence, $G$ is a core motif. ∎

As of this writing, we have no good reason to believe the converse is true. However, we have yet to find a counterexample.

In the case of clique unions and cyclic unions, however, $\operatorname{FP}(G)=\mathcal{F}_{G}^{*}(\mathcal{U})$ , and gluing in empty sets is again not allowed on components. In these cases, we obtain a similar result, and the converse is also true.

Corollary 6.10.

Let $G$ be a clique union or a cyclic union of components $\tau_{1},\ldots,\tau_{N}$ . Then

\operatorname{FP_{core}}(G)=\{\cup_{i=1}^{N}\sigma_{i}~{}|~{}\sigma_{i}\in\operatorname{FP_{core}}(G|_{\tau_{i}})\}.\vspace{-.05in}

In particular, $G$ is a core motif if and only if every $G|_{\tau_{i}}$ is a core motif.

Proof.

We will prove the second statement. The expression for $\operatorname{FP_{core}}(G)$ easily follows from this together with Elem Rule 6(c). Let $G$ be a clique union or a cyclic union for a simply-embedded partition $\mathcal{U}=\{\tau_{i}\}$ . Theorem 6.7 tells us that $\operatorname{FP}(G)=\mathcal{F}_{G}^{*}(\mathcal{U})$ . Observe that any $\sigma\in\mathcal{F}_{G}^{*}(\mathcal{U})$ must have nonempty $\sigma_{i}=\sigma\cap\tau_{i}\in\operatorname{FP}(G|_{\tau_{i}})$ for each $i$ . ( $\Leftarrow$ ) If each $G|_{\tau_{i}}$ is a core motif, it follows that $\sigma_{i}=\tau_{i}$ for each $i$ , and hence $\operatorname{FP}(G)=\{[n]\}$ . ( $\Rightarrow$ ) If the component graphs are not all core, then $\operatorname{FP}(G)$ will necessarily have more than one fixed point and $G$ cannot be core.∎

Going back to Figure 12, we can now see that all core motifs up to size $n=4$ are either clique unions, cyclic unions, or connected unions of smaller core motifs. For example, the $4$ -cycu graph is the cyclic union of a singleton (node $1$ ), a $2$ -clique (nodes $2$ and $3$ ), and another singleton (node $4$ ). The fusion $3$ -cycle is a clique union of a $3$ -cycle and a singleton. Finally, the $4$ -ufd is the connected union of a $3$ -cycle and a $2$ -clique. Infinite families of core motifs can be generated in this way, each having their own particular attractors.

6.4 Modeling with cyclic unions

The power of graph rules is that they enable us to reason mathematically about the graph of a CTLN and make surprisingly accurate predictions about the dynamics. This is particularly true for cyclic unions, where the dynamics consistently appear to traverse the components in cyclic order. Consequently, these architectures are useful for modeling a variety of phenomena that involve sequential attractors. This includes the storage and retrieval of sequential memories, as well as CPGs responsible for rhythmic activity, such as locomotion [Marder-CPG, Yuste-CPG].

Recall that the attractors of a network tend to correspond to core motifs in $\operatorname{FP_{core}}(G)$ . Using Corollary 6.10, we can easily engineer cyclic unions that have multiple sequential attractors. For example, consider the cyclic union in Figure 24A, with $\operatorname{FP_{core}}(G)$ comprised of all cycles of length 5 that contain exactly one node per component. For parameters $\varepsilon=0.75$ , $\delta=4$ , the CTLN yields a limit cycle (Figure 24B), corresponding to one such core motif, with sequential firing of a node from each component. By symmetry, there must be an equivalent limit cycle for every choice of 5 nodes, one from each layer, and thus the network is guaranteed to have $m^{5}$ limit cycles. Note that this network architecture, increased to 7 layers, could serve as a mechanism for storing phone numbers in working memory ( $m=10$ for digits $0-9$ ).

As another application of cyclic unions, consider the graph in Figure 25A which produces the quadruped gait ‘bound’ (similar to gallop), where we have associated each of the four colored nodes with a leg of the animal. Notice that the clique between pairs of legs ensures that those nodes co-fire, and the cyclic union structure guarantees that the activity flows forward cyclically. A similar network was created for the ‘trot’ gait, with appropriate pairs of legs joined by cliques.

Figure 25B shows a network in which both the ‘bound’ and ‘trot’ gaits can coexist, with the network selecting one pattern (limit cycle) over the other based solely on initial conditions. This network was produced by essentially overlaying the two architectures that would produce the desired gaits, identifying the two graphs along the nodes corresponding to each leg. Notice that within this larger network, the induced subgraphs for each gait are no longer perfect cyclic unions (since they include additional edges between pairs of legs), and are no longer core motifs. And yet the combined network still produces limit cycles that are qualitatively similar to those of the isolated cyclic unions for each gait. It is an open question when this type of merging procedure for cyclic unions (or other types of subnetworks) will preserve the original limit cycles within the larger network.

7 Conclusions

Recurrent network models such as TLNs have historically played an important role in theoretical neuroscience; they give mathematical grounding to key ideas about neural dynamics and connectivity, and provide concrete examples of networks that encode multiple attractors. These attractors represent the possible responses, e.g. stored memory patterns, of the network.

In the case of CTLNs, we have been able to prove a variety of results, such as graph rules, about the fixed point supports $\operatorname{FP}(G)$ – yielding valuable insights into the attractor dynamics. Many of these results can be extended beyond CTLNs to more general families of TLNs, and potentially to other threshold nonlinearities. The reason lies in the combinatorial geometry of the hyperplane arrangements. In addition to the arrangements discussed in Section 2, there are closely related hyperplane arrangements given by the nullclines of TLNs, defined by $dx_{i}/dt=0$ for each $i$ . It is easy to see that fixed points correspond to intersections of nullclines, and thus the elements of $\operatorname{FP}(W,b)$ are completely determined by the combinatorial geometry of the nullcline arrangement. Intuitively, the combinatorial geometry of such an arrangement is preserved under small perturbations of $W$ and $b$ . This allows us to extend CTLN results and study how $\operatorname{FP}(W,b)$ changes as we vary the TLN parameters $W_{ij}$ and $b_{i}$ . These ideas, including connections to oriented matroids, were further developed in [oriented-matroids-paper].

In addition to gluing rules, we have also studied graphs with simply-embedded covers and related structures in order to predict the sequential attractors of a network [seq-attractors]. This has led us to introduce the notions of directional graphs and directional covers, allowing us to generalize cyclic unions and DAGs. In particular, we were able to prove various nerve theorems for CTLNs, wherein the dynamics of a network with a directional cover can be described via the dynamics of a reduced network defined on the nerve [nerve-thms-ctlns].

Finally, although the theory of TLNs and CTLNs has progressed significantly in recent years, many open questions remain. We end with a partial list.

7.1 Open Questions

We group our open questions into four categories.

The first category concerns the bifurcation theory of TLNs, focusing on changes in $\operatorname{FP}(W,b)$ as one varies $W$ or $b$ :

1.

Recall the definition, in equation (4), of $\operatorname{FP}(W,b)$ for an arbitrary TLN $(W,b)$ . How does the set of fixed point supports change as we vary $W$ or $b$ ? What are the possible bifurcations? For example, what pairs of supports, $\{\sigma,\tau\}$ , can disappear or co-appear at the same time?

This first question is very general. The next two questions focus on special cases where partial progress has already been made.
2.

If we look beyond CTLNs, but constrain the $W$ matrix to respect a given architecture $G$ , how does this constrain the possibilities for $\operatorname{FP}(W,b)$ ?

In the case of constant $b_{i}=\theta$ across neurons, we have identified robust motifs, graphs for which $\operatorname{FP}(W,b)$ is invariant across all compatible choices of $W$ [robust-motifs]. What graphs allow only a few possibilities for $\operatorname{FP}(W,b)$ ? What are the most flexible graphs for which $\operatorname{FP}(W,b)$ can vary the most?
3.

What happens if we fix $W$ and vary $b\in\mathbb{R}^{n}$ ? What features of the connectivity matrix $W$ control the repertoire of possible fixed point regimes, $\operatorname{FP}(W,b)$ ? What $W$ matrices allow a core motif region, for which $\operatorname{FP}(W,b)=\{[n]\}$ ? And how do the dynamic attractors of a network change as we transition between different regions in $b$ -space?

The second category concerns the relationship between TLNs and the geometry of the associated hyperplane arrangements:

4.

To what extent does the hyperplane arrangement of a TLN, as described in Section 2, determine its dynamics? What are all the $(W,b)$ choices that have the same hyperplane arrangement? Same nullcline arrangement?
5.

What happens if we change the nonlinearity in equation (1) from $\varphi(y)=[y]_{+}$ to a sigmoid function, a threshold power-law nonlinearity [ken-miller-thresh-power-law], or something else? Can we adapt the proofs and obtain similar results for $\operatorname{FP}(W,b)$ and $\operatorname{FP}(G)$ in these cases?

Note that the combinatorial geometry approach in [oriented-matroids-paper] suggests that the results should not depend too heavily on the details of the nonlinearity. Instead, it is the resulting arrangement of nullclines that is essential for determining the fixed points.

The third category concerns graph rules, core motifs, and the corresponding attractors:

6.

What other graph rules or gluing rules follow from the elementary graph rules? We believe our current list is far from exhaustive.
7.

Classify all core motifs for CTLNs. We already have a classification for graphs up to size $n=5$ [n5-github], but beyond this little is known. Note that gluing rules allow us to construct infinite families of core motifs from gluing together smaller component cores (see Section 6.3). Are there other families of core motifs that cannot be obtained via gluing rules? What can we say about the corresponding attractors?
8.

Computational evidence suggests a strong correspondence between core motifs and the attractors of a network, at least in the case of small CTLNs [core-motifs, n5-github]. Can we make this correspondence precise? Under what conditions does the correspondence between surviving core fixed points and attractors hold?
9.

How does symmetry affect the attractors of a network? The automorphism group of a graph $G$ naturally acts on an associated CTLN by permuting the variables, $\{x_{i}\}$ . This translates to symmetries of the defining vector field (2), and a group action on the set of attractors. The automorphism group can either fix attractors or permute them. Moreover, a network may also have “surprise symmetry,” as in Figure 9, where the attractors display additional symmetry that was not present in the original graph $G$ . How do we make sense of these various phenomena?

Finally, the fourth category collects various conjectures about dynamic behaviors that we have observed in simulations.

10.

In [CTLN-preprint, stable-fp-paper] we conjectured that all stable fixed points of a CTLN correspond to target-free cliques. While [stable-fp-paper] provides proofs of this conjecture in special cases, the general question remains open.
11.

The Gaudi attractor from Figure 8 appears to have constant total population activity. In other words, $\sum_{i=1}^{5}x_{i}(t)$ appears to be constant in numerical experiments, once the trajectory has converged to the attractor. Can we prove this? For what other (non-static) TLN/CTLN attractors is the total population activity conserved?
12.

Prove that the “baby chaos” network in Figure 11D-F is chaotic. I.e., prove that the individual attractors are chaotic (or strange), in the same sense as the Lorenz or Rossler attractors.
13.

A proper source of a graph $G$ is a source node $j$ that has at least one outgoing edge, $j\to k$ for $k\neq j$ . In numerical experiments, we have observed that proper sources of CTLNs always seem to “die” – that is, their activity $x_{j}(t)$ tends to zero as $t\to\infty$ , regardless of initial conditions. Can we prove this?

Some progress on this question was made in [caitlin-thesis], but the general conjecture remains open. Note that although the sources Rule 4(i) guarantees that proper sources do not appear in any fixed point support of $\operatorname{FP}(G)$ , this alone does not imply that the activity at such nodes converges to zero.
14.

In our classification of attractors for small CTLNs, we observed that if two CTLNs with distinct graphs have the “same” attractor, as in Figure 14, then this attractor is preserved for the entire family of TLNs whose $W$ matrices linearly interpolate between the two CTLNs (and have the same constant $b_{i}=\theta$ for all $i$ ). In other words, the attractor persists for all TLNs $(W_{t},\theta)$ with $W_{t}=(1-t)W_{0}+tW_{1}$ and $t\in[0,1]$ , where $W_{0}$ and $W_{1}$ are the two CTLN connectivity matrices. (Note that the interpolating networks $W_{t}$ for $t\in(0,1)$ are not CTLNs.) Can we prove this?

More generally, we conjecture that if the same attractor is present for a set of TLNs $(W_{1},b),\ldots,(W_{m},b)$ , then it is present for all TLNs $(W,b)$ with $W$ in the convex hull of the $W_{i}$ matrices.

Acknowledgments

We would like to thank Zelong Li, Nicole Sanderson, and Juliana Londono Alvarez for a careful reading of the manuscript. We also thank Caitlyn Parmelee, Caitlin Lienkaemper, Safaan Sadiq, Anda Degeratu, Vladimir Itskov, Christopher Langdon, Jesse Geneson, Daniela Egas Santander, Stefania Ebli, Alice Patania, Joshua Paik, Samantha Moore, Devon Olds, and Joaquin Castañeda for many useful discussions. The first author was supported by NIH R01 EB022862, NIH R01 NS120581, NSF DMS-1951165, and a Simons Fellowship. The second author was supported by NIH R01 EB022862 and NSF DMS-1951599.

Graph rules for recurrent neural network dynamics: extended version

Contents

1 Introduction

Basic network setup.

Question 1.

Historical interlude: memories as attractors.

Beyond stable fixed points.

2 TLNs and hyperplane arrangements

The set of all fixed points 𝐅𝐏⁡(𝑾,𝒃)\boldsymbol{\operatorname{FP}(W,b)}.

3 Combinatorial threshold-linear networks

Theorem 3.1.

Fun examples.

4 Minimal fixed points, core motifs, and attractors

Question 2.

Definition 4.1.

5 Graph rules

Question 3.

5.1 Examples of graph rules

5.2 Uniform in-degree rule

Definition 5.1.

Theorem 5.2 ([fp-paper]).

5.3 Graphical domination

Definition 5.3.

Theorem 5.4 ([fp-paper]).

Proof.

5.4 Simply-embedded subgraphs and covers

Definition 5.5 (simply-embedded).

Lemma 5.6.

Lemma 5.7.

Proof.

Lemma 5.8 (pairwise gluing).

5.5 Elementary graph rules

6 Gluing rules

Definition 6.1 (simply-embedded covers).

Question 4.

Lemma 6.2.

6.1 Connected unions

Definition 6.3.

Theorem 6.4.

Example.

6.2 Disjoint unions, clique unions, cyclic unions, and linear chains

Definition 6.5.

Theorem 6.6.

Theorem 6.7.

Theorem 6.8.

6.3 Applications of gluing rules to core motifs

Corollary 6.9.

Proof.

Corollary 6.10.

Proof.

6.4 Modeling with cyclic unions

7 Conclusions

7.1 Open Questions

Acknowledgments

References

The set of all fixed points $\boldsymbol{\operatorname{FP}(W,b)}$ .

3 Combinatorial threshold-linear
networks