Theoretical and Empirical Insights into the Origins of Degree Bias in Graph Neural Networks
Authors: Arjun Subramonian
Jian Kang
Yizhou Sun
Venue: NeurIPS 2024 poster (2024)
Keywords: graph learning
fairness
degree
Primary area: fairness
TL;DR: We provide an empirically-validated theoretical analysis of the origins of degree bias in message-passing graph neural networks.

Abstract: Graph Neural Networks (GNNs) often perform better for high-degree nodes than low-degree nodes on node classification tasks. This degree bias can reinforce social marginalization by, e.g., privileging celebrities and other high-degree actors in social networks during social and content recommendation. While researchers have proposed numerous hypotheses for why GNN degree bias occurs, we find via a survey of 38 degree bias papers that these hypotheses are often not rigorously validated, and can even be contradictory. Thus, we provide an analysis of the origins of degree bias in message-passing GNNs with different graph filters. We prove that high-degree test nodes tend to have a lower probability of misclassification regardless of how GNNs are trained. Moreover, we show that degree bias arises from a variety of factors that are associated with a node's degree (e.g., homophily of neighbors, diversity of neighbors). Furthermore, we show that during training, some GNNs may adjust their loss on low-degree nodes more slowly than on high-degree nodes; however, with sufficiently many epochs of training, message-passing GNNs can achieve their maximum possible training accuracy, which is not significantly limited by their expressive power. Throughout our analysis, we connect our findings to previously-proposed hypotheses for the origins of degree bias, supporting and unifying some while drawing doubt to others. We validate our theoretical findings on 8 common real-world networks, and based on our theoretical and empirical insights, describe a roadmap to alleviate degree bias.

Theoretical and Empirical Insights into the Origins of Degree Bias in Graph Neural Networks
Arjun Subramonian', Jian Kang", Yizhou Sun' University of California, Los Angeles, University of Rochester jarjun,ub, yzsun @cs.ucla www.ucclaeee jian. kang@rochester. edu
Abstract
Graph Neural Networks (GNNs) often perform better for high-degree nodes than low-degree nodes on node classification tasks. This degree bias can reinforce social marginalization by, e.g., privileging celebrities and other high-degree ac- tors in social networks during social and content recommendation. While re- searchers have proposed numerous hypotheses for why GNN degree bias occurs. we find via a survey of 38 degree bias papers that these hypotheses are often not rigorously validated, and can even be contradictory. Thus, we provide an analysis of the origins of degree bias in passage-passing GNNs with different graph filters. We prove that high-degree test nodes tend to have lower prob- ability of misclassification regardless of how GNNs are trained. Moreover, we show that degree bias arises from a variety of factors that are associated with node's degree (e.g.. homophily of neighbors, diversity of neighbors). Fur- thermore, we show that during training, some GNNs may adjust their loss on low-degree nodes more slowly than high-degree nodes; however, with suffi- ciently many epochs of training, message-passinnn imum possible training accuracy, which is not significantly limited by their ex- pressive power. Throughout our analysis, we connect our findings to previously- proposed hypotheses for the origins of degree bias, supporting and unifying some while drawing doubt to others. We validate our theoretical findings on 8 common real-world networks, and based on our theoretical and empirical in- sights, describe a roadmap to alleviate degree bias. Our code can be found at: github. com Ar junuuramoo htt//degree-baeee biab-iiaabeee bia--exloooationn
GNNs can achieve their max-
Introduction
Graph neural networks (GNNs) have been applied node classification tasks such document topic prediction [4] and content moderation [41]. However, in recent years, researchers have shown that GNNs exhibit better performance for high-degree nodes on node classification tasks. This has significant social implications, such as the marginalization of: (1) authors of less-cited papers when predicting the topic of papers in citation networks; (2) junior researchers when predicting the suitability of prospective collaborators in academic collaboration networks; (3) creators of newer or niche products when predicting the category of products in online product networks: and (4) authors of short or standalone websites when predicting the topic of websites in hyperlink networks.
To illustrate this phenomenon, Figure shows that across different passsagepassingg GNNs (see DD for details about architectures) applied to the CiteSeer dataset (where nodes represent documents and the classification task is predict their topic), high-degree nodes generally incur a lower test loss than low-degree nodes. In practice, if such GNNs are applied to predict the topic of documents in social scientific studies, less-cited documents will be misclassified, which can lead the con-
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

CITESEER
RW
SYM
ATT
1.0
1.0
0.8
0.8
0.8
0.6
Testloss
0.6
Testloss
0.6
+
Teat
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
10000
0.0
30
40
Degree
Degree
Degree
Figure 1: Test loss vs. degree of nodes in CiteSeer for RW, SYM, and ATT GNNs. High-degree nodes generally incur lower loss than low-degree nodes do. Error bars are reported over 10 random seeds; all error bars are I-sigma and represent the standard deviation about the mean.
tributions of their authors not being appropriately recognized and erroneous scientific results. We present additional evidence of degree bias across different GNNs and datasets in SE
Researchers have proposed various hypotheses for why GNN degree bias occurs in node classifica- tion tasks. However, we find via a survey of 38 degree bias papers that these hypotheses are often not rigorously validated, and can even be contradictory ($2). Furthermore, almost prior works degree bias provide a comprehensive theoretical analysis of the origins of degree bias that explicitly links node's degree to its test and training eπror in the semi-supervised learning setting ($2)
Hence, we theoretically analyze the origins of degree bias node classification during test and training time for general message-passien paasgggg-gsinggggg GNNs, with separate parameters for source and target nodes and residual connections. Our analysis spans different graph filter choices: RW (random walk-normalized filter). SYM ssymmetric-normalizer filter), and ATT (attention-based filter) (see SD for formal definitions). particular, we prove that high-degree test nodes tend to have lower probability of misclassification regardless of how GNNs are trained. Moreover, gree bias arises from a variety of factors that are associated with a node's degree (c.g., homophily of neighbors, diversity of neighbors). Furthermore, to RW) may adjust its loss on low-degree nodes more slowly than on high-degree nodes; however, with sufficiently many epochs of training, sessage-passingg GNNs achieve their maximum pos- sible training accuracy, which is only trivially curtailed by their expressive power. Throughout our analysis, connect our findings to
show that de-
show that during training, SYM (compared
hypotheses for the origins of degree bias, supporting and unifying some while drawing doubt to others. We validate our theoretical findings on real-world datasets (see tCCthat commonly used in degree bias papers (see Figure 2 $ Based on our theoretical and empirical insights, we describe a principled roadmap to alleviate degree bias.
2 Background and Related Work
Numerous prior works have proposed hypotheses for why GNN degree bias occurs in node classifi- cation tasks. We summarize these hypotheses in Table 2 based on a survey of 38 non-review papers about degree bias in node classification that cite [55 seminal work on degree bias.
While many of these papers have contributed solutions to degree bias (see A for a thorough overview), we find that their hypotheses for the origins of degree bias are often not rigorously val- idated, and can even be contradictory. For example, some hypotheses locate the source degree bias in the training stage, while others cite interactions between training and test-time factors or purely test-time issues. Moreover, hypothesis (H5) in Table 2 which posits that high- node representations cluster representations have larger variance. In our theoretical analysis of the origins of degree bias, we connect findings to these hypotheses.
strongly, conflicts with and (H10), which argues that high-degree node
We further find that almost no prior works on degree bias provide a comprehensive theoretical anal- ysis of the origins of GNN degree bias that explicitly links node's degree to its test and training

---

Table 1: Five most popular hypotheses for the origins of degree bias proposed by papers. The remaining hypotheses can be found in Table
Hypothesis
Papers
(H1) Neighborhoods of low-degree nodes con- tain insufficient or overly noisy information for effective representations.
34
52
54
65
31
32
35
33
28
55
67
20
666]
[56]
(H2) High-degree nodes have larger influence on GNN training because they have a greater number of links with other nodes, thereby dominating message passing.
45
152
665
22
63
28
62
(H3) High-degree nodes exert more influence on the representations of and predictions for nodes as the number of GNN layers increases.
65
64
(H4) In semi-supervised learning, if training nodes are picked randomly, test predictions for high-degree nodes more likely to be in- fluenced by these training nodes because they have greater number of links with other nodes.
45
63
(H5) Representations of high-degree nodes cluster more strongly around their correspond- ing class centers, or are more likely to be lin- early separable.
39
49
26
error in the semi-supervised learning setting (see Table 3). For example, most works prove that: (a) high-degree nodes have a larger influence on GNN node representations or parameter gradients, or (b) high-degree nodes cluster more strongly around their class centers are more likely to be linearly separable; however, these works do not directly bound the probability of misclassifying node during training
time in terms of its degree.
The few works that do provide a theoretical analysis of degree bias: (A1) perform this analysis with overly strong assumptions, e.g., that graphs sampled from Contextual Stochastic Block Model (CSBM) [T]. or (A2) posit that GNNs do not have sufficient expressive power to map nodes with different degrees distinct representations. However, in the case of (1), for CSBM graphs, the number of nodes n -> 2c, the degrees of nodes in each class concentrate around a constant value, which is contradictory real-world graphs, making CSBM inappropriate model to theoretically analyze degree bias. Moreover, many real-world social networks exhibit a power-law degree distri- bution (3) which is captured by CSBM. In the case of (2), shoos that the accuracy of GNNs on real-world networks is not significantly limited by the Weisfeiler-Leman (WL) test, which draws doubt to hypothesis (H7).
Ultimately, seviiousl--proposee hypotheses for why GNN degree bias occurs lack rigorous valida- tion, and can even be contradictory. To unify and distill these hypotheses, provide analysis of the origins of degree bias in message-passing GNNs with different graph filters.
3 Preliminaries
Throughout our theoretical analysis, we connect our findings previously- proposed hypotheses for the origins of degree bias, supporting and unifying some while drawing doubt to others. We further validate our findings on real-world datasets (see {C) that are commonly used in degree bias papers
rreiiouslyppoooosed
(see Figure 2 $ In all figures (except the PCA plots), error bars are reported over 10 random seeds. The factors of variability include model parameter initialization and training dynamics. All
enror bars are 1 1-sigma and represent the standard deviation (not standard error) of the mean. We

---

implicitly assume that eπrors are
Error bars are computed using Py PyTorh's 's
std function 40 We relegate all proofs to $B
We first introduce relevant notation and assumptions. Suppose we have a C-class node classifica- tion problem defined over undirected connected graph g (V, E) with N |V] nodes. We assume that our graph structure A E {0, 10,1) and node labels Y E No are fixed, but our node features X E N are independently sampled from class-specific feature distributions, i.., Vi E V. Dr. We further have model M that maps A to predictions Ý E I NNC. We use cross-entropy loss function c(M]i, - log Y.,. that computes the loss for node E V with respect to class e for M. Per the semi-supervised learning paradigm (24), we train M with the full graph X, A but only labeled subset of nodes S C
Temt-Time Degree Bias
The test-time degree bias of models important to study, as it can yield disparate performance for low-degree nodes when models are deployed in the real world. We prove that high-degree test nodes tend to have a lower probability of misclassification. Moreover, we show that GNN degree bias arises from variety of factors that are associated with node's degree (c.g., homophily of neighbors, diversity of neighbors). We first present a theorem that bounds the probability of a test node i E V \ S being misclassified. We suppose M is neural network that has L layers. It takes input X, A and generates node representations (1.) NNC these representations are then passed through softmax activation function to get Y (L) softmax (Z()). At this point, we make few assumptions about the architecture M; .M could be a graph neural network (GNN), even MLP logistic regression model.
Theorem 1. Consider test node VVSS, with Y, c. Furthermore, consider label c' + c. Let P (e(M)i, c) > E(Mli,e)) c')) be the probability of misclassifying i. Then, if E (2000 (L) (i.e., M generalizes in expectation):
<0
((((M)i,)) ((Mi, S 1 Ri,d!
(L (1) 2 (1)
where the squared inverse coefficient of variation Ri,e
Var Zice
The assumption that M generalizes in expectation is required for the application of Cantelli's in- equality in the proof. Notably, it is not possible to prove similar lower bound without mak- ing assumptions about the higher-order moments of 2,2) - - The coefficient of variation sid
is a normalized measure of dispersion that is often used in economics to quantify
inequality 13 Thus, R5,2 captures how little Z, varies relative to its expected value. sum- mary, the probability of misclassification P (e(M)i, ((Mli,c')) can be minimized when R is maximized. Intuitively, the probability of misclassification reduced when Z, farther away, in expectation, from the decision boundary that separates classes and c', and has low dispersion. The following subsections reveal why Ri.e' is large when i is high-degree.
4.1 Random Walk Graph Filter
So far, we have made few assumptions about M. Now, we suppose M is a general paassig--passig GNN [16]. In particular, for layer l:
H _ (z()= = o!!)) (H p HL-1) + xW,")
(2)
where ( E R Nxd are the 1-th layer node representations (with H X and (L) C), (!)) is an instance-wist wise non-linearity (with (I.) being softmax), p()) E NxN is a graph filter, and
( ( w pd xd the 1-th layer model parameters.

---

RW
RW
RW
0.15
high degnes nodia
degres nodea
of Lust Iwwpeperntttio contttttiiiaaa
250
Low dwg.ee High- deg.oe modia
2.0
High diggis nodes
digres nodea
0.15
200
1.5
Valting L032
2
0.05
150
100
0.02
0.5-
40-
0.0
450
PC1
Eprchs of training
Epachs of tra hing
SYM
SYM
SYM
0.15
High degnne hodie
Low desree nodes
Jample ceraiiance oftis www.tteeettaaa..
250
High decpeeeeeeeeeee noces
Low degree nodes
2.0
Loar degiee nodes ligh-degree modes
0.10
200
02
0.03
150
Ta-ting
1.0
100
0.02
-0.05
-0.35
-0.10
-0.05
0.10
0is
100
2000
40
60
500
of tust resrruanaaioon cnnuuaiiiss
g 0.05
150
Traliing
1.0
100
0.02
50-
-0.03
0.15
0.3
2.05
0.00 0:05 PC1
0.10
0.55
100
300 Opochs training
200
400
500
20
40
80
300
450
475
500
Spocte of traitan
Figure 2: Visual summary of the geometry of representations, variance of representations, and train- ing dynamics of RW, SYM, and ATT GNNs on CiteSeer. We consider low-degree nodes to be the 100 nodes with the smallest degrees and high-degree nodes to be the 100 nodes with the largest degrees. Each point in the plots in the left column corresponds to test node representation and its color represents the node's class. (In this particular dataset, low-degree nodes are more heavily concentrated in few classes.) The plots in the left column are based single random seed, while the plots in the middle and right columns are based on 10 random seeds. RW representations of low-degree nodes often have larger variance than high-degree node representations, while SYM representations of low-degree nodes often have a smaller variance. Furthermore, SYM generally adjusts its training loss on low-degree nodes less rapidly.
We first consider the special case that VI E Ngz, p()) PIN D- (i.e., the uniform random walk transition matrix), where D the diagonal degree matrix with entries D;, Ejev A.. We further simplify the model by choosing all g()) (1 < L) to be the identity function (e.g., as in (1)). By doing so, we get the following linear jumping knowledge model RW 58
L p' X
H (L) softmax (Z())) softmax
Σ 1=0
is the sum of all the weight terms that correspond to pi in Eqn. 2 for simplicity, we collapse each sum of weight terms into single weight matrix. It is still reasonable to have a different weight matrix ( for each term P X, as we may need to extract different information from features aggregated from neighborhoods at different hops. For each model M, .M denotes the linearized version of the model that theoretically analyze. Linearizing GNNs is a common practice in the literature [17 39).
where vl E Ng1. ( E xC W
ru
We now prove lower bound for Rice. By identifying nodes for which this lower bound is larger, we can indirectly figure out which nodes have a lower probability of misclassification In particular, find that the bound is generally larger for high-degree nodes, which sheds light the origins of degree bias. For simplicity of notation, we denote the weights corresponding to the decision boundary of the (-th term that separates classes and c' by w w/o w w and (V to
5

---

be the distribution over the terminal nodes of length-/ uniform random walks starting from node i.
We further define:
P By) (EaDyy x cc
(4)
as the 1-hop prediction homogeneity of i with respect to d' when Y; = c. essence, Ba, x= " - captures the expected prediction score of w (1) w for node j whose features X3 D when Ex-Dy,
x 1 [ is more negative on average, w predicts j to belong to class with higher likelihood. Thus, 3 measures the expected prediction score for nodes j. weighted by their probability of being reached by length-/ random walk starting from i.
From topological perspective, because _ depends the distribution of random walks from is intimately related to local graph structure. Indeed, 3/ can be interpreted "local subgraph difference" and is highly influenced by the local homophily of i. However, 8/ also influenced by the presence of (-hop neighbors contained in the training set, as the model more likely to correctly
classify these nodes by a large margin; hence, ( does not only boil down to local homophily. We discuss other connections between prediction homogeneity, homophily, and separability $A.4
In addition to the (-hop prediction homogeneity, we denote the l-hop collision probability by:
(5)
Iw
JEV
which quantifies the probability of two length-/ random walks starting from i colliding at the same end node j. When the collision probability is lower, random walks starting from i have higher likelihood of ending at distinct nodes; in effect, the random walks can be considered to be more diverse.
Theorem 2. Assume that vl E Ngg. Vj E V, Var VaraWDy x u (1) & M. Then:
EE 8002
R 2 M(L Et (1)
(6)
We observe that to make Ri,e' larger, and thus minimize the probability of misclassification, it is sufficient (although not necessary) that the inverse collision probability Et. (")
1 is larger. When = Di +T which is larger for high-degree nodes. We find empirically that the
13 14p. (We elaborate on connections between the inverse collision probability and node degree SK
inverse collision probability is positively associated with node degree (see Figures
3
Further- more, disparities in the inverse collision probability across nodes with different degrees Is reduced by residual connections and increased by self-loops. Intuitively, random walks starting from high- degree nodes diffuse more quickly, maximizing the probability of any two random walks not collid- ing the same end node; in this way, a higher inverse collision probability indicates more diverse and possibly informative L-hop neighborhood. This finding supports hypothesis (H1) (see (able()).
Additionally, make Ri, larger, it is sufficient that for all ( NcL. 8.0 is more negative, c.g., when most nodes in the h-hop neighborhood of i predieted belong class Thus, s{(2 can be more negative when nodes in the h-hop neighborhood of also are in class (i.e., node has high local homophily) and were part of the training set S, leading to them being correctly classified. This finding supports hypotheses (H4) and (H6). Notably, cannot make Σ 3.) more positive to increase Rg,er; this would violate the assumption of Theorem 2 that the model generalizes in expectation, which is necessary to make a mathematically rigorous statement about degree bias via tail bounds. Intuitively, it also would not make sense that RW and SYM reduce the misclassification enror for node by predicting its neighbors to be of different class, since message passing smooths the representations of adjacent nodes. Moreover, distribution shifts in local homophily from train to

---

CITESEER SYM
RW
ATT
0.9
Inverse collision probability
Inverse collision probability
20
0.7-
15
0.7
collsion
0.6
0.5
10-
0.5
0.4
0.3-
0.3
0
10
20
30
40
0
10
20
30
40
10
20
30
40
Degree
Degree
Degree
Figure 3: Inverse collision probability vs. degree of nodes in CiteSeer for RW, SYM, and ATT GNNs. Node degrees generally have a strong association with inverse collision probabilities.
test time can reduce test-time prediction performance, bringing Pi. closer to this can increase Ri,e', thereby not inducing much degree bias at the expense of overall test performance.
Furthermore, our proof of Theorem (Eqn. 21 reveals that in expectation, the linearized model RW produces similar representations for low and high-degree nodes with similar L-hop neighborhood homophily levels. However, low-degree nodes (specifically nodes with lower inverse collision probability) tend to have a higher variance in RW's representation space than high-degree nodes do (Eqn. 24 This entails that factors beyond homophily (e.g.. diversity of neighbors) induce degree bias. We validate these findings empirically in Figure 2and and { Figure 2 we see the left plot in the RW row (first row) that low-degree test nodes have representations that are similarly centered but more spread out in the first two principal components of all the test representations than high-degree nodes; confirm that low-degree node representations have larger variance in the middle plot in the RW row. Thus, regardless of how RW trained, low-degree nodes have a higher probability of being the wrong side of RW's decision boundaries. Indeed, the left plot in the RW row shows that low-degree nodes of a certain class end up closer to nodes of different class at a higher rate. Notably, this occurs even when RW relatively shallow (i.e., layers). Thus, this finding supports hypothesis (H5), as well as draws doubt to hypotheses (H3) and (H10). Our results for RW may also hold for ATT when low-degree nodes are generally less attended to since like random walk transition matrices, attention matrices are row-stochastic.
4.2 Symmetric Graph Filter
We now consider the special case that V/ E Ngt, P()) Paym D AADD simplify M by making all g()) the identity function, getting SYM:
We once again
H (L) softmax (z() softmax
Σ pl sym xw
We define:
310 Ba~NO()
DDj ExNDy,
x W
(8)
as the degree-discounted l-hop prediction homogeneity. Similar to B.et Pee measures the expected prediction score for nodes j. but weighted by the inverse square root of their degree in addition to their probability of being reached by length-l random walk starting from i. In effect, 300 more heavily discounts the prediction scores for high-degree nodes. We also denote the degree-discounted sum of collision probabilities by:
Σ JEV
(P' (P
12
Djs
7

---

where each summation term (PL) quantifies the probability of two length-/ random walks starting from i ending at j and is discounted by the degree of j. Compared to the random walk setting, the the contributions of high-degree nodes. We now prove a lower bound for Ri for SYM.
ky
prediction homogeneity and sum of collision probabilities suppress
(1) x F
Theorem 3. Assume that vI E NeL. Vj E V, VaranDy,
S M. Then:
El 302 M(L + 1) Eio a
R
(10)
Once again, we observe that Ri is larger, and thus the probability of misclassification is minimized, is larger and for all
when the inverse Slegree-discounted sum of collision probabilities Σl a.
1
1 E Ngt, the (degree-discouuteed) I-hop prediction homogeneity Be is more negative. Like for RW, these findings support hypotheses (H1), (H4), and (H6) (see Table 2
Furthermore, our proof of Theorem 3 (Eqn. 33 reveals that in expectation, SYM often produces
representations for low-degree nodes that lie closer to SYM's decision boundary than representations of high-degree nodes with similar L-hop neighborhood homophily levels. This is because SYM produces node representations that are approximately scaled by the square root of the node's 's degree. However, for the same reason, unlike for RW, low-degree nodes tend to have a lower variance in SYM's representation space than high-degree nodes do (Eqn. 36); this corroborates the findings of [1]. We validate this empirically in Figure 2 and $ on the homophilic datasets (i.c., all datasets except chameleon and squirrel). In Figure 2 we see in the left plot the SYM row (second row) that low-degree test nodes (particularly low- low-degree nodes with many high-degree nodes in their L-hop neighborhood) have representations that are closer SYM's decision boundaries but less spread out in the first two principal components of all the test representations than high-degree nodes; we confirm that low-degree node representations have smaller or comparable variance the middle plot in the SYM row. We emphasize that while SYM representations of high-degree nodes have a higher variance, this itself is not the cause of degree bias; since the standard deviation and expectation of SYM node representations are approximately scaled by the same factor, by Theorem I. the variance of SYM representations of high-degree nodes does not enlarge Ri,c' noticeably more than in the RW case.
Notably, our theoretical findings do extend to heterophilic graphs. particular, high-degree nodes in heterophilic networks (e.g., chameleon and squirrel) do not have higher negative L-hop prediction homogeneity levels due higher local heterophily (see } and hence we do not necessarily observe better test performance for them (see Figure 5). None of our theoretical analysis assumes homophilic networks.
Ultimately, like for RW, low-degree nodes (specifically nodes with a lower inverse collision proba- bility) have larger probability of being on the wrong side of SYM's decision boundaries (regardless of how SYM is trained). Indeed, low-degree nodes of certain class end up closer to nodes of a dif- ferent class higher rate. Notably, this occurs even when SYM is relatively shallow (i.e., layers). Thus, this finding supports hypothesis (H5), and draws doubt to hypotheses (H3), (H7), and (H10).
5 Training-Tiin Time Degree Bias
We show that during training, SYM (compared to RW) may adjust its loss on low-degree nodes more slowly than on high-degree nodes. This finding important because as GNNs are applied to increasingly large networks, only a few epochs of training may be possible due to limited compute; as such, we must ask: which nodes receive superior utility from limited training? Even though we know the labels for training nodes, GNNs may serve as an efficient lookup mechanism for training nodes deployed systems; thus, if partially-trained, GNNs can perform poorly for low-degree training nodes. We also empirically demonstrate that despite learning at different rates for low vs. high-degree nodes, message-passing GNNs (even those with static filters) can achieve their maximum possible training accuracy, which is not significantly curtailed by their expressive power.

---

We first demonstrate that during each step of training of SYM with gradient descent, the loss of low-degree nodes is adjusted more slowly than high-degree nodes. We consider the setting that, for all I E Ngt. at each training step t:
deit] W +1 (( - (0
Mawoy
(B(t))
(11)
where W is W at training step t, 1) is the learning rate, E|(] is the model's loss at t, and Bit) S (where S the labeled subset of nodes) is the batch used at step t.
[t] to be 2,th at timestep t. We begin by proving the following lemma, which states that for any model M, (it((M)i,)) c) (for all t) is X-Lipschitz continuous with respect to Z!")tt
Consider a node i E V. with Y = c. We define z
Lemma 1. For all t, {[](MM],,c) c) is X-Lisschitz continuous with respect to z [t] with constant 22, that is:
lett 11+1] ((
(MMM c)l < - (t Z,
(12)
Now, we move to the main theorem where we bound the change in loss after an arbitrary training step t (regardless of batching paradigm) in terms of its degree. We denote the resid- ual of the predictions of SYM at step by c[t] = [t] - onehot (Y(t)), where H [t] and onehot (t) are the submatrices formed from the rows of H and onehot (Y), respectively, that correspond to the nodes in B[4]- Furthermore, we denote VI E Ngt. the expected similar- ity of the neighborhoods of and B(t] by x!" [R where for E B(t), (xi" 1t) m
DEy x Specifically, (x."1t) captures the degree- discounted expected similarity between the raw features of nodes j and & with respect to the l-hop random walk distributions of V and m E B(I.. Notably, our matrix is pre-feature aggregation (e.g., unlike (37).
D mm (1),)
Theorem 4, The change in loss for after an arbitrary training step t obeys:
(MMMs) S Da. [2 E1
|e[e + 11(55 -
(13)
As observed, the change (either increase or decrease) in loss for i after an arbitrary training step has a smaller magnitude if is low-degree. Thus, when Elt + (JSMMM),, c) < {[t[SSYM)i.) (e.g., i B(t)), the loss for decreases more slowly when i low-degree. In effect, because the magnitude of SYM node representations is positively associated with node degree while the magnitude of each gradient descent step is the same across nodes, the representations of low-degree nodes experience a smaller change during each step. We additionally notice that the loss for changes more slowly when the features of nodes in its L-hop neighborhood are not similar the features in the L-hop
neighborhoods of the nodes in each training batch (i.e., El {
is small). Because the L- hop neighborhoods of low-degree nodes tend to be smaller than those of high-degree nodes, their neighborhoods often have less overlap with the neighborhoods of training nodes, which can further constrain the rate at which the loss for i changes. Notably, while node degree highly affects the rate of learning, differences in across nodes due to factors other than degree are also influential.
[11]
We confirm these findings empirically in Figure 2 and { For all the datasets, when training SYM, the blue curve (i.e., the loss for low-degree nodes) has less steep rate of decrease than the orange curve (i.c., the loss for high-degree nodes) as the number of epochs increases. For example, in Figure 2 in the case of RW and ATT, the training loss curves for low and high-degree nodes (including error bars) overlap during the first ~ 20 epochs of training. However, for SYM, the loss curve for high- degree nodes descends more rapidly than the curve for low-degree nodes. These findings support hypothesis (H2) (c.f. Table
In H we demonstrate that during each step of training RW with gradient descent, compared to SYM, the loss of low-degree nodes in S is not necessarily adjusted more slowly. Furthermore,

---

in L we empirically show that SYM (despite learning at different rates for low vs. high-degree nodes), RW, and ATT can achieve their maximum possible training accuracy, which is often close to 100%; this indicates that expressive power does not significantly limit the accuracy of these models in practice and draws doubt to hypothesis (H7).
6 Principled Roadmap to Address Degree Bias
The primary aim of this work is to explore and explain the origins of GNN degree bias, which lacks a principled understanding. Future research can build on the strong theoretical and empirical foun- dation laid by this paper to propose alleviation strategies for degree bias. In particular, our findings reveal that any alleviation strategies should target the following theoretically-jussffeed criteria, which have empirically validated 8 real-world datasets:
Maximizing the inverse collision probability of low-degree nodes (e.g., via edge augmenta- tion for low-degree nodes). Figure the plots in Section Shsoww strong positive associations between inverse collision probability and degree for the RW, SYM, and ATT filters, and Figure and the plots in Section show strong negative associations between degree and test loss for the homophilic datasets. Hence, validate that higher inverse collision probability is associated with lower test loss, as our theory predicts.
Increasing the L-hop prediction homogeneity of low-degree nodes (e.g.. by ensuring similar label densities in the neighborhoods low and high-degree nodes). The lack of degree bias observed in Figure 5 for chameleon and squirrel (which are heterophilic networks), compared to Figure T and the plots in Section confirms our theoretical finding that under heterophily, the prediction homogeneity for high-degree nodes is closer to 0, high-degree nodes do not necessarily experience better performance.
Minimizing distributional differences (e.g., differences in expectation, variance) in the rep- resentations of low and high-degree nodes. Figures 2 and 60 empirically confirm our the- oretical finding that disparities in the expectation and variance of node representations sponsible for performance disparities. Figures IT and 12 suggest that smaller distributional dif- ferences among representations (due to heterophily) can alleviate degree bias.
Reducing training discrepancies with regards to the rate at which GNNs learn for low vs. high-degree nodes. Figure 2 and the plots in Section F validate our theoretical finding that SYM adjusts its loss on low-degree nodes more slowly than on high-degree nodes (see 5)
These criteria are important because they reflect (to large extent) inherent fairness issues with the graph filters that are popular in graph learning. For instance, the random walk and symmetric filters disadvantage low-degree nodes by yielding representations with high variance and low magnitude, respectively. It is valuable for graph learning practitioners to investigate filters that are adaptive or not restricted to the graph topology in a way that ensures that low-degree nodes are not marginalized through disparate representational distributions poor neighborhood diversity.
7 Conclusion
Our theoretical analysis aims to unify and distill previousty-proposed hypotheses for the origins of GNN degree bias. We prove that high-degree test nodes tend have lower probability of misclassification and that degree bias arises from a variety of factors associated with a node's degree (c.g., homophily of neighbors, diversity of neighbors). Furthermore, we show that during training, some GNNs may adjust their loss on low-degree nodes more slowly; however, GNNs often achieve their maximum possible training accuracy and are trivially limited by their expressive power. We validate our theoretical findings on 8 real-world networks. Finally, based on our theoretical and empirical insights, we describe roadmap to alleviate degree bias. More broadly, we encourage research efforts that unveil forms of inequality reinforced by GNNs. We detail the limitations and possible future directions of our work in L including our survey, theoretical analysis (e.g., focusing on linearized GNNs, node classification), empirical validation (e.g., exploring degree bias in the inductive learning setting and heterogeneous and directed networks), and roadmap. We additionally discuss broader impacts in M
10

---

Acknowledgments and Disclosure of Funding
This work was partially supported by NSF 2211557, NSF 1937599, NSF 21 21196,3, NSF 2303037, NSF 2312501, NASA, SRC JUMP 2.0 Center, Amazon Research Awards, and Snapchat Gifts.

---

References
[1] Ben Adlam and Jeffrey Pennington. The neural tangent kernel in high dimensions: Triple descent and multi-scale theory of generalization. In Hal Daumé III and Aarti Singh, edi- tors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 74-84. 84. PMLR, 13-18 Jul 2020.
[2] Chirag Agarwal, Himabindu Lakkaraju and Marinka Zitnik#. Towards a unified framework for fair and stable graph representation learning. 2021.
[3] Albert-Láázih Barabási. Network science. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 371, 2016.
[4] Alcksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsu- pervised inductive learning via ranking. In International Conference on Learning Representa- lions, 2018.
[5] Stephen Bonner, Ufuk Kirik, Ola Engkvist, Jian Tang, and Ian P Barrett. Implications of topologiaal imbalance for representation learning biomedical knowledge graphs. Briefings in Bioinformatics, 23(5):bbac279, 07 2022.
[6] Jiajia Chen, Jiancan Wu, Jiawei Chen, Xin Xin, Yong Li, and Xiangnan He. How graph convolutions amplify popularity bias for recommendation? Frontiers of Computer Science, 18(5), December 2023.
[7] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In Hal Daumé III and Aarti Singh. editors. Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pages 1725-1735. PMLR, 13-18 Jul 2020.
[8] Renyao Chen, Junye Lei, Hong Yao, Tailong Li, and Shengwen Li. Anchor-enhanced geo- graphical entity representation learning. IEEE Transactions on Neural Networks and Learning Systems, pages 1-15, 2023.
[9] Zhengyu Chen, Teng Xiao, and Kun Kuang. Ba-gnn: On learning bwar- graph neural network. In 2022 IEEE 38th International Conference on Data Engineering (ICDE), pages 3012-3024, 2022.
[10] Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, vol- ume 31. Curran Associates, Inc., 2018.
[11] Wei Ding, Jiawei Sun, Jie Li, and Chentao Wu, Inductive dummy-based homogeneous neigh- borhood augmentation for graph collaborative filtering. In 2023 International Joint Conference on Neural Networks (IJCNN), pages 1-8, 2023.
[12] Claire Donnat and So Won Jeong. Studying the effect of GNN spatial convolutions the embedding space's s geometry. In Robin J. Evans and Ilya Shpitser, editors, Proceedings of the Thirty-Nimth Conference Uncertainty in Artificial Intelligence, volume 216 of Proceedings of Machine Learning Research, pages 539-548. PMLR, 31 Jul-04 Aug 2023.
[13] Brian Everitt. The Cambridge dictionary of statistics. Cambridge University Press, Cambridge, UK; New York, 2002.
[14] Fuli Feng, Weiran Huang, Xiangnan He, Xin Xin, Qifan Wang, and Tat-Seng Chua. Should graph convolution trust neighbors? a simple causal inference method. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Re- trieval, SIGIR 21, page 1208-1218, New York, NY, USA, 2021. Association for Computing Machinery.
[15] Matthias Fey and Jan F. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[16] Francesco Di Giovanni, James Rowbottom, Benjamin Paul Chamberlain, Thomas Markovich, and Michael M. Bronstein. Understanding convolution on graphs via energies. Transactions on Machine Learning Research, 2023.
[17] William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the s International Conference on Neural Information Processing Systems, NIPS 17, page 1025-1035 Red Hook, NY, USA, 2017. Curran Associates Inc.
12

---

[18] Haoyu Han, Xiaorui Liu, Feng Shi, MohamadAli Torkamani, Charu C. Aggarwal, and Jiliang Tang. Towards label position bias in graph neural networks. In Thirty-sevent Conference on Neural Information Processing Systems, 2023.
[19] Xiaotian Han, Kaixiong Zhou, Ting-Hsiang Wang. Jundong Li, Fei Wang, and Na Zou. Marginal nodes matter: Towards structure fairness in graphs, 2023.
[20] Van Thuy Hoang and O-Joun Lee. Mitigating degree biases in message passing mechanism by utilizing community structures, 2023.
[21] Mingxuan Ju, Tong Zhao, Wenhao Yu, Neil Shah, and Yanfang Ye. Graphpatcher: Mitigating degree bias for graph neural networks via test-time augmentation. In I'hirty-seventh Conference on Neural Information Processing Systems, 2023.
[22] Jian Kang, Yan Zhu, Yinglong Xia, Jiebo Luo, and Hanghang Tong. Rawlsgen: Towards rawlsian difference principle graph convolutional network. In Proceedings of the ACM Web Conference 2022, WWW '22, page 1214-1225, New York, NY, USA, 2022. Association for Computing Machinery.
[23] Diederík P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. CoRR, abs/1412.6998 2014.
[24] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2017.
[25] Peizhao Li, Yifei Wang. Han Zhao, Pengyu Hong. and Hongfu Liu. On dyadic fairness: Ex- ploring and mitigating bias in graph connections. In International Conference on Learning Representations, 2021.
[26] Ting Wei Li, Qiaozhu Mei, and Jiaqi Ma. A metadata-driven approach to understand graph neural networks. In Seirth-seventh Conference on Neural Information Processing Systems, 2023.
[27] Xueqi Li, Guoqing Xiao, Yuedan Chen, Zhuo Tang, Wenjun Jiang, and Kenli Li. An explicitly weighted gen aggregator based on temporal and popularity features for recommendation. ACM Trans. Recomm. Syst., 1(2), apr 2023.
[28) Langzhang Liang, Zenglin Xu, Zixing Song, Irwin King, Yuan Qi, and Jieping Ye. Tackling long-tailed distribution issue in graph neural networks via normalization. IEEE Transactions on Knowledge and Data Engineering, pages --1,,022.
[29] Jie Liao, Jintang Li, Liang Chen, Bingzhe Wu, Yatao Bian, and Zibin Zheng. Sailor: Struc- tural augmentation based tail node representation learning. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, CIKM '23, page 1389-1399, New York, NY, USA, 2023. Association for Computing Machinery.
[30] Ningyi Liao, Haoyu Liu, Zulun Zhu, Siqiang Luo, and Laks V. S. Lakshmanan. Benchmarking spectral graph neural networks: A comprehensive study on effectiveness and efficiency, 2024.
[31] Songtao Liu, Rex Ying, Hanze Dong, Lanqing Li. Tingyang Xu, Yu Rong, Peilin Zhao, Jun- zhou Huang. and Dinghao Wu. Local augmentation for graph neural networks. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, edi- tors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 4054-14072 PMLR, 17-23 Jul 2022.
[32] Yazheng Liu, Xi Zhang, and Sihong Xie. Trade less accuracy for faireess and trade-off ex- planation for gnn. In 2022 IEEE International Conference Big Data (Big Data), pages 4681-4690, 2022.
[33] Zemin Liu, Yuan Fang, Wentao Zhang, Xinming Zhang, and Steven C.H. Hoi. Locality-aware tail node embeddings on homogeneous and heterogeneous networks. IEEE Transactions on Knowledge and Data Engineering, pages 1-16, 2023.
[34] Zemin Liu, Trung-Kien Nguyen, and Yuan Fang. Tail-gnn: Tail-node graph neural networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, KDD '21 page 1109-11 19, New York, NY, USA, 2021, Association for Computing Machin- ery.
13

---

[35] Zemin Liu, Trung-Kien Kien Nguyen, and Yuan Fang. On generalized degree faimess in graph neural networks. In Proceedings of the Thirty-Svvntth AAAI Conference on Arti- ficial Intelligence and Thirty-Fii Fifth Conference on Innovative Applications of Artificial In- telligence and Thirteenth Symposium on Educational Advances Artificial Intelligence, AAAI23/AAA/22/AAATTTS AAAI Press, 2023.
[36] L. Lovász. Random walks on graphs: A survey. In D. Miklós, T. Sós, and T. Szōnyi, editors, Combinatorics, Paul Erdős is Eighty, volume 2, pages 353-398. János Bolyai Mathematical Society, Budapest, 1996.
[37] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao- Wen Chang, and Doina Precup. Revisiting heterophily for graph neural networks. Advances in neural information processing systems, 35:1362-1333 1375, 2022.
[38] Sitao Luan, Chenqing Hua, Minkai Xu, Qincheng Lu, Jiaqi Zhu, Xiao- Xiao-Wen Chang, Jie Fu, Jure Leskovec, and Doina Precup. When do graph neural networks help with node classification? investigating the homophily principle on node distinguishability. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[39] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? In International Conference on Learning Representations, 2022.
[40] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang. Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, Biigh-Performnnce Deep Learning Library. Curran Associates Inc., Red Hook, NY, USA, 2019.
[41] Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-Scale attributed node embedding. Journal of Complex Networks, 9(2)cnnab014, 05 2021.
[42] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. ArXiv, abs/ 181 1.05868, 2018.
[43] Harry Shomer, Wei Jin, Wentao Wang. and Jiliang Tang. Toward degree bias in embedding- based knowledge graph completion. In Proceedings of the ACM Web Conference 2023, WWW "23, page 705- 7155715,,6 New York, NY. USA, 2023. Association for Computing Machinery.
[44] Arjun Subramonian, Levent Sagun, and Yizhou Sun. Networked inequality: Preferential at- tachment bias in graph neural network link prediction. In NeurIPS 2023 Workshop: New Frontiers in Graph Learning, 2023.
[45] Xianfeng Tang, Huaxiu Yao, Yiwci Sun, Yiqi Wang. Jiliang Tang, Charu Aggarwal, Prasenjit Mitra, and Suhang Wang. Investigating and mitigating degree-related biases in graph convol- tuional networks. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, CIKM '20 page 1435-1444, New York, NY, USA, 2020. Associa- tion for Computing Machinery.
[46] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Rep- resentations, 2018.
[47] Srinivas Virinchi and Anoop Saladi. Blade:
Biased neighborhood sampling based graph neural network for directed graphs. Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, WSDM '23, page 42-50, New York, NY, USA, 2023, Asso- ciation for Computing Machinery.
[48] Junfu Wang, Yuanfang Guo, Liang Yang. and Yunhong Wang. Understanding heterophily for graph neural networks. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp. editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 50489-50529, PMLR, 21-27 Jul 2024.
[49] Ruijia Wang, Xiao Wang, Chuan Shi, and Le Song. Uncovering the structural fairness in graph contrastive learning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
14

---

[50] Chunyu Wei, Jian Liang, Di Liu, Zehui Dai, Mang Li, and Fei Wang. Meta graph learning for long-tail recommendation. In Proceedings of the 29th ACM SIGKDD Conference on Knowl- edge Discovery and Data Mining, KDD '23, page 2512-2522, New York, NY, USA, 2023. Association for Computing Machinery.
[51] Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr. au2, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks, 2019.
[52] Jiancan Wu, Xiang Wang. Fuli Feng, Xiangnan He, Liang Chen, Jianxun Lian, and Xing Xie. Self-supervisce graph learning for recommendation. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '21, page 726-735, New York, NY, USA, 2021. Association for Computing Machinery.
[53] Jun Wu, Jingrui He, and Jiejun Xu. Demo-net: Degree-specific graph neural networks for node and graph classification. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '19, page 406-415, New York, NY, USA, 2019. Association for Computing Machinery.
[54] Teng Xiao, Zhengyu Chen, Donglin Wang. and Suhang Wang. Learning how to propagate messages in graph neural networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, KDD '21, page 1894-1903, New York, NY, USA, 2021. Association for Computing Machinery.
[55] Hui Xu, Liyao Xiang. Femke Huang, Yuting Weng, Ruijie Xu, Xinbing Wang, and Chenghu Zhou, Grace: Graph self-distillation and completion to mitigate degree-related biases. In Pro- ceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '23, page 2813-28244 New York, NY, USA, 2023, Association for Computing Machin- cry.
[56] Jianan Xu, Jiajin Huang, Jianwei Zhao, and Jian Yang. Hynef: A hybrid normalization strategy via feature statistics for collaborative filtering. Expert Systems with Applications, 238: 121875, 2024.
[57] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
[58] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe. Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5453- 5462. PMLR, 10-15 Jul 2018.
[59] Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. In 2022 IEEE International Conference on Data Mining (ICDM), pages 1287-1292, 2022.
[60] Sukwon Yun, Kibum Kim, Kanghoon Yoon, and Chanyoung Park. Lte4g: Long-tail experts for graph neural networks. In Proceedings of the 3t ACM International Conference Infor- mation & Knowledge Management, CIKM '22, page 2434-2443, New York, NY, USA, 2022. Association for Computing Machinery.
[61] An Zhang, Wenchang Ma, Xiang Wang, and Tat-Seng Chua. Incorporating bias-aware margins into contrastive loss for collaborative filtering. Advances in Neural Information Processing Systems, 35:7866-7878, 2022.
[62] Guixian Zhang, Debo Cheng, Guan Yuan, and Shichao Zhang. Learning fair representations via rebalancing graph structure. Information Processing & Management, 61 2024.
[63] Guixian Zhang, Rongjiao Liang, Zhongyi Yu, and Shichao Zhang. Rumour detection on social media with long-tail strategy. In 2022 International Joint Conference on Neural Networks (JCNN). pages 1-8, 2022.
[64] Guixian Zhang, Shichao Zhang, and Guan Yuan. Bayesian graph local extrema convolution with long-tail strategy for misinformation detection. ACM Trans. Knowl. Discov. Data, jan 2024. Just Accepted.
[65] Minghao Zhao, Qilin Deng, Kai Wang, Runze Wa, Jianrong Tao, Changjie Fan, Liang Chen, and Peng Cui. Bilateral filtering graph convolutional network for multi-relational social rec- ommendation in the pawer-law networks. ACM Trans. Inf. Syst., 40(2), sep 2021.
15

---

[66] Mingxia Zhao and Adele Lu Jia. Dahgn: Degree-aware heterogeneous graph neural network. Knowledge-Baat Baseed Systems, 285:111355, 2024.
[67] Jiangqiang Zhu, Kai Li, Jinjia Peng, and Jing Qi. Self-supervised graph attention collaborative filtering for recommendation. Electronics, 12(4), 2023.
[68] Markus Zopf. 1-wl expressiveness is (almost) all you need. In 2022 International Joint Con- ference Neural Networks (IJCNN), pages 1-8. IEEE, 2022.
16

---

Appendix
Table of Contents
A Overview of Hyppttheses for, Theoretical Analyses of, and Proposed Solutions to De-
gree Bias
18
A.
Hypotheses for Degree Bias
18
A.2
Theoretical Analyses of Degree Blas
19
A.3
Proposed Solutions Degree Bias
19
Degree Bias from the Perspectives of Homophily and Topology
20
B
Proofs
21
B.
Theorem
21
B.2
Theorem
22
B.3
Theorem
23
4
Lemmal
24
Theorem
25
B.6
Theorem
26
C
Datasets
27
Models
28
Additional Degree Bias Plots
29
F
Additional Visual Summaries of Theoretical Results
31
G Additional Inverse Collision Probability Plots
35
Training-Time Degree Bias: Random Walk Graph Filter
37
Achieving Maximum Training Accuracy
38
Additional Training Loss Plots
39
K
Connecting Inverse Collision Probability to Node Degree
42
Limitations and Future Directions
43
Survey
43
Theoretical analysis
43
Empiriaal validation
43
Principled roadmap
43
M Broader Impacts
45
17

---

A Overview of Hypotheses for, Theoretical Analyses of, and Proposed Solutions to Degree Bias
A.1 Hypotheses for Degree Bias
Table Full taxonomy of the hypotheses for the origins of GNN degree bias proposed by papers.
Hypothesis
Papers
(HI) Neighborhoods of low-degree nodes con- tain insufficient or overly noisy information for effective representations.
65
33
21
19
28
55
56
(H2) High-degree nodes have a larger influence on GNN training because they have greater number of links with other nodes, thereby dominating message passing.
45
52
665
22
28
(H3) High-degree nodes exert influence on the representations of and predictions for nodes as the number of GNN layers increases.
(H4) In semi-supervised learning, if training nodes are picked randomly, test predictions for high-degree nodes are more likely to be in- fluenced by these training nodes because they have a greater number of links with other nodes.
(H5) Representations of high-degree nodes cluster more strongly around their correspond- ing class centers, more likely to be lin- early separable.
39
49
26
(H6) Neighborhoods of high-degree nodes contain more homophilic links, enhancing their representations.
29
55
(H7) Nodes with different degrees not essarily mapped to distinct representations.
53
(H8) Low-degree nodes have class-imbalanced training samples, yielding worse generaliza- tion.
60
(H9) High-degree nodes are more likely to be labeled during training and thus GNNs gener- alize better for them.
9
(H10) Representations of high-degree nodes have higher variance.
28
(HI1) Low-degree nodes are more likely to be sampled during training/inferenee.
18

---

A.2 Theoretical Analyses of Degree Bias
taxonomy of GNN degree bias papers based on whether they theoretically analyze the origins of degree bias, explicitly linking node's degree to its test and training error.
Table 3:
Explicit theoretical analysis of origins of degree bias?
Papers
Yes No
53
39
26
45
34
52
54
14
65
49
31
22
600
661
99
13 27
32
28
36
3.6
21
29
18
6
19]
(55]
[50
67
20
62
66
[56
64
A.3 Proposed Solutions to Degree Bias
One line of research has produced neighborhood augmentation strategies. For example, 33 per- form feature-ant adaptive neighborhood translation from high-degree nodes to cencttrrlll-limitee low- degree nodes to enhance their representations. [52] generate multiple views of node neighborhoods (e.g., via node and edge dropping) and learn to maximize ferent views, towards improving the robustness of low-degree node representations. [2]] patch the ego-graphs of low-degree nodes by generating virtual neighbors.
similarity of representations dif-
(55] self-distill graphs and com- plete the neighborhoods of low-degree nodes with more homophilic links. Other methods include:
67 and [66] generate multiple views node neighborhoods (c.g., g., via node and edge dropping) and learn maximize the similarity of representations of different views, towards improving the robustness of low-degree node representations.
49 interpolate additional links for low-degree nodes and purify links for high-degree nodes to balance neighborhood information across nodes with different degrees.
generate more samples in the local neighborhoods of low-degree nodes, to augment the information in these neighborhoods.
31
leverage Transformer architecture and contrastive learning with augmentations (e.g., via node and edge dropping) to bolster the influence of low-degree nodes during training.
163
augment the neighborhoods of low-degree nodes in knowledge graphs with synthetic triples.
augment the local structure of low-degree nodes by adding homophilic edges.
generate contextually-depeddee neighborhoods based on node's degree.
50
contribute meta-learning strategy to generate additional edges for low-degree nodes.
introduce dummy nodes connected to all the nodes in the graph to improve message passing to low-degree nodes.
introduce learnable graph augmentation strategy connect low-degree nodes via more within-community edges, as well as an improved self-ateention mechanism.
20
Another line of research has produced algorithms that normalize graph filters or node representations to minimize distributional differences between the representations of nodes with different degrees. [22] propose pre-processing and in nn-processing approaches that re-normalize the graph filter to be doubly stochastic. (56) calculate node representation statistics via hybrid strategy and use these statistics to normalize representations. (28) normalize the representations low-degree and high- degree nodes to have similar distributions.
different line of research has produced algorithms that separate the learning process for high and low-degree nodes. [53] embed degree-specifis weights and hashing functions within the layers of
GNNs that guarantee degree-aware node representations. (45) propose a degree-specific GNN layer,
to avoid parameter sharing across nodes with different degrees, and a Bayesian teacher network that
generates pseudo-labeled neighbors for low-degree nodes increase their proximity labels. (60)
learn separate expert models for high and low-degree nodes with class and degree-balancee data
19

---

subsets, and distill the knowledge of these experts into two student models that are tailored to low and high-degree nodes.
There exist yet other solutions (e.g., based on adversarial learning, attention) that have been pro- duced. 35 learn debiasing functions that distill and complement the GNN encodings of high and low-degree nodes, respectively. (33] leverage meta-lcarning to learn to learn representations for low-degree nodes in a locality-awar manner. [18] propose a label proximity score, which they find to be more strongly associated with performance than degree, and learn a new graph structure that reduces discrepancies label proximity scores across nodes. [64] leverage an attention mechanism to enhance focus on low-degree nodes. Other methods include:
6.5 modify the aggregation weights for neighboring node representations according node degrees.
[54
learn custom message passing strategies for nodes with different degrees.
14
causally determine if low-degree nodes should "trust" messages from their neighbors.
learn node representations that are invariant to shifts in local neighborhood distributions.
32
optimize the graph's adjacency matrix to reduce upper bound on degree bias with
minimal decrease in overall accuracy.
locate anchor nodes that through the introduction of links with them can improve the repre- sentations of low-degree nodes.
8
27 propose a popularity-weighted aggregator for Graph Convolutional Networks.
19
leverage hop-aware attentive aggregation to attend differently to information at different
distances.
estimate the effect of influential high-degree nodes on the representations of low-degrce nodes and remove this effect after each graph convolution.
6
use adversarial learning to boost the influence of low-degree nodes.
A.4 Degree Bias from the Perspectives of Homophily and Topology
Prior research has connected degree bias to homophily and graph topology:
provides complementary perspective on the possible performance issues of GNNs that arise from degree disparities in graphs (e.g.. low-degree nodes induce oversmoothing in ho- mophilic graphs while high-degree nodes induce oversmoothing in heterophilic networks).
59
Oversmoothing is related to prediction homogeneity (2t B(0 )2; for homophilic networks,
as the number of layers in GNN increases (i.e., as oversmoothing occurs), (Et { gets closer to O (i.e., does not increase Ri,e)), thereby not inducing as much degree bias. In con- trast, our theoretical analysis demonstrates that degree bias occurs without oversmoothing and is amplified by high local homophily.
38 connects node distinguishability to node degree and homophily by analyzing the intra-class vs. inter-class embedding distance. We discuss similar quantities in $4.1 and $4.2 However, with the exception of Section 3.5, [38] considers the CSBM-H model in its theoretical analysis, which has pitfalls (as discuss in $ Moreover, unlike our work, [38] does not explicitly link the misclassification error a node to its degree in a more general data and model setting.
488 analyzes the effect of heterophily on GNNs via class separability, which characterizes through neighborhood distributions and average node degree. Similar to [8 [48 the HSBM model in its theoretical analysis.
only considers
observes that GNN performance is lower for high-degree nodes under heterophily. We likewise observe this in Figure 5 for chameleon and squirrel (which are heterophilic networks). Moreover, our theoretical analysis explains why degree bias not observed for heterophilic graphs. In $4.2 we explain that high-degree nodes in heterophilic networks do not have lower I- hop prediction homogeneity levels due to higher local heterophily; hence, we do not necessarily observe better performance for them compared to low-degree nodes.
330
20

---

B
Proofs
B.1
Theorem 1
Proof. Misclassification occurs when ((M]ic) > ((Mli,d) c).
P(e(M)i, E(Mli, =P (- log (1)) - log ([
(14)
=P H (D) H (L)
1,c
1,0
(15)
[ (L) 2 > 0).
P
(16)
E 12 - <0 (i.e., .M generalizes in expectation), by Cantelli's inequality:
c(((M)i,)) > ((Mjic]) =P =P((Z)t)
2 - 2 [ -E
2/:00
2,
(17)
(18)
-E 2 _ 2 12 2
We use Cantelli's inequality, rather than Chebyshev's inequality, because Cantelli's inequality is sharper for one-sided bounds.
21

---

B.2 Theorem 2
Proof. Denoting the 1-th term in the summation T Σjev (Pin) is X, w nc. It follows by the linearity of expectation that:
P
XWO,
T
T T.
Σ
(Pin)
BunDy x-" "
(1)
(19)
JEV
)-)((()))
(RanDy,
x w
(20)
(21)
Furthermore, by the linearity of variance:
T 1,6
T:10
Σ
(Pr)) (w)
12
-Vara x T (1)
Var
w de-
(22)
JEV
(Pl)) 2
S M
Σ
(23)
JEV
Mo (1)
(24)
Then, once again by the linearity of expectation and variance:
2
E 1 - )
2 Σ
1
(25)
1 Σ
Var
2 i,e'
_000
MM + 1)
(26)
1=0
Consequently:
E 2 (1)
300 )²
(27)
Var 2
M(L + 1) Et= (1)
22

---

B.3 Theorem 3
Proof. Re-expressing the 1-th term T
P
XWO ( the summation:
sym
T 1,c
=
D
AD
X,W
(28)
JEV
VDs ij
Σ JEV
(D
A)is
X, w
(29)
Daj
= D
P
X, xW ..
(30)
Dij
jEV
It follows by the linearity of expectation that:
Tuu:
T:00
VD
(P
1
EaNDy
x xT (1)
(31)
VDjs
JEV
D DuilEsanmn
1
BowDy,
x² 2
(1)
(32)
Djj
(33)
Furthermore, by the linearity of variance:
Var
T
1.
T:0
Dú: JEV
(Pt)) 15
12
"Dj
Var
w (1)
c-
(34)
D
Σ
(Pi))
Iw i5
1
(35)
Djj
JEV
DaMa,
(36)
Then, once again, by the linearity of expectation and variance:
2
= Dis
Σ
(37)
Var 2 2000
< DL 1)
Σ
(38)
1=0
Consequently:
E 2 (1) 2
(39)
Var (1)
M(L + I) z!1)
23

---

B.4 Lemmal 1
Proof. Define g( [t)) V ( f (M)i c). For simplicity of notation, let x [t].
[1) It is
Euzie 2x 60 and for j #
sufficient show that (|g()))l22 A. By simple derivation, (g(x)),
(g(x)), = De Then, by Hölder's inequality:
(xx))) Eofz eat) )² 2 + + Eaafi (c
(40)
2 (Eagieae)
Ea0) -.
(41)
Thus, 22.
24

---

B.5
Theorem
4
Proof. By the Lipschitz continuity ( (Lemma and the triangle inequality:
+ [[[+M](SMM
[[](SYM)ic)) <
z (.)
+ 1]
(42)
A
P sym x),
(woWt +1 -]
(43)
I=0
aett]
An
Σ
(Pl Syym X)
(B
(44)
OW
adfd By simple derivation, we see that B
(B(t)) (P sym [ x) T cjt), where Plym
R
the submatrix formed from the rows of p sym that correspond to the nodes in BBt]. Then, by the sub-muliipicatiiity of the Lg norm:
|e[t + (()MMi)) (M(SYMM
S An
Σ
(Pi))), xxx
(Payml!) b[1]
(45)
1=0
$ Xn [|[tt]] Σ
(Pism); xx" (Pinmlt)) [t)) )
(46)
Similarly the proof Theorem
(P (ymm)
XXX
(P sym)
Σ jeV
P (ym)
Pl (ym) mk (XX)), jk
(47)
=
D D mm mmmB p
Dis Dur
(xx*)
(48)
Hence, (P X (P (l)ml(t) '1111 VDu |x," and:
|e|1 + +1(SSMMii,)) - ([4(SYMMi,, S Vi An]le[[]I= 14]
(49)
25

---

B.6 Theorem
5
Proof. By the Lipschitz continuity of ([W i, c) (Lemma
and the triangle inequality:
|e[ + 1)(RW(i,)) - [[][RW e, = A
z
(1)
[ +
1]
z t0 10/1
(50)
(P (w + 1| w0011)11
A
(51)
1=0
Xn Σ
P x)
aw 1 (B ())
(52)
By simple derivation, we see that the submatrix formed from the rows of P that correspond the nodes in B(d. Then, by the sub-muliipiccaiivty of the Lg norm:
aed B
(B()))
(Pi [x c(t), where P [t] E R|
[4 + (RW)) e) ([[(, S An
Σ
(Pin)) xx" (P/+11)² <10
(53)
1=0
s Xn ||||t||l Σ (P Xx" (Pru [t)) T
(54)
Similarly the proof Theorem
2
(P Xxx
(Pt)
Σ
(Pl
(Prr) má (XX*) jb
(55)
m
ij
jEV
(XXX))) 5x
= (()
(56)
Hence, (PIa), XXT (P% -1x=000 and:
([t + [R - EE o)| S An [|(|t]]]
X 1
(57)
1=0
26

---

C
Datasets
In our experiments, we use 8 real-world network datasets from 4. 42 and 41 covering diverse domains (e.g., citation networks, collaboration networks, online product networks, Wikipedia net- works). We provide a description and statisties of each dataset in Table All the datasets have node features and are undirected. For each node, we normalize its features to sum to 1, following 15 We were unable find the exact class names and their label correspondence from the dataset documentation.
In all the citation network datasets, nodes represent documents, edges represent citation links, and features are a binary bag-of-worde representation of documents. The classification task is to predict the topic of documents.
In the collaboration network datasets, nodes represent authors, edges represent coauthorships, and features are a binary bag-of-words representation of keywords from the authors' papers. The classification task is to predict the most active field of study for authors.
In the online product network datasets, nodes represent products, edges represent that two prod- uets often purchased together, and features are binary bag-of-wond oord representation of product reviews. The classification task is to predict the category of products.
In the Wikipedia network datasets, nodes represent Wikipedia websites, edges represent hyper- links between them, and features are binary bag-of-word representation of informative nouns from the pages. The classification task to predict the level average daily traffic for pages.
Our us- age of these libraries and datasets complies with their license. PyTorch and PyTorch Geomet- ric are available under a torch-specific license and MIT license respectively. Cora ML and CiteSeer are available under an MIT License and can be found here: httts::/gitthe com/ https//gggggggggaaereeeeeeee watpggaussstteeeeeeeeeee wwwerreeeeeaeeeeeeeeeeeeeeeeeeee data CS, Physics, Amazon Photo, and Amazon com/ httpa/aaaaaaaeeeeeeeeeeeeeeeeeee /npz npz chameleon and squirrel are available under GLP-3.0 G and can be found here: hecp://htppps//rrhhhhnnnggg ai si/datasets//ptg///
We use PyTorch and PyTorch Geometric load and process all datasets 40
Computers available under an MIT License and can be found here: ptttps://gite
While these datasets are widely used, we did not obtain explicit consent from any data subjects whose data the datasets may contain. To the best of our knowledge (via manual sampling and inspection), the datasets do not contain any personally identifiable information offensive content.
Table 4: Summary of the datasets used our experiments.
Name
Domain
Nodes
# Edges
Features
# Classes
Cora_ML CiteSeer
citation
2995 4230
16316 10674
2879
7
citation
602
6
CS
collaboration
18333
163788
6805
Physics
collaboration
34493
495924
8415
5
Amazon Photo
online product
7650
238162
745
8
Amazon Computers
online product
13752
491722
767
10
chameleon
Wikipedia Wikipedia
2277
36101
2325
5
squirrel
5201
217073
2089
5
27

---

D Models
In our experiments, we transductively Iearn and compute node representations using encoders based
on Graph Convolutional Networks (GCNs) [24] GraphSAGE 17], and Graph Attention Networks (GAT') 46
In all cases, we use general message-passingg GNNs M [6]. which include separate parameters for source and target nodes and residual connections; in particular, for layer
H = ( (Z()= =a ( (w p H W 19)
xW
(58)
where HO Nxd the 1-th layer node representations (with H X and d(2) C), (1)) is instance- wise non-linearity (with ((4) being softmaxx, p()) RNN is graph filter, and
w("), w w! Rdd x)d are the 1-th layer model parameters.
We consider the following special cases of M which vary with respect to their graph filter:
RW: VI E NNL, P() P.N- D-1 1- (i.c., the uniform random walk transition matrix), where D is the diagonal degree matrix with entries Dj = EjeyAnj
SYM: E NLL, P(U) Paym = D AD-1. 3.
ATT: V/ E Nct, p()) is graph attentional operator with default hyperparameters and single head [46].
Each encoder has three layers (61-dimensional hidden layers), with a ReLU nonlinearity between layers. We do not use any regularization (e.g., Dropout, BatchNorm). The encoders are explicitly trained for node classification with the cross-entropy loss and the Adam optimizer (3 with full- batch gradient descent the training set. We use learning rate of 5e-3. We further use random node split of 1000-500-ree for test-val-train. We train all encoders until they reach the training accuracy of MAJwL and select the model parameters with the highest validation accuracy. Although we do not do any hyperparameter tuning, the test accuracy values indicate that the encoders are well- trained.
We use PyTorch [40] and PyToorch Geometric [5 train all the encoders on single NVIDIA GeForce GTX Titan Xp Graphic Card with 12196MiB of space internal cluster. On average (with respect to the datasets), the median time per training epoch was 0.05 seconds. Thus, the
estimated total compute is:
0.05 (approximate number of seconds per epoch)
(59)
500 (number of epochs per training run)
(60)
X 10 (number of training runs/random seeds per model)
(61)
(number of models per dataset)
(62)
X 8 (number of datasets)
(63)
12196 MiB (GPU memory)
(64)
= 73, 176k MiB x seconds
(65)
These experiments were run few times (e.g., due to the discovery of bugs), but the full research project did not involve other experiments not reported in the paper. We used a single CPU worker to load datasets and plot results. The datasets take up 0.2975 MB of disk space.
"Our usage of all libraries complies with their license. Py and PyTorch Geometric are available under torch-specific license and MIT license respectively.
28

---

E
Additional Degree Bias Plots
Unlike the other datasets, do not observe degree bias for chameleon and squirrel because these datasets are heterophilic. We intentionally include these datasets to draw contrast to the other, ho- mophilic datasets and validate our theory. For example, in $4.2. we explain that high-degree nodes in heterophilic networks do not have more negative I-hop prediction homogeneity levels due to higher local heterophily levels; hence, we not necessarily observe better performance for them compared to low-degree nodes.
CORA ML SYM
20
20
15
15
Test loss
20
10
5
20
60
20
40
60
Degree
Degree
Degree
RW
SYM
ATT
1.75
1.75
1.75
1.50
1.50
1.50
1.25
1.25
1.25
1.00
1.00
Test loss
1.00
0.75
Test
0.75
0.75
0.50
0.50
0.50
0.25
0.25
0.25
0.00
0.00
0.00
0
25
50
75
1000
125
25
50
75
100
125
0
25
50
75
100
125
Degree
Degree
Degres
PHYSICS
RW
SYM
ATT
3-
Test loss
Test loss
Text
100
150
100
150
50
100
150
Degree
Degree
Degree
Figure 4: Test loss vs. degree of nodes in citation and collaboration network datasets for RW, SYM, and ATT GNNs. High-degree nodes generally incur a lower test loss than low-degree nodes do. Error bars reported over 10 random seeds; all error bars are 1-sigma and represent the standard deviation about the mean.
29

---

PHOTO
RW
SYM
ATT
12
12
8-
Test loss
8-
Test
2-
0
200
400
600
800
200
400
600
800
200
400
600
800
Degree
Degree
Degree
COMPUTERS
RW
SYM
20
20
Test less
Testloss
10
10
4000
600
200
400
Degree
Degree CHAMELEON
Degree
RW
SYM
20
20
20
15
loss
Test loss
200
10
20
40
60
80
20
40
60
80
0
20
40
60
Dogree
Degran
Degree
SQUIRREL
RW
SYM
ATT
50
50
40
30
Test loss
Test loss
30
Test
20
20
10
10
100
150
200
250
50
100
150
200
250
50
100
150
200
250
Degree
Degree
Degree
Figure 5: Test loss degree of nodes in online product and Wikipedia network datasets for RW, SYM, and ATT GNNs. High-degree nodes generally incur a lower test loss than low-degree nodes do. Error bars reported over 10 random seeds; all error bars are 1-sigma and represent the standard deviation about the mean.
30

---

F Additional Visual Summaries of Theoretical Results
In the plots below, we consider low-degree nodes to be the 100 nodes with the smallest degrees and high-degree nodes to be the 100 nodes with the largest degrees. Each point in the plots in the left column corresponds a test node representation and its color represents the node's s class. The plots in the left column are based on a single random seed, while the plots in the middle and right columns are based on 10 random seeds. RW representations of low-degree nodes often have a larger variance than high-degree node representations, while SYM representations of low-degree nodes often have a smaller variance. Furthermore, SYM generally adjusts its training loss on low-degree nodes less rapidly.
The training loss curves in Figure 6 still support our theoretical analysis. Theorem reveals that for SYM, node degree and the (degree-discounted) expected feature similarity X, affects the rate of learning. On the other hand, Theorem 5 indicates that for 72W, while we do not expect node degree to impact the rate of learning, the expected feature similarity X is still influential. Hence, interpreting Theorems 4 and joiintly we expect and accordingly observe that the orange curve for SYM has a steeper rate of decrease relative to the orange curve for RW as the number of epochs increases.
CORA ML RW
RW
RW
0.18-
300
Low diggnee modes High degree nodes
2.0
Lose digree nodes High degree nodes
0.03
1.5
200
2
0.00
150
Traniig
1.0
-0.05
degres nodes
50-
High degree nodes
-0.10
0.30
0.05
100
2000
300
40 Spocta
502
Spocha
0.10
covarianca
degree
degred
250
0.05
200
Valdrig 1o00
0.02
150
100
-0.10
High degres rodes
Low degriss se nodes
0.0
-0.15
-0.10
-0.05
0.30
0.05
100
2000
300
400
500
20
40
60
60
300
450
475
500
PC1
Epochs training
Epacts of lrtrataann hang
ATT
ATT
ATT
0.33
of tas 1u0 1ar10aa"
300
Low digine modea High-degree modes
High-deggeen nodes
degres nodes
250
0.05
3.5
0.02-
350
3.0
-0.03
0.5
0.12
nodes High-degt
50-
0:20
80
450
475
PC2
Epochi of training
Spocta
Figure 6: Visual summary of the geometry of representations, variance of representations, and train- ing dynamics of RW, SYM, and ATT GNNs on Cora ML.
31

---

C5 RW
RW
RW
degree nodes
Low degree nodes High dogree nodes
degres nodes High diggns nodes
0.10
High degeez nodes
0.05
1.5
0.02
100
3.0
00.55
300
0.5
0.100
0,075
9,550
0025 0.000
0.025
100
200
300
400
500
20
40
50
100
450
475
500
Tpochs
SYM
3.0
diggeee
degnee
of (ass (igghtttoo www.rtatt.tt
400
High-Segow
23
Lighhdeige
0.05
300
Traning bos'
P2
0.02
-0.03
0.0
-0. 111.00-0.330 21000-00000022 0.000 0.025
100
300 Epochs of tr2kiing
200
40
00
100
450
475
500
PCI
Spocts of traaning
ATT
ATT
ATT
Low degree nodes
Low dagice modes
Low degres nodes High diggine nodes
0.10
High degres nodes
of Pepreeeeeeeaaoo www.eeeeeennaaiiinee Sentaationa
-000
High degredereeee nodedd
0.05
300
2.0
g
3.5
0.02
-00
300
PCB
training
Spacha
Figure 7: Visual summary of the geometry of representations, variance of representations, and train- ing dynamics of RW, SYM, and ATT GNNs on CS.
PHYSICS RW
RW
RW
0.12
Low degres nades High degnee nodes
200
Low dogree nodes High- del--dorreeee nodes
Low Sogres nodes High degies modes
larcec Track www.troooeaaaaaaaaoo Daniaation
0.03
0.02
300
Traliiep
50
-0.05
-0.
00.00-3.07
075 6 05000-25500000
000 8:025 0.050
100
200
300
400
500
20
40
60
435
500
SYM
0.15
degrne
Segres
1.5
-50
Trihiin Loda
PC2
3.0
100
50
0.5
0.05
Low degrra nodes
High degree nodees
0.0
11.30--3.000 0700075-000000 110000000000000 8.025 0.050
100
300 Epochs traliing
200
400
20
40
00
300
450
475
500
FCI
Epocts of tra ning
ATT
ATT
ATT
0.10
Low degree nodes High degnee hodes
200
Low degree nodes
Low degree nodes High-deggnen nodes
corurtunce
High dierdeeeeeeeee nodes
0.05
150
g-
6.02
300
Traning
3.0
50
-0.05
103-3 (5000 6.5
160 d5
475
PCI
Epocha of training
Spacts of
Figure& 8: Visual summary of the geometry of representations, variance of representations, and train- ing dynamics of RW, SYM, and ATT GNNs on Physies.
32

---

PHOTO
RW
RW
0.075
Thace of coveeeeee
Law degrue nodes
High dogr co nodic
2.0
High degres nodes
Low dogr nodes
0.050
250
1.5
230
1.0-
-0.025
100
-0.050
0.5
dogrea rodis
(1gg-edegree ee nodes
0.0
2:30
0.05
0.00
0.05
0.30
100
200
300
400
505
20
40
50
80
100
450
435
500
SYM
0.075
Loo-degree 11gg-degret
330
Lox-degree High-degre
Lnwedegree
230
0.025
1.5-
0.000
130
1.0
0.025
0.5
-0.075
0.0
-2.10
-0.05
0.00
0.05
0.30
1.00
200
300
400
500
25
40
10
85
150
450
475
500
PCL
Epocts toining
EpocTe traningg
ATT
ATT
ATT
330
Law diog oe nodes High degrie nodes
2.0
Low degr 2o nodes High degree nodes
0.010
0.025
200
g
150
-0.025
-0.500
Thece
rodis
50
0.075
0.05
500
Epechs
Epoche
Figure 9: Visual summary of the geometry of representations, variance of representations, and train- ing dynamics of RW, SYM, and ATT GNNs on Amazon Photo.
COMPUTERS
RW
RW
RW
0.075
Law degree rodies High-degnce nodes
23:00
Low dogr de nodis High degree nodes
Low dogree nodes High Segres nodes
0.030
Thacs of samele coosrtene
7.5
0.025
5.0-
0.000
1500
-0.025
0.050
0.0
500
-2.5
-0.00
0.005
20
0.35
500
1,000
1530
2000
2530
3000
20
40
80
150
2050
2975
3000
SYM
SYM
2500
10.0
diggne
Piace campaa cover unee
0.050
20:00-
5.0
2.5
1000
0.0
-0.075
2.5
0.300
0-
-5.0
-0.10
-0.05
0.50
0.50
300
1000 1550 2000 2500 Epochs of frainin
3000
20
40
80
10
150
2050
2015
3003
PC1
Epochs of traliing
ATT
ATT
ATT
2500
Low degr te nodes
15.0
Low degree modes
Tack of samole coPratunce
2003
High degree nodes
7.5
High degreeeeeee modes
0.025
5.0
6.000
35000
2.5
0.025
1000
00.00
3.0
0.075
Law-eegree hodes dogree
500
-2.5
-0.100
-010
-lios
0.
11:0
2530
160 2á10
2675
PC1
Spacts of training
Spachs traising
Figure 10: Visual summary of the geometry of representations, variance of representations, and training dynamics of RW, SYM, and ATT GNNs on Amazon Computers.
33

---

CHAMEL FON
RW
0.1
0.05
Thace CONN
1.50
Law degrea rodes High degroe nodis
125
1.50
Lowr degree nodes
H dog no nodes
0.02
1.00
220
0.75
0.10
0:50
degr nodes
0.115
H8gh degree
0.00
0.35
0.10
0.05
0.00
0.05
0.30
100
200
300
400
500
20
40
50
90
100
450
475
500
SYM
0.10
Low-degree
sampo covertance
150
11ghh-degree
1.25
1ighhdeggee
0.02
Telele Tiee
1.00
100
-0.05
0.75
50-
Lowi degree nodes High degree nodes
0.25
0.00
15
-0.10
-0.0
0.02
0.85
0.30
1000
200
350
400
550
20
45
80
100
450
475
500
FC1
Epochs tr2kning
Epochs trakiing
ATT
ATT
ATT
0.05
Thace eemple coveettrcce
Law degres rodes High dogice nodes
1.50
Low degros nodes
High-do high-doree nodes
0.03
1.00
g
1.00
0.05
0.75
-015
0.50
0.25
0.15
degres
0.00
-0.55
450
Epoche training
Epacha training
Figure 11: Visual summary of the geometry of representations, variance of representations, and training dynamics of RW, SYM, and ATT GNNs on chameleon.
SQURREL
RV
Low degr nodes High degree nodes
603-
Low degrae nodes High degree neides
Low dog nodes
High degree nodes
0.05
1.25
403-
g 0.02
-0.03
200
0.50
-0.10
0.25
-0.2
0.30
0005
0.50
0.15
0.30
300
200
300
400
500
20
60
80
<50
500
SYM
0.10
degres
of Sest HE 2010
Low-degre
1.50
degress
500-
1:25
PC2
0.02
300
0.75
200
0.50
-0.12
0.00
-0.10
-0.05
0.50
0.50
0:30
200
200
300
400
500
25
40
50
80
1.00
450
473
500
PC]
Epochs ortriining
EpocTe traningg
ATT
ATT
ATT
0.12
603-
Low degree rodes
H4gh- dediedeeeeee radees
1.50
Low de-ddegreee nodes High degree nodes
0.05
403-
1.50
g 0.02
300
0.75
-0.05
0.25
160
450
550
160 a60
475
PC1
Epocha of training
Epecte traning
Figure 12: Visual summary of the geometry of representations, variance of representations, and training dynamics of RW, SYM, and ATT GNNs on chameleon.
34

---

G
Additional Inverse Collision Probability Plots
CORA ML
RW
SYM
ATT
Inverse probability
Inverse collision probability
40
Inverse collision probability
0.8
0.8
30
0.6
20
0.6
10
20
40
60
20
40
0
20
40
60
Degree
Degree
Degree
CS
RW
SYM
ATT
collision probability
1.0
Inverse collision probability
Inverse collision probability
1.0
100
80
0.8
0.6-
40
20
0.4
0.4
50
100
100
50
100
Degree
Degree
Degree
PHYSICS
RW
SYM
ATT
probability
1.0-
Inverse collision prob probability
Inverse probability
1.0-
0.8
0.8
1000
0.6
6,90
0.6
50
0.4
0.4
150
50
50
150
Degree
Degree
Degree
Figure 13: Inverse collision probability degree of nodes in citation and collaboration network datasets for RW, SYM, and ATT GNNs. Node degrees generally have a strong association with inverse collision probabilities.
35

---

PHOTO
RW
SYM
ATT
1.0
Inverse collision probability
1.0
800
600
0.6
400
0.6
Inverse
0.4
200
Inverse
0.4
250
500
750
250
500
750
0
250
500
750
Degree
Degree
Degree
COMPUTERS
RW
SYM
ATT
Inverse collision probability
1.0
Inverse collision probability
probabiliey
1.0
0.8
0.8
400
0.6
0.6
200
400
600
200
400
600
200
400
600
Degree
Degree
Degree
CHAMELEON
SYM
ATT
colltsion probability
Inverse collision probability
80
Inverse collision probability
0.8
80
0.8
40
0.6
0.4
20
0.2
0.4
0.0
40
60
80
80
Degree
Degree
Degree
SQUIRREL
RW
SYM
ATT
Inverse collision probability
1.0-
Inverse collision probability
250
probability
1.0
0.8
200
0.8
0.6
150
0.4
100
0.6
0.2-
50
0.4
0.0
100
200
100
200
100
200
Degree
Degree
Degree
Figure 14: Inverse collision probability vs. degree of nodes in citation and collaboration network datasets for RW, SYM, and ATT GNNs. Node degrees generally have strong association with inverse collision probabilities.
36

---

H Maining-Timm Degree Bias: Random Walk Graph Filter
We now demonstrate that during each step of training RW with gradient descent, compared to SYM, the loss of low-degree nodes is not necessarily adjusted more slowly. We define
VI E NEL,X; X2 (1) RIBM|) where for m BlI, (x4
())
x
In effect, (x."1t) captures the expected similarity between the raw features of nodes j and with respect to the (-hop random walk distributions of i E V and m E Bit].
Theorem 5. The change loss for after an arbitrary training step obeys:
[[[++] - (W (1))) s v2n [e][1]] Σ
(66)
For RW, the change (either increase or decrease) in loss for after an arbitrary training step does necessarily have a smaller magnitude if is low-degree. However, the L-hop neighborhoods of low-degree nodes still often have less overlap with the neighborhoods of training nodes, which can constrain the rate at which the loss for changes. We confirm these findings empirically in Figure and $ For all the datasets, the blue curve for RW has a less steep rate of decrease than the blue curve for SYM as the number of epochs increases. However, for RW itself, the orange curve generally descends more quickly than the blue curve, with the exception of the heterophilic chameleon and squirrel datasets, for which the features of nodes the neighborhoods of high- degree nodes and training nodes are dissimilar. Therefore, models do not learn more rapidly for high-degree nodes under heterophily. These findings support hypothesis (H2). Our results for RW may also apply to ATT when low-degree nodes are generally attended to less.
37

---

I Achieving Maximum Training Accuracy
CITESEER
1e-7
Mean absolute gradient
1.2
RW
1.04
RW
SYM
SYM
Training accuracy
1.0
ATT
1.02
ATT
0.8
MAJwL
1.00
0.6
0.4
0.98
0.2
0.96
0.0
400
425
450
475
500
400
425
450
475
500
Epoch
Epoch
Figure 15: Mean absolute parameter gradient vs. training epoch for RW, SYM, and ATT GNNs on CiteSeer (over 10 random seeds). The training accuracy of SYM, RW, and ATT ultimately reach the accuracy of MAJwL.
We empirically show that SYM (despite learning different rates for low vs. high-degree nodes), RW, and ATT can achieve their maximum possible training accuracy (i.e., the accuracy of majority voting-classifier MAJw1.). Furthermore, per our experiments, the accuracy of MAJwr. is often close to 100%, indicating that the WL test does not significantly limit the accuracy of SYM, RW, and ATT in practice.
Per [57]. because the expressive power of SYM, RW, and ATT are limited by the WL test, an upper bound on their training accuracy is the accuracy of majority
MAJwı. applied to
WL node colorings (for details on how to compute colorings, see $IIAA and SVLB of (68)). In particular, if the WL test produces the colors E K S1 for nodes in S, MAJwI. predicts node to have the label Y; = MAJwL(í, X, X. A) = mode Yi E V. = c:}- However, Figure 15 and $J reveal that the number of training epochs increases, the training accuracy of SYM, RW, and ATT reach the accuracy of MAJwL. Because the accuracy of MAJwI. often close to 100%, our experiments suggest that insufficient expressive power likely does not contribute to degree bias, drawing doubt to hypothesis (H7).
Empirically inspecting the model gradients, compared ATT, the number of training epochs increases, the mean absolute gradients of SYM and RW are comparably small but often decrease more slowly fluctuate. To understand this, analytically inspect the gradients of RW:
dEe aw (B()) x (1) e[!]
(67)
(pl (t) T (for 0) often has numerous eigenvalues around 0, which can yield gradients 0eld
swopp (B(t)) with a small magnitude even when ||e[t]]| is not small. The same analysis holds for SYM. As such, SYM and RW may get trapped suboptimal minima during training, yielding slower or unstable convergence; in contrast, because ATT has dynamic filter, its training loss rarely exhibits slow or unstable convergence.
38

---

J
Additional Training Loss Plots
CORA ML
1e-8
Mean absolute gradient
RW
1.04
RW
1.5
SYM
SYM
Training accuracy
ATT
1.02
ATT
MAJwL
1.0
1.00
0.5
0.98
0.96
0.0
400
425
450
475
500
400
425
450 Epoch
475
500
Epoch
CS
1e-8
Mean absolute gradient
1.50
RW
1.04
RW
SYM
SYM
Training accuracy
1.25
ATT
1.02
ATT
MAJwL
1.00
1.00
0.75
0.50
0.98
0.25
0.96
0.00
400
425
450
475
500
400
425
450
475
500
Epoch
Epoch
PHYSICS
1e-9
6
Mean absolute gradient
RW
1.04
RW
5
SYM
SYM
Training accuracy
ATT
1.02
ATT
4
MAJwL
3
1.00
2
0.98
1
0.96
0
400
425
450
475
500
400
425
450
475
500
Epoch
Epoch
Figure 16: Mean absolute parameter gradient vs. training epoch for RW, SYM. and ATT GNNs on Cora_ML, CS, and Physics. The training accuracy of SYM, RW, and ATT ultimately reach the accuracy of MAJWL.
39

---

PHOTO
1e-6
Mean absolute gradient
RW
1.04-
RW
SYM
SYM
Training accuracy
5
ATT
1.02
ATT
MAJWL
4
1.00
3
2
0.98
1
0.96-
0
400
425
450
475
500
400
425
450 Epoch
475
500
Epoch
COMPUTERS
1e
Mean absolute gradient
RW
1.04
RW
2.5
SYM
SYM
Training accuracy
ATT
1.02
ATT
2.0
MAJwL
1.5
1.00
1.0
0.98
0.5
0.96
0.0
2900
2925
2950
2975
3000
2900
2925
2950 Epoch
2975
3000
Epoch
Figure 17: Mean absolute parameter gradient vs. training epoch for RW, SYM, and ATT GNNs on Photo and Computers. The training accuracy of SYM. RW, and ATT ultimately reach the accuracy of MAJwL.
40

---

CHAMELEON
1e-6
RW
RW
Mean absolute gradient
5
SYM
1.00
SYM
Training accuracy
ATT
ATT
0.98
MAJwL
0.96
0.94
0
0.92
400
425
450
475
500
400
425
450
475
500
Epoch
Epoch
SQUIRREL
1e-6
1.04
RW
RW
Mean absolute gradient
8
SYM
Training accuracy
1.02
SYM
ATT
ATT
MAJwL
1.00
4
0.98
2
0.96
400
425
450
475
500
400
425
450
475
500
Epoch
Epoch
Figure 18: Mean absolute parameter gradient vs. training epoch for RW, SYM, and ATT GNNs on chameleon and squirrel. The training accuracy of SYM, RW, and ATT ultimately reach the accuracy of MAJwL.
41

---

K Connecting Inverse Collision Probability to Node Degree
Our theoretical analysis may be improved upon by establishing rigorous connection, or a lack thereof, between the inverse collision probability of a node and its degree.
Via some preliminary analysis, find that it is possible to express the inverse collision prob- ability of (i.e., equivalently express the sum of I-hop collision probabilities) in terms of show: Ei
Dis. In particular, DI EivlEeen))) (Pm (P/w)))y)?
1 + )ay]?. As before, we can see that the inverse collision probability is
(1) a; (0) + Σi= Ejel((Pr)))))
larger (and thus R is larger) when Dù is larger and Σ ( (R,= o (D However, because EkEN(s) depends on Di., this expression does not completely isolate the im- pact of Dj on the inverse collision probability. similar expression can be derived for SYM by expressing: Peym D
Alternatively, may consider Σl of S Ei=o a,0, and then plug in the steady-state proba- D only depends bilities of uniform random walks on graphs. However, as - oo, (Prw)ij = 2|
on Djs (not Dis as desired). It is also possible to upper bound the inverse collision probability as: 1/ E/ (9) I {/(a + ) 1/(1/D;; + 1), which is in terms of D however, we cannot use this upper bound to lower bound Ri,e'. The collision probabilities themselves are intimately related to more global properties of graphs; for instance, via eigendeconposition, [(Pt < X where À
the eigenvalue Prw with the largest magnitude [6 Then, the inverse collision
probability is strictly greater than Σ IVAA
This being said, our paper argues that the inverse collision probability is more fundamental quantity that influences what the fair graph learning community has termed "degree bias" than degree alone, which we have shown positively associated with the inverse collision probability.
42

---

L Limitations and Future Directions
Survey While we aimed to thorough in our survey of prior papers on degree bias, is inevitable that we missed some relevant work. In addition, we extract hypotheses for the origins of degree bias from the main bodies of papers; it is possible that the hypotheses do not fully or accurately reflect the current perspectives of the papers' authors.
Theoretical analysis Our thcoretical analysis is limited to linearized message-passingg GNNs. While this is common practice in the literature 7 39], it is strong simplifying assumption. We empirically validate our theoretical findings on GNNs with non-linear activation functions, but our paper does not address possible sources of degree bias related to these non-linearities, which would be interesting to investigate in future work. Towards this, a possible option is to assume that node features are drawn from Gaussian distribution and derive precise high-dimensional asymptoties for degree bias in non-linear GNNs using the Gaussian equivalence theorem, as in (. Our assumptions that GNNs generalize in expectation (Theorem D and the variance of node representations is finite (Theorems and 3) are not overly strong assumptions in practice.
Furthermore, paper focuses on node classification. However, our findings readily lend insight into the origins of degree bias in link prediction. For example, if one uses node representations and an inner- inner-product decoder to predict links between nodes, results indicate that:
In the random walk filter case, link prediction scores between low-degree nodes will suffer from higher variance because low-degree node representations have higher variance (Theorem 2 Hence, Theorem | suggests that predictions for links between low-degree nodes will have higher misclassification error.
In the symmetric filter case, our proof of Theorem suggests that the link prediction scores between high-degree nodes will be over-calibrated (i.e., disproportionately large) because high- degree node representations have a larger magnitude (i.e., approximately proportional to the square root of their degree). Hence, over-optimistic and possibly inaccurate links will be pre- dicted between high-degree nodes.
The labels and evaluation for link prediction confound intuition. Unlike node classification, the labels for link prediction (i.c., the existence or not a link) make the task naturally imbalanced with respect node degree; high-degree nodes have much higher rate of positive links than low- degree nodes. This association between degree and positive labels can influence the misclassification error. Ultimately, more rigorous theoretical analysis and experimentation hypothesized implications of node degree for link prediction performance. Similarly, more research required to understand the implications of findings for degree bias in the context of graph classification.
needed confirm the
Furthermore, theoretical analysis does not encompass heterogeneous graphs. In our literature survey, we cover works that establish the issue of degree bias for knowledge graph predictions and embeddings (e.g.. [5] 43).. Our thcoretical analysis is general and covers diverse peessage-passing GNNs, and can be extended to heterogeneous networks if messages aggregated from different edge types subsequently linearly combined. In this setting, Ri,e' be computed the sum of the prediction homogeneity quantities (E/= ((t) )2 for each edge type divided by the sum of the collision probability quantities Ejev(( ((ee(((())))))) )ep) for each edge type.
Empirical validation We sought be transparent throughout our paper regarding misalignments between empirical and theoretical findings. Our experiments focus on the transductive learning setting; it would be valuable validate our theoretical findings in the inductive learning setting as well. Furthermore, while we aimed to cover diverse domains (c.g., citation networks, collaboration networks, online product networks, Wikipedia networks), well as homophilic and heterophilic networks, it remains to identify the shortcomings of our theoretical findings for heterogencous and directed networks.
Principled roadmap To do justice to studying the origins of degree bias in GNNs, which our paper reveals has various and sometimes conficting understandings, we limit the scope of our paper to understanding the root causes of degree bias, not providing concrete algorithm to alleviate it.
43

---

Instead, we offer principled roadmap based on our theoretical findings to address degree bias in the future. We further comment on the limitations of algorithmic solutions degree bias in our Broader Impacts section below.
44

---

M Broader Impacts
Our paper touches upon issues of discrimination, bias, and fairness, with the goal of advancing jus- tice in graph learning. In particular, our analysis of the origins of degree bias in GNNs seeks to inform principled approaches mitigate unfair performance disparities faced by low-degree nodes in networks (e.g., lowly-cited authors, junior researchers, niche product and content creators). De- spite our focus on fairness, our work can still have negative societal impacts malicious contexts. For example, alleviating the degree bias of GNNs that are intended to surveil individuals can further violate the privacy of low-degree individuals. Ultimately, performance disparities should only be mitigated when the task is aligned with the interests and well-being of marginalized individuals; we explicitly do not support evaluating or mitigating degree bias to ethics-wash inherently harmful applications of graph learning. Furthermore, any algorithm proposed to alleviate degree bias will not be a 'silver bullet' solution; graph learning practitioners must adopt a sociotechnical approach: (1) critically examining the societal factors that contribute their networks have degree disparities to begin with, and (2) monitoring their GNNs in deployment and continually adapting their degree bias evaluations and algorithms. In addition, alleviating degree bias does not necessarily address other forms of unfairness in graph learning, e.g., equal opportunity with respect to protected social groups 2] dyadic fairness [25], preferential attachment bias 44); fairness algorithms contextual and not one-size-fits-all.
45

---

Responsible Research Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: Yes]
Justification: All the theorems, formulas, and proofs in the paper numbered and cross- referenced. The assumptions are clearly stated in the main body of the paper and referenced in the proofs of theorems. Formal proofs provided in the appendix; while proof sketches are not included in the main body of the paper, we provide extensive interpretation of theoretical results.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Ye]]
Justification: Details reproduce experiments are provided in the main body of the paper, D and [C The code is released via Github.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code is released via Github. The data available through PyTorch Geometric [13], and data processing details are provided in $C
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: See D and C
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error bars are reported over 10 random seeds in all figures except for the PCA plots. The factors of variability include model parameter initialization and training dynamics. All eиrог bars are I-sigma and represent the standard deviation (not standard error) of the mean. We implicitly assume that errors computed using PyTorch std function 40). We provide this information at the beginning of
cermally-disrrbbueed Error bars
8. Experiments Compute Resources
46

---

For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory. time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: See
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httph//pppppppppp.....o/oo////oa
Answer: [Yes]
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: See M
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: See SC The original paper that produced each dataset is cited. Links to libraries and datasets are included; the versions of software dependencies can be found in the requirements. txt file via Github. We also provide the name and link to the license (which includes terms of use and copyright information, where applicable) of each library and dataset.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification: We release our code via Github under MIT license. We provide README that explains how to reproduce our experiments. Training, license compliance, and consent details are included in $D Limitations are discussed in
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
15. Institutional Review Board (IRB) Approvals Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
47


Reviews:
[{"review_id": "S45rF36oxg", "reviewer": "Reviewer_Ao8B", "summary": "Given the wide-adoption of GNN-based node classification and the potential risk of degree-related bias, this paper systematically reviews the degree-bias paper in previous literature and proposes a theoretical framework to analyze the degree-related bias. Several insightful observations have been drawn with empirical verification.", "questions": "(1) Since the degree bias focused on here is node classification, would it be better to note this special case somewhere in the paper, or at least for the title, would it be better to reword and limit the task scope to node classification? Is there any insight or potential thought on degree-related bias in link prediction and graph classification (here the degree would correspond to graph density)?\n\n(2) In Figure 5, when looking at the Squirrel and Chameleon datasets, there is no significant difference in high-degree and low-degree test loss, is there a specific reason for their difference from the other datasets?\n\n(3) Maybe it is a typo, but in the Equation at the bottom of page 4, if we unify different layers' weight transformation matrices as of dimension $\\mathbb{R}^{d^0\\times C}$, would it cause some dimension mismatch during matrix multiplication? Why does every layer of convolution consider the project from space $\\mathbb{R}^{d^0}$ to $\\mathbb{R}^{C}$? Moreover, it might be better to add back the Equation number.\n\n(4) It is not so clear about \"the diversity of neighborhoods\" until the formal definition in Line 168. It might be better to provide some concise illustrations to help readers understand the diversity of neighbors when it was mentioned for the very first time.\n\n(5) Based on Theorem 2, in addition to decreasing the negative $\\sum_{l=0}^{L}\\beta_{i, c'}^{(l)}$ so that $R_{i, c'}$ could increase, could we also increase the positive $\\sum_{l=0}^{L}\\beta_{i, c'}^{(l)}$ so that $R_{i, c'}$ could increase? Are these two scenarios corresponding to some graph local structure? Based on my understanding, as $\\beta_{i, c'}^{(l)}$ measures of the local subgraph difference between class $c'$ and class $c$, it really boils down to the local homophily and local heterophily, if the value is pretty small, then it might correspond to a very small $\\beta$, which might correspond to a equal contribution between class c and c' and hence the subgraph is really like a mixture between nodes from these two classes and hence cannot work very well. To sum up this point, my thinking is that it would be better to provide some intuition for some theoretical findings from a topology perspective.\n\n(6) It might be interesting to add some analysis when a distribution shift happens.\n\n(7) For the training loss visualization in Figure 2, it is really hard to see the difference of low/high-degree nodes for RW and ATT.", "limitations": "The paper addressed all limitations with the following exceptions:\n\nThe paper mainly studies degree-related bias for node classification. There are some other tasks such as link prediction and graph classification worth similar analysis as well.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) A systematic investigation of a long-standing yet not addressed research problem, degree bias. Comprehensive summary of previous works on this has been presented\n\n(2) The degree-related bias is urgently related to social benefit.", "weaknesses": "(1) Some experimental results are not supportive of some claims.\n\n(2) Some theoretical analyses lack intuitive justification from a graph topology perspective, e.g., the connection with network homophily/heterophily.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments and thorough questions! Regarding your questions:\n\n(1) We will make the scope of the paper clearer by indicating in the title, introduction section, and limitations section that we focus on node classification. Our findings readily lend insight into the origins of degree bias in link prediction. For example, if one uses node representations and an inner-product decoder to predict links between nodes, our results (lines 208-226) indicate that:\n- In the random walk filter case, link prediction scores between low-degree nodes will suffer from higher variance because low-degree node representations have higher variance. Hence, Theorem 1 suggests that predictions for links between low-degree nodes will have a higher misclassification error.\n- In the symmetric filter case, the link prediction scores between high-degree nodes will be over-calibrated (i.e., disproportionately large) because high-degree node representations have a larger magnitude (i.e., approximately proportional to the square root of their degree). Hence, our proof of Theorem 3 suggests that over-optimistic and possibly inaccurate links will be predicted between high-degree nodes.\nMore research is required to understand the implications of our findings for degree bias in the context of graph classification; such research likely has rich connections to the literature on spectral expressive power [1].\n\n[1] Balcilar, Muhammet, et al. \"Analyzing the expressive power of graph neural networks in a spectral perspective.\" 2021.\n\n(2) The reason that we do not observe degree bias for Chameleon and Squirrel is because unlike the other datasets, these datasets are heterophilic. We intentionally include these datasets to draw contrast to the other, homophilic datasets and validate our theory. For example, in lines 220-222, we explain that high-degree nodes in heterophilic networks do not have more negative $l$-hop prediction homogeneity levels due to higher local heterophily levels; hence, we do not necessarily observe better performance for them compared to low-degree nodes.\n\n(3) We will ensure that equation numbers are visible for all equations. The weight transformation matrices should all be of dimension $d_0 \\times C$; there is not a dimension mismatch issue. This is because we consider linearized versions of message-passing GNNs. In particular, in the equation between lines 132 and 133, if we set each $\\sigma^{(l)}$ to be identity and recursively expand the matrix multiplications, we end up with the expression: $Z^{(L)} = \\sum_{l = 0}^L P_{rw}^l X W^{(l)}$, where $W^{(l)}$ is the sum of all the weight terms in the expansion that correspond to $P_{rw}^l$; for simplicity, we collapse each sum of weight terms into a single weight matrix. Because each $W^{(l)}$ maps the input features $P_{rw}^l X \\in \\mathbb{R}^{n \\times d_0}$ to the outputs $Z^{(l)} \\in \\mathbb{R}^{n \\times C}$, they must all be of size $d_0 \\times C$. It makes sense to have a different weight matrix for each $P_{rw}^l X$, as we may need to extract different information from features aggregated from neighborhoods at different hops.\n\n(4) This is great feedback. We will include a figure at the beginning of the paper that visually illustrates the concepts of prediction homogeneity and collision probability, and their connections to homophily and diversity.\n\n(5) In Theorem 2 (lines 118-119), we assume that $\\mathbb{E} [Z_{i, c’}^{(L)} - Z_{i, c}^{(L)}] < 0$ (i.e., the model generalizes in expectation); this is necessary to make a mathematically rigorous statement about degree bias via tail bounds. Thus, we cannot make $\\sum_{l = 0}^L \\beta_{i, c’}^{l)}$ more positive to increase $R_{i, c’}$, as this would violate the assumption of our theorem. However, intuitively, it also would not make sense that RW and SYM reduce the misclassification error for a node by predicting its neighbors to be of a different class, since message passing smooths the representations of adjacent nodes. \n\nFurthermore, per lines 153-154, “$\\beta_{i, c’}^{(l)}$ measures the expected prediction score for nodes j, weighted by their probability of being reached by a _length-l random walk_ starting from i.” Because $\\beta_{i, c’}^{(l)}$ depends on the distribution of random walks from $i$, it is intimately related to local graph structure. Indeed, $\\beta_{i, c’}^{(l)}$ can be interpreted as a “local subgraph difference” and is highly influenced by the local homophily of $i$ (as we say in lines 170-174). However, $\\beta_{i, c’}^{(l)}$ is also influenced by the presence of $l$-hop neighbors contained in the training set, as the model is more likely to correctly classify these nodes by a large margin (lines 172-173); hence, $\\beta_{i, c’}^{(l)}$ does not _only_ boil down to local homophily. When revising our paper, we will include and expand on these clarifications on the similarities and differences between $\\beta_{i, c’}^{(l)}$ and local homophily, to provide better intuition from a topological perspective.\n\n(6) We can add some analysis for distribution shifts. For example, our results in Section 4 can be built upon to show that shifts in local homophily from train to test time reduce test-time prediction performance, which can bring $\\beta_{i, c’}^{(l)}$ closer to 0; this can increase $R_{i, c’}$, thereby not inducing as much degree bias.\n\n(7)  We will make the training loss visualizations in Figure 2 larger. The primary takeaway from this figure is that, in the case of RW and ATT, the training loss curves for low and high-degree nodes (including error bars) overlap during the first ~20 epochs of training; however, for SYM, the loss curve for high-degree nodes descends more rapidly than the curve for low-degree nodes.\n\nRegarding the weaknesses:\n\n(1) Could you please elaborate on which experimental results are “not supportive of claims?” We would like to address or clarify any potential mismatches between our theoretical analysis and experiments.\n\n(2) Please see (5) above.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Yi1BLMEsZt", "reviewer": "Reviewer_Xp6E", "summary": "The paper explores the causes and characteristics of degree bias in graph neural networks (GNNs), particularly in node classification tasks. It contributes to the field by providing a rigorous theoretical analysis supported by empirical evidence across multiple datasets, revealing that degree bias is influenced by factors such as homophily and diversity of neighbors. The study also proposes a structured approach to mitigate this bias, enhancing the fairness and effectiveness of GNN applications in social and recommendation systems.", "questions": "1. How does homophily relate to degree bias? I expect some conclusions in this paper but cannot find them.\n\n2. The \"expected similarity of the neighborhoods\" in section 5 is very similar to the similarity matrix defined in [5]\n\n3. The criteria proposed in section 6 should be verified in real-world datasets.\n\n\n\n\n[5] Revisiting heterophily for graph neural networks. Advances in neural information processing systems. 2022 Dec 6;35:1362-75.", "limitations": "the authors adequately addressed the limitations", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "originality: medium\nquality: good\nclarity: good\nsignificance: medium", "weaknesses": "Some degree-related papers should be included and discussed in this paper, for example:\n\n[1] takes a unified view to explain the over-smoothing and heterophily problems simultaneously by profiling nodes with two metrics: the relative degree of a node (compared to its neighbors) and the node-level heterophily.\n\n[2] investigates how does node degree, homophily and class variance influence the node distinguishability.\n\n[3] finds that the effectiveness of graph convolution operations in enhancing separability is determined by the Euclidean distance of the neighborhood distributions and the square root of the average node degree. Furthermore, they find that topological noise negatively affects separability by effectively lowering the average node degree.\n\n[4] observes that the prediction accuracy of high-degree nodes is usually significantly lower under heterophily and the hypothesis that \"nodes with higher degrees are naturally favored by GNNs\" no longer holds. In fact, the degree-wise bias is more sensitive, but not necessarily beneficial, to high-degree nodes with regard to varying graph conditions.\n\n\n\n[1] Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. In2022 IEEE International Conference on Data Mining (ICDM) 2022 Nov 28 (pp. 1287-1292). IEEE.\n\n[2] When Do Graph Neural Networks Help with Node Classification? Investigating the Homophily Principle on Node Distinguishability. Advances in Neural Information Processing Systems. 2024 Feb 13;36.\n\n[3] Understanding Heterophily for Graph Neural Networks. In Forty-first International Conference on Machine Learning.\n\n[4] Liao N, Liu H, Zhu Z, Luo S, Lakshmanan LV. Benchmarking Spectral Graph Neural Networks: A Comprehensive Study on Effectiveness and Efficiency. arXiv preprint arXiv:2406.09675. 2024 Jun 14.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback and the helpful resources! Regarding the weaknesses, we will definitely include and discuss the recommended references on homophily in our paper:\n\n[1] provides a complementary perspective on the possible performance issues of GNNs that arise from degree disparities in graphs (e.g., low-degree nodes induce oversmoothing in homophilic graphs, while high-degree nodes induce oversmoothing in heterophilic networks). Oversmoothing is related to prediction homogeneity $(\\sum_{l = 0}^L \\beta_{i, c’}^{(l)})^2$ (line 149); for homophilic networks, as the number of layers in a GNN increases (i.e., as oversmoothing occurs), $(\\sum_{l = 0}^L \\beta_{i, c’}^{(l)})^2$ gets closer to 0 (i.e., does not increase $R_{i, c’}$), thereby not inducing as much degree bias. In contrast, our theoretical analysis demonstrates that degree bias occurs without oversmoothing and is amplified by high local homophily (lines 170-171).\n\n[2] connects node distinguishability to node degree and homophily by analyzing the intra-class vs. inter-class embedding distance. We discuss similar quantities in lines 175-189 and lines 208-226, and will integrate connections to [2] in these discussions. However, with the exception of Section 3.5, [2] considers the CSBM-H model in its theoretical analysis, which has pitfalls (as we discuss in lines 79-83). Moreover, unlike our work, [2] does not explicitly link the misclassification error of a node to its degree in a more general data and model setting.\n\n[3] analyzes the effect of heterophily on GNNs via class separability, which it characterizes through neighborhood distributions and average node degree. Like with [1] and [2], we will discuss connections between prediction homogeneity, homophily, and separability. Notably, similar to [2], [3] only considers the HSBM model in its theoretical analysis.\n\n[4] observes that GNN performance is lower for high-degree nodes under heterophily. We likewise observe this in Figure 5 for Chameleon and Squirrel (which are heterophilic networks), and we will connect this observation to [4]. Moreover, our theoretical analysis explains why degree bias is not observed for heterophilic graphs; in lines 220-222, we explain that high-degree nodes in heterophilic networks do not have lower $l$-hop prediction homogeneity levels due to higher local heterophily, hence we do not necessarily observe better performance for them compared to low-degree nodes. We would additionally like to note that [4] was released on 4 Jun 2024, which was after the NeurIPS submission deadline on 22 May 2024.\n\nRegarding your questions:\n\n1. We make connections between homophily and degree bias in the paper. For example:\n- Lines 170-171: We show that to amplify degree bias, we need to make $R_{i, c’}$ larger, for which it is sufficient to make the prediction homogeneity $\\sum_{l = 0}^L \\beta_{i, c’}^{(l)}$ more negative, “e.g., when most nodes in the $l$-hop neighborhood of $i$ are predicted to belong to class $c$.” This can occur when node $i$ has high local homophily.\n- Lines 175-179: Our proof of Theorem 2 shows that, in expectation, $\\overline{RW}$ “produces similar representations for low and high-degree nodes with similar L-hop neighborhood homophily levels.” However, low-degree nodes have a higher representation variance (due to a lower inverse collision probability), which can amplify degree bias. This entails that factors beyond homophily (e.g., diversity of neighbors) induce degree bias.\n- Lines 208-214, 222-226: Our proof of Theorem 3 likewise shows that for SYM, homophily alone does not induce degree bias.\n-  Lines 220-222: We explain that high-degree nodes in heterophilic networks do not have lower $l$-hop prediction homogeneity levels due to higher local heterophily, hence we do not necessarily observe better performance for them.\n- Lines 693-696: We explain that models do not learn more rapidly for high-degree nodes under heterophily (Figures 11-12) because the “features of nodes in the neighborhoods of high-degree nodes and training nodes are dissimilar.”\n\n2. The similarity matrix defined by [5] is _post-aggregation_, while our matrix is _pre-aggregation_. Moreover, our similarity matrix is an interpretable quantity that naturally arose during our theoretical analysis. We are happy to cite [5].\n\n3. We perform extensive validation of the criteria in Section 6 on 8 real-world datasets:\n- Figure 3 and the plots in Section G show strong positive associations between inverse collision probability and degree for the RW, SYM, and ATT filters, and Figure 1 and the plots in Section E show strong negative associations between degree and test loss for the homophilic datasets. Hence, we validate that there is a negative association between inverse collision probability and test loss.\n\n- The lack of degree bias observed in Figure 5 for Chameleon and Squirrel (which are heterophilic networks), compared to Figure 1 and the other plots in Section E, confirms our theoretical finding that under heterophily, the prediction homogeneity for high-degree nodes is closer to 0, so high-degree nodes do not necessarily experience better performance.\n\n- Figures 2, 6-10 empirically confirm our theoretical finding that disparities in the expectation and variance of node representations are responsible for performance disparities. Figures 11-12 suggest that smaller distributional differences among representations (due to heterophily) can alleviate degree bias.\n\n- Figure 2 and the plots in Section F empirically validate the training discrepancies between low and high-degree nodes that we theoretically analyze in Section 5.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5WFHhP4aLh", "reviewer": "Reviewer_USpG", "summary": "The paper provides a comprehensive analysis of the origins of degree bias in message-passing GNNs, proving that high-degree test nodes have a lower probability of misclassification, regardless of how GNNs are trained.  They surveyed 38 papers on degree bias and found that existing hypotheses are often not rigorously validated and can be contradictory.  They also show that some GNNs may adjust their loss on low-degree nodes more slowly during training, but with sufficient training epochs, these models can achieve their maximum possible training accuracy. The theoretical findings are validated on eight real-world networks, and a roadmap to alleviate degree bias is proposed.", "questions": "Please address the questions regarding weaknesses.", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "+This paper explores the important issue of the origins of degree bias in Graph Neural Networks (GNNs). \n\n+The authors conduct a comprehensive survey on degree bias, carefully identifying and validating existing hypotheses while pointing out those that are contradictory or lack validation. \n\n+The study examines the effects of different graph filters and analyzes degree bias separately during both test time and training time. \n\n+The paper provides a thorough theoretical analysis and supports its claims with empirical studies on eight datasets.", "weaknesses": "-It appears that the findings in this paper are limited to homophilous graphs, as the results do not extend to heterophilic graphs, according to the paper's analysis. \n\n-The current analysis is based on graphs with a single edge type. Can these findings be expanded to heterogeneous graphs, where the edges can have different types? It could be worth studying to explore this possibility.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your thoughtful feedback and questions! Regarding the weaknesses and your questions:\n- Our findings do extend to heterophilic graphs. For example, in Lines 220-222, we explain that high-degree nodes in heterophilic networks do not have more negative L-hop prediction homogeneity levels due to higher local heterophily, hence we do not necessarily observe better performance for them; we empirically validate that there is a lack of degree bias for the heterophilic datasets Chameleon and Squirrel in Figure 5. Furthermore, in lines 693-696, we explain that models do not learn more rapidly for high-degree nodes under heterophily (Figures 11-12) because the “features of nodes in the neighborhoods of high-degree nodes and training nodes are dissimilar.” None of our theoretical analysis assumes homophilic networks. We will clarify any parts of the paper that suggest that our theoretical analysis does not encompass heterophilic networks.\n\n- We agree that it is valuable to study the possibility of expanding our findings to heterogeneous graphs. For example, in our literature survey, we cover works that establish the issue of degree bias for knowledge graph predictions and embeddings (e.g., [4, 38]). Furthermore, we state in Section K, “it remains to identify the shortcomings of our theoretical findings for heterogeneous and directed networks.” Our theoretical analysis is general and covers diverse message passing GNNs, and can be extended to heterogeneous networks if messages aggregated from different edge types are subsequently linearly combined. In this setting, $R_{i, c’}$ can be computed as the sum of the prediction homogeneity quantities $(\\sum_{l = 0}^L \\beta_{i, c’}^{(l)})^2$ for each edge type divided by the sum of the collision probability quantities $\\sum_{j \\in {\\cal V}} [(P_{rw}^l)_{i j}]^2$ for each edge type.\n\n[4] Stephen Bonner, Ufuk Kirik, Ola Engkvist, Jian Tang, and Ian P Barrett. Implications of topological imbalance for representation learning on biomedical knowledge graphs. Briefings in Bioinformatics, 23(5):bbac279, 07 2022.\n\n[38] Harry Shomer, Wei Jin, Wentao Wang, and Jiliang Tang. Toward degree bias in embedding based knowledge graph completion. In Proceedings of the ACM Web Conference 2023, WWW ’23, page 705–715, New York, NY, USA, 2023. Association for Computing Machinery.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qaFcxmVeNY", "reviewer": "Reviewer_Vv7z", "summary": "The authors consider the problem of degree bias for node classification using graph neural networks (GNNs). Much prior work has shown that GNNs tend to be much more accurate for nodes with higher degree than for lower degree. The authors survey 38 papers that pose hypotheses, sometimes contradictory, for why this degree bias exists. In this paper, the authors provide theoretical analyses on linearized versions of message-passing GNNs using random walk (RW) and symmetric (SYM) graph filters. Their bounds yield some insights on the origins of degree bias at both test time and training time and provide evidence to support some hypotheses from prior work but not others. Finally, they run experiments using the RW, SYM, and graph attention (ATT) filters on a variety of data sets, confirming their theoretical results. They conclude by providing some criteria that mitigation strategies for degree bias should target.", "questions": "1. Of the four target criteria you present in Section 6, is there any ordering or predicted importance that you would recommend future work to target?\n2. I noted the lack of a relationship between inverse collision probability and node degree as a weakness. Do you have any potential leads on whether it would be possible to bound this based on other quantities in the graph? This would allow your theoretical results to potentially be \"end to end\".", "limitations": "Limitations are discussed in the supplementary material. The paper would be strengthened if a short summary of the main limitations (maybe 2 or 3 lines) could be added to the conclusion.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- Provides a very general theoretical analysis on the misclassification probabilities of nodes using message-passing GNNs with RW and SYM graph filters.\n- Empirical results support predictions from theoretical results.\n- Theoretical and empirical results yield insights as to what types of mitigation strategies for degree bias may be most effective.\n- Thoroughly explores hypotheses for degree bias in the existing literature and connects the theoretical results in this paper to provide evidence for some hypotheses and against others.\n- Excellent use of hyperlinks to guide reader back and forth between portions of the supplement, figures, and body text. I really enjoyed reading this paper and would likely have found it much more frustrating if I had to navigate back and forth manually.\n- Addresses a topic of great interest to the NeurIPS community, as illustrated by the large body of recent work on the topic.", "weaknesses": "- Theorem 2 bounds the squared inverse coefficient of variation $R_{i,c^′}$ based on the inverse collision probability $1/\\sum_{l=0} \\alpha_i^{(l)}$. There is no relationship or bound on the inverse collision probability as a function of node degree beyond a single layer, with the authors providing only empirical results. Thus, the theoretical results are not \"end to end\", with this one link between misclassification probability and node degree missing.\n- Analysis is for linearized versions of GNNs and not the GNNs themselves.\n\nMinor presentation issues:\n- Error bars in Figure 1 and similar figures in Appendix E are not explained in the figure caption. I see that they are explained later in the beginning of Section 3. I suggest adding (or moving) the description to the figure caption.\n- Figure 2: Caption lists FAIR ATT, but those plots are not shown.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful comments and positive reception! Regarding the weaknesses:\n\n- This is a great and interesting question! We agree that it would be beneficial to close this missing link. Via some preliminary analysis, we find that it is possible to express the inverse collision probability (i.e., express the sum of $l$-hop collision probabilities) in terms of $D_{i i}$. In particular, we can show: $\\sum_{l = 0}^L \\alpha_i^{(l)} = \\alpha_i^{(0)} + \\sum_{l = 1}^L \\sum_{j \\in {\\cal V}} [(P^l_{rw})\\_{i j}]^2 = 1 + \\frac{1}{D^2\\_{i i}} \\sum_{l = 1}^L \\sum_{j \\in {\\cal V}} [\\sum_{k \\in {\\cal N(i)}} (P^{l - 1}\\_{rw})\\_{k j}]^2$. As before, we can see that the inverse collision probability is larger (and thus $R_{i, c’}$ is larger) when $D_{i i}$ is larger, and $\\sum_{l = 1}^L \\sum_{j \\in {\\cal V}} [\\sum_{k \\in {\\cal N(i)}} (P^{l - 1}\\_{rw})\\_{k j}]^2 \\in o(D_{i i}^2)$. However, because $\\sum_{k \\in {\\cal N(i)}}$ depends on $D_{i i}$, this expression does not completely isolate the impact of $D_{i i}$ on the inverse collision probability. A similar expression can be derived for SYM by expressing: $P_{sym} = D^{\\frac{1}{2}} P_{rw} D^{-\\frac{1}{2}}$. \n\nAnother proof route that was considered was via the following bound: $\\sum_{l = 0}^L \\alpha_i^{(l)} \\leq \\sum_{l = 0}^\\infty \\alpha_i^{(l)}$, as then we can plug in the steady-state probabilities of uniform random walks on graphs. However, as $l \\to \\infty$, $(P^l_{rw})\\_{i j} = D_{j j} / 2 |{\\cal E}|$ only depends on $D_{j j}$ (not $D_{i i}$ as desired). It is also possible to upper bound the inverse collision probability as: $1 / \\sum_{l = 0} \\alpha_i^{(l)} \\leq 1 / (\\alpha_i^{(0)} + \\alpha_i^{(1)}) = 1 / (1 / D_{i i} + 1)$, which is in terms of $D_{i i}$; however, we cannot use this upper bound to lower bound $R_{i, c’}$.\n\nWe will continue ideating about: (1) better bounds for the inverse collision probability in terms of $D_{i i}$, or (2) an impossibility result for a bound that isolates the effect of $D_{i i}$ on $R_{i, c’}$. This being said, our paper argues that the inverse collision probability is a more fundamental quantity that influences what the community has termed “degree bias” than degree alone, which is positively associated with the inverse collision probability.\n\n- It would be interesting as future work to investigate the effects of nonlinearities on degree bias. Towards this, a possible option is to assume that node features are drawn from a Gaussian distribution and derive high-dimensional asymptotics for degree bias in _non-linear_ GNNs using the Gaussian equivalence theorem, as in [1].\n\n[1] Ben Adlam, Jeffrey Pennington Proceedings of the 37th International Conference on Machine Learning, PMLR 119:74-84, 2020.\n\n- Thanks for catching the presentation issues. We will move the explanation of the error bars to the caption of Figure 1 and the captions of the figures in Appendix E. We will likewise remove “FAIR ATT” from the caption of Figure 2.\n\nRegarding your questions:\n1. We recommend that future work target criteria 2 and 3 (lines 291-294) first. These criteria are important because they reflect (to a large extent) inherent fairness issues with the graph filters that are popular in the graph learning community. For instance, the random walk and symmetric filters disadvantage low-degree nodes by yielding representations with high variance and low magnitude, respectively. It is valuable for the community to investigate filters that are adaptive or not restricted to the graph topology in a way that ensures that low-degree nodes are not marginalized through disparate representational distributions or poor neighborhood diversity.\n\n2. We discuss potential leads above to bound the inverse collision probability in terms of node degree. The collision probabilities themselves are intimately related to (more global) properties of the graph; for instance, via eigendecomposition, $[(P^l_{rw})\\_{i j}]^2 \\leq \\lambda^{2 l}$, where $\\lambda < 1$ is the eigenvalue of $P_{rw}$ with the largest magnitude [2]. Then, the inverse collision probability is strictly greater than $\\frac{1}{\\sum_{l = 0}^L |{\\cal V}| \\lambda^{2 l}}$. \n\n[2] Lovasz, L. M. Random walks on graphs: A survey. 2001.\n\n3. We will definitely detail the main limitations of our paper in the conclusion of the camera-ready version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their thoughtful and helpful comments! We are pleased to read that:
- Reviewer Ao8B finds our paper constitutes a “systematic investigation of a long-standing yet not addressed research problem.”
- Reviewer Xp6E finds our paper has good quality and clarity.
- Reviewer USpG finds our paper “provides a thorough theoretical analysis and supports its claims with empirical studies on eight datasets.”
- Reviewer Vv7z finds our paper “provides a very general theoretical analysis on the misclassification probabilities of nodes” and “really enjoyed reading this paper.”

We address the weaknesses and questions raised by each reviewer in individual responses below.

Meta-review: This paper provides theoretical results to justify why Graph Neural Networks perform better for high-degree nodes. The authors place their theoretical findings in the context of previously proposed hypothesis for the origins of degree bias. They validate their findings on real-world networks and give a sketch of how to tackle degree bias. The reviewers find the studied problem to be an important and timely one. The authors should incorporate the suggestions made by the reviewers to strengthen the paper.
Decision: Accept (poster)