Non-convex exact community recovery in stochastic block model
DOI10.1007/s10107-021-01715-1zbMath1505.05120arXiv2006.15843OpenAlexW3213629870MaRDI QIDQ2089764
Zirui Zhou, Anthony Man-Cho So, Peng Wang
Publication date: 24 October 2022
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2006.15843
finite terminationcommunity detectionexact recoveryorthogonal iterationnearly-linear timeprojected power iteration
Factor analysis and principal components; correspondence analysis (62H25) Asymptotic properties of nonparametric inference (62G20) Social networks; opinion dynamics (91D30) Applications of graph theory (05C90) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Integer programming (90C10) Nonconvex programming, global optimization (90C26)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Consistency thresholds for the planted bisection model
- On the largest principal angle between random subspaces
- Time bounds for selection
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- On semidefinite relaxations for the block model
- Random Laplacian matrices and convex relaxations
- Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
- Entrywise eigenvector analysis of random matrices with low expected rank
- Optimization for deep learning: an overview
- Consistency of spectral clustering in stochastic block models
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
- Exact Recovery in the Stochastic Block Model
- The university of Florida sparse matrix collection
- Community structure in social and biological networks
- Community Detection and Stochastic Block Models
- On the Estimation Performance and Convergence Rate of the Generalized Power Method for Phase Synchronization
- Near-Optimal Bounds for Phase Synchronization
- High-Dimensional Probability
- Global rates of convergence for nonconvex optimization on manifolds
- Nonconvex Robust Low-Rank Matrix Recovery
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- Community detection thresholds and the weak Ramanujan property
- Achieving Optimal Misclassification Proportion in Stochastic Block Model
