SSGNN: Simple Yet Effective Spectral Graph Neural Network

The results in the table below clearly illustrate the significant impact of the ReGA module on performance across various datasets.

Removing ReGA results in a noticeable decline in accuracy, with performance improvements of 2.91% on Chameleon, 2.64% on Squirrel, 2.26% on Amazon Ratings, 2.07% on Actor, 1.69% on Cora, 1.39% on Penn94, 1.29% on Tolokers, and 1.19% on Minesweeper when ReGA is incorporated. These consistent improvements across various datasets highlight ReGA’s pivotal role as a key contributor to SSGNN’s performance, directly addressing the reviewer’s concern regarding the impact of the ReGA module.

$**Answer-3**$: Thank you for pointing this out. We will definitely try to improve the manuscript's presentation. Just to clarify, “*” indicates models that were trained from scratch.

To address concerns regarding sparse decomposition, we leverage insights from the learned filters: band-rejection and high-pass filters are crucial for heterophilic datasets, while low-pass filters work well for homophilic datasets. Accordingly, we use eigenvectors with the smallest 3000 (low-frequency) and largest 3000 (high-frequency) eigenvalues for Penn94 (large-scale heterophilic) and the smallest 5000 eigenvalues (low-frequency) for ogbn-arXiv (large-scale homophilic). This targeted approach ensures meaningful spectral decomposition, avoiding performance loss while maintaining computational efficiency. Experimental results in Tables 2 and 3 of the main paper demonstrate that under these settings, SSGNN outperforms other models on ogbn-arXiv (large-scale homophilic graph) and Penn94 (large-scale heterophilic graph), demonstrating the effectiveness of this strategic spectral decomposition.

Table 1 presents the pre-computation (eigen decomposition) time for the graphs. It is important to note that this decomposition is performed only once. Consequently, the overall complexity of SSGNN is better represented as the sum of its forward pass complexity and the decomposition cost amortized over the number of uses in training and inference, rather than a direct summation of the two.

Table-1: Precomputation (decomposition) time for different datasets.

Table 2 summarizes the training time per epoch (ms) for Specformer, Polynormer, and SSGNN across homophilic and heterophilic graphs. SSGNN consistently demonstrates faster training times compared to Specformer and Polynormer, even on large-scale graphs like ogbn-arxiv and Penn94. However, on smaller datasets such as Chameleon and Squirrel, Specformer achieves slightly faster training times, likely due to the smaller node count.

$**Table-2:**$ Training time per epoch (in ms) of Specformer, Polynormer and SSGNN.

This addresses the reviewer’s concerns regarding the inclusion of training costs for baseline models and the precomputation time (eigen decomposition) required for SSGNN.

This insight emerged as a key finding from our detailed investigation of Specformer. To evaluate the role of Transformers in spectral filtering, we performed ablation studies by removing the multi-head attention (MHA) and feedforward network (FFN) blocks, retaining only the EigenEncoder and decoder. Interestingly, this simplified architecture achieved results that were comparable to, or even better than, the Specformer, as shown in the table below.

These findings highlight that Transformers contribute minimally to spectral domain performance, reinforcing the claim made in the abstract. Furthermore, the simplified architecture fits efficiently within the 24GB memory of an RTX 4090 GPU and delivers performance on par with SOTA models. In contrast, the original Specformer is unable to fit on datasets such as Roman Empire, Amazon Ratings, and Questions.

Below is Table 3, which shows the GPU usage for Specformer, Polynormer, and SSGNN in MiB. SSGNN occupies the least amount of GPU across almost all datasets.

Table3

SSGNN has a parameter count of 400K, which is lower than many of the best-performing models reported in the benchmarking experiments from [1]. For instance, GCN with 16 layers has 505K parameters and achieves a MAE of 0.278, while GatedGCN-E-PE with 16 layers has 505K parameters and achieves a MAE of 0.214 on the ZINC dataset. Similarly, Specformer, has 555K parameters and achieves a MAE of 0.066. Despite having fewer parameters than these models, SSGNN achieves a MAE of 0.0592 on the ZINC dataset, setting a new standard for accuracy. We would like to seek clarification regarding the mention of 50K parameters for ZINC. If it is a typographical error and the intended reference is 500K, we completely understand. However, if 50K parameters is indeed correct, we would be grateful if the reviewer could guide us to the relevant sources that achieve performance similar to SSGNN.

[1] Dwivedi, V.P., Joshi, C.K., Luu, A.T., Laurent, T., Bengio, Y. and Bresson, X., 2023. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43), pp.1-48.

The tables below present a comparison of training time per epoch (ms) in Table 1 and parameter count in Table 2 for Specformer, Polynormer, and SSGNN.

Table1 - Training time per epoch (ms)

Table2 - Parameter Count

The results clearly demonstrate that SSGNN has the lowest parameter count and the shortest training time per epoch, effectively addressing the reviewer’s concern regarding the time and space overhead comparison among Specformer, Polynormer, and SSGNN.

The results in Table 3 below clearly illustrate the significant impact of the ReGA module.

Table3

Removing ReGA results in a noticeable decline in accuracy, with performance improvements of 2.91% on Chameleon, 2.64% on Squirrel, 2.26% on Amazon Ratings, 2.07% on Actor, 1.69% on Cora, 1.39% on Penn94, 1.29% on Tolokers, and 1.19% on Minesweeper when ReGA is incorporated. These consistent improvements across various datasets highlight ReGA’s pivotal role as a key contributor to SSGNN’s performance.

To address this, we conducted comprehensive experiments to evaluate the role of eigen-correction and determine whether the performance improvement of SSGNN primarily stems from ReGA or eigen-correction. Specifically, we trained Specformer with eigen-correction to ensure a fair comparison, as shown in the Table 1 below.

Table1

The results demonstrate that even with eigen-correction, Specformer is outperformed by SSGNN (with eigen-correction) across most datasets. Furthermore, we removed eigen-correction from SSGNN and observed its performance, as presented in the Table 2 below.

Table 2

SSGNN without eigen-correction still outperformed Specformer on several datasets, highlighting the pivotal role of the ReGA module in its performance. Moreover, SSGNN benefited significantly more from eigen-correction than Specformer, showcasing its ability to effectively utilize this enhancement. These findings affirm that while eigen-correction adds value, SSGNN’s success is primarily driven by its ReGA module.

We acknowledge the reviewer’s observation regarding the absence of explicit set-to-set modelling in SSGNN. Unlike Specformer, which employs transformers to model relative interactions among eigenvalues, SSGNN achieves global context filtering through the mean shift applied to the decoder’s output. This mean shift computes a global mean and standard deviation across all N nodes, implicitly enabling interaction among eigenvalues.

To further substantiate the importance of this mechanism, we conducted an ablation study where the mean shift was removed, and the decoder’s output was directly passed to the scoring function. This resulted in a clear performance degradation as shown in the Table below, demonstrating that mean shift effectively captures global context and highlights the importance of interactions among eigenvalues.

Thus, while SSGNN may not explicitly perform set-to-set filtering, it leverages global context to model interactions, which is crucial for its performance, addressing the reviewer’s concern regarding “set-to-set” filtering.

• We initially planned to address the reviewer's queries in the rebuttal and update it in the revised manuscript. However, we have now uploaded the modified manuscript, with all changes clearly marked in red coloured text. We hope this will address the reviewer's confusions.

• As stated in our earlier response, we clearly agree with the reviewer that SSGNN does not perform a set-to-set filtering approach. This correction has been made in the revised manuscript, and we now term our filtering mechanism as global context filtering, which differs from set-to-set filtering. We sincerely thank the reviewer for carefully pointing out this mistake.

• Regarding the eigen-correction strategy, we cannot apply eigen-correction to Polynormer as it is a Graph Transformer, not a spectral filter-based approach. The eigen-correction strategy, as introduced in [1], specifically applies to spectral filters. Since Polynormer operates on Graph Transformer rather than spectral filters, incorporating eigen correction is not applicable to its framework.

• In Table 1 of the author response (where eigen correction is applied to both Specformer and SSGNN), Specformer marginally outperforms SSGNN on only 2 datasets: Photo (by 0.31%) (homo) and Penn94 (by 0.17%) (hetero). However, SSGNN outperforms Specformer on datasets, such as Chameleon (by 6.98%) (hetero), Squirrel (by 6.75%) (hetero), and others like Amazon-Computer (by 5.59%) (homo), Actor (by 2.11%) (hetero), and achieves nearly 1% higher performance on most other datasets. These improvements are substantial compared to Specformer’s minor gains on Photo and Penn94.

• Similarly, in Table 2 of the author response (where eigen correction is not applied in both the models), Specformer performs marginally better than SSGNN on 4 datasets: Cora (by 0.05%) (homo), Photo (by 0.39%) (homo), CS (by 0.36%) (homo), and Minesweeper (by 0.17%) (hetero). However, SSGNN significantly outperforms Specformer on others with gains of 5.94% on Chameleon (hetero), 4.49% on Squirrel (hetero), 3.75% on Amazon-Computer (hetero), and nearly 0.5% improvements on most other datasets. These improvements are substantial compared to Specformer’s minor gains on Cora, Photo, CS and Minesweeper.

• Based on these clarifications, we request the reviewer to revisit our points and consider re-evaluating the score.

[1] Lu, K., Yu, Y., Fei, H., Li, X., Yang, Z., Guo, Z., Liang, M., Yin, M. and Chua, T.S., 2024, March. Improving Expressive Power of Spectral Graph Neural Networks with Eigenvalue Correction. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 38, No. 13, pp. 14158-14166).

To substantiate the importance of mean-shift operation, we conduct an ablation study where the mean shift was removed, and the decoder’s output was directly passed to the scoring function. This resulted in a clear performance degradation as shown in the Table below, demonstrating that mean shift effectively captures global context and highlights the importance of interactions among eigenvalues.

Thus, mean-shift plays a vital role in capturing the global context, enabling effective modelling of interactions.

We agree that using the same symbol in multiple contexts can make the paper more difficult to read, and we address this in the revised manuscript to improve clarity. Specifically, $\epsilon$ in Line 182 refers to the scaling factor in the Eigen Encoder, $\epsilon$ in Lines 240-241 denotes the small constant added to the standard deviation $\sigma$ for numerical stability, and $\epsilon$ in Line 307 represents the bounded perturbation. Additionally, we confirm that the ablation experiments reported in Figure 4 were conducted on the $\epsilon$ representing the scaling factor in the Eigen Encoder. We ensure these distinctions are clearly stated in the revised version to enhance readability and avoid any confusion.

We acknowledge the reviewer’s observation regarding the absence of explicit set-to-set modelling in SSGNN. In Specformer, the "set" refers to the set of eigenvalues, and the transformer explicitly models relative dependencies among them. In contrast, SSGNN does not employ transformers or explicitly model interactions among eigenvalues through relative dependencies. Instead, SSGNN achieves global context filtering via the mean shift mechanism applied to the decoder’s output. This mean shift computes a global mean and standard deviation across all N nodes, implicitly enabling interactions among eigenvalues by normalizing them against the global context. Thus, while SSGNN may not explicitly perform set-to-set filtering, it leverages global context to model interactions, which is crucial for its performance, addressing the reviewer’s concern regarding set-to-set filtering.

The transformations could indeed be combined into a single unit. However, for better clarity and understanding, we separated them into the encoder and decoder stages. Specifically, $W_{\text{eig}}$ in the encoder is designed to capture the interdependencies between the corrected eigenvalues and their associated d -dimensional vectors. In the decoder, $W_1$ extracts meaningful patterns from the encoded representations, while $W_h$ learns diverse spectral filters initially and aligns these filters as the model converges. This division also ensures clarity in explaining the roles of each component at different stages. We hope this addresses the reviewer’s concerns.

We acknowledge that some components of our method have been previously explored. However, our primary goal is to develop a lightweight yet robust Spectral GNN. Drawing inspiration from Specformer, we first identified the absence of eigen-correction mechanisms, which we addressed to enhance performance. Additionally, we observed that transformers contribute minimally at the spectral level while introducing quadratic time complexity, raising scalability concerns for larger graphs. To address these limitations, we proposed a parameter-free ReGA for adaptive filtering, refining the filter bases learnt by the decoder. This ensures effective filtering while surpassing transformer-based set-to-set filtering in both performance and efficiency. The systematic analysis of each concept, coupled with the targeted solutions we introduce at each stage, offers a novel and meaningful perspective to the field.

We have provided visualizations demonstrating how different decoder heads influence the performance of SSGNN. These visualizations have been added as Figures 19, 20, and 21 in Section F: Visual Insights of the Multi-Headed Decoder in the Appendix of our revised manuscript.

For this analysis, we used the Amazon-Computers dataset. A single-head configuration achieves an accuracy of 90.5116, with convergence at the 849th epoch. Increasing to two heads improves the accuracy to 90.775 and reduces convergence to the 764th epoch. Our four-head configuration achieves the best results, with an accuracy of 91.28 and convergence at the 609th epoch.

Figures 19, 20, and 21 illustrate the filters learnt by the 1-head, 2-head, and 4-head configurations, respectively. The visualizations show that in the 4-head setup, the filters display variation during the initial epochs (e.g., the 25th epoch). By the 250th epoch, the filters begin to align, and by the 575th epoch, they converge to similar patterns. This progression demonstrates that using multiple heads allows the model to explore diverse filtering patterns in the early stages, ultimately accelerating convergence and improving performance.

Thanks for your detailed reply. I still keep my score.

The spectral decomposition is pre-computed using the eigen decomposition of the normalized graph Laplacian, which has a computational complexity of $\mathcal{O}(N^3)$, where $N$ represents the number of nodes in the graph. However, this computation is performed only once and stored, with the cost amortized across multiple training and inference steps. For smaller graphs, the pre-computation overhead is minimal. For larger graphs, fast numerical methods such as Krylov subspace approximations for the top $k$ eigenvalues or Sparse Generalized Eigenvalue algorithms can significantly reduce the cost by efficiently estimating $k$ eigenvalues and eigenvectors without the need for expensive full decomposition.

In our experiments on large graphs, we leverage insights from the learned filters: band-rejection and high-pass filters are crucial for heterophilic datasets, while low-pass filters work well for homophilic datasets. Accordingly, we use eigenvectors with the smallest 3000 (low-frequency) and largest 3000 (high-frequency) eigenvalues for Penn94 (large-scale heterophilic) and the smallest 5000 eigenvalues (low-frequency) for ogbn-arXiv (large-scale homophilic). This targeted approach ensures meaningful spectral decomposition, avoiding performance loss while maintaining computational efficiency.

We evaluate the scalability and performance of SSGNN across several large-scale graph datasets. For node classification, experiments were conducted on ogbn-arxiv (a large-scale homophilic graph with 169,343 nodes and 1,166,243 edges), Penn94 (41,554 nodes and 1,326,229 edges), and pokec (1,632,803 nodes and 30,622,564 edges) as large-scale heterophilic graphs. For large scale graph classification, we tested on MolPCBA, an Open Graph Benchmark dataset with 437,929 graphs.

Table 1 compares the accuracy of SSGNN with Specformer on large-scale node classification tasks (ogbn-arxiv, Penn94, and pokec) and graph classification tasks (MolPCBA, where AP values are reported). SSGNN outperforms Specformer across all datasets. For node classification, we also compared SSGNN with Polynormer in our main manuscript. While SSGNN surpasses Polynormer on ogbn-arxiv and Penn94, we did not include Polynormer results on pokec. It is important to note that SSGNN on pokec requires determining the appropriate smallest and largest k eigenvalues to ensure a fair comparison. However, due to time constraints, we could not conduct this extensive experimentation within the discussion window. As an initial experiment, we computed eigenvectors with the smallest 3000 (low-frequency) and largest 3000 (high-frequency) eigenvalues and compared SSGNN’s results with Specformer, as both methods share the same precomputation. This ensures consistent training settings. However, this is not the final result of SSGNN on Pokec and should be treated as preliminary findings.

• These results demonstrate that SSGNN outperforms Specformer in accuracy while training faster and requiring fewer parameters.

Table1 - Accuracy/AP comparison between Specformer and SSGNN

Table 2 reports the training time per epoch (in ms), where SSGNN consistently trains faster than Specformer on large-scale graphs.

Table2 - Time per Epoch (ms) for Specformer and SSGNN

Table 3 details the parameter counts, showing that SSGNN has significantly fewer parameters than Specformer on all datasets.

Table3 - Parameter Count of Specformer and SSGNN

These experiments address the reviewer’s concerns regarding the evaluation of SSGNN on large-scale graphs.

We sincerely appreciate the valuable feedback and recommendations to improve the experimental section. In response, we have included comprehensive comparisons between SSGNN and the relevant baselines, SGC and SSGC, evaluating both accuracy and training time per epoch (ms) across various datasets. The results, presented in Tables 1 and 2, demonstrate that SSGNN consistently outperforms SGC and SSGC in terms of accuracy, particularly on heterophilic datasets where SGC and SSGC face challenges. Tables 1 and 2 compare node classification accuracy on homophilic and heterophilic graphs among SGC, SSGC, and SSGNN. These results clearly show that SSGNN achieves superior accuracy across nearly all datasets. Table 3 and Table 4 present the training time per epoch (ms) for SGC, SSGC, and SSGNN on homophilic and heterophilic graphs, respectively.

Table1 - Comparison of node classification accuracy on homophilic graphs

Table2 - Comparison of node classification accuracy on heterophilic graphs

Table3 - Training time per epoch (ms) on homophilic graphs

Table4- Training time per epoch (ms) on heterophilic graphs

SGC and SSGC demonstrate faster training times due to their reliance on a simple two-layer MLP with precomputed aggregation. In contrast, SSGNN involves multiple components, including the encoder, decoder, ReGA, and graph convolution layer, which require more computation time compared to SGC and SSGC’s minimal architecture. However, our findings highlight a critical distinction: while SGC and SSGC perform well on homophilic graphs, their precomputation method, rooted in homophilic aggregation, hampers their effectiveness in heterophilic settings. SSGNN, on the other hand, effectively models both homophilic and heterophilic patterns, achieving a balanced tradeoff between accuracy, training speed, parameter efficiency, and computational demands. These additions comprehensively address the reviewers’ concerns regarding the need for extensive experimentation and analysis.

The table below summarizes the training time per epoch (in milliseconds) for Specformer, Polynormer, and SSGNN across homophilic and heterophilic graphs. SSGNN consistently demonstrates faster training times compared to Specformer and Polynormer, even on large-scale graphs like ogbn-arxiv and Penn94. However, on smaller datasets such as Chameleon and Squirrel, Specformer achieves slightly faster training times, likely due to the smaller node count.

Table-1: Training time per epoch (in ms) of Specformer, Polynormer and SSGNN.