Provable Estimation of the Number of Blocks in Block Models

• DOI: 10.48550/arxiv.1705.08580
• Publication Date: 2017-01-01
• Authors: Yan, Bowei; Sarkar, Purnamrita; Cheng, Xiuyuan
• Keywords: Methodology (stat.ME); FOS: Computer and information sciences; Statistics - Machine Learning; Machine Learning (stat.ML); 0101 mathematics; 01 natural sciences; Statistics - Methodology

Community detection is a fundamental unsupervised learning problem for unlabeled networks which has a broad range of applications. Many community detection algorithms assume that the number of clusters $r$ is known apriori. In this paper, we propose an approach based on semi-definite relaxations, which does not require prior knowledge of model parameters like many existing convex relaxation methods and recovers the number of clusters and the clustering matrix exactly under a broad parameter regime, with probability tending to one. On a variety of simulated and real data experiments, we show that the proposed method often outperforms state-of-the-art techniques for estimating the number of clusters.<br/>12 pages, 4 figure; AISTATS 2018<br/>