Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work tries to study the robustness of GCNs under structural perturbations from the perspective of graph spectrum, which for me is interesting. In theory, they proved that the low-frequency components can be more robust against structural perturbations if their eigenvalues fall into a robust interval. For algorithm design, they developed a regularized learning framework that combines a regular GCN-based objective and a low-frequency regularization term, named GCN-LFR. Finally, the authors tested the capability of GCN-LFR in resisting adversarial attacks on several benchmark datasets.
main_review: Strengths: 

The idea to bridge the gap between the spectral analysis and the robustness of GCNs under structural perturbations is interesting. 

Weakness:

(1) The reason why alternative training is better than joint training is not clearly explained. I am curious about the influence of parameter sharing used for two channels (GCN and LFR). 

(2) It is not clear to me whether the enhanced robustness shown in experiments is caused by the model’s two-channel cooperation architecture or exactly the functionality of LFR. The threshold value to select the top-k low-frequency eigenvectors is of high importance. 

(3) How is the scalability of the proposed method? Although authors provided a complexity analysis of GCN-LFR, more empirical verifications on one/two large-scale graph datasets are required. My initial impression of LFR is that it may need a huge computation burden. 

Major points: 

(1) In Figure 1, the authors concluded that “low-frequency components (far left) tend to be more robust in comparison with high-frequency ones (far right)”, which seems to be the case, intuitively. However, I do not feel confident about this conclusion since the ‘rate of change’ (over eigenvalues before & after perturbation), which can be more suitable and fair, is not clearly illustrated. 

(2) I am curious about one issue: Do the high-frequency components also play a role in affecting the robustness of GCNs? Some discussions or empirical studies could help readers better understand the key ingredients towards how to investigate GCN’s robustness analysis from a spectrum way.

(3) More experimental verifications on large-scale graph benchmark datasets, for example, OGB, are required to further demonstrate the potential of the proposed method. 

limitations_and_societal_impact: Yes, the authors mentioned the limitations in the conclusion and societal impacts in the Appendix.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Graph convolutional networks are volunerable to adversarial attacks.  As commonly recognized by researchers,  low-frequency components of GCNs are more robust than high-frequency parts of GCNs. However, the relationship between graph spectrum and robustness of GCN is not well studied. This paper theoretically proposes the robust interval of low-frequency components and regularizes the low-frequency components of GCNS within the robust interval through an auxiliary neural network. In this way,  the robustness of a GCN is enhanced.
main_review: Originality:  this paper bridges the gap between the spectrum analysis and the robustness of GCNs under structural perturbations. The depth of this paper is satisfied. The authors not only studied one-edge perturbation but also considered the multi-edge non-targeted perturbation.

Quality: the proposed method is technically sound. The experimental results support the proposed method. Its performance is evidently higher than baseline method. However, the chosen datasets are limited to homophily graph datasets. For these datasets, low-frequency components are more useful than high-frequency components. How well the proposed method suit for non-homophily datasets [*] should be further studied. 
[*] New Benchmarks for Learning on Non-Homophilous Graphs

Clarity: the connection between the proposed robust frequency interval and the proposed method is weak and not well clarified. The authors should clarify whether the parameters of F are constrained within the robust interval during training.
Besides, the authors should clarify the inference procedure of the proposed framework.

Significance: this paper is a first vulnerability study between the graph spectrum and the robustness behavior of GCNs. It theoretically shows that not all low-pass filters are robust in graph convolutional networks. 

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors introduce a method to improve the robustness of graph neural networks (GNNs). Specifically, the method performs robust training to defend against structure poisoning attacks. The algorithm learns low-pass filter coefficients $\mathbf{F}$. A GCN which uses this low-pass filter as the graph convolution matrix shares weights with a standard GCN during training. The authors compare results on a set of established datasets and attacks.
main_review: Strengths:
* The authors report strong robustness results across datasets and attacks.
* The theoretical analysis is insightful.
* The presentation of the paper is good and clear.

Weaknesses:
* The ablation study is weak and does not sufficiently support the claim that learning the filter weights $\mathbf{F}$ is better than the model where the eigenvalues are used (more in detailed comments).
* The complexity analysis is misleading, showing $O(ckN)$ where it is actually $O(cN^2)$ (more in detailed comments).  
* The clean accuracy of the method is quite consistently lower than the original accuracy. 

Detailed comments:

* Since the graph convolution matrix multiplication for M_LFR is no longer sparse, what effect does this have on the scalability of the method?
* In the Appendix, the authors state that the number $k$ of low frequency components considered is $0.25 N$. With this, the complexity to compute the top-$k$ eigenpairs is $O(cN^2)$. This is a major scalability limitation and should be addressed in the main text. 
* Are predictions of the low frequency GCN used at inference time? If yes, this means that the method cannot be used in an inductive fashion on new nodes at inference time.
* It seems like the method is also well suitable for evasion attacks. How does the method defend against these?
* Figure 3 (right) does not support the claim that "GCN-LFR achieves substantially better validation accuracy than that of GCN-LFRFix". The scale is too coarse to see much difference and there is quite some fluctuation in the curves.
* Figure 3 (right) also does not support the claim that "GCN-LFR achieves competitive performance against GCN", since it only shows the validation accuracy. Also, this is just a single run on one dataset.
* How does GCN-LRF_fix compare to GCN-LRF in a proper tabular comparison on multiple datasets? This is crucial to determine the usefulness learning the filter over keeping it fixed, and Figure 3 does not answer this as stated above.
* Similarly, Figure 4 (left) is not suited to draw general conclusions such as "GCN-LFR_Alter achieves better training and validation performance compared with GCN-LFRJoint". As above, please run a proper comparison on multiple splits and datasets.
* The results in Table 1 for GNNGuard seem to be substantially weaker than reported in Table 1 of the original paper. For example, for Citeseer they report 72.0% robustness after attack and 72.1% clean accuracy. This would correspond to an accurracy of 99.86% in the scale reported by the authors. What is the reason for this? 
* Table 4 seems to suggest that GCN-LFR has lower accuracy on average. On how many splits are these results computed? What are the confidence intervals? 
limitations_and_societal_impact: There is no broader impact statement in the main text of the paper. While the authors have put it into the appendix, this practice is not fair to other authors who sacrifice precious space in the main text of the paper to have the broader impact statement, as demanded by the NeurIPS guidelines.
review_title: null

Meta-review: All reviewers feel the paper is  on the borderline but leaning towards accept. The meta-reviewer read the paper and feel the insight obtained from this paper is interesting. Therefore, the meat-reviewer decides to be conformal with the rest reviewers and suggest an acceptance of this submission. 
Decision: Accept (Poster)