Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions

DOI10.1109/TIT.2016.2594812MaRDI QIDQ2976594zbMATH 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/1502.07738

Mathematics Subject Classification ID

Semidefinite programming (90C22) Applications of graph theory to circuits and networks (94C15)

Abstract: Resolving a conjecture of Abbe, Bandeira and Hall, the authors have recently shown that the semidefinite programming (SDP) relaxation of the maximum likelihood estimator achieves the sharp threshold for exactly recovering the community structure under the binary stochastic block model of two equal-sized clusters. The same was shown for the case of a single cluster and outliers. Extending the proof techniques, in this paper it is shown that SDP relaxations also achieve the sharp recovery threshold in the following cases: (1) Binary stochastic block model with two clusters of sizes proportional to network size but not necessarily equal; (2) Stochastic block model with a fixed number of equal-sized clusters; (3) Binary censored block model with the background graph being ErdH{o}s-R'enyi. Furthermore, a sufficient condition is given for an SDP procedure to achieve exact recovery for the general case of a fixed number of clusters plus outliers. These results demonstrate the versatility of SDP relaxation as a simple, general purpose, computationally feasible methodology for community detection.

Cited in

(30)

• Rate-optimal graphon estimation
• On semidefinite relaxations for the block model
• Random Laplacian matrices and convex relaxations
• Community detection in degree-corrected block models
• Convex relaxation methods for community detection
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
• Consistent nonparametric estimation for heavy-tailed sparse graphs
• Iterative algorithm for discrete structure recovery
• Community detection with a subsampled semidefinite program
• Optimal rates for community estimation in the weighted stochastic block model
• Entrywise eigenvector analysis of random matrices with low expected rank
• Maximum likelihood estimation of sparse networks with missing observations
• Convexified modularity maximization for degree-corrected stochastic block models
• 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
• The Lovász theta function for random regular graphs and community detection in the hard regime
• Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
• Joint community detection and rotational synchronization via semidefinite programming
• Hidden Hamiltonian cycle recovery via linear programming
• The Lovász theta function for random regular graphs and community detection in the hard regime
• A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
• The superconvergent cluster recovery method
• A Time-Varying Network for Cryptocurrencies
• Planted models for the densest k-subgraph problem
• Tightness of SDP and Burer-Monteiro factorization for phase synchronization in a high-noise regime
• Nonconvex landscapes for \(\mathbf{Z}_2\) synchronization and graph clustering are benign near exact recovery thresholds
• Title not available (Why is no real title available?)

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

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