On semidefinite relaxations for the block model.

*(English)*Zbl 1393.62021The 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.”

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

Reviewer: Mathias Trabs (Hamburg)

##### MSC:

62G20 | Asymptotic properties of nonparametric inference |

62H12 | Estimation in multivariate analysis |

62H30 | Classification and discrimination; cluster analysis (statistical aspects) |

90C22 | Semidefinite programming |

##### Software:

SDPLR
PDF
BibTeX
XML
Cite

\textit{A. A. Amini} and \textit{E. Levina}, Ann. Stat. 46, No. 1, 149--179 (2018; Zbl 1393.62021)

Full Text:
DOI

##### References:

[1] | Abbe, E., Bandeira, A. S. and Hall, G. (2016). Exact recovery in the stochastic block model. IEEE Trans. Inform. Theory 62 471-487. · Zbl 1359.94047 |

[2] | Abbe, E. and Sandon, C. (2015). Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. In 2015 IEEE 56 th Annual Symposium on Foundations of Computer Science—FOCS 2015 670-688. IEEE Computer Soc., Los Alamitos, CA. |

[3] | Agarwal, N., Bandeira, A. S., Koiliaris, K. and Kolla, A. (2017). Multisection in the stochastic block model using semidefinite programming. In Applied and Numerical Harmonic Analysis (H. Boche, G. Caire, R. Calderbank, et al., eds.) 125-162. Birkhäuser, Cham. |

[4] | Airoldi, E. M., Blei, D. M., Fienberg, S. E. and Xing, E. P. (2008). Mixed membership stochastic blockmodels. J. Mach. Learn. Res.9 1981-2014. · Zbl 1225.68143 |

[5] | Airoldi, E. M., Costa, T. B. and Chan, S. H. (2013). Stochastic blockmodel approximation of a graphon: Theory and consistent estimation. In Advances in NIPS 26, 692-700. |

[6] | Aldous, D. J. (1981). Representations for partially exchangeable arrays of random variables. J. Multivariate Anal.11 581-598. · Zbl 0474.60044 |

[7] | Ames, B. P. W. and Vavasis, S. A. (2014). Convex optimization for the planted \(k\)-disjoint-clique problem. Math. Program.143 299-337. · Zbl 1291.90194 |

[8] | Amini, A. A., Chen, A., Bickel, P. J. and Levina, E. (2013). Pseudo-likelihood methods for community detection in large sparse networks. Ann. Statist.41 2097-2122. · Zbl 1277.62166 |

[9] | Amini, A. A. and Levina, E. (2018). Supplement to “On semidefinite relaxations for the block model.” DOI:10.1214/17-AOS1545SUPP. · Zbl 1393.62021 |

[10] | Amini, A. A. and Wainwright, M. J. (2009). High-dimensional analysis of semidefinite relaxations for sparse principal components. Ann. Statist.37 2877-2921. · Zbl 1173.62049 |

[11] | Awasthi, P., Bandeira, A. S., Charikar, M., Krishnaswamy, R., Villar, S. and Ward, R. (2015). Relax, no need to round: Integrality of clustering formulations. In ITCS’15—Proceedings of the 6 th Innovations in Theoretical Computer Science 191-200. ACM, New York. · Zbl 1364.62144 |

[12] | Bandeira, A. S. (2015). Random Laplacian matrices and convex relaxations. Available at arXiv:1504.03987. · Zbl 1386.15065 |

[13] | Bandeira, A. S. (2016). A note on probably certifiably correct algorithms. C. R. Math. Acad. Sci. Paris 354 329-333. · Zbl 1387.68315 |

[14] | Bickel, P., Choi, D., Chang, X. and Zhang, H. (2013). Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels. Ann. Statist.41 1922-1943. · Zbl 1292.62042 |

[15] | Bickel, P. J. and Chen, A. (2009). A nonparametric view of network models and Newman-Girvan and other modularities. Proc. Natl. Acad. Sci. USA 106 21068-21073. · Zbl 1359.62411 |

[16] | Burer, S. and Monteiro, R. D. C. (2003). A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program.95 329-357. · Zbl 1030.90077 |

[17] | Cai, T. T. and Li, X. (2015). Robust and computationally feasible community detection in the presence of arbitrary outlier nodes. Ann. Statist.43 1027-1059. · Zbl 1328.62381 |

[18] | Celisse, A., Daudin, J.-J. and Pierre, L. (2012). Consistency of maximum-likelihood and variational estimators in the stochastic block model. Electron. J. Stat.6 1847-1899. · Zbl 1295.62028 |

[19] | Chaudhuri, K., Chung, F. and Tsiatas, A. (2012). Spectral clustering of graphs with general degrees in the extended planted partition model. In JMLR Workshop and Conference Proceedings 23, 35.1-35.23. |

[20] | Chen, Y., Sanghavi, S. and Xu, H. (2014). Improved graph clustering. IEEE Trans. Inform. Theory 60 6440-6455. · Zbl 1360.94499 |

[21] | Chen, Y. and Xu, J. (2016). Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices. J. Mach. Learn. Res.17 882-938. · Zbl 1360.62320 |

[22] | d’Aspremont, A., El Ghaoui, L., Jordan, M. I. and Lanckriet, G. R. G. (2007). A direct formulation for sparse PCA using semidefinite programming. SIAM Rev.49 434-448. · Zbl 1128.90050 |

[23] | Decelle, A., Krzakala, F., Moore, C. and Zdeborová, L. (2011). Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Phys. Rev. E 84 066106. |

[24] | Decelle, A., Krzakala, F., Moore, C. and Zdeborová, L. (2012). Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Phys. Rev. E 84 066106. |

[25] | Feige, U. and Ofek, E. (2005). Spectral techniques applied to sparse random graphs. Random Structures Algorithms 27 251-275. · Zbl 1076.05073 |

[26] | Gao, C., Lu, Y. and Zhou, H. H. (2015). Rate-optimal graphon estimation. Ann. Statist.43 2624-2652. · Zbl 1332.60050 |

[27] | Guédon, O. and Vershynin, R. (2016). Community detection in sparse networks via Grothendieck’s inequality. Probab. Theory Related Fields 165 1025-1049. · Zbl 1357.90111 |

[28] | Hajek, B., Wu, Y. and Xu, J. (2016). Achieving exact cluster recovery threshold via semidefinite programming. IEEE Trans. Inform. Theory 62 2788-2797. · Zbl 1359.94222 |

[29] | Hajek, B., Wu, Y. and Xu, J. (2016). Achieving exact cluster recovery threshold via semidefinite programming: Extensions. IEEE Trans. Inform. Theory 62 5918-5937. · Zbl 1359.94951 |

[30] | Holland, P. W., Laskey, K. B. and Leinhardt, S. (1983). Stochastic blockmodels: First steps. Soc. Netw.5 109-137. |

[31] | Javanmard, A., Montanari, A. and Ricci-Tersenghi, F. (2016). Phase transitions in semidefinite relaxations. Proc. Natl. Acad. Sci. USA 113 E2218-E2223. · Zbl 1359.62188 |

[32] | Joseph, A. and Yu, B. (2016). Impact of regularization on spectral clustering. Ann. Statist.44 1765-1791. · Zbl 1357.62229 |

[33] | Klopp, O., Tsybakov, A. B., Verzelen, N. et al. (2017). Oracle inequalities for network models and sparse graphon estimation. Ann. Statist.45 316-354. · Zbl 1367.62090 |

[34] | Le, C. M., Levina, E. and Vershynin, R. (2015). Sparse random graphs: Regularization and concentration of the Laplacian. Preprint. Available at arXiv:1502.03049. · Zbl 1373.05179 |

[35] | Lei, J. and Rinaldo, A. (2015). Consistency of spectral clustering in stochastic block models. Ann. Statist.43 215-237. · Zbl 1308.62041 |

[36] | Lusseau, D. and Newman, M. E. J. (2004). Identifying the role that animals play in their social networks. Proc. R. Soc. Lond., B Biol. Sci.271 S477-S481. |

[37] | Massoulié, L. (2014). Community detection thresholds and the weak Ramanujan property. In STOC’14—Proceedings of the 2014 ACM Symposium on Theory of Computing 694-703. ACM, New York. · Zbl 1315.68210 |

[38] | Mathieu, C. and Schudy, W. (2010). Correlation clustering with noisy input. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms 712-728. SIAM, Philadelphia, PA. · Zbl 1288.68197 |

[39] | Moitra, A., Perry, W. and Wein, A. S. (2016). How robust are reconstruction thresholds for community detection? In STOC’16—Proceedings of the 48 th Annual ACM SIGACT Symposium on Theory of Computing 828-841. ACM, New York. · Zbl 1381.62190 |

[40] | Montanari, A. (2016). A Grothendieck-type inequality for local maxima. Preprint. Available at arXiv:1603.04064. |

[41] | Montanari, A. and Sen, S. (2016). Semidefinite programs on sparse random graphs and their application to community detection. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing 814-827. ACM, New York. · Zbl 1376.90043 |

[42] | Mossel, E., Neeman, J. and Sly, A. (2012). Stochastic block models and reconstruction. Available at arXiv:1202.1499. |

[43] | Mossel, E., Neeman, J. and Sly, A. (2015). Consistency thresholds for the planted bisection model. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing. STOC ’15 69-75. ACM, New York. · Zbl 1321.05242 |

[44] | Mossel, E., Neeman, J. and Sly, A. (2017). A proof of the block model threshold conjecture. Combinatorica. DOI:10.1007/s00493-016-3238-8. |

[45] | Nowicki, K. and Snijders, T. A. B. (2001). Estimation and prediction for stochastic blockstructures. J. Amer. Statist. Assoc.96 1077-1087. · Zbl 1072.62542 |

[46] | Olhede, S. C. and Wolfe, P. J. (2014). Network histograms and universality of blockmodel approximation. Proc. Natl. Acad. Sci. USA 111 14722-14727. |

[47] | Peng, J. and Wei, Y. (2007). Approximating \(K\)-means-type clustering via semidefinite programming. SIAM J. Optim.18 186-205. · Zbl 1146.90046 |

[48] | Perry, A. and Wein, A. S. (2017). A semidefinite program for unbalanced multisection in the stochastic block model. In Sampling Theory and Applications (SampTA), 2017 International Conference on 64-67. IEEE, New York. |

[49] | Qin, T. and Rohe, K. (2013). Regularized spectral clustering under the degree-corrected stochastic blockmodel. In Advances in Neural Information Processing Systems 3120-3128. |

[50] | Rohe, K., Chatterjee, S. and Yu, B. (2011). Spectral clustering and the high-dimensional stochastic blockmodel. Ann. Statist.39 1878-1915. · Zbl 1227.62042 |

[51] | Snijders, T. A. B. and Nowicki, K. (1997). Estimation and prediction for stochastic blockmodels for graphs with latent block structure. J. Classification 14 75-100. · Zbl 0896.62063 |

[52] | Tomozei, D.-C. and Massoulié, L. (2014). Distributed user profiling via spectral methods. Stoch. Syst.4 1-43. · Zbl 1315.68024 |

[53] | Vu, V. Q., Cho, J., Lei, J. and Rohe, K. (2013). Fantope projection and selection: A near-optimal convex relaxation of sparse PCA. In Advances in Neural Information Processing Systems 2670-2678. |

[54] | Wainwright, M. J. (2009). Sharp thresholds for high-dimensional and noisy sparsity recovery using \(ℓ_{1}\)-constrained quadratic programming (Lasso). IEEE Trans. Inform. Theory 55 2183-2202. · Zbl 1367.62220 |

[55] | Wolfe, P. J. and Olhede, S. C. (2013). Nonparametric graphon estimation. Preprint. Available at arXiv:1309.5936. |

[56] | Xing, E. P. and Jordan, M. I. (2003). On semidefinite relaxations for normalized \(k\)-cut and connections to spectral clustering. Technical report, Univ. California, Berkeley. |

[57] | Yan, B. and Sarkar, P. (2016). Convex relaxation for community detection with covariates. Preprint. Available at arXiv:1607.02675. |

[58] | Zhang, Y., Levina, E. and Zhu, J. (2015). Estimating network edge probabilities by neighborhood smoothing. Available at arXiv:1509.08588. · Zbl 07072327 |

[59] | Zhao, Y., Levina, E. and Zhu, J. (2012). Consistency of community detection in networks under degree-corrected stochastic block models. Ann. Statist.40 2266-2292. · Zbl 1257.62095 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.