Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum
Authors: Snir Hordan
Maya Bechler-Speicher
Gur Lifshitz
Nadav Dym
Venue: NeurIPS 2025 spotlight ()
Keywords: spectral invariants
graph spectra
simple spectrum
expressiveness
expressivity
GNN
Spectral GNN
Primary area: deep_learning
TL;DR: We prove the incompleteness of Spectrally-enhanced GNNs on graphs with a simple spectrum.

Abstract: Spectral features are widely incorporated within Graph Neural Networks (GNNs) to improve their expressive power, or their ability to distinguish among non-isomorphic graphs. One popular example is the usage of graph Laplacian eigenvectors for positional encoding in MPNNs and Graph Transformers. The expressive power of such Spectrally-enhanced GNNs (SGNNs) is usually evaluated via the $k$-WL graph isomorphism test hierarchy and homomorphism counting. Yet, these frameworks align poorly with the graph spectra, yielding limited insight into SGNNs' expressive power. In this paper, we leverage a well-studied paradigm of classifying graphs by their largest eigenvalue multiplicity to introduce an expressivity hierarchy for SGNNs. We then prove that many SGNNs are incomplete even on graphs with distinct eigenvalues. To mitigate this deficiency, we adapt rotation equivariant neural networks to the graph spectra setting, yielding equiEPNN, a novel SGNN that provably improves upon contemporary SGNNs' expressivity on simple spectrum graphs. We then demonstrate that equiEPNN achieves perfect eigenvector canonicalization on ZINC, and performs favorably on image classification on MNIST-Superpixel and graph property regression on ZINC, compared to leading spectral methods.

Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum
Snir Hordan
Maya Bechler-Speicher Meta
Faculty of Mathematics
Technion Israel Institute of Technology
Gur Lifshitz
Nadav Dym
Blavatnik School of Computer Science Tel-Aviv University
Faculty of Mathematics
Technion Israel Institute of Technology
Abstract
Spectral features widely incorporated within Graph Neural Networks (GNNs) to improve their expressive power, or their ability to distinguish among non- isomorphic graphs. One popular example is the usage of graph Laplacian eigenvec- tors for positional encoding in MPNNs and Graph Transformers. The expressive power of such spectrally-enhancee k-WL. graph isomorphism test hierarchy and homomorphism counting. Yet, these frameworks align poorly with the graph spectra, yielding limited insight into SGNNs' expressive power. In this paper, we leverage well-studied paradigm of classifying graphs by their largest eigenvalue multiplicity to introduce an expres- sivity hierarchy for SGNNs. We then prove that many SGNNs are incomplete even on graphs with distinct eigenvalues. To mitigate this deficiency, we adapt rotation equivariant neural networks to the graph spectra setting, yielding equiEPNN, novel SGNN that provably improves upon contemporary SGNNs' expressivity on simple spectrum graphs. We then demonstrate that equiEPNN achieves perfect eigenvector canonicalization on ZINC, and performs favorably on image classifica- tion MNIST-Superpixe and graph property regression ZINC, compared leading spectral methods.
GNNs (SGNNs) usually evaluated via the
Introduction
Graph Neural Networks (GNNs) have become a ubiquitous paradigm for learning on graph-structured data. The core principle of GNNs is to maintain representation of each graph vertex and leverage the graph structure to iteratively refine each representation by its vertex's 's graph neighborhood [41]. To enhance the purview of the vertex's neighborhood, it is common incorporate spectral features, such as Random Walk matrices, positional encoding. and graph distances, into the refinement operation of GNNs 9 45 51). Such GNNs, which systematically incorporate spectral features within their representation refinement procedure, or Spectrally-enhancel GNNs (5GNNs))5)) have gained significant traction in the graph learning community, due their reasonable complexity and empirical
benefits 188 53 52 13).
Understanding the expressive power of GNNs provides researchers with a framework for comparing different models and identifying their deficiencies, often leading to improvements [15] 32 B5 49]. These frameworks ought to characterize which graphs the GNN distinguish among, based on the GNNs' inner workings. For instance, the Weisfeiler-Lemaa (WL) test, which maintains and refines vertex representations similarly to Message Passing Neural Networks, subclass of GNNs, completely determines which graphs these models can distinguish among
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

1-WL
EPNN
equiEPNN
Figure 1: Hierarchy of 1-WL test variants. The arrows with J indicate strict inclusion relationships, meaning each variant can distinguish all graphs that the previous one can, plus additional graphs. Standard 1-WL is the least discriminative, while equiEPNN achieves the highest discriminative power, by incorporating both spectral invariant and equivariant refinement.
To study the expressive power of SGNNs, recent papers (2
(22 K proposed spectrally enhanced GNN, called Eigenspace Projection GNN (EPNN), which generalizes many popular spectral graph neural networks, and analyze expressivity via WL tests and homomorphism counting. This comparison is valuable in comparing the expressivity of SGNNs to that of their combinatorial GNN counterparts. Yet, this analysis does not yield insight into the role of the graph spectra the distinguishing ability of these GNNs.
To address this gap, we propose analyzing the expressive power of SGNNs via Spectral Graph Theory, and in particular via the maximal eigenvalue multiplicity of graph. As isomorphism of graphs be determined in polynomial time, with the complexity
with bounded eigenvalue multiplicity depending exponentially on the eigenvalue multiplicity 22, this notion imposes a natural hierarchical classification of graphs, and SGNNs can potentially be complete on these graph classes, making this hierarchy a viable method for assessing their expressive power.
Our analysis centers around the expressivity of EPNN on graphs with distinct eigenvalues. This model is at least as expressive as many commonly used SGNNs [52), making an upper bound on the expressivity of EPNN applicable these models. Surprisingly. on the class of graphs with distinct eigenvalues. On the positive side, EPNN achieves completeness on simple spectrum graphs whose eigenvectors exhibit certain sparsity patterns. Based on these theoretical insights, we propose equiEPNN, inspired by equivariant neural networks for point clouds, which attains provably improved expressivity on graphs with distinct eigenvalues.
find that EPNN is incomplete
Our main contributions are summarized as follows:
1. We prove the incompleteness of EPNN (in Subsection 3.2 on graphs with a simple spectrum.
2. We formulate a guarantee on the completeness of EPNN on graphs with a simple spectrum based on sparsity patterns of the eigenvectors.
3. We introduce equiEPNN (in Section 3.3 modified EPNN variant, which integrates Euclidean message passing into the feature refinement procedure.
4. We benchmark equiEPNN on the ZINC and MNIST-Superpixel datasets, yielding favor- able performance in comparison with popular spectral methods. Furthermore, equiEPNN performs perfect eigenvector canonicalization on the ZINC dataset.
Related work
2.1 Spectral invariant GNNs
An enhancement to MPNNs and Transformer-basee models is incorporate spectral distances such as Random Walk, resistance, and shortest-pai -ath distances within the message passing operation 26 50 33 [2]. Zhang et al. [52] compare among spectral GNNs and the WL hierarchy by proving EPNN is strictly more powerful than 1-WL yet strictly less powerful than 3- WL. Despite the important result that WL strictly bounds the expressive power of EPNN, the large expressivity gap between 1- and 3-WL makes this determination difficult to conceptualize. Building on this work, Gai et al.
13 have characterized the expressive power of EPNN via graph homomorphism counting, showing spectral invariant GNNs can homomorphism-coum providing deeper understanding EPNN's expressive power, it remains hard to conceptualize and propose more expressive models based on it.
class of specific tree-like graphs. Despite

---

2.2 Spectral canonicalization methods
The cigenvectors of a graph are used as positional encoding to improve the expressive power of message-pasaeee passing and positional encoding for Transformer [38 21 31 based models. Yet, positional encoding has an inherent ambiguity problem. An eigenvector corresponding to a unique eigenvalue can be represented as itself or its negation [3]. Canonicalization methods [30, 29 are used to address the ambiguity problems of eigenvectors, by choosing a unique representative for each eigenvector.
Ma et al. [29] have uncovered an inherent limitation of canonicalization methods that process each eigenspace separately, which is that they cannot canonicalize eigenvectors with nontrivial self- symmetries. These models process each eigenbasis independently to obtain an orthogonal invariant and permotation-equuiaariant feature, and then these features for downstream applications. Notable examples include SignNet and BasisNet [27). MAP [29] and OAP [30]. Ma et al. [30] have shown that these methods lose information when canonicalizing eigenvectors with self-symmetriess, proving that the popular spectral invariant models SignNet and BasisNet are incomplete. In section 3.2 we
provide a canonicalization scheme that bypasses this issue, and while not provable complete on all
eigenvectors, empirically it canonicalizes all eigenvectors corresponding to distinct eigenvalues, in the ZINC 19 dataset.
2.3 Expressivity on simple spectrum graphs
An early study on the connection between GNNs and spectral features of the underlying graph studied the expressive power of CGNs [7]. They have proven that linear graph convolutional neural networks (GCNs) can map graph signal any chosen target vector, if the graph has distinct eigenvalues. Yet, this graph signal is sampled randomly and thus is not equivariant to permutations of the graph nodes, which may lead to degraded generalization, see Rechler-Speichee
al. [5].
For more related work see Appendix
3 Problem statement
3.1 Spectral graph decomposition
Graphs are typically represented by matrix A E R"x", where the -th entry of the matrix encodes the relationship between node i and j. This matrix could be the adjacency matrix, the normalized or un no-nommallzed graph Laplacian, have some underlying geometry.
distance Gram Matrix where the graph nodes
A crucial principle in the design of graph neural networks is the notion of permutation invariance. Since graph nodes are not endowed with an intrinsic order, we would like to think of a matrix A and its conjugation P PAPl by permutation matrix P E Sn, being equivalent. Graph neural networks respect this invariance constraint and produce a permutation-invarian
function f satisfying f(A) ( S(PAP?). One popular method to design these functions exploits the eigendecomposition of the matrix A.
In the general case, we assume that A has an eigenbasis (()),... (n)) of vectors of norm one, which corresponds to real eigenvalues ..,..., An This assumption holds when in the typical case where A is a symmetric matrix (e.g., adjacency and Laplacian matrices), and also often holds in other settings (e.g., Random Walk matrix). This endows an alternative representation of the matrix A with its own symmetries. Firstly. we note that each vector Py(9) will be an eigenvector of PAP with the same eigenvalue Xy- Secondly, if ((9)) is an eigenvector of norm one, then is -7(9), When the eigenvalues of f are pairwise distinct, then these are all the relevant ambiguities. This is referred to as the simple spectrum case. In the case of eigenbasis of dimension kt the eigendecomposition ambiguity is defined by orthogonal transformations in Og. In this paper, we will focus on the simple spectrum case. In this case, define sign-invariant functions as follows
Definition (Sign Invariant functions). For fixed natural n and K S n. denote
K simple {(V,A) ga
R >>>>> > AK).
3

---

We say that F: VK
simple
+
R is sign invariant if
F(V,))= = F(PVS VP Sn, S
We note that this definition, V represents a n x matrix whose columns represent the first K o(K) of A, and the notation S E {-1,1}* means that S is a diagonal matrix whose diagonal is a vector in {-1,
cigenvectors v(1), , ,
The notion of sign invariant function was first introduced in 22 and was later discussed in 29 0 }}, such that for all parameters 9 the function fo is sign invariant. To understand the expressiveness of these models, formally define the notion of completeness on simple spectrum graphs.
These papers discuss a collection of parametric functions J
Definition 2 (Sign Invariant Separation). For K S n, denote a collection of sign invariant simple and let 'D be subset of Vk simple' We say that F is complete on 'D for any com-isomopphic pair (V, X) and (U, i)) in D, there exists function f E EF such that
functions defined on vK
f(V, + f(U,m)
Ideally, we would like F to be complete on all of the domain VK applying it to eigendecompostions of graphs with simple spectrum, we will obtain models which can separate all graphs with simple spectrum, up to permutation equivalence. The goal of this paper is to understand whether existing sign-invariant functions are complete.
simple' If J is complete, then by
3.2 EPNN
We will focus on a large family of sign invariant functions named Eigenspuce Projection GNNs (EPNN). This family of functions, introduced in Zhang et al. [52], was shown to generalize many
spectral invariant methods such as Random Walk, resistance, and shortest-path distances (26 50 33
12]. This method is based on message passing like mechanism, where the spectral information is encoded by using the projection onto eigenspaces as edge features. In the simple spectrum case, this method can be formulated follows:
For given eigendecompositionn (V,)) E simples we we initialize coloring for each 'node" e [n]
DK
by
4 (0) = Vi
where V; A Vi,: is the K dimensional vector (1. (K) obtained by sampling all eigen- vectors at the i-th node, and @ denotes elementwise multiplication. Importantly, this initialization is sign-invariant: while the global sign of each eigenvector is ambiguous, the product of two elements of the same eigenvector is not.
We next iteratively refine the node features via the update rule:
(t+1) UPDATE (n.9) x, ( VI VI kovlli- h
Here and throughout } denote multisets (multiplicities are allowed) and the multiset notation implies that (PDATE()) is required to be invariant to the order of the elements in the multiset.
Finally, we apply global pooling operation obtain final permutation invariant representation
Ngllhhal READOUT(())) ( ii= 1 1......
n3)
Once UPDATE and READOUT functions are determined, this procedure determines a function f(V, X) Igglbaal which is sign-invariant as in Definition
The collection of all such functions obtained by all possible choices of (PDATE and READOUT functions is denoted by FEPNN.
3.3 Equivariant EPNN
In 13 the authors suggest methods based on higher order WI. tests to boost the expressive power of spectral message passing neural networks. The complexity of these methods is considerably higher

---

than EPNN. In contrast, we will now suggest method for increasing the expressive power of EPNN without significantly changing model complexity.
Our suggestions are based on constructions from neural networks for geometric point clouds. These neural networks operate point clouds X E Raad (where in many applications d = and each of the n points in I represents a geometric coordinate. Models for such data are required to be invariant (or equivariant) to both permutations in S, and rotations in Odd). This equivariant structure is similar to, but not identical to, the situation we have for graph eigecomposition: under the simple spectrum assumption, the symmetry transformations we are interested in a single global permutation, and K sign changes, which are rotations in O(1)*. In the more general setting, we will have a single permutation and multiple rotations, whose dimension is determined by the multiplicity of each eigenvalue.
Via this analogy. we can look spectral models for graphs from the perspective of point cloud networks. From this perspective, EPNN resembles geometric invariant networks, such as Schnet [42), which are based on simple invariant features. In contrast, [20] and (44) showed that, at least for point clouds, expressivity can be increased by recursively updating rotation equivariant (in our scenario,
sign equívariant) feature Uy
(1) in parallel with the invariant feature n, Inspired by these observations,
we suggest the following sign equivariant feature refinement procedure:
We use the same initialization h/ as in Equation ! and we initialize the equivariant feature e/ to
(()) Vi. We then iteratively update these two features via
(++1) UPDATE (1.1) (,, 00 = I.....n]) 1/
(++1) Us
(1)
UPDATE (1.2) 1 of o 10))
J=1
where (PDATE is a multiset function, and UPDATE maps its input to R K so that the elementwise product in the equation above is well defined.
After running this procedure for iterations, we obtain an invariant global feature Iygobal by aggregating the invariant node features h1 (T) using READOUT function, as in (3). This gives
sign invariant function f(V, liglobal- We name the class of all functions obtained by running this procedure with all different choices of update and readout functions equiEPNN.
We note that can obtain EPNN models by setting UPDATE to be the constant mapping to the zero vector. Accordingly, Foqui is at least as expressive as EPNN. In Section 4.4 we will show that it is strictly more expressive.
4 On the incompleteness of spectral graph neural networks
In this section, we analyze the expressive power of EPNN and equiEPNN on graphs with a simple spectrum. We first provide a counterexample to prove its incompleteness of EPNN on simple spectrum graphs. We then show that equiEPNN can separate the counterexample, thus proving it is strictly more expressive than EPNN. Next we provide a subset of y Finally, we discuss how our results imply the incompleteness of popular spectral GNNs even the simple spectrum case.
simple on which EPNN is complete.
4.1 EPNN is incomplete
We first introduce pair of non-isomorphic eigendecompositions, (V, and (U, in VK EPNN cannot distinguish, that is, it assigns them the same final feature after any number of refinement steps. In this construction both examples. To define V, U, we denote
simple which
12, K = 6, and fix the same choice of distinct eigenvalues X for
1)
(11).
23 = (=:). 02 = 0
20 =
21
1
22 =
-0)
5

---

and note that 2o..... are the four elements of the abelian group 1-1,13 Using these, we define U, V via
50
21
22
23
02
02
02
02
20
21
22
23
U
20
22
23
22
23
02
02
02
02
02
02
02
02
20
21
23
2/2
20
22
21
23
20
21
22
23
02
02
02
02
20
21
22
23
VT
20
22
23
20
21
22
23
02
02
02
02
02
02
02
21
20
22
23
22
20
23
21
We now show that U. are not isomorphic and cannot be separated by EPNN:
Theorem 1. (Incompletenesss of EPNN The following statements hold:
1. U and V are not isomorphic under the group action of S12 x {-1,1}
2. EPNN cannot separate U and V after any number of iterations.
3. U and V have no non-trivial automorphisms.
Therefore, EPNN is incomplete simple spectrum graphs.
Proof Idea. To show U, V are not isomorphic, we note that for any pair of permutation-sign matrices taking U V, the first four columns of U must be mapped the first four columns of VT. The same is true for columns sign matrix mapping them from U to V will be of the form diag(z, 2, 2') for 2, [-1,+11 The same argument for columns 5 - and 9 - 12 gives sign patterns of the form [iiag(='=2.0 21 =) and diag(2, 2', 22 =), respectively. But there simultaneously.
8 and
12. Considering the first four columns, we see that any
sign pattern satisfying these three constraints
We now explain the lack of separation of EPNN. We refer to the multiset of the multiplications of column with all the other columns, as the column i's purview. the initial step, the purview of each column in the first 4-column block in VL and U is identical, as the first 4 columns exhibit group structure with the multiplication operation. Thus, the hidden states the first 4 indices of U and V will be identical. By similar arguments, this holds for the remaining two blocks. Thus, after a refinement step, the nodes in each block cannot distinguish among those from other blocks, both in U and VT_ Therefore, additional refinement procedures maintain identical representations for members of each index 'block' and corresponding blocks in U and VT, This implies EPNN cannot separate U and V.
full proof of the theorem is provided the Appendix.
Remark: In many cases we are interested in eigenvalue decompositions of symmetric matrices, in which case the columns V, U (the rows of VT, UT) should orthonormal. While our V, U do not satisfy this condition, in the Appendix we show how they can be enlarged yield counterexample that has the same properties, and does have orthonormal columns.
4.2 When is EPNN complete?
The counterexample proves that there is an inherent limit to the expressive power of contemporary spectral invariant networks. We note that in this example U, V had significant number of zero entries. We now show that when U, V each have at least one row without any zeros, EPNN will be complete (in particular, this condition always holds when the matrices U, have less than n zero entries):
Theorem 2 (EPNN Can Distinguish Dense Graphs with Distinct Figenvalues). Let D S Vk denote the set of (V, X) where V has a row without zero entries. Then EPNN is complete on D.
simple
Proof. By assumption, index i exists such that the i-th of V has zeros. The hidden state i,()) after a signal iteration of EPNN (see (2) can encode the eigenvalues X, the squared values of each coordinate of V,, and the multiset of pairwise products V, O V,, as

---

(V. e [
To recover V from h. up symmetries, we can fix the sign ambiguity by choosing all coordinates of Vú to be positive. We can then recover the remaining Vj from the multiset Equation
This uncovers the inner workings of EPNN in processing simple spectrum graphs. Essentially, each entry can be normalized to represent a group element in ((1), which acts as a local frame of reference, see [10] for more background, allowing to reconstruct the cigenvectors up to sign symmetries.
4.3 Unique node identification via EPNN
well-known mechanism for circumventing the limited expressive power of GNNs is by injecting unique node identifiers (IDs), which break the symmetries that hinder GNNs' separation ability Popular approaches include random node initialization [5] and combinatorial methods 8 yet they are either limited by their discontinuity or break permutation equivariance. A natural question is whether the node features from EPNN are unique after finitely many iterations? If so, we have attained node IDs that do not break equivariance and change continuously with the eigendecomposition, alleviating the deficiencies of widely-used methods. We answer this question in the affirmative, provided the eigenvectors adhere to a sparsity pattern.
28
Theorem 3. (EPNN for Unique Node Identifiers) Let D V simple denote the set of (V, X) where V has no automorphisms, and has at most one zero per eigenvector. Then, one iteration of EPNN with injective UPDATE and READOUT functions assigns a unique identifier to each hidden node feature.
Proof. By contradiction, assume that there exist distinct indices i, such that h = n By the definition of EPNN, we have that
(V: ViJb== (V, ViJk=z and Vi V, =V=v,0V
(5)
We deduce for the second equality that |V,0) |V, for all coordinates q 1, 1,..., ................................ K. If for some q we had v:(0) then also vy(0) 0, in contradiction to the assumption that the q-th eigenvector has at most one zero entry. Thus all entries of Vú and Vy are non-zero.
Next, we deduce from Equation 5 and the fact that |V.00] = |V > 0 for all g, that
{(s)
(0) ((9)) K
9= 37
{(s) v. x 1
(9)
where (0) { and is defined as |y/li
vi and (a) is defined analogously. This means that there s)
exists a permutation which swaps i with j. such that 5 s q = 1,....K, K. Equivalently,
(a) v(1) for all k l...., n and a(k)
PVS = VS2 PVS,S2 =V
where S1 and S2 are diagonal matrices with (9)) and 8 (4) respectively, on the diagonals, and P is the permutation matrix corresponding to a. Since P swaps i with j. this is non-trivial automorphism. in contradiction to the assumption. Thus (n))) # n.)) required.
4.4 equiEPNN is strictly more expressive than EPNN
We show that equiEPNN is strictly more powerful than EPNN, as separates the pair U and V from Subsection 4.1 which EPNN cannot separate:
Corollary 1. equiEPNN (see Section 3.3 can separate U and V after 2 iterations. Thus equiEPNN strictly stronger than EPNN.
Proof Idea. We show that after a single iteration, the equivariant update step can yield new matrices U.)), V -= = 1 which have no zeros. From Theorem 2 we know that a single iteration of EPNN, and hence also equiEPNN, complete for such U?!), V and thus two iterations of equiEPNN are sufficient for separation.

---

While equiEPNN is stronger than EPNN, the following result (proven in the appendix) shows that equiEPNN is also incomplete over simple spectrum graphs:
Theorem 4. (Incompleteness of Equivariant EPNN) There exist X,Y Y E R1666 such that the following statements hold:
1. and Y are not isomorphic under the group action of Sis {-1,136.
2. Equivariant EPNN cannot separate X and Y after any number of iterations.
Therefore, Equivariant EPNN is incomplete on simple spectrum graphs.
In the appendix we also explain how this counterexample can be extended so that X, Y are orthogonal matrices which thus can form a full eigendecomposition of a real symmetric matrix.
4.5 Incompleteness of spectral GNNs
Theorem proves that EPNN is incomplete on graphs with a simple spectrum. This spectral isomorphism test upper bounds the expressive power of many popular distance-based GNNs, which incorporate graph distances as edge features, such as Random Walk, PageRank, shortest path, or
resistance distances 500 26
45 51. Therefore, an immediate corollary of Theorem 1 follows:
Corollary Graphormer-GD (50), PRD-WL (26), DiffWWir M. and Random- Walk based CN 511 are incomplete over graphs with a simple spectrum.
In addition to this result, in the appendix we prove that the model proposed by Zhou et al. 53 is not universal on simple spectrum graphs.
Proposition 3. Vanilla OGE-Aug
53 is incomplete over graphs with a simple spectrum.
5 Experiments
Our goal in the experiments section is twofold: (a) statistically evaluate the validity of our bounded eigenmultiplicity approach for measuring expressivity and (b) empirically exemplify the utility of equiEPNN [ To meet the first goal, statistically analyze the eigenvalue multiplicity in real- world datasets, and the number of non-zero entries in the eigenvectors, to compare these with our theoretical conditions for EPNN completeness. We find that while the sparsity conditions for EPNN completeness are satisfied on some real-world datasets (MNIST-Superpixel) they are not satisfied on datasets with more intricate symmetries (ZINC). For the second goal, we evaluate the utility of the equivariant features derived from equiEPNN on the task of eigenvector canonicalization 30. Finally, we benchmark equiEPNN against leading spectral methods on the popular ZINC and MNIST-Superpixel datasets.
5.1 Dataset statistics
We surveyed several popular graph datasets and documented their graph spectral properties. The results are shown in T We find that the MNIST Superpixel 34 dataset is almost homogeneously composed of graphs with a simple spectrum, and we find that (96.9%) of the graphs in this dataset have a full row without zeros, implying that EPNN is complete on almost all graphs.
Other datasets, such as MUTAG, ENZYMES, PROTEINS and ZINC 19 36 contain a substantial amount of graphs with eigenvalue multiplicity and 3. Despite this, the number of eigenspaces of dimensions 2 and 3 is very low, averaging at around per graph. On datasets with highly symmetric graphs, such as ENZYMES and PROTEINS, the graphs do not meet the sparsity condition of Theorem 2. thus EPNN will not necessarily faithfully learn the graph structure. This exemplifies the need for more expressive models that are complete graphs with higher maximal eigenvalue multiplicity and sparse eigenvectors.
'Code is available at httpa/////ggtuuu..oo///o//l/l///

---

Table I: Graph Statistics Analysis Across Different Datasets (Eigenvalue Tolerance: 10-4)
Dataset Name
MUTAG
ENZYMES PROTEINS
MNIST
ZINC
Dataset Overview
Number of Graphs
188
600
1,113
60,000
10,000
Eigenvalue Characteristies
Graphs with Distinct Higenvalues
41.5% (78)
34.8% (2119)
22.1% (246)
99.9% (39,950)
40.7% (4,072)
Graphs with Multiplicity Eigenvalues
58.5% (110)
65.2% (391)
77.9% (867)
59.3% (5.928)
Gruphs with Multiplicity Eigenvalues
19.1% (36)
46.2% (277)
57.9% (644)
26.2% (2.617)
Avg. Number of Multiplicity 2 Higenvalues
0.74
1.01
1.24
1.282
Avg. Number Multiplicity Eigenvalues
0.26
0.71
1.105
Eigenvector Properties
Average Ratio of Zeros
1,67
4.28
6.39
2.52
Average Numher of /eros
31.13
172.93
817.20
23.16
61.04
Graphs Full Row
75.0% (141)
35.8% (215)
37.1% (413)
96.9% (58.077)
64.5% (6.447)
Gruphs with 5 Zero per Eigenvector
0.0% (0)
6.3%
5.0% (56)
20.2% (12.085)
4.3% (430)
Graphs with Total Zeros < Vertices Gruphs Meeting Any Condition
29.8% (56)
16.3% (98)
14.3% (159)
89.9% (53.873)
13.0% (1.295)
75.0% (141)
35.8% (215)
37.1% (413)
96.9% (58,077)
64.5% (6,447)
5.2 Eigenvector canonicalization
Positional encoding is cornerstone of graph learning using Transformer architectures, yet they suffer from the sign ambiguity problem 19. It can be resolved by eigenvector canonicalization. which involves choosing a unique representation current canonicalization methods is that they unable to canonicalize eigenvectors with nontrivial self-symmetries, often called uncanonicalizable eigenvectors (2
each eigenvector. Yet, an inherent limitation of
Table Uncanonicalizable Graph Eigenvectors in ZINC (Subset)
19 as percentage of total eigen-
vectors of eigen-space dimension 1.
Property
Percentage (%)
Sum to
11.15 %
Uncanonicalizable
10.93 %
equiEPNN output sum to 0 Uncanonicalizable after equiEPNN
0.0 %
0.0 %
To overcome this limitation, we devise method choose a canonical representation of the original cigenvectors via the equivariant output of equiEPNN. The only requirement is that each vector in the cquivariant output does sum O.
We test our hypothesis on a popular benchmark ZINC 19, and find that all the vectors in the equivariant output canonicalizable and sum to zero, in contrast to the vectors from the eigende- composition, where 10% of them are uncanonicalizabll.. Furthermore, we devise a way to choose a canonical representation of the original eigenvectors via the equivariant output and describe this in the Appendix. The results are shown in Table
Table 3: Results on ZINC and MNIST-Superpixel datasets. The values are the MSE for ZINC (Subset) and the accuracy for MNIST-Superpixel Edge features are not used even if they are available in the datasets. For ZINC, all models use node labels. For MNIST-SUperpixel, the model uses superpixel-intensee values and node degree as node features. Models have budget of 30K free parameters for ZINC and 35K for MNIST.
Category
Model
ZIAC
MNIST-Superpixe (Acc.1)
NN
MLP
0.5869 0.025
25.10%=0.11
MPNN
GCN
0.3322 + 0.010
52.80% 0.31
GAT
0.3977 + 0.007
82.73% 0.21
GIN
0.3044 + 0.010
75.23% 0.41
3-WL
PPGN
0.1589 1 0.007
90.04% + 0.54
Spectral
ChebNet
0.3569 0.012
92.08% 0.22
GNNML1
0.3140 0.015
84.21% + 1.75
equiEPNN (Ours)
0.2805 + 0.019
90.32 0.7

---

5.3 Benchmarks: ZINC and MNIST
We evaluated equiEPNN on the image classification task MNIST-SSpperpa 341 in which clustering of images is performed according to regions with similar pixel values, algorithm creates graph based on these regions, and each node assigned a region-induced feature. We compared equiEPNN to leading spectral methods, all with a comparable parameter budget of 35K (see Table 3). We observe that it outperforms PPGN [32], which has cubic complexity, and GNNMLI, which also processes the eigendecomposition of the graph. ChebNet outperforms all other methods, perhaps due to its handcrafted polynomial features.
We further evaluate equiEPNN via the standard regression task the ZINC dataset of molecular graphs (we also tested eigenvector canonicalization on this same dataset). ZINC (Subset) has 12000 graphs with average of 23.16 nodes per graph. We compare ourselves leading methods with the standard Ra 500K parameter budget and find that, out of the spectral methods, our method attains the best results, Table
Table Results on ZINC.
Method
Test Error (MAE J)
GIN
0.526 + 0.051
GraphSage
0.398 = 0.002
GCN
0.384 + 0.007
GCN
0.367 + 0.011
GatedGCN-PE
0,214 + 0.006
MPNN (sum)
0.145 + 0.007
PNA
0.142 + 0.010
GT
0.226 + 0.014
SAN
0.139 + 0.006
GraphormersI.m
0.122 + 0.006
MPNN
0.138 = 0.006
EPNN
0.103 + 0.006
equiEPNN (Ours)
0.099 + 0.001
Subgraph GNN
0.110 0.007
Local 2-GNN
0.069 + 0.001
6
Future Work
A key future goal is to devise spectral GNNs that achieve completeness on graphs with simple spectra, and higher eigenvalue multiplicities. One interesting direction is to use higher-order point cloud networks to process the eigenvectors (53]. We have shown that treating each eigenspace separate entity does not lead to universality (see Subsection 4.5). Thus, these high-order networks should process the eigenvectors as a single entity, but remain invariant only the sign and basis symmetries.
Acknowledgements N.D. and S.H. were supported by ISF grant 272/23.
References
[1] Adrián Amaiz-Rodrrguez, Ahmed Begga, Francisco Escolano, and Nuria M Oliver. DiffWire: Inductive Graph Rewiring via the Lovász Bound. In Proceedings of the First Learning on Graphs Conference, volume 198 of Proceedings of Machine Learning Research, PMLR, 2022.
[2] László Babai, D. Yu. Grigoryev, and David M. Mount. Isomorphism of graphs with bounded eigenvalue multiplicity. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, STOC '82, 1982. ISBN 0897910702.
[3] Guy Bar-Shalom, Yam Eitan, Fabrizio Frasca, and Haggai Maron. A flexible, equivariant framework for subgraph GNNs via graph products and graph coarsening. Advances Neural Information Processing Systems, volume 37, 2024.
10

---

[4] Maya Bechler- Bechler-Speicher, Ido Amos, Ran networks use graphs when they shouldn't. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, 2024.
and Amir Globerson. Graph neural
[5] Maya Bechler-Speicher, Moshe Eliasof, Carola-Bibiana Schönlieb, Ran Gilad- Bachrach, and Amir Globerson. Towards invariance to node identifiers in graph neural networks, 2025.
[6] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. International Conference on Learning Representations, 2022.
[7] Jan Böker, Ron Levie, Ningyuan Huang, Soledad Villar, and Christopher Morris. Fine- ene-grained expressivity of graph neural networks. In Advances in Neural Information Processing Systems, volume 36, 2023.
[8] Zehao Dong, Muhan Zhang, Philip R. O. Payne, Michael A. Province, Carlos Cruchaga, Tianyu Zhao, Fuhai Li, and Yixin Chen. Rethinking the power of graph canonization in graph representation learning with stability. In The Twelfth International Conference on Learning Representations, 2024.
[9] Vijay Prakash Dwivedi, Chaitanya K. Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43), 2023.
[10] Nadav Dym, Hannah Lawrence, and Jonathan W. Siegel. Equivariant frames and the impossi- bility of continuous canonicalization. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, 2024.
[11] Yam Eitan, Moshe Eliasof, Yoav Gelberg, Fabrizio Frasca, Guy Bar-Shalom, and Haggai Maron. On the expressive power of GNN derivatives, 2025.
[12] Or Feldman, Amit Boyarski, Shai Feldman, Dani Kogan, Avi Mendelson, and Chaim Baskin. Weisfeiler and leman go infinite: Spectral and combinatorial pre-colorings. arXiv preprint arXiv:2201. 13410, 2022.
[13] Jingchu Gai, Yiheng Du, Bohang Zhang, Haggai Maron, and Liwei Wang. Homomorphism expressivity of spectral invariant graph neural networks. In The Thirteenth International Conference Learning Representations, 2025.
[14] Vikas K. Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, 2020.
[15] Snir Hordan, Tal Amir, and Naday Dym. Weisfeiler leman for Euclidean equivariant machine learning. Proceedings of the 41st International Conference on Muchine Learning, volume 235 of Proceedings of Machine Learning Research, 2024.
[16] Snir Hordan, Tal Amir, Steven Gortler, and Nadav Dym. Complete neural networks for complete euclidean graphs. In Proceedingy of the Thirty-Eighth AAAI Conference Artificial Intelligence, volume 38, 2024.
[17] Ningyuan Huang and Soledad Villar. A short tutorial on the weisfeiler-lehman test and its variants. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2021.
[18) Yinan Huang, William Lu, Joshua Robinson, Yu Yang, Muhan Zhang, Stefanie Jegelka, and Pan Li. On the stability of expressive positional encodings for graphs. In The Twelfth International Conference on Learning Representations, 2024.
[19] John J. Irwin, Teague Sterling, Michael M. Mysinger, Erin S. Bolstad, and Ryan G. Coleman. 7INC: A free tool to discover chemistry for biology. Journal of Chemical Information and Modeling, 52(7), 2012.

---

[20] Chaitanya K. Joshi, Cristian Bodnar, Simon V. Mathis, Taco Cohen, and Pietro Liò. On the expressive power of geometric graph neural networks. Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, 2023.
[21] Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, and Pruden- cio Tossou. Rethinking graph transformers with spectral attention. In Advances in Neural Information Processing Systems, volume 34, 2021.
[22] Hannah Lawrence, Kristian Georgiev, Andrew Dienes, and Bobak T. Kiani. Implicit bias of linear equivariant networks. International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, 2022.
[23] Hannah Lawrence, Vasco Portilheiro, Yan Zhang, and Sékou-Oumin Kaba. Improving Equivari- ant Networks with Probabilistic Symmetry Breaking. In International Conference on Learning Representations (ICLR), 2025.
[24] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2222 2002.
[25] Ron Levie, Federico Monti, Xavier Bresson, and Michael M. Bronstein. Cayleynets: Graph convolutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing, 67(1), 2019.
[26] Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. In Advances in Neural Information Processing Systems, volume 33, 2020.
[27] Derek Lim, Joshua David Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. In The Eleventh International Conference Learning Representations, 2023.
[28] Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations, 2020.
[29] George Ma. Yifei Wang, and Yisen Wang. Laplacian Canonization: A Minimalist Approach to Sign and Basis Invariant Spectral Embedding. In NeurlPS, 2023.
[30] George Ma, Yifei Wang, Derek Lim, Stefanie Jegelka, and Yisen Wang. A canonicalization perspective invariant and equivariant learning. Advances in Neural Information Processing Systems, 37:60936-60979, 2024.
[31] Liheng Ma. Chen Lin, Derek Lim, Adriana Romero, Youssef Mrouch, Razvan Pascanu, Misha Laskin, and Julien Mairal. Graph inductive biases in transformers without message passing. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, 2023.
[32] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Provably powerful graph networks. Advances in Neural Information Processing Systems, volume 32, 2019.
[33] Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. Graphit: Encoding graph structure in transformers. arXiv preprint arXiv:2106.0560 2021.
[34] Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodolà, Jan Svoboda, and Michael M. Bronstein. Geometric deep learning graphs and manifolds using mixture model CNNs. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
[35] Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, volume 33, 2019.
[36] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. TUDataset: A collection of benchmark datasets for learning with graphs. ICMI. 2020 Workshop Graph Representation Learning and Beyond, GRL+, 2020.
12

---

[37] Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe. Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. Journal of Machine Learning Research, 24, 2023.
[38]
Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for general, powerful, scalable graph transformer. In Advances in Neural Information Processing Systems, volume 35, 2022.
[39] Levi Rauchwerger, Stefanie Jegelka, and Ron Levie. Generalization, expressivity, and univer- sality of graph neural networks on attributed graphs. In International Conference on Learning Representations, 2025.
[40] Víctor Garcia Satorras, Emiel Hoogeboom, and Max Welling. E(n) equivariant graph neural networks. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, 2021.
[41] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks and Learning Systems, 20(1), 2009.
[42] Kristof T. Schütt, Pieter-Jan Kindermans, Huziel E. Sauceda Felix, Stefan Chmiela, Alexandre Tkatchenko, and Klaus-Robert Müller. SchNet: A continuous-filter convolutional neural network for modeling quantum interactions. In Advances in Neural Information Processing Systems, volume 30, 2017.
[43] Daniel Spielman. Spectral graph theory. Combinatorial scientific computing, 18(18), 2012.
[44]
Yonatan Sverdlov and Nadav Dym. On the expressive power of sparse geometric MPNNs. In The Thirteenth International Conference on Learning Representations, 2025.
[45] Ameya Velingker, Ali Kemal Sinop, Ira Ktena, Petar Veličković, and Sreenivas Gollapudi. Affinity-aware graph networks. In Thirty-seventhh Conference on Neural Information Processing Systems, 2023.
[46] Soledad Villar, David W. Hogg, Kate Storey-Fisher, Weichi Yao, and Ben Blum-Smith. Scalars are universal: equivariant machine learning, structured like classical physics. In Advances in Neural Information Processing Systems, volume 34, 2021.
[47] Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In Inter- national Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, 2022.
[48] Yanbo Wang and Muhan Zhang. An empirical study of realized GNN expressiveness. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 22134-52155 PMLR, 2024.
[49] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
[50] Bohang Zhang, Shengjie Luo, Liwei Wang, and Muhan Zhang. Rethinking the expressive power of GNNs via graph biconnectivity. In The Eleventh International Conference on Learning Representations, 2023.
[51] Bohang Zhang, Lingxiao Zhao, Chen Cai, Liwei Wang. and Muhan Zhang. A complete expres- siveness hierarchy for subgraph GNNs via subgraph weisfeiler-lehmar tests. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, 2023.
[52] Bohang Zhang, Lingxiao Zhao, and Haggai Maron. On the expressive power of spectral invariant graph neural networks. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, 2024.
[53] Junru Zhou, Cai Zhou, Xiyuan Wang, Pan Li, and Muhan Zhang. Towards stable, globally expressive graph representations with laplacian eigenvectors, 2024.
13

---

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: Our claims are properly stated the abstract within their scope. We diligently wrote the assumptions, The experiments are aligned with the claims.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. 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 long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We claim that we have not fully determined when completeness on simple spectrum graphs is achieved.
Guidelines:
The answer NA means that the paper has 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 a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on 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-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't '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
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: All assumptions are stated, we provide proof ideas and full proofs are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors 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
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: All code is provided in the supplementary material and configurations and instructions as well.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
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 a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to 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 reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
15

---

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?
Question:
Answer: [Yes]
Justification:
All code is reproducible and provided openly with instructions.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.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 //ipss.cc/pill wttpcccpppppppppeeeeeeeeeeeeeeee httpa////giieee/eeeSSbbiiiissss /Cc////oddiiisssseeeeeee sww.isoicciyyyyciicc for more details.
The authors should provide instructions on 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. If 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 the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
All configurations are described in supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: When statistical significance is clear, mention; otherwise claim it is only comparable.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
16

---

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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It 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 figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables 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: All computer resources needed are mentioned the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics /tttp::://ourpps.cccpbbbii.o
Answer: [Yes]
Justification:
We fully abide by the NeurlPS Code of Ethics and preserve anonymity.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
This is thcoretical research that does not affect society.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or 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 considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: There is no risk, all datasets have no risk and are widely used.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere 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. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All the results by other researchers are cited, stated and given credit fully.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset'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: All code is reproducible with instructions.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing 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 human subjects are involved in this research.
Guidelines:
The answer NA means that the paper does not 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 the main paper.
According the NeurIPS 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: No usage of LLMs in core method.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy fattps://neurigg: /ttpa/rrpp..ccooooofeeeee/e///// for what should or should not be described.
20

---

Appendix
Proofs
A.1
Proof of Incompleteness of EPNN
21
A.2
Extension orthonormal counterexamples
23
A.3 Proots for implications for real-world GNNs
23
A.4
Proof for equiEPNN strictly more expressive
25
A.5 Proof of Incompleteness of Equivariant EPNN
25
Experiments
32
B I Dataset statisties
32
B.2
MNIST Superpixel
32
B.3
Realizable Expressivity
34
B.4
Eigenvector Canonicalization
Further Related Work
36
Expressive Power and the Weisteiler-Lehman Hierarchy
36
C.2
Higher-Order and Subgraph GNNs
36
C,3
Spectral GNNs and Universality
36
Equivariant Design and Generalization
36
Unified Theories and GNN Limitations
36
A Proofs
A.1 Proof of Incompleteness of EPNN
Theorem 1. (Incompleteness of EPNN The following statements hold:
1. U and V are not isomorphic under the group action of S12 x 131
2. EPNN cannot sepurate U and V after any number of iterations.
3. U and V have no non-trivial automorphisms.
Therefore, EPNN incomplete on simple spectrum graphs.
Proof. For convenience, we recall the definitions of the point clouds U and V: We denoted the four elements of the abelian group { {12, and the zero vector in R.. by
1
1
(
2g
1
22
02
Using these, we define U, V via
20
21
22
23
02
02
02
02
20
21
22
23
UT
22
23
72
23
0z
02
02
02
02
02
02
02
20
21
23
22
20
22
21
23
20
21
7/2
23
02
02
02
02
70
71
32
23
V
20
22
23
72
73
02
02
02
02
02
02
02
02
21
Z2
23
Z2
20
23
21
21

---

We first prove: 2. the inseparability of U and V by EPNN
Observe the purview of node i of U after the first refinement step of EPNN:
U, hy - (U, OU, U,, OU, [10]})
(7)
We will show that point clouds can be partitioned into 'blocks' such that each point in the block obtains the same hidden state. This block structure is recognized by viewing each point as a group element and each block as a multiplicative group. We will then show that this multiplicative group structure allows us prove the inseparability of EPNN.
Concretely, our proof proceeds as follows:
1. The column entries of U and V can be partitioned into 3 blocks: B, (1,2,3,4),BB - {5, 6, 7, 8). and B3 & {9, 10, 11, 12), such h (U) and hy (e)((T) (U) are identical for every
i,j E Bg, k 1,2,3.
2. It holds that n1 (U) h (V) for every i 1,2,.... 12.
(U) = n1 (V) for every i 1,2. .., 3. For any E N. h (4)
,.....,1. 12.
We first focus on Bi and then extend the argument to B3 and B3
Since the elements Uj for j = 1, 2, 3, 4 admit multiplicative group structure, then for every i 3, 4, the respective entries U, C Uy for j [4] are identical (closure of groups.)
For j = 5, 6, 7, and entries and the non-zero entries in the remaining row, each element of the group Z = {20: 21, 22, 22, 23} appears exactly once in the non-zero entries of the products, as it holds that =; Z3.
1, 2, 4, the entries of the products Vi2 @ Vj. are are zeros in two row
Analogously, we can extend this argument to j 9, 10, 11, 12 and i 1,2,3,4.
This means that h1 (U) and (,(((()) (U) are identical for every i,j B1.
Since, by definition of U and symmetry, each four-index quadruple B1 _ 1, 4, B3 5, and B3 2 9, 10, 11, 12 a multiplicative group, the analysis for the hidden states of the indices in B, holds for B2 and Bz. This concludes item 1.
2. Up to now, we proved for indices j E B₁ for k = 2, 3, it holds that n, = n,(1) It remains to be proven that these hidden states are equivalent both point clouds to conclude step 2.
Since the point cloud V is derived from U by multiplying the columns in B3 by diag(=0, 20, 21) and the columns in B3 by diag( Zo, Ru, 22), the purview (see Equation 7 of each index is identical in both point clouds, since 22- EPNN, this modification that maps U to V doesn't 't affect the pairwise multiplications in Equation 7
21 21
which is the identity element, thus by definition of
3. To prove this step, we only need to show that the hidden states remain identical within each block, since the fact that they are identical across the point clouds stems from the same justification of step 2.
In the second update step, the arguments of Step 1 remain identical. Still, now we have updated hidden node information, but the hidden node information is identical across nodes belonging to the same block. Therefore, the only information this refinement yields the categorization of nodes into
(0) blocks. Yet this information is already known in the initialized hidden states, ( = 1 1,..., m).
since the zero entries of multiplication h1 = V @ VÚ determine the block that belongs to. Therefore, the hidden states don't supply the network with any supplementary information other than the initialization (0))) = V, @ V, Thus, after a second refinement step. the hidden states remain identical within each block, as they have after the first refinement step. Moreover, the corresponding hidden states of the two point clouds also remain equivalent due to the arguments Step 2, which remain analogous, as the hidden states after refinement only assign each node its respective block
22

---

membership, which is exactly the information given in the first update step. This argument can then be applied recursively to any number of update steps.
In conclusion, we have shown that for any & E N, the hidden states of both point clouds are identical (in corresponding indices), therefore after permutation invariant readout, we obtain the same output.
We now prove 3. U and V have no nontrivial automorphisms. To show U, V are not isomorphic, we note that for any pair of permutation-sip matrices taking U to V. the first four columns of U must be mapped the first four columns of V The same true for columns the first four columns,
8 and - 12. Considering see that any sign matrix mapping them from U to V will be of the form diag(z, 2, z') for 2, 2' E {-1, +1}². The same argument for columns 5 - and 12 gives sign patterns of the form diag(z', (2,, 21 22) and diag(z, 2', 2), respectively. But there is sign pattern satisfying these three constraints simultaneously.
The automorphism group of this extended eigendecomposition is contained within that of U and U, respectively, and thus is also only the trivial group
The proof of 1. which states that U and V are not isomorphic, is analogous to the proof of 3, and yields that the only sign pattern taking each point cloud to itself (za, 20; zo), which implies each point cloud has only a trivial automorphism.
A.2 Extension to orthonormal counterexamples
The rows the above point clouds U, V are not orthonormal. Thus, they are not eigenvectors of an eigendecomposition of symmetric matrix. We fix this misalignment via the following 'orthogonalization matrices:
Taking Ü be a concatenation of the previous U and Ú defined by
2gg
221
22g
22g
02
02
02
02
220
-221
-202
-233
5g
31
22
23
220
221
22g
223
02
02
02
02
2
02
02
02
02
50
81
53
82
22
21
23
2
2
2
2
2
Then take V to be concatenation of the previous V and V defined by
22g
221
222
2z3
02
02
02
02
-20
-2
-222
-2z
pT =
20
21
22
23
220
221
222
223
02
02
02
02
2
2
2
02
02
02
02
The columns of Ü and V are now orthogonal, and they can be made to have unit norm by normalizing each column. As these extensions exhibit the same symmetries U and V, respectively, analogous arguments to the proof of inseparability of U and V by EPNN (Theorem 2) will apply to this new pair Ü, V. Therefore, EPNN cannot distinguish Ü and V.
A.3 Proofs for implications for real-world GNNs
Proposition 3. Vanilla OGE-Aug 53 is incomplete over graphs with a simple spectrum.
Proof. The method proposed by Zhou et al. 53 consists of a permutation equivariant and orthogonal invariant function. We will show that a counterexample by (30) also applies to this network.
Vanilla PGE-Aug relies on a cetpuuattiooneuivarriiiii and orthogonal invariant set encoding to process each eigenspace separately. Werevisit their separate definitions and theorems:
Detinition 4 (O(p)-invariant universal representation (53)). Let f U B guxp U Rr. Given an input V R=xp, outputs vector f(V) E R". The function said to be -ivvainva universal representation if given V. V.V" Raxp and P E Sn, the following two conditions are equivalent:
(i) f(V) PP(V'):
(i) 3Q O(p), such that V = PV'Q.
23

---

Definition (Universal set representation [53]). Let X be a non-empry set. fuunction f: 2* - I said to be universal set representation if X2 E 2*, f(X1) f(X2) if and only if the two sets X1 and X2 are equal.
let fp be -ivv-invariant universal representation function. Further let g 2 - be a universal set representation. Then the following function
Proposition 3.5 (Zhou al. 53
For each p
r(G = GNN (Ac, concat [Xa.g 9 ([concat(ay, In, Anln, fuy (V))D))))) (]]
(8)
is a universal representation. Here n = [V(G), ((A1, MI)..... (Ax, pk)) )) is the spectrum of G, and VG RTx,; are the μú mutually orthogonal normalized eigenvectors of LG corresponding Aj. We denote 1, an all-1 vector of shape n x I. GNN is a maximally expressive MPNN.
Then Zhou al. [53 propose the following graph neural network:
Definition 3.6 (Vanilla OGE-Aug). Let fp be an O(p)-invariant universal representation, for each p= -= 1,2,,,.... and g 2² IR be a universal set representation. Define Z 9 + U R" as
Z(G) 9 (fconcat [Vsliv()) (x )=1
(5)
In which the notations follow Proposition 3.5. For G' g, Z(G) is called a vanilla orthogonal group equivariant augmentation, or Vanilla OGE-Aug on G.
We will show that architectures of the form of Proposition 3.5 and specifically Vanilla OGE-Aug incomplete simple spectrum graphs, contradicting the claim in Proposition 3.5 that such representation is universal.
Consider the point clouds proposed by Ma et al. 30
T
U1 [M1, M12]
(9)
2
3
4
5
T
-
1
-1
U2 U22 U22]
(10)
Suppose the first column eigenvector of U₁ and U2 corresponds eigenvalue
A 1, the second column eigenvector of U₁ and U2 corresponds to eigenvalue A2 2, and other eigenvectors not shown corresponds to eigenvalue 0 (so we
safely ignore them). Then the Laplacian matrices corresponding to U1 and U2 are:
11
17
19
19
23
31
L = Bmnnnn A2
(11)
17
23
33
39
19
31
39
51
11
21
11
19
25
29
L2 = Au + Ao
(12)
15
25
33
39
21
29
39
51
We will now demonstrate the model in Proposition 3.5 will be unable to distinguish U1 and Us. regardless of the choice of the GNN.
First, consider an arbitrary O(1) innaarant representation f R - R". We will show that f(U)) and f(U2) are identical.
By the permutation equivariance and O(1) invariance:
f(un) f(-u11) f(Piuu)) = Puif(un)
(13)
24

---

where P11 is any permutation that satisfies Pi1"111 = -11 Therefore P11 can be chosen to be 01 - (12) (3 4) or (1 4) 3).
By Equation 13 and since equality is transitive relation, it holds that (() ((11) for any and j in the same orbit under the group < 01, 02 >, the group generated by σa and d2- is easy to check any pair (1.j) {1, 2,, 3,42 can be transposed under group element in the generated group. Therefore, ((11) is constant function. Analogous arguments yield ((221) ) is also constant.
Note that for P12 _ 23 4), holds that
f(111)
Pf(un)
f(Pun1) f(22))
1(111) constant
perm equivariance
Therefore, f(u1)) f(22)) Moreover, the second eigenvectors, U12 and U22 Uj and U2. respec- tively, are identical therefore clearly (((12) = ((u2)).
This analysis naturally extends proper eigendecomposition (orthonormal eigenvectors of graph as proposed by Ma et al. (30) in the proof of their Corollary 3.5 (30
Therefore, as any universal, invariant set representation is the same both U₁ and U2. the input to the network will be identical per its definition, and thus for their corresponding graphs G₁ and G2 and identical node features XG, and XG,, respectively it holds that
rG1 XG:) (G2,,Xa.))
yet Gj and G2 are non-isomorphic, thus Vanilla OGE-Aug is incomplete.
A.4 Proof for equiEPNN strictly more expressive
Corollary 1. equiEPNN (see Section 3.3 can separate and after 2 iterations. Thus equiEPNN
is strictly stronger than EPNN.
Proof. We show that after a single iteration, the equivariant update step can yield new matrices U(0 V(), 10,,111 which have no zeros. We can choose the update function UPDATE such that UPDATE (12)) O us vn O 01 Ub v1) & (1. 1, 1,0,0,0,,0000 0) and for all other values we define it as Ō.
After single iteration (1) and (I) will be
20
21
22
23
20
02
02
02
20
21
22
23
UQYT
20
21
72
23
20
21
72
23
02
02
02
02
02
02
02
02
20
21
23
2:
20
22
23
20
21
22
23
20
02
02
02
20
21
22
23
V()T
20
21
22
23
20
81
22
23
02
02
02
02
02
02
02
02
21
20
22
23
22
20
23
21
Since there exists column (the fifth column) such that all its entries non-zero in both (1Y and V()T from Theorem 2. we know that a single iteration EPNN, and hence also equiEPNN, can separate (1)) V(I In conclusion, two iterations of equiEPNN are sufficient for separation. IT
A.5 Proof of Incompleteness of Equivariant EPNN
The purpose of this section is to show that equivariant EPNN is also not complete on simple spectrum graphs. To show this, we will construct a counter-example isomorphic with respect to the joint action of permutations and sign multiplications, and yet cannot be distinguished by equiEPNN, We note that the columns of X, Y are not orthonormal, and they do have automorphisms.
pair X, Y which are not
25

---

For X,Y E Ru** we will say that X = Y, if there is some permutation matrix P such that PX =. We will say that s [-1,1] is an isomorphism between X and Y. if (s) Y. Here diag(s) is the K x K diagonal matrix with on the diagonal. An automorphism of X is an isomorphism from X to X.
As first step to construct our counter example, we consider the subgroup // S {-1, defined by = {s
81 {-1,1}²
83 1}.
Let T be the 4 x matrix whose rows are the four elements of H, namely
-1 -1
T -1 -1 1
-1
Note that Aut(T) H due to having a group structure.
Next, we build the matrix X to consist of four different copies of T. Each copy will be not a 4 x but a 4 6 matrix, where three of the columns are the columns of T, and the rest are zero columns. Moreover, any two copies of I will only have one non-zero column in common.
To do this, choose four index sets in 21, ..... 6}. who have this intersection pattern, namely
1 = [1,2,3), I2 = {3, 5],
13 - {2, 63,, 14 = (1,5,6) 6).
One can verify that indeed [ n T& = 1 for all * k. We then define the matrix T(T to be the 4 x matrix as described previously. For example
0 0
1
1
0
0
0
1
-1
-1
0
T
0
0
1
-1
1
1
0
0
We define X to be the block matrix
T T
X
E R 16x6
T
7 T[4
explicitly
0
0
1
-1
X
0
0
0
0
I
0
0
1
0
-1
0
0 -1
We define Y similarly, but we elementwise multiply the rows of ["44] by the sign vector
q 1,,,,,,,1,1,11
to obtain
T didgg())(
T2 T T[44]
Y=
E ER 16x6
This is our counterexample. We claim/
26

---

Theorem 4. (Incompleteness of Equivariant EPNN There exist X,Y E R16x6 such that the following statements hold:
1. X and Y are not isomorphic under the group action of S1e x (-1,1}
2. Equivariant EPNN cannot separate X and Y after any number of iterations.
Therefore, Equivariant EPNN is incomplete on simple spectrun graphs
Proof. Remark: X.Y are not isomorphic. By considering the zero patterns of X and one sees that if E 1,, is an isomorphism mapping X to Y, then satisfies [ (d)) for some permutation matrix (acting on the rows of I and must also define an automorphism of [[]]] for j 2,3,4 4. Since each T[[]'s rows (padded with zeros) form a group, its only automorphisms are elementwise multiplications of rows by its group elements, which implies Ih,,,, 1. From these three automorphism conditions, we deduce:
83 85
$2 54 86
$1
Multiplying these three equations with each other we deduce that
81 52 53 = 1.
Now, if this holds, then cannot satisfy P diag(s) [[]g(()) because the product the first three entries of any row of P[]((i]dag is 1, while the product of the first three entries of any row of [d]ag(()) is 1.
X and cannot be separated by equiEPNN
We prove by induction that for any number of layers in an equiEPNN, the hidden states for nodes within the same partition Bg are identical, and this holds for both graph structures X and Y. This equivalence prevents the network from separating them.
We introduce useful definitions:
Definition 6 (Block Structure and Neighborhoods). We partition the 16 nodes (rows) into
4 disjoint blocks B3 for k = 1,...,, (e.g., B1 = ( -1....,,4 .]. B2 = (5....,8), ,,8,, etc.). The 4 x matrix of initial equivariant features for block By B X[BR,:] = T( The non-zero feature indices for this block are Ig. For a node E Br. we define its neighbors: Nimma 2 B& and Nimerr (1) A .1....,n] \ Bg.
Definition (Invariant Node Neighborhood). The message from neighbor to a node of is tuple containing the neighbor's 's invariant features and an invariant computed their equivariant (1)
features, (h) , xr ( The Invariant Node Neighborhood of node i layer is the multiset of invariant features I. & Iidnara U II() Inter where
(1)) (1)
Linntr {(1 2 о 5
(1)
11) Nuarra
((()) Liinter (11)0
x 2 0r li E (ineer(i)
(1)
where {.} denotes a multi-set. The update rule combines the node's own invariant state h with aggregations of the messages from its neighborhoods:
h (+1) 6b, AGG(I!"))
where AGG is a commutationninvariin aggregation function (e.g., sum or mean).
Definition (Equivariant Node Neighborhood). The Equivariant Node Neighborhood of a node at (t)
layer is defined by ei!) inta U iiinter where
27

---

of squaring to sign changes. Additionally, (1))) (0) for i, Bş and (1) + (0) for j & Bi. due to the unique sparsity pattern of each block. This completes the first step of the outline. We Inira-block Neighborhood (()) i,intn = (60001 (..001 a ". 0zy 2/ 1j E (1)
Inter-block Neighhorhood e(l) L,itte (dho(h))) 1 1 23 ,
2i !1)
1j Niiter
where { denotes multi-set. Also, define the messages arriving node i from a different (!) (1)
block Bx (k + p) at layer I by E = t (hg M , 2 o (1)
lie B.).
The equivariant feature updated by summing over both neighborhoods:
(1+1)
(1)
Σ
Σ m
m+
ME
ME L,irr
(t)
Proof outline:
1. We show that the blocks of X and Y are particular case of generalized block structure.
2. We analyze the mechanics of equiEPNN when processing these generalized X and Y prove that the invariant node neighborhoods of corresponding nodes X and Y are equivalent. This the base of our induction.
3. We show that the equivariant update step maintains this generalized block structure for both and Y. The equivariant update maintaining the generalized block pattern X and Y is the induction step of the proof.
4. Since equivariant update maintains the generalized block structure of X and Y, and the subsequent invariant node neighborhoods of corresponding points in generalized X and Y are identical, by the base of induction, equiEPNN will output the same readout for both and Y after arbitrarily many refinement iterations (the hidden states are equivalent as multisets for both point clouds).
Base Case (Generalized Block Pattern and Invariant Update)
x; are identical for all i E BE, as they equal the indicator vector for the partition 4. We consider generalized case, where the initial equivariant features for block Bg (with non-zero columns I&) form matrix B[() where (0) [:, Iu] is:
Generalized Block Pattern The initial invariant features h = r; (0) (0)
B
(0)
$k2
$.3
(0)
(0)
(0)
B [ I =
[0)
k.
-8
$6.3
(0)
(0)
(0)
8k.2
-8k3
k.2
-8k33
In counterexample X, the scalars $R.j = 1 for all k.j. For Y, 81,1 =1.1-111 (from block & = 1. column j 1) and all other Sk.j 1. We consider this generalized case because we will show that after equivariant aggregation, this will be the format of the blocks. These are called generalized X and Y with single scalar choice defining them, as the generalized Y is equivalent to generalized X up negation first of the first block of X. We refer these generalized X and Y as simply X and Y in the remainder of the proof.
These initial hidden states h (0) are identical for both point clouds X and Y, due to the invariance
now proceed to the second step of the outline, where we prove that an invariant update maintains the equivalence of the hidden states within each block.
Invariant Update We formally define the aggregation steps for a node i E B3 at layer / by splitting our analysis of its neighborhood into intra-block neighbors (i) and inter-block neighbors (i) For any two nodes i,j E Bj, we show their invariant neighborhoods yield identical aggregations.
28

---

(1) Intra-block: A message from neighbor m B₁ is (hm ax @ @.m) By the inductive hypothesis, Am is constant for all m E Bx- The set of vectors {am m E B forms a group under the Hadamard product (up scalar multiples). By the group closure property, the multiset of products {a C xm m E [i) is simply permutation of { C am
(1)
(t)
())
m E Nintra (j)) for any i, E Bk- Therefore, any permutation invariant aggregation over (1) i,intra and (1) j.inta is identical.
Inter-block:
The graph is constructed such that for any l + p. [T 1. The inter-block neighborhood for node in B& consists of nodes from the other three blocks. Consider neighbor m E Bp- The product 2!!0) C si non-zero only at the single index j T O T Due to this structure, the resulting multiset of invariants from block Bp is of the form {ayez, ayej, e, -aye, } (where e, is the standard basis vector and aj is some scalar), which is identical for all E lkk
Since both neighborhood aggregations are identical, and h. -ng for i, E Be, the update yields (1+1)
h; h n
(1+1) for both X and Y.
Inductive Step
Assume at layer I, for any partition Bx. h. = hn for all i,j E Be, and the equivariant feature matrix B A x[B ( maintains the scaled pattern structure.
The update for the equivariant features x ((+1) combines the original features 2 with aggregations from intra-block and inter-block neighbors.
Equivariant Update
The aggregation of messages within block Bg can be compactly expressed via summation and Hadamard products. The message function & produces scalar weights for each interaction. Since the invariant features (9) are constant within the block, these weights depend only on the structural relationship between nodes i and j. Due the graph's 's symmetries, there are only four unique interaction types within block, resulting in four learned scalar vectors, with scalar dimension weights in each feature dimension in R Since only IN are the indices with non-zero features, we focus on their aggregation, and the rest of the inputs along other feature dimensions will be aggregated to therefore denote by a, c, d E R the reduction into the feature indices in 4. These form symmetric weight matrix (in the node dimension) we denote by
Intra-block Aggregation:
a
c
d
(1)
b
d
R
4444X3
c
a
d
a_
This operation, which denote by x, scales the columns of the feature matrix B while preserving their sign-pattern structure:
[1,
1 + bo 12 2
+ B 0 B 4
do
B( [+]
(1)
B
[: I =
b B [1, 1x] + 12, +d
(2
B. 10
4 +c0
B
[4, [k]
R443
[1
B 2,
+a0 B 3 &
+0
+ba B(
(0000 [4,
d
B
2.
2,
3,4
+
[4]
(14)
3
-a
3
(15)
7
3
where the entries of the resulting matrix (in the Ig columns) are denoted by the scalars o. 8 7. These scalars are the result of applying the learned weights a, b, c, d (which are vectors) to the corresponding
29

---

e(t) i the resulting columns of B, Specifically, they are defined as:
k, (ai, bú, + Cin di,)
(1)
B 8 ( big ciz + dig
(1)
7 s (,3 + bis -ts ddi))
(1)
where aj is the j-th component of a, etc. and i1, i2, is E T.- This operation preserves the fundamen tal sign-pattern structure of each column, merely updating its overall scaling factor.
Inter-block Aggregation: Let E Bp be a node index block p. and let + p be different block
index. Consider the equivariant node neighborhood ii," We first focus the inter-block aggregation of X and proceed to discuss that of Y. Consider the contribution of the equivariant message passing to the features of node from block Bg. There are 3 possible cases:
Case I: Aggregation of (L) along dimension d 1 np. Along this single feature index d, i,k
the only non-zero information in the product is [d] 2 R for j E Bg- This scalar, apart from the hidden states (which are constant within blocks), is the only structural value that determines 6o (12
(1) (.)). This de in turn determines the feature-wise weighing of ag. It follows that (1) h2 2 .
for any node 8 E Bp. the sum of e(t) in the feature dimension d precisely equals that of i up to sign(x;) (1) [d] 2. [d). Because [d]"[d] follows the generalized block pattern for Bp, the aggregation into dimension also follows this pattern.
Case 2: Aggregation of E along feature indices in Is \ Ip. From Case 1, Φ. is determined by the sign of the product in dimension d. This results in two possible weight vectors, say ā and 6. The set of messages is
cx (ā@Ti a Tjz to Fjs 100aa ajs)
(16)
where FJ1 Fy are (w.loo.g) the points with a positive scalar product with o; in dimension d, and Ti, are those with negative product. By construction of T, the points , satisfy 2j, (m) = -Ija (m) for each m I& Ip. An analogous result holds for Tja Therefore, summing all ell) points in i yields zeros in feature entries 4 4p.
i.k. along remaining indices. In all other indices, f1,2...., 6} (I))))) the features of xy (for j E B₂) are O. Thus, it trivially holds that after aggregating vector entries in those dimensions will also be 0.
Case 3: Aggregation of c(l)
We now address the inter-block update of Y in comparison with that of X. The only structural difference is the negated first column in block Bi of Y. This affects aggregation for i E B1 and for i B, (since 1 44 {1)). The sign of x are swapped. For i By:
(1) [1] [((11] is flipped. This means the roles of ă and 5
(12 = o Yí do yjz, a O Vis. ē 2 yb.}
(17)
The sum is thus negated. This occurs only along the first column of the first block. For i E B,, the aggregation from B1 is:
(X)( AGG((T x,, ,,,d do Tn to E (o
(18)
AGG([ā @ Ki T0 2 O To
o Oij To - Ozy,)
(19)
= AGG( e o Un 1y.
1
① 1y á ee 2 vn))
(20)
= AGG((b yj To Yin do Vi, 1o Vi. = (Y)(E.
(21)
for some ū. 5 E T The equality holds. Therefore, the equivariant aggregation of Y is equivalent to that of X, except in the first column of the first block, where is negated. The aggregations for both X and Y maintain the generalized block pattern.
30

---

In conclusion of the inter-block aggregation, each 2, B₁ will be added with an equivariant feature of the form ell) ① (where e is shared column vector), and y: will be added with cl @ ys.
Full Update: The new feature matrix B is the sum of the original features and the intra- and inter-block aggregations. This process preserves the essential column structure. The update can be expressed as:
B B (I 4 B c @ B
(22) where e!l) is column vector. This operation simply updates scalar multiples of each column. For example, the sum of the original features and the intra-block aggregation (for the Ia columns) results in:
kk
11)
+
$k2 +
!1)
kk +
(T 1 BB
(8.11 +a)
11)
-6k,2 3))
5k +7
[0)
kk +a
- + B))
-(5 +7)
(5k,1 +
(1)
$1,2 B
- +
By Equation 22 the equivariant features remain in the generalized block form.
In conclusion, at each layer, invariant features remain uniform within partitions, and equivariant features update symmetrically. Since the representations structurally identical (up the 81, sign flip, which is preserved) for both graphs, they are indistinguishable.
X and Y can be extended to proper eigendecomposition
To form a complete basis of 16 eigenvectors, we construct the remaining 10 orthogonal vectors, X IR 16x Define the local orthogonal basis for I (along the rows of the matrix):
-1
1
b
(23)
1
-1
Let E RR be the zero vector. We construct the matrix block b.... is 4 row vector):
X
E
10 as block matrix (where each
a
b
0
-
0
C
0
0
b
b
0
T
O
c
(24)
0
0
0
0
0
0
1
The rows of T (columns of X) are orthogonal each other and the columns of X. Thus, after scaling, Xfau [X, X] E 16 forms orthonormal basis. The block structure is maintained within the first 6 rows of XT. new information to the hidden states, other than their block membership. The "all-ones" vectors (last rows) are constant on each block and do not pass messages between blocks. This means the invariant and equivariant aggregation remain analogous to Part 2 when processing the full matrix X fulr = [X, X]. The hidden states only depend on the structural relations defined by X. Therefore, for analogous matrix Y (with its first row replaced by equiEENN will yield the same output [Y, Y and [X, X]. which form valid eigendecomposstions for an equal simple spectrum. In conclusion, equiEPNN cannot separate and Y.
analogous proof to Part shows that these do not contribute
maintain orthogonality with Y),
31

---

B Experiments
B.1 Dataset statistics
We surveyed popular graph datasets and documented their graph spectral properties. The results are shown in Table We find that the MNIST Superpixel [34] dataset is almost homogeneously composed of graphs with a simple spectrum, and we find that (96.9%) of the graphs in this dataset have a full row without zeros, implying that EPNN is complete on almost all graphs.
Other datasets, such as MUTAG, ENZYMES, PROTEINS and ZINC 19 36), contain a substantial amount of graphs with eigenvalue multiplicity 2 and 3. Despite this, the number of eigenspaces of dimensions 2 and 3 is very few per graph, averaging at around per graph. On datasets with highly symmetric graphs, such of Theorem 2 thus EPNN will not necessarily faithfully learn the graph structure. This exemplifies the need for more expressive models that are complete on graphs with higher maximal eigenvalue multiplicity and sparse eigenvectors.
ENZYMES and PROTEINS, the graphs do not meet the sparsity condition
Table 5: Graph Statistics Analysis Across Different Datasets (Eigenvalue Tolerance: 10
Dataset Name
MUTAG
ENZYMES
PROTEINS
MNIST
ZINC
Dataset Overview
Number of Graphs
188
600
1,113
60,000
10,000
Eigenvalue Characteristies
Graphs with Distinct Figenvalues
41.5% (78)
34.8% (209)
12.1% (246)
99.9% (59,950)
40.7% (4,072)
Graphs with Multiplicity Eigenvalues
58.5% (110)
65.2% (391)
77.9% (867)
59.3% (5.928)
Gruphs with Multiplicity 3 Eigenvalues
19.1% (36)
46.2% (277)
57.9% (644)
26.2% (2.617)
Aug. Number of Multiplicity 2 Higenvalues
0.74
1.01
1.24
Avg. Number Multiplicity Eigenvalues
0.26
0.58
0.71
Eigenvector Properties
Average Ratio of Zeros
1,67
4,28
6,39
0.31
2.52
Average Numher of Zeros
31.13
172.93
817:20
23.16
61.04
Graphs Full Row
75.0% (141)
35.8% (215)
37.1% (413)
96.9% (58,077)
64.5% (6,447)
Graphs with 1 Zero per Eigenvector
0.0% (0)
6.3% (38)
5.0% (56)
20.2% (12,085)
4.3% (430)
Graphs with Total Zeros < Vertices Graphs Meeting Any Condition
29.8% (56)
16.3% (98)
14.3% (159)
89.9% (53.873)
13.0% (1,295)
75.0% (141)
35.8% (215)
37.1% (413)
96.9% (58,077)
64.5% (6,447)
We surveyed the graph spectra of popular datasets to verify the need for more expressive architectures based on graph properties. We now further specify the meaning of each row of Table 5 in Table B.1
B.2 MNIST Superpixel
Below, in Tables 8 and B.2 we list the experiment configurations and hyperparameters of the
MNIST experiment.
As toy experiment examine the potential benefit of using equiEPNN, We implemented equiEPNN via a modification of the EGNN architecture [40] and EPNN with the same architecture, but without the eigenvector update step. For precise hyperparameter configuration, see the Appendix.
In our first experiment, we applied the proposed method on a classical task of handwritten digit classification in the MNIST dataset [24] While almost trivial by today's standards, we use this example to verify the theoretical claims regarding expressivity on simple spectrum graphs. Our experimental setup employed both EPNN (coordinate updates disabled) and cquiEPNN (coordinate updates enabled) as our models exclusively on the superpixel- -baseed graph representation from the Superpiies dataset. In this approach, each 28 x 28 image where vertices correspond to superpixels and edges represent their spatial adjacency relations, each different graph. We tested our models with different positional encoding dimensions of l = 3, 8, 16 to evaluate performance across varying levels of spectral information.
converted into a graph
image represented
For details configutions see Tanbes 7
8 and 9
B.2.1 Ablation
We examined the performance of both methods on the MNIST Superpixel datasets, where the task is classification of handwritten digits. We found that cquiEPNN outperforms EPNN, with the same
32

---

Eigenvalue Characteristics
Graphs with Distinct Eigenvalues
Graphs where all eigenvalues have multiplic- ity 1, meaning each eigenvalue appears ex- actly once in the spectrum
Graphs with Multiplicity 2 Eigenvalues
Graphs that have at least one eigenvalue that
appears exactly twice in the spectrum
Graphs with Multiplicity 3 Eigenvalues
Graphs that have at least one eigenvalue that appears exactly three times in the spectrum
Avg. Number of Multiplicity 2 Eigenvalues
The average number of eigenbasis that have multiplicity exactly
Avg. Number of Multiplicity 3 Eigenvalues
The average number of eigenbasis that have multiplicity exactly
Eigenvector Properties
Average Ratio of Zeros
The average proportion of zero entries found in the eigenvectors across all analyzed graphs
Average Number of Zeros
The average count of zero entries in the eigen- vectors across all analyzed graphs
Graphs with Full Row
Graphs that have at least one eigenvector with
zero entries (i.e., a "full row" in the eigen-
vector matrix)
Graphs with Zero per Eigenvector
Graphs where each eigenvector has at most one zero entry
Graphs with Total Zeros
Vertices
Graphs where the total number of zero entries across all eigenvectors is less than the number of vertices the graph
Graphs Meeting Any Condition
Graphs that satisfy at least one of the specified eigenvector properties listed above
Table 6: Explanation of Surveyed Graph Spectral Properties
Table 7: MNIST Superpixel Experiment Configuration
Parameter
Default Value
Description
k_ values epochs
[3, 8, 16]
List of k values for positional encoding dimensions Number of training epochs
30
batch_size
32
Training batch size
data_dir
'data' ccuda'
Data directory path
device
Computing device (CUDA if available)
early_stopping
10
Early stopping patience
output dir
'results'
Output directory for results
coord _edd__ppp_e____ options random_seedd
update_options
[True, False]
Coordinate update configurations
42
Random seed for reproducibility
33

---

Table 8: MNIST Superpixel Network Hyperparameters
Parameter
Default Value
Description
fea_uesuuees num_clam sam_classes hidden_dim
Input node features (MNIST characteristic)
10
Output classes (MNIST digits 0-9)
64
Hidden layer dimension
num lanelayers
Number EGNN layers
pos_enc enc_ dim
k
Positional encoding dimension (varies: 3, 8, 16)
dropout Ir
0.2
Dropout rate
0.0005
Learning rate
weight_ deight_decay
le-5
Weight decay for regularization
norm_features
True
Normalize node features
norm_cowe norm_coords
True
Normalize coordinates
coord_ woord_weights_clane
1.0
Clamping value for coordinate weights
with_pos_enc
True
Use positional encoding Use edge projectors
with_proj with virtual node update_coords coords
False
False
Use virtual node Coordinate update flag (both tested)
True/False
Table 9: MNIST Superpixel Training Configuration
Parameter
Value
Description
Optimizer
Adam
Optimization algorithm
Loss Function
NLL Loss
Negative log-likelisi oggliiklihood loss
Scheduler
ReduaeelROnPlateau
Learning rate scheduler
LR Reduction Factor
0.5
Factor for LR reduction
LR Patience
Scheduler patience Minimum learning rate
Min LR
1e-6
Gradient Clipping
1.0
Maximum gradient norm
Early Stopping Patience
10
Training patience
number of model parameters and hyperparameter instantiations, in setting with few known eigenvectors. With sufficient number of eigenvectors EPNN and equiEPNN achieve comparable results, as expected, since they are both complete on almost all graphs in MNIST Superpixel. (see k=8 and k=16 in Table 10
B.3 Realizable Expressivity
The BREC 48 dataset is graph expressivity benchmark consisting of highly symmetric graphs that high-order GNNs struggle at distinguishing, which was used by [52) to check the expressivity of EPNN. We implemented EPNN and equiEPNN via the popular EGNN 40) framework and obtained statistically identical results shown in Table I2
B.4 Eigenvector Canonicalization
We specify the problem setup for eigenvector canonicalization and our proposed method.
Table 10: Ablation study on MNIST Superpixel (34]. Accuracy percentage comparison with deviation over 3 trials, for different values of K for EPNN and equiEPNN.
k
EPNN
EquiEPNN
48.45 + 1.2 %
60.95 + 0.9 %
85,55
2.1
83.56 + 2.5 %
16
90.13 + 2.3 %
91.37 + 2.2 %
34

---

Table 11: Network Hyperparameters for Eigenvector canonicalization
Parameter
Default Value
Description
num_layers
Number of message passing layers
uub__iim
128
Embedding dimension
in_dim
128
Input feature dimension
proj_dim coords _eight
10
Projection dimension
3.0
Coordinate update weight
activation
relu
Activation function
norm
layer
Normalization type Aggregation function
aggr residual
sum
False
Use residual connections
edge_aue aat_attr__dd _im
20
Edge feature dimension (2 x k k_projectors)
Table 12: Empirical performance of different GNNs on BREC (in percentages.) (Using k=3 spectral
features, results of non-EPNN models from 22
Model
WL class
Basic
Reg
Ext
CFI
Total
Graphormer
SPD-WI WL
26.7
10.0
41.0
10.0
19.8
NGNN
SWL
98.3
34.3
59.0
0
41.5
ESAN
GSWL
96.7
34.3
100.0
15.0
55.2
PPGN
3-WL
100.0
35.7
100.0
23.0
58.2
EPNN
EPWL
100.0
35.7
100.0
4.0
53.5
Equi-EPNN
N/A
100.0
35.7
100.0
4.0
53.5
Definition 9 (Figenvector Canonicalization). A canonicalization of an eigenvector E R is map & R + Ih such that for every 8 E O(1) = {-1.1}, holds that 6(sv) = ((v) and is permutation equivariant, that for every permutation a, <((ov) aœ(v).
We now define the following eigenvector canonicalization map via the steps
1. For given eigenvectors V g corresponding distinct eigenvalues, we run equiEPNN for T iterations, obtain the equivariant output V(T)
2. We sum over the columns to obtain a matrix S diag(s), ,2, .8) where - sign (( E +11,
3. Canonicalize the eigenvectors via SV.
This defines an eigenvector canonicalization map : Ra*k + ga where (VV) = SV for the S(V) defined above. This map is naturally permutation equivariant, and it is casy check that is sign invariant.
As this maps canonicalized the original eigenvectors via aggregating global graph information that depends on the entire graph eigendecomposition and not each eigenvector separately, we obtain map that practically achieves perfect canonicalization on ZINC [19
See Tables
11 and 13 for experiment configurations.
Table 13: Eigenvector Canonicalization Configuration
Parameter
Default Value
Description
subset_size
100
Number of ZINC graphs to test Number top eigenvalue projectors to use
k_projectors
10
num_ workers
Number of workers for data loading Computing device (CUDA available)
device
CUDA/CPU float64
precision
Default tensor precision
35

---

C Further Related Work
C.1 Expressive Power and the Weisfeiler-Lchman Hierarchy
The expressive power of GNNs is commonly evaluated via the Weisfeiler-Lehmann (WL) test, with standard Message Passing Neural Networks (MPNNs) being upper-bounded by the I-WL. test 449 35 This has motivated the development of more powerful models aligned with higher-order k- WL tests 32]. The WL hierarchy and variants have been clarified in tutorials by [17] 37]. Other works have moved beyond the binary isomorphism objective to develop more continuous, fine-grained measures of expressivity based on graphons and tree distances 77]. Our work diverges from these combinatorial frameworks by proposing a hierarchy based on eigenvalue multiplicity, a natural concept in spectral graph theory. We demonstrate that even SGNNs considered powerful in the WL hicrarchy (EPNN) can fail on spectrally-defined graph classes, revealing limitations not captured by combinatorial tests.
C.2 Higher-Order and Subgraph GNNs
To overcome the 1-WL barrier, a prominent line of research has focused on architectures that process higher-order structures. Subgraph GNNs, which represent graph as an equivariant collection of its subgraphs, have proven to be a particularly powerful paradigm [ A significant challenge has been the computational complexity of these models. Recent work by introduces flexible and scalable framework for Subgraph GNNs using graph products and coarsening to manage complexity. This line of research, including work by (.]. has also explored novel methods boost expressivity by leveraging high-order derivatives of a base GNN model, drawing deep connections between this calculus- based approach and the WL hierarchy. Our work provides a complementary perspective by showing that even highly expressive architectural paradigms can have fundamental blind spots, such as the inability to distinguish certain graphs with simple spectra.
C.3 Spectral GNNs and Universality
Spectral GNNs define graph convolutions via spectral filters. Early work improved filter expressivity by moving from polynomials to complex rational functions, as in CayleyNets (25). A key theoretical result from [47 established that linear spectral GNNs can achieve universal approximation
graphs with a simple spectrum. However, this universality relies on crucial assumption: the use of a randomly sampled, non-equivariant node signal. This setting is distinct from the standard GNN expressivity analysis, which assumes comnutation-equivarinn operations on graph structure. Our work investigates the expressivity of germutation-cqqiiariaaa SGNNs, such as EPNN, under the same simple spectrum condition. We prove that, in this more standard setting, these models are fundamentally incomplete. We construct explicit counterexamples of non-isomorphic graphs with simple spectra that EPNN cannot distinguish, revealing a critical limitation that was not apparent from prior analyses.
C.4 Equivariant Design and Generalization
core principle in modern GNN theory is designing architectures that respect the symmetries of graph data, i.e., permutation invariance and equivariance [46). This has led to principled methods for handling spectral features, such as the sign and basis ambiguities of eigenvectors. Models like SignNet and BasisNet are designed to be invariant to these symmetries by processing eigenspaces independently (27) Work by 22 has analyzed the implicit bias of such equivariant networks,
showing that gradient descent favors solutions with specific structural properties in the Fourier domain. Other work has explored probabilistic frameworks for breaking symmetries when necessary (33. Our work builds on these principles; we show that even a principled equivariant architecture like EPNN is incomplete, and our proposed solution, equiEPNN, is directly inspired by equivariant network designs.
C.5 Unified Theories and GNN Limitations
One recent research direction is to move towards a more holistic understanding of GNNs by connecting expressivity, generalization, and universality. Work by (39] proposes a unified framework using pscudometrics based on optimal transport to derive both universal approximation theorems and
36

---

generalization bounds for MPNNs on attributed graphs. Concurrently, critical work has highlighted the practical limitations of GNNs. For instance, 4 demonstrated that GNNs can 'overfit' the graph structure, using it even when it is detrimental to the task. This suggests that theoretical expressivity does not automatically translate better performance. Our paper contributes this line of inquiry by identifying a novel and unexpected failure mode for class of GNNs that are already considered highly expressive. This reinforces the notion that expressivity not monolithic and that different architectures have distinct failure modes.
37


Reviews:
[{"review_id": "p873paSMZg", "reviewer": "Reviewer_aLjK", "summary": "This paper emphasizes the limited understanding of the expressive power of spectral graph neural networks (SGNNs) via standard methods, such as, ,WL graph isomorphism test hierarchy and homomorphism counting. The analysis reveals that many SGNNs, including recently proposed Eigenspace Projection GNN (EPNN), are incomplete in distinguishing graphs, even with simple spectra. Further, the authors propose equiEPNN as a variant of EPNN that leverages rotation equivariant neural networks and achieves enhanced spectral expressivity. The effectiveness of equiEPNN is demonstrated empirically on MNIST-Superpixel and ZINC datasets.", "questions": "See strengths and weaknesses section.", "limitations": "Limitations have been adequately discussed.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. This work highlights the key limitations of spectral methods for understanding expressivity of GNNs by proving the incompleteness of spectral GNNs. Such observations are valuable to the field. \n2. Theoretical analysis reveals that EPNN's completeness can be achieved, based on eigenvector sparsity patterns. This analysis paves the way for equiEPNN as a novel spectral GNN framework.\n3. equiEPNN achieves superior graph discriminative ability over existing spectral GNNs.\n\n**Weaknesses**\n\n1.  The improved expressivity achieved by equiEPNN hinges on certain sparsity assumptions of the eigenvectors. These assumptions may not hold in many practical scenarios, potentially limiting the utility of the theoretical results. \n2. Empirical validations are limited to MNIST-Superpixel and ZINC. The generality of the findings across diverse graph types, especially those prevalent in real-world applications (e.g., social networks, biological graphs), remains to be further explored.", "was_revised": false, "final_justification": "", "rebuttal": "We wish to thank the reviewer for recognizing our incompleteness results are valuable to the community and appreciating the novelty of equiEPNN. We understand the concerns raised are due to misunderstandings and insufficient empirical evaluation, and we believe we have addressed these issues below:\n\n### 1. Sparsity Assumptions and Theoretical Completeness\n>  The improved expressivity achieved by equiEPNN hinges on certain sparsity assumptions of the eigenvectors. These assumptions may not hold in many practical scenarios, potentially limiting the utility of the theoretical results.\n\n **Our theoretical results point to fundamental limitations of previous spectral methods while showing equiEPNN can, to a certain extent, bypass these sparsity limitations.** equiEPNN *is able* to distinguish among a pair of graphs that violate the sparsity assumptions, see Corollary 1 in the manuscript, while EPNN is unable to distinguish this pair.\n \n Nonetheless, we did not claim that equiEPNN is complete in the simple spectrum case, and actually we have recently been able to find a counter example showing that this is not the case. This new result is described in some detail in Answer 5 to reviewer BrRb, and will be incorporated into the camera ready of the paper, if accepted.\n\nThe main importance of these theoretical results, in our view, is in pointing out the shortcomings of prevalent spectral methods, which are not complete even in the simple spectrum case, and showing that their expressivity can be improved with a simple modification, which does not increase the model complexity. We believe these observations will lead to additional improvements, and ultimately to spectral models which are complete in the simple spectrum case.\n\n### 2. Limited Empirical Validation\n\n> Empirical validations are limited to MNIST-Superpixel and ZINC. The generality of the findings across diverse graph types, especially those prevalent in real-world applications (e.g., social networks, biological graphs), remains to be further explored.\n\n**To address this concern, we introduce further benchmarks below.** \n\nThe first benchmark we add is a standard regression task on the ZINC dataset of molecular graphs (in the manuscript, we tested eigenvector canonicalization on this same dataset). It has 12000 graphs with a 23.16 average number of nodes. We compare ourselves to leading methods with the standard ~500K parameter budget and find that our method attains the best results:\n\n##### Graph regression results on ZINC with a parameter budget of ~500K\n\n| Category | Method | test MAE |\n|----------|--------|----------|\n| **MPNN** | GIN [Xu et al.] | 0.526±0.051 |\n|          | GraphSage [Hamilton et al.] | 0.398±0.002 |\n|          | GAT [Veličković et al.] | 0.384±0.007 |\n|          | GCN [Kipf et al.] | 0.367±0.011 |\n|          | MPNN (sum) [Gilmer et al.] | 0.145±0.007 |\n|          | PNA [Corso et al.] | 0.142±0.010 |\n| **Spectral** | GT [Dwivedi et al.] | 0.226±0.014 |\n|              | GatedGCN-PE [Bresson et al.] | 0.214±0.006 |\n|              | SAN [Kreuzer et al.] | 0.139±0.006 |\n|              | GraphormerSLIM [Ying et al.] | 0.122±0.006 |\n|              | EPNN [Gai et al.] | .103 ± .006 |\n|              | **equiEPNN (Ours)** | **0.0987 ± 0.0014** |\n\nThe second benchmark we add is a molecular property prediction task,  OGBG-MOLPCBA, which is larger with 437,929 graphs and an average of 26 nodes per graph. The results are shown below:\n\n\n##### Property prediction results on OGBG-MOLPCBA\n\n| Model | #param | AP ↑ |\n|-------|---------|------|\nChebNet | 1475K | 0.2306 ± 0.0016|\nGIN+FLAG | 1923K | 0.2395 ± 0.004 |\nGCN+virtual node+FLAG | 2017K | 0.2483 ± 0.0037|\n| equiEPNN | 2665K | **0.2682 ± 0.003** |\n\nWe compare to a leading spectral approach, ChebNet, and message-passing variants with similar parameter count. equiEPNN performs strongly in comparison with leading models.\n\n---\n\n\n### Epilogue\nWe hope this response has addressed your concerns. If so, we would appreciate if you would consider updating your score. If there are any remaining issues or points needing clarification, we would be happy to address them."}, {"review_id": "L3W7kV6Gp4", "reviewer": "Reviewer_BrRb", "summary": "The paper investigates the interesting question of whether spectral features (e.g., eigenvectors of the graph Laplacian matrix) can improve the expressivity of a graph neural network (GNN). In particular, in the case of a simple spectrum (i.e., eigenvalues with multiplicity no larger than 1), the authors prove that Eigenspace Projection GNNs (EPNN) are still incomplete. EPNN would be complete for a simple spectrum if there is an additional sparsity requirement on the eigenvectors. The authors then propose equiEPNN that provably improves the expressivity of EPNN. Whether equiEPNNs are complete for a simple spectrum remains an open question.", "questions": "1. Clarify whether the eigenvalue multiplicity in question is geometric or algebraic. Does this matter and why?\n\n2. Explain why the obsession on the simple spectrum case, given that the main result is a negative one--that even in this case, EPNNs are not complete.\n\n3. Explain whether the degree of freedom in choosing eigenvectors that span eigen-subspace corresponding to eigenvalues of multiplicity >1 can be exploited, so that the chosen eigenvectors behave as if they are eigenvectors of the simple spectrum case. (The deeper question is what is intrinsically different about the complex spectrum case--eigenvalues or eigenvectors--that the authors chose not to analyze it.)\n\n4. Explain whether the sparsity condition on the eigenvectors required for EPNNs to be complete in the simple spectrum case can be checked in linear time for a given graph, thus justifying the practicality of the proposal for large graphs.", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Positional encoding is now commonly used in GNNs, and it's theoretically interesting to study how/whether spectral features really improve expressivity of GNNs fundamentally. The paper is overall well written and theoretically strong. IMHO, the paper is a nice contribution to the GNN field. The following are weaknesses detected by the reviewer (who admittedly does not work directly in the GNN field).\n\n1. There are two notions of eigenvalue multiplicity: algebraic and geometric. Though the two are related (geometric multiplicity <= algebraic multiplicity), they are not the same. The authors ought to make clear which one they are referring to.\n\n2. The main result is actually a negative one: that EPNNs are NOT complete EVEN in the simple spectrum case. Whether EPNNs are complete in the complex case when eigenvalues have multiplicity > 1 is not even addressed. This begs the question of whether dividing the study into simple case (distinct eigenvalues) and complex case (eigenvalues with multiplicity > 1) is meaningful and worthwhile. \n\n3. For the complex case when eigenvalues have multiplicity > 1, the construction of eigenvectors that span the eigen-subspaces (corresponding to eigenvalues of multiplicity >1) is non-unique (as long as they are orthonormal and span the eigen-subspaces). Using this degree of freedom in eigenvector construction, it is not clear eigenvectors can be chosen so that they behave as if they are eigenvectors in the simple spectrum case. \n\n4. Full eigen-decomposition has complexity O(N^3) in the worst case. So practically, the sparsity requirement for eigenvectors to ensure EPNNs are complete for the simple spectrum case cannot be checked in linear time. So the practicality of the proposed method appears questionable.\n\n5. While the author proposed equiEPNN that has expressivity strictly better than EPNN in theory, whether equiEPNNs are complete in the simple spectrum case remains open. While the authors demonstrated equiEPNNs' better performance empirically in some datasets, theoretically this is still unsatisfying.", "was_revised": true, "final_justification": "The authors have addressed my concerns in detail. The weakness of the paper remains that the key theoretical result is a negative one, and the computation complexity of the method (requiring full eigen-decomposition) remains high, limiting its practicality. I am raising my rating to accept.", "rebuttal": "We highly appreciate that the reviewer found the paper well-written and theoretically strong. We believe that we address the reviewer's concerns regarding the paper's focus and **resolve the open question regarding the completeness of equiEPNN.**\n\n### 1. Eigenvalue Multiplicity Clarification\n> Clarify whether the eigenvalue multiplicity in question is geometric or algebraic. Does this matter and why?\n\n In line 108, we assume our matrices are diagonalizable, and for such matrices, the algebraic and geometric eigenvalue multiplicities are equal. The various notions of Graph Laplacians are typically self-adjoint, and thus diagonalizable over the real numbers.\n\n### 2. Focus on the Simple Spectrum Case\n> Explain why the obsession on the simple spectrum case, given that the main result is a negative one--that even in this case, EPNNs are not complete.\n\nThe focus on the simple spectrum case is based on the classical reference [2] (according to the numbering in our submission) which shows that when restricted to graphs with eigenmultiplicity m, graph isomorphism can be solved in $O(n^{2m+c})$ time, where n is the number of nodes and c is a constant related to the computational cost of computing the eigendecomposition. **This suggests that the simple spectrum case is the easiest, and as the eigenmultiplicity m increases the problem becomes harder.** Ultimately, we believe the GNN community should be able to design spectral-GNN models which are complete up to eigenmultiplicity m, where the larger m is, the more expressive the model. Our results show that we are still far from there, as standard spectral GNN are not complete even for m=1.\n\n### 3. Handling Eigenvalue Multiplicity\n> Explain whether the degree of freedom in choosing eigenvectors that span eigen-subspace corresponding to eigenvalues of multiplicity >1 can be exploited, so that the chosen eigenvectors behave as if they are eigenvectors of the simple spectrum case. (The deeper question is what is intrinsically different about the complex spectrum case--eigenvalues or eigenvectors--that the authors chose not to analyze it.)\n\nFor graphs with multiple repeating eigenvalues, it is indeed unclear whether there is a good canonical choice of an eigenbasis, up to sign ambiguity. Therefore,\n**handling eigenvectors of high order eigenspaces requires invariant features for each eigenspace. This is already fully incorporated into equiEPNN.** We use the elegant method from [Huang et al.] which, for given nodes $i,j$  considers pairwise invariant features of the form $\\sum_{s=1}^n f(\\lambda_s)v_i[s]v_j[s]$. These features do not depend on the choice of eigenvectors inside each eigenspace, and are invariant regardless of the eigenmultiplicity. In the simple spectrum case they have equivalent discrimination power to the formulation we present in our submission. This is explained in more detail in our answer to Question 3 of reviewer nt25. Regarding the deeper question- we hope we answered this in our response to question 2, we'd be happy to discuss further if this answer does not address what you meant.\n\n[Huang et al.] On the Stability of Expressive Positional Encodings for Graphs, Huang et al. ICLR 2024\n\n### 4. Checking the Sparsity Conditions\n> Explain whether the sparsity condition on the eigenvectors required for EPNNs to be complete in the simple spectrum case can be checked in linear time for a given graph, thus justifying the practicality of the proposal for large graphs.\n\n**Spectral GNNs must compute the eigendecomposition (e.g. for positional encoding), thus no further computation time is required to check the sparsity conditions.** We are not aware of a method that checks the sparsity assumptions and bypasses spectral eigendecomposition. However, note that Spectral GNNs compute the eigendecomposition in any case, so this inquiry is more on the practicality of Spectral GNNs in general. \n\nIn this context, it is worth noting that positional encoding via spectral methods is rather popular. Moreover, while the computational overhead of eigendecomposition is $O(n³)$, it only needs to be computed once as a preprocessing step, and not during training, and this complexity can be mitigated by considering only the top-k eigenvectors, and exploiting the sparsity of the graphs for eigendecomposition via the power method.\n\nWe provide the running time of computing the eigendecompositions of various datasets, including those with large graphs, below. \n\n| Dataset | OGBG-PPA | ZINC | MNIST | ogbg-molpcba |  COCO-SP | Peptides-func | \n|---------|----------|------|-------|--------------|--------------|---------|\n| Task type | Classification | Regression | Classification | Classification | Node Classification | Classification |\n| Total graphs | 158,100 | 12,000 | 70,000 | 437,929 | 123,286 | 15,535 | \n| Avg nodes | 243.4 | 23.16 | 75 | 26.0 |  476.88 | 150.94 | \n| PE precompute | 45.26min | 23s | 96s | 8.33min | 1h 34min | 73s |\n\nRunning times are taken from [Rampášek et al.] and were evaluated on an NVIDIA  A100 GPU. \n\n[Rampášek et al.] Rampášek et al.. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems.\n\n### 5. Incompleteness of equiEPNN\n\n> While the author proposed equiEPNN that has expressivity strictly better than EPNN in theory, whether equiEPNNs are complete in the simple spectrum case remains open. While the authors demonstrated equiEPNNs' better performance empirically in some datasets, theoretically this is still unsatisfying\n\n**We have recently proven that equiEPNN is incomplete on graphs with a simple spectrum.** We also felt the need to address this issue, and indeed a few weeks ago we were able to show that equiEPNN is incomplete over simple spectrum graphs. This is proven by this counterexample:\n\n**Construction:** Consider the subgroup $H \\\\leq \\\\{-1,1\\\\}^3$ defined by\n$$H = \\\\{s \\\\in \\\\{-1,1\\\\}^3 : s_1 s_2 s_3 = 1\\\\}.$$\n\nLet $T \\\\in \\\\mathbb{R}^{4 \\\\times 3}$ be the matrix whose rows enumerate the elements of $H$:\n$$T = \\\\begin{pmatrix}\n1 & 1 & 1\\\\\\\\\n1 & -1 & -1\\\\\\\\\n-1& -1 & 1\\\\\\\\\n-1& 1 & -1\n\\\\end{pmatrix}.$$\n\nNote that $\\\\text{Aut}(T) = H$.\n\nDefine index sets $I_1=\\\\{1,2,3\\\\}$, $I_2=\\\\{3,4,5\\\\}$, $I_3=\\\\{2,4,6\\\\}$, $I_4=\\\\{1,5,6\\\\} \\\\subset [6]$ satisfying $|I_j \\\\cap I_k| = 1$ for all $j \\\\neq k$. For each $j$, let $T[I_j] \\\\in \\\\mathbb{R}^{4 \\\\times 6}$ be the matrix obtained by placing the columns of $T$ in positions specified by $I_j$ and zeros elsewhere.\n\nDefine the counterexample matrices:\n$$X = \\\\begin{pmatrix}\nT[I_1]\\\\\\\\\nT[I_2]\\\\\\\\\nT[I_3]\\\\\\\\\nT[I_4]\n\\\\end{pmatrix} \\\\in \\\\mathbb{R}^{16 \\\\times 6}, \\\\quad Y = \\\\begin{pmatrix}\nT[I_1] \\\\odot q\\\\\\\\\nT[I_2]\\\\\\\\\nT[I_3]\\\\\\\\\nT[I_4]\n\\\\end{pmatrix} \\\\in \\\\mathbb{R}^{16 \\\\times 6},$$\n\nwhere $q = (-1,1,1,1,1,1) \\\\in \\\\{-1,1\\\\}^6$.\n\n\n**Theorem:** The matrices $X,Y$ satisfy: (1) $X$ is not isomorphic to $Y$ under any isomorphism, (2) $X$ and $Y$ are indistinguishable by equiEPNN, and (3) both admit an extension to proper eigendecompositions.\n\nTo explain this theorem, we recall that for matrices $X,Y \\\\in \\\\mathbb{R}^{n \\\\times K}$, we say that $X,Y$ are isomorphic if they are related by a permutation in $S_n$ and a multiplication of each of the $K$ columns by a sign $s_k \\\\in \\\\{-1,1 \\\\}$. An extension to a proper eigendecomposition means that this example can be lifted to a pair of orthonormal  $n \\\\times n$ matrices having the same properties, and hence that these matrices are realizable as eigendecompositions of an appropriate symmetric matrix. \n\nWe will add this discussion, and the full proof, to the camera ready version.\n\nWe wish to stress that while  equiEPNN is incomplete over simple spectrum graphs, it is still  provably more expressive than EPNN.\n\n\n\n## Additional Experiments\nWe ran additional experiments, at the request of some of the other reviewers. On the molecular property regression task for the ZINC dataset, we obtain the following results:\n\n##### Graph regression results on ZINC with a parameter budget of ~500K\n\n| Category | Method | test MAE |\n|----------|--------|----------|\n| **MPNN** | GIN [Xu et al.] | 0.526±0.051 |\n|          | GraphSage [Hamilton et al.] | 0.398±0.002 |\n|          | GAT [Veličković et al.] | 0.384±0.007 |\n|          | GCN [Kipf et al.] | 0.367±0.011 |\n|          | MPNN (sum) [Gilmer et al.] | 0.145±0.007 |\n|          | PNA [Corso et al.] | 0.142±0.010 |\n| **Spectral** | GT [Dwivedi et al.] | 0.226±0.014 |\n|              | GatedGCN-PE [Bresson et al.] | 0.214±0.006 |\n|              | SAN [Kreuzer et al.] | 0.139±0.006 |\n|              | GraphormerSLIM [Ying et al.] | 0.122±0.006 |\n|              | EPNN [Gai et al.] | .103 ± .006 |\n|              | **equiEPNN (Ours)** | **0.0987 ± 0.0014** |\n\nThese results show that equiEPNN outperforms EPNN and other models on this task. \n\nThe second benchmark we add is a molecular property prediction task,  OGBG-MOLPCBA, which is larger with 437,929 graphs and an average of 26 nodes per graph. The results are shown below:\n\n\n##### Property prediction results on OGBG-MOLPCBA\n\n| Model | #param | AP ↑ |\n|-------|---------|------|\nChebNet | 1475K | 0.2306 ± 0.0016|\nGIN+FLAG | 1923K | 0.2395 ± 0.004 |\nGCN+virtual node+FLAG | 2017K | 0.2483 ± 0.0037|\n| equiEPNN | 2665K | **0.2682 ± 0.003** |\n\nIn this experiment we compare to a leading spectral approach, ChebNet, and message-passing variants with similar parameter count. \n\n---\n### Epilogue\nWe hope this response has addressed your concerns. If so, we would appreciate if you would consider updating your score. If there are any remaining issues or points needing clarification, we would be happy to address them."}, {"review_id": "BKltYrWbPI", "reviewer": "Reviewer_nt25", "summary": "This paper presents a rigorous theoretical and empirical investigation into the expressive limitations of Spectrally-enhanced Graph Neural Networks (SGNNs), particularly those that fall within the Eigenspace Projection Neural Network (EPNN) framework. After demonstrating that even on graphs with a simple spectrum (distinct eigenvalues), EPNNs can be provably incomplete, the authors introduce a more expressive variant called equiEPNN, which augments the feature update with equivariant components inspired by point cloud neural networks. Theoretical claims are supported by experiments on datasets like MNIST Superpixel and ZINC.", "questions": "- What is the empirical runtime and memory overhead of equiEPNN versus EPNN on graphs? for example in case of $n>10^4$ nodes and $K>64$ eigenvectors?\n- How prevalent are the sparse-eigenvector failure modes in large real-world graphs (e.g., social networks, protein interactions)?\n- Can equiEPNN handle repeated eigenvalues (higher multiplicity)? If not, what obstacles arise?\n- How does equiEPNN perform empirically compared to modern spectral GNNs on standard benchmarks? It would be valuable to assess the practical impact of the proposed solution in real-world scenarios.", "limitations": "There is no dedicated discussion on the limitations of the method. However, the authors mention that they have not fully determined the conditions under which completeness is achieved for graphs with a simple spectrum.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n- **Theoretical Rigor:** Formal definitions of simple spectra and sign-invariance, with clear, correct proofs of incompleteness and conditional completeness.  \n- **Constructive Enhancement:** equiEPNN is a well-motivated, low-overhead extension that provably separates previously indistinguishable graphs.  \n- **Insightful Demonstration:** The use of eigendecomposition clearly illustrates the specific limitations of EPNN, offering a deep and constructive understanding of its expressive shortcomings rather than a superficial critique.  \n\n---\n\n### Major Weaknesses\n\n- **Narrow Experimental Validation:** Only toy datasets (MNIST Superpixel, ZINC) are used, with mostly simple spectra; no large real-world graphs (social, biological) are evaluated.  \n- **Unquantified Overhead:** The computational and memory costs of equiEPNN’s equivariant updates are not measured or analyzed.  \n- **Limited Scope:** The analysis is restricted to graphs with a simple spectrum (all eigenvalues distinct), yet real-world networks, such as social, biological, and chemical graphs, often feature repeated eigenvalues. By not addressing these more complex cases, the practical applicability of the method is significantly limited.  \n- **Insufficient Baselines:** Despite the strong theoretical insights, it remains unclear how this framework performs compared to other GNN architectures, such as Transformer-based GNNs (e.g., Graphormer [1]) or 1-WL–based models (e.g., GIN [2]). Without these comparisons, the real-world utility of the approach is uncertain.\n\n[1] Ying, Chengxuan, et al. \"Do transformers really perform badly for graph representation?.\" Advances in neural information processing systems 34 (2021): 28877-28888.\n[2] Xu, Keyulu, et al. \"How powerful are graph neural networks?.\" International Conference on Learning Representations, 2019", "was_revised": true, "final_justification": "After carefully reviewing the authors' responses, as well as those provided to the other reviewers, I believe this paper can be accepted.", "rebuttal": "We appreciate the reviewer's recognition of the paper's theoretical rigor and the constructive proof of the expressive limitations of EPNN. We believe the reviewer's concerns are mostly due to expecting further empirical evaluation.  We address this concern in the following response.\n\n### 1. Runtime and Memory Overhead\n> What is the empirical runtime and memory overhead of equiEPNN versus EPNN on graphs? for example in case of $n>10^4$ nodes and $K>64$ eigenvectors?\n\n**equiEPNN has a marginal memory overhead and mild computational overhead versus EPNN.** Firstly, note that equiEPNN is built on top of EPNN and its additional computational complexity is from its geometric update step. The complexity of this geometric update step of equiEPNN is at most n², which is also the running time of EPNN, thus their asymptotic running time are the same up to a constant. \n\nHere's a table of empirical running time and memory overhead on ZINC: \n\n\n| MODEL | # Params | Compute Time (Avg. Seconds Per Epoch) |\n|-------|---------|----------|\n|PPGN| 28,955 | 9.96 |\n| equiEPNN | 31,339 | 7.62 |\n| EPNN | 31,215 | 6.43 |\n\n\nWe see that EPNN and equiEPNN require almost the same number of parameters, while equiEPNN requires about 18.5 % more compute time. PPGN [Maron et al.], which has cubic complexity, is significantly (54 %) more expensive computationally than EPNN. \n\n### 2. Sparse Eigenvector Failure Modes \n> How prevalent are the sparse-eigenvector failure modes in large real-world graphs (e.g., social networks, protein interactions)? \n\n**We find that the sparsity conditions for the completeness of EPNN usually do not hold, justifying the necessity of equiEPNN.**\n\nFor large real-world graphs, we choose the Cornell dataset, which consists of web pages and hyperlinks between them,  and PPI, a benchmark protein-protein-interaction dataset. Empirically, we find that the (single) graph in the Cornell dataset does not meet any of the sparsity conditions, despite 91.7 % of its eigenspaces being one-dimensional. In PPI, while only 86 of the 31,281 eigenspaces are more than one-dimensional (i.e. 99.9 % are one-dimensional), none of the sparsity conditions hold. Thus, despite the graphs being close to having a simple spectrum, EPNN may be incomplete (miss crucial information) on them, due to the graphs' sparsity. \n\nThis analysis reveals the need for models that can handle sparse eigendecompositions more effectively. The equiEPNN model directly addresses this challenge, as proven in Corollary 1.\n\n### 3. Handling Repeated Eigenvalues\n> Can equiEPNN handle repeated eigenvalues (higher multiplicity)? If not, what obstacles arise?\n\n**equiEPNN can naturally be extended to handle eigenvectors of eigenvalues of higher multiplicity, using the elegant formulation defined in [Huang et al.]. Thus, equiEPNN is applicable to any eigenmultiplicity and this is already implemented in the code.** \n\nRecall that the update steps of equiEPNN are defined as\n\n$$h_i^{(t+1)} = \\\\text{UPDATE}_{(t,1)}\\\\left(h_i^{(t)}, \\\\tilde{\\\\lambda}, \\\\left\\\\{(h_j^{(t)}, v_i^{(t)} \\\\odot v_j^{(t)}) \\\\mid j = 1, \\\\ldots, n\\\\right\\\\}\\\\right)$$\n\n$$v_i^{(t+1)} = v_i^{(t)} + \\\\sum_{j=1}^{n} v_j^{(t)} \\\\odot \\\\text{UPDATE}_{(t,2)}\\\\left(h_i^{(t)}, h_j^{(t)}, v_i^{(t)} \\\\odot v_j^{(t)}\\\\right)$$\n\nwhere the $k$-th coordinate of $v_i^{(t)} \\\\odot v_j^{(t)}$ is the product of the $i,j$ coordinates of the $k$-th eigenvector. In the simple spectrum case, this operation is sign invariant. In the general setting, we consider invariants of the form $\\\\sum_{s =1}^n f(\\\\lambda_s)v_i[s]v_j[s]$. These functions are invariant, no matter what the eigenmulitplicity is. When the eigenmultiplicity is one, the elementwise product operation at the $s$ coordinate can be obtained by choosing $f$ such that $f(\\\\lambda_s)=1$ but $f(\\\\lambda_j)=0$ for $j \\\\neq s$. Thus, this method is equivalent to the one described in the paper in terms of the separation power when restricted to simple spectrum graphs.  \n\n\n[Huang et al.] On the Stability of Expressive Positional Encodings for Graphs, Huang et al. ICLR 2024\n\n### 4. Empirical Performance of equiEPNN\n> Question: How does equiEPNN perform empirically compared to modern spectral GNNs on standard benchmarks? It would be valuable to assess the practical impact of the proposed solution in real-world scenarios.\n\n**We add comparisons on two benchmarks, proving the effectiveness of equiEPNN.** Below we compare equiEPNN to leading models on a standard regression task for molecular graphs from the  ZINC dataset, using models with 500K free model parameters:\n##### Graph regression results on ZINC with a parameter budget of ~500K\n\n| Category | Method | test MAE |\n|----------|--------|----------|\n| **MPNN** | GIN [Xu et al.] | 0.526±0.051 |\n|          | GraphSage [Hamilton et al.] | 0.398±0.002 |\n|          | GAT [Veličković et al.] | 0.384±0.007 |\n|          | GCN [Kipf et al.] | 0.367±0.011 |\n|          | MPNN (sum) [Gilmer et al.] | 0.145±0.007 |\n|          | PNA [Corso et al.] | 0.142±0.010 |\n| **Spectral** | GT [Dwivedi et al.] | 0.226±0.014 |\n|              | GatedGCN-PE [Bresson et al.] | 0.214±0.006 |\n|              | SAN [Kreuzer et al.] | 0.139±0.006 |\n|              | GraphormerSLIM [Ying et al.] | 0.122±0.006 |\n|              | EPNN [Gai et al.] | 0.103 ± .006 |\n|              | **equiEPNN (Ours)** | **0.0987 ± 0.0014** |\n\nResults of other models taken from [Ying et al.] and [Gai et al.]. We see that equiEPNN outperforms all other models for this task. \n\n\nThe second benchmark we add is a molecular property prediction task,  OGBG-MOLPCBA, which is larger with 437,929 graphs and an average of 26 nodes per graph. The results are shown below\n\n##### Property prediction results on OGBG-MOLPCBA\n| Model | #param | AP ↑ |\n|-------|---------|------|\nChebNet | 1475K | 0.2306 ± 0.0016|\nGIN+FLAG | 1923K | 0.2395 ± 0.004 |\nGCN+virtual node+FLAG | 2017K | 0.2483 ± 0.0037|\n| equiEPNN | 2665K | **0.2682 ± 0.003** |\n\nHere we compare to a leading spectral approach, ChebNet, and message-passing variants with a similar parameter count.\n\n\n### Epilogue\nWe hope this response has addressed your concerns. If so, we would appreciate if you would consider updating your score. If there are any remaining issues or points needing clarification, we would be happy to address them."}, {"review_id": "N3MpPeqI0S", "reviewer": "Reviewer_AgJS", "summary": "This paper studies the limitations of spectral GNNs on graphs with a simple spectrum (distinct eigenvalues). It shows that Eigenspace Projection GNNs (EPNNs) are not expressive enough to distinguish such graphs. To address this, the authors propose equiEPNN, a sign-equivariant variant that improves expressivity. They provide theoretical proofs and empirical results showing that equiEPNN outperforms EPNN in distinguishing graph structures and canonicalizing eigenvectors.", "questions": "- The proposed equiEPNN assumes access to full eigenvector decomposition, which can be computationally expensive for large graphs. How does the method scale in practice? Is it feasible for datasets like ogbg-ppa large molecule graphs?\n- The paper presents completeness results for EPNN under specific sparsity and automorphism assumptions. How restrictive are these in practice?\n- The proposed method relies on simple spectrum graphs and the sparsity condition outlined in Theorem 2. However, according to the Statistics Analysis in Table 1, most real-world datasets appear to not satisfy both conditions simultaneously.\n- Would it be possible to provide more experimental results on datasets that fully satisfy the above conditions? Additionally, can the proposed method achieve comparable performance on datasets like ENZYMES and PROTEINS, which do not strictly meet the required assumptions?\n- The paper primarily focuses on graph-level tasks and the expressivity of models in distinguishing whole graphs. Have you considered how the proposed equiEPNN performs on node-level tasks, such as node classification or node clustering? Given that spectral methods often rely on global eigenvectors, how would equiEPNN handle localized, node-specific predictions in practice?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n- The paper presents strong theoretical contributions, rigorously proving the incompleteness of spectral GNNs such as EPNN on graphs with a simple spectrum.\n- The proposed equiEPNN method is well-motivated and theoretically grounded, offering a principled improvement through sign-equivariant feature updates.\n- The experimental section, although limited in scope, supports the theoretical claims—especially with ablation studies on MNIST Superpixel and eigenvector canonicalization on ZINC.\n- The paper is well-structured, with a clear flow from problem statement to proposed solution and evaluation. The definitions, assumptions, and theoretical claims are clearly stated, and the key proofs are presented in detail.\n\n\n**Weaknesses:**\n- The empirical evaluation is somewhat narrow in scope and does not include more challenging benchmarks, such as large-scale graph datasets like ogbg-ppa.\n- Some derivations (e.g., the canonicalization pipeline in equiEPNN) could benefit from further implementation or ablation details.\n- The practical implications for broader graph learning tasks (e.g., node classification, link prediction) are not fully explored.\n- The approach assumes access to full eigenvector information, which may be computationally prohibitive on large graphs.\n- While the spectral-equivariant update mechanism is well designed, some elements are conceptually borrowed from point cloud networks. The novelty lies more in adaptation than invention.", "was_revised": true, "final_justification": "The authors conducted a lot of experiments to verify the proposed method from various perspectives. I recommend Accept, as the authors have convincingly addressed the major concerns, and the paper contributes a solid and practical approach.", "rebuttal": "We wish to thank the reviewer for the positive and detailed review. Below we address the issues you raised:\n### 1. Computational Feasability\n\n> Question: The proposed equiEPNN assumes access to full eigenvector decomposition, which can be computationally expensive for large graphs. How does the method scale in practice? Is it feasible for datasets like ogbg-ppa large molecule graphs?\n\n**Eigendecomposition is computationally feasible for ogbg-ppa.** Despite the large number of average nodes and  number of graphs in ogbg-ppa,  158,100 graphs with an average of\t243.4 nodes per graph [OGB Documentation], we can see in the table below the eigendecomposition concludes in approximately 45 minutes, which we feel is reasonable, as this computation is a preprocessing step, which occurs only once during the training procedure.\n\n| Dataset | OGBG-PPA | ZINC | MNIST | ogbg-molpcba |  COCO-SP | Peptides-func | \n|---------|----------|------|-------|--------------|--------------|---------|\n| Task type | Classification | Regression | Classification | Classification | Node Classification | Classification |\n| Total graphs | 158,100 | 12,000 | 70,000 | 437,929 | 123,286 | 15,535 | \n| Avg nodes | 243.4 | 23.16 | 75 | 26.0 |  476.88 | 150.94 | \n| PE precompute | 45.26min | 23s | 96s | 8.33min | 1h 34min | 73s |\n\nWe ran the eigendecomposition for ogbg-ppa on an NVIDIA A40 GPU. The rest of the results are taken from [Rampášek et al.] and were evaluated on an NVIDIA A100 GPU. \n\n[Rampášek et al.] Rampášek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., & Beaini, D. (2022). Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35, 14501-14515.\n\n### 2. Restrictiveness of Assumptions\n> Question: The paper presents completeness results for EPNN under specific sparsity and automorphism assumptions. How restrictive are these in practice?\n\n**In many popular datasets, the assumptions break quite often.** Please note Table 1 in the manuscript features very common datasets, which do not adhere to the sparsity conditions. For example, in ENZYMES only 35.8\\% of the graphs fulfill one of the sparsity conditions. These restrictive conditions prompted us to develop equiEPNN, which alleviates the sparsity of eigendecompositions and is provably more expressive than EPNN.\n\n\n### 3. Performance on Unsatisfactory Datasets\n> The proposed method relies on simple spectrum graphs and the sparsity condition outlined in Theorem 2. However, according to the Statistics Analysis in Table 1, most real-world datasets appear to not satisfy both conditions simultaneously.\n\n**We agree the sparsity conditions in Theorem 2 for the completeness of EPNN do not hold in many real-world dataset. In fact, one of the reasons we introduced equiEPNN is to alleviate this incompleteness.** On the other hand, the simple spectrum presumption, which also applies for our analysis of equiEPNN, may not always hold as well. **Yet, even in highly symmetrical datasets (which tend to have more high dimensional eigenspaces), the frequency of high dimensional eigenspaces is relatively low, thus the utility of equiEPNN practically applies to many datasets.** Concretely, in ENZYMES and PROTEINS (highly symmetrical datasets), the average number of eigenvalues with multiplicity 2 and 3 are only 1.01 and 0.58, and 1.24 and 0.71, respectively. \n\nMore importantly, while our theoretical analysis focuses on simple spectrum graphs, equiEPNN can process graphs with eigenmultiplicity, as mentioned in the response to Reviewer nt25.\n\n\n### 4. More Experiments\n> Would it be possible to provide more experimental results on datasets that fully satisfy the above conditions? Additionally, can the proposed method achieve comparable performance on datasets like ENZYMES and PROTEINS, which do not strictly meet the required assumptions?\n\n**Per your suggestion, we tested out equiEPNN on the PROTEINS and ENZYMES datasets** [Morris et al.]. Below are the results:\n\n|Category | Model | ENZYMES | PROTEINS |\n|-------|-------|---------|----------|\n| **NN** | MLP | 30.8% ± 4.26 | 74.3% ± 4.88 |\n| **MPNN** | GCN | 49.0% ± 4.25 | 75.2% ± 5.11 |\n| | GAT | 54.1% ± 5.15 | 75.9% ± 4.26 |\n| | GIN | 55.8% ± 5.23 | 76.1% ± 3.97 |\n|**3-WL** | PPGN | 55.2% ± 5.44 | 77.2% ± 4.53 |\n| **Spectral**| ChebNet | 63.8% ± 7.92 | 76.4% ± 5.34 |\n| | GNML1 | 54.9% ± 5.97 | 75.8% ± 4.93 |\n| | equiEPNN (Ours) | 57.2% ± 5.68 | 76.03% ± 4.36 |\n\n\nOn PROTEINS, we see that equiEPNN performs en par with the other spectral approaches, and quite close to PPGN, which has cubic complexity. \n\nOn ENZYMES, equiEPNN performs en par with most other methods, even PPGN, except compared to ChebNet, which uses complex Chebyshev interpolation on top of the eigendecomposition.\n\n**Additionally, we tested equiEPNN on a molecular property prediction task,  OGBG-MOLPCBA,** which is larger with 437,929 graphs and an average of 26 nodes per graph. The results are shown below\n\n##### Property prediction results on OGBG-MOLPCBA\n| Model | #param | AP ↑ |\n|-------|---------|------|\nChebNet | 1475K | 0.2306 ± 0.0016|\nGIN+FLAG | 1923K | 0.2395 ± 0.004 |\nGCN+virtual node+FLAG | 2017K | 0.2483 ± 0.0037|\n| equiEPNN | 2665K | **0.2682 ± 0.003** |\n\nHere we compare to a leading spectral approach, ChebNet, and message-passing variants with a similar parameter count. We can see that we outperform ChebNet in this setting, and the other MPNN methods.\n\n\n**Furthermore, we tested equiEPNN on ZINC,** where the graphs only partially satisfy one of the sparsity conditions (64.5 %), and we see that equiEPNN improves its empirical performance in comparison with EPNN [Gai et al.] and other leading models.\n\n##### Graph regression results on ZINC with a parameter budget of ~500K\n\n| Category | Method | test MAE |\n|----------|--------|----------|\n| **MPNN** | GIN [Xu et al.] | 0.526±0.051 |\n|          | GraphSage [Hamilton et al.] | 0.398±0.002 |\n|          | GAT [Veličković et al.] | 0.384±0.007 |\n|          | GCN [Kipf et al.] | 0.367±0.011 |\n|          | MPNN (sum) [Gilmer et al.] | 0.145±0.007 |\n|          | PNA [Corso et al.] | 0.142±0.010 |\n| **Spectral** | GT [Dwivedi et al.] | 0.226±0.014 |\n|              | GatedGCN-PE [Bresson et al.] | 0.214±0.006 |\n|              | SAN [Kreuzer et al.] | 0.139±0.006 |\n|              | GraphormerSLIM [Ying et al.] | 0.122±0.006 |\n|              | EPNN [Gai et al.] | .103 ± .006 |\n|              | **equiEPNN (Ours)** | **0.0987 ± 0.0014** |\n\nBelow we further evaluate equiEPNN on ZINC with only 30K free parameters  and **we also evaluate equiEPNN on MNIST-Superpixels, a dataset that almost completely adheres to the completeness conditions of EPNN** (see Table 1 in the paper), with 35K free parameters:\n\n| Category | Model | ZINC | MNIST-SUPERPIXELS |\n|----------|-------|---------|----------|\n| NN | MLP | 0.5869 ± 0.025 | 25.10% ± 0.12 |\n| MPNN | GCN | 0.3322 ± 0.010 | 52.80% ± 0.31 |\n| | GAT | 0.3977 ± 0.007 | 82.73% ± 0.21 |\n| | GIN | 0.3044 ± 0.010 | 75.23% ± 0.41 |\n| 3-WL | PPGN | **0.1589 ± 0.007** | 90.04% ± 0.54 |\n| Spectral | ChebNet | 0.3569 ± 0.012 | **92.08% ± 0.22** |\n| | GNNML1 | 0.3140 ± 0.015 | 84.21% ± 1.75 |\n| | equiEPNN (Ours) | **0.2805 ± 0.019** | 90.32% ± 0.7 |\n\n(bold denotes best overall result, and best result within the spectral category)\n\nWe can see that equiEPNN outperforms most other models, especially on ZINC where the graphs are sparse. On MNIST-SUPERPIXELS, which adheres to the completeness conditions, competing models are also able to capture the spectral information. In both cases, equiEPNN's capturing of rich spectral information allows it to perform en par with models with PPGN, a model with a cubic running time complexity.\n\n\n\n### 5. Node-Level Tasks\n> The paper primarily focuses on graph-level tasks and the expressivity of models in distinguishing whole graphs. Have you considered how the proposed equiEPNN performs on node-level tasks, such as node classification or node clustering? Given that spectral methods often rely on global eigenvectors, how would equiEPNN handle localized, node-specific predictions in practice?\n\nIn this manuscript, we focused on the expressive power of spectral GNNs in terms of distinguishing among graphs, thus we believe node-wise prediction is out of scope for this paper. This is an excellent direction for future research, which we intend to look into. \n\n### Epilogue\nWe hope this response has addressed your concerns. If so, we would appreciate if you would consider updating your score. If there are any remaining issues or points needing clarification, we would be happy to address them."}]

Author rebuttal:

Meta-review: This paper shows that many Spectrally-enhanced Graph Neural Networks (SGNNs), which use features like eigenvectors to tell graphs apart, are surprisingly incomplete even on graphs with a simple spectrum (distinct eigenvalues). To address this limitation, the authors introduce equiEPNN, a new model inspired by equivariant neural networks that provably enhances the expressive power on these types of graphs. The study empirically confirms these theoretical claims, showing that equiEPNN improves performance and can also be used to resolve the inherent sign ambiguity in eigenvector-based positional encodings on real-world datasets.


Overall, the reviewers were positive about the paper (as highlighted in the authors' final comments:"strong theoretical contributions, rigorously proving the incompleteness of spectral GNNs" (Reviewer AgJS), calling the paper "theoretically strong...a nice contribution to the GNN field" (Reviewer BrRb), with "valuable" incompleteness results (Reviewer aLjK), and that our model "equiEPNN is a well-motivated, low-overhead extension" (Reviewer nt25). The main focus of the discussion during the rebuttal area seemed primarily centered around experimental results (with reviewers arguing that too few experiments had been performed by the authors, or that no large scale dataset had been used). The authors have adequately addressed these remarks, adding more experimental results and showcasing their method on a OGBG benchmarks. Some concerns remain on the scalability of this method, but overall, the reviewers agree that this will constitute a nice addition.
Decision: Accept (spotlight)