- 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
- 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.
- 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
- 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.
- 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 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
- 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?
- 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?
- 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.
- 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?
- Table 3 shows smaller gains over MoSE on ZINC. Could global aggregation already capture some of the structural information introduced by spectralization?
- 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
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 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, and , 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 , 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 -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.
We thank the reviewer for the constructive feedback and address the concerns below.
W1 & Q3: Connection Between Theory and Practical SpecSE
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.
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
We extend our BREC experiments to include 3-LWL, SI 3-OWL, 3-FWL, and Spec 3-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.