Uncovering the Structural Fairness in Graph Contrastive Learning
Authors: Ruijia Wang
Xiao Wang
Chuan Shi
Le Song
Venue: NeurIPS 2022 Accept (2022)
Keywords: Degree Bias
Graph Contrastive Learning
Graph Neural Networks

Abstract: Recent studies show that graph convolutional network (GCN) often performs worse for low-degree nodes, exhibiting the so-called structural unfairness for graphs with long-tailed degree distributions prevalent in the real world. Graph contrastive learning (GCL), which marries the power of GCN and contrastive learning, has emerged as a promising self-supervised approach for learning node representations. How does GCL behave in terms of structural fairness? Surprisingly, we find that representations obtained by GCL methods are already fairer to degree bias than those learned by GCN. We theoretically show that this fairness stems from intra-community concentration and inter-community scatter properties of GCL, resulting in a much clear community structure to drive low-degree nodes away from the community boundary. Based on our theoretical analysis, we further devise a novel graph augmentation method, called GRAph contrastive learning for DEgree bias (GRADE), which applies different strategies to low- and high-degree nodes. Extensive experiments on various benchmarks and evaluation protocols validate the effectiveness of the proposed method.

Uncovering the Structural Fairness in Graph Contrastive Learning
Ruijia Wang', Xiao Wang"", Chuan Shi! Le Song²
Beijing University of Posts and Telecommunications
2 BioMap and MBZUAI
(wangruijia, xiaowang, shi chichuan)@uupt edu. en, songle@biomap.com
Abstract
Recent studies show that graph convolutional network (GCN) often performs worse for low-degree nodes, exhibiting the so-called structural unfairness for graphs with Long-tailed degree distributions prevalent the real world. Graph contrastive learning (GCL), which marries the power of GCN and contrastive learning, has emerged as a promising sulf-supervised approach for learning node representations. How does GCL behave in terms of structural fairness? Surprisingly, we find that representations obtained by GCL methods are already fairer to degree bias than those learned by GCN, We theoretically show that this fairness stems from muta-community concentration and inter-community scatter properties GCL, resulting in much clear community structure to drive low-degree nodes away from the community boundary. Based on our theoretical analysis, we further devise a novel graph augmentation method, called GRAph contrastive learning for DEgree bias (GRADE), which applies different strategies to low- and high-degree nodes. Extensive experiments on various benchmarks and evaluation protocols validate the effectiveness the proposed method.
Introduction
Despite their strong expressive power in graph representation learning, recent studies reveal that the
performance of vanilla graph convolutional network (GCN) 17 exhibits structural unfairness [25]
16. which is primarily beneficial to high-degree nodes (head nodes) but biased against low-degree nodes (tail nodes). Such performance disparity alarming and causes performance bottleneck, given that node degrees of real-world graphs often follow a long-tailed power-law distribution [2].
38 has been promising paradigm in graph domain, which integrates the power of GCN and contrastive leaning [13 5 10]. In nutshell, these methods typically construct multiple views via stochastic augmentations the input, then optimize the GCN encoder by contrasting positive samples against negative ones. Inheriting advantages of contrastive learning, GCL relieves graph representation learning from human annotations, and displays state-of-
Graph contrastive learning (GCL) 30
the-art performance in variety of tasks 35
12 39 36
Will GCL present the to surprisingly find out that GCL methods are better at maintaining structural fairness where a smaller performance gap exists between tail nodes and head nodes than that of GCN. This finding suggests that GCL has the potential to mitigate structural unfaimess. Based on this finding, a natural and fundamental question arises: why is graph contrastive learning fairer degree bias? A well- informed answer can yield profound insights into solutions to this important problem, and deepen our understanding of the mechanism of GCL.
strucfure unfairness GCN? For this purpose, conduct experiments
"Corresponding authors.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

10
20.4"
10.00011xx00000 50.5
00000014x+ 0.744
0000016xx0.7400
Degne
(a) GCN on Cora
(b) DGI on Cora
(c) GraphCL on Cora
1.0
1.0
1.0
0.8-
0.8
0.0
$ 200
3.8.0
204
204
yo 11135xx005500 5544
ym 10000000000
ym0.01 08x00
25
25
25
10
20
Degree
Degree
Dogree
(d) GCN on Citeseer
(c) DGI on Citeseer
GraphCL on Citeseer
Figure 1: Visualization for the fairness of models to degree bias. Blue scatters refer to the average accuracy (Avg. Acc.) of specific degree group. Orange dotted lines are regression lines of blue scatters in each figure. For clarity, we annotate analytical expressions of regression lines. The higher the average accuracy of tail nodes and the smaller the slope of the regression line indicate that the model fairer to degree bias.
Intuitively, graph augmentation provides an opportunity for tail nodes to generate more within- community edges, making their representations closer to those with the same community via the contrastive framework. These refined representations drive tail nodes away from the community boundary. Theoretically, we prove that node representations learned by GCL conform to a clearer community structure by Intra-community Concentration Theorem [ and Inter-community Scatter Theorem
@ These theorems are relevant to two crucial components in GCL. One is the alignment of positive pairs, which is exactly the optimization objective. The other is the pre-defined graph augmentation, determining the concentration of augmented representations. Based on the analysis, we establish the relation between graph augmentation and representation concentration, implying that well-designed graph augmentation can promote structural fairness by concentrating augmented representations.
To take step further, we propose a GRAph contrastive learning for DEgree bias (GRADE) based on novel graph augmentation. To make augmented representations more concentrated within communities, GRADE enlarges limited neighbors of tail nodes to contain more nodes within the same community, where the ego network of the tail node interpolates with that of the sampled similar node. As for head nodes, GRADE purifies their ego networks by removing neighbors from different communities. Extensive experiments on various benchmark datasets and several evaluation protocols validate the effectiveness of GRADE.
In summary, our contributions are four-fold:
We are the first to discover that GCL methods exhibit more structural fairness than GCN, which has a smaller performance disparity between tail nodes and head nodes. This discovery inspires a new path for alleviating structural unfairness based contrastive learning.
We theoretically validate the reason for structural fairness GCL is that GCL stimulates intra- community concentration and inter-community seatter. Therefore, tail nodes are farther away from the community boundary for better classification.
Based on theoretical insights, we propose a method GRADE to further improve structural fairness by enriching the neighborhood of tail nodes while purifying neighbors of head nodes.
Comprehensive experiments demonstrate that our GRADE outperforms baselines on multiple benchmark datasets and enhances the fairness to degree bias.

---

2 Exploring the Behavior of Graph Contrastive Learning on Degree Bias
Real-world graphs in many domains follow a long-tailed distribution in node degrees, i.c., significant fraction of nodes are tail nodes with small degrees. It is well known that GCN often performs worse accuracy for tail nodes. Here aim to study how GCL behaves under degree bias.
Experimental Setup We take two representative GCL algorithms DGI [30] and GraphCL 33 as examples to analyze the performance disparity under degree bias. Specifically, we train DGI and GraphCL on four benchmarks Cora [17]. Citeseer [7]. Photo [23] and Computer [23], and leverage early stopping based the training loss. To compare with GCN, our linear evaluation protocol deploys the sumi-supervised split [17]. where 20 labeled nodes per class form training set and test set
composes of randomly sampled 1000 nodes with degrees less than 50. GCN follows the standard
training paradigm [17] with the above train-test split. Further implementation details and chosen hyper-parameters deferred to Appendix A
Results To illustrate the fairness to degree bias, we group nodes of the same degree and calculate the average accuracy of these degree groups separately shown in Figure To further visualize how the model balances the performance between tail nodes and head nodes, we fit these seatters with linear regression. If the slope of the regression line is flat, the model is fair to degree bias. More results on Photo and Computer datasets can seen in Appendix [ From the figure, we can find that the average accuracy for tail nodes of GCL methods DGI and GraphCL is higher than that of GCN, and the slope of the regression line is also smaller. These interesting observations suggest that label-indepenn GCL methods are actually fairer than GCN under degree bias.
3 Analysis on the Structural Fairness of Graph Contrastive Learning
Based the above observations, natural and fundamental question arises: where does this structural fairness stem from? We first define some preliminary notations, then provide a theoretical analysis to explain this question.
3.1 Preliminary Notations
Let = EV, X) be a graph, where V the set of N nodes {VI, U2, ,N & x V the set of edges, X = [1,, 22,- ............. [N] E R represents the node feature matrix and æ; is the feature vector of node vy- The edges can be represented by an adjacency matrix E {0, 1) XN where Au 1 iff (v,, 11)) E E. Given unlabeled training nodes, each node belongs to one of K latent communities C1, C2., CK. Assuming the augmentation set T consisting of all transformations on topology, the set of potential positive samples generated from ego network Gi of node is denoted as (G,). The goal of GCL is to learn a GCN encoder f such that positive pairs are closely aligned while negative pairs are far apart. Here we focus topological augmentation and single-layer GCN,
f(;)) ReLU (L,XW),
(I)
where L, is the i-row of transition matrix I. Dー1 Á, = A + I is self-looped adjacency matrix and Du E3 Aij is degree matrix. We consider community indicator F,
Fy( arg minl) 1xll
kε[K]
where Mk E,,ec, E [f((.)] is the community center, and || stands for Ig-norm. To quantify the performance of Fy, the error can be formulated as
K
Err(F/)
Σ ((.)
+ k, Ve, C.).
(3)
With the above definitions, we denote S. (wz UK Ck+ vgJ 8 E I(G)))
-
e) as the set of nodes with g-close representations among graph augmentations.
3.2 Theoretical Analysis
We assume the nonlinear transformation has M M-Lipschitz continuity, i.e., ||(())) - f(,))
(Lx ReLU M L |, and graph augmentations are uniformly
3

---

sampled with m augmented edges P(g: = T(G.)) 1/C(N 1, m)). Let there be ball of radius 3m such that for any augmentation || - L,XI1 S 3m, where L is the augmented transition.
Theorem Intra-community Concentration. Let pre-transformation representations LX be sub- Gaussian random variable with variance o². For all nodes vs E Se. if I 8m
6M their repre-
sentations f(Gi) fit lub-Gaussian distribution with variance 07.2 S + with K. Z where k. is coefficient that reflects the degree of concentration.
This theorem builds a relation between the intra-community concentration of final representations and the alignment positive pairs in S., Specifically, cormmmmmmmttttty concentration requires smaller By decreasing the distance between positive pairs, GCL fits the requirement.
Next, we demonstrate that GCL also maintains the property of inter-community scatter for community assignment. For given augmentation set T, we first define the augmentation distance between two nodes as the minimum distance between their pe-transforrmaton representations,
A d.
A dj
min dr (U;, Uz) &
min &.TT(O)),,ETIIC))
|X|,
(4)
where A, is the i-row of augmented adjacency matrix Å, and d, is the augmented node degree. Based on the augmentation distance, we further introduce the definition of (a,, (,,,7 (.)77.d)aumeeee -d-ammmmetttiion to measure the concentration pre-transformation representations.
Definition (a, d)-Augmentation. The augmentation set T is a (a, 7, d ",d)),,aaeeeeeee auugmentationn, if for each community Ck. there exists subset C2 C₁ such that the following two conditions hold
1. Pl 0g] aFlu: E Ck] where 10,
2. sup (7 1z) S 7(
B ) where y (0.
min
where d w.C d, and B is the feature dimension.
Larger a and smaller 7 B/dd indicate teetrransformation representations are more concentrated. We assume that the representation is normalized by (f()) and let Pı: = P[rr E Ca.. Then we simultaneously bound the interccommunity distance and the error of the community indicator.
Lemma For a (at, d) -augmentttiio with subset CK of each community Cs. if nodes belonging to (C+ U... CC n SSS can correctly assigned by the community indicator F,, then the error of all nodes can be bounded by (1 - a.) + Rg, where Rg = P[S.] is the proportion of complement.
The above lemma presents sufficient condition guarantee the performance of the community indicator. Then we need to explore when nodes in (C) U... C% SSS can be correctly assigned by Fy.
Lemma 2 For a (a,, 7, (...T,dddaummttttn augmentattin and each E [K], if
p pk < (1-(1- pela,,,,ee) 2pelpa d,E)) 22" A4)
holds for all k + then every node E Cf can be correctly assigned by the community indicator Fy. where pe(a, 2(1 - ai) 2R. + al MrVB + 23 and D, 1 minke[k] || //22.
"V min
Combining Lemma and we can obtain the Inter-community Scatter Theorem as follows.
Theorem Inter-community Scatter. For (a, 7, (a.,,d)aauua auggeeetttniinn, if
Nd Pk r2 Pmax 7, d, V 22maxx 7, d. A
(5)

---

holds for any pair of (e, k) with & # k. then the error of the community indicator Fj can be bounded by (1 a) + Rs, where Pmax d,E) E) = 2(1 a)) maxt and D = min ///x11//r2
2R=
+
MarvVB
+ 200
r
For the better assignment, the RHS of Equation 27
should approach r², implying that smaller
Pa Y: d,E) E) is required. We further bound R. by the alignment objective of contrastive loss.
Theorem The term Rg is upper bounded by
IC(N 11, 1,m) E., ( f(
Rg S
(6)
We direct the readers Appendix for proof of all the above lemmas and theorems. The combination of Theorem and Theorem B indicates that the inter-community distance and the error of community indicator are controlled by two key factors. 1) The alignment of positive pairs. Good alignment en- (efec))ll((()))))) ( f(" resulting in small R. 2) The concentration of augmented representations, where sharper concentration implies larger a in Definition 1 Small Rg and large directly decrease the error bound of community indicator, and provide small Prenxe (ax 7r d, s) for unter-community scatter. is worth mentioning that the first factor the contrastive objective GCL, reflecting the reason for structural faimesss in the GCL framework. While the second factor depends on the graph augmentation. Thus, we are motivated to propose a graph augmentation designed for further concentrating augmented representations.
ables small ggg (T())
4 GRADE Methodology
In this section, we present our novel GRADE framework dedicated to degree bias in detail, starting with the special graph augmentation, followed by the objective GCL.
4.1 Graph Augmentation
We generate two augmentations G1 and G₂ by simultaneously corrupting the original feature and topology to construct diverse contexts [36 26). We denote node representations in these two
augmentations H f(1)) and O f(G2).
Topology Augmentation To obtain more concentrated augmented representations, we aim to increase intra-community edges while decreasing inter-community edges. Due the different structural properties of tail nodes and head nodes, we design different topology augmentation strategies for them shown in Figure 2 In order to expand the neighborhood of tail nodes to include more same-commume nodes, we interpolate the ego network of the anchor tail node Ptail with that of sampled similar node Usample- To prevent injecting many different-communni neighbors, regulate the interpolation ratio depending on the similarity between Vtail and Usample. For head nodes, purify their neighborhood by similarity-basee sampling remove inter-community edges.
Formally, we build the similarity matrix S' between node pairs based on cosine similarity of their representations, Sij = sim h,; hj) for i & j and Sü = 0 otherwise. For any tail node Itail, we sample a node Usample from the multimodal distribution Multi(Stoa), where Stail is the row vector of S corresponding to Vtoil. Then we construct new similarity-aware neighborhood for Utail by interpolating between neighbor distributions Vtast and Utarget. Here, the neighbor distribution for node is defined as p(u)v) v) 1/) if (v) and p(ulv) detrimental connectivity, the similarity sim (heas Nsample) is used as the interpolation ratio ø,
otherwise. To avoid the
Psomple (u) (aart ) = (1 ()p(u()taa) + dp (p((uleamppe))
The interpolation ratio & decreases as the similarity between Vtait and Usample decreases, and we guarantee (1 ②) to be at least 0.5 to preserve the original neighborhood. Given the neighbor distribution Psample (u) (tau), we sample neighbors from it without replacement. The number of neighbors is sampled from degree distribution except tail nodes to keep degree statistics.
5

---

Psampte
Tail Nodes
Interpolation
Head Nodes
Merge
(b) Purification
Plond
(a) Interpolation
(b) Purification
Comb.
Lonn
p(u))
Sample
Prompte (M (Mnn))
Bample)
Topology augmentation in GRADE. Different augmentation strategies designed for tail nodes and head nodes. Tail nodes obtain more intra-community edges by interpolation, while head nodes remove inter-community edges via purification.
Figure 2:
For each head node Whead, we define the similarity distribution for purification. Specifically, the similarity distribution for node is Pesm (u (u v) sim(h h.) if (w) and p(ulv) otherwise. Based on the similarity distribution Paim (ul (u/Uhead), we sample dhead Pedr) neighbors without replacement, where Pedr the edge drop rate. Through this sampling, edges dissimilar nodes tend to be removed, thereby retaining effective neighborhood information.
Feature Augmentation We randomly sample mask vector E (0, 10 hide fraction of dimensions in node feature. Each element in mask m sampled from a Bernoulli distribution Ber(1 Pfár), where the hyperparameter Pydr dr the feature drop rate. Thus, the augmented node feature is computed by
X [ m, 22 m...., .NN m).
In implementation, set threshold Ç to distinguish tail nodes and head nodes. The same hyperparameters Pfdr and Pedr used to generate augmentations G and G2-
4.2 Optimization Objective
We employ a contrastive objective 38 on obtained node representations of two graph augmentations. For node H; node representations h, and o; from different graph augmentations form the positive pair, and node representations of other nodes in two graph augmentations are regarded as negative pairs. Therefore, define the pairwise objective for each positive pair (h; 0:) as
E(h,, o.) = log (lh,,o)/7
+ Exg o2h, + Enps (bu,)
where is a temperature parameter. The critic 0(h, o) is defined as sim(g(h), ((0),, where the projection g is two-layer multilayer perceptron (MLP) enhance the expression power (5). The overall objective to be maximized is the average of all positive pairs,
1 2N
Σ
[( 0.) - ((o,,
(10)

---

Table 1: Quantitative results (%) on node classification. (bold: best; em dash: out-of-memory)
Cora
Citeseer
Photo
Computer
Micro-F1
Macro-F1
Micro-FI
Macro-P1
Micro-F1
Macro-FI
Micro-F1
Macro-FI
GCN
82.30 76.87=034
65,841055
59.62sus4
93.52+0a2
78.88=201
89.14 89.144
Supervised Split
DG1
82.28
77.23=030
65.64
59.47
92.98a112
78.83
88.96=006
12.30
GraphCL
81.78=0.57
76.01=1m
65.16+1m
58.72+137
GRACE
82.322045 76.78=4x2
64.1622m
59.732194
93.122040
78.60
88.222104
71.74
MVGRL
83.22=1.00 17.84_135
66.261am
60.302095
94.10gaa1
78.362222
CCA-SSG
82.70 77.35_106
65.9621
58.81
94.362005
19.34
89.22.209
13.822190
GRADE
83.40.0.0 18.54_..15
67.14
61.04
94.72.a.00
78.86g2m
89.42.205
74.71.190
Semi Semi- sepni-sserrvseedddee Split
GCN
74.18 69.84_0.6
53.80
50.15
91.04
65.47
78.58
61.80.:.43
DGI
75.92 70.04=055
54.52+14
51,92
90.781075
66.27
79.00
62,00
GraphCL
75.68=2.4 69.86-141
54.06#1.0
51.75#175
GRACE
75.12=141 69.66-1.99
53.564342
49.83
91.12+031
6..07
79.10=1.7
61.76
MVGRL
76.44 7..
56.84+126
53.79#125
92.01
66.16=2.1
CCA-SSG
75.74
71.70-1.9
17.90
14.70
91.6820.50
=
82.20
65.04
GRADE
77.20=0.44 73.37
-1.2
59.44
$6.47
92.0
66.62+2.
82.50=1.04
67.50+1.0
5
Experiments
Datasets For a comprehensive comparison, we use four real-world datasets to evaluate the perfor- mance of node classification and the fairness to degree bias. Specifically, we choose two categories of datasets: 1) citation networks including Cora [17] and Citeseer [17]. 2) social networks Photo (23
and Computer (3 from Amazon. The statistics of these datasets are summarized in Appendix C
Evaluation Protocol We compare GRADE with state-of-the-art GCL. models DGI
30
GraphCL. (35]. GRACE (38), MVGRL 112 and CCA-SSG (36), and semi-supervised baseline GCN 17 for reference. For GCL models, we follow the linear evaluation scheme introduced in (30), where each model is firstly trained in an unsupervised manner and node representations are subse- quently fed into simple logistic regression classifier. We adopt two universally accepted splits for full evaluation: 1) semi-supervised split (30 351 that 20 labeled nodes per class are for training and 1000 nodes are for testing, 2) supervised split (38 36) that 1000 nodes are for testing and the rest of nodes form the training set. It is worth noting that 1000 nodes in the test set are randomly sampled with degrees less than 50 to provide an appropriate degree range for analysis. GCN is trained by the original paradigm [17 with the above train-test split. We refer readers of interest to Appendix C on details of experiments, including implementation and hyperparameters.
5.1 Main Results and Analysis
Node Classification We train each model for 10 independent trials with different seeds, and report mean and standard deviation results in Table [ We observe that the proposed GRADE outperforms all baselines in most cases. The improvement of GRADE is more pronounced on Cora and Citeseer datasets, where average node degrees around and a large number of tail nodes exist. Additionally, we find that GCL models tend to outperform GCN in the semi-supervised split, suggesting that GCN may benefit more from end-to-end training with more supervision.
To verify that GRADE improves the classification performance of tail nodes and also retains the performance of head nodes, we divide test nodes of Cora into tail nodes and head nodes based on the threshold Ç. We draw average accuracy w.r.t. degree of GRADE and competitive baselines as violin plots in Figure 3 The subsequent experiments default to the supervised split if not specified. As expected, GRADE achieves obvious performance gain regardless of tail nodes or head nodes.
Fairness Analysis In order to quantitatively analyze the faimess to degree bias, we define the group mean as the mean of degree-specific average accuracy while the bias the variance. Mathematically,
Avg. Acc. (kk) [([Acc(e:), V node e such that d, =]]], G.Mean = EE[AAg Acc. (k),V node degree k}}, Bias = Var([Avg. Acc. V node degree k.)..
7

---

Table 2: Quantitative results (%) fairesss analysis.
Cora
Citeseer
Photo
Computer
G. Meant
Biax
G. Meant
Bias
G. Meant
Bias
G. Meart
Bias
GCN
86.04
1.70
84.00
1.85
97.41
0.28
96.30
0.50
DGI
89.26
0.67
84.79
1.71
98.23
0.27
96.94
0.45
GraphCL
90.80
0.59
84.13
1.80
GRACE
89.91
0.70
85.44
1.67
98.28
0.23
96.92
0.47
MVGRL
91.01
0.54
83.86
1.83
98.39
0.27
CCA-SSG
90.86
0.63
84.35
1.73
98.44
0.24
97.17
0.39
GRADE
92.87
0.48
85.88
1.52
98.52
97.42
0.35
Based on these metrics, evaluation results are shown in T can be seen that GRADE reduces the bias across all datasets and maintain the highest group mean. Moreover, graph contrasting learning models have a smaller bias compared to GCN, conforming to our previous study in Section 2
Visualization To demonstrate that GRADE pulls same-community node representations more concentrated, we visualize node representations of GRADE and competitive baselines on the Cora dataset in Figure Particularly, learning baselines always depict more crisp boundaries than GCN, where blue nodes are still scattered in space. In GRADE, they are finally clustered together, illustrating that the proposed augmentation design exerts a vital part.
zoom into one specific community colored blue. Graph contrastive
5.2 Ablation Study and Hyperparameter Sensitivity
Ablation Study of Sampling Recall that GRADE augments tail nodes by sampling nodes for interpolation, and also sample edges to remove the purification of head nodes. We alter the augmentation by fixing the most similar node (without random interpolation) top-dheadd Pear) similar nodes (without random deleting) to validate the effectiveness of these sampling processes. Results of the ablation study Cora and Citeseer datasets are reported in Table We can observe that GRADE consistently better than the remaining variants. Such a phenomenon implies that reasonable randomness provides more diverse node contexts to contrast out essential features.
Effect of Threshold We investigate the impact of threshold Ç used to split tail nodes and head nodes on classification performance. Figure (a) shows the test Micro-F1 w.r.t. different Ç on Cora dataset. The performance benefits from an applicable selection of Ç. When Ç is too small, the neighbor sparsity of tail nodes cannot be mitigated; if it is too large, noise is injected.
Effect of Drop Rate We perform sensitivity analysis on feature drop rate dr and edge drop rate dedr which control the generation of graph augmentations. We vary these hyperparameters from 0.5 in node classification on the Cora dataset. The results are shown Figure 4 (b). It can be observed that the performance is relatively poor when the hyperparameter d is too large and dedr too small. We infer that if the djár is too large, the original graph is heavily undermined to contain useful information; and if the dedr is too small, the large number of neighbors makes the perturbation of different augmentations too insignificant to achieve the purpose of contrast.
200
204
224 MASSEL CCA-6G GRADS
GCV VOGAL COA-SGG GRADE
11
(a) Tail nodes
(b) Head nodes
(a) Threshold
(b) Drop rate
Figure Violin plots of the average accuracy w.r.t. node degree for (a) tail nodes and (b) head nodes on the Cora dataset. The box inside the violin indicates 25-75 percentiles, and the median shown by a white scatter.
Figure The hyperparameter sensitivity of GRADE with varying (a) threshold and (b) drop rate on Cora dataset. In (b), the lighter color rep- resents better performance, and the red scatter highlights the peak.

---

(a) GCN
(b) MVGRL
(c) CCA-SSG
(d) GRADE
Figure 5: Visualization of node representations learned by competitive baselines and GRADE on Cora dataset. Color denotes the community of nodes and size represents the node degree. Black boxes highlight one community colored by blue as an example.
Table 3:
Ablation study (%) on the sampling of GRADE. (w/o RI: without random interpolation; w/o RD: without random deleting)
Cora
Citeseer
Micro-FI7
Macro-FI*
G. Mean"
Bias)
Micro-F1t
Macro-F11
G. Meart
Bias.
w/o RI
83.00
77.97
90.86
0.55
66.10
61.02
84,96
1.80
w/o RD
82,30
76.50
90.54
0.60
65.90
58.83
84,21
1.84
w/o RI+RD
82.00
75.82
89.97
0.63
65.80
59.29
83.00
1.95
GRADE
84.30
92.87
0.48
68.80
64.21
85.88
1.52
6 Related Work
Graph Neural Networks Graph neural networks (GNNs) 18 32 31 can be generally divided into spectral methods and spatial methods. Specifically, spectral methods learn node representations based on graph spectral theory. 3 first proposes a spectral graph- based extension of convolutional networks, and GCN [17] simplifies ChebNet [6] by the first-order approximation. Spatial methods directly define graph convolution in the spatial domain. GraphSAGE [I1] learns aggregators by sampling and aggregating neighbors, and GAT 29) assigns different edge weights during aggregation. We refer readers to recent surveys [34] 377 for more comprehensive review. On the other hand, some literature 25 33 21 shows that there is structural unfairness between tail nodes and head nodes in GNNs. Existing explorations [20 16 focus on supervised settings, ignoring the great potential of self-supervised learning on this problem.
Graph Contrastive Learning Being popular in self-supervised visual representation learning 28 27 13 15), contrastive learning obtains discriminative representations by contrasting positive and negative samples. Inspired by the local-global mutual information maximization viewpoint [1], DGI (30) and InfoGraph (4 first marry the power of GNNs and contrastive learning. Following them, MVGRL [22 introduces the node diffusion to the graph contrastive framework. GRACE [8 GCA 33 and GraphCI. (35] learn node representations by treating other nodes as negative samples, while BGRL. 26 proposes a negative-sample-free model. CCA-SSG [36] optimizes a feature-level objective other than instance-level discrimination. There are several surveys 19] summarizing recent advances in graph contrastive learning. Despite their remarkable achievements, there is no graph contrastive learning targeting the fairness of degree bias.
7 Conclusion
In this paper. we bring to light the prospect of GCL to alleviate structural unfairness for node representation learning. We discover that node representations obtained by GCL methods are fairer to degree bias than those learned by GCN, and explore the underlying cause of this phenomenon. Based on our theoretical analysis, we further propose novel GCL model targeting degree bias.
Limitations and Broader Impact A limitation of GRADE is its heuristic design, therefore an interesting direction for future work is to extend GRADE into learnable graph augmentation. Our work investigates the structural fairness GCL for the first time and points out the great potential of GCL for this problem. Considering that most real-world graphs follow the long-tail distribution, the studied problem is practical and important. Additionally, our work deepens the understanding the learning mechanism of GCL, and may inspire more future research on structural faimess.


Reviews:
[{"review_id": "FaUYrGGcNoq", "reviewer": "Reviewer_5815", "summary": "This paper studies structural fairness on graph contrastive learning (GCL). The study is motivated by the finding that GCL is fairer to low degree nodes than GCN. Based on that, the authors first present theoretical analysis on such structural fairness for GCL through intra-community concentration theorem and inter-community scatter theorem. Guided by the theoretical analysis, the authors propose GRADE by enriching the neighborhood of tail nodes and purifying the neighborhood of head nodes. Experimental results on real-world datasets demonstrate the effectiveness of GRADE.", "questions": "- How correlated between the community assignment and the node labels? If there are high correlation between them, enhancing intra-community edges and purifying inter-community edges is an intuitive choice to debias.\n\n- Related to the previous questions, does the theoretical analysis implicitly assume the graph to be of high homophily? What would be the performance on graphs with heterophily?\n\n- For GCN in this paper, does it use the random walk graph Laplacian or the commonly used symmetrically normalized graph Laplacian? \n\n- How would the theoretical results change if we use the symmetric normalized graph Laplacian (as in original GCN) rather than random walk graph Laplacian?\n\n- What is the \\kappa in Theorem 1? \n\n- (Just some random thoughts) Rather than bringing high-level idea (enhancing intra-community edges and purifying inter-community edges) to methodology design, can we have more insights from the theoretical analysis? For example, is it possible that the bounds for intra-community concentration and inter-community scatter could help us identify what a good augmentation should look like? Then we can sample/augment edges guided by these bounds.\n", "limitations": "- More understanding on the performance for graphs with heterophily is needed. \n\n- There are too many notations in the paper. The authors may want to find a way to organize them so the readers won't need to check notations back and forth.\n\n- The authors should make sure the theorems are self-contained.\n\n- Significance test on the experimental results would be helpful to showcase the effectiveness of GRADE.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is well-motivated through empirical experiments.\n- The design of the proposed method is inspired from theoretical analysis.\n- The proposed method is effective in mitigating structural unfairness as shown by experimental results.\n\nWeaknesses:\nPlease see below.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "F4tHSMDyppI", "reviewer": "Reviewer_VyUL", "summary": "This paper investigates the great potential of graph contrastive learning to solve the degree-bias problem, and proposes a new graph augmentation for further improvement.", "questions": "1. Do other semi-supervised GNNs suffer from the same severe degree-bias problem?\n2. Some simplifications have been made in the theoretical analysis. For example, they only consider topology augmentation. Does it affect the analysis results?\n3. There is only one train-test split in Section 2, but two in Section 5.\n4. The complexity of the proposed model.\n", "limitations": "The authors have pointed out the limitations of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The motivation of this paper is clear. They discover that node representations obtained by GCL methods are fairer to degree bias than those learned by GCN, and explore the underlying cause of this phenomenon. Based on the theoretical analysis, they further propose a novel GCL model targeting the degree bias. Experimental results clearly show the merit of the proposed model, and the source code is attached (I have not run it though).\n\nConcerns:\n1. This paper focuses on semi-supervised GCN to motivate their investigation. Do other semi-supervised GNNs suffer from the same severe degree-bias problem? In other words, I doubt the finding is limited.\n2. Some simplifications have been made in the theoretical analysis. For example, they only consider the topology augmentation. Does it affect the analysis results?\n3. There is only one train-test split in Section 2, but two in Section 5.\n4. The complexity of the proposed model.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BdM4Al8kNyC", "reviewer": "Reviewer_va2A", "summary": "GCN is primarily beneficial to high-degree nodes but biased against low-degree nodes, which causes a performance bottleneck. As a promising paradigm in the graph domain, GCL integrates the power of GCN and contrastive learning, displaying SOTA performance in a variety of tasks. This paper investigates the question of whether will GCL present the same degree of bias as GCN. They surprisingly find out that a smaller performance gap exists between tail nodes and head nodes in GCL methods than that of GCN.\n\nThey intuitively and theoretically analyze the reason for this interesting finding. Particularly, Intra-community Concentration Theorem and Inter-community Scatter Theorem prove that node representations learned by GCL conform to a clearer community structure, and establish the relation between graph augmentation and representation concentration. These analyses yield profound insights into solutions to this important degree-bias problem and imply that GCL is a promising direction.\n\nTherefore, they further propose a GRAph contrastive learning for DEgree bias (GRADE) to concentrate augmented representations. Specifically, they enlarge limited neighbors of tail nodes to contain more nodes within the same community and purify head nodes by removing neighbors from a different community. Extensive experiments on various benchmark datasets and several evaluation protocols validate the effectiveness of GRADE.\n", "questions": "Q1: How to get a small degree of bias from a clear community structure?\nQ2: Why is the supremum in Definition 1 \\gamma(\\frac{B}{\\hat{d}_{\\min}^k})^{\\frac{1}{2}}? Based on this definition, how to prove that the proposed GRADE reduces this supremum?\nQ3: There is a lack of significant test results in Table 1.\n\n", "limitations": "A learnable augmentation is an interesting direction for improvement.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written in general and their finding is exciting.\nWeaknesses:\n1.\tHow to get a small degree of bias from a clear community structure needs more explanations. Theorem 1 and 2 prove that GCL conforms to a clearer community structure via intra-community concentration and inter-community scatter, but its relationship with degree bias is not intuitive enough.\n2.\tThere is some confusion in the theoretical analysis. Why is the supremum in Definition 1 \\gamma(\\frac{B}{\\hat{d}_{\\min}^k})^{\\frac{1}{2}}? Based on this definition, how to prove that the proposed GRADE reduces this supremum?\n3.\tThere is a lack of significance test in Table 1.\nDespite the weaknesses mentioned above, I believe that this paper is worth publishing. They consider an important degree-bias problem in the graph domain, given that node degrees of real-world graphs often follow a long-tailed power-law distribution. And they show an exciting finding that GCL is more stable w.r.t. the degree bias, and give a preliminary explanation for the underlying mechanism. Although the improvement does not seem significant in Table 1, they may inspire more future research on this promising solution.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6nbwisTc_Si", "reviewer": "Reviewer_x4f1", "summary": "Node degrees of real-world graphs follow a long-tailed distribution, but GCN exhibits a performance disparity between high-degree nodes and low-degree nodes, i.e., degree bias. This paper discovers an interesting phenomenon that graph contrastive learning methods have already a smaller degree bias.  Based on this discovery, this paper theoretically analyzes the reason and proposes a tailored contrastive learning method GRADE. Experiments validate the effectiveness of the proposed method.\n", "questions": "1. Is the conclusion only suitable for GCN? I wonder GAT may exhibit a smaller degree bias, even smaller than graph contrastive learning methods.\n2. From Figure 6 in Appendix A, the advantage of graph contrastive learning methods over GCN on Photo dataset is not obvious.\n3. How does a clear community structure lead to a smaller degree bias?\n4. The improvement of the proposed method in Table 1 does not seem statistically significant because of high variance. And the related works designed for degree bias are not set as baselines in the experimental comparison.\n", "limitations": "In addition to the limitations mentioned in the paper, the generalization of the conclusion should be taken into consideration.", "rating": 7, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1.\tThe finding is interesting and may inspire a new paradigm for alleviating degree bias.\n2.\tThe paper is well-written and the conclusion is clear.\nWeakness:\n1.\tThe conclusion seems to be only for GCN. I wonder GAT[1] may exhibit a smaller degree bias, even smaller than graph contrastive learning methods.\n2.\tFrom Figure 6 in Appendix A, the advantage of graph contrastive learning methods over GCN on Photo dataset is not obvious. The numerical values of their slopes are close.\n3.\tThere is a small gap between degree bias and theoretical analysis of clear community structure.\n4.\tThe improvement of the proposed method in Table 1 does not seem statistically significant because of high variance.\n5.\tThere are some related works designed for degree bias, such as SL-DSGCN[2]. But these methods are not set as baselines in the experimental comparison.\n\n[1] Veličković P, Cucurull G, Casanova A, et al. Graph Attention Networks[C]//International Conference on Learning Representations. 2018.\n[2] Tang X, Yao H, Sun Y, et al. Investigating and mitigating degree-related biases in graph convoltuional networks[C]//Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 2020: 1435-1444.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept