On semidefinite relaxations for the block model
From MaRDI portal
Publication:1747735
DOI10.1214/17-AOS1545zbMath1393.62021arXiv1406.5647MaRDI QIDQ1747735
Elizaveta Levina, Arash A. Amini
Publication date: 27 April 2018
Published in: The Annals of Statistics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1406.5647
Estimation in multivariate analysis (62H12) Asymptotic properties of nonparametric inference (62G20) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Semidefinite programming (90C22)
Related Items
Overlapping community detection in networks via sparse spectral decomposition, A likelihood-ratio type test for stochastic block models with bounded degrees, Hierarchical Community Detection by Recursive Partitioning, Community detection via an efficient nonconvex optimization approach based on modularity, A review on spectral clustering and stochastic block models, Optimal Bipartite Network Clustering, Multi-group binary choice with social interaction and a random communication structure -- a random graph approach, Universal inference, Unnamed Item, A review of dynamic network models with latent variables, Model assisted variable clustering: minimax-optimal recovery and algorithms, Rate optimal Chernoff bound and application to community detection in the stochastic block models, Exact recovery in block spin Ising models at the critical line, Spectral clustering-based community detection using graph distance and node attributes, \(k\)-median: exact recovery in the extended stochastic ball model, Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering, Subsampling spectral clustering for stochastic block models in large-scale networks, Hypothesis testing for populations of networks, Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates, Unnamed Item, Entrywise eigenvector analysis of random matrices with low expected rank, A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization, Semidefinite programming based community detection for node-attributed networks and multiplex networks, Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks, Measuring the stability of spectral clustering, Fluctuation results for general block spin Ising models, Maximum likelihood estimation of sparse networks with missing observations, Unnamed Item, On semidefinite relaxations for the block model, Community Detection and Stochastic Block Models, When do birds of a feather flock together? \(k\)-means, proximity, and conic programming, 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, Convex optimization for the densest subgraph and densest submatrix problems, Community detection in sparse networks via Grothendieck's inequality, Fluctuations for block spin Ising models, Profile likelihood biclustering, Dynamic network models and graphon estimation, Exact Clustering of Weighted Graphs via Semidefinite Programming, Partial recovery bounds for clustering with the relaxed \(K\)-means, Unnamed Item, Covariate Regularized Community Detection in Sparse Graphs, Unnamed Item, Phases of small worlds: a mean field formulation, Non-convex exact community recovery in stochastic block model, Unnamed Item, Unnamed Item, Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
Uses Software
Cites Work
- Unnamed Item
- Pseudo-likelihood methods for community detection in large sparse networks
- Rate-optimal graphon estimation
- Consistency thresholds for the planted bisection model
- Impact of regularization on spectral clustering
- Belief propagation, robust reconstruction and optimal recovery of block models
- Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
- Oracle inequalities for network models and sparse graphon estimation
- Spectral clustering and the high-dimensional stochastic blockmodel
- Community detection in sparse networks via Grothendieck's inequality
- High-dimensional analysis of semidefinite relaxations for sparse principal components
- Representations for partially exchangeable arrays of random variables
- Estimation and prediction for stochastic blockmodels for graphs with latent block structure
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- A note on probably certifiably correct algorithms
- A proof of the block model threshold conjecture
- On semidefinite relaxations for the block model
- Random Laplacian matrices and convex relaxations
- Consistency of community detection in networks under degree-corrected stochastic block models
- Consistency of maximum-likelihood and variational estimators in the stochastic block model
- Consistency of spectral clustering in stochastic block models
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- Convex optimization for the planted \(k\)-disjoint-clique problem
- Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
- Distributed user profiling via spectral methods
- A nonparametric view of network models and Newman–Girvan and other modularities
- Phase transitions in semidefinite relaxations
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
- Exact Recovery in the Stochastic Block Model
- Improved Graph Clustering
- Relax, No Need to Round
- Mixed membership stochastic blockmodels
- Estimation and Prediction for Stochastic Blockstructures
- Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)
- Community detection thresholds and the weak Ramanujan property
- Spectral techniques applied to sparse random graphs
- Semidefinite programs on sparse random graphs and their application to community detection
- How robust are reconstruction thresholds for community detection?
- Concentration and regularization of random graphs
- Estimating network edge probabilities by neighbourhood smoothing
- Approximating K‐means‐type Clustering via Semidefinite Programming
- A Direct Formulation for Sparse PCA Using Semidefinite Programming
