Algorithms and Hardness for Active Learning on Graphs

Vincent Cohen-Addad; Silvio Lattanzi; Simon Meierhans

ICML 2025poster0 citations

Algorithms and Hardness for Active Learning on Graphs

Vincent Cohen-Addad, Silvio Lattanzi, Simon Meierhans

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.

graphactive learninglabel selectionresource augmented algorithmsapproximation algorithms

BibTeX

@inproceedings{
cohen-addad2025algorithms,
title={Algorithms and Hardness for Active Learning on Graphs},
author={Vincent Cohen-Addad and Silvio Lattanzi and Simon Meierhans},
booktitle={Forty-second International Conference on Machine Learning},
year={2025},
url={https://openreview.net/forum?id=EAnuqHF0tx}
}