- 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 , and weighted K-means. Experiments demonstrate speedups over the classical spectral clustering.
Critical strengths
- How to reduce time complexity while preserving a clustering spectral clustering guarantee is meaningful.
- A detailed theoretical analysis connects sampling, matrix approximation, and clustering error.
Critical weaknesses
- The current proof does not fully justify the running time claimed in the main theorem. Lemma 4.6 requires a filtering depth proportional to , . Equation (11) subsequently asserts that this is , without bounding the denominator. A large provides relative cluster separation but does not ensure a constant lower bound.
- Insufficient empirical analysis and overly broad claims.
Questions for authors
- How does Equation (11) follow from the assumptions of Theorem 3.1 without an absolute spectral-gap condition? Please provide more justification.
- 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?
- Why do CSC and NSC perform close to random on several datasets?
- Why the results of CSC on HAR dataset is different with the one in original ICLR 2025 paper.
- Why not perform comparison with the newest works, such as fully dynamic coreset spectral clustering (ICML 2026)?
- How to explain the substantial performance degradation on Pendigits datasets? Any limitations are indicated by this results?
- Why use weighted -sampling strategy? An ablation study may help explain it.
4 comments
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.
-
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.
-
The value of SCNM algorithm On the SBM graphs, we varied the cluster separation , graph size , and number of clusters 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 and , SCNM reached near-zero misclassification by , 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 and , SCNM gives a misclassified-volume bound of , compared with from Macgregor’s Theorem 3.1 for FSC.
-
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.
Thank you for the constructive comments.
We overlooked that log(1/γ) can approach zero even when Υ(k)≥C. The stated assumptions therefore do not imply t=O(logn). With the additional assumption λk+1=Ω(1), our analysis gives t=O(logn+logΥ(k)), which yields t=O(logn) when Υ(k)≤nO(1). We will revise Eq. (11) and Theorem 3.1 accordingly.
Under these conditions, our bound of O(vol(G)/Υ(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)=Θ(log2n), we have ρG(k)=Θ(1/log2n). Macgregor’s condition ρG(k)=O(ϵ/log(n/ϵ)) then requires ϵ=Ω(1/logn). The best bound his theorem gives in this regime is O(vol(G)/logn), while ours is O(vol(G)/log2n).
We used the
coreset-scimplementation from Jourdan et al. (2025) for SC, CSC, and FSC. SC calls scikit-learn’sSpectralClustering. Following the authors’ example, CSC setscoreset_ratioto ℓ/n and uses an oversampling factor of 2, a kernel shift of 0.01, and unit self-loops. FSC runs 10⌈log2(n/k)⌉ 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 ℓ uniformly sampled landmarks, a requested rank of ℓ,
scipy.linalg.eigh, and a pseudoinverse tolerance of 10−12. SCNM uses sketch size ℓ, filter depth t, dense symmetric eigensolvers for the reduced matrices, and the positive semidefinite kernel K=D−1AD−1+D−1 from Dhillon et al. (2007). Dataset settings and random seeds are inexperiments/run_all_experiments.py. Table 2 uses ℓ=200 for Fashion-MNIST.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,299, k=6, 200 neighbors). SC uses the full graph.
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.
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.
The Pendigits results show SCNM’s sensitivity to the sampling budget. On the 20-nearest-neighbor graph (n=8,000, k=10, t=15), increasing ℓ from 80 to 400 raised SCNM’s ARI from about 0.25 to 0.60. At ℓ=400, its ARI remained about 0.08 below that of full-graph SC (Figure 7).
We use weighted D2-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 k-means objective.