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 k\geq 5 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 k\geq 5 but not for k\leq 4!

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

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 k\geq 5 we still don’t know where exactly it lies, so the problem remains! A particularly interesting regime described in these papers is the ``a=0 case, which is tightly connected to coloring.

Congratulations to the four of them!


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s