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 http://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
Pila 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))a 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 's 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)1--
(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 quantityiimbllnnee 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
model training phase. Active learning [3 TO 42 and Re-sampling 6 16 25 are two classical examples designed to construct a quantity-
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.
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": "qtP-eFDf87S", "reviewer": "Reviewer_84DB", "summary": "This paper proposes an instance-reweighting scheme for GNNs based on the idea that examples \"inside\" the class's cluster should be more important than ones which are on the boundary.  A heuristic (Totoro) is proposed for the class weight, based on how many other classes the personalized pagerank propagation goes through.", "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": "* **Significance**:  While I like some aspects of the write-up, I find there's some blind spots in the work as it currently stands, which limit its significance:\n\n  *   The proposed method has a strong assumption that the data is homophilous (edges are more likely to link nodes sharing the same label, so clusters of the same label are present in the data).  Should this not hold, all nodes are on the graph's \"class boundary\" (per the Totoro PPR definition). While true for many academic datasets which are hand-selected for this condition (especially citation networks like Cora, etc), this is just *not* the case for most real GNN datasets.  The authors acknowledge this limitation, but the phenomenon needs to be studied in my opinion.\n\n  *   In both absolute *and* relative terms, the performance gains by applying ReNode for all datasets is actually quite low.  (~1% absolute, ~<2% relative?)  This seems to indicate that ReNode doesn't really address imbalance much better than other proposed approaches (e.g. consider Table 3).  Furthermore it seems like there's no baseline in Table 3 that considers both kinds of imbalance (TINL and QINL)?\n\n  *  There seems to be no study of alternative reweighting strategies to validate the choice of PPR.  There are probably dozens of alternatives possible here -- this choice needs to be defended.\n\n  *  Understanding how ReNode works with other models (than GCN) is necessary to understand its significance.  For example, Figure 5 shows that there may be some difference in sensitivity between methods, but we don't know how ReNode effects different graph convolutions.\n\n* **Clarity**:  The paper is well written and easy to understand.  \n\n* **Quality**:  Generally high, but aside from the issues mentioned in significance, there were other obvious analysis that need to be performed:\n\n  *  A more thorough analysis of imbalance and its effect on performance (only two imbalance ratios [5,10] are used...it'd be nice to understand how ReNode (and baselines) performed as imbalance was more smoothly varied.\n\n  *  There's an assertion that  GAT is the least sensitive to topological imbalance (Figure 5), but quite frankly, I don't know if I believe this -- GAT (as the most parameterized model) is much more capable of overfitting.  Instead, I wonder if the hyper-parameters were not adequately searched for all 3 methods for each imbalance setting.\n\n* **Originality**:  There's a number of work out there which considers quantity and graph imbalance, so the onus is on ReNode to show that its unique.  I'm curious if related work for graphs *really* doesn't consider topology imbalance.  To be more specific, some of the regularizations to tackle quantity imbalance might end up encoding topology indirectly (e.g. via unlabeled nodes, edge generation, or something else).  \n\n  *  There has also been a lot of work studying PPR & GNNs lately, but the authors seem to do an ok job surveying the field.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There's a brief discussion about the limitation of the method due to its homophily assumption, but I think this is a big blocker that we need to understand more fully.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "f51DM7zcQ6K", "reviewer": "Reviewer_PVVk", "summary": "The authors concerns the topological imbalance problem in node classification problem. The imbalance caused by  asymmetric topological structure during the semi-supervised learning process. The authors introduces the intuition with classical label propagation problem and extended it to the case of learning GNN. To alleviate the pain of the imbalance issue the author introduced the Node reweighting loss, which puts more effort on learning with nodes that have less distance weighted conflicts. \n\n", "questions": "", "limitations": "", "rating": 6, "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": "clarity: Overall the paper is well written and easy to follow.\n\n\noriginality: I am not sure if topo imbalance problem proposed by the author is entirely new. Seems natural in Label Propagation type problem.  Please confirm.\n\n\nsignificance: Ok\n\n\nquality: The empirical study seems promising. I appreciate the scientific and transparent experimental section.\nHowever, the approach proposed by the authors seems more like a loss type of heuristic, lacking analysis why it needs to be designed in this form and what is the trade off by applying such loss, etc.  In the empirical study section, it seems that the benchmarks are not convincing enough. The ReNode approach may benefit from comparisons with other stronger benchmarks with potential to solve the topo imbalance problem. (please confirm if does not exist).\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": "0.6"}, "extra_text": {}}, {"review_id": "QWDREPkpAg0", "reviewer": "Reviewer_WAqa", "summary": "Authors study a problem named topology imbalance which is led from the topological difference of labelled nodes in a given graph. It degrades the performance of node classifiers by 'shifting' the decision boundary. The main contributions of this paper are (1) it points out the topology imbalance problem in node classification tasks; (2) it proposes a metric (Totoro) to measure the topology imbalance; (3) it designs an annealing method to reweight samples based on their topological importance; (4) authors provide vast experimental results over multiple scenarios, datasets, and baselines.", "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": "The topology imbalance problem is very interesting and should be paid more attention. It is clearly illustrated by the authors that labelled nodes at different positions should be weighted differently. Figure 3 is quite impressive that the proposed metric Totoro has strong indication about the position of the labelled nodes and the metric value is directly related with the performance of downstream node classifiers. Overall the presentation is good and I can follow most ideas presented. Specifically, I have following concerns:\n(1) A very important assumption this paper holds is that the decision boundary of Label propagation methods and GNNs methods are aligned. Authors verify this by a visualization in Figure 2(a) but this is very messy and I feel confused about the meaning of the legends (e.g., GCN=T, LP=T).\n(2) Authors empirically proves that nodes with large Totoro values are far away from the decision boundary and should be set large weights during training. Experiment results indeed demonstrate the performance gaining. However, it is still non-intuitive. Samples far away from the decision boundary should be easy cases and contribute less to the classification in many models (refer to SVM). Assigning larger weights to the easy samples is not intuitive for me. Also, the weight computed based on Rank of the Totoro metric is quite heuristic. It is fine but it would be better if authors can point out the direct connection between model performance, specific Totoro values and sample weights.\n(3) The presentation of the core idea from line 120 to line 122 can be improved.  The operation '*' in Eq. (6) and (7) is multiplication? If so try to replace it with other symbols since '*' represents convolution in many cases. Line 198 'GTA' should be 'GAT'. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I agree with authors mentioned in the checklist that their submission has no obvious potential negative societal effect.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigates the issue that nodes in a graph may have different local topology. This imbalance of topology may induce bias in node classification task. The paper proposes a solution inspired by classic label propagation. Nodes far away from decision boundary are assigned heavier weights in learning, whereas nodes near decision boundary are considered less important. 

While reviewers generally thought the paper does bring up an important and interesting problem, they did have many concerns that were not addressed after rebuttal. 

1) the problem statement (topology imbalance) lacks a rigorous / formal definition. This makes it harder to appreciate the proposed loss. 
2) the assumption (homophilous) may be too strong.
3) the proposed approach is too simplistic: nodes near the decision boundary should be used smartly, not be discarded.




Decision: Accept (Poster)