Towards Stable, Globally Expressive Graph Representations with Laplacian Eigenvectors

## Abstract

Abstract Graph neural networks (GNNs) have achieved remarkable success in a variety of machine learning tasks over graph data. Existing GNNs usually rely on message passing, i.e., computing node representations by gathering information from the neighborhood, to build their underlying computational graphs. Such an approach has been shown fairly limited in expressive power, and often fails to capture global characteristics of graphs. To overcome the issue, a popular solution is to use Laplacian eigenvectors as additional node features, as they are known to contain global positional information of nodes, and can serve as extra node identifiers aiding GNNs to separate structurally similar nodes. Since eigenvectors naturally come with symmetries—namely, O ⁢ ( p ) 𝑂 𝑝 O(p) italic_O ( italic_p ) -group symmetry for every p 𝑝 p italic_p eigenvectors with equal eigenvalue, properly handling such symmetries is crucial for the stability and generalizability of Laplacian eigenvector augmented GNNs. However, using a naive O ⁢ ( p ) 𝑂 𝑝 O(p) italic_O ( italic_p ) -group invariant encoder for each p 𝑝 p italic_p -dimensional eigenspace may not keep the full expressivity in the Laplacian eigenvectors. Moreover, computing such invariants inevitably entails a hard split of Laplacian eigenvalues according to their numerical identity, which suffers from great instability when the graph structure has small perturbations.
In this paper, we propose a novel method exploiting Laplacian eigenvectors to generate stable and globally expressive graph representations. The main difference from previous works is that (i) our method utilizes learnable O ⁢ ( p ) 𝑂 𝑝 O(p) italic_O ( italic_p ) -invariant representations for each Laplacian eigenspace of dimension p 𝑝 p italic_p , which are built upon powerful orthogonal group equivariant neural network layers already well studied in the literature, and that (ii) our method deals with numerically close eigenvalues in a smooth fashion, ensuring its better robustness against perturbations. Experiments on various graph learning benchmarks witness the competitive performance of our method, especially its great potential to learn global properties of graphs.

## 1 Introduction

Numerous real-world data—such as molecules, electric circuits or social networks—can be represented by graphs. Machine learning over graphs is thus an important approach to find underlying relations among them, and make predictions concerning novel data. So far, graph neural networks (GNNs) have proved successful on a plethora of learning tasks over graphs (Wu et al., ; Zhou et al., ), spanning across domains such as chemistry (Deshpande et al., ; Jin et al., ; Reiser et al., ), biology (Stokes et al., ; Zitnik & Leskovec, ; Zitnik et al., ), social recommendations (Ying et al., ) or electronic design automation (Lopera et al., ).

One of the most popularly adopted GNN architecture is message passing neural network (MPNN), which maintains a representation vector $h_{u}$ for each node $u$, and iteratively updates it by gathering information from the neighboring nodes of $u$. Despite its relative simplicity and efficiency, it has several weaknesses that severely limit its performance. One important problem is its limited expressive power, referring to the fact that MPNNs often fail to distinguish between two non-isomorphic graphs, or two structurally different nodes with similar neighborhood configuration (Xu et al., ; Zhang et al., ). Another issue is its inability to capture global properties of graphs, meaning that it cannot truthfully learn long-range interactions within a graph, due to “oversquashing” that occurs as a result of multiple message passing steps (Alon & Yahav, ; Dwivedi et al., ). In this paper, we refer to the former problem as a lack of local expressive power, while the latter as one concerning global expressive power.

A great number of works have attempted to tackle the aforementioned weaknesses of MPNNs, which we will review in Section 5 and Appendix C. For now, we restrict our discussion to one specific approach—using Laplacian eigenvectors as node feature augmentations. Why are we particularly interested in it? The reason is that Laplacian eigenvectors may alleviate both issues we raise above. First, Laplacian eigenvectors provably contain rich local structural information (Cvetković et al., ; Fürer, ; Rattan & Seppelt, ), and can thus serve as additional node labels, making it easier for a GNN to separate nodes that are otherwise similar. Furthermore, they can reflect the absolute position of each node within the graph (Von Luxburg, ), making GNNs aware of potential long-range interactions. Indeed, a vast literature has regarded Laplacian eigenvectors as so-called *graph positional encodings*, which play important roles both in MPNNs and graph transformers (Dwivedi et al., ; ; Rampášek et al., ; Ying et al., ).

Although Laplacian eigenvectors provide a promising solution for expressive graph representation learning, there are some well-known constraints that one must take into account for their reliable use. The first is orthogonal-group invariance. As is first pointed out by Wang et al. (); Lim et al. (), given a Laplacian $L$, its eigen-decomposition is in general not unique. In fact, assuming that $v_{1},\ldots,v_{p}$ are $p$ mutually orthogonal normalized eigenvectors of a Laplacian $L$ that correspond to the same eigenvalue $\lambda$, then so are $v^{\prime}_{1},\ldots,v^{\prime}_{p}$, as long as the two groups of eigenvectors can be associated via a $p\times p$ orthogonal matrix $Q$, namely $V^{\prime}=V\cdot Q$ where $V=(v_{1},\ldots,v_{p})$ and $V^{\prime}=(v^{\prime}_{1},\ldots,v^{\prime}_{p})$. One must ensure that the network output is invariant to such orthogonal transformations, so as to produce identical representations for identical (i.e., isomorphic) graphs. Another related but stricter constraint is stability, which, as formally defined by Huang et al. (), demands that network outputs should be close when the input graph undergoes small perturbations. It is easy to see that orthogonal-group invariance is a special case of stability in which the strength of perturbation approaches zero.

To ensure orthogonal-group invariance (and furthermore, stability), Lim et al. () and Huang et al. () both propose to use inner products—namely, $VV^{T}$ with $V=(v_{1},\ldots,v_{p})$ being the matrix consisting of $p$ mutually orthogonal normalized eigenvectors within an eigenspace of dimension $p$—instead of eigenvectors $(v_{1},\ldots,v_{p})$ themselves, as node feature augmentations. Despite being provably invariant to $O(p)$ transformations and even stable (with carefully designed network architectures), taking inner products can potentially lose much of the rich structural and positional information carried by vanilla Laplacian eigenvectors. Earlier than the above two works, Wang et al. () has proposed a special message passing operation in which only the norms of differences between rows of $V$ are used, and proved its stability. However, this method even dismisses important eigenvalue information by treating Laplacian eigenvectors from different eigenspaces uniformly. Given the limitations of existing methods to utilize Laplacian eigenvectors, a natural question is whether we can recover the information inherent in vanilla Laplacian eigenvectors while ensuring stability. To make the question even more general, we may ask:

> *What is the representational limit of graph learning methods exploiting Laplacian eigenvectors, given the stability constraint?*

In this paper, we attempt to partially answer the general question posed above. Our main contributions are summarized below.

- •
We propose vanilla orthogonal group equivariant augmentation (Vanilla OGE-Aug), a novel method exploiting Laplacian eigenvectors to produce node feature augmentations. Inspired by the property of orthogonal group invariance of invariant point cloud networks (for example, Tensor Field Network (Thomas et al., ) and its variant (Finkelshtein et al., )) as well as their great expressive power, we use them to process the Laplacian eigenvectors, resulting in node feature augmentations much more expressive than previous methods that make use of simple hand-crafted invariant functions only.
- •
We theoretically prove that Vanilla OGE-Aug, combined with an MPNN, can lead to universal representations of graphs, as long as the invariant point cloud networks we use are powerful enough. Previous works have theoretically guaranteed the expressive power of several specific invariant point cloud networks, which lays the foundations for the practicality of our theoretical result.
- •
Although Vanilla OGE-Aug can be maximally expressive, it unfortunately lacks stability. We then propose a smooth variant of Vanilla OGE-Aug, namely OGE-Aug, by trading expressive power for better stability. Our approach is to use a series of “soft” masks to filter Laplacian eigenvectors that belong to different eigenspaces, instead of hard-splitting and separately processing them. We theoretically prove the stability of OGE-Aug, and evaluate its empirical performance on various real-world graph datasets. The results indicate that our method not only shows competitive performance on popular graph benchmarks, but is surprisingly good at learning global properties of graphs.

## 2 Preliminaries

We use $\mathcal{G}$ to denote the set of all simple, undirected graphs. For a graph $G\in\mathcal{G}$, its node set and edge set are denoted by $V(G)$ and $E(G)$ respectively. Graphs considered in this paper are usually accompanied with node features, defined as a function from $V(G)$ to $\mathbb{R}^{d}$.

For a graph with $n$ nodes labeled by $1,\ldots,n$ respectively, its adjacency matrix is defined as $A\in\{0,1\}^{n\times n}$ in which $A_{ij}=1$ if and only if nodes $i$ and $j$ are connected; further, if the graph has node features, the node features are represented by a matrix $X\in\mathbb{R}^{n\times d}$ whose $i$-th row corresponds to the feature of node $i$.

Given the adjacency matrix $A\in\{0,1\}^{n\times n}$ of graph $G$, we define the Laplacian of graph $G$ as $L=D-A$, in which $D=\mathrm{diag}(d(1),\ldots,d(n))$, with $d(i)$ being the degree of node $i$ ($i=1,\ldots,n$). It is not hard to see that with $G$ being simple and undirected, its Laplacian $L$ is real symmetric, and further positive semi-definite. Therefore, all eigenvalues of $L$ are real non-negative. One may also verify that 0 is always an eigenvalue of $L$ (thus being the smallest eigenvalue of $L$). If $L$ has an eigenvalue $\lambda$ with multiplicity $\mu$, the linear subspace spanned by the $\mu$ mutually orthogonal eigenvectors of $L$ corresponding to $\lambda$ is called an eigenspace of $L$ with dimension $\mu$.

Let $A\in\mathbb{R}^{n\times n}$. $A$ is said to be orthogonal if $AA^{T}=A^{T}A=I$, with $I$ being the identity matrix. Given a positive integer $n$, we use $O(n)$ to denote the set of all orthogonal matrices of shape $n\times n$. A 0-1 matrix $A\in\{0,1\}^{n\times n}$ is said to be a permutation matrix if each of its rows and columns has exactly one $1$-element. Let $S_{n}$ be the set of all permutation matrices of shape $n\times n$. It’s easy to see that $S_{n}\subseteq O(n)$.

## 3 Universal graph representation with Laplacian eigenvectors

Despite the great number of works showing the efficacy of using Laplacian eigenvectors in graph learning tasks, few (Fürer, ; Rattan & Seppelt, ) have studied theoretically their expressiveness upper-bound—namely, to what extent can the information of a graph be learned, merely from its Laplacian eigenvectors? This is a weaker version of the general question we pose in Section 1, with the stability constraint removed. In this section, we will show that the answer to this weaker question is rather optimistic: ignoring the stability constraint, Laplacian eigenvectors can actually lead to universal representations of graphs. To reach the point, we start by reconsidering the problem of finding universal graph representations from the perspective of Laplacian eigenvalues and eigenvectors (Proposition 3.2), and then give a concrete construction of such universal representation (Proposition 3.5).

We first present the definition for universal representations of graphs.

###### Definition 3.1 (Universal representation) .

Let $f$ be a function mapping each pair $(G,X_{G})$ to a real value $f(G,X_{G})\in\mathbb{R}$, where $G\in\mathcal{G}$ is a graph and $X_{G}\in\mathbb{R}^{|V(G)|\times d}$ stands for node features accompanied with $G$. Further let $A_{G}$ be the adjacency matrix of graph $G$. The function $f$ is said to be a universal representation if the following condition holds: for any two pairs $(G,X_{G})$ and $(H,X_{H})$, $f(G,X_{G})=f(H,X_{H})$ if and only if $\exists P\in S_{|V(G)|}$,

$$ $\displaystyle A_{G}=PA_{H}P^{T},\quad X_{G}=PX_{H}.$ (1) $$

In other words, $f$ should produce equal outputs only for graphs that are identical up to a permutation of nodes.

Next, we will associate the concept of universal representations with eigendecompositions of graph Laplacians. We denote $L_{G}$ the Laplacian of a simple, undirected graph $G$. Due to the properties of graph Laplacians (stated in Section 2), we may assume that $L_{G}$ has $K$ distinct real eigenvalues $\lambda_{1},\ldots,\lambda_{K}$, with $0=\lambda_{1}<\lambda_{2}<\cdots<\lambda_{K}$. We further use $\mu_{j}$ to denote the multiplicity of eigenvalue $\lambda_{j}$, and $V_{j}\in\mathbb{R}^{|V(G)|\times\mu_{j}}$ the set of mutually orthogonal normalized eigenvectors corresponding to $\lambda_{j}$ (each column of $V_{j}$ being an eigenvector that has $L^{2}$-norm scaled to 1), for $j=1,\ldots,K$. Following Fürer (), we also denote

$$ $\displaystyle\mathrm{Spec}\ G=((\lambda_{1},\mu_{1}),(\lambda_{2},\mu_{2}), \ldots,(\lambda_{K},\mu_{K}))$ (2) $$

the *spectrum* of $G$.

Given the above notations, the following proposition is straightforward.

###### Proposition 3.2 .

Let $G,H\in\mathcal{G}$ with $|V(G)|=|V(H)|$. Let $A_{G}$ and $A_{H}$ be their adjacency matrices respectively. The following two statements are equivalent:
(i) $\exists P\in S_{|V(G)|},A_{G}=PA_{H}P^{T}$.
(ii) Both of the following conditions hold.

- •
$\mathrm{Spec}\ G=\mathrm{Spec}\ H$.
- •
Let the spectrum of $G$ (and thus $H$) be $((\lambda_{1},\mu_{1}),\ldots,(\lambda_{K},\mu_{K}))$, and $V_{j},V^{\prime}_{j}\in\mathbb{R}^{|V(G)|\times\mu_{j}}$ be sets of mutually orthogonal normalized eigenvectors belonging to $G,H$ respectively, both corresponding to eigenvalue $\lambda_{j}$, for $j=1,\ldots,K$. There exists $P\in S_{|V(G)|}$ and $Q_{j}\in O(\mu_{j})$ ($j=1,\ldots,K$), such that
$\displaystyle V_{j}=PV^{\prime}_{j}Q_{j}.$
(3)

We include the proof in Appendix A. Proposition 3.2 implies that in order to find universal representations of a graph, it may be helpful to find a sufficiently expressive representation for each of its Laplacian eigenspace. Nevertheless, such representation must stay invariant under actions of $O(p)$-group elements for an eigenspace of dimension $p$, due to the existence of arbitrary $Q_{j}$ matrices ($j=1,\ldots,K$). Thus, we are motivated to define as following an $O(p)$-invariant universal representation.

###### Definition 3.3 ( $O(p)$ -invariant universal representation) .

Let $f:\bigcup_{n=0}^{\infty}\mathbb{R}^{n\times p}\rightarrow\bigcup_{n=0}^{\infty
}\mathbb{R}^{n}$. Given an input $V\in\mathbb{R}^{n\times p}$, $f$ outputs a vector $f(V)\in\mathbb{R}^{n}$. The function $f$ is said to be an $\bm{O(p)}$-invariant universal representation if given $V,V^{\prime}\in\mathbb{R}^{n\times p}$ and $P\in S_{n}$, the following two conditions are equivalent: (i) $f(V)=Pf(V^{\prime})$; (ii) $\exists Q\in O(p)$, such that $V=PV^{\prime}Q$.

By Definition 3.3, an $O(p)$-invariant universal representation is one that assigns an output to each point of a point set embedded in $\mathbb{R}^{p}$, in a way that is invariant to global $O(p)$ rotations, equivariant to point permutations, and injective with respect to all possible point set configurations. Such networks have been named *universal point cloud networks*, whose design has been intensively studied, as we will survey in Section 5.

We still need another definition which follows Zaheer et al. ().

###### Definition 3.4 (Universal set representation) .

Let $\mathcal{X}$ be a non-empty set. A function $f:2^{\mathcal{X}}\rightarrow\mathbb{R}$ is said to be a universal set representation if $\forall X_{1},X_{2}\in 2^{\mathcal{X}}$, $f(X_{1})=f(X_{2})$ if and only if the two sets $X_{1}$ and $X_{2}$ are equal.

We remark that the problem of finding a universal set representation, at least for finite subsets of a countable universe $\mathcal{X}$, has been fully addressed by Zaheer et al. (), using the deep set architecture they propose.

With Definitions 3.3 and 3.4, we are now ready to present our main result on constructing universally expressive graph representations. For simplicity, we further introduce the following shorthands:

- •
Given a set of $n\times p$ matrices $\{V_{1},\ldots,V_{k}\}\subset\mathbb{R}^{n\times p}$, with the $i$-th ($i=1,\ldots,n$) row of $V_{j}$ denoted by $\bm{v}_{ji}$ ($j=1,\ldots,k$), and a universal set representation $g:2^{\mathbb{R}^{p}}\rightarrow\mathbb{R}$, let $g(\{V_{1},\ldots,V_{k}\})\in\mathbb{R}^{n}$ be the representation vector whose $i$-th component equals $g(\{\bm{v}_{1i},\ldots,\bm{v}_{ki}\})$, for $i=1,\ldots,n$.
- •
Given $V_{1}\in\mathbb{R}^{n\times p_{1}},\ldots,V_{k}\in\mathbb{R}^{n\times p_{k}}$, let $\mathrm{concat}[V_{1},\ldots,V_{k}]\in\mathbb{R}^{n\times(p_{1}+\cdots+p_{k})}$ be the concatenation of $V_{1},\ldots,V_{k}$ along the row dimension.

###### Proposition 3.5 .

For each $p=1,2,\ldots$, let $f_{p}$ be an $O(p)$-invariant universal representation function. Further let $g:2^{\mathbb{R}^{3}}\rightarrow\mathbb{R}$ be a universal set representation. Then the following function

$$ $\displaystyle r(G,X_{G})=\mathrm{GNN}\left(A_{G},\mathrm{concat}\left[X_{G},g \left(\left\{\mathrm{concat}\left[\mu_{j}\mathbf{1}_{n},\lambda_{j}\mathbf{1}_ {n},f_{\mu_{j}}(V_{j})\right]\right\}_{j=1}^{K}\right)\right]\right)$ (4) $$

is a universal representation (by Definition 3.1). Here $n=|V(G)|$, $((\lambda_{1},\mu_{1}),\ldots,(\lambda_{K},\mu_{K}))$ is the spectrum of $G$, and $V_{j}\in\mathbb{R}^{n\times\mu_{j}}$ are the $\mu_{j}$ mutually orthogonal normalized eigenvectors of $L_{G}$ corresponding to $\lambda_{j}$. We denote $\mathbf{1}_{n}$ an all-1 vector of shape $n\times 1$. $\mathrm{GNN}$ is a maximally expressive MPNN such as the one proposed in (Xu et al., ).

The proof is also given in Appendix A. By Proposition 3.5, the problem of finding a universal representation of graphs is completely reduced to that of finding $O(p)$-invariant universal representations of point sets (as constructions for other components are already known). Therefore, directly applying existing point cloud networks (such as those we will mention in Section 5) to graph Laplacian eigenspaces following equation (4) immediately results in a fairly large design space of GNNs, and universality of the resulting GNN directly follows from universality of the underlying point cloud network.

One may find that equation (4) takes the form of a node feature augmented MPNN. The observation is made explicit with the following definition.

###### Definition 3.6 (Vanilla OGE-Aug) .

Let $f_{p}$ be an $O(p)$-invariant universal representation, for each $p=1,2,\ldots$, and $g:2^{\mathbb{R}^{3}}\rightarrow\mathbb{R}$ be a universal set representation. Define $Z:\mathcal{G}\rightarrow\bigcup_{n=1}^{\infty}\mathbb{R}^{n}$ as

$$ $\displaystyle Z(G)=g\left(\left\{\mathrm{concat}\left[\mu_{j}\mathbf{1}_{|V(G) |},\lambda_{j}\mathbf{1}_{|V(G)|},f_{\mu_{j}}(V_{j})\right]\right\}_{j=1}^{K} \right),$ (5) $$

in which the notations follow Proposition 3.5. For $G\in\mathcal{G}$, $Z(G)$ is called a vanilla orthogonal group equivariant augmentation, or Vanilla OGE-Aug on $G$.

We end this section by discussing the complexity of computing $Z(G)$. The typical complexity of a universal point cloud network is $n\exp(\tilde{O}(\mathrm{dim}))$(^1^11$\tilde{O}(f(n))$ means a complexity linear in $f(n)$ if ignoring poly-logarithm factors, i.e., $O(\log^{k}f(n))$.), where $\mathrm{dim}$ is the coordinate dimension. Thus, the complexity of computing equation (5) is $n\exp(\tilde{O}(\max_{j}\mu_{j}))$. Our worst-case complexity (in which $\max_{j}\mu_{j}\sim n$) matches that of a typical algorithm for graph isomorphism problem (GI). Nevertheless, real-world graphs usually have $\max_{j}\mu_{j}\ll n$, making our method computationally affordable in general.

###### Definition 3.1 (Universal representation) .

###### Proposition 3.2 .

###### Definition 3.3 ( O ⁢ ( p ) 𝑂 𝑝 O(p) italic_O ( italic_p ) -invariant universal representation) .

###### Definition 3.4 (Universal set representation) .

###### Proposition 3.5 .

###### Definition 3.6 (Vanilla OGE-Aug) .

## 4 Incorporating the stability constraint

Proposition 3.5 has theoretically confirmed the possibility of finding universal graph representations with Laplacian eigenvectors, even when the backbone GNN is a (relatively weak) MPNN. Nevertheless, naively applying the network architecture proposed in Proposition 3.5 (or Vanilla OGE-Aug) may not necessarily bring performance gain, due to one important weakness—instability. As is mentioned in Section 1, instability refers to the proneness to produce very different outputs as the input undergoes small perturbations. Instability of Vanilla OGE-Aug stems from the fact that it treats Laplacian eigenspaces of different dimensions separately. As an example, let $\lambda$ be a $K$-fold eigenvalue of Laplacian $L$, whose $K$ corresponding eigenvectors should be encoded by an $O(K)$-invariant universal representation $f_{K}$; after a small perturbation on $L$, the $K$-dimensional eigenspace corresponding to $\lambda$ might split into two smaller eigenspaces of dimensions $k_{1}$ and $k_{2}$ respectively (i.e., the degeneracy of $\lambda$ is partially lifted), which should be alternatively encoded by $f_{k_{1}}$ and $f_{k_{2}}$. Since the functions $f_{K}$ and $f_{k_{1}}$ (or $f_{k_{2}}$) can be very different with $K\neq k_{1},K\neq k_{2}$, the output can vary a lot even if the changes in $L$ (or changes in the $K$ eigenvalues and eigenvectors) are small.(^2^22We remark that a similar problem pertains to BasisNet (Lim et al., ). See the discussion in Appendix C of Huang et al. ().) An important lesson from the above discussion is that a “hard split” of Laplacian eigenvectors into separate eigenspaces can be susceptible to perturbations. Hence, model predictions should not absolutely rely on such a “hard split” (especially, not relying on the dimension of each eigenspace) for the sake of stability.

According to equation (5), in Vanilla OGE-Aug there are two occurrences of explicit dependencies on eigenspace dimensions $\mu_{j}$ ($j=1,\ldots,K$), namely (i) $\mu_{j}$ being concatenated as a number, and (ii) a different $f_{\mu_{j}}$ being used for each value of $\mu_{j}$. To maintain stability, such dependencies should either be removed, or be replaced by functions not sensitive to the exact eigenspace splitting. Our attempt towards this goal is as follows.

###### Definition 4.1 (OGE-Aug) .

Let $G$ be a graph with $n$ nodes. Let $f$ be an $O(n)$-invariant universal representation function. Define

$$ $\displaystyle V_{j}^{\text{smooth}}=\mathrm{concat}\left[V_{1}\rho(|\lambda_{1 }-\lambda_{j}|),V_{2}\rho(|\lambda_{2}-\lambda_{j}|),\ldots,V_{K}\rho(|\lambda _{K}-\lambda_{j}|)\right],$ (6) $$

where $\rho:\mathbb{R}_{\geqslant 0}\rightarrow[0,1]$ is a continuous *smoothing function* with $\rho(0)=1$ and $\lim_{x\rightarrow+\infty}\rho(x)=0$, and other notations follow Proposition 3.5. Further let $\phi:\mathbb{R}^{2}\rightarrow\mathbb{R}^{m}$ and $\psi:\mathbb{R}^{m}\rightarrow\mathbb{R}$ be parameterized functions that apply row-wise on $n\times 2$ and $n\times m$ matrices, respectively. Then

$$ $\displaystyle Z(G)=\psi\left(\sum_{j=1}^{K}\mu_{j}\phi\left(\mathrm{concat} \left[\lambda_{j}\mathbf{1}_{n},f(V_{j}^{\text{smooth}})\right]\right)\right)$ (7) $$

is called an orthogonal group equivariant augmentation, or OGE-Aug on $G$.

There are some remarkable points regarding OGE-Aug. First, instead of using a different orthogonal group invariant encoder for different eigenspace dimensions, a single $O(n)$-invariant encoder $f$ is used to encode eigenvectors coming from all eigenspaces. The dependency on eigenspace dimensions $\mu_{j}$ ($j=1,\ldots,K$) appears only in the form of a weighted sum, which is insensitive to the exact splitting of Laplacian eigenspaces. Moreover, a continuous smoothing function $\rho$ is used to keep the eigenvectors aware of the eigenspace where they belong, as well as the eigenspaces nearby. As $\rho$ becomes more and more centered at 0 (namely, $\rho(0)=1$ and $\rho(x)\rightarrow 0$ for all $x>0$), each eigenspace gets encoded by its own portion of parameters from $f$ that are not shared with each other; contrarily, with $\rho$ being flatter, more parameters are shared across eigenspaces. In other words, the shape of $\rho$ controls the “degree of smoothness” of OGE-Aug.

Next, we quantitatively characterize the stability of OGE-Aug. To this end, we first present our definition of stability, following (Huang et al., ).

###### Definition 4.2 (Stability, following Definition 3.1 of (Huang et al., 2024 ) ) .

A function $f$, operating on the Laplacian $L$ of a graph $G$ and producing a node feature augmentation $Z\in\mathbb{R}^{|V(G)|\times d}$, is said to be stable, if there exist constants $c,C>0$, such that for any two Laplacians $L,L^{\prime}$,

$$ $\displaystyle\|f(L)-P_{*}f(L^{\prime})\|_{\text{F}}\leqslant C\cdot\|L-P_{*}L^ {\prime}P_{*}^{T}\|_{\text{F}}^{c},$ (8) $$

in which $\|\cdot\|_{\text{F}}$ stands for Frobenius norm, and $P_{*}=\arg\min_{P\in S_{n}}\|L-PL^{\prime}P^{T}\|_{\text{F}}$ is the permutation matrix matching $L$ and $L^{\prime}$ (assuming both $L$ and $L^{\prime}$ are of size $n\times n$).

We are now ready to give our theoretical result on the stability of OGE-Aug. We assume that the following conditions hold for functions $\psi,\phi,f$ and $\rho$.

- 1.
$\psi,\phi$ and $\rho$ are Lipschitz continuous, with Lipschitz constants $J_{\psi},J_{\phi}$ and $J_{\rho}$ respectively. Namely,
$\displaystyle\|\psi(X)-\psi(X^{\prime})\|_{\text{F}}\leqslant J_{\psi}\|X-X^{
\prime}\|_{\text{F}},\quad\forall X,X^{\prime}\in\mathbb{R}^{n\times m},$
(9)
$\displaystyle\|\phi(X)-\phi(X^{\prime})\|_{\text{F}}\leqslant J_{\phi}\|X-X^{
\prime}\|_{\text{F}},\quad\forall X,X^{\prime}\in\mathbb{R}^{n\times 2},$
(10)
$\displaystyle|\rho(x)-\rho(x^{\prime})|\leqslant J_{\rho}|x-x^{\prime}|,\quad
\forall x,x^{\prime}\in\mathbb{R}_{\geqslant 0}.$
(11)
- 2.
$f$ satisfies the following condition: $\exists J_{f}>0$,
$\displaystyle\|f(X)-f(X^{\prime})\|\leqslant J_{f}\min_{Q\in O(n)}\|X-X^{
\prime}Q\|_{\text{F}},\quad\forall X,X^{\prime}\in\mathbb{R}^{n\times n}.$
(12)
One may think of $f$ as $J_{f}$-Lipschitz continuous after rotating its arguments along the same direction.
- 3.
There exists a constant $\delta>0$, such that $\rho(x)=0$ for all $x>\delta$.

Given the above assumptions, we have

###### Proposition 4.3 (Stability of OGE-Aug) .

With the assumptions on $\psi,\phi,f$ and $\rho$ specified above, OGE-Aug defined by (7) is stable. To be specific, given two graphs $G,G^{\prime}\in\mathcal{G}$ with Laplacians $L$ and $L^{\prime}$ respectively, there exists a proper value of $\delta$ such that

$$ $\displaystyle\|Z(G)-P_{*}Z(G^{\prime})\|_{\text{F}}$ $\displaystyle\leqslant nJ_{\psi}J_{\phi}\big{[}(\sqrt{n}+2nJ_{\rho}J_{f})\|L-P _{*}L^{\prime}P_{*}^{T}\|_{2}$ $\displaystyle\qquad\qquad+4\sqrt[4]{2}J_{f}\sqrt{J_{\rho}}n\|L-P_{*}L^{\prime} P_{*}^{T}\|_{\text{F}}^{1/2}\big{]},$ (13) $$

where $\|\cdot\|_{2}$ is the spectral norm which is no larger than the Frobenius norm $\|\cdot\|_{\text{F}}$, and $n=|V(G)|=|V(G^{\prime})|$.

We give the proof in Appendix B. To ensure that the inequality (13) holds, in principle we need to tune $\delta$ for different $G$ and $G^{\prime}$. However, in our experiments we simply take $\delta$ as a hyperparameter designated before actual training.

Finally, we discuss practical implementations of OGE-Aug. While presenting the universality result (Proposition 3.5), we have assumed that $f_{p}$ ($p=1,2,\ldots$) can universally represent all $O(p)$-invariant and permutation-equivariant functions on point sets embedded in $\mathbb{R}^{p}$. This universality requirement is inherited to OGE-Aug (Definition 4.1). Namely, we still require that $f$ is an $O(n)$-invariant universal representation. We now point out that such universality requirement, despite producing maximally expressive networks in theory, can be impractical to implement. First, with $f$ being universal, the resulting network architecture has a typical complexity of $n\exp(\tilde{O}(n))$ which is generally unacceptable. Moreover, insisting on the universality of $f$ can be harmful to the stability of OGE-Aug, since a more expressive $f$ might result in a larger Lipschitz constant $J_{f}$. Therefore, in our actual implementation of OGE-Aug, we no longer require $f$ to be universal. Instead, we adopt as $f$ a Cartesian tensor based point cloud network (Finkelshtein et al., ) with Cartesian tensors up to the second order used. We include more experimental details, as well as a complexity analysis for our implementation, in Appendix D.

###### Definition 4.1 (OGE-Aug) .

###### Definition 4.2 (Stability, following Definition 3.1 of (Huang et al., 2024 ) ) .

###### Proposition 4.3 (Stability of OGE-Aug) .

## 5 Related works

#### Graph representation learning with Laplacian eigenvectors.

It is well-known that eigenvectors of graph Laplacian corresponding to the smallest eigenvalues contain “positional” information of nodes. A number of works have thus adopted Laplacian eigenvectors as a technique for node feature augmentation. As we have mentioned in Section 1, there are two important issues regarding the application of Laplacian eigenvectors in graph representation learning, namely orthogonal group invariance (or sign-and-basis invariance) and stability. Some early works (Dwivedi & Bresson, ; Kreuzer et al., ) have noticed the sign invariance problem and tried to alleviate it by randomly flipping the signs of Laplacian eigenvectors, while completely ignored the basis invariance problem. Lim et al. () is the first work to formally state and systematically address the sign-and-basis invariance issue. Nevertheless, it fails to meet the stronger requirement of stability. So far, only two works (Wang et al., ; Huang et al., ) have seriously discussed the stability issue by giving mathematical definitions for it, and proposing learning methods that are provably stable.

#### Orthogonal-group invariant networks.

A neural network is said to be orthogonal-group invariant if it takes as input one or more vector(s) (say, for instance, each of dimension $p$), and outputs an $O(p)$-invariant scalar, i.e., a value that remains invariant as the input vector system undergoes an $O(p)$ transformation. As is pointed out by, e.g., Bronstein et al. (), orthogonal-group invariance is a desirable property for learning tasks on molecular data or point clouds, in which Euclidean coordinates play important roles.

Orthogonal-group equivariance is a property closely related to invariance. A network is $O(p)$-equivariant if it takes as input one (or a set of) arbitrary representation(s)(^3^33In our context, a representation of $O(p)$ means a vector lying in a linear space $\mathcal{L}$, given that a group homomorphism from $O(p)$ to the general linear group $\mathrm{GL}(\mathcal{L})$ on $\mathcal{L}$ exists.) of $O(p)$ (with $p$-dimensional vectors being a special case), and outputs another (or another set of) representation(s) of $O(p)$, in a way that whenever the input system undergoes the action of an $O(p)$ group element, the output also undergoes an action corresponding to the same element. In practice, invariant networks are usually constructed by stacking multiple equivariant layers, along with a final invariant layer. Regarding the intermediate orthogonal group representations they use, existing works on the design of invariant networks mainly take one of the four approaches: (i) utilizing scalar or vector representations (Deng et al., ; Li et al., ; Satorras et al., ; Villar et al., ); (ii) utilizing hand-crafted higher-order representations (Gasteiger et al., ; ; Schütt et al., ); (iii) utilizing higher-order Cartesian tensor representations (Finkelshtein et al., ; Ruhe et al., ); (iv) utilizing higher-order irreducible representations (Batzner et al., ; Bogatskiy et al., ; Cohen et al., ; Fuchs et al., ; Thomas et al., ).

Similar to the question of expressive power of GNNs, there exists the question of whether an orthogonal-group invariant network can express all possible geometric configurations (either of a single vector or of a point cloud) up to an arbitrary orthogonal transformation. Invariant networks possessing the above property are usually called *universal*. There have been a few works establishing theoretically the universality of some of the aforementioned architectures. Villar et al. () shows that universality can be achieved merely using scalar and vector representations, as long as interaction terms including sufficiently many vectors are allowed, and that the network output is restricted to be scalars or vectors. Li et al. () further shows by construction that an invariant network can be already universal with 4-vector interaction terms, even if all intermediate representations are restricted scalar. Regarding methods using higher-order representations, Dym & Maron () proves the universality of two specific architectures exploiting higher-order irreducible representations of SO(3)—Tensor Field Networks (TFN) (Thomas et al., ) and SE(3)-Transformers (Fuchs et al., ). Based on TFN, Finkelshtein et al. () proposes another universal architecture utilizing Cartesian tensor representations. The universality results reviewed above have laid theoretical foundations for our proposed method.

We leave the discussion on more related works to Appendix C.

## 6 Experiments

In this section, we conduct extensive experiments to evaluate the performance of our methods. We adopt several popular real-world datasets, including: (1) QM9 (Ramakrishnan et al., ); (2) ZINC12k (Dwivedi et al., ); (3) Alchemy (Chen et al., ); (4) PCQM-Contact (Dwivedi et al., ). Information regarding those datasets is introduced below, and the dataset statistics are summarized in Table 5. We provide detailed experimental settings, as well as more experimental results in Appendix D. Remarkably, our method achieves state-of-the-art or highly competitive performance in all those datasets with significant advantages.

#### QM9.

QM9 (Ramakrishnan et al., ) is a graph property regression dataset containing 130k small molecules and 19 regression targets. We use a commonly adopted 0.8/0.1/0.1 training/validation/test split ratio, and report the results of the first 12 targets.
Several representative expressive GNNs are selected as baselines, including MPNN, 1-2-3-GNN (Morris et al., ), DTNN (Wu et al., ), DeepLRP (Chen et al., ), PPGN (Maron et al., ), NGNN (Zhang & Li, ), KP-GIN+ (Feng et al., ), and IDMPNN (Zhou et al., ). The results are shown in Table 1. Remarkably, OGE-Aug achieves state-of-the-art performance on 7 out of 12 targets, and also shows competitive performance on other 5 targets, which is a significant breakthrough. We also notice that our method achieves a relatively low MAE on targets $U_{0}$, $U$, $H$ and $G$, compared with subtree- or subgraph-based methods such as MPNN, NGNN or KP-GIN+. This fact indicates that our method has the ability to capture global properties of graphs, since those targets are macroscopic thermodynamic properties of molecules and heavily depend on long-range interactions (for example, intermolecular forces like hydrogen bonds).

**Table 1: QM9 results (MAE $\downarrow$). Highlighted are first, second best results.**
| Target | MPNN | 1-2-3-GNN | DTNN | DeepLRP | PPGN | NGNN | KP-GIN+ | 4-IDMPNN | OGE-Aug |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $\mu$ | 0.358 | 0.476 | 0.244 | 0.364 | 0.231 | 0.433 | 0.358 | 0.398 | 0.0822 |
| $\alpha$ | 0.89 | 0.27 | 0.95 | 0.298 | 0.382 | 0.265 | 0.233 | 0.226 | 0.159 |
| $\epsilon_{\textrm{HOMO}}$ | 0.00541 | 0.00337 | 0.00388 | 0.00254 | 0.00276 | 0.00279 | 0.00240 | 0.00263 | 0.00140 |
| $\epsilon_{\textrm{LUMO}}$ | 0.00623 | 0.00351 | 0.00512 | 0.00277 | 0.00287 | 0.00276 | 0.00236 | 0.00286 | 0.00144 |
| $\Delta\epsilon$ | 0.0066 | 0.0048 | 0.0112 | 0.00353 | 0.00406 | 0.00390 | 0.00333 | 0.00398 | 0.00198 |
| $\langle R^{2}\rangle$ | 28.5 | 22.9 | 17.0 | 19.3 | 16.7 | 20.1 | 16.49 | 10.4 | 5.55 |
| ZPVE | 0.00216 | 0.00019 | 0.00172 | 0.00055 | 0.00064 | 0.00015 | 0.00017 | 0.00013 | 0.000149 |
| $U_{0}$ | 2.05 | 0.0427 | 2.43 | 0.413 | 0.234 | 0.205 | 0.0682 | 0.0189 | 0.0526 |
| $U$ | 2.00 | 0.111 | 2.43 | 0.413 | 0.234 | 0.200 | 0.0553 | 0.0152 | 0.0356 |
| $H$ | 2.02 | 0.0419 | 2.43 | 0.413 | 0.229 | 0.249 | 0.0575 | 0.0160 | 0.0439 |
| $G$ | 2.02 | 0.0469 | 2.43 | 0.413 | 0.238 | 0.253 | 0.0484 | 0.0159 | 0.0441 |
| $c_{\textrm{v}}$ | 0.42 | 0.0944 | 0.27 | 0.129 | 0.184 | 0.0811 | 0.0869 | 0.0890 | 0.0681 |

#### ZINC.

ZINC12k (Dwivedi et al., ) is a subset of the ZINC250k dataset containing 12k molecules, and the task is molecular property (constrained solubility) regression evaluated by mean absolute error (MAE). We follow the official split of the dataset. We include common baselines such as GIN (Xu et al., ), PNA (Corso et al., ), DeepLRP (Chen et al., ), OSAN (Qian et al., ), KP-GIN+ (Feng et al., ), GNN-AK+ (Zhao et al., ) and CIN (Bodnar et al., ). We also include previous methods that make use of Laplacian eigenvectors to produce node feature

**Table 2: Zinc12K results (MAE $\downarrow$). Shown is the mean $\pm$ std of 5 runs.**
| Method | Test MAE |
| --- | --- |
| GIN | $0.163\pm 0.004$ |
| PNA | $0.188\pm 0.004$ |
| GSN | $0.115\pm 0.012$ |
| OSAN | $0.187\pm 0.004$ |
| KP-GIN+ | $0.119\pm 0.002$ |
| GNN-AK+ | $0.080\pm 0.001$ |
| CIN | $0.079\pm 0.006$ |
| GIN, with PEG | $0.144\pm 0.008$ |
| GIN, with SignNet | $0.085\pm 0.003$ |
| GIN, with BasisNet | $0.155\pm 0.007$ |
| GIN, with SPE | $0.069\pm 0.004$ |
| SAN | $0.139\pm 0.006$ |
| Graphormer | $0.122\pm 0.006$ |
| GPS | $0.070\pm 0.004$ |
| Specformer | $0.066\pm 0.003$ |
| GINE, with OGE-Aug (ours) | $0.066\pm 0.002$ |
| GPS, with OGE-Aug (ours) | 0.064 $\pm$ 0.003 |

**Table 3: Experiments on Alchemy. Shown is the mean $\pm$ std of 5 runs with different random seeds.**
| Model | PE | Test MAE $\downarrow$ |
| --- | --- | --- |
| GIN | None | $0.112\pm 0.001$ |
| GIN | PEG (8) | $0.114\pm 0.001$ |
| GIN | SignNet (All) | $0.113\pm 0.002$ |
| GIN | BasisNet (All) | $0.110\pm 0.001$ |
| GIN | SPE (All) | $0.108\pm 0.001$ |
| GINE | OGE-Aug (ours) | 0.087 $\pm$ 0.001 |

#### Alchemy.

Alchemy (Chen et al., ) is also a graph-level small molecular property regression dataset from the TUDatasets. We adopt message-passing GNN backbones, and consider alternative expressive PEs including PEG (Wang et al., ), SignNet (Lim et al., ), BasisNet (Lim et al., ) and SPE (Huang et al., ). As shown in Table 3, our OGE-Aug significantly outperforms all these baselines and achieves state-of-the-art performance.

#### PCQM-Contact.

As part of the long-range graph benchmarks (LRGB) (Dwivedi et al., ), PCQM-Contact is a dataset derived from the PCQM4Mv2 dataset along with the corresponding 3D molecular structures. The task is a binary link ranking measured by the Mean Reciprocal Rank (MRR), which requires the capability of capturing long range interactions. MPNN baselines include GCN (Kipf & Welling, ), GINE (Hu et al., ), and GatedGCN (Bresson & Laurent, ), while graph transformer baselines include Transformer, SAN and GPS combined with positional encodings (PEs) like LapPE (Kreuzer et al., ), RWSE (Dwivedi et al., ), EdgeRWSE (Zhou et al., ) and Hodge1Lap (Zhou et al., ). We combine GPS with our OGE-Aug and achieves the best performance across all baselines, which verifies the benefit of bringing in long-range information via OGE-Aug.

**Table 4: Experiments on PCQM-Contact dataset from the long-range graph benchmarks (LRGB). Highlighted are the first, second, third best results.**
| model | PE | PCQM-Contact (MRR $\uparrow$) |
| --- | --- | --- |
| GCN | None | $0.3234\pm 0.0006$ |
| GINE | None | $0.3180\pm 0.0027$ |
| GatedGCN | None | $0.3218\pm 0.0011$ |
| Transformer | LapPE | $0.3174\pm 0.0020$ |
| SAN | LapPE | $0.3350\pm 0.0003$ |
| SAN | RWSE | $0.3341\pm 0.0006$ |
| GPS | LapPE | $0.3337\pm 0.0006$ |
| GPS | EdgeRWSE | 0.3408 $\pm$ 0.0003 |
| GPS | Hodge1Lap | 0.3407 $\pm$ 0.0004 |
| GPS | OGE-Aug (ours) | 0.3543 $\pm$ 0.0004 |

## 7 Conclusion

In this paper, we propose to apply orthogonal group invariant neural networks on Laplacian eigenspaces of graphs, so as to produce node feature augmentations that may possess great expressive power. We present Vanilla OGE-Aug and OGE-Aug as two instances of our proposed framework, of which the former illustrates the potential of our method to achieve universal representation of graphs, while the latter is provably stable and practically useful. Extensive experiments have verified the outstanding performance of OGE-Aug on various benchmarks as well as its capability to learn global properties of graphs. We remark that our approach to incorporating stability into graph learning methods based on Laplacian eigenvectors, i.e., by ensuring *smoothness* while processing different Laplacian eigenspaces, is a general technique, and can be applied to other machine learning domains where eigenvalues and eigenvectors are of significant interest.

## Appendix A Proofs of propositions in Section 3

### A.1 Proof of Proposition 3.2

###### Proof.

We denote $n=|V(G)|$. Let $L_{G}$ and $L_{H}$ be the Laplacians of $G$ and $H$, respectively. We first show that statement (i) is equivalent to the following: $\exists P\in S_{n},L_{G}=PL_{H}P^{T}$. By definition of permutation matrices, for any $P\in S_{n}$ there exists a bijective function $p:\{1,\ldots,n\}\rightarrow\{1,\ldots,n\}$ such that $P_{ij}=1_{p(i)=j}$. Therefore, we have $L_{G}=PL_{H}P^{T}\Leftrightarrow L_{Gij}=L_{Hp(i)p(j)}$. Since the off-diagonal part of $L_{G}$ (or $L_{H}$) is $-A_{G}$ (or $-A_{H}$), $L_{Gij}=L_{Hp(i)p(j)}$ implies $A_{Gij}=A_{Hp(i)p(j)}$. Thus $A_{G}=PA_{H}P^{T}$ follows from $L_{G}=PL_{H}P^{T}$. To see the other direction, notice that given $A_{G}=PA_{H}P^{T}$ or $A_{Gij}=A_{Hp(i)p(j)}$, we have

$$ $\displaystyle(PD_{H}P^{T})_{ij}=D_{Hp(i)p(i)}1_{i=j}=\sum_{k=1}^{n}A_{Hp(i)p(k )}1_{i=j}=\sum_{k=1}^{n}A_{Gik}1_{i=j}=D_{Gij},$ (14) $$

or simply $D_{G}=PD_{H}P^{T}$. Thus $L_{G}=PL_{H}P^{T}$.

Next, we prove that statement (ii) is equivalent to $\exists P\in S_{n},L_{G}=PL_{H}P^{T}$. Assuming that statement (ii) is true, one may make use of the identities

$$ $\displaystyle L_{G}=\sum_{j=1}^{K}\lambda_{j}V_{j}V_{j}^{T},\quad L_{H}=\sum_{ j=1}^{K}\lambda_{j}V^{\prime}_{j}V^{\prime T}_{j},$ (15) $$

to observe that $L_{G}=PL_{H}P^{T}$. To see the other direction, notice that $L_{G}=PL_{H}P^{T}$ implies that $L_{G}$ and $L_{H}$ are similar, and thus $\mathrm{Spec}\ G=\mathrm{Spec}\ H$ as similar matrices share the set of eigenvalues combined with their corresponding multiplicities. Moreover, if the columns of $V^{\prime}_{j}$ constitute the set of mutually orthogonal normalized eigenvectors of $L_{H}$ corresponding to eigenvalue $\lambda_{j}$, then the columns of $PV^{\prime}_{j}$ contain mutually orthogonal normalized eigenvectors of $L_{G}$ corresponding to the same eigenvalue, for $j=1,\ldots,K$. Therefore, each column of $V_{j}$ must be a linear combination of columns of $PV^{\prime}_{j}$, namely

$$ $\displaystyle V_{j}=PV^{\prime}_{j}Q_{j},$ (16) $$

for some $Q_{j}\in\mathbb{R}^{\mu_{j}\times\mu_{j}}$. Further imposing the constraint that $V_{j}^{T}V_{j}=I_{\mu_{j}\times\mu_{j}}$ yields $Q_{j}^{T}Q_{j}=I_{\mu_{j}\times\mu_{j}}$, or $Q_{j}\in O(\mu_{j})$. Thus the proof is made.
∎

###### Proof.

### A.2 Proof of Proposition 3.5

###### Proof.

By Definition 3.1, we only need to prove that $r(G,X_{G})=r(H,X_{H})$ if and only if $\exists P\in S_{n}$ such that $A_{G}=PA_{H}P^{T}$ and $X_{G}=PX_{H}$, for any two graphs $G,H$ with accompanying node features $X_{G},X_{H}$. By Proposition 3.2, the latter condition is equivalent to the conjunction of the following:

- 1.
$\mathrm{Spec}\ G=\mathrm{Spec}\ H$.
- 2.
$\exists P\in S_{n}$ and $Q_{j}\in O(\mu_{j})$ ($j=1,\ldots,K$), such that $X_{G}=PX_{H}$, and $V_{j}=PV^{\prime}_{j}Q_{j}$, for $j=1,\ldots,K$.

Our notations follow those in Proposition 3.2. Now, given that the above two conditions are true, we immediately get $f_{\mu_{j}}(V_{j})=Pf_{\mu_{j}}(V^{\prime}_{j})$ due to the fact that $f_{\mu_{j}}$ is an $O(\mu_{j})$-invariant universal representation. Thus, we have

$$ $\displaystyle\mathrm{concat}\left[\mu_{j}\mathbf{1}_{n},\lambda_{j}\mathbf{1}_ {n},f_{\mu_{j}}(V_{j})\right]=P\ \mathrm{concat}\left[\mu_{j}\mathbf{1}_{n}, \lambda_{j}\mathbf{1}_{n},f_{\mu_{j}}(V^{\prime}_{j})\right].$ (17) $$

Similarly, since $g$ operates on individual rows of set elements, the permutation matrix $P$ passes through the operation of $g$. Therefore,

$$ $\displaystyle g\left(\left\{\mathrm{concat}\left[\mu_{j}\mathbf{1}_{n},\lambda _{j}\mathbf{1}_{n},f_{\mu_{j}}(V_{j})\right]\right\}_{j=1}^{K}\right)=Pg\left( \left\{\mathrm{concat}\left[\mu_{j}\mathbf{1}_{n},\lambda_{j}\mathbf{1}_{n},f_ {\mu_{j}}(V^{\prime}_{j})\right]\right\}_{j=1}^{K}\right).$ (18) $$

If we let

$$ $\displaystyle X^{\prime}_{G}=\mathrm{concat}\left[X_{G},g\left(\left\{\mathrm{ concat}\left[\mu_{j}\mathbf{1}_{n},\lambda_{j}\mathbf{1}_{n},f_{\mu_{j}}(V_{j} )\right]\right\}_{j=1}^{K}\right)\right],$ (19) $\displaystyle X^{\prime}_{H}=\mathrm{concat}\left[X_{H},g\left(\left\{\mathrm{ concat}\left[\mu_{j}\mathbf{1}_{n},\lambda_{j}\mathbf{1}_{n},f_{\mu_{j}}(V^{ \prime}_{j})\right]\right\}_{j=1}^{K}\right)\right],$ (20) $$

then $X^{\prime}_{G}=PX^{\prime}_{H}$. Since message passing GNNs are invariant with respect to node permutations, we know that

$$ $\displaystyle r(G,X_{G})=\mathrm{GNN}(A_{G},X^{\prime}_{G})=\mathrm{GNN}(PA_{H }P^{T},PX^{\prime}_{H})=\mathrm{GNN}(A_{H},X^{\prime}_{H})=r(H,X_{H}),$ (21) $$

thus proving one direction of the proposition.

For the other direction, notice that a maximally expressive message passing GNN is as powerful as the 1-WL test (Xu et al., ), and strictly stronger than a universal set encoder (regarding the set of node features).(^4^44Indeed, a message passing GNN with a maximally expressive pooling layer and no message passing layers is equivalent to a deep set, the latter having proved to be a universal set encoder by Zaheer et al. ().) Therefore, by construction (4), $r(G,X_{G})=r(H,X_{H})$ implies that $\exists P\in S_{n}$, $X^{\prime}_{G}=PX^{\prime}_{H}$, where $X^{\prime}_{G}$ is defined in equation (19) but $X^{\prime}_{H}$ should be alternatively defined as

$$ $\displaystyle X^{\prime}_{H}=\mathrm{concat}\left[X_{H},g\left(\left\{\mathrm{ concat}\left[\mu^{\prime}_{j}\mathbf{1}_{n},\lambda^{\prime}_{j}\mathbf{1}_{n} ,f_{\mu^{\prime}_{j}}(V^{\prime}_{j})\right]\right\}_{j=1}^{K^{\prime}}\right) \right],$ (22) $$

since we have not yet proved that $G$ and $H$ share spectra. The above fact further translates into $X_{G}=PX_{H}$ and

$$ $\displaystyle g\left(\left\{\mathrm{concat}\left[\mu_{j}\mathbf{1}_{n},\lambda _{j}\mathbf{1}_{n},f_{\mu_{j}}(V_{j})\right]\right\}_{j=1}^{K}\right)=Pg\left( \left\{\mathrm{concat}\left[\mu^{\prime}_{j}\mathbf{1}_{n},\lambda^{\prime}_{j }\mathbf{1}_{n},f_{\mu^{\prime}_{j}}(V^{\prime}_{j})\right]\right\}_{j=1}^{K^{ \prime}}\right).$ (23) $$

Since $g$ is a universal set representation, the sets on both sides are equal up to an element-wise application of $P$. As a consequence,

$$ $\displaystyle\{(\mu_{j},\lambda_{j})\}_{j=1}^{K}=\{(\mu^{\prime}_{j},\lambda^{ \prime}_{j})\}_{j=1}^{K^{\prime}},$ (24) $$

or $\mathrm{Spec}\ G=\mathrm{Spec}\ H$. Now that $G$ and $H$ share spectra, we may assume that the eigenvalues $\{\lambda_{j}\}_{j=1}^{K}$ are in an order such that $0=\lambda_{1}<\lambda_{2}<\cdots<\lambda_{K}$. We then arrive at equation (17), and subsequently $f_{\mu_{j}}(V_{j})=Pf_{\mu_{j}}(V^{\prime}_{j})$, for each $j=1,\ldots,K$. Due to $f_{\mu_{j}}$ being an $O(\mu_{j})$-invariant universal representation, we end up finding that $\exists Q_{j}\in O(\mu_{j})$ ($j=1,\ldots,K$), such that $V_{j}=PV^{\prime}_{j}Q_{j}$. So far we have proved the other direction of the proposition.
∎

###### Proof.

## Appendix B Proof of Proposition 4.3

Before proving Proposition 4.3, we present some useful lemmas. We quote these lemmas directly from (Huang et al., ).

###### Lemma B.1 (Davis-Kahan theorem, Proposition A.1 of (Huang et al., 2024 ) , see also (Yu et al., 2015 ) ) .

Let $A,A^{\prime}$ be $n\times n$ real symmetric matrices. Let $\lambda_{1}\leqslant\cdots\leqslant\lambda_{n}$ be eigenvalues of $A$ sorted in increasing order (possibly with repeats). Let the columns of $V,V^{\prime}\in O(n)$ contain mutually orthogonal normalized eigenvectors of $A,A^{\prime}$ respectively, sorted in increasing order of their corresponding eigenvalues. Let $\mathcal{J}=\{s,s+1,\ldots,t\}\subseteq\{1,\ldots,n\}$ be a contiguous interval of indices, and $[V]_{\mathcal{J}},[V^{\prime}]_{\mathcal{J}}$ be matrices of shape $n\times|\mathcal{J}|$ whose columns are the $s$-th, $(s+1)$-th, $\ldots$, $t$-th column of $V$ and $V^{\prime}$, respectively. Then

$$ $\displaystyle\min_{Q\in O(|\mathcal{J}|)}\|[V]_{\mathcal{J}}-[V^{\prime}]_{ \mathcal{J}}Q\|_{\text{F}}\leqslant\frac{\sqrt{8}\min\left\{\sqrt{|\mathcal{J} |}\|A-A^{\prime}\|_{2},\|A-A^{\prime}\|_{\text{F}}\right\}}{\min\{\lambda_{s}- \lambda_{s-1},\lambda_{t+1}-\lambda_{t}\}}.$ (25) $$

For convenience, we define $\lambda_{0}=-\infty$ and $\lambda_{n+1}=+\infty$.

###### Lemma B.2 (Weyl’s inequality, Proposition A.2 of (Huang et al., 2024 ) ) .

Given a real symmetric matrix $A$, let $\lambda_{i}(A)$ be its $i$-th smallest eigenvalue. For any two real symmetric matrices $A,A^{\prime}$ of shape $n\times n$, $|\lambda_{i}(A)-\lambda_{i}(A^{\prime})|\leqslant\|A-A^{\prime}\|_{2}$ holds for all $i=1,\ldots,n$.

###### Lemma B.3 (Lemma A.1 of (Huang et al., 2024 ) ) .

Assume $A_{1}A_{2}\cdots A_{p}$ is a valid matrix multiplication. Then

$$ $\displaystyle\left\|\prod_{k=1}^{p}A_{k}\right\|_{\text{F}}\leqslant\left( \prod_{k=1}^{\ell-1}\|A_{k}\|_{2}\right)\|A_{\ell}\|_{\text{F}}\left(\prod_{k= \ell+1}^{p}\|A_{k}^{T}\|_{2}\right).$ (26) $$

Now we can present the proof of Proposition 4.3.

###### Proof.

We will prove the uniform result that for any two graphs $G,G^{\prime}\in\mathcal{G}$ with Laplacians $L,L^{\prime}$ respectively, and for any $P\in S_{n}$, there exists a value of $\delta$ such that

$$ $\displaystyle\|Z(G)-PZ(G^{\prime})\|_{\text{F}}$ $\displaystyle\leqslant nJ_{\psi}J_{\phi}\big{[}(\sqrt{n}+2nJ_{\rho}J_{f})\|L- PL^{\prime}P^{T}\|_{2}$ $\displaystyle\qquad\qquad+4\sqrt[4]{2}J_{f}\sqrt{J_{\rho}}n\|L-PL^{\prime}P^{T }\|_{\text{F}}^{1/2}\big{]}.$ (27) $$

We may first rewrite equation (7) as

$$ $\displaystyle Z(G)=\psi\left(\sum_{i=1}^{n}\phi\left(\mathrm{concat}\left[ \tilde{\lambda}_{i}\mathbf{1}_{n},f(\tilde{V}_{i}^{\text{smooth}})\right] \right)\right),$ (28) $$

in which $\tilde{\lambda}_{i}$ is the $i$-th smallest eigenvalue of $L$ (*including repeats* when counting orders), and

$$ $\displaystyle\tilde{V}_{i}^{\text{smooth}}=\mathrm{concat}\left[v_{1}\rho(| \tilde{\lambda}_{1}-\tilde{\lambda}_{i}|),v_{2}\rho(|\tilde{\lambda}_{2}- \tilde{\lambda}_{i}|),\ldots,v_{n}\rho(|\tilde{\lambda}_{n}-\tilde{\lambda}_{i }|)\right],$ (29) $$

where $v_{1},v_{2},\ldots,v_{n}$ are mutually orthogonal normalized eigenvectors corresponding to eigenvalues $\tilde{\lambda}_{1},\tilde{\lambda}_{2},\ldots,\tilde{\lambda}_{n}$ respectively. With equation (28), we have completely removed the dependency on eigenspace dimensions in $Z(G)$. We then have

$$ $\displaystyle\|Z(G)-PZ(G^{\prime})\|_{\text{F}}$ $\displaystyle=\left\|\psi\left(\sum_{i=1}^{n}\phi\left(\mathrm{concat}\left[ \tilde{\lambda}_{i}\mathbf{1}_{n},f(\tilde{V}_{i}^{\text{smooth}})\right] \right)\right)\right.$ $\displaystyle\quad-\left.P\psi\left(\sum_{i=1}^{n}\phi\left(\mathrm{concat} \left[\tilde{\lambda}^{\prime}_{i}\mathbf{1}_{n},f(\tilde{V}_{i}^{\prime\text{ smooth}})\right]\right)\right)\right\|_{\text{F}}$ (30) $\displaystyle=\left\|\psi\left(\sum_{i=1}^{n}\phi\left(\mathrm{concat}\left[ \tilde{\lambda}_{i}\mathbf{1}_{n},f(\tilde{V}_{i}^{\text{smooth}})\right] \right)\right)\right.$ $\displaystyle\quad-\left.\psi\left(\sum_{i=1}^{n}\phi\left(\mathrm{concat} \left[\tilde{\lambda}^{\prime}_{i}\mathbf{1}_{n},f(P\tilde{V}_{i}^{\prime\text {smooth}})\right]\right)\right)\right\|_{\text{F}}$ (31) $\displaystyle\leqslant J_{\psi}\left\|\sum_{i=1}^{n}\phi\left(\mathrm{concat} \left[\tilde{\lambda}_{i}\mathbf{1}_{n},f(\tilde{V}_{i}^{\text{smooth}})\right ]\right)\right.$ $\displaystyle\quad\qquad-\left.\sum_{i=1}^{n}\phi\left(\mathrm{concat}\left[ \tilde{\lambda}^{\prime}_{i}\mathbf{1}_{n},f(P\tilde{V}_{i}^{\prime\text{ smooth}})\right]\right)\right\|_{\text{F}}$ (32) $\displaystyle\leqslant J_{\psi}\sum_{i=1}^{n}\left\|\phi\left(\mathrm{concat} \left[\tilde{\lambda}_{i}\mathbf{1}_{n},f(\tilde{V}_{i}^{\text{smooth}})\right ]\right)\right.$ $\displaystyle\qquad\qquad-\left.\phi\left(\mathrm{concat}\left[\tilde{\lambda} ^{\prime}_{i}\mathbf{1}_{n},f(P\tilde{V}_{i}^{\prime\text{smooth}})\right] \right)\right\|_{\text{F}}$ (33) $\displaystyle\leqslant J_{\psi}J_{\phi}\sum_{i=1}^{n}\left\|\mathrm{concat} \left[\left(\tilde{\lambda}_{i}-\tilde{\lambda}^{\prime}_{i}\right)\mathbf{1}_ {n},f(\tilde{V}_{i}^{\text{smooth}})-f(P\tilde{V}_{i}^{\prime\text{smooth}}) \right]\right\|_{\text{F}}$ (34) $\displaystyle\leqslant J_{\psi}J_{\phi}\sum_{i=1}^{n}\left[\sqrt{n}\left| \tilde{\lambda}_{i}-\tilde{\lambda}^{\prime}_{i}\right|+\|f(\tilde{V}_{i}^{ \text{smooth}})-f(P\tilde{V}_{i}^{\prime\text{smooth}})\|\right].$ (35) $$

The equality on (31) is due to the fact that $\psi$ and $\phi$ operate row-wise on the $n$ rows of their arguments, and that $f$ is permutation equivariant. (32) and (34) stem from the Lipschitz continuities of $\psi$ and $\phi$, respectively. (33) is due to triangular inequality. Now it suffices to bound the two terms in (35).

For the first term, we invoke Lemma B.2 to get

$$ $\displaystyle\sum_{i=1}^{n}\left|\tilde{\lambda}_{i}-\tilde{\lambda}^{\prime}_ {i}\right|\leqslant\sum_{i=1}^{n}\|L-PL^{\prime}P^{T}\|_{2}=n\|L-PL^{\prime}P^ {T}\|_{2},\quad\forall P\in S_{n}.$ (36) $$

This is because for any $P\in S_{n}$, $PL^{\prime}P^{T}$ has the same sequence of eigenvalues as $L^{\prime}$, namely $\tilde{\lambda}^{\prime}_{1},\tilde{\lambda}^{\prime}_{2},\ldots,\tilde{
\lambda}^{\prime}_{n}$.

For the second term, we have

$$ $\displaystyle\|f(\tilde{V}_{i}^{\text{smooth}})-f(P\tilde{V}_{i}^{\prime\text{ smooth}})\|$ $\displaystyle\leqslant J_{f}\min_{Q_{i}\in O(n)}\|\tilde{V}_{i}^{\text{smooth} }-P\tilde{V}_{i}^{\prime\text{smooth}}Q_{i}\|_{\text{F}}$ (37) $\displaystyle=J_{f}\min_{Q_{i}\in O(n)}\left\|\mathrm{concat}\left[v_{1}\rho(| \tilde{\lambda}_{1}-\tilde{\lambda}_{i}|),\ldots,v_{n}\rho(|\tilde{\lambda}_{n }-\tilde{\lambda}_{i}|)\right]\right.$ $\displaystyle\quad-\left.\mathrm{concat}\left[Pv^{\prime}_{1}\rho(|\tilde{ \lambda}^{\prime}_{1}-\tilde{\lambda}^{\prime}_{i}|),\ldots,Pv^{\prime}_{n} \rho(|\tilde{\lambda}^{\prime}_{n}-\tilde{\lambda}^{\prime}_{i}|)\right]Q_{i} \right\|_{\text{F}}$ (38) $\displaystyle\leqslant J_{f}\min_{Q_{i}\in O(n)}\left\{\left\|\mathrm{concat} \left[v_{1}\rho(|\tilde{\lambda}_{1}-\tilde{\lambda}_{i}|),\ldots,v_{n}\rho(| \tilde{\lambda}_{n}-\tilde{\lambda}_{i}|)\right]\right.\right.$ $\displaystyle\quad-\left.\mathrm{concat}\left[v_{1}\rho(|\tilde{\lambda}^{ \prime}_{1}-\tilde{\lambda}^{\prime}_{i}|),\ldots,v_{n}\rho(|\tilde{\lambda}^{ \prime}_{n}-\tilde{\lambda}^{\prime}_{i}|)\right]\right\|_{\text{F}}$ $\displaystyle\quad+\left\|\mathrm{concat}\left[v_{1}\rho(|\tilde{\lambda}^{ \prime}_{1}-\tilde{\lambda}^{\prime}_{i}|),\ldots,v_{n}\rho(|\tilde{\lambda}^{ \prime}_{n}-\tilde{\lambda}^{\prime}_{i}|)\right]\right.$ $\displaystyle\quad-\left.\left.\mathrm{concat}\left[Pv^{\prime}_{1}\rho(| \tilde{\lambda}^{\prime}_{1}-\tilde{\lambda}^{\prime}_{i}|),\ldots,Pv^{\prime} _{n}\rho(|\tilde{\lambda}^{\prime}_{n}-\tilde{\lambda}^{\prime}_{i}|)\right]Q_ {i}\right\|_{\text{F}}\right\}$ (39) $\displaystyle=J_{f}\sqrt{\sum_{j=1}^{n}\left[\rho(|\tilde{\lambda}_{j}-\tilde{ \lambda}_{i}|)-\rho(|\tilde{\lambda}^{\prime}_{j}-\tilde{\lambda}^{\prime}_{i} |)\right]^{2}}$ $\displaystyle\quad+J_{f}\min_{Q_{i}\in O(n)}\left\|\mathrm{concat}\left[v_{1} \rho(|\tilde{\lambda}^{\prime}_{1}-\tilde{\lambda}^{\prime}_{i}|),\ldots,v_{n} \rho(|\tilde{\lambda}^{\prime}_{n}-\tilde{\lambda}^{\prime}_{i}|)\right]\right.$ $\displaystyle\quad-\left.\mathrm{concat}\left[Pv^{\prime}_{1}\rho(|\tilde{ \lambda}^{\prime}_{1}-\tilde{\lambda}^{\prime}_{i}|),\ldots,Pv^{\prime}_{n} \rho(|\tilde{\lambda}^{\prime}_{n}-\tilde{\lambda}^{\prime}_{i}|)\right]Q_{i} \right\|_{\text{F}}.$ (40) $$

Here, (37) is due to our assumption on $f$, (38) follows from definitions of $\tilde{V}^{\text{smooth}}_{i}$ and $\tilde{V}^{\prime\text{smooth}}_{i}$, while (39) stems from triangular inequality. Now, for the first term of (40), we have

$$ $\displaystyle\sqrt{\sum_{j=1}^{n}\left[\rho(|\tilde{\lambda}_{j}-\tilde{ \lambda}_{i}|)-\rho(|\tilde{\lambda}^{\prime}_{j}-\tilde{\lambda}^{\prime}_{i} |)\right]^{2}}$ $\displaystyle\leqslant\sum_{j=1}^{n}\left|\rho(|\tilde{\lambda}_{j}-\tilde{ \lambda}_{i}|)-\rho(|\tilde{\lambda}^{\prime}_{j}-\tilde{\lambda}^{\prime}_{i} |)\right|$ (41) $\displaystyle\leqslant J_{\rho}\sum_{j=1}^{n}\left||\tilde{\lambda}_{j}-\tilde {\lambda}_{i}|-|\tilde{\lambda}^{\prime}_{j}-\tilde{\lambda}^{\prime}_{i}|\right|$ (42) $\displaystyle\leqslant J_{\rho}\sum_{j=1}^{n}\left(|\tilde{\lambda}_{i}-\tilde {\lambda}^{\prime}_{i}|+|\tilde{\lambda}_{j}-\tilde{\lambda}^{\prime}_{j}|\right)$ (43) $\displaystyle\leqslant 2nJ_{\rho}\|L-PL^{\prime}P^{T}\|_{2},\quad\forall P\in S _{n},$ (44) $$

where (42) is by Lipschitz continuity of $\rho$, (43) makes use of the fact that either $\tilde{\lambda}_{i}\geqslant\tilde{\lambda}_{j}$ and $\tilde{\lambda}^{\prime}_{i}\geqslant\tilde{\lambda}^{\prime}_{j}$, or $\tilde{\lambda}_{i}\leqslant\tilde{\lambda}_{j}$ and $\tilde{\lambda}^{\prime}_{i}\leqslant\tilde{\lambda}^{\prime}_{j}$. The final step (44) stems from Lemma B.2.

To bound the second term of (40), we first split the eigenvalues $\tilde{\lambda}^{\prime}_{1},\tilde{\lambda}^{\prime}_{2},\ldots,\tilde{
\lambda}^{\prime}_{n}$ into groups, namely $\mathcal{J}_{1}=\{\tilde{\lambda}^{\prime}_{J_{0}+1},\ldots,\tilde{\lambda}^{
\prime}_{J_{1}}\}$, $\mathcal{J}_{2}=\{\tilde{\lambda}^{\prime}_{J_{1}+1},\ldots,\tilde{\lambda}^{
\prime}_{J_{2}}\}$, $\ldots$, $\mathcal{J}_{L}=\{\tilde{\lambda}^{\prime}_{J_{L-1}+1},\ldots,\tilde{\lambda}^
{\prime}_{J_{L}}\}$, with $J_{0}=0$ and $J_{L}=n$. We ask that $\tilde{\lambda}^{\prime}_{k+1}-\tilde{\lambda}^{\prime}_{k}>\delta$ for all $k=J_{0},J_{1},\ldots,J_{L}$, and $\tilde{\lambda}^{\prime}_{k+1}-\tilde{\lambda}^{\prime}_{k}\leqslant\delta$ for all other $k$. We also denote by $\mathcal{J}(\tilde{\lambda}^{\prime}_{i})$ the group where $\tilde{\lambda}^{\prime}_{i}$ belong.

The consequence of such splitting is that for any eigenvalue $\tilde{\lambda}^{\prime}_{i}$ of $L^{\prime}$, all $\tilde{\lambda}^{\prime}_{j}$ satisfying $\rho(|\tilde{\lambda}^{\prime}_{j}-\tilde{\lambda}^{\prime}_{i}|)\neq 0$ belong to $\mathcal{J}(\tilde{\lambda}^{\prime}_{i})$. Therefore, we actually have

$$ $\displaystyle\qquad\min_{Q_{i}\in O(n)}\left\|\mathrm{concat}\left[v_{j}\rho(| \tilde{\lambda}^{\prime}_{j}-\tilde{\lambda}^{\prime}_{i}|)\right]_{j=1}^{n}- \mathrm{concat}\left[Pv^{\prime}_{j}\rho(|\tilde{\lambda}^{\prime}_{j}-\tilde{ \lambda}^{\prime}_{i}|)\right]_{j=1}^{n}Q_{i}\right\|_{\text{F}}$ $\displaystyle=\min_{Q_{i}\in O(|\mathcal{J}(\tilde{\lambda}^{\prime}_{i})|)} \left\|\mathrm{concat}\left[v_{j}\rho(|\tilde{\lambda}^{\prime}_{j}-\tilde{ \lambda}^{\prime}_{i}|)\right]_{\tilde{\lambda}^{\prime}_{j}\in\mathcal{J}( \tilde{\lambda}^{\prime}_{i})}-\mathrm{concat}\left[Pv^{\prime}_{j}\rho(| \tilde{\lambda}^{\prime}_{j}-\tilde{\lambda}^{\prime}_{i}|)\right]_{\tilde{ \lambda}^{\prime}_{j}\in\mathcal{J}(\tilde{\lambda}^{\prime}_{i})}Q_{i}\right \|_{\text{F}}.$ (45) $$

Now, for any $Q_{i}\in O(|\mathcal{J}(\tilde{\lambda}^{\prime}_{i})|)$, we have

$$ $\displaystyle\quad\left\|\mathrm{concat}\left[v_{j}\rho(|\tilde{\lambda}^{ \prime}_{j}-\tilde{\lambda}^{\prime}_{i}|)\right]_{\tilde{\lambda}^{\prime}_{j }\in\mathcal{J}(\tilde{\lambda}^{\prime}_{i})}-\mathrm{concat}\left[Pv^{\prime }_{j}\rho(|\tilde{\lambda}^{\prime}_{j}-\tilde{\lambda}^{\prime}_{i}|)\right]_ {\tilde{\lambda}^{\prime}_{j}\in\mathcal{J}(\tilde{\lambda}^{\prime}_{i})}Q_{i }\right\|_{\text{F}}$ $\displaystyle=\left\|\mathrm{concat}\left[v_{j}\rho(|\tilde{\lambda}^{\prime}_ {j}-\tilde{\lambda}^{\prime}_{i}|)-\sum_{k:\tilde{\lambda}^{\prime}_{k}\in \mathcal{J}(\tilde{\lambda}^{\prime}_{i})}Pv^{\prime}_{k}\rho(|\tilde{\lambda} ^{\prime}_{k}-\tilde{\lambda}^{\prime}_{i}|)(Q_{i})_{kj}\right]_{\tilde{ \lambda}^{\prime}_{j}\in\mathcal{J}(\tilde{\lambda}^{\prime}_{i})}\right\|_{ \text{F}}$ (46) $\displaystyle\leqslant\left\|\mathrm{concat}\left[\sum_{k:\tilde{\lambda}^{ \prime}_{k}\in\mathcal{J}(\tilde{\lambda}^{\prime}_{i})}Pv^{\prime}_{k}\left[ \rho(|\tilde{\lambda}^{\prime}_{j}-\tilde{\lambda}^{\prime}_{i}|)-\rho(|\tilde {\lambda}^{\prime}_{k}-\tilde{\lambda}^{\prime}_{i}|)\right](Q_{i})_{kj}\right ]_{\tilde{\lambda}^{\prime}_{j}\in\mathcal{J}(\tilde{\lambda}^{\prime}_{i})} \right\|_{\text{F}}$ $\displaystyle\quad+\left\|\mathrm{concat}\left[\rho(|\tilde{\lambda}^{\prime}_ {j}-\tilde{\lambda}^{\prime}_{i}|)\left(v_{j}-\sum_{k:\tilde{\lambda}^{\prime} _{k}\in\mathcal{J}(\tilde{\lambda}^{\prime}_{i})}Pv^{\prime}_{k}(Q_{i})_{kj} \right)\right]_{\tilde{\lambda}^{\prime}_{j}\in\mathcal{J}(\tilde{\lambda}^{ \prime}_{i})}\right\|_{\text{F}}$ (47) $\displaystyle\leqslant\sum_{j:\tilde{\lambda}^{\prime}_{j}\in\mathcal{J}( \tilde{\lambda}^{\prime}_{i})}\left\|\sum_{k:\tilde{\lambda}^{\prime}_{k}\in \mathcal{J}(\tilde{\lambda}^{\prime}_{i})}Pv^{\prime}_{k}\left[\rho(|\tilde{ \lambda}^{\prime}_{j}-\tilde{\lambda}^{\prime}_{i}|)-\rho(|\tilde{\lambda}^{ \prime}_{k}-\tilde{\lambda}^{\prime}_{i}|)\right](Q_{i})_{kj}\right\|$ $\displaystyle\quad+\left\|\mathrm{concat}\left[\rho(|\tilde{\lambda}^{\prime}_ {j}-\tilde{\lambda}^{\prime}_{i}|)\left(v_{j}-\sum_{k:\tilde{\lambda}^{\prime} _{k}\in\mathcal{J}(\tilde{\lambda}^{\prime}_{i})}Pv^{\prime}_{k}(Q_{i})_{kj} \right)\right]_{\tilde{\lambda}^{\prime}_{j}\in\mathcal{J}(\tilde{\lambda}^{ \prime}_{i})}\right\|_{\text{F}}.$ (48) $$

Now we analyze the two terms in (48). For the first term,

$$ $\displaystyle\quad\left\|\sum_{k:\tilde{\lambda}^{\prime}_{k}\in\mathcal{J}( \tilde{\lambda}^{\prime}_{i})}Pv^{\prime}_{k}\left[\rho(|\tilde{\lambda}^{ \prime}_{j}-\tilde{\lambda}^{\prime}_{i}|)-\rho(|\tilde{\lambda}^{\prime}_{k}- \tilde{\lambda}^{\prime}_{i}|)\right](Q_{i})_{kj}\right\|$ $\displaystyle=\left\|\mathrm{concat}\left\{Pv^{\prime}_{k}\left[\rho(|\tilde{ \lambda}^{\prime}_{j}-\tilde{\lambda}^{\prime}_{i}|)-\rho(|\tilde{\lambda}^{ \prime}_{k}-\tilde{\lambda}^{\prime}_{i}|)\right]\right\}_{\tilde{\lambda}^{ \prime}_{k}\in\mathcal{J}(\tilde{\lambda}^{\prime}_{i})}(Q_{i})_{\cdot j} \right\|_{\text{F}}$ (49) $\displaystyle\leqslant\left\|\mathrm{concat}\left\{Pv^{\prime}_{k}\left[\rho(| \tilde{\lambda}^{\prime}_{j}-\tilde{\lambda}^{\prime}_{i}|)-\rho(|\tilde{ \lambda}^{\prime}_{k}-\tilde{\lambda}^{\prime}_{i}|)\right]\right\}_{\tilde{ \lambda}^{\prime}_{k}\in\mathcal{J}(\tilde{\lambda}^{\prime}_{i})}\right\|_{ \text{F}}\|(Q_{i})_{\cdot j}\|_{2}$ (50) $\displaystyle=\left\|\mathrm{concat}\left\{Pv^{\prime}_{k}\left[\rho(|\tilde{ \lambda}^{\prime}_{j}-\tilde{\lambda}^{\prime}_{i}|)-\rho(|\tilde{\lambda}^{ \prime}_{k}-\tilde{\lambda}^{\prime}_{i}|)\right]\right\}_{\tilde{\lambda}^{ \prime}_{k}\in\mathcal{J}(\tilde{\lambda}^{\prime}_{i})}\right\|_{\text{F}}$ (51) $\displaystyle\leqslant\sum_{k:\tilde{\lambda}^{\prime}_{k}\in\mathcal{J}( \tilde{\lambda}^{\prime}_{i})}\|Pv^{\prime}_{k}\|\left|\rho(|\tilde{\lambda}^{ \prime}_{j}-\tilde{\lambda}^{\prime}_{i}|)-\rho(|\tilde{\lambda}^{\prime}_{k}- \tilde{\lambda}^{\prime}_{i}|)\right|$ (52) $\displaystyle=\sum_{k:\tilde{\lambda}^{\prime}_{k}\in\mathcal{J}(\tilde{ \lambda}^{\prime}_{i})}\left|\rho(|\tilde{\lambda}^{\prime}_{j}-\tilde{\lambda }^{\prime}_{i}|)-\rho(|\tilde{\lambda}^{\prime}_{k}-\tilde{\lambda}^{\prime}_{ i}|)\right|.$ (53) $$

Here, (49) translates the first term of (48) into the form of matrix multiplication. Then (50) makes use of Lemma B.3, and (51) further uses the fact that $Q_{i}$ is orthogonal. Finally, (53) stems from the fact that $v^{\prime}_{k}$ is a normalized eigenvector. Regarding (53), we may discuss two cases. If both $|\tilde{\lambda}^{\prime}_{j}-\tilde{\lambda}^{\prime}_{i}|\leqslant\delta$ and $|\tilde{\lambda}^{\prime}_{k}-\tilde{\lambda}^{\prime}_{i}|\leqslant\delta$, then

$$ $\displaystyle\quad\sum_{k:\tilde{\lambda}^{\prime}_{k}\in\mathcal{J}(\tilde{ \lambda}^{\prime}_{i})}\left|\rho(|\tilde{\lambda}^{\prime}_{j}-\tilde{\lambda }^{\prime}_{i}|)-\rho(|\tilde{\lambda}^{\prime}_{k}-\tilde{\lambda}^{\prime}_{ i}|)\right|$ $\displaystyle\leqslant J_{\rho}\sum_{k:\tilde{\lambda}^{\prime}_{k}\in\mathcal {J}(\tilde{\lambda}^{\prime}_{i})}\left||\tilde{\lambda}^{\prime}_{j}-\tilde{ \lambda}^{\prime}_{i}|-|\tilde{\lambda}^{\prime}_{k}-\tilde{\lambda}^{\prime}_ {i}|\right|$ (54) $\displaystyle\leqslant 2\delta J_{\rho}|\mathcal{J}(\tilde{\lambda}^{\prime}_{ i})|.$ (55) $$

If at least one of $|\tilde{\lambda}^{\prime}_{j}-\tilde{\lambda}^{\prime}_{i}|$ and $|\tilde{\lambda}^{\prime}_{k}-\tilde{\lambda}^{\prime}_{i}|$ exceeds $\delta$, we may assume without loss of generality that $|\tilde{\lambda}^{\prime}_{j}-\tilde{\lambda}^{\prime}_{i}|>\delta$. Then $\rho(|\tilde{\lambda}^{\prime}_{j}-\tilde{\lambda}^{\prime}_{i}|)=\rho(\delta)=0$ by continuity of $\rho$, and we still have

$$ $\displaystyle\quad\sum_{k:\tilde{\lambda}^{\prime}_{k}\in\mathcal{J}(\tilde{ \lambda}^{\prime}_{i})}\left|\rho(|\tilde{\lambda}^{\prime}_{j}-\tilde{\lambda }^{\prime}_{i}|)-\rho(|\tilde{\lambda}^{\prime}_{k}-\tilde{\lambda}^{\prime}_{ i}|)\right|$ $\displaystyle=\sum_{k:\tilde{\lambda}^{\prime}_{k}\in\mathcal{J}(\tilde{ \lambda}^{\prime}_{i})}\left|\rho(\delta)-\rho(|\tilde{\lambda}^{\prime}_{k}- \tilde{\lambda}^{\prime}_{i}|)\right|$ (56) $\displaystyle\leqslant J_{\rho}\sum_{k:\tilde{\lambda}^{\prime}_{k}\in\mathcal {J}(\tilde{\lambda}^{\prime}_{i})}\left|\delta-|\tilde{\lambda}^{\prime}_{k}- \tilde{\lambda}^{\prime}_{i}|\right|$ (57) $\displaystyle\leqslant 2\delta J_{\rho}|\mathcal{J}(\tilde{\lambda}^{\prime}_{ i})|.$ (58) $$

Therefore, we conclude that

$$ $\displaystyle\left\|\sum_{k:\tilde{\lambda}^{\prime}_{k}\in\mathcal{J}(\tilde{ \lambda}^{\prime}_{i})}Pv^{\prime}_{k}\left[\rho(|\tilde{\lambda}^{\prime}_{j} -\tilde{\lambda}^{\prime}_{i}|)-\rho(|\tilde{\lambda}^{\prime}_{k}-\tilde{ \lambda}^{\prime}_{i}|)\right](Q_{i})_{kj}\right\|\leqslant 2\delta J_{\rho}| \mathcal{J}(\tilde{\lambda}^{\prime}_{i})|,$ (59) $$

or

$$ $\displaystyle\sum_{j:\tilde{\lambda}^{\prime}_{j}\in\mathcal{J}(\tilde{\lambda }^{\prime}_{i})}\left\|\sum_{k:\tilde{\lambda}^{\prime}_{k}\in\mathcal{J}( \tilde{\lambda}^{\prime}_{i})}Pv^{\prime}_{k}\left[\rho(|\tilde{\lambda}^{ \prime}_{j}-\tilde{\lambda}^{\prime}_{i}|)-\rho(|\tilde{\lambda}^{\prime}_{k}- \tilde{\lambda}^{\prime}_{i}|)\right](Q_{i})_{kj}\right\|\leqslant 2\delta J_{ \rho}|\mathcal{J}(\tilde{\lambda}^{\prime}_{i})|^{2}.$ (60) $$

For the second term of (48), we have

$$ $\displaystyle\quad\left\|\mathrm{concat}\left[\rho(|\tilde{\lambda}^{\prime}_{ j}-\tilde{\lambda}^{\prime}_{i}|)\left(v_{j}-\sum_{k:\tilde{\lambda}^{\prime}_ {k}\in\mathcal{J}(\tilde{\lambda}^{\prime}_{i})}Pv^{\prime}_{k}(Q_{i})_{kj} \right)\right]_{\tilde{\lambda}^{\prime}_{j}\in\mathcal{J}(\tilde{\lambda}^{ \prime}_{i})}\right\|_{\text{F}}$ $\displaystyle\leqslant\left\|\mathrm{concat}\left[v_{j}-\sum_{k:\tilde{\lambda }^{\prime}_{k}\in\mathcal{J}(\tilde{\lambda}^{\prime}_{i})}Pv^{\prime}_{k}(Q_{ i})_{kj}\right]_{\tilde{\lambda}^{\prime}_{j}\in\mathcal{J}(\tilde{\lambda}^{ \prime}_{i})}\right\|_{\text{F}}$ (61) $\displaystyle=\left\|\mathrm{concat}\left[v_{j}\right]_{\tilde{\lambda}^{ \prime}_{j}\in\mathcal{J}(\tilde{\lambda}^{\prime}_{i})}-\mathrm{concat}\left[ Pv^{\prime}_{j}\right]_{\tilde{\lambda}^{\prime}_{j}\in\mathcal{J}(\tilde{ \lambda}^{\prime}_{i})}Q_{i}\right\|_{\text{F}}.$ (62) $$

Here, (61) uses the fact that $\rho(|\tilde{\lambda}^{\prime}_{j}-\tilde{\lambda}^{\prime}_{i}|)\in[0,1]$, and (62) rewrites (61) into matrix multiplication. We further transform (62) into

$$ $\displaystyle\quad\left\|\mathrm{concat}\left[v_{j}\right]_{\tilde{\lambda}^{ \prime}_{j}\in\mathcal{J}(\tilde{\lambda}^{\prime}_{i})}-\mathrm{concat}\left[ Pv^{\prime}_{j}\right]_{\tilde{\lambda}^{\prime}_{j}\in\mathcal{J}(\tilde{ \lambda}^{\prime}_{i})}Q_{i}\right\|_{\text{F}}$ $\displaystyle\leqslant\left\|\mathrm{concat}\left[v_{j}\right]_{\tilde{\lambda }^{\prime}_{j}\in\mathcal{J}(\tilde{\lambda}^{\prime}_{i})}Q_{i}^{T}-\mathrm{ concat}\left[Pv^{\prime}_{j}\right]_{\tilde{\lambda}^{\prime}_{j}\in\mathcal{J }(\tilde{\lambda}^{\prime}_{i})}\right\|_{\text{F}}\|Q_{i}^{T}\|_{2}$ (63) $\displaystyle=\left\|\mathrm{concat}\left[Pv^{\prime}_{j}\right]_{\tilde{ \lambda}^{\prime}_{j}\in\mathcal{J}(\tilde{\lambda}^{\prime}_{i})}-\mathrm{ concat}\left[v_{j}\right]_{\tilde{\lambda}^{\prime}_{j}\in\mathcal{J}(\tilde{ \lambda}^{\prime}_{i})}Q_{i}^{T}\right\|_{\text{F}},$ (64) $$

in which (63) makes use of Lemma B.3, and (64) uses the fact that the spectral norm of an orthogonal matrix is always 1. Now, we may apply Lemma B.1 on (64) to find that there exists $Q_{i}\in O(|\mathcal{J}(\tilde{\lambda}^{\prime}_{i})|)$, such that

$$ $\displaystyle\quad\left\|\mathrm{concat}\left[Pv^{\prime}_{j}\right]_{\tilde{ \lambda}^{\prime}_{j}\in\mathcal{J}(\tilde{\lambda}^{\prime}_{i})}-\mathrm{ concat}\left[v_{j}\right]_{\tilde{\lambda}^{\prime}_{j}\in\mathcal{J}(\tilde{ \lambda}^{\prime}_{i})}Q_{i}^{T}\right\|_{\text{F}}$ $\displaystyle\leqslant\frac{\sqrt{8}}{\delta}\min\left\{\sqrt{|\mathcal{J}( \tilde{\lambda}^{\prime}_{i})|}\cdot\|PL^{\prime}P^{T}-L\|_{2},\|PL^{\prime}P^ {T}-L\|_{\text{F}}\right\}.$ (65) $$

To arrive at (65), we exploit the fact that at boundaries of $\mathcal{J}(\tilde{\lambda}^{\prime}_{i})$ (assumed to be $\tilde{\lambda}^{\prime}_{J_{\ell-1}+1}$ and $\tilde{\lambda}^{\prime}_{J_{\ell}}$), we always have $\tilde{\lambda}^{\prime}_{J_{\ell-1}+1}-\tilde{\lambda}^{\prime}_{J_{\ell-1}}>\delta$ and $\tilde{\lambda}^{\prime}_{J_{\ell}+1}-\tilde{\lambda}^{\prime}_{J_{\ell}}>\delta$. Thus, we end up finding that

$$ $\displaystyle\quad\left\|\mathrm{concat}\left[\rho(|\tilde{\lambda}^{\prime}_{ j}-\tilde{\lambda}^{\prime}_{i}|)\left(v_{j}-\sum_{k:\tilde{\lambda}^{\prime}_ {k}\in\mathcal{J}(\tilde{\lambda}^{\prime}_{i})}Pv^{\prime}_{k}(Q_{i})_{kj} \right)\right]_{\tilde{\lambda}^{\prime}_{j}\in\mathcal{J}(\tilde{\lambda}^{ \prime}_{i})}\right\|_{\text{F}}$ $\displaystyle\leqslant\frac{\sqrt{8}}{\delta}\min\left\{\sqrt{|\mathcal{J}( \tilde{\lambda}^{\prime}_{i})|}\cdot\|L-PL^{\prime}P^{T}\|_{2},\|L-PL^{\prime} P^{T}\|_{\text{F}}\right\}.$ (66) $$

Plugging equations (60) and (66) into (48), we find that $\exists Q_{i}\in O(|\mathcal{J}(\tilde{\lambda}^{\prime}_{i})|)$, such that

$$ $\displaystyle\quad\left\|\mathrm{concat}\left[v_{j}\rho(|\tilde{\lambda}^{ \prime}_{j}-\tilde{\lambda}^{\prime}_{i}|)\right]_{\tilde{\lambda}^{\prime}_{j }\in\mathcal{J}(\tilde{\lambda}^{\prime}_{i})}-\mathrm{concat}\left[Pv^{\prime }_{j}\rho(|\tilde{\lambda}^{\prime}_{j}-\tilde{\lambda}^{\prime}_{i}|)\right]_ {\tilde{\lambda}^{\prime}_{j}\in\mathcal{J}(\tilde{\lambda}^{\prime}_{i})}Q_{i }\right\|_{\text{F}}$ $\displaystyle\leqslant 2\delta J_{\rho}|\mathcal{J}(\tilde{\lambda}^{\prime}_{ i})|^{2}+\frac{\sqrt{8}}{\delta}\min\left\{\sqrt{|\mathcal{J}(\tilde{\lambda}^ {\prime}_{i})|}\cdot\|L-PL^{\prime}P^{T}\|_{2},\|L-PL^{\prime}P^{T}\|_{\text{F }}\right\}$ (67) $\displaystyle\leqslant 2n^{2}\delta J_{\rho}+\frac{\sqrt{8}}{\delta}\|L-PL^{ \prime}P^{T}\|_{\text{F}}.$ (68) $$

Therefore,

$$ $\displaystyle\quad\min_{Q_{i}\in O(n)}\left\|\mathrm{concat}\left[v_{j}\rho(| \tilde{\lambda}^{\prime}_{j}-\tilde{\lambda}^{\prime}_{i}|)\right]_{j=1}^{n}- \mathrm{concat}\left[Pv^{\prime}_{j}\rho(|\tilde{\lambda}^{\prime}_{j}-\tilde{ \lambda}^{\prime}_{i}|)\right]_{j=1}^{n}Q_{i}\right\|_{\text{F}}$ $\displaystyle\leqslant 2n^{2}\delta J_{\rho}+\frac{\sqrt{8}}{\delta}\|L-PL^{ \prime}P^{T}\|_{\text{F}}.$ (69) $$

Plugging (44) and (69) into (40), we get

$$ $\displaystyle\|f(\tilde{V}_{i}^{\text{smooth}})-f(P\tilde{V}_{i}^{\prime\text{ smooth}})\|\leqslant J_{f}\left(2nJ_{\rho}\|L-PL^{\prime}P^{T}\|_{2}+2n^{2} \delta J_{\rho}+\frac{\sqrt{8}}{\delta}\|L-PL^{\prime}P^{T}\|_{\text{F}}\right).$ (70) $$

Combining everything together, we eventually arrive at

$$ $\displaystyle\|Z(G)-PZ(G^{\prime})\|_{\text{F}}$ $\displaystyle\leqslant nJ_{\psi}J_{\phi}\Bigg{[}(\sqrt{n}+2nJ_{\rho}J_{f})\|L- PL^{\prime}P^{T}\|_{2}$ $\displaystyle\qquad\qquad+J_{f}\left(2n^{2}\delta J_{\rho}+\frac{\sqrt{8}}{ \delta}\|L-PL^{\prime}P^{T}\|_{\text{F}}\right)\Bigg{]}.$ (71) $$

By choosing a $\delta$ value that minimizes the RHS of equation (71), we get

$$ $\displaystyle\|Z(G)-PZ(G^{\prime})\|_{\text{F}}$ $\displaystyle\leqslant nJ_{\psi}J_{\phi}\big{[}(\sqrt{n}+2nJ_{\rho}J_{f})\|L- PL^{\prime}P^{T}\|_{2}$ $\displaystyle\qquad\qquad+4\sqrt[4]{2}J_{f}\sqrt{J_{\rho}}n\|L-PL^{\prime}P^{T }\|_{\text{F}}^{1/2}\big{]},$ (72) $$

which is our desired final result.
∎

###### Lemma B.1 (Davis-Kahan theorem, Proposition A.1 of (Huang et al., 2024 ) , see also (Yu et al., 2015 ) ) .

###### Lemma B.2 (Weyl’s inequality, Proposition A.2 of (Huang et al., 2024 ) ) .

###### Lemma B.3 (Lemma A.1 of (Huang et al., 2024 ) ) .

###### Proof.

## Appendix C Other related works

#### Expressive GNNs.

As is shown by Xu et al. (), the expressive power of MPNNs is upper-bounded by that of 1-dimensional Weisfeiler-Leman test (1-WL). This implies that MPNNs can fail to discriminate many non-isomorphic graph pairs, potentially leading to their weakness in capturing important structural information or multi-node interactions. A great number of works have attempted to improve the expressive power of GNNs, in the sense that to make them better either at solving the graph isomorphism problem (GI), or at approximating certain graph functions. Those existing works can be roughly categorized into three families: (1) methods utilizing additional combinatorial features (Barceló et al., ; Bouritsas et al., ; Li et al., ); (2) methods applying message passing among higher-order tuples of nodes, or *higher-order GNNs* (Bodnar et al., ; Feng et al., ; Maron et al., ; ; Morris et al., ; ; Zhang et al., ; Zhou et al., ; ); (3) methods decomposing input graphs into bags of subgraphs, or *subgraph GNNs* (Bevilacqua et al., ; Cotta et al., ; Frasca et al., ; Huang et al., ; Kong et al., ; Qian et al., ; You et al., ; Zhang & Li, ; Zhou et al., ). While methods belonging to class (1) enjoy the lowest complexities, they often generalize worse due to their use of hand-crafted features. On the contrary, higher-order GNNs and subgraph GNNs bring more systematic gains to the expressive power, but their computational complexities are much higher than MPNNs. Hence, a trade-off between expressive power and efficiency is an important issue for the design of expressive GNNs.

#### Graph transformers.

Graph transformers (Chen et al., ; Dwivedi et al., ; Rampášek et al., ; Wang et al., ; Ying et al., ) treat each node within a graph as a separate token, and use a standard transformer architecture to update node features (or embeddings of tokens). With attention mechanism, graph transformers take into account the interactions between all pairs of nodes (instead of only connected node pairs, as in traditional MPNNs), and are naturally good at capturing long-range interactions (Dwivedi et al., ). One of the central issues regarding graph transformers is the design of structural and positional encodings of nodes, in order to make transformers aware of adjacency information. Kim et al. (); Zhou et al. () analyze the theoretical expressive power of graph transformers and their high-order versions as well as the effects of positional encodings.

## Appendix D Experimental details

### D.1 Dataset descriptions

The statistics of used datasets in the paper are summarized in Table 5.

**Table 5: Overview of the datasets used in the paper.**
| Dataset | #Graphs | Avg. # | Avg. # | Prediction | Prediction | Metric |
| --- | --- | --- | --- | --- | --- | --- |
| nodes | edges | level | task |  |  |  |
| QM9 | 130,000 | 18.0 | 37.3 | graph | regression | Mean Abs. Error |
| ZINC | 12,000 | 23.2 | 24.9 | graph | regression | Mean Abs. Error |
| Alchemy | 202,579 | 10.0 | 10.4 | graph | regression | Mean Abs. Error |
| PCQM-Contact | 529,434 | 30.1 | 61.0 | inductive link | link ranking | MRR |

### D.2 Implementation details

We implement OGE-Aug with the PyGHO library (Wang & Zhang, ). To integrate OGE-Aug with other base models including MPNN and graph transformers, we also implement our methods building on the GraphGPS (Rampášek et al., ) code base, where we build OGE-Aug as a plug-and-play module. The module takes in Laplacians as inputs and processes the eigenvalues/eigenvectors using # PE layers with dimension PE hidden dim, and outputs an embedding with dimension PE dim; see Table 6 for detailed settings. In this module, we use permutation-equivariant set function (Zaheer et al., ) to process the eigenvalues and multiply the eigenvalue embeddings to the eigenvectors. Moreover, we also multiply eigenvectors with eigenvectors to initialize the higher order representations. After that, this module will product each node’s representation with its neighbors’ and update the representation iteratively. The embedding is then combined with other node features and other optional positional encodings, then fed jointly into downstream layers (which consist of various GNN and graph transformer modules). Therefore, OGE-Aug can be either used solely or integrated easily with arbitrary backbones.

We also implement a version where OGE-Aug modules act on the embeddings of nodes and edges, which can be viewed as operating on weighted or latent Laplacians incorporating node and edge features. However, we experimentally find that processing the original Laplacians with OGE-Aug and encoding the node/edge features separately via other encoders (as explained above) yields better performance.

In addition, to make OGE-Aug more robust, we add a small-scale noise (typically a Gaussian noise with mean zero and variance $1e^{-5}$) to the Laplacians in the training process. We also randomly permute the Laplacians and do inverse permutation to the output eigenvectors to simulate the noise caused by the permutation and the numerical algorithm. We use the original Laplacians in the inference stage.

### D.3 Experimental settings

As explained earlier, we integrate our OGE-Aug with the GraphGPS code base, and thus also follow their experimental settings. With only mild hyperparameter search, we achieve SOTA or highly competitive results on all datasets. The adopted hyperparameters in our experiments are summarized in Table 6.

**Table 6: Hyperparameters of the experiments.**
| Hyperparameters | QM9 | ZINC | Alchemy | PCQM-Contact |
| --- | --- | --- | --- | --- |
| # Layers | 10 | 10 | 16 | 6 |
| Hidden dim | 64 | 64 | 128 | 96 |
| MPNN | GINE | GINE | GINE | GatedGCN |
| Attention | Transformer^† | Transformer^∗ | - | Transformer |
| # Heads | 4 | 4 | - | 4 |
| Dropout | 0 | 0 | 0 | 0 |
| Attention dropout | 0.2 | 0.5 | - | 0.1 |
| Graph pooling | sum | sum | sum | edge dot |
| Positional encoding | OGE-Aug(29) | OGE-Aug(37) | OGE-Aug(12) | OGE-Aug + LapPE |
| PE hidden dim | 64 | 64 | 64 | 32 |
| PE dim | 28 | 28 | 28 | 16 |
| PE # layer | 4 | 4 | 4 | 3 |
| Batch size | 256 | 32 | 128 | 64 |
| Learning rate | 0.001 | 0.001 | 0.001 | 0.0005 |
| # Epochs | 500 | 2000 | 1000 | 100 |
| # Warmup epochs | 50 | 50 | 50 | 10 |
| Weight decay | 1e-5 | 1e-5 | 1e-5 | 0 |
| # Parameters | 783249 | 617677 | 1968352 | 845632 |
| Time (epoch/total) | 139s/19.3h | 28s/15.6h | 5s/1.4h | 1541s/42.8h |

Here ^† for QM9 suggests that experiments on these four targets $U_{0},U,G,H$ are conducted using the PyGHO code version without GraphGPS. ^∗ for ZINC means that the transformer is not necessary - actually we can achieve highly competitive results even without global attention. When we use transformers, we reduce the PE hidden dimension to 32, PE dimension to 16, and PE # layers to 3, resulting $505905$ total number of parameters and $14.9h$ total training time, which are both less than the case without transformers.

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 5
presentation: 3
questions: * Could you elaborate on how taking inner products may potentially lead to a loss of the rich structural and positional information provided by vanilla Laplacian eigenvectors (line 85)?
* How does the method scale to large-scale graphs? Could you discuss its scalability?
soundness: 2
strengths: - The writing is well-organized and generally reader-friendly.
- The theoretical analysis is comprehensive and detailed.
summary: The paper presents a robust orthogonal group-equivariant neural network designed to enhance graph representation using Laplacian vectors. Experiments conducted on various graphs demonstrate the competitive performance of the proposed approach.
weaknesses: - The datasets used in the experiments are somewhat limited. The proposed method would be more convincing if validated on a wider range of datasets, such as PATTERN, CLUSTER, or MolHIV.
- Additional illustrations, such as ablation or comparison experiments (e.g., investigating the impact of the continuous smoothing function *ρ*, or examining how the method captures global properties of graphs), would provide a more thorough and solid foundation for the study.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: See weaknesses.
soundness: 2
strengths: 1. The paper is well-organized and easy to follow.
2. The experimental results seem promising.
3. Authors utilize a novel strategy to softly split the eigenvectors from different eigenspaces, solving the instability constraint of most existing work.
summary: This paper studies the improvement of positional encodings (PEs) based on Laplacian eigenvectors, commonly used as feature augmentations to enhance the expressivity and effectiveness of GNNs.
The paper points out that existing PEs, which deal with symmetries of Laplacian eigenvectors with naive $O(p)$-group invariant encoders, may lose the full expressivity in the eigenvectors. Moreover, the paper argues that the instability resulting from the properties of eigenvectors is ignored in most research. Thus, the paper proposes a novel encoder to generate expressive and stable positional embeddings by utilizing invariant point cloud networks and incorporating smooth function for "soft splitting". Theoretical analysis and extensive experiments demonstrate the effectiveness of the proposed positional encoder.
weaknesses: 1. The novelty of the method is somewhat limited, especially the direct application of existing invariant point cloud networks over the eigenvectors without any transfer challenge.
2. The paper doesn’t provide any detail about instance models of $\rho$, $\phi$, and $\psi$ (in Equations 6 and 7) implemented in the experiments, and doesn’t discuss the Lipschitz continuity of these practical models.
3. There is no detail about how OGE-Aug deals with the sign ambiguity of eigenvectors.
4. Authors ignore some essential experiments.
    - Authors don’t verify the stability of the OGE-Aug on OOD benchmarks such as DrugOOD [1], where SPE [2] is validated on this dataset.
    - There is no ablation study on the effectiveness of the proposed “soft splitting” strategy. I think it’ll be better to conduct experiments on Vanilla OGE-Aug as a control group.
    - There is no experiment studying the sensitivity of hyperparameters. For example, the authors don’t explore how different shapes of ρ influence the effectiveness and stability of the positional encodings.
    - The paper doesn’t report the running time of different positional encoding methods.
5. As mentioned in Line 346, insisting on the universality of invariant representation function f may hurt the stability of the positional encoder, however, there is no quantitative analysis nor experimental guidance about how to trade off university and stability.

[1] Ji, Yuanfeng, et al. "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. Vol. 37. No. 7. 2023.

[2] Huang, Yinan, et al. "On the stability of expressive positional encodings for graph neural networks." arXiv preprint arXiv:2310.02579 (2023).

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: The paper states that "taking inner products can potentially lose much of the rich structural and positional information carried by vanilla Laplacian eigenvectors." However, it seems to me that the inner product, which serves as a projection matrix onto the corresponding eigenspace, should preserve all the information about that space. I thought that the added expressivity comes from using more expressive point cloud architectures rather than the inner product itself.  Could the authors provide a more detailed explanation or proof of what specific information, if any, is lost when taking inner products of eigenvectors compared to using the raw eigenvectors? Additionally could the authors clarify whether the increased expressivity comes primarily from the expressive power of point cloud architectures rather than avoiding inner products?
soundness: 2
strengths: 1. The paper offers a simple and straightforward way to incorporate Laplacian eigenvectors into GNNs, making it easy to apply to existing architectures.

2. The theoretical result showing that the first approach can achieve universality with a model complexity of $n \cdot \exp(\text{max}(\mu))$ leverages the sparsity of natural graphs in an interesting way (most graphs have low values of $\mu$).

3. The approach is validated with competitive, and in some cases state-of-the-art, results across several common graph benchmarks, supporting its practical usefulness.
summary: This paper addresses the problem (established in [2]) of how to incorporate Laplacian eigenvectors into message-passing neural networks (MPNNs) to enhance expressivity while maintaining invariance to the symmetric group. The authors propose two main architectures to achieve this.

First, they present a natural method for integrating equivariant point cloud architectures into existing MPNNs. They then show that when using this method with a universal point cloud architecture, a universal GNN model can be constructed.

The paper then tackles the recently established problem (see [1]) of handling these eigenvectors in a stable manner. They propose a second architecture that, while sacrificing some expressivity compared to the first model, achieves provable stability bounds.

The paper concludes with empirical validation, showing that the second architecture achieves competitive, and in some cases state-of-the-art results across several standard graph benchmarks. 

[1]  Yinan Huang, William Lu, Joshua Robinson, Yu Yang, Muhan Zhang, Stefanie Jegelka, and Pan Li. On the stability of expressive
positional encodings for graph neural networks. arXiv preprint arXiv:2310.02579, 2023.

[2] Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv preprint arXiv:2202.13013, 2022.
weaknesses: 1. The paper's novelty is somewhat limited. The idea of incorporating Laplacian eigenvectors into MPNNs while respecting the symmetries of the orthogonal group $O(d)$ was already discussed in [2], making the use of point cloud architectures a natural but not particularly novel approach. Similarly, the importance of stability when dealing with Laplacian eigenvectors was pointed out in [1], and the way the second model is derived from the first resembles the approach proposed in [1] as well.

2. The introduction and title of the paper emphasize improved global performance, but this is not explored in depth throughout the rest of the paper. A more convincing theoretical argument explaining why the proposed model enhances "global expressivity" would be beneficial. Additionally, synthetic experiments demonstrating that the model outperforms others in learning global properties of graphs would strengthen the claims. Lastly, a brief recap of the types of global information that can be inferred from Laplacian eigenvalues and eigenvectors would provide useful context and support the discussion.

3. The theory section could be more cohesive. The paper introduces a first model, notes its likely instability, and then replaces it with a second model that is provably stable but less expressive. All experiments are then performed on the second model. However, the discussion regarding expressivity primarily focuses on the first model, leaving the expressivity of the second under explored despite being the one used in practice. Additionally, the authors define stability in one way but then prove the stability of their model using a slightly different notion. This could benefit from clearer alignment and explanation.

4. The paper [3] provides a similar analysis, outlining expressivity bounds of previous methods using laplacian eigenvectors and proposing a new architecture. A comparison between the results of that work and the current paper could offer valuable insights and strengthen the positioning of this paper’s contributions.

5. While the results on the QM9 benchmark are promising, it would be helpful to include a comparison with other methods that also use Laplacian eigenvectors on this dataset. 



[1]  Yinan Huang, William Lu, Joshua Robinson, Yu Yang, Muhan Zhang, Stefanie Jegelka, and Pan Li. On the stability of expressive
positional encodings for graph neural networks. arXiv preprint arXiv:2310.02579, 2023.

[2] Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv preprint arXiv:2202.13013, 2022.

[3] Bohang Zhang, Lingxiao Zhao, and Haggai Maron. On the expressive power of spectral invariant graph neural networks. arXiv preprint arXiv:2406.04336, 2024.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: 1. Please begin by clarifying the weaknesses section.
2. Could the authors provide an empirical comparison of training costs with the most competitive baselines?
soundness: 3
strengths: 1. The proposed OGE-Aug method is theoretically robust, demonstrating strong expressiveness and stability. The underlying motivation is both novel and compelling.
2.  Empirical experiments indicate that OGE-Aug performs competitively and holds promise for real-world applications.
3. The theoretical contributions of this paper are sufficient, and the proofs appear sound.
summary: This paper improves GNNs by incorporating Laplacian eigenvectors to capture global graph properties, addressing limitations in local message-passing approaches.  The proposed method uses learnable O(p)-invariant representations for each Laplacian eigenspace of dimension p and handles close eigenvalues in a smooth fashion, enhancing robustness and expressivity. Experiments show competitive performance, especially in capturing global graph characteristics.
weaknesses: 1. The proposed OGE-Aug method is intricate, highly complex, and challenging to implement. In this paper, the authors present a simplified version using a Cartesian tensor-based point cloud network, which introduces a gap between the theoretical framework and practical implementation.
2. This paper's writing is rough and difficult to read and follow. First, I recommend that the authors adopt the notation guidelines suggested by the ICLR template. In the current version, symbols such as V are used interchangeably to represent different elements, like sets and matrices, which makes the paper challenging to interpret. Second, the implementation of OGE-Aug should be presented with more detail, ideally including a pseudocode. 
3. There is no available code to reproduce the results or gain a deeper understanding of the method’s details.
4. In the experiments, the primary baselines are Laplacian-based embedding methods, but some recent state-of-the-art methods, such as Exphormer [1] on the PCQM-Contact dataset, are missing.
5. While the experiments include four different datasets or benchmarks, incorporating additional datasets or widely-used benchmarks, such as the OGB benchmark (e.g., ogbg-molhiv, ogbg-molpcba), could further strengthen the evaluation.

[1] Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, Ali Kemal Sinop. Proceedings of the 40th International Conference on Machine Learning, PMLR 202:31613-31632, 2023.

Meta-review: This paper addresses the problem of how to incorporate Laplacian eigenvectors into message-passing neural networks to maximize expressivity while maintaining invariance/equivariance. The authors propose two main architectures to achieve this based on positional encodings from Laplacian eigenvectors. They improve the stability by incorporating a smooth function for "soft splitting" the eigenvectors. Theoretical analysis and extensive experiments demonstrate the effectiveness of the proposed positional encoder.

The reviews for this paper were borderline. The main weaknesses are the numerical evaluation, scalability, and little novelty since the reviewers 7pZy and 9aT4 claim that there are several similar methods in the literature.

Decision: Reject