Is Homophily a Necessity for Graph Neural Networks?
Authors: Yao Ma
Xiaorui Liu
Neil Shah
Jiliang Tang
Venue: ICLR 2022 Poster (2022)

Abstract: Graph neural networks (GNNs) have shown great prowess in learning representations suitable for numerous graph-based machine learning tasks. When applied to semi-supervised node classification,  GNNs are widely believed to work well due to the homophily assumption (``like attracts like''), and fail to generalize to heterophilous graphs where dissimilar nodes connect. Recent works design new architectures to overcome such heterophily-related limitations, citing poor baseline performance and new architecture improvements on a few heterophilous graph benchmark datasets as evidence for this notion. In our experiments, we empirically find that standard graph convolutional networks (GCNs) can actually achieve better performance than such carefully designed methods on some commonly used heterophilous graphs. This motivates us to reconsider whether homophily is truly necessary for good GNN performance.  We find that this claim is not quite true, and in fact, GCNs can achieve strong performance on heterophilous graphs under certain conditions. Our work carefully characterizes these conditions and provides supporting theoretical understanding and empirical observations.  Finally, we examine existing heterophilous graphs benchmarks and reconcile how the GCN (under)performs on them based on this understanding.

Published as a conference paper at ICLR 2022
Is HOMOPHILY A NECESSITY FOR GRAPH NEURAL NETWORKS?
Yao Ma
Xiaorui Liu Michigan State University xi Maorriii (msu. edu
New Jersey Institute of Technology yao. mw@nnjnittt...m. edu
Neil Shah
Jiliang Tang Michigan State University t Langjil jamm@iimmmu.. edu
Snap Inc.
nshahhanap.oo com
ABSTRACT
Graph neural networks (GNNs) have shown great prowess in learning representa- tions suitable for numerous graph-based machine learning tasks. When applied to semi-supervised node classification, GNNs are widely believed to work well due to the homophily assumption ("like attracts like"), and fail to generalize to het- erophilous graphs where dissimilar nodes connect. Recent works have designed new architectures to overcome such heterophily-relatee limitations. However, we empirically find that standard graph convolutional networks (GCNs) actually achieve strong performance on some commonly used heterophilous graphs. This motivates us to reconsider whether homophily is truly necessary for good GNN performance. We find that this claim is not quite accurate, and certain types of "good" heterophily exist, under which GCNs can achieve strong performance. Our work carefully characterizes the implications of different heterophily condi- tions, and provides supporting thcoretical understanding and empirical observa- tions. Finally, we examine existing heterophilous graphs benchmarks and recon- cile how the GCN (under)performs on them based on this understanding.
INTRODUCTION
Graph neural networks (GNNs) are prominent approach for learning represen- tations for graph structured data. Thanks to their great capacity in jointly lever- aging attribute and graph structure information, they have been widely adopted to promote improvements for numerous graph-related learning tasks (Kipf and Welling, 2016; Hamilton al., 2017; Ying et al., 2018; Fan et al., 2019; Zit- nik et al., 2018), especially centered around node representation learning and semi-supervised node classification (SSNC). GNNs learn node representations by recursive neighborhood aggregation process, where each node aggregates and transforms features from its neighbors. The node representations can then be utilized for downstream node classification or regression tasks. Due this neighborhood aggregation mechanism, several existing works posit that many GNNs implicitly assume strong homophily and homophily is critical for GNNs achieve strong performance on SSNC (Zhu et al., 2020b;a; Chien al., 2021; Maurya et al., 2021; Halcrow et al., 2020; Lim et al., 2021). In general, homophily describes the phenomenon that nodes tend connect with "similar" or "alike" others. Homophily is observed in a wide range of real-world graphs including friendship networks (McPherson et al., 2001), po- litical networks (Gerber et al., 2013; Newman, 2018), citation networks (Ciotti et al., 2016) and more. Under the homophily assumption, through the aggregation process, a node's representation is "smoothed" via its neighbors' representations. since each node is able to receive additional infor- mation from neighboring nodes, which are likely to share the same label. Several recent works (Zhu et al., 2020b;a) claim that GNNs are implicitly (or explicitly) designed with homophily in mind, are not suitable for graphs exhibiting heterophily, where connected nodes are prone to have different properties or labels, e.g dating networks or molecular networks (Zhu et al., 2020b). Such works accordingly design and modify new architectures and demonstrate outperformance over other GNN models on several heterophilous graphs.
Figure 1: A het- crophilous graph on which GCN achieves perfect performance.

---

Published as a conference paper at ICLR 2022
Present work. In our work, we empirically find that the graph convolutional network (GCN) Kipf and Welling (2016), a fundamental, representative GNN model (which we focus on in this work) is actually able to outperform such heterophily-speciife models on some heterophilous graphs after careful hyperparameter tuning. This motivates us to reconsider the popular notion in the literature that GNNs exhibit a homophilous inductive bias, and more specifically that strong homophily is cru- cial to strong GNN performance. Counter to this idea, we find that GCN model has the potential to work well for heterophilous graphs under suitable conditions. We demonstrate intuition with the fol- lowing toy example: Consider the perfectly heterophilous graph (with all inter-class edges) shown in Figure 1, where the color indicates the node label. Blue-labeled and orange-labeled nodes are asso- ciated with the scalar feature O and 1, respectively. If we consider a single-layer GCN by performing an averaging feature aggregation over all neighboring nodes, it is clear that all blue nodes will have a representation of 1, while the orange nodes will have that of Additional layers/aggregations will continue to alternate the features between the two types of nodes. Regardless of the number of layers, the two classes can still be perfectly separated. In this toy example, each blue (orange) node only connects orange (blue) nodes, and all blue (orange) nodes share similar neighborhood patterns in terms of their neighbors' label/feature distributions.
Our work elucidates this intuition and extends it to a more general case: put simply, given a (ho- mophilous or heterophilous) graph, GCN has the potential to achieve good performance if nodes with the same label share similar neighborhood patterns. We theoretically support this argument by investigating the learned node embeddings from the GCN model. We find that homophilous graphs always satisfy such assumptions, which explains why GCN typically works well for them. On other hand, there exist both "good" and "bad" heterophily, and GCNs can actually achieve strong performance for "good" heterophily settings while they usually fail on "bad" heterophily settings. Our work characterizes these settings, and provides new perspective and solid step towards deeper understanding for heterophilous graphs. In short:
Our contributions. (1) We reveal that strong homophily is not a necessary assumption for the GCN model. The GCN model can perform well over some heterophilous graphs under certain condi- tions. (2) We carefully characterize these conditions and provide theoretical understandings on how GCNs can achieve good SSNC performance under these conditions by investigating their embed- ding learning process. (3) We carefully investigate commonly used homophilous and heterophilous benchmarks and reason about GCN's performs on them utilizing our theoretical understanding.
2 PRELIMINARIES
Let 9 = [V denote graph, where V and & are the sets of nodes and edges, respectively, The graph connection information can also be represented as an adjacency matrix A {0, 10 [P]]1, where |V] is the number of nodes in the graph. The i, j-th element of the adjacency matrix [i is equal if and only if nodes i and are adjacent to each other, otherwise A ((..j] = 0. Each node i is associated with a i-dimensional vector of node features x, E RR' the features for all nodes can be summarized as a matrix X [ Furthermore, each node i is associated with label y E C, where C denotes the set of labels. We also denote the set of nodes with a given label c E C as V-- We assume that labels are only given for a subset of nodes Viahet C V. The goal of semi-supervised node classification (SSNC) is to learn a mapping f : V > C utilizing the graph G, the node features X and the labels for nodes in Viabel.
2.1 HOMOPHILY IN GRAPHS
In this work, we focus on investigating performance in the context of graph homophily and het- erophily properties. Homophily in graphs is typically defined based on similarity between con- nected node pairs, where two nodes are considered similar if they share the same node label. The homophily ratio is defined based on this intuition following Zhu et al. (2020b).
Definition (Homophily). Given graph g = =\VE) and node label vector y, the edge homophily ratio defined as the fraction of edges that connect nodes with the same labels. Formally, we have:
MG, tuc E v))
Σ 1 - yx),
(1)
[EI
(iA)EE
where |3] is the number of edges in the graph and 1(-) is the indicator function.
A graph is typically considered to be highly homophilous when ht(-) is large (typically, 0.5 < h(-) S
1), given suitable label context. On the other hand, a graph with a low edge homophily ratio is considered to be heterophilous. In future discourse, we write i((-) as h when discussing given a fixed graph and label context.
2

---

Published as a conference paper at ICLR 2022
2.2 GRAPH NEURAL NETWORKS
Graph neural networks learn node representations by aggregating and transforming information over the graph structure. There are different designs and architectures for the aggregation and transforma- tion, which leads to different graph neural network models (Scarselli et al., 2008; Kipf and Welling, 2016; Hamilton et al., 2017; Veličković et al., 2017; Gilmer et al., 2017; Zhou et al., 2020).
One of the most popular and widely adopted GNN models is the graph convolutional network (GCN). A single GCN operation takes the following form H' = D D-DDDAAAA AHH, where H and H' denote the input and output features of layer, W(k) E R is a parameter matrix to transform the features, and D is diagonal matrix and Dii, i] = deg(i) with deg(1) denoting the degree of node i. From a local perspective for node i, the process can be written as a feature averaging process h. degli) ΣjeN() Wxy, where (i) denotes the neighbors of node i. The neighborhood (i) may contain the node itself. Usually, when building GCN model upon GCN operations, nonlinear activation functions added between consecutive GCN operations.
GRAPH CONVOLUTIONAL NETWORKS UNDER HETEROPHILY
Considerable prior literature posits that graph neural networks (such as GCN) work by assuming and exploiting homophily assumptions in the underlying graph (Maurya et al., 2021; Halcrow al., 2020: Wu et al., 2018). To this end, researchers have determined that such models are considered to be ill-suited for heterophilous graphs, where the homophily ratio is low (Zhu et al., 2020b;a; Chien al., 2021). To deal with this limitation, researchers proposed several methods including H2GNN (Zhu et al., 2020b), CPGNN (Zhu et al., 2020a) and GPRGNN (Chien et al., 2021), which are explicitly designed to handle heterophilous graphs via architectural choices (e.g. adding skip- connections, carefully choosing aggregators, etc.)
Table I: SSNC accuracy on two het- erophilous datasets.
In this section, we revisit the claim that GCNs have fundamental homophily assumptions and are not suited for heterophilous graphs. To this end, we first ob- serve empirically that the GCN model achieves fairly good performance on some of the commonly used het- erophilous graphs; specifically, we present SSNC per- formance on two commonly used heterophilous graph datasets, Chame leon eon and Squi rrel in Table 1 (see Appendix D for further details about the datasets and models). Both Chameleon and Squirrel are highly heterophilous (h=:0.2). We find that with some hyperparameter tuning, GCN can outperform al- ternative methods uniquely designed to operate on some certain heterophilous graphs. This obser- vation suggests that GCN does not always "underperform" on heterophilous graphs and it leads us to reconsider the prevalent assumption in literature. Hence, we next examine how GCNs learn representations, and how this information is used in downstream SSNC tasks.
Chame 1 leon
Squirrel
Method
(h = 0.23)
(h = 0.22)
GCN
67.96 1 1.82
54,47 1 1.17
H2GCN-1
57.11 + 1.58
36.42 1.89
H2GCN-2
59.39 + 1.98
37.90
CPGNN-MLP
54.53 1 2.37
29.13
1.57
CPGNN- Chehy GPRGNN MLP
65.17 + 3.17
29.25
4.17
66.31
+ 2.05
50.56
1.51
48.11 + 2.23
31.68
1.90
3.1 WHEN DOES GCN LEARN SIMILAR EMBEDDINGS FOR NODES WITH THE SAME LABEL?
GCN is considered to be unable to tackle heterophilous graphs due to its feature averaging pro- cess (Zhu et al., 2020b; Chien et al., 2021). Namely, node's 's newly aggregated features are con- sidered "corrupted" by those neighbors that do not share the same label, leading to the intuition that GCN embeddings are noisy and un-ideal for SSNC. However, we find that crucially, for some heterophilous graphs, the features of nodes with the same label are "corrupted in the same way." Hence, the obtained embeddings still contain informative characteristics and thus facilitate SSNC. We next illustrate when GCN learns similar embeddings for nodes with the same label, beginning with toy example and generalizing to more practical cases.
GCNs have been shown to be able capture the local graph topological and structural information (Xu et al., 2019; Morris et al., 2019). Specifically, the aggregation step the GCN model able to capture and discriminate neighborhood distribution information, e.g. the mean of the neighborhood features (Xu al., 2019). Let us con- sider the two nodes a and b shown in Figure 2, where we use color to indicate the label of each node. If we further assume that all nodes sharing the same label are associated with exactly the same features. then clearly, after 1-step aggregation, the GCN operation will output exactly the same embedding for nodes and b. Accordingly, Xu et al. (2019) reasons that the GCN model lacks expressiveness due to its inability to differentiate the two nodes in the embedding space. However, in
Figure 2: Two nodes share the same neighborhood distribution; GCN learns equivalent embeddings for a and b.
3

---

Published as a conference paper at ICLR 2022
the SSNC task, mapping and b to the same location in the embedding space is explicitly desirable. Intuitively, if all nodes with the same label are mapped to the same embedding and embeddings for different labels are distinct, SSNC is effortless (Zhao et al., 2020).
Such assumptions are hard meet in practice. Thus, to consider a more practical scenario, we assume that both features and neighborhood patterns for nodes with a certain label are sampled from some fixed distributions. Under these conditions, same-label nodes may not share fixed embeddings, but we can aim to characterize their closeness. Intuitively, if the learned embeddings for same-label nodes are close and embeddings for other-label nodes are fär, we expect strong SSNC performance to be good, given class separability (low intra-class variance and high inter-class variance) (Fisher, 1936). We prove that, for graphs meeting suitable conditions the distance between GCN-learned embeddings of any same-label node pair is bounded by a small quantity with high probability.
Assumptions on Graphs. We consider a graph G, where each node é has features x; E R'' and label 3/+ We assume that (1) The features of node i are sampled from feature distribution F i.e X; ~ Fy. with f(FF,)) denoting its mean; (2) Dimensions of x; are independent to each other; (3) The features in X are bounded by positive scalar B, i.e. max,, [Xl < B: (4) For node i, its neighbor's labels are independently sampled from neighbor distribution Dy, The sampling is repeated for deg(i) times to sample the labels for dig(t) neighbors.
We denote a graph following these assumptions (1)-(4) G = (V,E, [Fe, E (., c E C Note that we use the subscripts in Fy, and Dy, to indicate that these two distributions are shared by all nodes with the same label as node i. Next, we analyze the embeddings obtained after a GCN operation. Following previous works (Li et al., 2018; Chen et al., 2020; Baranwal al., 2021), we drop the non-linearit, in the analysis.
Theorem 1. Consider a graph G = (V.E,(Fe, E (De, E C}} which follows Assump- tions (1)-(4) For any node E V, the expectation of the pre-activation output of a single GCN operation is given by
Blh.]= W (e [x])
and for any t > O. the probability that the distance between the observation h, and its expectation is larger than L is bounded by
deg(i)?
P (l]b.- - E[hill 2 1) 2-1 exx
(3)
2p²(W) Ba1
where denotes the feature dimensionality and p(W) denotes the largest singular value of W.
The detailed proof can be found in Appendix A. Theorem 1 demonstrates two key ideas. First, in expectation, all nodes with the same label have the same embedding (Eq. (2)). Second, the distance between the output embedding of a node and its expectation is small with high probability. Specif- ically, this probability is related to the node degree and higher degree nodes have higher probability to be close to the expectation. Together, these results show that the GCN model is able map nodes with the same label to an area centered around the expectation in the embedding space under given assumptions. Then, the downstream classifier in the GCN model is able to assign these nodes to the same class with high probability. To ensure that the classifier achieves strong performance, the centers (or the expectations) of different classes must be distant from each other; if we assume that ((F,,) are distinct from each other (as is common), then the neighbor distributions {D.: c C} must be distinguishable to ensure good SSNC performance. Based on these understandings and discussions, we have the following key (informal) observations on GCN's performance for graphs with homophily and heterophily.
Observation 1 (GCN under Homophily). In homophilous graphs, the neighborhood distribution of nodes with the same label (w.l.o.g c) can be approximately regarded highly skewed discrete De.. with most of the mass concentrated on the category c. Thus, different labels clearly have distinct distributions. Hence, the GCN model rypically in SSNC on such graph, with high degree nodes benefiting more, which consistent with previous work (Tang et al., 2020b).
Observation 2 (GCN under Heterophily). In heterophilous graphs, if the neighborhood distribution of nodes with the same label (w.Lo.g. c) is (approximately) sampled from a fixed distribution 'D., and different labels have distinguishable distributions, then GCN can excel at SSNC, especially when node degrees are large. Otherwise, GCNs may fail for heterophilous graphs.
Notably, our findings illustrate that disruptions of certain conditions inhibit GCN performance on heterophilous graphs. but heterophily is not a sufficient condition for poor GCN performance. GCNs are able to achieve reasonable performance for both homophilous and heterophilous graphs if they follow certain assumptions as discussed in the two observations. In Section 3.2, theoretically
4

---

Published as a conference paper at ICLR 2022
demonstrate these observations for graphs sampled from the Contextual Stochastic Block Model (CSBM) (Deshpande et al., 2018) with two classes, whose distinguishablityy neighborhood dis- tributions can be explicitly characterized. Furthermore, in Section 3.3, we empirically demonstrate these observations on graphs with multiple classes. We note that although our derivations are for GCN, a similar line of analysis can be used for more general message- message-passing neural networks.
3.2 ANALYSIS BASED ON CSBM MODEL WITH TWO CLASSES
The CSBM model. To clearly control assumptions, we study the contextual stochastic block CCBMM. a generative model for random graphs; such models have been previously adopted for benchmarking graph clustering (Fortunato and Hric, 2016) and GNNs (Tsitsulin et al., 2021). Specifically, we consider a CSBM model consisting of two classes 61 and C2. In this case, the nodes in the generated graphs consist of two disjoint sets Ci and C2 corresponding to the two classes, respectively. Edges are generated according to an intra-class probability p and an inter-class prob- ability q- Specifically, any two nodes in the graph, are connected by an edge with probability p. if they are from the same class, otherwise, the probability is q. For each node i, its initial fea- tures X; E I are sampled from Gaussian distribution x; N(,, I), where = ut E TR' for i E Ce with 9 ~ CSBM f22, P, 9). We denote the features for node obtained after a GCN operation as h;-
{1, and μ1 * f2g. We denote a graph generated from such an CSBM model as
Linear separability under GCN. To better evaluate the effectiveness of GCN operation, study the linear classifiers with the largest margin based on ix, V} and (h,, E V} and compare their performance. Since the analysis is based on linear classifiers, we do not consider the linear transformation in the GCN operation as it can be absorbed in the linear model, i.e, we only consider the process h; destyy Σjev()) Xj. For graph G CSBM(HI M4. q), we can approximately regard that for each node its neighbor's labels are independently sampled from neighborhood distribution y,, where y, denotes the label of node i. Specifically, the neighborhood distributions respectively.
corresponding to 01 and are Dr, p+9-
P ptg and De, = ptg' ptq
=ppt0'
Based on the neighborhood distributions, the features obtained from GCN operation follow Gaussian distributions:
h, N
PJLl + 9u22
I
for i E Ci; and h. N
q/41 P11
for i Cz. (4)
p +
V deg(i)
p p+q
dde((t)
Based on the properties Gaussian distributions, it is easy to see that Theorem holds. We denote the expectation of the original features for nodes in the two classes as E,,, [x:] and Ee, [x.]. SSiilarly,, we denote the expectation of the features obtained from GCN operation as Ec, [h.] and E.,[h.] [h.]. The following proposition describes their relations.
Proposition 1. (Tee [x,], Berg (x:)) and (Eee [h.]. Re, [h,]) [h.]) share the same middle point. Beg [x;]x:
[x,] and EE, [h.] Ec, [h,] share the same direction. Specifically, the middle point m and the
shared direction are as follows: m (ML + 222/22, and = (WM -/2)/ 12212.
This proposition follows from direct calculations. Given that the feature distributions of these two classes are systematic to each other (for both x; and h;), the hyperplane that is orthogonal to w and goes through m defines the decision boundary of the optimal linear classifier for both types of features. We denote this decision boundary as P = {x w x w (14) + /2)/
Next, to evaluate how GCN operation affects the classification performance, we compare the proba- bility that this linear classifier misclassifies a certain node based on the features before and after the GCN operation. We summarize the results in the following theorem.
Theorem 2. Consider graph G CSBM 11 P2.P.9)
p.q). q)- For any node i in this graph, the linear classifier defined by the decision boundary P has a lower probability to misclassify h; than x; when deg(1) > (p + q)² (pp ?
The detailed proof can be found Appendix B. Note that the Euclidean distance between the two discrete neighborhood distributions Dep and De, is 22 lp-gl Hence, Theorem 2 demonstrates that the node degree deg(i) and the distinguishability (measured by the Euclidean distance) of the neighborhood distributions both affect GCN's performance. Specifically, we can make the following conclusions: (1) When p and y are fixed, the GCN operation is more likely to improve the linear separability of the high-degree nodes than low-degree nodes, which is consistent with observations in (Tang et al., 2020b). (2) The more distinguishable the neighborhood distributions are (or the larger the Fuclidean distance is), the more nodes be benefited from the GCN operation. For
5

---

Published as a conference paper at ICLR 2022
0.9
0.8-
0.8
Test Nat-ccuracydo
0.7
0.7
9.6
0.6
0.5
0.5
0.82 0.74 0.68 0.63 0.59 0.52 0.46 0.42 0.38 0.32 0.20 0.25
0.65 0.58 0.53 0.48 0.41 0.36 0.32 0.20 0.24 0.2 0.18 0.74
Homophily Ratio
Homophily Rabio
(a) Synthetic graphs generated from Cora
(b) Synthetic graphs generated from Citeseer Figure 3: SSNC accuracy of GCN on synthetic graphs with various homophily ratios.
example, when p = 9q or 9p = g. (p + /)2/(p - q)² ~ 1.23, thus nodes with degree larger than can benefit from the GCN operation. These two cases correspond to extremely homophily (h = 0.9) and extremely heterophily (h- 0.1), respectively. However, GCN model behaves similarly on these two cases and is able to improve the performance for most nodes. This clearly demonstrates that heterophily is not a sufficient condition for poor GCN performance. Likewise, when peaq, the two neighborhood distributions are hardly distinguishable, and only nodes with extremely large degrees can benefit. In the extreme case, where p g. the GCN operation cannot help any nodes at all. Note that Theorem 2 and the followed analysis can be extended to multi-class CSBM scenario as well see Appendix F for an intuitive explanation and proof sketch.
3.3 EMPIRICAL INVESTIGATIONS ON GRAPHIS WITH MULTIPLE CLASSES
We conduct experiments to substantiate our claims in Ob- servations and 2 in graphs with multiple classes. We evaluate how SSNC performance changes as we make a homophilous graph more and more heterophilous under two settings: (1) different labels have distinct distribu- tions, and (2) different labels' distributions are muddled.
Alg. 1: Hetero. Edge Addition
input : 9 = (V,E), K, (D.) and (V.))e1-1
output: g²= (V,E"
Initialize -²= (V,,
while < do
Sample node ~ Uniform(V); Ohtain the label, yı of node i; Sample label c ~ Dy.; Uniform(V.): Update edge set E = 8 u ((i))) k t- k + 1;
3.3.1 TARGETED HETEROPHILOUS EDGE ADDITION
Graph generation strategy. We start with common, real-
world benchmark graphs. and modify their topology by adding synthetic, cross-label edges that connect nodes with different labels. Following our discussion in Obser- vation 2, we construct synthetic graphs that have similar neighborhood distributions for same-label nodes. Specif-
Sample node
return g' = (V.E'
ically, given real-world graph G, we first define a discrete neighborhood target distribution DD. for each label e C. We then follow these target distributions to add cross-label edges. The process of generating new graphs by adding edges to G is shown in Algorithm 1. Specifically, we add a total K edges to the given graph G: to add each edge, we first uniformly sample a node i from V with label Vs. then we sample a label from C according to Dy.: and finally, we uniformly sample node j from Ve and add the edge () to the graph. We generate synthetic graphs based on several real-world graphs. We present the results based on Cora and Cite seer (Sen al., 2008). The results for other datasets can be found in Appendix C. Both Cora and Citeseer exhibit strong homophily. For both datasets, we fix D. for all labels. Although many suitable D. could be specified in line with Observation 2, we fix one set for illustration and brevity. For both datasets, we vary K over 11 values and thus generate 11 graphs. Notably, as K increases, the homophily h decreases. More detailed information about the (D., c C) and K for both datasets is included in Appendix C.
Observed results. Figure 3(a-b) show SSNC results (accuracy) on graphs generated based on Cora and Citeseer, respectively. The black line in both figures shows results for the presented setting (we introduce 7 in next subsection). Without loss of generality, we use Cora (a) to discuss our find- ings, since observations are similar over these datasets. Each point on the black line in Figure 3(a) represents the performance of GCN model on certain generated graph and the corresponding value in x-axis denotes the homophily ratio of this graph. The point with homophily ratio h = 0.81 de- notes the original Cora graph, i.e, K- = O. We observe that as K increases, h decreases, and while the classification performance first decreases, eventually begins to increase, showing pattern. For instance, when h = 0.25 (a rather heterophilous graph), the GCN model achieves an impressive 86% accuracy, even higher than that achieved on the original Cora graph. We note that
-happe

---

Published as a conference paper at ICLR 2022
0:34
0.32
0.62
8.44
114
0004
0004
9:2
844
0.31
124
0:45
14
039
33
57
355
1.1
37
3
0:77
65
02
(a) 7 = 0, Acc: 86%
(b) = 0.4, Ace: 66%
( 0.8, Ace: 44% (d) Y Acc: 41%
Figure 4: Cross-class neighborhood similarity on synthetic graphs generated from Cora; all graphs
have h = 0.25, but with varying neighborhood distributions as per the noise parameter y.
performance continues to increase as K increases further the right (we censor due to space limi- lations; see Appendix C for details). This clearly demonstrates that the GCN model can work well on heterophilous graphs under certain conditions. Intuitively, the V-shape arises due to a "phase transition". where the initial topology is overridden by added edges according to the associated D. target neighbor distributions. In the original graph, the homophily ratio is quite high (h = 0.81), and classification behavior is akin that discussed in Observation where same-label nodes have similar neighborhood patterns. As we add edges to the graph, the originally evident neighborhood patterns are perturbed by added edges and gradually become less informative, which leads to the performance decrease in the decreasing segment of the V-shape in Figure 3(a). Then, as we keep adding more edges, the neighborhood pattern gradually approaches De for all c, corresponding to the increasing segment of the V-shape.
3.3.2 INTRODUCING NOISE TO NEIGHBORHOOD DISTRIBUTIONS
Graph generation strategy. In Section 3.3.1, we showed that the GCN model can achieve reason- able performance on heterophilous graphs constructed following distinct, pre-defined neighborhood patterns. As per Observation our theoretical understanding suggests that performance should de- grade under heterophily if the distributions of different labels get more and more indistinguishabl.. Hence, we next demonstrate this empirically by introducing controllable noise levels into our edge addition strategy. We adopt a strategy similar to that described in Algorithm 1, but with the key difference being that we introduce an additional parameter y, which controls the probability that we add cross-label edges randomly rather than following the pre-defined distributions. A detailed description of this approach is demonstrated in Algorithm 2 in Appendix C. For nodes of a given class (w.l.o.),, compared to the edges added according to De, the randomly added edges can be regarded as noise. Specifically, by increasing the noise parameter 7, we increase the similarity be- tween De, Der for any pair of labels c, c'. If T = 1, then all neighborhood distributions will be indistinguishable (they will all be approximately Uniform([CI). By fixing K and varying 7, we can generate graph variants with the same homophily ratio but different similarities between D. and Dec As in Section 3.3.1, we create graphs by adding edges at various K, but also vary y [0, 1] in increments of 0.2 on both Cora and c teseer.
Observed results. We report the SSNC performance on these graphs in Figure 3. Firstly, we observe that noise affects the performance significantly when the homophily ratio is low. For example, 0.25, higher y clearly results in worse
observing Figure 3(a) vertically at homophily ratio performance. This indicates that not only the fixed-ness of the neighhorhood distributions, but their similarities are important for the SSNC task (aligned with Observation 2. It also indicates that there are "good" and "bad" kinds of heterophily. On the other hand, high does not too-negatively impact when K is small, since noise is minimal and the original graph topology is yet largely homophilous. At this stage, both "good" (fixed and disparate patterns) and "bad" (randomly added edges) heterophilous edges introduce noise to the dominant homophilous patterns. When the noise level y is not too large, we can still observe the V-shape: e.g. 7 = 0.4 in Figure 3(a) and y = 0.2 in Figure 3 (b); this is because the designed pattern is not totally dominated by the noise. However, when y is too high, adding edges will constantly decrease the performance, nodes of different classes have indistinguishably similar neighborhoods.
To further demonstrate how affects the neighborhood distributions in the generated graph, we examine the cross- class neighborhood similarity, which we define as follows:
Definition 2 (Cross-Class Neighborhood Similarity (CCNS)). Given graph G and labels y for all nodes, the CCNS between classes c, E C is s(c,d) |ellyyl Eievesev, (d(), d(f) where
7

---

Published as a conference paper at ICLR 2022
Ve indicates the set of nodes in class and d(()) denotes the empirical histogram (over |C| classes) of node i's neighbors' labels, and the function cos(..-) measures the cosine similarity.
When c c', s(c, c') calculates the intra-class similarity, otherwise, it calculates the inter-class similarity from a neighborhood label distribution perspective. Intuitively, if nodes with the same label share the same neighborhood distributions, the intra-class similarity should be high. Likewise, to ensure that the neighborhood patterns for nodes with different labels are distinguishable, the inter- class similarity should be low. To illustrate how various 7y values affect the neighborhood patterns, illustrate the intra-class and inter-class similarities in Figure 4 for 7 0, 0.4, 0.8, 1 on graphs generated from Cora a with homophily ratio h = 0.25. The diagonal cells in each heatmap indicate the intra-class similarity while off-diagonal cells indicate inter-class similarity. Clearly, when is small, the intra-class similarity is high while the inter-class similarity is low, which demonstrates the existence of strongly discriminative neighborhood patterns in the graph. As increases, the intra-class and inter-class similarity get closer, becoming more and more indistinguishable, leading to bad performance due to indistinguishable distributions as referenced in Observation 2.
REVISITING GCN'S PERFORMANCE ON REAL-WORLD. GRAPHS
In this section, we first give more details on the experiments run compare GCN and MLP. We next investigate why the GCN model does or does not work well on certain datasets utilizing the understanding developed in earlier sections.
4.1 QUANTITATIVE ANALYSIS
Following previous work (Pei et al., 2020: Zhu et al., 2020b), we evaluate the performance of the GCN model on several real-world graphs with different levels of homophily. We include the citation networks Cora, Citeseer and Pubmed (Kipf and Welling, 2016), which are highly homophilous. We also adopt several heterophilous benchmark datasets including Chame eon, Squirrel, Actor, Cornell, Wisconsin and Texas (Rozemberezki et al., 2021; Pei et al., 2020). Appendix D.1 gives descriptions and summary statistics of these datasets. For all datasets, we follow the experimental setting provided in (Pei et al., 2020), which consists of 10 random splits with proportions 48/32/20% corresponding to "raining/validationntee split, we use 10 random seeds, and report the average performance and standard deviation across 100 runs. We compare the GCN model with the MI.P model, which does not utilize the graph structure. With this comparison, heterophilous graphs (perform even worse than MLPP). We also compare GCN with state-of-the-ar methods and their descriptions and performance are included in the Appendix D. The node clas- sification performance (accuracy) of these models is reported in Table 2. Notably, GCN achieves better performance than MLP on graphs with high homophily (Cora, Citeseer, and Pubmed) as expected. For the heterophilous graphs, the results are comparatively mixed. The GCN model outperforms MI.P on Squi rrel and Chame 1 eon (it even outperforms methods specifically de- signed for heterophilous graphs as shown in Appendix D.5.), while underperforming on the other datasets (Actor, Cornell, Wis Wisconsing and Texas). In the next section, we provide explana- tions for GCN's distinct behaviors on these graphs based on the understanding developed in earlier sections.
for each graph. For each
aim to check whether the GCN model always fails for for
4.2 QUALITATIVE ANALYSTS
Our work far illustrates that the popular notion of GCNs not being suitable for heterophily, or homophily being a mandate for good GCN performance is not accurate. In this subsection, we aim to use the understanding we developed in Section 3 to explain why GCN does (not) work well on real-world graphs. As in Section 3.3.2, we inspect cross-class neighborhood similarity (Definition 2) for each dataset; due to the space limit, we only include representative ones here (Cora, Chameleon Actor and Cornel 11); see Figure 5). Heatmaps for the other datasets can be found in Appendix E. From Figure 5(a), it is clear that the intra-class similarity is much higher than the inter-similarity ones, hence Cora contains distinct neighborhood patterns, consistent with Observation 1. In Figure 5(b), we can observe that in Chame leon, intra-class similarity is generally higher than inter-class similarity, though not as strong as in Figure 5(a). Additionally, there is an apparent gap between labels 0, and 2,3, 4, which contributes separating nodes of the former 2 from the latter 3 classes, but potentially increasing misclassification within each of the two groupings. These observations also help substantiate why GCN can achieve reasonable performance (much higher than MLP) on Chameleon. The GCN model underperforms MLP in Actor and we suspect that the graph does not provide useful information. The heatmap for Act or in Figure 5 shows that the intra-class and inter-class similarities are almost equivalent, making the neighhorhood
8

---

Published as a conference paper at ICLR 2022
Table 2: Node classification performance (accuracy) on homophilous and heterophilous graphs.
Cora
Citeseer
Pubmed
Chane leon
rrel
Actoor
Cornell
Wicconiin
Texao
GCN MLP
$7.12
76.50 1611
67.96 1.82
54.47 31.68 4: 1.90
30.31
0,98
59.35
4.19
61.76
63.81 1:
75.01
1.97
72.40 1: 1.97
87.84 1 0.30
18.11 1: 2,23
36.17
1.09
81.86 2: 6.04
86.29 1: 4.50
$3.30 1: 4.51
0:33
6:24
3:40
3.5L
0:32
6.5L
0.4
6.3
1007 877
93
0.34
8.00
8.03
03
0.28
3.39
0:33
0:5
0.47
033
0:51
0:5
8:51
0
30
0.37
837
0:0 9:0
032
24
6.44
3.5L
0.00
9:70
34
3.5L
9.5
0.5
64
621
357
0.32
6:1
6.4
0.11 9:C
8:05
0.04
8:47
0.87
67
0.28
1:1
6:11
1:11
1:1
0.47
0.
0.1
(a) Cora
(b) Chameleor,
(c) Actor
(d) Cornell
Figure 5: Cross-class neighborhood similarity on homophilous graphs and heterophilous graphs.
distributions for different classes hard to distinguish and leading to bad GCN performance. Similar observations are made for Cornell, 1. Note that Cornell only consists of 183 nodes and 280 edges, hence, the similarities shown in Figure 5 are impacted significantly (e.g. there is a single node with label 1, leading to perfect intra- cltas-class similarity for label 1).
5 RELATED WORK
Graph neural networks (GNNs) are powerful models for graph representation learning, They have been widely adopted tackle numerous applications from various domains (Kipf and Welling, 2016; Fan et al., 2019; Bastings et al., 2017; Shi et al., 2019). (Scarselli et al., 2008) proposed the first GNN model, to tackle both node and graph level tasks. Subsequently, Bruna et al. (2013) and Defferrard et al. (2016) generalized convolutional neural networks to graphs from the graph spectral perspective. Kipf and Welling (2016) simplified the spectral GNN model and proposed graph convolutional networks (GCNs). Since then, numerous GNN variants, which follow specific forms of feature transformation (linear layers) and aggregation have been proposed ( (Veličković et al., 2017; Hamilton et al., 2017; Gilmer et al., 2017; Klicpera et al., 2019). The aggregation process can be usually understood as feature smoothing (Li al., 2018; Ma et al., 2020; Jia and Benson, 2021; Zhu et al., 10 Hence, several recent works claim (Zhu et al., 2020b;a; Chien et al., 2021), assume (Halcrow al., 2020; Wu al., 2018: 8; Zhao et al., 2020) or remark upon (Abu-El-Haijp
al., 2019; or unsuitability in capturing heterophily. Several recent works specifically develop GNN models choices to tackle heterophilous graphs by carefully designing or modifying model architectures such as Geom-GCh (Pei et al., 2020), H2GCN (Zhu et al., 2020b),
Maurya et al., 2021; Hou et al., 2020) GNN models homophily-reliane
(Chien et al., 2021), and CPGNN (Zhu et al., 2020a). Some other works aim modifylconstruet graphs to be more homophilous (Suresh et al., 2021). ))- There is concurrent work (Luan et al., 202 also pointing out that GCN can potentially achieve strong performance on heterophilous graphs. A major focus of this paper is to propose a new model to handle heterophilous graphs. However, our work aims to empirically and theoretically understand whether homophily is a necessity for GNNs and how GNNs work for heterophilous graphs.
6 CONCLUSION
It is widely believed that GNN models inherently assume strong homophily and hence fail to gener- alize graphs with heterophily. In this paper, we revisit this popular notion and show it is not quite accurate. We investigate one representative model, GCN, and show empirically that can achieve good performance on some heterophilous graphs under certain conditions. We analyze theoretically the conditions required for GCNs to learn similar embeddings for same-label nodes, facilitating the SSNC task; put simply, when nodes with the same label share similar neighborhood patterns, and different classes have distinguishable patterns, GCN can achieve strong class separation, regard- less of homophily or heterophily properties. Empirical analysis supports our theoretical findings. Finally, we revisit several existing homophilous and heterophilous SSNC benchmark graphs, and investigate GCN's empirical performance in light of our understanding. Note that while there exist graphs with "good heterophily", "bad heterophily" still poses challenges to GNN models, which calls for dedicated efforts. We discuss the limitation of the current work in Appendix I.

---

Published as a conference paper at ICLR 2022
REFERENCES
Sami Abu-EI-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. MixHop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In Kamalika Chaudhuri and Ruslan Salakhutdi- nov, editors, Proceedings of the 36th International Conference of Proceedings of Machine Learning Research, pages 21-29. PMLR, 09-15 Jun 2019. URL http::/ppooceeeeeeeeee httpppppeeeengssseeeeeeeeee www.nnng........mmm.mm........e. aar..pres /vcesssv99/ v aabuaaaueeee el hai jalia html.
Machine Learning, volume 97
http:/
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi- supervised classification: Improved linear separability and out-of-distribution generalization. arXiv preprint arXiv: 102.:2202206666, 2021.
Joost Bastings, Ivan Titov, Wilker Aziz, Diego Marcheggiani, and Khalil Sima an. Graph convolu- tional encoders for syntax-aware neural machine translation. arXiv preprint arXiv: Stdi::/704.06677 2017.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv: 1312v:331..6203, 2013.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pages 1725-1735. PMLR, 2020.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021. URL nttps:://penrett wtt.r/wwwwweeeeetteeeeeeeeeeeeee forum?id-n6j17fEEs
net/
Valerio Ciotti, Moreno Bonaventura, Vincenzo Nicosia, Pietro Panzarasa, and Vito Latora. Ho- mophily and missing links in citation networks. EPJ Data Science, 5:1-14, 2016.
Enyan Dai and Suhang Wang. Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pages 680-688, 2021.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. arXiv preprint arXiv:1606.09375. 20100,0,937,,,1111
Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models. In NeurIPS, 2018.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The World Wide Web Conference, pages 417-426, 2019.
Ronald A Fisher. The use of multiple measurements in taxonomic problems. Annals of eugenics, (2):179-188, 1936.
Santo Fortunato and Darko Hric. Community detection in networks: A user guide. Physics reports, 659:1-44, 2016.
Elisabeth R Gerber, Adam Douglas Henry, and Mark Lubell. Political homophily and collaboration in regional planning networks. American Journal of Political Science, 57(3):598-66 610, 2013.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Muchine Learning, pages 1263-1272. PMLR, 2017.
Jonathan Halerow, Alexandru Mosoi, Sam Ruth, and Bryan Perozzi. Grale: Designing networks for graph learning. In Proceedings of the 26th ACM SIGKDD International Conference on Knowl- edge Discovery & Data Mining, pages 2523-2532 2020.
William L Hamilton, Rex Ying. and Jure Leskovec. Inductive representation learning on large graphs. arXiv preprint 1rXiv:/706.022 16, 2017.
10

---

Published as a conference paper at ICLR 2022
Yifan Hou, Jian Zhang, James Cheng, Kaili Ma, Richard T. B. Ma, Hongzhi Chen, and Ming-Chang Yang. Measuring and improving the use of graph information in graph neural networks. In International Conference on Learning Representations, 2020. URL https: //tp:r/vi//peeeiee... net/ fort:/form?tt www.mniidddeieiiieee
Ankit Jain and Piero Molino. Enhancing recommendations on uber eats with graph convolutional networks.
Junteng Jia and Austin R Benson. unifying generative model for graph learning algorithms: Label propagation, graph convolutions, and combinations. arXiv preprint arXiv:2101.07773 2021.
Weiwei Jiang and Jiayun Luo. Graph neural network for traffic forecasting: A survey. arXiv preprint 1:Xi::2001.11174 2021.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: (16660009907 2016.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations (ICLR), 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- superviued learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on hon-hoopphilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34, 2021.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. heterophily a real nightmare for graph neural networks to do node classification? arXiv preprint 2tt::://090054411 2021.
Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah. A unified view on graph neural networks as graph signal denoising. arXiv preprint arXiv:2010.01777, 2020.
Sunil Kumar Maurya, Xin Liu, and Tsuyoshi Murata. Improving graph neural networks with simple architecture design. arXiv preprint arXiv:2 07634, 2021.
Miller McPherson, Lynn Smith-Lovin and James Cook. Birds of a feather: Homophily in social networks. Annual review of sociology. 27(1): 2001.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4602-4609, 2019.
Mark Newman. Networks. Oxford university press, 2018.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Yang. Geom-gen. Geometric graph convolutional networks. In International Conference on Learning Representations, 2020. URL
net forum? 2ormmlddd-ee2aggPPP
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9(2))cnab0114 2021.
Aravind Sankar, Yozen Liu, Jun Yu, and Neil Shah. Graph neural networks for friend ranking in large-scale social platforms. 2021.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1) (061).61-80 2008
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008

---

Published as a conference paper at ICLR 2022
Lei Shi, Yifan Zhang, Jian Cheng, and Hanqing Lu. Skeleton-basee action recognition with directed graph neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7912-7921, 2019.
Susheel Suresh, Vinith Budde, Jennifer Neville, Pan Li, and Jianzhu Ma. Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns. arXiv preprint ar 065866 2021.
Xianfeng Tang, Yozen Liu, Neil Shah, Xiaolin Shi, Prasenjit Mitra, and Suhang Wang. Knowing your fate: Friendship, action and temporal explanations for user engagement prediction on so- cial apps. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2269-2279, 2020a.
Xianfeng Tang, Huaxiu Yao, Yiwei Sun, Yiqi Wang, Jiliang Tang, Charu Aggarwal, Prasenjit Mitra, and Suhang Wang. Investigating and mitigating degree-related biases in graph convoltuional net- works. In Proceedings of the 29th ACM International Conference on Information & Knowledge Manugement, pages 1435-1444, 2020b.
Anton Tsitsulin, Benedek Rozemberezki, John Palowitch, and Bryan Perozzi. Synthetic graph gen- eration benchmark graph learning. 2021.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 17/0. 10903, 2017.
Xuan Wu, Lingxiao Zhao, and Leman Akoglu. A quest for structure: jointly learning the graph struc- ture and semi- supersupe classification. In Proceedings the 27th ACM international conference on information and knowledge management, pages 87-96, 2018
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https: //openzeview.... nwt wtt.eeew.ettttttmmooooorrrGi
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 974-983, 2018
Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data aug- mentation for graph neural networks. In AAAI, 2020.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applica- tions. Al Open, 1:57-81, 2020.
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily, arXiv preprini arXiv:2009. 13566, 2020a.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 2020b.
Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with optimization framework. arXiv preprint arXiv:2101.11859, 2021.
Marinka Zinik, Monica Agrawal, and Jure Leskovec. Modeling polypharmacy side effects with graph convolutional networks. Bioinformatics, 34(13):447-i466, 2018.
12

---

Published as a conference paper at ICLR 2022
A PROOF OF THEOREM
To prove Theorem I, we first introduce the celebrated Hoeffding inequality below.
Lemma (Hoeffding's Inequality). Let Zi.... Zu be independent bounded random variables with Zi E [a, for all i, where 00
< a
S cc. Then
Σ exp (- 2nt²
(Z
2 2
E
(T - a)²
n1 i=1
and
1 I
2nt²
-
Σ 1=1
(Z;
-t s-
exxp ( - aa)
for all t 2 O.
Theorem 1. Consider a graph 9 =
E (Dec C}}. which follows Assump- V. the expectation of the pre-activation ouiput of a single GCN
tions (1)-(4. For any node operation is given by
B[h.] = W (Eur-Dy x-xFx x
(5)
and for any t > O, the probability that the distance between the observation h; and its expectation larger than bounded by
deg(i)(2
P( E lla 2) 2-1.cxxpp
2P)(W)BBL
where is the feature dimensionality and p (W) denotes the largest singular value of W.
Proof. The expectation of h can be derived as follows.
h E
Σ
Wx,
deg(i)
(EN(()
De
deg(i)
JEN(
=W X-FFF
We utilize Hoeffding's Incquality to prove the bound in Eq. (6). Let [ek,, ....... denote the i-th element of x. Then, for any dimension k. (x, [k], E N(i) is a set of independent bounded random variables. Hence, directly applying Hoeffding's inequality, for any tı 2 O. we have the following bound:
2exp (- (deg
Σ JEN()
(x EE(x,(A)))
2 4
2B²
Σ
(x, - E (x,])
Vlt.. then at least for one lo E {l.....!}. the inequality
(a)
Σ
(x
E [x(,(A]]
2 4 holds. Hence, we have
(EN(1)
E(x((AI) 24 111)
P
Σ
- (x,)E(x,))
2 Vili
SP
Σ
(x
SEN(()
k=1
(EN(()
PP
-x
24
km
jEN((
(de)
1.l-exp eexp
2B2
13

---

Published as a conference paper at ICLR 2022
Let vi then we have
(deg(())
P
Σ
(xy E [x,])
2 tz
2 exp
2
JEV(1)
Furthermore, we have
[h - E/hill2 = W
Σ
(x, - -E(xx)
JEN(()
$ 22
Σ
(x, - - (x,])
JEN(()
= ((W)
Σ
(x) - E (x,1)
JEN(()
where [ is the matrix 2-norm of W. Note that the last line uses the identity |W| p(W).
Then, for any > 0, we have
P P( h; Elb.]ll
1) SP ((W)
Σ (x,
B
21
)EN(()
=P
Σ JEN(1)
(x, E [x5])
2
t p P(W)
(deg(i)){
$ 2 eexp
2p²(W)
which completes the proof.
B PROOF OF THEOREM
Theorem 2. Consider graph G CSBM(H1, 100MMp41.22P.. W2.P.)). 9)- For any node this graph, the linear classifier defined by the decision boundary P has lower probability to mis-classify h, than X; when deg(i) (p 9) (p 9)
Proof. We only prove for nodes from classes co since the case for nodes from classes ei is symmetric and the proof is exactly the same. For node E Co. we have the follows
P(x; is mis-classified) P(w x; b < 0) for i E Co
PP, is mis-classified) P(w Th, h, + b S for i Co,
(8)
where w and b w (μ1 + 41) /2 is the parameters of the decision boundary P. we have that P(w" ddeg(i)h; /deg(i)b 0).
(Pww" h, + b s
(9)
We denote the scaled version of h; as h2 deg( Then, h' follows
deg(i) (ppo + qui))
h / deg N
1) .oor Co.
(10)
p+q
Because the scale in Eq. (9), the decision boundary for h' is correspondingly moved to w + /deg(i)b = 0. Now, since x; and h share the same variance, to compare the mis-classification probabilities, we only need to compare the distance from their expected value their corresponding decision boundary. Specifically, the two distances are as follows:
I|400 u1
disx:
deg(()) i gl
140
pA ||2
disp
(11)
(p+
14

---

Published as a conference paper at ICLR 2022
The larger the distance is the smaller the mis-classification probability is. Hence, when dism; disx,, hn has lower probability be mis-classified than X,. Comparing the two distances, conclude that when deg(i) > ( h has a lower probability to be mis-classified than X;- Together with Eq. have that
P(,; is mis-classified) < P(;; is mis-classified) if deg(i) > + 9 q which completes the proof.
(12)
C ADDITIONAL DETAILS AND RESULTS FOR SECTION 3.3.1
C.I DETAILS THE GENERATED GRAPHS
In this subsection, we present the details of the graphs that generate in Section 3.3.1. Specifically, we detail the distributions {De, c E C} used in the examples, the number of added edges K, and the homophily ratio h. We provide the details for Cora and Citeseer in the following subsections. Note that the choices of distributions shown here are for illustrative purposes, to coincide with Observations and 2. We adapted circulant matrix-like designs due to their simplicity.
C.1.1 CORA
There are labels, which we denote 1, 2,,,,,,,, 6.. The distributions (De, E C} are listed as follows. The values of and the homophily ratio of their corresponding generated graphs are shown in Table 3.
Do Categorical 0.5, 0, 0,
D1 (00egoorical0055,00..0 (0.5,0,0.5,0,0,000,00
D2 00,
D3 Categorical
D4 Categorical 0,,,00,,,,,,,,0055000
D; (10,gorica((00,,,,00000.00
D6 Categorical 00.00000,,000000000000,0
Table of added edges (K) and homophily ratio (h) values for generated graphs based on Cora.
K
1003
2006
3009
4012
6018
8024
10030
12036
16048
20060
24072
h 0.740
0.681
0.630
0.587
0.516
0.460
0.415
0.378
0.321
0.279
0.247
C.1.2
CTTESEER
There are 6 labels, which we denote as (0, 3, 4,5). 5). The distributions (Da, C} are listed follows. The values of K and the homophily ratio of their corresponding generated graphs are shown in Table 4.
Do Categorical (0,, 0.5, 0, 0, 0,
D1 Categorical (0..5, 0, 0,0,
D2 Categorical
0)),
D3 (ategoriiaa((000.0000 0,0, 0, 0.5,0))
Da Categorical
D3 (0 0,
15

---

Published as a conference paper at ICLR 2022
# of added edges (K) and homophily ratio (h) values for generated graphs based Citeseer
Table 4:
K
1204
2408
3612
4816
7224
9632
12040
14448
19264
24080
28896
h
0.650
0.581
0.527
0.481
0.410
0.357
0.317
0.284
0.236
0.202
0.176
C.2 RESULTS ON MORE DATASETS: CHAMPI BON AND SOUTRRET.
We conduct similar experiments those in Section 3.3.1 based on Chameleow and Squ rrel. Note that both Squí rrel and Chamel eon have labels, which we denote as (0, 2.,,3, 4). We pre-define the same distributions for them as listed as follows. The values of K and the homophily ratio of their corresponding generated graphs based Squi rrel and Chame eon are shown in Table 5 and Table 6, respectively.
Do Categorical 0,,
D1 (ategorical 0j)]
D2 Categorical( 0.5, 0.5,, 0)),
D3 (0,,0, 0.5))
D4 (0
Table 5: # of added edges (K) and homophily ratio (h) values for generated graphs based on Squirrel.
12343
24686
37030
49374
61716
74060
86404
98746
111090
12434
135776
h 0.215
0.209
0.203
0.197
0.192
0.187
0.182
0.178
0.173
0.169
0.165
Table 6: # of added edges (K) and homophily ratio (h) values for generated graphs based Chame leon.
K
1932
3866
5798
7730
9964
11596
13528
15462
17394
19326
21260
h
0.223
0.217
0.210
0.205
0.199
0.194
0.1
0.184
0.180
0.1
0.172
y=0
0.85
0.9-
Test Accuraty
Accurscy
0.8
0.7
0222 0:15 0.200 1233 0.28 0.092 6.87 2182 6i26 0304 3100 0.68
0.06 3.09 1124 0.00 0.24 033 0.26 0372 120 0,223 0.237 3:21
Homophily
Homoshily
(a) Synthetic graphs generated from Squi mrel
(b) Synthetic graphs generated from Ch Chamel 1 len
Figure Performance of GCN on synthetic graphs with various homophily ratio.
The performance of the GCN model on these two sets of graphs (generated from Squi rrel and Chame is shown in Figure 6. The observations are similar to what we found for those gen- erated graphs based Cora and Citeseer in Section 3.3.1. Note that the original Squi rrel and Chame leon graphs already have very low homophily, but we still observe a V-shape from the figures. This is because there are some neighborhood patterns in the original graphs, which are distinct from those that we designed for addition. Hence, when we add edges in the early stage, the performance decreases. As we add more edges, the designed pattern starts to mask the original patterns and the performance starts increase.
16

---

Published as a conference paper at ICLR 2022
C.3 GCN'S PERFORMANCE IN THE LIMIT (AS K + 00)
In this subsection, illustrate that K - oo, the aceuracy of the GCN model approaches 100%. Specifically, we set K a set of larger numbers as listed Table Ideally, when K + oc, the homophily ratio will approach 0 and the model performance will approach 100% (for diverse- enough D.). The performance of the GCN model on the graphs described in Table 3 and Table are shown Figure 7. Clearly, the performance of the GCN model approaches the maximum as we continue increase K.
Table Extended added edges (K) and homophily ratio (h) values for generated graphs based on Cora.
K
28084
32096
36108
40120
44132
48144
52156
56168
80240
h
0.272
0.248
0.228
0.211
0.196
0.183
0.172
0.162
0.120
1.00
y=
0.95
Test Accuracy
0.85
0.75
0.70
0.65
0.81
0.74 0.68 0.63 0.59 0.52 0.46 0.42 0.38 0.32 0.28 0.25 0.22 0.2 0.18 0.16 0.15 0.14 0.140.3.... 0.09
Homaphily
Figure 7: As the number of edges approaches - co, the homophily ratio - 0, and GCN's performance approaches 100%.
C.4 DETAILS OF ALGORITIIM 2
The pseudo code to describe the process to generate graphs with a noise level 7 is shown in Al- gorithm 2. The only difference from Algorithm is in Line 6-7, we randomly add edges if the generated random number smaller than the pre-defined y (with probability 7).
Alg. 2: Heterophilous Edge Addition with Noise
input : 9 (V,8), K, (Da))el 10l-1 and (Va)/1-1 output: g' = (V.E")
Initialize 9'
while k K do
Sample node i Uniform(Y);
Obtain the label, of node ;;
Sample number Uniform(0.1))
// Uniform (0, denotes the continuous
standard uni form distribution
if y then
L Sample label e Uniform(C (w:)); clse
L Sample label e Dy,; Sample node j Uniform(V... Update edge set E¹ = ((tj));
k + + 1;
return (V,8))
17

---

Published as a conference paper at ICLR 2022
D EXPERIMENTAL DETAILS: DATASETS, MODELS, AND RESULTS
We compare the standard GCN model (Kipf and Welling, 2016) with several recently proposed methods specifically designed for heterophilous graphs including H2GCN (Zhu et al., 2020b), GPR- GNN (Chien et al., 2021), 1), and CPGNN (Zhu et al., 2020a). A brief introduction of these methods can be found in Appendix D.2.
D.1 DATASETS
We give the number of nodes, edges, homophily ratios and distinct classes of datasets we used in this paper in Table 8
Table 8: Benchmark dataset summary statistics.
Claeeeer
Picmmed
Chame
3qui
Actior
Cornall
Kisconsin
Nodes (V))
2708
3327
19717
2277
5201
7600
183
183
# Edges 8 5278
4676
44327
31421
198493
26752
280
466
295
Homaphily Ratio
0.23
0.22
Classes [[C]]
6
3
5
5
5
D.2 MODELS
H2GCN (Zhu et al., 2020b) specifically designed several architectures to deal with heterophilous graphs, which include ego- and neighbor-embedding separation (skip connection), aggregation from higher-order neighborhoods, and combination of intermediate representations. We include two variants H2GCN-1 and H2GCN-2 with 1 or 2 steps of aggregations, respectively. We adopt the code published by the authors at https: htt///tttut/ com/ Gems Lab HH2GHH
GPR-GNN (Chien et al., 2021) performs feature aggregation for multiple steps and then lin- early combines the features aggregated with different steps. The weights of the linear com- bination are learned during the model training. Note that it also includes the original fea- tures before aggregation in the combination. We adopt the code published by the authors at https: /gittubtb com/ anhao2016 RCNN.
CPGNN (Zhu et al., 2020a) incorporates the label compatibility matrix to capture the connec- tion information between classes. We adopted two variants of CPGNN that utilize MLP and ChebyNet (Defferrard et al., 2016) base models pre-caleulate the compatibility matrix, spectively. We use two aggregation layers for both variants. We adopt the code published by authors at https: //gpt//b///ttb//////////p com/ Lammssab//GGN
D.3 MLP+GCN
We implement a simple method to linearly combine the learned features from the GCN model and an MLP model. Let
(2) GCN E [[| denote the output features from a 2-layer GCN model, where [V] and [C] denote the number of nodes and the number of classes, respectively. Similarly, we use (2) MLP E R||[ to denote the features output from 2-layer MLP model. We then combine them
for classification. The process can be described as follows.
= a H cCx + (1 a)) H2
MLP:
(13)
where a is a hyperparameter balancing the two components. We then apply row-wise softmax to each row of H to perform the classification.
D.4 PARAMETER TUNING AND RESOURCES USED
We tune parameters for GCN, GPR-GCN, CPGNN, and MLP+GCN from the following options:
learning rate: {0.002, 0.005, 0.01, 0.05)
weight decay (5c-04. 04, 5e-05, 5c-06, 5c-07. 5c- 1e 1e-05,00 0}
dropout rate: {0, 0.2, 0.5, 0.8).
For GPR-GNN, we use the "PPR" the initialization for the coefficients. For MLP+GCN, we tune from (0.2, 0.4, 0.6, 0.8, 1}. Note that the parameter search range encompasses the range adopted in the original papers to avoid unfairness issues.
18

---

Published as a conference paper at ICLR 2022
All experiments are cluster equipped with Intel(R) Xeon(R) CPU E5-2680 v4 @ 2.40GHz
CPUs and NVIDIA Tesla K80 GPUs.
D.5
MORE RESULTS
Coso
Citesoor
Chomeloon
Squirso-
Racec
Cosnell
Wisconsin
Texos
16.50
MLP
72.40
97.01
16.35
1.11
94.82
HNGNN-1
77.07
57.11
36.42
H2GCN-2
76.88
1.77
35,62
92.16
4.22
CPINN-MLPP
85.84
1:20
74.80
0.37
54.53
20
1:57
79.91
2.72
CRONN--Cheby
87.23
76.64
0.33
65.17
29.25
4.17
75.08
7.51
7,80
75.96
GPR-GNN
86.79
1.27
75.55
1.56
86.79
1 0.55
66.31 2.05
50.56
1.51
33.94
0.95
79.27
6.03
83.73
4.02
$4.43
4.10
E HEATMAPS FOR OTHER BENCHMARKS
We provide the heatmaps for Citeseer and Pubmed in Figure 8 and those for Squirree rree, Texas, and Wisconsin in Figure 9. For the Citeseer and Pubmed, which have high ho- mophily, the observations are similar those of Cora as we described in Section 4.2. For Squirrel, there are some patterns; the intra-class similarity is generally higher than inter-class similarities. However, these patterns are not Very strong, i.e. the differences between them are not very large, which means that the neighborhood patterns different labels are not very distinguish- able from each other. This substantiates the middling performance of GCN Texas and Wisconsin are very small, with 183 nodes, 295 edges and 251 nodes, 466 edges, respectively. The average degree is extremely small (< 2). Hence, the similarities presented in the heatmap may present strong bias. Especially, in Texas, there is only node with label 1. In Nisconsin in, there are only 10 nodes with label 0.
Squirrel. Both
0:65
0.26
0.32
0.14
0.37
3.57
0.8
0.74
0.38
0.00
3.55
0.55
0.6
0.16
0.92
0.19
0.08
0.4
0.4
3,5
0:17
0.04
0.06
0.06
0.2
2.0
024
0.80
0.2
0.07
0.25
0.29
0.05
2.57
2.05
(a) Citeseer
(b) Puomed
Figure 8: Cross-class neighborhood similarity on Citeseer and Pubmed. On both graphs, the intra-class similarity is clearly higher than the inter-class ones.
F EXTENDING THEOREM 2 TO MULTIPLE CLASSES
Below, we provide a proof sketch and illustration for an extension to Theorem 2's main results in multi-class context. Specifically, we consider special case for more tractable analysis.
Consider a K-class CSBM. The nodes in the generated graphs consist of disjoint sets of the same size C,....,yx corresponding to the K classes, respectively. Edges are generated according to an intra-class probability p and an inter-class probability q. Specifically, for any two nodes in the graph, they are from the same class, then an edge is generated to connect them with probability p. other- wise, the probability is q. For each node i, its initial associated features x; R² are sampled from Gaussian distribution x; N(u, I), where μ μA IR for C& with μe # Yz, w E {l...., K). We further assume that the distance between the mean of distribu- tions corresponding to any two classes is equivalent, i.e, ||u uwwl12 D, Vz, w (1..... K). where a positive constant. We illustrate the 3-classes case Figure 10, where we use the dashed circles to demonstrate the standard deviation. Note that the K classes of the CSBM model are sym- metric to each other. Hence, the optimal decision boundary of the K classes defined by set
{1,..., K} and
19

---

Published as a conference paper at ICLR 2022
1.0
0.8
9.63
0.1
0.33
0.00
0.35
0.6
9:64
0.3
9:73
0.74
0.75
0.81
0.1
0.68
0.31
341
0.27
0.71
0.72
0.68
0.45
0.4
2.83
8.72
2.24
0.75
0.77
0.17
0.33
0.31
0.58
2.58
0.36
0.64
0.03
0.50
0.31
6.4
0.2
02
3.84
0.72
0.41
0.50
0.51
0.72
0.0
(a) Squirrel
(b) Texas
(c) Wisconsin
Figure 9: Cross-class neighborhood similarity on Squirrel, Texas and Wisconsin. The inter- class similarity on Squirrel is slightly higher than intra-class similarity for most classes, which substantiates the middling performance of GCN, Both Texas and Wi sconsir are quite small, hence the cross-class similarity these two graphs present severe bias and may not provide precise information about these graphs.
of (5) hyperplanes (see Figure 10 for an example), where each hyperplane equivalently separates two classes. Similar to the analysis in the binary case (see the description below Proposition 1), for any given two classes C₂ and Cu. the hyperplane
{x|w 122 which is orthogonal to (μt (tw) and going through (μu + pw) For example, Figure 10, the decision boundaries separate the entire space to 3 areas correspond- ing to the classes. Each decision boundary is defined by a hyperplane equally separating two classes. For example, the descision bounadry between and d2 is orthogonal to (14 (22 and going through the middle point (f4 + #2)/2. Clearly, the linear separability is dependent on the distance D between the classes and also the standard deviations of each class' node features. More specifically, linear separability is favored by larger distance D and smaller standard deviation.
w (m= pw, with
w w (u, -
111
112
113
Figure 10: 3-class CSBM in 2-dimensional space. The dashed circles demonstrate the standard deviation for each class. The entire space is split to three areas (indicated by different colors) corre- sponding to the three classes for optimal decision making. The equilateral triangle indicates that the distance between the means any two classes the same.
Next, we discuss how the GCN operation affects the linear separability. Overall, we want to demon- strate the following: (i) after the GCN operation, the classes are still symmetric to each other; (ii) the GCN operation will reduce the distance between the classes (in terms of the expectation of the output embeddings) and reduce the standard deviation of the classes; and (iii) reducing the distance impairs the separability while reducing the standard deviation improves the separability. Hence,
20

---

Published as a conference paper at ICLR 2022
analyze the two effect and provide threshold. We describe these three items in more detailed way as follows.
Preservation of Symmetry. For any class Cs 2 E fi...... J. ..].....,,... its neighborhood label distribution and all other
Dr, can be described by vector where only the z-th element equals p+(k 1)g
elements equal to - We consider the aggression process h, deg(( Σ Xj. Then, (EA(()
for node with label C22 its features obtained after this process follow the following Gaussian distribution.
pp: kE (.kk p (K 1)g
E
9/4
h; N
die for i E C2
(14)
Specifically, we denote the expectation of class Co after the GCN operation as Fe, [h]
PH4
Σ
gpen
We next show that the distance between any two classes is the same. Specifically, for any two classes and after the GCN operation, the distance between their
p+
expectation is as follows.
Pl4: +
E
q14
PM +
E
kEfl.... 1,pz
kE K).
Be. [h] Ee, [b]ll2
p + (K 1)g
p (K
-1)
(p:: pmm
p
p+ (K 1)q ||
H
(15)
p (K - 1)q
mw l2 for any pair of classes c₂ and Cw- Hence, after the GCN operation, the distance between any two classes is still the same. Thus, the classes are symmetric each other.
Note that we have ||
Reducing inter-class distance and intra-class standard deviation. According to Eq (15), after the graph convolution operation, the distance between any two classes is reduced by factor of lp-gl
p+(K 1-1y" On the other hand, according to Eq. (14), the standard deviation depends on the degree of nodes. Specifically, for node i with degree (i), its standard deviation is reduced by factor of /deg(1).
Implications for separability. For a node i, the probability of being mis-classified the prob- ability of its embedding falling out of its corresponding decision area. This probability depends on both the inter-class distance between classes (in terms of means) and the intra-class standard deviation. To compare the linear separability before and after the graph convolution operation, we scale the distance between classes before and after the graph convolution operation to be the same. Specifically, we scale h, as h p h, Note that classifying h; equivalent classifying [p-91
h4. Based on h', the distance between any two classes Cz, Cu is scaled to || - - = D, which is equivalent to the class distance before the graph convolution operation. Correspondingly, the Now, compare the miscclassification
standard deviation for h equals p+(K-1)
pp-q
ddegtt)
probability before and after the graph convolution, we only need to compare the standard devia- tions as the distances between classes in these two scenarios has been scaled to the same. More specifically, when p+(K (+-kg
the classiisifiinnnonn probability for node i re-
[p-9]
ddeg(t)
duced after the GCN model, otherwise, the mis-classification probability is increased after the (p-q)² GCN model. In other words, for nodes with degree larger than (p+(K-1)g)* the mis-classification
rate can be reduced after the graph convolution operation. This thereold is similar to the one we developed in Theorem 2 and similar analysis/discussions as those for Theorem 2 follows for the this multiple-class case.
G OTHER METRICS THAN COSINE SIMILARITY
The choice of similarity measure would not affect the results and conclusions significantly. We empirically demonstrate this argument by investigating two other metrics: Euclidean distance and Hellinger distance. The heatmaps based on these two metrics for Chamelon dataset is shown in Figure 11 in Appendix G. The patterns demonstrated in these two heatmaps are similar to those
21

---

Published as a conference paper at ICLR 2022
observed in Figure 5(b), where cosine similarity is adopted. Note that larger distance means lower similarity. Hence, the numbers in Figure should be interpreted in the opposite way as those in Figure 5.
0.70
1.25
0.59
0.59
0.65
0.64
0.69
1.03
1.05
1.21
1.21
1.25
2.15
0.60
1.10
1.05
0.65
0.61
0.46
0.47
0.51
1.21
1.13
0.85
0.89
0.93
0.64
0.61
0.47
0.42
0.48
0.50
1.21
1.14
0.89
0.8
0.88
0.95
0.50
0.45
0.69
0.67
0.51
0.48
0.47
1.25
1.2
0.93
0.88
0.86
2
0.40
2
3
(a) Euclidean Distance
(b) Hellinger distance
Figure 11: Cross-class neighborhood patterns on Chame eon based on different metrics than co- sine similarity metric.
H ADDITIONAL EXPERIMENTS WITH DIFFERENT SETTINGS
In this section, we discuss additional experiments for Section 3.3.1.
H.1 GENERATING GRAPHS WITH OTHER NEIGHBORHOOD DISTRIBUTIONS
In this section, we extend the experiments in Section 3.3.1 1 by including more patterns for neighbor- hood distributions. We aim illustrate if the neighborhood distribution for different classes (labels) are sufficiently distinguishable from each other, we should generally observe similar V-shape curves as in Figure 3 in Section 3. However, it is impractical to enumerate all possible neighborhood distributions. Hence, in this section, we include two additional neighborhood distribution patterns in Section H. 1.1 and two extreme patterns in Section H.1.2.
H.1.1 ADDITIONAL PATTERNS
Here, for both Cora and Citeseer, we adopt two additional sets of neighborhood distributions for adding new edges. For convenience, for Cora, we name the two neighborhood distribution patterns Cora Neighberhood Distribution Puttern I and Cora Neighborhood Distribution Pat- tern 2. Similarly. for Citeseer, we name the two neighborhood distribution patterns as Citeseer Neighborhood Distribution Pattern and Citeseer Neighborhood Distribution Patiern 2. We follow Algorithm generate graphs while utilizing these neighborhood distributions as the [D2 |CI-1 for Algorithm 1.
The two neighborhood distribution patterns for Cora listed bellow. Figure 12 and Figure 13 show GCN's 's performance on graphs generated from Cora following Cora Neighborhood Distribu- tion Pattern and Cora Neighborhood Distribution Pattern 2, respectively.
Cora Neighborhood Distribution Pattern I:
22

---

Published as a conference paper at ICLR 2022
1
Do Categorical [0, 3' 3' 3 0,0, OD)
Di : Categorical( 0,0,0,0 0, 3'3" 0),
Acourary
0.85
D2 : Categorical 0,0,0, 3'3
0.75
Da : Categorical
0,00,,0, 3.0
9.0.))). 1
0.65
3
1
D4 : Categorical
3 0, 3 0))
3
Hoooophll Ratio
1 3'
Ds Categorical
0, 3 0.0))
Performance of GCN on synthetic graphs from Cora. Graphs are generated follow- ing Cora Neighborhood Distribution Pattern
Figure 12:
1 2..000000000 0)..0).
D6 Categorical
Cora Neighborhood Distribution Pattern 2:
1
Dp Categorical [0.
0, 0,0,0),
2'
2"
D, Categorical
5, 0,000 0. 0,0,0 0)),
Accuracy
0.85
D2 0,
0.00
1
1
Da Categorical
5' 5'5 5''5" 5' 51.),,
1 D4 Categorical [0, 0,0, 2. 2.200 0),
0.70
0.16 the uEs 0.57 a52 044 D.z 1:30 U.50 0.2e 0 n.22 02 WIY S.R
Homophily
Ds Categorical(10, 3'3' 0, 3. 0.0))
Figure 13: Performance of GCN synthetic graphs from Cora. Graphs are generated follow- ing Cora Neighborhood Distribution Pattern 2 Clearly, the results demonstrated in Figure 12 and Figure 13 are similar to the black curve (n=0) in 3a. More specifically, they present V-shape curves.
De (1tegorica((000,00000000.
The two neighborhood distribution patterns for Citeseer are listed as bellow. Figure 14 and Fig- ure 15 show GCN's performance on graphs generated from Citeseer following Citeseer Neigh- borhood Distribution Pattern I and Citeseer Neighborhood Distribution Pattern 2, respectively.
Citeseer Neighborhood Distribution Puttern
0.85
Du Categorical(
2' 0,,,
1 1
8.75
D1 Categorical(( 3 0,0,0,
3 1b,
0.70
D2 Categorical(
_ 0,0,, 0,0,,0,0.5 ),),
2
Ds (0,00) 1,0).
0.55
0.5 159 03d u.8 SA: 039 5.30 225 928 22 518 03s ni4 512
Homophily
D4 Categorical((o..
3. 3 0, 7),
Figure 14: Performance of GCN on synthetic graphs from Citeseer. Graphs are gener- ated following Citeseer Neighborhood Distribu- tion Pattern I
1
D; Categorical [o. 3'3. 3. 0),
0, 0),
Citeseer Neighhorhood Distribution Pattern 2:
23

---

Published as a conference paper at ICLR 2022
1 Do : Categorical(O, 2' 2'
0,0]),
Acouracy
0.80
Dr : Categorical(( 2' 0, 0, 32 0),
0.75
D2 Categorical( 1,,0,0,1,0,000
1
1
0.65
0, 5'5)) Da Categorical( 5' 5'5'5"
0.40 CAt 0.25 6.33 1.28 0.24 22 1.1 0.5 624 Homophily Ratio
1
D4 Categorical(0,00) (0,0,0, (.. 1)
Figure 15: Performance of GCN on synthetic graphs from Citeseer. Graphs are gener- ated following Citeseer Neighborhood Distribu- tion Patter 2
Ds Categorical (0, (,,00 2' 0)). 0)),
Clearly, the results demonstrated in Figure 14 and Figure 15 are similar the black curve (y=0) 3b. More specifically, they present V-shpe curves.
H.1.2 EXTREME NEIGHBORHOOD DISTRIBUTION PATTERNS
In this subsection, we further extend the experiments in Section 3.3.1 by investigating "extreme" neighborhood distribution patterns suggested by WXGg. More specifically, these two patterns "a given label are connected to a single different label" and "a given label are connected to all other labels other excluding its own label". For convenience, we denote these two types of neigh- borhood distributions as single and all, respectively. We utilize these neighborhood distributions
as {D,) |C1-1 for generating synthetic graphs. Next, we first present the results for Cora with analysis for both the single and all neighborhood distribution patterns. Then, we present the results for Citeseer but omit analysis and discussion since the observations are similar to those we make for Cora.
Note that to ensure "a label is only connected to single different label". need to group the labels into pairs and "connect them".. Since there are different ways group labels into pairs, there exists various ways formulate the single neighborhood distributions. We demonstrate one of the single neighborhood distributions as all the other possible are symmetric each other. For Cora, the single neighborhood distribution we adopted as follows. Note that there are labels Cora, and we could not pair all the labels. Thus, we leave one of labels (label our setting) untouched, i.e, it is not connect to other labels during the edge addition process.
Do Categorical [0, 1,0, 0,0,00000 0),),
Di : Categorical (11, 0, 0, 0, 0)).
D2 Categorical((0, 1,,
D3 Categorical 0,000000,,
D4 Categorical (,,0o,,,,,,,,,,,,,,,,,,, 0,0,0,00,00)
Ds Categorical [0. 0, 0,0,0,0,0011
Da Categorical [0, 0,000,00000 0,0,0,0,0110
The GCN's performance on these graphs generated from Cora following the single neighborhood distribution pattern is shown in Figure 16a. It clearly presents a V-shape curve. Almost perfect performance can be achieved when the homophily ratio gets close to 0. This is because the single neighborhood distributions for different labels are clearly distinguishable from each other. We fur- ther demonstrate the heatmap of cross-class similarity for the generated graph with homophily ratio 0.07 (the right most point in Figure 16a) Figure 16b. Clearly, this graph has very high intra-class similarity and very low inter-class similarity, which explains the good performance.
For Cora, the all neighborhood distribution patterns can be described as follows.
1
1
Do Categorical
6*
6'
6'
6
6'
1
1
1
Dj Categorical
((
0.
6'
6
6'
6.
1
Da Categorical
6
6
0.
6'
6
24

---

Published as a conference paper at ICLR 2022
0.8
0.8
6.85
0.30
6.75
02
065
0.74
0.68
0.30
E.46
0.3
63
035
932
636
032
3.55
0.6
3.7
Himmpphlyy
(a) Performance of GCN on synthetic graphs from Cora. Graphs are gen-
(b) Cross-class neighborhood
crated following single neighborhood distribution.
similarity for the graph generated from Cora following single with
homophily ratio 0.07 (the right most point in Figure 16a).
Figure 16: Cora: single neighborhood distribution pattern
P3 : Categorical
6
6
6
24 Categorical(
6
6
6'
6
D. Categorical(
0,
6
6
6'
6
1
Do Categorical
0))
6
6
6'
The GCN's performance on these graphs generated from Cora following the all neighborhood distribution pattern is shown in Figure 17a. Again, it clearly presents a V-shape curve. However, the performance not perfectly good even when add extremely large number of edges. For example, for the right most point Figure 17a, we add almost as 50 times many as edges into the graph and the homophily ratio is reduced to 0.03 while GCN's performance for it is only around 70%. This because the all neighborhood distributions for different labels are not casily distinguishable from each other. More specifically, any two neighborhood distributions for different labels in all are very similar each other (they share "4 labels"). We further empirically demonstrate this by providing the heatmap cross-clas similarity for the generated graph with homophily ratio 0.03 (the right most point in Figure 17)) in Figure 17b. As per our discussion in Observation 2, this graph is with not such "good" heterophily and GCNs cannot produce perfect performance for it. This observation further demonstrates our key argument that the distinguishability of the distributions for different labels important for performance.
For Ci teseer, the single neighborhood distribution adopted is follows. The GCN's perfor- mance on these graphs generated from Citeseer following the single neighborhood distribution pattern is shown in Figure 18a. The heatmap of cross-class similarity for the generated graph with homophily ratio 0.06 (the right most point in Figure 18a) in Figure 18b.
Do Categorical 1, 0,0,
Categorical((11,.) 0, 0,
D2 Categorical 0, 1,0,0),
D3 Categorical 1,
D4 Categorical [0, 0, 0, 1)).
Ds Categorical 0,
For Citeseer, the all neighborhood distribution patterns can described as follows. The GCN's performance on these graphs generated from Citesees following the all neighborhood distribu- tion pattern is shown in Figure 19a. The heatmap of cross-class similarity for the generated graph with homophily ratio 0.01 (the right most point in Figure 19a) in Figure 19b.
Do : Categorical( (0, 1/5, 55, 1/5 1/5, 1/5)),
25

---

Published as a conference paper at ICLR 2022
08
0.8
Accurer
0.
0.8
0.6
0.5
02
0.4
3GL
3.5
159
245
638
933
652
833
633 Homophiy
635
0.5
6.06
007
606
0.5
104
3.3
E607
333
(a) Performance of GCN on synthetic graphs from Cora. Graphs are gen- crated following all neighborhood distribution.
(b) Cross-class neighborhood
similarity for the graph generated
from Cora following all with
homophily ratio 0.03 (the right most point in Figure 17a).
Figure 17: Cora: all neighborhood distribution pattern
0.67
0.53
08
0.01
0.8
0.94
3.15
0.0
5.0
0.8
0.15
13
04
02
0.0
0.0
0.0
0.5
0.11
1.0
0.51
221
632
(a) Performance of GCN on synthetic graphs from Citeseer. Graphs are generated following single neighborhood distribution.
(b) Cross-class neighborhood similarity for the graph generated from Citeseer following single with homophily ratio 0.06.
Figure 18: Citeseer: single neighborhood distribution pattern
Di : Categorca((115..01115./5// 1/5)),
D) Categprica((1/_.115...11 1/5, 1/5)),
Da (inggorica(11/,1//,11,1 1/5,, 1/5)),
D4 (1/,),,c
Ds ( 1/5, 1/5
Similar observations as those we made for Cora can be made for Citeseer, hence we do not repeat the analysis here.
LIMITATION
Though we provide new perspectives and understandings of GCN's performance on heterophilous graphs, our work has some limitations. To make the theoretical analysis more feasible, we make few assumptions. We dropped the non-linearity in the analysis since the main focus of this paper is the aggregation part of GCN. While the experiment results empirically demonstrate that our analysis seems to hold with non-linearity, more formal investigation for GCN with non-linearity is valuable. Our analysis in Theorem 2 assumes the independence between features, which limits the generality of the analysis and we would like to conduct further instigation to more general case. We provide theoretical understanding GCN's performance based on CSBM, which stands for type of graphs
26

---

Published as a conference paper at ICLR 2022
1.4
0.62
0.82
0.
0.8
0.5
6:2
0.81
0.99
9.5
0.81
0.63
0.8
0.5
8.81
0.3
6.6
2:39
0.81
8.8
02
0.83
0.61
0.09
334
250
848
235
628
934
838
634 Homophily
633
0.5
6.0
0.55
0.04
0.00
0.5
032
030
331
(a) Performance of GCN on synthetic graphs from Citeseer. Graphs are generated following all neighhorhood distribution.
neighborhood similarity for the graph generated from Citeseer following all with homophily ratio 0.01.
(b) Cross-class
Figure 19: Citeseer: all neighborhood distribution pattern
attracting increasing attention in the research community. However, it is ideal for modeling sparse graphs, which are commonly observed in the real-world. Hence, is important to devote more efforts to analyzing more general graphs. We believe our results established solid initial study for further investigation. Finally, our current theoretical analysis majorly focuses on the GCN model; we hope to extend this analysis in the future to more general pessage-passing neural networks.
J BROADER IMPACT
Graph neural networks (GNNs) are a prominent architecture for modeling and understanding graph- structured data in variety of practical applications. Most GNNs have a natural inductive bias towards leveraging graph neighborhood information make inferences, which can exacerbate unfair or biased outcomes during inference, especially when such neighborhoods are formed according inherently biased upstream processes, e.g. rich-get-richer phenomena and other disparities in the opportunities to "connect" to other nodes: For example, older papers garner more citations than newer ones, and are hence likely to have higher in-degree in citation networks and hence benefit more from neighborhood information; similar analogs can be drawn for more established webpages attracting more attention in search results. Professional networking ("ability to connect") top-tier, well-funded universities compared
may be easier for those individuals (nodes) who to those who are not. Such factors influence network formation, sparsity, and thus GNN inference quality simply due to network topology (Tang et al., 2020b). Given these acknowledged issues, GNNs are still used in applications including ranking (Sankar et al., 2021), recommendation((ing and Molino), engagement prediction (Tang et al., 2020a), traffic modeling(Jiang and Luo, 2021), search and discovery ( (Ying al., 2018) and more, and when unchecked, suffer traditional machine learning unfairness issues (Dai and Wang, 2021).
Despite these practical impacts, the prominent notion in prior literature in this space has been that such methods are inapplicable or perform poorly heterophilous graphs, and this may have miti- gated practitioners' interests in applying such methods for ML problems in those domains conven- tionally considered eeterophily-dommiann (e.g. dating networks). Our work shows that this notion is misleading, and that heterophily and homophily are not themselves responsible for good or bad in- ference performance. We anticipate this finding to be helpful in furthering research into the capacity of GNN models work in diverse data settings, and emphasize that our work provides under- standing, rather than a new methodology or approach, and thus do not anticipate negative broader impacts from findings.
ACKNOWLEDGEMENTSS
This research is supported by the National Science Foundation (NSF) under grant numbers II1171474,, CNS1815636, IIS1845081, I1S1907704, I1S1928278, II$1955285, 10$2107215, and
27

---

Published as a conference paper at ICLR 2022
IOS2035472, the Army Research Office (ARO) under grant number W91 INF-111--- the Home Depot, Cisco Systems Inc and Snap Inc.
28


Reviews:
[{"review_id": "uqd90ovs3Y2", "reviewer": "Reviewer_MC2o", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nHowever, 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. \nThe 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. \n\nIn 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. \n\nAt 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.\n\nSome further technical comments:\n\nThe 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.\n\nWhile 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)\n\nThere are at least some problematic aspects with this analysis:\n1) 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.\n\n2) 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. \n\n3) Dropping the nonlinearity, while done in practice, is clearly another strong simplification which would merit some more discussion I think.\n\nFinally, 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.\n\nMinor comments\np.2 last line -- X is never defined, instead H and H' are used as input/output. Please correct.\n\n", "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. \nThe 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. ", "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).\n\nThe paper should be improved with respect to the following points (see above for more detailed suggestions and comments)\na) provide a more nuanced appraisal of literature and the role of homophily/heterophiliy\nb) discuss the roles of the correlation structure between node labels and features more clearly\nc) discuss the role of self-loops/ego embedding in mixing information from different classes\nd) provide a more rigorous discussion on the assumptions and shortcomings of the theoretical analysis and the SBM model.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "tYEU09vD4a", "reviewer": "Reviewer_WXGg", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nFirst, 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?\n\nRelated 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?\n\nSecond, 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? \n\nThird, 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. \n\nFourth, 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)?\n", "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).\n", "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:\n\n- Table 1 and the following description cannot justify how GCNs outperform other models.\n- The edge addition algorithm does not control the degrees, which is the core control variate for the experiments.\n- The two-class graph results seem to be insufficient for the main claim.\n- Only one specific instance of the degree distribution $\\mathcal{D}_c$ for edge addition is used for the experiments.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "m8Vt9BsVUx", "reviewer": "Reviewer_YLxN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\nThe authors provide some valuable arguments about the performance of GCN on heterophilous graphs and verify the claims with some empirical results.\n\nWeakness&Advice:\n\n1. In the last line of page 2, where is $X$ in the equation?\n\n2. 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?\n\n3. Kenta’s work does not drop non-linearity in their analysis.\n\n4.  Could you please clarify the significance of theorem 1? What is its relation with heterophily and homophily in definition 1?\n\n5. Why do you use cosine similarity to define inter-class distance? What is its advantages over other metrics?\n\n6. Font size in figure 5 is too small. The dark blue background make it hard to read the value on it.\n\n7. 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.\n\n8. Can your theoretical analysis on CSBM generalize to multiple classes or to more general graphs.", "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.\n", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "BbxobQXujmm", "reviewer": "Reviewer_6L9A", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n1.\tIt provides a deeper insights into the heterophily problem and help us understand the GCNs’ performance.\n2.\tIt also designs a new cross-class neighborhood similarity metric to help explain the performance of GCN on various graphs (although it is not perfect).\n3.\tThe writing is generally clear.\n\n\nWeakness and Questions:\n1.\tThe analysis is only limited to GCNs, while the paper title is too general (GNNs). Not very \n2.\tOne 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.\n3.\tThe 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). \n4.\tAlthough 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?\n", "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. ", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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)