Reconstruction of Line-Embeddings of Graphons

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.