# Mastering Long-Tail Complexity on Graphs: Characterization, Learning, and Generalization

arXiv: https://arxiv.org/abs/2305.09938 · HTML: https://mlsanity.com/paper/2305.09938/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 69 references that are in the map.
- First posted on arXiv 17 May 2023.

## Builds on (most cited first, 30 of 39)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss](https://mlsanity.com/paper/1906.07413/) (2019)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Contrastive Multi-View Representation Learning on Graphs](https://mlsanity.com/paper/2006.05582/) (2020)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training](https://mlsanity.com/paper/2006.09963/) (2020)
- [Invariant Information Clustering for Unsupervised Image Classification and Segmentation](https://mlsanity.com/paper/1807.06653/) (2018)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [Deep Long-Tailed Learning: A Survey](https://mlsanity.com/paper/2110.04596/) (2021)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [Few-Shot Learning with Graph Neural Networks](https://mlsanity.com/paper/1711.04043/) (2017)
- [Wiki-CS: A Wikipedia-Based Benchmark for Graph Neural Networks](https://mlsanity.com/paper/2007.02901/) (2020)
- [Rethinking the Value of Labels for Improving Class-Imbalanced Learning](https://mlsanity.com/paper/2006.07529/) (2020)
- [The Benefit of Multitask Representation Learning](https://mlsanity.com/paper/1505.06279/) (2015)
- [Graph-based Anomaly Detection and Description: A Survey](https://mlsanity.com/paper/1404.4679/) (2014)
- [ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations](https://mlsanity.com/paper/1911.07979/) (2019)
- [A Semi-supervised Graph Attentive Network for Financial Fraud Detection](https://mlsanity.com/paper/2003.01171/) (2020)
- [Edge-labeling Graph Neural Network for Few-shot Learning](https://mlsanity.com/paper/1905.01436/) (2019)
- [An Empirical Study of Graph Contrastive Learning](https://mlsanity.com/paper/2109.01116/) (2021)
- [Meta-GNN: On Few-shot Node Classification in Graph Meta-learning](https://mlsanity.com/paper/1905.09718/) (2019)
- [InfoGCL: Information-Aware Graph Contrastive Learning](https://mlsanity.com/paper/2110.15438/) (2021)
- [Graph Convolutional Networks with EigenPooling](https://mlsanity.com/paper/1904.13107/) (2019)
- [Inferring Networks of Substitutable and Complementary Products](https://mlsanity.com/paper/1506.08839/) (2015)
- [HDMI: High-order Deep Multiplex Infomax](https://mlsanity.com/paper/2102.07810/) (2021)
- [DPGN: Distribution Propagation Graph Network for Few-shot Learning](https://mlsanity.com/paper/2003.14247/) (2020)
- [Label-Imbalanced and Group-Sensitive Classification under Overparameterization](https://mlsanity.com/paper/2103.01550/) (2021)
- [Simple and Efficient Heterogeneous Graph Neural Network](https://mlsanity.com/paper/2207.02547/) (2022)

## Built on by (most cited first, 8 of 8)

- [PyG-SSL: A Graph Self-Supervised Learning Toolkit](https://mlsanity.com/paper/2412.21151/) (2024)
- [LENSLLM: Unveiling Fine-Tuning Dynamics for LLM Selection](https://mlsanity.com/paper/2505.03793/) (2025)
- [Are Vision LLMs Road-Ready? A Comprehensive Benchmark for Safety-Critical Driving Video Understanding](https://mlsanity.com/paper/2504.14526/) (2025)
- [Towards Heterogeneous Long-tailed Learning: Benchmarking, Metrics, and Toolbox](https://mlsanity.com/paper/2307.08235/) (2023)
- [HeroFilter: Adaptive Spectral Graph Filter for Varying Heterophilic Relations](https://mlsanity.com/paper/2510.10864/) (2025)
- [SaVe-TAG: LLM-based Interpolation for Long-Tailed Text-Attributed Graphs](https://mlsanity.com/paper/2410.16882/) (2024)
- [EVINET: Towards Open-World Graph Learning via Evidential Reasoning Network](https://mlsanity.com/paper/2506.07288/) (2025)
- [Towards Federated Long-Tailed Graph Learning: An Energy-Guided Dual Decoupling Approach](https://mlsanity.com/paper/2606.24237/) (2026)

## Abstract (arXiv)

In the context of long-tail classification on graphs, the vast majority of existing work primarily revolves around the development of model debiasing strategies, intending to mitigate class imbalances and enhance the overall performance. Despite the notable success, there is very limited literature that provides a theoretical tool for characterizing the behaviors of long-tail classes in graphs and gaining insight into generalization performance in real-world scenarios. To bridge this gap, we propose a generalization bound for long-tail classification on graphs by formulating the problem in the fashion of multi-task learning, i.e., each task corresponds to the prediction of one particular class. Our theoretical results show that the generalization performance of long-tail classification is dominated by the overall loss range and the task complexity. Building upon the theoretical findings, we propose a novel generic framework HierTail for long-tail classification on graphs. In particular, we start with a hierarchical task grouping module that allows us to assign related tasks into hypertasks and thus control the complexity of the task space; then, we further design a balanced contrastive learning module to adaptively balance the gradients of both head and tail classes to control the loss range across all tasks in a unified fashion. Extensive experiments demonstrate the effectiveness of HierTail in characterizing long-tail classes on real graphs, which achieves up to 12.9% improvement over the leading baseline method in accuracy.