Exact Recovery in the Stochastic Block Model
From MaRDI portal
Abstract: The stochastic block model (SBM) with two communities, or equivalently the planted bisection model, is a popular model of random graph exhibiting a cluster behaviour. In the symmetric case, the graph has two equally sized clusters and vertices connect with probability within clusters and across clusters. In the past two decades, a large body of literature in statistics and computer science has focused on providing lower-bounds on the scaling of to ensure exact recovery. In this paper, we identify a sharp threshold phenomenon for exact recovery: if and are constant (with ), recovering the communities with high probability is possible if and impossible if . In particular, this improves the existing bounds. This also sets a new line of sight for efficient clustering algorithms. While maximum likelihood (ML) achieves the optimal threshold (by definition), it is in the worst-case NP-hard. This paper proposes an efficient algorithm based on a semidefinite programming relaxation of ML, which is proved to succeed in recovering the communities close to the threshold, while numerical experiments suggest it may achieve the threshold. An efficient algorithm which succeeds all the way down to the threshold is also obtained using a partial recovery algorithm combined with a local improvement procedure.
Cited in
(only showing first 100 items - show all)- Computational and statistical thresholds in multi-layer stochastic block models
- Spectral clustering revisited: information hidden in the Fiedler vector
- Nonconvex landscapes for \(\mathbf{Z}_2\) synchronization and graph clustering are benign near exact recovery thresholds
- Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering
- Community detection in signed networks: a penalized semidefinite programming framework
- Convex optimization for the densest subgraph and densest submatrix problems
- Overlapping community detection in weighted networks
- Exact clustering of weighted graphs via semidefinite programming
- A unified approach to synchronization problems over subgroups of the orthogonal group
- Sparse random hypergraphs: non-backtracking spectra and community detection
- Accelerated first-order methods for a class of semidefinite programs
- A goodness-of-fit test for stochastic block models
- Learning directed acyclic graph SPNs in sub-quadratic time
- Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
- k-median: exact recovery in the extended stochastic ball model
- Efficient joint object matching via linear programming
- The Lovász theta function for recovering planted clique covers and graph colorings
- A spectral method for community detection in moderately sparse degree-corrected stochastic block models
- An \({\ell_p}\) theory of PCA and spectral clustering
- Sharp optimal recovery in the two component Gaussian mixture model
- Efficient, certifiably optimal clustering with applications to latent variable graphical models
- Iterative algorithm for discrete structure recovery
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
- Matched bipartite block model with covariates
- Non-unique games over compact groups and orientation estimation in cryo-EM
- Contiguity and non-reconstruction results for planted partition models: the dense case
- Consistent nonparametric estimation for heavy-tailed sparse graphs
- Fast Network Community Detection With Profile-Pseudo Likelihood Methods
- Stochastic growth tree networks with an identical fractal dimension: construction and mean hitting time for random walks
- Semi-supervised clustering of sparse graphs: crossing the information-theoretic threshold
- Asymptotic mutual information for the balanced binary stochastic block model
- Global and individualized community detection in inhomogeneous multilayer networks
- Information-theoretic limits for testing community structures in weighted networks
- Network cross-validation for determining the number of communities in network data
- Exact recovery discrimination in planted bisection model
- Optimal rates for community estimation in the weighted stochastic block model
- Joint community detection and rotational synchronization via semidefinite programming
- Community detection and stochastic block models: recent developments
- Exact recovery in the Ising blockmodel
- Optimal bipartite network clustering
- Reconstructing community structure of online social network via user opinions
- Community detection in the sparse hypergraph stochastic block model
- A survey on theoretical advances of community detection in networks
- scientific article; zbMATH DE number 7307465 (Why is no real title available?)
- Soft happy colourings and community structure of networks
- The ratio-cut polytope and K-means clustering
- On semidefinite relaxations for the block model
- Mean estimation with sub-Gaussian rates in polynomial time
- Mutual information for the sparse stochastic block model
- Community detection in degree-corrected block models
- Step-by-step community detection in volume-regular graphs
- An impossibility result for reconstruction in the degree-corrected stochastic block model
- Bayesian community detection
- Detecting groups in large vector autoregressions
- Convexified modularity maximization for degree-corrected stochastic block models
- Universal latent space model fitting for large networks with edge covariates
- Random Laplacian matrices and convex relaxations
- Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
- Exact Recovery and Sharp Thresholds of Stochastic Ising Block Model
- Probably certifiably correct k-means clustering
- New abilities and limitations of spectral graph bisection
- Entrywise eigenvector analysis of random matrices with low expected rank
- Spectral norm bounds for block Markov chain random matrices
- Network-adjusted covariates for community detection
- An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization
- A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
- The geometry of continuous latent space models for network data
- The planted k-factor problem
- Non-convex exact community recovery in stochastic block model
- On the tightness of SDP relaxations of QCQPs
- Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator
- Asymptotic uncertainty quantification for communities in sparse planted bi-section models
- Joint Alignment from Pairwise Differences with a Noisy Oracle
- A generalized Bayesian stochastic block model for microbiome community detection
- Nonreconstruction of high-dimensional stochastic block model with bounded degree
- Community detection with a subsampled semidefinite program
- Frequentist validity of Bayesian limits
- scientific article; zbMATH DE number 7370527 (Why is no real title available?)
- The Lovász theta function for random regular graphs and community detection in the hard regime
- Exact recovery in the hypergraph stochastic block model: a spectral algorithm
- A computational transition for detecting correlated stochastic block models by low-degree polynomials
- Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals
- Confidence sets in a sparse stochastic block model with two communities of unknown sizes
- Testing for high-dimensional geometry in random graphs
- Clustering in block Markov chains
- Convex relaxation methods for community detection
- Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
- Robust high-dimensional factor models with applications to statistical machine learning
- Detecting Giver and Receiver Spillover Groups in Large Vector Autoregressions
- Strong consistency, graph Laplacians, and the stochastic block model
- scientific article; zbMATH DE number 7415091 (Why is no real title available?)
- Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
- Community Detection in Censored Hypergraph
- Fair community detection and structure learning in heterogeneous graphical models
- Exact recovery of community detection in k-partite graph models with applications to learning electric potentials in electric networks
- Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems
- Statistical inference on random dot product graphs: a survey
- Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
- Bootstrap percolation on the stochastic block model
- Community Detection in Partial Correlation Network Models
This page was built for publication: Exact Recovery in the Stochastic Block Model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977080)
