Graph Automorphism Group Equivariant Neural Networks
Permutation equivariant neural networks are typically used to learn from data
that lives on a graph. However, for any graph $G$ that has $n$ vertices, using
the symmetric group $S_n$ as its group of symmetries does not take into account
the relations that exist between the vertices. Given that the actual group of
symmetries is the automorphism group Aut$(G)$, we show how to construct neural
networks that are equivariant to Aut$(G)$ by obtaining a full characterisation
of the learnable, linear, Aut$(G)$-equivariant functions between layers that
are some tensor power of $\mathbb{R}^{n}$. In particular, we find a spanning
set of matrices for these layer functions in the standard basis of
$\mathbb{R}^{n}$. This result has important consequences for learning from data
whose group of symmetries is a finite group because a theorem by Frucht (1938)
showed that any finite group is isomorphic to the automorphism group of a
graph.
Edward Pearce-Crump, William J. Knottenbelt
# Graph Automorphism Group Equivariant Neural Networks

###### Abstract

For any graph \(G\) having \(n\) vertices and its automorphism group \(\mathrm{Aut}(G)\), we provide a full characterisation of all of the possible \(\mathrm{Aut}(G)\)-equivariant neural networks whose layers are some tensor power of \(\mathbb{R}^{n}\). In particular, we find a spanning set of matrices for the learnable, linear, \(\mathrm{Aut}(G)\)-equivariant layer functions between such tensor power spaces in the standard basis of \(\mathbb{R}^{n}\).

Machine Learning, ICML

## 1 Introduction

The learnable, linear, group equivariant layer functions between tensor power spaces of \(\mathbb{R}^{n}\) have recently been characterised for a number of important groups by (Pearce-Crump, 2022; 2023; 2023). This characterisation has been shown to be related to the combinatorics of set partitions. A set partition of a given set of elements is a partitioning of the set into a number of disjoint, non-empty subsets. The subsets are called blocks. Depending on the group and the structure of the blocks, we are able to determine the form of the learnable, linear, group equivariant layer functions between any two tensor power spaces of \(\mathbb{R}^{n}\) precisely.

In this paper, we look instead at how to construct neural networks that are equivariant to the automorphism group of a graph \(G\) having some \(n\) vertices, written \(\mathrm{Aut}(G)\). Specifically, we give a full characterisation of all of the possible \(\mathrm{Aut}(G)\)-equivariant neural networks whose layers are some tensor power of \(\mathbb{R}^{n}\) by finding a spanning set of matrices for the learnable, linear, \(\mathrm{Aut}(G)\)-equivariant layer functions between such tensor power spaces in the standard basis of \(\mathbb{R}^{n}\). Similar to the above mentioned approach of Pearce-Crump, instead of calculating the spanning set by studying set partitions, we obtain it by relating each spanning set element to a so-called _bilabelled graph_. In brief, a \((k,l)\)-bilabelled graph is a graph that comes with two tuples, one of length \(k\) and the other of length \(l\), whose entries are taken from the vertex set of the graph (with repetitions amongst entries allowed). Consequently, by looking at the combinatorics of bilabelled graphs, we can determine the learnable, linear \(\mathrm{Aut}(G)\)-equivariant layers in such a neural network.

We follow closely the work of (Mancinska & Roberson, 2020), who studied the problem of determining under what circumstances two graphs are quantum isomorphic. They built upon the work of (Chassaniol, 2019), who showed that a vertex-transitive graph has no quantum symmetries. We show how their results and methods can be applied instead for the purpose of learning from data that has an underlying symmetry to the automorphism group of a graph.

The obvious application of our approach is for learning from graphs themselves. There are a number of methods that currently exist in the machine learning literature for learning from graphs. These include Graph Attention Networks (GATs) (Velickovic et al., 2018), Graph Convolutional Networks (GCNs) (Kipf & Welling, 2017), and Graph Neural Networks (GNNs) (Gori et al., 2005; Scarselli et al., 2009), among others. Many of these approaches use some form of \(S_{n}\)-equivariance, since this has been determined previously by a number of authors (Maron et al., 2019; Ravanbakhsh, 2020; Pearce-Crump, 2022). However, the stronger condition of \(\mathrm{Aut}(G)\)-equivariance is more appropriate for learning from data on graphs since it takes into account relations between vertices in the graph itself, whereas \(S_{n}\)-equivariance does not. Consequently, we believe that the approach presented in this paper provides a different way for learning from graphs, where, specifically, the equivariance is guaranteed exactly, and the form of the possible architectures is determined precisely by the symmetries in the underlying structure of the graph.

There are other important motivations for performing such a characterisation. A famous theorem in algebraic graph theory known as Frucht's Theorem (Frucht, 1938) states that every finite group is isomorphic to the automorphism group of a finite undirected graph. Consequently, for any finite group of our choosing, if we know the graph (having some \(n\) vertices) whose automorphism group is isomorphic to the group in question, then we will be able to characterise all of the learnable, linear, group equivariant layer functions between any tensor power spaces of \(\mathbb{R}^{n}\) for that group. In particular, we show that we can recover the diagram basis that appears in (Godfrey et al., 2023) for the learnable, linear,
\(S_{n}\)-equivariant layer functions between tensor power spaces of \(\mathbb{R}^{n}\) in the standard basis of \(\mathbb{R}^{n}\). We also show that we can determine characterisations for other groups, such as for \(D_{4}\), considered as a subgroup of \(S_{4}\), which, to the best of our knowledge, have been missing from the literature.

Furthermore, even if, for a given finite undirected graph, we are unable to determine the finite group that is isomorphic to the automorphism group of the graph, we know that we can calculate the learnable, linear, automorphism group equivariant linear layers using this method, which will be sufficient for performing learning in situations where we do not need to know what the actual automorphism group is explicitly.

The main contributions of this paper, which appear in Section 6 onwards, are as follows:

1. We are the first to show how the combinatorics underlying bilabelled graph diagrams serves as the theoretical foundation for constructing neural networks that are equivariant to the automorphism group of a graph \(G\) having \(n\) vertices when the layers are some tensor power of \(\mathbb{R}^{n}\).
2. In particular, we find a spanning set for the learnable, linear, \(\operatorname{Aut}(G)\)-equivariant layer functions between such tensor power spaces in the standard basis of \(\mathbb{R}^{n}\).
3. We show how our approach can be used to recover the diagram basis for the learnable, linear, \(S_{n}\)-equivariant layer functions between tensor power spaces of \(\mathbb{R}^{n}\) in the standard basis of \(\mathbb{R}^{n}\) that appears in (Godfrey et al., 2023).

## 2 Preliminaries

We choose our field of scalars to be \(\mathbb{R}\) throughout. Tensor products are also taken over \(\mathbb{R}\), unless otherwise stated. Also, we let \([n]\) represent the set \(\{1,\ldots,n\}\), and we denote the standard basis of \(\mathbb{R}^{n}\) throughout by \(\{e_{i}\ |\ i\in[n]\}\).

Recall that a representation of a group \(G\) is a choice of vector space \(V\) over \(\mathbb{R}\) and a group homomorphism

\[\rho:G\to GL(V) \tag{1}\]

We choose to focus on finite-dimensional vector spaces \(V\) that are some tensor power of \(\mathbb{R}^{n}\) in this paper.

We often abuse our terminology by calling \(V\) a representation of \(G\), even though the representation is technically the homomorphism \(\rho\). When the homomorphism \(\rho\) needs to be emphasised alongside its vector space \(V\), we will use the notation \((V,\rho)\).

## 3 Group Equivariant Neural Networks

Group equivariant neural networks are constructed by alternately composing linear and non-linear \(G\)-equivariant maps between representations of a group \(G\). The following is based on the material presented in (Lim and Nelson, 2022).

We first define \(G\)-_equivariance_:

**Definition 3.1**.: Suppose that \((V,\rho_{V})\) and \((W,\rho_{W})\) are two representations of a group \(G\).

A map \(\phi:V\to W\) is said to be \(G\)-equivariant if, for all \(g\in G\) and \(v\in V\),

\[\phi(\rho_{V}(g)[v])=\rho_{W}(g)[\phi(v)] \tag{2}\]

The set of all _linear_\(G\)-equivariant maps between \(V\) and \(W\) is denoted by \(\operatorname{Hom}_{G}(V,W)\). When \(V=W\), we write this set as \(\operatorname{End}_{G}(V)\). It can be shown that \(\operatorname{Hom}_{G}(V,W)\) is a vector space over \(\mathbb{R}\). See (Segal, 2014) for more details.

A special case of \(G\)-equivariance is \(G\)-_invariance_:

**Definition 3.2**.: The map \(\phi\) given in Definition 3.1 is said to be \(G\)-invariant if \(\rho_{W}\) is defined to be the \(1\)-dimensional trivial representation of \(G\). As a result, \(W=\mathbb{R}\).

We can now define the type of neural network that is the focus of this paper:

**Definition 3.3**.: An \(L\)-layer \(G\)-equivariant neural network \(f_{NN}\) is a composition of _layer functions_

\[f_{NN}\coloneqq f_{L}\circ\ldots\circ f_{l}\circ\ldots\circ f_{1} \tag{3}\]

such that the \(l^{\text{th}}\) layer function is a map of representations of \(G\)

\[f_{l}:(V_{l-1},\rho_{l-1})\rightarrow(V_{l},\rho_{l}) \tag{4}\]

that is itself a composition

\[f_{l}\coloneqq\sigma_{l}\circ\phi_{l} \tag{5}\]

of a learnable, linear, \(G\)-equivariant function

\[\phi_{l}:(V_{l-1},\rho_{l-1})\rightarrow(V_{l},\rho_{l}) \tag{6}\]

together with a fixed, non-linear activation function

\[\sigma_{l}:(V_{l},\rho_{l})\rightarrow(V_{l},\rho_{l}) \tag{7}\]

such that

1. \(\sigma_{l}\) is a \(G\)-equivariant map, as in (2), and
2. \(\sigma_{l}\) acts pointwise (after a basis has been chosen for each copy of \(V_{l}\) in \(\sigma_{l}\).)
We focus on the learnable, linear, \(G\)-equivariant functions in this paper, since the non-linear functions are fixed. Note that, given a spanning set of matrices for \(\operatorname{Hom}_{G}(V_{l-1},V_{l})\), having picked a basis for each layer space in the set \(\{V_{l}\}\), the weight matrix is a weighted linear combination of the spanning set matrices, where each coefficient in the linear combination is a parameter to be learned. Consequently, the number of parameters appearing in the \(l^{\text{th}}\) layer function is equal to the number of matrices that appear in the spanning set for \(\operatorname{Hom}_{G}(V_{l-1},V_{l})\).

_Remark 3.4_.: The entire neural network \(f_{NN}\) is itself a \(G\)-equivariant function because it can be shown that the composition of any number of \(G\)-equivariant functions is itself \(G\)-equivariant.

_Remark 3.5_.: One way of making a neural network of the form given in Definition 3.3\(G\)-invariant is by choosing the representation in the final layer to be the \(1\)-dimensional trivial representation of \(G\).

## 4 Graph Theory Essentials

We begin by recalling some of the fundamentals of graph theory that will appear throughout the rest of this paper. For more details, see any standard book on graph theory, such as (Bollobas, 1998).

**Definition 4.1**.: A **graph**\(G\) is a tuple \((V(G),E(G))\) of sets, where \(V(G)\) is a set of vertices for \(G\) and \(E(G)\) is a subset of unordered pairs of elements from \(V(G)\times V(G)\) denoting the undirected edges between the vertices of \(G\).

We include the possibility that the graph has loops; however, we only allow at most one loop per vertex.

**Definition 4.2**.: Let \(G\) be a graph having \(n\) vertices. The **adjacency matrix** of \(G\), denoted by \(A_{G}\), is the \(n\times n\) matrix whose \((i,j)\)-entry is \(1\) if vertex \(i\) is adjacent to vertex \(j\) in \(G\), and is \(0\) otherwise. Note that \(A_{G}\) is a symmetric matrix, because \(G\) has undirected edges, and the \((i,i)\)-entry is \(1\) in \(A_{G}\) if and only if \(G\) has a loop at vertex \(i\).

**Definition 4.3**.: Let \(G\) be a graph. The **complement** of \(G\), denoted by \(\overline{G}\), is the graph having the same vertex set as \(G\) and the same loops as \(G\), but now distinct vertices are adjacent in \(\overline{G}\) if and only if they are not adjacent in \(G\).

_Example 4.4_.: The complete graph on \(n\) vertices, \(K_{n}\), is the loopless graph where every vertex is adjacent to every other vertex.

_Example 4.5_.: The cycle graph on \(n\) vertices, \(C_{n}\), is the loopless graph where every vertex \(i\in[n]\) is adjacent to \(j=i\pm 1\mod n\), where \(j\in[n]\).

**Definition 4.6**.: Let \(H\) and \(G\) be graphs. A **graph homomorphism** from \(H\) to \(G\) is a function \(\phi:V(H)\to V(G)\) such that if \(i\) is adjacent to \(j\) in \(H\), then \(\phi(i)\) is adjacent to \(\phi(j)\) in \(G\).

**Definition 4.7**.: Let \(H\) and \(G\) be graphs. A **graph isomorphism** from \(H\) to \(G\) is a bijection \(\phi:V(H)\to V(G)\) such that \(i\) is adjacent to \(j\) in \(H\) if and only if \(\phi(i)\) is adjacent to \(\phi(j)\) in \(G\).

Consequently, we get that

**Definition 4.8**.: Let \(G\) be a graph. An **automorphism** of \(G\) is an isomorphism from \(G\) to \(G\). The set of all automorphisms of \(G\), written \(\operatorname{Aut}(G)\), can be shown to be a group.

_Remark 4.9_.: If \(G\) is a graph having \(n\) vertices, then \(\operatorname{Aut}(G)\) is, in fact, a subgroup of \(S_{n}\). Specifically, if \(\sigma\in S_{n}\), then it is easy to show, viewing \(S_{n}\) as a subgroup of \(GL(n)\), that

\[\sigma\in\operatorname{Aut}(G)\iff\sigma A_{G}=A_{G}\sigma \tag{8}\]

It is also clear to see that \(\operatorname{Aut}(G)\cong\operatorname{Aut}(\overline{G})\).

_Example 4.10_.: The automorphism group of the complete graph on \(n\) vertices, \(\operatorname{Aut}(K_{n})\), is the symmetric group \(S_{n}\). Consequently, the automorphism group of the edgeless graph having \(n\) vertices, \(\operatorname{Aut}(\overline{K_{n}})\), is also the symmetric group \(S_{n}\).

_Example 4.11_.: The automorphism group of the cycle graph on \(n\) vertices, \(\operatorname{Aut}(C_{n})\), is isomorphic to the dihedral group \(D_{n}\) of order \(2n\).

_Example 4.12_.: The automorphism group of two copies of the complete graph on two vertices, \(\operatorname{Aut}(2K_{2})\), is isomorphic to the dihedral group \(D_{4}\) of order \(8\).

## 5 The representation \((\mathbb{R}^{n})^{\otimes k}\) of \(\operatorname{Aut}(G)\)

Recall that any \(k\)-tensor power of \(\mathbb{R}^{n}\), \((\mathbb{R}^{n})^{\otimes k}\), for any \(k\in\mathbb{Z}_{\geq 0}\), is a representation of \(S_{n}\), since the elements

\[e_{I}\coloneqq e_{i_{1}}\otimes e_{i_{2}}\otimes\cdots\otimes e_{i_{k}} \tag{9}\]

for all \(I\coloneqq(i_{1},i_{2},\ldots,i_{k})\in[n]^{k}\) form a basis of \((\mathbb{R}^{n})^{\otimes k}\), and the action of \(S_{n}\) that maps a basis element of \((\mathbb{R}^{n})^{\otimes k}\) of the form (9) to

\[e_{\sigma(I)}\coloneqq e_{\sigma(i_{1})}\otimes e_{\sigma(i_{2})}\otimes\cdots \otimes e_{\sigma(i_{k})} \tag{10}\]

can be extended linearly on the basis.

For any graph \(G\) having \(n\) vertices, as \(\operatorname{Aut}(G)\) is a subgroup of \(S_{n}\), we have that \((\mathbb{R}^{n})^{\otimes k}\) is also a representation of \(\operatorname{Aut}(G)\) that is given by the restriction of the representation of \(S_{n}\) to \(\operatorname{Aut}(G)\).

We denote the representation of \(S_{n}\) by \(\rho_{k}\). We will use the same notation for the restriction of this representation to \(\operatorname{Aut}(G)\), with the context making clear that it is the restriction of the \(S_{n}\) representation.

For more on the representation theory of the symmetric group, see (Sagan, 2000) and (Ceccherini-Silberstein et al., 2010).
## 6 Characterisation of the Equivariant, Linear Maps for the Automorphism Group of a Graph

In this section, we give a full characterisation of all of the possible \(\operatorname{Aut}(G)\)-equivariant neural networks whose layers are some tensor power of \(\mathbb{R}^{n}\) by finding a spanning set of matrices for the learnable, linear, \(\operatorname{Aut}(G)\)-equivariant layer functions between such tensor power spaces in the standard basis of \(\mathbb{R}^{n}\). We follow closely the work of Mancinska and Roberson (2020) throughout, but begin by stating a result found by Chassaniol (2019) which describes, in terms of a generating set of matrices, the category whose morphisms are the linear layer functions that we wish to characterise.

### Chassaniol's Result

For each group \(G\) that is a subgroup of \(S_{n}\), we can define the following category.

**Definition 6.1**.: The category \(\mathcal{C}(G)\) consists of objects that are the \(k\)-order tensor power spaces of \(\mathbb{R}^{n}\), as representations of \(G\), and morphism spaces between any two objects that are the vector spaces \(\operatorname{Hom}_{G}((\mathbb{R}^{n})^{\otimes k},(\mathbb{R}^{n})^{\otimes l})\).

The vertical composition of morphisms is given by the usual composition of linear maps, the tensor product is given by the usual tensor product of linear maps, and the unit object is the one-dimensional trivial representation of \(G\).

_Remark 6.2_.: We will sometimes write \(\mathcal{C}(G)(k,l)\) for \(\operatorname{Hom}_{G}((\mathbb{R}^{n})^{\otimes k},(\mathbb{R}^{n})^{ \otimes l})\), and reuse the notation \(\mathcal{C}(G)\) for the set \(\cup_{k,l=0}^{\infty}\mathcal{C}(G)(k,l)\).

**Proposition 6.3**.: _The category \(\mathcal{C}(G)\) is a symmetric tensor category with duals, in the sense that_

1. _if_ \(\phi_{1}\)_,_ \(\phi_{2}\in\mathcal{C}(G)\)_, then_ \(\phi_{1}\otimes\phi_{2}\in\mathcal{C}(G)\)__
2. _if_ \(\phi_{1}\)_,_ \(\phi_{2}\in\mathcal{C}(G)\) _are composable, then_ \(\phi_{1}\circ\phi_{2}\in\mathcal{C}(G)\)__
3. _if_ \(\phi\in\mathcal{C}(G)(k,l)\)_, then_ \(\phi^{*}\in\mathcal{C}(G)(l,k)\)__
4. _the identity map_ \(M^{1,1}\in\mathcal{C}(G)(1,1)\)__
5. _the swap map_ \(S\in\mathcal{C}(G)(2,2)\)_, where_ \(S\) _maps_ \(e_{i}\otimes e_{j}\) _to_ \(e_{j}\otimes e_{i}\)__
6. _the cup map_ \(M^{0,2}\in\mathcal{C}(G)(0,2)\)_, where_ \(M^{0,2}\) _maps_ \(1\) _to_ \(\sum_{i}e_{i}\otimes e_{i}\)__

Proof.: See Banica and Speicher (2009), Proposition 1.2. 

It will be useful to define a number of _spider_ maps \(M^{k,l}\).

**Definition 6.4**.: For all \(k,l\geq 0\), the map \(M^{k,l}\in\operatorname{Hom}((\mathbb{R}^{n})^{\otimes k},(\mathbb{R}^{n})^{ \otimes l})\) is defined as follows:

* if \(k,l>0\), then \(M^{k,l}\) maps \(e_{i}^{\otimes k}\) to \(e_{i}^{\otimes l}\) for all \(i\in[n]\) and maps all other vectors to the zero vector otherwise.
* if \(k=0\) and \(l>0\), then \(M^{0,l}\) maps \(1\) to \(\sum_{i}e_{i}^{\otimes l}\).
* if \(k>0\) and \(l=0\), then \(M^{k,0}\) maps \(e_{i}^{\otimes k}\) to \(1\) for all \(i\in[n]\) and maps all other vectors to \(0\) otherwise.
* if \(k=0\) and \(l=0\), then \(M^{0,0}\coloneqq(n)\).

_Remark 6.5_.: In particular, the identity map \(M^{1,1}\) and the cup map \(M^{0,2}\) given in Proposition 6.3 are spider maps, hence the notation used is consistent.

For any graph \(G\) having \(n\) vertices, Chassaniol (2019) found the following generating set for the category \(\mathcal{C}(\operatorname{Aut}(G))\):

**Theorem 6.6**Chassaniol (2019), Proposition 3.5.: _Let \(A_{G}\) denote the adjacency matrix of the graph \(G\). Then_

\[\mathcal{C}(\operatorname{Aut}(G))=\langle M^{0,1},M^{2,1},A_{G},S\rangle_{+, \circ,\otimes,*} \tag{11}\]

_where the right hand side denotes all matrices that can be generated from the four matrices using the operations of \(\mathbb{R}\)-linear combinations, matrix product, Kronecker product, and transposition._

### The Category of All Bilabelled Graphs

Mancinska and Roberson showed how Chassaniol's generating set for \(\mathcal{C}(\operatorname{Aut}(G))\) can be improved by relating it to the combinatorics of bilabelled graphs.

**Definition 6.7**Bilabelled Graph.: A \((k,l)\)-bilabelled graph \(\mathbf{H}\) is a triple \((H,\mathbf{k},\mathbf{l})\), where \(H\) is a graph having some \(m\) vertices with labels in \([m]\), \(\mathbf{k}\coloneqq(k_{1},\dots,k_{k})\) is a tuple in \([m]^{k}\), and \(\mathbf{l}\coloneqq(l_{1},\dots,l_{l})\) is a tuple in \([m]^{l}\).

We call \(\mathbf{k}\) and \(\mathbf{l}\) the input and output tuples to \(\mathbf{H}\) respectively, and we call \(H\) the underlying graph of \(\mathbf{H}\). A vertex in the underlying graph \(H\) of \(\mathbf{H}\) is said to be free if it does not appear in either of the input or output tuples.

In order to provide a diagrammatic representation of bilabelled graphs, we need the following definition.

**Definition 6.8**.: Let \(\mathbf{H_{1}}=(H_{1},\mathbf{k},\mathbf{l})\) be a \((k,l)\)-bilabelled graph and let \(\mathbf{H_{2}}=(H_{2},\mathbf{k^{\prime}},\mathbf{l^{\prime}})\) be another \((k,l)\)-bilabelled graph. Then \(\mathbf{H_{1}}\) and \(\mathbf{H_{2}}\) are isomorphic as \((k,l)\)-bilabelled
graphs, written \(\mathbf{H_{1}}\cong\mathbf{H_{2}}\), if there is a graph isomorphism from \(H_{1}\) to \(H_{2}\) such that \(k_{i}\mapsto k_{i}^{\prime}\) for all \(i\in[k]\) and \(l_{j}\mapsto l_{j}^{\prime}\) for all \(j\in[l]\).

We denote \(\mathbf{H_{1}}\)'s isomorphism class by \([\mathbf{H_{1}}]\).

_Remark 6.9_.: An isomorphism between two \((k,l)\)-bilabelled graphs can effectively be thought of as a relabelling of the vertices of the _same_ underlying graph, resulting in an appropriate relabelling of the elements of the tuples themselves. Consequently, the isomorphism can be thought of as a relabelling of the same bilabelled graph!

With this in mind, we can represent the _isomorphism class_\([\mathbf{H}]\) for a \((k,l)\)-bilabelled graph \(\mathbf{H}=(H,\mathbf{k},\mathbf{l})\) in diagrammatic form. We choose \(\mathbf{H}\) as a class representative of \([\mathbf{H}]\), and proceed as follows: we draw

* \(l\) black vertices on the top row, labelled left to right by \(1,\dots,l\),
* \(k\) black vertices on the bottom row, labelled left to right by \(l+1,\dots,l+k\),
* the underlying graph \(H\) in red, with labelled red vertices and red edges, in between the two rows of black vertices, and
* a black line connecting vertex \(i\) in the top row to \(l_{i}\), and a black line connecting vertex \(l+j\) in the bottom row to \(k_{j}\).

Note that if we drew a diagram for another representative of the same isomorphism class \([\mathbf{H}]\), by the definition of an isomorphism for \((k,l)\)-bilabelled graphs, we would obtain exactly the same diagram as for the first class representative, except the labels of the underlying graph's vertices (and consequently the elements of the tuples) would be different. As a result, the diagram for the isomorphism class \([\mathbf{H}]\) is independent of the choice of class representative, and so we choose the class' label, \(\mathbf{H}\), to draw the diagram throughout, unless otherwise stated. With the technicalities being understood, we refer to the construction defined above as a \((k,l)\)-bilabelled graph diagram _for \(\mathbf{H}\) itself_, and use the same notation \(\mathbf{H}\). We give an example of a \((2,3)\)-bilabelled graph diagram in Figure 1.

_Remark 6.10_.: We have chosen to represent \((k,l)\)-bilabelled graph diagrams from bottom to top, in contrast to Mancinska and Roberson, who chose a right to left orientation, in order to be consistent with the direction of set partition diagrams that appear in the author's other papers (Pearce-Crump, 2022; 2023a;b).

We can define a number of operations on isomorphism classes of bilabelled graphs, namely, composition, tensor product, and involution, as follows.

**Definition 6.11** (Composition of Bilabelled Graphs).: Let \([\mathbf{H_{1}}]\) be the isomorphism class of the \((k,l)\)-bilabelled graph \(\mathbf{H_{1}}=(H_{1},\mathbf{k},\mathbf{l})\), and let \([\mathbf{H_{2}}]\) be the isomorphism class of the \((k,l)\)-bilabelled graph \(\mathbf{H_{2}}=(H_{2},\mathbf{l}^{\prime},\mathbf{m})\).

Then we define the composition \([\mathbf{H_{2}}]\circ[\mathbf{H_{1}}]\) to be the isomorphism class \([\mathbf{H}]\) of the \((k,m)\)-bilabelled graph \(\mathbf{H}=(H,\mathbf{k},\mathbf{m})\), that is obtained as follows: drawing each isomorphism class as a diagram, we first relabel the red vertices in \(H_{2}\) (and consequently the elements of \(\mathbf{l}^{\prime},\mathbf{m}\)) under the map \(i\mapsto i^{\prime}\), for all \(i\in[V(H_{2})]\). Then, we connect the top row of black vertices of \(\mathbf{H_{1}}\) with the bottom row of black vertices of \(\mathbf{H_{2}}\), and delete the vertices themselves. We are now left with \(l\) black lines that are edges between red vertices of the underlying graphs \(H_{1}\) and \(H_{2}\). Next, we contract these, forming set unions of the vertex labels where appropriate, and remove any red multiedges between red vertices that appear in the contraction to obtain the new underlying graph \(H\). Note that we keep any loops that appear in the new underlying graph \(H\). Finally, we relabel the vertex set of the new underlying graph \(H\) so that each vertex is labelled by an integer only, and consequently relabel the entries of the tuples \(\mathbf{k}\) and \(\mathbf{m}\) accordingly.

Since this operation has been defined on diagrams, it means that the operation is well defined on the isomorphism classes themselves.

We give an example of this composition in Figure 2.

_Remark 6.12_.: Note that to compose two isomorphism classes of bilabelled graphs, only the number of bottom row vertices in the diagram for \(\mathbf{H_{2}}\) needs to be equal to the number of top row vertices in the diagram for \(\mathbf{H_{1}}\). In particular, the number of vertices in the underlying graphs of \(\mathbf{H_{1}}\) and \(\mathbf{H_{2}}\) do _not_ need to be the same.

**Definition 6.13** (Tensor Product of Bilabelled Graphs).: Let \([\mathbf{H_{1}}]\) be the isomorphism class of the \((k,l)\)-bilabelled graph \(\mathbf{H_{1}}=(H_{1},\mathbf{k},\mathbf{l})\) and let \([\mathbf{H_{2}}]\) be the isomorphism class of the \((q,m)\)-bilabelled graph \(\mathbf{H_{2}}=(H_{2},\mathbf{q},\mathbf{m})\).

Then we define the tensor product \([\mathbf{H_{1}}]\otimes[\mathbf{H_{2}}]\) to be the isomorphism class of the \((k+q,l+m)\)-bilabelled graph \((H_{1}\cup H_{2},\mathbf{k}\mathbf{q},\mathbf{l}\mathbf{m})\) where \(\mathbf{k}\mathbf{q}\) is the \((k+q)\)-length tuple obtained by concatenating \(\mathbf{k}\) and \(\mathbf{q}\), and likewise for \(\mathbf{l}\mathbf{m}\).

**Definition 6.14** (Involution of Bilabelled Graphs).: Let \([\mathbf{H}]\) be the isomorphism class of the \((k,l)\)-bilabelled graph \(\mathbf{H}=(H,\mathbf{k},\mathbf{l})\). Then we define the involution \([\mathbf{H^{*}}]\) to be the isomorphism class of the \((l,k)\)-bilabelled graph \((H,\mathbf{l},\mathbf{k})\).

We can form a category for the bilabelled graphs, as follows:

**Definition 6.15** (Category of Bilabelled Graphs).: The category of all bilabelled graphs \(\mathcal{G}\) is the category whose objects are the non-negative integers \(\mathbb{N}_{\geq 0}=\{0,1,2,\dots\}\), and, for any pair of objects \(k\) and \(l\), the morphism space \(\mathcal{G}(k,l)\coloneqq\operatorname{Hom}_{\mathcal{G}}(k,l)\) is defined to be the \(\mathbb{R}\)-linear span
of the set of all isomorphism classes of \((k,l)\)-bilabelled graphs.

The vertical composition of morphisms is the composition of isomorphism classes of bilabelled graphs given in Definition 6.11, the tensor product of morphisms is the tensor product of isomorphism classes of bilabelled graphs given in Definition 6.13, and the unit object is \(0\).

_Remark 6.16_.: It is easy to show that \(\mathcal{G}\) is a strict \(\mathbb{R}\)-linear monoidal category.

### \(G\)-Homomorphism Matrices

Mancinska and Roberson established a relationship between the abstract and the concrete: namely, between isomorphism classes of \((k,l)\)-bilabelled graphs and, for a fixed graph \(G\) having \(n\) vertices, matrices that are linear maps \((\mathbb{R}^{n})^{\otimes k}\rightarrow(\mathbb{R}^{n})^{\otimes l}\), which they termed \(G\)-homomorphism matrices. We express this relationship more formally in terms of functors and categories at the end of this section.

**Definition 6.17** (\(G\)-Homomorphism Matrix).: Suppose that \(G\) is a graph having \(n\) vertices, and let \([\mathbf{H}]\) be the isomorphism class of the \((k,l)\)-bilabelled graph \(\mathbf{H}\coloneqq(H,\mathbf{k},\mathbf{l})\).

Then we define the \(G\)-homomorphism matrix of \([\mathbf{H}]\) to be the \(n^{l}\times n^{k}\) matrix that has \((I,J)\) entry given by the number of graph homomorphisms from \(H\) to \(G\) such that \(\mathbf{l}\) is mapped to \(I\) and \(\mathbf{k}\) is mapped to \(J\). We denote this matrix by \(X^{G}_{\mathbf{H}}\).

_Remark 6.18_.: Note that the \(G\)-homomorphism matrix \(X^{G}_{\mathbf{H}}\) obtained is independent of the choice of class representative for \([\mathbf{H}]\), and that any such matrix must have only real entries, by definition.

We now describe some important examples of \(G\)-homomorphism matrices, where throughout, \(G\) is a graph having \(n\) vertices.

_Example 6.19_.: If \(\mathbf{A}\) is the \((1,1)\)-bilabelled graph \((K_{2},(1),(2))\), where \(K_{2}\) is the complete graph on two vertices, then \(X^{G}_{\mathbf{A}}\) is the adjacency matrix \(A_{G}\) of \(G\).

_Example 6.20_.: If \(\mathbf{M}^{k,l}\) is the \((k,l)\)-bilabelled graph \((K_{1},\mathbf{k}=(1,\ldots,1),\mathbf{l}=(1,\ldots,1))\), where \(K_{1}\) is the complete graph on one vertex, then \(X^{G}_{\mathbf{M}^{k,l}}\) is the spider matrix \(M^{k,l}\) given in Definition 6.4.

_Example 6.21_.: If \(\mathbf{S}\) is the \((2,2)\)-bilabelled graph \((\overline{K_{2}},(2,\ldots,1),(1,\ldots,2))\), where \(\overline{K_{2}}\) is the edgeless graph on two vertices, then \(X^{G}_{\mathbf{S}}\) is the swap map \(S\) given in Proposition 6.3.

_Remark 6.22_.: Given Chassaniol's result and Example 6.20, the \((0,1)\)-bilabelled graph \(\mathbf{M}^{0,1}\) and the \((2,1)\)-bilabelled graph \(\mathbf{M}^{2,1}\), in particular, will be important in what follows.

For a fixed graph \(G\) having \(n\) vertices, we can form a category for the \(G\)-homomorphism matrices, as follows:

**Definition 6.23** (Category of \(G\)-Homomorphism Matrices).: For a given graph \(G\) having \(n\) vertices, the category of all \(G\)-homomorphism matrices, \(\mathcal{C}^{G}\), is the category whose objects are the vector spaces \((\mathbb{R}^{n})^{\otimes k}\), and, for any pair of objects \((\mathbb{R}^{n})^{\otimes k}\) and \((\mathbb{R}^{n})^{\otimes l}\), the morphism space \(\operatorname{Hom}_{\mathcal{C}^{G}}((\mathbb{R}^{n})^{\otimes k},(\mathbb{R} ^{n})^{\otimes l})\) is defined to be the \(\mathbb{R}\)-linear span of the set of all \(G\)-homomorphism matrices obtained from all isomorphism classes of \((k,l)\)-bilabelled graphs.

The vertical composition of morphisms is given by the usual multiplication of matrices, the tensor product of morphisms is given by the usual Kronecker product of matrices, and the unit object is \(\mathbb{R}\).

_Remark 6.24_.: It is easy to show that \(\mathcal{C}^{G}\) is a strict \(\mathbb{R}\)-linear monoidal category.

Mancinska and Roberson showed that the operations given on isomorphism classes of bilabelled graphs \(\mathbf{H}\) correspond bijectively with the matrix operations on \(G\)-homomorphism matrices \(X^{G}_{\mathbf{H}}\). This is stated more formally in the following three lemmas:

**Lemma 6.25** (Mancinska and Roberson (2020), Lemma 3.21).: _Suppose that \(G\) is a graph having \(n\) vertices. Let \([\mathbf{H_{1}}]\) be the isomorphism class of the \((k,l)\)-bilabelled graph \(\mathbf{H_{1}}=(H_{1},\mathbf{k},\mathbf{l})\), and let \([\mathbf{H_{2}}]\) be the isomorphism class of the \((l,m)\)-bilabelled graph \(\mathbf{H_{2}}=(H_{2},\mathbf{l}^{\prime},\mathbf{m})\)._

_Then_

\[X^{G}_{\mathbf{H_{2}}}X^{G}_{\mathbf{H_{1}}}=X^{G}_{\mathbf{H_{2}}\circ\mathbf{H_{1}}} \tag{12}\]

Figure 2: The composition \([\mathbf{H_{2}}]\circ[\mathbf{H_{1}}]\) of the \((2,3)\)–bilabelled graph diagram \(\mathbf{H_{1}}=(H_{1},(3^{\prime},2^{\prime}),(1^{\prime},2^{\prime},3^{\prime}))\) with the \((3,3)\)–bilabelled graph diagram \(\mathbf{H_{2}}=(H_{2},(2,1,2),(1,4,2))\), where \(H_{1}\) is the graph having (relabelled) vertex set \([3^{\prime}]\) and edge set \(\{(1^{\prime},2^{\prime})\}\) and \(H_{2}\) is the graph having vertex set \([4]\) and edge set \(\{(1,4)\}\). The vertices of the resulting bilabelled graph diagram on the RHS would be relabelled, for example, \(\{1,2^{\prime}\}\) would be relabelled to \(1\), and, \(\{2,1^{\prime},3^{\prime}\}\) would be relabelled to \(2\), to give the \((3,3)\)–bilabelled graph diagram \(\mathbf{H}=(H,(2,1),(1,4,2))\), where \(H\) is the graph having vertex set \([4]\) and edge set \(\{(1,4),(1,2)\}\).
**Lemma 6.26** (Mancinska and Roberson (2020), Lemma 3.23).: _Suppose that \(G\) is a graph having \(n\) vertices. Let \([\mathbf{H_{1}}]\) be the isomorphism class of the \((k,l)\)-bilabelled graph \(\mathbf{H_{1}}=(H_{1},\mathbf{k},\mathbf{l})\), and let \([\mathbf{H_{2}}]\) be the isomorphism class of the \((q,m)\)-bilabelled graph \(\mathbf{H_{2}}=(H_{2},\mathbf{q},\mathbf{m})\)._

_Then_

\[X^{G}_{\mathbf{H_{1}}}\otimes X^{G}_{\mathbf{H_{2}}}=X^{G}_{\mathbf{H_{1}}\otimes\mathbf{H_{2}}} \tag{13}\]

**Lemma 6.27** (Mancinska and Roberson (2020), Lemma 3.24).: _Suppose that \(G\) is a graph having \(n\) vertices, and let \([\mathbf{H}]\) be the isomorphism class of the \((k,l)\)-bilabelled graph \(\mathbf{H}=(H,\mathbf{k},\mathbf{l})\)._

_Then_

\[(X^{G}_{\mathbf{H}})^{*}=X^{G}_{\mathbf{H^{*}}} \tag{14}\]

Consequently, we obtain the following theorem, expressed in terms of functors and categories.

**Theorem 6.28**.: _Suppose that \(G\) is a graph having \(n\) vertices. Then there exists a full, strict \(\mathbb{R}\)-linear monoidal functor_

\[\mathcal{F}^{G}:\mathcal{G}\to\mathcal{C}^{G} \tag{15}\]

_that is defined on the objects of \(\mathcal{G}\) by \(\mathcal{F}^{G}(k)\coloneqq(\mathbb{R}^{n})^{\otimes k}\) and, for any objects \(k,l\) of \(\mathcal{G}\), the map_

\[\operatorname{Hom}_{\mathcal{G}}(k,l)\to\operatorname{Hom}_{\mathcal{C}^{G}} (\mathcal{F}^{G}(k),\mathcal{F}^{G}(l)) \tag{16}\]

_is given by_

\[[\mathbf{H}]\mapsto X^{G}_{\mathbf{H}} \tag{17}\]

_for all isomorphism classes of \((k,l)\)-bilabelled graphs._

Proof.: See the Technical Appendix. 

Main Result: A Spanning Set of Matrices for the Learnable, Linear \(\operatorname{Aut}(G)\)-Equivariant Layer Functions

Compare the following proposition with Chassaniol's result, given in Theorem 6.6.

**Proposition 6.29** (Mancinska and Roberson (2020), Theorem 8.4).: _We have that_

\[\mathcal{G}=\langle[\mathbf{M}^{0,1}],[\mathbf{M}^{2,1}],[\mathbf{A}],[\mathbf{S}]\rangle_{ \circ,\otimes,*} \tag{18}\]

_where \(\mathbf{M}^{0,1},\mathbf{M}^{2,1},\mathbf{A},\mathbf{S}\) are the bilabelled graphs defined in Examples 6.19, 6.20, and 6.21, and the operations \(\circ,\otimes,*\) on bilabelled graphs are those given in Definitions 6.11, 6.13 and 6.14, respectively._

We have come to the main result of this paper.

**Theorem 6.30**.: _Suppose that \(G\) is a graph having \(n\) vertices. Then the vector space of all \(\operatorname{Aut}(G)\)-equivariant, linear maps between tensor power spaces of \(\mathbb{R}^{n}\), \(\operatorname{Hom}_{\operatorname{Aut}(G)}((\mathbb{R}^{n})^{\otimes k},( \mathbb{R}^{n})^{\otimes l})\), when the standard basis of \(\mathbb{R}^{n}\) is chosen, is spanned by all \(G\)-homomorphism matrices \(X^{G}_{\mathbf{H}}\) obtained from all isomorphism classes of \((k,l)\)-bilabelled graphs._

Proof.: The statement and proof of this theorem is adapted from Mancinska and Roberson (2020), Theorem 8.5.

We know, by Chassaniol, that

\[\mathcal{C}(\operatorname{Aut}(G))=\langle M^{0,1},M^{2,1},A_{G},S\rangle_{+, \circ,\otimes,*} \tag{19}\]

By Examples 6.19, 6.20, and 6.21, we get that \(\mathcal{C}(\operatorname{Aut}(G))\) is equal to

\[\{X^{G}_{\mathbf{H}}\mid[\mathbf{H}]\in\langle[\mathbf{M}^{0,1}],[\mathbf{M}^{2,1}],[\mathbf{A}], [\mathbf{S}]\rangle_{+,\circ,\otimes,*}\} \tag{20}\]

and so, by Proposition 6.29, we have that

\[\mathcal{C}(\operatorname{Aut}(G))=\mathbb{R}\text{-span}\{X^{G}_{\mathbf{H}}\mid [\mathbf{H}]\in\mathcal{G}\} \tag{21}\]

Consequently, for any \(k,l\), we get that

\[\mathcal{C}(\operatorname{Aut}(G))(k,l)=\mathbb{R}\text{-span}\{X^{G}_{\mathbf{H}} \mid[\mathbf{H}]\in\mathcal{G}(k,l)\} \tag{22}\]

As the LHS of (22) is equivalent notation for \(\operatorname{Hom}_{\operatorname{Aut}(G)}((\mathbb{R}^{n})^{\otimes k},( \mathbb{R}^{n})^{\otimes l})\), we obtain our result. 

_Remark 6.31_.: In particular, Theorem 6.30 shows that \(\mathcal{C}^{G}=\mathcal{C}(\operatorname{Aut}(G))\), and that the objects of the category, \((\mathbb{R}^{n})^{\otimes k}\), are actually representations of \(\operatorname{Aut}(G)\), as defined in Section 5.

_Remark 6.32_.: It is very important to note the following. If \(H\) is a group that is isomorphic to the automorphism group of a graph \(G\) having \(n\) vertices, then the spanning set that we obtain for \(\operatorname{Hom}_{H}((\mathbb{R}^{n})^{\otimes k},(\mathbb{R}^{n})^{\otimes l})\) using Theorem 6.30 depends not only on how the automorphism group is embedded in the symmetric group \(S_{n}\) (itself thought of as matrices in \(GL(n)\) having chosen the standard basis of \(\mathbb{R}^{n}\)), which is given by how the vertices of the underlying graph \(G\) are labelled (up to all automorphisms), but also by what the edges are in \(G\).

We show in the Technical Appendix, for example, that \(D_{4}\) has three embeddings in \(S_{4}\), but that each embedding can be obtained separately from two graphs that are the complement of each other, both having the same labelling of the vertices, and all six instances (an embedding of \(D_{4}\) coming from a graph with a certain labelling of its vertices) give rise to different, albeit related, bases of \(\operatorname{Hom}_{D_{4}}(\mathbb{R}^{4},\mathbb{R}^{4})\), that is, a basis for the specific embedding and labelled graph chosen.

Theorem 6.30 states that, by considering all isomorphism classes of \((k,l)\)-bilabelled graphs, we can find a spanning set for \(\operatorname{Hom}_{\operatorname{Aut}(G)}((\mathbb{R}^{n})^{\otimes k},( \mathbb{R}^{n})^{\otimes l})\). However, by applying the following result, we can reduce the number of elements that appear in the spanning set by reducing the number of isomorphism classes that we need to consider.
**Proposition 6.33**.: _Let \(\mathbf{H}\) be a \((k,l)\)-bilabelled graph diagram whose underlying graph \(H\) contains a subset of free vertices that, whilst they may have edges amongst themselves, are entirely disconnected from any vertices that are in a connected component containing a non-free vertex._

_Then \(X^{G}_{\mathbf{H}}\) is a scalar multiple of \(X^{G}_{\mathbf{H}^{\prime}}\), where \(\mathbf{H}^{\prime}\) is the \((k,l)\)-bilabelled graph diagram obtained from \(\mathbf{H}\) having the subset removed._

Proof.: See the Technical Appendix. 

We also have the following useful result:

**Proposition 6.34** (Frobenius Duality).: _Suppose that we use Theorem 6.30 to obtain a spanning set for \(\operatorname{Hom}_{\operatorname{Aut}(G)}((\mathbb{R}^{n})^{\otimes k},( \mathbb{R}^{n})^{\otimes l})\). Then we can immediately obtain a spanning set for \(\operatorname{Hom}_{\operatorname{Aut}(G)}((\mathbb{R}^{n})^{\otimes q},( \mathbb{R}^{n})^{\otimes m})\), for any \(q,m\geq 0\) such that \(q+m=k+l\)._

Proof.: See the Technical Appendix. 

_Remark 6.35_.: In the Technical Appendix, we show that we can recover the diagram basis for \(\operatorname{Hom}_{S_{n}}((\mathbb{R}^{n})^{\otimes k},(\mathbb{R}^{n})^{ \otimes l})\) by looking at homomorphism matrices for the complement of the complete graph on \(n\) vertices, \(\overline{K_{n}}\).

This result immediately implies that, for a graph \(G\) having \(n\) vertices, the spanning set of \(\operatorname{Hom}_{\operatorname{Aut}(G)}((\mathbb{R}^{n})^{\otimes k},( \mathbb{R}^{n})^{\otimes l})\), given in (22), automatically includes the image, under \(\mathcal{F}^{G}\), of all set partitions of \([l+k]\) having at most \(n\) blocks in their equivalent \((k,l)\)-bilabelled graph diagram form, since \(\operatorname{Aut}(G)\) is a subgroup of \(S_{n}\).

_Remark 6.36_.: We have provided a number of examples for how to calculate a spanning set of \(\operatorname{Hom}_{\operatorname{Aut}(G)}((\mathbb{R}^{n})^{\otimes k},( \mathbb{R}^{n})^{\otimes l})\) for different graphs \(G\) and for low order tensor powers of \(\mathbb{R}^{n}\) in the Technical Appendix.

_Remark 6.37_.: We can adapt the characterisation for the case where the feature dimension of the layers is greater than one, and we can include bias terms in the layer functions themselves such that the equivariance property is maintained. See the Technical Appendix for more details.

_Remark 6.38_.: We appreciate that there will be some technical challenges when implementing the neural networks that we have characterised given the current state of computer hardware. We discuss this in more detail in the Technical Appendix.

## 7 Related Work

As stated in the Introduction, our work has been heavily influenced by the paper of Mancinska and Roberson (2020), who proved that two graphs are quantum isomorphic if and only if they have the same number of graph homomorphisms from any planar graph. They themselves built upon the work of Chassaniol (2019), who, by studying the quantum automorphism group of a graph, showed that a vertex-transitive graph has no quantum symmetries. These results are quantum adaptations of the work of Lovasz (1967), who showed that two graphs are isomorphic if and only if they have the same number of graph homomorphisms from any graph.

The work by Zaheer et al. (2017), who constructed the first permutation equivariant neural network for learning from sets, instigated the search to find and classify the linear layer functions appearing in other group equivariant neural networks. Maron et al. (2019) classified the linear layer functions in permutation equivariant neural networks where the layers are some tensor power of \(\mathbb{R}^{n}\) by finding the orbit basis. Godfrey et al. (2023) determined that using the diagram basis instead is more beneficial for performing computations with the linear layer functions in such networks. Finzi et al. (2021) developed a numerical algorithm that enabled them to find a basis for the equivariant linear layer functions for the orthogonal group \(O(n)\), the symplectic group \(Sp(n)\), and the special orthogonal group \(SO(n)\), for small values of \(n\) and for low order tensor power spaces of \(\mathbb{R}^{n}\).

However, the approach taken in this paper to characterise all of the learnable, linear, equivariant layer functions \(\operatorname{Hom}_{\operatorname{Aut}(G)}((\mathbb{R}^{n})^{\otimes k},( \mathbb{R}^{n})^{\otimes l})\) is closest in spirit to the one seen in the papers written by Pearce-Crump (2022, 2023a, 2023b). They used various sets of set partition diagrams to characterise all of the learnable, linear, equivariant layer functions in \(\operatorname{Hom}_{G}((\mathbb{R}^{n})^{\otimes k},(\mathbb{R}^{n})^{\otimes l})\) when \(G\) is any of the following groups: the symmetric group \(S_{n}\), the alternating group \(A_{n}\), the orthogonal group \(O(n)\), the symplectic group \(Sp(n)\), and the special orthogonal group \(SO(n)\).

## 8 Conclusion

We are the first to show how the combinatorics underlying bilabelled graphs provides the theoretical background for constructing neural networks that are equivariant to the automorphism group of a graph having \(n\) vertices when the layers are some tensor power of \(\mathbb{R}^{n}\). We found the form of the learnable, linear, \(\operatorname{Aut}(G)\)-equivariant layer functions between such tensor power spaces in the standard basis of \(\mathbb{R}^{n}\) by finding a spanning set for the \(\operatorname{Hom}\)-spaces in which these layer functions live. However, given that the number of isomorphism classes of \((k,l)\)-bilabelled graphs increases exponentially, both as the number of vertices in the graph \(G\) increases and as \(k\) and \(l\) increase, resulting in the number of spanning set elements increasing exponentially, it would be useful to find further ways of reducing the number of isomorphism classes of \((k,l)\)-bilabelled graphs that we need to consider. We leave this to future work.
## Acknowledgements

The author would like to thank his PhD supervisor Professor William J. Knottenbelt for being generous with his time throughout the author's period of research prior to the publication of this paper.

This work was funded by the Doctoral Scholarship for Applied Research which was awarded to the author under Imperial College London's Department of Computing Applied Research scheme. This work will form part of the author's PhD thesis at Imperial College London.
