Skip to content

Structure-Aware Spectral Sparsification via Uniform Edge Sampling

Conference: NEURIPS2025 arXiv: 2510.12669 Code: None Area: Other Keywords: spectral sparsification, uniform sampling, spectral clustering, effective resistance, graph sparsification

TL;DR

This paper proves that on graphs with sufficiently strong clustering structure (structure ratio \(\Upsilon(k)\) large enough), uniform edge sampling suffices to preserve the spectral subspace structure required for spectral clustering, without expensive effective resistance precomputation — providing the first provable guarantee that uniform sampling preserves such structure.

Background & Motivation

Scalability bottleneck of spectral clustering: Spectral clustering requires computing eigenvectors of the graph Laplacian, which is prohibitively expensive on large-scale graphs (millions of nodes and edges).

Classical spectral sparsification: Spielman & Srivastava (2011) proved that sampling \(O(n \log n / \varepsilon^2)\) edges proportional to effective resistance yields an \(\varepsilon\)-spectral sparsifier that preserves all eigenvalues.

High cost of effective resistance computation: Estimating effective resistances requires solving Laplacian linear systems or constructing specialized data structures, whose overhead on large graphs may negate the benefits of sparsification.

Naive attempt with uniform sampling: On general graphs, uniform sampling cannot guarantee spectral properties — nodes with abnormally high degree or weakly connected structures lead to failure.

Special opportunity with clustered data: Recent coreset literature (Braverman et al. 2022, Huang & Vishnoi 2020) shows that under good clustering conditions, uniform sampling already suffices for k-means/k-median. Can analogous ideas apply to spectral graph clustering?

Core problem: Under what conditions does uniform edge sampling — without any preprocessing — suffice to preserve the structure needed for spectral clustering?

Method

Overall Architecture

The paper proceeds as follows: (1) quantify "clusterability" via the graph's clustering structure assumption; (2) derive effective resistance bounds for intra-cluster edges, showing that uniform sampling is sufficiently close to importance sampling; (3) prove spectral approximation of the sampled Laplacian on the leading eigensubspace via the Matrix Chernoff concentration inequality.

Key Designs

Module 1: Structure Ratio and Clusterability Characterization

The central concept is the structure ratio:

\[\Upsilon(k) = \frac{\lambda_{k+1}}{\rho_G(k)}\]

where \(\lambda_{k+1}\) is the \((k+1)\)-th eigenvalue of the normalized Laplacian and \(\rho_G(k)\) is the \(k\)-way expansion constant — the minimum over all \(k\)-partitions of the maximum cluster conductance. Intuitively:

Parameter Large → Meaning Small → Meaning
\(\lambda_{k+1}\) No \((k+1)\)-th cluster exists Finer clustering may exist
\(\rho_G(k)\) Strong inter-cluster connections (poor clustering) Weak inter-cluster connections (good clustering)
\(\Upsilon(k)\) Prominent clustering structure Weak clustering structure

The Structure Theorem (Peng et al.) guarantees that when \(\Upsilon(k)\) is sufficiently large, the subspace spanned by the bottom \(k\) eigenvectors of the Laplacian is close to that spanned by the cluster indicator vectors \(C_1, \ldots, C_k\), with error \(\leq k/\Upsilon(k)\).

Module 2: Rank-\((n-k)\) Effective Resistance Bound

The classical upper bound \(R_{\text{eff}}(u,v) \leq 2/\lambda_2\) is too coarse. This paper introduces the rank-\((n-k)\) effective resistance:

\[R_{\text{eff}}^{n-k}(a,b) = \langle \delta_a - \delta_b, \mathbf{L}_{n-k}^+ (\delta_a - \delta_b) \rangle\]

where \(\mathbf{L}_{n-k}\) retains only the projection onto the \((n-k)\) largest eigenvectors of the Laplacian. Lemma 4.5 proves that for a vertex pair \(\{a, b\}\) within the same cluster:

\[\frac{1}{\kappa}\left(1 - \frac{k}{\Upsilon(k)}\right) \frac{2}{\lambda_{k+1}} \leq R_{\text{eff}}^{n-k}(a,b) \leq \frac{2}{\lambda_{k+1}}\]

where \(\kappa = \lambda_n / \lambda_{k+1}\) is the rank-\((n-k)\) condition number. This shows that in well-clustered graphs, the effective resistance of intra-cluster edges is tightly bounded, with upper and lower bounds differing by only a factor of \(\kappa\) — the key to the feasibility of uniform sampling.

Module 3: Proximity Between Leverage Score and Uniform Distributions

Lemma 4.6 bounds the number of inter-cluster edges: \(|E_{\text{inter}}| \leq \rho_G(k) \cdot |E|\).

Lemma 4.7 gives a relative bound between the leverage score distribution \(p_e\) and the uniform distribution \(p^{\text{unif}}\):

\[\frac{(1 - k/\Upsilon(k))(1 - \rho_G(k))}{\kappa} \cdot p^{\text{unif}} \leq p_e \leq \frac{\kappa}{(1 - k/\Upsilon(k))(1 - \rho_G(k))} \cdot p^{\text{unif}}\]

When \(\Upsilon(k)\) is large and \(\rho_G(k)\) is small, the two distributions differ by only a constant factor — so uniform sampling can substitute for leverage score sampling.

Main Theorems (Theorem 4.3 & 4.8)

Structure preservation under effective resistance sampling (Theorem 4.2): Sampling \(O(n \log n / \varepsilon^2)\) edges by effective resistance, the alignment error between the top-\((n-k)\) eigenspace of the sparse Laplacian and the cluster indicator vectors satisfies:

\[\|\tilde{\mathbf{V}}_{n-k} \tilde{\mathbf{V}}_{n-k}^T \mathbf{C}\|_F^2 \leq \frac{1+\epsilon}{1-\epsilon} \cdot \frac{k}{\Upsilon(k)}\]

Structure preservation under uniform sampling (Theorem 4.3, main result): Uniformly sampling \(O\!\left(\frac{\kappa^2}{(1-k/\Upsilon(k))^2(1-\rho_G(k))^2} \cdot \frac{n \log n}{\varepsilon^2}\right)\) edges likewise satisfies:

\[\|\tilde{\mathbf{V}}_{n-k} \tilde{\mathbf{V}}_{n-k}^T \mathbf{C}\|_F^2 \leq k\left(\frac{1}{\Upsilon(k)} + \frac{\epsilon}{1-\epsilon} \kappa\right)\]

When \(\Upsilon(k) = \Omega(k^2)\) (standard clusterability assumption), the error terms are controlled, and spectral clustering can still recover the correct clustering structure.

Key Experimental Results

Main Results: Uniform Sampling vs. Effective Resistance Sampling on SBM Graphs

Setup: \(k=4\) clusters, 200 nodes per cluster, generated via the Stochastic Block Model (SBM). The error metric is \(\|\sin\Theta(\tilde{V}_k, C)\|_\infty\) — the maximum principal angle between the bottom \(k\) eigenvectors and the true cluster indicator vectors.

Clustering Structure Strong clustering (large \(\Upsilon(k)\)) Weak clustering (small \(\Upsilon(k)\))
Uniform sampling error Comparable to effective resistance sampling, sometimes slightly better Error increases but tracks effective resistance sampling
Effective resistance sampling error Low Low
Key finding Uniform sampling slightly outperforms effective resistance sampling on strongly clustered graphs Uniform sampling remains robust

Hypothesized explanation for uniform sampling's slight advantage in strongly clustered graphs: uniform sampling naturally under-samples inter-cluster edges, thereby enhancing subspace alignment with the cluster indicator vectors.

Ablation Study: Hierarchical SBM and LFR Benchmark Graphs

Hierarchical SBM (4 top-level clusters × 4 sub-clusters = 16 sub-clusters; target: recover top-level structure):

Hierarchy strength \(p_{\text{intra-sub}}\) \(p_{\text{inter-sub}}\) \(p_{\text{inter-top}}\) Uniform sampling performance
Strong 0.50 0.10 0.005 Nearly identical to effective resistance sampling
Medium 0.35 0.08 0.015 Slight degradation, but still effective
Weak 0.20 0.06 0.025 Larger gap, but overall trend consistent

LFR benchmark graphs (800-node networks, varying mixing parameter \(\mu\)):

\(\mu\) value Meaning Uniform vs. Effective Resistance
Small \(\mu\) Strong community structure Almost no difference
Large \(\mu\) Weak community structure Gap increases, but uniform sampling remains practical

All experiments were conducted on a MacBook Pro M1 (16GB RAM), with means and standard deviations reported over 20 runs.

Key Findings

  1. On well-clustered graphs, uniform sampling not only has theoretical guarantees but also performs no worse than effective resistance sampling in practice.
  2. Even under weak clustering, the error trajectory of uniform sampling tracks that of effective resistance sampling — theory is more conservative than practice.
  3. Uniform sampling's tendency to under-sample inter-cluster edges can be beneficial for clustering preservation in certain settings.

Highlights & Insights

  1. High practical value: Completely eliminates effective resistance precomputation, making sparsification preprocessing for spectral clustering extremely simple — only uniformly random edge sampling is required.
  2. Novel theoretical tools: The rank-\((n-k)\) effective resistance concept, tight resistance bounds for intra-cluster edges, and Matrix Chernoff analysis targeting the leading eigensubspace — these tools have independent value for spectral graph theory.
  3. Cross-domain bridge: The idea from coreset theory — that uniform sampling is effective under clustering structure — is introduced into the spectral graph domain, establishing an analogy from k-means to spectral clustering.
  4. Elegant intuition: When a graph has good clustering structure, the "importance" of each edge tends toward uniformity, so uniform sampling is naturally "structure-aware."

Limitations & Future Work

  1. Unweighted graphs only: Theorem 4.3 assumes unweighted graphs; extension to weighted graphs requires new analysis.
  2. Dependence on \(\kappa\): The sampling complexity contains a \(\kappa^2\) factor (rank-\((n-k)\) condition number), which may require more samples for graphs with large condition numbers.
  3. No overlapping clusters: The analysis assumes hard partitions and cannot handle overlapping communities.
  4. Lack of large-scale real-graph experiments: Validation is conducted only on synthetic graphs; real-world social networks, citation networks, etc. are not tested.
  5. Resistance bounds may be loose: The authors acknowledge that while the resistance bounds suffice for the theoretical proof, they may be loose in practice.
Direction Representative Work Relation to This Paper
Spectral sparsification Spielman & Srivastava (2011) Classical method requires effective resistance; this paper proves uniform sampling can substitute
Analysis of well-clustered graphs Peng et al. (2015), Macgregor & Sun (2022) Structure Theorem used as theoretical foundation
Clustering coresets Braverman et al. (2022), Huang & Vishnoi (2020) Analogous idea that uniform sampling is effective on structured data
Effective resistance estimation Peng et al. (2021) Local approximation methods; this paper bypasses resistance computation entirely
Uniform sampling for matrix approximation Cohen et al. (2014) They use uniform sampling to estimate leverage scores but still require importance sampling; this paper proves it is unnecessary
Higher-order Cheeger inequalities Kwok et al. (2013) Provides theoretical foundation for the structure ratio

Rating

  • Novelty: ⭐⭐⭐⭐ — First proof that uniform sampling preserves spectral clustering structure, filling a theoretical gap
  • Experimental Thoroughness: ⭐⭐⭐ — Synthetic graph experiments are thorough but lack validation on real large-scale graphs
  • Writing Quality: ⭐⭐⭐⭐ — Theoretical derivations are clear, with natural transitions from intuition to formalization
  • Value: ⭐⭐⭐⭐ — Solid theoretical contribution with significant practical potential (simplified preprocessing for large-scale graphs)