Structure-Aware Spectral Sparsification via Uniform Edge Sampling

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.

Relation to Braverman et al

Our 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.

Regarding niche scope and techniques

While 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.

Regarding near linear solvers and cost of spectral clustering

We 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.

There 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.

The 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.

Regarding JL-type approximate effective resistances and comparisons

There 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 once and then applying it to all of the edges is the most efficient method of computing the effective resistances.

Our 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.

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.)

This 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.

[1] Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. Uniform sampling for matrix approximation.

[2] Ioannis Koutis, Gary L. Miller, and Richard Peng. Approaching optimality for solving sdd systems

[3] Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances.

[4] Daniel A. Spielman and Shang-Hua Teng. Spectral sparsification of graphs.

We respectfully clarify that our runtime improvement does target the leading-order term of computation by removing a costly preprocessing bottleneck, and we have addressed this in the previous rebuttal. In particular, we have identified a regime where by using uniform edge sampling we eliminate the $\Omega(n^2)$ time needed to estimate effective resistances (or leverage scores) across all $|E|$ edges in a dense graph. This $\Omega(n^2)$ step dominated prior spectral sparsification methods, so bypassing it yields an asymptotic speedup in the highest-order term. Under the well-clustered graph assumption, our sample complexity is $O(n\log n)$. This approach aligns with recent theory emphasizing structure-driven speedups, including those by uniform sampling that we have also cited.

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.}

We 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.

I'm not quite sure how restrictive this graph class is, and what graphs with large structure ratio look like.

The 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)$.

it is not super clear what the purpose of proving this type of spectral bound is

The 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.

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?

This 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.

Is this [$\kappa$] value polylog in the case of graphs that have a large structure ratio?

For 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)$.

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?

From 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)$.

If 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$.

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.

We 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.

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).

The 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.

We 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.

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.

We 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.

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.

As 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.

[1] Ioannis Koutis, Gary L. Miller, and Richard Peng. Approaching optimality for solving sdd systems

[2] Daniel A. Spielman and Shang-Hua Teng. Spectral sparsification of graphs.

[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.

Evaluating the method on graph families beyond SBMs would better demonstrate its empirical robustness

Thank 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.

The experiments could include synthetic graphs that span a range of condition numbers.

This 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.

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.

Thank 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.

While the theory appears compelling, the numerical experiments are limited to small random graph models.

We 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.

Real-world graphs are seldom well-clustered so the structure ratio is usually not large enough for the discussions to hold.

We 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.

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?

On 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.

[1] Peter Macgregor and He Sun. A tighter analysis of spectral clustering, and beyond.

[2] Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances.

[3] Richard Peng, He Sun, and Luca Zanetti. Partitioning well-clustered graphs: Spectral clustering works!

[4] Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. Uniform sampling for matrix approximation.