Algorithms and Hardness for Active Learning on Graphs

We study the offline active learning problem on graphs. In this problem, one seeks to select k vertices whose labels are best suited for predicting the labels of all the other vertices in the graph. Guillory and Bilmes (Guillory & Bilmes, 2009) introduced a natural theoretical model motivated by a label smoothness assumption. Prior to our work, algorithms with theoretical guarantees were only known for restricted graph types such as trees (Cesa-Bianchi et al. , 2010) despite the models simplicity. We present the first O(log n)-resource augmented algorithm for general weighted graphs. To complement our algorithm, we show constant hardness of approximation.

Authors

• Vincent Cohen-Addad
• Silvio Lattanzi
• Simon Meierhans

Keywords

• graph
• active learning
• label selection
• resource augmented algorithms
• approximation algorithms