Rates of Convergence of Spectral Methods for Graphon Estimation

Abstract

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 $ρ\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 $ρ$ 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ρ=Ω(\log n)$. When $f$ belongs to Hölder or Sobolev space with smoothness index $α$, we show the error rate of USVT is at most $(nρ)^{ -2 α/ (2α+d)}$, approaching the minimax optimal error rate $\log (nρ)/(nρ)$ for $d=1$ as $α$ increases. Furthermore, when $f$ is analytic, we show the error rate of USVT is at most $\log^d (nρ)/(nρ)$. In the special case of stochastic block model with $k$ blocks, the error rate of USVT is at most $k/(nρ)$, 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$.