Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.


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. 

The 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.

It 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?

In 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. 

I 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.

limitations_and_societal_impact: Limitations related to the construction of the KNN graph are discussed. No potential negative societal impact is expected.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
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.

Originality: 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.

Quality: 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:
- 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?
- 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.

Clarity: 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. 
- 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.
- 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. 

Significance: 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.

Minor comments:
- In abstract, line 5, the authors mentioned "KSUMS and SC" without citation and before defining which algorithms these are referring to.
- 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.
- 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.
- In (9), I'm not sure about why is d_ij^{(k)} set as \gamma otherwise? Can the authors comment on this?

limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.


main_review: Strengths:

LKM 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. 
Specifically, the computational overhead is O(nk), where n and k denote the number of samples and nearest neighbors, respectively.

In 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.

Weaknesses:
1. Line 9: "Specifically....are denote the...". The sentence is grammatically incorrect, "are" should be removed.

2. Some works relating to the connection between k-means and clustering with graph cuts are not discussed in Section 2 (Related work).

3. The performance of SC optimized by the proposed algorithm is not shown.

4. What does \bar{y} stand for in Eq. (15) and (16)?

5. e_i should be a column vector.

6. Some steps in the derivations are not explained. What is the connection between (11) and (17)? 

7. 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.

8. Have the paper proof-read to remove grammatical errors

9. In page 7, line 178, "#Iter" should be "#Iter.".

10. In page 7, table 2, "FLK" should be "LKM".

11. References should be shown in the same format.

**comment after rebuttal**
I 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.


limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.
main_review: Hello authors,

Thank 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.

More details below (in no particular order):

1. 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.

2. 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
running 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.

3. 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.

4. 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
supplemental 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.

5. 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.

6. 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
tree-based ones) are so much faster---it can often be an orders-of-magnitude speedup.

7. 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?

8. I think the paper could benefit from some careful proofreading.  There are numerous grammatical issues, especially having to do with tenses (present/past/etc.).

9. 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.

[1] "N-Body'problems in statistical learning", NIPS 2001
[2] "Tree-independent dual-tree algorithms", ICML 2013
[3] "Random projection trees and low dimensional manifolds", STOC 2008
[4] "Near-optimal hashing algorithms for approximate nearest neighbor in high
dimensions", FOCS '06
[5] "LSH Forest: Practical Algorithms Made Theoretical", SODA 2017
[6] "Asymmetric LSH (ALSH) for sublinear time maximum inner product search (MIPS)", NIPS 2014
[7] "Maximum inner-product search using cone trees", KDD 2012
[8] "Fast Exact Max-Kernel Search", SDM 2013
[9] "Using the triangle inequality to accelerate k-means", ICML 2003
[10] "Making k-means even faster", SDM 2010

I hope that these comments are helpful!
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_title: null

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