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.

本文研究了在图上进行二元标签预测的主动学习问题，引入了一种被称为S2的简单标记效率算法，其中S2基于图的结构和之前收集的所有标签选择要标记的顶点。我们通过一种新颖的复杂性参数化方法，给出了S2需要查询的问题数量的理论估计，并呈现了S2在真实数据和合成数据上的表现。最后，我们展示了S2算法对非参数主动学习的理论影响。

S2:一种高效的基于图的主动学习算法及其在非参数分类中的应用