Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies GNN robustness against homophily changes (e.g., whether direct neighborhoods belong to the same class). It proposes a spectral graph filter that only considers even-polynomial signals, so that it’s robust to odd-hop changes.
strengths_and_weaknesses: Strengths

The paper gives clear motivation of why only considering odd-order might tackle homophily changes.
The paper gives theoretical analysis from both spatial and spectral perspectives.

Weaknesses (or questions)

1. Is EvenNet only effective in homophily change?

I think the paper is based on an assumption that most perturbation comes from homophily changes, more specifically, label changes of the direct neighborhood. Based on this assumption, taking even-hop and ignoring odd-hop could increase robustness and loss accuracy. However, this is a very specific type of attack (and from my understanding, people mainly study this to show the weakness of vanilla GCN). So I have the following two questions: is Evennet only effective for homophily changes? What if you also consider some general graph attack, such as random perturbation, a trained attacker? Or more specifically, what if we change the association of label correlation at even-hop (say 2) instead of the direct hop? It would be better if the authors could give an analysis to let people know at which scope the proposed method is effective; 

2. Will ignoring odd-hop affect performance? 

From my understanding of most graph datasets, first-hop neighborhoods contain the most information. If simply ignoring all odd-hop neighbors, will the performance be influenced a lot? Table 3 shows that EvenNet achieves competitive results with many old baselines, but it would be more convincing if the authors could conduct some ablation study, because the proposed approach and baselines could be run in different evaluation settings.

3. Theoretical analysis might not support the claim

Theorem 1 talks about whether an even-order graph filter has lower variation than full-order given different edge homophily. This could not support the author’s claim of “without losing average performance”. If we don’t do graph filtering and only use each node’s own feature the variance is 0, but it doesn't mean this baseline is better than a graph filter.

The result of Theorem 3 is very interesting, however, I could not really get how you estimate L(G), as it should depend on the filter parameter g, which I couldn’t figure out how you get even after reading the appendix. If you have some assumptions about this Theorem, it would be better to clearly state it so people might understand when the conclusion holds.


4. Experiment-wise, it would be better to test on larger-scale and more standard datasets such as OGB. Also, it would be good to show results with real-world distribution shifts instead of only synthetic shifts.
questions: See above
limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work designs a simple and robust GNN model, EvenNet, in the spectral domain. EvenNet discards messages from odd-order neighbors. Authors analyze this method theoretically. In the spatial domain, authors define homophily degree, which reflects the average possibility of deriving a node's label from its k-hop neighbors, and then prove that even-order filter can benefit from a lower variance of homophily degree. In the spectral domain, the author proves that an even-order filter can achieve a lower loss gap between the homophilic training graph and the heterophilic test graph. EvenNet exhibits generalization ability across homophily and robustness to many attacks in experiments. Moreover, it also keeps competitive performance and low time complexity.
strengths_and_weaknesses: Strength:

1. The method is simple but novel.
2. Experiments are persuasive.
3. The paper is well-written.

Weakness

Theoretical analysis is largely based on heuristics. In the spatial domain, whether the homophily degree change represents the effects of homophily change on GNN is doubtful. In the spectral domain, the analysis is based on too many unnatural assumptions like 1-dimensional feature, non-increasing and non-decreasing $\alpha$, and ring. 




questions: Why not use $\phi_{test}\neq\pm\phi_{train}$ in experiments? For example, can we use a setting like $\phi_{test}=0.3, \phi_{train}=0.75$?

limitations: Not related.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes to ignore odd-hop neighbors to improve the robustness of graph neural network. The authors analyze the influence of odd and even-hop neighbors to the graph filters and reveal that using only even-hop neighbors can improve the robustness of spectral graph neural networks. Based on the theoretical findings, the authors propose EvenNet and conduct several experiments to validate the effectiveness of EvenNet.
strengths_and_weaknesses: *Originality & Significance*: Improving the robustness of graph neural networks is of great importance to the community. The proposed solution enjoys lots of theoretical insights from the spectral graph neural networks and the balance theory. However, the motivation is confusing and the empirical evidences may not be sufficient to support the authors’ claims.

*Quality*: Despite of certain theoretical supports for the design of EvenNet. The theoretical analysis tend to put strong assumptions on the underlying graph homophily/heterophily. The empirical analysis might not be sufficient, as several important experiments are missing. See the questions for more details.

*Clarity*: Overall, the paper is well-organized, however, there are several important details are missing, making readers hard to follow.

questions: After the rebuttal, the authors resolve most of my concerns. Thus I raise my ratings to 6.

===========
The motivation of the paper is confusing:
- The EvenNet design seems to be heuristic, which tends to assume the task is binary thus the neighbors of heterophilic neighbors tend to have homophilic to the central nodes. I am not sure why this heuristic is a more general topological information beyond homophily. 

- Furthermore, the theoretical analysis throughout the paper including the synthetic experiments inherent the strong assumption on the problem structure, i.e., binary classification. Under binary classification, incorporating even-hop neighbors is straightforward as shown in Figure 1 by the author, which may weakens both the significance and novelty of the paper.

There are several missing important comparisons and experiments:
- Comparisons between existing spectral GNNs which are also designed to work on both homophily and heterophily GNNs are missing, e.g., Fu et al., 2021[1].
- The paper focuses on a inductive setting and discusses the homophily changes under adversarial attacks. In fact, Chen et al., 2022[5] established the same discussion in this setting under a more ``powerful’’ graph adversarial attack, i.e., Graph Injection Attack (GIA) [2,3,4,5]. More discussions and comparisons are required to distinguish the contributions of the paper, and more importantly, the effectiveness of EvenNet (See more details in the next point).
- In fact, most of existing graph adversarial attacks are limited to small scale graphs [6] in contrast to GIA which works on both small and large scale graphs [4,5], making the evaluations less convincing [4,5,6]. It would strengthen the claims and further improve the impact of the paper if the authors could validate the high robustness of EvenNet in large scale graphs.
- The authors claim the proposed method enjoys cheaper computational overhead than existing robust GNNs, yet did not provide any justifications.

The writing of the paper also misses several important details. Here are few:
- In Theorem 1, how the expectation is taken given the subscript as H and inputs \PI?
- In Line 150, why the regression problem of \alpha and \beta can be seen as linear?
- In Theorem 3, what is the relationship between homophily/heterophily and the non-increasing/non-decreasing \alpha?
- In experiments, how the threshold in GNNGuard is chosen?
- In all tables of the experiments, why are the standard variances are missing?
- How robust are EvenNet under Metattack with different budgets?

References:

[1] Guoji Fu, Peilin Zhao, Yatao Bian. p-Laplacian Based Graph Neural Networks. arXiv 2021.

[2] Wei Jin, Yaxin Li, Han Xu, Yiqi Wang, Shuiwang Ji, Charu Aggarwal, Jiliang Tang. Adversarial Attacks and Defenses on Graphs: A Review, A Tool and Empirical Studies. SIGKDD Explorations 2020.

[3] Lichao Sun, Yingtong Dou, Carl Yang, Ji Wang, Philip S. Yu. Adversarial Attack and Defense on Graph Data: A Survey. arXiv 2020.

[4] Qinkai Zheng, Xu Zou, Yuxiao Dong, Yukuo Cen, Da Yin, Jiarong Xu, Yang Yang, Jie Tang. Graph Robustness Benchmark: Benchmarking the Adversarial Robustness of Graph Machine Learning. NeurIPS 2021 Datasets and Benchmark Track.

[5] Yongqiang Chen, Han Yang, Yonggang Zhang, Kaili Ma, Tongliang Liu, Bo Han, James Cheng. Understanding and Improving Graph Injection Attack by Promoting Unnoticeability. ICLR 2022.

[6] Simon Geisler, Tobias Schmidt, Hakan Şirin, Daniel Zügner, Aleksandar Bojchevski, Stephan Günnemann. Robustness of Graph Neural Networks at Scale. NeurIPS 2021.


limitations: Could not find the corresponding discussion in the paper.
review_title: null

Meta-review: metareview: This paper proposes a simple and effective idea to only use even-order neighbors to improve the robustness and generalization ability of spectral GNNs. It is based on the intuition that a friend's friend is friend, and an enemy's enemy is also friend, thus only using even-order neighbors improves the generalization across different homophily/heterophily levels. Considering that spectral GNNs' expressive power have been shown to easily saturate recently, analyzing their generalization power is of great importance and is a natural next step. All the reviewers agree on the value of the paper. However, they also point out several issues, such as concerns on the theoretical analysis. I encourage the authors to further polish the paper and improve the theoretical analysis in the camera ready version.
confidence: Less certain
Decision: Accept