A Linear Time Active Learning Algorithm for Link Classification -- Full Version --
This addresses efficient active learning for link classification in networks, but it is incremental as it builds on existing stochastic models and focuses on theoretical improvements.
The paper tackles the problem of link classification in signed networks by proposing an active learning algorithm that achieves an optimal number of mistakes, querying O(|V|^{3/2}) edge labels for graphs with |E| = Ω(|V|^{3/2}), with a running time of O(|E| + |V|log|V|).
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| = Ω(|V|^{3/2}) by querying O(|V|^{3/2}) edge labels. More generally, we show an algorithm that achieves optimality to within a factor of O(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|.