acceptodds
Under review as a conference paper at ICLR 2027

Spectralization: Generalizing Spectral Invariants for Expressive Graph Learning

Abstract

Spectral invariant graph neural networks (GNNs), which use spectral invariants to avoid eigenvector ambiguities, have demonstrated strong expressive power. Rooted graph invariants (RGIs), such as distance measures and substructure counts, are also commonly incorporated as structural encodings to improve the expressiveness of GNNs and graph Transformers. We connect these two threads by reformulating these spectral invariants in terms of spectral responses to the identity signal, which is itself an elementary RGI. The construction of these spectral invariants can thus be understood as spectrally enriching the identity signal by capturing its interactions with graph topology. We therefore propose Spectralization, a general framework that extends this construction from the identity signal to arbitrary RGIs, thereby substantially broadening the scope of spectral invariants. To demonstrate its benefits, we spectralize the atomic types underlying Weisfeiler-Leman (WL) refinement to obtain Spectralized -FWL, which we prove to be strictly more expressive than -FWL for every and place within a hierarchy of classical and spectral WL variants. Beyond atomic types, we further show that spectralizing diverse RGIs can improve model expressiveness compared with using their raw forms directly. We then develop structural encoding schemes guided by Spectralization, with experiments corroborating these expressiveness gains on graph-isomorphism benchmarks and demonstrating improved predictive performance across multiple neural architectures and downstream tasks.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, Graph Transformers, Structural Encodings, Positional Encodings, GNN Expressiveness

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_RRSaOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes the general Spectralization framework, which generalizes spectral invariants from the identity signal to arbitrary rooted‑graph invariants (RGIs). It develops the Spectralized k‑FWL theory and proves that it is strictly more expressive than k‑FWL. Furthermore, the authors design the practical spectralized structural encoding SpecSE, which yields empirical improvements on the graph‑isomorphism benchmark BREC, molecular‑property regression, and graph‑classification tasks. The paper features rigorous mathematical derivations and clear problem formulation. Nevertheless, it suffers from several key drawbacks. For instance, certain open problems are not adequately discussed, and some comparisons within the experimental setup are insufficient.

Critical strengths
  1. The interpretation of spectral invariants as responses to the identity signal is conceptually insightful, providing a unified framework for extending spectral representations to more informative rooted graph invariants.
  2. The paper makes theoretical contributions, including strict expressiveness gains of Spec k-FWL over k-FWL for k≥2, a hierarchy of WL variants and gains from spectralizing selected count and distance invariants.
Critical weaknesses
  1. The connection between the expressiveness theory and practical SpecSE remains incomplete. Whether the finite filter banks and compression used in experiments preserve the theoretical expressiveness gains remains unclear. Theorem 4.10 relies on a case‑by‑case separation argument, constructing dedicated witness graphs for each given class of RGIs. However, it lacks a general criterion for characterizing which RGIs are guaranteed to yield strict expressiveness gains upon spectralization.
  2. There are several shortcomings in the experimental section. For example, only results for Spec 2‑FWL are reported on the BREC benchmark; experiments for Spec k‑FWL with k>2k>2 are missing. In addition, the paper does not investigate the impact on performance stemming from the number of filters and the polynomial order K, nor does it examine which RGIs yield the largest gains when spectralized.
Questions for authors
  1. Theorem 4.10 establishes strict gains for individual RGIs. Do these gains persist for the jointly encoded RGI families used in the experiments, and can the authors provide a separating graph pair for this joint setting?
  2. Eq.(3) avoids eigendecomposition but propagates matrix signals. What are the time and memory costs as graph size increases, including storage of all precomputed polynomial basis responses?
  3. Eq.(4) preserves raw RGIs through concatenation, whereas the implementation compresses these signals. Please clarify whether this compression preserves the original information and the additional distinctions introduced by spectralization.
  4. The paper lacks ablation studies. Could the authors separately ablate spectral filtering, raw signal inclusion, and response compression under consistent experimental settings to clarify their respective contributions?
  5. Table 3 shows smaller gains over MoSE on ZINC. Could global aggregation already capture some of the structural information introduced by spectralization?
  6. The paper contains some grammatical errors, such as “a S-valued” (Section 3) and “the first-order case recover” (Section 4). The authors should carefully proofread the entire paper.
4 comments

We thank the reviewer for the constructive feedback and address the concerns below.

W1 & Q3: Connection Between Theory and Practical SpecSE

"W1: Whether the finite filter banks and compression used in experiments preserve the theoretical expressiveness gains remains unclear."

"Q3: "Please clarify whether this compression preserves the original information and the additional distinctions introduced by spectralization."

We respond to this concern in two parts: (i) finite filter banks and (ii) response compression.

(i) Finite Filter Banks

We agree that the connection between full Spectralization and its finite-filter realizations needs further clarification. As this concern was raised by multiple reviewers, we address it in our General Response: Preserving Full Expressiveness with Finite Spectral Filters posted above.

(ii) Response Compression

While arbitrary compression is not guaranteed to preserve all individual spectral responses, our Proposition 5.3 and Corollary 5.4 shows that multiple output channels are not inherently necessary to retain the full expressive power of Spectralization.

In practice, we employ multiple learnable filters to provide greater flexibility during training and facilitate task-adaptive representation learning, rather than because multiple filters are theoretically required for full expressiveness.

"W1: It lacks a general criterion for characterizing which RGIs are guaranteed to yield strict expressiveness gains upon spectralization."

We respond to this concern from two perspectives: (i) strict expressiveness gains of refinement algorithms and (ii) strict refinement of RGIs themselves.

(i) Strict Expressiveness Gains

We agree with the reviewer that we currently lack a general criterion guaranteeing strict expressiveness gains. We have discussed this in Appendix A, Limitations and Discussions. Developing a more general criterion remains an interesting and challenging open question for future research.

(ii) Strict Refinement of RGIs

Nevertheless, at the level of RGIs themselves, we can establish general strict-refinement results. In the newly added Appendix D.5 Spectralization Strictly Refines RGIs, we prove that Spectralization strictly refines all those distance RGIs and substructure count RGIs.

However, strict refinement at the RGI level does not imply a strict expressiveness gain for the corresponding refinement algorithms. This is because the expressiveness gain from Spectralization may already be captured by an expressive refinement algorithm itself.

Revision: We added Appendix D.5, Spectralization Strictly Refines RGIs.

W2: Higher-Order BREC Experiments

"[...] experiments for Spec k-FWL with (k>2) are missing."

We extend our BREC experiments to include 33-LWL, SI 33-OWL, 33-FWL, and Spec 33-FWL. The complete results are summarized below:

\hline \text{Method} & \text{Basic (60)} & \text{Reg (140)} & \text{Ext (100)} & \text{CFI (100)} & \text{Overall} \\\\ \hline 2\text{-LWL} & 60 & 50 & 100 & 57 & 267 \\\\ \text{SI }2\text{-OWL} & 60 & 50 & 100 & 60 & 270 \\\\ 2\text{-FWL} & 60 & 50 & 100 & 60 & 270 \\\\ \text{Spec }2\text{-FWL} & 60 & 137 & 100 & 70 & 367 \\\\ \hline 3\text{-LWL} & 60 & 138 & 100 & 80 & 378 \\\\ \text{SI }3\text{-OWL} & 60 & 138 & 100 & 80 & 378 \\\\ 3\text{-FWL} & 60 & 140 & 100 & 80 & 380 \\\\ \text{Spec }3\text{-FWL} & 60 & 140 & 100 & 96 & 396 \\\\ \hline \end{array}$$ These results are consistent with our theoretical hierarchy. We did not extend the experiments beyond $k=3$, as higher-order implementations become computationally prohibitive. **Revision**: We updated Table 1 in the main text.

W2 & Q4: Ablation Study

Since the graph sizes in our experiments allow explicit spectral decomposition, all our final experiments use the spectral decomposition-based implementation of SpecSE, where spectral filters are directly parameterized by neural networks. Therefore, the polynomial degree KK is not an explicit parameter of our implementation, making a polynomial-order ablation inapplicable.

Nevertheless, we investigate the contributions of spectral filtering and raw RGIs, as well as the impact of the number of learned spectral filters. Here we report ablation experiments on two QM9 targets, α\alpha and Ω\Omega, using the same GPS backbone. The variants are defined as follows:

  • SpecSE: Our full model, using four learned spectral filters per RGI.
  • Raw Filtering: Replaces the input RGIs with the equality signal 1[u=v]\mathbf{1}[u=v], retaining spectral filtering but removing other RGIs.
  • Raw RGI: Uses the original RGIs directly, without Spectralization.
  • SpecSE(2)/SpecSE(6): Changes the number of learned spectral filters per RGI from the default four to two or six, respectively.

The results are summarized below:

\hline \text{Property} & \text{SpecSE} & \text{Raw Filtering} & \text{Raw RGI} & \text{SpecSE(2)} & \text{SpecSE(6)} \\\\ \hline \alpha & 1.28\pm0.03 & 1.55\pm0.12 & 1.49\pm0.07 & 1.33\pm0.09 & 1.29\pm0.05 \\\\ \Omega & 0.36\pm0.01 & 0.42\pm0.02 & 0.39\pm0.02 & 0.36\pm0.02 & 0.35\pm0.01 \\\\ \hline \end{array}$$ As shown, both removing Spectralization and replacing the original RGIs lead to worse performance. Meanwhile, varying the number of learned filters does not yield a consistent improvement. This is consistent with our single-filter completeness result discussed in **W1 & Q3**: even a single suitably chosen filter can preserve the full expressiveness, so a larger filter bank may not be inherently necessary. Regarding which RGIs benefit most from Spectralization, we agree that this is an important question worth further investigation. However, a systematic comparison of individual RGIs is beyond the scope of this work, and we leave it for future research. ## **Q1: Strict Gains for Jointly Encoded RGI Families** Yes, we can provide a separating graph pair for this joint setting. Specifically, we consider the two families of RGIs used in our experiments: 1. Homomorphism counts based on all connected graphs with at most five vertices, with $C_6$ additionally included for QM9. 2. $\operatorname{Spasm}(C_7)\cup\operatorname{Spasm}(C_8)$, as used in ZINC-12K. We find that the same pair of non-isomorphic graphs witnesses a strict distinguishing gain from Spectralization for both families. The separating graph pair and its verification have been added to our updated code under `Joint RGI gain`. ## **Q2: Time and Memory Cost** We discuss two types of structural encodings with different scalability: **(i) node-pair encodings obtained by spectralizing 2-RGIs**, and **(ii) node-level encodings obtained by spectralizing 1-RGIs**. Let $n$ be the number of nodes, $R$ the number of input RGIs, $K$ the maximum polynomial degree, and $F$ the number of learned filters. We write $s_G=n+\operatorname{nnz}(T_G)$, where $T_G$ is the graph operator and $\operatorname{nnz}(T_G)$ denotes its number of nonzero entries. ### **(i) Node-Pair Structural Encodings (2-RGIs): $O(n^2)$** With $B=\binom{K+2}{2}$ polynomial basis filters, its main costs are: - **Preprocessing:** $O(RBs_Gn)$. - **Precomputed storage:** $O(RBn^2)$. - **Forward feature mixing:** $O(RBFn^2)$. This quadratic dependence arises because we explicitly construct structural encodings for all ordered node pairs. ### **(ii) Node-Level Structural Encodings (1-RGIs): $O(n)$** For stronger scalability, we can instead spectralize 1-RGIs, such as node-rooted substructure counts, to construct node-level structural encodings. In this case, each spectral response is an $n$-dimensional vector rather than an $n\times n$ matrix, and the polynomial basis contains only $K+1$ filters. The corresponding costs become: - **Preprocessing:** $O(R(K+1)(s_G+n))$. - **Precomputed storage:** $O(R(K+1)n)$. - **Forward feature mixing:** $O(R(K+1)Fn)$. We further report the actual memory footprint of raw RGIs and precomputed polynomial spectral responses on ZINC-12K, for different polynomial degrees: $$\begin{array}{lcccc} \hline \text{RGI} & \text{Raw} & K=3 & K=5 & K=10 \\\\ \hline 1\text{-RGI} & 46.68\\ \text{MB} & 186.72\\ \text{MB} & 280.09\\ \text{MB} & 513.49\\ \text{MB} \\\\ 2\text{-RGI} & 100.46\\ \text{MB} & 1.005\\ \text{GB} & 2.110\\ \text{GB} & 6.630\\ \text{GB} \\\\ \hline \end{array}$$ **Revision:** We have added Appendix F.3, *Computational Complexity and Scalability*, to provide a detailed analysis of the time and memory complexity of different Spectralization implementations, together with empirical memory measurements.

Q5: Global Aggregation and Spectralization

Yes, this is possible.

As discussed in our response to W1 & Q3, a strict refinement of an RGI through Spectralization does not necessarily lead to a strict expressiveness gain when incorporated into a GNN, since the additional structural information may already be captured by the underlying message-passing mechanism.

A concrete example is Spec 22-FWL, where spectralizing only the initial pairwise atomic types does not improve its distinguishing power, as the underlying refinement already captures their spectral responses (Table 6, Appendix F.1).

Therefore, this depends on both the choice of RGIs and the expressiveness of the message passing. We acknowledge that systematically identifying suitable RGIs for different datasets and message-passing mechanisms remains an important open question for future research.

Q6: Presentation and Grammatical Issues

We thank the reviewer for pointing these out. We have corrected the cited expressions.

We thank the reviewer again for the detailed suggestions, which have helped us strengthen the theoretical results and clarify practical implementations.

Thanks for the authors‘ replies and I will keep the original score.

Reviewer_JTYgOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper connects spectral invariant GNNs with rooted graph invariants (RGIs). Earlier spectral invariants, the eigenspace projection invariant of Zhang et al. (2024b) and its higher order extension SI k-OWL of Gai et al. (2025), stay below k-FWL (for SI k-OWL this is Thm 4.7(ii) here). The authors observe that the eigenspace projection invariant is equivalent to the spectralization of the identity RGI, i.e. its responses to all second order spectral filters together with the spectrum (Thm 4.4). They define spectralization for any k-RGI and apply it to atomic types to get Spec k-FWL, which is strictly more expressive than k-FWL for every k ≥ 2 and bounded by (k+1)-LWL (Thm 4.7). They also show that spectralizing rooted homomorphism and subgraph counts, SPD, diffusion and biharmonic distances strictly helps 1-WL (Thm 4.10).

On BREC, Spec 2-FWL distinguishes 367 of 400 pairs against 270 for 2-FWL. The authors also propose SpecSE structural encodings and evaluate them on QM9, ZINC-12K and CIFAR10 against RWSE and MoSE.

Critical strengths
  1. The question is a good one and the approach is original. Spectral invariants built from eigenspace projectors do not go beyond k-FWL, and this paper finds a principled way to get spectral information that does. Thm 4.4 gives a clean view of the eigenspace projection invariant as the spectralization of the identity signal, and Thm 4.7 places Spec k-FWL, SI k-OWL, k-LWL and k-FWL in one hierarchy. The appendix proofs are detailed, and the concrete witnesses, e.g. Rook and Shrikhande in Cor D.4, check out.

  2. The BREC results follow the theory closely. Spec 1-WL and SI 1-WL both get 236 (Prop 4.9), and Spec 2-FWL gets 367 against 270 for 2-FWL, with the gains on the Regular (137 vs 50) and CFI (70 vs 60) categories. It is nice that the learned SpecPPGN also almost doubles PPGN on CFI (38.0 vs 20.3).

Critical weaknesses
  1. It is not clear what drives the strict gain in Thm 4.7(i). Def 4.5 defines the spectralized atomic type on k-tuples (lines 236-238), but the update in Def 4.6 uses SatpG(v,w)Satp_G(v, w) on (k+1)-tuples (line 244). The main text does not say this. It matters, since for strongly regular graphs every eigenspace projector lies in span{I,A,J}\mathrm{span}\{I, A, J\}, so spectral labels on pairs carry only the atomic type. With pair labels alone Spec 2-FWL cannot separate Rook and Shrikhande. The separation comes from the order k+1 response, and Prop D.1 (lines 1350-1382) uses the filter ∏jzj\prod_j z_j, i.e. A⊗(k+1)A^{\otimes (k+1)}, which counts Kk+2K_{k+2}. So the gain over k-FWL is a clique count from an order k+1 filter rather than the spectral enrichment of Thm 4.4, which is also why the upper bound is (k+1)-LWL. There is no complexity or runtime statement in the paper, although these labels range over all (k+1)-tuples.

  2. Positioning and experiments. By Thm 4.7 applied at k+1 (T = A), Spec k-FWL ⪯ (k+1)-LWL ≺ SI (k+1)-OWL, so the higher order spectral invariant WL of Gai et al. (2025) at order k+1 is strictly stronger. The paper does not discuss this, and Table 1 has no 3-FWL or SI 3-OWL row. The downstream gains are mostly within one standard deviation. On QM9, 10 of the 13 gaps to MoSE are below one pooled standard deviation, and on ZINC-12K the gain disappears for GINE+VN and GPS (0.066 vs 0.068, 0.061 vs 0.062). Also, lines 465-468 say the MoSE configuration is retained, but App. F (lines 2834-2837) switches the local branch from GIN-E to R-GCN for U0, U, H, G and ZPVE. So in my view the contribution of the paper is mainly theoretical.

Questions for authors

Clarifications that could change my assessment:

  1. Please state in the main text that Def 4.6 uses spectral labels on (k+1)-tuples, and give the time and memory cost. Is the strict gain in Thm 4.7(i) entirely due to the order k+1 response? For example, how close does 2-FWL get on BREC when initialized with the number of K4K_4 containing each pair?

  2. How does Spec k-FWL compare with SI (k+1)-OWL in cost? Please add 3-FWL and SI 3-OWL to Table 1.

  3. Please report GIN-E results for U0, U, H, G and ZPVE on QM9, or explain the switch to R-GCN.

  4. For BREC, which operator T do you use, how are the order 3 labels computed, and what exactly does SpecPPGN add to PPGN?

Suggestions for future work (not part of my assessment):

  1. Resistance distance is one of the motivating RGIs (lines 216-217) but is not covered by Thm 4.10. Does spectralization strictly help it too?
6 comments

We thank the reviewer for the constructive suggestions. We respond to each concern and question below.

W1 & Q1: What Drives the Strict Gain in Spec kk-FWL

Yes, the strict expressiveness gain indeed comes from the order-(k+1)(k+1) spectral responses. In the following, we first explain the rationale for incorporating these order-(k+1)(k+1) terms and then clarify what drives the strict gain.

Why Incorporate Order-(k+1)(k+1) Responses

In fact, the use of order-(k+1)(k+1) atomic types was already discussed in the original manuscript (Section 4.2, "Atomic Types and FWL"). The original explanation may be overly concise, and we have expanded it to improve clarity.

Specifically, we adopt an augmented kk-FWL formulation, which incorporates order-(k+1)(k+1) atomic types into the refinement process:

\left\lbrace\\!\left\lbrace \left( \widehat{\chi}_{F,G}^{(t)}(\boldsymbol v^{\\,1\leftarrow w}), \ldots, \widehat{\chi}_{F,G}^{(t)}(\boldsymbol v^{\\,k\leftarrow w}), \mathbf{atp}_{G}(\boldsymbol v,w) \right): w\in V(G) \right\rbrace\\!\right\rbrace.$$ **Augmented $k$-FWL is expressively equivalent to standard $k$-FWL**, as established in Lemma C.4 of Appendix C.3 in the original manuscript. In our construction of Spec $k$-FWL, we spectralize both the order-$k$ atomic types $\mathbf{atp}_G(\boldsymbol v)$ used for initialization and the order-$(k+1)$ atomic types $\mathbf{atp}_{G}(\boldsymbol v,w)$ above as structural labels during refinement. Another observation is that our construction can be viewed as a **natural higher-order generalization of the construction of EPWL in [1]**. Specifically, [1] considers an equivalent all-node formulation of $1$-WL, rather than its standard neighborhood-based update: $$\widehat{\chi}_G^{(t+1)}(u)= \operatorname{hash}\left( \widehat{\chi}_G^{(t)}(u), \left\lbrace\\!\left\lbrace \left( \widehat{\chi}_G^{(t)}(v), \mathbf{atp}_G(u,v) \right) : v\in V(G) \right\rbrace\\!\right\rbrace \right).$$ This formulation has the same graph-distinguishing power as standard $1$-WL. EPWL can then be understood as enriching the pairwise atomic type $\mathbf{atp}_G(u,v)$ with the eigenspace projection invariant $\mathcal P^T(G,u,v)$. By Theorem 4.4 and Proposition 4.9, this enrichment is equivalent to the Spectralization of order-$2$ $\mathbf{atp}$. **Therefore, the construction of EPWL can itself be understood as an instance of Spectralization applied to $1$-WL, while our Spec $k$-FWL naturally extends this principle to higher orders.** ### **What Drives the Strict Gain** We agree with the reviewer that, for strongly regular graphs, spectralizing the initial pairwise atomic types does not contribute to the strict gain. To further investigate this mechanism, we conduct the following ablations on BREC: - **2-FWL:** The standard baseline without Spectralization. - **Spec 2-FWL (pair-only):** Spectralizes only the initial $2$-atomic types. - **Spec 2-FWL ($K_4$-pair):** Uses the filter $g(z_1,z_2,z_3)=z_2z_3$ on the $3$-atomic types, which captures **the number of copies of $K_4$ containing a given edge**. - **Spec 2-FWL ($K_4$-node):** Uses the $g(z_1,z_2,z_3)=z_1z_2z_3$ on the $3$-atomic types, which captures **the number of copies of $K_4$ containing a given node**. - **Spec 2-FWL:** Full Spectralization. The results are summarized below: $$\begin{array}{lccccc} \hline \text{Method} & \text{Basic (60)} & \text{Reg (140)} & \text{Ext (100)} & \text{CFI (100)} & \text{Overall} \\\\ \hline 2\text{-FWL} & 60 & 50 & 100 & 60 & 270 \\\\ \text{Spec }2\text{-FWL (pair-only)} & 60 & 50 & 100 & 60 & 270 \\\\ \text{Spec }2\text{-FWL }(K_4\text{-pair}) & 60 & 136 & 100 & 60 & 356 \\\\ \text{Spec }2\text{-FWL }(K_4\text{-node}) & 60 & 137 & 100 & 60 & 357 \\\\ \text{Spec }2\text{-FWL (Exp)} & 60 & 137 & 100 & 70 & 367 \\\\ \text{Spec }2\text{-FWL (Full)} & 60 & 137 & 100 & 70 & 367 \\\\ \hline \end{array}$$ We have the following conclusions: - pair-only Spectralization provides no improvement, consistent with the reviewer's analysis. - The two $K_4$-related filters distinguish 356 and 357 pairs, respectively, demonstrating that counting copies of $K_4$ improves the distinguishing power on regular graphs, but does not provide additional distinctions on CFI pairs. - Full Spec $2$-FWL further distinguishes 10 additional CFI pairs, indicating that its spectral responses capture structural information beyond these particular $K_4$ counts. Detailed theoretical explanations and experimental results are provided in the newly added Appendix F.1. **Revisions:** 1. We added Appendix F.1 to provide detailed experimental settings and further analysis of the graph isomorphism tests on BREC. 2. We revised "Atomic Types and FWL" in Section 4.2 to improve clarity. **Reference:** [1] On the Expressive Power of Spectral Invariant Graph Neural Networks.

W1 & W2 & Q1 & Q2: Comparisons with Higher-Order WL Variants

"W1: There is no complexity or runtime statement in the paper, [...]"

"W2: Table 1 has no 3-FWL or SI 3-OWL row."

"Q1: ...give the time and memory cost."

"Q2: How does Spec k-FWL compare with SI (k+1)-OWL in cost?"

In the following, we address those concerns from two perspectives: (i) graph-distinguishing power, and (ii) computational complexity and empirical efficiency.

(i) Graph-Distinguishing Power

Our theoretical hierarchy establishes

\prec \operatorname{Spec}\\,k\text{-FWL} \preceq (k+1)\text{-LWL} \prec \operatorname{SI}(k+1)\text{-OWL} \prec (k+1)\text{-FWL}.$$ Following the reviewer's suggestion, we have expanded the BREC experiments to include $3$-LWL, SI $3$-OWL, $3$-FWL, and Spec $3$-FWL. The complete comparison is summarized below: $$\begin{array}{lccccc} \hline \text{Method} & \text{Basic (60)} & \text{Reg (140)} & \text{Ext (100)} & \text{CFI (100)} & \text{Overall} \\\\ \hline 2\text{-LWL} & 60 & 50 & 100 & 57 & 267 \\\\ \text{SI }2\text{-OWL} & 60 & 50 & 100 & 60 & 270 \\\\ 2\text{-FWL} & 60 & 50 & 100 & 60 & 270 \\\\ \text{Spec }2\text{-FWL} & 60 & 137 & 100 & 70 & 367 \\\\ \hline 3\text{-LWL} & 60 & 138 & 100 & 80 & 378 \\\\ \text{SI }3\text{-OWL} & 60 & 138 & 100 & 80 & 378 \\\\ 3\text{-FWL} & 60 & 140 & 100 & 80 & 380 \\\\ \text{Spec }3\text{-FWL} & 60 & 140 & 100 & 96 & 396 \\\\ \hline \end{array}$$ These results are consistent with our theoretical hierarchy. ### **(ii) Computational Complexity and Empirical Efficiency** Let $n$ be the number of vertices and $k$ the order of the tuples on which refinement operates. The per-round time complexity and storage requirements are summarized below: $$\begin{array}{lccc} \hline \text{Refinement} & \text{Time / round} & \text{Tuple-color space} & \text{Spectral-label space} \\\\ \hline k\text{-FWL} & O(kn^{k+1}) & O(n^k) & \text{--} \\\\ \text{Spec }k\text{-FWL} & O(kn^{k+1}) & O(n^k) & O(n^{k+1}) \\\\ \text{SI }(k+1)\text{-OWL} & O((k+1)n^{k+2}) & O(n^{k+1}) & O(n^2) \\\\ \hline \end{array}$$ Importantly, **Spec $k$-FWL retains the same per-round time complexity and tuple-color storage as standard $k$-FWL**, at the expense of additional storage and preprocessing for spectralized labels. In contrast, SI $(k+1)$-OWL operates directly on $(k+1)$-tuples, incurring an additional factor of $n$ in its per-round time complexity. We further provide empirical runtime and memory comparisons on BREC, including spectral preprocessing where applicable: $$\begin{array}{lccc} \hline \text{Metric} & 2\text{-FWL} & \text{Spec }2\text{-FWL} & \text{SI }3\text{-OWL} \\\\ \hline \text{Distinguished pairs} & 270/400 & 367/400 & 378/400 \\\\ \hline \text{Total time (s)} & 10.72 & 29.05 & 1377.08 \\\\ \text{Smallest-pair time (s)} & 0.0005 & 0.0228 & 0.0066 \\\\ \text{Largest-pair time (s)} & 0.94 & 2.28 & 245.52 \\\\ \hline \text{Peak host memory (MiB)} & 855 & 1357 & 6378 \\\\ \text{Peak GPU memory (MiB)} & 0 & 310 & 11 \\\\ \hline \end{array}$$ As shown, Spec $2$-FWL achieves stronger distinguishing power than $2$-FWL with moderate additional computational overhead, while remaining more efficient than SI $3$-OWL in runtime and host memory. The GPU memory usage of Spec $2$-FWL and SI $3$-OWL comes from spectral preprocessing: the former computes spectralized atomic types, while the latter computes eigenspace projection invariants. **Revisions:** 1. We updated Table 1 to include order-3 WL variants. 2. We added Appendix F.3, *Computational Complexity and Scalability*, to provide theoretical complexity analysis and empirical runtime and memory comparisons.

W2 & Q3: Concerns on Experiments

"W2: The downstream gains are mostly within one standard deviation. [...] The gain disappears for GINE+VN and GPS."

We agree that the improvements on downstream prediction tasks are less pronounced than those on graph-isomorphism benchmarks. Two main factors help explain this phenomenon.

First, the choice of RGIs matters. On QM9, we follow the RGI selection of MoSE. As shown in Table 3, MoSE itself achieves relatively small improvements over RWSE on many targets, suggesting that the selected RGIs may provide limited additional structural information for these tasks. Nevertheless, SpecSE achieves further improvements over MoSE on most QM9 targets.

Second, the additional information introduced by Spectralization may already be captured by stronger message passing. On ZINC-12K, the improvements are more pronounced for simpler or local backbones such as MLPE and GINE, but become smaller for GINE+VN and GPS, which incorporate global information. This suggests that stronger message passing may already capture some of the structural distinctions introduced by Spectralization. This also motivates the exploration of more expressive RGIs. The similar phenomenon occurs in Spec kk-FWL, where spectralizing the initial kk-atomic types does not improve the distinguishing power of the underlying refinement.

Therefore, the practical benefit of Spectralization depends on both the selected RGIs and the downstream architecture. We acknowledge that systematically identifying suitable RGIs for different datasets and message-passing mechanisms remains an important open question for future research.

"Please report GIN-E results for U0, U, H, G and ZPVE on QM9, or explain the switch to R-GCN."

In the original MoSE configurations, these five QM9 targets use GINE as the local message-passing module within GPS. However, when incorporating SpecSE, we observed consistent and substantial performance degradation with GINE on these targets, whereas the other targets using R-GCN did not exhibit this issue. Switching these five targets to R-GCN consistently improved their performance in our experiments.

Although we have not yet identified the underlying cause, this empirical observation motivated our choice of R-GCN for these targets.

Revision: We further clarify the choice of local message-passing module within GPS in the main text, see lines 509--511.

Q4: BREC Graph Operator, Spectral Labels, and SpecPPGN:

Graph operator

The non-neural WL experiments use adjacency T=AT=A. Neural SpecPPGN uses normalized adjacency T=A~=I−L~T=\widetilde A=I-\widetilde L.

Computation of Order-3 Spectralized Atomic-Type Labels

We describe the computation of spectralized atomic-type labels separately for non-neural WL refinements and neural SpecPPGN implementations.

1. Non-neural WL refinements.

In our original implementation, we used randomized polynomial fingerprints to encode the Spectralization. Specifically, for each atomic type τ∈AT3\tau\in\mathrm{AT}_3, we first consider the moment responses

(A_G^{a_1}\otimes A_G^{a_2}\otimes A_G^{a_3})\Phi_{\tau,G},$$ where $\boldsymbol a\in\{0,\ldots,n-1\}^3$. The complete collection of these moments determines full Spectralization. To avoid storing all moments, we construct eight randomized fingerprint channels of the form $$h_{\ell,G}(\boldsymbol v)= \sum_{\tau,\boldsymbol a} \alpha_{\ell,\tau} \left(\prod_{j=1}^{3}r_{\ell,j}^{a_j}\right) M_{\tau,\boldsymbol a}^G(\boldsymbol v) \pmod{p_\ell},$$ where $p_\ell$ is a large prime number. **With sufficiently large primes, the probability of fingerprint collisions can be made arbitrarily small**. Furthermore, guided by our newly added **Proposition 5.3**, we update a simpler realization using a single exponential filter: $$g_{\boldsymbol t}(z_1,z_2,z_3)=\exp(t_1z_1+t_2z_2+t_3z_3).$$ Its response can be computed as $$\mathcal F_{G,g_{\boldsymbol t}}^{(3)}\Phi_{\tau,G}= \left( e^{t_1A_G}\otimes e^{t_2A_G}\otimes e^{t_3A_G} \right)\Phi_{\tau,G}.$$ This requires computing **only one spectral filtering** per atomic-type signal. Proposition 5.3 guarantees that a generic exponential filter preserves the full expressiveness of Spectralization. Our BREC experiments further support this result: $$\begin{array}{lccccc} \hline \text{Method} & \text{Basic (60)} & \text{Reg (140)} & \text{Ext (100)} & \text{CFI (100)} & \text{Overall} \\\\ \hline \text{Spec }2\text{-FWL (Exp)} & 60 & 137 & 100 & 70 & 367 \\\\ \text{Spec }2\text{-FWL (Full)} & 60 & 137 & 100 & 70 & 367 \\\\ \hline \end{array}$$ For background and further details on how finitely many filters can preserve the full expressiveness of Spectralization, please refer to our **General Response: Preserving Full Expressiveness with Finite Spectral Filters** above, as well as the newly added Proposition 5.3, Corollary 5.4, and Appendices E.2 and E.3 in the revised manuscript.
Reviewer_P1EEOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces Spectralization, a framework that treats a rooted graph invariant (RGI) as a graph signal on node tuples and augments it with the graph spectrum and responses to higher-order spectral filters. A key theoretical result identifies the eigenspace projection invariant as the spectralization of the identity RGI, thereby linking spectral-invariant GNNs with structural encodings such as distances and substructure counts.

Critical strengths
  1. Theorem 4.4 provides a clean bridge between two previously separate threads—spectral invariant GNNs and positional/structural encodings based on RGIs.

  2. Strong expressiveness result for the oracle algorithm (Theorem 4.7).

  3. Reasonable experimental coverage.

Critical weaknesses
  1. Definition 4.3 defines spectralization using all continuous filters. This is an infinite, non-finite-dimensional object. Without approximation guarantees or a careful analysis of how much expressiveness is lost under finite filtering, the main theoretical claims risk feeling disconnected from the deployed model.

  2. The experiments are on relatively small molecular graphs and CIFAR-derived graphs. The paper does not provide a clear complexity analysis, memory footprint, or scaling study. Scalability is underanalyzed.

  3. Experiment improvements are modest at best and not fully convincing.

  4. Novelty is weak comparing with existing spectral message-passing and kernel-filter methods.

Questions for authors
  1. What exact finite filters are used in SpecPPGN and SpecSE?

  2. How much expressiveness is retained by the finite filter bank?

5 comments

We thank the reviewer for the constructive feedback. Below, we respond to each weakness and question raised in the review.

W1: Expressiveness under Finite Spectral Filtering

We agree that clarifying the connection between full Spectralization and its finite implementations is important. As this concern was raised by multiple reviewers, we address it in our General Response: Preserving Full Expressiveness with Finite Spectral Filters posted above.

W2: Computational Complexity and Scalability

We agree and have added Appendix F.3, Computational Complexity and Scalability, to provide a detailed analysis. Below, we summarize the key findings in two parts:

  • The computational complexity of non-neural WL refinement algorithms;
  • The computational complexity and scalability of practical neural implementations.

Computational Complexity of WL Refinements

We summarize the per-round computational complexity and storage requirements of different WL refinements, where kk denotes the tuple order on which the refinement operates, and nn is the number of vertices in the graph.

\hline \text{Refinement} & \text{Time / round} & \text{Tuple-color space} & \text{Spectral-label space} \\\\ \hline k\text{-FWL} & O(kn^{k+1}) & O(n^k) & \text{--} \\\\ \text{Spec }k\text{-FWL} & O(kn^{k+1}) & O(n^k) & O(n^{k+1}) \\\\ \text{SI }(k+1)\text{-OWL} & O((k+1)n^{k+2}) & O(n^{k+1}) & O(n^2) \\\\ \hline \end{array}$$ We have also measured runtime and memory on BREC: $$\begin{array}{lccc} \hline \text{Method} & \text{Distinguished pairs} & \text{Total runtime} & \text{Peak host memory} \\\\ \hline 2\text{-FWL} & 270/400 & 10.72\\ \text{s} & 855\\ \text{MiB} \\\\ \text{Spec }2\text{-FWL} & 367/400 & 29.05\\ \text{s} & 1357\\ \text{MiB} \\\\ \text{SI }3\text{-OWL} & 378/400 & 1377.08\\ \text{s} & 6378\\ \text{MiB} \\\\ \hline \end{array}$$ ### **Computational Complexity and Scalability of Neural Implementations** We consider three practical implementations of SpecSE, with different computational costs depending on graph size and the type of structural encodings. Let $n$ denote the number of nodes. **(i) SpecSE via Spectral Decomposition: $O(n^3)$** This implementation explicitly computes the eigendecomposition and applies spectral filters, with $O(n^3)$ computational complexity for a fixed number of RGIs and filters. It is suitable for relatively small graphs, such as those in our molecular and image benchmarks, where spectral decomposition is computationally feasible. **(ii) SpecSE via Polynomial Filtering with 2-RGIs: $O(n^2)$** Polynomial filtering avoids eigendecomposition by computing spectral responses through polynomial recurrences, achieving $O(n^2)$ complexity for 2-RGIs. This quadratic dependence arises from computing structural encodings for all node pairs. **(iii) SpecSE via Polynomial Filtering with 1-RGIs: $O(n)$** For larger graphs requiring stronger scalability, Spectralization can instead be applied to 1-RGIs to construct node-level structural encodings. These encodings can be computed in $O(n)$ time and stored in $O(n)$ space. **Revision:** We added Appendix F.3, Computational Complexity and Scalability, which provides a detailed complexity analysis and additional experimental results.

W3: Experimental Improvements

We respond to this concern from two perspectives: (i) graph-isomorphism benchmarks and (ii) downstream prediction tasks.

Graph-Isomorphism Benchmarks

First, we emphasize that Spectralization brings significant improvements on graph-isomorphism benchmarks, which directly evaluate the expressive power studied in our theoretical analysis, with fewer confounding factors from downstream architectures and tasks. We believe those controlled expressiveness benchmarks provide clear empirical evidence of the benefits of Spectralization, directly supporting our theoretical contributions.

Downstream Prediction Tasks

We agree that the improvements on downstream prediction tasks are less pronounced than those on graph-isomorphism benchmarks. Two main factors help explain this phenomenon.

First, the choice of RGIs matters. On QM9, we follow the RGI selection of MoSE. As shown in Table 3, MoSE itself achieves relatively small improvements over RWSE on many targets, suggesting that the selected RGIs may provide limited additional structural information for these tasks. Nevertheless, SpecSE achieves further improvements over MoSE on most QM9 targets.

Second, the additional information introduced by Spectralization may already be captured by stronger message passing. On ZINC-12K, the improvements are more pronounced for simpler or local backbones such as MLPE and GINE, but become smaller for GINE+VN and GPS, which incorporate global information. This suggests that stronger message passing may already capture some of the structural distinctions introduced by Spectralization. This also motivates the exploration of more expressive RGIs.

A similar phenomenon occurs in Spec 22-FWL, where spectralizing the initial pairwise atomic types provides no additional distinguishing power because the underlying refinement already captures their spectral responses (see Table 6 in Appendix F.1).

Therefore, the practical benefit of Spectralization depends on both the selected RGIs and the downstream architecture. We acknowledge that systematically identifying suitable RGIs for different datasets and message-passing mechanisms remains an important open question for future research.

W4: Novelty

We would like to clarify the scope and contributions of our work. Our work does not aim to design another message-passing or spectral filtering method. Instead, its originality and contributions lie in three main aspects:

  • A unified framework for structural encodings. We connect and generalize spectral invariant encodings and rooted graph invariant (RGI) encodings through Spectralization.
  • A systematic expressiveness analysis. We establish strict expressiveness gains and a WL hierarchy for spectralized refinements, together with strict refinement results for broad classes of RGIs.
  • Practical implementations with theoretical guarantees. We prove that a single analytic filter can preserve the full expressiveness of Spectralization and extend this guarantee to neural-network-parameterized filters.

Q1: Exact Filters in SpecPPGN and SpecSE

SpecPPGN

In our original implementation, we used a Chebyshev filter bank constructed from tensor products of Chebyshev polynomials, of the form gi,j,ℓ(z1,z2,z3)=Ti(z1)Tj(z2)Tℓ(z3)g_{i,j,\ell}(z_1,z_2,z_3)=T_i(z_1)T_j(z_2)T_\ell(z_3), where TiT_i denotes the Chebyshev polynomial of degree ii. As the reviewer pointed out, the restricted choice of filters limits the expressiveness.

Guided by our new Proposition 5.3, we further introduce an exponential-filter implementation. Specifically, we apply g(2)(z1,z2)=exp⁡(t1(2)z1+t2(2)z2)g^{(2)}(z_1,z_2)=\exp(t_1^{(2)}z_1+t_2^{(2)}z_2) to all 22-atp\mathbf{atp} indicators and g(3)(z1,z2,z3)=exp⁡(t1(3)z1+t2(3)z2+t3(3)z3)g^{(3)}(z_1,z_2,z_3)=\exp(t_1^{(3)}z_1+t_2^{(3)}z_2+t_3^{(3)}z_3) to all 33-atp\mathbf{atp} indicators. The filter parameters are randomly sampled once, then fixed and shared across graphs. The performance results for both implementations are reported below, under SpecPPGN (Cheb) and SpecPPGN (Exp), respectively.

\hline \text{Model} & \text{Basic (60)} & \text{Reg (140)} & \text{Ext (100)} & \text{CFI (100)} & \text{Overall} \\\\ \hline \text{PPGN} & 60.0 & 50.0 & 100.0 & 20.3 & 230.3 \\\\ \text{SpecPPGN (Cheb)} & 60.0 & 93.7 & 100.0 & 38.0 & 291.7 \\\\ \text{SpecPPGN (Exp)} & 60.0 & 135.7 & 100.0 & 61.2 & 356.9 \\\\ \hline \end{array}$$ As shown, SpecPPGN (Exp) achieves a clear improvement over SpecPPGN (Cheb), distinguishing 356.9 versus 291.7 graph pairs on average. ### **SpecSE** For all datasets, we use the spectral decomposition-based implementation. For each RGI, four learnable spectral filters are parameterized by a neural network with $\mathtt{GELU}$ activations: $$\begin{aligned} f_\theta(\boldsymbol z) &=W_2\mathtt{GELU}\bigl(W_1\boldsymbol z+\boldsymbol b_1\bigr)+\boldsymbol b_2,\\\\ g_{b,\theta}(\boldsymbol z) &=[f_\theta(\boldsymbol z)]_b, \qquad \boldsymbol z\in\mathbb R^2,\quad b\in[4], \end{aligned}$$ where $f_\theta:\mathbb R^2\to\mathbb R^4$ takes an eigenvalue pair as input. Details of the filter constructions and updated experimental results are provided in Appendix F.1. ## **Q2: How Much Expressiveness Does the Finite Bank Retain** As explained in **W1**, a single generic analytic filter, including one parameterized by a neural network with $\mathtt{GELU}$ activations, can preserve the full expressive power of Spectralization. We thank the reviewer again for the feedback, which helped us sharpen both the theoretical scope and the empirical evidence.

Comments on the paper

3 comments
AuthorsOpenReview ↗

General Response: Preserving Full Expressiveness with Finite Spectral Filters

We would like to address an important concern raised by both reviewers P1EE and RRSa: whether the expressiveness of Spectralization can be preserved using only a finite number of spectral filters.

The answer is Yes. We establish this through two newly added theoretical results:

  • Single-filter completeness. A single appropriately chosen spectral filter can preserve the full expressive power of Spectralization (Proposition 5.3 and Appendix E.2).
  • Neural realization. The same completeness guarantee holds for filters parameterized by neural networks with GELU\mathtt{GELU} activations (Corollary 5.4, Appendix E.3).

For instance, with the exponential filter family gt(z1,…,zk)=exp⁡(∑j=1ktjzj),g_{\boldsymbol t}(z_1,\ldots,z_k)=\exp\left(\sum_{j=1}^{k}t_jz_j\right), we prove that, for any fixed family Ck\mathcal C_k of real-valued kk-RGIs and Lebesgue-almost every t∈Rk\boldsymbol t\in\mathbb R^k, Spectralization restricted to the single filter gtg_{\boldsymbol t} is equivalent to full Spectralization as RGIs:

\equiv \operatorname{Spec}_{\mathcal{C}_k}^{T}.$$ Since equivalent RGIs induce the same distinguishing power when used in refinement algorithms, a single generic exponential filter preserves the full expressiveness of Spectralization in such refinements. Furthermore, we extend this completeness result to **analytic filter families** (see Appendix E.2). We further corroborate the single-filter completeness result empirically on BREC by comparing Spec $2$-FWL using a single exponential filter with its full-Spectralization counterpart: $$\begin{array}{lccccc} \hline \text{Method} & \text{Basic (60)} & \text{Reg (140)} & \text{Ext (100)} & \text{CFI (100)} & \text{Overall} \\\\ \hline \text{Spec 2-FWL (Exp)} & 60 & 137 & 100 & 70 & 367 \\\\ \text{Spec 2-FWL (Full)} & 60 & 137 & 100 & 70 & 367 \\\\ \hline \end{array}$$ As shown, the exponential-filter implementation exactly matches full Spectralization on BREC. This agreement is consistent with our theoretical findings. Further details are provided in Appendix F.1 (*Analytic-filter realization*, lines 3429-3451; Table 6, lines 3403-3414). In our experiments on molecular and image datasets, spectral filters are parameterized by neural networks with $\mathtt{GELU}$ activations, precisely the setting covered by Corollary 5.4. Therefore, our theoretical results directly support the filter parameterization used in our practical models. **Revisions:** 1. We added Proposition 5.3, Corollary 5.4, Appendix E.2 and Appendix E.3 to establish expressiveness guarantees for single spectral filters and their neural-network parameterizations. 2. We added experimental evidence corroborating the single-filter completeness in Appendix F.1.

Dear Reviewers,

The authors have submitted their responses to the questions and concerns raised in the reviews. Please review their responses and provide any further comments or clarifications, if applicable.

Thank you for your time and consideration.

AuthorsOpenReview ↗

Summary of Reviews and Rebuttal

We thank all three reviewers for their constructive comments and the AC for encouraging further feedback. We would like to briefly summarize the positive assessments from the reviews and the main concerns addressed during our rebuttal.

Positive feedback highlighted by the reviewers:

  1. A good research question (RRSa) and a clear problem formulation (JTYg).
  2. Clear theoretical contributions (all three reviewers), with conceptual insight and mathematical rigor highlighted by RRSa, and originality by JTYg.
  3. Theoretical expressiveness results closely supported by experiments (JTYg), demonstrating strong expressiveness gains (P1EE, JTYg).
  4. Reasonable experimental coverage (P1EE).

In our rebuttal, we have mainly addressed the following concerns:

  1. Finite Spectralization and neural realization: We clarified under what conditions finite filter banks retain the expressive power of the full framework, and how these results support the practical design of SpecSE in the previous General Response (P1EE, RRSa).
  2. Implementation details: We provided a more detailed explanation of the construction and implementation of SpecSE (P1EE, JTYg).
  3. Complexity analysis: We added a theoretical complexity analysis and empirical evaluations to clarify the computational costs (all three reviewers).
  4. Additional expressiveness experiments: We conducted further experiments to provide empirical support for the theoretical expressiveness hierarchy (all three reviewers) and shed further light on the sources of the expressiveness gains achieved by Spec k-FWL (JTYg).
  5. Ablation studies: We added ablation studies to examine the contributions of key components (JTYg, RRSa).

We believe these clarifications and additional results directly address the main concerns raised during the review and further strengthen the theoretical and empirical support for our work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.