Local $K$-means: An Efficient Optimization Algorithm And Its Generalization
Authors: Feiping Nie
Shenfei Pei
Rong Wang
Liang Zhang
Jun Wu
Qinglong Chang
Xuelong Li
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Clustering
efficient
local
k-means
generalization

Abstract: Until now, $k$-means is still one of the most popular clustering algorithms because of its simplicity and efficiency, although it has been proposed for a long time.
In this paper, we considered a variant of $k$-means that takes the $k$-nearest neighbor ($k$-NN) graph as input and proposed a novel clustering algorithm called Local K-Means (LKM).
We also developed a general model that unified LKM, KSUMS, and SC, and discussed the connection among them.
In addition, we proposed an efficient optimization algorithm for the unified model. 
Thus, not only LKM but also SC can be optimized with a linear time complexity with respect to the number of samples. 
Specifically, the computational overhead is $O(nk)$, where $n$ and $k$ are denote the number of samples and nearest neighbors, respectively.
Extensive experiments have been conducted on 11 synthetic and 16 benchmark datasets from the literature. 
The effectiveness, efficiency, and robustness to outliers of the proposed method have been verified by the experimental results.

Local K-means: An Efficient Optimization Algorithm And Its Generalization
Anonymous Author(s)
Affiliation
Address
email
Abstract
Until now, k-means still one the most popular clustering algorithms because of its simplicity and efficiency, although it has been proposed for long time. In this paper, we considered a variant of k-means that takes the k-nearest neighbor (k-NN) graph as input and proposed novel clustering algorithm called Local K-Means (LKM). We also developed a general model that unified LKM, KSUMS, and SC, and discussed the connection among them. In addition, we proposed an efficient optimization algorithm for the unified model. Thus, not only LKM but also SC can be optimized with linear time complexity with respect the number of samples. Specifically, the computational overhead is ((n)), where n and & are denote the number of samples and nearest neighbors, respectively. Extensive experiments have been conducted on synthetic and 16 benchmark datasets from the literature. The effectiveness, efficiency, and robustness outliers of the proposed method have been verified by the experimental results.
11
13
Introduction
14
Clustering is of the fundamental tasks of machine learning [10]. It plays very important role in many applications such as document analysis [6], image processing [14], and recommender system
16
Given dataset with samples and the number of clusters its purpose is to split these samples into e disjoint groups, so that the samples within the same group are similar to each other, and the samples between different groups are not. Although there lots of clustering algorithms have been proposed, k-means still getting lot of attention. In this paper, we proposed an efficient clustering method called local k--maans where k-NN graph taken input. It can be seen as variant of traditional k-means. the following, the two basic materials of our model are firstly described, and the main contributions of this article will be mentioned the end of this section.
12
18
20
21
22
23
24 Notations: Bold capital letters and bold lowercase letters denote matrices and vectors, respectively. The symbols n. d, and are respectively used to represent the number of samples of the dataset, the number of features, and the number of clusters to construct. For matrix A, we call it indicator matrix, if each row of it has only element equal to 1. xx is the set of all indicator matrices.
26
28 1.1
k-means
29 As one of the most popular clustering algorithms, k-means aims to group samples into e clusters
30 where each sample belongs to the cluster with the nearest cluster centers. Let X = [x x,,'' e
31 Raxd be a collection of samples to cluster, where x; E dd denotes the i-th sample. Then the objective
32 function of k-means be formulated
min ΣΣ
|x ma
K=1xEEA
Submitted to Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

User
D
Figure I: Community in the social network. There is connection between users if they know each other, in other words, the two people are friends with each other. The thicker the line, the more familiar the users. According to the connections between users, the clustering algorithm divides them into disjoint sets. For example, partition composed of A, B, C, and D is satisfactory clustering result.
where A& denotes the set of samples in the i-th cluster, A A.U....UA (x: (x 1 ,n), and 34 m. denotes the mean samples in A&.
Although the problem in Eq. (1 is computationally difficult. many efficient optimization algorithms
36 where local optimum will be found quickly have been proposed. Among them, Lloyd's 's algorithm the most widely used. Let Y
yy.. .y. [y,, .8.] E IRexe be an indicator matrix, i.e.,
1
x; E,, ,i= 1..,,,,,, nn. 1, 1.,.. ,
Vij
0
otherwise
38
the problem in Eq. ①1 can be then rewritten as
min |X YM
(3)
where M (Y" In Lloyd's algorithm, Y and M regarded as two independent variables and be optimized alternately.
40
41
1.2
Data in the form of graph
In fields such as social networks and recommendation systems, the data being studied is often
43 presented in the form of graphs. other words, for single sample, we have no features to describe
44 it, what we have is only the relationship between it and others, as shown in Figure [
45 In generally, a sparse similarity matrix W R=*x can be used to describe this kind of data, i.e..
f(xi,x) xj) If x; and xj are directly connected Otherwise
Wij
...j = 1,,.., n,
(4)
where f(x,, Xy) represents the similarity between x; and xj. and its value can be usually obtained 47
directly.
Based on the above discussion, k-means-like algorithm is proposed, which takes the A-NN graph as input and can be quickly optimized. In addition, we also discussed its connection with other algorithms, such as KSUMS and spectral clustering. Here, summarize the main contributions of the article as follows
49
51
52
A novel clustering algorithm called Local K-Means (LKM) is proposed. Because only the distances between the sample and its neighbors considered, LKM is robust to outliers.
54
The relationship between LKM and other algorithms (KSUMS and SC) is discussed, and unified model established.
55
An efficient optimization algorithm for the unified model is developed, from which we find that the spectral clustering model can be optimized in the same way as L.M,, which means both of them can also be optimized in (nk) time.
57
58
'Specifically, it is np-hard problem.

---

59 2
Related work
A disadvantage of k-means is that its performance will be affected largely by the initialization of the cluster center. To this end, a lot of efforts have been made, such as [2] 3]. In these methods, the cluster center is carefully initialized through special process. In addition the more robust clustering result, an improvement of performance can also be achieved. More related work can be
61
63
found here [[5 22
65
Since the computational complexity of k-means involves the product of the number samples and clusters, it will be very time-consuming if the two numbers are very large. With the help of techniques that used to accelerate the nearest neighbor search, the nearest center for each sample
66
67
can be quickly found without computing distances to all centers [25 [T]. 7 developed fast
69
implementation of k-means using coreset. partition on a small coresct is computed firstly and is used as initialization a larger coreset. In (32,, Xia al. described each cluster by ball and proposed Ball k-means which accelerated k-means by reducing the computation of distances between samples and centers. [ proposed compressive k-means (CKM) where the centers are estimated from a sketch (a compressed representation of the original data). Once the sketch is obtained, the computational overhead is then independent of the size of the original data. Moreover, it's also hot spot to use the advantages of GPU to shorten the time consumed by k-means, such as [17 and 5
71
73
74
75
Clustering on graph data is also a hot topic. Some well-known algorithms include 19 29 21 However, these algorithms often have a time complexity that increases quadratically with respect to the number of samples. To this end, many fast versions of them are proposed [33 20 9].
77
3 The proposed model
80 In our article, how solve the problem in Eq. ① has not been paid attention to, but some simple 81 derivations are firstly made on it. Therefore we can analyze the meaning of the problem from the
82 perspective of a distance graph. For convenience, we define (x,)), {xx x, is among the
83 k-nearest neighbors of x; or x; is among the k-nearest neighbors of x, and start from the following
84 equivalent form of k-means
min
||x - 1
(5)
A
EAA
85
With the help of the definition of in Eq. problem 5
can be equivalently expressed as follows
(YY"))-1) T diag (Y"DY),
min diag
Y Ye
min Tr YeaoXe
where (A) [a11. 86
ann]" IT, Obviously, if we only consider the distances between the sample
87 and its neighbors, then the problem in Eq. (7) can be expressed
(())))
min T' Yegaxe
(8)
88 with
||:; -x,112
if (x,xx)
7
Otherwise
where y is the maximum value of set {||x; - x,113
x; E i 1,..., .n... The Equation (8)
89
90 is the final objective function of L.K.
91 From the discussion in Section 1.2 we know that only the similarity instead of the distance between
82 samples can be obtained directly in graph data. Fortunately, in practical applications, we can convert
93 the similarity dissimilarity by
(og(s)))
0 0< 8ij
(10)
Sig =
34 where sij is the normalized simillarit between x; and xj 3 is the maximum value of set (-log( (siz) 95 i.j 1.......0 .... Then the dissimilarity can be used replace the distance in the model.
Ssy E []
3

---

98 3.1 Generalization
97 It not difficult to find that LKM, KSUMS 23 and Ratio-cut 29 can all be represented uniformly
98 by the following model
Tr ( Y
min
(11)
where Gig denotes the dissimilarity distance between x, and Xj, and p >= 0 is parameter. The meaning of will be explored in future work.
(k)
100
Instances of KSUMS and LKM: The objective function of KSUMS is
min Tr (Y"D(OY))
(12)
(k) where D takes the same expression that in LKM. Let 9ij be setted by Eq. (9 the problem (1
103 is identical with KSUMS 12 p= O, and is identical with LKM if =
104
Instance of Ratio-cut: Benefiting from the introduction of Y, the problem of ratio-cut (an algorithm that belongs to the spectral clustering (SC) family) can be expressed as
105
min Tr Y
()))),
(13)
106 where A is diagonal matrix, Au -E Wij- In generally, the similarity matrix W can be 1x |x,-,,11 x, 1
determined by heat kemel, i.e., Wij
if x; (xxx),), Waj 0 otherwise. Therefore the (k) is setted by
108
problem
11 is equivalent with ratio-cut, if p = and Oij
1 Waj
i i and E (x,) Otherwise
Bij
Wij
(14)
109
3.2
Optimization
110 From the discussion above, we know that the problem of LKM can be expressed by Eq. [I] with
1. Therefore, an optimization algorithm for problem (IT) instead of problem (8) is developed.
112 To begin with, some notations are presented as follows
8; 2 y. (1) Vi, i= i-
(15)
n; - y!',,, yi, i i= =1,,..
(16)
the problem
11
then becomes
min Obj(Y), with Obj(Y) Yeanxe
81
(17)
m2
In the following derivation, the i-th row of Y (i.e., y:) is regarded the variable to be optimized 115 while others are fixed, and y; = e, before updated. Thus y; can be updated by
yi e3
arg min Obj(y; e;) Obj(y: =0,
(18)
116 where e; [0, 1, be a vector with all elements equal except the i-th, which is 1, and
117 is the column vector of all zeros,
Because Obj(y; 0) is constant, the above formula holds. According to Eq. 17 we have
Syth Ine
4 n
j 4 a
Obj(y; = e,)
e,) - Obbjy, 0)
- = 1, ,,
(19)
51
b
j
n²
( 1ym
119 with
2 ExxEA E.A, Fit 9ns
(k) (k)
j i
(20)
Σ E,A, Fit gii j j=
(k) (k)

---

Algorithm 1: An efficient program for solving problem (1I).
Note: The vector y E R. denotes the clustering result, i.e., y: is the cluster that x; belongs
The Eq. (15). (T6). and 20 involved in the algorithm have high computational complexity, but
these can be computed more efficiently if the sparsity of G()) is considered. See the
supplementary material for more detailed algorithm:
Data: Sparse matrix Pr R=x*" the number of cluster
Result: The clustering result Initialize y randomly;
Compute vector and n by Eq. 15 and 16 respectively;
while not converge do
for i - 1, -,..... , do
Compute 6, by Eq. Compute Obj(y
20
for j E B;;
Obj 0) by Eq. 19 for j E B;;
Update y by Eq. 18
Update and n Eq.
21 and Eq. 22
respectively;
Benefiting from the sparsity of G(,), takes O(nk), O(k + c), and O(k) time to compute s, and n. respectively. Therefore, the proposed optimization algorithm has computational complexity of O(n²k: + ne), which unbearable, for large-scale datasets. However, if the variables s and are computed in advance and updated following the update of yi. then the computational complexity of the algorithm can greatly be reduced. The update rules for s and n are as follows
120
122
124
Sa $ Sa ba
SB - 8B + bg.
(21)
na + aa 1,
ng + ng + 1,
(22)
125 Thus, the computational complexity of the optimization algorithm is O(n(k: + c)).
On more step From Eq. 11 we know that only the information of pair (x:, Xj) Xx) is considered in
127
the model, and there are at most 2nk such pairs. For convenience, we assume that there are exactly
2k such pairs for each sample x,, i..., 2k = (x,, x,) x, (x,))) x; (x,)))) For cluster j. we call an element of B, (j E B,), if there is at least one sample in cluster j belongs to (x,) the assumption and notations above, we know that when updating y; by Eq. (88). the size of B, is at most 2k. However, it does not make sense group the sample x; into cluster & B, from the perspective of the performance. Therefore, we only need to pay attention to the cases where j E B, Thus, the computational complexity of the optimization algorithm can be reduced to ((n)).
129
or x; belongs to the set of neighbors of these samples. Based
131
132
133
134
135
Time and space complexity From Algorithm we can see that the memory is mainly occupied by the matrix (k) E I which is equivalent to sparse matrix, and contains at most 2nk non non-constants. The memory overhead caused by other variables is O(n) at most. For example, y,
136
137
B, and require (n)) O(k), and O(c) memory, respectively. Thus the memory overhead of LKM (nk).. Benefiting from the sparsity of G(k), Eq. (15). (16). and (20) can all be calculated more efficiently. Specifically, only ((nk), O()), and O(k) time are needed respectively, please refer to the supplementary materials for details. After y; updated, only ((1) time is needed to update variables
138
139
140
141
142
S and n. Thus, the computational complexity of LKM is O(nk).
4 Experiments
144
In this section, the performance of the proposed algorithm, LKM, is verified on eleven synthetic datasets and sixteen benchmark datasets. The rest of this section is organized as follows: First, experiments on synthetic datasets are shown. In short, Mickey, Outlier, and family of Grid datasets are used to verify the effectiveness, robustness, and efficiency of LKM, respectively. Then, we compare 7 popular clustering algorithms with LKM on 16 benchmark datasets, to evaluate the performance of the proposed algorithm.
145
148
147
148
149
Strictly speaking, (*) is not sparse matrix. However, at most 2nk values in G are not equal to X, so it be regarded sparse matrix.
5

---

150
4.1
Experiments conducted on synthetic datasets
151
Experiment on "Mickey" To verify the effectiveness of LKM, a synthetic dataset called "Mickey" constructed. The distribution of points is shown in Figure 2(a) The triangles representing the means of the clusters are not points of the datasets.
158
154
we found that The proposed method LKM successfully found the cluster structure, but k-means did not. k-means still cannot find the correct structure, even with the initialization of the ground truth label. Because the distance between point I and the blue triangle (mean of all blue points), di is greater than the distance between point and the orange triangle (mean of all orange points), d2, k-means will group it into the blue cluster instead of orange. Therefore, k-means cannot handle datasets like this.
From Figure 2(b) and 2(c)
155
157
159
di
d2
(a) Original
(b) k-means
(c) LKK
Figure 2: The performance of k-means and LKM on "Mickey".
160
Experiment on "Outlier" In order to verify the robustness of our method, we construct a dataset called "Outlier". It consists of four clusters with centers (0, 0), (0, 5), (5, 0). and (5, 5), and an outlier with the coordinate of (100, 100). The distance between outlier A and other points is not as close as shown Figure From Figure and we can see that the performance of k-means severely affected by the outlier A, while the performance of LKM is not. In k-means, the center of the cluster containing abnormal points will largely shift towards the direction of the abnormal points, resulting in poor performance. In LKM, the distance between and x5 is not calculated if X, & (x,).... but a parameter is used instead, so ideally, the distance between any two points belonging to different clusters is A. In other words, for the sample point x,, there is no difference between the outlier and the samples that do not belong to Nig (x,).
161
163
165
167
189
A (100, 100)
A (100, 100)
A (100, 100)
(a) Original
(b) k-means
(c) LKM
Figure 3: The performance of k-means and LKM on "Outlier".
Experiments on the family of "Grid" In order to verify the efficiency of LKM, in this paragraph, synthetic datasets called Toy-1, Toy-2, ... Toy-9 are constructed. These datasets share the same structure, and their distributions are similar to that shown in Figure In these datasets, each cluster always composed of points generated by Gaussian distribution. Since the time complexity of
172
175
LKM and k-means is closely related to the number of points, we set different sizes for these data
175 sets, ranging from 1960 125440. The number of clusters and the standard deviation involved the Gaussian distribution for cach dataset is shown in Table

---

k-mmans
(b) LKM
Figure 4: The performance of k-means and LKM on Toy-1.
Table 1: Performance of m-mma and LKM
Precision
Recall
Fi score
Datasets
# Clusters
30
k-means
LKM
k-means
LKM
k-means
LKM
Toy-1
196
0.5
0.854
0.975
0.915
0.983
0,883
0.979
Toy-2
196
0.6
0.834
0.948
0.885
0.957
0.859
0.953
Toy-3
196
0.7
0.785
0.874
0.828
0.889
0,806
0,881
Toy-4
3136
0.5
0.856
0.981
0.918
0.988
0.886
0.984
Toy-5
3136
0.6
0.832
0.947
0.881
0.957
0.856
0.952
Toy-6
3136
0.7
0.783
0.883
0.825
0.893
0.803
0.888
Toy-7
12544
0.5
0.855
0.982
0.917
0.988
0.885
0.985
Toy-8
12544
0.6
0.833
0.948
0.882
0.957
0.857
0.952
Toy-9
12544
0.7
0.785
0.884
0.826
0.896
0.805
0.890
Table 2: Time (s) consumed by k-means and LKM
FLK
k-means
Datasets
Ball-Tree
Algo.
Iter.
Total
# Iter.
Total
Speed-up
Toy-1
6.26E-03
1.30E-03
3.96
7.56E-03
13.12
5,97E-03
1.39E+00
Toy-2
6.54E-03
1.66E-03
5,66
8.20E-03
14.32
5.57E-03
1.33E+00
Toy-3
6.27E-03
1.73E-03
5.96
8.00E-03
15.32
6.00E-03
1.35E+00
Toy-4
1.34E-01
2.64E-02
5.80
1.60E-01
14.68
2,00E+00
3.00E+01
Toy-5
1.37E-01
3.32E-02
7.64
1.70E-01
16.62
2,27E+00
3.15E+01
Toy-6
1.39E-01
3,98E-02
9.40
1.79E-01
18.50
2.55E+00
3.25E+01
Toy-7
6.50E-01
1.35E-01
7.20
7.85E-01
16.22
3.89E+01
1.28E+02
Toy-8
6.04E-01
1.64E-01
9.08
7.68E-01
17.58
4,21E+01
1.33E+02
Toy-9 6.18F-01
1.95E-01
10.96
8.13E-01
18.88
4.50B+01
1.34E+02
177 In Table 2 the column named "Ball-Tres represents the time takes to construct the graph required by LKM through Ball-tree with & = 20. The column named "# Iter" denotes the number of iterations required for the algorithm to converge. The total time of LKM refers to the sum the time consumed by Ball-Tree and Algorithm 1. The speed-up is the ratio of the time consumed by each iteration of k-means to the time consumed by each iteration of Algorithm 1. Both k-means and LKM were run 50 times, and the average results were reported.
179
181
185 As shown Table 2 Algorithm consumes a significantly shorter time than k-means, which is more obvious on datasets with more clusters. The main reason is that when yı is going to update, only the case where B, considered. In addition, L.K has a significant improvement terms of the k
185
quality of the clustering result, compared to k-means, shown in Table I and Figure

---

187
4.2
Mpeg7 7 Experiments conducted on benchmark datasets
188
4.2.1
Datasets
189
Sixteen benchmark datasets are used including LFW 8 CPLFW 34 CALFW 35
FERET 241
190
Colon M. MUCT [8]. CMUPIE BO), CFPW 27 Dexter Madelon, GTDB V5
191
Olivetti, Yale, and Umist All facial datasets are processed by the way (33. For those non- facial
192
datasets, PCA [T is adopted and some components are selected such that the amount of variance is
195
greater than 95% if the dimensionality of the datasets larger than 1024. The names of datasets are
all linked to where the dataset can be download. The introduction to these datasets can be found in the supplemental material.
195
196
4.2.2
Baselines and experimental settings
197
We compare LKK with several clustering algorithms, including AGCI 33 FINCH (26). k-means
196
[6]. KSUMS 23], , RCC 28), SC (29]. and FCDMF (20]. For graph-based methods, i.e., KSUMS, RCC, and SC, the number of nearest neighbors, k is fixed at 20. For anchor-basce methods, AGCI and FCDMF, the number of anchors is always set by m = min(nn/, 1024). Whether k-NN graph anchor graph, heat-kernel is always adopted to construct the graph. In FINCH, we take the clustering result with the number clusters closest to the number of ground truth clusters as the final clustering result. In RCC, the threshold assign points together in a cluster is tuned from 00.1. 0.3, 0.5, 0.7, 0.9}. K Ke-maan/i is initialized in a random way and the step of k-means involved in AGCI and SC share the same configuration with k-means itself. If the performance of the algorithm
200
202
204
206
is related to the initialization, we run it repeatedly 50 times and report the average performance.
We run all methods on an Arch machine with i7-8700 CPU (3.20 GHz), 32 GB main memory.
208
4.2.3
Experimental results
209
Clustering ACCuracy (ACC), Normalized Mutual Information (NMI), and Adjusted Rand index (ARI) are used to evaluate the performance of these algorithms. From Table we can clearly see that: (1) In most cases LKM has achieved the highest performance comparing to several state-of-the-an algorithms, which verified the effectiveness of the proposed algorithm. Specifically, LKM exceeds the second-best results 24.4%, 4.6%, 4.8%, 1.5% and 1.3% on CALFW, LFW, Umist, Olivetti, and CMU respectively, in terms of ACC. Under the metrics of NMI and ARI, we can come to similar results. (2) Although only slight improvements LKM has achieved over many datasets compared to the second- best results, the computational complexity of LKM is much lower than that of most algorithms, which is an important property of LKM. (3) RCC has poor performance on F5 CMU, GTdb, Umist, and Yale, which may be caused largely by inappropriate threshold, while only one parameter (the number of neighbors) is needed in LKM, is an integer and easy to tune. In addition, the influence of parameter is (the number of neighbors) on clustering performance has been studied, and the results are shown in the supplemental material.
211
213
215
217
219
221
Conclusions
222
223
In this paper, we devote ourselves to an unsupervised learning problem, clustering. An efficient clustering algorithm called Local K-Means (LKM) was proposed. It can be seen as a variant of k-means that takes the k--N graph as input. We also discussed general model that unified LKM, KSUMS, and SC. Thus the connection among them can be easily established. In addition, we developed an efficient optimization algorithm for the unified model, so that not only LKM but also
224
225
226
227
228
SC can be optimized in ((nk) time, which is very important for large-scale datasets, especially for these datasets with a large number of clusters. In order to verify the advantages of LKM, extensive experiments on eleven synthetic and sixteen benchmark datasets are conducted, and the results have shown the effectiveness, efficiency, and robustness of our model.
229
231
232
Limitations In some cases where K--N graphs are not available, our algorithm cannot work, in other words, a graph construction algorithm necessary. Although many methods have been proposed, it is still very difficult to effectively construct an approximate k-NN graph if the number of features is large. Thus, in these situations, the graph construction algorithm will produce a k-NN graph of poor quality that would lead to poor performance of clustering results.
233
235
8

---

Table 3: Performance on benchmark datasets
Datasets
Met.
AGCI
FCDMF
FIN
k-means
KSUMS
RCC
SC
LKM
ACC
0,460
0,450
0.373
0.460
0.454
0.551
0.424
0.597
LFW
NMI
0,866
0.860
0.711
0.866
0.850
0.805
0.703
0.893
ARI
0.063
0.078
0.008
0.063
0.037
0.592
0.010
0.100
ACC 0,599
0.399
0.504
0.599
0,419
0.573
0.560
0.843
CALFW
NMI
0.887
0.859
0.696
0.888
0.878
0.886
0.754
0.971
ARI
0.187
0.084
0.007
0.190
0.098
0.373
0.005
0.729
ACC
0.537
0.355
0.584
0.546
0.738
0.745
0.527
0.742
CPLFW
NMI
0.770
0.689
0.613
0.772
0.889
0.857
0.733
0.865
ARI
0.209
0.167
0.012
0.208
0.627
0.201
0.089
0.333
ACC
0.730
0.517
0.535
0.731
0.934
0.069
0.621
0.938
V5
NMI
0,930
0.829
0.829
0.931
0.979
0.105
0.812
0.983
ARI
0.605
0.280
0.290
0.621
0.899
0.001
0.070
0.910
ACC
0.537
0.355
0.584
0.546
0.738
0.745
0.527
0.742
CFPW
NMI
0.770
0.689
0.613
0.772
0.889
0.858
0.733
0.865
ARI
0,209
0.167
0.012
0.208
0.627
0.202
0.089
0.333
ACC
0.185
0.154
0.165
0.182
0.286
0.015
0.285
0.299
CMU
NMI
0.409
0.372
0.306
0.407
0.571
0.000
0.552
0.582
ART
0.079
0.063
0.018
0.077
0.192
0.000
0.173
0.201
ACC
0.690
0.581
0.629
0.608
0.635
0.581
0.737
0.748
Colon
NMI
0.178
0.010
0.129
0.094
0.108
0.045
0.143
0.259
ARI
0.208
0.011
0.249
0.078
0.110
-0.05
0.210
0.317
ACC
0.579
0.627
0.153
0.596
0.584
0.490
0.567
0.612
Dexter
NMI
0.077
0.124
0.080
0.091
0.024
0.051
0.015
0.123
ARI
0.035
0.063
0.011
0.042
0.031
0.002
0.017
0.050
ACC
0.522
0.378
0.495
0.521
0.546
0.661
0.463
0.621
FERET
NMI
0.822
0.734
0.686
0.822
0.839
0.714
0.735
0.863
ARI
0.354
0.211
0.039
0.353
0.439
0.022
0.036
0.520
ACC
0.454
0.419
0.391
0.459
0.533
0.047
0.491
0.541
GTdb
NMI
0.658
0.634
0.579
0.661
0.690
0.032
0.666
0.697
ARI
0.313
0.282
0.211
0.319
0.382
0.002
0.314
0.387
ACC
0.517
0.513
0.456
0.521
0.529
0.500
0.507
0.534
Madelon
NMI
0.003
0.001
0.001
0.005
0.005
0.000
0.000
0.005
ARI
0.004
0.000
0.000
0.006
0.006
0.000
0.000
0.006
ACC
0.463
0.445
0.442
0.462
0.539
0.429
0.462
0.552
Mpeg7
NMI
0.660
0.650
0.617
0.666
0.720
0.701
0.657
0.721
ARI
0.278
0.295
0.153
0.291
0.414
0.452
0.220
0.346
ACC
0.732
0.741
0.972
0.722
0.982
0.754
0.627
0.979
MUCT
NMI
0,928
0.922
0.991
0.923
0.992
0.922
0.791
0.995
ARI
0.612
0.698
0.971
0.586
0.976
0.700
0.093
0.980
ACC
0.509
0.407
0.480
0.510
0.569
0.550
0.527
0.584
Olivetti
NMI
0.722
0.643
0.674
0.718
0.758
0.780
0.723
0.768
ARI
0.366
0.263
0.323
0.366
0.443
0.387
0.364
0.456
ACC
0.413
0.412
0.468
0.416
0.450
0.083
0.431
0.516
Umist
NMI
0.626
0.589
0.673
0.628
0.641
0.000
0.634
0.690
ARI
0.320
0.300
0.375
0.317
0.355
0.000
0.323
0.428
ACC 0.395
0.344
0.339
0.397
0.443
0.067
0.405
0.452
Yale
NMI
0.448
0.398
0.358
0.455
0.495
0,000
0.456
0.498
ARI
0.187
0.139
0.119
0.196
0.234
0.000
0.194
0.239

---

References
237
238
[1] U. Alon, N. Barkai, D. A. Notterman, K. Gish, S. Ybarra, D. Mack, and A. J. Levine. Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tis- sues probed by oligonucleotide arrays. Proceedings of the National Academy of Sciences, 96(12)677556770, 1999.
240
241
242
[2] D. Arthur and S. Vassilvitskii. k-means++: The advantages of careful seeding. Technical report, Stanford, 2006.
244
[3] O. Bachem, M. Lucic, H. Hassani, and A. Krause. Fast and provably good seedings for k-means. In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 55-63. Curran Associates, Inc., 2016.
246
[4] O. Bachem, M. Lucic, S.H. Hassani, and A. Krause. Approximate k-means++ in sublinear time. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pages 1459-1467, 2016.
248
250
[5] Cuomo, V. De Angelis, G. Farina, L. Marcellino, and G. Toraldo. A gpu-accelerated parallel k-means algorithm. Computers & Electrical Engineering, 75:262-274, 2019.
252
[6] G.R. De Miranda, R. Pasti, and L.N. de Castro. Detecting topies in documents by clustering word vectors. In International Symposium on Distributed Computing and Artificial Intelligence, pages
253
254
Springer, 2019.
255
[7] G. Frahling and C. Sohler. A fast k-means implementation using coresets. International Journal of Computational Geometry & Applications. 18(06):605- 625, 2008
256
257
[8] B.H. Gary, R. Manu, B. Tamara, and L.M.r Erik. Labeled faces in the wild: A database for studying face recognition in unconstrained environments. Technical Report 07-49, University of Massachusetts, Amherst, October 2007.
258
259
[9] L. He, N. Ray, Y. Guan, and H. Zhang. Fast large-scale spectral clustering via explicit feature mapping. JEEE Transactions on Cybernetics, 49(3):1058-1071 2019.
261
[10] A.K. Jain, M.N. Murty, and P.J. Flynn. Data clustering: review. ACM computing surveys (CSUR), 31(3):264-322 -333, 1999.
263
[11] T. Kanungo, D.M. Mount, N.S. Netanyahu, C.D. Piatko, R. Silverman, and A.Y. Wu. An efficient k-means clustering algorithm: Analysis and implementation. IEEE transactions on pattern analysis and machine intelligence, 24(7):881-892, 2002.
265
267
[12] R. Katarya and O.P. Verma. An effective web page recommender system with fuzzy c-mean clustering. Multimedia Tools and Applications, 76020):21481-21466 2017. 2017.
289
[13] N. Keriven, N. Tremblay, Y. Traonmilin, and R. Gribonval. Compressive k-means. In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 0669-6373, 2017.
270
271
272
[14] W. Kim, A. Kanezaki, and M. Tanaka. Unsupervised learning of image segmentation based on differentiable feature clustering, JEEE Transactions on Image Processing, 29:8055-8066 2020.
273
274
[15] M. Li, D. Xu, D. Zhang, and J. Zou. The seeding algorithms for spherical k-means clustering. Journal of Global Optimization, pages 695-708, 2019.
275
276
[16] S. Lloyd. Least squares quantization in pem. IEEE transactions on information theory, 28(2):129-137, 1982.
278
[17] C. Lutz, S. Breß, T. Rabl, S. Zeuch, and V. Markl. Efficient k-means on gpus. In Proceedings of the 14th International Workshop Data Management New Hardware, pages 1-3, 2018.
280
[18] S. Milborrow, J. Morkel, and Nicolls. The MUCT Landmarked Face Database. Pattern Recognition Association of South Africa, 2010. http://www. mi mio.o.... org/muct
10

---

282
[19] A. Y. Ng, M.I. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In Advances neural information processing systems, pages 849-856, 2002.
283
284
[20] Nie, S. Pei, R. Wang, and X. Li. Fast clustering with co-clustering via discrete non-negative matrix factorization for image identification. In ICASSP 2020-2020 IEEE International Confer- ence on Acoustics, Speech and Signal Processing (ICASSP), pages 2073-2077. IEEE, 2020.
286
[21] F. Nie, X. Wang, and H. Huang. Clustering and projected clustering with adaptive neighbors. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD "14, page 977-986, New York, NY, USA, 2014. Association for Computing Machinery.
288
290
291
[22] J. Ortiz-Bejar, E.S. Tellez, M. Graff, J. Ortiz-Bejar, J.C. Jacobo, and A. Zamora-Mendez. Performance analysis of k-means seeding algorithms. In 2019 IEEE International Autumn Meeting on Power, Electronics and Computing (ROPEC), pages 1 1-6. IEEE, 2019.
282
293
[23] S. Pei, F. Nie, R. Wang, and X. Li. Efficient clustering based unified view of k-means and ratio-cut. Advances in Neural Information Processing Systems, 33, 2020.
295
296
[24] P.J. Phillips, H. Wechsler, J. Huang, and P.J. Rauss. The feret database and evaluation procedure for face-recognition algorithms. Image and vision computing, 16(5):295-33) 1998.
297
298
[25] SJJ. Phillips. Acceleration k-means and related clustering algorithms. In Algorithm Engineer- ing and Experiments, pages 166-177. Springer Berlin Heidelberg, 2002.
300
[26] S. Sarfraz, V. Sharma, and R. Stiefelhagen. Efficient parameter-free clustering using first neighbor relations. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8934 8943, 2019.
302
303
[27] S. Sengupta, J. Chen, C. Castillo, V.M. Patel, R. Chellappa, and D.W. Jacobs. Frontal to profile face verification in the wild. In 2016 IEEE Winter Conference on Applications of Computer Vision (WACV), pages 1-9. IEFF, 2016.
305
[28] S.A. Shah and V. Koltun. Robust continuous clustering. Proceedings of the National Academy of Sciences, 114(77:9814-9819, 2017.
307
308
[29] J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 2288))888-900 2000.
309
310
[30] T. Sim, S. Baker, and M. Bsat. The cmu pose, illumination, and expression database. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(12):1615-1618 2003.
312
[31] M.E. Tipping and C.M. Bishop. Probabilistic principal component analysis. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 61 61(3):61--62) 1999.
313
[32] S. Xia, D. Peng. D. Meng, C. Zhang, G. Wang, E. Giem, W. Wei, and Z Chen. A fast adaptive k-means with no bounds. IEEE Transactions on Pattern Analysis and Machine Intelligence. pages 1-1, 2020.
315
317
[33] Y. Zhao, Yuan, and Q. Wang. Fast spectral clustering for unsupervised hyperspectral image classification. Remote Sensing, 11(4):399, 2019.
318
[34] T. Zheng and W. Deng. Cross-pose Ifw: A database for studying cross-pose face recognition in unconstrained environments. Technical Report 18-01, Beijing University of Posts and Telecommunicationss, February 2018.
320
322
[35] Zheng, Deng, and J. Hu. Cross-age LFW: A database for studying cross-age face recognition in unconstrained environments. CoRR, hbs//708..08997 2017.
11

---

Checklist
324
325
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
327
contributions and scope? [Yes]
328
(b) Did you descrihe the limitations of your work? [Yes]
329
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
331
332
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
334
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
337
338
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
339
340
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
343
344
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
345
(a) If your work uses existing assets, did you cite the creators? [Yes]
346
(b) Did you mention the license of the assets? [No]
347
(c) Did you include any new assets either in the supplemental material or as a URL? [No]
348
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes]
349
350
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No]
352
5. If you used crowdsourcing or conducted research with human subjects...
353
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
355
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
356
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
358
12


Reviews:
[{"review_id": "zEbnfRxXQ24", "reviewer": "Reviewer_PD9K", "summary": "This submission introduces a computationally efficient clustering algorithm called LKM, which focuses on the scenarios where data is presented in the form of graph. In brief, only the k-nearest neighbour distances of each point are considered in the objective and a simple truncation of large distances is introduced to mitigate the effect of outliers.  The method is shown to produce promising practical performance in comparison with existing techniques both computationally and in terms of clustering performance.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strengths:\n\nLKM is developed based on the k-means problem which is a fundamental problem in machine learning and the authors might bring some new insights and develop a new algorithm. The main strength of LKM lies in the practical aspects of the proposed algorithm, in that it is efficient and the performance is compelling. \nSpecifically, the computational overhead is O(nk), where n and k denote the number of samples and nearest neighbors, respectively.\n\nIn addition, the unified framework of KSUMSC, and LCM also seems interesting. It revolves that SC, a popular clustering algorithm derived from graph cuts, can be optimized with the same time complexity as that of LKM.\n\nWeaknesses:\n1. Line 9: \"Specifically....are denote the...\". The sentence is grammatically incorrect, \"are\" should be removed.\n\n2. Some works relating to the connection between k-means and clustering with graph cuts are not discussed in Section 2 (Related work).\n\n3. The performance of SC optimized by the proposed algorithm is not shown.\n\n4. What does \\bar{y} stand for in Eq. (15) and (16)?\n\n5. e_i should be a column vector.\n\n6. Some steps in the derivations are not explained. What is the connection between (11) and (17)? \n\n7. The evaluation needs to be improved. The proposed clustering method uses ball-tree to construct a k-nearest neighbors graph as an intermediate step. Correspondingly, it is suggested to include the clustering performance of ball-tree as a baseline to compare.\n\n8. Have the paper proof-read to remove grammatical errors\n\n9. In page 7, line 178, \"#Iter\" should be \"#Iter.\".\n\n10. In page 7, table 2, \"FLK\" should be \"LKM\".\n\n11. References should be shown in the same format.\n\n**comment after rebuttal**\nI acknowledge that I read and other reviewers' comments and authors' responses. I would like to keep my score as most concerns of mine have been well addressed.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "N.A.", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "hlRcPS6VCWb", "reviewer": "Reviewer_o7mN", "summary": "This paper considers a variant of k-means which takes the k-nearest neighbor graph as input. The proposed algorithm, called local k-means (LKM in short), then works by locally optimizing the assignment vector of a point using an objective function that is roughly the incremental cost for the k-means objective. The paper provided a lot of empirical data to show the advantages of LKM.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Overall, this paper proposes a novel k-means algorithm, but I think there has not been enough discussion on its guarantees (from both a theoretical and empircal point of view) to make it convincing. The paper writing can also be greatly improved.\n\nOriginality: The mthods used in this paper are new. The paper converts the k-means objective into a different format which is compatible with nearest-neighbor graph inputs, where the main variable is the indicator matrix, and optimizes the columns in this matrix one by one (each column corresponding to the assignment vector of one point). The idea of optimizing the assignment of each point to clusters might not be new to the community, but the proposed local optization function seems to be novel.\n\nQuality: The paper does not provide any theoretical guarantees for the proposed algorithm and mainly used empirical evaluation approaches to show its superiority. The experiments are carefully designed, but I think the authors are trying to make some claims that are too broad and thus the provided empirical results do not seem to be convincing enough to show that this approach really beats state-of-the-art. LKM is compared with a lot of baselines and that may still not cover the entire state-of-the-art clustering approaches. Some comments:\n- The self-synthesized data are well designed, and serves to show that LKM performs well on some datasets whose natural clustering cannot be captured by the optimal k-means objective function. However, it seems to me that they might be suitable for other types of clustering such as density-based clustering (DBSCAN might be good for \"Mickey\"), or common k-means implementation packages might also be good for them (k-means++ might be good for \"Outlier\" depending on the sampled seeds?).  I wonder if the authors have considered these?\n- After reading the experiment section I get a bit more confused about the claims that this paper is trying to make: LKM seems to be beating most baselines on the datasets in clustering quality and be significantly faster than k-means? The improvement of LKM , especially when compared with KSUMS on most of the datasets, do not seem to be very significant. Actually, the results gave me the impression that there are many datasets and each of them might be suitable for different types of clustering methods, with LKM performing relative well for all datasets.\n\nClarity: The writing clarity is fine, although occasionally there are some flaws such as definition/notation that has not been used again later, typos and so on, but it does not affect reading too much. It has a clear problem definition and algorithm description. That being said, I'm not very impressed with the organization of the paper. \n- The paper spent enough space on problem definition but the paragraphs did not serve to fully motivate this design. For example, previous methods like KSUMS and LKM, whose math formulation, as the authors pointed out, have very similar structure with the one used in this paper, but the authors did not provide intuition about why the differences lead to better performance.\n- The description of the algorithm design is only about one page and I think there should be more intuitive explanation of why this particular design of local objective function (18) might lead to a better solution and make it robust against outliers. \n\nSignificance: This paper could potentially propose a solution that advances state-of-the-art, but the comparsion between the new algorithm and previous approaches does not seem to convince people of its superiority. Also, I'm not sure if the improvement is significant enough for this venue.\n\nMinor comments:\n- In abstract, line 5, the authors mentioned \"KSUMS and SC\" without citation and before defining which algorithms these are referring to.\n- line 26, \"For matrix A, we call it indicator matrix\", I don't really see the point of introducing the indicator matrix here, and the notation is not really used again in this paper.\n- line 86, \"where diag(A) = [a11,..., ann]^T\",  A is not used in (7), and I'm not sure about what a11, ..., ann are referring to.\n- In (9), I'm not sure about why is d_ij^{(k)} set as \\gamma otherwise? Can the authors comment on this?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hrs"}, "extra_text": {}}, {"review_id": "E7spRxvYot2", "reviewer": "Reviewer_8H3D", "summary": "This paper introduces a local efficient version of k-means which leverages the KNN graph of the data to compute neighborhoods of data. Extensive empirical results both on synthetic and real data are reported.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Running times are not reported for the results on real data in Table 3. One of the main advantages of the proposed method is gained efficiency with respect to the clustering competitors, therefore running times should be reported and discussed. \n\nThe proposed method LKM also depends on the initialization of the clustering y, and this is not discussed. It's unclear whether the results on simulated data in Table 1 are averages of different runs or not. This is not discussed and it should. Results should be averages and standard deviations should also be reported.\n\nIt is well-known that k-means is sensitive to outliers, but it's unclear in Figure 3(b) why the performance of k-means is poor in this case. It seems it was still able to detect the four clusters in the data?\n\nIn Section 3, the definition of neighborhood of a point is confusing and not necessarily correct. The notion of neighbor is not symmetric: x_j may be a neighbor of x_i, but not vice versa. \n\nI don't find the analogy of KNN graph with social networks particularly useful or insightful. They are not quite the same concept, really. The paper can instead be improved by discussing related work on exemplar-based approaches aimed at making clustering more robust. See for example recent work on regularized NMF methods which leverage the KNN graphs of the data, e.g. Mani et al, Unsupervised Selective Manifold Regularized Matrix Factorization, SDM 2021, and related work.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations related to the construction of the KNN graph are discussed. No potential negative societal impact is expected.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "1WKTb7TUo_9", "reviewer": "Reviewer_bmZT", "summary": "The authors use a reformulation of the k-means objective to propose an algorithm that minimizes that objective (or some relaxation thereof), and then show some experiments that indicate promising clustering performance.  Currently I believe the paper needs revision before acceptance: the empirical results are not particularly compelling as they omit runtimes on real-world datasets, and the theoretical results do not factor in or bound the number of iterations of the algorithm.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Hello authors,\n\nThank you for your submission.  I enjoyed reading it and I think there are some nice ideas contained in the paper.  However, I have a number of concerns that keep me from recommending acceptance for this paper.  Primarily, my biggest concern is the given runtime bound (which I find inaccurate as it does not count the number of iterations), and the experimental evaluation: runtime analysis is a very important measure of the utility of an algorithm, and this is missing for the real-world datasets.\n\nMore details below (in no particular order):\n\n1. The computational complexity does not consider the number of iterations before convergence.  Therefore I find the claim that the algorithm takes $O(nc)$ time (or rather $O(n(k + c))$ where $c$ is the number of clusters and $k$ is the number of distances known per point) misleading or incorrect.  In fact, Lloyd's algorithm also takes $O(nc)$ per iteration, but the number of iterations is not easily bounded.  Unless the authors can conclusively show that the number of iterations should not be considered in the runtime, this claim must be modified or retracted.\n\n2. As pointed out in the introduction, the initialization of k-means can make a huge difference for performance.  However, on line 204 the authors simply write \"K-means is initialized in a random way\"---but what is this random way?  If I were to, e.g., randomly assign points to clusters to initialize, this can lead to very poor results and slow convergence, at least for Lloyd's algorithm.  Even\nrunning many trials of this strategy will produce poor performance for every strategy.  Thus proper initialization is very important.  It would be very helpful if the authors could provide more information on this point.\n\n3. The authors have not provided any information on runtime on real-world datasets.  Thus it is difficult to evaluate the utility of the proposed algorithm, LKM.  Clustering algorithms often behave very differently on diverse datasets, and thus I think that runtimes only on the toy dataset---and only comparing with Lloyd's algorithm---does not give a full picture.  In fact, the number of iterations on the toy datasets is very small when compared to what Lloyd's algorithm will do on higher-dimensional real datasets (where cluster boundaries are not so clear-cut).  For the sake of clarity, the authors should address the issue of runtime comprehensively on real-world datasets.\n\n4. It would also be nice to include some information on the dimensionality and number of points in each dataset listed in 4.2.1 in the main paper, if possible.  I appreciate that 16 datasets are used---this seems like a fairly comprehensive set of experiments---but I suspect most readers will not have an idea of what the characteristics of these datasets are, and many will not look at the\nsupplemental material.  When I consult the supplementary material, I see that many of the datasets used are relatively high-dimensional; the minimum dimension appears to be 256.  I would suggest that the authors also try on lower-dimensional data (e.g. below 50 dimensions), as convergence characteristics of different algorithms tend to be very different in lower dimensions.\n\n5. A note about the limitations: there are many techniques to quickly construct k-NN graphs.  In lower dimensions, this can be done via trees (see, e.g., [1-3]); in higher dimensions, this can be done approximately via hashing (e.g., [4-5]).  In fact even if only a similarity function is used, so long as that function is a kernel, additional branch-and-bound techniques could be used ([6-8]).  Anyway, perhaps you will find these interesting, if you were not already aware of those lines of work.\n\n6. When comparing Lloyd's algorithm to LKM, note also that there are several variants of Lloyd's algorithm that produce exactly the same result in accelerated time.  The authors even cite some (reference [11]).  There are more however, especially Elkan's [9] and Hamerly's [10] that perform very well in practice that should probably be considered in an empirical comparison.  Personally, if I am doing k-means in practice, I often don't bother with the standard Lloyd algorithm because Elkan's or Hamerly's variants (or the\ntree-based ones) are so much faster---it can often be an orders-of-magnitude speedup.\n\n7. Can more detail be provided in Algorithm 1 on how y is initialized randomly?  Is the algorithm uniformly randomly drawing a cluster assignment for each point?\n\n8. I think the paper could benefit from some careful proofreading.  There are numerous grammatical issues, especially having to do with tenses (present/past/etc.).\n\n9. The suggestion in Eq. (10) to convert a (non-metric) similarity function to a dissimilarity function still produces a non-metric: it is not guaranteed to satisfy the triangle inequality.  This makes the change from Eq. (8) (which is built on distances using D) to Eq. (11) (which is built on dissimilarities using G) significant: particularly, I am no longer certain that we are solving the same problem as (3).  I am okay with the fact that LKM solves a relaxation of (3) but I think this should be explicitly pointed out.  On the other hand, note that if the similarity function is a kernel, then it *does* induce a distance metric in kernel space, and that could be used instead.  Specifically, Eq. (2.2) in [8] uses this induced distance metric.\n\n[1] \"N-Body'problems in statistical learning\", NIPS 2001\n[2] \"Tree-independent dual-tree algorithms\", ICML 2013\n[3] \"Random projection trees and low dimensional manifolds\", STOC 2008\n[4] \"Near-optimal hashing algorithms for approximate nearest neighbor in high\ndimensions\", FOCS '06\n[5] \"LSH Forest: Practical Algorithms Made Theoretical\", SODA 2017\n[6] \"Asymmetric LSH (ALSH) for sublinear time maximum inner product search (MIPS)\", NIPS 2014\n[7] \"Maximum inner-product search using cone trees\", KDD 2012\n[8] \"Fast Exact Max-Kernel Search\", SDM 2013\n[9] \"Using the triangle inequality to accelerate k-means\", ICML 2003\n[10] \"Making k-means even faster\", SDM 2010\n\nI hope that these comments are helpful!", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't think that a new clustering algorithm has either positive or negative societal impact.  So everything seems fine here.", "review_text": "", "extra_scores": {"ethical_concerns": "I have no ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces faster algorithms for clustering.  The paper has some good insights, but ultimately the reviewers were not convined that there is a regime in which the tradeoffs of LKM (their algorithm) actually make sense compared to the existing state of the art.  Due to this, the paper falls below the competition at NeurIPS. 
Decision: Reject