Timezone: »
Oral
Rates of Convergence of Spectral Methods for Graphon Estimation
Jiaming Xu
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 polynomialtime estimators and the minimax optimal error rate. We improve on the previously known error rates of polynomialtime 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)

2018 Poster: Rates of Convergence of Spectral Methods for Graphon Estimation »
Fri Jul 13th 04:15  07:00 PM Room Hall B
More from the Same Authors

2021 Poster: LearnerPrivate Convex Optimization »
Jiaming Xu · Kuang Xu · Dana Yang 
2021 Spotlight: LearnerPrivate Convex Optimization »
Jiaming Xu · Kuang Xu · Dana Yang 
2020 Poster: Spectral Graph Matching and Regularized Quadratic Relaxations: Algorithm and Theory »
Zhou Fan · Cheng Mao · Yihong Wu · Jiaming Xu