# Reconstruction of Line-Embeddings of Graphons

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2020.

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

- [Localization in 1D non-parametric latent space models from pairwise affinities](https://mlsanity.com/paper/2108.03098/) (2021)
- [Detection-Recovery Gap for Planted Dense Cycles](https://mlsanity.com/paper/2302.06737/) (2023)
- [Information-Theoretic Thresholds for Planted Dense Cycles](https://mlsanity.com/paper/2402.00305/) (2024)
- [Estimating the history of a random recursive tree](https://mlsanity.com/paper/2403.09755/) (2024)
- [Active Seriation: Efficient Ordering Recovery with Statistical Guarantees](https://mlsanity.com/paper/2603.15336/) (2026)

## Abstract (arXiv)

Consider a random graph process with n vertices corresponding to points vi ~ Unif[0,1] embedded randomly in the interval, and where edges are inserted between vi, vj independently with probability given by the graphon w(vi,vj) ∈ [0,1]. Following Chuangpishit et al. (2015), we call a graphon w diagonally increasing if, for each x, w(x,y) decreases as y moves away from x. We call a permutation σ ∈ Sn an ordering of these vertices if vσ(i) < vσ(j) for all i < j, and ask: how can we accurately estimate σ from an observed graph? We present a randomized algorithm with output hatσ that, for a large class of graphons, achieves error max1 ≤ i ≤ n | σ(i) - hatσ(i)| = O*(√n) with high probability; we also show that this is the best-possible convergence rate for a large class of algorithms and proof strategies. Under an additional assumption that is satisfied by some popular graphon models, we break this "barrier" at √n and obtain the vastly better rate O*(nε) for any ε > 0. These improved seriation bounds can be combined with previous work to give more efficient and accurate algorithms for related tasks, including: estimating diagonally increasing graphons, and testing whether a graphon is diagonally increasing.