Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new initialization scheme for the k-median problem on graph input (or general metric spaces) using metric embedding tree structure. The paper proposes an algorithm that finds initialization of good centers using HST that gets an approximation factor of O(log min{k,d}) if the data is in Euclidean space  where d is the number of dimensions. Then, the paper studies clustering with differential privacy guarantee and hows that the initialization method could be adapted to give a slightly stronger muliplicative and additive errors. The work complemented these theoretical findings with experiments and show that the proposed initialization imporves the performance of k-median++ initialization.
main_review: Overall the paper makes some good contributions and adds to the communities' understanding of the k-clustering problem, espeically with privacy constraints. The paper proposed new algorithm designs and proved updated bounds for k-median with/without privacy constraints.  The experiment design also seems comprehensive and persuasive to me.

The writing in this paper is mostly smooth but could still be improved and be more clarifying in some ways. The paper did well in presenting the algorithm's framework and the ideas there are interesting. Although one can argue that the improvement in approximation ratio in classical k-median clustering is marginal, but as the authors noted, the design is new and it serves well for the setting of differential privacy constraints. I do think the authors could be more clear when talking about previous work on privacy clustering, the approaches used and the differences, the setting of Euclidean space v.s. general graph input. Right now the problem setting and the results seem a bit confusing to me.

Minor comments:
1. Does the number "2" really matter in the 2-HST that you are using, or can we replace it with something like $1+\epsilon$?
2. In the approximation ratio there is $min\{k, d\}$. Does that mean that we can only obtain this result with points in Euclidean space? 
3. The notation $N(v)$ and $N_v$ share the same meaning, right?
3. When defining $score(v)=N(v)\cdot 2^{h_v}$, is this the first time the notation $h_v$ appears? I couldn't seem to find a definition of it.
4.  In my opinion the paper sometimes uses a new terminology and assume the reader knows what it is. I think it is better to introduce terminologies and include a short description of them just to make sure the reader is on the same page. For example, the major comparison, k-means/median++,  is never fully explained.
5. The paper studies k-median clustering, I wonder if we know anything about what happens when we switch to k-means. Do the conclusions still hold?
summary_of_the_review: Mostly, I consider the contribution made in this paper to be meaningful to the clustering community, but it could be improved (at least in writing). It has a valid theoretical framework, but as a review from the broader clustering community, I find it hard to judge how significant these findings are.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper introduces a new initialization scheme for the k-medians clustering problem in the general metric space setting. This is based on the construction of metric embeddings via 2-HST’s (Hierarchically well-separated trees). The authors also extend this to the differential privacy (DP) setting. They prove approximation guarantees in both the non-DP and DP settings, improving upon the literature. Finally, they empirically validate algorithms against a number of baselines with both real world and synthetic datasets for multiple metrics.
main_review: Strengths:
- This paper gives improved k-medians bounds in the general metric setting (non DP) that improve over the literature in the d < k regime. It also gives the best known theoretical guarantee in the DP setting, and is worse than the lower bound by a small additive factor (k log log n)
- The paper empirically compares their algorithm to a number of standard baselines, showing favorable results for multiple datasets and metrics, and especially for less separable data and when the input data an unbalanced subset of the universe.

Weaknesses:
A few comments on improving the paper:
- The paper does not discuss runtimes of algorithms. A discussion of runtimes as well as comparison of runtimes in experiments would be useful
- Regarding the results for k-means - moving the k-means results to the main paper, as well as a brief discussion and comparison to k-medians would be useful.

We give a number of suggestions to improve clarity:
- “HST tree” -> “HST”
- “symmetric difference one” -> “symmetric difference of size one”
- (In Algorithm 1) “cost(F - x + y)” -> “cost(F - {x} + {y})”
- “we will count levels from large to small” -> “we will count levels in descending order down the tree”
- (Section 3.2 Intro) - “Suppose T is an L = log \Delta -level-2 HST” -> “Let L = log \Delta and suppose T is an L-level-2-HST”
- (Algorithm 2) Mention Algorithm 6 in “Build a level-L 2-HST tree T based on input U”
- State Theorem 3.4 and Theorem 3.5 before lemmas
- State that NDP stands for Non Differentially Private
- Theorem 4.2: Constants (10) can be absorbed into big-oh notation

summary_of_the_review: This paper improves upon the literature for the k-medians clustering problem in the general metric setting as well as in the differentially private case. The approximation guarantees improve the best known results in this case. The experiments demonstrate the validity of the theoretical contributions as well.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers the problem of finding good initial centers for the fundamental problem of $k$-median clustering using a randomized embedding of the original metric into a tree metric.  After setting the initial centers, a standard local search algorithm is applied to produce an improved solution.  This is explored in both the standard context of $k$-median clustering, as well as in the relevant context of differentially private clustering.  In the latter setting, the goal is to minimize the amount of additive error introduced by the algorithm subject to being $\epsilon$-differentially private.  An extension to $k$-means is given in the appendix.

In the standard setting of $k$-median clustering, the main theoretical result is an initialization algorithm which is an $O(\log(\min(\Delta,k)))$-approximation to the optimal k-median clustering.  This is an improvement over k-median++ (which gives $O(\log k)$) when $\Delta$ is small, e.g. for $\Delta = O(d)$ and $d$ is small.  Using this as a seed results for a local search method results in an $O(1)$-approximation overall.  At a high level, their algorithm first constructs an embedding of the original metric into a hierarchically well-separated tree (HST).  From there, the initialization can be seen as finding an $O(1)$-approximate solution on the HST efficiently.  The overall guarantee follows from standard results about HST's

In  the differentially private setting, the main result is a similar guarantee on the quality of the initial solution and also a bound on the quality of the final solution when using a known private local search algorithm.  The quality of the final solution has $O(1)$-multiplicative error and $O(\epsilon^{-1}k^2\Delta\log(n)\log\log(n))$ additive error.  This is an improvement over the additive error of $O(\epsilon^{-1}k^2\Delta\log^2(n)$ due to Gupta et al. 2010.  The number of local search iterations is also improved from $O(k\log n)$ to $O(k\log\log n)$.  The main idea for the initialization is similar to the standard setting, but here they use the structure of the HST to ensure the initial solution is private by injecting a different amount of noise at each level of the tree.

An empirical study is done on a class of synthetic graphs as well as the MNIST dataset.  For the synthetic graphs, the metric space is given by the weighted shortest path distance in each graph, while for the MNIST dataset the metric is given by either $\ell_1$ or $\ell_2$.  The authors compare both the initial costs and the final costs (after running a local search method) for several initialization methods in both the standard and differentially private settings.  The main observation is that the proposed initialization methods tend to have better initial cost and the proposed differentially private method often outperforms the other methods in both initial cost and final cost.




main_review: The main strengths of this paper lie in the differentially private version of their algorithm.  Here we get both theoretical and empirical improvements over prior work.  I also appreciated the simplicity of the algorithms and the clarity of the presentation.

In terms of weakness, first there is some misleading language with how the result for the standard setting is presented.  On page 2, the paper claims that the proposed method provides an $O(\log \min(k,d))$-approximation, but later on page 6 this is clarified as being an $O(\log(\min(\Delta,k)))$-approximation.  This achieves the former bound when the input data is bounded so that $\Delta = O(d)$, but this caveat is not discussed in the beginning of the paper.  I recommend the authors to move this discussion up to the statement of their contributions to avoid misleading readers.

Next, the main approach of the paper is to embed the input metric into a tree metric (via an HST) then efficiently compute an O(1)-approximation on this HST.  Metric embeddings (especially tree embeddings) are a standard technique in approximation algorithms, and this should be made clear in the discussion.  Additionally, it should be noted that there are polynomial time algorithms for computing an exact k-median solution on a tree metric (e.g. see [1,2]).  The proposed algorithm is a worthwhile contribution due to its simplicity, but these prior results should be discussed.  Additionally, it would be interesting to use one of these exact methods as a baseline in the experiments.

In the experiments, the authors run a fixed 20 iterations of local search after finding the initial centers, then report the k-median costs.  It might be interesting to also compare the runtime/iteration cost of reaching a locally optimal solution for the proposed methods and baselines, as well as the final cost of the locally optimal solutions found by each.  This sort of experiment seemed to be motivated by the discussion of the improved iteration bound for the differentially private method, but is missing.

As of now I lean more towards rejection, but would be inclined to increase my score of the above comments are addressed.

References

[1] - Shah, Rahul. Faster algorithms for k-median problem on trees with
smaller heights.  Technical report. 2003.

[2] - Tamir, Arie.  An $O(pn^2)$ algorithm for the $p$-median and related problems on tree graphs.  Operations Research Letters. 1996.  

--------------------------------------------------

Edit after reading the author's responses:

One of the main benefits of the proposed method for clustering on a tree is that it can be adapted to the differentially private setting, which it is unclear how to do for other (dynamic programming based) methods.  I have raised my score to weak accept.



summary_of_the_review: This paper considers initialization methods for $k$-median clustering in both the standard setting and the differentially private setting.  The paper gives theoretical bounds for their methods in both settings and backs this up with an empirical study.  Given the misleading presentation of some of the results, a lack of discussion/comparison to prior work on k-median in tree metrics, and a lack of running time/iteration count comparison in the experiments, I am not okay with accepting this paper unless these points are addressed.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper suggests an algorithm for the metric k-median problem using ideas from Metric embedding theory. The suggested use of the algorithm is as an initialization routine for the local search based algorithm for k-median. The differentially private version of the algorithm is also given along with bounds on k-median approximation factor. Experiments are conducted over datasets such as MNIST and results compared against the k-means++ algorithm (a popular initialisation algorithm).
main_review: The paper uses familiar techniques from metric embedding literature to suggest an algorithm for the k-median problem. The contributions does not seem to be very strong.
- The Metric embedding based algorithm for k-median is shown to give approximation guarantee of log{min(k, d)} which is better than k-means++ which gives O(log k). However, there are other algorithms that give much better approximation guarantees. It is not clear why the comparison is done with k-means++ here. This is something that the paper does not elaborate. Perhaps the algorithm is being suggested as an initialisation routine and hence the comparison is done with k-means++ but then that cannot be the only reason since the other algorithms with better approximation guarantees can also be suggested as initialisation routines. The discussion seems to be lacking on this aspect in my opinion.
- The improvement with respect to the Differentially Private seems to be minor over the previous work.
summary_of_the_review: In summary, the paper neither introduces new techniques nor obtains significant improvement over past results. My suggestion for improving the paper would be to add a discussion on why the suggested algorithm should be the right "initialisation" algorithm.
review_title: null

Meta-review: This paper considers initialization methods for the k-means algorithm.  There is a lot of prior work in this area. The reviewers were mildly positive on the paper.  There were several concerns on how the results were presented as well as the comparison to prior work. Importantly, no reviewer felt that there was a lot of novelty in the paper over the line of work on k-means initialization.
Decision: Reject