Coreset Spectral Clustering
Authors: Ben Jourdan
Gregory Schwartzman
Peter Macgregor
He Sun
Venue: ICLR 2025 Poster (2025)
Keywords: spectral clustering
kernel k-means
coresets
Primary area: learning on graphs and other geometries & topologies
TL;DR: We combine the benefits of spectral clustering and coresets

Abstract: Coresets have become an invaluable tool for solving $k$-means and kernel $k$-means clustering problems on large datasets with small numbers of clusters. On the other hand, spectral clustering works well on sparse graphs and has recently been extended to scale efficiently to large numbers of clusters. We exploit the connection between kernel $k$-means and the normalised cut problem to combine the benefits of both. Our main result is a coreset spectral clustering algorithm for graphs that clusters a coreset graph to infer a good labelling of the original graph. We prove that an $\alpha$-approximation for the normalised cut problem on the coreset graph is an $O(\alpha)$-approximation on the original. We also improve the running time of the state-of-the-art coreset algorithm for kernel $k$-means on sparse kernels, from $\tilde{O}(nk)$ to $\tilde{O}(n\cdot \min (k, d_{avg}))$, where $d_{avg}$ is the average number of non-zero entries in each row of the $n\times n$ kernel matrix. Our experiments confirm our coreset algorithm is asymptotically faster on large real-world graphs with many clusters, and show that our clustering algorithm overcomes the main challenge faced by coreset kernel $k$-means on sparse kernels which is getting stuck in local optima.

Published as a conference paper at ICLR 2025
CORESET SPECTRAL CLUSTERING
Ben Jourdan', Gregory Schwartzman', Peter Macgregor', and He Sun!
University of Edinburgh, UK
JJapan Advanced Institute of Science and Technology (JAIST),
UUniversity of St Andrews, UK greg jaist. ac. h. ac.uccukuk.k........
ben. b jonrdnneedee ac. uk,
ABSTRACT
Coresets have become an invaluable tool for solving k-means and kernel k-means clustering problems on large datasets with small numbers of clusters. On the other hand, spectral clustering works well on sparse graphs and has recently been extended to scale efficiently to large numbers of clusters. We exploit the connection between kernel k-means and the normalised cut problem to combine the benefits of both. Our main result is coresct spectral clustering algorithm for graphs that clusters a coreset graph to infer good labelling of the original graph. We prove that a-approximation for the normalised cut problem the coreset graph is ((a)- approximation on the original. We also improve the running time of the ofate-of-the-art coreset algorithm for kernel k-means on sparse kernels, from Ö(n)) to Ó( min (k, davg) }), where dang is the average number of non-zero entries in each row of the experiments confirm our coreset algorithm is asymptoticllly faster on large real-world graphs with many clusters, and show that our clustering algorithm overcomes the main challenge faced by coreset kernel k-means on sparse kernels which is getting stuck in local optima.
n kernel matrix. Our
INTRODUCTION
Kernel k-means and spectral clustering are two popular algorithms which are capable of learning non-linear decision boundaries between clusters. For this reason, they have been applied to many practical problems in machine learning, including in the fields of medical research and network
science (Gönen & Margolin, 2014 Kuo al. 2014 White & Smyth 2005).
Given a data set X, both kernel k-means and spectral clustering make use of a kernel similarity function K X X + R>o. which is often represented as a matrix of size n x n, where [X]. The spectral clustering algorithm considers the kernel matrix be the adjacency matrix of a similarity graph and clusters the nodes of the graph in order to minimise the normalised cut objective function, which we define Section 3 Von Luxburg 2007). Kernel k-means exploits the fact that the kernel function implicitly defines embedding of the data points into Hilbert space, represented by Φ= X + H. such that for all E X,
(I) The kernel k-means problem to minimise the k-means objective in this Hilbert space and is usually solved using a generalisation of Lloyds algorithm (Dhillon et al., (004), using the kernel K compute inner products. Remarkably, the normalised cut and kernel k-means objectives are equivalent up to constant factor (Dhillon et al. 2004).
(o(z), = K(x,y).
Despite this equivalence, spectral clustering and kernel k-means have been largely studied separately, and new techniques have been developed with one or the other in mind. For spectral clustering, one of the most promising techniques is to construct a sparse similarity graph in order to achieve a speedup, This can be achieved through constructing approximate nearest neighbour algorithms (Alshammari et al.) 2021 Harwood & Drummond] 2016 Malkov & Yashunin 2018), or by constructing clustering preserving sparsifier of the complete kernel similarity graph (Macgregor Sun| [023) (Snn & Zanetti 2019). By operating on a sparse similarity graph, the time and memory cost of spectral clustering reduced from Ω (n² to O( (onlo)n))):
approximate k-nearest neighbour graph using fast

---

Published as a conference paper at ICLR 2025
To speed up kernel k- k-menns, Jiang et al. (2024) applied recent coreset result for Euclidean spaces (Braverman et al. 2021 to kernel spaces. Given a dataset X and kernel function K, they showed that an E-coreset (Definition 4 of size Ó(k2= can be constructed in time Ó(k ! The cost of running an iteration of Lloyd's s algorithm on the coreset is then independent of n, for small k.
In this paper, we show that the benefits of the techniques developed for both spectral clustering and kernel k-means be combined in order to create faster and more accurate clustering algorithm. In particular, we show that, by exploiting the sparsity of the kernels usually considered for spectral design faster algorithm for constructing a coreset. Then, we apply
clustering, it is possible spectral clustering directly to the coreset graph with only a small number of nodes and use the result cluster the original graph. Empirically, we find that on sparse graphs our coreset spectral clustering algorithm has significantly faster running time than the classical spectral clustering algorithm, and achieves a higher accuracy than coreset kernel k k-means.
1.1 OUR RESULTS
Faster k-means++ and coreset construction. In Section 4 we exploit the fact that inputs to kernel k-means are often sparse to devise a faster algorithm for k-means++ initialisation in kernel space. Specifically, when the input kernel matrix is sparse, we improve the rumning time from ((nk) to Ö(n min(ks k. daeg)) where daey is the average number of non-zero entries in each row of the kernel matrix. Speeding up k- 4-means++ has received lot of attention for Euclidean spaces (Bachem al. 2016 Cohen-oohhccae Addad et al. 2020). This is the first result to provide speed up in sparse kernel spaces. Combining this with Jiang et al. (2024). we present the first coreset construction for kernel spaces that makes use of kernel sparsity, and reduce the coreset construction time from Ö(nk) to On min daeg)) while maintaining the same theoretical guarantees. For large graphs with many clusters, it is critical break the linear dependence on the number of clusters for practical use.
Coreset spectral clustering. In Section we introduce the coreset spectral clustering algorithm that explicitly combines spectral clustering with coresets by exploiting the equivalence between the normalised cut and weighted kernel k-means problems. Previous work has used this equivalence to convert spectral clustering problems to kernel k-means problems and then solve them using coreset kernel k-means (Jiang et al., (024).. We propose a new method which solves the coreset problem directly with spectral clustering and then transfers the solution back to the original graph. This sidesteps some of the less desirable properties that running kernel k-means would entail, such as its susceptibility to local minima when using indefinite kernels (Dhillon al., 2007). In Theorem [ we prove that an a-approximation of the normalised cut problem on the coreset graph gives an (aa)aaaproximatioon of the normalised cut problem on the original graph.
Experiments. In Section 6 we preform three experiments to test our coreset construction and coreset spectral clustering algorithms. The first confirms the asymptotic improvement in running time of our coreset construction algorithm for kernel k-means over the previous method of Jiang et al. (2024) on large real-world graphs with up to 65 million nodes and thousands of clusters. The second experiment compares coreset spectral clustering algorithm against coreset kernel k-means (Jiang (et al. 2024) and the sklearn (Pedregosa et al. 2011) implementation of spectral clustering on several real-world graph datasets. This shows that for a small number of clusters, the coreset methods much faster than spectral clustering and our coreset spectral clustering algorithm finds significantly better solutions than coreset kernel k-means. The third experiment compares our coreset spectral clustering algorithm against coreset kernel k-means on a synthetic graph dataset where we vary the number of clusters to be linear in the number of nodes. Using the spectral clustering method proposed by Macgregor (2023) to cluster the coreset graphs, this experiment shows that our method can scale to hundreds of clusters while coreset kernel k k-means is rendered ineffective by local optima after only tens of clusters.
2 RELATED WORK
The techniques for speeding up kernel k-means and spectral clustering can be broadly categorised into the methods that sparsify the relations between input data and the methods based on coresets.
We use Ō(-) to suppress polylogarithmic factors.
2

---

Published as a conference paper at ICLR 2025
2004), low rank approximations of the kernel matrix have been proposed (Musco & Musco| 2017; Wang et al. 2019) as well as low dimensional approximations of ø (Chitta et (0012). On the other hand, coresets for Euclidean spaces (Braverman et al. 2021 Har-Peled & Mazumdar 2004 Huang & Vishnoi] 2020) have recently been extended to kernel k-means QJiang et al. 2024). Coreset methods sample weighted subset of the input so that the
For kernel me-ms (Dhillon et al.
objective of every feasible solution is preserved.
For spectral clustering (Von Luxburg 2007 ) spectral sparsifiers (Spielman & Teng 2011) and more recently cluster preserving sparsifiers (Sun & Zanetti 2019) can sparsify dense graphs while retaining cluster structure. While effective in theory, spectral sparsifiers require complicated Laplacian solvers to run efficiently, making them difficult to implement in practice. Cluster preserving sparsifiers are practical to implement but their performance is sensitive to the choice of hyperparameters. [Pnn et al.. (2017) proposed nearly-linear time algorithm for clustering an arbitrary number of clusters which is similar in spirit to coreset approach. They sample O log(k)) nodes leveraging the property that in the spectral embedding nodes in the same cluster are nearby and have approximately the same norm. From this, they efficiently extract a set of points from which the rest of the data can be labelled. However, this approach is impractical they make of Laplacian solvers to approximate heat kernel distances.
As well sparsification and coresets, speedup can also be achieved via improvements to the optimisation algorithms themselves. The triangle inequality can be used to reduce the number of inner products calculated by the kernel k-means algorithm (Dhillon et al. 2004) and recently mini-bare batch algorithm has been proposed (Jourdan & Schwartzman 20024). Macgregor (2023) developed simple spectral clustering algorithm that forgoes the expensive computation of eigenvectors in place of (log(k)) independent calls to the power method. We refer to this method as fast spectral clustering and will use it in our experiments cluster coreset graphs.
PRELIMINARIES
Let X be set of n objects, and K X R20 be function measuring the pairwise similarity of data points in X. Let Φ: X + H be the function implicitly defined by K that maps data points in X to the unique Hilhert space such that ((y)) = K(r, y) for all x. y X. The function K is usually represented as a matrix: if +- = (6(x)),-.... ((x,)) then K
= TH E R with
Kú- - (ύ=(((z;)) o(x;)) Let A ((d(x), d(y)) & [|ő(x) d(v)l denote the squared distance in feature space for all x, y E X, and A A(o(s), C) = min.ec A ((((r), ((c)) denote the smallest squared distance from
X to a set CC X. We refer to the diagonal elements of K as self similarities and say x is a neighbour of (or incident to) y. written 2 ~ y, iff (ő(x), ,(v)) * If E X and S c X, say x is incident to S iff is incident to at least one clement of S.
Given graph G (V, E), the conductance of set S of vertices is defined as 2c(S) [E(S,V V S) /vol(())) where [ES, V S)) is the number of edges crossing the cut between S and V S and (S) is the total weight of edges incident to S. We define a k-partition of X to be collection of sets II = {T; 1 such that each element of X appears in exactly one member of II.
We make extensive use of the following concepts in our analysis.
Definition (centroids). Given a k-partition II = {Tili= of a set X, a map &b : X - H for some Hilbert space H., and a weight function X R4, define the set of centroids of II as e (II) & (T,))) where (TT) (ZEEs, w(z))(x) / (Ezex, w((x))
Definition 2 (kernel k-means objective). Given a weighted dataset X with weights w X - R. and feature map X H satisfying equation [or some kernel function K, the weighted kernel k-means objective with respect to an arbitrary set of points C C H. is
COST (X,C) Σ (()))((()))CC).
(2)
ZEX
The kernel k-means objective with respect to arbitrary k-partiton II == [TT of X is
COST (II) = ΣΣ
((
j=l
3

---

Published as a conference paper at ICLR 2025
Definition (Normalised cut objective). Given graph G = (V, E), the normalised cut problem is to minimise the aveerage conductance over all k k-partitions of the vertices: min
II(,,II), [1=
where I))
(T())
Definition 4 (E-coresets). For 0 < 1, an e-corset for kernel k-means weighted dataset X with weights w. X- + R2 a reweighted subset S C X such that for the Hilbert space H and map 6: X
H salisfying equation] 7 we have
CO E =1 COST
AC C H with |C| = k,
where w' : : + Rx gives the weight for each element in the coreset.
4 FAST CORESET CONSTRUCTION
Given a sparse kernel matrix with ((m) nonzero entries and weight function w. we give an algorithm to construct an E-coreset in (m) time. This improves on the algorithm given by Jiang et al. (202)) which has running time (nnk). The running time of Jiang et al. (2024) is dominated by the running time of D'-sampling. Algorithm 1 which just the k-means++ initialisation algorithm (Arthur & Vassilvitskii 2007) in kernel space. For completeness, we provide the full description of the E-coreset algorithm of Jiang et al. (2024) in Algorithm in Appendix
C.I
In Algorithm 2 we use the fact the kernel matrix is sparse to design efficient data structure, built around sampling tree (Wong & Easton 1980). perform D2-sampling in nearly-linear time in and independent of k. To avoid unnecessary updates to the sampling tree, our algorithm has to sample one additional data point prior to performing D²-sampling. Specifically, before uniformly sampling the first point, we will select the point in C' with the smallest self affinity. Let xx & arg min,ex x (0(x), Φ(x)) and c* - (Ø(2"), <(x")) We show that adding this extra point does not affect the approximation guarantee, and consequently we get a faster e-coreset algorithm for sparse kernels using the same analysis as Jiang et al. (2024).
Algorithm 1 D Sampling(l))) (Jiang et al.
2024
Input: X
2: Draw X uniformly at random, and initialise C' + {p(x)}
3: for i = I,...,k k do
4: Draw one sample x E X, using probabilities wx(x)
A(p(z),C) cosr (X.C)
5: Let Cu
6: end for
7: return C
4.1 OUR DATA STRUCTURE
The key observation is that as points are added to C, the distances from the data points C' can't tt change for too many points due to the sparsity of the kernel and our choice of x". We formalise this intuition in what follows. Let C C X be set of points such that xt is in C, and consider the squared distance from an arbitrary point x to C' feature space. We see that
A(r, min oEC
+ (o(c), o(c)) ((()) -()))))))))
2(6(z),
(0(x), ((x)((())))))))))))))))))))))( + (6(c), d(c))
2 x a~e
min aEc
(((xx), ol + (o(c), d(c)) - 2(0(x),
[2 (z. x²)
x x c for c C
(3)
min A A(I, c) .EC
otherwise,
where the last transition makes use of the fact that and A(r, (0(x), (())) + (6(x)) ((x))) (0(x), + (((c) ((x,
4

---

Published as a conference paper at ICLR 2025
for all X and C' such that of c. From this we see how adding a point to C changes the distance between some I E X and C:
[1 C) (mimm((2, (), I ~ y.
x y
(x CU CCC))
Assuming we know the values of A(x, C) for x E X, each time we add a point y to C, for each neighbour of y, it suffices to check whether A(x,y) is less than A(r, C). Let A X be the set returned by Algorithm 2 Then the total number
checks is EzEd deg(z) where deg(z)) = Ky x ~ y} is the number nonzero entries in the row of K corresponding to æ. In the worst case, have to check the entries in the rows of the l + 1 data points with the highest degree. Letting davg 2| be the average degree, holds that
davg
2 2
Σ FEX
deg(x)
Σ deg(z))
TI
#EA
and therefore EzEa deg(z) S n deBavg and the maximum number of checks we need to perform is (minn( (anindaagg k) n2).
Sampling data points according to contribution. We define the contribution of a data point x with respect to C' f(z C) & wx(z). A(o(z), and the contribution of set of data points S S X with respect to C as ()
far C). Normalised by COST (X, C), the contribution of
each data point follows the D -ampling distribution and S(S.C) is the probability of sampling point from set S S X.
f(X,C)
Suppose we have nested sets S1 c S2 C S3 C... C. Sm X. For any x E S1, we have that C(r,C) f(Sm, C) f(Sm-11 f(r [(X,C) ((X,C) C) I(S1,C)
Pr (ar is sampled]
Due to this decomposition, we can use sampling tree T to efficiently sample proportional to contributions and update contributions as points are added C.
The root node of T corresponds to the entire set X and stores the total contribution f(X, C). Sibling nodes represent partition of the set their parent corresponds to and store their respective contributions. Leaf nodes store the data points they represent, their contributions, and weights.
To sample data point proportional to contribution, we start the root node of and recursively sample child node with probability equal to the child's contribution divided by the parent's 's con- tribution until we reach a leaf, corresponding to the sampled data point, From equation 4 this is equivalent to sampling points porportional to contribution, and therefore the distribution required by D2 sassamning..
Updating contributions efficiently. We can update the contributions stored in T efficiently each time a point is added to C. Suppose we find a neighbouring data point x of y such that A (xx, y) is less than the stored value of (xx. C). Then subtract the difference in contribution from every internal node along the path from the leaf node to the root. If T' is balanced, then the cost to repair T' after each check is (log(n))). The full algorithm is given in Algorithm 2 Since x² can be found in time O(n), T is constructed in time (n). and the cost of sampling i points and repairing T is O(min (doug: k) log(n)), the overall running time of Algorithm is (minndavay k) n)).
the stored value of A A(x, C) be A(x, y) and
Correctness. We start with the following useful definition:
Definition 5 ((a, 3) -ppppoooinntoo for weighted kernel k-means), Let OPT optimal objective of equation 2 We call a subset H an (a, (app))aapro solution for kernel k-means if [S] = ak and cOST Th (X. (X,
(X, 6) denote the
D2 sammmining returns an (0(1), (+log(()))approoiiaat approximmae solution for k-means with high probability (Jiang et al. 2024); adding the extra point x has negligible effect. The proof follows that of Lemma 3.1 in Arthur & Vassilvitskii (007)) with the only difference being the equality of Lemma 3.1 becomes an inequality. We summarise the result in the following lemma:
5

---

Published as a conference paper at ICLR 2025
Lemma 4.1. Given kernel matrix K corresponding dataset X, Algorithm 2 returns (O(1), O(log)))))))ooo (oop,,ooo approxxmxxinntio for kernel k-means with high probability and running time (min (minn(dvvg k) n).
By the analysis of Jiang et al. 2024), this immediately implies the following kernel coreset result: Lemma 4.2. Given kernel matrix K corresponding dataset X, Algorithm 4 using Algorithm for D2 samplinnng returns an e-coreset with high probability with size O and running time Ommin(dea (daugs k) n)).
Algorithm 2 FASTD* FASTD'-SAMPLING SAMPLING
1: Input: Dataset with [X] = n, positive definite matrix K Ruxn W E Bi, k N
2: T COONSTRUCTT(X, K, W)
> Algorithm
3: x² arg min (0(x), ((x))
4: draw x E X uniformly at random
5: C' (6(z),((x")
6: REPAIR(E", ,T)
b Algorithm
7: for = to & do
8: #+-SAMPLEPOINT(T
4 Algorithm
9: C-(
10: REPAIR(Z,T)
end for
12: return C
5 CORESET SPECTRAL CLUSTERING
In this section we present our Coreset Spectral Clustering (CSC) algorithm. An intuitive illustration is given in Figure [ Given an input graph, we first extract the corresponding weighted kernel k-means problem via the equivalence to the normalised cut problem, and then construct an s-coreset. Following this, again via the equivalence, graph to get the coreset partition. Finally, we label the rest of the data by considering kernel distances to the implied centers induced by the coreset graph partition. Our main contribution is summarised in Theorem I which states that coreset graphs preserve normalised cuts from the original graph.
solve the corresponding normalised cut problem on the coreset
Input graph
Coreset graph
Coresel partition II
Spectral clustering
Graph space
Construct corcaet
Kemel space
Equivalent kemel k-meuns problem
Reweighted coresct
Implied ceuters
Figure Sketch the Coreset Spectral Clustering Algorithm.

---

Published as a conference paper at ICLR 2025
Equivalence between normalised cut and kernel k-means. First recall that the normalised cut problem and the kernel k-means problem can both be written as the following trace optimisation problems up constant (Dhillon et al., 2004):
Normalised Cut
Weighted Kernel k-means
min
Tr(D-1A) -
min
Tr(WK) - TTYY"
s.t.
X [0,1)uxR,
X {0, 1,xx,,
X1: Ln,
X1 = Im
Z = D
Y WX
(5)
In the above optimisation problems (5 A and D are the adjacency and degree matrices corresponding to some graph G, K a kernel matrix such that K;, (o(x;), ((xz)))((z)); and W is diagonal matrix with Wi wxxz). Crucially, these problems are equivalent. Indeed substituting K Dー ADD! and W = D shows that any normalised cut problem can be written as a kernel k-means problem; substituting D W and A WWW shows the reverse. The only wrinkle with translating one to the other is that K must be positive semi-definite. If A is not positive semi-definite then we can add multiple of D D 1--lA AD-1 to make it so while preserving the optimal partitioning (Dhillon
et al. 2007).
Coreset graphs. The first and third transitions in Figure are due to equivalence (5). The second transition is simply via constructing coreset, and the fourth is by executing spectral clustering, The crux our proof is the fifth transition. Specifically, it is not clear how to translate the partition of the coreset (in graph space) to solution for the entire input graph. The main difficulty with using coresets for the normalised cut problem is that there is no notion of "cluster centers" on graphs. To overcome this, go back to kernel space (the fifth transition) and label the entire input there. For the rest of the section we prove that this approach preserves the approximation of spectral clustering on the coreset for the entire graph.
To help with this, we will use the following lemma, whose proof is deferred to Appendix
Lemma 5.1 (Adapted from (Kanungo al. 20022). Let S a finite set of points Hilbert space H. and w H. + I_ be the weight of each point. Let c(S) (Eaes w(x)x) / (Eres w(x) be the centroid of S. Then, it holds for any z E H that
Σ w(x) || =112 = Σ PES
(((x) || c(S))]]] + [[]](((S) - =112 Σ w(x).
FES
FES
Intuitively, the above lemma allows us to draw a connection between the centroids of the coreset partition (in kernel space) and the centroids of the full partition, where every node is assigned to its closest coreset center. We will also make use of the following definitions which allow us to use k-partitions instead of set membership matrices in
1. Let G (V, be graph vertices with adjacency matrix A and degree matrix D, and let
II be k-pan k-partition of V. Then define NCI. & Tr(D-1 A) DT(Z"D--//AA 1 Z) to be the objective of the trace minimisation version of the normalised cut problem in (5), where 11/2 (xx 11/2 and {0, 1 the unique set membership matrix on V corresponding to II.
2. For any k-partition of X, II, further define COST ( (II) (
to be the objective of the trace minimisation version of the weighted kernel k-means problem in 5). where Y = 1/12 2/1122((X") x(x"") TTT.WW Wx) 11/2 and X E {0, 1 is the unique set membership matrix X corresponding IT.
Translating the objective of a k-partition with respect to the normalised cut problem to the objective of a set of centres with respect to the kemel k-means objective straightforward. Dhillon al. (2004) show that for any k-partition Il {TT ) we have COST .e. (II) COST (V, cg (II), AD-1 We De. we diag(Wo) and & V H is map such that
where KG
7

---

Published as a conference paper at ICLR 2025
(0(2), o(u) (o for all 2, V. For completeness we include simpler derivation in
Lemma B.1 This implies that D (II) = COST (II) = COST (V, c (II)
The other direction is more difficult; given an arbitrary set of k centers S = {&,} C H, we would like to construct k- k-partition II' { of V such that
NCA, = wo, (TT) = COST w (V, wa (TT') = COST (V,
In general it may not be possible to choose II' such that COST (V, o (II') COST (V,S). However, the inequality COST (V, c (II') COST SV does hold by choosing II' such that a E TY iff (((()),)) = ( 8j), breaking ties arbitrarily. This a consequence of Lemma 5.1 which tells us that moving the center of each n' to their centroids can only reduce the weighted kernel k-means objective. This will be sufficient to prove our main result.
Given graph G with adjacency matrix and degree matrix D, let O.TNCA.D(C denote the optimal value of the normalised cut problem (5) on G. We can now state our main result:
Theorem 1. Given a graph G (V, E) and a-approximation algorithm for the normalised
problem with l clusters ()) SPESTRALCLUSSTERING Algorithm returns a k-partition of V such that
AC Do (II') S a 1+
The running time of Algorithm is the of the running time of the 8-coreset algorithm, OPECTRAI.CL.USTERING. and labelling VP
Algorithm 3 CORESET SPECTRAL CLUSTERING
1: Input: Graph G (V, E), l with adjacency matrix Ag and degree matrix De
2: Ka, WG +- D AcDaa DG
3: V', WH f- An e-coreset for kernel k-means on (V, KG Wa)
4: AE < WyK((V))z
5: II < EEECCRAALLLUSTERING(AA.. *K(V)) is the principle submatrix of K with respect to V
> ---pattttoon {
6: II' < partition assigning each E V to the closest coreset centroid in city (II).
7: return II'
To prove Theorem we show that the objective of any partition of V is preserved on V (Lemma B.2 and the objective of any optimal partition of V is preserved on V (Lemma B.3 We defer their statements and proofs to Appendix B
Proof of Theorem 1 Let = { be an optimal k-partition of such that NC NCA., (2) Op Do (k) and let E' {o)} be the k-partition of V' such that x E of iff A(o(z), ol (E)) (()(x), e (a;)), breaking ties arbitrarily. Then we have
DD NCAc (1I') < NC An Da (II) <
1
a NCA ( Du (E') S a 1-
NC (2),
1 1+
1-8
where the first inequality follows from Lemma B.2, the second holds because NC (II)
aPPTNC A (k) S aNCAg, (E'), and the third follows from Lemma B.3
6 EXPERIMENTS
We perform three experiments to compare our coreset algorithm against the naive method, and secondly, to compare our Coreset Spectral Clustering algorithm to coreset kernel k-means and the skleam implementation of spectral clustering. Experiments 2690 system with 384GB of RAM. Our implementation was written in Rust using Facr El Kazdadi
performed on dual Intel Xcon E5-
TThis can be done efficiently, exploiting sparsity, by first computing the norms of cach ch "A user friendly python wrapper is available here: g thtbb.com//eeeuuuurrrr//o/oo
8

---

Published as a conference paper at ICLR 2025
6.1 CORESET RUNNING TIME COMPARISON
We compare the running time of our improved coreset construction with that of Jiang et al. (2024).
In partieular, we compare the running time of Algorithm using Algorithm 2 (our method) for D2 Da-samlling against Algorithm 4 jusing Algorithm Jiang et al. 2024) for D -ammlling We test these algorithms on the following three large graph datasets from the SuiteSparse Matrix Collection Davis & Hu 2011).
Friendster:
A snapshot of the social media network with 65M nodes, 1.8B edges, and 5000
labeled overlapping communities.
LiveJournal: A snapshot of the blogging network with 4M nodes, 34M edges, and 5000 labeled overlapping communities.
wiki-topeats: A snapshot of the Wikipedia hyperlink graph with 2M nodes, 28M edges, and 17K overlapping page categories.
We preprocess each graph to be undirected and construct K D- and W D from the corresponding adjacency and degree matrices. We measure the time it takes each method to construct 100K point coreset for the weighted kernel k-means problem on K and W while varying the number of clusters passed to the D'-samplig routines. Following Jiang et al. (2024), we only do one iteration of importance sampling in Algorithm FigureZcontfn confirms our method significantly faster than the previous method, This matches our expectations based on the theoretical results since each graph very sparse.
wikipedia
Iveicurnal
friendster
10a
10
132
107
soconds (log Gcale)
seconds (10g scale)
10a
(lgg
20*
10
100
20P
102
10a
10a
10"1
10-1
3000
2000
3000
8000
5000
0
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Clusters
Clusters
Clusters
Jong el al. coresel construction
Our coresel construction
Figure 2: Running time comparison of coreset construction using either Algorithm O et al..
2024 or Algorithm 2 for D2-sampling. Shaded regions denote 1 standard deviation over 10 runs.
6.2 CLUSTERING WORLD DATASETS
We evaluate the clustering performance of our Coreset Spectral Clustering (CSC) algorithm using our faster coreset construction, the size of the coreset varies. We test the effect of using both the sklearn spectral clustering algorithm and the faster method of Macgregor (2023) to cluster the coreset graphs. We compare against the sklear implementation of Spectral Clustering (SC) and coreset kernel k-means using the naive coreset construction (Jiang et al.) 2024). We measure each algorithm's 's running time and Adjusted Rand Index (ART) (Rand) 1971) on nearest neighbour graphs of the following datasets:
MNIST: A labelled collection of 70,000 28x28 pixel images of handwritten digits (Lecun et al. 1998).
PenDigits: 10,992 labeled instances of 2D pen movements covering the digits 0-9, each represented with 16 numerical features. (Anguita et al. (003)).
HAR: A collection 10,299 labeled smartphone sensor readings capturing six human movements, each represented as 561 numerical features (Anguita et al. 2013).
9

---

Published as a conference paper at ICLR 2025
Letter: A labelled collection of 20,000 instances of handwritten alphabetic english characters, represented as 16 numerical features (Frey & Slate 1991).
Figure 3 shows the results for the HAR dataset, and demonstrates that the coreset methods much faster than SC and both variants of CSC perform as well as SC using a coreset less than 5% the size of the original dataset, in fraction of second. While increasing coreset size does help coreset kernel k-means, it struggles to escape local optima, reducing performance. The results for the other datasets are in Appendix
Running time
Normalised cut
3.2
10P
Normalieed mii
poconds
335
127
235
1500
300
300
1950 Coreset size
Coreset size
Coreset size
Coreset Spectral Clustering
Fast Coreset Spectral Clustering
Coreset Kernel k-means
Spectral Clustering ig
Figure 3:
Running time, ARI, and Normalised cut each algorithm on a 200-nearest neighbour graph of the HAR dataset. Shaded regions denote 1 standard deviation over 20 runs.
6.3 CLUSTERING SYNTHETIC GRAPHS WITH MANY CLUSTERS
Finally, we push CSC the limit by tasking cluster the stochastic block model (Abbe 2018 when the number of clusters is proportional to the number of nodes. We sample graphs where the number of nodes in each cluster is 1000, the probability of edge between two nodes in the same cluster is 0.5 and the probability of an edge between two nodes from different clusters is 0.001/K //k. We report the ARI of the coreset graph nodes instead of the full graph because the running time is otherwise dominated by labelling. We only consider the variant of CSC using the method of Macgregor (2023) as computing hundreds of eigenvectors becomes prohibitively expensive. The coresct size set to be 1% the size of the input graph, implying that each cluster has average of 10 nodes in the coreset graph. Figure 4 shows a gradual decline in performance of fast CSC as I increases, probably due to fluctuations the number of nodes the coreset samples per cluster. Nevertheless, still achieves an ARI of 0.5 in less than seconds on a graph with 250K nodes and 250 clusters. On the other hand, local optima render coreset kernel k-means useless after 50 clusters.
Running time
1.0
2.
ARI
0.6
0.4
0.0
50
100
150
200
250
100
150
200
250
Number of clusters
Number clusters
Coreset Spectral Clustering
means
Figure 4: Running time and ARI of each algorithm on the stochastic block model with clusters of size 1000, p = 1/2, q 0.001/k /k with coreset size of 1.. Shaded regions denote standard deviation over 20 runs.
10

---

Published as a conference paper at ICLR 2025
7 ACKNOWLEDGMENTS
The second author was supported by the following research grants: KAKENHI 21K17703, JST ASPIRE JPMJAP2302 and JST CRONOS Japan Grant Number JPMJCS24K2. The last author was supported by an EPSRC Early Career Fellowship (EP/T00729X/1).
REFERENCES
Emmanuel Abbe. Community detection and stochastic block models: recent developments. Journal of Machine Learning Research, 18(17)):1-86, 2018.
Mashaan Alshammari, John Stavrakakis, and Masahiro Takatsuka. Refining k-nearest neighbor graph for computationally efficient spectral clustering. Pattern Recognition, 114, 2021.
D. Anguita, Alessandro Ghio, L. Oneto, Xavier Parra, and Jorge Luis Reyes-Ortiz. A public domain dataset for human activity recognition using smartphones. In The European Symposium on Artificial Neural Networks, 2013.
David Arthur and Sergei Vassilvitskii.. k-means++: the advantages of careful seeding. In 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '07). pp. 1027-1035, 2007.
Olivier Bachem, Mario Lucic, S Hamed Hassani, and Andreas Krause. Approximate k-means++ in sublinear time. In the AAAI conference on artificial intelligence, volume 30, 2016.
Vladimir Braverman. Shaofeng H-C Jiang. Robert Krauthgamer, and Xuan Wu. Coresets for clustering in excluded-minor graphs and beyond. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA (21). pp. 2679-2696, 2021.
Radha Chitta, Rong Jin, and Anil K Jain. Efficient kemnl clustering using random fourier features. In 2012
IEEE 12th International Conference on Data Mining, pp. 161-170, 2012.
Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fatt Christian Sohler, and Ola Svensson. Fast and accurate k-means++ rejection sampling. In 33rd Advances Neural Information Processing Systems (NeurIPS'20), 2020.
Timothy Davis and Yifan Hu. The university of florida sparse matrix collection. ACM Transactions on Mathematical Software, 38(1), 2011.
Inderjit S. Dhillon, Yuqiang Guan, and Brian Kulis. Kernel k-means: spectral clustering and normalized cuts. In 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD' 04), pp- 551-556, 2004.
Inderjit S. Dhillon, Yuqiang Guan, and Brian Kulis. Weighted graph cuts without eigenvectors a multilevel approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(1 1957, 2007.
Sarah El Kazdadi. facr-rs. URL/pttps:///gthuus ccm/ waw.s/aaaa--uoooo//arerrerr
MIT License.
Peter W Frey and David J Slate. Letter recognition using holland-style adaptive classifiers. Machine learning, 6: 161-182, 1991.
Mehmet Gönen and Adam A Margolin. Localized data fusion for kernel k-means clustering with application cancer biology. In 27th Advances Neural Information Processing Systems (NeurIPS 14), 2014.
Sariel Har-Peled and Soham Mazumdar. On coresets for k-meaas and k-median clustering. In 36th Annual ACM Symposium on Theory of Computing (STOC '04), pp. 291-300, 2004.
Ben Harwood and Tom Drummond, Fanng: Fast approximate nearest neighbour graphs. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR'16), 16), 2016.
Lingxiao Huang and Nisheeth K. Vishnoi. Coresets for clustering in euclidean spaces: importance sampling nearly optimal. In 52nd Annual ACM SIGACT Symposium Theory of Computing (STOC'20), pp. [416-1429, 2020.
Shaofeng H.-C Jiang, Robert Krauthgamer, Jianing Lou, and Yubo Zhang Coresets for kernel clustering. Machine Learning, (3318):58115900 2024.
Ben Jourdan and Gregory Schwartzman. Mini-hatch kernel k-means, 2024. URL http::ttp///t... /ttp:::://xxvvvvr/// abs /241 O. 05902
11

---

Published as a conference paper at ICLR 2025
Tapas Kanungo. David M Mount, Nathan S Netanyahu, Christine Piatko, Ruth Silverman. and Angela Y Wu. local scarch approximation algorithm for k-means clustering. 18th Annual Symposium on Computational Geometry (SoCG 022, pp. 10-18, 2002.
Chia-Tung Kuo, Peter Walker, Owen Carmichael, and Ian Davidson. Spectral clustering for medical imaging. In 2014 IEEE International Conference on Data Mining, pp. 887-892, 2014.
Lecun, L. Bottou, Bengio, and P. Haffner. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 86(11)22278 2324, 1998.
Peter Macgregor. Fast and simple spectral clustering in theory and practice. In 36th Advances in Neural Information Processing Systems (NeurIPS' 23), 2023.
Peter Macgregor and Sun. Fast approximation similarity graphs with kernel density estimation, In 36th Advances in Neural Information Processing Systems (NeurIPS 2023.
Yu A Malkov and Dmitry Yashunin. Efficient robust approximate nearest neighbor search using hicrarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(():824 836, 2018.
Cameron Musco and Christopher Musco. Recursive sampling for the nystrom method. 30th Advances in Neural Information Processing Systems (NeurIPS' 17). 2017.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825 2830, 2011.
Richard Peng, He Sun, and Luca Zanetti. Partitioning well-clustered graphs: Spectral clustering works! SIAM
Journal Computing, 46(2):710 1007710-73,,,, 2017.
William M Rand. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association, 66(336):846-88 8500 1971.
Daniel A Spielman and Shang- Hua Teng. Spectral sparsification of graphs. SIAM Journal on Computing, 40(4): 981 1025, 2011.
He Sun and Luca Zanetti. Distributed graph clustering and sparsification. ACM Transactions Parullel Computing, 6(3), 2019.
Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17:395 416, 2007.
Shusen Wang, Alex Gittens, and Michael W Mahoney. Scalable kernel k-means clustering with nystrom approximation: Relative-error bounds. Journal of Machine Learning Research, 20(12):1-49, 2019.
Scott White and Padhraic Smyth. A spectral clustering approach to finding communities in graphs. In 2005
SIAM International Conference Data Mining (SDM). pp. 274-285, 2005.
Than-Kuen Wong and Malcolm C. Easton. An efficient method for weighted sampling without replacement. SIAM Journal on Computing, 91):111-113, 1980.
12

---

Published as a conference paper at ICLR 2025
A FURTHER EXPERIMENTS ON WORLD DATASETS
In this section, we report the experimental results omitted from Section 6.2
Running time
ARI
Normalised cut
06
10P
Normalised Iinaalisedd cut
seconds
ARR
232
2.4
2.2
00
15:0
2008
3000
1558
2000
Coreset size
Coreset size
Coreset size
Coreset Spectral Clustering
Fast Coreset Spectral Clustering
Coreset Kernel k-means
Spectral Cluster ing
Figure 5: Running time, ARI, and Normalised cut of each algorithm on a 250-nearest neighbour graph of the PenDigits dataset coreset size varies.
Running time
ARI
Normalised cut
0.54
100
Normalised cut
0:300
seconds
0..0
C275
0.03
0:20
0.44
0.15
0.100
1008
2000
2000
2000
2000
Coreset size
Coreset size
Coreset size
Coreset Spectral Llustering
bast Coresat Spectral Clustering
Coreset Kernel k-maans
Spectral Clustering mg
Figure 6: Running time, ARI, and Normalised cut of each algorithm on a 300- 300-ncarest neighbour graph of the Letter dataset coreset size varies.
Running time
ARI
Narmalised cut
0.-
0.35
Normalised cut
scconds
0.5
0.30
013
1560
2000
1000
2000
303C
200
1300
2000
Careset size
Careset size
Coreset size
Coreset Spectral Clustering
Rost Coreset Spectral Clustering
Coreset Kernel k-means
Figure 7: Running time, ARI, and Normalised cut each algorithm on a 500-nearest neighbour graph of the MNIST dataset coreset size varies. Skleam spectral clustering not included because it took too long.
13

---

Published as a conference paper at ICLR 2025
B SUPPLEMENTARY LEMMAS AND PROOFS
In this section we provide the proofs omitted from Section
Proof of Lemma 5.1
w(u) 2| 2||²
Σ w())(u 2,
Σ w(u) ((u-c(s) (c(S)- - -:). (
((u- (()) (c(S) - =))
MES
Σ w(u)
[[s)| + (()), - 2) [|((s) =ll²)
wES
Σ w(u) lu--((]] +2 c(S) 2, Σ all)
- -
[|5]] =11² E w(x)
WES
MES
z68
Σ [[=x) cS) ||((S) =||² ES
Σ w(x)
#s
where last step follows from the fact that c(S) is the weighted centroid of S, so Emes (" - -c()) = 0.
L
Lemma B.1 (Kemel k-means objective equivalence). Given a set of objects X. : + R., X - Ryo and Φ X + H. satisfying equation for any l-partition 11 { of X, holds that
C, (II) COST (=1),
(6)
Eatny w(a)o(o)
where my
and Diag(w).
Moer, w(b)
Proof. Let X (0, 1)ax* be the unique set membership matrix corresponding to IT; that is, X1g = 1, and ((i,)) iff xı E n,. Therefore X W Diag(s1...., where s; Emex, w(e). Expanding right hand side of equation we have
cost (m1))=))
Σ j=l nEN,
w(a m5l1
Σ Σ w(a) (o(a), (((a))((()), a(a)) - 2((((a). m2) + (my, (my, my))
(7)
Notice that Σ₁=1 EnEr, (d(a) )(a))
j=1 Ener, Ka.) Tr(WK) K) since II is partition of X. Expanding the other terms of equation 7 for the jth cluster, find they multiples of the same quantity:
Σラ=
((aa)) (b))
((a)(o(a), m,)
Σ Σ uEN
Exeny w(c)
aEw
Eoer, EcEr, (()))
w(a)a(t)(((a))00 6(0))
Σ w(a)(m;;mj)) = Σ w(a) aE
Eeer, w(c)
(Eden, w(d)
GET,
acry bEny
Finally, show that these quantities for each cluster are the diagonal entries of the matrix X WKWX -x)-1 w
[X"WXXX(X""X"" 11 -XW
'1ss
Σ
E Xay XayXay (W]]o.))
Σ EnEr, w(b)
1
WKW]aa
Eaen, w(a)
aEmy beay
w(ajw(b)(o(a))
Σ
Eeer, w(c)
aemy bEny
14

---

Published as a conference paper at ICLR 2025
Thus CO {m,)) T<(WK) Tr(X' TIXX'WXWXXX'WX) COSTX.W
Lemma B.2. For any k-partition 11 {Tz)}== of we have that
NCAc.Do (II') 1- NCA NC (II)
1-
where II' (z]) is the k-partition of such that m/ A(d(x), (T)) A(0(x),cl (mi)).
breaking ties arbitrarily.
Proof of Lemma 8.2 We have NCAn.DD (IT) = COSTRH. (TI) COST wy (V' c (TJ). Since V and
wH constitute an e-coreset, we have that COST (V, oen (1I) I COST (V', Gwn (11).. Then by the definition of and Lemma 5.1 COST (V, Seg (II')) & COST (V, Goy (I)). Since NCA,, (II)
Co (TT') = COST wa (V, cee (TT'), the claim follows.
Lemma B.3. Let fos )5-2 be an optimal k-partition of V such that NCAG. (2) OPTNCAAN (k). Then
NCAH DH (E)) (1 Eo
where 2' {o]} is the k-partition of V such that æ E of ifl A(o(x)), eeo ((ox)).co (o,))
breaking ties arbitrarily.
B.3 We have that NC (2) = COST (V, (V,cua (E)). (E)). Since V and wy constitute an e-coreset, we have that COST wn (V', ch (E)) S (1 E)COST (V, ch
Proof of Lemma
o (E)). From the definition of E'
Lemma 5.1 we have NCAg (x5) = COST (V', cl (E")) S COST (V', e (E.)). claim follows.
C
ALGORITHMS
this section we provide the coreset kernel k-means algorithm given by Jiang et al. (2024) along with our subroutines for Algorithm 2
C.I
CORESET KERNEL M-MSS ALGORITHMS (JIANG ET AL. 2024
Algorithm 4 Constructing an e-coreset for kernel k-means on dataset X with kernel K (Jiang et al.
2024)
1: Input: Xo + X, +- 0
2: repeat
i i and E; + e/olg || 1/4
log (.) is the ith iterated logarithm. & Algorithm
4:
X, < IMPORTANCE- SAMEE-SAMPIIGGGG X; 1,,,,
5: until ||X;|] does not decrease compared ||,
6: return X;
Algorithm 5 Importance-SSmplinngh. (Jiang al. 2024)
1: Input: X,
2: Let C* -'--sampling(X))
Algorithm orr Algorithm 2 (our faster algorithm)
3: for r X do
4: Oz ((,.)) "x(C)
5: end for
6: for E X do
ox 7: Pe f Eyex T
8: end for
(ol x| iid. samples from X. using probabilities (p=)xex
9: Draw N
10: Let D be the sampled set; for each r E D let wp(x)
+ wx (r)
N
11: return weighted set D
15

---

end if Published as a conference paper at ICLR 2025
C.2 FAST D SAMPLING SUBROUTINES
Algorithm 6 CONSTRUCTT
Input: X s.t. [X] K S++ W E Ry
2: current Dereat__eveeee []
3: for do
4: leaft- a leaf node corresponding to x with attribute A (0(x), +
5: current_level. push (leaf)
6: end for
7: while current_ len(> 1 do
8:
NextLevel
for 2 1svel. - do
9:
10:
left_child + wurrent_eeeeeellleee right_child ceapefccure__ttuee [azrent_leveii+11] internal an internal node with left left_child child and right_child child as their spective children and attribute contributi on equal to the sum of the contribution of its children.
11:
12:
13:
next_level. push (internal)
end for
15: if' "'cuuren__levv (en is odd then
next_level push capuuret__eevvee poureet__eevee ()n ))]) 17: end if
current_lever < next_leve
19:
end while
20: return current level [1]
Algorithm 7 REPAIR(:.I)
1: Let L the leaf node corresponding to æ
2: delta_di fference L.A
3: L.A 4 0
4: for Internal node in the path from I. to the root of do
5:
I.contiiution + w.contribbuuuu ion - delta delta_ difference x w(z)
6: end for
7: for in (xx) do
8: Let I' be the leaf node corresponding y
9: if A(x, v) < L'.A then
delta_differee
+- L'AA A(x,y)
11:
L.A + Azx,y)
12:
for Internal node / in the path from L' to the root of do
13:
I.contributin delta di fference w(y)
14:
end for
15:
16:
end for
Algorithm 8 SAMPLEPOINT
1: Input: T
2: Let / be the root of T.
3: while I an internal node do
4: Let C1 and C2 be the children of L.
5: child + Select C₁ or C2 with probabilities proportional to Ci.contrbbut ion and If I only has one child, sample with probability 1.
Cocoontribution
6: + child
7: end while
8: return the data point associated with I.
16


Reviews:
[{"review_id": "yeiy0h87La", "reviewer": "Reviewer_Gaz4", "summary": "The paper develops new tools in coreset construction merging ideas from two different problems: one is the coresets for k-means and kernel k-means clsutering and the other is spectral clustering, hence the name Coreset Spectral Clustering of the paper.\n\nThe main result is to give an approximation algorithm for the problem of normalized cut based on coresets. Specifically, they can approximately solve the problem on the coreset graph and prove that this is enough to get a reasonable approximation on the original input graph. The authors also perform experiments and demonstrate that their approach leads to asymptotically faster results on large real-world graphs with many clusters beating prior coreset kernel k-means approaches for sparse kernels.\n\nThe second result of the paper is to speed up the running time of the current state-of-the-art coreset algorithm for the problem of kernel k-means on sparse kernels, where the speed up depends on the average degree of the graph.", "questions": "-The authors say their speed up is from nk to nd where d is the average degree in some sense. In the abstract this is a bit confusing: but is this necessarily a speedup; what if k is relatively small but the average degree in the kernel matrix leads to more non-zero entries? Perhaps this is good to clarify early on as you do later in the main body cause the reader might be confused.\n\n-While reading the paper, many ideas used in the analysis are actually coming from (and are cited) from the prior work by Jiang et al. I was curious if the authors could elaborate on what ideas were the novel part of the paper?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-nice idea to rely on kernel sparsity that yields the first coreset construction for kernel spaces and leads to speed up which is especially useful for large graphs with many clusters.\n\n-the two main protagonists here which are spectral clustering and kernel k-means are studied often separately, and I view this approach of merging ideas/techniques interesting.\n\n-the coreset spectral clustering algorithm is interesting and gives a clean result statement: an \\alpha-approximation of the normalized cut problem on the coreset graph will  in fact give an O(\\alpha)-approximation of the normalized cut problem on the original graph. To me this is a very useful and interesting statement as it can be used as a black box and lead to practical results as well.", "weaknesses": "-novely: while the paper draws inspiration and combines cleverly prior works on normalized cut, kernel clustering and coresets, I wanted to point out that the current paper seems to heavily rely on ideas and techniques that were developed before. Of course the authors had to cleverly combine them in order to get the clean statement as their main result. I also read parts of the technical proofs in the appendix, and I believe that in terms of techniques the paper is a bit weak. Perhaps the authors could elaborate on what crucial ideas in terms of techniques were the novel aspects of this work. Specifically the analysis of Jiang et al. seems to be doing the heavy lifting in many parts of the paper, and conditioned on that  paper, I believe  the current technical contribution appears to be slightly less solid. This is my only concern about the paper, otherwise I do like the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sXldteoWoz", "reviewer": "Reviewer_8Sqn", "summary": "The paper leverages the equivalence between kernel kmeans and spectral\nclustering to improve spectral clustering. As a secondary result they also\nimprove coreset construction for sparse matrices.\n\nThe equivalence between kernel kmeans and spectral clustering is well known.\nIt is, therefore, natural to expect improvements in kernel kmeans\nalgorithms to produce better spectral clustering. Results along this line\nwere recently described by Jiang24, performing kernel kmeans on\nweighted sampled data (coreset).\n\nThe paper argues that improving coresets do not necessarily lead to\nimproved spectral clustering because the kernel kmeans typically gets\nstuck in a local minimum. By contrast, spectral clustering computes\nan approximation to the global optimum, and does not gets stuck in local\nminima.\n\nUsing this key observation the authors propose a novel framework of going\nback and forth between \nthe graph and the points in high dimensional space that are represented\nby the coreset. This improves the speed, but not the quality of the clustering \n(as measured by NCUT). The paper shows that the reduction in quality\nis linear.", "questions": "The result: Why are the derivation and experiments discussing only NCUT?\nThe equivalence of Dhillon04 was extended in Dhillon07 to other criteria,\nin particular RatioCut. It should also apply to the newer stochastic box model.\n\n\nExperimental results: why is there no comparison of the NCUT values\nthat were obtained in the experiments? The current evaluation is\nin terms of ARI, but this is not what the algorithms attempt to maximize.", "limitations": "", "rating": 10, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is very nicely written. It describes a result that appear interesting\nin theory and useful in practice.", "weaknesses": "An important side result is the fast construction of a coreset that can be used\nfor kernel k-means clustering. The improvement comes from a fast\n$D^2$ sampling technique. I believe that there are other, competitive\nfast sampling techniques and I was missing a comparison.\nHere is an example:\n\nChib and Greenberg, 1995, Understanding the Metropolis-Hastings algorithm,\nThe American Statistician.\n\n\nIn addition please see the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "d5D22TL28d", "reviewer": "Reviewer_CV9w", "summary": "This paper presents an algorithm coreset spectral clustering algorithm for k-means clustering. This is done by first converting the input graph into a k-means problem instance, constructing and $\\epsilon$-coreset for this instance, then solving the spectral clustering problem on the reduced graph. A second contribution is an algorithm for fast $D^2$-sampling utilized in coreset construction, which results in an coreset construction algorithm with running time $\\widetilde{O}(n d_{avg})$.", "questions": "Please address the concern that I raised in the weaknesses section.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The contribution of the paper is solid, with the main idea being combining the approaches of coreset construction and spectral clustering. The utilization of sparsity to improve the running time of clustering algorithm is also well-executed.\n- The presentation is overall excellent, with all of the contributions stated clearly. Schemes and easy-to-read pseudocode are very helpful with understanding the approach.\n- The experimental section is detailed and well-organised.", "weaknesses": "It is somewhat unclear how often it is desired to solve spectral clustering on sparse data, or whether settings of interest have $d_{avg} < k$. I would like the authors to add an overview on how clustering methods are used in the empirical research, for example social network analysis, in the introduction or related work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eRUjrGCIOJ", "reviewer": "Reviewer_in36", "summary": "The paper tackles the challenges of clustering large, sparse datasets, where traditional spectral clustering methods can be computationally demanding. While spectral clustering is widely used for identifying non-linear cluster boundaries, its dependence on dense similarity matrices restricts scalability, particularly when dealing with numerous clusters. The authors introduce Coreset Spectral Clustering (CSC), a method that merges the efficiency of coreset sampling with the accuracy of spectral clustering, achieving a substantial speedup while maintaining clustering precision.", "questions": "See weakness.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- CSC is optimized for sparse graphs, where the sparsity structure significantly reduces both computation and memory usage. By using a small, representative subset of data (the coreset), CSC scales well with data size and can handle graphs with millions of nodes and thousands of clusters. This scalability makes CSC suitable for large datasets in social networks, biological clustering, and sensor network analysis, where traditional methods would struggle.\n\n- Standard spectral clustering can become infeasible with large, dense similarity matrices due to the high demands on computation and memory. CSC addresses this by working with a sparse kernel matrix and clustering only on the coreset, significantly reducing matrix size and computational cost. This efficiency enables CSC to process large datasets on standard hardware, which would otherwise require extensive resources for traditional spectral clustering.\n\n- A smaller coreset speeds up computation, while a larger coreset captures more nuances in the data structure. This adaptability is useful for applications with specific accuracy or runtime needs, making CSC versatile across different types of data and clustering goals.", "weaknesses": "- The accuracy of CSC’s clustering largely depends on the representativeness of the coreset. To achieve high-quality clusters, the coreset need to accurately capture key structural and distributional aspects of the dataset. In datasets with uneven distributions or subtle data patterns, it could be difficult to create a coreset that fully represents the original data, and even minor inaccuracies could impact clustering results.\n\n- CSC relies on an initial similarity or nearest-neighbor graph, and parameters such as the number of neighbors (k) or distance threshold (ϵ) can significantly affect clustering performance. Choosing suboptimal values for these parameters may lead to an inaccurate initial graph structure, impacting the quality of the final clusters.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YzvEVpE3re", "reviewer": "Reviewer_bKLj", "summary": "This paper proposes a refined algorithm of constructing a coreset for kernel k-means problem. They improves the time complexity from $\\tilde{O}(nk)$ [Jiang et al. ML' 24] to $\\tilde{O}(nd_{avg})$, where $d_{avg}$ is the average number of neighbors of a single vertex on the graph defined by the given similarity matrix. They also showed how to use their technique to improve spectral clustering and obtain a approximate solution for normalized cut problem. The experiments are designed to support their theoretical results.", "questions": "1. In the experimental part, the ARI performance of yours is much better than the green baseline (which is the method of [Jiang et al. ML' 24]). But I think your result is mainly based on the green baseline and you improve their running time. So it makes sense that your method is faster. But why your ARI is so much better than the green baseline?\n2. In the experimental part, you mention that you use the nearest neighbor graphs of MNIST. How to construct such a graph on MNIST? Is it a nearest neighbor graphs based on Euclidean distance?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The proposed technique of constructing a coreset is quite useful when k is large and the similarity is sufficiently sparse.", "weaknesses": "1. Limited contribution. The proposed method highly depends on the former work [Jiang et al. ML' 24]. And their claimed improvements seems trivial. Theorem 1 is also easy to obtain. \n2. This paper assumes that the similarity matrix is sparse, which means a vertex has only few neighbors. So when a vertex is sampled, only its neighbors ($d_{avg}$ neighbors on average) need to update the their distance to the sampled set. Therefore, the time complexity of $\\tilde{O}(nd_{avg})$ is straightforward.\n3. The experimental on the Appendix A seems not ideal. For example, in Figure 5,6,7, the proposed method does not obtain the best ARI; Figure 7 also shows that the green baseline is actually faster. And there is no explanation for that.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)