Rates of Convergence of Spectral Methods for Graphon Estimation
This work addresses the computational gap in graphon estimation for applications like link prediction and recommender systems, providing near-optimal rates for spectral methods.
The paper tackles the problem of graphon estimation from a single network realization, showing that the universal singular value thresholding (USVT) algorithm achieves error rates close to minimax optimal in sparse regimes, with specific bounds such as $(n\ ho)^{-2\\alpha/(2\\alpha+d)}$ for Hölder or Sobolev spaces and $\\log^d(n\ ho)/(n\ ho)$ for analytic functions.
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$.