{'fraction_non_alphanumeric': 0.03726791640505875, 'fraction_numerical': 0.00953000269082429, 'mean_word_length': 4.775317275317275, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
ImGCL: Revisiting Graph Contrastive Learning on Imbalanced Node Classification

Graph contrastive learning (GCL) has attracted a surge of attention due to its superior performance for learning node/graph representations without labels. However, in practice, unlabeled nodes for the given graph usually follow an implicit imbalanced class distribution, where the majority of nodes belong to a small fraction of classes (a.k.a., head class) and the rest classes occupy only a few samples (a.k.a., tail classes). This highly imbalanced class distribution inevitably deteriorates the quality of learned node representations in GCL. Indeed, we empirically find that most state-of-the-art GCL methods exhibit poor performance on imbalanced node classification. Motivated by this observation, we propose a principled GCL framework on Imbalanced node classification (ImGCL), which automatically and adaptively balances the representation learned from GCL without knowing the labels. Our main inspiration is drawn from the recent progressively balanced sampling (PBS) method in the computer vision domain. We first introduce online clustering based PBS, which balances the training sets based on pseudo-labels obtained from learned representations. We then develop the node centrality based PBS method to better preserve the intrinsic structure of graphs, which highlight the important nodes of the given graph. Besides, we theoretically consolidate our method by proving that the classifier learned by balanced sampling without labels on an imbalanced dataset can converge to the optimal balanced classifier with a linear rate. Extensive experiments on multiple imbalanced graph datasets and imbalance settings verify the effectiveness of our proposed framework, which significantly improves the performance of the recent state-of-the-art GCL methods. Further experimental ablations and analysis show that the ImGCL framework remarkably improves the representations of nodes in tail classes.


Introduction
Recently, graph contrastive learning (GCL) has become the de facto standard for self-supervised learning on graphs [1] due to its superior performance as compared to the equivalent methods trained with labels in a supervised manner on graph benchmark datasets [2][3][4][5]. Inheriting the advantage of self-supervised learning, GCL frees the model from the reliance on label information in the graph domain, where label information can be costly and error-prone in practice [6] while unlabeled/partially labeled data is extremely common, such as fraudulent user detection [7] and molecular graph data [8]. In a nutshell, most GCL methods typically first construct multiple graph views via stochastic augmentations on the input graph and then learn representations by maximizing the feature consistency between two views.  Figure 1: (a) Class distribution sorted in decreasing order of the Amazon-Computers dataset, where training sets are highly imbalanced but testing sets are balanced. (b) Compared to the GBT [3] baseline model on Amazon-computers, ImGCL+GBT substantially outperforms GBT on the overall accuracy. On three splits (many-/med-/few-shot) depicted in different colors (blue/yellow/red), ImGCL+GBT improves the performance of few-and medium-shots categories by a large margin with slightly sacrificing accuracy on many-shots.
Despite the proliferation and effectiveness of such methods, existing GCL methods mostly assume the standard graph benchmark datasets are carefully curated and well balanced across classes. However, unlabeled graph data randomly gathered in the wild often exhibit highly imbalanced property [9] and thus implicitly deteriorates the performance of the GCL methods [10]. For instance, Fig. 1(a) illustrates the class distribution sorted in decreasing order of the Amazon-Computers dataset [11], a network of co-purchase goods belonging to 10 classes. In the training set, we can clearly find that a small fraction of classes have massive samples (a.k.a., head classes) and the rest of classes are associated with only a few samples (a.k.a., tail classes). Note that the highly imbalanced property of label information within the training data is unknown to the GCL methods. This important property implicitly exists and is largely ignored by the current GCL methods [1]. On imbalanced node classification, the testing set is balanced across all classes to treat each class equally. As shown in the blue line of Fig. 1(b), we adopt one of the state-of-the-art GCL methods-GBT-to conduct experiments on imbalanced node classification settings. We can find that the baseline GBT model obtains very poor results, especially on the middle and tail classes. Hence, a natural question arises: How to improve GCL on highly imbalanced node classification?
Recent works [12,13] utilize progressively balanced sampling (PBS for brevity) method to decouple the learning procedure into representation learning and classification two stages and achieve remarkable success by narrowing the gap between the training and testing class distribution. However, this method is impractical since it requires knowing the labels, which does not hold in the GCL setting. This dilemma motivates us to explore how to implicitly obtain label information in the traditional GCL setting.
In this paper, we present a principled GCL framework on Imbalanced node classification (ImGCL), to automatically and adaptively balance the representation learned from GCL without knowing the labels. We first propose online clustering based PBS to implicitly obtain label information for PBS. The starting point of GCL is to push similar nodes in a given graph into the same cluster. Motivated by this, we make pseudo-labels to satisfy the need for labels in PBS. We also provide theoretical insight into our proposed method by proving that the classifier learned by balanced sampling without label information on an imbalanced dataset can converge to the optimal balanced classifier with a linear rate, which justifies the rationale of the PBS method. Moreover, we propose the node centrality based PBS method to fit the graph domain. We give large probabilities to nodes with high node centrality scores when down-sampling the head class nodes in online clustering based PBS. This scheme is able to guide the model to learn the features of nodes with high node centrality scores, which is often 'important' in the graph and has abundant structural connectivity when performing message passing. Furthermore, existing GCL models can be seamlessly incorporated into our proposed ImGCL framework. In short, our main contributions can be summarized as follows: • New problem and insights: we introduce an important but under-explored problem, namely graph contrastive learning on imbalanced node classification. The recently proposed GCL methods are vulnerable to the imbalanced node classification setting and result in performance degradation.
• New principled framework: we propose a novel ImGCL framework, which utilizes the node centrality based PBS method. Further theoretical justification provides the rationale of our proposed method. Moreover, existing GCL models can be seamlessly incorporated into our framework.
• Convincing empirical results: we conduct comprehensive experiments to show that the ImGCL framework achieves superior performance compared with the recently proposed GCL methods  Figure 2: Overview of the proposed ImGCL framework. (a) Graph contrastive learning (GCL) methods take graph/sugbgraph as input and produce the corresponding node embeddings as ouputs. (b) Node centrality based progressively balanced sampling (PBS) method automatically and adaptively balances the representations learned from GCL without knowing the labels.
on imbalanced node classification. Extensive ablation studies also demonstrate that the ImGCL framework improves the representations of nodes in tail classes.

Background
T ∈ R N ×d represents the node feature matrix Graph Contrastive Learning. Given an input graph, graph contrastive learning aims to learn effective graph/node representations that can be transferred to downstream tasks by constructing positive and negative sample pairs [1][2][3][14][15][16][17][18][19]. GCL maximizes the feature consistency between two augmented views of the input graph via contrastive loss in the latent space [1,4,5]. Note that we have no access to node labels during training in the setting of GCL. However, the underlying class distribution of the unlabeled dataset is usually highly imbalanced, as shown in Fig. 1. At each training step, we first perform stochastic graph augmentations to generate multiple views of the original graph. Specifically, we utilize two augmentation functions t 1 , t 2 ∼ T to generate graph views where T is the set of graph augmentation functions, such as node dropping, edge perturbation, and subgraph sampling [5]. We then obtain node representations for the two graph views via the (parameter shared) GNN encoder f (·), denoted by Z = f ( X 1 , A 1 ) and Z = f ( X 2 , A 2 ) respectively. Given the latent representations, a contrastive loss is defined to optimize the parameters of the GNN encoder. For any node u, we aim to score the positive pairs u, v higher compared to other negative pairs. Typically, the negative pairs are construed from the augmented views of the original graph or other graphs in the same batch. The commonly-used InfoNCE loss [20] can be defined as: where z u and z v denote the node representation vector of node u and v in G 1 , respectively. z n denotes the node representation of node n in G 2 . s is a contrasting operation to measure the similarity between two node representations. τ represents the temperature hyper-parameter. The similarity function is typically defined as: s(z u , z v , τ ) = exp(z u · z v /τ ).
Imbalanced Learning. Imbalanced learning seeks to learn a model from the training dataset with an imbalanced class distribution, where a small fraction of classes have the vast majority of samples (a.k.a., head class) and the rest classes occupy only a few samples (a.k.a., tail class) [12,[21][22][23], and generalize well on the balanced testing dataset. For a K-class node classification problem, let {v i , y i } N i=1 be the imbalanced training dataset, where each node v i has the corresponding class label y i , which is not known in the training phase of GCL. The total number of training dataset over K classes is N = K k=1 N k , where N k denotes the number of samples in class k. Let π be the vector of label frequencies, where π k = N k /N denotes the label frequency of class k. Without loss of generality, a common assumption in imbalanced learning is that the classes are sorted by π k in a descending order (i.e., if i 1 < i 2 , then N i1 ≥ N i2 ). In imbalanced learning, the number of samples in the head class is often substantially larger than that in the tail class, i.e., N 1 N K . The imbalance ratio is defined as N 1 /N K . Note that in imbalanced learning, the training dataset is imbalanced to mimic the long-tailed class distribution of real-world data collection, but the testing dataset is balanced assuming equality of all classes. Therefore, the overall performance on all classes and the performance for the head, middle, and tail classes are usually reported.

ImGCL: The Proposed Framework
In this section, we first introduce the progressively balanced sampling (PBS) method, which is impractical in our unsupervised setting since it requires knowing the labels. Motivated by the property of GCL, we generate pseudo-labels by clustering the node representations. Finally, we utilize the proposed node centrality based PBS method to adaptively focus on 'important' nodes of the given graph during the down-sampling phase. The overall framework of ImGCL is shown in Fig. 2.

Progressively Balanced Sampling (PBS)
Sampling strategies. As suggested in [13], the probability p k of sampling a node for the given graph from the class k is defined as: where q ∈ [0, 1]. Different sampling strategies have different specific values of q.
PBS [12]. In imbalanced learning, the testing dataset is balanced whereas the training dataset is not. A single data sampling strategy which fits only one case, the balanced dataset (p M k = 1 K by setting q = 0 in Eq. 2) or the imbalanced dataset (p R k = N k K i=1 Ni by setting q = 1 in Eq. 2), cannot account for the class distribution shift between the training and testing datasets. Thus, we adopt two data samplers with different sampling strategies for training in the imbalanced setting. The key idea is to apply an adaptive sampling strategy known as decoupled training in long-tailed learning literature [21]. Formally, at training step t, data are sampled according to a linear combination of the random and mean strategies, controlled by a parameter α ∈ [0, 1]. Therefore, the probability of sampling a node from the class k is given by: Intuitively, at early stages of the training phase, an imbalanced class distribution is used for representation learning of the feature extractor. At later stages, the model prefers the balanced dataset for training an unbiased classifier. Therefore, the control parameter α should progressively decrease from 1 to 0 during the training phase. Concretely, at training step t, α is calculated by [12]: where T is the total number of training epochs.

Online clustering Based PBS
Progressively balanced sampling requires real labels to adjust the class distribution during training, which compromises its practicality. Since GCL is typically applied for the label-free scenario, we cannot directly apply PBS here.
On one hand, McPherson et al. [24] have revealed the homophily phenomenon in graphs, i.e., the nodes with similar features tend to be connected with each other and share the same label. On the other hand, the motivation of GCL is to learn representations in which similar node pairs stay close to each other while dissimilar ones are far apart. We propose to connect these two facts by the pseudo-label method in semi-supervised learning [25], which iteratively generates artificial labels by the model itself to further improve its performance.
Previous work [25,26] made a hypothesis that similar nodes may reside in the same cluster, which is far away from those dissimilar nodes, and showed that cluster assignments can be used as pseudolabels to learn visual representations. Thus, we utilize the emergence of representation clusters learned from GCL to generate pseudo-labels of each node for the given graph. Specifically, suppose there are K-classes for the node classification task. At the certain iteration t of the training phase, we obtain the node representation Z t ∈ R N ×d via the learned GNN encoder. We apply the clustering algorithm to the nodes in the embedding space to produce a set of K prototypes {c 1 , . . . , c K }. Formally, we intend to learn a d × K centroid matrix C and a one-hot cluster assignment vector y n ∈ R K + for each node n of the given graph by solving the following problem: where z t,n ∈ R d denotes the n-th node embedding vector of Z t , and 1 K ∈ R K is the vector with all elements of 1. Solving this above problem provides a set of optimal assignments {ŷ * n |n = 1, . . . , N } and a centroid matrix C * . These assignments are then used as pseudo-labels. We set the number of centroids (clusters) in the clustering algorithm equal to the number of classes in the training dataset. In order to avoid trivial solutions and empty clusters, we use the constrained K-means clustering [27] to instantiate the clustering algorithm. It can implement the K-means clustering algorithm whereby a minimum size for each cluster can be specified. Thus, we can address the representation collapse problem [28] which would produce a highly imbalanced pseudo-label distribution.

Node Centrality based PBS
To take full advantage of the imbalanced dataset, we propose to down-sample nodes of the head classes to balance the class distribution over all classes. We design a down-sampling strategy by incorporating graph structural information to achieve the full potential of the online clustering based PBS method. In network science, node centrality, which measures how important a node is in a graph, is an important metric to understand the influence of each node of a graph [29]. Therefore, we propose an adaptive down-sampling scheme based on node centrality when performing online clustering based PBS. In this paper, we utilize the PageRank centrality due to its simplicity and effectiveness [29]. Formally, the centrality values are calculated by the following iterative form: σ = αAD −1 + 1, where σ ∈ R N is the PageRank centrality score vector for each node, α is a damping factor to control the probability of randomly jumping to another node in the graph, and 1 is the identity vector with all value 1. Note that we pre-calculate the PageRank score σ before the training phase of GCL. When performing down-sampling of the head classes, we calculate the probability of each node based on σ.
Formally, for node v in class j with the centrality score σ v , the probability with the normalized centrality score is defined as: p NPB v,j = min σmax−σv σmax−σmin · p PB j , p τ , where p PB j is the progressively balanced sampling probability of class j, σ max and σ min are the maximum and minimum centrality score, and p τ is a cut-off probability to ensure that nodes with extremely low connections can also be sampled. In node centrality based PBS, we then perform a normalization step that transforms p NPB v,j into probabilities and then use it to balance the class distribution. Concretely, we obtain a subgraph of the original graph in form of a masked vector m ∈ R N by sampling each node independently according to p NPB , which acts as the input of GCL in the next training iteration as shown in Fig. 2.

More Discussions on ImGCL
Implementation details. Instead of utilizing all nodes in the graph, we select N × l nodes in GCL, where l is a hyper-parameter to control the selected nodes. In order to consider the number of nodes in tail classes, we set l = 10% in the experiments. We down-sample the head nodes to the required number according to their PageRank centrality score. One challenge of the implementation is that the quality of the learned pseudo-labels and representations are mutually-dependent, which could destabilize the training loop. In response, we re-balance the class distribution every B epochs, thus there are T /B times to adjust the class distribution. Following the linear evaluation scheme of GCL, we train a linear classifier with a small fraction of datasets after obtaining node representations, which is trained on the balanced dataset by using the PBS method as in [12].
Computational complexity. ImGCL is a general GCL framework. Suppose we use the traditional GCN [30] model in GCL, the training time complexity of a GCN with L layers is O Lmd + Lnd 2 , where d is the dimension of the learned representations, and n = |V| and m = |E| denote the number of vertices and edges in the given graph, respectively. In the ImGCL framework, the time complexity of the clustering algorithm is O (nd). We have k = T /B times to adjust the class distribution using the clustering algorithm to produce pseudo-labels, thus we have an extra O (knd) time complexity. Note that k is always less than 10 in our experiments, so the time of the clustering algorithm in ImGCL is negligible compared with the training of GNN encoders of GCL. Moreover, the time complexity of calculating node centrality is O (t * n), where t is the number of iterations in the PageRank algorithm. This step can be seen as a pre-computing step and can also be ignored compared with the training of GNN encoders.
Modular design of ImGCL. ImGCL is a general GCL framework on imbalanced node classification, which can be readily applied with existing GCL methods adopting the two-branch design (e.g., [2][3][4]). ImGCL does not rely on specific approaches of graph view augmentation, graph view encoding, and representation contrasting in GCL.

Theoretical Justification
In order to justify our proposed method, we theoretically prove that, on the imbalanced unlabeled dataset, a classifier learned iteratively by balanced sampling converges to the optimal balanced classifier with a linear rate. Detailed proofs can be found in Appendix A.
Consider a binary classification problem with two Gaussian distributions with different means and the equal variance. Suppose the data generating distribution is P XY and the probability of positive labels (+1) and negative labels (−1) are P Y (1) and P Y (−1), respectively. We have X|Y = +1 ∼ N (µ 1 , σ 2 ) conditioned on Y = +1 and similarly, X|Y = −1 ∼ N (µ 2 , σ 2 ) conditioned on Y = −1. In addition, suppose µ 1 < µ 2 without loss of generality. We consider the imbalanced setting and it is straightforward to have [31]: Fact 1. Consider the above setup, the optimal Bayes classifier is with the optimal balanced decision boundary θ * being Interpretation. Intuitively, if the label Y is either positive (+1) or negative (−1) with equal probability, the optimal Bayes's classifier boundary is the perpendicular hyperplane through the midpoint of two Gaussian centers. However, if the number of positive labels is larger than that of negative labels, the decision boundary will be dominated by the positive (head) class and shift towards the negative (tail) class.
In the context of imbalanced learning, the training dataset is imbalanced but the testing dataset is balanced. However, in self-supervised GCL, label information is absent and we instead propose to create pseudo-labels iteratively via representations learned from GCL to enable the PBS method. At the first iteration t = 1, one starts from the imbalanced unlabeled dataset and generates pseudo-labelsŶ 0 by the PBS method. Then, we obtain the learned decision boundary estimatorθ 1 and produce pseudo-labelsŶ 1 . The fact that the initial dataset being imbalanced (i.e., , P Y (1) = P Y (−1)) leads to biasedθ 1 andf 1 by Eq. 1, which has three consequences: (1) The learned classifierf 1 exhibits higher recall/lower precision for the head classes and the opposite for the tail classes [6], aligned with our empirical observations in Fig. 3. (2) For any iteration t, the biased classifierf t and pseudo-labelsŶ t induce distribution shift between the pseudo-classesX and ground truth classes X.
(3) For any following iteration t, the dataset re-balanced based onŶ t is still imbalanced with respect to the ground truth labels Y , which by Eq. 1 means |θ t+1 − θ * | > 0, ∀t ∈ N + . For which we prove the following proposition: Our estimator converges to the optimal balanced decision boundary θ * , i.e. θ t+1 − θ * ≤ C · θ t − θ * , ∀t ≥ T with a linear convergence rate C = 2 π < 1. Interpretation. In the context of PBS, the classifier is trained starting from the imbalanced data distribution. Intuitively, by iteratively down-sampling head classes, the data distribution gradually becomes balanced, on which the trained classifier also converges to the balanced optimum. As stated in proposition 1, the classifier learned by balanced sampling with pseudo-label on the imbalanced dataset can converge to the optimal balanced classifier with a linear rate, which justifies the rationale of the PBS method.

Experiments
In this section, we provide empirical results to demonstrate the effectiveness of our proposed ImGCL framework. We conduct extensive experiments on imbalanced graph datasets to mainly answer the following questions: (1) Can ImGCL generally improve the performance of GCL methods on node classification? (Sec. 5.1) (2) Does all proposed components in the node centrality based PBS method benefit the learning of GCL? (Sec. 5.2) (3) How does ImGCL help improve GCL methods on imbalanced node classification? (Sec. 5.2) (4) Is ImGCL sensitive to the hyperparameters? (Sec. E) Dataset. For a comprehensive comparison, we use four widely-used datasets, including Wiki-CS, Amazon-computers, Amazon-photo, and DBLP, to study the performance of transductive node classification. Recently proposed work evaluates the performance of semi-supervised node classification. ImGAGN [32] reconstructs the binary imbalanced network by setting the smallest class as the tail class and the rest classes as the head class. The testing dataset in Tail-GNN [9] is also imbalanced. We think these experimental settings are not ideal for imbalanced learning due to the limited number of node classes or imbalanced testing datasets. In order to validate the effectiveness of our proposed framework on the imbalanced node classification setting, we select an equal number of nodes in each class for the validation and testing dataset. The training set is randomly sampled from the rest according to train/valid/test ratios = 1:1:8, which is highly imbalanced. The statistics and the imbalance ratio of each dataset are summarized in Table 4. The detailed description of datasets can be found in Appendix F.
Evaluation protocol. For each experiment, we follow the commonly-used linear evaluation scheme for GCL as introduced in [5]. The model is firstly trained in a self-supervised manner, and then the learned representations are used to train and test with a simple l 2 -regularized logistic regression classifier. For results in this section, we train each model in twenty runs for different data splits and report the average performance with the corresponding standard deviation for a fair comparison. In what follows, we measure performance in terms of accuracy, if not otherwise specified.
Imbalanced types. In order to comprehensively evaluate the performance of ImGCL in different imbalanced types, we introduce two imbalanced types [10]: Exp and Pareto, parameterized by an imbalanced factor. Exp imbalanced class distribution is given by an exponential function, where the higher imbalanced factor means the more imbalanced graph. Pareto imbalanced class distribution is determined by a Pareto distribution, where the lower imbalanced factor means the smaller power value of Pareto distribution and thus the more imbalanced graph.

Experimental Results on Node Classification
The empirical performance of imbalanced node classification is summarized in Table 1. ImGCL consistently outperforms current GCL baselines or even the supervised baselines. We summarize Table 1: Summary of performance on imbalanced node classification in terms of accuracy (%) with standard deviation (std). The 'Available Data' means data we can obtain during the training phase, where X, A, and Y denotes the node feature matrix, the adjacency matrix, and the corresponding labels respectively. The highest performance in the GCL and ImGCL category is bold. We highlight ImGCL based on the recently proposed GCL methods with gray background. The highest performance improvement of the GCL baseline w & w/o the ImGCL framework is underlined. our observations from the table as follows: (1) Recently proposed GCL methods [1], which are evaluated on randomly split training and testing sets, exhibit severe performance degradation in our imbalanced node classification setting. By incorporating our proposed ImGCL framework (the gray background), these GCL methods improve by a large margin. Concretely, ImGCL+GCL achieves [41.22%, 34.47%, 28.13%, 23.76%] average absolute gain in accuracy than the baseline GCL models on [Amazon-Computers, Amazon-Photo, Wiki-CS, DBLP], respectively. We also find that the recently proposed GBT [3] obtains the best performance among a set of GCL competitors. We think the reason is that feature decorrelation method in GBT is more fit for the imbalanced node classification and we adopt the GBT baseline model in the following experimental analysis. (2) The traditional methods, e.g., Node2vec and DeepWalk, can achieve competitive performance in the imbalanced node classification task compared with GCL methods. We postulate the reason is that the traditional network embedding methods can take advantage of the homophily [29] property of the given graph to utilize the graph topology features which is important on imbalanced node classification [9]. Moreover, the "Raw features" method without considering the graph topology cannot achieve satisfactory performance, which indicates the necessity of utilizing the graph topology features on imbalanced node classification. (3) Compared with the supervised learning methods GCN and GCN+PBS, the ImGCL framework achieves superior or competitive performance on all datasets, which further corroborates the effectiveness of our proposed framework.

Experimental Analysis
Imbalanced type analysis. In the imbalanced node classification setting, the performance for the head, middle, and tail classes are usually reported [21]. We first divide the Amazon-computers dataset into three disjoint groups in terms of class size:  dataset might break our assumption in Proposition 1 that |θ t − θ * | |µ 2 − µ 1 |, which undermines the convergence guarantee and therefore degrades performance of ImGCL given a fixed number of iterations. Nevertheless, the ImGCL+baseline model consistently outperforms the baseline model. Per-class analysis. We analyze the per-class recall and precision in Fig. 3 to better understand the model bias on the imbalanced node classification. We test GBT on Amazoncomputers under imbalanced experimental settings introduced in Sec. 5. The GBT baseline model exhibits highly skewed performance on head and tail classes. The recall on the most majority and minority class is 82.0% and 4.1% respectively, while the corresponding numbers for precision are 30.9% and 95.8%. We observe that GBT falsely classifies most of the tail class samples into head classes with low confidence but have high confidence on the correctly classified nodes in tail classes [35]. In contrast, GBT with ImGCL obtains relatively balanced recall and precision value on both head (the most majority precision: 30.9% → 81.2%) and tail (the most minority recall: 4.1% → 88.2%) classes, which leads to the substantial improvement in the overall accuracy (i.e., 39.06% → 78.62%) across all classes, as shown in Table 3. Visualization. For a more intuitive comparison and to further demonstrate the effectiveness of the ImGCL framework, we design experiments of visualization on Amazon-computers. We utilize the output embeddings on the last layer of GBT w & w/o ImGCL before softmax and plot the learned representation of the testing graph dataset using t-SNE [36]. As in Fig. 4, GBT w/o ImGCL clearly exhibits minority collapse [28]. In Fig. 4 (a), where the representations in tail classes are mixed together, which fundamentally limits the performance of the baseline model on the tail classes. In com-parison, the learned embeddings of GBT+ImGCL has distinct boundaries among different classes and more compact intra-class structures.

Conclusion
In this work, we study how to improve graph contrastive learning methods on imbalanced node classification, which is a very practical but rarely explored problem. We propose the principled ImGCL framework, which automatically and adaptively balances the representation learned from GCL without knowing the classes and then theoretically justifies it. Through extensive experiments on multiple graph datasets and imbalance settings, we show that ImGCL can significantly improve the recently proposed GCL methods by improving the representations of nodes in tail classes. For the future work, we will explore more data types, such as bioinformatics graphs. We hope our work will extend GCL to more realistic task settings with (underlying) imbalanced node class distribution.

A.1 Proof of Fact 1
The optimal Bayes's classifier is the probabilistic model that makes the most probable prediction for new examples. Thus, we have: where we omit P X (x) in the denominator, which is unrelated to the objective function. Due to the monotonicity property of the log function, we have: So, we will pick the positive sample +1 if Therefore, the optimal Bayes's classifier is: where sign is the indicator function with sign(x) = 1 if x > 0 and sign(x) = −1 otherwise.

A.2 Proof of Proposition 1
At training step t, we obtain the biased decision boundaryθ t and generate corresponding pseudo-labelsŶ t . We perform the balanced sampling method onŶ t to get balanced positive and negative samples and then take them as input for the next training step to getθ t+1 . Suppose the probability of true labels on selected positive samples (+1) and negative samples (−1) are P Y,t (1) and P Y,t (−1), respectively. According to Fact 1, the decision boundaryθ t produces the bias term . We intend to prove that, at training step t + 1, we get a smaller bias term C∆, where C < 1. Without loss of generality, we set σ = 1 in what follows, which can be recovered by dimensional analysis. The optimal balanced decision boundary is θ * = µ1+µ2 2 , and we construct the estimatorθ t+1 =μ t,1+μt,2 2 by the balanced sampling method. Therefore, we need to estimateμ t,1 andμ t,2 conditional on the decision boundaryθ t . Suppose the cumulative distribution function (CDF) of the standard normal distribution with a mean of 0 and standard deviation of 1 is Φ(·). For clarity, we denote x = µ2−µ1 2 > 0 assuming µ 1 < µ 2 and A = 1 √ 2π e − x 2 2 . The imbalanced ratio of positive and negative samples is defined as: Since ∆ = |θ t − θ * | satisfies ∆ |µ 2 − µ 1 | and |∆(µ 2 − µ 1 )| σ 2 = 1, we have the following equation by first-order approximation: The probability of Y = 1 on the left of the decision boundaryθ t is: The probability of Y = −1 on the left of the decision boundaryθ t is: The total probability mass on the left of the decision boundaryθ t is: By translating the Gaussian to zero mean, the unnormalized mean of Y = 1 on the left of the decision boundaryθ t is: Similarly, the unnormalized mean of Y = −1 on the left of the decision boundaryθ t is: The estimated mean on the left of the decision boundary is given by N L /D L where: According to Eq. 9, we have . Dividing both N L and D L by P Y,t (−1), we have: Similarly, on the right of the decision boundary, we get: Next, we can estimateμ t,1 andμ t,2 according to Eq. 18 and 19.

B More Discussions on Graph Contrastive Learning and Imbalanced Learning
Graph Contrastive Learning. Some recent remarkable progress has been made to adapt contrastive learning methods to the graph domain. Typically, the main idea behind graph contrastive learning (GCL) is to learn effective representations in which similar sample pairs stay close to each other while dissimilar ones are far apart [1]. According to [37], we can divide GCL methods into three categories: (1) contrastive learning methods [16-18, 4, 5] aim to reduce the distance between two augmented views of the same nodes/graphs (positive samples), and push apart views of different nodes/graphs (negative samples). These methods mainly differ in several design choices including graph data augmentations, contrasting modes, and contrastive objectives. DGI [16] adopts the InfoNCE principle [20] to the node classification task by contrasting the node-and graph-level representations of the given graph. InfoGraph [17] mainly focus on graph classification task by contrasting graph representation of different granularity via mutual information maximization. MV-GRL [18] utilizes the graph diffusion matrix to construct the augmentation views of the original graph and then contrast node-and graph-level representation by scoring the agreement between representations. GraphCL [4] adopts the SimCLR [38] framework and propose four practical graph augmentation methods to obtain better graph representations. GRACE [5] capitalizes on the idea that data augmentations for GCL should preserve the property of graphs to highlight important node features.
(2) Negative samples play an important role in contrastive learning methods. However, asymmetric network methods [2] get rid of negative samples via the introduction of a predictor network and the stop-gradient operation to avoid mode collapse. (3) Feature decorrelation methods [14,3] has recently been introduced as a new solution to GCL. They focus on reducing the redundancy among feature dimensions by introducing a loss function calculated by the cross-correlation matrix of two augmentation views. Different from our work, these methods mainly assume that the unlabeled graph data distribution is always balanced for GCL. However, in practice, the (unlabeled) class distribution could be highly skewed and lead to sub-optimal generalization on the imbalanced graph dataset.
Imbalanced Learning. It is well known that the degree of many large graphs follows a scale-free power-law distribution, which is long-tailed and highly imbalanced [39]. In this work, we focus on the imbalanced class distribution, which is also ubiquitous for graph datasets. There exists some recent work to study the class imbalance of semi-supervised node classification problems. They mainly improve the imbalanced classification performance by re-balancing the sample ratio of head and tail classes [40,32,41] and transfer knowledge from head classes to enhance model performance on tail classes [42][43][44]. GraphSMOTE [40] utilizes the SMOTE synthetic over-sampling algorithm to up-sample the tail nodes and then improve their prediction performance. ImGAGN [32] aims to improve the representation learning of tail nodes by generating adversarial tail nodes to balance the class distribution of the original graph. DPGNN [43] borrows the idea of metric learning to transfer knowledge from head classes to tail classes to boost model performance. However, they mainly ignore that open-world unlabeled data usually follows the imbalanced distribution, which will lead to performance degradation under unsupervised or self-supervised learning. To our best knowledge, we are the first to explore contrastive learning on highly imbalanced graph datasets.

C More Discussions on Data Sampling Strategies
Different sampling strategies have different specific values of q in Eq. 2, which have different practical meanings introduced below.
Random sampling. The probability of a node from the class k is defined as Ni by setting q = 1 in Eq. 2, referred to as instance-balanced sampling in some literature [21]. A node from class k is sampled proportionally according to the cardinality N k of each class. If we sample nodes from a given graph according to p R k , the highly imbalanced property still remains just like the training dataset in imbalanced learning. It reflects the highly imbalanced and skewed class distribution of real-world data collection.
Mean sampling. The probability of a node from the class k is given by p M k = 1 K by setting q = 0 in Eq. 2, referred to as class-balanced sampling in some literature [21]. A node is sampled with an equal probability for each class. Sampling each class with an equal probability according to p M k has been found to significantly improve the performance of the classifier in long-tailed learning, while being sub-optimal for representation learning [12].

D Ablation Study on Amazon-computers
We conduct ablations using the GBT baseline on Amazon-computers due to its largest imbalanced factor among four datasets, as shown in Tabel 4. In the imbalanced node classification setting, the performance for the head, middle, and tail classes are usually reported [21]. We first divide the Amazon-computers dataset into three disjoint groups in terms of class size: Many, Medium, Few. Many and Few each include the top and bottom 1/3 classes, respectively. Because there are 10 classes of Amazon-computers in total, the classes with sorted indices in decreasing order [1-3, 4-7, 8-10] belong to [Many (3 classes), Medium (4 classes), Few (3 classes)] categories, respectively. We consider four variants of GBT+ImGCL in three settings: GBT with one-stage pseudo-labels (k-means and community detection), multi-stage pseudo-labels (PBS without node centrality), and ground truth labels (true labels). The "k-means" and "community detection" variants only consider node features and graph topology respectively. Compared with these two variants, we conclude that graph topology is more important for PBS of GCL. This aligns with the observation that PBS using node centrality information (GBT+ImGCL) significantly outperforms ordinary PBS (GBT+PBS), which also shows that the proposed node centrality (PageRank centrality) is an effective component in PBS. Moreover, ImGCL achieves better or comparable results compared to the variant with true labels, which means that ImGCL indeed generates faithful pseudo-labels from the learned representations in an iterative manner. Overall, ImGCL substantially outperforms the baseline in terms of overall accuracy and improves the performance in few-and medium-shots categories by a large margin at cost of slightly sacrificing the accuracy on many-shots.

E Hyperparameter Study
We study the hyperparameter sensitivity of our proposed framework ImGCL, and conduct experiments on Amazon-Computers based on the GCN model. We have one main hyperparameter in ImGCL: the re-balanced labeling frequency B. The #Labeling = T /B denotes the number of stages in which class distribution is re-balanced based on newly-generated pseudo-labels. As the #Labeling varies from 6 to 12, our proposed ImGCL achieves relatively stable performance. We can also find that when #Labeling is larger than 10, the accuracy slightly decreases but the variance largely increases. We conjecture that when we produce pseudo-labels frequently, the GCL model cannot quickly adapt to the new sample distribution, which leads to large fluctuations in performance. In summary, we find the performance of our framework is relatively stable across different values of hyperparameter #Labeling.

F Experimental Setup
For reproducibility, we provide all websites of the baseline GNN models and datasets. Our codes and data are publicly available 3 .

F.2 Datasets
The statistics of datasets we used in experiments are summarized in 4. We also provide a brief description of datasets in the experiment section as follows: • Wiki-CS [1] is a reference network constructed based on Wikipedia. The nodes represent articles about computer science and the edges represent the hyperlinks between two articles. Each node corresponds to a label representing a branch of the field. Node features are calculated by the average of word embeddings in each article.
• Amazon-Computers and Amazon-Photo [11] are two networks of co-purchase relationships constructed from Amazon. The nodes represent goods and the edges indicate that two goods are frequently bought together. Node features are bag-of-words encoded product reviews, and class labels are given by the product category.
• DBLP [11] is a citation network constructed from DBLP website. The nodes represent papers and the edges represent the citation relationship between two papers. For each paper, a sparse bag-of-words vector is utilized as the node feature vector. The node labels are defined according to their research topic.

G Preliminaries of GNN Encoders
Typically, the training process of modern GNN encoders follows the message-passing mechanism [45] in graph contrastive learning (GCL). During each message-passing iteration, a hidden embedding h (k) u corresponding to each node u ∈ V is updated by aggregating information from u's neighborhood N (u), which can be expressed as follows: where UPDATE and AGGREGATE are arbitrary differentiable functions (i.e., neural networks), and m N (u) denotes the "message" that is aggregated from u's neighborhood N (u). The initial embedding at k = 0 is set to the input features, i.e., h u = x u , ∀u ∈ V. After running k iterations of the GNN message-passing, we can obtain information from k-hops neighborhood nodes. Different GNNs can be obtained by choosing different UPDATE and AGGREGATE functions. For example, the classical Graph Convolutional Networks (GCN) [30] updates the hidden embedding as where H (l+1) = h (l+1) 1 ; · · · ; h (l+1) n is the hidden matrix of the (l+1)-th layer.Â =D −1/2 (A+ I)D −1/2 is the re-normalization of the adjacency matrix, andD is the corresponding degree matrix of A + I. W (l) ∈ R C l ×C l+1 is the filter matrix in the l-th layer with C l referring to the size of l-th hidden layer and σ(·) is a nonlinear function, e.g., ReLU.