Recognition of adherent polychaetes on oysters and scallops using Microsoft Azure Custom Vision

1.   Introduction

Coupled cell systems can be studied under several important aspects in a systematic way through network theoretical techniques. In particular, those techniques have been developed and used for networks with gradient and Hamiltonian structures; see for example ^[1,2,3] for gradient networks and ^[4,5,6] for Hamiltonian networks, as well as references therein. These two types of structures have attracted attention in many different directions. We enumerate below some contexts where either structure fits in. There are however some biological systems modelled by networks presenting both structures, namely neural networks given by two subnetworks of excitatory and inhibitory neurons. As an example we consider a dynamical system of neurons which in reality has a very complex behavior. The approach we present generalizes the mathematical model given in ^[7] (see Section 6), but we do not claim a specific result which would explain the real neuron dynamics. The model consists of a pair of continuous variables $(x, y) \in {\Bbb R}^n \times {\Bbb R}^m$ dividing neurons into two groups. The groups of $x$'s and $y$'s are coupled in such a way that within either group the synaptic strengths are symmetric, whereas between groups they are antisymmetric. This kind of system models neurophysiological patterns that have mixed gradient and Hamiltonian structures (see ^[7] and ^[8]). The generating function of such vector field is decomposed as a sum of a potential function $V$ and a Hamiltonian function $H$, so that the ordinary differential equations are

where $J$ denotes a skew-symmetric transformation defined from the synaptic connections. The equations must satisfy an additional admissibility condition on the generating function to be compatible with the network structure. It is now direct from our results that the general form of such function is given by the sum of an admissible gradient function (given in Theorem 5.2) and an admissible Hamiltonian function (given in Theorem 5.7). Furthermore, for these networks we also investigate synchronization inside groups. Synchrony of spiking across neurons is important. There has been a large number of investigations towards the role of synchrony in cognitive and executive processes and, more recently, towards the relevance of synchrony among neurons in some pathological brain states (see ^[9] and references therein). Here we show how to select excitatory-inhibitory synaptic networks supporting synchrony patterns.

Some other contexts of potential applications of our results are the following:

$1.$ Many properties of a Lotka-Volterra system can be expressed geometrically in terms of its associated network. Volterra introduced the system of differential equations

as a model for the competition of $n$ biological species. In this model, $x_j$ represents the number of individuals of species $j$, the $a_{jk}$'s are the interaction coefficients (entries of the adjacency matrix) and the $\epsilon_j$'s are parameters that depend on the environment. The authors in ^[10] prove that in a flow-invariant set there exists a global attractor and the dynamics of the attractor is Hamiltonian.

$2.$ The dynamics of Lotka-Volterra equations having an invariant hyperplane is investigated in ^[3]. It is shown that the dynamics depends on whether the dimension of the phase space is even or odd. While for the even-dimensional case the dynamics is Hamiltonian (with respect to an appropriately chosen Poisson structure), for odd dimensions the dynamics is gradient-like, due to the existence of a global potential function.

$3.$ The networks treated in ^[11] are in the same class we consider here, namely associated with a network with only one type of cell and one type of bidirectional coupling between the cells. The vector field is of difference-coupled type, and synchrony and anti-synchrony are studied. For this kind of systems, the cells have the same internal dynamics, and the coupling between cells is identical, symmetric, and depends only on the difference of the states of the interacting cells. If $V$ denotes the configuration space of each cell, these are given by a vector field $f: V^n \to V^n$ such that the component functions $f_i : V^n \to V$, $i = 1, \ldots, n$, are of the form

for some $\alpha, \delta : V \to V$ and where ${E}$ denotes the set of edges of the network.

$4.$ Closely related to the networks described in the previous item, there are vector fields for which the interest also lies in the behaviour of phase differences between planar unit vector states of coupled cells. This leads to an extra ${\bf S}^1$-symmetry, implying that self-connections in this case are trivial. Functions of this type appear in many applications, including the Kuramoto model (see ^[1], ^[12]) and the Antiferromagnetic XY model (see ^[13,14,15]). Existence and stability of equilibria in this type of systems have also been investigated (see ^[2]).

Gradient and Hamiltonian coupled systems are admissible only by undirected (bidirected) networks. Also, every undirected network admits gradient and Hamiltonian coupled systems; see ^[5] and ^[2]. We refer to ^[16] for dynamics of neural networks over undirected graphs. More generally, for coupled systems associated with any network, there can be flow-invariant spaces (synchrony subspaces where some subsystems evolve synchronously), whose existence is independent of the systems equations and depends only on the network topology. Any coupled system on the network, when restricted to such a synchrony subspace, determines a new coupled system associated with a smaller network (quotient). The original network is said to be a lift of the quotient network. Our goal is to investigate gradient and Hamiltonian structures that can occur in synchrony subspaces on networks in general, having or not that structure. This has come to our attention from examples for which gradient and Hamiltonian dynamics can appear in coupled cell systems that are neither gradient nor Hamiltonian. Section 5 is addressed to explain those questions. We show that the extra structure of being gradient or Hamiltonian for the coupled systems admissible by an undirected network can be lost by the systems admissible by a directed quotient network. Conversely, gradient (Hamiltonian) dynamics can appear for an undirected quotient network of a directed network or of an undirected network whose associated dynamics is not gradient (Hamiltonian). The above results are obtained by characterizing quotients and lifts of undirected networks. We follow here the formalism of Golubitsky, Stewart and co-workers ^[17,18,19] to treat coupled cell systems through network theory. Synchrony in our excitatory-inhibitory synaptic model is investigated here under this point of view (Section 6). There are many other directions of research aiming to understand how the right balance between inhibitory and excitatory cells in the brain is created, and how the disruption of this balance is thought to be critical in conditions of some deseases ^[9,20].

Here is what comes in the next sections. We organize the fundamentals of our study in Section 2. In Section 3 we define and illustrate quotient and lift networks of a given network. In Section 4 we characterize quotients and lifts of undirected networks. Section 5 is devoted to gradient and Hamiltonian coupled systems. In Section 6 we apply our formalism to a model of biological networks of neurons coupled through excitatory and inhibitory synapses.

2.   Preliminaries

In this section we recall the basics about the formalism of addressing coupled cell systems through network theory ^[17,18,19]. Let $G$ be a directed graph with a finite set of vertices $V$ and a finite set of edges $E$. The cells (the dynamical systems) are represented by the vertices and the couplings between the cells are represented by the edges of $G$, to form the coupled cell network. For every edge in $E$, if the corresponding inversed edge also belongs to $E$ the network is said undirected or equivalently, bidirected. This work focuses on undirected networks.

Coupled cell systems admissible by a given network $G$ must be consistent with $G$ in the following way. A set of ordinary differential equations is associated with each vertex (cell). Thus a finite-dimensional vector space $P_v$ is assigned to each vertex $v \in V$. The total configuration space is then $P = \prod_{v \in V} P_v$. Let $x_v$ denote coordinates on $P_v$. The space $P_v$ is called the cell phase space of $v$ and $P$ is the total phase space of the coupled cell system consistent with $G$. Any coupled cell system associated with $G$, for a given choice of $P_v$, is

where the system associated with vertex $v$ takes the form

The first argument $x_v$ in $g_v$ represents the internal dynamics of the cell $v$ and each of the remaining variables $x_{v_p}$ indicates an input edge from cell $v_p$ to the cell $v$. As we are assuming that the input edges directed to any cell $v$ are of the same type, we have that $g_v$ is invariant under any permutation of the corresponding input variables. Moreover, systems associated with cells of the same valency are governed by the same function $g_v$. Vector fields $F$, as well as their associated systems of equations, satisfying the above properties are called $G$-admissible. For instance, if $G$ is a regular network with valency $\ell$, namely the number of edges ponting to each vertex is $\ell$, then an admissible coupled cell system must be given by a unique $g_v$, say $g$, and have the form

where the overbar indicates the invariance of $g$ under any permutation of the vertex coordinates $x_{v_1}, \ldots, x_{v_\ell}$. An example is given by the undirected (bidirected) network of Figure 1.

Example 2.1. Consider the Petersen network (graph) in Figure 1, which is regular of valency $3$. If each vertex phase space is ${\bf{R}}^m$, for some $m \geq 1$, the total phase space is $P = ({\bf{R}}^{m})^{10}$ and the associated coupled cell systems have the form

for some smooth function $g:\ \left({\bf R}^m\right)^4 \to {\bf R}^m$.

One of the phenomena in dynamics explored by the coupled cell network formalism is synchrony between cells, namely when cells have setwise identical behavior. In the next section two distinct synchrony configurations are presented for the Petersen network. The formalism starts with a special type of equivalence in the set $V$ of vertices of the graph $G$ associated with the network. An equivalence relation $\bowtie$ on $V$ is balanced when, for any two vertices $u$ and $v$ in the same $\bowtie$-class, the number of directed edges in $E$ from vertices of each $\bowtie$-class directed to $u$ and to $v$ is the same. Coloring the vertices of the network by choosing one color for each $\bowtie$-class, the coloring is said to be balanced when $\bowtie$ is balanced.

We recall that the adjacency matrix of $G$ is the $n \times n$ matrix, denoted by $A_{G}$, with non-negative integer entries, where the $(i, j)$ entry is the number of directed edges in $E$ from vertex $j$ to vertex $i$. A network $G$ is undirected if and only if its adjacency matrix $A_{G}$ is symmetric.

Given an equivalence relation $\bowtie$ on $V$, we define the polydiagonal subspace of ${\bf{R}}^n$ associated with $\bowtie$ by

Trivially, we have that:

Theorem 2.2. An equivalence relation $\bowtie$ on the set of vertices of a directed network $G$ is balanced if and only if the network adjacency matrix $A_G$ leaves the polydiagonal subspace $\Delta_{\bowtie}$ invariant.

In ^[21] it is proved that the set of all balanced equivalence relations of a network forms a complete lattice taking the relation of refinement. Moreover, an algebraic and algorithmic description of this lattice using the network adjacency matrix eigenvector structure is given in ^[22].

In this setup, a synchrony subspace $\Delta_{\bowtie}$ of $G$ is a polydiagonal subspace which is flow-invariant under any coupled cell system associated with the network structure of $G$. Moreover, a crucial result that characterizes the relations $\bowtie$ for which $\Delta_{\bowtie}$ is indeed a synchrony subspace uses precisely the balanced property. Theorem 4.3 of ^[18], followed by Corollary 2.10 and Theorem 4.2 of ^[22], can be stated in the following way:

Theorem 2.3. Given a network $G$, we have that the following statements are equivalent:

(i) An equivalence relation $\bowtie$ on the network set of vertices is balanced.

(ii) For any choice $P$ of the total phase space, the polydiagonal subspace $\Delta_{\bowtie}$ is a network synchrony subspace.

(iii) The polydiagonal subspace $\Delta_{\bowtie}$ is flow-invariant for all linear admissible vector fields taking the vertex phase spaces to be ${\bf{R}}$.

(iv) The network adjacency matrix leaves the polydiagonal subspace $\Delta_{\bowtie}$ invariant.

Hence, we have two types of criteria to enumerate the synchrony subspaces of a network: one is algebraic using the network adjacency matrix; the other is graph theoretical, by finding the balanced equivalence relations (colorings) of the set of vertices of the network.

3.   Quotients and lifts

Given a balanced equivalence relation on the vertex set $V$ of a directed network $G$, with edge set $E$, the network with vertex set $V/\bowtie$ and edge set given by the edges $([u]_{\bowtie}, [v]_{\bowtie})$, where $(u, v) \in E$, is the quotient network of $G$ by $\bowtie$ and is denoted by $Q = G/\bowtie$. Thus, the set of vertices of $Q$ is formed by one vertex corresponding to each $\bowtie$-equivalence class; the edges are the projections of the edges in the original network. A network $G$ with a finite set of vertices $V$ and a finite set of edges $E$ is a lift of a network $Q$ when $G = Q/\bowtie$ for some balanced relation $\bowtie$ on $V$.

We call valency of a vertex the number of arrows directed to it. So for a regular network its valency is defined as the valency of all its vertices. It follows trivially that:

Remark 3.1. Given a balanced equivalence relation $\bowtie$ on the vertex set of a directed network $G$, the valency of the vertices is an invariant under quotienting and lifting operations. Moreover, $G$ is regular if and only if $G/\bowtie$ is regular.

A relevant observation concerning quotient and lift networks is the following:

Remark 3.2. Fixing $G$ and a balanced equivalence relation $\bowtie$ of $G$, the quotient network $Q = G / \bowtie$ is unique; also, for distinct balanced equivalence relations, the associated quotient networks are distinct in general. On the other hand, fixing a network, say with $k$ vertices, and choosing $n > k$, in general there exist distinct lifts of this network with $n$ vertices; we refer to ^[23] for a systematic method of enumerating the lifts of a network.

As it can easily be seen, the property of being undirected (bidirected) may not be preserved under quotienting and lifting operations. In fact, for most of the undirected networks, there are quotients and lifts that are directed. We finish this section with the Petersen graph, illustrating existence of undirected and directed quotients of a network.

Example 3.3. Let $G$ denote the Petersen network (graph) pictured in Figure 1. Let $\bowtie$ be the equivalence relation on the set of vertices of $G$ with classes

which corresponds to the coloring of the vertices of the Petersen graph presented in Figure 2. We have that $\bowtie$ is balanced: every grey vertex has two inputs from grey vertices and one input from one black vertex, and every black vertex is the input of two black vertices and of one grey vertex. This is equivalent to saying that the order-10 adjacency matrix $A_G$ leaves invariant the linear subspace

Note that the quotient network $G/ \bowtie$ is the $2$-vertex undirected network $Q_1$ in Figure 3, which has adjacency matrix

Moreover, the restriction of $A_G$ to $\Delta_{\bowtie}$ is similar to $A_{Q_1}$.

Consider now the equivalence relation $\bowtie_2$ on the set of vertices of $G$ with classes

corresponding to the coloring as in Figure 4. We have that $\bowtie_2$ is also balanced and $Q_2 = G/ \bowtie_2$ is the directed network of Figure 5. The quotient $Q_2$ has the (non-symmetric) adjacency matrix

4.   Quotients and lifts of undirected networks

In this section, we characterize quotients and lifts of undirected (bidirected) networks. In particular, we identify the quotients and the lifts of undirected networks that are also undirected. These are Theorem 4.1 and Theorem 4.7 below, which are the main results of this section.

Theorem 4.1. An $m$-vertex network $Q$ is a quotient network of an $n$-vertex undirected network $G$ by a balanced equivalence relation on the set of vertices of $G$, with $m < n$, if and only if the entries of the adjacency matrix $A_{Q} = [q_{ij}]_{m \times m}$ of $Q$ satisfy the following: there are positive integers $k_1, \ldots, k_m$ summing $n$ and such that $k_i q_{ij} = k_j q_{ji}$.

Proof. Let $G$ be an $n$-vertex undirected network. Thus its adjacency matrix is an $n\times n$ symmetric matrix. Consider a balanced equivalence relation on its set of vertices and the corresponding quotient network $Q$ with adjacency matrix $A_{Q} = [q_{i, j}]_{m \times m}$. Let $i = \{ i_1, \ldots, i_{k_i} \}$ and $j = \{ j_1, \ldots, j_{k_j} \}$ be any two such equivalence classes. Since the relation is balanced, it follows that the number of edges directed from vertices of the class $j$ to each vertex of the class $i$ is the constant $q_{ij}$. Thus, the total number of directed edges from vertices of $j$ to vertices of $i$ is then $k_i q_{ij}$. Moreover, as $G$ is bidirectional, all these directed edges are bidirectional. It then follows that the total number of directed edges from vertices of class $i$ to vertices of class $j$, which is $k_j q_{ji}$, satisfy

Conversely, let $Q$ be a network with adjacency matrix $A_{Q} = [q_{ij}]_{m \times m}$ such that there are positive integers $k_1, \ldots, k_m$ summing $n > m$ and such that $k_i q_{ij} = k_j q_{ji}$ for all $i, j = 1, \ldots, m$. We construct a symmetric matrix $A$ of order $n$ from the matrix $A_{Q}$ in the following way:

(ⅰ) Consider $A$ as a block matrix with $m \times m$ blocks $Q_{ij}$, with $1 \le i, j \le m$.

(ⅱ) For $i$ and $j$ such that $i \leq j$, define the submatrix $Q_{ij}$ of $A$ as a matrix of order $k_i \times k_j$ with the row sum $q_{ij}$ and column sum $q_{ji}$. If $i = j$ the submatrix $Q_{ii}$ must also satisfy $Q_{ii} = Q_{ii}^T$.

(ⅲ) For $j < i$, set the submatrix $Q_{ji} = Q_{ij}^T$.

It follows that $A$ is symmetric. Let $G$ be the $n$-vertex network with set of vertices $\{1, \ldots, n\}$ and adjacency matrix $A$. It follows that $G$ is bidirectional. Moreover, by construction, the equivalence relation $\bowtie$ on the set of vertices of $G$ with classes $I_1 = \{1, \ldots, k_1\}, \ I_2 = \{ k_1 + 1, \ldots, k_1 + k_2\}, \ \ldots, I_m = \{ k_{m-1} + 1, \ldots, k_m\}$, is balanced and $Q$ is the quotient of $G$ by $\bowtie$. That is, the network $G$ is a bidirectional lift of the network $Q$.

Remark 4.2. In Lemma 4.3 of ^[24], it is obtained that in order for a network to be a quotient of a regular undirected network of valency $v$ then its adjacency matrix satisfies the conditions stated in Theorem 4.1 and the vector $(k_1, \ldots, k_m)$ is a left eigenvalue of that matrix associated with the eigenvalue $v$.

Remark 4.3. We recall that a square matrix $(q_{ij})$ is a combinatorially symmetric matrix if $q_{ij} = 0$ implies $q_{ji} = 0$. From Theorem 4.1, it follows that the adjacency matrix of a quotient network of an undirected network by a balanced equivalence relation on the vertex set is a combinatorially symmetric matrix. Thus a necessary condition for $Q$ to be a quotient network $G/\bowtie$ of an undirected network $G$ under a balanced equivalence relation $\bowtie$ is that, for any two vertices in $Q$, if they are connected then there is at least one bidirectional connection between them.

Remark 4.4. Trivially, in general, there are lifts $G$ of the network $Q$, where $Q = G/ \bowtie$ for balanced $\bowtie$, that are not undirected networks.

Corollary 4.5. Let $Q$ be an $m$-vertex connected network with adjacency matrix $A_{Q} = [q_{ij}]_{m \times m}$ such that there are positive integers $k_1, \ldots, k_m$ summing $n > m$ with $k_i q_{ij} = k_j q_{ji}$. If $k_1, \ldots, k_m$ are coprime then the undirected lifts of $Q$ with the minimum number of vertices have $n = \sum_{i = 1}^m k_i$ vertices.

Proof. The proof follows from the proof of Theorem 4.1. Since $Q$ is connected, we have $k_i \ne 0$, for all $i = 1, \ldots, m$, and so if $(k_1, \ldots, k_m)$ is a solution of the system of equations $k_i q_{ij} = k_j q_{ji}$ with $k_1, \ldots, k_m$ coprime then it is unique. We can then conclude that if $n = \sum_{i = 1}^m k_i$ then there can be no undirected lift of $Q$ having p vertices, with $m < p < n$. Otherwise, we would have to have $p = \sum_{i = 1}^m \frac{k_i}{d}$ for some positive integer $d > 1$, which is impossible given that $k_1, \ldots, k_m$ are coprime.

Example 4.6. Consider the directed network $Q$ given in Figure 6. The adjacency matrix of $Q$ is

The entries of $A_{Q}$ satisfy $q_{12} = 3 q_{21}$, $q_{13} = 2 q_{31}$ and $3 q_{23} = 2 q_{32}$, that is, the matrix satisfies the hypothesis in Theorem 4.1 for $k_1 = 1$, $k_2 = 3$ and $k_3 = 2$. Hence, by Theorem 4.1 the network $Q$ is a quotient of an undirected network $G$ by some balanced equivalence relation of the set of vertices of $G$. Moreover, by Corollary 4.5 the undirected lifts with the minimum number of vertices have $6$ vertices. In fact, the two matrices below are adjacency matrices which realize such undirected networks that have $6$ vertices:

As illustrated in Section 3 and in the above example, given an undirected network $G$ and a balanced equivalence relation $\bowtie$ on its set of vertices, the quotient $Q = G/ \bowtie$ may not be an undirected network. In the next result we give a necessary and sufficient condition for the quotient $Q$ to be a undirected network.

Theorem 4.7. Let $Q$ be an $m$-vertex quotient network of an $n$-vertex undirected network $G$, with $m < n$, associated with a balanced equivalence relation $\bowtie$ on the vertices of $G$. The quotient network $Q$ is undirected if, and only if, for each pair of connected vertices in $Q$, the corresponding $\bowtie$-classes on the set of vertices of $G$ have the same cardinality.

Proof. Let $G$ be an $n$-vertex undirected network and $Q$ an $m$-vertex quotient network of $G$ associated with a balanced equivalence relation $\bowtie$, with classes $I_i$ for $i = 1, \ldots, m$, where $n > m$. Denote the cardinality of class $I_i$ by $k_i$, for $i = 1, \ldots, m$ and so the sum of $k_1, \ldots, k_m$ is $n$. Take the adjacency matrix $A_Q = [q_{ij}]$ of $Q$ according to the first part of the proof of Theorem 4.1. Thus the positive integers $k_1, \ldots, k_m$ satisfy $k_i q_{ij} = k_j q_{ji}$. In particular, we have that $q_{ij} = 0$ if and only if $q_{ji} = 0$. Take $i, j$ such that $i\not = j$ and $q_{ij} \not = 0$. If $q_{ij} = q_{ji}$ and $k_i q_{ij} = k_j q_{ji}$ then $k_i = k_j$, that is, the classes $I_i$ and $I_j$ have the same cardinality. Conversely, if $k_i = k_j$ and $k_i q_{ij} = k_j q_{ji}$, then $q_{ij} = q_{ji}$. Thus $A_Q$ is symmetric if, and only if, for every pair of vertices $i, j$ of $Q$ which are connected, that is, such that $q_{ij} \not = 0$, the classes $I_i$ and $I_j$ have the same cardinality.

Example 4.8. Consider the $6$-vertex undirected network $G$ in Figure 7 with adjacency matrix

Also, consider the following two balanced equivalence relations on the set of vertices of $G$: $\bowtie_1 = \{ \{ 1, 2\}, \{3, 4 \}, \{5, 6 \} \}$ and $\bowtie_2 = \{ \{ 1, 2, 3, 4\}, \{5 \}, \{6 \} \}$. For each relation, there are connections between vertices of any class to vertices of any other class. Since the cardinality of all the $\bowtie_1$-classes is the same, it follows from Theorem 4.7 that the corresponding quotient network $Q_1 = G / \bowtie_1$ (Figure 8 (a)) must be undirected; in fact, the adjacency matrix of $Q_1$ is the symmetric matrix

Since the cardinality of the $\bowtie_2$-classes is not the same, it follows from Theorem 4.7 that the quotient network $Q_2 = G/ \bowtie_2$ (Figure 8 (b)) is not undirected; in fact, the adjacency matrix of $Q_2$ is the non-symmetric matrix

Corollary 4.9. If an $n$-vertex undirected network has an $m$-vertex connected undirected quotient network for a balanced relation of its set of vertices, where $n > m$, then $n$ is a multiple of $m$.

We apply now the previous results to characterize the lifts of undirected networks using balanced equivalence relations.

Corollary 4.10. Let $Q$ be an undirected network. We have that for any undirected lift $G$ of $Q$, where $Q = G/ \bowtie$ and $\bowtie$ is a balanced equivalence relation on the set of vertices of $G$, any two connected vertices in $Q$ must unfold to the same number $r$ of vertices in $G$. Moreover, the lift network $G$ has no multiple connections if and only if that number of vertices is greater or equal to the number of connections between the two quotient vertices.

Proof. Let $Q$ be an undirected network and $G$ an undirected lift of $Q$. Let $I_i$ and $I_j$ be any two connected vertices of $Q$. By Theorem 4.7 the $\bowtie$-equivalence classes $I_i$ and $I_j$ of the lift network $G$ have the same number $r$ of vertices.

Let $q_{ij} = q_{ji} = s$ be the number of connections between $I_i$ and $I_j$ in the network $Q$. Thus, each vertex in the class $I_i$ receives $s$ connections from the vertices in the class $I_j$ and, analogously, each vertex in the class $I_j$ receives $s$ connections from the vertices in the class $I_i$.

If the lift $G$ has no multiple connections then each vertex in the class $I_i$ receives exactly one connection from one same vertex in the class $I_j$, which means that there must exist at least $s$ vertices in the class $I_j$. Analogously, each vertex in the class $I_j$ receives exactly one connection from one same vertex in the class $I_i$, which means that there must exist at least $s$ vertices in the class $I_i$. Thus, it must be $r \ge s$.

Theorem 4.11. Let $Q$ be an $m$-vertex undirected connected network with multiple edges. Take $p$ as the maximum of the entries of the adjacency matrix of $Q$. Then:

(i) The undirected lifts $G$ of $Q$, where $Q = G/ \bowtie$ for balanced $\bowtie$, with no multiple edges have $mr$ vertices with $r \geq p$.

(ii) For any $r \geq p$ there are undirected lifts $G$ of $Q$, where $Q = G/ \bowtie$ for balanced $\bowtie$, with no multiple edges and $mr$ vertices.

Proof. Let $Q$ be an $m$-vertex undirected connected network with multiple edges and take $p$ as the maximum of the entries of the adjacency matrix of $Q$. Let $G$ be an undirected lift of $Q$, where $Q = G/ \bowtie$ for balanced $\bowtie$.

(ⅰ) As $Q$ is undirected, applying Theorem 4.7, it follows that if there is any connection between two vertices then they both unfold to the same number $r$ of vertices in $G$. As $Q$ is connected, it follows that there is a directed path linking all the vertices of $Q$. Thus all the vertices must unfold to the same number $r$ of vertices in $G$. As it is required that $G$ has no multiple edges, then $r \geq p$. Thus any such lift has $mr$ vertices with $r \geq p$.

(ⅱ) Let $r \geq p$ and denote the adjacency matrix of $Q$ by $A_{Q} = [q_{ij}]_{m \times m}$. Following the procedure in the second part of the proof of Theorem 4.1, with $k_1 = \cdots = k_m = r$, we build, from the matrix $A_{Q}$, a symmetric matrix $A$ of order $mr$ with all the entries equal to 0 or $1$. By construction, the symmetric matrix $A$ is the adjacency matrix of an undirected lift of $Q$ with no multiple edges, $mr$ vertices where each vertex in $Q$ unfolds to $r$ vertices, and where $Q = G/ \bowtie$ for balanced $\bowtie$.

Example 4.12. Consider the $3$-vertex undirected network presented in Figure 9. Note that it is connected and it has adjacency matrix

Two possible undirected lifts with no multiple edges are the $9$-vertex and $12$-vertex networks with adjacency matrices given, respectively, by

5.   Coupled cell systems

Fixing a network $G$ and one of its synchrony subspaces $\Delta_{\bowtie}$, the restriction of any coupled cell system associated with $G$ is a coupled cell system consistent with the quotient network $Q = G/\bowtie$. Moreover, any admissible vector field of $Q$ can be seen as the restriction to $\Delta_{\bowtie}$ of an admissible vector field of $G$ ([18,Theorem 5.2]). To illustrate we consider again the Petersen graph:

Example 5.1. Let $G$ denote the network given by the Petersen graph (Figure 1) and consider the balanced equivalence relation $\bowtie_2 = \left\{ \{1, 3, 9, 10\}, \, \{ 2, 7\}, \, \{4, 5, 6, 8\}\right\},$ corresponding to the coloring of its vertices presented in Figure 4. Choosing the representatives $1, 2, 4$ of the $\bowtie_2$-classes, we have that the equations (2.1) restricted to $\Delta_{\bowtie_2}$ are

which are consistent with the quotient network $Q_2 = G / \bowtie_2$ (Figure 5).

The importance of the existence of flow-invariant subspaces under the dynamics of a system has been long recognized and explored. For example, flow-invariant subspaces can imply the existence of non-generic dynamical behavior such as heteroclinic cycles and networks, leading to complex dynamics. In the context of coupled cell systems, synchrony subspaces are examples of flow-invariant spaces, having an important role in understanding the dynamics of the coupled cell systems associated with a given network. Moreover, the restriction of the dynamics of a coupled cell system to a synchrony subspace is again a coupled cell system whose structure is consistent with a network that has fewer vertices (the quotient network), with a lower-dimensional phase space, and potentially with known dynamics. The dynamics of the quotient can then be lifted to the overall phase space and give full information concerning the dynamics on those synchrony subspaces. Moreover, the knowledge of the set of all synchrony subspaces of a coupled cell network and the associated quotients can be used, for example, to investigate the possibility of the associated coupled cell systems to support heteroclinic behavior. See for example ^[25,26].

In ^[2], gradient coupled cell systems are addressed and it is shown that only undirected networks can have admissible coupled cell systems with gradient structure. An analogous result is obtained in ^[5] for Hamiltonian coupled cell systems. Moreover, there are in general coupled cell systems associated with undirected networks that are neither gradient nor Hamiltonian. Nevertheless, for undirected networks, there are always coupled cell systems with each one of those structures, as explained in ^[2,5]. The next two subsections are devoted to these two types of coupled cell systems.

Throughout, the total number of cells in a coupled system is denoted by $n$ and we take coordinates on the (identical) cells so that the cells state space is ${\bf{R}}^m$, for some $m \geq1$.

5.1.   Gradient coupled cell systems

In this section we investigate quotients and lifts of undirected networks related to gradient structure, that is, associated with a coupled dynamical system given by the (negative) gradient of a smooth function $f: P \to { {\bf{R}} }$,

where $x = (x_1, \ldots, x_n)$ denotes the state variable of the total phase space $P = ({ {\bf{R}} }^m)^n$ and, for $i = 1, \ldots n,$ $x_i \in { {\bf{R}} }^m$ is the variable of cell $i$.

The function $f$ whose gradient is an admissible vector field for a given network $G$ is called an admissible gradient function for $G$. Hence, the gradient structure of a coupled system is in one-to-one correspondence with the existence of an admissible gradient function associated with it. We also notice that a necessary condition for an admissible vector field to be gradient is that each individual cell to be also gradient.

In ^[2] the characterization of admissible gradient functions is given for undirected networks with no multiple edges. We remark that the result generalizes directly for undirected networks with multiple edges and loops. The result is given in Theorem 5.2 below.

We first recall that a network is called bipartite if its set of vertices $\mbox{ ${\mathcal{V}}$ }$ can be devided into two disjoint subsets $\mbox{ ${\mathcal{V}}$ }_1$ and $\mbox{ ${\mathcal{V}}$ }_2$ such that every edge of $G$ connects a vertex in a subset to a vertex in the other. If the network is bipartite, we reorder the numbering of cells if necessary so that $\mbox{ ${\mathcal{V}}$ }_1 = \{1, \ldots, r\}$ and $\mbox{ ${\mathcal{V}}$ }_2 = \{r+1, \ldots, n\}$, $r > 1$, and $A_G$ is an order-$n$ matrix of the block form

We then have:

Theorem 5.2. Let $G$ be an undirected network that may have multiple edges and loops, and let $A_{G}\; = \; (a_{ij})$ denote the adjacency matrix of the network $G$. A function $f: P \to { { {\bf{R}} }}$ is an admissible gradient function associated with $G$ if, and only if, there exist smooth functions $\alpha : {\bf{R}}^m \to {\bf{R}}$ and $\beta : {\bf{R}}^{2m} \to {\bf{R}}$ such that

If $G$ is bipartite and in addition there exist $v_i \in \mbox{ ${\mathcal{V}}$ }_1$ and $v_j \in \mbox{ ${\mathcal{V}}$ }_2$ with same valency, or if $G$ is not bipartite, then $\beta$ is invariant under permutation of the vector variables.

Proof. It follows the steps of the proof of [2, Theorem 2.4]. The main idea behind that proof is the fact that the component $g_v$ of an admissible vector field in the direction of a vertex $v \in V$ is an invariant function under any permutation of the corresponding input variables, say $u_1, \ldots u_\ell$, for some $\ell \geq 1$. The graphs in [2, Theorem 2.4] have no multiple edges, in which case $g_v$ is of the form

with $u_i \neq u_j$ for $i \neq j$, $i, j = 1, \ldots \ell$. As a consequence, the coupling term of the admissible function $f$ is a sum of one law in two variables applied to each $(x_{v_i}, x_{v_j})$ whenever there is an edge from vertex $v_i$ to vertex $v_j$, which is at most one edge in this case. If there are multiple edges to a vertex $v$, then $g_v$ is still of the form above, but with repeating vertex variables under the permutation bar. If $v_i$ is such a vertex, then there are $a_{ij}$ edges from $v_i$ to $v_j$, $j = 1, \ldots, a_{ij}$. These edges will then contribute with $a_{ij}$ equal terms in the sum of coupling terms.

Example 5.3. The simplest network with multiple edges is given in Figure 10. From Theorem 5.2, choosing the cell phase spaces to be ${\bf{R}}$, the function $f: {\bf{R}}^2 \to {\bf{R}}$,

is an admissible gradient function for this network.

Example 5.4. Consider the network of Figure 8. From Theorem 5.2, the general form of the admissible gradient functions associated with this network is given by

with $\beta(x, y) = \beta(y, x)$.

It is a consequence of Theorem 4.11 that any undirected network admits an undirected lift. We remark that an admissible vector field associated with an undirected network can admit a restriction to an invariant subspace with a gradient dynamics even if it is not of a gradient type, as we illustrate in the next example.

Example 5.5. Consider the undirected network of Figure 11. We recall from [2, Lemma 2.2] that for any network with more than three vertices, a necessary condition for a function $f$ to be admissible for this network is that

for any two-by-two distinct cells $i, j, k$. It then follows that the system of equations

defines a coupled cell system admissible for the network of Figure 11 which is not gradient. As the equivalence relation $\bowtie$ with classes $\{1, 3\}$ and $\{2, 4\}$ is balanced for this network, we have that $\Delta_{\bowtie} = \{ {\bf x}:\, x_1 = x_3, \ x_2 = x_4\}$ is a synchrony subspace. Moreover, the corresponding quotient is the network given in Figure 10. Equations (5.6) restricted to $\Delta_{\bowtie}$ correspond to:

corresponding to a gradient coupled cell system admissible for the network in Figure 10. Note that $f/2$, for $f$ as in (5.3), is an admissible gradient function for it.

We finally observe that, as more naturally expected, gradient admissible vector fields can also be lifted to vector fields that are still gradient.

Example 5.6. The vector field (5.7) associated with the network of Figure 10 can be lifted to an admissible vector field for the network of Figure 11 which is gradient. In fact, taking $\tilde{f}: {\bf{R}}^4 \to {\bf{R}}$,

for $\beta(x, y) = - 1/2(x^2y + x y^2)$, we have that $\tilde{f}$ is an admissible gradient function for the network of Figure 11 which restricts to (5.3) on the synchrony subspace $\Delta$. That is, the restriction of the admissible gradient function $\tilde{f}$ for the network of Figure 11 is an admissible gradient function for its quotient network in Figure 10.

5.2.   Hamiltonian coupled cell systems

In this section quotients and lifts of undirected networks related to a Hamiltonian dynamical systems are investigated. A Hamiltonian coupled dynamical system is a system defined from ordinary differential equations

where

The variable vectors $q = (q_1, \ldots, q_n)$ and $p = (p_1, \ldots, p_n)$ are called position and momentum vectors, respectively, and form the total phase space $P = ({\bf{R}}^{2m})^n$ where, for $i = 1, \ldots n,$ $(q_i, p_i) \in {\bf{R}}^{2m}$ are the position and momentum variables of each cell.

The function $h: {\bf{R}}^{mn} \times {\bf{R}}^{mn} \to {\bf{R}}$ satisfying (5.8) is the Hamiltonian function of the system, and when this system of equations is a coupled system associated with a given network $G$ this is called an admissible Hamiltonian function for $G$. Hence, the Hamiltonian structure of a coupled system is in one-to-one correspondence with the existence of an admissible Hamiltonian function associated with it. In addition, a necessary condition for an admissible vector field to be Hamiltonian is that each individual cell be also Hamiltonian.

In the following theorem we characterize the admissible Hamiltonian functions of any undirected network. This corresponds to Theorem 5.2 of the previous section adapted to the Hamiltonian setup.

Theorem 5.7. Let $G$ be an undirected network that may have multiple edges and loops, and let $A_{G}\; = \; (a_{ij})$ denote the adjacency matrix of the network $G$. A function $h: P \to { {\bf{R}} }$ is an admissible Hamiltonian function associated with $G$ if, and only if, there exist smooth functions $\alpha : {\bf{R}}^{2m} \to {\bf{R}}$ and $\beta : {\bf{R}}^{2m} \times {\bf{R}}^{2m} \to {\bf{R}}$ such that

If $G$ is bipartite and in addition there exist $v_i \in \mbox{ ${\mathcal{V}}$ }_1$ and $v_j \in \mbox{ ${\mathcal{V}}$ }_2$ with same valency, or if $G$ is not bipartite, then $\beta$ is invariant under the permutation $\sigma(q_i, q_j, p_i, p_j) = (q_j, q_i, p_j, p_i)$.

Proof. It is the same as the proof of Theorem 5.2. To see this, consider the similarity between the expressions (5.2) and (5.9) so that the algebraic arguments used to prove the result for an admissible gradient function in the first case hold to construct an admissible Hamiltonian function for the second. For the present case, it is crucial to notice that (5.5) holds by replacing each $x_l$, for $l = i, j, k,$ by $q_l$ and $p_l$.

Example 5.8. Consider the network of Figure 10. Taking the cell phase spaces to be ${\bf{R}}$, the function $h: {\bf{R}}^4 \to {\bf{R}}$ defined by

is an admissible Hamiltonian function for this network.

As expected from the discussion in Section 5.1 for gradient coupled systems, an admissible vector field associated with an undirected network can admit a restriction to an invariant subspace with a Hamiltonian dynamics even if it is not Hamiltonian, as we illustrate in the next example.

Example 5.9. As before, consider the undirected network of Figure 11. Note that the following coupled cell system

is admissible for that network but it is not Hamiltonian. However, its restriction to the synchrony subspace $\Omega = \{ ({\bf q}, {\bf p}):\, (q_1, p_1) = (q_3, p_3) \ (q_2, p_2) = (q_4, p_4)\}$, leads to the quotient network given in Figure 10 with reduced equations

These equations define an admissible Hamiltonian coupled cell system for the quotient network in Figure 10. Note that $h/2$, for $h$ as in (5.10), is an admissible Hamiltonian function for this quotient network.

Again as for gradient coupled systems, admissible Hamiltonian systems can also be lifted to vector fields that are still Hamiltonian.

Example 5.10. The admissible and Hamiltonian coupled cell system (5.12) associated with the network of Figure 10 can be lifted to a coupled cell system which is admissible and Hamiltonian for its lift of Figure 11. Notice that $\tilde{h}: ({\bf{R}}^4)^2 \to {\bf{R}}$ defined by

for $\beta(x, y, z, w) = 1/2 (z^2y + 2w^2x)$, is an admissible Hamiltonian function for this network which restricts to (5.10) on the synchrony subspace $\Omega$.

5.3.   Gradient and Hamiltonian coupled cell systems

The general form of the gradient admissible functions and Hamiltonian admissible functions for $G$ and $Q$ are related in the following way:

Proposition 5.11. Let $G$ be an undirected network and let $\bowtie$ be a balanced relation on the set of vertices of $G$ defining an undirected connected quotient network $Q = G/\bowtie$. Let $f^G$ ($h^G$) be a gradient (Hamiltonian) admissible function of a gradient (Hamiltonian) coupled cell system of $G$. Then, there is a gradient (Hamiltonian) admissible function $f^Q$ ($h^Q$) for the coupled cell system of $G$ restricted to $\Delta_{\bowtie}$, such that

where $k$ is the cardinality of the $\bowtie$-classes.

Proof. It follows from Theorem 4.7 that the cardinality $k$ of every $\bowtie$-class is the same. The result then follows from Theorems 5.2 and 5.7 and the definition of quotient network.

Corollary 5.12. Let $G$ be an undirected network and let $\bowtie$ be a balanced relation on the set of vertices of $G$ defining an undirected quotient network $Q = G/\bowtie$. Then:

(i) The gradient (Hamiltonian) admissible functions for $G$ restricted to the synchrony subspace determined by $\bowtie$ are gradient (Hamiltonian) admissible functions for $Q$.

(ii) A gradient (Hamiltonian) admissible function for $Q$ is a restriction of a gradient (Hamiltonian) admissible function for $G$.

As we have shown, from our results, it follows that gradient and Hamiltonian dynamics can appear in coupled cell systems that are neither gradient nor Hamiltonian. This already comes from the fact that non undirected networks can often admit quotient networks by balanced relations that are undirected. But this comes also from the more subtle situation in the level of undirected networks, for which gradient and Hamiltonian structure can occur on proper synchrony subspaces.

For a given gradient (or Hamiltonian) coupled cell system associated to an undirected network $G$, we are also able to identify the flow invariant subspaces of the total phase space where the restriction of the dynamics is still gradient (or Hamiltonian). These are precisely the subspaces defined by each balanced relation $\bowtie$ for which $Q = G/\bowtie$ is undirected.

Example 5.13. Consider a gradient coupled cell system associated with the undirected network $G$ in Figure 7, part of the gradient dynamics of the system appears in the restriction to the synchrony subspace $\Delta_{\bowtie_1} = \{ x: \, x_{1} = x_{2}, \ x_{3} = x_{4}, \ x_{5} = x_{6} \}$ but not in the restriction to the synchrony subspace $\Delta_{\bowtie_2} = \{ x: \, x_{1} = x_{2} = x_{3} = x_{4} \}$. The same goes for Hamiltonian dynamics.

6.   Neural networks with excitatory and inhibitory synaptic coupling

In simple terms, there are two types of neurons in the brain, namely those that increase activity in other cells (excitatory neurons) and those that decrease activity (inhibitory neurons); see ^[20]. In addition, this interaction and the dynamical behavior of a gradient vector field is related to artificial learning mechanisms and learning processes in biological neural networks. In ^[7], the authors propose a system of polynomial differential equations to model an excitation-inhibition interaction between two groups of neurons. Here we follow their same idea of decomposing the governing vector field in a gradient part and a Hamiltonian part. We use our results to present the general form of the vector field. As we shall see, this depends on the conditions on the potential and Hamiltonian generating functions combined with the graph structure of the neural network.

Neurons inside each group are assumed to be identical with identical synapses of gradient type, and synapses between neurons of distinct groups are Hamiltonian and all identical. A schematic neural network of this type is given by a graph $G = (V, E)$, where each vertex represents one neuron and each edge represents a synapse. Let $V_1, V_2$ denote the set of vertices representing $n$ excitatory and $m$ inhibitory neurons, respectively, $n, m \geq1$. Let $E_1$ denote the set of edges representing the synapses inside $V_1$ and $E_2$ inside $V_2$. The adjacency matrix of this graph is a matrix of order $n+m$ of the form

where $A_{G_1} = (a_{ij}^{G_1})$ and $A_{G_2} = (a_{ij}^{G_2})$ are the adjacency matrices of the subetaaphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$, respectively, and $A_H$ is the matrix of adjacencies between vertices of $V_1$ and $V_2$. Figure 12 represents schematically the two groups in two layers.

The general system of ordinary differential equations defined on ${\Bbb R}^n \times {\Bbb R}^m$ is given by

where $J$ is the skew-symmetric transformation with matricial form

If $a_{ij}^{H} \neq 0$, the pair ($x_i, y_j)$ is a Hamiltonian synapse, which is $(q_k, p_k)$, for some $k$, in Subsection 5.2, so the sum of couplings in expression (5.9) is written here as

with no restrictions on the coupling function $\beta_H$. It now follows from Theorems 5.2 and {5.7 that the generating function for such network is $g = f + h$, where

and

with the conditions of invariance under permutation of variables on the two coupling functions $\beta_{G_{1}}$ and $\beta_{G_{2}}$ as given in the two theorems.

It follows that the excitation-inhibition configuration is realized in such model if the synapses between groups are sufficiently stronger than interior synapses. For example, consider the network given in Figure 12. The graph structure of this network implies that $\beta_{G_1}$ and $\beta_{G_2}$ are invariant under permutation of variables, so the generating function is of the form

for some constants $a, b, c, \alpha, \beta$. The excitation-inhibition configuration is realized in such model if, for example,

As pointed out in ^[27], synchronous activities of neurons are driven through the synaptic connectivity of excitatory and inhibitory neurons, and in order to understand how neural networks generate these or more complex patterns of activity underlying behaviors, it is necessary to understand both the specific patterns of connectivity between neurons and how individual neurons respond to the inputs that they receive. In our theoretical model, synchronyzation is realized from its graph structure. Patterns of synchrony in excitatory-inhibitory networks are derived from quotients of graphs supporting gradient and Hamiltonian structures, and these are precisely those defined from balanced equivalence relations on the sets of vertices whose equivalence classes have the same cardinality, from Theorem 4.7. As a direct consequence, in the network given in Figure 12 the excitatory neurons and inhibitory neurons synchronyze in pairs, $x_1 = x_3$, $x_4 = x_6$ and $y_1 = y_3$, $y_2 = y_4$.

Acknowledgments

The authors thank the comments of the referees that have contributed to clarify some remarks and their suggestion of including an example illustrating some of the results of the paper. The first two authors were partially supported by CMUP (UID/MAT/00144/2019), which is funded by FCT with national (MCTES) and European structural funds through the programs FEDER, under the partnership agreement PT2020. M.M. acknowledges partial support by CAPES under CAPES/FCT grant 99999.008523/2014-02. She also thanks University of Porto for their great hospitality during the visit when this work was carried out.

Conflict of interest

The authors declare there is no conflicts of interest.