Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors analyze the relation between GNN robustness against attacks with heterophily and propose a method to improve GNN robustness by separating the aggregators of ego- and neighbor-embeddings.
main_review: In this paper, the authors analyze the relation between GNN robustness against attacks with heterophily and propose a method to improve GNN robustness by separating the aggregators of ego- and neighbor-embeddings. In general, the authors focus on an interesting and novel problem and the paper is of good structure. However, there are some issues the authors need to address.

My primary concern is with the evaluation. First, no baseline methods on improving GNN robustness or defending attacks are provided. The authors only show the performance gap between before- and after-attack on different GNNs that integrate the proposed technique. However, it is unclear how much the results are significant without comparing the baseline methods. I suggest the authors either add several baselines to compare or justify why no baseline is applicable. Meanwhile, I suggest the authors to compare the GNN models that integrate the proposed technique with the vanilla versions to examine the results without attacking so that the readers can understand how the general performance can be affected by separating the ego-aggregator.

The novelty of the proposed method also needs to be justified. Using stacked ego-embeddings for prediction has been applied before to solve issues like oversmoothing. I suggest the authors to further justify why the proposed approach is novel and significant.
summary_of_the_review: Strength:
+ Focusing on an interesting problem
+ The paper is of good structure

Weakness:
- Incompelete evaluation
- The novelty needs to be further justified
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the relationship between graph heterophily and robustness of GNNs. The authors claim that effective structural attacks on GNNs for homophilious graphs lead to increased heterophily level, while for heterophilious graphs they alter the homophily level contingent on node degrees. The paper shows that a heterophily-inspired design for GNN, separate aggregators for ego- and neighbor-embeddings, could improve the robustness of several GNN architectures.
main_review: This work studies the relation between graph heterophily and the robustness of GNNs and theoretically show that effective structural attacks on GNNs for homophilious graphs lead to increased heterophily level, while for heterophilious graphs they alter the homophily level contingent on node degrees under some specific assumptions. 

Despite this, the paper is not particularly novel. The theoretical results are derived under some specific assumptions on graphs and GNN layers, which may not be appliable to real-world graphs. 
Theorem 3 cannot support the claims that the heterophily-inspired design (i.e. separate aggregators for ego- and neighbor-embeddings) could improve the robustness of GNNs because the GNN layer analyzed in the theorem is significantly different with the heterophily-inspired design. 
Furthermore, experiments are conducted on small datasets and the experimental results cannot validate whether the theoretical claims can be generalized to large real-world graphs, which is an important aspect given that the theoretical claims are based on specific assumptions about graphs.


 
## Strength

1. The paper is well written and is easy to follow.
2. The authors have studied an important open problem in deep graph learning community.


## Weakness

1.  The paper is limited in novelty: while the paper investigates the relation between graph heterophily and the robustness of GNN and show that several heterophily-inspired GNNs work more robust to GCN and GAT, there is no new methodology proposed in the paper.
2.  This paper is constrained to specific target attacks (i.e. CM-type attacks) and linear GNN layers, which may not be applicable to most GNN architectures with nonlinearity and other types of attacks. 
In addition, they are derived for specific graphs with fixed degrees for every node and specific node features, which may not generalize to real-world graphs.
3.   Theorem 3 does not support their claims on the effectiveness of the heterophily-inspired design (i.e. separate aggregator for ego- and neighbor embeddings). Theorem 3 shows that the GNN layer $f = ((1 - \alpha)\bar{\mathbf A} + \alpha\mathbf {I})\mathbf{X}\mathbf {W}$ is more robust than the GNN layer $f_s = \bar{\mathbf  A_s}\mathbf {X}\mathbf {W}$ to CM-type attack on a node. The GNN layer f follows the message passing scheme of APPNP (with K=1) and GPRGNN (with K=1, $\gamma_0=\alpha$, $\gamma_1=1-\alpha$), which indicates that Theorem 3 is applicable to APPNP and GPRGNN under some assumptions. However, it is not clear whether it could work for the heterophily-inspired design since the architectures of ANNPN and GPRGNN are significantly different toi the heterophily-inspired design.
4.  It would be nice to include APPNP in the experiments since the architecture of APPNP is very close to the GNN layer analyzed in Theorem 3.
5.  The datasets used in the experiment are small, say, around 2k nodes, and it is not clear whether the results can be extended to large real-world graphs. It would be great to include experiments on larger datasets to validate their theoretical claims,  especially when their claims were made upon specific assumptions. Moreover, the homophily level h of FB100 is 0.531 (> 0.5), which does not meet the definition of heterophilious graphs ($h <<1/ |Y|$) in the paper. Other heterophilious benchmark datasets with lower homophily levels may be more helpful for validating the theoretical claims for heterophilious graphs.
6.   There is no empirical study for validating the claim of Theorem 2 that the type (homophily or heterophily) of attack on a node for heterophilious graph depends on the node degree.

## Minor comments:
1. Table 7 in Appendix E.1 shows that GAT and GCN outperform most heterophily-inspired GNNs (e.g. H2GCN, GPRGNN, FAGCN) on the original (clean) FB100 and Snap datasets. Can you give some insights on why GAT and GCN worked better than heterophily-inspired GNNs on these heterophilious graphs?

summary_of_the_review: This paper studies an interesting open problem in deep graph learning. However, it has limited novelty, and theoretical results do not support some of their claims.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors present a study on the robustness on GNNs on homophilic and heterophilic datasets. The authors first show in a stylized theoretical setting that GNNs with a *heterophilic design* (separate aggregation of ego- and neighborhood representations) should show increased robustness against structure perturbations. Then, they follow up with an experimental study where they compare homophily-based GNNs with GNNs following a heterophilic design on both homophilic and heterophilic datasets. In addition, the authors augment three GNN models with the SVD preprocessing by [Entezari et al. 2020] in order to improve robustness. The authors study both empirical as well as certifiable robustness (via randomized smoothing). In general, GNNs with heterophilic design show higher empirical and certifiable robustness across datasets.
main_review: ### Strengths
* The paper has a thorough and well-designed experimental study.
* The paper studies empirical *and* certifiable robustness, which are both interesting and important.
* The authors compare a broad range of different models.

### Weaknesses
* The paper does not propose a new method.
* The authors only combine the SVD preprocessing with two of the models studied in this work.
* The paper references [Geisler et al. 2020] but does not compare to their proposed model.

### Detailed comments
Some remarks and questions:

**SVD preprocessing**
* Why are only two GNNs combined with SVD? CPGNN is the most robust non-vaccinated GNN, so adding SVD to it might lead to more robustness than e.g., GraphSage-SVD. 
* The SVD preprocessing effectively acts as a low-pass filter and could "destroy" some of the high-frequency heterophily information in FB100 and Snap. Could this be a reason why the SVD-augmentation adds much less robustness on these datasets?
* On a related note, the SVD preprocessing does in general not preserve sparsity of the graph. Thus, the 1- and 2-hop neighborhoods of the nodes might become very large and could lead to oversmoothing. Is this an issue in the present study? An alternative could be to use GDC [Klicpera et al. 2019] preprocessing, which is also a low-pass filter but preserves sparsity.

**Robustness in homophily-based GNNs.** While the authors' arguments for increasing robustness via heterophily-adjusted GNNs makes sense to me, [Geisler et al. 2020] achieve comparable or larger certified performance (e.g., as measured by AC) on Cora and Citeseer, while not adhering to the heterophily design proposed in this work. Instead, the method "doubles down" on the homophily design by using GDC [Klicpera et al. 2019] preprocessing and an aggregation function designed to be not affected by outliers. Are the strategies in the present work and [Geisler et al. 2020] alternative solutions to increase robustness in homophily networks? A discussion on this would be very interesting in my view. 

**Benchmark results.** In my view the benchmark results section would benefit from also showing the clean performance of the models for the untargeted attacks. For example by having an analogous to Fig. 1 for untargeted attacks or by swapping the error bars in Table 3 with the change in accuracy compared to the clean performance (the error bars should then of course be provided in the appendix). 

**Heterophilic structure attacks (Q1) (side remark).** The results for the homophilic datasets in Table 2 seem to corroborate the findings presented in [[Zügner et al. 2020](https://dl.acm.org/doi/10.1145/3394520)]  and [[Zügner and Günnemann 2019](https://openreview.net/pdf?id=Bylnx209YX)] (which is good to see), and the results on heterophilic datasets are a valuable and interesting addition.
summary_of_the_review: In summary, I appreciate the thorough experimental study in the paper and believe that – even though the paper does not propose a new method – the findings have relevant implications for GNN design choices. There are some additional experiments and discussions I would be interested to see (see main review). Overall, I'm not opposed acceptance currently.

After reading the authors' response to my review I increase my score.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper investigates the change of the degree of homophily under adversarial perturbation of graphs from both theoretical and empirical points of view. In theory, this paper proves under simplified settings, for homophily graphs, the attack will increase the level of heterophily, and for heterophily graphs, this change will depend on the degree. In practice, this paper advocates a design principle of GNNs that separate aggregators for ego- and neighbor-embeddings.
main_review: Pros:
- The writing of this paper is very clean and easy to read.
- The paper focuses on a quite interesting problem, i.e., the connection between the adversarial attack on the graph and the change of heterophily.
Cons:
- The major concern is the novelty and significance of this paper:
    1. The main observation comes from previous work (Wu et al. 2019; Jin et al. 2020a) as mentioned in the paper. And the main contribution from the theoretical view, as the authors claimed, is the first formalization of the connection. However, the theory is rather weak as both the graph structure and the used model are simplified, i.e., regular graph with very simple node features plus linear GNN.
    2. The design principle mentioned in the paper has already been proposed by previous works, e.g., GraphSAGE, and the connection between this principle and the aforementioned theory results is vague.


summary_of_the_review: This paper aims to investigate an interesting question about the relationship between robustness and heterophily of graphs, however, the novelty and significance of both theory and empirical results are not clear.
review_title: null

Meta-review: This work studies the relation between graph heterophily and the robustness of GNNs and theoretically shows that effective structural attacks on GNNs for homophilous graphs lead to increased heterophily level, while for heterophils graphs they alter the homophily level contingent on node degrees under some specific assumptions.

Overall, the findings in the paper are interesting and can be useful for other researchers trying to improve GNNs' robustness on homophilic and heterophilic datasets. After the discussion and rebuttal, the main concerns are: 
- while the paper has shown some interesting observations, no new methodology was proposed based on these findings. 
- The authors have attempted to relax assumptions and justified their setup on experiments, however the explanations are still limited. For example, Theorem 1 does not allow attention mechanism, different choices of aggregator, skip-connection, and more GNN layers.
Decision: Reject