Average Sensitivity of Hierarchical Clustering

We thank the reviewer for helpful comments. We provide detailed answers to comments and questions below.

Applications of methods from differential privacy, i.e., exponential mechanism, may not be as surprising as initially seemed, due to connections to the notion of worst-case sensitivity in differential privacy

Differential privacy (DP) corresponds to measuring the sensitivity using TV distance with $\max\_{x \in X}$ instead of $\frac{1}{n} \sum\_{x \in X}$ in Eq. (1), i.e., DP is more pesimistic than Average Sensitivity (AS). Because of this relation, one can derive a trivial bound like $\mathrm{AS} \le \mathrm{DP} \cdot n$. In general, ensuring the stability with respect to DP inccurs worse complexity.

The main approximation guarantee for the stable-on-average hierarchical clustering algorithm seems to be in terms of the expected size of the sparsest cut, rather than the expected cost of the clustering

This is correct. Here, we would like to remind that the sparsest cut is related to Dasgupta score.

Other hierarchical clustering objectives such as the Moseley-Wang or Cohen-Addad objectives are not considered

Moseley-Wang is essentially the same as Dasguta score, while Cohen-Addad is a generalization of Dasguta score. The question when using Cohen-Addad is on the choice of the function $g$, where Dasguta score corresponds to a specific choice of $g$. We there think the use of Moseley-Wang or Cohen-Addad do not add much on our results.

What can be said about the approximation guarantees of the main algorithm in terms of the Dasgupta objective? Can anything be said about the approximation guarantees of the algorithm given an $\alpha$-approximation algorithm for sparsest cut?

Theorem 12 of (Dasgupta, 2016) showed the $O(\alpha \log n)$ approximation.

Is it true that the random cut algorithm that provides a good approximation to the Moseley-Wang objective would also have low average sensitivity?

The random cut will induce zero average sensitivity. Thus, the overall average sensitivity will also be zero. However, the 1/3-approximation of Moseley-Wang may not be that useful in practice because random cut will not provide any interesting clusters.

Thanks for the response.

I'm not sure I understand the notion that Moseley-Wang is essentially the same as the Dasgupta score, while Cohen-Addad is a generalization of the Dasgupta score, especially if we provide approximation guarantees in terms of the clustering cost, rather than the size of the cut. For example, you noted that Mosely-Wang has 1/3 approximation algorithm that may not be useful in practice, while achieving constant-factor approximation for the Dasgupta objective seems challenging.

Would you be able to elaborate?

We thank the reviewer for helpful comments. We provide detailed answers to comments and questions below.

Why stable results are needed?

Hierarchical clustering is used to understand the data visually. If a cluster structure changes drastically, the users will be confused whether their data understanding is truly reliable or only a noisy artifact induced by the unstable clustering algorithm. The stability is essential for reliable data understading.

The experimental analysis appears to be insufficient. Firstly, the experiments are conducted on three benchmark datasets and a single set of real-world data, which results in a relatively small dataset size.

The purpose of hierarchical clustering is to visualize the relationships between the data points. Visualization of thousands of data points are generally hard for users to inspect. Because of this reason, hierarchical clustering is better suited for the cases where the number of data points are not too large.

Secondly, common external clustering performance evaluation metrics, such as NMI, ARI, and ACC, are not employed in the experiments.

We used the metrics tailored specifically for hierarchical clustering, which are Dasgupta score, Dendrogram purity, and Cophenetic correlation. We believe these are appropriate choices for assessing the proposed method, rather than using generic metircs.

We nevertheless agree with the importance of evaluating the proposed method using several different metrics. However, we have to say that it is not possible to evaluate the method with (possibly) tens or hundreds of metrics. We therefore believe that the exhaustive evaluation is not the duty. Our responsibility is to relase the code so that any users with interest in alternative metrics can perform evaluations by modifying the provided code.

Lastly, there is no clear discernible consistent trend evident from Figure 2 and the related figures in the supplementary materials.

We do not say that there is a discernible consistent trend in the results. Our bound $O(\lambda Dn)$ is the worst-case upper bound. It is sometimes the case that the worst-case bound and practical performances have some gaps. Our results indicate that using a slightly larger $\lambda$ can result in better stability in some cases.

We thank the reviewer for helpful comments. We provide detailed answers to comments and questions below.

SHC has time complexity $O(Dn^3)$. This makes it impractical to moderate to large size data sets, which is perhaps the reason why experiments are conducted on mostly small data sets. I would like to see a more efficient algorithm, or at least an approximate one with proven theoretical bound.

We would like to remind that the typical agglomerative methods also run in $O(n^3)$ time. Because small $D$ is typicall chosen, the $O(Dn^3)$ time of the propsoed method is comparable with the existing methods. We also observed in the experiments that the proposed methos can run faster than the agglomerative methods for $D \le 10$.

The average sensitivity of SHC is $O(\lambda Dn)$, which can be made small by setting $\lambda \ll 1$. In the experiments, this is not always the case, for instance in Section 8. This signifies that SHC in practice doesn't really have a low average sensitivity.

Our bound $O(\lambda Dn)$ is the worst-case upper bound. It is sometimes the case that the worst-case bound and practical performances have some gaps. Our results indicate that using a slightly larger $\lambda$ can result in better stability in some cases.

The data sets chosen in the experiments are way too small. This makes the results not so convincing.

The purpose of hierarchical clustering is to visualize the relationships between the data points. Visualization of thousands of data points are generally hard for users to inspect. Because of this reason, hierarchical clustering is better suited for the cases where the number of data points are not too large.

SHC's time complexity is quadratic in data size. Could this be alleviated?

The answer is no because SSC requires $O(k^3)$ time for the size $k$ input. Here, we would like to remind that this time complexity is comparable with the existing agglomerative methods.

Why was $\lambda > 1$ used in the experiments?

$\lambda \to 0$ corresponds to random sparse cut while $\lambda \to \infty$ corresponds to greedy sparse cut. In the experiments, we are interested in the middle of these two extremes.

We thank the reviewer for helpful comments. We provide detailed answers to comments and questions below.

While the proposed algorithms are certainly non-trivial its not clear to me that:

1. a similar guarantee cannot be given for a simpler algorithm, and
2. the proposed algorithms are doing something desirable in the context of hierarchical clustering it would help to see some notion of lower bound to better understand the complexity of the problem it would help if the algorithm was also constrained to perform well on some notion of utility, e.g., the Dasgupta cost function that is used as a metric in the experiments

Unfortunately, we do not have a rigid answer to this point. The complexity analysis requires an approximation guarantee for the sparsest cut problem. However, the known approximation algorithm are computationally quite demanding even though they are polynomial time, which can result in $O(D \cdot \mathrm{poly}(n))$ time.

The proposed algorithm makes use of the exponential mechanism from differential privacy. How does average sensitivity relate to differential privacy? Does one notion imply the other or vice versa? Overall, these two notions both seem to capture the intuitive idea of "the output distribution for similar inputs should be similar".

Differential privacy (DP) corresponds to measuring the sensitivity using TV distance with $\max\_{x \in X}$ instead of $\frac{1}{n} \sum\_{x \in X}$ in Eq. (1), i.e., DP is more pesimistic than Average Sensitivity (AS). Because of this relation, one can derive a trivial bound like $\mathrm{AS} \le \mathrm{DP} \cdot n$. In general, ensuring the stability with respect to DP inccurs worse complexity.

The average sensitivity seems to scale with the maximum allowable depth $D$. Why not just set $D=1$, or some other small value? It feels like there should be a tension with some notion of clustering quality that benefits from using a tree with more depth.

$D$ is the depth of the hierarchical clustering, which is determined based on the users’ preference. $D=1$ induces only one splitting of the daset to two clusters, which is generally not sufficient for the clustering purpose.

Can the quality of the proposed algorithm be analyzed in terms of some cost or utility function (e.g., Dasgupta's cost function or the utility function due to Moseley and Wang)?

For the analysis, we need an approximation guarantee for the sparsest cut problem. The typical approximation algorithms are LP (Leighton-Rao) and SDP (Arora-Rao-Vazirani). However, the rounding operation in LP will not be stable, and SDP is generally too slow. In the current state, we do not have a good way to ensure the approximation and stability guarantees in the same time.