Technical University of Denmark<EMAIL_ADDRESS>RWTH
Aachen University<EMAIL_ADDRESS>Research Council (DFG) within Research Training Group 2236 (UnRAVeL) David E.
Roberson and Tim Seppelt Mathematics of computing Discrete mathematics
Combinatorics Mathematics of computing Discrete mathematics Graph theory

###### Acknowledgements.

# Lasserre Hierarchy for Graph Isomorphism and Homomorphism
Indistinguishability

David E. Roberson  Tim Seppelt

###### Abstract

We show that feasibility of the $t^{\text{th}}$ level of the Lasserre
semidefinite programming hierarchy for graph isomorphism can be expressed as a
homomorphism indistinguishability relation. In other words, we define a class
$\mathcal{L}_{t}$ of graphs such that graphs $G$ and $H$ are not distinguished
by the $t^{\text{th}}$ level of the Lasserre hierarchy if and only if they
admit the same number of homomorphisms from any graph in $\mathcal{L}_{t}$. By
analysing the treewidth of graphs in $\mathcal{L}_{t}$ we prove that the
$3t^{\text{th}}$ level of Sherali–Adams linear programming hierarchy is as
strong as the $t^{\text{th}}$ level of Lasserre. Moreover, we show that this
is best possible in the sense that $3t$ cannot be lowered to $3t-1$ for any
$t$. The same result holds for the Lasserre hierarchy with non-negativity
constraints, which we similarly characterise in terms of homomorphism
indistinguishability over a family $\mathcal{L}_{t}^{+}$ of graphs.
Additionally, we give characterisations of level-$t$ Lasserre with non-
negativity constraints in terms of logical equivalence and via a graph
colouring algorithm akin to the Weisfeiler–Leman algorithm. This provides a
polynomial time algorithm for determining if two given graphs are
distinguished by the $t^{\text{th}}$ level of the Lasserre hierarchy with non-
negativity constraints.

###### keywords:

Lasserre hierarchy, homomorphism indistinguishability, Sherali–Adams
hierarchy, treewidth, semidefinite programming, linear programming, graph
isomorphism

###### category:

##  1 Introduction

The aim of this paper is to relate two rich sets of tools used to distinguish
non-isomorphic graphs: the Lasserre semidefinite programming hierarchy and
homomorphism indistinguishability.

Distinguishing non-isomorphic graphs is a ubiquitous problem in the
theoretical and practical study of graphs. The ability of certain graph
invariants to distinguish graphs has long been a rich area of study, leading
to fundamental questions such as the longstanding open problem of whether
almost all graphs are determined by their spectrum [37]. In practice,
deploying e.g. machine learning architectures powerful enough to distinguish
graphs with different features is of great importance [16]. This motivates an
in-depth study of the power of various graph invariants and tools used to
distinguish graphs.

Among such techniques is the Lasserre semidefinite programming hierarchy [22]
which can be used to relax the integer program for graph isomorphism
$\operatorname{ISO}(G,H)$, cf. Section 2.4. This yields a sequence of
semidefinite programs, i.e. the level-$t$ Lasserre relaxation of
$\operatorname{ISO}(G,H)$ for $t\geq 1$, which are infeasible for more and
more non-isomorphic graphs as $t$ grows. In [35, 29, 5], it was shown that in
general only the level-$\Omega(n)$ Lasserre system of equations can
distinguish all non-isomorphic $n$-vertex graphs. In [4], the Lasserre
hierarchy was compared with the Sherali–Adams111Following [4], when referring
to the Sherali–Adams relaxation of $\operatorname{ISO}(G,H)$ in this article,
we do not refer to the original relaxation [34] but to its variant introduced
by [3, 18], which corresponds more directly to other graph properties, cf.
Theorem 2.3 and [20]. linear programming hierarchy [34], which is closely
related to the Weisfeiler–Leman algorithm [38, 3, 18], the arguably most
relevant combinatorial method for distinguishing graphs. It was shown in [4]
that there exists a constant $c$ such that, for all graphs $G$ and $H$, if the
level-$ct$ Sherali–Adams relaxation of $\operatorname{ISO}(G,H)$ is feasible
then so is the level-$t$ Lasserre relaxation, which in turn implies that the
level-$t$ Sherali–Adams relaxation is feasible, cf. [23].

Another set of expressive equivalence relations comparing graphs is given by
homomorphism indistinguishability, a notion originating from the study of
graph substructure counts. Two graphs $G$ and $H$ are _homomorphism
indistinguishable_ over a family of graphs $\mathcal{F}$, in symbols
$G\equiv_{\mathcal{F}}H$, if the number of homomorphisms from $F$ to $G$ is
equal to the number of homomorphisms from $F$ to $H$ for every graph
$F\in\mathcal{F}$. The study of this notion began in 1967, when Lovász [24]
showed that two graphs $G$ and $H$ are isomorphic if and only if they are
homomorphism indistinguishable over all graphs. In recent years, many
prominent equivalence relations comparing graphs were characterised as
homomorphism indistinguishability relations over restricted graph classes [13,
14, 15, 10, 25, 20, 2, 28, 1, 31, 9, 30]. For example, a folklore result
asserts that two graphs have cospectral adjacency matrices iff they are
homomorphism indistinguishable over all cycle graphs, cf. [20]. Two graphs are
quantum isomorphic iff they are homomorphism indistinguishable over all planar
graphs [25]. Furthermore, feasibility of the level-$t$ Sherali–Adams
relaxation of $\operatorname{ISO}(G,H)$ has been characterised as homomorphism
indistinguishability over all graphs of treewidth at most $t-1$ [3, 18, 14].
In this way, notions from logic [14, 15, 30], category theory [10, 28, 1],
algebraic graph theory [13, 20], and quantum groups [25] have been related to
homomorphism indistinguishability.

###  1.1 Contributions

Although feasibility of the level-$t$ Lasserre relaxation of
$\operatorname{ISO}(G,H)$ was sandwiched between feasibility of the level-$ct$
and level-$t$ Sherali–Adams relaxation in [4], the constant $c$ remained
unknown. In fact, this $c$ is not explicit and depends on the implementation
details of an algorithm developed in that paper. Our main result asserts that
$c$ can be taken to be three and that this constant is best possible.

######  Theorem 1.1.

For two graphs $G$ and $H$ and every $t\geq 1$, the following implications
hold:

$G\simeq_{3t}^{\textup{SA}}H\implies G\simeq_{t}^{\textup{L}}H\implies
G\simeq_{t}^{\textup{SA}}H$

Furthermore, for every $t\geq 1$, there exist graphs $G$ and $H$ such that
$G\simeq_{3t-1}^{\textup{SA}}H$ and $G\not\simeq_{t}^{\textup{L}}H$.

Here, $G\simeq_{t}^{\textup{L}}H$ and $G\simeq_{t}^{\textup{SA}}H$ denote that
the level-$t$ Lasserre relaxation and respectively the level-$t$ Sherali–Adams
relaxation of $\operatorname{ISO}(G,H)$ are feasible.

Theorem 1.1 is proven using the framework of homomorphism
indistinguishability. In previous works [13, 27, 20, 30], the feasibility of
various systems of equations associated to graphs like the Sherali–Adams
relaxation of $\operatorname{ISO}(G,H)$ was characterised in terms of
homomorphism indistinguishability over certain graph classes. We continue this
line of research by characterising the feasibility of the level-$t$ Lasserre
relaxation of $\operatorname{ISO}(G,H)$ by homomorphism indistinguishability
of $G$ and $H$ over the novel class of graphs $\mathcal{L}_{t}$ introduced in
Definition 4.1.

######  Theorem 1.2.

For every integer $t\geq 1$, there is a minor-closed graph class
$\mathcal{L}_{t}$ of graphs of treewidth at most $3t-1$ such that for all
graphs $G$ and $H$ it holds that $G\simeq_{t}^{\textup{L}}H$ if and only if
$G\equiv_{\mathcal{L}_{t}}H$.

The bound on the treewidth of graphs in $\mathcal{L}_{t}$ in Theorem 1.2
yields the upper bound in Theorem 1.1 given the result of [3, 18, 4, 14] that
two graphs $G$ and $H$ satisfy $G\simeq_{t}^{\text{SA}}H$ if and only if they
are homomorphism indistinguishable over the class $\mathcal{TW}_{t-1}$ of
graphs of treewidth at most $t-1$. To our knowledge, Theorem 1.1 is the first
result which tightly relates equivalence relations on graphs by comparing the
graph classes which characterise them in terms of homomorphism
indistinguishability.

Our techniques extend to a stronger version of the Lasserre hierarchy which
imposes non-negativity constraints on all variables. Denoting feasibility of
the level-$t$ Lasserre relaxation of $\operatorname{ISO}(G,H)$ with non-
negativity constraints by $G\simeq_{t}^{\textup{L}^{+}}H$, we characterise
$\simeq_{t}^{\textup{L}^{+}}$ in terms of homomorphism indistinguishability
over the graph class $\mathcal{L}_{t}^{+}$, defined in Definition 4.1 as a
super class of $\mathcal{L}_{t}$. This is in line with previous work in [13,
20], where the feasibility of the level-$t$ Sherali–Adams relaxation of
$\operatorname{ISO}(G,H)$ without non-negativity constraints was characterised
as homomorphism indistinguishable over the class $\mathcal{PW}_{t-1}$ of
graphs of pathwidth at most $t-1$.

######  Theorem 1.3.

For every integer $t\geq 1$, there is a minor-closed graph class
$\mathcal{L}_{t}^{+}$ of graphs of treewidth at most $3t-1$ such that for all
graphs $G$ and $H$ it holds that $G\simeq_{t}^{\textup{L}^{+}}H$ if and only
if $G\equiv_{\mathcal{L}_{t}^{+}}H$.

Given the aforementioned correspondence between the Sherali–Adams relaxation
with and without non-negativity constraints and homomorphism
indistinguishability over graphs of bounded treewidth and pathwidth, we
conduct a detailed study of the relationship between the class of graphs of
bounded treewidth, pathwidth, and the classes $\mathcal{L}_{t}$ and
$\mathcal{L}_{t}^{+}$. Their results, depicted in Figure 1, yield independent
proofs of the known relations between feasibility of the Lasserre relaxation
with and without non-negativity constraints and the Sherali–Adams relaxation
with and without non-negativity constraints [5, 4, 20] using the framework of
homomorphism indistinguishability.

${\mathcal{OP}}$${\mathcal{PW}_{2t-1}}$${\mathcal{TW}_{\max\\{2t-1,2\\}}}$${\mathcal{TW}_{t-1}}$${\mathcal{L}_{t}}$${\mathcal{L}_{t}^{+}}$${\mathcal{TW}_{3t-1}}$
Figure 1: Relationship between $\mathcal{L}_{t}$, $\mathcal{L}_{t}^{+}$, the
classes of graphs of bounded treewidth, bounded pathwidth, and the class of
outerplanar graphs. An arrow $\mathcal{A}\rightarrow\mathcal{B}$ indicates
that $\mathcal{A}\subseteq\mathcal{B}$ and thus that $G\equiv_{\mathcal{B}}H$
implies $G\equiv_{\mathcal{A}}H$ for all graphs $G$ and $H$. For formal
statements, see Sections 4.1 and 4.2.

In the course of proving Theorems 1.2 and 1.3, we derive further equivalent
characterisations of $\simeq_{t}^{\textup{L}}$ and
$\simeq_{t}^{\textup{L}^{+}}$. These characterisations, which are mostly of a
linear algebraic nature, ultimately yield a characterisation of
$\simeq_{t}^{\textup{L}^{+}}$ in terms of a fragment of first-order logic with
counting quantifiers and indistinguishability under a polynomial time
algorithm akin to the Weisfeiler–Leman algorithm. In this way, we obtain the
following algorithmic result. It implies that _exact_ feasibility of the
Lasserre semidefinite program with non-negativity constraints can be tested in
polynomial time. In general, only the _approximate_ feasibility of
semidefinite programs can be decided efficiently, e.g. using the ellipsoid
method [21, 4].

######  Theorem 1.4.

Let $t\geq 1$. Given graphs $G$ and $H$, it can be decided in polynomial time
whether $G\simeq_{t}^{\textup{L}^{+}}H$.

Finally, for $t=1$, we show that $\mathcal{L}_{1}$ and $\mathcal{L}_{1}^{+}$
are respectively equal to the class $\mathcal{OP}$ of outerplanar graphs and
to the class of graphs of treewidth at most $2$. The following Theorem 1.5
parallels a result of [25] asserting that two graphs $G$ and $H$ are
indistinguishable under the $2$-WL algorithm iff
$G\simeq_{1}^{\textup{L}^{+}}H$.

######  Theorem 1.5.

Two graphs $G$ and $H$ satisfy $G\simeq_{1}^{\textup{L}}H$ iff
$G\equiv_{\mathcal{OP}}H$.

###  1.2 Techniques

In the first part of the paper (Section 3), linear algebraic tools developed
in [26, 25] are generalised to yield reformulations of the entire Lasserre
hierarchy with and without non-negativity results. Section 4 is concerned with
the graph theoretic properties of the graph classes $\mathcal{L}_{t}$ and
$\mathcal{L}_{t}^{+}$. For understanding the homomorphism indistinguishability
relations over these graph classes, the framework of bilabelled graphs and
their homomorphism tensors developed in [27, 20] is used. Despite this, our
approach is different from [20, 30] in the sense that here the graph classes
$\mathcal{L}_{t}$ and $\mathcal{L}_{t}^{+}$ are inferred from given systems of
equations, namely the Lasserre relaxation, rather than that a system of
equations is built for a given graph class.

##  2 Preliminaries

###  2.1 Linear Algebra

Let $\mathcal{S}_{+}$ denote the family of real _positive semidefinite
matrices_ , i.e. of matrices $M$ of the form $M_{ij}=v_{i}^{T}v_{j}$ for
vectors $v_{1},\dots,v_{n}$, the _Gram vectors_ of $M$. Write $M\succeq 0$ iff
$M\in\mathcal{S}_{+}$. Let $\mathcal{DNN}$ denote the family of _doubly non-
negative matrices_ , i.e. of entry-wise non-negative positive semidefinite
matrices.

A linear map $\Phi\colon\mathbb{C}^{m\times m}\to\mathbb{C}^{n\times n}$ is
_trace-preserving_ if $\operatorname{tr}\Phi(X)=\operatorname{tr}X$ for all
$X\in\mathbb{C}^{m\times m}$, _unital_ if
$\Phi(\operatorname{id}_{m})=\operatorname{id}_{n}$, _$\mathcal{K}$
-preserving_ for a family of matrices $\mathcal{K}$ if $\Phi(K)\in\mathcal{K}$
for all $K\in\mathcal{K}$, _positive_ if it is $\mathcal{S}_{+}$-preserving,
i.e. if $\Phi(X)$ is positive semidefinite for all positive semidefinite $X$,
_completely positive_ if $\operatorname{id}_{r}\otimes\Phi$ is positive for
all $r\in\mathbb{N}$. The _Choi matrix_ of $\Phi$ is
$C_{\Phi}=\sum_{i,j=1}^{m}E_{ij}\otimes\Phi(E_{ij})\in\mathbb{C}^{mn\times
mn}$.

A _tensor_ is an element $A\in\mathbb{C}^{n^{t}\times n^{t}}$ for some
$n,t\in\mathbb{N}$. The symmetric group $\mathfrak{S}_{2t}$ acts on
$\mathbb{C}^{n^{t}\times n^{t}}$ by permuting the coordinates, i.e. for all
$\boldsymbol{u},\boldsymbol{v}\in[n]^{t}$,
$A^{\sigma}(\boldsymbol{u},\boldsymbol{v})\coloneqq
A(\boldsymbol{x},\boldsymbol{y})$ where
$\boldsymbol{x}_{i}\coloneqq(\boldsymbol{uv})_{\sigma^{-1}(i)}$ and
$\boldsymbol{y}_{j-t}\coloneqq(\boldsymbol{uv})_{\sigma^{-1}(j)}$ for all
$1\leq i\leq t<j\leq 2t$.

For two vectors $v,w\in\mathbb{C}^{n}$, write $v\odot w$ for their _Schur
product_ , i.e. $(v\odot w)(i)\coloneqq v(i)w(i)$ for all $i\in[n]$.

###  2.2 Bilabelled Graphs and Homomorphism Tensors

All graphs in this article are undirected, finite, and without multiple edges.
A graph is _simple_ if it does not contain any loops. A _homomorphism_
$h\colon F\to G$ from a graph $F$ to a graph $G$ is a map $V(F)\to V(G)$ such
that for all $uv\in E(F)$ it holds that $h(u)h(v)\in E(G)$. Note that this
implies that any vertex in $F$ carrying a loop must be mapped to a vertex
carrying a loop in $G$. Write $\hom(F,G)$ for the number of homomorphisms from
$F$ to $G$. For a family of graphs $\mathcal{F}$ and graphs $G$ and $H$ write
$G\equiv_{\mathcal{F}}H$ if $G$ and $H$ are _homomorphism indistinguishable
over $\mathcal{F}$_, i.e. $\hom(F,G)=\hom(F,H)$ for all $F\in\mathcal{F}$.
Since the graphs $G$ and $H$ into which homomorphisms are counted, are
throughout assumed to be simple, looped graphs in $\mathcal{F}$ can generally
be disregarded as they do not admit any homomorphisms into simple graphs.

We recall the following definitions from [25, 20]. Let $\ell\geq 1$. An
_$(\ell,\ell)$ -bilabelled graph_ is a tuple
$\boldsymbol{F}=(F,\boldsymbol{u},\boldsymbol{v})$ where $F$ is a graph and
$\boldsymbol{u},\boldsymbol{v}\in V(F)^{\ell}$. The $\boldsymbol{u}$ are the
_in-labelled vertices_ of $\boldsymbol{F}$ while the $\boldsymbol{v}$ are the
_out-labelled vertices_ of $\boldsymbol{F}$. Given a graph $G$, the
_homomorphism tensor_ of $\boldsymbol{F}$ for $G$ is
$\boldsymbol{F}_{G}\in\mathbb{C}^{V(G)^{\ell}\times V(G)^{\ell}}$ whose
$(\boldsymbol{x},\boldsymbol{y})$-th entry is the number of homomorphisms
$h\colon F\to G$ such that $h(\boldsymbol{u}_{i})=\boldsymbol{x}_{i}$ and
$h(\boldsymbol{v}_{i})=\boldsymbol{y}_{i}$ for all $i\in[\ell]$.

For an $(\ell,\ell)$-bilabelled graph
$\boldsymbol{F}=(F,\boldsymbol{u},\boldsymbol{v})$, write
$\operatorname{soe}\boldsymbol{F}\coloneqq F$ for the underlying unlabelled
graph of $\boldsymbol{F}$. Write $\operatorname{tr}\boldsymbol{F}$ for the
unlabelled graph underlying the graph obtained from $\boldsymbol{F}$ by
identifying $\boldsymbol{u}_{i}$ with $\boldsymbol{v}_{i}$ for all
$i\in[\ell]$. For $\sigma\in\mathfrak{S}_{2t}$, write
$\boldsymbol{F}^{\sigma}\coloneqq(F,\boldsymbol{x},\boldsymbol{y})$ where
$\boldsymbol{x}_{i}\coloneqq(\boldsymbol{uv})_{\sigma(i)}$ and
$\boldsymbol{y}_{j-t}\coloneqq(\boldsymbol{uv})_{\sigma(j)}$ for all $1\leq
i\leq t<j\leq 2t$, i.e. $\boldsymbol{F}^{\sigma}$ is obtained from
$\boldsymbol{F}$ by permuting the labels according to $\sigma$. As a special
case, define $\boldsymbol{F}^{*}\coloneqq(F,\boldsymbol{v},\boldsymbol{u})$
the graph obtained by swapping in- and out-labels.

For two $(\ell,\ell)$-bilabelled graphs
$\boldsymbol{F}=(F,\boldsymbol{u},\boldsymbol{v})$ and
$\boldsymbol{F}^{\prime}=(F^{\prime},\boldsymbol{u}^{\prime},\boldsymbol{v}^{\prime})$,
write $\boldsymbol{F}\cdot\boldsymbol{F}^{\prime}$ for the graph obtained from
them by _series composition_. That is, the underlying unlabelled graph of
$\boldsymbol{F}\cdot\boldsymbol{F}^{\prime}$ is the graph obtained from the
disjoint union of $F$ and $F^{\prime}$ by identifying $\boldsymbol{v}_{i}$ and
$\boldsymbol{u}^{\prime}_{i}$ for all $i\in[\ell]$. Multiple edges arising in
this process are removed. The in-labels of
$\boldsymbol{F}\cdot\boldsymbol{F}^{\prime}$ lie on $\boldsymbol{u}$, the out-
labels on $\boldsymbol{v}^{\prime}$. Moreover, write
$\boldsymbol{F}\odot\boldsymbol{F}^{\prime}$ for the _parallel composition_ of
$\boldsymbol{F}$ and $\boldsymbol{F}^{\prime}$. That is, the underlying
unlabelled graph of $\boldsymbol{F}\odot\boldsymbol{F}^{\prime}$ is the graph
obtained from the disjoint union of $F$ and $F^{\prime}$ by identifying
$\boldsymbol{u}_{i}$ with $\boldsymbol{u}^{\prime}_{i}$ and
$\boldsymbol{v}_{i}$ with $\boldsymbol{v}^{\prime}_{i}$ for all $i\in[\ell]$.
Again, multiple edges are dropped. The in-labels of
$\boldsymbol{F}\odot\boldsymbol{F}^{\prime}$ lie on $\boldsymbol{u}$, the out-
labels on $\boldsymbol{v}$.

As observed in [25, 20], the benefit of these combinatorial operations is that
they have an algebraic counterpart. Formally, for all graphs $G$ and all
$(\ell,\ell)$-bilabelled graphs $\boldsymbol{F},\boldsymbol{F}^{\prime}$, it
holds that
$\operatorname{soe}\boldsymbol{F}_{G}=\hom(\operatorname{soe}\boldsymbol{F},G)$,
$\operatorname{tr}\boldsymbol{F}_{G}=\hom(\operatorname{tr}\boldsymbol{F},G)$,
$(\boldsymbol{F}_{G})^{\sigma}=(\boldsymbol{F}^{\sigma})_{G}$,
$(\boldsymbol{F}\cdot\boldsymbol{F}^{\prime})_{G}=\boldsymbol{F}_{G}\cdot\boldsymbol{F}^{\prime}_{G}$,
and
$(\boldsymbol{F}\odot\boldsymbol{F}^{\prime})_{G}=\boldsymbol{F}_{G}\odot\boldsymbol{F}^{\prime}_{G}$.

Slightly abusing notation, we say that two graphs $G$ and $H$ are homomorphism
indistinguishable over a family of bilabelled graphs $\boldsymbol{S}$, in
symbols $G\equiv_{\mathcal{S}}H$ if $G$ and $H$ are homomorphism
indistinguishable over the family
$\\{\operatorname{soe}\boldsymbol{S}\mid\boldsymbol{S}\in\mathcal{S}\\}$ of
the underlying unlabelled graphs of the $\boldsymbol{S}\in\mathcal{S}$.

###  2.3 Pathwidth and Treewidth

######  Definition 2.1.

Let $F$ and $T$ be graphs. A _$T$ -decomposition of $F$_ is a map $\beta\colon
V(T)\to 2^{V(F)}$ such that

  1. 1.

$\bigcup_{t\in V(T)}\beta(t)=V(F)$,

  2. 2.

for every $e\in E(F)$, there is $t\in V(T)$ such that $e\subseteq\beta(t)$,

  3. 3.

for every $v\in V(F)$, the set of $t\in V(T)$ such that $v\in\beta(t)$ induces
a connected component of $T$.

The _width_ of a $T$-decomposition $\beta$ is $\max_{t\in
V(T)}\left|\beta(t)\right|-1$. For a graph class $\mathcal{T}$, the
_$\mathcal{T}$ -width of $F$_ is the minimal width of a $T$-decomposition of
$F$ for $T\in\mathcal{T}$.

The _treewidth_ $\operatorname{tw}F$ of a graph $F$ is the minimal width of a
$T$-decomposition of $F$ where $T$ is a tree. Similarly, the _pathwidth_
$\operatorname{pw}F$ is the minimal width of a $P$-decomposition of $F$ where
$P$ is a path.

###  2.4 Systems of Equations for Graph Isomorphism

Two simple graphs $G$ and $H$ are isomorphic if and only if there exists a
$\\{0,1\\}$-solution to the system of equations $\operatorname{ISO}(G,H)$
which comprises variables $X_{gh}$ for $gh\in V(G)\times V(H)$ and equations

$\displaystyle\sum_{h\in V(H)}X_{gh}-1$ $\displaystyle=0$
$\displaystyle\text{for all }g\in V(G),$ (1) $\displaystyle\sum_{g\in
V(G)}X_{gh}-1$ $\displaystyle=0$ $\displaystyle\text{for all }h\in V(H),$ (2)
$\displaystyle X_{gh}X_{g^{\prime}h^{\prime}}$ $\displaystyle=0$ (3)

Here,
$\operatorname{rel}_{G}(g,g^{\prime})=\operatorname{rel}_{H}(h^{\prime},h^{\prime})$
if and only if both pairs of vertices are adjacent, non-adjacent, or
identical.

The Lasserre relaxation of $\operatorname{ISO}(G,H)$ is defined as follows. An
element $\\{g_{1}h_{1},\dots g_{\ell}h_{\ell}\\}\in\binom{V(G)\times
V(H)}{\ell}$ is a _partial isomorphism_ if $g_{i}=g_{j}\Leftrightarrow
h_{i}=h_{j}$ and $g_{i}g_{j}\in E(G)\Leftrightarrow h_{i}h_{j}\in E(H)$ for
all $i,j\in[\ell]$. See also Appendix A for a comparison to the version used
in [4].

######  Definition 2.2.

Let $t\geq 1$. The _level- $t$ Lasserre relaxation for graph isomorphism_ has
variables $y_{I}$ ranging over $\mathbb{R}$ for $I\in\binom{V(G)\times
V(H)}{\leq 2t}$. The constraints are

$\displaystyle M_{t}(y)\coloneqq(y_{I\cup J})_{I,J\in\binom{V(G)\times
V(H)}{\leq t}}$ $\displaystyle\succeq 0,$ (4) $\displaystyle\sum_{h\in
V(H)}y_{I\cup\\{gh\\}}$ $\displaystyle=y_{I}\text{ for all }I\text{ s.t.
}\left|I\right|\leq 2t-2\text{ and all }g\in V(G),$ (5)
$\displaystyle\sum_{g\in V(G)}y_{I\cup\\{gh\\}}$ $\displaystyle=y_{I}\text{
for all }I\text{ s.t. }\left|I\right|\leq 2t-2\text{ and all }h\in V(H),$ (6)
$\displaystyle y_{I}$ $\displaystyle=0\text{ if }I\text{ s.t.\@
}\left|I\right|\leq 2t\text{ is not partial isomorphism}$ (7) $\displaystyle
y_{\emptyset}$ $\displaystyle=1.$ (8)

If the system is feasible for two graphs $G$ and $H$, write
$G\simeq_{t}^{\textup{L}}H$. If the system together with the constraint
$y_{I}\geq 0$ for all $I\in\binom{V(G)\times V(H}{\leq 2t}$ is feasible, write
$G\simeq_{t}^{\textup{L}^{+}}H$.

For a definition of the Sherali–Adams relaxation of $\operatorname{ISO}(G,H)$
in the version used here following [4], the reader is referred to [19,
Appendix D.1]. Instead of feasibility of the level-$t$ Sherali–Adams
relaxation, one may think of the following equivalent notions:

######  Theorem 2.3 ([4, 14, 7]).

Let $t\geq 1$. For graphs $G$ and $H$, the following are equivalent:

  1. 1.

the level-$t$ Sherali–Adams relaxation of $\operatorname{ISO}(G,H)$ is
feasible, i.e. $G\simeq_{t}^{\textup{SA}}H$,

  2. 2.

$G$ and $H$ satisfy the same sentences of $t$-variable first order logic with
counting quantifiers,

  3. 3.

$G$ and $H$ are homomorphism indistinguishable over the class of treewidth at
most $t-1$,

  4. 4.

$G$ and $H$ are not distinguished by the $(t-1)$-dimensional Weisfeiler–Leman
algorithm,

##  3 From Lasserre to Homomorphism Tensors

In this section, the tools are developed which will be used to translate a
solution to the level-$t$ Lasserre relaxation into a statement on homomorphism
indistinguishability. For this purpose, three equivalent characterisations of
$\simeq_{t}^{\text{L}}$ and $\simeq_{t}^{\text{L}^{+}}$ are introduced.
Theorems 3.1 and 3.2 summarise our results. The notions in items 2–4 and the
graph classes $\mathcal{L}_{t}$ and $\mathcal{L}_{t}^{+}$ are defined in
Sections 3.1, 3.2, 3.4 and 4, respectively. Most of the proofs are of a linear
algebraic nature. Graph theoretical repercussions are discussed in Section 4.

######  Theorem 3.1.

Let $t\geq 1$. For graphs $G$ and $H$, the following are equivalent:

  1. 1.

the level-$t$ Lasserre relaxation of $\operatorname{ISO}(G,H)$ is feasible,

  2. 2.

$G$ and $H$ are level-$t$ $\mathcal{S}_{+}$-isomorphic,

  3. 3.

there is a level-$t$ $\mathcal{S}_{+}$-isomorphism map from $G$ to $H$,

  4. 4.

$G$ and $H$ are partially $t$-equivalent,

  5. 5.

$G$ and $H$ are homomorphism indistinguishable over $\mathcal{L}_{t}$.

######  Theorem 3.2.

Let $t\geq 1$. For graphs $G$ and $H$, the following are equivalent:

  1. 1.

the level-$t$ Lasserre relaxation of $\operatorname{ISO}(G,H)$ with non-
negativity constraints is feasible,

  2. 2.

$G$ and $H$ are level-$t$ $\mathcal{DNN}$-isomorphic,

  3. 3.

there is a level-$t$ $\mathcal{DNN}$-isomorphism map from $G$ to $H$,

  4. 4.

$G$ and $H$ are $t$-equivalent,

  5. 5.

$G$ and $H$ are homomorphism indistinguishable over $\mathcal{L}_{t}^{+}$.

Variants of the notions in items 2–4 have already been defined for the case
$t=1$ in [27]. Our contribution amounts to extending these definitions to the
entire Lasserre hierarchy. A recurring theme in this context is accounting for
additional symmetries. The variables $y_{I}$ of the Lasserre system of
equations, cf. Definition 2.2, are indexed by sets of vertex pairs rather than
by tuples of such. Hence, when passing from such variables to tuple-indexed
matrices, one must impose the additional symmetries arising this way. This is
formalised at various points using an action of the symmetric group on the
axes of the matrices. In the case $t=1$, such a set up is not necessary since
indices $I$ are of size at most $2$ and all occurring matrices can be taken to
be invariant under transposition.

In the subsequent sections, Theorems 3.1 and 3.2 will be proven in parallel.
The equivalence of items 1 and 2, 2 and 3, and 3 and 4 are established in
Section 3.3, Section 3.2, and Section 3.4, respectively. The statements on
homomorphism indistinguishability are proven in Section 4.

###  3.1 Isomorphism Relaxations via Matrix Families

In this section, as a first step towards proving Theorems 3.1 and 3.2, the
notion of level-$t$ $\mathcal{K}$-isomorphic graphs for arbitrary families of
matrices $\mathcal{K}$ is introduced. In [27], level-$1$
$\mathcal{K}$-isomorphic graphs where studied for various families of matrices
$\mathcal{K}$. In this work, the main interest lies on the family of positive
semidefinite matrices $\mathcal{S}_{+}$ and the family of entry-wise non-
negative positive semidefinite matrices $\mathcal{DNN}$. Level-$t$ isomorphism
for these families is proven to correspond to $\simeq_{t}^{\text{L}}$ and
$\simeq_{t}^{\text{L}^{+}}$ respectively, cf. Theorems 3.8 and 3.9.

######  Definition 3.3.

Let $\mathcal{K}$ be a family of matrices. Graphs $G$ and $H$ are said to be
_level- $t$ $\mathcal{K}$-isomorphic_, in symbols $G\cong^{t}_{\mathcal{K}}H$,
if there is a matrix $M\in\mathcal{K}$ with rows and columns indexed by
$(V(G)\times V(H))^{t}$ such that for every $g_{1}h_{1}\dots
g_{t}h_{t},g_{t+1}h_{t+1}\dots g_{2t}h_{2t}\in(V(G)\times V(H))^{t}$ the
following equations hold:

For every $i\in[2t]$, $\displaystyle\sum_{g_{i}\in V(G)}M_{g_{1}h_{1}\dots
g_{t}h_{t},g_{t+1}h_{t+1}\dots g_{2t}h_{2t}}$ $\displaystyle=\sum_{h_{i}\in
V(H)}M_{g_{1}h_{1}\dots g_{t}h_{t},g_{t+1}h_{t+1}\dots g_{2t}h_{2t}},$ (10)
$\displaystyle\sum_{h^{\prime}_{1},\dots,h^{\prime}_{2t}\in
V(H)}M_{g_{1}h^{\prime}_{1}\dots
g_{t}h^{\prime}_{t},g_{t+1}h^{\prime}_{t+1}\dots g_{2t}h^{\prime}_{2t}}$
$\displaystyle=1=\sum_{g^{\prime}_{1},\dots,g^{\prime}_{2t}\in
V(G)}M_{g^{\prime}_{1}h_{1}\dots
g^{\prime}_{t}h_{t},g^{\prime}_{t+1}h_{t+1}\dots g^{\prime}_{2t}h_{2t}}.$ (11)
If
$\operatorname{rel}_{G}(g_{1},\dots,g_{2t})\neq\operatorname{rel}_{H}(h_{1},\dots,h_{2t})$
then $\displaystyle M_{g_{1}h_{1}\dots g_{t}h_{t},g_{t+1}h_{t+1}\dots
g_{2t}h_{2t}}$ $\displaystyle=0.$ (12) For all $\sigma\in\mathfrak{S}_{2t}$,
$\displaystyle M_{g_{1}h_{1}\dots g_{t}h_{t},g_{t+1}h_{t+1}\dots
g_{2t}h_{2t}}$ $\displaystyle=M_{g_{\sigma(1)}h_{\sigma(1)}\dots
g_{\sigma(t)}h_{\sigma(t)},g_{\sigma(t+1)}h_{\sigma(t+1)}\dots
g_{\sigma(2t)}h_{\sigma(2t)}}.$ (13)

Note that for $t=1$ and any family of matrices $\mathcal{K}$ closed under
taking transposes Equation 13 is vacuous.

Systems of equations comparing graphs akin to Equations 10, 11, 12 and 13 were
also studied by [20]. Feasibility of such equations is typically invariant
under taking the complements of the graphs as remarked below. This semantic
property of the relation $\cong^{t}_{\mathcal{K}}$ is relevant in the context
of homomorphism indistinguishability as shown by [33].

######  Remark 3.4.

For a simple graph $G$, write $\overline{G}$ for its complement, i.e.
$V(\overline{G})\coloneqq V(G)$ and
$E(\overline{G})\coloneqq\binom{V(G)}{2}\setminus E(G)$. For all graphs $G$
and $H$ and $g_{1},\dots,g_{2t}\in V(G)$, $h_{1},\dots,h_{2t}\in V(H)$, it
holds that

$\operatorname{rel}_{G}(g_{1},\dots,g_{2t})=\operatorname{rel}_{H}(h_{1},\dots,h_{2t})\iff\operatorname{rel}_{\overline{G}}(g_{1},\dots,g_{2t})=\operatorname{rel}_{\overline{H}}(h_{1},\dots,h_{2t}).$

Thus, $G\cong^{t}_{\mathcal{K}}H$ if and only if
$\overline{G}\cong^{t}_{\mathcal{K}}\overline{H}$ for all families of matrices
$\mathcal{K}$ and $t\in\mathbb{N}$.

###  3.2 Choi Matrices and Isomorphism Maps

In this section, an alternative characterisation for level-$t$
$\mathcal{K}$-isomorphism is given. Intuitively, the indices of the matrix
$M\in\mathbb{C}^{(V(G)\times V(H))^{t}\times(V(G)\times V(H))^{t}}$ from
Definition 3.3 are regrouped yielding a linear map
$\Phi\colon\mathbb{C}^{V(G)^{t}\times V(G)^{t}}\to\mathbb{C}^{V(H)^{t}\times
V(H)^{t}}$. In linear algebraic terms, $M$ is the Choi matrix of $\Phi$. The
map $\Phi$ will later be interpreted as a function sending homomorphism
tensors of $(t,t)$-bilabelled graphs
$\boldsymbol{F}_{G}\in\mathbb{C}^{V(G)^{t}\times V(G)^{t}}$ with respect to
$G$ to their counterparts $\boldsymbol{F}_{H}$ for $H$.

The most basic bilabelled graphs, so called _atomic_ graphs, make their first
appearance in Theorem 3.6. These graphs are used to reformulate Equations 12
and 7. The atomic graphs are also the graphs which the sets $\mathcal{L}_{t}$
and $\mathcal{L}_{t}^{+}$ of Theorems 1.2 and 1.3 are generated by, cf.
Definition 4.1. Examples are depicted in Figures 2 and 3.

(a) $\boldsymbol{J}$

(b) $\boldsymbol{A}^{2,2t}$

(c) $\boldsymbol{I}^{2,2t}$

Figure 2: Examples of the atomic graphs from Definition 3.5. The gray lines
(the _wires_ [25]) indicate the in-labels (left) and out-labels (right).

######  Definition 3.5.

Let $t\geq 1$. A $(t,t)$-bilabelled graph
$\boldsymbol{F}=(F,\boldsymbol{u},\boldsymbol{v})$ is _atomic_ if all its
vertices are labelled. Write $\mathcal{A}_{t}$ for the set of
$(t,t)$-bilabelled atomic graphs. Note that the the set of atomic graphs
$\mathcal{A}_{t}$ is generated under parallel composition by the graphs

  * •

$\boldsymbol{J}\coloneqq(J,(1,\dots,t),(t+1,\dots,2t))$ with $V(J)=[2t]$,
$E(J)=\emptyset$,

  * •

$\boldsymbol{A}^{ij}\coloneqq(A^{ij},(1,\dots,t),(t+1,\dots,2t))$ with
$V(A^{ij})=[2t]$, $E(A^{ij})=\\{ij\\}$ for $1\leq i<j\leq 2t$,

  * •

$\boldsymbol{I}^{ij}$ for $1\leq i<j\leq 2t$ which is obtained from
$\boldsymbol{A}^{ij}$ by contracting the edge $ij$.

The following Theorem 3.6 relates the properties of $\Phi$ and $M$. In
Equation 16, $J$ denotes the all-ones matrix of appropriate dimension. Its
proof is deferred to Section C.1.

######  Theorem 3.6.

Let $t\geq 1$. Let $G$ and $H$ be graphs and
$\mathcal{K}\in\\{\mathcal{DNN},\mathcal{S}_{+}\\}$ be a family of matrices.
Let $\Phi\colon\mathbb{C}^{V(G)^{t}\times
V(G)^{t}}\to\mathbb{C}^{V(H)^{t}\times V(H)^{t}}$ be a linear map. Then the
following are equivalent.

  1. 1.

The Choi matrix $C_{\Phi}$ of $\Phi$ satisfies Equations 10, 11, 12 and 13 and
$C_{\Phi}\in\mathcal{K}$,

  2. 2.

$\Phi$ is a _level- $t$ $\mathcal{K}$-isomorphism map from $G$ to $H$_, i.e.
it satisfies

$\displaystyle\Phi\text{ is completely }\mathcal{K}\text{-preserving},$ (14)
$\displaystyle\Phi(\boldsymbol{A}_{G}\odot
X)=\boldsymbol{A}_{H}\odot\Phi(X)\text{ for all atomic
}\boldsymbol{A}\in\mathcal{A}_{t}\text{ and all
}X\in\mathbb{C}^{V(G)^{t}\times V(G)^{t}},$ (15)
$\displaystyle\Phi(J)=J=\Phi^{*}(J),$ (16)
$\displaystyle\Phi(X^{\sigma})=\Phi(X)^{\sigma}\text{ for all
}\sigma\in\mathfrak{S}_{2t}\text{ and all }X\in\mathbb{C}^{V(G)^{t}\times
V(G)^{t}}.$ (17)

  3. 3.

$\Phi^{*}$ is a level-$t$ $\mathcal{K}$-isomorphism map from $H$ to $G$.

We remark that Theorem 3.6 and in particular its Equation 16 has brought us
closer to interpreting the Lasserre system of equation from the perspective of
homomorphism indistinguishability. As argued in Remark 3.7, the map $\Phi$,
which will be understood as mapping homomorphism tensors $\boldsymbol{F}_{G}$
to $\boldsymbol{F}_{H}$, is sum-preserving. Since the sum of the entries of
these tensors equals the number of homomorphisms from their underlying
unlabelled graphs to $G$ and $H$, respectively, for establishing a connection
between $\mathcal{K}$-isomorphism maps and homomorphism indistinguishability.

######  Remark 3.7.

If a linear map $\Phi\colon\mathbb{C}^{n\times n}\to\mathbb{C}^{m\times m}$ is
such that $J=\Phi^{*}(J)$ then it is _sum-preserving_ , i.e.
$\operatorname{soe}X=\operatorname{soe}\Phi(X)$ for all
$X\in\mathbb{C}^{n\times n}$. Indeed,
$\operatorname{soe}X=\left<X,J\right>=\left<X,\Phi^{*}(J)\right>=\left<\Phi(X),J\right>=\operatorname{soe}\Phi(X)$
where $\left<A,B\right>\eqqcolon\operatorname{tr}(AB^{*})$. In particular, if
there is $\Phi$ satisfying Equations 15 and 16 for graphs $G$ and $H$ then
$|G|=|H|$.

###  3.3 Connection to Lasserre

By the following Theorems 3.8 and 3.9, the notions introduced in Definitions
3.3 and 3.6 are equivalent to the object of our main interest, namely
feasibility of the level-$t$ Lasserre relaxation with and without non-
negativity constraints. Our results extend those of [27, Lemma 9.1] to the
entire Lasserre hierarchy. The proofs are deferred to Section C.2.

######  Theorem 3.8.

Let $t\geq 1$. Two graphs $G$ and $H$ are level-$t$
$\mathcal{S}_{+}$-isomorphic if and only if the level-$t$ system of the
Lasserre hierarchy for graph isomorphism, i.e. Equations 4, 5, 6, 7 and 8, is
feasible.

######  Theorem 3.9.

Let $t\geq 1$. Two graphs $G$ and $H$ are level-$t$ $\mathcal{DNN}$-isomorphic
if and only if the level-$t$ system of the Lasserre hierarchy for graph
isomorphism Equations 4, 5, 6, 7 and 8 with the additional constraint
$y_{I}\geq 0$ for all $I\in\binom{V(G)\times V(H)}{\leq 2t}$ is feasible.

###  3.4 Isomorphisms between Matrix Algebras

To the two reformulations of $\simeq_{t}^{\textup{L}}$ and
$\simeq_{t}^{\textup{L}^{+}}$ from the previous sections, a third
characterisation is added in this section. It is shown that two graphs are
level-$t$ $\mathcal{S}_{+}$-isomorphic ($\mathcal{DNN}$-isomorphic) if and
only if certain matrix algebras associated to them are isomorphic. These
algebras will be identified as the algebras of homomorphism tensors for graphs
from the families $\mathcal{L}_{t}$ and $\mathcal{L}_{t}^{+}$. The so called
(partially) coherent algebras considered in this section are natural
generalisations of the coherent algebra which are well-studied in the context
of the $2$-dimensional Weisfeiler–Leman algorithm [8].

####  3.4.1 Partially Coherent Algebras and $\mathcal{S}_{+}$-Isomorphism Maps

Let $S\subseteq\mathbb{C}^{n^{t}\times n^{t}}$. A matrix algebra
$\mathcal{A}\subseteq\mathbb{C}^{n^{t}\times n^{t}}$ is _$S$ -partially
coherent_ if it is unital, self-adjoint, contains the all-ones matrix, and is
closed under Schur products with any matrix in $S$. A matrix algebra
$\mathcal{A}\subseteq\mathbb{C}^{n^{t}\times n^{t}}$ is _self-symmetrical_ if
for every $A\in\mathcal{A}$ and $\sigma\in\mathfrak{S}_{2t}$ also
$A^{\sigma}\in\mathcal{A}$. Note that for $t=1$, an algebra $\mathcal{A}$ is
self-symmetrical if for all $A\in\mathcal{A}$ also $A^{T}\in\mathcal{A}$.

######  Definition 3.10.

Given a graph $G$, construct its _$t$ -partially coherent algebra_
$\widehat{\mathcal{A}}^{t}_{G}$ as the minimal self-symmetrical $S$-partially
coherent algebra where $S$ is the set of homomorphism tensors of
$(t,t)$-bilabelled atomic graphs for $G$.

Two $n$-vertex graphs $G$ and $H$ are _partially $t$-equivalent_ if there is a
_partial $t$-equivalence_, i.e. a vector space isomorphism
$\varphi\colon\widehat{\mathcal{A}}^{t}_{G}\to\widehat{\mathcal{A}}^{t}_{H}$
such that

  1. 1.

$\varphi(M^{*})=\varphi(M)^{*}$ for all $M\in\widehat{\mathcal{A}}^{t}_{G}$,

  2. 2.

$\varphi(MN)=\varphi(M)\varphi(N)$ for all
$M,N\in\widehat{\mathcal{A}}^{t}_{G}$,

  3. 3.

$\varphi(I)=I$, $\varphi(\boldsymbol{A}_{G})=\boldsymbol{A}_{H}$ for all
$\boldsymbol{A}\in\mathcal{A}_{t}$, and $\varphi(J)=J$,

  4. 4.

$\varphi(\boldsymbol{A}_{G}\odot M)=\boldsymbol{A}_{H}\odot\varphi(M)$ for all
$\boldsymbol{A}\in\mathcal{A}_{t}$ and any
$M\in\widehat{\mathcal{A}}^{t}_{G}$.

  5. 5.

$\varphi(M^{\sigma})=\varphi(M)^{\sigma}$ for all
$M\in\widehat{\mathcal{A}}^{t}_{G}$ and all $\sigma\in\mathfrak{S}_{2t}$.

The following Theorem 3.11 extends [27, Theorem 5.2]. Its proof is deferred to
Section C.3.

######  Theorem 3.11.

Let $t\geq 1$. Two graphs $G$ and $H$ are partially $t$-equivalent if and only
if there is a level-$t$ $\mathcal{S}_{+}$-isomorphism map from $G$ to $H$.

####  3.4.2 Coherent Algebras and $\mathcal{DNN}$-Isomorphism Maps

(a) $\boldsymbol{J}$

(b) $\boldsymbol{A}^{1,2}$

(c) $\boldsymbol{I}^{1,2}$

Figure 3: The three atomic graphs in $\mathcal{A}_{1}$.

A matrix algebra $\mathcal{A}\subseteq\mathbb{C}^{n\times n}$ is _coherent_ if
it is unital, self-adjoint, contains the all-ones matrix and is closed under
Schur products.

For $t=1$, the $1$-adjacency algebra as defined below is equal to the well-
studied _adjacency algebra_ of a graph $G$, cf. [8]. The latter is the
smallest coherent algebra containing the adjacency matrix of the graph. The
former is generated by the homomorphism tensors of $(1,1)$-bilabelled atomic
graphs. These graphs are depicted in Figure 3. Their homomorphism tensors are
the all-ones matrix, the adjacency matrix of the graph, and the identity
matrix.

######  Definition 3.12.

Let $t\geq 1$. The _$t$ -adjacency algebra_ $\mathcal{A}_{G}^{t}$ of a graph
$G$ is the self-symmetrical coherent algebra generated by the homomorphism
tensors of the atomic graphs $\mathcal{A}_{t}$.

Two $n$-vertex graphs $G$ and $H$ are _$t$ -equivalent_ if there is _$t$
-equivalence_, i.e. a vector space isomorphism
$\varphi\colon\mathcal{A}^{t}_{G}\to\mathcal{A}^{t}_{H}$ such that

  1. 1.

$\varphi(M^{*})=\varphi(M)^{*}$ for all $M\in\mathcal{A}^{t}_{G}$,

  2. 2.

$\varphi(MN)=\varphi(M)\varphi(N)$ for all $M,N\in\mathcal{A}^{t}_{G}$,

  3. 3.

$\varphi(I)=I$, $\varphi(\boldsymbol{A}_{G})=\boldsymbol{A}_{H}$ for all
$\boldsymbol{A}\in\mathcal{A}_{t}$, and $\varphi(J)=J$,

  4. 4.

$\varphi(M\odot N)=\varphi(M)\odot\varphi(N)$ for all
$M,N\in\mathcal{A}^{t}_{G}$.

  5. 5.

$\varphi(M^{\sigma})=\varphi(M)^{\sigma}$ for all $M\in\mathcal{A}^{t}_{G}$
and all $\sigma\in\mathfrak{S}_{2t}$.

The following Theorem 3.13 extends [27, Theorem 6.3]. Its proof is deferred to
Section C.3.

######  Theorem 3.13.

Let $t\geq 1$. Two graphs $G$ and $H$ are $t$-equivalent if and only if there
is a level-$t$ $\mathcal{DNN}$-isomorphism map from $G$ to $H$.

##  4 Homomorphism Indistinguishability

Using techniques from [20], we finally establish a characterisation of when
the level-$t$ Lasserre relaxation of $\operatorname{ISO}(G,H)$ is feasible in
terms of homomorphism indistinguishability of $G$ and $H$. In order to do so,
we introduce the graph classes $\mathcal{L}_{t}$ and $\mathcal{L}_{t}^{+}$. In
Section 4.1, we relate $\mathcal{L}_{t}$ and $\mathcal{L}_{t}^{+}$ to the
classes of graphs of bounded treewidth and pathwidth obtaining the results
depicted in Figure 1. In Section 4.2, $\mathcal{L}_{1}$ and
$\mathcal{L}_{1}^{+}$ are identified as the classes of outerplanar graphs and
graphs of treewidth two, respectively.

######  Definition 4.1.

Let $t\geq 1$. Write $\mathcal{L}_{t}^{+}$ for the class of $(t,t)$-bilabelled
graphs generated by the set of atomic graphs $\mathcal{A}_{t}$ under parallel
composition, series composition, and the action of $\mathfrak{S}_{2t}$ on the
labels.

Write $\mathcal{L}_{t}\subseteq\mathcal{L}_{t}^{+}$ for the class of
$(t,t)$-bilabelled graphs generated by the set of atomic graphs
$\mathcal{A}_{t}$ under parallel composition with graphs from
$\mathcal{A}_{t}$, series composition, and the action of $\mathfrak{S}_{2t}$
on the labels.

Note that the only difference between $\mathcal{L}_{t}$ and
$\mathcal{L}_{t}^{+}$ is that $\mathcal{L}_{t}$ is closed under parallel
composition with atomic graphs only. This reflects an observation by [20]
relating the closure under arbitrary gluing products to non-negative solutions
to systems of equations characterising homomorphism indistinguishability.
Intuitively, one may use arbitrary Schur products, the algebraic counterparts
of gluing, for a Vandermonde interpolation argument, cf. [19, Appendix B.4].

The following Section 4 illustrates how the operations in Definition 4.1 can
be used to generate more complicated graphs from the atomic graphs.

Let $t\geq 1$. The class $\mathcal{L}_{t}$ contains a bilabelled graph whose
underlying unlabelled graph is isomorphic to the $3t$-clique $K_{3t}$.

######  Proof 4.2.

Let $\boldsymbol{E}\coloneqq\bigodot_{1\leq i<j\leq
2t}\boldsymbol{A}^{ij}\in\mathcal{A}_{t}$. The graph underlying
$\boldsymbol{E}\odot(\boldsymbol{E}\cdot\boldsymbol{E})$ is isomorphic to
$K_{3t}$.

The only missing implications of Theorems 3.1 and 3.2 follow from the next two
theorems:

######  Theorem 4.3.

Let $t\geq 1$. Two graphs $G$ and $H$ are homomorphism indistinguishable over
$\mathcal{L}_{t}$ if and only if they are partially $t$-equivalent.

######  Theorem 4.4.

Let $t\geq 1$. Two graphs $G$ and $H$ are homomorphism indistinguishable over
$\mathcal{L}_{t}^{+}$ if and only if they are $t$-equivalent.

For the proofs of Theorems 4.3 and 4.4, we extend the framework developed by
[20]. In this work, the authors introduced tools for constructing systems of
equations characterising homomorphism indistinguishably over classes of
labelled graphs. A requirement of these tools is that the graph class in
question is _inner-product compatible_ [20, Definition 24]. This means that
for every two labelled graphs $\boldsymbol{R}$ and $\boldsymbol{S}$ one can
write the inner-product of their homomorphism vectors $\boldsymbol{R}_{G}$ and
$\boldsymbol{S}_{G}$ as the sum-of-entries of some $\boldsymbol{T}_{G}$ where
$\boldsymbol{T}$ is labelled graph from the class. Due to the correspondence
between combinatorial operations on labelled graphs and algebraic operations
on their homomorphism vectors, cf. Section 2.2, this is equivalent to the
graph theoretic assumption that
$\operatorname{soe}(\boldsymbol{R}\odot\boldsymbol{S})=\operatorname{soe}(\boldsymbol{T})$,
i.e. the unlabelled graph obtained by unlabelling the gluing product of
$\boldsymbol{R}$ and $\boldsymbol{S}$ can be labelled such that the resulting
labelled graph is in the class.

We extend this notion to bilabelled graphs. A class of $(t,t)$-bilabelled
graphs $\mathcal{S}$ is said to be _inner-product compatible_ if for all
$\boldsymbol{R},\boldsymbol{S}\in\mathcal{S}$ there is a graph
$\boldsymbol{T}\in\mathcal{S}$ such that
$\operatorname{tr}(\boldsymbol{R}\cdot\boldsymbol{S}^{*})=\operatorname{soe}(\boldsymbol{T})$.
This definition is inspired by the inner-product on $\mathbb{C}^{n\times n}$
given by $\left<A,B\right>\coloneqq\operatorname{tr}(AB^{*})$.

######  Lemma 4.5.

Let $t\geq 1$. The classes $\mathcal{L}_{t}$ and $\mathcal{L}_{t}^{+}$ are
inner-product compatible.

######  Proof 4.6.

Since $\mathcal{L}_{t}$ is closed under matrix products and taking transposes,
it suffices to show that for every $\boldsymbol{S}\in\mathcal{L}_{t}$ the
graph $\operatorname{tr}\boldsymbol{S}$ is the underlying unlabelled graph of
some element of $\mathcal{L}_{t}$. Indeed, for every $(t,t)$-bilabelled graphs
$\boldsymbol{F}$ it holds that
$\operatorname{tr}(\boldsymbol{F})=\operatorname{soe}(\boldsymbol{I}^{1,t+1}\odot\dots\odot\boldsymbol{I}^{t,2t}\odot\boldsymbol{F})$
where the $\boldsymbol{I}^{ij}$ are as in Definition 3.5. Since
$\mathcal{L}_{t}$ is closed under parallel composition with atomic graphs, the
claim follows. For $\mathcal{L}_{t}^{+}$, an analogous argument yields the
claim.

The following Theorem 4.7, which extends the toolkit for constructing systems
of equations characterising homomorphism indistinguishability over families of
bilabelled graphs, is the bilabelled analogue of [20, Theorem 13]. Write
$\mathbb{C}\mathcal{S}_{G}\subseteq\mathbb{C}^{V(G)^{t}\times V(G)^{t}}$ for
the vector space spanned by homomorphism tensors $\boldsymbol{S}_{G}$ for
$\boldsymbol{S}\in\mathcal{S}$.

######  Theorem 4.7.

Let $t\geq 1$ and $\mathcal{S}$ be an inner-product compatible class of
$(t,t)$-bilabelled graphs containing $\boldsymbol{J}$. For graphs $G$ and $H$,
the following are equivalent:

  1. 1.

$G$ and $H$ are homomorphism indistinguishable over $\mathcal{S}$,

  2. 2.

there exists a sum-preserving vector space isomorphism
$\varphi\colon\mathbb{C}\mathcal{S}_{G}\to\mathbb{C}\mathcal{S}_{H}$ such that
$\varphi(\boldsymbol{S}_{G})=\boldsymbol{S}_{H}$ for all
$\boldsymbol{S}\in\mathcal{S}$.

The proof of Theorem 4.7 is deferred to Appendix D. Theorems 4.3 and 4.4
follows from this theorem as described in Appendix D.

###  4.1 The Classes $\mathcal{L}_{t}$ and $\mathcal{L}_{t}^{+}$ and Graphs of
Bounded Treewidth

In this section, the classes $\mathcal{L}_{t}$ and $\mathcal{L}_{t}^{+}$ are
compared to the classes of graphs of bounded treewidth and pathwidth. Figure 1
depicts the relationships between these classes. The first result, Lemma 4.8,
gives an upper bound on the treewidth of graphs in $\mathcal{L}_{t}^{+}$. The
proof, which is by induction on the structure of elements in
$\mathcal{L}_{t}^{+}$ as given by Definition 4.1, is deferred to Section D.1.

######  Lemma 4.8.

Let $t\geq 1$. The treewidth of an unlabelled graph $F$ underlying some
$\boldsymbol{F}=(F,\boldsymbol{u},\boldsymbol{v})\in\mathcal{L}_{t}^{+}$ is at
most $3t-1$.

Lemma 4.8 in conjunction with Theorems 3.1 and 3.2 implies Theorems 1.2 and
1.3. As a corollary, this yields the upper bound in Theorem 1.1. Indeed, by
Theorem 2.3, $G\simeq_{t}^{\textup{SA}}H$ if and only if $G$ and $H$ are
homomorphism indistinguishable over the class of graphs of treewidth at most
$t-1$. Hence, if $G\simeq_{3t}^{\textup{SA}}H$ then
$G\simeq_{t}^{\textup{L}^{+}}H$ and in particular $G\simeq_{t}^{\textup{L}}H$.

It remains to show the lower bound asserted by Theorem 1.1, i.e. that $3t$
cannot be replaced by $3t-1$ for no $t\geq 1$. To that end, first observe that
Section 4 implies that the bound in Lemma 4.8 is tight. However, this
syntactic property of the graph class $\mathcal{L}_{t}$ does not suffice to
derive the aforementioned semantic property of $\simeq_{t}^{\textup{SA}}$ and
$\simeq_{t}^{\textup{L}}$. In fact, it could well be that for all graphs $G$
and $H$ if $G$ and $H$ are homomorphism indistinguishable over the graphs of
treewidth at most $3t-2$ also $\hom(K_{3t},G)=\hom(K_{3t},H)$ despite that
$\operatorname{tw}K_{3t}>3t-2$. That this does not hold is implied by a
conjecture of the first author [31] which asserts that every minor-closed
graph class $\mathcal{F}$ which is closed under taking disjoint unions
(_union-closed_) is _homomorphism distinguishing closed_ , i.e. for all
$F\not\in\mathcal{F}$ there exist graphs $G$ and $H$ such that
$G\equiv_{\mathcal{F}}H$ but $\hom(F,G)\neq\hom(F,H)$. Although being
generally open, this conjecture was proven by Daniel Neuen (personal
communication) for the class of graphs of treewidth at most $t$ for every $t$
using techniques of [11, 31]. Theorem 4.9 implies the last assertion of
Theorem 1.1.

######  Theorem 4.9.

For every $t\geq 1$, there exist graphs $G$ and $H$ such that
$G\simeq_{3t-1}^{\textup{SA}}H$ and $G\not\simeq_{t}^{\textup{L}}H$.

######  Proof 4.10.

Towards a contraction, suppose that $G\simeq_{3t-1}^{\textup{SA}}H\implies
G\simeq_{t}^{\textup{L}}H$ for all graphs $G$ and $H$. By Theorem 2.3,
$G\simeq_{3t-1}^{\textup{SA}}H$ if and only if $G$ and $H$ are homomorphism
indistinguishable over the class $\mathcal{TW}_{3t-2}$ of graphs of treewidth
at most $3t-2$. By Sections 4 and 3.1, if $G\equiv_{\mathcal{TW}_{3t-2}}H$
then $G\equiv_{\mathcal{L}_{t}}H$ and in particular
$\hom(K_{3t},G)=\hom(K_{3t},H)$. As shown by Daniel Neuen (personal
communication), the class $\mathcal{TW}_{3t-2}$ is homomorphism distinguishing
closed. As $\operatorname{tw}K_{3t}=3t-1$, it follows that there exist graphs
$G$ and $H$ with $G\simeq_{3t-1}^{\textup{SA}}H$ and
$\hom(K_{3t},G)\neq\hom(K_{3t},H)$. In particular,
$G\not\simeq_{t}^{\textup{L}}H$ by Theorem 3.1.

It is worth noting that the classes of unlabelled graphs underlying the
elements of $\mathcal{L}_{t}$ and $\mathcal{L}_{t}^{+}$ are themselves minor-
closed and union-closed. Hence, they are subject to the aforementioned
conjecture. Furthermore, by the Robertson–Seymour Theorem and [32], membership
in $\mathcal{L}_{t}$ and $\mathcal{L}_{t}^{+}$ can be tested in polynomial
time for every fixed $t\geq 1$. The proof of Lemma 4.11 is deferred to Section
D.2.

######  Lemma 4.11.

Let $t\geq 1$. The class of graphs underlying the elements of
$\mathcal{L}_{t}$ and the class of graphs underlying the elements of
$\mathcal{L}_{t}^{+}$ are minor-closed and union-closed.

The remainder of this section is dedicated to some further relations between
the classes of graphs of bounded treewidth or pathwidth, $\mathcal{L}_{t}$,
and $\mathcal{L}_{t}^{+}$. Note that these facts give independent proofs for
the correspondence between the feasibility of the level-$t$ Sherali–Adams
relaxation (without non-negativity constraints), which corresponds to
homomorphism indistinguishability over graphs of treewidth (pathwidth) at most
$t-1$, as proven by [13, 20], and the feasibility of the level-$t$ Lasserre
relaxation with and without non-negativity constraints.

First of all, it is easy to see that dropping the semidefiniteness constraint
Equation 4 of the level-$t$ Lasserre system of equations turns this system
essentially into the level-$2t$ Sherali–Adams system of equations without non-
negativity constraints, e.g. as defined in [19, Appendix D.1]. This is
paralleled by Lemma 4.12.

######  Lemma 4.12.

Let $t\geq 1$. For every graph $F$ with $\operatorname{pw}F\leq 2t-1$, there
is a graph $\boldsymbol{F}\in\mathcal{L}_{t}$ whose underlying unlabelled
graph is isomorphic to $F$.

Furthermore, one may drop Equation 4 from the level-$t$ Lasserre system of
equations with non-negativity constraints to obtain the level-$2t$
Sherali–Adams system of equations in its original form, i.e. with non-
negativity constraints. This is paralleled by Lemma 4.13.

######  Lemma 4.13.

Let $t\geq 1$. For every graph $F$ with $\operatorname{tw}F\leq 2t-1$, there
is a graph $\boldsymbol{F}\in\mathcal{L}_{t}^{+}$ whose underlying unlabelled
graph is isomorphic to $F$.

Since the diagonal entries of a positive semidefinite matrix are necessarily
non-negative, Equation 4 implies that any solution $(y_{I})$ to the level-$t$
Lasserre system of equations is such that $y_{I}\geq 0$ for all
$I\in\binom{V(G)\times V(H)}{\leq t}$. Hence, such a solution is a solution to
the level-$t$ Sherali–Adams system of equations as well. This is paralleled by
Lemma 4.14.

######  Lemma 4.14.

Let $t\geq 1$. For every graph $F$ with $\operatorname{tw}F\leq t-1$, there is
a graph $\boldsymbol{F}\in\mathcal{L}_{t}$ whose underlying unlabelled graph
is isomorphic to $F$.

The proofs of Lemmas 4.12, 4.13 and 4.14 are all by inductively constructing
an element of $\mathcal{L}_{t}^{+}$ using a tree decomposition of the given
graph. They are deferred to Section D.1.

###  4.2 The Classes $\mathcal{L}_{1}$ and $\mathcal{L}_{1}^{+}$

The classes $\mathcal{L}_{1}$ and $\mathcal{L}_{1}^{+}$ can be identified as
the class of outerplanar graphs and as the class of graphs of treewidth at
most two, respectively. This yields Theorem 1.5. Proofs are deferred to
Section D.3.

######  Proposition 4.15.

The class of unlabelled graphs underlying an element of $\mathcal{L}_{1}^{+}$
coincides with the class of graphs of treewidth at most two.

A graph $F$ is _outerplanar_ if it does not have $K_{4}$ or $K_{2,3}$ as a
minor. Equivalent, it is outerplanar if it has a planar drawing such that all
its vertices lie on the same face [36].

######  Proposition 4.16.

The class of unlabelled graphs underlying an element of $\mathcal{L}_{1}$
coincides with the class of outerplanar graphs.

As a corollary of Proposition 4.16, we observe the following:

######  Corollary 4.17.

If $G\equiv_{\mathcal{L}_{1}}H$ then $G$ is connected iff $H$ is connected.

##  5 Deciding Exact Feasibility of the Lasserre Relaxation with Non-
Negativity Constraints in Polynomial Time

This section is dedicated to proving Theorem 1.4. To that end, it is argued
that $\simeq_{t}^{\textup{L}^{+}}$ has equivalent characterisations in terms
of logical equivalence and a colouring algorithm akin to the $k$-dimensional
Weisfeiler–Leman algorithm [38]. This algorithm has polynomial running time.
It is defined as follows:

######  Definition 5.1.

Let $t\geq 1$, define for a graph $G$, $i\geq 1$, and
$\boldsymbol{r},\boldsymbol{s}\in V(G)^{t}$

$\displaystyle\mathsf{mwl}_{G}^{0}(\boldsymbol{r}\boldsymbol{s})$
$\displaystyle\coloneqq\operatorname{rel}_{G}(\boldsymbol{r}\boldsymbol{s}),$
$\displaystyle\mathsf{mwl}_{G}^{i-1/2}(\boldsymbol{r}\boldsymbol{s})$
$\displaystyle\coloneqq\left(\mathsf{mwl}_{G}^{i-1}(\sigma(\boldsymbol{r}\boldsymbol{s}))\
\middle|\ \sigma\in\mathfrak{S}_{2t}\right),$
$\displaystyle\mathsf{mwl}_{G}^{i}(\boldsymbol{r}\boldsymbol{s})$
$\displaystyle\coloneqq\left(\mathsf{mwl}_{G}^{i-1/2}(\boldsymbol{r}\boldsymbol{s}),\left\\{\\!\\!\left\\{\left(\mathsf{mwl}_{G}^{i-1/2}(\boldsymbol{r}\boldsymbol{t}),\mathsf{mwl}_{G}^{i-1/2}(\boldsymbol{t}\boldsymbol{s})\right)\
\middle|\ \boldsymbol{t}\in V(G)^{t}\right\\}\\!\\!\right\\}\right).$

The $\mathsf{mwl}_{G}^{i}$ for $i\in\mathbb{N}$ define increasingly fine
colourings of $V(G)^{2t}$. Let $\mathsf{mwl}_{G}^{\infty}$ denote the finest
such colouring. Two graphs $G$ and $H$ are not _distinguished by the
$t$-dimensional $\mathsf{mwl}$ algorithm_ if the multisets

$\left\\{\\!\\!\left\\{\mathsf{mwl}_{G}^{\infty}(\boldsymbol{r}\boldsymbol{s})\
\middle|\ \boldsymbol{r},\boldsymbol{s}\in
V(G)^{t}\right\\}\\!\\!\right\\}\quad\text{ and
}\quad\left\\{\\!\\!\left\\{\mathsf{mwl}_{H}^{\infty}(\boldsymbol{u}\boldsymbol{v})\
\middle|\ \boldsymbol{u},\boldsymbol{v}\in V(H)^{t}\right\\}\\!\\!\right\\}$

are the same.

Since the finest colouring $\mathsf{mwl}_{G}^{\infty}$ is reached in $\leq
n^{2t}-1$ iterations for graphs on $n$ vertices, for fixed $t$, it can be
tested in polynomial time whether two graphs are not distinguished by the
$t$-dimensional $\mathsf{mwl}$ algorithm. We are about to show that the latter
happens if and only if the level-$t$ Lasserre relaxation with non-negative
constraints is feasible. As a by-product, we obtain a logical characterisation
for this equivalence relation.

######  Definition 5.2.

For $t\geq 1$, let $\mathsf{M}^{t}$ denote the fragment of first-order logic
with counting quantifiers and at most $3t$ variables comprising the following
expressions:

  * •

$x_{i}=x_{j}$ and $Ex_{i}x_{j}$ for all $i,j\in[3t]$,

  * •

if $\varphi,\psi\in\mathsf{M}^{t}$ then $\neg\varphi$, $\varphi\land\psi$, and
$\varphi\lor\psi$ are in $\mathsf{M}^{t}$,

  * •

if $\varphi,\psi\in\mathsf{M}^{t}$ and $n\in\mathbb{N}$ then $\exists^{\geq
n}\boldsymbol{y}.\
\varphi(\boldsymbol{x},\boldsymbol{y})\land\psi(\boldsymbol{y},\boldsymbol{z})$
is in $\mathsf{M}^{t}$. Here, the bold face letters $\boldsymbol{x}$,
$\boldsymbol{y}$, $\boldsymbol{z}$ denote $t$-tuples of distinct variables.

The semantic of the quantifier $\exists^{\geq n}\boldsymbol{y}.\
\varphi(\boldsymbol{y})$ is that there exist at least $n$ many $t$-tuples of
vertices from the graph over which the formula is evaluated which satisfy
$\varphi$. The following Theorem 5.3 may be thought of as a analogue of
Theorem 2.3 for $\mathcal{L}_{t}^{+}$.

######  Theorem 5.3.

Let $t\geq 1$. For graphs $G$ and $H$, the following are equivalent:

  1. 1.

$G$ and $H$ are not distinguished by the $t$-dimensional $\mathsf{mwl}$
algorithm,

  2. 2.

$G$ and $H$ are homomorphism indistinguishable over $\mathcal{L}_{t}^{+}$,

  3. 3.

$G$ and $H$ satisfy the same $\mathsf{M}^{t}$-sentences.

The proof of Theorem 5.3 is deferred to Appendix E. It is conceptually similar
to arguments of [7, 14, 20]. As mentioned above, Theorem 5.3 implies Theorem
1.4.

##  6 Conclusion

We have established a characterisation of the feasibility of the level-$t$
Lasserre relaxation with and without non-negativity constraints of the integer
program $\operatorname{ISO}(G,H)$ for graph isomorphism in terms of
homomorphism indistinguishability over the graph classes $\mathcal{L}_{t}$ and
$\mathcal{L}_{t}^{+}$. By analysing the treewidth of the graphs
$\mathcal{L}_{t}$ and $\mathcal{L}_{t}^{+}$ and invoking results from the
theory of homomorphism indistinguishability, we have determined the precise
number of Sherali–Adams levels necessary such that their feasibility
guarantees the feasibility of the level-$t$ Lasserre relaxation. This
concludes a line of research brought forward in [4]. For feasibility of the
level-$t$ Lasserre relaxation with non-negativity constraints, we have given,
besides linear algebraic reformulations generalising the adjacency algebra of
a graph, a polynomial time algorithm deciding this property.

An interesting extension of our work might be an efficient algorithm for
computing an explicit partial $t$-equivalence between two graphs, cf.
Definitions 3.10 and 3.12, or deciding that no such map exists. This would
yield an efficient algorithm for deciding the exact feasibility of the
Lasserre semidefinite program without non-negativity constraints, cf. [4].

Another object meriting further investigations is the maximum number of
iterations needed by the $\mathsf{mwl}$-algorithm to terminate. Recent work
[17] suggests that the trivial bound of $O(n^{2t})$ rounds is far from best
possible. In virtue of Theorem 5.3, tighter bounds on this number would yield
for every $n$ proper subclasses of $\mathcal{L}_{t}$ whose homomorphism counts
suffice to determine whether $G\simeq_{t}^{\textup{L}^{+}}H$ for $n$-vertex
graphs $G$ and $H$.

## References

  * [1] Samson Abramsky, Tomás Jakl, and Thomas Paine.  Discrete density comonads and graph parameters.  In Helle Hvid Hansen and Fabio Zanasi, editors, Coalgebraic Methods in Computer Science - 16th IFIP WG 1.3 International Workshop, CMCS 2022, Colocated with ETAPS 2022, Munich, Germany, April 2-3, 2022, Proceedings, volume 13225 of Lecture Notes in Computer Science, pages 23–44. Springer, 2022.  doi:10.1007/978-3-031-10736-8\\_2.
  * [2] Albert Atserias, Phokion G. Kolaitis, and Wei-Lin Wu.  On the expressive power of homomorphism counts.  In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, pages 1–13. IEEE, 2021.  doi:10.1109/LICS52264.2021.9470543.
  * [3] Albert Atserias and Elitza Maneva.  Sherali–Adams Relaxations and Indistinguishability in Counting Logics.  SIAM Journal on Computing, 42(1):112–137, 2013.  doi:10.1137/120867834.
  * [4] Albert Atserias and Joanna Ochremiak.  Definable ellipsoid method, sums-of-squares proofs, and the isomorphism problem.  In Anuj Dawar and Erich Grädel, editors, Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK, July 09-12, 2018, pages 66–75. ACM, 2018.  doi:10.1145/3209108.3209186.
  * [5] Christoph Berkholz and Martin Grohe.  Limitations of algebraic approaches to graph isomorphism testing.  In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming, pages 155–166. Springer Berlin Heidelberg, 2015.  doi:10.1007/978-3-662-47672-7_13.
  * [6] Hans L. Bodlaender.  A partial k-arboretum of graphs with bounded treewidth.  Theoretical Computer Science, 209(1):1–45, 1998-12-06.  URL: https://www.sciencedirect.com/science/article/pii/S0304397597002284, doi:10.1016/S0304-3975(97)00228-4.
  * [7] Jin-Yi Cai, Martin Fürer, and Neil Immerman.  An optimal lower bound on the number of variables for graph identification.  Combinatorica, 12(4):389–410, 1992.  doi:10.1007/BF01305232.
  * [8] Gang Chen and Ilia Ponomarenko.  Lectures on Coherent Configurations.  Central China Normal University Press, Wuhan, 2018.  URL: https://www.pdmi.ras.ru/~inp/ccNOTES.pdf.
  * [9] Yijia Chen, Jörg Flum, Mingjun Liu, and Zhiyang Xun.  On algorithms based on finitely many homomorphism counts.  In Stefan Szeider, Robert Ganian, and Alexandra Silva, editors, 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, August 22-26, 2022, Vienna, Austria, volume 241 of LIPIcs, pages 32:1–32:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.MFCS.2022.32.
  * [10] Anuj Dawar, Tomáš Jakl, and Luca Reggio.  Lovász-type theorems and game comonads.  In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, pages 1–13. IEEE, 2021.  doi:10.1109/LICS52264.2021.9470609.
  * [11] Anuj Dawar and David Richerby.  The power of counting logics on restricted classes of finite structures.  In Jacques Duparc and Thomas A. Henzinger, editors, Computer Science Logic, pages 84–98. Springer Berlin Heidelberg, 2007.  doi:10.1007/978-3-540-74915-8_10.
  * [12] Anuj Dawar, Simone Severini, and Octavio Zapata.  Descriptive complexity of graph spectra.  Annals of Pure and Applied Logic, 170(9):993–1007, 2019.  URL: https://linkinghub.elsevier.com/retrieve/pii/S0168007219300338, doi:10.1016/j.apal.2019.04.005.
  * [13] Holger Dell, Martin Grohe, and Gaurav Rattan.  Lovász Meets Weisfeiler and Leman.  45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), pages 40:1–40:14, 2018.  doi:10.4230/LIPICS.ICALP.2018.40.
  * [14] Zdeněk Dvořák.  On recognizing graphs by numbers of homomorphisms.  Journal of Graph Theory, 64(4):330–342, August 2010.  URL: http://doi.wiley.com/10.1002/jgt.20461, doi:10.1002/jgt.20461.
  * [15] Martin Grohe.  Counting Bounded Tree Depth Homomorphisms.  In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’20, pages 507–520, New York, NY, USA, 2020. Association for Computing Machinery.  doi:10.1145/3373718.3394739.
  * [16] Martin Grohe.  word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data.  In Dan Suciu, Yufei Tao, and Zhewei Wei, editors, Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, June 14-19, 2020, pages 1–16. ACM, 2020.  doi:10.1145/3375395.3387641.
  * [17] Martin Grohe, Moritz Lichter, and Daniel Neuen.  The Iteration Number of the Weisfeiler-Leman Algorithm, 2023.  doi:10.48550/ARXIV.2301.13317.
  * [18] Martin Grohe and Martin Otto.  Pebble Games and Linear Equations.  The Journal of Symbolic Logic, 80(3):797–844, 2015.  URL: http://www.jstor.org/stable/43864249, doi:10.1017/jsl.2015.28.
  * [19] Martin Grohe, Gaurav Rattan, and Tim Seppelt.  Homomorphism tensors and linear equations.  arXiv:2111.11313 [cs, math], 2021.  URL: http://arxiv.org/abs/2111.11313, arXiv:2111.11313.
  * [20] Martin Grohe, Gaurav Rattan, and Tim Seppelt.  Homomorphism Tensors and Linear Equations.  In Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 70:1–70:20, Dagstuhl, Germany, 2022\. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/opus/volltexte/2022/16411, doi:10.4230/LIPIcs.ICALP.2022.70.
  * [21] Martin Grotschel.  Geometric Algorithms and Combinatorial Optimization.  Springer Berlin Heidelberg, S.l., 2012.
  * [22] Jean B. Lasserre.  Global optimization with polynomials and the problem of moments.  SIAM Journal on Optimization, 11(3):796–817, 2001.  doi:10.1137/S1052623400366802.
  * [23] Monique Laurent.  A Comparison of the Sherali–Adams, Lovász–Schrijver, and Lasserre Relaxations for 0-1 Programming.  Mathematics of Operations Research, 28(3):470–496, 2003.  URL: http://www.jstor.org/stable/4126981.
  * [24] László Lovász.  Operations with structures.  Acta Mathematica Academiae Scientiarum Hungarica, 18(3):321–328, September 1967.  doi:10.1007/BF02280291.
  * [25] Laura Mančinska and David E. Roberson.  Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 661–672, 2020.  doi:10.1109/FOCS46700.2020.00067.
  * [26] Laura Mancinska, David E. Roberson, Robert Samal, Simone Severini, and Antonios Varvitsiotis.  Relaxations of Graph Isomorphism.  In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 76:1–76:14, Dagstuhl, Germany, 2017\. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  URL: http://drops.dagstuhl.de/opus/volltexte/2017/7469, doi:10.4230/LIPIcs.ICALP.2017.76.
  * [27] Laura Mančinska, David E. Roberson, and Antonios Varvitsiotis.  Graph isomorphism: Physical resources, optimization models, and algebraic characterizations.  arXiv:2004.10893 [math], 2020-04-22.  URL: http://arxiv.org/abs/2004.10893, arXiv:2004.10893.
  * [28] Yoàv Montacute and Nihil Shah.  The pebble-relation comonad in finite model theory.  In Christel Baier and Dana Fisman, editors, LICS ’22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2 - 5, 2022, pages 13:1–13:11. ACM, 2022.  doi:10.1145/3531130.3533335.
  * [29] Ryan O’Donnell, John Wright, Chenggang Wu, and Yuan Zhou.  Hardness of robust graph isomorphism, lasserre gaps, and asymmetry of random graphs.  In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1659–1677. SIAM, 2014.  doi:10.1137/1.9781611973402.120.
  * [30] Gaurav Rattan and Tim Seppelt.  Weisfeiler–Leman and Graph Spectra.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2268–2285, 2023.  URL: https://epubs.siam.org/doi/abs/10.1137/1.9781611977554.ch87, doi:10.1137/1.9781611977554.ch87.
  * [31] David E. Roberson.  Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree, 2022.  Number: arXiv:2206.10321.  URL: http://arxiv.org/abs/2206.10321, arXiv:2206.10321[math].
  * [32] N. Robertson and P.D. Seymour.  Graph Minors XIII. The Disjoint Paths Problem.  Journal of Combinatorial Theory, Series B, 63(1):65–110, 1995.  URL: https://www.sciencedirect.com/science/article/pii/S0095895685710064, doi:https://doi.org/10.1006/jctb.1995.1006.
  * [33] Tim Seppelt.  Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors, 2023.  In preparation.
  * [34] Hanif D. Sherali and Warren P. Adams.  A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems.  SIAM Journal on Discrete Mathematics, 3(3):411–430, 1990.  doi:10.1137/0403036.
  * [35] Aaron Snook, Grant Schoenebeck, and Paolo Codenotti.  Graph isomorphism and the lasserre hierarchy, 2014.  URL: http://arxiv.org/abs/1401.0758, arXiv:1401.0758[cs,math].
  * [36] Maciej M. Sysło.  Characterizations of outerplanar graphs.  Discrete Mathematics, 26(1):47–53, 1979.  URL: https://www.sciencedirect.com/science/article/pii/0012365X79900608, doi:https://doi.org/10.1016/0012-365X(79)90060-8.
  * [37] Edwin R. van Dam and Willem H. Haemers.  Which graphs are determined by their spectrum?  Linear Algebra and its Applications, 373:241–272, 2003.  URL: https://linkinghub.elsevier.com/retrieve/pii/S002437950300483X, doi:10.1016/S0024-3795(03)00483-X.
  * [38] Boris Weisfeiler.  On Construction and Identification of Graphs, volume 558 of Lecture Notes in Mathematics.  Springer Berlin Heidelberg, Berlin, Heidelberg, 1976.  URL: http://link.springer.com/10.1007/BFb0089374, doi:10.1007/BFb0089374.

##  Appendix A Versions of the Lasserre Hierarchy

The level-$t$ Lasserre relaxation for graph isomorphism studied in [4] has a
slightly different form. For every $\alpha\in\mathbb{N}^{V(G)\times V(H)}$, it
comprises a real-valued variable $z_{\alpha}$. For an integer
$t\in\mathbb{N}$, write $M_{t}(z)$ for the matrix whose rows and columns are
indexed by $\alpha\in\mathbb{N}^{V(G)\times V(H)}$ such that
$|\alpha|\coloneqq\sum_{gh\in V(G)\times V(H)}\alpha_{gh}\leq t$ with
$(\alpha,\beta)$-th entry $z_{\alpha+\beta}$. Abusing notation by writing $gh$
for the $gh$-th standard basis vector in $\mathbb{N}^{V(G)\times V(H)}$, the
equations can be written as

$\displaystyle M_{t}(z)$ $\displaystyle\succeq 0$ (18)
$\displaystyle\sum_{g\in V(G)}z_{\alpha+gh}$ $\displaystyle=z_{\alpha}$
$\displaystyle\text{for all }\alpha\text{ s.t. }|\alpha|\leq 2t-2,$ (19)
$\displaystyle\sum_{h\in V(H)}z_{\alpha+gh}$ $\displaystyle=z_{\alpha}$
$\displaystyle\text{for all }\alpha\text{ s.t. }|\alpha|\leq 2t-2,$ (20)
$\displaystyle z_{\alpha}$ $\displaystyle=0$ $\displaystyle\text{if
}\alpha\text{ is not a partial isomorphism},$ (21) $\displaystyle
z_{\alpha+2gh}$ $\displaystyle=z_{\alpha+gh}$ $\displaystyle\text{for all
}\alpha\text{ s.t. }|\alpha|\leq 2t-2,$ (22)
$\displaystyle(z_{\alpha+\beta+gh})_{|\alpha|,|\beta|\leq 2t-2}$
$\displaystyle\succeq 0$ $\displaystyle\text{for all }gh\in V(G)\times V(H)$
(23)
$\displaystyle(z_{\alpha+\beta}-z_{\alpha+\beta+gh})_{|\alpha|,|\beta|\leq
2t-2}$ $\displaystyle\succeq 0$ $\displaystyle\text{for all }gh\in V(G)\times
V(H)$ (24) $\displaystyle z_{\emptyset}$ $\displaystyle=1$ (25)

$\alpha$ is a partial isomorphism iff for all $gh$ and $g^{\prime}h^{\prime}$
such that $\alpha_{gh},\alpha_{g^{\prime}h^{\prime}}>0$,
$\operatorname{rel}_{G}(gg^{\prime})=\operatorname{rel}_{H}(hh^{\prime})$.

######  Lemma A.1.

The system Equations 18, 18, 19, 20, 21, 22, 23, 24 and 25 has a solution iff
the system Equations 4, 5, 6, 7 and 8 has a solution.

######  Proof A.2.

Let $(y_{I})_{I\in\binom{V(G)\times V(H)}{\leq 2t}}$ be a solution to
Equations 4, 5, 6, 7 and 8. For $\alpha\in\mathbb{N}^{V(G)\times V(H)}$ with
$|\alpha|\leq 2t$, define $z_{\alpha}$ to be $y_{[\alpha]}$ where
$[\alpha]\in\binom{V(G)\times V(H)}{\leq 2t}$ is the set
$\\{gh\mid\alpha_{gh}\geq 1\\}$. Observe that
$[\alpha+\beta]=[\alpha]\cup[\beta]$ for all
$\alpha,\beta\in\mathbb{N}^{V(G)\times V(H)}$.

By Equation 4, let $v_{I}$ for $I\in\binom{V(G)\times V(H)}{\leq t}$ be real
vectors such that $y_{I\cup J}=\left<v_{I},v_{J}\right>$ for all
$I,J\in\binom{V(G)\times V(H)}{\leq 2t}$. Then
$z_{\alpha+\beta}=y_{[\alpha+\beta]}=y_{[\alpha]\cup[\beta]}=\langle
v_{[\alpha]},v_{[\beta]}\rangle.$ Hence, the vectors $v_{[\alpha]}$ for
$\alpha\in\mathbb{N}^{V(G)\times V(H)}$ with $|\alpha|\leq 2t$ witness
Equation 18. Furthermore,

$z_{\alpha+\beta+gh}=y_{[\alpha+\beta+gh]}=y_{[\alpha]\cup\\{gh\\}\cup[\beta]\cup\\{gh\\}}=\langle
v_{[\alpha+gh]},v_{[\beta+gh]}\rangle.$

Hence, the matrix in Equation 23 is positive semidefinite. For Equation 24,
similarly,

$z_{\alpha+\beta}-z_{\alpha+\beta+gh}=z_{\alpha+\beta}+z_{\alpha+\beta+gh}-z_{\alpha+\beta+gh}-z_{\alpha+\beta+gh}=\langle
v_{[\alpha]}-v_{[\alpha+gh]},v_{[\beta]}-v_{[\beta+gh]}\rangle.$

Equations 19, 20, 21 and 25 follow readily from Equations 5, 6, 7 and 8,
respectively. Equation 22 holds by definition since
$[\alpha+2gh]=[\alpha+gh]$.

Conversely, let $(z_{\alpha})$ be a solution to Equations 18, 18, 19, 20, 21,
22, 23, 24 and 25. Define $y_{I}$ for $I\in\binom{V(G)\times V(H)}{\leq 2t}$
as $z_{\delta_{I}}$ where $\delta_{I}\in\mathbb{N}^{V(G)\times V(H)}$ is the
indicator vector of $I$, i.e. $(\delta_{I})_{gh}=1$ if $gh\in I$ and
$(\delta_{I})_{gh}=0$ otherwise. By Equation 22, $z_{\delta_{I\cup
J}}=z_{\delta_{I}+\delta_{J}}$ for all $I,J\in\binom{V(G)\times V(H)}{\leq
2t}$. Hence, Equations 5, 6, 7 and 8 follow readily from Equations 19, 20, 21
and 25, respectively.

For Equation 4, let $v_{\alpha}$ for $\alpha\in\mathbb{N}^{V(G)\times V(H)}$
with $|\alpha|\leq t$ be vectors such that
$z_{\alpha+\beta}=\left<v_{\alpha},v_{\beta}\right>$ for all $\alpha,\beta$,
by Equation 18. Then $y_{I\cup J}=z_{\delta_{I}+\delta_{J}}=\langle
v_{\delta_{I}},v_{\delta_{J}}\rangle.$ for all $I,J\in\binom{V(G)\times
V(H)}{\leq 2t}$. Hence, Equation 4 holds.

##  Appendix B Extended Preliminaries

###  B.1 Linear Algebra

######  Lemma B.1 ([27, Lemma 4.4]).

Consider a family of matrices
$\mathcal{K}\in\\{\mathcal{DNN},\mathcal{S}_{+}\\}$ and a linear map
$\Phi\colon\mathbb{C}^{m\times m}\to\mathbb{C}^{n\times n}$. The following are
equivalent:

  1. 1.

the map $\operatorname{id}_{m}\otimes\Phi$ is $\mathcal{K}$-preserving,

  2. 2.

the Choi matrix $C_{\Phi}$ lies in $\mathcal{K}$,

  3. 3.

$\Phi$ is _completely $\mathcal{K}$-preserving_, i.e.
$\operatorname{id}_{r}\otimes\Phi$ is $\mathcal{K}$-preserving for all
$r\in\mathbb{N}.$

######  Lemma B.2 ([27, Lemma 4.9]).

Let $\Phi\colon\mathbb{C}^{n\times n}\to\mathbb{C}^{n\times n}$ be a linear
map which is completely positive, trace-preserving, and unital. Then for any
pair of matrices $X$ and $Y$ such that $\Phi(X)=Y$ and $\Phi^{*}(Y)=X$ it
holds that $\Phi(XW)=\Phi(X)\Phi(W)$ and $\Phi(WX)=\Phi(W)\Phi(X)$ for all
$W\in\mathbb{C}^{n\times n}$.

######  Lemma B.3 ([27, Lemma A.1]).

Let $\mathcal{A}$ and $\mathcal{B}$ be self-adjoint unital subalgebras of
$\mathbb{C}^{n\times n}$ and $\varphi\colon\mathcal{A}\to\mathcal{B}$ be a
trace-preserving isomorphism such that $\varphi(X^{*})=\varphi(X)^{*}$ for all
$X\in\mathcal{A}$. Then there exists a unitary $U\in\mathbb{C}^{n\times n}$
such that $\varphi(X)=UXU^{*}$ for all $X\in\mathcal{A}$.

######  Lemma B.4 ([27, Lemma 4.5]).

Let $D\in\mathbb{C}^{m\times n}$ be a matrix and let $u\in\mathbb{C}^{n}$ and
$v\in\mathbb{C}^{m}$. Then the following are equivalent:

  1. 1.

$D(u\odot w)=v\odot(Dw)$ for all $w\in\mathbb{C}^{n}$,

  2. 2.

$D_{ij}=0$ whenever $v_{i}\neq u_{j}$,

  3. 3.

$D^{*}(v\odot z)=u\odot(D^{*}z)$ for all $z\in\mathbb{C}^{m}$.

###  B.2 Pathwidth and Treewidth

The following slight generalisation of [6, Lemma 8] is used repeatedly in
Section 4.1.

######  Lemma B.5 ([6, Lemma 8]).

Let $G$ be a graph such that $\operatorname{tw}G\leq k$ and $|V(G)|\geq k+1$.
Then $G$ has a tree decomposition $\beta\colon T\to 2^{V(G)}$ such that

  1. 1.

$|\beta(t)|=k+1$ for all $t\in V(T)$, and

  2. 2.

$|\beta(s)\cap\beta(t)|=k$ for all $st\in E(T)$.

######  Proof B.6.

Suppose that the treewidth of $G$ is $\ell\leq k$. If $|V(G)|=k+1$ then the
tree decomposition over the one-vertex tree is as desired. Otherwise, any tree
decomposition of width at most $k$ must be over a graph on at least two
vertices. Let $\beta\colon T\to 2^{V(F)}$ be any tree decomposition of width
$\ell$. We repeatedly apply the following steps:

  * •

If $st\in E(T)$ is such that $\beta(s)\subseteq\beta(t)$ or
$\beta(t)\subseteq\beta(s)$ then the edge $st$ in $T$ can be contracted and
the set $\beta(s)\cup\beta(t)$ can be taken to be the bag at the vertex
obtained by contraction.

  * •

If $st\in E(T)$ and $|\beta(s)|<k+1$ and $\beta(t)\not\subseteq\beta(s)$ then
$\beta(s)$ can be enlarged by a vertex $v\in\beta(s)\setminus\beta(t)$.

  * •

If $st\in E(T)$ and $|\beta(s)|=|\beta(t)|=k+1$ and $|\beta(s)\cap\beta(t)|<k$
then subdivide the edge $st$ in $T$ by introducing a fresh vertex $r$. Choose
vertices $v\in\beta(s)\setminus\beta(t)$ and $w\in\beta(t)\setminus\beta(s)$
and let $\beta(r)\coloneqq(\beta(s)\setminus\\{v\\})\cup\\{w\\}$.

If none of these operations can be applied, the tree decomposition is as
desired.

Observe that the operations used in the proof of Lemma B.5 to manipulate the
decomposition tree were contraction and subdivision. If the decomposition tree
is in fact a path then the resulting tree will also be a path. This yields the
following Lemma B.7:

######  Lemma B.7.

Let $G$ be a graph such that $\operatorname{pw}G\leq k$ and $|V(G)|\geq k+1$.
Then $G$ has a path decomposition $\beta\colon T\to 2^{V(G)}$ such that

  1. 1.

$|\beta(t)|=k+1$ for all $t\in V(T)$, and

  2. 2.

$|\beta(s)\cap\beta(t)|=k$ for all $st\in E(T)$.

##  Appendix C Material Omitted in Section 3

###  C.1 Proof of Theorem 3.6

######  Proof C.1 (Proof of Theorem 3.6).

For the equivalence of Items 1 and 2, first note that, by Lemma B.1,
$C_{\Phi}\in\mathcal{K}$ if and only if Property (14) holds. Moreover, for
$g_{1},\dots,g_{2t}\in V(G)$ and $h_{1},\dots,h_{2t}\in V(H)$, the assertions

$\forall\boldsymbol{A}\in\mathcal{A}_{t},\quad\boldsymbol{A}_{G}(g_{1}\dots
g_{t},g_{t+1}\dots g_{2t})=\boldsymbol{A}_{H}(h_{1}\dots h_{t},h_{t+1}\dots
h_{2t})$

and
$\operatorname{rel}_{G}(g_{1},\dots,g_{2t})=\operatorname{rel}_{H}(h_{1},\dots,h_{2t})$
are equivalent. By Lemma B.4, Equations 15 and 12 are equivalent. Furthermore,
Equations 16 and 11 and Equations 17 and 13 are respectively equivalent. The
equivalence of Items 2 and 3 follows immediately from Lemmas B.1 and B.4.

###  C.2 Proof of Theorem 3.8

######  Proof C.2 (Proof of Theorem 3.8).

Suppose that $(y_{I})_{I\in\binom{V(G)\times V(H)}{\leq 2t}}$ is a solution to
Equations 4, 5, 6, 7 and 8. It is argued that the matrix defined via
$M_{g_{1}h_{1}\dots g_{t}h_{t},g_{t+1}h_{t+1}\dots g_{2t}h_{2t}}\coloneqq
y_{\\{g_{1}h_{1},\dots,g_{2t}h_{2t}\\}}$ satisfies Equations 10, 11, 12 and
13. Equation 12 follows directly from Equation 7. Equation 13 is immediate
from the definition.

By Equation 4, let $v_{I}$ for $I\in\binom{V(G)\times V(H)}{\leq t}$ be
vectors such that $y_{I\cup J}=\left<v_{I},v_{J}\right>$. Then

$M_{g_{1}h_{1}\dots
g_{t}h_{t},g_{t+1}h_{t+1}}=y_{\\{g_{1}h_{1},\dots,g_{2t}h_{2t}\\}}=\left<v_{\\{g_{1}h_{1},\dots,g_{t}h_{t}\\}},v_{\\{g_{t+1}h_{t+1},\dots,g_{2t}h_{2t}\\}}\right>.$

Thus, $M$ is positive semidefinite. It remains to verify Equations 10 and 11.

######  Claim 1.

Every $I\in\binom{V(G)\times V(H)}{\leq t-1}$ satisfies $\sum_{g\in
V(G)}v_{I\cup\\{gh\\}}=v_{I}=\sum_{h\in V(H)}v_{I\cup\\{gh\\}}$.

By Equations 7 and 6,

$\displaystyle\left\langle\sum_{g\in V(G)}v_{I\cup\\{gh\\}},\sum_{g\in
V(G)}v_{I\cup\\{gh\\}}\right\rangle$ $\displaystyle=\sum_{g,g^{\prime}\in
V(G)}\left\langle v_{I\cup\\{gh\\}},v_{I\cup\\{g^{\prime}h\\}}\right\rangle$
$\displaystyle=\sum_{g,g^{\prime}\in
V(G)}y_{I\cup\\{gh\\}\cup\\{g^{\prime}h\\}}$
$\displaystyle\stackrel{{\scriptstyle\eqref{lassere4}}}{{=}}\sum_{g\in
V(G)}y_{I\cup\\{gh\\}}\stackrel{{\scriptstyle\eqref{lassere3}}}{{=}}y_{I}.$

Observe that Equation 6 indeed applies since $t-1\leq 2t-2$ for all $t\geq 1$.
Moreover,

$\displaystyle\left<v_{I},\sum_{g\in V(G)}v_{I\cup\\{gh\\}}\right>=\sum_{g\in
V(G)}y_{I\cup\\{gh\\}}=y_{I}$

and hence combining the above equalities,

$\displaystyle\left\lVert v_{I}-\sum_{g\in
V(G)}v_{I\cup\\{gh\\}}\right\rVert^{2}=y_{I}-2y_{I}+y_{I}=0$

The claim is proven analogously when summation is over $h\in V(H)$. 1 implies
Equation 11. Indeed,

$\displaystyle\sum_{g_{1}h_{1}\dots g_{2t}h_{2t}\in V(G)}M_{g_{1}h_{1}\dots
g_{t}h_{t},g_{t+1}h_{t+1}\dots g_{2t}h_{2t}}$
$\displaystyle=\sum_{g_{1}h_{1}\dots g_{2t}h_{2t}\in
V(G)}y_{\\{g_{1}h_{1},\dots,g_{t}h_{t}\\}\cup\\{g_{t+1}h_{t+1}\dots
g_{2t}h_{2t}\\}}$ $\displaystyle=\sum_{g_{1}h_{1}\dots g_{2t}h_{2t}\in
V(G)}\left<v_{\\{g_{1}h_{1},\dots,g_{t}h_{t}\\}},v_{\\{g_{t+1}h_{t+1}\dots
g_{2t}h_{2t}\\}}\right>$
$\displaystyle=\left<v_{\emptyset},v_{\emptyset}\right>$
$\displaystyle=y_{\emptyset}$ $\displaystyle=1.$

Moreover, for Equation 10, letting $i=1$ to ease notation,

$\displaystyle\sum_{g_{1}\in V(G)}M_{g_{1}h_{1}\dots
g_{t}h_{t},g_{t+1}h_{t+1}\dots g_{2t}h_{2t}}$ $\displaystyle=\sum_{g_{1}\in
V(G)}y_{\\{g_{1}h_{1}\\}\cup\\{g_{2}h_{2}\dots
g_{t}h_{t}\\}\cup\\{g_{t+1}h_{t+1}\dots g_{2t}h_{2t}\\}}$
$\displaystyle=\sum_{g_{1}\in
V(G)}\left<v_{\\{g_{1}h_{1}\\}\cup\\{g_{2}h_{2}\dots
g_{t}h_{t}\\}},v_{\\{g_{t+1}h_{t+1}\dots g_{2t}h_{2t}\\}}\right>$
$\displaystyle=\sum_{h_{1}\in
V(G)}\left<v_{\\{g_{1}h_{1}\\}\cup\\{g_{2}h_{2}\dots
g_{t}h_{t}\\}},v_{\\{g_{t+1}h_{t+1}\dots g_{2t}h_{2t}\\}}\right>$
$\displaystyle=\sum_{h_{1}\in V(G)}M_{g_{1}h_{1}\dots
g_{t}h_{t},g_{t+1}h_{t+1}\dots g_{2t}h_{2t}}.$

This concludes the proof that $M$ satisfies Equations 10, 11, 12 and 13.

Conversely, let $v_{\vec{I}}$ for $\vec{I}\in(V(G)\times V(H))^{t}$ denote the
Gram vectors of a matrix $M$ satisfying Equations 10, 11, 12 and 13. Define
$v_{I}\coloneqq v_{\vec{I}}$ for $|I|=t$ and any ordering. By Equation 13,
$v_{I}$ is well-defined. Let furthermore,

$v_{I}^{g_{i+1}\dots g_{t}}\coloneqq\sum_{h_{i+1},\dots,h_{t}\in
V(H)}v_{\vec{I}g_{i+1}h_{i+1}\dots g_{t}h_{t}}$

for $I\in\binom{V(G)\times V(H)}{i}$ and $g_{i+1}\dots g_{t}\in V(G)^{t-i}$.
Define $v_{I}^{h_{i+1}\dots h_{t}}$ analogously.

######  Claim 2.

For all $g_{i+1}\dots g_{t},g^{\prime}_{i+1}\dots g^{\prime}_{t}\in
V(G)^{t-i}$, $v_{I}^{g_{i+1}\dots g_{t}}=v_{I}^{g^{\prime}_{i+1}\dots
g^{\prime}_{t}}$.

By definition, the term $\left\lVert v_{I}^{g_{i+1}\dots
g_{t}}-v_{I}^{g^{\prime}_{i+1}\dots g^{\prime}_{t}}\right\rVert^{2}$ is equal
to

$\displaystyle\sum_{\begin{subarray}{c}h_{i+1},\dots,h_{t}\in V(H),\\\
h^{\prime}_{i+1},\dots,h^{\prime}_{t}\in V(H)\end{subarray}}\big{(}$
$\displaystyle M_{\vec{I}g_{i+1}h_{i+1}\dots
g_{t}h_{t},\vec{I}g_{i+1}h^{\prime}_{i+1}\dots g_{t}h^{\prime}_{t}}$
$\displaystyle-2M_{\vec{I}g_{i+1}h_{i+1}\dots
g_{t}h_{t},\vec{I}g^{\prime}_{i+1}h^{\prime}_{i+1}\dots
g^{\prime}_{t}h^{\prime}_{t}}$
$\displaystyle+M_{\vec{I}g^{\prime}_{i+1}h_{i+1}\dots
g^{\prime}_{t}h_{t},\vec{I}g^{\prime}_{i+1}h^{\prime}_{i+1}\dots
g^{\prime}_{t}h^{\prime}_{t}}\big{)}.$

By Equation 10, this expression is zero.

By 2, the reference to $g_{i+1}\dots g_{t}$ can be dropped, yielding vectors
$v_{I}^{G}$ and $v_{I}^{H}$. It follows that

$\displaystyle|V(G)|^{t-i}v_{I}^{G}$ $\displaystyle=\sum_{g_{i+1}\dots
g_{t}\in V(G)^{t-i}}v_{I}^{g_{i+1}\dots
g_{t}}=\sum_{\begin{subarray}{c}g_{i+1}\dots g_{t}\in V(G)^{t-i}\\\
h_{i+1}\dots h_{t}\in V(H)^{t-i}\end{subarray}}v_{\vec{I}g_{i+1}h_{i+1}\dots
g_{t}h_{t}}$ $\displaystyle=\sum_{h_{i+1}\dots h_{t}\in
V(H)^{t-i}}v_{I}^{h_{i+1}\dots h_{t}}=|V(H)|^{t-i}v_{I}^{H}.$

This implies that $v_{I}^{G}=v_{I}^{H}$ since $G$ and $H$ have the same number
of vertices, cf. Remark 3.7. Let $v_{I}\coloneqq v_{I}^{G}=v_{I}^{H}$.

######  Claim 3.

If $I\cup J=I^{\prime}\cup J^{\prime}$ for
$I,I^{\prime},J,J^{\prime}\in\binom{V(G)\times V(H)}{\leq t}$ then
$\left<v_{I},v_{J}\right>=\left<v_{I^{\prime}},v_{J^{\prime}}\right>$.

Immediate from Equation 13.

Hence, $y_{I}$ for $I\in\binom{V(G)\times V(H)}{\leq 2t}$ can be set to
$\left<v_{I^{\prime}},v_{I^{\prime\prime}}\right>$ for any
$I^{\prime},I^{\prime\prime}\in\binom{V(G)\times V(H)}{\leq t}$ such that
$I=I^{\prime}\cup I^{\prime\prime}$. Then Equations 4, 5 and 6 holds by
construction. Equation 7 follows from Equation 12.

###  C.3 Proofs of Theorems 3.11 and 3.13

######  Proof C.3 (Proof of Theorem 3.11).

Let $\Phi\colon\mathbb{C}^{V(G)^{t}\times
V(G)^{t}}\to\mathbb{C}^{V(H)^{t}\times V(H)^{t}}$ be a level-$t$
$\mathcal{S}_{+}$-isomorphism map from $G$ to $H$, i.e. it satisfies Equations
14, 15, 16 and 17. By Remarks 3.7, 15 and 16,
$\Phi(\boldsymbol{A}_{G})=\boldsymbol{A}_{H}$ for all atomic
$\boldsymbol{A}\in\mathcal{A}_{t}$ and $|V(G)|=|V(H)|\eqqcolon n$. Similarly,
$\Phi^{*}(\boldsymbol{A}_{H})=\boldsymbol{A}_{G}$ for all atomic $A$ by
Theorem 3.6. By Equations 14 and 15, $\Phi$ is completely positive and unital.
By Theorem 3.6 and [27, Lemma 4.2], $\Phi$ is trace-preserving. Furthermore,

$\Phi(\boldsymbol{A}_{G})=\boldsymbol{A}_{H},\quad\Phi^{*}(\boldsymbol{A}_{H})=\boldsymbol{A}_{G},\quad\Phi(J)=J=\Phi^{*}(J).$

for all atomic $\boldsymbol{A}\in\mathcal{A}_{t}$. Thus, Lemma B.2 implies
that for any $W\in\mathbb{C}^{V(G)^{t}\times V(G)^{t}}$ we have
$\Phi(\boldsymbol{A}_{G}W)=\boldsymbol{A}_{H}\Phi(W)$ and
$\Phi(W\boldsymbol{A}_{G})=\Phi(W)\boldsymbol{A}_{H}$ for all atomic
$\boldsymbol{A}\in\mathcal{A}_{t}$. Hence, the restriction of $\Phi$ to
$\widehat{\mathcal{A}}^{t}_{G}$ witnesses that $G$ and $H$ are partially
$t$-equivalent.

Conversely, suppose that
$\varphi\colon\widehat{\mathcal{A}}^{t}_{G}\to\widehat{\mathcal{A}}^{t}_{H}$
is as in Definition 3.10. By Lemma B.3, there exists a unitary matrix
$U\in\mathbb{C}^{n^{t}\times n^{t}}$ such that $\varphi(X)=UXU^{*}$ for all
$X\in\widehat{\mathcal{A}}^{t}_{G}$. Let
$\widehat{\varphi}\colon\mathbb{C}^{V(G)^{t}\times
V(G)^{t}}\to\mathbb{C}^{V(H)^{t}\times V(H)^{t}}$ be the map given by
$\widehat{\varphi}(X)=UXU^{*}$. Let $\Pi\colon\mathbb{C}^{V(G)^{t}\times
V(G)^{t}}\to\widehat{\mathcal{A}}^{t}_{G}$ be the orthogonal projection onto
$\widehat{\mathcal{A}}^{t}_{G}$. Define $\Phi\colon\mathbb{C}^{V(G)^{t}\times
V(G)^{t}}\to\mathbb{C}^{V(H)^{t}\times V(H)^{t}}$ by
$\Phi\coloneqq\widehat{\varphi}\circ\Pi$. By [27, Lemma A.3],
$\widehat{\varphi}$ is completely positive and trace-preserving. By [27, Lemma
A.4], so is $\Pi$ and hence their composition $\Phi$. Hence, Equation 14
holds.

Furthermore, $\Pi(J)=J$ and hence $\Phi(J)=J=\Phi^{*}(J)$. So $\Phi$ satisfies
Equation 16.

For Equation 17, consider the linear map $\Lambda_{\sigma}\colon X\mapsto
X^{\sigma}$ for $\sigma\in\mathfrak{S}_{2t}$. Since
$\widehat{\mathcal{A}}_{G}$ is closed under the action of $\mathfrak{S}_{2t}$,
it holds that $\Lambda_{\sigma}\circ\Pi=\Pi\circ\Lambda_{\sigma}\circ\Pi$.
Furthermore, $(\Lambda_{\sigma})^{*}=\Lambda_{\sigma^{-1}}$ and $\Pi$ is self-
adjoint, i.e. $\Pi^{*}=\Pi$. Hence,

$\Pi\circ\Lambda_{\sigma}=\Pi^{*}\circ\Lambda_{\sigma}=(\Lambda_{\sigma^{-1}}\circ\Pi)^{*}=(\Pi\circ\Lambda_{\sigma^{-1}}\circ\Pi)^{*}=\Pi\circ\Lambda_{\sigma}\circ\Pi=\Lambda_{\sigma}\circ\Pi.$

So $\Pi$ and $\Lambda_{\sigma}$ commute. Hence,

$\Phi(X^{\sigma})=(\widehat{\varphi}\circ\Pi\circ\Lambda_{\sigma})(X)=(\widehat{\varphi}\circ\Lambda_{\sigma}\circ\Pi)(X)=((\widehat{\varphi}\circ\Pi)(X))^{\sigma}=\Phi(X)^{\sigma}.$

Equation 15 follows similarly, cf. the proof of [27, Theorem 5.2].

######  Proof C.4 (Proof of Theorem 3.13).

Let $\Phi\colon\mathbb{C}^{V(G)^{t}\times
V(G)^{t}}\to\mathbb{C}^{V(H)^{t}\times V(H)^{t}}$ be a level-$t$
$\mathcal{DNN}$-isomorphism map. Let $\varphi$ be the restriction of $\Phi$ to
$\mathcal{A}^{t}_{G}$. Given the arguments in the proof of Theorem 3.11, it
suffices to show that $\varphi(M\odot N)=\varphi(M)\odot\varphi(N)$ for all
$M,N\in\mathcal{A}^{t}_{G}$ and that $\varphi^{*}(M\odot
N)=\varphi^{*}(M)\odot\varphi^{*}(N)$ for all $M,N\in\mathcal{A}^{t}_{H}$.
This follows from [27, Lemma 6.2].

Conversely, suppose that
$\varphi\colon\mathcal{A}^{t}_{G}\to\mathcal{A}^{t}_{H}$ is as in Definition
3.12. By Lemma B.3, there exists a unitary matrix $U\in\mathbb{C}^{n^{t}\times
n^{t}}$ such that $\varphi(X)=UXU^{*}$ for all $X\in\mathcal{A}^{t}_{G}$. Let
$\widehat{\varphi}\colon\mathbb{C}^{V(G)^{t}\times
V(G)^{t}}\to\mathbb{C}^{V(H)^{t}\times V(H)^{t}}$ be the map given by
$\widehat{\varphi}(X)=UXU^{*}$. Let $\Pi\colon\mathbb{C}^{V(G)^{t}\times
V(G)^{t}}\to\mathcal{A}^{t}_{G}$ be the orthogonal projection onto
$\mathcal{A}^{t}_{G}$. Define $\Phi\colon\mathbb{C}^{V(G)^{t}\times
V(G)^{t}}\to\mathbb{C}^{V(H)^{t}\times V(H)^{t}}$ by
$\Phi\coloneqq\widehat{\varphi}\circ\Pi$. Given Theorem 3.11, it suffices to
argue that the Choi matrix of $\Phi$ is entry-wise non-negative. This can be
done as in the proof of [27, Theorem 6.3].

##  Appendix D Material Omitted in Section 4

######  Proof D.1 (Proof of Theorem 4.7).

For the forward direction, observe that for all
$\boldsymbol{R},\boldsymbol{S}\in\mathcal{S}$ it holds that
$\left<\boldsymbol{R}_{G},\boldsymbol{S}_{G}\right>=\operatorname{tr}(\boldsymbol{R}_{G}\boldsymbol{S}_{G}^{*})=\left<\boldsymbol{R}_{H},\boldsymbol{S}_{H}\right>$
by inner-product compatibility. Hence, by a Gram–Schmidt argument [19, Lemma
29], there exists a unitary map such that
$\varphi(\boldsymbol{S}_{G})=\boldsymbol{S}_{H}$ for all
$\boldsymbol{S}\in\mathcal{S}$. Since
$\varphi(\boldsymbol{J}_{G})=\boldsymbol{J}_{H}$ and $\varphi$ is unitary, it
is sum-preserving by Remark 3.7. Conversely, let $\varphi$ be as stipulated.
For every $\boldsymbol{S}\in\mathcal{S}$, it holds that
$\operatorname{soe}\boldsymbol{S}_{H}=\operatorname{soe}\varphi(\boldsymbol{S}_{G})=\operatorname{soe}\boldsymbol{S}_{G}$
since $\varphi$ is sum-preserving.

This completes the preparations for the proof of Theorems 4.3 and 4.4.

######  Proof D.2 (Proof of Theorems 4.3 and 4.4).

By comparing the operations from Definitions 3.10 and 4.1, it is easy to see
that $\mathbb{C}\mathcal{S}_{G}=\widehat{\mathcal{A}}^{t}_{G}$ for
$\mathcal{S}=\mathcal{L}_{t}$. By Lemmas 4.5 and 4.7, $G$ and $H$ are
homomorphism indistinguishable over $\mathcal{L}_{t}$ if and only if there is
sum-preserving vector space isomorphism
$\varphi\colon\widehat{\mathcal{A}}^{t}_{G}\to\widehat{\mathcal{A}}^{t}_{H}$
satisfying $\varphi(\boldsymbol{S}_{G})=\boldsymbol{S}_{H}$ for all
$\boldsymbol{S}\in\mathcal{L}_{t}$.

For all atomic $\boldsymbol{A}\in\mathcal{A}_{t}$, it holds that
$\varphi(\boldsymbol{A}_{G})=\boldsymbol{A}_{H}$. Furthermore, since
$\mathcal{L}_{t}$ is closed under the action of $\mathfrak{S}_{2t}$,
$\varphi(\boldsymbol{S}_{G}^{\sigma})=\varphi((\boldsymbol{S}^{\sigma})_{G})=(\boldsymbol{S}^{\sigma})_{H}=\boldsymbol{S}_{H}^{\sigma}$
for all $\sigma\in\mathfrak{S}_{2t}$. Finally, for all
$\boldsymbol{S},\boldsymbol{T}\in\mathcal{L}_{t}$ it holds that
$\varphi(\boldsymbol{S}_{G}\cdot\boldsymbol{T}_{G})=\varphi((\boldsymbol{S}\cdot\boldsymbol{T})_{G})=\boldsymbol{S}_{H}\cdot\boldsymbol{T}_{H}$
and
$\varphi(\boldsymbol{S}_{G}\odot\boldsymbol{T}_{G})=\varphi((\boldsymbol{S}\odot\boldsymbol{T})_{G})=\boldsymbol{S}_{H}\odot\boldsymbol{T}_{H}$.
The homomorphism matrices $\boldsymbol{S}_{G}$ for
$\boldsymbol{S}\in\mathcal{L}_{t}$ span
$\mathbb{C}\mathcal{S}_{G}=\widehat{\mathcal{A}}^{t}_{G}$. Hence, $\varphi$ is
a partial $t$-equivalence.

Conversely, every partial $t$-equivalence
$\varphi\colon\widehat{\mathcal{A}}^{t}_{G}\to\widehat{\mathcal{A}}^{t}_{H}$
is such that $\varphi(\boldsymbol{S}_{G})=\boldsymbol{S}_{H}$ for all
$\boldsymbol{S}\in\mathcal{L}_{t}$ by definition of $\mathcal{L}_{t}$. With
slight modifications, [27, Lemma A.3] yields that $\varphi$ is trace-
preserving, which implies with $\varphi(J)=J$ that $\varphi$ is sum-
preserving.

The proof of Theorem 3.2 is analogous.

###  D.1 Material Omitted in Section 4.1

######  Proof D.3 (Proof of Lemma 4.8).

By structural induction, it is shown that every
$\boldsymbol{F}=(F,\boldsymbol{u},\boldsymbol{v})\in\mathcal{L}^{+}_{t}$
admits a tree decomposition $\beta\colon V(T)\to 2^{V(F)}$ of width $3t-1$
such that the labelled vertices $\boldsymbol{u}$ and $\boldsymbol{v}$ lie
together in one bag, i.e. there exists $x\in V(T)$ such that
$\\{\boldsymbol{u}_{1},\dots,\boldsymbol{u}_{t},\boldsymbol{v}_{1},\dots,\boldsymbol{v}_{t}\\}\subseteq\beta(x)$.

This is clearly the case for all $\boldsymbol{F}\in\mathcal{A}_{t}$. Let
$\boldsymbol{F}=(F,\boldsymbol{u},\boldsymbol{v})$ and
$\boldsymbol{F}^{\prime}=(F^{\prime},\boldsymbol{u}^{\prime},\boldsymbol{v}^{\prime})$
from $\mathcal{L}^{+}_{t}$ be given. Suppose there are tree decompositions
$\beta\colon V(T)\to 2^{V(F)}$ and $\beta^{\prime}\colon V(T^{\prime})\to
2^{V(F^{\prime})}$ as in the inductive hypothesis. Let $x\in V(T)$ and
$x^{\prime}\in V(T^{\prime})$ be such that the labelled vertices of
$\boldsymbol{F}$ and $\boldsymbol{F}^{\prime}$ lie in $\beta(x)$ and
$\beta^{\prime}(x^{\prime})$ respectively. Let $S$ be the tree obtained by
taking the disjoint union of $T$, $T^{\prime}$, and a fresh vertex $y$, and
connecting $x$ and $x^{\prime}$ to $y$.

For the graph $\boldsymbol{F}\cdot\boldsymbol{F}^{\prime}$, an
$S$-decomposition is given by the function

$\gamma\colon z\mapsto\begin{cases}\beta(z),&\text{if }z\in V(T),\\\
\beta^{\prime}(z),&\text{if }z\in V(T^{\prime}),\\\
\\{\boldsymbol{u}_{1},\dots,\boldsymbol{u}_{t},\boldsymbol{v}^{\prime}_{1},\dots,\boldsymbol{v}^{\prime}_{t},\boldsymbol{v}_{1},\dots,\boldsymbol{v}_{t}\\},&\text{if
}z=y.\end{cases}$

where one may note that $\boldsymbol{v}_{i}=\boldsymbol{u}^{\prime}_{i}$ for
every $i\in[t]$ in $\boldsymbol{F}\cdot\boldsymbol{F}^{\prime}$. It is easy to
check that Definition 2.1 are satisfied. The decomposition is of width $3t-1$.

For the graph $\boldsymbol{F}\odot\boldsymbol{F}^{\prime}$, an
$S$-decomposition is given by the function

$\gamma\colon z\mapsto\begin{cases}\beta(z),&\text{if }z\in V(T),\\\
\beta^{\prime}(z),&\text{if }z\in V(T^{\prime}),\\\
\\{\boldsymbol{u}_{1},\dots,\boldsymbol{u}_{t},\boldsymbol{v}_{1},\dots,\boldsymbol{v}_{t}\\},&\text{if
}z=y.\end{cases}$

where one may note that $\boldsymbol{u}_{i}=\boldsymbol{u}^{\prime}_{i}$ and
$\boldsymbol{v}_{i}=\boldsymbol{v}^{\prime}_{i}$ for every $i\in[t]$ in
$\boldsymbol{F}\odot\boldsymbol{F}^{\prime}$. Again, it is easy to check that
the Definition 2.1 are satisfied. The decomposition is of width $3t-1$.

######  Lemma D.4.

Let $t\geq 1$. For every
$\boldsymbol{F}=(F,\boldsymbol{u},\boldsymbol{v})\in\mathcal{L}^{+}_{t}$ there
is a
$\boldsymbol{F}^{\prime}=(F^{\prime},\boldsymbol{u}^{\prime},\boldsymbol{v}^{\prime})\in\mathcal{L}^{+}_{t+1}$
such that $F\cong F^{\prime}$.

######  Proof D.5.

For a $(t,t)$-bilabelled graph
$\boldsymbol{F}=(F,\boldsymbol{u},\boldsymbol{v})$, write
$\widehat{\boldsymbol{F}}$ for the $(t+1,t+1)$-bilabelled graph
$(F,\boldsymbol{u}\boldsymbol{u}_{t},\boldsymbol{v}\boldsymbol{v}_{t})$, which
is obtained from $\boldsymbol{F}$ by repeating the final in- and out-label
respectively.

Observe that for all $\boldsymbol{A}\in\mathcal{A}_{t}$ it holds that
$\widehat{\boldsymbol{A}}\in\mathcal{A}_{t+1}$, cf. Definition 3.5. Also, for
all $(t,t)$-bilabelled graphs $\boldsymbol{R},\boldsymbol{S}$, one may observe
that
$\widehat{\boldsymbol{R}\odot\boldsymbol{S}}=\widehat{\boldsymbol{R}}\odot\widehat{\boldsymbol{S}}$
and
$\widehat{\boldsymbol{R}\cdot\boldsymbol{S}}=\widehat{\boldsymbol{R}}\cdot\widehat{\boldsymbol{S}}$.

Write $s\colon[2t]\to[2t+1]\setminus\\{t+1\\}$ for the bijection sending $i$
to $i$ if $i\leq t$ and $i$ to $i+1$ if $t+1\leq i\leq 2t$. For a permutation,
$\sigma\in\mathfrak{S}_{2t}$, write $\widehat{\sigma}\in\mathfrak{S}_{2(t+1)}$
for the permutation

$i\mapsto\begin{cases}s(\sigma(s^{-1}(i)))&\text{if }1\leq i\leq t\text{ or
}t+2\leq i\leq 2t+1,\\\ i&\text{if }i=t+1\text{ or }i=2t+2.\end{cases}.$

Observe that

$\widehat{\boldsymbol{F}^{\sigma}}=\left(\bigodot_{i=1}^{t}\boldsymbol{I}^{i,t+1+i}\odot\boldsymbol{I}^{t+1,s(\sigma(t))}\right)\cdot\widehat{\boldsymbol{F}}^{\widehat{\sigma}}\cdot\left(\bigodot_{i=1}^{t}\boldsymbol{I}^{i,t+1+i}\odot\boldsymbol{I}^{2t+2,s(\sigma(2t))}\right).$

In virtue of these observations, it can be easily seen inductively that if
$\boldsymbol{F}\in\mathcal{L}^{+}_{t}$ then
$\widehat{\boldsymbol{F}}\in\mathcal{L}^{+}_{t+1}$. Since the underlying
unlabelled graphs of $\boldsymbol{F}$ and $\widehat{\boldsymbol{F}}$ are
identical, the claim follows.

######  Lemma D.6.

Let $t\geq 1$. For every
$\boldsymbol{F}=(F,\boldsymbol{u},\boldsymbol{v})\in\mathcal{L}_{t}$ there is
a
$\boldsymbol{F}^{\prime}=(F^{\prime},\boldsymbol{u}^{\prime},\boldsymbol{v}^{\prime})\in\mathcal{L}_{t+1}$
such that $F\cong F^{\prime}$.

######  Proof D.7.

Analogous to Lemma D.4.

######  Proof D.8 (Proof of Lemma 4.13).

If $|V(F)|\leq 2t$ then there exists an atomic graph
$\boldsymbol{F}\in\mathcal{A}_{t}$ whose underlying unlabelled graph is
isomorphic to $F$. Otherwise, by Lemma B.5, there exists a tree decomposition
$\beta\colon V(T)\to 2^{V(F)}$ of $F$ such that $|\beta(v)|=2t$ for all $v\in
V(T)$ and $|\beta(s)\cap\beta(t)|=2t-1$ for all $st\in E(T)$. It is shown by
induction on $|V(T)|$ that for every $r\in V(T)$ there exist
$\boldsymbol{u}=u_{1}\dots u_{t}\in V(F)^{t}$, $\boldsymbol{v}=v_{1}\dots
v_{t}\in V(F)^{t}$ with $\beta(r)=\\{u_{1},\dots,u_{t},v_{1},\dots,v_{t}\\}$
such that
$\boldsymbol{F}=(F,\boldsymbol{u},\boldsymbol{v})\in\mathcal{L}_{t}^{+}$.
Observe that this implies that the labels of $\boldsymbol{F}$ lie on distinct
vertices of $F$.

In the base case, when $|V(T)|=1$, the tuples $\boldsymbol{u}$ and
$\boldsymbol{v}$ can be chosen arbitrarily and $\boldsymbol{F}$ is an atomic
graph.

Let $|V(T)|\geq 2$ and $r\in V(T)$ be arbitrary. Write $s_{1},\dots,s_{\ell}$
for the neighbours of $r$ in $T$. First a bilabelled graph
$\boldsymbol{F}_{i}\in\mathcal{L}_{t}^{+}$ is constructed for each
$i\in[\ell]$. Let $T_{i}$ be the connected component of $T\setminus\\{r\\}$
containing $s_{i}$. Let $F_{i}$ be the induced subgraph of $F$ on
$\bigcup_{t\in V(T_{i})}\beta(t)$. The restriction of $\beta$ to $V(T_{i})$ is
a tree decomposition of $F_{i}$ with the properties listed in the inductive
hypothesis. Hence, there exist $\boldsymbol{u}^{i}=u^{i}_{1}\dots u^{i}_{t}\in
V(F_{i})^{t}$, $\boldsymbol{v}^{i}=v^{i}_{1}\dots v^{i}_{t}\in V(F_{i})^{t}$
with $\beta(s_{i})=\\{u^{i}_{1},\dots,u^{i}_{t},v^{i}_{1},\dots,v^{i}_{t}\\}$
such that
$\boldsymbol{F}_{i}\coloneqq(F_{i},\boldsymbol{u}^{i},\boldsymbol{v}^{i})\in\mathcal{L}_{t}^{+}$.

Figure 4: The atomic graph $\boldsymbol{K}_{j}$ as defined in Equation 26.

Let $x_{1},\dots,x_{2t}$ denote the vertices in $\beta(r)$. By permuting
labels, it can be guaranteed that for every $i\in[\ell]$, the tuples
$u^{i}_{1}\dots u^{i}_{t}v^{i}_{1}\dots v^{i}_{t}$ and $x_{1}\dots x_{2t}$
differ at precisely one index $j_{i}\in[2t]$. Recall the bilabelled graphs
defined in Definition 3.5. Define the following bilabelled graph, cf. Figure
4. For $j\in[t]$,

$\boldsymbol{K}_{j}\coloneqq\boldsymbol{I}^{1,t+1}\odot\dots\odot\boldsymbol{I}^{j-1,t+j-1}\odot\boldsymbol{I}^{j+1,t+j+1}\odot\dots\odot\boldsymbol{I}^{t,2t}.$
(26)

Let
$\boldsymbol{F}^{\prime}_{i}\coloneqq\boldsymbol{K}_{j_{i}}\cdot\boldsymbol{F}_{i}$
if $j_{i}\leq t$ and
$\boldsymbol{F}^{\prime}_{i}\coloneqq\boldsymbol{F}_{i}\cdot\boldsymbol{K}_{j_{i}-t}$
otherwise. Intuitively, the bilabelled graph $\boldsymbol{F}^{\prime}_{i}$ is
obtained from $\boldsymbol{F}_{i}$ by adding a fresh vertex and moving the
$j_{i}$-th label to this vertex. Clearly,
$\boldsymbol{F}_{i}^{\prime}\in\mathcal{L}_{t}^{+}$. Finally, let
$\boldsymbol{F}=\boldsymbol{F}^{\prime}_{1}\odot\dots\odot\boldsymbol{F}^{\prime}_{\ell}\odot\bigodot_{x_{i}x_{j}\in
E(F)}\boldsymbol{A}^{ij}$.

######  Proof D.9 (Proof of Lemma 4.12).

If $|V(F)|\leq 2t$ then there exists an atomic graph
$\boldsymbol{F}\in\mathcal{A}_{t}$ whose underlying unlabelled graph is
isomorphic to $F$. Otherwise, by Lemma B.7, there exists a path decomposition
$\beta\colon V(P)\to 2^{V(F)}$ such that $|\beta(v)|=2t$ for all $v\in V(P)$
and $|\beta(s)\cap\beta(t)|=2t-1$ for all $st\in E(P)$.

It is shown by induction on $|V(P)|$ that for every vertex $r\in V(P)$ of
degree at most one there exist $\boldsymbol{u}=u_{1}\dots u_{t}\in V(F)^{t}$,
$\boldsymbol{v}=v_{1}\dots v_{t}\in V(F)^{t}$ with
$\beta(r)=\\{u_{1},\dots,u_{t},v_{1},\dots,v_{t}\\}$ such that
$\boldsymbol{F}=(F,\boldsymbol{u},\boldsymbol{v})\in\mathcal{L}_{t}$.

The inductive argument is very similar to the one in the proof of Lemma 4.13.
Indeed, since the vertex $r$ has at most one neighbour, $\ell\leq 1$ in the
proof of Lemma 4.13 and the construction does not require arbitrary parallel
compositions.

######  Proof D.10 (Proof of Lemma 4.14).

If $|V(F)|\leq t$ then there exists an atomic graph
$\boldsymbol{F}\in\mathcal{A}_{t}$ whose underlying unlabelled graph is
isomorphic to $F$. Otherwise, by Lemma B.5, there exists a tree decomposition
$\beta\colon V(T)\to 2^{V(F)}$ of $F$ such that $|\beta(v)|=t$ for all $v\in
V(T)$ and $|\beta(s)\cap\beta(t)|=t-1$ for all $st\in E(T)$. It is shown by
induction on $|V(T)|$ that for every $r\in V(T)$ there exist
$\boldsymbol{u}=u_{1}\dots u_{t}\in V(F)^{t}$ with
$\beta(r)=\\{u_{1},\dots,u_{t}\\}$ such that
$\boldsymbol{F}=(F,\boldsymbol{u},\boldsymbol{u})\in\mathcal{L}_{t}$.

In the base case, when $|V(T)|=1$, the tuple $\boldsymbol{u}$ can be chosen
arbitrarily and $\boldsymbol{F}$ is an atomic graphs.

Let $|V(T)|\geq 2$ and $r\in V(T)$ be arbitrary. Write $s_{1},\dots,s_{\ell}$
for the neighbours of $r$ in $T$. First a graph
$\boldsymbol{F}_{i}\in\mathcal{L}_{t}$ is constructed for each $i\in[\ell]$.
Let $T_{i}$ be the connected component of $T\setminus\\{r\\}$ containing
$s_{i}$. Let $F_{i}$ be the induced subgraph of $F$ on $\bigcup_{t\in
V(T_{i})}\beta(t)$. The restriction of $\beta$ to $V(T_{i})$ is a tree
decomposition of $F_{i}$ with the properties listed in the inductive
hypothesis. Hence, there exist $\boldsymbol{u}^{i}=u^{i}_{1}\dots u^{i}_{t}\in
V(F_{i})^{t}$ with $\beta(s_{i})=\\{u^{i}_{1},\dots,u^{i}_{t}\\}$ such that
$\boldsymbol{F}_{i}\coloneqq(F_{i},\boldsymbol{u}^{i},\boldsymbol{u}^{i})\in\mathcal{L}_{t}$.

Let $x_{1},\dots,x_{t}$ denote the vertices in $\beta(r)$. By permuting
labels, it can be guaranteed that for every $i\in[\ell]$, the tuples
$u^{i}_{1}\dots u^{i}_{t}$ and $x_{1}\dots x_{t}$ differ at precisely one
index $j_{i}\in[t]$. Recall the bilabelled graphs defined in Definition 3.5
and $\boldsymbol{K}_{j}$ from Equations 26 and 4. Let
$\boldsymbol{F}_{i}^{\prime}\coloneqq\boldsymbol{I}^{j_{i},t+j_{i}}\odot(\boldsymbol{K}_{j_{i}}\cdot\boldsymbol{F}\cdot\boldsymbol{K}_{j_{i}})$.
Clearly, $\boldsymbol{F}_{i}^{\prime}\in\mathcal{L}_{t}$. The labelled
vertices of $\boldsymbol{F}_{i}$ differ from those of $\boldsymbol{F}_{i}$ in
$x_{j_{i}}$. Finally, let

$\boldsymbol{F}\coloneqq(\boldsymbol{I}^{1,t+1}\odot\dots\odot\boldsymbol{I}^{t,2t})\odot(\boldsymbol{F}_{1}^{\prime}\cdot\dots\cdot\boldsymbol{F}_{\ell}^{\prime})\odot\bigodot_{x_{i}x_{j}\in
E(F)}\boldsymbol{A}^{ij}.$

This graph is as desired.

###  D.2 Bilabelled Minors and Lemma 4.11

In order to proof Lemma 4.11, we introduce bilabelled analogues of graph
minors.

######  Definition D.11.

Let $\boldsymbol{M}$ and $\boldsymbol{F}$ be $(\ell,k)$-bilabelled graphs for
some $k,\ell\in\mathbb{N}$. Then $\boldsymbol{M}$ is a _bilabelled minor_ of
$\boldsymbol{F}$, in symbols $\boldsymbol{M}\leq\boldsymbol{F}$, if it can be
obtained from $\boldsymbol{F}$ by applying a sequence of the following
_bilabelled minor operations_ :

  1. 1.

edge contraction,

  2. 2.

edge deletion,

  3. 3.

deletion of unlabelled vertices,

A family of bilabelled graphs $\mathcal{F}$ is _minor-closed_ if it is closed
under taking bilabelled minors.

Note that for $(0,0)$-bilabelled graphs, i.e. unlabelled graphs, Definition
D.11 and the standard definition of graph minors coincide.

######  Example D.12.

Let $t\geq 1$. The class of atomic graphs $\mathcal{A}_{t}$ as defined in
Definition 3.5 is minor-closed.

######  Lemma D.13 (Minor Unlabelling Lemma).

Let $\boldsymbol{M}\leq\boldsymbol{F}$ be bilabelled. Then
$\operatorname{soe}(\boldsymbol{M})\leq\operatorname{soe}(\boldsymbol{F})$.

######  Proof D.14.

It is argued by induction on the number of bilabelled minor operations
necessary to transform $\boldsymbol{F}$ into $\boldsymbol{M}$. If
$\boldsymbol{M}=\boldsymbol{F}$ then the claim is readily verified. Suppose
that $\boldsymbol{M}\leq\boldsymbol{M}^{\prime}\leq\boldsymbol{F}$ where
$\boldsymbol{M}^{\prime}$ can be transformed into $\boldsymbol{M}$ by applying
a single minor operation and $\boldsymbol{M}^{\prime}$ is minimal among all
such graphs with respect to the number of minor operations necessary to derive
it from $\boldsymbol{F}$. By the inductive hypothesis,
$\operatorname{soe}(\boldsymbol{M}^{\prime})\leq\operatorname{soe}(\boldsymbol{F})$.
Since bilabelled minor operations are more restrictive than minor operations,
any operation of Definition D.11 carried out on $\boldsymbol{M}^{\prime}$ can
be applied to $\operatorname{soe}(\boldsymbol{M}^{\prime})$. It follows that
$\operatorname{soe}(\boldsymbol{M})\leq\operatorname{soe}(\boldsymbol{F})$.

######  Lemma D.15 (Minor Labelling Lemma).

Let $\boldsymbol{F}$ be bilabelled and $M$ be unlabelled. If
$M\leq\operatorname{soe}(\boldsymbol{F})$ then there exists
$\boldsymbol{M}\leq\boldsymbol{F}$ such that
$\operatorname{soe}(\boldsymbol{M})$ is the disjoint union of $M$ and
potential isolated vertices which are labelled in $\boldsymbol{M}$.

######  Proof D.16.

It is argued by induction on the number of minor operations needed to
transform $\operatorname{soe}(\boldsymbol{F})$ into $M$. If
$M=\operatorname{soe}(\boldsymbol{F})$, let
$\boldsymbol{M}\coloneqq\boldsymbol{F}$. Now suppose there are $M\leq
M^{\prime}\leq\operatorname{soe}(\boldsymbol{F})$ such that $M^{\prime}$ can
be transformed into $M$ by applying a single minor operation. Then there
exists $\boldsymbol{M}^{\prime}\leq\boldsymbol{F}$ such that
$\operatorname{soe}(\boldsymbol{M}^{\prime})$ is the disjoint union of
$M^{\prime}$ and potential isolated vertices. Distinguish cases:

  * •

$M$ is obtained from $M^{\prime}$ by deleting or contracting an edge $e$. Then
$e$ has a counterpart in $\boldsymbol{M}^{\prime}$ since
$\operatorname{soe}(\boldsymbol{M}^{\prime})$ contains $M^{\prime}$.
Contracting/deleting the edge there yields the desired $\boldsymbol{M}$.

  * •

$M$ is obtained from $M^{\prime}$ by deleting a vertex $v$. If $v$ is
unlabelled in $\boldsymbol{M}^{\prime}$ then it can be deleted by 3 yielding
$\boldsymbol{M}$. If $v$ is labelled in $\boldsymbol{M}^{\prime}$, remove all
edges incident to $v$ by 2 and $\boldsymbol{M}$ be the resulting graph.
Clearly, $\operatorname{soe}(\boldsymbol{M})$ is the disjoint union of $M$ and
an isolated vertex.

Intuitively, the following Lemmas D.19 and D.17 assert that minor operations
commute with bilabelled graph multiplication.

######  Lemma D.17 (Minor Parallel Composition Lemma).

Let $\boldsymbol{P}_{1}$ and $\boldsymbol{P}_{2}$ be $(k,\ell)$-bilabelled
graphs.

  1. 1.

If $\boldsymbol{M}_{1}$ is a minor of $\boldsymbol{P}_{1}$ and
$\boldsymbol{M}_{2}$ is a minor of $\boldsymbol{P}_{2}$ then
$\boldsymbol{M}_{1}\odot\boldsymbol{M}_{2}$ is a minor of
$\boldsymbol{P}_{1}\odot\boldsymbol{P}_{2}$.

  2. 2.

If $\boldsymbol{K}$ is a minor of $\boldsymbol{P}_{1}\odot\boldsymbol{P}_{2}$
then there exist $(k,\ell)$-bilabelled $\boldsymbol{M}_{1}$ and
$\boldsymbol{M}_{2}$ such that

    1. (a)

$\boldsymbol{K}=\boldsymbol{M}_{1}\odot\boldsymbol{M}_{2}$,

    2. (b)

$\boldsymbol{M}_{i}$ is a minor of $\boldsymbol{P}_{i}$ for $i\in\\{1,2\\}$.

######  Proof D.18.

For the first claim, it is argued by induction on the sum of the number of
minor operations applied to transform $\boldsymbol{P}_{1}$ into
$\boldsymbol{M}_{1}$ and $\boldsymbol{P}_{2}$ into $\boldsymbol{M}_{2}$. For
the base case, $\boldsymbol{M}_{1}=\boldsymbol{P}_{1}$ and
$\boldsymbol{M}_{2}=\boldsymbol{P}_{2}$, and the claim follows trivially.

Now suppose that $\boldsymbol{M}_{1}$ is obtained from
$\boldsymbol{M}^{\prime}_{1}$, a minor of $\boldsymbol{P}_{1}$, by applying a
single minor operation. Suppose inductively that
$\boldsymbol{M}^{\prime}_{1}\odot\boldsymbol{M}_{2}$ is a minor of
$\boldsymbol{P}_{1}\odot\boldsymbol{P}_{2}$. Distinguish cases:

  * •

$\boldsymbol{M}_{1}$ is obtained from $\boldsymbol{M}^{\prime}_{1}$ by
contracting an edge $e$. In
$\boldsymbol{M}^{\prime}_{1}\odot\boldsymbol{M}_{2}$, this edge is either a
loop or a proper edge. In the former case, it can be deleted by 2, in the
latter case, it can be contracted by 1, yielding in both cases
$\boldsymbol{M}_{1}\odot\boldsymbol{M}_{2}$.

  * •

$\boldsymbol{M}_{1}$ is obtained from $\boldsymbol{M}^{\prime}_{1}$ by
deleting an edge $e$. In $\boldsymbol{M}^{\prime}_{1}\odot\boldsymbol{M}_{2}$,
this edge is either a loop or a proper edge. In both cases, it can be deleted
by 2 yielding $\boldsymbol{M}_{1}\odot\boldsymbol{M}_{2}$.

  * •

$\boldsymbol{M}_{1}$ is obtained from $\boldsymbol{M}^{\prime}_{1}$ by
deleting an unlabelled vertex $v$. Then $v$ is unlabelled in
$\boldsymbol{M}^{\prime}_{1}\odot\boldsymbol{M}_{2}$ and can be deleted by 3.
The resulting graph is $\boldsymbol{M}_{1}\odot\boldsymbol{M}_{2}$.

For the second claim, it is argued by induction on the number of minor
operations necessary to transform $\boldsymbol{P}_{1}\odot\boldsymbol{P}_{2}$
into $\boldsymbol{K}$. For the base case, if
$\boldsymbol{K}=\boldsymbol{P}_{1}\odot\boldsymbol{P}_{2}$, let
$\boldsymbol{M}\coloneqq\boldsymbol{K}$ and let
$\boldsymbol{M}_{i}=\boldsymbol{P}_{i}$ for $i\in\\{1,2\\}$.

Now suppose that $\boldsymbol{K}$ is a minor of
$\boldsymbol{P}_{1}\odot\boldsymbol{P}_{2}$. Then there exists a
$(k,\ell)$-bilabelled graph $\boldsymbol{K}^{\prime}$ such that
$\boldsymbol{K}^{\prime}$ is a minor of
$\boldsymbol{P}_{1}\odot\boldsymbol{P}_{2}$ and $\boldsymbol{K}$ is obtained
from $\boldsymbol{K}^{\prime}$ by applying a single minor operation. By the
induction hypothesis, there exist $\boldsymbol{M}^{\prime}_{1}$, and
$\boldsymbol{M}^{\prime}_{2}$ such that the assertions of this lemma are
satisfied. Distinguish cases:

  * •

$\boldsymbol{K}$ is obtained from $\boldsymbol{K}^{\prime}$ by deleting or
contracting an edge $e$.

The edge $e$ may lie in both $\boldsymbol{M}^{\prime}_{1}$ and
$\boldsymbol{M}^{\prime}_{2}$ or only in one of the two graphs. In the first
case, both endpoints of $e$ are labelled in both graphs. In either case,
construct $\boldsymbol{M}_{1}$ and $\boldsymbol{M}_{2}$ by respectively
deleting or contracting the edge in $\boldsymbol{M}^{\prime}_{1}$ and
$\boldsymbol{M}^{\prime}_{2}$ or leaving the graph unchanged if it does not
contain the edge.

  * •

$\boldsymbol{K}$ is obtained from $\boldsymbol{K}^{\prime}$ by deleting an
unlabelled vertex $v$.

Since no vertex is unlabelled under parallel composition, the vertex $v$ is
also unlabelled in the graph $\boldsymbol{M}^{\prime}_{1}$ or
$\boldsymbol{M}^{\prime}_{2}$ which it contains. It follows that $v$ can be
deleted from $\boldsymbol{M}^{\prime}_{i}$ leaving the other graph untouched.
This yields $\boldsymbol{M}_{1}$ and $\boldsymbol{M}_{2}$.

######  Lemma D.19 (Minor Series Composition Lemma).

Let $\boldsymbol{P}_{1}$ be $(k,\ell)$-bilabelled and $\boldsymbol{P}_{2}$ be
$(\ell,j)$-bilabelled.

  1. 1.

If $\boldsymbol{M}_{1}$ is a minor of $\boldsymbol{P}_{1}$ and
$\boldsymbol{M}_{2}$ is a minor of $\boldsymbol{P}_{2}$ then
$\boldsymbol{M}_{1}\cdot\boldsymbol{M}_{2}$ is a minor of
$\boldsymbol{P}_{1}\cdot\boldsymbol{P}_{2}$.

  2. 2.

If $\boldsymbol{K}$ is a minor of $\boldsymbol{P}_{1}\cdot\boldsymbol{P}_{2}$
then there exists a $(k,j)$-bilabelled $\boldsymbol{M}$, a
$(k,\ell)$-bilabelled $\boldsymbol{M}_{1}$, and a $(\ell,j)$-bilabelled
$\boldsymbol{M}_{2}$ such that

    1. (a)

$\boldsymbol{M}$ is the disjoint union of $\boldsymbol{K}$ and potential
isolated unlabelled vertices, which are labelled in $\boldsymbol{M}_{1}$ and
$\boldsymbol{M}_{2}$,

    2. (b)

$\boldsymbol{M}=\boldsymbol{M}_{1}\cdot\boldsymbol{M}_{2}$,

    3. (c)

$\boldsymbol{M}_{i}$ is a minor of $\boldsymbol{P}_{i}$ for $i\in\\{1,2\\}$.

######  Proof D.20.

Proof of the first claim is analogous to the proof of the first claim of Lemma
D.17.

For the second claim, it is argued by induction on the number of minor
operations necessary to transform $\boldsymbol{P}_{1}\cdot\boldsymbol{P}_{2}$
into $\boldsymbol{K}$. For the base case, if
$\boldsymbol{K}=\boldsymbol{P}_{1}\cdot\boldsymbol{P}_{2}$, let
$\boldsymbol{M}\coloneqq\boldsymbol{K}$ and let
$\boldsymbol{M}_{i}=\boldsymbol{P}_{i}$ for $i\in\\{1,2\\}$.

Now suppose that $\boldsymbol{K}$ is a minor of
$\boldsymbol{P}_{1}\cdot\boldsymbol{P}_{2}$. Then there exists a
$(k,j)$-bilabelled graph $\boldsymbol{K}^{\prime}$ such that
$\boldsymbol{K}^{\prime}$ is a minor of
$\boldsymbol{P}_{1}\cdot\boldsymbol{P}_{2}$ and $\boldsymbol{K}$ is obtained
from $\boldsymbol{K}^{\prime}$ by applying a single minor operation. By the
induction hypothesis, there exist $\boldsymbol{M}^{\prime}$,
$\boldsymbol{M}^{\prime}_{1}$, and $\boldsymbol{M}^{\prime}_{2}$ such that
Items 2a, 2b and 2c are satisfied. Distinguish cases:

  * •

$\boldsymbol{K}$ is obtained from $\boldsymbol{K}^{\prime}$ by deleting or
contracting an edge $e$.

Define $\boldsymbol{M}$ by deleting/contracting the same edge in
$\boldsymbol{M}^{\prime}$. The edge $e$ may lie in both
$\boldsymbol{M}^{\prime}_{1}$ and $\boldsymbol{M}^{\prime}_{2}$ or only in one
of the two graphs. In the first case, both endpoints of $e$ are labelled in
both graphs. In either case, construct $\boldsymbol{M}_{1}$ and
$\boldsymbol{M}_{2}$ by respectively deleting or contracting the edge in
$\boldsymbol{M}^{\prime}_{1}$ and $\boldsymbol{M}^{\prime}_{2}$ or leaving the
graph unchanged if it does not contain the edge.

  * •

$\boldsymbol{K}$ is obtained from $\boldsymbol{K}^{\prime}$ by deleting an
unlabelled vertex $v$.

If $v$ is among the unlabelled vertices of $\boldsymbol{M}^{\prime}_{i}$ for
$i\in\\{1,2\\}$ then define $\boldsymbol{M}$ by deleting $v$ in
$\boldsymbol{M}^{\prime}$. It follows that $v$ can be deleted from
$\boldsymbol{M}^{\prime}_{i}$ leaving the other graph untouched. This yields
$\boldsymbol{M}_{1}$ and $\boldsymbol{M}_{2}$.

If otherwise $v$ is among the vertices at which $\boldsymbol{M}^{\prime}_{1}$
and $\boldsymbol{M}^{\prime}_{2}$ are glued together then define
$\boldsymbol{M}$ as the graph obtained from $\boldsymbol{M}^{\prime}$ by
deleting all edges incident with $v$ but keeping the vertex. By the inductive
hypothesis, $\boldsymbol{M}^{\prime}$ is the disjoint union of
$\boldsymbol{K}^{\prime}$ and isolated unlabelled vertices and via the
aforementioned construction the same holds for $\boldsymbol{M}$ and
$\boldsymbol{K}$. Note that $v$ is neither in-labelled in
$\boldsymbol{M}^{\prime}_{1}$ nor out-labelled in
$\boldsymbol{M}^{\prime}_{2}$ as it would otherwise be labelled in
$\boldsymbol{M}$. Delete all edges incident to $v$ in both
$\boldsymbol{M}^{\prime}_{1}$ and $\boldsymbol{M}^{\prime}_{2}$. The resulting
$\boldsymbol{M}_{1}$ and $\boldsymbol{M}_{2}$ satisfy
$\boldsymbol{M}=\boldsymbol{M}_{1}\cdot\boldsymbol{M}_{2}$, as desired.

####  D.2.1 Proof of Lemma 4.11

######  Proof D.21 (Proof of Lemma 4.11).

For $(t,t)$-bilabelled graphs $\boldsymbol{F}$ and $\boldsymbol{F}^{\prime}$
and $\boldsymbol{J}\in\mathcal{A}_{t}$ as defined in Definition 3.5, the graph
underlying $\boldsymbol{F}\cdot\boldsymbol{J}\cdot\boldsymbol{F}^{\prime}$ is
isomorphic to the disjoint union of the graphs underlying $\boldsymbol{F}$ and
$\boldsymbol{F}^{\prime}$. Hence, the classes of graphs underlying elements of
$\mathcal{L}_{t}$ and $\mathcal{L}_{t}^{+}$ are union-closed.

######  Claim 4.

The classes $\mathcal{L}_{t}$ and $\mathcal{L}_{t}^{+}$ are closed under
taking bilabelled minors.

The claim is proven by induction on the structure of elements
$\boldsymbol{F}\in\mathcal{L}_{t}$ that if $\boldsymbol{K}\leq\boldsymbol{F}$
then also $\boldsymbol{K}\in\mathcal{L}_{t}$. For $\mathcal{L}_{t}^{+}$, the
proof is very similar, requiring fewer case distinctions. It is therefore
omitted. If $\boldsymbol{F}$ is atomic then all its minors are atomic by
Example D.12. This constitutes the base case of the induction.

If $\boldsymbol{F}=\boldsymbol{F}_{1}\odot\boldsymbol{F}_{2}$ for
$\boldsymbol{F}_{1}\in\mathcal{A}_{t}$, $\boldsymbol{F}_{2}\in\mathcal{L}_{t}$
of lesser complexity, and $\boldsymbol{K}\leq\boldsymbol{F}$ then, by Lemma
D.17, there exist $\boldsymbol{K}_{1}\leq\boldsymbol{F}_{1}$ and
$\boldsymbol{K}_{2}\leq\boldsymbol{F}_{2}$ such that
$\boldsymbol{K}=\boldsymbol{K}_{1}\odot\boldsymbol{K}_{2}$. By Example D.12,
$\boldsymbol{K}_{1}$ is atomic and, by the inductive hypothesis,
$\boldsymbol{K}_{2}\in\mathcal{L}_{t}$. Hence,
$\boldsymbol{K}\in\mathcal{L}_{t}$.

If $\boldsymbol{F}=\boldsymbol{F}_{1}\cdot\boldsymbol{F}_{2}$ for two
$\boldsymbol{F}_{1},\boldsymbol{F}_{2}\in\mathcal{L}_{t}$ of lesser complexity
and $\boldsymbol{K}\leq\boldsymbol{F}$ then, by Lemma D.19, there exist
$\boldsymbol{M}$, $\boldsymbol{M}_{1}$, $\boldsymbol{M}_{2}$ such that
$\boldsymbol{M}_{1}\leq\boldsymbol{F}_{1}$,
$\boldsymbol{M}_{2}\leq\boldsymbol{F}_{2}$, and
$\boldsymbol{M}=\boldsymbol{M}_{1}\cdot\boldsymbol{M}_{2}$ is the disjoint
union of $\boldsymbol{K}$ and potential isolated unlabelled vertices which are
labelled both in $\boldsymbol{M}_{1}$ and $\boldsymbol{M}_{2}$. By the
inductive hypothesis,
$\boldsymbol{M}_{1},\boldsymbol{M}_{2}\in\mathcal{L}_{t}$. It remains to
remove these isolated vertices. Suppose that the $i$-th out-label of
$\boldsymbol{M}_{1}$ and the $i$-th in-label of $\boldsymbol{M}_{2}$ are
carried by an isolated vertex. Then graph
$(\boldsymbol{I}^{1,t+1+i}\odot\boldsymbol{M}_{1})\cdot\boldsymbol{M}_{2}$
does not contain this isolated vertex since taking the parallel composition
with $\boldsymbol{I}^{1,t+1+i}$ as defined in Definition 3.5 amounts to gluing
it to the first in-labelled vertex of $\boldsymbol{M}_{1}$. Observe that
$\boldsymbol{I}^{1,t+1+i}\odot\boldsymbol{M}_{1}\in\mathcal{L}_{t}$.
Proceeding in this fashion, one can construct
$\boldsymbol{K}_{1},\boldsymbol{K}_{2}\in\mathcal{L}_{t}$ such that
$\boldsymbol{K}=\boldsymbol{K}_{1}\cdot\boldsymbol{K}_{2}\in\mathcal{L}_{t}$,
as desired.

If $\boldsymbol{F}=\boldsymbol{F}_{1}^{\sigma}$ for
$\sigma\in\mathfrak{S}_{2t}$ and $\boldsymbol{F}_{1}\in\mathcal{L}_{t}$ of
lesser complexity and $\boldsymbol{K}\leq\boldsymbol{F}$ then
$\boldsymbol{K}^{\sigma^{-1}}\leq\boldsymbol{F}_{1}$ and
$\boldsymbol{K}^{\sigma^{-1}}\in\mathcal{L}_{t}$ by the inductive hypothesis.
Hence, $\boldsymbol{K}\in\mathcal{L}_{t}$, as desired.

Given 4, it remains to observe that the classes of unlabelled graphs
underlying the elements of $\mathcal{L}_{t}$ and $\mathcal{L}_{t}^{+}$ are
minor closed. By Lemma D.15, if an unlabelled graph $M$ is a minor of
$\operatorname{soe}(\boldsymbol{F})$ for some
$\boldsymbol{F}\in\mathcal{L}_{t}$ then there exists
$\boldsymbol{M}\leq\boldsymbol{F}$ such that
$\operatorname{soe}(\boldsymbol{M})$ is the disjoint union of $M$ and
potential isolated vertices which are labelled in $\boldsymbol{M}$. By 4,
$\boldsymbol{M}\in\mathcal{L}_{t}$. As in the proof of 4, the potential
isolated vertices can be identified with other labelled in $\boldsymbol{M}$ by
taking the parallel composition of this graph with atomic graphs. Hence, it
may be assumed that $M=\operatorname{soe}(\boldsymbol{M})$. This yields the
claim.

###  D.3 Material Omitted in Section 4.2

######  Proof D.22 (Proof of Proposition 4.15).

Given Lemmas 4.8 and 4.13, it suffices to show that if a graph $F$ is such
that $\operatorname{tw}F=2$ then there is a graph
$\boldsymbol{F}\in\mathcal{L}_{1}^{+}$ whose underlying unlabelled graph is
isomorphic to $F$.

By Lemma B.5, there exists a tree decomposition $\beta\colon V(T)\to 2^{V(F)}$
of $F$ such that $|\beta(v)|=3$ for all $v\in V(T)$ and
$|\beta(s)\cap\beta(t)|=2$ for all $st\in E(T)$. It is shown by induction on
$|V(T)|$ that for every $r\in V(T)$ and $x\neq y\in\beta(r)$ the graph
$\boldsymbol{F}=(F,x,y)$ is in $\mathcal{L}_{1}^{+}$.

If $|V(T)|=1$ write $\\{x,y,z\\}$ for the unique bag. Since $F$ has treewidth
$2$, it is isomorphic to the $3$-clique which is the underlying graph of
$\boldsymbol{A}^{12}\odot(\boldsymbol{A}^{12}\cdot\boldsymbol{A}^{12})$ which
clearly is contained in $\mathcal{L}_{1}^{+}$.

Let $|V(T)|\geq 2$ and $r\in V(T)$ be arbitrary. Write
$\beta(r)=\\{x_{1},x_{2},x_{3}\\}$. Partition the neighbours of $r$ in $T$ in
three sets $X_{1},X_{2},X_{3}$ such that $s\in X_{i}$ iff
$x_{i}\in\beta(r)\setminus\beta(s)$ for $i\in[3]$.

For every neighbour $s$ of $r$, let $T_{s}$ be the connected component of
$T\setminus\\{r\\}$ containing $s$. Let $F_{s}$ be the induced subgraph of $F$
on $\bigcup_{t\in V(T_{s})}\beta(t)$. The restriction of $\beta$ to $V(T_{s})$
is a tree decomposition of $F_{s}$ with the properties listed in the inductive
hypothesis. Hence, for every $s$, there exists
$\boldsymbol{F}_{s}\in\mathcal{L}_{1}^{+}$ as stipulated. By permuting labels,
it may be supposed that for every $s\in X_{1}$ the labels of
$\boldsymbol{F}_{s}$ lie on $x_{2}x_{3}$, for $\boldsymbol{F}_{s}$ with $s\in
X_{2}$ on $x_{1}x_{3}$, and for $\boldsymbol{F}_{s}$ with $s\in X_{3}$ on
$x_{1}x_{2}$. For $i\in[3]$, let

$\boldsymbol{F}_{i}\coloneqq\begin{cases}\bigodot_{s\in
X_{i}}\boldsymbol{F}_{s},&\text{if }X_{i}\neq\emptyset,\\\
\boldsymbol{A}^{12},&\text{if }X_{i}=\emptyset\text{ and the vertices in
}\beta(r)\setminus\\{x_{i}\\}\text{ are adjacent},\\\
\boldsymbol{J},&\text{otherwise.}\end{cases}$

Finally, let
$\boldsymbol{F}\coloneqq\boldsymbol{F}_{2}\odot(\boldsymbol{F}_{3}\cdot\boldsymbol{F}_{1})$.
This graph is as desired if $x_{1},x_{3}$ are required to be labelled. For
other choices of labels,
$\boldsymbol{F}_{1},\boldsymbol{F}_{2},\boldsymbol{F}_{3}$ can be permuted and
if necessary transposed yielding any desired labelling.

######  Proof D.23 (Proof of Corollary 4.17).

Let $\boldsymbol{D}=(D,v,v)$ be the $(1,1)$-bilabelled graph with
$V(D)=\\{u,v\\}$ and $E(D)=\\{uv\\}$ and write $\boldsymbol{A}$ as before for
the $(1,1)$-bilabelled graph corresponding to the adjacency matrix. For every
graph $G$, the homomorphism matrix $\boldsymbol{D}_{G}-\boldsymbol{A}_{G}$
equals its Laplacian matrix. By [37], if two graphs $G$ and $H$ have
cospectral Laplacians then they have the same number of connected components.
The former condition holds iff
$\operatorname{tr}\left((\boldsymbol{D}_{G}-\boldsymbol{A}_{G})^{i}\right)=\operatorname{tr}\left((\boldsymbol{D}_{H}-\boldsymbol{A}_{H})^{i}\right)$
for all $i\in\mathbb{N}$ by Newton’s identities [12]. The bilabelled graphs
appearing as summands in the expression
$\operatorname{tr}\left((\boldsymbol{D}-\boldsymbol{A})^{i}\right)$ are cactus
graphs and hence outerplanar. By Proposition 4.16, if
$G\equiv_{\mathcal{L}_{1}}H$ then $G$ and $H$ have cospectral Laplacians and
hence the same number of connected components.

####  D.3.1 Proof of Proposition 4.16

######  Definition D.24.

The _expansion_ of a $(1,1)$-bilabelled graphs $\boldsymbol{F}=(F,u,v)$ is the
graph $F^{\prime}$ obtained from $F$ by adding a path of length two between
$u$ and $v$, i.e. $V(F^{\prime})\coloneqq V(F)\sqcup\\{x\\}$ and
$E(F^{\prime})\coloneqq E(F)\sqcup\\{ux,xv\\}$. Write $\mathcal{OP}$ for the
class of $(1,1)$-bilabelled graphs $\boldsymbol{F}$ whose expansion is
outerplanar.

Note that the above definition implies that for all
$\boldsymbol{F}=(F,u,v)\in\mathcal{OP}$ the underlying unlabelled graph $F$ is
outerplanar as it is a minor of the expansion of $\boldsymbol{F}$. If the two
labels of $\boldsymbol{F}$ coincide then its expansion is obtained by adding a
dangling edge and outerplanar iff the underlying unlabelled graph of
$\boldsymbol{F}$ is outerplanar.

Write $\boldsymbol{A}$ and $\boldsymbol{I}$ for the $(1,1)$-bilabelled graphs
corresponding to the adjacency matrix and the identity matrix respectively. In
the notation of Definition 3.5, $\boldsymbol{A}=\boldsymbol{A}^{12}$ and
$\boldsymbol{I}=\boldsymbol{I}^{12}$. These graphs are depicted in Figure 3.

######  Lemma D.25.

The class $\mathcal{OP}$ possesses the following closure properties:

  1. 1.

If $\boldsymbol{F}\in\mathcal{OP}$ then $\boldsymbol{F}^{*}\in\mathcal{OP}$.

  2. 2.

If $\boldsymbol{F}\in\mathcal{OP}$ then
$\boldsymbol{A}\odot\boldsymbol{F}\in\mathcal{OP}$ and
$\boldsymbol{I}\odot\boldsymbol{F}\in\mathcal{OP}$.

  3. 3.

If $\boldsymbol{F}_{1},\boldsymbol{F}_{2}\in\mathcal{OP}$ then
$\boldsymbol{F}_{1}\cdot\boldsymbol{F}_{2}\in\mathcal{OP}$.

######  Proof D.26.

The first claim is purely syntactical readily verified.

For the second claim, first consider the case when the labels of
$\boldsymbol{F}$ coincide. Then
$\boldsymbol{I}\odot\boldsymbol{F}=\boldsymbol{I}$ and
$\boldsymbol{A}\odot\boldsymbol{F}$ differs from $\boldsymbol{F}$ only in the
loop at the labelled vertex. Clearly, $\boldsymbol{A}\odot\boldsymbol{F}$ is
in $\mathcal{OP}$. Now consider the case when the labelled vertices of
$\boldsymbol{F}$ are distinct. Write $F$ for the unlabelled graph underlying
$\boldsymbol{F}$ and $F^{\prime}$ for the expansion of $\boldsymbol{F}$. It
can be easily seen that the graphs underlying
$\boldsymbol{A}\odot\boldsymbol{F}$ and $\boldsymbol{I}\odot\boldsymbol{F}$
are minors of $F^{\prime}$ and thus outerplanar. The expansion of
$\boldsymbol{I}\odot\boldsymbol{F}$ is a minor of the expansion of
$\boldsymbol{A}\odot\boldsymbol{F}$. Thus, it suffices to argue that the
expansion of $\boldsymbol{A}\odot\boldsymbol{F}$ is outerplanar.

Write $K$ for the unlabelled graph underlying
$\boldsymbol{A}\odot\boldsymbol{F}$ and $K^{\prime}$ for the expansion of
$\boldsymbol{A}\odot\boldsymbol{F}$. Since $K$ and $F^{\prime}$ are
outerplanar, any $K_{4}$-minor of $K^{\prime}$ can be obtained from
$K^{\prime}$ without contracting the triangle induced by the labelled vertices
of $\boldsymbol{A}\odot\boldsymbol{F}$ and the vertex added by expansion. This
cannot be since the latter vertex is of degree two. By the same argument,
since $K_{2,3}$ is triangle-free, the graph $K^{\prime}$ does not contain any
$K_{2,3}$-minor either.

For the third claim, let $F$ denote the graph underlying
$\boldsymbol{F}_{1}\cdot\boldsymbol{F}_{2}$. Let $y$ denote the vertex at
which $\boldsymbol{F}_{1}$ and $\boldsymbol{F}_{2}$ are glued together and
write $x,z$ for the vertices labelled in
$\boldsymbol{F}_{1}\cdot\boldsymbol{F}_{2}$. The graph $F-y$ is disconnected.
Hence, if $K_{4}$ or $K_{2,3}$ is a minor of $F$ then $\boldsymbol{F}_{1}$ or
$\boldsymbol{F}_{2}$ are not outerplanar. Hence, $F$ is outerplanar.

(a) The graph $\boldsymbol{P}=\boldsymbol{A}\cdot\boldsymbol{A}$.

(b) The graph $\boldsymbol{C}$.

Figure 5: Bilabelled graphs from the proof of Lemma D.25.

Write $F^{\prime}$ for the expansion of
$\boldsymbol{F}\coloneqq\boldsymbol{F}_{1}\cdot\boldsymbol{F}_{2}$. In
symbols, $F^{\prime}=\operatorname{soe}(\boldsymbol{P}\odot\boldsymbol{F})$
where $\boldsymbol{P}$ is the bilabelled graph in Figure 5(a). For
$K\in\\{K_{4},K_{2,3}\\}$, observe the following: If $F^{\prime}$ contains $K$
as a minor then, by Lemma D.15, there exists a bilabelled minor
$\boldsymbol{K}\leq\boldsymbol{P}\odot\boldsymbol{F}$ such that
$\operatorname{soe}(\boldsymbol{K})$ is the disjoint union of $K$ and
potential isolated vertices which are labelled in $\boldsymbol{K}$. By Lemma
D.17, $\boldsymbol{K}$ can be written as
$\boldsymbol{K}=\boldsymbol{K}_{1}\odot\boldsymbol{K}_{2}$ such that
$\boldsymbol{K}_{1}\leq\boldsymbol{P}$ and
$\boldsymbol{K}_{2}\leq\boldsymbol{F}$. The graph $\boldsymbol{P}$ has six
bilabelled minors. Distinguish cases:

  1. 1.

If $\boldsymbol{K}_{1}=\boldsymbol{P}$ then the labels of $\boldsymbol{K}_{2}$
must lie on distinct vertices because $\boldsymbol{K}$ does not contain any