Almost exact recovery in noisy semi-supervised learning

Abstract

Graph-based semi-supervised learning methods combine the graph structure and labeled data to classify unlabeled data. In this work, we study the effect of a noisy oracle on classification. In particular, we derive the Maximum A Posteriori (MAP) estimator for clustering a Degree Corrected Stochastic Block Model (DC-SBM) when a noisy oracle reveals a fraction of the labels. We then propose an algorithm derived from a continuous relaxation of the MAP, and we establish its consistency. Numerical experiments show that our approach achieves promising performance on synthetic and real data sets, even in the case of very noisy labeled data.

References in corpus (8)

• Stochastic blockmodels and community structure in networks
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms
• Understanding Regularized Spectral Clustering via Graph Conductance
• Community Detection with Side Information: Exact Recovery under the Stochastic Block Model
• Poisson Learning: Graph Based Semi-Supervised Learning At Very Low Label Rates
• Mean Field Analysis of Personalized PageRank with Implications for Local Graph Clustering
• Consistent Semi-Supervised Graph Regularization for High Dimensional Data