Bad local minima exist in the stochastic block model

2024/07/25 by Coja-Oghlan, Amin, Krieg, Lena, Lawnik, Johannes Christian +1
#05C80 (Primary) 62B10 #68R10 (Secondary) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Information Theory (cs.IT) #Mathematical Physics (math-ph) #Probability (math.PR) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2407.17851

Abstract

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)].

Related

• Recovering communities in the general stochastic block model without\n knowing the parameters
• Confidence sets in a sparse stochastic block model with two communities of unknown sizes
• Uncertainty quantification and testing in a stochastic block model with two unequal communities
• Optimal Bayesian estimation in stochastic block models
• Exact Recovery in the Stochastic Block Model