Understanding Class Bias Amplification in Graph Representation Learning
Authors: Shengzhong Zhang
Wenjie Yang
Yimin Zhang
Hongwei Zhang
Zengfeng Huang
Venue: Accepted by TMLR ()

Abstract: Recent research reveals that GNN-based graph representation learning may inadvertently introduce various structural biases. In this work, we discover a phenomenon of structural bias in graph representation learning called class bias amplification, which refers to the exacerbation of performance bias between different classes by GNN encoder. We conduct an in-depth theoretical study of this phenomenon from a novel spectral perspective. Our analysis suggests that structural disparities between nodes in different classes result in varying local convergence speeds for node embeddings. This phenomenon leads to bias amplification in the classification results of downstream tasks. Based on the theoretical insights, we propose random graph coarsening, which is proved to be effective in dealing with the above issue. Finally, we propose an unsupervised graph contrastive learning model called Random Graph Coarsening Contrastive Learning (RGCCL), which utilizes random coarsening as data augmentation and mitigates class bias amplification by contrasting the coarsened graph with the original graph. Extensive experiments on various datasets demonstrate the advantage of our method when dealing with class bias amplification.

Published in Transactions on Machine Learning Research (12/2025)
Understanding Class Bias Amplification in Graph Represen- tation Learning
Shengzhong Zhang
Saahang@nua..ddu.cr
College of Computer Science and Technology Nanjing University of Aeronautics and Astronautics
Wenjic Yang"
yanguj24 @mm.fudan. edu.cn
School Data Science, Fudan University
Yimin Zhang
giminnhhnng200@@uulnn.....
School of Date Science, Fudan University
Hongwei Zhang
zhanghaw. hranghuu..onggueS@mmaai.cc
School of Data Science, Fudan University
Zengfeng Huang"
huangafffuudnn.edu.. edu..cr
School of Data Science, Fudan Universily Shanghoi Innovation Institution
Reviewed on OpenReview: ht tps:: // en re net mft//ffn or 34 Sq DU
Abstract
Recent research reveals that GNN-based graph representation learning may inadvertently introduce various structural biases. In this work, we discover a phenomenon of structural bias in graph representation learning called class bias amplification, which refers to the ex- acerbation of performance bias between different classes by GNN encoder. We conduct an in-depth theoretical study of this phenomenon from novel spectral perspective. Our anal- ysis suggests that structural disparities between nodes in different classes result in varying local convergence speeds for node embeddinggs. This phenomenon leads to bias amplifica- tion in the classification results of downstream tasks. Based on the theoretical insights, we propose random graph coarsening, which is proved to be effective in dealing with the above issue. Finally, we propose an unsupervised graph contrastive learning model called Ran- dom Graph Coarsening Contrastive Learning (RGCCL), which utilizes random coarsening as data augmentation and mitigates class bias amplification by contrasting the coarsened graph with the original graph. Extensive experiments on various datascts demonstrate the advantage of our method when dealing with class bias amplification.
Introduction
Graph reprosentation learning (GRL) aims to generate embodding vectors capturing both the structuro and feature information. Graph neural networks (GNNs) are the primary encoder architecture for GRL [Bojchevski Günnemann 2018 Zhu et al. 2020 2021 Zhang al. 2021 Zheng al. 2022 Yang al, 2026), which are often trained with unsupervised graph contrastive objectives. Such methods are called graph contrastive learning (GCL) and exhibit outstanding performance in various downstream tasks. Compared to traditional unsupervised GRL methods(Peroze et al. 2014 Grover & Leskoved 2016). the distinctiveness of GCL lies in the GNN encoder's use of message passing. Due to the encoder's 's use of message passing, the final embeddings are likely to inherit the structural bias in the graph, which may cause undesirable performance
* *Corresponding authors.

---

Published in Transactions on Machine Learning Research (12/2025)
0.8.
0.8
0.6
Actureey
0.6
0.7
0.7
0.6
0.4
0.4
0.5
0.5
0.2
02
Cleos
(a) MLP on Cora
(b) SPAN on Cora
(c) MLP on Citeseer
(d) SPAN on Citeseer
Figure 1: The classification performance of MLP and SPAN in different classes on Cora and Citescer, where each class has 20 labeled nodes in the training set. A represents the maximum performance difference observed between classes.
unfairness in downstream tasks. This phenomenon demonstrated in Figure 1 where we compare the node classification performance of MLP (utilizing feature information only) and the state-of-the-art GCL model SPAN (Lnn et al. 2023). Although SPAN has much better overall accuracy than MLP, SPAN exhibits greater performance differences between different classes of nodes. In other words, GNN-based GRL exacerbates the performance bias between different classes.
We refer to the phenomenon exhibited in Figure 1 as class bias amplification. This exacerbated bias arises from local structural disparities between nodes in different classes and is unrelated to other information. Graph structural bias problems have been studiod in previous works (Tang et al., 2020 Kang al.] 2022; Liu et al., 2023b Wang et al. 2022). However, they focused on the structure of individual nodes such degrees and the distance to class boundaries. Class bias amplification studied in this work should also be distinguished from the class inbalance problem (Song et al. 2022). Although both consider the collective bias of class, works on class-imbalanced classification focus on (semi- jumpriispeeeieed learning and aim to reduce prediction bias caused by imbalanced label distributions. However, class bias amplification occurs in GNN- based GRL and is present even when the label distribution is balanced.
This paper investigates the following two questions: 1. Why class bias amplification ewists in eristing GNN- based GRL methods? 2. Can we design new unsupervised GRL models to alleviate this issue? To answer the first question, analyze the structural bias problem from spectral perspective, which provides theoretical explanation on the causes of class bias amplification in existing GNN-based GRL models. There have been numerous works conducting spectral analysis of GNNs, e.g., (Kipf & Welling 2017 Wu et al. 2019 Oono & Suzuki 2020 Rong et al.) 2020). However, cxisting analyscs mainly focus on the global behaviour: They try to characterize the distribution of node representations using the spectrum of the message passing operator. We point out that this not suitable when structural bias exists across different regions the graph. If the number of layers in a GNN is not too large as prevalent in real applications, and we define community nodes that belong to the same class, then the embedding distributions of different communities are better characterized by their local spectrum. In particular, if the structures of two communities differ a lot, then the second largest eigenvalues of their normalized adjacency matrices can be quite different, which leads to very different convergence speeds to the stationary subspace. As a result, the embedding distributions of the two communities exhibit different levels of concentration. We then show that such an embedding concentration discrepancy can cause unfairness in downstream tasks through a natural statistical model.
Based on the theoretical analysis, we then locus on how to alleviate the class bias amplification. We propose simple data augmentation technique, namely random graph coarsening, and provide theoretical justifi- cations on the effectiveness. We finally propose an unsupervised graph contrastive learning model, called Random Graph Coarsening Contrastive Learning (RGCCL), which utilizes random graph coarsening as data augmentation and uses a contrastive loss that compares the coarsened graph with the original graph. Em- pirical results on real datasets show our model effectively reduce performance disparities between different classes and also achieves botter overall accuracy than basclines, confirming our thcoretical analyses.
Our contributions summarized follows:
2

---

Published in Transactions on Machine Learning Research (12/2025)
1. We uncover the class bias amplification in the graph and analyze the causes of this problem from spectral perspective. We show that local structural bias leads to embedding concentration discrep- ancy, which is harmful on downstream tasks in terms of fairness.
We show that an appropriately designed random graph coarsening algorithm can be used as an effective data augmentation tool for alleviating the issue of embedding density imbalance.
3. Based on our theoretical analysis, we propose novel GCL model RGCCL. Our model mitigates class bias amplification by comparing the coarsened graph with the original graph.
We compare RGCCL with other graph representation learning models in various datasets. Empirical experiments and quantitative analysis demonstrate the advantage of RGCCL, which confirms the effectiveness of using random coarsening to mitigate class bias amplification.
2 Preliminaries
Notation. Consider an undirected graph G = EV E)), where V represents the vertex set, E denotes the edge set, and X RR*D is the feature matrix. Let n = |V| and m |E| represent the number of vertices and edges, respectively. We use A {0, 1] to denote the adjacency matrix of G and {or uj} to denote the undirected edge between node v, and node vy.- The degree of node e, denoted de is the number of edges incident on ei. The degree matrix D is a diagonal matrix and its i-th diagonal entry is d;
Graph neural network.In In each layer of a GNN, the representation of a node is computed by recursively aggregating and transforming representation vectors of its neighboring nodes from the last layer. One special case is the Graph Convolutional Network (GCN) (Kipf Welling 2017). The layer-wise propagation rule of GCN is:
H(++) =o o (D- AD - #H(
(1)
where À = A+I D+I and W is a learnable parameter matrix. GCNs consist of multiple convolution layers of the above form, with each layer followed by an activation a such as Relu.
Graph coarsening. The coarse graph is a smaller graph G' = X'). G' is obtained from the original graph by computing a partition P of V. The partition can be represented by a binary matrix P E {0, 1] 1]"xn', with P.j = 1 if and only if vertex belongs cluster j. We define as the set of super-node and for each super-node i 8, St as the set of nodes that make up the super-node i. Lu the index of which supernode node belongs to.
Convergence of Graph Neural Networks There has been lots of work investigating the asymptotic behavior of GNNs as the number of layers L goes to infinity, e.g., (Oono & Suzuki 2020 Rong et al.) 2020). The general conclusion is that as L + co, the representations of all nodes converge to a 1-dimensional subspace, assuming the graph G is connected. The convergence speed is determined by the second largest eigenvalue of the message passing operator Á. Following the notation from Oono & Suzuki (2zu))((2000).. we denote the maximum singular value of W(l) by wi and set w := maxte[[) Wi and assume that W(() of all layers are initialized so that w < 1. Given subspace M, use dı := infyem||X -|||p to measure the closeness between X and M, where || l| denote the Frobenius norm. Oono & Suzuki (2020) shows that if G is connected, there is a 1-d subspace M such that for all
dm(H)+)) S (H",,
(2)
which means the embeddings of all nodes collapse to M exponentially fast.
3 Exploring Class Bias Amplification
In this section, we analyze the reasons for class bias amplification. We initially explore how local structural biases result in discrepancies in embedding concentration. Then, we demonstrate that such discrepancies can cause unfairness in classification tasks.
3

---

Published in Transactions on Machine Learning Research (12/2025)
3.1 Illustration of Embedding Concentration Discrepancy
In real applications, the number of layers L is typically small. In these cases, the asymptotic results from 2q. do not provide accurate predictions of the model behavior. In particular, they ignore structural differences between different regions of the graph. Here, we illustrate the problem through a simple example. We consider the following example. There are two classes of nodes in the graph, which form the communities C1 and C2, with all nodes within each community belonging to the same class. C₁ is more densely connected than C2, and there are only loose connections between them (see the Figure 2 Then, the expression of the symnetrie normalized adjacency malrix Å can be succinctly represented using block matrix as follows:
[A Bi Ag)
where the matrix is partitioned according to C1 and Cz. By the assumption, || and ||
Bg
are close to 0, and since C1 has a better connectivity than C2 the second largest cigenvalue of Å1, denoted by X(Ai) is smaller than X(A2) (Chung & Graham 1997). According to (2), the representations of all nodes converges to M with speed exponential in X(4). A more detailed analysis presented below shows that, the two communities exhibit different convergence speed the first few layers, due to different local connectivities.
Original Graph 2(A) 94
Embedding Space
GCN
Communily 6₁
Community C2
Community G ((A)) 0.50
Community Cz
A(42)
Figure 2: simple example of embedding density imbalance.
Following the message passing mechanism in Eq. the representations for community C1 and C2 can be defined as (((+1) = (A, + H, and H = (A
(y (((),, respectively. Since ||Bi||e and ||B very close to 0, the impact of H ((+1) and H1 on H!!t!)) is very small. Based on the result of Oono Suzuki 2020). we have:
{ am(Hr((t))) = d s w> dmnHtbttl se d (2H( S (AMA))d
(3)
When the number of iterations relatively small as in many real applications, the effects B, and Bg can be ignored, and the embodding distributions of different regions ( and dx are much better characterized by local connectivity 3 Therefore, the embedding density of each community is primarily determined by nodes that constitute the community.
If the structure of communitics C₁ and C2 differs dramatically, for example, X(A,) & A(A2), then after L layers of message passing, we have d ( < d)(H)(")) This means the embeddings of nodes in C1 will be much more concentrated than those in C2. In other words, the disparity in local convergence speeds leads to an imbalance in local embedding densities. Figure provides an example of this phenomenon. We sample
feature vectors for nodes in C1 and C2 from normal distributions, NO _
and N N
1 1
respectively. We then apply a 2-layer graph convolutional network, and the resulting embeddings of the nodes are visualized. Even though the node features for C1 and C2 are sampled with the same variance, the variance of their embeddings differs due to the convergence bias resulting from the distinct structures.
To further illustrate the differences in the variances of their embeddings, we provide more quantitative analysis based on the contextual stochastic block model (CSBM) (Deshpande et al. 2018). CSBM is widely

---

Published in Transactions on Machine Learning Research (12/2025)
used statistical model for analyzing expressive power of GNNs (Baranwal et al. 2021 Wu et al. 2022 We consider a two-block CSBM denoted as (n,,Pi, P2, 9. M1, M2, o²). Here, A E T represents the adjacency matrix of the graph, and X E gaxd represents the feature matrix. In this model, for any two nodes in the graph, the intra-class probability is denoted as p: (i = 1, and the inter-class probability is denoted as q. Additionally, each node's initial feature is independently sampled from a Gaussian distribution N N(u, o²).
Our objective to estimate the variance of node embeddings within each class. Formally, we aim to compute:
E
E D D AX B(D-
(4)
Assumption 3.1 (Structural Information). P1,P2, 52( 1 and p1 > P2 > q- Lemma 3.1. Assume that d E logn, n, we have (1 c)llA- EA I |AX EAX s (1 -) EEA with probability at least 1 2 eexp(-ce -ccp-
Proof. Let X E Rexd be the projection matrix which maps each vector A, R" to a d-dimensional vector A,X E Rd. Then according to the Johnson-Tindenstraass lemma (Johnson & Lindenstrauss 1984] given
some tolerance e, it holds with probability at least 1 - 2exp(-cedd).
Lemma 3.2. For a given Erdös-Rényi (ER) graph ((n,)) p), there exists a constant C such that ||A BA| S Cyppp with probability at least 1 - n= for any > 0.
Proof. By using corollary 3.12 from (Bandeira & van Handel 2016 we obtain sharper bounds.
Lemma 3.3 (Sharp concentration, Lemma 3.2 and Theorem 3 from (W et al. 2022 ) There erists a constant C such that for sufficienlly large n, with probability at least 1 Onn"),
C
A - ADD
(5)
Theorem 3.4. Given on CSBM (n, P1,P2, 2 H1, P2, ,2) it holds that for the variance of class I with intra- class probabilily P1 is smaller than the the variance of class II with intra-class probabilily p2.
Proof. According to Lemma 3.1 to measure the variance of node embedding, we just need to consider
A
B
structure influence || - B(D-1))]] By expressing A =
A2 this allows us to focus on ER
B
graph (().p:) for each class separately. Denote Ri = D-111 We have
AA - B(D- A1) and R = D- B(D-1A2)
C < (1 - 62)
C < 1
|1 < (1 (1+
(6)
np
np2
for appropriate G1, C2. It follows that variance of node embedding decreases more rapidly for the denser class. Furthermore, the convergence speed is inversely proportional to the intra-probability Pt-
3.2 From Embedding Concentration Discrepancy to Class Bias Amplification
We have discussed how different local convergence speeds lead to varying degrees of dispersion in local embedding distributions, and next we provide a theoretical justification on why this can lead to class bias amplification in downstream tasks.
To illustrate the issue, consider binary classification problem. Following the setting in Section 3.1 the graph contains two classes of nodes, which form the distinct communities C1 and Cz. We assume that the node embeddings from each community follow a Gaussian distribution. We consider the optimal Bayes classifier for the above model, which is known to be the quadratic discriminant rule.
Definition (Quadratic Discriminant Analysis). For binary classification problem, where class 1 has mean #1 and variance Σ1 and class 2 has mean #2 and varionce Σz. Each sample is drawm from either one with equal probabilily. Given a new sample I, the QDA rule is
1 log det D.
1 (x Mo) T2 (x Mc).
arg 112 2
(7)
2
5

---

Published in Transactions on Machine Learning Research (12/2025)
To simplify the discussion, focus the one-dimensional case, while the results for higher dimensions are similar. More specifically, each sample x is drawn from of) or Mu2,, og) with equal probability, and let y be the label of z. Assume d1 # 02, meaning the data distribution of one class is more concentrated than the other, which models the embodding density imbalance. For this simple case, the optimal classification error can be represented as a closed form.
Proposition 1. For the above QDA classifier, the error probability of samples from class is:
+
P1 P=
-o - -ff) + 20 lo 03))
(8)
02 of
where Y ~ OV -f + (21(0) > 02) -)
to
10 - -2)(o})
10
The classification error probability of class is symmetric and thus omitted. The above expression is quile complicated. To demonstrate the class bias amplification issue, define the degree of class bias max(p1.P2)
K min (P1.2) (larger x means more severe class bias issuc), and investigate how the imbalance in data distribution affects K. To this end, we fix the value of of + ož2 and vary the ratio 01 0//22-
3.0
Pmad/pmm Pminn
2.0
1.5
1.0
0.5
1.0
1.5
2.0
0,/02
Figure 3: Fairness k vs. ratio between variances.
The value и corresponding different ratios is plotted in Figure 3 It evident that as the degree of imbalance in a 0 increases, also increases. That is to say, the degree of imbalance in embedding density grows, the class bias gradually increases well. Overall, local structural differences exacerbate the embedding concentration discrepancy, which further leads to the amplification of class bias in the classifier.
4 Random Graph Coarsening Contrastive Learning
In this section, we first present the main idea and theoretical justifications of random coarsening to alleviate the class bias amplification. Additionally, we propose the Random Graph Coarsening Contrastive Learning (RGCCL) model, which utilizes random graph coarsening as data augmentation.
4.1 Mitigating Class Bias Amplification via Random Coarsening
Our goal is to make the embedding distribution of sparse classes more concentrated. For this to happen, we first randomly partition the graph into clusters S = . St} according to some random process. Let f be a GNN encoder, and f()) be the embedding node u. We define the embedding for a cluster S; as f(S.) = [5. Eves, f(v). We use the loss
1 f(S))) S,ES NES,
ΣΣ
Σ
regularize the GNN encoder, which encourages nodes in each cluster in the random partition to be more concentrated. In the following, first show that if the distribution of the random partition, denoted

---

Published in Transactions on Machine Learning Research (12/2025)
by P, satisfies certain requirements, the above loss has the implicit effect of pushing the embeddings of sparse classes more heavily. Then, we provide specific random partition algorithm, namely random graph coarsening, which meets the requirements.
Following the setting in Section 3.2, we consider a binary classification problem. Assume that for a random partition drawn from P, the probability that two nodes from class (class 2) lie the same cluster is qi (g2), and the probability that two nodes from different classes are clustered together is Q12- We have the following lemma, the proof of which is provided in the appendix A.I]
Lemma 4.1. Let C1 and C2 be the two classes of nodes. Suppose each cluster has the same size 8, then
Ep-p ΣE
sl]f(w) f(S.)1I WES
qq
Σ
I1f(u) f(x)]12 92
E
II((u) f(v)ll
Σ MECL
IIf(u) f(6)i²
Q12
Now suppose C is denser than C2, and by the analysis in Section 3.1 the embeddings in C1 are likely lo more concentrated. To make the embedding densities of C1 and C2 more balanced, from Lemma 4.1 a preferred random partitioning algorithm should satisfy
42 91 > 912
(10)
Here, we design a random graph coarsening strategy to obtain such a reasonable partition, which can satisfy (10p. Due to the homophily principle that similar nodes may be more likely to attach to each other than dissimilar ones, we always merge nodes that are connected by an edge, 412 should be less than q and d2- On average, the degrees of nodes in C2 are lower than Ct. To realize q2 > Q1; we adopted simple probability function w(u, v) t. for random edge selection during coarsening, ensuring higher probability for low- degree nodes to participate in the random coarsening. Specifically, we first compute w(u, v) to construct the weight set Z of all edges, and then determine the edges to be coarsened by randomly selecting edges according to the weight set I.
Therefore, our random graph coarsening strategy iteratively merging two (super) nodes through edge con- traction form more super nodes. Eventually, we can obtain a coarsened graph, where each supernode represents cluster, and the nodes that constitute this supernode belong to the same partition. By contrast- ing the nodes in the original graph with their corresponding supernodes (clusters) in the coarsened graph, we can optimize loss (9) to mitigate class bias amplification. To prevent the formation of large supernodes, we use a threshold limiting the size of supernodes during the coarsening process. A detailed description of our random coarsening algorithm is provided in the appendix A.4.
4.2 Framework of RGCCL
Based on the theoretical insights from Section 4.1 method RGCCT, which can effectively alleviate the issue of class bias amplification. Compared to existing GCL models, the key difference in our approach to use random graph coarscning as the graph augmentation method and specially designed loss function for this framework.
we present a novel multi-view graph contrastive learning
The GCL method generates different views through graph augmentation, and then trains the model param- eters by comparing the node embeddings from different views. The architecture of RGCCL is presented in Figure 4 In our RGCCL, we regard the original graph as one view and the coarsened graph as another view, and then compare the corresponding nodes in these two views. In order to alleviate class bias amplifi- cation, we ncod to push the node embedding f(u towards its corresponding cluster center embedding f(S.) according to the analysis in Section 4.1 Specifically, the super-node embedding computed in the coarsened view is used as the cluster center, and then each node embedding in the original graph and its corresponding
7

---

Published in Transactions on Machine Learning Research (12/2025)
Input Graph
Coarsened Graph
Random
Coarsening
Community C
Community C2
Community
Community C2
Shared Weight
GNN Encoder
GN Encoder
Embedding Space
Embedding Space
Positive Loss
OO
Negative Loss
Community C
Community C2
Community C
Community Cy
Contrastive Loss
Figure 4: The architecture of the proposed RGCCL.
super- node embedding in the coarsened graph is defined a positive pair. By conducting contrastive learn- ing such positive pairs, we make the embedding distribution of sparse classes more concentrated, thereby reducing class bias amplification.
In this work, we use a method different from the previous graph coarsening algorithms (Huang et al. 2021 I
to construct the coarsened feature matrix. A difference is that they construct the new feature matrix simply by summing ie., given a partition matrix P, X' = = Here, a normalization based on degrees is applied: x' p DX, where D' and D are the degree matrices of the two views. The purpose is ensure, as the number of graph propagations goes infinity, the embedding of node and its corresponding supernode in the coarsened view converge to the same point. This computational method is supported by the following upper bound
D. 2,11 /V/ dmmax
(n1) + n' n't))).
(11)
dmin
Here, represents a node in the original graph, while e is its corresponding node in the coarsened graph. We denote the node embeddings learned from the original graph G and the coarsened graph G' as Za and Z respectively. λ2 and X/2 are the second largest eigenvalues in G and G' respectively. dman and dmi are the maximum degree and minimum degree in G and G', respectively. A detailed proof can be found in Appendix A.2
On the other hand, graph coarsening is a method of data reduction, so using random graph coarsening data augmentation can also reduce the resource consumption of GNN training, especially when computing positive and negative sample pairs.
Specifically, we apply the random graph coarsening algorithm to generate one graph augmentation G' (A', x') in each epoch during training. Then, we compute the coarsened graph and original graph embeddings by GNN encoder with shared parameters: H GN x) and Z (NN(A,X,)
Recall that positive pairs are of the form (u, S.), where S, denotes the corresponding supernode of u. So we penalize 2,, Hs. 112. The loss function of positive pairs can be described more concisely in the matrix form. Let Z' = PH, then Z = Hs.. Therefore, the positive pair loss function
Lpss = 2 2 = 2 + 2 2Tr(Z"
(12)
If 7 and 7' normalized appropriately, only need to minimize -2Tr(Z² 7')
8

---

Published in Transactions on Machine Learning Research (12/2025)
Considering that the node embeddings Z derived from the original graph G may encounter imbalance issues, whereas the coarsened graph G' typically exhibits more balanced embedding distribution. Therefore, we do not pick negative pairs from the original graph and only compute a negative pair loss with the coarsened graph. There are various methods for selecting negative pairs and computing the loss; here we use the loss from Zhang et al. (2020), which is derived from the graph partition problem. More specifically, we randomly sample small set of supernode pairs N C V' V and the negative pair loss function is:
Lueg L(ij)N manyldh hyll?
(13)
where and hj are the embeddings of supernodes i and j, and n, and ny are the number of original nodes contained in supernodes and j.
Optimizing Eneg + prs will be difficult due to the huge difference of the scale of Loo and feeg- Therefore, we transform Los into the following form
B Tr(Z ZT)
Cos
(14)
Finally, the loss function of our model is
a L naylh nmm,lh, hyl1? Tr(ZTz')
B
+
(15)
4.3
Generalizability of RGCCL
The generalizability of sell-supervised learning methods has recently been theoretically analyzed in (Huang
et al. 2023 Wang et al. 2022). They characterize it with three properties, namely the concentration of
augmented data, the aligument of positive samples and the divergence of class centers. Huang et al. (2023) also shows that the divergence of class centers is controlled by classic contrastive losses such as InfoNCE and the cross-correlation loss.
Following the proof of Huang et al. (2023). we show that our self-supervised loss Lneg can also upper bounds the divergence of class centers, thus classes will be more separable if our objective is optimized. The theorem is stated as follows, with further details provided in Appendix A.3
Theorem 4.2. Assume that encoder with norm is M Lipschitz continuous. For a given (a, 7, aug- mentation set A, any O and k +
1 PEPl
1 m S
(- 2n2Cneg +(
(16)
where T(C, a, 7, +1.(1111111111111121111111111111 a(1 - - MMaxx / mmin
Mmaxx
))+
K + K-1)
Next we discuss the concentration property of the random coarsening augmentation. First notice that for any two nodes and v, the probability that they are coarsened together is equal to the probability that they are connected by randomly selected edges in the algorithm. Suppose the edges are selected independent and identically with probability p. then the connection probability lower bounded by (lia((), where dia(G) is the diameter of G. Once and are coarsened together at least one coarsened graph, d(u, v) = 0, which means our random coarsening augmentation can be very well-concentrated.
5 Related Work
Contrastive learning on graphs. Contrastive learning is type of unsupervised learning tochnique that learns representation of data by differentiating similar and dissimilar samples. It. has been used
9

---

Published in Transactions on Machine Learning Research (12/2025)
in variety of applications within the domain of graph data. DGI (Veličković et al. 2018) and MVGRL (Hassani & Ahmadi 2020) contrast node embeddings with graph embeddings using loss function based on
mutual information estimation (Belghazi et al. 2018 [jeelm et al.) 2019). GRACE (Zhu et al. 2020) and its variants (Zhu et al.) 2021 You et al. 2020) aim to maximize the similarity of positive pairs and minimize the similarity of negative pairs in augmented graphs in order to learn node embeddings. To counter the performance degradation induced by false negative pairs, CCA-SSG (Zhang et al., 2021) simplifies the loss function by eliminating negative pairs. In order to reduce the computational complexity of contrastive loss, GGD Zheng et al., 2022) discriminates between two groups of node samples using binary cross-entropy loss.
For broader understanding, we recommend that readers refer to the latest surveys (Liu et al. 2023a Xie
et al. 2023).
Structural bias on graphs. Fair graph mining has attracted much more research attention since recent studies reveal that there are unfairness in a large number of graph mining models. Several notions of fairness have been proposed in recent survey (Dong et al. 2023). and structural bias is mainly manifested
as degree bias. Prior studies (Tang el al., 2020 Kang et. al.) 2022: Dong al. 2022 Liu et al.] 2023bb have primarily concentrated on degree bias in supervised graph learning. GRADE (Wang et al. 2022 first focuses on structural bias in unsupervised graph representation learning, mitigating the degree bias issue through a degree-based graph data augmentation method. In view of the wide application of GNN- based graph representation learning, the structural bias problem associated with it should receive more attention from researchers. Existing studies on bias amplification, such as those in computer vision and NLP (Zhao et al. 2017 Wang & Russakovsky 2021 Hall et al., 2022), ; have not considered graph structural bias, and their definitions of bias amplification are primarily based on output distribution shifts rather than structural propagation. Different Differetn from them, we are the first to study the phenomenon of class bias amplification graphs, which specifically captures how initial class imbalances are progressively exacerbated by GNN structures, rather than demographic or attribute biases commonly discussed in prior works.
Graph coarsening. Recently, graph coarsening techniques have been used to address issues in graph neural networks (Fahrbach el al. 2020 Deng el al. 2019 Huang el al.) 2021 Jin el al. 2022: Yang el al., 2025 Graph coarsening with spectral approximation guarantees are studied in (Li & Schild 2018 Loukas 2019
Jin et al. (020). Graph coarsening can reduce the size of graph by combining the similar nodes, then the coarsened graph can be used for downstream tasks related to the graph. Existing graph coarsening techniques primarily strive to maintain the overall graph structure, resulting in a static and downsized coarsened graph. These methods overlooks the local structural bias, and typically involves massive computational costs.
6 Experiments
6.1 Experimental Setup
Datasets. The results are evaluated six real-world datasets Kipp & Welling. 2017 Veličković et al, 2018 Zhu et al. 2021 Hu et al.] 2020), Cora, Citeseer, Pubmed, Amazon Computer, Amazon Photo, and Ogbn-Ariss Graph representation learning shows different degrees of class bias in these datasets. More detailed statistics of the six datasets are summarized in Table 77 On small-scale datasets Cora, Citeseer, Pubmed, Photo and Computers, performance is evaluated on random splits. We select 20 labeled nodes per class for training, while the remaining nodes are used for testing. For Ogbn-Arixv, we use fixed data splits as in previous studies Hu et al. (2020).
Baselines. We compare our approach against ten representative graph embedding models: Deepwalk Per- ozzi et al. 2014), DGI (Veličković et al.] 2018). GraphCL (You et al., 2020), GRACE (Zhu et al. 2020)
GCA (Zhu el al. 2021,, CCA-SSG (Zhang el al. 2021), gCool (Li el al. 2022). GRADE Wang et al. 2022 et al. 2024 For all the baselines,
GGD[Zheng et al. 2022), SPAN [Lin et al. 2023) and PolyGCL
we use the public code released in their previous papers. All models evaluate the learned representations by
training and testing classifiers with the same settings. More experimental details are listed in the appendix
A.5
10

---

Published in Transactions on Machine Learning Research (12/2025)
6.2 Results and Analysis
Table rreporss the node classification performance small datasets. In these data splits, employ Acc and Macro-F1 as metries to assess the overall performance of models. Tf Macro-F1 significantly drops compared to Ace, it indicates that the model's performance is not balanced across different classes. It is evident that the performance of RGCCL outperforms other GRL models within the given experimental framework. Mostly, RGCCL surpasses the runner-up by an advantage of 1%-2%. Notably, although RGCCL's Ace score on the Computers datasct slightly lower than that of CCA-SSG, our Macro-F1 score significantly higher than that of CCA-SSG. This suggests that CCA-SSG has generated significant class bias on Computers. Clearly, our specially designed model can improve the overall classification performance effectively while resolving the issue of class bias amplification.
Table 1: Summary of results in terms of mean node classification accuracy and standard deviation over 50 runs five dat asetss
Method
Cora
Citesoer
Pubmed
Photo
Computers
Ace
Macro-F1
Ace
Macro=F1
Ace
Macro-F1
Ace
MacrosP2
Acc
Macro- P1
Deepwalk
DGI
78:5100.
77.210.9
70.411.0
63.621.4
72.51
72.013.3
87 0..1..
86.2211 1.1
79.711
78.41 1.3
GraphCtI.
78:31 5
76-711.7
70.611.2
61:121.4
71.7115
71.713.6
88 88.311.3
86-7211
79.71
18.011.1
GRACE
74.422.0
12.512.0
68 68.111.0
61.221.1
76.1422
75.812.7
85-111.6
83-521
76.2118
15.211.5
GCA
78.621.2
17.311.2
68.821.5
65.321.4
75-411.
75:3129
87811:2
88.221..
79.1222
77.912.0
CCA-SSG
70.2::1.4
75.02:.4
718+100
66.3=111
76.02288
76.8+2.77
88.74111
86.0=8.2
82.71100
76.0
gCooL
1T:121.1
68.6214
64.021.3
75.0230
T5.322.9
87.213
85.0=14
79.821
78.12:.3
GRADE
81:52:100
80-911.0
67.62:.3
04.2213
74-5277
T4:022.6
87-121/2
80.420.0
13.82
64.723.1
GGD
61.910.1 8
80.5.0.8
70-1
06.221-1
74.7232
74-123.1
65.4214
80-411
80.04 1.2
SPAN
80-7100.8
78.810.7
69-121.2
61-321-1
73-1228
T2.6128
86-11155
61-121-6
764111
75.811.4
PolyCCL
77.45-3.2
76.643.1
09.9#1.4
62.7=113
75.253.4
76.643.1
$6.741.4
84.0=1.8
10.751.
T6.6+1.5
RGCCL
80.211.2
Quantitative analysis. To further demonstrate that RGCCL effectively alleviates the amplification of class bias, we present statistics of the learned representations and compare them with other popular GRL methods. Firstly, we mcasure the concentration of the embedding for each class by calculating their mean distances from the centroid (i.e., Ve ले Eiec || াcT Σiec zi| for class C). Next, we compute the average and standard deviation of Vo across all classes. smaller average value indicates that the representations for each class are more concentrated, which in turn makes the classification boundary casier to learn. A smaller standard deviation suggests more balanced embedding density, which has been shown to be beneficial for classification fairness (as discussed in Section 3.2). In Table 2 present the results of four baseline methods as well as RGCCL on Cora and Citesoer. RGCCL demonstrates not only more concentrated embeddings for each class but also the most balanced embedding density. These results strongly support our theory. Furthermore, we use the Matthew's 's coefficient to measure class bias. Table 3 presents the results of Matthew's coefficient for representative GRL models and our RGCCL. The results indicate that the bias in the embeddings learned by RGCCL is significantly less than that of other GRL models.
Visualization. To further illustrate that RGCCL effectively mitigates the issue of class bias amplification, we have visualized the performance of each model across different classes. For each class, compute the
Table 2: The average and standard deviation of class density. A smaller average indicates higher embedding quality, while a smaller standard deviation suggests less class bias
Cora
Citeseer
Method
Ave
Std
Ave
Std
DGI
0.3782
0.0294
0.3402
0.0255
GRACE
0.2114
0.0252
0.1715
0.0163
CCA-SSG
0.2817
0.1031
0.1672
0.0109
GRADE
0.1983
0.0352
0.2141
0.0243
GGD
0.3183
0.0541
0.3297
0.0329
SPAN
0.3260
0.0323
0.3234
0.0227
RGCCL
0.0942
0.0084
0.1401
0.0097
11

---

Published in Transactions on Machine Learning Research (12/2025)
Table 3: Matthew's coefficient for RGCCL and six baselines.
Cora
CiteSeer
PubMed
DGI
73.01:1.5
61.5111.
57.8:14.3
GRACE
67.911..
60.0.1..0
62.3.3.8
CCA-SSG
74.5+1.6
64.6+1.4
64.0=#411
GRADE
75.7+1.5
62.1+1.3
58.1
GGD
77.0::1.6
64.9112
63.714.1
SPAN
76.910.7
62.4114
60.324.0
RGCCL
78.9
66.310.8
65.6144.
10
3.9
0.8
0.3
0.88
0.6
0.7
0.5-
0.3
ROCCL
GRADE
(a) Cora
(b) Citeseer
(c)
PubMed
Figure 5: Box plots of the average accuracy w.r.t. class for five baselines and RGCCL on the Cora, Citeseer and Pubmed dataset.
average performance of the model in this class and then draw a box plot based on these accuracies. Figure provides a visualization of the node classificatonn accuracy in different classes on the Cora, Citeseer and PubMed. It is clear that our model has the smallest performance difference across different classes, while also having the best overall performance.
Scalability. Another benefit of RGCCL is its small memory usage. This efficiency primarily because the random graph coarsening is preprocessed the CPU, resulting in coarsened graph notably smaller than the original. Experiments were also conducted on the Arxiv dataset, which is large-scale dataset for most GRL models. Larger size makes sub-sampling necessary for training some baselines, but our RGCCL can be trained directly on the full graph. As shown in Table the Acc and Macro-F1 of RGCCT, both exceed those of other baselines.
Figure shows the memory usage of our model and seven mainstream GCL models on Citeseer and Pubmed. RGCCL exhibits the same level of memory usage GGD, which is specifically designed save computation costs; our model benefits from the effective reduction of graph size via random coarsening.
Effectiveness of different coarsening ratios. We studied the effect of random coarsening ratio on model performance. The random coarsening ratio refers to the proportion of the number of nodes reduced relative to the total number of nodes. Table 5 shows the results of differont coarscning ratios. According to our
Table 4: Summary of results terms of accuracy on Ogbn-Arxiv.
Ogbn-Arxiv
Method
Acc
Macro-F1
DGT
68.8+0.2
46.8--0.4
GRACE
68.4+0.1
46.120.3
CCA-SSG
69.8+0.2
46.5+0.6
GRADE
67.710..2
45.0.10.4
GGD
70.7-0..3
48 48.5.10.4
SPAN
70.1100.3
48.7.0.55
RGCCL
71.7:10.1
50.610.2
12

---

Published in Transactions on Machine Learning Research (12/2025)
Memory (M1)
Memory (40)
2006
(a) Cora
(b) Citeseer
(c) Pubmed
Figure 6: The memory usage of baselines and RGCCL on Cora, Citeseer and Pubmed.
observations, the changes in the coarsening rate have a more significant impact on the Macro-F1, The model performs better when the coarsening rate is between 30% and 50%. Tf the coarsened graph too small, it may lead to the loss information in the augmented graph, which could turn cause a decline in the performance of the RGCCL.
Table 5: The performance of different coarsening ratio.
Cora
Citeseer
Pubmed
Ratio
Macro-F1
Acc
Macro- F1
Macro-Fi F1
0.3
83.110.8
82.0.10.8
72.410.9
67.6100.8
77.112.9
76.912.7
0.5
82.8
81810.8
72.410.9
67.7.0.88
77.312.9
77.112.7
0.7
82.510.9
81.41099
72.110.7
67.0.10.7
77.112.8
76.8.1266
0.9
8..410.9
81.1+1.0
72.010.7
66.910.7
77.0::2.8
76.942.6
Table 6: The performance of different loss terms ratio.
Cora
Citeseer
Pubemd
Method
Acc
Macro-F1
Acc
Macro-F1
Acc
Macro-F1
RGCCL
83.1+0.8
82.0
72.4+00.9
67.7+0.8
77.3+2.
77.1
RGCCL w/o fing
80.8+0.9
79.8+0.8
58.0+3.4
54.6+2.9
67.746.0
66.9+-6.8
RGCCL w/o Los
82.8:00.8
81.7-0.7
72.020.8
67.420.7
76.642.88
76.412.6
Effectiveness of different loss terms. We conducted an ablation study to evaluate the contribution of different loss terms in our model. Specifically, we examined the impact of removing the positive loss term Cpos and the negative loss term Ling on node classification ion performance. As shown in Table 6 the removal of Gneg leads to a significant drop in performance across three datasets, especially on Citeseer, where the accuracy and Macro-F1 decrease by about 14% and 13%, respectively. This indicates that Lneg plays crucial role in preserving discriminative information during training. On the other hand, removing Epoe only causes slight performance degradation, suggesting that while beneficial, its contribution is less critical compared to Lneg. Overall, the full model achieves the best results, demonstrating the complementary effects of both loss terms.
7 Limitations and Future Work
It is important to emphasize that this study is conducted under the homophilic graph setting, which aligns closcly with the mainstream rescarch direction in the field of graph represcntation learning. This setting ensures that our theoretical framework and methods are well-suited to the widely adopted paradigm namely, that connected nodes are more likely to share similar attributes. While our method demonstrates excellent performance and robustness under the homophilic assumption, its applicability heterophilic graphs remains an open question. Heterophilic graphs are characterized by connections between dissimilar nodes, presenting unique challenges that. are beyond the scope of this study. In future work, we plan to extend the exploration
13

---

Published in Transactions on Machine Learning Research (12/2025)
of class bias amplification to heterophilic graph settings. This direction will likely require the development of new theoretical tools and the establishment of evaluation metries tailored to the characteristios of heterophilic graphs.
8 Conclusion
In this paper, we study the issue of class bias amplification in GNN-based graph representation learning. We present novel perspective this problem through the lens of convergence bias and embedding concentration discrepancy, and comprehensive theoretical analysis is provided. Based on theoretical insights, we propose to use random graph coarsening to mitigate this issue, and give theoretical guidance on how to design effective random coarsening algorithms. Finally, a graph contrastive learning model is proposed which utilize random graph coarsening as graph augmentation and a loss function is designed for this new form of graph augmentation. Comprehensive experimental evaluation illustrates the superiority of RGCCL in mitigating class bias amplification.
Acknowledgments
This work is supported by National Natural Science Foundation of China No. U2241212, No. 62276066, and the Postdoctoral Fellowship Program of CPSF under Grant No. GZC20252742. The computations in this research were performed using the CFFF platform of Fudan University.
References
Afonso S. Bandeira and Ramon van Handel. Sharp nonasymptotic bounds on the norm of random matrices with independent entries. The Annals of Probability, 44(4):2479 2506, 2016.
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi-supervised classification: Improved lincar separability and out-of-distribution generalization. In Proceedings of the 38th International Conference on Machine Learning, 684 693, 2021.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeshwar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and Devon Hjelm. Mutual information neural estimation. In International Conference on Machine Learn- ing, pp. 531 540, 2018
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised induc- tive learning via ranking. In International Conference on Learning Representations, 2018.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In International Conference on Machine Learning, pp. 942-950, 2018.
Jingyu Chen, Runlin Lei, and Zhewei Wei. Polygel: Graph contrastive learning via learnable spectral polynomial filters. In International Conference on Learning Represenlations, 2024.
Fan RK Chung and Fan Chung Graham. Spectral graph theory. American Mathematical Soc., 1997.
Weilin Cong, Rana Forsati, Mahmut Kandemir, and Mehrdad Mahdavi. Minimal variance sampling with provable guarantees for fast training of graph neural networks. In ACM SIGKDD international conference on Knowledge Discovery and Data Mining, pp. 1398-1403, 2020.
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On the importance of sampling in learning graph convolutional networks. arXiv preprint Xrv: 11t::2033.0666,, 2021.
Chenhui Deng, Zhiqiang Zhao, Yongyu Wang, Zhiru Zhang, and Zhuo Feng. Graphzoom: A multi-level spectral approach for accurate and scalable graph embedding. In International Conference on Learning Representations, 2019.
14

---

Published in Transactions on Machine Learning Research (12/2025)
Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block
models. In Advonces in Newral Informalion. Processing Systems, volume 31, pp. 5590-8602 2018.
Yushun Dong, Ninghao Liu, Brian Jalaian, and Jundong Li. EDITS: modeling and mitigating data bias for graph neural networks. In The Web Conference, 2022.
Yushun Dong, Jing Ma, Chen Chen, and Jundong Li. Fairness in graph mining: A survey, TKDE, 2023.
Matthew Fahrbach, Gramoz Goranci, Richard Peng, Sushant Sachdeva, and Chi Wang. Faster graph em- beddings via coarsening. In International Conference on Machine Learning, 2020.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference Machine Learning, pp. 3419 3430, 2020.
Aditya Grover and Jure Leskovee. node2vec: Scalable feature learning for networks. In Proceedings of the International Conference on Knowledge Discovery and Data Mining, pp. 855 864, 2016.
Melissa Hall, Laurens van der Maaten, Laura Gustafson, and Aaron Adcock. A systematic study of bias
amplification. Arziv, abs/2201.11706, 2022.
Kaveh Hassani and Amir Hoscin Khas Ahmadi. Contrastive multi-view representation learning on graphs. In International Conference on Machine Learning, pp. 4116 4126, 2020.
R Devon Hjelm, Alex Fedorov, Samucl MarchinM Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. In International Conference on Learning Representations, 2019.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. Advances in neural information processing systems, pp. 22118-22133, 2020.
Weiran Huang, Mingyang Yi, and Xuyang Zhao. Towards the generalization of contrastive self-supervised learning. In International Conference Learning Representations, 2023.
Zengfeng Huang, Shengzhong Zhang, Chong Xi, Tang Liu,, and Min Zhou. Scaling up graph neural networks via graph coarsening. In ACM SIGKDD international conference on Knowledge Discovery and Data Mining, pp. 675-684- 2021.
Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. Graph condensation for graph neural networks. In International Conference on Learning Representations, 2022.
Yu Jin, Andreas Loukas, and Joseph JaJa. Graph coarsening with preserved spectral properties. In Inter- national Conference on Artificial Intelligence and Statistics, 2020.
William B. Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into Hilbert space. Tn Conference modern analysis and probability, volume 26, pp. 189 206, 1984.
Jian Kang, Yan Zhu, Yinglong Xia, Jiebo Luo, and Hanghang Tong. Rawlsgen: Towards rawlsian difference principle on graph convolutional network. In The Web Conference, 2022.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Leurning Representations, 2017.
Bolian Li, Baoyu Jing, and Hanghang Tong. Graph communal contrastive lcarning. In The Web Conference, 2022.
Huan Li and Aaron Schild. Spectral subspace sparsification. In IEEE Annual Sympostum on Foundations of Computer Science, 2018.
Lu Lin, Jinghui Chen, and Hongning Wang. Spectral augmentation for self-supervised learning on graphs. Tn International Conference on Learning Representations, 2023.
15

---

Published in Transactions on Machine Learning Research (12/2025)
Yixin Liu, Ming Jin, Shirui Pan, Chuan Zhou, Yu Zheng, Feng Xia, and Philiip S. Yu. Graph self-supervised learning: A survey. IEEE TKDE, 35(6):5879-59M) 2023a.
Zemin Liu, Trung-Kien Nguyen, and Yuan Fang. On generalized degree fairness in graph neural networks. In Association for the Advancement of Artificial Intelligence, 2023b.
Andreas Loukas. Graph reduction with spectral and cut guarantees. Journal of Machine Learning Research, 20 2019.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classifi- cation. In International Conference on Learning Representations, 2020.
Bryan Peronii, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. Tn
ACM SIGKDD international conference on Knowledge Discovery and Dato Mining, 2014.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang, Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Representations, 2020.
Jacyun Song, Joonhyung Park, and Eunho Yang. Tam: topology-aware margin loss for class-imbalanced node classification. In International Conference on Machine Learning, pp. 20369 20383. PMLR, 2022.
Xianfeng Tang, Huaxiu Yao, Yiwei Sun, Yiqi Wang, Jiliang Tang, Charu C. Aggarwal, Prasenjit Mitra, and Suhang Wang. Investigating and mitigating degree-related biases in graph convoltuional networks. In International Conference on Information and Knowledge Management, 2020.
Petar Veličković, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In International Conference on Learning Representations, 2018.
Angelina Wang and Olga Russakovsky. Directional bias amplification. In International Conference on Machine Learning, volume 139, pp. 10882-10893, 2021.
Ruijia Wang, Xiao Wang, Chuan Shi, and Le Song.
Uncovering the structural fairness in graph contrastive learning. In Advances in neural information processing systems, 2022.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International Conference on Machine Learning, pp. 6861-6877 2019.
Xinyi Wu, Zhengdao Chen, William Wang, and Ali Jadbabaie. A non-asymptotic analysis of oversmoothing in graph neural networks. In International Conference on Learning Representations, 2022.
Yaochen Xie, Zhao Xu, Jingtun Zhang, Zhengyang Wang, and Shuiwang Ji. Sclf-supervised learning of graph neural networks: A unified review. IEEE TPAMI, 45(2):2412 2429, 2023.
Wenjie Yang, Shengshong Zhang, Jiaxing Guo, and Zengfeng Huang. Contra": A one-step active learning method for imbalanced graphs. Artif. Intell., 349: 104319,,,,, 2025.
Wenjie Yang, Shengzhong Zhang, and Zengfeng Huang. Cross-level graph contrastive learning for community value prediction. Neural Networks, 194:108103, 2026.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In Advances in neural information processing systems, volume 33, pp. 5812 5823, 2020.
Hengrui Zhang, Qitian Wu, Junchi Yan, David Wipf, and Philip S. Yu. From canonical correlation analysis to self-supervised graph neural networks. In Advances in Newral Information Processing Systems, 2021.
Shengzhong Zhang, Zengfeng Huang, Haicang Zhou, and Ziang Zhou. SCE: scalable network embedding from sparsest cut. In ACM SIGKDD international conference on Knowledge Discovery and Data Mining, pp. 257-265. 2020.
16

---

Published in Transactions on Machine Learning Research (12/2025)
Jieyu Zhao, Tianlu Wang, Mark Yatskar, Vicente Ordonez, and Kai-Wei Chang. Men also like shopping: Reducing gender bias amplification using corpus-level constraints. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing,, pp. 2979 2989, 2017.
Yizhen Zheng, Shirui Pan, Vincent C. S. Lee, Yu Zheng, and Philip S. Yu. Rethinking and scaling up graph contrastive learning; An extremely efficient approach with group discrimination. In Advances in Newral Information Processing Systems, 2022.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive repre- sentation learning. In International Conference on Machine Learning Workshop on Graph Representation Learning and Beyond, 2020.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Lüu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In Proceedings of the Web Conference, pp. 2069 2080, 2021.
A Appendix
A.1 The proof of Lemma 4.1
Lemma A.1. Let C1 and C2 be the two classes of nodes. Suppose each cluster has the same size s, then
Ep-p
Σ
Σ +lIf(u) - f(S:)11
S:ES
uES
Σ
llf(u) f(u)]12 + 92
Σ
llf(u) f()))
91
u,
012
Σ
lIf(u)
f(o)113
NECL
Proof. Let I, be the index such that St., We have
Σ sll((u) - ((S)) =Epo Σ 5 Σ Σ -
Epap
(17)
5,ES HES,
S,ES
uES, vES,
For fixed S E S, without loss of generality assume f(S.) = 0 (if not, redefine f(u) f(u) f(S.)), then we have
Σ IIf(w) S(0)
(18)
2
S vES,
Σ (1I(())1² + -
(19)
WE VES:
Σ =llf(u) f( wES;
(20)
The equation 20 is due to the assumption that f(S.) = 0. Therefore,
E EPaP Σ s(l(w)) - Σ
(1.=1lll(()) - f(o)]1
(21)
SEES
17

---

Published in Transactions on Machine Learning Research (12/2025)
We next divide pairs in
21
into three categories and get
Ep-p
Σ
4u.=1,1lf(()) - f(v)11
uste
=PPwp
4 f(o)]
+ E Pppp
Σ
I [(==1,11f(u)) f(v)l?
+ Epup
Σ
Tu.= f(v)]12
MECI,ECC2
E
41 aill(u)) - [(v)]1++
Σ 221l((u) f(v)]2
U,
Σ MECI,PEC2
(2llf(()) f(o)]1
which finishes the proof.
A.2 Comparison of Node Embeddings of the Original Graph and the Coarsened Graph
In this section, we assume the graph is connected. When there are multiple connected components, each component can be analyzed separately, and thus the conclusion holds for general graphs.
The feature matrix of the coarsened graph is computed using the formula in line 13 of Algorithm 1 which is different from prior work. Here we provide a justification on this. We consider a GNN encoder Z = o (X) with -= DD 1 '.. Assume the corresponding supernode of u in the coarsened graph is v. We use Z, and Z represent the node embeddings learned from the original graph G and the coarsened graph G' respectively. We show next that using our coarsened feature matrix, the difference between Zu and Z, converges zero k
We assume the activation function o-)) and the linear transformation function W to be Lipschitz continuous. These assumptions are commonly used in previous analyses of GNNs (Chen et al. 2018 Garg et al. 2020:
Cong et al. 2020 2021 Then, the coansening error can be expressed as:
Z 2,11 = (oo - ('W)) S <l](A*x), - (A X')ell,
(22)
where represents the Lipschitz constant. For notational convenience, let Ta (A X').. We need the following Lemma, the proof of which can be found in Chung & Graham (1997)
(A* X), and Te
((k)
Lemma A.2.
á
d
AC
AA
An3 S
Xad, dj
(23)
Σneo du where X2 is the second largest eigenvalue of A and d, denotes the degree of node i with self-loop. Theorem A.3. Let the coarsened feature X' = D'-1pf then for any node u, have
2m + n
(k) m (4)
dmax dmin (n n' x
V
(24)
where d2 and X2 are the second largest eigenvalues in G and G' respectively. dman and dmai are the mazimum degree and minimum degree in G and G', respectively.
Proof. Given the coarsened adjacency matrix A' = PT ATAP, the sum of the weighted edges in A' is still
2m + n. If node j in G' is not a supernode, we have A!e.. = Evecr d 2m = Ar3- Let S be the set of
J,
18

---

Published in Transactions on Machine Learning Research (12/2025)
supernodes in G', ie., those nodes in G' containing at least two nodes from the original graph, and define Q as the set of nodes participating in the coarsening process: Q
U S.. Then we have:
S.ES
(8)
(A
X's.
Σ
AN
x
E
(Ab.s Xj - Ao. Xf)1l
U.S.
(25)
S,ES
jES,
jEVIQ
<11
(A U.S, X''s Σ
A
+1))+++||
Σ
(Ai.) Xx م6. Xf)I
S.ES
jES,
jEVIQ
First,
|| Σ (A U.S, X's. Σ A
ΣAn Xj)l
SIES
JES.
11
Σ (A U, -X's. A U.S. X's, + AA X's.
8,E8
Σ (A X, - An.. .X, + Ane X,))II
JES.
Σ (A 8,
Xx'; A
v.5. Xx's Σ
- X, Anr Xz)
5,E8
JES,
+ A 8,8,
X's Σ
ACe
X,)l|
KJ
(26)
JES.
(Á S
X''; A v.S.
Xx x1
+1
Σ
Σ
(Ath X2 A.. x,)I|
S,ES
S:ES JES;
+1|
Σ
(A U,S:
Xxs. Σ
Ang X,)ll
S,ES
JES,
||Á E.S,
A.C.s,
|1lxs ||
+
Σ
Σ
| |XX
S,ES
S JES.
+
(A v.S. X''.
Σ
A X,)Il.
8,E8
jES:
For the sake of simplicity, assume the feature Xy is non-negative and normalize the X, that ||X||| 1. Let the supernode feature X's, = E,cs, X Σ Eges, d,X,
In other words, the coarsened feature matrix
Eje, dy
X' is defined as 5' Dx, which implics |x]| | 1. Then, we have
|1 Σ (A v.S. X's.
Σ Ab. X,)I|
S,ES
JES:
|| U.S,
- 111
Σ
|AA
A. |||
8.E8
S.S.
(A v.S. -X's- - Σ Au. X,)Il
+1
(27)
S,ES
JES.
| U.S.
A |l
Σ
| A
8.68
S,E9 JeS,
<
d'
d'g,
Σ
(by Lemma A.2
S:ES
S.SS
For each uncoarsened node u E V\Q, we have As.
A
v.g and X, X/. Therefore,
19

---

Published in Transactions on Machine Learning Research (12/2025)
Σ
(A X; - - X²)1
1EV
-11 Σ (A X;- - X, + Au.j Xj A:.s X))I
< Σ (I .X; - - Xiyl + ||Ain Xj - A X)I)
(28)
JEVIQ
Σ (I -AW + +1 n.j A A
JEVIe
Σ jEvie
(22du $d, + +X 2z (by Lemma A.2
We define dmaw and dmin as the maximum degree and minimum degree in G and G², respectively. Thus, we have the following conclusion
(k)
(R)
dmax
dmaas dman
dmaa dmin
|5|2/ %b + V
1Q12 + V
(n (n- 121 + +x²²)
dmii
(29)
dmax
(n12 + (n + 1S| - -1Q1)
dmin
dmaz
(n n n'2))
dmii
0
According Theorem A.3 and inequality
22 we have the following upper bound:
dinar (n15 + n' xtt)
Zu Z,11 xy
(30)
dmni
On the account of 0 < d2 < and 0 < X/2 < when & co, the error I| Z + 0.
A.3 Generalizability of RGCCL
Following (Huang et al. 2023 Wang et al. 2022 we investigate the generalizability of our self-supervised model. Denote Gv, as the ego network of node v; and the corresponding adjacency matrix as Ag., Wang
et al. 2022) characterizes the concentration of a graph augmentation set with the following definition.
Definition 2 ((a, 7, d) Angmentation)) The data augmentation set A, which includes the original graph, (a,7, 7, d) auggentttn,,, if for each class Ck there erists a main part C S Ck (i.e., Ply Ct. 2 oPlu E Ck)),
Agg Agg }x1, and D )122 hold with d'(r, vz) Ai (GG,, )ll àog dgg
where sup mecedaa S <1(
( de...
a is the minimum degree in class Ck.
Given a (a, 7, Augmentatin, one can establish inequalities between contrastive losses and the dot product of class center pairs. This means classes will be more separable while the objectives are being optimized. For example, Huang et. al. (2023) gives the proofs for InfoNCE and the cross-correlation loss. Since our objective differs from both of them, prove similar theorem as Huang et al. (2023). Denote μ4
Evec, EGrA Ps P(u E Ct), S. := (v UK C+ VGI. E A(G.), (1( f(92)) $ <) and R. : PP((S.
20

---

Published in Transactions on Machine Learning Research (12/2025)
Theorem A.4. Assume that encoder with norm 1 is M-Lipschitz continuous. For given (a, d) augmenlation set A, any > 0 and k + 1
1 (-
1 14 S
2n 2n2 + ((,,,,
(31)
P&Pt
where T(,, 0t 7, 2R. +1,11((1-aa---- je- Mmmaxs(7 mmi
kR) 2e Mmmaxi(T de
D
)
K + 2
Proof. Our negative pair loss is
1 Ei=1 2== |1|b:|12+ |1, 2h hy)
Lung Epupl
Epwpl
112 Li=1 2ÿ=1 1 h3
Since Σx Eラ=1 hifh; S n², and -ー is convex for x S n², Using Jensen's 's inequality, we have:
20neg n² Eppp Ei=1 i=1 Eド= h hyl
n²(1 Ee, Ep- Ih? hy])
Next, we focus on Ex,,, Bp hiyhhh
K [U(2, E S. (c)l((, e ()Ep-P((hhh))
E Ex,
Epnp 11g [nT
E Bx,,,
Egg,, [1(;;; E S.)l
K K
Brazy [T(2; CL)T(ar E (()(T( R. + A
k=
1=1
K K
[PuPINK mi] R. + A
1 2 PAPURT +
RR + A1, K
where A defined as
K
A
Ban,, [x, E E.r.eSEnCe C.) E (G)
1=1 1=1
K
Ex,,, [[(x; Cx)l(zz (()
Bx,or [[[ E Cx)Il(a, E Ci)E mi]
K K
Em,,, [[[x; E Ct) I(x e S. (c))))( E (h)
A=l 1=1
21

---

Published in Transactions on Machine Learning Research (12/2025)
Then,
|1
SR.
E8 Ex,,, [1 Cx)l(ay E Gilkpwolhhhh - mE mll
1=1
D D) + KR.)²
SR. + +16(1 - aa(1 2 33=2Mmaxi(7
minu
d
+ 8(1 - a(1 --- +Mmaxx(7y
D-)++ KR))
D
min
Thus, if we define
D
T(G,,,,d) -2 + 16(1 - a(1
2
2-
4
Mmaxx((y)
di
)) + KR.)²
+ +8(1 a(1
1
Mmaxx(7
D
+) + KR. +
K
2
4
gt
K
min
we have
T 111
-(1
1
K + R. + (111)
P4P1
2n Long
1
(-
a((,,,
P&P1
2n Cneg
This finishes the proof.
A.4 Random Graph Coarsening Algorithm
Algorithm is a detailed description of our random graph coarsening algorithu..
Algorithm 1 Random Graph Coarsening
Input: G X), threshold 8, the coarsening ratio r, number of nodes n
Output: G' (A',,)))
Compute the weight set I of all edges
Construct an edge set & of length en by randomly selecting the edges according to the weight set I.
Initialize the cluster list T for i= to rn do Obtain vu, E; Retrieve the clusters Tu and To from T, where To contains u and To contains v if [T..l + |To 5 and Ta * To then
Merge cluster Tu and cluster To to cluster end if end for Construct the assignment matrix P by T Compute the coarsened adjacency matrix A' = -p2 AP Compute the coarsened feature matrix X' - Dx Return G = (A),X')
A.5 Experimental details
For all unsupervisod models, the learned representations are evaluated by training and testing a logistic regression classifier except for Ogbn-Arxiv. Since Ogbn-arxiv exhibits more complex characteristics, we use more powerful MLP classifier. The detailed statistics of the six datasets summarized in Table
22

---

Published in Transactions on Machine Learning Research (12/2025)
Table 7: Summary of the datasets used in our experiments
Dataset
Nodes
Features
Classes
Avg. Degree
Cora
2,708
1,433
3.907
Citeseer
3,327
3,703
2.74
Pubmed
19,717
500
4.50
Amazon-Photo
7,650
745
31.13
Computees
13,752
767
10
35.76
Ogbn-Arxii
169,343
128
40
13.67
Details of our model. our model, we use SGC as the encoder for Cora, Citeseer, Pubmed, while we use GCN the encoder for Photo and Computers. The detailed hyperparameter settings are listed in Table X
Our code is available al:
com / Classssssnnn--sss---aaaa -aass-BBas--a Seias-Amplificattie
Fn orppeepaheeeerreeettttiooooooo
Table 8: Summary of the hyper-parameters.
Datasct
Epoch
Learning rate
Cora
25
0.01
15000
500
Citescer
200
0.0002
15000
500
Pubmed
25
0.02
20000
200
Amazon-Photo
20
0.001
100000
100000
Amazon- Conzoon-smmsuerss
20
0.0002
20000
20000
Ogbn-Arxiv
10
0.0001
2000000
200000
Details of Baselines. We compare RGCCL with state-of-the-art GCL models DG1 GRACE GraphC1 GCAD CCA-SSG" gCool GGL GRADE SPAND PolyGC1 and classic graph embedding model Deepwalk. For all the bascline models, we use the source code from corresponding repositories. Due the large scale of Ogbn-Arixv, some GCL models unable to process the full-graph on GPU because of memory limitations. As result, apply graph sampling techniques to train these models.
Configuration. All the algorithms and models are implemented in Python and Py PyTTrch Geometric. Ex- periments are conducted on a server with NVIDIA 3090 GPU (24 GB memory), NVIDIA A6000 GPU (48 GB memory) and Intel(R) (eon(R) Silver 4210R CPU 2.40GHz.
'DGI (MIT License):
hsductive. py
"GRACE (Apache License http://pp////tttuu.oc/aaaaaaaaoa
*GraphCL (MIT License): httpts::/gggii..
4GCA (MIT License): (ttp:://ggtbbb..co///UPPP------
*CCA-SSG (Apache Lacense 2.0): http:///n./ggggg/.ooooooooaaaaaa
6gCooL
7GGD (MIT License):
&GRADE (MTT License):
Graph
Contrastive-Learninn
"SPAN [MIT License::
PCPoyGGC. (MIT License): http://ggtiib..co//heeeaaaaaa/aa
23


Reviews:
[{"review_id": "xeKiRcv9w6", "reviewer": "Reviewer_dkPn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper deals with the problem of bias favoring well-connected nodes (that tend to correlate with some classes, possibly majority classes) in Graph Representation Learning (GRL) methods. It alternates nicely between intuition on simple cases and more general theory.\n\nAfter explaining the issue and demonstrating it very clearly on a concrete case (figure 1), it proposes an explanation for it as mechanism that is both explained intuitively and backed by more theoretical derivations.\nIt then introduces a simple graph coarsening mechanism, RGCCL, that should alleviate the issue. It then demonstrates empirically how RGCCL effectively decreases the problem.\n\n# Strengths:\n\n- clearly written, nice to read, intuitions precede the maths\n- a complete approach, as the paper combines theory (with intuitions), from problem observed, to theoretical solution, to experiments.\n\n\n# Weaknesses\n\n- it seems authors were stressed about the page limit and squashed a few things to appendix when they could have been integrated in the main text\n- although overall clear, some definitions are missing. See requested changes.\n- some details about the recipe for reproducing experiments (on new datasets) are missing. See requested changes.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The theory is backed by proofs presented in appendix, \nbut most importantly the intuitions presented are convincing (up to a few precisions required below)\nand the experiments are rigorous and show the point claimed.", "audience_yn": "Yes", "audience_explanation": "This paper is at the frontier of several topics of general interest:\n- Graph Representation Learning (Self Supervised)\n- Bias and fairness in ML\n- class imbalance", "requested_changes": "# Important changes\n- remember that the length limit in TMLR is not a hard threshold, it's just that reviewing is supposed to be done earlier for papers less than 14 pages. Don't squash too much relevant material into the appendix, it hurts clarity.\n- please define mathematically the notions of 1) embedding density (or embedding concentration) and 2) class density (the sentence \"C1 is denser than C2\" above Eq 10 is also problematic). The only sentence I found was \"Firstly, we measure the concentration for each class by calculating their mean distances of the embedding from the centroid [inline equation]\"... at page 10. I think this should come earlier and with a numbered equation.  Although these notions are quite well explained intuitively, it is important to know what you mean quantitatively. I believe that actually estimating these densities is computationally hard, but one may look at the variance of the points (representations) within one class, or one cluster, which seems to be what is done.\n- The reasoning after Eq. 10 is a bit fast for me.\n    - 1. \"homophily principle\": there are counter examples to that principle I guess, it would be better to mention it. Although I guess than when classes mix together, there is less class bias amplification (at least by the mechanism discussed in the paper)\n    - 2. * we adopted a simple probability function ...\". This is a bit vague and could be stated more explicitly. This goes together with my next comment:\n- lines 3,4 of algorithm 1 (\"Compute the weight...to the weight set I.\") which are the key lines, should be explicited, in the main text.  This is a central part of the RGCCL recipe, so it should be clearly stated and explained in the main text. The rest is rather technical and straightforward and can be kept in appendix (well the coarsened feature matrix computation is non trivial but is discussed in the main text, so, fine.)\n- paragraph just before section 5, \"Next we discuss the concentration property of the random coarsening augmentation.\" is quite unclear. I follow well the beginning, but not how it relates to the conclusion: \"Once u and v are coarsened together in at least one coarsened graph, d(u, v) = 0, which means our random coarsening augmentation can be very well-concentrated.\" How come? I don't see the connection at all with the fact that any two nodes, however far in the graph, can always be connected, at least with probability $p^{diameter(G)}$.\n- how were α,β chosen ? In table 7, values are given, but how are they guessed? It's important to provide guidelines for future users.\n- is code available? Please make it so.\n\n\n# Small changes and Typos\n- the statement \"However, class bias amplification occurs in GNN-based GRL and is unrelated to label distributions.\" seems slightly misleading. I think I understand the point, yet, the measures used later in the paper refer to unequal performance for different classes. Although GRL does not use labels to be trained, the problem of a weak representation for minority classes is surely related to class frequency, isn't it?\n- typo page 3, missing space: belonging to the same class.C 1 is more\n- typo page 6, missing space: thus omitted.The above\n- table 3 does not follow the style of other tables, also the order of the other models has been changed. Please always order them the same way.\n- table 5: you could add a comment about how results are very robust to changes in $r$! It's actually quite impressive. Often, people introduce new methods, that actually work well only when fine-tuning their newly introduced hyper-parameters (here, r), That's not the case at all here, very nice.\n- \"A.5 More Related Work\" -> move to main text.\n- algorithm 1: define n.", "broader_impact_concerns": "None, on the contrary, dealing with biases better can only help.", "additional_comments": "I invite the authors to consider participating in:\n- Unifying Perspectives on Learning Biases\n- EurIPS 2025 Workshop - Copenhagen, DK - December 2025\n- https://sites.google.com/view/towards-a-unified-view", "extra_scores": {}, "extra_text": {}}, {"review_id": "pKFgW1wReL", "reviewer": "Reviewer_3oVj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper identifies class bias amplification in GNN-based graph representation learning: when GNN encoders are used for unsupervised pretraining, downstream per-class performance gaps can increase relative to non-graph baselines. The authors formalize how local structural disparities between classes induce different message-passing convergence speeds, causing embedding concentration discrepancies and biased class-wise errors. They propose RGCCL (Random Graph Coarsening Contrastive Learning), using stochastic graph coarsening that favors low-degree regions. The method  creates a two-view contrastive objective: each node is pulled toward its coarsened super-node embedding, with negatives sampled only from the coarsened view. Experiments on six node-classification benchmarks show improved Macro-F1 and reduced per-class disparity versus strong GCL baselines. Ablations section examines memory use and coarsening ratios.\n\nStrengths\n- The authors define a clear articulation of a practically relevant phenomenon (class-level performance gaps in GRL) with aspectral explanation (different second eigenvalues and different finite-depth convergence)\n- They theoretically analyze and propose a simple yet effective strategy (general augmentation, i.e. random coarsening ) backed by analysis (q₂>q₁>q₁₂) and integrated into a contrastive framework \n- Broad, competitive empirical study across standard datasets with different models and ablations studies on embeddings properties define a well designed experimental setup\n\nWeaknesses\n- While the manuscript includes links to baseline code, it does not (as far as I can see) provide a code repository for RGCCL, which would be important for reproducibility\n- The related work section is too brief and would benefit from a more comprehensive discussion and positioning within the broader literature, for example by expanding it incorporating section A.5 from the appendix\n- The paper does not explicitly discuss its limitations, for example how the proposed method behaves on heterophilic versus homophilic graphs", "claims_and_evidence_yn": "Yes", "claims_explanation": "Mostly yes. The paper provides a spectral account of local convergence leading to embedding concentration imbalance, a statistical link from variance imbalance to class error asymmetry, and experiments on multiple datasets showing overall gains and reduced dispersion across classes compared to strong baselines. This supports the main acceptance criterion of TMLR", "audience_yn": "Yes", "audience_explanation": "Yes. Graph contrastive learning and fairness in graph representation learning are active topics, and the idea of using coarsening as a bias reducing augmentation is simple, practical, and broadly applicable", "requested_changes": "- The paper does not explicitly discuss its limitations. In particular, all experiments are conducted on standard homophilic benchmarks (Cora, Citeseer, PubMed, Amazon, OGB-Arxiv), while it remains unclear how the proposed method would perform on heterophilic graphs (e.g., Chameleon, Texas). Since the theoretical analysis is built on assumptions of community homogeneity, some discussion of this limitation and potential extensions to heterophilous settings would strengthen the work.\n- Provide a public code repository for RGCCL to ensure reproducibility, in addition to the baseline code links.\n- Expand the related work section with a more comprehensive discussion and clearer positioning within the broader literature, for example by integrating or extending section A.5 from the appendix.", "broader_impact_concerns": "I recommend adding a brief clarification that the notion of fairness in this work is limited to class-wise performance balance in benchmark tasks and does not extend to demographic or sensitive groups.", "additional_comments": "Some typos:\n\t- Sec.1 Introduction: \"behaviour:They try\"\n\t- Sec 3.:\"to the same class.C_1\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "vrs1AkOdei", "reviewer": "Reviewer_kEHx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "**Summary:**\n\nThis paper explores a structural bias phenomenon in graph representation learning (GRL), referred to as class bias amplification. It is the tendency of graph neural network (GNN) encoders to worsen performance disparities across classes. The authors present a theoretical analysis to explain how such bias arises in downstream classification tasks. And, building on these findings, they introduce a method based on contrastive learning to alleviate the issue.\n\n**Strengths:**\n\n1.\tThe paper is well-motivated, with a clear progression from problem definition to theoretical analysis and method design.\n2.\tThe paper establishes a sufficient theoretical foundation to explain the phenomenon of bias amplification.\n3.\tExtensive experiments on multiple benchmark datasets validate the effectiveness of the proposed method.\n\n**Weaknesses:**\n\n1.\tThe most recent baseline used for comparison is from 2023. It would be helpful to present empirical comparisons with newer methods.\n2.\tThe ablation study and sensitivity analyses (e.g., hyperparameters, coarsening strategies) are relatively brief and would benefit from deeper exploration.\n3.\tSince the main focus of the paper is addressing class bias amplification, the related work section should include a discussion of prior studies on bias amplification and clarify how the proposed notion of class bias amplification differs from existing definitions of bias amplification [1,2,3].\n\n[1] Zhao, Jieyu, et al. \"Men also like shopping: Reducing gender bias amplification using corpus-level constraints.\" arXiv preprint arXiv:1707.09457 (2017).\n\n[2] Wang, Angelina, and Olga Russakovsky. \"Directional bias amplification.\" International Conference on Machine Learning. PMLR, 2021.\n\n[3] Hall, Melissa, et al. \"A systematic study of bias amplification.\" arXiv preprint arXiv:2201.11706 (2022).", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper’s claims are supported with both theoretical and empirical evidence. The theoretical analysis offers a clear explanation of class bias amplification, while the proposed random graph coarsening and RGCCL model are well-motivated. Experiments on six benchmark datasets consistently demonstrate reduced class disparities and improved overall accuracy.", "audience_yn": "Yes", "audience_explanation": "The paper addresses an important problem in graph representation learning—the tendency of GNN encoders to amplify performance disparities across classes—a challenge that is highly relevant to both the graph learning and bias mitigation research communities.", "requested_changes": "1.\tThe flow of the paper is disrupted by Section 5; I suggest moving it to the end, just before the conclusion.\n2.\tThe comparison with recent fairness-aware GNN methods is limited and should be expanded.\n3.\tThe ablation study should be presented in greater detail.\n4.\tThe related work section should include a discussion on bias amplification and clarify how the proposed notion of class bias amplification differs from prior definitions.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)