Research map / Learning theory and algorithms / Clustering
Coreset Spectral Clustering
Ben Jourdan, Gregory Schwartzman, Peter Macgregor, He Sun
Read the paperCheck your idea against 137,217 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes coreset spectral clustering that clusters a coreset graph and labels the full graph via kernel distances, plus a faster sparse-kernel D^2-sampling coreset construction.
Problem
Scaling spectral clustering and kernel k-means to large sparse graphs with many clusters, where existing coreset kernel k-means suffers from local optima and linear-in-k running time.
Approach
Exploit the equivalence between normalised cut and weighted kernel k-means to build a coreset of the graph, run spectral clustering on the coreset graph, and transfer the partition to all nodes via nearest coreset centroid in kernel space; a tree-based D^2-sampling reduces coreset construction time to roughly O(min(d_avg, k) n) on sparse kernels.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use coreset spectral clustering instead of coreset kernel k-means | HAR nearest-neighbor graph · HAR | ARI | Improved |
| Use coreset methods instead of sklearn spectral clustering | HAR nearest-neighbor graph · HAR | running time | Improved |
| Use fast CSC with a 1% coreset | Stochastic block model · 250 clusters | ARI: 0.5 | Improved |
| Use coreset kernel k-means instead of fast CSC | Stochastic block model · More than 50 clusters | ARI | Hurt |
| Increase the coreset size | Coreset kernel k-means · HAR | ARI | Improved |
Surprising findings
- Coreset kernel k-means is rendered useless by local optima after about 50 clusters on the synthetic graphs, even as coreset size grows.
Limitations
- Fast CSC performance declines gradually as the number of clusters increases, likely due to fluctuations in nodes sampled per cluster.
- The variant using full sklearn spectral clustering is too expensive for hundreds of clusters, so only the fast spectral clustering variant is evaluated at large k.
- Results on the synthetic graphs report ARI on coreset nodes only, not the full graph, because labelling dominates runtime.
Experimental setup
Datasets: Friendster LiveJournal wiki-topcats MNIST PenDigits HAR Letter synthetic stochastic block model graphs
Benchmarks: Friendster LiveJournal wiki-topcats MNIST PenDigits HAR Letter stochastic block model
Metrics: running time Adjusted Rand Index normalised cut
Baselines: coreset kernel k-means sklearn spectral clustering naive D^2-sampling coreset construction
Builds on: kernel k-means coreset (Woodruff et al.) k-means++ / D^2-sampling fast spectral clustering (Ng/Jordan style power method) sklearn SpectralClustering
Closest papers by meaning
- Fully Dynamic Coreset Spectral Clustering (ICML 2026 · similarity 0.91)
- COKE: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering (ICML 2025 · similarity 0.88)
- Universal Weak Coreset (AAAI 2024 · similarity 0.88)
- Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling (NeurIPS 2026 · similarity 0.87)
- Equivalence between Graph Spectral Clustering and Column Subset Selection (Student Abstract) (AAAI 2024 · similarity 0.87)
- Coresets for Clustering Under Stochastic Noise (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
