Topology-Imbalance Learning for Semi-Supervised Node Classification
Authors: Deli Chen
Yankai Lin
Guangxiang Zhao
Xuancheng Ren
Peng Li
Jie Zhou
Xu Sun
Venue: NeurIPS 2021 Poster (2021)
Keywords: node classification
topology imbalance learning
semi-supervised learning
graph neural network

Abstract: The class imbalance problem, as an important issue in learning node representations, has drawn increasing attention from the community. Although the imbalance considered by existing studies roots from the unequal quantity of labeled examples in different classes (quantity imbalance), we argue that graph data expose a unique source of imbalance from the asymmetric topological properties of the labeled nodes, i.e., labeled nodes are not equal in terms of their structural role in the graph (topology imbalance). In this work, we first probe the previously unknown topology-imbalance issue, including its characteristics, causes, and threats to semisupervised node classification learning. We then provide a unified view to jointly analyzing the quantity- and topology- imbalance issues by considering the node influence shift phenomenon with the Label Propagation algorithm. In light of our analysis, we devise an influence conflict detection–based metric Totoro to measure the degree of graph topology imbalance and propose a model-agnostic method ReNode to address the topology-imbalance issue by re-weighting the influence of labeled nodes adaptively based on their relative positions to class boundaries. Systematic experiments demonstrate the effectiveness and generalizability of our method in relieving topology-imbalance issue and promoting semi-supervised node classification. The further analysis unveils varied sensitivity of different graph neural networks (GNNs) to topology imbalance, which may serve as a new perspective in evaluating GNN architectures.

Topology-Imbalance Learning for Semi-Supervised Node Classification
Deli Chen 1.2, Yankai Lin', Guangxiang Zhao', Xuancheng Ren', Peng Li', Jie Zhou', Xu Sun?
Pattern Recognition Center, WeChat AI, Tencent Inc., China
MOE Key Lab of Computational Linguistics, School of EECS, Peking University {delichen, yankailin, patrickpli, wi thtonhoou) @tencenteeetttteeeeeemmeeemee com (zhaoguangxiang, renxc, xusun] @pku edu. cn
Abstract
The class imbalance problem, as an important issue in learning node representations, has drawn increasing attention from the community. Although the imbalance considered by existing studies roots from the unequal quantity of labeled examples in different classes (quantity imbalance), source of imbalance from the asymmetric topological properties of the labeled nodes, i.e., labeled nodes are not equal in terms of their structural role the graph (topology imbalance). In this work, we first probe the previously unknown topology-imbalane issue, including its characteristies, causes, and threats semi- supervised node classification learning. We then provide unified view to jointly analyzing the quantity- and topology- imbalance issues by considering the node influence shift phenomenon with the Label Propagation algorithm. In light of our analysis, we devise an influence conflict detection- metric Totoro to measure the degree of graph topology imbalance and propose a model-agnostic method ReNode to address the topology-imbll -imbllagee issue by re-weighting the influence of labeled nodes adaptively based their relative positions to class boundaries. Systematic experiments demonstrate the effectiveness and generalizability of our method in relieving aapology-imbalene node classification. The further analysis unveils varied sensitivity of different graph neural networks (GNNs) to topology imbalance, which may serve perspective in evaluating GNN architectures
argue that graph data expose unique
issue and promoting semi- supervsee
Introduction
Graph widely-used data structure
where the nodes are connected to each other through natural or handcrafted edges. Similar to other data structures, the representation learning for node clas- sification faces the challenge of quantity-imbalant -mballace issue, where the labeling size varies among classes and the decision boundaries of trained classifiers
mainly decided by the majority classes [46]. Node Representation Learning (short as QINL). However, different with other data structures, graph-structured data suffers from another aspect of the imbalance problem: the imbalance caused by the asymmetric and uneven topology of labeled nodes, where the decision boundaries are driven by the labeled nodes close the topological class boundaries (left of Figure thus interfering with the model lcarning.
There have been a series of studies [35] [1 49 handling the Quantity-Imballn
Present Work. For the first time, we recognize the Eoollgy-IImbalaee Node Representation Learning (short as TINL) as graph-specific imbalance learning topic, which mainly focus on the
'The code is available at htgp://jihaaaccmm/cccocceeeeeeed
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

ReNode
B
R2
R2
Unlabeled Node
Labeled Node
Influence Conflict
Influence Insufficient
Figure I: Schematic diagram of the -imlllgy-mbbllacee issue in node representation learning. The color and the hue denote the type and the intensity of each node's received influence from the labeled nodes, respectively. The left shows that nodes close to the boundary have the risk of information conflict and nodes far away from labeled nodes have the risk of information insufficient. The right shows that our method can decrease the training weights of labeled nodes (R1) close to the class boundary and increase the weights labeled nodes (B and R2) close to the class centers, thus relieving the topology-imbalant issue.
decision boundaries shift phenomena driven by the topology imbalance in graph and an essential component for node imbalance learning. Comparing with the well-explored QINI. that studies the imbalance caused by the numbers of labeled nodes, TINL explores the imbalance caused by the positions of labeled nodes and owns the following characteristics:
Ubiquity: Due the complex connections of the graph nodes, the topology structure of nodes in different categories is naturally asymmetric, which makes TINL an essential characteristic in node representation learning. Hence, is difficult to construct a completely symmetric labeling set even with an abundant annotation budget.
The influence from labeled nodes decays with the topology distance 3 The asymmetric topology of labeled nodes in different classes and the uneven distribution of labeled nodes in the same class will cause the influence conflict and influence insufficient problems (left of Figure P respectively, resulting in a shift of decision boundaries.
Perniciousness:
Orthogonality: Quantity-imbalant the same class as whole and devise solutions based on the total numbers each class, while TINL explores the influence of the unique position of each labeled node on decision boundaries. Thus, TINL is independent of QINL in terms of the object of study.
studies 19 g 5 usually treat the labeled nodes of
Exploring TINL is of great importance for node representation learning due to its ubiquity and pemiiiouusness. However, the methods [17 22) for quantity imbalance can be hardly applied TINL because of the orthogonality. To remedy the topology-imbalane issue, thus promoting the node classification, we propose a model-agnostic training framework ReNode to re-weight the labeled nodes according to their positions. We devise the conflict detection-based Topology Relative Lecation (Totoro) metric to leverage structural positions. Based the Totoro metric, with small conflict that are highly likely to be close to topological class centers to make them play more pivotal role during training. and vice versa (right of Figure DT. Empirical results of various imbalance scenarios (TINL, QINL, large-scale graph) and multiple graph neural networks (GNNs) demonstrate the effectiveness and generalizability of our method. Besides, provide the sensitivity to topology imbalance as a new evaluation perspective for different GNN architectures.
interaction among labeled nodes across the whole graph locate their
further increase the training weights of nodes
Topology-Imbalance Node Representation Learning
2.1 Notations and Preliminary
In this work, we follow the well-established semi-supervised node classification setting 447 to conduct analyses and experiments. Given undirected and unweighted graph = E), where V is the node set represented by the feature matrix X E I (n | is the node size and d the node embedding dimension),
the edge set which is represented by an adjacency matrix A E gr L V is the labeled node set and usually we have [ << [V the node classification

---

ocd-r, LX-T octert
The Pastine
Basiic
Febo Polline
The Postiiv
Ine Negaine
Toe begaive
Fale Negaiie
Pala Napatoe
(a) Predictions of GCN and LP
(b) Uniform Sampling
(c) Quantity-balaneed Sampling
Figure 2: Node influence and boundary shift caused by quantity- and topology- oppolgy-imballnce. (a): The prediction results of GCN and LP are highly consistent (t-SNE [39] visualization of the CORA dataset). (b): The node influence boundary (the yellow dotted line) is shifted towards the small class from the true class boundary (the black dotted line) under the quantity- and topology-imbalanee imbalance scene. (c): The node influence boundary shifted towards the large class under the quantity-balant topology-inin ioplogy-imballnced scene. We regard the large class as positive class to indicate the results.
task is to train a classifier F (usually GNN) to predict the class label y for the unlabeled node set u = - C. The training sets for different classes are represented by (C1, C2. Cs) and & the number of classes. The labeling ratio 8 = C/V is the proportion of labeled nodes in all nodes. In this work, we focus on TINL. nonogeneously-connees on the critical topology-imbalance issue.
graphs and hope inspire future studies
2.2 Understanding Topology Imbalance via Label Propagation
From Figure T can intuitively perceive the imbalance brought by the positions of labeled nodes; in this part, we further explore the nature of topology imbalance with the well-known Label Propagation (50) algorithm (short as LP) and provide uniform analysis framework for the comprehensive node imbalance issue. In LP, labels are propagated from the labeled nodes and aggregated along edges, which can also be viewed random walk process from labeled nodes. The convergence result Y after repeated propagation is regarded as the nodes soft-labels:
Y = a(I (1 (1-a))4 a)
where I is the identity matrix, E (0, 1] is the random walk restart probability. ='= D D- is the adjacency matrix normalized by the diagonal degree matrix D, Y is the initial label distribution where labeled nodes are represented by the one-hot vectors. The prediction label for the i-th node is qi = arg max, Y.j. LP a simple yet successful model [37 and can unified with GNN models owning the message-passes passing mechanism [4]. From Figure 2(a), we empirically find that there is a significant correlation between the results of LP and GCN (T/F indicates prediction True/False).
The LP prediction q can be viewed as the distribution of the (labeled) node infiuence [4]] (i.c. each node is mostly influenced by which class's 's information); hence the boundaries of the node influence can act as an effective reflection for the GNN model decision boundaries considering the high consistency between LP and GNN. Moreover, node influence offers unified view of TINL and QINL: ideally, the node influence boundaries should be consistent with the true class boundaries, but both the labeled nodes' numbers (QINL) and positions (TINL) can cause a shift of the node influence boundaries from the true one, resulting in deviation of the model decision boundaries.
Node imbalance issue composed of topology- and mrantityiibalance Figure 2 iillustrates two examples of node influence boundary shift. In Figure 2(b),, when the uniform selection is adopted generate training set, both the quantity and the topology are imbalanced for model training; then the large class with more total nodes (denotes by blue color) will own stronger influence than the small class with fewer total nodes (denotes by red color) due to the quantity advantage and the node influence boundary is shifted towards the small class. In Figure strategy is adopted for sampling training nodes, will easier the small class to has more labeled nodes close to the class boundary and the boundary of the node influence is shifted into the large class. We can find that even when the training set is quantity-balanced the topology-imbn -imballnce issue still exists and hinders the node classification learning. Hence, conclude that node imbalance
when the
balanced
3

---

34 4.9
071
42
Conflict
Figure 3: Effectiveness of Totoro (a) Node Level: labeled nodes (t-SNE visualization the CORA dataset) with less influence conflict (lighter color) are farther-away from class boundaries than those with high conflict (darker color), and (b) Dataset Level: There significant negative correlation between the GNN (GCN) performance and overall conflict of the training set (the Pearson correlation coefficient is 0.618 over 50 randomly selected training sets with the p value smaller than 0.01).
learning is caused by the joint effect of TINL and QINL. Separately considering TINL or QINL will lead to one-sided solution to node imbalance learning.
2.3 Measuring Topology Imbalance by Influence Conflict
Although we have realized that the imbalance of node topology interferes with model learning, how measure the labeled node's ss relative topological position its class (being far away from close to the class center) remains the key challenge in handling the topology-imbalane complex graph connections and the unknown class labels for most nodes in the graph. As the nodes are homogencously connected when constructing the graph, even nodes close to the class boundaries own similar characteristics their neighbors. Thus it is unreliable leverage the difference between the characteristics of one labeled node and its surrounding subgraphs to locate its topological position. Instead, we propose utilize the node topology information by considering the node influence conflict across the whole graph and devise the Conflict Detection-baser Topology Relative Location metric (Totoro).
issue due to the
Similar to Eq (I) we calculate the Personalized PageRank 27 matrix P to measure node influence distribution from each labeled node:
P= - a))--
(2)
Node influence conftict denotes topological position. According related studies [4] 19 21. P
can be viewed as the distribution of influence exerted outward from each node. We assume that if a labeled node E V encounters strong heterogeneous influence from the other classes' labeled nodes in the subgraph around node v where node v itself owns great influence, we have the conclusion that node meets large influence conflict in message passing and it is close to topological class boundaries, and vice versa. Based on this hypothesis, we take the expectation of the influence conflict between the node v and the labeled nodes from other classes when node randomly walks across the entire graph as a measurement of how topologically close node is to the center of the class it belongs to. The Totoro value of node computed as:
T. = E
Σ
L Pr.ll SEC,
(3)
Cc, |c,
JE(LAA),7
where ye is the ground-truth label of node v, P. indicates the personalized PageRank probability vector for the node v. A larger Totoro value T, indicates that node v topologically closer to class boundaries, and vice versa. The normalization item 1/Ic,1 is added make the influence from the different classes comparable when computing conflict.
We visualize the node labels and the Totoro values (scaled to [0, 1J) of labeled nodes in Figure a).. We can find that the labeled nodes with smaller Totoro values are farther away from the class boundaries. demonstrating the effecctivnness of Totoro in locating the positions of labeled nodes. Besides, sum

---

the conflict of all the labeled nodes Ebec T. to measure the overall conflict of the dataset, which can be viewed as the metric for the overall topology imbalance given the graph g and the training set L. Figure 3b) shows that there is a significant negative correlation between the overall conflict and the model performance, which further demonstrates the effectiveness of Totoro measuring the intensity of topology imbalance at the dataset level.
2.4 Alleviate Topology Imbalance by Instance-wise Node Re-weighting
In this section, we introduce ReNode, a model-agnostic training weight schedule mechanism to address TINI. for general GNN encoder in plug-and-play manner. Inspired by the analysis in Section 2.2 the ReNode method is devised to promote the training weights of the labeled nodes that are close to the topological class centers, so as to make these nodes play a more active role in model learning, and vice versa. Specifically, we devise a cosine annealing mechanise for the training node weights based on their Totoro values:
Rank m)); U EEC C
4 = Umin + 2 (Wimax Wminn) + cos(
(4)
where wo, is the modified training weight for the labeled node v, Wmin, Wmax are the hyper-parameters indicating the lower bound and upper bound of the weight correction factor, Rank(T, is the ranking
order of T. from the smallest to the largest. The training loss Lor for the quantity-balanced topology- imbalanced node classification task is computed by the following equations:
L
1 C
Σ W. Σv VEC
yo log ge, 9 softmaxx SosottmaxFF(X...... A,)),
(5)
where F denotes any GNN encoder, is the parameter of F, 9: is the GNN output for node i, y. is the gold label for node i in one-hot embedding. By encouraging the positive effects of the labeled nodes near the class topological centers, and reducing the negative effects of those near the topological class boundaries, our ReNode method is expected to minimize the deviation between the node influence boundaries and the true class boundaries, so as to correct the class imbalance caused by the positions of labeled nodes.
ReNode to Jointly Handle TINL and QINL In this part, we introduce the application of the ReNode method in more general graph imbalance scenario where both the topology- and quantity- imbalance issues exist. As analyzed in previous sections, the TINL and QINL are orthogonal problems. Therefore, we propose that our ReNode method based on (labeled) node topology can be seamlessly combined with the existing methods designed for the Without loss of generality, we present how our ReNode method can be combined with the vanilla class frequency-based re-weight method [17]. The training loss Lo for the quantity-imbalanee topology-imban imbalanced node classification task is formalized in the following equation:
learning.
1 Σ
C IC,
k
LQ = |
we
Σ
cc log g
(6)
|
DEC
where |C] is the average number of the class training sizes. With this method, the final weight of the labeled node is affected by two perspectives: training examples of the minority classes will have higher weights than that of the majority classes; training examples close to the topological class centers will have higher weights than those are close to the topological class boundaries.
ReNode for Large-scale Graph There are mainly two challenges when applying ReNode to large- scale graphs: (1) how to calculate the PageRank matrix, and (2) how train the GNN model in an inductive setting [33. In this work, we follow the PPRGo method (2) to implement our method on the large-scale graph, which can decouple the feature learning process from the information transmission process to resolve the dependence on the global graph topology structure and can be carried out much efficiently. Following PPRGo, the Personalized PageRank matrix P and the corresponding training ReNode factor vp are generated by the estimation method from Andersen et al. M and then 1 is
We also try other schedules and the cosine method works best. More details can be found in Appendix B.
5

---

Table I: ReNode (short RN) for the pure epplooyyiimbllace issue. We report Weighted-F1 (W-F, %). Macro-F1 (M-F, %) and the corresponding standard deviation for each group of experiments. and represent the result is significant in student t-test with p 0.05 and p 0.01, respectively.
Model
Training
CORA
CiteSeer
Med
Photo
Computers
GCN
w/o RN
79.T
=90
77.8.s5
78.6"**"
66.9
66.2at
620
62.8"
76.1
76.1"
74.7at9
86.8.20
87.7"
B4.7a13
85.4"
74.7"
74.2
74.5
73.6229
GAT
W/ RN
w/o RN
27.
7600
74.9.1
76.2" 21
66.392
62.4
63.2 21
739933
75.2"
75.1"
73.9
88.3539
89.1"
87.1"
86.2
78.821s
79.0.2:
78.8a33
78.7am
PPNP
W/ RN
W/o
80.5
80.5" 403
68.1"
63.7 114
46.0"1200
46.1""
74,7a17
89.7"
8618
87.2"
79.0" 412
77.7
78.3' .M4
SAGR
W/o RN
75.7"*
*514
74.6.14
67.021
67.3
63.0
63.5"
74.9" aue
74,2112
78.2"
74,2221
56.2.2
83.9.5
73.5134
71.6.15
72.3 425
CHEB
W/o RN
RN
a513
74.5gm
73.4g1
74.0"*
63.
66.8
63.2gt
63.8"
76.2"
75.2gm
76.3"
82.1
8488
82.1
49.
70.5
68.6.114
08.421
SGC
W/ RN
W/b
77.0 77.0""211 211
74.9
73.8
76.0"
113
68.7ar
67.2"
62.9 215
8gr
72.9
73.7" 222
73.8 123
23.
87.1
87.415
84
85.2:13
78.2 L13
77.4
76.8g:
77,8" 112
Table 2: Result of different dataset conflict levels (High/Midklle/Low) Our ReNode method improve the GNN (GCN) performance most when the conflict level of graph is high.
W-F(%)
CORA-H
CORA-M
CORA-L
CiteSeer-H
CiteSeer-M
CiteSeer-L
PubMed-H
PubMed-M
PubMed-L
w/o RN
76.5 78.7"* =ea
78.4ga
79.7
62.6215
65.3
67.3
22.
74.7a18 75.6"" 210
78.3218 78.8" #ts
RN
79.3"
80.4
63.8"
66.0"">ax
67.5=14
74.3"
directly employed the aggregation weights from all the other nodes regardless of their topology distance from the current node:
g' = soft (FF
where F' can be a linear layer or a multi-layer perceptron with parameter 6', The final training loss for large-scale graph Lr, follows Eq (5) and (6). and replaces w and g with v and g'.
3 Experiments
In this section, we will first introduce the experimental datasets for both transductive and inductive semi-supervised node classification. Then we introduce the experiments to verify the effectiveness of the proposed ReNode method in three different imbalance situations: (1) TINL only, (2) TINL and QINL, (3) Large-scale Graph.
3.1 Datasets
We adopt two sets of graph datasets to conduct experiments. For the transductive setting 13 we take the widely-used Plantoid paper citation graphs [K] (CORA,CileSeer, Pubmed) and the Amazon co- purchase graphs (44
to verify the effectiveness of our method. For the inductive setting, conduct experiments on the popular Reddit dataset [13] and the enormous MAG-Scholar dataset (coarse-gg graii version) [2] which owns millions of nodes and features. For each of these datasets, repeat experiments 5 different datasets splittings 34 and we run 3 times for each splitting to reduce the random variance. More details about the datasets and experiment settings are presented in Appendix A.
3.2 ReNode for the Pure Topology-imbas
Issue
Settings When considering topology-imbalant only, the labeling set takes a balanced setting and the annotation size for each class all equal Cl/k. Following the most widely-used semi- supervised setting in node classification studies [47 [8] we randomly select 20 nodes in each class for training and 30 nodes per class for validation; all the remaining nodes form the test set. We display the experiment results for the 5 transductive datasets on 6 widely-used GNN models: GCN [18]. GAT [40] PPNP 19, GraphSAGE [3] (short as SAGE), ChebGCN 9 (short as CHEB) and
SGC
We strictly align the hyperparameters in each group of experiments to show the pure improvement brought by our ReNode method (similarly hereinafter). The training loss Ler from
43
section 2.4 is adopted.

---

Table 3: ReNode method for the compound scene of TINL and QINI. The imbalance ratio p is set to different levels (15, 10) to test the effect of our method under different imbalance intensities.
Macro-FIl Fl(S)
CORA
CiteSeer
PubMed
Photo
Computers
Imbhllncc Ratio
10
10
5
10
5
10
5
10
60.9gs
41.0g1
53.6271
47.6ggx
61.0gg
49.7gt
62.0gr
40.7g3
50.4gr
35.5
DR-GCN
67.7at
51.3
54,7a..
52.5
19
78.0.u
80.8
29.5
66.9133
67.4.3
RA.GEN
69.0ats
51.7at1
5
52.7-21
80.6
78.
81,4
79.4
71.2
68,7
G-SMOTE
68.1
49.6ar
54.0..a
51.8-13
79.7
764411
82.2
77.5
71.93s
61.3
RW (wlo RN)
69.1
49.7
53,6123
52.9
80.5
78.0.20
80.S
80.4
70.5
67.8
RW (w/ RN)
70.0"
50.1
55,2""
44,0""
81.2"
78.5"
13.
81.3"
72.4"
124
FOCAL (wl RN)
66.1a16
$1.9
$1.31:33
54.0.19
80.5
78.0.14
79.2
63.8
63.9
FOCAL (w/ RN)
68.7"
$2.6"
54.62:2
24.7
80.9" 205
78.7"
80.0"" 123
80.7" 129
68.6"
6335""a33
CB (wlo RN)
89.8
5115
54.1a:3
53.5
77.9aza
78.8
69 6126
64.8at9
CB (w/ RN)
21.9"217 217
54.7"
54.3"aar
81.2"a11
79.6" 780
80.4">1 213
73.1
66.5
Results From Table we can find that our ReNode method can effectively improve the overall performance (Weighted-F1) and the Mlas-ballacce performance (Macro-F1) for all the experiment GNNs in most cases, which proves the effectiveness and generalizability of our method. Our method considers the graph-specific topology imbalance issue which has been usually neglected in existing methods and conducts a fine-grained and self-adaptive adjustment to the training node weights based on their topological positions. We notice that the improvement for the CiteSeer dataset is less than the other datasets. We analyze the reason lies in that the connectivity of CiteSeer is poor, which makes the conflict detection-based method fail to reflect the node topological position well. To verify the motivation of relieving topology-imbalanee we set training sets with different levels of topology- imbalance to test our method" Table 2 displays that our ReNode method improves the performance of GNN (GCN) most when the dataset is highly topologically imbalanced. which demonstrates that our method can effectively alleviate topology topology-imbalane imbalance and improve GNN performance.
3.3 ReNode for the Compound Scene of TINL and QINL
Settings When jointly considering both topology- and quantity-imbllane issues, following existing studies [5] 4. we take the step imbalance setting, in which all the minority classes have the same labeling size n, and all the majority classes have the same labeling size n, p 72g, The imbalance ratio P denotes the intensity of quantity imbalance which is equal to the ratio of the node size of the most frequent to least frequent class. In this work, the imbalance ratio p is set to [5, 10] for each dataset. The fraction of the majority classes is μ. and for all experiments, we set = 0.5 and round down the result μ k. The training loss T.Q from section 2.4 is adopted. We implement two groups of baselines for comparison: (1) Popular quantity-imbalance methods for general scenarios:
Re-weight [17] (RW), Focal Loss (2 (Focal) and Class Balanced Loss [8 (CB); (2) Graph-specific quantityiimbllncee methods: DR-GCN (35). RA-GCN [T] and GraphSMOTE 14]. To jointly handle the topology- and quantity -amaaaty-imblllneee issues and demonstrate the orthogonality of them, we combine our ReNode method with these three general quantity-imbalance methods (RW, Focal, CB 4
The backbone model is GCN and the labeling ratio is set to 5%.
Results From Table 3 (Macro-Fl is reported here for fair comparison with these methods designed find that our ReNode method significantly outperforms both methods in most situations by simultaneously
for class-balance performance), the general and the graph-specific alleviating the topology- and quantity -mballacce issues. Even when the training set is severely quantity-imbul imbalanced (p=10), our method still effectively alleviates the imbalance issue and promotes model performance well. The performance of the quantity-imbalane field (RW, Focal, CB) is on par with or less effective than the graph-specific quantity-imbalance methods (DR-GCN, RA-GCN, G-SMOTE), while the combination of our ReNode method and these general quantity-imin -imalay-- methods can surpass the graph-specifi quantity-imbalane methods, which demonstrates that the node imbalance learning can be further solved by jointly handling the topology- and chantity-imbalane issues instead of considering the quantity-mmbllance issue only.
methods from the general
2 'The settings of the dataset topology-imbalance imbalance levels is shown in Appendix C.
A 'The three graph-specific methods have special operations for the training loss, which can be hardly combined with our method.
7

---

90 XM
XM
15
70
20%
1007
50%
Robii:
Figure 4: Experimental results (Weighted-FI, %) on the large-scale Reddit and MAG-Scholar graphs. Our ReNode method can effectively improve the model performance under different labeling sizes.
GDh
GCV
2h7
High
Midll CORA
Righ
XiAlk
High
Midl+
Low
Cleceerr
PabMed
Figure 5: Evaluating GNNs from the aspect of topology-imbalanee sensitivity (Metrie: Weighted-F1 (%)). We can summarize the ranking of
sensitivity: GCN > PPNP > GAT.
3.4 ReNode for Large-scale Graphs
Settings We conduct experiments the two large-scale datasets: Reddit and MAG-Scholar, to verify the effectiveness of our ReNode method the inductive setting. We conduct experiments with different labeling sizes (20/50/100 training nodes per class) and imbalance settings (TINL-only, TINL and QINL). The backbone GNN model is PPRGo [2] For QINL, we take the uniform selection to sample training nodes to be consistent with PPRGo. The training loss I. from section 4 is adopted. Both baseline and our methods are not combined with any quantity-imbalane method.
Results In Figure 4 present the experiment results with different labeling sizes and imbalance settings, we can find that our method can effectively promote the performance on the large-scale graphs comparing the popular PPRGo model across different settings, which demonstrates the applicability of our method for extremely-large graphs. We also notice that our method can bring greater improvement when the labeling size large. We explain the reason lies in that when the labeling size is large, the positions located by the conflicts among nodes will be more accurate, thus bringing more reasonable weight adjustments. On the other hand, when the labeling ratio is extremely small (especially for the enormous MAG-Scholar graph) and the influence conflict between labeled nodes negligible, our method exhibits cold start problem.
Discussions
4.1 Evaluating GNNs from the Aspect of TTpology-Imballan Sensitivity
In Figure we evaluate the GNN's capability for handling applooy-imbalanne and find that different GNNs present significant difference in the topology-inbalance sensitivity across multiple datasets. imbalance level of the graph and its performance decays
The GCN model is susceptible to the greatly when the topology-imin imbalance increases. On the opposite, the GAT model less sensitive to the appoloyy-imbllace level and can achieve the best results when the aapology-imbllany level is level low, high. The PPNP model can achieve ideal performance when the topology-imbalan level is high. and its performance does not drop as sharply as GCN when the We analyze the reason lies that: (1) the aggregation operation of GCN equivalent directly
'e do not implement other inductive backbone GNN models like Cluster-Gon 7 or APPNP 19 due to the low efficiency 2 of them when handling the enormous MAG-Scholar dataset.

---

averaging neighbor features [45] that lacks the noise filtering mechanism, so it is more sensitive to the topology-imball
level of the graph; (2) the GAT model can dynamically adjust the aggregation weight from different neighbors, which increases its robustness to the high topology-imhalane level is low and
situation but hinders the model performance when the graph topology-imbalane there is less need to filter neighbor information; (3) the infinite convolution mechanism of the PPNP model makes it possible to aggregate the information from distant nodes to enhance its robustness to the graph topology imbalance.
Shehur al. 34 notice that the performance ranking of GNNs varies with the training set selection. Hence, existing node classification studies [32 [4] usually repeat experiments multiple times with different training sets reduce this randomness. The results from Figure [5] inspire us that the topology imbalance can partly explain the randomness of GNN performance caused by the training set selection and we can adopt the copology-imbllnee sensitivity as new aspect in evaluating the performance of different GNN architectures.
4.2 Limitations of Method
Although our ReNode method has proven effective in multiple scenarios, we also notice some limitations of it because of the complexity of node imbalance learning. First, the ReNode method is devised for homogeneously-comeee various datasets in experiments), and it needs further update for heterogeneously-comeen (such as protein networks). Besides, the ReNode method improves less when the graph connectivity poor (Section 3.2) or the labeling ratio is extremely low (Section 3.3 because in these cases, the conflict level among nodes is low thus the nodes topological positions are insufficiently reflected.
graphs (linked nodes are expected to be similar, such as the graphs
5 Related Work
Imbalanced classification problems are widespread in real scenarios and have attracted extensive attention from both academia and industry. Most existing studies on this topic focus on the class- imbalanced quantity distribution [15]. where the model's 's inference ability for the majority classes will be significantly better than that of minority classes [12] The existing methods for solving the quantity-imbalance issue can be roughly divided into methods for the data selection phase and the
are two classical guantity-balanced balanced training set On the other hand, Re-weighting is simple but effective solution for the model training phase, which adjusts the weights of training samples in different classes based on the labeling sizes [17] 30 8 33. However, directly applying these methods into the graph scene lacks the consideration for the graph-specific topology-imbalance issue. Unlike the re-weight methods which conduct class-lever re- weighgtting, our ReNode method is a more fine-gra grained one and assign weights to each node individually.
model training phase. Active learning [3 TO 42 and Re-sampling 6 16 25
examples designed to construct a quantity-
There have been quantity-imballne tion (20)) trying exclude the negative influence of labeling samples close to class boundaries by measuring the similarity of sample features. However, in the graph scene, the prior knowledge contained in node connections is more reliable than directly calculating the feature similarity. Besides, the number of labeled nodes is quite small in the semi cemi-supervised setting. Thus it is not robust to locate their positions by computing similarity among a small number of nodes and we propose to leverage the influence conflict across the whole graph to locate node position to boundaries.
studies (Tomek links (38), NearMiss [23
One-Sided Selec-
Graph data structure owns wide range of applications, such as social media 133, stock exchange 21. shopping (3, medicine 44 node representation learning also suffer from the quantity-imbalane
transportation (28) and so on. Similar to other data structures, graph
issue (35). Apart from the
universal srantity-balance approaches introduced in Section 55 which can be transferred to the graph methods recently proposed. DR-GCN (35)
scene, there are some graph-specific quantity-imballan propose two types of regularization to tackle quantity imbalance: class-conditions training and unlabeled nodes latent distribution constraint. RA-GCN [I]] propose to automatically learn to weight the training samples in different classes in an adversarial training manner. AdaGCN Shi et al. (36] propose to leverage the boosting algorithm to handle the quantity-imbalane issue for the node classification task. GraphSMOTE [49 combines the synthetic node generation and the edge generation to up-sample nodes for the minority classes. However, these studies only pay attention to the quantity imbalance and overlook the topology imbalance.
adversarial

---

Different from these studies 48 29 26 that try to locate the absolute positions for all the nodes by measuring their distance from the selected anchor nodes, our Totoro metric is devised locate the relative positions to the class boundary for the laheling nodes by considering the influence conflict and can get rid of the dependence on the anchor nodes. Besides, our relative positions can more accurately reflect node class information because we distinguish the information from different classes while treat all the anchor nodes the same and ignore the class difference.
existing studies [48 29
6 Conclusion and Future Work
In this work, we recognize the topology-imbalance node representation learning (TINL) as a graph- specific imbalance learning problem that has not been studied far. We find that the topology- imbalance issue widely exists in graphs and severely hinders the learning of node classification. We unify TINL with the quantity-imbalanny shift of the node influence boundaries from true class boundaries. To measure the degree of topology imbalance, devise a conflict detection-based metric Totoro to locate node position, and further propose the ReNode method to adaptively adjust the training weights of labeled nodes based on their topological positions. Extensive empirical results have verified the effectiveness of our method in various settings: TINL-only, both TINL and QINL, and large-scale graph. Besides, we also propose the topology-imbalane sensitivity as a new metric to evaluate GNNs.
node representation learning (QINL) by considering the
Considering the importance the copology-imbalnne issue and the limitations of our approach, advanced methods with stronger theoretical experimental support expected in future work. Moreover, since topology imbalance widespread in graph-related tasks other than node classifi- cation, how measure and solve the topology-imbalan issues in broader graph scopes remains meaningful challenge for future study.
7 Acknowledgement
We appreciate all the thoughtful and insightful suggestions from reviews, This work was supported in part by Tencent Research Grant and National Natural Science Foundation of China (No. 61673028). Xu Sun is the corresponding author of this paper.
References
[1] Reid Andersen, Fan R. Chung, and Kevin Lang. Local Graph Partitioning using PageRank Vectors. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 475-486. IEEE Computer Society, 2006.
[2] Aleksandar Bojchevski, Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik, and Stephan Günnemann. Scaling Graph Neural Networks with Approximate PageRank. the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2020, pages 2464-2473, ACM, 2020.
[3] Eliay Buchnik and Edith Cohen. Bootstrapped Graph Diffusions: Exposing the Power of Nonlinearity. Proc. ACM Meas. Anal. Compur. Syst., 2(1):10:1-10:19 2018.
[4] Mateusz Buda, Atsuto Maki, and Maciej A. Mazurowski. A Systematic Study of the Class Imbalance Problem in Convolutional Neural Networks. Neural Networks, 106:249-259, 2018.
[5] Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Aréchiga, and Tengyu Ma. Learning Imbalanced Datasets with aabbel-Dstributtonn--ee Processing Systems 32: Anmual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 1565-1576. 2019.
Margin Loss. In Advances in Neural Information
[6] 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.
10

---

[7] Wei-Lin Chiang, Xuanqing Liu, Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks. In the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pages 257-266. ACM, 2019.
[8] Yin Cui, Menglin Jia, Tsung- Yi Lin, Yang Song, and Serge J. Belongie. Class-Balancd Loss Based on Effective Number of Samples. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, pages 9268-9277. Computer Vision Foundation / IEEE, 2019.
[9] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. In Advances in Neural Information Processing Systems 29; Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 3837-3845, 2016.
[10] Seyda Ertekin, Jian Huang, and C Lee Giles. Active Learning for Class Imbalance Problem. In the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2007, pages 823-824, 2007.
[11] Mahsa Ghorbani, Anees Kazi, Mahdich Soleymani Baghshah, Hamid R. Rabiee, and Nas- sir Navab. RA-GCN: Graph Convolutional Network for Disease Prediction Problems with Imbalanced Data. arXiv preprint: 2103.00221, 2021.
[12] Haixiang Guo, Yijing Li, Jennifer Shang, Gu Mingyun, Huang Yuanyue, and Gong Bing. Learning from Mlass-Imbalances Data: Review of Methods and Applications. Expert Syst. Appl., 73:220-239, 2017.
[13] William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive Representation Learning on Large Graphs. In Advances in Neural Information Processing Systems 30: Anmual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 1024-1034, 2017.
[14] Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive Multi- Representation Learning on Graphs. In the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 4126. PMLR, 2020.
[15] Haibo He and Edwardo A. Garcia. Learning from imbalanced data. IEEE Trans. Knowl. Data Eng.. 21(9):1263 1284, 2009.
[16] Haibo He, Yang Bai, Edwardo A. Garcia, and Shutao Li. ADASYN: Adaptive synthetic sampling approach for imbalanced learning. In the International Joint Conference on Neural Networks, IJCNN 2008, part of the IEEE World Congress on Computational Intelligence, WCCI 2008, Hong Kong, China, June 1-6, 2008, pages 1322-1328. IEEE, 2008.
[17] Chen Huang, Yining Li, Chen Change Loy, and Xiaoou Tang. Learning Deep Representation for Imbalanced Classification. In the 29th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, pages 5375-5384, 2016.
[18] Thomas N Kipf and Max Welling. Supi-supe Classification with Graph Convolutional Networks. In the 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
[19] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then Propagate: Graph Neural Networks meet Personalized PageRank. In the 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, OpenReview.net, 2019.
[20] Miroslav Kubat, Stan Matwin, et al. Addressing the Curse of Imbalanced Training Sets: One- sided Selection. In the 14th International Conference on Machine Learning (ICML 1997), Nashville, Tennessee, USA, July 8- 12, 1997, volume 97, pages 179-186. Morgan Kaufmann, 1997.

---

[21] Wei Li, Ruihan Bao, Keiko Harimoto, Deli Chen, Jingjing Xu, and Qi Su. Modeling the Stock Relation with Graph Network for Overnigtt Stock Movement Prediction. In the 29th Inter- national Joint Conference on Artificial Intelligence, IJCAI 2020, pages 4541-4547. ijcai.org, 2020.
[22] Tsung-Yo Yi Lin, Priya Goyal, Ross B. Girshick, Kaiming He, and Piotr Dollár. Focal Loss for Dense Object Detection. In IEEE International Conference on Computer Vision, ICCV 2017, Venice, Italy, October 22-29, 2017, pages 2999-3007 IEEE Computer Society, 2017.
[23] Inderjeet Mani and Zhang. KNN Approach to Unbalanced Data Distributions: A Case Study Involving Information Extraction. In Workshop on Learning from Imbalanced Datasets, volume 126, 2003.
[24] Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image-based Rocommendations on Styles and Substitutes. In the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, Santiago, Chile, August 9-13, 2015, pages 43-52. ACM, 2015.
[25] Iman Nekooeimehr and Susana Lai-Yuen. Adaptive Semi-unsupervised Weighted Oversam- pling (A-SUWO) for Imbalanced Datasets. Expert Systems with Applications, 46:405-416 2016.
[26] Sunil Nishad, Shubhangi Agarwal, Amab Bhattacharya, and Sayan Ranu. GraphReach: Position- Aware Graph Neural Networks using Reachability Estimations. In the 30th International Joint Conference on Artificial Intelligence IJCAI, 2020.
[27] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The PageRank Citation Ranking: Bringing Order to the Web. Technical report, Stanford InfoLab, 1999.
[28] Nikolay G Prokoptsev, AE Alekseenko, and Yaroslav Aleksandrovich Kholodov. Traffic Flow Speed Prediction Transportation Graph with Convolutional Neural Networks. Computer research and modeling, 10(3):359-33 367-5599-66622 2018
[29] Zhenyue Qin, Saeed Anwar, Dongwoo Kim, Yang Liu, Pan Ji, and Tom Gedeon. Position- Sensing Graph Neural Networks: Proactively Learning Nodes Relative Positions. arXiv preprint: 2105. 1005./1346, 2021.
[30] Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to Reweight Examples for Robust Deep Learning. In International Conference on Machine Learning, pages 4334 4343. PMLR, 2018
[31] Pengzhen Ren, Yun Xiao, Xiaojun Chang, Yao Huang, Zhihui Li, Xiaojiang Chen, and Xin Wang. A Survey of Deep Active Learning. arXiv preprint: 2009,00236, 2020.
[32] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. The Truly Deep Graph Convolu- tional Networks for Node Classification. arXiv preprint: 1907.10903, 2019.
[33] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective Classification in Network Data. Al magazine, 29(3):93 93, 2008
[34] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of Graph Neural Network Evaluation. arXiv preprint: 181 1811.05868, 2018.
[35] Min Shi, Yufei Tang, Xingquan Zhu, David A. Wilson, and Jianxun Liu. Multi-Class Imbalanced Graph Convolutional Network Learning. In the 29th International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 2879-2885. ijcai.org 2020.
[36] Shuhao Shi, Kai Qiao, Shuai Yang. L Wang. Chen, and Bin Yan. AdaGCN: Adaptive Boosting Algorithm for Graph Convolutional Networks Imbalanced Node Classification. arXiv preprint: 2105. 11625, 2021.
[37] Marina Sokol, Konstantin Avrachenkov, Paulo Gonçalves, and Alexey Mishenin. Generalized Optimization Framework for Graph-based Supi-supe Learning. In the 12th SIAM In- ternational Conference on Data Mining, Anaheim, California, USA, April 26-28, 2012, pages 966-974, SIAM/ / Omnipress, 2012.
12

---

[38] Ivan Tomek et al. Two Modifications of CNN. IEEE Transactions on Systems, Man, and Cyberneties, 1976.
[39] Laurens Van der Maaten and Geoffrey Hinton. Visualizing Data using t-SNE. Journal of machine learning research, 9(11), 2008.
[40] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph Attention Networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
[41] Hongwei Wang and Jure Leskovec. Unifying Graph Convolutional Neural Networks and Label Propagation. arXiv preprint: 2002.06755, 2020.
[42] Xinyue Wang, Bo Liu, Siyu Cao, Liping Jing, and Jian Yu. Important Sampling based Active Learning for Imbalance Classification. Science China Information Sciences, 63(8):1-14, 2020.
[43] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying Graph Convolutional Networks. In International Conference on Machine Leaminng pages 6861-6871. PMLR, 2019.
[44] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. MoleculeNet: a Benchmark for Molecular Machine Learning. Chemical science, 2018.
[45] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Networks? In the 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[46] Yuzhe Yang and Zhi Xu. Rethinking the Value of Labels for Improving Class-Imbalanced Learning. In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[47] Zhilin Yang. William W Cohen, and Ruslan Salakhutdinov. Revisiting Semi-supervised Learning with Graph Embeddings. In the 33nd International Conference on Machine Learning, ICML 2016, volume 48 of JMLR Workshop and Conference P Proceedings, pages 40-48. JMLR.org, 2016.
[48] Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware Graph Neural Networks. In the 36th International Conference on Machine Learning, ICML 2019, volume of Proceedings of Machine Learning Research, pages 7134-11444 7143. PMLR, 2019.
[49] Tianxiang Zhao, Xiang Zhang, and Suhang Wang. GraphSMOTE: Imbalanced Node Classifica- tion on Graphs with Graph Neural Networks. In WSDM '21, The Fourteenth ACM International Conference Web Search and Data Mining, Virtual Event, Israel, March 8-12, 2021, pages 833-841, ACM, 2021.
[50] Dengyong Zhou and Christopher J. C. Burges. Spectral Clustering and Transductive Learning with Multiple Views. In the 24th Annual International Conference Machine Learning, ICML 2007, volume 227, pages 1159-116 1166. ACM, 2007.
[51] Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Graph Neural Networks: Review of Methods and Applications. Al Open, 1, 2020.
13


Reviews:
[{"review_id": "jSYd6jHLYin", "reviewer": "Reviewer_1Cph", "summary": "The paper studied the problem of imbalanced classification on graphs, by proposing to unify the quantity imbalance and topology imbalance together. The authors develop a label propagation algorithm that locates the topological position of the labeled nodes, and then re-weight nodes to alleviate the imbalanced data distribution. Experimental results on various benchmark datasets show the performance of the proposed model. ", "questions": "", "limitations": "", "rating": 5, "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": "The paper is easy-to-follow and well-organized. The approach and the solution to the problem are very well handled. Despite this, there lacks some insightful analysis about the proposed approach, and the empirical studies should be further improved. Here are the detailed comments:\n\n[Related work] The idea of using label propagation for imbalance classification on graphs is not novel, such as [1]. The authors may want to re-conduct the literature review in the context of imbalanced classification and discuss the difference between this paper and the previous work.  \n[1] https://dl.acm.org/doi/10.1145/3219819.3219968\n\n[Clarity] The authors stated that the imbalance classification problem “roots from the unequal quantity of labeled examples”, which is misleading and vulnerable. In general, in the setting of imbalanced classification, both the labeled set and the unlabeled set exhibit highly skewed data distribution. \n\n[Technical contribution] The technical contribution of this paper is unclear – both the idea of label propagation and node-reweighting scheme are not novel in the setting of imbalance classification. The authors may want to provide more discussion to show the technical contribution of this paper. \n\n[Evaluation] In Tab.1, the comparison experiments are conducted on CORA, Citeseer and PubMed, which are standard (balanced) node classification benchmark datasets. I don’t see any reasons why they are considered for imbalanced node classification. Moreover, all of the baselines (GCN, GAT, SGC, SAGE, CHEB) are not designed for imbalanced classification. With these, I doubt the comparison results in Tab.1 are unfair and do not stand. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1 hour"}, "extra_text": {}}, {"review_id": "fPBi2nYz6-k", "reviewer": "Reviewer_9Atj", "summary": " The issue of imbalance is a very critical problem in ML, especially in a realistic setting. In general, imbalance is quantitative, but this paper points out topological imbalance as a graph-specific problem. As a solution to topological imbalance, a method of reweighting called ReNode is proposed and its effectiveness is verified.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": " The problem of imbalance is a very real and important issue. The problem of imbalance for graphs has also been studied extensively in recent years. When we talk about imbalance issues, most of us consider quantitative imbalance, but the authors point out the problem of toplological imbalance. This is a very thought-provoking point, and I think it may become an important topic in the future. The authors state that this is a problem specific to graphs, but there may be similar issues with general data in the form of sampling imbalance. The idea of ReNode is relatively simple and the validation is experimental, but I think the results shown are good enough. I think ReNode is affected by the quantitative imbalance and the position of the labeled nodes, but are there any cases where ReNode might make things worse?  It seems to me that if we can see the bounds that the model shows during training, we will be able to adjust the weights better. Is it possible to adjust the weighting during training?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not believe that this paper will have any negative impact on society.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7 hours"}, "extra_text": {}}, {"review_id": "R-YmdeFtVOj", "reviewer": "Reviewer_t36c", "summary": "This paper first points out the topology-imbalance problem of node representation learning on graph-structured data. To address the problem (which is denoted as Topology-Imbalance Node Representation Learning, TINL), this paper presents a conflict detection-based metric (named Totoro) based on label propagation algorithm and Personalized PageRank matrix. Then, the authors introduce the ReNode algorithm that considers the Totoro of each node in semi-supervised training of GNN models. The ample experimental results show the superiority of ReNode in addressing the TINL problem. ", "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": "Originality: This paper introduces a novel research problem of semi-supervised node classification on graphs: the topology-imbalance problem. A minor concern is that the proposed solution mostly relies on the existing techniques (label propagation, PPR, and weighted training loss), although the combination of them is reasonable. \n\nQuality: The paper has good quality. The proposed problem is critical and meaningful in real-world model training. The proposed Totoro metric is highly related to the research problem. The proposed ReNode algorithm is flexible and easy to apply. The experimental results can well evaluate the effectiveness of the proposed method.\n\nClarity: The paper is well-organized and has a good writing style. The motivation, proposed method, experiments, and analysis are all introduced clearly in the paper. There are some minor problems, e.g. in Equation (3), the definition of P_v is not given very clearly in the paper.\n\nSignificance: This paper addresses the topology-imbalance problem in semi-supervised node classification, which is different from most existing works addressing the quantity-imbalance problem. I believe that pointing out this new research problem is significant to the community. The proposed method can well handle the problem, which is proved by the empirical results. \n\nProblems: I have two further concerns about this paper:\n1.Although the performance of the proposed method is validated by experiments, the method lacks a theoretical explanation or boundary to prove its effectiveness. Concretely, the designs of Totoro metric and ReNode method seem experience-based but do not have enough theory to support them.\n2.The computation of Totoro and node weights is based on the known labelled nodes, while these labels themselves may be biased due to the topology-imbalance problem. Hence, how to prove that the biased labels would generate unbiased node weights?\n\nPost Rebuttal:\nThe responses answer my questions, and the authors have revised the paper according to my previous opinions. I do not have further questions. Based on the quality I will remain my rating. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the limitation and potential negative societal impact of the paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper points out and investigates the "topology-imbalance" problem of node representation learning on graph-structured data. Unlike the "quantity-imbalance" problem, the topology imbalance is caused by the topological properties of the labeled nodes, i.e., the locations of the labeled nodes on the graph can influence how information is spread over the entire graph. As it involves the graph topology, the topology imbalance is much harder to quantify than the quantity imbalance. In this work, the authors demonstrate how this issue can impact the semi-supervised node classification based on graph neural networks (GNN). The authors then propose a simple proxy to measure the topology imbalance and re-weighting based method to correct for this imbalance. 

As pointed out by Reviewer 9Atj and t36c, this paper introduces a novel research problem of semi-supervised node classification on graphs, which I consider as a positive aspect of this paper. On the other hand, there are a couple of criticisms on the simplicity of the proposed method and lack of theoretical guarantees (Reviewer 1Cph and t36c). As this problem is previously unknown to the community and the task of solving topology imbalance is non-trivial due to the asymmetry and complexity of the graph topology, I can understand the point that the authors raise in their response: "the main purpose of this work is to reveal the topology imbalance issue to the community". Hence, the simplicity of the proposed method stems from the need to effectively communicate to the community that the problem does exist and the proposed method can be used to solve this problem to certain extent. However, several challenges remain to be addressed to fully alleviate this problem.   

Based on my own evaluation of the paper and reviews of the expert reviewers, I view the introduction of a novel research problem as a major contribution of this paper that will stimulate subsequent works in this direction. Hence, I recommend this paper for acceptance as a poster at NeurIPS2021.
Decision: Accept (Poster)