# Algebraic Multigrid Acceleration for Efficient Label Spreading

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 41 references that are in the map.
- First posted on arXiv 26 Aug 2026.

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

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [Learning from Noisy Labels with Deep Neural Networks: A Survey](https://mlsanity.com/paper/2007.08199/) (2020)
- [The Faiss library](https://mlsanity.com/paper/2401.08281/) (2024)
- [Label Propagation for Deep Semi-supervised Learning](https://mlsanity.com/paper/1904.04717/) (2019)
- [Human uncertainty makes classification more robust](https://mlsanity.com/paper/1908.07086/) (2019)
- [Efficient Diffusion on Region Manifolds: Recovering Small Objects with Compact CNN Representations](https://mlsanity.com/paper/1611.05113/) (2016)
- [Is one annotation enough? A data-centric image classification benchmark for noisy and ambiguous label estimation](https://mlsanity.com/paper/2207.06214/) (2022)
- ["Garbage In, Garbage Out" Revisited: What Do Machine Learning Application Papers Report About Human-Labeled Training Data?](https://mlsanity.com/paper/2107.02278/) (2021)
- [Are LLMs Better than Reported? Detecting Label Errors and Mitigating Their Effect on Model Performance](https://mlsanity.com/paper/2410.18889/) (2024)
- [Improving Label Error Detection and Elimination with Uncertainty Quantification](https://mlsanity.com/paper/2405.09602/) (2024)
- [Probabilistic Label Spreading: Efficient and Consistent Estimation of Soft Labels with Epistemic Uncertainty on Graphs](https://mlsanity.com/paper/2602.04574/) (2026)

## Abstract (arXiv)

Modern machine learning models rely on large amounts of labeled data. However, manual annotation of large-scale datasets is expensive and time-consuming. Label spreading is a semi-supervised learning technique that addresses this challenge by propagating information from a few labeled examples to a larger pool of unlabeled data. Despite its effectiveness, its application to large-scale, high-dimensional datasets is limited by computational costs and memory constraints. To address these limitations, we propose Algebraic Multigrid Acceleration for Efficient Label Spreading (AMELS), an efficient label spreading framework that improves scalability by fast construction of neighborhood graphs and the incorporation of algebraic multigrid solvers. The latter is an iterative solver that replaces the ordinary random walk iteration typically performed in label spreading. Due to the multilevel nature of algebraic multigrid solvers, AMELS spreads given label information across a graph of any size in a single multigrid cycle. We demonstrate that AMELS achieves significant runtime reductions compared to existing implementations while also being more robust to hyperparameter choices in terms of both runtime and classification accuracy. Our framework therefore enables efficient label spreading on large-scale image datasets and produces accurate labels even when only a few labeled samples are available.