Clustering and Community Recovery in Polynomial Time below the Kesten-Stigum Threshold
Christophe Giraud
Paris Saclay University
Seminar of the Series MLP@P (Machine Learning Physics @ Plateau), joint with LISN and IPhT.
Where: LISN, bat 660 salle 2014 (2° étage)
Predictions based on the cavity and replica methods stipulate that clustering in the Gaussian Mixture Model and community recovery in the Stochastic Block Model cannot be achieved in polynomial time below the Kesten-Stigum (KS) threshold. These predictions have stimulated an active line of mathematical research, and have been confirmed rigorously in a wide range of regimes: spectral based algorithms succeed above the KS threshold, while computational hardness below the KS threshold has been proved within the low-degree polynomials framework. However, the picture changes when the number of clusters or communities is large. In such regimes, the computational barrier appears to lie below the KS threshold, and seems to be disconnected from spectral algorithms. In this talk,I will present these recent results, and discuss some related open questions.