# 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 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.

1 INTRODUCTION

In recent years, GCNs (Defferrard et al., 2016; Kipf & Welling, 2016; Veliˇckovi´c et al., 2017)
have been widely used in applications ranging from social science (Li & Goldwasser, 2019) and
biology (Yan et al., 2019) to program understanding (Allamanis et al., 2018; Shi et al., 2019). A
typical GCN architecture (Gilmer et al., 2017) for the node classification task can be decomposed
into two main components: propagation/aggregation, and combination. Messages are first exchanged
between neighboring nodes, then aggregated. Afterwards, the messages are combined with the
self-representations (a.k.a., the current node representations) to update the node representations.
Though GCNs are effective, they have some key limitations.

The first limitation is the “oversmoothing" problem (Li et al., 2018): the performance of GCNs
degrade when stacking many layers. Recent work has found that oversmoothing could be caused by
GCNs exponentially losing expressive power in the node classification task (Oono & Suzuki, 2019)
and that the node representations converge to a stationary state which is decided by the degree of the
nodes and the input features (Chen et al., 2020; Wang et al., 2019; Rong et al., 2019; Rossi et al.,
2020). These works focus on the analysis of the steady state in the limit of infinite layers, but they do
not explore the dynamics on how oversmoothing is triggered, or which nodes tend to cause it. Other
works like (Xu et al., 2018; Wang et al., 2019; Chen et al., 2020) focus on heuristic-based model
designs to alleviate the oversmoothing problem. To fill this gap, we seek to theoretically analyze the
dynamics around oversmoothing. In our empirical analysis, by dividing the nodes in real graphs into


-----

several degree groups and tracking their average accuracy while increasing the layers of GCN (Kipf
& Welling, 2016), we observe two phases (Fig. 1): the initial stage when higher-degree nodes have
higher accuracy and the developing stage when the accuracy of higher-degree nodes decreases more
sharply (cf. § 5.4 for details). As we will show theoretically and empirically, the low-degree nodes
are the ones that trigger oversmoothing. Though Chen et al. (2020) provide some explanations for the
developing stage by analyzing the convergence rate, their theory fails to characterize the initial stage.
In fact, we find that the analysis of initial stage provides valuable insights about oversmoothing.

The second limitation of GCNs is their poor performance on heterophilous graphs (Pei et al.,
2019; Lim et al., 2021), which—unlike homophilous graphs—have many neighboring
nodes that belong to different classes (Newman,
2002). For instance, in protein networks, amino
acids of different types tend to form links (Zhu
et al., 2020), and in transaction networks, fraudsters are more likely to connect to accomplices
than to other fraudsters (Pandit et al., 2007). Most Figure 1: Accuracy of nodes grouped by degree di
GCNs (Kipf & Welling, 2016; Veliˇckovi´c et al., on Citeseer. Initial stage: when mean effective ho2017) fail to effectively capture heterophily, so mophily _h[l]i_ [(ratio of a node’s neighbors in the same]
emerging works have proposed some effective class–§ 3.3.2) is high, the accuracy increases as the
designs (Pei et al., 2019; Zhu et al., 2020), in- degree increases. Developing stage: when[b] _h[l]i_ [is low,]
cluding signed messages (positive and negative the accuracy of high-degree nodes drops more sharply.
interactions between nodes) proposed by concur
[b]

rent works (Chien et al., 2021; Bo et al., 2021). Though these works justify signed messages from a
spectral perspective, they focus on asymptotic results, requiring an infinite number of filters. Our
work does not make this assumption, and our theory works in more practical scenarios (§ 3.4).

These two limitations have mostly been studied independently, but recent work on oversmoothing (Chen et al., 2020) was shown empirically to address heterophily, and vice versa (Chien et al.,
2021). Motivated by this empirical observation, we set out to understand the theoretical connection
between the oversmoothing and heterophily problems by studying the change in node representations
during message passing. Specifically, we make the following contributions:

-  Theory: We introduce the first theory that explains the connections between heterophily and

oversmoothing which opens up the possibility of jointly studying the two problems.

-  Insights: We find that under conditions, the relative degree of a node (compared to its neighbors)
and its heterophily level affect the misclassification rate of node labels in the oversmoothing and
heterophily problems. We further prove that signed messages can mitigate their negative impact.

-  Improved model & empirical analysis: Based on these insights, we design a generalized GCN
model, GGCN, that allows negative interactions between nodes and compensates for the effect of
low-degree nodes through a learned rescaling scheme. Our empirical results show that our model
is robust to oversmoothing, achieves state-of-the-art performance on datasets with high levels of
heterophily, and achieves competitive performance on homophilous datasets.

2 PRELIMINARIES

We first provide the notations & definitions that we use in the paper, and a brief background on GCNs.

**Notation. We denote an unweighted and self-loop-free graph as G (V, E) and its adjacency matrix as**
**A. We represent the degree of node vi** by di, and the degree matrix—which is a diagonal matrix
whose elements are node degrees—by ∈V D. Let Ni be the set of nodes directly connected to vi, i.e., its
neighbors. I is the identity matrix. We denote the node representations at l-th layer as F[(][l][)], and the
_i-th row of F is fi[(][l][)][, which is the representation of node][ v][i][. The input node features are given by]_
**F[(0)]. The weight matrix and bias vector at the l-th layer are denoted as W[(][l][)]** and b[(][l][)], respectively.

**Homophily and Heterophily. Given a set of node labels/classes, homophily captures the tendency**
of a node to have the same class as its neighbors. Specifically, the homophily of node vi is defined
_i[s]_
as hi E _|N_ _i_ _[|]_, where _i[s]_ [is the set of neighboring nodes with the same label as][ v][i][,][ | · |][ is the]
_≡_ _|N_ _|_ _N_

cardinality operator, and the expectation is taken over the randomness of the node labels. High 
homophily corresponds to low heterophily, and vice versa, so we use these terms interchangeably.


-----

**Supervised Node Classification Task. We focus on node classification: given a subset of labeled**
nodes (from a label set ), the goal is to learn a mapping F : fi[(0)] _yi between each node vi_
_L_ _7→_
and its ground truth labelmisclassification rate of a fixed learnt model over a node set yi ∈L. We use ˆyi to represent the predicted label of V as: E _|{vi| ˆyi v≠_ _|V|yii and define the,vi∈V}|_ . The

expectation is taken over the randomness of graph structures and input node features. 

**Graph Convolutional Neural Networks.** In node classification tasks, an L-layer GCN contains two components (Gilmer et al., 2017): (1) neighborhood propagation and aggrega
tion: **fi[(][l][)]** = AGGREGATE(fj[(][l][)][,][ v][j] _∈_ _Ni), and (2) combination:_ **fi[(][l][+1)]** = COMBINE(fi[(][l][)][,]

**fLi[(][l]CE[)][), where]=CrossEntropyc** [ AGGREGATE](Softmax[ and][ COMBINE](fi[(][L][)]W[(][L][ are learnable functions.][)] + b[(][L][)]), yi). The vanilla GCN suggests a renor-The loss is given by[c]
malization trick on the adjacency A to prevent gradient explosion (Kipf & Welling, 2016). The
(l + 1)-th output is given by: F[(][l][+1)] = σ( AF[˜] [(][l][)]W[(][l][)]), where **A[˜]** = D[˜] _[−][1][/][2](I + A) D[˜]_ _[−][1][/][2],_ **D[˜]** is the
degree matrix of I + A, and σ is ReLU. When the non-linearities in the vanilla GCN are removed,
it reduces to a linear model called SGC (Wu et al., 2019), which has competitive performance and
is widely used in theoretical analyses (Oono & Suzuki, 2019; Chen et al., 2020). For SGC, the l-th
layer representations are given by: F[(][l][)] = A[˜] _[l]F[(0)]_ and the last layer is a logistic-regression layer:
_yˆi = Softmax(F[(][L][)]W[(][L][)]_ + b[(][L][)]). We note that only one weight matrix W[(][L][)] is learned; it is
equivalent to the products of all weight matrices in a linear GCN. Find more related works in § 6.

3 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 to the misclassification
rate of node labels; and (2) we identify the factors that affect the movements of representations. We
use the SGC model to analyze binary node classification with nodes in class 1 denoted as set V1 and
nodes in class 2 denoted as set 2. We show empirically (§ 5) that the insights obtained in this section
_V_
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) is a permutation-invariant function p(x1, . . ., xn) =
_p(P(x1, . . ., xn)), where P(·) means permutation._

**(1) Random graph: Node degrees {di} are i.d. random variables. {(·)i} represents a set with**
_i = 1, . . ., |V|. (2) Inputs: (2.1) Node labels {yi} are i.d. Bernoulli random variables given by the_
ratio ρ: ρ ≡ P[P]([(]y[y]i[i]=2)[=1)] _[,][ ∀][i][. (2.2) Initial input node features][ {][f][ (0)]i_ _} are i.d. random vectors given by (PDF)_

_f1(x),_ when yi = 1. **_µ,_** when yi = 1.
_f_ (x), which is expressed as: f (x) = _f2(x),_ when yi = 2. [E][(][f][ (0)]i _|yi) =_ _ρµ,_ when yi = 2.
 −

so E(fi[(0)]) = 0. (3) Independence: _di_ are independent of _yi_ and **fi[(0)]** .
_{_ _}_ _{_ _}_ _{_ _}_

3.2 MISCLASSIFICATION RATE & MOVEMENTS OF NODE REPRESENTATIONS
The following lemmas illustrate why the movements of node representations are a good indicator
of SGC’s performance. We view the changes of node representations across the layers as their
movements; i.e., fi[(][l][+1)] is moved from fi[(][l][)][,][ ∀][i][.][ The misclassification rate of an][ L][-layer SGC is]
determined by **fi[(][L][)]**, which is the input to the last regression layer, and can be studied through the
_{_ _}_
decision boundary of fi[(][L][)].

**Lemma 1 In SGC, the decision boundaries w.r.t.** **fi[(][L][)]** in multi-class classification are linear
_{_ _}_
hyperplanes. In particular, the decision boundary is a single hyperplane for binary classification.
_Proof. We provide the proof in App. A.1._
The decision boundary of an (L + 1)-layer SGC can be viewed as a perturbation to the decision
boundary of an L-layer SGC due to the movements from **fi[(][L][)]** to **fi[(][L][+1)]** . Due to Lemma 1,
_{_ _}_ _{_ _}_
we can use the hyperplane xw + b = 0 to represent the decision boundary of **fi[(][L][)]**, where w
_{_ _}_
is a unit vector, b is a scalar, and the **fi[(][L][)]** are classified to class 1 if fi[(][L][)]w + b > 0. Suppose
_{_ _}_
when w = w[∗] and b = b[∗], we find an optimal hyperplane xw[∗] + b[∗] = 0 that achieves the lowest


-----

Figure 2: Node representation dynamics during neighborhood aggregation (in 1D for illustration purposes; ‘MR’:
misclassification rate). The expectation of node representations from class 1 & 2 are denoted by µ and −µ,
respectively. The bars show the expected node representations of node vi before and after the aggregation.

total misclassification rate (§ 2) for **fi[(][L][)]** . Due to the movements of node representations, the new
_{_ _}_
optimal hyperplane is decided by: xw[∗′] + b[∗′] = 0. In Lemma 2, we show that, under constraints,
moving towards the original decision boundary with a non-zero step results in a non-decreasing total
misclassification rate under the new decision boundary.

**Lemma 2 Moving representations** **fi[(][L][)]** from class 1 by adding _tw[∗][T]_, t > 0, s.t. w[∗][T] **w[∗′]** _> 0,_
_{_ _}_ _−_
the new total misclassification rate is no less than the misclassification rate before the movements.
_Proof. We provide the proof in App. A.2._

Note that the special case where the representations of the two classes swap positions (e.g, bipartite
graphs) violates the condition w[∗][T] **w[∗′]** _> 0 and leads to different conclusions. We refer to the_
condition w[∗][T] **w[∗′]** _> 0 as "non-swapping condition" and throughout the paper, we analyze SGC_
under that. Lemma 2 shows that, under the "non-swapping condition", if **fi[(][l][)]**

original decision boundary (or the other class), SGC tends to perform worse. { _[}][ move towards the]_

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, di, of node vi and assume that vi 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 "non-swapping condition", during message passing in shallow**
_layers, the nodes with low homophily hi ≤_ 1+ρ _ρ_ _[and the nodes with high homophily][ h][i][ >]_ 1+ρ _ρ_ _[but]_

**_small relative degree are prone to be misclassified. Defining rij ≡_** _ddji+1+1_ _[and the relative degree]_

_ri ≡_ EA|di,vi∈V1 ( _d[1]i_ _j∈Ni_ _[r][ij][)][, the conditional expectation of representation]q_ **[ f][ (1)]i** _is given by:_

((1 + ρ)hi _ρ)diri + 1_
EA,{yi},{f (0)i _}|di,vi∈VP1_ [(][f][ (1)]i _|vi ∈V1, di) =_ _di − + 1_ E(fi[(0)]) ≡ _γi[1][E][(][f][ (0)]i_ ), (1)
 

_where the multiplicative factor γi[1]_ _[is:]_

( _,_ [1]2 []][,] _if hi_ 1+ρ _ρ_

_γi[1]_ (0−∞, 1], _if hi ≤ >_ 1+ρ _ρ_ [&][ r][i][ ≤] (1+ρ1)hi _ρ_ (2)

_[∈]_ _−_

(1, ), otherwise.

_∞_

_Proof. We provide the proof in App. A.3._

From Thm. 1, we identify three types of movements of node representations, which are characterized
by relative degree ri and homophily level hi. For illustration purposes, in Fig. 2, we illustrate the
three cases when we apply our theorem to 1D node representations. The bars reflect the value change
of vi’s node representation. Intuitively, under heterophily (case 1) or under high homophily but
low degrees (case 2), the expected representations will move heavily towards the opposing class.
Otherwise, they will move away from the opposing class (case 3). Among the three cases, only nodes
with high homophily and high relative degree benefit from propagation and aggregation.

**Explanation of the heterophily and oversmoothing problems:**

-  In heterophilous graphs, node representations move heavily towards the opposite class. According
to Lemma 2, under the "non-swapping" condition, it indicates higher misclassification rate (i.e.,
poorer performance) for SGC.

-  In homophilous graphs, high-degree nodes may initially benefit (case 3), leading to performance
gain in shallow layers. However, the representations of low-degree nodes tend to move towards the
opposing class (case 2) and eventually flip the labels. The misclassification of low-degree nodes
causes a pseudo-heterophily situation (case 1) later.


-----

3.3.2 DEVELOPING STAGE: DEEPER LAYERS
The following theorem analyzes the pseudo-heterophily scenario in deeper layers. Based on Thm. 1,
message passing will result in scaling the node representations (γi[1][) and some nodes may cross]
the origin. To account for those, let ξi[l] [be an accumulated discount factor at the][ l][-th layer and]

EA, _yi_ _,_ **f (0)i** _di_ _dfii[(]+1[l][)]_ _[|][d][i]_ = ξi[l][µ][. Conditioned on][ A][ and][ ξ]i[l][, the nodes contributing positively]
_{_ _}_ _{_ _}|_ _T_

are defined as: _Nˆi[s][(][A][, ξ]i[l][)][ ≡{][v][j][|][v][j][ ∈N][i][ and][ (][ξ]i[l][µ][)][ ·][ E]{yi},{fi[(0)]}|ξi[l][,][A]_ **fj[(][l][)]** _|ξil[,][ A]_ _> 0}. We_

 

denote: EA,{yi},{f (0)i _}|di,ξi[l][,v][j]_ _[∈N][i]_ **fj[(][l][)][r][ij][|][d][i][, ξ]i[l][, v][j][ ∈N][i]!** = (−ξi[l]ρ′µ[l]i[ξ]i[l]′µ _vvjj ̸∈ ∈_ _NN[ˆ][ˆ]ii[s][s][(][(][A][A][, ξ][, ξ]ii[l][l][)][)]_ [.][ ξ]i[l]′ and

_ρ[l]i_ [characterize the neighborhood property of][ v][i][. We further define the][ effective homophily][ of node][ i]
asthe perspective of message passing under this pseudo-heterophily scenario, the deeper layers will acth[ˆ][l]i [=][ P][(][v][j][ ∈] _N[ˆ]i[s][|][v][j][ ∈N][i][, d][i][, ξ]i[l][)][.][ Intiuitively, even if the original graph is not heterophilous, from]_
as if the graph is more heterophilous than it truly is, which may increase the misclassification rate.
**Theorem 2. [Developing Stage] Under the “non-swapping condition”, during message passing in**
_deeper layers, when the effective homophily_ _h[l]i_ _[is sufficiently][ low][ (][b]h[l]i_ _[≤]_ 1+ρ[l]iρ[l]i [)][, the nodes with][ higher]

_effective relative degree are prone to misclassification. Specifically, by defining the effective relative_
_degree as ¯ri[l]_ _≡_ _[ξ]ξi[l]i[l]′_ _[, the conditional expectation of][b]_ **[ f][ (]i** _[l][+1)]_ _is:_

( h[ˆ][l]i[(1 +][ ρ]i[l][)][ −] _[ρ][l]i[)][d][i][ ¯]ri[l]_ + 1

EA,{yi},{f (0)i _}|di,ξi[l][)]_ **fi[(][l][+1)]|di, ξi[l][)]!** =  _di + 1_  _ξi[l][µ][ ≡]_ _[γ]i[(][l][+1)]E(fi[(0)])._ (3)

_Proof. We provide the proof in App. A.4. Other nodes can be derived similarly._
We note that Eq. (3) holds for layers l ≥ 2 in general. We regard layers for which _h[l]i_ _[>]_ 1+ρ[l]iρ[l]i [holds]

for most nodes i as part of the initial stage, as they exhibit three cases similar to Eq. (2).

[b]

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 labels are not accessible for every node, so we
use approximations, which introduces errors. For node vi, we define m[l]i [as the][ ratio of neighbors]
_that send incorrect messages at the l-th layer (i.e., different-class neighbors that send non-negated_
messages and same-class neighbors that send negated messages). We define the l-th layer error rate
as e[l]i [=][ E][(][m]i[l][)][, where the expectation is over the randomness of the neighbors that send incorrect]
messages. We make the following assumption: m[l]i [is independent of][ {][d][i][}][,][ {][y][i][}][ and][ {][f][ 0]i _[}][.]_

**Theorem 3. [Signed Messages] With the independence assumptions and under the “non-swapping**
_condition”, by allowing the messages to be optionally multiplied by a negative sign, in the initial_
_stage, the movements of representations will be less affected by the initial homophily level hi, and_
_will be dependent on the error rate e[l]i[. Specifically, the multiplicative factor][ γ]i[1]_ _[at the first layer is:]_

(1 2e0i [)(][ρ][ + (1][ −] _[ρ][)][h][i][)][d][i][r][i][ + 1]_
EA,{yi},{f (0)i _}|di,vi∈V1_ [(][f][ (1)]i _|di, vi ∈V1) =_ _−_ _di + 1_ **_µ ≡_** _γi[1][E][(][f][ (0)]i_ ),
 

(4)

(−∞, [1]2 []][,] _if e[0]i_ _[≥]_ [0][.][5] 1

_where γi[1]_ _[∈]_ (0, 1], _if e[0]i_ _[<][ 0][.][5 &][ r][i][ ≤]_ (1−2e[0]i [)(][ρ][+(1][−][ρ][)][h][i][)] (5)

(1, ), 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 ( _γi[1]_ _[>][ 1][), the minimum]_

we get:relative degree satisfies:(1−2e[0]i [)(][ρ]1[+(1][−][ρ][)] r[h][i]i[)] >[ ≤] (1(1+−2ρe1)[0]ih[)(]i[ρ]−1[+(1]ρ [, and][−][ρ][)][h][i](1+[)] [. Given]ρ1)hi−ρ[ h][is the minimum relative degree required][i][ ≤] [1][, if the error rate is low (][e]i[0] _[≪]_ [0][.][5][),]

when not using signed messages. This implies that more nodes can benefit from using signed messages.
We note that if low error rate cannot be guaranteed, signed messages may hurt the performance.


-----

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 a decaying combination of the current and previous node representations (Chen et al., 2020), into a generalized GCN model, GGCN. In § 5, we empirically show its
effectiveness in addressing the two closely-related problems.

4.1 SIGNED MESSAGES
Thm 3 points out the importance of signed messages in tackling the heterophily and oversmoothing
problems. Our first proposed mechanism uses cosine similarity to send signed messages.

For expressiveness, as in GCN (Kipf & Welling, 2016), we first perform a learnable linear transformation of each node’s representation at the l-th layer: **F[(][l][)]** = F[(][l][)]W[(][l][)] + b[(][l][)] Then, we define a sign
function to be multiplied with the messages exchanged between neighbors. To allow for backpropagation of the gradient information, we approximate the sign function with cosine similarity. Denote S[l]

[d]

as the matrix which stores the sign information about the edges, defined as: S[(][l][)][i, j] =Cosine(fi[(][l][)][,]
**fj[(][l][)][) if (][i][ ̸][=][ j][) & (][v][j][ ∈N][i][); 0 otherwise.]**

In order to separate the contribution of similar neighbors (likely in the same class) from that of
dissimilar neighbors (unlikely to be in the same class), we split S[(][l][)] into a positive matrix S[(]pos[l][)] [and]
a negative matrix S[(]neg[l][)] [. Thus, our proposed GGCN model learns a weighted combination of the]
self-representations, the positive messages, and the negative messages:

**F[(][l][+1)]** = σ ˆα[l]( β[ˆ]0[l] **F[(][l][)]** + β[ˆ]1[l][(][S]pos[(][l][)] **A)F[d][(][l][)]+ β[ˆ]2[l](S[(]neg[l][)]** **A)F[d][(][l][)])** _,_ (6)

_[⊙]_ [˜] _[⊙]_ [˜]
where _β[ˆ]0[l]_ [,][ ˆ]β1[l] [and][ ˆ]β2[l] [are scalars obtained by applying softmax to the learned scalars]  _[ β]0[l]_ [,][ β]1[l] [and]
_β2[l]_ [; the non-negative scaling factor][ ˆ]α[d][l] = softplus(α[l]) is derived from the learned scalar α[l]; is
_⊙_
element-wise multiplication; and σ is the nonlinear function Elu. We note that we learn different
_α and β parameters per layer for flexibility. We also require the combined weights, ˆα[l][ ˆ]βx[l]_ [, 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 § 3.4 highlights that, when the error rate and homophily level are high,
oversmoothing is initially triggered by low-degree nodes. Thus, our second proposed mechanism
aims to compensate for low degrees via degree corrections.

Based on Eq. (5), and given that most well-trained graph models have a relatively low error rate
at the shallow layers (i.e, e[l]i
1 _[≪]_ [0][.][5][ for small][ l][), we require that the node degrees satisfy][ r][i][ >]

(1−2e[0]i [)(][π][+(1][−][π][)][h][i][)][ to prevent oversmoothing. Since the node degrees cannot be modified, our]

strategy is to rescale them. Specifically, we correct the degrees by multiplying with scalars τij[l] [and]
change the original formulation as follows:


_τi,j[l]_ **F[(][l][)][j, :]**

_√di + 1_ _dj + 1_ _._ (7)

[d]

(τij[l] _d[)][2]j[(]+1[d][i][+1)]p_ . That is, a larger


**F[(][l][)][i, :]** **F[(][l][)][j, :]**
( A[˜]F[d][(][l][)])[i, :] = =
ddi + 1 [+] _vjX∈Ni_ _√di + 1d_ _dj + 1_ _⇒_ _vjX∈Ni_

p

This multiplication is equivalent to changing the ratio rij in Thm. 1 to

r


_τij[l]_ [increases the effective][ r][i][ at layer][ l][. Training independent][ τ][ l]i,j [is not practical because it would]
require O(|V|[2]) additional parameters per layer, which can lead to overfitting. Moreover, low-rank
parameterizations suffer from unstable training dynamics. Intuitively, when rij is small, we would
like to compensate for it via a larger τi,j[l] [. Thus, we set][ τ][ l]i,j [to be a function of][ r][ij][ as follows:]

_τij[l]_ [=][ softplus] _λ[l]0_ _r1ij_ + λ[l]1 _,_ (8)

_[−]_ [1]

where λ[l]0 [and][ λ]1[l] [are learnable parameters. We subtract 1 so that when]    _[ r][ij]_ [= 1][ (i.e.,][ d][i] [=][ d][j][), then]
_τij[l]_ [=][ softplus][(][λ]1[l] [)][ is a constant bias.]

In our proposed GGCN model, we combine the signed messages in Eq. (6) and our degree correction
mechanism to obtain the representations at layer l + 1:

**F[(][l][+1)]** = σ _αˆ[l]_ ˆβ0[l] **F[(][l][)]** + β[ˆ]1[l] [(][ S]pos[(][l][)] _[⊙]_ **A[˜]** _⊙TTT_ [(][l][)] )F[d][(][l][)] + β[ˆ]2[l] [(][ S]neg[(][l][)] _[⊙]_ **A[˜]** _⊙TTT_ [(][l][)] )F[d][(][l][)] _,_ (9)
where TTT [(][l][)] is a matrix with elements  _τij[l]_ [.] []

[d]


-----

4.3 DECAYING AGGREGATION

In addition to our two proposed mechanisms that are theoretically grounded in our analysis (§ 3), we
also incorporate into GGCN an existing design—decaying aggregation of messages—that empirically
increases performance. However, we note that, even without this design, our GCN architecture still
performs well under heterophily and is robust to oversmoothing (App. §B.1).

Decaying aggregation was introduced in (Chen et al., 2020) as a way to slow down the convergence
rate of node representations. Inspired by this work, we modify the decaying function, ˆη, and integrate
it to our GGCN model:

**F[(][l][+1)]** = F[(][l][)] + ˆη _σ_ ˆα[l]( β[ˆ]0[l] **F[(][l][)]+ β[ˆ]1[l]** [(][S]pos[(][l][)] _[⊙]_ **A[˜]** _⊙TTT_ [(][l][)])F[d][(][l][)] + β[ˆ]2[l] [(][S]neg[(][l][)] _[⊙]_ **A[˜]** _⊙TTT_ [(][l][)])F[d][(][l][)]) _,_ (10)

  []

In practice, we found that the following decaying function works well:[d] ˆη ln( _l[η][k][ +1)][,][ iff][ l][ ≥]_ _[l][0][; ˆ]η =_
_≡_

1, otherwise. The hyperparameters k, l0, η 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., 2018). We provide their summary
statistics in Table 1, where we compute the homophily level h of a graph as the average of hi of all
nodes vi . For all benchmarks, we use the feature vectors, class labels, and 10 random splits
(48%/32%/20% of nodes per class for train/validation/test ∈V [1]) from (Pei et al., 2019).
**Baselines. For baselines we use (1) classic GNN models for node classification: vanilla GCN (Kipf**
& Welling, 2016), GAT (Veliˇckovi´c et al., 2017) and GraphSage (Hamilton et al., 2017); (2) recent models tackling heterophily: Geom-GCN (Pei et al., 2019), H2GCN (Zhu et al., 2020) and
GPRGNN (Chien et al., 2021); (3) models tackling oversmoothing: PairNorm (Zhao & Akoglu,
2019) and GCNII (Chen et al., 2020) (state-of-the-art); and (4) 2-layer MLP (with dropout and Elu
non-linearity). For GCN, PairNorm, Geom-GCN, GCNII, H2GCN and GPRGNN, we use the original
codes provided by the authors. For GAT, we use the code from a well-accepted Github repository[2].
For GraphSage, we report the results from (Zhu et al., 2020), which uses the same data and splits. For
the baselines that have multiple variants (Geom-GCN, GCNII, H2GCN), we choose the best variant
for each dataset and denote them as [model]*. For each dataset and baseline, if applicable, we use the
best hyperparameters provided by the authors. Otherwise, we perform parameter search to set the
best hyperparameters for each baseline. The setting and analysis of hyperparameters are in App. § C.
**Machine. We ran our experiments on Nvidia V100 GPU.**
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 “[†]” results (GraphSAGE)
are obtained from (Zhu et al., 2020).

**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** 5 5 5 5 5 5 7 3 6 **Avg Rank**


GGCN (ours) 84.86±4.55 86.86±3.29 37.54±1.56 55.17±1.58 71.14±1.84 85.68±6.63 77.14±1.45 89.15±0.37 87.95±1.05 1.78
GPRGNN 78.38±4.36 82.94±4.21 34.63±1.22 31.61±1.24 46.58±1.71 80.27±8.11 77.13±1.67 87.54±0.38 87.95±1.18 5.56
H2GCN* 84.86±7.23 87.65±4.98 35.70±1.00 36.48±1.86 60.11±2.15 82.70±5.28 77.11±1.57 89.49±0.38 87.87±1.20 3.89
GCNII* 77.57±3.83 80.39±3.4 37.44±1.30 38.47±1.58 63.86±3.04 77.86±3.79 77.33±1.48 90.15±0.43 88.37±1.25 3.56
Geom-GCN* 66.76±2.72 64.51±3.66 31.59±1.15 38.15±0.92 60.00±2.81 60.54±3.67 78.02±1.15 89.95±0.47 85.35±1.57 6.11
PairNorm 60.27±4.34 48.43±6.14 27.40±1.24 50.44±2.04 62.74±2.82 58.92±3.15 73.59±1.47 87.53±0.44 85.79±1.01 7.78
GraphSAGE[†] 82.43±6.14 81.18±5.56 34.23±0.99 41.61±0.74 58.73±1.68 75.95±5.01 76.04±1.30 88.45±0.50 86.90±1.04 5.78
GCN 55.14±5.16 51.76±3.06 27.32±1.10 53.43±2.01 64.82±2.24 60.54±5.3 76.50±1.36 88.42±0.5 86.98±1.27 6.56
GAT 52.16±6.63 49.41±4.09 27.44±0.89 40.72±1.55 60.26±2.5 61.89±5.05 76.55±1.23 86.33±0.48 87.30±1.10 7.22
MLP 80.81±4.75 85.29±3.31 36.53±0.70 28.77±1.56 46.21±2.99 81.89±6.40 74.02±1.90 87.16±0.37 75.69±2.00 6.78

1(Pei et al., 2019) claims that the ratios are 60%/20%/20%, which is different from the actual data splits
shared on GitHub.
2https://github.com/Diego999/pyGAT


-----

Table 2: Model performance for different layers: mean accuracy ± stdev over different data splits. Per dataset
and GNN model, we also report the layer at which the best performance (given in Table 1) is achieved. ‘OOM’:
out of memory; ‘INS’: numerical instability. For larger font, refer to Table D.1 in the Appendix.

**Layers** **2** **4** **8** **16** **32** **64** **Best** **2** **4** **8** **16** **32** **64** **Best**

**Cora (h=0.81)** **Citeseer (h=0.74)**

GGCN (ours) 87.00±1.15 87.48±1.32 87.63±1.33 87.51±1.19 87.95±1.05 87.28±1.41 32 76.83±1.82 76.77±1.48 76.91±1.56 76.88±1.56 76.97±1.52 76.65±1.38 10
GPRGNN 87.93±1.11 87.95±1.18 87.87±1.41 87.26±1.51 87.18±1.29 87.32±1.21 4 77.13±1.67 77.05±1.43 77.09±1.62 76.00±1.64 74.97±1.47 74.41±1.65 2
H2GCN* 87.87±1.20 86.10±1.51 86.18±2.10 OOM OOM OOM 2 76.90±1.80 76.09±1.54 74.10±1.83 OOM OOM OOM 1
GCNII* 85.35±1.56 85.35±1.48 86.38±0.98 87.12±1.11 87.95±1.23 88.37±1.25 64 75.42±1.78 75.29±1.90 76.00±1.66 76.96±1.38 77.33±1.48 77.18±1.47 32
PairNorm 85.79±1.01 85.07±0.91 84.65±1.09 82.21±2.84 60.32±8.28 44.39±5.60 2 73.59±1.47 72.62±1.97 72.32±1.58 59.71±15.97 27.21±10.95 23.82±6.64 2
Geom-GCN* 85.35±1.57 21.01±2.61 13.98±1.48 13.98±1.48 13.98±1.48 13.98±1.48 2 78.02±1.15 23.01±1.95 7.23±0.87 7.23±0.87 7.23±0.87 7.23±0.87 2
GCN 86.98±1.27 83.24±1.56 31.03±3.08 31.05±2.36 30.76±3.43 31.89±2.08 2 76.50±1.36 64.33±8.27 24.18±1.71 23.07±2.95 25.3±1.77 24.73±1.66 2
GAT 87.30±1.10 86.50±1.20 84.97±1.24 INS INS INS 2 76.55±1.23 75.33±1.39 66.57±5.08 INS INS INS 2


**Cornell (h=0.3)** **Chameleon (h=0.23)**

GGCN (ours) 83.78±6.73 83.78±6.16 84.86±5.69 83.78±6.73 83.78±6.51 84.32±5.90 6 70.77±1.42 69.58±2.68 70.33±1.70 70.44±1.82 70.29±1.62 70.20±1.95 5
GPRGNN 76.76±8.22 77.57±7.46 80.27±8.11 78.38±6.04 74.59±7.66 70.00±5.73 8 46.58±1.771 45.72±3.45 41.16±5.79 39.58±7.85 35.42±8.52 36.38±2.40 2
H2GCN* 81.89±5.98 82.70±6.27 80.27±6.63 OOM OOM OOM 1 59.06±1.85 60.11±2.15 OOM OOM OOM OOM 4
GCNII* 67.57±11.34 64.59±9.63 73.24±5.91 77.84±3.97 75.41±5.47 73.78±4.37 16 61.07±4.10 63.86±3.04 62.89±1.18 60.20±2.10 56.97±1.81 55.99±2.27 4
PairNorm 50.27±7.17 53.51±8.00 58.38±5.01 58.38±3.01 58.92±3.15 58.92±3.15 32 62.74±2.82 59.01±2.80 54.12±2.24 46.38±2.23 46.78±2.26 46.27±3.24 2
Geom-GCN* 60.54±3.67 23.78±11.64 12.97±2.91 12.97±2.91 12.97±2.91 12.97±2.91 2 60.00±2.81 19.17±1.66 19.58±1.73 19.58±1.73 19.58±1.73 19.58±1.73 2
GCN 60.54±5.30 59.19±3.30 58.92±3.15 58.92±3.15 58.92±3.15 58.92±3.15 2 64.82±2.24 53.11±4.44 35.15±3.14 35.39±3.23 35.20±3.25 35.50±3.08 2
GAT 61.89±5.05 58.38±4.05 58.38±3.86 INS INS INS 2 60.26±2.50 48.71±2.96 35.09±3.55 INS INS INS 2

5.2 Q1. PERFORMANCE UNDER HOMOPHILY & HETEROPHILY
Table 1 provides the test accuracy of different GNNs on the supervised node classification task over
datasets with varying homophily levels (arranged from low homophily to high homophily). A graph’s
homophily level is the average of nodes’ homophily levels. We report the best performance of each
model across different layers. In App. § B.4, we provide the analysis based on the nodes’ homophily
levels (§ 3), which is a better metric to predict GCN’s performance and is aligned with our theory.

GGCN performs the best in terms of average rank (1.78) across all datasets, which suggests its strong
adaptability to graphs of various homophily levels. In particular, GGCN achieves the highest accuracy
in 5 out of 6 heterophilous graphs (h is low). For datasets like Chameleon and Cornell, GGCN
enhances accuracy by around 6% and 3% compared to the second-best model. On homophily datasets
(Citeseer, Pubmed, Cora), the accuracy of GGCN is within a 1% difference of the best model.

Our experiments highlight that MLP is a good baseline in heterophilous datasets. In heterophilous
graphs, the models that are not specifically designed for heterophily usually perform worse than an
MLP. Though H2GCN* is the second best model in heterophilous datasets, we can still see that in the
Actor dataset, MLP performs better. GPRGNN and Geom-GCN*, which are specifically designed for
heterophily, achieve better performance than classic GNNs (GCN and GAT) in heterophilous datasets,
but do not show clear advantage over MLP. Our GGCN model is the only model that performs better
than MLP across all the datasets.

In general, GNN models perform well in homophilous datasets. GCNII* performs the best, and
GGCN, H2GCN*, GPRGNN and Geom-GCN* also achieve high performance.
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 2 presents the results for two homophilous
datasets (top) and two heterophilous datasets (bottom). Per model, we also report the layer at which
the best performance is achieved (column ‘Best’). We provides Table 2 in larger font in App. § D.

According to Table 2, GGCN and GCNII* achieve increase in accuracy when stacking more layers in
four datasets, while GPRGNN and PairNorm exhibit robustness against oversmoothing. Models that
are not designed for oversmoothing have various issues. The performance of GCN and Geom-GCN*
drops rapidly as the number of layers grows; H2GCN* requires concatenating all the intermediate
outputs and quickly reaches memory capacity; GAT’s attention mechanism also has high memory
requirements. We also find that GAT needs careful initialization when stacking many layers as it may
suffer from numerical instability in sparse tensor operations.

In general, models like GGCN, GCNII*, and GPRGNN that perform well under heterophily usually
exhibit higher resilience against oversmoothing. One exception is Geom-GCN*, which suffers more
than GCN. This model incorporates structurally similar nodes into each node’s neighborhood; this
design may benefit Geom-GCN* in the shallow layers as the node degrees increase. However, as
we point out in Thm. 2, when the effective homophily is low, higher degrees are harmful. If the
structurally similar nodes introduce lower homophily levels, their performance will rapidly degrade
once the effective homophily is lower than 1+ρ[l]iρ[l]i [. On the other hand, GGCN][ virtually][ changes the]

degrees thanks to the degree correction mechanism (§ 4.2), and, in practice, this design has positive
impact on its robustness to oversmoothing.


-----

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 1 shows the results for Citeseer. In the initial stage ([b]h[l]i
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 a GCN model**
that combines spectral filtering of graph signals and non-linearity for supervised node classification.
The scalability and numerical stability of GCNs was later improved with a localized first-order
approximation of spectral graph convolutions proposed in (Kipf & Welling, 2016). (Veliˇckovi´c et al.,
2017) proposes the first graph attention network to improve neighborhood aggregation. Many more
GCN variants have been proposed for different applications such as: computer vision (Satorras &
Estrach, 2018), social science (Li & Goldwasser, 2019), biology (Yan et al., 2019), algorithmic
tasks (Veliˇckovi´c et al., 2020; Yan et al., 2020), and inductive classification (Hamilton et al., 2017).
Concurrent work (Baranwal et al., 2021) provides theoretic analysis on the linear separability of
graph convolution but does not provide effective strategies to increase the separability.

**Oversmoothing. The oversmoothing problem was first discussed in (Li et al., 2018), which proved**
that by repeatedly applying Laplacian smoothing, the representations of nodes within each connected
component of the graph converge to the same value. Since then, various empirical solutions have been
proposed: residual connections and dilated convolutions (Li et al., 2019); skip links (Xu et al., 2018);
new normalization strategies (Zhao & Akoglu, 2019); edge dropout (Rong et al., 2019); and a new
model that even increases performance as more layers are stacked (Chen et al., 2020). Some recent
works provide theoretical analyses: (Oono & Suzuki, 2019) showed that a k-layer renormalized graph
convolution with a residual link simulates a lazy random walk and (Chen et al., 2020) proved that the
convergence rate is related to the spectral gap of the graph.

**Heterophily & GCNs. Heterophily has recently been recognized as an important issue for GCNs.**
It is first outlined in the context of GCNs in (Pei et al., 2019). (Zhu et al., 2020) identified a set of
effective designs that allow GCNs to generalize to challenging heterophilous settings, and (Zhu et al.,
2021) introduced a new GCN model that leverages ideas from belief propagation (Gatterbauer et al.,
2015). Though recent work (Chen et al., 2020) focused on solving the oversmoothing problem, it
also empirically showed improvement on heterophilous datasets; these empirical observations formed
the basis of our work. Finally, (Chien et al., 2021) recently proposed a PageRank-based model that
performs well under heterophily and alleviates the oversmoothing problem. However, they view the
two problems independently and analyze their model via an asymptotic spectral perspective. Our
work studies the representation dynamics and unveils the connections between the oversmoothing
and heterophily problems theoretically and empirically. As we demonstrate with GGCN, addressing
both issues in a principled manner provides superior performance across a variety of datasets.
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 a variety of domains.


-----

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. § C, we provide detailed hyperparameter setting for GGCN. We also provide our
code in the supplementary material and we will share the link to our code upon acceptance.

REFERENCES

Miltiadis Allamanis, Marc Brockschmidt, and Mahmoud Khademi. Learning to represent programs with graphs,
2018.

Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi-supervised classification: Improved linear separability and out-of-distribution generalization. arXiv preprint arXiv:2102.06966,
2021.

Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional
networks. arXiv preprint arXiv:2101.00797, 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 on 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):581–592, January 2015.

Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing
for quantum chemistry. In International conference on 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 arXiv:1609.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. Deepgcns: Can gcns go as deep as cnns? In
_Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 9267–9276, 2019._

Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semisupervised learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.

Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim.
Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in
_Neural 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 on Mining and Learning with Graphs, volume 8,
2012.

Mark EJ Newman. Assortative mixing in networks. Physical review letters, 89(20):208701, 2002.

Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification.
_International Conference on Learning Representations, 2019._


-----

Shashank Pandit, Duen Horng Chau, Samuel Wang, and Christos Faloutsos. Netprobe: a 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 Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gcn: Geometric graph
convolutional networks. International Conference on Learning Representations, 2019.

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 A. 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.13021, 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. AI magazine, 29(3):93–93, 2008.

Oleksandr Shchur, 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 on Knowledge discovery and data mining, pp. 807–816,_
2009.

Petar Veliˇckovi´c, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph
attention networks. arXiv preprint arXiv:1710.10903, 2017.

Petar Veliˇckovi´c, 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 arXiv:1910.11945, 2019.

Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph
convolutional networks. In International conference on machine learning, pp. 6861–6871. PMLR, 2019.

Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka.
Representation learning on 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: Groupingbased 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 execute 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.


-----

A DETAILED PROOFS OF THEOREMS IN § 3

A.1 PROOF OF LEMMA 1

_Proof. The loss function for SGC is: CrossEntropy(Softmax(F[(][L][)]W[(][L][)]_ + b[(][L][)]), yi). Rewrite
**W[(][L][)]** into an array of column vectors: W[(][L][)] = [w0[(][L][)], w1[(][L][)], . . . w[(][L][)][]][,][ b][(][L][)][ into an array of scalars:]
_|L|_

**b[(][L][)]** = [b[(]0[L][)], b[(]1[L][)], . . . b[(][L][)][]][, and][ F][(][L][)][ into an array of row vectors:][ F][(][L][)][ = [][f][ (]0[L][)]; f1[(][L][)]; . . . f [(][L][)][]][ (][[][·][;][ ·][]]
_|L|_ _|V|_

_e[f]i[(][L][)]_ **wc[(][L][)]** +b[(]c[L][)] 1, iff yi = c
means stacking vertically). Let pi,c ≡ _j_ _[e]fi[(][L][)]_ **wj[(][L][)]** +b[(]j[L][)] and let yi,c ≡ 0, otherwise [then we]

rewrite the loss function as: P

_n_ _|L|_

_yi,c_ log(pi,c), (11)

_−_ _n[1]_ _i=1_ _c=1_ _·_

X X

_n is the number of nodes used for training. To predict that the node vi belongs to class c, we require:_
_c[′]_ = c, pi,c > pi,c′ . Thus, we have:
_∀_ _̸_

_e[f][ (]i_ _[L][)]wc[(][L][)]+b[(]c[L][)]_ _e[f][ (]i_ _[L][)]wc[(][L][′][ +][)]_ _[b][(]c[L][′]_ [)]

_>_ _._ (12)
_i_ **wj[(][L][)]+b[(]j[L][)]** _i_ **wj[(][L][)]+b[(]j[L][)]**
_j_ _[e][f][ (][L][)]_ _j_ _[e][f][ (][L][)]_

It is equivalent to:

P P

**fi[(][L][)]wc[(][L][)]** + b[(]c[L][)] _> fi[(][L][)]wc[(][L][′]_ [)] + b[(]c[L][′][ .][)] (13)
It shows that the decision region of class c is decided by a set of hyper-planes:

**x(wc[(][L][)]** _−_ **wc[(][L][′][ ) + (][)]** _[b]c[(][L][)]_ _−_ _b[(]c[L][′][ )][)]_ _[ >][ 0][.]_ (14)

**x is the vector variable that describes the plane. Any vectors that satisfy the equation are on this**
plane. We note that for binary classification, there is one hyper-plane.

A.2 PROOF OF LEMMA 2

Before giving the proof, we first explain the meaning of the Lemma. As we point out in § 3, the
misclassification rate of an L-layer SGC can be studied through its last logistic-regression layer, the
input to which is **fi[(][L][)]** . To study the misclassification rate of an (L + 1)-layer SGC, we can view
_{_ _}_
the input to the last layer **fi[(][L][+1)]** as being moved from **fi[(][L][)]** . The misclassification rate is closely
_{_ _}_ _{_ _}_
related to the decision boundary and will be our tool for studying the change of the misclassification
rate. This Lemma studies the movements that bring the node representations closer to the original
decision boundary; we will prove that moving towards the original decision boundary by a non-zero
step is not beneficial (i.e., harmful) to the SGC’s performance.

_Proof. We prove it by contradiction and suppose that after the movements, the total misclassification_
rate is lowered. We denote the conditional distribution of {fi[(][L][)]} as f1[L][(][x][)][ conditioned on that they]
are from class 1 and f2[L][(][x][)][ conditioned on that they are from class 1 or class 2, respectively.][ To note]
that, the distributions of different layers are different.

After the movements, the representations from class 1 become: **fi[(][L][)]** _tw[∗][T]_ _, t > 0. tw[∗][T]_
_{_ _−_ _}_

represents moving towards the original decision boundary along the norm direction by a non-zero
step. This causes a corresponding change in the conditional PDF given that they are from class 1:
_f1[L][(][x][ +][ t][w][∗][T][ )][.]_

Recall that in § 3, the parameters for the original optimal hyperplane w[∗] and b[∗], and the parameters
for the later optimal hyperplane w[∗′] and b[∗′] are normalized such that when xw[∗] + b[∗] _> 0 and_
**xw[∗′]** + b[∗′] _> 0, we predict class 1._

The new misclassification rate conditioned on class 1 is:


_f1[L][(][x][ +][ t][w][∗][T][ )][d][x][ =]_
**xw[∗′]+b[∗′]<0**


_Mt[′]_ [=]


_f1[L][(][x][)][d][x][.]_ (15)
(x−tw[∗] _[T]_ )w[∗′]+b[∗′]<0


-----

The new misclassification rate conditioned on class 2 is:


_Mr[′]_ [=]

The new total misclassification rate is:


_f2[L][(][x][)][d][x][.]_ (16)
**xw[∗′]+b[∗′]>0**


_M_ _[′]_ = Mt[′][P][(][v][i] _[∈V][1][) +][ M][ ′]r[P][(][v][i]_ _[∈V][2][)]_

P(vi 1) P(vi 2)
= Mt[′] P(vi ∈V1) + ∈V P(vi ∈V2) [+][ M][ ′]r P(vi ∈V1) + ∈V P(vi ∈V2)

_ρ_ 1
= _t_ [+] _r[.]_

_ρ + 1_ _[M][ ′]_ _ρ + 1_ _[M][ ′]_


(17)


Next, we will prove that if the total misclassification is lowered, xw[∗] + b[∗] = 0 is not the optimal
hyper-plane before the movements which should achieve the lowest total misclassification rate.

Consider a hyper-plane xw[∗′] + b[∗′] 2 = 0. Given that w[∗][T] **w[∗′]** _> 0 and t > 0, for_ **x, s.t.**
_−_ _[t][w][∗]_ _[T][ w][∗′]_ _∀_

**xw[∗′]** +b[∗′] 2 _< 0, we have: (x_ _tw[∗][T]_ )w[∗′] +b[∗′] = xw[∗′] +b[∗′] 2 2 _< 0._
_−_ _[t][w][∗]_ _[T][ w][∗′]_ _−_ _−_ _[t][w][∗][T][ w][∗′]_ _−_ _[t][w][∗]_ _[T][ w][∗′]_

It means:


**x** (x _tw[∗][T]_ )w[∗′] + b[∗′] _< 0_ **x** **xw[∗′]** + b[∗′]
_{_ _|_ _−_ _} ⊇{_ _|_ _−_ _[t][w][∗][T]2[ w][∗′]_

Because f1[L][(][x][)][ is a PDF which is a nonnegative function,]


_< 0}._ (18)


_f1[L][(][x][)][d][x][ ≥]_

Z(x−tw[∗] _[T]_ )w[∗′]+b[∗′]<0

Similarly, we can obtain


_f1[L][(][x][)][d][x][.]_ (19)
_<0_


**xw[∗′]+b[∗′]−** _[t][w][∗]_ _[T]2[ w][∗′]_


**x** **xw[∗′]** + b[∗′] _> 0_ **x** **xw[∗′]** + b[∗′]
_{_ _|_ _} ⊇{_ _|_ _−_ _[t][w][∗][T]2[ w][∗′]_


_> 0}._ (20)


Thus,

Define

_Mf_
_≡_


_f2[L][(][x][)][d][x][ ≥]_
**xw[∗′]+b[∗′]>0**


_f2[L][(][x][)][d][x][.]_ (21)
_>0_


**xw[∗′]+b[∗′]−** _[t][w][∗]_ _[T]2[ w][∗′]_


_f1[L][(][x][)][d][x][ +]_
_<0_


_f2[L][(][x][)][d][x][.]_ (22)
_>0_


_ρ + 1_


_ρ + 1_


**xw[∗′]+b[∗′]−** _[t][w][∗]_ _[T]2[ w][∗′]_


**xw[∗′]+b[∗′]−** _[t][w][∗]_ _[T]2[ w][∗′]_


The quantity Mf represents the total misclassification rate before the movements if the decision
boundary is xw[∗′] + b[∗′] 2 = 0. Given Eq. 17, 19 and 21, we have:
_−_ _[t][w][∗]_ _[T][ w][∗′]_

_M_ _Mf_ _._ (23)

_[′]_ _≥_

Let M denotes the total classification rate before the movements. Based on the assumption that the
total misclassification rate is lowered after the movements (M > M _[′]), we have:_

_M > Mf_ _._ (24)

Eq. 24 indicates that we find a hyper-plane xw[∗′] + b[∗′] 2 = 0, which yields smaller total
_−_ _[t][w][∗]_ _[T][ w][∗′]_

misclassification rate than xw[∗] + b[∗] = 0 before the movements. This contradicts to the fact that
**xw[∗]** + b[∗] = 0 is the optimal hyper-plane before the movements.

A.3 PROOF OF THEOREM 1

_Proof. The first layer node representations are given by:_


_√di + 1f ·j[(0)]_


**fi[(1)]** = _dif + 1 i[(0)]_ [+] _jX∈Ni_


(25)
_dj + 1_ _[.]_


-----

Without loss of generality, we assume node vi is in the first class V1. Then, we can express the
conditional expectation of fi[(1)] as:

EA,{yi},{f (0)i _}|di,vi∈V1_ [(][f][ (1)]i _|vi ∈V1, di) = EA|di,vi∈V1_ (E{yi},{f (0)i _}|A,vi∈V1_ [(][f][ (1)]i _|vi ∈V1, A))_
(26)

Recall that A is the graph adjacency matrix; the first expectation is taken over the randomness of ground truth labels and initial input features, and the second expectation is taken over
the randomness of graph structure (A) given the degree of node vi and its label. Denote
_ki = E{yi},{f (0)i_ _}|A,vi∈V1_ [(][ |N]|N[ s]ii|[|] [)][ and][ h][i][ =][ E]A,{yi},{fi[(0)]}|vi∈V1,di [(][ |N]|N[ s]ii|[|] [)][.]


E{yi},{f (0)i _}|A,vi∈V1_ [(][f][ (1)]i _|vi ∈V1, A)_

=E{yi},{f (0)i _}|A,vi∈V1_ _dif + 1i[(0)]_ _[|][v][i][ ∈V][1][,][ A]_


**fj[(0)]**

! + _j_ _i_ E{yi},{f (0)i _}|A,vi∈V1_ _√di + 1_ _dj + 1_ _[|][v][i][ ∈V][1][,][ A]_

X∈N _·_

_√di + 1fj[(0)]_ _dj + 1_ _[|][A][, v][i][, v][j][ ∈V][1]!_ _· P(vpj ∈V1|A, vi ∈V1)_
_·_
p


E _yi_ _,_ **f (0)i** **A,vi,vj** 1
_{_ _}_ _{_ _}|_ _∈V_


_di + 1 [+]_


_j∈Ni_


_√di + 1fj[(0)]_ _dj + 1_ _[|][A][, v][i][ ∈V][1][, v][j][ ∈V][2]_
_·_
p


+E _yi_ _,_ **f (0)i** **A,vi** 1,vj 2
_{_ _}_ _{_ _}|_ _∈V_ _∈V_



_· P(vj ∈V2|A, vi ∈V1)!_

(27)


Let 1{·} represent the indicator function: it equals 1 if and only if the event in the bracket holds.

E{yi},{f (0)i _}|A,vi∈V1_ [(]jX∈Ni 1{vj ∈V1|A, vi ∈V1}) = _jX∈Ni_ P(vj ∈V1|A, vi ∈V1) = diki. (28)

Due to our assumptions in § 3, though the labels of nodes are dependent, they share the same
marginal distribution and their joint distribution is a permutation-invariant function. Thus, given
_vi.e.,i ∈Vj, j1(y[′]_ _i = 1)i,, the conditional joint distribution of P(vj_ 1 _vi_ 1) = P(vj[′] _{yt|t ̸= i} is also permutation invariant—_
_d{yiPi}( ∀,v Pj ∈V(vj ∈V∈N1|vi1 ∈V|A, v1i) = ∈V ∈V d1i) =ki| and k ∈Vi. P(vj ∈V1|vi ∈V[∈V]1[1]) =[|][v][i][ ∈V] ki. Due to the independence of[1][)][. Then for][ ∀][j][ ∈N][i][, we have:] A and_


**_µ_** _ki_

_di + 1 [+]_ _j_ _i_ _√di + 1_
X∈N _·_

**_µ_**

_di + 1 [+ ((1 +]√[ ρ]d[)]i[k] + 1[i][ −]_ _[ρ][)][µ]_


(1 _ki)_
_−_
_dj + 1_ **_[µ][ −]_** _√di + 1_ _dj + 1_ _[ρ][µ]_
_·_
p


E{yi},{f (0)i _}|vi∈V1,A[(][f][ (1)]i_ _|vi ∈V1, A) =_


_dj + 1_


_j∈Ni_


1 _j∈Ni_ _√dj_ +1

((1 + ρ)ki _ρ)_ **_µ_**

_di + 1 [+]_ P _√di + 1_ _−_ 

_√di+1_ 

1 _j∈Ni_ _√dj_ +1

((1 + ρ)ki _ρ)_ **_µ_**

_di + 1 [+]_ P _di + 1_ _−_ 




1 _di_ _j∈Ni_ _[r][ij]_ ((1 + ρ)ki _ρ)_ **_µ._**

_di + 1 [+]_ _di + 1_ P _di_ _−_ 


(29)


Combining Equation (26) and Equation (29) and given the independence of rij and ki, we have:

EA,{yi},{f (0)i _}|di,vi∈V1_ [(][f][ (1)]i _|vi ∈V1, di) =_ _di + 1 1_ [+] _di + 1di_ [E][A][|][d][i][,v][i][∈V][1] _j∈Ndi_ _i_ _[r][ij]_ EA|di,vi∈V1 ((1 + ρ)ki − _ρ)) µ_

 [P] 

1 + ((1 + ρ)hi _ρ)diri_
= _−_ **_µ_** _γi[1][µ][.]_

_di + 1_ _≡_

 

(30)


-----

**(3)Define hi > ϵ ≡1+ρ(1 +ρ** [&][ r] ρ[i])[ >]hi[ 1] −ϵ [.] _ρ, and we consider three cases: (1) hi ≤_ 1+ρ _ρ_ [,][ (2)][ h][i][ >] 1+ρ _ρ_ [&][ r][i][ ≤] [1]ϵ [, and]


**CASE 1: hhhiii** 1+1+1+ρρρρρρ
_≤ ≤ ≤_



_• Upper Bound_

We have:
1
_γi[1]_ _[≤]_ _di + 1_ _[≤]_ 2[1] _[.]_ (31)

_• Lower Bound_

To see if there exists a lower bound, we first show that when hi 1+ρ _ρ_ [,][ 1+((1+]d[ρ]i[)]+1[h][i][−][ρ][)][d][i][r][i] is a
_≤_

decreasing function of di given that di ≥ 1.

When hi ≤ 1+ρ _ρ_ [, we have:]

1. ((1 + ρ)hi _ρ)_ 0
2. _did+1i_ [is an increasing non-negative function of] − _≤_ _[ d][i]_

3. ri is an increasing non-negative function of di
4. _di1+1_ [is a decreasing function of][ d][i]


Thus [1+((1+]d[ρ]i[)]+1[h][i][−][ρ][)][d][i][r][i] is a decreasing function of di.


_ρ_

1+ρ [,][ 1+((1+]d[ρ]i[)]+1[h][i][−][ρ][)][d][i][r][i]

_ρ_

1+ρ [,]


When hi =

When hi <


1

_di+1_ [and][ 0][ <]


1

_di+1_ 2 [.]

_[≤]_ [1]


1 + ((1 + ρ)hi _ρ)diri_
_−_ + [1]

_di + 1_ _≤_ [((1 +][ ρ]d[)]i[h] + 1[i][ −] _[ρ][)][d][i][r][i]_ 2

(32)

+ [1]

_≤_ [((1 +][ ρ][)]2[h][i][ −] _[ρ][)][r][i]_ 2 _[.]_


And we know that when hi <


_ρ_

1+ρ [:]


((1 + ρ)hi _ρ)ri_

lim _−_

_ri→∞_ 2


+ [1]2 [=][ −∞][.] (33)


Thus,


lim 1 + ((1 + ρ)hi − _ρ)diri_ = _._ (34)

_ri→∞_ _di + 1_ _−∞_


**CASE 2: hhhiii > > >** 1+1+1+ρρρρρρ &&& _rrriii_ _ϵϵϵ_

_≤ ≤ ≤_ [1][1][1]


If hi >


_ρ_

1+ρ [,][ 0][ < ϵ][ ≤] [1][; if][ r][i][ ≤] [1]ϵ [,][ 0][ < ϵr][i][ ≤] [1][. Given]

E(fi[1][) =] 1 + ϵdiri

_di + 1_




**_µ._** (35)


we have 0 <


1

_di+1_ _[< γ]i[1]_ _[≤]_ [1][.]


**CASE 3: hhhiii > > >** 1+1+1+ρρρρρρ &&& _rrriii > > >_ [1][1]ϵ[1]ϵϵ

In this case, Equation (35) still holds, since hi >

_• Lower Bound_

If ri > [1]ϵ [, then][ ϵr][i][ >][ 1][ and therefore][ γ]i[1] _[>][ 1][.]_


_ρ_

1+ρ [.]


-----

_• Upper Bound_

When ϵ > 0,

Because

we have:

To sum it up,

**Remarks: Special cases**


1 + ϵdiri

_> [ϵd][i][r][i]_
_di + 1_ _di + 1_

(36)

_≥_ _[ϵr]2[i]_ _[.]_

_ϵri_

lim (37)

_ri_ 2 [=][ ∞][,]
_→∞_


1 + ϵdiri

lim = _._ (38)

_ri→∞_ _di + 1_ _∞_

( _,_ [1]2 []][,] if hi 1+ρ _ρ_

(0−∞, 1], if hi > ≤ 1+ρ _ρ_ [&][ r][i][ ≤] (1+ρ1)hi _ρ_ (39)

_−_
(1, ∞), otherwise.


_γi[1]_

_[∈]_


For different types of graphs and different nodes in the graph, diri might be different. For a d-regular
**graph whose nodes have constant degree or a graph whose adjacency matrix is row-normalized, we**
will have:

1 + ((1 + ρ)hi _ρ)diri_
_γi[1]_ [=] _−_

_di + 1_

  (40)

1 _di_
(
_≤_ (di + 1) [+] (di + 1) [) = 1]


Equality is achieved if and only if hi = 1. To note that, hi = 1 is not achievable for every node as
long as there are more than one class. Boundary nodes will suffer most.

A.4 PROOF OF THEOREM 2

_Proof. After propagating over multiple layers, we use ξi[l]_ [to account for the accumulated scaling]

effects (γi[l][). That is,][ E]A, _yi_ _,_ **fi[(0)]** _di_ _dfii[(]+1[l][)]_ _[|][d][i]_ = ξi[l][µ][. Furthermore, conditioned on][ A][ and][ ξ]i[l][, the]
_{_ _}_ _{_ _}|_

 

set of nodes contributing positively to node vi is defined as:

_T_

_Nˆi[s][(][A][, ξ]i[l][)][ ≡{][v][j][|][v][j][ ∈N][i][ and][ (][ξ]i[l][µ][)][ ·][ E]{yi},{fi[(0)]}|ξi[l][,][A]_ **fj[(][l][)]** _|ξil[,][ A]_ _> 0}._

 

EA,{yi},{f (0)i _}|di,ξi[l][,v][j]_ _[∈N][i]_ **fj[(][l][)][r][ij][|][d][i][, ξ]i[l][, v][j][ ∈N][i]!** = (−ξi[l]ρ′µ[l]i[ξ]i[l]′µ _vvjj ̸∈ ∈_ _NN[ˆ][ˆ]ii[s][s][(][(][A][A][, ξ][, ξ]ii[l][l][)][)]_

In the following proof, we use _N[ˆ]i[s]_ [to refer to][ ˆ]Ni[s][(][A][, ξ]i[l][)][ for conciseness.]

The representations at (l + 1)-th layer:


**fi[(][l][+1)]** = _dif + 1 i[(][l][)]_ [+]


_√di + 1f ·i[(][l][)]_


(41)
_dj + 1_


_j∈Ni_


-----

**fi[(][l][+1)]** _di, ξi[l]_
_|_ !

**fi[(][l][)]**

_di + 1_ _[|][d][i][, ξ]i[l]_


EA, _yi_ _,_ **f (0)i** _di,ξi[l]_
_{_ _}_ _{_ _}|_

EA, _yi_ _,_ **f (0)i** _di,ξi[l]_
_{_ _}_ _{_ _}|_


(42)

(43)i

_dj + 1_ _[|][d][i][, ξ][l]_

(44)


_√di + 1f ·j[(][l][)]_




_j∈Ni_

 [X]


+ EA, _yi_ _,_ **f (0)i** _di,ξi[l]_
_{_ _}_ _{_ _}|_


**fj[(][l][)]√di + 1**

_i_
_dj + 1_

p _[|][d][i][, ξ][l]_


_ξi[l][µ]_

_di + 1 [+]_


1

_di + 1_ [E][A][,][{][y][i][}][,][{][f][ (0)]i _}|di,ξi[l]_


_j∈Ni_


In § 3, we assume that _dj_ follow the same distribution and their joint distribution function is
_{_ _}_
permutation-invariant, and {yj} and {fj[l][}][ also have this property. Thus, conditioned on][ d][i][,][ ξ]i[l] [and][ N][i][,]

the distribution of **fj[(]√[l][)]√djd+1i+1** is the same for ∀j ∈Ni (neighbors are indistinguishable) and we obtain:


EA,{yi},{f (0)i _}|di,ξi[l][,][N][i]_ _j_ _i_ **fj[(][l][)]√djd + 1i + 1** _i[,][ N][i]!_

X∈N _[|][d][i][, ξ][l]_

_diEA,{yi},{f (0)i_ _}|di,ξi[l][,][N][i][,v][j]_ _[∈N][i]_ pfj[(][l][)]√djd + 1i + 1 _i[,][ N][i][, v][j]_ _[∈N][i]_

p _[|][d][i][, ξ][l]_


(45)

(46)


Given that the joint distribution of _dj_, the joint distribution of _yj_ and
_{_ _}_ _{_ _}_
the joint distribution of _{fj[l][}]_ are permutation-invariant functions, for any _Ni,_

EA,{yi},{f (0)i _}|di,ξi[l][,][N][i]_ _j∈Ni_ **fj[(]√[l][)]√djd+1i+1** _[|][d][i][, ξ]i[l][,][ N][i]!_ is the same. That is:

P


EA,{yi},{f (0)i _}|di,ξi[l]_ _j_ _i_ **fj[(][l][)]√djd + 1i + 1** _i!_

X∈N _[|][d][i][, ξ][l]_

EA,{yi},{f (0)i _}|di,ξi[l][,][N][i]_ _j_ pi **fj[(][l][)]√djd + 1i + 1** _i[,][ N][i]!_

X∈N _[|][d][i][, ξ][l]_

_diEA,{yi},{f (0)i_ _}|di,ξi[l][,v][j]_ _[∈N][i]_ **fj[(]p[l][)]√djd + 1i + 1** _i[, v][j]_ _[∈N][i]_

p _[|][d][i][, ξ][l]_


(47)

(48)

(49)


We note that vj in Equation 49 can be any node except vi due to the equivalence of those nodes.


-----

Combining Equation 44 and Equation 49, we can obtain:


**fi[(][l][+1)]** _di, ξi[l]_
_|_


EA, _yi_ _,_ **f (0)i** _di,ξi[l]_
_{_ _}_ _{_ _}|_


(50)

(51)

(52)


_ξi[l][µ]_ _di_ **fj[(][l][)]√di + 1**

_di + 1 [+]_ _di + 1_ [E][A][,][{][y][i][}][,][{][f][ (0)]i _}|di,ξi[l][,v][j]_ _[∈N][i]_ _dj + 1_ _i[, v][j]_ _[∈N][i]!_ (51)

_[|][d][i][, ξ][l]_

_ξi[l][µ]_ _di_ p **fj[(][l][)]√di + 1**

_di + 1 [+]_ _di + 1_ EA,{yi},{f (0)i _}|di,ξi[l][,v][j]_ _[∈]N[ˆ]i[s][,v][j]_ _[∈N][i]_ _dj + 1_ _i[, v][j]_ _[∈]_ _N[ˆ]i[s][, v][j][ ∈N][i]!_ (52)

_[|][d][i][, ξ][l]_

P _vj ∈_ _N[ˆ]i[s][|][v][j][ ∈N][i][, d][i][, ξ]i[l]!_ + EA,{yi},{f (0)i _}|di,ξi[l][,v][j]_ _[̸∈]pN[ˆ]i[s][,v][i][∈N][i]_ **fj[(][l][)]√djd + 1i + 1** _i[, v][j]_ _[̸∈]_ _N[ˆ]i[s][, v][j][ ∈N](53)[i]!_

p _[|][d][i][, ξ][l]_

P _vj ̸∈_ _N[ˆ]i[s][,][ |][d][i][, ξ]i[l][, v][j]_ _[∈N][i]!!_ (54)

_ξi[l][µ]_ _diP(vj ∈_ _N[ˆ]i[s][|][d][i][, ξ]i[l][, v][j][ ∈N][i][)]_ _ξi[l]′µ_ _di(1 −_ P(vj ∈ _N[ˆ]i[s][|][d][i][, ξ]i[l][, v][j][ ∈N][i][))]_ _ρ[l]i[ξ]i[l]′µ_ (55)

_di + 1 [+]_ _di + 1_ _−_ _di + 1_ !


_ξi[l][µ]_ _di_

_di + 1 [+]_ _di + 1_ [E][A][,][{][y][i][}][,][{][f][ (0)]i _}|di,ξi[l][,v][j]_ _[∈N][i]_


= _ξi[l][µ]_ _Ni[s][|][d][i][, ξ]i[l][, v][j][ ∈N][i][)(1 +][ ρ][l]i[)][ −]_ _[ρ][l]i[)][ξ]i[l]′µ_ (56)

_di + 1 [+][ d][i][(][P][(][v][j][ ∈]_ [ˆ] _di + 1_

Define ¯ri[l] _≡_ _ξξi[l]i[l]′_ [. If we know the degree][ d][i][,][ ξ]i[l][, and that a neighbor][ v][j][ is in the group][ ˆ]Ni[s][,][ ¯]ri[l]

actually represents the ratio of expected fj[l][r][i,j][ to expected][ f][ l]i [. We regard it as the effective related]
degree at l-th layer. For the initial layer, if we know the degree di, yi, and that a neighbor vj is in
the group Ni[s][, the ratio of][ f][ 0]j _[r][i,j][ to][ f][ 0]i_ [is][ r][ij][. Recall that the related degree][ r][i][ at the initial layer]
is the expected average of rij in the neighborhood. Thus ¯ri[l] is an extension of ri. Moreover, let
_ha positive contribution in expectation. This naturally extends the meaning of homophily in deeperˆ[l]i_ [=][ P][(][v][j][ ∈] _N[ˆ]i[s][|][v][j][ ∈N][i][, d][i][, ξ]i[l][)][ represent the probability of a neighbor whose representation has]_
layers. Thus, we regard it as the effective homophily of node vi at l-th layer. Given the degree di, ξi[l][,]
_ρ[l]i_ [represents the ratio of the probability that a neighbor will have a positive rather than a negative]
contribution to vi. This naturally extends the meaning of ρ.


We further write Equation 56 as:

_ξi[l]_

_di + 1_


( h[ˆ][l]i[(1 +][ ρ]i[l][)][ −] _[ρ][l]i[)][d][i]r[¯]il)_


1 +


and it will have three cases similar to Thm. 1.


-----

A.5 PROOF OF THEOREM 3

_Proof. Similar to Equation 26, we can express the conditional expectation of fi[(1)]_ as:


**fi[(1)]** _vi_ 1, di
_|_ _∈V_


EA, _yi_ _,_ **f (0)i** _di,vi_ 1
_{_ _}_ _{_ _}|_ _∈V_


**fi[(1)]** _vi_ 1, di, m[0]i
_|_ _∈V_


**fi[(0)]**

_di + 1_ _[|][v][i][ ∈V][1][, d][i][, m]i[0]_


=Em0i EA, _yi_ _,_ **f (0)i** _di,vi_ 1,m[0]i

_[|][v][i][∈V][1][,d][i]_ _{_ _}_ _{_ _}|_ _∈V_



=Em0i

_[|][v][i][∈V][1][,d][i]_


EA, _yi_ _,_ **f (0)i** _vi_ 1,di,m[0]i
_{_ _}_ _{_ _}|_ _∈V_


_√di + 1f ·j[(0)]_




_j∈Ni_

 [X]


+EA, _yi_ _,_ **f (0)i** _vi_ 1,di,m[0]i
_{_ _}_ _{_ _}|_ _∈V_

**_µ_**
=

_di + 1_


_i_
_dj + 1_ _[|][v][i][ ∈V][1][, d][i][, m][0]_


_√di + 1f ·j[(0)]_


+Em0i

_[|][v][i][∈V][1][,d][i]_


EA _di,vi_ 1,m0i
_|_ _∈V_


E _yi_ _,_ **f (0)i** **A,vi,vj** 1,m[0]i
_{_ _}_ _{_ _}|_ _∈V_


_i_ _[, v][j]_

pdj + 1 _[|][A][, m][0]_ _[∈V][1][, v][i]_ _[∈V][1]_

_· P(vj ∈V2|m[0]i_ [)]!!!.

(57)


_j∈Ni_


P(vj 1 _m[0]i_ _[, v][i]_

_·_ _∈V_ _|_ _[∈V][1][,][ A][)]_

+E _yi_ _,_ **f (0)i** **A,vi** 1,vj 2,m[0]i
_{_ _}_ _{_ _}|_ _∈V_ _∈V_


_√di + 1f ·j[(0)]_


_i_ _[, v][i]_
_dj + 1_ _[|][A][, m][0]_ _[∈V][1][, v][j]_ _[∈V][2]_


Next, we will show how to compute the conditional expectation and conditional probability in the
summand.

E{yi},{f (0)i _}|A,vi,vj_ _∈V1,m[0]i_ _√di + 1fj[(0)]_ _dj + 1_ _[|][m]i[0][, v][i][, v][j]_ _[∈V][1][,][ A]!_

_·_

=E{yi},{f (0)i _}|A,vi∈V1,m[0]i_ _[,v][j]_ _√di + 1fj[(0)]pdj + 1_ _[|][A][, m]i[0][, v][i]_ _[∈V][1][, v][j]_ _[∈V][1][, v][j][wrongly send information]_

_·_

P(vjwrongly send information **A, mp[0]i** _[, v][i]_

_·_ _|_ _[∈V][1][, v][j]_ _[∈V][1][)]_

**fj[(0)]**

+E{yi},{f (0)i _}|A,vi∈V1,m[0]i_ _[,v][j]_ _√di + 1_ _dj + 1_ _[|][A][, m]i[0][, v][i]_ _[∈V][1][, v][j]_ _[∈V][1][, v][j][correctly send information]_

_·_

P(vjcorrectly send information **A, mp[0]i** _[, v][i]_

_·_ _|_ _[∈V][1][, v][j]_ _[∈V][1][)][.]_
(58)


Combined with the independence assumption, we have:

P(vjwrongly send information|A, m[0]i _[, v][i]_ _[∈V][1][, v][j]_ _[∈V][1][) =][ m]i[0][.]_ (59)

Similarly, we obtain:

P(vjcorrectly send information|A, m[0]i _[, v][i]_ _[∈V][1][, v][j]_ _[∈V][1][) = 1][ −]_ _[m]i[0][.]_ (60)


-----

Then Equation (58) can be rewritten as:

E{yi},{f (0)i _}|A,vi,vj_ _∈V1,m[0]i_ _√di + 1fj[(0)]_ _dj + 1_ _[|][m]i[0][, v][i][, v][j]_ _[∈V][1][,][ A]!_

_·_

**fj[(0)]p**

=E{yi},{f (0)i _}|A,vi∈V1,m[0]i_ _[,v][j]_ _√di + 1_ _dj + 1_ _[|][A][, m]i[0][, v][i]_ _[∈V][1][, v][j]_ _[∈V][1][, v][j][wrongly send information]_

_·_

+E{yi},{f (0)i _}|A,vi∈V1,m[0]i_ _[,v][j]_ _√di + 1fj[(0)]pdj + 1_ _[|][A][, m]i[0][, v][i]_ _[∈V][1][, v][j]_ _[∈V][1][, v][j][correctly send information]_

_·_

_m[0]i_ **_[µ]_** (1 _m[0]ip[)][µ]_
= _−_
_−_ _√di + 1 ·_ _dj + 1 [+]_ _√di + 1 ·_ _dj + 1_

(1 2m[0]i [)]p[µ] p
= _−_
_√di + 1_ _dj + 1_ _[.]_
_·_

(61)

p


_m[0]i_

_·_

_· (1 −_ _m[0]i_ [)]


Similarly, we have:

**fj[(0)]** (1 2m[0]i [)][ρ][µ]

E{yi},{f (0)i _}|A,vi∈V1,vj_ _∈V2,m[0]i_ _√di + 1_ _dj + 1_ _[|][A][, m]i[0][, v][i]_ _[∈V][1][, v][j]_ _[∈V][2]!_ = _√di + 1 −_ _._ _dj + 1_ _[.]_

_·_ _·_

(62)

p p

Consider the independence between m[0]i [and node class & degrees, and insert Equation (61) and]
Equation (62) into Equation (57), we will have:


**fi[(1)]** _vi_ 1, di
_|_ _∈V_

EA _di,vi_ 1,m0i
_|_ _∈V_

EA _di,vi_ 1,m0i
_|_ _∈V_


EA, _yi_ _,_ **f (0)i** _di,vi_ 1
_{_ _}_ _{_ _}|_ _∈V_

**_µ_**

_di + 1 [+][ E][m]i[0][|][v][i][∈V][1][,d][i]_

**_µ_**

_di + 1 [+][ E][m]i[0][|][v][i][∈V][1][,d][i]_


**_µ_** _i_ EA _di,vi_ 1,m0i ( (1 − 2m[0]i [)][k][i][µ] _i_ [)(1][ −] _[k][i][)][ρ][µ]_

_di + 1 [+][ E][m][0][|][v][i][∈V][1][,d][i]_ _|_ _∈V_ j _i_ _√di + 1_ _dj + 1 [+ (1]√[ −]di[2] + 1[m][0]_ _dj + 1 [)]_

_∈N_ _·_ _·_

 [X] p p 

**_µ_** _i_ EA _di,vi_ 1,m0i (1 − 2m[0]i [)(][ρ][ + (1][ −] _[ρ][)][k][i][)][µ]_

_di + 1 [+][ E][m][0][|][v][i][∈V][1][,d][i]_ _|_ _∈V_ j _i_ _√di + 1_ _dj + 1_  !

_∈N_ _·_

0  [X] p 

**_µ_** (1 2mi [)(][ρ][ + (1][ −] _[ρ][)][h][i][)][d][i][r][i]_

_di + 1 [+][ E][m]i[0][|][v][i][∈V][1][,d][i]_  _−_ _di + 1_  **_µ!_**

1 + (1 2e0i [)(][ρ][ + (1][ −] _[ρ][)][h][i][)][d][i][r][i]_
_−_ _di + 1_ **_µ ≡_** _γi[1][E][(][f][ (0)]i_ ).
 

(63)


Whenthe ranges ofe[0]i _[<][ 0] h[.][5]i ≤[,][ 0][ < ϵr]1 γ, ρi[1] + (1[, when][i][ ≤]_ _−[1][, it resembles the derivations of CASE 2; when][ e]ρi[0])h[≥]i = (1[0][.][5][,][ ϵ] −[′][ ≤]hi[0])ρ[, it resembles the derivations of CASE 1 in Proof A.3; when] + hi > 0. Define ϵ[′]_ _≡_ (1 −[ e]2i[0]e[0]i[<][)(][ 0][ρ][ + (1][.][5][,][ ϵr][ −][i][ >][ρ][ 1][)][h][, it resembles][i][)][. To obtain]
the derivations of CASE 3.

B ADDITIONAL EXPERIMENTS

B.1 ABLATION STUDY

Table B.1: Ablation study: degree correction has consistent benefits (robust to oversmoothing & ability to handle
heterophily) in different datasets while signed information has more benefits in heterophilous datasets. Best
performance of each model is highlighted in gray.

**Layers** **2** **4** **8** **16** **32** **64** **2** **4** **8** **16** **32** **64**

**Cora (h=0.81)** **Citeseer (h=0.74)**

Base 86.56±1.21 86.04±0.72 85.51±1.51 85.33±0.72 85.37±1.58 72.17±8.89 76.51±1.63 75.03±1.67 73.96±1.52 73.59±1.51 71.91±1.94 32.08±15.74
+deg 86.72±1.29 86.02±0.97 85.49±1.32 85.27±1.59 85.27±1.51 84.21±1.22 76.63±1.38 74.64±1.97 74.15±1.61 73.73±1.31 73.61±1.84 70.56±2.27
+sign 84.81±1.63 86.06±1.7 85.67±1.26 85.39±0.97 84.85±0.98 78.57±6.73 77.13±1.69 74.56±2.02 73.64±1.65 72.31±2.32 71.98±3.44 68.68±6.72
+deg,sign 86.96±1.38 86.20±0.89 85.63±0.78 85.47±1.18 85.55±1.66 77.81±7.95 76.81±1.71 74.68±1.97 74.69±2.35 73.28±1.45 71.81±2.28 69.91±3.97

**Cornell (h=0.3)** **Chameleon (h=0.23)**

Base 61.89±3.72 60.00±5.24 58.92±5.24 56.49±5.73 58.92±3.15 49.19±16.70 64.98±1.84 62.65±3.09 62.43±3.28 54.69±2.58 47.68±2.63 29.74±5.21
+deg 63.78±5.57 62.70±5.90 59.46±4.52 56.49±5.73 57.57±4.20 58.92±3.15 66.54±2.19 68.31±2.70 68.99±2.38 67.68±3.70 56.86±8.80 41.95±9.56
+sign 85.41±7.27 76.76±7.07 70.00±5.19 67.57±9.44 63.24±6.07 63.24±6.53 65.31±3.20 53.55±6.35 53.05±2.28 51.93±4.00 57.17±3.39 51.93±8.95
+deg,sign 84.32±6.37 78.92±8.09 73.51±5.90 70.81±5.64 68.11±5.14 62.43±6.67 65.75±1.81 61.49±7.38 53.73±7.79 52.43±5.37 55.92±5.14 56.95±3.93


-----

We now study the impact of two proposed mechanisms (signed messages and degree correction, § 4).
To better show their effects, we add each design choice to a base model and track the changes in
the node classification performance. As the base model, we choose a GCN variant that uses the
message passing mechanism (Kipf & Welling, 2016) with weight bias, a residual connection (but
_not decaying aggregation) for robustness to oversmoothing, and Elu non-linearity σ. We denote the_
model that replaces the message passing with our signed messages mechanism as +sign, and the
model that incorporates the degree correction as +deg. The model that uses both designs is denoted
as +sign,deg. Table B.1 gives the accuracy of the models in the supervised node classification
task for different layers.

We observe that both mechanisms alleviate the oversmoothing problem. Specifically, the base model
has a sharp performance decrease after 32 layers, while the other models have significantly higher
performance. In general, the +deg model is better than +sign in alleviating oversmoothing, and has
a consistent performance gain across different data. For Chameleon, we observe increase in accuracy
as we stack more layers; the large performance gain of GGCN results from the degree correction. In
Cora and Cornell, +sign,deg consistently performs better across different layers than the model
with only one design, demonstrating the constructive effect from our two proposed mechanisms.

The signed message design has an advantage in heterophilous datasets. In the Cornell dataset, using
signed information rather than plain message passing results in over 20% gain, which explains the
strong performance of GGCN. However, in homophilous datasets, the benefit from signed messages
is limited, as these datasets have few different-class neighbors. This is because when the effective

homophily _h[l]i_ [is high and error rate][ e]i[0] [is low,][ lim][b]h[l]i[→][1][,e]i[0][→][0] (1−2(1+e[0]i [)(]ρ[ρ])[+(1][b]h[l]i[−][−][ρ][ρ][)][b]h[l]i[)][ = 1][, so using signed]

messages is less beneficial in homophilous datasets.

[b]

B.2 BATCH NORM & LAYER NORM

In § 4, we use decaying aggregation instead of other normalizing mechanisms. Other mechanisms,
such as batch or layer norm, may be seen as solutions to the heterophily and oversmoothing problems.
However, batch norm cannot compensate for the dispersion of the mean vectors (§ 3) due to different
degrees and homophily levels of the nodes. Although, to some extent, it reduces the speed by
which the representations of the susceptible nodes (case 1 & 2) move towards the other class (good
for oversmoothing), it also prevents the representations of the nodes that could benefit from the
propagation (case 3) from increasing the distances (drop in accuracy). Layer norm is better at
overcoming the dispersion effect but may lead to a significant accuracy drop in some datsets when a
subset of features are more important than the others. Thus, we do not use any of these normalizations.

Next, we provide experiments to show the effects of batch norm and layer norm. We use the following
base model (the same model used in §B.1): a GCN Kipf & Welling (2016) with weight bias, Elu
non-linearity and residual connection. We do not include any of our designs so as to exclude any
other factors that can affect the performance. The models we compare against are +BN and +LN,
which represent the models that add batch norm and layer norm right before the non-linear activation,
respectively.

Table B.2: 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.

**Layers** **2** **4** **8** **16** **32** **64** **2** **4** **8** **16** **32** **64**

**Cora (h=0.81)** **Citeseer (h=0.74)**

Base 86.56±1.21 86.04±0.72 85.51±1.51 85.33±0.72 85.37±1.58 72.17±8.89 76.51±1.63 75.03±1.67 73.96±1.52 73.59±1.51 71.91±1.94 32.08±15.74
+BN 84.73±1.10 83.76±1.61 83.94±1.51 84.57±1.22 84.63±1.58 85.17±1.18 71.62±1.48 71.58±1.00 72.18±1.39 72.45±1.42 72.76±1.31 72.61±1.41
+LN 84.73±1.63 86.60±1.01 86.72±1.36 86.08±1.16 85.67±1.23 85.13±1.20 76.11±1.80 74.02±2.77 75.00±1.95 74.50±0.96 74.49±2.10 73.94±2.03

**Cornell (h=0.3)** **Chameleon (h=0.23)**

Base 61.89±3.72 60.00±5.24 58.92±5.24 56.49±5.73 58.92±3.15 49.19±16.70 64.98±1.84 62.65±3.09 62.43±3.28 54.69±2.58 47.68±2.63 29.74±5.21
+BN 58.38±6.42 59.19±4.59 55.41±6.65 57.30±3.15 57.57±6.29 57.02±6.19 60.88±2.24 61.38±2.17 61.84±4.08 61.97±3.01 59.04±3.79 57.84±3.67
+LN 58.11±6.19 55.68±6.19 58.92±7.63 59.19±3.07 58.92±3.15 58.00±3.03 61.86±1.73 62.17±2.48 62.41±2.99 60.37±2.36 58.25±3.03 58.92±3.15

Table B.2 shows that both batch norm and layer norm can help with oversmoothing. Moreover,
adding layer norm is in general better than adding batch norm. This is expected because the scaling
effect caused by the propagation can be alleviated by normalizing across the node representations.
Thus, the dispersion of the expected representations can be mitigated. On the other hand, batch norm
normalizes across all the nodes, so it requires sacrificing the nodes that benefit (case 3) to compensate


-----

for the nodes that are prone to moving towards the other classes (case 1 & case 2). As a result, batch
norm is less effective in mitigating oversmoothing and leads to a bigger decrease in accuracy.

Another finding is that both layer norm and batch norm lead to a significant accuracy decrease
(2%-3%) in the heterophilous datasets. +BN has a clear accuracy drop even in the homophilous
datasets. As Thm. 1 points out: higher heterophily level may result in sign flip. If the representations
flip the sign, using batch norm or layer norm will not revert the sign, but they may instead encourage
the representations to move towards the other class more.

Given the limitations shown above, we do not use either batch norm or layer norm in our proposed
model, GGCN.

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. 1 and 2, in order to see both the initial and the developing stage, we**
need to use homophilous datasets. In heterophilous datasets, most nodes satisfy case 1, so the initial
stage does not exist.

**Measurement of effective homophily** _hhh[l]i[l]i[l]i[.][ To estimate the effective homophily][ b]h[l]i[, we measure]_
the portion of neighbors that have the same ground truth label as vi and are correctly classified.
Following our theory, we estimate _h[l]i_ **[before][b]bb** [ the last propagation takes place and analyze its impact]
on the accuracy of the final layer. In more detail, we obtain the node representations before the
last propagation from a trained vanilla GCN Kipf & Welling (2016) and then perform a linear

[b]
transformation using the weight matrix and bias vector from the last layer. Then, we use the
transformed representations to classify the neighbors of node vi and compute _h[l]i[. We note that we]_
leverage the intermediate representations only for the estimation of _h[l]i[; the accuracy of the final layer]_
is still measured using the outputs from the final layer. [b]

**Degree intervals. To investigate the** Table B.3: Citeseer: Accuracy (Acc) and average effective ho-[b]
change in GCN accuracy with different mophily (h[¯][l]i[) for nodes with different degrees across various layers.]
layers for nodes with different degrees, Last layer of initial stage marked in gray.
we categorize the nodes in n degree b
intervals. For the degree intervals, we

**Degrees**

use logarithmic binning (base 2). In

**Layers** [1, 2] [3, 6] [7, 15] [16, 39] [40, 99]

detail, we denote the highest and lowest
degree by dmax and dmin, respectively, **2** Acc¯ 74.44 78.51 84.04 96.00 100.00
and let Ω _n_ . Then, _h[l]i_ 0.65 0.67 0.72 0.83 0.91
_≡_ [log][2][ d][max][−][log][2][ d][min]

we divide the nodes into n intervals, Acc 70.92 77.59 83.03 92.75 100.00
where the j-th interval is defined as: **3** b¯

[dmin 2[(][j][−][1)Ω], dmin 2[j][Ω]). _h[l]i_ 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-** **4** b¯
ble B.3 show how the accuracy changes _h[l]i_ 0.54 0.58 0.66 0.79 0.84
with the number of layers for differ- Acc 41.66 48.70 56.97 61.33 11.11
ent node degree intervals. We observethat in the initial stage, the accuracy in- **5** bh¯[l]i 0.36 0.38 0.45 0.48 0.11

Acc 23.61 28.87 41.17 31.83 0.00

creases as the degree andHowever, in the developing stage, theh[¯][l]i [increase.] **6** bh¯[l]i 0.18 0.19 0.27 0.22 0.00
accuracy of high-degree nodes dropsb

b

more sharply than that of low-degree
nodes.

**Dataset: Cora. The results for Cora are shown in Figure B.1 and Table B.4. In the initial stage, the**
nodes with lower


-----

Table B.4: Cora: Accuracy and average effective
homophily (h[¯][l]i[) for nodes with different degrees]
across different layers. Last layer of initial stage
marked in gray.b

**Degrees**

**Layers** [1, 2] [3, 7] [8, 21] [22, 60] [61, 168]

Acc 85.14 88.52 83.78 90.00 100.00
**2** ¯
_h[l]i_ 0.77 0.77 0.72 0.63 0.81

Acc 82.28 87.26 84.42 85.00 100.00
**3** b¯
_h[l]i_ 0.77 0.78 0.73 0.64 0.84

Acc 79.57 85.52 83.26 85.00 100.00
**4** b¯
_h[l]i_ 0.75 0.76 0.71 0.63 0.80

Acc 77.38 83.75 82.83 85.00 96.19
**5** b¯
_h[l]i_ 0.72 0.73 0.68 0.56 0.83

Acc 63.35 68.20 66.01 70.00 78.57
**6** b¯
_h[l]i_ 0.57 0.60 0.54 0.52 0.67

Acc 30.91 30.62 29.12 17.50 21.43
**7** b¯
_h[l]i_ 0.25 0.26 0.21 0.26 0.23

Acc 31.48 31.02 28.44 32.50 25.24
**8** b¯
_h[l]i_ 0.24 0.26 0.20 0.28 0.24


Figure B.1: Cora: Accuracy per (logarithmic) degree bin.


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 _h[¯][l]i_ [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. b

GCN’s behavior on both Citesser and Cora datasets verifies our conjecture based on our theorems in
§ 3.3.

B.4 HOMOPHILY METRIC

In Table 1, we provide the graph homophily level h, which is defined as the average of the nodes’
homophily levels. In our theoretical analysis in § 3, we use a node’s homophily level and relative
degree to characterize three cases (Fig. 2 and Thm. 1). To better align our empirical results with our
theoretical analysis, we provide below the proportion of nodes in each case.

Table B.5: The percentage (%) of nodes in each case (Fig. 2 and Thm. 1): case 1:hi > 1+ρ _ρ_ [&][ r][i][ ≤] (1+ρ)1hi _ρ_ [and case 3: otherwise. The dominant case for each dataset is colored in grey.] hi ≤ 1+ρ _ρ_ [, case 2:]

_−_

**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** 5 5 5 5 5 5 7 3 6

Case 1 87.43 78.49 63.49 47.74 48.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 3.83 5.58 6.99 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 3 is the dominant case. As we stated in Thm 1, under
"non-swapping" condition, case 3 is the only case to have a benefit. Thus, in the commonly-used
homophilous datasets (Citeseer, Pubmed and Cora), case 3 dominates and enjoys the benefits from
graph convolution. In the Texas, Wisconsin and Actor datasets, only case 1 dominates and case 1
hurts the performance most, this explains why GCN performs worse than most methods in Table 1. In
the Squirrel and Chameleon datasets, both case 1 and case 2 dominate, GCN yields acceptable results.
Using portions of the three cases to analyze the datasets is a better metric, because it aligns more
with the GCN’s performance. As shown by Table B.5, Wisconsin, Actor, Squirrel and Chameleon
have very close graph level homophily, but GCN’s performance are quite different as shown in Table
1. Our way to define homophily level does predict that GCN should perform decently in Squirrel and
Chameleon datasets.


-----

B.5 COMPLEXITY ANALYSIS

We first analyze the time complexity of the forward path GGCN. For degree correction, we need to
compute the rij. However, we do not need to compute all of them, and we only need to compute
_rij for node pairs who are linked. The time complexity is O(|E|), but it is a one-time computation,_
the results of which can be saved. We compute τij[l] [based on the learned weights][ λ]0[l] _[, λ][l]1[. The time]_
complexity is O(|E|· _L), where L is the number of layers. The time complexity to compute the signed_
function is O(|E| · H · L), where H is the hidden dimension of representations, and we only compute
the cosine similarity between the nodes that are linked. We also need to compute the multiplication
of the propagation matrix and representation matrices. The time complexity is O(|V|[2] _· H · L), ._
Similarly, the time complexity of the multiplication of representation matrices and the weight matrices
is O(|V| · H [2] _· L). The total time complexity would be O(max(|V|[2], |E|) · H · L). The complexity of_
GGCN resembles the complexity of attention-based model. Thus we compare with GAT (Veliˇckovi´c
et al., 2017) the total time to train and test on 4 larger homophilous and heterophilous datasets. We
run the training and testing for 10 times.

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 7m24s 2m29s 2m9s 5m47s
GAT 8m14s 7m34s 9m39s 4m11s

In general, GGCN runs faster than GAT because degree correction and signed messages in GGCN
learn fewer parameters.

C HYPERPARAMETERS AND PARAMETERS

C.1 HYPERPARAMETER SETTINGS

**Experiments for Table 1 & Table 2**

For the baselines, we set the same hyperparameters that are provided by the original papers or the
authors’ github repositories, and we match the results they reported in their respective papers. In our
experiments, we find that the original hyperparameters set by the authors are already well-tuned.

All the models use Adam as the optimizer. GAT sets the initial learning rate as 0.005 and Geom-GCN
uses a custom learning scheduler. All the other models (include GGCN) use the initial learning rate
0.01.

For GGCN, we use the following hyperparameters:

-  k in the decaying aggregation: 3

We tune the parameters in the following ranges:

-  Dropout rate: [0.0, 0.7]

-  Weight decay: [1e-7, 1e-2]

-  Hidden units: {8, 16, 32, 64, 80}

-  Decay rate η: [0.0, 1.5]

**Experiments for Table B.1 and Table B.2**

The hyperparameters that are used in all the models (Base, +deg, +sign, +deg,sign, +BN, +LN)
are set to be the same and they are tuned for every dataset. Those common hyperparameters are:

-  Dropout rate: [0.0, 0.7]

-  Weight decay: [1e-7, 1e-2]

-  Hidden units: {8, 16, 32, 64, 80}


-----

C.2 INITIALIZATION OF PARAMETERS

**Initialization**

For GGCN, we adopt the following parameter initialization in the experiments for Table 1 & Table 2

-  Initialization of λ[l]0 [and][ λ]1[l] [: 0.5 and 0, respectively]

-  Initialization of α[l], β0[l] [,][ β]1[l] [and][ β]2[l] [: 2, 0, 0, 0, respectively.]

We initialize β[l] 0,1,2 [= 0][ in Eq. (6) because, after applying softmax,][ ˆ]β[l] 0,1,2 [= 1][/][3][; this ensures equal]
_{_ _}_ _{_ _}_

contributions from positive and negative neighbors and themselves (and sum=1). We initialize λ[l]1 [= 0]
in Eq. (9) following the common practice for initializing the bias. We set α[l] = 2 and λ[l]0 [= 0][.][5][ in]
Eq. (6) and Eq. (9), because when rij +, the degree correction (including global scaling) is:
_αˆ[l]τij[l]_ [=][ softplus][(2)][ ·][ softplus][(0][.][5][ ·][ (0][ −] [1) + 0)] → _∞[ ≈]_ [1][. As we mention in Thm. 1, when the homophily]
level is high, nodes with large ri may benefit (case 3), thus we do not want to compensate for these
nodes and would like to keep _α[ˆ][l]τij[l]_ [close to 1.]

C.3 PARAMETERS AFTER TRAINING


Figure C.1 shows the original and corrected rij
(avg rij). Corrected rij are given by _α[ˆ][l]τij[l]_ _[r][ij][,]_
which are a combination of global scaling and
local degree correction. Because β{[l] 0,1,2} [sum to]
1 and do not change global scaling, they are not
considered in the corrected rij. As can be seen
in Fig. C.1, after the training, GGCN learns to
increase rij, which satisfies our theorems.

D TABLE 2 WITH LARGER FONTS


Figure C.1: Original rij (avg. rij) and corrected (preand post-training).


-----

-----

