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 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=( 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 (n)/(n) for d=1 as increases. Furthermore, when f is analytic, we show the error rate of USVT is at most ^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/ 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.

Tasks

Reproductions