Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: In this paper, the authors provided the pitfalls of Wasserstein K-means via giving the examples and theoretical proof, and proposed a distance-based formulation of K-means in the Wasserstein space.  In addition, the authors conduct a set of experiments on real and simulation data examples to evaluate the proposal. The main contributions are:
1. The authors analyze the irregularity and non-robustness of barycenter-based formulation of K-means theoretically and empirically.
2. To escape the pitfalls of the Wasserstein space, the authors generalize the distance-based formulation of K-means to the Wasserstein space.

strengths_and_weaknesses: Strengths:
1. The proposed problem is worth exploring
2. The research is meaningful 
Weaknesses:
1. In this paper, the authors claim that they provide evidence for pitfalls of barycenter-based Wasserstein K-means, but I cannot find the details of proof for the irregularity and non-robustness.
2. Experiments are not enough. My main concern is the experiments in this paper. The authors conduct a set of experiments on real and simulation data examples to evaluate the proposal. However, the authors only conduct experiment on one real-world dataset and use error rate to evaluate the proposal. Using more datasets, and considering the imbalanced datasets, adding the F1 score can be more convincing. 

questions: 1. Please further add the experiments of this paper.
2. Please include the detailed proof of the pitfalls. 
3. The conclusion section may be missing. Please include this section in the end of this paper.

limitations: In this paper, the authors only consider the two categories problem, and conduct the experiments on the real-world dataset. The multiple categories problem also should be considered.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper uses k-means like algorithm to cluster probability measures using 2- Wasserstein metric. k-means clustering can be formulated in two ways 1) Centroid Based and 2) Distance based . Both formulations are equivalent in the Euclidean space however in the Wasserstein space the same is not true. The authors show that in the Wasserstein space centroid based k-means is much inferior to the distance based version due to irregularity and non-robustness. This is shown using well crafted examples. The authors empirically demonstrate the superiority of the distance based version. In addition the authors also give an SDP relaxation of the distance based k-means in Wasserstein space and show both theoretically and empirically that when the clusters are well separated , the SDP relaxation formulation can recover the clusters exactly with high probability.
strengths_and_weaknesses: Strengths:
1) The paper appears technically sound. I did not check the proofs but the main theorem and other results appear correct.
2) Clustering is a very important problem in Machine learning and hence extending a popular algorithm like k-means to another non-Euclidean metric space, backed with a nice theoretical result will be of interest to the community.
3) The use of examples with accompanied figures to highlight the important results is appreciable and aids understanding.

Weaknesses:
1) The paper is difficult to follow for a person not having background knowledge of Wasserstein space. For example terms like Alexandrov curvature, optimal transport map etc. are used without giving additional information or definition. I believe adding a bit more background information and details of notations used will go a long way in improving the readability of the paper for broader audience. 
2) Experiments are done on very small data and also only for k values 2 and 4. More experiments with different values of k and larger datasets (may be more clusters from MNIST ) will strengthen the paper.
3) Related work for clustering of probability distributions is discussed very briefly. It would be good if the authors can cite works on clustering probability distributions in general (if available) and compare and contrast the Wasserstein k-means method.
questions: 1)Did you compare the empirical results with Euclidean k-means algorithm as baseline, used on the probability distribution vectors?
2) Do you try some experiments with distributions other than Gaussian? Are there any results on exact recovery for other probability measures?
limitations: see the above sections
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Paper studies the behavior of two formulations of Wasserstein-K-means: i) a centroid based ii) a distance based formulation. It shows that the centroid-based formulation can have some unexpected behaviors and illustrates the phenomenon on several toy examples. A SDP formulation of the distance based formulation is then proposed in order to speed up the computations. Experiments on simulated data are given, together with a simple real-data application on a MNIST clustering scenario. 
strengths_and_weaknesses: Strengths of the paper :
- the paper highlight an interesting behavior of the Wasserstein-k-means, advocating for the use of the distance-based formulation rather than the centroid based one (exhibiting some cases in which they lead to different solutions in the Wasserstein space). To my knowledge, this analysis is new. 
- Illustrations are provided, allowing better understanding the behavior in some specific cases.

Weaknesses:
- The paper advocates the use of the distance-based formulation but the scenarii that are considered seem rather limited. An in-depth analysis of the cases in which the difference appears and matters is lacking. For instance, it seems that it is related to « unbalanced » scenario, that is to say when the different cluster sizes are different. This behavior should be better investigated. 
- the complexity analysis of the algorithm is not provided. 
- The experimental section is rather limited, with one simple illustration on a MNIST clustering (digit 0 vs. digit 5) provided. 

questions: See above
limitations: As far as I can see, there is no potential negative societal impact of the work.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper performs studies on three different implementations of K-means clustering for probability distributions. Conventionally, the problem was solved by finding barycenters. The authors point out that such approaches are unsuitable because of two pitfalls in Wasserstein barycenters. In contrast, the alternative implementations with pairwise distances and SDP relaxation can provide better clustering results.

strengths_and_weaknesses: Strength:
The work points out the difference between Wasserstein K-means and conventional K-means. Good examples are provided. Through the paper, readers can realize the difficulty due to the Wasserstein barycenters, and future research efforts should be devoted to non-barycenter-based clustering algorithms.

Weakness:
Most illustrative examples are small and artificial. Although distance-based and SDP-based approaches work better for such examples, it is hard to say they are the future for the research problem because they are not scalable.

questions: The proposed distance-based and SDP-based approaches do not include barycenters or means as optimization variables. Can they still be called "K-means"?


Although the proposed alternatives work better in the given examples, they are more expensive for large-scale data sets because they have a quadratic cost to the number of instances. Optimizing over the cluster membership also makes them more difficult to parallelize. All given examples are small and cannot reveal the drawback. The whole MNIST data set has 70,000 images, but the authors picked only a few hundred.

How did the authors obtain the pairwise distances for MNIST?
limitations: In the checklist, the authors claimed that they described the limitations of their work but did not say where. There is no discussion or conclusion section in the paper, and I cannot find any relevant part for the limitations.
review_title: null

Meta-review: metareview: This paper provides a Wasserstein-based k-means formulation for clustering probability distributions. Though the overall reception was mildly positive but two reviewers raised their scores following the author feedback. There remains some doubts that there is enough evidence to support all claims in the paper--most relevant, referees have noted to us that fundamentally a strong empirical validation is lacking. We recommend revising the paper and focusing on a strong empirical narrative (without relegating new details to the appendix), together with improving the exposition as outlined by reviewers
confidence: Less certain
Decision: Accept