AdaSpec: Adaptive Spectrum for Enhanced Node Distinguishability
Authors: Fangbing Liu
Qing Wang
Venue: ICLR 2026 Poster (2026)
Keywords: spectral graph neural networks
symmetry on graph
permutation equivalence
node distinguishability
Primary area: learning on graphs and other geometries & topologies
TL;DR: An adaptive plug-in graph matrix generation module to enhance the node distinguishability of spectral graph neural networks.

Abstract: Spectral Graph Neural Networks (GNNs) achieve strong performance in node classification, yet their node distinguishability remains poorly understood. We analyze how graph matrices and node features jointly influence node distinguishability. Further, we derive a theoretical lower bound on the number of distinguishable nodes, which is governed by two key factors: distinct eigenvalues in the graph matrix and nonzero frequency components of node features in the eigenbasis. Based on these insights, we propose AdaSpec, an adaptive graph matrix generation module that enhances node distinguishability of spectral GNNs without increasing the order of computational complexity. We prove that AdaSpec preserves permutation equivariance, ensuring that reordering the graph nodes results in a corresponding reordering of the node embeddings. Experiments across eighteen benchmark datasets validate AdaSpec's effectiveness in improving node distinguishability of spectral GNNs.

Published as a conference paper at ICLR 2026
ADASPEC: ADAPTIVE SPECTRUM FOR ENHANCED NODE DISTINGUISHABILITY
Fangbing Liu & Qing Wang
The Australian National University fangbing liu,, qing. wang@anu edu edu
ABSTRACT
Spectral Graph Neural Networks (GNNs) achieve strong performance in node clas- sification, yet their node distinguishability remains poorly understood. We analyze how graph matrices and node features jointly influence node distinguishability. Fur- ther, we derive theoretical lower bound on the number of distinguishable nodes, which is governed by two key factors: distinct cigenvalues in the graph matrix and nonzero frequency components of node features the eigenbasis. Based on these insights, we propose AdaSpec, an adaptive graph matrix generation module that enhances node distinguishability of spectral GNNs without increasing the order of computational complexity. We prove that AdaSpec preserves permutation equivari- ance, ensuring that reordering the graph nodes results in corresponding reordering of the node embeddings. Experiments across eighteen benchmark datasets validate AdaSpec's 's effectiveness in improving node distinguishability of spectral GNNs. Code: https//gtthhb.cmm//iii33///////
INTRODUCTION
Graph Neural Networks (GNNs) have become increasingly popular for graph learning tasks due to their strong performance in tasks such as graph and node classification (Kipf & Welling 2017
Xu al. 2019 He et al. 2021 Wang & Zhang 2022 Qin et al. 2025). Among the various GNN models, spectral GNNs represent prominent class that transforms graph signals into the spectral domain, enabling graph filters process information for downstream tasks. Although numerous spectral GNNs have been proposed, their node distinguishability remains insufficiently understood. Node distinguishability refers to the capacity of GNN to map topologically or feature-different nodes to different embeddings. These models typically utilize different graph matrices, such as the normalized adjacency or Laplacian matrix. Further, the distribution of node features across the graph plays crucial role in model performance (He et al. 2022b Platonov et al. 2023). To the best of our knowledge, no existing work has systematically analyzed the interaction between the graph matrix and node features in determining node distinguishability in spectral GNNs.
Spectral GNNs with state-of-thed of-thh-rrtttt art performance generally follow the form:
X) ge fM) (X)),
where M E TR represents the graph matrix (such as the Laplacian or adjacency matrix), X E Raxh denotes the node feature matrix, ge (M) Σk= (MT)(M) is the graph convolution function parameterized by θ {0x) o and (-) denotes the k-th polynomial basis. The term fw (X) represents the feature transformation function parameterized by W. Spectral GNNs learn meaningful node features by optimizing W. projecting them into the spectral domain. By adjusting O, spectral GNNs filter out unnecessary information and enhance useful information for downstream tasks.
While this formulation illustrates how spectral GNNs process node features through graph convolution, their capacity for node distinguishability remains inadequately understood. This leads to a fundamental question: how does the interaction between the graph matrix M and the node features X projected into the spectral domain affect the node distinguishability of spectral GNNs? In this work, we demonstrate that node distinguishability is influenced by the eigenvalue multiplicity and the missing frequency components of node features in the eigenbasis of the graph matrix. Further, derive a theoretical lower bound on the number of nodes that can be distinguished by spectral GNNs, given a specific graph matrix and node features.

---

Published as a conference paper at ICLR 2026
Motivated by our theoretical analysis of node distinguishability, we introduce AdaSpec, an adaptive graph matrix generation module that optimizes the graph matrix to maximize its lower bound on node distinguishabiltty. Designed plug-in, AdaSpec can be scamlessly integrated into any spectral GNN to enhance node distinguishability. Moreover, spectral GNNs augmented with AdaSpec preserve permutation equivariance, ensuring that reordering graph nodes results in corresponding reordering of node embeddings. Finally, AdaSpec maintains the graph's 's connectivity, guaranteeing that the learned embeddings accurately reflect the underlying graph structure.
We evaluate our approach on eighteen benchmark node classification datasets, covering range of small- and large-scale graphs with both homophilic and heterophilic structures in Section 6 Spectral GNNs with AdaSpec achieve notable performance improvements on heterophilic graphs, while maintaining or slightly improving accuracy on homophilic ones. These results validate the effectiveness of AdaSpec in boosting node distinguishability.. Additionally, experimental results show that the order of time complexity of spectral GNNs with and without AdaSpec are the same.
2 RELATED WORKS
Spectral GNNs perform graph convolution by applying filters in the spectral domain for representation learning. Based on the design of their graph filters, spectral GNNs can be categorized into polynomial (He al. 2022a 2021) and rational types (Levie al.. 2019 Bianchi iet al. 2021 Li et al. 2025). Polynomial graph filters are computationally efficient and localized in the vertex domain (Hammond et al. 2009 Defferrard et al. 2016), and this paper focuses on their analysis. Recent studies primarily investigate how different polynomial bases affect spectral GNN performance, for instance, ChebNet, ChebNetll, JacobiConv. BernNet. GPRGNN and GLN (Defferrard al.) 2016: He et al. 2022a Wang & Zhang, 2022 He et al.) 2021: Chien et al. 2021 Li & Wang 2024).
Spectral GNNs.
Further, FavardGNN, UniFilter and PolyCF learn polynomial bases that adapt to different graph
structures (Guo & Wei
2023
Huang et al. 2024. Qin et al.) 2025).
Above spectral GNNs use fixed graph matrices like normalized adjacency or Laplacian matrices. While research has focused effect of polynomial bases on performance of spectral GNNs, we demonstrate the critical role of the graph matrix. We analyze how the interaction between the graph matrix and node features affects spectral GNN performance. Further, we propose AdaSpec, graph matrix generation module to enhance the performance of spectral GNNs.
Expressive Power of Spectral GNNs The expressive power of GNNs in graph classification has been extensively analyzed through the Weisseiler-Lehman (WL) test (Li & Leskovee. 2022. Zhang et al., 2023; Jin et al. 2025), which are algorithms determining graph isomorphism (Weisfeiler & Leman 1968). In contrast, the expressive power of GNNs for node classification remains less explored. The expressive capacity of linear spectral GNNs has been analyzed via the uniform approximation theorem in (Wang& /Zhang 2022), which shows that when the graph matrix has no repeated eigenvalues and node features span all frequency components, the model can approximate any one-dimensional function. However, these conditions rarely hold in real-worle graphs, where symmetric structures are common and node features are often sparse. An eigenvalue correction method was proposed in (Lu et al., 2024) to enhance the expressiveness of spectral GNNs. This method reassigns eigenvalues purely by their sorted index, it does not preserve eigenspaces under node permutations, thereby breaking permutation equivariance, which is theoretically unsound.
Our work investigates the expressive power of spectral GNNs from the perspective of node distinguishability. We extend the understanding of how the interaction between the graph matrix and node features influences node distinguishability beyond linear GNNs by incorporating nonlinear feature transformations fw. Moreover, we rigorously establish a theoretical lower bound on the number of distinguishable nodes in spectral GNNs.
spectral GNNs. Notably, our analysis goes
Graph Rewiring. Another line of works focuses on improving the performance of GNNs through graph rewiring techniques. Early methods include DropEdge and EDGEWIRE, which randomly remove edges to alleviate over-smoothing (Rong et al., 2020) Chan & Akoglu 2016). Curvature- based approaches (Topping et al.) 2022) adjust connectivity using discrete Ricci curvature to combat over-squashing, while locality aware strategies preserve structures efficiency (Barbero et al.) 2024).
Recent methods include DiffWire, differentiable and parameter-free approach guided by the Lovász bound (Arnaiz- (Arnaiz-Rodééuuee et al. (022);; FoSR, improving spectral expansion (Karhadkar et al. 2023)
and GPER, selecting edges based on resistance to enhance information flow (Shen et al. 2024
2

---

Published as a conference paper at ICLR 2026
Objectives and underlying mechanisms of graph rewiring methods differ fundamentally from ours. Graph rewiring addresses structural issues by modifying graph topology in the spatial domain, method enhances node distinguishability in the spectral domain. Our AdaSpec is not competitor to graph rewiring. is a plug-and-play spectral enhancement and can be seamlessly integrated with existing graph rewiring methods to achieve superior performance.
PRELIMINARIES
Let G = E,E,NN denote an undirected, simple graph, where iss the set of nodes with cardinality [V] n, & is the set of edges, and X Rx is the node feature matrix. For each node V, (()) E R denotes its associated feature vector. The graph structure is represented by the adjacency matrix A E {0, |=x", where Aij
if (vi, Uz) E E, and 0 otherwise. The degree matrix D E RRxn is diagonal with entries Du: equal to the degree of node U; The normalized adjacency matrix is defined as Á = D- ADD The normalized graph Laplacian is given by L = A, where I R=x= is the identity matrix.
Two nodes and in an undirected graph G' are structurally equivalent Su Sy if they share exactly the same neighbors; formally, for every other node w E V {u, v). (u, w) E = (v, w) E E. In effect, swapping and v leaves the graph's 's adjacency relation unchanged.
A permutation of the node set V is a bijection forms the symmetric group Sym(V). An automorphism of the graph G is permutation л E Sym()) satisfying the following conditions: (1) edge preservation: (v, 2) E E
V + V. The set of all permutations on V
> (I(U), (u)) E
E, Vv, u E V, and (2) feature preservation: ((T(v)) = =(()) Vu E V. The automorphism group of G. denoted Aul( is the set of all such automorphisms.
Two nodes u and are said to be isomorphic, denoted u ~ v, if they belong to the same orbit under (ut(G); that is, there exists permutation ग E Aut(G)) such that (u) = w. Otherwise, u and v are non-isome non-isomorphic.
An important property of functions defined on graphs is permutation equivariance, which ensures that the output remains consistent under any reordering of the nodes. Formally,
Definition 3.1 (Permutation Equivariance). Let G denote the set of graphs. A function f: + gaad said to be permutation equivariant if, for any graph G E g and any permutation E Sym((V) holds that
f(=(G)
where T TG) denotes the graph obtained by permuting the nodes of G according to and (f(()) denotes the corresponding permutation of the output of f.
4 NODE DISTINGUISHABLLITY OF SPECTRAL GNNS
The node distinguishability of spectral GNN refers to its ability to distinguish non-isomorphic nodes within graphs. Formally,
Definition 4.1 (Node Distinguishability). For spectral GNN with function class F. where each I E F G - Raa maps a graph to node representations, node distinguishability refers to the ability to learn function that assigns distinct representations non-isomorphic nodes:
f(G), + f(G) for all u, u E V where v of
where S(G), and f(G),. denote representations of node u and u. o6 indicates node u, are non-isomorphic.
The spectral GNN's node distinguishability capacity that mapping non-isomorphic nodes to distinct representations is determined by its function class J. To understand the distinguishability of spectral GNNs in the form of Equation ( with input of graph matrix M and feature matrix X, we begin by formally defining the spectrum of M and the frequency components of X.
Definition 4.2 (Spectrum and Frequency Components). Let M UAUT be the eigendecomposition of a graph matrix M E IR" x where A is a diagonal matrix of eigenvalues and U = [uI..... unl contains the corresponding eigenvectors. The spectrum of M, denoted spec(M), is the multiset of eigenvalues: spec(M) (M) = {{A,, >g...., An where X; = Aü;- Let support supp(spec (MM) be the underlying set of spec(M).. Define ds |supp(spec ())], which is the number of distinet
3

---

Published as a conference paper at ICLR 2026
Texas
Cora
Texas
Cora
0.10
Denuity
Denaty
0.02
Density
Density
0.4
0.05
0.00
0.00
0.5
1.0
Eigenvalues
Eigenvaalues
Frequency companent
Frequency compenent
(a)
(b)
(c)
(d)
Figure 2: Eigenvalues and frequency component distributions.
eigenvalues. Given node features X E R the frequency components in the eigenbasis of M are X = =UUXX X, where X; un X is the i-th frequency component. The number of non-zero frequency components is || lo0 [XX, X, # O,
2
The limitations of node distinguishabiiity in spectral GNNs stem from two key factors: Eigenvalue multiplicity of the graph matrix M and the missing of frequency components of node features X when projected onto the cigenbasis of M. In Figure we show that spectral GNNs with a first-order polynomial filter and normalized adjacency matrix A as graph matrix cannot distinguish node and 6. (1) Non-distinguishable nodes can exist when there are missing
3
6
5
(a)
(b)
Figure I: Nodes and 6 cannot be distinguished by spectral GNNs K = with A when graph signal X = [1,0, 0,0, 0,0, 0, (a)
frequency components that d 6 n but || 5 in Figure T (2) Non-distinguishable nodes can exist when there
are repeated eigenvalues dj = 3 < n even if |x( 6 in TigureTib) Nodes and 6 in both subfigures are non-isomorphic but spectral GNNs yield identical embeddings for them. Hence they are indistinguishable. We provide a theoretical bound on the number of nodes that can be distinguished by spectral GNNs, stated as follows.
Missing frequency components:
d 6. ||x Eigenvalue multiplicityy: dj
5. (b)
3. ||xx())
Theorem 4.3. For X * Onxn. there exist spectral GNN V (M, that can distinguish at least min(d das, (10))) nodes graph.
This result provides a fundamental guarantee on the node distinguishability of spectral GNNs. The lower bound depends on both the number of distinct eigenvalues d&s and the number of non-zero frequency components || llo. which together characterize the alignment between the graph matrix M and the node features X. When multiple eigenvectors share the same eigenvalue. the graph filter ge applies identical transformations to them, preventing from distinguishing different structural patterns. Similarly, if node features lack frequency components corresponding certain eigenvectors, structural differences captured by those eigenvectors become invisible in embeddings. This has practical implications: increasing distinct eigenvlaue number d' and non-zero frequency components of X in the eigenbasis of M improves the theoretical guarantee the lower bound of number of distinguishable nodes, offering a clear direction for enhancing the expressive power of spectral GNNs.
In real-world graphs, we observe that eigenvalue multiplicity and missing frequency component are very common.
Observation I (Figenvalues of Multiplicity.) The normalized graph adjacency matrix Ā D- AD-1/2 often contains eigenvalues with multiplicities greater than one and the eigenvalue zero has largest multiplicity.
We illustrate the eigenvalue distribution of the normalized graph adjacency matrix for the Texas and Cora datasets in Figure datasets are provided in Figure 3 (Appendix). This phenomenon is also observed in (Lim et al. 2023). Graph symmetry, repeated substructures often lead repeated eigenvalues in the normalized adjacency matrix and reduce its rank. Real-world graphs also tend to be sparse due to many low- degree nodes, further lowering the rank. Since the rank of a real symmetric matrix equals the number of non-zero eigenvalues, low-rank matrices imply high multiplicity of the zero eigenvalue.
Additional eigenvalue distributions for various other real-world
Node features in connected real- world graphs are sampled independently of the graph structure. For instance, in citation networks (such as Cora and PubMed), node features are the textual content of papers, which are collected independently of the graph structure. Thus, graph signals are not aligned with the graph's 's eigenvectors. We have below observations.
4

---

Published as a conference paper at ICLR 2026
Observation II (Missing Frequency Components.) Many frequeney components of graph signal (node feature) is zero in the cigenbasis of normalized graph adjacency matrix A.
We illustrate the distribution of frequency components for Texas and Cora in Figure[[c-d] ((cd)) where most components are zero. Additional results for other real-world datasets are provided Figure (Appendix). Zero frequency component means that the frequency component in the direction of corresponding eigenvectors missing. Real-world node features are often either smooth or oscillatory, containing only low or high-freen frghffreyencc components, leading to many others to be zero or negligible. Additionally, features are typically sparse, with only k non-zero entries that < n. When projected onto the eigenbasis, each component scales as O(k/vn) As + co, the proportion of non-zero frequency components tends toward zero.
Based on above observations and Theorem 4.3 distinguishability of spectral GNNs.
we propose AdaSpec to enhance the node
ADASPEC
AdaSpec generates graph matrix that adapts both the graph structure and node features, enabling it to serve as a plug-in module for any spectral GNN (MM, X) of the form in Equation [ The spectral GNN augmented with AdaSpec is defined as:
(A, = ge ())
(2)
where Ω maps the adjacency matrix A and node features X to new graph matrix. The functions ge and fw (X) remain the same as those in (M,XX).
AdaSpec enables V (A, X) to capture richer interactions between graph structure and node features, which are not possible using fixed matrices in classic spectral GNNs V ()) To ensure permutation equivariance of node embeddings. the generated graph matrix = [2(A, X) must (1) M commutes with Aut(G): P.M- MP.. Vo E Aut(G' where P. the permutation matrix corresponding to the automorphism σ; (2) M preserves edge connectivity: My # 0 + eij & and My = + Cij E. Thus, we design (2A,, X)
satisfy two key properties:
() = (A)(A) + (1s)s(A) a²)x(()
where (A) is designed to increase the number of distinct eigenvalues, (A) aims to reduce the multiplicity zero eigenvalues, and 92r(X) (X) designed to decrease missing frequency components of X. The hyperparameters 01,02 control the eigenvalue range for stable training.
5.1 INCREASE DISTINCT EIGENVALUES
According to Theorem 4.3 increasing the number of distinct eigenvalues of the graph matrix can raise the lower bound of number of nodes distinguished by a spectral GNN, thereby increasing its node distinguishability. To achieve this, the term 2p (A) in AdaSpec is designed follows:
lD(A) (D + B) (A B) (D + 1)21
where A and D are the graph adjacency matrix and the degree matrix, respectively, and B diag()) is a learnable diagonal matrix with non-negative elements.
The diagonal element of B initialized by = 1/Duus ensuring nodes with the same degree start with the same bias. For isomorphic nodes u ~ we have b, = b, throughout training; for of v. training yields by # b.. This initialization preserves permutation equivariance of & yt( (A. as shown in Proposition 5.3] Adding B to A introduces node-specific flexibility, enabling A + B and D + to adapt to graphs. This enhances node distinguishability by allowing structurally equivalent but feature different nodes to play distinct roles. For two non-isomorphic nodes u, that u o if Su ~ 5y but X (u) * X (v). introducing different biases b, +f b, breaks structure symmetry and reduces eigenvalue multiplicity, Intuitively, B modifies the self-loop strength, altering information flow from the node itself. We later provide theoretical justification that this increases the number of distinct cigenvalues.
Theorem 5.1 (Increased Distinct Eigenvalues). Given a graph G with the adjacency matrix A, and the degree matrix D, we have:
do 2 dí
5

---

Published as a conference paper at ICLR 2026
We prove that for any A, there exist diagonal matrix B so that (A) has distinct eigenvalues. This indicates that the lower bound of the number distinguishable nodes for spectral GNNs using Op is greater than or equal to that for those using A, according to Theorem 4.3
5.2 SHIFTS EIGENVALUES FROM ZERO
The presence of zero cigenvalues forces spectral filters to suppress the associated frequency compo- nents, thereby hindering node distinguishability. We shift eigenvalues away from zero by using:
(s(A)= = =-
We choose the identity matrix because adding it to any matrix shifts the eigenvalues while preserving the eigenvectors. This ensures minimal alteration to the original matrix.
Adding term clly to any matrix C' can reduce the number of zero eigenvalues. As all eigenvalues of C add the same scalar e, distinct cigenvalues remain distinct after addition. As all eigenvectors of C' stays the same, so the number of non-zero frequency component of node feature stays the same.
5.3 INCREASE FREQUENCY COMPONENTS
We can increase the number of non-zero frequency component to the node distinguishability of spectral GNNs. Given node feature matrix X, design a matrix f2 that adapts to X to increase the frequency components:
h
X X
(x = Σ
o
where o denotes the Hadamard product.
By dividing by the Frobenius norm ||X 1| features with larger magnitudes don't dominate the transformation. We prove in theory that for any symmetric matrix C of no repeated eigenvalues, adding (X) can increase non-zero frequency components.
Theorem 5.2 Noe-Decrggs Frequency Components). For real symmetric matrix C Buxx of no repeated eigenvalues with orthonormal basis {u, (ren).)) Under Condition 5.3 the following holds for index E [h]:
||
(x+(CeB))))) 11o
11
where is non-zero constant.
Condition 5.3 (Non-zero feature projections). Let E RRxa be real symmetric matrix with orthonormal cigenbasis {ur 1 There exist two column node feature vectors X and X₃ with i E [h] and / such that Ug X. # O, Ug X. * O, and u. X. * 0 for some indices k,j j E [n].
Condition 5.3 naturally satisfied in most real-world graph datasets. This condition requires that node features have non-zero projections onto certain eigenvectors of the graph matrix. Nat- ural heterogeneity in node features makes it likely that different nodes will have diverse nonzero projections onto eigenvectors, even with sparse features. Additionally, while feature correlation exists, real-world graph typically varies lot along certain dimensions, satisfying our non-zero projection condition. Therefore, incorporating (2((X) ensures that the number of non-zero frequency components of node features increased in real-world graphs.
In summary, each component of Ω X) either increases the number of distinct eigenvalues or the number non-zero frequency components of the node features in the eigenbasis of the graph matrix. By Theorem 4.3 this leads to higher lower bound on the number of distinguishable nodes, thereby enhancing node distinguishability. We show properties our design Q(A, X) as below.
Theorem 5.4. For graph G, the learnable matrix Q(A, X) is commutative with Aut(G) and preserves edge connectivity.
As ((A satisfies desirable properties, it ensures that the augmented spectral GNNs T XA, with AdaSpec remains permutation equivariant.
Proposition 5.5. When fw is permutation equivariant, spectral GNNs + XA, augmented with AdaSpec permutation equivariant.
Theorem 5.4 and Proposition 5.5 ensures that for spectral GNNs v - (A, X), reordering the graph nodes results in a corresponding reordering of node embeddings. AdaSpec can be combined with any spectral GNNs enhance their node distinguishabilit..

---

Published as a conference paper at ICLR 2026
5.4 TIME COMPLEXITY ANALYSIS
The time complexity of classic spectral GNNs (M,, X) and V (A, augmented with AdaSpec is in the same order in both forward and backward propagation. (x in AdaSpec will increase the pre-computing time, but needs to be computed only once. We list the time complexity in Table [
The time complexity can be analyzed in two main phases: pre-computation and forward/backwart propagation. During pre-computation, graph matrix normalization requires O(IV] + | operations such as graph adjacency matrix normalization. (X) in V (A, X) requires an additional (h{( V|+ [E])) where computation is efficiently limited to non-zero entries in the adjacency matrix. Thus, the one-off pre-computing of v (A, X) scales linearly in the size of graph and node feature dimension.
For forward and backward propagation, the feature transformation step (X) incurs com- plexity of (hW while graph convolution ge requires (KKTE)) operations when Ty (MM is computed recursively, such in ChebNet, JacobiConv. Although V (A, requires additional computation of (2A, X) during each forward pass and gradient calculation for matrix B during backpropagation at cost of O(D) [E]), this does not change the overall asymptotic complexity.
6 EXPERIMENTS
We design our experiments to investigate the following research questions: (1) Q1: does AdaSpec generate task-adaptive graph matrices that enhance node distinguishability in spectral GNNs? (2) Q2: What is the contribution of each component within AdaSpec to overall performance? (3) Q3: How does AdaSpec affect the spectral properties of the graph matrix, particularly in terms of increasing the number of distinct eigenvalues? (4) Q4: What is the computational overhead introduced by integrating AdaSpec into spectral GNNs during training?
To what extent
Experimental Setup. We conduct experiments on eighteen benchmark datasets for node classifica- tion to verify the effectiveness of AdaSpec. Datasets includes: six small heterophilic graphs (Texas, Wisconsin, Actor, Chameleon, Squirrel, Cornell), five large heterophilic graphs (Roman [mpire_ Amazon Ratings, Minesweeper, Tolokers, Questions) and seven homophilic graphs (Citeseer, Pubmed, Cora, Computers, Photo, Coauthor-CS, Coauthor- Coauthor-Physics), Statistics of datasets, details about the baselines, and the setting of hyperparameters are included in Appendix B For each dataset, we follow (Chien et al. 2021 He et al.) 2022a) and use sparse splitting that nodes are randomly divided into training/ validation//estingg with ratios of 2.5% /2.5% 995%, respectively. Notably, for Citeseer, Pubmed, and Cora datasets, 20 nodes per class are for training, 500 nodes for validation, and 1,000 nodes for testing.
We chose five popular spectral GNNs as our baselines: ChebNet (Defferrard et al. 2016)). GPRGNN (Chien al., (202)), BernNet (He et al., (002), JacobiConv (Wang & Zhang] (2022), and ChebNetll (He et al.] (022aa), and compare their performances augmented with AdaSpec and with fixed graph matrix across all datasets. For each spectral GNN, we use GNN (O) to denote the original model and GNN (M) to denote the spectral GNNs augmented by AdaSpec, with A 1 indicating the performance improvement.
Effectiveness of AdaSpec. We present the node classification performance with and without the AdaSpec all small heterophilic datasets and subset of large heterophilic datasets in Table 2 The Minesweeper and Question datasets are particularly challenging to classify, as their label informativeness (i.e., the mutual information between the labels of the central node and its neighbors) is zero (Platonov et al. 2023). The complete experimental results are in ( Results on homophilic graphs are shown in Table
Spectral GNNs
Parameter Count
Pre-computing Complexity
Forward/Backward Complexity
((M.)) V/T (A.
1+K 1
O( + EI) O(h[D] + (E())
O(KTIE + [M]]W]) O + [V][W]]
Table 1: Time complexity comparison of GNNs with and without AdaSpec. V and E denotes the node and edge set respectively. is the node feature dimension. T is the node class number. K is the polynomial order of spectral GNNs.
7

---

Published as a conference paper at ICLR 2026
Model
Texas
Wisconsin
Actor
Chameleon
Squirsel
Cornell
Minesweeper
Questions
ChebNet(O)
38.67
32,92
25. 15
29.32sa13
24.23
31,33
86.29
55.13
ChebNeuMD
51.1623.56
33,8329.38
25.38
29.73aa3
23.2a384
33,477732
86.720.3
55.2
+12.49
+0.91
+0.23
+0.41
-1.03
+2.14
+0.41
+0.07
ChebNetll())
36.24a1.99
51.54363
29. 29.89
35,261166
37.19
39.54#688
18
13e00s
()))
56,7623.2
52.0a275
30.43a1:3
35.62
36.8819.9
39,9447.5
19.120.9
65.54
A 1
+0.52
+0,5
+0.54
+0.36
-0.31
+0.4
+0,75
+1.41
JacobiConv(O)
55,09
19,021051
32.15
34.29
29.2911.99
38, 38.9618799
87.34gou2
64.72s0.3
JncobiConv(M) A
57.4
52.33
32,526075
18.16
31.35+1
41.62210.06
89,1349.1
65, 8t
+2.31
+3.33
+0.37
+3.87
+2.06
+2,66
+1.79
+1.08
GPRGNN(O)
48. 15:475
44.25
30.39
32.5+2
27.7
34,39268
87, 87.15
53. 14.12
GPRGNN(M)
58,27=40
53.25e1.1
50.4+1.5
32.82+476
27
27.366034475
36, 13+7.2
88.58=0
58. 19
A
+10,12
+9.0
+0.01
+0.32
-0.4
+1,74
+1.43
+5.05
Bc
192752
79,382775
30.5
35,352346
33.412544
36. 82.82410.4
76.342o22
64.862737
BemNet(M) M)
58 14411
51,96+144
30.61=067
39.61+1
34.464341
76.95e021
A
+2.71
+2.58
+0.11
+4.26
+1.05
+3,41
+0.41
+0.34
Table 2: Performance of spectral GNNs with/without AdaSpec on heterophilic datasets. ROC AUC is reported on Minesweeper, Questions. Testing accuracy is reported on other datasets. High accuracy and ROC AUC indicate good performance.
Model
Citeseer
Puhmed
Cora
Computers
Photo
Coauthor-CS
Coauthor-Physsi
ChebNet(O)
69.21
75.29=234
80.45#1.09
82. $2.6421.76
91.7720.2
90.95+034
95.032011
(he)Ner(M)
68.524086
77.38+145
82.2644084
85.14
92.34a041
91.54+a2:
94.93=a09
A
-0,69
+2,09
+1.81
+2.5
+0,57
+0.59
-0.1
ChebNetIro)
69 15
78,42=148
81.64 86
84.96#0.97
92.71
93.088027
95.23+a
ChehNetll(M)
69.54aa9
78.59
81.97
84.79
92.58
93.1 1aa2s
95.26sa11
A
-0.39
+0.17
+0.33
-0.17
-0,13
+0.03
+0.03
JacobiConv
70.8+07
79,43=145
77.15
85,39
92.794a.36
93.33+a22
95.32t0
JacobiConv(M)
70.91
79.65a1.2
83.52a0.00
84.92an.2
92.831036
93.27aa25
95.43an11
A
+0.11
+0.22
+6.37
-0.47
+0.04
-0,06
+0.11
GPRGNN(O)
70.02407
79,2421.1
82.2420.86
84.0920.81
92.432224
92,992a22
95,282004
GPRGNN(M)
70.4044
79.6+0.97
82.19
84,28+0.66
92.53+038
93.33+a29
95.32+015
A
+0.38
+0,36
-0.05
+0.19
+0.1
+0,34
+0.04
Bernieet(O)
69. 12#096
78.921.04
81,9088
85.15
92.6320.9
93.114022
95.320.17
(ernNer(M)
69.45
79.07=1m
82.5+078
85. 18+077
92.58+036
93.074a.9
95.32#a15
A
+0.33
+0.17
+0.6
+0.03
-0.05
-0.04
+0.02
Table 3: Test accuracy of spectral GNNs with/without AdaSpec on homophilic datasets. High accuracy indicates good performance.
From Tables 2ad observe the following: (1) AdaSpec significantly improves performance
on heterophilic graphs compared to homophilic graphs. There is an average accuracy improvement of 1.89% on small heterophilic graphs, an average ROC AUC improvement of 1.27% on large heterophilic graphs, and an average accuracy improvement of 0.43% on homophilic graphs. (2) AdaSpec shows greater performance improvement on small-sized graphs compared to large-sized graphs. The average node classification accuracy improvement on small graphs (Texas, Wisconsin, Coreell) is 3.45%, whereas the improvement on larger graphs (Chameleon, Squirrel) is 0.46%.
The main performance improvement stems from AdaSpec's ability to increase node distinguisha- bility in spectral GNNs. By refining the graph structure representation, AdaSpec enables the model to better separate nodes with similar features or structures. In homophilic graphs, oowffreuenccy components are sufficient for smooth features, so adding more may hurt. Heterophilic graphs require richer spectral patterns, and AdaSpec help by increasing useful frequency components. In small graphs, changes in graph matrix can reveal critical structure. In large graphs, existing structure dominates, changes in graph matrix are less effective.
Component-wiss Analysis. We report ChebNet performance augmented with AdaSpec across multiple datasets and conduct an ablation study to isolate the effects of each component. Results in Table show: (1) Full components: Combining all three components consistently yields the best performance. (2) Structure-dominater graphs (e.g.. Chameleon, Cora): Ωp outperforms Ωs. (3) graphs (e.g.. Texas, Roman : 22g outperforms Qp. (4) Frequency com- ponents: Increasing non-zero frequency components via (XX) improves performance, even when used alone. Each component within AdaSpec independently improves node distinguishability. When combined, these mechanisms complement each other, leading to the strongest overall performance.
8

---

Published as a conference paper at ICLR 2026
AdaSpec
Texas
Chameleon
Roman Empire
Amazon Ratings
Citeseer
Cora
ChebNet(O)
38.67
29.32
47.15
39.79
69.21
80.45
(p(4)
40.75
26.71
22.70
40.75
68.27
81.53
(1s(4)
44,51
23.27
54,04
35.28
52.29
55.63
(x(X)
26.24
28.22
54.12
37.16
29.49
65.49
X)
51.16
29.73
54.55
40.92
68.52
82.26
Table 4: Test accuracy of ChebNet with different components of AdaSpec across datasets that
?(A,X) X) contains all three components.
Increased Distinct Eigenvalue Number. We compare the number of distinct eigenvalues between the original normalized adjacency matrix Á and the modified matrix (2p(A) from AdaSpec when using ChebNet. Due to the computational cost of full eigendecomposition we conduct this analysis on small-scale homophilic and heterophilic datasets. As shown in Table 12((A) consistently increases the number of distinct eigenvalues, supporting Theorem 5.1 Standard normalized adjacency matrix Ā and its self-loop version Á are specific cases of the component (Ap(A) in AdaSpec by setting B = and B = respectively. We introduces richer structural information in spectral GNNs by making learnable matrix (updated via gradient descent) in AdaSpec. The increased number of distinct eigenvalues directly enhances the model's ability to differentiate non-isomorphic nodes.
Dataset
Texas
Wisconsin
Chameleon
Squirel
Cornell
Citeseer
Cora
[V] di
183
251
890
2,223
183
3,327
2,708
113
178
845
2,213
122
2,508
2,395
d(((A)
181
229
888
2,221
144
3,227
2,645
A 1
68
51
43
8
22
719
250
Table 5: Number of distinct eigenvalues of the graph matrix, |V] denotes the number of nodes in graphs. dj and (A) numbers of distinct eigenvalues of Á and (n(A) in AdaSpec respectively.
Time Complexity of AdaSpec. We evaluate the training efficiency of ChebNet with and without AdaSpec across multiple datasets. For each dataset, we conduct ten independent runs. We report average training time per and the pre-computing time of + (A, X) in Table 6 The results show that AdaSpec introduces minimal overhead and can even accelerate convergence on large heterophilic graphs (c.g.. g.. Roman Empire, Amazon Ratings). When increase graph size from Amazon Ratings to Coauthor- thhsorr, the pre-computation time rises from 0.03s to 12.44s, which is consistent with our time complexity analysis in Section 5.4, By incorporating structural and feature bias into the node representation, AdaSpec enables faster convergence and more efficient training.
Roman Empire
Amazon Ratings
Coauthor -CS
Coauthor -Physics
Datasets
Tolokers
Minesweeper
Questions
Computers
Photo
ChebNet (O)
1.93
1.91
1.76
1.28
2.53
4,73
3.4
3.67
4.54
ChebNet (M)
2.51
3.05
4.60
A
-0.5
-0.56
0.75
0.9
0.52
0.59
1.43
0.44
0.06
Pre-Computing
0.26
0.03
0.44
0.08
0.56
1.83
0.9
4.1
12.44
Table 6:
Average training and pre-computing time (in seconds) for ChebNet with and without AdaSpec on large heterophilic and homophilic datasets. Pre-computing is for Op(X) in AdaSpec.
7 CONCLUSION AND LIMITATIONS
This work analyzes node distinguishability of spectral GNNs and shows it is governed by the interplay between the graph matrix and node features. Specifically, by the number of distinct eigenvalues and nonzero frequency components in the graph matrix's 's eigenbasis. We propose AdaSpec, a plug-in module that enhances the node distinguishability of spectral GNNs, offering theoretical guarantees and empirical gains.
While effective, our approach is limited to spectral GNNs and provides only a lower bound on distinguishability. The design of AdaSpec is tailored to certain data distributions and may not gener- alize universally. Future work could explore more generalizable graph matrix designs, applications to dynamic graphs, and integration with advanced spectral GNNs for broader applicability.

---

Published as a conference paper at ICLR 2026
REFERENCES
Adrián Ardaiz-Rodréguez, Ahmed Begga, Francisco Escolano, and Nuria M Oliver. Diffwire: Inductive graph rewiring via the lovász bound. In Learning on Graphs Conference, pp. 15-1. PMLR, 2022.
Federico Barbero, Ameya Velingker, Amin Saberi, Michael M Bronstein, and Francesco Di Giovanni. Locality-aware graph rewiring in gnns. In ICLR, 2024.
Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Francesco Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. JEEE transactions on pattern analysis and machine intelligence, 2021.
Hau Chan and Leman Akoglu. Optimizing network robustness by edge rewiring: a general framework. Data Mining and Knowledge Discovery, 30:1395-1422 -425,, 2016.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv: Learning. 2021.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS, 2016.
Yu Tang Guo and Zhewei Wei. Graph neural networks with learnable and optimal polynomial bases. ArXiv, abs/2302. 12432, 2023. URL https: semanticscholar wttp:oopo///oro....oooo
257205644)
David K. Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. ArXiv, abs/0912.3884, 2009.
Mingguo He, Zhewei Wei, Zengfeng Huang, and Hongteng Xu. Bernne:: Learning arbitrary graph spectral filters via bernstein approximation. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Mingguo He, Zhewei Wei, and rong Wen. Convolutional neural networks on graphs with chebyshev approximation, revisited. ArXiv, abs/2202.03580, 2022a. URL https://api
semant i cscholar. watachollr..rg//orrpp... Cowprrorroorro/220000 246652363
Mingguo He, Zhewei Wei, and rong Wen. Convolutional neural networks on graphs with
chebyshev approximation, revisited. ArXiv, abs/2202.03580) 2022b. URL hhtpss:/app
prrpchoolr..og/Coruuussssss. wrg/Corpus 246652363
Keke Huang, Yu Guang Wang, Ming Li, et How universal polynomial bases enhance spec- tral graph neural networks: Heterophily, over-smoothing, and over-squashing. arXiv preprint arXiv:2405. 12474, 2024.
Ming Jin, Guangsi Shi, Yuan-Fang Li, Bo Xiong, Tian Zhou, Flora Salim, Liang Zhao, Lingfei Wu, Qingsong Wen, and Shirui Pan. Towards expressive spectral-temporal graph neural networks for time series forecasting. IEEE transactions on pattern analysis and machine intelligence, 2025.
Kedar Karhadkar, Pradcep Kr Banerjee, and Guido Montufar. Fosr: First-order spectral rewiring for addressing oversquashing in gnns. In ICLR, 2023.
Tosio Kato. Perturbation theory for linear operators, volume 132. Springer Science & Business Media, 2013.
Thomas Kipf and M. Welling. Semi-supervised classification with graph convolutional networks, In International Conference Learning Representations, 2017.
Ron Levie, Federico Monti, Xavier Bresson, and Michael M. Bronstein. Cayleynets: Graph con- volutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing, 67:97-109, 2019.
Guoming Li, Jian Yang, and Shangsong Liang. Ergnn: Spectral graph neural network with explicitly- optimized rational graph filters. In ICASSP 2025-2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1-5. IEEE, 2025.
10

---

Published as a conference paper at ICLR 2026
Pan Li and Jure Leskovec. The expressive power of graph neural networks. Graph Neural Networks: Foundations, Frontiers, and Applications, pp. 63 98, 2022.
Zhengpin Li and Jian Wang. Spectral graph neural networks with generalized laguerre approximation. In ICASSP 2024-2024 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp- 7760-7764. IEEE, 2024.
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 ICLR, 2023.
Kangkang Lu, Yanhua Yu, Hao Fei, Xuan Li, Zixuan Yang, Zirui Guo, Meiyu Liang. Mengran Yin, and Tat-Seng Chua. Improving expressive power of spectral graph neural networks with eigenvalue correction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 14158-1411 14166, 2024.
Hongbin Pei, Bingzhen Wei, K. Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. ArXiv, abs/2002.05287, 2020.
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look the evaluation of gnns under heterophily: Are we really making progress? arXiv preprint arXiv:2302. /640, 2023.
Yifang Qin, Wei Ju, Yiyang Gu, Ziyue Qiao, Zhiping Xiao, and Ming Zhang. Polycf: Towards optimal spectral graph filters for collaborative filtering, ACM Transactions on Information Systems, 13-4):1-28, 2025.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In ICLR, 2020.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. J. Complex Networks, 9, 2021.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint 1rXiv:1811.0530 2018
Xu Shen, Pietro Lio, Lintao Yang, Ru Yuan, Yuyang Zhang, and Chengbin Peng. Graph rewiring and preprocessing for graph neural networks based on effective resistance. IEEE Transactions on Knowledge and Data Engineering, 2024.
GW Stewart. Matrix perturbation theory. Computer Science and Scientific Computing/Aculemic Press, Inc, 1990.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. 2022.
Xiyuan Wang and Muhan Zhang. How powerful spectral graph neural networks. ArXiv, abs/2205.11172. 2022.
Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. NT7, Series, 2(9):12-16, 1968.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? International Conference on Learning Representations, 2019.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. ArXiv, abs/1907. 0049314 2020.
Bingxu Zhang, Changjun Fan, Shixuan Liu, Kuihua Huang, Xiang Zhao, Jincai Huang, and Zhong Liu. The expressive power of graph neural networks: survey, arXiv preprint arXiv:2308.08235, 2023.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In Advances in Neural Information Processing Systems, 2020.
11

---

Published as a conference paper at ICLR 2026
APPENDIX
A PROOFS
Detailed proofs of theorems and propositions are provided.
Theorem 4.3. For X # Onxn. there exist spectral GNN (M, that can distinguish at least min(das, |})))) nodes on graph.
Proof. (1) Rank of fw.
The rank of matrix corresponds to the dimension of its column space. When fw is MLP, which can approximate any function, there exist parameter W so that fw: injective function, and rank(fw (X)) rank(X).
(2) Rank gM(M).
For K order polynomial function on symmetric graph matrix g (M), we can represent as (MM) = = Og Mr We conduct cigendecomposition M = UAU thus, g(M) = Ug(A) where g(1,) = agA (an)(g(MM) equals the number of non-zeros in g(A). When dg + 7 is full rank matrix. Therefore, there exist parameter O' that 8g & 0.
we have Rank(g
such that rank / (M) = n 2 rank
(3) Rank and eigenvalues.
As ger (M) is full rank matrix, so rank(ger (M)) 2 rank(MM) 2 das- As eigenvectors there at least linearly independent directions to represent X in eigenbasis of M, i.e, rank(X) 2 |
are linearly independent, has non-zero frequency components, then
Thus, for spectral GNN v in Equation
[.. there exist parameter O', W' that
rank (mn
rank(ger (A))fw:(XI)
min(rank(ger rank(f.
(5)
wv min(dar, rank
IV min(dar, (M)
If (Mn,(V(M, 2 r, it means that at least r rows in embeddings (M, X) are linearly independent. Thus, (M, X) can distinguish nodes in graph.
summary, there exist a spectral GNN that can distinguish least min(dy, || (M) (lo) on graph.
Lemma A.1 (First-Oree Order Eigenvalue Perturbation (Kato 2013
Let Ωit) be an analytic maliti of
real symmetric matrices, and let X be eigenvalue of (2(0) with multiplicity m. Let Vx E Rixm have orthonormal columns spanning the eigenspace of x. Then there exist real-analytic eigenvalue branches .., (m) (t) of S(t) with (0) X, and their first-order derivatives
0 satisfy
X( = Pix
where P1.... pm are the eigenvalues of the compressed matrix
Hx VT d
2(())
Vx.
dt
t=0
In particular, the multiplicity-m eigenvalue À splits to first order precisely when H2, is not scalar multiple of the identity.
Theorem 5.1 (Increased Distinct Eigenvalues). Given a graph G with the adjacency matrix A, and the degree matrix D, we have:
( dí
12

---

Published as a conference paper at ICLR 2026
Proof. When À has eigenvalue of multiplicity l 1 and let V1 Ra have orthonormal columns spanning the corresponding eigenspace Ex.
Consider the analytic family
(tt) (D + 1B) +B)(+ +
te (0,
so (2(0)= = A. The first-order perturbation matrix at t = 0 is
d
P =
201) = - B/D 1/2 + D DD2 1/2 D 112 1/2
D-12 AD 3/2 B.
dt
1=0
Equivalently, conjugating by 11/2 yields the simpler form
Q = D = B (D-BBA+AD
from which = -D-1/2QD-112
= (bag(b) (b.....,b)) and Q depends linearly on the diagonal vector 6, hence so does P. By Lemma A.I, the first-order shifts of the & eigenvalue branches emanating from are the cigenvalues of the k x k symmetric matrix
Hx V PV 1
Since Q and H linear in b, the condition that Hx be a scalar matrix is a finite system of homogeneous linear equations in b. Thus the "bad set"
Sx = {b E II:: Hy is scalar)
a proper linear subspace of R (for k > the system nontrivial unless the eigenspace has special coordinate structure). Taking the finite union over all repeated eigenvalues produces proper algebraic subset S = U^ Sx C 12
Choose 6* & (and bū 0). Then for each repeated eigenvalue À the corresponding Hy is non-scalar, so the multiplicity of A splits into at least two distinct eigenvalue branches for small t > 0. Therefore for sufficiently small >> O the matrix ??tt) has strictly more distinct eigenvalues than A. Setting B* diag(b*) yields the desired diagonal perturbation.
Because have produced point outside the discriminant variety, the discriminant polynomial not identically zero; hence the complement (the set B giving simple spectrum) is Zariski-open and dense in R"
In summary, there exists diagonal B" (indeed Zariski-open dense set of such diagonals) for which (A) = (D + Bdy B² (A (A- + B*) - B has all eigenvalues simple, i.e., doo(A) =
d
Theorem A.2 (First-order Perturbation Theorem (Stewart) 1990)). When a system described by matrix A E gaxn of repeated eigenvalues is slightly allered by small perturbation Ç Raxn and the new new system can be represented as A' = A + eč, where is a non-zero constant. A has eigenvalues {Xilie(m) and eigenvectors {ui]eejn]- A' has eigenvalues (M)xej and eigenvectors
{u) ieen)
Relations between eigenvalues and eigenvectors of A' are:
X A + Edd;
=u, (u, + O(e?)
4 St
1 = +
Xj Uj + (
Theorem 5.2 non--ecreasing Frequency Components). For a real symmetric matrix C' Raxn of no repeated eigenvalues with orthonormal basis {u, (rem)) Under Condition 5.3 the following holds for index E [h]
(C+eBF) llo || 3
where is non-zero constant.
13

---

Published as a conference paper at ICLR 2026
Proof. Since C' is real symmetric matrix, it can be diagonalized
C UAU
where U = (ui.....u........... un] is orthonormal eigenvectors and A = diag(Ai.......... An) is the diagonal
matrix of eigenvalues.
We denote (Ei) and (ūs kejn eigenvalues and eigenvectors of clp.
According to Theorem A.2 have
S2 4
ü1 = Uj
O(c²)
Aj Av
kØj
Then,
U Su
ú] X = u/ X +
Σ
X + 0(22)
Xj A
køj
(I) For Xilu,X, # 0}
The leading term u² X * ensures that aj X # 0.
It indicates that non-zero components of X, in eigenspace of C is still non-zero components in eigenspace of C + el2r.
(2) For Uilf, X, 0} We have
Ug AFu
ú X2
us X, 0(e2)
Av
k
(u. Xx) Ubj)
(xy >xc) 1u X 0
When there exist & that of X, * and there exist 1 that uf X2 + 0, X. X. # 0. Thus, (ug (X] u;) + and ūā X,, # 0.
It indicates that the zero-components of X in eigenspace of C' becomes eigenspace of C + eldp.
components in
In summary, when perturbing matrix with clp, the non-zero frequency component | x (C+eRr))
llo > || llo.
Theorem 5.4. For graph G. the learnable matrix ((A,X) is commutative with Aut(G) and preserves edge connectivity.
Proof. (1) R(A,X) commutes with Aul(G).
For any permutation matrix P E Aul(G), we have PAP = A, p-1- PT and PDPT D. Therefore:
P(D B)PT PDPT PBPT D+B
P(D + B) 1/1ppppT--- = BD+
For two isomorphic nodes u ~ v, they will have same node labels. Each element in updated by gradient, when the gradient of b, and b, are the same. As we initial all b, L. we will get by b.. Thus, PBPT B.
14

---

Published as a conference paper at ICLR 2026
For (B (A+ B)
PDD(AA)T
(D++ pT
+(D PID+B-IAAD++))111
+ P(D - (
= +D++ [D++))1PPAP") (D+ (D++) BD+
+D+ (D+B)-"/PBP) (D B)-11
=D++ (D++
+D +B0+BBB/BBB- + +B)
=(D+ B)- B) B/-
(A)(A)
Obviously, for (s(AA) L, we have PIPT I.e.. PQs((A)T (As(A).
For (x(X)= E x,X7
A, have
[X.I
P22(X)PT
XIXX
A PT
(PX,) AA
X
& aA = (X)
As each term in S2A, X) commutes with Aut putting them together, we have
PR(A, X)PT = ((A,
(2) ((4, preserves edge connectivity.
For (D(A) = (D 11+ B)(D 1/21/2 B is a diagonal matrix and A represents the edge connectivity, (D (D+B) B)- () B) ensures that all original edges are scaled but not removed.
For Is(D) 1, it adds self-loops but does not affect the existing edges.
X For (x() Σ ||
A. the Hadamard product o.A ensures that only weights of existing edges are modified (no new edges are added), the edge connectivity is preserved.
summary, 9(A, X) commutes with Aul(G) and preserves edge connectivity.
Proposition 5.5. When Jw is permutation equivariant, spectral GNNs V X) augmented with AdaSpec permutation equivariant.
Proof. The spectrum GNNs Equation 2 has the format + (A, X) (2)4 We denote M S2(A, X) to simplify the analysis.
It has been proved in Theorem 5.4 that M = [(A,, X) is commutative with Aut(G) and preserves edge connectivity.
(1) Permuted Graph.
Let ग E Sym(V) be a permutation the nodes. Applying π to G results in a permuted graph (G), where both the adjacency matrix M and the feature matrix X are permuted:
15

---

Published as a conference paper at ICLR 2026
(MM) 7TMP T (X) P.X
where PT the permutation matrix corresponding to n. (2) Applying E to the Permuted Graph π (G).
T (+((() = go (M))))))( K
Σ
(.T((((MM)) fw
(3) Term (M)))(M)) Since T& is polynomial basis and M = (2(, X) commutes with Pa for all E Aut(G), we
have:
TR(+(M)) = PMT)
Therefore:
(e( = Σ (&T2(=(M)) Σ ( (M))
K=
(4) Term (=()) As fw is permutation equivariant, we have
fw(x(X))= = (X)
Therefore,
V (+((())) P=go(M)Pp (X) = Prgo(M)) = (G)
Thus, spectral GNN T (A, X) permutation equivariant.
Tocas
Wisarain
Actor
0.05
Oensity
0.05
Denally
0.04
8,2
0.00
Eipervatees
Bigervalues
Eigenvolues
Bieervaluss
(d)
Chameleon
Squimel
Clteseer
Pubmed
Cora
0.04
Denelity
0.02
0.02
0.92
Egenvalues
Egenvalues
Eigenvlluss
Elgenvelues
Eipervatues
(c)
(f)
g
(h)
Figure 3: Distributions eigenvalues of normalized graph adjacency matrix.
B EXPERIMENTAL SETTINGS AND RESULTS
We introduce statistical information of datasets, details of spectral GNNs, hyperparameter setting, distribution of graph matrix spectrum and frequency components of node features of real-world datasets and more experimental results in this section.
16

---

Published as a conference paper at ICLR 2026
Statistics
Texas
Wisconsin
Comell
Actor
Chameleon
Squirrel
# Nodes
183
251
183
7,600
890
2.223
Edges
295
466
280
26,752
27.168
131,436
Features
1,703
1,703
1,703
932
2.325
2,089
Classes
Edge Homophily
0.11
0.21
0.3
0.22
0.24
0.22
Statistics of six small heterophilic datasets (Pei et al.
2020: Rozemberczki et al. 2021 Platonov
al. 2023).
Statisties
Roman, Empire
Amazon Ratings
Talokers
Mineswerper
Questions
Nodes
22,662
11,758
48,921
# Edges
32,927
93,050
519,000
39,402
153,540
# Features
300
300
10
301
# Edge Homophily
0,05
0.38
0.59
0.68
0.84
Statistics of five large heterophilic datasets Platonov et al.
2023
Statistics
Citeseer
Pubmed
Computers
Photo
Coautber CS
Couuthor. Cousihor-Physics
Nodes
3,327
19.717
2,708
13,752
7,650
18,333
134,493
Edges
4,676
44,327
5,278
491,722
238,162
163,788
495 924.924
3,703
1,433
8,415
# Classes
6
5
7
10
8
15
5
Edge Homophity
0.74
0.8
0,93
Statistics of homophilic datasets, including three small datasets (Citeseer, Pubmed, Cora) and four large datasets (Computers, Photo, Coauthor-CS, Coauthor- Phoshosr- (Kipf & Welling 2017 Zeng
et al. 2020 Shchur al. 2018).
Table 7: Statistics of real-world datasets.
B. DATASETS
The statistical information of the datasets, including node numbers, edge number, feature dimensions, node class numbers, edge homophilic ratios are summarized in in Table 7
We use the directed clean version of Chameleon and Squirrel provided by (Platonov al. (023) which removes repeated nodes in graphs. The large heterophilic dataset is proposed in (Platonov al. 2023). The datasets Tolokers, Minesweeper and Questions classified as homophilic datasets under the Hedge metric (Zhu et (2000), although they belong to heterophilic datasets according to the adjusted homophily metric (Platonov et al. 2023
B.2 DATA DISTRIBUTION IN REAL-WORLD DATASETS
We show eigenvalues distributions of normalized graph adjacency matrix of real-world datasets in Figure Distributions of frequency components of node feature column vectors in eigenspace of normalized graph adjacency matrix in Figure[4
B.3 HYPERPARAMETER SETTINGS
All experiments are run on GPU NVIDIA RTX A6000 with 48G memory.
Following (Platonov et al. 2023) we fix the hidden size of the MLP to 512 and set early stopping
with patience of 100 steps on five large heterophilic datasets (Roman Empire, Amazon_ Amazon_Ratings,
Tolokers, Minesweeper, Questions). Following (Chien et al.) [222]] He et al. 2021) we For all other fix the hidden size of the MLP 64 and set early stopping with patience of 200 steps on all other datatsets. The maximum number of epochs is set to 1,000.
We conduct a grid search for hyperparameters used during the training of spectral GNNs, including learning rates, dropout rates, exponential decay parameters, propagating coefficient for GPRGNN and JacobiConv, parameters o, in JacobiConv. For different datasets, we use different grid search range, The exact search ranges for different hyperparameters different datasets are detailed in Table 8
17

---

Published as a conference paper at ICLR 2026
Wacominn
Ganell
Actor
0.2
0.7
022
2
0.50
0.0
0.0
0.00
0.0
0.5
1.0
1.0
Frequency component
Prequency component
Frequency component.
Frequency component
(a)
(b)
(c)
(d)
Chamelcon
0.4
0.0
0.25
0.0
0.0
0.00
0.0 Frequency
0.0
component
component
Frequency component
Frequency component
(c)
(f)
(h)
ii)
Figure 4: Distributions of frequency components of graph signals in eigenspace of normalized graph adjacency matrix.
Datasets
Hyperparameters
GNNs
Range
'Cora', 'Citeseer', 'Pubmed', 'Chameleon', 'Squirrel', 'Actor', "Texas', 'Cornell', 'Wisconsin'
dropout in MLP
AlIJacobiConv
0.5, 0.7.
dropout after MLP
AllaaobiCoov
0.5, 0.7,
dropout in MI.P
JacobiCony
0.5. 0.7
dropout after MLP
JacobiConv
0.5, 0.7
learning rale
0.001,
learning rate of W
All
0.01,
weight decay of @
All
0.0, 0.0005
weight decay of W
All
0.0, 0.000
JacobiConv
0.55
JacobiCony
0.55,
propagation parameter propagation parameter
JacobiConv
0.1.0.9
GPRGNN
0.1, 0.9
"amazon ratings', 'minesweeper', 'questions,, 'roman_empire', 'tolokers'
dropout in MLP dropout after MI.P learning rate of θ learning rate of W weight decay of C weight decay W
All
0.5
AlI
0.5, 0.7
All
0.001,0.00
All
0.01, 0.05
All
0.0, 0.0000
0.0, 0.000.005
JacobiConv
0.55,
JacobiCony
-055,
propagation parameter a propagation parameter
JacobiConv
0.1,
GPRGNN
0.0.
"computers', 'photo', 'coauthor-es', "coauthor-physic'
dropout in MLP dropout after MI.P learning rate learning rate of weight decay of e weight decay of W
All
0.5,
All
0.5. 0.7
0.001,
0.01,
All
0.0, 0.005
All
0.0, 0.0005
JacobiConv
0.5,
JacobiConv
-0.5,
propagation parameter propagation parameter
JacobiConv
0.1,
GPRGNN
0.1,
Table 8: Grid search ranges of hyperparameters. Dropout search ranges JacobiCony is smaller than other spectral GNNs it contains too many hyperparameters, have to reduce the search range to guarantee that the searching process can be finished in accepted computing time.
18

---

Published as a conference paper at ICLR 2026
B.4 SPECTRAL GNNS
We provide the detailed description for spectral GNNs used in our experiments in the following.
For a graph with the adjacency matrix A, the degree matrix D, and the identity matrix 7, we use and A' (D+ +) () T) + /)-1/2 to denote the normalized Laplacian matrix, the shifted normalized Laplacian matrix, the normalized adjacency, matrix and the normalized adjacency matrix with self-loops, respectively.
= - D-122 A L. - --11/2 AD-1/2 A = D-1/2AD-----
ChebNet (Defferrard et al. 2016 This model uses the Chebyshev basis to approximate spectral filter:
K Σ k=
Y
(L)
where X the raw feature matrix, θ -0000 01..... 0x] the graph convolution parameter, W is the feature transformation parameter and fw(X is usually a 2-layer MLP. (x( is the k-th Chebyshev basis expanded on the shifted normalized graph Laplacian matrix and is recursively calculated:
To(L) =
(ī(). i.
[L) = -2ÍTxI(()) Tk- 2L)
ChebNetII (He al. 2022a): The model is formulated
Σ _ (1) K + k=0,==0
2
where X is the input feature matrix, W is the feature transformation parameter, fw(() ( is usually 2-layer MLP, (-) is the k-th Chebyshev basis expanded on cos ((j + 1/2) x/ (K + 11) is the j-th Chebyshev node, which is the root of the Chebyshev polynomials of the first kind with degree K + 1, and 8, is a learnable parameter. Graph convolution parameter in ChebNet is reparameterized with Chebyshev nodes and learnable parameters 0z-
JacobiNet (Wang & Zhang 2022): This model uses the Jacobi basis to approximate filter as:
Ý Σ On pa. P (A)sw(X).
where is the input feature matrix, θ =0 01....,0y. is the graph convolution parameter, W is the feature transformation parameter and fw (X) is usually a 2-layer MLP. PP. is the Jacobi basis normalized graph adjacency matrix À and is recursively calculated as
p (A) =
b (A) 1 1-b1+ a+ b+2
1+
A
2
2
pe pa. (A) 7 b
ipab
k- (A) 2/c pab (Ā) th (
where ?ik (2k+a+ ((2+ % (2
2 (6+1-D)(+b-
2k(k+a+b)
+(k+o+))2b+o+b
and are hyperparameters. Usually, grid search used to find the optimal and values.
GPRGNN CChen et al., (202T): This model uses the monomial basis to approximate filter:
K A fx
k=
19

---

Published as a conference paper at ICLR 2026
where X is the imput feature matrix, e [Bu, ....... 0x] is the graph convolution parameter, W the feature transformation parameter and fw (X) is usually 2-layer MLP. A' is the normalized adjacency matrix with self-loops.
BernNet (He al. 2021): This model uses the Bernstein basis for approximation:
K
K
(21 - Jw())
2
k=
where X is the input feature matrix, = 10n, 0,,..., 0x] the graph convolution parameter, is the feature transformation parameter and Jw (X) is usually a 2-layer MLP. É is the normalized Laplacian matrix.
B.5 FULL EXPERIMENTAL RESULTS ON LARGE HETEROPHILIC GRAPHS
We show our full experimental results on large heterophilic graphs Table 2 There an average 1.08% accuracy improvement Roman Empire, Amazon Ratings and average 1.1% ROC AUC improvement on the rest datasets.
Model ChebNet(O)
Roman_ Empire
Amazon Ratings
Tolokers
Minesweeper
Questions
47.15e042
39.79sa29
70. +o.25
86.29e02
35.134054
cheb (M)
54.55to.3
40.92sa27
69.2
86.7202
55.221
A
+7.4
+1.13
-0.9
+0.41
+0.07
ChebNetll
35.442n19
39.99ga2s
69.93anm:
78.35a0.14
64.132095
ChebNetll (M)
55.
40.66aa33
70.94an36
79.1
65.54a0.7
A f
-0.34
+0.67
+1.01
+0.75
+1.41
JacobiConv (0)
55, 85.857577
40.27am3
70.1
87.34an.12
64.72a035
JacobiConv (M)
56.21
40.17
71,04e022
89.13e0.
82.88
A
+0.35
-0.1
+0.94
+1.79
+1.08
GPRGNN (O)
56.33e151
40.07=025
66.3481.6
87.154n.9
53. 14
GPRGNN (M)
56.9621.99
40.14
68 68.44
38.58
58. 19
A
+0.63
+0.07
+2.1
+1.43
+5.05
BernNet (O)
55.0620.
392357
68.812n91
76.54am.23
64.862037
BerNeet
55.5
39.85a023
69.49aa72
76.95an21
65.2an.31
À f
+0.45
+0.49
+0.68
+0.41
+0.34
Table 9: Performance with/without AdaSpec on large heterophilic datasets (Roman Empire, Ama- zon Ratings, Tolokers, Minesweeper, Questions ). Test accuracy is used as the metric for Roman- Empire and Amazon-Rating datasets and ROC AUC is reported on Minesweeper, Tolokers, Ques- tions. High accuracy and ROC AUC indicate good performance.
Model
Texas
Wisconsin
Actor
Chameleon
Squireel
Cornell
Citsseer
Pubmed
Cora
ChebNer(O)
38.67exa:
32.92e13
25.15
29.32
24.23
31.33
69.21aus7
75.24
80.45
GDC ChehNee(()
50,58=50
34.00=74
24.92=07
21 S2522222
20.62+1.7
28.50a7m
67.52a137
74.53e1.5
75.91
ChebNee(M)
52,14
36.3144
24.15
a1
22.02
34.1
68.26
77.22 45
21.01
A
+1.56
+2.33
-0.77
+10.32
+1.40
+6.41
+0.74
+2.69
+5.10
Table 10: Impact of AdaSpec applied on top of GDC. Our method (GDC + ChebNet(M)) consistently improves performance ChebNet(O) ). (2) ChebNet with GDC ( (GDC+ChebNer())) ), and (3) ChebNet with GDC + AdaSpec (GDC+CheNNe(M1) )
most benchmarks. Three configurations: (1) Standard ChebNet (
20

---

Published as a conference paper at ICLR 2026
B.6 EXPERIMENTAL RESULTS ADASPEC WITH GRAPH DIFFUSION CONVOLUTION
Our AdaSpec is not competitor to graph rewiring; it is a plug-and-pla spectral enhancement. We demonstrate below that, can be seamlessly integrated with existing graph rewiring methods like graph diffusion convolution (GDC) to achieve superior performance, validating its unique value proposition beyond standard rewiring.
we conducted set of experiments combining AdaSpec with GDC and results are shown in Ta- ble TO] Our key findings are as follows. (1) Performance improvement: GDC+ChebNe((M) improves performance than GDC+ChebNet(O) In 8 out of 9 reported cases. (2) Orthogonality: If AdaSpec and GDC were solving the exact same problem (competitive mechanisms), stacking them would yield diminishing returns. The fact that AdaSpec provides significant gains on top of GDC proves they address orthogonal limitations of the graph structure. (3) Spatial rewiring optimizes topological connectivity (e.g., denoising edges to improve homophily). AdaSpee optimizes eigenspace. Even graph that is topologically clean (via GDC) may still suffer from eigenvalue multiplicity missing frequency components the spectral domain. AdaSpec resolves these spectral collisions, which GDC cannot detect repair.
21


Reviews:
[{"review_id": "QhzjTqsjYB", "reviewer": "Reviewer_RPRH", "summary": "AdaSpec is an adaptive spectral module for GNNs that learns to modify a graph’s spectral structure (eigenvalues and frequency components) to make node representations more distinguishable. It generates an adjusted graph matrix that increases the number of distinct eigenvalues and enhances the frequency coverage of node features in the spectral domain. The approach is theoretically grounded, preserving permutation equivariance and providing provable guarantees on node distinguishability.", "questions": "See all the points in weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- AdaSpec provides a clear theoretical analysis linking graph spectra and node features to node distinguishability, and even derives a lower bound on how many nodes can be distinguished.\n- Unlike prior spectral GNNs that use fixed graph matrices, AdaSpec learns to adjust the graph’s spectral structure (eigenvalues and frequency components), leading to improved representational power without extra computational cost.\n- The method maintains a critical property for graph learning (permutation equivariance) ensuring that node reordering doesn’t change the model’s predictions, which preserves theoretical and practical soundness.\n- The model is rigorously tested across 18 benchmark datasets, consistently improving node distinguishability and classification performance, showing that the theoretical ideas transform into real-world gains.", "weaknesses": "- While AdaSpec focuses on adaptive graph matrix generation, prior works like ARMA-GNN [1], SpecFormer [2] already explored adaptive spectral filtering or learnable spectral responses. AdaSpec’s contribution lies more in its theoretical framing (node distinguishability + eigenvalue diversity) than in introducing a fundamentally new mechanism.\n\n[1] Graph Neural Networks with convolutional ARMA filters\n[2] Specformer: Spectral Graph Neural Networks Meet Transformers\n\n- Although AdaSpec theoretically explains how distinct eigenvalues improve distinguishability, it doesn’t provide much empirical interpretability (how the learned spectral modifications relate to graph structure or which frequencies become emphasized). This makes the adaptive mechanism somewhat of a black box.\n\n- The paper claims “no increase in computational complexity,” but adaptively generating or modifying a graph matrix could introduce training instability or hidden overhead.\nThe supplementary doesn’t discuss runtime comparisons or scalability to very large graphs, areas where methods like GPR-GNN [3] are better optimized. What will be the performance of AdaSpec on the cases of very large graphs?\n\n[3] Adaptive Universal Generalized PageRank Graph Neural Network\n\n- Recent works such as SpecFormer achieve similar goals but with stronger end-to-end learnability and better scaling to large, dynamic graphs.\n\n- Can AdaSpec handle temporal or evolving graph spectra, or is it limited to static adjacency matrices?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SjWQs6VhOF", "reviewer": "Reviewer_1nzt", "summary": "This paper investigates the problem of node distinguishability in spectral Graph Neural Networks (GNNs). The authors state that a spectral GNN's ability to distinguish nodes is theoretically lower-bounded by two main factors: the number of distinct eigenvalues of the graph matrix ($d_M$) and the number of non-zero frequency components of the node features in the matrix's eigenbasis. Based on this analysis, the paper proposes AdaSpec, a plug-in module that generates an adaptive graph matrix $\\Omega(A,X)$ designed to maximize this lower bound. AdaSpec consists of three components: $\\Omega_D(A)$ to increase distinct eigenvalues using a learnable diagonal matrix, $\\Omega_S(A)$ to shift eigenvalues from zero, and $\\Omega_F(X)$ to increase the number of non-zero frequency components by incorporating feature information. The authors provide theoretical guarantees that AdaSpec maintains permutation equivariance and empirically demonstrate its effectiveness at improving node classification, particularly on heterophilic datasets.", "questions": "Q1. To validate the paper's central claim, the authors must demonstrate that their spectrally-motivated adaptive matrix is more effective than other spatially-motivated or general-purpose adaptive matrices.\n\nQ2. It is better to move the formal definition of node distinguishability (Definition 4.1) to the preliminaries (Section 3) or to provide a concise, informal definition in the introduction.\n\n\nQ3. Could the authors elaborate on the unique necessity of the $\\Omega_S(A)$ component given the presence of $\\Omega_D(A)$? Does the learnable diagonal matrix $B$ in $\\Omega_D(A)$ not already provide sufficient flexibility to shift eigenvalues, including the zero eigenvalues?\nThe ablation study (Table 4) shows that $\\Omega_S(A)$ on its own has inconsistent and often poor performance (e.g., on Citeseer and Cora), suggesting it may be redundant or unnecessary.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "S1.  The paper tackles an important and specific problem—node distinguishability for spectral GNNs.\n\nS2. The design of the AdaSpec module is well-motivated. Each of its three components ($\\Omega_D$, $\\Omega_S$, $\\Omega_F$) is explicitly designed to address a specific limitation identified in the theoretical analysis.\n\nS3. The experiments are extensive, covering 18 benchmark datasets with diverse characteristics (homophilic, heterophilic, large, and small). The ablation study in Table 4 validates the contribution of each component of AdaSpec.", "weaknesses": "W1. The most critical flaw is the failure to compare AdaSpec against other relevant graph augmentation or rewiring methods. The paper frames its contribution as a graph matrix generation module, which is functionally a form of learnable graph rewiring or augmentation. Although the authors claimed that they are the first to study node distinguishability, many other papers on spectral GNNs studied the expressive power of spectral GNNs, where node distinguishability was explicitly or implicitly studied. As we can see from the methodology and the experiments, AdaSpec is in fact a graph augmentation method for spectral GNN. Adding a comparison with other related augmentation methods in spectral GNN is necessary.\n\nW2. The related work section acknowledges graph rewiring techniques (e.g., DropEdge, DiffWire, FoSR) but dismisses them as \"fundamentally different\", arguing they operate in the spatial domain. This distinction is not convincing. The goal is the same: modify the graph structure to improve GNN performance.AdaSpec also demonstrates its improved GNN performance, not in terms of node distinguishability. On the other hand, there are many methods that operate in the spectral domain.\n\n\nW3. The experiments only compare spectral GNNs with AdaSpec to the same GNNs without it (i.e., using a fixed matrix). This demonstrates that some form of adaptation is better than none, but it fails to show that AdaSpec is superior to, or even competitive with, other existing augmentation/rewiring techniques. The observed performance gains might simply stem from adding any adaptive rewiring, rather than from the specific spectral motivations of AdaSpec.\n\n\nW4.   The paper's central concept, \"node distinguishability,\" is not formally defined until Section 4 (Definition 4.1). This is a major structural flaw. The term is used in the title, abstract, and throughout the entire introduction without a precise technical definition.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JqDmOGAT7X", "reviewer": "Reviewer_D6hk", "summary": "This is a good paper that mainly investigates how distinct eigenvalues and missing frequency components affect node distinguishability. The paper proposes AdaSpec, which includes three modules: INCREASE DISTINCT EIGENVALUES, SHIFTS EIGENVALUES FROM ZERO, and INCREASE FREQUENCY COMPONENTS. The proposed method is supported by solid theoretical proofs, and extensive experiments demonstrate the effectiveness of AdaSpec.", "questions": "please see Weaknesses", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1.The paper studies how the graph matrix and node features jointly influence node distinguishability, which is an interesting direction.\n\n2.The paper provides solid theoretical proofs to support the proposed method.\n\n3.The time complexity analysis and comprehensive experiments further validate the effectiveness of AdaSpec.", "weaknesses": "1.In line 175, the paper states that “The presence of zero eigenvalues can hinder node distinguishability”, but I did not find any detailed explanation about this point. It should be the zero frequency components, not the zero eigenvalues, that hinder node distinguishability. The authors need to clarify the role of Section 5.2 in detail; otherwise, this section should be removed.\n\n2.In lines 91–94, the paper mentions that eigenvalue correction does not ensure permutation invariance, but no further explanation is provided, leaving readers unclear about why this is the case.\n\n3.In Figure 1, why can’t node 1 and node 3 be distinguished? Based on the current analysis, this conclusion does not seem directly supported.\n\n4.Although the paper mainly studies node distinguishability, only Figure 1 involves this concept; both the method and experiment sections lack relevant discussion. The authors could conduct further analysis, for example, by relating their work to the Weisfeiler–Lehman (WL) test.\n\n5.The two factors affecting node distinguishability mentioned in this paper — distinct eigenvalues and nonzero frequency components — have already been discussed in prior work, such as Wang & Zhang (2022). This weakens the contribution of the present paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "izHml9q89L", "reviewer": "Reviewer_kQFo", "summary": "This paper proposes to enhance spectral GNNs by improving their node distinguishability. Namely it starts by observing that node distinguishability is limited by two factors, the repeated eigenvalues in the graph adjacency matrix and the missing frequency components in the node features. Based on this, the paper proposes to modify the graph shift operator used in spectral GNNs with constructions that improve the two factors, and provides theory supporting this. Finally, experiments on many transductive datasets are performed by using the learned graph shift operator in various spectral GNNs. Results show improvements over baselines and show that the number of distinct eigenvalues is indeed increased on several datasets.", "questions": "1. Fig 1 a) The paper states that a spectral GNN cannot distinguish nodes 1 and 3. Should a GNN be able to distinguish these? It seems like nodes 1 and 3 are isomorphic as the node features is [1, 0, 1, -1, -1].\n2. Proof of theorem 5.1: “More unique coefficients in characteristic polynomial implies more unique eigenvalues of the matrix.” Can you clarify what you mean by this? Are you claiming that more different coefficients imply more roots to a polynomial? A counterexample to this claim is: (x-1)^3 =x^3-3x^3+3x-1 has 4 distinct coefficients but a single root and (x-1)(x-2)(x-3)=(x^2-3x+2)(x-3) = x^3 -6x^2 +11x -6 has three distinct roots but three distinct coefficients.\n3. Theorem 5.2 relies on Theorem A.1 which require C to have no repeated eigenvalues, hence the statement of Theorem 5.2 is wrong/misleading since it seems like it applies to any matrix C. Particularly, since the motivation is that the adjacency has repeated eigenvalues, and a modification of A will play the role of C makes me question the usefulness of this statement in the context of the paper.\n4. Table 4: Please add the base performance of ChebNet.\n5. Table 5: please add the statistics for all datasets, not necessarily in the main text.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. **Motivating objective.** The focus on improving node distinguishability in spectral GNNs is well-motivated and addresses a relevant limitation of existing approaches.\n\n2. **Theoretical development.** The paper provides substantial theoretical analysis in support of the proposed method, offering formal insights into the factors influencing node distinguishability.\n\n3. **Clear experimental framing.** The experiments are structured around clear research questions, making it easy to understand the intended empirical validation.\n\n4. **Breadth of evaluation.** The method is evaluated on a range of standard transductive benchmark datasets, demonstrating applicability across multiple settings.", "weaknesses": "1. **Practical relevance of the theoretical bound.** The main conceptual contribution is an improved lower bound on the number of nodes that can be distinguished. However, it remains unclear how meaningful this bound is in practice, or whether it provides actionable guidance for model design or empirical performance.\n\n2. **Clarity of assumptions.** Some theoretical results (e.g., Theorem 5.2) rely on assumptions that are either not fully stated or not clearly motivated. It would be helpful to explicitly articulate these assumptions and discuss their necessity and scope.\n\n3. **Novelty claims may be overstated.** The statements “To the best of our knowledge, no existing work has systematically analyzed the interaction between the graph matrix and node features in determining node distinguishability in spectral GNNs” and “In this work, we demonstrate that node distinguishability is influenced by the eigenvalue multiplicity and the missing frequency components of node features in the eigenbasis of the graph matrix” appear stronger than warranted. Similar themes were examined in prior work, particularly [1]. The contribution would be clearer if the relationship to [1] were more explicitly discussed and the novelty claims were calibrated accordingly.\n\n4. **Readability and exposition.** The paper is difficult to follow in several places. A clearer introduction to the problem setting, intuition for the theoretical results, and more accessible mathematical presentation would greatly improve readability.\n\n5. **[Minor]Limited significance of empirical results.** The experimental findings are not particularly strong: in Table 2, 25 out of 40 comparisons are not statistically significant, and in Table 3, 27 out of 35 are not significant. That said, this is standard in the field. \n\nReference:\n[1] Wang, X., & Zhang, M. (2022). How powerful are spectral graph neural networks? In ICML (pp. 23341–23362). PMLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)