acceptodds
Under review as a conference paper at ICLR 2027

Faster Spectral Clustering with Approximation Guarantee

Abstract

Spectral clustering is a basic algorithm in machine learning with widespread applications. However, classical spectral clustering requires computing the bottom eigenvectors of the Laplacian of the input graph, which leads to high time complexity. To address this limitation, we propose a faster clustering algorithm based on coresets and the Nyström method, and prove that it achieves the same approximation guarantee as classical spectral clustering. We empirically evaluate our algorithm on both synthetic and real-world datasets, and the results confirm that our algorithm runs substantially faster while producing results comparable to those of classical spectral clustering.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Spectral clustering, Nyström method

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_G8pcOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper propose a spectral clustering algorithm based on coresets and the Nyström method, namely SCNM. It essentially combines importance sampling, Nyström approximation of the positive semidefinite matrix SS, and weighted K-means. Experiments demonstrate speedups over the classical spectral clustering.

Critical strengths
  1. How to reduce time complexity while preserving a clustering spectral clustering guarantee is meaningful.
  2. A detailed theoretical analysis connects sampling, matrix approximation, and clustering error.
Critical weaknesses
  1. The current proof does not fully justify the running time claimed in the main theorem. Lemma 4.6 requires a filtering depth proportional to log⁡(1+A0/r(c))log⁡(1/γ)\frac{\log(1+A_0/r(c))}{\log(1/\gamma)}, γ=2−λk+12−λk\gamma=\frac{2-\lambda_{k+1}}{2-\lambda_k}. Equation (11) subsequently asserts that this is O(log⁡n)O(\log n), without bounding the denominator. A large Υ(k)\Upsilon(k) provides relative cluster separation but does not ensure a constant lower bound.
  2. Insufficient empirical analysis and overly broad claims.
Questions for authors
  1. How does Equation (11) follow from the assumptions of Theorem 3.1 without an absolute spectral-gap condition? Please provide more justification.
  2. Provide more details on implementations of each clustering methods, including parameters, eigensolvers, convergence criteria. Also, which sketch size or aggregation produce produced the results in Table 2?
  3. Why do CSC and NSC perform close to random on several datasets?
  4. Why the results of CSC on HAR dataset is different with the one in original ICLR 2025 paper.
  5. Why not perform comparison with the newest works, such as fully dynamic coreset spectral clustering (ICML 2026)?
  6. How to explain the substantial performance degradation on Pendigits datasets? Any limitations are indicated by this results?
  7. Why use weighted D2D^2-sampling strategy? An ablation study may help explain it.
4 comments

Thank you for the constructive comments.

  1. We overlooked that log⁡(1/γ)\log(1/\gamma) can approach zero even when Υ(k)≥C\Upsilon(k)\ge C. The stated assumptions therefore do not imply t=O(log⁡n)t=O(\log n). With the additional assumption λk+1=Ω(1)\lambda_{k+1}=\Omega(1), our analysis gives t=O(log⁡n+log⁡Υ(k))t=O(\log n+\log\Upsilon(k)), which yields t=O(log⁡n)t=O(\log n) when Υ(k)≤nO(1)\Upsilon(k)\le n^{O(1)}. We will revise Eq. (11) and Theorem 3.1 accordingly.

    Under these conditions, our bound of O(vol⁡(G)/Υ(k))O(\operatorname{vol}(G)/\Upsilon(k)) on misclassified volume can be tighter than the bound in Theorem 3.1 of Macgregor (2023) for almost-balanced clusters. For example, when Υ(k)=Θ(log⁡2n)\Upsilon(k)=\Theta(\log^2 n), we have ρG(k)=Θ(1/log⁡2n)\rho_G(k)=\Theta(1/\log^2 n). Macgregor’s condition ρG(k)=O(ϵ/log⁡(n/ϵ))\rho_G(k)=O(\epsilon/\log(n/\epsilon)) then requires ϵ=Ω(1/log⁡n)\epsilon=\Omega(1/\log n). The best bound his theorem gives in this regime is O(vol⁡(G)/log⁡n)O(\operatorname{vol}(G)/\log n), while ours is O(vol⁡(G)/log⁡2n)O(\operatorname{vol}(G)/\log^2 n).

  2. We used the coreset-sc implementation from Jourdan et al. (2025) for SC, CSC, and FSC. SC calls scikit-learn’s SpectralClustering. Following the authors’ example, CSC sets coreset_ratio to ℓ/n\ell/n and uses an oversampling factor of 2, a kernel shift of 0.01, and unit self-loops. FSC runs 10⌈log⁡2(n/k)⌉10\lceil\log_2(n/k)\rceil power iterations on the full graph without early stopping.

    We could not locate public NSC code, so we implemented the algorithm of Choromanska et al. with GPT-6 Astra Ultra and used Kimi 3 for code review. NSC uses ℓ\ell uniformly sampled landmarks, a requested rank of ℓ\ell, scipy.linalg.eigh, and a pseudoinverse tolerance of 10−1210^{-12}. SCNM uses sketch size ℓ\ell, filter depth tt, dense symmetric eigensolvers for the reduced matrices, and the positive semidefinite kernel K=D−1AD−1+D−1K=D^{-1}AD^{-1}+D^{-1} from Dhillon et al. (2007). Dataset settings and random seeds are in experiments/run_all_experiments.py. Table 2 uses ℓ=200\ell=200 for Fashion-MNIST.

  3. Our original HAR experiment used 8,000 points and 20 neighbors. We repeated it with 10,299 points and 200 neighbors to match the setting of Jourdan et al. At a 1% sampling budget, SCNM achieved a mean ARI of 0.448, close to the full-graph SC value of 0.447. The first tested budget at which CSC exceeded SC was 3.25% (ARI 0.475), consistent with their finding that a coreset below 5% can match SC.

    Mean ARI on HAR (n=10,299n=10{,}299, k=6k=6, 200 neighbors). SC uses the full graph.

    ℓ\ellℓ/n\ell/nSCNMCSCNSCSC
    1031.00%0.4480.1250.3200.447
    2572.50%0.4490.4050.3990.447
    3353.25%0.4490.4750.4580.447
    4124.00%0.4490.4550.4640.447
  4. At small budgets, few edges may connect the sampled CSC landmarks. For NSC, an average of 6.66% of vertices had zero embeddings at the 1% budget. SCNM can use paths through unsampled vertices.

  5. Jourdan et al. (ICML 2026) measure the cost of maintaining a clustering under graph updates and answering membership queries. We measure the running time and quality of a single partition on a fixed graph. Their static CSC algorithm therefore provides a direct baseline.

  6. The Pendigits results show SCNM’s sensitivity to the sampling budget. On the 20-nearest-neighbor graph (n=8,000n=8{,}000, k=10k=10, t=15t=15), increasing ℓ\ell from 80 to 400 raised SCNM’s ARI from about 0.25 to 0.60. At ℓ=400\ell=400, its ARI remained about 0.08 below that of full-graph SC (Figure 7).

  7. We use weighted D2D^2-sampling to select preliminary centers for the sensitivity scores. After the first center, each vertex’s sampling weight equals its degree times its squared distance to the nearest center. This is exactly its contribution to the current weighted kernel kk-means objective.

I thank the authors for their responses. Some of my concerns are addressed.

However, new experiment results under the matched setting shows that CSC and NSC obtain higher mean ARI than SCNM. The runtime of different methods are not reported for the new experiment. It is not clear that SCNM have computational advantages over CSC and NSC at different sample budgets. At the moment, I still think the contribution of SCNM is quite limited and may not provide enough values to our community.

Also, the response Our original HAR experiment used 8,000 points and 20 neighbors. is not disclosed in the original paper. It give me an impression that the original paper is not written carefully and all the results reported in Table 1 is not fair.

Additionally, I really suggest the authors provide details of the experiments in the paper to help readers assess whether the comparisons are fair and make the results easier to reproduce. It is suggested to done that in Appendix.

  1. Running times on the HAR dataset On the graph with 10,299 points and 200 neighbors, SCNM achieved higher mean ARI than both CSC and NSC at every tested budget from 1% to 2.75%. At 1%, the mean ARI / runtime in seconds was 0.448 / 0.509 for SCNM, 0.125 / 0.068 for CSC, and 0.320 / 0.202 for NSC. CSC and NSC were faster at every tested budget, and both achieved higher mean ARI at 3.25% and 4%. SCNM’s advantage here was that it reached the full-graph SC accuracy level (ARI 0.447) with only 103 landmarks.

  2. The value of SCNM algorithm On the SBM graphs, we varied the cluster separation p/qp/q, graph size nn, and number of clusters kk in three separate experiments. Across these settings, SCNM’s misclassification rate generally tracked full-graph SC and was lower than those of FSC, CSC, and NSC. For example, at n=12,000n=12{,}000 and k=15k=15, SCNM reached near-zero misclassification by p/q=20p/q=20, where FSC still misclassified over 20% of vertices and CSC and NSC each misclassified over 80%. SCNM’s running time was comparable to FSC’s and much lower than full-graph SC’s (Figure 2 and Appendix C.1).

    The original real-data experiments showed a similar pattern. In Table 1, SCNM achieved higher mean ARI than all three approximate methods on HAR and USPS (8,000 points, 20 neighbors) and on MNIST and Fashion-MNIST (15,000 points, 200 neighbors). Its mean normalized cut was lower than all three on all six datasets. SCNM was faster than full-graph SC on all six and faster than FSC on the three 15,000-point graphs. Appendix C.2, Additional Results on the Real-World Datasets, reports accuracy and running time across sampling budgets (Figures 6–13).

    Our theoretical guarantee directly bounds the misclassified volume of the returned partition. CSC gives a normalized-cut approximation guarantee, and NSC bounds spectral embedding error relative to an ideal block-diagonal model. For almost-balanced clusters with λk+1=Ω(1)\lambda_{k+1}=\Omega(1) and Υ(k)=Θ(log⁡2n)\Upsilon(k)=\Theta(\log^2 n), SCNM gives a misclassified-volume bound of O(vol⁡(G)/log⁡2n)O(\operatorname{vol}(G)/\log^2 n), compared with O(vol⁡(G)/log⁡n)O(\operatorname{vol}(G)/\log n) from Macgregor’s Theorem 3.1 for FSC.

  3. Experimental details. All five methods used the same graph for each dataset in Table 1. We chose 20 and 200 neighbors to evaluate sparser and denser graphs. Because of space limits, we reported these settings in Appendix C. The original Figure 6 caption specifies 8,000 points and 20 neighbors for HAR. We will add the graph settings and sampling budgets alongside Table 1 and document the matched HAR experiment in the appendix. The original benchmark configurations can be rerun with experiments/run_all_experiments.py. We are happy to help with any questions about reproducing the results. Thank you again for your valuable advice.

Thanks for your responses. I have no further questions at this stage.

Reviewer_uyoEOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies an efficient variant of the spectral clustering method, an important problem in analyzing large-scale datasets. The authors propose SCNM, a spectral method based on the Nystrom method and importance sampling, which avoids the more expensive direct eigendecomposition of the graph Laplacian. They prove that, under the same well-clusteredness assumption as Macgregor & Sun (2022), SCNM achieves the same bound on the volume of misclassified vertices as exact spectral clustering. They further show on synthetic SBM data and real-world datasets that SCNM achieves accuracy close to exact spectral clustering with a much lower running time.

Critical strengths

Overall, this paper is solid

  1. The proofs are complete and clearly written. The result is strong, as the misclustering volume matches exact clustering under the same assumptions as Macgregor & Sun (2022).
  2. The experiments on SBMs and real-world datasets show that the method achieves accuracy close to exact spectral clustering, outperforms other fast baselines, and runs substantially faster than exact spectral clustering.
Critical weaknesses

see questions

Questions for authors
  1. In Lemma 4.2, the Nystrom approximation guarantee requires that the sample size l \geq b·max{1536k^2, 3072k/\epsilon^2}. These constants can be very large. For example, in the synthetic experiment (Section 5.1), where the authors choose n=12000 and k=15, this requires the sampled indices size to be even larger than the original graph size. The guarantee therefore appears vacuous at practical sizes

  2. In Lemma 4.6, the required number of iterations is t \geq ln(1 + A_0/r(c)) / ln(1/\gamma). Here, the denominator, ln(1/\gamma) is of order \lambda_{k+1} - \lambda_{k}, which can be o(1). It is unclear to me why the eigengap factor is dropped and the lower bound on t is O(log n)

1 comment

Thank you for the constructive comments.

  1. The sample-size condition in Lemma 4.2 is sufficient but conservative. The proof uses Υ(k)≥4\Upsilon(k)\ge 4 to control eigenspace alignment. To establish invertibility and control the spectral tail, it then uses a worst-case bound on the sampling weights, bounds the operator norm by the Frobenius norm, and applies Markov’s inequality.

    On an SBM instance with n=12,000n=12{,}000, k=15k=15, and p/q=20p/q=20, we measured σmin⁡(F⊤H)=0.926\sigma_{\min}(F^\top H)=0.926, indicating strong alignment between the leading eigenspace and the ground-truth indicator space before sampling. With ℓ=600\ell=600 landmark draws (ℓ/n=5\ell/n=5\\%) and t=15t=15 power iterations, the mean misclassification rate over 25 runs was near zero at this and all larger tested ratios.

  2. We overlooked that log⁡(1/γ)\log(1/\gamma) can approach zero even when Υ(k)≥C\Upsilon(k)\ge C. The stated assumptions therefore do not imply t=O(log⁡n)t=O(\log n). With the additional assumption λk+1=Ω(1)\lambda_{k+1}=\Omega(1), our analysis gives t=O(log⁡n+log⁡Υ(k))t=O(\log n+\log\Upsilon(k)), which yields t=O(log⁡n)t=O(\log n) when Υ(k)≤nO(1)\Upsilon(k)\le n^{O(1)}. We will revise Eq. (11) and Theorem 3.1 accordingly.

    Under these conditions, our bound of O(vol⁡(G)/Υ(k))O(\operatorname{vol}(G)/\Upsilon(k)) on misclassified volume can be tighter than the bound in Theorem 3.1 of Macgregor (2023) for almost-balanced clusters. For example, when Υ(k)=Θ(log⁡2n)\Upsilon(k)=\Theta(\log^2 n), we have ρG(k)=Θ(1/log⁡2n)\rho_G(k)=\Theta(1/\log^2 n). Macgregor’s condition ρG(k)=O(ϵ/log⁡(n/ϵ))\rho_G(k)=O(\epsilon/\log(n/\epsilon)) then requires ϵ=Ω(1/log⁡n)\epsilon=\Omega(1/\log n). The best bound his theorem gives in this regime is O(vol⁡(G)/log⁡n)O(\operatorname{vol}(G)/\log n), while ours is O(vol⁡(G)/log⁡2n)O(\operatorname{vol}(G)/\log^2 n).

Reviewer_RADQOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes a faster spectral clustering algorithm based on coreset sampling and the Nyström method. The authors claim that the algorithm achieves the same misclassification-volume guarantee as classical spectral clustering, with a lower time complexity.

Critical strengths

The paper addresses an important problem of improving the computational efficiency of spectral clustering while preserving its theoretical clustering guarantees.

This paper studies a useful problem, which establishes a misclassification-volume guarantee for fast Nyström-based spectral clustering on well-clustered graphs, and potentially provides interesting theoretical result. The proposed analysis provides a connection between Nyström approximation error and clustering quality.

Critical weaknesses

eakness

  1. A potential gap in the running-time analysis.

Theorem 3.1 claims a running time of (O(k^4n+k^2m\log n+k^6)). However, Lemma 4.6 requires

[ t\geq \frac{\log(1+A_0/r(c))}{\log(1/\gamma)}. ]

The authors conclude that (t=O(\log n)), but I do not see how this follows from the assumption (\Upsilon(k)\geq C). In particular, this assumption does not imply a constant lower bound on (\log(1/\gamma)).

An additional assumption, such as (\lambda_{k+1}=\Omega(1)), may resolve this issue. However, this would weaken the claimed generality of the result. In particular, the paper explicitly claims the same assumptions as Macgregor and Sun (2022). Since the running-time guarantee is central to the paper, I consider this a major concern.

  1. Unclear technical novelty.

The analysis appears to rely largely on a relatively straightforward combination of existing techniques. Nyström-based spectral clustering has already been studied by Choromanska et al. (2013). The orthogonal alignment and eigenspace perturbation arguments in Lemmas 4.3 and 4.5 are also well established in the spectral clustering literature (see, e.g., Rohe et al., 2011). Moreover, Lemma 4.7 largely follows Macgregor and Sun (2022).

While combining existing techniques can certainly be valuable, I do not see a clear explanation of what nontrivial technical challenges arise from this combination or what new insights are required to overcome them. The authors should clarify the key technical novelty of their analysis, particularly in Lemma 4.2.

I also question the necessity of the coreset-based sampling scheme. Under the almost-balanced assumption, simple degree-proportional sampling (q_x=d_G(x)/\operatorname{vol}(G)) gives

[ \frac{|H_{x,:}|_2^2}{q_x}\leq 2k, ]

which is stronger than the bound in Lemma 4.1. This appears sufficient for the proof of Lemma 4.2. Thus, the same theoretical guarantee may hold without the proposed coreset construction. The authors should clarify its theoretical role and compare it empirically with degree-proportional sampling.

  1. Insufficient comparison with prior work.

The paper claims a "substantially stronger" guarantee than existing fast spectral clustering methods, but the precise source of this improvement is unclear. A more careful comparison of assumptions, guarantees, and time complexities with Choromanska et al. (2013) and Macgregor (2023) would help establish the contribution.

The related work also omits relevant research lines, such as the misclassification analysis of Rohe et al. (2011) and randomized or sparsification-based approaches to spectral clustering. These omissions further obscure the paper's position relative to existing work.

Questions for authors

I would love authors to address the weakness above.

1 comment

Thank you for the constructive comments.

We overlooked that log⁡(1/γ)\log(1/\gamma) can approach zero even when Υ(k)≥C\Upsilon(k)\ge C. The stated assumptions therefore do not imply t=O(log⁡n)t=O(\log n). With the additional assumption λk+1=Ω(1)\lambda_{k+1}=\Omega(1), our analysis gives t=O(log⁡n+log⁡Υ(k))t=O(\log n+\log\Upsilon(k)). We will revise Eq. (11) and Theorem 3.1 accordingly.

Under these conditions, our bound of O(vol⁡(G)/Υ(k))O(\operatorname{vol}(G)/\Upsilon(k)) on misclassified volume can be tighter than the bound in Theorem 3.1 of Macgregor (2023) for almost-balanced clusters. For example, when Υ(k)=Θ(log⁡2n)\Upsilon(k)=\Theta(\log^2 n), we have ρG(k)=Θ(1/log⁡2n)\rho_G(k)=\Theta(1/\log^2 n). Macgregor’s condition ρG(k)=O(ϵ/log⁡(n/ϵ))\rho_G(k)=O(\epsilon/\log(n/\epsilon)) then requires ϵ=Ω(1/log⁡n)\epsilon=\Omega(1/\log n). The best bound his theorem gives in this regime is O(vol⁡(G)/log⁡n)O(\operatorname{vol}(G)/\log n), while ours is O(vol⁡(G)/log⁡2n)O(\operatorname{vol}(G)/\log^2 n).

Our main technical contribution is Lemma 4.2. Our sampling distribution controls the row norms of the cluster indicator matrix HH, but global alignment with the leading eigenspace FF gives no pointwise bound on its leverage scores. We show that M=F⊤ΠΠ⊤HM=F^\top\Pi\Pi^\top H is well conditioned. Taking J=Π⊤HM−1J=\Pi^\top H M^{-1} gives F⊤ΠJ=IkF^\top\Pi J=I_k. Bounding the spectral-tail contribution of this same JJ yields Eq. (8) without computing the leverage scores of FF or knowing the target partition.

We agree that degree-proportional sampling suffices under almost balance, since ∣Hx,:∣22/qx=vol⁡(G)/vol⁡(Si)≤2k\\|H_{x,:}\\|_2^2/q_x=\operatorname{vol}(G)/\operatorname{vol}(S_i)\le 2k for x∈Six\in S_i. The distance term may improve clustering performance in practice by giving more sampling weight to regions poorly represented by the preliminary centers. For two equal-volume clusters, degree sampling gives each the same mass. If one has four times the degree-weighted mean squared distance to the nearest center, it receives 4/54/5 of their combined distance-term mass. Arthur and Vassilvitskii (2007) also observed lower kk-means costs with distance-based seeding on real datasets.

In the regime described in point 1, our algorithm gives a tighter bound on misclassified volume than Macgregor’s, but it has a less favorable dependence on kk and uses a spectrum-dependent filter depth. Choromanska et al. (2013) bound embedding perturbation relative to an ideal block model, whereas our guarantee concerns the returned partition. We will compare the assumptions, error bounds, and running times in greater detail and expand our discussion of prior work on misclassification guarantees (including Rohe et al., 2011) and randomized spectral clustering.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.