Research map / Learning theory and algorithms / Clustering

Structure-Aware Spectral Sparsification via Uniform Edge Sampling

NeurIPS 2025 · Learning theory and algorithms › Clustering · approach: Spectral clustering algorithms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that under strong k-cluster structure (large structure ratio Υ(k)), uniform edge sampling of O(κ² n log n/ε²) edges preserves the top (n−k)-eigenspace of the graph Laplacian, so spectral clustering on the sparsifier remains faithful, without effective-resistance importance sampling.

Problem

Spectral clustering does not scale to massive graphs; classical spectral sparsification needs effective-resistance sampling, which is costly to compute. The question is when uniform edge sampling suffices to preserve the spectral structure needed for clustering.

Approach

Uses the structure ratio Υ(k)=λ_{k+1}/ρ_G(k) to show that, for well-clustered graphs, rank-(n−k) effective resistances are nearly uniform, so uniform sampling approximates leverage-score sampling and a matrix Chernoff bound on the dominant eigenspace yields a top-(n−k) spectral sparsifier.

Key results

• Theory: uniformly sampling O(κ² n log n/ε²) edges yields a sparsifier preserving the top (n−k) eigenspace, with a bound ||Ṽ_{n-k}Ṽ_{n-k}^T C||_F² ≤ k(1/Υ(k) + ε/(1−ε)·κ).
• Experiments on SBM graphs (k=4, 200 nodes per cluster, 20 runs): uniform sampling matched or slightly outperformed effective resistance sampling on well-clustered graphs in subspace error.
• Experiments on poorly clustered graphs: uniform sampling followed an error trajectory similar to effective resistance sampling.

Measured effects reported in the paper

Surprising findings

• Uniform sampling slightly outperformed effective resistance sampling on well-clustered graphs in the reported experiments, which the authors hypothesize is due to undersampling cross-cluster edges.
• Even on poorly clustered graphs, uniform sampling showed error trajectories similar to effective resistance sampling.

Limitations

• Theoretical bounds may be loose in practice; sample complexity depends on κ² and on (1−k/Υ)² factors.
• Analysis is restricted to unweighted graphs; weighted or overlapping clusters are left open.
• Experiments are small-scale synthetic graphs with k=4 clusters and only a handful of runs; no real-world datasets.

Experimental setup

Datasets: Stochastic Block Model synthetic graphs Hierarchical Stochastic Block Model synthetic graphs LFR benchmark graphs (800 nodes)

Benchmarks: Stochastic Block Model graphs Hierarchical SBM graphs LFR benchmark graphs

Metrics: largest principal angle between bottom-k eigenvectors and cl

Baselines: Effective resistance sampling

Builds on: Spectral sparsification by effective resistance sampling (Spielman-Srivastava) Structure theorem for well-clustered graphs (Peng et al.) Matrix Chernoff bound Davis-Kahan theorem

Closest papers by meaning

• Pass-Efficient Algorithms for Graph Spectral Clustering (Student Abstract) (AAAI 2024 · similarity 0.91)
• Fully Dynamic Coreset Spectral Clustering (ICML 2026 · similarity 0.90)
• Optimal Graph Clustering without Edge Density Signals (NeurIPS 2025 · similarity 0.90)
• Equivalence between Graph Spectral Clustering and Column Subset Selection (Student Abstract) (AAAI 2024 · similarity 0.89)
• On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models (NeurIPS 2024 · similarity 0.89)
• Signed Laplacians for Constrained Graph Clustering (ICML 2025 · similarity 0.87)