Bad local minima exist in the stochastic block model
<|reference_start|>Bad local minima exist in the stochastic block model: 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. (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 (2003)].<|reference_end|>
@article{coja-oghlan2024bad,
    title={Bad local minima exist in the stochastic block model},
    author={Amin Coja-Oghlan, Lena Krieg, Johannes Christian Lawnik, Olga
  Scheftelowitsch},
    journal={arXiv preprint arXiv:2407.17851},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.17851},
    primaryClass={math.ST cs.DM cs.IT math-ph math.IT math.MP math.PR stat.TH}
}