# On the Stability of Expressive Positional Encodings for Graph Neural
Networks

Yinan Huang
Georgia Institute of Technology
<EMAIL_ADDRESS>
&William Lu∗
Purdue University
<EMAIL_ADDRESS>&Joshua Robinson
Stanford University
<EMAIL_ADDRESS>
&Yu Yang
Tongji University
<EMAIL_ADDRESS>
&Muhan Zhang
Peking University
<EMAIL_ADDRESS>
&Stefanie Jegelka
MIT CSAIL
<EMAIL_ADDRESS>
&Pan Li
Georgia Institute of Technology
<EMAIL_ADDRESS>
Equal contribution.

###### Abstract

Designing effective positional encodings for graphs is key to building
powerful graph transformers and enhancing message-passing graph neural
networks. Although widespread, using Laplacian eigenvectors as positional
encodings faces two fundamental challenges: (1) _Non-uniqueness_ : there are
many different eigendecompositions of the same Laplacian, and (2)
_Instability_ : small perturbations to the Laplacian could result in
completely different eigenspaces, leading to unpredictable changes in
positional encoding. Despite many attempts to address non-uniqueness, most
methods overlook stability, leading to poor generalization on unseen graph
structures. We identify the cause of instability to be a “hard partition” of
eigenspaces. Hence, we introduce Stable and Expressive Positional Encodings
(SPE), an architecture for processing eigenvectors that uses eigenvalues to
“softly partition” eigenspaces. SPE is the first architecture that is (1)
provably stable, and (2) universally expressive for basis invariant functions
whilst respecting all symmetries of eigenvectors. Besides guaranteed
stability, we prove that SPE is at least as expressive as existing methods,
and highly capable of counting graph structures. Finally, we evaluate the
effectiveness of our method on molecular property prediction, and out-of-
distribution generalization tasks, finding improved generalization compared to
existing positional encoding methods. Our code is available at
https://github.com/Graph-COM/SPE.

##  1 Introduction

Graph Neural Networks (GNNs) have been arguably one of the most popular
machine learning models on graphs, and have achieved remarkable results for
numerous applications in drug discovery, computational chemistry, and social
network analysis, etc. (Kipf & Welling, 2017; Bronstein et al., 2017; Duvenaud
et al., 2015; Stokes et al., 2020; Zhang & Chen, 2018). However, there is a
common concern about GNNs: the limited _expressive power_. It is known that
message-passing GNNs are at most expressive as the Weisfeiler-Leman test (Xu
et al., 2019; Morris et al., 2019) in distinguishing non-isomorphic graphs,
and in general cannot even approximate common functions such as the number of
certain subgraph patterns (Chen et al., 2020; Arvind et al., 2020; Tahmasebi
et al., 2020; Huang et al., 2023). These limitations could significantly
restrict model performance, e.g., since graph substructures can be closely
related to the target function in chemistry, biology and social network
analysis (Girvan & Newman, 2002; Granovetter, 1983; Koyutürk et al., 2004;
Jiang et al., 2010; Bouritsas et al., 2022).

To alleviate expressivity limitations, there has been considerable interest in
designing effective positional encodings for graphs (You et al., 2019; Dwivedi
& Bresson, 2021; Wang et al., 2022a). Generalized from the positional
encodings of 1-D sequences for Transformers (Vaswani et al., 2017), the idea
is to endow nodes with information about their relative position within the
graph and thus make them more distinguishable. Many promising graph positional
encodings use the eigenvalue decomposition of the graph Laplacian (Dwivedi et
al., 2023; Kreuzer et al., 2021). The eigenvalue decomposition is a strong
candidate because the Laplacian fully describes the adjacency structure of a
graph, and there is a deep understanding of how these eigenvectors and
eigenvalues inherit this information (Chung, 1997). However, eigenvectors have
special structures that must be taken into consideration when designing
architectures that process eigenvectors.

Firstly, eigenvectors are _not_ unique: if ${\bm{v}}$ is an eigenvector, then
so is $-{\bm{v}}$. Furthermore, when there are multiplicities of eigenvalues
then there are many more symmetries, since any orthogonal change of basis of
the corresponding eigenvectors yields the same Laplacian. Because of this
basis ambiguity, neural networks that process eigenvectors should be _basis
invariant_ : applying basis transformations to input eigenvectors should not
change the output of the neural network. This avoids the pathological scenario
where different eigendecompositions of the same Laplacian produce different
model predictions. Several prior works have explored sign and basis symmetries
of eigenvectors. For example, Dwivedi & Bresson (2021); Kreuzer et al. (2021)
randomly flip the sign of eigenvectors during training so that the resulting
model is robust to sign transformation. Lim et al. (2023) instead design new
neural architectures that are invariant to sign flipping (SignNet) or basis
transformation (BasisNet). Although these basis invariant methods have the
right symmetries, they do not yet account for the fact that two Laplacians
that are similar but distinct may produce completely different eigenspaces.

This brings us to another important consideration, that of _stability_. Small
perturbations to the input Laplacian should only induce a limited change of
final positional encodings. This “small change of Laplacians, small change of
positional encodings” actually generalizes the previous concept of basis
invariance and proposes a stronger requirement on the networks. But this
stability (or continuity) requirement is a great challenge for graphs, because
small perturbations can produce completely different eigenvectors if some
eigenvalues are close (Wang et al. (2022a), Lemma 3.4). Since the neural
networks process eigenvectors, not the Laplacian matrix itself, they run the
risk of being highly discontinuous with respect to the input matrix, leading
to an inability to generalize to new graph structures and a lack of robustness
to any noise in the input graph’s adjacency. In contrast, stable models enjoy
many benefits such as adversarial robustness (Cisse et al., 2017; Tsuzuku et
al., 2018) and provable generalization (Sokolić et al., 2017).

Unfortunately, existing positional encoding methods are not stable. Methods
that only focus on sign invariance (Dwivedi & Bresson, 2021; Kreuzer et al.,
2021; Lim et al., 2023), for instance, are not guaranteed to satisfy “same
Laplacian, same positional encodings” if multiplicity of eigenvalues exists.
Basis invariant methods such as BasisNet are unstable if they apply different
neural networks to different eigensubspaces, i.e., if they perform a _hard
partitioning_ of eigenspaces and treat each chunk separately. The
discontinuous nature of partitioning makes them highly sensitive to
perturbations of the Laplacian. The hard partition also requires fixed
eigendecomposition thus unsuitable for graph-level tasks. On the other hand,
Wang et al. (2022a) proposes a provably stable positional encoding. But, to
achieve stability, it completely ignores the distinctness of each
eigensubspaces and processes the merged eigenspaces homogeneously.
Consequently, it loses expressive power and has, e.g., a subpar performance on
molecular graph regression tasks (Rampášek et al., 2022).

Main contributions. In this work, we present Stable and Expressive Positional
Encodings (SPE). The key insight is to perform a soft and learnable
“partition” of eigensubspaces in a eigenvalue dependent way, hereby achieving
both stability (from the soft partition) and expressivity (from dependency on
both eigenvalues and eigenvectors). Specifically:

  * •

SPE is provably stable. We show that the network sensitivity w.r.t. the input
Laplacian is determined by the gap between the $d$-th and $(d+1)$-th smallest
eigenvalues if using the first $d$ eigenvectors and eigenvalues. This implies
our method is stable regardless of how the used $d$ eigenvectors and
eigenvalues change.

  * •

SPE can universally approximate basis invariant functions and is as least
expressive as existing methods in distinguishing graphs. We also prove its
capability in counting graph substructures.

  * •

We empirically illustrate that introducing more stability helps generalize
better but weakens the expressive power. Besides, on the molecule graph
prediction datasets ZINC and Alchemy, our method significantly outperforms
other positional encoding methods. On DrugOOD (Ji et al., 2023), a ligand-
based affinity prediction task with domain shifts, our method demonstrates a
clear and constant improvement over other unstable positional encodings. All
these validate the effectiveness of our stable and expressive method.

##  2 Preliminaries

Notation. We always use $n$ for the number of nodes in a graph, $d\leq n$ for
the number of eigenvectors and eigenvalues chosen, and $p$ for the dimension
of the final

positional encoding for each node. We use $\left\lVert\cdot\right\rVert$ to
denote the $L2$ norm of vectors and matrices, and
$\left\lVert\cdot\right\rVert_{\mathsf{F}}$ for the Frobenius norm of
matrices.

Graphs and Laplacian Encodings. Denote an undirected graph with $n$ nodes by
$\mathcal{G}=({\bm{A}},{\bm{X}})$, where ${\bm{A}}\in\mathbb{R}^{n\times n}$
is the adjacency matrix and ${\bm{X}}\in\mathbb{R}^{n\times p}$ is the node
feature matrix. Let ${\bm{D}}=\text{diag}([\sum_{j=1}^{n}A_{i,j}]_{i=1}^{n})$
be the diagonal degree matrix. The normalized Laplacian matrix of
$\mathcal{G}$ is a positive semi-definite matrix defined by
${\bm{L}}={\bm{I}}-{\bm{D}}^{-1/2}{\bm{A}}{\bm{D}}^{-1/2}$. Its eigenvalue
decomposition ${\bm{L}}={\bm{V}}\text{diag}(\bm{\lambda}){\bm{V}}^{\top}$
returns eigenvectors ${\bm{V}}$ and eigenvalues $\bm{\lambda}$, which we
denote by $\text{EVD}({\bm{L}})=({\bm{V}},\bm{\lambda})$. In practice we may
only use the smallest $d\leq n$ eigenvalues and eigenvectors, so abusing
notation slightly, we also denote the smallest $d$ eigenvalues by
$\bm{\lambda}\in\mathbb{R}^{d}$ and the corresponding $d$ eigenvectors by
${\bm{V}}\in\mathbb{R}^{n\times d}$. A Laplacian positional encoding is a
function that produces node embeddings ${\bm{Z}}\in\mathbb{R}^{n\times p}$
given $({\bm{V}},\bm{\lambda})\in\mathbb{R}^{n\times d}\times\mathbb{R}^{d}$
as input.

Basis invariance. Given eigenvalues $\bm{\lambda}\in\mathbb{R}^{d}$, if
eigenvalue $\lambda_{i}$ has multiplicity $d_{i}$, then the corresponding
eigenvectors ${\bm{V}}_{i}\in\mathbb{R}^{n\times d_{i}}$ form a
$d_{i}$-dimensional eigenspace. A vital symmetry of eigenvectors is the
infinitely many choices of basis eigenvectors describing the same underlying
eigenspace. Concretely, if ${\bm{V}}_{i}$ is a basis for the eigenspace of
$\lambda_{i}$, then ${\bm{V}}_{i}{\bm{Q}}_{i}$ is, too, for any orthogonal
matrix ${\bm{Q}}_{i}\in O(d_{i})$. The symmetries of each eigenspace can be
collected together to describe the overall symmetries of ${\bm{V}}$ in terms
of the direct sum group
$O(\bm{\lambda})\vcentcolon=\oplus_{i}O(d_{i})=\\{\oplus_{i}{\bm{Q}}_{i}\in\mathbb{R}^{\sum_{i}d_{i}\times\sum_{i}d_{i}}:{\bm{Q}}_{i}\in
O(d_{i})\\}$, i.e., block diagonal matrices with $i$th block belonging to
$O(d_{i})$. Namely, for any ${\bm{Q}}\in O(\bm{\lambda})$, both
$({\bm{V}},\bm{\lambda})$ and $({\bm{V}}{\bm{Q}},\bm{\lambda})$ are
eigendecompositions of the same underlying matrix. When designing a model $f$
that takes eigenvectors as input, we want $f$ to be _basis invariant_ :
$f({\bm{V}}{\bm{Q}},\bm{\lambda})=f({\bm{V}},\bm{\lambda})$ for any
$({\bm{V}},\bm{\lambda})\in\mathbb{R}^{n\times d}\times\mathbb{R}^{d}$, and
any ${\bm{Q}}\in O(\bm{\lambda})$.

Permutation equivariance. Let $\Pi(n)=\\{{\bm{P}}\in\\{0,1\\}^{n\times
n}:{\bm{P}}{\bm{P}}^{\top}={\bm{I}}\\}$ be the permutation matrices of $n$
elements. A function $f:\mathbb{R}^{n}\to\mathbb{R}^{n}$ is called permutation
equivariant, if for any $\bm{x}\in\mathbb{R}^{n}$ and any permutation
${\bm{P}}\in\Pi(n)$, it satisfies $f({\bm{P}}\bm{x})={\bm{P}}f(\bm{x})$.
Similarly, $f:\mathbb{R}^{n\times n}\to\mathbb{R}^{n}$ is said to be
permutation equivariant if satisfying
$f({\bm{P}}{\bm{X}}{\bm{P}}^{\top})={\bm{P}}f({\bm{X}})$.

##  3 A Provably Stable and Expressive PE

In this section we introduce our model _Stable and Expressive Positional
Encodings_ (SPE). SPE is both stable and a maximally expressive basis
invariant architecture for processing eigenvector data, such as Laplacian
eigenvectors. We begin with formally defining the stability of a positional
encoding. Then we describe our SPE model, and analyze its stability. In the
final two subsections we show that higher stability leads to improved out-of-
distribution generalization, and show that SPE is a universally expressive
basis invariant architecture.

###  3.1 Stable Positional Encodings

Stability intuitively means that a small input perturbation yields a small
change in the output. For eigenvector-based positional encodings, the
perturbation is to the Laplacian matrix, and should result in a small change
of node-level positional embeddings.

######  Definition 3.1 (PE Stability).

A PE method $\mathrm{PE}:\mathbb{R}^{n\times
d}\times\mathbb{R}^{d}\to\mathbb{R}^{n\times p}$ is called stable, if there
exist constants $c,C>0$, such that for any Laplacian
${\bm{L}},{\bm{L}}^{\prime}$,

$\left\lVert\mathrm{PE}(\mathrm{EVD}({\bm{L}}))-{\bm{P}}_{*}\mathrm{PE}(\mathrm{EVD}({\bm{L}}^{\prime}))\right\rVert_{\mathsf{F}}\leq
C\cdot\left\lVert{\bm{L}}-{\bm{P}}_{*}{\bm{L}}^{\prime}{\bm{P}}_{*}^{\top}\right\rVert_{\mathsf{F}}^{c},$
(1)

where
${\bm{P}}_{*}=\arg\min_{{\bm{P}}\in\Pi(n)}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}$
is the permutation matrix matching two Laplacians.

It is worth noting that here we adopt a slightly generalized definition of
typical stability via Lipschitz continuity ($c=1$). This definition via
H$\ddot{\text{o}}$lder continuity describes a more comprehensive stability
behavior of PE methods, while retaining the essential idea of stability.

######  Remark 3.1 (Stability implies permutation equivariance).

Note that a PE method is permutation equivariant if it is stable: simply let
${\bm{L}}={\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}$ for some
${\bm{P}}\in\Pi(n)$ and we obtain the desired permutation equivariance
$\mathrm{PE}(\mathrm{EVD}({\bm{P}}{\bm{L}}{\bm{P}}^{\top}))={\bm{P}}\cdot\mathrm{PE}(\mathrm{EVD}({\bm{L}}))$.

Stability is hard to achieve due to the instability of eigenvalue
decomposition—a small perturbation of the Laplacian can produce completely
different eigenvectors (Wang et al. (2022a), Lemma 3.4). Since positional
encoding models process the eigenvectors (and eigenvalues), they naturally
inherit this instability with respect to the input matrix. Indeed, as
mentioned above, many existing positional encodings are not stable. The main
issue is that they partition the eigenvectors by eigenvalue, which leads to
instabilities.

###  3.2 SPE: A positional encoding with guaranteed stability

Figure 1: Illustration of the SPE architecture (first two rows) and its
stability property (last row). The input graph is first decomposed into
eigenvectors ${\bm{V}}$ and eigenvalues $\bm{\lambda}$. In step 1, a
permutation equivariant $\phi_{\ell}$ act on $\bm{\lambda}$ to produce another
vector $\phi_{\ell}(\bm{\lambda})$. In step 2, we compute
${\bm{V}}\text{diag}\\{\phi_{\ell}(\bm{\lambda})\\}{\bm{V}}^{\top}$ for each
$\phi_{\ell}$ and concatenate the results into a tensor. This tensor is input
into a permutation equivariant network $\rho$ to produce final node positional
encodings.

To achieve stability, the key insight is to avoid a hard partition of
eigensubspaces. Simultaneously, we should fully utilize the information in the
eigenvalues for strong expressive power. Therefore, we propose to do a “soft
partitioning” of eigenspaces by leveraging eigenvalues. Instead of treating
each eigensubspace independently, we apply a weighted sum of eigenvectors in
an eigenvalue dependent way. If done carefully, this can ensure that as two
distinct eigenvalues converge—these are exactly the degenerate points creating
instability—the way their respective eigenvectors are processed becomes more
similar. This means that if two eigenvectors are “swapped”, as happens at
degenerate points, the model output does not change much. The resulting method
is (illustrated in Figure 1):

$\textbf{SPE}:\hskip
5.0pt\mathrm{SPE}({\bm{V}},\bm{\lambda})=\rho\big{(}{\bm{V}}\mathrm{diag}(\,\phi_{1}(\bm{\lambda})){\bm{V}}^{\top},{\bm{V}}\mathrm{diag}(\phi_{2}(\bm{\lambda})){\bm{V}}^{\top},...,{\bm{V}}\mathrm{diag}(\phi_{m}(\bm{\lambda})){\bm{V}}^{\top}\;\big{)},$
(2)

where the input is the $d$ smallest eigenvalues
$\bm{\lambda}\in\mathbb{R}^{d}$ and corresponding eigenvectors
${\bm{V}}\in\mathbb{R}^{n\times d}$, $m$ is a hyper-parameter, and
$\phi_{\ell}:\mathbb{R}^{d}\to\mathbb{R}^{d}$ and $\rho:\mathbb{R}^{n\times
n\times m}\to\mathbb{R}^{n\times p}$ are always permutation equivariant neural
networks. Here, permutation equivariance means
$\phi_{\ell}({\bm{P}}\bm{\lambda})={\bm{P}}\phi_{\ell}(\bm{\lambda})$ for
${\bm{P}}\in\Pi(d)$ and
$\rho({\bm{P}}{\bm{A}}{\bm{P}}^{\top})={\bm{P}}\rho({\bm{A}})$ for any
${\bm{P}}\in\Pi(n)$ and input ${\bm{A}}$. There are many choices of
permutation equivariant networks that can be used, such as element-wise MLPs
or Deep Sets (Zaheer et al., 2017) for $\phi_{\ell}$, and graph neural
networks for $\rho$. The permutation equivariance of $\phi_{\ell}$ and $\rho$
ensures that SPE is _basis invariant_.

Note that in Eq. (2), the term
${\bm{V}}\text{diag}(\phi_{\ell}(\bm{\lambda})){\bm{V}}^{\top}$ looks like a
spectral graph convolution operator. But they are methodologically different:
SPE uses ${\bm{V}}\text{diag}(\phi_{\ell}(\bm{\lambda})){\bm{V}}^{\top}$ to
construct positional encodings, which are not used as a convolution operation
to process node attributes (say as
${\bm{V}}\text{diag}(\phi_{\ell}(\bm{\lambda})){\bm{V}}^{\top}{\bm{X}}$).
Also, $\phi_{\ell}$’s are general permutation equivariant functions that may
express the interactions between different eigenvalues instead of elementwise
polynomials on each eigenvalue separately which are commonly adopted in
spectral graph convolution.

It is also worthy noticing that term
${\bm{V}}\text{diag}(\phi_{\ell}(\bm{\lambda})){\bm{V}}^{\top}$ will reduce to
hard partitions of eigenvectors in the $\ell$-th eigensubspace if we let
$[\phi_{\ell}(\bm{\lambda})]_{j}=\mathbbm{1}(\lambda_{j}\text{ is the $l$-th
smallest eigenvalue})$. To obtain stability, what we need is to constrain
$\phi_{\ell}$ to continuous functions to perform a continuous “soft
partition”.

######  Assumption 3.1.

The key assumptions for SPE are as follows:

  * •

$\phi_{\ell}$ is $K_{\ell}$-Lipshitz continuous: for any
$\bm{\lambda},\bm{\lambda}^{\prime}\in\mathbb{R}^{d}$,
$\left\lVert\phi_{\ell}(\bm{\lambda})-\phi_{\ell}(\bm{\lambda}^{\prime})\right\rVert_{\mathsf{F}}\leq
K_{\ell}\left\lVert\bm{\lambda}-\bm{\lambda}^{\prime}\right\rVert.$

  * •

$\rho$ is $J$-Lipschitz continuous: for any
$[{\bm{A}}_{1},{\bm{A}}_{2},...,{\bm{A}}_{m}]\in\mathbb{R}^{n\times n\times
m}$ and
$[{\bm{A}}_{1}^{\prime},{\bm{A}}_{2}^{\prime},...,{\bm{A}}_{m}^{\prime}]\in\mathbb{R}^{n\times
n\times m}$,
$\left\lVert\rho({\bm{A}}_{1},{\bm{A}}_{2},...,{\bm{A}}_{m})-\rho({\bm{A}}_{1}^{\prime},{\bm{A}}_{2}^{\prime},...,{\bm{A}}_{m}^{\prime})\right\rVert_{\mathsf{F}}\leq
J\sum_{l=1}^{m}\left\lVert{\bm{A}}_{\ell}-{\bm{A}}_{\ell}^{\prime}\right\rVert_{\mathsf{F}}.$

These two continuity assumptions generally hold by assuming the underlying
networks have norm-bounded weights and continuous activation functions, such
as ReLU. As a result, Assumption 3.1 is mild for most neural networks.

Now we are ready to present our main theorem, which states that continuity of
$\phi_{\ell}$ and $\rho$ leads to the desired stability.

######  Theorem 3.1 (Stability of SPE).

Under Assumption 3.1, SPE is stable with respect to the input Laplacian: for
Laplacians ${\bm{L}},{\bm{L}}^{\prime}$,

$\begin{split}\left\lVert\mathrm{SPE}(\mathrm{EVD}({\bm{L}}))-{\bm{P}}_{*}\mathrm{SPE}(\mathrm{EVD}({\bm{L}}^{\prime}))\right\rVert_{\mathsf{F}}\leq&(\alpha_{1}+\alpha_{2})d^{5/4}\sqrt{\left\lVert{\bm{L}}-{\bm{P}}_{*}{\bm{L}}{\bm{P}}_{*}^{\top}\right\rVert_{\mathsf{F}}}\\\
&+\left(\alpha_{2}\tfrac{d}{\gamma}+\alpha_{3}\right)\left\lVert{\bm{L}}-{\bm{P}}_{*}{\bm{L}}{\bm{P}}_{*}^{\top}\right\rVert_{\mathsf{F}},\end{split}$
(3)

where the constants are $\alpha_{1}=2J\sum_{l=1}^{m}K_{\ell}$,
$\alpha_{2}=4\sqrt{2}J\sum_{l=1}^{m}M_{\ell}$ and
$\alpha_{3}=J\sum_{l=1}^{m}K_{\ell}$. Here
$M_{\ell}=\sup_{\bm{\lambda}\in[0,2]^{d}}\left\lVert\phi_{\ell}(\bm{\lambda})\right\rVert$
and again
${\bm{P}}_{*}=\arg\min_{{\bm{P}}\in\Pi(n)}\left\lVert{\bm{L}}-{\bm{P}}_{*}{\bm{L}}{\bm{P}}_{*}^{\top}\right\rVert_{\mathsf{F}}$.
The eigengap $\gamma=\lambda_{d+1}-\lambda_{d}$ is the difference between the
$(d+1)$-th and $d$-th smallest eigenvalues, and $\gamma=+\infty$ if $d=n$.

Note that the stability of SPE is determined by both the Lipschitz constants
$J,K_{\ell}$ and the eigengap $\gamma=\lambda_{d}-\lambda_{d+1}$. The
dependence on $\gamma$ comes from the fact that we only choose to use $d$
eigenvectors/eigenvalues. It is inevitable as long as $d<n$, and it disappears
($\gamma=+\infty$) if we let $d=n$. This phenomenon is also observed in PEG
(Wang et al. (2022a), Theorem 3.6).

###  3.3 From stability to out-of-distribution generalization

An important implication of stability is that one can characterize the domain
generalization gap by the model’s Lipschitz constant (Courty et al., 2017;
Shen et al., 2018). Although our method satisfies H$\ddot{\text{o}}$lder
continuity instead of strict Lipschitz continuity, we claim that
interestingly, a similar bound can still be obtained for domain
generalization.

We consider graph regression with domain shift: the training graphs are
sampled from source domain ${\bm{L}}\sim\mathbb{P}_{\mathcal{S}}$, while the
test graphs are sampled from target domain
${\bm{L}}\sim\mathbb{P}_{\mathcal{T}}$. With ground-truth function
$f({\bm{L}})\in\mathbb{R}$ and a prediction model $h({\bm{L}})\in\mathbb{R}$,
we are interested in the gap between in-distribution error
$\varepsilon_{s}(h)=\mathbbm{E}_{{\bm{L}}\sim\mathbb{P}_{\mathcal{S}}}|h({\bm{L}})-f({\bm{L}})|$
and out-of-distribution error
$\varepsilon_{t}(h)=\mathbbm{E}_{{\bm{L}}\sim\mathbb{P}_{\mathcal{T}}}|h({\bm{L}})-f({\bm{L}})|$.
The following theorem states that for a base GNN equipped with SPE, we can
upper bound the generalization gap in terms of the H$\ddot{\text{o}}$lder
constant of SPE, the Lipschitz constant of the base GNN and the 1-Wasserstein
distance between source and target distributions.

######  Proposition 3.1.

Assume Assumption 3.1 hold, and assume a base GNN model
$\mathrm{GNN}({\bm{L}},{\bm{X}})\in\mathbb{R}$ that is $C$-Lipschitz
continuous, i.e.,

$|\mathrm{GNN}({\bm{L}},{\bm{X}})-\mathrm{GNN}({\bm{L}}^{\prime},{\bm{X}}^{\prime})|\leq
C\min_{{\bm{P}}\in\Pi(n)}\left(\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}+\left\lVert{\bm{X}}-{\bm{P}}{\bm{X}}^{\prime}\right\rVert_{\mathsf{F}}\right),$
(4)

for any Laplacians ${\bm{L}},{\bm{L}}^{\prime}$ and node features
${\bm{X}},{\bm{X}}^{\prime}$. Now let GNN take positional encodings as node
features ${\bm{X}}=\mathrm{SPE}(\mathrm{EVD}({\bm{L}}))$ and let the resulting
prediction model be
$h({\bm{L}})=\mathrm{GNN}({\bm{L}},\mathrm{SPE}(\mathrm{EVD}({\bm{L}})))$.
Then the domain generalization gap $\varepsilon_{t}(h)-\varepsilon_{t}(s)$
satisfies

$\varepsilon_{t}(h)-\varepsilon_{s}(h)\leq
2C(1+\alpha_{2}\tfrac{d}{\gamma}+\alpha_{3})W(\mathbb{P}_{\mathcal{S}},\mathbb{P}_{\mathcal{T}})+2Cd^{5/4}(\alpha_{1}+\alpha_{2})\sqrt{W(\mathbb{P}_{\mathcal{S}},\mathbb{P}_{\mathcal{T}})},$
(5)

where $W(\mathbb{P}_{\mathcal{S}},\mathbb{P}_{\mathcal{T}})$ is the
1-Wasserstein distance111For graphs,
$W(p_{s},p_{t}):=\inf_{\pi\in\Pi(\mathbb{P}_{\mathcal{S}},\mathbb{P}_{\mathcal{T}})}\int\min_{{\bm{P}}\in\Pi(n)}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}\pi({\bm{L}},{\bm{L}}^{\prime})d{\bm{L}}d{\bm{L}}^{\prime}$.
Here $\Pi(\mathbb{P}_{\mathcal{S}},\mathbb{P}_{\mathcal{T}})$ is the set of
product distributions whose marginal distribution is
$\mathbb{P}_{\mathcal{S}}$ and $\mathbb{P}_{\mathcal{T}}$ respectively..

###  3.4 SPE is a Universal Basis Invariant Architecture

SPE is a basis invariant architecture, but is it universally powerful? The
next result shows that SPE is universal, meaning that _any_ continuous basis
invariant function can be expressed in the form of SPE (Eq. 2). To state the
result, recall that
$\mathrm{SPE}({\bm{V}},\bm{\lambda})=\rho({\bm{V}}\mathrm{diag}(\phi(\bm{\lambda})){\bm{V}}^{\top})$,
where for brevity, we express the multiple $\phi_{\ell}$ channels by
$\phi=(\phi_{1},\ldots,\phi_{m})$.

######  Proposition 3.2 (Basis Universality).

SPE can universally approximate any continuous basis invariant function. That
is, for any continuous $f$ for which $f({\bm{V}})=f({\bm{V}}{\bm{Q}})$ for any
eigenvalue $\bm{\lambda}$ and any ${\bm{Q}}\in O(\bm{\lambda})$, there exist
continuous $\rho$ and $\phi$ such that
$f({\bm{V}})=\rho({\bm{V}}\mathrm{diag}(\phi(\bm{\lambda})){\bm{V}}^{\top})$.

Only one prior architecture, BasisNet (Lim et al., 2023), is known to have
this property. However, unlike SPE, BasisNet does not have the critical
stability property. Section 5 shows that this has significant empirical
implications, with SPE considerably outperforming BasisNet across all
evaluations. Furthermore, unlike prior analyses, we show that SPE can provably
make effective use of eigenvalues: it can distinguish two input matrices with
different eigenvalues using 2-layer MLP models for $\rho$ and $\phi$. In
contrast, the original form of BasisNet does not use eigenvalues, though it is
easy to incorporate them.

######  Proposition 3.3.

Suppose that $({\bm{V}},\bm{\lambda})$ and
$({\bm{V}}^{\prime},\bm{\lambda}^{\prime})$ are such that
${\bm{V}}{\bm{Q}}={\bm{V}}^{\prime}$ for some orthogonal matrix ${\bm{Q}}\in
O(d)$ and $\bm{\lambda}\neq\bm{\lambda}^{\prime}$. Then there exist 2-layer
MLPs for each $\phi_{\ell}$ and a 2-layer MLP $\rho$, each with ReLU
activations, such that
$\text{SPE}({\bm{V}},\bm{\lambda})\neq\text{SPE}({\bm{V}}^{\prime},\bm{\lambda}^{\prime})$.

Finally, as a concrete example of the expressivity of SPE for graph
representation learning, we show that SPE is able to count graph substructures
under stability guarantee.

######  Proposition 3.4 (SPE can count cycles).

Assume Assumption 3.1 hold and Let $\rho$ be 2-IGNs (Maron et al., 2019b).
Then SPE can determine the number of 3, 4, 5 cycles of a graph.

##  4 Related Works

Expressive GNNs. Since message-passing graph neural networks have been shown
to be at most as powerful as the Weisfeiler-Leman test (Xu et al., 2019;
Morris et al., 2019), there are many attempts to improve the expressivity of
GNNs. We can classify them into three types: (1) high-order GNNs (Morris et
al., 2020; Maron et al., 2019a; b); (2) subgraph GNNs (You et al., 2021; Zhang
& Li, 2021; Zhao et al., 2022; Bevilacqua et al., 2022); (3) node feature
augmentation (Li et al., 2020; Bouritsas et al., 2022; Barceló et al., 2021).
In some senses, positional encoding can also be seen as an approach of node
feature augmentation, which will be discussed below.

Positional Encoding for GNNs. Positional encodings aim to provide additional
global positional information for nodes in graphs to make them more
distinguishable and add global structural information. It thus serves as a
node feature augmentation to boost the expressive power of general graph
neural networks (message-passing GNNs, spectral GNNs or graph transformers).
Existing positional encoding methods can be categorized into: (1) Laplacian-
eigenvector-based (Dwivedi & Bresson, 2021; Kreuzer et al., 2021; Maskey et
al., 2022; Dwivedi et al., 2022; Wang et al., 2022b; Lim et al., 2023; Kim et
al., 2022); (2) graph-distance-based (Ying et al., 2021; You et al., 2019; Li
et al., 2020); and (3) random node features (Eliasof et al., 2023). A
comprehensive discussion can be found in (Rampášek et al., 2022). Most of
these methods do not consider basis invariance and stability. Notably, Wang et
al. (2022a) also studies the stability of Laplacian encodings. However, their
method ignores eigenvalues and thus implements a stricter symmetry that is
invariant to rotations of the entire eigenspace. As a result, the “over-
stability” restricts its expressive power. Bo et al. (2023) propose similar
operations as ${\bm{V}}\text{diag}(\phi(\bm{\lambda})){\bm{V}}^{\top}$.
However they focus on a specific architecture design ($\phi$ is transformer)
for spectral convolution instead of positional encodings, and do not provide
any stability analysis.

Stability and Generalization of GNNs. The stability of neural networks is
desirable as it implies better generalization (Sokolić et al., 2017; Neyshabur
et al., 2017; 2018; Bartlett et al., 2017) and transferability under domain
shifts (Courty et al., 2017; Shen et al., 2018). In the context of GNNs, many
works theoretically study the stability of various GNN models (Gama et al.,
2020; Kenlay et al., 2020; 2021; Yehudai et al., 2020; Arghal et al., 2022; Xu
et al., 2021; Chuang & Jegelka, 2022). Finally, some works try to characterize
the generalization error of GNNs using VC dimension (Morris et al., 2023) or
Rademacher complexity (Garg et al., 2020).

Table 1: Test MAE results (4 random seeds) on ZINC and Alchemy.

Dataset | PE method | #PEs | #param | Test MAE
---|---|---|---|---
ZINC | No PE | N/A | 575k | $0.1772_{\pm 0.0040}$
PEG | 8 | 512k | $0.1444_{\pm 0.0076}$
PEG | Full | 512k | $0.1878_{\pm 0.0127}$
SignNet | 8 | 631k | $0.1034_{\pm 0.0056}$
SignNet | Full | 662k | $0.0853_{\pm 0.0026}$
BasisNet | 8 | 442k | $0.1554_{\pm 0.0068}$
BasisNet | Full | 513k | $0.1555_{\pm 0.0124}$
SPE | 8 | 635k | $0.0736_{\pm 0.0007}$
SPE | Full | 650k | $\bm{0.0693_{\pm 0.0040}}$
Alchemy | No PE | N/A | 1387k | $0.112_{\pm 0.001}$
PEG | 8 | 1388k | $0.114_{\pm 0.001}$
SignNet | Full | 1668k | $0.113_{\pm 0.002}$
BasisNet | Full | 1469k | $0.110_{\pm 0.001}$
SPE | Full | 1785k | $\mathbf{0.108_{\pm 0.001}}$
|  |  |  |

##  5 Experiments

In this section, we are to use numerical experiments to verify our theory and
the empirical effectiveness of our SPE. Section 5.1 tests SPE’s strength as a
graph positional encoder, and Section 5.2 tests the robustness of SPE to
domain shifts, a key promise of stability. Section 5.3 further explores the
empirical implications of stability in positional encodings. Our key finding
is that there is a _trade-off_ between generalization and expressive power,
with less stable positional encodings fitting the training data better than
their stable counterparts, but leading to worse test performance. Finally,
Section 5.4 tests SPE on challenging graph substructure counting tasks that
message passing graph neural networks cannot solve, finding that SPE
significantly outperforms prior positional encoding methods.

Datasets. We primarily use three datasets: ZINC (Dwivedi et al., 2023),
Alchemy (Chen et al., 2019) and DrugOOD (Ji et al., 2023). ZINC and Alchemy
are graph regression tasks for molecular property prediction. DrugOOD is an
OOD benchmark for AI drug discovery, for which we choose ligand-based affinity
prediction as our classfication task (to determine if a drug is active). It
considers three types of domains where distribution shifts arise: (1) Assay:
which assay the data point belongs to; (2) Scaffold: the core structure of
molecules; and (3) Size: molecule size. For each domain, the full dataset is
divided into five partitions: the training set, the in-distribution (ID)
validation/test sets, the out-of-distribution validation/test sets. These OOD
partitions are expected to be distributed on the domains differently from ID
partitions.

Implementation. We implement SPE by: $\phi_{l}$ either being a DeepSet (Zaheer
et al., 2017), element-wise MLPs or piece-wise cubic splines (see Appendix B.1
for detailed definition); and $\rho$ being GIN (Xu et al., 2019). Note that
the input of $\rho$ is $n\times n\times m$ tensors, hence we first split it
into $n$ many $n\times m$ tensors, and then independently give each $n\times
m$ tensors as node features to an identical GIN. Finally, we sum over the
first $n$ axes to output a permutation equivariant $n\times p$ tensor.

Baselines. We compare SPE to other positional encoding methods including (1)
No positional encodings, (2) SignNet and BasisNet (Lim et al., 2023), and (3)
PEG (Wang et al., 2022a). In all cases we adopt GIN as the base GNN model. For
a fair comparison, all models will have comparable budgets on the number of
parameters. We also conducted an ablation study to test the effectiveness of
our key component $\phi_{\ell}$, whose results are included in Appendix B.

###  5.1 Small Molecule Property Prediction

We use SPE to learn graph positional encodings on ZINC and Alchemy. We let
$\phi_{l}$ be Deepsets using only the top 8 eigenvectors (PE-8), and be
element-wise MLPs when using all eigenvectors (PE-full). As before, we take to
$\rho$ to be a GIN.

Results. The test mean absolute errorx (MAEs) are shown in Table 1. On ZINC,
SPE performs much better than other baselines, both when using just 8
eigenvectors ($0.0736$) and all eigenvectors ($0.0693$) . On Alchemy, we
always use all eigenvectors since the graph size only ranges from 8 to 12. For
Alchemy we observe no significant improvement of any PE methods over base
model w/o positional encodings. But SPE still achieves the least MAE among all
these models.

###  5.2 Out-Of-Distribution Generalization: Binding Affinity Prediction

Table 2: AUROC results (5 random seeds) on DrugOOD.

Domain | PE Method | ID-Val (AUC) | ID-Test (AUC) | OOD-Val (AUC) | OOD-Test (AUC)
---|---|---|---|---|---
Assay | No PE | $92.92_{\pm 0.14}$ | $92.89_{\pm 0.14}$ | $71.02_{\pm 0.79}$ | $71.68_{\pm 1.10}$
PEG | $92.51_{\pm 0.17}$ | $92.57_{\pm 0.22}$ | $70.86_{\pm 0.44}$ | $71.98_{\pm 0.65}$
SignNet | $92.26_{\pm 0.21}$ | $92.43_{\pm 0.27}$ | $70.16_{\pm 0.56}$ | $\bm{72.27_{\pm 0.97}}$
BasisNet | $88.96_{\pm 1.35}$ | $89.42_{\pm 1.18}$ | $71.19_{\pm 0.72}$ | $71.66_{\pm 0.05}$
| SPE | $92.84_{\pm 0.20}$ | $92.94_{\pm 0.15}$ | $71.26_{\pm 0.62}$ | $\bm{72.53_{\pm 0.66}}$
Scaffold | No PE | $96.56_{\pm 0.10}$ | $87.95_{\pm 0.20}$ | $79.07_{\pm 0.97}$ | $68.00_{\pm 0.60}$
PEG | $95.65_{\pm 0.29}$ | $86.20_{\pm 0.14}$ | $79.17_{\pm 0.29}$ | $\bm{69.15_{\pm 0.75}}$
SignNet | $95.48_{\pm 0.34}$ | $86.73_{\pm 0.56}$ | $77.81_{\pm 0.70}$ | $66.43_{\pm 1.06}$
BasisNet | $85.80_{\pm 3.75}$ | $78.44_{\pm 2.45}$ | $73.36_{\pm 1.44}$ | $66.32_{\pm 5.68}$
| SPE | $96.32_{\pm 0.28}$ | $88.12_{\pm 0.41}$ | $80.03_{\pm 0.58}$ | $\bm{69.64_{\pm 0.49}}$
Size | No PE | $93.78_{\pm 0.12}$ | $93.60_{\pm 0.27}$ | $82.76_{\pm 0.04}$ | $\bm{66.04_{\pm 0.70}}$
PEG | $92.46_{\pm 0.35}$ | $92.67_{\pm 0.23}$ | $82.12_{\pm 0.49}$ | $\bm{66.01_{\pm 0.10}}$
SignNet | $93.30_{\pm 0.43}$ | $93.20_{\pm 0.39}$ | $80.67_{\pm 0.50}$ | $64.03_{\pm 0.70}$
BasisNet | $86.04_{\pm 4.01}$ | $85.51_{\pm 4.04}$ | $75.97_{\pm 1.71}$ | $60.79_{\pm 3.19}$
| SPE | $92.46_{\pm 0.35}$ | $92.67_{\pm 0.23}$ | $82.12_{\pm 0.49}$ | $\bm{66.02_{\pm 1.00}}$
|  |  |  |  |

We study the relation between stability and out-of-distribution generalization
using the DrugOOD dataset (Ji et al., 2023). We take $\phi_{l}$ to be element-
wise MLPs and $\rho$ be GIN as usual.

Results. The results are shown in Table 2. All models have comparable Area
Under ROC (AUC) on the ID-Test set. However, there is a big difference in OOD-
Test performance on Scaffold and Size domains, with the unstable methods
(SignNet and BasisNet) performing much worse than stable methods (No PE, PEG,
SPE). This emphasizes the importance of stability in domain generalization.
Note that this phenomenon is less obvious in the Assay domain, which
hypothesizes is because the Assay domain represents concept (labels) shift
instead of covariant (graph features) shift.

###  5.3 Trade-offs between stability, generalization and expressivity

Figure 2: Training error, test error and generalization gap v.s. model
complexity (stability). In the first row, we directly change the Lipschitz
constant of individual MLPs; in the second row, we choose $\phi_{\ell}$ to be
piecewise spline functions and change the number of pieces.

We hypothesize that stability has different effects on expressive power and
generalization. Intuitively, very high stability means that outputs change
very little as inputs change. Consequently, we expect highly stable models to
have lower expressive power, but to generalize more reliably to new data. To
test this behavior in practice we evaluate SPE on ZINC using 8 eigenvectors.
We control the stability by tuning the complexity of underlying neural
networks in the following two ways:

  1. 1.

Directly control the Lipschitz constant of each MLP in SPE (in both
$\phi_{\ell}$ and $\rho$) by normalizing weight matrices.

  2. 2.

Let $\phi_{\ell}$ be a piecewise cubic spline. Increase the number of spline
pieces from 1 to 6, with fewer splines corresponding to higher stability.

See Appendix B for full details. In both cases we use eight $\phi_{\ell}$
functions. We compute the summary statistics over different random seeds. As a
measure of expressivity, we report the average training loss over the last 10
epochs on ZINC. As a measure of stability, we report the generalization gap
(the difference between the test loss and the training loss) at the best
validation epoch over ZINC.

Results. In Figure 2, we show the trend of training error, test error and
generalization gap as Lipschiz constant of individual MLPs (first row) or the
number of spline pieces (second row) changes. We can see that as model
complexity increases (stability decreases), the training error gets reduced
(more expressive power) while the generalization gap grows. This justifies the
important practical role of model stability for the trade-off between
expressive power and generalization.

###  5.4 Counting Graph Substructures

Figure 3: $\log_{e}(\text{Test MAE})$ over 3 random seeds on cycle counting
task. Lower is better.

To empirically study the expressive power of SPE, we follow prior works that
generate random graphs (Zhao et al., 2022; Huang et al., 2023) and label nodes
according to the number of subtructures they are part of. We aggregate the
node labels to obtain the number of substructures in the overall graph and
view this as a graph regression task. We let $\phi_{l}$ be element-wise MLPs
and $\rho$ be GIN.

Results. Figure 3 shows that SPE significantly outperforms SignNet in counting
3,4,5 and 6-cycles. We emphasize that linear differences in log-MAE correspond
to exponentially large differences in MAE. This result shows that SPE still
achieves very high expressive power, whilst enjoying improved robustness to
domain-shifts thanks to its stability (see Section 5.2).

##  6 Conclusion

We present SPE, a learnable Laplacian positional encoding that is both
provably stable and expressive. Extensive experiments show the effectiveness
of SPE on molecular property prediction benchmarks, the high expressivity in
learning graph substructures, and the robustness as well as generalization
ability under domain shifts. In the future, this technique can be extended to
link prediction or other tasks involving large graphs where stability is also
crucial and desired.

## References

  * Arghal et al. (2022) Raghu Arghal, Eric Lei, and Shirin Saeedi Bidokhti.  Robust graph neural networks via probabilistic lipschitz constraints.  In _Learning for Dynamics and Control Conference_ , pp. 1073–1085. PMLR, 2022.
  * Arvind et al. (2020) Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky.  On weisfeiler-leman invariance: Subgraph counts and related graph properties.  _Journal of Computer and System Sciences_ , 113:42–59, 2020.
  * Barceló et al. (2021) Pablo Barceló, Floris Geerts, Juan Reutter, and Maksimilian Ryschkov.  Graph neural networks with local graph parameters.  _Advances in Neural Information Processing Systems_ , 34:25280–25293, 2021.
  * Bartlett et al. (2017) Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky.  Spectrally-normalized margin bounds for neural networks.  _Advances in neural information processing systems_ , 30, 2017.
  * Bevilacqua et al. (2022) Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, and Haggai Maron.  Equivariant subgraph aggregation networks.  In _International Conference on Learning Representations_ , 2022.
  * Bo et al. (2023) Deyu Bo, Chuan Shi, Lele Wang, and Renjie Liao.  Specformer: Spectral graph neural networks meet transformers.  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * Bouritsas et al. (2022) Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein.  Improving graph neural network expressivity via subgraph isomorphism counting.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 45(1):657–668, 2022.
  * Bronstein et al. (2017) Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst.  Geometric deep learning: going beyond euclidean data.  _IEEE Signal Processing Magazine_ , 34(4):18–42, 2017.
  * Chen et al. (2019) Guangyong Chen, Pengfei Chen, Chang-Yu Hsieh, Chee-Kong Lee, Benben Liao, Renjie Liao, Weiwen Liu, Jiezhong Qiu, Qiming Sun, Jie Tang, Richard S. Zemel, and Shengyu Zhang.  Alchemy: A quantum chemistry dataset for benchmarking ai models.  _CoRR_ , abs/1906.09427, 2019.
  * Chen et al. (2020) Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna.  Can graph neural networks count substructures?  _Advances in neural information processing systems_ , 33:10383–10395, 2020.
  * Chuang & Jegelka (2022) C. Chuang and S. Jegelka.  Tree mover’s distance: Bridging graph metrics and stability of graph neural networks.  In _Neural Information Processing Systems (NeurIPS)_ , 2022.
  * Chung (1997) Fan RK Chung.  _Spectral graph theory_ , volume 92.  American Mathematical Soc., 1997.
  * Cisse et al. (2017) Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier.  Parseval networks: Improving robustness to adversarial examples.  In _International conference on machine learning_ , pp. 854–863. PMLR, 2017.
  * Courty et al. (2017) Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamonjy.  Joint distribution optimal transportation for domain adaptation.  _Advances in neural information processing systems_ , 30, 2017.
  * Duvenaud et al. (2015) David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams.  Convolutional networks on graphs for learning molecular fingerprints.  _Advances in neural information processing systems_ , 28, 2015.
  * Dwivedi & Bresson (2021) Vijay Prakash Dwivedi and Xavier Bresson.  A generalization of transformer networks to graphs.  _AAAI Workshop on Deep Learning on Graphs: Methods and Applications_ , 2021.
  * Dwivedi et al. (2022) Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson.  Graph neural networks with learnable structural and positional representations.  In _International Conference on Learning Representations_ , 2022.
  * Dwivedi et al. (2023) Vijay Prakash Dwivedi, Chaitanya K. Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson.  Benchmarking graph neural networks.  _Journal of Machine Learning Research_ , 24(43):1–48, 2023.
  * Eliasof et al. (2023) Moshe Eliasof, Fabrizio Frasca, Beatrice Bevilacqua, Eran Treister, Gal Chechik, and Haggai Maron.  Graph positional encoding via random feature propagation.  _International Conference on Machine Learning_ , 2023.
  * Gama et al. (2020) Fernando Gama, Joan Bruna, and Alejandro Ribeiro.  Stability properties of graph neural networks.  _IEEE Transactions on Signal Processing_ , 68:5680–5695, 2020.
  * Garg et al. (2020) Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola.  Generalization and representational limits of graph neural networks.  In _International Conference on Machine Learning_ , pp. 3419–3430. PMLR, 2020.
  * Girvan & Newman (2002) Michelle Girvan and Mark EJ Newman.  Community structure in social and biological networks.  _Proceedings of the national academy of sciences_ , 99(12):7821–7826, 2002.
  * Granovetter (1983) Mark Granovetter.  The strength of weak ties: A network theory revisited.  _Sociological theory_ , pp. 201–233, 1983.
  * Horn & Johnson (2012) Roger A Horn and Charles R Johnson.  _Matrix analysis_.  Cambridge university press, 2012.
  * Huang et al. (2023) Yinan Huang, Xingang Peng, Jianzhu Ma, and Muhan Zhang.  Boosting the cycle counting power of graph neural networks with i$^2$-GNNs.  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * Ji et al. (2023) Yuanfeng Ji, Lu Zhang, Jiaxiang Wu, Bingzhe Wu, Lanqing Li, Long-Kai Huang, Tingyang Xu, Yu Rong, Jie Ren, Ding Xue, Houtim Lai, Wei Liu, Junzhou Huang, Shuigeng Zhou, Ping Luo, Peilin Zhao, and Yatao Bian.  Drugood: Out-of-distribution dataset curator and benchmark for ai-aided drug discovery – a focus on affinity prediction problems with noise annotations.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 37(7):8023–8031, 2023.
  * Jiang et al. (2010) Chuntao Jiang, Frans Coenen, and Michele Zito.  Finding frequent subgraphs in longitudinal social network data using a weighted graph mining approach.  In _Advanced Data Mining and Applications: 6th International Conference, ADMA 2010, Chongqing, China, November 19-21, 2010, Proceedings, Part I 6_ , pp. 405–416. Springer, 2010.
  * Kenlay et al. (2020) Henry Kenlay, Dorina Thanou, and Xiaowen Dong.  On the stability of polynomial spectral graph filters.  In _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pp. 5350–5354. IEEE, 2020.
  * Kenlay et al. (2021) Henry Kenlay, Dorina Thano, and Xiaowen Dong.  On the stability of graph convolutional neural networks under edge rewiring.  In _ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pp. 8513–8517. IEEE, 2021.
  * Kim et al. (2022) Jinwoo Kim, Dat Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Seunghoon Hong.  Pure transformers are powerful graph learners.  _Advances in Neural Information Processing Systems_ , 35:14582–14595, 2022.
  * Kipf & Welling (2017) Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In _International Conference on Learning Representations_ , 2017.
  * Koyutürk et al. (2004) Mehmet Koyutürk, Ananth Grama, and Wojciech Szpankowski.  An efficient algorithm for detecting frequent subgraphs in biological networks.  _Bioinformatics_ , 20(suppl_1):i200–i207, 2004.
  * Kreuzer et al. (2021) Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou.  Rethinking graph transformers with spectral attention.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Li et al. (2020) Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec.  Distance encoding: Design provably more powerful neural networks for graph representation learning.  _Advances in Neural Information Processing Systems_ , 2020.
  * Lim et al. (2023) Derek Lim, Joshua David Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka.  Sign and basis invariant networks for spectral graph representation learning.  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * Maron et al. (2019a) Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman.  Provably powerful graph networks.  In _Advances in Neural Information Processing Systems_ , pp. 2153–2164, 2019a.
  * Maron et al. (2019b) Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman.  Invariant and equivariant graph networks.  In _International Conference on Learning Representations_ , 2019b.
  * Maskey et al. (2022) Sohir Maskey, Ali Parviz, Maximilian Thiessen, Hannes Stärk, Ylli Sadikaj, and Haggai Maron.  Generalized laplacian positional encoding for graph representation learning.  In _NeurIPS 2022 Workshop on Symmetry and Geometry in Neural Representations_ , 2022.
  * Morris et al. (2019) Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe.  Weisfeiler and leman go neural: Higher-order graph neural networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pp. 4602–4609, 2019.
  * Morris et al. (2020) Christopher Morris, Gaurav Rattan, and Petra Mutzel.  Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings.  _Advances in Neural Information Processing Systems_ , 33:21824–21840, 2020.
  * Morris et al. (2023) Christopher Morris, Floris Geerts, Jan Tönshoff, and Martin Grohe.  WL meet VC.  In _Proceedings of the 40th International Conference on Machine Learning_ , pp. 25275–25302. PMLR, 2023.
  * Neyshabur et al. (2017) Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro.  Exploring generalization in deep learning.  _Advances in neural information processing systems_ , 30, 2017.
  * Neyshabur et al. (2018) Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro.  A PAC-bayesian approach to spectrally-normalized margin bounds for neural networks.  In _International Conference on Learning Representations_ , 2018.
  * Rampášek et al. (2022) Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini.  Recipe for a general, powerful, scalable graph transformer.  _Advances in Neural Information Processing Systems_ , 35:14501–14515, 2022.
  * Shen et al. (2018) Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu.  Wasserstein distance guided representation learning for domain adaptation.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Sokolić et al. (2017) Jure Sokolić, Raja Giryes, Guillermo Sapiro, and Miguel RD Rodrigues.  Robust large margin deep neural networks.  _IEEE Transactions on Signal Processing_ , 65(16):4265–4280, 2017.
  * Stewart & Sun (1990) Gilbert W Stewart and Ji-guang Sun.  Matrix perturbation theory.  1990\.
  * Stokes et al. (2020) Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M Donghia, Craig R MacNair, Shawn French, Lindsey A Carfrae, Zohar Bloom-Ackermann, et al.  A deep learning approach to antibiotic discovery.  _Cell_ , 180(4):688–702, 2020.
  * Tahmasebi et al. (2020) Behrooz Tahmasebi, Derek Lim, and Stefanie Jegelka.  Counting substructures with higher-order graph neural networks: Possibility and impossibility results.  _arXiv preprint arXiv:2012.03174_ , 2020.
  * Tsuzuku et al. (2018) Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama.  Lipschitz-margin training: Scalable certification of perturbation invariance for deep neural networks.  _Advances in neural information processing systems_ , 31, 2018.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Wang et al. (2022a) Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li.  Equivariant and stable positional encoding for more powerful graph neural networks.  In _International Conference on Learning Representations_ , 2022a.
  * Wang et al. (2022b) Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li.  Equivariant and stable positional encoding for more powerful graph neural networks.  In _International Conference on Learning Representations_ , 2022b.
  * Xu et al. (2021) K. Xu, M. Zhang, J. Li, S. Du, K. Kawarabayashi, and S. Jegelka.  How neural networks extrapolate: From feedforward to graph neural networks.  In _International Conference on Learning Representations_ , 2021.
  * Xu et al. (2019) Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  In _International Conference on Learning Representations_ , 2019.
  * Yehudai et al. (2020) Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, and Haggai Maron.  On size generalization in graph neural networks.  2020\.
  * Ying et al. (2021) Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu.  Do transformers really perform badly for graph representation?  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * You et al. (2019) Jiaxuan You, Rex Ying, and Jure Leskovec.  Position-aware graph neural networks.  In _International Conference on Machine Learning_ , pp. 7134–7143. PMLR, 2019.
  * You et al. (2021) Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovec.  Identity-aware graph neural networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pp. 10737–10745, 2021.
  * Yu et al. (2015) Yi Yu, Tengyao Wang, and Richard J Samworth.  A useful variant of the davis–kahan theorem for statisticians.  _Biometrika_ , 102(2):315–323, 2015.
  * Zaheer et al. (2017) Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola.  Deep sets.  _Advances in neural information processing systems_ , 30, 2017.
  * Zhang & Chen (2018) Muhan Zhang and Yixin Chen.  Link prediction based on graph neural networks.  _Advances in neural information processing systems_ , 31, 2018.
  * Zhang & Li (2021) Muhan Zhang and Pan Li.  Nested graph neural networks.  _Advances in Neural Information Processing Systems_ , 34:15734–15747, 2021.
  * Zhao et al. (2022) Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah.  From stars to subgraphs: Uplifting any GNN with local structure awareness.  In _International Conference on Learning Representations_ , 2022.

##  Appendix A Deferred Proofs

Basic conventions. Let $[n]=\mathbb{Z}\cap[1,n]$ and $\left\llbracket
a,b\right\rrbracket=\mathbb{Z}\cap[a,b]$ denote integer intervals. Let
$\Pi(n)$ be the symmetric group on $n$ elements. Unless otherwise stated,
eigenvalues are counted _with multiplicity_ ; for example, the first and
second smallest eigenvalues of ${\bm{I}}\in\mathbb{R}^{2\times 2}$ are both
$1$. Let $\left\lVert\cdot\right\rVert$ and
$\left\lVert\cdot\right\rVert_{\mathsf{F}}$ be L2-norm and Frobenius norm of
matrices.

Matrix indexing. For any matrix ${\bm{A}}\in\mathbb{R}^{n\times d}$:

  * •

Let $\left[{\bm{A}}\right]_{i,j}\in\mathbb{R}$ be the entry at row $i$ and
column $j$

  * •

Let $\left[{\bm{A}}\right]_{\left\langle i\right\rangle}\in\mathbb{R}^{d}$ be
row $i$ represented as a column vector

  * •

Let $\left[{\bm{A}}\right]_{j}\in\mathbb{R}^{n}$ be column $j$

  * •

For any set
$\mathcal{J}=\left\\{j_{1},\cdots,j_{d^{\prime}}\right\\}\subseteq[d]$, let
$\left[{\bm{A}}\right]_{\mathcal{J}}\in\mathbb{R}^{n\times d^{\prime}}$ be
columns $j_{1},\cdots,j_{d^{\prime}}$ arranged in a matrix

  * •

If $n=d$, let $\operatorname*{diag}({\bm{A}})\in\mathbb{R}^{n}$ be the
diagonal represented as a column vector

  * •

$\operatorname*{diag}$

Special classes of matrices. Define the following sets:

  * •

All $n\times n$ diagonal matrices:
$\mathrm{D}(n)=\left\\{{\bm{D}}\in\mathbb{R}^{n\times n}:\forall i\neq
j,\,\left[{\bm{D}}\right]_{i,j}=0\right\\}$

  * •

The orthogonal group in dimension $n$, i.e. all $n\times n$ orthogonal
matrices: $\mathrm{O}(n)=\left\\{{\bm{Q}}\in\mathbb{R}^{n\times
n}:{\bm{Q}}^{-1}={\bm{Q}}^{\top}\right\\}$

  * •

All $n\times n$ permutation matrices:
$\Pi(n)=\left\\{{\bm{P}}\in\left\\{0,1\right\\}^{n\times
n}:{\bm{P}}^{-1}={\bm{P}}^{\top}\right\\}$

  * •

All $n\times n$ symmetric matrices:
$\mathrm{S}(n)=\left\\{{\bm{A}}\in\mathbb{R}^{n\times
n}:{\bm{A}}={\bm{A}}^{\top}\right\\}$

Spectral graph theory. Many properties of an undirected graph are encoded in
its (normalized) Laplacian matrix, which is always symmetric and positive
semidefinite. In this paper, we only consider connected graphs. The Laplacian
matrix of a connected graph always has a zero eigenvalue with multiplicity $1$
corresponding to an eigenvector of all ones, and all other eigenvalues
positive. The _Laplacian eigenmap_ technique uses the eigenvectors
corresponding to the $d$ smallest positive eigenvalues as vertex positional
encodings. We assume the $d$th and $(d+1)$th smallest positive eigenvalues of
the Laplacian matrices under consideration are distinct. This motivates
definitions for the following sets of matrices:

  * •

All $n\times n$ Laplacian matrices satisfying the properties below:

$\displaystyle\begin{split}\mathrm{L}_{d}(n)=&\\{{\bm{L}}\in\mathrm{S}(n):{\bm{L}}\succeq\mathbf{0}\,\land\,\mathrm{rank}\left({\bm{L}}\right)=n-1\,\land\,{\bm{L}}\mathbf{1}=\mathbf{0}\,\\\
&\land\,\text{$d$-th and $(d+1)$-th smallest positive eigenvalues are
distinct}\\}\end{split}$ (6)

  * •

All $n\times n$ diagonal matrices with positive diagonal entries:
$\mathrm{D}_{+}(n)=\left\\{{\bm{D}}\in\mathrm{D}(n):{\bm{D}}\succ\mathbf{0}\right\\}$

  * •

All $n\times d$ matrices with orthonormal columns:
$\mathrm{O}(n,d)=\left\\{{\bm{Q}}\in\mathbb{R}^{n\times
d}:\left[{\bm{Q}}\right]_{i}\bm{\cdot}\left[{\bm{Q}}\right]_{j}=\mathbbm{1}\left[i=j\right]\right\\}$

Eigenvalues and eigenvectors. For the first two functions below, assume the
given matrix has at least $d$ positive eigenvalues.

  * •

Let $\Uplambda_{d}:\bigcup_{n\geq d}\mathrm{S}(n)\rightarrow\mathrm{D}_{+}(d)$
return a diagonal matrix containing the $d$ smallest positive eigenvalues of
the given matrix, sorted in increasing order.

  * •

Let $\mathscr{X}_{d}:\bigcup_{n\geq d}\mathrm{S}(n)\rightarrow\mathrm{O}(n,d)$
return a matrix whose columns contain an unspecified set of orthonormal
eigenvectors corresponding to the $d$ smallest positive eigenvalues (sorted in
increasing order) of the given matrix.

  * •

Let $\mathscr{X}_{\left\langle d\right\rangle}:\bigcup_{n\geq
d}\mathrm{S}(n)\rightarrow\mathrm{O}(n,d)$ return a matrix whose columns
contain an unspecified set of orthonormal eigenvectors corresponding to the
$d$ smallest eigenvalues (sorted in increasing order) of the given matrix.

  * •

Let $\Uplambda^{d}:\bigcup_{n\geq d}\mathrm{S}(n)\rightarrow\mathrm{D}(d)$
return a diagonal matrix containing the $d$ greatest eigenvalues of the given
matrix, sorted in increasing order.

  * •

Let $\mathscr{X}^{d}:\bigcup_{n\geq d}\mathrm{S}(n)\rightarrow\mathrm{O}(n,d)$
return a matrix whose columns contain an unspecified set of orthonormal
eigenvectors corresponding to the $d$ greatest eigenvalues (sorted in
increasing order) of the given matrix.

Batch submatrix multiplication. Let ${\bm{A}}\in\mathbb{R}^{n\times d}$ be a
matrix and let $\left\\{\mathcal{J}_{k}\right\\}_{k=1}^{p}$ be a partition of
$[d]$. For each $k\in[p]$, let $d_{k}=\left|\mathcal{J}_{k}\right|$ and let
${\bm{B}}_{k}\in\mathbb{R}^{d_{k}\times d_{k}}$ be a matrix. For notational
convenience, let
$\mathcal{B}=\left\\{({\bm{B}}_{k},\mathcal{J}_{k})\right\\}_{k=1}^{p}$.
Define a binary _star operator_ such that

$\displaystyle{\bm{A}}\star\mathcal{B}\in\mathbb{R}^{n\times
d}\enspace\text{is the matrix where}\enspace\forall
k\in[p],\,\left[{\bm{A}}\star\mathcal{B}\right]_{\mathcal{J}_{k}}=\left[{\bm{A}}\right]_{\mathcal{J}_{k}}{\bm{B}}_{k}\,.$
(7)

We primarily use batch submatrix multiplication in the context of orthogonal
invariance, where an orthogonal matrix is applied to each eigenspace. For any
(eigenvalue) matrix $\bm{\Lambda}\in\mathrm{D}(d)$, define

$\displaystyle\mathrm{O}(\bm{\Lambda})=\left\\{\left\\{({\bm{Q}}_{k},\mathcal{J}_{k})\right\\}_{k=1}^{p}:\left\\{{\bm{Q}}_{k}\right\\}_{k=1}^{p}\in\prod_{k=1}^{p}\mathrm{O}(d_{k})\right\\}\,,$
(8)

where
$\mathcal{J}_{k}=\left\\{j\in[d]:\left[\operatorname*{diag}(\bm{\Lambda})\right]_{j}=\sigma_{k}\right\\}$
for each $k\in[p]$ and $\left\\{\sigma_{k}\right\\}_{k=1}^{p}$ are the
distinct values in $\operatorname*{diag}(\bm{\Lambda})$. In this context,
$\mathrm{O}(\bm{\Lambda})$ is the domain of the right operand of $\star$.

###  A.1 Proof of Theorem 3.1

See 3.1

###### Proof.

Fix Laplacians ${\bm{L}},{\bm{L}}^{\prime}\in\mathrm{L}_{d}(n)$. We will show
that for any permutation matrix ${\bm{P}}\in\Pi(n)$,

$\displaystyle\begin{split}\left\lVert\mathrm{SPE}(\mathrm{EVD}({\bm{L}}))-{\bm{P}}\,\mathrm{SPE}(\mathrm{EVD}({\bm{L}}^{\prime}))\right\rVert_{\mathsf{F}}\leq&\left(\alpha_{1}+\alpha_{2}\right)d^{\frac{5}{4}}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}^{\frac{1}{2}}\\\
&+\left(\alpha_{2}\frac{d}{\gamma}+\alpha_{3}\right)\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}\,.\end{split}$
(9)

Fix ${\bm{P}}\in\Pi(n)$. For notational convenience, we denote
$\text{diag}\\{\rho(\bm{\lambda})\\}$ by $\rho(\bm{\Lambda})$ with
$\bm{\Lambda}=\text{diag}\\{\bm{\lambda}\\}$, and let
${\bm{X}}=\mathscr{X}_{d}({\bm{L}})$, $\bm{\Lambda}=\Uplambda_{d}({\bm{L}})$,
${\bm{X}}^{\prime}=\mathscr{X}_{d}({\bm{L}}^{\prime})$, and
$\bm{\Lambda}^{\prime}=\Uplambda_{d}({\bm{L}}^{\prime})$. Then

$\displaystyle\mathrel{\phantom{=}}\left\lVert\mathrm{SPE}(\mathrm{EVD}({\bm{L}}))-{\bm{P}}\,\mathrm{SPE}(\mathrm{EVD}({\bm{L}}^{\prime}))\right\rVert_{\mathsf{F}}$
(10)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(a)}}}{{=}}\left\lVert\bm{\rho}\left({\bm{X}}\bm{\phi}_{1}(\bm{\Lambda}){\bm{X}}^{\top},\cdots,{\bm{X}}\bm{\phi}_{m}(\bm{\Lambda}){\bm{X}}^{\top}\right)-{\bm{P}}\bm{\rho}\left({\bm{X}}^{\prime}\bm{\phi}_{1}\left(\bm{\Lambda}^{\prime}\right){\bm{X}}^{\prime\top},\cdots,{\bm{X}}^{\prime}\bm{\phi}_{m}\left(\bm{\Lambda}^{\prime}\right){\bm{X}}^{\prime\top}\right)\right\rVert_{\mathsf{F}}$
(11)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(b)}}}{{=}}\left\lVert\bm{\rho}\left({\bm{X}}\bm{\phi}_{1}(\bm{\Lambda}){\bm{X}}^{\top},\cdots,{\bm{X}}\bm{\phi}_{m}(\bm{\Lambda}){\bm{X}}^{\top}\right)-\bm{\rho}\left({\bm{P}}{\bm{X}}^{\prime}\bm{\phi}_{1}\left(\bm{\Lambda}^{\prime}\right){\bm{X}}^{\prime\top}{\bm{P}}^{\top},\cdots,{\bm{P}}{\bm{X}}^{\prime}\bm{\phi}_{m}\left(\bm{\Lambda}^{\prime}\right){\bm{X}}^{\prime\top}{\bm{P}}^{\top}\right)\right\rVert_{\mathsf{F}}$
(12)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(c)}}}{{\leq}}J\sum_{\ell=1}^{m}\left\lVert{\bm{X}}\bm{\phi}_{\ell}(\bm{\Lambda}){\bm{X}}^{\top}-{\bm{P}}{\bm{X}}^{\prime}\bm{\phi}_{\ell}\left(\bm{\Lambda}^{\prime}\right){\bm{X}}^{\prime\top}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}$
(13)
$\displaystyle\begin{split}&\stackrel{{\scriptstyle\mathclap{(d)}}}{{\leq}}J\sum_{\ell=1}^{m}\left\lVert{\bm{X}}\bm{\phi}_{\ell}(\bm{\Lambda}){\bm{X}}^{\top}-{\bm{P}}{\bm{X}}^{\prime}\bm{\phi}_{\ell}(\bm{\Lambda}){\bm{X}}^{\prime\top}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}\\\
&\qquad\qquad\qquad+\left\lVert{\bm{P}}{\bm{X}}^{\prime}\bm{\phi}_{\ell}(\bm{\Lambda}){\bm{X}}^{\prime\top}{\bm{P}}^{\top}-{\bm{P}}{\bm{X}}^{\prime}\bm{\phi}_{\ell}\left(\bm{\Lambda}^{\prime}\right){\bm{X}}^{\prime\top}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}\end{split}$
(14)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(e)}}}{{=}}J\sum_{\ell=1}^{m}\biggl{\\{}\underbrace{\left\lVert{\bm{X}}\bm{\phi}_{\ell}(\bm{\Lambda}){\bm{X}}^{\top}-{\bm{P}}{\bm{X}}^{\prime}\bm{\phi}_{\ell}(\bm{\Lambda}){\bm{X}}^{\prime\top}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}}_{\leavevmode\hbox
to7.49pt{\vbox to7.49pt{\pgfpicture\makeatletter\hbox{\hskip
3.74467pt\lower-3.74467pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.54468pt}{0.0pt}\pgfsys@curveto{3.54468pt}{1.95769pt}{1.95769pt}{3.54468pt}{0.0pt}{3.54468pt}\pgfsys@curveto{-1.95769pt}{3.54468pt}{-3.54468pt}{1.95769pt}{-3.54468pt}{0.0pt}\pgfsys@curveto{-3.54468pt}{-1.95769pt}{-1.95769pt}{-3.54468pt}{0.0pt}{-3.54468pt}\pgfsys@curveto{1.95769pt}{-3.54468pt}{3.54468pt}{-1.95769pt}{3.54468pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}+\underbrace{\left\lVert{\bm{X}}^{\prime}\bm{\phi}_{\ell}(\bm{\Lambda}){\bm{X}}^{\prime\top}-{\bm{X}}^{\prime}\bm{\phi}_{\ell}\left(\bm{\Lambda}^{\prime}\right){\bm{X}}^{\prime\top}\right\rVert_{\mathsf{F}}}_{\leavevmode\hbox
to7.49pt{\vbox to7.49pt{\pgfpicture\makeatletter\hbox{\hskip
3.74467pt\lower-3.74467pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.54468pt}{0.0pt}\pgfsys@curveto{3.54468pt}{1.95769pt}{1.95769pt}{3.54468pt}{0.0pt}{3.54468pt}\pgfsys@curveto{-1.95769pt}{3.54468pt}{-3.54468pt}{1.95769pt}{-3.54468pt}{0.0pt}\pgfsys@curveto{-3.54468pt}{-1.95769pt}{-1.95769pt}{-3.54468pt}{0.0pt}{-3.54468pt}\pgfsys@curveto{1.95769pt}{-3.54468pt}{3.54468pt}{-1.95769pt}{3.54468pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\biggr{\\}}\,,$ (15)

where (a) holds by definition of SPE, (b) holds by permutation equivariance of
$\bm{\rho}$, (c) holds by Lipschitz continuity of $\bm{\rho}$, (d) holds by
the triangle inequality, and (e) holds by permutation invariance of Frobenius
norm.

Next, we upper-bound 1. Let
$\delta=\min\left\\{\gamma,d^{-\frac{1}{4}}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}^{\frac{1}{2}}\right\\}$.
The $\delta=0$ case is trivial, because

$\displaystyle\begin{split}\delta=0\iff{\bm{L}}={\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}&\implies\mathrm{SPE}(\mathrm{EVD}({\bm{L}}))=\mathrm{SPE}(\mathrm{EVD}\left({\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right))\\\
&\stackrel{{\scriptstyle\mathclap{(a)}}}{{\iff}}\mathrm{SPE}(\mathrm{EVD}({\bm{L}}))={\bm{P}}\,\mathrm{SPE}(\mathrm{EVD}({\bm{L}}^{\prime}))\,,\end{split}$
(16)

where (a) holds due to permutation equivariance of $\mathrm{SPE}$. Thus,
assume $\delta>0$ for the remainder of this proof. Let

$\displaystyle\left\\{j_{k}\right\\}_{k=1}^{p+1}=\left\\{1\right\\}\cup\left\\{j\in[d+1]:\lambda_{j}-\lambda_{j-1}\geq\delta\right\\},\quad
1=j_{1}<\cdots<j_{p+1}\stackrel{{\scriptstyle\mathclap{(a)}}}{{=}}d+1$ (17)

be the _keypoint_ indices at which eigengaps are greater than or equal to
$\delta$, where (a) holds because

$\displaystyle\lambda_{d+1}-\lambda_{d}=\gamma\geq\min\left\\{\gamma,d^{-\frac{1}{4}}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}^{\frac{1}{2}}\right\\}=\delta\,.$
(18)

For each $k\in[p]$, let $\mathcal{J}_{k}=\left\\{j\in[d]:j_{k}\leq
j<j_{k+1}\right\\}$ be a _chunk_ of contiguous indices at which eigengaps are
less than $\delta$, and let $d_{k}=\left|\mathcal{J}_{k}\right|$ be the size
of the chunk. Define a matrix $\tilde{\bm{\Lambda}}\in\mathrm{D}(d)$ as

$\displaystyle\forall k\in[p],\,\forall
j\in\mathcal{J}_{k},\,\left[\operatorname*{diag}\left(\tilde{\bm{\Lambda}}\right)\right]_{j}=\lambda_{j_{k}}\,.$
(19)

It follows that

$\displaystyle\begin{split}\leavevmode\hbox to9.93pt{\vbox
to9.93pt{\pgfpicture\makeatletter\hbox{\hskip 4.9644pt\lower-4.9644pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&\stackrel{{\scriptstyle\mathclap{(a)}}}{{\leq}}\left\lVert{\bm{X}}\bm{\phi}_{\ell}(\bm{\Lambda}){\bm{X}}^{\top}-{\bm{X}}\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right){\bm{X}}^{\top}\right\rVert_{\mathsf{F}}+\left\lVert{\bm{X}}\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right){\bm{X}}^{\top}-{\bm{P}}{\bm{X}}^{\prime}\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right){\bm{X}}^{\prime\top}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}\\\
&\hskip
140.0pt+\left\lVert{\bm{P}}{\bm{X}}^{\prime}\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right){\bm{X}}^{\prime\top}{\bm{P}}^{\top}-{\bm{P}}{\bm{X}}^{\prime}\bm{\phi}_{\ell}(\bm{\Lambda}){\bm{X}}^{\prime\top}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}\end{split}$
(20)
$\displaystyle\begin{split}&\stackrel{{\scriptstyle\mathclap{(b)}}}{{=}}\left\lVert{\bm{X}}\bm{\phi}_{\ell}(\bm{\Lambda}){\bm{X}}^{\top}-{\bm{X}}\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right){\bm{X}}^{\top}\right\rVert_{\mathsf{F}}+\left\lVert{\bm{X}}\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right){\bm{X}}^{\top}-{\bm{P}}{\bm{X}}^{\prime}\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right){\bm{X}}^{\prime\top}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}\\\
&\hskip
140.0pt+\left\lVert{\bm{X}}^{\prime}\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right){\bm{X}}^{\prime\top}-{\bm{X}}^{\prime}\bm{\phi}_{\ell}(\bm{\Lambda}){\bm{X}}^{\prime\top}\right\rVert_{\mathsf{F}}\end{split}$
(21)
$\displaystyle\begin{split}&\stackrel{{\scriptstyle\mathclap{(c)}}}{{\leq}}\left\lVert{\bm{X}}\right\rVert^{2}\left\lVert\bm{\phi}_{\ell}(\bm{\Lambda})-\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right)\right\rVert_{\mathsf{F}}+\left\lVert{\bm{X}}\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right){\bm{X}}^{\top}-{\bm{P}}{\bm{X}}^{\prime}\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right){\bm{X}}^{\prime\top}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}\\\
&\hskip
110.0pt+\left\lVert{\bm{X}}^{\prime}\right\rVert^{2}\left\lVert\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right)-\bm{\phi}_{\ell}(\bm{\Lambda})\right\rVert_{\mathsf{F}}\end{split}$
(22)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(d)}}}{{=}}2\left\lVert\bm{\phi}_{\ell}(\bm{\Lambda})-\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right)\right\rVert_{\mathsf{F}}+\left\lVert{\bm{X}}\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right){\bm{X}}^{\top}-{\bm{P}}{\bm{X}}^{\prime}\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right){\bm{X}}^{\prime\top}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}$
(23)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(e)}}}{{\leq}}2K_{\ell}\left\lVert\bm{\Lambda}-\tilde{\bm{\Lambda}}\right\rVert_{\mathsf{F}}+\left\lVert{\bm{X}}\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right){\bm{X}}^{\top}-{\bm{P}}{\bm{X}}^{\prime}\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right){\bm{X}}^{\prime\top}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}$
(24)
$\displaystyle\begin{split}&\stackrel{{\scriptstyle\mathclap{(f)}}}{{=}}2K_{\ell}\left\lVert\bm{\Lambda}-\tilde{\bm{\Lambda}}\right\rVert_{\mathsf{F}}\\\
&\hskip
15.0pt+\left\lVert\sum_{k=1}^{p}\left[{\bm{X}}\right]_{\mathcal{J}_{k}}\left[\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right)\right]_{\mathcal{J}_{k},\mathcal{J}_{k}}\left[{\bm{X}}\right]_{\mathcal{J}_{k}}^{\top}-{\bm{P}}\left(\sum_{k=1}^{p}\left[{\bm{X}}^{\prime}\right]_{\mathcal{J}_{k}}\left[\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right)\right]_{\mathcal{J}_{k},\mathcal{J}_{k}}\left[{\bm{X}}^{\prime}\right]_{\mathcal{J}_{k}}^{\top}\right){\bm{P}}^{\top}\right\rVert_{\mathsf{F}}\end{split}$
(25)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(g)}}}{{\leq}}2K_{\ell}\underbrace{\left\lVert\bm{\Lambda}-\tilde{\bm{\Lambda}}\right\rVert_{\mathsf{F}}}_{\leavevmode\hbox
to7.49pt{\vbox to7.49pt{\pgfpicture\makeatletter\hbox{\hskip
3.74467pt\lower-3.74467pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.54468pt}{0.0pt}\pgfsys@curveto{3.54468pt}{1.95769pt}{1.95769pt}{3.54468pt}{0.0pt}{3.54468pt}\pgfsys@curveto{-1.95769pt}{3.54468pt}{-3.54468pt}{1.95769pt}{-3.54468pt}{0.0pt}\pgfsys@curveto{-3.54468pt}{-1.95769pt}{-1.95769pt}{-3.54468pt}{0.0pt}{-3.54468pt}\pgfsys@curveto{1.95769pt}{-3.54468pt}{3.54468pt}{-1.95769pt}{3.54468pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}+\sum_{k=1}^{p}\underbrace{\left\lVert\left[{\bm{X}}\right]_{\mathcal{J}_{k}}\left[\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right)\right]_{\mathcal{J}_{k},\mathcal{J}_{k}}\left[{\bm{X}}\right]_{\mathcal{J}_{k}}^{\top}-{\bm{P}}\left[{\bm{X}}^{\prime}\right]_{\mathcal{J}_{k}}\left[\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right)\right]_{\mathcal{J}_{k},\mathcal{J}_{k}}\left[{\bm{X}}^{\prime}\right]_{\mathcal{J}_{k}}^{\top}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}}_{\leavevmode\hbox
to7.49pt{\vbox to7.49pt{\pgfpicture\makeatletter\hbox{\hskip
3.74467pt\lower-3.74467pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.54468pt}{0.0pt}\pgfsys@curveto{3.54468pt}{1.95769pt}{1.95769pt}{3.54468pt}{0.0pt}{3.54468pt}\pgfsys@curveto{-1.95769pt}{3.54468pt}{-3.54468pt}{1.95769pt}{-3.54468pt}{0.0pt}\pgfsys@curveto{-3.54468pt}{-1.95769pt}{-1.95769pt}{-3.54468pt}{0.0pt}{-3.54468pt}\pgfsys@curveto{1.95769pt}{-3.54468pt}{3.54468pt}{-1.95769pt}{3.54468pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\,,$ (26)

where (a) holds by the triangle inequality, (b) holds by permutation
invariance of Frobenius norm, (c) holds by lemma A.1, (d) holds because
${\bm{X}}$ and ${\bm{X}}^{\prime}$ have orthonormal columns, (e) holds by
Lipschitz continuity of $\bm{\phi}_{\ell}$, (f) holds by block matrix algebra,
and (g) holds by the triangle inequality. Next, we upper-bound 3:

3
$\displaystyle\stackrel{{\scriptstyle\mathclap{(a)}}}{{=}}\sqrt{\sum_{k=1}^{p}\sum_{j\in\mathcal{J}_{k}}(\lambda_{j}-\lambda_{j_{k}})^{2}}$
(27)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(b)}}}{{=}}\sqrt{\sum_{k=1}^{p}\sum_{j\in\mathcal{J}_{k}}\left(\sum_{j^{\prime}=j_{k}+1}^{j}(\lambda_{j^{\prime}}-\lambda_{j^{\prime}-1})\right)^{2}}$
(28)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(c)}}}{{\leq}}\sqrt{\sum_{k=1}^{p}\sum_{j\in\mathcal{J}_{k}}\left(\sum_{j^{\prime}=j_{k}+1}^{j}\delta\right)^{2}}$
(29)
$\displaystyle=\delta\sqrt{\sum_{k=1}^{p}\sum_{j\in\mathcal{J}_{k}}(j-j_{k})^{2}}$
(30)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(d)}}}{{=}}\delta\sqrt{\sum_{k=1}^{p}\sum_{j=1}^{d_{k}-1}j^{2}}$
(31) $\displaystyle\leq\delta\sqrt{\sum_{k=1}^{p}d_{k}^{3}}\,,$ (32)

where (a) holds by definition of $\tilde{\bm{\Lambda}}$, (b) holds because the
innermost sum in (b) telescopes, (c) holds because $\mathcal{J}_{k}$ is a
chunk of contiguous indices at which eigengaps are less than $\delta$, and (d)
holds because $\mathcal{J}_{k}$ is a contiguous integer interval.

Next, we upper-bound 4. By definition of $\tilde{\bm{\Lambda}}$, the entries
$\left[\operatorname*{diag}\left(\tilde{\bm{\Lambda}}\right)\right]_{j}$ are
equal for all $j\in\mathcal{J}_{k}$. By permutation equivariance of
$\bm{\phi}_{\ell}$, the entries
$\left[\operatorname*{diag}\left(\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right)\right)\right]_{j}$
are equal for all $j\in\mathcal{J}_{k}$. Thus,
$\left[\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right)\right]_{\mathcal{J}_{k},\mathcal{J}_{k}}=\mu_{\ell,k}{\bm{I}}$
for some $\mu_{\ell,k}\in\mathbb{R}$. As $\phi_{\ell}$ is Lipschitz continuous
and defined on a bounded domain $[0,2]^{d}$, it must be bounded by constant
$M_{\ell}=\sup_{\bm{\lambda}\in[0,2]^{d}}\phi_{\ell}(\bm{\lambda})$. Then by
boundedness of $\bm{\phi}_{\ell}$,

$\displaystyle\left|\mu_{\ell,k}\right|=\frac{1}{\sqrt{d_{k}}}\left\lVert\mu_{\ell,k}{\bm{I}}\right\rVert_{\mathsf{F}}=\frac{1}{\sqrt{d_{k}}}\left\lVert\left[\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right)\right]_{\mathcal{J}_{k},\mathcal{J}_{k}}\right\rVert_{\mathsf{F}}\leq\frac{1}{\sqrt{d_{k}}}\left\lVert\bm{\phi}_{\ell}\left(\tilde{\bm{\Lambda}}\right)\right\rVert_{\mathsf{F}}\leq\frac{M_{\ell}}{\sqrt{d_{k}}}\,.$
(33)

Therefore,

4
$\displaystyle=\left\lVert\left[{\bm{X}}\right]_{\mathcal{J}_{k}}(\mu_{\ell,k}{\bm{I}})\left[{\bm{X}}\right]_{\mathcal{J}_{k}}^{\top}-{\bm{P}}\left[{\bm{X}}^{\prime}\right]_{\mathcal{J}_{k}}(\mu_{\ell,k}{\bm{I}})\left[{\bm{X}}^{\prime}\right]_{\mathcal{J}_{k}}^{\top}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}$
(34)
$\displaystyle=\left|\mu_{\ell,k}\right|\left\lVert\left[{\bm{X}}\right]_{\mathcal{J}_{k}}\left[{\bm{X}}\right]_{\mathcal{J}_{k}}^{\top}-{\bm{P}}\left[{\bm{X}}^{\prime}\right]_{\mathcal{J}_{k}}\left[{\bm{X}}^{\prime}\right]_{\mathcal{J}_{k}}^{\top}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}$
(35)
$\displaystyle\leq\frac{M_{\ell}}{\sqrt{d_{k}}}\left\lVert\left[{\bm{X}}\right]_{\mathcal{J}_{k}}\left[{\bm{X}}\right]_{\mathcal{J}_{k}}^{\top}-{\bm{P}}\left[{\bm{X}}^{\prime}\right]_{\mathcal{J}_{k}}\left[{\bm{X}}^{\prime}\right]_{\mathcal{J}_{k}}^{\top}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}\,.$
(36)

Now, we consider two cases. Case 1: $k\geq 2$ or
$\lambda_{1}-\lambda_{0}\geq\delta$. Define the matrices

$\displaystyle{\bm{Z}}_{k}=\left[{\bm{X}}\right]_{\mathcal{J}_{k}}\enspace\text{and}\enspace{\bm{Z}}^{\prime}_{k}=\left[{\bm{X}}^{\prime}\right]_{\mathcal{J}_{k}}\,.$
(37)

There exists an orthogonal matrix ${\bm{Q}}_{k}\in\mathrm{O}(d_{k})$ such that

$\displaystyle\left\lVert{\bm{Z}}_{k}-{\bm{P}}{\bm{Z}}^{\prime}_{k}{\bm{Q}}_{k}\right\rVert_{\mathsf{F}}$
$\displaystyle\stackrel{{\scriptstyle\mathclap{(a)}}}{{=}}\left\lVert\left[\mathscr{X}_{d}({\bm{L}})\right]_{\mathcal{J}_{k}}-\left[\mathscr{X}_{d}\left({\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right)\right]_{\mathcal{J}_{k}}{\bm{Q}}_{k}\right\rVert_{\mathsf{F}}$
(38)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(b)}}}{{\leq}}\frac{\sqrt{8}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}}{\min\left\\{\lambda_{j_{k}}-\lambda_{j_{k}-1},\lambda_{j_{k+1}}-\lambda_{j_{k+1}-1}\right\\}}$
(39)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(c)}}}{{\leq}}\frac{\sqrt{8}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}}{\delta}\,,$
(40)

where (a) holds by lemmas A.2 and A.3, (b) holds by proposition A.1,222We can
apply proposition A.1 because $\mathscr{X}_{d}$ extracts the same contiguous
interval of eigenvalue indices for any matrix in $\mathrm{L}_{d}(n)$, and
${\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\in\mathrm{L}_{d}(n)$ by lemmas A.2
and A.3. and (c) holds because $j_{k}$ and $j_{k+1}$ are keypoint indices at
which eigengaps are greater than or equal to $\delta$.

Case 2: $k=1$ and $\lambda_{1}-\lambda_{0}<\delta$. Define the matrices

$\displaystyle{\bm{Z}}_{1}=\begin{bmatrix}\frac{1}{\sqrt{n}}\mathbf{1}&\left[{\bm{X}}\right]_{\mathcal{J}_{1}}\end{bmatrix}\enspace\text{and}\enspace{\bm{Z}}^{\prime}_{1}=\begin{bmatrix}\frac{1}{\sqrt{n}}\mathbf{1}&\left[{\bm{X}}^{\prime}\right]_{\mathcal{J}_{1}}\end{bmatrix}\,.$
(41)

There exists an orthogonal matrix ${\bm{Q}}_{1}\in\mathrm{O}(d_{1}+1)$ such
that

$\displaystyle\left\lVert{\bm{Z}}_{1}-{\bm{P}}{\bm{Z}}^{\prime}_{1}{\bm{Q}}_{1}\right\rVert_{\mathsf{F}}$
$\displaystyle\stackrel{{\scriptstyle\mathclap{(a)}}}{{=}}\left\lVert\mathscr{X}_{\left\langle
d_{1}+1\right\rangle}({\bm{L}})-\mathscr{X}_{\left\langle
d_{1}+1\right\rangle}\left({\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right)\,{\bm{Q}}_{1}\right\rVert_{\mathsf{F}}$
(42)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(b)}}}{{\leq}}\frac{\sqrt{8}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}}{\lambda_{j_{2}}-\lambda_{j_{2}-1}}$
(43)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(c)}}}{{\leq}}\frac{\sqrt{8}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}}{\delta}\,,$
(44)

where (a) holds by lemmas A.2 and A.3, (b) holds by proposition A.1,333We can
apply proposition A.1 because $\mathscr{X}_{\left\langle
d_{1}+1\right\rangle}$ extracts the same contiguous interval of eigenvalue
indices for any matrix. and (c) holds because $j_{2}$ is a keypoint index at
which the eigengap is greater than or equal to $\delta$.

Hence, in both cases,

$\displaystyle\quad\left\lVert\left[{\bm{X}}\right]_{\mathcal{J}_{k}}\left[{\bm{X}}\right]_{\mathcal{J}_{k}}^{\top}-{\bm{P}}\left[{\bm{X}}^{\prime}\right]_{\mathcal{J}_{k}}\left[{\bm{X}}^{\prime}\right]_{\mathcal{J}_{k}}^{\top}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}\stackrel{{\scriptstyle\mathclap{(a)}}}{{=}}\left\lVert{\bm{Z}}_{k}{\bm{Z}}_{k}^{\top}-{\bm{P}}{\bm{Z}}^{\prime}_{k}{\bm{Z}}_{k}^{\prime\top}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}$
(45)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(b)}}}{{=}}\left\lVert{\bm{Z}}_{k}{\bm{Z}}_{k}^{\top}-{\bm{P}}{\bm{Z}}^{\prime}_{k}{\bm{Q}}_{k}{\bm{Q}}_{k}^{\top}{\bm{Z}}_{k}^{\prime\top}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}$
(46)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(c)}}}{{\leq}}\left\lVert{\bm{Z}}_{k}{\bm{Z}}_{k}^{\top}-{\bm{Z}}_{k}{\bm{Q}}_{k}^{\top}{\bm{Z}}_{k}^{\prime\top}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}+\left\lVert{\bm{Z}}_{k}{\bm{Q}}_{k}^{\top}{\bm{Z}}_{k}^{\prime\top}{\bm{P}}^{\top}-{\bm{P}}{\bm{Z}}^{\prime}_{k}{\bm{Q}}_{k}{\bm{Q}}_{k}^{\top}{\bm{Z}}_{k}^{\prime\top}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}$
(47)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(d)}}}{{\leq}}\left\lVert{\bm{Z}}_{k}\right\rVert\left\lVert{\bm{Z}}_{k}^{\top}-{\bm{Q}}_{k}^{\top}{\bm{Z}}_{k}^{\prime\top}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}+\left\lVert{\bm{Z}}_{k}-{\bm{P}}{\bm{Z}}^{\prime}_{k}{\bm{Q}}_{k}\right\rVert_{\mathsf{F}}\left\lVert{\bm{Q}}_{k}\right\rVert\left\lVert{\bm{Z}}_{k}^{\prime}\right\rVert\left\lVert{\bm{P}}\right\rVert$
(48)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(e)}}}{{=}}\left\lVert{\bm{Z}}_{k}^{\top}-{\bm{Q}}_{k}^{\top}{\bm{Z}}_{k}^{\prime\top}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}+\left\lVert{\bm{Z}}_{k}-{\bm{P}}{\bm{Z}}^{\prime}_{k}{\bm{Q}}_{k}\right\rVert_{\mathsf{F}}$
(49)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(f)}}}{{=}}2\left\lVert{\bm{Z}}_{k}-{\bm{P}}{\bm{Z}}^{\prime}_{k}{\bm{Q}}_{k}\right\rVert_{\mathsf{F}}$
(50)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(g)}}}{{\leq}}\frac{\sqrt{32}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}}{\delta}\,,$
(51)

where (a) holds in Case 2 because

$\displaystyle\hskip
10.0pt\left[{\bm{X}}\right]_{\mathcal{J}_{k}}\left[{\bm{X}}\right]_{\mathcal{J}_{k}}^{\top}-{\bm{P}}\left[{\bm{X}}^{\prime}\right]_{\mathcal{J}_{k}}\left[{\bm{X}}^{\prime}\right]_{\mathcal{J}_{k}}^{\top}{\bm{P}}^{\top}$
(52)
$\displaystyle=\frac{1}{n}\mathbf{1}\mathbf{1}^{\top}+\left[{\bm{X}}\right]_{\mathcal{J}_{k}}\left[{\bm{X}}\right]_{\mathcal{J}_{k}}^{\top}-\frac{1}{n}\mathbf{1}\mathbf{1}^{\top}-{\bm{P}}\left[{\bm{X}}^{\prime}\right]_{\mathcal{J}_{k}}\left[{\bm{X}}^{\prime}\right]_{\mathcal{J}_{k}}^{\top}{\bm{P}}^{\top}$
(53)
$\displaystyle=\frac{1}{n}\mathbf{1}\mathbf{1}^{\top}+\left[{\bm{X}}\right]_{\mathcal{J}_{k}}\left[{\bm{X}}\right]_{\mathcal{J}_{k}}^{\top}-{\bm{P}}\left(\frac{1}{n}\mathbf{1}\mathbf{1}^{\top}+\left[{\bm{X}}^{\prime}\right]_{\mathcal{J}_{k}}\left[{\bm{X}}^{\prime}\right]_{\mathcal{J}_{k}}^{\top}\right){\bm{P}}^{\top}$
(54)
$\displaystyle=\begin{bmatrix}\frac{1}{\sqrt{n}}\mathbf{1}&\left[{\bm{X}}\right]_{\mathcal{J}_{k}}\end{bmatrix}\begin{bmatrix}\frac{1}{\sqrt{n}}\mathbf{1}^{\top}\\\
\left[{\bm{X}}\right]_{\mathcal{J}_{k}}^{\top}\end{bmatrix}-{\bm{P}}\begin{bmatrix}\frac{1}{\sqrt{n}}\mathbf{1}&\left[\mathbf{X^{\prime}}\right]_{\mathcal{J}_{k}}\end{bmatrix}\begin{bmatrix}\frac{1}{\sqrt{n}}\mathbf{1}^{\top}\\\
\left[\mathbf{X^{\prime}}\right]_{\mathcal{J}_{k}}^{\top}\end{bmatrix}{\bm{P}}^{\top}$
(55)
$\displaystyle={\bm{Z}}_{k}{\bm{Z}}_{k}^{\top}-{\bm{P}}{\bm{Z}}^{\prime}_{k}{\bm{Z}}_{k}^{\prime\top}{\bm{P}}^{\top}\,,$
(56)

(b) holds because ${\bm{Q}}_{k}{\bm{Q}}_{k}^{\top}={\bm{I}}$, (c) holds by the
triangle inequality, (d) holds by lemma A.1, (e) holds because ${\bm{Z}}_{k}$
and ${\bm{Z}}^{\prime}_{k}$ have orthonormal columns and ${\bm{Q}}_{k}$ and
${\bm{P}}$ are orthogonal, (f) holds because Frobenius norm is invariant to
matrix transpose, and (g) holds by substituting in eqs. 40 and 44. Combining
these results,

$\displaystyle\leavevmode\hbox to9.93pt{\vbox
to9.93pt{\pgfpicture\makeatletter\hbox{\hskip 4.9644pt\lower-4.9644pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\leq\frac{\sqrt{32}\,M_{\ell}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}}{\sqrt{d_{k}}\,\delta}\,.$
(57)

Next, we upper-bound 2:

2
$\displaystyle\stackrel{{\scriptstyle\mathclap{(a)}}}{{\leq}}\left\lVert{\bm{X}}^{\prime}\right\rVert^{2}\left\lVert\bm{\phi}_{\ell}(\bm{\Lambda})-\bm{\phi}_{\ell}\left(\bm{\Lambda}^{\prime}\right)\right\rVert_{\mathsf{F}}$
(58)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(b)}}}{{=}}\left\lVert\bm{\phi}_{\ell}(\bm{\Lambda})-\bm{\phi}_{\ell}\left(\bm{\Lambda}^{\prime}\right)\right\rVert_{\mathsf{F}}$
(59)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(c)}}}{{\leq}}K_{\ell}\left\lVert\bm{\Lambda}-\bm{\Lambda}^{\prime}\right\rVert_{\mathsf{F}}$
(60)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(d)}}}{{=}}K_{\ell}\sqrt{\sum_{j=1}^{d}\left(\lambda_{j}-\lambda^{\prime}_{j}\right)^{2}}$
(61)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(e)}}}{{\leq}}K_{\ell}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}\,,$
(62)

where (a) holds by lemma A.1, (b) holds because ${\bm{X}}^{\prime}$ has
orthonormal columns, (c) holds by Lipschitz continuity of $\bm{\phi}_{\ell}$,
the notation $\lambda^{\prime}_{j}$ in (d) is the $j$th smallest positive
eigenvalue of ${\bm{L}}^{\prime}$, and (e) holds by propositions A.3 and A.3.

Combining our results above,

$\displaystyle\mathrel{\phantom{=}}\left\lVert\mathrm{SPE}_{n,d}({\bm{L}})-{\bm{P}}\,\mathrm{SPE}_{n,d}({\bm{L}}^{\prime})\right\rVert_{\mathsf{F}}$
(63)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(a)}}}{{\leq}}J\sum_{\ell=1}^{m}\left\\{2K_{\ell}\delta\sqrt{\sum_{k=1}^{p}d_{k}^{3}}+\sum_{k=1}^{p}\frac{4\sqrt{2}\,M_{\ell}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}}{\sqrt{d_{k}}\,\delta}+K_{\ell}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}\right\\}$
(64)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(b)}}}{{\leq}}J\sum_{\ell=1}^{m}\left\\{2K_{\ell}d^{\frac{3}{2}}\delta+4\sqrt{2}\,M_{\ell}d\,\frac{\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}}{\delta}+K_{\ell}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}\right\\}$
(65)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(c)}}}{{=}}\alpha_{1}d^{\frac{3}{2}}\delta+\alpha_{2}d\,\frac{\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}}{\delta}+\alpha_{3}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}$
(66)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(d)}}}{{\leq}}\left(\alpha_{1}+\alpha_{2}\right)d^{\frac{5}{4}}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}^{\frac{1}{2}}+\left(\alpha_{2}\frac{d}{\gamma}+\alpha_{3}\right)\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}$
(67)

as desired, where (a) holds by substituting in 1-4, (b) holds because
$\sum_{k=1}^{p}d_{k}^{3}\leq\left(\sum_{k=1}^{p}d_{k}\right)^{3}=d^{3}$ and
$\sum_{k=1}^{p}\frac{1}{\sqrt{d_{k}}}\leq p\leq d$, (c) holds by the
definition of $\alpha_{1}$ through $\alpha_{3}$, and (d) holds because

$\displaystyle\delta$ $\displaystyle\leq
d^{-\frac{1}{4}}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}^{\frac{1}{2}}\,,$
(68)
$\displaystyle\frac{\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}}{\delta}$
$\displaystyle\leq\frac{\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}}{\gamma}+d^{\frac{1}{4}}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}^{\frac{1}{2}}\,.$
(69)

∎

###  A.2 Proof of Proposition 3.1

See 3.1

###### Proof.

The proof goes in two steps. The first step shows that a Lipschitz continuous
base GNN with a H$\ddot{\text{o}}$lder continuity SPE yields an overall
H$\ddot{\text{o}}$lder continuity predictive model. The second step shows that
this H$\ddot{\text{o}}$lder continuous predictive model has a bounded
generalization gap under domain shift.

Step 1: Suppose base GNN model $\text{GNN}({\bm{L}},{\bm{X}})$ is
$C$-Lipschitz and SPE method $\text{SPE}({\bm{L}})$ satifies Theorem 3.1. Let
our predictive model be
$h({\bm{L}})=\text{GNN}({\bm{L}},\mathrm{SPE}(\mathrm{EVD}({\bm{L}})))\in\mathbb{R}$.
Then for any Laplacians ${\bm{L}},{\bm{L}}^{\prime}\in$ and any permutation
${\bm{P}}\in\Pi(n)$ we have

$\displaystyle|h({\bm{L}})-h({\bm{L}}^{\prime})|$
$\displaystyle=|\mathrm{GNN}({\bm{L}},\mathrm{SPE}(\mathrm{EVD}({\bm{L}})))-\mathrm{GNN}({\bm{L}}^{\prime},\mathrm{SPE}(\mathrm{EVD}({\bm{L}}^{\prime}))|$
(70)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(a)}}}{{\leq}}C\left(\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}\right\rVert_{\mathsf{F}}+\left\lVert\mathrm{SPE}(\mathrm{EVD}({\bm{L}}))-{\bm{P}}\mathrm{SPE}(\mathrm{EVD}({\bm{L}}^{\prime}))\right\rVert_{\mathsf{F}}\right)$
(71)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(b)}}}{{\leq}}C\left(1+\alpha_{2}\frac{d}{\gamma}+\alpha_{3}\right)\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}+C\left(\alpha_{1}+\alpha_{2}\right)d^{5/4}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}^{1/2},$
(72)
$\displaystyle\vcentcolon=C_{1}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}+C_{2}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}^{1/2},$
(73)

where (a) holds by continuity assumption of base GNN, and (b) holds by the
stability result Theorem 3.1.

Step 2: Suppose the ground-truth function $h^{*}$ lies in our hypothesis space
(thus also satisfies eq. (73)). The absolute risk on source and target domain
are defined
$\varepsilon_{s}(h)=\mathbb{E}_{{\bm{L}}\sim\mathbb{P}_{\mathcal{S}}}|h({\bm{L}})-h^{*}({\bm{L}})|$
and
$\varepsilon_{t}(h)=\mathbb{E}_{{\bm{L}}\sim\mathbb{P}_{\mathcal{T}}}|h({\bm{L}})-h^{*}({\bm{L}})|$
respectively. Note that function $f({\bm{L}})=|h({\bm{L}})-h^{*}({\bm{L}})|$
is also H$\ddot{\text{o}}$lder continuous but with two times larger
H$\ddot{\text{o}}$lder constant. This is because

$\displaystyle|h({\bm{L}})-h^{*}({\bm{L}})|$
$\displaystyle\leq|h({\bm{L}})-h({\bm{L}}^{\prime})|+|h({\bm{L}}^{\prime})-h^{*}({\bm{L}})|\quad(\text{triangle's
inequality for arbitrary }{\bm{L}}^{\prime})$ (74)
$\displaystyle\leq|h({\bm{L}})-h({\bm{L}}^{\prime})|+|h({\bm{L}}^{\prime})-h^{*}({\bm{L}}^{\prime})|+|h^{*}({\bm{L}})-h^{*}({\bm{L}}^{\prime})|\quad(\text{triangle's
inequality}),$ (75)

and thus for arbitrary ${\bm{L}},{\bm{L}}^{\prime}$,

$\displaystyle f({\bm{L}})-f({\bm{L}}^{\prime})$
$\displaystyle=|h({\bm{L}})-h^{*}({\bm{L}})|-|h({\bm{L}}^{\prime})-h^{*}({\bm{L}}^{\prime})|\leq|h({\bm{L}})-h({\bm{L}}^{\prime})|+|h^{*}({\bm{L}})-h^{*}({\bm{L}}^{\prime})|$
(76) $\displaystyle\leq
2C_{1}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}+2C_{2}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}^{1/2}.$
(77)

We can show the same bound for $f({\bm{L}}^{\prime})-f({\bm{L}})$. Thus $f$ is
H$\ddot{\text{o}}$lder continuous with constants $2C_{1},2C_{2}$, and we
denote such property by $\left\lVert f\right\rVert_{H}\leq(2C_{1},2C_{2})$ for
notation convenience.

An upper bound of generalization gap $\varepsilon_{t}(h)-\varepsilon_{s}(h)$
can be obtained:

$\displaystyle\varepsilon_{t}(h)-\varepsilon_{s}(h)$
$\displaystyle=\mathbb{E}_{{\bm{L}}\sim\mathbb{P}_{\mathcal{T}}}|h({\bm{L}})-h^{*}({\bm{L}})|-\mathbb{E}_{{\bm{L}}\sim\mathbb{P}_{\mathcal{S}}}|h({\bm{L}})-h^{*}({\bm{L}})|$
(78)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(a)}}}{{\leq}}\sup_{\left\lVert
f\right\rVert_{H}\leq(C_{1},C_{2})}\mathbb{E}_{{\bm{L}}\sim\mathbb{P}_{\mathcal{T}}}f({\bm{L}})-\mathbb{E}_{{\bm{L}}\sim\mathbb{P}_{\mathcal{S}}}f({\bm{L}})$
(79) $\displaystyle=\sup_{\left\lVert f\right\rVert_{H}\leq(C_{1},C_{2})}\int
f({\bm{L}})(\mathbb{P}_{\mathcal{T}}({\bm{L}})-\mathbb{P}_{\mathcal{S}}({\bm{L}}))\mathrm{d}{\bm{L}}$
(80)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(b)}}}{{=}}\inf_{\pi\in\Pi(n)(\mathbb{P}_{\mathcal{T}},\mathbb{P}_{\mathcal{S}})}\sup_{\left\lVert
f\right\rVert_{H}\leq(C_{1},C_{2})}\int(f({\bm{L}})-f({\bm{L}}^{\prime}))\pi({\bm{L}},{\bm{L}}^{\prime})\mathrm{d}{\bm{L}}\mathrm{d}{\bm{L}}^{\prime}$
(81)

where (a) holds because
$\left\lVert|h({\bm{L}})-h^{*}({\bm{L}})|\right\rVert_{H}\leq(C_{1},C_{2})$,
and (b) holds because of the definition of product distribution

$\Pi(\mathbb{P}_{\mathcal{T}},\mathbb{P}_{\mathcal{S}})=\left\\{\pi:\int\pi({\bm{L}},{\bm{L}}^{\prime})\mathrm{d}{\bm{L}}^{\prime}=\mathbb{P}_{\mathcal{T}}({\bm{L}})\,\land\
\int\pi({\bm{L}},{\bm{L}}^{\prime})\mathrm{d}{\bm{L}}=\mathbb{P}_{\mathcal{S}}({\bm{L}})\right\\}.$

Notice the integral can be further upper bounded using H$\ddot{\text{o}}$lder
continuity of $f$:

$\displaystyle\begin{split}&\sup_{\left\lVert
f\right\rVert_{H}\leq(C_{1},C_{2})}\int(f({\bm{L}})-f({\bm{L}}^{\prime}))\pi({\bm{L}},{\bm{L}}^{\prime})\mathrm{d}{\bm{L}}\mathrm{d}{\bm{L}}^{\prime}\\\
&\leq\int\left(2C_{1}\min_{{\bm{P}}\in\Pi(n)}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}+2C_{2}\min_{{\bm{P}}\in\Pi(n)}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}^{1/2}\right)\pi({\bm{L}},{\bm{L}}^{\prime})\mathrm{d}{\bm{L}}\mathrm{d}{\bm{L}}^{\prime}.\end{split}$
(82)

Let us define the Wasserstein distance of $\mathbb{P}_{\mathcal{T}}$ and
$\mathbb{P}_{\mathcal{S}}$ be

$W(\mathbb{P}_{\mathcal{T}},\mathbb{P}_{\mathcal{S}})=\inf_{\pi\in\Pi(\mathbb{P}_{\mathcal{T}},\mathbb{P}_{\mathcal{S}})}\int\min_{{\bm{P}}\in\Pi(n)}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}\pi({\bm{L}},{\bm{L}}^{\prime})\mathrm{d}{\bm{L}}\mathrm{d}{\bm{L}}^{\prime}.$
(83)

Then plugging eqs. (82, 83) into (81) yields the desired result

$\displaystyle\varepsilon_{t}(h)-\varepsilon_{s}(h)$ $\displaystyle\leq
2C_{1}W(\mathbb{P}_{\mathcal{T}},\mathbb{P}_{\mathcal{S}})+2C_{2}\inf_{\pi\in\Pi(\mathbb{P}_{\mathcal{T}},\mathbb{P}_{\mathcal{S}})}\int\min_{{\bm{P}}\in\Pi(n)}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}^{1/2}\pi({\bm{L}},{\bm{L}}^{\prime})\mathrm{d}{\bm{L}}\mathrm{d}{\bm{L}}^{\prime}$
(84)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(a)}}}{{\leq}}2C_{1}W(\mathbb{P}_{\mathcal{T}},\mathbb{P}_{\mathcal{S}})+2C_{2}\inf_{\pi\in\Pi(\mathbb{P}_{\mathcal{T}},\mathbb{P}_{\mathcal{S}})}\left(\int\min_{{\bm{P}}\in\Pi(n)}\left\lVert{\bm{L}}-{\bm{P}}{\bm{L}}^{\prime}{\bm{P}}^{\top}\right\rVert_{\mathsf{F}}\pi({\bm{L}},{\bm{L}}^{\prime})\mathrm{d}{\bm{L}}\mathrm{d}{\bm{L}}^{\prime}\right)^{1/2}$
(85)
$\displaystyle=2C_{1}W(\mathbb{P}_{\mathcal{T}},\mathbb{P}_{\mathcal{S}})+2C_{2}W^{1/2}(\mathbb{P}_{\mathcal{T}},\mathbb{P}_{\mathcal{S}}),$
(86)

where (a) holds due to the concavity of sqrt root function. ∎

###  A.3 Proof of Proposition 3.2

See 3.2

###### Proof.

In the proof we are going to show basis universality by expressing BasisNet.
Fix eigenvalues $\bm{\lambda}\in\mathbb{R}^{d}$. Let
$\tilde{\bm{\lambda}}\in\mathbb{R}^{L}$ be a sorting of eigenvalues without
repetition, i.e., $\tilde{\bm{\lambda}}_{i}=\text{i-th smallest eigenvalues}$.
Assume $m\geq d$. For eigenvectors ${\bm{V}}$, let
$\mathcal{I}_{\ell}\subset[d]$ be indices of $\ell$-th eigensubspaces. Recall
that BasisNet is of the following form:

$\mathrm{BasisNet}({\bm{V}},\bm{\lambda})=\rho^{(B)}\left(\phi^{(B)}_{1}({\bm{V}}_{\mathcal{I}}{\bm{V}}^{\top}_{\mathcal{I}_{1}}),...,\phi^{(B)}_{L}({\bm{V}}_{\mathcal{I}_{L}}{\bm{V}}^{\top}_{\mathcal{I}_{L}})\right),$
(87)

where $L$ is number of eigensubspaces.

For SPE, let us construct the following $\phi_{\ell}$:

$\displaystyle[\phi_{\ell}({\bm{x}})]_{i}=\left\\{\begin{aligned}
&1,\quad\text{if }x_{i}=\tilde{\lambda}_{\ell},\\\
&1-\frac{x_{i}-\tilde{\lambda}_{\ell}}{\tilde{\lambda}_{\ell-1}-\tilde{\lambda}_{\ell}},\quad\text{if
}x_{i}\in(\tilde{\lambda}_{l},\tilde{\lambda}_{l+1}),\\\
&\frac{x_{i}-\tilde{\lambda}_{\ell-1}}{x_{i}-\tilde{\lambda}_{l}},\quad\text{if
}x_{i}\in(\tilde{\lambda}_{\ell-1},\tilde{\lambda}_{\ell}),\\\
&0,\quad\text{otherwise}.\end{aligned}\right.$ (88)

Note that this is both Lipschitz continuous with Lipschitz constant
$1/\min_{\ell}(\tilde{\lambda}_{\ell+1}-\tilde{\lambda}_{\ell})$, and
permutation equivariant (since it is elementwise). Now we have
${\bm{V}}\text{diag}\\{\phi_{\ell}(\bm{\lambda})\\}{\bm{V}}^{\top}={\bm{V}}_{\mathcal{I}_{\ell}}{\bm{V}}^{\top}_{\mathcal{I}_{\ell}}$,
since $\phi_{\ell}(\bm{\lambda})$ is either $1$ (when
$\lambda_{i}=\tilde{\lambda}_{\ell}$) or $0$ otherwise. For $\ell>L$, we let
$\phi_{\ell}=0$ by default. Then simply let $\rho$ be:

$\rho({\bm{A}}_{1},...,{\bm{A}}_{m})=\rho^{(S)}\left(\phi^{(S)}_{1}({\bm{A}}_{1}),...,\phi^{(S)}_{m}({\bm{A}}_{m})\right)=\rho^{(B)}\left(\phi^{(B)}_{1}({\bm{A}}_{1}),...,\phi^{(B)}_{L}({\bm{A}}_{L})\right).$
(89)

Here $\phi^{(S)}_{\ell}({\bm{A}}_{\ell})=\phi^{(B)}_{\ell}({\bm{A}}_{\ell})$
for ${\bm{A}}_{\ell}\neq 0$ and WLOG $\phi^{(S)}_{\ell}({\bm{A}}_{\ell})=0$ if
${\bm{A}}_{\ell}=0$. And $\rho^{(S)}$ is a function that first ignores $0$
matrices and mimic $\rho^{(B)}$. Therefore,

$\begin{split}\mathrm{SPE}({\bm{V}},\bm{\lambda})&=\rho({\bm{V}}\text{diag}\\{\phi_{1}(\bm{\lambda})\\}{\bm{V}}^{\top},...,{\bm{V}}\text{diag}\\{\phi_{m}(\bm{\lambda})\\}{\bm{V}}^{\top})\\\
&=\rho^{(S)}\left(\phi^{(S)}_{1}({\bm{V}}_{\mathcal{I}_{1}}{\bm{V}}^{\top}_{\mathcal{I}_{1}}),...,\phi^{(S)}_{m}({\bm{V}}_{\mathcal{I}_{m}}{\bm{V}}^{\top}_{\mathcal{I}_{m}})\right)\\\
&=\mathrm{BasisNet}({\bm{V}},\bm{\lambda}).\end{split}$ (90)

Since BasisNet universally approximates all continuous basis invariant
function, so can SPE. ∎

###  A.4 Proof of Proposition 3.4

See 3.4

###### Proof.

Note that from Lim et al. (2023), Theorem 3 we know that BasisNet can count 3,
4, 5 cycles. One way to let SPE count cycles is to approximate BasisNet first
and round the approximate error, thanks to the discrete nature of cycle
counting. The key observation is that the implementation of BasisNet to count
cycles is a special case of SPE:

$\displaystyle\\#\text{cycles of each
node}=\text{BasisNet}({\bm{V}},\bm{\lambda})=\rho({\bm{V}}\text{diag}\\{\hat{\phi}_{1}(\bm{\lambda})\\}{\bm{V}}^{\top},...,{\bm{V}}\text{diag}\\{\hat{\phi}_{m}(\bm{\lambda})\\}{\bm{V}}^{\top}),$
(91)

where $[\hat{\phi}_{\ell}(\bm{\lambda})]_{i}=\mathbbm{1}(\lambda_{i}\text{ is
the $\ell$-th smallest eigenvalue})$ and $\rho$ is continuous. Unfortunately,
these $\hat{\phi}_{\ell}$ are not continuous so SPE cannot express them under
stability requirement. Instead, we can construct a continuous function
$\phi_{\ell}$ to approximate discontinuous $\hat{\phi}_{\ell}$ with arbitrary
precision $\varepsilon$, say,

$\displaystyle\forall\bm{\lambda}\in[0,2]^{d},\quad\left\lVert\hat{\phi}(\bm{\lambda})-\phi(\bm{\lambda})\right\rVert<\varepsilon.$
(92)

Then we can upper-bound

$\displaystyle\left\lVert{\bm{V}}\text{diag}\\{\hat{\phi}_{\ell}(\bm{\lambda})\\}{\bm{V}}^{\top}-{\bm{V}}\text{diag}\\{\phi_{\ell}(\bm{\lambda})\\}{\bm{V}}^{\top}\right\rVert_{\mathsf{F}}\stackrel{{\scriptstyle\mathclap{(a)}}}{{\leq}}\left\lVert{\bm{V}}\right\rVert\left\lVert{\bm{V}}^{\top}\right\rVert\left\lVert\hat{\phi}_{\ell}(\bm{\lambda})-\phi_{\ell}(\bm{\lambda})\right\rVert<\epsilon,$
(93)

where (a) holds due to the Lemma A.1. Moreover, using the continuity of $\rho$
(defined in Assumption 3.1), we obtain

$\displaystyle\left\lVert\text{BasisNet}({\bm{V}},\bm{\lambda})-\text{SPE}({\bm{V}},\bm{\lambda})\right\rVert_{\mathsf{F}}\leq
J\sum_{\ell=1}^{m}\left\lVert{\bm{V}}\hat{\phi}(\bm{\lambda}){\bm{V}}^{\top}-{\bm{V}}\phi_{\ell}(\bm{\lambda}){\bm{V}}^{\top}\right\rVert_{\mathsf{F}}<Jd\varepsilon.$
(94)

Now, let $\varepsilon=Jd/2$, then we can upper-bound the maximal error of
node-level counting:

$\displaystyle\max_{i\in[n]}\left|\\#\text{cycles of node
$i$}-\mathrm{SPE}({\bm{V}},\bm{\lambda})\right|^{2}$
$\displaystyle\leq\left\lVert\text{BasisNet}({\bm{V}},\bm{\lambda})-\text{SPE}({\bm{V}},\bm{\lambda})\right\rVert_{\mathsf{F}}^{2}<J^{2}d^{2}\varepsilon^{2}=1/4.$
(95) $\displaystyle\implies$ $\displaystyle\max_{i\in[n]}\left|\\#\text{cycles
of node $i$}-\mathrm{SPE}({\bm{V}},\bm{\lambda})\right|<1/2.$ (96)

Then, by applying an MLP that universally approximates rounding function, we
are done with the proof. ∎

###  A.5 Proof of Proposition 3.3

See 3.3

###### Proof.

Our proof does not require the use of the channel dimension—i.e., we take $m$
and $p$ to equal $1$. The argument is split into two steps.

First we show that for the given $\bm{\lambda},\bm{\lambda}^{\prime}$ and any
$\bm{\phi},\bm{\phi}^{\prime}\in\mathbb{R}^{d}$ there is a choice of two layer
network
$\phi(\bm{\lambda})={\bm{W}}_{2}\sigma({\bm{W}}_{1}\bm{\lambda}+{\bm{b}}_{1})+{\bm{b}}_{2}$
such that $\phi(\bm{\lambda})=\bm{\phi}$ and
$\phi(\bm{\lambda}^{\prime})=\bm{\phi}^{\prime}$. Our choices of
${\bm{W}}_{1},{\bm{W}}_{2}$ will have dimensions $d\times d$,
${\bm{b}}_{1},{\bm{b}}_{2}\in\mathbb{R}^{d}$, and $\sigma$ denotes the ReLU
activation function.

Second we choose $\bm{\phi},\bm{\phi}^{\prime}\in\mathbb{R}^{d}$ such that
${\bm{V}}\bm{\phi}{\bm{V}}^{\top}$ has strictly positive entries, whilst
${\bm{V}}^{\prime}\bm{\phi}^{\prime}{\bm{V}}^{\prime\top}=\mathbb{0}$ (the
matrix of all zeros). The argument will conclude by choosing
$a_{1},a_{2},b_{1},b_{2}\in\mathbb{R}$ such that the 2 layer network (on the
real line) $\rho(x)=a_{2}\cdot\sigma(a_{1}x+b_{1})+b_{2}$ (a 2 layer MLP on
the real line, applied element-wise to matrices then summed over both $n$
dimensions) produces distinct embeddings for $({\bm{V}},\bm{\lambda})$ and
$({\bm{V}}^{\prime},\bm{\lambda^{\prime}})$.

We begin with step one.

Step 1: If $\bm{\phi}=\bm{\phi}^{\prime}$ then we may simply take $W_{1}$ and
${\bm{b}}_{1}$ to be the zero matrix and vector respectively. Then
$\sigma({\bm{W}}_{1}\bm{\lambda}+{\bm{b}}_{1})=\sigma({\bm{W}}_{1}\bm{\lambda}^{\prime}+{\bm{b}}_{1})=\mathbb{0}$.
Then we may take $W_{2}=I$ (identity) and ${\bm{b}}_{2}=\bm{\phi}$, which
guarantees that $\phi(\bm{\lambda})=\bm{\phi}$ and
$\phi(\bm{\lambda}^{\prime})=\bm{\phi}^{\prime}$.

So from now on assume that $\bm{\phi}\neq\bm{\phi}^{\prime}$. Let
$\bm{\lambda}$ and $\bm{\lambda}^{\prime}$ differ in their $i$th entries
$\lambda_{i},\lambda^{\prime}_{i}$, and assume without loss of generality that
$\lambda_{i}<\lambda^{\prime}_{i}$. Let
$W_{1}=[\mathbb{0},\ldots,\mathbb{0},\mathbb{e}_{i},\mathbb{0},\ldots,\mathbb{0}]$
the matrix of all zeros, except the $i$th column which is the $i$th standard
basis vector. Then $W_{1}\bm{\lambda}$ is the vector of all zeros, except for
$i$ entry equaling $\lambda_{i}$ (similarly for $\bm{\lambda}^{\prime}$). Next
take ${\bm{b}}_{1}$ to be the vector of all zeros, except for $i$th entry
$-(\lambda_{i}+\lambda^{\prime}_{i})/2$, the midpoint between the differing
eigenvalues. These choices make
$\mathbb{z}=\sigma({\bm{W}}_{1}\bm{\lambda}+{\bm{b}}_{1})=\mathbb{0}$, and
$\mathbb{z}^{\prime}=\sigma({\bm{W}}_{1}\bm{\lambda}^{\prime}+{\bm{b}}_{1})$
such that $z^{\prime}_{j}=0$ for $j\neq i$, and
$z^{\prime}_{i}=(\lambda^{\prime}_{i}-\lambda_{i})/2$. Next, taking
$W_{2}=[\mathbb{0},\ldots,\mathbb{0},\mathbb{c}_{i},\mathbb{0},\ldots,\mathbb{0}]$
where the $i$th column is
$\mathbb{c}_{i}=2(\bm{\phi}^{\prime}-\bm{\phi})/(\lambda^{\prime}_{i}-\lambda_{i})$
ensures that

$\displaystyle W_{2}\bm{z}=\bm{0},$ (97) $\displaystyle
W_{2}\bm{z}^{\prime}=\bm{\phi}^{\prime}-\bm{\phi}.$ (98)

Then we may simply take ${\bm{b}}_{2}=\bm{\phi}$, producing the desired
outputs:

$\displaystyle\phi(\bm{\lambda})={\bm{W}}_{2}\sigma({\bm{W}}_{1}\bm{\lambda}+{\bm{b}}_{1})+{\bm{b}}_{2}=\bm{\phi},$
(99)
$\displaystyle\phi(\bm{\lambda}^{\prime})={\bm{W}}_{2}\sigma({\bm{W}}_{1}\bm{\lambda}^{\prime}+{\bm{b}}_{1})+{\bm{b}}_{2}=\bm{\phi}^{\prime}$
(100)

as claimed.

Step 2: Expanding the matrix multiplications into their sums we have:

$\displaystyle[{\bm{V}}\text{diag}(\bm{\phi}){\bm{V}}^{\top}]_{ij}=\sum_{d}\phi_{d}v_{id}v_{jd}$
(101)
$\displaystyle[{\bm{V}}^{\prime}\text{diag}(\bm{\phi}^{\prime}){\bm{V}}^{\prime\top}]_{ij}=\sum_{d}\phi^{\prime}_{d}v^{\prime}_{id}v^{\prime}_{jd}.$
(102)

Our first choice is to take $\bm{\phi}^{\prime}=\mathbb{0}$, ensuring that
${\bm{V}}^{\prime}\text{diag}(\bm{\phi}^{\prime}){\bm{V}}^{\prime\top}=\mathbb{0}$
(an $n\times n$ matrix of all zeros). Next, we aim to pick $\bm{\phi}$ such
that [ ${\bm{V}}\text{diag}(\bm{\phi}){\bm{V}}^{\top}]_{i^{*}j^{*}}>0$ for
some indices $i^{*},j^{*}$. In fact, this is possible for an $i,j$ pair since
each pair of eigenvectors is orthogonal, and non-zero, so for each $i,j$ there
must be a $d^{*}$ such that $v_{id^{*}}v_{jd^{*}}>0$, and we can simply take
$\phi_{d}=1$ if $d=d^{*}$ and $\phi_{d}=0$ for $d\neq d^{*}$.

Thanks to the above choices, taking $a_{1}=1$ and $b_{1}=0$ ensures that

$\displaystyle\sigma\big{(}a_{1}\cdot{\bm{V}}^{\prime}\text{diag}(\bm{\phi}^{\prime}){\bm{V}}^{\prime\top}+b_{1}\big{)}=\mathbb{0}.$
(103)

but that,

$\displaystyle\big{[}\sigma\big{(}a_{1}\cdot{\bm{V}}\text{diag}(\bm{\phi}){\bm{V}}^{\top}+b_{1}\big{)}\big{]}_{ij}>0$
(104)

for some $i,j$. Note that in both cases, the scalar operations are applied to
matrices element-wise.

Finally, taking
$a_{2}=1/\sum_{ij}[\sigma\big{(}a_{1}\cdot{\bm{V}}\text{diag}(\bm{\phi}){\bm{V}}^{\top}+b_{1}\big{)}\big{]}_{ij}>0$
and $b_{2}=0$ produces embeddings

$\displaystyle\text{SPE}({\bm{V}},\bm{\lambda})=1\neq
0=\text{SPE}({\bm{V}}^{\prime},\bm{\lambda}^{\prime}).$ (105)

∎

###  A.6 Auxiliary results

######  Proposition A.1 (Davis-Kahan theorem (Yu et al., 2015, Theorem 2)).

Let ${\bm{A}},{\bm{A}}^{\prime}\in\mathrm{S}(n)$. Let
$\lambda_{1}\leq\cdots\leq\lambda_{n}$ be the eigenvalues of ${\bm{A}}$,
sorted in increasing order. Let the columns of
${\bm{x}},{\bm{x}}^{\prime}\in\mathrm{O}(n)$ contain the orthonormal
eigenvectors of ${\bm{A}}$ and ${\bm{A}}^{\prime}$, respectively, sorted in
increasing order of their corresponding eigenvalues. Let
$\mathcal{J}=\left\llbracket s,t\right\rrbracket$ be a contiguous interval of
indices in $[n]$, and let $d=\left|\mathcal{J}\right|$ be the size of the
interval. For notational convenience, let $\lambda_{0}=-\infty$ and
$\lambda_{n+1}=\infty$. Then there exists an orthogonal matrix
${\bm{Q}}\in\mathrm{O}(d)$ such that

$\displaystyle\left\lVert\left[{\bm{x}}\right]_{\mathcal{J}}-\left[{\bm{x}}^{\prime}\right]_{\mathcal{J}}{\bm{Q}}\right\rVert_{\mathsf{F}}\leq\frac{\sqrt{8}\min\left\\{\sqrt{d}\left\lVert{\bm{L}}-{\bm{L}}^{\prime}\right\rVert,\left\lVert{\bm{L}}-{\bm{L}}^{\prime}\right\rVert_{\mathsf{F}}\right\\}}{\min\left\\{\lambda_{s}-\lambda_{s-1},\lambda_{t+1}-\lambda_{t}\right\\}}\,.$
(106)

######  Proposition A.2 (Weyl’s inequality).

Let $\lambda_{i}:\mathrm{S}(n)\rightarrow\mathbb{R}$ return the $i$th smallest
eigenvalue of the given matrix. For all
${\bm{A}},{\bm{A}}^{\prime}\in\mathrm{S}(n)$ and all $i\in[n]$,
$\left|\lambda_{i}({\bm{A}})-\lambda_{i}({\bm{A}}^{\prime})\right|\leq\left\lVert{\bm{A}}-{\bm{A}}^{\prime}\right\rVert$.

###### Proof.

By Horn & Johnson (2012, Corollary 4.3.15),

$\displaystyle\lambda_{i}({\bm{A}}^{\prime})+\lambda_{1}({\bm{A}}-{\bm{A}}^{\prime})\leq\lambda_{i}({\bm{A}})\leq\lambda_{i}({\bm{A}}^{\prime})+\lambda_{n}({\bm{A}}-{\bm{A}}^{\prime})\,.$
(107)

Therefore
$\lambda_{i}({\bm{A}})-\lambda_{i}({\bm{A}}^{\prime})\in\left[\lambda_{1}({\bm{A}}-{\bm{A}}^{\prime}),\lambda_{n}({\bm{A}}-{\bm{A}}^{\prime})\right]$,
and

$\displaystyle\left|\lambda_{i}({\bm{A}})-\lambda_{i}({\bm{A}}^{\prime})\right|$
$\displaystyle=\max\left\\{\lambda_{i}({\bm{A}})-\lambda_{i}({\bm{A}}^{\prime}),\lambda_{i}({\bm{A}}^{\prime})-\lambda_{i}({\bm{A}})\right\\}$
(108)
$\displaystyle\leq\max\left\\{\lambda_{n}({\bm{A}}-{\bm{A}}^{\prime}),-\lambda_{1}({\bm{A}}-{\bm{A}}^{\prime})\right\\}$
(109)
$\displaystyle=\max_{i\in[n]}\left|\lambda_{i}({\bm{A}}-{\bm{A}}^{\prime})\right|$
(110) $\displaystyle=\sigma_{\max}({\bm{A}}-{\bm{A}}^{\prime})$ (111)
$\displaystyle=\left\lVert{\bm{A}}-{\bm{A}}^{\prime}\right\rVert\,.$ (112)

∎

######  Proposition A.3 (Hoffman-Wielandt corollary (Stewart & Sun, 1990,
Corollary IV.4.13)).

Let $\lambda_{i}:\mathrm{S}(n)\rightarrow\mathbb{R}$ return the $i$th smallest
eigenvalue of the given matrix. For all
${\bm{A}},{\bm{A}}^{\prime}\in\mathrm{S}(n)$,

$\displaystyle\sqrt{\sum_{i=1}^{n}\left(\lambda_{i}({\bm{A}})-\lambda_{i}({\bm{A}}^{\prime})\right)^{2}}\leq\left\lVert{\bm{A}}-{\bm{A}}^{\prime}\right\rVert_{\mathsf{F}}\,.$
(113)

######  Lemma A.1.

Let $\left\\{{\bm{A}}_{k}\right\\}_{k=1}^{p}$ be compatible matrices. For any
$\ell\in[p]$,

$\displaystyle\left\lVert\prod_{k=1}^{p}{\bm{A}}_{k}\right\rVert_{\mathsf{F}}\leq\left(\prod_{k=1}^{\ell-1}\left\lVert{\bm{A}}_{k}\right\rVert\right)\left\lVert{\bm{A}}_{\ell}\right\rVert_{\mathsf{F}}\left(\prod_{k=\ell+1}^{p}\left\lVert{\bm{A}}_{k}^{\top}\right\rVert\right)\,.$
(114)

###### Proof.

First, observe that for any matrices ${\bm{A}}\in\mathbb{R}^{m\times r}$ and
${\bm{B}}\in\mathbb{R}^{r\times n}$,

$\displaystyle\begin{split}\left\lVert{\bm{A}}{\bm{B}}\right\rVert_{\mathsf{F}}=\sqrt{\sum_{j=1}^{n}\left\lVert\left[{\bm{A}}{\bm{B}}\right]_{j}\right\rVert^{2}}=\sqrt{\sum_{j=1}^{n}\left\lVert{\bm{A}}{\bm{B}}\mathbf{e}_{j}\right\rVert^{2}}\leq\sqrt{\sum_{j=1}^{n}\left\lVert{\bm{A}}\right\rVert^{2}\left\lVert{\bm{B}}\mathbf{e}_{j}\right\rVert^{2}}&=\left\lVert{\bm{A}}\right\rVert\sqrt{\sum_{j=1}^{n}\left\lVert\left[{\bm{B}}\right]_{j}\right\rVert^{2}}\\\
&=\left\lVert{\bm{A}}\right\rVert\left\lVert{\bm{B}}\right\rVert_{\mathsf{F}}\,.\end{split}$
(115)

Therefore,

$\displaystyle\left\lVert\prod_{k=1}^{p}{\bm{A}}_{k}\right\rVert_{\mathsf{F}}$
$\displaystyle\stackrel{{\scriptstyle\mathclap{(a)}}}{{\leq}}\left(\prod_{k=1}^{\ell-1}\left\lVert{\bm{A}}_{k}\right\rVert\right)\left\lVert\prod_{k=\ell}^{p}{\bm{A}}_{k}\right\rVert_{\mathsf{F}}$
(116)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(b)}}}{{=}}\left(\prod_{k=1}^{\ell-1}\left\lVert{\bm{A}}_{k}\right\rVert\right)\left\lVert\prod_{k=0}^{p-\ell}{\bm{A}}_{p-k}^{\top}\right\rVert_{\mathsf{F}}$
(117)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(c)}}}{{\leq}}\left(\prod_{k=1}^{\ell-1}\left\lVert{\bm{A}}_{k}\right\rVert\right)\left(\prod_{k=0}^{p-\ell-1}\left\lVert{\bm{A}}_{p-k}^{\top}\right\rVert\right)\left\lVert{\bm{A}}_{\ell}^{\top}\right\rVert_{\mathsf{F}}$
(118)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(d)}}}{{=}}\left(\prod_{k=1}^{\ell-1}\left\lVert{\bm{A}}_{k}\right\rVert\right)\left\lVert{\bm{A}}_{\ell}\right\rVert_{\mathsf{F}}\left(\prod_{k=\ell+1}^{p}\left\lVert{\bm{A}}_{k}^{\top}\right\rVert\right)\,,$
(119)

where (a) and (c) hold by applying eq. 115 recursively, and (b) and (d) hold
because Frobenius norm is invariant to matrix transpose. ∎

######  Lemma A.2 (Permutation equivariance of eigenvectors).

Let ${\bm{A}}\in\mathbb{R}^{n\times n}$ and ${\bm{P}}\in\mathrm{P}(n)$. Then
for any ${\bm{x}}\in\mathbb{R}^{n}$, ${\bm{P}}{\bm{x}}$ is an eigenvector of
${\bm{P}}{\bm{A}}{\bm{P}}^{\top}$ iff ${\bm{x}}$ is an eigenvector of
${\bm{A}}$.

###### Proof.

${\bm{P}}{\bm{x}}$ is an eigenvector of ${\bm{P}}{\bm{A}}{\bm{P}}^{\top}$
$\displaystyle\stackrel{{\scriptstyle\mathclap{(a)}}}{{\iff}}\exists\lambda\in\mathbb{R},\,{\bm{P}}{\bm{A}}{\bm{P}}^{\top}{\bm{P}}{\bm{x}}=\lambda{\bm{P}}{\bm{x}}$
(120)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(b)}}}{{\iff}}\exists\lambda\in\mathbb{R},\,{\bm{P}}{\bm{A}}{\bm{x}}=\lambda{\bm{P}}{\bm{x}}$
(121)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(c)}}}{{\iff}}\exists\lambda\in\mathbb{R},\,{\bm{P}}{\bm{A}}{\bm{x}}={\bm{P}}\lambda{\bm{x}}$
(122)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(d)}}}{{\iff}}\exists\lambda\in\mathbb{R},\,{\bm{A}}{\bm{x}}=\lambda{\bm{x}}$
(123)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(e)}}}{{\iff}}\text{${\bm{x}}$
is an eigenvector of ${\bm{A}}$}\,,$ (124)

where (a) is the definition of eigenvector, (b) holds because permutation
matrices are orthogonal, (c) holds by linearity of matrix-vector
multiplication, (d) holds because permutation matrices are invertible, and (e)
is the definition of eigenvector. ∎

######  Lemma A.3 (Permutation invariance of eigenvalues).

Let ${\bm{A}}\in\mathbb{R}^{n\times n}$ and ${\bm{P}}\in\mathrm{P}(n)$. Then
$\lambda\in\mathbb{R}$ is an eigenvalue of ${\bm{P}}{\bm{A}}{\bm{P}}^{\top}$
iff $\lambda$ is an eigenvalue of ${\bm{A}}$.

###### Proof.

$\lambda$ is an eigenvalue of ${\bm{P}}{\bm{A}}{\bm{P}}^{\top}$
$\displaystyle\stackrel{{\scriptstyle\mathclap{(a)}}}{{\iff}}\exists\mathbf{y}\neq\mathbf{0},\,{\bm{P}}{\bm{A}}{\bm{P}}^{\top}\mathbf{y}=\lambda\mathbf{y}$
(125)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(b)}}}{{\iff}}\exists\mathbf{y}\neq\mathbf{0},\,{\bm{P}}{\bm{A}}{\bm{P}}^{\top}\mathbf{y}=\lambda{\bm{P}}{\bm{P}}^{\top}\mathbf{y}$
(126)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(c)}}}{{\iff}}\exists\mathbf{y}\neq\mathbf{0},\,{\bm{P}}{\bm{A}}{\bm{P}}^{\top}\mathbf{y}={\bm{P}}\lambda{\bm{P}}^{\top}\mathbf{y}$
(127)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(d)}}}{{\iff}}\exists{\bm{x}}\neq\mathbf{0},\,{\bm{P}}{\bm{A}}{\bm{x}}={\bm{P}}\lambda{\bm{x}}$
(128)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(e)}}}{{\iff}}\exists{\bm{x}}\neq\mathbf{0},\,{\bm{A}}{\bm{x}}=\lambda{\bm{x}}$
(129)
$\displaystyle\stackrel{{\scriptstyle\mathclap{(f)}}}{{\iff}}\text{$\lambda$
is an eigenvalue of ${\bm{A}}$}\,,$ (130)

where (a) is the definition of eigenvalue, (b) holds because permutation
matrices are orthogonal, (c) holds by linearity of matrix-vector
multiplication, (d)-(e) hold because permutation matrices are invertible, and
(f) is the definition of eigenvalue. ∎

##  Appendix B Experimental details and Additional Results

###  B.1 Implementation of SPE

SPE includes parameterized permutation equivariant functions
$\rho:\mathbb{R}^{n\times n\times m}\to\mathbb{R}^{n\times p}$ and
$\phi_{\ell}:\mathbb{R}^{d}\to\mathbb{R}^{d}$.

For $\phi_{\ell}$, we treat input $\bm{\lambda}$ as $d$ vectors with input
dimension 1 and use either elementwise-MLPs, i.e.,
$[\phi_{\ell}(\bm{\lambda})]_{i}=\mathrm{MLP}(\lambda_{i})$, or Deepsets to
process them. We also use piecewise cubic splines, which is a $\mathbb{R}$ to
$\mathbb{R}$ piecewise function with cubic polynomials on each piece. Given
number of pieces as a hyperparameter, the piece interval is determined by
uniform chunking $[0,2]$, the range of eigenvalues. The learnable parameters
are the coefficients of cubic functions for each piece. To construct
$\phi_{\ell}$, we simply let one piecewise cubic spline elementwisely act on
each individual eigenvalues:

$[\phi_{\ell}(\bm{\lambda})]_{i}=\mathrm{spline}(\lambda_{i}).$ (131)

For $\rho$, in principle any permutation equivariant tensor neural networks
can be applied. But in our experiments we adapt GIN as $\rho$. Here is how:
for input ${\bm{A}}\in\mathbb{R}^{n\times n\times m}$, we first partition
${\bm{A}}$ along the second axis into $n$ many matrices
${\bm{A}}_{i}\in\mathbb{R}^{n\times m}$ (in code we do not actually need to
partition them since parallel matrix multiplication does the work). Then we
treat ${\bm{A}}_{i}$ as node features of the original graph and independently
and identically apply a GIN to this graph with node features ${\bm{A}}_{i}$.
This will produce node representations ${\bm{Z}}_{i}\in\mathbb{R}^{n\times p}$
from ${\bm{A}}_{i}$. Finally we let ${\bm{Z}}=\sum_{i=1}^{n}{\bm{Z}}_{i}$ be
the final output of $\rho$. Note that this whole process makes $\rho$
permutation equivariant.

###  B.2 Implementation of baselines

For PEG, we follow the formula of their paper and augment edge features by

$e_{i,j}\leftarrow
e_{i,j}\cdot\mathrm{MLP}(\left\lVert{\bm{V}}_{i,:}-{\bm{V}}_{j,:}\right\rVert).$
(132)

For SignNet/BasisNet, we refer to their public code release at
https://github.com/cptq/SignNet-BasisNet. Note that the original BasisNet does
not support inductive learning, i.e., it cannot even apply to new graph
structures. This is because it has separate weights for eigensubspaces with
different dimension. Here we simply initialize an unlearned weights for
eigensubspaces with unseen dimensions.

###  B.3 Other training details

We use Adam optimizer with an initial learning rate 0.001 and 500 warm-up
steps. We adopt a linear decay learning rate scheduler. Batch size is 128 for
ZINC, Alchemy and substructures counting, 256 for ZINC-full and 64 for
DrugOOD.

###  B.4 Ablation study

One key component of SPE is to leverage eigenvalues using
$\phi_{\ell}(\bm{\lambda})$. Here We try removing the use of eigenvalues,
i.e., set $\phi_{\ell}(\bm{\lambda})=1$ to see the difference. Mathematically,
this will result in
$\mathrm{SPE}({\bm{V}},\bm{\lambda})=\rho([{\bm{V}}{\bm{V}}^{\top}]_{\ell=1}^{m})$.
This is pretty similar to PEG and we loss expressive power from this over-
stable operation ${\bm{V}}{\bm{V}}^{\top}$. As shown in the table below,
removing eigenvalue information leads to a dramatic drop of performance on
ZINC-subset. Therefore, the processing of eigenvalues is an effective and
necessary design in our method.

Method | Test MAE
---|---
SPE ($\phi_{\ell}=$MLPs) | $0.0693_{\pm 0.0040}$
SPE ($\phi_{\ell}=0$) | $0.1230_{\pm 0.0323}$
Table 3: Abalation study for SPE on ZINC (subset).