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 ρ × f(xi,xj), where xi 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ρ=Omega(log n). When f belongs to H"older 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 logd (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.