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)- Convex optimization for the densest subgraph and densest submatrix problems
- Network cross-validation for determining the number of communities in network data
- An impossibility result for reconstruction in the degree-corrected stochastic block model
- Bayesian community detection
- Probably certifiably correct k-means clustering
- Spectral and structural properties of random interdependent networks
- A note on probably certifiably correct algorithms
- On semidefinite relaxations for the block model
- Contiguity and non-reconstruction results for planted partition models: the dense case
- Random Laplacian matrices and convex relaxations
- Community detection in degree-corrected block models
- 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
- Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
- Consistent nonparametric estimation for heavy-tailed sparse graphs
- Spectral clustering revisited: information hidden in the Fiedler vector
- Non-convex exact community recovery in stochastic block model
- Sharp optimal recovery in the two component Gaussian mixture model
- An \({\ell_p}\) theory of PCA and spectral clustering
- Global and individualized community detection in inhomogeneous multilayer networks
- Bootstrap percolation on the stochastic block model
- Iterative algorithm for discrete structure recovery
- 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
- Community detection with a subsampled semidefinite program
- Local law and Tracy-Widom limit for sparse stochastic block models
- Optimal rates for community estimation in the weighted stochastic block model
- Exact recovery in block spin Ising models at the critical line
- Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering
- Mean estimation with sub-Gaussian rates in polynomial time
- Entrywise eigenvector analysis of random matrices with low expected rank
- Step-by-step community detection in volume-regular graphs
- Detecting groups in large vector autoregressions
- Nonreconstruction of high-dimensional stochastic block model with bounded degree
- The geometry of continuous latent space models for network data
- Learning directed acyclic graph SPNs in sub-quadratic time
- Exact recovery in the hypergraph stochastic block model: a spectral algorithm
- Exact recovery in the Ising blockmodel
- Convexified modularity maximization for degree-corrected stochastic block models
- Efficient, certifiably optimal clustering with applications to latent variable graphical models
- Frequentist validity of Bayesian limits
- Exact recovery of community detection in k-partite graph models with applications to learning electric potentials in electric networks
- Spectral norm bounds for block Markov chain random matrices
- Testing for high-dimensional geometry in random graphs
- An Exact Algorithm for Blockmodeling of Two-Mode Network Data
- Community detection and stochastic block models: recent developments
- Submatrix localization via message passing
- Statistical inference on random dot product graphs: a survey
- Asymptotic mutual information for the balanced binary stochastic block model
- Sparse general Wigner-type matrices: local law and eigenvector delocalization
- Exact clustering of weighted graphs via semidefinite programming
- Matched bipartite block model with covariates
- Universal latent space model fitting for large networks with edge covariates
- Weighted message passing and minimum energy flow for heterogeneous stochastic block models with side information
- Optimal bipartite network clustering
- Rank optimality for the Burer-Monteiro factorization
- Recovering structured probability matrices
- scientific article; zbMATH DE number 7370527 (Why is no real title available?)
- Strong consistency, graph Laplacians, and the stochastic block model
- Non-unique games over compact groups and orientation estimation in cryo-EM
- Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
- Exact Recovery and Sharp Thresholds of Stochastic Ising Block Model
- On Convex Hulls of Epigraphs of QCQPs
- scientific article; zbMATH DE number 7626745 (Why is no real title available?)
- The ratio-cut polytope and K-means clustering
- Joint community detection and rotational synchronization via semidefinite programming
- Distribution-free, size adaptive submatrix detection with acceleration
- New abilities and limitations of spectral graph bisection
- Find Your Place: Simple Distributed Algorithms for Community Detection
- Hidden Hamiltonian cycle recovery via linear programming
- Learning big Gaussian Bayesian networks: partition, estimation and fusion
- Statistical guarantees for local graph clustering
- Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems
- The Lovász theta function for random regular graphs and community detection in the hard regime
- A spectral method for community detection in moderately sparse degree-corrected stochastic block models
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
- Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
- The planted k-factor problem
- Joint Alignment from Pairwise Differences with a Noisy Oracle
- Estimating Mixed Memberships With Sharp Eigenvector Deviations
- A goodness-of-fit test for stochastic block models
- k-median: exact recovery in the extended stochastic ball model
- Efficient joint object matching via linear programming
- Community detection in the sparse hypergraph stochastic block model
- Fast Network Community Detection With Profile-Pseudo Likelihood Methods
- A unified approach to synchronization problems over subgroups of the orthogonal group
- Mutual information for the sparse stochastic block model
- 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
- Asymptotic uncertainty quantification for communities in sparse planted bi-section models
- Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals
- Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
- Community Detection in Censored Hypergraph
- A UNIFIED COMMUNITY DETECTION ALGORITHM IN LARGE-SCALE COMPLEX NETWORKS
- Reconstructing community structure of online social network via user opinions
- Stochastic growth tree networks with an identical fractal dimension: construction and mean hitting time for random walks
- A survey on theoretical advances of community detection in networks
- 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)
