  Graphon estimation has been one of the most fundamental problems in network
analysis and has received considerable attention in the past decade. From the
statistical perspective, the minimax error rate of graphon estimation has been
established by Gao et al (2015) for both stochastic block model and
nonparametric graphon estimation. The statistical optimal estimators are based
on constrained least squares and have computational complexity exponential in
the dimension. From the computational perspective, the best-known
polynomial-time estimator is based universal singular value thresholding, but
it can only achieve a much slower estimation error rate than the minimax one.
The computational optimality of the USVT or the existence of a computational
barrier in graphon estimation has been a long-standing open problem. In this
work, we provide rigorous evidence for the computational barrier in graphon
estimation via low-degree polynomials. Specifically, in SBM graphon estimation,
we show that for low-degree polynomial estimators, their estimation error rates
cannot be significantly better than that of the USVT under a wide range of
parameter regimes and in nonparametric graphon estimation, we show low-degree
polynomial estimators achieve estimation error rates strictly slower than the
minimax rate. Our results are proved based on the recent development of
low-degree polynomials by Schramm and Wein (2022), while we overcome a few key
challenges in applying it to the general graphon estimation problem. By
leveraging our main results, we also provide a computational lower bound on the
clustering error for community detection in SBM with a growing number of
communities and this yields a new piece of evidence for the conjectured
Kesten-Stigum threshold for efficient community recovery. Finally, we extend
our computational lower bounds to sparse graphon estimation and biclustering.
