acceptodds
Under review as a conference paper at ICLR 2027

Fully Spectral Graph Scattering Networks With Transformer-Based Component-Adaptive Graph Filter Banks and Spectral Nonlinearity

Abstract

Graph scattering networks (GSNs) learn multi-scale node representation via graph filter banks along multiple scattering paths of different lengths. However, existing GSNs are still challenged by two problems: i) spectral filtering via single graph filter or filter bank with uniform frequency response to different graph components, and ii) lack of spectral nonlinearity to ensure the invariance to node permutation. To tackle the issues, we propose a novel fully spectral graph scattering network name SpecGSN to allow invariant node representation learning with learnable spectral filtering and nonlinearity. Specifically, for spectral filtering, we design Transformer-based graph filter banks on the orthonormal subspaces induced by graph shift operators to achieve diverse frequency response to different graphs components. Moreover, we develop spectral nonlinear activation via subspace folding to guarantee the commutativity between the nonlinear operator and transform with subspace basis for invariant learnable filtering in the spectral domain. We theoretically demonstrate that SpecGSN is invariant to node permutations and subspace basis rotations. Experimental results show that SpecGSN achieves competitive or state-of-the-art node classification performance on both homophilic and heterophilic graphs with enhanced computation efficiency.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Graph scattering networks, graph scattering transform, multi-scale representation learning

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_y534OpenReview ↗
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
  1. 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.

  2. 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.

  3. 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
  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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
AuthorsOpenReview ↗

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.

  1. Spectral nonlinear activation via subspace folding vs. sign and basis invariant representation [1]

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)\phi(u_r)+\phi(-u_r), where uru_r is the eigenvector of the rthr^{th} subspace. In contrast, SpecGSN first determines a direction Dr=sign(1⊤ur)D_r=sign(\mathbf{1}^\top u_r) such that Dr⊤ur⊤xD_r^\top u_r^\top x remains unchanged under ur↦−uru_r\mapsto-u_r. Only when the direction cannot be identified (∣1⊤ur∣<tol|\mathbf{1}^\top u_r|<tol), do we adopt Dr=12[1,−1]D_r=\frac{1}{\sqrt{2}}[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⊤U_rU_r^\top, where UrU_r is the eigenvector matrix of the rthr^{th} subspace of dimension krk_r. Instead of constructing the full projection matrix, SpecGSN builds a direction matrix Dr∈Rkr×mrD_r\in\mathbb{R}^{k_r\times m_r} with row selection on UrU_r. Here, mrm_r is the number of selected directions. Given any orthonormal basis transform with matrix Qr∈Rkr×krQ_r\in\mathbb{R}^{k_r\times k_r}, Ur↦UrQrU_r\mapsto U_rQ_r leads to Dr↦Qr⊤DrD_r\mapsto Q_r^\top D_r, ensuring UrDr=UrQrQr⊤Dr=U~rD~rU_rD_r=U_rQ_rQ_r^\top D_r=\tilde{U}_r\tilde{D}_r. Moreover, direction selection based on the ℓ2\ell_2-norm preserves permutation equivariance.

  1. Subspace folding vs. Laplacian Canonization [2]

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×mrD_r\in\mathbb{R}^{k_r\times m_r} based on the rows of Ur∈RN×krU_r\in\mathbb{R}^{N\times k_r}. The columns of DrD_r serve as the "reference directions" to perform "subspace folding", and the resulting operator UrDrU_rD_r is independent of the arbitrary basis choice. For any orthonormal matrix Qr∈Rkr×krQ_r\in\mathbb{R}^{k_r\times k_r}, UrDr=UrQrQrTDr=U~rD~rU_rD_r=U_rQ_rQ_r^TD_r=\tilde{U}_r\tilde{D}_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 (C4C_4), with U2=12[[1,0,−1,0]⊤,[0,1,0,−1]⊤]U_2=\frac{1}{\sqrt{2}}[[1,0,-1,0]^\top,[0,1,0,-1]^\top], 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 U2U_2 are selected so that D2=U2TD_2=U_2^T, which reduces to the form of BasisNet [1].

AuthorsOpenReview ↗

Responses to Reviewer y534 - part 2

W1 - Difference from previous works (continue)

  1. 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 xx, the output of Index-NLSF given a specific subspace is in the form of X^r(out)=σ(∥X^r∥)X^r\hat{X}_r^{(out)}=\sigma(\|\hat{X}_r\|)\hat{X}_r, which is a rescaled form of X^r\hat{X}_r.

In contrast, SpecGSN performs subspace folding in the form of σspec(r)(X^r)=X^r+Dr(σ(DrTX^r)−DrTX^r)\sigma_{spec}^{(r)}(\hat{X}_r)=\hat{X}_r+D_r(\sigma(D_r^T\hat{X}_r)-D_r^T\hat{X}_r)

with direction matrix DrD_r 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.

AuthorsOpenReview ↗

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.

MethodElliptic-S5Pattern-100Cluster-100PascalVOC-50
SpecGSN97.73±0.1997.73\pm0.1992.18±0.0992.18\pm0.0970.39±0.4070.39\pm0.4092.59±0.3192.59\pm0.31
SpecGSN+no mask97.69±0.1697.69\pm0.1692.12±0.1092.12\pm0.1070.30±0.9770.30\pm 0.9788.23±0.5688.23\pm0.56

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.

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

This paper proposes SpecGSN, a fully spectral graph scattering network. The method performs spectral decomposition separately for each connected component, generates multiscale filters using a Transformer conditioned on the component’s spectral context, and constructs a spectral nonlinearity using direction matrices to make the node-domain output independent of the eigenbasis choice. Filtering and activation are performed along scattering paths in the spectral domain before conversion to node representations for classification. The experiments demonstrate competitive node classification performance and reduced scattering computation time on some datasets.

Critical strengths
  1. The motivation for developing a spectral nonlinearity is technically meaningful.

  2. The construction of the orientation matrix is an important contribution—it is both simple and reasonable.

  3. The experimental setup aligns well with the paper’s main argument, and the computational cost of constructing the direction matrix is also analyzed.

Critical weaknesses
  1. If the initial coefficient of a sub-eigenspace is 0, it will remain zero during subsequent filtering; furthermore, due to the frequency-grouping design, no other subspaces will generate that frequency component. This effectively undermines the inherent advantages of the scattering network.

  2. The differences between this paper and existing work should be further emphasized. In terms of motivation, the idea of using a group of adaptive filters for node learning, as outlined in the introduction of this paper, is identical to that of NFGNN[1]. In terms of methodology, the approach of encoding based on eigenvalues and subsequently applying attention modeling is identical to that of Specformer[2].

[1] Node-oriented spectral filtering for graph neural networks. IEEE TPAMI 2024.

[2] Specformer: Spectral graph neural networks meet transformers. ICLR 2023.

  1. When the input graph has only one connected component, the component mask has no effect, and the mechanism reduces to spectral-context filtering over the entire graph while still requiring its full eigendecomposition. However, spectral decomposition is computationally expensive, which limits the practicality of the method described in this paper.
Questions for authors
  1. Since an eigenspace with initially zero coefficients remains zero under the proposed filtering and activation, how does the method retain the frequency-generation capability of conventional scattering networks? What implications does this restriction have for its expressive power?

  2. What distinguishes the motivation and adaptive filtering design from NFGNN [1]? Beyond component-wise attention masking, what are the substantive methodological differences between the proposed filter generator and Specformer [2]?

  3. For a graph with only one connected component, what additional benefit does the proposed design provide over existing spectral filtering methods? Does the reported runtime include full eigendecomposition, and under what conditions can the computational savings offset this preprocessing cost?

3 comments
AuthorsOpenReview ↗

Responses to Reviewer kabq - part 1

W1 & Q1 - The frequency missing issue and limitation in expression

To further address the frequency missing issue, we introduce an optional learnable bias in the proposed spectral nonlinear activation based on subspace folding to recover the missing frequency component before graph scattering transform. σspec(r)(X^r)=X^r+Dr(σ(DrTX^r)+1mrb−DrTX^r),\sigma_{spec}^{(r)}(\hat{X}_r)=\hat{X}_r+D_r(\sigma(D_r^T\hat{X}_r)+\mathbf{1}_{m_r}b-D_r^T\hat{X}_r),

where b∈R1×Cb\in\mathbb{R}^{1\times C} is the learnable parameter shared across different activation directions within a subspace and across different subspaces. The bias can be configured individually for 1-dimensional and multi-dimensional subspaces with only a limited number of additional learnable parameters. This formulation alleviates the frequency missing issue while preserving the permutation equivariance and basis-rotation invariance of the proposed spectral nonlinear activation. Our supplementary experiments demonstrate that this modification can further improve the classification performance for SpecGSN from 85.92%±2.00% to 86.09%±0.86% on Texas and the performance for SpecGSN+Relu from 83.48%±1.33% to 83.91%±0.72% on WISCONSIN. We have updated Section 4.2 and Appendices 2 and 3 with technical modification and proofs in the revised manuscript.

Actually, we find that when the graph is grid-like or exhibits high structural symmetry, the conventional node-domain activation (SpecGSN$^\dagger$) usually outperforms spectral nonlinear activation (SpecGSN). In supplementary experiments, SpecGSN$^\dagger$ achieves 88.33%±0.19%88.33\%\pm0.19\% on MINESWEEPER while SpecGSN only achieves 86.51%±0.07%86.51\%\pm0.07\%. The similar phenomenon also occurs on Roman-Empire. In contrast, when the graph structure is of low symmetry with fewer multi-dimensional subspaces, SpecGSN usually outperforms SpecGSN$^\dagger$ due to the controllable energy transfer within subspaces. Here, we summarize the characteristics and results of some datasets to provide a clear comparison.

#MD: number of multi-dimensional subspaces. The comprehensive discussion has been included in Appendix 5 in the revised manuscript.)

Datasets#node#MD#node/#MDSpecGSNSpecGSN$^{\dagger}$Class
Chameleon-Filtered8901180.9144.52±0.5344.52\pm0.5341.68±1.2741.68\pm1.27Heterophilic
Amazon-Ratings24492128519.0652.22±0.6052.22\pm0.6051.12±0.2651.12\pm0.26Heterophilic
TOLOKERS11758100811.6681.83±0.1581.83\pm0.1581.86±0.1081.86\pm0.10Heterophilic
Roman-Empire2266223279.7480.51±0.1980.51\pm0.1982.31±0.2882.31\pm0.28Heterophilic
MINESWEEPER1000035242.8486.51±0.0786.51\pm0.0788.33±0.1988.33\pm0.19Heterophilic
PUBMED1971722896.2390.16±0.1090.16\pm0.1090.04±0.0990.04\pm0.09Homophilic
DBLP17716149118.9086.06±0.0986.06\pm0.0985.97±0.1085.97\pm0.10Homophilic
Amazon-Photo765012262.7095.63±0.1495.63\pm0.1495.81±0.0695.81\pm0.06Homophilic
Amazon-Computers1375263321.7392.61±0.1092.61\pm0.1092.78±0.0892.78\pm0.08Homophilic
AuthorsOpenReview ↗

Responses to Reviewer kabq - part 2

W2 & Q2 - Difference from previous works

We thank the reviewer for highlighting these relevant works. We have added Section 4.5 in the revised manuscript to discuss the relationship between our work and these previous studies. In summary, the motivation of this work is fundamentally different from NFGNN, while the eigenvalue encoding and subsequent filter generation are not identical to Specformer. The distinctions are elaborated below.

  1. Motivation of SpecGSN vs. NFGNN [1]

We have to emphasize that it is a broad paradigm in methodology rather than a research motivation to use adaptive filters or a filter bank. To this end, we respectfully disagree that the motivation of SpecGSN is identical to that of NFGNN, though adaptive filter learning for node-wise representation learning is employed in both works. In fact, NFGNN addresses the adaptation of local neighborhood aggregation, while SpecGSN addresses graph-dependent multiscale representation learning with controlable energy transfer and time efficiency. They are completetly distinct in motivations.

NFGNN is motivated by improving the effectiveness of GNNs for the nodes with various local structural patterns. The authors notice that there might be several types of important local patterns in the graphs, where different nodes may require different neighborhood aggregation strategies. Therefore, NFGNN learns node-wise polynomial filters to adapt varying local graph patterns.

In contrast, SpecGSN is motivated by two distinct limitations of existing graph scattering networks (GSNs). First, previous GSNs employ a predefined or graph-independent graph filter bank. This could not be optimal for multiscale representation learning given different graph components with distinct spectral distributions and preference of frequency response. Therefore, the learned graph filter bank of SpecGSN is graph component-adaptive instead of node adaptive as presented in NFGNN. Second, we notice that the conventional modulus operation adopted in conventional GSNs usually introduces dense energy transfer between subspaces that potentially causes overfitting. Existing methods require GFT and IGFT in GSNs to achieve the nonlinearities in the vertex domain. Therefore, the spectral nonlinear activation is developed as a solution in the spectral domain.

  1. Multi-scale, component-aware filter generation vs. Specformer [2]

We acknowledge that Specformer first introduces eigenvalue encoding with a Transformer for adaptive filter learning. However, the filter generation approach of SpecGSN differs from Specformer in three aspects: 1) SpecGSN employs a scale-specific multi-scale eigenvalue encoder. In SpecGSN, each filter within the filter bank is assigned an individual scaled eigenvalue embedding for frequency response generation, while Specformer simply encode the original eigenvalues. 2) SpecGSN introduces graph-component attention masks for graph component-adaptive filter learning. The interactions of eigenvalue embeddings are restricted within each graph component to enable spectral modeling for each graph component rather than performing unrestricted attention over the entire spectrum as Specformer. 3) SpecGSN directly generates frequency responses of individual filters from their corresponding spectral embeddings. In contrast, Specformer decodes filters with a unified spectral embedding, and could suffer from filter coupling and limit the specialization of individual filter.

[1]. Zheng, S., Zhu, Z., Liu, Z., Li, Y., & Zhao, Y. (2023). Node-oriented spectral filtering for graph neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(1), 388–402.

[2]. Bo, D., Shi, C., Wang, L., & Liao, R. (2023). Specformer: Spectral graph neural networks meet transformers [Preprint]. arXiv.

AuthorsOpenReview ↗

Responses to Reviewer kabq - part 3

Q3 - Benefits on single-component graphs and computational efficiency

We thank the reviewer for these important questions.

  1. Benefits on single-component graphs

We acknowlege that the graph component mask does not provide additional benefits, when the dataset only contains 1 graph component. However, the benefits of SpecGSN are not restricted to component-adaptive filtering. Compared with Specformer, SpecGSN introduces scale-specific eigenvalue encoding, allowing each filter to learn its frequency response from a unique eigenvalue embedding. Second, SpecGSN introduces a subspace-wise spectral nonlinear activation into graph scattering, which preserves spectral localization and is more time efficient. As discussed in W1 & Q1, graph scattering with subspace-wise spectral nonlinear activation usually outperforms graph scattering with conventional node-domain activation for graphs with fewer multi-dimensional subspaces. Therefore, SpecGSN retains distinct advantages in both filter-bank generation and nonlinearity for datasets with only one graph component.

  1. Run time evaluation and preprocessing costs

We clarify that the preprocessing time does not contain full eigen-decomposition of the graph shift operator, since the experiment is designed to compare graph scattering transform with the proposed spectral nonlinear activation (SpecGSN) against conventional node-domain activation (SpecGSN$^\dagger$). Since both SpecGSN and SpecGSN$^\dagger$ require the same full eigen-decomposition, the shared cost of preprocessing is excluded in this experiment.

SpecGSN requires additional computation of the direction matrix DrD_r for each subspace, but this preprocessing is performed only once given a dataset. Consequently, when the graph is fixed and sufficiently many training iterations or repeated experiments are performed, the accumulated computational savings can offset the preprocessing costs.

Detailed discussions about time consumption of preprocessing and graph scattering have been added to Section 5.3 in the revised manuscript.

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

This paper proposes SpecGSN, a fully spectral graph scattering network combining Transformer-based component-adaptive filter banks with spectral nonlinear activation via subspace folding, aiming to improve spectral filtering flexibility.

Critical strengths

(1) The paper addresses meaningful challenges in adaptive spectral filtering.

(2) The proposed spectral nonlinearity provides an approach to handling eigenspace basis ambiguity.

Critical weaknesses

(1) Insufficient differentiation from existing spectral graph learning methods. The paper does not sufficiently position its contributions relative to recent advances in adaptive spectral filtering [1, 2], spectral wavelet learning [3], and basis-invariant spectral representations [4]. In particular, [1, 2] already investigate adaptive filtering under heterogeneous graph structures, while [4] addresses closely related eigenbasis ambiguities. Although these works differ from SpecGSN in their specific formulations, the paper does not adequately clarify its methodological distinctions.

(2) Insufficient empirical support for the core motivation. According to Table 5, all six original heterophilic benchmarks contain only a single connected component, limiting their ability to validate component-adaptive filtering. Moreover, Table 3 shows only marginal improvements over unified filtering on most datasets. Stronger evidence is needed to establish the practical necessity and effectiveness of the proposed component-specific filtering mechanism.

(3) Incomplete evaluation on contemporary benchmarks. The evaluation relies heavily on conventional datasets. Although Roman-empire is included, several established heterophily benchmarks, such as Amazon-ratings, Minesweeper, Tolokers, and Questions [5, 6], are missing. Moreover, the reported Chameleon configuration appears to use the original dataset, which has documented duplicate-node and data leakage concerns [5]. Recent studies [6, 7] also demonstrate the importance of evaluation on more diverse and large-scale graphs, including Pokec, Penn94, and Twitch-Gamer. Additional evaluations using contemporary benchmark protocols and representative larger graphs are needed.

[1] HeroFilter: Adaptive Spectral Graph Filter for Varying Heterophilic Relations

[2] Graph Neural Networks with Diverse Spectral Filtering

[3] A General Graph Spectral Wavelet Convolution via Chebyshev Order Decomposition

[4] Sign and Basis Invariant Networks for Spectral Graph Representation Learning

[5] A Critical Look at the Evaluation of GNNs under Heterophily: Are We Really Making Progress?

[6] Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification

[7] Understanding and Enhancing Message Passing on Heterophilic Graphs via Compatibility Matrix

Questions for authors

see weaknesses

4 comments
AuthorsOpenReview ↗

Responses to Reviewer p9Gc - part 1

W1 – Differentiation from existing spectral graph learning methods

We thank the reviewer for highlighting these relevant works. We have added Section 4.5 in the revised manuscript to discuss the relationship between our work and these previous studies. We have clarified that SpecGSN differs substantially in the design choices and contribution from the methods [1-3] that focus on the learning of adaptive spectral graph filters or graph wavelets and [4] that discusses the basis-invariant representation learning of spectral GNNs. The distinctions are summarized below:

  1. Component-adaptive graph filter bank vs. adaptive spectral filter [1, 2].

HeroFilter [1] directly parameterizes the frequency response in adaptive filter learning, and uses the learned filter to estimate node correlations and construct node-wise patches. However, the filter responses are not explicitly conditioned on the overall eigenvalue distribution of each graph. The spectral filter of HeroFilter can be interpreted in the form of f(λi)=gθ(λi)f(\lambda_i)=g_\theta(\lambda_i), where λi\lambda_i is the ithi^{th} eigenvalue of the graph shift operator and θ\theta is the learnable parameter.

DSF [2] learns node-wise coefficients through iterative position encoding (IPE) for rescaling the node-wise outputs of polynomial filters to capture local structure heterogeneity. The filter of DSF is generally non-diagonal in graph Fourier basis due to node-wise rescaling, and cannot be interpreted from the spectral view.

In contrast, SpecGSN introduces a fundamentally different method for filter generation. We adopt multi-resolution eigenvalue encoding with a Transformer and graph component mask to directly generate frequency response for each eigenvalue of each graph component. In SpecGSN, we design a different spectral filter in the form of f(λi(j))=gθ(λi(j),Λ(j))f(\lambda_i^{(j)})=g_\theta (\lambda_i^{(j)},\Lambda^{(j)}), where λi(j)\lambda_i^{(j)} is the ithi^{th} eigenvalue of graph component G(j)G^{(j)} and Λ(j)\Lambda^{(j)} is the set of distinct eigenvalues of G(j)G^{(j)}. Such design allows SpecGSN to dynamically generate distinct spectral filter banks for different graph components within a single dataset.

Furthermore, SpecGSN is totally different from HeroFilter and DSF in the backbone of representation learning. While HeroFilter and DSF utilize the filtering-based architecture, SpecGSN adopts graph scattering transform with subspace-wise nonlinear activation for representation learning. The tree-structured graph scattering architecture combines different filters to achieve more abundant band-pass frequency responses and multi-scale representation.

  1. Component-adaptive graph filter bank vs. adaptive spectral wavelet convolution [3].

SpecGSN differs from WaveletGC in filter-bank generation mechanism and representation learning paradigm.

WaveletGC [3] adopts the eigenvalue encoding mechanism of Specformer [5], and utilizes a Transformer to capture spectral dependencies to generate the subsequent Chebyshev coefficients and wavelet scales. In contrast, SpecGSN extends eigenvalue encoding to multi-scale eigenvalue encoding to construct specific eigenvalue embeddings for different filters. Meanwhile, SpecGSN adopts a Transformer with component mask to directly generate the frequency response of each filter at individual spectral components, instead of generating a shared mother wavelet function. Denote Λ\Lambda as the set of eigenvalues for the whole dataset. While the wavelet bank generation for WaveletGC can be formulated as fs(λi)=ψ(sλi)f_s(\lambda_i )=\psi(s\lambda_i), where s=gθ∗(λi,Λ)s=g_\theta^*(\lambda_i,\Lambda) and ψ(λi)=gθ(λi,Λ)\psi(\lambda_i)=g_\theta (\lambda_i,\Lambda), the filter bank of SpecGSN is in the form of f(k)(λi(j))=gθ(skλi(j),Λ(j))f^{(k)}(\lambda_i^{(j)} )=g_\theta(s_k\lambda_i^{(j)}, \Lambda^{(j)}) where sks_k is the scale parameter. SpecGSN allows each filter to adopt its own frequency response for each graph component, instead of adopting a scaled version of the learned mother wavelet.

Furthermore, SpecGSN and WaveletGC are completely different in representation learning. WaveletGC adopts the network structure that is similar to SGWF [6] by transforming features into wavelet coefficients. SpecGSN utilizes the tree-structured graph scattering architecture (as shown in Figure 1 in the revised manuscript) with subspace-wise nonlinear activation. SpecGSN can cascade spectral filters to construct diverse multi-scale scattering representations, and prevent uncontrollable energy transfer between subspaces with the subspace-wise nonlinearity.

AuthorsOpenReview ↗

Responses to Reviewer p9Gc - part 2

W1 – Differentiation from existing spectral graph learning methods (continue)

  1. Spectral nonlinear activation via subspace folding vs. sign and basis invariant representation [4].

We acknowledge that the design of spectral nonlinear activation of SpecGSN shares the same motivation as SignNet/BasisNet [4]. Despite focusing 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 [4].

For 1D eigenspaces, SignNet explicitly ensures sign invariance through the form of ϕ(ur)+ϕ(−ur)\phi(u_r)+\phi(-u_r), where uru_r is the eigenvector of the rthr^{th} subspace. In contrast, SpecGSN first determines a direction Dr=sign(1⊤ur)D_r=sign(\mathbf{1}^\top u_r) such that Dr⊤ur⊤xD_r^\top u_r^\top x remains unchanged under ur↦−uru_r\mapsto-u_r. Only when the direction cannot be identified (∣1⊤ur∣<tol|\mathbf{1}^\top u_r|<tol), do we adopt Dr=12[1,−1]D_r=\frac{1}{\sqrt{2}}[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⊤U_rU_r^\top, where UrU_r is the eigenvector matrix of the rthr^{th} subspace of dimension krk_r. Instead of constructing the full projection matrix, SpecGSN builds a direction matrix Dr∈Rkr×mrD_r\in\mathbb{R}^{k_r\times m_r} with row selection on UrU_r. Here, mrm_r is the number of selected directions. Given any orthonormal basis transform with matrix Qr∈Rkr×krQ_r\in\mathbb{R}^{k_r\times k_r}, Ur↦UrQrU_r\mapsto U_rQ_r leads to Dr↦Qr⊤DrD_r\mapsto Q_r^\top D_r, ensuring UrDr=UrQrQr⊤Dr=U~rD~rU_rD_r=U_rQ_rQ_r^\top D_r=\tilde{U}_r\tilde{D}_r. Moreover, direction selection based on the ℓ2\ell_2-norm preserves permutation equivariance.

[1] Zhang, S., Wang, H., Lin, J., Guo, X., Zhu, Y., Zhang, S., Fu, D., & Zhou, D. (2025). HeroFilter: Adaptive spectral graph filter for varying heterophilic relations. In neural information processing systems (pp. 71898–71920).

[2] Guo, J., Huang, K., Yi, X., & Zhang, R. (2023). Graph neural networks with diverse spectral filtering. In ACM Web Conference (WWW) (pp. 306–316).

[3] Liu, N., He, X., Laurent, T., Di Giovanni, F., Bronstein, M. M., & Bresson, X. (2024). A general graph spectral wavelet convolution via chebyshev order decomposition [Preprint]. arXiv.

[4] 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.

[5] Bo, D., Shi, C., Wang, L., & Liao, R. (2023). Specformer: Spectral graph neural networks meet transformers [Preprint]. arXiv.

[6] Shen, Y., Dai, W., Li, C., Zou, J., & Xiong, H. (2021). Multi-scale graph convolutional network with spectral graph wavelet frame. IEEE Transactions on Signal and Information Processing over Networks, 7, 595–610.

AuthorsOpenReview ↗

Responses to Reviewer p9Gc - part 3

W2 - Multi-graph datasets and ablation study

We thank the reviewer for this valuable comment. Considering that most of the previously selected datasets only contain 1 graph components, 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) to provide stronger evidence for justifying component-adaptive filtering. 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 in the revised manuscript with the supplementary ablation study, and presented the information of the datasets and experimental settings in Appendices 6 and 7.)

MethodElliptic-S5Pattern-100Cluster-100PascalVOC-50
SpecGSN97.73±0.1997.73\pm0.1992.18±0.0992.18\pm0.0970.39±0.4070.39\pm0.4092.59±0.3192.59\pm0.31
SpecGSN+no mask97.69±0.1697.69\pm0.1692.12±0.1092.12\pm0.1070.30±0.9770.30\pm 0.9788.23±0.5688.23\pm0.56

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.

AuthorsOpenReview ↗

Responses to Reviewer p9Gc - part 4

W3 - Supplementary experiments on contemporary benchmarks and scalability limitations

We thank the reviewer for pointing out the missing heterophilic graph datasets and the potential problem of Chameleon. To provide a more comprehensive evaluation, we conduct additional experiments on three recent heterophilic benchmarks: Amazon-Ratings, Minesweeper, and Tolokers. Meanwhile, we also adopt the filtered version of Chameleon (named Chameleon-filtered) to further expand our experiments. The results are presented below.

All the experiments follow the same settings as described in the paper. Supplementary results are included in Section 5.1 and Appendix 4 in the revised manuscript. Information of datasets and experimental settings is presented in Appendices 6 and 7.

MethodsAmazon-RatingsTOLOKERSMINESWEEPERChameleon-Filtered
GCN47.88±0.3447.88\pm0.3480.29±0.0880.29\pm0.0880.22±0.0380.22\pm0.0340.39±0.9240.39\pm0.92
GAT51.89±0.1251.89\pm0.1281.09±0.1081.09\pm0.1084.88±0.2484.88\pm0.2440.66±0.6240.66\pm0.62
GraphSAGE47.02±0.2447.02\pm0.2480.73±0.1680.73\pm0.1686.16±0.1486.16\pm0.1443.12±1.2543.12\pm1.25
LightGCN39.49±0.0939.49\pm0.0978.21±0.0678.21\pm0.0680.11±0.0780.11\pm0.0738.79±0.8938.79\pm0.89
MixHop49.87±0.3349.87\pm0.3378.69±0.2978.69\pm0.2983.34±0.2283.34\pm0.2239.73±0.8239.73\pm0.82
DAGNN48.26±0.1348.26\pm0.1378.29±0.0978.29\pm0.0980.07±0.0280.07\pm0.0240.19±0.8640.19\pm0.86
HLGNN45.69±0.1945.69\pm0.1980.22±0.1080.22\pm0.1084.01±0.2784.01\pm0.2743.64±1.1243.64\pm1.12
DeloopSGNN47.18±0.1247.18\pm0.1279.07±0.0779.07\pm0.0784.80±0.2984.80\pm0.2939.47±0.7539.47\pm0.75
ChebNet50.74±0.2450.74\pm0.2481.77±0.1381.77\pm0.1388.23±0.12‾\underline{88.23\pm0.12}40.56±1.1040.56\pm1.10
GeomGNN48.79±0.3048.79\pm0.3081.39±0.1081.39\pm0.1086.92±0.1186.92\pm0.1142.13±1.2342.13\pm1.23
SGWF46.00±0.3946.00\pm0.3981.86±0.09‾\underline{81.86\pm0.09}86.82±0.1486.82\pm0.1439.17±0.8739.17\pm0.87
ARMA47.01±0.4047.01\pm0.4080.89±0.1280.89\pm0.1286.21±0.1686.21\pm0.1643.71±1.0343.71\pm1.03
Specformer47.75±0.2347.75\pm0.2379.96±0.1579.96\pm0.1585.44±0.2185.44\pm0.2142.97±0.8242.97\pm0.82
BernNet42.91±0.3042.91\pm0.3078.19±0.0278.19\pm0.0280.72±0.1980.72\pm0.1938.44±0.6938.44\pm0.69
GSN45.48±0.2245.48\pm0.2278.57±0.1278.57\pm0.1285.44±0.1885.44\pm0.1841.47±0.5541.47\pm0.55
LEGS48.25±0.2048.25\pm0.2079.52±0.1579.52\pm0.1584.19±0.2884.19\pm0.2843.23±0.2943.23\pm0.29
ScatteringGCN46.51±0.0946.51\pm0.0980.71±0.1880.71\pm0.1885.76±0.0685.76\pm0.0644.45±0.7444.45\pm0.74
GSAN46.32±0.1646.32\pm0.1678.54±0.1678.54\pm0.1684.47±0.3784.47\pm0.3739.30±0.7339.30\pm0.73
GGSN49.90±0.1349.90\pm0.1381.51±0.1581.51\pm0.1587.31±0.1687.31\pm0.1640.95±1.4440.95\pm1.44
ad-GSN40.45±0.2140.45\pm0.2182.15±0.19\mathbf{82.15\pm0.19}86.07±0.1686.07\pm0.1641.09±0.7141.09\pm0.71
SpecGSN52.22±0.60‾\underline{52.22\pm0.60}81.83±0.1581.83\pm0.1586.51±0.0786.51\pm0.0744.52±0.53‾\underline{44.52\pm0.53}
SpecGSN+Relu52.28±0.19\mathbf{52.28\pm0.19}81.40±0.1281.40\pm0.1286.28±0.1486.28\pm0.1445.03±0.28\mathbf{45.03\pm0.28}
SpecGSN$^\dagger$51.12±0.2651.12\pm0.2681.86±0.10‾\underline{81.86\pm0.10}88.33±0.19\mathbf{88.33\pm0.19}41.68±1.2741.68\pm1.27

SpecGSN achieves the best or nearly the best performance on Amazon-Ratings, TOLOKERS and Chameleon-filtered, while SpecGSN$^\dagger$ performs the best on MINESWEEPER. These supplementary experiments provide further evidence to support SpecGSN's effectiveness across more diverse heterophilic graph structures.

For large-scale graph datasets, the SpecGSN architecture could not be suited for handling very large graphs by requiring eigen-decomposition of graph shift operators. Specifically, SpecGSN requires full-spectrum perception to generate component-adaptive filter banks and perform subspace-wise nonlinear activation. For example, SpecGSN is limited in the applicability to graphs with more than 40K nodes in our experiments on NVIDIA GeForce RTX 3090 with 24 GB memory. However, such computational limitation arises for all the methods relying on full eigen-decomposition such as Specformer, WaveletGC and SGWF, and is not unique to SpecGSN. Developing efficient approximations such as truncated spectral representations or polynomial approximations to overcome this limitation is left for future works.

Reviewer_SGmeOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper presents SpecGSN, a graph scattering network that performs filtering and nonlinearity entirely in the spectral domain, thereby avoiding the per-layer GFT/iGFT round trips of standard scattering. It combines per-component spectral decomposition, a masked Transformer that generates filter banks for each connected component, and a "subspace folding" nonlinearity that is invariant to the choice of eigenbasis within degenerate subspaces, and it evaluates the method on twelve node-classification benchmarks plus a constructed multi-component dataset.

Critical strengths
  • Making the connected component an explicit modeling unit is a reasonable choice, since it prevents components that share a numerical eigenvalue from being forced to share a filter response.
  • Folding applies a pointwise nonlinearity in the spectral domain without depending on the choice of eigenbasis.
Critical weaknesses
  • Nonlinearity stays within each subspace, so no path moves energy across bands and depth only refines a per band transform.
  • Gains are not systematic, as homophilic gains cancel out, the largest heterophilic graphs lag, and the heterophilic advantage is confounded with graph size.
Questions for authors
  • Since the nonlinearity acts independently within each subspace, how does additional depth expose frequency content that is not already present in the input spectrum, and what does a layer count ablation show?
  • Given that the homophilic improvements cancel out and the largest heterophilic graphs lag, how do the authors separate the claimed heterophilic advantage from a small graph effect, for instance by comparing datasets of matched size?
  • Could the authors clarify what the two propositions contribute beyond the formal statement of these design choices, for example by naming a claim or an experimental decision that depends on them?
4 comments
AuthorsOpenReview ↗

Responses to Reviewer SGme - part 1

W1 – Energy transfer between subspaces

We thank the reviewers for careful reading and insightful comments. We emphasize that it is our deliberated design choice rather than a techincal limitation that the proposed spectral nonlinear activation does not enable energy transfer across spectral subspaces. Previous graph scattering networks (e.g., GSN, LEGS, GGSN) adopt the modulus operation that could introduce uncontrollable energy shifting across subspaces. For instance, the energy of eigenvector uiu_i is concentrated while the energy of its modulus ∣ui∣|u_i| usually spreads out. Such energy transfer disrupts the spectral localization and does not necessarily lead to better performance in node classification.

Most importantly, our experimental results support this design choice. In the original experiments, SpecGSN achieves similar or superior performance compared with SpecGSN$^\dagger$ except Roman-Empire. Notice that SpecGSN$^\dagger$ differs from SpecGSN only by applying node-wise modulus operation in the graph scattering transform. In supplementary experiments with the Chameleon-filtered dataset, SpecGSN$^\dagger$ exhibits overfitting and achieves only 41.68%±1.27% accuracy, while SpecGSN and SpecGSN+Relu outperform all other baselines and achieve 44.52%±0.53% and 45.03%±0.28%, respectively. These results suggest that cross-subspace energy transfer is not necessary for better node classification performance.

AuthorsOpenReview ↗

Responses to Reviewer SGme - part 2

W2 & Q2 - The gains for different datasets and relation to graph size

Despite that the designed SpecGSN may not be the optimal choice for every dataset, it maintains competitive performance across diverse datasets, even if it does not perform the best. More importantly, we observe that the advantage on heterophilic graphs is not simply attributed to graph size. On Roman-Empire (22662 nodes), SpecGSN is superior to all the baselines except for SpecGSN$^\dagger$ and GGSN. On Amazon-Ratings (24492 nodes), SpecGSN outperforms all competing methods. These results demonstrate that SpecGSN is not only effective on small graphs such as TEXAS, WISCONSIN and CORNELL, but also competitive on large heterophilic graphs.

Some results from supplementary experiments (all the experiments follow the same settings as described in the paper). All the supplementary results are updated in Section 5.1 and Appendix 4 in the revised manuscript. Information of datasets and experimental settings is presented in Appendices 6 and 7.

MethodsAmazon-RatingsChameleon-Filtered
GCN47.88±0.3447.88\pm0.3440.39±0.9240.39\pm0.92
GAT51.89±0.1251.89\pm0.1240.66±0.6240.66\pm0.62
GraphSAGE47.02±0.2447.02\pm0.2443.12±1.2543.12\pm1.25
LightGCN39.49±0.0939.49\pm0.0938.79±0.8938.79\pm0.89
MixHop49.87±0.3349.87\pm0.3339.73±0.8239.73\pm0.82
DAGNN48.26±0.1348.26\pm0.1340.19±0.8640.19\pm0.86
DeloopSGNN47.18±0.1247.18\pm0.1239.47±0.7539.47\pm0.75
ChebNet50.74±0.2450.74\pm0.2440.56±1.1040.56\pm1.10
GeomGNN48.79±0.3048.79\pm0.3042.13±1.2342.13\pm1.23
SGWF46.00±0.3946.00\pm0.3939.17±0.8739.17\pm0.87
ARMA47.01±0.4047.01\pm0.4043.71±1.0343.71\pm1.03
Specformer47.75±0.2347.75\pm0.2342.97±0.8242.97\pm0.82
BernNet42.91±0.3042.91\pm0.3038.44±0.6938.44\pm0.69
GSAN46.32±0.1646.32\pm0.1639.30±0.7339.30\pm0.73
GGSN49.90±0.1349.90\pm0.1340.95±1.4440.95\pm1.44
ad-GSN40.45±0.2140.45\pm0.2141.09±0.7141.09\pm0.71
SpecGSN52.22±0.60‾\underline{52.22\pm0.60}44.52±0.53‾\underline{44.52\pm0.53}
SpecGSN+Relu52.28±0.19\mathbf{52.28\pm0.19}45.03±0.28\mathbf{45.03\pm0.28}
SpecGSN$^\dagger$51.12±0.2651.12\pm0.2641.68±1.2741.68\pm1.27
AuthorsOpenReview ↗

Responses to Reviewer SGme - part 3

Q1 - Frequency missing issue and ablation of spectral nonlinear activation

To further address the frequency missing issue, we introduce an optional learnable bias in the proposed spectral nonlinear activation based on subspace folding to recover frequency components that are missing before the graph scattering transform.

σspec(r)(X^r)=X^r+Dr(σ(DrTX^r)+1mrb−DrTX^r),\sigma_{spec}^{(r)}(\hat{X}_r)=\hat{X}_r+D_r(\sigma(D_r^T\hat{X}_r)+\mathbf{1}_{m_r}b-D_r^T\hat{X}_r),

where b∈R1×Cb\in\mathbb{R}^{1\times C} is the learnable parameter shared across different activation directions within a subspace and across different subspaces. The bias can be configured individually for 1-dimensional and multi-dimensional subspaces with only a limited number of additional learnable parameters. This formulation alleviates the frequency missing issue while preserving the permutation equivariance and basis-rotation invariance of the proposed spectral nonlinear activation. Our supplementary experiments demonstrate that this modification can further improve classification performance for some datasets. The implementation of bias improves SpecGSN’s performance on Texas from 85.92%±2.00% to 86.09%±0.86%, and SpecGSN+Relu’s performance on WISCONSIN from 83.48%±1.33% to 83.91%±0.72%. We have updated Section 4.2 and Appendices 2 and 3 with technical modification and proofs in the revised manuscript.

Furthermore, we claim that the absence of certain frequency components does not necessarily lead to degradation of nodes’ discriminability. Consider a four-node cycle (C4) with u4=[1/2,−1/2,1/2,−1/2]⊤u_4=[1/2,-1/2,1/2,-1/2]^⊤. For x=[1,0,0,1]⊤x=[1,0,0,1]^⊤, u4⊤x=0u_4^⊤ x=0. The direction matrix for the second subspace is D2=1/√2×[[1,0,−1,0],[0,1,0,−1]]∈R2×4D_2=1/√2×[[1,0,-1,0],[0,1,0,-1]]\in \mathbb{R}^{2×4}. The proposed spectral nonlinear activation gives rise to the node representations in the form of [c+a,c−a,c−a,c+a]⊤[c+a,c-a,c-a,c+a]^⊤, where a=σ(1/2)≠0a=σ(1/2)≠0 and c=σ(1)/2c=σ(1)/2. The two node classes are separable. Similarly, for the two-channel input X=[[1,0,0,1]⊤,[1,1,0,0]⊤]X=[[1,0,0,1]^⊤,[1,1,0,0]^⊤], the four nodes remain distinguishable after our spectral nonlinear activation.

Finally, the comparison between SpecGSN and SpecGSN$^\dagger$ serves as the ablation study for the proposed spectral nonlinear activation. It shows that full energy transfer between subspaces is not a must. Refining nonlinear representations within existing spectral subspaces can be both competitive and time-efficient. A more detailed comparison between SpecGSN and SpecGSN$^\dagger$ is provided in Appendix 5 in the revised manuscript.

AuthorsOpenReview ↗

Responses to Reviewer SGme - part 4

Q3 - The meanings of propositions and relation to design choice

The meanings of propositions: The two propositions are not only formal statements of the design choices, they motivates the whole design of the spectral nonlinear activation. As emphasized by SignNet/BasisNet [1] and Laplacian Canonization [2], graph permutation equivariance and canceling spectral basis ambiguities are fundamental for reliable representation learning with spectral GNNs. Basis rotation invariance guarantees that the output of SpecGSN is independent of the basis choice for each eigenspace, while permutation equivariance guarantees the consistency of learned representation under node relabeling. Without such properties, node relabeling or basis choice could lead to different representations for the same graph signal with the same topology. This violates the fundamental symmetry of representation learning for graph-structured data.

Relation to design choice: Proposition 4.1 directly affects the construction of direction matrix DrD_r for each subspace. Rather than applying element-wise nonlinear activation on spectral coefficients, a direction selection algorithm is developed to select the “reference directions” for subspace folding. We choose the norm-2 metric for direction selection, since it is permutation invariant. Meanwhile, the rows of UrU_r are adopted as candidate directions so that UrDr=UrQQTDr=U~rD~rU_rD_r=U_rQQ^TD_r=\tilde{U}_r\tilde{D}_r forms a basis-rotation invariant operator for XrX_r.

Proposition 4.2 directly relates to the motivation for the component-adaptive mask by designing the adaptive filter in the form of f(λi(j))=gθ(λi(j),Λ(j))f(\lambda_i^{(j)})=g_\theta(\lambda_i^{(j)}, \Lambda^{(j)}), where λi(j)\lambda_i^{(j)} is the ithi^{th} eigenvalue of graph component GjG_j, Λ(j)\Lambda^{(j)} is the set of distinct eigenvalues of GjG_j, rather than adopting the traditional form of f(λi)=gθ(λi)f(\lambda_i)=g_\theta(\lambda_i). The ablation study in Section 5.2 and supplementary experiments on the graph component mask support the statement that the component-adaptive filter bank is more expressive than the unified filter bank for all graph components. We have updated Section 5.2 to include all the supplementary results and presented the information of datasets and experimental settings in Appendices 6 and 7 in the revised manuscript.

All the experiments follow the same settings as described in the paper. Elliptic-S5: the five smallest connected components of Elliptic. PATTERN-100 and CLUSTER-100: the first 100 graphs from PATTERN and CLUSTER respectively. PascalVOC-50: the first 50 graphs from PascalVOC-SP.

MethodElliptic-S5Pattern-100Cluster-100PascalVOC-50
SpecGSN97.73±0.1997.73\pm0.1992.18±0.0992.18\pm0.0970.39±0.4070.39\pm0.4092.59±0.3192.59\pm0.31
SpecGSN+no mask97.69±0.1697.69\pm0.1692.12±0.1092.12\pm0.1070.30±0.9770.30\pm 0.9788.23±0.5688.23\pm0.56

[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).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.