Local K-means: An Efficient Optimization Algorithm And Its Generalization
Year: 2021

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

Until now, k-means is still one of the most popular clustering algorithms because of1 its simplicity and efficiency, although it has been proposed for a long time. In this2 paper, we considered a variant of k-means that takes the k-nearest neighbor (k-NN)3 graph as input and proposed a novel clustering algorithm called Local K-Means4 (LKM). We also developed a general model that unified LKM, KSUMS, and SC,5 and discussed the connection among them. In addition, we proposed an efficient6 optimization algorithm for the unified model. Thus, not only LKM but also SC can7 be optimized with a linear time complexity with respect to the number of samples.8 Specifically, the computational overhead is O(nk), where n and k are denote the9 number of samples and nearest neighbors, respectively. Extensive experiments10 have been conducted on 11 synthetic and 16 benchmark datasets from the literature.11 The effectiveness, efficiency, and robustness to outliers of the proposed method12 have been verified by the experimental results.13
1 Introduction14
Clustering is one of the fundamental tasks of machine learning [10]. It plays a very important role in15 many applications such as document analysis [6], image processing [14], and recommender system16 [12]. Given a dataset with n samples and the number of clusters c, its purpose is to split these samples17 into c disjoint groups, so that the samples within the same group are similar to each other, and the18 samples between different groups are not. Although there are lots of clustering algorithms have been19 proposed, k-means is still getting a lot of attention. In this paper, we proposed an efficient clustering20 method called local k-means where a k-NN graph is taken as input. It can be seen as a variant of21 traditional k-means. In the following, the two basic materials of our model are firstly described, and22 the main contributions of this article will be mentioned at the end of this section.23
Notations: Bold capital letters and bold lowercase letters denote matrices and vectors, respectively.24 The symbols n, d, and c are respectively used to represent the number of samples of the dataset, the25 number of features, and the number of clusters to construct. For matrix A, we call it indicator matrix,26 if each row of it has only one element equal to 1. Φn×c is the set of all indicator matrices.27
1.1 k-means28
As one of the most popular clustering algorithms, k-means aims to group n samples into c clusters29 where each sample belongs to the cluster with the nearest cluster centers. Let X = [x1, · · · ,xn]T ∈30 Rn×d be a collection of samples to cluster, where xi ∈ Rd denotes the i-th sample. Then the objective31 function of k-means can be formulated as32
min A1,··· ,Ac c∑ k=1 ∑ xi∈Ak ‖xi −mk‖22, (1)
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.
where Ak denotes the set of samples in the i-th cluster, A1 ⋃ · · · ⋃ Ac = {xi | i = 1, · · · , n}, and33 mk denotes the mean of samples in Ak.34 Although the problem in Eq. (1) is computationally difficult, 1 many efficient optimization algorithms35 where a local optimum will be found quickly have been proposed. Among them, Lloyd’s algorithm is36 the most widely used. Let Y = [y1, · · · ,yn]T = [ȳ1, · · · , ȳc] ∈ Rn×c be an indicator matrix, i.e.,37
yij = { 1 xi ∈ Aj 0 otherwise , i = 1, · · · , n, j = 1, · · · , c, (2)
the problem in Eq. (1) can be then rewritten as38 min Y ‖X−YM‖22, (3)
where M = (YTY)−1YTX. In Lloyd’s algorithm, Y and M are regarded as two independent39 variables and be optimized alternately.40
1.2 Data in the form of graph41
In fields such as social networks and recommendation systems, the data being studied is often42 presented in the form of graphs. In other words, for a single sample, we have no features to describe43 it, what we have is only the relationship between it and others, as shown in Figure 1.44
In generally, a sparse similarity matrix W ∈ Rn×n can be used to describe this kind of data, i.e.,45
wij =
{ f(xi,xj) If xi and xj are directly connected
0 Otherwise , i, j = 1, · · · , n, (4)
where f(xi,xj) represents the similarity between xi and xj , and its value can be usually obtained46 directly.47
Based on the above discussion, a k-means-like algorithm is proposed, which takes the k-NN graph48 as input and can be quickly optimized. In addition, we also discussed its connection with other49 algorithms, such as KSUMS and spectral clustering. Here, we summarize the main contributions of50 the article as follows51
• A novel clustering algorithm called Local K-Means (LKM) is proposed. Because only the52 distances between the sample and its neighbors are considered, LKM is robust to outliers.53 • The relationship between LKM and other algorithms (KSUMS and SC) is discussed, and a54 unified model is established.55 • An efficient optimization algorithm for the unified model is developed, from which we find56 that the spectral clustering model can be optimized in the same way as LKM, which means57 both of them can also be optimized in O(nk) time.58
1Specifically, it is an np-hard problem.
2 Related work59
A disadvantage of k-means is that its performance will be affected largely by the initialization of60 the cluster center. To this end, a lot of efforts have been made, such as [2, 4, 3]. In these methods,61 the cluster center is carefully initialized through a special process. In addition to the more robust62 clustering result, an improvement of performance can also be achieved. More related work can be63 found here [15, 22].64
Since the computational complexity of k-means involves the product of the number of samples65 and clusters, it will be very time-consuming if the two numbers are very large. With the help of66 techniques that used to accelerate the nearest neighbor search, the nearest center for each sample67 can be quickly found without computing distances to all centers [25, 11]. [7] developed a fast68 implementation of k-means using coreset. A partition on a small coreset is computed firstly and is69 used as an initialization on a larger coreset. In [32], Xia et al. described each cluster by a ball and70 proposed Ball k-means which accelerated k-means by reducing the computation of distances between71 samples and centers. [13] proposed compressive k-means (CKM) where the centers are estimated72 from a sketch (a compressed representation of the original data). Once the sketch is obtained, the73 computational overhead is then independent of the size of the original data. Moreover, it’s also a hot74 spot to use the advantages of GPU to shorten the time consumed by k-means, such as [17] and [5].75
Clustering on graph data is also a hot topic. Some well-known algorithms include [19, 29, 21].76 However, these algorithms often have a time complexity that increases quadratically with respect to77 the number of samples. To this end, many fast versions of them are proposed [33, 20, 9].78
3 The proposed model79
In our article, how to solve the problem in Eq. (1) has not been paid attention to, but some simple80 derivations are firstly made on it. Therefore we can analyze the meaning of the problem from the81 perspective of a distance graph. For convenience, we define Nk(xi) = {xj | xj is among the82 k-nearest neighbors of xi or xi is among the k-nearest neighbors of xj}, and start from the following83 equivalent form of k-means84
min A1,··· ,Ac c∑ k=1 1 |Ak| ∑ xi,xj∈Ak ‖xi − xj‖22, (5)
With the help of the definition of Y in Eq. (2), problem (5) can be equivalently expressed as follows85
min Y∈Φn×c
diag ( (YTY)−1 )T diag ( YTDY ) , (6)
⇔ min Y∈Φn×c
Tr ( (YTY)−1YTDY ) , (7)
where diag(A) = [a11, · · · , ann]T . Obviously, if we only consider the distances between the sample86 and its neighbors, then the problem in Eq. (7) can be expressed as87
min Y∈Φn×c
Tr ( (YTY)−1YTD(k)Y ) , (8)
with88
d (k) ij =
{ ‖xi − xj‖22 if xi ∈ Nk(xj)
γ Otherwise , (9)
where γ is the maximum value of set {‖xi − xj‖22 | xi ∈ Nk(xj), i = 1, · · · , n}. The Equation (8)89 is the final objective function of LKM.90
From the discussion in Section 1.2, we know that only the similarity instead of the distance between91 samples can be obtained directly in graph data. Fortunately, in practical applications, we can convert92 the similarity to dissimilarity by93
rij =
{ −log(sij) 0 < sij
β sij = 0 , (10)
where sij is the normalized2 similarity between xi and xj , β is the maximum value of set {−log(sij) |94 i, j = 1, · · · , n}. Then the dissimilarity can be used to replace the distance in the model.95
2sij ∈ [0, 1]
3.1 Generalization96
It is not difficult to find that LKM, KSUMS [23], and Ratio-cut [29] can all be represented uniformly97 by the following model98
min Y∈Φn×c
Tr ( (YTY)−pYTG(k)Y ) , (11)
where g(k)ij denotes the dissimilarity or distance between xi and xj , and p >= 0 is a parameter. The99 meaning of p will be explored in future work.100
Instances of KSUMS and LKM: The objective function of KSUMS is101
min Y∈Φn×c
Tr ( YTD(k)Y ) , (12)
where D(k) takes the same expression as that in LKM. Let g(k)ij be setted by Eq. (9), the problem (11)102 is identical with KSUMS (12) if p = 0, and is identical with LKM if p = 1.103
Instance of Ratio-cut: Benefiting from the introduction of Y, the problem of ratio-cut (an algorithm104 that belongs to the spectral clustering (SC) family) can be expressed as105
min Y∈Φn×c
Tr ( (YTY)−1YT (∆−W)Y ) , (13)
where ∆ is a diagonal matrix, ∆ii = ∑n j=1 wij . In generally, the similarity matrix W can be106
determined by heat kernel, i.e., wij = e− ‖xi−xj‖ 2 2
t if xi ∈ Nk(xj), wij = 0 otherwise. Therefore the107 problem (11) is equivalent with ratio-cut, if p = 1 and g(k)ij is setted by108
g (k) ij =  ∑n j=1 wij i = j −wij i 6= j, and xi ∈ Nk(xj)
0 Otherwise . (14)
3.2 Optimization109
From the discussion above, we know that the problem of LKM can be expressed by Eq. (11) with110 p = 1. Therefore, an optimization algorithm for problem (11) instead of problem (8) is developed.111 To begin with, some notations are presented as follows112
si , ȳ T i G (k)ȳi, i = 1, · · · , c, (15) ni , ȳ T i ȳi, i = 1, · · · , c, (16)
the problem (11) then becomes113
min Y∈Φn×c Obj(Y), with Obj(Y) = c∑ i=1 si npi . (17)
In the following derivation, the i-th row of Y (i.e., yi) is regarded as the variable to be optimized114 while others are fixed, and yi = eα before updated. Thus yi can be updated by115
yi = eβ , β = arg min j
Obj(yi = ej)−Obj(yi = 0), (18)
where ei = [0, · · · , 1, · · · , 0] be a vector with all elements equal to 0, except the i-th, which is 1, and116 0 is the column vector of all zeros,117
Because Obj(yi = 0) is constant, the above formula holds. According to Eq. (17), we have118
Obj(yi = ej)−Obj(yi = 0) =  sj+bj (nj+1)p − sj npj j 6= α
sj npj − sj−bj(nj−1)p j = α
, j = 1, · · · , c, (19)
with119
bj =
{ 2 ∑
xl∈Aj g (k) il + g (k) ii j 6= α 2 ∑
xl∈Aj g (k) il − g (k) ii j = α
, (20)
Algorithm 1: An efficient program for solving problem (11). Note: The vector y ∈ Rn denotes the clustering result, i.e., yi is the cluster that xi belongs to. The Eq. (15), (16), and (20) involved in the algorithm have high computational complexity, but these can be computed more efficiently if the sparsity of G(k) is considered. See the supplementary material for a more detailed algorithm; Data: Sparse matrix 3G(k) ∈ Rn×n, the number of cluster c Result: The clustering result y Initialize y randomly; Compute vector s and n by Eq. (15) and (16), respectively; while not converge do
for i = 1, · · · , n do Compute bj by Eq. (20) for j ∈ Bi; Compute Obj(yi = j)−Obj(yi = 0) by Eq. (19) for j ∈ Bi; Update yi by Eq. (18); Update s and n by Eq. (21) and Eq. (22), respectively;
Benefiting from the sparsity of G(k), it takes O(nk), O(k + c), and O(k) time to compute s, b, and120 n, respectively. Therefore, the proposed optimization algorithm has a computational complexity of121 O(n2k + nc), which is unbearable, for large-scale datasets. However, if the variables s and n are122 computed in advance and updated following the update of yi, then the computational complexity of123 the algorithm can greatly be reduced. The update rules for s and n are as follows124
sα ⇐ sα − bα, sβ ⇐ sβ + bβ , (21) nα ⇐ nα − 1, nβ ⇐ nβ + 1, (22)
Thus, the computational complexity of the optimization algorithm is O(n(k + c)).125
On more step From Eq. (11), we know that only the information of pair (xi,xj) is considered in126 the model, and there are at most 2nk such pairs. For convenience, we assume that there are exactly127 2k such pairs for each sample xi, i.e., 2k = |{(xi,xj) | xj ∈ Nk(xi) or xi ∈ Nk(xj)}|. For cluster128 j, we call it an element of Bi (j ∈ Bi), if there is at least one sample in cluster j belongs to Nk(xi)129 or xi belongs to the set of neighbors of these samples. Based on the assumption and notations above,130 we know that when updating yi by Eq. (18), the size of Bi is at most 2k. However, it does not make131 sense to group the sample xi into cluster j 6∈ Bi, from the perspective of the performance. Therefore,132 we only need to pay attention to the cases where j ∈ Bi. Thus, the computational complexity of the133 optimization algorithm can be reduced to O(nk).134
Time and space complexity From Algorithm 1, we can see that the memory is mainly occupied135 by the matrix G(k) ∈ Rn×n, which is equivalent to a sparse matrix, and contains at most 2nk136 non-constants. The memory overhead caused by other variables is O(n) at most. For example, y,137 Bi, and s require O(n), O(k), and O(c) memory, respectively. Thus the memory overhead of LKM138 is O(nk). Benefiting from the sparsity of G(k), Eq. (15), (16), and (20) can all be calculated more139 efficiently. Specifically, only O(nk), O(n), and O(k) time are needed respectively, please refer to the140 supplementary materials for details. After yi is updated, only O(1) time is needed to update variables141 s and n. Thus, the computational complexity of LKM is O(nk).142
4 Experiments143
In this section, the performance of the proposed algorithm, LKM, is verified on eleven synthetic144 datasets and sixteen benchmark datasets. The rest of this section is organized as follows: First,145 experiments on synthetic datasets are shown. In short, Mickey, Outlier, and family of Grid datasets146 are used to verify the effectiveness, robustness, and efficiency of LKM, respectively. Then, we147 compare 7 popular clustering algorithms with LKM on 16 benchmark datasets, to evaluate the148 performance of the proposed algorithm.149
3Strictly speaking, G(k) is not a sparse matrix. However, at most 2nk values in G(k) are not equal to λ, so it can be regarded as a sparse matrix.
4.1 Experiments conducted on synthetic datasets150
Experiment on “Mickey” To verify the effectiveness of LKM, a synthetic dataset called “Mickey”151 is constructed. The distribution of points is shown in Figure 2(a). The triangles representing the152 means of the clusters are not points of the datasets.153
From Figure 2(b) and 2(c), we found that The proposed method LKM successfully found the154 cluster structure, but k-means did not. k-means still cannot find the correct structure, even with the155 initialization of the ground truth label. Because the distance between point 1 and the blue triangle156 (mean of all blue points), d1 is greater than the distance between point 1 and the orange triangle (mean157 of all orange points), d2, k-means will group it into the blue cluster instead of orange. Therefore,158 k-means cannot handle datasets like this.159
Experiment on “Outlier” In order to verify the robustness of our method, we construct a dataset160 called “Outlier”. It consists of four clusters with centers (0, 0), (0, 5), (5, 0), and (5, 5), and an outlier161 with the coordinate of (100, 100). The distance between outlier A and other points is not as close as162 shown in Figure 3. From Figure 3(b) and 3(c), we can see that the performance of k-means is severely163 affected by the outlier A, while the performance of LKM is not. In k-means, the center of the cluster164 containing abnormal points will largely shift towards the direction of the abnormal points, resulting165 in poor performance. In LKM, the distance between xi and xj is not calculated if xj 6∈ Nk(xi), but166 a parameter λ is used instead, so ideally, the distance between any two points belonging to different167 clusters is λ. In other words, for the sample point xi, there is no difference between the outlier and168 the samples that do not belong to Nk(xi).169
Experiments on the family of “Grid” In order to verify the efficiency of LKM, in this paragraph,170 9 synthetic datasets called Toy-1, Toy-2, · · · , Toy-9 are constructed. These datasets share the same171 structure, and their distributions are similar to that shown in Figure 4. In these datasets, each cluster172 is always composed of 10 points generated by Gaussian distribution. Since the time complexity of173 LKM and k-means is closely related to the number of points, we set different sizes for these data174 sets, ranging from 1960 to 125440. The number of clusters and the standard deviation involved in the175 Gaussian distribution for each dataset is shown in Table 1.176
In Table 2, the column named “Ball-Tree” represents the time it takes to construct the graph required177 by LKM through Ball-tree with k = 20. The column named “# Iter” denotes the number of iterations178 required for the algorithm to converge. The total time of LKM refers to the sum of the time consumed179 by Ball-Tree and Algorithm 1. The speed-up is the ratio of the time consumed by each iteration of180 k-means to the time consumed by each iteration of Algorithm 1. Both k-means and LKM were run181 50 times, and the average results were reported.182
As shown in Table 2, Algorithm 1 consumes a significantly shorter time than k-means, which is more183 obvious on datasets with more clusters. The main reason is that when yi is going to update, only the184 case where j ∈ Bi is considered. In addition, LKM has a significant improvement in terms of the185 quality of the clustering result, compared to k-means, as shown in Table 1 and Figure 4.186
4.2 Experiments conducted on benchmark datasets187
4.2.1 Datasets188
Sixteen benchmark datasets are used including LFW [8], CPLFW [34], CALFW [35], FERET [24],189 Colon [1], MUCT [18], CMUPIE [30], CFPW [27], Dexter, Madelon, GTDB, FaceV5, Mpeg7,190 Olivetti, Yale, and Umist. All facial datasets are processed by the way [23]. For those non-facial191 datasets, PCA [31] is adopted and some components are selected such that the amount of variance is192 greater than 95% if the dimensionality of the datasets is larger than 1024. The names of datasets are193 all linked to where the dataset can be download. The introduction to these datasets can be found in194 the supplemental material.195
4.2.2 Baselines and experimental settings196
We compare LKM with several clustering algorithms, including AGCI [33], FINCH [26], k-means197 [16], KSUMS [23], RCC [28], SC [29], and FCDMF [20]. For graph-based methods, i.e., KSUMS,198 RCC, and SC, the number of nearest neighbors, k, is fixed at 20. For anchor-based methods, AGCI199 and FCDMF, the number of anchors is always set by m = min(n/2, 1024). Whether k-NN graph200 or anchor graph, heat-kernel is always adopted to construct the graph. In FINCH, we take the201 clustering result with the number of clusters closest to the number of ground truth clusters as the202 final clustering result. In RCC, the threshold to assign points together in a cluster is tuned from203 {0.1, 0.3, 0.5, 0.7, 0.9}. K-means is initialized in a random way and the step of k-means involved in204 AGCI and SC share the same configuration with k-means itself. If the performance of the algorithm205 is related to the initialization, we run it repeatedly 50 times and report the average performance.206
We run all methods on an Arch machine with i7-8700 CPU (3.20 GHz), 32 GB main memory.207
4.2.3 Experimental results208
Clustering ACCuracy (ACC), Normalized Mutual Information (NMI), and Adjusted Rand index209 (ARI) are used to evaluate the performance of these algorithms. From Table 3, we can clearly see that:210 (1) In most cases LKM has achieved the highest performance comparing to several state-of-the-art211 algorithms, which verified the effectiveness of the proposed algorithm. Specifically, LKM exceeds212 the second-best results 24.4%, 4.6%, 4.8%, 1.5% and 1.3% on CALFW, LFW, Umist, Olivetti, and213 CMU respectively, in terms of ACC. Under the metrics of NMI and ARI, we can come to similar214 results. (2) Although only slight improvements LKM has achieved over many datasets compared215 to the second-best results, the computational complexity of LKM is much lower than that of most216 algorithms, which is an important property of LKM. (3) RCC has poor performance on FaceV5,217 CMU, GTdb, Umist, and Yale, which may be caused largely by an inappropriate threshold, while218 only one parameter (the number of neighbors) is needed in LKM, is an integer and easy to tune. In219 addition, the influence of parameter k (the number of neighbors) on clustering performance has been220 studied, and the results are shown in the supplemental material.221
5 Conclusions222
In this paper, we devote ourselves to an unsupervised learning problem, clustering. An efficient223 clustering algorithm called Local K-Means (LKM) was proposed. It can be seen as a variant of224 k-means that takes the k-NN graph as input. We also discussed a general model that unified LKM,225 KSUMS, and SC. Thus the connection among them can be easily established. In addition, we226 developed an efficient optimization algorithm for the unified model, so that not only LKM but also227 SC can be optimized in O(nk) time, which is very important for large-scale datasets, especially for228 these datasets with a large number of clusters. In order to verify the advantages of LKM, extensive229 experiments on eleven synthetic and sixteen benchmark datasets are conducted, and the results have230 shown the effectiveness, efficiency, and robustness of our model.231
Limitations In some cases where k-NN graphs are not available, our algorithm cannot work,232 in other words, a graph construction algorithm is necessary. Although many methods have been233 proposed, it is still very difficult to effectively construct an approximate k-NN graph if the number of234 features is large. Thus, in these situations, the graph construction algorithm will produce a k-NN235 graph of poor quality that would lead to poor performance of clustering results.236
References237 [1] U. Alon, N. Barkai, D. A. Notterman, K. Gish, S. Ybarra, D. Mack, and A. J. Levine. Broad238 patterns of gene expression revealed by clustering analysis of tumor and normal colon tis-239 sues probed by oligonucleotide arrays. Proceedings of the National Academy of Sciences,240 96(12):6745–6750, 1999.241
[2] D. Arthur and S. Vassilvitskii. k-means++: The advantages of careful seeding. Technical report,242 Stanford, 2006.243
[3] O. Bachem, M. Lucic, H. Hassani, and A. Krause. Fast and provably good seedings for k-means.244 In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, editors, Advances in245 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.247 In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pages 1459–1467,248 2016.249
[5] S. Cuomo, V. De Angelis, G. Farina, L. Marcellino, and G. Toraldo. A gpu-accelerated parallel250 k-means algorithm. Computers & Electrical Engineering, 75:262–274, 2019.251
[6] G.R. De Miranda, R. Pasti, and L.N. de Castro. Detecting topics in documents by clustering252 word vectors. In International Symposium on Distributed Computing and Artificial Intelligence,253 pages 235–243. Springer, 2019.254
[7] G. Frahling and C. Sohler. A fast k-means implementation using coresets. International Journal255 of Computational Geometry & Applications, 18(06):605–625, 2008.256
[8] B.H. Gary, R. Manu, B. Tamara, and L.M.r Erik. Labeled faces in the wild: A database for257 studying face recognition in unconstrained environments. Technical Report 07-49, University258 of Massachusetts, Amherst, October 2007.259
[9] L. He, N. Ray, Y. Guan, and H. Zhang. Fast large-scale spectral clustering via explicit feature260 mapping. IEEE Transactions on Cybernetics, 49(3):1058–1071, 2019.261
[10] A.K. Jain, M.N. Murty, and P.J. Flynn. Data clustering: a review. ACM computing surveys262 (CSUR), 31(3):264–323, 1999.263
[11] T. Kanungo, D.M. Mount, N.S. Netanyahu, C.D. Piatko, R. Silverman, and A.Y. Wu. An264 efficient k-means clustering algorithm: Analysis and implementation. IEEE transactions on265 pattern analysis and machine intelligence, 24(7):881–892, 2002.266
[12] R. Katarya and O.P. Verma. An effective web page recommender system with fuzzy c-mean267 clustering. Multimedia Tools and Applications, 76(20):21481–21496, 2017.268
[13] N. Keriven, N. Tremblay, Y. Traonmilin, and R. Gribonval. Compressive k-means. In 2017269 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages270 6369–6373, 2017.271
[14] W. Kim, A. Kanezaki, and M. Tanaka. Unsupervised learning of image segmentation based on272 differentiable feature clustering. IEEE Transactions on Image Processing, 29:8055–8068, 2020.273
[15] M. Li, D. Xu, D. Zhang, and J. Zou. The seeding algorithms for spherical k-means clustering.274 Journal of Global Optimization, pages 695–708, 2019.275
[16] S. Lloyd. Least squares quantization in pcm. IEEE transactions on information theory,276 28(2):129–137, 1982.277
[17] C. Lutz, S. Breß, T. Rabl, S. Zeuch, and V. Markl. Efficient k-means on gpus. In Proceedings of278 the 14th International Workshop on Data Management on New Hardware, pages 1–3, 2018.279
[18] S. Milborrow, J. Morkel, and F. Nicolls. The MUCT Landmarked Face Database. Pattern280 Recognition Association of South Africa, 2010. http://www.milbo.org/muct.281
[19] A.Y. Ng, M.I. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In282 Advances in neural information processing systems, pages 849–856, 2002.283
[20] F. Nie, S. Pei, R. Wang, and X. Li. Fast clustering with co-clustering via discrete non-negative284 matrix factorization for image identification. In ICASSP 2020-2020 IEEE International Confer-285 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. In287 Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and288 Data Mining, KDD ’14, page 977–986, New York, NY, USA, 2014. Association for Computing289 Machinery.290
[22] J. Ortiz-Bejar, E.S. Tellez, M. Graff, J. Ortiz-Bejar, J.C. Jacobo, and A. Zamora-Mendez.291 Performance analysis of k-means seeding algorithms. In 2019 IEEE International Autumn292 Meeting on Power, Electronics and Computing (ROPEC), pages 1–6. IEEE, 2019.293
[23] S. Pei, F. Nie, R. Wang, and X. Li. Efficient clustering based on a unified view of k-means and294 ratio-cut. Advances in Neural Information Processing Systems, 33, 2020.295
[24] P.J. Phillips, H. Wechsler, J. Huang, and P.J. Rauss. The feret database and evaluation procedure296 for face-recognition algorithms. Image and vision computing, 16(5):295–306, 1998.297
[25] S.J. Phillips. Acceleration of k-means and related clustering algorithms. In Algorithm Engineer-298 ing and Experiments, pages 166–177. Springer Berlin Heidelberg, 2002.299
[26] S. Sarfraz, V. Sharma, and R. Stiefelhagen. Efficient parameter-free clustering using first300 neighbor relations. In Proceedings of the IEEE/CVF Conference on Computer Vision and301 Pattern Recognition, pages 8934–8943, 2019.302
[27] S. Sengupta, J. Chen, C. Castillo, V.M. Patel, R. Chellappa, and D.W. Jacobs. Frontal to profile303 face verification in the wild. In 2016 IEEE Winter Conference on Applications of Computer304 Vision (WACV), pages 1–9. IEEE, 2016.305
[28] S.A. Shah and V. Koltun. Robust continuous clustering. Proceedings of the National Academy306 of Sciences, 114(37):9814–9819, 2017.307
[29] J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern308 analysis and machine intelligence, 22(8):888–905, 2000.309
[30] T. Sim, S. Baker, and M. Bsat. The cmu pose, illumination, and expression database. IEEE310 Transactions on Pattern Analysis and Machine Intelligence, 25(12):1615–1618, 2003.311
[31] M.E. Tipping and C.M. Bishop. Probabilistic principal component analysis. Journal of the312 Royal Statistical Society: Series B (Statistical Methodology), 61(3):611–622, 1999.313
[32] S. Xia, D. Peng, D. Meng, C. Zhang, G. Wang, E. Giem, W. Wei, and Z Chen. A fast adaptive314 k-means with no bounds. IEEE Transactions on Pattern Analysis and Machine Intelligence,315 pages 1–1, 2020.316
[33] Y. Zhao, Y. Yuan, and Q. Wang. Fast spectral clustering for unsupervised hyperspectral image317 classification. Remote Sensing, 11(4):399, 2019.318
[34] T. Zheng and W. Deng. Cross-pose lfw: A database for studying cross-pose face recognition319 in unconstrained environments. Technical Report 18-01, Beijing University of Posts and320 Telecommunications, February 2018.321
[35] T. Zheng, W. Deng, and J. Hu. Cross-age LFW: A database for studying cross-age face322 recognition in unconstrained environments. CoRR, abs/1708.08197, 2017.323
Checklist324
1. For all authors...325 (a) Do the main claims made in the abstract and introduction accurately reflect the paper’s326 contributions and scope? [Yes]327 (b) Did you describe the limitations of your work? [Yes]328 (c) Did you discuss any potential negative societal impacts of your work? [N/A]329 (d) Have you read the ethics review guidelines and ensured that your paper conforms to330 them? [Yes]331 2. If you are including theoretical results...332
(a) Did you state the full set of assumptions of all theoretical results? [N/A]333 (b) Did you include complete proofs of all theoretical results? [N/A]334
3. If you ran experiments...335 (a) Did you include the code, data, and instructions needed to reproduce the main experi-336 mental results (either in the supplemental material or as a URL)? [Yes]337 (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they338 were chosen)? [Yes]339 (c) Did you report error bars (e.g., with respect to the random seed after running experi-340 ments multiple times)? [Yes]341 (d) Did you include the total amount of compute and the type of resources used (e.g., type342 of GPUs, internal cluster, or cloud provider)? [Yes]343 4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...344
(a) If your work uses existing assets, did you cite the creators? [Yes]345 (b) Did you mention the license of the assets? [No]346 (c) Did you include any new assets either in the supplemental material or as a URL? [No]347 (d) Did you discuss whether and how consent was obtained from people whose data you’re348 using/curating? [Yes]349 (e) Did you discuss whether the data you are using/curating contains personally identifiable350 information or offensive content? [No]351 5. If you used crowdsourcing or conducted research with human subjects...352
(a) Did you include the full text of instructions given to participants and screenshots, if353 applicable? [N/A]354
(b) Did you describe any potential participant risks, with links to Institutional Review355 Board (IRB) approvals, if applicable? [N/A]356
(c) Did you include the estimated hourly wage paid to participants and the total amount357 spent on participant compensation? [N/A]358

Review summaries:
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.  

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.