AI Paper Atlas

Research map / Learning theory and algorithms / Clustering

Coreset Spectral Clustering

Ben Jourdan, Gregory Schwartzman, Peter Macgregor, He Sun

ICLR 2025 · Learning theory and algorithms › Clustering · approach: Spectral clustering algorithms

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 changedWhereMeasuredEffect
Use coreset spectral clustering instead of coreset kernel k-meansHAR nearest-neighbor graph · HARARIImproved
Use coreset methods instead of sklearn spectral clusteringHAR nearest-neighbor graph · HARrunning timeImproved
Use fast CSC with a 1% coresetStochastic block model · 250 clustersARI: 0.5Improved
Use coreset kernel k-means instead of fast CSCStochastic block model · More than 50 clustersARIHurt
Increase the coreset sizeCoreset kernel k-means · HARARIImproved

Surprising findings

Limitations

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

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy