Spatio-Spectral Graph Neural Networks
Authors: Simon Geisler
Arthur Kosmala
Daniel Herbst
Stephan Günnemann
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Neural Networks
long-range interactions
Primary area: graph_neural_networks
TL;DR: We propose Spatio-Spectral Graph Neural Networks (S^2GNNs) that have a global receptive field, vanquish over-squashing and deliver strong empirical results on small and large graphs.

Abstract: Spatial Message Passing Graph Neural Networks (MPGNNs) are widely used for learning on graph-structured data. However, key limitations of *ℓ*-step MPGNNs are that their "receptive field" is typically limited to the *ℓ*-hop neighborhood of a node and that information exchange between distant nodes is limited by over-squashing. Motivated by these limitations, we propose *Spatio-Spectral Graph Neural Networks (S²GNNs)* – a new modeling paradigm for Graph Neural Networks (GNNs) that synergistically combines spatially and spectrally parametrized graph filters. Parameterizing filters partially in the frequency domain enables global yet efficient information propagation. We show that S²GNNs vanquish over-squashing and yield strictly tighter approximation-theoretic error bounds than MPGNNs. Further, rethinking graph convolutions at a fundamental level unlocks new design spaces. For example, S²GNNs allow for free positional encodings that make them strictly more expressive than the 1-Weisfeiler-Leman (WL) test. Moreover, to obtain general-purpose S²GNNs, we propose spectrally parametrized filters for directed graphs. S²GNNs outperform spatial MPGNNs, graph transformers, and graph rewirings, e.g., on the peptide long-range benchmark tasks, and are competitive with state-of-the-art sequence modeling. On a 40 GB GPU, S²GNNs scale to millions of nodes.

Spatio-Spectral Graph Neural Networks
Simon Geisleri, Arthur Kosmala', Daniel Herbst, and Stephan Günneeaan
Department of Computer Science Munich Data Science Institute Technical University of Munich {s. geisler a. a.kosmala, d. hererbs,, s. ..guennemann) Sttnr
Abstract
Spatial Message Passing Graph Neural Networks (MPGNNs) are widely used for learning on graph-structured data. However, key limitations of f-step MPGNNs are that their "receptive field" typically limited to the ε-hop neighborhood node and that information exchange between distant nodes is limited by over- squashing. Motivated by these limitations, we propose Spatio-Spectred Graph Neural Networks (S' GNNs) new modeling paradigm for Graph Neural Net- works (GNNs) that synergistically combines spatially and spectrally parametrized graph filters. Parameterizing filters partially in the frequency domain enables global yet efficient information propagation. We show that S2GNNs vanquish over-squashing and yield strictly tighter approximation-theoretie than MPGNNs. Further, rethinking graph convolutions at a fundamental level unlocks new design spaces. For example, S*GNNs allow for free positional codings that make them strictly more expressive than the 1- I-Weisfeiler-Lenn Leman (WL) test. Moreover, obtain general-purpose S we propose spectrally parametrized filters for directed graphs. GN outperform spatial MPGNNs, graph transformers, and graph rewirings, e.g., on the peptide long-range bench- mark tasks, and are competitive with state-of-the-arr sequence modeling. On a 40 GB GPU, GNNN scale millions of nodes.
error bounds
Introduction
Spatial Message-Passingg Graph Neural Networks (MPGNNs) ush- ered various recent breakthroughs. For example, MPGNNs are able to predict the weather with unprecedented precision (Lam et al.) 2023), can be composed as foundation model for rich set tasks on knowledge graphs (Galkin et al. (023), and key component in the discovery of millions of Alggnneraeed crystal structures (Mer- chant et al. 2023). Despite this success, MPGNNs produce node- level signals solely considering limited-size neighborhoods, effec- tively bounding their expressivity. Even with large number of message-passing steps, MPGNNs are limited in their capability of propagating information to distant nodes due over-squashing. As evident by the success of global models like transformers (Vaswani al. 2017), modeling long-range interactions can be pivotal and important step towards foundation models that understand graphs.
Spocial
Spectral filter
Messoro pooslag
spotial Rictane POAA
estodi
Spectcal
cutoff
llter
Donasin:
Spatial
Preqeracy
We propose Spatio-Spectrad Graph Neural Networks (Sa GNNs), a new modeling paradigm for tackling the aforementioned limita-
Figure SºGNN principle.
tions, that synergistically combine message passing with spectral filters, explicitly parametrized in the spectral domain. Spectral filters are virtually ignored by prior work but go beyond stacks of passage-passing layers polynomial parametrizations. Due message passing's 's finite number
38th Conference on Neural Information Processing Systems (NcurIPS 2024).
t equal contribution.

---

of propagation steps, it comes with a distance cutoff Peut (# hops, see Fig. D.. Conversely, spectral filters act globally (pmax), even on truncated frequency spectrum Aeut- Truncating the frequency spectrum for spectral filters is required for efficiency, yet message passing has access to the entire spectrum (right plots in Fig. 1). The combination of message passing and spectral filters provably leverages the strengths of each parametrization. Utilizing this combination, S*GNN generalize the concept of "virtual nodes" and distill many important properties of hierarchical message-passing schemes, graph-rewirings, and pooling into a single GNN (see Fig. 3). Outside of GNNs, a similar composition is at the core of some State Space Models (SSM) models (Poli et al. (023), that deliver transformer-Iie likee properties with superior scalability on sequences as do S on graphs.
Our
analysis of GNN (S 3.1 validates their capability for modeling long-range interactions. We prove in S 3.1.I that combining spectral and spatial filters alleviates the over-squashing phe- nomenon (Alon & Yahav, 2020] Di Giovanni et al. 2023a b), a necessity for effective information- exchange among distant nodes. Our approximation
analysis goes one step further and proves strictly tighter error bounds in terms of approximation of the target idealized GNN ( 3.1.2.
Design space of S (S 3.2). Except for initial works like (Bruna et al., 2014) and in con- trast to spatial MPGNNs, the de- sign decisions for spectral filters are virtually unexplored and so is their composition. The
Synergistic compasition
1
Choose Smente....
spectral filters & sputial message passing
Vanquishes over-sppushing $ $3.11
Spottal message passing
Superier approximation capabilitiss (5 3.1.122
Spectral Elter
Spatial message passing (see literature)
Design Space
Spectral filter parametrization
-pectral-omminn MLP (S..
Spectral filter for directed graphs
PB
novel aspects of S2GNN's de- sign space include the spectral filter parametrization (8 3.2.I). We propose the first permutation- sudivarraace-preservivn
Dual use of partial Figendccompostton (EVD):
EVDaL.
free-of-coon Positional Encodings (PE) B (3224
x
A
Figure 2: SAGNN framework with adjacency matrix A, node features X, and Laplacian L (function of A).
neural network in the spectral domain @$ 3.2.2) and generalize spectral filters to directed graphs (S 3.2.3). 'he dual use of the partial eigendecomposition, required for spec-
tral filters, allows us to propose "free-of-cost" positional encodings I 3.2.4. that are permutation- equivariant, stable, and increase expressivity strictly beyond the 1 w-Weisfeiler-Lent Leman (WL) test.
S'GNNs are effective and practical. We empirically verify the shortcomings of MPGNNs and how SNNN overcome them (S 4). E.g., we set new state-of-the-as on peptides-func (Dwivedi et al., 2022] with = 35% fewer parameters, outperforming MPGNNs and graph transformers. Although sequences are just subdomain of (directed) graphs, we also study how SºGNNs compare to spe- cialized sequence models like transformers (Vaswani et al. 2017) or Hyena (Poli et al. 2023). We find that SNGNNs are highly competitive even though they operate (un-/directed graphs). Last, the runtime and space complexity of S*GNNS equivalent to MPGNNs and, with vanilla full-graph training, GNNN can handle millions of nodes with 40 GB GPU.
much more general domain
2 Background
We study graphs ((A, X) with adjacency matrix A E (0, 1) (or A E 1220 if weighted), node features X E Raxd and edge count m. A is symmetric for undirected graphs and, thus, has oigendecomposition X, V = EVD((A) (A) with eigenvalues X E IR" and eigenvectors V E Raxn, A VAVT using A diag( A). Instead of A, we decompose the Laplacian L = I- AD 1/2 with diagonal degree matrix D diag(Al) (A1). since its ordered cigenvalues 0 X₁ S S
An < 2 are similar to frequencies (e.g.. low cigenvalues relate to low frequencies. see Fig. Likewise, one could use, e.g., L I D A or more general variants (Yang et al.) 2023); however, we focus our explanations on the most common choice L == I D AD 7/2 We choose the matrix of eigenvectors V E R==x to be orthogonal VVT I. We refer V as the Fourier basis of the graph, with Graph Fourier Transformation (GFT) X V x and its inverse X= VX. To provide an overview, Table 5 lists the symbols used in this work.
Spectral graph filters. Many GNNs implement graph convolution, where node signal X E RRax convolved g *g X for every d with scalar filter g e R=. The graph convolution (Hammond et al. 20 is defined in the spectral domain as g &G X = V(V g] C XX), with element- wise product @ and broadcast of V g to match shapes. Instead of spatial g. spectral graph filters
parametrize 9 [0, 2] I explicitly and yield V "gg == (A) E R" as function of the eigenvalues.
2

---

Message Passing Graph Neural Networks (MPGNNs) cir- cumvent the EVD via polynomial (A)),
Node
Magaitule
Pomner coctician
Σド= X, since vIΣ}=o "i diag(A))VV] X - 7/3 L'X. In practice, many MPGNNs use p 1: H (70 + L H(-11) with H (0) X, and stack 1 S 1 S layers interleaved with node-wist transformations and activations We refer to Bal- cilar et al. 202Tb) for similar interpretations of MPGNNs like
color
Gather
Scatter @ Apply
frequency
GAT (Veličković et al. 2018) GIN (Xu et al. 2019)
3 Method
Ace
SNGNNs symbiotically pair spatial Spatial (H A) MPGNNs and Spectral (ovetraa(HH"))) (I V. A) filters, using partial eigendecomposition. Even though the spectral filter operates truncated cigendecomposition (spectrally bounded), it spatially unbounded. Conversely, spatial MPGNNs are spatially bounded yet spectrally unbounded (see Fig. 1).
Figure 3: Message-passing inter- pretation of (A) Ø [X) (spectral filter): via the Fourier efficients they may exchange infor- mation globally and allow intra- and inter-cluster message pass- ing. Edge width/color denotes the magnitude/sign of V.
spectrally bounded filter sensible for modeling global pair-wise interactions, considering its message-passing in- terpretation of Fig. 3 Conceptually, a spectral filter consists of three steps: ① Gather: The multiplication of the node signal with the cigenvectors v, X (GFT) is a weighted and signed aggregation over all nodes; @ Apply: the "Fourier co- efficients" are weighted; and @ Scatter broadcasts the signal v. X back to the nodes (inverse GFT). The first eigenvector (here for L D A) acts like "virtual node" (Gilmer et al. 2017) (see also | E}. That is, it calculates the average embedding and then distributes this information, potentially interlayered with neural networks. Importantly, the other eigenvectors effectively allow messages to be passed within or between clusters. As we show for exemplary graphs in Fig. 4 low Trequencieseeigevvaless capture coarse structures, while high(er) frequencies/eigenaales capture details. For example, the second eigenvector in Fig. 4b contrasts the inner with the outer rectangle, while the third eigenspace models both symmetries up/down and left/right. In conclusion, SCGNNs augment spatial message-pasee with a graph- adaptive hierarehy (spectral filter). Thus,
S'GNNs distill many important properties of hierarchical message-passing schemes (Bod- nar et al., 2021), graph-rewirings (Di Gio- vanni et al. 2023a), pooling (Lee et al. 2019) etc. See J.1 for more examples.
(b)
Figure 4: Exemplary (lowest) eigenspaces.
S2GNN's composition. We study an additive combination for its simpler approximation theoretic interpretation (S 3.1.2), or ( an arbitrary sequence of filters due to its flexibility. In both cases, residual connections may desirable (sce
H Spectral (H V, Spatial (H (H (1-);); A) H ( (h o on (C-1) o ... (1) (H ())
(I)
with G) {Spectral, Spatial}
(2)
Spectral Filter. The building block that turns a spatial MPGNN into an SºGNN is the spectral filter:
Spectral (H-()) V, = v
v 0 (A)
[VT (0) (H--1)))
(3)
with a point-wise transformation 1 RRnxdd 2) + Rax a learnable spectral filter (0 (A)
( parameterized element-wise as 060²) (2),,) n,,- g.0h (Au: (.) (see 3.2. and truncated
V E Rank A R Due to the combination message passing with spectral filters, S'GNNs' hy- pothesis class goes beyond (finite-order) polynomials of the Laplacian L (or stacks message passing layers), unlocking a larger class filters. In Algo. 1 we provide pseudo code for S'GNNs (Eq.
Truncated spectrum. We omit extra notation for the truncated eigendecompositon EVD(L, k)
since it is equivalent to define )(A,) = for j > However, truncating after the k-th eigen- vector requires care with the last eigenspance to maintain permutation equivariance. Due to the

---

ambiguity of eigenvectors in the presence of repeated eigenvalues, we must ensure that we only include eigenspaces their entirety. That is. we only include 1, I lo A X3 # AR+13. Thus, Spectral( (I-))) EVD(( k)) is permutation equivariant nonetheless. We defer all proofs to H
Theorem 1. Spectral H;:)); (VD(L, of Fq.. 3 is equivariant to all n. permutation matrices P E P: Spectral (PH 1 EVD(PLP k)) = - (Spectra(HH EVD(L k))..
Complementary high-resolution filters. Our Spectral filters are highly discriminative between the frequencies and, e.g.. can readily access a single eigenspace. Yet, for efficiency, we limit the spectral filter a specific frequency band. Due to the combination with message passing, this choice of band does not decide on, say, low-pass behavior; it solely determines where to increase the spectral selec- tivity. While S*GNN with subsequent guarantees adapt to domain-specific choices for the spectral filter's 's frequency band, a sensible default is to focus on the low frequencies. The two main reasons for this are (see J.3 for an extensive list): (1) Low frequencies model the smoothest global signals w.r.t the graph structure (see Fig. 3 & 4 (2) Under a relative perturbation model (perturbation budget proportional to degree), stability implies cannegral-Lipschizness (3C > 0: [Ado/dx| < C),,
i.e. the filter can vary strongly around zero but must level out for large À (see Gama et al. (0200).
3.1 Theoretical Analysis
1.0
Accuracy
We show that how SCGNNs alleviate oversquashing in 3.1.1 Next, makes the cerooiimatiin-thhorette advantages precise.
a.5
GCN
$ 3.1.2
Spoc.
0.0
3.1.1 SPGNNs Vanquish Over-Squashing
Source to target distance
Figure 5: Spectral filters do not exhibit over- squashing Path" graphs (Di Gio- vanni et al. (023a).
Alon & Yahay (2020) pointed out that MPGNNs must pass informa- tion through bottlenecks that connect different communities using fixed- size embedding vectors. Topping et al. (022) and Di Giovanni et al.
"Clique
(2023)) formalize this via an L -norm Jacobian sensitivity analysis: [ob;"Jan"" [1 models the output's 's h
change if altering input h. ())
MPGNNS' Jacobian sensitivity typically decays O (-x) with node distance r if the number
of walks between the two nodes is small. See S F for results of Di Giovanni et al. (2023a).
GNNN not prone such exponential sensitivity decay due to their global message scheme. We formalize this in Theorem 2,, refer to Fig. 4 4]for intuition and Fig. 5 for empirical verification. All theoretical guarantees hold if 0 exists such that So I.
Theorem 2. An l-layer S GNN can be parametrized s.f. output hy has uniformly lower- bounded Jacobian sensitivity on a connected graph: | /ab 11 2 C.d/m with rows h h! of ()), ( for nodes u, U e 9, a marameter-depente
Cg, network width d and edge count m.
In contrast to Di Giovanni et al. 2023a). we prove a lower bound for SP SNGNNs, guaranteeing a min- imum "influence" for any u on e. This is true since S'GNNs contain a virtual node as special case with 93 (A) = [oz- with 5 denoting the indicator function of a set S (see also S E}. However, we find that virtual node is insufficient for some long-range tasks, including our long-range clustering (LR-CLUSTER) Fig. 10b Hence, the exponential sensitivity decay of spatial MPGNNs only shows their inadequacy in long-range settings. Proving its absence is not sufficient to quantify long-range modeling capabilities, noting that the lower bound is not tight for S²GNNs on many graphs. We close this gap with our subsequent analysis rooted in polynomial approximation theory.
3.1.2 Approximation Theory: Superior Error Bounds Despite Spectral Cutoff
To demonstrate how SºGNNs can express a more general hypothesis class than MPGNNs, we study how well an "idcalized" GNN (IGNN) can be approximated. Each IGNN layer I can express convo- lution operators g of any spectral form (()) [0.2] + J.. We approximate IGNNs with S²GNNs from Eq. 1 with spectral filter as in Eq. 3 and spatial part parametrized by polynomial. While we assume here that the SºGNN spectral filter is bandlimited and universal approximator on the interval [0, Amar], the findings generalize to, e.g., high-pass pass interval. In the main body, we focus on the key insights for architectures without nonlinear activations. Wang & Zhang (2022) prove that even linear IGNNs can produce any one-dimensional output under certain regularity assumptions on the graph and input signal. Thus, we solely need to consider a single layer. In S H.4 we cover the generic setting including nonlinearities, where multiple layers are helpful.

---

Locality relates to spectral smoothness. The locality of the truefideal filter g is related to the smoothness of its Fourier transform g. For instance, if g is low-order polynomial of L, is localized to few-hop neighborhood, and g is regularized to vary slowly FFgg. 6a w/o discontinuity). The other extreme is discontinuous spectral filter 9. such as the en- tirely non-local virtual node filter, (o) (discontinuity in Fig. 6a details in S E). This viewpoint of spectral smoothness illuminates the complements spatial analyses in the over-squashing picture. It informs a lower bound on the error, which shows that spatial message passing, i.e, order-p polynomial graph filters Iy, with p coefficients "pp E Re+1, can converge exceedingly slowly - slower than any inverse root (!) of p- discontinuous ground truth in the Frobenius-induce operator norm:
Raw
Tre
Spa. (p
Spec. (k-
(p R
Filter sf
Sigma
Eigevvauue À
Node
(a) Spectral domain
(b) Spatial domain
Figure 6: S filter perfectly approximates true filter (a) with discontinuity at = O, while polynomial ("Spa.") and spectral ("Spec.") alone do not. (b) shows responses a path graph.
limitations of finite-hop message passing from angle that
Theorem 3. Let 9 be a discontinuous spectral filter. For any approximating sequence (DT)) of polynomial filters, an adversarial sequence (Gp) of input graphs exists such that
11(TT -9) *Gp X
|
fa E Ryo:
O (p-a)
sup
Og X XEER O
|
Superior SºGNN error bound. A spatio-spectral convolution wins over a purely spatial filter when the sharpest irregularities of the ground truth ğ are within reach of its expressive spectral part. The spatial part, which can "focus" on learning the remaining, smoother part outside of this window, now needs much fewer hops to give faithful approximation. We illustrate this principle in Fig. 6 where we approximate an additive combination of an order-three polynomial filter with discontinuous low- pass. Only the S filter is faithfully approximating this filter. Formally, we find:
Theorem 4. Assume øl (1 is r-limes continuously differentiable on [Neur 2). and a bound d'
(ū, dem)) 2 O such that dxr 3(A) I Kr(r dew) AA E [eeu 2). An approximating S'GNN sequence with parameters (0p,7p) 1p) PEN exists such that, for arbitrary graph sequences (Go)peN.
(0y; + 90; - g) *g, X11e =0 -0 (Krr (o.N))ppp)p))
sup 0 E3 Gp
|
with scaling constant that depends only on not on (Gp)peN.
The above bound extends to purely spatial convolutions terms of K2 K_ 0) if is r-times contin- uously differentiable
the full interval [0, 2]. The S'GNN bound of Theorem 4 is then still strietly tighter if K,( (ğ. Aqu)) < Kg (g.0 0). In particular, taking the limit K1 (g.0) + oo towards discontinu- ity makes the purely spatial upper bound arbitrarily loose, whereas benign filter might still admit small Ki (g. Aeu)) for some Acut > 0. Theorem 3 sugggest that this is not an artifact of a loose upper bound but that there is inherent difficulty in approximating unsmooth filters with polynomials.
We conclude the analysis by instantiating the bounds: assuming 9 is ity reasons (see Gama et al. 22020) and the paragraph before & 3.1.1b yields K₁ (g. Acur) C/ whereas for the electrostatics example åo in G we find upper bounds K,, (G. Acut) = rl/x(n+*) In both cases, the pure spatial bound diverges smoothness around O remains unconstrained.
Liiggral-Lipschitz for stabil-
3.2 Design Space
As shown in Fig. 2 we identify three major, yet unexplored, directions S*GNNs design space. In 1.2. we discuss how parametrize the spectral filter. in2.3.2.2 we propose the first neural net- work for the spectral domain. That is, we allow transformations and non-linearities in the "Fourier" domain. In $ 3.2.3. are the first to instantiate spectral filters for directed graphs. Additionally,
5

---

due to the availability of the partial eigendecomposition, positional encodings may dual use them to improve epxressivity at negligible cost. In 3.2.4, we propose the first permutation equivariant, stable and efficient positional encodings that provably admit an expressivity beyond 1 1-WI.. [ pro- vides further details and considerations, like some remarks on batching ( J.7.. For the (sub-) design space of spatial message passing (You et al. 2020), we refer to its rich literature.
3.2.1 Parametrizing Spectral Filters
Be(A) [Sunestrng (A) @ (indow(A)
Gaussian
(Thlaey)
For spectral filter function (A) of Eq. 3 we learn channel- wise linear combination of translated Gaussian basis functions (see "Gaussian smearing" used by |Shüüt al. (2017). ), as depicted in This choice (I) may represent any possible (A) with suf- licient resolution (assumption in [S 3.1.2: (2) avoids overfitting to- wards numerical inaccuracies of the eigenvalue calculation: (3) lim- its the discrimination of almost repeated eigenvalues and, in turn.
Sancaring
Window
Fig. 7
10
Avas
Acut
Figure 7: go (A) with
Smearing(A) (A) : [0,
R linear map W e Rxxd (v = (W)). and fixed win- dow function Window(A).
should yield stability (similar to 3.2.4. Strategies to cope with a variable Aeut and (e-g., using attention similar to SpecFormer (Bo)
et al. 2023a)) did usually not yield superior experimental results.
Window. We multiply the learned combinations of Gaussians by envelope function (we choose a Tukey window) that decays smoothly to zero around cutoff' Xeur- This counteracts the so-called "Gibbs phenomenon" (aka "ringing")) as visualized for a path graph/sequence of 100 nodes in Fig. 8) trying to approximate a spatially-disconiimuus target signal using an ideal low-pass range of frequency components results in an overshooting oscillatory behavior near the spatial discontinuity. Dampening the frequencies near Acu by smooth envelope/window function alleviates this behavior. We note that the learned filter may, in principle, overrule the windowing at the cost of higher weight decay penalty. Seel Algo. for Oo (A)'s 's algorithmic description.
Depth-wise separable convolution (Sifre) 2014 Howard al. 2017]: Applying different filters for each dimension is computa- tionally convenient for spectral filters. While "full" convolutions are also possible, we find that such a construction is more prone to over-fitting In practice, we even use parameter sharing and apply fewer filters than dimensions to counteract over-fitting We argue that sharing filters among dimensions is similar to the heads in a transformer (Vaswani et al. 2017).
L.
Signal x
M
0.5
Window
w/
0.0
w/o
Node x2
Figure 8: Ringing of ideal low
Feature transformations f8 As sketched in Fig. 3 & 4 all nodes
pass filter on path graph.
participate in the global data transfer. While this global peesssge--assiing scheme is graph- aapp-vee it does not adjust to the inputs. For adaptivity, we typically consider non-linear feature transforma- tions f((-1) (1-))), like gating mechanism ((
(1 @ (H (1-) w((1) + ibb)) with element-wiis, multiplication O. SiLU function a', learnable weight W, and bias b. A linear transformation fø (H))- (1111) (!)) is another interesting case since we may first apply the GFT and then the transformation: (VT T ((--))W()) Next, extend this linear transformation to a neural network in the spectral domain by adding multiple transformations and nonlincarities.
3.2.2 Neural Network for the Spectral Domain
Applying neural network 8{ in the spectral domain is highly desirable due to its negligible com- putational cost if A < n. Moreover, 8ç allows the spectral filter to become data-dependent and may mix between channels. Data-dependent filtering is one of the properties that is hypothesized to make transformers powerful Fu et al. (2023), We propose the first neural network for the spectral domain that is designed to preserve permutation equivariance.
of graph filters sc -
(!)
R
(1) Spectral (H--"..VAA. = V (A)
о [V ( ((H(()))))
(4)
We achieve permutation equivariance via sign equivariance sc O X)- -S sx)) VS
{-1, 1) ( combined with permutation equivariance sc PX) = Ps((X), P E Pa. where Pa is the set of all x l permutation matrices. Specifically, we stack linear mappings
W, E ( ( (without bias) with a gated nonlinearity Φ = H O [ W. + b.D. with
sigmoid a, column-wise norm m, || |]. and learnable W. E nd x as well as b, E Rd

---

3.2.3 Directed Graphs
Directed graphs are an important topic that did not discuss so far. For S' to generalize the capabilities of non-local sequence models like transformers (Vaswani et al. 2017) or SSMs (Poli) et [ Gu & Dao 2023) it is vital to support direction, e.g., for distinguishing source/beginning and sink/end. However, all discussion before assumed the existence of the eigenvalue decomposition of L. This was the case for symmetric L; however, for directed graphs, L may be asymmetric.
To guarantee L is diagonalizable with real eigenvalues, we use the Magnetic Laplacian (Forman [993] SSubbin 1994 De Verdière 2013) which is Hermitian and models direction in the complex
domain: Lg
expli2nq(A A '] with symmetrized adjacency/degrees .. potential q E [0, 2T... element wise exponential exp, and imaginary unit 1² = 1. While
D A,
A.
other parametrizations of a Hermitian matrix are also possible, with A {0, 1) and appropriate choice of 9, L {0. 10.1) + Cax is injective. In other words, every possible asymmetric A maps to exactly one L and, thus, this representation is lossless. Moreover, for sufficiently small potential 4, the order of eigenvalues is well-behaved (Furutani et al., 2020). In contrast to Koke & Cremers (2024), a Hermitian parametrization of spectral filters does not require a dedicated propagation for forward and backward information flow. For simplicity we choose < 1/naus with maximal number of nodes 7max (with binary A). This choice ensures that the first eigenvector suffices to obtain, c.g., the topological sorts of Directed Acyclic Graph (DAG). Due to the real cigenvalues of Hermitian matrix, the presented content generalizes with minor adjustments. Most notably, we use feature transformation f/" "R= B Caxd")) and map back into the real
domain after the spectral convolution. We give more implementation details in S J.6 and provide additional background on directed graphs in C
3.2.4 Efficient Yet Stable and Expressive Positional Encodings
(a)
The availability of the partial eigendecomposition allows for their dual use for posi- tional encodings negligible cost. Motivated by this, we propose the first efficient (Kkm) and (fully) permutation equivariant spectral Positional Encodings PE that provably increase the expressivity strictly beyond the 1-Weisfeiler-Lent
(1-WL) (b)
test (Xu et al. [019 Morris et al. 2019). In contrast to the I Laplacian encodings of Dwivedi & Bresson (2021), PF do not require augmenting eigenvectors w.r.t.
their sign and maintain permutation equivariance also in the presence of repeated
eigenvalues. In comparison Huang al. (2024), our PE come with drastically lower computational cost and have no learnable parameters, Due to the absence of learnable parameters, we need calculate our PE only once.
(c)
We construct our k-dimensional positional encodings PE(V, A) E R as
(d)
PE(V, A)
(5)
with concatenation and binary adjacency A E 10,10" We use a Radial
Basis Function (RBF) filter with normalization around each eigenvalue (A)
softmax((A; (AA,-A)(AA,A))///aa with small width a R2o. This parametrization not only permutation equivariant but also stable according to the subsequent def-
(e)
inition via the Hölder continuity. Note that C depends on the eigengap between 1/ (/(x)11>x)) at the frequency cutoff (for exact constant C see proof in S H.5).
Figure 9: PE discriminates the depicted
Definition (Stable PE). HHang et al. 2024) A PE method PE : R x R2* Baxk is called stable, if there exist constants c, C > O, such that for any Laplacian
degree-regular graphs, except for (a) vs. (c).
L, L', and P, = arg minp p L PL' ||F
|PE(EVD(L) - P. PEVD SC.LIPPPP...
(6)
Theorem 5. The Positional Encodings PE in Eg. Sare stable according to Definition
Next to their stability, our PE can discriminate certain degree-regular graphs (e.g., Fig. 9) Since degree-regular graphs cannot be distinguished by 1-WL, our PE makes the equipped GNN (as ex- pressive as I-WL) strictly more expressive than 1-WL. See g 1 for continued expressivity analyses.
Theorem 6. S are strictly more expressive than I-WL with the PE of Eg.
7

---

4 Empirical Results
With state-of-the-an performance on the peptides-fums task of the long-range benchmark (Dwivedi et al. 2022). plus strong results further benchmarks, demonstrate that S' a GCN paired with spectral filters, is highly capable of modeling long-range interactions ($ 4.1). We assess SAGNNs' long sequence performance ($ 4.2) (mechanistic in-context learning) and show that S'GCN, a graph machine learning method, can achieve competitive results to state-of-the-art se- quence models, including H3, Hyena, and transformers. We exemplify S*GNNs' practicality and competitiveness at scale on large-scale benchmarks ($ 4.3) like TPUGraphs (Phothilimthana et al. 2023). PCQM4Mv2 (Hu al., 2021), and Open Graph Benchmark (OGB) Products (Hu et al. 2020 Further, in M.8] we report state-of-the-art performance on the heterophilic ar ariiv-year (Lim
ct al.
202T and,in [S M.4] we study combinations of spatial and spectral filters beyond E.. 1
Setup. We pair different MPGNNs with spectral filters and name the composition S S'<base>, For example, a GNN with GAT base will be called S? We typically perform 3 to 10 random reruns and report the mean +: standard deviation. The experiments of [S 4.1 require <1 GB (e.g.
Nvidia GTX 1080Ti); for the experiments in 4.2 &4.33 4.3 we use a 40 GB AT0O. We usually optimize weights with Adam W (Loshchilov & Hutter (019) and cosine annealing scheduler (Loshchilov & Hutter 2017). We use early stopping based on the validation loss/score. See (S M for more details and ht Aatpps:/// http:p://wwwwwccc c8 cit tum. de/ //dmm/m/////// /2gnn for code as well as supplementary material.
4.1 Long-Range Interactions
Finding (I): SCGCN outperforms state-of-the-art graph transformers, MPGNNs, and graph rewirings on the peptides-fune long-range benchmarks (Dwivedi al., 2022) by a substantial mar- gin. Simultaneously, we remain approximately 35% below the 500k parameter threshold and. On peptides-struct strrid we are only outperformed by NBA-GIN (Park et al., 2023). We extend the best con- figuration for a GCN Tönshoff et al. (2023) (see GCN in Table lower the number of message passing steps from six to three, and interleave spatial and spectral filters (Eq. 2) with Acut- = 0.7.
Clustering, given a single seed node per cluster, measures the ability (1) to spread information within the cluster and (2) discriminate between the clusters. We complement the semi- supervised task CLUSTER from Dwivedi eet al.] (2023) with (our) LR- AR-CLUSTER dataset, a scaled-up version with long- range interactions (1). We closely follow Dwivedi et al.] (2023), but instead of us- ing graphs sampled from Stochastic Block Models (SBMs), we sample coordinates from Gaussian Mixture Model (GMM) and then connect nearby nodes. CLUSTER has 117 nodes average, while ours has 896. LR-CLUSTER has an average diame- ter of x 33 and often contain hub nodes that cause over-squashing. For full details on the dataset construction, see $ M.6
Dataset contribution:
Table 1: Long-range benchmark. Our SNNNN uses
xs 35% fewer parameters than the other models. AP is Peptides-fune's and MAE peptides-struct target met- ric. The best/second best is bold/underlined.
Model
peptides-fune (1)
peplides-struet (1)
Transformer
TIGE (Choo et al 20044
MGT-WFE Ngod ena 2023
0.6817 :: 0.0064
0.0679 = 0.0044
0.2453 1: 0.0025
0.2485 +: 0.0015
G.M PM [F2
0.6921 + 0 0004
0.2476 0.0015
Gruph VT [1
0.69112 1 0 0075
0,2410 0.0011
GRIT
0.6088
0.2460 0-0.0012
GPS- GPS-11D55 1r10
0,7156 0.0068
0.2457
meniring: DEN
(Gulttendgee et al. 2013
0.7150 + 0.0044
0.2536 0.0015
State Space Mindeis Gragt Mamba
[Behrouz & Hashomi 2021
0,7071 : 0063
0.2473
0.0025
(sanion Hismeni 2124
0.7133 000111
0.2456 0,0013
PathNNN [xizieer
0.8866 0.0026
0.2545
CIN++ (Grusd 2t
2iz3
0.6589 1: 0.0177
0,2523 0.0013
NBA.G.N (Pare ararerrd 2023
0,7071 = 006T
0. 0.2424 =: 0010
GCN [Tondkon or 2004
0.6860 : 0060
0.2460 1.660-00.000 0.0007
SPGCA (ours)
0,7275 0 0000
0,2467 0.0019
0.7311 0.0066
0.2447 0.0002
Dataset contribution: Distance regression is task with long-range interactions used in prior work
Geisler et al. 2023 Lim et al., 2023). Here, the regression targets are the shortest path distances to the only root node (in-degree 0). We generate random trees/DAGs with =550 # of nodes on
average (details are in S M.7). The target distances often exceed 30 hops. We evaluate on similarly sized graphs in the training data, i.e., in-distribution (ID) samples, and out-of-distribution (OOD) samples that consist of slightly larger graphs. Details on the dataset construction are in S M.7
Finding (II): spatial MPGNNs are less effective as S²GNNs, for long- range interactions. This is evident for peptides Table I clustering Fig. 10 distance regression Fig. 11 and over-squashing Fig. 12, Specifically, if the task requires long-range interactions beyond the receptive field of MPGNNs, they return crude estimates. F.g., in Fig. 1T] the MPGNN predicts (approx.) constantly 20 for all distances beyond its receptive field roughly the mean in the training data. Moreover,
8

---

1.0
Accuracy
0.8
Vind Vole
Accuracy
50.75
Prediction 44)
Accuracy
hW
MPONN
0.5
20
5
0.0
GaialOCN
0
#
cigenvecttors 3
1
2
4
6 8 10
2. 3 4 56 6
# sppptial MP layers
9 10
Ground truth distance
20
40
50 Number nodes
(a) 4+1 layer MP Spec. (h) w/ vs. w/o Spec.
Figure 11: pred. intervals on OOD DAGs.
90%
Figure 12: Over-sq.:
Figure 10: Results on LR-CLUSTER. Solid lines are w/ dashed lines are w/o our PE ($ 3.2.4.
25-layer GatedGCN
1-layer spec. ID is grey.
A
Vdlin((a(A) (A) V
Vdiaglūa v (A)
Vdiog(āa(A)..
Figure 13: 4 filters on LR-CLUSTER. Large/small entries are yellow/blue, white lines mark clusters.
S'GNNs may converge faster (see Fig. 25 in $ M.6.2) and are more parameter-efficient, as we show on PCQM4My2 (Hu et al. 2021
M.9
Finding (III): virtual nodes are insufficient. We frequently find that including more than a single eigenvector (k >> 1) yields substantial gains. We make this explicit in Fig. 10al where append single spectral layer and sweep over the number eigenvectors k. We complement these findings with ablation for the frequency cutoff Aca peptides-func in M.5
Finding (IV): our Positional Encodings PE consistently help, when concatenated the node features. While this finding is true throughout our evaluation, the differences are more pronounced certain situations. For example, on LR-CLUSTER in Fig. 10 the PE help with spectral filter and small & or without spectral filter and many message passing steps.
Table 2: 30k token asso- ciative recall.
Finding (V): spectral filters align with clusters, as we illustrate in Fig. 13 for four arbitrary spectral filters learned on LR- LR-CLUSTER. We observe that (a) the spectral filters reflect the true clustering structure, (b) some filters are smooth while others contain details, and (c) they model coarser or finer cluster structures (e.g., first vs. third filter).
Model
Accuracy (t)
Tranforner
Vaswani at al. 2017
00M
10 FIee
Dhe 2022
01324
11
0.084
Poli et 202
4.2 Sequence Modelling: Mechanistic In-Context Learning
SCCN (ours)
0.97 = 0.05
Following the evaluation of Hyena (Poli et al. 2023) and H3 (Fu et al. 2023), we benchmark S²GCN with sequence models on the associa- five recall in-context learning task, stemming from mechanistic inter- pretability (Elhage et al. [2021] Power et al.) 2022] Zhang et al.] 20033]
1.0
Accuracy
0.5
Dir. Undir.
Olsson al.] [022). In associative recall, the model is asked to retrieve the value for a key given in a sequence. For example, in the sequence a, e,O,e, b,z,9,h,24 since it follows z its prior occurrences. We create a sequence/path graph with node for each "token" (separated by "" in the example above) and label the target node with its value. We assess the perfor- mance of S²GCN on graphs that vary in size by almost two orders of magnitude and follow Poli et al. (2023) with a vocabulary of 30 tokens. Moreover, we finetune our SCGCN on up to 30k nodes.
0.0
,z, zz, the target is the value for key z, which is
500
1000
Number of nodes nI
Figure 14: SºGCN solves associative recall for se- quences varying in size by two orders of magni- tude. Grey area marks ID. Finding (VI): our spectral filter for directed are effective and may improve generalization, as we find in Fig. 14 Table 13 of M.7].
Finding (VII): SCGCN a state-of-the-art sequence model, as it performs on par with Hyena and, here, outperforms transformers (Table 2).

---

4.3 Large-Scale Benchmarks
Finding (VIII;; SNNN is practical and scalable. We demonstrate this on the OGB Products graph (2.5 mio. nodes, Table 3) and the (directed) 10 million graphs dataset TPUGraphs (average number of nodes = 10,000. Table 4). In both cases, we find full-graph training (without segment training (Cao et al. )023)) ) using 3 (Dir-) GCN layers interlayered with spectral filters, a reasonable configuration on a GB A A100. However, for OGB Products, we find that batching is superior, presumably because the training nodes are drawn from "small" region of the graph (see K
The cost of partial EVD for each dataset (excluding TPUGraphs and distance regression) is between I to 30 minutes on CPUs. We report the detailed costs of EVD and experi- ments in S M.3
Table 3: OGB Products.
Table 4: Graph rank- ing on TPUGraphs "layout".
Split
Model
Accuracy (f)
F1 (1)
0.866.10.001
0.081110.001
Train
S"GAT
0.902-1-00000
0.472 0.006
Val
00007
Model
Kendall (?)
S"GAT
0.913-100002
0.582.10.014
GCN
60.25
Test
GAT
0.79:=00003
0.347:00004
S'GON
63.62
GAAT
0.811=00007
0,381:20.009
5 Related Work
Combining spatial and spectral filters has recently attracted attention outside of the graph domain in models like Hyena (Poli et al. (202)), Spectral State Space Models (Agarwal et al.) 2024), etc. with different flavors of parametrizing the global/FFT convolution. Nevertheless, the properties of spatial and spectral filter parametrization (e.g., local vs. global) are well-established in classical signal processing. A combination of spectral and spatial filters was applied to (periodic) molecular point clouds (Kosmala et al., 2023). For GNNs, Stachenfeld et al.] (2020) compose a spatial and spectral message passing but do not handle the ambiguity of the eigendecomposition and, thus, do not maintain permutation equivariance. Moreover, [Beaini et al. (202T) use the EVD for localized anisotropic graph filters: Liao et al. (2019) propose approach that combines spatial and spectral convolution via the Lanczos algorithm: and Huang et al. (2022) augment message passing with power iterations. [Behrouz& & Hashemi (2024) apply Mamba-like state space model to graphs via arbitrarily ordering the nodes and, thus, sacrifice permutation equivariance.
Long-range interactions on graphs. Works that model long-range interactions be categorized into: (a) MPGNNs on rewired graphs (Gasteiger et al. 2019a] Gutteridge et al., (003);; (b) higher- order GNNs (Fey et al. 2020 Wollschläger et al. (224) that, e.g., may pass information to distant nodes through hierarchical message passing schemes; and (c) message passing adaptations to facil- itate long-range interactions. For example, Park et al. 2023 propose "non-backtrackingg message passing, Erriia et (2024) adaptively choose the numbers of message passing steps, andg et al.. (2024) use linear RNNs aggregate over each node's 's neighborhoods. While approaches (a-c) can increase the receptive field of GNNs, they are typically still spatially bounded. In contrast, (d) al- ternative architectures, like graph transformers (Ma al. 2023 Dwivedi & Bresson 2021 Kreuzer et al. 2021 Rampášek et al.) 2022] Geisler et al. [023]] Deng et al. (2024) with global attention, may model all possible n n interactions. We provide notes on the limitations of graph transformers with absolute positional encodings in $ D which highlights the importance of capturing the relative rela- tionships between nodes, as SNN do. Morcover, in a secenn/contemporary non-attention model for all pair-wise interactions, Batatia et al. (2024) use resolvent parametrization of matrix functions relying on the LDL factorization of a matrix, but do not characterize their wwwoiiiationntoorettttt properties, over-squashing, expressivity on graphs, nor how to deal with directed graphs.
In B we discuss additional related work w.r.t. expressivity and directed graphs
6 Discussion
We propose SCGNNs, adept at efficiently modeling complex long-range interactions via the syner- gistic composition of spatially and spectrally parametrized filters (8.). We show that S2GNNs share many properties with graph rewirings, pooling, and hierarchical message passing schemes (Fig. 3 & & SºGNNs outperform the aforementioned techniques with a substantial margin on the peptides long-range benchmark $ 4. and we show that S'GNNs are also strong sequence models, per- forming on par outperforming state-of-the-arr like Hyena or H3 in our evaluation d 4.2 Even though we find global graph models, like S²GNNs, more prone to overfitting (see $ K [. for further limitations/impact), moving to global models aligns with the trend for other deep learning domains.
10

---

Acknowledgments and Disclosure of Funding
We want to express our gratitude to Nicholas Gao for his feedback and the discussions about mod- eling choices. Moreover, we thank Leo Schwinn and Tim Beyer for their helpful and on-point feedback and suggestions.
This research was supported by the Helmholtz Association under the joint research school "Munich School for Data Science MUDS". as well as by the Munich Data Science Institute (MDSI) via the Linde/MDSI Doctoral Fellowship program and the MDSI Seed Fund.
References
Naman Agarwal, Daniel Suo, Xinyi Chen, and Elad Hazan. Spectral State Space Models, arXiv, 2024.
Uri Alon and Eran Yahav. On the Bottleneck Graph Neural Networks and its Practical Implica- tions. In International Conference on Learning Representutions, ICLR, 2020.
Muhammet Balcilar, Pierre Héroux, Benoit Gaüzère, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the Limits of Message Passing Graph Neural Networks. In International Conference on Machine Learning, ICML, 2021a.
Muhammet Balcilar, Guillaume Renton, and Pierre Heroux. Analyzing the Expressive Power of Graph Neural Networks in Spectral Perspective. In International Conference on Learning Rep- resentations, ICLR, 2021b.
Ilyes Batatia, Lars Schaaf, Gabor Csanyi, Christoph Ortner, and Felix Faber. Equivariant Matrix Function Neural Networks. In International Conference on Learning Representations, ICLR, 2024.
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzaler Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song, Andrew Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks, arvi 2018
Dominique Beaini, Saro Passaro, Vincent Létourneau, William L. Hamilton, Gabriele Corso, and Pietro Liò. Directional Graph Networks. In International Conference on Machine Learning, ICML, 2021.
Ali Behrouz and Farnoosh Hashemi. Graph Mamba: Towards Learning on Graphs with State Space Models, arXiv, 2024.
Deyu Bo, Chuan Shi, Lele Wang, and Renjie Liao. Specformer: Spectral Graph Neural Networks Meet Transformers. In International Conference Learning Representations, ICLR, 2023a.
Deyu Bo, Xiao Wang, Yang Liu, Yuan Fang, Yawen Li, and Chuan Shi. Survey on Spectral Graph Neural Networks, arXiv, 2023b.
Cristian Bodnar, Cätälina Cangea, and Pietro Liò. Deep Graph Mapper: Seeing Graphs Through the Neural Lens. Frontiers in Big Data, 4:38, 2021.
Xavier Bresson and Thomas Laurent. Residual Gated Graph ConvNets, arXiv, 2018.
Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges. arXiv, 2021.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral Networks and Locally Connected Networks on Graphs, arXiv, 2014.
Chen Cai, Truong Son Hy, Rose Yu, and Yusu Wang. On the Connection Between MPNN and Graph Transformer. In International Conference on Machine Learning, ICML. arXiv, 2023.
11

---

Shaofei Cai, Liang Li, Xinzhe Han, Jiebo Luo, Zheng-Jun Zha, and Qingming Huang. Automatic Aelation-Aware Graph Network Proliferation. In Conference on Computer Vision and Pattern Recognition, CVPR, 2022.
Kaidi Cao. Phitchaya Mangpo Phothilimthana, Sami Abu-EI-Haija, Dustin Zelle, Yanqi Zhou, Charith Mendis, Jure Leskovec, and Bryan Perozzi. Learning Large Graph Property Prediction via Graph Segment Training. In Neural Information Processing Systems, NerulPS, arXiv, 2023.
Zhe Chen, Hao Tan, Tao Wang, Tianrun Shen, Tong Lu, Qiuying Peng, Cheng Cheng, and Yue Qi. Graph Propagation Transformer for Graph Representation Learning. In International Joint Conference on Artificial Intelligence, IJCAI, 2023.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive Universal Generalized PageRank Graph Neural Network. In International Conference on Learning Representations, (ICLRJ. 2021.
Yun Young Choi, Sun Woo Park, Minho Lee, and Youngho Woo. Topology-Informed Graph Trans- former, arXiv, 2024.
Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. FlashAttention: Fast and Meffii-Efficient Exact Attention with IO-Awareness. In Neural Information Processing Sys- tems, NeruPPS, arXiv, 2022.
Yves Colin De Verdière. Magnetic interpretation of the nodal defect on graphs. Analysis & PDE, 6 (5):1235-1242, 2013.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. In Neural Information Processing Systems, NeurlPS, 2017.
Chenhui Deng, Zichao Yue, and Zhiru Zhang. Polynormer: Solymomial-Eppessiiie Graph Trans- former Linear Time. In International Conference on Learning Representations, ICLR, 2024.
Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pictro Liò, and Michael Bronstein. On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology. In International Conference on Machine Learning, ICML, arXiv, 2023a.
Francesco Di Giovanni, Konstantin Rusch, Michael M. Bronstein, Andreea Deac, Mare Lackenby, Siddhartha Mishra, and Petar Veličković. How does over wver-squahhing affect the power of GNNs?, arXiv, 2023b.
Yuhui Ding, Antonio Orvieto, Bobby He, and Thomas Hofmann. Recurrent Distance Filtering for Graph Representation Learning. In International Conference on Machine Learning, ICML, 2024.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenbom, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale. In International Conference on Learning Representations, ICLR, 2021.
Vijay Prakash Dwivedi and Xavier Bresson. A Generalization of Transformer Networks to Graphs. Deep Learning on Graphs at AAAI Conference on Artificial Intelligence, 2021.
Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long Range Graph Benchmark. In Neural Information Processing Sys- tems, NeruPSS. arviv, 2022.
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking Graph Neural Networks. Journal of Machine Learning Research, JMLR, 2023.
Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, and et al. A math- ematical framework for transformer circuits. Transformer Circuits Thread, 2021.
Federico Errica, Henrik Christiansen, Viktor Zaverkin, Takashi Maruyama, Mathias Niepert, and Francesco Alesiani. Adaptive Message Passing: A General Framework to Mitigate Oversmooth- ing, Oversquashing, and Underreaching, arXiv, 2024.
12

---

Matthias Fey and Jan Eric Lenssen. Fast Graph Representation Learning with Py PyTorch Geometric, arXiv, 2019.
Matthias Fey, Jan-Gin Yuen, and Frank Weichert. Hierarchical Inter-Message Passing for Learning on Molecular Graphs. In Graph Representation Learning and Beyond (GRL+) Workhop at ICML 2020. arXiv, 2020.
Robin Forman. Determinants of Laplacians on graphs. Topology. 32(11:35 46, 1993.
Daniel Y. Fu, Tri Dao, Khaled K. Saab, Armin W. Thomas, Atri Rudra, and Christopher Ré. Hun- gry Hungry Hippos: Towards Language Modeling with State Space Models. In International Conference on Learning Representations, ICIR, 2023.
Satoshi Furutani, Toshiki Shibahara, Mitsuaki Akiyama, Kunio Hato, and Masaki Aida. Graph Sig- nal Processing for Directed Graphs Based on the Hermitian Laplacian. In European Conference on Machine Learning and Principles and Pructice of Knowledge Discovery Databases, ECML PKDD, 2020.
Mikhail Galkin, Xinyu Yuan, Hesham Mostafa, Jian Tang, and Zhaocheng Zhu. Towards Foundation Models for Knowledge Graph Reasoning, arXiv, 2023.
Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability Properties of Graph Neural Networks. IEEE Transactions on Signal Processing, 68:5680-5695, 2020.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized PageRank. International Conference on Learning Rep- resentations, ICLR, 2019a.
Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion Improves Graph Learning. Neural Information Processing Systems, NeurIPS, 2019b.
Floris Geerts. On the Expressive Power of Linear Algebra on Graphs. Theory Comput. Syst., 65(1): 179-239, 2021.
Simon Geisler, Yujia Li, Daniel Mankowitz, Ali Taylan Cemgil, Stephan Günnemann, and Cos- min Paduraru. Transformers Meet Directed Graphs. In International Conference on Machine Learning, ICML, 2023.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neu- ral message passing for quantum chemistry. International Conference on Machine Learning, ICML, 2017.
Lorenzo Giusti, Teodora Reu, Francesco Ceccarelli, Cristian Bodnar, and Pietro Liò. CIN++: En hancing Topological Message Passing, arXiv, 2023.
Martin Grohe, Kristian Kersting, Martin Mladenov, and Pascal Schweitzer. Color Refinement and Its Applications. In Guy Van Den Broeck, Kristian Kersting, Sriraam Natarajan, and David Poole (eds.), An Introduction to Lifted Probabilistic Inference, pp. 349-372, The MIT Press, 2021.
Albert Gu and Tri Dao. Mamba: arXiv, 2023.
Linear-Time Sequence Modeling with Selective State Spaces,
Yuhe Guo and Zhewei Wei. Graph Neural Networks with Learnable and Optimal Polynomial Bases. In International Conference on Machine Learning, ICML. arXiv, 2023.
Benjamin Gutteridge, Xiaowen Dong, Michael Bronstein, and Francesco Di Giovanni. DRew: Dy- namically Rewired Message Passing with Delay. In International Conference on Learning Rep- resentations, ICLR, 2023.
David K. Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129-150, 2011.
Mingguo He, Zhewei Wei, Zengfeng Huang, and Hongteng Xu. BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation. In Neural Information Processing Systems, NerulPS, 2021.
13

---

Mingguo He, Zhewei Wei, and Ji-Rong Wen. Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited. In Neural Information Processing Systems, NeurIPS, 2022.
Xiaoxin He, Bryan Hooi, Thomas Laurent, Adam Perold, Yann LeCun, and Xavier Bresson. A Generalization of ViT/MLP-Mixer to Graphs. In International Conference Machine Learning, ICML, 2023.
Dan Hendrycks and Kevin Gimpel. Bridging nonlinearities and stochastic regularizers with gaussian error linear units. CoRR, abs/1606.0844 2016.
Sepp Hochreiter and Urgen Schmidhuber. Long Short-term Memory, Neural Computation, 9(8):
17351780-17351777 1997.
Andrew G. Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications, arXiv, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. Neural Information Processing Systems, NeurIPS, 2020.
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. OGB- LSC: A Large-Scale Challenge for Machine Learning on Graphs, arXiv, 2021.
Ningyuan Huang, Soledad Villar, Carey E. Priebe, Da Zheng, Chengyue Huang, Lin Yang, and Vladimir Braverman. From Local to Global: ppectral-Inspiing Graph Neural Networks. New Frontiers in Graph Learning at NeurIPS, arXiv, 2022.
Yinan Huang, William Lu, Joshua Robinson, Yu Yang, Muhan Zhang, Stefanic Jegelka, and Pan Li. On the Stability of Expressive Positional Encodings for Graph Neural Networks. In International Conference on Learning Representations, ICLR, 2024.
Md Shamim Hussain, Mohammed J. Zaki, and Dharmashankar Subramanian. Global Self-Attention as a Replacement for Graph Convolution. In International Conference Knowledge Discovery and Data Mining, KDD, pp. 655-665, 2022.
Md Shamim Hussain, Mohammed J. Zaki, and Dharmashankar Subramanian. Triplet Interaction Improves Graph Transformers: Accurate Molecular Graph Learning with Triplet Graph Trans- formers, arXiv, 2024.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. International Conference on Learning Representations, ICLR, 2017.
Christian Koke and Daniel Cremers. HoloNets: Spectral Convolutions do extend to Directed Graphs. In International Conference on Learning Representations, ICLR, 2024.
Arthur Kosmala, Johannes Gasteiger, Nicholas Gao, and Stephan Günnemann. Ewald-based Long- Range Message Passing for Molecular Graphs. In International Conference on Muchine Learning, ICMI,, 2023.
Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking Graph Transformers with Spectral Attention. In Neural Information Pro- cessing Systems, NeurlPS, 2021.
Remi Lam, Alvaro Sanchez-Gonzaler Matthew Willson, Peter Wirnsberger, Meire Fortunato, Fer- Alet, Suman Ravuri, Timo Ewalds, Zach Eaton-Rosen, Weihua Hu, Alexander Merose, Stephan Hoyer, George Holland, Oriol Vinyals, Jacklynn Stott, Alexander Pritzel, Shakir Mo- hamed, and Peter Battaglia. Learning skillful medium-range global weather forecasting. Science, (52(6677):1416-11 1-22,, 2023.
Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L. D. Jackel. Backpropagation Applied to Handwritten Zip Code Recognition. Neural Computation, 1(4):541- 551, 1989.
14

---

Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In International Confer- ence on Machine Learning. ICML, 2019.
R. B. Lehoucq, D. C. Sorensen, and C. Yang. ARPACK Users' Guide; Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods. Society for Industrial and Ap- plied Mathematics, 1998.
Pan Li and Jure Leskovec. The Expressive Power of Graph Neural Networks. In Lingfei Wu, Peng Cui, Jian Pei, and Liang Zhao (eds.), Graph Neural Networks: Foundations, Frontiers, and Applications, pp. 63-98. Springer Nature Singapore, Singapore, 2022.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning. In Neural Information Processing Systems, NeurlPS, 2020.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S. Zemel. LanczosNet: Multi-Scale Deep Graph Convolutional Networks. In International Conference on Learning Representations, ICLR. arXiv, 2019.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large Scale Learning on Non- Homophilous Graphs: New Benchmarks and Strong Simple Methods. In Advances in Neural Information Processing Systems, 2021.
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. In International Conference Learning Representations, ICLR, 2023.
lyy Loshchilov and Frank Hutter. SGDR: Stochastic gradient descent with warm restarts. In Inter- national Conference on Learning Representations, ICLR, 2017.
Ilya Loshchilov and Frank Hutter. Decoupled Weight Decay Regularization. International Confer- ence on Learning Representations, ICLR, 2019.
Yuankai Luo, Hongkang Li, Lei Shi, and Xiao-Ming Wu. Enhancing Graph Transformers with Hierarchical Distance Structural Encoding, arXiv, 2024.
Liheng Ma, Chen Lin, Derek Lim, Adriana Romero-Soriant Puneet K. Dokania, Mark Coates, Philip Torr, and Ser-Nam Lim. Graph Inductive Biases Transformers without Message Passing. In International Conference on Machine Learning, ICML, 2023.
Amil Merchant, Simon Batzner, Samuel S. Schoenholz, Muratahan Aykol, Gowoon Cheon, and Ekin Dogus Cubuk. Scaling deep learning for materials discovery. Nuture, 82447790):80-85,, 2023.
Gaspard Michel, Giannis Nikolentzos, Johannes Lutzeyer, and Michalis Vazirgiannis. Path Neural Networks: Expressive and Accurate Graph Neural Networks. In International Conference on Machine Learming. ICML, 2023.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gau- rav Rattan, and Martin Grohe Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks. AAAI Conference on Artificial Intelligence, 33:4602 4609, 2019.
I. P. Natanson. Constructive function theory. Vol. I: Uniform approximation. Translated by Alexis N. Obolensky. New York: Frederick Ungar Publishing Co. IX, 232 p. (1964),, 1964.
Nhat Khang Ngo. Truong Son Hy, and Risi Kondor. Multiresolution Graph Transformers and Wavelet Positional Encoding for Learning Hierarchical Structures. The Journal of Chemical Physics. 159(3):034109, 2023.
Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Scott Johnston, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah. In-context Learning and Induction Heads, arXiv, 2022.
15

---

Seonghyun Park, Narae Ryu, Gahee Kim, Dongyeop Woo, Se- Young Yun, and Sungsoo Ahn. Non- backtracking Graph Neural Networks, arXiv, 2023.
Phitchaya Mangpo Phothilimthana, Sami Abu-EI-Haija, Kaidi Cao, Bahare Fatemi, Charith Mendis, and Bryan Perozzi. TpuGraphs: A Performance Prediction Dataset on Large Tensor Computa- tional Graphs. In Neural Information Processing Systems, NerulPS, 2023.
Michael Poli, Stefano Massaroli, Eric Nguyen, Daniel Y. Fu, Tri Dao, Stephen Baccus, Yoshua Bengio, Stefano Ermon, and Christopher Ré. Hyena Hierarchy: Towards Larger Convolutional Language Models. In International Conference on Machine Learning, ICML. arXiv, 2023.
Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra. Grokking: Gener- alization Beyond Overfitting on Small Algorithmic Datasets, arXiv, 2022.
Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for General, Powerful, Scalable Graph Transformer. In Neural Infor- mation Processing Systems, NeurIPS, 2022.
Emanuele Rossi, Bertrand Charpentier, Francesco Di Giovanni, Fabrizio Frasca, Stephan Günne- mann, and Michael Bronstein. Edge Directionality Improves Learning Heterophilic Graphs. In Learning on Graphs Conference, LoG, 2023.
Kristof T. Schütt, Pieter-Jan Kindermans, Huziel E. Sauceda, Stefan Chmiela, Alexandre Tkatchenko, and Klaus-Robert Müller. SchNet: continuous-filter convolutional neural net- work for modeling quantum interactions. In Neural Information Processing Systems, NerulPS. arXiv, 2017.
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, and Ali Kemal Sinop. Exphormer: Sparse Transformers for Graphs. In International Conference Machine Learning. JCML, 2023.
M. A. Shubin. Discrete Magnetic Laplacian. Communications in Mathematical Physics, 164(2): 259-275, 1994.
Laurent Sifre. Rigid-Motion Scattering For Image Classification. PhD thesis, Ecole Polytechnique, CMAP, 2014.
Kimberly Stachenfeld, Jonathan Godwin, and Peter Battaglia. Graph Networks with Spectral Mes- sage Passing, Xrv,,, 2020.
Zekun Tong, Yuxuan Liang, Changsheng Sun, David S. Rosenblum, and Andrew Lim. Directed Graph Convolutional Network, arXiv, 2020.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M.
Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In Interna- fional Conference on Learning Representations, ICLR, 2022.
Jan Tönshoff, Martin Ritzert, Eran Rosenbluth, and Martin Grohe Where Did the Gap Go? Re- assessing the
Graph Benchmark. In Learning on Graphs Conference, 2023.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In Neural Information Processing Systems, NeurIPS, 2017.
Petar Veličković, Arantxa Casanova, Pietro Liò, Guillem Cucurull, Adriana Romero, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, ICLR, 2018.
Ulrike von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395-416. 2007.
Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks. In International Conference on Learning Represen- tations, ICLR, 2022.
16

---

Xiyuan Wang and Muhan Zhang. How Powerful are Spectral Graph Neural Networks. In Interna- tional Conference on Machine Learning, ICML. arXiv, 2022.
Tom Wollschläger, Niklas Kemper, Leon Hetzel, Johanna Sommer, and Stephan Günnemann. Ex- pressivity and Generalization: Fragment Biases for Molecular GNNs, arXiv, 2024.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken Ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference Machine Learning, ICML, 2018.
Keyulu Xu, Stefanie Jegelka, Weihua Hu, and Jure Leskovec. How powerful are graph neural networks? In International Conference on Learning Representations, ICLR, 2019.
Mingqi Yang, Wenjie Feng, Yanming Shen, and Bryan Hooi. Towards Better Graph Representa- tion Learning with Parameterized Decomposition & Filtering. In International Conference on Machine Learning, ICMI,, 2023.
Jiaxuan You, Rex Ying, and Jure Leskovec. Design Space for Graph Neural Networks. pp. 13, 2020.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbhakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander J. Smola. Deep sets. In Neural Information Processing Systems, NerulPS, 2017.
Xitong Zhang, Yixuan He, Nathan Brugnone, Michael Perlmutter, and Matthew Hirn. MagNet: A Neural Network for Directed Graphs. In Neural Information Processing Systems, NeurIPS, 2021.
Yi Zhang, Arturs Backurs, Séhastien Bubeck, Ronen Eldan, Suriya Gunasekar, and Tal Wagner. Unveiling Transformers with LEGO: synthetic reasoning task, arXiv, 2023.
17

---

Appendix
Notation
19
Related Work for Expressivity and Directed Graphs
19
Background for Directed Graphs
20
Limitations of Graph Transformers Using Absolute Positional Encodings
21
S'GNN Generalizes a Virtual Node
21
Existing Results on Over-Squashing
21
Construction an explicit ground truth filter
22
Proofs
24
H.1
Proof of Theorem
24
H.2
Proof of Theorem
26
H.3
Proof of heorem
26
Proof of heorem
28
H.5
Proof of Thorem 5
31
H.6
Proof of Theorem 6
33
Expressivity Spectral Filters and Spectrally Designed Spatial Filters
34
J
Further Remarks on S'GNNs
35
J.1
Visualization of Spectral Filters
36
J.2
Composition Filters
37
J.3
Exhaustive Reasons Why Low Frequencies Are Sensible
37
J.4
Scaling to Graphs of Different Magnitude
37
J.5
Spectral Normalization
37
J.6
Adjusting S'GNNs to Directed Graphs
38
J.7
Computational Remarks
38
Limitations
38
Broader Impact
39
M
Experimental Results
39
M.
Experimental Details
39
M.2
Qualitative Experiments
M.3
Computational Cost
41
M.4
SºGNN Aggregation Ablation
42
M.5
Number of Eigenvectors Ablation Peptides-Fum
43
M.6
Clustering Tasks
43
M.7
Distance Regression]
47
M.8
Heterophilic arXiv--ear (Lim et al. 202
49
M99
Large-Scale PCQM4Mv2 (Hu et al. 2021
50
M. 10 TPUGraps Graph Construction
50
18

---

A
Notation
Table 5: List of most important symbols used in this work (with the most general domain).
6
Scalar
b
(column) Vector
B B
Matrix
Set
Transpose matrix
BH
Conjugate transpose of matrix B
1,8 --1
Complex number
Element-wis multiplication
Function composition, i.c., f2 o fi = fi (f(())))
Frobenius norm
O
"Big O" notation for asymptotic growth of function Permutation matrix
PEP
*g
Graph convolution (see $
(G,)
Graph sequence (cf. Theorem 3)
C(A,
Graph
A E 20
Adjacency matrix
X E Raxd
Node features
Number of nodes
Number of edges
Number of attributes
Lg E CaR
htaph//ombinatooiillaaddooo walk (Magnetic) Laplacian
9 Rgo
Potential (see Eq. 7
- L E Raxn
Real-valued Laplacian (g 0)
A, V- EVD(L)
Eigendecomposion L = V diag (A) L
A, = A)
Partial cigendecomposion containing A S 22 .... S (S Ant1)
k
Number of eigenvectors
p
Polynomial order
Peu
Receptive field size (number hops) of polynomial filter Maximal diameter of graph
Pmax
Aent
Eigenvalue threshold considered in spectral filter
Amax
Maximal eigenvalue of graph
L
Number of layers
Kr(G.
Bound on r-th derivative of spectral filter on interval [eeur: 2]
Spectral
(1) (H V. V. Spectral(ly parametrized) filter
Spatial H (1)) A)
Spatial message passing
g
Filter in graph convolution
Order-p polynomial filter in graph convolution, with coefficients % Filter in graph convolution, in spectral domain function evaluated eigenvalues
g
(A)
go
as parametrized function evaluated at eigenvalues
9o (A)
parametrized function at layer evaluated eigenvalues Positional encodings
PE(V,))
fo
Feature transformation in spatial domain
sç
Feature transformation in spectral domain
B Related Work for Expressivity and Directed Graphs
Expressivity. Laplacian eigenvectors have been used previously to construct positional encodings that improve the expressivity GNNs or Transformers (Lim 2023 Wang et al. 2022 Geisler
et al. 2023 Huang et al.) 2024). Our positional encodings are similar to the preprocessing of Balcilan
al. 2021a), where the authors design an edge-level incoding/mast to surpass 1-WI.. The hierar-
chy of Weisfeiler-Leman (WL) tests is common way to categorize the expressivity of GNNs (Grohe
19

---

et al. ). p. Xu et al. 2019) showed that most MPGNNs are bound by or as strong as the 1-WL test. Lim et al. 2023) point out that spectral GNNs suffer from similar limitations MPGNNS w.r.t. their expressivity. Generally, the development of expressive GNNs is an active research direction, and we refer to Li Leskovec|
for a broad overview.
Directed graphs. Rossi et al. (023) also extend the WL test to directed graphs and propose an MPGNN for directed graphs. How model direction graphs also still an open question and various approaches were proposed (Battaglia et al. 2018 Tong et al. 2020 Zhang et al. 202 Rossi al. 2023: Koke & Cremers, 2024). We utilize a Hermitian Laplacian for direction awareness, namely the Magnetic Laplacian, which was also used by /Zhang et al. (2021) for an MPGNN and Geisler et al. (2023) for positional encodings.
C Background for Directed Graphs
Undirected directed graphs. For spatial filtering, it is straightforward to plausibly extend the message passing (e.g. [Battaglia et al. (2018); Rossi et al. (2023)). However, the spectral motivation and spectral filter on directed graphs require more care. The eigendecompooition is guaranteed to exist for real symmetric matrices. Real symmetric matrices are always diagonalizable, and the eigen- vectors will then span complete orthogonal basis represent all possible signals X E Raxd Note that some non-symmetric square matrices are also diagonalizable and, thus, also have an eigende- composition, albeit the eigenvectors may not be orthogonal. Thus, further consideration is required to generalize the graph Laplacian to general directed graphs
Magnetic Laplacian. For the spectral filter on directed graphs, we build upon direction-aware generalization, called Magnetic Laplacian (Forman 1993 Shhbii 1994 tani et al. 2020 Geisler et al. 2023)
De Verdière 2013 Furu-
Lg = I (D, A.D, V/) expli22mg( A
where A. A AVA A is the symmetrized graph with diagonal degree matrix D.. denotes the element-wise product, exp the element-wise exponential, V-I an imaginary number, and q the potential (hyperparameter)) By construction L, is Hermitian matrix Lg L where the conjugate transpose is equal to Lg itself. Importantly, Hermitian matrices naturally generalize real symmetric matrices and have a well-defined eigendecomposition L, = VAVH with real eigenvalues A and unitary eigenvectors VVH I. For appropriate choices of the potential q, the order of eigenvalues is well-behaved (Furutani al., 2020). Recently Geisler al. of these eigenvectors for positional encodings for transformers. Moreover, the Magnetic Laplacian was used for spectrally designed spatial MPGNN (Zhang et al. 202I). extending Defferrard et al. (2117). Due to the real cigenvalues, one could, in principle, also apply a monomial basis (Chien al.] 202T). or different polynomial bases stemming from approximation theory (He et al. 2021
(2023) demonstrated the efficacy
Wang & Zhang 2022 He et al. 2022 Guo & Wei 2023).
To see why [Eq. 7 describes injection for appropriate choices of q. consider that the sparsity pattern of Lg matches A up to the main diagonal. A contains a self-loop the main diagonal will have a 0 instead of entry at the self-loop location. A - A can be directly inferred from the A)), assuming that q < 1/(2 max,,v A,..). Thus, it is solely left to obtain A, from -D. A, D. 1/2 which is trivial for a binary adjacency but more involved for rell-v weights Determining if and when Lg is injective for real-valued A is left for future work.
phase expli2mg(A A- AT)
Properties of the eigendecomposition. The eigendecomposition not unique, and thus, one should consider the result of the eigensolver arbitrary in that regard. One ambiguity becomes apparent from the definition of an cigenvalue itself Lu = Ao since one can multiply both sides of the equation with a scalar E C (0): L(cv) X(cv). We already implicitly normalized the magnitude of the eigenvectors V by choosing them to be orthogonal (VVT I) or unitary (VV I). Thus, after this normalization, e only represents an arbitrary sign for real-valued eigenvectors or a rotation on the unit circle in the complex case. Another reason for ambiguity occurs in the case of repeated / multiple eigenvalues (e.g., Ao = A, for u A v). In this case, the eigensolver may return an arbitrary set of orthogonal eigenvectors chosen from the corresponding eigenspace.
20

---

D Limitations of Graph Transformers Using Absolute Positional Encodings
Here, consider vanilla graph transformer s(X) that solely becomes structure-aware due to the addition (or concatenation) of positional encodings: f(X + PE(A)). The main point we are going to demonstrate that a vanilla transformer with such absolute positional encodings PE(A) E Raxd will be limited in its expressivity if the positional encodings are permutation equiv- ariant (P) = PE(PEPPPPPP w.r.t. any n x n permutation matrix E P.
The limitation particularly arises in the presence of automorphisms PaAPT cally chosen permutation Pa. To be more specific, assume that nodes and u are automorphic to each other. That is, there exists Pa that will swap the order of and v (among other nodes) s.t. P. a A. By permutation equivariance, we know P. PE(A) = PE(P.AP, = PE(A) and, hence, (E(A), PE(A)..
with specifi-
We have just shown that automorphic nodes will have the same positional encodings PE if the po- sitional encodings permutation equivariant. This implies that permutation equivariant positional encodings PE are not even able to capture simple neighboring relationships. For example, consider an undirected sequence/path graph o 0-0-0-0-0 with five nodes. Here, the two end nodes, which we also all first and last node, are automorphic. So are the second and second-last nodes. Assuming the second and second last nodes have different node features (e.g., A-B-C-D-A)) A), that breaks the sym- metry, it is still not possible for a transformer with absolute positional encodings to tell the first and last node apart. In other words, in the example, the transformer cannot tell apart the end node with neighboring feature B from the end node with neighboring feature D. This shows severe limitation of architectures without additional components capturing the relative distances (e.g., S'GNNs can). This concern is not critical for architectures where the positional encodings are not entirely permutation equivariant (Dwivedi Bresson 2021 Kreuzer et al. (02T), with relative positional encodings (Ma et al. 2023), and might also be of lesser concern for directed graphs (Geisler et al., 2023).
E SNGNN Generalizes a Virtual Node
Adding a fully connected virtual node (Gilmer et al. 2017) is among the simplest ways to add the ability for long-range information exchange. An equivalent method was proposed as a simple over- squashing remedy in the seminal work by Alon & Yahav 2020). A single Spectral layer amounts to type of virtual nodes the special case of fo = I and
1 for À 0, (0 for 0,
(a)())
Assuming a simply-connected graph g, the unique normalized zero-eigenvector v of the catnnntrically-oommaaiin graph Laplacian L 1 AD 1/2 has components v. = v 2
where d. denotes the degree of node u 9. and [E] the number of edges in the graph. node E G, we therefore find
Spectral (0) [H (H V,A)
Vanng-n
F
vEg
with h (1-1) denoting the row of H (1-1 corresponding to node E G. In other words, filtering out the zero-frequency component of the signal means scattering global, begree--eiighte embedding average to all nodes of the graph. For the unnormalized graph Laplacian, [g. 9 instead becomes an unweighted average, which is consistent with the usual definition of virtual node. We refer to
Fig. 3 & 4 for additional intuition.
F Existing Results on Over-Squashing
We restate two key results from Di Giovanni et al. (2023a) using our notation. They imply the exis- tance of regime in which 1-hop MPNN architectures suffer from exponentially decaying Jacobian sensitivity. Meanwhile, S'GNNs can easily learn a signal of constantly lower-bounded sensitivity, as shown by invoking its trivial subcase of virtual node in Theorem 2
21

---

Theorem 7 (Adapted from Di Giovanni et al. (203al),, In an E-layer spatial MPGNN with message- passing matrix
c, + C, A (c,, Co E R and a Lipschitz nonlinearity a.
H ( = Spatial (1) (H (H A)=A)))- a (SH(-DWU--)) ,
(10)
the Jacobian sensitivity satisfies the following upper bound:
(C)
Th
S wo) )
(11)
Th
L1
with h h denoting the rows of H Lipschitz constant of the nonlinearity, w the maximum entry value over all weight matrices W and d the network width.
H corresponding to the nodes v, u E G, Co the
The dependence of the upper bound on the matrix power (5" on not generally present for S by Theorem 2] leads to a concerns the typical diammer regime, in which the number of MPGNN layers is com- parable to the graph diameter.
which becomes explicit in the following theorem.
Theorem (Adapted from Di Giovanni et al. (2023a). Given an MPNN as in Eq. 10 with ca I 1, let U, u 9 be at distance r. Let Co be the Lipschitz constant of σ, w the maximal entry-value overall weight matrices, dmin the minimal degree of 9, and re(v, u) the number of walks from v to of maximal length For any O such that
r, there exists Ck independent of and of the graph,
0h(rtk) The
(r+R)
I Cann-uu u) wd (2oowd) dmin
Th. (0)
1,2
For I-hop MPGNNS with 2c, wd < dmiin we therefore identify an exponential decay of sen- sitivity with node distance in the weak-connectivity limit for which Tr+* (v, u) increases sub- exponentially with r. As Giovanni et al. (2023a) point out, sharper bounds can be derived under graph-specific information about (S")ew Vew"
G Construction of an explicit ground truth filter
We express the electric potential along periodic sequence of screened ID charges as a convolution of corresponding graph signal with consistently defined graph filter. This closed-form example underscores our default use a low-pass window for the spectral part of S'NNNs by showing how a continuous problem with convolutional structure and quickly flattening spectral response (typical for pair interactions in physics and chemistry) discretizes into graph problem with similar features.
The approach exploits the surjective mapping of Fourier modes on [0, ni onto the Laplacian eigen- vectors of a cycle graph Cn. We consider two corresponding representations of the same problem:
R-1
p(x) = Σ
An (Ir 1), 1), Am(x)= = Σ 8(x mmn), V(x) = (or *R p)(x),
(12)
1-0
mEZ
)) -
(x(x) = xerf
2 (2o)
+
2
exp
x2
-10), |z/, a> 0
[
[(() = (do *R ()) 1 (go #g q)i 0 < k < n - Aq ER"
(13)
g = Cn. q (q1 (gi..... 9m.)
(14)
A continuous representation (Eq. 12) in terms of ID distribution p of n point charges (I..... .....ge. (n and their periodically repeating image charges, written as a sum of Dirac combs at equidistant offsets / with 0 < 5 - 1, interacting via the potential profile & obtained from solving in Gauss' law of electrostatics for a 1D point charge screened by a Gaussian cloud of opposite background charge with standard deviation The screening ensures
22

---

convergence to finite potential and its exact form is insignificant (we choose the Gaussian- type screening due its analytical tractability). Note that o, (x) = const. |x| for - (the unscreened ID potential in the direction normal to infinitely wide capacitor plate), while the screening guarantees an exponential dropoff to zero as + co,
A graph representation (Eq. 14 by placing the charges Q1..... On onto a cycle graph C,.
We derive the graph filter Io from a consistency condition (Eq. 13) between both representations: the graph convolution (go *g q) has to yield the electric potential V sampled at the charge loci if we want Jo to act like the continuous convolution kernel 6, in the discrete graph picture.
The Fourier transform of dor (in the convention without integral prefactor and with 2n frequency 1
prefactor) reads do (k) = THz (1 - exp (-)o² For the density, the Poisson sum formula vn
gives p(x) k= vn
J. A )) with d: 1 Ej=o qi exp (-i2m The coefficients 9k
are precisely the components of the graph Fourier transform of q (physically, they amount for the structure factor). By the convolution theorem, (Ms) = de ((r). By noting that all integer-shifted frequencies in the Dirac combs A1 (- (-- :) (or all Brillouin zones, in physics terminology) yield the same phase exp (i2m () if we only sample V(x) at the charge loci = 1, 0 < S n 1, we write (()) 2オ Σx= 4R (Emez do ( + m)) vn exp (12 Through mattern-matchine with the consistency condition of Eq. 13 we can therefore identify that the graph filter is a sum over Brillouin zones, (0.)
2 Emez 6. ( + m). where A denotes the eigenvalues of the
normalized C, graph Laplacian, A = 1 cos (2rk) ). To fulfill this relation for all A we set
(A)
Σ mEZ
de
1 2n
arccos(1 - A) + m
2T
We claim now (and prove in a later paragraph) that for > Ao > 0 and a sufficiently large choice a > (r, Ao), the absolute r-th derivative satisfies the upper bound 1 9 (A) S lax (A)), where we can think of 9o as the limit of taking oo (i.e., constant background charge):
Oo0 (1)
1 Σ 2T
000
2 arccoss(1 - A) + m). (x(()) Tk? 2T
mEZ
The merit of this is that unlike the screened 9o (A), 9o0 (A) can be solved analytically to find closed- form bounds on the absolute derivatives d= 7x= 9o (Ao)l. By invoking the sum expansion form of the
trigamma function 1,(=) Em=o (=+m)² the reflection identity th (1 2) + (1((2)
7²
sin x2²
and the half- formula sin? 2 (3) 1-cos(z) we find
1
arccos(1 - -1) + v (1- arccos(1 - -1)
g00 (A)
V
2n
2m
2n
2 sin 2
( arccos( 1 - X)) X
a remarkably simple result. We can now readily evaluate 4' -r prove that this upper-bounds 1,K- (A)) for any À > Ao > 0 and sufficiently large o > arr Au)- For compactness, define the expressions z(A) == ž arccos(1 A) E [0, # (strictly increasing in
(m) (>)l = X but remains to
23

---

1), (2) = exp (-20²²²)
and _ = -1-22 2 2. Consider the series of "term-by-terni derivatives
dz Bo(2))
d
Σ
0c
(2 n)3 (1 yo(2 + +m))
(2 + = (1 yo Vr + ml)
1
π
Σ
O (yo (m))
m=
d
dea d=2 (x(2))
(3 (3+ vo(2 1 + m)) +
(3 n)t (1 yo (2 -m))
m=0
(v)(
They converge uniformly on [0, [ as they clearly are Cauchy sequences under uniform bound (moreover, well-definedness in merit provided by including Gaussian screening in our model). Therefore, they indeed converge dar 90 (A(z)) (justifying the above notation). The same holds for the der (x they are not defined in = 0, but otherwise still converge as they match the known series expansion of the polygamma function. Given Ap 2AAo) > 0, taking a larger than some or, Ao) guarantees that d (A(2) and d' (X are of the same sign for À > do (z(A) > z(Aa)). This holds for all orders r N since we see by induction that the product rule always yields one term analogous to the first respective terms above, and otherwise only terms of O (yo (m))). Then, observing that O < 1 Yo (x) < 1 V x 2 0 and d' E 2 implies dzr Hn (An(z))) < the chain rule.
follows by applying I'Hospital's rule physically, this is the
to the respective derivatives d'
corresponding series for d'
0 and thus
d" dz Foc (Ao(=o)) The same must hold for the X-derivatives by
One interesting question is whether do is also C-integral-Lipschitz for some constant C' > 0. We discuss this stability-ifformed criterion (Gama et al.] 2020) in the main body as domain-agnostic prior assumption about the "ideal" graph filter if no other ground truth knowledge informing ad- ditional smoothness bounds (such as here) available. While the above bound is loose to certify this directly (1 (A) I CX would be needed), Integral-Lisschiznee under some con- stant follows from the fact that dd 9o (A)l is bounded [0,2]: by the uniform convergence of the bere-my-term derivative series, it is continuous. Well-definedness of the product d dz has to be dz ax checked in X = 0, where it follows by continuous extension using l'Hospital's 's rule. As a continuous function defined on a compact interval,
dX 0o assumes maximum.
d
H
Proofs
H.1 Proof Theorem
We next prove the permutation equivariance of the spectral filter in Eq.
Theorem 1. Spectral (U-)) EVD( k)) of Eg. 3 is equivariant to all n x n permutation matrices P E P: SS EVL(PP k)) = P Spectral(H' (1-1), EVD k)).
for the general case of parametrizing Hermitian "Laplacian" L E C " L. Note that this proof does not rely in any means on the specifics of L, solely that the cigendecomposition exists L V AVV" H with unitary eigenvectors VVH I. For practical reasons, it is suitable to define L(A) as a function of A. A similar proof for real-valued eigenvectors is given by (Lim et al. 2023 The specific spectral filter consider is
(pe V. (g())
(((2) o [v (HH))H
(15)
with arbitrary / Cd: + Cd, applied row-wise (--) E Caxdi Analogously, Cd Cds is applied row-wise. We choose complex functions to emphasize generality, although we restrict
24

---

Spectral to real in- and outputs in all experiments. The graph filter is defined as element-wise func- tion (x,,(A) == (Am. {År, d2...........................2.. )x.) that depends on the specific eigenvalue and potentially the set of eigenvalues (A1, )2, ......, ) (or its vector representation A) of the partial eigendecompo- sition.
We need to make sure that the partial decomposition includes all eigenvalues of the same magnitude, i.c. Au A Au' Yu {1, ....., k}, u' {k 1, .... In practice, this is achieved by choosing large enough A to accommodate all eigenvalues Acur < A or by dropping trailing eigenvalues where X; > for E (1.2.....kk) .).. Generally, is also not important that we consider the k smallest eigenvalues in the spectral filter. We only need to ensure that the spectral filter is either calculated on all or no cigenvalues/vvectrs of an eigenspace.
Proof. Assuming functions (X) and & X are permutation equivariant, then (X)) is permu- tation equivariant ( (P)) = o(
(X)) for any n x n permutation P P. Thus, it sufficies to prove permutation equivariance for h. f. (Ā(A) @ [V X]) independently, where X E C"xds
P X
()((())
Regardless of the complex image and domain of h and f. they permuation equivariant since they are applied row-wise
((x) = (f f(x2)
f(X,)) )M
and reordering the rows in X C"xxd also reorders the outputs: f(PX) = Pf()).
For finalizing the proof of permutation equivariance, we first rearrange @ [o X]) and Y., = - Ia. o (uu)o,. X.,.
V(((A) (VHX))
Ex Vn (Au,
This construction (a) is invariant to the ambiguity that every eigenvector vn can be arbitrarily rotated va by {cu E C |cul | = 1}. That is, (c. = Uu = V.e
Moreover, (b) in the case of repeated eigenvalues 1, ..... +} where X,+1 A2+2
Àg+j. we can choose a set of orthogonal eigenvectors arbitrarily rotated/reflected from the j dimeensional eigenspace (basis symmetry). The given set of eigenvectors can be arbitrarily trans- formed V V.,++1:4,,,, by a matrix chosen from the unitary group r E U().. Since
Du (A X (Aa)(Aa)
Σ
X., = (A,) [V.st VHI Vittisss X
we simply need to show that the expression is invariant a transformation by ry:
Vist 1a+ 1 15) Vis+lis+ ; r V Vil = V. V s.ttee+]
To see why F3 E U(f) a sufficient choice in the light of repeated/mmultile eigenvalues, consider the defintion of eigenvalues/vectors
LV Aottsst = L U V Us+2
Ust
Ast1
0
X
0
Dot1
Ux42
Us+s
A
-oo11
Vatl
Do42
Ua+j
A Ves+lsos
we can now multiply both sides from the right with an arbitrary matrix B E Cixi, To preserve the unitary property V,,+Iis4 VH :.s11s4; I, we require BB) s+114 B) I. Thus, the eigenvectors can be arbitrarily transformed by T E U(j instead of B E Cixs.
This concludes the proof.
25

---

H.2 Proof of Theorem
We restate Theorem more detail and also considering graphs that contain multiple connected components. The unchanged bottom line is that GNNNNs can express signals lower- bounded by a constant that is unaffected by local properties of the graph topology, instead of suffering from exponential sensitivity decay like spatial MPGNNs.
Theorem (Theorem 2 formal). Consider an E-layer SNNNN of the form Eq. 1 Let (0, 0, 0) be parameters of the spatial GNN, spectral filters 93 and feature transformation fo. Assume the existence of parameters ô such that Spatial (H-1 ( A, i) = 0 LA S I S i and such that fo = I. Then, filter choice 0 exists such that the E-layer S GNN of the additive form Eq. 1 can
express signal h (0); 0,0, 0, with uniformly lower-bounded Jacobian sensitivity,
Th! (H (1) 0.0
21Eel ifu, connected,
ak
(16)
Ohu
0 otherwise,
L
with has he denoting the rows of H (0), ()))) corresponding to the nodes + E G, connected component C9 containing Eel edges, network width and parameter-dependert constant Kg.
Proof. Choose such that Spatial (H (1;; A) = A4 < 1 < & (typically by setting all weights and biases to zero), 8 such that fo = and set such that
19 9 0): Ka [1 for X 0,
< / S s
(17)
10 for A > 0,
for some Kg > O. This choice of filter parameters lets Spectral act like a type of virtual node across all hidden dimensions k: In the standard orthonormal basis of the O-eigenspace given by
(11)) =
du [1 for u C,
(18)
2 E|Ec {0 else,
where C enumerates all connected components, and du denotes the degree of node u, we find
H :0,00000000 0,0,00
(Spoctral(9) o...o Spectral (H) V V.
K3 K3vd, 2| Egtool NEC())
(19)
with ((v) denoting the connected component containing Particularly, note that applying the spec- tral layer more than once does not affect the result since the projector onto an eigenvector is idem- potent (up to Kz). The result must also hold in any other orthonormal basis of the O-eigenspace due to the invariance of Spectral under orthogonal eigenbasis transformations. Differentiating with respect to h taking the T,- norm and using / Vd 2 1 shows the statement.
H.3 Proof of Theorem
Let 9 be discontinuous spectral filter. For any approximating sequence (g-p) peN of polynomial filters, an adversarial sequence (Gp)peN of input graphs exists such that
Theorem 3.
11( - 9) *gp X
||F
Bo E R
sup
| ||
O (p-a)
of XER lxd
The proof makes use a result by S. Bernstein Natanson 1964):
Theorem 9 (Bernstein). Let f: [0, 2n] + C be a 2 20-periodic function. Then I is a-Hölder con- tinuous for some a E (0, 1) if. for every p E N, there exists a degree-p trigonometric polynomial
Tz(z) ao ΣE aj cos + Σ 1 by sin(jæ) with coefficients aj, bj E C, such that
sup 1f(z) - (x)) CS) OSa52=
pd
where C(f) is positive number depending f.
26

---

Proof. Given discontinuous filter g: [0, 2] - R. construct the function f: 10, 2nj + C fulfill- ing the prerequisites of Theorem 9 by pre-composing contradiction. Suppose that there is an E (0, 1) and a sequence of degree-p polynomial filters, 9y, (A) = ΣS N3 7 (7o..... 7p) E R2+1, such that 1l 0ll = Opp"). Then, the sequence of trigonometric polynomials T := 9yp o (cos(-) + 1) fulfills the condition of Theorem 9 This would imply that f = ğ o (cos(-) + 1) is a a-Hölder continuous, meaning that constant K > exists such that
:= و o (cos(.) 1) + 1). We proceed via
lő(cos(z) 1) g(cos(y) (3) 1) - K 2 y/ A Vz, y [0,2
Considering Àn E [0, 2]. À - A and = arccos Ao 1), arccos (A 1) (using the arcoos branch in which both λo À eventually end up) shows a contradiction to the assumed discontinuity of ÿ. Therefore, polynomial filter sequence (0-,) pEN together with E (0, 1) exist such that
ll0,, rl = Ogp ") In particular, for any sequence (Φ+,) pEnt a sequence of adversarial values (Ap)PEN, Xo E [0, 2] exists such that
Da E (0,1): (Ap) 3(Xp)) = 0p
The proof is finished if we can find a sequence of graphs (g,) such that the symmetrically- normalized graph Laplacian L, of Gp contains A as an eigenvalue. In this case, can construct adversarial input signals X, p on the graphs Gp by setting the first embedding channel to an eigen- vector corresponding to Ap. and the remaining channels to zero, such that (9T, - 9) *g, X, = 10,, (Ap) - ((Ap) xp. In particular, it then holds that
9) t |X |
X O (p-o)
Bo E IR::
sup
Of X
If we assume only simple graphs. such construction is unfortunately not possible since the set of all simple graphs and therefore the set of all realizable eigenvalues is countable, whereas the adversarial values Ap could lie anywhere in the uncountable set [0, 2]. We can, however realize arbitrary cigenvalues by using weighted graphs with three nodes. Consider a cyclic graph structure and tune the weight of edge (1, to sin (0p) and the weight of edges (2, 3) and (3, 1) to cos" (0p)
with Op E [0, T The symmetrically-normalli normalizedd graph Laplacian,
- cos2((p)) sin (0p)
Lp cos" (0p)
1
sin 2 (0p)
sin 2 (8p) sin sinn((pp)
has eigenvalues x 1, Ap
sin sin? (0p),
sip)
,,² can assume all values
Ap E [0, 1), whereas A can assume all values Xp E [1. This finishes the proof.
O
Remark. If one wishes to restrict the set of possible adversarial graph sequences (Gp) to include
only simple graphs, a version of Theorem 3 still holds where we restrict the assumption to filters
ğ which are piecewise-continuor with discontinuities on finite set of points D CS where S c [0, 2] denotes the countable set of eigenvalues realizable by simple graphs. This still covers large class of filters to which order-p polynomial filters can provably converge slower than any inverse root of in the operator norm, and includes the virtual node filter (discontinuous only in X 0) presented as an example in the main body. The proof is fully analogous up to the point of constructing >p- If Ap E D. can find graph that realizes it exactly. Now assume Ap & D. We note that the set S is dense in [0, 2] (clear from considering, e.g., the cyclic graphs C, with symmetrically- normalized Laplacian eigenvalues d = 1 cos ( (2nk) )). Since we assume that 9 and therefore also 10,, - أl is cettiiiee-ootuuuusss anywhere but on D C S and D is finite, we can find an open neighborhood (App)) for any Ap & DD on which ğ continuous. Using that S is dense in [0, 2). we find a graph sequence (g(() IEN
with eigenvalues X EN(A,, VI E, (5() ) Ap for which
11 (7(00) ((5(5)) II
ll0,, (Ap) ((Ap))l Therefore, by the same reasoning as in the proof of [1,,, g) X is of ||]|e
Theorem we find that there can be no a E (0, 1) for which sup xERllpln.
O (p
27

---

H.4 Proof of Theorem- 4
We first introduce the setting and notation to state Theorem 4 in its general version. We study how well SGGNNs can approximate "idealized" GNNs (IGNNs) containing L graph convolution layers
1 S 1 I L. each of which can express a convolution operator g with any spectral representation
g(): [0,2] + Rd An IGNN layer therefore has the structure
7 a (9 #g [H
= ((()
7 t1 - w()
(20)
with H E RDX w E RD xD and V E R=X"
We compare this to GNNN with & = (m + 1)L layers for m 2 1, in the additive form of
Eq.
H Spectral (H 11); V, A) Spatial (H A)
(21)
Each layer 1 S S l parametrizes spatio spectrl convolution. The spectral part satisfies Eq. 3
Spectral (H (F A) = v
9o (A)
V
H
(1
(1))))
spec
(22)
with embeddings ( E Raxd linear feature transforms
f(() aae E Rd x and
spectral filter g/² [0, + R that is fully supported and universal approximator on [0, Aem] Note we assume here that in every layer, there is only one spectral filter which gets reshaped as to act on every hidden component. whereas in practice, we relax this assumption different filters per component, which can only be more expressive. The spatial part is polynomial filter of the form
Spatial (H =a
Σ 1=0
L'
H 1-1
W
spor
=
04
[V H ww
spat
spal E R xd polynomial order p (fixed across layers), and spectral representation ..... 7p ) E R=+1 We note that theorem extends immediately the case of directed graphs if the spatial part is instead polynomial of the magnetic Laplacian (see section 3.2.3) over complex-valued embeddings like in Zhang et al. (2021).
with (:( 1 By (A) = Ei Pj
(1) X with coefficients 7()) = (70 (1)
Note that the layer-wise hidden dimensions D vs. d()) of the IGNN vs. S'GNN do not have agree except at the input layer, d()) DD() (of course, both networks receive the same input H
(0)) X), and the output layer, d(t) D(1), We now state the general version of
Theorem 4
Theorem Theorem general). Assume an L-layer IGNN with filters g()) such that g()) Pr |
C" (" 2] and
(() dAr
d" 2 S Kmiaa (Dew) for all 1 s L. Let [|g(9) 11c I |1@ lmar and
[| 1/2 S W|
max for all 1 S L. Assume that a = [-]2 is the ReLu function. Then,
(1) For a fixed polynomial order p an approximating sequence (S*GNMm) MEN of [(m 1) layer SNNN exists such that, for arbitrary graph sequences (Gm)meN.
[ G... GIGNN) [xXIlF
sup U. x X
|X||
= -CCCllll maX
W (Wx)
K max (Deur) (pm))-r)
L-1
Clgl
||
maa
max
max
[119]]
W
max
(lg
W
2
maxx
with leading- order scaling constant that depends only on r. Here, (- )mm. denotes the instantiation of all model filters on the eigenvalues of an input graph Gm, which maps both models onto a 9m-
r.
dependent function ig ( +BD(()
(2) For fixed m Z 1, an approximating sequence (S'GNN pER (mm + 1)Ll-layer S S'GNNs with increasing layer-wise polynomial order p exists such that, for all (Gp)pEn, the same bound holds.
28

---

Proof. We first prove the following lemma, narrowing down the previous theorem to single layer.
Lemma 1. Let IGNN denote a single IGNN layer as in Eq. 20 with filter gl) such that
g(t) D is r-times continuously differentiable on [Deur 2] and satisfies a bound K, (g , >em) 2 0, Tx (1) I Kr (g Aow) VX E Dowa, 2). Let o 1. be the ReLu function, and let [| ||2 denote the spectral norm of W Then,
(1) fixed polynomial order p 2 2. an approximating sequence (S*NN (t)
(m 1l-lyer
mEN
GNNN exists such that, for arbitrary graph sequences (9m)
[[ Sm.. - -IGNNV') (x) = O (1l 112K, dewe )em))(mm))
sup OF Splxa
|||||
with scaling constant that depends only on Here, (m)m denotes the instantiation of all model filters on the eigenvalues of an input graph Gm. which maps both models onto a 9m -en-eeendent
function IR D -RD
(2) For fixed m Z 1, an approximating sequence (S
P. ())
(m + 1)-layer S SGNN with PEN
increasing layer-wise polynomial order p exists such that, for all (Gp)pEN, the same bound holds.
Remark. The proof of the simplified Theorem 4 used the main body is analogous to the proof of Lemma justt without the nonlinearity, which has the following consequences:
The final layer + 1 which we only need to apply one last nonlinearity to the output (since the spectral part of all layers, including the previous layer m, has none) becomes obsolete, the final layer instead becomes m,
The two limits (1) and (2) are equivalent by the reduction to an mp-order polynomial filter,
We do not need the cinensionndoubllee "trick" outlined below to get rid of the nonlinearity in the proof and instead set all feature transform matrices in layers through m - to the identity and the final ones to (r ((), W=(m) W
spec
Proof Lemma 1 We first note that SºGNN spatial parts, each of order p. would act like an (mp)-orde) polynomial filter (factorized into m order-p polynomials), were it not for the nonlinear- ities in between. However, using the fact that is the ReLu function, we choose intermediate hidden dimensions twice the size the input dimension and then use the linear transforms to store positive and negative copy of the embeddings, add them back together after applying each ReLu, just to split the result back into a positive and negative copy for the next layer. This essentially gets superscript to denote the specific parameters that will ultimately satisfy our bound, whereas we put no star above parameters that are yet to be fixed in later part of the proof.
us rid of a. Throughout the proof,
For m 2 2, the trick discussed above works if we set
1 II
-1) E RR
D
1) x2
2
(=
Wa((--)-
1
(I
-I) E R2D0-))x2000
2
-I
Wa(m++1
= w(I)
(-1)
1
E
R 2D xxx0
spoc
W=(l)
= (I -1) E R 2D
1) D) 1)
spat
W (2)
we(m-1) 1)
I
I -1) E I 22
-1
(m++) = w())
(111)
1
E 2D
29

---

In the case = 1, pick the matrices Wopee' W from above for the first, and the matrices ()(++l) w from above for the second layer.
spec
sper
Set 9r (m 1) (A) = and 9o (m (A) = O. Given these choices and a graph 9 with eigenvalues X,
(S"NNN xx(
" )s()) = (v (Appp(A) ()) ① (l1l)) Dspep
II
m
90 + 044
We see that Ispsp [A 11 m (1) since Io [] = 0 for S S m. This can express any By
polynomial up to order mp on [Amax 2), since we assumed a layer-wise p 2 2 and any polynomial with real coefficients factorizes into real-coefficient polynomials of degree less equal to 2 by the fundamental theorem of algebra. On the interval [0, Amax]. on the other hand, the filter Ispepl [o.Aall
can express any IGNN filter 9eD) g0' Amx)" For 1, this is immediately clear. Else, set 06 to
constants Cj E 12, 1 j m large enough that none of the polynomials (c, (C,+99)
94 10.2mad gives the g()) [.Amm) 11 C (c,-84')
1 iSJS S m - 1, has zero in [0, Amax.. Defining g5(m)
desired function.
We proceed by making of result by D. Jackson NNaaanson 1964), which is essentially a con-
verse to Theorem 9 which we used to prove Theorem
Theorem (Jackson's theorem on interval). Let < b R. k,r E N with k: 2 0. f E C" b]. Then, a polynomial pt of degree less or equal to ls exists such that
llpk ffl I b- a π
1
2
2
(k+ (+k1)k. ... (k + 2)
dx
Since Sspsp can express any polynomial up to order mpp on [Amax. 2| and, for any such polynomial, find parameters for the spectral parts that match the ideal filter g()) [0,2ma)] exactly (not contributing
to the supremum error), we can directly transfer this theorem to our case. Define S'GNN (1) m from the lemma by setting the linear feature transforms and final-layer filters above. For the filters in
layers through m., define (1), ,.... 7 7((m) such that [1 07 =0() factorizes into into the polynomial
from Jackson's 's theorem on [Amax, 2), and 0-(1), ...., (m(m) match g()) on [0, Amax] This defines
filter Spp.. We then find, for mp 2 r- 1 0,
2 2-Amax TT 10 100 <
1
d' [0,
dlA ((0)
2
②
(mp + 1) mp ... (mp + 2)
Therefore, 110.p 110) is of O (K (Ô. Avm)) (mp) and we can find scaling constant that depends only on r. Since the Lipschitz constant of o is 1, we find for any graph G with eigenvalues and any graph signal 0 + X E RR!
(1)
[S>oNN))")) - (IGNN()) )5 (x)
@appp - g(0)
(A)
O [V XW
F
| F
X ||
11000pp
g00) 100 (IVV )
|E < 11
||
=0 (11W""0) Aewr) (mm)))
with a scaling constant that depends only on r. Exactly the same procedure and bounds hold if instead keep m fixed and increase p. This finishes the proof Lemma I
We can now prove the main theorem by induction. Lemma I gives the initial step. Now, assume the theorem holds for L IGNN layers. We can then choose (S²GNN mEN
30

---

(S'GNN (1+1)
G (1o (
where S'N (1+1) are the approximating models fulfill-
MEN
ing Lemma while (G fulfill the induction assumption. We assume fixed p and in- creasing m, but the proof is fully analogous in the other case. Applying the same decomposition to (IGNNm) m lets us express the error on a graph sequence (em)meN as
(Lo
mSN (IGNN) e.. (x)Il
|
(S'GNN (L+1) S o1)
IGNN(LO mm. - -IGNNÍÍ-") m
5mm
(x)
m
m
m
|
< [)
GN (1+11)
SSGNN (L
(Lo
mm
GS (1+1) IGNN(L
Om (x)
+ (II
IN (L+1)
e (INN((L
gm (IGNN(
I ()) gmm (x)
m
m
m
< [110 MIL
max
O(K,TM max (Aaa) (pm)
O] O0
max
W
K,T (Nou) (pm)
0
OKKTTN (Nou) (pmm)))((
(CL+1a(11) (1lila -|I ( KrTa (Aea) (pm))-
We first used the triangle inequality in line 3 to split the difference into two terms. Next, we bound the first term using the induction assumption, as well as the Lipschitz constant of SPGNN(L-1) which in turn, by Lemma is the Lipschitz constant of IGNN up term of O(KT max (Newt) (pm)-r). We moreover bound the second term using the Lipschitz. constant of IGNN (G- as well as Lemma to arrive at the final result.
m
H.S Proof Theorem
We next prove the stability of our positional encodings:
Theorem 5. The Positional Encodings PE in Eq. 5 are stable according Definition
Recall the definition of stability via Hölder continuity:
Definition 1 (Stable PE). (Huang et al. 2024) A PE method PE : R x R - Bank is
called stable, there exist constants c, C such that for any Laplacian L, and P. arg minp p L PL'P ||
[PEEEVD(L)) P. PE (EVV c -- -
For this proof, we build on the work of Huang et al. (2024) where the authors show that under the assumptions of Definition 2| and some minor adjustments, a positional encoding of the following form Eq. 23 stable (Theorem 10).
SPE(V. A) = (V diag (&r (A)) VT, V diag (dz(A)) VT, V diag (Øx VT) (23)
Definition 2.
The key ussumptions for SPE are as follows:
de and p are permutation equivariant.
the is Ky-Lipschitz continuous: for any X, E (R,,110E()) - de (X) S Kg X XII-
p J-Liscchitz continuous: for any [1, B2. Bx] E Fuxaxk and [B B 2..... BB]
Ruxnxk lp (Bi, B2,..., BB) (Bi. B
BillI S J B B F
Theorem 10 (Stability of [Eq 23 by Huang et al. (2024)). Under Definition SPE Eq. 23 is
stable with respect the inpul Laplacian: for Laplaciann L,
SPE(EVD(L) P.
(L')) S (an + +02) k5/)
/ VIL--,LLP l|r
(24)
a2 k
+
az
| L- J.-P.PP F
31

---

where the constants are 01 2J K 4V
K2,0
Mr. and as JE Kg. Here
Mj = 2) (é and again P. = arg min (E I PLLP. 1| The eigengap Y = AR+1 >u is the difference between the (k + 1 and k-th smallest eigenvalues, and -00 if T1.
We prove a similar bound for general weighted adjacency matrices A E R20 (note that such stability result would be trivial if we restrict A 10,1) since any function finite set is Lipschitz continuous). To achieve this, we need a technical assumption in order to ensure that the function values do not blow up and degree normalization indeed Lipschitz continuous function: We assume that the domain of A is restricted to (symmetric) matrices whose degrees are uniformly bounded by some constants <
Dunin
Dmaxi
du == A E [Dmin: D Dmax]
Vu E [I....,n].
(25)
To decompose the proof into smaller pieces we commonly use the well-known fact that the composi- tion of Lipschitz continuous functions fio with constants C and C2, is also Lipschitz continuous
(ff((()()) fi(f(=))) C1C₂ ly 2|| with constant CjC2.
Proof. Our proposed encoding
Eq. 5) matches roughly Eq. 23
Specifically, (x(
softmax((M, (Ag () 2))o2)) with E R However, (B, Bg...., B&) does not directly match 1 By ④ A] i, since it is also function of the adjacency A. Nevertheless, we show that de is Ke-Lipschitz continuous and is J-Lipschitz continuous, where we also bound the change of A.
The softmax is well-known to be of Lipschitz constant w.r.t. the L vector norm/Frobenius norm. -2/o has a Lipschitz constant of 1/a. This leaves us with the quadratic term (A) (Au X) (Au A) where we bound the
We will start with (A) softmax((1,
norm of the Jacobian
2( -11) 0
0
-2(Au
X2)
0
Joh =
(26)
2((x Ax)
that is zero everywhere except for the diagonal entries, excluding its w-th entry. Thus, || ||F I
2k max, v (1.2.....k) (Ar Xa) I 2k(Aa A1) I 4k, as 0 = x S d I 2. We can therefore use
K2 = 4k/o.
Now we continue with pe(A B1, B2, adjacency A E mxx, we consider
B&). For f(A, B) (B A).T with a general weighted
[ C A)
I B' A
B O A
B' 0 A'IIF
(A)
=Vn
B O A B' O A'I
B O A B' O A+ B' C A - B' O A'IIF
Vnl
B O A B' O A + Vn B' O A - B' O A'IlF
-V B') & A |P + VT B' 3 (A A')lI
Vn max Au,o |B B'Il
max
B 0e
Vn A A AlIFE
M
(F)
D
EE)
(27)
(A) holds by Canchy-Schwarz, (B) by triangle inequality, (C) by Cauchy-Schward (D) follows from the domain of A, and (E) is true since the largest eigenvalue of = VA is because de (e))), < 1, j k.
32

---

To further bound (F). i.c. 1|A - A |F. note that L L'IEE = | 1D-1/2AD AD 1/2
For ( = D our initial assumption from Eq. 25 yields the
existence of Lipschitz constant C CD.., for g. which can be verified by computing the partial derivatives of g. Thus, we can bound
|| A A = [10(D
1/2 1/2 AD 1/2)
A'D'
S C Pmin
| 1/2 AD DD' D''''
Duans.
(28)
Dmax
Diin
= Pmin Dmax
- =: a4ll I L'|FF.
Puax
Pmin
As concatenation of l vectors _ has Lipschitz constant of 1, we have J = V More- have additional term for the RHS of Eq. 24 with constant esynk, coming from (F) and
Eq. 28
To finalize the proof, we restate the beginning of the proof of Huang et al. (2024) and incorporate additional A-dependency of (e,A, B1, . BB) with Bj diag (Ø, V for s
j $ k.
SPE(EVD(L), L) P. SPE (EVD (I') L) [oe(A, B1, B2...... Bb) (Ap Bi, B BlIlF
(od(A, B1, B
B²) P..A'P P.B.P. P.B.P...... P.B.P.D)ls P.B.P........EPPP.)
(29)
B: P.B 1p
+aiViik L- P.L.P.
subjoct of (Hung et al 2024
Including the extra term stemming from our A-dependent pr Bi, B2.... BB), the stability guarantee reads
[SPE(EVD(L)) L) P. SPE(DE) l) & (a= + +az)
11L P.LPP.
k
+
02 + + auvTi)
| P.PP.PP
(30) The
with the newly introduced 044 arising as Lipschitz constant of (inverse) degree normalization.
proof is complete.
Windowing for "eigengap" independent bounds. Note that depends on the eigengap between
1/A2+1 As the frequency cutoff. One should be able improve upon this bound with windowing
(see Fig. ). effectively lowering the Lipschitz constant of h2(A) around λu. We leave a formal treatment of this insight to future work.
H.6 Proof Theorer
We next prove the expressivity of a GNN/S in combination with our positional encodings: Theorem 6. SNNN are strictly more expressive than 1-WL with the PE of Eg. 5
For this, we assume that the positional encodings are the only node attributes, subsuming constant feature or that there is linear transformation on the raw features. We require that the choice of spatial MPGNN spectral filter least as expressive as the 1-WL test, which the case, e.g., for GIN. Moreover, we assume that the node-level embeddings are aggregated to the graph level using summation.
Proof. To show that GNN(PE(V. A)) is strictly more expressive 1-WL. For all graphs that 1- WI. can distinguish, the GNN may learn to ignore the PF. Thus, we only need to prove that the positional encodings/node features of PF(V, X) suffice to distinguish some graphs that 1-WL could
33

---

Figure 15: Our positional encodings PE Eq. 5 illustrated in the node colors and sizes. We plot all 5 (rows) 3-regular graphs with nodes and all possible dimensions of the encoding (columns). We use 0.001. Color denotes the sign, and size encodes the absolute value. We hypothesize that the visual "smoothness" between graphs and dimensions is due to our PE's stability (Theorem 5).
not distinguish. For all graphs that 1-WL can distinguish we know, by assumption, that the GNN can distinguish the graphs.
As Li et al. (2020) point out, I-WL (and MPGNN that capable as I-WL) cannot distinguish degree-regular graphs with the same number of nodes and degrees. A degree regular graph is graph where each node has the same degree. This is closely related to Theorem II]
We next show that our PE alone distinguishes certain degree-regular graphs. In this construction, consider all 3-regular graphs with n 8 nodes for this (see Fig. 15 The encodings I PE result in the following values with a 0.001 and rounded to max 2 decimal places:
IT PE(EVD(L,) ,,)) )) = [3 1.73
0.41
-1 -1 -1.73
-2.41]
I PE(EVD(L.) L2)) = [3 1.56
0.62
0.62
0 -1.62
-1.62
-2.1
IT PE(EVD(L3)
1.73
0.41
-1 -1 -1.73
-2.41]
(31)
T PE(EVD(L.) = [3 1
0.41
0.41
-1 -2.11
-2.1
IT PE(EVD(L:)) = [3 1
-1 -1
-1 -3]
By constructing examples, this shows that our PE can distinguish 4 out of the 5 3-regular graphs with nodes. Thus, our PE may distinguish at least some graphs that 1-WL cannot. This concludes the proof.
I Expressivity of Spectral Filters and Spectrally Designed Spatial Filters
While it is well-known that common spatial MPGNNs are at most as expressive as 1-WL and that spectrally designed GNNs can more expressive than 1-WL (Theorem 2 of Balcilar et (202 show that spectral GNNs are not able to distinguish degree-regular graphs. This upper bound was
34

---

not known/formalized prior to our work (Bo et al. 2023b). Fortunately, our PE largely mitigates the limitation. The improved expressivity of our positional encodings, along with their efficiency, stems from the element wise product with A (see also Geerts (202T))
Theorem 11. Spectral V diag (0( V T are strictly less expressive than 3-WL with Lapla- cian L D A,
D A, or I 1-1/2
Proof. The proof relies on properties of the eigenvectors for the different choices Lu - D A, Liw = D- or L, = D-1/2 AD-1/2 For Lu = Ag = 0 and L T Ao = 0 the first cigenvector is constant. The first eigenvector L, is D (ignoring normalization). Thus, for degree-regular graphs, the first eigenvector of L, is also constant.
By the orthogonality of eigenvectors, V. 1 if u. +f orthogonal to constant node features. Consequently, the "Fourier transformed" node features are vTI= Vv 0 0] for all three choices Lu. Low. and Lg. Since this is true for all degree- regular graphs, spectral GNNs cannot distinguish degree-regular graphs with the same number of nodes.
know that all other eigenvectors are
Since the 3-WL test can distinguish some degree-regular graphs, 3-WL is strictly more expressive than spectral GNN.
"Spectrally designed" MPGNNs that use a polynomial parametrization of filter diag(G(A)) are strictly less expressive than 3-WL with the same choices for L.
Corollary 1.
Proof. With a polynomial parametrization of the spectral filter ((A), we know (ūū(A) O IV xx) =
V diag()(A)) x = g(L)x = Σラ= oo= L and spatial filter and the constant node features x I, any polynomial filter E 7 L'i cannot distinguish degree-regular graphs. This argument also holds if the polynomial filter is normalized by the maximum eigenvalue as done by ChebNet (Defferrard et al. 2017).
(see $ 2 Due to this equivalence between a spectral
J Further Remarks on SNGNN
We next provide insights, details, and remarks on the details and variants of GNNNS, accompanying the main section 3 The structure roughly follows the main body.
Next to the overview in Fig. 2] and the method description of the main part, we provide pseudo- code in Algo. I for Spatio-Spectral Graph Neural Network graph with node attributes, and in Algo. for a spectral filter.
Algorithm
Graph Neural Network (S"GNN), implementing Eq.
I: Input: Adjaceney A Rgx"... node attributes X E ( number of eigenvectors k
2: V, A + EVD(L(()) A), k)
H()) + X PE(V, V
4: for E (1, do
H(") < S0 (H(-1) V, X) Spatial (H (H(11);
Return (
Algorithm Real-valued spectral filter of Eq..
1: Input: Node embeddings H (1-1) E R=xa(l-1) cigenvalues E [0, 2 eigenvectors V E R
2: Ø3 (A) +- Smearing( A) @ Window(A)
3: H <- (1-)
4: H!l) + 2c (0 (A) 2 (-1)
5: H! (
Return (!)
35

---

(a)
(A
+ (z)
(ss)s)
+ (a(As)
(b)
9e(A.)
(a(2))
(A()))
+ (o(
(c)
3
(x())
(o(sss
(a()))
(d)
(o(A.)
(2))
+ (Ass))
+ *o(()))
(c)
(A1)
9o(As)
(a(Ae)
Figure 16: Sketch of intra- and inter-cluster message passing capabilities (V) @ [V = [E/= "==))o(A)uuy (A()))u))) JX. The "star" node reflects the global Fourier coefficient and colors/widths illustrate its signed and weighted message passing. We show the first four eigenvectors, order nodes left right in vy. and sum repeated eigenvalues.
J.1 Visualization of Spectral Filters
In Fig. I6 we provide further examples of hierarchiesseeieensaaes spectral filters have access to, complementing Fig. 3 & Here and in the main part,
the main diagonal of Ejst >,= f for deciding on the edge weights the graph structures, potentially summing over multiple eigenvectors with identical values X;- = A We take the product II, ,,= sign(1))) for visualizing the sign of the edges for the global aggregation.
For all graphs, the first eigenvector denotes the constant signal (for - A). For (a-d), we observe that the second eigenspace roughly describes half oscillation, i.e.. the left vs. right part of graph. The third eigenspace separates the middle parts. For (a), the fourth eigenspace models the interactions between the extremal nodes. For (b-d), the frequency increments again, effectively clustering the graph four roughly equal pieces. For (e), the eigenspaces model the interplay between (automorphic) inner and outer structures, as well as the vertical and horizontal symmetry.
36

---

J.2 Composition of Filters
Composing residual connection with graph filter G diag(ā(A)) E R yields Y VGV H H V(G + rjV H. chaining multiple filters (without nonlinearities) sults in V(G2G + G2+GG G H. Hence, an arbitrary sequence of graph filters (Eq. 2) can more flexible due the interactions between filters. Note that this composition is only true in the absence of nonlinearities. Nevertheless, the main intuition about how filters interact remains approximately the same also in the light of nonlinearities.
H VG H. Chaining and residual connections resolve to
J.3 Exhaustive Reasons Why Low Frequencies Are Sensible
sensible default to focus on the low frequencies. We specifically identify the following six reasons: (1) Low frequencies model the smoothest global signals w.r.t. the high-level graph struc- ture (see Fig. 3 & A. (2) Gama et al. (2020) find that, under a relative perturbation model (per- turbation budget proportional to connectivity), stability implies
Hunterral-Lisshitznes (3C > 0: |^45/aa| s C). i.e., the filter can vary arbitrarily around zero but must level out towards larger X. Stability to graph perturbations is strong domain- -agnosic prior. (3) Many physical long-range in- teractions are power laws with a flattening frequency response. For example, we construct an explicit graph filter modeling the electric potential of charges in a ID "ion crystal" ( G) and find that low- pass window is optimal. (4) Sequence models like Hyena (Poli et al. 2023) apply global low-pass filters through their exponential windows. (5) Cai al. 2023) prove that MPGNN plus virtual node (see S E) can emulate DeepSets (Zaheer et al. 2017) )) and, thus, approximate self-attention to any precision. Nonetheless, we find that virtual node alone does not necessarily yield good gener- alization ( 3.1.1 & 4.I). (6) Nonlinearities "spill" features between frequency bands (Gama et al.) 2020). This includes spillage from higher frequencies the band of the spectral filter. Gaaa al. (2020) argue that this spillage makes it possible to learn stable yet expressive graph filters and is also feature of stable message passing models.
J.4 Scaling to Graphs of Different Magnitude
For scaling a single to graphs of different orders of magnitude, it can be beneficial to rescale the eigenvalues before learning the filter åæ (A). That is, we use d (Å) with rescaled X.
For example, the eigenvalues for a path/sequence are A (1 cos(*s/n)). Thus, the resolution is poor, especially for the cigenvalues close to zero since cos approaches slope O. For this reason, we consider rescaling the eigenvalues with
}y 1/x cos -ooosss(1110 - A1)
(32)
or
x, = 7/- cos- (1 X,)
(33)
The latter is, e.g., convenient for identifying the second lowest eigenvalue regardless of n. Due to the poor numerical properties of these relations, we evaluate cos (1- AÚ) ttan aann' - 1-))) instead.
cos-1(1
J.5 Spectral Normalization
While the GFT and its inverse preserve the norm of the input (c.g., || = ||V æ||2 = | this not true if operating on a truneated frequency spectrum if the filter (A) suppresses certain frequencies. For example, in the example of a virtual node (for simplicity here with L = D - A), signal æ that is zero at every node but one at single node, then the signal will be equally scattered to every frequency. Then, suppressing all frequencies but X = 0, yields || [| (0) V VT = 1/V5.
Motivated by this unfortunate scaling, also consider normalization in the spectral domain. Specifically, we normalize H ( [ E gexd s.t. H, + (1aa) AA with learnable a [0, 1]d. This allows, e.g., broadcasting a signal from one node without impacting its scale. However, we empirically find that this normalization only helps only marginally in the over-smoo experiment (Di Giovanni et al. 2023a) and otherwise can destabilize training. We also consider variants where the norm in the spectral domain is scaled with the norm of the signal
37

---

in the spatial domain with more or less identical results. We hypothesize that such normalization counter-prood produccve for, e.g., bandpass filter if the signal does not contain the corresponding frequencies.
J.6 Adjusting S'GNNs to Directed Graphs
For the spectral filter of Eq. 3 we fg (H))
H [o(HO G.R. +
o (HO G.a)] and subsequently map the result of Spectral back the real domain, e.g., using (H)(-1)) E. and real R(-) as well as imaginary component 3-)). For the positional encodings PE(V (V, A)
" (eeRR((peece (((()))) + wg
(H(-)))), (H with learnable weights w 33
(!) (!)
of 3.2.4] we use A, in [g. 5) and concatenate real as well as imaginary components. The neural
network for the spectral domain sc of 3.2.2 generalizes without adjustment. Similar to Koke &
Cremers 2024). one could also employ complex weights; however, we do not.
J.7 Computational Remarks
We use readily available eigensolvers (scipy) and, thus, use a fixed number of eigenvectors (typi- cally k < n) instead of determining k based on Acut- The partial eigendecomposition is of complex- ity (kk) for m edges, while the spectral filter has complexity (kdn)). On different remark, batch multiple graphs using block diagonal matrices (Fig.
Spectral graph-level readouts. The key insight is that fre- quencies are a global concept, and hence, the GFT can be used for global readouts in graph-level tasks. With k < n, such readout is practically free in the presence of intermediate spec- tral layers and of Okk) otherwise. Thus, there is the oppor- tunity for a computationally convenient aggregation of global information, including sort of graph-level "jumping knowl- edge" (Xu et al. 2018). The only caveat is that the Fourier coefficients are unique due the ambiguity in the eigende- composition. To maintain permutation equivariance, we take the absolute value and aggregate over dimension We observe that such intermediate readout can improve performance slightly, e.g., on TPUGraphs. However, we leave systematic evaluation of its benefits for future work.
A
Vi
Aa
W
A
0
Vi
Σ
Figure 17: Block diagonal batch- ing for spatial and spectral filters. [q. 4 instead of the multiplication with V.
Linear bottle necks. To circumvent overfitting, we commonly replace the linear transformations (fi(0) ()) and (A) with low-rank bottlenecks W, W,,W s.t. W E gdxd, W2 dxd
W in f W1 Rdd and d'
K
Limitations
We expect that many common graph benchmarks do not have only insignificant long-range inter- actions. We observe that MPGNNs are less likely to overfit, perhaps since locality is a good inductive bias in many circumstances (Bronstein al., 2021). Moreover,
observe that the spectral filter
$ 3.2. may converge slowly and get stuck in local optima. We find that a sufficient amount of randomly initialized filters mitigates this issue large extent. Further, can introduce inductive biases via windowing functions (Fig. 7). like the exponential window used by Hyena (Poli et al. 2023
Even if the true causal model generating the target consists of long-range interactions, it might be sufficient to model the training data solely using (potentially spurious) local interactions. This might be especially true if the training nodes are samples from a "small" vicinity of the graph (e.g.. OGB Products (Hu al. 2020)).
Closely related to the previous point is the amount of available training data. We hypothesize that SºGNNs are more data-hungr than their purely spatial counterpart. That is, to reliably detect (non- spurious) lang-range interactions in the training data, a sufficient amount of data required. Similar findings have been made, e.g., in the image domain (Dosovitskiy et al. 202I).
38

---

Except for heterophilic graphs, direction plays small role in graph machine learning even though many benchmark tasks actually consist of directed graphs (Rossi et al.) 2023). Moreover, there is lack of benchmarks involving directed graphs, which require long-range interactions. Note that most of the theoretical findings generalize to directed graphs under appropriate modeling deci- sions/assumptions. However, we do not make this discussion explicit since MPGNNs for directed graphs are still actively researched.
Since a lot of the previous points hover around the insufficiency of the available benchmarks, we propose two new tasks 4.1 and derive further datasets, e.g., for associative recall.
While we demonstrate the practicality of S'GNNs in $ 4.3 on large-scale benchmarks, the partial eigendecomposition EVD starts to become costly the largest graphs use for evaluation. Even though we did not experiment with lowering the requested precision, etc., we expect that for scaling further, naïve approaches might not be sufficient. One direction could be to utilize GPUs instead of CPUs or to adapt concepts, e.g. from spectral clustering (von Luxburg (007).
Even though there are many important reasons why we should utilize spectral filter on the low end of the spectrum, there might be tasks for which this choice suboptimal. One way to estimate the frequency band to which one should apply spectral filter is via polynomial regression and then de- termine where the derivative is maximal. Note that it is efficient to calculate the eigenvectors around an arbitrary location of the spectrum, e.g., with the 'shift-invert mode" of scipy/ARPACK (Lehoucg ct al. 1998).
Due to the many possible design decisions of spectrally parametrized filters, the neglect of spectral filters in prior work, and the lack of appropriate benchmarks, it was not possible to ablate all the details. We expect that future work will discuss the specific building blocks in greater detail.
L Broader Impact
We expect that S'GNNs will have similar societal implications as other model developments like Convolutional Neural Networks (CNNs) (LeCun et al. 1989), LSTMs (Hochreiter & Urgen Schmid-
huber 1997), transformers (Vaswani et al. 2017). or modern Graph Neural Networks (Gimmer et al., 2017). Since such models may be used as building blocks in architectures for predictive tasks, gen- erative modeling, etc.. they have a wide range of positive and negative implications. Nevertheless, expect that S'GNNs will not have more negative implications than other machine learning model innovations.
M Experimental Results
This section provides further details the experimental setup ( M.I. the computational cost S M.3). and graph constructions with additional experimental results for the clustering tasks S M.66; likewise we provide details for the distance regression (8 M.7). arXiv-year ($ M.8), and pro-
vide nodes on the graph construction in TPUGraphs ( M. Note that the sections on clustering
$ M.6) and distance regression ( M.7 also contain ablations and further insights.
M.1 Experimental Details
Implementation. The code base is derived from Cao et al. (2023), which on the other hand derive the code of Rampášek et al. (2022). The implementation heavily relies PyTorcc geometric (Fey
& Lenssen 2019).
Datasets. We collect the main statistics, including licenses, for the datasets in Table 6 The provided code will download all datasets along with the experiment execution, except for TPUGraphs, where one should follow the official instructions. Due to the high variation in results, merge all "layout" datasets and present the results on this joint dataset. We use the fixed public splits for all experiments and proceed accordingly for our datasets (see S M.6land ß M.7).
Hyperparameters. While we provide full parameters for all experiments and models in our code, we gather an overview of the used G*GNNs variants here. The parameters were determined through cascades of random search throughout the development of the method. We list the most important parameters in Table 7
39

---

Table 6: Dataset statistics and licenses.
Name
of graphs
Avernge of nodes
Average edges
Task
License
Poptides func Dwivedi et al. 2022
15,535
150.9
307.3
classification
gruph multi-lahel
CC BY-NCCC 4.0
Poptides upad Dereer
307.3
graph regression
BY-NCC4
CLUSTER (Dwavedi et a 2023
12,000
117.2
4,301.7
node classification
CC-BY 4.0
LR-CIISTTR (ORPS)
12,000
896.9
6,195.1 1
onde classification
CC-RY 4.0
Thee Distance regression (ours)
55,000
749.2
748.2
mode regression
CC-BY 4.0
DAG Distance regression (ours)
55,000
748 6
821.8
mode regression
CC-BY 4.0
Ovenquashing ottcaded
(derived from (Di Giovanni al. 2023a
730
43.8
231.9
node classification
CC-BY 4,0
Assoclative rocal
(derived from (Poli al. 2023
26,000
524.7
523.7
node classification
CC-BY 4.0
Associative recall 30%
(derived from
2023
30,003.8
30,002.8 8
classification
CC-BY
OGB arXiv (Euu 2mmm 4uk0
169,343 343
1,166.243
node classification
MIT
0GB Products (Tire 2000
2,499,029
61,859,141
node classification
MIT
TPU'rrppss [Pli0
2023
=31,000,000
graph ranking
Apacho License
Usage of external results. The performance of baselines is commonly taken from leaderboards and the respective accompanying papers. This specifically includes the results in Table 1 Table 2 and Table 11
Setup. For clustering ( M.6). distance regression IS M.7 and arXiv-year ( M.8 we report the detailed setup in the respective sections. For the other tasks, the relevant details are:
Peptides: We follow the setup and implementation of Raappššk et al. (2022). That is, we
train for 250 epochs with a batch size of 200. We rerun experiments on 10 random seeds.
Over-squashing: We derive the setup from Di Giovanni et al. (2023a). In the main part (Fig. 5), for the GCN, we report the numbers of their Figure for GCN on "Clique Path" graphs. For the spectral filter, we actually consider the more challenging setting where we do not train one model per graph size. Instead, we train one model for all sequence lengths. The task is to retrieve the correct of five possible classes on the other end of the graph. the extended experiment of Fig. 12] we compose the dataset of "Clique Path" and "Ring" graphs (see Di Giovanni et al. (2023a)) To avoid m Onn²), limit the fully connected clique to 15 nodes. For training and validation, we enumerate all graphs with even E {4. 6, 50} and train for 500 epochs. For test, enumerate the graphs with even n E (52, 54...... 1003. We rerun experiments on 10 random seeds.
Associative recall: We construct one dataset consisting of key-value sequences of length 20 999. As Poli et al. (2023), use vocabulary of 30. We sample 25,000/500 ran- dom graphs for train/validati
For the test set, we randomly generate 500 graphs for the sequence lengths of 1,000 to I, 19199. We train for 200 epochs. In the experiment with val- idation/test sequence length 30k (Table 2). we generate 10,000 training graphs of length 29,500 to 30,499 and finetune SCGNNGGCN from the smaller setup. We rerun experiments on 10 random seeds.
Table 7: Important SCGNNS specific hyperparameters and runtimes. The times for the EVD cover the respective dataset entirely.
Dataoot
MP layers
upec. layers
Dim.
il spoc. filters per layer
eégenvectors frequency cuteff Ave
Spectral NN
Train
time
EVD time
GPU
Notes
Pepeides-Tunc
214
128
Aua 0.7
X
1bb
2mm
(0801)
PepridesStract
260
260
Aua 0.7
1b
2
1087T1
18
Aug 13
1:3h
4min
1R-CU2STIE (ours)
138
128
A- Aue 0.05
min
4min
Distmax regaession
(ours)
5
A) 50. Ace 0.1
3b
1.5h
10800 pussible
smalles butch
estended
Overguushing
0.05
3s
eigenaatne manstoon 32 expenetta
Asseciative recall
1o 10
3b
closed
year Open
A.
Renchwark Preditcts
100 - 0,006
11h
eigemaltee
A.a
40h
40

---

OGB Products: Even though full-graph training with 3 layers GCN plus one spectral layer fits into GB A100 GPU, we find that batched training works better. We randomly divide the graph during training into 16 parts and train 6-layer S'GAT with spectral layers after the second and last message passing step. Inference is performed on the entire graph at once. We rerun experiments on 5 random seeds.
This is the only dataset where the procedure detailed in S 3.2.1 We fix the number of eigenvectors to A = 100 and do not apply any windowing. Due the large variation of results, we merge all "layout" tasks into a single dataset. Since the default graph construction is not able to express all relevant information, we adapt it detailed in [ M.10) however, the empirical impact was small. TPUGraphs "layout" consists of few hundred distinct graph structures with large variation on the node-level configuration//catures. We sample 10,000 configurations for each graph structure of each "layout" sub-split. Here, we introduce two batch dimensions: (I) batching over multiple graphs and (2) batching over the configurations. step of the 1,000 epochs, we sample small subset of configurations per graph structure and apply a pairwise hinge loss rank the configurations. We do not perform random reruns due to the computational cost.
TPUGraphs:
transformer model instead of
each training
M.2
Qualitative Experiments
In Fig. 6
and Fig. 8
we provide qualitative insights about the approximation of filters and ringing.
In Fig. 6 we construct true filter by adding discontinuous filter À 0 and polynomial filter of order 3. For the spectral part, we use the true filter values and fit a Chebyshev polynomial on the remaining part. We then plot the response of the true filter and its approximations a path graph with 21 nodes and L
D-1 A.
Similarly, in Fig. 8 perfect low pass (k 25) and approximate a rectangular wave.
path graph with 100 nodes and L I D-
A. We then construct
M.3
Computational Cost
We report the computational cost for the experiments in Table 7 for a single random seed. On top of the pure cost of reproducing numbers, we conducted hyperparameter scarches using random search. Partially, we required 100s of runs to determine good parameter ranges. A generally well- working approach was first to reproduce the results of the best available MPGNN in prior work. Thereafter, we needed to assess how likely additional capacity would lead to overfitting. Usually, we reduced the number of message- peessage-passing steps, added the spectral filter, and determined appropriate values for the number of eigenvectors
In the light of overfitting, it is a good idea to lower the number of Gaussians in the smearing of the filter parametrization (S 3.2.T. introduce bottle-neck layers and use fewer spectral filters than hidden dimensions.
Runtime with precalculated eigenvectors. In Fig. 18 convolution with spatial messages passing on ogb-arXiv (170k nodes) of Hu et al. (2020), using an Nvidia GTX 1080Ti. This essentially compares sparse matrix multiplication (adjacency matrix)
contrast the runtime cost of spectral
Number message passing steps
GCN
200
Spec.
Runtime
100
1000 2000 3000 4000 5000 Number of cigenvectors k
Figure 18: Runtime comparison on arXiv (w/o EVD) using k = 2, 500 for the spectral filter.
41

---

with matrix multiplications on dense "tall and skinny" matrices (GFT). we find that one GCN-layer here is as costly as a spectral filter with approx. & 500 eigenvectors.
Large-scale benchmarks. On the large-scale datasets OGB Products and TPUGraapss, we perform full-graph training (without, e.g., segment training (Cao al. 2023) using DirGCN layers inter- layered with spectral filters targeting a pair-wise hinge loss. The spectral GNN uses the Magnetic Laplacian incorporate direction. The spatial MPGNN closely resembles the model of Rossi al. (023), except that we half the dimension for the forward and backward message passing and con- catenate the result. We shrink the dimensions model the direction at very low cost. We conclude that GN can be very practical even if applied at scale and can effectively model long-range interactions also on large graphs.
Dense
Sparse
Time cost s
10
Time cost s
10'
10P
100
10-1
10-1
10-2
10-2
0
2000
0
10000
Number of nodes
Number of nodes n
(a) scipy (CPU)
(b) PyTorch (GPU)
Figure 19: Runtime of partial eigendecomposition k = 25 Erdós Rényi graph with average degree
5. Dashed mark directed/Hermitian Laplacian.
Eigendecoopositon. We show the computational cost for the eigendecomposition of a random Erdös Rényi graph (every edge has equal likelihood be drawn). We scipy (CPU) and PyTorch (GPU) with default arguments. For the sparse decomposition with PyTorch, we use the svd_lowrank method. Note that the default parameters for PyTorch are usually leading large numerical errors. Fig. 19 demonstrates that the cost of the eigendeconposition is manageable. For large graphs like ogbn-products (2.5 mio. nodes), the EVD takes around 30 minutes with k: 100 on 6 CPU cores of an AMD EPYC 7542. Note that the default parameters of the eigensol ver allow for 1000s of iterations or until the error in the 32-bit float representation achieves machine precision.
M.4 SºGNN Aggregation Ablation
In the main body we present two ways to combine a spatial and spectral filter: additive combi- nation (Eq. 1) and an arbitrary sequence of filters (Eq. 2). In this section, we perform ablation analysis on the peptides-fune benchmark and report the results in Table 8
Instead of summation of the spatial and spectral parts, concatenation another possible op- design Spectral and Spatial() to map
tion. Getting input features (1-1) E x to IR" xg and update the embeddings as
H (1) Spectral (H V) Spatial (H A).
(34)
Additionally, consider normalization of the addends at the end of each embedding update, dividing by 1/v2 (concatenation w/ residual) and 1/v3 (summation w/ residual) as attempt to keep the variance constant.
Inspired by recent advancements in state space models like Mamba Gu & Dao 2023). we also consider modeling update step in similar way, identifying the convolutional part with Spatial and the SSM part with Spectra)
The following table shows results for the different design choices to combine the spatial and spectral parts, with all hyperparameters being precisely the ones reported in Table 7 for peptides-func.
42

---

Table 8: Ablation of different aggregation functions the peptides-func benchmark, with our PE.
Agyregation
Normalization
params
Test AP (t)
322k
0.6527 0.0055
322k
0.6783 0.0023
323k
0.7235 0,0059
323k
0.7171 + 0.0070
Mamba-like
474k
Sequential
N/A
323k
0.7311 1 + 0.0066
M.5 Number of Eigenvectors Ablation Peptides-Fune
In Fig. 20 we ablate the number of eigenvectors on the real-world dataset peptides-func Since we here limit the number of eigenvalues by cut-off frequency Acut, we report the average number of cigenvectors.
Average Precision (AP)
0.74
Avcrage Precision (AP)
0.74
0.72
0.72
0.70
0.70
0.68
0.68
test
test
0.66
val
0.66
val
0.00
0.25
0.50
0.75
60
80
Cutoff frequency Acal
Average number of eigenvectors k
Figure 20: Average precision vs. number of used eigenvalues on the peptides-func long-range bench- mark task via frequency cutoff Aan-
M.6 Clustering Tasks
We use clustering task LR-CLUSTER based on Gaussian Mixture Models (GMMs), which requires long-range interactions measure the ability of SºGNN to spread information within clusters and consider the original CLUSTER task from Dwivedi et al. (2023) based on Stochastic Block Models (SBMs) in order to measure the ability to discriminate between the clusters. The differences apparent from an illustration of some exemplary graphs Fig. 21 & 22 While LR-CLUSTER has long-range interactions, the challenge of CLUSTER is to discriminate between the clusters. Without the arrangement of nodes, colors, and different edge weights, for CLUSTER, it is virtually impossible to discriminate the clusters by visual inspection.
(a)
(b)
(c)
Figure 21: Examples of generated graphs for the LR-CLUSTER task (GMM). Labeled nodes are marked red.
43

---

(b)
(c)
Figure 22: Examples of generated graphs for the CLUSTER task (SBM). Labeled nodes are marked red. Edges within clusters are highlighted.
Nevertheless, find that the spectral filter is well aligned with the cluster structure in these tasks. We plot this some exemplary filter in Fig. 23 The findings match the explanations of 4.1 also for CLUSTER.
Vdiag(ão
VV
(dia
Vdiag( a.)
(A)) VV
(a)
Vdiag( 1)
Vdiag(āo aa)
Vdiag(āa(A) sV (A)
(b)
Figure 23: SBM-based (a), visualized in Fig. 21a and GMM-based (b), visualized in Fig. 22a graphs along with four learned filters. Large entries are yellow, small are blue, and white lines denote clusters.
In the remainder of the section, we provide full details of the experiment setups. Moreover, we provide additional results not presented in the main text, including ablations.
M.6.1 GMM Clustering CL-CLLSEER
Setup. To sample an input graph, we start by generating C 6 p-dimensional cluster centers Me UOO, 1002 for E {O...., C' 1} (we use p 2). Next, draw n. {100..... 199] points Tie ~ (N(e, 41p) which will represent the nodes of the graph. Subsequently, we update the class memberships such that every point is in its most likely class according to the underlying probabilistic model. Finally, we connect each node v to its e, ~ U(f1,...
10}) closest neighbors by Euclidean distance || 112. This whole procedure is repeated until the generated graph is connected. We then discard the location information and only keep the graph structure. In this way, we generate graphs of average diameter of 33. See Fig. for depictions of example graphs.
Apart from the graph generation procedure, we adhere closely Dwivedd et (2023): introduce input features in {0, 1, 2, ..... C... where a feature value of I,..., ., C' corresponds to the node
44

---

Table 9: Accuracy the GMM clustering task for varying number of eigenvectors k. using GCN layers and one spectral layer in the end.
(MPGNN)
(Virtual Node)
S'OCN
0,4546
0.0002
0,4646
0.0001
0.6786
0.0010
0.7429
0.0026
0.7971 + 0.00U8
SPGON (+ PR)
0.4546 + 0.0002
0.4642 + 0.0007
0.7221 + 0.0008
0.7860 + D.0005
0.8202 + 0.0011
5
7
10
0.8322 0.0004
0,8511
0,0008
0,8510
0.0008
0.8519
0.0006
0.8517 = 0.0006
0,8513 = 0.0018
0.8440 + 0.0006
0.8538
0.0012
0.8548
0.0011
0.8546
+ 0.0002
0.8545
0.0005
0.8554
0.0005
Table 10: Accuracy on the GMM clustering task for varying number of MP layers, while comparing purely spatial GCN model to S*GCN with one spectral layer added in the end.
2
4
5
GCN
0.270U + 0.0002
0.3537
0.0000
0.4544 + 0.0003
0.5521 + 0.0001
GCN (+ PE)
0.2684 + 0.0005
0,3532 + 0.0015
0.4550 + 0.0004
0.5526 + 0.0006
S'GCN
0.8517 + 0.0003
0.8520 0.0008
0,8518 : 0.0005
0.8512 : 0.0002
S'GCN (+
0.8517 + 0.0007
0.0010 0.8550
0.8552 + 0.0015
0.8539 + 0.0010
10
0.6367 0.0001
0.7013 + 0.0001
0.7448 + 0.0003
0.7708 + 0.0007
0.7860 + 0.0004
0.6387 = 0.0012
0.7104 + 0.0011
0.7609 = 0.0009
0.7931 + 0.0005
0.8135 + 0.0007
0.8512 0.0008
0.8509 + 0.0008
0.8511 + 0.0003
0.8504 + 0.0009
0.8509 + 0.0006
0.8552 0.0008
0.8542 0.0004
0.8541 + 0.0008
0,8536 + 0.0013
0.8542 + 0.0008
being in class c 1 and a feature value of means that the class is unknown and has to be inferred by the model. Only one node Ue per class is randomly chosen to be labeled and all remaining node features are set O. The output labels are defined as the class labels. We use weighted cross entropy loss for training and class-size-weightes accuracy as a target metric. We generate 10,000 training and 1,000 val/test graphs each and report the average + standard deviation over random reruns.
Models. As an underlying spatial model baseline, we use a vanilla GCN (Kipf & Welling 2017). We compare this to S'G only applying one spectral convolution immediately before the last spatial layer. We investigate the influence of the number k E 10. 10} of eigenvectors to be taken into account with 4 spatial layers, with k = indicating the absence of spectral layer (see Fig. 10a and/Table 9 for the underlying data). We also vary the number of spatial MP layers from 2 to 10 and compare the performance of purely spatial GCN to the corresponding S2GCN with one spectral convolution (see Fig. 10b) and Table 10) for the underlying data).
Throughout all evaluations, we maintain a consistent hyperparameter configuration: Specifically, we use an inner dimension of 128, GELU (Hendrycks & Gimpel 2016) as an activation function, no dropout, and residual connections for all spatial and spectral layers. For the spectral layer, we
implement the gating mechanism f("), but abstain from a neural network in the spectral domain ( 3.2.2), bottlenecks, or parameter sharing. We train for 50 epochs with batch size of 50, using the AdamW W optimizer (Loshchilov & Hutter) 2019) with a base learning rate of 0.003, a weight decay of 0.0001, cosine scheduler and warmup epochs.
Further discussion. The clustering task comes naturally to S²GCN, as a spectral layer can simulate certain variations of spectral clustering (von Luxburg 2007): Suppose (1-1) E R a one-hot encoding of the cluster labels, i.e. H de,e. with c E {1,..., C} and v, being the unique labeled node per class. In its simplest form, taking a( (2) = 1 and f(( = id, the spectral layer Spectral") from Eq. 3 turns into (O) VVT T H (1-), Hence, H!! V V Vr.: Ve. encodes notion of similarity between a node e and each labeled node Ve. This relates to the Euclidean distance
V|Ve Vo...l2 = / VI..1. + VI. 2V Vo..: which more typically used for spectral clustering.
45

---

M.6.2 SBM Clustering CLUSTER (Dwivedi et al. 2023
Setup. We conduct ablation study the original CLUSTER task (Dwivedi et al. 2023), which uses a similar setup to our GMM clustering task, however drawing from SBM instead: For each cluster, nhe (5,.... ........ 35) nodes are sampled. Nodes in the community connected with probability of p = 0.55, while nodes in different communities are connected with a probability of q 0.25. While there no need for long-range interactions in this task, considering that the average diameter of the graphs is just R 2.17, separating the clusters is much harder than in the GMM clustering task (see Fig. 23 for example adjacency matrices from the SBM and GMM models). We use weighted cross entropy loss for training and class-size- class-size-eigghted accuracy as target metric. We report the average standard deviation over random reruns.
Models. In our ablation study, we consider GCN Kipf & Welling 2017). GAT (Velčkkovi et al. 2018), and GatedGCN (Bresson & Laurent 2018) as MPGNN baselines, following a setup similar to Dwivedi et al. (2023). We consider models with 4 layers (roughly 100k parameters) and 16 lay- (roughly 500k parameters), while keeping most hyperparameters the as in the benchmark, including inner dimension, dropout, and the number of heads for GAT. However, our reported base- line results and parameter counts differ slightly as we are using different post-MP head, where we maintain a constant dimension until the last layer, in contrast to Dwivedi et al. (202)) who pro- gressively shrink the inner dimension. We construct the corresponding S-GNNS by modifying each baseline model, replacing the 3rd and the /15th layers with spectral layers, ensuring roughly equivalent parameter count. Additionally, each model is optionally supplemented by our positional encodings PE ( 3.2.4).
We further conduct hyperparameter search the most promising base MPGNN candidate, Gat- edGCN, which leads to an optimized version of SNGNN. This optimized model has 18 spatial MPGNN layers, spectral layers between all spatial layers, and additional RWSE encodings. The inner dimension is adjusted to keep the model well below a parameter budget of 500k. Finally, we also evaluate GCG and SA using these hyperparameter settings.
Throughout all evaluations, GELU (Hendrycks) & Gimpel, 2016) as an ac- tivation function, residual connections for all spatial and spectral layers, and im- plement the gating mecha- nism f(() without employ- ing a neural network the spectral domain. We use a batch size of 128 for train- ing the 4-layer models and 64 for all other models. For the spectral layer, we use the partial cigendecompositionn corresponding the lowest k 50 eigen- values (k 100 for the optimized S2GNN versions), spectral normalization, and Acut = 1.3. For the optimized models, we employ parameter sharing with 128 heads, and a bottleneck of 0.25 in feature gating. We use 8 attention heads for all GAT versions in accordance with Dwivedi et al. (2023) (in-
Hisc MEGNN
SPONN
Basc MPUNN (+PE)
SPONN (+PI)
GCN
GAT
GatoIGNN
0.88
0.8
0,8
Test accumcy
Tet accumcy
Teat accumecy
0.7
6.7
0.7
0.6
0.6
0.6
0.5
layers
layees
4aaees
Layers
4aayes
layen
Figure 24: Effects of the spectral part on SBM clustering performance for different base architectures.
Table 11: Results the CLUSTER task (Dwivedi et al. 2023 Transformer models that outperform our GGGateGGCN are underlined.
Model
Accuracy (*)
ARGNP Cai al.
2022
0.7735 0.0005
GNN Transformer
GPS Rampasek
2022
0.7802 0.0018
TIGT Choi et
2024
0.7803 0.0022
GPTrans- Nano hen et
2023
0.7807 + 0.0015
Exphormer Shirzad et al.
2025
0.7807 + 0.0004
EGT (Hussain al 2022
0.7923 + 0.0035
GRIT (Ma al. 2025
0.8003 0.0028
GatedGCN
0.7608 0.0020
S GGatedGGN (ours)
0.7808 0.0005
46

---

Table 12: Ablation results the SBM clustering task (Dwivedi et al. 2023 accuracy is bold, second is underlined.
The best mean test
MPGNN base
# total
Inner dim.
Spec. fillers
Pos. enc.
Dropout
# params
Train accuracy (t)
Test accuracy (t)
layers
K
0.0
109k
0.5059 + 0.0018
0.5037
0.0023
X
V
0.0
117k
0.5053 : 0.0010
0.5026
0.0006
146
I
X
0.1
117k
0,6492 1 0.0009
0.6545
0.0013
GCN
1
/
0.1
125k
0.6663 + 0.0020
0.0021 0.6640
X
X
0.0
508k
0.7354 : 0.0009
0.7190
0.0010
X
V
0.0
517k
0.7378 1 0.0017
0.7194
0.0010
16
172
2
X
0.1
527k
0.7535 + 0.0011
0.7359
0.0017
2
536k
0.7526 + 0.0021
0.0011 0.7269
18
124
17
PE +RWSE
0.2
491k
0,8022 1 0.0147
0.7711
0.0020
X
0.0
120k
0.6705 = 0.0008
0.6525 0.0010
X
V
0.0
128k
0.7167 = 0.0001
0. 0.6680 0.0020
152
I
X
0.1
128k
0.7093 1 0. 0.0007
O. 6960 0.0010
GAT
1
0.1
136k
0,7398 = 0.0006
0.7065 = 0.0007
X
X
0.0
541k
0,8537 = 0.0025
0.7126 0.0014
X
V
0.0
549k
0.8740 = 0.0014
0.7139 = 0.0022
16
176
2
X
0.1
558k
0.8723 = 0.0013
0.7277 = 0.0005
2
567k
0. 8.8836 = 0.0005
0.7232
0.0010
18
120
17
PR RWISE
0.1
469k
0.8071 # 0.0262
0.7681 = 0.0003
X
X
0.0
106k
0.6181 + 0.0020
0.6039 0.0019
X
V
0.0
110k
0.7292 = 0.0031
0.6889
0.0027
70
GatedGCN
X
0.1
90k
0.6933 + 0.0003
0.7050
0.0001
94k
0.7245 + 0.0002
0.0018 0.7217
X
X
0.0
505k
0,8667 T 0.0019
0.7369
0.0011
X
V
0.0
509k
0.8753 + 0.0257
0.7314
0.0058
16
78
X
464k
0.8086 + 0.0016
0.7627
0.0010
468k
0.8302
0.0011
0.7659
18 64 17
PE +RWSE
0.2
460k
0,8202 + 0.0024
0. 7808 0.0005
ner dimension is not expanded but split up), except for the optimized version, which uses heads. p 0.0 dropout (similar to Dwivedi al. (2023)) ). We
For the purely spatial models, observe this to lead to overfitting for models with spectral layers, for which we set
{0.1, 0.2). Hyperparameters differing between the compared models listed in Table 12 We train for 100 epochs using the A optimizer (Loshchilov & Hutter (019) with a base learning rate of 0.001, weight decay, and cosine scheduler with 5 warmup epochs.
Introducing spectral layer significantly enhances performance on the 4-layer architectures, both with and without positional encodings. The effect is most pronounced on GCN, where replacing just a single GCN layer by a spectral layer boosts accuracy from 0.504 to 0.655. Notably, introducing two spectral layers still has a consistent positive effect on all 16-layer architectures.
Results. Results for the CLUSTER task are presented in Table 12 Table 11 Fig. 24
M.7 Distance Regression
Setup. We generate directed random trees with one source by sampling trees with (500.... .999 nodes, picking one node at random to declare as a source and introducing edge directions accordingly. To construct random DAGs with long distances, we start from such directed random trees and proceed by adding nn/10 edges at random, choosing each edge direction such that the resulting graph still DAG. Additionally, we mark the source node with a node fea- ture. Besides evaluating all models in an in an-distribution regime, we also assess the generalization power of the methods by drawing outtt--distribution val/test splits from slightly larger graphs of {1000,... ... 1099) and n E {1100... ... 1199) nodes each. We use 1,2 loss for training and R² as a target metric. We sample 50,000 training and 2,500 val/test graphs each and report the average + standard deviation over random reruns.
47

---

0.8
0.8
0.6
0.6
loyers
Accuncy
Accuna
Actanay
0.4
0.4
0.4
0.2
0.2
0.2
50
100
50
100
0
50
100
0.8
0.8
0.8
16 layers
0.6
0.6
0.6
Acurayy
Aosesy
0.4
0.4
0.2
0.2
0.2
50 Bzech
100
Spacc
Eprch
GCN
GAT
GatedGCN
Figure 25: Test accuracy curves for the SBM clustering task. Curves are shown for the models from Table 12 with PE, with the MPGNN baseline and the respective GNN
Table 13: Results on the distance task, with DirGCN as base. The best mean score is bold, second underlined.
+Spec.
In-distribution RMSE(L
out-of-distcbution RMSF(()
filter
MAP(()
A (1)
M MAP(L)
k (t)
X
X
7,0263
0,0033
9.0950 0.0005
0.1915 0.0001
8.1381 1. 0.0068
10.7735 1 0.0002
0.1214
0,0098
0.0002
0.0018
0.00017
0.1745
0.0003
DAGs
undir:
1,8248 0.0116
3.2987
0.0100
0.8956
0.0006
3.0471 4: 0.0192
4.9467 0.0263
0.8148 0.0020
undic:
1.7984 0.0033
2 2.0034
0.0046
0.9124 = 0.0009
2.7950 + 0.0041
4.5834 = 0.0117
0.8410 0.0088
clinec.
X
1,2401 (101733
2. 3.1600
0.0340
0.9644 0.0014
2.1824 + 0.0787
3.7034 = 0.0710
0,8924 0.0020
Clinec:
16166
0. 0032
2.04288 1: 0.0066
95952 : 0008
2,0565 :: 0.0326
5 5.5887 : 0.0444
0 0.9025 : 0.0024
X
17.3902
+ 0.0699
0.0144
Trees
undic.
X
X
11,6316
1.0236 0.0408
0.0370
15.0123
1,7991
1 0.1956
0.0249
0.3282 a: 0.0022
0,9902 1 0.0020
14.9837 4. 0.0501
1.5981 1. 0.2221
19:3639 =: 0.0610
2,7377 1. 0.1786
0.2110 0,0050
0.9839
0.0053
undir.
1,2887
0.1195
2.0095
0.2638
0.9678
0. 0.01
1:7184 1: 0.3088
2.5791
0 535322
0.9856
0.0055
1.2224 0.7600
1,5280 0.4630
2.2042
0.7582
0.9881
0.7767 0.3306
1.1612 0.5839
0.3964
= 0.0041
0.9911 :: 0.6911
1.6064
: 1.0206
0.9938
0.0077
Models. As a MPGNN baseline, we use five-layer directed version of GCN, DirGCN (Rossi) jet al. 2023), with three post-messgg- layers, and concatenating instead of averaging over the source-to-target and target-to-source parts. We compare these baselines to DirGGGN of the form Eq. 2 with four spectral layers, alternating spatial and spectral convolutions and employing residual connections. We benchmark versions of S DirGGCC that ignore edge direction in the spec- tral convolution against directed versions in which we set q = 0.001. In all cases, we use the partial cigendecomposition corresponding to the A 50 lowest eigenvalues. All models are optionally en- riched by the positional encodings from S 3.2.4 Throughout all evaluations, we use an inner dimen- activation function, and dropout p 0.05. For the spectral layers, we utilize the gating mechanism (()) not employing a neural network in the spectral domain, layer. We train for 50 epochs, using a batch size of 36 and the AdamW optimizer (Loshchilov & Hutter 2019) with base learning rate of 0.001, weight decay of 0.008, and a cosine scheduler with warmup epochs.
sion of 236, GELU (Hendrycks & Gimpel (016))
spectral normalization, Acut = 0.1, and bottleneck of 0.03 in the spectral
Results. In Table 13] we show the performance of the different models on DAGs and trees. We observe that the simple MPGNNs are notably surpassed by all versions of DiDGGGN. While DiDiGGCN achieves nearly perfect predictions on the tree tasks in both the directed and undirected case, the undirected version outperformed by the directed version on the DAG tasks. Here, per- formance also reduces slightly in the oft-t--diitributtinn regime. The great performance the tree
48

---

DirGON
DirGCN
D'DIGGNN (+PE, undir.)
S DDiGGNN (+PE, direc.)
15
30
30
RMSE
10
RMSE
RMSE
22
RMSE
20
10
0
40
0
40
Ground truth
Ground truth
Ground truth
Ground truth
40
60
60
Prediction
Prediction
Prodiction
Prediction
80
80
20
20
220
40
Ground truth
Ground truth
Ground truth
Ground truth
DAGs (in-sample)
DAGs (out of sample)
Trees (in-sample)
Trees (out of sample)
Figure 26: RMSE and 90% prediction intervals for distance predictions by ground truth.
task due the fact that trees are collision-free graphs (Geisler al., 2023), where the phase of each eigenvector is exp(i2ng(d) + c)) for each node with d, representing the distance to the source node and noteworthy that simple MPGNN with positional encodings, despite having the distances (shifted by c) readily available, fails the task, as the information about the phase of the source node can- not be effectively shared among all nodes. In Fig. 26 we compare the distance predictions by the different models. While the prediction spatial MPGNNs are almost unable to distinguish higher distances. By contrast, DirGGG predicts reasonable distances regardless of the ground truth, with the absolute error only increasing slowly.
being an arbitrary constant (due phase invariance of the eigenvector). is
all models is close to perfect below a distance of 5,
M.8 Heterophilic aiXiv-year (Lim al. 2021)
Setup. We evaluate S*GNN on large-scale heterophilic dataset, namely arXiv-year. arXiv-year is based on OGB arXiv (Hu et al. 2020), but instead paper subject areas, the year of publication (divided into 5 classes) is the prediction target. While there are long-range interactions in this dataset, preliminary experiments indicated that the phase of the Magnetic Laplacian eigenvectors on its own can also be predictive of the class label. We report average + standard deviation over reruns with the splits from Lim et al. (2021), using a different random seed for each run.
Models. We use DirGCN RRssii et al. 2023) as baseline and largely follow the original setup. However, we observe that using layers (instead 6) and introducing dropout of p 0.5 im- proves baseline performance. Furthermore, (2023). We compare this baseline to S*DirGCN with two spectral layers (after the second and third spatial layers) and apply residual connections only for the spectral layers. For the spectral layers, we set g 0.0001 and use the partial cigendecomposition with & 100, a NN in the spectral domain $ 3.2.2 feature gating, and bottleneck of 0.05. All other parameters are kept similar to the DirGCN base of Rossi et al. 2023).. We train for 2000 epochs using the AdamW opti- mizer (Loshchilov & Hutter] 2019) with base learing rate of 0.005, weight decay, and cosine scheduler with 50 warmup epochs.
drop the jumping knowledge used by Rossi et al.
Notably, our D'CGG outperforms both our baseline DirGCN as well as the recent FaberNet (Koke Cremers) 2024), albeit by a very tight margin. However, found hyperparameter optimizations be quite noisy, and as such, the resulting per- formance metrics should be interpreted cautiously. more comprehensive evaluation of S²GNN's power on heterophilic datasets, potentially with long-range interactions, is left for future work.
Results. We report the results in Table 14
49

---

Table 14: Results yraiv-year. Best test accuracy is bold, second is underlined.
Model
Accuracy (?)
DirGCN
Rossi al.
2023
0.6408 + 0.0026
FaberNet Koke & Cremers 2024
0.6462 + 0.0101
DirGCN (tuned) 5 DirGCN (ours)
0.6450 = 0.0025
0.6472 + 0.0024
M.9 Large-Scale PCQM4M+2 (Hu et al. 2021
We show that S'GNNs are very parameter efficient. Even though we only conduct very rudimen- tary hyperparameter search, S*GNNs keep up with state of the art approaches. Specifically, we adapt the hyperparameters from peptides-fing and achieve comparable performance to the state of the art (excluding external data) with about 3-20% of the number of parameters.
Table 15: Results on PCQM4Mv2 (Hu et al. 2021 (validation).
Meihod
MAE
Parameters
Notes
EGT Hossain et al. 2023
0,0857
89.3 mio.
layers
GRIT Ma 2025
0.0859
16.6 mio.
layers
0.0652
13.8 mio.
layers
32 layers, pretraining
TGT-Ai Hussain al.
2024
0.0671
203.9
coordinates (RDKit)
S'GNN
0.0870
2.8 mio.
adupted from peptides func
5 layers, hyperparameters
M.10 TPUGraphs Graph Construction
The "XLA" collections of TPUGraphs contain many constructs that most certainly suboptimal for a machine-learning-ee
runtime prediction. However, in our preliminary experiments, we could not show that our graph construction yielded better results in statistically significant manner. Nevertheless, we include this discussion since might be insightful.
To understand the challenges with the default graph construction, note that in the TPUGraphs dataset each node represents an operation in the compuational graph of Accelerated Linear Algebra (XLA). Its incoming edges the respective operands, and the outgoing edges signal where the operation's result is used. Thus, the graph describes how the tensors are being transformed. An (perhaps unnecessary) challenge for machine learning models arises from using tuple, which represents a sequence of tensors of arbitrary shapes. In this case, the model needs to reason how the tuple is constructed, converted, and unpacked again. Moreover, directly adjacent tensors/operations can be very far away in the graphs of TPUGraphs.
We identified and manually "fixed" three cases to climinate this problem largely in the TPUGraphs dataset: Tuple-Get Gepple-Getuullllemmnnntt While, and Conditional. Since we could not access the config- urations in the HLO protobuf files and C++ XLA extraction code, we decided to perform these optimizations ourselves. However, might be a better strategy to utilize the existing XLA compiler etc.
Additionally, to the subsequently described graph structure changes, we extract the order of operands from the HL.O protobud files. Outgoing edges are assumed to be unordered except for the Get- Tupleflement operation, where the tuple index used order. Moreover, we extracted all features masked in the C++ code and then excluded constant features.
M.10.1 Tuple-GetTuppeEElement
The dataset contains aggregations via the XLA Tuple operation that are often directly followed by a GetTupleElement operation. To large extent, these constructs are required for the subsequently discussed While and Conditional operations. Importantly, the model could not extract the relation- ships through tuple aggregation since the tuple_imee dntdexiddxxx_eeee was not included the default features. Moreover, the resulting tuple hub nodes severely impact the Fourier basis of the graphs (see $ 2}. We illustrate the graph simplification Fig. 27 27 and denote the edge order of incoming edges from top to bottom. The edge order represents the order of operands.
50

---

We propose dropping immediate GepTpleetullellemennt constructs and directly connecting prede- cessors and successors. For this, we generate graph solely consisting of direct connections and then resolve multiple consecutive Tuppe-GGie/hupleeleeenn constructs via a graph traversal (depth- first search).
Tuple GetTupleElement
Predecessors
Succcessor
3
4
Add
Drop
Figure 27: Tuple-GeeTupllellmmen simplification: the Tuple aggregates the output of multiple pre- decessors/operations and then the GerTluleeElemen extracts the tensor according its index (num- ber in respective nodes). We propose dropping immediate Yuple-GerTTuleeEIl constructs and connecting predecessors and successors.
We perform the Tuple-GGetTupleeleeeee simplification after dealing with While and Conditionals. However, for the sake of simplicity, will avoid using tuples in the subsequent explanations for While and Conditional. In other words, the subsequent explanations extend to functions with multi- ple arguments via the use of tuples.
M.10.2
While Operation
The While operation has the signature While (condition, body, init) where condi tion is function given the init or output of the body function. Note that in the TPUGraph construction, body as well as condition only represent the outputs of the respective function and their operands need to be extracted from HLO.
To avoid hub nodes and retain the dataflow between operations (important for decisions about the layout), operands and outputs are connected directly. Technically, we am modeling a do-while construct because the condition is not connected the inputs. Since the successors of the while are of type GelTupleElement, they relabeled to a new node type, signaling the end of a while loop. To support nested while loops, each node the body is assigned new node feature signaling the number of while body statements it is part of.
Successorr
Body
While
Condition
Keep
Add
Predecessozs
Drop
Figure 28: Instead of aggregating everything into a hub node, we propose to connect respective inputs and outputs.
51

---

M.10.3 Conditional Operation
Conditional (branch_ seranch_index, Sranch_cooputationn mon signature of the Conditional operation, where the integer-valued branch_ index selects which branch_ caaachhcomutaaiinns is executed with the respective input in branch_ aorichoppeaadd... Similarly to the While operation, we introduce new node types for the inputs computations and the successors (they are GelTupleeßlement operations).
branch_operandee is the most com-
Compatation
Conditional
Competation
Operand
Keep
Operand
Drop
Beanchh Indexx
Figure 29: Instead of aggregating everything into a hub node, we propose to connect respective inputs and outputs. Here as an example with two conditional computations.
52

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We discuss the shortcomings of prior MPGNNs and that new framework S'GNN takes a new approach to overcome the limitations. We detail our theoretical analy- sis/justification, outline the yet largely unexplored design space of GNN, and summarize the experimental evaluation.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We provide upproximation-thhoreee error bound S 3.1.2 that also gives light on the limitations. Moreover, we discuss important considerations of SCGNNs throughout the method section S Additionally, we elaborately list and summarize the limitations in K
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex, system might be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairnsss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
53

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
3.2.4 and state im- portant assumptions the main text. All theorems, dehnitions, formulas, and proof' are numerated. Due to the page limit, we do not provide proof sketches in the main body. Nev- ertheless, we provide accompanying sketches and illustrations to convey the main intuition. The proofs, full assumptions, and details are given in H
Justification:
The theoretical analysis of S
3.1.2
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross- referenced.
All assumptions should clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We describe our S-GNNs in length in $ and detail the experimental setup
in S 4 Additional relevant details are provided in $ M. We provide code, including configuration, at htthtts://wwwe
cit tum. de/daml dam /tsmmammmms//////a// s2gnn
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- reasonable avenue for reproducibility, which may depend
missions to provide on the nature the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
54

---

(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We will open source fully automized scripts for all datasets that download and preprocess the data prior to the execution of the configured experiment (except TPU- Graphs (Phothilimthana al., 2023) due its dedicated access). This includes our own datasets on clustering, distance prediction, and associative recall. We provide code at https: //www. cs. cit. tum. tte/daml/s22) Moreover, we provide reasonable details for reproduction in S M
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (nttps://nips.co cc/
wublic/guides////
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: wwciiicggiiisseeeeeee SooeeSubiieeSSeeecccc ssi sesssssiooooooo onPolicy) for more details.
//nips.coo//
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: We provide the setup and details reasonable detail in and S M. For additional details, we refer to the provided code, including configuration, at https://wwwd cs. cit. tum. wwt.de/da....mmeee de/daml/s2gnm
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
55

---

7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report mean, standard deviation, and details on randomization for all rele- vant results on benchmark datasets. For qualitative insights and the large-scale TPUGraphs dataset, we solely provide mean estimates. The collective experimental results underline the claims and are strong evidence against the statistical insignificance of our results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of еrrors is not verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer:
[Yes]
Justification: We provide reasonable summary of used resources in $ M. and specifically Table 7 Here, we list the hardware accelerator used and the runtime of the experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://///.arep..cpppp/a/tttaaaa
Answer: [Yes]
Justification: [Yes]
56

---

The proposed framework S'GNN does not pose an unusual risk on top of the common risks for research on machine learning architectures. Our evaluation does not include human subjects, participants, or data. We discuss the broader impact in L. Thus, in summary, we conform to the ethics guidelines in every aspect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: We discuss the broader impact in $ 1. It should be noted that the proposed framework SNN does not pose an unusual risk on top of the common risks for research on machine learning architectures. We discuss the broader impact in L
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The proposed framework S^GNN does not pose an unusual risk on top of the common risks for research on machine learning architectures. Our evaluation does not include human subjects, participants, or data.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
57

---

Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cite all origins of the datasets, even we derive the benchmark from someone else. We provide an overview of the datasets, including the licenses in Table 6 We provide code, including configuration, at hhtps: //ww cs. cit. tum. de de/damm/s2gmt It also contains an (anonymized) license for its usage and discloses the provenance of the project setup.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URI..
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that souree should be provided.
assets are released, age should be provided. For popular datasets, wwwppaaitphaaaaecccpppppp.pppp thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
license, copyright information, and terms of use pack-
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [Yes]
The code and configuration for the dataset on GMM clustering, distance re- gression, and associative recall will be provided. The generation of all resources takes around one hour and uses solely CPUs. We provide code, including configuration, at https://we htts://wwwt //www/ceco cs. cit. tum. de/ ht///mmmm/////// and M.7
Justification:
The datasets described in M M.6
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodll part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsoureing experiments and research with human subjects, does the pa- per include the full text instructions given participants and sereenshots, applicable, well as details about compensation (if any)?
58

---

Answer: [NA]
Justification:
Our work neither involves crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our work neither involves crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper neither involves crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
59


Reviews:
[{"review_id": "YXMCXIPic7", "reviewer": "Reviewer_ohZY", "summary": "The proposed method Spatio-Spectral Graph Neural Networks (S2GNNs) combine the spectral GCN and spatial GCNs embeddings linearly. The paper considers a deep dive into spectral filter properties and attempt to motivate the combination with spatial filtering. There are well known results repeated in the method section, which could have been part of background. Also, the contribution towards directed graphs is not clear.", "questions": "GNNs aim to learn data driven filters. “Ideal” filters may NOT be a “good” choice always. Then what is the need of implementing an ideal discontinuous spectral filter discussed in Section 3.2?\n\nIn the experiments, did you take the directionality into account in S2GNN? If, yes what is the performance of S2GNN without directionality?", "limitations": "n/a", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1.\tThe paper considers a deep dive into spectral filter properties and attempt to motivate the combination of spectral filters with spatial filtering. \n2.\tThe linear combination of spectral and spatial embeddings is new.", "weaknesses": "1.\tThere are well known results repeated in the method section. For example, it is established that the spectral filters are permutation equivariant, Locality relates to spectral smoothness.\n2.\tThe paper sometimes fails to connect the dots. For example, MPNNs (spatial) suffer from oversquashing, but at the same time spectral GNNs can handle oversquashing issue. So why do we need to combine them both? Its not clear in Introduction.\n3.\tContribution towards the directed graphs is unclear, any spectral filters can be adapted to directed graphs via magnetic Laplacian. The main point of the paper is to demonstrate the superiority against existing methods for undirected settings first.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their critical thoughts about our work! We are convinced that we conclusively resolved all points brought up by the reviewer. We would highly appreciate a major reevaluation of our submission.\n\nBefore going into detail, we want to highlight that our empirical results yield conclusive evidence for the validity of the advocated GNN construction. For example, S$^2$GNNs outperform all prior message passing schemes, transformers, and graph rewirings on the long-range benchmark task peptides-func by a comfortable margin using substantially fewer parameters.\n\n---\n\n## W1: Well known results repeated\n\nChief among our contributions is the exploration of novel GNN design spaces, given that a part of the model is *parametrized explicitly on the spectrum*. **There indeed are reasonable parametrizations of such filters that would break permutation equivariance** – e.g., truncating after a fixed number of eigenvectors, specifically if the last considered eigenspace is degenerate. As we show, each eigenspace must be either left out or included entirely to preserve equivariance. As our treatment substantially extends the traditional parametrization of spectral filters as Laplacian polynomials, proving that equivariance still holds is essential to the formal completeness of our work. Additionally, we capture a **more general case than usual**, considering complex-valued eigenvectors. We detail this in §F.1 and will highlight these differences in the method section as well.\n\nWe decided to include the fact that \"locality relates to spectral smoothness\" in the main part *for readability reasons* and because it is a vital insight for our method.\n\nIn case we missed important references etc., we would be glad to include them upon the reviewer's request.\n\n---\n\n## W2: Connecting the dots\n\nSince the reviewer focuses in their critique on the introduction, we want to briefly point out that the technical arguments can be found in the method section (§3, §3.1, and §3.2). From this technical viewpoint, combining both filters is a fundamental prerequisite for the approximation-theoretic guarantees derived in §3.2.\n\nIn the introduction, starting with Figure 1, we illustrate the complimentary limitations of each parametrization on its own. We state in lines 38-39 that a spectrally parametrized convolution should operate on a truncated frequency spectrum for efficiency reasons. This implies a limitation of a purely spectral parametrization. Finally, in lines 61-62, we state explicitly that the combination of both approaches alleviates over-squashing, providing a forward pointer to the technical argument.\n\nIn the camera-ready version, we plan to change\n> Conversely, spectral filters act globally ($p_\\max$), even with truncation of the frequency spectrum ($\\lambda_\\text{cut}$) **that is required for efficiency.** \n\nto \n> Conversely, spectral filters act globally ($p_\\max$), even with truncation of the frequency spectrum ($\\lambda_\\text{cut}$). The truncation of the frequency spectrum is required for efficiency. Yet, the combination of spatial and spectral filters provably leverages the strengths of each parametrization.\n\nWe appreciate further suggestions and more details on potentially missing connections.\n\n---\n\n## Q1: GNNs aim to learn data driven filters. Ideal filters may NOT be a “good” choice.\n\n**We empirically demonstrate that our parametrization can substantially improve over the prior state of the art**, providing strong evidence that the capability of approximating ideal filters is useful! Perhaps we misunderstand a part of the reviewer's concern. However, **it is common practice in deep learning to strive for a maximally general hypothesis class s.t. training can decide for a good parametrization in a data-driven manner**. Popular examples include Graph Isomorphism Networks (GIN) [1] or even the well-known works on universal approximation. These works also show how to overcome certain limitations or how to obtain full generality. While we make a connection to **universal approximation of idealized GNNs** [2] explicit in lines 195-197, in the camera-ready version, we will elaborate more on the motivation in Section 3.2. We should also mention that the discontinuity is solely a worst-case example (lines 204-206) and that our approximation-theoretic discussion implies that S$^2$GNNs are strictly more powerful than Message-Passing GNNs (MPGNNs).\n\nIf this answer does not fully address the reviewer's questions, we kindly ask for clarification.\n\n[1] Xu et al. How Powerful are Graph Neural Networks? ICLR 2019.\n\n[2] Wang and Zhang. How Powerful are Spectral Graph Neural Networks. ICML 2022.\n\n---\n\n## Q2 & W3: Directionality\n\nThe ability to support directed graphs shows the general applicability of S$^2$GNNs. For graph machine learning to generalize, e.g., sequence models, directedness is required. This is why we show that S$^2$GNNs are also exceptional sequence models in the associative recall task.\n\nWe are the first to use the Magnetic Laplacian for a spectrally parametrized filter. We provide the important and unique (e.g., for potential $q$) design decisions in lines 298-303 and §H.5. It should be noted that only very few MPGNNs, including MagNet (Zhang et al., 2021), also use the Magnetic Laplacian, out of the thousands of papers that work with graph neural networks.\n\nWe present results on directed graphs in Figure 12 (distance regression) and Figure 15 (associative recall), Table 2 (associative recall), Table 4 (TPU Graphs), Table 11 (distance regression), Figure 24 (distance regression), Table 12 (arXiv-year). We ablate the importance of directed graphs, e.g., in Figure 15 and Table 11. In both cases, directionality improves performance.\n\nWe will use the extra space in the camera-ready version to make these points more explicit and appreciate further suggestions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cQJi23NiYl", "reviewer": "Reviewer_EZD5", "summary": "The paper presents Spatio-Spectral Graph Neural Networks (S$^2$GNNs), a novel paradigm that combines spatial and spectral parameters to overcome the limitations of $\\ell$-step MPGNNs, notably their restricted receptive fields and over-squashing issues. S$^2$GNNs achieve global information propagation efficiently, surpassing MPGNNs in approximation accuracy, expressivity, and scalability, demonstrated through superior performance on various graph tasks and ability to handle large-scale datasets.", "questions": "See above", "limitations": "NA", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper presents a rigorous theoretical basis and comprehensive analysis, reinforcing the validity of the proposed approach.\n\n2. The proposed method is straightforward and practical, with the added advantage of being easily integrable into a wide range of existing GNN models.\n\n3. The method has been extensively tested across various backbones and datasets of differing types and sizes, demonstrating its robustness and versatility.", "weaknesses": "1. **Deficiency in Ablation Studies for Embedding Updates**: Eq.~(1) within the paper that updates to the latent embeddings are achieved through the summation of spectral and spatial layers. This method warrants a broader range of ablation studies, such as exploring concatenation, normalization, or adopting a randomized approach to select between spectral or spatial optimizations like [1], to validate the robustness and efficiency of these embeddings.\n\n2. **Inadequate Comparative Analysis for Over-Squashing and Long-Range Interactions**: The paper's treatment of over-squashing and long-range interactions could be enhanced by incorporating comparative analyses with established methods. Notably, the GCNII[2], which utilizes skip connections and PageRank to facilitate up to 64 layers in a GNN, and methods based on random walks that intensify depth-first search capabilities for extended influence, should be examined. This inclusion would enhance the analysis and provide a more rigorous evaluation of the proposed model’s capabilities in handling long-range interactions.\n\n[1] Chang, Heng, et al. \"Not all low-pass filters are robust in graph convolutional networks.\" Advances in Neural Information Processing Systems 34 (2021): 25058-25071.\n[2] Chen, Ming, et al. \"Simple and deep graph convolutional networks.\" International conference on machine learning. PMLR, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and for acknowledging the theoretical justification along with the ubiquitous possibilities of lifting GNNs to S$^2$GNNs.\n\n---\n\n## W1: Ablation on the combination of spatial and spectral filter\n\nWe agree with the reviewer that different combinations may yield beneficiary properties. In the camera-ready version, we will highlight that we focus on the simplest options, showing that the combination is very effective (Eq.  1 & 2). From an approximation-theoretic standpoint, choosing addition moreover recovers the analysis in §3.2 most naturally. Nevertheless, we value the suggestion and present the following comparison of concatenation, addition (Eq. 1), a Mamba-like composition, and arbitrary sequence of filters (Eq. 2), on peptides-func. \n\n| Aggregation | Normalization | # params | Test AP (↑)       |\n|-------------|---------------|----------|-------------------|\n| Concat      | ✗             | 322k     | 0.6827 ± 0.0055   |\n| Concat      | ✓             | 322k     | 0.6783 ± 0.0023   |\n| Sum (Eq. 1)         | ✗             | 323k     | *0.7235 ± 0.0059* |\n| Sum         | ✓             | 323k     | 0.7171 ± 0.0070   |\n| Mamba-like  | -             | 474k     | 0.7073 ± 0.0081   |\n| Sequential (Eq. 2)  | -             | 323k     | **0.7311 ± 0.0066** |\n\nFor the normalization, we add the factor $\\sqrt{1/2}$ if aggregating two values and $\\sqrt{1/3}$ for three values. We use the same hyperparameters as before and solely alter the aggregations. In a different set of experiments, we also tried BatchNorm and GraphNorm, which did not yield significant improvements.\n\nWe agree that there are many important aspects, including robustness like in [1]. However, it is not clear how to transfer their approach to our setting since we do not have the option to tie the weights of the spectral and spatial filters. We may try this option if the reviewer can provide more details on the specifics.\n\n---\n\n## W2: Comparative Analysis\n\nWe do not state that S$^2$GNNs provide the *only* solution to over-squashing, but we would like to note that we did compare our method to a wide range of popular methods that overcome over-squashing, such as various graph transformer models and rewiring approaches. Our theoretical analysis can be extended to the mentioned GCNII [2] with similar conclusions.\nHowever, we want to highlight that although GCNII vanquishes over-smoothing, the information propagation through the graph is similarly constrained by the graph structure as in many other standard MPGNN architectures like GCN. This implies that GCNII does not effectively alleviate all potential over-squashing issues (i.e., information still needs to pass bottlenecks in the graph). We conducted additional experiments with GCNII on the peptides-func benchmark, using similar hyperparameters as GCN-tuned (Tönshoff et al., 2023) and varying the number of layers from 6 up to 64. While results in the standard 6-layer setting approach performance of GCN-tuned (AP of 0.6860±0.0050 with GCN, 0.6656±0.0004 with GCNII), performance starts to deteriorate after ~16 layers, which we conjecture to be caused by over-squashing.\n\nWe will include GCNII in the camera-ready version and appreciate further pointers if the point is not fully addressed.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rxCS6geZZH", "reviewer": "Reviewer_H69b", "summary": "This paper proposes Spatio-Spectral Graph Neural Networks (S²GNNs) to address the limitations of ℓ-step Spatial Message Passing Graph Neural Networks (MPGNNs), such as limited receptive fields and over-squashing. S²GNNs combine spatial and spectral graph filters for efficient global information propagation, offering tighter error bounds and greater expressiveness than MPGNNs. They outperform traditional MPGNNs, graph transformers, and graph rewirings on benchmarks and scale efficiently to millions of nodes.", "questions": "1. Please refer to the weaknesses mentioned above.\n2. What is the upper bound of the graph size that the EVD used in S²GNN can support? For example, can it handle graphs with billions of nodes, such as papers100m?\n3. In real tasks, are the eigenvectors $k$ sensitive to performance? For instance, on products and TPU graphs, would using a larger $k$ improve performance?", "limitations": "The authors discussed limitations in the Appendix.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Combining spectral and spatial methods is interesting. The proposed method can overcome many problems associated with MPNNs.\n2. The theoretical proofs in this paper are sufficient and, in my opinion, sound.\n3. This paper offers a lot of intuitive analysis, with examples that help readers understand the concepts.\n4. S²GNN performs excellently in multiple tasks and can be extended to various applications. It also demonstrates scalability, running efficiently on graphs with millions of nodes.", "weaknesses": "1. This paper's writing and structure can be further improved. Adding descriptions to the notation and including pseudocode would enhance readability.\n2. The experiment includes too few baselines. For instance, only GAT and GCN are used as baselines in Tables 3 and 4, while some of the latest methods, such as SpecFormer, which also uses Eigenvector, are not considered.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and for acknowledging the theoretical justification along with the ubiquitous possibilities of lifting GNNs to S$^2$GNNs. Furthermore, we thank the reviewer for highlighting that the paper contains a lot of intuitive analysis with examples.\n\n---\n\n## W1: Pseudocode and notation table\n\nWe provide pseudo-code and a table covering the notations in the global response. If this does not fully address the reviewer's comment, we ask for clarification.\n\n---\n\n## W2: Baselines\n\nWe include *task-specific state-of-the-art baselines* for each task/experiment (see Table 1 for peptides tasks, Table 2 for associative recall, in Table 10 for CLUSTER, and Table 12 for arXiv-year). In total, we compare to the following *21 baselines* (see paper for full references): (1) GAT  (Velickovic et al., 2018), (2) GCN (Kipf & Welling 2017; Tönshoff et al., 2023), (3) GatedGCN (Bresson & Laurent, 2018), (4) DirGCN (Rossi et al., 2023),  (5) FaberNet (Koke & Cremers, 2024), (6) TIGT (Choi et al., 2024), (7) MGT+WPE (Ngo et al., 2023), (8) GraphMLPMixer (He et al., 2023), Graph ViT (He et al., 2023), (9) GRIT (Ma et al., 2023), (10) DRew-GCN (Gutteridge et al., 2023), (11) PathNN (Michel et al., 2023), (12) CIN++ (Giusti et al., 2023), (13) ARGNP (Cai et al., 2022), (14) GPS (Rampášek et al., 2022), (15) GPTrans-Nano (Chen et al., 2023), (16) Exphormer (Shirzad et al., 2023), (17) EGT (Hussain et al., 2022), (18) Transformer (Vaswani et al., 2017), (19) Transformer w/ FlashAttention (Dao et al., 2022), (20) H3 (Fu et al., 2023), (21) Hyena (Poli et al., 2023).\n\nFollowing the suggestion, in the revised version of the manuscript, we will also include a comparison to further baselines on OGB Products (Table 3). It should be noted that the largest dataset considered by the suggested SpecFormer is arXiv (170k nodes). Scaling by >10x (Products, 2.5M nodes) would be prohibitively expensive due to SpecFormer's large required fraction of eigenvalues. Furthermore, SpecFormer does not discuss directed graphs and, thus, is not directly applicable to TPUGraphs (Table 4).\n\n---\n\n## Q2: Scaling the eigendecomposition\n\nThere is no clear scalability limit for the eigendecomposition as calculating $k$ eigenvectors scales linearly in the number of edges $m$. However, it should be noted that the EVD of such large graphs will come at considerable computational cost and one should consider approximate methods. For example, there are open-source implementations for an approximate partial SVD (equivalent to EVD for PSD matrices) that support a hundred million rows and columns: [https://github.com/criteo/Spark-RSVD](https://github.com/criteo/Spark-RSVD). \n\n---\n\n## Q3: Performance vs. number of eigenvectors on real tasks\n\nWe plot the influence of the number of eigenvectors in the global response (Figure 2) on the real-world dataset peptides-func. Since we here limit the number of eigenvalues by cut-off frequency $\\lambda_{\\text{cut}}$ (Figure 2a), we report the average number of eigenvectors in Figure 2b.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rzBiYwGLZr", "reviewer": "Reviewer_rAa9", "summary": "The authors are proposing Spatio-Spectral Graph Neural Networks ($S^2GNNs$), a hybrid model that combines (Spatial) Message Passing Neural Networks (MPNNs) and Spectral Graph Neural Networks. The authors argue that, by combining message-passing with spectral filters, the model can better model both local and global information, alleviating phenomena such as over-squashing and under-reaching. The authors discuss the design space of their proposed method and showcase a technique for obtaining position encodings that can make their model more expressive than the 1-WL test. The authors perform multiple experiments on both synthetic and real-world datasets.", "questions": "- In the graph rewiring literature, the models are often benchmarked on other graph-level datasets (such as QM9, Zinc, or the TUDataset collection). Did the authors try their method on these datasets? I am not requesting these experiments, but they would be a nice addition.\n- The Long-Range Graph Benchmark also contains COCO-SP, PascalVOC-SP, and PCQM-Contact. Did the authors try to benchmark their models on these datasets? I'm personally not a fan of COCO-SP and PascalVOC-SP because they're obtained from Computer Vision datasets, so the GNN inductive bias might not be appropriate for them. Still, PCQM-Contact is a molecular dataset, and it would be interesting to see some results on it.", "limitations": "- The limitations are addressed in the appendix.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- The paper is well-written, and the figures and tables are aesthetically pleasing.\n- The tackled problem is well-motivated.\n- The method is relatively easy to comprehend. The idea is simple and elegant, yet it has very strong empirical results.\n- The proposed $S^2 GNN$ is analyzed very well. Including mechanistic in-context learning experiments is very interesting in the context of long-range modeling on graphs. Moreover, the connections between $S^2 GNNs$ and SSMs that the authors make are insightful and could be very interesting to some readers.\n- The empirical results on the Peptides datasets are very good. $S^2 GNNs$ obtain state-of-the-art results on peptides-func *without* using Position Encodings, which is very hard to accomplish even with models that consider the graph as being complete (such as Graph Transformers). Moreover, the proposed method uses significantly fewer parameters than other competing models.\n- The theoretical analysis is well thought out. The authors also make some remarks about the advantages of having spectral filters, and they provide some very useful intuitions that connect them to using virtual nodes (Fig 3, Fig 4).\n- The authors introduce two new datasets - a long-range clustering dataset (\\textsc{LR-CLUSTER}) and a long-range regression dataset that is then used to make several observations about their model - such as the ability to solve long-range tasks and the alignment between the clusters and the learned spectral filters.\n- The authors also propose a way of obtaining some Laplacian Position Encodings that improve the overall performance and make their model more expressive than the 1-WL test.\n- The paper contains an extensive amount of supplementary materials detailing other experiments and proofs for the theoretical results.", "weaknesses": "- The paper's main weaknesses are that the main text is somewhat unfocused, and some related work is not mentioned. I will detail in the following:\n\t- While the authors generally do a very good job of providing valuable theoretical insights regarding their design choices, I would argue that some of them are unnecessary and distract the reader from the main points of the paper. For instance, I believe the discussion about \"high-resolution filters for low frequencies\" from lines 149-167 to be somewhat hand-wavy and distracting, especially the remark that \"as graph problems discretize continuous phenomena, stability to the graph perturbations is a strong domain-agnostic prior\". While I don't think that the discussion is bad, I feel that the supplementary materials would be a much better place in which to include it. \n\t- I believe that Subsection 3.3 (Parametrizing Spectral Filters) is somewhat confusing, especially for a reader who is not very familiar with spectral methods. I did not initially understand the discussion about the window (Lines 247-253), and I believe it should contain more context. The authors should either expand the section or move it to the supplementary materials.\n\t- The proposed positional encodings are a nice addition, but similar laplacian positional encodings, such as [[1]], have not been discussed as related work. Other works, such as [[2]], are cited in the paper but not in the context of the laplacian positional encodings that they propose.\n\t- Some other recent methods deal with long-range relationships on graphs and have not been discussed in the related work. Notably, GRED [[3]] uses Linear Recurrent Units to model distant relationships with a mechanism similar to k-hop MPNNs and also draws inspiration from SSMs; AMP [[4]] has a message filtering mechanism and is adaptively increasing the number of layers depending on the dataset; NBA [[5]] is passing messages in a non-backtracking manner, obtaining a slightly better score than $S^2 GCN$ on *peptides-struct* ($0.2424$ v.s. $0.2447$), and PR-MPNN [[6]] rewires graphs adaptively by learning a probability distribution for the adjacency matrices.\n- The authors mention on line 69 that the runtime of their method is equivalent to that of an MPNN, but I could not find a table containing a direct comparison. It would be great if this were included somewhere. There are training times on page 35, Table 6, but no comparison with a simple MPNN (such as a GCN or a GIN model).\n\n\nOverall, I believe that the paper is very strong. The model is conceptually simple but contains novel ideas. The empirical results are very good, and the authors test their method on many different scenarios. I found the mechanistic in-context learning experiments to be particularly interesting. I believe the work could have a considerable impact on how we design GNN architectures going forward.\n\nAs stated previously, the main weakness is that the paper feels somewhat unfocused, and some important related work is omitted. This is a somewhat strange complaint to have, but I feel that the scope of the paper is very broad. In my opinion, the overall style of the paper would be better suited for a journal submission if some details from the appendix were moved into the main text. For a conference with more limited space, I would advise the authors to move some of the more in-depth details to the appendix. This is in no way an argument for rejection, I just believe that the paper would be a lot nicer to read if it didn't contain these details in the main text.\n\nI recommend a 7 (Accept), but I will update my score to an 8 (Strong Accept) if the authors expand their related work discussion and provide more details for Subsection 3.3. I would also recommend to the authors that they move some of the details from Section 3 to the Appendix, but not doing so will not affect my final score. \n\n\n\n[1]: https://arxiv.org/abs/2110.07875\n[2]: https://arxiv.org/pdf/2012.09699\n[3]: https://arxiv.org/pdf/2312.01538\n[4]: https://arxiv.org/pdf/2312.16560\n[5]: https://arxiv.org/pdf/2310.07430\n[6]: https://arxiv.org/abs/2310.02156", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable points and positive feedback. We will use the extra space in the camera-ready version to address the reviewer's points.\n\n---\n\n## High-resolution filters for low frequencies\n\nWe truncate the spectral filter for efficiency reasons mainly, whereas the special choice of a low-pass window is required by neither our theoretical analysis nor by any specifics of its implementation (we state this in ll. 192-193, now moved out of §3.2 directly into §3 for clarity). While we intended ll. 149-167 to provide supplementary intuition as for why low-pass windows might be a sensible default, we do agree that this might distract the reader from initially understanding the essentials of our method. We intend to keep points (1) and (2) as main arguments (except for the point on \"as graph problems discretize continuous phenomena [...]\") and move the remainder (ll. 158-167) to the appendix.\n\n---\n\n## Parametrizing spectral filters\n\nTo improve readability, we have rewritten the second sentence (ll. 240-241), explaining our use of the term \"Gaussian smearing\": \n> As depicted in Fig. 7, we learn a channel-wise linear combination of translated Gaussian basis functions (similar to the \"Gaussian smearing\" used by Schütt et al., 2017).\n\nMoreover, we have overhauled the window discussion (ll. 247-253) to explain, first, how the Gibbs phenomenon adversely affects learning, and, second, how we alleviate it by overlaying the filters with a window function: \n> We multiply the learned combinations of Gaussians by an envelope function (we choose a Tukey window) that decays smoothly to zero outside the cutoff $\\lambda_{\\text{cut}}$. This counteracts the so-called \"Gibbs phenomenon\" (also known as \"ringing\"): as visualized for a path graph/sequence of 100 nodes in Fig. 8, trying to approximate a spatially-discontinuous target signal using a low-pass range of frequency components results in an overshooting oscillatory behavior near the spatial discontinuity. Dampening the frequencies near $\\lambda_{\\text{cut}}$ by a smooth envelope function alleviates this behavior. We note that the learned filter may, in principle, overrule the windowing at the cost of an increased weight decay penalty.\n\n---\n\n## Additional structure to enhance presentation\n\nTo streamline the presentation and reading flow, we will use the extra space to introduce additional structure. Specifically, we have revised the paper to make sure that the overall \"story arc\" implied by Fig. 2 (core theory in §3.1-3.2, design space considerations in §3.3-3.6) is more closely aligned with the section structure: §3 of the revised manuscript will instead feature two subsections, §3.1 (Theoretical Analysis) and §3.2 (Design Space) that form the umbrella for the previous §3.1-3.2 and §3.3-3.7. This extra structure will allow for better guidance through the considerations around S$^2$GNNs. Naturally, we greatly welcome any additional suggestions on how to improve the presentation.\n\n---\n\n## Positional encodings\n\nWe thank the reviewer for the helpful suggestions and we have extended the related work section accordingly. We would like to note that LapPE [2] (and accordingly LSPE [1]) breaks permutation equivariance (sign invariance is approximately enforced through augmentations; repeated eigenvalues are ignored). We will use the extra page to explicitly discuss this aspect in the revised manuscript instead of only referring to background literature. Experimentally, we have so far (implicitly) addressed LapPE, e.g., through our evaluations of GPS.\n\n---\n\n## Further related work\n\nWe thank the reviewer for pointing out additional related work, and we have included them in our manuscript accordingly. Thus, we will implement the requested changes in the camera-ready version.\n\n---\n\n## Runtime comparison of message passing and spectral filters\n\nGreat suggestion! Of course, the runtime comparison depends severely on the used hardware since it essentially compares a sparse matrix multiplication (adjacency matrix) with matrix multiplications on dense \"tall and skinny\" matrices (GFT). With OGB-arXiv (170k nodes) as the graph for comparison, we find that one GCN-layer here is as costly as a spectral filter with approx. 2,500 eigenvectors. We provide the detailed plot in the global PDF.\n\n---\n\n## Additional dataset: PCQM\n\nSince the primary download of PCQM-contact is currently not available, we report results on PCQM4Mv2 instead (also 3.4 million graphs etc.). Due to the time and resource constraints during the rebuttal phase, we were not able to tune the hyperparameters. Instead, here we manually merged the configuration from S$^2$GNN with the configuration from the Long Range Graph Benchmark. This yields a much smaller yet very effective model for PCQM4Mv2. For the camera-ready version, we intend to scale the model up and also follow the pretraining procedure of TGT-At (without using RDKit coordinates at test time).\n\n| Method | Validation MAE (↓) | # Parameters | Comment |\n|---|---|---|---|\n| EGT (Hussain et al., 2022) | 0.0857 | 89.3 mio. | 16 layers |\n| GRIT (Ma et al., 2023) | 0.0859 | 16.6 mio. | 16 layers |\n| GPS (Rampášek et al., 2022) | 0.0852 | 13.8 mio. | 16 layers |\n| TGT-At (Hussain et al., 2024) | 0.0671 | 203.9 mio. | 32 layers, uses RDKit coordinates, Pretraining on 3D coordinates |\n| S$^2$GNN (*ours*) | 0.0870 | **2.8 mio.** | 5 layers, no hyperparameter tuning |", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their time and valuable feedback! Notably, we thank reviewers EZD5, H69b, and rAa9 for uniformly acknowledging our theoretical foundations/analysis of our Spatio-Spectral Graph Neural Networks (S$^2$GNNs), along with our method's general applicability and strong empirical results. We also want to highlight the assessment of reviewer rAa9:
> [...] the work could have a considerable impact on how we design GNN architectures going forward.

At the request of the reviewers, we have conducted several additional experiments and now provide pseudocode as well as a table summarizing the notation. We divert results to the reviewer-specific rebuttal where beneficial for presentation. In the attached pdf of the global response:
1. We compare the runtimes of a GCN with a spectral filter (w/o EVD) on OGB-arXiv (170k nodes), showing that one GCN-layer here is as costly as a spectral filter with 2,500 eigenvectors. This is due to the better parallelizability of dense matrix multiplications over sparse matrix multiplications. Requested by reviewer rAa9.
1. We study the influence of the number of eigenvectors on the real-world task peptides-func. Requested by reviewer H69b.
1. We provide pseudocode for S$^2$GNNs and a real-valued spectral filter. Requested by reviewer H69b.
1. We provide a table summarizing our notation. Requested by reviewer H69b.

Additionally, addressing reviewer EZD5, we now include further ablations on combining spatial with spectral filters, and we study the GCNII architecture. Following the suggestion of reviewer rAa9, we also report preliminary yet competitive results on the large-scale dataset PCQM4Mv2.

Meta-review: This paper studies an essential and timely topic. It proposes a novel hybrid method of spatio-spectral Graph Neural Networks to combine spatial and spectral graph filters and ensure better efficiency and bounds. After a fruitful discussion between the authors and the reviewers, this paper has an overall positive feeling.

The authors should carefully read and address all remaining concerns in the final version of the paper.
Decision: Accept (poster)