# Rates of Convergence of Spectral Methods for Graphon Estimation

arXiv: https://arxiv.org/abs/1709.03183 · HTML: https://mlsanity.com/paper/1709.03183/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Sep 2017.

## Built on by (most cited first, 28 of 28)

- [Causal Matrix Completion](https://mlsanity.com/paper/2109.15154/) (2021)
- [Transferability Properties of Graph Neural Networks](https://mlsanity.com/paper/2112.04629/) (2021)
- [Learning Graphon Mean Field Games and Approximate Nash Equilibria](https://mlsanity.com/paper/2112.01280/) (2021)
- [Conformal Prediction for Network-Assisted Regression](https://mlsanity.com/paper/2302.10095/) (2023)
- [Matrix factorisation and the interpretation of geodesic distance](https://mlsanity.com/paper/2106.01260/) (2021)
- [Federated Optimization of Smooth Loss Functions](https://mlsanity.com/paper/2201.01954/) (2022)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Optimal network online change point localisation](https://mlsanity.com/paper/2101.05477/) (2021)
- [Learning Graphon Autoencoders for Generative Graph Modeling](https://mlsanity.com/paper/2105.14244/) (2021)
- [Nonparametric Matrix Estimation with One-Sided Covariates](https://mlsanity.com/paper/2110.13969/) (2021)
- [Beyond the Signs: Nonparametric Tensor Completion via Sign Series](https://mlsanity.com/paper/2102.00384/) (2021)
- [On the Validity of Conformal Prediction for Network Data Under Non-Uniform Sampling](https://mlsanity.com/paper/2306.07252/) (2023)
- [Transfer Learning for Latent Variable Network Models](https://mlsanity.com/paper/2406.03437/) (2024)
- [Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations](https://mlsanity.com/paper/2111.04681/) (2021)
- [A Causal Inference Framework for Data Rich Environments](https://mlsanity.com/paper/2504.01702/) (2025)
- [Exploiting Observation Bias to Improve Matrix Completion](https://mlsanity.com/paper/2306.04775/) (2023)
- [Two-Sided Nearest Neighbors: An adaptive and minimax optimal procedure for matrix completion](https://mlsanity.com/paper/2411.12965/) (2024)
- [Transfer Learning on Edge Connecting Probability Estimation under Graphon Model](https://mlsanity.com/paper/2510.05527/) (2025)
- [Hawkes Processes on Graphons](https://mlsanity.com/paper/2102.02741/) (2021)
- [Asymptotics of ℓ2 Regularized Network Embeddings](https://mlsanity.com/paper/2201.01689/) (2022)
- [Statistical and computational rates in high rank tensor estimation](https://mlsanity.com/paper/2304.04043/) (2023)
- [A Deep Learning Method for Optimal Investment Under Relative Performance Criteria Among Heterogeneous Agents](https://mlsanity.com/paper/2402.07365/) (2024)
- [Entrywise error bounds for low-rank approximations of kernel matrices](https://mlsanity.com/paper/2405.14494/) (2024)
- [The Spectral Barycentre of a Set of Graphs with Community Structure](https://mlsanity.com/paper/2502.00038/) (2025)
- [A Spectral Framework for Graph Neural Operators: Convergence Guarantees and Tradeoffs](https://mlsanity.com/paper/2510.20954/) (2025)
- [Global Optimization on Graph-Structured Data via Gaussian Processes with Spectral Representations](https://mlsanity.com/paper/2511.07734/) (2025)
- [On the Oracle Complexity of Interpolation-Based Gradient Descent](https://mlsanity.com/paper/2606.19878/) (2026)
- [Synthetic Nearest Neighbors: Extending Synthetic Controls for Matrix Completion with Missing Not at Random Data](https://mlsanity.com/paper/2609.13586/) (2026)

## Abstract (arXiv)

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(xi,xj), where xi 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ρ=Omega(log 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 log (nρ)/(nρ) for d=1 as α increases. Furthermore, when f is analytic, we show the error rate of USVT is at most logd (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.