On semidefinite relaxations for the block model (Q1747735)

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.''