Consistency of spectral seriation

¹ Département de Mathématiques et Statistiques Université de Montréal Mila - Quebec Artificial Intelligence Institute 6666 St Urbain St, Montreal, Canada
² Department of Mathematics and Statistics University of Ottawa 585 King Edward Ave, Ottawa, Canada
³ Tutte Institute for Mathematics and Computing, Ottawa, Canada

^* Corresponding author: This email address is being protected from spambots. You need JavaScript enabled to view it.

Received: 21 July 2025
Accepted: 24 December 2025

Abstract

Consider a random graph G of size N constructed according to a graphon w : [0, 1]² ↦ [0, 1] as follows. First embed N vertices V = {v₁, v₂,…, v_N} into the interval [0, 1], then for each i < j add an edge between v_i, v_j with probability w(v_i, v_j). Given only the adjacency matrix of the graph, we might expect to be able to approximately reconstruct the permutation σ for which v_σ(1) < … < v_σ(N) if w satisfies the following linear embedding property introduced in [Janssen et al. Electron. J. Statist. 16 (2022) doi:10.1214/21-EJS1940]: for each x, w(x, y) decreases as y moves away from x. For a large and non-parametric family of graphons, we show that (i) the popular spectral seriation algorithm [Atkins et al., SIAM J. Comput. 28 (1998) 297–310] provides a consistent estimator σ̂ of σ, and (ii) a small amount of post-processing results in an estimate σ̃ that converges to σ at a nearly-optimal rate, both as N → ∞.