- Rating
- 2
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
this paper proposes SpecGSN, a fully spectral graph scattering network for node representation learning. The method focuses on two limitations of existing graph scattering networks: using shared spectral filters across different graph components and the difficulty of applying nonlinear operations directly in the spectral domain. To address these issues, the authors introduce Transformer-based component-adaptive filter banks and a spectral nonlinear activation based on subspace folding. The paper also provides theoretical analysis of the filter expressiveness, basis-rotation invariance, and permutation equivariance. Experiments on homophilic and heterophilic datasets show competitive classification results, along with ablation and runtime comparisons.
Critical strengths
-
The paper addresses two meaningful problems in graph scattering networks. I find the motivation for component-adaptive filtering reasonable, especially when a graph contains several disconnected components with different spectral structures. The discussion of why nonlinear operations are difficult to define directly in the spectral domain is also interesting. These are relevant problems, and the paper gives a clear reason for studying them.
-
The spectral nonlinear activation is an interesting part of the method. The authors try to perform nonlinear operations directly in the spectral domain while keeping the output independent of the chosen eigenspace basis. I think this is more than just replacing one activation function with another. The subspace folding design has a clear mathematical motivation and could be useful beyond the specific scattering architecture considered here.
-
The experimental evaluation covers several useful aspects. The authors compare SpecGSN with spatial GNNs, spectral GNNs, and existing scattering methods on both homophilic and heterophilic datasets. The results are generally competitive, with particularly good performance on some heterophilic benchmarks. I also appreciate the comparisons between component-adaptive and unified filtering, as well as the runtime analysis of different nonlinear operations. These experiments help explain where the method works well and where its benefits may come from.
Critical weaknesses
-
The discussion of closely related work is incomplete. The paper cites Specformer (Bo et al., 2023), which is relevant to the Transformer-based filter design, but several important studies on spectral invariance and nonlinear spectral filtering are missing. In particular, Sign and Basis Invariant Networks for Spectral Graph Representation Learning (Lim et al., ICLR 2023, https://mlanthology.org/iclr/2023/lim2023iclr-sign/) studies sign and basis invariance in spectral graph representations. Laplacian Canonization: A Minimalist Approach to Sign and Basis Invariant Spectral Embedding (Ma et al., NeurIPS 2023, https://proceedings.neurips.cc/paper_files/paper/2023/hash/257b3a7438b1f3709e91a86adf2fdc0a-Abstract-Conference.html) also addresses the ambiguity of Laplacian eigenvectors through canonical directions. More importantly, Equivariant Machine Learning on Graphs with Nonlinear Spectral Filters (Lin et al., NeurIPS 2024, https://proceedings.neurips.cc/paper_files/paper/2024/hash/e742e93b9f709f522986f53eeebaeef7-Abstract-Conference.html) already studies nonlinear spectral filters and their equivariance properties. I am not suggesting that these methods are equivalent to SpecGSN, but their connection to the proposed spectral activation should be discussed more carefully. In particular, I would like to understand what subspace folding offers beyond these existing approaches.
-
The practical benefit of component-adaptive filtering is not fully convincing yet. According to Table 5, the original heterophilic datasets used in the experiments each contain only one connected component. In these cases, the proposed mechanism cannot really demonstrate the benefit of assigning different filters to different graph components. The Merged dataset is useful for testing this idea, but it is constructed by combining three existing datasets. Also, Table 3 shows relatively small improvements over the version without component masking on most datasets. I think the authors should explain more clearly how much of the overall improvement actually comes from component-adaptive filtering, rather than from the other parts of SpecGSN.
-
The efficiency claims need a more complete evaluation. The runtime results in Table 4 are encouraging, and the spectral nonlinear activation does appear faster during repeated scattering computations on some datasets. However, the reported comparisons do not fully reflect the cost of spectral decomposition and preprocessing. For example, constructing the direction matrices on Pubmed requires considerable additional time. This matters because the paper emphasizes computational efficiency as one of its advantages. I would like to see a clearer discussion of the total computational cost, including preprocessing, and under what conditions the proposed method becomes more efficient than conventional alternatives.
-
Some details of the subspace construction and theoretical guarantees need clarification. The proposed activation relies on grouping eigenvalues and selecting directions within each eigenspace. However, these operations involve numerical tolerances and rank-dependent decisions, so it is not entirely clear how stable the results are when eigenvalues are very close or when the eigenspace basis changes. I also noticed a possible issue in Algorithm 1. Since K is initialized to 1 and the condition "if K = 1" is checked for every candidate, the initialization branch appears to remain active throughout the loop. As written, this seems to overwrite the existing cluster rather than build multiple clusters. Could the authors clarify whether this is a pseudocode error and whether the implementation follows the intended procedure? Since the direction selection process is important for the proposed spectral activation, I think this deserves attention.
-
The explanation of the main framework could be improved. Figure 1 includes many intermediate matrices, arrows, and small labels, making it somewhat difficult to follow the complete process at first glance. The connection between component-wise spectral decomposition, filter generation, and subspace folding could be made clearer. I think a simpler high-level illustration, with the more detailed operations explained in the text, would help readers understand the method more easily.
Questions for authors
Please see Weaknesses 1–4 above. I would particularly appreciate clarification on how the proposed spectral activation differs from existing invariant and nonlinear spectral methods, the actual contribution of component-adaptive filtering, the end-to-end computational cost, and the possible issue in Algorithm 1.
5 comments
Responses to Reviewer y534 - part 2
W1 - Difference from previous works (continue)
- Subspace folding vs. nonlinear spectral filters [3]
Lin et al. [3] investigate nonlinear spectral filtering and its equivariance properties by projecting the graph signal onto eigenspaces or predefined frequency bands and transforming spectral coefficients based on the energy of the projected signal. However, their nonlinear filters cannot directly transform the spectral coefficients within each eigenspace. For a single-channel graph signal , the output of Index-NLSF given a specific subspace is in the form of , which is a rescaled form of .
In contrast, SpecGSN performs subspace folding in the form of
with direction matrix to allow for transforming spectral coefficients within a subspace. Furthermore, the frequency response of SpecGSN is not explicitly based on the signal energy of each subspace. Instead, the frequency response is based on the interaction of eigenvalue embeddings of each graph component. Finally, SpecGSN employs a tree-structured graph scattering transform, rather than the energy-based analysis-synthesis framework adopted in [3].
[1]. Lim, D., Robinson, J. A., Zhao, L., Smidt, T., Sra, S., Maron, H., & Jegelka, S. (2022). Sign and basis invariant networks for spectral graph representation learning [Preprint]. arXiv.
[2]. Ma, G., Wang, Y., & Wang, Y. (2023). Laplacian canonization: A minimalist approach to sign and basis invariant spectral embedding. In neural information processing systems (pp. 11296–11337).
[3]. Lin, Y.-W. E., Talmon, R., & Levie, R. (2024). Equivariant machine learning on graphs with nonlinear spectral filters. In neural information processing systems.
Responses to Reviewer y534 - part 3
W2 - Multi-graph datasets and ablation study
We thank the reviewer for this valuable comment. To provide stronger evidence for justifying component-adaptive filtering in the ablation study, we conduct additional controlled ablation experiments on four multi-graph datasets: Elliptic-S5 (the five smallest connected components of Elliptic), PATTERN-100 and CLUSTER-100 (the first 100 graphs from PATTERN and CLUSTER respectively), and PascalVOC-50 (the first 50 graphs from PascalVOC-SP). We compare SpecGSN with and without graph-component attention masks, while keeping other settings the same. The results are shown below.
All the experiments follow the same settings as described in the paper. We have updated Section 5.2 with the results of the supplementary ablation experiments in the revised manuscript, and presented the information of datasets and experimental settings in Appendices 6 and 7.
| Method | Elliptic-S5 | Pattern-100 | Cluster-100 | PascalVOC-50 |
|---|---|---|---|---|
| SpecGSN | ||||
| SpecGSN+no mask |
All the selected datasets exhibit a positive gain with graph-component attention masks. Among the selected datasets, the improvement is most pronounced on PascalVOC-50, a real-world graph dataset. These results, together with Table 3 in the original paper, support the practical effectiveness of component-adaptive filtering.
Actually, the gain becomes nonsubtle when different graph components exhibit distinct structural and spectral characteristics. As illustrated by the MERGED dataset, when the preference of frequency responses of graph components (TEXAS, WISCONSIN and CORNELL) differs, the component-specific filtering can provide nonnegligible improvements.
Responses to Reviewer y534 - part 1
W1 - Difference from previous works
We thank the reviewer for highlighting these closely related works. We have added Section 4.5 to the revised manuscript to discuss the relationship between our work and these previous studies. SpecGSN differ substantially in the design choices and contribution from the approaches [1, 2] that focus on permutation equivariant and basis-rotation invariant representation learning of graphs and [3] that develops nonlinear spectral filters with equivariance properties, as elaborated below.
Despite that SpecGSN and SignNet/BasisNet [1] share the motivation on representation learning invariant to the choice of sign and basis for eigenvectors and subspaces, SpecGSN achieves these properties through a fundamentally different mechanism based on subspace folding from SignNet/BasisNet [1].
For 1D eigenspaces, SignNet explicitly ensures sign invariance through the form of ϕ(ur)+ϕ(−ur), where ur is the eigenvector of the rth subspace. In contrast, SpecGSN first determines a direction Dr=sign(1⊤ur) such that Dr⊤ur⊤x remains unchanged under ur↦−ur. Only when the direction cannot be identified (∣1⊤ur∣<tol), do we adopt Dr=21[1,−1] and the spectral nonlinear activation reduces to the form of SignNet.
For multi-dimensional eigenspaces, BasisNet constructs invariant representations from the eigenspace projection matrix UrUr⊤, where Ur is the eigenvector matrix of the rth subspace of dimension kr. Instead of constructing the full projection matrix, SpecGSN builds a direction matrix Dr∈Rkr×mr with row selection on Ur. Here, mr is the number of selected directions. Given any orthonormal basis transform with matrix Qr∈Rkr×kr, Ur↦UrQr leads to Dr↦Qr⊤Dr, ensuring UrDr=UrQrQr⊤Dr=U~rD~r. Moreover, direction selection based on the ℓ2-norm preserves permutation equivariance.
Laplacian Canonization [2] solves eigenbasis ambiguities by explicitly identifying canonical directions for individual eigenvectors through the Maximal Axis Projection (MAP) algorithm. In contrast, SpecGSN does not attempt to canonicalize the eigenbasis itself, but constructs another direction matrix Dr∈Rkr×mr based on the rows of Ur∈RN×kr. The columns of Dr serve as the "reference directions" to perform "subspace folding", and the resulting operator UrDr is independent of the arbitrary basis choice. For any orthonormal matrix Qr∈Rkr×kr, UrDr=UrQrQrTDr=U~rD~r.
More importantly, SpecGSN remains applicable to certain eigenspaces where Laplacian Canonization cannot establish a canonical basis. Consider the two-dimensional eigenspace of the four-node cycle (C4), with U2=21[[1,0,−1,0]⊤,[0,1,0,−1]⊤], Laplacian Canonization fails to define canonical directions due to the violation of its Assumption 2, and the summary vector is orthogonal to the entire eigenspace. In contrast, SpecGSN can handle this situation. All 4 rows of U2 are selected so that D2=U2T, which reduces to the form of BasisNet [1].