# Poisson Reweighted Laplacian Uncertainty Sampling for Graph-based Active Learning

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 56 references that are in the map.
- First posted on arXiv 27 Oct 2022.

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

- [FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence](https://mlsanity.com/paper/2001.07685/) (2020)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [An Introduction to Variational Autoencoders](https://mlsanity.com/paper/1906.02691/) (2019)
- [Deep Bayesian Active Learning with Image Data](https://mlsanity.com/paper/1703.02910/) (2017)
- [EMNIST: an extension of MNIST to handwritten letters](https://mlsanity.com/paper/1702.05373/) (2017)
- [Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operator](https://mlsanity.com/paper/1801.10108/) (2018)
- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Active Learning for Graph Embedding](https://mlsanity.com/paper/1705.05085/) (2017)
- [Graph Policy Network for Transferable Active Learning on Graphs](https://mlsanity.com/paper/2006.13463/) (2020)
- [Poisson Learning: Graph Based Semi-Supervised Learning At Very Low Label Rates](https://mlsanity.com/paper/2006.11184/) (2020)
- [Analysis of p-Laplacian Regularization in Semi-Supervised Learning](https://mlsanity.com/paper/1707.06213/) (2017)
- [Rethinking deep active learning: Using unlabeled data at model training](https://mlsanity.com/paper/1911.08177/) (2019)
- [Attribute Surrogates Learning and Spectral Tokens Pooling in Transformers for Few-shot Learning](https://mlsanity.com/paper/2203.09064/) (2022)
- [The game theoretic p-Laplacian and semi-supervised learning with few labels](https://mlsanity.com/paper/1711.10144/) (2017)
- [Large Data and Zero Noise Limits of Graph-Based Semi-Supervised Learning Algorithms](https://mlsanity.com/paper/1805.09450/) (2018)
- [S2: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification](https://mlsanity.com/paper/1506.08760/) (2015)
- [Properly-weighted graph Laplacian for semi-supervised learning](https://mlsanity.com/paper/1810.04351/) (2018)
- [Rates of Convergence for Laplacian Semi-Supervised Learning with Low Labeling Rates](https://mlsanity.com/paper/2006.02765/) (2020)
- [Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data](https://mlsanity.com/paper/1710.10364/) (2017)
- [MaxiMin Active Learning in Overparameterized Model Classes}](https://mlsanity.com/paper/1905.12782/) (2019)
- [Diffusion-based Deep Active Learning](https://mlsanity.com/paper/2003.10339/) (2020)
- [Model-Change Active Learning in Graph-Based Semi-Supervised Learning](https://mlsanity.com/paper/2110.07739/) (2021)
- [Minimum-Margin Active Learning](https://mlsanity.com/paper/1906.00025/) (2019)
- [Cautious Active Clustering](https://mlsanity.com/paper/2008.01245/) (2020)
- [LaplaceNet: A Hybrid Graph-Energy Neural Network for Deep Semi-Supervised Classification](https://mlsanity.com/paper/2106.04527/) (2021)
- [Graph-Based Active Learning: A New Look at Expected Error Minimization](https://mlsanity.com/paper/1609.00845/) (2016)
- [Efficient Graph-Based Active Learning with Probit Likelihood via Gaussian Approximations](https://mlsanity.com/paper/2007.11126/) (2020)

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

- [Consistency of semi-supervised learning, stochastic tug-of-war games, and the p-Laplacian](https://mlsanity.com/paper/2401.07463/) (2024)
- [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)
- [A signal separation view of classification](https://mlsanity.com/paper/2509.24140/) (2025)
- [Topology-Aware Active Learning on Graphs](https://mlsanity.com/paper/2510.25892/) (2025)
- [Fermat Active Laplace Learning for Semi-Supervised Hyperspectral Image Classification](https://mlsanity.com/paper/2608.02483/) (2026)

## Abstract (arXiv)

We show that uncertainty sampling is sufficient to achieve exploration versus exploitation in graph-based active learning, as long as the measure of uncertainty properly aligns with the underlying model and the model properly reflects uncertainty in unexplored regions. In particular, we use a recently developed algorithm, Poisson ReWeighted Laplace Learning (PWLL) for the classifier and we introduce an acquisition function designed to measure uncertainty in this graph-based classifier that identifies unexplored regions of the data. We introduce a diagonal perturbation in PWLL which produces exponential localization of solutions, and controls the exploration versus exploitation tradeoff in active learning. We use the well-posed continuum limit of PWLL to rigorously analyze our method, and present experimental results on a number of graph-based image classification problems.