Fibration symmetry

Fibration symmetry is a mathematical notion of symmetry in networks that overcomes the limitations of classical group-theoretic symmetry through automorphisms. It is based on the theory of graph fibrations and provides a natural framework for understanding robust cluster synchronization and functional organization in complex networks, especially in biological and dynamical systems. Unlike global symmetries defined by automorphism groups, fibration symmetries are local, structural, and robust under perturbations, making them particularly suited to biological networks such as gene regulatory networks and neural circuits.

Overview

Traditionally, symmetries of an object are described by an automorphism, that is, an isomorphism of the object to itself. This idea applies also to graphs. For example, consider the simple graph $G$ with node set $N_G=\{1,2,3,4,5\}$ and adjacency matrix

$$A_G=\left(\begin{array}{ccccc}0& 1& 1& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0\end{array}\right)$$

The permutation $\pi :N_G\to N_G$ defined (in cycle notation) by $(45)(23)$ is a non-trivial automorphism of $G$: if we apply this permutation simultaneously to the rows and columns of the adjacency matrix of the graph we obtain the matrix itself. The application of $\pi$ to the graph can be seen as a renaming of its nodes:

The application of an automorphism to a graph can be seen as a node renaming.

The set $\mathrm{A}\mathrm{u}\mathrm{t}(G)$ of all automorphisms of the graph $G$ is a group with respect to functional composition. This group induces an equivalence relation between nodes: two nodes $x$ and $y$ are equivalent if there is an automorphism $\pi$ of $G$ such that $y=\pi (x)$. This equivalence relation describes which nodes can be exchanged by an automorphism.

A graph with nodes colored according to the orbit of the automorphism group they belong to.

Here you can see that nodes 4 and 5 are exchanged by an automorphism, and the same is true for nodes 2 and 3. In fact, the automorphism group of this graph contains only one non-trivial automorphism, the one we described above.

In many real-world networks—especially biological ones—classical symmetries in the sense of graph automorphisms are rare or absent. Nevertheless, such systems often display synchronized behavior among subsets of nodes, known as cluster synchronization. Fibration symmetry explains how such synchronized clusters arise independently of global symmetry groups.

The theory shows that cluster synchronization is governed by local structural equivalence, formalized through graph fibrations, balanced colorings, and equitable partitions. These structures identify nodes that necessarily evolve identically under any admissible dynamics compatible with the network topology.

Historical background

Graph fibrations were introduced in graph theory and distributed computing by Paolo Boldi and Sebastiano Vigna in their study of structural graph mappings.

Independently, related ideas appeared in the theory of coupled dynamical systems, where synchronization phenomena were studied using symmetry groups and later groupoids, notably by Martin Golubitsky and Ian Stewart.

The unification of these approaches led to the modern theory of fibration symmetry, which connects graph theory, dynamical systems, and biological network analysis. This synthesis is presented systematically in Symmetries of Living Systems: Symmetry Fibrations and Synchronization in Biological Networks.

Mathematical definition

Graph fibrations

Given two directed graphs $G$ and $B$, a graph fibration is a graph homomorphism $\phi :G\to B$ that satisfies the lifting property:

For every edge $e^{\prime }$ in $B$ targeting a node $\phi (v)$, and for every node $v$ in $G$, there exists a unique edge $e$ in $G$ targeting $v$ such that $\phi (e)=e^{\prime }$.

This condition ensures that the input structure of each node is preserved under the mapping.

A fibration from a graph G (on the left) and the graph B (on the right).

In the figure above you can see a graph $G$ (on the left) and another graph $B$ on the right. Between the two there is a morphism $\phi :G\to B$ defined on nodes as

${\phi }_N:\left(\begin{array}{ccccccc}1& 2& 3& 4& 5& 6& 7\\ b_1& b_{23}& b_{23}& b_{45}& b_{45}& b_6& b_7\end{array}\right)$

and on arcs as

${\phi }_A:\left(\begin{array}{ccccccccc}a& b& c& d& e& f& g& h& i\\ a^{\prime }& b^{\prime }& c^{\prime }& c^{\prime }& e^{\prime }& e^{\prime }& g^{\prime }& g^{\prime }& i^{\prime }\end{array}\right).$

It is easy to verify that this is a homomorphism and, in fact, a fibration.

Fibration symmetry

The preimage of a node in the base graph $B$ is called a fiber: fibers define implicitly an equivalence relation on the nodes of the graph G. Nodes in the same fiber have isomorphic input trees, meaning they receive structurally identical information from the rest of the network. The base graph represents the dynamics of these fibers collapsed into single nodes.

For every graph $G$ there exist a smallest graph over which $G$ can be fibred, called its minimum base $\hat{G}$. The minimum base is unique (up to isomorphism), although there can be many fibrations $G\to \hat{G}$: those fibrations (called minimal fibrations of $G$) can only differ from one another for how they map parallel arcs. So the fibers of all minimal fibrations are the same. The equivalence relation those fibers define is called the fibration symmetry of $G$.

The fibration displayed above is in fact a minimal fibration, and the fibration symmetry of the graph above is the following (nodes with the same color belong to the same minimum fiber):

The graph G above with its fibration symmetry.

It is worth mentioning that the graph $G$ in this example does not have any non-trivial automorphism. This is because node 7 breaks the natural symmetry that the graph would otherwise possess. Nonetheless, fibrations do not take outgoing arcs into account, and for this reason it does not interfere with the formation of natural synchronization clusters.

Equivalent formulations

Fibration symmetry admits several mathematically equivalent characterizations:

• Balanced colorings: a coloring of nodes such that nodes of the same color receive the same multiset of colors from their incoming neighbors.
• Equitable partitions: partitions of the node set where each node in a part has the same number of incoming edges from every other part.
• Symmetry groupoids: local symmetry structures generalizing groups, capturing input-preserving isomorphisms without global closure.

These formulations describe the same synchronization constraints from different disciplinary viewpoints.

In the following, we shall delve in the groupoid formalism.

Groupoid formalism

As mentioned above, the natural algebraic structure for the symmetries of basic physics is a group. The analogous structure for fibration symmetries is the more general concept of a groupoid. An automorphism is global in nature. A more relevant concept for synchrony patterns is that of an isomorphism between input sets, that is, sets of all input edges to a given node.

This type of constraint on an ordinary differential equation (ODE) is local and more general than group symmetry. The set of all such input isomorphisms naturally forms a groupoid. A groupoid resembles a group, except that composition of elements may not be defined. This happens because each node provides a base point for its input set, and composition must be compatible with these base points.

Groupoids were introduced by Heinrich Brandt in 1927 and have since been developed systematically within category theory and algebraic topology.

They can be characterized as categories in which every morphism is invertible (see Higgins 1971, Chapter 1, page 5, or Mac Lane 1998, Chapter 1, page 20).

In more detail, a groupoid $({ℐ},\mathrm{\Theta })$ consists of:

1. A set ${ℐ}$ of objects $i$.
2. For each $(i,j)\in {ℐ}\times {ℐ}$, a set $\mathrm{\Theta }(i,j)$ of morphisms (which may be empty). Instead of writing $\theta \in \mathrm{\Theta }(i,j)$, the more intuitive notation $i\stackrel{\theta }{\to }j$ is often used. The $\mathrm{\Theta }(i,j)$ are assumed disjoint. The set of all morphisms is the disjoint union $\mathrm{\Theta }=\bigcup \mathrm{\Theta }(i,j)$.
3. For each $i\in {ℐ}$, the set $\mathrm{\Theta }(i,i)$ contains a distinguished morphism ${ϵ}_i$.
4. There is a composition rule $(\theta ,\varphi )\mapsto \varphi \theta$ whenever $i\stackrel{\theta }{\to }j\stackrel{\varphi }{\to }k$, and $i\stackrel{\varphi \theta }{\to }k$.
5. Identitities: If $i\stackrel{\theta }{\to }j$ then $\theta {ϵ}_i=\theta ={ϵ}_j\theta$.
6. Inverses: If $i\stackrel{\theta }{\to }j$ there exists $j\stackrel{\varphi }{\to }i$ such that $\varphi \theta ={ϵ}_i$ and $\theta \varphi ={ϵ}_j$. We write $\varphi ={\theta }^{-1}$.
7. Associativity: If $i\stackrel{\theta }{\to }j\stackrel{\varphi }{\to }k\stackrel{\psi }{\to }l$ then $(\psi \varphi )\theta =\psi (\varphi \theta )$.

Note that, unlike a group, a groupoid has a different identity element for each object.

Network Groupoids

The connection between networks and groupoid theory centers on the groupoid ${{ℬ}}_{{𝒢}}$ of a general network ${𝒢}$.

The objects ${ℐ}$ of ${{ℬ}}_{{𝒢}}$ are the input sets $I(c)$ of nodes $c\in {𝒞}$. We can identify these objects with the corresponding nodes. Each node $c$ acts as a distinguished base point for $I(c)$, and is the unique node that equals ${\mathscr{H}}(i)$ for all $i\in I(c)$.

The morphisms of ${{ℬ}}_{{𝒢}}$ in $\mathrm{\Theta }(c,d)$ are the input isomorphisms $\beta :I(c)\to I(d)$; that is, bijections that preserve the type of the node and the types of input edges. The usual notation in network dynamics is $B(c,d)$ and henceforth this is synonymous with $\mathrm{\Theta }(c,d)$.

The network groupoid ${{ℬ}}_{{𝒢}}$ of ${𝒢}$ is the disjoint union

${{ℬ}}_{{𝒢}}=\underset{c,d}{⨆}B(c,d)$

with the operation of composition (where possible). It is easy to prove that ${{ℬ}}_{{𝒢}}$ is a groupoid under composition of input isomorphisms.

Admissible maps and ODEs

In a dynamic interpretation, each node $i$ of a (directed) graph $G$ represents a state variable $x_i$, and directed edges indicate couplings. We model dynamics of the nodes by admissible ODEs , which have the form

${\dot{x}}_i=f_i(x_i,x_{j_1},x_{j_2},\dots )(1\le i\le n)$

where there are $n$ nodes, $j_1,j_2,\dots$ are the source (tail) nodes of input edges to the target (head) node $i$, and ${\dot{x}}_i$ indicates the time derivative of $x_i$. The form of the equation above means that the dynamics respects the topology of the network. In particular it correctly represents which nodes talk to which, and how.

Groupoid equivariance

The role of the network groupoid ${{ℬ}}_{{𝒢}}$ with regard to fibration symmetries is analogous to that of the automorphism group for global symmetries. The definition of an admissible map can be viewed as a form of groupoid equivariance analogous to the equivariant maps of dynamical systems with symmetry. Equivariance of a map $f:X\to X$ under a group $\mathrm{\Gamma }$ acting on $X$ means that for all $\gamma \in \mathrm{\Gamma }$,

$f(\gamma (x))=\gamma (f(x))\mathrm{\forall }x\in X,$

so $f$ commutes with the action of $\mathrm{\Gamma }$.

Analogously, the admissible ODE form can be restated in the following terms. If $\beta \in B(c,d)$, so that $d=\beta (c)$, then an admissible map $f=(f_1,\dots ,f_n)$ satisfies

$f_{\beta (c)}(x_d,x_{T(d)})=f_c(x_d,{\beta }^{*}{x}_{T(d)}),$

where $T(c)=(i_1,i_2,\dots ,i_k)$ is the set of source nodes $i_j$ of edges in $I(c)$, and ${\beta }^{*}(x_{i_1},x_{i_2},\dots x_{i_k})=(x_{\beta (i_1)},x_{\beta (i_2)},\dots ,x_{\beta (i_k)})$. That is, $f$ commutes with each $\beta \in {{ℬ}}_{{𝒢}}$.

Example: The Smolen oscillator network

The Smolen oscillator network. Left: Smolen oscillator network. Sharp arrowhead: excitation/activation. Barred arrowhead: inhibition/repression. Colors show synchrony pattern (total synchrony). Middle: Fibration $\phi$. Right: Base network.

The figure shows the {\em Smolen network}. It has two nodes, edges of two different types, and its automorphism group is trivial. The input set of node 1 is $I(1)=\{a,b\}$ and that of node 2 is $I(2)=\{c,d\}$.

Admissible ODEs have the general form

$\begin{array}{rl}{\dot{x}}_1& =f(x_1,x_1,x_2)\\ {\dot{x}}_2& =f(x_2,x_1,x_2)\end{array}$

There is no nontrivial automorphism because these equations are not preserved by interchanging $x_1$ and $x_2$. Nonetheless, if we set $x_1=x_2=y$ then b components reduce to $\dot{y}=f(y,y,y)$. Solutions of this ODE correspond precisely to synchronous solutions of the 2-variable ODE.

These synchronous solutions can be explained by a fibration symmetry: the input sets of the two nodes are isomorphic. There is a fibration $\phi$ to a one-node network, shown in the figure, where

$\begin{array}{rl}& \phi (1)=\overline{1}\phi (2)=\overline{1}\\ & \phi (a)=\overline{a}\phi (b)=\overline{b}\phi (c)=\overline{a}\phi (d)=\overline{b}\end{array}$

It is a fibration because the node type and the types of input edges are preserved. There is a single fiber $\{1,2\}$, so the nodes can synchronize. The subsets $B(i,j)$ of the network groupoid are:

$\begin{array}{rl}B(1,1):& \left(\begin{array}{cc}a& b\\ a& b\end{array}\right)={ϵ}_1\\ B(1,2):& \left(\begin{array}{cc}a& b\\ c& d\end{array}\right)=\tau \\ B(2,1):& \left(\begin{array}{cc}c& d\\ a& b\end{array}\right)={\tau }^{-1}\\ B(2,2):& \left(\begin{array}{cc}c& d\\ c& d\end{array}\right)={ϵ}_2\end{array}$

The composition table of the Smolen network groupoid is:

Composition table

	${ϵ}_1$	${ϵ}_2$	$\tau$	${\tau }^{-1}$
${ϵ}_1$	${ϵ}_1$	-	-	${\tau }^{-1}$
${ϵ}_2$	-	${ϵ}_2$	$\tau$	-
$\tau$	$\tau$	-	-	${ϵ}_2$
${\tau }^{-1}$	-	${\tau }^{-1}$	${ϵ}_1$	-

Entry in row $a$, column $b$ is $ab$. A dash indicates that composition is not defined.

Synchronization and dynamics

A central result of fibration theory is that:

Every robust cluster synchronization pattern corresponds to a fibration symmetry, and vice versa.

Here robust means that synchronization persists under arbitrary admissible perturbations of the system’s equations, as long as they respect the network structure. This result has been proved for equilibria. It also holds for periodic states under technical hypotheses. More generally, Joly has proved that there exists a generic set of admissible vector fields $f$ for which the synchrony patterns of every solution of the ODE $\dot{x}=f(x)$ corresponds to a fibration symmetry. Here generic means a countable intersection of open dense sets, which is dense by Baire's Theorem. This version of the theorem applies to any type of dynamics, including chaos.

Applications in biology

Gene regulatory networks

In transcriptional regulatory networks, fibration symmetries identify groups of genes whose synchronized activity is determined by network topology rather than fine tuning of kinetic parameters. In idealized models of gene regulation, genes belonging to the same fiber receive isomorphic regulatory inputs and therefore evolve synchronously. Empirical studies have shown that such fiber-induced structure can predict approximate gene coexpression patterns observed in bacterial regulatory networks, even in the absence of global graph automorphisms.

More generally, symmetry fibrations have been used to decompose gene regulatory networks into functional building blocks based on the isomorphism classes of their input trees, providing a structural explanation for coordinated gene expression.

Neural systems

In neural networks, fibration symmetry predicts synchronization of neuronal populations based solely on connectivity patterns. Nodes belonging to the same fiber have identical input structures and are therefore constrained to process information in an equivalent manner. Applications range from small nervous systems, such as the Caenorhabditis elegans connectome, to large-scale mammalian cortical networks, where fibration analysis reveals functional cell classes and information-processing pathways.

The same framework has been used to analyze the dynamics of biological circuits supported by neural and gene-regulatory architectures, showing how fibration symmetries constrain bifurcations and synchronization patterns independently of specific model details.

Robustness and evolution

Unlike automorphism-based symmetries, fibration symmetries depend only on local input structure and therefore persist under edge perturbations, node duplication, and incomplete or noisy data. This locality makes them particularly robust in biological contexts, where networks evolve through mutation and are reconstructed from imperfect experimental measurements. As a result, biological networks may exhibit fibration symmetries even when global symmetries are absent or difficult to detect.

Algorithms and computation

Fibration symmetries can be identified using partition-refinement algorithms closely related to those employed in graph isomorphism testing. In practice, these methods compute the coarsest equitable partition or balanced coloring compatible with the directed network structure. Such algorithms scale efficiently to large biological networks with thousands of nodes and have been applied to transcriptomic and connectomic data sets.

Relation to other symmetry notions

Concept	Global	Local	Preserves inputs	Preserves outputs
Graph automorphism	Yes	No	Yes	Yes
Graph covering	No	Yes	Yes	Yes
Graph fibration	No	Yes	Yes	No

Graph fibrations strictly generalize automorphism symmetries by capturing structural invariances that depend on local input equivalence rather than global graph isomorphisms. This makes them suitable for analyzing synchronization and functional equivalence in asymmetric and heterogeneous networks.

See also

• Fibrations of graphs
• Balanced coloring
• Cluster synchronization
• Graph automorphism
• Groupoids in category theory
• Network dynamical systems