Algorithms and Hardness for Active Learning on Graphs
Abstract
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.
Cite
Text
Cohen-Addad et al. "Algorithms and Hardness for Active Learning on Graphs." Proceedings of the 42nd International Conference on Machine Learning, 2025.Markdown
[Cohen-Addad et al. "Algorithms and Hardness for Active Learning on Graphs." Proceedings of the 42nd International Conference on Machine Learning, 2025.](https://mlanthology.org/icml/2025/cohenaddad2025icml-algorithms/)BibTeX
@inproceedings{cohenaddad2025icml-algorithms,
title = {{Algorithms and Hardness for Active Learning on Graphs}},
author = {Cohen-Addad, Vincent and Lattanzi, Silvio and Meierhans, Simon},
booktitle = {Proceedings of the 42nd International Conference on Machine Learning},
year = {2025},
pages = {11200-11214},
volume = {267},
url = {https://mlanthology.org/icml/2025/cohenaddad2025icml-algorithms/}
}