Rethinking Spectral Graph Neural Networks with Spatially Adaptive Filtering

Q.1 Limitations regarding spectral decomposition in this work.

Thank you for your feedback on our use of spectral decomposition. We have addressed this shared concern in our "global" response.

Q.2 I am a little confused with the so-called supervised setting.

Thank you for your inquiry about the "supervised setting" in our experiments.

(1) In line with established experimental protocols in transductive node classification, as referenced in prior works [1,2,3], our approach utilizes all node features (train, validation, and test) while only incorporating training node labels during the training phase. This method is a standard practice in the field, aimed at evaluating GNNs in node-level tasks.

(2) To further evaluate models comprehensively under varying levels of supervision, we implemented two distinct data splitting strategies: a sparse splitting (2.5%/2.5%/95%) and a dense splitting (60%/20%/20%) for the training, validation, and testing sets, respectively. Consistent with the terminology used in [3], we refer to these tasks as "semi-supervised" and "full-supervised" node classification. This distinction is based on the degree of supervision each setting entails.

[1] Chien, Eli, et al. "Adaptive universal generalized pagerank graph neural network." ICLR, 2021.

[2] He, Mingguo, et al. "Bernnet: Learning arbitrary graph spectral filters via bernstein approximation." NeurIPS, 2021.

[3] He, Mingguo, et al. "Convolutional neural networks on graphs with chebyshev approximation, revisited." NeurIPS, 2022.

Q.3 Theoretically, as the adapted new graph can express the power series of graph Laplacian, the most straightforward advantage of SAF, against existing spectral GNNs that use truncated polynomial approximation, is the capability of fitting specific graph filters.

Thanks for your constructive feedback and the insightful suggestion to incorporate experiments on fitting specific filters. We appreciate this opportunity to clarify the scope and focus of our work.

(1) Essence of the Adapted New Graph: In our theoretical framework, the adapted new graph is fundamentally anchored in the spatial domain. This spatial orientation plays a pivotal role in making spectral GNNs interpretable. While it is true that our new graph expresses the infinite power series of the graph Laplacian (more so of the original adjacency matrix $\hat{\mathbf{A}}$), this aspect mainly highlights its non-local nature in the vertex domain. This non-locality is crucial for our approach to capture complex node relations, but it does not intrinsically boost expressiveness in the spectral domain.

(2) Enhancement of Spectral GNNs by SAF: Our SAF framework is designed to address a key limitation of existing spectral GNNs -- the oversight of global vertex dependencies caused by truncated polynomials. By employing spatial aggregation on the non-local new graph, SAF adeptly captures long-range dependencies between nodes, a feature we have rigorously demonstrated in our experiments. These findings demonstrate SAF's effectiveness in handling complex graph structures, particularly in scenarios like heterophilic graphs where global interactions are essential.

(3) Comparison in Fitting Specific Filters: Addressing the spectral domain challenge of fitting specific filters, it's noteworthy that both our SAF and BernNet utilize Bernstein polynomials as their spectral filter functions. This commonality implies that any experimental results in this regard would likely be identical for both frameworks. Hence, we chose not to include this specific task in our experiments. The congruence in the outcomes also underscores that our framework aligns with the capabilities of existing approaches in the spectral domain.

Q.4 Could you explain figure 1 for me?

Thanks for your question regarding Figure 1 in our paper. We are pleased to provide further clarification on its content and how it supports our conclusions.

(1) In Figure 1, the x-axis represents the geodesic distance between node pairs in the original graph. This distance is calculated as the number of hops in the shortest path between the vertices. Concurrently, the y-axis quantifies the frequency of node pairs (of various types) being connected in the new graph.

(2) Using the Minesweeper dataset in Figure 1, where the longest geodesic distance is 99, as an example, we observe that node pairs from the original graph, regardless of their distance, are often directly connected in the new graph (indicated by a frequency greater than 0). This finding is crucial as it demonstrates the capability of the new graph to establish direct links among nodes that originally require multiple hops to do so.

(3) To enhance clarity, we have revised the caption of Figure 1 as "Distributions of adjacent nodes in the new graph based on their geodesic distance in the original graph. It is seen that nodes, distant in the original graph, can be connected in the new graph.".

Thanks for your detailed explanation! I also read your general response. I appreciate the analysis and the connections established in this paper. However, when it comes to instantiate a concrete GNN architecture, it requires the eigen-decomposition, which is unaffordable for even graph of moderate size. This is not a severe issue for a research paper in my opinion, but there would be a lot of interesting design/variants for spectral GNNs if such a computation is allowed. In this sense, I tend to keep the rating unchanged, while raising contribution to 3.

Q.1 SAF is only compatible with BernNet due to its assumption of non-negative filtering. As a result, it raises questions about whether the observed good performance is attributable to BernNet or SAF?

Thank you for your thoughtful feedback regarding the compatibility of our SAF framework with BernNet. We appreciate the opportunity to clarify and expand on this important aspect of our work.

(1) As you rightly pointed out, SAF indeed requires non-negative graph filters, which we discuss in Section 5 of our paper. However, we would like to highlight that SAF's compatibility extends beyond BernNet. Theoretically, SAF is also applicable to other models like ChebNetII [1], a recent Spectral GNN variant based on Chebyshev interpolation, by reparameterizing its learnable parameters to be non-negative. To substantiate this theoretical proposition, we have conducted additional experiments with ChebNetII, incorporating our SAF framework. These experiments yielded encouraging results as shown in the following table, proving the potential of SAF in enhancing models other than BernNet.

Full-supervised node classification accuracies (%)

(2) While SAF, as detailed in our paper, does build upon the foundational structure of BernNet, its distinct feature is the inclusion of non-local aggregation, aimed at capturing long-range dependencies and addressing graph heterophily. This aspect is crucial for advanced graph learning and is not a native feature of BernNet. Our experimental results, as detailed in Tables 1, 2, and 4, clearly show that the enhancements brought by SAF are distinct and significant, with performance improvements of up to 15.37%. These results underscore the unique contributions of SAF, reaffirming its significance beyond the inherent capabilities of BernNet.

[1] He, Mingguo, et al. "Convolutional neural networks on graphs with chebyshev approximation, revisited." NeurIPS, 2022.

Q.2 When compared to other spectral methods, SAF requires eigen decomposition, which incurs a time complexity of O(n 3). This is a computational cost that exceeds that of other baseline methods that does not need eigen decomposition (BernNet, ChebNetII).

Thanks for raising the question regarding our explict use of spectral decomposition. As this concern was shared among multiple reviewers. we've addressed it in the "global" response for a thorough explanation.

Q.1 Computational Concerns about the use of explicit eigndecomposition.

Thank you for raising this important question. We acknowledge that this query was shared among multiple reviewers. To provide a comprehensive response, we have elaborated on this topic in our "global" response section.

Q.2 Opting for the Bernstein basis as the backbone may not represent the optimal choice. On the one hand, ChebNetII can also guarantee filter non-negativity, and its Chebyshev interpolation boasts lower complexity in comparison to Bernstein approximation.

Thank you for your insightful comments regarding our choice of the Bernstein basis in our SAF framework. Your comment has prompted a valuable extension of our analysis, which can be found in the Appendix G of our revised manuscript.

(1) Experimenting with ChebNetII as Base Model: We sincerely apologize for the initial omission in not including experiments with ChebNetII as a base model for SAF. We have now conducted additional experiments with ChebNetII as a base model for SAF (SAF-Cheb), alongside our original implementation using BernNet (SAF-Bern). The results, which we present in the subsequent table, illustrate that SAF indeed enhances ChebNetII’s performance.

Full-supervised node classification accuracies (%)

(2) Performance Comparison: Interestingly, SAF-Bern slightly outperforms SAF-Cheb in most datasets, and the improvement margin with SAF-Bern is notably larger. This may be due to the $g_ \phi(\lambda) \leq 1$ constraint in our SAF (see Section 5), where filter functions need to be rescaled by their maximum values on the graph spectrum. For Bernstein polynomials, this maximum is simply the maximum polynomial coefficient ($\max \{\phi_k\}_ {k=0}^K$), as per our Proposition 3. In contrast, the best theoretical upper bound for Chebyshev polynomials is $\sum_ {k=0}^K |\phi_ k|$, which is less precise. This distinction potentially affects the new graph's construction, thereby limiting model performance. We plan to address this issue in future work.

(3) Empirical Complexity Studies: We acknowledge that Chebyshev interpolation boasts greater efficiency over Bernstein approximation in theory. However, our empirical studies indicate that BernNet and SAF-Bern generally demand less training time compared to ChebNetII and SAF-Cheb, as evidenced in the table below. This could be due to ChebNetII requiring additional computations for the values w.r.t. $(K+1)^2$ Chebyshev nodes.

Average total running time (s).

Q.4 This paper lacks of parameter analysis regarding $\tau, \eta, \epsilon$, $L$ and $K$.

Thanks for your insightful feedback regarding the sensitivity analysis of hyper-parameters in our model. We regret the initial omission of this crucial analysis in our experiments. To address this, we have now conducted a comprehensive analysis of our model's behavior across a wide range of hyper-parameter choices, specifically for $\tau, \eta, \epsilon$, and $L$. More detailed results and analysis have been added in the revision (see Appendix H).

(1) Regarding the parameter $K$, which represents the number of polynomial orders in the spectral filter, we aligned with existing literature and fixed it at 10 in our SAF model. This choice reflects our focus on the novel aspects of SAF rather than on parameters well-explored in previous works.

(2) To provide a clear illustration of our findings, we have included results from two datasets, Texas and Cora, in the following tables as an typical example. As can be observed, our SAF model exhibits robust stability across a broad range of parameter values. For instance, promising performance can be obtained by selecting both $\tau$ and $\eta$ values from {$0.1, 0.2, ..., 1$}. This interval aligns with the parameter tuning strategy we described in Appendix E.3.

(3) For the non-local aggregation layer number $L$, a noticeable decline in model performance is observed when $L$ exceeds 10. This is attributed to the non-local nature of our new graph, which facilitates efficient information exchange between nodes. Exceeding a certain number of layers may potentially lead to oversmoothing, where there is an overemphasis on global information, thus degrading model performance. However, choosing the number of layers within a reasonable range generally ensures consistent and impressive model performance, as verified in Figures 9p-9t of our revised manuscript.

Sensitivity analysis of parameter $\tau$ in node classification accuracy

Sensitivity analysis of parameter $\eta$

Sensitivity analysis of parameter $\epsilon$

Sensitivity analysis of parameter $L$

Q.3 The ablation study should exclude each component.

Thank you for your valuable suggestion to augment our ablation analysis. Your guidance has been instrumental in enhancing the comprehensiveness of our study, and we have added detailed analysis in the revision (see Appendix F.3).

(1) Our SAF framework primarily comprises three modules: "Non-negative Spectral Filtering" (Spec.), "Non-local Spatial Aggregation" (Spat.), and "Node-wise Prediction Amalgamation" (Amal.). We have already tested our SAF without the Spec. module in the "Ablation Study" subsection of Section 6. Additionally, the configuration of SAF w/o Spat. is effectively equivalent to the BernNet model, of which the performance can be observed in Tables 1 and 2.

(2) Following your kind suggestion, we have now included experiments that ablate the Amal. module. We implemented this by removing the attention mechanism and equally blending predictions from different domains. To provide a comprehensive view, all ablation results are presented in the following table. These results illustrate that the omission of any module generally results in a noticeable decrease in performance, affirming the effectiveness of our design. Interestingly, for the Amal. module, some datasets like Cham. and Squi. exhibit only a modest performance decline. This observation aligns with our observation that their optimal attention values are close to an even split, as suggested in Figures 3(b) and 8(a).

Ablation study of SAF framework regarding “Node-wise Prediction Amalgamation” (Amal.), “Non-local Spatial Aggregation” (Spat.) and “Non-negative Spectral Filtering” (Spec.) modules.

Q.1 Previous works on the correlation between spectral and spatial domain graph learning.

Thanks for your insightful comments. We are glad to further clarify our work's position in relation to previous studies on the correlation between spectral and spatial domain graph learning.

(1) In our original submission, we actually have acknowledged these pioneering researches, including but not limited to works [1,2,3], in exploring the congruencies between spectral and spatial GNNs. This discussion is present in the second paragraph of Section 1 and the "Unified Viewpoints for GNNs" subsection of Section 2. Our work, distinct from these previous efforts, represents the first endeavor to delve into the interpretability of spectral GNNs from the spatial domain, examining the theoretical interplay between spectral filtering and spatial aggregation.

(2) Regarding GCNII [4], which utilizes spectral analysis to validate its anti-oversmoothing capability, we regret its omission in our earlier discussion and have now included it in Section 2 (highlighted in blue).

(3) In our experiments, we have compared our SAF framework against relevant models including GNN-LF [1], GNN-HF [1], ADA-UGNN [2], FE-GNN [3], and GCNII [4], as detailed in Tables 1 and 2 of our manuscript. These comparisons demonstrate that SAF significantly outperforms these models (including the two as you kindly mentioned), thereby underscoring our contribution to the existing literature in not only theoretical but also practical terms.

[1] Zhu, Meiqi, et al. "Interpreting and unifying graph neural networks with an optimization framework." WWW, 2021.

[2] Ma, Yao, et al. "A unified view on graph neural networks as graph signal denoising." CIKM, 2021.

[3] Sun, Jiaqi, et al. "Feature expansion for graph neural networks." ICML, 2023.

[4] Chen, Ming, et al. "Simple and deep graph convolutional networks." ICML, 2020.

Q.2 Why the combination of polynomail graph filter and the adapted adjacent also derived from this filter can address its limitation?

Thanks for your insightful comments. We appreciate the opportunity to clarify the capabilities of our SAF framework in addressing the limitations of spectral GNNs.

(1) Most spectral GNNs are limited by their reliance on fixed-order polynomials for graph filter approximation, confining their effective propagation to within $K$ hops and thus restricting long-range dependency capture. Our research, however, has unveiled an intriguing aspect. We discovered that spectral filtering, while performed in the spectral domain, implicitly crafts a non-local new graph in the spatial domain. This new graph, free from the constraints of the original topology, uncovers deeper, previously unobserved node connections. Despite this, domain barriers impede spectral GNNs from exploiting this non-locality existing in the spatial domain. In response, our SAF framework is designed to enhance spectral filtering with auxiliary non-local aggregation. This combination effectively overcomes the truncated polynomials' limitations, enriching long-range dependency capture and graph information exploration.

(2) This concept is extensively discussed in the last paragraph of Section 4.1 of our paper, where we elaborate on the distinct mechanics of the adapted new graph compared to conventional spectral filtering. Moreover, in Section 6, particularly in the "Full-supervised Node Classification" subsection, we provide empirical evidence and analytical insights that demonstrate SAF's superiority over other spectral GNNs, substantiating our methodology.

Dear Reviewer 2DDa,

We are deeply grateful for your time and effort in reviewing our paper. As the discussion period is drawing to a close, we sincerely hope that our rebuttal has carefully addressed each of your comments.

In particular, we have clarified the unique position of our work in relation to prior studies on the correlation between spectral and spatial domain graph learning. Besides, we have elaborated on how our SAF framework overcomes certain limitations of current spectral GNNs. As you kindly suggested, additional experimental results, focusing on ablations and the sensitivity analysis of parameters, are also provided to enable a comprehensive analysis of SAF.

If you have any other comments or questions, we are happy to engage and provide further clarification. Thank you for your invaluable feedback and attention to our submission.

Best regards,

4497Authors

Tables regarding time and space overheads, where local GNNs (BernNet [13] and ChebNet [14]) and global GNNs (SAF, NodeFormer[15], and GloGNN++ [16]) are included for comparison.

Time overheads (s).

Space overheads (MB).

References

[1] Belkin, Mikhail, and Partha Niyogi. "Laplacian eigenmaps for dimensionality reduction and data representation." Neural computation 15.6 (2003): 1373-1396.

[2] Wang, Haorui, et al. "Equivariant and stable positional encoding for more powerful graph neural networks." ICLR, 2022

[3] Dwivedi, Vijay Prakash, et al. "Benchmarking graph neural networks." arXiv preprint arXiv:2003.00982 (2020).

[4] Lim, Derek, et al. "Sign and basis invariant networks for spectral graph representation learning." ICLR, 2023

[5] Kreuzer, Devin, et al. "Rethinking graph transformers with spectral attention." NeurIPS, 2021.

[6] Kim, Jinwoo, et al. "Pure transformers are powerful graph learners." NeurIPS, 2022.

[7] Rampášek, Ladislav, et al. "Recipe for a general, powerful, scalable graph transformer." NeurIPS, 2022.

[8] Liao, Renjie, et al. "Lanczosnet: Multi-scale deep graph convolutional networks." ICLR, 2019.

[9] You, Yuning, et al. "Graph domain adaptation via theory-grounded spectral regularization." ICLR, 2022.

[10] Chang, Heng, et al. "Not all low-pass filters are robust in graph convolutional networks." NeurIPS, 2021.

[11] Bo, Deyu, et al. "Specformer: Spectral graph neural networks meet transformers." ICLR, 2023.

[12] Sun, Jiaqi, et al. "Feature expansion for graph neural networks." ICML, 2023.

[13] He, Mingguo, et al. "Bernnet: Learning arbitrary graph spectral filters via bernstein approximation." NeurIPS, 2021.

[14] He, Mingguo, et al. "Convolutional neural networks on graphs with chebyshev approximation, revisited." NeurIPS, 2022.

[15] Wu, Qitian, et al. "Nodeformer: A scalable graph structure learning transformer for node classification." NeurIPS, 2022.

[16] Li, Xiang, et al. "Finding global homophily in graph neural networks when meeting heterophily." ICML, 2022.