Algorithms and Hardness for Active Learning on Graphs

Vincent Cohen-Addad, Silvio Lattanzi, Simon Meierhans
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:11200-11214, 2025.

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 this Paper

BibTeX
@InProceedings{pmlr-v267-cohen-addad25a, 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}, pages = {11200--11214}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/cohen-addad25a/cohen-addad25a.pdf}, url = {https://proceedings.mlr.press/v267/cohen-addad25a.html}, 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.} }
Endnote
%0 Conference Paper %T Algorithms and Hardness for Active Learning on Graphs %A Vincent Cohen-Addad %A Silvio Lattanzi %A Simon Meierhans %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-cohen-addad25a %I PMLR %P 11200--11214 %U https://proceedings.mlr.press/v267/cohen-addad25a.html %V 267 %X 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.
APA
Cohen-Addad, V., Lattanzi, S. & Meierhans, S.. (2025). Algorithms and Hardness for Active Learning on Graphs. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:11200-11214 Available from https://proceedings.mlr.press/v267/cohen-addad25a.html.

Related Material