On semidefinite relaxations for the block model
From MaRDI portal
Publication:1747735
DOI10.1214/17-AOS1545zbMATH Open1393.62021arXiv1406.5647MaRDI QIDQ1747735FDOQ1747735
Authors: Arash A. Amini, Elizaveta Levina 
Publication date: 27 April 2018
Published in: The Annals of Statistics (Search for Journal in Brave)
Abstract: The stochastic block model (SBM) is a popular tool for community detection in networks, but fitting it by maximum likelihood (MLE) involves a computationally infeasible optimization problem. We propose a new semidefinite programming (SDP) solution to the problem of fitting the SBM, derived as a relaxation of the MLE. We put ours and previously proposed SDPs in a unified framework, as relaxations of the MLE over various sub-classes of the SBM, revealing a connection to sparse PCA. Our main relaxation, which we call SDP-1, is tighter than other recently proposed SDP relaxations, and thus previously established theoretical guarantees carry over. However, we show that SDP-1 exactly recovers true communities over a wider class of SBMs than those covered by current results. In particular, the assumption of strong assortativity of the SBM, implicit in consistency conditions for previously proposed SDPs, can be relaxed to weak assortativity for our approach, thus significantly broadening the class of SBMs covered by the consistency results. We also show that strong assortativity is indeed a necessary condition for exact recovery for previously proposed SDP approaches and not an artifact of the proofs. Our analysis of SDPs is based on primal-dual witness constructions, which provides some insight into the nature of the solutions of various SDPs. We show how to combine features from SDP-1 and already available SDPs to achieve the most flexibility in terms of both assortativity and block-size constraints, as our relaxation has the tendency to produce communities of similar sizes. This tendency makes it the ideal tool for fitting network histograms, a method gaining popularity in the graphon estimation literature, as we illustrate on an example of a social networks of dolphins. We also provide empirical evidence that SDPs outperform spectral methods for fitting SBMs with a large number of blocks.
Full work available at URL: https://arxiv.org/abs/1406.5647
Recommendations
- Phase transitions in semidefinite relaxations
- Community detection with a subsampled semidefinite program
- Community detection in sparse networks via Grothendieck's inequality
- Community detection and stochastic block models: recent developments
- Semidefinite programs on sparse random graphs and their application to community detection
Asymptotic properties of nonparametric inference (62G20) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Estimation in multivariate analysis (62H12) Semidefinite programming (90C22)
Cites Work
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- A nonparametric view of network models and Newman–Girvan and other modularities
- Estimation and Prediction for Stochastic Blockstructures
- Spectral clustering and the high-dimensional stochastic blockmodel
- Pseudo-likelihood methods for community detection in large sparse networks
- Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)
- Estimation and prediction for stochastic blockmodels for graphs with latent block structure
- Rate-optimal graphon estimation
- A proof of the block model threshold conjecture
- 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
- Mixed membership stochastic blockmodels
- Belief propagation, robust reconstruction and optimal recovery of block models
- Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
- Community detection thresholds and the weak Ramanujan property
- Concentration and regularization of random graphs
- A Direct Formulation for Sparse PCA Using Semidefinite Programming
- On semidefinite relaxations for the block model
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- Convex optimization for the planted \(k\)-disjoint-clique problem
- Exact Recovery in the Stochastic Block Model
- Improved Graph Clustering
- Oracle inequalities for network models and sparse graphon estimation
- Correlation clustering with noisy input
- Community detection in sparse networks via Grothendieck's inequality
- Representations for partially exchangeable arrays of random variables
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
- Impact of regularization on spectral clustering
- High-dimensional analysis of semidefinite relaxations for sparse principal components
- Spectral techniques applied to sparse random graphs
- Approximating K‐means‐type Clustering via Semidefinite Programming
- Random Laplacian matrices and convex relaxations
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
- Phase transitions in semidefinite relaxations
- Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices
- Semidefinite programs on sparse random graphs and their application to community detection
- Estimating network edge probabilities by neighbourhood smoothing
- A note on probably certifiably correct algorithms
- Relax, no need to round: integrality of clustering formulations
- Distributed user profiling via spectral methods
- How robust are reconstruction thresholds for community detection?
Cited In (58)
- Fluctuation results for general block spin Ising models
- Joint community detection and rotational synchronization via semidefinite programming
- Community detection via an efficient nonconvex optimization approach based on modularity
- Community detection and stochastic block models: recent developments
- Optimal bipartite network clustering
- A review on spectral clustering and stochastic block models
- A likelihood-ratio type test for stochastic block models with bounded degrees
- Title not available (Why is that?)
- A review of dynamic network models with latent variables
- Title not available (Why is that?)
- Measuring the stability of spectral clustering
- On semidefinite relaxations for the block model
- Dynamic network models and graphon estimation
- Covariate regularized community detection in sparse graphs
- Overlapping community detection in networks via sparse spectral decomposition
- Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
- When do birds of a feather flock together? \(k\)-means, proximity, and conic programming
- Structural similarity: spectral methods for relaxed blockmodeling
- Entrywise eigenvector analysis of random matrices with low expected rank
- Universal inference
- Integer programs for one- and two-mode blockmodeling based on prespecified image matrices for structural and regular equivalence
- Non-convex exact community recovery in stochastic block model
- Semidefinite programs on sparse random graphs and their application to community detection
- Community detection with a subsampled semidefinite program
- Profile likelihood biclustering
- Maximum likelihood estimation of sparse networks with missing observations
- Strong consistency, graph Laplacians, and the stochastic block model
- Title not available (Why is that?)
- Convex relaxation methods for community detection
- Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
- Hypothesis testing for populations of networks
- Subsampling spectral clustering for stochastic block models in large-scale networks
- Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
- Fluctuations for block spin Ising models
- Partial recovery bounds for clustering with the relaxed \(K\)-means
- Model assisted variable clustering: minimax-optimal recovery and algorithms
- Rate optimal Chernoff bound and application to community detection in the stochastic block models
- Clustering is semidefinitely not that hard: nonnegative SDP for manifold disentangling
- Multi-group binary choice with social interaction and a random communication structure -- a random graph approach
- Exact recovery in block spin Ising models at the critical line
- Spectral clustering-based community detection using graph distance and node attributes
- Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering
- Exact clustering of weighted graphs via semidefinite programming
- Hierarchical Community Detection by Recursive Partitioning
- Convex optimization for the densest subgraph and densest submatrix problems
- Title not available (Why is that?)
- Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates
- \(k\)-median: exact recovery in the extended stochastic ball model
- Phases of small worlds: a mean field formulation
- Community detection in sparse networks via Grothendieck's inequality
- Matched bipartite block model with covariates
- A Time-Varying Network for Cryptocurrencies
- A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
- Semidefinite programming based community detection for node-attributed networks and multiplex networks
- Community detection in complex networks: from statistical foundations to data science applications
- Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
- Tractably modelling dependence in networks beyond exchangeability
- Community detection with nodal information: likelihood and its variational approximation
Uses Software
This page was built for publication: On semidefinite relaxations for the block model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1747735)
