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(κ) by querying at most order of |V| + (|V|=κ) 3/2 edge labels. The running time of this algorithm is at most of order |E| + |V| log |V|.

A linear time active learning algorithm for link classification / N. Cesa-Bianchi, C. Gentile, F. Vitale, G. Zappella - In: Advances in neural information processing systems / [a cura di] F. Pereira, C.J.C. Burges, L. Bottou, K.Q. Weinberger. - [s.l] : Neural information processing systems foundation, 2012. - pp. 1610-1618 (( convegno Conference on Neural Information Processing Systems tenutosi a South Lake Tahoe, USA nel 2012.

A linear time active learning algorithm for link classification

N. Cesa-Bianchi;F. Vitale
Penultimo
;
G. Zappella
2012

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| = Ω(|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(κ) by querying at most order of |V| + (|V|=κ) 3/2 edge labels. The running time of this algorithm is at most of order |E| + |V| log |V|.
Settore INF/01 - Informatica
http://papers.nips.cc/paper/4598-a-linear-time-active-learning-algorithm-for-link-classification
Book Part (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/231332
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact