Provable Estimation of the Number of Blocks in Block Models

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.

• Publication year

  2017

• Venue

  International Conference on Artificial Intelligence and Statistics

• Publication date

  2017-05-24

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1705.08580
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Efficient method for estimating the number of communities in a network

  2017cited by this paper
• Convex Relaxation for Community Detection with Covariates

  2016influential reference
• Clustering subgaussian mixtures by semidefinite programming

  2016cited by this paper
• On Robustness of Kernel Clustering

  2016cited by this paper
• A semidefinite program for unbalanced multisection in the stochastic block model

  2015influential reference
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions

  2015cited by this paper
• Semidefinite programs on sparse random graphs and their application to community detection

  2015cited by this paper
• Recovering Communities in the General Stochastic Block Model Without Knowing the Parameters

  2015cited by this paper
• Likelihood-based model selection for stochastic block models

  2015cited by this paper
• Estimating the number of communities in networks by spectral methods

  2015influential reference
• Sparse random graphs: regularization and concentration of the Laplacian

  2015cited by this paper
• Convexified Modularity Maximization for Degree-corrected Stochastic Block Models

  2015cited by this paper
• On semidefinite relaxations for the block model

  2014influential reference
• How Many Communities Are There?

  2014cited by this paper
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming

  2014cited by this paper
• Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs

  2014cited by this paper
• A goodness-of-fit test for stochastic block models

  2014cited by this paper
• Community detection in sparse networks via Grothendieck’s inequality

  2014cited by this paper
• Network Cross-Validation for Determining the Number of Communities in Network Data

  2014cited by this paper
• Robust and Computationally Feasible Community Detection in the Presence of Arbitrary Outlier Nodes

  2014cited by this paper
• Hypothesis testing for automated community detection in networks

  2013cited by this paper
• Consistency of spectral clustering in stochastic block models

  2013cited by this paper
• Improved Graph Clustering

  2012influential reference
• Consistent Adjacency-Spectral Partitioning for the Stochastic Block Model When the Model Parameters Are Unknown

  2012cited by this paper
• Learning to Discover Social Circles in Ego Networks

  2012cited by this paper
• Pseudo-likelihood methods for community detection in large sparse networks

  2012influential reference
• Matrix estimation by Universal Singular Value Thresholding

  2012cited by this paper
• Clustering Sparse Graphs

  2012cited by this paper
• Stochastic blockmodels and community structure in networks

  2010cited by this paper
• Uncovering latent structure in valued graphs: A variational approach

  2010cited by this paper
• Community extraction for social networks

  2010cited by this paper
• Variational Bayesian inference and complexity control for stochastic block models

  2009cited by this paper
• Bi-cross-validation of the SVD and the nonnegative matrix factorization

  2009cited by this paper
• A mixture model for random graphs

  2008cited by this paper
• Mixed Membership Stochastic Blockmodels

  2007cited by this paper
• Modeling homophily and stochastic equivalence in symmetric relational data

  2007cited by this paper
• Bayesian approach to network modularity.

  2007cited by this paper
• Population Structure and Eigenanalysis

  2006cited by this paper
• Advanced Optimization Laboratory Title : Approximating K-means-type clustering via semidefinite programming

  2005cited by this paper
• Learning the k in k-means

  2003cited by this paper
• Community structure in social and biological networks

  2001cited by this paper
• X-means: Extending K-means with Efficient Estimation of the Number of Clusters

  2000cited by this paper
• Assessing a Mixture Model for Clustering with the Integrated Completed Likelihood

  2000cited by this paper
• Stochastic blockmodels: First steps

  1983cited by this paper
• An Information Flow Model for Conflict and Fission in Small Groups

  1977cited by this paper
• Computational Statistics and Data Analysis Selecting the Number of Components in Principal Component Analysis Using Cross-validation Approximations

  year unknowncited by this paper

• The Spectral Barycentre of a Set of Graphs with Community Structure

  2025cites this paper
• Multiple Hypothesis Testing To Estimate The Number Of Communities in Stochastic Block Models

  2025cites this paper
• Determining the Number of Communities in Sparse and Imbalanced Settings

  2024cites this paper
• A Review of Community Detection Based on Modularity Optimization in Complex Networks

  2024cites this paper
• Efficient Algorithms for Exact Graph Matching on Correlated Stochastic Block Models with Constant Correlation

  2023influential citation
• On the Estimation of the Number of Communities for Sparse Networks

  2023cites this paper
• Subsampling-based modified Bayesian information criterion for large-scale stochastic block models

  2023cites this paper
• Estimation and inference for stochastic blockmodels

  2022cites this paper
• Improved Representation Learning Through Tensorized Autoencoders

  2022cites this paper
• Estimating the Number of Communities in Weighted Networks

  2022cites this paper
• A novel memorizing single chromosome evolutionary algorithm for detecting communities in complex networks

  2022cites this paper
• Graphon based Clustering and Testing of Networks: Algorithms and Theory

  2021cites this paper
• Joint Community Detection and Rotational Synchronization via Semidefinite Programming

  2021cites this paper
• Network Estimation by Mixing: Adaptivity and More

  2021cites this paper
• Graphon estimation via nearest‐neighbour algorithm and two‐dimensional fused‐lasso denoising

  2021cites this paper
• Near-Optimal Comparison Based Clustering

  2020influential citation
• On hyperparameter tuning in general clustering problemsm

  2020cites this paper
• Adjusted chi-square test for degree-corrected block models

  2020cites this paper
• A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outliers

  2019cites this paper
• Certifying Global Optimality of Graph Cuts via Semidefinite Relaxation: A Performance Guarantee for Spectral Clustering

  2019cites this paper
• Diffusion K-means clustering on manifolds: provable exact recovery via semidefinite relaxations

  2019cites this paper
• A Unified Framework for Tuning Hyperparameters in Clustering Problems

  2019influential citation
• Latent Simplex Position Model: High Dimensional Multi-view Clustering with Uncertainty Quantification

  2019cites this paper
• Determining the Number of Communities in Degree-corrected Stochastic Block Models

  2018cites this paper
• Certifying Global Optimality of Graph Cuts via Semidefinite Relaxation: A Performance Guarantee for Spectral Clustering

  2018cites this paper
• Convex Relaxation Methods for Community Detection

  2018cites this paper
• Graphon estimation via nearest neighbor algorithm and 2D fused lasso denoising

  2018cites this paper
• Two provably consistent divide-and-conquer clustering algorithms for large networks

  2017influential citation
• Clustering of Sparse and Approximately Sparse Graphs by Semidefinite Programming

  2016cites this paper
• Convex Relaxation for Community Detection with Covariates

  2016cites this paper
• Covariate Regularized Community Detection in Sparse Graphs

  2016cites this paper
• Exact Clustering of Weighted Graphs via Semidefinite Programming

  2016cites this paper
• Estimating the number of communities by spectral methods

  2015cites this paper
• Subsampling Sparse Graphons Under Minimal Assumptions

  year unknowncites this paper