UNREAL: Unlabeled Nodes Retrieval and Labeling for Heavily-imbalanced Node Classification
Authors: Liang Yan
Shengzhong Zhang
Bisheng Li
min zhou
Zengfeng Huang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Node Classification
Heavily-imbalanced Representation Learning
Graph Neural Networks

Abstract: Extremely skewed label distributions are common in real-world node classification tasks. If not dealt with appropriately, it significantly hurts the performance of GNNs on minority classes. Due to the practical importance, there have been a series of recent researches devoted to this challenge. Existing over-sampling techniques smooth the label distribution by generating ''fake'' minority nodes and synthesize their features and local topology, which largely ignore the rich information of unlabeled nodes on graphs. Recent methods based on loss function modification re-weight different samples or change classification margins, which achieve good performance. However, representative methods need label information to estimate the distance of each node to its class center, which is unavailable on unlabeled nodes.  In this paper, we propose UNREAL, which is an iterative over-sampling method. The first key difference is that we only add unlabeled nodes instead of synthetic nodes, which eliminates the challenge of feature and neighborhood generation. To select which unlabeled nodes to add, we propose geometric ranking, which ranks unlabeled nodes based on unsupervised learning results in the node embedding space. Finally, we identify the issue of geometric imbalance in the embedding space and provide a simple metric to filter out geometrically imbalanced nodes. Extensive experiments on real-world benchmark datasets are conducted, and the empirical results show that our method significantly outperforms current state-of-the-art methods consistent on different datasets with different imbalance ratios.

Under review as a conference paper at ICLR 2023
UNREAL: NODES RETRIEVAL AND LA- BELING FOR HEAVILY-MBBALANCED NODE CLASSIFI- CATION
Anonymous authors Paper under double-bling review
ABSTRACT
Extremely skewed label distributions common in real-world node classifica- tion tasks. If not dealt with appropriately, it significantly hurts the performance of GNNs minority classes. Due to the practical importance, there have been a series recent researches devoted to this challenge. Existing over-sampling techniques smooth the label distribution by generating "fake" minority nodes and synthesize their features and local topology, which largely ignore the rich infor- mation of unlabeled nodes on graphs. On the other hand, methods based loss function modification re- re-weight different samples or change classification mar- gins. Representative methods in this category need use label information estimate the distance of each node to its class center, which is unavailable on un- labeled nodes. In this paper, we propose UNREAL, an iterative ove--sampling method. The first key difference is that we only add unlabeled nodes instead of synthetic nodes, which eliminates the challenge of feature and neighborhood gen- eration. To select which unlabeled nodes to add, we propose geometric ranking to rank unlabeled nodes. Geometric ranking exploits unsupervised learning in the node embedding space to effectively calibrates pscudo-label assignment. Finally, we identify the issue of geometric imbalance in the embedding space and provide simple metric to filter out geometrically imbalanced nodes. Extensive experi- ments on real-world benchmark datasets are conducted, and the empirical results show that our method significantly outperforms current state-of-the-art methods consistent on different datasets with different imbalance ratios.
INTRODUCTION
Node classification is ubiquitous in real-world applications, ranging from malicious account de- tection (Mohammadrezaei et al., 2018) to fake news detection (Monti et al., 2019). Many real- world data comes with an imbalanced class distribution (Mohammadrezaeii al., 2018; Wang al., 2020b). For instance, the proportion of malicious accounts in social networks is usually very rare. A model trained using imbalanced dataset is prone be sub-optimal under-represenned classes. While GNNs have achieved superior performance on node classification, training a fair GNN model for handling highly-imbalanced class distributions remains challenging task. For the application of malicious account detection, GNN models would easily overfit the samples from the rare class of malicious accounts (Liu et al., 2018: Zhao al., 2021). The message passing scheme of GNN mod- els make the problem even more complex, as here the samples cannot be treated as i.i.d. samples. Moreover, quantity imbalanced is often coupled with topology imbalance (Chen al., 2021), 1), and thus it is difficult to extend existing techniques for handling i.i.d. data to relational data.
Given its importance and unique characteristics, a group of recent studies has been devoted to solving the imbalanced node classification problem (Zhao et al., 2021; Shi et al., 2020; Chen et al., 2021; Park et al., 2021; Song et al., 2022). Over-sampling strategies are simple and effective for handling data imbalance. However, it is non-trivial task to adapt them to graph data since the topological information of newly synthesized nodes is not provided. GraphSMOTE (Zhao et al., 2021) extends the synthetic minority embedding space and generating relation information using link prediction. Shi et al. (2020) uses a generative model to generate nodes smooth the label distribution. GraphENS (Park et al., 2021)
sampling technique (SMOTE) graph data by synthesizing nodes in the

---

Under review as a conference paper at ICLR 2023
synthesizes the whole ego network of a new sample by combining two different ego networks based on their similarity.
It is empirically observed in (Song al., 2022) that the performance of existing over-sampling ap- proaches is casily affected by (synthetic) minority nodes with high connectivity to other classes. To alleviate this issue, Song et al. (2022) modify the loss function (thus the classification margin) based on various statistics of the true label distributions of target nodes and classes. Chen et al. (2021) coin this phenomenon by topology imbalance, and propose re-weight the samples according to their distance to the classification boundary, in which the distance is inferred via the structural similarity and label information. As we note, both methods rely on ground truth label information, which is not available for most nodes. Song et al. (2022) first train the model with the original training set and use the model predictions to modify the loss function, while Chen et al. (2021) only uses label information in the training set when computing the topology imbalance metric. However, the train- ing set is highly-skewed in the first place, so information derived from them is less reliable, and the bias could spread to later building blocks, which hurts the overall performance.
In this paper, we propose a novel imbalanced node classification method: unlabeled node retrieval and labeling (UNREAL). At a high level, UNREAL is an over-sampling based approach, however several distinct features make our method differ from existing over-sampling techniques signifi- cantly. First, motivated by the observation that abundant unlabeled nodes available in node classification scenario, instead of synthesizing new minority nodes, which brings in both additional noise and large computational burden, only add "real" nodes to the training set. Adding unla- beled nodes (logether with their pseudo-labels) to the training set is commonly used technique for semi-supervised node classification, which is proved to be highly effective for dealing with label sparseness (Li et al., 2018; Zhou et al., 2019; Sun et al., 2020; Wang et al., 2021c). (ST) trains GNN on existing labeled data, then selects samples with high prediction confidence for each class from unlabeled data, and adds them to the training set. However, in imbalanced scenar- ios, ST cannot achieve satisfactory performance due to the bias in the original training set: using the predictions from a classifier trained on the imbalanced training set may be highly biased and contains a large portion incorrect pseudo-labels. This drawback of ST is empirically verified in our experiments (see Section 3). Thus, we propose a series of techniques to overcome this challenge, and our experimental results show these techniques are highly effective and outperforms baselines by large margin.
Similar to (Chen et al., 2021), we try to add nodes that are close to class centers to alleviate topology imbalance. To identify such good nodes, we train the model with the training set and use the predic- tion confidence as the selecting criteria, which we call confidence ranking. However, the bias in the original training set results in unreliable predictions (Song al., 2022), which inevitably hurts the performance. Therefore, we introduce a key building block which utilizes the geometric structure in the embedding space to calibrate the bias in the prediction confidence. This idea is partially inspired by the work of Kang et al. (2019), where they hypothesize and verify empirically that the classifier is the only under- pedfor-erf component in the model when trained on an imbalanced training set. Thus, after the preliminary training step, we retrieve node embeddings from the output layer (before the classification layer) and use unsupervised clustering methods to rank the closeness of nodes to their class centers, which we call geometric ranking. Also, given the two rankings, we apply infor- mation retrieval techniques to select the best-unlabeled nodes to add. In practice, this procedure will be applied iteratively for multiple rounds.
We summarize our contribution as follows: 1) As far as we know, UNREAL is the first method to use unlabeled nodes rather than synthetic ones in over-sampling approaches deal with class imbalanced node classification; 2) for unlabeled node selection, UNREAL is also the first to apply unsupervised methods in the embedding space get complementary and less biased label predic- tions; 3) we introduce geometric ranking, which ranks nodes according to the closeness of each node to its class center in the embedding space; 4) given confidence and geometric rankings, infor- mation retrieval techniques is used to effectively select high-quality new samples; 5) We identify the Geometric Imbalance (GI) issue in the embedding space, and propose metric measure GI and discard imbalanced nodes.
We conduct comprehensive experiments on multiple benchmarks, including citation networks (Sen et al., 2008), an Amazon product co-purchasing network (Sen et al., 2008), and Flickr (Zeng et al., 2019). We also test the performance of UNREAL on several mainstream GNN architectures namely
2

---

Under review as a conference paper at ICLR 2023
GCN (Kipf & Welling, 2016), GAT (Veličkovié al., 2017), and GraphSAGE (Hamilton et al., 2017). Experimental results demonstrate the superiority of the proposal as UNREAL consistently outperforms existing state-of-the-aa approaches by a large margin.
PRELIMINARIES
2.1 NOTATION AND DEFINITIONS
In this work, we mainly focus on the ubiquitous semi-supervised node classification setup. Given an undirected and unweighted graph G (V,E,C) Here, V is the node set and & is the edge set, L C V denote the set of labeled nodes, so the set of unlabeled nodes is 2 = V - C. and X E RR*xf the feature matrix (where n |V] the node size and f is the node feature dimension). We use A E {0, 1) to denote the adjacency matrix and (Nv) the set of 1-hop neighbors for node e. The labeled sets for classes are denoted by (2., ,Cz), where is the number of different classes. We use imbalance ratio, defined as == max, min;([C,])) to measure the level of imbalance in dataset. We summarize the notation in table in Appendix A.
2.2 MESSAGE PASSING NEURAL NETWORK FOR NODE CLASSIFICATION
In this section, we briefly introduce message passing neural networks (MPNNs). A standard MPNNs consists of three components, message function my an information aggregation function O,, and a node feature update function 4/2. The feature of each node is updated iteratively. Let h2 be the feature of node the (-th layer, then in the (1 + 1)-th layer the feature is updated as:
k 1/1 (n.).e. O: (f (n(9, MD) eu..) I IuE.N()))))
where Gy is the edge weight between v and u. For the classic GCN model (Kipf & Welling, ev.u Nru where क' is the parameter 2016), 1hg (1+1) is computed as: 1eg (1+1) ΦO EneN(o)u(o) Vd.d.
matrix of the 1-th layer and d. 11 1+1 11 EueN(o) Cu For node classification, classification layer concatenated after the last layer of a GNN.
3 PSEUDO-LABEL MISJUDGMENT AUGMENTATION PROBLEM IN IMBALANCED LEARNING
Since self- trifitraining adds pseudo-labels to the training set and trains the model iteratively, misjudge- ments in the early stages will cause the method to fail badly. We extensively investigate this issue of ST in imbalanced learning. Conventional ST-based methods are generally exploited to deal with sparsely label distribution to improve the performance of the model. However, the problem of clas- sifier bias that often occurs in imbalanced scenarios has not received attention if we apply these methods straightly imbalanced learning. Here, we hypothesize that as the imbalance ratio of the dataset becomes larger, the pseudo-labed obtained by ST-based methods are less credible. At the same time, the prediction confidence of unlabeled nodes is no longer reliable. We conduct com- prehensive experimental studies to very this hypothesis. Due to space constraints, we elaborate the experimental details and conclusions in Appendix B.
UNREAL
In this section, we provide the details of the proposed method. UNREAL iteratively adds unlabeled nodes (with predicted labels) to the training set and retrains the model. We propose three com- plementary techniques to enhance the unlabeled node selection and labeling. More specifically, in Section 1. we describe Dual Pseudo-tag Alignment Mechanism (DPAM) for effective node filter- ing, the key idea of which to use unsupervised clustering in the embedding space to obtain a node ranking. In Section 4.2, show how to combine geometric rank from DPAM and confidence rank- ing to reorder unlabeled nodes according to their closeness to the class centers Noode-reodderig! Finally, in Section 4.3, identify the issue of geometric node imbalance (GI) and define new
3

---

Under review as a conference paper at ICLR 2023
metric to measure GI, which is then used to filter out nodes with high GI. The overall pipeline of UNREAL illustrated in Figure Our full algorithm is also provided in the Appendix G (Algo- rithm 1).
4.1 DUAL PSEUDO-TAG ALIGNMENT MECHANISM FOR NODE FILTERING
UNREAL iteratively adds unlabeled nodes to the training In each iteration, first train the GNN model using the current training set. In the early stages the training set remains imbalanced, so the model is likely generate biased predictions. According to Kang et al. (2019), the embeddings learned by the model are still of high quality, even if it is trained on imbalanced data. Therefore, DPAM exploits the geometric structure in the embedding space and produce candidate set of new samples.
Let be the embedding dimension. We use H E RIalxd and H² E R|4 x to denote the embed- ding matrix of labeled and unlabeled nodes respectively. Each row of the embedding matrix the embedding of a node u (denoted as hn and hw), which is considered as a point in the d-dimension Euclidean space. DPAM applies an unsupervised clustering algorithm, felusters which partitions the embeddings of unlabeled nodes into / clusters and produces k corresponding cluster centers, where K is usually larger than k, the number of classes.
fehuster (11)
C2, ... ,K,, cx
(2)
where K2, is the i-th cluster and is the i-th cluster center. We use vanilla k-means in our imple- mentation. We also compute the embedding center of each class in the training set
Jrain M(( yuu E C.)).
Since we use k-means in our experiments, M() is simply the mean function. We next assign pseudo-label Vm each cluster Km::
y: arg min distance(d ca).
We then combine clusters with the same pseudo-label m Um. and = = Üm On the other hand, the GNN model gives each node u in U prediction Du. and put unlabeled nodes whose prediction is into the set Um. and 4 U Um.
Dual Pseudo-tag Alignment Mechanism (DPAM) The pseudo-labels produced by applying an unsupervised algorithm on the embeddings provide alternative and potentially less biased predic- tion, which may compensate the bias introduced by the imbalanced training set. At the same time, the overall accuracy of the unsupervised algorithm is inferior to supervised methods, and thus is sub-optimal to rely solely on the pseudo-labels from clustering. As a result, DPAM only keeps un- labeled nodes whose two labels aligns, i.e., those belong to the intersection of Um and Um for each m E 2, ... k); and each node in Um nuum gets a pseudo-label m. Due to the space constraints, we defer the empirical studies on why DPAM works to Appendix D.I.
4.2 NODE RE-ORDERING
Now DPAM has selected pool of candidate nodes: 2 U (Uhm Mm). In this section, f=m
present Code-Reoo,,,,ng, a method that re-orders nodes in Z according to the closeness of each node to its class center. Rode-Reordering combines the geometric ranking from the unsupervised method and confidence ranking from model prediction.
Geometric and confidence rankings Suppose u E Üm Un. and let by be the embedding of u. We measure the distance between node and its class center by
8, distance ( unin)
(5)
4

---

Under review as a conference paper at ICLR 2023
Training GNN
Prediction
Cluster
1.67
Inn. IT Goomaric Ranidnn
Alignment
Update
11 111..
Discarting geometrically Intsfanced
Mode-Reordering
Figure I: Overall pipeline of our UNREAL. Colored nodes denote labeled nodes. Parameters in the GNN Model and the classifier are trained together using the current training set.
where ctrain is the class center of class m (see equation 3). For each class m, sort nodes in Um n Um in the increasing order of their distance to the class center, obtain ls sorted lists (S,,S,, S.),, which we call geometric rankings.
On the other hand, for each node u E Um Nun. we can get a classification confidence for the node from the output of the classifier as follow:
predictions = softmax (logits), con fidence max (predictions).
(6)
Here, logits is the output of the neural network, usually h (number of classes) dimensional vector. The pseudo-labels u from the classifier is the index of class with highest prediction probability and the corresponding probability its confidence. We sort nodes in üm n tm in the decreas- ing order of their confidence, and obtain another & sorted lists (T1, T2 ... T which we call confidence rankings.
Rank Biased Overlap In the fields of information retrieval and recommendation systems, fun- damental task is to measure the similarity between two rankings. Rank Biased Overlap (RBO) (Webber al., 2010) compares two ranked lists, and returns numeric value between and one to quantify their similarity. A RBO value of zero indicates the lists are completely different, and RBO of one means completely identical.
Node-Reo For each class m, we calculate the RBO value between S,, and Tm and then use the RBO score as a weight and get the weighted combination of the two rankings. More specifically, we first compute = RRBO(Sm, Tm), and then compute
N New max (Tm, 1 - rm)} S.. + min - Tm Tms
We then select nodes according to the new ranking based on values in NeNew Note that we always make the geometric rankings have the dominating influence in this step. Due the space constraints, ablation analysis on Node- Reordeing is presented Appendix D.2.
4.3 GEOMETRIC IMBALANCE
In this section, we consider the issue geometric imbalance (GD) in the embedding space, and define simple and effective metric measure GI.
5

---

Under review as a conference paper at ICLR 2023
Geometric Imbalance In highly imbalanced scenarios, minority nodes often suffer from topology imbalance (Song et al., 2022; Chen et al., 2021), which means the node stays near the boundary between the minority class and majority class. The geometric ranking and DPAM introduced above effectively alleviate this issue. However, when the class centers of a minority class and a majority class very close in the emhedding space, the problem may still exist: rank nodes only based on their absolute distance to the centers, so the nodes on the boundary of two close classes may have high rankings. We refer to this issue as geometric imbalance in the embedding space. We present a visualization to illustrate geometric imbalance, which is in Figure 9 due to space constraints.
Discarding geometrically imbalanced nodes (DGI) After identifying the GI problem, we define a simple and natural metric to measure the degree of GL. According to equation 5, 6, refers to the distance between the embedding of u and the center of the class to which u is assigned (i.e.. the closest class center among all classes). Similarly, we define Su as the distance between the embedding of u and the second closest center to u. We have on S Bu for all u, and intuitively, o, ~ Bu, then is likely to have high degree of GI. We thus define the metric for measuring GI as
Bu 6n
Gl
6a
We refer to the metric as GI index. The GI issue is more seriously on node with smaller GI index. So we set a threshold and discard all nodes with GI index below the threshold. We empirically verify the effectiveness of DGI, and the results and analysis are provided in Appendix D.2.
4.4 SELECTING NEW NODES ITERATIVELY
As in self-training techniques. we select nodes to join the training set in several rounds, and in each round we retrain the model using the newly formed training set. In highly-imbalanced cases, we only add nodes from the minority classes. In this way, the label distribution of the training set gradually smoothed, and the imbalance issues of minority nodes are alleviated, benefiting from the addition of high-quality new samples.
5
EXPERIMENT
5.1
EXPERIMENTAL SETUPS
Datasets We validate the advantages of our method on five benchmark datasets(i.e. Cora, CiteSeer, PubMed, Compuut- and Flickr) under different imbalance scenarios, in which the step imbalance scheme given in (Zhao et al., 2021; Park et al., 2021; Song et al., 2022) is adopted to construct class imbalanced datasets. More specifically, we choose half of the classes as minority classes and convert randomly picked labeled nodes into unlabeled ones until the imbalance ratio of the training set reaches p. For Flickr, in the public split, the training set is already imbalanced, and thus directly this split and do not make any changes. For the three citation networks (Cora, CiteSeer, Pubmed), we use the standard splits from Yang et al. (2016) as our initial splits when the imbalance ratio is 10, 20. To create larger imbalance ratio, 20 labeled nodes per class is not enough, and we use a random split as the initial split for creating an imbalance ratio of 50 and 100. The detailed experimental settings such as evaluation protocol and implementation details of our algorithm are described in Appendix F.
Baselines We compare UNREAL with several classic techniques (cross-entropy loss with re- weighting (Japkowicz & Stephen, 2002), PC Softmax (Hong al., 2021) and Balanced Soft- max (Ren et al., 2020)) and state-of-the-ard methods for imbalanced node classification, including GraphSMOTE (Zhao et al., 2021), GraphENS (Park et al., 2021), ReNode (Chen et al., 2021), and TAM (Song et al., 2022). Among them GraphSMOTE and GraphENS are representative over-sampling method for node classification. ReNode and TAM are loss function modification approaches. For TAM, test its performances when combined with different base models, includ- ing GraphENS, ReNode, and Balanced softmax, following Song et al. (2022). The implementation details of baselines are described in Appendix F.5.

---

Under review as a conference paper at ICLR 2023
Table 1: Experimental results of our method UNREAL and other baselines on four node classification benchmark datasets with p 10. We report averaged balanced accuracy (bAcc.,% 9) and FI FI-score (%) with the standard errors over 5 repetitions on three representative GNN architectures.
Dataset
Cona
Clichin
Publde
Imhalance Ratio (p- 10)
hAr::
bAcc:
hAoz
Weight
1.78
2:30
68.04
0.81
50.18
0.14
0.94
$1.54
73.30 0.51
ValzacedSofemax
69.95 0.55
0.55
55.52
0.7
71,55
1.06
$1.46 0.74
74.31
0.51
GraphSMOrI
06.29:10.66
05:09
053
44.80
67.91
62
1.91
78.48
1:447
72.651:00 1:30
Renak:
67.03:4:1.41
67.16:11.5
1.67
43.47
2.32
57.52
3.10
71.40
$ 1.42
67.27
2:99
81779:0.777
73.13
1113::11.00 1.40
GrayhENS
7089--10.71
$6.57
= 0.98
55.29
1.33
72.13
$ 1.04
70.72
2 1.07
82.40 0.39
74.26
1.00
BalancedSftmaa-TAAA
09:34
69:54
0:47
56.73
= 0.71
56.15
0.76
74,62
6 0.97
12.25
2: 1.30
92.36
2: 0.67
72.94
1:43 1.43
Renode TAM
08.25 1.84
65.11
1.97
46.30
= 1.17
39.96
2.76
72,63
à 2.02
68.28
3.30
90.36
2: 1.19
72.51
1:0.8
GraphENS-AAM TAM
71,99+:0.35
73.14
0.51
$5.01
0.68
56.30
1.0
74.14
+ 1.43
72.42
1.30
$1.02
+ 0.99
70.76
+ 1.72
UNREAL
78.33 1: 1/04
76.44
1/86
05.63
1.38
64.94 2 1.38
75.35 a: 1.41
73.65
1.43
$5.08 1: 0.38
75.27
4 0.23
46.64
+1.23
+2.68
+0.96
Vanilla
02.31 1: 1.56
61.82
1.34
38.84
1.13
$1.25
1.64
04.00
1: 1.64
25.26
2.80
79.06 3: 1.00
70000 2.50
Ke- Weight
06.87 0:09
66
85.47
2.35
40.00
2.9%
10
2.85
63:16
3,54
0.56
0:76
Sefene
06 0:0:9
0604
90.78
1.66
48.56
2.08
0.89
79.45
71
0.56
BalancedSotmax
67.89
54.78
1.25
2.13
72.30
1.79
82.02
72.94
GraphSMOTE
66.71 4:332
07:43
2.54
09:76
Renode
GrapatiN
13.15
11,001
09.66:00.77
56.30
1.25
1.14
75.54
1.44
Ranode TAM
67.50 0:67
45.12
70.66
3.54
1.75
GraphENS TAM
70.15 0.18
0.40
0.36
1.98
UNREAL
7891 1 0.29
75.99
11.7
64.10 = 1.49
63.44
1.47
74,68 :: 1.43
72.78
0.89
85.62 d: 0.44
75.34
0.99
A
+8.46
+5.99
+7,90
+9.13
+1.13
+4.68
+3.60
+2.40
Vanill:
+1:92
60.97
1.07
43.18 = 0.52
56.56
1.25
68.68 + 1.51
64.16
2.58
72.36 + 2.50
64.32:5
2.21
Re. Weight
63.94 1: 1.07
63,82
1.30
96,17
1.32
40.13
1.65
09.80 09.89-1
:: 1.60
65.71
2.51
76.08
6: 1.14
06.76-1
1 1.40
PC Sofemax
0..79-1-::0
66:04
: 0.92
50.66
= 0.99
47
1.65
71.49 :: 0.94
10.25
0.67
78.65 0: 3.01
06.44
4.00
IalnnedSofmmx
67:43-1-00 (-43
67
0.69
S1.34
2.32
49.01
3:16
71.36
1:37
09:06
1.81
73.67 0: 1.11
65.25
2.44
GrSpSSMOT
61:65 6:.34
6009
0.98
43:71
2.87
55.18
1.25
66.1
+ 0.65
61
2.54
71.85
+ 0.08
08.92
0:73
Renode
06.84 1.78
67.05
1.75
48.63
1.37
14.25
2.20
71.37
= 1.33
67.78
1.38
77.37
01 0.74
68.42
1.51
GraphENN
08.74 0:446
68.34
0.33
53.51
0.78
51,42
1.19
70:97
2 0.78
10.00
1.22
$2.57
11 0.50
71.95
0.51
BalncedSofema--AA TAM
0900 0.99
69:00
0.7
51.93
2.19
48,57
3.25
72.28
=: 1.40
71.02
1.51
77.00
3: 2.95
70.85
2.28
Renodee FAM
6722 8: 1:11
65
1:11
08. 99
1.76
63.56
2.51
11.25
1.00
08
0.98
74.81
1.2.2
08.81
7.52
GuaphENS-TE TAM
70455
0.75
$4.69
1.12
53.56
73,61
72.50
1.58
82.17
72.46
1.00
UNREAL
75.99 0.98
66.45
74.78
1,70
A
+5.44
+3.23
+11.76
+12.77
+1,07
+0.30
+0.64
-1.65
5.2 MAIN RESULTS
Experimental results under different imbalance ratios In Table 1 and Table 2, we report the av- eraged balanced accuracy (bAcc.) and F1 score with standard emrors for the baselines and UNREAL on four class-imbalanced node classification benchmark datasets under different imbalance ratios (p 10, 20). The results clearly demonstrate the advantage of UNREAL. Our method consistently outperforms existing state-of- the-art approaches across four datasets, three base models and two im- balance ratios (except for GrE on Amazon- Comzuuerss with imbalance ratio 10). In many cases the margin is significant. To evaluate the performance on very skewed label distribution, we also test in more imbalanced settings (p- = 50, 100), and similarly, our method outperforms all other methods consistently and often by notable margin. We remark that since GraphSMOTE (Zhao et al., 2021) synthesizes nodes within the minority class, it is not applicable when there is only one node in some classes, which is the case when p 20, 50, 100 in our setup. The results are presented in Appendix C.I.
Experimental results for naturally imbalanced datasets We also validate our model on a natu- rally inbalanced dataset, Flickr. The split of training set, validation set, and testing set follows (Zeng et al., 2019), which has an imbalance ratio roughly p= 10.8. We found that existing over-sampling methods use too much memory due to synthetic nodes generation, and cannot handle Flickr on 3090 GPU with 24GB memory. This include GraphENS (Park et al., 2021), GraphSMOTE (Zhao al., 2021) and ReNode (Chen et al., 2021). Due to the space constraints, we provide the experi- mental results in 8.
5.3 ABLATION ANALYSIS
In this section, we conduct ablation studies to analyze the benefit of each component in our method. From the results in Section 3, the necessity of unsupervised learning in the embedding space has been verified. Thus, in this section, DPAM is applied in all comparing methods. Here, test the
7

---

Under review as a conference paper at ICLR 2023
Table 2: Experimental results of our method UNREAL and other baselines on four class-imbalanced node classification benchmark datasets with p 20. We report averaged balanced accuracy (bAcc.,% %)) and Fl-score (%) with the standard errors over 5 repetitions on three representative GNN architectures.
Dataset
Cona
Clickin
PubMed
Amsann-Conggsicn
Ratio (p- 50)
Weight
$7.51
61.74
42.53
36.54
1.8
2.97
VadancedSoftmax
64.05 1.05.:0.74
0.36
47.29
1.29
68.31
1.71
69.85
1.59
Renode
59.00.1-100
160
225
67.45
60.40
5.74
74.15
67.27
0.52
GrayhENS
67:30 1.45
66.82
1.40
46.39
3.48
42.38
4.14
71.37
1.77
69.37
1.69
75.41
9: 1.75
69.32
1.58
64.75:10.254
63:45
0.72
48.52
1.6
46.38
1.79
09.95
2.09
68.90
2 1.86
77.09
8: 2.00
69.86
1.76
Renode TAM
59.88 4:
58,03
1.66
41.11
2.45
51.58
2.62
68.53
6 3.53
64.2
4.32
73.46
2: 1.77
67.50
1.18
GraphENS- TAM
00.94
1.28
66.07
1.42
48,00
2.98
45.00
4.15
71.92
1.58
09.35
2: 1,88
75.78
1,57
68.58
2: 1.78
UNREAL
77.12 2: 0.75
74.15
11.7
55.81 = 6.11
53.19
6.23
73,06 :: 1.87
70.77
1.96
$5.69 2: 0.11
74.81
0.68
Vanilla
51.51 1: 0.55
46.59
0.61
54.14
0.15
22.00
0.15
00:22 2: 0.47
46.05
0.70
08.09
2.96
00L08 2.76
Weight
58.63
55.95
3.7
36.79
26,83
1.61
63.47 1: 1.73
54.53
3.25
71.48
2.42
02.86
1.98
Sefemax
3961 1: 1.41
56.71
1.55
2.01
39.10
2.12
10.51
1.41
10.25
1.30
71.16
02
0.57
RalmeenSSofmmx
62.05 1/62
61:14
1.25
67.4%
1:71
0:08
Renode
1.67
GraphENS
64.52 2.05
BalanceSSttma-TOo
71.17
GryyEENSTAMM TAM
65.78
1.32
UNREAL
0.71
76.21
11.88
65.11
5,00
53.67
5.51
72.54
1.52
710.4 1.91
83.19 :: 0.66
74.39 0.59
A
+13.22
+12.41
+6.75
+5.51
+1.37
+1.69
19.64
+10.36
Vanill
$6.61
$0.95
1.50
97.30 96
1.0%
27:49
1.41
60.04
54.18
1.21
62:330
7.67
65.
2.09
Re-Weight
$7.37 03.7-+-061
55 99.99
0:32
37.00 09
1.20
27.90
2.01
65.01
3.60
58.34
2.19
68.31
+ 7.06
60:45
00445++23 2.40
PC Sollinas
50.25
58.55
0.81
42.77
1.82
40.08
1.82
70.55 + 1.19
67
+ 1.99
71.57 + 2.86
62.75+t2.40 2.69
BzlenceSootmax
61.93:11.26
60,89
1.36
43.64
1.35
58.31
2: 1.13
09.89
1:40
68.12
2: 0.78
08.45
2: 2.92
62.12:3..10
Renede
38.88-10057
55.39
0.58
90.00
= 2.36
$1.78
5.24
06.30
2.63
58.72
4.16
08.36
1.54
61.60 2:000
GraphEZNS
63.54 1:511
02:20=00.37 0.87
44.89
2:51
40.48
2.94
71.37
1.77
09.37
1.89
75 2.20
67.89
1.60
66.15.1:::4
63.63
1:10
44.90
2.36
40.17
2.06
10.06
69.34
1.35
66.10
2.30
99.22
Ranoder TAMM
59.77 2.20
57.95
2.79
42.50
0.93
35.11
1.84
67.31
2.73
00.63
3.69
66.42
2: 2.32
58.62
1.95
GraphENN- TAM
03.39 0:9-1:11 1.36
61.00
1.53
05.92
1.95
$1.97
2.50
09.02
0: 2.59
06.35
3.00
75.75
9 2.30
08.96
1.29
58.35
0.67
1.42
+5.69
+15.54
+1.61
Table 3: Ablation analysis on different components
Modules
Confidence ranking Geometrie ranking
Node-reordering DGI
F1
73.93
0.95
72.74
0.63
Cor+GGCN
X
x
75.85 1: 0.82
75.34
0.63
75.00
0.97
X
X
76.44
1.06
X
46.09 :: 4.08
47.76
50.32 +: 3.75
CiteSer4SAGE (p 20)
53.32 :: 3.75
58.711 3.21
X
x
57.51 1: 4.92
X
X
X
76.34 1: 0.39
0.39
77.32
0.21
PuhMed+GGAT (o 50)
X
76.89 1 1.43
77.38
0.39
x
X
X
70.86 + 1.73
x
72.32
2.43
Computers+GAT (p 100)
X
73.65 1: 0.67
74.03 1: 2.53
75.83 0.74
performance of three different ranking methods, namely confidence ranking, geometric ranking, and Node-reordering (which combines the former two rankings with information retrieval techniques). Moreover, we test the effect of DGI, which aims to eliminate geometrically imbalanced nodes. As shown in Table 3, each component our method can bring performance improvements. In particular, in three out of four settings in the table, Node-reordering- achieves best F1 scores.
8

---

Under review as a conference paper at ICLR 2023
In all cases, using geometric ranking is better than confidence ranking, which empirically verifies our hypothesis that the prediction confidence scores might contain bias and be less reliable.
RELATED WORK
Imbalanced learning Most real-world data is naturally imbalanced. The major challenge in im- balanced scenarios is how train fair model which does not biased toward majority classes. There are several commonly used approaches for alleviating this problem. Ensemble learning (Freund & Schapire, 1997; Liu al., 2008; Zhou al., 2020; Wang al., 2020a; Liu al., 2020; Cai al., 2021) combines the results of multiple weak classifiers. Data re-sampling methods (Chawla et al., 2002; Han et al., 2005; Smith et al., 2014; Sáez et al., 2015; Kang et al., 2019; Wang al., 2021a) smooth the label distribution in the training set by synthesizing or duplicating minority class sam- ples. A third class of approaches alleviate the imbalance problem by modifying the loss function, which give larger weights to minority classes change the margins of different classes (Zhou & Liu, 2005; Tang al., 2008; Cao et al., 2019; Tang et al., 2020; Xu al., 2020; Ren et al., 2020; Wang et al., 2021b). Methods based on post-hoc correction compensate minority classes during the inference step, after model training is complete (Kang et al., 2019; Tian et al., 2020; Menon et al., 2020; Hong et al., 2021). Although these techniques have been widely applied on the i..d. data, is not a trivial task to extend them to graph-structure data.
Imbalanced learning in node classification Recently, series of researches (Shi et al., 2020; Wang et al., 2020c; Zhao et al., 2021; ;; Liu et al., 2021: Qu et al., 2021; Chen et al., 2021; Park et al., 2021; Song et al., 2022) explicitly tackle the challenges brought by the topological structures of graph data when handling imbalanced node classification. GraphSMOTE (Zhao et al., 2021) syn- thesizes minority nodes in embedding space by interpolating two minority nodes using the SMOTE (Chawla et al., 2002) algorithm, and infers the neighborhoods of new nodes with link prediction algorithms. ImGAGN (Qu al., 2021) generates the features of minority nodes with all of the minority nodes according to the learned weight matrix, and synthesizes the neighborhoods of new nodes by based on weights. Qu al. (2021) only consider binary classification, and is computa- tionally expensive to build a generator for each class multi-classification tasks. GraphENS (Park et al., 2021) works for multi-class node classification, which synthesizes the whole ego network for minority nodes by interpolating the ego networks of two nodes based on their similarity. Chen et al. (2021) identify topology imbalance as a main source of difficulty when handling imbalance on node classification tasks; they propose ReNode, which mitigates topology imbalance by adjusting the weights of nodes according to their distance to class boundaries. TAM (Song et al., 2022) adjusts the scores of different classes in the Softmax function based local topology and label statistics. To obtain label information of unlabeled nodes, TAM trains the model using the original imbalanced training set and takes the model predictions proxies for ground-truth labels.
CONCLUSION
In this work, we observe that selecting unlabeled nodes instead of generating synthetic nodes in over- sampling based methods for imbalanced node classification is much simpler and more effective. We propose a novel iterative unlabeled nodes selection and retraining framework, which effectively se- lect high-quality new samples from the unlabeled sets to smooth the label distribution of training set. Moreover, we propose to exploit the geometric structure in the node embedding space to compensate the bias in the model predictions. Extensive experimental results show that UNREAL consistently outperforms existing state-of-the-art approaches by large margins.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Jiarui Cai, Yizhou Wang, and Jenq-Neng Hwang. Ace: Ally complementary experts for solving long-tailed recognition one-shot. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 112-121, 2021.
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with bibell-dsttrbutton-awaaaa margin loss. Advances in neural information processing systems, 32, 2019.
Nitesh V Chawla, Kevin W Bowyer, Lawrence O Hall, and W Philip Kegelmeyer. Smote: synthetic minority over-sampling technique. Journal of artificial intelligence research, 16:321-357, 2002.
Deli Chen, Yankai Lin, Guangxiang Zhao, Xuancheng Ren, Peng Li, Jie Zhou, and Xu Sun. Topology-imbalance learning for semi-supervised node classification. Advances in Neural In- formation Processing Systems, 34:29885-29888 29897, 2021.
Yoav Freund and Robert E Schapire. A application to boosting. Journal of computer and system sciences, 55(1):119-139, 1997.
generalization of on-line learning and an
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Hui Han, Wen-Yuan Wang, and Bing-Huan Mao. Borderline-smote: a new over-sampling method in imbalanced data sets learning. International conference on intelligent computing, pp. $78-887. Springer, 2005.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance imagenet classification. In Proceedings the IEFE international conference on computer vision, pp. 1026-1034, 2015.
Youngkyu Hong. Seungju Han, Kwanghee Choi, Scokjun Seo, Beomsu Kim, and Buru Chang. Dis- entangling label distribution for long-tailed visual recognition. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 6626-6636, 2021.
Nathalie Japkowicz and Shaju Stephen. The class imbalance problem: A systematic study. Intelli- gent data analysis, 6(5):429 449, 2002.
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.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXiv:1412.69800 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint 1ewp:090990200. 2016.
Dong-Hyun Lee et al. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. In Workshop on challenges representation learning, ICML, volume 3, pp. 896, 2013.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirly-Second AAAI conference artificial intelligence, 2018.
Xu- Mi-Y Liu, Jianxin Wu, and Zhi-Hua Zhou. Exploratory undersampling for class-imbalance learn- ing. IEEE Transactions Systems, Man, and Cybernetics, Part B (Cybernetics), 39(2):539-550. 2008.
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 202/, pp. 3168-3177, 2021.
10

---

Under review as a conference paper at ICLR 2023
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-14474, 2020.
Ziqi Liu, Chaochao Chen, Xinxing Yang, Jun Zhou, Xiaolong Li, and Le Song. Heterogeneous graph neural networks for malicious account detection. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pp. 2077-2085, 2018.
Aditya Krishna Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar. Long-tail learning via logit adjustment. arXiv preprint arXiv:2007.0733 07314, 2020,
Mohammadreza Mohammadrezaci. Mohammad Ebrahim Shiri, and Amir Masoud Rahmani. Iden- tifying fake accounts on social networks based on graph analysis and classification algorithms. Security and Communication Networks, 2018, 2018.
Federico Monti, Fabrizio Frasca, Davide Eynard, Damon Mannion, and Michael M Bronstein. Fake news detection on social media using geometric deep learning. arXiv preprint 2019.
Joonhyung Park, Jaeyun Song, and Eunho Yang. Graphens: Neighbor-aware ego network synthesis for class- imnalancedd node classification. In International Conference on Learning Representa- tions, 2021.
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, pp. 1390-1398, 2021.
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.
José 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 1111884311100 2015.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collective classification in network data. AI magazine, 29(3):93-93, 2008.
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 Confer- ence on Artificial Intelligence (IJCAI-20), 2020.
Michael R Smith, Tony Martinez, and Christophe Giraud-Carrins An instance level analysis of data complexity. Machine learning, 95(2):225 2014.
Jaeyun Song, Joonhyung Park, and Eunho Yang. Tam: Topology-awad margin loss for class- imbalanced node classification. In International Conference on Machine Learning, pp. 20369- 20383. PMLR, 2022.
Ke Sun, Zhouchen Lin, and Zhanxing Zhu Multi-stage self-supervised learning for graph convo- lutional networks on graphs with few labeled nodes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5892-5899 2020.
Kaihua Tang, Jiangiang Huang, and Hanwang Zhang. Long-tailed classification by keeping the good and removing the bad momentum causal effect. Advances Neural Information Processing Systems, 33:1513-1524 2020.
Yuchun Tang, Yan-Qing Zhang, Nitesh V Chawla, and Sven Krasser. Syms modeling for highly imbalanced classification. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cyber- netics), 39(1):281-288 2008.
Junjiao Tian, Yen-Cheng Liu, Nathaniel Glaser, Yen-Chan Hsu, and Zsolt Kira. Posterior calibration for imbalanced datasets. Advances in Neural Information Processing Systems, 33: 8101-8115 13, 2020.
11

---

Under review as a conference paper at ICLR 2023
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 2017.
Jianfeng Wang, Thomas Lukasiewicz, 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, pp. 3784-3793, 2021a.
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/CVE conference on computer vision and pattern recognition, pp. 3103-3112, 2021b.
Xiao Wang, Hongrui Liu, Chuan Shi, and Cheng Yang. Be confident! towards trustworthy graph neural networks via confidence calibration. Advances in Neural Information Processing Systems, 34:23768 23779, 2021c.
Xudong Wang, Long Lian, Zhongqi Miao, Ziwei Liu, and Stella X Yu. Long-tailed recognition by routing diverse distribution-awar experts. arXiv preprint arXiv:2010.01800 2020a.
Zheng Wang, Qiao Wang, Tanjie Zhu, and Xiaojun Ye. Extending line for network embedding with completely imbalanced labels. International Journal of Data Warehousing and Mining (IJDWM), 16(3):20-36 36, 2020b.
Zheng Wang. Xiaojun Ye, Chaokun Wang, Jian Cui, and S Yu Philip. Network embedding with completely-imballncee labels. IEEE Transactions on Knowledge and Data Engineering, 33(11): 3634-3647, 2020c.
William Webber, Alistair Moffat, and Justin Zobel. A similarity measure for indefinite rankings. ACM Transactions on Information Systems (TOIS), 28(4):1-38, 2010.
Ziyu Xu, Chen Dan, Justin Khim, and Pradeep Ravikumar. Class-weighted classification: Trade- offs and robust approaches. In International Conference on Machine Leurning, pp. 10544-10554. PMLR, 2020.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learming, pp. 40-48. PMLR, 2016.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. arXiv preprint vrxXiv/907.049)) 990700491,, 2019.
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 web search and data mining, pp. 833-841, 2021.
Boyan Zhou, Quan Cui, Xiu-Shen Wei, and Zhao-Min Chen. Bbn: Bilateral-brande network with cumulative learning for long-tailed visual recognition. In Proceedings of the IEEF/CVF confer- ence on computer vision and pattern recognition, pp. 9719-9728, 2020.
Zhi-Hi Hua Zhou and Xu- Ying Liu. Training cost-sensitive neural networks with methods addressing the class imbalance problem. IEEE Transactions on knowledge and data engineering, 18(1): 63-77, 2005.
Ziang Zhou, Jieming Shi, Shengzhong Zhang, Zengfeng Huang, and Qing Li. Effective semi- supervised node classification on laweledeled graph data. arXiv preprint 1901021910002684, 2019.
12

---

Under review as a conference paper at ICLR 2023
A
NOTATION TABLE
Table 4: Elaborated notation table of this paper.
Indices
n
The number of nodes.
The node feature dimension
The number of different classes The number of cluster centers in the embedding space
k
d
The dimension of the embedding space, or the dimension of the last layer of GNNs
T
Rounds select nodes
Parameters
An undirected and unweighted graph
V
The node set of g
The edge set of G
X
The feature matrix of G. X' E Rnx/ The set of labeled nodes of G
The adjacency matrix 9, E (0, 1jaxn The set of 1 1-hop neighbors for node The set of unlabeled nodes, =
(())
C,
The i class of the labeled sets
Imbalance ratio of dataset, p = max: (1C:)) ((C:((CC))
p
The feature of node in the (-th layer The edge weight between v and u The parameter matrix of the (-th layer
ena
H
The embedding matrix of labeled nodes, 11 E H 4lxd The embedding matrix of unlabeled nodes, H E IR u|xd
HU
The embedding of node и E & The embedding of node u, U The i-th cluster
K;
The i-th cluster center, center cluster i-th The pseudo-label of the cluster IC;
Um
The combination of clusters with the same pseudo-label
Ju
The prediction node u II given by GNN model
Um
The combination of unlabeled nodes whose prediction given by the GNN model is
z
The pool of candidate nodes after DPAM, Z
U (úmm num)
i=m
Jrain
The class center of class in the embedding space The sorted lists of geometric rankings
S
T
The sorted lists of confidence rankings
Tm
The similarity between two rankings, r. = RBO(Sm. Tm)
8n
The distance between the embedding of and the closest class center u The distance between the embedding of and the second closest class center to w Threshold of DGI
Ba
7
Weight hyperparameter of RBO
The size threshold of nodes being added in each class per round
Learning rate of GNN model
Functions
The message function of MPNNs
The information aggregation function
di
The node feature update function
fetuster
An unsupervised clustering algorithm for the embedding space
M()
The mean function
Jg
GNN model
13

---

We process Under review as a conference paper at ICLR 2023
B ADDITIONAL RESULTS OF PSEUDO-LABEL MISJUDGMENT AUGMENTATION PROBLEM
Here, we present the details and results of the experiment which are not reported in Scction due to the space constraints.
Experimental setup We first conduct experiments to test the accuracy pseudo label for unla- beled nodes on itaalaimbllncced graphs. ST based on different GNN structures are trained on four node classification benchmark datasets, Cora, CiteSeer, PubMed, Amazon-Compunee the four datasets with a traditional imbalanced distribution following Zhao et al. (2021); Park et al. (2021); Song et al. (2022). The imbalance ratio p between the numbers of most frequent class and the least frequent class is set as 1, 10, 20, 50, 100. We fix architecture as the 2-layer GNN (i.e. GCN (Kipf & Welling, 2016), GAT (Veličković et al., 2017). GraphSAGE (Hamilton et al., 2017)) having 128 hidden dimensions and train models for 2000 epochs. We select the model by the vali- dation accuracy. We test the accuracy of pseudo labels for unlabeled nodes which are newly added the training set, more specifically, separately examine 100 nodes that join the majority class and join the minority class. We repeat each experiment five times and report the average experiment results.
Pscudo-label Misjudgment Augmentation Problem different imbalanced scenarios for ST, the accuracy of the pseudo labels for the unlabeled nodes which are selected into the minority class and the majority class of the training set respectively are reported in Figure 2, 3, 4, and Table 5. We can find that p becomes larger, the accuracy of pseudo labels for unlabeled nodes selected into the minority class becomes lower, in other words, the influence of the bias of the classifier becomes larger. This means that in imbalanced scenario, the pseudo-labels given by the classifier are not credible. Similarly, we also believe that even the pseudo-label of a node accurate, the confidence given by the classifier is skewed, which means that we will also possibly put the low-quality unlabeled nodes into the training set, and neglect high-quality unlabeled nodes. For the unlabeled nodes selected into the majority class, we found that with the increasing degree of imbalance, accuracy of pseudo labels for unlabeled nodes is basically stable at a low level, which also better confirms the bias problem of the classifier. More importantly, regardless of selecting majority class nodes or minority class nodes, UNREAL consistently outperforms ST.
Kecuuayyy 7943
22,2
L1BLL Vier
UNE AL Papc
(a) Cora-GCN
(b) Cora-GAT
(c) Cora-SAGE
Figure 2: The experimental results on Cora under different imbalance scenarios (p 1, 5, 10, 20, 50, 100). We select 100 unlabeled nodes newly added to the training set through ST UNREAL, and evaluate the performance of ST & UNREAL by testing the accuracy (%) with the standard errors of these nodes' pscudo labels. ST-Minor, UNREAL-Minon means that we only test unlabeled nodes that are selected into the minority class, and SL-Major, UNREAL-Major means that we only test unlabeled nodes that are selected into the majority class.
The specific performance of ST ST is a classic technique in sumiviupereised learning to enhance performance and robustness, e.g., Lee et al. (2013). However, have argued and verified above,
14

---

Under review as a conference paper at ICLR 2023
Accumso
31
(oa Side
Insalance Rati
Inielance Natio
Inielance
(a) CiteSeer-GCN
(b) CiteSecr-GAT
(c) CiteSecr-SAGE
Figure The experimental results on CiteSeer under different imbalance scenarios (p= 1,5, 10, 20, 50, 100). We select 100 unlabeled nodes newly added to the training set through ST & UNREAL, and evaluate the performance of ST UNREAL by testing the accuracy (%) with the standard errors of these nodes' pseudo labels. ST-Minor, UNREAL-Minon means that only unlabeled nodes that are selected into the minority class, and SL-MMaor, UNREAL-Major means that we only test unlabeled nodes that are selected into the majority class.
1008 SCA
1008 2C34
Iusalane Rato
Inselanue Ratoo
Intelance
(a) PubMed-GCN
(b) PubMed-GAT
(c) PuhMed-SAGE
Figure 4: The experimental results on PubMed under different imbalance scenarios (p = 1, 10, 20, 50, 100). We select 100 unlabeled nodes newly added to the training set through ST & UNREAL, and evaluate the performance of ST UNREAL by testing the accuracy (%) with the standard errors of these nodes' pseudo labels. ST-Minor, UNREAL-Minol means that only test unlabeled nodes that are selected into the minority class, and SL-Major, UNREAL-Majjr means that we only test unlabeled nodes that selected into the majority class.
15

---

Under review as a conference paper at ICLR 2023
Accumey
Iniatanns Bati
Incalence
Intalance
(a) Computers-GCN
(b) Computers-GAl
(c) Computers-
Figure 5: The experimental results on Amazon-Compune under different imbalance scenarios (p 10, 20, 50, 100). We select 100 unlabeled nodes newly added the training set through ST & UNREAL, and evaluate the performance of ST & UNREAL by testing the accuracy (%) with the standard errors of these nodes' pseudo labels. ST-Minor, UNREAL.-Mnnr means that we only test unlabeled nodes that are selected into the minority class, and SI.-Major, UNREAL-Maajr means that we only test unlabeled nodes that are selected into the majority class.
Table 5: Experimental results of ST and UNREAL on four iaaasiimbllnnced node classification benchmark datasets with p 1, 5, 10, 20, 50, 100. We select 100 unlabeled nodes newly added to the training set through ST & UNREAL, and evaluate the performance of ST & UNREAL by testing the accuracy (%) with the standard errors of the pseudo labels for the seleted nodes, minor means that we only evaluate unlabeled nodes thich are selected into the minority class, and major means that we only evaluate unlabeled nodes which are selected into the majority class. We report average results over 5 repetitions on three representative GNN architectures.
Dataset
PulMed
Amazon Computers
Method
SclC-raininx
UNREAL
Self-Traisink
UNREAL
Training
UNREAL
Sall-
UNREAL
Minisoe)
91.40 = 1.67
92.80 +: 1.30
78.60 1.34
17.20 : 2.55
95.80
1.92
90.20 : 0.44
54.40
1.81
84:00 :: 3,50
Simisor]
87.00
6.59
96.40 2: 4.27
74.00
0.83
77.40 :: 1.20
$7.60
1.67
92.40 2: 1.14
63.60
1.67
82.20 :: 2.16
[[mmnor)
R3.20
1.56
92.20 8 0.85
69.60
1.00
77.50 01
8: 1.29
$2.80
2.20
96.00 0: 3.19
53,00
5.73
80.00 8: 3.46
M[minorr
77.80
1448
59:40 9: 1.39
64:00
0:336
69:40
1.59
7.50
81.00 + 3,69
67:00
5.73
80.00 + 1.51
50entoor)
74.00
1.76
05:00
+ 0.80
1.45 63,80
60:60
72.40
3.84
77.80
1.28
80.20
+ 1.20
64.00
3.75
69
1/04
[00mmsoee
61.20
1.04
77
3.50
0..80
69.20
3.96
76.07
3.17
85:40 + 5.45
60.30
4.40
66:40
3.30
((mejer)
97.00
1.00
79.20
0.01
17.40
98
Stmazar)
78.80
1.92
$1.50
2.58
96.20
1.34
94.20
2.54
3imajor)
14.20
100mater)
1.43
7.43
72.40
Minisor]
93
80.20 0.04
95.00
89.00
Simbsor]
85.80 0.31
91.20
77.00 1.53
76.20
2.62
91.20
86.60
SNeshamr))
1.25 65.80
78.00
78.20
79.80
(mniur)
94.80 0.85
09 20 1.00
75.00 1.58
76-40
1.62
50.50
1.78
96.20
1.64
92.00
1.41
90060 0.50
3(mojor)
95,50 =: 1.22
97.40
2: 2.07
76.40 0.89
73840 =: 1.53
$4.00
3.50
95,00
2: 1.58
92.40
2: 1.89
99.90 1 0.15
[Mnaaorr
95.00
1.00
98.40 1.81
66. 00.60:2
0.54
1.64
$3.40
2:
2.19
95.5 50
5: 0.83
91.40
10.40-11
1.51
99.90 1 0.46
[Kmajor)
95.00
0.56
98.00 3: 1.87
66 20 0.83
10.60
1.96
83.40
2.50
95.3 20
1.64
93.20
1: 1.64
99.90
0.12
SMmajoor
01.40
3:16
97:40
9: 1.81
69
3,62
71 A0
2.19
$2.00
5.70
96. 20
2.58
60-30
0183
99
60
0.54
10tmaser)
90.20 1220=:2: 3.11
94.00 1: 2,70
68.30 5,50
77.20
:: 1.97
94.00 2: 3.51
97.50
2: 1.51
94.50
1.94
99.80 1: 1.64
Himosor]
92.00 0.70
97.80 1.78
$2.20
2.28
76.60 &: 2.40
95.40
3.36
90.00 2: 1.22
90.20
1.45
88.20
2.16
3imisor]
80,80
4.05
92.20
1.32
74.00
1:71 1.71
74,20
&: 1.78
$7.20
3.07
96,00
3 0,50
80.20
1.09
ST.60
1: 1.14
Wistnor
71.40
1.54
78.8 =: 1.82
68.90
1,00
73.20
6 3.29
$4.40
2: 1.79
N2. 2 2.15
64.20
1.45
$5.40 1 4.72
65.40
1.54
$4.20 +
$1
3.16
72.40
3.20
76.20
2.45
K2.60
3.06
73.50
1.30
78:00
+ 1.55
SAOR:
64.00
0.55
94.20 +: 8.04
$3.00
3.65
71,60
3.46
37.50
0.67
NA.
1.81
62.40
4.49
66. 20 2.56
[00mmooee
$0.60 = 1.74
85.40 4: 1.02
$9.60
1.53
73.00
2: 1.87
0.79 75.20
85.20
2: 2.30
63.60
4.82
72.20 0.53
Minujer)
92.20 2.58
78:00 1.02
00330
98.20
93.00
0.71
Mimujar)
0.33
09.00
76.00 2.54
1.58
99.60
[Wmajor)
[[najor)
SWaaaoor]
94.20
for highly imbalanced data, ST is unlikely achieve optimal performance as biased and untrust- worthy predictions may bring low-quality nodes into the training set in the early stage. Our key idea to remedy this is exploit the geometric structural information in the embedding space. In this sec-
16

---

Under review as a conference paper at ICLR 2023
tion, empirically verify the informativeness of geometric structures by comparing UNREAL with pure self frff-training schemes.
Vanile Sefftruining
Vontle frubiing
Setferriing
60
60
40
p=10
2-20
5=50
$=100
p=10
p=
p=50
p=110
p=10
2=
p=
p=100
(a) Cora-GCN
(b) Cora-GAT
(c) Cora-SAGE
Figure 6: The experimental results on Cora under different imbalance scenarios (p = 10, 20, 50, 100). We compare the Fi-score (%) with the standard errors of ST and UNREAL.
seifsraiiing
seiferraiing
URAEAL
UHERAL
0=10
p=20
p=50
p=100
0=10
p=
p=50
p=100
p-10
0-20
p-50
p=100
(a)
CiteSeer-GCN
(b) CiteSeer-GAT
(c) CiteSeer-SAGE
Figure 7: The experimental results on CiteSeer under different imbalance scenarios (p= = 10, 20, 50, 100). We compare the Fl-score (%) with the standard errors of ST and UNREAL.
Vineila
Vaniil
Vaniil
self craining
80
Swif-rriising
60
(a) PubMed-GGa
(b) PubMed-GAT
(c) PubMed-SAGE
Figure 8: The experimental results PubMed under different imbalance scenarios (p 10, 20, 50, 100). We compare the F1-score (%) with the standard emrors of ST and UNREAL.
Results The size of added nodes in each round for each class is hyperparameter, and we tune the hyperparameter based on the accuracy on the validation set. We repeat each experiment five times and report the average experiment results on the node classification benchmark datasets under different imbalance ratios in Figure 6, 7, 8. It can be observed that across different ratios, UN- REAL consistently outperforms self-training by a large margin, and as imbalance ratio increases, the gap of the Fl scores between ST and our method becomes larger. This shows that the data imbalance issue become more severe, the performance of ST degrades more rapidly, which is likely due to noise introduced in early rounds.
17

---

Under review as a conference paper at ICLR 2023
C ADDITIONAL RESULTS IN DIFFERENT SCENARIOS
C.I MORE RESULTS ON HIGHER IMBALANCE RATIOS
In this section, we show the performance of UNREAL in highly-imballnned scenarios by construct- 50, 100 on the benchmark datasets which is not presented in the main
ing training sets with paper. The results are presented in Table 6 and Table 7. We can find that our model is more robust on highly-imbali imbalanced datasets with different architectures, namely GCN (Kipf & Welling, 2016), GAT (Veličković et al., 2017), GraphSAGE (Hamilton et al., 2017)). is shown that UNREAL can deal with different degrees of imbalance, and significantly outperforms other methods with large margin. We observe from the Table and Table that the performance of of GraphENNS (also GraphENS+TAM) degrades noticeably scenarios, synthesizing or duplicating huge amounts of nodes based on rare minority nodes in the training set is prone overfitting of minority classes. On the other hand, BalancedSoftmax- achieves an overall better performance than GraphENS+TAM those highly imbalanced scenarios.
highly-imbalancce datasets. In highly imbalanced
C.2 RESULTS ON FLICKR
The Flickr is naturally imbalanced and the training set in the public split is also imbalanced, so we directly evaluate the performance of all methods on the public split (Zeng et al., 2019). The results presented in Table 8.
D ADDITIONAL ANALYSIS FOR EACH COMPONENTS OF UNREAL
D.1 ADDITIONAL ANALYSIS FOR DPAM
In this section, we analyze why DPAM works. DPAM conducts an unsupervised algorithm to obtain pseudo-labels for each unlabeled node in the embedding space, and finally only unlabeled nodes whose pseudo-labels and classifier's predictions are aligned are put into the candidate pool, which effectively circumvents the bias problem of the classifier, such as pseudo-label misjudgment of unla- beled nodes, selecting tow-quality nodes into training set based on the skewed condidence rankings. To quantify the performance of DPAM, we conduct the novel experiments below.
Experimental setup We use DPAM filter the unlabeled nodes of the whole graph, and test the accuracy of pseudo-labels (prediction of the classifier) of the aligned node set Uin and the dis- carded node set Mout respectively. DPAM based on different GNN structures are trained on two node classification benchmark datasets, Cora, Amazon-Computt
We process the two dataset with tra- ditional imbalanced distribution following Zhao et al. (2021); Park al. (2021); Song et al. (2022). The imbalance ratio p between the numbers of the most frequent class and the least frequent class is set as 5,5, 10, 20, 50, 100. We fix architecture as the 2-layer GNN (i.e. GCN(Kipf & Welling, 2016), GAT(Veličkovä et al., 2017), GraphSAGE(Hamillon
et al., 2017)) having 128 hidden dimensions and train models for 2000 epochs. We select the model by the validation accuracy. We observe the accuracy of pseudo labels for unlabeled nodes which are filtered out and absorbed into by DPAM respectively. We repeat each experiment five times and present the average experiment results.
Result DPAM divides the unlabeled nodes of the whole graph into two parts, Min Mout- We verify the effect of DPAM by testing the accuracy of pseudo-labels for these two parts of nodes. We can observe that the accuracy of pseudo-labels for U4,, and Hout differ greatly in different imbalanced scenarios. Usually the pseudo-label accuracy of 24,, is high and the pseudo-labe accuracy of Mout is lower, which means the effectiveness of DPAM. We can also observe that as p increases. the accuracy of both decreases, which also reflects the model bias caused by the imbalanced label distribution.
D.2 ADDITIONAL ANALYSIS FOR
AND DGI
In this section, we analyze why Node- Reordering and DGI works. With DPAM, we filter out large part of untrustworthy nodes, and get pool of candidate nodes. We try to carefully hunt for part of high-quality nodes in the pool to add to the training set, which involves a priority issue. As we mentioned before, we have already verified in Section 3 that the prediction and confidence given by
18

---

Under review as a conference paper at ICLR 2023
Table 6: Experimental results of our method UNREAL and other baselines on four class-imbalances node classification benchmark datasets with p= 50. We report averaged balanced accuracy (b)c..%) and Fl Fl-score (%) with the standard errors over 5 repetitions on three representative GNN architectures.
Datasel
PulMec
Amsznn-Cnguuienn
Imbalunce Ratlo
bdee.
Mec.
F1
Vanilla
5181 a 0.62
43.95
1,20
37.59 = 0.17
23.54
2:
61.65 1: 0.34
47.95
2: 0.50
17.36 1: 3.41
69.68
3:12
Re-Weight
3854 4.33
54.1 13
3:30
36.10-1
1.28
27.43 1.34
65.70 + 1.50
56.15-1
44336
79.10
2.44
71:40-1
2:56
PC Serhmas
44877+2.33
62.01
1.14
42.41
2.19
38.83
1..3--170
49.21
0.500
69:40
0.87
81.90
1.63
74.34-1
+.13
BelancalSedems
1.55
6::00
47.62
1.11
46.55
1.46
70.40 + 1.00
69.04
0.56
82:97
+.053
73.74
1.27
Renals
62222 1.76
2.225
40.23
= 1.66
33.66 = 2.69
68.67 + 1.21
63.05
1.47
81.71 2:09
72:55
1.61
GrapatzNs
63477 0:68
62:21
1:45
08.13
1.58
41.01
2.34
09
6- 2.55
64:30 3:51
81.63
2.35
72.1 2:38
InlincalsefmmeeTAM
6857 1.58
67.25
1:20
53.61
S1.74
77.20
1.45
24.86 0.0.
81:34
73.85
41.07
09
04:00
80.55
7233
GNsp TAM
6505
62.11
45.07
69.74
70.52 0.63
81.69
72.09
UNREAL
75662
A
+7.05
+5.34
+6.92
+1.35
+1.86
+2.57
+1,91
Vanillu
4:.00:000:63
45.53
36.65
23.68
60.16
0.47
72:42
Weight
56,09
2:31
66.27
0.68
73.46
SoChma
29.44:1:2.2
58.05
70.56
77.21
64.71
62.55
70.94
1.09
17.49
2.33
Raval:
+..1++1.72
60 2.36
41.60
2:30
53.54
4.60
70.35
1.36
67.45
0.01
12.39
2.75
65.23 3.35
GrajiENS
6-.5
61.41 +:115
45.23
41.12
4:23
60.66
1.01
66.33
+
76.36 2.74
70.44
2.51
BelancaBeddmss
1:.0
66.07
1:14
54.25
= 0.79
52.77
0.97
75.65
1.11
74.02
+
78.86
6: 1.53
70.71
2.04
Renode-TAM TAM
06:00:1: 1.83
63.
2.53
43.54
1.56
35,80
2.43
71.23
2.04
06.01
2:4.31
76.07
8: 2.70
08.03
2.68
GrapLENS-TAM
05:35-12.00 2.67
65
34
2.53
48.00
1.46
48.14
1:43
71
50.50
1.26
72.58
1,07
9000
8 0.3.2
72.95
7.47
UNREAL
77.07 1 0.83
73:44
21 1/05
57,70
4.35
56.81
4.67
79.1
1: 0.29
77.38 1: 0.39
$6.06 31 0.45
77.55 L 0.71
+7.37
+3.76
Vanillo
53.02 3 0.83
45.58
1:30
38.81
=: 0.89
25.28
0.51
61.41 1: 1.01
50.46
2.47
56.53
#: 2.12
48.52 1: 2.75
Rs. Weight
35.05 4 0.81
54.32
0.59
38,0 09
1.34
30.41
1.82
62.4
0,.00
51.37
2.82
70.35 00.35.
2.21
61.52
2.73
Soclma
62.33
1:58
41.70
1.09
0.95
73.53
3:39
Belancaloodmmx
64.77 0.77
41.84
73.27
Renode
6135
40.37
67.54
5:30
70.46
GrIpENS
0:95
41.99
37.44
66.07
61.63
76.21
2.56
Bulneca TAMM
Rendk-TAM
74.55
GrypENS-TAM
64.84
1.13
80.75
0:00
UNRRAL
76.04 + 1,30
72.99 1,25
58.70 4.10
57.53
4.89
75.27
1,26
72.86 1,50
82,03
0.77
72.98 0.52
A
+18.06
+7.46
+5.81
+7.11
+283
-1.57
+1.28
+0.67
Table 7: Experimental results of our method UNREAL and other baselines on four class-iballanced node classification benchmark datasets with = 100. We report averaged balanced accuracy (bAcc.%) and F1-score (%) with the standard errors over 5 repetitions three representative GNN architectures.
C'inpattes
Imbnlance Rotio
bAcc
bAcc.
bAct:
MAo.
Vanalla
51.02
0120
43.91
2: 0.25
30,85
0.25
24.71
4: 0.25
61
0.12
47.55
2: 0.16
76.09
3.79
69.32
3:49
Ri-Weighht
50.11
1.06
$4.04
= 1.36
42,67
2.06
33.17
2 1.40
67.14
2.71
55.24
2 5.36
81.53
2.20
71,45
2.05
PC Scelma
63.75
1.02
61.19
= 1.43
38.34
0.71
33
4: 1.42
30.85
0.44
70.26
2 0.63
82.23
1.39
72.34
2.52
BilaneeSSolmax
63.03
1 1.57
61.28
1.77
48.40
1.20
46.59
2: 1.34
70.77
1.68
68.88
1.74
83,33
3.35
74.34
2.74
Reaode
00.76
2.53
58.09
2 3.00
43.1=2007
33,69
2: 2.76
67.63
2.77
61.70
- 4.84
82.13
1.73
71.79
0: 1.85
CrspaENS
1:90
2.06
10:33
1.00
83.57
2.17
BolinealSo ToMaacTTMMM
0.50
$1.21
73.75
73.72
2.17
75.50
Renale+
0.75
64.35
75.00
GrsphENS-
57.77
39.40
72.50
$1.29
1.52
71.66
UNREAL
3.55
69.12
56.50
76.03
84.30
0.30
76.06
A
+3.33
+2.62
+5.86
+8.29
+5.00
+2.31
+0.60
+0.07
0.32
43.37
0.25
47.39
72.66
2.97
Re Weight
1.55
2.69 69
77.10
3.26
Sormas
2.01
59.76
79.72
1.52
InloncedSottmx
1:35
61.00
1.46
2.11
43.38
2.06
Renal:
62044:22
53.04
5 2.66
43,40
2.07
34,09
2 0.04
68.54
19.5442233 2.11
65.63
3.15
75.34
1.65
60.99
1660
GrapEES
63.93 2:70
61.77
2: 3.38
44,43
1.90
39.26
2.55
68.30
1.51
64.14
3.25
$1.63
2.08
71.20
2.75
BalnccddodmaaeTii TAM
61.96 3.23
62.91
3.96
$2.75
1.29
50,69 6 1.83
1
0.77
22:45
$0.86
2.52
72.93
4 2.5
Renode TAM
0345 0 1.41
61.51
- 1.95
$1.55
1.59
36.15
0 2.57
11.5511333
08.11
2 4.28
75.60
1.50
70.35
4 2.80
GraplENS- TAM
62.52 0.95
61.65
+ 1.19
45.79
1.31
44,90 + 1.14
69.09
+
1.11
70
+ 1.10
83.53
0.53
72.81
+1 1.95
UNREAT
0.91
71,50
0.89
1.87
59.63
1.86
77.88
1.M
74.98
85.33
0.19
75.83
Vanilla Ke- Weight
52.55 0.24
43.79
01:47
36.53
0.09
24.12 3: 0LEN
62 29
0.25
41.02 3. 0.38
55.94
2.37
45.21
275
59.62 2.3.6
55.26
4.40
16.24
1.30
27
63.35
0.75
55
1.62
20.26
3.35
61.09
3.30
IC Softmae
64:01
09:14
1.68
1.41
37.11
1.00
12.62
1.40
90.5
1:30
75.06
2.46
09.10
2.00
BilancedSoOmm
2:12
62.50
0.92
69.15
74.66
0.56
06.23
Renode
60:08
30.13
67.11
1.12
73.73
2.26
GripLES
16.71
72.83
64.56
3.06
78.01
Rendes
00.72
05
1.01
74.81
3.29
GuypEES- TAM
2.25
1.01
1.08
UNREAL
73.47
231
68.30 211
91.77
2.98
58,92 4: 3,07
77.11
0.39
74.33 :: 6,81
K2.9 4: 2.94
73.11 257
A
+6.89
-3.74
+6.44
+R.33
+3.33
+1.99
+1.20
+0.25
19

---

Under review as a conference paper at ICLR 2023
Table 8: Experimental results of our method UNREAL and other baselines on Flickr. We report averaged balanced accuracy (bAce.,%) %) and Fi-score (%) with the standard errors over 5 repetitions on three representative GNN architectures.
Dataset (Flickr)
GCN
GAT
SAGE
Ratio( 10.80)
bAce.
Cross Entropy
24.62
0.07
24.53 = 0.11
25.87
+0.30
25.32
0.44
25.29
0.18
24.16 = 0.27
Re-Weight
28.31
1.64
24.06
30.66 0.76
27.12
0.34
27.39
1.84
22.62
PC Softmax
29.21 2.16
25.81 + 1.75
30.20
0.46
27.24
0.37
25.40
2.49
21.08
1.73
BalancedSotimax
27.61
23.70 0.77
26.01 2.81
23,50
3,07
2.10
24.98 +
GrphSMMTE
00M
0OM
OOM
0OM
0OM
OOM
GraphENS
OOM
COM
OOM
OOM
OOM
OOM
BalanceSSofmax-
0.99 OOM
Renode-TAM
OUM
0OM
0OM
OOM
OOM
GraphENS-TAM
UNREAL
30.76
0.27
30.60 1 0.29
29.45 0,72
28.21 0.76
53.68
0.63
54,01
1.34
+1.55
+0.97
Cora 6Ch 101
Chrese
Galnaed
Cllmaod
aa)
Figure 9: An claboration Geometric Imbalance and DGI, we use T-SNE to visualize the all embeddings of nodes in the training set and the part of embeddings of unlabeled nodes.
20

---

Under review as a conference paper at ICLR 2023
Table 9: Experimental results of DPAM effectiveness on Cora with p p= 1, 5, 10, 20, 50, 100. We observe the accuracy (%) of the pscudo-label (prediction of the classifier) of the aligned node set in and the discarded node set Hout respectively. We report averaged results with the standard errors over 5 repetitions on three representative GNN architectures. All, Labeled, Unlabeled represent the size of whole nodes, labeled nodes, and unlabeled nodes on the graph. Align, Out, Align-True, Out- Ture represent the size of Um, Mout, nodes with accurate pseudo-labels of Min. Mous respectively.
Dutasset
All
Labled
Unlabled
Align
Align True
Accorncy(%)
Out
Out True
Aucumeyr9)
2708
1400
2568
2072.00
10.29
1391.00
22.56
67.11 1 1.17
496.00
10:29
233 33,80
16.66
47.87 3.74
2708
92
2616
2122 80
18.93
1392,00
54.21
65.58
2: 1.57
493
18.73
196.80
13:08
37.86
1.75
30
2708
86
26:22
2134.00
=: 23.42
1326.40
24.25
62.14
1: 1.67
487.40
25:43
151.00
18:24
37.32
=: 3.13
20
2708
83
3625
3149.60
17.63
1310,20
+ 96.72
60.97
+ 3.50
475 40
17667
169 000.0-13
21:47
35.64
- 3.44
50
2708
203
2515
1860.00 80
31.15
1059.40
58.77
56,90
2.62
644
31.14
225
80
10:70
35.05
3.79
100
2708
403
2305
1820.40
12:42
1001.60
21.60
$5,02
3.99
484.60
23.99
151.40
20.74
31.78
2.37
2708
2508
3072.00
37.38
14122.0
57.31
1.41
496-0M
11:37
2708
2616
40
1433.00
59.87
66,90
2.09
474
41.02
30
2708
26222
2132.60
=2 29.94
1377,40
49.61
64.58
1.60
489.40
29.95
185,
12.28
37,97
1.13
2708
83
2625
2150.60
37.35
1341,60
54.17
62.16
1.64
462
33.28
178.00
5.05
38,60
2.12
2708
140
2568
1892 401
= 37.38
1060 80
51,86
1.52 53.66
57,52
612.60
-3.337
271.20 =:: 6.30
44.35
1.86
2708
403
2305
1934 60 = 19.65
1038 20
21.06
0.83
370.
37.11
147,53- +: 3.70
39.83
1.36
2708
2568
1944.00 25.77
973,
52.26
51.27
3.36
624.00
257.00 13.28
36.11
2708
20014.00 40 35.50
1008
22.53
51.80
611.60
35.50
203,80
7.15
33.40
1885
2708
29-1
32.48
1039.00
50,89
580 40
32.48
189.20
2.35
32.50
2706
1002.20
30.95
2706
33,87
300
2708
1859000 192.42
914.41 23.65
49.36 2.59
446.00
21.24
138.87
6.32
31.15
2.43
Table 10: Experimental results of DPAM effectiveness on Amazon-Computers with
P = 1,5, 10, 20, 50, 100. We observe the accuracy (%) of the pseudo-label (prediction of the classi- fier) of the aligned node set Uin and the discarded node set Vout respectively. We report averaged results with the standard errors over 5 repetitions Labeled, Unlabeled represent the size of whole nodes, labeled nodes, and unlabeled nodes on the graph. Align, Out, Align-True, Out-Ture represent the size of Min. Mout, nodes with accurate lseudo-labels of Uin Mout respectively.
three representative GNN architectures. All,
Dataset
Labled
Unlibled
Align
Aligu-True
Accoracy(16
Out-True
Accumcy(9)
13752
13552
11977
108.09
93.
50,08
3.07
1554.40
05.25
676,60
141.11
43.58
2,83
13632
11595.60
57.32
79.06
2508
173.54
544.40
66.26
30.74
9,09
13612
11522,40
55.48
1807.60
27:24
4.30
13752
13647
11566.00
8698.22 20
73.40
1750.40
521.00
60.76
29.20
50
13497
11543.20
168.20
8994.00
75,94
0.75
1653.80
138.11 4068.00
474.20 5.0772
28.68
13347
9159.00
192.42
7352.90 +
81.41
4.59
1129:60 75.74
28.67
4.77
13752
200
13552
12008.00
1 101.93
998-1.20 1. 308.03
83.44
4.13
1544.80
101.94
$80.10
190.49
43.33
1.32
13752
120
13632
11570..0
136.11
8715.00 + 96.35
75,33
1154
2066 20 136.13
477.00
= 97.00
25.39
1.35
GAT
111
13752
110
13642
8947.000
13.40
6680.40
177.54
75,85
6.07
4694.60
134.74
591.00 :: 13.74
15:94
2.97
20
13752
105
13647
10145.50
$8.00
7300.80
64.89
71,42
1.50
3401 20 + 29.76
370.60
+ 41.67
18.52
0.09
50
13752
255
13197
10L33.60
31.55
7772.00
155.87
77.17
2,85
3363.40
1 10.42
457.20 108.19
19.28
1.43
13752
505
13247
11377.00
63.32
9122.20 1 70
$0.46
1.01
1910,00 1 63.32
458.20 1 41.04
24.78
2.04
13552
10815.20
7131.40 + 72.83
66.94
11.28
2736.
$6,50
965.40
35.36
1.31
p=
13750
170
13612
10627.50 50 : 78.33
6728.00 00 :: 53.24
63.25
0.36
3004.20
+: 78.03
978.30
59 91
32.55
1.49
10
13752
110
13642
10475.00
1: 118.41
6015.00 1: 41.14
57,43
4.01
3167.00 4: 15.41
1064.40
52.71
33.59
6.23
SMGR
20
13752
105
13647
10653.20 J. $7.35
5998, 80 1. 69.35
$6.30
4.01
2993.80
80 1. $7.35
386.20
1. 73.25
29.57
1.77
13752
255
13497
11044.30
+ 129. 14
6760.
80 + 50
61.22
3.42
2442.20
+ 23.48
879100
+ 91 45
35.71
1.78
100
13753
505
13247
9175.20
1 32.53
6475.80
1: 80.88
72.07
1.96
4071
80
1 32.63
1218.60
14.70
34.43
1.08
the classifier are biased, resulting in low accuracy of the pseudo-labels for nodes selected by ST in highly imbalanced scenarios. We can get the geometric ranking according to the distance between the unlabeled nodes and the class centers in the embedding space. Considering the influence of classifier bias on confidence ranking, we believe that geometric ranking is more credible in the early rounds. At the same time, we take into account the suboptimal nature of the unsupervised algorithm. We believe that with the rounds of UNREAL increases, the label distribution of the training set is gradually balanced, and the confidence given by the classifier is more reliable. Node-reordering considers both geometric ranking and confidence ranking, specifically, obtain the similarity between them to get weight to reorder the priority of the nodes. To quantify the performance of Node- Reordering and DGI, we conduct the novel experiments below.
Experimental setup We conduct experiments to test the accuracy of pseudo labels for unlabeled nodes on class-imallnneed graphs. All model combinations based on different GNN structures are trained on two node classification benchmark datasets, Cora, two dataset with a traditional imbalanced distribution following Zhao et al. (2021); Park et al. (2021); Song et al. (2022). The imbalance ratio p between the numbers of the most frequent class and the
We process the
21

---

Under review as a conference paper at ICLR 2023
least frequent class is set 1, 5, 10, 20, 50, 100. We fix architecture the 2-layer GNN (i.e. GCN(Kipf Welling, 2016), GeT(Veličkovié et al.. 2017), GraphSAGE(Hamittnn et al., 2017)) having 128 hidden dimensions and train models for 2000 epochs. We select the model by the valida- tion accuracy. We observe the accuracy of pseudo labels for unlabeled nodes which are newly added the minority class of training set. We repeat each experiment five times and present the average experiment results.
Num
Thrashaic
(a) Sensitivity performance K-Means
(b) Sensitivity performance the threshold y of DGI
Figure 10:
Sensitivity analysis on Cora based on GCN, The two images show the performance change as clusters' size k of K-Means and the threshold y of DGI increases respectively.
Result As shown in Table 11 and Table 12, we verify the effectiveness of each component of UNREAL by testing the accuracy of the nodes' pseudo-labels selected by different model com- binations, DPAM+Confidence ranking(with or without DGI), DPAM+Geometric ranking(win) (wtth or without DGI), imbalanced scenarios, each component UNREAL (Node-reoddering & DGI) plays an important role, and the performance outperforms the other model combinations significantly.
without DGI). It can be observed that in different
E HYPERPARAMETER SENSITIVITY ANALYSIS OF UNREAL
We investigate the sensitivity of performance to clusters' size k' of K-Means algorithm and the threshold 7 of DGI Figure 10. We observe the performance gradually stabilize when k have extremely high values, on the other hand, when k is extremely low values, the performance of UN- REAL drops largely. We believe that when k is too small, the pseudo-labels given by unsupervised algorithms will have extremely low values. We believe this is because that the DGI screening is too strict, which will lead the loss of some high-quality nodes. On the other hand, extremely large y will introduce many noise into the training set.
errors. Also, observe the performance gradually stabilize when y have
F DETAILS OF THE EXPERIMENTAL SETUP
Here, we introduce the method of imbalanced datasets construction, evaluation protocol, and the details of our algorithm and baseline methods.
F.I IMBALANCED DATASETS CONSTRUCTION
The detailed descriptions of the datasets are shown in Table 13. For each citation dataset, for p 10, 20, we follow the "public" split, and randomly convert minority class nodes to unlabeled nodes until the dataset reaches imbalanced ratio p. For class in the public split training set, we choose randomly selected nodes as training samples, and for validation and test sets still follow the public split. For the co-purchased networks Amazon- Computers, we randomly select nodes as training set in each replicated experiment, and construct random validation with 30 nodes in each class, and treat the remaining nodes testing set.
50, 100, since there are not enough nodes per
22

---

Under review as a conference paper at ICLR 2023
Analyzed experimental results of Mode-Reordering and DGI on Cora with 1,5, 10, 20, 50, 100. We select 100 unlabeled nodes newly added to the minority class of train- ing set through different method combinations, and evaluate the validity of cooddeccgd & DGI by testing the accuracy (%) with the standard errors of the pscudo labels for these nodes. We report averaged results over 5 repetitions on three representative GNN architectures.
Table 11:
Dataset
Inbalance Ratio
10
20
50
1000
Coulideee Ranking
61.40 = 2.75
62.40
2:59
60:20 = 1.02
58.40
1.05
57.60 =: 1.86
58.40
2.15
DBAM:
Goommtt Ratking
64.00
3.67
61.20
2.89
61.20
2: 2.54
63:60
1.31
55.60
2: 2.31
47.80
2.87
D Recedering
89.65
5.25
86.98
0.21
58.32
= 0.83
85.32
2.88
50.87
2: 2.31
71.60
2.91
MeAMi-Cohheence Ranking-DGG DGG
71.00
5.47
75,40
2.15
08.20
2: 1.24
09.40
1.28
67.80
22 2.75
06.60
0.16
Gromarra: Rankinp-DDi
60:60
5.78
1.01 $9,40
57.00
69:00
1:71
02.80
1.30
96.40
92.20
93,00
77.80
2.50
DPAM-Conlidmne Ranking
61.60
4.26
64.00
2.07
62.50
3.47
$7.50
1.63
58.20 +: 1.00
60.60
0.79
DeAM--Gemmry: Ranking
64.00
2.78
67,80
3.75
00:00
4.30
52.00
1.00
66.20 2: 2.58
40.80
2.83
D9MMM-Node--e Kecedoring
91.19
0.25
00:65
5.76
64.32
3.45
58.34
0.23
90.32
0.63
75 34
1.54
D99MM4Conhdenn BankingeD00
09 80
2.77
72.80
3.94
1.13
67:60
1.59
71.60
06
1:14
(orm-rr Rankin-400
71.60
24.00-
1.63 90.40
7.17
68.00
62.00
DRAMI+Node Row.detnug-GG/UNNNRBEEEE
M3,90
90,00
9.93
94,60
78.20
2.47
DRNM: Contidence Ratking
$4,80 = 4.56
53.00
2.45
$1.50
1.97
43.00
2.57
46.20 2: 0.53
41.60 1.14
DPAM-
Geomers:: Ranking
33,00 = 2.78
65,40
1.75
40.00 = 0.26
$2.60
2.07
47.40 1: 4.27
41.00
2.64
90.69
0.36
16.45
2.43
75.34
76.43
Confidence Ranking-DGi
66.20
63.30
60.60
57.40
2.26
Geometrk: Ranking-DDi
61.60:3.71 3.71
5:21
$4.00
63.00
NoPe Reordeetog Rorderdugg-DGUUNNEALL
07.80 1.78
92,20
90,80
94.20
$5.40
1.02
Table 12: Analyzed experimental results of Nodd-Reog and DGI on Amazon-Computte
with p = 5, 10, 20, 50, 100. We select 100 unlabeled nodes newly added to the minority class of training set through different method combinations, and evaluate the validity of Node-Reorded DGI by testing the accuracy (%) with the standard errors of the pseudo labels for these nodes. We report averaged results over 5 repetitions on three representative GNN architectures.
&
Datavel
AumonnCompiiss
Inhuabnee Ratio En]
p- 90
p- 50
100
ConfidConfience Ranking
25:40
2.50
20.20
3.03
68:20
4:20 63600
2.30
61.40
1.51
MRMM--Grmmrrrs Ranking
26.00
1.41
24.00
4.71
1.20
68
1:08
83.80
70:00
78.20
65.00
66000
2.60
Confidence DDG
76.40
75.30
66:20
62.80
59
1:30
GooMeniommeicc Rankin--GG
75.20
DPAMI-Node-Ron Rerliooee-Rooreeeng-------
84.09
1.55
D9MM- Contidence Ranking
84.00
2.40
29.200
1.76
73.00
2.12
14.80
2.16
00.00 8: 1:13
08.60 1,40
Grometri: Ranking
86.00
2.01
70,80
DeAMoNNdde-BB Recndering
87.40
50:40
79,00
3.67
75,00
73.40
2.52
Confidence Ratking
84.20
2.07
76.40
76.00
2.54
06.00
72.00
L.54
D9AM Gromericc Ranknn--DG
77.80
71.60
69,00
DPAMM-Nudo- Mur---innddRRttleeinnn----- Dew.eeerinn---UUUNRRRRRR.
3,00
DPMM Conlidenc Ranking
85.
3.38
77 0.89
61.00
65 2.65
Gromatri Ranking
86.00
0.70
2.16
61
Kecnderin
86.00
1.00
Danking-DDG
Table 13: Summary of the datasets used in our experiments.
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
Caazzon-Comuuters
13,752
491.722
10
Flickr
89,250
899,756
500
7
23

---

Under review as a conference paper at ICLR 2023
For Flickr, we follow the dataset split from Zeng et al. (2019). The details of label distribution in training set of the five imbalanced benchmark datasets are in Table 14, and the label distribution of full graph is provided in Table 15.
F.2 DETAILS OF GNNS
We evaluate our method with three classic GNN architectures, namely GCN (Kipf & Welling, 2016), GAT (Veličković et al., 2017), and GraphSAGE (Hamilton et al., 2017). GNN consists of L 1, 3 layers and each GNN layer is followed by BatchNorm layer (momentum=0.99) and a PRelu activation (He al., 2015). For GAT, we adopt multi-head attention with heads. We search for the best model on the validation set. The choices of hidden unit size for each layer are 64, 128, 256.
F.3 EVALUATION PROTOCOL
We adopt Adam (Kingma & Ba, 2014) optimizer with initial learning rate 0.01 or 0.005. We follow (Song et al., 2022) devise scheduler, which cuts the learning rate by half if there is no decrease on validation loss for 100 consecutive epochs. All learnable parameters in the model adopt weight decay with rate 0.0005. For the first training iteration, we train the model for 200 epochs using the original training set for Cora, CiteSeer, PubMed or Amazon- Amazon-Compunn Computers. For Flickr, we train for 2000 epochs in the first iteration. We train models for 2000 epochs in the rest of the iteration with the above optimizer and scheduler. The best models are selected based on validation accuracy. Early stopping used with patience set to 300.
F.4 IMPLEMENTATION DETAILS
In UNREAL, employ the vanilla K-means algorithm as the unsupervised clustering method. The number of clusters K is chosen from (100, 300, 500, 700, 900} for Cora, CiteSeer, PubMed and Computers.. For Flickr, K is selected among {1000, 2000, 3000, 5000). For Cora, CiteSeer, PubMed, and Mmazzon-Computers the number of training round T is tuned among {40, 60, 80, 100). For Flickr, T' is tuned among (40, 50, 60, 70). We also introduce hyperparameter a. which the upper bound on the number of nodes being added per class per round. The tuning range of a is Amazon-Computee
(4, 6, 8, 10} for Cora, CiteSeer, value of is selected among {30, 40, 50, 60). The weight parameters in RBO is selected among {0.5, 0.75, 0.98). and the threshold in DGI is tuned among (0.25, 0.5, 0.75, 1.00]. For Flickr, we only add minority nodes the training set in all iterations, which means that set 0 for majority classes in Flickr.
and {64, 72, 80} for PubMed. For Flickr the
F.5 BASELINES
For GraphSMOTE (Zhao et al., 2021), we use the branched algorithms whose edge predictions are siscret-vvauee. which have achieved superior performance over other variants in most exper- iments. For the ReNode method (Chen al.. 2021), we search hyperparameters among lower bound of cosine annealing Wminn E {0.25, 0.5, 0.75) and upper bound of the cosine annealing Wmax E (1.25, 1.5, 1.75) following Chen al. (2021). PageRank teleport probability is fixed as == 0.15, which is the default setting in the released codes. For TAM (Song et al., 2022), search the best hyperparameters among the coefficient of ACM term a E {1.25, 1.5, 1.75J, the coeffi- cient of ADM term 10.125, 0.25, 0.5), and the minimum temperature of class-wise temperature E {0.8, 1.2) following Song et al. (2022). The sensitivity to imbalance ratio of class-wise tem- perature is fixed 0.4 for all main experiments. Following (Song al., 2022), we adopt warmup for 5 iterations since we utilize model prediction for unlabeled nodes.
F.6 CONFIGURATION
All the algorithms and models are implemented in Python and PyTorch Geometric. Experiments are conducted on a server with an NVIDIA 3090 GPU (24 GB memory) and an Intel(R) Xeon(R) Silver 4210R CPU 2.40GHz.
24

---

Under review as a conference paper at ICLR 2023
Table 14: Label distributions in the training sets
C3
Cora (jm10)
20
20%)
(25
(23 (23.26%)
20
(23.26%)
(21.26%)
Corn ()=20)
(21 10%)
20
(24.10%)
(24.100)
(24.10%)
20
(1.19%)
(1.19%)
(1.19%)
Cora (x=50)
(24.65%)
90
(24.639)
(24.69)
50
(0.40%)
(0.40%)
(0.49%%
Cora (x=100)
(21.81%)
100
(24.819)
(24.8195)
(24.819))
(0.25%)
(0.255)
(0.2555)
CiteSerr (j=10)
(30,3055)
20
(30.500))
20
(30. (0.5000)
20
(30.50%)
(3.05%)
2
(3.055)
(p=20)
75%))
(31.759))
(31.15%)
(1.50%
(1.00%
(1.60%)
CitcSeer (p=50)
(32 6896)
50
(32.88%)
50
(32.98%)
50
(166%)
(0.05%)
1
(0.65%)
(33.0006)
(33.006))
(1.33%)
(0.37%)
(0.3855)
PubMed (jm10)
(47 62%))
20
(47.627))
(4.76%)
PubMed (j-20)
PubMed (n-50)
(49.00%)
(49.30%%
(0.99%5)
PubMed (p=100)
(49.75%)
100
(49.75%)
100
(0 (0.50%)
Cmaoon-Computerr (y100)
(18. 189)
(18.18%)
(18.18%)
(18.18%)
(18. (85))
20
(L.82%)
(1.82%)
(1.82%)
(1.82%)
(1.825)
Ainzon-Computers (jm20)
(19.05%)
20
(19.05%)
20
(19.05%)
20
(19.1%%)
20
(19.05))
20
(0.96%)
(0.95%)
(0.95%)
(0.00%)
(0.95%)
AmmonnComputers.coom. (j=50)
(19.61%)
(19.61%)
(19.8196)
(19.11%)
(19.61%)
(0.80%)
(0.3095)
(0.89%)
(0.00%)
Monzon-Compuczsseeee (p=100)
(19.80 (19.90%%)
100
(19.80%)
100
(19.80%)
100
(19.80%)
100
(19.80%)
100
(0.20%)
(0.20%)
(0.2095)
(0.2055)
(0.2015)
2628
2431
11525
1742
18814
(8.88%)
Table 15: Label distributions on the whole graphs
Dataset
Co
C
C2
C3
C,
Cs
C
C,
Cx
Ca
Cora
351
217
418
818
426
298
180
CiteSeer
264
590
668
701
696
508
PubMed
4103
7739
7835
Amazon-Coue Compute-s
436
2142
1414
542
5158
308
487
818
2156
291
Flickr
5264
8506
6413
4903
22966
3479
37719
25

---

Under review as a conference paper at ICLR 2023
G MAIN ALGORITHM
Algorithm UNREAL
Input: Imbalanced dataset (g (V. Co). y). feature matrix X, adjacency matrix A, unlabeled set 41 = = Lo, rounds 7 to select nodes, the size threshold a of nodes being added in each RBO, threshold y of DGI, learning rate r, the size k' of the clusters, GNN model fg. clustering algorithm feluster, and the mean function M-).
class per round, weight hyperparameter
1:
for i = 0 to round T do
2: Train fg based the current training set L; (C1....,,a.) ,.).
3: Obtain node embedding matrix of the labeled node set and unlabeled node set H² Bl _1 E xd prediction and confidence from classifier.
4:
% Step Dual Pseudo-tag Alignment Mechanism(DPAMM)
5:
feluster H
{K1, C2, c = M (th Yu E C.))
KK, Ck')
6:
7:
Assign label Im to each cluster Km Dm arg min, distance(cfrain C.m).
8:
Combine clusters with the same pseudo-label Umn and 2 U Um.
9:
Put unlabeled nodes whose prediction in i is m into the set Um. and U U Um-
% Step 2: Node-reordering
For each u E Um N 6w distance (h Cm
12:
Obtain geometric rankings {SI, ... S based on o; and confidence rankings
based on r. For each m, N.New max(rm: 1 rm Sm + minfrms 1- - rm Tm-
(71, T.. T
13:
Select nodes based on the rank of their values in N
15:
% Step 3: 3:Discarding geometrically imbalanced nodes (DGI)
Obtain the distance between the embedding of and the second closest center to as Bus
compute GI index node u as Bu-bu.
6n
if 3-- -u du <y then Discard node
18:
19:
else
20: Select it to training set.
21:
end if
Update the training set L.
23:
end for
26


Reviews:
[{"review_id": "jXu1ya9zil", "reviewer": "Reviewer_fiXK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "To address imbalanced label distributions in node classification tasks, the author suggested an over-sampling-based technique. To obtain unlabelled nodes rather than artificial ones, it uses unsupervised approaches in the embedding space. Additionally, new samples are simultaneously chosen using geometric confidence rankings.", "summary_of_the_review": "Model effectiveness validated in this work when competing with recent baselines. However, the contribution of this work may be over-claimed. Results of some experiments need to be further clarified. Some key points have not been validated.", "strength_and_weaknesses": "Pros:\n\n1.\tSome recent baselines are considered as compared methods in evaluation.\n2.\tThe results of the main experiment also show the effectiveness of the model. \n3.\tThe author's ablation experiments are conducted by arranging and combining \"Confidence ranking\", \"Geometric ranking\", \"Node reordering\" and \"DGI\" four modules on different datasets and encoders.\n4.\tExperiments in Sec 4.2 show the ability of the new model to handle imbalanced node classification problem under different ratios.\n\nCons:\n\n1. The author states that \"As far as we know, UNREAL is the first method to use unlabelled nodes rather than synthetic ones in over-sampling approaches to deal with class imbalanced node classification.\" in Section 1.  However, we believe that this is a method of learning pseudo labels for graph node classification tasks. There have been many efforts working on this topic, and thus the contribution of \"using unlabelled nodes rather than synthetic ones.\" may be over-claimed.\n2. As Section 3.3 states, \"Identify the problem of geometric node imbalance (GI) and define a new metric to measure GI.\" Does this dimension has been validated through experimental results or theoretical analysis? I see that the author just referred to a previous article. A meaningful experiment and the theoretical foundation of the \"metric\" created for this problem are also lacking. Overall, this section may not be solid enough.\n\n\n3. It is suggested that the author should improve the paper organization to facilitate paper reading. For example, \"labelled nodes\" and \"aggregation function\" are in Section 2.1. In addition, there are too many notations in the article. It is recommended to organize a notation table.\n4. We did not find the author's source code and experimental dataset link in the paper for result reproducibility.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BEHU4H7drX", "reviewer": "Reviewer_D8cW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors propose an over-sampling based approach to tackle the situation of extremely skewed label distributions. Instead of generating synthetic minority nodes, as well as features and local topology, the authors consider unlabeled nodes, thereby eliminating the challenge of generating synthetic features and neighborhoods. Specifically, they conduct geometric ranking based on node embedding. The experiments conducted on benchmark datasets demonstrate that the proposed method significantly outperforms several baseline methods with different imbalance ratios. ", "summary_of_the_review": "In sum, I would recommend “6: marginally above the acceptance threshold”. The proposed idea is novel with significant gains, but it would be great to have more serious validation and analysis on concrete examples and large-scale datasets. ", "strength_and_weaknesses": "Strengths\n* Interesting and novel idea of DPAM and reranking for node retrieval.\n* Surprisingly good accuracy. The improvements over baseline methods are significant, especially for the cases with higher imbalance ratios.\n* The paper is well-written and easy-to-follow.\n\nWeaknesses\n* Lack of experiments with large-scale graphs, such as OGB benchmarks, where the imbalance could naturally exist.\n* Some analysis could be more extensive. For example, I wonder why for each dataset the authors only report the analysis for one imbalance ratio (and different across datasets). The space is actually enough to show all if using more columns.\n* Some concrete examples and qualitative analysis could be valuable to validate the motivations and justify the high improvements over baseline methods. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "AyzYNNdGVWl", "reviewer": "Reviewer_9Evz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper is targeted at class-imbalanced node classification. The authors propose UNREAL, an over-sampling-based approach which iteratively adds unlabeled nodes into the training set. UNREAL consists of the Dual Pseudo-tag Alignment Mechanism (DPAM), Node-Reordering, and Discarding Geometrically Imbalanced nodes (DGI). The authors conduct comprehensive experiments over five datasets and the results demonstrate that the proposed UNREAL outperforms recent baselines with different GNN backbones.", "summary_of_the_review": "This paper is not good enough for this conference. The paper needs more clarification to enhance the rationale of the proposed method. In addition, the authors need to conduct more experiments to verify the superiority of UNREAL.", "strength_and_weaknesses": "Strength:\n1. The paper introduces the target problem in class-imbalanced node classification clearly. The motivation is convincing and strong.\n2. The authors use figures to illustrate the pipeline of the proposed approach UNREAL, which helps readers understand the approach.\n3. The authors elaborate experiment details in the paper including experimental settings and datasets. It enhances reproducibility of the paper.\n\n\n\nWeaknesses:\n1. The proposed approach UNREAL does not solve the class-imbalanced problem in the real world. UNREAL iteratively selects unlabeled nodes from the minority classes during training. In practice, however, the class-imbalanced problem in the test set may be also severe. For instance, suppose we have $20n$ normal accounts and $n$ malicious accounts as the training set for malicious account detection. Meanwhile, the number of malicious accounts in the test set may be also limited (e.g., $2n$). In this case, the new training set formed by UNREAL is still class imbalanced. On the contrary, synthetic over-sampling algorithms (e.g., GraphSMOTE) can overcome this problem and may have better performance.\n2. In Section 3.2, Node-Reordering sorts nodes in the decreasing order of their confidence. The authors should provide a clear definition of the confidence. However, it is not provided either in Section 3 or in the main algorithm.\n3. According to Table 3, using geometric ranking is empirically better than confidence ranking. So why do we need to involve confidence ranking in Node-Reordering instead of solely using geometric ranking? In other words, does the weighted combination of the two rankings really benefit the performance? The authors may answer the concern by explaining in Section 3.2 and conducting experiments in Section 4.\n4. The proposed approach UNREAL involves a few hyperparameters such as $k’$ in $f_{\\text{cluster}}$ and the threshold $\\gamma$ of DGI. The authors should conduct experiments to investigate the sensitivity of UNREAL to hyperparameters.\n5. The main algorithm in Appendix C should be consistent with the description of UNREAL in the main paper. In Section 3.1, the unlabeled nodes are clustered into $k’$ clusters and $k’$ is usually larger than $k$. So $k’$ should be an input of the main algorithm and line 5 in the main algorithm is incorrect. In addition, Section 3.4 implies that UNREAL only adds nodes from the minority classes, which does not appear in the main algorithm.\n6. Please pay attention to grammar. I found many typos in the paper. For instance, in Related Work, “compensates” should be “compensate”, and “adjust” should be “adjusts”.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject