On semidefinite relaxations for the block model
From MaRDI portal
(Redirected from Publication:1747735)
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.
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
Cites work
- A Direct Formulation for Sparse PCA Using Semidefinite Programming
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- A nonparametric view of network models and Newman–Girvan and other modularities
- A note on probably certifiably correct algorithms
- A proof of the block model threshold conjecture
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
- Approximating K‐means‐type Clustering via Semidefinite Programming
- Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
- Belief propagation, robust reconstruction and optimal recovery of block models
- Community detection in sparse networks via Grothendieck's inequality
- Community detection thresholds and the weak Ramanujan property
- Concentration and regularization of random graphs
- 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
- Convex optimization for the planted \(k\)-disjoint-clique problem
- Correlation clustering with noisy input
- Distributed user profiling via spectral methods
- Estimating network edge probabilities by neighbourhood smoothing
- Estimation and Prediction for Stochastic Blockstructures
- Estimation and prediction for stochastic blockmodels for graphs with latent block structure
- Exact Recovery in the Stochastic Block Model
- High-dimensional analysis of semidefinite relaxations for sparse principal components
- How robust are reconstruction thresholds for community detection?
- Impact of regularization on spectral clustering
- Improved Graph Clustering
- Mixed membership stochastic blockmodels
- On semidefinite relaxations for the block model
- Oracle inequalities for network models and sparse graphon estimation
- Phase transitions in semidefinite relaxations
- Pseudo-likelihood methods for community detection in large sparse networks
- Random Laplacian matrices and convex relaxations
- Rate-optimal graphon estimation
- Relax, no need to round: integrality of clustering formulations
- Representations for partially exchangeable arrays of random variables
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- Semidefinite programs on sparse random graphs and their application to community detection
- Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)
- Spectral clustering and the high-dimensional stochastic blockmodel
- Spectral techniques applied to sparse random graphs
- Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices
Cited in
(58)- Matched bipartite block model with covariates
- Fluctuation results for general block spin Ising models
- A Time-Varying Network for Cryptocurrencies
- Community detection via an efficient nonconvex optimization approach based on modularity
- Joint community detection and rotational synchronization via semidefinite programming
- 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
- A review of dynamic network models with latent variables
- scientific article; zbMATH DE number 7255095 (Why is no real title available?)
- On semidefinite relaxations for the block model
- Measuring the stability of spectral clustering
- scientific article; zbMATH DE number 7626708 (Why is no real title available?)
- Dynamic network models and graphon estimation
- Overlapping community detection in networks via sparse spectral decomposition
- Covariate regularized community detection in sparse graphs
- When do birds of a feather flock together? \(k\)-means, proximity, and conic programming
- Structural similarity: spectral methods for relaxed blockmodeling
- Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
- Entrywise eigenvector analysis of random matrices with low expected rank
- A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
- Integer programs for one- and two-mode blockmodeling based on prespecified image matrices for structural and regular equivalence
- Universal inference
- Non-convex exact community recovery in stochastic block model
- Semidefinite programs on sparse random graphs and their application to community detection
- Semidefinite programming based community detection for node-attributed networks and multiplex networks
- Community detection with a subsampled semidefinite program
- Community detection in complex networks: from statistical foundations to data science applications
- Profile likelihood biclustering
- Maximum likelihood estimation of sparse networks with missing observations
- 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
- scientific article; zbMATH DE number 7415091 (Why is no real title available?)
- Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
- Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
- Hypothesis testing for populations of networks
- Subsampling spectral clustering for stochastic block models in large-scale networks
- Tractably modelling dependence in networks beyond exchangeability
- 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
- Multi-group binary choice with social interaction and a random communication structure -- a random graph approach
- Clustering is semidefinitely not that hard: nonnegative SDP for manifold disentangling
- 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
- Convex optimization for the densest subgraph and densest submatrix problems
- Exact clustering of weighted graphs via semidefinite programming
- Hierarchical Community Detection by Recursive Partitioning
- scientific article; zbMATH DE number 7307464 (Why is no real title available?)
- Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates
- Phases of small worlds: a mean field formulation
- \(k\)-median: exact recovery in the extended stochastic ball model
- Community detection in sparse networks via Grothendieck's inequality
- Community detection with nodal information: likelihood and its variational approximation
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)
