Timezone: »

Rates of Convergence of Spectral Methods for Graphon Estimation
Jiaming Xu

Fri Jul 13 07:50 AM -- 08:00 AM (PDT) @ K11
This paper studies the problemof estimating the graphon function -- a generativemechanism for a class of random graphs that are usefulapproximations to real networks.Specifically, a graph of $n$ vertices is generated such that each pair of two vertices $i$ and $j$ are connected independently with probability$\rho_n \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 $\rho_n$,assumed to be $\Omega(\log n/n)$,is a scaling parameter characterizing the graph sparsity. The taskis to estimate graphon $f$ given the graph. Recent studies have identified the minimax optimal estimation error rate for $d=1$. However, there exists a wide gap betweenthe known error rates of polynomial-time estimators and the minimax optimal error rate. We improve on the previously known error rates of polynomial-time estimators, by analyzing a spectral method, namely universal singular value thresholding (USVT) algorithm.When $f$ belongs to either H\"{o}lder or Sobolev space with smoothness index $\alpha$, we show the error rates of USVT are at most $(n\rho)^{ -2 \alpha / (2\alpha+d)}$.These error rates approach the minimax optimal error rate $\log (n\rho)/(n\rho)$ proved in prior work for $d=1$, as $\alpha$ increases, i.e., $f$ becomes smoother. Furthermore, when $f$ is analytic with infinitely many times differentiability, we show the error rate of USVT is at most $\log^d (n\rho)/(n\rho)$. When $f$ is a step function which corresponds to the stochastic block modelwith $k$ blocks for some $k$, the error rate of USVT is at most $k/(n\rho)$, whichis larger than the minimax optimal error rate by at most a multiplicative factor $k/\log k$.This coincides with the computational gap observed in community detection. A key ingredient of our analysis is to derive the eigenvalue decaying rate of the edge probability matrix using piecewise polynomial approximations of the graphon function $f$.

Author Information

Jiaming Xu (Duke University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors