Almost exact recovery in noisy semi-supervised learning
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.
Code (1)
Tasks
ClusteringCommunity DetectionStochastic Block ModelSimilar Papers 제목 키워드 기반
Robust Graph Learning from Noisy Data
Learning graphs from data automatically has shown encouraging performance on clustering and semisupervised learning tasks. However, real data are often corrupted, which may cause the learned graph to be inexact or unreli…
ClusteringGeneral Classificationgraph constructionGraph Learning+5Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach
We study the problem of community detection in a random hypergraph model which we call the stochastic block model for $k$-uniform hypergraphs ($k$-SBM). We investigate the exact recovery problem in $k$-SBM and show that …
Community DetectionStochastic Block ModelOpen problem: Tightness of maximum likelihood semidefinite relaxations
We have observed an interesting, yet unexplained, phenomenon: Semidefinite programming (SDP) based relaxations of maximum likelihood estimators (MLE) tend to be tight in recovery problems with noisy data, even when MLE c…
Deterministic Symmetric Positive Semidefinite Matrix Completion
We consider the problem of recovering a symmetric, positive semidefinite (SPSD) matrix from a subset of its entries, possibly corrupted by noise. In contrast to previous matrix recovery work, we drop the assumption of a …
Matrix CompletionSupport Recovery in Sparse PCA with Incomplete Data
We study a practical algorithm for sparse principal component analysis (PCA) of incomplete and noisy data. Our algorithm is based on the semidefinite program (SDP) relaxation of the non-convex $l_1$-regularized PCA probl…