Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors characterize the conditions and provide supporting theoretical understanding and empirical observations of the conditions that GCNs can achieve strong performance on heterophilous graphs.

main_review: Strength:

The authors provide some valuable arguments about the performance of GCN on heterophilous graphs and verify the claims with some empirical results.

Weakness&Advice:

1. In the last line of page 2, where is $X$ in the equation?

2. The results in table 1 is not consistent with my personal experience even with the hyperparameter tuning range provided in appendix D. Could you please provide more details about the settings for table 1?

3. Kenta’s work does not drop non-linearity in their analysis.

4.  Could you please clarify the significance of theorem 1? What is its relation with heterophily and homophily in definition 1?

5. Why do you use cosine similarity to define inter-class distance? What is its advantages over other metrics?

6. Font size in figure 5 is too small. The dark blue background make it hard to read the value on it.

7. The writing of this paper is not satisfying. I suggest the authors to cut the long paragraphs into smaller pieces, e.g. section 3.3.1, so that it is more reader friendly. It’s better to re-organize the paper, especially for the content after section 3.1.

8. Can your theoretical analysis on CSBM generalize to multiple classes or to more general graphs.
summary_of_the_review: The novelty and significance are OK but the writing is not satisfactory. I'll consider raising my score if the authors can address my concerns properly.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper revisited the performance of GCN on graph with heterophily and provide negative evidence that heterophily does not always result in the poor performance of GCN, which contradicts with the assumptions/observations of many previous papers. They demonstrated that the GCN embeddings are still label-distinguishable on a special type of graphs with assumptions that the nodes with same labels have the same node feature distribution as well as the same neighborhood label distributions. They theoretically analyzed the case of CSBM model with two classes, and also empirically investigated on synthetic/real-world graphs with multiple classes. The conclusion is that GCNs can achieve good performance on heterophilous graphs under certain conditions. 
main_review: Strength:
1.	It provides a deeper insights into the heterophily problem and help us understand the GCNs’ performance.
2.	It also designs a new cross-class neighborhood similarity metric to help explain the performance of GCN on various graphs (although it is not perfect).
3.	The writing is generally clear.


Weakness and Questions:
1.	The analysis is only limited to GCNs, while the paper title is too general (GNNs). Not very 
2.	One concern is that the performance of GCN on Chameleon and Squirrel (Table1) differs a lot from the one reported in other papers (e.g. Geom-GCN (Pei et al. 2020), H2GNN (Zhu et al. 2020)). It seems the settings are the same as Pei et al. 2020, why is the result on these two datasets so different (2 to 3 times different)? Generally, I do not think the hyperprameter tunning should impact so much. Could the authors explain more details about it? In fact I also run some experiments on those datasets before and I cannot get those high numbers either.
3.	The cross-class neighborhood similarity metric is intuitive and a good idea. However, it lacks of a direct theoretic connection to GCNs’ performance. Same as the heterophily metric, I do not think it can completely decide the GCNs’ performance, because the node feature distribution is also important here.  In fact, the assumptions in Theorem 1 are quite strong. If the nodes with the same label are sampled from the same feature distribution, it means generally MLP can also have a good performance. When this assumption does not meet, the analysis will become very complex. That is why I think Figure5 may be not enough to explain everything (but it is still interesting to see this empirical result). 
4.	Although Theorem 1 seems correct to me, I have a question here. Assume we have a separate node with 0 neighbors, that means the upper bound here is 0. It is obviously not true. So, how to explain this exception?

summary_of_the_review: The paper provides a new perspective of heterophily and GCNs, but there remains some concerns both in the theoretic part and in the experiments.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper revisits the common belief in prior works, “GCNs require strong homophily assumption.” The paper claims that even under low homophily, if the nodes of each label have distinguishable neighbor label distributions, GCNs can learn distinguishable node representations. To prove this claim, the authors (1) show that GCNs outperform representative baselines on two heterophilous graphs, (2) theoretically analyze the relation between homophily and decision boundary on CSBM with two classes, (3) conduct experiments on synthetic benchmarks created by distinct/random edge addition, and (4) analyze real-world benchmarks qualitatively and quantitatively with the lens of (3).

main_review: This work proposes a novel perspective on learning node representations under various homophily. Considering how recent GNN papers on heterophily treat GCNs (as the weakest baseline), we can say that empirical results by this paper are groundbreaking. However, this paper has several flaws which should be fixed/justified before publication.

First, the Table 1 results are not convincing. We now agree that GCNs can learn good representations under some conditions on neighbor label distributions. However, this cannot justify how GCNs outperform other models. Does it not hold for other specialized architectures (H2GCN, CPGNN, GRRGNN)? Or, how about simple other baselines such as GraphSAGE and GAT?

Related to the first point, is there any reason for GCNs’ supremacy other than hyperparameter tuning? I have read Appendix D.4, and it is a standard procedure with reasonable computational budgets. Does it mean that other related works were doing something wrong? What is the magic here?

Second, the edge addition algorithm does not control the degree distribution; it monotonically increases the degree of nodes. In Theorem 1, the probability is bounded with singular value, feature dimension, and degree. However, the edge addition algorithm adds edges, and the average degree always increases; thus, whole experiments in Figure 3 do not control the key variate. Does it contribute to getting over-optimistic results for a high degree (or low homophily) regime? 

Third, the two-class graph results seem to be insufficient for the main claim. Theorem 2 is about the relation between decision boundary and degree, $p$, and $q$, and this is just one example of a graph with distinguishable neighbor label patterns. Can we say that Theorem 2 *theoretically supports* the paper’s argument? This can work just because predicting one can be reducible to predicting the other in a two-class problem, might not because of the distinguishability. 

Fourth, the degree distribution $\mathcal{D}_c$ for edge addition is clearly distinguishable to each other, but only one specific instance has been experimented with (i.e., having neighbors of two other classes other than itself). Is there any specific reason to experiment with one pattern across all datasets? Can we confirm that these empirical results generalize to various neighbor label distributions? For extreme cases, how does the model perform if the node connects to a single different label, or all labels except for itself (with the different number of classes)?

summary_of_the_review: The authors discuss the interesting question (in the title) and their answers in theoretical and empirical ways. The paper has merits but also has the following weaknesses:

- Table 1 and the following description cannot justify how GCNs outperform other models.
- The edge addition algorithm does not control the degrees, which is the core control variate for the experiments.
- The two-class graph results seem to be insufficient for the main claim.
- Only one specific instance of the degree distribution $\mathcal{D}_c$ for edge addition is used for the experiments.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper discusses the relationships between the performance of GNNs for semi-supervised node-classification taaks and label-homophily/heterophily in the underlying graph structure. 
The authors show that the classic CGN architecture can perform well on certain label heterophilic graphs -- which they argue is disputed heavily in the literature -- and provide a theoretical discussion on when a good performance for CGN on such heterophilic graphs is possible. 
main_review: The paper aims to provide a more careful assessment about the role of label-homophily for graph neural network. Given the research activity  in this area recently, I think this is an interesting topic. As the authors outline, there appears to be indeed some "folklore knowledge" about label-homophily present in the literature which is probably not entirely accurate. Establishing a more precise understanding on when CGNs can work well, and when not is indeed useful.

However, what I find problematic is that the authors claim that the current understanding in the literature is that homophily would be a necessity for CGN to perform well (i.e., a necessary condition for CGNs to work). This feels to much like a straw man argument for me; I think in most cases the argument is that heterophily can be problematic for CGNs -- and indeed the authors confirm this as well: "bad homophily" does indeed exist, as they say. The claim that there was some kind of consensus that CGNs can never perform well in label-heterophilic graphs is too far reaching to me. 
The authors have to be very careful here to not throw out the baby with the bathwater. There is merit in what the authors do: clarifying when CGNs can perform well (even under heterophily); however, that does not mean that there are no issues with heterophilic graphs in general. I strongly suggest the authors reconsider their phrasing in certain areas. 

In a similar vein, I believe the paper would benefit from a more precise treatment of certain aspects of homophily as well. Basically, the authors consider a homophily definition at the level of node-labels; they also assume that there is a tight correlation between the node labels and the underlying node features; so a label-homophily would translate into a feature homophily (or heterophily) as well. I think some more in depth discussion in this context about the relation between the correlation of features of neighbors and labels would be helpful. 

At a high level, CGNs act by aggregating (averaging) the features of the node neighbors. If those features in the neighborhood are correlated (or indeed anti-correlated) to the target node label, then CGNs will be able to pick out the correct relation. This is true for fully homophilic graphs -- in which there is a strong positive correlation between the neighborhood features and the true node label -- and, e.g., for the bipartite example the authors present, in which case there is a strong anti-correlation (which works for prediction as well). However, extending the bipartite examples to multiple classes is already much more complicated: it may well happen that there is no clear label-to-feature correspondence any more that can be exploited. Some aspects of this are already alluded to in the discussion on the embeddings -- but I believe need to be more clearly articulated.

Some further technical comments:

The CGN architecture described by the authors has no self-embedding component; this is an important point as it leads to "no mixing" behavior of the features / labels the authors describe for the toy example. Most convolutional architectures of GNNs have however at least some diagonal weights / self-embeddings -- which will inevitably lead to a stronger mixing between features of nodes of different classes. Again it is the correlation structure between node-labels (across the graph) and node-features (features to labels and features across the graph) that will come into play here and self-loops may help or hinder here.

While the probabilistic analysis provided with the SBMs is clearly better than simply assuming constant features; performing the analysis in expectation is in this case basically the same as the deterministic construction discussed at the end of page 3, augmented with a bound on the deviation bound (which is only available here because of the bounded feature assumption it seems)

There are at least some problematic aspects with this analysis:
1) the SBM and alike models are not a good model for sparse graphs, as they exhibit a graphon like structure and lead to dense graphs -- which is problematic as we often consider sparse graphs in practise; this limitation needs to be at least discussed I think.

2) the assumption that the every node with the same class label has the same feature distribution (thus providing a perfect probabilistic coupling between labels and features) and the same neighbor label distribution and that each feature is indeed independent seems very unrealistic. This would lead basically to a problem in which a single inspection of the neighborhood suffices -- there is (almost) no graph structure necessary here really. 

3) Dropping the nonlinearity, while done in practice, is clearly another strong simplification which would merit some more discussion I think.

Finally, the numerical experiments paint a much richer picture than the theoretical analysis and indeed the introduction of the paper. Some of these aspects could also be discussed in the theoretical parts (neighborhood similarity and correlation structure) -- which would lead to a more balanced picture. As it stands the introduction and theory parts make the paper feel a bit one-sides (to exaggerate: "heterophily is not a problem"); whereas in the end the conclusion is much more nuanced. I think such a more nuanced appraisal of heterophily/homophily is useful throughout.

Minor comments
p.2 last line -- X is never defined, instead H and H' are used as input/output. Please correct.


summary_of_the_review: Overall I see the paper slightly above the line, provided some of the above points are addressed (I think this is possible).

The paper should be improved with respect to the following points (see above for more detailed suggestions and comments)
a) provide a more nuanced appraisal of literature and the role of homophily/heterophiliy
b) discuss the roles of the correlation structure between node labels and features more clearly
c) discuss the role of self-loops/ego embedding in mixing information from different classes
d) provide a more rigorous discussion on the assumptions and shortcomings of the theoretical analysis and the SBM model.
review_title: null

Meta-review: Heterophily is known to degrade the performance of graph neural networks. This paper explores whether, for graph convolutional networks (GCNs), this is a general phenomenon, or if there are some circumstances under which a GCN can still perform well in a heterophilous setting. This paper characterizes one such setting under a contextual stochastic block model (CSBM) distribution with two classes (generalized in the appendix to multiple classes). The main takeaway is that there are indeed scenarios where a GCN can be expected to perform well, even under heterophilic neighborhoods.

There are limitations, and the reviewers have been fairly thorough in pointing these out: the analysis is specific to GCNs under CSBM, and there are a number of assumptions on the node label/feature/neighborhood distributions. The non-linear operations in the GCN have also been dropped. Even still, the reviewers were generally satisfied that the experiments backed up the claims in this specific scenario.

There is still quite a bit more to do in order to make this a more general result. Essentially, this paper shows that heterophily is not always a problem. One reviewer has stated that it is not always considered a problem anyway, but at least this paper outlines a specific scenario in which this is theoretically true. However, there is still a large space of “bad” heterophily, and this paper leaves open what these are, and how to deal with them. It is also possible that there are other “good” scenarios as well that are unexplored.

Still, in the narrow scope under which the analysis lies, the paper is clear and accomplishes what it sets out to do. I would encourage the authors to ensure that the paper incorporates the suggestions of the reviewers, particularly with regard to scope, to ensure that the paper is properly grounded in its claims.

All reviewers leaned towards the side of acceptance, except one who did not engage in post-review discussion. After reading over their review, and the subsequent response, I am satisfied that their concerns have been adequately addressed.
Decision: Accept (Poster)