On semidefinite relaxations for the block model
type: Item
instance of: scholarly article
title: On semidefinite relaxations for the block model
zbMATH Open document ID: 1393.62021
DOI: 10.1214/17-AOS1545
author: Arash A. Amini
author: Elizaveta Levina
published in: The Annals of Statistics
publication date: 2018-04-27T00:00:00Z
full work available at URL: https://arxiv.org/abs/1406.5647
review text: The article proposes a new semidefinite programming solution to the calibrating of the stochastic block model (SBM). In the SBM an adjacency matrix \(A\in\{0,1\}^{n\times n}\) is observed whose entries \(A_{ij}\) are Bernoulli random variables with \(\mathbb E[A_{i,j}|z_i,z_j]=z_i^\top\Psi z_j\) for unobserved \(z_i\in\{0,1\}^K\), \(i=1,\dots,n\) and a parameter matrix \(\Psi\in[0,1]^{K\times K}\). The authors focus first on the special case where \(\Psi\) is constant on the diagonal and constant off the diagonal, but analyze the method in a larger class of SBMs. In this simple case the maximum likelihood estimator is of the form, denoting \(Z=(z_1,\dots,z_n)^T\in\{0,1\}^{n\times K}\), \[ \hat Z=\text{argmax}_{Z\in\mathcal Z}\langle A,ZZ^T\rangle-\lambda\langle E_n,ZZ^T\rangle, \] which is a computationally infeasible optimization problem due to the special structure of \(\mathcal Z\). Writing \(X=ZZ^T\in\{0,1\}^{n\times n}\) we may equivalently maximize in \(X\). The semidefinite programming solution is obtained by a relaxation of the MLE, more precisely, by considering appropriate subsets of \(\mathcal X:=\{ZZ^\top:Z\in\mathcal Z\}\). The authors describe their results as follows: ``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.''
reviewed by: Mathias Trabs
Mathematics Subject Classification ID: 62G20
Mathematics Subject Classification ID: 62H12
Mathematics Subject Classification ID: 62H30
Mathematics Subject Classification ID: 90C22
zbMATH DE Number: 6865108
zbMATH Keywords: community detection
zbMATH Keywords: network
zbMATH Keywords: semidefinite programming
zbMATH Keywords: stochastic block model
describes a project that uses: SDPLR
MaRDI profile type: Publication
arXiv ID: 1406.5647
cites work: Exact Recovery in the Stochastic Block Model
cites work: Mixed membership stochastic blockmodels
cites work: Representations for partially exchangeable arrays of random variables
cites work: Convex optimization for the planted \(k\)-disjoint-clique problem
cites work: Pseudo-likelihood methods for community detection in large sparse networks
cites work: High-dimensional analysis of semidefinite relaxations for sparse principal components
cites work: Relax, No Need to Round
cites work: Random Laplacian matrices and convex relaxations
cites work: A note on probably certifiably correct algorithms
cites work: Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
cites work: A nonparametric view of network models and Newman–Girvan and other modularities
cites work: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
cites work: Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
cites work: Consistency of maximum-likelihood and variational estimators in the stochastic block model
cites work: Improved Graph Clustering
cites work: Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices
cites work: A Direct Formulation for Sparse PCA Using Semidefinite Programming
cites work: Spectral techniques applied to sparse random graphs
cites work: Rate-optimal graphon estimation
cites work: Community detection in sparse networks via Grothendieck's inequality
cites work: Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
cites work: Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
cites work: Phase transitions in semidefinite relaxations
cites work: Impact of regularization on spectral clustering
cites work: Oracle inequalities for network models and sparse graphon estimation
cites work: Concentration and regularization of random graphs
cites work: Consistency of spectral clustering in stochastic block models
cites work: Community detection thresholds and the weak Ramanujan property
cites work: Q5417661
cites work: How robust are reconstruction thresholds for community detection?
cites work: Semidefinite programs on sparse random graphs and their application to community detection
cites work: Belief propagation, robust reconstruction and optimal recovery of block models
cites work: Consistency thresholds for the planted bisection model
cites work: A proof of the block model threshold conjecture
cites work: Estimation and Prediction for Stochastic Blockstructures
cites work: Approximating K‐means‐type Clustering via Semidefinite Programming
cites work: Spectral clustering and the high-dimensional stochastic blockmodel
cites work: Estimation and prediction for stochastic blockmodels for graphs with latent block structure
cites work: Distributed user profiling via spectral methods
cites work: Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)
cites work: Estimating network edge probabilities by neighbourhood smoothing
cites work: Consistency of community detection in networks under degree-corrected stochastic block models
description: scientific article