Year: 2021

Abstract:
In node classification tasks, heterophily and oversmoothing are two problems that can hurt the performance of graph convolutional neural networks (GCNs). The heterophily problem refers to the model’s inability to handle heterophilous graphs where neighboring nodes belong to different classes; the oversmoothing problem refers to the model’s degenerated performance with increasing number of layers. These two seemingly unrelated problems have been studied mostly independently, but there is recent empirical evidence that solving one problem may benefit the other. In this work, beyond empirical observations, we aim to: (1) analyze the heterophily and oversmoothing problems from a unified theoretical perspective, (2) identify the common causes of the two problems based on our theories, and (3) propose simple yet effective strategies to address the common causes. In our theoretical analysis, we show that the common causes of the heterophily and oversmoothing problems—namely, the relative degree of a node (compared to its neighbors) and its heterophily level—trigger the node representations in consecutive layers to "move" closer to the original decision boundary, which increases the misclassification rate of node labels under certain constraints. We theoretically show that: (1) Nodes with high heterophily have a higher misclassification rate. (2) Even with low heterophily, degree disparity in a node’s neighborhood can influence the movements of node representations and result in a "pseudo-heterophily" situation, which helps to explain oversmoothing. (3) Allowing not only positive, but also negative messages during message passing can help counteract the common causes of the two problems. Based on our theoretical insights, we propose simple modifications to the GCN architecture (i.e., learned degree corrections and signed messages), and we show that they alleviate the heteorophily and oversmoothing problems with extensive experiments on nine real networks. Compared to other approaches, which tend to work well in either heterophily or oversmoothing, our modified GCN model performs well in both problems.

heading: 1 INTRODUCTION
text: In recent years, GCNs (Defferrard et al., 2016; Kipf & Welling, 2016; Veličković et al., 2017) have been widely used in applications ranging from social science (Li & Goldwasser, 2019) and biology (Yan et al., 2019) to program understanding (Allamanis et al., 2018; Shi et al., 2019). A typical GCN architecture (Gilmer et al., 2017) for the node classification task can be decomposed into two main components: propagation/aggregation, and combination. Messages are first exchanged between neighboring nodes, then aggregated. Afterwards, the messages are combined with the self-representations (a.k.a., the current node representations) to update the node representations. Though GCNs are effective, they have some key limitations.
The first limitation is the “oversmoothing" problem (Li et al., 2018): the performance of GCNs degrade when stacking many layers. Recent work has found that oversmoothing could be caused by GCNs exponentially losing expressive power in the node classification task (Oono & Suzuki, 2019) and that the node representations converge to a stationary state which is decided by the degree of the nodes and the input features (Chen et al., 2020; Wang et al., 2019; Rong et al., 2019; Rossi et al., 2020). These works focus on the analysis of the steady state in the limit of infinite layers, but they do not explore the dynamics on how oversmoothing is triggered, or which nodes tend to cause it. Other works like (Xu et al., 2018; Wang et al., 2019; Chen et al., 2020) focus on heuristic-based model designs to alleviate the oversmoothing problem. To fill this gap, we seek to theoretically analyze the dynamics around oversmoothing. In our empirical analysis, by dividing the nodes in real graphs into
several degree groups and tracking their average accuracy while increasing the layers of GCN (Kipf & Welling, 2016), we observe two phases (Fig. 1): the initial stage when higher-degree nodes have higher accuracy and the developing stage when the accuracy of higher-degree nodes decreases more sharply (cf. § 5.4 for details). As we will show theoretically and empirically, the low-degree nodes are the ones that trigger oversmoothing. Though Chen et al. (2020) provide some explanations for the developing stage by analyzing the convergence rate, their theory fails to characterize the initial stage. In fact, we find that the analysis of initial stage provides valuable insights about oversmoothing.
The second limitation of GCNs is their poor performance on heterophilous graphs (Pei et al., 2019; Lim et al., 2021), which—unlike homophilous graphs—have many neighboring nodes that belong to different classes (Newman, 2002). For instance, in protein networks, amino acids of different types tend to form links (Zhu et al., 2020), and in transaction networks, fraudsters are more likely to connect to accomplices than to other fraudsters (Pandit et al., 2007). Most GCNs (Kipf & Welling, 2016; Veličković et al., 2017) fail to effectively capture heterophily, so emerging works have proposed some effective designs (Pei et al., 2019; Zhu et al., 2020), including signed messages (positive and negative interactions between nodes) proposed by concur-
rent works (Chien et al., 2021; Bo et al., 2021). Though these works justify signed messages from a spectral perspective, they focus on asymptotic results, requiring an infinite number of filters. Our work does not make this assumption, and our theory works in more practical scenarios (§ 3.4).
These two limitations have mostly been studied independently, but recent work on oversmoothing (Chen et al., 2020) was shown empirically to address heterophily, and vice versa (Chien et al., 2021). Motivated by this empirical observation, we set out to understand the theoretical connection between the oversmoothing and heterophily problems by studying the change in node representations during message passing. Specifically, we make the following contributions:
• Theory: We introduce the first theory that explains the connections between heterophily and oversmoothing which opens up the possibility of jointly studying the two problems. • Insights: We find that under conditions, the relative degree of a node (compared to its neighbors) and its heterophily level affect the misclassification rate of node labels in the oversmoothing and heterophily problems. We further prove that signed messages can mitigate their negative impact. • Improved model & empirical analysis: Based on these insights, we design a generalized GCN model, GGCN, that allows negative interactions between nodes and compensates for the effect of low-degree nodes through a learned rescaling scheme. Our empirical results show that our model is robust to oversmoothing, achieves state-of-the-art performance on datasets with high levels of heterophily, and achieves competitive performance on homophilous datasets.

heading: 2 PRELIMINARIES
text: We first provide the notations & definitions that we use in the paper, and a brief background on GCNs.
Notation. We denote an unweighted and self-loop-free graph as G (V , E) and its adjacency matrix as A. We represent the degree of node vi ∈ V by di, and the degree matrix—which is a diagonal matrix whose elements are node degrees—by D. Let Ni be the set of nodes directly connected to vi, i.e., its neighbors. I is the identity matrix. We denote the node representations at l-th layer as F(l), and the i-th row of F is f (l)i , which is the representation of node vi. The input node features are given by F(0). The weight matrix and bias vector at the l-th layer are denoted as W(l) and b(l), respectively.
Homophily and Heterophily. Given a set of node labels/classes, homophily captures the tendency of a node to have the same class as its neighbors. Specifically, the homophily of node vi is defined as hi ≡ E ( |N si | |Ni| ) , where N si is the set of neighboring nodes with the same label as vi, | · | is the cardinality operator, and the expectation is taken over the randomness of the node labels. High homophily corresponds to low heterophily, and vice versa, so we use these terms interchangeably.
Supervised Node Classification Task. We focus on node classification: given a subset of labeled nodes (from a label set L), the goal is to learn a mapping F : f (0)i 7→ yi between each node vi and its ground truth label yi ∈ L. We use ŷi to represent the predicted label of vi and define the misclassification rate of a fixed learnt model over a node set V as: E ( |{vi|ŷi 6=yi,vi∈V}|
|V|
) . The
expectation is taken over the randomness of graph structures and input node features.
Graph Convolutional Neural Networks. In node classification tasks, an L-layer GCN contains two components (Gilmer et al., 2017): (1) neighborhood propagation and aggrega-
tion: f̂ (l)i = AGGREGATE(f (l) j , vj ∈ Ni), and (2) combination: f (l+1) i = COMBINE(f̂ (l) i , f (l) i ), where AGGREGATE and COMBINE are learnable functions. The loss is given by LCE=CrossEntropy(Softmax(f (L) i W
(L) + b(L)), yi). The vanilla GCN suggests a renormalization trick on the adjacency A to prevent gradient explosion (Kipf & Welling, 2016). The (l + 1)-th output is given by: F(l+1) = σ(ÃF(l)W(l)), where Ã = D̃−1/2(I + A)D̃−1/2, D̃ is the degree matrix of I + A, and σ is ReLU. When the non-linearities in the vanilla GCN are removed, it reduces to a linear model called SGC (Wu et al., 2019), which has competitive performance and is widely used in theoretical analyses (Oono & Suzuki, 2019; Chen et al., 2020). For SGC, the l-th layer representations are given by: F(l) = ÃlF(0) and the last layer is a logistic-regression layer: ŷi = Softmax(F(L)W(L) + b(L)). We note that only one weight matrix W(L) is learned; it is equivalent to the products of all weight matrices in a linear GCN. Find more related works in § 6.

heading: 3 THEORETICAL ANALYSIS
text: In this section, we formalize the connection between the oversmoothing and heterophily problems in two steps: (1) We show how the movements of node representations relate to the misclassification rate of node labels; and (2) we identify the factors that affect the movements of representations. We use the SGC model to analyze binary node classification with nodes in class 1 denoted as set V1 and nodes in class 2 denoted as set V2. We show empirically (§ 5) that the insights obtained in this section are effective for other non-linear models in multi-class classification.

heading: 3.1 ASSUMPTIONS
text: Next, we use “i.d.” to represent random variables/vectors that follow the same marginal distribution and their joint probability density function (PDF) is a permutation-invariant function p(x1, . . . ,xn) = p(P(x1, . . . ,xn)), where P(·) means permutation. (1) Random graph: Node degrees {di} are i.d. random variables. {(·)i} represents a set with i = 1, . . . , |V|. (2) Inputs: (2.1) Node labels {yi} are i.d. Bernoulli random variables given by the ratio ρ: ρ ≡ P(yi=1)P(yi=2) ,∀i. (2.2) Initial input node features {f (0) i } are i.d. random vectors given by (PDF)
f(x), which is expressed as: f(x) = { f1(x), when yi = 1. f2(x), when yi = 2. E(f (0)i |yi) = { µ, when yi = 1. −ρµ, when yi = 2. so E(f (0)i ) = 0. (3) Independence: {di} are independent of {yi} and {f (0) i }.

heading: 3.2 MISCLASSIFICATION RATE & MOVEMENTS OF NODE REPRESENTATIONS
text: The following lemmas illustrate why the movements of node representations are a good indicator of SGC’s performance. We view the changes of node representations across the layers as their movements; i.e., f (l+1)i is moved from f (l) i ,∀i. The misclassification rate of an L-layer SGC is determined by {f (L)i }, which is the input to the last regression layer, and can be studied through the decision boundary of f (L)i .
Lemma 1 In SGC, the decision boundaries w.r.t. {f (L)i } in multi-class classification are linear hyperplanes. In particular, the decision boundary is a single hyperplane for binary classification. Proof. We provide the proof in App. A.1. The decision boundary of an (L + 1)-layer SGC can be viewed as a perturbation to the decision boundary of an L-layer SGC due to the movements from {f (L)i } to {f (L+1) i }. Due to Lemma 1, we can use the hyperplane xw + b = 0 to represent the decision boundary of {f (L)i }, where w is a unit vector, b is a scalar, and the {f (L)i } are classified to class 1 if f (L) i w + b > 0. Suppose when w = w∗ and b = b∗, we find an optimal hyperplane xw∗ + b∗ = 0 that achieves the lowest
total misclassification rate (§ 2) for {f (L)i }. Due to the movements of node representations, the new optimal hyperplane is decided by: xw∗′ + b∗′ = 0. In Lemma 2, we show that, under constraints, moving towards the original decision boundary with a non-zero step results in a non-decreasing total misclassification rate under the new decision boundary.
Lemma 2 Moving representations {f (L)i } from class 1 by adding −tw∗ T , t > 0, s.t. w∗Tw∗′ > 0, the new total misclassification rate is no less than the misclassification rate before the movements. Proof. We provide the proof in App. A.2.
Note that the special case where the representations of the two classes swap positions (e.g, bipartite graphs) violates the condition w∗Tw∗′ > 0 and leads to different conclusions. We refer to the condition w∗Tw∗′ > 0 as "non-swapping condition" and throughout the paper, we analyze SGC under that. Lemma 2 shows that, under the "non-swapping condition", if {f (l)i } move towards the original decision boundary (or the other class), SGC tends to perform worse.

heading: 3.3 MOVEMENTS OF NODE REPRESENTATIONS IN SHALLOW AND DEEPER LAYERS
text: In the following theorems, we will show how relative degree and homophily level will affect the movement of node representations in both shallow and deeper layers. We show results given the degree, di, of node vi and assume that vi is in class 1. The results in class 2 can be derived similarly.

heading: 3.3.1 INITIAL STAGE: SHALLOW LAYERS
text: Theorem 1. [Initial Stage] Under the "non-swapping condition", during message passing in shallow layers, the nodes with low homophily hi ≤ ρ1+ρ and the nodes with high homophily hi > ρ 1+ρ but
small relative degree are prone to be misclassified. Defining rij ≡ √
di+1 dj+1 and the relative degree ri ≡ EA|di,vi∈V1( 1di ∑ j∈Ni rij), the conditional expectation of representation f (1) i is given by:
E A,{yi},{f (0)i }|di,vi∈V1 (f (1) i |vi ∈ V1, di) =
( ((1 + ρ)hi − ρ)diri + 1
di + 1
) E(f (0)i ) ≡ γ 1 i E(f (0) i ), (1)
where the multiplicative factor γ1i is:
γ1i ∈  (−∞, 12 ], if hi ≤ ρ 1+ρ (0, 1], if hi > ρ1+ρ & ri ≤ 1
(1+ρ)hi−ρ (1,∞), otherwise.
(2)
Proof. We provide the proof in App. A.3.
From Thm. 1, we identify three types of movements of node representations, which are characterized by relative degree ri and homophily level hi. For illustration purposes, in Fig. 2, we illustrate the three cases when we apply our theorem to 1D node representations. The bars reflect the value change of vi’s node representation. Intuitively, under heterophily (case 1) or under high homophily but low degrees (case 2), the expected representations will move heavily towards the opposing class. Otherwise, they will move away from the opposing class (case 3). Among the three cases, only nodes with high homophily and high relative degree benefit from propagation and aggregation.
Explanation of the heterophily and oversmoothing problems: • In heterophilous graphs, node representations move heavily towards the opposite class. According
to Lemma 2, under the "non-swapping" condition, it indicates higher misclassification rate (i.e., poorer performance) for SGC. • In homophilous graphs, high-degree nodes may initially benefit (case 3), leading to performance gain in shallow layers. However, the representations of low-degree nodes tend to move towards the opposing class (case 2) and eventually flip the labels. The misclassification of low-degree nodes causes a pseudo-heterophily situation (case 1) later.

heading: 3.3.2 DEVELOPING STAGE: DEEPER LAYERS
text: The following theorem analyzes the pseudo-heterophily scenario in deeper layers. Based on Thm. 1, message passing will result in scaling the node representations (γ1i ) and some nodes may cross the origin. To account for those, let ξli be an accumulated discount factor at the l-th layer and
E A,{yi},{f (0)i }|di
( f (l) i di+1 |di ) = ξliµ. Conditioned on A and ξ l i, the nodes contributing positively
are defined as: N̂ si (A, ξli) ≡ {vj |vj ∈ Ni and (ξliµ) · E{yi},{f (0)i }|ξli,A
( f
(l) j T |ξli,A ) > 0}. We
denote: E A,{yi},{f (0)i }|di,ξli,vj∈Ni
( f
(l) j rij |di, ξli, vj ∈ Ni
) = { ξli ′ µ vj ∈ N̂ si (A, ξli)
−ρliξli ′ µ vj 6∈ N̂ si (A, ξli)
. ξli ′ and
ρli characterize the neighborhood property of vi. We further define the effective homophily of node i as ĥli = P(vj ∈ N̂ si |vj ∈ Ni, di, ξli). Intiuitively, even if the original graph is not heterophilous, from the perspective of message passing under this pseudo-heterophily scenario, the deeper layers will act as if the graph is more heterophilous than it truly is, which may increase the misclassification rate. Theorem 2. [Developing Stage] Under the “non-swapping condition”, during message passing in deeper layers, when the effective homophily ĥli is sufficiently low (ĥli ≤
ρli 1+ρli
), the nodes with higher effective relative degree are prone to misclassification. Specifically, by defining the effective relative degree as r̄il ≡ ξ l i ′
ξli , the conditional expectation of f (l+1)i is:
E A,{yi},{f (0)i }|di,ξli)
( f
(l+1) i |di, ξ l i)
) = ( (ĥli(1 + ρ l i)− ρli)dir̄il + 1 ) di + 1 ξliµ ≡ γ (l+1) i E(f (0) i ). (3)
Proof. We provide the proof in App. A.4. Other nodes can be derived similarly. We note that Eq. (3) holds for layers l ≥ 2 in general. We regard layers for which ĥli >
ρli 1+ρli
holds for most nodes i as part of the initial stage, as they exhibit three cases similar to Eq. (2).

heading: 3.4 SIGNED MESSAGES & MOVEMENTS OF REPRESENTATIONS
text: In this section, we provide theory to show that signed messages can help enhance the performance in heterophilous graphs and also alleviate oversmoothing. Due to limited space, we only show the effect of signed messages in the initial stage; similar results can be derived in the developing stage.
Setup. Signed messages consist of the negated messages sent by neighbors of the opposing class (i.e., after multiplying initial messages by -1), and the unchanged messages ("positive messages") sent by neighbors of the same class. In reality, ground-truth labels are not accessible for every node, so we use approximations, which introduces errors. For node vi, we define mli as the ratio of neighbors that send incorrect messages at the l-th layer (i.e., different-class neighbors that send non-negated messages and same-class neighbors that send negated messages). We define the l-th layer error rate as eli = E(mli), where the expectation is over the randomness of the neighbors that send incorrect messages. We make the following assumption: mli is independent of {di}, {yi} and {f0i }. Theorem 3. [Signed Messages] With the independence assumptions and under the “non-swapping condition”, by allowing the messages to be optionally multiplied by a negative sign, in the initial stage, the movements of representations will be less affected by the initial homophily level hi, and will be dependent on the error rate eli. Specifically, the multiplicative factor γ1i at the first layer is:
E A,{yi},{f (0)i }|di,vi∈V1 (f (1) i |di, vi ∈ V1) =
( (1− 2e0i )(ρ+ (1− ρ)hi)diri + 1
di + 1
) µ ≡ γ1i E(f (0) i ),
(4)
where γ1i ∈  (−∞, 12 ], if e 0 i ≥ 0.5
(0, 1], if e0i < 0.5 & ri ≤ 1(1−2e0i )(ρ+(1−ρ)hi) (1,∞), otherwise.
(5)
Proof. The proof is provided in App. A.5. From Eq. 5, we see that when using signed messages, to benefit from case 3 (γ1i > 1), the minimum relative degree satisfies: ri > 1(1−2e0i )(ρ+(1−ρ)hi) . Given hi ≤ 1, if the error rate is low (e 0 i 0.5), we get: 1 (1−2e0i )(ρ+(1−ρ)hi) ≤ 1(1+ρ)hi−ρ , and 1
(1+ρ)hi−ρ is the minimum relative degree required when not using signed messages. This implies that more nodes can benefit from using signed messages. We note that if low error rate cannot be guaranteed, signed messages may hurt the performance.

heading: 4 MODEL DESIGN
text: Based on our theoretical analysis, we propose two new, simple mechanisms to address both the heterophily and oversmoothing problems: signed messages and degree corrections. We integrate these mechanisms, along with a decaying combination of the current and previous node representations (Chen et al., 2020), into a generalized GCN model, GGCN. In § 5, we empirically show its effectiveness in addressing the two closely-related problems.

heading: 4.1 SIGNED MESSAGES
text: Thm 3 points out the importance of signed messages in tackling the heterophily and oversmoothing problems. Our first proposed mechanism uses cosine similarity to send signed messages.
For expressiveness, as in GCN (Kipf & Welling, 2016), we first perform a learnable linear transformation of each node’s representation at the l-th layer: F̂(l) = F(l)W(l) +b(l) Then, we define a sign function to be multiplied with the messages exchanged between neighbors. To allow for backpropagation of the gradient information, we approximate the sign function with cosine similarity. Denote Sl as the matrix which stores the sign information about the edges, defined as: S(l)[i, j] =Cosine(f (l)i , f
(l) j ) if (i 6= j) & (vj ∈ Ni); 0 otherwise.
In order to separate the contribution of similar neighbors (likely in the same class) from that of dissimilar neighbors (unlikely to be in the same class), we split S(l) into a positive matrix S(l)pos and a negative matrix S(l)neg. Thus, our proposed GGCN model learns a weighted combination of the self-representations, the positive messages, and the negative messages:
F(l+1) = σ ( α̂l(β̂l0 F̂ (l) + β̂l1 (S (l) pos Ã)F̂(l)+ β̂l2(S (l) neg Ã)F̂(l)) ) , (6)
where β̂l0, β̂ l 1 and β̂ l 2 are scalars obtained by applying softmax to the learned scalars β l 0, β l 1 and βl2; the non-negative scaling factor α̂l = softplus(α l) is derived from the learned scalar αl; is element-wise multiplication; and σ is the nonlinear function Elu. We note that we learn different α and β parameters per layer for flexibility. We also require the combined weights, α̂lβ̂lx, to be non-negative so that they do not negate the intended effect of the signed information.

heading: 4.2 DEGREE CORRECTIONS
text: Our analysis in § 3.3 and § 3.4 highlights that, when the error rate and homophily level are high, oversmoothing is initially triggered by low-degree nodes. Thus, our second proposed mechanism aims to compensate for low degrees via degree corrections.
Based on Eq. (5), and given that most well-trained graph models have a relatively low error rate at the shallow layers (i.e, eli 0.5 for small l), we require that the node degrees satisfy ri > 1 (1−2e0i )(π+(1−π)hi) to prevent oversmoothing. Since the node degrees cannot be modified, our strategy is to rescale them. Specifically, we correct the degrees by multiplying with scalars τ lij and change the original formulation as follows:
(ÃF̂(l))[i, :] = F̂(l)[i, :]
di + 1 + ∑ vj∈Ni F̂(l)[j, :]√ di + 1 √ dj + 1 =⇒ ∑ vj∈Ni τ li,j F̂(l)[j, :] √ di + 1 √ dj + 1 . (7)
This multiplication is equivalent to changing the ratio rij in Thm. 1 to
√ (τ lij) 2(di+1)
dj+1 . That is, a larger
τ lij increases the effective ri at layer l. Training independent τ l i,j is not practical because it would require O(|V|2) additional parameters per layer, which can lead to overfitting. Moreover, low-rank parameterizations suffer from unstable training dynamics. Intuitively, when rij is small, we would like to compensate for it via a larger τ li,j . Thus, we set τ l i,j to be a function of rij as follows:
τ lij = softplus ( λl0 ( 1 rij − 1 ) + λl1 ) , (8)
where λl0 and λ l 1 are learnable parameters. We subtract 1 so that when rij = 1 (i.e., di = dj), then
τ lij = softplus(λ l 1) is a constant bias.
In our proposed GGCN model, we combine the signed messages in Eq. (6) and our degree correction mechanism to obtain the representations at layer l + 1:
F(l+1) = σ ( α̂l ( β̂l0F̂ (l) + β̂l1( S (l) pos Ã T (l) )F̂(l) + β̂l2( S (l) neg Ã T (l) )F̂(l) )) , (9)
where T (l) is a matrix with elements τ lij .

heading: 4.3 DECAYING AGGREGATION
text: In addition to our two proposed mechanisms that are theoretically grounded in our analysis (§ 3), we also incorporate into GGCN an existing design—decaying aggregation of messages—that empirically increases performance. However, we note that, even without this design, our GCN architecture still performs well under heterophily and is robust to oversmoothing (App. §B.1).
Decaying aggregation was introduced in (Chen et al., 2020) as a way to slow down the convergence rate of node representations. Inspired by this work, we modify the decaying function, η̂, and integrate it to our GGCN model:
F(l+1) = F(l) + η̂ ( σ ( α̂l(β̂l0F̂ (l)+β̂l1(S (l) pos Ã T (l))F̂(l) + β̂l2(S (l) neg Ã T (l))F̂(l)) )) , (10)
In practice, we found that the following decaying function works well: η̂ ≡ ln( η lk +1), iff l ≥ l0; η̂ = 1, otherwise. The hyperparameters k, l0, η are tuned on the validation set.

heading: 5 EXPERIMENTS
text: Due to the space limit, in the main paper, we focus on the following three questions: (Q1) Compared to the baselines, how does GGCN perform on homophilous and heterophilous graphs? (Q2) How robust is it against oversmoothing under homophily and heterophily? (Q3) How can we verify the correctness of our theorems on real datasets? We provide the ablation study of signed messages and degree correction in App. § B.1 and the study of different normalization strategies in App. § B.2.

heading: 5.1 EXPERIMENTAL SETUP
text: Datasets. We evaluate the performance of our GGCN model and existing GNNs in node classification on various real-world datasets (Tang et al., 2009; Rozemberczki et al., 2019; Sen et al., 2008; Namata et al., 2012; Bojchevski & Günnemann, 2018; Shchur et al., 2018). We provide their summary statistics in Table 1, where we compute the homophily level h of a graph as the average of hi of all nodes vi ∈ V . For all benchmarks, we use the feature vectors, class labels, and 10 random splits (48%/32%/20% of nodes per class for train/validation/test1) from (Pei et al., 2019). Baselines. For baselines we use (1) classic GNN models for node classification: vanilla GCN (Kipf & Welling, 2016), GAT (Veličković et al., 2017) and GraphSage (Hamilton et al., 2017); (2) recent models tackling heterophily: Geom-GCN (Pei et al., 2019), H2GCN (Zhu et al., 2020) and GPRGNN (Chien et al., 2021); (3) models tackling oversmoothing: PairNorm (Zhao & Akoglu, 2019) and GCNII (Chen et al., 2020) (state-of-the-art); and (4) 2-layer MLP (with dropout and Elu non-linearity). For GCN, PairNorm, Geom-GCN, GCNII, H2GCN and GPRGNN, we use the original codes provided by the authors. For GAT, we use the code from a well-accepted Github repository2. For GraphSage, we report the results from (Zhu et al., 2020), which uses the same data and splits. For the baselines that have multiple variants (Geom-GCN, GCNII, H2GCN), we choose the best variant for each dataset and denote them as [model]*. For each dataset and baseline, if applicable, we use the best hyperparameters provided by the authors. Otherwise, we perform parameter search to set the best hyperparameters for each baseline. The setting and analysis of hyperparameters are in App. § C. Machine. We ran our experiments on Nvidia V100 GPU.
1(Pei et al., 2019) claims that the ratios are 60%/20%/20%, which is different from the actual data splits shared on GitHub.
2https://github.com/Diego999/pyGAT

heading: 5.2 Q1. PERFORMANCE UNDER HOMOPHILY & HETEROPHILY
text: Table 1 provides the test accuracy of different GNNs on the supervised node classification task over datasets with varying homophily levels (arranged from low homophily to high homophily). A graph’s homophily level is the average of nodes’ homophily levels. We report the best performance of each model across different layers. In App. § B.4, we provide the analysis based on the nodes’ homophily levels (§ 3), which is a better metric to predict GCN’s performance and is aligned with our theory.
GGCN performs the best in terms of average rank (1.78) across all datasets, which suggests its strong adaptability to graphs of various homophily levels. In particular, GGCN achieves the highest accuracy in 5 out of 6 heterophilous graphs (h is low). For datasets like Chameleon and Cornell, GGCN enhances accuracy by around 6% and 3% compared to the second-best model. On homophily datasets (Citeseer, Pubmed, Cora), the accuracy of GGCN is within a 1% difference of the best model.
Our experiments highlight that MLP is a good baseline in heterophilous datasets. In heterophilous graphs, the models that are not specifically designed for heterophily usually perform worse than an MLP. Though H2GCN* is the second best model in heterophilous datasets, we can still see that in the Actor dataset, MLP performs better. GPRGNN and Geom-GCN*, which are specifically designed for heterophily, achieve better performance than classic GNNs (GCN and GAT) in heterophilous datasets, but do not show clear advantage over MLP. Our GGCN model is the only model that performs better than MLP across all the datasets.
In general, GNN models perform well in homophilous datasets. GCNII* performs the best, and GGCN, H2GCN*, GPRGNN and Geom-GCN* also achieve high performance.

heading: 5.3 Q2. OVERSMOOTHING
text: We also test how robust the models are to oversmoothing. To this end, we measure the supervised node classification accuracy for 2 to 64 layers. Table 2 presents the results for two homophilous datasets (top) and two heterophilous datasets (bottom). Per model, we also report the layer at which the best performance is achieved (column ‘Best’). We provides Table 2 in larger font in App. § D.
According to Table 2, GGCN and GCNII* achieve increase in accuracy when stacking more layers in four datasets, while GPRGNN and PairNorm exhibit robustness against oversmoothing. Models that are not designed for oversmoothing have various issues. The performance of GCN and Geom-GCN* drops rapidly as the number of layers grows; H2GCN* requires concatenating all the intermediate outputs and quickly reaches memory capacity; GAT’s attention mechanism also has high memory requirements. We also find that GAT needs careful initialization when stacking many layers as it may suffer from numerical instability in sparse tensor operations.
In general, models like GGCN, GCNII*, and GPRGNN that perform well under heterophily usually exhibit higher resilience against oversmoothing. One exception is Geom-GCN*, which suffers more than GCN. This model incorporates structurally similar nodes into each node’s neighborhood; this design may benefit Geom-GCN* in the shallow layers as the node degrees increase. However, as we point out in Thm. 2, when the effective homophily is low, higher degrees are harmful. If the structurally similar nodes introduce lower homophily levels, their performance will rapidly degrade once the effective homophily is lower than ρ l i
1+ρli . On the other hand, GGCN virtually changes the
degrees thanks to the degree correction mechanism (§ 4.2), and, in practice, this design has positive impact on its robustness to oversmoothing.

heading: 5.4 Q3. EMPIRICAL VERIFICATION OF THE INITIAL & DEVELOPING STAGES
text: Using the vanilla GCN model (Kipf & Welling, 2016), we validate our theorems by measuring the test accuracy and effective homophily for different node degrees (binned logarithmically) on real datasets. We estimate the effective homophily as the portion of the same-class neighbors that are correctly classified before the last propagation. Figure 1 shows the results for Citeseer. In the initial stage (ĥli is high), the accuracy increases with the degree, but in the developing stage, the trend changes, with high-degree nodes being impacted the most, as predicted by our theorems. In App. § B.3, we provide more details for this analysis and we further verify our conclusion on Cora.

heading: 6 RELATED WORK
text: Graph Convolutional Neural Networks. Early on, (Defferrard et al., 2016) proposed a GCN model that combines spectral filtering of graph signals and non-linearity for supervised node classification. The scalability and numerical stability of GCNs was later improved with a localized first-order approximation of spectral graph convolutions proposed in (Kipf & Welling, 2016). (Veličković et al., 2017) proposes the first graph attention network to improve neighborhood aggregation. Many more GCN variants have been proposed for different applications such as: computer vision (Satorras & Estrach, 2018), social science (Li & Goldwasser, 2019), biology (Yan et al., 2019), algorithmic tasks (Veličković et al., 2020; Yan et al., 2020), and inductive classification (Hamilton et al., 2017). Concurrent work (Baranwal et al., 2021) provides theoretic analysis on the linear separability of graph convolution but does not provide effective strategies to increase the separability.
Oversmoothing. The oversmoothing problem was first discussed in (Li et al., 2018), which proved that by repeatedly applying Laplacian smoothing, the representations of nodes within each connected component of the graph converge to the same value. Since then, various empirical solutions have been proposed: residual connections and dilated convolutions (Li et al., 2019); skip links (Xu et al., 2018); new normalization strategies (Zhao & Akoglu, 2019); edge dropout (Rong et al., 2019); and a new model that even increases performance as more layers are stacked (Chen et al., 2020). Some recent works provide theoretical analyses: (Oono & Suzuki, 2019) showed that a k-layer renormalized graph convolution with a residual link simulates a lazy random walk and (Chen et al., 2020) proved that the convergence rate is related to the spectral gap of the graph.
Heterophily & GCNs. Heterophily has recently been recognized as an important issue for GCNs. It is first outlined in the context of GCNs in (Pei et al., 2019). (Zhu et al., 2020) identified a set of effective designs that allow GCNs to generalize to challenging heterophilous settings, and (Zhu et al., 2021) introduced a new GCN model that leverages ideas from belief propagation (Gatterbauer et al., 2015). Though recent work (Chen et al., 2020) focused on solving the oversmoothing problem, it also empirically showed improvement on heterophilous datasets; these empirical observations formed the basis of our work. Finally, (Chien et al., 2021) recently proposed a PageRank-based model that performs well under heterophily and alleviates the oversmoothing problem. However, they view the two problems independently and analyze their model via an asymptotic spectral perspective. Our work studies the representation dynamics and unveils the connections between the oversmoothing and heterophily problems theoretically and empirically. As we demonstrate with GGCN, addressing both issues in a principled manner provides superior performance across a variety of datasets.

heading: 7 CONCLUSION
text: Our work provides the first theoretical and empirical analysis that unveils the connections between the oversmoothing and heterophily problems. By analyzing the statistical change of the node representations after the graph convolution, we identified two causes, i.e., the relative degree of a node compared to its neighbors and the level of heterophily in its neighborhood, which influence the movements of node representations and lead to a higher misclassification rate. Based on our new, unified theoretical perspective, we obtained three important insights: (1) Nodes with high heterophily tend to be misclassified after graph convolution; (2) Even with low heterophily, low-degree nodes can trigger a pseudo-heterophily situation that explains oversmoothing. (3) Allowing signed messages (instead of only positive messages) helps alleviate the heterophily and oversmoothing problems. Based on these insights, we designed a generalized model, GGCN, that addresses the identified causes using signed messages and degree corrections. Though other designs may also address these two problems, our work points out two effective directions that are theoretically grounded (§ 3). In summary, our research suggests it is beneficial to study the oversmoothing and heterophily problems jointly; this leads to architectural insights that can improve the learned representations of graph neural network models across a variety of domains.

heading: 8 REPRODUCIBILITY STATEMENT
text: To reproduce our experimental results, we provide the references to the datasets and baselines in § 5. For the baselines, we use code provided by the authors and set the hyperparameters as the authors suggest. In App. § C, we provide detailed hyperparameter setting for GGCN. We also provide our code in the supplementary material and we will share the link to our code upon acceptance.

heading: A DETAILED PROOFS OF THEOREMS IN § 3

heading: A.1 PROOF OF LEMMA 1
text: Proof. The loss function for SGC is: CrossEntropy(Softmax(F(L)W(L) +b(L)), yi). Rewrite W(L) into an array of column vectors: W(L) = [w(L)0 ,w (L) 1 , . . .w (L) |L| ], b (L) into an array of scalars: b(L) = [b (L) 0 , b (L) 1 , . . . b (L) |L| ], and F (L) into an array of row vectors: F(L) = [f (L)0 ; f (L) 1 ; . . . f (L) |V| ] ([·; ·]
means stacking vertically). Let pi,c ≡ e f (L) i w (L) c +b (L) c∑
j e f (L) i w (L) j +b (L) j
and let yi,c ≡ {
1, iff yi = c 0, otherwise then we
rewrite the loss function as:
− 1 n n∑ i=1 |L|∑ c=1 yi,c · log(pi,c), (11)
n is the number of nodes used for training. To predict that the node vi belongs to class c, we require: ∀c′ 6= c, pi,c > pi,c′ . Thus, we have:
ef (L) i w (L) c +b (L) c∑
j e f (L) i w (L) j +b (L) j
> ef
(L) i w (L) c′ +b (L) c′∑ j e f (L) i w (L) j +b (L) j . (12)
It is equivalent to: f
(L) i w (L) c + b (L) c > f (L) i w (L) c′ + b (L) c′ . (13)
It shows that the decision region of class c is decided by a set of hyper-planes:
x(w(L)c −w (L) c′ ) + (b (L) c − b (L) c′ ) > 0. (14)
x is the vector variable that describes the plane. Any vectors that satisfy the equation are on this plane. We note that for binary classification, there is one hyper-plane.

heading: A.2 PROOF OF LEMMA 2
text: Before giving the proof, we first explain the meaning of the Lemma. As we point out in § 3, the misclassification rate of an L-layer SGC can be studied through its last logistic-regression layer, the input to which is {f (L)i }. To study the misclassification rate of an (L+ 1)-layer SGC, we can view the input to the last layer {f (L+1)i } as being moved from {f (L) i }. The misclassification rate is closely related to the decision boundary and will be our tool for studying the change of the misclassification rate. This Lemma studies the movements that bring the node representations closer to the original decision boundary; we will prove that moving towards the original decision boundary by a non-zero step is not beneficial (i.e., harmful) to the SGC’s performance.
Proof. We prove it by contradiction and suppose that after the movements, the total misclassification rate is lowered. We denote the conditional distribution of {f (L)i } as fL1 (x) conditioned on that they are from class 1 and fL2 (x) conditioned on that they are from class 1 or class 2, respectively. To note that, the distributions of different layers are different.
After the movements, the representations from class 1 become: {f (L)i − tw∗ T }, t > 0. tw∗T represents moving towards the original decision boundary along the norm direction by a non-zero step. This causes a corresponding change in the conditional PDF given that they are from class 1: fL1 (x + tw ∗T ).
Recall that in § 3, the parameters for the original optimal hyperplane w∗ and b∗, and the parameters for the later optimal hyperplane w∗′ and b∗′ are normalized such that when xw∗ + b∗ > 0 and xw∗′ + b∗′ > 0, we predict class 1.
The new misclassification rate conditioned on class 1 is:
M ′t = ∫ xw∗′+b∗′<0 fL1 (x + tw ∗T )dx = ∫ (x−tw∗T )w∗′+b∗′<0 fL1 (x)dx. (15)
The new misclassification rate conditioned on class 2 is:
M ′r = ∫ xw∗′+b∗′>0 fL2 (x)dx. (16)
The new total misclassification rate is:
M ′ = M ′tP(vi ∈ V1) +M ′rP(vi ∈ V2)
= M ′t P(vi ∈ V1)
P(vi ∈ V1) + P(vi ∈ V2) +M ′r P(vi ∈ V2) P(vi ∈ V1) + P(vi ∈ V2)
= ρ
ρ+ 1 M ′t +
1
ρ+ 1 M ′r.
(17)
Next, we will prove that if the total misclassification is lowered, xw∗ + b∗ = 0 is not the optimal hyper-plane before the movements which should achieve the lowest total misclassification rate.
Consider a hyper-plane xw∗′ + b∗′ − tw ∗Tw∗′ 2 = 0. Given that w ∗Tw∗′ > 0 and t > 0, for ∀x, s.t. xw∗′+b∗′− tw ∗Tw∗′
2 < 0, we have: (x−tw ∗T )w∗′+b∗′ = xw∗′+b∗′− tw ∗Tw∗′ 2 − tw∗Tw∗′
2 < 0. It means:
{x|(x− tw∗T )w∗′ + b∗′ < 0} ⊇ {x|xw∗′ + b∗′ − tw ∗Tw∗′
2 < 0}. (18)
Because fL1 (x) is a PDF which is a nonnegative function,∫ (x−tw∗T )w∗′+b∗′<0 fL1 (x)dx ≥ ∫ xw∗′+b∗′− tw∗T w∗′2 <0 fL1 (x)dx. (19)
Similarly, we can obtain
{x|xw∗′ + b∗′ > 0} ⊇ {x|xw∗′ + b∗′ − tw ∗Tw∗′
2 > 0}. (20)
Thus, ∫ xw∗′+b∗′>0 fL2 (x)dx ≥ ∫ xw∗′+b∗′− tw∗T w∗′2 >0 fL2 (x)dx. (21)
Define
Mf ≡ ρ
ρ+ 1 ∫ xw∗′+b∗′− tw∗T w∗′2 <0 fL1 (x)dx + 1 ρ+ 1 ∫ xw∗′+b∗′− tw∗T w∗′2 >0 fL2 (x)dx. (22)
The quantity Mf represents the total misclassification rate before the movements if the decision boundary is xw∗′ + b∗′ − tw ∗Tw∗′
2 = 0. Given Eq. 17, 19 and 21, we have:
M ′ ≥Mf . (23)
Let M denotes the total classification rate before the movements. Based on the assumption that the total misclassification rate is lowered after the movements (M > M ′), we have:
M > Mf . (24)
Eq. 24 indicates that we find a hyper-plane xw∗′ + b∗′ − tw ∗Tw∗′
2 = 0, which yields smaller total misclassification rate than xw∗ + b∗ = 0 before the movements. This contradicts to the fact that xw∗ + b∗ = 0 is the optimal hyper-plane before the movements.

heading: A.3 PROOF OF THEOREM 1
text: Proof. The first layer node representations are given by:
f (1) i =
f (0) i di + 1 + ∑ j∈Ni f (0) j√ di + 1 · √ dj + 1 . (25)
Without loss of generality, we assume node vi is in the first class V1. Then, we can express the conditional expectation of f (1)i as:
E A,{yi},{f (0)i }|di,vi∈V1 (f (1) i |vi ∈ V1, di) = EA|di,vi∈V1(E{yi},{f (0)i }|A,vi∈V1(f (1) i |vi ∈ V1,A))
(26) Recall that A is the graph adjacency matrix; the first expectation is taken over the randomness of ground truth labels and initial input features, and the second expectation is taken over the randomness of graph structure (A) given the degree of node vi and its label. Denote ki = E{yi},{f (0)i }|A,vi∈V1( |N si | |Ni| ) and hi = EA,{yi},{f (0)i }|vi∈V1,di( |N si | |Ni| ).
E{yi},{f (0)i }|A,vi∈V1(f (1) i |vi ∈ V1,A)
=E{yi},{f (0)i }|A,vi∈V1
( f
(0) i
di + 1 |vi ∈ V1,A ) + ∑ j∈Ni E{yi},{f (0)i }|A,vi∈V1 ( f (0) j√ di + 1 · √ dj + 1 |vi ∈ V1,A )
= µ di + 1 + ∑ j∈Ni ( E{yi},{f (0)i }|A,vi,vj∈V1 ( f (0) j√ di + 1 · √ dj + 1 |A, vi, vj ∈ V1 ) · P(vj ∈ V1|A, vi ∈ V1)
+E{yi},{f (0)i }|A,vi∈V1,vj∈V2
( f
(0) j√ di + 1 · √ dj + 1 |A, vi ∈ V1, vj ∈ V2
) · P(vj ∈ V2|A, vi ∈ V1) ) (27)
Let 1{·} represent the indicator function: it equals 1 if and only if the event in the bracket holds. E{yi},{f (0)i }|A,vi∈V1( ∑ j∈Ni 1{vj ∈ V1|A, vi ∈ V1}) = ∑ j∈Ni P(vj ∈ V1|A, vi ∈ V1) = diki. (28)
Due to our assumptions in § 3, though the labels of nodes are dependent, they share the same marginal distribution and their joint distribution is a permutation-invariant function. Thus, given vi ∈ V1(yi = 1), the conditional joint distribution of {yt|t 6= i} is also permutation invariant— i.e., ∀j, j′ ∈ Ni,P(vj ∈ V1|vi ∈ V1) = P(v′j ∈ V1|vi ∈ V1). Then for ∀j ∈ Ni, we have: diP(vj ∈ V1|vi ∈ V1) = diki and P(vj ∈ V1|vi ∈ V1) = ki. Due to the independence of A and {yi}, P(vj ∈ V1|A, vi ∈ V1) = ki.
E{yi},{f (0)i }|vi∈V1,A(f (1) i |vi ∈ V1,A) =
µ di + 1 + ∑ j∈Ni
( ki√
di + 1 · √ dj + 1 µ− (1− ki)√ di + 1 · √ dj + 1 ρµ
)
= µ
di + 1 + ((1 + ρ)ki − ρ)µ√ di + 1 ∑ j∈Ni 1√ dj + 1
=  1 di + 1 + ∑ j∈Ni 1√ dj+1√ di + 1 ((1 + ρ)ki − ρ) µ =  1 di + 1 + ∑ j∈Ni √ di+1√ dj+1 di + 1 ((1 + ρ)ki − ρ)
µ = ( 1
di + 1 + di di + 1
∑ j∈Ni rij
di ((1 + ρ)ki − ρ)
) µ.
(29)
Combining Equation (26) and Equation (29) and given the independence of rij and ki, we have:
E A,{yi},{f (0)i }|di,vi∈V1 (f (1) i |vi ∈ V1, di) =
1
di + 1 + di di + 1 EA|di,vi∈V1
(∑ j∈Ni rij
di
) EA|di,vi∈V1 ((1 + ρ)ki − ρ))µ
=
( 1 + ((1 + ρ)hi − ρ)diri
di + 1
) µ ≡ γ1i µ.
(30)
Define ≡ (1 + ρ)hi − ρ, and we consider three cases: (1) hi ≤ ρ1+ρ , (2) hi > ρ 1+ρ & ri ≤ 1 , and (3) hi > ρ1+ρ & ri > 1 .
• CASE 1: hi ≤ ρ1+ρ
• Upper Bound We have:
γ1i ≤ 1 di + 1 ≤ 1 2 . (31)
• Lower Bound To see if there exists a lower bound, we first show that when hi ≤ ρ1+ρ , 1+((1+ρ)hi−ρ)diri di+1
is a decreasing function of di given that di ≥ 1. When hi ≤ ρ1+ρ , we have:
1. ((1 + ρ)hi − ρ) ≤ 0 2. didi+1 is an increasing non-negative function of di 3. ri is an increasing non-negative function of di 4. 1di+1 is a decreasing function of di
Thus 1+((1+ρ)hi−ρ)diridi+1 is a decreasing function of di.
When hi = ρ1+ρ , 1+((1+ρ)hi−ρ)diri di+1 = 1di+1 and 0 < 1 di+1 ≤ 12 .
When hi < ρ1+ρ ,
1 + ((1 + ρ)hi − ρ)diri di + 1 ≤ ((1 + ρ)hi − ρ)diri di + 1 + 1 2
≤ ((1 + ρ)hi − ρ)ri 2 + 1 2 .
(32)
And we know that when hi < ρ1+ρ :
lim ri→∞ ((1 + ρ)hi − ρ)ri 2 + 1 2 = −∞. (33)
Thus,
lim ri→∞ 1 + ((1 + ρ)hi − ρ)diri di + 1 = −∞. (34)
• CASE 2: hi > ρ1+ρ & ri ≤ 1
If hi > ρ1+ρ , 0 < ≤ 1; if ri ≤ 1 , 0 < ri ≤ 1. Given E(f1i ) = (
1 + diri di + 1
) µ. (35)
we have 0 < 1di+1 < γ 1 i ≤ 1.
• CASE 3: hi > ρ1+ρ & ri > 1
In this case, Equation (35) still holds, since hi > ρ1+ρ .
• Lower Bound If ri > 1 , then ri > 1 and therefore γ 1 i > 1.
• Upper Bound When > 0,
1 + diri di + 1 > diri di + 1
≥ ri 2 .
(36)
Because
lim ri→∞ ri 2 =∞, (37)
we have:
lim ri→∞ 1 + diri di + 1 =∞. (38)
To sum it up,
γ1i ∈  (−∞, 12 ], if hi ≤ ρ 1+ρ (0, 1], if hi > ρ1+ρ & ri ≤ 1
(1+ρ)hi−ρ (1,∞), otherwise.
(39)

heading: Remarks: Special cases
text: For different types of graphs and different nodes in the graph, diri might be different. For a d-regular graph whose nodes have constant degree or a graph whose adjacency matrix is row-normalized, we will have:
γ1i =
( 1 + ((1 + ρ)hi − ρ)diri
di + 1 ) ≤( 1
(di + 1) + di (di + 1) ) = 1
(40)
Equality is achieved if and only if hi = 1. To note that, hi = 1 is not achievable for every node as long as there are more than one class. Boundary nodes will suffer most.

heading: A.4 PROOF OF THEOREM 2
text: Proof. After propagating over multiple layers, we use ξli to account for the accumulated scaling
effects (γli). That is, EA,{yi},{f (0)i }|di
( f (l) i di+1 |di ) = ξliµ. Furthermore, conditioned on A and ξ l i, the
set of nodes contributing positively to node vi is defined as:
N̂ si (A, ξli) ≡ {vj |vj ∈ Ni and (ξliµ) · E{yi},{f (0)i }|ξli,A
( f
(l) j T |ξli,A ) > 0}.
E A,{yi},{f (0)i }|di,ξli,vj∈Ni
( f
(l) j rij |di, ξli, vj ∈ Ni
) = { ξli ′ µ vj ∈ N̂ si (A, ξli)
−ρliξli ′ µ vj 6∈ N̂ si (A, ξli)
In the following proof, we use N̂ si to refer to N̂ si (A, ξli) for conciseness. The representations at (l + 1)-th layer:
f (l+1) i =
f (l) i di + 1 + ∑ j∈Ni f (l) i√ di + 1 · √ dj + 1
(41)
E A,{yi},{f (0)i }|di,ξli
( f
(l+1) i |di, ξ l i
) (42)
= E A,{yi},{f (0)i }|di,ξli
( f
(l) i
di + 1 |di, ξli
) + E
A,{yi},{f (0)i }|di,ξli ∑ j∈Ni f (l) j√ di + 1 · √ dj + 1 |di, ξli (43) = ξliµ
di + 1 +
1
di + 1 E A,{yi},{f (0)i }|di,ξli ( ∑ j∈Ni f (l) j √ di + 1√ dj + 1 |di, ξli ) (44)
In § 3, we assume that {dj} follow the same distribution and their joint distribution function is permutation-invariant, and {yj} and {f lj} also have this property. Thus, conditioned on di, ξli and Ni, the distribution of f (l) j √ di+1√
dj+1 is the same for ∀j ∈ Ni (neighbors are indistinguishable) and we obtain:
E A,{yi},{f (0)i }|di,ξli,Ni ( ∑ j∈Ni f (l) j √ di + 1√ dj + 1 |di, ξli,Ni ) (45)
= diEA,{yi},{f (0)i }|di,ξli,Ni,vj∈Ni
( f
(l) j √ di + 1√
dj + 1 |di, ξli,Ni, vj ∈ Ni
) (46)
Given that the joint distribution of {dj}, the joint distribution of {yj} and the joint distribution of {f lj} are permutation-invariant functions, for any Ni,
E A,{yi},{f (0)i }|di,ξli,Ni (∑ j∈Ni f (l) j √ di+1√ dj+1 |di, ξli,Ni ) is the same. That is:
E A,{yi},{f (0)i }|di,ξli ( ∑ j∈Ni f (l) j √ di + 1√ dj + 1 |di, ξli ) (47)
= E A,{yi},{f (0)i }|di,ξli,Ni ( ∑ j∈Ni f (l) j √ di + 1√ dj + 1 |di, ξli,Ni ) (48)
= diEA,{yi},{f (0)i }|di,ξli,vj∈Ni
( f
(l) j √ di + 1√
dj + 1 |di, ξli, vj ∈ Ni
) (49)
We note that vj in Equation 49 can be any node except vi due to the equivalence of those nodes.
Combining Equation 44 and Equation 49, we can obtain:
E A,{yi},{f (0)i }|di,ξli
( f
(l+1) i |di, ξ l i
) (50)
= ξliµ
di + 1 + di di + 1 E A,{yi},{f (0)i }|di,ξli,vj∈Ni
( f
(l) j √ di + 1√
dj + 1 |di, ξli, vj ∈ Ni
) (51)
= ξliµ
di + 1 + di di + 1 ( E A,{yi},{f (0)i }|di,ξli,vj∈N̂ si ,vj∈Ni ( f (l) j √ di + 1√ dj + 1 |di, ξli, vj ∈ N̂ si , vj ∈ Ni ) (52)
· P ( vj ∈ N̂ si |vj ∈ Ni, di, ξ l i ) + E
A,{yi},{f (0)i }|di,ξli,vj 6∈N̂ si ,vi∈Ni
( f
(l) j √ di + 1√
dj + 1 |di, ξli, vj 6∈ N̂ si , vj ∈ Ni
) (53)
· P ( vj 6∈ N̂ si , |di, ξ l i, vj ∈ Ni )) (54)
= ξliµ
di + 1 +
( diP(vj ∈ N̂ si |di, ξli, vj ∈ Ni)
di + 1 ξli ′ µ− di(1− P(vj ∈ N̂ s i |di, ξli, vj ∈ Ni)) di + 1 ρliξ l i ′ µ
) (55)
= ξliµ di + 1 + di(P(vj ∈ N̂ si |di, ξli, vj ∈ Ni)(1 + ρli)− ρli)ξli
′ µ
di + 1 (56)
Define r̄il ≡ ξ l i ′
ξli . If we know the degree di, ξli, and that a neighbor vj is in the group N̂ si , r̄il
actually represents the ratio of expected f ljri,j to expected f l i . We regard it as the effective related degree at l-th layer. For the initial layer, if we know the degree di, yi, and that a neighbor vj is in the group N si , the ratio of f0j ri,j to f0i is rij . Recall that the related degree ri at the initial layer is the expected average of rij in the neighborhood. Thus r̄il is an extension of ri. Moreover, let ĥli = P(vj ∈ N̂ si |vj ∈ Ni, di, ξli) represent the probability of a neighbor whose representation has a positive contribution in expectation. This naturally extends the meaning of homophily in deeper layers. Thus, we regard it as the effective homophily of node vi at l-th layer. Given the degree di, ξli, ρli represents the ratio of the probability that a neighbor will have a positive rather than a negative contribution to vi. This naturally extends the meaning of ρ.
We further write Equation 56 as:
ξli di + 1
( 1 + ( (ĥli(1 + ρ l i)− ρli)dir̄il) ) µ
and it will have three cases similar to Thm. 1.

heading: A.5 PROOF OF THEOREM 3
text: Proof. Similar to Equation 26, we can express the conditional expectation of f (1)i as:
E A,{yi},{f (0)i }|di,vi∈V1
( f
(1) i |vi ∈ V1, di ) =Em0i |vi∈V1,di ( E A,{yi},{f (0)i }|di,vi∈V1,m0i ( f (1) i |vi ∈ V1, di,m 0 i
)) =Em0i |vi∈V1,di ( E A,{yi},{f (0)i }|vi∈V1,di,m0i ( f (0) i di + 1 |vi ∈ V1, di,m0i )
+E A,{yi},{f (0)i }|vi∈V1,di,m0i ∑ j∈Ni f (0) j√ di + 1 · √ dj + 1 |vi ∈ V1, di,m0i )
= µ
di + 1
+Em0i |vi∈V1,di ( EA|di,vi∈V1,m0i ( ∑ j∈Ni ( E{yi},{f (0)i }|A,vi,vj∈V1,m0i ( f (0) j√ di + 1 · √ dj + 1 |A,m0i , vj ∈ V1, vi ∈ V1 ) ·P(vj ∈ V1|m0i , vi ∈ V1,A)
+E{yi},{f (0)i }|A,vi∈V1,vj∈V2,m0i
( f
(0) j√ di + 1 · √ dj + 1 |A,m0i , vi ∈ V1, vj ∈ V2
) · P(vj ∈ V2|m0i ) ))) .
(57)
Next, we will show how to compute the conditional expectation and conditional probability in the summand.
E{yi},{f (0)i }|A,vi,vj∈V1,m0i
( f
(0) j√ di + 1 · √ dj + 1 |m0i , vi, vj ∈ V1,A
)
=E{yi},{f (0)i }|A,vi∈V1,m0i ,vj
( f
(0) j√ di + 1 · √ dj + 1 |A,m0i , vi ∈ V1, vj ∈ V1, vjwrongly send information ) · P(vjwrongly send information|A,m0i , vi ∈ V1, vj ∈ V1)
+E{yi},{f (0)i }|A,vi∈V1,m0i ,vj
( f
(0) j√ di + 1 · √ dj + 1 |A,m0i , vi ∈ V1, vj ∈ V1, vjcorrectly send information ) · P(vjcorrectly send information|A,m0i , vi ∈ V1, vj ∈ V1).
(58)
Combined with the independence assumption, we have:
P(vjwrongly send information|A,m0i , vi ∈ V1, vj ∈ V1) = m0i . (59)
Similarly, we obtain:
P(vjcorrectly send information|A,m0i , vi ∈ V1, vj ∈ V1) = 1−m0i . (60)
Then Equation (58) can be rewritten as:
E{yi},{f (0)i }|A,vi,vj∈V1,m0i
( f
(0) j√ di + 1 · √ dj + 1 |m0i , vi, vj ∈ V1,A
)
=E{yi},{f (0)i }|A,vi∈V1,m0i ,vj
( f
(0) j√ di + 1 · √ dj + 1 |A,m0i , vi ∈ V1, vj ∈ V1, vjwrongly send information
) ·m0i
+E{yi},{f (0)i }|A,vi∈V1,m0i ,vj
( f
(0) j√ di + 1 · √ dj + 1 |A,m0i , vi ∈ V1, vj ∈ V1, vjcorrectly send information
) · (1−m0i )
=− m 0 iµ√ di + 1 · √ dj + 1 + (1−m0i )µ√ di + 1 · √ dj + 1
= (1− 2m0i )µ√ di + 1 · √ dj + 1 .
(61)
Similarly, we have: E{yi},{f (0)i }|A,vi∈V1,vj∈V2,m0i
( f
(0) j√ di + 1 · √ dj + 1 |A,m0i , vi ∈ V1, vj ∈ V2
) =
(1− 2m0i )ρµ√ di + 1. · √ dj + 1 .
(62) Consider the independence between m0i and node class & degrees, and insert Equation (61) and Equation (62) into Equation (57), we will have:
E A,{yi},{f (0)i }|di,vi∈V1
( f
(1) i |vi ∈ V1, di ) = µ
di + 1 + Em0i |vi∈V1,di
( EA|di,vi∈V1,m0i ∑ j∈Ni ( (1− 2m0i )kiµ√ di + 1 · √ dj + 1 + (1− 2m0i )(1− ki)ρµ√ di + 1 · √ dj + 1 ) )
= µ
di + 1 + Em0i |vi∈V1,di
( EA|di,vi∈V1,m0i ∑ j∈Ni (1− 2m0i )(ρ+ (1− ρ)ki)µ√ di + 1 · √ dj + 1 )
= µ
di + 1 + Em0i |vi∈V1,di
(( (1− 2m0i )(ρ+ (1− ρ)hi)diri
di + 1
) µ )
=
( 1 + (1− 2e0i )(ρ+ (1− ρ)hi)diri
di + 1
) µ ≡ γ1i E(f (0) i ).
(63)
When hi ≤ 1, ρ+ (1− ρ)hi = (1−hi)ρ+hi > 0. Define ′ ≡ (1− 2e0i )(ρ+ (1− ρ)hi). To obtain the ranges of γ1i , when e 0 i ≥ 0.5, ′ ≤ 0, it resembles the derivations of CASE 1 in Proof A.3; when e0i < 0.5, 0 < ri ≤ 1, it resembles the derivations of CASE 2; when e0i < 0.5, ri > 1, it resembles the derivations of CASE 3.

heading: B.1 ABLATION STUDY

heading: B ADDITIONAL EXPERIMENTS
text: We now study the impact of two proposed mechanisms (signed messages and degree correction, § 4). To better show their effects, we add each design choice to a base model and track the changes in the node classification performance. As the base model, we choose a GCN variant that uses the message passing mechanism (Kipf & Welling, 2016) with weight bias, a residual connection (but not decaying aggregation) for robustness to oversmoothing, and Elu non-linearity σ. We denote the model that replaces the message passing with our signed messages mechanism as +sign, and the model that incorporates the degree correction as +deg. The model that uses both designs is denoted as +sign,deg. Table B.1 gives the accuracy of the models in the supervised node classification task for different layers.
We observe that both mechanisms alleviate the oversmoothing problem. Specifically, the base model has a sharp performance decrease after 32 layers, while the other models have significantly higher performance. In general, the +deg model is better than +sign in alleviating oversmoothing, and has a consistent performance gain across different data. For Chameleon, we observe increase in accuracy as we stack more layers; the large performance gain of GGCN results from the degree correction. In Cora and Cornell, +sign,deg consistently performs better across different layers than the model with only one design, demonstrating the constructive effect from our two proposed mechanisms.
The signed message design has an advantage in heterophilous datasets. In the Cornell dataset, using signed information rather than plain message passing results in over 20% gain, which explains the strong performance of GGCN. However, in homophilous datasets, the benefit from signed messages is limited, as these datasets have few different-class neighbors. This is because when the effective
homophily ĥli is high and error rate e 0 i is low, limĥli→1,e0i→0 (1+ρ)ĥli−ρ (1−2e0i )(ρ+(1−ρ)ĥli) = 1, so using signed messages is less beneficial in homophilous datasets.

heading: B.2 BATCH NORM & LAYER NORM
text: In § 4, we use decaying aggregation instead of other normalizing mechanisms. Other mechanisms, such as batch or layer norm, may be seen as solutions to the heterophily and oversmoothing problems. However, batch norm cannot compensate for the dispersion of the mean vectors (§ 3) due to different degrees and homophily levels of the nodes. Although, to some extent, it reduces the speed by which the representations of the susceptible nodes (case 1 & 2) move towards the other class (good for oversmoothing), it also prevents the representations of the nodes that could benefit from the propagation (case 3) from increasing the distances (drop in accuracy). Layer norm is better at overcoming the dispersion effect but may lead to a significant accuracy drop in some datsets when a subset of features are more important than the others. Thus, we do not use any of these normalizations.
Next, we provide experiments to show the effects of batch norm and layer norm. We use the following base model (the same model used in §B.1): a GCN Kipf & Welling (2016) with weight bias, Elu non-linearity and residual connection. We do not include any of our designs so as to exclude any other factors that can affect the performance. The models we compare against are +BN and +LN, which represent the models that add batch norm and layer norm right before the non-linear activation, respectively.
Table B.2 shows that both batch norm and layer norm can help with oversmoothing. Moreover, adding layer norm is in general better than adding batch norm. This is expected because the scaling effect caused by the propagation can be alleviated by normalizing across the node representations. Thus, the dispersion of the expected representations can be mitigated. On the other hand, batch norm normalizes across all the nodes, so it requires sacrificing the nodes that benefit (case 3) to compensate
for the nodes that are prone to moving towards the other classes (case 1 & case 2). As a result, batch norm is less effective in mitigating oversmoothing and leads to a bigger decrease in accuracy.
Another finding is that both layer norm and batch norm lead to a significant accuracy decrease (2%-3%) in the heterophilous datasets. +BN has a clear accuracy drop even in the homophilous datasets. As Thm. 1 points out: higher heterophily level may result in sign flip. If the representations flip the sign, using batch norm or layer norm will not revert the sign, but they may instead encourage the representations to move towards the other class more.
Given the limitations shown above, we do not use either batch norm or layer norm in our proposed model, GGCN.

heading: B.3 MORE ON THE INITIAL & DEVELOPING STAGES
text: Section 5.4 shows how the node classification accuracy changes for nodes of different degrees with the number of layers on Citeseer. Here, we provide more details of this experiment and give the results on another dataset, Cora.
Datasets. According to Thm. 1 and 2, in order to see both the initial and the developing stage, we need to use homophilous datasets. In heterophilous datasets, most nodes satisfy case 1, so the initial stage does not exist.
Measurement of effective homophily ĥli . To estimate the effective homophily ĥli, we measure the portion of neighbors that have the same ground truth label as vi and are correctly classified. Following our theory, we estimate ĥli before the last propagation takes place and analyze its impact on the accuracy of the final layer. In more detail, we obtain the node representations before the last propagation from a trained vanilla GCN Kipf & Welling (2016) and then perform a linear transformation using the weight matrix and bias vector from the last layer. Then, we use the transformed representations to classify the neighbors of node vi and compute ĥli. We note that we leverage the intermediate representations only for the estimation of ĥli; the accuracy of the final layer is still measured using the outputs from the final layer.
Degree intervals. To investigate the change in GCN accuracy with different layers for nodes with different degrees, we categorize the nodes in n degree intervals. For the degree intervals, we use logarithmic binning (base 2). In detail, we denote the highest and lowest degree by dmax and dmin, respectively, and let Ω ≡ log2 dmax−log2 dminn . Then, we divide the nodes into n intervals, where the j-th interval is defined as: [dmin · 2(j−1)Ω, dmin · 2jΩ). Dataset: Citeseer. Figure 1 and Table B.3 show how the accuracy changes with the number of layers for different node degree intervals. We observe that in the initial stage, the accuracy increases as the degree and ¯̂hli increase. However, in the developing stage, the accuracy of high-degree nodes drops more sharply than that of low-degree nodes.
Dataset: Cora. The results for Cora are shown in Figure B.1 and Table B.4. In the initial stage, the nodes with lower
degrees usually have lower accuracy. One exception is the nodes with degrees in the range [3, 7]. These nodes have higher accuracy because the average effective homophily ¯̂hli of that degree group is the second highest. In the developing stage, the accuracy of the high-degree nodes drops more than the accuracy of the remaining node groups.
GCN’s behavior on both Citesser and Cora datasets verifies our conjecture based on our theorems in § 3.3.

heading: B.4 HOMOPHILY METRIC
text: In Table 1, we provide the graph homophily level h, which is defined as the average of the nodes’ homophily levels. In our theoretical analysis in § 3, we use a node’s homophily level and relative degree to characterize three cases (Fig. 2 and Thm. 1). To better align our empirical results with our theoretical analysis, we provide below the proportion of nodes in each case.
We observe that a low graph homophily level indicates that case 1 is the dominant case, while a high graph homophily level indicates that case 3 is the dominant case. As we stated in Thm 1, under "non-swapping" condition, case 3 is the only case to have a benefit. Thus, in the commonly-used homophilous datasets (Citeseer, Pubmed and Cora), case 3 dominates and enjoys the benefits from graph convolution. In the Texas, Wisconsin and Actor datasets, only case 1 dominates and case 1 hurts the performance most, this explains why GCN performs worse than most methods in Table 1. In the Squirrel and Chameleon datasets, both case 1 and case 2 dominate, GCN yields acceptable results. Using portions of the three cases to analyze the datasets is a better metric, because it aligns more with the GCN’s performance. As shown by Table B.5, Wisconsin, Actor, Squirrel and Chameleon have very close graph level homophily, but GCN’s performance are quite different as shown in Table 1. Our way to define homophily level does predict that GCN should perform decently in Squirrel and Chameleon datasets.

heading: B.5 COMPLEXITY ANALYSIS
text: We first analyze the time complexity of the forward path GGCN. For degree correction, we need to compute the rij . However, we do not need to compute all of them, and we only need to compute rij for node pairs who are linked. The time complexity is O(|E|), but it is a one-time computation, the results of which can be saved. We compute τ lij based on the learned weights λ l 0, λ l 1. The time complexity isO(|E| ·L), where L is the number of layers. The time complexity to compute the signed function is O(|E| ·H ·L), where H is the hidden dimension of representations, and we only compute the cosine similarity between the nodes that are linked. We also need to compute the multiplication of the propagation matrix and representation matrices. The time complexity is O(|V|2 · H · L), . Similarly, the time complexity of the multiplication of representation matrices and the weight matrices is O(|V| ·H2 ·L). The total time complexity would be O(max(|V|2, |E|) ·H ·L). The complexity of GGCN resembles the complexity of attention-based model. Thus we compare with GAT (Veličković et al., 2017) the total time to train and test on 4 larger homophilous and heterophilous datasets. We run the training and testing for 10 times.
In general, GGCN runs faster than GAT because degree correction and signed messages in GGCN learn fewer parameters.

heading: C HYPERPARAMETERS AND PARAMETERS

heading: C.1 HYPERPARAMETER SETTINGS

heading: Experiments for Table 1 & Table 2
text: For the baselines, we set the same hyperparameters that are provided by the original papers or the authors’ github repositories, and we match the results they reported in their respective papers. In our experiments, we find that the original hyperparameters set by the authors are already well-tuned.
All the models use Adam as the optimizer. GAT sets the initial learning rate as 0.005 and Geom-GCN uses a custom learning scheduler. All the other models (include GGCN) use the initial learning rate 0.01.
For GGCN, we use the following hyperparameters:
• k in the decaying aggregation: 3
We tune the parameters in the following ranges:
• Dropout rate: [0.0, 0.7] • Weight decay: [1e-7, 1e-2] • Hidden units: {8, 16, 32, 64, 80} • Decay rate η: [0.0, 1.5]

heading: Experiments for Table B.1 and Table B.2
text: The hyperparameters that are used in all the models (Base, +deg, +sign, +deg,sign, +BN, +LN) are set to be the same and they are tuned for every dataset. Those common hyperparameters are:
• Dropout rate: [0.0, 0.7] • Weight decay: [1e-7, 1e-2] • Hidden units: {8, 16, 32, 64, 80}
C.2 INITIALIZATION OF PARAMETERS

heading: Initialization
text: For GGCN, we adopt the following parameter initialization in the experiments for Table 1 & Table 2
• Initialization of λl0 and λ l 1: 0.5 and 0, respectively • Initialization of αl, βl0, β l 1 and β l 2: 2, 0, 0, 0, respectively.
We initialize βl{0,1,2} = 0 in Eq. (6) because, after applying softmax, β̂l{0,1,2} = 1/3; this ensures equal contributions from positive and negative neighbors and themselves (and sum=1). We initialize λl1 = 0 in Eq. (9) following the common practice for initializing the bias. We set αl = 2 and λl0 = 0.5 in Eq. (6) and Eq. (9), because when rij → +∞, the degree correction (including global scaling) is: α̂lτ lij = softplus(2) · softplus(0.5 · (0 − 1) + 0) ≈ 1. As we mention in Thm. 1, when the homophily level is high, nodes with large ri may benefit (case 3), thus we do not want to compensate for these nodes and would like to keep α̂lτ lij close to 1.

heading: C.3 PARAMETERS AFTER TRAINING
text: Figure C.1 shows the original and corrected rij (avg rij). Corrected rij are given by α̂lτ lijrij , which are a combination of global scaling and local degree correction. Because βl{0,1,2} sum to 1 and do not change global scaling, they are not considered in the corrected rij . As can be seen in Fig. C.1, after the training, GGCN learns to increase rij , which satisfies our theorems.
D TABLE 2 WITH LARGER FONTS
Ta bl
e D
.1 :M
od el
pe rf
or m
an ce
fo rd
iff er
en tl
ay er
s: m
ea n
ac cu
ra cy ±
st de
v ov
er di
ff er
en td
at a
sp lit
s. Pe
rd at
as et
an d
G N
N m
od el
,w e
al so
re po
rt th
e la
ye ra
tw hi
ch th
e be
st pe
rf or
m an ce (g iv en in Ta bl e 1) is ac hi ev ed .‘ O O M ’: ou to fm em or y; ‘I N S’ :n um er ic al in st ab ili ty .
L ay
er s
2 4
8 16
32 64
B es
t 2
4 8
16 32
64 B
es t
C or
a (h
=0 .8
1) C
ite se
er (h
=0 .7 4) G G C N (o ur s) 8 7 .0 0 ± 1 .1 5 8 7 .4 8 ± 1 .3 2 8 7 .6 3 ± 1 .3 3 8 7 .5 1 ± 1 .1 9 8 7 .9 5 ± 1 .0 5 8 7 .2 8 ± 1 .4 1 32 7 6 .8 3 ± 1 .8 2 7 6 .7 7 ± 1 .4 8 7 6 .9 1 ± 1 .5 6 7 6 .8 8 ± 1 .5 6
7 6 .9
7 ± 1 .5 2
7 6 .6
5 ± 1 .3 8 10 G PR G N N 8 7 .9 3 ± 1 .1 1 8 7 .9 5 ± 1 .1 8 8 7 .8 7 ± 1 .4 1 8 7 .2 6 ± 1 .5 1 8 7 .1 8 ± 1 .2 9 8 7 .3 2 ± 1 .2 1 4 7 7 .1 3 ± 1 .6 7 7 7 .0 5 ± 1 .4 3 7 7 .0 9 ± 1 .6 2 7 6 .0 0 ± 1 .6 4 7 4 .9 7 ± 1 .4 7 7 4 .4 1 ± 1 .6 5 2 H 2G C N * 8 7 .8 7 ± 1 .2 0 8 6 .1 0 ± 1 .5 1 8 6 .1 8 ± 2 .1 0 O O M O O M O O M 2 7 6 .9 0 ± 1 .8 0 7 6 .0 9 ± 1 .5 4 7 4 .1 0 ± 1 .8 3 O O M O O M O O M 1 G C N II * 8 5 .3 5 ± 1 .5 6 8 5 .3 5 ± 1 .4 8 8 6 .3 8 ± 0 .9 8 8 7 .1 2 ± 1 .1 1 8 7 .9 5 ± 1 .2 3 8 8 .3 7 ± 1 .2 5 64 7 5 .4 2 ± 1 .7 8 7 5 .2 9 ± 1 .9 0 7 6 .0 0 ± 1 .6 6 7 6 .9 6 ± 1 .3 8 7 7 .3 3 ± 1 .4 8 7 7 .1 8 ± 1 .4 7 32 Pa ir N or m 8 5 .7 9 ± 1 .0 1 8 5 .0 7 ± 0 .9 1 8 4 .6 5 ± 1 .0 9 8 2 .2 1 ± 2 .8 4 6 0 .3 2 ± 8 .2 8 4 4 .3 9 ± 5 .6 0 2 7 3 .5 9 ± 1 .4 7 7 2 .6 2 ± 1 .9 7 7 2 .3 2 ± 1 .5 8 5 9 .7 1 ± 1 5 .9 7 2 7 .2 1 ± 1 0 .9 5 2 3 .8 2 ± 6 .6 4 2 G eo m -G C N * 8 5 .3 5 ± 1 .5 7 2 1 .0 1 ± 2 .6 1 1 3 .9 8 ± 1 .4 8 1 3 .9 8 ± 1 .4 8 1 3 .9 8 ± 1 .4 8 1 3 .9 8 ± 1 .4 8 2 7 8 .0 2 ± 1 .1 5 2 3 .0 1 ± 1 .9 5 7 .2 3 ± 0 .8 7 7 .2 3 ± 0 .8 7 7 .2 3 ± 0 .8 7 7 .2 3 ± 0 .8 7 2 G C N 8 6 .9 8 ± 1 .2 7 8 3 .2 4 ± 1 .5 6 3 1 .0 3 ± 3 .0 8 3 1 .0 5 ± 2 .3 6 3 0 .7 6 ± 3 .4 3 3 1 .8 9 ± 2 .0 8 2 7 6 .5 0 ± 1 .3 6 6 4 .3 3 ± 8 .2 7 2 4 .1 8 ± 1 .7 1 2 3 .0 7 ± 2 .9 5 2 5 .3 ± 1 .7 7 2 4 .7 3 ± 1 .6 6 2 G A T 8 7 .3 0 ± 1 .1 0 8 6 .5 0 ± 1 .2 0 8 4 .9 7 ± 1 .2 4 IN S IN S IN S 2 7 6 .5 5 ± 1 .2 3 7 5 .3 3 ± 1 .3 9 6 6 .5 7 ± 5 .0 8 IN S IN S IN S 2 C or ne ll (h =0 .3 ) C ha m el eo n (h =0 .2 3) G G C N (o ur s) 8 3 .7 8 ± 6 .7 3 8 3 .7 8 ± 6 .1 6 8 4 .8 6 ± 5 .6 9 8 3 .7 8 ± 6 .7 3 8 3 .7 8 ± 6 .5 1 8 4 .3 2 ± 5 .9 0 6 7 0 .7 7 ± 1 .4 2 6 9 .5 8 ± 2 .6 8 7 0 .3 3 ± 1 .7 0 7 0 .4 4 ± 1 .8 2 7 0 .2 9 ± 1 .6 2 7 0 .2 0 ± 1 .9 5 5 G PR G N N 7 6 .7 6 ± 8 .2 2 7 7 .5 7 ± 7 .4 6 8 0 .2 7 ± 8 .1 1 7 8 .3 8 ± 6 .0 4 7 4 .5 9 ± 7 .6 6 7 0 .0 0 ± 5 .7 3 8 4 6 .5 8 ± 1 .7 7 1 4 5 .7 2 ± 3 .4 5 4 1 .1 6 ± 5 .7 9 3 9 .5 8 ± 7 .8 5 3 5 .4 2 ± 8 .5 2 3 6 .3 8 ± 2 .4 0 2 H 2G C N * 8 1 .8 9 ± 5 .9 8 8 2 .7 0 ± 6 .2 7 8 0 .2 7 ± 6 .6 3 O O M O O M O O M 1 5 9 .0 6 ± 1 .8 5 6 0 .1 1 ± 2 .1 5 O O M O O M O O M O O M 4 G C N II * 6 7 .5 7 ± 1 1 .3 4 6 4 .5 9 ± 9 .6 3 7 3 .2 4 ± 5 .9 1 7 7 .8 4 ± 3 .9 7 7 5 .4 1 ± 5 .4 7 7 3 .7 8 ± 4 .3 7 16 6 1 .0 7 ± 4 .1 0 6 3 .8 6 ± 3 .0 4 6 2 .8 9 ± 1 .1 8 6 0 .2 0 ± 2 .1 0 5 6 .9 7 ± 1 .8 1 5 5 .9 9 ± 2 .2 7 4 Pa ir N or m 5 0 .2 7 ± 7 .1 7 5 3 .5 1 ± 8 .0 0 5 8 .3 8 ± 5 .0 1 5 8 .3 8 ± 3 .0 1 5 8 .9 2 ± 3 .1 5 5 8 .9 2 ± 3 .1 5 32 6 2 .7 4 ± 2 .8 2 5 9 .0 1 ± 2 .8 0 5 4 .1 2 ± 2 .2 4 4 6 .3 8 ± 2 .2 3 4 6 .7 8 ± 2 .2 6 4 6 .2 7 ± 3 .2 4 2 G eo m -G C N * 6 0 .5 4 ± 3 .6 7 2 3 .7 8 ± 1 1 .6 4 1 2 .9 7 ± 2 .9 1 1 2 .9 7 ± 2 .9 1 1 2 .9 7 ± 2 .9 1 1 2 .9 7 ± 2 .9 1 2 6 0 .0 0 ± 2 .8 1 1 9 .1 7 ± 1 .6 6 1 9 .5 8 ± 1 .7 3 1 9 .5 8 ± 1 .7 3 1 9 .5 8 ± 1 .7 3 1 9 .5 8 ± 1 .7 3 2 G C N 6 0 .5 4 ± 5 .3 0 5 9 .1 9 ± 3 .3 0 5 8 .9 2 ± 3 .1 5 5 8 .9 2 ± 3 .1 5 5 8 .9 2 ± 3 .1 5 5 8 .9 2 ± 3 .1 5 2 6 4 .8 2 ± 2 .2 4 5 3 .1 1 ± 4 .4 4 3 5 .1 5 ± 3 .1 4 3 5 .3 9 ± 3 .2 3 3 5 .2 0 ± 3 .2 5 3 5 .5 0 ± 3 .0 8 2 G A T 6 1 .8 9 ± 5 .0 5 5 8 .3 8 ± 4 .0 5 5 8 .3 8 ± 3 .8 6 IN S IN S IN S 2 6 0 .2 6 ± 2 .5 0 4 8 .7 1 ± 2 .9 6 3 5 .0 9 ± 3 .5 5 IN S IN S IN S 2

Review summaries:
Two issues confronting GCNs, heterophily and over-smoothing, share a common cause. This article asserts that the relative degree and homophily level account for node representation movement and further affect the likelihood of misclassification.   The contributions of this paper are as follows:  1) it attempts to establish a connection between heterophily and over-smoothing by identifying common causes;  2) it establishes that the relative degree and homophily level have an effect on the misclassification rate; and  3) it also designs and presents a model that allows for negative interactions between nodes, which is shown to be robust to over-smoothing and capable of achieving state-of-the-art performance on heterophily datasets.

The paper studies two problems plaguing graph neural networks (GCNs/GNNs): 1) oversmoothing of GCNs/GNNs; and 2) GCNs/GNNs often do not yield good performance on heterophilous networks. The authors aim to develop a theory to explain these issues simultaneously, where a few lemmas and theorems were developed based on certain simplifying assumptions. Based on these theoretical results, the authors develop a generalized GCN (GGCN) with negative message passing. Evaluation is conducted and compared with the state-of-the-art.