# On a Hierarchy of Spectral Isomorphism Invariants

V. Arvind, Frank Fuhlbrück, Johannes Köbler†, Oleg Verbitsky† The Institute of
Mathematical Sciences (HBNI), Chennai, India.Institut für Informatik,
Humboldt-Universität zu Berlin, Germany.Supported by DFG grant KO 1053/8–2. On
leave from the IAPMM, Lviv, Ukraine.

###### Abstract

We consider a hierarchy of graph invariants that naturally extends the
spectral invariants defined by Fürer (Lin. Alg. Appl. 2010) based on angles
between the projections of standard basis vectors onto an eigenspace of the
adjacency matrix of a graph. We provide a purely combinatorial
characterization of this hierarchy in terms of the walk counts. This allows us
to give a complete answer to Fürer’s question about the strength of his
invariants in distinguishing non-isomorphic graphs in comparison to the
2-dimensional Weisfeiler-Leman algorithm, extending the recent work of Rattan
and Seppelt (SODA 2023). As another application of the characterization, we
prove that almost all graphs are determined up to isomorphism by their
eigenvalues and angles, which is closely related to the long-standing open
problem whether almost all graphs are determined by their spectrum. Finally,
we describe the exact relationship between the hierarchy and the Weisfeiler-
Leman algorithms for small dimensions, as also some other important spectral
characteristics of a graph such as the generalized and the main spectra.

##  1 Introduction

The spectrum of a graph is a remarkable graph invariant that has found
numerous applications in computer science; e.g., [17, 21]. These applications
are based on analyzing relevant information in the eigenvalues of a given
graph. In a sense the maximum information possible, of direct relevance to the
graph isomorphism problem, is obtained for graphs that are determined by their
spectra up to isomorphism. This graph class is often abbreviated as DS. Thus,
a graph $G$ is DS if every graph cospectral to $G$, i.e., with the same
spectrum as $G$, is actually isomorphic to $G$. Though the problem of
characterizing DS graphs has been intensively studied since the beginning of
spectral graph theory (see [10] and references therein), we are still far from
a satisfactory solution. In particular, a long-standing open question [16, 31]
is whether or not almost all graphs are DS.

Somewhat surprisingly, at first sight, the area is connected to a purely
combinatorial approach to the graph isomorphism problem. In their seminal
work, Weisfeiler and Leman [33] proposed and studied a method for
distinguishing a graph $G$ from another non-isomorphic graph by computing a
sequence of canonical partitions of $V(G)^{2}$ into color classes. The final
partition of $V(G)^{2}$ results in a _coherent configuration_ , a concept
studied in algebraic combinatorics and which plays an imporant role in
isomorphism testing [2]; see also [7]. This method [33] is now called the
2-dimensional Weisfeiler-Leman algorithm (2-WL). A similar approach based on
partitioning $V(G)$ is known as _color refinement_ and is often called 1-WL.
Even this one-dimensional method is quite powerful as it suffices for
identification of almost all graphs [3]. On the other hand, construction of
graphs not identifiable by 2-WL is rather tricky. Particular examples are
based on rare combinatorial objects. General constructions, like the far-
reaching one in [6], give rather sporadic families of “hard” graphs. It turns
out (see, e.g., [4, 14]) that if two graphs are indistinguishable by 2-WL,
then they are cospectral. As a consequence, graphs not identifiable by 2-WL
are examples of non-DS graphs.

Our overall goal in this paper is a systematic exploration of connections
between spectral and combinatorial approaches to finding graph invariants. A
_graph invariant_ $\mathcal{I}$ is a function of a graph such that
$\mathcal{I}(G)=\mathcal{I}(H)$ whenever $G\cong H$. An invariant
$\mathcal{I}$ is _stronger_ than invariant $\mathcal{I}^{\prime}$ if
$\mathcal{I}(G)$ determines $\mathcal{I}^{\prime}(G)$. That is,
$\mathcal{I}(G)=\mathcal{I}(H)$ implies
$\mathcal{I}^{\prime}(G)=\mathcal{I}^{\prime}(H)$. Equivalently, we sometimes
say that $\mathcal{I}^{\prime}$ is _weaker_ than $\mathcal{I}$ and write
$\mathcal{I}^{\prime}\preceq\mathcal{I}$. A stronger invariant can be more
effective in distinguishing non-isomorphic graphs: If
$\mathcal{I}^{\prime}\preceq\mathcal{I}$ and $\mathcal{I}^{\prime}$ can
distinguish non-isomorphic graphs $G$ and $H$, i.e.,
$\mathcal{I}^{\prime}(G)\neq\mathcal{I}^{\prime}(H)$, then these graphs are
distinguishable by $\mathcal{I}$ as well.

Let $\operatorname{\mathsf{Spec}}(G)$ denote the spectrum of a graph $G$, and
$\mathsf{WL}_{2}(G)$ denote the output of 2-WL on $G$ (formal definition in
Section 2.2). The discussion above shows that
$\operatorname{\mathsf{Spec}}\preceq\mathsf{WL}_{2}$. This can be seen as
evidence of limitations of $\operatorname{\mathsf{Spec}}$, as well as evidence
of the power of $\mathsf{WL}_{2}$.

A reasonable question is what can be achieved if
$\operatorname{\mathsf{Spec}}(G)$ is enhanced by other spectral
characteristics of the adjacency matrix of $G$. One such line of research in
spectral graph theory considers $\operatorname{\mathsf{Spec}}(G)$ augmented
with the multiset of all angles between the standard basis vectors and the
eigenspaces of $G$. The parameters and properties of a graph $G$ which are
determined by its _e_ igenvalues and _a_ ngles are called _EA-reconstructible_
and are thoroughly studied by Cvetković and co-authors; see [11, Ch. 4] and
[10, Ch. 3].

A further natural step is to include the multisets of angles between the
projections of the standard basis vectors onto eigenspaces. Fürer [14] uses
this additional data to define two new graph invariants, namely, the _weak_
and _strong spectral invariants_. We denote these spectral invariants by
$\operatorname{\mathsf{weak-FSI}}$ and $\operatorname{\mathsf{strong-FSI}}$
respectively; formal definitions are in Section 3. Fürer shows that both
$\operatorname{\mathsf{weak-FSI}}$ and $\operatorname{\mathsf{strong-FSI}}$
remain weaker than $\mathsf{WL}_{2}$. That is,

$\operatorname{\mathsf{weak-FSI}}\preceq\operatorname{\mathsf{strong-
FSI}}\preceq\mathsf{WL}_{2}$ (1)

(note that $\operatorname{\mathsf{Spec}}\preceq\operatorname{\mathsf{weak-
FSI}}$ by definition). An open problem posed in [14] it to determine which of
the relations in (1) are strict. Rattan and Seppelt, in their recent paper
[25], show that this small hierarchy does not entirely collapse by separating
$\operatorname{\mathsf{weak-FSI}}$ and $\mathsf{WL}_{2}$. Hence, at least one
of the two relations in (1) is strict. Fürer [14] conjectures that the first
relation in (1) is strict and does not exclude that the last two invariants in
(1) are equivalent, and our aim is to give precise answers to these questions.

In [25] the invariants $\operatorname{\mathsf{weak-FSI}}$ and
$\mathsf{WL}_{2}$ are separated by introducing a new natural graph invariant
$\mathsf{WL}_{3/2}$, whose strength lies between $\mathsf{WL}_{1}$ and
$\mathsf{WL}_{2}$. The authors give an elegant algebraic characterization of
$\mathsf{WL}_{3/2}$ using which they show that $\operatorname{\mathsf{weak-
FSI}}\preceq\mathsf{WL}_{3/2}$. The final step in their analysis is an example
of graph pair that separates $\mathsf{WL}_{3/2}$ and $\mathsf{WL}_{2}$.

Our approach is different. First, we observe that the invariants
$\operatorname{\mathsf{weak-FSI}}$ and $\operatorname{\mathsf{strong-FSI}}$
are part of a broader scheme, presented in Section 2.1, that leads to a
potentially infinite hierarchy of graph invariants. We define the
corresponding spectral hierarchy containing $\operatorname{\mathsf{weak-FSI}}$
and $\operatorname{\mathsf{strong-FSI}}$ on its lower levels in Section 3.
Another level is taken by the invariant $\operatorname{\mathsf{EA}}$ based on
eigenvalues and angles. In Section 4 we characterize this hierarchy in terms
of walk counts. A connection between spectral parameters and walk counts is
actually well known (see an overview in Subsection 4.1). With a little extra
effort we are able to show that this connection is tight; see Theorem 4. This
yields a purely combinatorial characterization of the invariants
$\operatorname{\mathsf{EA}}$, $\operatorname{\mathsf{weak-FSI}}$, and
$\operatorname{\mathsf{strong-FSI}}$ (Corollary 5), which also reveals some
new relations. For example, we notice that $\operatorname{\mathsf{weak-FSI}}$
determines the _generalized spectrum_ of a graph (Theorem 14).

As another application of our combinatorial characterization, we prove that
almost all graphs are determined up to isomorphism by their eigenvalues and
angles (i.e., by $\operatorname{\mathsf{EA}}$). We find this interesting in
the context of the open problem mentioned above: whether or not almost all
graphs are DS.

We present the relations between the spectral and combinatorial invariants
under consideration in Section 5; see the diagram in Fig. 1. In Section 6 we
prove that this diagram is complete, that is, it shows all existent relations,
and all the relations are strict (perhaps up to higher levels of the hierarchy
whose separation remains open). In particular, both relations in (1) are
strict, which gives a complete answer to Fürer’s questions. Another noteworthy
separation is $\operatorname{\mathsf{strong-FSI}}\npreceq\mathsf{WL}_{3/2}$
(Theorem 16). Curiously, the separating pair of graphs is the same that was
used in [25], which yields more information now because we also use our
characterization in Theorem 4.

The more involved separations are shown in Theorems 17, 20, and 22. The
corresponding separating examples are not ad hoc. They are obtained by a quite
general construction (Lemma 18). The construction is based on a considerable
extension of the approach taken in [32] to separate various concepts related
to 1-WL and the walk matrix a graph (an important notion discussed in Section
4.2). Implementation of the construction requires vertex-colored strongly
regular graphs with certain properties. The required colorings were found by a
computer assisted search among members of the family of strongly regular
graphs on 25 vertices.

##  2 Preliminaries

###  2.1 From isomorphism-invariant colorings to isomorphism invariants

Let $\mathcal{C}$ be a set of colors and $\chi:V(G)^{2}\rightarrow\mathcal{C}$
be a coloring of vertex pairs in a graph $G$. It is natural to see $\chi(x,x)$
as the color of a vertex $x$. We suppose that $\chi=\chi_{G}$ is defined for
every graph $G$. That is, speaking of a coloring $\chi$, we actually mean a
map $G\mapsto\chi_{G}$. Such a coloring $\chi$ is _isomorphism invariant_ if
for every isomophism $f$ from a graph $G$ to a graph $H$ (the equality $G=H$
is not excluded) we have $\chi_{G}(x,y)=\chi_{H}(f(x),f(y))$ for all vertices
$x$ and $y$ in $G$.

The simplest isomorphism-invariant colorings are the adjacency relation $A$
and the identity relation $I$. That is, $A(x,y)=1$ if $x$ and $y$ are adjacent
and $A(x,y)=0$ otherwise. For the identity relation, $I(x,y)=1$ if $x=y$ and
$I(x,y)=0$ if $x\neq y$. Below, we will consider $A$ and $I$ also as the
adjacency and the identity matrices. Other examples of isomorphism-invariant
colorings are the distance $d(x,y)$ between two vertices $x$ and $y$ and the
number of all such triangles in the graph that contain the vertices $x$ and
$y$. One can consider also more complex definitions like the triple
$\chi(x,y)=(\deg x,d(x,y),\deg y)$, where $\deg x$ denotes the degree of $x$.

Given an isomorphism-invariant coloring $\chi$, we can build on it to define
various graph invariants. The simplest such examples are

$\displaystyle\mathcal{I}_{1}(G)$ $\displaystyle=$
$\displaystyle\left\\{\\!\\!\left\\{\chi(x,y)\right\\}\\!\\!\right\\}_{x,y\in
V(G)},$ $\displaystyle\mathcal{I}_{2}(G)$ $\displaystyle=$
$\displaystyle\left(\left\\{\\!\\!\left\\{\chi(x,x)\right\\}\\!\\!\right\\}_{x\in
V(G)},\left\\{\\!\\!\left\\{\chi(x,y)\right\\}\\!\\!\right\\}_{x,y\in
V(G)}\right),$ $\displaystyle\mathcal{I}_{3}(G)$ $\displaystyle=$
$\displaystyle\left\\{\\!\\!\left\\{(\chi(x,x),\chi(x,y),\chi(y,y))\right\\}\\!\\!\right\\}_{x,y\in
V(G)},$ $\displaystyle\mathcal{I}_{4}(G)$ $\displaystyle=$
$\displaystyle\left\\{\\!\\!\left\\{\left(\chi(x,x),\left\\{\\!\\!\left\\{(\chi(x,y),\chi(y,y))\right\\}\\!\\!\right\\}_{y\in
V(G)}\right)\right\\}\\!\\!\right\\}_{x\in V(G)},$

where $\left\\{\\!\\!\left\\{\ldots\right\\}\\!\\!\right\\}$ denotes a
multiset. Note that
$\mathcal{I}_{1}(G)\preceq\mathcal{I}_{2}(G)\preceq\mathcal{I}_{3}(G)\preceq\mathcal{I}_{4}(G)$.

Given an isomorphism-invariant coloring $\chi$, we can define a hierarchy of
ever more complex graph invariants. We first inductively define a sequence of
colorings $\chi_{0},\chi_{1},\chi_{2},\ldots$ of single vertices by

$\chi_{0}(x)=\chi(x,x)\text{ and
}\chi_{r+1}(x)=\left(\chi_{r}(x),\left\\{\\!\\!\left\\{(\chi(x,y),\chi_{r}(y))\right\\}\\!\\!\right\\}_{y\in
V(G)}\right).$ (2)

This definition is a natural extension of the well-know concept of _color
refinement (CR)_ to edge- and vertex-colored graphs. In broad outline, CR
computes an isomorphism-invariant color of each vertex in an input graph and
recognizes two graphs as non-isomorphic if one of the colors occurs in one
graph more frequently than in the other. In the case of an uncolored
undirected graph $G$, CR starts with a uniform coloring $\chi_{0}$ of $V(G)$,
that is, $\chi_{0}(x)=\chi_{0}(x^{\prime})$ for all $x,x^{\prime}\in V(G)$. In
the $(r+1)$-th round, the preceding coloring $\chi_{r}$ is refined to a new
coloring $\chi_{r+1}$. For each vertex $x$, its new color $\chi_{r+1}(x)$
consists of $\chi_{r}(x)$ and the multiset
$\left\\{\\!\\!\left\\{\chi_{r}(y)\right\\}\\!\\!\right\\}_{y\in N(x)}$ of all
colors occurring in the neighborhood $N(x)$ of $x$. In other words, CR counts
how frequently each $\chi_{r}$-color occurrs among the vertices adjacent to
$x$ (or, equivalently, among the vertices non-adjacent to $x$). In an edge-
and vertex-colored graph $G$, each vertex paar $(x,y)$ is assigned a color,
which we denote by $\chi(x,y)$. This is a generalization of uncolored graphs
where $\chi(x,y)=1$ if $x$ and $y$ are adjacent and $\chi(x,y)=0$ otherwise.
The edge colors must be taken into account while computing $\chi_{r+1}(x)$. In
the colored case, CR first splits all vertices $y$ into classes depending on
$\chi(x,y)$ and then computes the frequencies of $\chi_{r}(y)$ within each
class. This is exactly what (2) does.

Note that

$\chi_{1}(x)=\left(\chi(x,x),\left\\{\\!\\!\left\\{(\chi(x,y),\chi(y,y))\right\\}\\!\\!\right\\}_{y\in
V(G)}\right).$ (3)

In addition, we set

$\chi_{1/2}(x)=\left(\chi(x,x),\left\\{\\!\\!\left\\{\chi(x,y)\right\\}\\!\\!\right\\}_{y\in
V(G)}\right)$ (4)

Now, we define

$\chi^{(r)}(G)=\left\\{\\!\\!\left\\{\chi_{r}(x)\right\\}\\!\\!\right\\}_{x\in
V(G)}.$ (5)

For each $r$, the coloring $\chi_{r}$ is isomorphism invariant in the sense
that $\chi_{r}(f(x))=\chi_{r}(x)$ for any isomorphism of graphs $f$. This
readily implies that $\chi^{(r)}$ is a graph invariant. As easily seen,
$\chi^{(r)}\preceq\chi^{(s)}$ if $r\leq s$.

###  2.2 First two dimensions of combinatorial refinement

We now give a formal description of the isomorphism tests 1-WL and 2-WL
already introduced in Section 1. Note that 1-WL is an alternative name for CR.
In what follows we will apply the 1-WL procedure to _vertex-colored_ graphs.
Given a vertex-colored graph $G$, we consider a coloring $\chi$ of $V(G)^{2}$
defined by $\chi(x,y)=A(x,y)$, i.e., according to the adjacency relation, for
$x\neq y$ and by setting $\chi(x,x)$ to be the color of a vertex $x$. On an
input $G$, 1-WL iteratively computes the vertex colorings $\chi_{r}$ according
to (2). After performing $n$ iterations, where $n$ is the number of vertices
in $G$, 1-WL outputs $\mathsf{WL}_{1}(G)=\chi^{(n)}(G)$ as defined by (5). Two
graphs $G$ and $H$ are recognized as non-isomorphic if
$\mathsf{WL}_{1}(G)\neq\mathsf{WL}_{1}(H)$.

2-WL exploits a similar approach but computes colorings of vertex pairs. If an
input graph $G$ is uncolored, then 2-WL begins with an initial coloring
$\chi_{0}$ of $V(G)^{2}$ defined by $\chi_{0}(x,y)=A(x,y)$ if $x\neq y$ and by
$\chi_{0}(x,x)=2$ for every vertex $x$ of $G$. If $G$ is a vertex-colored
graph, then $\chi_{0}(x,y)$ must include the colors of $x$ and $y$.
Furthermore,

$\chi_{r+1}(x,y)=\left(\chi_{r}(x,y),\,\,\left\\{\\!\\!\left\\{(\chi_{r}(x,z),\,\chi_{r}(z,y))\right\\}\\!\\!\right\\}_{z\in
V(G)}\right).$

Thus, the new color of a pair $(x,y)$ can be seen as a kind of“superposition”
of the old color pairs observable along all extensions of $(x,y)$ to a
triangle $xzy$. Finally, 2-WL outputs the multiset
$\mathsf{WL}_{2}(G)=\left\\{\\!\\!\left\\{\chi_{n^{2}}(x,y)\right\\}\\!\\!\right\\}_{x,y\in
V(G)}$

##  3 A hierarchy of spectral invariants

Speaking of an $n$-vertex graph $G$, we will assume that
$V(G)=\\{1,2,\ldots,n\\}$. Let

$\mu_{1}<\mu_{2}<\ldots<\mu_{m}$ (6)

be all pairwise distinct eigenvalues of the adjacency matrix $A$ of $G$. Let
$\operatorname{\mathsf{Spec}}(G)$ denote the spectrum of $G$, i.e., the
multiset of all eigenvalues where each $\mu_{i}$ occurs with its multiplicity.
As mentioned before, $\operatorname{\mathsf{Spec}}(G)$ is a well-studied graph
invariant with numerous applications in computer science.

Let $E_{i}$ be the eigenspace of $\mu_{i}$. Recall that $E_{i}$ consists of
all eigenvectors of $\mu_{i}$, i.e.,
$E_{i}=\\{v\in\mathbb{R}^{n}\,:\,\begin{array}[]{@{}l@{}}Av=\mu_{i}v\end{array}\\}$.
Let $P_{i}$ be the matrix of the orthogonal projection of $\mathbb{R}^{n}$
onto $E_{i}$. Note that $P_{i}^{2}=P_{i}=P_{i}^{\top}$. For $1\leq x,y\leq n$,
the matrix entry $P_{i}(x,y)$ can be seen a color of the vertex pair $(x,y)$.
This coloring is isomorphism invariant.

Throughout the paper, we use the following notational convention for compact
representations of sequences.

######  Notation 1.

For an indexed set $\left\\{a_{i}\right\\}$ with index $i$ ranging through the
interval of integers $s,s+1,\ldots,t-1,t$ we set $a_{*}=(a_{s},\ldots,a_{t})$.

In particular,

$P_{*}(x,y)=\left(P_{1}(x,y),\ldots,P_{m}(x,y)\right).$

Since the order on the index set is determined by (6), $P_{*}$ is also an
isomorphism-invariant coloring. As given by the general framework of Section
2.1, the coloring $P_{*}$ determines the sequence of graph invariants
$P_{*}^{(0)},P_{*}^{(1/2)},P_{*}^{(1)},P_{*}^{(2)},\ldots$. In particular, by
(3)–(4) we have

$\displaystyle P_{*}^{(0)}(G)$ $\displaystyle=$
$\displaystyle\left\\{\\!\\!\left\\{\ P_{*}(x,x)\
\right\\}\\!\\!\right\\}_{1\leq x\leq n},$ (7) $\displaystyle
P_{*}^{(1/2)}(G)$ $\displaystyle=$ $\displaystyle\left\\{\\!\\!\left\\{\
\left(\ P_{*}(x,x),\
\left\\{\\!\\!\left\\{P_{*}(x,y)\right\\}\\!\\!\right\\}_{1\leq y\leq n}\
\right)\ \right\\}\\!\\!\right\\}_{1\leq x\leq n},$ $\displaystyle
P_{*}^{(1)}(G)$ $\displaystyle=$ $\displaystyle\left\\{\\!\\!\left\\{\ \left(\
P_{*}(x,x),\
\left\\{\\!\\!\left\\{\left(P_{*}(x,y),P_{*}(y,y)\right)\right\\}\\!\\!\right\\}_{1\leq
y\leq n}\ \right)\ \right\\}\\!\\!\right\\}_{1\leq x\leq n}.$

Fürer [14] introduces the _weak_ and _strong spectral invariants_. Using our
notation, Fürer’s spectral invariants (FSI) can be defined as follows:

$\displaystyle\operatorname{\mathsf{weak-FSI}}(G)$ $\displaystyle=$
$\displaystyle\left(\operatorname{\mathsf{Spec}}(G),P_{*}^{(1/2)}(G)\right)\text{
and }$ (8) $\displaystyle\operatorname{\mathsf{strong-FSI}}(G)$
$\displaystyle=$
$\displaystyle\left(\operatorname{\mathsf{Spec}}(G),P_{*}^{(1)}(G)\right).$
(9)

The entries of the projection matrices $P_{i}$ have a well-known geometric
meaning [12, 10]. For $1\leq x\leq n$, the standard basis vector
$\mathrm{e}_{x}$ of $\mathbb{R}^{n}$ has 1 in the position $x$ and 0
elsewhere. The _angle_ $\alpha_{i,x}$ of a graph $G$ is defined to be the
cosine of the angle between $\mathrm{e}_{x}$ and the eigenspace $E_{i}$, i.e.,
the angle between $\mathrm{e}_{x}$ and its projection $P_{i}\mathrm{e}_{x}$
onto $E_{i}$. We have the equality

$P_{i}(x,x)=\alpha_{i,x}^{2}.$ (10)

Indeed, let $\langle u,v\rangle$ denote the scalar product of two vectors
$u,v\in\mathbb{R}^{n}$. Then

$P_{i}(x,x)=\langle\mathrm{e}_{x},P_{i}\mathrm{e}_{x}\rangle=\|\mathrm{e}_{x}\|\|P_{i}\mathrm{e}_{x}\|\alpha_{i,x}=\alpha_{i,x}^{2}.$

Furthermore, let $\alpha_{i,xy}$ be the cosine of the angle between the
projections $P_{i}\mathrm{e}_{x}$ and $P_{i}\mathrm{e}_{y}$ of the standard
basis vector $\mathrm{e}_{x}$ and $\mathrm{e}_{y}$ onto $E_{i}$. If
$\mathrm{e}_{x}$ or $\mathrm{e}_{y}$ is orthogonal to $E_{i}$, i.e.,
$\alpha_{i,x}=0$ or $\alpha_{i,y}=0$, then the angle is undefined and we set
$\alpha_{i,xy}=0$ in this case. In particular, $\alpha_{i,xx}=0$ if
$\alpha_{i,x}=0$ while $\alpha_{i,xx}=1$ if $\alpha_{i,x}\neq 0$. Equality
(10) generalizes to

$P_{i}(x,y)=\alpha_{i,x}\alpha_{i,y}\alpha_{i,xy}.$ (11)

Indeed,

$P_{i}(x,y)=\langle\mathrm{e}_{x},P_{i}\mathrm{e}_{y}\rangle=\langle\mathrm{e}_{x},P_{i}^{2}\mathrm{e}_{y}\rangle=\langle
P_{i}\mathrm{e}_{x},P_{i}\mathrm{e}_{y}\rangle=\|P_{i}\mathrm{e}_{x}\|\|P_{i}\mathrm{e}_{y}\|\alpha_{i,xy}=\alpha_{i,x}\alpha_{i,y}\alpha_{i,xy}.$

Now, define a coloring $\alpha_{i}$ by $\alpha_{i}(x,x)=\alpha_{i,x}$ and
$\alpha_{i}(x,y)=\alpha_{i,xy}$ for $x\neq y$. This coloring is isomorphism
invariant basically because an isomorphism is represented by a permutation
matrix, which is the transformation matrix of an isometry of $\mathbb{R}^{n}$.
Using Notation 1,

$\alpha_{*}(x,y)=\left(\alpha_{1}(x,y),\ldots,\alpha_{m}(x,y)\right),$

where $\alpha_{*}$ is an isomorphism-invariant coloring as well. The
corresponding graph invariants $\alpha_{*}^{(r)}$ are closely related to the
invariants $P_{*}^{(r)}$. More precisely, we say that two graph invariants
$\mathcal{I}$ and $\mathcal{I}^{\prime}$ are _equivalent_ and write
$\mathcal{I}\equiv\mathcal{I}^{\prime}$ if
$\mathcal{I}^{\prime}\preceq\mathcal{I}$ and
$\mathcal{I}\preceq\mathcal{I}^{\prime}$.

######  Lemma 2.

$P_{*}^{(r)}\equiv\alpha_{*}^{(r)}$ for every integer $r\geq 0$.

###### Proof.

$r=0$. The equivalence
$\left\\{\\!\\!\left\\{P_{*}(x,x)\right\\}\\!\\!\right\\}_{x}\equiv\left\\{\\!\\!\left\\{\alpha_{*}(x,x)\right\\}\\!\\!\right\\}_{x}$
readily follows from Equality (10) because the angles $\alpha_{i,x}$ are non-
negative.

$r=1$. The equivalence reads

$\left\\{\\!\\!\left\\{\left(P_{*}(x,x),\left\\{\\!\\!\left\\{(P_{*}(x,y),P_{*}(y,y))\right\\}\\!\\!\right\\}_{y}\right)\right\\}\\!\\!\right\\}_{x}\equiv\left\\{\\!\\!\left\\{\left(\alpha_{*}(x,x),\left\\{\\!\\!\left\\{(\alpha_{*}(x,y),\alpha_{*}(y,y))\right\\}\\!\\!\right\\}_{y}\right)\right\\}\\!\\!\right\\}_{x}.$

For the “$\preceq$” part, it suffices to show for each $x$ that
$\left(P_{*}(x,x),\left\\{\\!\\!\left\\{(P_{*}(x,y),P_{*}(y,y))\right\\}\\!\\!\right\\}_{y}\right)$
is determined by
$\left(\alpha_{*}(x,x),\left\\{\\!\\!\left\\{(\alpha_{*}(x,y),\alpha_{*}(y,y))\right\\}\\!\\!\right\\}_{y}\right)$.
Indeed, as we already know, $P_{*}(x,x)$ is determined by $\alpha_{*}(x,x)$ by
(10). In order to show that
$\left\\{\\!\\!\left\\{(P_{*}(x,y),P_{*}(y,y))\right\\}\\!\\!\right\\}_{y}$ is
determined by
$\left\\{\\!\\!\left\\{(\alpha_{*}(x,y),\alpha_{*}(y,y))\right\\}\\!\\!\right\\}_{y}$,
we fix also $y$ and notice that $(P_{*}(x,y),P_{*}(y,y))$ is determined by
$(\alpha_{*}(x,y),\alpha_{*}(y,y))$ because for $1\leq i\leq m$

$P_{i}(x,y)=\alpha_{i}(x,x)\alpha_{i}(x,y)\alpha_{i}(y,y)$ (12)

as a consequence of Equality (11).

The proof of the “$\succeq$” part is similar but requires a little bit more
care. Specifically, we have to argue that for fixed $x$ and $y$,
$(\alpha_{*}(x,y),\alpha_{*}(y,y))$ is determined by
$(P_{*}(x,y),P_{*}(y,y))$. If $\alpha_{i}(x,x)=0$ or $\alpha_{i}(y,y)=0$, then
we cannot determine $\alpha_{i}(x,y)$ from (12) by division but we know that
$\alpha_{i}(x,y)=0$ in this case just by definition.

In general, we proceed like above using induction with $r=0$ as the base case.
∎

Motivated by the equivalence $P_{*}^{(0)}\equiv\alpha_{*}^{(0)}$, we define
the graph invariant $\operatorname{\mathsf{EA}}$ similar to (8)–(9) as

$\operatorname{\mathsf{EA}}(G)=\left(\operatorname{\mathsf{Spec}}(G),P_{*}^{(0)}(G)\right),$
(13)

where the abbreviation $\operatorname{\mathsf{EA}}$ stands for _E_ igenvalues
and _A_ ngles and corresponds to the known concept [11, 10] mentioned in the
introduction.

##  4 Characterization of the spectral invariants by walk counts

A walk of length $k$ (or $k$-walk) from a vertex $x$ to a vertex $y$ is a
sequence of vertices $x=x_{0},x_{1},\ldots,x_{k}=y$ such that every two
successive vertices $x_{i},x_{i+1}$ are adjacent. Let $w_{k}(x,y)$ denote the
number of walks of length $k$ from $x$ to $y$ in a graph. Obviously, $w_{k}$
is an isomorphism-invariant coloring in the sense of Section 2.1. In
accordance with Notation 1, we also consider the isomorphism-invariant
coloring $w_{*}$ defined by

$w_{*}(x,y)=\left(w_{0}(x,y),w_{1}(x,y),\ldots,w_{n-1}(x,y)\right),$

where $n$, as usually, denotes the number of vertices in a graph. Note that
for each $y$, the matrix $\left(w_{k}(x,y)\right)_{1\leq x\leq n,\,0\leq k\leq
n-1}$ determines the value of $w_{k}(x,y)$ for every $x$ and for every
arbitrarily large $k$.

It is well known that the walk counts are expressible in terms of spectral
parameters of a graph; see, e.g., [10]. On the other hand, it is also well
known that the numbers of closed $k$-walks in a graph determine the graph
spectrum. We give a brief overview of these facts in Subsection 4.1. In
Subsection 4.2 we make further use of this connection between walks and
spectra. We are able to characterize the spectral invariants defined in
Section 3 using solely the walk numbers, that is, in purely combinatorial
terms without involving any linear algebra.

###  4.1 Linear-algebraic background and known relations

Since the adjacency matrix $A$ of a graph $G$ is symmetric, the eigenspaces
$E_{i}$ are pairwise orthogonal and, hence $P_{i}P_{j}=O$ for $i\neq j$, where
$O$ denotes the zero matrix. The spectral theorem for symmetric matrices says
in essence that

$\mathbb{R}^{n}=E_{1}\oplus\cdots\oplus E_{m},$

that is, $\mathbb{R}^{n}$ has an orthonormal basis consisting of eigenvectors
of $A$. This decomposition implies that

$I=P_{1}+\cdots+P_{m}.$ (14)

From Equality (14) it is easy to derive the spectral decomposition

$A=\mu_{1}P_{1}+\cdots+\mu_{m}P_{m}.$

Raising both sides of this equality to the $k$-th power and taking into
account that $P_{i}^{2}=P_{i}$ and $P_{i}P_{j}=O$ for $i\neq j$, we conclude
that

$A^{k}=\mu_{1}^{k}P_{1}+\cdots+\mu_{m}^{k}P_{m}.$

Since $w_{k}(x,y)=A^{k}(x,y)$, we get

$w_{k}(x,y)=\mu_{1}^{k}P_{1}(x,y)+\cdots+\mu_{m}^{k}P_{m}(x,y).$ (15)

Let $c_{k}(G)=\sum_{x\in V(G)}w_{k}(x,x)$ denote the total number of closed
$k$-walks in a graph $G$. In particular, $c_{0}(G)=n$ and $c_{1}(G)=0$.

######  Lemma 3 (folklore).

$\operatorname{\mathsf{Spec}}G=\operatorname{\mathsf{Spec}}H$ if and only if
$c_{k}(G)=c_{k}(H)$ for $k=0,1,\ldots,n$.

###### Proof.

(following [15]) Note that $c_{k}(G)=\operatorname{tr}A^{k}$, where
$\operatorname{tr}$ denotes the trace of a matrix. It follows that

$c_{k}(G)=\sum_{i=1}^{n}\lambda^{k}_{i}$ (16)

where the summation is over all $n$ eigenvalues. This proves the forward
direction of the lemma. For the other direction, note that Equalities (16),
for $k=0,1,\ldots,n$, yield the coefficients of the characteristic polynomial
$P_{G}(z)=\prod_{i=1}^{n}(z-\lambda_{i})$ by Newton’s identities. ∎

###  4.2 General characterization

######  Theorem 4.

$(\operatorname{\mathsf{Spec}},P_{*}^{(r)})\equiv w_{*}^{(r)}$ for every
$r=0,1/2,1,2,\ldots$.

Before proving Theorem 4, we describe some of its consequences.

######  Corollary 5.

  1. 1.

$\operatorname{\mathsf{EA}}\equiv w_{*}^{(0)}$.

  2. 2.

$\operatorname{\mathsf{weak-FSI}}\equiv w_{*}^{(1/2)}$.

  3. 3.

$\operatorname{\mathsf{strong-FSI}}\equiv w_{*}^{(1)}$.

Parts 2 and 3 of Corollary 5, which are particular cases of Theorem 4 for
$r=1/2$ and $r=1$ respectively, provide a characterization of both Fürer’s
spectral invariants. We now comment on Part 1. By Definition (13), this part
is the special case of Theorem 4 for $r=0$. Note that
$w_{*}^{(0)}(G)=w_{*}^{(0)}(H)$ if and only if the graphs $G$ and $H$ are
_closed-walk-equivalent_ in the sense that there is a bijection
$f:V(G)\rightarrow V(H)$ such that $w_{k}(x,x)=w_{k}(f(x),f(x))$ for all $x\in
V(G)$ and all $k$. On the other hand, let us say that $G$ and $H$ are _EA-
equivalent_ if these graphs have the same eigenvalues (spectrum) and angles,
i.e., $\operatorname{\mathsf{EA}}(G)=\operatorname{\mathsf{EA}}(H)$. As seen
from the summary in Subsection 4.1, close connections between the closed walk
numbers and the eigenvalues and angles are well known. Part 1 of Corollary 5
pinpoints the fact that the two equivalence concepts actually coincide.

Corollary 5 reveals connections of spectral invariants to other graph
invariants studied in the literature, which we introduce now.

The _walk matrix_ $W$ of a graph $G$ is indexed by vertices $1\leq x\leq n$
and the length parameter $0\leq k\leq n-1$ and defined by

$W(x,k)=\sum_{y=1}^{n}w_{k}(x,y).$ (17)

That is, $W(x,k)$ is the total number of $k$-walks starting from the vertex
$x$. Let $\mathit{WL}_{1}^{k}(G,x)$ denote the color assigned by $1$-WL to a
vertex $x$ of $G$ after the $k$-th refinement round. For a vertex $x$ of $G$,
let $G_{x}$ denote the version of $G$ with $x$ _individualized_. This means
that $G_{x}$ is a vertex-colored graph where $x$ has a special unique color
while the other vertices are colored uniformly. We now state two well-known
facts.

######  Lemma 6.

  1. 1.

$W(x,k)$ is determined by $\mathit{WL}_{1}^{k}(G,x)$;

  2. 2.

$w_{k}(x,y)$ is determined by $\mathit{WL}_{1}^{k}(G_{x},y)$;

Part 1 of Lemma 6 is proved in algebraic terms in [24, Theorem 2]. Another
proof, involving logical concepts, is provided in [13, Lemma 4] and a direct
combinatorial proof can be found in [32, Lemma 8]. Part 2 is a straightforward
extension of Part 1.

In addition to the graph invariants $\mathsf{WL}_{1}$ and $\mathsf{WL}_{2}$
introduced in Section 2.2, we define

$\mathsf{WL}_{3/2}(G)=\left\\{\\!\\!\left\\{\mathsf{WL}_{1}(G_{x})\right\\}\\!\\!\right\\}_{x\in
V(G)}.$

This yields a chain of graph invariants $\mathsf{WL}_{d}$ for
$d\in\\{1,3/2,2\\}$, where $\mathsf{WL}_{c}\preceq\mathsf{WL}_{d}$ if $c\leq
d$. The walk matrix naturally defines a graph invariant, which we denote by
$\operatorname{\mathsf{WM}}$ and define as
$\operatorname{\mathsf{WM}}(G)=\left\\{\\!\\!\left\\{W(x,*)\right\\}\\!\\!\right\\}_{x\in
V(G)}$ where $W(x,*)=\big{(}W(x,0),W(x,1),\ldots,\allowbreak W(x,n-1)\big{)}$.
In other words, $\operatorname{\mathsf{WM}}(G)$ is the multiset of the rows of
the walk matrix of $G$. Part 1 of Lemma 6 readily implies that
$\operatorname{\mathsf{WM}}\preceq\mathsf{WL}_{1}$. Thus,

$\operatorname{\mathsf{WM}}\preceq\mathsf{WL}_{1}\preceq\mathsf{WL}_{3/2}\preceq\mathsf{WL}_{2}.$

The second relation in the following corollary is the recent result in [25]
already described above.

######  Corollary 7.

$\operatorname{\mathsf{WM}}\preceq\operatorname{\mathsf{weak-
FSI}}\preceq\mathsf{WL}_{3/2}$.

###### Proof.

By Part 2 of Corollary 5, it is enough to show that

$\operatorname{\mathsf{WM}}\preceq w_{*}^{(1/2)}\preceq\mathsf{WL}_{3/2}.$

The former relation follows directly from the definitions of
$\operatorname{\mathsf{WM}}$ and $w_{*}^{(1/2)}$. Indeed, $w_{*}^{(1/2)}(G)$
comprises the multiset
$\left\\{\\!\\!\left\\{w_{*}(x,y)\right\\}\\!\\!\right\\}_{y\in V(G)}$ for
each vertex $x$ of $G$; see (4). This multiset allows us to calculate the sum
(17). The latter relation follows from the definitions of $w_{*}^{(1/2)}$ and
$\mathsf{WL}_{3/2}$ by Part 2 of Lemma 6. ∎

The relationship between the graph invariants discussed above is summarized in
Figure 1 below, which also puts these invariants in a somewhat broader
context.

###  4.3 Completeness of spectral invariants for almost all graphs

The next consequence of Theorem 4 is interesting in view of the long-standing
open question whether almost all graphs are determined up to isomorphism by
their spectrum [16, 31].

######  Corollary 8.

Almost all graphs are determined up to isomorphism by
$\operatorname{\mathsf{weak-FSI}}$.

###### Proof.

It is known that if the walk matrix is non-singular, then it determines the
adjacency matrix [19]. Moreover, the walk matrix of a random graph is non-
singular with high probability [22]. As a consequence, almost all graphs are
determined by the graph invariant $\operatorname{\mathsf{WM}}$; see [19, Th.
7.2]. The same is true also for $\operatorname{\mathsf{weak-FSI}}$ because
$\operatorname{\mathsf{weak-FSI}}$ is stronger than
$\operatorname{\mathsf{WM}}$ by Corollary 7. ∎

Since
$\operatorname{\mathsf{Spec}}\preceq\operatorname{\mathsf{EA}}\preceq\operatorname{\mathsf{weak-
FSI}}$, Corollary 8 motivates the question whether almost all graphs are
determined by their eigenvalues and angles, which would be yet closer to the
aforemention open problem. We answer this question in the affirmative. In
addition to the properties of random graphs exploited in the proof of
Corollary 8, we will also use the result of Tao and Vu [29] that a random
graph has simple spectrum, i.e., no multiple eigenvalues with high
probability.

######  Lemma 9.

If $G$ has simple spectrum, then $\operatorname{\mathsf{WM}}(G)$ is determined
by $\operatorname{\mathsf{EA}}(G)$.

###### Proof.

Since every eigenspace $E_{i}$ of $G$ is one-dimensional, we have
$\alpha_{i,xy}=1$ unless $\alpha_{i,x}=0$ or $\alpha_{i,y}=0$. If at least one
of the last two equalities is true, we have $\alpha_{i,xy}=0$. In any case,
Equality (11) simplifies to

$P_{i}(x,y)=\alpha_{i,x}\alpha_{i,y}.$ (18)

The value of $\operatorname{\mathsf{EA}}(G)$ provides us with all $n$
eigenvalues $\mu_{1},\ldots,\mu_{n}$ and, by Equality (10), also with the
multiset
$\left\\{\\!\\!\left\\{(\alpha_{1,y},\ldots,\alpha_{n,y})\right\\}\\!\\!\right\\}_{y}$.
Using this multiset, for each $x$ we can compute the multiset
$\left\\{\\!\\!\left\\{(\alpha_{1,x}\alpha_{1,y},\ldots,\alpha_{n,x}\alpha_{n,y})\right\\}\\!\\!\right\\}_{y}$,
which is, by (18), nothing else as the multiset
$\left\\{\\!\\!\left\\{(P_{1}(x,y),\ldots,P_{n}(x,y))\right\\}\\!\\!\right\\}_{y}$.
On the account of Equality (15), the last multiset allows us to compute

$W(x,k)=\sum_{y=1}^{n}w_{k}(x,y)=\sum_{y=1}^{n}\sum_{i=1}^{n}\mu_{i}^{k}P_{i}(x,y)$

for each $x$ and each $k$, yielding $\operatorname{\mathsf{WM}}(G)$. ∎

######  Theorem 10.

Almost all graphs are determined up to isomorphism by
$\operatorname{\mathsf{EA}}$.

###### Proof.

Suppose that a graph $G$ has non-singular walk matrix and simple spectrum, the
two properties that are fulfilled for almost all graphs [22, 29]. Let $H$ be
an arbitrary graph. It suffices to prove that the equality
$\operatorname{\mathsf{EA}}(G)=\operatorname{\mathsf{EA}}(H)$ implies that $G$
and $H$ are isomorphic.

By [19], the isomorphism of $G$ and $H$ follows from the equality
$\operatorname{\mathsf{WM}}(G)=\operatorname{\mathsf{WM}}(H)$ because the walk
matrix of $G$ is non-singular. Thus, all what we need is the equality
$\operatorname{\mathsf{WM}}(G)=\operatorname{\mathsf{WM}}(H)$. The graph $G$
has simple spectrum. The condition
$\operatorname{\mathsf{EA}}(G)=\operatorname{\mathsf{EA}}(H)$ implies that $H$
has the same spectrum and, hence, the spectrum of $H$ is also simple. By Lemma
9, $\operatorname{\mathsf{WM}}(G)$ is determined by
$\operatorname{\mathsf{EA}}(G)$, and $\operatorname{\mathsf{WM}}(H)$ is
determined by $\operatorname{\mathsf{EA}}(H)$. Since
$\operatorname{\mathsf{EA}}(G)=\operatorname{\mathsf{EA}}(H)$, we therefore
have $\operatorname{\mathsf{WM}}(G)=\operatorname{\mathsf{WM}}(H)$, as
required. ∎

We remark that Theorem 10 is, in fact, more constructive than it is stated.
The proof implies that the closed walk numbers, which are the diagonal
elements of the powers of the adjacency matrix, can be used to distinguish
almost every graph for any non-isomorphic graph. Moreover, there are explicit
conditions ensuring that this works for a particular graph, namely the walk
matrix non-singularity and the spectrum simplicity.

######  Open Problem 11.

Are almost all graphs determined by one of the invariants
$\operatorname{\mathsf{main-EA}}$ and $\operatorname{\mathsf{gen-Spec}}$,
introduced below (see also Figure 1)?

###  4.4 Proof of Theorem 4

$r=0$. We have to prove that

$\left(\operatorname{\mathsf{Spec}},\left\\{\\!\\!\left\\{P_{*}(x,x)\right\\}\\!\\!\right\\}_{x}\right)\equiv\left\\{\\!\\!\left\\{w_{*}(x,x)\right\\}\\!\\!\right\\}_{x}.$
(19)

The “$\succeq$” part immediately follows from Equality (15). In the other
direction, the relation
$\operatorname{\mathsf{Spec}}\preceq\left\\{\\!\\!\left\\{w_{*}(x,x)\right\\}\\!\\!\right\\}_{x}$
is a direct consequence of Lemma 3. To complete the proof of (19), we show
that for each vertex $x$, the sequence $P_{*}(x,x)$ can be obtained from the
sequences $w_{*}(x,x)$ and $\mu_{*}$. To this end, put $y=x$ in Equality (15),
obtaining

$\mu_{1}^{k}P_{1}(x,x)+\cdots+\mu_{m}^{k}P_{m}(x,x)=w_{k}(x,x).$ (20)

This equality makes sense also for $k=0$. In this case, it reads

$P_{1}(x,x)+\cdots+P_{m}(x,x)=1,$ (21)

which is true by Equality (14) (if $\mu_{i}=0$, we need to use the convention
$0^{0}=1$). Consider Equalities (20) for $k=0,1,\ldots,m-1$ as a system of $m$
linear equations for $m$ unknowns $P_{1}(x,x),\ldots,P_{m}(x,x)$. The
coefficients of this system are powers of the $m$ pairwise distinct
eigenvalues. They form a Vandermonde matrix. Therefore, the system is uniquely
solvable, and the sequence $P_{*}(x,x)$ is determined.

$r=1/2$. Now we have to prove that

$\left(\operatorname{\mathsf{Spec}},\left\\{\\!\\!\left\\{\left(P_{*}(x,x),\left\\{\\!\\!\left\\{P_{*}(x,y)\right\\}\\!\\!\right\\}_{y}\right)\right\\}\\!\\!\right\\}_{x}\right)\equiv\left\\{\\!\\!\left\\{\left(w_{*}(x,x),\left\\{\\!\\!\left\\{w_{*}(x,y)\right\\}\\!\\!\right\\}_{y}\right)\right\\}\\!\\!\right\\}_{x}.$
(22)

The “$\succeq$” part is again an immediate consequence of Equality (15).

Let us prove the part “$\preceq$”. That is, we have to show that for a given
graph, the left hand side of (22) can be obtained from the right hand side.
The spectrum is, as already observed in the case of $r=0$, determined by the
multiset $\left\\{\\!\\!\left\\{w_{*}(x,x)\right\\}\\!\\!\right\\}_{x}$, which
is easy to obtain from the right hand side of (22). Thus, in what follows we
can assume that the sequence $\mu_{1},\ldots,\mu_{m}$ of distinct eigenvalues
is known. For each vertex $x$, we have to compute the sequence $P_{*}(x,x)$
and the multiset
$\left\\{\\!\\!\left\\{P_{*}(x,y)\right\\}\\!\\!\right\\}_{y}$. The former
task is solvable exactly as in the case of $r=0$, and we focus on the latter
task. In addition to $x$, we now fix also $y$ and consider Equalities (15) for
$k=0,1,\ldots,m-1$. Here, the equality for $k=0$ is actually a particular
instance of Equality (14), that is, this is (21) if $y=x$ and

$P_{1}(x,y)+\cdots+P_{m}(x,y)=0$

if $y\neq x$. As in the case of $r=0$, for $m$ unknowns
$P_{1}(x,y),\ldots,P_{m}(x,y)$ we obtain a system of $m$ linear equation whose
coefficients form a non-singular Vandermonde matrix. Hence, we can determine
the sequence $P_{*}(x,y)$, completing the proof of (22).

For $r\geq 1$ we proceed as above using induction. To facilitate the notation,
we set $\pi(x,y)=P_{*}(x,y)$ and $\omega(x,y)=w_{*}(x,y)$. We write
$a\mapsfrom b$ to say that $a$ is obtainable from $b$. As we have already
seen,

$\omega(x,y)\mapsfrom\operatorname{\mathsf{Spec}},\,\pi(x,y)$ (23)

by Equality (15) and

$\pi(x,y)\mapsfrom\operatorname{\mathsf{Spec}},\,\omega(x,y)$ (24)

by the Vandermonde matrix argument. The vertex colorings $\pi_{r}$ and
$\omega_{r}$ are defined as in (2). For every $r$,

$\operatorname{\mathsf{Spec}}\mapsfrom\left\\{\\!\\!\left\\{\omega_{0}(x)\right\\}\\!\\!\right\\}_{x}\mapsfrom\left\\{\\!\\!\left\\{\omega_{r}(x)\right\\}\\!\\!\right\\}_{x}.$
(25)

The former relation is, as already observed above, a consequence of Lemma 3,
while the latter relation follows directly from the definition of
$\omega_{r}$. Therefore, in order to prove that

$\left(\operatorname{\mathsf{Spec}},\left\\{\\!\\!\left\\{\pi_{r}(x)\right\\}\\!\\!\right\\}_{x}\right)\preceq\left\\{\\!\\!\left\\{\omega_{r}(x)\right\\}\\!\\!\right\\}_{x},$

it suffices to prove for each $x$ that

$\pi_{r}(x)\mapsfrom\operatorname{\mathsf{Spec}},\,\omega_{r}(x).$ (26)

In order to prove that

$\left\\{\\!\\!\left\\{\omega_{r}(x)\right\\}\\!\\!\right\\}_{x}\preceq\left(\operatorname{\mathsf{Spec}},\left\\{\\!\\!\left\\{\pi_{r}(x)\right\\}\\!\\!\right\\}_{x}\right),$

it suffices to prove for each $x$ that

$\omega_{r}(x)\mapsfrom\operatorname{\mathsf{Spec}},\,\pi_{r}(x).$ (27)

We prove (26) and (27) by induction on $r$.

In the base case we have $r=0$. The relation (27) for $r=0$ follows from the
relation (23) for $y=x$. Similarly, the relation (26) for $r=0$ follows from
the relation (24) for $y=x$.

For the induction step, suppose that $r\geq 1$. Consider first (26). Recall
that

$\pi_{r}(x)=\left(\pi_{r-1}(x),\left\\{\\!\\!\left\\{(\pi(x,y),\pi_{r-1}(y))\right\\}\\!\\!\right\\}_{y}\right).$

By the induction hypothesis,

$\pi_{r-1}(x)\mapsfrom\operatorname{\mathsf{Spec}},\,\omega_{r-1}(x)\mapsfrom\operatorname{\mathsf{Spec}},\,\omega_{r}(x).$

The latter relation follows from the fact that $\omega_{r-1}(x)$ is a part of
$\omega_{r}(x)$. Another part of $\omega_{r}(x)$ gives us the multiset
$\left\\{\\!\\!\left\\{(\omega(x,y),\omega_{r-1}(y))\right\\}\\!\\!\right\\}_{y}$.
Therefore, it suffices to argue that, for each $y$,

$(\pi(x,y),\pi_{r-1}(y))\mapsfrom\operatorname{\mathsf{Spec}},\,(\omega(x,y),\omega_{r-1}(y)).$

Indeed, $\pi(x,y)$ is determined by (24), and $\pi_{r-1}(y)$ is determined by
the induction hypothesis.

The argument for (27) is virtually the same, with the roles of $\pi$ and
$\omega$ interchanged. In place of (24), we have to refer to (23). The proof
is complete.

##  5 Hierarchy

Figure 1 shows the invariants from Section 4.2 and the relations between them
as a part of a more general picture involving also some other spectral
invariants studied in the literature, which we introduce in the next two
subsections.

Moreover, we define a new invariant $w_{*}^{(\bullet)}$ which is, in a sense,
the limit of the sequence of invariants $w_{*}^{(r)}$ for $r=1,2,\ldots$. The
definition is rather general. As we already mentioned, the formal framework of
Section 2.1 is analogous to the concept of color refinement. Given an
isomorphism-invariant coloring $\chi$, we therefore can along with graph
invariants $\chi^{(r)}$ define the stable version $\chi^{(\bullet)}$. One
possibility to do this is to set $\chi^{(\bullet)}(G)=\chi^{(n)}(G)$, where
$n$ is the number of vertices in $G$. Note that
$\chi^{(r)}\preceq\chi^{(\bullet)}$ for every $r$.

${\mathsf{WL}_{2}}$${w_{*}^{(\bullet)}}$${\cdots}$${w_{*}^{(r)}}$${(r\geq
1)}$${\vdots}$${\mathsf{WL}_{3/2}}$${w_{*}^{(1)}}$${\operatorname{\mathsf{strong-
FSI}}}$${\mathsf{WL}_{1}}$${w_{*}^{(1/2)}}$${\operatorname{\mathsf{weak-
FSI}}}$${\operatorname{\mathsf{WM}}}$${\operatorname{\mathsf{gen-
Spec}}}$${w_{*}^{(0)}}$${\operatorname{\mathsf{EA}}}$${\operatorname{\mathsf{main-
EA}}}$${\operatorname{\mathsf{Spec}}}$ Figure 1: Relations between graph
invariants. An arrow $\mathcal{I}\to\mathcal{I}^{\prime}$ means
$\mathcal{I}^{\prime}\preceq\mathcal{I}$.

###  5.1 Main eigenvalues and angles

Let $\mathrm{j}$ denote the all-ones vector (the dimension should be clear
from the context). Using our usual notation, suppose that $G$ has $m$ distinct
eigenvalues $\mu_{1},\ldots,\mu_{m}$, and let $E_{1},\ldots,E_{m}$ be the
corresponding eigenspaces of $G$. Consider the angle between $E_{i}$ and
$\mathrm{j}$ and denote its cosine by $\beta_{i}$. If $\beta_{i}\neq 0$, the
corresponding eigenvalue is called a _main eigenvalue_ , and then the positive
number $\beta_{i}$ is called a _main angle_. Let
$\nu_{1},\ldots,\nu_{m^{\prime}}$ be the sequence of all main eigenvalues in
the ascending order and $\theta_{1},\ldots,\theta_{m^{\prime}}$ be the
sequence of the main angles in the corresponding order. We define a graph
invariant $\operatorname{\mathsf{main-EA}}$ by

$\operatorname{\mathsf{main-EA}}(G)=\left(\nu_{*},\theta_{*}\right).$

A characterization of $\operatorname{\mathsf{main-EA}}$ in terms of walk
numbers is known. We state it in the proposition below and, for the sake of
completeness, provide some proof details apparently missing in the available
literature. Let

$w_{k}(G)=\sum_{x\in V(G)}w_{k}(x)$

be the total number of $k$-walks in $G$. By $W_{G}$ we will denote the
corresponding generating function, that is, a formal series

$W_{G}(z)=\sum_{k=0}^{\infty}w_{k}(G)z^{k}.$

######  Proposition 12 (folklore, e.g. [27]).

Let $G$ and $H$ be graphs with $n$ vertices. Then $\operatorname{\mathsf{main-
EA}}(G)=\operatorname{\mathsf{main-EA}}(H)$ if and only if $w_{k}(G)=w_{k}(H)$
for $k=1,\ldots,n-1$ (hence for all $k\geq 0$).

###### Proof.

In the forward direction the proposition follows from the trivial equality
$w_{0}(G)=n$ and the equality

$w_{k}(G)=n\sum_{i=1}^{m^{\prime}}\nu_{i}^{k}\theta_{i}^{2}$ (28)

for $k\geq 1$; see [10, Th. 1.3.5] for details.

For the other direction, consider the generating function $W_{G}(z)$. This is
a formal power series, i.e., an element of the ring $\mathbb{R}[[z]]$. In this
ring we have

$W_{G}(z)=\sum_{k=0}^{\infty}\left(n\sum_{i=1}^{m^{\prime}}\nu_{i}^{k}\theta_{i}^{2}\right)z^{k}=\sum_{i=1}^{m^{\prime}}n\theta_{i}^{2}\sum_{k=0}^{\infty}(\nu_{i}z)^{k}=\sum_{i}\frac{n\theta_{i}^{2}}{1-\nu_{i}z}.$
(29)

Note that all divisions are well defined because $1-\nu_{i}z$ are invertible
elements of $\mathbb{R}[[z]]$. If 0 is a main eigenvalue, then the sum in (28)
involves the coefficient $0^{0}=1$. In this case, we suppose that $\nu_{0}=0$,
starting the indexation from 0. Otherwise it is still convenient to set
$\nu_{0}=0$ and $\theta_{0}=0$. In each case, Equality (29) can be rewritten
as

$W_{G}(z)=n\theta_{0}^{2}+\sum_{i\neq
0}\frac{n\theta_{i}^{2}/\nu_{i}}{1/\nu_{i}-z}.$

From here we see that the numbers $\nu_{i}$ and $\theta_{i}$ are uniquely
determined by $W_{G}(z)$. This follows from the simple observation that if
$c_{0}+\sum_{i\neq 0}c_{i}/(a_{i}-z)=0$ in $\mathbb{R}[[z]]$ for finitely many
pairwise distinct reals $a_{i}$, then $c_{i}=0$ for all $i$. ∎

As a direct consequence, we get the relation $\operatorname{\mathsf{main-
EA}}\preceq\operatorname{\mathsf{WM}}$.

###  5.2 The generalized spectrum

Another important spectral invariant of $G$ is the spectrum of the complement
graph $\overline{G}$. The equalities
$\operatorname{\mathsf{Spec}}G=\operatorname{\mathsf{Spec}}H$ and,
simultaneously,
$\operatorname{\mathsf{Spec}}{\overline{G}}=\operatorname{\mathsf{Spec}}{\overline{H}}$
are equivalent to the condition that the graphs $G$ and $H$ have the same
_generalized spectrum_. For the definition of this concept and its various
characterizations we refer the reader to [18] and [30, Th. 3]. We define the
graph invariant $\operatorname{\mathsf{gen-Spec}}$ by

$\operatorname{\mathsf{gen-
Spec}}(G)=\left(\operatorname{\mathsf{Spec}}G,\operatorname{\mathsf{Spec}}{\overline{G}}\right).$

We note that

$\operatorname{\mathsf{main-EA}}\preceq\operatorname{\mathsf{gen-Spec}}.$

This follows from Proposition 12 and the following result in [8]. Let $P_{G}$
denote the characteristic polynomial of a graph $G$.

######  Proposition 13 (Cvetković [8]).

$W_{G}(z)=\frac{1}{z}\left((-1)^{n}\frac{P_{\overline{G}}(-1/z-1)}{P_{G}(1/z)}-1\right)$.

To complete the diagram in Figure 1, it remains to prove the following
relation.

######  Theorem 14.

$\operatorname{\mathsf{gen-Spec}}\preceq\operatorname{\mathsf{weak-FSI}}$.

To give the reader a flavour of how our characterization of spectral
invariants in terms of walk counts (Theorem 4) works, we provide two proofs of
Theorem 14, one combinatorial that uses the characterization of
$\operatorname{\mathsf{weak-FSI}}$ in Corollary 5 and anoter one, more
algebraic, that uses the original definition of $\operatorname{\mathsf{weak-
FSI}}$.

###### Combinatorial proof of Theorem 14.

The spectrum of $G$, hence also the characteristic polynomial $P_{G}$, is
determined by $\operatorname{\mathsf{weak-FSI}}(G)$ just by definition. We
have to show that $\operatorname{\mathsf{Spec}}{\overline{G}}$ or,
equivalently, $P_{\overline{G}}$ is also determined. By Proposition 13,
$P_{\overline{G}}$ is obtainable from $P_{G}$ and $W_{G}$. Using Part 2 of
Corollary 5, it remains to notice that $W_{G}$ is determined by
$w_{*}^{(1/2)}(G)$. Indeed,

$w_{k}(G)=\sum_{x}w_{k}(x)=\sum_{x}\sum_{y}w_{k}(x,y),$

where the right hand side is obtainable from the multiset
$\left\\{\\!\\!\left\\{\left\\{\\!\\!\left\\{w_{k}(x,y)\right\\}\\!\\!\right\\}_{y}\right\\}\\!\\!\right\\}_{x}$,
which is a part of $w_{*}^{(1/2)}(G)$. ∎

The algebraic proof is based on the fact that $\operatorname{\mathsf{weak-
FSI}}$ determines not only the main angles but also the entire sequence of
angles between the all-ones vector and eigenspaces ordered by the ascending
order of the eigenvalues.

######  Lemma 15.

$\operatorname{\mathsf{weak-FSI}}$ determines $\beta_{*}$.

###### Proof.

Note that

$\langle\mathrm{j},P_{i}\mathrm{j}\rangle=\|\mathrm{j}\|\|P_{i}\mathrm{j}\|\beta_{i}.$

On the other hand,

$\langle\mathrm{j},P_{i}\mathrm{j}\rangle=\langle\mathrm{j},P_{i}^{2}\mathrm{j}\rangle=\langle
P_{i}\mathrm{j},P_{i}\mathrm{j}\rangle=\|P_{i}\mathrm{j}\|^{2},$

from which we conclude that $\beta_{i}=\|P_{i}\mathrm{j}\|/{\sqrt{n}}$.
Furthermore,

$\|P_{i}\mathrm{j}\|^{2}=\langle\mathrm{j},P_{i}\mathrm{j}\rangle=\langle\sum_{x}\mathrm{e}_{x},P_{i}\sum_{y}\mathrm{e}_{y}\rangle=\sum_{x,y}\langle\mathrm{e}_{x},P_{i}\mathrm{e}_{y}\rangle=\sum_{x,y}P_{i}(x,y).$

It follows that $\|P_{i}\mathrm{j}\|$ and, hence, $\beta_{i}$ can be
determined from $\operatorname{\mathsf{weak-FSI}}$ because
$\operatorname{\mathsf{weak-FSI}}$ gives us the multiset
$\left\\{\\!\\!\left\\{\left\\{\\!\\!\left\\{P_{i}(x,y)\right\\}\\!\\!\right\\}_{y}\right\\}\\!\\!\right\\}_{x}$
for each $i=1,\ldots,n$. ∎

###### Another proof of Theorem 14.

As it readily follows from Lemma 15, $\operatorname{\mathsf{EA}}(G)$ is
determined by $\operatorname{\mathsf{weak-FSI}}(G)$. By Proposition 12, this
implies that $\operatorname{\mathsf{weak-FSI}}(G)$ determines $W_{G}$.
Therefore, $\operatorname{\mathsf{Spec}}{\overline{G}}$ is obtainable from
$\operatorname{\mathsf{weak-FSI}}(G)$ by Proposition 13. ∎

##  6 Separations

Fürer [14] poses the open problem of determining which of the relations in the
chain

$\operatorname{\mathsf{weak-FSI}}\preceq\operatorname{\mathsf{strong-
FSI}}\preceq\mathsf{WL}_{2}$

are strict. As mentioned before, Rattan and Seppelt [25] show that this chain
does not entirely collapse. They separate $\operatorname{\mathsf{weak-FSI}}$
and $\mathsf{WL}_{2}$ by proving that $\operatorname{\mathsf{weak-
FSI}}\preceq\mathsf{WL}_{3/2}$ and separating $\mathsf{WL}_{3/2}$ and
$\mathsf{WL}_{2}$. Hence, at least one of the two relations in (1) is strict.
Fürer [14] conjectures that the first relation in (1) is strict and does not
exclude the possibility that the last two invariants in (1) are equivalent. We
settle this by showing that, in fact, both relations in (1) are strict. We
actually prove much more: up to one question remaining open, the diagram shown
in Figure 1 is exact in the sense that all present arrows are non-reversible
and that any two invariants not connected by arrows are provably incomparable.
The only remaining question concerns the chain $w_{*}^{(\bullet)}\to\cdots\to
w_{*}^{(r)}\to\cdots\to w_{*}^{(1)}$; see Problem 21 stated below.

We now present a minimal set of separations from which all other separations
follow. For compatibility with Figure 1, we write
$\mathcal{I}\nrightarrow\mathcal{I}^{\prime}$ to negate
$\mathcal{I}^{\prime}\preceq\mathcal{I}$.

$\mathsf{WL}_{1}\nrightarrow\operatorname{\mathsf{Spec}}$.

To show this, we have to present two $\mathsf{WL}_{1}$-equivalent but not
cospectral graphs. The simplest pair of $\mathsf{WL}_{1}$-equivalent graphs,
$2C_{3}$ and $C_{6}$, works. Indeed, the eigenvalues of $C_{n}$ are
$2\cos\frac{2\pi k}{n}$ for $k=0,1,\ldots,n-1$, and the spectrum of the
disjoint union of graphs is the union of their spectra; see, e.g., [10,
Example 1.1.4 and Theorem 2.1.1].

$\operatorname{\mathsf{EA}}\nrightarrow\operatorname{\mathsf{main-EA}}$.

It is known [9] that among trees with up to 20 vertices there is a single pair
of non-isomorphic trees, with 19 vertices, with the same eigenvalues and
angles. Using Proposition 12, a direct computation shows that these two trees
are not $\operatorname{\mathsf{main-EA}}$-equivalent; see Appendix A for
details.

$\operatorname{\mathsf{gen-Spec}}\nrightarrow\operatorname{\mathsf{WM}}$.

The smallest, with respect to the number of vertices and the number of edges,
pair of generalized cospectral graphs consists of 7-vertex graphs $G$ and $H$
where $G=C_{6}\cup K_{1}$ and $H$ is obtained from the 3-star $K_{1,3}$ by
subdividing each edge; see [16, Fig. 4]. Since $G$ has an isolated vertex and
$H$ does not, these graphs are not $\operatorname{\mathsf{WM}}$-equivalent.

$\operatorname{\mathsf{gen-Spec}}\nrightarrow\operatorname{\mathsf{EA}}$.

The same pair of graphs $G$ and $H$ works. They are not
$\operatorname{\mathsf{EA}}$-equivalent because connectedness of a graph is
determined by its spectrum and angles [10, Th. 3.3.3]. Another reason for this
is that every graph with at most 9 vertices is determined by its spectrum and
angles up to isomorphism [9].

$\operatorname{\mathsf{strong-FSI}}\nrightarrow\mathsf{WL}_{1}$.

An even stronger fact, namely $w_{*}^{(2)}\nrightarrow\mathsf{WL}_{1}$ is
proved as Theorem 17 below. The separation implies that
$\operatorname{\mathsf{strong-FSI}}\nrightarrow\mathsf{WL}_{2}$ answering one
part of Fürer’s question. Another consequence is also the separation
$\operatorname{\mathsf{WM}}\nrightarrow\mathsf{WL}_{1}$, which follows as well
from [32, Theorem 3].

$\mathsf{WL}_{1}\nrightarrow\mathsf{WL}_{3/2}$.

Consider $C_{6}$ and $2C_{3}$.

$\mathsf{WL}_{3/2}\nrightarrow\operatorname{\mathsf{strong-FSI}}$.

This is Theorem 16 below. As a consequence, $\operatorname{\mathsf{weak-
FSI}}\nrightarrow\operatorname{\mathsf{strong-FSI}}$, answering the other part
of Fürer’s question. Another consequence is the separation
$\mathsf{WL}_{3/2}\nrightarrow\mathsf{WL}_{2}$ shown in [25].

$w_{*}^{(\bullet)}\nrightarrow\mathsf{WL}_{2}$.

This is Theorem 20 below. It considerably strengthens the negative answer to
Fürer’s question by showing that the whole hierarchy of the invariants
$w_{*}^{(r)}$ for all $r$ is strictly weaker than $\mathsf{WL}_{2}$.

We state and prove the three results announced above in the rest of this
section.

###  6.1 $\mathsf{WL}_{3/2}$ is not stronger than
$\operatorname{\mathsf{strong-FSI}}$

######  Theorem 16.

$\operatorname{\mathsf{strong-FSI}}\npreceq\mathsf{WL}_{3/2}$.

###### Proof.

The separation $\mathsf{WL}_{2}\npreceq\mathsf{WL}_{3/2}$ in [25] is shown by
constructing a pair of $\mathsf{WL}_{3/2}$-equivalent graphs $G$ and $H$ as
follows. Consider two copies of $C_{6}*K_{1}$, where $*$ is the join of
graphs. Denote the vertices of degree 6 by $u_{1}$ and $u_{2}$. Consider also
two copies of $(2C_{3})*K_{1}$, denoting their vertices of degree 6 by $v_{1}$
and $v_{2}$. The graph $G$ is obtained by adding four edges forming the cycle
$u_{1}u_{2}v_{1}v_{2}$, and the graph $H$ is obtained by adding the cycle
$u_{1}v_{1}u_{2}v_{2}$. In [25] it is observed that $G$ and $H$ are
distinguishable by 2-WL. We now show the stronger fact that
$\operatorname{\mathsf{strong-FSI}}(G)\neq\operatorname{\mathsf{strong-
FSI}}(H)$.

The vertices $u_{1},u_{2},v_{1},v_{2}$ will be referred to as $Q$-vertices.
The other vertices are split into two classes, $H$-vertices and $T$-vertices,
depending on whether they belong to a hexagonal or a triangular part. A vertex
$x$ is a $Q$-vertex exactly when $w_{2}(x,x)=\deg x=8$. The $H$\- and the
$T$-vertices are distinguishable by the condition $w_{3}(x,x)=6$ for a
$T$-vertex and $w_{3}(x,x)=4$ for an $H$-vertex. Consider an arbitrary
$T$-vertex $x$ in $G$. Note that from $x$ there is at least one 3-walk to each
of the twelve $T$-vertices $y$. If we consider a $T$-vertex $x$ in $H$, then
from $x$ there are 3-walks only to six $T$-vertices $y$. This implies that
$w_{*}^{(1)}(G)\neq w_{*}^{(1)}(H)$. We conclude by Part 3 of Corollary 5 that
$G$ and $H$ are not $\operatorname{\mathsf{strong-FSI}}$-equivalent, as
needed. ∎

###  6.2 $w_{*}^{(2)}$ is not stronger than $\mathsf{WL}_{1}$

######  Theorem 17.

$\mathsf{WL}_{1}\npreceq w_{*}^{(2)}$.

The proof requires a substantial extension of the approach in [32] to separate
various $\mathsf{WL}_{1}$\- and $\operatorname{\mathsf{WM}}$-based concepts.

#### Construction.

Suppose that we have a graph $A$ with $m$ designated vertices
$a_{1},\ldots,\allowbreak a_{m}$ and a graph $B$ with $m$ designated vertices
$b_{1},\ldots,b_{m}$, which will be referred to as _port vertices_. In each of
the graphs, the port vertices are colored by different colors. Specifically,
$a_{i}$ and $b_{i}$ are colored by color $i$. The resulting partially colored
graphs are denoted by $A^{\prime}$ and $B^{\prime}$. We construct a graph
$G(A^{\prime},B^{\prime})$ with no colored vertices as follows.
$G(A^{\prime},B^{\prime})$ consists of the vertex-disjoint union of $A$ and
$B$ and a number of new vertices of two sorts, namely _connecting_ and
_pendant vertices_. For each $i$, there is a connecting vertex $c_{i}$
adjacent to $a_{i}$ and $b_{i}$. Moreover, for each $i$ there are $i$ pendant
vertices $p_{i,1},\ldots,p_{i,i}$ of degree $1$ all adjacent to $c_{i}$. An
example of the construction is shown in Figure 2.

$A^{\prime}$$B^{\prime}$$\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!G(A^{\prime},B^{\prime})\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!$
Figure 2: Construction of $G(A^{\prime},B^{\prime})$.

#### The main lemma.

The crux of the proof is the following lemma, whose proof is postponed to
Subsection 6.4. Recall that a _strongly regular graph_ with parameters
$(n,d,\lambda,\mu)$ is an $n$-vertex $d$-regular graph where every two
adjacent vertices have $\lambda$ common neighbors, and every two non-adjacent
vertices have $\mu$ common neighbors. Extending the notation used in Section
4.2, for a graph $G$ we set
$\mathit{WL}_{1}^{r}(G)=\left\\{\\!\\!\left\\{\mathit{WL}_{1}^{r}(G,x)\right\\}\\!\\!\right\\}_{x\in
V(G)}$.

######  Lemma 18.

Let $A$ and $B$ be strongly regular graphs with the same parameters ($A\cong
B$ is not excluded). Let $A^{\prime}$ and $B^{\prime}$ be their vertex-
disjoint partially colored versions, with possibly some vertices remaining
uncolored. Assume that
$\mathit{WL}_{1}^{0}(A^{\prime})=\mathit{WL}_{1}^{0}(B^{\prime})$, which means
the the multisets of the initial colors occurring in $A^{\prime}$ and
$B^{\prime}$ are equal and, therefore, we can construct the uncolored graph
$G(A^{\prime},B^{\prime})$. Let $G=G(A^{\prime},B^{\prime})$. Consider also
$H=G(A^{\prime},A^{\prime})$ constructed from two vertex-disjoint copies of
$A^{\prime}$.

  1. 1.

If $\mathit{WL}_{1}(A^{\prime})\neq\mathit{WL}_{1}(B^{\prime})$, then
$\mathit{WL}_{1}(G)\neq\mathit{WL}_{1}(H)$. In words: if color refinement
distinguishes $A^{\prime}$ and $B^{\prime}$, then it distinguishes also $G$
and $H$.

  2. 2.

If $\mathit{WL}_{1}^{r}(A^{\prime})=\mathit{WL}_{1}^{r}(B^{\prime})$ for
$r\geq 1$ (i.e., $r$ rounds of color refinement are not enough for
distinguishing $A^{\prime}$ and $B^{\prime}$), then
$w_{*}^{(r-1)}(G)=w_{*}^{(r-1)}(H)$.

#### The rest of the proof.

We can separate $\mathsf{WL}_{1}$ and $w_{*}^{(2)}$ by finding partially
colored strongly regular graphs $A^{\prime}$ and $B^{\prime}$ as in Lemma 18
with $r=3$. Let $\mathrm{SRG}(n,d,\lambda,\mu)$ denote the set of strongly
regular graphs with parameters $(n,d,\lambda,\mu)$. Two suitable colorings
$A^{\prime}$ and $B^{\prime}$ exist for a graph in the set SRG(25,12,5,6) of
_Paulus graphs_ , namely for the graph $P_{25.12}$ in Brouwer’s collection
[5]. We specify these colorings in Appendix B. They were found by computer
search using the small Lua package TCSLibLua [1].

Note that $P_{25.12}$ is one of the two latin square graphs in SRG(25,12,5,6).
The other latin square graphs in SRG(25,12,5,6) is $P_{25.15}$, which is the
Paley graph on 25 vertices. This is the only vertex-transitive graph in this
family. Curiously, it is not suitable for our purposes. Moreover, it seems
that strongly regular graphs with less than 25 vertices do not admit
appropriate colorings even for $r=2$.

###  6.3 Separation of the $P_{*}^{(r)}$ hierarchy from $\mathsf{WL}_{2}$

######  Lemma 19.

Let $A$ and $B$ be strongly regular graphs with the same parameters ($A=B$ is
not excluded). Let $A^{\prime}$ and $B^{\prime}$ be their single vertex
individualized versions. Let $G=G(A^{\prime},B^{\prime})$ and
$H=G(A^{\prime},A^{\prime})$.

  1. 1.

$w_{*}^{(r)}(G)=w_{*}^{(r)}(H)$ for all $r$.

  2. 2.

If $\mathit{WL}_{2}(A^{\prime})\neq\mathit{WL}_{2}(B^{\prime})$, then
$\mathit{WL}_{2}(G)\neq\mathit{WL}_{2}(H)$.

###### Proof.

For Part 1, note that
$\mathsf{WL}_{1}(A^{\prime})=\mathsf{WL}_{1}(B^{\prime})$. Indeed, the
distinguishability of $A^{\prime}$ and $B^{\prime}$ by 1-WL would imply the
distinguishability of $A$ and $B$ by 2-WL, contradicting the assumption that
these strongly regular graphs have the same parameters. Thus,
$\mathit{WL}_{1}^{r}(A^{\prime})=\mathit{WL}_{1}^{r}(B^{\prime})$ for all
integers $r\geq 1$, and we can apply the second part of Lemma 18. Part 2 is
easy. ∎

######  Theorem 20.

$\mathsf{WL}_{2}\npreceq P_{*}^{(r)}$ for any $r$ or, equivalently,
$\mathsf{WL}_{2}\npreceq w_{*}^{(\bullet)}$.

###### Proof.

We apply Lemma 19, where $A$ is the Shrikhande graph and $B$ the $4\times 4$
rook’s graph, both are strongly regular with parameters $(16,6,2,2)$ and are
vertex-transitive. Therefore, $A^{\prime}$ and $B^{\prime}$ are uniquely
defined. The neighborhood of the individualized vertex induces $C_{6}$ in the
Shrikhande graph and $2C_{3}$ in the $4\times 4$ rook’s graph. Therefore,
$\mathsf{WL}_{2}(A^{\prime})\neq\mathsf{WL}_{2}(B^{\prime})$. ∎

######  Open Problem 21.

We leave open the question whether the hierarchy

$w_{*}^{(1)}\preceq w_{*}^{(2)}\preceq w_{*}^{(3)}\preceq
w_{*}^{(4)}\preceq\cdots\preceq w_{*}^{(\bullet)}$ (30)

is strict or at least does not collapse to some level. While we know that each
$w_{*}^{(r)}$ is strictly weaker than $\mathsf{WL}_{2}$, it remains open
whether $w_{*}^{(r)}$ can be stronger than $\mathsf{WL}_{1}$ for some large
$r$. A negative answer will follow from our Main Lemma (Lemma 18) if there is
an infinite sequence of partially colored strongly regular graphs
$A^{\prime}_{r}$ and $B^{\prime}_{r}$ for $r=1,2,3\ldots$, where the
underlying graphs are equal or have the same parameters, such that
$A^{\prime}_{r}$ and $B^{\prime}_{r}$ are distinguished by 1-WL, but requiring
at least $r$ refinement rounds.

Suppose that strongly regular graphs $A$ and $B$ have the same parameters and
their partially colored versions$A^{\prime}$ and $B^{\prime}$ are
distinguished by 1-WL exactly in the $(r+1)$-th round. By Lemma 18,
$G(A^{\prime},B^{\prime})$ and $G(A^{\prime},A^{\prime})$ are
$w_{*}^{(r-1)}$-equivalent and, therefore, this pair of graphs is a good
candidate for separation of $w_{*}^{(r-1)}$ from $w_{*}^{(r)}$. This approach
works indeed pretty well.

######  Theorem 22.

The hierarchy (30) is strict up to the 4-th level, that is, the first three
relations in (30) are strict.

###### Proof.

For each $r=1,2,3$, we provide a pair of graphs $G_{r}$ and $H_{r}$ such that

$w_{*}^{(r)}(G_{r})=w_{*}^{(r)}(H_{r})$ (31)

while

$w_{*}^{(r+1)}(G_{r})\neq w_{*}^{(r+1)}(H_{r}).$ (32)

For $r=1$ and $r=2$, these graphs are obtained by using our construction, that
is, $G_{r}=G(A^{\prime}_{r},B^{\prime}_{r})$ and
$H_{r}=G(A^{\prime}_{r},A^{\prime}_{r})$ for suitable partially colored
strongly regular graphs $A^{\prime}_{r}$ and $B^{\prime}_{r}$. For both $r=1$
and $r=2$, $A^{\prime}_{r}$ and $B^{\prime}_{r}$ are colored versions of the
Paulus graph $P_{25.12}$ that was already used in the proof of Theorem 17.
$A^{\prime}_{2}$ and $B^{\prime}_{2}$ are exactly as in the proof of Theorem
17. $A^{\prime}_{1}$ and $B^{\prime}_{1}$ are obtained by using 3 colors,
specifically, by setting $a_{i}=(1,i)$ and $b_{i}=(i,1)$ for $i=1,2,3$. Here
we use the representation of $P_{25.12}$ as a latin square graph; see Appendix
B for details. While we already know that $A^{\prime}_{2}$ and
$B^{\prime}_{2}$ satisfy the assumptions of Lemma 18 for $r=3$, a direct
computation shows that $A^{\prime}_{1}$ and $B^{\prime}_{1}$ satisfy the
assumptions of Lemma 18 for $r=2$. Thus, Equality (31) follows from Lemma 18
in both cases of $r=1$ and $r=2$. Inequality (32) is in both cases verified
directly by computation. The computations are done by using the Lua package
TCSLibLua [1]. More specifically, $w(x,y)$ is computed using the method
`graphs::walkMatrix` with $e_{y}$ as `filter` for each vertex $y$; the graph
invariant $w_{*}^{(r)}$ is computed using the `genref` module.

For $r=3$, we use an extension of the construction of
$G(A^{\prime},B^{\prime})$, allowing color classes of size larger than one.
Specifically, for each color $i$ we now allow possibly more than one vertex
$a_{i}^{1},a_{i}^{2},\ldots$ colored by $i$ in $A^{\prime}$ and the same
number of vertices $b_{i}^{1},b_{i}^{2},\ldots$ colored by $i$ in
$B^{\prime}$. The connecting vertex $c_{i}$ is adjacent to $a_{i}^{j}$ and
$b_{i}^{j}$ for all $j$. Since we do not prove an analog of Lemma 18 for the
generalized construction, we will need to verify Equality (31) und Inequality
(32) by computation. $A^{\prime}_{3}$ and $B^{\prime}_{3}$ are colored
versions of another Paulus graph $P_{25.02}$. This graph and its complement
are the only two graphs in SRG(25,12,5,6) with trivial automorphism group. We
work with a particular labeled version of $P_{25.02}$, namely with a graph
`X}rU\adeSetTjKWNJEYNR]PLjPBgUGVTkK^YKbipMcxbk‘{DlXF` in graph6 notation.
Assuming vertex names $1,\dots,25$ (the graph6 notation defines an order on
the vertices), we color the vertices $2$ and $6$ in $A^{\prime}$ and $3$ and
$22$ in $B^{\prime}$ all with the same color; the other vertices are
uncolored. $G_{3}=G(A^{\prime}_{3},B^{\prime}_{3})$ and
$H_{3}=G(A^{\prime}_{3},A^{\prime}_{3})$ are obtained by using the generalized
construction. Equality (31) und Inequality (32) are verified with help of the
Lua package TCSLibLua [1]. ∎

In fact, the same approach can also be used to strengthen Theorem 17.

######  Theorem 23.

$\mathsf{WL}_{1}\npreceq w_{*}^{(3)}$.

###### Proof.

We have to exhibit two graphs $G$ and $H$ such that
$w_{*}^{(3)}(G)=w_{*}^{(3)}(H)$ while
$\mathsf{WL}_{1}(G)\neq\mathsf{WL}_{1}(H)$. For this purpose, we take
$G=G_{3}$ and $H=H_{3}$ as in the preceding proof and verify that both
conditions are true by using the Lua package TCSLibLua [1]. ∎

###  6.4 Proof of Lemma 18

1\. Though the colors of port vertices in $A^{\prime}$ and $B^{\prime}$ are
removed after these graphs are combined into $G$ and $H$, these colors are
simulated by CR due to the adjacency to the respective connection vertex
$c_{i}$. Recall that $c_{i}$ bears the information about the color $i$ as it
is adjacent to exactly $i$ pendant vertices. Since the vertex-colored graphs
$A^{\prime}$ and $B^{\prime}$ are distinguishable by CR, every vertex in the
$B^{\prime}$-part of $G$ will eventually receive a color not occurring in $H$.

2\. Recall that we write $A$ and $I$ to denote the adjacency and the equality
relations. We will use the following well-known property of strongly regular
graphs.

Claim A.  Let $w_{k}^{X}(x,y)$ be the number of $k$-walks from a vertex $x$ to
a vertex $y$ in a strongly regular graph $X$. The walk count $w_{k}^{X}(x,y)$
is a function of $k$, the predicate values $I(x,y)$ and $A(x,y)$, and the
parameters of $X$ (and otherwise does not depend on a particular choice of $x$
and $y$).

In Claims 6.4 and 6.4 below we establish some crucial properties of our
construction of $G(A^{\prime},B^{\prime})$. For every vertex $x$ of
$G(A^{\prime},B^{\prime})$ we define its type $\tau(x)$ as follows. If $x$ is
in the $A$-part, then $\tau(x)=C_{1}^{A^{\prime}}(x)$, i.e., the color of $x$
after performing the first round of CR in the vertex-colored graph
$A^{\prime}$. Similarly, $\tau(x)=C_{1}^{B^{\prime}}(x)$ if $x$ belongs to the
$B$-part. In order to define the types of connecting and pendant vertices we
use special symbols $\mathfrak{c}$ and $\mathfrak{p}$ and set
$\tau(c_{i})=(\mathfrak{c},\tau(a_{i}))$ and
$\tau(p_{i,h})=(\mathfrak{p},\tau(a_{i}))$ for all $h\leq i$. We define a
binary relation $D$ on the vertex set of $G(A^{\prime},B^{\prime})$ by setting
$D(x,y)=1$ exactly when $x$ and $y$ are both in the $A$-part or both in the
$B$-part. Finally, we define a coloring $\eta$ of vertex pairs in
$G(A^{\prime},B^{\prime})$ by

$\eta(x,y)=\left(\tau(x),D(x,y),I(x,y),A(x,y),\tau(y)\right).$

We also set $\sigma(A^{\prime})=(\tau(a_{1}),\ldots,\tau(a_{m}))$ and denote
the tuple of the four parameters of $A$ (hence also of $B$) by $\pi(A)$.

Claim B.  Suppose that $\tau(a_{i})=\tau(b_{i})$ for all $i\leq m$ (or,
equivalently, that the mapping $a_{i}\mapsto b_{i}$ is a partial isomorphism
between the colored graphs $A^{\prime}$ and $B^{\prime}$). For vertices $x$
and $y$ of $G(A^{\prime},B^{\prime})$, the sequence $w_{*}(x,y)$ is solely
determined by $\eta(x,y)$, $\sigma(A^{\prime})$, and $\pi(A)$.

Proof of Claim B.  By induction on $k$, we prove that $w_{k}(x,y)$ is
determined by $\eta(x,y)$, $\sigma(A^{\prime})$, and $\pi(A)$. The base case
of $k=0$ is trivial. For the induction step, suppose that $k\geq 1$.

Case 1: $D(x,y)=1$. Assume that $x$ is in the $A$-part; the case of $x\in
V(B)$ is similar.

Subcase 1-a: $x=y$. We split the set of closed $k$-walks from $x$ to itself in
$G(A^{\prime},B^{\prime})$ into two classes: those remaining all the time in
$A$ and those leaving $A$ at some point. For the first type of walks, we use
Claim 6.4, which implies that their number, i.e., $w_{k}^{A}(x,x)$, depends
only on $k$ and $\pi(A)$ and is independent of $x$.

Let $w_{k}^{\triangledown}(x,x)$ denote the number of closed walks from $x$
leaving $A$ at some point. Since a walk leaves $A$ only via one of the $m$
port vertices $a_{i}$ and visits the connecting vertex $c_{i}$ immediately
after this, we have

$w_{k}^{\triangledown}(x,x)=\sum_{i=1}^{m}\sum_{s=0}^{k-2}\sum_{t=1}^{k-1-s}w_{s}^{A}(x,a_{i})w_{t}(c_{i},x).$

By Claim 6.4, $w_{s}^{A}(x,a_{i})$ is for each $s$ determined by $\pi(A)$ and
the pair of boolean values $I(x,a_{i})$ and $A(x,a_{i})$. Since the last pair
is determined by $C_{1}^{A^{\prime}}(x)$, the whole sequence
$w_{s}^{A}(x,a_{1}),\ldots,w_{s}^{A}(x,a_{m})$ is determined by
$\tau(x)=C_{1}^{A^{\prime}}(x)$. The sequence
$w_{t}(c_{1},x),\ldots,w_{t}(c_{m},x)$ is determined due to the knowledge of
$\tau(x)$ and $\sigma(A^{\prime})$ by the induction hypothesis (note that
$\eta(c_{i},x)$ for all $i$ are obtainable from $\tau(x)$ and
$\sigma(A^{\prime})$).

We conclude that the count
$w_{k}(x,x)=w_{k}^{A}(x,y)+w_{k}^{\triangledown}(x,x)$ is determined by
$\sigma(A^{\prime})$, $\pi(A)$, and $\tau(x)$, where $\tau(x)$ is a part of
$\eta(x,x)$.

We define Subcase 1-b by the condition $A(x,y)=1$ and Subcase 1-c by
$A(x,y)=I(x,y)=0$. The analysis of both these subcases is completely similar
to Subcase 1-a.

Case 2: $D(x,y)=0$.

Subcase 2-a: $x\in V(A)$ and $y\in V(B)$. (The case $x\in V(B),y\in V(A)$ is
similar.) Since a walk from $x$ to $y$ must leave $A$ somewhere, we have

$w_{k}(x,y)=\sum_{i=1}^{m}\sum_{s=0}^{k-2}\sum_{t=1}^{k-1-s}w_{s}^{A}(x,a_{i})w_{t}(c_{i},y),$

which enables the same analysis as in Subcase 1-a.

Subcase 2-b: $x\in V(A)$ while $y=c_{j}$ or $y=p_{j,h}$. (If $x\in V(B)$, the
analysis is virtually the same.) By the same reasons as in Subcase 2-a, we
have

$w_{k}(x,y)=\sum_{i=1}^{m}\sum_{s=0}^{k-1}\sum_{t=0}^{k-1-s}w_{s}^{A}(x,a_{i})w_{t}(c_{i},y),$

which makes the above argument applicable.

Subcase 2-c: $x=c_{j}$ and $y=c_{j^{\prime}}$. The induction step is in this
case based on the equality

$w_{k}(c_{j},c_{j^{\prime}})=w_{k-1}(a_{j},c_{j^{\prime}})+w_{k-1}(b_{j},c_{j^{\prime}})+\sum_{h=1}^{j}w_{k-1}(p_{j,h},c_{j^{\prime}}).$

Subcase 2-d: $x=p_{j,h}$ and $y=c_{j^{\prime}}$. For the induction step, note
that $w_{k}(p_{j,h},c_{j^{\prime}})=w_{k-1}(c_{j},c_{j^{\prime}})$.

Subcase 2-e: $x=p_{j,h}$ and $y=p_{j^{\prime},h^{\prime}}$. Quite similarly to
Subcase 2-d, we use the equality
$w_{k}(p_{j,h},p_{j^{\prime},h^{\prime}})=w_{k-1}(c_{j},p_{j^{\prime},h^{\prime}})$.
$\,\triangleleft$

To facilitate the notation, set $\omega(x,y)=w_{*}(x,y)$. For $r\geq 0$, let
$\omega_{r}$ be the vertex coloring as defined in (2).

Claim C.  Suppose that $\tau(a_{i})=\tau(b_{i})$ for all $i\leq m$. For a
vertex $x$ of $G(A^{\prime},B^{\prime})$, the color $\omega_{r}(x)$ depends on
$\sigma(A^{\prime})$ and $\pi(A)$. Once these are fixed, $\omega_{r}(x)$ is
determined by the pair of multisets
$M_{A,r}=\left\\{\\!\\!\left\\{C^{A^{\prime}}_{r}(y)\right\\}\\!\\!\right\\}_{y\in
V(A)}$ and
$M_{B,r}=\left\\{\\!\\!\left\\{C^{B^{\prime}}_{r}(y)\right\\}\\!\\!\right\\}_{y\in
V(B)}$ and

  * •

by the color $C^{A^{\prime}}_{r+1}(x)$ if $x$ is in the $A$-part,

  * •

by the color $C^{B^{\prime}}_{r+1}(x)$ if $x$ is in the $B$-part,

  * •

by the color $C^{A^{\prime}}_{r+1}(a_{i})$ if $x=c_{i}$ or $x=p_{i,h}$.

Proof of Claim C.  We proceed by induction on $r$. In the base case we have
$r=0$. If $x\in V(A)\cup V(B)$, then either $C^{A^{\prime}}_{1}(x)$ or
$C^{B^{\prime}}_{1}(x)$ determines $\omega_{0}(x)=w_{*}(x,x)$, by Claim 6.4.
If $x=c_{i}$ or $x=p_{i,h}$, then $C^{A^{\prime}}_{1}(a_{i})$ determines
$\omega_{0}(x)$, again by Claim 6.4.

For the induction step, suppose that $r\geq 1$ and recall that

$\omega_{r}(x)=\left(\omega_{r-1}(x),\left\\{\\!\\!\left\\{(\omega(x,y),\omega_{r-1}(y))\right\\}\\!\\!\right\\}_{y}\right).$

Case 1: $x\in V(A)$. (The case of $x\in V(B)$ is similar.) By the induction
hypothesis, $\omega_{r-1}(x)$ is determined by $M_{A,r-1}$, $M_{B,r-1}$, and
$C^{A^{\prime}}_{r}(x)$, which are obviously obtainable from $M_{A,r}$,
$M_{B,r}$, and $C^{A^{\prime}}_{r+1}(x)$. It remains to show that

$\left\\{\\!\\!\left\\{(\omega(x,y),\omega_{r-1}(y))\right\\}\\!\\!\right\\}_{y}$
(33)

is determined as well. To this end, we split this multiset into several parts.

For $y=x$, the corresponding element $(\omega_{0}(x),\omega_{r-1}(x))$ of the
multiset is determined as we have already shown.

Consider the restriction of (33) to $y\in V(A)\setminus\\{x\\}$. Along with
$M_{A,r}$, the color $C^{A^{\prime}}_{r+1}(x)$ determines the multiset
$\left\\{\\!\\!\left\\{(A(x,y),C^{A^{\prime}}_{r}(y))\right\\}\\!\\!\right\\}_{y\in
V(A)\setminus\\{x\\}}$. As easily seen from the definition of $\eta(x,y)$, a
pair $(A(x,y),C^{A^{\prime}}_{r}(y))$ yields the pair
$(\eta(x,y),C^{A^{\prime}}_{r}(y))$. By Claim 6.4, $\eta(x,y)$ determines
$\omega(x,y)$. By the induction hypothesis, $C^{A^{\prime}}_{r}(y)$ determines
$\omega_{r-1}(y)$ (by taking into account that $M_{A,r-1}$ and $M_{B,r-1}$ are
obtainable from $M_{A,r}$ and $M_{B,r}$). Thus, we do obtain (33) over $y\in
V(A)\setminus\\{x\\}$.

Next, consider the restriction of (33) to $y\in V(B)$. The multiset $M_{B,r}$
readily provides us with the multiset
$\left\\{\\!\\!\left\\{(\eta(x,y),C^{B^{\prime}}_{r}(y))\right\\}\\!\\!\right\\}_{y\in
V(B)}$. Similarly to the above, this gives us (33) over $y\in V(B)$ by Claim
6.4 and the induction hypothesis.

Now, we have to reconstruct the restriction of (33) to $y$ ranging over all
connecting vertices, that is, the multiset
$\left\\{\\!\\!\left\\{(\omega(x,c_{i}),\omega_{r-1}(c_{i}))\right\\}\\!\\!\right\\}_{i=1}^{m}$.
The multiset $M_{A,r}$ gives us the sequence
$\left(C^{A^{\prime}}_{r}(a_{1}),\ldots,C^{A^{\prime}}_{r}(a_{m})\right)$,
which also determines
$\left(C^{A^{\prime}}_{1}(a_{1}),\ldots,C^{A^{\prime}}_{1}(a_{m})\right)$ (the
last sequence is, in fact, nothing else as $\sigma(A^{\prime})$ and is
supposed to be prespecified). As a result, for each $i$ we obtain
$\left(\eta(x,c_{i}),C^{A^{\prime}}_{r}(c_{i})\right)$. By Claim 6.4 and the
induction hypothesis, this yields $(\omega(x,c_{i}),\omega_{r-1}(c_{i}))$, as
needed.

The restriction of (33) to pendant vertices is reconstructible in the same
way. Summing up, we see that the multiset (33) for $y$ ranging over the vertex
set of $G(A^{\prime},B^{\prime})$ is determined.

Case 2: $x=c_{i}$ for some $i\leq m$. Similarly to the preceding case,
$\omega_{r-1}(c_{i})$ is determined by the induction hypothesis and we only
have to consider the multiset
$\left\\{\\!\\!\left\\{(\omega(c_{i},y),\omega_{r-1}(y))\right\\}\\!\\!\right\\}_{y}$.
We again split this multiset into several parts and reconstruct each of them
separately.

The restriction to $y\in V(A)\cup V(B)$ is reconstructable because $M_{A,r}$
and $M_{B,r}$ give us the multisets
$\left\\{\\!\\!\left\\{(\eta(c_{i},y),C^{A^{\prime}}_{r}(y))\right\\}\\!\\!\right\\}_{y\in
V(A)}$ and
$\left\\{\\!\\!\left\\{(\eta(c_{i},y),C^{B^{\prime}}_{r}(y))\right\\}\\!\\!\right\\}_{y\in
V(B)}$, which allows using Claim 6.4 and the induction hypothesis.

The restriction to the connection vertices, i.e.,
$\left\\{\\!\\!\left\\{(\omega(c_{i},c_{j}),\omega_{r-1}(c_{j}))\right\\}\\!\\!\right\\}_{j=1}^{m}$
is reconstructible like in Case 1 because we have the sequences
$\left(C^{A^{\prime}}_{r}(a_{1}),\ldots,C^{A^{\prime}}_{r}(a_{m})\right)$, and
$\left(C^{A^{\prime}}_{1}(a_{1}),\ldots,C^{A^{\prime}}_{1}(a_{m})\right)$. The
restriction to the pendant vertices is reconstructible by similar reasons.

Case 3: $x=p_{i,h}$ for some $i\leq m$ and $h\leq i$. This case is similar to
Case 2. $\,\triangleleft$

To complete the proof of Lemma 18, consider $G=G(A^{\prime},B^{\prime})$ and
$H=G(A^{\prime},A^{\prime})$ for partially colored strongly regular graphs
$A^{\prime}$ and $B^{\prime}$ satisfying the conditions of the lemma. In
particular,

$\mathit{WL}_{1}^{r}(A^{\prime})=\mathit{WL}_{1}^{r}(B^{\prime}),$ (34)

where $r\geq 1$. Note that the last condition makes Claim 6.4 applicable.
Another consequence of (34) is that the multiset $M_{A,r}$, as well as
$M_{B,r}$, is the same for $G$ and $H$. In particular, there is a bijection
$f:V(A)\rightarrow V(B)$ such that

$C^{A^{\prime}}_{r}(x)=C^{B^{\prime}}_{r}(f(x)).$ (35)

Define a bijection $F:V(H)\rightarrow V(G)$ as the identity on the first
$A$-part of $H$ (which we identify with the $A$-part of $G$) and as $f$
mapping the second $A$-part of $H$ to the $B$-part of $G$. Furthermore, $F$
matches the connecting vertices of the same color as well as the corresponding
pendant vertices. By taking into account (35) and the fact that $G$ and $H$
share the same $M_{A,r}$ and $M_{B,r}$, Claim 6.4 readily implies that
$\omega_{r-1}(x)=\omega_{r-1}(F(x))$ for all vertices $x$ of $H$. This gives
us the desired equality $\omega^{(r-1)}(G)=\omega^{(r-1)}(H)$.

## References

  * [1] Tcsliblua.  URL: https://gitlab.com/tcslib/tcsliblua.
  * [2] L. Babai.  Graph isomorphism in quasipolynomial time.  In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC’16), pages 684–697, 2016.  doi:10.1145/2897518.2897542.
  * [3] L. Babai, P. Erdős, and S. M. Selkow.  Random graph isomorphism.  SIAM Journal on Computing, 9(3):628–635, 1980.  doi:10.1137/0209047.
  * [4] A. R. Barghi and I. Ponomarenko.  Non-isomorphic graphs with cospectral symmetric powers.  Electron. J. Comb., 16(1), 2009.  doi:10.37236/209.
  * [5] A. E. Brouwer.  Paulus-Rozenfeld graphs.  URL: https://www.win.tue.nl/~aeb/drg/graphs/Paulus.html.
  * [6] J. Cai, M. Fürer, and N. Immerman.  An optimal lower bound on the number of variables for graph identifications.  Combinatorica, 12(4):389–410, 1992.  doi:10.1007/BF01305232.
  * [7] G. Chen and I. Ponomarenko.  Coherent configurations.  Wuhan: Central China Normal University Press, 2019.
  * [8] D. Cvetković.  The main part of the spectrum, divisors and switching of graphs.  Publ. Inst. Math., Nouv. Sér., 23:31–38, 1978.  URL: http://elib.mi.sanu.ac.rs/files/journals/publ/43/6.pdf.
  * [9] D. Cvetković and M. Lepović.  Cospectral graphs with the same angles and with a minimal number of vertices.  Publ. Elektroteh. Fak., Univ. Beogr., Ser. Mat., 8:88–102, 1997\.  URL: http://www.jstor.org/stable/43666387.
  * [10] D. Cvetković, P. Rowlinson, and S. Simić.  An introduction to the theory of graph spectra, volume 75 of Lond. Math. Soc. Stud. Texts.  Cambridge: Cambridge University Press, 2010.  doi:10.1017/CBO9780511801518.
  * [11] D. Cvetković, P. Rowlinson, and S. Simic.  Eigenspaces of Graphs.  Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1997.  doi:10.1017/CBO9781139086547.
  * [12] D. Cvetković, P. Rowlinson, and S. Simić.  A study of eigenspaces of graphs.  Linear Algebra and its Applications, 182:45–66, 1993.  doi:10.1016/0024-3795(93)90491-6.
  * [13] Z. Dvořák.  On recognizing graphs by numbers of homomorphisms.  Journal of Graph Theory, 64(4):330–342, 2010.  doi:10.1002/jgt.20461.
  * [14] M. Fürer.  On the power of combinatorial and spectral invariants.  Linear Algebra and its Applications, 432(9):2373–2380, 2010.  doi:10.1016/j.laa.2009.07.019.
  * [15] D. Garijo, A. J. Goodall, and J. Nesetril.  Distinguishing graphs by their left and right homomorphism profiles.  Eur. J. Comb., 32(7):1025–1053, 2011.  doi:10.1016/j.ejc.2011.03.012.
  * [16] W. H. Haemers and E. Spence.  Enumeration of cospectral graphs.  European Journal of Combinatorics, 25(2):199–211, 2004.  doi:10.1016/S0195-6698(03)00100-8.
  * [17] S. Hoory, N. Linial, and A. Widgerson.  Expander graphs and their applications.  Bull. Am. Math. Soc., New Ser., 43(4):439–561, 2006.  doi:10.1090/S0273-0979-06-01126-8.
  * [18] C. R. Johnson and M. Newman.  A note on cospectral graphs.  Journal of Combinatorial Theory, Series B, 28(1):96–103, 1980.  doi:10.1016/0095-8956(80)90058-1.
  * [19] F. Liu and J. Siemons.  Unlocking the walk matrix of a graph.  J. Algebr. Comb., 55(3):663–690, 2022.  doi:10.1007/s10801-021-01065-3.
  * [20] B. D. McKay.  Graphs.  URL: https://users.cecs.anu.edu.au/~bdm/data/graphs.html.
  * [21] B. Mohar and S. Poljak.  Eigenvalues in combinatorial optimization.  In Combinatorial and graph-theoretical problems in linear algebra, pages 107–151. New York: Springer-Verlag, 1993.  doi:10.1007/978-1-4613-8354-3.
  * [22] S. O’Rourke and B. Touri.  On a conjecture of Godsil concerning controllable random graphs.  SIAM J. Control. Optim., 54(6):3347–3378, 2016.  doi:10.1137/15M1049622.
  * [23] A. J. L. Paulus.  Conference matrices and graphs of order 26.  Technical report, Eindhoven University of Technology, 1973.  URL: https://research.tue.nl/files/4424819/252855.pdf.
  * [24] D. L. Powers and M. M. Sulaiman.  The walk partition and colorations of a graph.  Linear Algebra Appl., 48:145–159, 1982.  doi:10.1016/0024-3795(82)90104-5.
  * [25] G. Rattan and T. Seppelt.  Weisfeiler-Leman and graph spectra.  In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA’23), pages 2268–2285. SIAM, 2023.  doi:10.1137/1.9781611977554.ch87.
  * [26] M. Z. Rozenfeld.  The construction and properties of certain classes of strongly regular graphs.  Uspehi Mat. Nauk, 28:197–198, 1973.
  * [27] Sirolf.  Characterization of $k$-walk-equivalent graphs, 2018.  URL: https://mathoverflow.net/questions/304106/characterization-of-k-walk-equivalent-graphs.
  * [28] E. Spence.  Strongly regular graphs on at most 64 vertices.  URL: http://www.maths.gla.ac.uk/~es/srgraphs.html.
  * [29] T. Tao and V. Vu.  Random matrices have simple spectrum.  Combinatorica, 37(3):539–553, 2017.  doi:10.1007/s00493-016-3363-4.
  * [30] E. van Dam, W. Haemers, and J. Koolen.  Cospectral graphs and the generalized adjacency matrix.  Linear Algebra and its Applications, 423(1):33–41, 2007.  doi:10.1016/j.laa.2006.07.017.
  * [31] E. R. van Dam and W. H. Haemers.  Which graphs are determined by their spectrum?  Linear Algebra and its Applications, 373:241–272, 2003.  doi:10.1016/S0024-3795(03)00483-X.
  * [32] O. Verbitsky and M. Zhukovskii.  Canonization of a random graph by two matrix-vector multiplications.  In 31st Annual European Symposium on Algorithms (ESA 2023), volume 274 of Leibniz International Proceedings in Informatics (LIPIcs), pages 100:1–100:13, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.ESA.2023.100.
  * [33] B. Weisfeiler and A. Leman.  The reduction of a graph to canonical form and the algebra which appears therein.  NTI, Ser. 2, 9:12–16, 1968.  English translation is available at https://www.iti.zcu.cz/wl2018/pdf/wl_paper_translation.pdf.

##  Appendix A
$\operatorname{\mathsf{EA}}\nrightarrow\operatorname{\mathsf{main-EA}}$

The first ten columns of the walk matrices for the trees $T$ and $T^{\prime}$
found in [9] are (rows are sorted lexicographically).

     1  1  2   3   8   14   39   76   208   431
     1  1  2   3   8   14   39   76   208   431
     1  1  2   3   8   14   39   76   208   431
     1  1  3   6  14   35   76  200   431  1136
     1  1  3   6  14   35   76  200   431  1136
     1  1  3   7  18   45  107  268   623  1551
     1  1  4   8  23   48  130  279   736  1612
     1  1  4   8  23   48  130  279   736  1612
     1  2  3   8  14   39   76  208   431  1152
     1  2  3   8  14   39   76  208   431  1152
     1  2  3   8  14   39   76  208   431  1152
     1  2  6  11  31   62  169  355   944  2043
     1  2  6  11  31   62  169  355   944  2043
     1  2  6  11  31   62  169  355   944  2043
     1  2  7  15  41   93  237  547  1359  3163
     1  3  6  14  35   76  200  431  1136  2474
     1  3  7  18  45  107  268  623  1551  3594
     1  4  8  23  48  130  279  736  1612  4175
     1  4  8  23  48  130  279  736  1612  4175

and

     1  1  2   3    8   14   41  76  224  429
     1  1  2   3    8   14   41  76  224  429
     1  1  2   3    8   14   41  76  224  429
     1  1  3   6   14   33   76 184  433 1040
     1  1  3   6   14   33   76 184  433 1040
     1  1  3   7   18   43  109 252  641 1453
     1  1  4   8   21   48  118 281  672 1636
     1  1  4   8   21   48  118 281  672 1636
     1  2  3   8   14   41   76 224  429 1248
     1  2  3   8   14   41   76 224  429 1248
     1  2  3   8   14   41   76 224  429 1248
     1  2  6  11   33   62  183 353 1024 2017
     1  2  6  11   33   62  183 353 1024 2017
     1  2  6  11   33   62  183 353 1024 2017
     1  2  7  15   43   91  251 529 1441 3041
     1  3  6  14   33   76  184 433 1040 2502
     1  3  7  18   43  109  252 641 1453 3718
     1  4  8  21   48  118  281 672 1636 3837
     1  4  8  25   48  142  277 800 1588 4513

The total number of walks of length 9 is 35506 for $T$ and 35498 for
$T^{\prime}$. By Proposition 12, $T$ and $T^{\prime}$ are not
$\operatorname{\mathsf{main-EA}}$-equivalent.

##  Appendix B Colorings of a SRG whose distinction requires 3 rounds of 1WL

As $X=Y$, we take the graph in SRG(25,12,5,6) with graph6-code

    X~}UH\VJ{YIpgrKNhF|GqQrD‘a{dEwwh~CgsWdUHiKJbLHVacg~

This is the Paulus graph $P_{25.12}$ in [5] first described by [23] and [26].
It can also be found as the first among the SRG(25,12,5,6) graphs in McKay’s
collection of graphs [20] and the 14th SRG(25,12,5,6) graph from Spence’s
collection [28]. The following latin square $L$ can be used to construct $X$:

$L=\left[\begin{matrix}1&2&3&4&5\\\ 4&1&5&2&3\\\ 5&4&1&3&2\\\ 3&5&2&1&4\\\
2&3&4&5&1\end{matrix}\right]$

Here $X=(V_{X},E_{X})$, where $V_{X}=\left\\{1,2,3,4,5\right\\}^{2}$ and

$E_{X}=\\{\left\\{(i,j),(i^{\prime},j^{\prime})\right\\}\,:\,\begin{array}[]{@{}l@{}}i=i^{\prime}\text{
or }j=j^{\prime}\text{ or }L_{i,j}=L_{i^{\prime},j^{\prime}}\end{array}\\},$

that is, two vertices are adjacent if and only if they are in the same row or
the same column or they have the same color (entry in $L$).

The adjacency matrix (in order $(1,1),(1,2),\dots,(5,5))$ of $X$ is

    0  1  1  1  1  1  1  0  0  0  1  0  1  0  0  1  0  0  1  0  1  0  0  0  1
    1  0  1  1  1  0  1  0  1  0  0  1  0  0  1  0  1  1  0  0  1  1  0  0  0
    1  1  0  1  1  0  0  1  0  1  0  0  1  1  0  1  0  1  0  0  0  1  1  0  0
    1  1  1  0  1  1  0  0  1  0  0  1  0  1  0  0  0  0  1  1  0  0  1  1  0
    1  1  1  1  0  0  0  1  0  1  1  0  0  0  1  0  1  0  0  1  0  0  0  1  1
    1  0  0  1  0  0  1  1  1  1  1  1  0  0  0  1  0  0  0  1  1  0  1  0  0
    1  1  0  0  0  1  0  1  1  1  0  1  1  0  0  0  1  0  1  0  0  1  0  0  1
    0  0  1  0  1  1  1  0  1  1  1  0  1  0  0  0  1  1  0  0  0  0  1  1  0
    0  1  0  1  0  1  1  1  0  1  0  0  0  1  1  0  0  1  1  0  1  0  0  1  0
    0  0  1  0  1  1  1  1  1  0  0  0  0  1  1  1  0  0  0  1  0  1  0  0  1
    1  0  0  0  1  1  0  1  0  0  0  1  1  1  1  1  1  0  0  0  1  0  0  1  0
    0  1  0  1  0  1  1  0  0  0  1  0  1  1  1  0  1  0  0  1  0  1  1  0  0
    1  0  1  0  0  0  1  1  0  0  1  1  0  1  1  0  0  1  1  0  0  0  1  0  1
    0  0  1  1  0  0  0  0  1  1  1  1  1  0  1  1  0  0  1  0  0  1  0  1  0
    0  1  0  0  1  0  0  0  1  1  1  1  1  1  0  0  0  1  0  1  1  0  0  0  1
    1  0  1  0  0  1  0  0  0  1  1  0  0  1  0  0  1  1  1  1  1  1  0  0  0
    0  1  0  0  1  0  1  1  0  0  1  1  0  0  0  1  0  1  1  1  0  1  0  1  0
    0  1  1  0  0  0  0  1  1  0  0  0  1  0  1  1  1  0  1  1  1  0  1  0  0
    1  0  0  1  0  0  1  0  1  0  0  0  1  1  0  1  1  1  0  1  0  0  0  1  1
    0  0  0  1  1  1  0  0  0  1  0  1  0  0  1  1  1  1  1  0  0  0  1  0  1
    1  1  0  0  0  1  0  0  1  0  1  0  0  0  1  1  0  1  0  0  0  1  1  1  1
    0  1  1  0  0  0  1  0  0  1  0  1  0  1  0  1  1  0  0  0  1  0  1  1  1
    0  0  1  1  0  1  0  1  0  0  0  1  1  0  0  0  0  1  0  1  1  1  0  1  1
    0  0  0  1  1  0  0  1  1  0  1  0  0  1  0  0  1  0  1  0  1  1  1  0  1
    1  0  0  0  1  0  1  0  0  1  0  0  1  0  1  0  0  0  1  1  1  1  1  1  0

In the colored version $A^{\prime}$, the vertex $(1,1)$ is colored red and
$(1,3)$ is colored blue. In $B^{\prime}$, the vertex $(1,3)$ is red and
$(3,4)$ is blue.