Videos

Detection, Estimation, and Reconstruction in Networks: Sharp Phase Transitions in Estimation with Low-Degree Polynomials

Presenter
April 22, 2025
Keywords:
  • combinatorial statistics
  • random graphs
  • network inference
  • network reconstruction
  • detection
  • estimation
MSC:
  • 05C80 - Random graphs (graph-theoretic aspects) [See also 60B20]
  • 60C05 - Combinatorial probability
Abstract
In the stochastic block model (a canonical model for finding hidden communities in random networks), it has long been conjectured that the so-called Kesten-Stigum (KS) threshold marks the boundary between the "easy" (polynomial-time solvable) and "hard" (computationally intractable) regimes. We substantiate this conjecture by proving a sharp transition at the KS bound for a restricted class of estimators, namely those that compute low-degree polynomials in the entries of the adjacency matrix. This builds on a long line of work that uses low-degree polynomials as a proxy for efficient computation, but our work is the first to establish "sharp" thresholds for the estimation (rather than detection) task. I will also discuss some unexpected phenomena that emerge when the number of communities grows with the problem size. This is based on multiple joint works with Youngtak Sohn, Byron Chin, and Elchanan Mossel.