# S2: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jun 2015.

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

- [GALAXY: Graph-based Active Learning at the Extreme](https://mlsanity.com/paper/2202.01402/) (2022)
- [RIM: Reliable Influence-based Active Learning on Graphs](https://mlsanity.com/paper/2110.14854/) (2021)
- [Data driven semi-supervised learning](https://mlsanity.com/paper/2103.10547/) (2021)
- [Partition-Based Active Learning for Graph Neural Networks](https://mlsanity.com/paper/2201.09391/) (2022)
- [Uncertainty for Active Learning on Graphs](https://mlsanity.com/paper/2405.01462/) (2024)
- [Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries](https://mlsanity.com/paper/2102.00504/) (2021)
- [Model-Change Active Learning in Graph-Based Semi-Supervised Learning](https://mlsanity.com/paper/2110.07739/) (2021)
- [Poisson Reweighted Laplacian Uncertainty Sampling for Graph-based Active Learning](https://mlsanity.com/paper/2210.15786/) (2022)
- [Maximizing and Satisficing in Multi-armed Bandits with Graph Information](https://mlsanity.com/paper/2108.01152/) (2021)
- [A label-efficient two-sample test](https://mlsanity.com/paper/2111.08861/) (2021)
- [Efficient Algorithms for Learning Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2405.00853/) (2024)
- [Robust Offline Active Learning on Graphs](https://mlsanity.com/paper/2408.07941/) (2024)
- [Advanced Tutorial: Label-Efficient Two-Sample Tests](https://mlsanity.com/paper/2501.03568/) (2025)
- [Graph Laplacian-based Bayesian Multi-fidelity Modeling](https://mlsanity.com/paper/2409.08211/) (2024)
- [MALADY: Multiclass Active Learning with Auction Dynamics on Graphs](https://mlsanity.com/paper/2409.09475/) (2024)
- [Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2506.23186/) (2025)
- [A-Optimal Active Learning](https://mlsanity.com/paper/2110.09585/) (2021)
- [Active learning using region-based sampling](https://mlsanity.com/paper/2303.02721/) (2023)
- [An Approximation Algorithm for Graph Label Selection](https://mlsanity.com/paper/2605.18623/) (2026)
- [Active Learning on Adversarially Corrupted Graphs](https://mlsanity.com/paper/2607.04869/) (2026)

## Abstract (arXiv)

This paper investigates the problem of active learning for binary label prediction on a graph. We introduce a simple and label-efficient algorithm called S2 for this task. At each step, S2 selects the vertex to be labeled based on the structure of the graph and all previously gathered labels. Specifically, S2 queries for the label of the vertex that bisects the *shortest shortest* path between any pair of oppositely labeled vertices. We present a theoretical estimate of the number of queries S2 needs in terms of a novel parametrization of the complexity of binary functions on graphs. We also present experimental results demonstrating the performance of S2 on both real and synthetic data. While other graph-based active learning algorithms have shown promise in practice, our algorithm is the first with both good performance and theoretical guarantees. Finally, we demonstrate the implications of the S2 algorithm to the theory of nonparametric active learning. In particular, we show that S2 achieves near minimax optimal excess risk for an important class of nonparametric classification problems.