for all $v\in V(G)$. Since the domains of both deg and $\mathbf{Q}$ are
compact, there exists parameters for both of these embeddings such that
without loss of generality we may assume that for $v\in V(G)$,

$\text{deg}(v)+\mathbf{Q}(v)=\begin{bmatrix}\text{deg}(v)&\mathbf{Q}(v)\end{bmatrix}\in\mathbb{R}^{d}$

and that deg and $\mathbf{Q}$ are instead embedded into some smaller
$p$-dimensional and $s$-dimensional sub-spaces, respectively, where it holds
that $d=p+s$.

Next, we choose the embedding $\text{deg}(v)$ to be

$\text{deg}(v)=\begin{bmatrix}\sqrt{d_{v}}&0&\dots&0\end{bmatrix}\in\mathbb{R}^{p},$

where $d_{v}$ is the degree of node $v$ and we write $\sqrt{d_{v}}$ into the
first component and pad the remaining vector with zeros to fit the target
dimension $p$ of deg. We will now use FFN to approximate the following
function $f$, defined as

$f\Big{(}\begin{bmatrix}\text{deg}(v)&\mathbf{Q}(v)\end{bmatrix}\Big{)}=\begin{bmatrix}\text{deg}(v)&\sqrt{d_{v}}\mathbf{Q}(v)\end{bmatrix}.$

Note that a FFN can approximate such a function arbitrarily close since our
domain is compact. Hence, we have that

$\big{|}\big{|}\mathbf{P}(v)-\begin{bmatrix}\text{deg}(v)&\sqrt{d_{v}}\mathbf{Q}(v)\end{bmatrix}\big{|}\big{|}_{\text{F}}<\epsilon_{1},$

for all $\epsilon_{1}>0$. Further, in matrix form this becomes

$\Bigg{|}\Bigg{|}\mathbf{P}-\begin{bmatrix}\begin{bmatrix}\text{deg}(v_{1})\\\
\vdots\\\
\text{deg}(v_{n})\end{bmatrix}&\mathbf{D}^{\frac{1}{2}}\mathbf{Q}\end{bmatrix}\Bigg{|}\Bigg{|}_{\text{F}}<\epsilon_{2},$

for all $\epsilon_{2}>0$, since left multiplication of a matrix by
$\mathbf{D}^{\frac{1}{2}}$ corresponds to an element-wise multiplication of
the $i$-th row of $\mathbf{Q}$ with $\sqrt{d_{v_{i}}}$, the square-root of the
degree of the $i$-th node $v_{i}$ in an arbitrary but fixed node ordering.
Now, since we have that there exists matrices $\mathbf{W}^{Q}$ and
$\mathbf{W}^{K}$ such that

$\frac{1}{\sqrt{d_{k}}}(\mathbf{Q}\mathbf{W}^{Q})(\mathbf{Q}\mathbf{W}^{K})^{T}=\tilde{\mathbf{L}},$

then, for the same matrices $\mathbf{W}^{Q}$ and $\mathbf{W}^{K}$ we know that

$\frac{1}{\sqrt{d_{k}}}(\mathbf{D}^{\frac{1}{2}}\mathbf{Q}\mathbf{W}^{Q})(\mathbf{D}^{\frac{1}{2}}\mathbf{Q}\mathbf{W}^{K})^{T}=\mathbf{D}^{\frac{1}{2}}\tilde{\mathbf{L}}\mathbf{D}^{\frac{1}{2}}=\mathbf{L}$

Finally, since $\mathbf{P}$ has a sub-matrix that can approximate
$\mathbf{D}^{\frac{1}{2}}\mathbf{Q}$ arbitrarily close and since, by Lemma 15,
$\mathbf{D}^{\frac{1}{2}}\mathbf{Q}$ is node- and adjacency-identifying,
$\mathbf{P}$ is sufficiently node- and adjacency-identifying. This shows the
statement. ∎

We now show Theorem 8.

######  Theorem 22 (Theorem 8 in the main paper).

Structural embeddings with SPE as node-level PE are sufficiently node- and
adjacency-identifying.

###### Proof.

We begin by stating that the domain of SPE is compact, since eigenvectors are
unit-norm and eigenvalues are bounded by twice the maximum node degree for
graphs without self-loops (Anderson & Morley, 1985). Further, the domain of
the structural embeddings is compact, since SPE is compact and the node
degrees are finite and hence the domain of deg is compact.

Let $G$ be a graph with (normalized or non-normalized) graph Laplacian
$\mathbf{L}$. Let $\mathbf{L}=\mathbf{V}\mathbf{\Sigma}\mathbf{V}^{T}$ be the
eigendecomposition of $\mathbf{L}$, where the $i$-th column of $\mathbf{V}$
contains the $i$-th eigenvector, denoted $\mathbf{v}_{i}$, and the $i$-th
diagonal entry of $\mathbf{\Sigma}$ contains the $i$-th eigenvalue, denoted
$\lambda_{i}$.

Recall that structural embeddings with SPE as node-level PEs are defined as

$\mathbf{P}(v)=\textsf{FFN}(\text{deg}(v)+\text{SPE}(v)),$

for all $v\in V(G)$, where

$\text{SPE}(v)=\rho\Big{(}\begin{bmatrix}\mathbf{V}\text{diag}(\phi_{1}(\mathbf{\lambda}))\mathbf{V}^{T}&\dots&\mathbf{V}\text{diag}(\phi_{n}(\mathbf{\lambda}))\mathbf{V}^{T}\end{bmatrix}\Big{)}(v).$

To show node and adjacency identifiability, we first replace the neural
networks $\rho,\phi_{1},\dots,\phi_{n}$ in SPE with functions permutation
equivariant functions $g,h_{1},\dots,h_{n}$ over the same domain and co-
domain, respectively, and choose $g$ and $h_{1},\dots,h_{n}$ such that the
resulting encoding, which we call $f_{\text{SPE}}$, is sufficiently node- and
adjacency-identifying. Then, we show that $\rho$ and $\phi_{1},\dots,\phi_{n}$
can approximate $g$ and $h_{1},\dots,h_{n}$ arbitrarily close, which gives the
proof statement.

We first define, for all $\ell\in[n]$,

$h_{\ell}(\lambda)=\begin{bmatrix}0\\\ \vdots\\\
\lambda_{\ell}^{\frac{1}{2}}\\\ \vdots\\\ 0\end{bmatrix},$

such that $\lambda_{\ell}$ is the $\ell$-th sorted eigenvalue where ties are
broken arbitrarily333Note that despite eigenvalues with higher multiplicity,
the output of $h_{\ell}$ is the same, no matter how ties are broken. and
$\lambda_{\ell}$ is the $\ell$-th entry of $h_{\ell}(\mathbf{\lambda})$. Note
that due to the sorting, $h_{\ell}$ is equivariant to permutations of the
nodes.

We then define the matrix $\mathbf{M}_{i}$ as $i$-th input to $g$ in
$f_{\text{SPE}}$, for all $i\in[n]$. We have

$\displaystyle\mathbf{M}_{i}$
$\displaystyle\coloneqq\begin{bmatrix}\mathbf{V}\text{diag}(h_{1}(\mathbf{\lambda}))\mathbf{V}_{i}^{T}&\dots&\mathbf{V}\text{diag}(h_{n}(\mathbf{\lambda}))\mathbf{V}_{i}^{T}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\sum_{j}v_{1j}\cdot
h_{1}(\mathbf{\lambda})_{j}\cdot v_{ij}&\dots&\sum_{j}v_{1j}\cdot
h_{n}(\mathbf{\lambda})_{j}\cdot v_{ij}\\\ &\ddots&\\\ \sum_{j}v_{nj}\cdot
h_{1}(\mathbf{\lambda})_{j}\cdot v_{ij}&\dots&\sum_{j}v_{nj}\cdot
h_{n}(\mathbf{\lambda})_{j}\cdot v_{ij}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}v_{11}\cdot\lambda_{1}^{\frac{1}{2}}\cdot
v_{i1}&\dots&v_{1n}\cdot\lambda_{n}^{\frac{1}{2}}\cdot v_{in}\\\ &\ddots&\\\
v_{n1}\cdot\lambda_{1}^{\frac{1}{2}}\cdot
v_{i1}&\dots&v_{nn}\cdot\lambda_{n}^{\frac{1}{2}}\cdot v_{in}\end{bmatrix},$

where the last equality follows from the fact that
$h_{\ell}(\mathbf{\lambda})_{j}\neq 0$ if and only if $\ell=j$. Now, we choose
a linear set function $f$, satisfying

$f(\\{a\cdot x\mid x\in X\\})=a\cdot f(X),$

for all $a\in\mathbb{R}$ and all $X\subset\mathbb{R}$, e.g., sum or mean.
Since $f$ is a function over sets, $f$ is equivariant to the ordering of $X$.
We now define the function $g$ step-by-step. In $g$, we first apply $f$ to the
columns of $\mathbf{M}_{i}$ for all $i\in[n]$. To this end, let
$\mathbf{M}_{ij}$ denote the set of entries in the $j$-column of matrix
$\mathbf{M}_{i}$. Then, we define

$\displaystyle\mathbf{f}_{i}$
$\displaystyle=\begin{bmatrix}f(\mathbf{M}_{i1})&\dots&f(\mathbf{M}_{in})\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\lambda_{1}^{\frac{1}{2}}\cdot v_{i1}\cdot
f(\\{v_{o1}\mid o\in[n]\\})&\dots&\lambda_{n}^{\frac{1}{2}}\cdot v_{in}\cdot
f(\\{v_{on}\mid o\in[n]\\})\end{bmatrix},$

We then multiply $\mathbf{f}_{i}$ element-wise to each row of $\mathbf{M}_{i}$
and obtain a matrix

$\displaystyle\mathbf{P}_{i}$
$\displaystyle=\mathbf{M}_{i}\cdot\mathbf{f}_{i}$
$\displaystyle=\begin{bmatrix}v_{11}\cdot(\lambda_{1}^{\frac{1}{2}})^{2}\cdot(v_{i1})^{2}&\dots&v_{1n}\cdot(\lambda_{1}^{\frac{1}{2}})^{2}\cdot(v_{in})^{2}\\\
&\ddots&\\\
v_{n1}\cdot(\lambda_{1}^{\frac{1}{2}})^{2}\cdot(v_{i1})^{2}&\dots&v_{nn}\cdot(\lambda_{n}^{\frac{1}{2}})^{2}\cdot(v_{in})^{2}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}v_{11}\cdot\lambda_{1}\cdot(v_{i1})^{2}&\dots&v_{1n}\cdot\lambda_{n}\cdot(v_{in})^{2}\\\
&\ddots&\\\
v_{n1}\cdot\lambda_{1}\cdot(v_{i1})^{2}&\dots&v_{nn}\cdot\lambda_{n}\cdot(v_{in})^{2}\end{bmatrix}.$

Further, we divide each row of $\mathbf{M}_{i}$ element-wise by
$\mathbf{f}_{i}$ and obtain a matrix

$\displaystyle\mathbf{Q}_{i}$ $\displaystyle=\mathbf{M}_{i}/\mathbf{f}_{i}$
$\displaystyle=\begin{bmatrix}\dfrac{v_{11}}{f(\\{v_{o1}\mid
o\in[n]\\})}&\dots&\dfrac{v_{1n}}{f(\\{v_{on}\mid o\in[n]\\})}\\\ &\ddots&\\\
\dfrac{v_{n1}}{f(\\{v_{o1}\mid
o\in[n]\\})}&\dots&\dfrac{v_{nn}}{f(\\{v_{on}\mid o\in[n]\\})}\end{bmatrix}.$

Hence, we also need to ensure that

$f(\\{v_{oj}\mid o\in[n]\\})\neq 0,$

for all $j\in[n]$. Now, we define

$\mathbf{P}=\sum_{i}\mathbf{P}_{i}$

and

$\mathbf{Q}=\sum_{i}\mathbf{Q}_{i}.$

and have that

$\displaystyle(\mathbf{P}\mathbf{Q}^{T})_{k,l}$
$\displaystyle=\sum_{\ell}\Big{(}v_{k\ell}\cdot\lambda_{\ell}\cdot
f(\\{v_{o\ell}\mid
o\in[n]\\})\cdot\sum_{i}v_{i\ell}^{2}\Big{)}\cdot\Big{(}\dfrac{v_{l\ell}}{f(\\{v_{o\ell}\mid
o\in[n]\\})}\Big{)}$ $\displaystyle=\sum_{\ell}v_{k\ell}\cdot
v_{l\ell}\cdot\lambda_{\ell},$

where we recall that the eigenvectors are normalized and hence,
$\sum_{i}v_{i\ell}^{2}=1$.

In the last step of $g$, we return the matrix

$\begin{bmatrix}\mathbf{P}&\mathbf{Q}\end{bmatrix}\in\mathbb{R}^{n\times 2n}.$

We will now show that this matrix is node- and adjacency-identifying. To this
end, note that

$(\mathbf{P}\mathbf{Q}^{T})_{k,l}=(\mathbf{V}\Sigma\mathbf{V}^{T})_{k,l}$

and hence,

$\mathbf{P}\mathbf{Q}^{T}=\mathbf{V}\Sigma\mathbf{V}^{T}=\mathbf{L}.$

We distinguish between two cases. If $\mathbf{L}$ is the non-normalized graph
Laplacian, then according to Lemma 16, the matrix

$\begin{bmatrix}\mathbf{P}&\mathbf{Q}\end{bmatrix}$

is node- and adjacency-identifying and hence, according to Lemma 19,
$f_{\text{SPE}}$ is node- and adjacency-identifying. Further, if $\mathbf{L}$
is the normalized graph Laplacian, according to Lemma 21, $f_{\text{SPE}}$ is
sufficiently node- and adjacency-identifying.

To summarize, we have shown that there exist functions $g,h_{1},\dots,h_{n}$
such that if, in SPE, we replace $\rho$ with $g$ and $\phi_{\ell}$ with
$h_{\ell}$, then the resulting encoding $f_{\text{SPE}}$ is sufficiently node-
and adjacency-identifying. To complete the proof, we will now show that we can
approximate $g,h_{1},\dots,h_{n}$ with $\rho,\phi_{1},\dots,\phi_{n}$
arbitrarily close. Since our domain is compact, we can use $\phi_{\ell}$ to
approximate $h_{\ell}$ arbitrarily close, i.e., we have that

$\big{|}\big{|}\phi_{\ell}-h_{\ell}\big{|}\big{|}_{\text{F}}<\epsilon,$

for all $\epsilon>0$. Further, $g$ consists of a sequence of permutation
equivariant steps and is thus, permutation equivariant. Since the domain of
$g$ is compact and, by construction, $g$ and $\rho$ have the same domain and
co-domain, and since $\rho$ can approximate any permutation equivariant
function on its domain and co-domain arbitrarily close, we have that $\rho$
can also approximate $g$ arbitrarily close. As a result, SPE can approximate a
sufficiently node- and adjacency-identifying encoding arbitrarily close, and
hence, by definition, we have that SPE is also sufficiently node- and
adjacency-identifying. This completes the proof. ∎

##  Appendix G Learnable embeddings

Here, we pay more attention to learnable embeddings, which play an important
role throughout our work. Although our definition of learnable embeddings is
fairly abstract, learnable embeddings are very commonly used in practice,
e.g., in tokenizers of language models (Vaswani et al., 2017). Since many
components of graphs, such as the node labels, edge types, or node degrees are
discrete, learnable embeddings are useful to embed these discrete features
into an embedding space. In our work, different embeddings are typically
joined via sum, e.g., in Equation 1 or Equation 4. Summing embeddings is much
more convenient in practice since every embedding has the same dimension $d$.
In contrast, joining embeddings via concatenation can lead to very large $d$,
unless the underlying embeddings are very low-dimensional. However, in our
theorems joining embeddings via concatenation is much more convenient. To
bridge theory and practice in this regard, in what follows we establish under
what conditions summed embeddings can express concatenated embeddings and vice
versa. Specifically, we show that summed embeddings can still act as if
concatenating lower-dimensional embeddings but with more flexibility in terms
of joining different embeddings.

The core idea is that we show under which operations one may replace a
learnable embedding e to $\mathbb{R}^{d}$ with a lower-dimensional learnable
embedding $\text{e}^{\prime}$ to $\mathbb{R}^{d^{\prime}}$ while preserving
the injectivity of e. This property is useful since it allows us to, for
example, add two learnable embeddings without losing expressivity. As a
result, we can design a tokenizer that is practically useful without
sacrificing theoretical guarantees.

We begin with a projection of a concatenation of learnable embeddings.

######  Lemma 23 (Projection of learnable embeddings).

Let $\text{e}^{\prime}_{1},\dots,\text{e}^{\prime}_{k}$ be learnable
embeddings from $\mathbb{N}$ to $\mathbb{R}^{p}$ for some $p\geq 1$. If $d\geq
k$ then, there exists learnable embeddings $\text{e}_{1},\dots,\text{e}_{k}$
as well as a projection matrix $\mathbf{W}\in\mathbb{R}^{d\cdot k\times k\cdot
p}$ such that for $v_{1},\dots,v_{k}\in\mathbb{N}$

$\big{[}\text{e}_{i}(v_{i})\big{]}_{i=1}^{k}\mathbf{W}=\big{[}\text{e}^{\prime}_{i}(v_{i})\big{]}_{i=1}^{k}\in\mathbb{R}^{k\cdot
p},$

where it holds for all $v,w\in\mathbb{N}$ and all $i\in\\{1,\dots,k\\}$ that

$\text{e}_{i}(v)=\text{e}_{i}(w)\Longleftrightarrow\text{e}^{\prime}_{i}(v)=\text{e}^{\prime}_{i}(w).$

###### Proof.

For a learnable embedding e and some $v\in\mathbb{N}$, we denote with
$\text{e}(v)_{j}$ the $j$-th element of the vector $\text{e}(v)$. Since
learnable embeddings are from $\mathbb{N}$ to $\mathbb{R}^{d}$, for every $i$
we define $\text{e}_{i}$ such that for every $v\in\mathbb{N}$,
$\text{e}_{i}(v)_{1}=\text{e}^{\prime}_{i}(v)$ and $\text{e}_{i}(v)_{j}=0$ for
$j>0$.

Now, we define $\mathbf{W}$ as follows. For row $l$ and column $j$, we set
$\mathbf{W}_{lj}=1$ if $(l-1)$ is a multiple of $d$, i.e.,
$l=1,(d+1),2(d+1),\dots$. Otherwise we set $\mathbf{W}_{lj}=0$. Intuitively,
applying $\mathbf{W}$ to $\big{[}\text{e}_{i}(v_{i})\big{]}_{i=1}^{k}$ will
select the first, $d$-th, $2d$-th, $\dots$, $kd$-th, element of
$\big{[}\text{e}_{i}(v_{i})\big{]}_{i=1}^{k}$, corresponding to
$v_{1},\dots,v_{k}$, respectively, according to our construction of
$\text{e}_{i}$. Now, we have that

$\big{[}\text{e}_{i}(v_{i})\big{]}_{i=1}^{k}\mathbf{W}=\big{[}\text{e}^{\prime}_{1}(v_{1})\,\dots\,\text{e}^{\prime}_{k}(v_{k})\big{]}=\big{[}\text{e}^{\prime}_{i}(v_{i})\big{]}_{i=1}^{k}.$

Further we have by construction that for all $v,w\in\mathbb{N}$ and all
$i\in\\{1,\dots,k\\}$

$\text{e}_{i}(v)=\text{e}_{i}(w)\Longleftrightarrow\text{e}^{\prime}_{i}(v)=\text{e}^{\prime}_{i}(w).$

This shows the statement. ∎

Next, we turn to a composition of learnable embeddings, namely the structural
embeddings $\mathbf{P}$, as defined in Section 3.1. In particular, we show
next that a projection of multiple structural embeddings preserves node- and
adjacency identifiability of the individual structural embeddings in the new
embedding space.

######  Lemma 24 (Projection of structural embeddings).

Let $G$ be a graph with $n$ nodes and let $\mathbf{P}\in\mathbb{R}^{n\times
d}$ be structural embeddings for $G$. Let $k>1$. If $d\geq k\cdot(2n+1)$ then,
there exists a parameterization of $\mathbf{P}$ as well as a projection matrix
$\mathbf{W}\in\mathbb{R}^{k\cdot d\cdot k\times(2n+1)}$ such that for any
$v_{1},\dots,v_{k}\in V(G)$,

$\big{[}\mathbf{P}(v_{i})\big{]}_{i=1}^{k}\mathbf{W}=\big{[}\mathbf{P}^{\prime}(v_{i})\big{]}_{i=1}^{k}\in\mathbb{R}^{n\times
d},$

where $\mathbf{P}^{\prime}\in\mathbb{R}^{n\times d^{\prime}}$ is also a
structural embedding for $G$ and it holds that if $\mathbf{P}$ is sufficiently
node- and adjacency-identifying, then so is $\mathbf{P}^{\prime}$.

###### Proof.

We know from Theorem 20 that there exists sufficiently node- and adjacency-
identifying structural embeddings $\mathbf{P}^{\prime}$ in
$\mathbb{R}^{n\times(2d+1)}$. Since $d\geq k\cdot(2n+1)$, we define

$\mathbf{P}=\begin{bmatrix}\mathbf{P}^{\prime}&\mathbf{0}\end{bmatrix},$

where $\mathbf{0}\in\mathbb{R}^{n\times(k-1)\cdot(2n+1)}$ is an all-zero
matrix. Since $\mathbf{P}$ has a sufficiently node- and adjacency-identifying
subspace $\mathbf{P}^{\prime}$, by Lemma 19, $\mathbf{P}$ is sufficiently
node- and adjacency-identifying. Further, by setting

$\mathbf{W}=\mathbf{I}_{n\times k\cdot(2n+1)},$

where $\mathbf{I}_{n\times k\cdot(2n+1)}$ are the first $n$ rows of the
$k\cdot(2n+1)$-dimensional identity matrix and
$\mathbf{0}\in\mathbb{R}^{n\times(k-1)\cdot(2n+1)}$ is again an all-zero
matrix.

Then, we have that for nodes $v_{1},\dots,v_{k}\in V(G)$,

$\big{[}\mathbf{P}(v_{i})\big{]}_{i=1}^{k}\mathbf{W}=\big{[}\mathbf{P}^{\prime}(v_{i})\big{]}_{i=1}^{k}\in\mathbb{R}^{n\times
d},$

and $\mathbf{P}^{\prime}$ is by definition sufficiently node- and adjacency-
identifying, from which the statement follows. ∎

We continue by showing that our construction of token embeddings in Equation 1
can be equally well represented by another form that will be easier to use in
proving Theorem 2.

######  Lemma 25.

Let $G$ be a graph with node features $\mathbf{F}\in\mathbb{R}^{n\times d}$.
For every tokenization $\mathbf{X}^{(0,1)}\in\mathbb{R}^{d}$ according to
Equation 1 with (sufficiently) adjacency reconstructing structural embeddings
$\mathbf{P}(v)$, there exists a parameterization of $\mathbf{X}^{(0,1)}$ such
that for node $v\in V(G)$ as

$\mathbf{X}^{(0,1)}(v)=\begin{bmatrix}\mathbf{F}^{\prime}(v)&\mathbf{0}&\text{deg}^{\prime}(v)&\mathbf{P}^{\prime}(v)\end{bmatrix},$

with

$\mathbf{P}^{\prime}(v)=\textsf{FFN}^{\prime}(\text{deg}^{\prime}(v)+\text{PE}(v)),$

such that $\mathbf{F}^{\prime}(v)\in\mathbb{R}^{p}$,
$\mathbf{0}\in\mathbb{R}^{p}$,
$\text{deg}^{\prime}:\mathbb{N}\rightarrow\mathbb{R}^{r}$ and
$\textsf{FFN}^{\prime}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{s}$ for $d=2p+r+s$
and where it holds for every $v,w\in V(G)$ that

$\mathbf{F}(v)=\mathbf{F}(w)\Longleftrightarrow\mathbf{F}^{\prime}(v)=\mathbf{F}^{\prime}(w)$

and

$\text{deg}(v)=\text{deg}(w)\Longleftrightarrow\text{deg}^{\prime}(v)=\text{deg}^{\prime}(w)$

and

$\mathbf{P}(v)=\mathbf{P}(w)\Longleftrightarrow\mathbf{P}^{\prime}(v)=\mathbf{P}^{\prime}(w)$

and $\mathbf{P}^{\prime}(v)$ is (sufficiently) adjacency-identifying.

###### Proof.

We set $p=\nicefrac{{(d-(2n+1))}}{{2}}-1$, $r=2$ and $s=(2n+1)$. Indeed, we
have that

$2p+r+s=2(\nicefrac{{(d-(2n+1))}}{{2}}-1)+2+(2n+1)=d-(2n+1)+(2n+1)=d.$

We continue by noting that the node features $\mathbf{F}$ are mapped from
$\mathbb{N}$ to $\mathbb{R}^{d}$ and can be obtained from a learnable
embedding. More importantly, we can define

$\mathbf{F}^{\prime}(v)=\begin{bmatrix}\ell(v)&0&\dots&0\end{bmatrix},$

where $\mathbf{F}^{\prime}(v)\in\mathbb{R}^{d}$ is another learnable embedding
for which it holds that

$\mathbf{F}(v)=\mathbf{F}(w)\Longleftrightarrow\mathbf{F}^{\prime}(v)=\mathbf{F}^{\prime}(w),$

for all $v,w\in V(G)$.

Further, we can write

$\text{deg}(v)+\text{PE}(v)=\begin{bmatrix}\text{deg}^{\prime}(v)&\text{PE}(v)\end{bmatrix},$

where $\text{deg}^{\prime}$ is another learnable embedding for the node
degrees mapping to $\mathbb{R}^{r}$. Moreover, we know from Theorem 20 that
there exist (sufficiently) adjacency-identifying structural embeddings of
dimension $(2n+1)$. We choose the FFN in Equation 2 such that

$\mathbf{P}(v)=\begin{bmatrix}\mathbf{0}&\text{deg}^{\prime}(v)&\mathbf{P}^{\prime}\end{bmatrix},$

where $\mathbf{0}\in\mathbb{R}^{2p}$ is an all-zero vector and

$\mathbf{P}^{\prime}=\textsf{FFN}^{\prime}(\text{deg}^{\prime}(v)+\text{PE}(v)),$

with $\textsf{FFN}^{\prime}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{s}$, another
FFN inside of FFN. Note that such a FFN exists without approximation. Further
according to Lemma 24, $\mathbf{P}^{\prime}$ is still (sufficiently)
adjacency-identifying. Hence, we can write

$\mathbf{X}^{(0,1)}(v)=\mathbf{F}^{\prime}(v)+\mathbf{P}^{\prime}(v)=\begin{bmatrix}\mathbf{F}^{\prime}(v)&\mathbf{0}&\text{deg}^{\prime}(v)&\textsf{FFN}^{\prime}(\text{deg}^{\prime}(v)+\text{PE}(v))\end{bmatrix},$

where through the concatenation it is easy to verify that indeed
$\mathbf{X}^{(0,1)}(v)$ has the desired properties, namely that

$\mathbf{F}(v)=\mathbf{F}(w)\Longleftrightarrow\mathbf{F}^{\prime}(v)=\mathbf{F}^{\prime}(w)$

and

$\text{deg}(v)=\text{deg}(w)\Longleftrightarrow\text{deg}^{\prime}(v)=\text{deg}^{\prime}(w)$

and

$\mathbf{P}(v)=\mathbf{P}(w)\Longleftrightarrow\mathbf{P}^{\prime}(v)=\mathbf{P}^{\prime}(w)$

and $\mathbf{P}^{\prime}(v)$ is (sufficiently) adjacency-identifying. This
shows the statement. ∎

Lastly, we show a similar result for Equation 4.

######  Lemma 26.

Let $G$ be a graph with node features $\mathbf{F}\in\mathbb{R}^{n\times d}$.
For every tokenization $\mathbf{X}^{(0,k)}\in\mathbb{R}^{d}$ according to
Equation 4 with node- and adjacency reconstructing structural embeddings
$\mathbf{P}(v)$, there exists a parameterization of $\mathbf{X}^{(0,k)}$ such
that for $k$-tuple $\mathbf{v}=(v_{1},\dots,v_{k})\in V(G)^{k}$,

$\mathbf{X}^{(0,k)}(v)=\begin{bmatrix}\mathbf{F}^{\prime}(v_{1})\,\,\,\,\dots\,\,\,\,\mathbf{F}^{\prime}(v_{k})&\mathbf{0}&\text{deg}^{\prime}(v_{1})&\dots&\text{deg}^{\prime}(v_{k})&\mathbf{P}^{\prime}(v_{1})&\dots&\mathbf{P}^{\prime}(v_{k})&\text{atp}^{\prime}(\mathbf{v})\end{bmatrix},$

with

$\mathbf{P}^{\prime}(v)=\textsf{FFN}^{\prime}(\text{deg}^{\prime}(v)+\text{PE}(v)),$

such that $\mathbf{F}^{\prime}(v)\in\mathbb{R}^{p}$,
$\mathbf{0}\in\mathbb{R}^{k^{2}\cdot p}$,
$\text{deg}^{\prime}:\mathbb{N}\rightarrow\mathbb{R}^{r}$,
$\text{atp}^{\prime}:\mathbb{N}\rightarrow\mathbb{R}^{o}$ and
$\mathbf{P}^{\prime}\in\mathbb{R}^{s}$ for $d=k^{2}\cdot p+k\cdot p+k\cdot
r+k\cdot s+o$ and where it holds for every $v,w\in V(G)$,

$\mathbf{F}^{\prime}(v)=\mathbf{F}(w)\Longleftrightarrow\mathbf{F}^{\prime}(v)=\mathbf{F}^{\prime}(w)$

and

$\text{deg}(v)=\text{deg}(w)\Longleftrightarrow\text{deg}^{\prime}(v)=\text{deg}^{\prime}(w)$

and

$\mathbf{P}(v)=\mathbf{P}(w)\Longleftrightarrow\mathbf{P}^{\prime}(v)=\mathbf{P}^{\prime}(w)$

and $\mathbf{P}^{\prime}(v)$ is node and adjacency-identifying and for every
$\mathbf{v},\mathbf{w}\in V(G)^{k}$

$\text{atp}(\mathbf{v})=\text{atp}(\mathbf{w})\Longleftrightarrow\text{atp}^{\prime}(\mathbf{v})=\text{atp}^{\prime}(\mathbf{w}).$

###### Proof.

We set $p=1$, $r=2$, $o=1$ and $s=\frac{d-k^{2}-3k-1}{k}$. Indeed, we have
that

$k^{2}\cdot p+k\cdot p+k\cdot r+k\cdot s+o=k^{2}+3k+d-k^{2}-3k-1+1=d.$

Recall Equation 4 as

$\mathbf{X}^{(0,k)}(\mathbf{v})=\big{[}\mathbf{F}(v_{i})\big{]}_{i=1}^{k}\mathbf{W}^{F}+\big{[}\mathbf{P}(v_{i})\big{]}_{i=1}^{k}\mathbf{W}^{P}+\text{atp}(\mathbf{v}),$

where $\mathbf{W}^{F}\in\mathbb{R}^{d\cdot k\times d}$ and
$\mathbf{W}^{P}\in\mathbb{R}^{d\cdot k\times d}$ are projection matrices,
$\mathbf{P}$ are structural embeddings and $\mathbf{v}=(v_{1},\dots,v_{k})$ is
a $k$-tuple.

We continue by noting that the node features $\mathbf{F}$ are mapped from
$\mathbb{N}$ to $\mathbb{R}^{d}$ and can be obtained from a learnable
embedding. More importantly, we can define $\mathbf{F}^{\prime}(v)=\ell(v)$
for which it clearly holds that

$\mathbf{F}(v)=\mathbf{F}(w)\Longleftrightarrow\mathbf{F}^{\prime}(v)=\mathbf{F}^{\prime}(w),$

for all $v,w\in V(G)$. Invoking Lemma 23, there exists learnable embeddings
$\mathbf{F}$ and a projection matrix $\mathbf{W}^{F,*}\in\mathbb{R}^{k\cdot
d\times k\cdot p}$ such that

$\big{[}\mathbf{F}(v_{i})\big{]}_{i=1}^{k}\mathbf{W}^{F}=\begin{bmatrix}\mathbf{F}^{\prime}(v_{1})&\dots&\mathbf{F}^{\prime}(v_{k})\end{bmatrix}\in\mathbb{R}^{k\cdot
p}.$

Note that since we do not have an assumption on $d$, we can make $d$
arbitrarily large to ensure that $d\geq k$. Hence, by defining

$\mathbf{W}^{F}=\begin{bmatrix}\mathbf{W}^{F,*}&\mathbf{0}\end{bmatrix},$

where $\mathbf{0}\in\mathbb{R}^{k\cdot d\times(d-k\cdot p)}$ is an all-zero
matrix, we can write

$\big{[}\mathbf{F}(v_{i})\big{]}_{i=1}^{k}\mathbf{W}^{F}=\begin{bmatrix}\mathbf{F}^{\prime}(v_{1})&\dots&\mathbf{F}^{\prime}(v_{k})&\mathbf{0}\end{bmatrix}\in\mathbb{R}^{d},$

where $\mathbf{0}\in\mathbb{R}^{d-k\cdot p}$ is an all-zero vector.

Moreover, we know from Theorem 7 that there exists adjacency-identifying
structural embeddings of dimension $(2n+1)$. We choose the FFN in Equation 2
such that

$\mathbf{P}(v)=\begin{bmatrix}\mathbf{0}&\text{deg}^{\prime}(v)&\mathbf{P}^{\prime}(v)\end{bmatrix},$

where $\mathbf{0}\in\mathbb{R}^{k^{2}\cdot p+k\cdot p}$ is an all-zero vector
and

$\mathbf{P}^{\prime}(v)=\textsf{FFN}^{\prime}(\text{deg}^{\prime}(v)+\text{PE}(v)),$

with $\textsf{FFN}^{\prime}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{s}$, another
FFN inside of FFN. Note that such a FFN exists without approximation. Further,
according to Lemma 24, $\mathbf{P}^{\prime}$ is still sufficiently adjacency-
identifying, and there exists a projection matrix
$\mathbf{W}^{P,*}\in\mathbb{R}^{k\cdot d\times d-o}$ such that

$\big{[}\mathbf{P}(v_{i})\big{]}_{i=1}^{k}\mathbf{W}^{P,*}=\begin{bmatrix}\mathbf{0}&\text{deg}^{\prime}(v_{1})&\mathbf{P}^{\prime}(v_{1})&\dots&\mathbf{0}&\text{deg}^{\prime}(v_{k})&\mathbf{P}^{\prime}(v_{k})\end{bmatrix}\in\mathbb{R}^{d-o}.$

But then, there also exists a permutation matrix
$\mathbf{Q}\in\\{0,1\\}^{d-o\times d-o}$ such that

$\big{[}\mathbf{P}(v_{i})\big{]}_{i=1}^{k}\mathbf{W}^{P,*}\mathbf{Q}=\begin{bmatrix}\mathbf{0}&\text{deg}^{\prime}(v_{1})&\dots&\text{deg}^{\prime}(v_{k})&\mathbf{P}^{\prime}(v_{1})&\dots&\mathbf{P}^{\prime}(v_{k})\end{bmatrix}\in\mathbb{R}^{d-o},$

where we simply re-order the entries of
$\big{[}\mathbf{P}(v_{i})\big{]}_{i=1}^{k}\mathbf{W}^{P,*}$. Note that now,
$\mathbf{0}\in\mathbb{R}^{k^{2}\cdot p+k\cdot p}$, as we grouped the zero-
vectors of $\big{[}\mathbf{P}(v_{i})\big{]}_{i=1}^{k}\mathbf{W}^{P,*}$ into a
single zero-vector of size $k^{2}\cdot p+k\cdot p$.

Note that since we do not have an assumption on $d$, we can make $d$
arbitrarily large to ensure that $d\geq k\cdot(2n+1)$. Hence, by defining

$\mathbf{W}^{P}=\begin{bmatrix}\mathbf{W}^{P,*}\mathbf{Q}&\mathbf{0}\end{bmatrix},$

where $\mathbf{0}\in\mathbb{R}^{o}$ is an all-zero vector, we can write

$\big{[}\mathbf{P}(v_{i})\big{]}_{i=1}^{k}\mathbf{W}^{P}=\begin{bmatrix}\mathbf{0}&\text{deg}^{\prime}(v_{1})&\dots&\text{deg}^{\prime}(v_{k})&\mathbf{P}^{\prime}(v_{1})&\dots&\mathbf{P}^{\prime}(v_{k})&\mathbf{0}\end{bmatrix}\in\mathbb{R}^{d},$

where $\mathbf{P}^{\prime}(v_{i})\in\mathbb{R}^{s}$. Further, since
$\mathbf{P}$ is by assumption sufficiently node- and adjacency-identifying,
Lemma 24 guarantees that then so is $\mathbf{P}^{\prime}$.

Finally, for tuple $\mathbf{v}\in V(G)^{k}$, we set

$\text{atp}(\mathbf{v})=\begin{bmatrix}\mathbf{0}&\text{atp}^{\prime}(\mathbf{v})\end{bmatrix},$

where $\text{atp}^{\prime}(\mathbf{v})=\text{atp}(\mathbf{v})$ and we recall
that atp maps to $\mathbb{N}$ and $\mathbf{0}\in\mathbb{R}^{d-1}$ is an all-
zero vector.

Then, we can write

$\displaystyle\mathbf{X}^{(0,k)}(\mathbf{v})$
$\displaystyle=\big{[}\mathbf{F}(v_{i})\big{]}_{i=1}^{k}\mathbf{W}^{F}+\big{[}\mathbf{P}(v_{i})\big{]}_{i=1}^{k}\mathbf{W}^{P}+\text{atp}(\mathbf{v})$
$\displaystyle=\begin{bmatrix}\mathbf{F}^{\prime}(v_{1})\,\,\,\,\dots\,\,\,\,\mathbf{F}^{\prime}(v_{k})&\mathbf{0}&\text{deg}^{\prime}(v_{1})&\dots&\text{deg}^{\prime}(v_{k})&\mathbf{P}^{\prime}(v_{1})&\dots&\mathbf{P}^{\prime}(v_{k})&\text{atp}^{\prime}(\mathbf{v})\end{bmatrix},$

where it holds for every $v,w\in V(G)$,

$\mathbf{F}^{\prime}(v)=\mathbf{F}(w)\Longleftrightarrow\mathbf{F}^{\prime}(v)=\mathbf{F}^{\prime}(w)$

and

$\text{deg}(v)=\text{deg}(w)\Longleftrightarrow\text{deg}^{\prime}(v)=\text{deg}^{\prime}(w)$

and

$\mathbf{P}(v)=\mathbf{P}(w)\Longleftrightarrow\mathbf{P}^{\prime}(v)=\mathbf{P}^{\prime}(w)$

where $\mathbf{P}^{\prime}(v)$ is node and adjacency-identifying and for every
$\mathbf{v},\mathbf{w}\in V(G)^{k}$

$\text{atp}(\mathbf{v})=\text{atp}(\mathbf{w})\Longleftrightarrow\text{atp}^{\prime}(\mathbf{v})=\text{atp}^{\prime}(\mathbf{w}).$

This shows the statement. ∎

##  Appendix H Expressivity of $1$-GT

Here, we prove Theorem 2 in the main paper. We first restate Theorem VIII.4 of
(Grohe, 2021), showing that a simple GNN can simulate the $1$-WL.

######  Lemma 27 (Grohe (2021), Theorem VIII.4).

Let $G=(V(G),E(G),\ell)$ be a graph with $n$ nodes with adjacency matrix
$\mathbf{A}(G)$ and node feature matrix
$\mathbf{X}^{(0)}\coloneqq\mathbf{F}\in\mathbb{R}^{n\times d}$ consistent with
$\ell$. Further, assume a GNN that for each layer, $t>0$, updates the vertex
feature matrix

$\mathbf{X}^{(t)}\coloneqq\mathsf{FFN}\Big{(}\mathbf{X}^{(t-1)}+2\mathbf{A}(G)\mathbf{X}^{(t-1)}\Big{)}.$

Then, for all $t\geq 0$, there exists a parameterization of $\mathsf{FFN}$
such that

$C^{1}_{t}(v)=C^{1}_{t}(w)\Longleftrightarrow\mathbf{X}^{(t)}(v)=\mathbf{X}^{(t)}(w),$

for all vertices $v,w\in V(G)$.

We now give the proof for a slight generalization of Theorem 2. Specifically,
we relax the adjacency-identifying condition to sufficiently adjacency-
identifying.

######  Theorem 28 (Generalization of Theorem 2 in main paper).

Let $G=(V(G),E(G),\ell)$ be a labeled graph with $n$ nodes and
$\mathbf{F}\in\mathbb{R}^{n\times d}$ be a node feature matrix consistent with
$\ell$. Let $C^{1}_{t}$ denote the coloring function of the $1$-WL at
iteration $t$. Then, for all iterations $t\geq 0$, there exists a
parametrization of the $1$-GT with sufficiently adjacency-identifying
structural embeddings, such that

$C^{1}_{t}(v)=C^{1}_{t}(w)\Longleftrightarrow\mathbf{X}^{(t,1)}(v)=\mathbf{X}^{(t,1)}(w),$

for all nodes $v,w\in V(G)$.

###### Proof.

According to Lemma 25, there exists a parameterization of $\mathbf{X}^{(0,1)}$
such that for each $v\in V(G)$,

$\mathbf{X}^{(0,1)}(v)=\mathbf{F}^{\prime}(v)+\mathbf{P}^{\prime}(v)=\begin{bmatrix}\mathbf{F}^{\prime}(v)&\mathbf{0}&\text{deg}^{\prime}(v)&\mathbf{P}^{\prime}(v)\end{bmatrix},$

where it holds that

$\mathbf{F}(v)=\mathbf{F}(w)\Longleftrightarrow\mathbf{F}^{\prime}(v)=\mathbf{F}^{\prime}(w)$
(17)

and

$\text{deg}(v)=\text{deg}(w)\Longleftrightarrow\text{deg}^{\prime}(v)=\text{deg}^{\prime}(w)$

and

$\mathbf{P}(v)=\mathbf{P}(w)\Longleftrightarrow\mathbf{P}^{\prime}(v)=\mathbf{P}^{\prime}(w)$

and $\mathbf{P}^{\prime}(v)$ is adjacency-identifying. Further,
$\mathbf{F}^{\prime}(v),\mathbf{0}\in\mathbb{R}^{p}$,
$\text{deg}^{\prime}(v)\in\mathbb{R}^{r}$ and
$\mathbf{P}^{\prime}(v)\in\mathbb{R}^{s}$, for some choice of $p,r,s$ where
$d=2p+r+s$, specified in Lemma 25. We will use this parameterization for
$\mathbf{X}^{(0,1)}$ throughout the rest of the proof.

We will now prove the statement by induction over $t$. Since by definition

$C^{1}_{0}(v)=C^{1}_{0}(w)\Longleftrightarrow\mathbf{F}(v)=\mathbf{F}(w),$

the base case follows from Equation 17. We let $\mathbf{F}^{(t)}(v)$ denote
the representation of the color of node $v$ at iteration $t$. Initially, we
set $\mathbf{F}^{(t)}(v)=\mathbf{F}^{\prime}(v)$. Further, we define the
matrix $\mathbf{D}_{\text{emb}}\in\mathbb{R}^{n\times r}$ such that for the
$i$-th row of $\mathbf{D}_{\text{emb},i}=\text{deg}^{\prime}(v_{i})$, where
$v_{i}$ is the $i$-th node in a fixed but arbitrary node ordering. Hence, we
can write

$\mathbf{X}^{(0,1)}(v)=\begin{bmatrix}\mathbf{F}^{(0)}(v)&\mathbf{0}&\text{deg}^{\prime}(v)&\mathbf{P}^{\prime}(v)\end{bmatrix},$

for all $v\in V(G)$ and in matrix form

$\mathbf{X}^{(0,1)}=\begin{bmatrix}\mathbf{F}^{(0)}&\mathbf{0}&\mathbf{D}_{\text{emb}}&\mathbf{P}^{\prime}\end{bmatrix}.$

Now, assume that the statement holds up to iteration $t-1$. For the induction,
we show

$C^{1}_{t}(v)=C^{1}_{t}(w)\Longleftrightarrow\mathbf{F}^{(t)}(v)=\mathbf{F}^{(t)}(w).$
(18)

That is, we compute the $1$-WL-equivalent aggregation using the node color
representations $\mathbf{F}^{(t)}$ and use the remaining columns in
$\mathbf{X}^{(0,1)}$ to keep track of degree and structural embeddings.
Clearly, if Equation 18 holds for all $t$, then the statement follows.
Thereto, we aim to update the vertex representations such that

$\begin{split}\mathbf{X}^{(t,1)}&=\begin{bmatrix}\mathbf{F}^{(t)}&\mathbf{0}&\mathbf{D}_{\text{emb}}&\mathbf{P}^{\prime}\end{bmatrix}\end{split},$
(19)

where, following Lemma 27,

$\mathbf{F}^{(t)}\coloneqq\mathsf{FFN}\Big{(}\mathbf{F}^{(t-1)}+2\mathbf{A}(G)\mathbf{F}^{(t-1)}\Big{)}.$
(20)

Hence, it remains to show that our graph transformer layer can update vertex
representations according to Equation 19. To this end, we will require only a
single transformer head in each layer. Specifically, we want to compute

$\displaystyle h_{1}(\mathbf{X}^{(t-1,1)})$
$\displaystyle=\begin{bmatrix}\mathbf{0}&\mathbf{D}^{-1}\mathbf{A}(G))\mathbf{F}^{(t-1)}&\mathbf{0}&\mathbf{0}\end{bmatrix},$
(21)

where $\mathbf{D}^{-1}$ denotes the inverse of the degree matrix and
$\mathbf{I}$ denotes the identity matrix with $n$ rows. Note that since we
only have one head, the head dimension $d_{v}=d$. We begin by re-stating
Equation 8 with expanded sub-matrices and then derive the instances necessary
to obtain the head Equation 21. We re-state projection weights
$\mathbf{W}^{Q}$ and $\mathbf{W}^{K}$ with expanded sub-matrices as

$\mathbf{W}^{Q}=\begin{bmatrix}\mathbf{W}^{Q}_{1}\\\ \mathbf{W}^{Q}_{2}\\\
\mathbf{W}^{Q}_{3}\\\ \mathbf{W}^{Q}_{4}\end{bmatrix}$

and

$\mathbf{W}^{K}=\begin{bmatrix}\mathbf{W}^{K}_{1}\\\ \mathbf{W}^{K}_{2}\\\
\mathbf{W}^{K}_{3}\\\ \mathbf{W}^{K}_{4}\end{bmatrix},$

where $\mathbf{W}^{Q}_{1},\mathbf{W}^{K}_{1}\in\mathbb{R}^{p\times
d},\mathbf{W}^{Q}_{2},\mathbf{W}^{K}_{2}\in\mathbb{R}^{p\times
d},\mathbf{W}^{Q}_{3},\mathbf{W}^{K}_{3}\in\mathbb{R}^{r\times
d},\mathbf{W}^{Q}_{4},\mathbf{W}^{K}_{4}\in\mathbb{R}^{s\times d}$. We then
define

$\mathbf{Z}^{(t-1)}\coloneqq\frac{1}{\sqrt{d_{k}}}(\mathbf{X}^{(t-1,1)}\mathbf{W}^{Q})(\mathbf{X}^{(t-1,1)}\mathbf{W}^{K})^{T}=\frac{1}{\sqrt{d_{k}}}(\mathbf{X}^{(t-1,1)}\begin{bmatrix}\mathbf{W}^{Q}_{1}\\\
\mathbf{W}^{Q}_{2}\\\ \mathbf{W}^{Q}_{3}\\\
\mathbf{W}^{Q}_{4}\end{bmatrix})(\mathbf{X}^{(t-1,1)}\begin{bmatrix}\mathbf{W}^{K}_{1}\\\
\mathbf{W}^{K}_{2}\\\ \mathbf{W}^{K}_{3}\\\
\mathbf{W}^{K}_{4}\end{bmatrix})^{T},$

where

$\mathbf{X}^{(t-1,1)}=\begin{bmatrix}\mathbf{F}^{(t-1)}&\mathbf{0}&\mathbf{D}_{\text{emb}}&\mathbf{P}^{\prime}\end{bmatrix},$

by the induction hypothesis. By setting
$\mathbf{W}^{Q}_{1},\mathbf{W}^{Q}_{2},\mathbf{W}^{Q}_{3},\mathbf{W}^{K}_{1},\mathbf{W}^{K}_{2},\mathbf{W}^{K}_{3}$
to zero, we have

$\mathbf{Z}^{(t-1)}=\frac{1}{\sqrt{d_{k}}}(\mathbf{P}^{\prime}\mathbf{W}^{Q}_{4})(\mathbf{P}^{\prime}\mathbf{W}^{K}_{4})^{T}.$

Now, let

$\tilde{\mathbf{P}}\coloneqq\frac{1}{\sqrt{d_{k}}}(\mathbf{P}^{\prime}\mathbf{W}^{Q}_{P})(\mathbf{P}^{\prime}\mathbf{W}^{K}_{P})^{T},$

for some weight matrices $\mathbf{W}^{Q}_{P}$ and $\mathbf{W}^{K}_{P}$. We
know from Lemma 12 that, since $\mathbf{P}^{\prime}$ is sufficiently adjacency
reconstructing, there exists $\mathbf{W}^{Q}_{P}$ and $\mathbf{W}^{K}_{P}$
such that by setting $\mathbf{W}^{Q}_{4}=b\cdot\mathbf{W}^{Q}_{P}$ and
$\mathbf{W}^{K}_{4}=\mathbf{W}^{K}_{P}$, we have

$\mathbf{Z}^{(t-1)}=b\cdot\tilde{\mathbf{P}},$

where for all $\varepsilon>0$, there exists a $b>0$, such that

$\Big{\lVert}\mathsf{softmax}\Big{(}\mathbf{Z}^{(t-1)}\Big{)}-\mathbf{D}^{-1}\mathbf{A}(G)\Big{\rVert}_{F}<\varepsilon.$

Hence, by choosing a large enough $b$, we can approximate the matrix
$\mathbf{D}^{-1}\mathbf{A}(G)$ arbitrarily close. In the following, for
clarity of presentation, we assume
$\mathsf{softmax}\Big{(}\mathbf{Z}^{(t)}\Big{)}=\mathbf{D}^{-1}\mathbf{A}(G)$
although we only approximate it arbitrarily close. However, by choosing
$\varepsilon$ small enough, we can still approximate the matrix
$\mathbf{X}^{(t,1)}$, see below, arbitrarily close.

We now again expand sub-matrices of $\mathbf{W}^{V}$ and express Equation 8 as

$h_{i}(\mathbf{X}^{(t-1,1)})=\mathsf{softmax}\Big{(}\mathbf{Z}^{(t-1)}\Big{)}\mathbf{X}^{(t-1,1)}\begin{bmatrix}\mathbf{W}^{V}_{1}\\\
\mathbf{W}^{V}_{2}\\\ \mathbf{W}^{V}_{3}\\\ \mathbf{W}^{V}_{4}\end{bmatrix},$

where $\mathbf{W}^{V}_{1}\in\mathbb{R}^{p\times
d},\mathbf{W}^{V}_{2}\in\mathbb{R}^{p\times
d},\mathbf{W}^{V}_{3}\in\mathbb{R}^{r\times
d},\mathbf{W}^{V}_{4}\in\mathbb{R}^{s\times d}$. By setting

$\displaystyle\mathbf{W}^{V}_{1}$
$\displaystyle=\begin{bmatrix}\mathbf{0}&\mathbf{I}&\mathbf{0}&\mathbf{0}\end{bmatrix}$
$\displaystyle\mathbf{W}^{V}_{2}$
$\displaystyle=\mathbf{W}^{V}_{3}=\mathbf{W}^{V}_{4}=\mathbf{0},$

where $\mathbf{I}\in\mathbb{R}^{p\times p}$, we can approximate

$h_{1}(\mathbf{X}^{(t-1,1)})=\begin{bmatrix}\mathbf{0}&\mathbf{D}^{-1}\mathbf{A}(G)\mathbf{F}^{(t-1)}&\mathbf{0}&\mathbf{0}\end{bmatrix}$

arbitrarily close. We now conclude our proof as follows. Recall that the
transformer computes the final representation $\mathbf{X}^{(t,1)}$ as

$\begin{split}\mathbf{X}^{(t,1)}&=\mathsf{FFN}_{\text{final}}\Bigg{(}\mathbf{X}^{(t-1,1)}+h_{1}(\mathbf{X}^{(t-1,1)})\mathbf{W}^{O}\Bigg{)}\\\
&=\mathsf{FFN}_{\text{final}}\Bigg{(}\begin{bmatrix}\mathbf{F}^{(t-1)}&\mathbf{0}&\mathbf{D}_{\text{emb}}&\mathbf{U}\end{bmatrix}+\begin{bmatrix}\mathbf{0}&\mathbf{D}^{-1}\mathbf{A}(G)\mathbf{F}^{(t-1)}&\mathbf{0}&\mathbf{0}\end{bmatrix}\mathbf{W}^{O}\Bigg{)}\\\
&\underset{\mathbf{W}^{O}\coloneqq\mathbf{I}}{=}\mathsf{FFN}_{\text{final}}\Bigg{(}\begin{bmatrix}\mathbf{F}^{(t-1)}&\mathbf{D}^{-1}\mathbf{A}(G)\mathbf{F}^{(t-1)}&\mathbf{D}_{\text{emb}}&\mathbf{U}\end{bmatrix}\Bigg{)},\end{split}$

for some $\mathsf{FFN}_{\text{final}}$. We now show that there exists an
$\mathsf{FFN}_{\text{final}}$ such that

$\mathbf{X}^{(t,1)}=\mathsf{FFN}_{\text{final}}\Bigg{(}\begin{bmatrix}\mathbf{F}^{(t-1)}&\mathbf{D}^{-1}\mathbf{A}(G)\mathbf{F}^{(t-1)}&\mathbf{D}_{\text{emb}}&\mathbf{U}\end{bmatrix}\Bigg{)}=\begin{bmatrix}\mathbf{F}^{(t)}&\mathbf{0}&\mathbf{D}_{\text{emb}}&\mathbf{U}\end{bmatrix},$

which then implies the proof statement. To this end, we show that there exists
a composition of functions $f_{\text{FFN}}\circ f_{\text{add}}\circ
f_{\text{deg}}\circ f_{\times 2}$ such that

$f_{\text{FFN}}\circ f_{\text{add}}\circ f_{\text{deg}}\circ f_{\times
2}\Bigg{(}\begin{bmatrix}\mathbf{F}^{(t-1)}&\mathbf{D}^{-1}\mathbf{A}(G)\mathbf{F}^{(t-1)}&\mathbf{D}_{\text{emb}}&\mathbf{U}\end{bmatrix}\Bigg{)}=\begin{bmatrix}\mathbf{F}^{(t)}&\mathbf{0}&\mathbf{D}_{\text{emb}}&\mathbf{U}\end{bmatrix},$

where the functions are applied independently to each row. We denote

$\mathbf{X}^{(t-1)}_{\text{upd}}\coloneqq\begin{bmatrix}\mathbf{F}^{(t-1)}&\mathbf{D}^{-1}\mathbf{A}(G)\mathbf{F}^{(t-1)}&\mathbf{D}_{\text{emb}}&\mathbf{U}\end{bmatrix}\in\mathbb{R}^{n\times
d}$

and obtain for node $v\in V(G)$,

$\mathbf{X}^{(t-1)}_{\text{upd}}(v)=\begin{bmatrix}\mathbf{F}^{(t-1)}(v)&\sum_{w\in
N(v)}\frac{1}{|N(v)|}\cdot\mathbf{F}^{(t-1)}(w)&\text{deg}^{\prime}(v)&\mathbf{P}^{\prime}(v)\end{bmatrix}\in\mathbb{R}^{d}.$

We can now define

$\text{deg}^{\prime}(v)=\begin{bmatrix}|N(v)|&0\end{bmatrix}\in\mathbb{R}^{2}.$

Since our domain is compact, there exist choices of
$f_{\text{FFN}},f_{\text{add}},f_{\text{deg}},f_{\times 2}$ such that
$f_{\text{FFN}}\circ f_{\text{add}}\circ f_{\text{deg}}\circ f_{\times
2}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ is continuous. As a result,
$\mathsf{FFN}_{\text{final}}$ can approximate $f_{\text{FFN}}\circ
f_{\text{add}}\circ f_{\text{deg}}\circ f_{\times 2}$ arbitrarily close.

Concretely, we define

$\displaystyle f_{\times 2}\Bigg{(}$
$\displaystyle\begin{bmatrix}\mathbf{F}^{(t-1)}(v)&\sum_{w\in
N(v)}\frac{1}{|N(v)|}\cdot\mathbf{F}^{(t-1)}(w)&|N(v)|&0&\mathbf{P}^{\prime}(v)\end{bmatrix}\Bigg{)}$
$\displaystyle=\begin{bmatrix}\mathbf{F}^{(t-1)}(v)&2\sum_{w\in
N(v)}\frac{1}{|N(v)|}\cdot\mathbf{F}^{(t-1)}(w)&|N(v)|&0&\mathbf{P}^{\prime}(v)\end{bmatrix},$

where $f_{\times 2}$ multiplies the second column with $2$.

Next, we define

$\displaystyle f_{\text{deg}}\Bigg{(}$
$\displaystyle\begin{bmatrix}\mathbf{F}^{(t-1)}(v)&2\sum_{w\in
N(v)}\frac{1}{|N(v)|}\cdot\mathbf{F}^{(t-1)}(w)&|N(v)|&0&\mathbf{P}^{\prime}(v)\end{bmatrix}\Bigg{)}$
$\displaystyle=\begin{bmatrix}\mathbf{F}^{(t-1)}(v)&2\sum_{w\in
N(v)}\frac{1}{|N(v)|}\cdot\mathbf{F}^{(t-1)}_{j}\cdot|N(v)|&|N(v)|&\mathbf{P}^{\prime}(v)\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\mathbf{F}^{(t-1)}(v)&2\sum_{w\in
N(v)}\mathbf{F}^{(t-1)}(w)&|N(v)|&0&\mathbf{P}^{\prime}(v)\end{bmatrix}$

where $f_{\text{deg}}$ multiplies the second column with the degree of node
$v$ in the third column.

Next, we define

$\displaystyle f_{\text{add}}\Bigg{(}$
$\displaystyle\begin{bmatrix}\mathbf{F}^{(t-1)}(v)&2\sum_{w\in
N(v)}\mathbf{F}^{(t-1)}(w)&|N(v)|&0&\mathbf{P}^{\prime}(v)\end{bmatrix}\Bigg{)}$
$\displaystyle=\begin{bmatrix}\mathbf{F}^{(t-1)}(v)+2\sum_{w\in
N(v)}\mathbf{F}^{(t-1)}(w)&\mathbf{0}&|N(v)|&0&\mathbf{P}^{\prime}(v)\end{bmatrix},$

where we add the second column to the first column and set the elements of the
second column to zero.

Finally, we define

$\displaystyle f_{\text{FFN}}\Bigg{(}$
$\displaystyle\begin{bmatrix}\mathbf{F}^{(t-1)}(v)+2\sum_{w\in
N(v)}\mathbf{F}^{(t-1)}(w)&\mathbf{0}&|N(v)|&0&\mathbf{P}^{\prime}(v)\end{bmatrix}\Bigg{)}$
$\displaystyle=\begin{bmatrix}\mathsf{FFN}\Big{(}\mathbf{F}^{(t-1)}(v)+2\sum_{w\in
N(v)}\mathbf{F}^{(t-1)}(w)\Big{)}&\mathbf{0}&|N(v)|&0&\mathbf{P}^{\prime}(v)\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\mathbf{F}^{(t)}(v)&\mathbf{0}&\text{deg}^{\prime}(v)&\mathbf{P}^{\prime}(v)\end{bmatrix},$

where $\mathsf{FFN}$ denotes the FFN in Equation 20, from which the last
equality follows. Clearly, applying $f_{\text{FFN}}\circ f_{\text{add}}\circ
f_{\text{deg}}\circ f_{\times 2}$ to each row $i$ of
$\mathbf{X}^{(t-1)}_{\text{upd}}$ results in

$f_{\text{FFN}}\circ f_{\text{add}}\circ f_{\text{deg}}\circ f_{\times
2}\Big{(}\mathbf{X}^{(t-1)}_{\text{upd}}\Big{)}=\begin{bmatrix}\mathbf{F}^{(t)}&\mathbf{0}&\mathbf{D}_{\text{emb}}&\mathbf{P}^{\prime}(v)\end{bmatrix},$

from which our proof follows. ∎

##  Appendix I Expressivity of higher-order transformers

Here, we prove Theorem 4, Theorem 5, and Theorem 6 in Section 3.2 in the main
paper. To this end, we first construct new higher-order GNNs aligned with the
$k$-WL, $\delta$-$k$-WL, $\delta$-$k$-LWL, and $(k,s)$-WL, respectively. We
will use these higher-order GNNs as an intermediate step to show the
expressivity results for the $k$-GT and $(k,s)$-GT.

###  I.1 Higher-order GNNs

Here, we generalize the GNN from Grohe (2021) to higher orders $k$. Higher-
order GNNs with the same expressivity have been proposed in prior works by
Azizian & Lelarge (2021) and Morris et al. (2019). However, our GNNs have a
special form that can be computed by a transformer. To this end, we extend
Theorem VIII.4 in Grohe (2021) to the $k$-WL. Specifically, for each $k>1$ we
devise neural architectures with $k$-WL expressivity. Afterwards, we show that
transformers can simulate these architectures.

Formally, let $S\subset\mathbb{N}$ be a finite subset. First, we show that
multisets over $S$ can be injectively mapped to a value in the closed interval
$(0,1)$, which is a variant of Lemma VIII.5 in Grohe (2021). Here, we outline
a streamlined version of its proof, highlighting the key intuition behind
representing multisets as $m$-ary numbers. Let $M\subseteq S$ be a multiset
with multiplicities $a_{1},\dots,a_{k}$ and distinct $k$ values. We define the
order of the multiset as $\sum_{i=1}^{k}a_{i}$. We can write such a multiset
as a sequence $x^{(1)},\dots,x^{(l)}$ where $l$ is the order of the multiset.
Note that the order of the sequence is arbitrary and that for $i\neq j$ it is
possible to have $x^{(i)}=x^{(j)}$. We call such a sequence an $M$-sequence of
length $l$. We now prove the following, a slight variation of Grohe (2021).

######  Lemma 29.

For a finite $m\in\mathbb{N}$, let $M\subseteq S$ be a multiset of order $m-1$
and let $x_{i}\in S$ denote the $i$-th number in a fixed but arbitrary
ordering of $S$. Given a mapping $g\colon S\rightarrow(0,1)$ where

$g(x_{i})\coloneqq m^{-i},$

and an $M$-sequence of length $l$ given by $x^{(1)},\dots,x^{(l)}$ with
positions $i^{(1)},\dots,i^{(l)}$ in $S$, the sum

$\sum_{j\in[l]}g(x^{(j)})=\sum_{j\in[l]}m^{-i^{(j)}}$

is unique for every unique $M$.

###### Proof.

By assumption, let $M\subseteq S$ denote a multiset of order $m-1$. Further,
let $x^{(1)},\dots,x^{(l)}\in M$ be an $M$-sequence with
$i^{(1)},\dots,i^{(l)}$ in $S$. Given our fixed ordering of the numbers in $S$
we can equivalently write $M=((a_{1},x_{1}),\dots,(a_{n},x_{n}))$, where
$a_{i}$ denotes the multiplicity of $i$-th number in $M$ with position $i$
from our ordering over $S$. Note that for a number $m^{-i}$ there exists a
corresponding $m$-ary number written as

$0.0\ldots\underbrace{1}_{i}\ldots$

Then the sum,

$\displaystyle\sum_{j\in[l]}g(x^{(j)})$
$\displaystyle=\sum_{j\in[l]}m^{-i^{(j)}}$ $\displaystyle=\sum_{i\in
S}a_{i}m^{-i}\in(0,1)$

and in $m$-ary representation

$\displaystyle 0.a_{1}\ldots a_{n}.$

Note that $a_{i}=0$ if and only if there exists no $j$ such that $i^{(j)}=i$.
Since the order of $M$ is $m-1$, it holds that $a_{i}<m$. Hence, it follows
that the above sum is unique for each unique multiset $M$, implying the
result. ∎

Recall that $S\subseteq\mathbb{N}$ and that we fixed an arbitrary ordering
over $S$. Intuitively, we use the finiteness of $S$ to map each number therein
to a fixed digit of the numbers in $(0,1)$. The finite $m$ ensures that at
each digit, we have sufficient “bandwidth” to encode each $a_{i}$. Now that we
have seen how to encode multisets over $S$ as numbers in $(0,1)$, we review
some fundamental operations about the $m$-ary numbers defined above. We will
refer to decimal numbers $m^{-i}$ as corresponding to an $m$-ary number

$0.0\ldots\underbrace{1}_{i}\ldots,$

where the $i$-th digit after the decimal point is $1$ and all other digits are
$0$, and vice versa.

To begin with, addition between decimal numbers implements counting in $m$-ary
notation, i.e.,

$m^{-i}+m^{-j}\text{ corresponds to
}0.0\ldots\underbrace{1}_{i}\ldots\underbrace{1}_{j}\ldots,$

for digit positions $i\neq j$ and

$m^{-i}+m^{-j}\text{ corresponds to }0.0\ldots\underbrace{2}_{i=j}\ldots,$

otherwise. We used counting in the proof of the previous result to represent
the multiplicities of a multiset. Next, multiplication between decimal numbers
implements shifting in $m$-ary notation, i.e.,

$m^{-i}\cdot m^{-j}\text{ corresponds to
}0.0\ldots\underbrace{1}_{i+j}\ldots.$

Shifting further applies to general decimal numbers in $(0,1)$. Let
$x\in(0,1)$ correspond to an $m$-ary number with $l$ digits,

$0.a_{1}\ldots a_{l}.$

Then,

$m^{-i}\cdot x\text{ corresponds to }0.0\ldots 0\underbrace{a_{1}\ldots
a_{l}}_{i+1,\dots,i+l}.$

We continue by deriving a neural architecture simulating the $k$-WL.

######  Proposition 30.

Let $G=(V(G),E(G),\ell)$ be a $n$-order (node-)labeled graph. Then for all
$t\geq 1$, there exists a function $g^{(t)}$ and scalars
$\beta_{1},\dots,\beta_{k}$ with

$g^{(t)}(\mathbf{u})\coloneqq\mathsf{FFN}\Big{(}g^{(t-1)}(\mathbf{u})+\sum_{j\in[k]}\beta_{j}\cdot\sum_{w\in
V(G)}g^{(t-1)}(\phi_{j}(\mathbf{u},w))\Big{)},$

where $g^{(0)}(\mathbf{u})$ is initialized consistent $\ell$ consistent with
the atomic type, such that for all $\mathbf{u},\mathbf{v}\in V(G)^{k}$

$C_{t}^{k}(\mathbf{u})=C_{t}^{k}(\mathbf{v})\Longleftrightarrow
g^{(t)}(\mathbf{u})=g^{(t)}(\mathbf{v}).$ (22)

###### Proof.

Before we start, let us recall the relabeling computed by the $k$-WL for a
$k$-tuple $\mathbf{u}$ as

$\mathsf{RELABEL}\Big{(}C_{t}^{k}(\mathbf{u}),M_{1}^{(t)}(\mathbf{u}),\dots,M_{k}^{(t)}(\mathbf{u})\Big{)},$

with

$M_{j}^{(t)}(\mathbf{u})\coloneqq\\{\\!\\!\\{C_{t-1}^{k}(\phi_{j}(\mathbf{u},w))\mid
w\in V(G)\\}\\!\\!\\}.$

To show our result, we show that there exist scalars
$\beta_{1},\dots,\beta_{k}$ such that the $m$-ary representations computed for
$C_{t}^{k}(\mathbf{u})$ and $M_{1}^{(t)},\dots,M_{k}^{(t)}$ are pairwise
unique. To this end, we show that a weighted sum can represent multiset
counting in different exponent ranges of $m$-ary numbers in $(0,1)$. We then
simply invoke Lemma 29 to show that we can map each unique tuple
$(C_{t}^{k}(\mathbf{u}),M_{1}^{(t)}(\mathbf{u}),\dots,M_{k}^{(t)}(\mathbf{u}))$
to a unique number in $(0,1)$. Finally, the $\mathsf{FFN}$ will be responsible
for the relabeling.

Each possible color in $C^{k}_{t}$ is a unique number in $[n^{k}]$ as the
maximum possible number of unique colors in $C^{k}_{t}$ is $n^{k}$. We then
fix an arbitrary ordering over the $[n^{k}]$.

We show the statement via induction over $t$. Let $m>0$ such that $m-1$ is the
order of the multiset $M_{j}^{(0)}(\mathbf{u})$. Note that this is the same
$m$ for each $\mathbf{u}$. For a $k$-tuple $\mathbf{u}$ with initial color
$C^{k}_{0}(\mathbf{u})$ at position $i$, we choose $g^{(0)}$ such as to
approximate $m^{-i}$ arbitarily close, i.e.,

$\big{|}\big{|}g^{(0)}(\mathbf{u})-m^{-i}\big{|}\big{|}_{\text{F}}<\epsilon,$

for an arbitrarily small $\epsilon>0$. By choosing $\epsilon$ small enough, we
have that $g^{(0)}(\mathbf{u})$ is unique for every unique position $i$ and
hence Equation 22 holds for all pairs of $k$-tuples for $t=0$. Note that by
construction, $i\leq n^{k}$ and hence, for tuple $\mathbf{u}$ at position $i$,
the $m$-ary number corresponding to $m^{-i}$ is non-zero in at most the first
$n^{k}$ digits.

For the inductive case, we assume that

$C^{k}_{t-1}(\mathbf{u})=C^{k}_{t-1}(\mathbf{v})\Longleftrightarrow
g^{(t-1)}(\mathbf{u})=g^{(t-1)}(\mathbf{v}).$

Further, we assume that for tuple $\mathbf{u}$ at position $i$,

$\big{|}\big{|}g^{(t-1)}(\mathbf{u})-m^{-i}\big{|}\big{|}_{\text{F}}<\epsilon,$

for an arbitrarily small $\epsilon>0$. Let now $\mathbf{u}\in V(G)^{k}$. We
say that the $j$-neighbors of $\mathbf{u}$ w.r.t. $w$ have indices
$l^{(1)}(w),\dots,l^{(k)}(w)$ in our ordering. Then, $\sum_{w\in
V(G)}m^{-l^{(j)}(w)}$ is unique for each unique

$M_{j}^{(t)}(\mathbf{u})=\\{\\!\\!\\{C_{t}^{k}(\phi_{j}(\mathbf{u},w))\mid
w\in V(G)\\}\\!\\!\\},$ (23)

according to Lemma 29.

We now obtain a unique value for the tuple

$\Big{(}M_{1}^{(t)}(\mathbf{u}),\dots,M_{k}^{(t)}(\mathbf{u})\Big{)},$

by setting

$\beta_{j}\coloneqq m^{-(n^{k})\cdot j},$

for $j\in[k]$. Specifically, let $a_{1},\dots,a_{n^{k}}$ denote the
multiplicities of multiset $M_{j}^{(t)}(\mathbf{u})$ and let

$0.a_{1}\ldots a_{n^{k}},$

denote the $m$-ary number that corresponds to the sum

$\sum_{w\in V(G)}m^{-l^{(j)}(w)}.$

Note that since each $m^{-l^{(j)}(w)}$ corresponds to a color under $k$-WL at
iteration $t-1$, all digits after the $n^{k}$-th digit are zero. Then,
multiplying the above sum with $\beta_{j}$ results in a shift in $m$-ary
notation and, hence, for the $m$-ary number that corresponds to the term

$\beta_{j}\cdot\sum_{w\in V(G)}m^{-l^{(j)}(w)},$ (24)

we can write

$0.0\ldots\underbrace{0}_{n^{k}\cdot j}\,\,\underbrace{a_{1}\ldots
a_{n^{k}}}_{n^{k}\cdot j+1,\dots,n^{k}\cdot
j+n^{k}}\,\,\underbrace{0}_{n^{k}\cdot(j+1)+1}\ldots 0.$

As a result, for all $l\neq j$, the non-zero digits of the $m$-ary number that
corresponds to

$\beta_{l}\cdot\sum_{w\in V(G)}m^{-l^{(j)}(w)}$

do not collide with the non-zero digits of the output of Equation 24 and
hence, the sum

$\sum_{j\in[k]}\beta_{j}\cdot\sum_{w\in V(G)}m^{-l^{(j)}(w)},$ (25)

is unique for each unique tuple

$\Big{(}M_{1}^{(t)}(\mathbf{u}),\dots,M_{k}^{(t)}(\mathbf{u})\Big{)}.$

Let $\mathbf{u}_{i}$ be the $i$-th tuple in our fixed but arbitrary ordering.
Then, $g^{(t-1)}(\mathbf{u})$ approximates the number $m^{-i}$ arbitrarily
close. Note that by the induction hypothesis, the $m$-ary number that
corresponds to $m^{-i}$ is non-zero in at most the first $n^{k}$ digits, as
$n^{k}$ is the maximum possible number of colors attainable under $k$-WL.
Since the smallest shift in Equation 25 is by $n^{k}$ (for $j=1$) and since
the $m$-ary number that corresponds to $m^{-i}$ is non-zero in at most the
first $n^{k}$ digits, the sum of $m^{-i}$ and Equation 25 have no intersecting
non-zero digits. As a result,

$m^{-i}+\sum_{j\in[k]}\beta_{j}\cdot\sum_{w\in V(G)}m^{-l^{(j)}(w)}$ (26)

is unique for each tuple

$\Big{(}C_{t}^{k}(\mathbf{u}),M_{1}^{(t)}(\mathbf{u}),\dots,M_{k}^{(t)}(\mathbf{u})\Big{)}.$

Now, by the induction hypothesis, we can approximate each $m^{-i}$ with
$g^{(t-1)}(\mathbf{u}_{i})$ arbitrarily close. Further, we can approximate
each $m^{-l^{(j)}(w)}$ with $g^{(t-1)}(\phi_{j}(\mathbf{u},w))$ arbitrarily
close. As a result, we can approximate Equation 26 with

$g^{(t-1)}(\mathbf{u})+\sum_{j\in[k]}\beta_{j}\cdot\sum_{w\in
V(G)}g^{(t-1)}(\phi_{j}(\mathbf{u},w))$

arbitrarily close, i.e.,

$\big{|}\big{|}\Big{(}g^{(t-1)}(\mathbf{u})+\sum_{j\in[k]}\beta_{j}\cdot\sum_{w\in
V(G)}g^{(t-1)}(\phi_{j}(\mathbf{u},w))\Big{)}-\Big{(}m^{-i}+\sum_{j\in[k]}\beta_{j}\cdot\sum_{w\in
V(G)}m^{-l^{(j)}(w)}\Big{)}\big{|}\big{|}_{\text{F}}<\epsilon,$

for an arbitrarily small $\epsilon$. Hence, we by choosing $\epsilon$ small
enough,

$g^{(t-1)}(\mathbf{u})+\sum_{j\in[k]}\beta_{j}\cdot\sum_{w\in
V(G)}g^{(t-1)}(\phi_{j}(\mathbf{u},w))$

is also unique for each unique tuple

$\Big{(}C_{t}^{k}(\mathbf{u}),M_{1}^{(t)}(\mathbf{u}),\dots,M_{k}^{(t)}(\mathbf{u})\Big{)}.$

Finally, since for finite graphs of order $n$ there exists only a finite
number of such tuples, there exists a continuous function mapping the output
of Equation 26 to $m^{-i}$ where $i$ is the position of the color
$C^{k}_{t}(\mathbf{u})$ in $[n^{k}]$, for all $\mathbf{u}\in V(G)^{k}$. We
approximate this function with $\mathsf{FFN}$ arbitrarily close and obtain

$||g^{(t)}(\mathbf{u})-m^{-i}||<\epsilon,$

for an arbitrarily small $\epsilon>0$. This concludes the proof. ∎

We finish with a few Corollaries regarding variants of the $k$-WL.

######  Corollary 31.

Let $G=(V(G),E(G),\ell)$ be a $n$-order (node-)labeled graph. Then for each
$k$-tuple $\mathbf{u}\coloneqq(u_{1},\dots u_{k})$ and each $t>0$, we can
equivalently express the coloring of the $\delta$-$k$-WL as
$C^{\delta,k}_{t}(\mathbf{u})\coloneqq$

$\displaystyle\mathsf{RELABEL}\Big{(}C^{\delta,k}_{t-1}(\mathbf{u}),$
$\displaystyle\\{\\!\\!\\{C^{\delta,k}_{t-1}(\phi_{1}(\mathbf{u},w))\mid
w\in{N}(u_{1})\\}\\!\\!\\},\\{\\!\\!\\{C^{\delta,k}_{t-1}(\phi_{1}(\mathbf{u},w))\mid
w\in V(G)\setminus{N}(u_{1})\\}\\!\\!\\},\dots,$
$\displaystyle\\{\\!\\!\\{C^{\delta,k}_{t-1}(\phi_{k}(\mathbf{u},w))\mid
w\in{N}(u_{k})\\}\\!\\!\\},\\{\\!\\!\\{C^{\delta,k}_{t-1}(\phi_{k}(\mathbf{u},w))\mid
w\in V(G)\setminus{N}(u_{k})\\}\\!\\!\\}\Big{)}.$

With the above statement, we can directly derive a $\delta$-variant of
Proposition 30. To this end, let $\Delta_{j}(\mathbf{u})$ denote the set of
vertices adjacent to the $j$-th node in $\mathbf{u}$.

######  Corollary 32.

Let $G=(V(G),E(G),\ell)$ be a $n$-order (vertex-)labeled graph and assume a
vertex feature matrix $\mathbf{F}\in\mathbb{R}^{n\times d}$ that is consistent
with $\ell$. Then for all $t\geq 1$, there exists a function $g^{(t)}$ and
scalars $\beta_{1},\dots,\beta_{2k}$ with

$g^{(t)}(\mathbf{u})\coloneqq\mathsf{FFN}\Big{(}g^{(t-1)}(\mathbf{u})+\sum_{j\in[k]}\Big{(}\alpha_{j}\cdot\sum_{w\in\Delta_{j}(\mathbf{u})}g^{(t-1)}(\phi_{j}(\mathbf{u},w))\,+\,\beta_{j}\cdot\sum_{w\in
V(G)\setminus\Delta_{j}(\mathbf{u})}g^{(t-1)}(\phi_{j}(\mathbf{u},w)\Big{)}\Big{)},$

such that for all $\mathbf{u},\mathbf{v}\in V(G)^{k}$

$C^{k,\text{M}}_{t}(\mathbf{u})=C^{k,\text{M}}_{t}(\mathbf{v})\Longleftrightarrow
g^{(t)}(\mathbf{u})=g^{(t)}(\mathbf{v}).$ (27)

The proof is the same as for Proposition 30. Further, we can also recover the
$\delta$-$k$-LWL variant of Proposition 30 by setting $\beta_{j}=0$. Lastly,
we again recover Proposition 30 by setting $\alpha_{j}=\beta_{j}$.

###  I.2 Higher-order pure transformers

Here, we use the results from the previous section to show the expressivity
results for Theorem 4, Theorem 5 and Theorem 6 in the main paper. In fact, we
prove a slightly stronger result than Theorem 4 from which then also Theorem 5
and Theorem 6 will follow directly.

######  Theorem 33 (Generalization of Theorem 4 in main paper).

Let $G=(V(G),E(G),\ell)$ be a labeled graph with $n$ nodes and $k\geq 2$ and
$\mathbf{F}\in\mathbb{R}^{n\times d}$ be a node feature matrix consistent with
$\ell$. Let $C^{k}_{t}$ denote the coloring function of the $k$-WL,
$\delta$-$k$-WL, or $\delta$-$k$-LWL at iteration $t$. Then for all iterations
$t\geq 0$, there exists a parametrization of the $k$-GT such that

$C^{k}_{t}(\mathbf{v})=C^{k}_{t}(\mathbf{w})\Longleftrightarrow\mathbf{X}^{(t,k)}(\mathbf{v})=\mathbf{X}^{(t,k)}(\mathbf{w})$

for all $k$-tuples $\mathbf{v}$ and $\mathbf{w}\in V(G)^{k}$. If $C^{k}_{t}$
is the coloring function of the $k$-WL, it suffices that the structural
embeddings of $k$-GT are sufficiently node-identifying. Otherwise, we require
the structural embeddings of $k$-GT to be both sufficiently node and
adjacency-identifying.

###### Proof.

We begin by recalling Equation 4 as

$\mathbf{X}^{(0,k)}(\mathbf{v})\coloneqq\big{[}\mathbf{F}(v_{i})\big{]}_{i=1}^{k}\mathbf{W}^{F}+\big{[}\mathbf{P}(v_{i})\big{]}_{i=1}^{k}\mathbf{W}^{P}+\text{atp}(\mathbf{v}),$

where $\mathbf{P}$ are structural embeddings and atp is a learnable embedding
of the atomic type. We further know from Lemma 26 that we can write

$\mathbf{X}^{(0,k)}(\mathbf{v})=\begin{bmatrix}\mathbf{F}^{\prime}(v_{1})\,\,\,\,\dots\,\,\,\,\mathbf{F}^{\prime}(v_{k})&\mathbf{0}&\text{deg}^{\prime}(v_{1})&\dots&\text{deg}^{\prime}(v_{k})&\mathbf{P}^{\prime}(v_{1})&\dots&\mathbf{P}^{\prime}(v_{k})&\text{atp}^{\prime}(\mathbf{v})\end{bmatrix},$
(28)

where it holds for every $v,w\in V(G)$,

$\mathbf{F}(v)=\mathbf{F}(w)\Longleftrightarrow\mathbf{F}^{\prime}(v)=\mathbf{F}^{\prime}(w)$

and

$\text{deg}(v)=\text{deg}(w)\Longleftrightarrow\text{deg}^{\prime}(v)=\text{deg}^{\prime}(w)$

and

$\mathbf{P}(v)=\mathbf{P}(w)\Longleftrightarrow\mathbf{P}^{\prime}(v)=\mathbf{P}^{\prime}(w)$

where $\mathbf{P}^{\prime}(v)$ is sufficiently node and adjacency-identifying
and for every $\mathbf{v},\mathbf{w}\in V(G)^{k}$

$\text{atp}(\mathbf{v})=\text{atp}(\mathbf{w})\Longleftrightarrow\text{atp}^{\prime}(\mathbf{v})=\text{atp}^{\prime}(\mathbf{w}).$

Further, $\mathbf{F}^{\prime}(v)\in\mathbb{R}^{p}$,
$\mathbf{0}\in\mathbb{R}^{k^{2}\cdot p}$,
$\text{deg}^{\prime}\colon\mathbb{N}\rightarrow\mathbb{R}^{r}$,
$\text{atp}^{\prime}\colon\mathbb{N}\rightarrow\mathbb{R}^{o}$ and
$\mathbf{P}^{\prime}\in\mathbb{R}^{s}$, for some choice of $p,r,s,o$ where
$d=k^{2}\cdot p+k\cdot p+k\cdot r+k\cdot s+o$, as specified in Lemma 26. We
will use this parameterization for $\mathbf{X}^{(0,k)}$ throughout the rest of
the proof.

We prove our statement by induction over iteration $t$. For the base case,
notice that the initial color of a tuple $\mathbf{v}$ depends on the atomic
type and the node labeling. In Equation 28, we encode the atomic type with
$\text{atp}^{\prime}(\mathbf{v})$ and the node labels by concatenating the
features $\mathbf{F}^{\prime}(v_{1}),\dots,\mathbf{F}^{\prime}(v_{k})$ of the
$k$ nodes $v_{1},\dots,v_{k}$ in $\mathbf{v}$. The concatenation of both node
labels and atomic type is clearly injective, and so

$C^{k}_{0}(\mathbf{v})=C^{k}_{0}(\mathbf{w})\Longleftrightarrow\mathbf{X}^{(0,k)}(\mathbf{v})=\mathbf{X}^{(0,k)}(\mathbf{w})$

for any two $\mathbf{v},\mathbf{w}\in V(G)^{k}$.

Before continuing with the induction, we define some additional notation.
Throughout the induction, we will denote the color representation of a tuple
$\mathbf{v}$ at iteration $t$ as $\mathbf{F}^{(t)}(\mathbf{v})$. Further, we
initially define
$\mathbf{F}^{(0)}(\mathbf{v})=\big{[}\mathbf{F}^{\prime}(v_{i})\big{]}_{i=1}^{k}$,
$\text{deg}^{\prime}(\mathbf{v})=\big{[}\text{deg}^{\prime}(v_{i})\big{]}_{i=1}^{k}$
and
$\mathbf{P}^{\prime}(\mathbf{v})=\big{[}\mathbf{P}^{\prime}(v_{i})\big{]}_{i=1}^{k}$.
Hence, we can rewrite

$\mathbf{X}^{(0,k)}(\mathbf{v})=\begin{bmatrix}\mathbf{F}^{(0)}(\mathbf{v})&\mathbf{0}&\text{deg}^{\prime}(\mathbf{v})&\mathbf{P}^{\prime}(\mathbf{v})&\text{atp}^{\prime}(\mathbf{v})\end{bmatrix}.$

For the induction step, we show

$C^{k}_{t}(\mathbf{v})=C^{k}_{t}(\mathbf{w})\Longleftrightarrow\mathbf{X}^{(t,k)}(\mathbf{v})=\mathbf{X}^{(t,k)}(\mathbf{w}),$
(29)

that is we compute the $k$-WL-, $\delta$-$k$-LWL, or $\delta$-$k$-WL-
equivalent aggregation. Clearly, if Equation 29 holds for all $t$, then the
proof statement follows. Thereto, we show that the standard transformer
updates the tuple representation of tuple
$\mathbf{u}_{i}=(u_{1},\dots,u_{k})$, following Corollary 32, as

$\mathbf{X}^{(t,k)}(\mathbf{u}_{i})=\begin{bmatrix}\mathsf{FFN}\Big{(}\mathbf{F}^{(t-1)}(\mathbf{u}_{i})+H(\mathbf{X}^{(t-1,k)}(\mathbf{u}_{i}))\Big{)}&\mathbf{0}&\text{deg}^{\prime}(\mathbf{u}_{i})&\mathbf{P}^{\prime}(\mathbf{u}_{i})&\text{atp}^{\prime}(\mathbf{u}_{i})\end{bmatrix},$
(30)

where

$H(\mathbf{X}^{(t-1,k)}(\mathbf{u}_{i}))\coloneqq\sum_{j\in[k]}\Big{(}\alpha_{j}\cdot\sum_{w\in\Delta_{j}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{j}(\mathbf{u}_{i},w))+\beta_{j}\cdot\sum_{w\in
V(G)\setminus\Delta_{j}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{j}(\mathbf{u}_{i},w))\Big{)},$

for $\alpha_{1},\dots,\alpha_{k},\beta_{1},\dots,\beta_{k}\in\mathbb{R}$, for
$j\in[k]$ that we pick such that $H(\mathbf{X}^{(t-1,k)}(\mathbf{u}_{i}))$ is
equivalent to the neural architecture in Corollary 32. Note that we obtain the
$k$-WL for $\alpha_{j}=\beta_{j}$ for all $j\in[k]$. Then,

$H(\mathbf{X}^{(t-1,k)}(\mathbf{u}_{i}))=\sum_{j\in[k]}\Big{(}\beta_{j}\cdot\sum_{w\in
V(G)}\mathbf{F}^{(t-1)}(\phi_{j}(\mathbf{u}_{i},w))\Big{)}.$

Further, we obtain $\delta$-$k$-LWL for $\beta_{j}=0$ for all $j\in[k]$. Then,

$H(\mathbf{X}^{(t-1,k)}(\mathbf{u}_{i}))=\sum_{j\in[k]}\Big{(}\alpha_{j}\cdot\sum_{w\in\Delta_{j}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{j}(\mathbf{u}_{i},w))\Big{)}.$

Hence, it remains to show that the standard transformer layer can update tuple
representations according to Equation 30. To this end, we will require $2k$
transformer heads $h^{1}_{1},\dots h^{1}_{k},h^{2}_{1},\dots h^{2}_{k}$ in
each layer. Specifically, in the first $k$ heads, we want to compute

$h^{1}_{j}(\mathbf{X}^{(t-1,k)}(\mathbf{u}_{i}))=\alpha_{j}\cdot\sum_{w\in\Delta_{j}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{j}(\mathbf{u}_{i},w)).$
(31)

In the remaining $k$ heads, we want to compute

$h^{2}_{j}(\mathbf{X}^{(t-1,k)}(\mathbf{u}_{i}))=\beta_{j}\cdot\sum_{w\in
V(G)\setminus\Delta_{j}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{j}(\mathbf{u}_{i},w)).$
(32)

In both of the above cases, for a head $h^{\gamma}_{j}$, $\gamma\in\\{-1,1\\}$
denotes the type of head, and $j\in[k]$ denotes the $j$-neighbors the head
aggregates over. For the head dimension, we set $d_{v}=d$.

For each $j$, recall the definition of the standard transformer head at tuple
$\mathbf{u}_{i}$ at position $i$ as

$h^{\gamma}_{j}(\mathbf{X}^{(t-1,k)}(\mathbf{u}_{i}))=\mathsf{softmax}\Big{(}\begin{bmatrix}\mathbf{Z}_{i1}^{(t-1,\gamma)}&\dots&\mathbf{Z}_{in^{k}}^{(t-1,\gamma)}\end{bmatrix}\Big{)}\begin{bmatrix}\mathbf{X}^{t-1}(\mathbf{u}_{1})&\dots&\mathbf{X}^{t-1}(\mathbf{u}_{n^{k}})\end{bmatrix}^{T}\mathbf{W}^{V},$

where

$\mathbf{Z}_{il}^{(t-1,\gamma)}\coloneqq\frac{1}{\sqrt{d_{k}}}(\mathbf{X}^{(t-1,k)}(\mathbf{u}_{i})\mathbf{W}^{Q,\gamma})(\mathbf{X}^{(t-1,k)}(\mathbf{u}_{l})\mathbf{W}^{K,\gamma})^{T}\in\mathbb{R}$
(33)

is the unnormalized attention score between tuples $\mathbf{u}_{i}$ and
$\mathbf{u}_{l}$, with

$\mathbf{X}^{(t-1,k)}(\mathbf{u}_{i})=\begin{bmatrix}\mathbf{F}^{(t-1)}(\mathbf{u}_{i})&\mathbf{0}&\text{deg}^{\prime}(\mathbf{u}_{i})&\mathbf{P}^{\prime}(\mathbf{u}_{i})&\text{atp}^{\prime}(\mathbf{u}_{i})\end{bmatrix}$

for all $i\in[n^{k}]$ and

$\displaystyle\mathbf{W}^{Q,\gamma}$
$\displaystyle=\begin{bmatrix}\mathbf{W}^{Q}_{F}\\\ \mathbf{W}^{Q}_{Z}\\\
\mathbf{W}^{Q}_{D}\\\ \mathbf{W}^{Q,\gamma}_{P}\\\
\mathbf{W}^{Q}_{A}\end{bmatrix}$ $\displaystyle\mathbf{W}^{K,\gamma}$
$\displaystyle=\begin{bmatrix}\mathbf{W}^{K}_{F}\\\ \mathbf{W}^{K}_{Z}\\\
\mathbf{W}^{K}_{D}\\\ \mathbf{W}^{K,\gamma}_{P}\\\ \mathbf{W}^{K}_{A}\\\
\end{bmatrix}$ $\displaystyle\mathbf{W}^{V}$
$\displaystyle=\begin{bmatrix}\mathbf{W}^{V}_{F}\\\ \mathbf{W}^{V}_{Z}\\\
\mathbf{W}^{V}_{D}\\\ \mathbf{W}^{V}_{P}\\\ \mathbf{W}^{V}_{A}\\\
\end{bmatrix},$

where

$\displaystyle\mathbf{F}^{(t-1)}(\mathbf{u}_{i})$ $\displaystyle\text{ is
projected by }\mathbf{W}^{Q}_{F},\mathbf{W}^{K}_{F},\mathbf{W}^{V}_{F},$
$\displaystyle\mathbf{0}$ $\displaystyle\text{ is projected by
}\mathbf{W}^{Q}_{Z},\mathbf{W}^{K}_{Z},\mathbf{W}^{V}_{Z},$
$\displaystyle\text{deg}^{\prime}(\mathbf{u}_{i})$ $\displaystyle\text{ is
projected by }\mathbf{W}^{Q}_{D},\mathbf{W}^{K}_{D},\mathbf{W}^{V}_{D},$
$\displaystyle\mathbf{P}^{\prime}(\mathbf{u}_{i})$ $\displaystyle\text{ is
projected by
}\mathbf{W}^{Q,\gamma}_{P},\mathbf{W}^{K,\gamma}_{P},\mathbf{W}^{V}_{P},$
$\displaystyle\text{atp}^{\prime}(\mathbf{u}_{i})$ $\displaystyle\text{ is
projected by }\mathbf{W}^{Q}_{A},\mathbf{W}^{K}_{A},\mathbf{W}^{V}_{A}.$

Note that only sub-matrices $\mathbf{W}^{Q,\gamma}_{P}$ and
$\mathbf{W}^{K,\gamma}_{P}$ are different for different $\gamma$. We now
specify projection matrices $\mathbf{W}^{Q,\gamma}$, $\mathbf{W}^{K,\gamma}$
and $\mathbf{W}^{V}$ in a way that allows the attention head $h^{\gamma}_{j}$
to dynamically recover the $j$-neighborhood adjacency as well as the adjacency
between $j$-neighbors in the attention matrix. To this end, in heads
$h^{1}_{j}$ and $h^{2}_{j}$ we set

$\displaystyle\mathbf{W}^{Q}_{F}=\mathbf{W}^{K}_{F}$
$\displaystyle=\mathbf{0}$
$\displaystyle\mathbf{W}^{Q}_{Z}=\mathbf{W}^{K}_{Z}=\mathbf{W}^{V}_{Z}$
$\displaystyle=\mathbf{0}$ $\displaystyle\mathbf{W}^{V}_{P}$
$\displaystyle=\mathbf{0}$
$\displaystyle\mathbf{W}^{Q}_{D}=\mathbf{W}^{K}_{D}=\mathbf{W}^{V}_{D}$
$\displaystyle=\mathbf{0}$
$\displaystyle\mathbf{W}^{Q}_{A}=\mathbf{W}^{K}_{A}=\mathbf{W}^{V}_{A}$
$\displaystyle=\mathbf{0}.$

The remaining non-zero sub-matrices are
$\mathbf{W}^{V}_{F},\mathbf{W}^{Q,\gamma}_{P},\mathbf{W}^{K,\gamma}_{P}$,
which we will define next.

We begin by defining $\mathbf{W}^{Q,\gamma}_{P}$ and
$\mathbf{W}^{K,\gamma}_{P}$. Specifically, we want to choose
$\mathbf{W}^{Q,\gamma}_{P}$ and $\mathbf{W}^{K,\gamma}_{P}$ such that the
attention matrix in head $h^{\gamma}_{j}$ can approximate the generalized
adjacency matrix $\mathbf{A}^{(k,j,\gamma)}$ in Equation 11. To this end, we
simply invoke Lemma 13, guaranteeing that there exists
$\mathbf{W}^{Q,\gamma}_{P}$ and $\mathbf{W}^{K,\gamma}_{P}$ such that that for
each $\epsilon>0$ and each $\gamma\in\\{-1,1\\}$,

$\Big{\lVert}\mathsf{softmax}\Big{(}\begin{bmatrix}\mathbf{Z}_{i1}^{(t-1,\gamma)}&\dots&\mathbf{Z}_{in^{k}}^{(t-1,\gamma)}\end{bmatrix}\Big{)}-\tilde{\mathbf{A}}^{(k,j,\gamma)}_{i}\Big{\rVert}_{F}<\varepsilon,$

i.e., we can approximate the generalized adjacency matrix arbitrarily close
for each $k>1,j\in[k]$ and $\gamma\in\\{-1,1\\}$. In the following, for
clarity of presentation, we assume

$\mathsf{softmax}\Big{(}\begin{bmatrix}\mathbf{Z}_{i1}^{(t-1,\gamma)}&\dots&\mathbf{Z}_{in^{k}}^{(t-1,\gamma)}\end{bmatrix}\Big{)}=\tilde{\mathbf{A}}^{(k,j,\gamma)}_{i}$

although we only approximate it arbitrarily close. However, by choosing
$\varepsilon$ small enough, we can still approximate the matrix
$\mathbf{X}^{(t,k)}$, see below, arbitrarily close. We now set

$\mathbf{W}^{V}=\begin{bmatrix}\mathbf{I}_{n\times
kp}&\mathbf{0}\end{bmatrix},$

where $\mathbf{I}_{n\times kp}$ denotes the first $n$ rows of the $kp$-by-$kp$
identity matrix if $kp>n$ or else the first $kp$ columns of the $n$-by-$n$
identity matrix and $\mathbf{0}\in\mathbb{R}^{n\times d-kp}$ is an all-zero
matrix. The above yields

$\begin{split}h^{\gamma}_{j}(\mathbf{X}^{(t-1,k)}(\mathbf{u}_{i}))&=\frac{1}{d^{\gamma}_{ij}}\begin{bmatrix}\tilde{\mathbf{A}}^{(k,j,\gamma)}_{i1}&\dots&\tilde{\mathbf{A}}^{(k,j,\gamma)}_{in^{k}}\end{bmatrix}\cdot\begin{bmatrix}\mathbf{F}^{(t-1)}(\mathbf{u}_{1})\\\
\vdots\\\ \mathbf{F}^{(t-1)}(\mathbf{u}_{n^{k}})\end{bmatrix}\\\ \\\
&=\frac{1}{d^{\gamma}_{ij}}\cdot\begin{cases}\sum_{w\in\Delta_{j}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{j}(\mathbf{u}_{i},w))&\gamma=1\\\
\\\ \sum_{w\in
V(G)\setminus\Delta_{j}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{j}(\mathbf{u}_{i},w))&\gamma=-1\\\
\end{cases},\end{split}$

where

$d^{\gamma}_{ij}=\begin{cases}d_{ij}&\gamma=1\\\
n-d_{ij}&\gamma=-1\end{cases}$

with $d_{ij}$ the degree of node $u_{j}$ in $k$-tuple
$\mathbf{u}_{i}=(u_{1},\dots,u_{k})$.

We now conclude our proof as follows. Recall that the standard transformer
layer computes the final representation $\mathbf{X}^{(t,k)}(\mathbf{u}_{i})$
as

$\mathbf{X}^{(t,k)}(\mathbf{u}_{i})=\mathsf{FFN}\Bigg{(}\mathbf{X}^{(t-1,k)}(\mathbf{u}_{i})+\begin{bmatrix}h^{1}_{1}(\mathbf{X}^{(t-1,k)})(\mathbf{u}_{i})\\\
\vdots\\\ h^{1}_{k}(\mathbf{X}^{(t-1,k)})(\mathbf{u}_{i})\\\
h^{2}_{1}(\mathbf{X}^{(t-1,k)})(\mathbf{u}_{i})\\\ \vdots\\\
h^{2}_{k}(\mathbf{X}^{(t-1,k)})(\mathbf{u}_{i})\end{bmatrix}^{T}\mathbf{W}^{O}\Bigg{)}.$

We can now satisfy the requirements in Equation 31 and Equation 32 as follows.

Recall that for the first $k$ heads we set $\gamma=1$, in the remaining $k$
heads we set $\gamma=-1$. Further, since we have $2k$ heads,
$\mathbf{W}^{O}\in\mathbb{R}^{2k\cdot d_{v}\times d}$. We set

$\mathbf{W}^{O}_{ij}=\begin{cases}\alpha_{j}&kp<i=j\leq k+kp\\\
\beta_{j}&k+kp<i=j\leq 2k+kp\\\ 0&\text{ else},\end{cases}$

i.e., we leave the first $kp$ diagonal elements zero and then fill the next
$2k$ diagonal elements of $\mathbf{W}^{O}$ with the $\alpha_{j}$ and
$\beta_{j}$, respectively. All other elements are $0$. We now obtain

$\displaystyle\begin{bmatrix}h^{1}_{1}(\mathbf{X}^{(t-1,k)})(\mathbf{u}_{i})\\\
\vdots\\\ h^{1}_{k}(\mathbf{X}^{(t-1,k)})(\mathbf{u}_{i})\\\
h^{2}_{1}(\mathbf{X}^{(t-1,k)})(\mathbf{u}_{i})\\\ \vdots\\\
h^{2}_{k}(\mathbf{X}^{(t-1,k)})(\mathbf{u}_{i})\end{bmatrix}^{T}\mathbf{W}^{O}$
$\displaystyle=\begin{bmatrix}\frac{\alpha_{1}}{d_{i1}}\sum_{w\in\Delta_{1}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{1}(\mathbf{u}_{i},w))\\\
\vdots\\\
\frac{\alpha_{k}}{d_{ik}}\sum_{w\in\Delta_{k}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{k}(\mathbf{u}_{i},w))\\\
\frac{\beta_{1}}{n-d_{i1}}\sum_{w\in
V(G)\setminus\Delta_{1}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{1}(\mathbf{u}_{i},w))\\\
\vdots\\\ \frac{\beta_{k}}{n-d_{ik}}\sum_{w\in
V(G)\setminus\Delta_{k}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{k}(\mathbf{u}_{i},w))\end{bmatrix}^{T}\mathbf{W}^{O}$
$\displaystyle=\begin{bmatrix}\mathbf{0}\\\
\frac{\alpha_{1}}{d_{i1}}\sum_{w\in\Delta_{1}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{1}(\mathbf{u}_{i},w))\\\
\vdots\\\
\frac{\alpha_{k}}{d_{ik}}\sum_{w\in\Delta_{k}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{k}(\mathbf{u}_{i},w))\\\
\frac{\beta_{1}}{n-d_{i1}}\sum_{w\in
V(G)\setminus\Delta_{1}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{1}(\mathbf{u}_{i},w))\\\
\vdots\\\ \frac{\beta_{k}}{n-d_{ik}}\sum_{w\in
V(G)\setminus\Delta_{k}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{k}(\mathbf{u}_{i},w))\\\
\mathbf{0}\end{bmatrix}^{T},$

where the first zero vector is in $\mathbb{R}^{kp}$ and the second zero vector
is in $\mathbb{R}^{d-k(r+s)+o}$. We now define the vector

$\begin{split}\tilde{\mathbf{X}}(\mathbf{u}_{i})&=\begin{bmatrix}\mathbf{F}^{(t-1)}(\mathbf{u}_{i})\\\
\mathbf{0}\\\ \text{deg}^{\prime}(\mathbf{u}_{i})\\\
\mathbf{P}^{\prime}(\mathbf{u}_{i})\\\
\text{atp}^{\prime}(\mathbf{u}_{i})\end{bmatrix}^{T}+\begin{bmatrix}\mathbf{0}\\\
\frac{\alpha_{1}}{d_{i1}}\sum_{w\in\Delta_{1}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{1}(\mathbf{u}_{i},w))\\\
\vdots\\\
\frac{\alpha_{k}}{d_{ik}}\sum_{w\in\Delta_{k}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{k}(\mathbf{u}_{i},w))\\\
\frac{\beta_{1}}{n-d_{i1}}\sum_{w\in
V(G)\setminus\Delta_{1}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{1}(\mathbf{u}_{i},w))\\\
\vdots\\\ \frac{\beta_{k}}{n-d_{ik}}\sum_{w\in
V(G)\setminus\Delta_{k}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{k}(\mathbf{u}_{i},w))\\\
\mathbf{0}\end{bmatrix}^{T}\\\
&=\begin{bmatrix}\mathbf{F}^{(t-1)}(\mathbf{u}_{i})\\\
\frac{\alpha_{1}}{d_{i1}}\sum_{w\in\Delta_{1}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{1}(\mathbf{u}_{i},w))\\\
\vdots\\\
\frac{\alpha_{k}}{d_{ik}}\sum_{w\in\Delta_{k}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{k}(\mathbf{u}_{i},w))\\\
\frac{\beta_{1}}{n-d_{i1}}\sum_{w\in
V(G)\setminus\Delta_{1}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{1}(\mathbf{u}_{i},w))\\\
\vdots\\\ \frac{\beta_{k}}{n-d_{ik}}\sum_{w\in
V(G)\setminus\Delta_{k}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{k}(\mathbf{u}_{i},w))\\\
\text{deg}^{\prime}(\mathbf{u}_{i})\\\ \mathbf{P}^{\prime}(\mathbf{u}_{i})\\\
\text{atp}^{\prime}(\mathbf{u}_{i})\end{bmatrix}^{T}\in\mathbb{R}^{d}.\end{split}$

To simplify terms, we additionally define

$\tilde{\mathbf{F}}^{\alpha}(\mathbf{u}_{i})\coloneqq\begin{bmatrix}\frac{\alpha_{1}}{d_{i1}}\sum_{w\in\Delta_{1}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{1}(\mathbf{u}_{i},w))\\\
\vdots\\\
\frac{\alpha_{k}}{d_{ik}}\sum_{w\in\Delta_{k}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{k}(\mathbf{u}_{i},w))\end{bmatrix}^{T}$

and

$\tilde{\mathbf{F}}^{\beta}(\mathbf{u}_{i})\coloneqq\begin{bmatrix}\frac{\beta_{1}}{n-d_{i1}}\sum_{w\in
V(G)\setminus\Delta_{1}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{1}(\mathbf{u}_{i},w))\\\
\vdots\\\ \frac{\beta_{k}}{n-d_{ik}}\sum_{w\in
V(G)\setminus\Delta_{k}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{k}(\mathbf{u}_{i},w))\end{bmatrix}^{T}$

and consequently, we can write

$\tilde{\mathbf{X}}(\mathbf{u}_{i})=\begin{bmatrix}\mathbf{F}^{(t-1)}(\mathbf{u}_{i})\\\
\tilde{\mathbf{F}}^{\alpha}(\mathbf{u}_{i})\\\
\tilde{\mathbf{F}}^{\beta}(\mathbf{u}_{i})\\\
\text{deg}^{\prime}(\mathbf{u}_{i})\\\ \mathbf{P}^{\prime}(\mathbf{u}_{i})\\\
\text{atp}^{\prime}(\mathbf{u}_{i})\end{bmatrix}^{T}$

We additionally define

$\text{deg}^{\prime}(u_{j})=\begin{bmatrix}d_{ij}&n-d_{ij}\end{bmatrix}\in\mathbb{R}^{2},$

where $d_{ij}$ is again the degree of node $u_{j}$ in $k$-tuple
$\mathbf{u}_{i}=(u_{1},\dots,u_{k})$. Note that
$\tilde{\mathbf{X}}(\mathbf{u}_{i})$ represents all the information we feed
into the final $\mathsf{FFN}$. Specifically, we obtain the updated
representation of tuple $\mathbf{u}_{i}$ as

$\mathbf{X}^{(t,k)}(\mathbf{u}_{i})=\mathsf{FFN}\Big{(}\tilde{\mathbf{X}}(\mathbf{u}_{i})\Big{)}.$

We now show that there exists an $\mathsf{FFN}$ such that

$\displaystyle\mathbf{X}^{(t,k)}$
$\displaystyle=\mathsf{FFN}\Big{(}\tilde{\mathbf{X}}(\mathbf{u}_{i})\Big{)}$
$\displaystyle=\begin{bmatrix}\mathbf{F}^{(t)}(\mathbf{u}_{i})&\mathbf{0}&\text{deg}^{\prime}(\mathbf{u}_{i})&\mathbf{P}^{\prime}(\mathbf{u}_{i})&\text{atp}^{\prime}(\mathbf{u}_{i})\end{bmatrix},$

which then implies the proof statement. It is worth to pause at this point and
remind ourselves what each element in $\tilde{\mathbf{X}}(\mathbf{u}_{i})$
represents. To this end, we use PyTorch-like array slicing, i.e., for a vector
$\mathbf{x}$, $\mathbf{x}[a:b]$ corresponds to the sub-vector of length $b-a$
for $b>a$ containing the $(a+1)$-st to $b$-th element of $\mathbf{x}$. E.g.,
for a vector $\mathbf{x}=(x_{1},x_{2},x_{3},x_{4},x_{5})^{T}$,
$\mathbf{x}[1:4]=(x_{2},x_{3},x_{4})^{T}$. Now, we interpret
$\tilde{\mathbf{X}}(\mathbf{u}_{i})$ by its sub-vectors. Concretely,

  1. 1.

$\tilde{\mathbf{X}}(\mathbf{u}_{i})[0:kp]\in\mathbb{R}^{kp}$ corresponds to
the previous color representation $\mathbf{F}^{(t-1)}(\mathbf{u}_{i})$ of
tuple $\mathbf{u}_{i}$.

  2. 2.

$\tilde{\mathbf{F}}^{\alpha}(\mathbf{u}_{i})[(j-1)kp:jkp]\in\mathbb{R}^{kp}$
corresponds to the degree-normalized sum over adjacent $j$-neighbors
$\frac{\alpha_{j}}{d_{j}}\sum_{w\in\Delta_{j}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{j}(\mathbf{u}_{i},w))$.

  3. 3.

$\tilde{\mathbf{F}}^{\beta}(\mathbf{u}_{i})[(j-1)kp:jkp]\in\mathbb{R}^{kp}$
corresponds to the degree-normalized sum over non-adjacent $j$-neighbors
$\frac{\beta_{j}}{n-d_{j}}\sum_{w\in\Delta_{j}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{j}(\mathbf{u}_{i},w))$.

  4. 4.

$\text{deg}^{\prime}(\mathbf{u}_{i})[2(j-1)]=d_{ij}$, where $d_{ij}$ is the
degree of node $u_{j}$ in the $k$-tuple $\mathbf{u}_{i}=(u_{1},\dots,u_{k})$.

  5. 5.

$\text{deg}^{\prime}(\mathbf{u}_{i})[2(j-1)+1]=n-d_{ij}$, where $d_{ij}$ is
the degree of node $u_{j}$ in the $k$-tuple
$\mathbf{u}_{i}=(u_{1},\dots,u_{k})$.

To this end, we show that there exists a sequence of functions
$f_{\text{FFN}}\circ f_{\text{add}}\circ f_{\text{deg}}$ such that

$\displaystyle\mathbf{X}^{(t,k)}$ $\displaystyle=f_{\text{FFN}}\circ
f_{\text{add}}\circ
f_{\text{deg}}\Big{(}\tilde{\mathbf{X}}(\mathbf{u}_{i})\Big{)}$
$\displaystyle=\begin{bmatrix}\mathbf{F}^{(t)}(\mathbf{u}_{i})&\mathbf{0}&\text{deg}^{\prime}(\mathbf{u}_{i})&\mathbf{P}^{\prime}(\mathbf{u}_{i})&\text{atp}^{\prime}(\mathbf{u}_{i})\end{bmatrix},$

where the functions are applied independently to each row.

Since our domain is compact, there exist choices of
$f_{\text{FFN}},f_{\text{add}},f_{\text{deg}}$ such that $f_{\text{FFN}}\circ
f_{\text{add}}\circ f_{\text{deg}}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$,
in which case $f_{\text{FFN}}\circ f_{\text{add}}\circ f_{\text{deg}}$ is
continuous. As a result, $\mathsf{FFN}$ can approximate $f_{\text{FFN}}\circ
f_{\text{add}}\circ f_{\text{deg}}$ arbitrarily close.

Concretely, we define

$f_{\text{deg}}\Big{(}\tilde{\mathbf{X}}(\mathbf{u}_{i})\Big{)}=\begin{bmatrix}\mathbf{F}^{(t-1)}(\mathbf{u}_{i})\\\
d_{i1}\cdot\frac{\alpha_{1}}{d_{i1}}\sum_{w\in\Delta_{1}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{1}(\mathbf{u}_{i},w))\\\
\vdots\\\
d_{ik}\cdot\frac{\alpha_{k}}{d_{ik}}\sum_{w\in\Delta_{k}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{k}(\mathbf{u}_{i},w))\\\
(n-d_{i1})\cdot\frac{\beta_{1}}{n-d_{i1}}\sum_{w\in
V(G)\setminus\Delta_{1}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{1}(\mathbf{u}_{i},w))\\\
\vdots\\\ (n-d_{ik})\cdot\frac{\beta_{k}}{n-d_{ik}}\sum_{w\in
V(G)\setminus\Delta_{k}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{k}(\mathbf{u}_{i},w))\\\
\text{deg}^{\prime}(\mathbf{u}_{i})\\\ \mathbf{P}^{\prime}(\mathbf{u}_{i})\\\
\text{atp}^{\prime}(\mathbf{u}_{i})\end{bmatrix}^{T},$

where for each $j\in[k]$, $f_{\text{deg}}$ multiplies

  1. 1.

$\tilde{\mathbf{F}}^{\alpha}(\mathbf{u}_{i})[(j-1)kp:jkp]$ with
$\text{deg}^{\prime}(\mathbf{u}_{i})[2(j-1)]$.

  2. 2.

$\tilde{\mathbf{F}}^{\beta}(\mathbf{u}_{i})[(j-1)kp:jkp]$ with
$\text{deg}^{\prime}(\mathbf{u}_{i})[2(j-1)+1]$.

We then define

$\mathbf{F}^{\alpha}(\mathbf{u}_{i})\coloneqq\begin{bmatrix}\alpha_{1}\cdot\sum_{w\in\Delta_{1}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{1}(\mathbf{u}_{i},w))\\\
\vdots\\\
\alpha_{k}\cdot\sum_{w\in\Delta_{k}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{k}(\mathbf{u}_{i},w))\end{bmatrix}^{T}$

and

$\mathbf{F}^{\beta}(\mathbf{u}_{i})\coloneqq\begin{bmatrix}\beta_{1}\cdot\sum_{w\in
V(G)\setminus\Delta_{1}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{1}(\mathbf{u}_{i},w))\\\
\vdots\\\ \beta_{k}\cdot\sum_{w\in
V(G)\setminus\Delta_{k}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{k}(\mathbf{u}_{i},w))\end{bmatrix}^{T}$

and consequently, we can write

$f_{\text{deg}}\Big{(}\tilde{\mathbf{X}}(\mathbf{u}_{i})\Big{)}=\begin{bmatrix}\mathbf{F}^{(t-1)}(\mathbf{u}_{i})\\\
\mathbf{F}^{\alpha}(\mathbf{u}_{i})\\\ \mathbf{F}^{\beta}(\mathbf{u}_{i})\\\
\text{deg}^{\prime}(\mathbf{u}_{i})\\\ \mathbf{P}^{\prime}(\mathbf{u}_{i})\\\
\text{atp}^{\prime}(\mathbf{u}_{i})\end{bmatrix}^{T}.$

Next, we define

$\displaystyle
f_{\text{add}}\Big{(}f_{\text{deg}}\Big{(}\tilde{\mathbf{X}}(\mathbf{u}_{i})\Big{)}\Big{)}$
$\displaystyle=\begin{bmatrix}\mathbf{F}^{(t-1)}(\mathbf{u}_{i})+\sum_{j\in[k]}(\mathbf{F}^{\alpha}(\mathbf{u}_{i})[(j-1)kp:jkp]+\mathbf{F}^{\beta}(\mathbf{u}_{i})[(j-1)kp:jkp])\\\
\mathbf{0}\\\ \text{deg}^{\prime}(\mathbf{u}_{i})\\\
\mathbf{P}^{\prime}(\mathbf{u}_{i})\\\
\text{atp}^{\prime}(\mathbf{u}_{i})\end{bmatrix}^{T},$

where $f_{\text{add}}$ sums up $\mathbf{F}^{(t-1)}(\mathbf{u}_{i})$ with
$\mathbf{F}^{\alpha}(\mathbf{u}_{i})[(j-1)kp:jkp]$ and
$\mathbf{F}^{\beta}(\mathbf{u}_{i})[(j-1)kp:jkp]$ for each $j$. Afterwards,
$f_{\text{add}}$ sets

$f_{\text{deg}}\Big{(}\tilde{\mathbf{X}}(\mathbf{u}_{i})\Big{)}[kp:2k^{2}p+kp]=\mathbf{0}\in\mathbb{R}^{2k^{2}p}.$

Now, finally, note from the definition of
$\mathbf{F}^{\alpha}(\mathbf{u}_{i})$ and $\mathbf{F}^{\beta}(\mathbf{u}_{i})$
that

$\sum_{j\in[k]}(\mathbf{F}^{\alpha}(\mathbf{u}_{i})[(j-1)kp:jkp]+\mathbf{F}^{\beta}(\mathbf{u}_{i})[(j-1)kp:jkp])=H(\mathbf{X}^{(t-1,k)}(\mathbf{u}_{i})),$

where we recall that we defined

$H(\mathbf{X}^{(t-1,k)}(\mathbf{u}_{i}))=\frac{1}{n}\cdot\sum_{j\in[k]}\Big{(}\alpha_{j}\cdot\sum_{w\in\Delta_{j}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{j}(\mathbf{u}_{i},w))+\beta_{j}\cdot\sum_{w\in
V(G)\setminus\Delta_{j}(\mathbf{u}_{i})}\mathbf{F}^{(t-1)}(\phi_{j}(\mathbf{u}_{i},w))\Big{)}.$

Hence, we have that

$f_{\text{add}}\Big{(}f_{\text{deg}}\Big{(}\tilde{\mathbf{X}}(\mathbf{u}_{i})\Big{)}=\begin{bmatrix}\mathbf{F}^{(t-1)}(\mathbf{u}_{i})+H(\mathbf{X}^{(t-1,k)}(\mathbf{u}_{i}))\\\
\mathbf{0}\\\ \text{deg}^{\prime}(\mathbf{u}_{i})\\\
\mathbf{P}^{\prime}(\mathbf{u}_{i})\\\
\text{atp}^{\prime}(\mathbf{u}_{i})\end{bmatrix}^{T}.$

Finally, we define

$\displaystyle
f_{\text{FFN}}\Big{(}f_{\text{add}}\Big{(}f_{\text{deg}}\Big{(}\tilde{\mathbf{X}}(\mathbf{u}_{i})\Big{)}\Big{)}$
$\displaystyle=\begin{bmatrix}\mathsf{FFN}\Big{(}\mathbf{F}^{(t-1)}(\mathbf{u}_{i})+H(\mathbf{X}^{(t-1,k)}(\mathbf{u}_{i}))\Big{)}\\\
\mathbf{0}\\\ \text{deg}^{\prime}(\mathbf{u}_{i})\\\
\mathbf{P}^{\prime}(\mathbf{u}_{i})\\\
\text{atp}^{\prime}(\mathbf{u}_{i})\end{bmatrix}^{T}$
$\displaystyle=\begin{bmatrix}\mathbf{F}^{(t)}(v)&\mathbf{0}&\text{deg}^{\prime}(v)&\mathbf{P}^{\prime}(v)\end{bmatrix},$

where $\mathsf{FFN}$ denotes the FFN in Equation 30, from which the last
equality follows. Thank you for sticking around until the end. This completes
the proof. ∎

The above proof shows that the $k$-GT can simulate the $\delta$-$k$-WL. Since
the $\delta$-$k$-WL is strictly more expressive than the $k$-WL (Morris et
al., 2020), Theorem 5 follows directly from Theorem 4.

Further, the above proof shows that the $k$-GT can simulate the
$\delta$-$k$-LWL. If we simulate the $\delta$-$k$-LWL with the $k$-GT while
only using token embeddings for tuples in $V(G)^{k}_{s}$, Theorem 6 directly
follows.