A Linear Time Active Learning Algorithm for Link Classification
Abstract
We present very efficient active learning algorithms for link classification in signed networks. Our algorithms are motivated by a stochastic model in which edge labels are obtained through perturbations of a initial sign assignment consistent with a two-clustering of the nodes. We provide a theoretical analysis within this model, showing that we can achieve an optimal (to whithin a constant factor) number of mistakes on any graph $G = (V,E)$ such that $|E|$ is at least order of $|V|^{3/2}$ by querying at most order of $|V|^{3/2}$ edge labels. More generally, we show an algorithm that achieves optimality to within a factor of order $k$ by querying at most order of $|V| + (|V|/k)^{3/2}$ edge labels. The running time of this algorithm is at most of order $|E| + |V|\log|V|$.
Cite
Text
Cesa-bianchi et al. "A Linear Time Active Learning Algorithm for Link Classification." Neural Information Processing Systems, 2012.Markdown
[Cesa-bianchi et al. "A Linear Time Active Learning Algorithm for Link Classification." Neural Information Processing Systems, 2012.](https://mlanthology.org/neurips/2012/cesabianchi2012neurips-linear/)BibTeX
@inproceedings{cesabianchi2012neurips-linear,
title = {{A Linear Time Active Learning Algorithm for Link Classification}},
author = {Cesa-bianchi, Nicolò and Gentile, Claudio and Vitale, Fabio and Zappella, Giovanni},
booktitle = {Neural Information Processing Systems},
year = {2012},
pages = {1610-1618},
url = {https://mlanthology.org/neurips/2012/cesabianchi2012neurips-linear/}
}