Equivariant Machine Learning on Graphs with Nonlinear Spectral Filters
Authors: Ya-Wei Eileen Lin
Ronen Talmon
Ron Levie
Venue: NeurIPS 2024 poster (2024)
Keywords: graph machine learning
graph signal processing
equivariant machine learning
geometric deep learning
spectral method
nonlinear method
Primary area: graph_neural_networks
TL;DR: We present a novel equivariant graph neural network based on nonlinear operations in the spectral domain.

Abstract: Equivariant machine learning is an approach for designing deep learning models that respect the symmetries of the problem, with the aim of reducing model complexity and improving generalization. 
In this paper, we focus on an extension of shift equivariance, which is the basis of convolution networks on images, to general graphs. Unlike images, graphs do not have a natural notion of domain translation. 
Therefore, we consider the graph functional shifts as the symmetry group: the unitary operators that commute with the graph shift operator. 
Notably, such symmetries operate in the signal space rather than directly in the spatial space.
We remark that each linear filter layer of a standard spectral graph neural network (GNN) commutes with graph functional shifts, but the activation function breaks this symmetry. Instead, we propose nonlinear spectral filters (NLSFs) that are fully equivariant to graph functional shifts and show that they have universal approximation properties. 
The proposed NLSFs are based on a new form of spectral domain that is transferable between graphs. 
We demonstrate the superior performance of NLSFs over existing spectral GNNs in node and graph classification benchmarks.

extension Equivariant Machine Learning on Graphs with Nonlinear Spectral Filters
Ya- Wei Eileen Lin
Ronen Talmon
Ron Levie
Viterbi Faculty of Electrical and Computer Engineering, Technion Faculty of Mathematics, Technion
Abstract
Equivariant machine learning is an approach for designing deep learning mod- els that respect the symmetries of the problem, with the aim of reducing model complexity and improving generalization. In this paper, focus shift equivariance, which is the basis of convolution networks on images, to general graphs. Unlike images, graphs do not have a natural notion of domain translation. Therefore, we consider the graph functional shifts as the symmetry group: the unitary operators that commute with the graph shift operator. Notably, such symmetries operate in the signal space rather than directly in the spatial space. We remark that each linear filter layer of standard spectral graph neural network (GNN) commutes with graph functional shifts, but the activation function breaks this symmetry. Instead, we propose nonlinear spectral filters (NLSFs) that are fully equivariant to graph functional shifts and show that they have universal approxima- tion properties. The proposed NLSFs are based on new form of spectral domain that is transferable between graphs. We demonstrate the superior performance of NLSFs over existing spectral GNNs in node and graph classification benchmarks.
Introduction
In many fields, such as chemistry [37], biology [36, 3], social science [9], and computer graphics [97], data can be described by graphs. In recent years, there has been a tremendous interest in the development of machine learning models for graph-structured data [98, 13]. This young field, often called graph machine learning (gruph-MI.) or graph representation learning, has made significant contributions the applied sciences, e-g-, in protein folding, molecular design, and drug discovery [45, 2, 70, 89], and has impacted the industry with applications in social media, recommendation systems, traffic prediction, computer graphics, and natural language processing, among others.
Geometric Deep Learning (GDL) [13] is design philosophy for machine learning models where the model is constructed inherently respect symmetries present in the data, aiming to reduce model complexity and enhance generalization. By incorporating knowledge of these symmetries into the model, it avoids the need expend parameters and data to learn them. This inherent respect for symmetries is automatically generalized to test data, thereby improving generalization [6. 76, 25). For instance, convolutional neural networks (CNNs) respect the translation symmetries of 2D images, with weight sharing due to these symmetries contributing significantly to their success [54]. Respecting node re-indexing in a scalable manner revolutionized machine learning on graphs [13, 12] and has placed GNNs as main general-purpose tool for processing graph-structured data. Moreover, within GNNs, respecting the 3D Euclidean symmetries of the laws of physics (rotations, reflections, and translations) led to state-of-the-art performance in molecule processing [24].
Our Contribution. In this paper, we focus on GDL for graph-ML. We consider extensions of shift symmetries from images to general graphs. Since graphs do not have a natural notion of domain
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

translation, as opposed to images, we propose considering functional translations instead. We model the group translations on graphs as the group of all unitary operators on signals that commute with the graph shift operator. Such unitary operators are called graph functional shifts. Note that each linear filter layer of standard spectral GNN commutes with graph functional shifts, but the activation function breaks this symmetry. Instead, we propose non-linear spectral filters (NLSFs) that are fully equivariant to graph functional shifts and have universal approximation properties.
In Sec. 3, we introduce our NLSFs based on new notions of analysis and synthesis that map signals between their spde-space representations and spectral representations. Our transforms are related to standard graph Fourier and inverse Fourier transforms but differ from them in one important aspect. One key property of our analysis transform that it independent of a specific choice of Laplacian eigenvectors. Hence, our spectral representations are transferable between graphs. In comparison, standard graph Fourier transforms are based on an arbitrary choice of eigenvectors, and therefore, the standard frequency domain is not transferable. To achieve transferabilityy standard graph Fourier methods resort to linear filter operations based on functional calculus. Since we do not have this limitation, we can operate on the frequency coefficients with arbitrary nonlinear functions such as multilayer perceptrons. In Sec. 4, we present theoretical results of our NLSFs, including the universal approximation and expressivity properties. In Sec. 5, we demonstrate the efficacy of our NLSFs in node and graph classification benchmarks, where our method outperforms existing spectral GNNs.
2 Background
Notation. For N E N, we denote [M] = fI,..., .N. We denote matrices by boldface uppercase letter B, vectors (assumed to be columns) by lowercase boldface b, and the entries of matrices and vectors are denoted with the same letter in lower case, e.g.. B = (ba.s (bL.))..EE())- Let G = ([N]] E, A, X) be an undirected graph with a node set [N] an edge set & C [N] x [M], an adjacency matrix A E R N representing the edge weights, and a node feature matrix (also called a signal) X E R Nxd containing d-dimensional node attributes. Let D be the diagonal degree matrix of G, where the diagonal element di,; is the degree of node i. Denote by A any normal graph shift operator (GSO). For example, A could be the combinatorial graph Laplacian or the normalized graph Laplacian given by L= D A and N D à
LD- 3, respectively. Let A VAV be the eigendecomposition of A, where V is the eigenvector matrix and A = diag(A1,
Ax) is the diagonal matrix with eigenvalues (Ax), ordered by |^ı| I .... I | An eigenspace the span of all eigenvectors corresponding to the same eigenvalue. Let P; = P a: denote the projection upon the i-th eigenspace of A in increasing order of | We denote the Euclidean norm by |X|| We define the channel-wise signal norm
|| sig of a feature matrix X E Nxd as the vector |X|l. = (I)X:., 12) E Rd, where X., is
the j-th column on X and S a < 1. We abbreviate multilayer perceptrons by MLP.
2.1 Linear Graph Signal Processing
Spectral GNNs define convolution operators on graphs via the spectral domain. Given a self-adjoint graph shift operator (GSO) A, e.g., graph Laplacian, the Fourier modes of the graph are defined to be the eigenvectors { {v; J of A and the eigenvalues {Ar) are the frequencies. A spectral filter is defined to directly satisfy the "convolution theorem" [11] for graphs. Namely, given signal
X E IR and a function Q R idd' xd, the operator Q(A): Nxd + Nx.'' defined by
Q Σ v.v. XQ(A)T,
(I)
is called filter. Here, d' is the number of output channels. Spectral GNNs, e.g., [21, 49, 61, 5], are graph convolutional networks where convolutions are via Eq. (1), with a trainable function Q at each layer, and nonlinear activation function.
2.2 Equivariant GNNs
Equivariance describes the ability of functions f to respect symmetries. is expressed as ((H, = (x),, where K. x +> H is an action of a symmetry group K. on the domain of f. GNNs [83, 14], including spectral GNNs [22, 49] and subgraph GNNs [31, 4], are inherently permutation equivariant

---

w.r.t. the ordering of nodes. This means that the network's operations are unaffected by the specific arrangement of nodes, property stemming from passive symmetries [95] where transformations are applied to both the graph signals and the graph domain. This permutation equivariance is often compared to the translation equivariance in CNNs [56, 57], which involves active symmetries [44]. The key difference between the two symmetries lies in the domain: while CNNs operate on fixed domain with signals transforming within it, graphs lack a natural notion of domain translation. To address this, we consider graph functional shifts the symmetry group, defined by unitary operators that commute with the graph shift operator. This perspective allows for our NLSF's to be interpreted extension of active symmetry within the graph context, bridging the gap between the passive and active symmetries inherent to GNNs and CNNs, respectively.
3 Nonlinear Spectral Graph Filters
In this section, we present new concepts of analysis and synthesis under which the spectral domain is transferrable between graphs. Following these concepts, we introduce new GNNs that equivariant to functional symmetries symmetries of the Hilbert space of signals rather than symmetries in the domain of definition of the signal [64].
3.1 Translation Equivariance of CNNs and GNNs
For motivation, we start with the grid graph R with node set [M] and circular adjacency B, we define the translation operator T Tm, by [m, n] as
(Tm, X1,k where (i-m) mod M and A: = (j-n) mod M. Note that any Tm,n is unitary operator that commutes with the grid Laplacian AR. i.c. Tm, AR = AnTT,, and therefore it belongs to the group of all unitary operators U4 that commute with the grid Laplacian AR. In fact, the space of isotropic convolution operators (with 90" rotation and reflection symmetric filters) can be seen the space of all normal operators' that commute with unitary operators from Un [18]. Applying a non-lineen -on-line after the convolution retains this equivariance, and hence, we can build multi-layer CNNs that commute with UR. By the universal approximation theorem [19, 34, 58), this allows us to approximate any continuous function that commutes with Un.
T Tm.n E IR MRMMMxMM M2;
Note that such translation equivariance cannot be extended to general graphs. Achieving equivariance to graph functional shifts through linear spectral convolutional layers Q( is straightforward. since these layers commute with the space of all unitary operators Ul that commute with A. However, introducing non-linearity p( ((()()))))))))))() breaks the symmetry. That is, there exists E Ua such that p (Q(A)UXX * Up (Q)A)))
where p is any non-line linear activation function, e.g.. ReLU, Sigmoid, etc.
This means that multi-layer spectral GNNs do not commute with Ug. and are hence not appropriate as approximators of general continuous functions that commute with UG (see App. for an example illustrating how non-linear activation functions break the functional symmetry). Instead, we propose in this paper multi-layer GNN that is fully equivariant to UG. which we show to be universal: can approximate any continuous graph-signal function (w.rt. some metric) commuting with UG.
3.2 Graph Functional Symmetries and Their Relaxations
We define the symmetry group of graph functional shifts as follows.
Definition (Graph Functional Shifts). The space of graph functional shifts is the unitary subgroup Us where a unitary matrix U is in Us iff it commutes with the GSO A, namely, UA = AU.
It is important note that functional shifts, in general, are not induced from node permutations. Instead, functional shifts are related to the notion of functional maps [73] used in shape correspon- dence and are general unitary operators that are not permutation matrices in general. The value of the functionally translated signal at a given node can be mixture of the content of the original signal at many different nodes. For example, the functional shift can be combination of shifts of different frequencies at different speeds. See App. B for illustrations and examples of functional translations.
'The operator B is normal iff B' "B- BB", Equivalently, iff B has an orthogonal eigendecomposition.
3

---

A fundamental challenge with the symmetry group in Def. is its lack of transferability between different graphs. Hence, we propose to relax this symmetry group. Let g1..... Is R. be the indicator functions of the intervals
which constitute a partition of the frequency band [s] C TR. The operators gj( (A), interpreted via functional calculus Eq. (1), are projections of the signal space upon band-limited signals. Namely, gj (ك Ei V.V." In our work,
consider filters gj that are supported on the dyadic sub-bande [ANr ANN ANrS->1, where 0 < r < 1 is the decay rate. See Fig. 5 in App. F for an illustrated example. Note that for j = 1, the sub-band falls in [0, ANT The total band [0, is [0, ).
Definition 2 (Relaxed Functional Shifts). The space of relaxed functional shifts with respect to the filter bank {9a 1= j=1 (of indicators) is the unitary subgroup U2g, where a unitary matrix U is in Ug iff commutes with g3 (A) for all j. namely, (A) ()(
Similarly, relax functional shifts by restricting to the leading eigenspaces.
Definition 3 (Leading Functional Shifts), The space of leading functional shifts is the unitary subgroup Ut where a unitary U is in Ug iff it commutes with the eigenspuce projections (Pz})=r
3.3 Analysis and Synthesis
We use the terminology of analysis and synthesis, as in signal processing [68], to describe transforma- tions of signals between their graph and spectral representations. Here, we consider two settings: the eigenspace projections case and the filter bank (of indicators) case. The definition of the frequency domain depends on a given signal X E R.xdd where its projections to the eigenspaces of A are taken as the Fourier modes. Spectral coefficients are modeled as matrices R. that mix the Fourier modes, allowing to synthesize signals of general dimensions.
Spectral Index Case. We first define analysis and synthesis using the spectral index up to frequency J. Let PJ+1 = I- Σ P, be the orthogonal complement to the first J eigenprojections. Let X E IR Nxd be the graph signal and R e ((++))xx(J+)i the spectral coefficients to be synthesized,
where d represents number of output channels. The analysis and synthesis are defined respectively by
J+1
A A, x)= (IP
J+1
R (J+1j and (R A.)
P,X
R. (2)
||
sig +e
j=1
where I a < and < e < are parameters that promote stability, and the power I a sig as well as the division in Eq. (2) are element-wise operations on each entry. Here,
+ +]] J+1 j=1 E NxJ+1)d denotes concatenation. We remark that the orthogo-
nal complement in the (J + 1)-th filter alleviates the loss of information due to projecting to the low-frequency bands, and therefore, the full spectral range of the signal can be captured. This is particularly important for heterophilic graphs, which rely on frequecyy components for accurate label representation. The term inder stems from the fact that eigenvalues are treated according to their index when defining the projections P,, Note that the synthesis here differs from classic signal pro- cessing as it depends operation is denoted by Sia (R) == gind (R: X).. We similarly denote And (X) = Ainn (A, X).
given signal on the graph. When treating A and X as fixed, this synthesis
Filter Bank Case. Similarly, we define the analysis and synthesis in the filter bank up to band gK as follows. Let 9K 9 (A) = I Σ 9j (A) denote the orthogonal complement to the first K bands. Let X E Nxd be the graph signal, and let R E R(K-1)dx represent the spectral coefficients to be synthesized, where d refers to the general dimension. The analysis and synthesis in the filter bank case are defined by
K
A val A, X) = (I19: i=1 E { and Sval (R: (R =
K+1
9
A
X
R
[9gs(
X +
a sig
(3)
respectively, where a, e are as before. Here, (A) The term value refers to how eigenvalues are used based on their magnitude when defining the projections 9,( A). As before, we denote A. and Ayal.
K+1
E Nx(K+1]

---

Nonlinear spectral filters
Output
Synthesis to graph domain S
|
119 ( (A)
Input
Analysis to spectral domain A
Spectral Domain
Graph Domain
Figure 1: Illustration nonlinear spectral filters for equivariant machine learning on graphs. Given a graph G, the node features X are projected onto eigenspaces (analysis A). The function ! map a sequence of frequency coefficients sequence of frequency coefficients. The coefficients are synthesized to the graph domain using the using S.
In App. C.I, we present special case of diagonal synthesis where d d= d. In App. D.3, we show that the diagonal synthesis is stably invertible.
3.4 Definitions of Nonlinear Spectral Filters
We introduce three novel types of non-linear spectral filters (NLSF): Node-level NLSFs, Graph-level NLSFs, and Pooling-NL.S NLSFs. Fig. illustrates our NLSFs for equivariant machine learning on graphs.
Node-level NLSFs. To be able to transfer NLSFs between different graphs and signals, one key property of NLSF is that they not depend on the specific basis chosen each eigenspace. This independence is facilltated by the synthesis process, which relies on the input signal X. Following the spectral index and filter bank cases in Sec. 3.3, we define the Index NLSFs and Value NLSFs by
J+1
ind A, X
(ind)) A.X Vnd (AA (innt)) (ind)
(X)))
P,X
Vind (IP:X
J+1
(4)
| sig
+
i=1
K+1
Pral A, X)
(vall) A.X (a
(Aa (m4 (X)))
g
X
Vval (I19(AA)
K+1
|19
A
+
i=1
sig
j=1
(5)
where Vind R(J+1)d [(J+I))x((+1)d and Vaa [K++) (K(K))xx((Xx) are called nonlinear frequency responses, and d is the output dimension. To adjust the feature output dimension. we apply an MLP with shared weights to all nodes after the NLSF, In the case when and the filters operator diagonally (i.e., the product and division are element-wise in synthesis), we refer to it as diag-NLSF. See App. for more details.
Graph-level NLSFs. We first introduce the Graph-level NLSFs that are fully spectral. where the NLSFFs map sequence of frequency coefficients to an output vector. Specifically, the Index-based and Value-based Graph-level NLSFF are given by
ind A X)
V ind (I sig
and P (A,
X) V (199
(A)
(6)
where V IR (J+1)d 12d",
V (K + Idd and d' is the output dimension.
Pooling-NLSFs, We introduce another type of graph- NLSFF by first representing each graph in a Node-level NLSFs as in Eq. (4) and Eq. (5). The final graph representation is obtained by applying a nonlinear activation function followed by a readout function to these node-level representations. We consider four commonly used pooling methods, including mean, sum, max, and Lornormm pooling, as the readout function for each graph. We apply an MI.P after readout function to obtain d'- dimensional graph-level representation. We term these graph-level NLSFs as Pooling-NLSFs,
5

---

(V,
Attention
Index NLSPs
(r' X)
1 (1-0 a
( liie
U
Value
rr (
Illustration of Laplacian attention NI.SFs. An attention mechanism is applied to both Index NL.SFs and Value NLSFs, enabling the adaptive selection of the most appropriate parameterization.
Figure 2:
3.5 Laplacian Attention NLSFs
To understand which Laplacian and parameterization (index v/s value) of the NLSF are preferable in different settings, we follow the random geometric graph analysis outlined in [74]. Specifically, we consider setting where random geometric graphs sampled from metric-probabile In such a case, the graph Laplacian approximates continuous Laplacians on the metric spaces under some conditions. We aim for our NLSFs to produce approximately the same outcome for any two graphs sampled from the same underlying metric space S, ensuring that the NLSF is transferable. In App. D.5, show that if the nodes of the graph sampled uniformly from S, then using the graph Laplacian L in Index NLSFs yields a transferable method. Conversely, if the nodes of the graph are sampled non-uniformly, and any two balls of the same radius in S have the same volume, then utilizing the normalized graph Laplacian N in Value NLSF's is a transferable method. Given that graphs may fall between these boundary cases, we present an architecture that chooses between the Index NLSFs with respect to L and Value NLSFs with respect to N, as illustrated in Fig. 2. While the above theoretical setting may be appropriate as a model for every real-life graph dataset, it suggests that index NLSF may be more appropriate with L, value NLSFs with N, and different graphs are more appropriately analyzed by different balances between these two cases.
space S.
In the Laplacian attention architecture, soft attention mechanism is employed to dynamically choose between the two parameterizations, given by
att (Oma (L, X), v (N,)) x)) = o (L, x1 - 0a N, X),
where 0 S < 1 is obtained using softmax function to normalize the scores into attention weights, balancing each NLSFs' contribution.
4 Theoretical Properties of Nonlinear Spectral Filters
We present the desired theoretical properties of our NLSFF at the node-level and graph-level.
4.1 Complexity of NLSFs
NLSFs are implemented by computing the eigenvectors of the GSO. Most existing spectral GNNs avoid direct eigendecomposition due to its perceived inefficiency. Instead, they use filters implemented by applying polynomials [49, 22] or rational functions [61, 5] to the GSO in the spatial domain. However, power feeration-based eigendecomposition algorithms, e.g., variants of the Lanczos method, can be highly efficient [80, 55J. For matrices with E non-zero entries, the computational complexity of one iteration for finding J eigenvectors corresponding to the smallest or largest eigenvalues (called leading eigenvectors) is OJE)). In practice, these eigendecomposition algorithms converge quickly due to their super-exponential convergence rate, often requiring only a few iterations, which makes them as efficient as message passing networks of signals with vJ channels.
This makes NLSFs applicable to node-level tasks on large sparse graphs, as demonstrated empirically in App. F.5, since they rely solely on the leading eigenvectors. In Sec. 4.4, we show that using the leading eigenvectors can approximate GSOs well in the context of learning on graphs. Note that we can precompute the spectral projections of the signal before training. For node-level tasks, such as semi-supervised node classification, the leading eigenvectors only need to be pre-computed once, with a complexity of (JF.). This During the learning phase, each step of the architecture search and hyperparameter optimization takes JdN complexity for analysis and synthesis, and O(J2d))

---

for the MLP in the spectral domain, which is faster than the complexity O of message passing or standard spectral methods if NJ < Ed. Empirical studies on runtime analysis are App. F.
For dense matrices, the computational complexity of a full eigendecompooition is O(N)) per iteration, where Nº is the complexity of matrix multiplication. This is practical for graph-level tasks on relatively small and dense graphs, which is typical for many graph classification datasets. In these cases, the eigendeconposition of all graphs in the dataset can be performed as a pre-computation step, significantly reducing the complexity during the learning phase.
4.2 Equivariance of Node-level NLSFF
We demonstrate the node-level equivariance of our NLSFs, ensuring that our method respects the functional shift symmetries. The proof is given in App. D.I.
Proposition 1. Index NLSFs in Eg. (4) are equivariant to the graph functional shifts Us, and Value NLSFs in Eq. (5) are equivariant to the relaxed graph functional shifts U
4.3 Universal Approximation and Expressivity
In this subsection, we discuss the approximation power of NLSFs.
Node-Level Universal Approximation. We begin with a setting where graph is given as a fixed domain, and the data distribution consists of multiple signals defined on this graph. An example of this setup is a spatiotemporal graph [17]. e.g.. traffic networks, where a fixed sensor system defines a graph and the different signals represent the sensor readings collected at different times.
In App. D.2.1, we prove the following lemma, which shows that linear NLSFs exhaust the space of linear operators that commute with graph functional shifts.
Lemma 1. A linear operator RN Nxd N commutes with UA (resp. U2a) iff it is a NLSF based on a linear function V in Eq. (4) (resp. Eq. (5)).
Lemma shows close relationship between functions that commute with functional shifts and those defined in the spectral domain. This motivates the following construction of pseudo-metric on N In the case of relaxed functional shifts, we define the standard Fuclidean metric distg in the spectral domain (k)xx We pull back the Euclidean metric to the spatial domain to define signal pseudo-metric. Namely, for two signals X and X', their distance is defined by
dist (X, (X, X') == distg (A(A, X), A(A', (())))))
This pseudo metric can be made into a metric by considering each equivalence class of signals with zero distance as single point in the space. As MLPs V can approximate any continuous function R [K-+)) + R(K+1)xd (the universal approximation theorem [19, 34, 58)), node-level NL.FFs can approximate any continuous function that maps (equivalence classes of) signals to (equivalence classes of) signals. For details, see App. D.2.2. A similar analysis applies to hard functional shifts.
Graph-Level Universal Approximation. The above analysis also motivates the construction of graph-signal metric for graph-level tasks. For graphs with d-channel signals, we consider again the standard Euclidean metric distg in the spectral domain R x)) We define the distance between
any two graphs with GSOs and signals (A,X) X) and (Ai X') to be
dist((,, X), (A', x') dist (A(A,X) A(A''')
This definition can be extended into metric by considering the space G of equivalence classes of graph-signals with distance O. As before, this distance inherits the universal approximation properties of standard MLPs. Namely, any continuous function & dR with respect to dist can be approximated by NLSFs based on MLPs. Additional details are in App. D.2.3.
Graph-Level Expressivity of Pooling-NLSFss. In App. D.2.4, we show that Pooling-NLSH NNSSss are more expressive than graph-leved NLSF when any Lp norm used in Eq. (4) and Eq. (5) with p * both in the definition of the NLSF and as the pooling method. Specifically, for every graph-level that coincides with it. Additionally, there are graph signals (A, X)
NLSF, there is a Pooling-NL.s and (A, X') for which Pooling-NI. NF can attain different values, whereas any graph-level NL.FF must attain the same value. Hence, Pooling-NI NLSSFs have improved discriminative power compared to graph-level NLSFs. Indeed, as shown in Tab. 3, Pooling- NLSFs outperform Graph-level NLSFs in
7

---

Table I: Semi-supervised node classification accuracy.
Cora
Citeseer
Pubmed
Chamelcon
Squirrel
Actor
GCN
81.92=0.9
70.73
80.14
43.64
33.26408
27.63=1.
GAT
83.64
71.32+13
79.45
42.19
28.21
29.46=09
SAGE
74.01 =2.1
66.40a12
79.91 any
41.92.07
27 17.11
10.85
ChebNet
79.72=1.1
70.48:110
76.47
44.95
33.82108
27.42::23
ChebNeill
83.95
71.76
81.3811.
46.37
34.4021.1
33.48
CayleyNet
81.76=1.9
68.32=13
77.48+2.1
38.29=32
26.53+33
30.62=288
APPNP
83.19=0.
71.93-008
82.69:14
37.43=19
25.68+1.
35.98
GPRGNN
82.82=1.3
70.28=14
81.31
39.27=23
26.09
31.47=15
ARMA
81.64
69.91
79.24..0
39.40
27 17.77
30.42:25
JacohiConv
84.12=0.7
72.59
82.05.19
49.66219
33.65
34.61
BernNet
82.96=1.1
71.25
81.07
42.65
31.68118
33,92.08
Speeformer
82.27=0.7
73.45+14
81,62+10
49.79+12
38 +8.24
34,12:05
OptBasisGNN
81.97=1.2
70.46=1.
80.38+0.9
47.12=24
37.66#1.1
34.84=13
att Neve- NLSFS
85.37=118
=5.41=00
82.22+1.2
50.58
38.39
35.13=10
practice, which can be attributed their increased expressivity. We refer App. D.2.5 for additional discussion graph-level expressivity.
4.4 Uniform Approximation of GSOs by Their Leading Eigenvectors
Since NLSFs large graphs are based on the leading eigenvectors of A, justify its low-rank approximation in the following. While approximating matrices with low-rank matrices might lead to high error in the spectral and Frobenius norms, we show that such an approximation entails a uniformly small error in the cut norm. We define and interpret the cut norm in App. D.4.1, and explain why it natural graph similarity measure for graph machine learning.
The following theorem is a corollary of the Constructive Weak Regularity Lemma presented in [29]. Its proof is presented in App. D.4.
Theorem 1. Let M be a symmetric matrix with entries bounded by |maJl S. a, and let J E N. Suppose m is sampled uniformly from [J], and let 2 1 s.t. J/R N. Let $1...., ........m... be the
leading eigenvectors of M, with eigenvalues fi...., Hm ordered by their magnitudes |pa] 2 [pm]] Define C -E (A P. Then, with probability
(w.r.. the choice of m))
< 3a
R
- MM-
Note that the bound in Thm. is uniformly small, independently of M and its dimension N. This theorem justifies using the leading eigenvectors when working with the adjacency matrix as the GSO. For justification when working with other GSOs see App. D.4.
5 Experimental Results
We evaluate the NLSFs node and graph classification tasks. Additional implementation details in App. E, and additional experiments, including runtime analysis and ablation studies, are in App. F.
5.1 SuperiSuee Node Classification
We first demonstrate the main advantage of the proposed Node-level NLSFs over existing GNNs with convolution design on semi-supervised node classification tasks. We test three citation networks [84, 100]: Cora, Citeseer, and Pubmed. In addition, we explore three heterophilic graphs: Chameleon, Squirrel, and Actor [79, 90]. For more comprehensive descriptions of these datasets, see App. E.
We compare the Node-level NLSFs using Laplacian attention with existing spectral GNNs for node- level predictions, including GCN [49], ChebNet [22], ChebNetll [41], CayleyNet [61], APPNP [50], GPRGNN [16], ARMA [5], JacobiCony [96], BernNet [42], Specformer [7]. and OptBasisGNN [38]. We also consider GAT [93] and SAGE [39]. For datasets splitting on citation graphs (Cora, Citeseer, and Pubmed), apply the standard splits following [100], using 20 nodes per class for training,
8

---

500 nodes for validation, and 1000 nodes for testing. For heterophilic graphs (Chameleon, Squirrel, and Actor), we use the sparse splitting as in [16, 41], allocating 2.5% of samples for training. 2.5% for validation, and 95% for testing. We measure the classification quality by computing the average classification accuracy with a 95% confidence interval over 10 random splits. We utilize the source code released by the authors for the baseline algorithms and optimize their hyperparameters using Optuna [l]. Each model's hyperparameters are fine-tuned to achieve the highest possible accuracy. Detailed hyperparameter settings are provided in App. E.
Tab. presents the node classification accuracy of our NLSFs using Laplacian attention and the various competing baselines. We see that att att-Node-level NLSFs outperform the competing models on the Cora, Citeseer, and Chameleon datasets. Notably, shows remarkable performance on the densely connected Squirrel graph, outperforming the baselines by a large margin. This can be explained by the sparse version Eq. (21) of Thm. I, which shows that the denser the graphs is, the better its rank-J approximation. For the Pubmed and Actor datasets, att-Node-level NLSFs yield the second-best results, which are comparable to the best results obtained by APPNP.
5.2 Node Classification on Filtered Chameleon and Squirrel Datasets in Dense Split Setting
Recently, the work in [77] identi- fied the presence of many duplicate nodes across the train, validation, and test splits in the dense split set- ting of the Chameleon and Squirrel [75]. This results in train-test data leakage, causing GNNs to inadver- tently fit the test splits during train- ing, thereby making performance re- sults on Chameleon and Squirrel less reliable. To further validate the per- formance of our Node-level NLSFs
Table 2: Node classification performance original and filtered Chameleon and Squirrel datasets.
Chameloon
Squirrel
Original
Filtered
Original
Filtered
ResNet+SOC
49.93=2.3
41.01=45
34.36
38.36=20
ResNet+udj
71.07
38.67-39
65,46
38.37=20
GCN
50.18
40.89=411
39.06=15
39.47=15
GPRGNN
47.26
39 39.93-33
33.39a21
38.95=20
FSGNN
77.85
40.61=30
68.93
35.92=13
GloGNN
70.04-2.1
25.90
61.21
35.11=12
FAGON
64.23:22.
41.90-22
47.63219
41.08-2a
att-Node-level NLSFs
79.84
42,53-15
68.17
42.66-1.7
on these datasets in the dense split setting, we use both the original and filtered versions of Chameleon and Squirrel. which do not contain duplicate nodes, suggested in [77]. We use the same random splits as in [77], dividing the datasets into 48% for training, 32% for validation, and 20% for testing.
Tab. 2 presents the classification performance comparison between the original and filtered Chameleon and Squirrel. The baseline results are taken from [77], and we include the following competitive models: ResNet+SGC [77], ResNet+adj [77], GCN [49], GPRGNN [16], FSGNN [69], GloGNN [62], and FAGCN [8]. The detailed comparisons are in App. F. We see in the table that the att- Node-level NLSFs consistently outperform the competing baselines on both the original and filtered datasets. att-Node-level NLSFs demonstrate less sensitivity to node duplicates and exhibit stronger generalization ability, further validating the reliability of the Chameleon and Squirrel datasets in the dense split setting. We note that compared to the dense split setting, the sparse split setting in Tab. I is more challenging, resulting in lower classification performance. A similar trend of significant performance difference between the two settings of Chameleon and Squirrel is also observed in [41].
5.3 Graph Classification
We further illustrate the power of NLSFFs on eight graph classification benchmarks [47]. Specifically, we consider five bioinformatics datasets [10, 53, 86]: MUTAG, PTC, NCI1, ENZYMES, and PROTEINS, where MUTAG, PTC, and NCII are characterized by discrete node features, while ENZYMES and PROTEINS have continuous node features. Additionally, we examine three social network datasets: IMDB-B, IMDB-M, and COLLAB. The unattributed graphs are augmented by adding node degree features following [26]. For more details of these datasets, see App. E.
In graph classification tasks, a readout function is used to summarize node representations for each graph. The final graph-level representation is obtained by aggregating these node-level summaries and is then fed into an MLP with a (log)softmax layer to perform the graph classification task. We compare our NI NFF with two kernel-based approaches: GK [87] and WI. [86], as well as nine GNNs: GCN [49], GAT [93], SAGE [39], ChebNet [22], ChebNetll [41], CayleyNet [61], APPNP [50]. GPRGNN [16], and ARMA [5]. Additionally, consider the hierarchical graph pooling model

---

Table 3: Graph classification accuracy.
MUTAG
PTC
ENZYMES
PROTEINS
NCI1
IMDB-B
IMDB-M
COLLAB
GK
76.38
52.13
30.07=6.1
72.33=45
62.62
67.63-10
44.19
72.32
W1.
18
52.44
51.29
76.20
76.45a23
71.42
46.63213
76.23
GCN
81.63
60.22
43.66 33.66:34
75.17=37
76,29
12.96=13
50.28
79,98
GAT
83.17
62.31
74.72.41
2:411
70.62.25
45.67.111
74.27
SAGE
75. 15.18:44
61.33
37.99=37
74.01 =433
74.90
68.38:226
46,94=29
73.61
DitPolol
82.40
56,43229
60.13
79.47=9.1
77.18
71I191A
50,43215
80. 11
ChebNet
82. 16
64.06+12
50.42=14
74.28=00
76,98+a21
73.14
49.82#1.5
77. 17
ChebNeill
84.17 17:31
70.03+28
64.29 (4.29=29
78.31
81.14:36
77.09:39
52.69=27
80.06#33
Cayley Net
83.06
62.73
42.28
74.12:277
77.21 2:4.
71 45:444
51.89 51.89219
36.33
APPNP
84.45=44A
65.26
49.68=39
77.26=4X
73.24
72.94=2.3
44.36#19
73.85
GPRONN
80.26 80.26:220
58.41
45.29 1.
73.90
73.12:40
69. 69.17:22
47.07
77 77.93219
ARMA
83.21=27
69.23
61.21=34
76.62=33
79.51
73.27=a27
53.60
78.3 18.34
att-GGraph-level NIS
13
17.17
82.69
80,51
74.26.1
52.49.07
79.00 19.061112
att-Pooling NLSFs
PosSs
86.89
1..02
69.94=1.
84.89
80.95
76.78#119
55,28
82.19
DiftPool [101]. For dataset splitting, we apply the random split following [94, 101, 67, 104], using 80% for training, 10% for validation, and 10% for testing. This random splitting process repeated 10 times, and we report the average performance along with the standard deviation. For the baseline algorithms, we use the source code released by the authors and optimize their hyperparameters using Optuna [1]. We fine-tune the hyperparameters of each model to achieve the highest possible accuracy. Detailed hyperparameter settings for both the basclines and our method are provided in App. E.
Tab. 3 presents the graph classification accuracy. Notably, the att-Graph-level NLSFs (i.e.. NLSFs without the synthesis and pooling process) perform the second best on the ENZYMES and PROTEINS. Additionally, att Sett-Pooling-NSS the node features learned in our Node-level NLSFs representation are more expressive, corroborating our theoretical findings in Sec. 4.3. Furthermore, our att-Pooling-NLSTSs consistently outperform all baselines on the MUTAG, PTC, ENZYMES, PROTEINS, IMDB-M, and COLLAB datasets. For NCII and IMDB-B. att- Gooling-NLSHE rank second and are comparable to ChebNetII.
consistently outperform Set--Graph-level NLSFs, indicating that
6 Summary
We presented an approach for defining non-linear filters in the spectral domain of graphs in transferable and equivariant way. Transferability between different graphs achieved by using the signal as a basis for the synthesis operator, making the NLSF depend only on the eigenspaces of the GSO and not on an arbitrary choice of the eigenvectors. While different graph-signals may be of different sizes, the spectral domain is fixed Euclidean space independent of the size and topology of the graph. Hence, our spectral approach represents graphs as vectors. We note that standard spectral methods do not have this property since the coefficients of the signal in the frequency domain depend on an arbitrary choice of eigenvectors, while our representation depends only on the eigenspaces. We analyzed the universal approximation and expressivity power of NLSFs through metrics that are pulled back from this Euclidean vector space. From a geometric point of view, our NLSFs are motivated by respecting graph functional shift symmetries, making them related Fuclidean CNNs.
Limitation and Future Work. One limitation of NLSFF is that, when deployed on large graphs, they only depend on the leading cigenvectors of the GSO and their orthogonal complement. However, important information can also within any other band. In future work, we plan to explore NLSFs that are sensitive to eigenvalues that lie within set of bands of interest, which can be adaptive to the graph.
Acknowledgments
The work of YEL and RT was supported by the European Union's Horizon 2020 research and innovation programme under grant agreement No. 902735-ERC-DIFFOP The work of RL was supported by the Israel Science Foundation grant No. 1937/23, and the United States Israel Binational Science Foundation (NSF-BSF) grant No. 2024660.
10

---

References
[1] T. Akiba, S. Sano, T. Yanase, T. Ohta, and M. Koyama. Optuna: A next-generation hyper- parameter optimization framework. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages
[2] Atz, Grisoni, and G. Schneider. Geometric deep learning on molecular representations. Nature Machine Intelligence, 3:1023-1032, 2021.
[3] A.-L. Barabasi and N. Oltvi.. Network biology: understanding the cell's functional organization. Nature reviews genetics, 5(2):101-113, 2004.
[4] Bevilacqua, Frasca, D. Lim, B. Srinivasan, C. Cai, G. Balamurugan, M. M. Bronstein, and H. Maron. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2022.
[5] F. M. Bianchi, D. Grattarola, L. Livi, and C. Alippi. Graph neural networks with convolutional ARMA filters, IEEE transactions on pattern analysis and machine intelligence, 44(7):3496 3507, 2021.
[6] A. Bietti, L. Venturi, and Bruna, On the sample complexity of learning with geometric stability. arXiv preprint arXiv:2106.0711 2021.
[7] D. Bo, C. Shi, L. Wang, and R. Liao. Specformer: Spectral graph neural networks meet transformers. In The Eleventh International Conference Learning Representations, 2023.
[8] D. Bo, X. Wang, C. Shi, and H. Shen. Beyond low- frequenq information in graph convolu- tional networks. In Proceedings the AAAI conference artificial intelligence, volume 35, pages 3950-3957, 2021.
[9] S. P. Borgatti, A. Mehra, J. Brass, and G. Labianca. Network analysis in the social sciences. science, 523(5116: 2009.
[10] K. M. Borgwardt, C. S. Ong, S. Schönauer, S. Vishwanathan, A. J. Smola, and H.-P. Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21 [1supp]_ 2005.
[11] R. Bracewell and P. B. Kahn. The fourier transform and its applications. American Journal of Physics, (4((8)7712771) 1966.
[12] M. M. Bronstein, J. Bruna, T. Cohen, and P. Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. preprint arXiv:2104.13478, 2021.
[13] M. M. Bronstein, Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst. Geometric deep learning: Going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-42, 2017.
[14] J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv: 1312.6223 2013.
[15] D. Burago, S. O. Ivanov, and Y. Kurylev. Spectral stability of metric-measure laplacians. Israel Journal of Mathematics, 232:125-158, 2019.
[16] E. Chien, J. Peng. P. Li, and O. Milenkovic. Adaptive universal generalized pagerank graph neural network. International Conference on Learning Representations, 2020.
[17] A. Cini and I. Marisca. Torch Spatiotemporal, 3 2022.
[18] T. Cohen and Welling. Group equivariant convolutional networks. In ICMI., pages 2990-2999, PMLR, 2016.
[19] Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.

---

[20] A. Daigavane, S. Kim, M. Geiger, and T. Smidt. Symphony: Symmetry-equivarie point- centered spherical harmonics for molecule generation. arXiv preprint arXiv:2311.16199 2023.
[21] M. Defferrard, X. Bresson, and P. Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NeurlPS. Curran Associates Inc., 2016.
[22] M. Defferrard, X. Bresson, and P. Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering, Advances in neural information processing systems, 29, 2016.
[23] L. Du, X. Shi, Q. Fu, X. Ma, H. Liu, S. Han, and D. Zhang. Gbk-gnn: Gated bi-kernel graph neural networks for modeling both homophily and heterophily. In Proceedings of the ACM Web Conference 2022, pages 1550-1558, 2022.
[24] A. Duval, S. V. Mathis, C. K. Joshi, V. Schmidt, S. Miret, F. D. Malliaros, T. Cohen, P. Liò, Y. Bengio, and M. Bronstein. A hitchhiker's guide geometric gnns for 3d atomic systems, 2024.
[25] B. Elesedy and S. Zaidi. Provably striet generalisation benefit for equivariant models. ICML, 2021.
[26] F. Errica, M. Podda, D. Bacciu, and A. Micheli. A fair comparison of graph neural networks for graph classification. In International Conference on Learning Representations, 2019.
[27] P. Esser, L. Chennuru Vankadara, and D. Ghoshdastidar. Learning theory can (sometimes) explain generalisation in graph neural networks. Advances in Neural Information Processing Systems, 34:27043-27056 2021.
[28] M. Fey and J. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[29] B. Finkelshtein, i. i. Ceylan, M. Bronstein, and R. Levie. Learning large graphs using intersecting communities. arXiv preprint arXiv:2405.20724, 2024.
[30] M. Finzi, S. Stanton, P. Izmailov, and A. G. Wilson. Generalizing convolutional neural networks for equivariance lie groups on arbitrary continuous data. In International Conference on Machine Learning, pages 3 3165-3176. PMLR, 2020.
[31] F. Frasca, B. Bevilacqua, M. Bronstein, and H. Maron. Understanding and extending subgraph GNN by rethinking their symmetries. Advances in Neural Information Processing Systems, 35:31376-3139, 2022.
[32] A. M. Frieze and R. Kannan. Quick approximation to matrices and applications. Combinator- ica, 1999.
[33] F. Fuchs, D. Worrall, V. Fischer, and M. Welling. trans-rranssos:mr::: roto-translation equivariant attention networks. Advances in neural information processing systems, 33:1970- 1981, 2020.
[34] K.-I. Funahashi. On the approximate realization of continuous mappings by neural networks. Neural networks, 1(3):183-192 83-192, 1989.
[35] V. Garg, S. Jegelka, and T. Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, pages 3419-3430. PMLR, 2020.
[36] T. Gaudelet, B. Day, A. R. Jamasb, J. Soman, C. Regep, G. Liu, J. B. Hayter, R. Vickers, C. Roberts, J. Tang, et al. Utilizing graph machine learning within drug discovery and development. Briefings in bioinformatics, 22(6):bbabl 159, 2021.
[37] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263-1272 PMLR, 2017.
12

---

[38] Y. Guo and Z. Wei. Graph neural networks with learnable and optimal polynomial bases, In International Conference on Machine Learning, pages 12077-12097. PMLR, 2023.
[39] W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs. Advances in Neural Information Processing Systems, 30, 2017.
[40] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770- 778, 2016.
[41] M. He, Z. Wei, and J.-R. Wen. Convolutional neural networks on graphs with chebyshev approximation, revisited. Advances in Neural Information Processing Systems, 35:7264-7276, 2022.
[42] M. He, Z. Wei, H. Xu, et al. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. Advances in Neural Information Processing Systems, 01414429--42511 2021.
[43] W. Hoeffding. Probability inequalities for sums of bounded random variables. The collected works of Wassily Hoeffding, pages 409-426, 1994.
[44] N. Huang, R. Levie, and S. Villar. Approximately equivariant graph networks. Advances in Neural Information Processing Systems, 36, 2024.
[45] J. M. Jumper, R. Evans, A. Pritzel, T. Green, M. Figurnov, O. Ronneberger, K. Tunyasuvu- nakool, R. Bates, A. Zidek, A. Potapenko, A. Bridgland, C. Meyer, S. A. A. Kohl, A. Ballard, A. Cowie, B. Jomera-Paredes, S. Nikolov, R. Jain, J. Adler, T. Back, S. Petersen, D. A. Reiman, E. Clancy, M. Zielinski, M. Steinegger, M. Pacholska,
Berghammer, S. Bodenstein, D. Silver, O. Vinyals, A. W. Senior, K. Kavukcuoglu. P. Kohli, and D. Hassabis. Highly accurate protein structure prediction with alphafold. Nature, 596:583 589, 2021.
[46] Keriven and G. Peyré. Universal invariant and equivariant graph neural networks. Advances in Neural Information Processing Systems, 32, 2019.
[47] K. Kersting, N. M. Kriege, C. Morris, P. Mutzel, and M. Neumann. Benchmark data sets for graph kernels. 2016.
[48] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
[49] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2016.
[50] J. Klicpera, A. Bojchevski, and S. Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2019.
[51] M. Kofinas, B. Knyazev, Y. Zhang, Y. Chen, G. J. Burghouts, E. Gavves, C. G. M. Snoek, and D. W. Zhang. Graph neural networks for learning equivariant representations of neural networks. 2024.
[52] N. J. Korevaar and R. M. Schoen. Sobolev spaces and harmonic maps for metric space targets. Communications in Analysis and Geometry, 1:561-659, 1993.
[53] N. Kriege and P. Mutzel. Subgraph matching kernels for attributed graphs. arXiv preprint 2XXXv:/2066683. 2012.
[54] A. Krizhevsky, Sutskever, and G. Hinton. Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
[55] C. Lanczos. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. 1950.
[56] LeCun, Y. Bengio, al. Convolutional networks for images, speech, and time series. The handbook of brain theory and neural networks, (361 1995.
13

---

[57] Y. LeCun, K. Kavukcuoglu, and C. Farabet. Convolutional networks and applications in vision. In Proceedings of IEEE international symposium on circuits and systems, pages 253-256 IEFE, 2010.
[58] M. Leshno, V. Y. Lin, A. Pinkus, and S. Schocken. Multilayer feedforward networks with nonpolynomial activation function can approximate any function. Neural networks, 6(6):861- 867, 1993.
[59] R. Levie. A graphon-signal analysis of graph neural networks. In NeurfPS, 2023.
[60] Levie, W. Huang. Bucci, M. Bronstein, and G. Kutyniok. Transferability of spectral graph convolutional neural networks. Journal of Machine Learning Research, 22(272):1-59, 2021.
[61] Levie, Monti, Bresson, and M. M. Bronstein. Cayleynets: Graph convolutional neural networks with complex rational spectral filters. IEEE Transactions Signal Processing, 67(1):97-109, 2018.
[62] X. Li, R. Zhu, Y. Cheng, C. Shan, S. Luo, D. Li, and W. Qian. Finding global homophily in graph neural networks when meeting heterophily. In International Conference Machine Learning, pages 33242-13256. PMLR, 2022.
[63] D. Lim, F. Hohne. X. Li, S. L. Huang, V. Gupta, O. Bhalerao, and S. N. Lim. Large scale learning on non- hom-hoooph graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887-20902, 2021.
[64] D. Lim, J. Robinson, S. Jegelka, and H. Maron. Expressive sign equivariant networks for spectral geometric learning. Advances Neural Information Processing Systems, 36, 2024.
[65] L. Lovász and B. Szegedy. Szemerédi's lemma for the analyst. GAPA Geometric And Functional Analysis, 2007.
[66] L. M. Lovász. Large networks and graph limits. In volume 60 of Colloquium Publications, 2012.
[67] Y. Ma. S. Wang. C. C. Aggarwal, and J. Tang. Graph convolutional networks with cigenpooling. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery data mining, pages 723-731, 2019.
[68] S. G. Mallat. A theory for multiresolution signal decomposition: the wavelet representation. IEEE transactions on pattern analysis and machine intelligence, 11(7):674-693, 1989.
[69] S. K. Maurya, X. Liu, and T. Murata. Simplifying approach to node classification in graph neural networks. Journal of Computational Science, 62:10169: 2022.
[70] O. Méndez-Lucio, M. Ahmad, E. A. del Rio-Chanona, and K. Wegner. geometric deep learning approach to predict binding conformations of bioactive molecules. Nature Machine Intelligence, 1-1033-1039, 2021.
[71] F. Monti, D. Boscaini, Masci, E. Rodola, Svoboda, and M. M. Bronstein. Geometric deep learning graphs and manifolds using mixture model cnns. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5115-5124, 2017.
[72] C. Morris, N. M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08665 2020.
[73] M. Ovsjanikov, M. Ben-Chen, J. Solomon. A. Butscher, and L. Guibas. Functional maps: A flexible representation of maps between shapes. ACM Transactions on Graphics (ToG), 3 3144::1-11, 2012.
[74] R. Paolino, A. Bojchevski, S. Günnneman, G. Kutyniok, and R. Levie. Unveiling the sampling density in non-uniform geometric graphs. In The Eleventh International Conference on Learning Representations, 2023.
14

---

[75] H. Pei, B. Wei, K. C.-C. Chang, Y. Lei, and B. Yang. Geom-gen geom-gen: Geometric graph convolu- tional networks. In International Conference on Learning Representations. 2020.
[76] M. Petrache and S. Trivedi. Approximaioo-ennezzizzziiio generalization trade-offs under (approximate) group equivariance. Advances in Neural Information Processing Systems, 36, 2024.
[77] O. Platonov, D. Kuznedelev, M. Diskin, A. Babenko, and L. Prokhorenkova. A critical look at the evaluation of gnns under heterophily: Are we really making progress? In The Eleventh International Conference on Learning Representations, 2023.
[78] O. Puny, D. Lim, B. Kiani, H. Maron, and Y. Lipman. Equivariant polynomials for graph neural networks. In International Conference on Machine Learning, pages 28191-28222. PMLR, 2023.
[79] B. Rozemberezki, C. Allen, and R. Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9()):cnab014 4, 2021.
[80] Y. Saad. Numerical methods for large eigenvalue problems: revised edition. SIAM, 2011.
[81] R. Sato, M. Yamada, and H. Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM international conference on data mining (SDM), pages 333-341. SIAM, 2021.
[82] V. G. Satorras, E. Hoogeboom, and M. Welling, E (n) equivariant graph neural networks. In International conference on machine learning, pages 9323-9332. PMLR, 2021.
[83] F. Scarselli, M. Gori, Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61 2008.
[84] P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad. Collective classifi- cation in network data, Al magazine, 29(3):93 93, 2008
[85] J.-P. Serre et Linear representations finite groups, volume 42. Springer, 1977.
[86]
Shervashidze, P. Schweitzer, E. Van Leeuwen, K. Mehlhorn, and K. M. Borgwardt. Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
[87] N. Shervashidze, S. Vishwanathan, T. Petri, K. Mehlhorn, and K. Borgwardt. Efficient graphlet kernels for large graph comparison. Artificial intelligence and statistics, pages 488-495. PMLR, 2009.
[88] Y. Shi, Z. Huang. S. Feng, H. Zhong, W. Wang, and Y. Sun. Masked label prediction: Unified message passing model for semi-supervised classification. arXiv preprint 20Xv:2000.,3509, 2020.
[89] J. M. Stokes, K. Yang, K. Swanson, W. Jin, A. Cubillos-Ruiz, N. M. Donghia, C. R. MacNair, S. French, L. A. Carfrae, Z. Aloom-Ackermant et al. A deep learning approach to antibiotic discovery. Cell, 180(4)6688-D))))
2020.
[90] J. Tang. J. Sun, C. Wang, and Z. Yang. Social influence analysis in large-scale networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 807-816. 2009.
[91] N. Thomas, T. Smidt, S. Kearnes, Yang, L. Li, K. Kohlhoff, and P. Riley. Tensor field networks: Rotation-am translation translation-equivarini equivariant neural networks for 3D point clouds. arXiv preprint arXiv: 1al::8802.022 08219, 2018.
[92] L. N. Trefethen and D. Bau. Numerical Linear Algebra, Twenty-fifth Anniversary Edition. Society for Industrial and Applied Mathematics, 2022.
[93] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention networks. arXiv preprint 17Xiv:1710.10000 10903, 2017.
[94] P. Velickovic, W. Fedus, W. I.. Hamilton, Liò, Bengio, and R. D. Hjelm. Deep graph infomax. ICLR, 2(3):4, 2019.
15

---

[95] S. Villar, D. W. Hogg, W. Yao, G. A. Kevrekidis, and B. Schölkopf. Towards fully covariant machine learning. arXiv preprint arXiv:2301.13724. 2023.
[96] Wang and M. Zhang. How powerful are spectral graph neural networks. In International conference machine learning, pages 23341-23362. PMLR, 2022.
[97] Y. Wang, Y. Sun, Z. Liu, S. E. Sarma, M. M. Bronstein, and J. M. Solomon. Dynamic graph cnn for learning on point clouds. ACM Transactions on Graphics (tog), 38(5):1-12, 2019.
[98] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip. A comprehensive survey on graph neural networks. JEEE transactions on neural networks and learning systems, 32(1):4-24, 2020.
[99] K. Xu, M. Zhang, J. Li. S. S. Du, K.-i. Kawarabayashi, and S. Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. arXiv preprint arXiv:2009. 1848, 2020.
[100] Z. Yang, W. Cohen, and R. Salakhudinov. Revisiting semi- superviid learning with graph embeddings. In International conference on machine learning. pages 40-48. PMLR, 2016.
[101] Z. Ying, You, C. Morris, X. Ren, W. Hamilton, and Leskovec. Hierarchical graph representation learning with differentiable pooling. Advances in neural information processing systems, 31, 2018.
[102] J. Zhu, R. A. Rossi, A. Rao, T. Mai, N. Lipka, N. K. Ahmed, and D. Koutra. Graph neural networks with heterophily. Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 11168-114 1116,, 2021.
[103] J. Zhu, Y. Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra, Beyond homophily in graph neural networks: Current limitations and effective designs. Advances neural information processing systems, 33:7793-7804, 2020.
[104] Y. Zhu, Y. Xu, F. Yu. Q. Liu, S. Wu, and L. Wang. Graph contrastive learning with adaptive augmentation. In Proceedings of the Web Conference 202/, pages 2069-2080, 2021.
16

---

A Non-linear Activation Functions Break the Functional Symmetry
We offer a construction for complex-valuee signals and first order derivative as the graph Laplacian. which is easy extend to the real case and second order derivative. Consider circular ID grid with 100 nodes and the first order central difference as the Laplacian. Here, the Laplacian eigenvectors the standard Fourier modes. In this case, one that is diagonal in the frequency domain and multiplies each frequency by any complex number with the unit norm. Consider the nonlinearity that takes the real part of the signal and then applies ReLU, which we denote in short by ReLU. Consider graph signal
that graph functional shift is any operator
(e (eir10n/1000 1000 + e === We consider graph functional shift S that shifts frequencies 10 and 20 at a distance of 5, and every other frequency is not shifted. Namely, frequency 10 is multiplied by e e-n50//100 = -i, frequency 20 by 1. and every other frequency is multiplied by I. Consider also the classical shift D that translates the whole signal by 5 uniformly. Since x consists only of the frequencies 10 and 20, is easy to see that Sx Da. Hence, ReI.U(Sz) = (ex) we apply (eI.U(x:) and only then shift, note that (=) consists of many frequencies in addition to 10 and 20. For example, by nonnegativity of ReLU,, ReI.U(x)) has a nonzero DC component (zeroth frequency). Now, S(ReLU(z)) only translates the 10 and 20 frequencies, we have ((eeUU(r)) # D(ReLU(x)) = ReLU(S(x)).
100/100
D(ReLLU<r)) Conversely,
B Illustrating Functional Translations
Here we present an additional discussion and illustrations on the new notions of symmetry.
B.1 Functional Translation of a Gaussian Signal with Different Speeds at Different Frequencies
To illustrate the concepts of relaxed symmetry and functional translation, we present a toy example involving the classical translation and a functional translation of Gaussian signal on 2D grid with a standard deviation of 1.
The classical translation involves moving the entire signal uniformly across the grid. This uniform movement can be represented as I'(x, y) = 1(x lz. fyy, where by and ty are the translation amounts in the x and y directions, respectively, and x tu and y - ty are circular translations. namely, subtractions modulo the size of the circular grid. For simplicity, we consider t, = ty = t. For instance, if 5, the Gaussian is shifted by units in both the x and y directions. Fig. top-row shows the classical translation for t = 0, t = 5, t = 10, and t = 15. We see that every part of the signal shifts at the same rate and direction, preserving the overall shape of the Gaussian signal. Note that classical translation is equivalent to modulation of the frequency domain, i.e. Pl, v) = I(u, u (2rt((tt where i(u, u) is the Fourier transform of I [(x, v). Therefore, can view the classical translation as a specific type of functional translation.
Next, we illustrate functional translation that is based on rrquuency-dependee movement. Specifically, the Gaussian signal is decomposed into low and high-frequency components based on two indicator band-pass filters. In our example, the translation parameter t is different for the low and high-frequee frequerreenny components: low frequencies are shifted by Hoow while high frequencies are shifted by thigh. This functional translation is defined via modulations in the freeuency do- main given by Pionc(u v) = Trou (u, w)ee (oa to,, for low-frequency components and Thigh (u, (u,v) = Thigh (u, -52r--uaa tdy. for high-frequency components. The combined
functionally translated signal in the frequency domain is then /' = (Fimup Thigh.) ). Fig. bottom-row demonstrates the functional translation for / = 0, l = 5, / 10, and / = 15. We observe that the low-frequency components (smooth parts) of the signal move at one speed, while high-frequency components move at another. This demonstrates that functional symmetries are typically more rich than domain symmetries.
17

---

Ciscical Tandacionts
Olosical Tansiation to5
Cassiral Trarelsioon Is10
Chosscal Thanslatin to15
Funciional Tansation
Runctiona Transbilion
Funciional Thand tw100
Functiona:
Figure 3: Comparison of classical and functional translation of Gaussian signal. Top Row (Classical Translation): The Gaussian signal moves uniformly across the grid without changing shape. Bottom Row (Functional Translation): The Gaussian signal translates as low-frequency components move at different speeds than segg-frequency components, demonstrating relaxed symmetry.
B.2 Robust Graph Functional Shifts in Image Translation and MNIST Classification on Perturbed Grids
We present another toy example to illustrate that functional translations are more stable than hard symmetries of the graph, namely, graph automorphisms (isomorphisms from the graph to itself). Automorphisms are another analog to translations on general graphs, which competes with our notion of functional shifts. Consider The automorphisms the grid include translations. However, this notion of hard symmetry is very sensitive graph perturbations. If one adds deletes even one edge in the graph, the automorphism group becomes much smaller and does not contain the translations anymore.
example the standard 2D) cireular grid (discretizing the torus).
In contrast, claim that functional shifts not sensitive graph perturbations. To demonstrate this empirically, we conducted the following toy experiment. We add a Gaussian noise to the edge weights of the 2D grid create a perturbed graph. Given standard domain shift, optimize the coefficients a functional shift so is as close as possible to the classical domain shift of the clean grid in Frobenius error. Fig. presents example of classically and functionally shifted image of the digit 5. The original digit (left), a classical domain translation of the clean grid (middle), and a functional translation constructed from the perturbed graph (right) match the classical translation. We see that standard translations can be approximated by graph functional shift on perturbed grid.
We further demonstrate the robustness to graph perturbations of NLSFs trained on MNIST classi- fication. The experimental setup follows previous work in [22, 71, 61]. We compare the NLSF on the clean grid (i.e., without Gaussian noise) the NLSF the perturbed grid. Tab. 4 presents the classification accuracy the NLSF. We see that the classification performance almost unaffected by the perturbation, indicating that NLSFs on the perturbed grid can roughly express CNN-like operations (translation equivariant functions).
Original
Translated
Func. transieted
MNIST
Perturbed MNIST
Ours
99.19
99.16
Figure 4: Approximate standard translation by functional translation on perturbed graph.
Table 4: Classification accuracy on the MNIST and perturbed MNIST using NLSFs.
18

---

C Special Cases of NLSFs
We present two special cases of NLSFs as follows.
C.1 Diagonal NLSFs
In Sec. 3, we introduced the NLSFs with the output dimension d, which is a tunable hyperparameter. Here, we present special case when = d such that the multiplication and division in synthesis are operated diagonally. Specifically, the diagonal analysis and synthesis in the spectral index case and in the filter bank case are defined respectively by
J+I
Alnd, diag
A
X)=
E RR(+1)xdd
and
(7)
sig
j=1
K+1
A val, diag
X)= = [11g)] (A)
sig
E R
(K+))x
(8)
==1
and
P,X
gind. diag [R: A, X): Σ O
and
(9)
sig
K+1
A
Sval. ding AR = r
Σ
(10)
9
sig te"
j=1
where the product and division are element-wise along the channel direction. That is, rj
?
P.X
P,X.
P,X.J
in the spectral index case (resp. rj
P lig te
P,
in the filter bank case). Here, R = (r 741 E ((++))xd in the spectral index case (resp. R = (r,) E (KK+))x in the
3: (A)
ns a (AX
Ti (1, 2 (AX
lay
(A)
te
(A)x,
(
a
filter bank case) are the spectral coefficients to be synthesized and a, e before.
For Node-level diag-NISSs, we define the Index diag- SSag and Value diag-NISSPs as follows
iidd diag A X)=
(ind, diug) 2
(V (VA (AA (ind)
Σ
J+1
V
(IP:X
J+1
P,X
(11)
1=1
P
==1
val, diag A
X
S (val, diag) A.X
(V (VA (val) (X)))
Σ
K+1
v
(11
sig
K+1
gj
(A
1199
A
X
sig
(12)
where : R(++1)d + (J+1d in Oind ding and V (K+)d + (K(++))d in Oval, ding. To adjust the feature output dimension at each node, we apply MLP with shared weights to all nodes after the NLSF. We present the empirical study of diag-NLSFs App. F.7.
C.2 Leading NLSFs
In Sec. 3.3, we introduce the NLSFFs with the orthogonal complement. Specifically, the (J + 1) 1) filter the Index NLSFs is given by P,+1 = I Σ Pj. and the (K + 1)-th filter in Vale NLSFF defined as 9 (A) =I I 9
(). . To explore the effects of the orthogonal complement, we focus on the leading NLSFF in both the Index NLSFs and Vale NLSFs, considering only the first and K filters without including their orthogonal complements. In this case, the analysis and synthesis in the spectral index case and in the filter bank case are respectively given by
ind, lead
A) (IP,X 1=1
E JR and
(13)
val, lead A)
(19((4)X sig
K
E E Kd
19

---

and
P,X
Sind, lead (R;
R and
a sig
te
j=l
(14)
95 (x
Sval, lead (R
R.
|1, (A)X]
te
sig
j=1
where Pj and gj ()) defined as in Sec. 3.2. The lead-NLSFs then defined by ind. (A, X) = (ind, lead)
(Wina (ind) (AA (X)))
P,X P, Sig
Wind (IP )
(15)
te
i=1
val, ind (A, = vaaa ind) A
(V (A(aa)) (X)))
9j
A
Vall (119: (l)x(
]
K
(16)
sig
11g,
te
sig
j=1
where Wnd RJ Jdx Vaal : RRdd R Kd and d is the output dimension. To adjust the feature output dimension, we apply an MLP with shared weights to all nodes after the NLSF.
Similar to App. C.I, when considering d = d such that the multiplication and division in synthesis are operated diagonally, we have the Bad-diag-NLSSS defined by
ind, diag A X) = (ind, lead, diag) (AA (ind)
(X)))
P,X
(17)
Σ
(IP lass
==1
|P
+
val, lead, diag A
X)
S
/val, lead, diug) (Vr (TF(A (val)) (X)))
K
9j (x(A
(18)
V (19(
[=1];
19, Uiig
+
where V : Jd + Jdd Oind, lead, diag and R Rkd + RKd in O lead, ding. We present the empirical study of lead-NLSSss and lead-diag-NISSSs in App. F.7.
D Theoretical Analysis
We note that the numbering of the statements corresponds to the numbering used in the paper, and we have also included several separately numbered propositions and lemmas that are used supporting the proofs presented. We restate the claim of each statement for convenience.
D.1 Equivariance of NLSFs
We start with two simple lemmas that characterize the graph functional shifts. The lemmas directly follow the fact that two normal operators commute iff the projections upon their eigenspaces commute.
Projection to Eigenspaces Case.
Note that
J+1 [[
RV
where II denotes direct products of linear spaces and the (J+1)-th filter is the orthogonal complement, given by P/41 = I Σ P,, Denote by @ the direct sum of operators.
20

---

Lemma D.1. U is in Uy iff it has the form =( J+1 P,R.
U,) where Uj is unitary operator in j=1
Proof. Let E Ug Since commute with P, for j 1,..., and with also commutes with PJ41= = Σ Py. Therefore, we can write
J+1 P P PPUPP,
J+1
J+1
U=
Σ P
j=1
Now, when restricting P, UP, to an operator in Py P,R,, is unitary. Indeed, for every v Py Py PjR* and u Pyu P, R since U unitary and P, is self-adjoint and satisfies P = Pj. we have
P u) (v. P,u).
and P, is the inverse of P. UP, in P,R since for every P,R
P =v
and similarly Pj PUU
Here, invertible normal operator commutes with orthogonal projection if and only if its inverse does.
The other direction is trivial.
Projection to Bands Case.
Note that
K+1 II ==1
R
g3
(A)R
where the (K + 1)-th filter is the orthogonal complement, given by gk+1 -I -ド (A)
Lemma D.2. U is in U2 iff it has the form U
(+) K+1
U₁). where Uj is unitary operator in /
Oj ()(A)) AA)
The proof is analogous to the proof of Lemma D.I.
D.1.1 Proof of Propositions
Proposition 1. Index NLSFs in Eq. (4) are equivariant to the graph functional shifts Uz and Value NLSFs in Eq. (5) are equivariant to the relaxed graph functional shifts U
Proof. We start with Index-NLSFs. Consider the Index NLSF defined as in Eq. (4)
J+1
e A X)
P&X
Vind
(IP;X
J+1
|P 1
i=1
j=1
We need show that for any unitary operator E Ul.
mna (A, UX) = UOnnd X.)
Consider U Uı and apply it to the graph signal X. The Index NLSF with the transformed input is given by
J+1
O A, UX) = JP R
PJUX
Wind (IP,UX sig i=
J+1
+e
sig
j=1
Since U E UA it commutes with P, for all j. i.e., we can rewrite the norm and the projections as
UP, = -P,U. Using this commutation property,
JP, PPUl |UP,X sig
addition, since U is a unitary matrix, it preserves the norm. Therefore, we have JUP sig |
21

---

Substituting these expressions back into the definition of the Index NLSFss gives
++1
ina A, UX)=
3
ind (IP:X)
J+1
P
sig
1==1
Notice that U appears linearly in the numerator of the fraction. Hence, we can factor out by
ind A UX)
U
P,X
Vind
(IP:X
J+1
PP sig
The expression inside the summation is exactly the original Index NLSFs applied to X, so ind (A, UX) ind A X).
Therefore, we have shown that applying the unitary operator U to the graph signal X results in the Index NLSFs being transformed by the same unitary operator U, proving the equivariance property.
The proof for value-NISF follows the same steps.
D.2 Expressivity and Universal Approximation
In this section, we focus on value parameterized NLSFs. The analysis for index-NLSF equivalent.
D.2.1 Proof of Lemma 1 Linear Node-level NLSF Exhaust the Linear Operators that Commute with Functional Shifts
We next show that node-level linear NLSFF exhaust the space of linear operators that commute with graph functional shifts (on the fixed graph).
Lemma 1. A linear operator Nx + N commute with UA (resp. 42)) iff it is NLSF based on linear function V in Eq. (4) (resp. Eq. (5)).
Proof. For simplicity, we restrict the analysis to the case of ID signals (d = 1). The extension to general dimension d natural.
By Lemma D.2, the unitary operators U in 4% are exhausted by the operators of the form
K+1
+
U
j=1
where U, is any unitary operator in gj MTR. Hence, since the unitary representation T . of the group of unitary operators in I." (for any m E () is irreducible, by Schur's 's lemma [85] any
linear operator that commutes with all operators of 21% must be a scalar times the identity when
projected to g A )RR, Namely, has the form
K+1 +
B
(b,
where I, the identity operator g, N This means that linear node-level NLSFs exhaust the space of linear operators that commute with 4
The case of hard graph functional shifts is treated similarly.
D.2.2 Node-Level Universal Approximation
The above analysis motivates the following construction of a metric on g Given the filter bank (9, ( K+1 on graph with d-dimensional signals, we define the standard Euclidean metric distp in the spectral domain (K We pull back the Euclidean metric to the spatial domain to define graph-signal metric. Namely, for two signals X and X', their distance is defined to be
dist A X, x') == distg (A(A, X), A(A', X')).
22

---

This defines a pseudometric on the space of graph-signals. To obtain metric, we consider each equivalence class of signals with zero distance as a single point. Namely, we define the space NA = RR /dist to be the space of signals with ID features modulo dist. In Na, the pseudometric /dist A an isometry of metric spaces".
dist. becomes a metric, and A
Now, since MLPs can approximate any continuous function R R(K+l)xd + R (by the universal approximation theorem). and by the fact that / / is an isometry, node-level NLSFs based on MLPs in the spectral domain can approximate any continuous function from signals with features to signal with d' features (Na)" (Wa)
D.2.3 Graph-Level Universal approximation
The above analysis also motivates the construction of graph-signal metric for graph-level tasks. For graphs with d-channel signals, we define the standard Euclidean metric distp in the spectral domain {(K+)) We pull back the Euclidean metric to the spatial domain to define a graph-signal metric. Namely, for two graphs with Laplacians and signals (A, X) and (A', X'), their distance is defined to be
dist ((A, X), (A') = distp (A(A, X),
This defines a pseudometric on the space of graph-signals. classes of graph-signale with zero distance single point. Namely, define the space to be the space of graph-signal modulo dist. In G. the function dist becomes a metric, and A an isometry.
obtain a metric, we consider equivalence
By the isometry property, inherits any approximation property from ((--))xd For example, since MLPs can approximate any continuous function ( - Rdd the space of NLSFs based MLPs has universality property: any continuous function + Rdd with respect to dist can be approximated by NLSF based on MLP.
D.2.4 Graph-Level Expressivity of Pooling-NLSFF
We now show that pooling-NL.. -LSS are more expressive than graph-level NLSF the norm in Eq. (4) and Eq. (5) is Lp with + 2.
First, we show that there are graph-signals that graph-level-NLSF: cannot separate and Pooling- NLSFs can. Consider index NLSF with norm L1 normalize by 1/N. Namely, for R.
||al|
lanl-
N n=1
The general case is similar.
For the two graphs, take the graph Laplacian
(1 (
+)
with eigenvalues 0, 1, and corresponding eigenvectors (1, 1) and (1, (1). Take the graph Laplacian
( - 0 -
-1 0
with cigenvalues 0, 1, The first two eigenvectors are (1, 1, 1) and (1, -1), respectively.
Consider an Index-NLSF based on two eigenprojcctions P1, P2. As the signal of the first graph take
1), + (1, -)), and for the second graph take 11,1,1) + 2 (1,0, -1). Both graph-signals have the
same spectral coefficients (1, 1), so graph-level NLSF cannot separate them. Suppose that the NLSF
P,X
P&X
X) [ PI + e) |PPXXXX
+e + (1 + e) |P
+e
PAA/dista /dist operates on an equivalence class [X] of signals by applying Aa on an arbitrary element Y of X]. The output of As Y does not depend the specific representative Y. but only on [X].
23

---

The outcome of the corresponding Pooling NLSF on the two graphs is
4
1 [[11 1,1 1)ll + II 3/2, - 3/2)
3
Hence, Pooling- NLSFs separate these inputs, while graph-level-NLSSss do not.
Next, we show that Pooling-NLSFs are at least as expressive as graph-level NLSFs. In particular, any graph-level NLSF can be expressed as a pooling NLSF.
Let V be a graph-level NLSF. Define the node-level NLSF that chooses one spectral index with a nonzero value (e.g., the band with the largest coefficient) and projects upon it the value (A, XXII,, aig + e)/ [IP; llaig Hence, before pooling, the NLSF gives
P,X
( VA X
I sig
+ +c)
IP +
where j depends on the spectral coefficients (e.g.. it is the index of the largest spectral coefficient). Hence, after pooling, the Pooling NLSF returns Vi ( X), which coincides with the output of the graph-level NLSF.
Now, let us show that for p 2, they have the same expressivity. For any NLSF,
J
P,X
@ x)=
=
Σ
Tp
PP
sig
IP
sig
sig
X
2 sig
Σ
v
[ Usiz
j=1
|P
sig
+
This is a generic fully spectral NLSF.
D.2.5 Discussion on Graph-Level Expressivity of NLSFs
We offer additional discussion on the expressivity of graph-level NLSFs. Note that graph-level NLSFs are bounded by the expressive power of MPNNs with random positional encodings. For example, in [81], the authors showed that random features improve GNN expressivity, distinguishing certain structures that deterministic GNNs cannot. The Lanezos algorithm for computing the leading J eigenvectors can be viewed as message-passing algorithm with randomly initialized J-channel signal.
The example in App. D.2.4 can be written as a standard linear graph spectral filter, followed by the pooling (readout) function. This shows that graph-level NLSFs (without synthesis and pooling) are not more expressive than standard spectral GNNs with pooling. In the other direction, there are no graph-signals that can be separated by a graph-level NLSF but not by a spectral GNN. Given two graph-signals that an NLSF can separate, we can build a specific standard spectral GNN that gives the same output as the NLSF specifically for the two given graph- However, several considerations should be noted:
1. the feature dimension of this GNN would is large as the combined number of eigenvalues of the two graphs times the number of features,
2. this GNN is designed fit these two specific graphs, and will not work for other graphs, and,
3. if implemented via polynomial filters, the polynomial order would have to be the combined number of eigenvalues of the two graphs, which makes it very unstable.
Let us explain the architecture next. Given the two graphs (1) with Nj vertices and (G2, f2) with N₂ vertices, with node features of dimension D, define band-pas pass filters that separate the combined set of eigenvalues of the two given graphs Concatenate these filters to build a single multi-channel filter. Namely, this filter maps the signal to the sequence of band-pas, filtered signal - each band at different channel, for a total of D(N, + N₂) channels. the band-pass filters are based on polynomials, each polynomial would be chosen to be zero on all eigenvalues except for one. Apply Zorm pooling on each channel to obtain single feature of dimension D(N, + N₂). This gives the sequence of norms of the signal at the bands, where, for the two given graphs, the two
24

---

pooled signals of the two graphs are supported on disjoint sets of indices. Hence, the linear spectral filter contains the frequency information of the NLSF. Then, one can apply the MLP the NLSF to the channels corresponding to the first graph, and to the channels corresponding to the second graph. This means that the linear spectral GNN gives the exact same outputs on (G1, f1) and (G2, f2) as the NLSF.
Regarding pooling-NLSE, we do not offer an answer the question whether standard spectral GNNs are more powerful (assuming an unlimited budget) than pooling-NLSTS, or vice-versa. More practically meaningful questions would be:
1. Compare the expressivity of standard spectral GNNs NLSFs for given budget of parameters.
2. How many graph-signal can single spectral GNN separate, single NLSF, of the same budget.
We leave these questions as open problems for future research. We note that, in practice, NLSFs with the same budget standard spectral GNNs perform better.
D.3 Stable Invertibility of Synthesis
We present the analysis for diagonal synthesis defined from App. C.I. In the fixed graph setting, given any ID signal X such that gf (A)X * 0 for every j E [K + 1], we show that the synthesis operator Syal. diag is stably invertible.
Since we consider ID signal X, the diagonal synthesis in filter bank case in Eq. (10) can be written as
Sval, ding A
Hr',
where
X
9K+1 X
RN+((11) & H
( (A)
a X
[g
2
9i(AXX lgy (A)x
E ER, and r' [11,22 TK+1l E R+11
Since
(ạ), (A)X) (9f2 A X) = all f1,22 E KK + 1], the matrix H H a diagonal matrix (A)X
with entries
Therefore, the singular values of H
(A X
( 1/ +e
the right singular vectors are the standard basis elements ey in K+1 and the left singular vectors are
9, A X
19 2|
for [K 1]. Hence, have
Sval. ding A.X
max Jj
and
(
diag S
min, Jj
Suppose that and 0. In this case, Sval.ding ding is isometry from the spectral domain SA.
subspace of the signal space N Analysis is the adjoint of synthesis. This analysis can be extended the index parametrization case for diagonal synthesis, and higher dimensional signals.
D.4 Uniform Approximation of Graphs with J Eigenvectors
In this section, we develop the setting under which the low-rank approximation of GSOs with their leading cigenvectors can be interpreted as uniform approximation (Sec. 4.4).
25

---

D.4.1
Cut Norm
The cut norn of M RNN is defined to be
|M == N2
sup STTCIM
ΣΣ mi.j
(19)
RES
The distance between two matrices in cut norm is defined to be |
M' Il
The cut norm has the following interpretation, which has precise formulation in terms of the weak regularity lemma [32, 65]. Any pair of (deterministic) graphs are close to each other in cut norm if and only they can be described as pseudo-random graphs sampled from the same stochastic block model. Hence, the cut norm is meaningful notion of graph similarity for practical graph machine learning, where graphs are noisy and can represent the same underlying phenomenon even if they have different sizes and topologies. In addition, the distance between non-isomorphic graphons is always positive in cut norm [66]. In this context, the work in [59] showed that GNNs with normalized sum aggregation cannot separate graphs that have zero distance in the cut norm. This means that the cut norm is sufficiently discriminative for practical machine learning on graphs.
D.4.2 The Constructive Weak Regularity Lemma in Hilbert Spaces
The following lemma, called the constructive weak regularity lemma in Hilbert spaces, was proven in [29]. It is an extension of the classical respective result from [65].
We define the Frobenius norm normalized by 1/N
|M
1 N
Σ 1
mm
Lemma D.3. [[29]] Let [Kj be a sequence of nonempty subsets of real Hilbert space and let 6 2 O. Let J 0, let R 2 1 such that J/R E N, and let g E H. Let m be randomly uniformly sampled from [J]. Then, in probability 1 It (with respect to the choice of m), any vector of the form
m
9
Σ rifa such that
Y (Ta) R and
(E) X... Km
...
that gives close-to-best Hilbert space approximation of g in the sense that
m
11g - 9"1l S (1+
inf 7.
11g
Enfilll
(20)
==1
where the infimum is over y R and f E K1 ... Kins also satisfies
R v
Vw Km+1,
kw.g- - g" i1 s ||0|
y + +
D.4.3 Proof of Theorem
Theorem 1. Let M be symmetric matrix with entries bounded by |ma S and let J E N. Suppose m sampled uniformly from [J], and let R s. J/R E N. Consider .i..... &m as the leading eigenvectors of M, with eigenvalues -1.....H4 Hmm ordered by their magnitudes |pa] 2 ...
|mm] Define C -i Pa (u oT. Then, with probability
(w.rt. the choice of m))
3a R 2
<
J
Proof. Let us use Lemma D.3, with matrices of the form VvT where v E R is a column vector. Denote by ym the space of linear combinations of elements of K., which is the space of symmetric matrices of rank bounded by m. For the Hilbert space norm, we take the Frobenius norm. In the setting of the lemma, we take y = M. and 9" ym. and 8 0. By the lemma, with probability 1 1/ any Frobenius minimizer C.
NNN and K, K. the set of symmetric rank one
26

---

namely, that satisfies |M - Cflg = mincrey..
M C. also satisfies
V
R
M - C) 2 Y
M F V J S Y F V
for every Y E vm. Hence, for every choice of subset S, 7 C [M]. we have
Σ Σ
(ma cis)
iES JET
maj c2.) ΣΣ
(m,j cij)
2
SET JES
1
Σ
(mas -c.))
mij -..) ΣΣ
(mas) cas))
2
iESUT JESUT
iES JES
1ET JET
(1sur L.T M M- c) + ( M
(
F
3a
R
2 V
J
where for set S C [N], denote by I E T the column vector with at coordinates in S and otherwise.
Hence, we also have
3a
R J
|M- Clln S
Lastly, note that by the best rank-m approximation theorem (Eckart-Young. -ousg- Theorem [92, Thm. 5.9]), any Frobenius minimizer the projection upon the m leading eigenvectors of M (or some choice of these eigenvectors in case of multiplicity higher than 1).
Now, one can the adjacency matrix A M in Thm. 1. When working with sparse matrices of E < N2 edges, to achieve a meaningful scaling of cut distance, we re-normalize the cut norm and define
N F
M
(E)
|M
With this norm, Thm. 1 gives
No
R
MM (
(B)
J
(21)
2E
While this bound is not uniformly small in N, it is still independent of M. contrast, the error bounds for spectral and Frobenius norms do depend the specific properties of M.
Now, want to apply Thm. that when the GSO is a Laplacian, we take as the leading eigenvectors the ones correspoding to the smallest eigenvalues, not the largest ones. To make the theorem applicable, we need to reorder the eigenvectors of A. This can be achieved by applying decreasing function h to A, such as ((A) -1 1 The role of is to amplify the eigenspaces of A which most of the energy of signals interest (the ones that often appear in the dataset) is concentrated. Under the assumption that h(A) A) has entries bounded by some not-too-high > O, one can now justify approximating GSOs by low-rank approximations based on the smallest eigenvectors.
other GSOs A, need to make some assumptions. Note
27

---

D.5 NLSFss on Random Geometric Graphs
In this section we consider the [2[N] norm normalized by 1/N1/2 namely,
l|vll2
1
pupl 2
NN
We follow a similar analysis to [74), mostly skipping the rigorous Monte-Carke error rate proofs, as these are standard.
Let S be compact metric space with metric d and with a Borel probability measure, that we formally call the standard measure dr. Let r > O, and denote by B, (z) the ball of radius r about & E S. Let V (z) be the volume of (x) with respect the standard measure (note that V(x) need not be constant). We consider an underlying Laplacian on the space S defined on signals f : + R by
B. ()(x) C C (f(x) -()))dy
(22)
where assume C = 1 in the analysis below without loss of generality. In case the integral in Eq. (22) is normalized by (x)) this Laplacian was called p-Laplacian in [15], which we denote by L,. Such Laplacian is related to Korevaar-Schoen type energies [52], in which the limit case of the radius r going to O is considered. It was shown in [15] that the p-Laplacian is self-adjoint with spectrum supported inside some interval [0, Q). for some Q >> O. where for some 0 R < Q, the part of the spectrum in [0, Rt U (R, Q] is discrete (consisting of isolated eigenvalues with finite multiplicities). The intuition behind this result is that, for the p-Laplacian Ly, we have
1 f, = 72 V(I)r2 (.)))
1
/ f(y)dy.
(23)
The first term in the
of Eq. (23) is a scaled version of the identity operator, and the second term is compact self-adjoint integral operator, and hence has discrete spectrum with accumulation point at 0, or no accumulation point. After showing that the sum of these two operators is seff-adjoint, end up with only one accumulation point of the spectrum of L,.
We show below that L is self-adjoint under the assumption that (ar) bounded from above. this case it must also be positive semi-definite (the proof is equivalent to the positivity of the combinatorial graph Laplacian). Consider the decomposition
Cf(x) = CV())
f(yddy.
(24)
B,(x))
The second term of Eq. (24) is a compact integral operator, and hence only has an accumulation point at O, or has no accumulation point. The first term a multiplication operator by the real-valued function Vzz), so it is self-adjoint and its spectrum is the closure of (V()) æ E S}. We suppose that ((c) bounded from below by some R' > 0 and also bounded from above. This shows that bounded and self-adjoint (as a sum of two bounded self-adjoint operators). Under these assumptions, is reasonable to further assume that the spectrum of L in the interval [0, R), for some 0, is discrete, with accumulation point at R. This happens, for example, if V (z) V is constant.
We now assume that the signal consists only of frequencies in [0, Rt.. This means that we can project L upon this part of the spectrum, giving a self-adjoint operator with discrete spectrum, and accumulation point of the eigenvalues only at R.
Let w S + IR be a measurable weight function with Is w(x)dz = 1. Suppose that w(x) is continuous and varies slowly over S. Namely, we assume that w(x) xe w(y) for every E (z).. To generate a random geomertic graph of N nodes, we sample N points x from the weighted probability measure w(r)drr We connect node xy to Ty by an edge if and only if d(z,; xyy) < to obtain the adjacency matrix A. Let L be the combinatorial Laplacian with respect to A, and N the normalized symmetrie Laplacian. The number of samples inside the ball of radius r around x is approximately (x)) Hence, the degree of the node v,, is approximately (x.,,,
J. independently
We consider the leading J eigenvectors the ones corresponding to the smallest eigenvalues of L in the interval [0. R), where < N. We order the eigenvalues in increasing order. Let PW(J) be the space spanned by the J leading eigenvectors of L, called the Paley- Wiener space of C. Let p. be the
28

---

projection upon the Paley-Wiener Wiener space of L. Let RN (2(S) - L be the sampling operator, defined by NR f), f(z)).
Let f : + IR be a bounded signal over the metric space and suppose that f PW(J). Denote f (f(a))) R. By Monte Carlo theory, we have
(Lf), ~ w(x))N S (..Co)) (f(x)
So, in case the sampling is uniform. i.e., w(x) = 1, we have
L NL,
pointwise. To make this precise, let us recall Hoeffding's ss Inequality [43].
Theorem D.1 (Hoeffdiing's s Inequality [43]). Let ,,,,,,, Yn be independent random variables such that a S Yu S 6 almost surely. Then, for every k >> 0,
N
21:2 N
Σ 1=1
(Y, - EYY.)) 2 2 S 2exp
(- a)
N
Using Hoeffding's 's Inequality, one can now show that there is an event of probability more than 1 which for every [N.. the error between (N ..R.N. f), and Lf satisfies
RNCf |
1 N
log(1/p) + log(N) + log(2)
JV
N
The fact that different graphs of different sizes N approximate & with different scaling factors means that L is not value transferable. Let us show that L is index transferable.
We now evoke the transferability theorem a slight reformulation Section of Theorem 4 in [60]. Theorem D.2. Let & be a compact operator on (S) and L an operator on CN Let J E N and let Ry be the sampling operator defined above. Let (P((J the space spanned by the J leading eigenvectors of L, and let f PP(JJ. Let TR - IR. be Lipschitz with Lipschitz constant D. Then,
RNg(()) (L) = DVJ
RNLf
N LR.
For every leading eigenvalue XÚ of L let Vi be the leading eigenvalue of L closest to X, where, if there are repeated eigenvalues, ij is chosen arbitrarily from the eigenvalues that best approximate Aç. Let
min 3).
where
min min { ]E[j]
min [) Vel min [
[Aj Aml min 178 Am JpmE))
]=mE[J]
and
B = min has
7ml
iE(J].nE[N]
and suppose that > 0. For each j E [N] there exists a Lipschitz continuous function 9j with Lipschitz constant 8-1 such that 9, (2,) = g (7,, = and is zero on all other leading cigenvalues of L and all other cigenvalues of L. Hence,
リン ( of Rx) -ffff.
where pf is the projection upon the space spanned by the j-th eigenvector of and pl is the projection upon the space spanned by the iy-th eigenvector of L.
Now, by the transferability theorem,
1 Lf O(VJ/N). N By induction over with base must have i, for every j E [J].
|NNDS p DVJ RN
Now, note that by standard Monte Carlo theory (evoking Hoeffding's 's inequality again and intersecting events), we have
RNNf /12
s = (()-1/2
29

---

Table 5: Node classification datasets statistics.
Dataset
# Nodes
# Classes
# Edges
# Features
Cora
2708
5278
1433
Citeseer
3327
4552
3703
Pubmed
19717
44324
500
Chamelcon
2277
31371
2325
Squirrel
5201
198353
2089
Actor
7600
26659
932
in high probability. Hence, by the fact that
|| f12 |1lf 1 (1) RI fll2 lbf f112) RI fl12 + (11f)
and [RNnfffl f12 + oeffll2 is bounded from below by the constant ||gf fl12- we have
|| RNDS /1l2 ||rf fll 013-113).
This shows that
||aff112 = |||)
which shows index transferability. Namely, for two graphs of N and N' nodes sampled from S, with corresponding Laplacians and , by the triangle inequality,
|| ||
Next, we show value transferability for N. Here,
Nf(xz) V(x,) V(xx) (f(z))
Hence, if V(x) V is constant, we have N R L up to a constant that does not depend on N. In this case, by similar analysis the above, N value transferable. We note that N is also index transferable, but value transferability is guaranteed in a more general case, where we need not assume a separable spectrum.
E Additional Details on Experimental Study
We describe the experimental setups and additional details of our experiments in Sec. 5. The experiments are performed NVIDIA DGX A100.
E.1 Semi-Supervised Node Classification
We provide detailed overview of the experimental settings for semi-supervised node classification tasks, along with the validated hyperparameters used in our benchmarks.
Datasets. We consider six datasets in node classification tasks, including Cora, Citeseer, Pubmed, Chamelcon, Squirrel, and Actor The detailed statistics of the node classification benchmarks are summarized in Tab. 5. For datasets splitting follow the standard splits from [100], using 20 nodes per class for training. 500 nodes for validation, and 1000 nodes for testing. For heterophilic graphs (Chameleon, Squirrel, and Actor), we adopt the sparse splitting method from [16, 41], allocating 2.5% of samples for training, 2.5% for validation, and 95% for testing. The classification quality is assessed by computing the average classification accuracy across 10 random splits, along with a 95% confidence interval.
citation graphs (Cora, Citeseer, and Pubmed),
Baselines. For GCN, GAT, SAGE, ChebNet, ARMA, and APPNP, we use the implementations from the PyTorch Geometric library [28]. For other baselines, we use the implementations released by the respective authors.
30

---

Table 6: Graph classification datasets statistics.
Dataset
# Graphs (2)
# Classes (C)
[N:
N
[N log
# Features (d)
min
max
MUTAG
188
10
28
17.93
7
PTC
344
2
64
14.29
18
ENZYMES
600
2
126
32.63
18
PROTEINS
1113
4
620
39.06
NCII
4110
3
111
29.87
37
IMDB-B
1000
12
136
19.77
None
IMDB-M
1500
7
89
13.00
None
COLLAB
5000
32
492
74.50
None
Hyperparameters Settings. The hidden dimension set to be either 64 128 for all mod- els and datasets. We implement our proposed Node-level NLSFs using PyTorch and opti- mize the model with the Adam optimizer [48]. To determine the optimal dropout probabil- ity. we search within the range (.. in increments of 0.1. The learning rate is examined within the set {le- 1 5e -2, le
5e 5e
le $) We explore weight decay values within the set 1e-0, .0.03. Furthermore, the number of layers is 55 1,,-5,
{1e-2.5e -5-3, le 5e 1,e 5e-5, 1e-5, varied from decay rate in the Value NLSFs is determined using dyadic sampling within the set { 3 21 3: 3. the sampling resolution S within [1, le and the number of the bands in Value NLSFs K S S. For
The number of leading eigenvectors in Index NL.SFs set within [1, le The
hyperparameter optimization, we conduct a grid search using Optuna [1] for each dataset. An early stopping criterion is employed during training, stopping the process if the validation loss does not decrease for 200 consecutive epochs.
E.2
Graph Classification
We provide a comprehensive description of the experimental settings for graph classification tasks and the validated hyperparameters used in benchmarks. The results reported in the main paper.
Problem Setup. Consider set of Z graphs Gz (G1, G2...,, G2), where in each graph G3 E,, X,,X),, we have N; nodes for each graph G₁, & represents the edge set, A, E R N;N, denotes the edge weights, and X, E R.N.dd represents the node feature matrix with d-dimensional node attributes. Let Y c be the label matrix with C classes such that yr
if the graph G; belongs to the class j. and Vi.j = 0 otherwise. Given a set of Z' graphs Gz C CG where
Z. with the label information Y E IR Z''xxx our goal is to classify the set of unseen graph labels of Gz Gz..
Datasets. We consider eight datasets [72] for graph classification tasks, including five bioinformatics: MUTAG, PTC, NCI1, ENZYMES, and PROTEINS, and three social network datasets: IMDB- B, IMDB-M, and COLLAB. The detailed statistics of the graph classification benchmarks are summarized in Tab. 6. We use the random split from [94, 101, 67, 104], using 80% for training, 10% for validation, and 10% for testing. This process is repeated 10 times, and we report the average performance and standard deviation.
Baselines. For GCN, GAT, SAGE, ChebNet, ARMA, APPNP, and DifiPPol,, we use the implemen- tations from the PyTorch Geometric library [28]. For other baselines, use the implementations released by the respective authors.
Hyperparameters Settings. The dimension of node representations is set to 128 for all methods and datasets. We implement the proposed Pooling-NLSSE and Graph-level NLSFs using Py and optimize the model with the Adam optimizer [48]. A readout function is applied to aggregate the node representations for each graph, utilizing mean, add, max, or RMS poolings. The learning rate and weight decay are searched within (1e-1, 12 1e-3, le-1, 1) the pooling ratio within 10.1, 0.9) with step 0, the number layers within [1, 10] with step 1, the number of leading eigenvectors J in Index NLSFs within [1, 1e2], the decay rate in the Value NLSFs using dyadic sampling within
31

---

Table 7: Semi-supervised node classification aceuracy with random split, following the experimental protocol established by [41]. Results marked with are taken from [41].
Cora
Citeseer
Pubmed
Chameleon
Squirel
Actor
GCN
79. 19"144"
69,71
78.81
38.15
31.18110"
22.74a23*
GAT
80.03
68.16209
77.26205
34.16=12
27.40=14
24.35
SAGB
72.68
63.87
77.66 77.68108
31.77
22.67=1a
25.61
ChebNet
78.08
67.87+15"
73.96+17"
37.15=15
26.55+a.5*
26.58+19"
ChehNetll
82,42-06"
69.89*12"
79.53=10"
43.42+15
33.96=12"
30.18108*
CayleyNel
80.25
66.46129
75.42134
34.52.111
24.08
27.42:53
APPNP
82.39
69.79#09*
79.97+16"
32.73=2.5
24.50+0.
29.74
GPRGNN
=2.37=08*
69,22213"
79.28211"
33.03=1.9
24.36215
28.58210"
ARMA
19.14=11"
69.35#14
78.31
37.42=1.7
24.15=09"
27.02+23"
att Neve NLSFFs
82.94
72.13:11
79.62a12
46.75-21x
35,17=1A
29.96;n8
L 1.1.1 2). the sampling resolution S within [1, 1e and the number of the bands in Value 21 31 NLSFs within K < S. The graph-level representation is then fed into an MLP with a (log)softmax classifier, using a cross-entropy loss function for predictions over the labels. Specifically, the MLP consists of three fully connected layers with 256, 128, and 64 neurons, respectively, followed by (log)softmaxx classifier. We conduct a grid search on the hyperparameters for each dataset using Optuna [1]. An early stopping criterion is employed during training, stopping the process if the validation loss does not decrease for 100 consecutive epochs.
F
Additional Experimental Results
Here, we present additional experiments node and graph classification benchmarks, ablation studies, runtime analysis, and uniform sub-bee bub-bands.
F1 Semi-Superviser Node Classification Following [41] Protocol
We present additional experimental results for semi-supervised node classification using random splits, adhering the protocol established by [41]. The results, summarized in Tab. 7, demonstrate the classification accuracy across six benchmark datasets: Cora, Citeseer, Pubmed, Chameleon, Squirrel, and Actor. Our att-Node-level NLSFs achieve the highest accuracy four out of the six datasets, outperforming other models significantly. On Pubmed, records a close second-highest accuracy, slightly behind APPNP. Our method achieves competitive second place in the Actor dataset. att-Node-level NLSFs demonstrate substantial improvements, particularly in challenging datasets like Chameleon and Squirrel. The comparison models, including GCN, GAT, SAGE, ChebNet, ChebNetll, CayleyNet, APPNP, GPRGNN, and ARMA, varied in their effectiveness, with ChebNetll and APPNP also showing strong results on several datasets. These findings highlight the efficacy of the att-Node-level NLSFs in semi-supervised node classification tasks.
F.2 Node Classification Filtered Chameleon and Squirrel Datasets in Dense Split Setting
Following [77], we conduct additional experiments on the original and filtered Chameleon and Squirrel datasets in the dense split setting. We the same random splits as in [77], dividing the datasets into 48% for training, 32% for validation, and 20% for testing. We compare the Node- level NLSFs using Laplacian attention with GCN [49]. SAGE [39], GAT [93], GT [88], H₂GCN
[103], CPGNN [102]. GPRGNN [16]. FSGNN [69], GloGNN [62], FAGCN [8], GBKGNN [23], JacobiCony [96]. and ResNet [40] with GNN models [77]. The study by [103] demonstrates the benefits of separating ego- and neighbor bemeddinembeddiing in the GNN aggregation step when dealing with heterophily. Therefore, [77] also adopts this approach for the GNN aggregation step in GAT and GT models, denoted as "sep." The baseline results used for comparison are taken from [77]. Tab. presents the full performance comparison on the original and filtered datasets. Note that Tab. 8 is the same as Tab. 2 but with more baseline methods. att-Node-level NLSFs achieve the highest accuracy on both the filtered Chameleon and Squirrel datasets. Additionally, att-Node-level NLSFs demonstrate strong performance the original Chamelcon dataset, achieving the highest
32

---

Table 8: Full Performance comparison of node classification original and filtered Chameleon and Squirrel datasets dense split setting. The baseline results used for comparison are taken from [77].
Chameleon
Squirrel
Original
Filtered
Original
Filtered
ResNet
49.52
36. 66.73
33.88
36,55+18
ResNa-SGG:
49. 49.93
41,01:45
34.36x12
38.36120
ResNettadj
71.07=22
38.67439
65.46+14
38.37+20
GCN
40.89:41
39.06215
39,47.15
SAGE
10.18
37.77
35.83+13
36,09+20
GAT
45.02=18
39.21
32.21
35.62+21
GAT-sep
20.24
39.26a35
35.72a20
35,46181
GT
44,93
38,87
31.61111
36,30+20
GTT-sep
50.33226
40.31
36.08216
36,66116
H,GCN
46.27
26.75#36
29 19.45
35. 10+12
CPGNN
48.77
33,00
30.91
30,04130
GPRONN
47, 47,26
39,93+33
33.39
38, 38.95#20
FSGNN
07.85
40.61
68.93+17
35,92+13
GloGNN
70.04
25,90 35.90436
61.21#20
35,11
FAGCN
64,23=:0
41,90+17
47.63=19
41,08
GBKGNN
51.36111
39.61
37.06112
35.51
JacobiCony
68.33
39,00s42
46.17:43
29.71
att-Node-level NLSEs
79.42
42,061133
67.81214
42,18
Table 9: An ablation study investigated the effect of Node-level NLSFs node classification,
comparing the use of Index NLSFs and Value NLSFs. The symbol (1) denotes an improvement using Laplacian attention.
Cora
Citesoer
Pubmed
Chameloon
Squirrel
82.46114
71.31
80.97 ns
44.37
34.12114
29.88
ewr(N,
81.73+14
70.25408
79.88112
44.52e13
34.26415
29.97=11
e,alL,))
80.25=15
70.43
80.06-16
45.52=11
35,23+08
32.69=19
(..
81.98.007
71.16a13
80.33_17
47.91
35.78a08
33.53.11
attiO ). (.O.
82.46s12
71-48s0s
(t)
80.97
46.71=22
(f)
36.92s11
(t)
32.69=19
attiO...NN 1. )
81,98a07
72.45=14
80.33a13
47.91=14
36.87
33.53=14
att(OuuaN 1. 1. [)
82.65e12
(t)
71.26
(T)
80.56
(1)
45.98s23
(1)
37.03+19
33.09
(1)
att(O L. (N.
84.75
73.62+11
(1)
81.93a10
(1)
49.68
38.25
(1)
34.72e09
(1)
accuracy and the aecond-highest accuracy the original Squirrel dataset. att-Node-level NLSFs show less sensitivity to node duplicates and exhibit stronger generalization ability, further validating the reliability of the Chameleon and Squirrel datasets in the dense split setting.
F.3 Ablation Study on att-Node-level NLSFs, att-Graph-NLSF. and att-Pooling-NLSSH
In Sec. 3.5, we note that using the graph Laplacian L in Index NLSFs and the normalized graph Laplacian N in Value NLSFF is transferable. Since real-world graphs often fall between these two boundary cases, we present the Laplacian attention NLSFs that operate between them at both the node-level and graph-level. Indeed, as demonstrated in Sec. 5, the proposed att-Node-leve NLSFs, att-Graph-level NLSFs, and att-Pooling-NLSFF outperform existing spectral GNNs.
We conduct an ablation study to evaluate the contribution and effectiveness of different components within the att-Node-level NLSFs, See---rrravae--L-SS--- and att- Pooling-NLSS on node and graph classification tasks. Specifically, the graph Laplacian L and the normalized graph Laplacian N to understand their individual and Laplacian attention impact on these tasks.
compare the Index NLSFs and Value NLSFs using both
The ablation study of aee- NLSPs for node classification is summarized in Tab. 9. We investigate the performance on six node classification benchmarks as in Sec. 5, including Cora, Citeseer, Pubmed, Chameleon, Squirrel, and Actor. Tab. 9 shows that using the graph Laplacian L in Index NLSFF (denoted as Oina (L,-)) and the normalized graph Laplacian N in Value NI (denoted as @ (N.-) )) has superior node classification accuracy compared using the normalized graph Laplacian N in Index NLSFs (denoted (N, :) and the graph Laplacian L in Value
33

---

Table 10: An ablation study investigated the effect of Graph-NL on graph classification, comparing the use of Index NLSFs and Value NLSFs. The symbol (f) denotes an improvement using Laplacian attention.
MUTNO
PTC
ENZYMES
PROTEINS
NCII
IMDB-B
IMDB-M
COLLAB
Oer(I..: )
12.14
65.73424
62.31
78.22
80.51413
63.27
50:29
70.06a13
Owi(N..)
83 27,07
66.02221
90 1Rses
8031214
78 40.40ss
58
52 2:33am
71 88
(u(T..))
83.40a
65
66.42:11
83336
17
72 22.71
19
Pui(N.) -)
81.19103
06.20113
63.32:12
78.20.83
78.08412
74.26118
$2.49 uX7
79.06.122
atr(ChelTe..)) (1.
83 40tna
(t)
66.42111
K3.3211
20.51
72.71
1411 (1)
stx stz/ (N.
57.15115
(1)
65
65.97A31
(19
$1,79112
(1)
79
19.83:36
(1)
74.36.115
52.49.00
79. 79,06.12
stt str/ku(NN (..).
06.02.11
83,36114
78,00136
72.71.t4
52.3 52.33
76,22 20.22.
(1)
ati(hall,,) Pha
84.13
68.17433
(1)
65 65.94415
(1)
$2.69ha12
(1)
90.51
74,26-11
52.49
79.06-112
Table 11:
An ablation study investigated the effect of Pooling-NLSF's on graph classification, com- paring the use of Index NLSFs and Value NLSFs. The symbol (1) denotes an improvement using Laplacian attention.
MUTAG
PTC
ENZYMES
PROTBINS
NCI1
IMDB-B
IMDIIMM
COLLAB
86 411
66.
09.88a1
84.27a11
90.33asx
60-40asa
51.01
11-28
19.19
42.37421
77.66222
62.08-14
72.03415
67.74.13
68.87414
84.18
79.43.24
7198820
78
09.13
68.89.34
84
50.52
76.48.14
54.12.13
81.31
7244
51.85115
72
L. P.
71.12ar
69.94-13
$4.89m0
(1)
80.9-11
76.78a19
55.25
82.19
NLSFF (denoted as (L, This is in line with our theoretical findings in App. D.5. Moreover, the att-Node-level NLSFs using the Laplacian attention att (Ond (L, +), (N,. yield the highest accuracies across all datasets, corroborating the findings in Sec. 3.5. We also note that without Laplacian attention, the Node-level NLSFs (Qma and O (N, alone still achieve more effective classification performance compared to existing baselines, shown in Tab. 1.
Tab. 10 demonstrates the ablation study of Graph-level NLSFs for graph classification tasks. We examine the eight graph datasets as in Sec. 5, including MUTAG, PTC, ENZYMES, PROTEINS, NCII, IMDB-B, IMDB-M, and COLLAB. Similar to the above, we investigate the Index and Value settings using graph Laplacian L and normalized graph Laplacian N, including Pina (L, Pina (N, +), (L, ,) and van .N,)). +). along with their variants using Laplacian attention. Here, we see that att-Graph-level NLSFs do not show significant improvement over the standard Graph-level NLSFs. Notably, (N, :) outperforms other models in social network datasets (IMDB-B, IMDB-M, and COLLAB), where the node features are augmented by the node degree. We plan investigate the limited graph attribution in future work.
The ablation study of att- att-Pooling-NL.o NLSFs for graph classification is reported in Tab. 11. Similar to Tab. 10, we consider eight graph classification benchmarks: MUTAG, PTC, ENZYMES, PROTEINS, NCII, IMDB-B, IMDB-M, and COLLAB. Tabl. 11 demonstrates that using the graph Laplacian in Index Pooling-NLSFs (denoted as O (L,-) and the normalized graph Laplacian N in Value Pooling-NI.SHE (denoted as O (N,)) achieves superior graph classification accuracy compared to using the normalized graph Laplacian N in Index Pooling-NLSS (denoted as O (N, -)) and the graph Laplacian L in Value Pooling-NLSFs NLSFs (denoted @ (L.-)). -)). This finding aligns with theoretical results in App. D.5. Morcover, the Stt-Poolinng-Ne -NSSss using the Laplacian attention att? (0 ind (L.-) (N, )) yield the highest accuracies across all datasets, corroborating the findings consistently outperform att-Graph-level NLSFs as shown in Tab. 10, indicating that the node features learned in our Node-level NLSFs representation are more expressive. This supports our theoretical findings in Sec. 4.3.
in Sec. 3.5. In addition, att- Pooling-NLSS
The ablation study demonstrates that the Laplacian attention between the Index and Value NL.Fs significantly enhances classification accuracy for both node and graph classification tasks across various datasets, outperforming existing baselines.
34

---

Table 12: Average running time per epoch(ms))aveeaage total running time(s).
Cora
Citeseer
Puhmed
Chameleon
Squirel
Actor
GCN
8.97/2.1
9.1/2.3
12.15/3.9
11.68/2.7
25,52/6,2
14.51/3.8
GAT
13.13/3.3
13.87/3.6
19.42/6.2
14.83/3.4
46.13/15.9
20.13/4.4
SAGE
11.72/2.2
12.11/2.4
25.31/6.1
60.61/12.7
321.65/72.8
25.16/5.4
ChebNet
21.36/4.9
22.51/5.3
34.53/13.1
42.21/16.0
38.21/45.1
42.91/9.3
ChebNeill
20.53/5.9
20.61/5.7
33.57/12.9
39.03/17.3
37.29/38.04
40.05/9.1
CayleyNet
401.24/79.3
421 669894334
723.61/252.3
848.51/389.4
972.53/361
794.61/289.4
APPNP
18.31/4.2
19.17/4.8
19.63/5.9
18.56/3.8
24.18/4.9
15.93/4.6
GPRGNN
19.07/3.8
18 19/40
19.77/6.3
19.31/3.6
28, 28/31/5.5
17.28/4.8
ARMA
20.91/5.2
19.33/4.9
34,27/14.5
41.63/19.7
42/42/2
46.22/5.7
att-Node-level NLSFs
18.22/4.5
18.51/44
20.23/6.1
28.51/17.1
25.56/5.1
17.09/4.6
Table 13: Experimental results large heterophilic graphs. The results for BernNet, ChebNet, ChebNetll, and GPRGNN are taken from [41]. while the results for OptBasisGNN are taken from [38]. All other competing results are taken from [63].
Penn94
Pokec
Genius
Twitch- Gaach-GGmers
Wiki
82.47
+5.45
.7.442+0.4
62.18
0OM
LINK
80.79
80.54
73.56+0.1
64.85=a2
$7.1
LINKX
84.71
82, 10.11
90.77.103
66.06112
59.80...4
GPRGNN
83.54
80.74.0.2
90.15.03
62.59=04
58.73
ChebNet
82.59
72.71
89.3610.3
62.31
OOM
ChebNetll
84.86=0.
82.33
90.85+03
65.03=a3
60.95+04
BernNet
83,26
81.67.0.2
90.47.103
64.27
59.02.103
OptBasisGNN
84.85
82.83
90.83+0.
65.17=02
61.85
att-NNdd-level NLSFs
85.19
82.96=a011
91.24
65.97=a2
62.44
F,4 Runtime Analysis
In our NLSFs, the eigendecomposition can be calculated once for each graph and reused in the training process. This step is essential the cost of the forward pass during model training often surpasses the initial cigendecomposition preprocessing cost. Note that the computation time for eigendecomposition considerably less than the time needed for model training. For medium and large graphs, the computation time is further reduced when partial cigendecomposition is utilized, making more efficient than the training times of competing baselines. To evaluate the computational complexity of our NLSFs compared to baseline models, we report the empirical training time in Tab. 12. Our Node-level NLSFs showcase competitive rumning times, with moderate values per epoch and total running times that are comparable to the most efficient models like GCN, GPRGNN, and APPNP. Notably, Node-level NL.SFs are particularly efficient for the Cora, Citeseer, and Pubmed datasets. For the dense Squirrel graph, our Node-level NI.FFs exhibit efficient performance with moderate running time, outperforming several models that struggle with significantly higher times.
F.5 Scalability to Large-Scale Datasets
To demonstrate the scalability of our method, we conduct additional tests on five large heterophilic graphs: Penn94, Pokec, Genius, Twitch-Gamers, and Wiki datasets from [63]. The experimental setup is in line with previous work by [16, 63, 41]. We use the same hyperparameters for our NL.Fs as reported in App. E. Tab. 13 presents the classification accuracy. We see that NL.SFs outperform the competing methods dataset, NLSFs yield the second-best results. Our additional experiments show that our method could indeed scale to handle large-scale graphs effectively.
the Penn94, Pokec, Genius, and Wiki datasets. For the
F.6 Index-by-Index Index-NLSFs and Band-by-Band Value-NLSFs
Our primary objective in this work to introduce new GNNs that are equivariant to functional symmetries, based on novel spectral domain that is transferable between graphs. We emphasize
35

---

Table 14: Graph classification performance using Diagonal NLSFs, including index-by-indes Index- NLSFs and band-by-bana Value-NLSFy along with their variants using Laplacian attention. The symbol (1) denotes an improvement using Laplacian attention.
MUTAG
PTC
FNZYMES
PROTEINS
NCTI
IMDR-8
IMDR-M
COLLAR
T (N.) [
82.33u17
66 66-43:1a
69.69
83,47:22
77 77.43a14
60.77ac
5004g12
70,89a29
82.85
63. 63.40
68.06:11
$2,69.s
78,00114
62:274:1
51.74114
70.69113
62.77
63 20000
64 19
$3.50a12
78 78.2641
7061e72
51 86
77.03ai5
20.29.0
65 15.02:14
29.29
$1,02.12
78.28.10
74.33117
52.89
80.41:84
stt (all, J.T. (L.
85.19
66.43118
69.99
83,47
76 16.26.14
10.6
$2.0314
77.56.15
stt a T.a.N
83.34a12
66.58112
26.13
(1)
22.99
78.28
14.3
53.14:58
50.41
64U08a07
68.116621
78.26.14
70.61422
52.13
75.12419
09.69
78.28-18
Table 15: semi-supervised node classification accuracy using NLSFs, diag-NLSFs, lead-NLSFs and Sead-diag-NISSF
Citeseer
Pubmed
Squirrll
Att-Node-level ding-NLSFs
85,37
75 75.41
82.22a1a
50,58=13
38. 38.39s09
35. 13.13
---ooee--eeel NLSFs
86.03e12
74.87+12
83.15=15
50.12=12
36,23+1s
35.01=177
-t--Nodo-eeeel lead-NLSFs
35,26
74.16=14
82.24203
49 49.86219
34.21
33,68=11
att-Nodeelevel lead-diug. SFs
84.75
73.62.11
81.93
49.68.16
38.25
34.72_n9
the unique aspects of our method rather than providing an exhaustive list of operators in this group, which, while important, is key direction for future research.
Here, we present a new type of NLSFs: index-by-index Index-NLSF's and band-by-band Value-NLSFs. We denote them as follows:
and P,X a I
T inn A,
X
Σ 7/
(IP
sig
+
j=1
sig
K
gi (L) A
T vall A X) = Σ
(1le)
(
19p
I +
==1
where o, are as before in Sec. 3.3. Note that these operators are also equivariant to our group actions.
We investigate by-ix-x Index-NLSFs and band-by-band Value-NLSFs in graph classification tasks as described in Sec. 5, including MUTAG, PTC, ENZYMES, PROTEINS, NCII, IMDB-B, IMDB-M, and COLLAB datasets. Unlike Graph-NLSFs, which are fully spectral and map sequence of frequency coefficients to output vector, index-by-inde Index-NLSFs and band-by-band Value- NLSFs do not possess such a sequential spectral form. In index-by-indes byniiexx Index-NLSFa and band- by-band Value-NLSFs, the index-by-inde to the graph domain. Consequently, for graph classification tasks, we apply the readout function as defined for Pooling-NLSSFs in Sec. 3.4.
(or band-by-band) frequency response is projected back
Following App. F.3, we examine index- seex-bb-iidexx Index-NLSFs and band-by-bame Value-NLSFs settings using graph Laplacian L and normalized graph Laplacian N, including I (L,-), -), 1 1 (N, -). I (L, and & .N..). :), along with their variants using Laplacian attention, where P denotes the pooling function as in Tab. 11.
Tab. 14 presents the graph classification accuracy using index-by-index Index-NLsS and band-by- band NLSFs. It shows that incorporating Laplacian attention consistently improves classifica- tion performance, aligning with the findings in App. F.3. We note that Index-by-index Index-NLSS and band-by-band Value-NISFs perform comparably to existing baselines in graph classification benchmarks. However, index-by-index Index-NI.St SFS and band-by-band Value-NISSE are generally less effective compared to Pooling-NLSFs as shown in Tab. 11.
36

---

1
1 4
0
2
8
2
Figure 5: Illustration of dyadic sub-bands for r = and S = 4.
Table 16: Graph classification performance using Graph-NI.SH, with uniform sub-bands. The symbol (t) denotes an improvement using Laplacian attention.
MUTAG
PTC
ENZYMES
PROTEINS
NC11
IMDB-B B
IMDB-M
COLLAB
Pesl Pai(N.)
82 14.12
65.73:24
62 62.31
78.22.15
50,51:12
63.2 63.27-11
50.29
70.06.15
83,27a33
0608121
60.18103
50.31a14
78.40
64.58.22
$2.33a
71 88
81.75484
6481414
64-46412
78.31.89
78.22-14
70.84
50.42-1
73.89
(N.
$1.12a88
65:13127
00006113
78.85.84
78,45.15
74.05
51.13
78.16.13
$2 76.603
(1)
65.73:24
64.5%
79,23
(1)
11.51-14
20
51.04-22
(1)
74.21412
(t)
atarhh (N..)
$3.27
60.08.211
61.25
(1)
$1.07-177
(1)
79
79,26-11
7408
$2.33.00
78.16.13
ats strre. 1.
$3.27.133
66.08.21
64 64.66112
50.51
79.14..4
7034-:3
$2.33.00
74.5412
(1)
at L. OuilN
$2,53
(1)
65.73u04
62.31a
79.54.31
(1)
7408
51.57
(1)
78.1661
F.7 Node Classification Using Diag-NLSSs and Lead-NLSFs
In App. C, we presented the diag-NLSFs,, considering ă d, and lead-NLSFss for leading filters that do not include orthogonal complements. We explore the leading filters, orthogonal complement, and diagonal operation in our NLSFs. The results of these investigations are summarized in Tab. 15 which shows the node classification accuracy achieved using various configurations, including NLSFs. diag-NLSFF Wead-NLSFs, and Lead-diag-NLSFF We see that incorporating both the orthogonal complement and the multi-channel approach yields the highest classification accuracy.
F8 Uniform Sub-Bands
Our primary objective in this work to introduce new GNNs that are equivariant to functional symmetries, based on a novel spectral domain transferable between graphs using analysis and synthesis. Our NLSFs Sec. 3.4 consider filters 9j that are supported on the dyadic sub-bands [AyrS-5+1 ANT "j. The closer the low-frequency range, the denser the sub-bands become. We illustrate an example of filters 9j supported on dyadic sub-bands with r = 1/ and = 4 in Fig. 5, showing that sub-bands become denser as they approach the low-frequency range. Our primary goal is to highlight the unique aspects of our method rather than sub-band separation, which, while crucial, is important consideration across spectral GNNs. Therefore, sub-bands, where filters Zj supported on the uniform sub-bands [(j 1) A . Ag Note that the modifications required for our NLSFs are minimal, and most steps can be scamlessly applied with filters supported on the uniform sub-bands.
also present uniform
We evaluate our NLSFFs with uniform sub-bands on graph classification tasks. We consider the graph benchmarks as in Sec. 5, including five bioinformatics datasets: MUTAG, PTC, NCI1, ENZYMES, and PROTEINS, and three social network datasets: IMDB-B, IMDB-M, and COLLAB. Note the sub-bands only affect our Value-NLSFs, where Index-NLSFss remain the same as in Sec. 3.4.
We report the graph classification accuracy of Graph-NLSFFs and Pooling-NLSSI sub-bands in Tab. 16 and Tab. 17, respectively, where the in (L, -), + ind (N, +). @nd -). and Ond (NN.) are the index-based NLSFs and therefore they are the same as Tab. 10 and Tab. 11. Interestingly, the Laplacian attention does not yield significant improvements for either Graph-level NLSFF or Pooling-NLSFs when considering uniform sub-bands. Moreover, we observe that the graph classification performance is generally worse than when using the dyadic sub-bands reported in Tab. 10 and Tab. 11. We emphasize the importance of considering the spectral support of filters 9j. Empirically, we found that using the dyadic grid is more effective, which is why we focus on it and report those results in the main paper. However, exploring other sub-bands remains an important task for future work. For instance, we plan to investigate sub-bands based on {ar - b)k_ for other choices of < r < 2 and b > In the limit when r -> 1, -> oo and - oo this "converges" to the uniform grid.
using uniform
37

---

Table 17: Graph classification performance using Pooling-NLSES with uniform sub-bands. The
symbol (1) denotes an improvement using Laplacian attention.
MUTAG
PROTTHNNS
IMDB-M
COLLAAB
71,25.00
77.0
72.00
33.4911
67.12:19
68.38117
82.89
8057:24
72.85:14
50.91114
25,02-112
(N,)
83.54
64 64.22,n0
62. 62.24467
80.03
8050811
72 12.49
$2.08454
80.80.22
and (8 (la)) (1)
214
68.76:04
69.88
84.27
50. 30.33
42.85
51.01
76. Be61
(1)
ate Oeu NN1. (.
Bd.52sta
17.19:12
67.13
(7)
62.53a11
(1)
80, $0.90:1
72.69.11
53 13.16.85
(1)
8089
(te (N. J.N.].eBl. Baal. 1)
N4.52.04
08.1
(1)
00,44:39
(7)
K3.52424
(1)
30.57422
72.85
52,45413
77.42407
(1)
and (T. B.iN
26.41
68.66:09
69.88
84.27
$0,90
72.49
53.48;17
81.12
G Additional Related Equivariant GNNs
Equivariant GNNs are designed to handle graph data with symmetries. The output of an equivariant GNN respects the same transformation applied to the input. Depending on the application, the transformation could involve translations, reflections, or permutations, to name but few [82, 46, 78J. Due to respecting the symmetries, equivariant GNNs can reduce model complexity and improve generalization [35, 27]. which can be applied to test data and produce more interpretable representations [99, 51]. When symmetry plays a critical role, such as in physical simulations, molecular modeling, and protein folding, equivariant GNNs have been demonstrated to be effective [20]. For example, [91, 33] employ spherical harmonics to handle 3D molecular structures, and [82] simplify computations for explicit rotation and translation matrices by focusing relative distances between nodes. In addition, [30] embeds symmetry transformations by parameterizing convolution operations Lie groups, such rotations, translations, and scalings, through Lie algebra.
38

---

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 point out that our NLSFs are fully equivariant to graph functional shifts and show that they have universal approximation properties, where the proposed NLSFs are based on a new form of spectral domain that transferable between graphs. We list out our contributions in Sec. 1.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A 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.
It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We present the limitation discussion of our method in Sec. 6 (lines 359-363).
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section 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 authors should reflect 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 on a few datasets or 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 approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it 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 address problems of privacy and faimess.
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 an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
39

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Right before and/or after each stated theoretical result, we indicate that the proof and the theoretical analysis can be found in App. D.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
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 provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or 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 information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Detailed descriptions of the methodology are provided in the manuscript and App. E. The method can be re-implemented, and results are reproducible.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer to this question will not 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, 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 hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of 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.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce 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 authors are welcome 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 (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
40

---

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, as described in supplemental material?
Answer: [Yes]
Justification: We provide detailed descriptions of our method's implementation within the paper and report the hyper-parameters! in App. E.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttps://nips.cm Bttll//guiides/ooeSeuue
onsiliillycy 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: / /nips. cc/public/guiieeeeccccccccccccce gwtp///iiee//eee///g httpa///ggiieee//eeuuuiiiiieeees
for more details.
The authors should provide instructions data access and preparation, including how to 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. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to 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
Question: 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?
Answer: [Yes]
Justification: We provide comprehensive information data splits, hyperparameters, and the criteria for their selection. Additionally, we describe the type of optimizer used and other relevant training details. All this information is thoroughly detailed in App. E.
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 to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: In Sec. 5, we report the node classification quality by computing the average classification accuracy along with 95% confidence interval. Additionally, present the mean and standard deviation for the graph classification accuracy to provide a comprehensive understanding of the experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
41

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to 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 or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that 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 or 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: Detailed descriptions the type of computer resources and time of execution are provided in App. E and App. F.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or 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 failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: : /ttp//euuippp//e
Answer: [Yes]
Justification:
We have respected the NeurIPS code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS 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.. there special consid- eration due to laws or regulations in their jurisdiciio))
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper presents work whose goal advance the field graph machine learning. The paper has no foresecable societal impact.
42

---

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 specific groups), privacy considerations, and security considcrations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is 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, it 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 as intended and functioning conrectly, 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 mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe 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 paper poses such risks.
Guidelines:
The answer NA means that the paper poses no 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 requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
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 is 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]
We provide credit to the original papers of all external data, code, and models used in this work, ensuring that their contributions are acknowledged and their licensing terms are followed.
Justification:
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, possible, include URL.
43

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it 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 is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide detailed descriptions of our method's implementation within the paper and report the hyper-parameters in App. E.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as 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 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 crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing nor research with human subjects was involved in this work.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No crowdsourcing nor research with human subjects involved in this work.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
44

---

Depending on the country in which research is conducted, IRB approval (or equivalent) 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 NeurIPS 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.
45


Reviews:
[{"review_id": "w6Rk6FtZdT", "reviewer": "Reviewer_8cKX", "summary": "The paper tackles the task of Network design for graph neural networks. The suggested approach is based on spectral properties of graphs. So far in the literature spectral methods were limited in assuming that the graph domain is fixed. To address this, a relaxed version of symmetry is proposed based on band-limited projections. In addition, a nonlinear spectral filter design is suggested, suggesting node-level, graph-level, and pooling operations. The method is evaluated on several graph learning tasks, demonstrating improvement in generalization over existing spectral methods.", "questions": "No question other than the weakeness stated above.", "limitations": "Yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper makes a valuable contribution to the literature on Graph Neural Networks (GNNs), particularly by addressing the challenge of transferability in spectral methods, which is highlighted as a significant issue.\n\nclaims are supported by theoretical analysis.\n\nThe paper is self-contained, providing both background information and a short overview on spectral graph learning.", "weaknesses": "Writing Quality: Some sections of the manuscript could benefit from revision. For instance, reordering the paragraphs in the introduction could improve readability. Specifically, mentioning what was missing from previous works earlier rather than at the end would help.\n\nMore examples can be found in the method section: i) The discussion on problem the activation functions is missing some details, e.g., what rho is exactly? ii) The paper states that \"It is important to note that functional shifts, in general, are not induced from node permutations. In stead, functional shifts are related to the notion of functional maps...\". This sentence is too vague. Consider adding more details to make it clearer.\n\nNo qualitative results are provided. Is it possible to visualize learned features as in the illustration in figure 2? Is it possible to design a toy experiment showcasing the suggested notion of relaxed symmetry, for which the suggested network design generalizes adequately?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback.\n\n>**Enhancing Writing Quality for Improved Readability and Clarity:**\n\nThank you for your valuable feedback. \n    \nIn response to the reviewer’s suggestions, we will make the following revisions:\n- Introduction Section: We will reorder the paragraphs in the introduction. Specifically, we will highlight the research gap earlier in the section. \n- Method Section:\n    - We will emphasize that $\\rho$ is any non-linear activation function (such as ReLU, Sigmoid, etc.). We will include the following explanation of why non-linear activation functions break the functional symmetry. We offer a construction for complex-valued signals, which is easy to extend to the real case. Consider a 1D grid with $100$ nodes and the central difference Laplacian. Here, the Laplacian eigenvectors are the standard Fourier modes. In this case, one can see that a graph functional shift is any operator that is diagonal in the frequency domain and multiplies each frequency by any complex number with the unit norm. Consider the nonlinearity that takes the real part of the signal and then applies ReLU, which we denote in short by ReLU. Consider a graph signal $x=(e^{i\\pi 10n/100} + e^{i\\pi 20n/100})_{n=0}^{99}$. We consider a graph functional shift $S$ that shifts frequencies 10 and 20 at a distance of 5, and every other frequency is not shifted. Namely, frequency 10 is multiplied by $e^{-i\\pi 50/100}=-i$, frequency 20 by $e^{ -i\\pi = -i\\pi 100/100}=-1$, and every other freequency is multiplied by 1. Consider also the classical shift $D$ that translates the whole signal by $5$ uniformly. Since $x$ consists only of the frequencies 10 and 20, it is easy to see that $Sx=Dx$. Hence, $ReLU(Sx)=ReLU(Dx)=D(ReLU(x))$. Conversely, if we apply $ReLU(x)$ and only then shift, note that $ReLU(x)$ consists of many frequencies in addition to 10 and 20. For example, by nonnegativity of ReLU, $ReLU(x)$ has a nonzero DC component (zeroth frequency). Now, $S(ReLU(x))$ only translates the 10 and 20 frequencies, so we have $S(ReLU(x))\\neq D(ReLU(x))=ReLU(S(x))$. \n    We will add this example to an appendix.\n    - We will revise the sentence, \"Instead, functional shifts are related to the notion of functional maps...\" into \"Instead, functional shifts are general unitary operators that are not permutation matrices in general. The value of the functionally translated signal at a given node can be a *mixture* of the content of the original signal at many different nodes. For example, the functional shift can be a combination of shifts of different frequencies at different speeds.\" \n    - We will also explain in detail why spectral filters commute with graph functional shifts. This is easily seen from the fact that both spectral filters and functional shifts are diagonal operators in the graph Fourier domain.\n            \n>**Visualizing Learned Features and Demonstrating Relaxed Symmetry:**\n\nVisualizing the learned filter directly is not feasible due to its high-dimensional nature: the filter is a general MLP, which makes it challenging to visualize in a meaningful way (as is typically the case in deep learning). However, to illustrate the concepts of relaxed symmetry and functional translation, we will add a new toy example. Similarly to the above construction, one example of a functional translation on the grid, which is not a classical translation, is an operator that translates different frequency bands at different speeds. In the example, we compare the translation of a Gaussian signal on a 2D grid by a classical uniform translation and by different speeds for different frequencies. See the experiments in the rebuttal PDF.\n\nIn addition, we add another experiment showing that functional translations are much more stable than hard symmetries of the graph, namely, graph automorphisms (isomorphisms from the graph to itself). Autonorpisms are another analogue to translations on general graphs, which competes with our notion of functional shifts. Consider again the standard 2D grid on the torus. The automorphisms of the grid include all translations. However, this notion of hard symmetry is very sensitive to graph perturbations. If one adds or deletes even one edge in the graph, the automorphism group becomes much smaller and does not contain the translations anymore. On the other hand, we propose a toy experiment that illustrates the graph functional shifts are stable to graph perturbations. Specifically, we show that standard translations can be approximated by a graph functional shift on a perturbed grid (adding Gaussian noise to the edge weights), optimizing the coefficients of the functional shift so the operator is as close as possible to the classical shift. See Figure 2 in the PDF. We then train the NLSFs on a perturbed grid to do MNIST classification, following the setup in [1,2,3]. We compare the NLSF on the clean grid to the NLSF on the perturbed grid. Table 3 shows that the performance of the NLSF is almost unaffected by the perturbation, which demonstrates that NLSFs on the perturbed grid can roughly implement CNN-like architectures (translation equivariant functions).\n\nThese examples will be incorporated into the camera-ready version if accepted, including the discussion about automorphism symmetries vs functional shifts.\n\n[1] Defferrard et al. (2016). Convolutional neural networks on graphs with fast localized spectral filtering.\n\n[2] Monti et al. (2017). Geometric deep learning on graphs and manifolds using mixture model CNNs.\n\n[3] Levie et al. (2018). Cayleynets: Graph convolutional neural networks with complex rational spectral filters.", "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": "Q7U31Fv2ce", "reviewer": "Reviewer_fGo4", "summary": "The authors propose nonlinear spectral filters (NLSFs) that achieve full equivariance to graph functional shifts, demonstrating that these filters have universal approximation properties. These NLSFs are designed based on transferable spectral domain, potentially improving GNN performance in node and graph classification tasks across diverse graph structures.", "questions": "(i) Does your theory adapt differently when applied to heterophilous graphs compared to homophilous graphs, and if so, how are these differences addressed within your methodology?\n\n(ii) Given that your Nonlinear Spectral Filters (NLSFs) are motivated by respecting graph functional shift symmetries, similar to Euclidean CNNs, do you have any claims or observations regarding how NLSFs fit within or potentially extend the Weisfeiler-Lehman hierarchy of expressivity? Additionally, could you elaborate on how the expressivity of NLSFs, as informed by metrics from the Euclidean vector space, compares to traditional graph neural network models?", "limitations": "Also, the efficiency of the proposed models in terms of computation and resource utilization is not adequately addressed. For practical applications, especially in resource-constrained environments, understanding the computational overhead is essential.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1- The paper is well-written and self-contained, offering clear, didactic insights. The experiments provide valuable conclusions that future practitioners will find useful. However, a synthesis of the information could further enhance readability and understanding for the reader.\n\n2- The use of the nonlinear spectral filters for graphs to achieve full equivariance to graph functional shifts may be a promising avenue to explore.", "weaknesses": "Despite these merits, I have the following concerns about the paper.\n\n1- While the paper presents a compelling method with potential applications in graph analysis, one significant limitation is its scalability, particularly concerning large-scale graphs. The reliance on specific spectral properties, such as the leading eigenvectors, may not only limit the method's capacity to capture diverse graph dynamics but also result in computational inefficiencies when applied to extensive graph datasets.\n\n2- The datasets used in the paper predominantly consist of mid-sized, homophilic graphs, which may not fully represent the diverse range of real-world applications, particularly in contexts involving heterophilic graphs.\n\n3- The efficiency of the proposed models in terms of computation and resource utilization is not adequately discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful comments and questions.\n\n>**Complexity, Efficiency, and Runtime Analysis:**\n\nIn Section 4.1, we discussed our method's complexity and efficiency, highlighting the efficiency of the Lanczos algorithm. This algorithm estimates the leading $J$ eigenvectors in $O(JE)$ operations per iteration and converges quickly, making it as efficient as a message-passing neural network with $J$-dimensional features.\n\nWe will extend Section 4.1 to clarify that the Lanczos algorithm can be viewed as a message-passing algorithm for sparse graphs, using only the matrix's nonzero entries, interpreted as edges in graph machine learning. In addition, we reported the runtime analysis in Appendix C, where the average running time per epoch(ms)/average total running time(s) of our method is 18.22/4.5 for Cora, 18.51/4.4 for Citeseer, 20.23/6.1 for Pubmed, 28.51/17.1 for Chameleon,  25.56/5.1 for Squirrel, and 17.09/4.6 for Actor. In comparison, for example, the runtime for ChebNetII is 20.53/5.9 for Cora 20.61/5.7, for Citeseer, 33.57/12.9 for Pubmed, 39.03/17.3 for Chameleon, 37.29/38.04 for Squirrel, and 40.05/9.1 for Actor. Our method is efficient and comparable with competing baselines. Furthermore, we will include the space overhead (MB) of our method: 79 for Cora, 163 for Citeseer, 2054 for Pubmed, 85 for Chameleon, 263 for Squirrel, and 319 for Actor. In comparison, the space overhead for ChebNetII is 67 for Cora, 159 for Citeseer, 1821 for Pubmed, 79 for Chameleon, 259 for Squirrel, and 316 for Actor. \n\nWe also explain below how we addressed the limitation of computing only the leading eigenvectors. We slightly extended the NLSF method (the extension is called rem-NLSF), which now allows capturing all of the frequency contant of the graph. See the details below.\n\n>**Theoretical Analysis on Heterophilic Graphs and Large-Scale Datasets:**\n\nThank you for your comment. \n\nWe would like to clarify that in our first submission, we used three heterophilic graphs (Chameleon, Squirrel, and Actor) among the six datasets for the node classification task. We will emphasize this point more clearly in our revised version.\n\nMotivated by the reviewer's question, we extend our approach to include an additional filter in both Index and Value NLSFs. For Index NLSFs, we incorporate the $(J+1)$-th filter as $\\mathbf{I} - \\sum_ {j=1}^J \\mathbf{P}_ j$, and for Value NLSFs, we add the $(K+1)$-th filter $\\mathbf{I} - \\sum_ {j=1}^K g_ j(\\mathbf{\\Delta})$. This alleviates the loss of information due to projecting to the low-frequency bands. Now, the full spectral range of the signal is captured by the NLSF.\n\nWe denote these NLSFs with orthogonal complement as **rem-NLSFs**. This setup is particularly relevant for heterophilous graphs, which require high-frequency components to accurately represent the labels. Table 2 presents the classification performance, and we see that rem-NLSFs improve performance for heterophilic graphs. We will motivate this construction in our paper from the perspective of heterogeneous components of the target.\n\nThe theory, and all of our proofs, trivially extend to rem-NLSF. If the reviewer would like to see the new version of the proofs, which are almost identical to the old proofs, we would be more than happy to send an anonymous PDF file to the AC according to NeurIPS regulations.\n\nIn addition, following the reviewer's questions, we conduct additional tests on five large heterophilic graphs: Penn94, Pokec, Genius, Twitch-Gamers, and Wiki datasets from Lim et al. (2021). The experimental setup is in line with previous work by Chien et al. (2021), Lim et al. (2021), and He et al. (2022). We use the same setup for our NLSFs as reported in Appendix B. Table 1 (in the global response PDF) presents the classification accuracy. We see that rem-NLSFs outperform the competing methods on the  Penn94, Pokec, Genius, and Wiki datasets. For the Twitch-Gamers dataset, rem-NLSFs yield the second-best results. Our additional experiments show that our method could indeed scale to handle large-scale graphs effectively. \n\nThank you again for the valuable comment.\n\n>**Expressivity:**\n\nWe note that graph-level NLSFs are bounded by the expressive power of MPNNs with random positional encodings. For example, in [1], the authors showed that random features improve GNN expressivity, distinguishing certain structures that deterministic GNNs cannot. The Lanczos algorithm for computing the leading $J$ eigenvectors can be viewed as a message-passing algorithm with a randomly initialized $J$-channel signal.\n\nIn Section 4.3, we discuss the expressivity in the context of a single fixed graph with variable signals. This setting is unrelated to the traditional graph isomorphism test hierarchy of expressivity. \n\nAt the graph-level, our example in Appendix A.2.4 can be used to show that graph-level NLSFs (without synthesis and pooling) are not more expressive than spectral GNNs. We also have an approach for showing that spectral GNNs are more expressive than graph level NLSF (without synthesis and pooling), but it requires very high dimensional features and unstable filters. If the reviewer would like to see the analysis, we can write you a comment in OpenReview or send an anonymous PDF to the AC according to the NeurIPS regulations.\n\nRegarding pooling-NLSFs, we do not have an answer to whether standard spectral GNNs are more powerful than pooling-NLSFs with unlimited resources. A more practically useful question is comparing their expressivity within the same parameter budget. This is a theoretically challenging question. However, in practice, NLSFs typically perform better than standard spectral GNNs with equal budgets, or equivalent architecture. This comparison is also valid for graph-level NLSF (without synthesis and pooling).\n\nWe will add a discussion on these points in the camera-ready version if accepted. \n\n[1] Sato et al. (2021). Random features strengthen graph neural networks.", "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": "v892UQ7PDW", "reviewer": "Reviewer_J5Wx", "summary": "The authors introduce spectral GNNs that are equivariant to functional symmetries. Specifically, they introduce node-level, graph-level and pooling non-linear spectral filters and show that these are able to outperform standard convolutional GNNs on (semi-supervised) node classification and graph classification tasks.", "questions": "- While it's very intuitive to understand what is meant by \"shift\" in the context of images and CNNs, this doesn't come across very clear in the paper in the context of graphs: what is the rationale behind the decision to \"model the group of translations on graphs as the group of all unitary operators on signals that commute with the graph shift operator\"? If more space in the paper can be used to make the underlying concepts more accessible (perhaps moving some of the material on the theoretical properties of the NLSFs to the appendix) I think the paper would greatly gain in accessibility, potentially increasing its impact beyond the graph signal processing community.", "limitations": "The limitations are clearly discussed.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The experimental results are compelling.\n- To the best of my understanding, the theory is sound\n- The idea being proposed is novel and worth being investigated\n- The paper is clearly written, even though it doesn't seem to be very accessible to readers unfamiliar with graphs signals processing", "weaknesses": "- While the authors did a good job in trying to introduce all the relevant concepts, the paper is quite dense with mathematical details and notions that will likely be unfamiliar to many GNN researchers and may therefore hinder the accessibility of the manuscript.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and encouraging comments. \n\n>**Enhancing Accessibility of Theoretical Contributions:**\n\nThank you for your comment. \n    \nWe recognize the importance of making our manuscript accessible to a broader audience. To improve accessibility, we will provide more details on the mathematical concepts in the appendix. For instance, we will write and explain Schur’s lemma, extend the discussion on random geometric graphs, and elaborate on the background of the cut norm and Hoeffding's inequality.\n\n>**Clarifying the Concept of Functional Translation on Graphs for Enhanced Accessibility:**\n\nWe will extend the text in Section 3.1 to further clarify the link between graph functional shifts and standard domain translations. We will start by showing that on the standard grid (on the 2D torus) with central difference GSO, the standard Fourier basis is the eigenbasis of the Laplacian. We will then show that any domain shift on the grid, when applied on signals, is equivalent to modulation in the frequency domain. Hence, domain shifts commute with the Laplacian (both of them are diagonal matrices in the frequency domain). Functional shifts are defined by adopting this property as a definition. We call *any* unitary operator that commutes with Laplacian a graph functional shift. For the grid, these include exactly the operators that multiply each frequency by a complex number of unit modulus. \n\nFig. 1  (in the global response PDF) presents a comparison of a classical and a functional translation of a Gaussian signal. The classical translation $f(t-T)$ is a specific case of functional translation, which is equivalent to modulation in the frequency domain $e^{-i\\omega T}\\hat{f}(\\omega)$. Our example of a graph functional shift is an operator that modulates low frequencies by a given rate and modulates high frequencies by another rate. This is interpreted as shifting the low-frequency content and the high-frequency content of the signal at different speeds. This illustrates that functional symmetries are more rich than domain symmetries. \n\nIn addition, we add another experiment showing that functional translations are much more stable than hard symmetries of the graph, namely, graph automorphisms (isomorphisms from the graph to itself). Autonorpisms are another analogue to translations on general graphs, which competes with our notion of functional shifts. Consider again the standard 2D grid on the torus. The automorphisms of the grid include all translations. However, this notion of hard symmetry is very sensitive to graph perturbations. If one adds or deletes even one edge in the graph, the automorphism group becomes much smaller and does not contain the translations anymore. On the other hand, we propose a toy experiment that illustrates the graph functional shifts are stable to graph perturbations. Specifically, we show that standard translations can be approximated by a graph functional shift on a perturbed grid (adding Gaussian noise to the edge weights), optimizing the coefficients of the functional shift so the operator is as close as possible to the classical shift. See Figure 2 in the PDF. We then train the NLSFs on a perturbed grid to do MNIST classification, following the setup in [1,2,3]. We compare the NLSF on the clean grid to the NLSF on the perturbed grid. Table 3 shows that the performance of the NLSF is almost unaffected by the perturbation, which demonstrates that NLSFs on the perturbed grid can roughly implement CNN-like architectures (translation equivariant functions).\n\nThese examples will be incorporated into the camera-ready version if accepted, including the discussion about automorphism symmetries vs functional shifts.\n\n[1] Defferrard et al. (2016). Convolutional neural networks on graphs with fast localized spectral filtering.\n\n[2] Monti et al. (2017). Geometric deep learning on graphs and manifolds using mixture model CNNs.\n\n[3] Levie et al. (2018). Cayleynets: Graph convolutional neural networks with complex rational spectral filters.", "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": "wTwK9qLRyk", "reviewer": "Reviewer_GXWH", "summary": "This paper proposes a spectral GNN called non-linear spectral filters (NLSF), which aims to enhance GNNs with nonlinear functions. Since general GNNs with nonlinear functions do not commute with unitary operators, this paper defines Graph Functional Shifts, which is a set of unitary matrices commuting with a normal graph shift operator (GSO). It then formulates two functions for spectral index and filter bank, respectively, and concatenates these two functions as graph attention. In the experiment section, NLSF is compared with GAT, SAGE, and other spectral-like GNNs. In the node-classification task, att-Node-level NLSF shows outstanding performance among these models. In the graph classification task, att-Graph-level NLSF achieves comparable results with these models, and att-Pooling-NLSF performs better than other models in the graph classification task.", "questions": "None", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. NLSFs have a solid mathematical foundation and proof, especially on Universal Approximation and graph expressivity.\n2. The experimental results validate the effectiveness of the theory.", "weaknesses": "1. The method proposed in this paper requires the use of eigenvalues, hence it necessitates eigen decomposition of the GSO. The time complexity of eigendecomposition is relatively high, especially for very large graphs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comment.\n \nPlease note that in Section 4.1, we discussed the complexity of our method. We elaborated on the efficiency of the Lanczos algorithm, which is well-known for its computational efficiency. For estimating the leading $J$ eigenvectors, the Lanczos algorithm takes $O(JE)$ operations per iteration and converges very fast, where $E$ is the number of edges. Hence, the Lanczos algorithm is as efficient as a message-passing neural network that operates on features of dimension $J$.\n\nSection 4.1 already discusses the efficiency of the Lanczos algorithm, but we will extend the text and make this clearer. We will clarify that the Lanczos algorithm (for sparse graphs) can be seen as a message-passing algorithm, as it only uses the nonzero entries of the matrix, which are interpreted as edges in our context of graph machine learning. \n\nAdditionally, we reported the runtime analysis in Appendix C, where the average running time per epoch(ms)/average total running time(s) of our method is 18.22/4.5 for Cora, 18.51/4.4 for Citeseer, 20.23/6.1 for Pubmed, 28.51/17.1 for Chameleon, 25.56/5.1 for Squirrel, and 17.09/4.6 for Actor. In comparison, for example, the runtime for ChebNetII is 20.53/5.9 for Cora 20.61/5.7, for Citeseer, 33.57/12.9 for Pubmed, 39.03/17.3 for Chameleon, 37.29/38.04 for Squirrel, and 40.05/9.1 for Actor. Our method is efficient and comparable with competing baselines. \n\nWe appreciate the reviewer's feedback and will make sure that these points are more explicitly detailed in the camera-ready versions if accepted.", "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": "kRqVUHltVu", "reviewer": "Reviewer_6hk5", "summary": "This paper addresses the issue of inadequate modeling of graph equivariance in existing spectral GNNs due to nonlinear operations. The authors investigate the concept of domain translation in graph space as functional translations, drawing from the convolutional operations defined on images. Based on a series of in-depth analyses, they propose nonlinear spectral filters (NLSFs) that are fully equivariant to graph functional shifts and demonstrate universal approximation capabilities.", "questions": "see weaknesses", "limitations": "yes, the authors discuss the limitations in Section 6", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The research problem is highly valuable, and the ideas presented are novel.\n2. The theoretical analysis is rigorous, thoroughly supporting the arguments and solutions proposed in the paper. It reflects the authors' deep understanding and insight in the field.\n2. Notable experimental improvements in classification tasks.", "weaknesses": "1. The paper is missing important spectral GNN models such as [1,2,3,4].\n2. There is a lack of discussion on equivariant GNNs, such as [5,6,7,8,9,10,11,12]. While the focus is on spectral GNNs, it is also essential to discuss works in the spatial GNN domain, especially given that the paper’s title starts with \"Equivariant Machine Learning on Graphs.\" Positioning your work within the broader GNN field can further elucidate the significance and unique advantages of your contributions.\n3. The experiments are somewhat lacking in comprehensiveness. While you have demonstrated the effectiveness of your proposed model in common node and graph classification tasks, your core contribution is enhancing equivariant representation learning in spectral GNNs. I suggest adding experiments that specifically show how the improved performance is due to enhanced equivariant learning, such as graph isomorphism tests.\n\n[1] How powerful are spectral graph neural networks\n\n[2] Bernnet: Learning arbitrary graph spectral filters via bernstein approximation\n\n[3] Specformer: Spectral graph neural networks meet transformers\n\n[4] Graph neural networks with learnable and optimal polynomial bases\n\n[5] Universal Invariant and Equivariant Graph Neural Networks\n\n[6] E(n) Equivariant Graph Neural Networks\n\n[7] On the Generalization of Equivariant Graph Neural Networks\n\n[8] Expressive Power of Invariant and Equivariant Graph Neural Networks\n\n[9] Approximately Equivariant Graph Networks\n\n[10] Equivariant Polynomials for Graph Neural Networks\n\n[11] Graph Neural Networks for Learning Equivariant Representations of Neural Networks\n\n[12] Sign and Basis Invariant Networks for Spectral Graph Representation Learning", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful and constructive review.\n\n>**Additional Comparison with Spectral GNNs:**\n\nThank you for the comment.\n\nFollowing the reviewer's request, we included JacobiConv, BernNet, Specformer, and OptBasisGNN in our node classification experiment.\n\nMoreover, motivated by other comments about heterophilic graphs, we extended NLSFs to include an additional filter capturing the band that contains the remaining non-leading eigenvectors, which we call rem-NLSFs. For Index NLSFs, we incorporate $\\mathbf{I} - \\sum_ {j=1}^J \\mathbf{P}_ j$, and for Value NLSFs, we add the $\\mathbf{I} - \\sum_ {j=1}^K g_ j(\\mathbf{\\Delta})$. This alleviates the loss of information due to projecting to the low-frequency bands. All of our proofs are trivially extended to rem-NLSFs. If the reviewer would like to see the new proofs, which are almost identical to the old ones, we can send an anonymous PDF file to the AC according to the regulations of NeurIPS.\n\nTable 2 of the global response PDF presents the node classification accuracy for these methods and rem-NLSFs. We see that rem-NLSFs outperform the other models on the Cora, Citeseer, and Chameleon datasets. For the Pubmed and Actor datasets, rem-NLSFs achieve the second-best results. Adding the orthogonal component alleviates the loss of information due to projecting to the low-frequency bands and, therefore, further improves the empirical results. The new experiments will be included in the camera-ready version if accepted.\n\n>**Additional Discussion on Equivariant GNNs:**\n\nThank you for this feedback. \n    \nWhile Section 2 already shortly discusses the background of Equivariant GNNs, we add an extended review in the appendix to include more works:\n\nIn recent developments on equivariant GNN model design, Satorras et al. (2021) introduced a new model for learning graph neural networks (GNNs) that are equivariant to rotations, translations, reflections, and permutations, Huang et al. (2023) developed an approach for designing GNNs that respect approximate automorphism symmetries. Additionally, Lim et al. (2023) presented SignNet and BasisNet, which process eigenvectors invariant to sign and eigenspaces. Different from these methods, Kofinas et al. (2024) proposed representing neural networks as computational graphs of parameters. In a more theoretically oriented work, Keriven et al. (2019) extended the Stone-Weierstrass theorem for the algebra of real-valued functions to the equivariant case, and Karczewski et al. (2024) established a generalization bound for E(n)-Equivariant GNNs.  Azizian et al. (2021) explored the expressive power of message-passing GNNs, linear GNNs, and folklore GNNs, for both their invariant and equivariant versions. Additionally, Puny et al. (2023) introduced an alternative expressive power hierarchy to evaluate GNNs based on their ability to approximate equivariant graph polynomials. \n\nWe will also include a more detailed comparison to methods that consider graph automorphisms as symmetries, like Huang et al. (2023). Let us explain the main idea of the comparison. The goal is to illustrate that functional translations are more stable than hard symmetries of the graph, namely, graph automorphisms (isomorphisms from the graph to itself). Automorphisms are another analog to translations on general graphs, which competes with our notion of functional shifts. Consider as an example the standard 2D grid on the torus. The automorphisms of the grid include all translations. However, this notion of hard symmetry is very sensitive to graph perturbations. If one adds or deletes even one edge in the graph, the automorphism group becomes much smaller and does not contain the translations anymore. On the other hand, we claim that functional shifts are not so sensitive. To visualize this, we conducted a toy experiment that illustrates that graph functional shifts are stable to graph perturbations. Specifically, we show that standard translations can be approximated by a graph functional shift on a perturbed grid (adding Gaussian noise to the edge weights), optimizing the coefficients of the functional shift so the operator is as close as possible to the classical shift. See Figure 2 in the PDF. We then train the NLSFs on a perturbed grid to do MNIST classification, following the setup in [1,2,3]. We compare the NLSF on the clean grid to the NLSF on the perturbed grid. Table 3 presents the performance of the NLSF, which is almost unaffected by the perturbation, which demonstrates that NLSFs on the perturbed grid can roughly implement CNN-like architectures (translation equivariant functions).\n\n[1] Defferrard et al. (2016). Convolutional neural networks on graphs with fast localized spectral filtering.\n\n[2] Monti et al. (2017). Geometric deep learning on graphs and manifolds using mixture model CNNs.\n\n[3] Levie et al. (2018). Cayleynets: Graph convolutional neural networks with complex rational spectral filters.\n\n>**Experiments Highlighting the Benefits of Equivariant Learning:**\n\nThanks for this comment. \n    \nIt is important to note that the connection between graph isomorphism testing and GNNs is primarily theoretical. In practical applications, spectral GNNs are not commonly utilized for direct isomorphism testing to the best of our knowledge. We would appreciate it if the reviewer could provide any specific work they are referring to for further clarification.\n\nFollowing the reviewer's suggestion, as explained above, we added a new toy example demonstrating how a standard translation can be estimated by a graph functional shift on a perturbed grid, which shows the robustness of functional shift symmetries. We then train an NLSF MNIST classifier, which illustrates that NLSFs can roughly implement CNN-like architectures, also on a perturbed grid. \n\nThank you again for your valuable feedback. We will include these examples in the camera-ready version if accepted.", "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:
# General Response to All the Reviewers

We thank the reviewers for their valuable input and criticism. We highlight the main revisions to the paper below.

>**Enhancing NLSFs with Orthogonal Complements:**

Our original method projected the signal's information to the leading (low) frequencies. This projection can lose important information, especially in the context of heterogeneous graphs, which require high frequencies to represent the target/label. To mitigate this limitation, we slightly extended NLSFs to include an additional high-pass filter, denoting the new method **rem-NLSFs**. For Index NLSFs we add $\mathbf{I} - \sum_ {j=1}^J \mathbf{P}_ j$, and for Value NLSFs we add $\mathbf{I} - \sum_ {j=1}^K g_ j(\mathbf{\Delta})$. Now, the full spectral range of the signal is captured by the NLSF.

Table 2 presents classification performance on benchmark graphs, where rem-NLSFs improve performance. We will motivate this construction in our paper from the perspective of heterogeneous graphs.

The theory, and all of our proofs, trivially extend to rem-NLSF. If the reviewers would like to see the new version of the proofs, which are almost identical to the old proofs, we would be happy to send an anonymous PDF file to the AC according to the NeurIPS regulations.

>**Illustrating Functional Translations:**

Some reviewers asked for an additional discussion and illustrations focused on helping the reader to better grasp the new notions of symmetry.

We will start by showing that on the standard grid (on the 2D torus) with central difference GSO, the standard Fourier basis is the eigenbasis of the Laplacian. We will then show that any domain shift on the grid, when applied on signals, is equivalent to modulation in the frequency domain. Hence, domain shifts commute with the Laplacian (both of them are diagonal matrices in the frequency domain). Functional shifts are defined by adopting this property as a definition. We call *any* unitary operator that commutes with Laplacian a graph functional shift. For the grid, these include exactly the operators that multiply each frequency by a complex number of unit modulus. 

Fig. 1  (in the global response PDF) presents a comparison of a classical and a functional translation of a Gaussian signal. While classical translation shifts the whole signal uniformly, functional translations can shift different frequency bands at different speeds. This illustrates that functional symmetries are more rich than domain symmetries. 

In addition, we add another experiment showing that functional translations are much more stable than hard symmetries of the graph, namely, graph automorphisms (isomorphisms from the graph to itself).  Autonorpisms are another analogue to translations on general graphs, which competes with our notion of functional shifts. The relevant experiments are in Fig.2 and Table 3 in the PDF. See the response to Reviewer 6hk5 for more details.

These examples will be incorporated into the camera-ready version if accepted.

>**Expressivity in the Context of WL:**

We will add a discussion about the relation between our notion of expressivity and the traditional WL hierarchy. See the rebuttal of Reviewer fGo4 for more details.

>**Efficiency of Eigendecomposition:**
 
Some reviewers were concerned about the efficiency of eigendecomposition. We would like to point out that computing the leading eigenvectors of sparse graphs is as efficient as message-passing networks. In Section 4.1, we discussed our method's complexity and efficiency. The Lanczos algorithm estimates the leading $J$ eigenvectors in $O(JE)$ operations per iteration and converges quickly, making it as efficient as a message-passing neural network with $J$-dimensional features.

>**Scalability to Large-Scale Datasets:**

To demonstrate the scalability of our method, we conduct additional tests on five large heterophilic graphs: Penn94, Pokec, Genius, Twitch-Gamers, and Wiki datasets from Lim et al. (2021). The experimental setup is in line with previous work by Chien et al. (2021), Lim et al. (2021), and He et al. (2022). We use the same setup for our NLSFs as reported in Appendix B. Table 1 (in the global response PDF) presents the classification accuracy. We see that rem-NLSFs outperform the competing methods on the  Penn94, Pokec, Genius, and Wiki datasets. For the Twitch-Gamers dataset, rem-NLSFs yield the second-best results. Our additional experiments show that our method could indeed scale to handle large-scale graphs effectively. We will include these experiments in the camera-ready version if accepted.

>**Additional Comparison with Spectral GNNs:**

In response to the feedback about missing important spectral GNNs, we included JacobiConv, BernNet, Specformer, and OptBasisGNN in our node classification experiment following the reviewer's request. 

Table 2 of the global response PDF presents the node classification accuracy for these methods and rem-NLSFs. We see that rem-NLSFs outperform the other models on the Cora, Citeseer, and Chameleon datasets. For the Pubmed and Actor datasets, rem-NLSFs achieve the second-best results. Adding the orthogonal component alleviates the loss of information due to projecting to the low-frequency bands and, therefore, further improves the empirical results. The new experiments will be included in the camera-ready version if accepted.

Meta-review: The paper introduces Nonlinear Spectrum Filters (NLSFs), a novel filter operation for Graph Neural Networks (GNNs) that is equivariant to functional symmetries. The authors propose node-level, graph-level, and pooling non-linear spectral filters, demonstrating that these filters outperform standard convolutional GNNs in both semi-supervised node classification and graph classification tasks. The paper is well-supported by rigorous theoretical analysis and extensive empirical validation across various benchmarks.

While there were minor concerns about the mathematical density of the paper, which may limit accessibility, the reviewers acknowledged that the authors effectively addressed the most relevant concerns. There was limited discussion among reviewers, with the primary concern from the "borderline accept" reviewer focusing on the scalability of the method. The authors addressed this by providing results on larger datasets.

Given the overall positive feedback from the reviewers, particularly regarding the paper’s novelty, theoretical rigor, and comprehensive experimental validation, I recommend accepting the paper.
Decision: Accept (poster)