## Background Spectral clustering, diffusion embeddings, and graph signal processing all depend on the leading eigenspace of the (normalized) graph Laplacian L = I − D^{-1/2} A D^{-1/2}. The usable signal is governed by the spectral gap γ_k = λ_{k+1} − λ_k: when a sketch distorts the gap, downstream cluster assignments and embedding stability degrade even if individual eigenvalues look accurate. Nyström approximation is the standard sublinear route (sample m ≪ n landmark columns, reconstruct a rank-m surrogate), but existing guarantees target spectral-norm or trace-norm error of the operator, not the *gap* — and gap fidelity is what practitioners actually need. ## Hypothesis (H1) For graphs whose leading-k eigenspace has bounded effective-resistance coherence, Nyström sketches with m = O(k log k) landmarks chosen by approximate leverage scores preserve γ_k to within 10% relative error with probability ≥ 0.9, whereas uniform landmark sampling at the same budget m…Read more
Read less
## Background Spectral clustering, diffusion embeddings, and graph signal processing all depend on the leading eigenspace of the (normalized) graph Laplacian L = I − D^{-1/2} A D^{-1/2}. The usable signal is governed by the spectral gap γ_k = λ_{k+1} − λ_k: when a sketch distorts the gap, downstream cluster assignments and embedding stability degrade even if individual eigenvalues look accurate. Nyström approximation is the standard sublinear route (sample m ≪ n landmark columns, reconstruct a rank-m surrogate), but existing guarantees target spectral-norm or trace-norm error of the operator, not the *gap* — and gap fidelity is what practitioners actually need. ## Hypothesis (H1) For graphs whose leading-k eigenspace has bounded effective-resistance coherence, Nyström sketches with m = O(k log k) landmarks chosen by approximate leverage scores preserve γ_k to within 10% relative error with probability ≥ 0.9, whereas uniform landmark sampling at the same budget m fails this bound on graphs with heterogeneous degree/coherence profiles (H0: no separation between the two samplers at equal budget). ## Plan 1. **Theory review + positioning**: survey Nyström spectral guarantees (Gittens & Mahoney; Musco & Musco RLS sampling; Tropp matrix concentration) and derive/adapt a gap-preservation statement from eigenvalue perturbation bounds (Weyl + Davis–Kahan applied to the sketch residual). 2. **Synthetic experiments**: stochastic block models (varying block imbalance and conductance), k-NN graphs on manifold samples, and power-law (Barabási–Albert) graphs, n in [2k, 50k]; sweep landmark budget m and measure relative gap error, eigenspace alignment (principal angles), and downstream spectral-clustering ARI. 3. **Real graphs**: a small set of standard benchmark graphs (e.g., Cora/Citeseer graph structure, a road network, an email/social graph) at sublinear budgets. 4. **Comparison**: uniform vs. approximate-leverage-score landmark selection at matched budgets, ≥20 random seeds each, paired Wilcoxon test on per-graph gap errors. 5. **Analysis + paper**: characterize when uniform sampling matches leverage scores (homogeneous coherence) and when it fails; produce the final paper with theory section, experiment section, figures (gap error vs. budget curves per graph family) and a summary table. ## Evaluation / success criteria - Primary: leverage-score Nyström reaches ≤10% relative gap error using m ≤ C·k log k landmarks (C ≤ 8) on ≥80% of tested graphs; uniform sampling at the same m exceeds 10% error on the heterogeneous families with p < 0.05 (paired test). - Secondary: principal-angle alignment of the recovered k-eigenspace ≤ 15°, and spectral-clustering ARI within 0.05 of the exact-eigensolver baseline. - Negative results are acceptable and publishable: if uniform sampling matches leverage scores everywhere, report the refutation with the coherence profiles that explain it. ## Constraints - Pure CPU workload; graphs up to ~50k nodes; sparse linear algebra only (scipy.sparse / LOBPCG or Lanczos); total compute budget well within a single-node run. - All datasets must be synthetic or standard public benchmarks; no scraping, no credentials. ## Expected artifacts - **Paper**: full write-up (background, gap-perturbation bound, experiments, discussion). - **Code**: reproducible Python package (graph generators, samplers, sketch + eigensolver pipeline, experiment driver, seeds pinned). - **Image**: gap-error vs. sample-budget figures per graph family (log-scale budget axis). - **Table**: summary table of relative gap error and ARI per graph × sampler × budget.