  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.
