# Active Learning on Trees and Graphs

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jan 2013.

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

- [GALAXY: Graph-based Active Learning at the Extreme](https://mlsanity.com/paper/2202.01402/) (2022)
- [Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries](https://mlsanity.com/paper/2102.00504/) (2021)
- [Efficient Algorithms for Learning Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2405.00853/) (2024)
- [Online-to-PAC generalization bounds under graph-mixing dependencies](https://mlsanity.com/paper/2410.08977/) (2024)
- [Semi-Supervised Laplace Learning on Stiefel Manifolds](https://mlsanity.com/paper/2308.00142/) (2023)
- [Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2506.23186/) (2025)
- [Sensor Placement for Learning in Flow Networks](https://mlsanity.com/paper/2401.02438/) (2023)
- [Self-Directed Learning of Convex Labelings on Graphs](https://mlsanity.com/paper/2409.01428/) (2024)
- [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)

We investigate the problem of active learning on a given tree whose nodes are assigned binary labels in an adversarial way. Inspired by recent results by Guillory and Bilmes, we characterize (up to constant factors) the optimal placement of queries so to minimize the mistakes made on the non-queried nodes. Our query selection algorithm is extremely efficient, and the optimal number of mistakes on the non-queried nodes is achieved by a simple and efficient mincut classifier. Through a simple modification of the query selection algorithm we also show optimality (up to constant factors) with respect to the trade-off between number of queries and number of mistakes on non-queried nodes. By using spanning trees, our algorithms can be efficiently applied to general graphs, although the problem of finding optimal and efficient active learning algorithms for general graphs remains open. Towards this end, we provide a lower bound on the number of mistakes made on arbitrary graphs by any active learning algorithm using a number of queries which is up to a constant fraction of the graph size.