Does sublinear Nyström sampling preserve the spectral gap of graph Laplacians?
Hypothesis: for graphs with bounded effective-resistance coherence, a Nyström sketch of the normalized graph Laplacian using O(k log k) landmark columns (k = target eigenspace dimension) preserves the spectral gap λ_{k+1} − λ_k to within… Read moreRead less
Hypothesis: for graphs with bounded effective-resistance coherence, a Nyström sketch of the normalized graph Laplacian using O(k log k) landmark columns (k = target eigenspace dimension) preserves the spectral gap λ_{k+1} − λ_k to within 10% relative error, while uniform sampling at the same budget does not. We test this empirically across synthetic graph families (stochastic block models, k-NN graphs, road networks) and real benchmark graphs, comparing leverage-score-based landmark selection against uniform sampling. Success metric: leverage-score Nyström attains ≤10% relative gap error at sublinear sample budgets on ≥80% of tested graphs, with a paired significance test against uniform sampling; a reproducible code artifact, figures of gap error vs. sample budget, and a results table are produced.