Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks
Authors: Yujun Yan
Milad Hashemi
Kevin Swersky
Yaoqing Yang
Danai Koutra
Venue: ICLR 2022 Submitted (2022)
Keywords: graph convolutional neural networks
node classification
heterophily
oversmoothing

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.

Under review as a conference paper at ICLR 2022
Two SIDES OF THE SAME COIN: HETEROPHILY AND OVERSMOOTHING IN GRAPH CON- VOLUTIONAL NEURAL NETWORKS
Anonymous authors Paper under double-blind review
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 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, 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.
aim to: (I) analyze the
In our theoretical analysis, we show that the common causes of the heterophily and oversmoothing problems- namely. the relative degree of node (compared its neighbors) and its heterophily level level-trigge trigger the node representations in consec- utive layers to "move" closer to the original decision boundary, which increases the miselassification 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 node's 's neighborhood can influ- ence the movements node representations and result in a gseudo-hhetrophhe 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 hetcorophily 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.
INTRODUCTION
In recent years. GCNs (Defferrard et al. 2016 Kipf & Welling 2016: Veličković al. 2017
2019) and biology Yan et al., 2019 to program understanding (Allamanis al. 2018] Shi et al. (019). A typical GCN architecture (Gilmer et al., 2017) for the node classification task can be decomposed into two main components:
have been widely used in applications ranging from social science (Li & Goldwasser
propagation/aggrrgattion and combination. Messages are first exchanged between neighboring nodes, then aggregated. Afterwards, the messages are combined with the self-representations ka.k.a., the current node representations) update the node representations. Though GCNs are effective, they have some key limitations.
The first limitation the "oversmoothing" problem (Li 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 the node classification task (Oono Suzuki 2019) and that the node representations converge to 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 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 empirical analysis, by dividing the nodes in real graphs into

---

Under review as a conference paper at ICLR 2022
several degree groups and tracking their average accuracy while increasing the layers of GCN (iipf & Welling, 2016), we observe two phases (Fig. []:: 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 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 per- formance on heterophilous graphs (Pei et al.) uhich-unlike unlike ho- mophilous graphs have many neighhoring nodes that belong to different classes (Newman, 2002]. For instance, in protein networks, amino acids of different types tend to form links (Zhu ct al. 2020), and in transaction networks, fraud- sters more likely connect to accomplices than to other fraudsters (Pandit et al. 2007). Most
100
Avg fj values
2019; Lim et al.] 202T), which-
Accuracy
60
E
[40, 00
-1
E
[16.
30)
20
-1 [7, 16)
Initial Stage
Transition
Developing
Stage
[1.2]
3
Layers
Figure 1: Accuracy of nodes grouped by degree d: on Citeseer. Initial stage: when mean effective ho- mophily K (ratio of node's neighbors in the same class (3..22 is high, the accuracy increases the degree increases. Developing stage: when bi is low, the accuracy of high-degree nodes drops more sharply.
GCNs (Kipf & Welling, [0166] Velicković et al., 2017) fail to effectively capture heterophily, so
emerging works have proposed some effective designs (Pei et al. 2019; Zhu et al. 2202)), in- cluding signed messages (positive and negative interactions between nodes) proposed by concur- rent works (Chien et al. [021] [Bo et al. 202T). 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 ($ (3444..
These two limitations have mostly been studied independently. but recent work on oversmooth- ing (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 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 sfate-of-the-arr performance on datasets with high levels of heterophily, and achieves competitive performance on homophilous datasets.
2 PRELIMINARIES
We first provide the notations& & definitions that we use the paper, and brief background on GCNs.
Notation. We denote an unweighted and self self-loop-free graph as g (V. E) and its adjacency matrix as A. We represent the degree of node v; E V by d,, and the degree matrix maich a diagonal matrix whose elements are node degrees- by D. Let Mf be the set of nodes directly connected to 0; i.e., its neighbors. I is the identity matrix. We denote the node representations at I-th layer as F(1, and the i-th row of F is (("), which is the representation of node v. The input node features are given by F(0) The weight matrix and bias vector at the 1-th layer are denoted as (!)) and (*), respectively.
Homophily and Heterophily, Given a set of node labels/classes, homophily captures the tendency of a node have the same class as its neighbors. Specifically, the homophily of node v, is defined as h4 = E 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.
[ A..
where N₂ is the set of neighboring nodes with the same label Ug |- is the
2

---

Under review as a conference paper at ICLR 2022
Supervised Node Classification Task. We focus on node classification: given subset of labeled nodes (from a label set L), the goal is learn a mapping & r. + y; between each node U; and its ground truth label y/ E L. We use yi to represent the predicted label of and define the misclassification rate of a fixed learnt model over a node set V as: E
[fw [V] ( The
expectation is taken over the randommess graph structures and input node features.
Graph Convolutional Neural Networks. In node classification tasks, an L-layer GCN con- tains two components (Gilmer al.) 2017]: (1) neighborhood propagation and aggrega- tion: 1 = AGGREGATE( Dj E No., and (2) combination: r(((1) = COMBINE(T")
r1") where AGGREGATE and COMBINE are learnable functions. The loss is given by wwa:FooosEntroyyoootttaaata ((()))))a(((( + bb44), y4). The vanilla GCN suggests renor- malization trick on the adjacency A to prevent gradient explosion (Kipf & Welling 2016). The (I (+ 1)-th output is given by: F(++1) = a (AF (F(), where A = D (1 A)D 172 D is the degree matrix of + A, and a 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 widely used in theoretical analyses (Oono & Suzuki 2019; Chen al.. 2020). For SGC, the 1-th layer representations are given by: F()) = F and the last layer is logistic-regressonn layer: di Softmax (T.) + b(*)). We note that only one weight matrix
W(1) is learned; it is equivalent to the products of all weight matrices in a linear GCN, Find more related works in $
THEORETICAL ANALYSIS
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 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 denoted as set V and nodes in class denoted as set V/2 We show empirically ($5) that the insights obtained in this section are effective for other non-linear models in multi-class classification.
3.1 ASSUMPTIONS
Next, we use "i.d." to represent random variables/vectors that follow the same marginal distribution and their joint probability density function (PDF) a permutation-invariaat function p(x1...... (xx1,...,,..... x.,) p(P(x....... x))), where P(-) means permutation.
(1) Random graph: Node degrees {d:} are i.d. random variables. {(-):} represents a set with
i i= 1,.... D/. (2) Inputs: 12.1) Node labels {vi} are i.d. Bernoulli random variables given by the
ratio p: p 2))=2))
Vi. (2.2) Initial imput node features [1(") are i.d. random vectors given by (PDF)
[u. when y/3 1. fx),, which is expressed as: f(x) [f((x), when y; = 2. B(C(")) (yv)) 1-p
[x)), when y, 1.
when y/s = 2.
so E(C!") = 0. (3) Independence: } are independent of {v:} and (r!")),
3.2 MISCLASSIFICATTIN RATE& & MOVEMENTS OF NODE REPRESENTATIONS
The following lemmas illustrate why the movements of node representations are good indicator of SGC's performance. We view the changes of node representations across the layers as their movements; i.e., p((+1) is moved from r.") Vi. The misclassification rate of an L-layer SGC is determined by {f. ()), which is the input to the last regression layer, and can be studied through the decision boundary of r.7)
Lemma 1 In SGC, the decision boundaries w.r.. (F. 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.I
The decision boundary of an (L + 1)-layer SGC can be viewed as perturbation to the decision boundary of an L-layer SGC due to the movements from (r(2)) to (r((+1)). Due to Lemma 1,
use the hyperplane xw + b 0 to represent the decision boundary of (E(")) f(()) w + > Suppose when w and b b², find optimal hyperplane xw" 1² that achieves the lowest
). where w
a unit vector, b is a scalar, and the (F(")) are classified to class if
3

---

Under review as a conference paper at ICLR 2022
Homophily
Class
Relative Degree
Low
High
High Loor
Case
(MR[)
Before eggregation
Case
Case
(MR])
Case
Case
Case
aggregation
Figure Node representation dynamics during neighhorhood aggregation (in 1D for illustration purposes; 'MR': misclassification rate). The expectation of node representations from class & 2 are denoted by j and /4, respectively. The bars show the expected node representations of node v; before and after the aggregation.
total misclassification rate ($ 2 for {E."), Due to the movements of node representations, the new optimal hyperplane is decided by: xw" + b" = O. In Lemma 2, 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 [r,42) from class by adding -Iw*f, I > O, s.t. w w > O, the new total misclassification 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* w- > 0 and leads to different conclusions. We refer to the condition w w" > as "non-swapping condition" and throughout the paper, we analyze SGC
under that. Lemma 2 shows that, under the "non-swapping condition", if (f(") move towards the original decision boundary (or the other class), SGC tends to perform worse
3.3 MOVEMENTS OF NODE REPRESENTATIONS IN SHALLOW AND DEEPER LAYERS
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, d,, of node 0, and assume that U, is in class 1. The results in class 2 can be derived similarly.
3.3.1 INITIAL STAGE: SHALLOW LAYERS
Theorem 1. [Initial Stage] Under the "nop-swapping condition", during message passing in shallow e but
layers, the nodes with low homophily h S 1hg and the nodes with high homophity h; > 1+p
small relative degree are prone to be misclassifed.. Defining riş = = d++1 and the relative degree
EAjd,,en (d EjeN, Tag), the conditional expectation of representation F(2) is given by: B(E(") = 7d B(E!)) (1)
((1 + p)h; p)ddr +
E (f (f V1.d4)
di d+1
where the multiplicative factor 77 is:
(-00, 4
if
d E
(0,1),
Th + & (Itp)hi-p
(1,
otherwise.
Proof. We provide the proof in App. A.3
A.3
From Thm. [ we identify three types of movements of node representations, which are characterized by relative degree 7i and homophily level h;, For illustration purposes, in Fig. we illustrate the three cases when apply our theorem to ID node representations. The bars reflect the value change of ut'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 the heterophily and oversmoothing problems:
In heterophilous graphs, node representations move heavily towards the opposite class. According Lemma 2, under the "non-swapping" condition, it indicates higher misclassification rate (i.e., poorer performance) for SGC.
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 seeudo-heterophit situation (case 1) later.
4

---

Under review as a conference paper at ICLR 2022
3.3.2 DEVELOPING STAGE: DEEPER LAYERS
The following theorem analyzes the pseudo-heterophily scenario in deeper layers. Based on Thm. [ message passing will result in scaling the node representations (7/² and some nodes may cross
the origin. To account for those, let E be an accumulated discount factor at the 1-th layer and
E (n.)))( 14 are defined as: (A, = (1sl0s E Ns and (L) -E (u.),, HEE
d:+1 14 = g/p. Conditioned on A and E), the nodes contributing positively
(19
0}. We
1/ (ENN((A +
denote: TE (.....(r JdistheeEN ro Eh. EN.)
& and U/ (
of characterize the neighborhood property e, We further define the effective homophily of node i as ię = (u, E Ni EV, di, {)). 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 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 Til is sufficiently low (T). S (gg)), the nodes with higher effective relative degree are prone to misclassification. Specifically, by defining the effective relative degree as r,' = e¹ the conditional expectation of (! p!l+1) is:
g..
(1L,(1 + p - pb)ddr + +1) d; +1
( (d., (1+2))dd,.))
E A. H(.E!)
5/u 7/
(3)
Proof. We provide the proof in App. A.4 Other nodes can be derived similarly.
We note that Eq. (3) holds for layers for most nodes i as part of the initial stage, they exhibit three cases similar to Eq. 2
in general. We regard layers for which 7 > 1t
holds
3.4 SIGNED MESSAGES & MOVEMENTS OF REPRESENTATIONS
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 -ruth labels are not accessible for every node, so we use approximations, which introduces errors. For node us we define m. as the ratio of neighbors that send incorrect messages at the 1-th layer (i.e., different-class neighbors that send non-negated messages and same-class neighbors that send negated messages). We define the I-th layer error rate as of = Emm)), where the expectation is over the randomness of the neighbors that send incorrect messages. We make the following assumption: m is independent of {de), {y,} and {f")-
Theorem 3. [Signed Messages] With the independence ussumptions 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 homophity level he, and will be dependent on the error rate c, Specifically, the multiplicative factor 7 at the first layer is:
(1 11-20 12-2e) + ((10+(111111 - p)h.)ddrs++ +1 F +=> E(F
E A. M Hd. (P()
① Idd, 14 /dd.ueVi (2)=
de 1 1
(4)
(-o0,
ife > 0.5
where oo E
(0,
ife 0.5
(1 (1-2e")(ot(-pp)))
(5)
(0))
otherwise.
Proof. The proof is provided in App. A.5
From Eq. 5 we see that when using signed messages, to benefit from case 3 (7) >> 1), the minimum relative degree satisfies: rú (1 (1-2:)ee(11-p)))) p/h.) Given h2 & 1, if the error rate is low (cf < 0.5),
(1+)),,-p' and (T+ 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 low error rate cannot be guaranteed, signed messages may hurt the performance.
we get: (1=2e")
5

---

Under review as a conference paper at ICLR 2022
4 MODEL DESIGN
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 decaying combination of the current and previous node represen- tations (Chen et al. 2020), into generalized GCN model, GGCN. In $ we empirically show its effectiveness in addressing the two closely-related problems.
4.1 SIGNED MESSAGES
Thm 3 points 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 learnable linear transfor-
mation of each node's representation at the I-th layer: F F + (() Then, we define sign function to multiplied with the messages exchanged between neighbors. To allow for backpropaga- tion of the gradient information, we approximate the sign function with cosine similarity. Denote S'
as the matrix which stores the sign information about the edges, defined as: [i. =Cosine(f""
((")) if (i (i j) & (uy E NG);; 0 otherwise.
In order separate the contribution of similar neighbors (likely the same class) from that of dissimilar neighbors (unlikely to be in the same class), we split (()) into a positive matrix Spo and negative matrix S0 Thus, our proposed GGCN model learns weighted combination of the self-representations, the positive messages, and the negative messages:
p(++1) = o o² (5g F()) + S @ A)F + A A @ A)F
(6) where 8g. 31 and 34 are scalars obtained by applying softmax to the learned scalars By 0f and 8y: the non-negative scaling factor a² softplus(a') is derived from the learned scalar a'; @ is element-wise multiplication; and a is the nonlinear function Elu. We note that we learn different and 3 parameters per layer for flexibility. We also require the combined weights, à' 31, to be non-negative so that they do not negate the intended effect of the signed information.
4.2 DEGREE CORRECTIONS
Our analysis in $ 3.3 and bighhiihll that, when the error rate and homophily level are high, oversmoothing is initially triggered by low-degree nodes. Thus, 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 relatively low error rate at the shallow layers (i.e, of < 0.5 for small I), we require that the node degrees satisfy rī > (== to prevent oversmoothing. Since the node degrees cannot be modified, our strategy to rescale them. Specifically, we correct the degrees by multiplying with sealars rly and change the original formulation as follows:
F.
(AF [i.
F(O :]
+
Σ MEN,
F j.
(7)
d: +1
Vd. +i.+idd
Vd
+1
YEM
((4++1)1))) dy+1
This multiplication is equivalent to changing the ratio rij in Thm. to
That is, a larger
Th increases the effective r; layer l. Training independent Thy is not practical because would require 0(112) additional parameters per layer, which can lead to overfitting. Moreover, low-rank parameterizations suffer from unstable training dynamics. Intuitively, when Túj is small, we would like to compensate for it via a larger T..- Thus, we set Th to be a function of ray follows:
softplus (26 1/ - +x))
(8)
where X/ and X are learnable parameters. We subtract 1 so that when rig = 1 (i.e., d, = dz), then T = (oftplus(X1) 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 / 1:
p(+1) a @ ( { ! À @ ( IPO) + 8 Sneg
A T )TO)
where ( is a matrix with elements T/y-

---

Under review as a conference paper at ICLR 2022
4.3 DECAYING AGGREGATION
In addition our two proposed mechanisms that theoretically grounded in our analysis ($ 3. we also incorporate into GGCN an existing lriign-decayingg aggregation of messages- 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.II.
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, n). and integrate it to our GGCN model:
F p(+1) = F +
(sp A
F + +
(S
(1) neg
A T
(10)
In practice, we found that the following decaying function works well: n In( + 1), iff 2 40: f 1, otherwise. The hyperparameters k. lo. 17 are tuned on the validation set.
EXPERIMENTS
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
5.1 EXPERIMENTAL SETUP
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.) 20188] 18) We provide their summary
statistics Table where we compute the homophily level h of graph as the average of h; of all
nodes U2 E V. For all benchmarks, we use the feature vectors, class labels, and 10 random splits 228% of nodes per class for vrain/validation/ts// from (Pei et al. 2019).
Baselines. For baselines we use (1) classic GNN models for node classification: vanilla GCN (Kipf & Welling 2016). GAT (Veličković et al.) 2017) and GraphSage (Hamilton et al. (017]; (2) re- cent 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) -ftaae-of-the-arrt; and (4) 2- 2-layer MLP (with dropout and Elu non-linearity). ). For GCN, PairNorm, Geom-GCN, GCN, GCNII, H2GCN and GPRGNN, we use the original codes provided by the authors. For GAT, we use the code from well-accepted Github repository For GraphSage, we report the results from (Zhu et all 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.
Table 1: Real data: mean accuracy = stdev over different data splits. Per GNN model, we report the best performance across different layers. Best model per benchmark highlighted in gray. The "i" results (GraphSAGE) are obtained from (7hu et al. 2020).
Texns
Wisconsin
Actor
Squirrel
Chamelcon
Cornell
Citeseer
Pahmed
Cora
Hom, level
0.21
0.22
0.23
0.3
0.74
0.8
#Nodes
183
251
7,00
5,201
2,277
3,327
19,717
2,708
#Edges
295
466
26,752
198.4 493
31,421
280
4,676
44,327
5,278
#Classes
5
5
2
GGUN (ours)
84.8654.55
86
37.64
55.17a1.4
71.14a1
47.14
87
1.78
GPRGNN
78.381133
92.44110
34.6311
31.61
46.58.17
80:27-411
77.18-1-47
87.54
87.06
5.56
H2GCN*
84.8617.33
87.651456
18.48.1
60.11.215
82.70.5.
17.11.3.07
80.49.0.3s
87.87.1.20
3.89
GUNIP
77.57
80 80.90ass
37.44
38
63
77 m0
77.33=1.0
90-15a0.s
3.56
66.7612.79
64.5143m
31.5011-5
38.1610m
01.00.381
00.54.3.77
78.02-111
80.06.0.17
86.35u11.5
6.11
PairNorm
60.271433
49.431611
27.40
50.441201
62.741880
15.92_315
73.50_1.47
87.3316.4
85.7011.63
7.78
GraphSAGE!
82. 22.4330.14
$1.18
34,23
41.61a024
75.96an.. 58.73a1.
76.04-1.30
$8.45sc.10
86. 80.90s1.24
5.78
GCN
65.14
51.
76
27.32=1.1
58.09e2m
61 64
00.54es.3
76.50=1.30
88.12a0a
80, 18.17
6.56
GAT
62.16
89
27.444029
40.72a1as
80
76.55-1.28
86.33es.4s
57.30e
7.22
MLP
50.51e477
85.29ena:
30.53a..0
28.77a1.55
46.21a2m
81 40 74.02-1.00
87.16e0.77
75.00
6.78
Pei et al. 2019) claims that the ratios are 60%/220%/20%, which is different from the actual data splits
shared on GitHuu.

---

Under review as a conference paper at ICLR 2022
Table 2: Model performance for different layers: mean accuracy + stdev different data splits. Per dataset and GNN model, we also report the layer at which the best performance (given in Table is achieved, 'OOM": out of memory: 'INS": numerical instability, For larger font, refer to Table D.I in the Appendix.
Layers
32
64
Best
2
32
64
Best
Clusser dee 74)
10:00
GERGNN
67.05.1.4
87.25-331
57.8811
67.52
4..05.1.44
70.00
74.7711
HROON*
46 10x
86.
00M
00M
00M
76 70.00121
70.00:1
76
T4.10aa
00M
000
00M
GCNI
65.85-1.36
86.85
86.5
87.12
57.0611:3
88.57
64
10.42
76.20...9
70.30
70.36
77.881.4
17.15
32
PritNvem
65-79-1-1 1
85.07 85
60.32g4
73.50x
12.32
58
Geou GUNY
85.85 1.31
21.01124:
12.9
1.30
18.2811
13.00 Lios
78 15
28.0 L..
7,23
7,28
7.281aa0
7.25.003
66.08-1-17
3:100aa.e
31.05.m
50.76ass
34
25.3a1 25.0
GAT
87.00.100
84.07a
IN8
76.33.1.29
15,07
185
Cocnell (1-033)
Chanctoo (6-8.23)
GGCN (mm)))
70:77a::3
10:35
GPKGNN
76.76...2
17.07a5.a
80.271x-u
78.
74.201044 es
70.0015.0
4..58.1.771
45.72.0.4
41.3615.1
50
30.881245
35.42.a.3
36.86...0
H2OCK*
61.80
80.27axmm O0M
00M
00M
50 30
60.11
00M
00M
000
O0M
GUNIT
07.572:1 14
64 64.09um
77.8
47
75
70.7814.0
16
61
63
02.8012.11
56977.1
65.9915:87
PainNiem
6027-707
68.584xmm
68.90-mm
68.02.311
33
62.7442aa
30001-29
54.12a2
46.38.22x
46.78a2
26.27a
67
12.07a300 1247-0.1
19
00:00122::
1M:17a1
19.3Na1
GCN
36.30
GAY
61.89g1
38-38g-
58.5823-0
INS
188
1NS
48.71ge 00.00277
03.00gs00
1NS
188
INS
5.2 Q1. PERFORMANCE UNDER HOMOPHILY HETEROPHILY
Table 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 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 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 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.
5.3 Q2. OVERSMOOTHING
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 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- a 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
Ai once the effective homophily is lower than I+p 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 its robustness oversmoothing.
8

---

Under review as a conference paper at ICLR 2022
5.4 Q3. EMPIRICAL VERIFICATION OF THE INITIAL & DEVELOPING STAGES
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 shows the results for Citeseer. In the initial stage (h) 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.
6 RELATED WORK
Graph Convolutional Neural Networks, Early on, (Defferrard et al. 2016) proposed 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 localized first-order approximation of spectral graph convolutions proposed in (Kipf & Welling 2016). (Veličković 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 al.) 2201)), algorithmic
tasks (Veličković et al. [020] Yan et al. 2020), and inductive classification (Hamilton et al. (017)).
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 (Li 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 Akogiu 2019); edge dropout (Rong et al. 2019); and 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 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. is first outlined in the context of GCNs in (Pei et al., 2019)). (Zhu et al., (020) identified a set of effective designs that allow GCNs generalize to challenging heterophilous settings, and (Zhu et al. 202T) introduced a new GCN model that leverages ideas from belief propagation (Gatterbauer et al. 2015). Though recent work (Chen al. 2020) focused on solving the oversmoothing problem, 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- 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 principled manner provides superior performance across variety of datasets.
7 CONCLUSION
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 variety of domains.
9

---

Under review as a conference paper at ICLR 2022
8 REPRODUCIBILITY STATEMENT
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. $ we provide detailed hyperparameter setting for GGCN. We also provide our code in the supplementary material and we will share the link our code upon acceptance.
REFERENCES
Miltiadis Allamanis, Mare Brockschmidt, and Mahmoud Khademi. Learning to represent programs with graphs,
2018.
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi-supervised classifi- cation: Improved linear separability and out-of-distribution generalization. arXiv preprint urXiv:2102.0690 2021.
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. arXiv preprint arXiv:2101.0079 2021.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive
learning via ranking. International Conference on Learning Representations (ICLR), 2018.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pp. 1725-1735. PMLR, 2020.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network, 2021.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 3844-3852, 2016.
Wolfgang Gatterbauer, Stephan Günnemann, Danai Koutra, and Christos Faloutsos. Linearized and single-pass belief propagation. Proc. VLDB Endow. 8(5):811599) January 2015.
Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference machine learning, pp. 1263-1272. PMLR, 2017.
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 1rXiv:1609.02000 02907, 2016.
Chang Li and Dan Goldwasser. Encoding social information with graph convolutional networks forpolitical perspective detection in news media. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 2594-2604 2019.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as enns? In Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 9267-9276, 2019.
Qimai Li, Zhichao Han, Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- supervised learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
Derck Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Newral Information Processing Systems, 34, 2021.
Galileo Namata, Ben London. Lise Getoor, Bert Huang, and UMD EDU. Query-driven active surveying for collective classification. In 10th International Workshop Mining and Learning with Graphs, volume 8, 2012.
Mark EJ Newman. Assortative mixing in networks. Physical review letters, 89(20)200870,, 2002.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. International Conference on Learning Representations, 2019.
10

---

Under review as a conference paper at ICLR 2022
Shashank Pandit, Duen Horng Chau, Samuel Wang, and Christos Faloutsos. Netprobe: fast and scalable system for fraud detection in online auction networks. In Proceedings of the 16th international conference on World Wide Web, pp. 201-210, 2007.
Hongbin Pei, Bingzhe Wei, Kevin convolutional networks. International Conference on Learning Representations, 2019.
Chang, Lei, Bo Yang. Geom-gen: Geometric graph
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. International Conference on Learning Representations, 2019.
Ryan Rossi, Di Jin, Sungchul Kim, Nesreen K. Ahmed, Danai Koutra, and John Boaz Lee. On proximity and structural role-based embeddings in networks: Misconceptions, techniques, and applications. ACM Trans. Knowl. Discov. Data, 14(5), August 2020.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. arXiv preprint arXiv:1909.1300 2019.
Victor Garcia Satorras and Joan Bruna Estrach. Few-shot learning with graph neural networks. International Conference on Learning Representations, 2018.
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, 93, 2008
Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop. NeurIPS 2018, 2018.
Zhan Shi, Kevin Swersky, Daniel Tarlow, Parthasarathy Ranganathan, and Milad Hashemi. Learning execution through neural code fusion. International Conference on Learning Representations, 2019.
Jie Tang. Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In Proceedings of the 15th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 807-816. 2009.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.1090 2017.
Petar Veličković. Lars Buesing, Matthew Overlan, Razvan Pascanu, Oriol Vinyals, and Charles Blundell. Pointer graph networks. Advances in Neural Information Processing Systems, 33, 2020.
Guangtao Wang. Rex Ying, Jing Huang, and Jure Leskovec. Improving graph attention networks with large margin-based constraints. arXiv preprint 1910. 2019.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference machine learning, pp. 6861-6871. PMLR, 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian. Tomohiro Sonobe, Ken-ichi Kawarabayashi. and Stefanie Jegelka. Representation learning graphs with jumping knowledge networks. In International Conference on Machine Learning, pp. 5453-5462. PMLR, 2018
Yujun Yan, Jiong Zhu, Marlena Duda, Eric Solarz, Chandra Sripada, and Danai Koutra. Groupinn: Grouping- based interpretable neural network for classification of limited, noisy brain data. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp. 772-782, 2019.
Yujun Yan, Kevin Swersky, Danai Koutra, Parthasarathy Ranganathan, and Milad Hashemi. Neural execution engines: Learning to exccute subroutines. Advances in Neural Information Processing Systems, 33, 2020.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. International Conference on
Learning Representations, 2019.
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, 2020.
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In AAAI Conference on Artificial Intelligence, 2021.
11

---

Under review as a conference paper at ICLR 2022
A DETAILED PROOFS OF THEOREMS IN $
A.1 PROOF OF LEMMA 1
Proof. The loss function for SGC is: CrosstittrroyyS6fttmxxxxx
(()),, yi). Rewrite
((L) into an array of column vectors: W(4) = !wo w (4)
w [2]) b(4) into an array of scalars:
((T) = 1b6d) b1th ............................... .... -/2) and F(4) into an array of row vectors: F(L) = 150 () L.)
1i (=+1
1,
iff yb then we otherwise
means stacking vertically). Let Pi,c
Σ woo and let Vi.
0,
rewrite the loss function as:
yi.e log(pt.);
(11)
1=1
is the number of nodes used for training. To predict that the node 2 belongs to class c, we require:
de' # c, Pi.c Pi,ee Thus, we have:
w 4
+D2
(12)
(0) w3 11 +0
E,
It is equivalent to:
F. w(L) (( > ff" w (2) + 6
(13)
shows that the decision region of class e is decided by a set of hyper-planes:
x(w!!) ( (6( (1 =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 one hyper-plane.
A.2 PROOF OF LEMMA 2
Before giving the proof, we first explain the meaning of the LeMma. As we point out in $ $ the misclassification rate of an L-layer SGC can be studied through its last logistic-regression layer, the input to which is (f(2)). ). To study the misclassification rate of an (L + 1>-layer SGC, we can view the input the last layer (r(2+1)) being moved from (r(4)). 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 the original decision boundary; we will prove that moving towards the original decision boundary by non-zero step not beneficial (i.e., harmful) 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 ( as f( conditioned on that they are from class 1 and (x) conditioned on that they are from class I or class 2. respectively. To note that, the distributions of different layers are different.
After the movements, the representations from class 1 become: (r(2) represents moving towards the original decision boundary along the norm direction by a non-zero step. This causes corresponding change in the conditional PDF given that they are from class 1: (x T.)
/ J, 0. /w
Recall that in $ the parameters for the original optimal hyperplane wt and 6*, and the parameters for the later optimal hyperplane wx and b* normalized such that when xw" + b" 0 and
xw +b" > 0, we predict class 1.
The new misclassification rate conditioned on class I is:
[
Xxw'4 f tw" T f(
Mf
/xx-t"0 ff (x)dxx
(15)
12

---

Under review as a conference paper at ICLR 2022
The new misclassification rate conditioned class 2 is:
Mf SSw (x)dx.
(16)
The new total misclassification is:
M' = MMP( E V1) + MiP(Us E V2)
P(e. V1)
P(u, V2) P(u; E Vi) + P(u; E 12)
Mi P(ey E Vi) + P(u: E V2) + +M²
(17)
p Mi + My-
Next, we will prove that if the total misclassificattin is lowered, xw" + 6- = 0 is not the optimal hyper-plane before the movements which should achieve the lowest total misclassification rate.
Consider hyper-plane xw" + b"d 1w Tw" w' 0. Given that w *T w > and / >> 0, for Vx, s.t.
xw" +b" tw"? < O, we have: (x-I w +b" xw" + b²d tw 7
tw
2
2
It means:
[x|(x- - tw tw"" + +b" <0} 2 fx|xw" +bV tw war
< <0}.
(18)
2
Because (x) is a PDF which a nonnegative function,
fx 2 /
ft (x)
(19)
(x-t 46
xww 4b Twr <0
Similarly, we can obtain
[x/xw" +0'0>0 >0} 2 fx/xw>' + -b0¹ tw"T w
2 > 0}.
(20)
Thus,
J (x)dx > I /xwer4bu sw Twrl 20
ft' (x)dx.
(21)
Define
P Mj p + /ww Two <0
(x)dxx +
f (x)dx.
(22)
p Jxw
The quantity My represents the total misclassification rate before the movements the decision
boundary is xw" +6" Tw" O. Given Eq. 17 19 and 21
we have:
M' 2 My.
(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 > My.
(24)
Eq. 24 indicates that we find a hyper-plane xw* + 6" fw w O, which yields smaller total
misclassification rate than xw" + b' before the movements. This contradicts the fact that
xw* + b is the optimal hyper- plane before the movements.
A.3 PROOF OF THEOREM 1
Proof. The first layer node representations are given by:
(0)
(1)
(25)
+
v de
+I
dd +1
JEN,
13

---

Under review as a conference paper at ICLR 2022
Without loss of generality, assume node v is in the first class V1. Then, we express the conditional expectation of f( as:
E "dd (E) I/ E d,) = EAjd,men (E (B (uch10)) " (f." E V1,
(26)
Recall that A is the graph adjacency matrix; the first expectation is taken over the random- ness of ground truth labels and initial input features, and the second expectation is taken the randomness of graph structure (A) given the degree of node ey and its label. Denote
(V2) and h2 E ( HoLev,,d, [1 4 E J.n.n,, (NN))
(4. V)
E (uch HA
F.0) d,+1 us E VI,A
+
Σ
E
1s E Vi,A
Vdi+ +I vd, +1
JEN,
P(U, E E A A )
11
+
E ( HAA,,,e
d: +1
Vd, +1
vdz +
jEN
p(0)
+E (u.hit)) HARVE,
A E V
P(us E Vs
Vd.+I dd
(27)
Let (.) represent the indicator function: equals if and only the event in the bracket holds.
Σ
H(u VVIA,, vi))= E P(es E VIJA & E Vi) d.kg (28)
HAA HA
JEN.
JEN,
Due to assumptions in 3 though the labels of nodes are dependent, they share the same marginal distribution and their joint distribution is permutation-invariant function. Thus, given w Vi (y: 1), the conditional joint distribution of (yel4 + i) is also permutation invariant- ie.. Vj.j" E PM, E Vilu, E Vi) P(u/ E Vilu, E Vi). Then for Vj E N, we have: d,P(ey E Vilu; E V1) = d;k; and P(ey E Vile, E Vi) = kū Due to the independence of A and (v.). P(ry E Vi - kg.
E (u.. A (1:2)) E V1, A)
Σ
KG
(1 k.)
+
Vd, + 1. /d, + P/
di +
Vd: + +1
dl +1
JEN,
1
((1 + p)ki 1)
Σ
1
+
Vd; +1
Vd +1
JEN.
EjEN. Vo,+I
((1 + p)k: - p)
d. +1
Vdd +1
ΣjEN. Vd,+I Vdz+I
((1 p)k;s pp) p)
d ++
d; +1
1
dj EjEN, Tij ((1 p)ks p)) /..
+ d; +1
d +1
dj
(29)
Combining Equation 266 and Equation
29 and given the independence of rij and ki we have:
EZeess Tij
E (100) (f.2 E V2, d+)
d, + + d, + EAId,,,e
E EAldimen ((1 ()k - p)) 4
di
1 + ((1 + p)h1 - -
μ= u H.p.
d, +
(30)
14

---

Under review as a conference paper at ICLR 2022
Define (1 + p)h; (3) h4 > P ri >
P. and consider three cases: (1) h; $ Itp (2) h4 Ttp & ? and
1tp
CASE 1: h4 S I+p
Upper Bound
We have:
1 d; +1 S 2
(31)
Lower Bound
To see if there exists lower bound, we first show that when h, S Ttp. decreasing function of d, given that d; 1.
11((t))); is
d+1
When h2 E
___ T+p' we have:
((1 + p)h; - p) 0
2. d;
0,+1 is an increasing non-negative function of d,
3. 77 an increasing non-negative function of d; 1
4. 2.+1
is a decreasing function of d;
1+((1+p)h:-odds is decreasing function of d,.
Thus
d,+1
When h; 0
(M((L+p)h-p)dd d:+1
d.+1 and - S 2.
Itp'
When h, I+p'
1 + ((1 + p)h - p)d.T
((1 + p)h - p)d,rr
<
+
d2 +1
dj +
2
(32)
((1 + p)h P)TT
2
And we know that when h2 :
((1 (11+phh: p)
lim
+ 2
-00.
(33)
2
Thus,
1 ((1 + p)hn p)d.T
lim
-0.
(34)
400000
d, ++1
CASE 2: h4 >
P
I+p
If e.
if < 1. < o7. S 1. Given
B(f')= = + ediT.
d; + μ.
(35)
we have 0 <
d.+l < <n 1.
CASE 3: h4
P
.4 >
I+p
this case, Equation 35 still holds, since h4 > Itp
Lower Bound
If 1 then er; 1 and therefore 7/ 1.
15

---

Under review as a conference paper at ICLR 2022
Upper Bound When e > 0,
1 cd,
cd,T,
dj +1
d, +1
(36)
Cii
2
Because
e7i = 00,
lim
(37)
77-000 2
we have:
1 Ed.T%
lim
oc.
(38)
7-0000
di +1
To sum it up.
(-00, 2) (0,1],
if S p
1mp if - & r3 S (1+0)/;-P
(39)
(1,00),
otherwise.
Remarks: Special cases
For different types of graphs and different nodes in the graph, d,7, might be different. For a d-regular graph whose nodes have constant degree or graph whose adjacency matrix row-normalized, will have:
1 ((1 + p)h+ p)ddT
7/
d; +1
(40)
1
d;
<( (d: 1)
+
=1
(d: + 1)
Equality achieved if and only if h; 1. To note that, h; not achievable for every node as long as there are more than one class. Boundary nodes will suffer most.
A.4 PROOF OF THEOREM
Proof. After propagating over multiple layers, we use to account for the accumulated scaling (!))
effects (7/).. That is, E. A Au "
C/p. Furthermore, conditioned on A and c/. the set of nodes contributing positively to node u, is defined as:
d:+1 [d;
( e! <.
N2 ( {uyloy E N, and (E(u)- E HEL
> 0}. Uy N by (ENN((,
c -pss!
E Ma.. (lyyd, E EN
In the following proof, we use Nit to refer to No (A (A,E) for conciseness.
The representations (1 + 1) layer:
p())
P(O) dd + / +1
(+1)
(41)
d; +
JEN,
16

---

Under review as a conference paper at ICLR 2022
plit2) di E E/
(42)
(t Hdii
p(() di d 14+1dd15)) (d
E ((.
E A......)(( dell
Σ JEN,
de $H1
vd: + 1 vd, +
t
(1)
d+ +1 vd +1
di +1 A. di +1
+
Σ JEN,
di E
(44)
In $ 3 we assume that {dj} follow the same distribution and their joint distribution function is permutation-innartee and {y,} and {f/} also have this property. Thus, conditioned on d,. c and M.
the distribution of 1 Vd.+1 is the same for Vjj N, (neighbors are indistinguishable and we obtain:
Vd,
(1)
dd
E Ha.
Σ
dd Ni.
(45)
Vd, +1
JEN.
(())
Vdd+I
= d. A.(x:) (.dl.MMe dasl.NW.e
|d Ni, og E eV:
(46)
+
Given that the joint distribution of {dy}. the joint distribution of {go} and the joint distribution of (}} are permutation-invariiat functions, for any N,.
HA.. pl Vd,+1 EjEN, vd,+1 du No
"t
is the same. That is:
1 Vdl +1
E A. Hddie!
Σ
Vd, +T Idi,
(47)
JEN,
12(0 Vod++ +1
E AA
Id st..G.
(48)
Vd, +I
JEN,
((1) Vd +1
d,E
Idi, st. 1. EN
(49)
Vd +1
We note that Uy in Equation can be any node except t; due the equivalence of those nodes.
17

---

Under review as a conference paper at ICLR 2022
Combining Equation 44 and Equation 49
obtain:
gettt) (44t)dd.E)
E
Aa " Haiss
(50)
(()) Vd.
di
+
B (e
1d idi.Sto my EN,
(51)
d, ++1
d4 +1
Vd, +1
E
di
(P() Vd +
|d E/ E EN EN
(52)
de +1
di +1
V +d
1 Vd, +1
(1)
oj E Nolos E Ni
+ E E JAN
dis c Uj & NN
A63
V +1
oj @ N;, S/ EN.)
(54)
[ddP(us Nildi, E ENi)
E!' d.(1 P(uy Niidd, 4 Uj ENI)
pist 14
(55)
d, 4+11
d+1
d +1
E/P
d((P(u E Nyyde & oj EN) + p)) - -
+
(56)
d+1
dc +1
Define F.' <f' If we know the degree d,, E and that a neighbor vj is in the group Nj, Fi द..
actually represents the ratio of expected fri, to expected r/. We regard it as the effective related degree at 1-th layer. For the initial layer, if we know the degree d4 yı, and that a neighbor vy is in the group N2, the ratio of frrs to f.) is rij. Recall that the related degree 7; at the initial layer the expected average of rij in the neighborhood. Thus ri an extension of r7. Moreover, let i P(u; E A E NN, de { represent the probability
neighbor whose representation has positive contribution in expectation. This naturally extends the meaning of homophily in deeper layers. Thus, we regard it as the effective homophily of node u, at (-th layer. Given the degree d,, E/. p represents the ratio of the probability that a neighbor will have positive rather than a negative contribution to v, This naturally extends the meaning of p.
further write Equation 56as: as:
$t
(1+ ((i/a 0b) ddarrt)
di +
and it will have three cases similar to Thm.
18

---

Under review as a conference paper at ICLR 2022
A.5 PROOF OF THEOREM 3
Proof. Similar to Equation 26 we can express the conditional expectation of (()) as:
E A. HAREEn (1 vi,
=Bmg neVid E (
(1 I1 E Vi, di,d,,1, m!) (0)
BBmg nEVid
E (A
1i V1, di, mi
di +
r
|/s E Vi, )
Σ JEN;
+B Muu
/dd + /d +1
d; +1
P10)
+Bmg neVid BAIdimeni
E
(va+ +1 V
A A. A. E V2
JEN:
PP(y E Vilm, V1,A)
(1)
+E
A m V1, E V12
P(uy E Valm!)
Vd,+ + v dd
(57)
Next, we will show how to compute conditional expectation and conditional probability in the summand.
(0)
E (t
mm. us V1, A
vd. II I. dd +
p()))
=E "AL.
A, mp v; E Vi, E Vi, uyrongll send information
Vd. +I I. d,
Wrugglyngly send information A, m. o E V. E V1)
(()))
+E JA.e"" (Va,+1
A m. Us uy E V1, u,correclly send information
d +
correctryy send information A, m. da E V1, E V1).
(58)
Combined with the independence assumption, we have:
Pl wrongly send information A, mG, ve E Vi, E V1) m
(59)
Similarly, we obtain:
Ploycorrectly send information| A, m., is Vi, E V1) 1-mh 1-m
(60)
19

---

Under review as a conference paper at ICLR 2022
Then Equation 58 can be rewritten
P())
E
m U1. Uj V1.A
Vd: + 1.-1--1 d
(())
=B (wl.:f/"/A//eeee.
A m Us E V1,0, E V1, uywrongly send information
m
Wd; + 1. dj +
F,00
+E (ui).(1 "1.,,,
A m 2/ E V/ E V1, v,correctyy send information
(1 - (1-m!)
Vd, + d2 +
m p
(1 mm
vd, + dd
vd, + /d +1
(1 (1-211) 2m k
vd 11 /dz
(61)
Similarly, we have:
((()) Vd; +1 da +1 A, m, 0i E V1 E V/2
(1 2m Pm
E
vd, I. Vd, +1
(62)
Consider the independence between my and node class & degrees, and insert Equation Equation 62 into Equation (57p. we will have:
61 and
E ( Hdl..r (1.1 V),d.)
))
μ
(1 2m 2mm)kss kkipe
(1 2m (1 k:)oo))
E E
de +1
vd,+ + dd +I
vd: +I vd, +I
JEN;
))
1
(1 (1-2m (p + (1- - (1DD)i)
+ Eme.
d: +
vd: + /d, ( +1
JENS
((11221910)
((1-22 (p + +1-11)ppppp ---)hssddra 1
d; + + Empluievi.d
d++1
1 + (1 20 + (1 -p)li)d;ii
11 1= ()
d; +1
(63)
When h; S
= -1- h,)p bo 0. Define d' (1 (p (1- (1-p),.). To obtain
the ranges of 7// when ce 2 0.5, < 0. resembles the derivations of CASE in Proof A.3 when el 0.5, < O. S 1, resembles the derivations of CASE 2; when ei < 0.5, cP. > 1, it resembles the derivations of 3.
B ADDITIONAL EXPERIMENTS
B. ABLATION STUDY
Table B.I: Ablation study: degree correction has consistent benefits (robust oversmoothing & ability to handle heterophily) in different datasets while signed information has more benefits in heterophilous datasets. Best performance of cach model is highlighted in gray.
(lemt)
Ciieseer (4=0744
75.00:3.17
71.1:1M
32.06::5.4
+66g
73.01a1
-a1gn
L7
78.0744
72.31 70.641166
71981344
+dog. pi.n
86.901124
30.2010s
85.60.0.0
85.47
17.811756
76.81.7
7.68
74.09.235
73.28
71.1122
Cornell (1m30.3)
Chamelron (1m0.22)
Resd
648821 s 1200
bitllaa 47.082m12
+003
63.78
70un.ac
36.29urm
57.574420
38.92
60.61110
68 28.71:
68.00130
67 13.78
36,861a00
41.081a.e
-p1gn
70, 10.76ame
10.0us 75.514520
67.5/a544
03.24
24
59.53
33.05123e
51.05ucc
+dog. ai.n
78.02
70.8142.4
18.11-5
82
42:4
65.75-151
61.49.7.3
52 42:434
35.924611
26,96
20

---

Under review as a conference paper at ICLR 2022
We now study the impact of two proposed mechanisms (signed messages and degree correction, $ 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, choose GCN variant that uses the message passing mechanism (Kipt & 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 + iin,, and the model that incorporates the degree correction as +deg. The model that uses both designs denoted as + singg, deg. Table B.. 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 + gn 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, tsign, 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
(1+p) homophily 7 is high and error rate e/ is low, lim (1 (1=22))ot(1-pp))) 1, so using signed messages is less beneficial in homophilous datasets.
B.2 BATCH NORM & LAYER NORM
In $ 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 ($ 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 & 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 significant accuracy drop in some datsets when 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 I. a GCN Kipf & Welling (2016) with weight bias, Elu non-linearity and residual connection. We do not include any of our designs so as exclude any other factors that can affect the performance. The models we compare against are +BN and + +IN, which represent the models that add batch norm and layer norm right before the non- non-linear activation, respectively.
Table B.2: Effects of using batch norm & layer norm: decrease in accuracy but improvement in oversmoothing. Best performance of each model across different layers is highlighted in gray.
Lavers
16
64
8
16
32
64
Cora (1 $1)
Citsseer
(b-0.44)
12.17
13.00a::
83.76at 63.73.100
63.9441
81.57a132
84.6311
85,17
7L62 71.58.3.6
72.18at.m
72, 42.45.1-4
72.7661
72
-LN
8477-141
186.721100 86.0841.0
85.0741.30
86.18e130
70l1aaa 74.02-227
75.00:1.45
74.000000
74.891200
78.94-243
Cornell (1w0).3
Chameleon (1=0.22))
Base
61.89
80.00ga or 58.022a na 16.4925 na 58.02as in
48.19g 10
64.88
02.43gr on 54.092 de 47 17.08amm
20.74g301
-2N
58.18.5.4
50.191459
55.41100s
$7.301:.15 57. $7.57.1.29
57. $7.022:61
00.81121
61.18-227 2.77
61.81:40
661.97131
59.04:377
57.8411147
18.1159.9 00.0840..
1883229 19.194a. 58.922s.
61 86806
02.17 02.41822
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, it requires sacrificing the nodes that benefit (case 3) compensate
21

---

Under review as a conference paper at ICLR 2022
for the nodes that prone moving towards the other classes (case & case 2). As 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 significant accuracy decrease (2%-3%) in the heterophilous datasets. +BN has a clear accuracy drop even in the homophilous datasets. As Thm. poitts 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.
B.3 MORE ON THE INITIAL & DEVELOPING STAGES
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. and in order to see both the initial and the developing stage, we need to use homophilous datasets. heterophilous datasets, most nodes satisfy case 1, so the initial stage does not exist.
Measurement of effective homophily Tt. To estimate the effective homophily Ti. we measure the portion of neighbors that have the same ground truth label as & and are correctly classified. Following theory, we estimate hi 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 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 is and compute ht. We note that we leverage the intermediate representations only for the estimation of h/; 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 dmar and dmiin respectively, and let Ω log, dmaz -log, dmnn Then,
Table B.3: Citeseer: Accuracy (Acc) and average effective ho- mophily (h() for nodes with different degrees across various layers. Last layer of initial stage marked in gray.
Degrees
Layers
11,
2]
[3,
77, 15
16,39
[40, 99
Acc
74.44
78.51
84.04
96.00
100.00
2
0.65 Ry
0.67
0.72
0.83
0.91
we divide the nodes into n intervals, where the j-th interval is defined as: [dmmn 1 dmmnn 2)2)
3 Acc
70.92
77.59
83.03
92.75
100.00
h!
0.63
0.66
0.71
0.84
0.92
Acc 60.54
68.56
77.63
94.00
100.00
Dataset: Citeseer. Figure 1 and Ta- B.3 how the accuracy changes with the number of layers for differ- ent node degree intervals. We observe that in the initial stage, the accuracy in-
Tr.
0.54
0.58
0.66
0.79
0.84
Acc
41.66
48.70
56.97
61.33
11.11
5
0.36
0.38
0.45
0.48
0.11
Ace 23.61
28.87
41.17
31.83
0.00
creases the degree and hi increase. However, in the developing stage, the accuracy of high-degree nodes drops more sharply than that of low-degree nodes.
h!
0.18
0.19
0.27
0.22
0.00
Dataset: Cora. The results for Cora are shown in Figure B.I and Table nodes with lower
B.4
In the initial stage, the
22

---

Under review as a conference paper at ICLR 2022
Table B.4: Cora: Accuracy and average effective
homophily (ht) for nodes with different degrees across different layers. Last layer of initial stage marked in gray.
Developing Stage
Initial Stage
Transitio
80
Accuracy
60
Degrees
Layers
[L:2]
[3.7]
[8. 21
[22, 60)
[61,
40
de (61 168
Avg R.
625
85.14
88.52
83.78
90.00
100.00
20
de [22, 60]
d: [8.21]
de [3,7]
values
0.26
Acc
R]
82:28
87.26
84.42
85.00
0.63
100.00
0.81
-d [1.2
0.77
0.78
0.73
0.64
0.84
0
2
3
4
5 Layers
6
7
8
Acc
79.57
85.52
83,26
85,00
100,00
X]
0.75
0.76
0.71
0.63
0.80
77.38
83.75
82.83
85.00
96.19
Figure B.1: Cora: Accuracy per (logarithmic) degree bin.
0.72
0.73
0.88
0.56
0.83
Apc
63.35
68.20
66.01
70.00
78.57
0.57
0.60
0.54
0.52
0-67
30.02
29.12
17.50
21.
X
0.23
Acc
31.48
31 01.002
28.44
32.50
26.24
0.24
0.26
0.20
0.28
0:24
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 RGद 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 theorems in
B.4 HOMOPHILY METRIC
In Table [ 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. To better align our empirical results with our theoretical analysis, we provide below proportion of nodes in each case.
Table B.5: The percentage (%) of nodes in each case (Fig. 2 and Thm. D case S
1-p" case
P
lu >
P 14o
& Fz S
(Tp))--p and case 3: otherwise. The dominant case for each dataset colored grey.
Texas
Wisconsin
Actor
Squirrel
Chameleon
Cornell
Citeseer
Pubmed
Cora
Hom. level h
0.11
0.21
0.22
0.22
0.23
0.3
0.74
0.8
0.81
#Nodes
183
251
7,600
5,201
2,277
183
3,327
19,717
2,708
#Edges
295
466
26,752
198.493
31,421
280
4,676
44,327
5,278
#Classes
Case 1
87, 43
78.49
63.49
47.74 74
48 18.48
79.23
18.33
14.80
6.50
Case 2
8.74
15.93
29.53
50.14
48.84
6.01
25.58
33.75
32.98
Case
3.83
5.58
6.90
2.11
2.68
14.75
56.09
51.45
60.52
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 is the dominant case. As we stated in Thm [ 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 [] In the Squirrel and Chameleon datasets, both case 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 [ Our way define homophily level does predict that GCN should perform decently in Squirrel and Chameleon datasets.
23

---

Under review as a conference paper at ICLR 2022
B.5 COMPLEXITY ANALYSIS
We first analyze the time complexity of the forward path GGCN, For degree correction, we need to compute the réj. However, do not need to compute all of them, and we only need to compute riy for node pairs who are linked. The time complexity is O(EE)), but it is a one-time computation, the results of which can be saved. We compute Ti based on the learned weights Xo. X1. The time complexity is O L). where L is the number of layers. The time complexity to compute the signed function is O[LE] H L), where H 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 O(V H L). Similarly, the time complexity of the multiplication of representation matrices and the weight matrices O(V) -2 H.) L... The total time complexity would be O (max (1V12, GGCN resembles the complexity of attention-basel model. Thus we compare with GAT (Veličkovid ct al.
L.. The complexity of
2017) the total time to train and test on larger homophilous and heterophilous datasets. We
the training and testing for 10 times.
Table B.6: Training and test time (m:minutes, s:seconds) for 10 runs. Shorter time is colored in grey.
Actor
Chameleon
Citeseer
Cora
Nodes 7,600
2,277
3,327
2,708
#Edges
26,752
31,421
4,676
5,278
GGCN
7m224s
2m229 7m334
2m9s 9m339s
5mn47s
GAT
8m114
4m11s
In general, GGCN runs faster than GAT because degree correction and signed messages in GGCN learn fewer parameters.
C HYPERPARAMETERS AND PARAMETERS
C.I HYPERPARAMETER SETTINGS
Experiments for Table & Table
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 RCN uses 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 7y: [0.0, 1.5]
Experiments for Table B.1 and Table B.2
The hyperparameters that 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, Ic-2]
Hidden units: (8, 16, 32, 64, 80)
24

---

Under review as a conference paper at ICLR 2022
C.2 INITIALIZATION PARAMETERS
Initialization
For GGCN, adopt the following parameter initialization in the experiments for Table T& Table
Initialization of 2 and 2f: 0.5 and 0, respectively
Initialization of a', 3/ 81 and B/: 2, O, 0, 0, respectively.
We initialize & 12. = 0 in Eq. (6) because, after applying softmax, (o....) = 1/3; this ensures equal contributions from positive and negative neighbors and themselves (and sum=1). We initialize X in Eq. (9) following the common practice for initializing the bias. We set a 2 and X/ 0.5 in Eq. (6) and Eq. (9), because when rij + +oo, the degree correction (including global scaling) is: a'ryy softplus(2) softplus(0.5 (0 1) 0) z 1. As we mention in Thm. 1, when the homophily level high, nodes with large 7; may benefit (case 3), thus we not want to compensate for these
nodes and would like to keep a'''' close to 1.
10
C.3 PARAMETERS AFTER TRAINING
Original Pre-training Poet-training
Figure C.T shows the original and corrected TG (avg riy). Corrected are given by a² "'y which are combination of global scaling and local degree correction. Because (0,112) sum to I and do not change global scaling, they are not considered in the corrected raj. As can be seen Fig. C.I. after the training, GGCN learns to increase Tij. which satisfies our theorems.
5
Cora
Citeseer
Cornell Chameleon
Figure C.I: Original Fej (avg. riy) and corrected (pre-
and post-training).
D TABLE 2 WITH LARGER FONTS
25

---

Under review as a conference paper at ICLR 2022
Table D.1: Model performance for different layers: mean accuracy + stdlv over diffcrent data splits. Per datasct and GNN model, we also report the layer at which the best performance (given Table 1 achieved. 'OOM': of memory: 'INS': numerical instability.
Best
10
2
1
32
2
4
2
2
2
2
76.65
74.11=165
77. 17.1
23 03.82=600 64
7-23 10
70 1.06
60
55 25.99-2.22
46,5 10.2723332
19. 19.58+1.77 1.78
35. 35.50 08
64
00M
24.73
INS
00M
INS
36.
32
76.9721.
74.97=144
0OM
77-3321.4
27.21=10.00 96
T,23
25.3+1.77
INS
70.29=1.0
35 42.4229
0OM
56 06.97111.81
46.78 46.7822.20
19. 10.58+177
05.20 3.20
INS
35.2
Chameleon (1=0.23)
Citeseer (h=0,74)
70.8821.50
76.00
76.96G21.5
30.71=1500
7-23L0
23.07+2.06
10.41=1.22
30.58
20.20
46.3822-23
19.58+1.75
35.39
16
OOM
INS
00M
INS
60
50
$1.00 1.00
77.09=1.6.
1.62
74.10s1.8 1.
70.00=1.4
72.32=1.00
7.23 10
24.18=171
06.37
70. 10.33=1.770
41.16
62 10.10
54.1 14.1222.21
19.58-177
35.15
35. 35.09933.55
00M
76.31
66.37
19.58
72
35.
76.77 de
77.05 48
76.00 76.00 1.
25.2021.00
72.62$199
23-0111
6M.33
73.33
69 00.5842.00
45. 15.7213 08
10.11122.1
63 63.86
59.01 80
19. 19.17+1.00 m8
53. 53.11
48.71
06
73.33
75
16.83 a2
77.13=16 aT
76. 76.90 80
75 11.4221.76
73. 11
78 11
76.50=1.55
76.55
23
70.77=1
46.58
59.06=1.8
61 61.07=4..
62. 02.7422.2
60 00)00--.81
64. 64.82
60. 00.26:2.66
50
2
Best
32
4
64
16
32
2
64
87.2821.4
87.32+1.2
121
00M
28.37+1.25
31.3933.00
13.9811.48
INS
1.332=5.00
70.0013.77
0OM
73.7844.37
58.9213-15
12.97-2.03
28.9213:15
INS
58.92
31
87.0521.00
87.18 1.20
.7.95 122
11.3248.22
18.0811448
N0.7643348
83. 55.7846.11
75. 43.4133.47
08.9213311
12.07+2.11
58.02 08.0213335
32
0OM
INS
0OM
INS.
87.
17
87 1.
87. 12
2.
13 13.0811449
31 1..55.2..00
83 68.7846778
3816600
84
05.3813.01
12.97+2.11
38.9213.15
16
Cora (h=0.81)
00M
INS
Cornell (A=0.3)
00M
58.381.5
INI
77.
58.0
87 87.6321.33
87.87
86 2.11
00.38
84 34.65+1.00
13.9811.44
31 31.03+3..00
84.9711.34
1864 69
11
8.
73.24
58 35.3815.01
12.97 (2.97+2.01
13.9219111
19.38+3..5
86
80
58
58
47.88
87.95 17.95=1.18
86. 10
21.35
85 10.07=0..0.
12.01
83 21-
36.30
83 78
77. 17.77=7.0
82. 20
64. 20.00
53 28-5128800
23.78+11.64
59.19
58. 28.38=4.06
0.05
87
21
86
87.0 17.00
87 1.111
87 1..20
11
85 10
85 1157
86 18.
87 37.0011.1
83 78
76. 76
67 11.3331
50. 27.17
60. 51-6677
60 5..0
61 -9.8955005
81
Layers
GGCN (ours)
Geom- GCN'
GGCN (ours)
Geeom Gion-GGN* GCC*
GPRGNN
H2GCN
GONTT
PairNorm
GPRGNN
H2GCN
GCNIT
PainNorm
GCN
GAT
GCN
GAT
26


Reviews:
[{"review_id": "ifErN7Z2rcl", "reviewer": "Reviewer_ehjS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "(+)\n\n- I really like the study of the authors, the approach in terms of degree and homophily level, the analysis in terms of separability is interesting. And the suggested mechanisms seem to be useful.\n\n- The appendix is detailed and provides a lot of additional information and insights.\n\n(-)\n\n- The paper is there to present the work and should be self-contained. However, below the theorems, it just says \"proof in appendix\". Even if the authors do not think it is necessary that the readers get an idea why the proposals are valid, an intuition should be given, at least in the appendix. \n\n- The authors mention the related works from Bo et al. and Chien et al. which also apply signed messages. Although the theoretical setting is slightly different in this paper, the novelty of the proposed solution is limited.\n\n- A closely related recent work is not mentioned/discussed in the paper:\nLim et al. Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods, NeurIPS 2021\n\n(other)\nOversmoothing is particularly a problem in dense graphs, e.g., DDI data. I wonder if the authors have any insights (from other experiments or similar) that the theory about the nodes with varying degree holds also for such data sets.\n", "summary_of_the_paper": "The paper analyses the GNN over-smoothing problem in terms of node degree and homophily level, suggests two correction mechanisms, and empirically shows that they help in various experiments.\n", "summary_of_the_review": "This approach to study this topic definitely deserves the attention of the community. The paper is overall well-written. I do not recommend full acceptance at the current point because I think it is not fair scientific practice to omit recent and very closely related work altogether.\n\n[Note] I reviewed the paper before. While the previous version of the paper was basically the same in the technical and experimental contents, the presentation was lacking clarity a lot. Great parts have been rewritten now, and I appreciate the efforts of the authors in addressing these issues. Since there was already a lot of discussion of various aspects of the approach, I only have few comments above. I am fairly confident about the paper itself, but I did not verify the proofs in the appendix in more detail.\n\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": "Not applicable"}, "extra_text": {}}, {"review_id": "dkS4HhHm8T4", "reviewer": "Reviewer_nAQJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "In this paper, the authors attempt to theoretically unify the cause of oversmoothing and heterophily. Specifically, the authors prove that under their proposed framework with certain assumptions, the level of homophily and relative degree may affect model performance. The authors further show the link between GNN performance and signed messages. Based on the analysis results, the authors propose a GCN model named GGCN by utilizing signed messages and degree corrections along with decaying aggregation. The effectiveness of the proposed model is validated by several experiments using real-world datasets of different statistics. In general, the paper is structured well and easy to follow. However, there are several issues the authors need to address.\n\nFirst, it would be better if the authors can further justify the novelty of the proposed approach, especially the modeling part. Both signed messages and degree corrections have been adopted to improve GNN performance and to solve a similar or the same problem (e.g., heterophily). I suggest the authors to further justify why this approach can be considered novel rather than combining several existing methods that focus on the same problem.\n\nI also have two questions for the evaluation: 1) It is good to see that GGCN performs well on heterophilous datasets. However, I suggest the authors to further discuss the potential reasons why GGCN performs worse than several baselines given that the analysis in Sec. 3 does not show the signed messages and degree corrections may hurt model performance on homophilous graphs. 2) The ablation study results in Table B.1 seem to be not aligned with the results in Table 2. When the number of layer increases, GGCN's performance seems to be stable in Table 1 but all the variants seem to decay much in Table B.1. I suggest the authors to further explain the difference between these results.\n\nThe signed messages require to compute pair-wise cosine similarities on node embeddings. It would be better if the authors can append a scalability analysis to compare GGCN with baselines on training/inference efficiency.", "summary_of_the_paper": "In this paper, the authors attempt to theoretically unify the cause of oversmoothing and heterophily, propose a generalized GCN model named GGCN by using signed messages and degree corrections along with decaying aggregation, and conduct several experiments to validate the performance of the proposed method.", "summary_of_the_review": "Strength:\n+ Comprehensive summary on existing literature\n+ Good paper structure\n\nWeakness:\n- Novelty needs to be justified\n- Evaluation results need to be further discussed\n- Missing scalability analysis", "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": "OPR8d8EAup", "reviewer": "Reviewer_osW7", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "Strengths:\n 1. The attempt to develop a theory to simultaneously address heterophily and oversmoothing issues in graph neural networks is important.\n 2. Evaluation  shows that the proposed GGCN shows some promising results.\n\nWeaknesses and Concerns:\n\n - Theoretical analysis is based on first on the vanilla linear GCN model, i.e., SCN of (Wu et al 2019), which removes non-linear activations. This makes analysis of GCNs trivial. For example, with the linear GCN model, the statement in Lemma 1 is trivially true.\n\n  - In addition, the graph generation process is also greatly simplified, assuming each node generates \"links\" uniform-randomly to nodes within the same class vs. nodes of the different class, independently of the choices made by, say, neighboring nodes.\n\n - Despite these simplifying assumptions (which are Okay to make the problems trackable in order to obtain rigorous theoretical results), I find that the theoretical developments are rather sloppy, and I have difficulty in following the theoretical derivations and proofs. All in all, the paper lacks rigor as I would have liked to see in a \"theory\"-oriented paper.\n\n\n  For example, in the proof of Lemma 1, you go from eq.(13) to eq(14), but never explain what $\\mathbf{x}$ is? Is $\\mathbf{x}$ simply $\\mathbf{f}_{i}^{L}$?   \nOr does it refer to the input (node features)?  I assume it is the latter, as in Lemma 2, you seem to use $\\mathbf{x}$ to denote the input. In any case, if it is the latter,  you have NOT established it yet (without accumulating all the weight matrices $\\\\mathbf{w}$ in the lower layers.  \n\n - The authors use the term \"movements\" in the latent space rather loosely, I have no ideas what it means precisely. In Lemma 2, it seems that you meant by the shifting the decision boundary.\n\n As an example, take the proof of Lemma 2. First of all, by stating that the representation of class 1 becomes: $\\{\\mathbf{f}^{(L)}_{i} - t {\\mathbf{w}}^{*T}\\}$, you seem to assume that only one hyperplane has shifted, as t ${\\mathbf{w}}^{*T}$ represents only a single hyperplane. This is in general NOT true.  Why do you need to\"overload\"  $f_1(x)$ and $f_2(x)$? This seems to create confusion. In fact, I am not sure what the first equation in eq(15) represents, in particular, what $w'$ and $b'$ represent, since they are never explained. What is the relation between eq.(15) and eq.(16)?\n\n  I am not sure wherer eq.(17) comes from.  \n\n Likewise in the proofs of Theorem 1 and Theorem 2, you start taking expectations without even properly defining the random variables and distributions over which you are taking expectations. Specifically, in the proof of Theorem 2,  when you start considering the higher layers $l$, you take the expectations based only on $k_i$ -- here you completely ignore the fact that once you move to higher layers where the aggregation of  \"messages\" from neighboring nodes would  introduce dependence on the inputs of the neighboring nodes.\n\n- There are a lot of issues similar to what I have pointed out here. It really makes following the proofs difficult. I have NO confidence in the theoretical results obtained in the paper.\n\n - In terms of the GGCN model, having \"negative\" message passing to deal with heterophily seems rather straightforward -- ideally, if the model is designed properly,  this \"negativity should follow directly from the model (if one assumes  \"+\" captures similarity, and \"-\" captures \"dissimilar\", as in signed networks); I suspect that the (relative) \"low\" degree claim is mostly due to the simplistic graph generation process used in the paper where node links are generated independently of other nodes.\n\n", "summary_of_the_paper": "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.", "summary_of_the_review": "The papers attempts to develop a theory to simultaneously address heterophily and oversmoothing issues in graph neural networks, which is a plus. However, despite making many simplifying assumptions, the \"theoretical\" developments are sloppy and hard to follow. As such, I have NOT confidence on the theoretical results obtained in the paper. I have NO confidence in the theoretical results obtained in the paper.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "36saRQtKJc", "reviewer": "Reviewer_1EPP", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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- The idea of finding the common causes of the two problems instead of simply releasing them separately is very enlightening. It is a good starting point for tackling these two problems from a theoretical perspective.\n- Theoretical analysis is provided and it is technically sound.\n- This paper justifies the introduction of the signed messages in solving these two problems in a more general setting.\n\nWeakness:\n- Theorems are based on probably many assumptions.\n- The theorems fail to prove that the relative degree would affect the misclassification rate. On one hand, in theorem 1, high-homophily nodes with a relatively low degree will move toward the original boundary and the opposite class in the shallow layers. However, based on this theorem, they will not flip the labels because the parameters will never be negative. On the other hand, the effective homophily of the nodes is actually the only factor in theorem 2. The proof of Theorem 2 in appendix A.4 actually verifies that the relative degree has no effect in this process.\n- In this paper, high/low homophily/heterophily are defined by comparing the node's homophily level with the homophily level of the whole graph. When we discuss the heterophily problem faced by the GCNs, we are mostly talking about the heterophily level of the graph. Unluckily, the homophily level defined in this paper cannot be translated into the homophily level of the graph. That is to say, a graph with an average homophily level higher than 0.5 doesn't guarantee that it has more nodes with a homophily level higher than the average. At the same time, the empirical experiments are conducted on a collective level (performance on the whole graph on average) instead of on each node. I have to say the theory and the experiment are not well combined.\n", "summary_of_the_paper": "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. \n\nThe contributions of this paper are as follows: \n1) it attempts to establish a connection between heterophily and over-smoothing by identifying common causes; \n2) it establishes that the relative degree and homophily level have an effect on the misclassification rate; and \n3) 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.", "summary_of_the_review": "Overall, I recommend rejecting this paper. It is actually exciting to see a paper that tries to link the two widely existing problems of GCNs together theoretically. However, although the theorems presented in the paper are actually correct, they don't support the conclusion that the authors claim.\n\nAfter reading the other reviews, I would choose to maintain my opinion, and the lack of innovation is my primary concern.", "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: This paper focuses on investigating the relations between the heterophily and over-smoothness problem. However, the relationship is not clear.

The over-smoothness problem considers the features and the adjacency matrix, while the heterophily incorporates the adjacency matrix and the labels. They have different views on the graph. It may not be treated as the same coin. Besides, the stacked aggregations lead to indistinguishable node representations and poor performance in the over-smoothing problem. The same phenomenon appears in the heterophily problem because the features in different classes are falsely mixed, leading to indistinguishable nodes [2]. They have the same phenomenon but different origins. It may be not a necessity to combine these two problems.

Besides, MADGap[1] is proposed to evaluate the over-smoothness problem. It is unreliable to use the accuracy and the degree to measure this problem. Therefore, in section 3, the relations between node degrees and the homophily ratio cannot infer the relations between the heterophily and over-smoothness problem.

As a result, the authors should carefully re-organize their paper and results. 

A suggestion is to pack the submission as a new method to learn from heterophily instead of trying to make such a close relationship with over-smoothing.

- [1] Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View. AAAI 2020
- [2] Beyond homophily in graph neural networks: Current limitations and effective designs. NeurIPS 2020
Decision: Reject