Venue: NeurIPS 2022 Conference

Reviews:

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: 
The authors propose a branch and bound approach to solving the K-mediod problem by taking advantage of the Lagrangian relaxation method explored by Cornuejols in
 the 70's. In particular, they modify the lagrangian relaxation for each cluster by building appropriate boxes for the BB scheme and provide various speedups by
probing, feasibility based bound tightening and parallelization. Experiments are shown on a wide variety of datasets.

strengths_and_weaknesses: The paper is clearly written with references to related work and is easy to follow. The theoretical results are shown in the main paper with the proofs delegated
 to the supplementary. Additional experiments with varying sizes of clusters are also provided.

The problem is of broad interest since clustering is a core component of many machine learning tasks. The key ideas of using Lagrangian relaxtion and branch and
bound techniques have been explored in the broader literature but combining them in the context K-mediods problem along with mediods on samples constraint makes
it novel and relevant.      

The paper pretty much builds on the work of Cornujols et al as well as the branch/bound literature and the proofs of finite termination/global optimum are provided.  Most of the literature for the relevant work is covered and referenced in the paper.

questions: (A) How does the scaling look like in terms of the dimensions d? Also, in general what is the computational complexity of the proposed algorithm? Of course, it w
ould depend on the number of the branch and bound steps. 

(B) The algorithm seem to be more sensitive to dimensions than to samples in terms of performance (Table 2). Is that really true and if so, any reason why that could be the case?

limitations: The key reason it works is because of the Lagrangian relaxation available to the K-mediod setting and it is not clear if this will extend to other clustering problems. Can the authors shed some light as to where else this could be applicable?
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: The paper presents a spatial branch-and-bound method for the K-medoids clustering problem. The authors introduce several bound tightening techniques tailored for their approach. In numerical experiments they demonstrate that their method is able to solve large scale instances of the problem to global optimality.
strengths_and_weaknesses: The paper makes a strong technical contribution to a computationally challenging problem. The writing is clear and concise, the numerical results are significant. Overall it's a good paper with only few flaws.
questions: The presentation of the results is mostly clear, but I have a few questions/comments:

In lines 96-97 you are mentioning that the value $d_{s,j}$ are precomputed. However, the number of values scales quadratically with the size of  the data set, which seems intractable for the claimed size of 1M samples. How do you deal with this issue?

In line 130, the authors define $S^{k+}$ as the set of indexes whose samples are contained in the $k$-th medoid constraint set. Then, in equation (9) we consider the union $S^+ = S^{1+} \cup \dotso \cup S^{K+}$, which should just be the set of all sample indexes. Can you please make your notation more clear as to what you actually mean here?

In line 166 please clarify the notation $\mathrm{mid}$.

Typos/vocabulary:
- line 83: it should be $\mathbb R^{S \times A}$
- line 85: "objective"
- line 124: "belongings" -> "assignment"
- line 227: "miscellaneous"
- line 228: "symmetry-breaking"
limitations: not applicable
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 K-Medoids, as a classic clustering method, have many real applications. To fix the pool scalability of classic branch and bound (BB), this work proposed a method with reduced-space BB, in which the lower bound is provided by Lagrangian relaxation. Combined with several tailored bound tightening techniques, the method was tested in 28 datasets in the experiments section, including two datasets with one million samples.
strengths_and_weaknesses: I do recognize the huge sets of experiments and the effort. Just saying, I have a feeling that: Compared to machine learning, this works probably more like the FOCS or STOC type of paper for theoretical computing.

Strengths：
The idea is intuitive and makes sense.

There is an experiments-side contribution since the author compares the state-of-art baselines. The author provided experiments on 28 datasets, including two datasets with one million samples. The experiment on this data size is impressive.

Several tailored bound tightening techniques needs effort as an engineering solution, especially when facing large-scale dataset.

Weaknesses：
Theoretical side, the focus should be on how we select the proper upper and lower bound in the BB. In this work, the upper bounding methods are fine but not surprising. And, as they mentioned, the tight lower bound from the work of Cornuejols. 

questions: It would be better if the author can emphasize the significance of their upper/lower bound method.
limitations: No potential negative societal impact.
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: This paper uses a branch-and-bound (BB) method to improve Cornuejols work on Lagrangian relaxation for the K-Medoids clustering problem. Through bounding the regions of the medoids, search space is significantly reduced, leading to notable computation speed improvements. A convergence proof is also provided. To obtain the lower and upper bound, a couple of tricks are used: 1. Other than the Lagrangian based lower bound, the author proposes a simple basic lower bound, to further speed up the process. 2. The author proposes heuristic methods to obtain the upper bound; 3. Different bound tightening methods (probing, FBBT) are applied before updating the search space. The proposed approach can run on millions of data samples within reasonable time. 

strengths_and_weaknesses: Strengths:
1. The combination of brand-and-bounding with Lagrangian relaxation, on the K-Medoids problem is relatively novel. This method makes the Lagrangian based K-Medoids approach much more applicable in real-world datasets that have more than thousands of samples.
2. The proposed approach is trivially parallelizable, which makes the method suitable for large scale problems.
3. Theoretical convergence proof is provided.

Weaknesses:
The biggest weakness of the paper is regarding the practical value of the proposed method. It might interest the optimization community due to its convergence guarantee and various bound-shrinking tricks, but as a clustering method, the proposed approach is significantly more complicated than the counterparts like K-Means:
1. Though vanilla K-Means does not converge to global optimal, simple modifications like K-Means++ could alleviate the problem and often performs well in practice. The paper lacks a comparison (in terms of speed and quality) with such a simple baseline (K-Means or K-Means style methods).
2. Other than the centroid-based approaches, there are many other kinds of clustering, e.g. density-based, hierarchical clustering, etc. They often don't need the ball-shape assumption and work better in real world datasets. The paper lacks comparison with these different approaches, especially the state-of-the-art ones like [Sarfraz, et al, Efficient Parameter-free Clustering Using First Neighbor Relations].
3.  In experiments, the performance are evaluated using the achieved optimal gap and number of solved nodes. Standard clustering metrics include ARI and NMI, which provide a sense of clustering quality. The gap is useful in theoretical settings but not very meaningful in applications.

------

Score update from borderline reject to borderline accept, after reviewing the authors' responses. 
questions: It would be better to introduce more on BB method in this setting, e.g. what are the BB tree and node? How are they constructed?
limitations: NA
review_title: null

Meta-review: metareview: The authors solve an important theoretical problem via a nice connection to Lagrangian relaxation for k-medoids and k-medoids on samples. The paper also has significant experimental results. The paper is also well-written, and information from the rebuttal should be incorporated into the final version. I recommend acceptance. 

confidence: Certain
Decision: Accept