Provable Estimation of the Number of Blocks in Block Models

Bowei Yan, Purnamrita Sarkar, Xiuyuan Cheng
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:1185-1194, 2018.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v84-yan18a, title = {Provable Estimation of the Number of Blocks in Block Models}, author = {Yan, Bowei and Sarkar, Purnamrita and Cheng, Xiuyuan}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {1185--1194}, year = {2018}, editor = {Storkey, Amos and Perez-Cruz, Fernando}, volume = {84}, series = {Proceedings of Machine Learning Research}, month = {09--11 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v84/yan18a/yan18a.pdf}, url = {https://proceedings.mlr.press/v84/yan18a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Provable Estimation of the Number of Blocks in Block Models %A Bowei Yan %A Purnamrita Sarkar %A Xiuyuan Cheng %B Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2018 %E Amos Storkey %E Fernando Perez-Cruz %F pmlr-v84-yan18a %I PMLR %P 1185--1194 %U https://proceedings.mlr.press/v84/yan18a.html %V 84 %X 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.
APA
Yan, B., Sarkar, P. & Cheng, X.. (2018). Provable Estimation of the Number of Blocks in Block Models. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 84:1185-1194 Available from https://proceedings.mlr.press/v84/yan18a.html.

Related Material