Rethinking Semi-Supervised Imbalanced Node Classification from Bias-Variance Decomposition
Authors: Liang Yan
Gengchen Wei
Chen Yang
Shengzhong Zhang
Zengfeng Huang
Venue: NeurIPS 2023 poster (2023)
Keywords: Imbalanced Node Classification
Bias-Variance Decomposition
Graph Neural Networks
TL;DR: A novel framework regularizes the model’s variance, introducing a new perspective for semi-supervised imbalanced node classification.

Abstract: This paper introduces a new approach to address the issue of class imbalance in graph neural networks (GNNs) for learning on graph-structured data. Our approach integrates imbalanced node classification and Bias-Variance Decomposition, establishing a theoretical framework that closely relates data imbalance to model variance. We also leverage graph augmentation technique to estimate the variance and design a regularization term to alleviate the impact of imbalance. Exhaustive tests are conducted on multiple benchmarks, including naturally imbalanced datasets and public-split class-imbalanced datasets, demonstrating that our approach outperforms state-of-the-art methods in various imbalanced scenarios. This work provides a novel theoretical perspective for addressing the problem of imbalanced node classification in GNNs.

Rethinking Semi-Supervised Imbalanced Node Classification from Bias- Variance Decomposition
Divin Yan', Gengehen Weit, Chen Yang', Shengzhong Zhang", Zengfeng Huang?*
Fudan University, (yan121, gcwei22, yanc22) fudan. edu. cn (szzhang17, huangzf)0fuun @fudan edu.
Abstract
This paper introduces a new approach to address the issue class imbalance in graph neural networks (GNNs) for learning graph-structured data. Our approach integrates imbalanced node classification and Bias- Variance Decompo- sition, establishing a theoretical framework that closely relates data imbalance model variance. We also leverage graph augmentation technique to estimate the variance, and design regularization term to alleviate the impact of imbalance. Exhaustive tests are conducted on multiple benchmarks, including naturally imbal- anced datasets and public-split plass-imbalanced datasets, demonstrating that approach outperforms state-of-the-ar methods in various imbalanced scenarios. This work provides novel theoretical perspective for addressing the problem of imbalanced node classification in GNNs.
1 Introduction
Graphs are ubiquitous the real world, encompassing social networks, financial networks, chemical molecules [22, 46, 9] and so on. Recently, graph neural networks (GNNs) [16, 35, 9] have shown exceptional proficiency in representation learning on graphs, facilitating their broad application in various fields. Nevertheless, the process of learning on graphs, analogous to its counterparts in computer vision and natural language processing, frequently encounters significant obstacles in the form of skewed insufficient data, leading the prevalent issue of class imbalance. It is undeniable that real-world data often exhibits biases and numerous categories, which entail data limitations and distribution shifts to be common. Furthermore, coupled with the fact that GNNs often feature shallow architectures to prevent "over-smoothing" or "information loss", training with such datasets leads to severe over-fitting problems in minor classes.
Designing GNN imbalanced learning schemes for graph-structured data poses unique challenges, unlike image data. Graph-structured data often requires consideration of the data's topology and environment, and empirical evidence [6, 24, 31] shows that topological asymmetries can also affect the model's performance. However, due to the extremely irregular and structured nature of the data, quantifying and solving topological asymmetry is difficult and computationally intensive. As result, existing methods such as oversampling [28, 50, 24J and loss function engineering [6, 31] are problematic for achieving satisfactory outcomes. data personalization exhibits very poor scalability and generalization capability. Furthermore, the prevalence of this problem has prompted the community to seck a more effective framework for imbalanced lcarning. Thus, more fundamental and theoretical perspective is urgently needed when considering the imbalance node classification problem.
depth, the modeling approach for
"Corresponding Author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Following the idea, in this work, we propose a novel viewpoint to understand graph imbalance through the lens of Bias- Variance Decomposition. The Bias- Variance Decomposition [1. 2, 23. 45] has long been applied in terms of model complexity and fitting capacity. Our theoretical analyses have confirmed the relationship between model variance and the degree of dataset imbalance, whereby an imbalanced training set can lead to poor prediction accuracy due to the resulting increase in variance. Furthermore, we conducted some experiments on real-world dataset and the results demonstrate a significant relationship between the variance and the imbalance ratio of the dataset. As fär as know, we were the first to establish a connection between imbalanced node classification and model variance, which conducts theoretical analysis in this field.
Moreover, we have devised a regularization term for approximating the variance of model, drawing on our theoretical analysis. The main challenge of this idea lies in estimating the expectation across different training sets. Our key insight to leverage graph data augmentation to model the different training sets in the distribution, which has not been explored before. Our empirical evaluations have consistently demonstrated that our algorithm, leveraging three basic GNN models [16, 35, 9], yields markedly superior performance in diverse imbalanced data settings, surpassing the current state-of-the-arr methods by a substantial margin. Notably, we have conducted meticulous experiments on two naturally imbalanced datasets, which serve as the realistic and representative benchmarks for real-world scenarios.
Our contribution can be succinctly summarized as follows: (i) We are the first to integrate imbalanced node classification and Bias- Variance Decomposition. Our work establishes the close relationship between data imbalance and model variance, based on theoretical analysis. (ii) Moreover, we are the first to conduct a detailed theoretical analysis for imbalanced node classification domain. (iii) Our principal insight is to leverage graph data augmentation as means of representing the varied training sets that lie within the distribution, whilst simultancously designing regularization term that approximates the model's variance. (iv) We conduct exhaustive tests on multiple benchmarks, such as the naturally imbalanced datasets and the public-split clas--iballaned datasets. The numerical results demonstrate that our model consistently outperforms state-of-the-art machine learning methods and significantly outperforms them in ceavily-imbalanne scenarios.
2 Preliminaries
2.1 Notations
We concentrates on the task of semi-supervised imbalanced node classification within an undirected and unweighted graph, denoted as G = (V, E, VL). V represents the node set, E stands for the edge set, and VL C V denotes the set of labeled nodes. The set of unlabeled nodes is denoted as VU : V \ VL The feature matrix is X E gaxf, where is the number of nodes and is the feature dimension. The adjacency matrix is denoted by A E [0,1] 1|nx,, Let N(v) represent set of adjacent nodes to node v. The labeled sets for each class are denoted as (C1, C2..... Ck), where C; represents the labeled set for class i. The imbalance ratio p. is defined as p = max; |C,l / min; C
2.2 Graph Dataset Augmentations
To craft diversified perspectives of the graph dataset, we deploy advanced graph augmentation methodologies, leading to the formation of G (A, X) and G' (Á', X'). Flements such as node attributes and connections within the foundational graph are selectively obfuscated. These augmented perspectives are subsequently channeled through a common Graph Neural Network (GNN) encoder, symbolized as fa = x / + ga in order to distill compact node-centric embeddings: To(A,X) = h E aad and (A X') h E Raad
2.3 Related Work
Semi-Supervised Imbalanced Node Classification. Numerous innovative approaches[28, 40, 50, 19, 25, 6, 24, 31, 43) have been proposed to tackle the difficulties arising from imbalanced node classification on graph data. GraphSMOTE [50] employs the SMOTE [5] algorithm to perform interpolation at the low dimensional embedding space to synthesize the minority nodes, while ImGAGN [25] introduces GAN [8] for the same purpose. Another work GraphENS [24] synthesizes
2

---

mixed nodes by combining the ego network of minor nodes with target nodes. To address topology imbalance in imbalanced node classification task, ReNode [6] adjusts node weights based on their proximity to class boundaries. TAM [31] leverages local topology that automatically adapts the margins of minor nodes. Due to spatial constraints, we provide comprehensive exposition of other relevant literature in Appendix A.
3 Theory
3.1
Theoretical Motivation
This section presents a succinct overview of the classical Bias-variance Decomposition [1, 23, 45] and its application to supervised node classification. Furthermore, we illustrate the influence of imbalance on classification results, which subsequently amplifies the variance.
Slas-variance Decomposition. Let E X and E Y denote the input and label, respectively, Consider an underlying mapping f: Y and the label can be expressed as y = f(x) + e, where
is some noise. Given a training set D = (2), we train a model f(x) = f(x; D) using the samples in D.
Definition Bias-Variance Decomposition is that the expected predicted error of I can be decom- posed into Eq(I),
ED (u f(x; (Bias[f(a))) VarnIf(x; Irreducible error,
(I)
where Bias [ias[f(=)] Exlf(x; D) f(x)] ED[[(x; B[y(z)), and VarpIf(z;
ED
f(x; (Bo
is important to note that this expectation taken with respect to both the training sets D and the predicted data r. The bias term reflects the model's 's ability to fit the given data, while the variance term indicates the stability of the model's results with different training sets. In other words, the variance describes the model's generalization performance.
Next, we consider the specific formulation of variance in the setting of semi-supervised node classification on graph. First, we make some assumptions to simplify the analysis.
Assumptions. We make two assumptions in our approach. Firstly, we assume that the node embeddings h node x' extracted by a graph neural network for nodes belonging to class follow multivariate normal distribution h ~ N (n', A*), where A is diagonal matrix for all i 1,2, Here, let h² μ² which follows the distribution e¹ N(0 A²).
Secondly, we consider a simple classifier that estimates the probability of a node belonging to particular class based the distance h"C', Here, C C² (D) 1 of labeled node embedding in training set D, where n, is the number of nodes in class C follows the distribution C ~ N (u', T.e A.). Similarly, we denote e = =C ーرr² and follows that e' ~ (o, A.)
n, (h +... hr,) the average
Variance for Semi-supervise Node Classification. Under the above assumption, we can write the variance generated by different sampling training set explicitly. For a node x that belongs to class the variance can be written:
Var(x)
ED
(1) -zD [NT ( (x)())))
Σ
Est (IT(z)((²
( - (2))x) (()))))
(2)
1=1
Ee (1)(())))))
1 ( Σ
m
3

---

The last equation is derived from the variance of multivariate normal distribution. The variance over the whole graph Ei=1 Eg [Var(=)] = Ei= Ex hT (x))Ah((z) the expectation of Equation node
Variance and Imbalance. In Equation 2, we notice that the variance of specific class i is propor- tional 1. This reveals relation between imbalance and variance. If assume F. [h ( (x)) the same for different i, then the following theorem holds:
Theorem Under the condition that Ei T4 constant, the variance Ei= Eg M. (=)(()))h())) reach its minimum when all n. equal.
The proof is include in Appendix B.1. As the ratio of imbalance increases, the minority class exhibits smaller sample size n,, which consequently makes greater contribution the overall variance. This result gives an new perspective of explanation about why the model shows poor performance under imbalance training, that variance will increase the training becomes imbalanced. To substantiate our analysis, we conducted an experimental study to show the relation between imbalance and the variance. The result is shown in Figure
0.034
0.032
0.0255
Variance
Variance
0.0250
Variance
86.030
0.020
8.0255
0.028
0.018
0.0200
0.0175
0,024
0.018
0.150
0.022
10
10:
101
(a) CiteSeer-GCN
(b) CiteSeer-GAT
(c) SiteSeer-SAGE
Figure 1: We examine the alteration in variance concerning node classification as the imbalance ratio increases on and plot the regression curves for variance and imbalance ratio. We conduct this experiment using a fixed number of training set nodes but different ones, to mitigate the influence of the number of training set nodes on variance, Detailed experimental setup Appendix D.2.
3.2 Variance Regularization
Optimize Variance during Training. Both our analysis and the experimental results show that the increase of variance is a reason for the deterioration of performance for imbalance training set. Therefore, We propose to estimate the variance and use as regularization during training. We decompose the model into two parts. A GNN E is utilized as feature extractor, and a classifier P predict probability based on the feature extracted by GNN. We define variance of conditioning E of as Equation evaluated for fixed GNN E. Then we take this as regularization. By optimizing this term, we allow the model to automatically search for the feature extractor that yields the smallest variance during the optimization process.
Estimate the Expectation with Labeled Nodes. The most challenging aspect lies in the estimation of variance, we lack access other training sets. Therefore, we propose Lemma to estimate the variance on training set with the variance on labeled data. The proof is included in Appendix B.2.1.
Lemma Under the above assumption for V "(L,,,) C N (n' A.). minimizing the
Di En [Var(x)) is equivalent minimizing Equation 3:
Σ ZEG 2m
Σ
h(x)=
(hi
1b)
2
ny
(nL + c.)" /2n;
1
(ef - c5) (3)
N
/2ni
N

---

Estimate the Expectation with Unlabeled Nodes. Lemma allows us to replace the sampling on training set with sampling on labeled node pairs (hj. hi) of class i. However, to evaluate Equation it still needs to have access to embedding pair (h₁, h2) that belong to the same class i. Since labels are searce, such node pairs is difficult obtain. To make our algorithm more practical, a way of utilizing unlabeled nodes for estimating Equation 3 is required. We accomplish this goal through two steps. In the first step, we use graph augmentation to obtain pseudo embedding pair (/1 f2).. Graph augmentation is typical used technique in graph contrastive learning. It generate new view G' of a graph G by adding noise to the graph structure. For a node x in two different views G, G", the resulting embedding h, h can be seen that of two different nodes. Thus, they can be used to replace true embedding pair in Equation 3.
However, these pseudo node pairs give no information about which class it belongs to. Thus it prohibits us from assign proper v2n; for different in Equation 3. is such coefficients that compensate on the minority class, so it's crucial to reintroduce the message about class number for constructing variance regularization. Therefore, in the second step, we use the class center C to replace h in Equation 3, as shown in Equation 4. Since C³ = /e¹ + e² and the variance of et is proportional to I, using Equation estimate Lemma I can apply the similar compensatory for the minority class. More mathematical details presented in Appendix B.2.1.
n.
(CC))(()
ZEG i=1
n2 ΣEΣ (w)) (c) - (c
N
From the Viewpoint of Graph Sampling. We notice that an alternative perspective can be adopted to interpret this regularization term. Given graph data G. we should acknowledge that there exists some noise in its structure or feature, as a result of measuring. This randomness also attribute to the variance of classification. Assume each graph in our dataset a sample drawn from an underlying true graph G. Denote the classification result trained on G as [x; G). Then the variance on G can be written
Varg EzeG EG [If G) (zlf(>; G)
(5)
Taking f(x) h=()(,, it straitforward to show that Equation and Equation 5 are same.
Despite the algorithm obtained through this new interpretation being identical to the previous one, is worth noting that the two interpretations differ significantly. The former incorporates information from unlabeled nodes and assumes the variance originates from selecting different nodes as the training set. Graph augmentation facilitates the sampling of node pairs belonging to the same class. The latter, on the other hand, considers the same training set, but the variance originates from the entire graph's 's information. Graph augmentation is used to simulate the process of sampling the training graph from the underlying true graph.
4
The Final Algorithm
In this section, we introduce our ReVar (Regularize Variance) framework which is based on previous theoretical frameworks for optimizing model variance. We explain our innovative approach to approximating the model's variance and using it as a regularization term in our algorithm in Section 4.1. Section 4.2, we discuss how we integrate the GCL framework with a new contrastive learning term designed for semi-supervised learning tasks. Lastly, we present the final formulation of our optimization objective Section 4.3, which optimizes both the cross-entropy loss function and our variance-constrained regularization term, providing comprehensive approach to improve the performance of semi-supervised imbalanced node classification tasks.
4.1 Variance-constrainee Optimization with Adaptive Regularization
To initiate, we elucidate the methodology underpinning the computation of Equation 4. Initially, we calculate the class center C corresponding to each class. Following this, we systematically construct
5

---

Labeled nodes Unlabeled nodes
V Optimization
Intra-Class Aggregation Regularization
with Adaptive Regularization
GNN encoder
de Class center
label probubilitt distribution
dimansionz moaaniion
(r transform
Node features
Undend pudes
(L.A)
(2.4)
cartert
Gentole
dimension Class center
CE
probabiity
distibbttion
fo
transform (-11.e)
dimunioon
Undiiind rocess
Node features
dimension 1
(a) Graph augmentations
(b) Intra-view and regularization
Variance regularization [Corresponding Lyx)
(Corresponding
Figure 2: Overall pipeline of ReVar. (a) Two different views of the graph G, G' are obtained by graph augmentation trans form and are subsequently fed into GNN encoder fa. (b) Intra-class and inter-class representations are aggregated, which means, for labeled nodes, it's positive samples not only belong to the same class in both view but also in the other view. (c) Variance is estimated by Equation 4. Specifically, the label probability distribution computed for each node in two views based on it's similarity with each class center. And the difference between two probability distributions used to approximate the model's variance and also optimized as one term the loss function.
a probability distribution reference matrix, denoted by S := [C1 Ck]. It's worth noting that the assemblage of class centers is represented by C' = (Ci; C2;,..;;a,) Ck).
Given a node with its associated embedding h, the label probability distribution x; pertaining to node i is ascertainable via the subsequent equation:
exp (sim (h,, CT)
1i=1 exp (sim (h,, Ci) /T)
In the aforementioned equation, के. signifies the j-th dimensional component of π; sim(.s) .)) denotes the function to compute the cosine similarity between pair of vectors, and is specified temperature hyperparameter.
Subsequent to this, for every node i V, we determine the label probability distribution. Distinctively, म; and म are derived from & and G", respectively. The former acts the prediction distribution, whereas the latter represents the target distribution. Our approach then aims to minimize the cross- entropy between these two distributions.
It's paramount to underscore that for each labeled node within G' its one-hot label vector is directly assigned # = yı for all E Vz. This diverges from the procedure of deducing the predicted class distribution as described in Equation 6. This methodology is purposed to optimally leverage the extant label information.
However, a simplistic minimization the aforementioned loss might engender confirmation bias. This is attributed to the potentially inaccurate #/ estimated for the unlabeled nodes (i.e., Vu), an aspect that can deleteriously impact the efficacy of pseudo-labeling-orieee -orientte semi-supervised methodologies. To address this concern, introduce confidence-based label-guided consistency regularization [41, 30, 48), as detailed below:
CVR = |Vont
Σ CE (E
+
Σ CE (yt, ū.)
VE
V
VEV
where Venff {vz [max(({)>e) 1, E Vo represents the set of nodes with confident predictions, v is the threshold for determining whether a node has confident prediction, and 1 (...) an indicator function.

---

In the context of confidence determination for nG, we employ criterion wherein value is appraised as confident if its maximum constituent surpasses stipulated threshold. We postulate that a heightened threshold, represented by acts as a safeguard against confirmation bias. This stratagem ensures that only high-caliber target distributions, specifically 7. have pivotal influence on Equation 7.
4.2 Intra-Class Aggregation Regularization
In this section, we propose an extension to the concept of graph contrastive learning that emphasizes the invariance of node representations semi-supervised scenarios. To achieve this, we partition the nodes into two groups: labeled and unlabeled. Specifically, for the unlabeled nodes, we learn node representation invariance through the use of positive examples exclusively. For each labeled node in both views, its positive sample no longer includes itself in the other view, but instead encompasses all labeled nodes in both views belonging the same class. Through this approach, labeled nodes belonging to the same class can be aggregated, enabling the model to lear that representation invariance now applies not to single node, but the complete class representation.
LR
Σ hv.
sim (he h/)
Σ Iml Eg
sim (h, h2)
+
Σ Zm bibyec
Σ
sim (h, hy))
VV
Naul
(8)
where Nou => =
[C,[ - h, and hy represent feature embedding in G and Ō" respectively for node To the best of our knowledge, we are the first to introduce label information into the contrastive learning paradigm to obtain invariant representations within the context of intra-class variation and address the challenge of remi-supervisedd imbalanced node classification. Notably, approach only utilizes positive examples, which significantly reduces the model's 's training complexity and enhances its scalability and generalization capabilities.
4.3 Objective Funetion
To derive our ultimate objective function, we incorporate both LVR and Lin- These are weighted by coefficients x and A2, respectively. Formally, the amalgamation can be represented as:
Coomposite \1CVR + X2 + Ssup
Additionally, we introduce the cross-entropy loss denoted by Luup which is established over collection of labeled nodes, denominated Vi.
5 Experiment
5.1
Experimental Setups
Datasets and Baselines. We have demonstrated the efficacy of our method on five commonly used benchmark datasets across various imbalance scenarios. For the conventional setting (p=10) of imbalanced node classification in [50, 24, 31], we conducted experiments on Cora, CiteSeer, Pubmed, and Amazon-Computter. More precisely, we select half of the classes the minority classes and randomly convert labeled nodes into unlaheled ones until the training set reaches an imbalance ratio of p. To be more precise, for the three citation networks, as our initial splits, with an initial imbalance ratio of p. In order to better reflect real-world scenarios, conducted representative experiments on the naturally imbalanced datasets Amazon-Compur and Coauthor-Ch CS. For this setting, we utilize random sampling to construct training set that adheres the true label distribution of the entire graph. The comprehensive experimental settings, including the evaluation protocol and implementation details of our algorithm, are explicated in Appendix E. For baselines, we evaluate our method against classic techniques, including cross-entropy loss with re- seweeighting [13], PC Softmax [12], and Balanced Softmax [26], as well as state-of-the-art methods for imbalanced node classification, such as GraphSMOTE [50], GraphENS [24], ReNode [6], and TAM [31]. See Appendix E for implementation details of the basclines.
adopt the standard splits proposed by [44]
7

---

GNN Encoder Selection. As the foundational structures for our GNN encoder, we harness archi- tectures such as GCN [16]. GAT [35], and GraphSAGE [9].
5.2 Main Results
Experimental Results Under Traditional Semi-supervised Settings. Table presents the eraged balanced accuracy (bAcc.) and F1 score, along with their standard errors, obtained by the baselines and Re three class-imballe iass-imbalnnced node classification benchmark datasets, where p 10. The outcomes showcase the superiority ReVar in comparison to the existing methods. Our proposed technique exhibits consistent and significant oufperformance of the state-of-the-an approaches across all three datasets and three base models. In all cases, ReVar achieves decisive advantage that underscores its efficacy in addressing the challenge of class imbalance in node classification. Due space limitations, the experimental results and analysis on Cora are presented in the Appendix C.
Table 1:
Comparison of our method ReVar and other baselines on three benchmark datasets. Experimental results are measured by averaged balanced accuracy (bAcc.,%, and Fi-score (%) with the standard errors over repetitions on three GNN architectures. Highlighted are the top first and second. A is the margin by which our method leads ofte--of-hheart method.
Dataset
CiteSeer- Semi
PubMedd- Seiie
Computers Semi
Imbalance Ratio 10)
bAcc.
bAce.
F1
bAce.
Vanilla
38.72 1.8
28.74 3.21
65.64
1.72
56.97
3.17
80.01 #
71.56
Re-Wost Re-Weight
44.69 à 1.76
38.61
1:3
69.06
1M
64.08
1.97
80.93 a 1.30
73.99
2:20
PC Softmax
72.46
70.27
81.54 + 676
73.30
GCN
GraphSMOTE
44.87 L.22
39.20 1.52
67.91
62.68
1.92
79.48 6:4
72.63
BalancedSoftmax
55.52 0:9
$3.74 1.42
73.73 0:080
71.53
1.06
81.46 +: 0.34
74.31 0:051
+ TAM
56.73 +:0.1
56.15 0.0.8
74.62
0.0
72.25
1.30
82.36 0,67
72.94
Renide
13.47 3..5
33..5
71.40
T:T
G7.27
Σ06
88,89 EoT
73.13
1: T.66
+ TAM
46,20 L.17
39.96 2.76
72.63 200
68.28
3,30
80.36 1.19
72.51
GraphENS
36.57 1:998
55.22 1.335
72.13
T.4
70.72
1.07
6:0
74.26
TAM
58.01
56,32
74.14
1:42
72.42
81,02 6:99
70.78
1.72
ReVar
65.28 4:051
64,91 4:051
79.20 0:022
78.45 0.46
84.67 0:0
80.25 030
(.7.2702336)
+ 8.59(15.59)
5.06663228)
6.03
2.27(
5,94(7.99))
Vanilla
38.84
31.25
64,60
55.24
79.04
70.00
Re- ReiWetght
45.47 235
40.60 +: 1.98
68.10 2:5
3.54 63.76
80.38
0.66
69.99
PC Softmax
50.78 1,66
1.08 38.96
72.88 030
71.09
0:8
1: 0.9
71.33
GraphSMOTE
45.68
67.43
61.97
2.54
79.38
69.76
GAT
BalancedSoftrux
54.78 1.25
$1.83 2.11
72.30 1:20
69,30
1.79
82.02 1.39
72.94
+ TAM
56.30 1.25
53.87 1.14
73.50 1:M
71.36
1.99
75.54
3.00
66.69
Renode
44.48
37.99 2:87
69.93 2.16
63.27
16.01
66.12
+ TAM
45.12
39.29 +
70.66
2:2
66.94
3.54
1.13 74.30
66.13
GraphENS
51.45 + 1.26
47.98 #.266
73.15
T.44
71.90
1.08
81.22
0.44
71.23
TAM
56.15
54.31
73.45
72.10
81,07
71.27
ReVar
66.04 0:66
65.70 0.5.
77.85 0.766
77.08 0.69
86.37 0.000
82.35
A
1.89(12669))
11.39cu979)
5.90))
4.98
4,35
+ 9.41
Vanilla
43.18
36.66
68.68
64.16
72.36
64.32
Re- Re-Weight
46.17
40.13 3::.
69.89
65.71
2.31
76.08
65.76
PC Softmmx
50.66 0.99
47.48 1.56
71.49 0.4
70.23 0.67
74.63
+ 3.01
66.44
GraphSMOTE
42.73
35.18
66.63
61.97
71.85
68.92
SAGE
BalancedSoftmaa
51.74 2.32
49.01
11.36
69.66 1.81
73.67
65,23
+ TAM
51.93 2.19
48.67 3.25
72.28 1:47
71.02 1.31
77.00 1.5
70.85
Renode
1:57
1:30
71.37 1:51
67.78
77.37 6.6
+ TAM
48.39
43.56 4:31
71.25
68.69
74,87
66.87
CiraphT:NS
33.551 1.75%
7037
70700
"W2.37 Eo0
7
TAM
53.56
73.61
72.50
82.17 0:0
72.46
ReVar
60.48
57.99
77.72
76.01 1:30
83.50
76.48
A
+ 5.79
+ 4.533...405)
+ +..11.5
+ 3.51
1.933..133)
+ 4.02
Experimental Results On Naturally Imbalanced Datasets. Our model was evaluated on two naturally imbalanced datasets, Coauthor-CS (p RJ (1)0) and Amazon-Computters (p 17.7), both of which exhibit imbalanced unlabeled data (as indicated Table 7). The construction of the training, validation, and testing sets is detailed in Appendix E. Experimental results presented in Table

---

Table 2: Comparison of our method Va and other baselines on CS-Random. Highlighted are the top first and second. A is the margin by which our method leads ofateoof-the-an method.
Datasc((CS-Random)
GCN
GAT
SAGE
Imbalance Ratio(p = 41.00)
bAcc.
hAce,
F1
hAcc.
F1
Vanilla
84.85 +: 0
87.12 = 0.14
82.47
=0.36
84.21
0.31
83.76
022
86.22 0:0.1
Re-Weight
87.42
88.70
83.55
84.73
85.76
87.32
PC Softmax
88.36 a:
88.94 004
85,22
0:31
85,54 0:3
87.18 0.14
88.00 1.0.9
GraphSMOTE
85.76 +: 1.75
87.31 = 1.3
84.65
1.33
85.63 1:1
85.76 = 1.98
87.34 0.98
BalancedSoftmux
87.72 +: 0.07
88.67 = 0.n
84.38 0.20
84.53
0.11
86.78
0.00
05 s: 0.09
'TAM
88.22
89.22
85.48
85.77
87.83
88.77
Rénöde
87.53
5 6.IT
88.91 =00ss"
85.98
0.19
86.97 = 0.0
86.13
= 0.15
"8.89 89 0.39
TAM
87.55
+: 0.06
89.03
=: n.0
86.61
0.30
87.42
0.2
85,21
= 0.33
87.01 # 0.3.
GraphENS
85.97
166.6 68 67300
85.86
0.19
88.51 =33""
85,39
886 1034"
-AM
86.34
0.12
87.36
0.08
86.29
0.20
87.28
0.13
85.99
0.13
87.25 0.07
Ve
88.44 0.16
89.54 0.11
87.33
0.04
88,33 0.05
90.11 =00.1
91.18 a 0.11
A
(.08
0.32
0.72
+ 0.91(1.08)
+ 2.28(2600)
2.4122299)
4 and Table 2. Notably, ReVar outperformed other methods consistently on these two datasets, significant finding given the challenging nature of the imbalanced data in these datasets.
5.3 Further Analysis of ReVar
Analysis Each Component in the Loss Function. As shown in Figure 3a)) each component of our loss function can bring performance improvements. In particular, in all three settings in the figure, our full loss achieves the best scores. all cases, VR loss improves the performance of the model, proving hypothesis that can approximate the variance of the model improve the performance of the model. More analysis presented in Appendix D.
78-
SAGE
22 (96)
75
Vontlla GAT
Our GAT
F1-score(0p
Loss
SCV
Model
BAT
G2N
025
225
325 42554552233
À1
60
03
15
25
35
A2
4.
53
85
Epoch
(a) Computers-Semt
(b) Pubmed-Xi A1
(c) PubMed-A2
(d) CiteSeer-Loss
Figure 3: Analysis of Re Var.
Sensitive to Hyperparameters Aı and Az. The two intensity terms, ar and λ2, corresponding to the LVR and LIR, respectively, is depicted in Figure 3(b), 3(c). We explore the impact of perturbations on model performance when one of the two intensity terms is held constant while the other is varied. We believe that smaller value of À is inadequate to reflect the regularization of Re Instead, suitable values of can significantly enhance the performance of ReVar. More analysis is presented in Appendix D.
The present study includes comparison of Re Var and Vanilla models(only use cross-entropy) terms of their loss and Fl score. As shown in Figure 3(d), various models were evaluated. The ReVar model, which incorporates additional LVR and LIR components, demonstrated a faster convergence of loss, as evidenced by the larger slope Figure 3(d). More analysis is presented in Appendix D.
Analysis of Test Loss and F1 Score Curves.

---

Conclusion and Future Work
This paper presents novel approach address imbalanced node classification, Our method integrates imbalanced node classification and the Bias- Vars-Varinnce Decomposition framework, establishing theoretical foundation that closely links data imbalance model variance. Additionally, we employ graph augmentation techniques to estimate model variance and design a regularization term to mitigate the impact of class imbalance. We conduct exhaustive testing to demonstrate superior performance compared to state-of-the-er methods in various imbalanced scenarios. Future work includes extending ReVar and its theories the fields of computer vision and natural language processing. Moreover, we anticipate the emergence of more effective theories and algorithms to be developed and flourish.
Acknowledgements
This work is supported by National Natural No.62276066.
Science Foundation of China No. N2.12241212,
Reproducibility Statements
The model implementation and data is released at https//giihbb..oom/yyaaianngggg
References
[1] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias variance trade-off. Proceedings of the National Academy of Sciences, 116(32)15844--1588 15854, 2019.
[2] Erica Briscoe and Jacob Feldman. Conceptual complexity and the bias/variance tradeoff. Cognition, 118(1):2-16, 2011.
[3] Jiarui Cai, Yizhou Wang, and Jenq-Neng Hwang. Ace: Ally complementary experts for solving long-tailed recognition in one-shot. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 112-121, 2021.
[4] Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with sineelddisirbutionawwweaa margin loss. Advances in neural information processing systems, 32, 2019.
[5] Nitesh V Chawla, Kevin W Bowyer, Lawrence Hall, and Philip Kegelmeyer. Smote: synthetic minority over-sampling technique. Journal of artificial intelligence research, 16:321- 357, 2002.
[6] Deli Chen, Yankai Lin, Guangxiang Zhao, Xuancheng Ren, Peng Li, Jie Zhou, and Xu Sun. Topology-imbalance learning for sumi-super node classification. Advances in Neural Information Processing Systems, 34:29885-29897, 2021.
[7] Yoav Freund and Robert Schapire. A theisicn- generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-11) 139, 1997.
[8] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 63(1 1):139-4444 2020.
[9] Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[10] Hui Han, Wen- Yuan Wang, and Huan Mao. Borderline-smote: new over-sampling method in imbalanced data sets learning. In International conference on intelligent computing, pages
Springer, 2005.
[11] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference computer vision, pages 1026-1034, 2015.
10

---

[12] Youngkyu Hong. Seungju Han, Kwanghee Choi, Seokjun Seo, Beomsu Kim, and Buru Chang. Disentangling label distribution for long-tailed visual recognition. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 6626-6636, 2021.
[13] Nathalie Japkowicz and Shaju Stephen. The class imbalance problem: A systematic study. Intelligent data analysis, 6(5):429-449) 2002.
[14] Bingyi Kang. Saining Xie, Marcus Rohrbach, Zhicheng Yan, Albert Gordo, Jiashi Feng, and Yannis Kalantidis. Decoupling representation and classifier for long-tailed recognition. In International Conference on Learning Representations, 2019.
[15] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
[16] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint (eXXiv:609.099000 2016.
[17] Bolian Li, Baoyu Jing, and Hanghang Tong. Graph communal contrastive learning. In The Web Conference, 2022.
[18) Xu- Ying Liu, Jianxin Wu, and Zhi-Hua Zhou. Exploratory undersampling for class-imbalance learning. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 39(2):539- 550, 2008.
[19] Yang Liu, Xiang Ao. Zidi Qin, Jianfeng Chi, Jinghua Feng, Hao Yang, and Qing He. Pick and choose: a gnn-based imbalanced learning approach for fraud detection. In Proceedings of the Web Conference 2021, pages 3168-3177, 2021.
[20] Zhining Liu, Pengfei Wei. Jing Jiang, Wei Cao, Jiang Bian, and Yi Chang. Mesa: boost ensemble imbalanced learning with meta-sampler. Advances in Neural Information Processing Systems, 33:14463-14477 2020.
[21] Aditya Krishna Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar. Long-tail learning via logit adjustment. arXiv preprint 2007v:2007.07314, 2020.
[22] Mohammadreza Mohammadrezaci. Mohammad Ebrahim Shiri, and Amir Masoud Rahmani. Identifying fake accounts on social networks based on graph analysis and classification algo- rithms. Security and Communication Networks, 2018, 2018
[23] Brady Neal, Sarthak Mittal, Aristide Baratin, Vinayak Tantia, Matthew Scicluna, Simon Lacoste- Julien, and loannis Mitliagkas. A modern take on the viri-nariance tradcoff in neural networks. arXiv preprint arXiv: /0.::////..00000 110008891, 2018
[24] Joonhyung Park, Jaeyun Song, and Eunho Yang. Graphens: Neighbor-aware ego network synthesis for class-inbalanced node classification. In International Conference on Learning Representations, 2021.
[25] Liang Qu, Huaisheng Zhu, Ruiqi Zheng, Yuhui Shi, and Hongzhi Yin. Imgagn: Imbalanced network embedding via generative adversarial graph networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1390-1398, 2021.
[26] Jiawei Ren, Cunjun Yu, Xiao Ma, Haiyu Zhao, Shuai Yi, et al. Balanced meta-softmax for long- tailed visual recognition. Advances in neural information processing systems, 33:4175-4186. 2020.
[27] José A Sáez, Julián Luengo, Jerzy Stefanowski, and Francisco Herrera. Smote-ipf: Addressing the noisy and borderline examples problem in imbalanced classification by a re-sampling method with filtering. Information Sciences, 291:184-200 2015.
[28] Min Shi, Yufei Tang, Xingquan Zhu, David Wilson, and Jianxun Liu. Multi-class imbalanced graph convolutional network learning. In Proceedings of the Twenty-Ninth International Joint Conference Artificial Intelligence (IJCAI-20), 2020.

---

[29] Michael R Smith, Tony Martinez, and Christophe Giraud-Cariin An instance level analysis of data complexity. Machine learning, 95(2):225-25 256, 2014.
[30] Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raf- fel, Ekin Dogus Cubuk, Alexey Kurakin, and Chun-Liang Li. Fixmatch: Simplifying semi- supervised learning with consistency and confidence. Advances in neural information processing systems, 33:596-600 2020.
[31] Jaeyun Song, Joonhyung Park, and Eunho Yang. Tam: Topology-aware margin loss for class- imbalanced node classification. In International Conference Machine Learning, pages PMLR, 2022.
[32] Kaihua Tang, Jianqiang Huang, and Hanwang Zhang. Long-tailed classification by keeping the good and removing the bad momentum causal effect. Advances in Neural Information Processing Systems, 33:1513-1524, 2020.
[33] Yuchun Tang, Yan-Qing Zhang, Nitesh V Chawla, and Sven Krasser. Svms modeling for highly imbalanced classification. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), (9(1):281-22) 2008
[34] Junjiao Tian, Yen-Cheng Liu, Nathaniel Glaser, Yen-Chang Hsu, and Zsolt Kira. Posterior re-calibration for imbalanced datasets. Advances in Neural Information Processing Systems, 33:8101-8113, 2020.
[35] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10003 2017.
[36] Petar Veličković, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. 2018
[37] Jianfeng Wang, Thomas Lukasiewiez, Xiaolin Hu, Jianfei Cai, and Zhenghua Xu. Rsg: A simple but effective module for learning imbalanced datasets. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3784-3793, 2021.
[38] Tong Wang, Yousong Zhu, Chaoyang Zhao, Wei Zeng, Jinqiao Wang, and Ming Tang. Adaptive class suppression loss for long-tail object detection. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 3103-3112, 2021.
[39] Xudong Wang, Long Lian, Zhongqi Miao, Ziwei Liu, and Stella X Yu. Long-tailed recognition by routing diverse distribution-awee experts. arXiv preprint arXiv:2010.0180% 2020.
[40] Zheng Wang, Xiaojun Ye, Chaokun Wang, Jian Cui, and S Yu Philip. Network embedding with campletely-imbalaneeee labels. IEEE Transactions on Knowledge and Data Engineering, (3(11):333436477
2020.
[41] Qizhe Xie, Zihang Dai, Eduard Hovy, Thang Luong, and Quoe Le. Unsupervised data augmenta- tion for consistency training. Advances in neural information processing systems, 33:6256 6268, 2020.
[42] Ziyu Xu, Chen Dan, Justin Khim, and Pradeep Ravikumar. Class-weighted classification: Trade-off's and robust approaches. In International Conference Machine Learning, pages 10544-10554. PMLR, 2020.
[43] Liang Yan, Shengzhong Zhang, Bisheng Li, min zhou, and Zengfeng Huang. UNREAL: Unlabeled nodes retrieval and labeling for meavily-imbalante node classification, 2023.
[44] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi sumi-supervised learning with graph embeddings. In International conference on machine learning, pages 40) PMLR, 2016.
[45] Zitong Yang. Yaodong Yu, Chong You, Jacob Steinhardt, and Yi Ma. Rethinking varianee trade-off for generalization of neural networks. In International Conference on Machine Learning, pages 10767-10777. PMLR, 2020.
12

---

[46] Rex Ying, Ruining He. Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 974-983, 2018.
[47] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in neural information processing systems, 33:5812-5823, 2020.
[48] Bowen Zhang, Yidong Wang, Wenxin Hou, Hao Wu, Jindong Wang, Manabu Okumura, and Takahiro Shinozaki. Flexmatch: Boosting semi-supervised learning with curriculum pseudo labeling. Advances in Neural Information Processing Systems, 34: 8440-18419, 2021.
[49] Hengrui Zhang, Qitian Wu, Junchi Yan, David Wipf, and Philip S. Yu. From canonical correlation analysis to superviee graph neural networks. In Advances in Neural Information Processing Systems, 2021.
[50] Tianxiang Zhao, Xiang Zhang, and Suhang Wang. Graphsmote: Imbalanced node classification on graphs with graph neural networks. In Proceedings of the 14th ACM international conference on web search and data mining, pages 833-841, 2021.
[51] 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 Neural Information Processing Systems, 2022.
[52] Boyan Zhou, Quan Cui, Xiu-Shen Wei, and Zhao-Min Chen. Bbn: Bilateral-branch network with cumulative learning for long-tailed visual recognition. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9719-9728, 2020.
[53] Zhi-Hua Zhou and Xu- Ying Liu. Training cost-sensitive neural networks with methods ad- dressing the class imbalance problem. IEEE Transactions on knowledge and data engineering, 18(1):63-77, 2005.
[54] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. In International Conference Machine Learning Workshop Graph Representation Learning and Beyond, 2020.
[55] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In The Web Conference, 2021.
13

---

A Other related work
Imbalanced Learning in Traditional ML. Most real-world data is naturally imbalanced, pre- senting significant challenge in training fair models that are not biased towards majority classes. To address this problem, various approaches have been commonly utilized. Ensemble learning [7, 18, 52, 39, 20, 3] combines the outputs of multiple weak classifiers. Data re-sampling methods [5, 10, 29, 27, 14, 37] aim to adjust the label distribution in the training set by synthesizing or duplicat- ing samples from the minority class. Another approach tackles the imbalance issue by modifying the loss function, assigning larger weights to minority classes or adjusting the margins between different classes [53, 33, 4, 32, 42, 26, 38]. Post-hoc correction methods compensate for the imbalanced classes during the inference step, after completing the model training [14, 34, 21, 12]. Although these techniques have been extensively applied to i..dd data, extending them to graph strucc-r data poses non-trivial challenges.
Graph Contrastive Learning. Contrastive methods, which have proven effective for unsupervised learning in vision, have also been adapted for graph data. One notable approach is DGI [36]. which presents framework for unsupervised node-level representation learning that maximizes global mutual information. Other approaches, such as GRACE (54), GCA [55], and GraphCL. [47], utilize augmented graphs to optimize the similarity between positive node pairs and minimize negative pairs. CCA-SSG [49] introduces an efficient loss function based on canonical correlation analysis, eliminating the need for negative samples. Incorporating community information, gCooL [17] enhances node representations and downstream task performance. GGD [51] simplifies the mutual information loss function by directly discriminating between two of node samples, resulting in faster computation and lower memory usage. These contrastive methods exhibit potential for improving unsupervised learning on graph data, However, is important note that our model operates within the context of semi- superisseeeieed learning, which significantly differs from the mechanisms employed by these models.
14

---

B Proofs
B.1 Proofs of Theorem
Theorem Under the condition that Ei is constant, the variance
Σ Li
By (x)
reach its minimum when all equal.
n
Proof
The expression
EL E. T4 (=))))(a(a))) can be equivalently expressed as
Eis E. [b*(x)) (x)) As previously assumed, the E (x)))())) is the same for dif- ferent i, which implies that our goal is to demonstrate that Σ n. equal.
is minimized when all nę
Let m be Ei= Th. We wish to find the extremum of the sum of their reciprocals, which given by
S
(10)
n1
n2
The
Using the inequality of arithmetic and harmonic means, we have
Th
112
(11)
c
n2
no
with equality if and only if n n2
Ne.
Rearranging, get
6
S S
(12)
11 + 12 +
nr
with equality if and only mn n12
Ne.
Since = + 112 + + Tis we have
c² < S
(13)
m
with equality if and only if n1 n2 ne m. Therefore, when all the numbers are equal, the sum of their reciprocals is minimized and given by S e²
We can also use the method of Lagrange multipliers. Let f .., ae) 1 + be the function that we want to extremize. Then, the Lagrangian is:
C(n,, n2, M A) f(n,, n2. n.) M(n1 + + + m).
(14)
Taking the partial derivatives of L with respect to a, and X, we get:
ac 1
7 A
On; n
(15)
0C
+
n2
+ ne m.
0X
Setting these partial derivatives to zero, we get:
2
(16)
7i 112
T1g
m
Thus, when the numbers are equal, their reciprocal sum is minimized and is equal to Moreover, since S is continuously differentiable function of nı, n2, ne. this extremum is minimum. Therefore, we have shown that the reciprocal sum of numbers with a sum of m is minimized and e when the e numbers are equal.
equal to
15

---

B.2 Proofs of Lemma and More Details for Estimating the Expectation with Unlabeled Nodes (Section 3.2)
B.2.1 Proofs of Lemma 1
Lemma Under the above assumption for h' N ,'), C N (p' (. minimizing the
Ei Ey [Var(x)) is equivalent minimizing Equation 17:
h(z)*
1 (1i nb))
ΣEE k=ij=lii
(ut + tbb)T 1 (s) - (17)
N
22n;
V2n,
ZEG i=1
Proof Let e¹ denote h' u', which follows the distribution el N(0, A'). Similarly, we denote e'= C* p² and it follows that e N (0, n. AA)
We know
a
Var( Σ ED (1 (x)C²
ED [h' -E
(x))))))
Σ Es (1) + - h=²)))²)))
(18)
Σ Es [h*
1 -n (x)A'((x). Σ
n4
1=1
so we get
Eg [Va((>)]
E
1 h
(z)
(19)
n
Motivated by stochastic gradient descent, opt sample an e on each occasion and compute, as opposed to directly calculating the expectation Epcc.
At present, we remain uncertain about how to sample the noise term associated with the class center C, We put forth proposition to estimate the class center noise e utilizing the feature noise c. Under the supposition that when E Ck. the jth element of the feature f(v adheres to a Gaussian distribution:
é ~ N e¹ ~ (1.,
(20)
Consequently, multiplying the noise term et in Equation 20 by exhibits an identical distribution to
yields random variable that
n2
é' ~ N (
1 0,
^ーa Ml
(21)
Moreover, how might we compute e;? In practical scenarios, we merely possess the feature h. However, we are able to calculate the disparity between two features, hi and hi, originating from the same class é:
1 _
0, 1 - n4
(h)
h+))
(E: E2) ~
(22)
22n
V2n;
Incorporating this into Equation 19, the loss is expressed as:
2 (ri n₂))
h(x)T
(23)
N
22n;
BEG
1=1
16

---

B.2.2 More Details for Estimating the Expectation with Unlabeled Nodes (Section 3.2)
Lemma I suggests that Ei=1 Ex [Var(x)) can be estimated by sampling labeled node pairs ( h2) from the same class i. However, due to the scareity of data in the minority class, this can often be challenging. In Section 3.2, we address this issue by utilizing random data augmentation and defining nodes from different views as members the same class, enabling us to sample node pairs for Equation 3 and perform embedding subtraction.
However, as we mentioned, the pseudo node pairs lack information regarding their class membership. making it impossible to assign appropriate v2n, values for different in Equation 3. These coefficients play a crucial role in compensating for the minority class, making it imperative to reintroduce information about the class number when constructing variance regularization. Therefore, in the second step, replace h in Equation 3 with the class center C", as demonstrated in Equation 4. As C = μ + e' and the variance e* is proportional to L. using Equation to estimate Lemma 1 can provide similar compensatory effects for the minority class. We present the proof for the aforementioned propositions below.
n;
Proof Firstly, the Ei= Ex [Var(z)] can be decomposed as follows:
B. [Var[<)]
1 N
Σ
h(x) 1
(n
/2n,
ZEG
(1h + +x)
2'
(hi 112)
2
2mm
(1(TTT
(ci ()) + (e%)
22n, (ci t
V2Tg
2
(nt)T
(ci - k) + (5)))
TTu (c) - b/)
2N
VTu
(ci (xt)TT
(+)) (é) eb)
+ 2N
2N
n4
k=
Ti
T2
(T (ci -5) (2)) (á- e
(24) The above Equation can be decomposed into three parts, namely Tı, T2, and Tz. Notably, each of these parts is associated with weight J. This observation supports Theorem I and Lemma which suggest that the variance of model is highly dependent on the distribution of the dataset's 's sample size, and that the extent of sample imbalance can significantly increase the model's variance.
Note that e N(O, A'), el N (o.
n. (+). and J e' N (1)) So. if use the class center C to replace h in Equation then we can get the following expression,
17

---

-C
REG i=
(W)) - -60) (e)) -
(1))7(())))) - -6+)+ +
1
T
ck
1
et) of
VTa
vTa
(c -6+)+ +
_e)T c/
1
est {
1
Vmj
/nj
=
(25)
(c) - +
1
(Et
T/aj
(Jan) - =
1 -())
n
2
- (
-43)
N
Like the previous Equation 24, Equation 25 can be decomposed into three parts: L1, L2, and Lz. If we substitute the class center C* for h, we can observe that even though L1 is insensitive to class imbalance, variables L2 and L3. which respectively incorporate weights 1 and - can still provide n, the following support: when optimizing the variance of the model, more attention can be given to the variance introduced by the minority classes, which also provides an innovative perspective for understanding class imbalance on graphs.
18

---

C More Results
C.1 More results Under Traditional Semi-supervised Settings
In Table 3, we present the results of Re and other algorithms on Cora-Semi (p=10). The experi- mental results demonstrate that TAM has a significant gain effect on all models (BalancedSoftmax, Renode, GraphENS), while GraphENS achieved the best performance among all current baselines on various models. By comparing with GraphSMOTE, we can conclude that addressing the node classification imbalance issue should focus on the topological characteristics of the graph. Finally, and most importantly, ReVar achieved state-of-the-ee results under all basic models, which also verifies the superiority of our model in traditional imbalanced segmentation.
Table 3: Experimental results our method ReVar and other baselines on Cora-Semi. We report averaged balanced accuracy (bAce.,%) and Fi-score (%) with the standard errors over 5 repetitions on three representative GNN architectures. Highlighted are the top first and second. is the margin by which our method leads state-of-te of-the-art art method.
GCN
GAT
SAGE
Imbalance Ratio (p 10)
bAcc.
Fl
bAcc.
F1
bAce.
Vanilla
62.82
61.67
62.33
61.82 #
61.82
0.97
60.97
Re- Weight
65,36 115
64,97
66.87
66.62 1:13
63.94
63.82
PC Softmax
68.04 0.82
67.84 0.81
66.69 = 0.79
66.04 = 1.10
65.79 0.70
66.04 :: 0.92
GruphSMOTE
66.39 0.5
65.49 1 033
66.71 = 0:3
65.01 +: 1:21
61.65 0.34
60.97 1: 0.98
BalancedSoftmax
69.98
68.68 0.55
67.89
67.96 +
67.43
67.66
+ TAM
69.94
69.54 0:477
69.16
69.39 0:377
69.03
69,03 0:977
RenadE
67.105
6716
67.33 EnN
6800 1..1
66.34
The
"67.08 I 175
TAM
68.26
68.11
67,50
68.06
67.28 1.11
67.15
GraphENS
70.89 0.1
70,90 0.11
70.45 1:25
69.87 1.3
68.74 0.46
68.34 0.35
+ TAM
71.69 0.36
72.14 001
70.15 2.18
70.00 0:4.0
70.45 a: 0.24
70.40 1:075
ReVar
72.92 2:2
72.60 1:366
74.56 = n.6
74.61 1:096
73.32 2: k.
68.91 a: 3.33
1.2331.72%)
+ 0.4660649)
+ 4.116335%
4.61
2.87(407)
-..49
Table 4: Experimental results of our method ReVar and other baselines on Computers-Randont
We report averaged balanced accuracy (bAcc.,% %) and Fl-score (%) with the standard errors over repetitions on three representative GNN architectures. Highlighted are the top first and second. A the margin by which our method leads state-of-the-art method.
DatasetCComptter---anddnm
GCN
GAT
SAGE
Imbalance Ratio (p 25.50)
bAce.
bAcc.
bAcc.
Vanilla
78.43
77.14
71.35
69.60
65.30
64.77
Re- Weight
80.49 0.44
75.07 nas
71.95
0,00
70.67
0.51
66.50 :: 1.47
66.10 = 1.46
PC Softmax
81.34 0.55
75.17 0.5
70.56 = 1.46
67.26
1.4
69.73 + 0.53
67.03 0.
GraphSMOTE
80.50
73.79
71.98
67.98
72.69
68.73
BalancedSoftmax
81.39
74.54
72.09
68.38
73.80
69.74
+ -AM
81.64 0.48
75.59 083
74.00 0.77
70.72 0.50
73.77 + 1.26
71.03 0.60
Renöde
3[.64 0.34
76.87 m.3t
72.30
0034
71,40
0.77
70.94
1.50
770.04 ET
TAM
80.50
75.79
71.98
70.98
1:31
72.69
70.73
GraphENS
82,66 0.61
76.53
201
775.25
n35
71.49
0.5.
77.64
1: 0.50
72265
0.3
TAM
82.83 0.68
76.76
1766=09 039
75.81
0.72
72.62
0.57
78.98 4: 0.00
73.59
=: 0.55
ReVar
85,00 0.07
82.35 0.0
81.94 0:54
80.94 0:25
80.61 +: 0.11
77.49 =: 0.09
A
22217/2
5.48
6.1338.09)
8-..2(11449)
1.63:22069)
3.990:3300)
C.2 More results On Naturally Imbalanced Datasets
One of our major highlights testing our algorithms on naturally imbalanced datasets, which is more representative of real-world scenarios. This means that in semi-supervised setting, our training set and unlabeled data are both imbalanced, which poses significant challenge for oversampling methods. In Table 4, present the results of Var and all baselines Camputers-Randone
19

---

demonstrating that our model still achieves state-of-the- art performance. In contrast, oversampling methods such as GraphSMOTE perform poorly on this dataset due to overfitting limitations. We believe that our model's is ability to regularize variance from a bottom-up perspective contributes to its superior performance on naturally imbalanced graphs, while also demonstrating its powerful generalization capabilities.
20

---

D More Analysis
D.1 More Ablation Analysis for the Loss Function
Sup SupeIR
Sup+9R Sup+IReUR
Sup Sup+
Sip+VR SupeRR-VS
F1-score( (%)
-ccore
SAGE
GAT Model
GLN
SAGE
GCN
Model
(a) CiteSeer-Semi
(b) PubMed-Semi
Figure 4: More Ablation Analysis for the Loss Function.
Details of Experimental Setup. We conduct more experiments imbalance ratio 10 10) for the datasets CiteSeer and PubMed. For each GNN network, we add one loss regularization at a time, i.c. for GCN, gradually add LIR, LvR from the initial Csup. The architecture employed consisted of 2-layers graph neural network (GNN) with 128 hidden dimensions, using GCN [16], GAT [35], and GraphSAGE [9]. The models were trained for 2000 epochs.
experiments for each component in the loss function. As have seen, each component of the loss function can bring an improvement in the training effect. is worth noting that in most cases Lvn has larger effect boost than LIR. We believe that LVR plays more important role in the loss function.
Analysis. Figure 4 reports
D.2 More Experiments for Variance and Imbalance Ratio Correlation in Theorem 1
0.16
0.16
0.14
Varlance
0.10
Vañana
00012
Variance
0.12
8.10
0.10
0.00
0.08
0.04
0.06
10
10
10'
P
P
P
PubMed-GCN
(b) PubMed-GAT
(c) PubMed-SAGE
Figure 5: More experiments for variance and imbalance ratio correlation in Theorem
Details of Experimental Setup. In this experiment, the classifier not MIP, which means that the probability of node being classified into class depends on the distance of this node from the center of class i. We classify half of the classes as majority classes and the other half as minority classes. Initially, each class in majority classes and minority classes has 200 labeled nodes. To generate different imbalance scenarios (p), we reduce the number of labeled nodes in the minority class by and add to the number of labeled nodes in the majority class each time, so as keep the number of samples in the training set consistent and eliminate the effect of the sample size variance the training set. calculate the variance of the model under a certain imbalance ratio (p), we repeat 20 times to randomly select different but the same number of training sets, and train 2000 epochs for each fixed training set. The architecture we employed consisted of a 2-layers graph neural network (GNN) with 12 128 hidden dimensions, using GCN [16], GAT [35], and GraphSAGE [9].
21

---

Hypothesis testing. To test the correlation between the variance and imbalance ratio, we computed the Pearson correlation coefficient (p) between variance and imbalance ratio (log), as presented in the table below. The Pearson correlation coefficient, denoted as is prevalent metric for gauging linear correlations. This coefficient lies between (-1) and (1) ,and reflects both the magnitude and direction of the correlation between two variables. An (r) value greater than (0.5) indicates strong positive correlation. Furthermore, the p-value results from hypothesis test with the null hypothesis (Ho p 0) and the alternative hypothesis (H1 p + 0), where represents the population correlation coefficient.
Citeseer-GCN
Citeseer-GAT
Citeseer-SAGE
PubMed-GGCN
PubMed-GAT
PubMed-SAGE
0.751 3.203 10
0.786
0,642
0.694
0.760
0.747 5.634 10
p-value
1.516x10
5.107x10-00
2.233x 10
2.344x 10
Given that the Pearson correlation coefficient between variance and imbalance ratio exceeds (0.5), and the p-value below (0.01), we deduce that there is robust correlation between variance and imbalance ratio. This relationship is statistically significant at the (0.01) significance level.
Analysis. Figure 5 reveals an intriguing pattern, as the majority of data points closely align along regression curve exhibiting a positive slope. This observation provides substantial evidence that establishes a strong and direct linear relationship between the imbalance ratio (p) and the associated variance. Consequently, our findings provide compelling support for the hypothesis postulated in Theorem 1.
D.3 More Experiments for Hyperparameter Sensitivity Analysis of ReVar
F1-score(%
25
46
5461 D4
SACE ce
GAT
SACE
COI
025
525
5.5
6.15 125 2.53
05
25
A
A2
A1
A2
CiteSeer-Ai
(b) CiteSeer-Na
(c) Computers-Xi
(d) Computers- X2
Figure 6: More Experiments of Hyperparameter Sensitivity Analysis for Re
Details of Experimental Setup. We implemented experiments on the datasets, CiteSeer and Amazon-Come Crazzon-Computrs..... In this experiment, we evaluate the FI score when we fix one while the other changes. The architecture we employed consisted of 2-layer graph neural network (GNN) with 128 hidden dimensions, using GCN [16), GAT [35], and GraphSAGE [9]. The models were trained for 2000 epochs.
Analysis. In Figure 6, present the sensitivity analysis of Re to two weight hyperparameters (A1, X2) the loss function on the CiteSeer and Comazon-Computers. It is evident that ReVar different datasets. Specifically, the
exhibits varying degrees of sensitivity to hyperparameters model demonstrates lower sensitivity to and b on CiteSeer, while the opposite is observed on Amazon- Mrizzon-Compttess.. We postulate that the number of nodes (i.e., dataset size) may be crucial factor in this discrepancy. Nevertheless, the optimal range of hyperparameter selection appears to be relatively narrow, indicating that significant efforts not be required for model fine-tuning.
D.4 More Results of loss curve and F1 score
Details of Experimental Setup. We implemented experiments on three datasets PubMed, CiteSeer and Crazoo-Coompttess We compare our method ReVar and other vanilla models (only using cross-entropy and not using graph augmentation). The architecture employed for Var and
22

---

10.0
7.5
Our GAT
13
GAT
100.
Our GAT
SAGE
Our SAVE
Our coll
5.0
F1-score( %6
F1-score(%)
2.5
Vonduo our
Scedio DEN
LOSs
0.0
-2.5
-50
Varilia
Varili CAT
Vertii SCN
Vontil CON
Epoch
Epoch
Epoch
Epoch
(a) PubMed-Loss
(b) Computers-Loss
(c) PubMed-F1 Score
(d) Computers- score
Figure 7: More analysis of loss curve and Fl score.
vanilla model consisted of a 2-layer graph neural network (GNN) with 128 hidden dimensions, using GCN [16], GAT [35], and GraphSAGE [9]. The models were trained for 2000 epochs.
Analysis. We plot the loss curve and Fl score with epoch on the PubMed and Computers datasets. By analyzing the plotted loss curves, we observe that our model demonstrates notable advantages, including faster convergence of the loss curves and improved performance across multiple datasets. For the Fl score, our model consistently outperforms alternative approaches, showcasing its superior capability in effectively capturing the complex relationships within the data and making accurate predictions.
23

---

E Elaboration of the experimental setup
In this section, we present our approach for constructing imbalanced datasets, describe our evaluation protocol, and provide comprehensive details on our algorithm as well as the baseline methods utilized our study. To achieve this, we leverage sophisticated techniques and utilize advanced metrics to ensure the reliability and relevance of our results.
E.1 Construction for Imbalanced datasets
The detailed descriptions of the datasets shown in Table 5. The details of label distribution in the training set of the five imbalanced benchmark datasets are in Table 7, and the label distribution the full graph is provided in Table 7.
Table 5: Summary of the datasets used in this work.
Dataset
Nodes
Edges
Features
Classes
Cora
2,708
5,429
1,433
7
Citeseer
3,327
4,732
3,703
6
Pubmed
19,717
44,338
500
3
Amazon- Computerss
13.752
491,722
10
Couuthor-CS
18,335
163,788
6,805
15
Imbalanced datasets construction for Traditional Semi-supervised Settings. For each citation dataset, we adopt the "public" split and apply random undersampling technique make the class distribution imbalanced until the target imbalance ratio is achieved. Specifically, we convert the minority class nodes to unlabeled nodes in random manner. Regarding the co-purchased networks we conduct replicated experiments by randomly selecting nodes as the training in each trial. We create a random validation that contains 30 nodes each class, and the remaining nodes are used as the testing set.
Imbalanced datasets construction for Naturally Imbalanced Datasets. For Computers- Randut and CS- 2S-Random, we constructed a training set with equal proportions based on the label distribution of The label distributions for the training sets of Computers-
the complete graph Jamazon-Compurt Random and CS-Random are presented in Table 7. To achieve this, we employed a stratified sampling approach that ensured an unbiased representation of all labels in the training set.
Table 6: Label distributions in the training sets
45/04
0542% 53
3085 01
237 m
11.34% 26
12%
138% 12)
11859 12n
126 01
2215
1.8% m
830% (1) 3.0% 11.05
125 2305 4505
Table 7: Label distributions on the whole graphs
Dataset
C,
C.
C;
Co
C11
Cia
Csa
Cora (p Fe 1.54)
351
217
418
818
426
298
180
CiteSeer 2.68)
264
590
668
701
696
508
PubMed ts 1.91)
4103
7739
Mmazznn-Compuce (p m 17.73)
436
2142
1414
542
5138
308
487
818
2156
291
Comuthor-CS ss 35.05)
708
462
2050
429
1394
2193
371
924
775
118
1444
2033
420
4136
876
E.2 Architecture of GNNs
We conducted evaluations using three classic GNN architectures, namely GCN [16], GAT [35]. and GraphSAGE [9]. The GNN models were constructed with different numbers of layers, namely -= 1, 2. 3. To enhance the learning process, each GNN layer was accompanied by BatchNorm layer with momentum of 0.99, followed by PRelu activation function [11]. For the GAT architecture, we employed multi-head attention with 8 heads. We search for the best model on the validation set. The available choices for the hidden unit sizes were 64, 128, and 256.
24

---

E.3 Evaluation Protocol
We utilized the Adam optimizer [15] with an initial learning rate 0.01 0.005. To manage the learning rate, we employed scheduler based on the approach outlined in [31], which reduced the learning rate by half when there was no decrease in validation loss for 100 consecutive epochs. Weight decay with a rate of 0.0005 was applied to all learnable parameters in the model. In the initial training iteration, we trained the model for 200 epochs using the original training set for Cora, CiteSeer, PubMed, or Amazon- Compoo-er. However, for Flickr, the training was extended to 2000 epochs in the first iteration. Subsequently, the remaining iterations, we trained the models for 2000 epochs using the aforementioned optimizer and scheduler. The best models were selected based on validation accuracy, and we employed early stopping with patience of 300 epochs.
E,4 Technical Details of ReVar
For all datasets Cora-Semi, CiteSeer-Semi, PubMed-Semi, Computers-Semt Computers-Randon and CS-Random, the learning rate ?) chosen from {0.0001, 0.0005, 0.001, 0.005, 0.01, 0.1). The temperature hyperparameter r is chosen from {0.05, 0.08, 0.13, 0. 0.16. 0.21, 0.23, 0.26). The threshold chosen from (0.6, 0.63, 0.66, 0.7, 0.8, 0.83, 0.9, 0.93, 0.96, 0.99). The factor X of LVR is chosen from {0.25, 0.35, 0.5, 0.85, 1.5, 2, 2.15, 2.65,33 The factor X2 of LIR is cho- sen from {0.35, 0.5, 1, 1.25, 1.5, 2.85, 3}. The factors of mask node properties and edges in G are chosen from {0.4, 0.45, 0.5, 0.6, 0.65, 0.7} and {0.4, 0.45, 0.5, 0.55, 0.6, 0.65, 0.7]. The fac- tors of mask node properties and edges in G' are chosen from 0,2.0..5,022,00333 0.4, 0.45] and {0.1, 0.15, 0.2, 0.3, 0.35, 0.4, 0.45).
E.5 Technical Details of Baselines
For the GraphSMOTE method [50], we employed the branched algorithms whose edge predictions are discrete-valuce valued, which have achieved superior performance over other variants in most experiments. Regarding the ReNode method [6], we search hyperparameters within the lower bound of cosine annealing, Wiiin 0.25, 0.5, 0.75, and the upper bound range, Wmax 1.25, 1.5, 1.75, suggested in [6]. The PageRank teleport probability was fixed at a = 0.15, which is the default setting in the released codes. As for TAM [31], we performed hyperparameter search for the coefficient of the ACM term, a E 1.25, 1.5, 1.75, the coefficient of the ADM term, 3 E 0. 0.125, 0.25, 0.5, and the minimum temperature of the class-wise temperature, Φ 0.8, 1.2, following the approach described in [31]. The sensitivity to the imbalance ratio of the class-wise temperature, 8, was fixed at 0.4 for all the main experiments. Additionally, consistent with [31], we implemented warmup phase for iterations, as we utilized model predictions for unlabeled nodes.
E.6 Configuration
All the algorithms and models are implemented in Python and PyTorch Geometric. Experiments conducted on a server with an NVIDIA 3090 GPU (24 GB memory) and an Intel(R) Xeon(R) Silver 4210R CPU @ 2.40GHz.
25

---

Algorithm
Algorithm 1 ReVar
Input: Imbalanced Graph G (V, E, VL., feature matrix X. adjacency matrix A, unlabeled =u= = - VL. label matrix Y. feature matrix of labeled nodes and unlabeled nodes X1, and Xu. the number of classes k, the threshold for determining whether node has confident prediction, temperature hyperparameter т, GNN model fa, the classifier ha, learning rate The total number T of epochs for model training. The sim(-.)) computes the cosine similarity between two vectors, CE represents the cross-entropy loss function, and T(-) is an indicator function.
Vu
1: for 0, d do
2:
Generate two differently augmented views G = (A and G" = (A, X') from original graph
G.
3:
O, + (A(, OF + Ja(A,Xx))
O fo X2). O - fo(A',
4:
5:
% Component I: Supervised Loss
6:
Sou + ( (Öz), Y) + CC((ho Y) % Component 2: intra-Class Aggregation Regularization
7:
8:
LIR
No sim O O,) No ΣN
(IN4 Naul
No
sim L Ö7)
EN 5-1.54 sim ÓO, O,) (E.))aame
9:
% Component Varfance-constrainee Optimization with Adaptive Regularization
10:
for 1, ..... A do
11:
Compute the class centers Č, and C': for class end for
12:
13:
> Obtain the Label Probability for Each Node
14:
for 1,2, V do
C T
15:
p. - Softmax Ó C
P - Softmax 0 (Č C'
16:
17:
end for
18:
> Eliminate Nodes with Low Confidence.
V conf + {i I [max (p() > v) 1, vi Vv}
20: > Replace Labeled Node Prediction
for ........ VL do
22:
P Y:
end for
24: LVR + Veout EiEV EvEE CE P.) + IVI Evev. CE P:)
25:
Ciraining f- Loup XLLVR + dgLIR
26: 06 17 (VV (raiining)
27:
end for
26

---

G
Notations
Table 8: Notation table.
Indices
n
The number of nodes, n |V]. The node feature dimension. The number of different classes.
D
The dimension of the embedding space, the dimension of the last layer of GNNs.
Parameters
G
An undirected and unweighted graph. The node set of G. The edge set of G. The feature matrix G. E Rnx/, The set of labeled nodes of G.
V
X
VI
A
The adjacency matrix G, A E {0, 1)mxn. The set of 1-hop neighbors for node The set of unlabeled nodes, Vu == V VL. The labeled set for class i. Imbalance ratio of dataset, = max; C2 min; C₁|-
N(E)
VU
C
G
view from the original graph G G A, X
G
Another view from the original graph G, G' A x
h
Output of GNN network, h (A,
S
The probability distribution reference matrix, S [C1 Czi The collection of class centers, C. := (C1; Cz; Ct). The probability distribution for node The one-hot label vector for node i. Supervised loss.
C
Sap
Lin
Intra-class aggregation regularization.
Ln
Variance-constrainee optimization with adaptive regularization. The sum of all losses.
Cival
sonf
The set of nodes with confident predictions.
The weight for LVR.
A2
The weight for LIR-
The threshold for determining whether node has confident prediction. The temperature hyperparameter.
T
The size threshold of nodes being added in each class per round. Learning rate of GNN model.
Functions
(-))
The indicater function.
sim (+)
The function that computes the cosine similarity between two vectors. The cross-entropy function.
CE
fo
GNN model.
27


Reviews:
[{"review_id": "HqWmPKA0ZD", "reviewer": "Reviewer_bhDb", "summary": "This paper proposes a theory that relates data imbalance to model variance and designs a method to mitigate the bias of class imbalance. \nFor the theory, this paper finds that the variance of each class is proportional to the invert of the number of samples in that class. \nFor the method, this paper uses a regularization term to approximate the model variance and construct a varied training distribution with graph augmentation. The regularization term is added to the original loss function.\n Results on public-split datasets and naturally imbalanced datasets verify the proposal.", "questions": "1. Why can you assume that node embeddings follow a multivariate normal distribution?\n\n2. Many elements of Figure 2 need descriptions. E.g.,  What do yellow and blue circles mean?", "limitations": "This paper does not discuss limitations. But I think the novelty and unique contribution is limited.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "This paper first connects the model variance and class imbalance in graph learning.", "weaknesses": "1. L_IR objective is more closely related to variance than contrastive learning. It would help to clarify the difference between your work and contrastive graph learning.\n\n2. This paper does not discuss previous work on variance and imbalance in traditional imbalanced learning. Since the variance calculated in this paper does not use graph-specific settings, it is not unique to graph learning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for the comments. We appreciate your comments that our novelty that first connects the model variance and class imbalance problem on the graph. We address all your concerns below:\n***\n**Q1**: $L_{IR}$  objective is more closely related to variance than contrastive learning. It would help to clarify the difference between your work and contrastive graph learning. \n\n**Answer1**: \n- The main focus of our study is to utilize graph augmentation to formulate the loss function $L_{VR}$ for approximating the model's variance. It's worth clarifying that **$L_{IR}$ is not directly linked to the model's variance**. We hope this provides a clearer understanding.\n- We acknowledge that there might have been confusion caused by a misleading sentence in Sec 4.2, where we mentioned, \"In this section, we propose an extension to the concept of graph contrastive learning that emphasizes the invariance of node representations in semi-supervised scenarios.\" We understand that this statement could imply a direct relation between $L_{IR}$ and variance, which was not our intention. **In the revision, we will carefully rephrase this section to clarify our intentions** and avoid any potential misinterpretations.\n- For the term $L_{IR}$, our experiments revealed that the inclusion of an additional loss term, $L_{IR}$, **is beneficial in ensuring that the graph augmentation does not negatively influence GNN feature extraction**. This concept is inspired by graph contrastive learning, which we have tailored to better fit our specific setting.\n\n***\n**Q2**: This paper does not discuss previous work on variance and imbalance in traditional imbalanced learning. Since the variance calculated in this paper does not use graph-specific settings, it is not unique to graph learning.\n\n**Answer2**: \n- First, we truly appreciate the reviewer's attention and feedback about this concern. After an in-depth literature review, we found that our study is among **the first to concentrate on optimizing the model's variance, both in graph learning and traditional imbalanced learning**. We consider this a significant contribution and have approached the challenge from a thoughtful theoretical perspective. As mentioned in Section 6, our future directions include extending RVGNN and its foundational theories to the realms of computer vision and natural language processing. Considering this focus, we feel that an extensive discussion about the combination of variance and imbalance in traditional imbalanced learning might not be central to our current study. Once again, thank you for your invaluable insights and suggestions.\n- Regarding your second concern, we would like to clarify that in our work, we indeed incorporate graph-specific settings when approximating the variance of the model.\n  - In optimizing the approximate variance, graph data augmentation(GDA) is crucial as it serves to emulate diverse training sets. In this work, it's worth noting that GDA is distinct from traditional data augmentation. Here, **GDA acts as a form of dataset augmentation**.  It not only perturbs the features of individual nodes but also significantly modifies the graph dataset by cropping or adding edges. However, we recognize that **applying our framework to traditional settings may not be direct**.\n  - As detailed in our paper, we believe that **addressing the graph imbalance problem by optimizing the model's variance offers a more meaningful approach compared to traditional imbalanced learning domains**. Unlike conventional imbalanced learning, devising GNN imbalanced learning methods for graph-structured data presents distinct challenges. Graph-structured data often necessitate careful consideration of the data’s topology and surroundings. Traditional strategies such as oversampling and loss function engineering often fall short in achieving satisfactory results. More specifically, the modeling approach for data personalization shows marked deficiencies in scalability and generalization capability. Therefore, a more fundamental and theoretical viewpoint is urgently needed to address the imbalance node classification issue. In this work, we introduce a novel perspective to comprehend graph imbalance through the prism of Bias-Variance Decomposition. This forms the motivation for our work.\n\n***\n**Q3**: The node embeddings follow a multivariate normal distribution.\n\n**Answer3**: \n\nWe acknowledge and appreciate your observation regarding our assumption about the embeddings following a multivariate normal distribution. **Our rationale is inspired by the Central Limit Theorem (CLT)**. The generation of these embeddings of graph involves aggregating information from several random processes—such as random walks and aggregations from neighboring nodes[1,2]. Each of these can be viewed as a distinct random variable. As we aggregate numerous such variables, the CLT suggests that their aggregate effect tends to approach a normal distribution, given they possess finite expectations and variances.\n\n**We recognize this as an approximation and aimed to streamline our theoretical framework**. In practice, this assumption has proven to be a satisfactory fit. Nonetheless, we are cognizant of its limitations and value your feedback on this matter.\n\n[1] Cavallari, Sandro, et al. \"Learning community embedding with community detection and node embedding on graphs.\" Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. 2017.\n\n[2] Xu, Mengjia. \"Understanding graph embedding methods and their applications.\" SIAM Review 63.4 (2021): 825-853.\n***\n**Q4**: Many elements of Figure 2 need descriptions. E.g., What do yellow and blue circles mean??\n\n**Answer4**: \n\nWe have revised Figure 2 to provide more detail. In this figure, additional elements have been incorporated that were not previously marked  (yellow and blue represent different classes).  **We have placed the modified Figure 2 to in the PDF file that has been uploaded.**\n\n"}, {"review_id": "r0hyLCqqIZ", "reviewer": "Reviewer_vtyV", "summary": "This paper introduces a new approach to address the issue of class imbalance in graph neural networks (GNNs) for learning on graph-structured data. It also provides a novel theoretical perspective for addressing the problem of imbalanced node classification in GNNs.", "questions": "No more questions.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1 The article is well written and easy to understand.\n\n3 The authors prove their claim by theoretical derivation.\n\n4 The experimental results further corroborate the authors' view.\n", "weaknesses": "1 The use of L to represent the set of labeled nodes is still relatively rare in the definition of graphs, and the authors are advised to describe the definition involved further in the opening paragraph of the method.\n\n2 Is the authors considering restructuring the article? Putting the theoretical derivation before the introduction of the method may not give the reader a good reading experience.\n\n3 I am curious about this one: the authors point out that the full graph noise distribution is taken into account when sampling the graph in order to sample the training set that has approximate variance. However, if one considers graph learning in an open world, then the noise from the added data might be quite different from the original graph data.\n\n4 In Table 1, the authors can consider further reporting the percentage of performance improvement compared to SOTA.\n\n5 In Fig 3(a), it seems that the performance improvement from VR loss is not significant. Are you considering the Sup+VR combination? Also, can you further diet why VR loss gives a smaller boost to GAT?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for the comments. We appreciate your comments that the theoretical and experimental superiority is strong for our model. We address all your concerns below:\n***\n**Q1**: The use of L to represent the set of labeled nodes is still relatively rare in the definition of graphs, and the authors are advised to describe the definition involved further in the opening paragraph of the method.\n\n**Answer1**: \n\nWe have modified our notation to **use $V_{L}$ and $V_{U}$**  to represent the sets of labeled and unlabeled nodes, respectively, replacing the previous $L$ and $U$. This revised notation aligns better with common conventions.\n***\n**Q2**: Is the authors considering restructuring the article? Putting the theoretical derivation before the introduction of the method may not give the reader a good reading experience.\n\n**Answer2**: \n\nWe sincerely appreciate your valuable feedback concerning the structure of our paper. We will **thoughtfully consider your suggestions and discuss potential refinements to the article's organization** with our co-authors. Our goal is to enhance the clarity and readability for the audience.\n***\n**Q3**: I am curious about this one: the authors point out that the full graph noise distribution is taken into account when sampling the graph in order to sample the training set that has an approximate variance. However, if one considers graph learning in an open world, then the noise from the added data might be quite different from the original graph data.\n\n**Answer3**:  \n\nThank you for raising this intriguing scenario. Our original focus **revolved around semi-supervised learning within the \"close-world\" setting, where all labeled and unlabeled nodes are accessible during the training stage**. Therefore, we would like to clarify that the concern you've mentioned won't be applicable to our current paper.\nWe do recognize that in the \"open-world\" setting, the regularization term introduced in our paper **may not be able to handle the variance of unseen data effectively**. However, it still serves as a valuable regularization term for addressing the imbalance present within the known dataset. We appreciate your acknowledgment of the potential value in estimating variance within the \"open-world\" setting, and we agree that it could pave the way for generalizing our algorithm.\n***\n**Q4**: In Table 1, the authors can consider further reporting the percentage of performance improvement compared to SOTA.\n\n**Answer4**:  \n\nWe agree that including the percentage of performance improvement compared to the state-of-the-art (SOTA) would provide additional clarity. **We have updated the tables** to reflect this comparison and believe it enhances the understanding of our method's effectiveness.\n\n***\n**Q5**: In Fig 3(a), it seems that the performance improvement from VR loss is not significant. Are you considering the Sup+VR combination? Also, can you further diet why VR loss gives a smaller boost to GAT?\n\n**Answer5**:  \n\n1. Thank you for pointing that out. It's true that the notable performance enhancement from the VR loss isn't as pronounced in the CiteSeer-GAT instance. **However, in a majority of the other cases, the role of $L_{VR}$ is quite significant**.  We would like to **kindly draw your attention to Appendix D of the original submission**, where we have provided more detailed ablation experiments across additional datasets like PubMed and Computers, and using various model scenarios such as GCN, GAT, and SAGE. We hope this addresses your concerns.\n\n2. Based on your insightful feedback, we **rigorously incorporated the combination of Sup+$L_{VR}$ into our ablation study as follows**. The results affirm a fundamental insight of our work: optimizing the model's variance proves to be an effective method to address the long-tail problem.\n\n|                  | **Dataset**          | **CiteSeer-Semi**    | **PubMed-Semi**      | **Computers-Semi**    |\n|:-----------------|:--------------------:|:--------------------:|:--------------------:|:--------------------:|\n|                  |                      | F1-Score(%)          | F1-Score(%)          | F1-Score(%)           |\n|------------------|----------------------|----------------------|----------------------|----------------------|\n| **SAGE**         | Sup                  | 44.43                | 64.80                | 77.16                 |\n|                  | Sup+IR               | 60.92                | 68.35                | 78.62                 |\n|                  | Sup+VR               | 62.33                | 73.68                | 79.54                 |\n|                  | Sup+IR+VR            | 64.91                | 76.44                | 80.40                 |\n|------------------|----------------------|----------------------|----------------------|----------------------|\n| **GAT**          | Sup                  | 48.08                | 65.91                | 74.04                 |\n|                  | Sup+IR               | 65.35                | 67.04                | 74.35                 |\n|                  | Sup+VR               | 65.67                | 72.87                | 77.65                 |\n|                  | Sup+IR+VR            | 65.70                | 74.46                | 78.12                 |\n|------------------|----------------------|----------------------|----------------------|----------------------|\n| **GCN**          | Sup                  | 43.98                | 62.28                | 73.54                 |\n|                  | Sup+IR               | 53.94                | 66.16                | 76.32                 |\n|                  | Sup+VR               | 57.43                | 72.34                | 77.09                 |\n|                  | Sup+IR+VR            | 59.73                | 74.48                | 78.49                 |\n|------------------|----------------------|----------------------|----------------------|----------------------|\n\n"}, {"review_id": "Yb2C3fZEP2", "reviewer": "Reviewer_j7Kz", "summary": "This paper focuses on semi-supervised imbalanced node\nclassification tasks. Specifically, the authors first establish a theoretical result that connects the imbalance ratio with the model variance and then propose a new regularization term related to the variance based on the graph augmentation technique. Experimental results show the effectiveness of the proposal.", "questions": "1. How to determine the hyper-parameters in different datasets?\n2. How to demonstrate the superiority of algorithm performance is related to theoretical results?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors give theoretical results that connect the imbalance ratio to the model variance. The results are insightful.\n2. The experimental results show the proposal can achieve the SOTA performance on various class-imbalanced datasets.", "weaknesses": "1. The theoretical results rely on strong assumptions, which may be difficult to satisfy in real-world tasks.\n2.  From Figure 3, it looks like the performance is highly influenced by the hyper-parameters. So how to determine the hyper-parameter should be discussed in the paper.\n3. Moreover, I doubt that the performance of the proposal is not related to the theoretical results, it may rely on graph augmentation. Thus, more ablation studies should be conducted.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for the comments. We appreciate your comments that the theoretical and experimental superiority is strong for our work. We address all your concerns below:\n***\n**Q1**: The theoretical results rely on strong assumptions, which may be difficult to satisfy in real-world tasks.\n\n**Answer1**: \n\nWe acknowledge and appreciate your observation regarding our assumption about the embeddings following a multivariate normal distribution to approximate the variance. **Our rationale is inspired by the Central Limit Theorem (CLT)**. The generation of these embeddings of GNN involves aggregating information from several random processes—such as random walks and aggregations from neighboring nodes[1,2]. Each of these can be viewed as a distinct random variable. As we aggregate numerous such variables, the CLT suggests that their aggregate effect tends to approach a normal distribution, given they possess finite expectations and variances.\n\n**We recognize this as an approximation and aimed to streamline our theoretical framework**. In practice, this assumption has proven to be a satisfactory fit. Nonetheless, we are cognizant of its limitations and value your feedback on this matter.\n\n\n[1] Cavallari, Sandro, et al. \"Learning community embedding with community detection and node embedding on graphs.\" Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. 2017.\n\n[2] Xu, Mengjia. \"Understanding graph embedding methods and their applications.\" SIAM Review 63.4 (2021): 825-853.\n\n***\n**Q2**: From Figure 3, it looks like the performance is highly influenced by the hyper-parameters. So how to determine the hyper-parameter should be discussed in the paper.\n\n**Answer2**: \n\n- We would like to **kindly draw your attention to Appendix E.4 of the original submission**, where we have provided detailed range for our hyperparameter search.\n\n- In determining the hyperparameters for different datasets, we follow a rigorous and systematic approach rather than relying on heuristic methods. **Our methodology involves conducting a hyperparameter sweep in the conventional manner**.\n\n  To begin, we partition the dataset into training, validation, and test sets. During the hyperparameter sweep, we carefully configure the range for each hyperparameter and employ some strategies to generate sets of hyperparameters. **We then search for the set of hyperparameters that yields the best performance on the validation set, using F1 score as key evaluation metrics**. In our experiments, we observed that **the hyperparameter selection process for our model is exceptionally robust.**\n\n  To facilitate this process, we leverage the wandb platform (wandb.ai) to organize our experiments and **utilize the built-in Bayes strategy within the hyperparameter sweep**. This allows for efficient exploration of the hyperparameter space, enabling us to identify the optimal combination of hyperparameters for each dataset.\n\n***\n**Q3**: Moreover, I doubt that the performance of the proposal is not related to the theoretical results, it may rely on graph augmentation. Thus, more ablation studies should be conducted.\n\n**Answer3**:  \n- The core idea of our work is to optimize the variance of the model. As the key technology we use to **approximate the variance, graph data augmentation plays a very important role**. In fact, the **theoretical result derivation also does depend on graph data augmentation**.\n\n- We are not sure that we understand your point. We think that your concern may be about that the use of contrastive loss ($L_{IR}$) together with data augmentation plays a key role. Through **the following detailed ablation analysis**, we clearly show that $L_{VR}$  plays the most important role.\n\n|                  | **Dataset**          | **CiteSeer-Semi**    | **PubMed-Semi**      | **Computers-Semi**    |\n|:-----------------|:--------------------:|:--------------------:|:--------------------:|:--------------------:|\n|                  |                      | F1-Score(%)          | F1-Score(%)          | F1-Score(%)           |\n|------------------|----------------------|----------------------|----------------------|----------------------|\n| **SAGE**         | Sup                  | 44.43                | 64.80                | 77.16                 |\n|                  | Sup+IR               | 60.92                | 68.35                | 78.62                 |\n|                  | Sup+VR               | 62.33                | 73.68                | 79.54                 |\n|                  | Sup+IR+VR            | 64.91                | 76.44                | 80.40                 |\n|------------------|----------------------|----------------------|----------------------|----------------------|\n| **GAT**          | Sup                  | 48.08                | 65.91                | 74.04                 |\n|                  | Sup+IR               | 65.35                | 67.04                | 74.35                 |\n|                  | Sup+VR               | 65.67                | 72.87                | 77.65                 |\n|                  | Sup+IR+VR            | 65.70                | 74.46                | 78.12                 |\n|------------------|----------------------|----------------------|----------------------|----------------------|\n| **GCN**          | Sup                  | 43.98                | 62.28                | 73.54                 |\n|                  | Sup+IR               | 53.94                | 66.16                | 76.32                 |\n|                  | Sup+VR               | 57.43                | 72.34                | 77.09                 |\n|                  | Sup+IR+VR            | 59.73                | 74.48                | 78.49                 |\n|------------------|----------------------|----------------------|----------------------|----------------------|\n\n\n"}, {"review_id": "XNej30wH1z", "reviewer": "Reviewer_zTQi", "summary": "This paper is majoring on the imbalance problem in graph node classification. The authors confirmed the relationship between model variance and the degree of dataset imbalance by adopting the Bias-Variance Decomposition. Furthermore, they diverted a regularization term for approximating the variance of the model from the above theoretical analysis.", "questions": "1. Why do the authors assume node embeddings follow the multivariate normal distribution?\n2. Could the authors provide the significance of the results in Fig1 (e.g., using hypothesis testing)?\n", "limitations": "The author could improve their manuscript by solving the below points and typos:\n- line 25-27: sentence should be shortened.\n- line 76: no definition for $N$, $F$ and $D$.\n- Section 3.1: Is there a lack of citations of Bias-variance Decomposition?\n- The term between Eq(2) and line 111, line 114 is different.\n- line 140: \"condition on\" should be replaced by \"conditioning on\".\n- line 208: indicator function is often denoted as $\\\\mathbf{1}_{ \\\\{ \\\\cdots \\\\} }$.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper discovers the relation between imbalance and variance, estimates the variance with graph argumentation, and solves the imbalance problem by adopting two proposed regularization terms, which is an important problem in node classification.\nThe regularization term is theoretically derived from the Bias-variance Decomposition, and the author, for the first time, fits this theory into the field of imbalance by making two weak assumptions, which is a good contribution to this field.", "weaknesses": "- Overall, this paper contains many typos and abuse of the notation that may make the reader uncomfortable. I list those points in the limitations.\n- In this work, the authors make a strong assumption that all embeddings follow the multivariate normal distribution with the same sample variance ($h(x)^T\\Lambda^ih(x)$ in the paper) between each class. And the authors use this assumption to derive the core relation between variance and imbalance, then the regularization term. \nHowever, this assumption is strongly related to the quality of the extracted embeddings. \nOne important guarantee for this assumption is a well-trained feature extractor with a clear boundary between each class. \nHowever, at the initial stage, the model is not well-trained, meaning that a large variance of $h(x)^T\\Lambda^ih(x)$ in each class. \nIt is unclear how this will affect the power of regularization though the overall results look good, and the authors did not make a discussion of the above problem in the paper. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for the comments. We appreciate your comments that the theoretical and experimental contribution of RVGNN is strong for tackling imbalance problems. We address all your concerns below:\n***\n**Q1**: This paper contains many typos and abuse of the notation that may make the reader uncomfortable. \n\n**Answer1**: \n\nThanks for highlighting the concerns related to typos and notation inconsistencies. We have **taken every point you listed into consideration. We have thoroughly revised the paper, making sure to correct all the typos and standardize the notation throughout**. Also based on this, we have **updated the notation table (Appendix G)** of the full text we compiled earlier to facilitate the reading of the article. We believe these changes have enhanced the readability and clarity of the manuscript. **Details are as follows:**\n\n- For the line 25-27 which sentence should be shortened, we modified it to: \"Graph-structured data often requires consideration of the data's topology and environment, and empirical evidence indicates that topological asymmetries can also affect the performance of models.\"\n***\n- For the line 76 which is no definition for N, F, D, we modified it to: \"N, F, and D are the dimensions of features and models, and they have the same meaning as n, f, and d of Preliminaries. We unify them.\"\n***\n- For Section 3.1 which is a lack of citations of Bias-variance Decomposition, we have cited some of the most relevant papers[1,2,3,4].\n\n  [1] Belkin, Mikhail, et al. \"Reconciling modern machine-learning practice and the classical bias–variance trade-off.\" Proceedings of the National Academy of Sciences 116.32 (2019): 15849-15854\n\n  [2] Kohavi, Ron, and David H. Wolpert. \"Bias plus variance decomposition for zero-one loss functions.\" ICML. Vol. 96. 1996.\n\n  [3] Von Luxburg, Ulrike, and Bernhard Schölkopf. \"Statistical learning theory: Models, concepts, and results.\" Handbook of the History of Logic. Vol. 10. North-Holland, 2011. 651-706.\n\n  [4] Neal, Brady. \"On the bias-variance tradeoff: Textbooks need an update.\" arXiv preprint arXiv:1912.08286 (2019).\n***\n- For the term between Eq(2) and line 111, line 114 is different, I guess you are confused about the definition of $x_{i}$ in line 111, for a better understanding for the readers, we modified the sentence as \" We make two assumptions in our approach. Firstly, we assume that the node embeddings $h^i$  of node $x^i$ extracted by a graph neural network for nodes belonging to class $i$ follow a multivariate normal distribution $h^{i} \\sim N(\\mu^{i}, \\Lambda^{i})$ ''. For $h_{n_{i}}^{i}$, it means the embedings of the $n_{i}$th node belong to $i$ class. We know that this notation can also cause some confusion, and we have carefully corrected it in the paper.\n***\n- For the line 140 where \"condition on\" should be replaced by \"conditioning on\", we have corrected it.\n***\n- For the line 208 that indicator function is often denoted as $\\boldsymbol{1}_{\\{...\\}}$, we have followed your idea and have corrected it.\n***\nPlease let us know if there are any other aspects that need further attention.\n***\n**Q2**: The strong assumption that all embeddings follow the multivariate normal distribution with the same sample variance $(h(x)^{T}\\Lambda^{i}h(x))$ in the paper) between each class. And the authors use this assumption to derive the core relation between variance and imbalance, then the regularization term.\n\n**Answer2**: \n\nWe appreciate the reviewer's feedback. Our work indeed assumes, for illustrative purposes, that different classes share the same $\\Lambda^i$ when demonstrating the relationship between variance and imbalance. However, it is vital to clarify that our regularization term is not contingent on this assumption. By employing graph augmentation, we generate pseudo-node pairs belonging to an identical class, subsequently reducing the feature discrepancy within these pairs to diminish the class-specific variance. It's worth noting that this variance approximation remains unaffected by the discrepancy of different $\\Lambda^i$ values. The optimization is conducted concurrently with the classification training. As you astutely pointed out, by the conclusion of the training phase, the relationship between variance and dataset imbalance is evident. Given that our algorithm consistently yields a model with reduced variance, we confidently assert that the resultant model exhibits robustness in imbalanced scenarios.\n***\n**Q3**: Could the authors provide the significance of the results in Fig1 (e.g., using hypothesis testing)?\n\n**Answer3**: \n\nThank you for your constructive suggestions. **We computed the Pearson correlation coefficient between variance and imbalance ratio (log), as presented in the table below**. The Pearson correlation coefficient, denoted as $r$, is a prevalent metric for gauging linear correlations. This coefficient lies between $-1$ and $1$ and reflects both the magnitude and direction of the correlation between two variables. An $r$ value greater than $0.5$ indicates a strong positive correlation. Furthermore, the p-value results from a hypothesis test with the null hypothesis $H_{0}: \\rho = 0$ and the alternative hypothesis $H_{a}: \\rho \\neq 0$, where $\\rho$ represents the population correlation coefficient.\n\n|            | Citeseer-GCN | Citeseer-GAT | Citeseer-SAGE | PubMed-GCN | PubMed-GAT | PubMed-SAGE |\n|------------|--------------|--------------|---------------|------------|------------|-------------|\n| **$r$**    | 0.751        | 0.786        | 0.642         | 0.694      | 0.760      | 0.747       |\n| **P-value**| 3.203e-14    | 1.516e-14    | 5.107e-07     | 2.233e-09  | 2.344e-14  | 5.634e-13   |\n\n**Given that the Pearson correlation coefficient between variance and imbalance ratio exceeds $0.5$, and the p-value is below $0.01$, we deduce that there is a robust correlation between variance and imbalance ratio. This relationship is statistically significant at the $0.01$ significance level.**"}, {"review_id": "gtPox8yNJk", "reviewer": "Reviewer_8yVE", "summary": "The paper studies imbalanced node classification problem and propose  a novel perspective to understand graph imbalance via bias-variance decomposition.By leveraging graph data augmentation, the paper develops a regularization technique to approximate the model's variance. The effectiveness of the method is evaluated across multiple settings and datasets, where the proposed method largely outperforms the compared baselines.", "questions": "- What value does \"v\" at Line 208 take? Is it a fixed value across the training or it is dynamically adapted? \n- What does it mean in Sec. 2.2 that \"We randomly mask node properties\"? Does it mean dropping nodes and the corresponding edges of the original graph at random? Is this a standard way of performing data augmentation on graph? What are other alternative data augmentation methods? It would be great if the authors could give more information on this either in Sec. 2.2 or in related work.", "limitations": "None", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The idea is novel and has solid theoretical motivation.\n- Strong performance improvement + extensive experiments.\n- The paper is clearly written and well-structured.", "weaknesses": "- As someone not working directly in the same field, I think it would be very helpful if the related work section could be more comprehensive than its current shape. Plus, the method design in Sec. 4 shares similarity with many existing techniques. For example, the \"confidence-based label-guided consistency regularization\" in Eq. 8 has been widely used in standard semi-supervised learning (UDA, FixMatch, FlexMatch) for a long time. And the idea of intra-class aggregation for contrastive learning is also studied in Supervised Contrastive Learning paper. IMHO, it would be better if the paper could discuss the difference with them and tune down accordingly, which does not harm the originality of this paper.\n\nUnconfident comments:\n- I appreciate the analysis on that overall variance increases with the increase of imbalance ratio. But it is a bit surprising there was not any analysis like this before even in the field of long-tailed recognition. Could the authors please comment on this?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your comments that the theoretical and experimental contribution of RVGNN is strong for tackling imbalance problems. We address all your concerns below:\n***\n**Q1**:The related work section could be more detailed. The method in Sec. 4 resembles existing techniques. Discussing differences and making adjustments won't affect the paper's originality.\n\n**Answer1**:  \nWe appreciate your recognition of the similarities between our method and existing techniques [1,2,3], and we agree that a more detailed comparison with these techniques would enhance the paper.  we would like to kindly draw your attention to **Appendix A where we have provided more detailed related work** including Imbalanced Learning in the Vision Domain and Graph Contrastive Learning. Here is an attempt to address your concern. \n- **Related work of our confidence-based label-guided consistency regularization**:  You are right in pointing out that the method in Eq. 8 shares similarities with widely-used semi-supervised learning techniques like UDA, FixMatch, and FlexMatch. Both UDA[1] and FixMatch[2] emphasize consistent labels after enhanced data augmentation. Consistency loss is skipped for low-confidence samples. FlexMatch[3] challenges a fixed threshold, advocating for adaptive adjustment of pseudo-label status via curriculum learning during training.\n- **We distinguish our work from them as follows**:\n  - First, the confidence-based label-guided consistency regularization we use is **to better estimate the variance of the model** accurately and reduce the interference of samples whose samples are poorly predicted.\n  -  **Our approach considers the underlying graph structure, exploiting the relationships between nodes to guide the consistency regularization process. This adaptation leads to more coherent propagation of information across graph structures, which distinguishes our method from the conventional techniques mentioned**. However, we acknowledge the importance of making these distinctions more explicit and will revise the section to articulate these differences more clearly.\n- **Related work of our Intra-class Aggregation for Contrastive Learning**: we also acknowledge the similarities between our method and the ideas studied in the Supervised Contrastive Learning[4] paper. Our intra-class aggregation is indeed conceptually similar, but we employ this concept differently to suit the particularities of graph-structured data. \n   - By considering the relational information in graphs and employing an innovative aggregation strategy, our method strives to capture deeper inter-node dependencies, which differentiates it from the approach taken in Supervised Contrastive Learning. We will provide a more explicit comparison between these methods in the revised manuscript to clarify the novel aspects of our approach. **Importantly, within the GNN domain, we are the first to introduce the idea of supervised contrastive learning into imbalance node classification, which can inspire follow-up work, and we think this is one of our contributions.**\n\n**We agree with your suggestion that discussing these differences and drawing connections with existing methods would not harm the originality of our paper.**  \n\n[1] Xie, Qizhe, et al. \"Unsupervised data augmentation for consistency training.\" Advances in neural information processing systems 33 (2020): 6256-6268.\n\n[2] Sohn, Kihyuk, et al. \"Fixmatch: Simplifying semi-supervised learning with consistency and confidence.\" Advances in neural information processing systems 33 (2020): 596-608.\n\n[3] Zhang, Bowen, et al. \"Flexmatch: Boosting semi-supervised learning with curriculum pseudo labeling.\" Advances in Neural Information Processing Systems 34 (2021): 18408-18419.\n\n[4] Khosla, Prannay, et al. \"Supervised contrastive learning.\" Advances in neural information processing systems 33 (2020): 18661-18673.\n***\n**Q2**: The author values the variance analysis with imbalance ratio but is surprised it's absent in long-tailed recognition.\n\n**Answer2**:  \n- We sincerely value the reviewer's keen insights and feedback on this matter. Upon conducting an exhaustive literature review, it appears that **our study is among the pioneering works to investigate the relationship between variance and imbalance ratio**. We also believe that our focus on optimizing the model's variance through theoretical analysis in both graph learning and traditional imbalanced learning is novel. Recognizing the importance of this contribution, we have been meticulous in our theoretical approach. As detailed in Section 6, we have plans to extend RVGNN and its foundational theories to broader areas, including computer vision and natural language processing.\n- To further clarify, we'd like to emphasize that our work currently seems best suited for graph-specific settings. In optimizing the approximate variance, graph data augmentation(GDA) is crucial as it serves to emulate diverse training sets. In this work, it's worth noting that GDA is distinct from traditional data augmentation. Here, GDA acts as a form of dataset augmentation.  It not only perturbs the features of individual nodes but also significantly modifies the graph dataset by cropping or adding edges. However, we recognize that applying our framework to traditional settings may not be direct.\n***\n**Q3**: Value of \"v\" at Line 8.\n\n**Answer3**: The value  \"v\" serves as a threshold to determine whether a node's prediction is confident. It is treated as a hyperparameter.\n\n***\n**Q4**: The meaning of \"randomly mask node properties\" and other alternative graph augmentation methods.\n\n**Answer4**:  \n- Randomly masking node properties involves randomly **replacing or hiding specific attributes of certain nodes** within the graph.\n- Other augmentation methods include node/edge perturbation, subgraph sampling, feature noise addition, and so on.\n\nWe will expand on these points in **detail in the related work section** to provide a more comprehensive explanation."}]

Author rebuttal:
We thank all the reviewers for their constructive and insightful feedback. 
  - We have thoroughly revised the paper, making sure to correct all the typos and standardize the notation throughout.
  - We **have uploaded our revised Figure 2(Pipeline of RVGNN) here**, in this figure, additional elements have been incorporated that were not previously marked. 



Meta-review: The paper has received positive and constructive feedback from multiple reviewers. The innovative approach of connecting model variance with class imbalance in graph learning has been recognized for its novelty and significance. The comprehensive rebuttal process effectively addressed concerns across various aspects of the research, such as theoretical derivations, experimental results, and assumptions. 

Reviewer j7Kz initially raised some critical points; however, he did not engage further after the authors offered additional justifications. Overall, the majority of reviewers have acknowledged the paper's merits.
Decision: Accept (poster)