Below the Kesten-Stigum bound for Community Detection

I have great news: There was (a lot) of progress on the Open Problem 9.1. of Ten Lectures and Forty-Two Open Problems in the Mathematics of Data Science in the last couple of weeks, independently by Emmanuel Abbe & Colin Sandon and by Jess Banks & Cristopher Moore.

I’ll refer the reader to both Section 9 of my notes and the papers above for a description of the context of the problem, but, in a nutshell, the Conjecture of Decelle et al. that stated that for communities it is information theoretically possible to recover the community structure better than chance below the Kesten-Stigum bound is now proved! This is particularly remarkable because the Kesten-Stigum bound is suspected to characterize the limit of efficient algorithms, which suggests the bizarre phenomenon that a computational gap is present for but not for !

In fact, Emmanuel Abbe & Colin Sandon shed extra light on the Kesten-Stigum bound by developping a new algorithm, Acyclic Belief Propagation, and proving that it reaches the Kesten-Stigum bound for all .

Jess Banks & Cristopher Moore also investigate the threshold at which is starts being impossible to distinguish the graph drawn from the stochastic block model from an Erdos-Renyi graph with the same average degree!

While we now know that the information theoretical bound cross the Kesten-Stigum bound for we still don’t know where exactly it lies, so the problem remains! A particularly interesting regime described in these papers is the case, which is tightly connected to coloring.

Congratulations to the four of them!

Advertisement