A Linear Time Active Learning Algorithm for Link Classification -- Full\n Version --

2013/01/21 by Nicolò Cesa‐Bianchi, Cesa-Bianchi, Nicolo, Claudio Gentile +5
Computer Science · #Distributed systems and fault tolerance #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Search Problems #Social and Information Networks (cs.SI)

paper · pdf · doi:10.48550/arxiv.1301.4767

openalex publication_date 2013/01/21 · openalex created_date 2022/08/31 · openalex updated_date 2026/07/28

Abstract

We present very efficient active learning algorithms for link classification\nin signed networks. Our algorithms are motivated by a stochastic model in which\nedge labels are obtained through perturbations of a initial sign assignment\nconsistent with a two-clustering of the nodes. We provide a theoretical\nanalysis within this model, showing that we can achieve an optimal (to whithin\na constant factor) number of mistakes on any graph G = (V,E) such that |E| =\n\Ω(|V|^3/2) by querying O(|V|^3/2) edge labels. More generally, we show\nan algorithm that achieves optimality to within a factor of O(k) by querying at\nmost order of |V| + (|V|/k)^3/2 edge labels. The running time of this\nalgorithm is at most of order |E| + |V|\log|V|.\n

Citations

• Active Learning on Trees and Graphs
• A tutorial on spectral clustering

Related

• A Correlation Clustering Approach to Link Classification in Signed Networks -- Full Version --
• Even Trolls Are Useful: Efficient Link Classification in Signed Networks
• S2: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification
• A Signed Subgraph Encoding Approach via Linear Optimization for Link Sign Prediction
• Active Learning on Trees and Graphs