Rates of Convergence of Spectral Methods for Graphon Estimation
  This paper studies the problem of estimating the grahpon model - the
underlying generating mechanism of a network. Graphon estimation arises in many
applications such as predicting missing links in networks and learning user
preferences in recommender systems. The graphon model deals with a random graph
of $n$ vertices such that each pair of two vertices $i$ and $j$ are connected
independently with probability $\rho \times f(x_i,x_j)$, where $x_i$ is the
unknown $d$-dimensional label of vertex $i$, $f$ is an unknown symmetric
function, and $\rho$ is a scaling parameter characterizing the graph sparsity.
Recent studies have identified the minimax error rate of estimating the graphon
from a single realization of the random graph. However, there exists a wide gap
between the known error rates of computationally efficient estimation
procedures and the minimax optimal error rate.
  Here we analyze a spectral method, namely universal singular value
thresholding (USVT) algorithm, in the relatively sparse regime with the average
vertex degree $n\rho=\Omega(\log n)$. When $f$ belongs to H\"{o}lder or Sobolev
space with smoothness index $\alpha$, we show the error rate of USVT is at most
$(n\rho)^{ -2 \alpha / (2\alpha+d)}$, approaching the minimax optimal error
rate $\log (n\rho)/(n\rho)$ for $d=1$ as $\alpha$ increases. Furthermore, when
$f$ is analytic, we show the error rate of USVT is at most $\log^d
(n\rho)/(n\rho)$. In the special case of stochastic block model with $k$
blocks, the error rate of USVT is at most $k/(n\rho)$, which is larger than the
minimax optimal error rate by at most a multiplicative factor $k/\log k$. This
coincides with the computational gap observed for community detection. A key
step of our analysis is to derive the eigenvalue decaying rate of the edge
probability matrix using piecewise polynomial approximations of the graphon
function $f$.
