Achieving Exact Cluster Recovery Threshold via Semidefinite Programming

DOI10.1109/TIT.2016.2546280MaRDI QIDQ2976866zbMATH OpenOpenAlexFDO

Authors Bruce Hajek, Yihong Wu, Jiaming Xu

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.6156

Mathematics Subject Classification ID

Semidefinite programming (90C22) Detection theory in information and communication theory (94A13)

Abstract: The binary symmetric stochastic block model deals with a random graph of $n$ vertices partitioned into two equal-sized clusters, such that each pair of vertices is connected independently with probability $p$ within clusters and $q$ across clusters. In the asymptotic regime of $p=alogn/n$ and $q=blogn/n$ for fixed $a,b$ and $noinfty$, we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold for exactly recovering the partition from the graph with probability tending to one, resolving a conjecture of Abbe et al. cite{Abbe14}. Furthermore, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold in the planted dense subgraph model containing a single cluster of size proportional to $n$.

Cited in

(56)

• Consistent nonparametric estimation for heavy-tailed sparse graphs
• Semi-supervised clustering of sparse graphs: crossing the information-theoretic threshold
• A Time-Varying Network for Cryptocurrencies
• 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
• Self-concordant inclusions: a unified framework for path-following generalized Newton-type algorithms
• Optimal bipartite network clustering
• Community detection in the sparse hypergraph stochastic block model
• The ratio-cut polytope and K-means clustering
• The Lovász theta function for random regular graphs and community detection in the hard regime
• On semidefinite relaxations for the block model
• Community detection in degree-corrected block models
• Recovering a hidden community beyond the Kesten-Stigum threshold in \(O(| E|\log^\ast| V|)\) time
• Convexified modularity maximization for degree-corrected stochastic block models
• Universal latent space model fitting for large networks with edge covariates
• Covariate regularized community detection in sparse graphs
• Random Laplacian matrices and convex relaxations
• New abilities and limitations of spectral graph bisection
• Threshold-based declustering
• Spectral norm bounds for block Markov chain random matrices
• A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
• Non-convex exact community recovery in stochastic block model
• Ellipsoidal embeddings of graphs
• 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
• Adaptive power method: eigenvector estimation from sampled data
• Joint Alignment from Pairwise Differences with a Noisy Oracle
• The superconvergent cluster recovery method
• The Lovász theta function for random regular graphs and community detection in the hard regime
• Multilayer hypergraph clustering using the aggregate similarity matrix
• Confidence sets in a sparse stochastic block model with two communities of unknown sizes
• Large deviations of the largest eigenvalue of supercritical sparse Wigner matrices
• Clustering in block Markov chains
• Analysis of singular subspaces under random perturbations
• Convex relaxation methods for community detection
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• Strong consistency, graph Laplacians, and the stochastic block model
• Community Detection in Censored Hypergraph
• Exact recovery of community detection in k-partite graph models with applications to learning electric potentials in electric networks
• On the estimation of latent distances using graph distances
• Community Detection in Sparse Networks Using the Symmetrized Laplacian Inverse Matrix (SLIM)
• Local law and Tracy-Widom limit for sparse stochastic block models
• Hidden Hamiltonian cycle recovery via linear programming
• Rate optimal Chernoff bound and application to community detection in the stochastic block models
• Consistency of Lloyd's algorithm under perturbations
• scientific article; zbMATH DE number 7626745 (Why is no real title available?)
• Sum-of-squares lower bounds for densest k-subgraph
• Orthogonal symmetric non-negative matrix factorization under the stochastic block model
• Nonconvex landscapes for \(\mathbf{Z}_2\) synchronization and graph clustering are benign near exact recovery thresholds
• A unified approach to synchronization problems over subgroups of the orthogonal group
• k-median: exact recovery in the extended stochastic ball model
• Memory-efficient structured convex optimization via extreme point sampling
• Efficient joint object matching via linear programming
• Iterative algorithm for discrete structure recovery

This page was built for publication: Achieving Exact Cluster Recovery Threshold via Semidefinite Programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976866)