# GALAXY: Graph-based Active Learning at the Extreme

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 32 references that are in the map.
- First posted on arXiv 3 Feb 2022.

## Builds on (most cited first, 16 of 16)

- [Deep Bayesian Active Learning with Image Data](https://mlsanity.com/paper/1703.02910/) (2017)
- [MedMNIST v2 -- A large-scale lightweight benchmark for 2D and 3D biomedical image classification](https://mlsanity.com/paper/2110.14795/) (2021)
- [Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds](https://mlsanity.com/paper/1906.03671/) (2019)
- [Adversarial Active Learning for Deep Networks: a Margin Based Approach](https://mlsanity.com/paper/1802.09841/) (2018)
- [Batch Active Learning at Scale](https://mlsanity.com/paper/2107.14263/) (2021)
- [FairBatch: Batch Selection for Model Fairness](https://mlsanity.com/paper/2012.01696/) (2020)
- [Discriminative Active Learning](https://mlsanity.com/paper/1907.06347/) (2019)
- [Gone Fishing: Neural Active Learning with Fisher Embeddings](https://mlsanity.com/paper/2106.09675/) (2021)
- [Deep Active Learning over the Long Tail](https://mlsanity.com/paper/1711.00941/) (2017)
- [SIMILAR: Submodular Information Measures Based Active Learning In Realistic Scenarios](https://mlsanity.com/paper/2107.00717/) (2021)
- [Active Learning at the ImageNet Scale](https://mlsanity.com/paper/2111.12880/) (2021)
- [Similarity Search for Efficient Active Learning and Search of Rare Concepts](https://mlsanity.com/paper/2007.00077/) (2020)
- [S2: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification](https://mlsanity.com/paper/1506.08760/) (2015)
- [Improved Algorithms for Agnostic Pool-based Active Classification](https://mlsanity.com/paper/2105.06499/) (2021)
- [Active Learning on Trees and Graphs](https://mlsanity.com/paper/1301.5112/) (2013)
- [Diffusion-based Deep Active Learning](https://mlsanity.com/paper/2003.10339/) (2020)

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

- [A Survey on Deep Active Learning: Recent Advances and New Frontiers](https://mlsanity.com/paper/2405.00334/) (2024)
- [An Experimental Design Framework for Label-Efficient Supervised Finetuning of Large Language Models](https://mlsanity.com/paper/2401.06692/) (2024)
- [LabelBench: A Comprehensive Framework for Benchmarking Adaptive Label-Efficient Learning](https://mlsanity.com/paper/2306.09910/) (2023)
- [Algorithm Selection for Deep Active Learning with Imbalanced Datasets](https://mlsanity.com/paper/2302.07317/) (2023)
- [Uncertainty for Active Learning on Graphs](https://mlsanity.com/paper/2405.01462/) (2024)
- [A Cross-Domain Benchmark for Active Learning](https://mlsanity.com/paper/2408.00426/) (2024)
- [Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation](https://mlsanity.com/paper/2312.09196/) (2023)
- [AHA: Human-Assisted Out-of-Distribution Generalization and Detection](https://mlsanity.com/paper/2410.08000/) (2024)
- [Out-of-Distribution Learning with Human Feedback](https://mlsanity.com/paper/2408.07772/) (2024)
- [AnchorAL: Computationally Efficient Active Learning for Large and Imbalanced Datasets](https://mlsanity.com/paper/2404.05623/) (2024)
- [Deep Active Learning in the Open World](https://mlsanity.com/paper/2411.06353/) (2024)
- [Learning from the Best: Active Learning for Wireless Communications](https://mlsanity.com/paper/2402.04896/) (2024)
- [How To Overcome Confirmation Bias in Semi-Supervised Image Classification By Active Learning](https://mlsanity.com/paper/2308.08224/) (2023)
- [COBRA: COmBinatorial Retrieval Augmentation for Few-Shot Adaptation](https://mlsanity.com/paper/2412.17684/) (2024)
- [Labeled TrustSet Guided: Batch Active Learning with Reinforcement Learning](https://mlsanity.com/paper/2604.12303/) (2026)
- [Active Few-Shot Classification: a New Paradigm for Data-Scarce Learning Settings](https://mlsanity.com/paper/2209.11481/) (2022)
- [Class-Balanced and Reinforced Active Learning on Graphs](https://mlsanity.com/paper/2402.10074/) (2024)
- [Improving Task Diversity in Label Efficient Supervised Finetuning of LLMs](https://mlsanity.com/paper/2507.21482/) (2025)
- [EPS: Efficient Patch Sampling for Video Overfitting in Deep Super-Resolution Model Training](https://mlsanity.com/paper/2411.16312/) (2024)
- [Active Learning Methods for Efficient Data Utilization and Model Performance Enhancement](https://mlsanity.com/paper/2504.16136/) (2025)
- [Batch Bayesian Active Learning with Partial Batch Label Sampling](https://mlsanity.com/paper/2510.09877/) (2025)
- [Active Learning with Task-Driven Representations for Messy Pools](https://mlsanity.com/paper/2510.25926/) (2025)
- [When Imbalance Comes Twice: Active Learning under Simulated Class Imbalance and Label Shift in Binary Semantic Segmentation](https://mlsanity.com/paper/2601.06209/) (2026)
- [DREAM: Dual-Standard Semantic Homogeneity with Dynamic Optimization for Graph Learning with Label Noise](https://mlsanity.com/paper/2601.17449/) (2026)
- [An Approximation Algorithm for Graph Label Selection](https://mlsanity.com/paper/2605.18623/) (2026)
- [Active Learning with Foundation Model Priors: Efficient Learning under Class Imbalance](https://mlsanity.com/paper/2606.07630/) (2026)
- [CuBAS: Information Geometric Curvature-Based Adaptive Sampling for Supervised Classification](https://mlsanity.com/paper/2607.03145/) (2026)
- [FunnelAL: Retrieve-then-Rank Active Learning for Single-Class Discovery](https://mlsanity.com/paper/2607.25276/) (2026)
- [Overcoming Shortcut Learning in Graph Neural Networks through Active Explanation Guidance](https://mlsanity.com/paper/2608.14121/) (2026)

## Abstract (arXiv)

Active learning is a label-efficient approach to train highly effective models while interactively selecting only small subsets of unlabelled data for labelling and training. In "open world" settings, the classes of interest can make up a small fraction of the overall dataset -- most of the data may be viewed as an out-of-distribution or irrelevant class. This leads to extreme class-imbalance, and our theory and methods focus on this core issue. We propose a new strategy for active learning called GALAXY (Graph-based Active Learning At the eXtrEme), which blends ideas from graph-based active learning and deep learning. GALAXY automatically and adaptively selects more class-balanced examples for labeling than most other methods for active learning. Our theory shows that GALAXY performs a refined form of uncertainty sampling that gathers a much more class-balanced dataset than vanilla uncertainty sampling. Experimentally, we demonstrate GALAXY's superiority over existing state-of-art deep active learning algorithms in unbalanced vision classification settings generated from popular datasets.