summaries: 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.  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.   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. 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.    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.
abstractText: 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 quantityand topologyimbalance 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.1
authors.name: Deli Chen
authors.name: Yankai Lin
authors.name: Guangxiang Zhao
authors.name: Xuancheng Ren
authors.name: Peng Li
authors.name: Jie Zhou
authors.name: Xu Sun
references.authors: Reid Andersen Fan R.K. Chung Kevin J. Lang
references.title: Local Graph Partitioning using PageRank Vectors
references.venue: Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006),
references.authors: Aleksandar Bojchevski Johannes Klicpera Bryan Perozzi Amol Kapoor Martin Blais Benedek Rózemberczki Michal Lukasik Stephan Günnemann
references.title: Scaling Graph Neural Networks with Approximate PageRank
references.venue: In the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,
references.authors: Eliav Buchnik Edith Cohen
references.title: Bootstrapped Graph Diffusions: Exposing the Power of Nonlinearity
references.venue: Proc. ACM Meas. Anal. Comput. Syst.,
references.authors: Mateusz Buda Atsuto Maki Maciej A. Mazurowski
references.title: A Systematic Study of the Class Imbalance Problem in Convolutional Neural Networks
references.venue: Neural Networks,
references.authors: Kaidi Cao Colin Wei Adrien Gaidon Nikos Aréchiga Tengyu Ma
references.title: Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss
references.venue: In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems
references.authors: Nitesh V Chawla Kevin W Bowyer Lawrence O Hall W Philip Kegelmeyer
references.title: SMOTE: Synthetic Minority Over-sampling Technique
references.venue: Journal of artificial intelligence research,
references.authors: Wei-Lin Chiang Xuanqing Liu Si Si Yang Li Samy Bengio Cho-Jui Hsieh
references.title: Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks
references.venue: In the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,
references.authors: Yin Cui Menglin Jia Tsung-Yi Lin Yang Song Serge J. Belongie
references.title: Class-Balanced Loss Based on Effective Number of Samples
references.venue: In IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Michaël Defferrard Xavier Bresson Pierre Vandergheynst
references.title: Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
references.venue: In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems
references.authors: Seyda Ertekin Jian Huang C Lee Giles
references.title: Active Learning for Class Imbalance Problem
references.venue: In the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval,
references.authors: Mahsa Ghorbani Anees Kazi Mahdieh Soleymani Baghshah Hamid R. Rabiee Nassir Navab
references.title: RA-GCN: Graph Convolutional Network for Disease Prediction Problems with Imbalanced Data
references.venue: arXiv preprint:
references.authors: Haixiang Guo Yijing Li Jennifer Shang Gu Mingyun Huang Yuanyue Gong Bing
references.title: Learning from Class-Imbalanced Data: Review of Methods and Applications
references.venue: Expert Syst. Appl.,
references.authors: William L. Hamilton Zhitao Ying Jure Leskovec
references.title: Inductive Representation Learning on Large Graphs
references.venue: In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017,
references.authors: Kaveh Hassani Amir Hosein Khasahmadi
references.title: Contrastive Multi-View Representation Learning on Graphs
references.venue: In the 37th International Conference on Machine Learning,
references.authors: Haibo He Edwardo A. Garcia
references.title: Learning from imbalanced data
references.venue: IEEE Trans. Knowl. Data Eng.,
references.authors: Haibo He Yang Bai Edwardo A. Garcia Shutao Li
references.title: ADASYN: Adaptive synthetic sampling approach for imbalanced learning
references.venue: In the International Joint Conference on Neural Networks, IJCNN 2008, part of the IEEE World Congress on Computational Intelligence,
references.authors: Chen Huang Yining Li Chen Change Loy Xiaoou Tang
references.title: Learning Deep Representation for Imbalanced Classification
references.venue: In the 29th IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Thomas N Kipf Max Welling
references.title: Semi-supervised Classification with Graph Convolutional Networks
references.venue: In the 5th International Conference on Learning Representations,
references.authors: Johannes Klicpera Aleksandar Bojchevski Stephan Günnemann
references.title: Predict then Propagate: Graph Neural Networks meet Personalized PageRank
references.venue: In the 7th International Conference on Learning Representations,
references.authors: Miroslav Kubat Stan Matwin
references.title: Addressing the Curse of Imbalanced Training Sets: Onesided Selection
references.venue: In the 14th International Conference on Machine Learning (ICML
references.authors: Wei Li Ruihan Bao Keiko Harimoto Deli Chen Jingjing Xu Qi Su
references.title: Modeling the Stock Relation with Graph Network for Overnight Stock Movement Prediction
references.venue: In the 29th International Joint Conference on Artificial Intelligence,
references.authors: Tsung-Yi Lin Priya Goyal Ross B. Girshick Kaiming He Piotr Dollár
references.title: Focal Loss for Dense Object Detection
references.venue: In IEEE International Conference on Computer Vision, ICCV 2017,
references.authors: Inderjeet Mani I Zhang
references.title: kNN Approach to Unbalanced Data Distributions: A Case Study Involving Information Extraction
references.venue: In Workshop on Learning from Imbalanced Datasets,
references.authors: Julian McAuley Christopher Targett Qinfeng Shi Anton Van Den Hengel
references.title: Image-based Recommendations on Styles and Substitutes
references.venue: In the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval,
references.authors: Iman Nekooeimehr Susana K Lai-Yuen
references.title: Adaptive Semi-unsupervised Weighted Oversampling (A-SUWO) for Imbalanced Datasets
references.venue: Expert Systems with Applications,
references.authors: Sunil Nishad Shubhangi Agarwal Arnab Bhattacharya Sayan Ranu
references.title: GraphReach: Position- Aware Graph Neural Networks using Reachability Estimations
references.venue: In the 30th International Joint Conference on Artificial Intelligence IJCAI,
references.authors: Lawrence Page Sergey Brin Rajeev Motwani Terry Winograd
references.title: The PageRank Citation Ranking: Bringing Order to the Web
references.venue: Technical report, Stanford InfoLab,
references.authors: Nikolay G Prokoptsev AE Alekseenko Yaroslav Aleksandrovich Kholodov
references.title: Traffic Flow Speed Prediction on Transportation Graph with Convolutional Neural Networks
references.venue: Computer research and modeling,
references.authors: Zhenyue Qin Saeed Anwar Dongwoo Kim Yang Liu Pan Ji Tom Gedeon
references.title: Position- Sensing Graph Neural Networks: Proactively Learning Nodes Relative Positions
references.venue: arXiv preprint:
references.authors: Mengye Ren Wenyuan Zeng Bin Yang Raquel Urtasun
references.title: Learning to Reweight Examples for Robust Deep Learning
references.venue: In International Conference on Machine Learning,
references.authors: Pengzhen Ren Yun Xiao Xiaojun Chang Po-Yao Huang Zhihui Li Xiaojiang Chen Xin Wang
references.title: A Survey of Deep Active Learning
references.authors: Yu Rong Wenbing Huang Tingyang Xu Junzhou Huang
references.title: The Truly Deep Graph Convolutional Networks for Node Classification
references.authors: Prithviraj Sen Galileo Namata Mustafa Bilgic Lise Getoor Brian Galligher Tina Eliassi- Rad
references.title: Collective Classification in Network Data
references.venue: AI magazine,
references.authors: Oleksandr Shchur Maximilian Mumme Aleksandar Bojchevski Stephan Günnemann
references.title: Pitfalls of Graph Neural Network Evaluation
references.venue: arXiv preprint:
references.authors: Min Shi Yufei Tang Xingquan Zhu David A. Wilson Jianxun Liu
references.title: Multi-Class Imbalanced Graph Convolutional Network Learning
references.venue: In the 29th International Joint Conference on Artificial Intelligence,
references.authors: Shuhao Shi Kai Qiao Shuai Yang L Wang J Chen Bin Yan
references.title: AdaGCN: Adaptive Boosting Algorithm for Graph Convolutional Networks on Imbalanced Node Classification
references.venue: arXiv preprint:
references.authors: Marina Sokol Konstantin Avrachenkov Paulo Gonçalves Alexey Mishenin
references.title: Generalized Optimization Framework for Graph-based Semi-supervised Learning
references.venue: In the 12th SIAM International Conference on Data Mining,
references.authors: Ivan Tomek
references.title: Two Modifications of CNN
references.venue: IEEE Transactions on Systems, Man, and Cybernetics,
references.authors: Laurens Van der Maaten Geoffrey Hinton
references.title: Visualizing Data using t-SNE
references.venue: Journal of machine learning research,
references.authors: Petar Veličković Guillem Cucurull Arantxa Casanova Adriana Romero Pietro Lio Yoshua Bengio
references.title: Graph Attention Networks
references.venue: In 6th International Conference on Learning Representations,
references.authors: Hongwei Wang Jure Leskovec
references.title: Unifying Graph Convolutional Neural Networks and Label Propagation
references.authors: Xinyue Wang Bo Liu Siyu Cao Liping Jing Jian Yu
references.title: Important Sampling based Active Learning for Imbalance Classification
references.venue: Science China Information Sciences,
references.authors: Felix Wu Amauri Souza Tianyi Zhang Christopher Fifty Tao Yu Kilian Weinberger
references.title: Simplifying Graph Convolutional Networks
references.venue: In International Conference on Machine Learning,
references.authors: Zhenqin Wu Bharath Ramsundar Evan N Feinberg Joseph Gomes Caleb Geniesse Aneesh S Pappu Karl Leswing Vijay Pande
references.title: MoleculeNet: a Benchmark for Molecular Machine Learning
references.venue: Chemical science,
references.authors: Keyulu Xu Weihua Hu Jure Leskovec Stefanie Jegelka
references.title: How Powerful are Graph Neural Networks
references.venue: In the 7th International Conference on Learning Representations,
references.authors: Yuzhe Yang Zhi Xu
references.title: Rethinking the Value of Labels for Improving Class-Imbalanced Learning
references.venue: In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems
references.authors: Zhilin Yang William W Cohen Ruslan Salakhutdinov
references.title: Revisiting Semi-supervised Learning with Graph Embeddings
references.venue: In the 33nd International Conference on Machine Learning, ICML 2016,
references.authors: Jiaxuan You Rex Ying Jure Leskovec
references.title: Position-aware Graph Neural Networks
references.venue: In the 36th International Conference on Machine Learning, ICML 2019,
references.authors: Tianxiang Zhao Xiang Zhang Suhang Wang
references.title: GraphSMOTE: Imbalanced Node Classification on Graphs with Graph Neural Networks. In WSDM ’21
references.venue: The Fourteenth ACM International Conference on Web Search and Data Mining, Virtual Event, Israel, March 8-12,
references.authors: Dengyong Zhou Christopher J.C. Burges
references.title: Spectral Clustering and Transductive Learning with Multiple Views
references.venue: In the 24th Annual International Conference on Machine Learning, ICML 2007,
references.authors: Jie Zhou Ganqu Cui Zhengyan Zhang Cheng Yang Zhiyuan Liu Maosong Sun
references.title: Graph Neural Networks: A Review of Methods and Applications
references.venue: AI Open,
sections.heading: 1 Introduction
sections.text: Graph is a widely-used data structure [51], where the nodes are connected to each other through natural or handcrafted edges. Similar to other data structures, the representation learning for node classification faces the challenge of quantity-imbalance issue, where the labeling size varies among classes and the decision boundaries of trained classifiers are mainly decided by the majority classes [46]. There have been a series of studies [35, 11, 49] handling the Quantity-Imbalance 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 to the topological class boundaries (left of Figure 1) thus interfering with the model learning.
  Present Work. For the first time, we recognize the Topology-Imbalance Node Representation Learning (short as TINL) as a graph-specific imbalance learning topic, which mainly focus on the
  1The code is available at https://github.com/victorchen96/ReNode.
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  decision boundaries shift phenomena driven by the topology imbalance in graph and is an essential component for node imbalance learning. Comparing with the well-explored QINL 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 to 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, it is difficult to construct a completely symmetric labeling set even with an abundant annotation budget.
  • Perniciousness: 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 1) respectively, resulting in a shift of decision boundaries.
  • Orthogonality: Quantity-imbalance studies [49, 8, 5] usually treat the labeled nodes of the same class as a whole and devise solutions based on the total numbers of 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.
  Exploring TINL is of great importance for node representation learning due to its ubiquity and perniciousness. However, the methods [17, 22] for quantity imbalance can be hardly applied to TINL because of the orthogonality. To remedy the topology-imbalance 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 Location (Totoro) metric to leverage the interaction among labeled nodes across the whole graph to locate their structural positions. Based on the Totoro metric, we further increase the training weights of nodes with small conflict that are highly likely to be close to topological class centers to make them play a more pivotal role during training, and vice versa (right of Figure 1). 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, we provide the sensitivity to topology imbalance as a new evaluation perspective for different GNN architectures.
sections.heading: 2 Topology-Imbalance Node Representation Learning
sections.heading: 2.1 Notations and Preliminary
sections.text: In this work, we follow the well-established semi-supervised node classification setting [47, 18] to conduct analyses and experiments. Given an undirected and unweighted graph G = (V ,E,L), where V is the node set represented by the feature matrixX ∈ Rn∗d (n = |V | is the node size and d is the node embedding dimension), E is the edge set which is represented by an adjacency matrix A ∈ Rn∗n, L ⊂ V is the labeled node set and usually we have |L| |V |, the node classification
  task is to train a classifier F (usually a GNN) to predict the class label y for the unlabeled node set U = V −L. The training sets for different classes are represented by (C1,C2, · · · ,Ck) and k is the number of classes. The labeling ratio δ = L/V is the proportion of labeled nodes in all nodes. In this work, we focus on TINL in homogeneously-connected graphs and hope to inspire future studies on the critical topology-imbalance issue.
sections.heading: 2.2 Understanding Topology Imbalance via Label Propagation
sections.text: From Figure 1, we 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 a 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 as a random walk process from labeled nodes. The convergence result Y after repeated propagation is regarded as the nodes soft-labels:
  Y = α(I − (1− α)A′)−1Y 0, (1)
  where I is the identity matrix, α ∈ (0, 1] is the random walk restart probability,A′ = D− 12AD− 12 is the adjacency matrix normalized by the diagonal degree matrixD, Y 0 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 maxj Yij . LP is a simple yet successful model [37] and can be unified with GNN models owning the message-passing mechanism [41]. From Figure 2(a), we can empirically find that there is a significant correlation between the results of LP and GCN (T/F indicates prediction is True/False).
  The LP prediction q can be viewed as the distribution of the (labeled) node influence [41] (i.e. each node is mostly influenced by which class’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 a 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 is composed of topology- and quantity-imbalance. Figure 2 illustrates two examples of node influence boundary shift. In Figure 2(b), when the uniform selection is adopted to 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 2(c), when the quantity-balanced strategy is adopted for sampling training nodes, it will be easier for 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-imbalance issue still exists and hinders the node classification learning. Hence, we can conclude that node imbalance
  learning is caused by the joint effect of TINL and QINL. Separately considering TINL or QINL will lead to a one-sided solution to node imbalance learning.
sections.heading: 2.3 Measuring Topology Imbalance by Influence Conflict
sections.text: Although we have realized that the imbalance of node topology interferes with model learning, how to measure the labeled node’s relative topological position to its class (being far away from or close to the class center) remains the key challenge in handling the topology-imbalance issue due to the complex graph connections and the unknown class labels for most nodes in the graph. As the nodes are homogeneously connected when constructing the graph, even nodes close to the class boundaries own similar characteristics to their neighbors. Thus it is unreliable to leverage the difference between the characteristics of one labeled node and its surrounding subgraphs to locate its topological position. Instead, we propose to utilize the node topology information by considering the node influence conflict across the whole graph and devise the Conflict Detection-based Topology Relative Location metric (Totoro).
  Similar to Eq (1), we calculate the Personalized PageRank [27] matrix P to measure node influence distribution from each labeled node:
  P = α(I − (1− α)A′)−1. (2)
  Node influence conflict denotes topological position. According to related studies [41, 19, 2], P can be viewed as the distribution of influence exerted outward from each node. We assume that if a labeled node v ∈ 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 v 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 v randomly walks across the entire graph as a measurement of how topologically close node v is to the center of the class it belongs to. The Totoro value of node v is computed as:
  Tv = Ex∼Pv,: [ ∑
  j∈[1,k],j 6=yv
  1 |Cj | ∑ i∈Cj Pi,x], (3)
  where yv is the ground-truth label of node v, Pv indicates the personalized PageRank probability vector for the node v. A larger Totoro value Tv indicates that node v is topologically closer to class boundaries, and vice versa. The normalization item 1/|Cj | is added to make the influence from the different classes comparable when computing conflict.
  We visualize the node labels and the Totoro values (scaled to [0, 1]) of labeled nodes in Figure 3(a). We can find that the labeled nodes with smaller Totoro values are farther away from the class boundaries, demonstrating the effectiveness of Totoro in locating the positions of labeled nodes. Besides, we sum
  the conflict of all the labeled nodes ∑
  b∈L Tv 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 3(b) shows that there is a significant negative correlation between the overall conflict and the model performance, which further demonstrates the effectiveness of Totoro in measuring the intensity of topology imbalance at the dataset level.
sections.heading: 2.4 Alleviate Topology Imbalance by Instance-wise Node Re-weighting
sections.text: In this section, we introduce ReNode, a model-agnostic training weight schedule mechanism to address TINL for general GNN encoder in a 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 2 for the training node weights based on their Totoro values:
  wv = wmin + 1
  2 (wmax − wmin)(1 + cos(
  Rank(Tv)
  |L| π)), v ∈ L (4)
  wherewv 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(Tv) is the ranking order of Tv from the smallest to the largest. The training loss LT for the quantity-balanced, topologyimbalanced node classification task is computed by the following equations:
  LT = − 1 |L| ∑ v∈L wv k∑ c=1 y∗cv log g c v, g = softmax(F(X,A,θ)), (5)
  where F denotes any GNN encoder, θ is the parameter of F , gi is the GNN output for node i, y∗i 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 a more general graph imbalance scenario where both the topology- and quantityimbalance 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 quantity-imbalance learning. 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 LQ for the quantity-imbalanced, topology-imbalanced node classification task is formalized in the following equation:
  LQ = − 1 |L| ∑ v∈L wv ¯|C| |Cj | k∑ c=1 y∗cv log g c v, (6)
  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 largescale graphs: (1) how to calculate the PageRank matrix, and (2) how to train the GNN model in an inductive setting [13]. 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 ŵ are generated by the estimation method from Andersen et al. [1] and then P̂ is
  2We also try other schedules and the cosine method works best. More details can be found in Appendix B.
  directly employed as the aggregation weights from all the other nodes regardless of their topology distance from the current node:
  g′ = softmax(P̂F ′(X, θ′)), (7)
  where F ′ can be a linear layer or a multi-layer perceptron with parameter θ′. The final training loss for large-scale graph LL follows Eq (5) and (6), and replaces w and g with ŵ and g′.
sections.heading: 3 Experiments
sections.text: 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.
sections.heading: 3.1 Datasets
sections.text: We adopt two sets of graph datasets to conduct experiments. For the transductive setting [13], we take the widely-used Plantoid paper citation graphs [33] (CORA,CiteSeer, Pubmed) and the Amazon copurchase graphs [24] (Photo,Computers) to verify the effectiveness of our method. For the inductive setting, we conduct experiments on the popular Reddit dataset [13] and the enormous MAG-Scholar dataset (coarse-grain version) [2] which owns millions of nodes and features. For each of these datasets, we repeat experiments on 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.
sections.heading: 3.2 ReNode for the Pure Topology-imbalance Issue
sections.text: Settings When considering topology-imbalance only, the labeling set takes a balanced setting and the annotation size for each class is all equal to |L|/k. Following the most widely-used semisupervised setting in node classification studies [47, 18], 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 [13] (short as SAGE), ChebGCN [9] (short as CHEB) and SGC [43]. 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 LT from section 2.4 is adopted.
  Results From Table 1, we can find that our ReNode method can effectively improve the overall performance (Weighted-F1) and the class-balance performance (Macro-F1) for all the 6 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-imbalance, we set training sets with different levels of topologyimbalance to test our method3. 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-imbalance and improve GNN performance.
sections.heading: 3.3 ReNode for the Compound Scene of TINL and QINL
sections.text: Settings When jointly considering both topology- and quantity-imbalance issues, following existing studies [5, 4], we take the step imbalance setting, in which all the minority classes have the same labeling size ni and all the majority classes have the same labeling size na = ρ ∗ ni. The imbalance ratio ρ 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 ρ 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 LQ 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 [22] (Focal) and Class Balanced Loss [8] (CB); (2) Graph-specific quantity-imbalance methods: DR-GCN [35], RA-GCN [11] and GraphSMOTE [49]. To jointly handle the topology- and quantity-imbalance 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 [18], and the labeling ratio δ is set to 5%.
  Results From Table 3 (Macro-F1 is reported here for a fair comparison with these methods designed for class-balance performance), we can find that our ReNode method significantly outperforms both the general and the graph-specific quantity-imbalance methods in most situations by simultaneously alleviating the topology- and quantity-imbalance issues. Even when the training set is severely quantity-imbalanced (ρ=10), our method still effectively alleviates the imbalance issue and promotes model performance well. The performance of the quantity-imbalance methods from the general 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-imbalance methods can surpass the graph-specific quantity-imbalance methods, which demonstrates that the node imbalance learning can be further solved by jointly handling the topology- and quantity-imbalance issues instead of considering the quantity-imbalance issue only.
  3The settings of the dataset topology-imbalance levels is shown in Appendix C. 4The three graph-specific methods have special operations for the training loss, which can be hardly combined
  with our method.
sections.heading: 3.4 ReNode for Large-scale Graphs
sections.text: Settings We conduct experiments on the two large-scale datasets: Reddit and MAG-Scholar, to verify the effectiveness of our ReNode method in 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] 5. For QINL, we take the uniform selection to sample training nodes to be consistent with PPRGo. The training loss LL from section 2.4 is adopted. Both baseline and our methods are not combined with any quantity-imbalance method.
  Results In Figure 4, we 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 to 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 is 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 the labeled nodes is negligible, our method exhibits the cold start problem.
sections.heading: 4 Discussions
sections.heading: 4.1 Evaluating GNNs from the Aspect of Topology-Imbalance Sensitivity
sections.text: In Figure 5, we evaluate the GNN’s capability for handling topology-imbalance and find that different GNNs present significant difference in the topology-imbalance sensitivity across multiple datasets. The GCN model is susceptible to the topology-imbalance level of the graph and its performance decays greatly when the topology-imbalance increases. On the opposite, the GAT model is less sensitive to the topology-imbalance level and can achieve the best results when the topology-imbalance level is high. The PPNP model can achieve ideal performance when the topology-imbalance level is low, and its performance does not drop as sharply as GCN when the topology-imbalance level is high. We analyze the reason lies in that: (1) the aggregation operation of GCN is equivalent to directly
  5We do not implement other inductive backbone GNN models like Cluster-GCN [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-imbalance 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-imbalance situation but hinders the model performance when the graph topology-imbalance level is low and 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.
  Shchur et al. [34] notice that the performance ranking of GNNs varies with the training set selection. Hence, existing node classification studies [32, 14] usually repeat experiments multiple times with different training sets to 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 topology-imbalance sensitivity as a new aspect in evaluating the performance of different GNN architectures.
sections.heading: 4.2 Limitations of Method
sections.text: 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-connected graphs (linked nodes are expected to be similar, such as the various datasets in experiments), and it needs a further update for heterogeneously-connected graphs (such as protein networks). Besides, the ReNode method improves less when the graph connectivity is 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.
sections.heading: 5 Related Work
sections.text: 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 classimbalanced quantity distribution [15], where the model’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 [31, 10, 42] and Re-sampling [6, 16, 25] are two classical examples designed to construct a quantity-balanced training set . On the other hand, Re-weighting is a 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, 5]. 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-weighting, our ReNode method is a more fine-grained one and assign weights to each node individually.
  There have been quantity-imbalance studies (Tomek links [38], NearMiss [23], One-Sided Selection [20]) trying to 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-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.
  Graph data structure owns a wide range of applications, such as social media [13], stock exchange [21], shopping [34], medicine [44], transportation [28] and so on. Similar to other data structures, graph node representation learning also suffer from the quantity-imbalance issue [35]. Apart from the universal quantity-balance approaches introduced in Section 5 which can be transferred to the graph scene, there are some graph-specific quantity-imbalance methods recently proposed. DR-GCN [35] propose two types of regularization to tackle quantity imbalance: class-conditioned adversarial training and unlabeled nodes latent distribution constraint. RA-GCN [11] 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-imbalance 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.
  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 to locate the relative positions to the class boundary for the labeling 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 existing studies [48, 29] treat all the anchor nodes the same and ignore the class difference.
sections.heading: 6 Conclusion and Future Work
sections.text: In this work, we recognize the topology-imbalance node representation learning (TINL) as a graphspecific imbalance learning problem that has not been studied so far. We find that the topologyimbalance issue widely exists in graphs and severely hinders the learning of node classification. We unify TINL with the quantity-imbalance node representation learning (QINL) by considering the shift of the node influence boundaries from true class boundaries. To measure the degree of topology imbalance, we 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-imbalance sensitivity as a new metric to evaluate GNNs.
  Considering the importance of the topology-imbalance issue and the limitations of our approach, advanced methods with stronger theoretical or experimental support are expected in future work. Moreover, since topology imbalance is widespread in graph-related tasks other than node classification, how to measure and solve the topology-imbalance issues in broader graph scopes remains a meaningful challenge for future study.
sections.heading: 7 Acknowledgement
sections.text: We appreciate all the thoughtful and insightful suggestions from reviews. This work was supported in part by a Tencent Research Grant and National Natural Science Foundation of China (No. 61673028). Xu Sun is the corresponding author of this paper.
title: Topology-Imbalance Learning for Semi-Supervised Node Classification