Rates of Convergence of Spectral Methods for Graphon Estimation
share
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ö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 (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.
READ FULL TEXT