Consistency of Spectral Seriation

2021/12/08 by Natik, Amine, Smith, Aaron
#Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2112.04408

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 2019]: 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 1998] 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 → ∞.

Related

• Rates of Convergence of Spectral Methods for Graphon Estimation
• Minimax Optimal Probability Matrix Estimation For Graphon With Spectral Decay
• Optimal Rates of Statistical Seriation
• Uncovering a graph
• Uniform linear embeddings of graphons