Structure-Aware Spectral Sparsification via Uniform Edge Sampling
Authors: Kaiwen He
Petros Drineas
Rajiv Khanna
Venue: NeurIPS 2025 poster ()
Keywords: Spectral Clustering
Graph Sparsification
Primary area: theory
TL;DR: For Spectral Clustering, Uniform Sampling on the edges works.

Abstract: Spectral clustering is a fundamental method for graph partitioning, but its reliance on eigenvector computation limits scalability to massive graphs. Classical sparsification methods preserve spectral properties by sampling edges proportionally to their effective resistances, but require expensive preprocessing to estimate these resistances. We study whether uniform edge sampling—a simple, structure-agnostic strategy—can suffice for spectral clustering. Our main result shows that for graphs admitting a well-separated $k$-clustering, characterized by a large structure ratio $\Upsilon(k) = \lambda_{k+1} / \rho_G(k)$, uniform sampling preserves the spectral subspace used for clustering. Specifically, we prove that uniformly sampling $O(\gamma^2 n \log n / \varepsilon^2)$ edges, where $\gamma$ is the Laplacian condition number, yields a sparsifier whose top $(n-k)$-dimensional eigenspace is approximately orthogonal to the cluster indicators. This ensures that the spectral embedding remains faithful, and clustering quality is preserved. Our analysis introduces new resistance bounds for intra-cluster edges, a rank-$(n-k)$ effective resistance formulation, and a matrix Chernoff bound adapted to the dominant eigenspace. These tools allow us to bypass importance sampling entirely. Conceptually, our result connects recent coreset-based clustering theory to spectral sparsification, showing that under strong clusterability, even uniform sampling is structure-aware. This provides the first provable guarantee that uniform edge sampling suffices for structure-preserving spectral clustering.

Structure-Aware Spectral Sparsification via Uniform Edge Sampling
Kaiwen He Department of Computer Science
Petros Drineas
Department of Computer Science
Purdue University he he788@purdue. edu
Purdue University
pdrineas@purdue. edu
Rajiv Khanna
Department of Computer Science
Purdue University
rajivak@purdue. edu
Abstract
Spectral clustering fundamental method for graph partitioning, but its reliance on cigenvector computation limits scalability to massive graphs. Classical sparsifi- cation methods preserve spectral properties by sampling edges proportionally their effective resistances, but require expensive preprocessing to estimate these re- sistances. We study whether uniform edge sampling a simple, aggnstie strategy- can suffice for spectral clustering. Our main result shows that for graphs admitting a well-separated k-clustering, characterized by a large structure ratio Y (kk 1 uniform sampling preserves the spectral subspace used for clustering. Specifically, we prove that uniformly sampling O(72n log n/=²) edges, where is the Laplacian condition number, yields a sparsifier whose top (n k)) dimensional eigenspace is approximately orthogonal to the cluster indicators. This ensures that the spectral embedding remains faithful, and clustering quality is preserved. Our analysis introduces new resistance bounds for intra-cluster edges, a rank-(n k) effective resistance formulation, and matrix Chernoff bound adapted to the dominant eigenspace. These tools allow us to bypass importance sampling entirely. Conceptually, result connects recent coreset-based clustering theory to spectral sparsification, showing that under strong clusterability, even uniform sampling structure-aware. This provides the first provable guarantee that uniform edge sampling suffices for structure-preserving spectral clustering.
Introduction
Spectral clustering a fundamental approach for discovering community structure in graphs, with applications such image segmentation (18). The technique embeds nodes into low-dimensional space using the eigenvectors of the graph Laplacian, after which standard clustering algorithms (e.g. k-means) can be applied to identify latent groups. However, real-world graphs grow increasingly large-often with millions of nodes and edges- computin even a handful of eigenvectors of the Laplacian becomes computationally prohibitive. This scalability challenge has spurred interest in spectral graph sparsification, which aims to drastically reduce the number of edges while preserving the graph's 's key spectral (and hence clustering) properties.
Classical results in spectral sparsification show that it is possible to approximate a graph by sampling edges with probabilities proportional to their effective resistances, yielding high-quality spectral sparsifiers that preserve every eigenvalue up to a (1 E) factor [9] Unfortunately, estimating these
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

effective resistances is itself expensive in practice, as it typically requires solving large Laplacian linear systems or constructing specialized data structures (so-called resistance "sketches") for the graph. This overhead can negate the computational gains of sparsification, especially for large graphs. So it natural to ask whether simpler sampling methods can succeed. Specifically:
When can uniform edge needed for spectral clustering?
without any heavy rreprocesiing-sufiie to preserve the structure
Intuitively, there are coherent clusters in the data, and we want our sampling design to focus on preserving this structure, then standard samplers (e.g. based effective resistances) for approxi- mating the entire graph would be an overkill. Looking at the extreme case, if there are disconnected but coherent clusters in the data, surely uniform sampling will suffice in preserving the clustering structure. Relaxing this corner case, in presence of "strong enough' well-separated cluster structure, with sufficiently more intracluster edges than intercluster edges, simple uniform sampling may still suffice. Our focus is to use spectral properties of the graph to identify sufficient conditions for a strong enough k-cluster structure allow uniform sampling for sparsification without compromising the said structure. We formalize this through the structure ratio (Ak
pa[kj where A is the (k + 1) eigenvalue of the normalized Laplacian and Pc: (k) is the k-way expansion (conductance) constant of the graph (i.e. the minimum over all k-partitionings of the maximum cluster conductance).
A
Our main result shows that in graphs with large ((k), fraction of uniformly sampled edges suffices to preserve the pertinent spectral structure for clustering:
Theorem 1.1. (Informal restatement of Theorem 4.3y For a graph with n vertices, by subsampling m O C-n C-nlog log ) edges uniformly at random we obtain a sparsified graph whose top n k eigenspace remains approximately orthogonal to the original cluster indicators:
V Vn- c I S ( ((T)))
1-c²) )=)
T(K))
Here, C and и are constants depending on structural and spectral properties of the graph. In the presence of coherent clusters in the graph, T(k) is large. For example, under well-clusterability assumption of 177. T(k)= (2(k2). Consequently, the bottom-k: spectral embedding of the subsam- pled graph continues to preserve the cluster structure, even though edges were sampled uniformly without any structural information. As a result, spectral clustering applied to the sparsified Laplacian continues to succeed, inheriting the corresponding guarantees of the original graph.
This finding has both practical and theoretical implications. On the practical side, it justifies simple and scalable preprocessing step for spectral clustering: one can simply sparsify the graph by uniform sampling, without complex computations, and still reliably recover clusters. By eliminating the need for computing leverage scores or resistances, our approach enables spectral clustering to scale to previously infeasible graph sizes with minimal overhead. On the theoretical side, our results contribute to the emerging understanding of how structural assumptions can yield beyond-worst-cass guarantees. In particular, it complements recent advances in the coreset and data reduction literature, which show that under clusterability conditions, even uniform random sampling can produce excellent summaries for clustering problems [4] [4]. Here we provide an analogous message for spectral graph clustering: when a graph is inherently well well-clusterable, random uniform sampling of edges is powerful enough to preserve its cluster structure.
Technical Contributions We present a structure-aware analysis of spectral clustering under uniform edge sampling. Our key insight is that in graphs with well-separated clusters (characterized by large structure ratio (k)). the cigenvectors associated with those clusters are robust to random edge removals. In what follows, we highlight three main contributions of this work:
Structure-aware sparsification guarantee. We prove that uniform sampling can produce a spectral sparsifier that preserves cluster structure under standard clusterability assumptions. In particular, we show that if T(k) is sufficiently large, sampling m On log n n/=)) edges uniformly at random is enough to ensure that the relevant spectral subspace for clustering is approximately preserved. Intuitively, our main theorem (Theorem 4.3) guarantees that the sampled graph Laplacian has its top (n k) dimeesioona eigenspace nearly orthogonal to the original k-dimensional cluster indicator subspace. Equivalently, the cluster indicator vectors remain (up to a small error) in the span of the bottom & eigenvectors of the sparsified Laplacian. This result is notable because it achieves form of

---

preetering spectral sparsification without any adaptive weighting, purely through uniform edge selection.
Resistance bounds for intra-cluster structure. To analyze uniform sampling, we derive new bounds on the effective resistances of edges in clustered graphs. We show that within well-defined clusters, every edge has limited spectral influence. Specifically, leveraging the effective condition number and the cluster expansion constant (k),,, we bound the contribution of any intra-cluster edge the top (n - k) eigen-spectrum of the Laplacian. Symmetrically, we also bound the spectral effect of inter-cluster edges. These results quantify how strong cluster structure (large T [(k) constrains the 'spectral mass' of edges, and they are crucial in showing that importance anawaae uniform sampling (which does not distinguish between edges) can still preferentially preserve important connections. Notably, these resistance- based bounds are new and may be of independent interest for understanding spectral properties of clustered graphs.
Eigenspace matrix Chernoff analysis. Our analysis introduces a matrix Chernoff concentration argument tailored the top-(n-k) eigenvector subspace. After sampling edges uniformly, we study the deviation of the sparsified Laplacian from the original Laplacian on the subspace orthogonal to the cluster indicators. By adapting matrix Chernoff bounds to this specific subspace (rather than the entire space), we prove that the sparsifier's Laplacian remains well-behaver (i.e. within a (1 + e) factor of the original) on all vectors that are orthogonal to the cluster indicator vectors. This step is key to translating our resistance bounds into a global spectral guarantee.
2 Related Work
Clusterable Graphs and Spectral Clustering. Our work is motivated by the setting of well-clustered graphs, where the graph contains pronounced k-cluster structure. A convenient way to quantify clusterability is via the structure ratio (k) proposed by Peng et al. [7]. They proved a Structure Theorem for such graphs: if T(k) ?(k2) (or stronger bounds in subsequent refinements), then the subspace spanned by the bottom Laplacian eigenvectors is close to the subspace spanned by the l cluster indicator vectors. Macgregor and Sun [15) showed that one can guarantee spectral clustering's 's success under much weaker assumptions on (k) that do not scale exorbitantly with k. Beyond these spectral analysis results, there have been complementary advances in testing and detecting cluster structure. For example, Czumaj et al. [8] design property testers for cluster structure in counded-degre graphs, assuming that the graph can be partitioned into well-connected clusters with low conductance cut between clusters.
Spectral Graph Sparsification. A series of foundational works has established that any graph can be approximated by sparse subgraph spectral sense, In their seminal result, Spielman [19] introduced an algorithm to produce an e-spectral sparsifier with O(n logn/ edges by sampling edges with probabilities proportional to their effective resistances. These sparsification methods, while powerful, rely non-uniform edge sampling schemes to skew the sample toward "important" edges. In subsequent work, Batson et al. [2) proved the existence of linear-sized spectral sparsifiers (with (n/e)) edges) using deterministic constructive method. In general graphs, uniform random sampling of edges without such weights can fail to preserve spectral properties unless the sample size is prohibitively large (e.g., on adversarial graphs with high-degree vertices or weak connectivity structure) Recent matrix approximation results formalize this limitation: for instance, Cohen al. 7 study uniform sampling for matrix approximation and show that uniform row sampling can produce effective approximations for certain matrix classes. Critically, their framework uses uniform sampling as an intermediate step to estimate leverage scores, which then used for subsequent importance sampling to construct the final approximation Their two-stage approach improves the efficiency of computing importance sampling distributions but fundamentally still relies on resistance-basee sampling for final spectral preservation. Our work differs in showing that under structural assumptions (large T(k)), uniform sampling alone suffices for preserving the spectral subspace relevant to clustering, without any refinement or resistance estimation step. While their work demonstrates that uniform sampling can be useful computational tool within importance sampling frameworks, our contribution identifies specific graph structures where the importance sampling phase can be eliminated entirely. There have been alternative methods that aim to compute sparsifies that avoid Laplacian graph solvers entirely: Kapralov and Panigrahy [1I obtain a spectral sparsifier by taking a union of random graph spanners. However, their scheme require non trivial algorithm for computing importance probabilities over the edges. Peng et al. [16] develop local
impor
3

---

appoximation algorithms that estimate effective resistance by exploring only small portion of the graph, via random walks, achieving Oppoly n/e) with additive e error for graphs with bounded mixing time.
Uniform Sampling for Clustering Coresets. Classical clustering coresets (e.g.. for k-means or k-median) typically rely on importance sampling, but recent work shows that when the data is well- structured, uniform sampling can yield equally effective-and much simpler-coresets Braverman et al. 4 present a meta-theorem for constructing clustering coresets via uniform sampling; they obtain the first coresets for many constrained clustering problems (such as capacitated or fair clustering) using uniform sampling instead of sensitivity sampling. However, the technical problem and solution are fundamentally different: Braverman et al. [4] sample data points in metric spaces for distance-based clustering objectives, using VC-dimension theory and cluster-balance parameters, while our paper aims to sample graph edges for spectral sparsification, requiring novel (o--k)-fffectivv resistances and matrix concentration bounds to preserve Laplacian eigenspaces for the spectral clustering objective. Focusing on the unconstrained k-median objective, Huang and Vishnoi [10] investigate the role of balanced clusters. They define a balancedness parameter 3 E (0, 1] measuring how evenly the points are distributed among optimal clusters. When / is not too small (no cluster is overwhelmingly large or tiny), uniform sample of only poly(k, 1/3, 1/e) points yields (1 + >aappooxinaiionn for k-median, nearly matching the information-theoretie lower bound on sample complexity. In contrast, without assuming balance (3 close to 1), any coreset construction must effectively inspect (11/3) points in the worst case. Our work is complementary to this line of research: while Braverman et al. and Huang- Vishnoi sample data points in metric spaces for clustering objectives like k-means/k- median, we sample graph edges for spectral graph clustering. The mathematical frameworks differ fundamentally: their work relies on metric space geometry and sensitivity analysis, while ours operates in the spectral graph domain using Laplacian eigenspaces and matrix perturbation theory. These results mirror our theme: uniform sampling performs as well as sophisticated importance sampling when each cluster or component of the data is well-conditioned (e.g. size-balanced or with limited "leverage"). Our contribution can be seen as an analogous statement in the graph setting: if the graph's 's clusters are sufficiently well-separated (large Tlk) gap), then each edge is roughly equally "important" and hence uniform edge sampling preserves the spectral clustering structure.
3 Background
Let G = (V, (V,E) E) be an undirected graph where V represents the set of vertices and E the set of edges. For weighted graphs. we denote the weight of an edge between vertices u and as w(fu, v)). The adjacency matrix A of graph G has entries A, representing the weight of the edge between vertices i and j (or for unweighted graphs if an edge exists, 0 otherwise). The degree matrix 1 is a diagonal matrix where D;; = E, Ai represents the sum of weights of all edges incident to vertex i. For any subset S C V, define vol(S) Eies Dü as the volume of S, representing the total weight of edges incident to vertices in S. The standard graph Laplacian is defined as L = D - A. The normalized I Laplacian is given by L = D-1/2AD AD-1//111// 1/2, where is the identity matrix. Both matrices are positive semidefinite with eigenvalues ordered as 0 = a S d2 S ... S \lp for connected graphs. For any vector x E RIVI, the Laplacian quadratic form gives:
T Lx x
Σ {u,o)EE
w(fu, (x(( - =z(o))
This form reveals the connection between the Laplacian and the cut structure of the graph: it sums the weighted squared difference across each edge, so x. La is small if is nearly constant on connected components (e.g. indicator vectors of clusters). The Laplacian can be factorized as
= E(Oo,)E w((a, ()) = B"W B where B E IR [ the edge-incidence matrix and W a diagonal matrix of edge weights. The normalized Laplacian is defined as L I-D AD- 1/2 Both L and L are positive semidefinite (PSD) matrices. We label their eigenvalues as 0 = A < A22 <
Az
Graph Conductance and Expansion Constant. For a subset S C V, the conductance (or Cheeger ratio) is defined as:
EESS V (S)
de (S)
vol(S)
4

---

where [ESS V S) represents the sum of weights of edges connecting S to its complement, and (S) the number of edges in S. This ratio small when has very few edges leaving compared to the sum of degrees inside S. The conductance of the graph is:
min ((G) Sval)/)) $G(S)
small (G)) indicates that the graph has well-defined 'bottleneck' of few edges separating the graph into two clusters. Cheeger's ' inequality establishes a fundamental relationship between conductance and the second eigenvalue of the normalized Laplacian: 2
A - ((G) S /222. This tells
us that the second eigenvalue is small iff the graph contains sparse cut. For multi-way clustering, this is generalized as:
PG(k) = min max (oc(.))). : St.....s
GGG) is small when we can partition the graph into k clusters each having few inter-cluster edges. Higher-order Cheeger-type inequalities [12] extend the two-cluster case the k-th eigenvalue, providing guarantees for k-way spectral partitioning: y pG I C' V log K, where C and C" are constants. A convenient way to quantify how well-separated l clusters are is the structure ratio (k: defined as
AR+1 (k)
T(k)
This ratio compares the + 1)-th eigenvalue (which increases when there is no "(k: + 1)-st cluster") against the k-cluster expansion Pa (which decreases when clusters are better insulated). Intuitively, large T(k) means the first & eigenvalues .g..... A are very small (signifying k good elusters), but AR+1 jumps much higher (no (k + 1)-th cluster), so the clustering structure is pronounced.
Spectral Clustering. The Spectral clustering algorithm partitions the graph by computing the bottom eigenvectors of the normalized Laplacian and using them to embed each vertex into RR The resulting matrix F, whose i-th represents the embedding of vertex is then clustered using an algorithm like k-means. When the graph has a clear k-cluster structure (large (k)),, theory guarantees that these embedded points (the of F) cluster tightly around k: distinct centers corresponding to the true communities.
Spectral Sparsification. Spectral sparsification of graph aims to reduce the number of edges in graph while preserving its essential structural properties. A spectral sparsifier is subgraph C(V, É) of G(V, E) with reweighted edges that approximates the quadratic form of the Laplacian for all vectors. Specifically, & an e-spectral sparsifier of G if:
(1- Lo S S (1 +)xx La, Va RM
where L and L are the Laplacians of G and G. respectively. Preserving the spectrum in this way also preserves the results of spectral clustering: in particular, the important bottom-k eigenspace will have a close counterpart L.
Effectivv Resistance. The effective resistance Rar(e) of an edge e = (u. v) measures the importance of edge in the graph's 's connectivity structure. When viewing the graph as an electrical network with edges as resistors, the effective resistance between vertices u and v is:
Rur v) = (ō. - L 5.)
where I is the pseudoinverse of the Laplacian and o, defined the standard basis vector with value 1 at index x and 0 elsewhere. The leverage score т. of an edge e = (u, v) with weight w. is defined Te w. (e
4 Results
In the context of graph clustering, is crucial to understand how the eigenvectors of the Laplacian relate to the underlying cluster structure. For graphs that are well-clustered, the subspace spanned
5

---

by the bottom & cigenvectors aligns closely with the optimal cluster indicator matrix. This is demonstrated in the following theorem.
Theorem 4.1 (Structure Theorem I7). Let [CI....,CC, be a k-way partition of achieving pk()), and let (kk) = PG+1/PG(k)), Assume that {vili= are the first bottom eigenvectors of ma- trix L, and Ci...., C₁ E R" are the cluster indicator vectors of {Cr)i=1 with proper normalization (i.e. V(ci) Then, the following statements hold:
1. For each cluster C₁ there exists linear combination of the eigenvectors VI:... Vg- V Σ a,v; such that ||c. - vvll? S T(K)
2. For each eigenvector vi, there exists a linear combination of the cluster indicator vectors,
è ; دーー1 3ycj such that Σ || -2,1
&
T(R)
For completeness, we also provide their proof in Section A.I
4.1 Spectral Sparsification for Well-Clustered Graphs
As our first result, we extend the structure theorem study how the alignment of the cluster indicator vectors and the bottom eigenvectors of the Laplacian is preserved under sparsification. Intuitively, when the vertices well-clusterable, we would expect the Laplacian matrix to be decomposable as == L+ E, where L is block diagonal representing optimal intracluster edge weights, and E is small error matrix of intercluster edge weights. If graph is well-clusterable, this error matrix should have a very small norm. Using Davis-Kahan (Theorem B.2). the eigenvectors of L, which correspond precisely to the cluster indicator vectors, and the eigenvectors of L should be close together. We first explore sparsification through effective resistances which are known to be able to approximate the underlying graph well [19].
Theorem 4.2 (Sparsification with Structure Preservation). Let G = (V, E) be a graph with normal- ized Laplacian matrix that satisfies Theorem 4. If we sample O n logn edges proportional to their effective resistance to construct sparsified Laplacian L, then:
1 ++ kpa(k) I-e Au+1
V
S
where Vn- is defined as the matrix top n eigenvectors if..
This result expectedly follows from the e-approximation of the graph, which preserves the entire spectral information of the graph up to error. This theorem immediately suggests that for clustering, it is possible to sparsify the graph via effective resistance sampling while preserving the useful information of the alignment between the bottom eigenvectors and the cluster indicator vectors.
Interestingly and perhaps a bit surprisingly, for well-clustered graphs, sampling uniformly at random instead of costly effective resistance sampling also preserves the alignment of cluster indicator vectors and the bottom l eigenspace, hinting that sparsification by sampling edges uniformly at random preserves clusterability of the graph.
Theorem 4.3. ([Main result] Sparsification via Uniform Sampling with Structure Preservation) Let G (V, E) be unweighted graph with Laplacian matrix L that satisfies Theorem 4.1 Additionally, suppose there exists clusters (C1,.., Ck. with k-way cut value pG(k). Let Am
be the rank
Nais
k condition number, and let T T(k)= pa(k)
Aeta be the clusterability constant. If we uniformly sample
0 (1-K/T(R))(1--a0 Laplacian L, that satisfies
log log(n)/ edges with proper reweighting. we obtain sparsified
I VT VV
(1)
T(k)
where Vn-k is defined the matrix of ks eigenvectors of L.

---

Theorem 4.3
ensures practical structural guarantee it implies that for well-clustered graphs sparsification by uniform sampling still retains approximate alignment of the bottom eigenvectors with the cluster indicator vectors, and so the spectral clustering algorithm when applied to the sparsified Laplacian will recover the underlying clusters.
Proof idea: To prove this claim, we now develop a detailed analysis that connects structural properties of well-clustered graphs spectral stability under uniform sampling. Specifically, we derive new bounds on rank-(n - k) effective resistances in Section 4.2 quantify the distributional proximity between leverage score sampling and uniform sampling, and apply a matrix Chernoff argument tailored to the dominant eigenspace. These efforts culminate in Theorem 4.8 which formally proves that uniform sampling preserves spectral approximation of the top-(n-K) eigenspace of the Laplacian. Finally, we utilize the preservation of the top- (n - k) eigenspace to show that the projection matrices between the original and sparsified Laplacians are close. This results in an additive bound on the squared Frobenius norm of the alignment between the bottom & eigenspace of the sparsified graph. The detailed proof is in the appendix.
4.2 Bounding effective resistances
To justify the effectiveness of uniform edge sampling, we must understand how much spectral influence individual edges exert specifically, through their effective resistances. While classical upper bounds depend only global spectral properties, they fail to exploit the underlying cluster structure. In this section, we derive new resistance bounds tailored to well-clustered graphs, showing that most intra-cluster edges have uniformly low spectral impact when T(k) is large.
Define 5n E I to be a vector that is at index u and 0 everywhere else. Given an edge {a. E, the effective resistance is defined as (6g - 8g, L (6. 66)). For L VV²VT, the effective resistance can be expressed and bounded in terms of the second eigenvalue:
(5n- 1 8,, It L+(5,, (6.m - -5,) Σ (5a
22
1 _ o
60) uo (5. - -56) (Uia Uz))2
2
A2
This bound is quite weak in that it only leverages information regarding the second eigenvalue. Chandra et al. (5) showed that this global bound is tight (5), but there are other more fine-grained bounds under reasonable assumptions (e-g. under a bounded expansion 3) For our analysis, we must go beyond worst-case bounds too and examine how edge resistances behave under structural assumptions of well-clusterabilityy We begin by introducing a rank-(n k) formulation of effective resistance that is more aligned with the subspace relevant to spectral clustering.
4.2.1 Bound on Rank n-k Effective Resistance
Prior work on spectral sparsification often relies on effective resistance as an importance score for edge sampling. However, in clustering applications, this heuristic can be misaligned: inter-cluster edges typically have high resistance, increasing their sampling probability edges we hope to downweight or ignore. In contrast, uniform sampling treats all edges equally, and our goal is to show that it naturally favors preserving intra-cluster structure well-clustered graphs. To formalize this, we focus not preserving the entire Laplacian spectrum, but specifically the top (n - k)) eigenspace, which captures finer intra-cluster variation. We introduce the notion of rank (n k) effective resistance, tailored to this subspace, and show that for well-separated clusters, the resistance of intra-cluster edges is uniformly small. This will allow us to argue that even uniform sampling suffices to preserve the dominant spectral structure relevant clustering.
being the very
Definition 4.4 (Rank k Effective Resistance), Given graph G EV, Le VEVT be the unnormalized Laplacian. Let Ln-k := Σ" Σm A.v.v." The Rank (n - k) effective resistance between vertices a, E V is defined as the following
R=-k(a,b)
(a,b) == (6.
Sr. L (6. -86)
In the seminal paper by Chandra et al.
(5] they have the following bounds for effective resistance:
2
X2 > Run(u, v) 2 Xa2
7

---

However, for our applications this lower bound is extremely weak as it scales based on the number of vertices. In the following lemma, we show a lower bound on the effective resistance that is purely based on clusterability and the "rank n-k condition number" of the graph.
Lemma 4.5. Let (Ci,..,,Ca be a partition of G achieving pG(k), and let ((k)
Let BBT be the laplacian of the graph and let An. Then for any pairs of vertices {a, b)
Aets
within a cluster, the rank (n k) effective resistance is bounded by
2 2 R (a, "
1 -
k 2 T(k)
A6+1
AR+1
Lemma 4.5 provides an improved structure-aware lower bound on the rank-(n- effective resistance of intra-cluster edges. It shows that in graphs with large structure ratio T(k) with high connectedness (large k), these resistances are tightly bounded, reinforcing the intuition that uniform sampling predominantly selects low-resistance edges and thus implicitly preserves intra-cluster connectivity essential for spectral clustering.
To quantify how close leverage score sampling is to uniform sampling, we next bound the number of inter-cluster edges. In well-clustered graphs, it is natural expect that the fraction of inter-cluster edges is small relative to the total number of edges. This structural property will us to compare the leverage distribution the uniform distribution in the analysis that follows.
Lemma 4.6 (Intercluster Edges). Let {CI....,CC be a clustering of G = (V, F) that satisfies pa(k) minc......C. C. max k (go((C))) (C.)). Then the number of inter cluster edges is bounded by
|inttel S Pc(k)
|E]
4.3 Matrix Chernoff Proof of Top-(n- k) Approximation
Having established that intra-cluster edges have bounded rank-(n-k)) effective resistance (Lemma 4.5 and that inter-cluster edges are proportionally few (Lemma we now analyze how these structural properties translate into spectral guarantees for uniform sampling. Our goal in this section is to show that the Laplacian of uniformly sampled subgraph approximates the original Laplacian well on the top-(n - k) eigenspace. To do this, we first show that under clusterability assumptions, the leverage score distribution is 'close enough' uniform to allow concentration.
We first start with notation. Let == (e) be the rank k effective resistance for edge the associated probability distribution based on the effective resistances.
e E Let Pa = EeegTo To
To
Let unif = 1/| 1/m the uniform distribution.
Lemma 4.7. Les {C1, C& be a partition of G achieving Pa(k), and let T(k) - K Auti Then we have the following relative upper bound on the leverage score probability distribution
(1 -1 kk))(()) * pc((k) .pmit S Pc 5 k/T(k)()))))))))))))))><)<)))k -po(k))))))))))))))))))()))))- uni
for all edges E.
Lemma 4.7 enables us to treat uniform sampling as an approximate surrogate for leverage score sampling in the structured setting. With this in place, we now apply matrix Chernoff bound to show that the Laplacian of a uniformly sampled subgraph preserves the spectral structure of the original Laplacian the top-(n- k) eigenspace, leading to main result:
Theorem 4.8 (Chernoff via Uniform Sampling). Consider a graph G = (V, E) with laplacian Ak+1 Let
=V,
matrix L E R Suppose that there exists clusters {CI...., Ck} that satisfies T T(k)
Pa(k)
Xe+i be the restricted rank n - k condition number of L
Let LH be the Laplacian of a sparsified graph where we sample edges uniformly. Then by uniformly
sampling O (I==A/10) nllo(n))/e?) edges, we can guarantee
(1 c)x Lx S x LHI x S ()x Lx
for all x E span (k.,,,... Un). other words, we obtain a spectral sparsifier for the dominant n of the original Laplacian.
8

---

5 Experiments
We empirically validate our theoretical results by comparing uniform edge sampling against effective resistance sampling on synthetic graphs generated by a Stochastic Block Model []]. We focus on graphs with k 4 clusters with 200 nodes per cluster. To measure the error, we compute the bottom k = 4 eigenvectors of the sparsified graph, and we measure the largest principal angle between the bottom 4 eigenvectors with the true cluster indicator vectors (ie || sin ( I) Smaller angles indicate better preservation of the cluster structure in the spectral embedding. We evaluate both sampling strategies in two settings.
Well Clustered Graphs: Graphs are generated with large intra-edge inter-edge probability ratio. The probabilities were chosen to highlight uniform edge sampling for low ry values (strong clustering structure).
Weakly Clustered Graphs: Graphs are generated with small intra-edge to inter-edge probability ratio. These ratios corresponds to large y values (bad clustering structure).
Serving
312
112
110
Eu
3.
115
870
Figure 1: Good Clusters: Error plots comparison between Uniform Sampling and Effective Resis- tance Sampling of strong clusters with varying values of y. Shaded region denotes sd over 20 runs.
Quredoo
To.
Figure 2: Poor Clusters: Error plots comparison between Uniform Sampling and Effective Resistance Sampling of bad clusters with varying values of y. Shaded region denotes 1 sd over 20 runs
For the experiments, the effective resistances were computed via computing the pseudoinverse of the unnormalized Laplacian. All experiments Experiments on the well-clustered graphs confirm the effectiveness of uniform sampling in terms of preserving the bottom-k eigenspace. Surprisingly, even in the poorly-clustere sampling still followed an error trajectory similar to that of effective resistance sampling. Emperically, it is interesting see that on the well clustered graphs, uniform sampling actually performs slightly better than effective resistance sampling. We hypothesize that this is due to uniform sampling being biased towards undersampling cross cluster edges. which results in stronger subspace alignment with the cluster membership vectors. We leave further investigation of this phenomena to future work.
a Macbook Pro MI with 16GB of RAM.
setting, uniform
5.1 Hierarchical Stochastic Block Model
Experiments are done similarly for hierarchical stochastic block model. We fix the number of top clusters and sub clusters to be 4 for a total of 16 clusters with the goal of approximating the subspace structure of the top clusters. To test the strength of uniform sampling versus effective resistance sampling, we adjust the probability of a connection between nodes within the same sub cluster (Pimta-sub), between nodes of different sub clusters (Pinter and between nodes of different top clusters (Pinee-top).
Strong Hierarchical Structure: Pintra-sub 0.5, Pinter-sub 0.10, Pinter-top = 0.005
Moderate Hierarchical Structure: Pintra-sub 0.35, Pinter-sub 0.08, Pinter-top 0.015

---

Weak Hierarchical Structure: Pintra-sub 0.20, Pinter-sub 0.06, Pinter-top = 0.025
Hiararchical Clusters: Top Level, Sub-Clusters Each
Strog setperiieeeeeattte 15.8 190
Wiek Hevoo Tr
2.3
Ne ucgas
of udges hppt
of odges hapt
Figure 3: Hierarchical Clusters: Error plots comparison between Uniform Sampling and Effective Resistance Sampling of strong clusters with varying values of y. Shaded region denotes sd over 20 runs.
5.2 Lannichineti--orttttto---ee
Benchmark Graphs
We perform experiments based on the network benchmark graphs by 133. Experiments are performed for network of 800 nodes. The mixing parameter μ determines the fraction of edges connecting to others communities, which we vary to generate strong versus weak community structure.
110110
pi 3.30
Figure 4: LFR Network Clusters: Error plots comparison between Uniform Sampling and Effective Resistance Sampling of strong clusters with varying values of μ. Shaded region denotes sd over 20 runs.
6 Conclusion and Future Work
We presented structure-aware analysis of spectral sparsification via uniform edge sampling, showing that for well-clustered graphs--charccterized by a large structure ratio [(k)-unfform sampling suffices to preserve the spectral subspace critical for clustering. Our approach introduced new resistance bounds for intra-cluster edges, leveraged rank- (n k) formulation of effective resistance, and applied matrix Chernoff analysis to the dominant eigenspace. Together, these tools enabled the first provable guarantees for structure- structure-preserving preserving sparsification using uniform sampling alone.
Several directions remain open for future work. First, our resistance bounds-while sufficient for matrix moncentration-may be loose in practice; tightening them, especially by refining the dependence on x and T(k). could lead to sharper sampling rates. Second, extending this analysis to weighted graphs or graphs with overlapping clusters may reveal new structural insights. Finally, it would be valuable to explore whether similar structure-aware uniform sampling results can be obtained for other graph problems, such as semi-supervised learning, or spectral embedding beyond clustering.
10

---

References
[1] Emmanuel Abbe. Community detection and stochastic block models: Recent developments.
Journal of Machine Learning Research, 18(177):1-86, 2018. URL http://jmlz org/
papers/v18/ 1ate///v8116-4800 html
[2] Joshua Batson, Daniel A. Spiclman, and Nikhil Srivastava. Twice-ramanujan sparsifiers. SIAM Journal Computing, 41(6):1704-172) 2012.
[3] Radostaw Becker, Carsten Wendler, and Marcin Wrochna. Geometric embeddings of graphs and applications to spectral optimization. arXiv preprint arXiv:1711.065300 2017. URL
[4] Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, and Xuan Wu. The power of uniform sampling for coresets. In 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 462-473. IEEE, 2022. doi: 10. 11100FF0C55455.0022.2.00
[5] Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, and Prasoon Tiwari. The electrical resistance of graph captures its commute and cover times. 6(4):312-340, 1996. ISSN 1420-8954. doi: 10.1007/BF01270385. URL https://doi. org /0. 1007/ BF01270385
[6] Yan Mei Chen, Xiao Shan Chen, and Wen Li. On perturbation bounds for orthogonal projections. 73(2):433 444, 2016. ISSN 1572-9265. doi: 10.10077/11075--1--00222 //doi.org/10. 00000//11075-00-0002222
URL https
[7] Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. Uniform sampling for matrix approximation, 2014. URL http:://////rrii.orrg org/abs/
[8] Artur Czumaj, Pan Peng, and Christian Sohler. Testing cluster structure of graphs. In Proceed- ings of the 47th Annual ACM Symposium Theory of Computing (STOC), pages 723-732, 2015.
[9] James Demmel and Krešimir Veselić. Jacobi's method is more accurate than QR. 13(4): 1204 1245, 1992. doi: 10.1137/06 13074. URL https://doi. /tt.////..rrrr11.11////111111111 10171/1111117 http://di..rrr111.1137/////6
-eprint:
[10] Lingxiao Huang and Nisheeth K. Vishnoi. Coresets for clustering in euclidean spaces: Impor- tance sampling is nearly optimal, 2020. /ttLittt////rxxx.rr///aaaa///
[11] Michael Kapralov and Rina Panigrahy. Spectral sparsification via random spanners. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS '12, page 393-398, New York, NY. USA, 2012. Association for Computing Machinery. ISBN 1781450311151, doi: 10. 00.1145/2000236620000666 URL httph:t/po//oot or./10..
2090236. 2090267]
[12] Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, and Luca Trevisan. Improved cheeger's ' inequality: Analysis of spectral partitioning algorithms through higher order spectral gap. 2013. URL http://arxix org/ wwarg//b//iia abaaaaaa//1/0 5584
[13] Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. Benchmark graphs for testing community detection algorithms. Physical Review E, 78(4). October 2008. ISSN 1550-2376. doi: 10.1 10.1103/physreee. 78..e.7.... 78.046610 10. http:///
doix org/ 10. 1103 www.0////yy/eeeee.ee 78. 046110
[14] Jianing Lou Lingxiao Huang, Shaofeng H.-C. Jiang. The power of uniform sampling for k-median clustering. In Proceedings of the 40th International Conference on Machine Learning (ICMI.), 2023.
[15] Peter Macgregor and He Sun. A tighter analysis of spectral clustering, and beyond. Proceed- ings of the 39th International Conference Muchine Learning, pages 14717-14742. PMLR, 2022. http:tttss//prrcceddnng mmw.mngss..rrr...mmmmmmm..m wtt..pp.reeeeeee/////rggggggg22a html. ISSN: 2640- 3498.

---

[16] Pan Peng, Daniel Lopatta, Yuichi Yoshida, and Gramoz Goranci. Local algorithms for estimating effective resistance, 2021. URL hattps://arrivvorgg/aaaa
03476
[17] Richard Peng, He Sun, and Luca Zanetti. Partitioning well-clustered graphs: Spectral clustering works! In Proceedings of The 28th Conference on Learning Theory, pages 1423-1455, PMLR, 2015. URL /attps://procceedings. mmlr pr Serres//40//Ee wvaps////OPPeeg555// html ISSN: 1938-7228.
[18] Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888 905, 2000. doi: 10.1109/34.66688.
URL http:: org/ 10. 1109/34.... 868688
[19] Daniel A. Spiclman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6):1913-1926, 2011. doi: 10.1137/080734022.
URL https
7/doi www.1..og111.1111 11710001117//
[20] Daniel A. Spielman and Shang-Hua Teng. Spectral sparsification of graphs, 2010. URL
http://arxiv..o ottp://vv..rrr////0/003 4134
[21] JG Sun. The stability of orthogonal projections. J. Graduate School, 1: 1:123-133, 1984.
[22] Yi Yu, Tengyao Wang, and Richard Samworth. A useful variant of the davis kahan theorem for statisticians, 2014. URL (RLLhtts::////
http//bb/1400....0
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In our abstract and in the introduction under "technical contributions" we give a description of the claims and the results we prove in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Throughout our paper, we explicitly state the assumptions and conditions that we require for our theory to hold. In our paper we use clusterability parameter T that has been used in many previous works, and we require rank n l condition number ii in our sampling bound. Additionally, In the conclusion, we discuss that our effective resistance bound may be loose in practice, and we note the strong dependance on K, which may to restrictive in real world applications.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specifiiattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
13

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: In every theorem and lemma state all of the conditions and parameters (for example pa(k), T,x) required for the statement and then give a proof.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We will release the experimental code and datasets. In Section 5 we describe the setup for experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility.
14

---

In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We will release all the code for generating the experimental results. We describe the setup in Section
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/cipp..cc/ublic/guiieeee guw.e//ddee/eee CCodeSubeeiieeeee cesbbbmmssiiiee onyolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: We specify the exact datasets use. In the experiments section 5 for the stochastic block model we specify nodes and probabilities.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
In the experiments section 5 we specify number of runs with I sd error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
15

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eπror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: In the experimentss section 5 we describe the computer resources including processor and memory.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Our work is theoretical and does not involve any human subjects or any obvious ethically sensitive applications. We assume conforms the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [No]
16

---

The paper focus is mostly theory and the focus is on the theorems and lem- mas. While our method for uniform sampling may have larger implications for applications that use spectral clustering, we do not explicitly discuss the larger impacts.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
This paper explores the use of uniform sampling for sparsifying graphs for clustering applications. The datasts and methods we use are open sourse and thus do not pose risk for safeguarding beyond standard practices.
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
In our experiments we cite the datasets we use and provide their source.
Guidelines:
The answer NA means that the paper does not existing assets.
17

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, patiasets.paperssttt paperswi thcode. com/ datasets
has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper is mostly theory with validation from open source datasets. We do not release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our research does not crowdsourse experiments nor use any human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for rescarch with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
18

---

The research does not involve human subjects and therefore does not need an IRB
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
Declaration LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLM's were used in helping us write code for the experiments to validate our theory. But there is no core methodology in our paper that requires LLM.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
httppe//ioorrps.cc//offrrrrcacce
19

---

A Proofs
A.1 Proof of Theorem 4.1 from 15
Proof of Part I. Define V = [V1,-.., ViJ- Let vector v, be the projection of vector c; onto the
subspace spanned by {vz}}=1;
V&VIC ai ak
(
Vb
(2)
By the definition of Rayleigh quotients: R(c,) (a [ai'v] vi + ... + an vn
V1 +0p Vn)) L((a
(3)
c
= (a) + ... )
(4)
(az (8) ) + .... (a ) (1-a' (1 (2
22
where = (a
+ (a )² and we use the fact that the squared norm of the coefficients of
C, is 1.
Therefore:
R(c,)) 1
1 1- a - 12 2 Ax+1
(6)
T(k)
And:
||. -112 (ax41) )2
(1)
.... + +aa 1 a a (aa - T(k)
Proof of Part 2. Define C = [cI,..., Ck). For each 1 S i let
: CC E(vic,je
(8)
The objective of bounding Σ ||v; - 2b112 is equivalent to bounding the following projection approximation:
IV
(9)
Let L = VEVT be the eigendecomposition of the Laplacian. Then:
tr( Cr(C = =C(C'VVVV
(10)
= -r(C"V +
(11)
2 VVV
(12)
V A
Vn C)
(13)
(14)
Note that tr( CC(C = D R(C+) S (k)(k). Combining the statements above, get:
|V C kk)(k) k
(15)
Ast1
T(k)
This gives us the final bound on the approximation of the eigenvectors:
k k> IV.V. 2 k
(16)
T(k)
20

---

A.2 Proof of Theorem 4.2
Proof. Let = / be the SVD of the edge-incidence matrix, and S sampling matrix that satisfies - - + L We have I, VEVT and
EUS L = V uS = L vE / U' -
Note that -eL 3 V I eL, and since L is normalized, we have | S C.
We start with the sum over the Rayleigh quotients of the cluster indicator matrix:
From the eigendecomposition of L, we obtain:
kpa (k) + tr(C² AC) 2 X V
(17)
We can obtain an upper bound on tr(C" AC):
|tr(C" AC) = |tr(C / BUE
|x((X"EX)
|tr(XX E)
S |XX* 1| |E|2
$ E
S /2 C
etr(C" VV // u2
etr(C" kkpp(k)
Plugging this back into our inequality, get:
(1 + (k)
V. C
d
Using an eigenvalue perturbation result (Theorem B.3 since
| < we have for each d:
This gives the final bound:
(1 (k+c)kpk(k) 1 14 k
IV.- V
(1 - e)A++1 - T(k)
A.3
Proof of Theorem
Proof. From Theorem 4.8 we obtain a sparsified graph with Laplacian matrix with the following
guarantee.
(1 cxx Lx < L = (1+ c)x² Lx
Vx span (V .... vn
From the structure theorem by Macgregor al. 15 they have the following bound
k
I
C
21

---

Now we want to obtain an analogous bound for V ClF,, where V = (V,, V&] is the eigenbasis of Ln. We can consider the following
C - IV = (V,V - V
[T<(CC" V&VD)I
S TT(CC") V. VaVile
=k =
IV V&
This implies that
M
VI - 12
k VV V=VII12
We now proceed to obtain an upper bound for VV VaVil2
Theorem 4.8 guarantees the following.
(1 (-e)x"Lm->> S (L + E) S (1+ L -
where E the error matrix in the dominant Vn-x eigenspace. Note ||E||2 S eAn. Using Theorem B.4 we obtain that
Iia-AV Vn- VT all2 min min (In- E) (2) |B||
$ minn11An-aa 1/ / exn
(18)
An
Se -1- c))+1
where 18 is from -
(1 s E & (1 + Ee), for all i = k + I,....n. n.
Using this bound we obtain
C x
e 1
k
(19)
h
V H c s
r 1 k
(20)
(21)
A.4 Proof of Lemma 4.5
Proof. We start with the upper bound.
"
1
(5. 8b 66. - -8n)
= Σ
(5. 60) "oou"" (ō. - 86)
(22)
X;
i=k+1
12
(Dio 120)2
(23)
Ai
i=
V - -66
(24)
A6+11
2
(25)
A6+11
22

---

To prove the lower bound, we first show that for vertices in the same cluster, the value of the bottom eigenvectors are almost constant. From the second statement of the structure we have that
k T(k)
Σ v2 - v S Σ Ilv CC v. v
Cc(c1... Ct. is defined such that each e; is the normalized cluster indicator vector. It is important to note that CC 02 has special structure. the columns of the matrix C are comprised of constant vectors whose support is defined by the each cluster C.. Hence, when we approximate each V linear combination of the columns of C, we get that CC o is a constant k-step function, where each step defined by each cluster. We define f CC V; the best k-step function approximation to Vy- In order to bound the difference between vi(a) and v.(b), we leverage the fact that vertices a and b are in the same cluster, which implies that
Va = (b)
Now we can prove the lower bound on the effective resistance
Rat (a, b) = Σ
(6n 5,) v.v. (6. 6n)
(26)
Xi
k+++
(Vi(a) vi(b))
(27)
Xi
i=1+1
(v:(a) vb)2
(28)
k=++1
2k
(2 T(k)
(29)
An
2
= (1 [(k)
(30)
AR+1
A.5 Proof of Lemma 4.6
Proof.
Emserl Σ C, CJII
k
Σ (C, Vol(C,)
2 1=1
- (c( Vol(C,)
1=1
pP((K) Vol(G)
= pa(k) - |E|
A.6 Proof of Lemma 4.7
Proof. We first prove the upper bound. Recall that
Utilizing Lemma 4.5 the We now obtain a lower bound for the denominator.
ExeR Te
numerator can be upper bounded by r. S A
2
23

---

Given the clusters {CI...., , we can partition the edge set into two disjoint set of intercluster and intracluster edges, E Einra Enterr- where Einta E the set of edges whose vertices lie within the same cluster and Fineer is the set of edges whose vertices lie in two different clusters. The denominator can be lower bounded
Σ <EE
Σ
Σ
Te
+
Te
eE eE
e Einer
Σ
2
Te
Enna
Lemma 4.
Σ (1
r)Tr
AK-1
E
1 (1 k/Tr) Ac+1
2
(| Einra
6
Lemma 1.6
2
(m pca(k) -m)) - k
Ac+1
_ k/r)
2
m (1 - po()))
k
AR+1
Combining the upper bound of the numerator and the lower bound of the denominator we have the final bound
Pe S (1 -- (1+)) k/T)
The proof for the lower bound follows similarly.
A.7 Proof of Theorem 4.8
Proof. We start with notation. Let Te := R"r*(e) (e) be the rank k effective resistance for an edge
E E. Let Pe = Ecen the associated probability distribution based on the effective resistances.
To
Let p E/|E| be the uniform distribution.
Let P E (n- where
Ln-k
P
Oux
Given matrix A E gaxx, The operation P AP takes the top k submatrix of A.
Let
R pint
PT
[L
+/2 n-
T +/2 P.
w.p. pTT /n
X.
otherwise
Observe that
Σ pui
E Σ X.
X.
E
Q"
+/2
8.8 L nー
Q
cE
Q"
+/2 LL
+ /2
Q
= Tn-k
it immediately follows that the smallest and largest singular value of E E.EE X, are equal to 1.
Pmin CE
X.)
pmaz (E
Σxxxx, Xx) =
eEE
24

---

Now we proceed to bound the norm of
X
X
2|2
R
|P"
+/2 " -n- Pll (L,
punit
R
+/2
k de 0 L +/2
p 112
pumit
R
(6th
L
12 x 8e)
punit
R Pe
punif
Using 4.7
For the application of the Chernoff bound we choose
2 3.5x(1-R/T)lnman
Then
2
X v
=: L
3.5In(n)
Then
2
P(Dmin
X.) 11--6 - S (n- k) exp(
S (n k)
-3/2
(31)
2T.
2²
P(Amax
X.) 2 (1 + +)} s (n k)) exp(
S (n k)-
(32)
3L
Thus we preserve the top n k eigenspace with high probability. The expected number of edges sampled is
Σ
D
unif
IR
Σ k(1 k/T)p./R
(33)
EEE
k k/ k/T k)) In(n k)/e²
(34)
This follows from the fact that the sum of the rank n h leverage scores must add up to k (ie
Σe Pe n k)).
For this sampling to hold we need that R 3.5x(1- pky ln probabilities for each exceeds 1.
<
EJ, otherwise the sampling
B Useful theorems
Theorem B.1 (Matrix Chernoff). Let (Xx} be a finite sequence of independent, random, Hermetian matrices with common dimension Assume that
0 < Amin (Xx) Amax (X&) S L
Vk
LetY = Ee Xx. Xx. Define
Puin = Amin (EY)
(35)
Mmax Amax EY)
(36)
(37)
Then,
é Puin
P(Amin (Y) < (1 c)pminn exp(
(38)
2L
P(Amax (Y) 2 (1 c) < exxpp
Pmax
(39)
3L
25

---

Theorem B.2 Davis-Kahan Theorem from (22)). Let A, A E R be symmetric. with eigenvalues
A1 1.... Ap and Å .... 2 Ap respectively. Fix 1 - S 8 S p and assume that min(>r where 2o = 0o and Ap+1 = 00. Let d := $ +
++ 1, and let V (Vr, v vo) E Rexd and V = (Vr, Vrt1,..., v,,) E Rexd have orthonormal columns satisfying Av, 2jv; and Ad; for = =r, 1, .. Then
),, )
2 mminnd A Ilop I AllF)
sin (VV, F s
(40)
min min(Ar-1 dr, X
Moreover. there exists orthogonal matrix Ô Raxd such that
23/2 min(d lops A AlF IÃÓ Vil S
(41)
min Ap-1 Ao - A
Theorem B.3 (Theorem 2.3 from Let DAD a symmetric positive definite matrix such that D is diagonal matrix and Ai for all i. Let DED be perturbation matrix such that [El| S Amin (A). Let X; the i-th eigenvalue of DAD and X₁ be the i-th eigenvalue of D(A + E)D. Then, for all i,
E
A X
S
Amiu (A)
Theorem B.4 (Orthogonal Projector Distance from [61[1)). Let A E R=x= and let B = A EE Baxn, Let AI II be the projection matrix onto the column space of A, B respectively, Then huve the following bound
A 1gl1 2 S. m 1 | 11 |
26


Reviews:
[{"review_id": "4w253TqmHW", "reviewer": "Reviewer_UEcv", "summary": "The paper investigates the effectiveness of uniform edge sampling for spectral sparsification in the context of spectral clustering. Traditionally,  spectral sparsification involves the approximate computation of effective resistance values for sampling. This work, however, demonstrates that under certain graph-structural assumptions, specifically quantified by a structure ratio $\\Upsilon$, simple uniform sampling can effectively preserve spectral clustering structure. High structure ratio $\\Upsilon(k)$ implies that the clusters within the graph are well-separated and the graph has a clear $k$ - partitioning structure. Under such conditions, the authors show that uniform edge sampling (randomly selecting edges without bias) sufficiently preserves spectral clustering quality, eliminating the need for other importance-based sampling methods.\n\nThe main theoretical result establishes that uniformly sampling edges preserves the eigenspaces crucial to clustering, given a sufficiently large structure ratio and well-conditioned rank properties. Experiments using stochastic block model (SBM) graphs confirm that uniform sampling performs comparably to more expensive sampling strategies under these conditions.", "questions": "See the weakness section.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n1) The paper identifies conditions under which uniform sampling suffices for spectral sparsification.\n\n2) Introduces rank‑(n‑k) effective‑resistance formulation and subspace‑specific Chernoff bound. \n\nThe paper shows that if a graph is genuinely clusterable, expensive importance sampling is unnecessary. This is a non‑trivial theoretical contribution that sharpens our understanding of when uniform sampling works. While the practical section is thin, the conceptual result fills a gap between coreset theory and spectral sparsification and should interest both theoretical and applied communities.\n\nWeakness:\n\n1) Evaluating the method on graph families beyond SBMs would better demonstrate its empirical robustness.\n\n2) The experiments could include synthetic graphs that span a range of condition numbers.\n\nRelated work:\n\nSuggestion: include the following work in the related work section. Efficient approximation algorithms exist to estimate effective resistance. However, that doesn’t lessen the significance of the results established in this paper. \n\nLocal algorithms for estimating effective resistance, KDD 2021.", "was_revised": true, "final_justification": "This work’s main contributions are theoretical, and the overall quality is strong. I maintain my score.", "rebuttal": "> Evaluating the method on graph families beyond SBMs would better demonstrate its empirical robustness\n    \nThank you for this suggestion. We agree that evaluating our approach on additional graph families would strengthen the empirical validation. In a revision, we would include experiments on other well-studied graph models, such as Degree-Adjusted SBMs and also Hierarchical Random Graphs to evaluate the performance of uniform sampling under finer-grain cluster structures. We will also try larger-scale experiments to see if there are any significant changes. Preliminary experiments on the above families during the rebuttal period seem to indicate that our approach still works in those families of graphs, and in larger-scale graphs, as predicted by our theoretical bounds. \n\n> The experiments could include synthetic graphs that span a range of condition numbers.\n    \nThis is an excellent suggestion! We will include experiments that systematically vary the condition number and structure ratio $\\Upsilon(k)$ to empirically validate how these parameters affect uniform sampling performance, providing clearer practical guidance on when our method is most effective. In particular, we also need to understand the connection between the condition number of, say, SBM-generated graphs and the clustering parameter $\\Upsilon(k)$. In preliminary evaluations and in order to control the condition number, we had to vary the cluster sizes and we observed, as expected, a correlation between the ratio of the largest to the smallest cluster and the condition number. In preliminary evaluations, this does not significantly affect the performance of our approach, but more extensive experiments are needed. \n\n> Suggestion: include the following work in the related work section. Efficient approximation algorithms exist to estimate effective resistance. However, that doesn’t lessen the significance of the results established in this paper. Local algorithms for estimating effective resistance, KDD 2021.\n    \nThank you for the reference to the KDD 2021 work. Indeed, there exist many algorithms that seek to approximate effective resistances both theoretically and empirically. We will add this discussion to our related work section. It is worth noting that all these algorithms only guarantee additive error approximations: our bounds when exact effective resistances are used to sample edges would still hold if relative-error approximations or constant factor approximations to the effective resistances were used (with a small loss in the quality of our guarantees). However, this is not the case when additive error approximations to the effective resistances are used."}, {"review_id": "uTFPX1rvrx", "reviewer": "Reviewer_irHX", "summary": "This paper investigates whether uniform edge sampling can suffice for spectral clustering in graphs with well-separated clusters. The main contribution is a theoretical analysis showing that uniform sampling preserves the spectral subspace necessary for clustering under strong clusterability conditions. The authors derive resistance bounds for intra-cluster edges to analyze uniform sampling for clustered graphs.", "questions": "If I understand correctly, one main practical conclusion of this work is to show that the expensive effective resistance sampling does not surpass trivial uniform sampling as much as we'd expect. What about other sampling strategies?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. Understanding the side effects of uniform edge sampling is an important topic for graph sparsification. The paper provides a novel theoretical analysis showing that uniform sampling suffices for spectral clustering under strong clusterability conditions.  \n2. The results suggest that simple and efficient uniform sampling can be effective for large-scale spectral clustering.  \n3. This paper introduces resistance bounds and the matrix Chernoff bound, which may be of independent interest for spectral graph theory.\n\nWeaknesses\n1. While the theory appears compelling, the numerical experiments are limited to small random graph models.\n2. Real-world graphs are seldom well-clustered so the structure ratio $\\Upsilon(k)$ is usually not large enough for the discussions to hold.", "was_revised": true, "final_justification": "The primary contributions of this work are theoretical in nature, and the overall quality is robust, albeit constrained by certain simplifying assumptions necessary to facilitate the proof.", "rebuttal": "> While the theory appears compelling, the numerical experiments are limited to small random graph models.\n\nWe would like to emphasize that this work is, primarily, a theoretical contribution that establishes a new understanding of sparsification and provides new analytical tools, following the practice of past seminal papers in spectral graph theory. We use the flexible SBM experiments to validate our theory, consistent with what has also been done in previous works, e.g., [1,3]. This allows us to have precise control over graph constructions to verify our theoretical contributions. Further development of other algorithms as suggested by the reviewer are indeed important future directions which will require deeper empirical evaluations. \n\n> Real-world graphs are seldom well-clustered so the structure ratio is usually not large enough for the discussions to hold.\n   \nWe acknowledge that not all real graphs for clustering satisfy our conditions, and our results will not be applicable for those graphs. Our contributions use clusterability assumptions that have been established in prior seminal works like Peng et al. and Macgregor et al. [1,3] . We want to emphasize that our contribution includes new tools, such as the rank (n-k) effective resistance, to inform practical algorithm design. \n\n> If I understand correctly, one main practical conclusion of this work is to show that the expensive effective resistance sampling does not surpass trivial uniform sampling as much as we'd expect. What about other sampling strategies?\n\nOn one hand, we have the optimal sampling regime of effective resistance sampling, and on the other hand, we have oblivious uniform sampling, which we demonstrate is sufficient for sampling. A very promising future direction is to use a uniform subsample to compute a coarse approximation of the effective resistance. We can subsequently sample using the approximate effective resistances. This technique has been explored in Cohen et al. [4] and can be extended to our setting. We will discuss this in our revision. \n    \n[1] Peter Macgregor and He Sun. A tighter analysis of spectral clustering, and beyond.\n\n[2] Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances.\n\n[3] Richard Peng, He Sun, and Luca Zanetti. Partitioning well-clustered graphs: Spectral clustering works!\n\n[4] Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. Uniform sampling for matrix approximation."}, {"review_id": "7nBILRpRrs", "reviewer": "Reviewer_R6LN", "summary": "The authors work on the problem of spectral sparsification in the context of graph clustering. their primary contribution is demonstrating that if a graph has a large structure ratio, i.e., it naturally forms k clusters, with few edges in between each cluster, then uniform sampling will produce a sparsifier preserving the top $n-k$ eigenspace of the Laplacian. \n\n\nThe approach by the authors is much more efficient than the usual sparsification approach, which requires computing the leverage scores of the edges, and sampling proportional to them. Their work is more similar in spirit to CLMMPS14, exploring what can be achieved with uniform edge sampling.", "questions": "in the abstract $\\kappa$ is said to be the laplacian condition number, but i believe it is the ratio of the nth eigenvalue to the k+1th. Is this value polylog in the case of graphs that have large structure ratio?\n\nAs someone who is unfamiliar with this notion of the cluster ratio, what do graphs with large cluster ratio look like? If a graph has cluster ratio k^2, how many total edges are there across cuts?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\nThe authors prove some nice bounds on what uniform sampling can achieve, and give a concrete condition, large structure ratio, characterising when uniform sampling would perform well. On the way to proving these, they define some new notions for effective resistance, as well as clustering. \n\nWeaknesses\n\nI'm not quite sure how restrictive this graph class is, and what graphs with large structure ratio look like. Furthermore, it is not super clear what the purpose of proving this type of spectral bound is. If the goal is to sparsify graphs that naturally break into components, would running any graph clustering algorithm, then uniformly sampling the individual clusters not also achieve the same spectral bound?", "was_revised": true, "final_justification": "Overall, I would lean towards acceptance. \n\nI feel like this paper addresses a somewhat interesting question in this regime, where we ask what can be achieved with uniform sampling over leverage score sampling. The authors do indeed make an interesting contribution here, by describing precisely a metric, as well as a class of graphs, for which spectral properties are preserved. \n\nI do not personally similarly to the other reviewers about runtime objections here, it seems pretty clear to me that this will run in $O(|V|)$ time. The main reason why I did not give a higher score, is because it does not seem obvious to me what the applications of this work would be. Nevertheless, structural results like these do oftentimes end up finding use eventually somwhere.", "rebuttal": "> In the abstract $\\kappa$ is said to be the Laplacian condition number, but i believe it is the ratio of the nth eigenvalue to the k+1th.}\n    \nWe apologize for the confusion in our terminology. The reviewer is correct that $\\kappa := \\lambda_n/\\lambda_{k+1} $, which we refer to as the \"rank n-k condition number\" of the Laplacian. What we refer to as the ``Laplacian Condition number\" in the abstract is a condensed form of $\\frac{\\kappa^2}{(1-k/\\Upsilon(k))^2(1-\\rho_G(k))^2}$, which we mistakenly used the same notation $\\kappa$. We will fix this notation error and clarify it in the paper. In our response, we refer to the Laplacian Condition number as $\\gamma$ to prevent confusion.\n    \n> I'm not quite sure how restrictive this graph class is, and what graphs with large structure ratio look like.\n\nThe reviewer is raising a good point. Indeed, we cannot answer this question in full generality. We do know that graphs whose adjacency matrices have block-like structure with a few number of entries outside the block structure exhibit a large structure ratio. Graphs models like the Stochastic Block Model (SBM), Degree-Adjusted SBMs, and also Hierarchical Random Graphs tend to exhibit larger structure ratio $\\Upsilon(k)$. \n\n> it is not super clear what the purpose of proving this type of spectral bound is\n    \nThe purpose of our spectral bound is to address a fundamental challenge in spectral clustering: it requires computing the bottom k eigenvectors of the Laplacian, but this becomes prohibitively expensive on large graphs. Our bound establishes that uniform sampling of the edges (which corresponds to sparsification of the underlying adjacency matrix) can preserve the clustering-relevant eigenspace (the bottom k eigenvectors) with $\\mathcal{O}(\\gamma^2 n \\log n /\\epsilon^2)$ samples, eliminating the need for the rather expensive effective resistance computation entirely. Importantly, the penalty for using uniform sampling (captured by $\\gamma$) is *independent* of graph size, meaning the difficulty of uniform sampling is determined by spectral structure, not scale. This provides the first theoretical result of its kind, showing that simple uniform sampling suffices to make spectral clustering scalable while preserving the essential spectral subspace.\n    \n> If the goal is to sparsify graphs that naturally break into components, would running any graph clustering algorithm, then uniformly sampling the individual clusters not also achieve the same spectral bound?\n  \nThis is a great question: The reviewer essentially comments that clustering followed by sparsification might achieve the same goals and bounds. However, the challenge of spectral clustering is to discover the unknown cluster structure of the graph, and spectral clustering becomes prohibitively expensive as graphs get larger. This work highlights that we can use uniform sampling first to preserve the relevant spectral properties of the graph for clustering and, therefore, make spectral clustering cheaper. Existing methods all require a preprocessing step of computing the effective resistances (or approximate effective resistances) for all edges to determine which edges are important for preserving spectral structure. Our contributions show that under clusterability conditions, the expensive preprocessing step is not required - simple uniform sampling suffices.\n    \n    \n> Is this [$\\kappa$] value polylog in the case of graphs that have a large structure ratio? \n    \nFor graphs with a large structure ratio, the value of $\\kappa$ can greatly vary depending on the spectral structure of each individual cluster, and can in fact be a constant with **no dependence** on the size of the graph. For example, if we have two complete graphs with $n$ vertices and connect the two complete graphs with a few edges. The structure of the two complete graphs dominate the eigenspace from $\\lambda_2$ to $\\lambda_{2n}$, which results in $\\kappa = \\mathcal{O}(1)$.\n    \n> As someone who is unfamiliar with this notion of the cluster ratio, what do graphs with large cluster ratio look like? If a graph has cluster ratio $k^2$, how many total edges are there across cuts?\n    \nFrom an intuitive perspective, the cluster measure ratio of the strength of each cluster (captured by $\\lambda_{k+1})$ to the proportion of edge crossings between clusters (captured by $\\rho_G(k)$). From the example of the SBM, the $p_{in}$ value determines the strength of individual clusters, which should increase $\\lambda_{k+1}$, while a low value of $p_{out}$ corresponds to a smaller ratio of inter-cluster edges to intra-cluster edges, decreasing the value of $\\rho_G(k)$. \n    \nIf a graph has cluster ratio $\\Upsilon(k) = k^2$, this gives us the $k$-way cut cost of $\\rho_G(k) = \\frac{\\lambda_{k+1}}{k^2}$. From Lemma 4.3, in the paper, we have the bound on the number of inter-cluster edges $|E_{inter}| \\leq \\rho_G(k)\\cdot |E|$. This gives an upper bound of $|E|\\lambda_{k+1}/k^2$."}, {"review_id": "uyeX9KbPNQ", "reviewer": "Reviewer_51ez", "summary": "This paper considers the problem of sparsifying graphs to preserve the subspace used for clustering graphs clusterable into k pieces using spectral clustering. The paper proves that uniform sampling suffices to preserve this clusterability information provided that suitable number of samples are taken relevant to the number of nodes in the graph, certain measures of the condition number of the graph, and other parameters. Additionally, they perform experiments to corroborate their findings.  To obtain this result they introduce a new notion of effective resistance tailored to the desired approximation and use matrix concentration results tailored to their setting.", "questions": "Question / Suggestion: In the abstract it is claimed that the number of uniform samples in the final algorithm scales polynomially with the condition number of the matrix. However, later writing suggests that in fact it scales with a different notion of condition number. I think it is important to clarify which is the case early on. I think for context, it is also important to note that uniform sampling is known to give spectral sparsifiers with a number of samples that scale polynomial with the condition number of the matrix (if appropriately defined). From this perspective it seems that the paper’s improvement can be stated simply in terms of what condition number they depend on. I think it would be great if the paper articulated this a little more clearly.\n\nQuestion / Suggestion: What are the state-of-the-art runtimes / sample complexities for solving the problems of preserving the bottom subspace and for clustering? Are there overlap in techniques. I think this would be helpful to know and clarify a little more.\n\nHere are some additional detailed comments that may be helpful:\n* Page 1: Line 8: I’m not sure that \\lambda_{k + 1} and rho_G(k)\n* Page 1: Line 14: Perhaps “resistance bounds” should be “effective resistance bounds”\n* Page 2: Line 54: I’m not sure that the matrix C was defined. Also, it might be good to use a different symbol given the use of the scalar constant C in the same theorem.\n* Page 3: Line 124 – 127: I think one of the key results of that paper is that uniform sampling can be used (through appropriate frameworks to produce sparsifiers); this seems relevant and is not suggested by the summary.\n* Page 5: Line 178: I am not sure that “Spectral” should be capitalized in “The Spectral clustering”", "limitations": "Yes, with the possible exception of the concerns raised elsewhere in the review.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: Clusterability problems involving graphs are well-studied problems. New algorithms for graph clustering could have various applications and the spectral method is a natural method to try to improve the efficiency of.  More broadly, this paper considers practically motivated notions of graph approximation and proves that simple methods can obtain these approximations. Along the way the paper introduces a natural notion of edge importances and reasons about them. Altogether, this paper could facilitate future theoretical and practical developments for graph clustering and graph approximation more broadly.\n\nWeaknesses: The number of edges that the paper proves suffices scales near-linearly with the number of vertices and polynomially with measures of the input matrix condition number and the clusterability. It is unclear what the practical settings are where this size isn’t prohibitively expense and substantial reductions in the graph size are obtained. Additionally, there are various methods that have been proposed for the tasks that the paper suggests using graph sparsification for, e.g., subspace computation / approximation and graph clustering. It is unclear if the proposed technique gives end-to-end efficiency gains for these downstream tasks (especially as the methods one might consider may already use sampling). Furthermore, as discussed in the “Questions” section, I think the paper could benefit from a little more comparison and relating of the results to prior work and known approaches. \n\nFinally, I would note that the approach taken by the paper seems straightforward once the problem is established. This not necessarily a strength or a weakness but worth noting. If the paper could more completely articulate where which steps are standard and which are more novel or required novelty, it might elevate the submission.", "was_revised": true, "final_justification": "My score remains the same for the reasons outlined in the original review. The discussion elevated my view of the contributions paper but not quite enough to change the final numerical value; the concerns about significance from the original review persist. I think the paper would benefit from edits to reflect the discussion with the reviewers, in particular the relationship of the results to the known techniques for spectral sparsification.", "rebuttal": "> In the abstract it is claimed that the number of uniform samples in the final algorithm scales polynomially with the condition number of the matrix. However, later writing suggests that in fact it scales with a different notion of condition number. I think it is important to clarify which is the case early on. I think for context, it is also important to note that uniform sampling is known to give spectral sparsifiers with a number of samples that scale polynomial with the condition number of the matrix (if appropriately defined). From this perspective it seems that the paper’s improvement can be stated simply in terms of what condition number they depend on. I think it would be great if the paper articulated this a little more clearly.\n\nWe apologize for the confusion in our terminology. The reviewer is correct that $\\kappa := \\lambda_n/\\lambda_{k+1} $, which we refer to as the \"rank n-k condition number\" of the Laplacian. What we refer to as the \"Laplacian Condition number\" in the abstract is a condensed form of $\\frac{\\kappa^2}{(1-k/\\Upsilon(k))^2(1-\\rho_G(k))^2}$, and we mistakenly used the same notation $\\kappa$. We will fix this notational error and clarify it in the paper. In our response, we refer to the Laplacian Condition number as $\\gamma$ to prevent confusion.\n\n> The number of edges that the paper proves suffices scales near-linearly with the number of vertices and polynomially with measures of the input matrix condition number and the clusterability. It is unclear what the practical settings are where this size isn’t prohibitively expense and substantial reductions in the graph size are obtained. Additionally, there are various methods that have been proposed for the tasks that the paper suggests using graph sparsification for, e.g., subspace computation / approximation and graph clustering. It is unclear if the proposed technique gives end-to-end efficiency gains for these downstream tasks (especially as the methods one might consider may already use sampling).\n\nThe reviewer raises a valid concern regarding the practical scalability. Our sample complexity of $\\mathcal{O}(\\gamma^2 n \\log(n))$ can indeed be large when $\\gamma$ is large, and we do not provide theoretical bounds on $\\gamma$ in terms of properties of the graph. However, our contribution identifies a key property: **$\\gamma$ is structural property independent of the size of the graph**. Our results show that for well-clustered graphs, the difficulty of uniform sampling is captured by $\\gamma$, which characterizes the spectral structure of clustering, and not the size of the graph. In our experiments, we observe $\\kappa \\approx 12$ for well-separated clusters, compared to the $n \\approx 1,000$ nodes. \n    \nWe would like to note that the current state-of-the-art involves effective resistances using near-linear time Laplacian solvers [1,2]. These solvers are, in general, of theoretical interest, with limited practical applications. Additionally, even if a practical Laplacian solver existed, one still needs to compute the effective resistances for all edges, which could quadratically (in the number of edges) for dense graphs. In contrast, our approach requires only $\\mathcal{O}(\\gamma^2 n \\log n/\\epsilon^2)$ samples ($\\gamma^2$ is a constant that doesn't grow with graph size), plus a trivial preprocessing time for uniform sampling.\n\n> Finally, I would note that the approach taken by the paper seems straightforward once the problem is established. This not necessarily a strength or a weakness but worth noting. If the paper could more completely articulate where which steps are standard and which are more novel or required novelty, it might elevate the submission.\n   \nWe recognize that the algorithm seems straightforward once the rest of the framework is set. We would like to point out that there are several key insights and technical results in our work that are not straightforward but are required to arrive at the straight-forward algorithm. Previous spectral sparsification literature strongly suggested that importance sampling via effective resistances was *necessary* to preserve spectral structure. The fact that Uniform sampling works seems to heavily contradict conventional intuition. Standard effective resistance measures the importance of an edge with respect to the entire spectrum. Our key insight is that for clustering, standard effective resistance captures more information than necessary for clustering. Thus, we formalize the notion of \"rank n-k effective resistance,\" and prove novel bounds: specifically, we prove that the rank n-k effective resistance behaves nicely under clustering assumptions via Lemma 4.7. Such bounds do not hold for the standard definition of the effective resistance. The tight bounds on the full effective resistance by Chandra et al. [3] are not sufficient and would lead to a parameter $\\gamma$ that depends on the graph size. Finally, while matrix Chernoff bounds are a standard tool in the sampling literature, adapting them to our setting required non-trivial modifications. \n\nWhat are the state-of-the-art runtimes / sample complexities for solving the problems of preserving the bottom subspace and for clustering? Are there overlap in techniques. I think this would be helpful to know and clarify a little more. \n    \nAs far as we know, one could use variants of power method or Krylov methods to approximate the bottom part of the spectrum of a matrix. However, these methods are too expensive and their convergence properties depend on spectral gaps, etc. Also, implicitly, the nearly linear-time Laplacian solvers [1,2] preserve such subspaces as well as the associated singular values, but these are largely theoretical algorithms involving sophisticated data structures such as multilevel/combinatorial preconditioners and are not practical. Providing explicit running times for such methods is challenging; we will add these discussions and pointers to the literature in our revision. We thank the reviewer for bringing this up as it further highlights the importance of our results.\n        \n[1] Ioannis Koutis, Gary L. Miller, and Richard Peng. Approaching optimality for solving sdd systems\n\n[2] Daniel A. Spielman and Shang-Hua Teng. Spectral sparsification of graphs.\n\n[3] Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, and Prasoon Tiwari. The electrical resistance of a graph captures its commute and cover times."}, {"review_id": "3EaxJvwIux", "reviewer": "Reviewer_xS39", "summary": "This paper considers the use of uniform edge sampling for sparsifying a graph with the goal of using the sparsified graph for spectral clustering. While uniform sampling cannot be used for sparsification in general, the authors show that for graphs with well-separated k-clusters, it is possible to use uniform sampling. This is interesting because it provides a guarantee that unfiorm edge sampling suffices for preserving certain graph structural properties.", "questions": "(1) Can the authors please respond to my questions about the fairness of the experimental runtime comparison, given that effective resistances needn't be computed exactly for sparsification? \n(2) Can the authors address my question about the relative cost of nearly-linear time effective resistance computation vs the cost of spectral clustering the sparsified graph? \n(3) Given the conditioning assumptions, I am curious whether the authors believe that there could be a wider range of valid sampling distributions. Given that uniform and effective resistance sampling both work, I'm curious if the analysis could be generalized to show something even stronger. (Note: This is just a question out of my curiosity, and should not be considered a negative point against the paper.)", "limitations": "Yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 1, "originality": 2, "strengths_and_weaknesses": "Strengths: \n- the paper studies uniform sampling in a new context, and proves an interesting fact about the power of uniform sampling, and their result could be considered surprising given the precedent of effective resistance sampling for structure-preserving sparsification \n- the paper is overall well-written in my opinion \n- the result itself seems original, but see concerns below \n\nWeaknesses: \n- I am not completely sure how interesting/surprising this result is given the prior work of Braverman et al. '22 on the power of uniform sampling. As a side note, I think the authors do not sufficiently describe this related work.\n- The main result, while interesting, seems extremely niche to a specific application. I think the paper would be much stronger if the same analytical techniques were extended to more interesting applications. \n- I believe that the original Spielman and Teng paper on sparsification by effective resistance, one only requires a constant-approximation to the effective resistance, which can be computed in nearly-linear time. How does this overhead compare to the cost of computing the eigenvectors? This would be interesting to discuss, under different notions of approximate eigenvector computation. \n- Likewise, in the experiments, authors compute the effective resistance by explicitly evaluating the pseudoinverse rather than doing any JL-type approximations. This seems like an unfair comparison. I'd be curious how the error vs edges curves look if one calibrates the effective resistance approximation ratio to be larger. \n\nMinor: \n- There are a number of typos including missing references (??) in the submitted draft, but this is a minor point", "was_revised": true, "final_justification": "I would like to clarify that I maintain my score of 3 due to remaining unconvinced about the main claims raised in the rebuttal (as described in the chain above).\n- I find that the discussion of prior work on effective resistance is incomplete (the authors should have clearly mentioned that effres only need to be computed to constant accuracy in the original submission, so that all reviewers would have been aware of this fact.) This is a very big oversight, in my respectful opinion. \n- I don't think the paper clearly articulates when the results lead to a real improvement in the higher order runtimes. This would be okay, if this were an empirical paper, but this is a theory paper, and the overall runtimes should be made extremely explicit and formal. \n- Many of my questions from the original review were not addressed satisfactorily (see the chain below) and in some cases were answered incorrectly (in the rebuttal). Although the authors corrected such statements later, I still feel that my original questions were unfairly dismissed as \"out of scope\" and not ultimately answered. \n- As other reviewers and myself noted, I worry that the authors might be overclaiming the novelty of their work as the first to incorporate uniform sampling / alternatives to effres for sparsification. \n- Although this is a theory paper (and I am a theorist myself) I find that the empirical demonstration to effres is incomplete, for the reasons articulated in my rebuttal. This is a minor point, and I would not be concerned about it if I felt that the theoretical contributions were described (1) clearly and (2) completely in the sense of comparing to all relevant context of prior work.", "rebuttal": "As other reviewers have pointed out, there is a notation confusion regarding the rank-$(n-k)$ condition number $\\kappa:= \\frac{\\lambda_n}{\\lambda_{k+1}}$, and the Laplacian Condition number $\\frac{\\kappa^2}{(1-k/\\Upsilon(k))^2(1-\\rho_G(k))^2}$. For this response, we refer to the Laplacian condition number as $\\gamma$. We apologize for the confusion.\n\n**Relation to Braverman et al**\n\nOur work is complementary but fundamentally different from that of Braverman et al. They sample data points (nodes) for clustering coresets in *metric spaces*, while we sample graph edges for spectral sparsification. This difference in sampling targets reflects deeper distinctions in our mathematical frameworks. Their work with metric space clustering involving distance-based objectives like k-means and k-median, whereas we operate in the domain of spectral graph analysis involving Laplacian eigenspaces and matrix perturbation theory. Correspondingly, our structural assumptions differ: They rely on cluster-balance parameters and capacity constraints, while we depend on the spectral structure ratio $\\Upsilon(k) = \\lambda_{k+1}/\\rho_G(k)$ that captures clusterability in eigenspaces. These fundamental differences require distinct technical machinery. They employ VC-dimension theory and sensitivity analysis for point sampling, while our approach introduces rank-(n-k) effective resistance bounds, eigenspace-specific matrix concentration arguments, and novel connections between leverage score and uniform distributions in clustered graphs. Our novel contributions within this broader paradigm (and un-related to Braverman et al) include the first proof that uniform edge sampling preserves spectral clustering structure; new resistance bounds exploiting graph cluster structure rather than worst-case analysis; and matrix Chernoff analysis restricted to clustering-relevant eigenspaces. We will expand our related work section to properly position our contribution within this emerging understanding of when uniform sampling suffices across different domains.\n\n**Regarding niche scope and techniques**\n\nWhile spectral clustering itself is a specific technique, it has been a long-standing method in many fundamental machine learning and network analysis domains. We very much agree that our analytical techniques can and should be extended to more interesting applications; however, we want to emphasize that our contributions address a fundamental assumption in spectral sparsification for graphs that has stood since the seminal paper of Srivastava and Spielman [3], which established that importance sampling is necessary for spectral preservation. Our contribution provides the first theoretical proof that the assumption can be broken under structural conditions for an important problem like clustering. This breakthrough has implications beyond clustering for any spectral graph algorithm: in applications like streaming/dynamic settings, or distributed graphs, effective resistance computation is infeasible. The spectral sparsification literature is highly mature precisely because it is fundamental. New theoretical insights in such mature fields are often the most impactful as they challenge established paradigms and thus have tremendous downstream impact. Our work connects to the emerging theme showing that uniform sampling can be surprisingly powerful under structural assumptions, extending this insight to the spectral domain for the first time and changing how we think about when sophisticated sampling is necessary versus when simple methods such as uniform sampling suffice.\n \n**Regarding near linear solvers and cost of spectral clustering**\n\nWe acknowledge the remarkable progress in near-linear Laplacian solvers, from the seminal Spielman-Teng [4] work  through recent advances by Peng, Kyng-Sachdeva, and others. These achieve $\\tilde{\\mathcal{O}}(n)$ complexity using sophisticated techniques like combinatorial preconditioning and multilevel methods. However, these methods are mostly theoretical and many barriers remain that limit their real-world applicability. Specifically, the $|E|$ bottleneck always remains: regardless of how fast individual solver operations become, importance sampling requires computing effective resistance for every edge in the graph. For dense graphs with $|E| = \\Theta(n^2)$, this means processing $\\Theta(n^2)$ edges, which is an unavoidable quadratic cost that persists even with the most advanced approximation schemes. Additionally, while these solvers are theoretically elegant, they involve complex data structures and numerical conditioning that remain challenging to implement robustly, which explains why most practical systems still rely on other standard sparse methods. \n\nThere has been substantial work, for example by Koutis, Miller, Peng [2], that provides near optimal time for approximating leverage scores, but even those methods requires machinery like low stretch spanning trees, which make their implementation highly non-trivial. This has been a large motivating factor in our work where we aimed to provide theoretical guarantees on the effectiveness of uniform sampling, which is trivial to implement. Unlike effective resistance sampling, uniform sampling requires constant preprocessing and achieves spectral guarantees that match importance sampling up to a penalty factor $\\gamma$ that depends *only* on the graph's spectral structure, not its size. Our bounds show that for well-clustered graphs, this penalty remains moderate while eliminating all preprocessing overhead.\n    \nThe reviewer asks how the effective resistance computation cost compares to the eigenvector computation. The key insight is that eigenvector computation is unavoidable - we need it for spectral clustering regardless of our sparsification approach. Effective resistance computation represents additional preprocessing overhead that scales with graph density. Our contribution eliminates this preprocessing entirely. For dense well-clustered graphs, this represents a fundamental improvement: from $\\Omega(n^2)$ preprocessing plus eigenvector computation to just eigenvector computation. Even if near-linear resistance computation becomes practical, our result shows that this sophisticated machinery is theoretically unnecessary.\n\n**Regarding JL-type approximate effective resistances and comparisons**\n\nThere indeed has been significant progress on improving run-times for evaluating effective resistances, including by using JL approximations. However, these are orthogonal to our contributions. Approaches for approximating effective resistances were originally given by Spielman and Srivastava [3], who used JL projections; however their method still **required** a Spielman-Teng solver [4]. The fundamental $|E| = n^2$ bottleneck persists even with these approximations: for dense graphs, computing effective resistances for all edges requires processing $n^2$ edge pairs, leading to $\\mathcal{O}(n^2 \\log n/\\epsilon^2)$ total complexity regardless of how sophisticated the approximation scheme becomes. More critically, all prior approaches require complex data structure maintenance, random projection computations, and careful numerical conditioning. All this machinery is avoided by uniform sampling. We acknowledge that more sophisticated experimental comparisons using approximate resistances would strengthen our empirical evaluation; however, efficient implementations of Spielman-Teng solvers are not readily available for practical experimental comparison. At the scale of our experiments, we believe that computing the psuedoinverse \\textbf{once} and then applying it to all of the edges is the most efficient method of computing the effective resistances.\n\nOur theoretical runtime comparison shows that uniform sampling requires $\\mathcal{O}(\\gamma^2 n \\log n/\\epsilon^2)$ edges with O(1) preprocessing per edge, followed by an eigen-computation, while the resistance-based approach requires at least $\\mathcal{O}(\\log n/\\epsilon^2)$ preprocessing per edge plus the same eigen-computation. For well-clustered graphs where $\\gamma$ remains moderate and **independent** of $n$, uniform sampling provides a fundamental practical advantage by eliminating the preprocessing bottleneck entirely. While more sophisticated comparisons for fairer experimental setup can indeed be constructed, the purpose of our proof-of-concept experiments is to show effectiveness of uniform sampling in structured graphs; we agree approximations can speed up effective resistance calculations through non-trivial implementations (combined with JL approximations) but a fundamental gap will still remain. We will add this discussion in our paper and thank the reviewer for pointing this out.\n\n> I am curious whether the authors believe that there could be a wider range of valid sampling distributions. Given that uniform and effective resistance sampling both work, I'm curious if the analysis could be generalized to show something even stronger. (Note: This is just a question out of my curiosity, and should not be considered a negative point against the paper.)\n    \nThis is a good question that was also raised by another reviewer. A very promising direction is to use a uniform subsample in order to compute a coarse approximation of the effective resistance. This technique has been explored in Cohen et al. [1], and could be extended to our structured setting. This approach could potentially be a hybrid between uniform and importance sampling without the need for a fast Laplacian solver.\n\n[1] Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. Uniform sampling for matrix approximation.\n\n[2] Ioannis Koutis, Gary L. Miller, and Richard Peng. Approaching optimality for solving sdd systems\n\n[3] Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances.\n\n[4] Daniel A. Spielman and Shang-Hua Teng. Spectral sparsification of graphs."}]

Author rebuttal:

Meta-review: The authors present a new algorithm for spectral sparsification based on uniform sampling. While in previous work uniform sampling is used as a step to compute good sparsifiers, it is interesting to obtain good bound to get spectral sparsifier via uniform sampling.

The reviewers found the paper interesting and techniques nice although they all felt that the paper would improve significantly by:
- adding a more in depth comparison with the worked based on effective resistance
- adding a detailed comparison with the work "Uniform Sampling for Matrix Approximation"
- the experimental analysis is very limited and it would be nice to have a more comprehensive list of experiments
Decision: Accept (poster)