Bad local minima exist in the stochastic block model - Coja-Oghlan, Amin; Krieg, Lena; Lawnik, Johannes Christian; Scheftelowitsch, Olga (Technische Universität Dortmund, 2024)
We study the disassortative stochastic block model with three communities, a well-studied model of graph partitioning and Bayesian inference for which detailed predictions based on the cavity method exist (Decelle et al. in Phys Rev E 84:066106, 2011). We provide strong evidence that for a part of the phase where efficient algorithms exist that approximately reconstruct the communities, inference based on maximum a posteriori (MAP) fails. In other words, we show that there exist modes of the posterior distribution that have a vanishing agreement with the ground truth. The proof is based on the analysis of a graph colouring algorithm from Achlioptas and Moore (J Comput Syst Sci 67:441–471, 2003).
Journal of statistical physics; 191(11)
Keywords: Stochastic block model; Random graphs; Maximum a posteriori inference; 004; Maximum-a-posteriori-Schätzung; Zufallsgraph