Average Sensitivity of Hierarchical $k$-Median Clustering
Authors: Shijie Li
Weiqiang He
Ruobing Bai
Pan Peng
Venue: ICML 2025 poster (2025)
Keywords: Hierarchical Clustering
Average Sensitivity
$k$-Median
Primary area: theory->probabilistic_methods

Abstract: Hierarchical clustering is a widely used method for unsupervised learning with numerous  applications. However, in the application of modern algorithms, the datasets studied are usually large and dynamic. If the hierarchical clustering is sensitive to small perturbations of the dataset, the usability of the algorithm will be greatly reduced. 

In this paper, we focus on the hierarchical $k$ -median clustering problem, which bridges hierarchical and centroid-based clustering while offering theoretical appeal, practical utility, and improved interpretability. We analyze the average sensitivity of algorithms for this problem by measuring the expected change in the output when a random data point is deleted. We propose an efficient algorithm for hierarchical $k$-median clustering and theoretically prove its low average sensitivity and high clustering quality. Additionally, we show that single linkage clustering and a deterministic variant of the CLNSS algorithm exhibit high average sensitivity, making them less stable. Finally, we validate the robustness and effectiveness of our algorithm through experiments.

Average Sensitivity of Hierarchical k-Median Clustering
Shijie Li Weiqiang Hel
Ruobing Bai" Pan Peng'
Abstract
science (Jin et al., 2015; Charikar & Chatziafratis, 2017;
Hierarchical clustering is widely used method for unsupervised learning with numerous applica- tions. However, in the application of modern algo- rithms, the datasets studied are usually large and dynamic. If the hierarchical clustering is sensitive to small perturbations of the dataset, the usabil- ity of the algorithm will be greatly reduced. In this paper, focus on the hierarchical it -median clustering problem, which bridges hierarchical and centroid-based clustering while offering the- oretical appeal, practical utility, and improved interpretability. We analyze the average sensitiv- ity of algorithms for this problem by measuring the expected change in the output when random data point is deleted. We propose an efficient al- gorithm for hierarchical k-median clustering and theoretically prove its low average sensitivity and high clustering quality. Additionally, we show that single linkage clustering and a deterministic variant of the CLNSS algorithm exhibit high aver- age sensitivity, making them less stable. Finally. we validate the robustness and effectiveness of our algorithm through experiments.
Dasgupta, 2016; Moseley & Wang, 2023; Lin et al., 2010) because of its ability to reveal nested patterns in real-world data. Several agglomerative and divisive methods have been proposed and widely used in practice for hierarchical clus- tering, such as those based on single, complete, average linkage and Ward's method (see Appendix B).
On the other hand, the stability of algorithms is becoming increasingly important in practical applications. If an al- gorithm is highly sensitive to changes in data points, even minor alterations can significantly impact the clustering re- sults, leading analysts to make incorrect decisions based on unreliable outcomes, which can, in turn, result in higher costs for error correction. At the same time, such insta- bility may inadvertently expose sensitive information, as small perturbations in data could highlight individual con- tributions or reveal underlying patterns that compromise privacy. Furthermore, unstable algorithms may erode trust in the analysis process, making their adoption in critical applications more challenging.
It is thus crucial to understand if hierarchical clustering algorithm is stable. Indeed, several studies have found that many hierarchical clustering algorithms, such as those using single linkage or complete linkage, are sensitive to small changes in the data (Balcan et al., 2014; Cheng et al., 2019; Eriksson et al., 201 I). This sensitivity can cause the dendro- gram structure to change dramatically with slight variations in the data. However, most of these works focus only on adversarial perturbations or attacks on the input and/or lack theoretical rigor.
1. Introduction
Hierarchical clustering, as discussed in (McQuitty, 1957: Hastie al., 2009), is one of the most commonly used clustering strategies. It produces a set of nested clusters, organized into tree-like structure known as a dendrogram. In this structure, each leaf node typically encompasses only a single object, whereas each internal node represents the union of its child nodes. By exploring the dendrogram's is multiple levels. one can identify clusters with varying levels of granularity. Consequently, hierarchical clustering adept at detecting and analyzing complex data structures. Hier- archical clustering has attracted great interest in computer
In this paper, we investigate the question of the stability of hierarchical clustering by adopting the concept of average sensitivity, as introduced by (Peng & Yoshida, 2020; Varma & Yoshida, 2021) that provides a theoretical framework for measuring the stability of the output of hierarchical clustering when data points randomly removed from the original dataset. Roughly speaking, for (deterministic) a algorithm that outputs k clusters, its average sensitivity is the expected size of the symmetric difference of the output clusters before and after we randomly remove a few points. One can generalize this notion to random algorithms for hierarchical clustering. This notion effectively captures the scenario where adversarial perturbations of the input are
'School of Computer Science and Technology, University of Science and Technology of China, Hefei, China. Correspondence to: Pan Peng <ppeng @ustc.eduutt edu.en...
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Average Sensitivity of Hierarchical k-Median Clustering
rare, but random noise is still commonly expected, such as in data collection with few missing items or in sensor network with a few sensors out of operation.
commonly used in differential privacy with the CLNSS algorithm. Specifically, the CLNSS algorithm first con- structs a 2-hierarchically well separated tree (2-RHST; see Appendix C.2) and then invokes a greedy algorithm to se- lection the centers according the tree distance. To ensure stability, we utilize the exponential mechanism by iteratively selecting the centers according to a probability distribution based on the cost of a point as a potential center. We provide theoretical guarantee on the performance of our algorithm by proving that our algorithm exhibits small average sensi- tivity while preserving the utility guarantee (Section 3).
We study the fundamental hierarchical Euclidean k-median clustering problem, which bridges hierarchical clustering (providing multiscale structure) and centroid-basee cluster- ing (optimizing a global objective). This makes it both the- oretically appealingg and practically useful. While linkage- based hierarchical methods are widely used, they lack well-defined objective function, limiting their theoretical analysis. Moreover, unlike linkage methods that merge clusters based on pairwise distances, hierarchical k-median clustering maintains explicit cluster centers, making it more interpretable and well-suited for applications like data sum- marization or facility location problems.
(2) We show that several agglomerative clustering algo- rithms, including single linkage clustering and a variant of the CLNSS algorithm have large average sensitivity (Sec- tion 4). That is, we identify specific datasets where these algorithms demonstrate poor stability. This implies that such algorithms are unstable under random perturbation of the data.
Specifically, given set of points P S Rd the objective of the hierarchical k-median problem (Lin et al., 2010), is to return an ordered set of centers {cI...., J. and a nested sequence of cluster sets PI....,Py Pn of P so that the maximum over all 1 S k S n of the ratio of Ex= Epec,llp cal12 to the optimum unconstrained k- median cost is minimized, where C₁ = {ci,..., )i) is the set of centers and Pa- [PI..... } is a k-partition. Here, P. is obtained by splitting particular cluster P3 from [P..... ................................ Pi-13 }. where j E j - 1], resulting in P; being divided into (P3 \ AP,, P.). Consequently, Pa becomes {PI...., P3 \.................... .P.....,P. P.}. Each P. is a subset of a part from the partition P.-1-
(3) In Section 5, we evaluate our algorithm on multiple datasets. Our results show that our algorithm achieves low average sensitivity while maintaining good approximation guarantees. Additionally, we validate the instability of clas- sie hierarchical clustering algorithms using both synthetic and real datasets. We also observe that single linkage ex- hibits good robustness on the selected real-world dataset (albeit at the cost of a high k-median cost.). To explain this phenomenon, we show both theoretically and experi- mentally (Appendix G)- - that single linkage achieves low sensitivity on datasets with strong cluster structures.
= P
Several papers have proposed algorithms to address this problem (Lin et al., 2010; Lattanzi et al., 2020). In particular, Cohen-Addad, Lattanzi, Norouzi-Fard, Sohler and Svensson (Cohen-Addad et al.. 2021) recently gave parallel algo- rithm, which in turn is based on a sequential algorithm that we refer to as the CLNSS algorithm, with small space and round complexity for the above problem that outputs a hier- archical clustering such that for any fixed k. the k-median cost of the solution is at most an (minfd, log } log A) factor larger in expectation than that of an optimal solution, where A is the ratio between the maximum and minimum distance of two points in the input dataset.
Comparison to the work (Hara et al., 2024) Hara et al. (2024) also examines the average sensitivity of hierarchical clustering. However, the clustering criteria in our study differ significantly from theirs, as we offer much stronger theoretical guarantees. Several key distinctions set our ap- proach apart. First, while their method relies on sparsest cut and Dasgupta cost (Dasgupta, 2016) to construct the hierarchical clustering, our study employs hierarchical k-median clustering approach. Second, although they also leverage the exponential mechanism, they do not provide an approximation guarantee, leaving the effectiveness of their method without theoretical support.
However, it remains unclear whether the CLNSS algorithm and other hicrarchical clustering algorithms in Euclidean space, has small average sensitivity (i.e., good stability).
1.2. Other Related Work
Robust or Stable Hierarchical Clustering. There has been research on robust/stable hierarchical clustering (Balcan et al., 2014; Cheng et al., 2019; Eriksson et al., 2011), but these studies aim to achieve stable clustering results by iden- tifying input outliers. They consider the impact of outliers on clustering, it means that they potentially classify input points as "good points" or "bad points". In fact, even with- out outliers, the clustering results are not necessarily stable. Any change in data points may cause drastic changes in
1.1. Our Results
In this work, we study the stability of hierarchical k-median clustering algorithms for Euclidean space under random perturbations using the concept of average sensitivity. Our main contribution is summarized as follows.
(1) We give a new algorithm for hierarchical k-median clus- tering by incorporating the exponential mechanism that was
2

---

Average Sensitivity of Hierarchical k-Median Clustering
hierarchical clustering results. Therefore, our work follows natural consideration, and more natural robustness standard.
minimum distance from p to any point in C.
Given a set of points P S R set of centers C' {ci...., ,.....,chh Cx the k-median cost is defined as
Average Sensitivity of Algorithmss. The concept of av- erage sensitivity, pivotal assessing the stability of algo- rithms against minor perturbations in input data, was first introduced by Murai & Yoshida (2019). They studied the stability of network centralities. Varma & Yoshida (2021) apply average sensitivity more widely to graph problem analysis, such as maximum matching, minimum s-t cut, etc. Kumabe & Yoshida (2022) extended the study of average sensitivity to dynamic programming algorithms. Peng & Yoshida (2020) analyzed the average sensitivity of k-way spectral clustering to evaluate its reliability and efficiency. The average sensitivity of k-means++ and coresets which is studied by Yoshida & Ito (2022) further explored these concepts. The application of average sensitivity to decision tree problems was studied by Hara & Yoshida (2022).
COST(P,C) Σ DIST((,,
= E minll c||s
cEC
PEP
PEP
The points in C' are referred to as cluster centers.
For two partitions Pi and P2, we say that Pi is nested in P2 if P2 can be obtained from P1 by merging two or more parts of PI.
Average Sensitivity For hierarchical clustering, the input is point set P = {P1. P2.... pr and we want to measure the average sensitivity of the algorithm after randomly delet- ing a point. We let p(t) = (pI...., Pi-.. Pr+1,...,, Pn denote the dataset in which the i-th point deleted.
Consider a deterministic algorithm A that takes as in- put a point set P and parameter is and outputs Pk (PI..... P... Let pp()) = put clustering when takes input p(t and k. The aver- age sensitivity of A on P is given by
Differential Privacy. The concept of differential privacy (DP) is similar to that of average sensitivity. DP (Dwork et al., 2006) which developed by Dwork et al. is a data privacy protection standard that states that if given two ad- jacent databases, differential private algorithm produces statistically indistinguishable outputs. DP clustering algo- rithms have been widely studied and designed by (Su et al., 2016; Huang & Liu, 2018; Ghazi et al., 2020; Cohen-Addae et al., 2022; Imola et al., 2023), such as k-means, k-median, correlation clustering and hierarchical clustering.
..... (() denote the out-
B(A, P)
PRAPE
10
1 Σ 12
min
P3
PAPP
P() a())
(1)
where π [ [k] is bijection, establishing cor- respondence between the clusters in Px and p(() based on the symmetric difference of sets. Specifically, for any two sets X and Y. the symmetric difference is defined as XAY = (X (Y X).
Note that the difference is that DP focuses worst-case sensitivity rather than the average-case sensitivity. For ex- ample, as long as the algorithm is very sensitive to a certain input, we consider the algorithm to be bad under the concept of DP. In addition, due to the requirements of the definition of DP, the total variation distance of the results two ad- jacent inputs must be small, but the earth mover's distance of these two results is smaller than the total variation dis- tance, which means that even if an algorithm is not DP, its average sensitivity may be small. Importantly, it is known that if an algorithm is 3-DP (see e.g., (Dwork et al., 2006)), then its average sensitivity is at most 3 (Varma & Yoshida, 2021). Despite these differences, DP and average sensitivity are both measures of algorithmic robustness, and there are meaningful connections between them.
For randomized algorithm, we often measure the average sensitivity by the distance between its output distributions. Specifically, the average sensitivity of a randomized algo- rithm A on a dataset P (with respect to the total variation distance) is defined as
1 n Σ (eP)
B(A.
=
(2)
where dEM (A(X),A(X(!) represents the Earth Mover's Distance (EMD) between the outputs A(X) and A(xx(),, with the distance between two outputs measured by the symmetric difference (see Eq. (1)). Specifically, ( where D denotes distribution over pairs (ær, y) of outputs of A such that the left and right marginals of D correspond to A(X) and A(X(1)), respectively.
We provide more related work on statistically robust cluster- ing in Appendix A.
defined as minp [E (x) ( (y/y.]]
2. Preliminaries
Distances and k-Median Cost For two points p and q in Euclidean space, the Euclidean distance between them is defined as DIST(p, 9) = ||p gll- Given a point p and set
The CLNSS algorithm Now we describe the CLNSS algo- rithm. We need the following notion of {-RHST, which is way of embedding the dataset into a restricted hierarchical structure based on a quadtree.
C' C Rdd we define DIST C) = mincec ||p clJ. as the
3

---

Average Sensitivity of Hierarchical k-Median Clustering
Definition 2.1. A restricted l-hierarchically well-separated tree (1-RHST) is positively weighted rooted tree where all leaves are at the same level, and edges at each level have the same weight, and the length of the edges decreases by factor of f on any root-to-leaf path.
3. An Algorithm with Low Average Sensitivity
In this section, we present our low-sensitivity algorithm for Hierarchical k-Median Clustering and provide theoretical guarantee of its performance (see Theorem 3.1). The al- gorithm, detailed in Algorithm 2, incorporates exponential mechanism with Algorithm I to ensure low sensitivity.
We will describe in detail on how to build 2-RHST, i.e., algorithm CONSTRUCT2HSSTCP, in Algorithm of Ap- pendix C.2. Given such a tree, let (PSTr(P, q) denote the shortest path between any two points p and q in tree T - (P, E, w). where P is the point set, with all points p located in the leaf nodes of the tree and at the same level, E is the edge set, and w denotes the edge weights, form- ing the metric space (P, r. For a set of points P on a tree and a set of centers C' where |C| = ki we define COSTT(P,C) = Σ minsec (p.
The algorithm begins with the set P and incrementally con- structs the hierarchical clustering from top to bottom. This process unfolds over n iterations, where in each iteration the exponential mechanism (Appendix C.1) is used to select center point. This selected center then divides the cur- rent cluster into two new clusters, driving the hierarchical structure forward.
We first introduce some definition. Let T denote the 2- RHST constructed from the point set P. Furthermore, let 7 represent the 2-RHST derived from the set p(t), which is obtained after the removal of the i-th point.
PEP
The CLNSS algorithm begins by applying a random shift to set P, where the shift is uniformly sampled from [0, A]". Then, a 2-RHST T' is constructed on the shifted dataset, and hierarchical clustering process Algorithm is performed the 2-RHST tree T. See Algorithm 5 in Appendix C.2.
For each t I...., n, let S denote the set of cen- ters selected in the first t - 1 rounds from the point set P. and let S represent the set of centers selected in the first t - 1 rounds from the subset p(i), x U S to rep- resent {*} U.S where x is a point and S is a set. Let 54 = arg minper COST (P.pU S(-1). This optimal center H, is crucial for maintaining the desired clustering properties throughout the hierarchical process. Then, we the exponential mechanism to select new center et, where the parameter À is approximately e-COSTr(P, (2S)US.11) Inn This iterative process yields a sequence of centers and the resulting clustering.
Algorithm/ 1 (Cohen-Addad et al., 2021) GREEDY ALGO- RITHM FOR HIERARCHICAL M-MEDINN ON 2- 2-RHST
Input: Set of points P, cost function COST, defined by 2-RHST
Set So + 0.
2 Set Po- + {P).
3 Label all internal nodes of the 7 as unlabelled.
4 for f =
1 to n do
Compared to the CLNSS algorithm (Algorithm 5), Algo- rithm 2 has low average sensitivity while ensuring utility. We provide a theoretical guarantee for the algorithm in The- orem 3.1. Recall that OPT(P, k) represents the optimal cost of the k-median problem for the point set P.
Let c, = arg m COST, (P, U S, Label the highest unlabelled ancestor of ct with et.
Set S, be ct U S
Define P. as the clustering obtained by assigning all points to the cluster centered at their closest labeled ancestor.
Theorem 3.1. Given point set P of size n and pa- rameter E > O, Algorithm 2 provides an approximation for the hierarchical k-median clustering problem for any k E (1....,, n.. Specificully, it achieves an expected cost of (PC S Old log A (1++)*) OPT(P,)))
Output:
Return ci...., On. PI....,P. Pn
We have the following theorem about the CLNSS algorithm.
with average sensitivity O (klmm) ). any k E [I,...,n], n.). with probability at least #. And the running time of the Algorithm 2 is O log n²))
Theorem 2.2 ((Cohen- Addad et al., 2021)). For any k e (1....,n), n). let Ci & be the center set representing the op- timal solution to the k-median problem on the 2-RHST T, where T is randomly shifted as described above. Then it
By Theorem 3.1, we can easily derive Corollary 3.2. The proof details of Theorem 3.1 and Corollary 3.2 are both deferred to Appendix D.
holds that for any k E nn..
(1) the set (ct.....oR] of the first k centers outpul by Algo- rithm I is exactly Ci,
Corollary 3.2. Considering the setting in Theorem 3.1, we have that
(2) and ECCOST(P, = (ICOST(PPC where OPT(P, k) represents the optimal cost of the k- median problem for the point set P.
log A)- OPT(P, k).
CO,TT(P,St) = = log A log (dnA))
E
max
(PT(P, (1 (1+

---

Average Sensitivity of Hierarchical k-Median Clustering
Algorithm 2 A LOW-SENSITIVITY ALGORITHM FOR HI- ERARCHICAL k- MEDIAN CLUSTERING
the input point P, and computes the clustering on P(s)
(obtained by uniformly and randomll deleting one point from P) with the resulting centers s(e and partition p(() is:
Input: Set of points P
Apply a random shift to each point P, where the shift is uniformly drawn from [),
2
Construct 2-RHST and let c denote the cost function
1
dEM (ALG )(
defined by T.
72
Set So 0.
1
0 Il
Set Po- {P].
Label all internal nodes of the RHST as unlabelled.
for /. = 1 to do
Randomly sample
number
A
E
In order to prove Lemma 3.3, we first show the following:
(CCOST((P(EE)USS...) (C, 3ln
Lemma 3.4. For Algorithm 2, given a of points P and Si-1, that is, if the first t 1 centers are the same, then "i=1dvv(ca (8) 0 lnn 5-m where
6lum
p(ù, if $
Let Ca where is sampled with probability
exp( exp(-COr COS-COST((0 (P, /X).
Label the highest unlabelled ancestor of o with ce.
drv (") represents the Total Variation (TV) distance between the distributions of the algorithm's 's selected t-th center a, and (0)
10
Set 5; = C2 U -
11
Define P; as the clustering obtained by assigning all points to the cluster centered at their closest labelled ancestor.
Without loss of generality, we assume that the t- th center is currently selected, and the centers se- lected in the previous set S.-1 remain consistent, meaning S = Si-1. At this stage, we apply Lemma D.1 to bound dAL St), ALG(P(),, s(")) by drv (ALG ALG((()) x==)), which repre- sents the expected difference of the distribution under the same choice of A. Given that 1 S,-1, the latter is bounded by Σ (z). Then by letting M (an upper bound the total variation distance), and a in Lemma D.1, obtain
Output: Return CI,..., PI....,
We sketch the proof of Theorem 3.1 in the following.
3.1. Proof of Theorem 3.1: Sensitivity
We demonstrate the average sensitivity by proving it through average sensitivity at each level of hierarchical clustering. More specifically, when proving the t-th layer, we assume that the set of centers chosen in the previous & layers is fixed (denoted as 1t-1), and then calculate the average sensitivity of the 1-th layer under this condition.
We first introduce some definitions.
1
Σ dr dr oo)
1
2B
Σ
Σ
A
di
Let T(X, 3) = COST, (X, y COSTrO (X, y U S,-))) Here. represents set and y represents point such that y X and X C Rdd. Define A (I), B, and ((9) follows:
UUUUUS, S.-I) (resp. (X,
n
Bn
JB
EEP(
(i)
+
B
1=1
exp
T())x))
exp
(p(t) .x)
Now we bound the first term and the second term separately and give some lemmas. First, we note that
(x)
Σ exp P
-T(Px))
Σ exp
(PO)
PEP() T() ( (p()), 2(11)
Σ Σ A
8. (P,
d= IEP(
B =
B(i)
6hn
6 In(n 1)
TT(P))
-T(0 .1
exp
exp
We first present the results of the average sensitivity analysis for the Algorithm 2.
Σ exp PEP
-T(Pp))
Σ exp
-T(Pp))
1=1 zEP(
PEP
Lemma 3.3 (Sensitivity). Let ALG represent our algorithm described in Algorithm The average sensitivity of the clustering produced by ALG, where ALG generates the set of i centers Ss and partition PE = (PI,..., Pb) from
-2(()((())_))
exp
Σ exp
-T(Pp))
i=1 1EPE)
PEP
5

---

Average Sensitivity of Hierarchical k-Median Clustering
(p()) mn
By these two lemmas, we then derive
exp
Σ exp
-
Σ
Σ
A (x)
In
PEP
PEP()
:=(I) + (IT).
Next, we aim to bound the term
We bound (I) using Lemma 3.5, bound (II) using
Lemma 3.6.
2
B
B
Lemma 3.5. It holds that
In
To this end, we state the following lemma: Lemma 3.7. It holds that
E
B
Proof. By definition of (I), we have
S 00
B
exp (-T
-(P,)))
((((()) A
cxp
(1)
-T(P,p)
The proof of Lemma 3.7 deferred Appendix D. We will make of this bound in the analysis below.
i= PEP()
exp
PEP
Note that
T(x(0,x)
S (e- 1) T(x(0)x))
1 1
dr (ce, 1
2B
Σ
100
di
exe
- exp
Bn
JB
i=
xEP()
(
as ed
1 15 (e - 11)x, for x E [0, 1]. Thus,
+
7
B
(e - 1)
exp
T(P.))
X
1
2B
In
di di+ d
(1)
A
Σ exp
-P(P.)
Bn
JB
1=1
Dc (()
pEP
A
0
Inn
-T(P.))
(T
8
(e
exp
A
Σ exp PEP
T(Pp)
This completes the proof of Lemma 3.4. Now we are ready to prove Lemma 3.3.
PCP
5o T(P.E)))
In n
50
Proof of Lemma 3.3. The sensitivity of the clustering after the j j-th round is given by
Here, the last inequality follows from the definition of :COST, 6lnm
d (LLL, 5()))
( since
X. A
3lnn
COST (P,E, U
U S simplifies to T(P,Te), we can
This can be expressed as the cost
rewrite this as:
((1))
E E- T(P.t) T(((E))))
AE
6lnn
3 Il
plus the sum of the costs incurred after selecting the j-th center Cj.
By Lemma 3.4, it holds that
Lemma 3.6. It holds that
Inn
deM (ALG)
(II)
E
(drv(ct, (
The proof of Lemma 3.6 is deferred Appendix D.
6

---

Average Sensitivity of Hierarchical k-Median Clustering
dEM (EM.AAGG(..S-1)AAGGIP .S
We now prove the property for k. On the basis of Sk-1, can obtain
7
Inn O(n)
CO (1+E)OSSTT ohe USk-1)
0
en
(3)
with probability at least 1 n from Lemma C.I and the setting where C₁ is the center choice Algorithm in k-th round and opt the optimal center choice based on Sk-1 in k-th round.
deM(ALG((P.S-)))AGGGPP
where the first inequality arises from the properties of the Earth Mover's (EM) distance. The lemma then follows by induction.
Because of the meaning of c it's cost must be less than equal to of U for i [k] From this, derive
COSTr(P.C& opt U S I min COSTr(P, U Sk-1) (E
3.2. Proof of Theorem 3.1: Utility
(4)
Now we prove the utility guarantec of the algorithm.
By the pigeonhole principle, there must exist of for E [k] that is a subtree not covered by Sk-1. Consequently, without loss of generality, we assume that ct is subtree not covered by Sk-1. Then, the following equation
Lemma 3.8 (Approximate Ratio). For the k-MEDIAN hierarchical clustering problem, let Sy represent the set of centers for the point set P obtained using Algorithm 2, [S&| = k. Let C represent the set of centers for the point set P' obtained by the RHST tree-based hierarchical clus- tering, with (CT = The clusters output by Algorithm 2
COST frooted at c Sk-1)
$ S (1 (1++))= (rooted at ct), C+
satisfy
holds true. Now we will discuss the classification show that our conclusion is correct. First, if ck and of are the same cluster, then c and of are equal. In the second case, opt is not in the cluster where ot is located, then the cost if Cj
(P, Sw) S(1+ (
A (1 (1+5))
with probability at least 1 - J
of the cluster centered on c is at least equal to that of the cluster centered on cj That is shown in Eq. (4), Thus,
Proof. We prove the lemma by induction.
COST ct Sk (1 "OST")"""""
Base Case. We begin by proving the theoretical guarantee for selecting the first center. Let C1 denote the first center chosen by our algorithm, and let of denote the optimal value under the current conditions, which the result obtained on 2-RHST. This be directly established using the ponential mechanism Lemma C.1 with [R] = n, In n² and utility function u(I,r) = COST, (P, 2 U U..)). We have the following:
(5)
Combining Eq. (3) and Eq. (5), we obtain
COST S(1 (P. opt US
< + <(1+))COSTT(P.C (
which holds with a probability of at least 1 Therefore,
(P(C S (P, 2 1- 1
k n22
n²
Pt(COSTr(P,S4) =)
(=CCOST((Pe)) -CoSTr(Pee))
Since X
Glax
3lnn
we can get
Then combining Theorem 2.2 we complete the proof.
4. Lower Bounds on the Average Sensitivity of Some Classical Algorithms
n
Inductive Step. Assume the property holds for
In this section, we analyze the average sensitivity of exist- ing hierarchical clustering algorithms through illustrative examples. We first give lower bound on the sensitivity of the single linkage (see Appendix B) in the worst case.
where à 2 2. Consider Ci which is the set of the centers chosen by 2-RHST. Suppose that
PP(COST,(P,Sx..) (1 + COST, Ci)
k
Lemma 4.1 (Average sensitivity of Single Linkage). The average sensitivity of Single Linkage is at least 11(m).
>
n2

---

Average Sensitivity of Hierarchical k-Median Clustering
Proof. For simplicity, assume the number of clusters k is 2. Let X = (. ,,. be points
the experiments: Ee [Ex (P)AA, Us- ing this quantity, we measure the expected symmetric dif- ference in the outputs of A on P and p(i under the same random seed и.. It provides an upper bound the true av- erage sensitivity given in Eq. (2), as shown in ( (Varma & Yoshida, 2021). Additional experimental setups and results are provided in Appendix F.
line in IR,
nearly equidistant as shown in Fig. 1. Specifically, sup- pose d1, .n. d
are the distances between 21 and ø2,
22 and z3. , In- and Vn respectively, then it follows that
d1 n
2 d1
du = 1+ (n- 1) di
d2 = 1 +
d3 = +
Experiments on synthetic datasets We first evaluate the sensitivity of our algorithm on synthetic datasets. Using the data from Lemmas 4.1 1 and 4.2, we observe that our algo- rithm (with = L. k = 2) behaves consistently with our theoretical predictions. Specifically, Single Linkage shows the highest sensitivity on one dataset (Fig. 2a), while CLNSS exhibits high average sensitivity on the other (Fig. 2b). In contrast, our algorithm and some other baseline methods demonstrate low average sensitivity across these datasets. The primary goal of this experiment is to highlight the sen- sitivity issues in Single Linkage and CLNSS, rather than to emphasize the superiority of our own method.
n
n
21
12
X
Figure I. n nearly equidistant points on a line.
For X, single linkage starts by merging the points with smaller indices first. After deleting T3, single linkage will merge the points to the left and right of x; separately, and finally merge them. Thus, the symmetric difference of the clustering results of X and X {2;) by the algorithm is
Next, we test our algorithm on a random regression dataset with 500 points generated with scikit-lean (Pedregosa et al., 2011), varying k and e. Fig. 3 shows that our algorithm maintains low sensitivity (at most 50). Moreover, larger values lead to smoother sensitivity curves, while smaller & values result in greater fluctuations. One reason is that when e is close to O, the algorithm tends to select centers greedily (as in Algorithm 1); when & increases (approaching oo), center selection becomes increasingly uniform at random.
(11), ((fi,..,, [mn]] A (Z 11 (dith,,,,,,
Note that the size of the above set is n -ii Thus, the average sensitivity of single linkage in X is En (n-1) = (()). L
While the above results demonstrate that single linkage can have high average sensitivity on certain hard instances, we show in Lemma G.2 that for datasets with strong cluster structure, its sensitivity can be significantly lower.
Experiments real-world datasets We use datasets from the Scikit-learn library repository (Pedregosa et al., 201 I) and the UCI Machine Learning Repository (Asuncion et al., 2007) to evaluate our algorithm. See Table 1 for more detailed description.
We also provide the lower bound for the deterministic ver- sion of the CLNSS algorithm, whose proof is deferred to Appendix E.
Lemma 4.2 (Average sensitivity of Algorithm 1). The aver- age sensitivity of the deterministic version of CLNSS Algo- rithm (Algorithm 1) is at least Q(n).
(l) k-median cost We evaluate the k-median cost, reflecting the clustering quality, using the criteria defined in Section 2. Here, the cost refers to the k-median cost of the k-clustering output. The comparison includes our algorithm (s = 1) and other methods across varying values of k. as shown in Figs. 4 and 9, The results indicate that while our algo- rithm slightly underperforms Ward's ''s method and complete linkage, it outperforms other approaches. Note that single linkage produces significantly higher costs, demonstrating poor performance. Overall, our algorithm achieves cluster- ing costs comparable to other algorithms.
5. Experiments
We experimentally evaluate the average sensitivity and clus- tering performance of our proposed algorithm, and compare linkage
it against CLNSS algorithm and four algorithm, i.c., single linkage, complete linkage, average linkage, and Ward's method.
All algorithms were implemented in Python 3010, and the experiments were conducted on high-performance comput- ing system featuring a 128-core Intel(R) Xeon(R) Platinum 8358 CPU and 504GB of RAM.
(II) Average sensitivity To evaluate an algorithm's 's average sensitivity, we run it on both the original and perturbed
'The choice of the s parameter largely depends on the spe- cific requirements of the problem. It should be set to balance the trade-off between the approximation ratio and average sensitivity, depending on the desired outcome. For instance, in practice, one could use a geometric search to find an appropriate a that satisfies the target accuracy achieves the desired sensitivity.
Implementation Changes Exactly computing the average sensitivity as defined in Eq. (2) is impractical for the experi- ments, due to high computational cost. Inspired by (Varma & Yoshida, 2021), We exploit the following quantity for
8

---

Average Sensitivity of Hierarchical M-Median Clustering
Synthatic Datasst from
Synthetic Delaset from Lemma 4.2
Awarage
Meragg lellage
120
Data Site
(a)
(b)
Figure 2. Results for generated datascts deseribed in Lemmas 4.1 and 4.2. The a-axis represents the data size, while the y-axis represents the average sensitivity.
Figure 3. Results for a generated regression dataset with 500 points.
Diabetes k-median cost
Wholesale k-median cost
WDBC k-median cost
Digits k-med an cost
25 Cluszonng numbar
Cluttring number
12 Clustering numbor
Clustorig number
(a) Diabetes
(b) Wholesale
(c) WDBC
(d) Digits
Figure 4. Results real-world datasets comparing the k- medin cost of different algorithms for varying values of A:
Diabates
Wholesale
Walcc
Digits
beerage Seniiiiitt
Calf
Delete number
Delete mumber
Delete number
Deleze mamber
(a) Diabetes
(b) Wholesale
(c) WDBC
(d) Digits
Figure 5. Results on real-world datasets with k 4. The z-axis shows the number of deleted points, and the y-axis represents average sensitivity. Our algorithm performs slightly worse than single linkage but surpasses the other algorithms.
datasets (see below) and measure the symmetric difference between the resulting clusterings. This process is repeated 100 times, and the average difference is computed.
lower clustering costs than average linkage, single linkage, and the CLNSS algorithm, seen in Figs. 4 and 9.) Further- more, as E increases, the average sensitivity of our algorithm decreases, confirming our theoretical result (Theorem 3) We also report that (in Fig. 7) our algorithm consistently maintains lower average sensitivity across different values of k, whereas other algorithms (except single linkage) per- form well only for certain & values.
Given dataset, we generate perturbed datasets by removing certain points as follows: (1) For each deletion setting (1 point, 1%, 5%, and 10% deletions), conduct 100 indepen- dent trials. (2) In each trial, randomly remove the specified number percentage of points from the original dataset to create a perturbed version. For fixed k we evaluate our algorithm with three values of E: 1, 10, and 1000.
While single linkage appears to have lower sensitivity, this seemingly contradicts our lower bound in Lemma 4.1. We believe this is because real-world datasets often have strong clustering structures, unlike worst-case instances. In Lemma G.2, we prove that single linkage has low average sensitivity for well-clusterable datasets and show experi- mentally (Fig. 10) that many real datasets exhibit similar structures.
In terms of average sensitivity, Fig. 5 shows that our algo- rithm (k = 4) outperforms traditional linkage-based algo- rithms and the CLNSS algorithm. (Recall that it achieves
We also tested = = 10 and 100, but since center selection probability depends exponentially on =1 the algorithm's 's behavior remains similar for = 10, 100, 1000, with nearly overlapping curves. For clarity, we show only the largest
9

---

Average Sensitivity of Hierarchical k-Median Clustering
Acknowledgments
Dwork, C., Roth, A., et al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theo- retical Computer Science, 9(34)) 100021111007,,0 2014.
This work is supported in part by NSFC Grant 62272431 and Innovation Program for Quantum Science and Technology (Grant No. 202 (02IZD330201),
Eriksson, B., Dasarathy, G., Singh, A., and Nowak, R. Ac- tive clustering: Robust and efficient hierarchical cluster- ing using adaptively selected similarities. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 260-268. JMLR Workshop and Conference Proceedings, 2011.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Ghazi, B., Manurangsi, P., Pagh, R., and Velingker, A. Pri- vate aggregation from fewer anonymous messages. In Ad- vances in PryptologyEEUROCRER
2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10- 14, 2020, Proceedings, Part II 30, pp. 798-827, Springer, 2020.
References
Ackermann, M. R., Blömer, J., Kuntze, D., and Sohler, C. Analysis of agglomerative clustering. Algorithmica, 69; 184-215, 2014.
Asuncion, A., Newman, D., et al. Uci machine learning repository, 2007.
GroBwendt, A., Röglin, H., and Schmidt, M. Analysis of ward's method. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithmss pp. 2939- 2957. STAM, 2019.
Balcan, M.-F., Liang. Y., and Gupta, P. Robust hicrarchical clustering. The Journal of Machine Learning Research, 15(1):3831-387) 2014.
Hara, S. and Yoshida, Y. Average sensitivity of decision tree learning. In The Eleventh International Conference on Learning Representations, 2022.
Charikar, M. and Chatziafratis, V. Approximate hierarchical clustering via sparsest cut and spreading metrics. In Proceedings of the Twenty-Eight Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 841-854. SIAM, 2017.
Hara, S., Takeuchi, K., and Yoshida, Average sensi- tivity of hierarchical clustering, 2024. URL https: / //openreview.o wet.eee.eeeeeeeeeeeeeeeeeeeeeeee seerummiddcCLaAII1X.
Cheng, D., Zhu, Q.. Huang, J., Wu, Q. and Yang, L. A hierarchical clustering algorithm based on noise removal. International Journal of Machine Learning and Cyber- netics, 10:1591-1602, 2019.
Hastie, T., Tibshirani, R., Friedman, J. H., and Friedman, J. H. The elements of statistical learning: data mining, inference, and prediction, volume Springer, 2009.
Henelius, A., Puolamäki, K., Boström, H., and Papapetrou, P. Clustering with confidence: Finding clusters with statistical guarantees. arXiv preprint arXiv: 1612.08714 2016.
Cohen-Addad, V., Lattanzi, S., Norouzi-Fard, A., Sohler, C., and Svensson, O. Parallel and efficient hierarchical k-median clustering. Advances in Neural Information Processing Systems, 34:20333-20345, 2021.
Huang, Z. and Liu, J. Optimal differentially private algo- rithms for k-means clustering. In Proceedings of the 37th ACM SIGMOD-SIGACT-SO of Database Systems, pp. 395 408.400.11 2018.
Cohen-Addad, V., Fan, C., Lattanzi, S., Mitrovic, S., Norouzi-Fard, A., Parotsidis, N., and Tarnawski, J. M. Near-optimal correlation clustering with privacy. Ad- vances in Neural Information Processing Systems, 35: 33702-33715, 2022.
Symposium on Principles
Imola, J., Epasto, A., Mahdian, M., Cohen-Addad, V., and Mirrokni, V. Differentially private hierarchical cluster- ing with provable approximation guarantees. In Inter- national Conference on Machine Learning, pp. 14353 14375. PMLR, 2023.
Dasgupta, S. A cost function for similarity-basee hierarchi- cal clustering. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 118-127, 2016.
Jin, C., Liu, R., Chen, Z., Hendrix, W., Agrawal, A., and Choudhary, A. A scalable hierarchical clustering algo- rithm using spark. 2015 IEEE First International Con- ference on Big Data Computing Service and Applications, pp. 418 426. IEFF, 2015.
Dwork, C., Mcsherry, F., Nissim, K., and Smith, A. Cal- ibrating Noise to Sensitivity in Private Data Analysis, pp. 265 284. Springer Berlin Heidelberg, 2006. doi: 10.1007/1 1671878 14.
10

---

Average Sensitivity of Hierarchical k-Median Clustering
Kumabe, S. and Yoshida, Average sensitivity of dynamic programming. In Proceedings of the 2022 Annual ACM- SIAM Symposium Discrete Algorithms (SODA), pp. SIAM, 2022.
Varma, N. and Yoshida, Y. Average sensitivity of graph algorithms. In Proceedings of the 2021 ACM-SIAM Sym- posium Discrete Algorithmss (SODA), pp. 684-703, Society for Industrial and Applied Mathematics, 2021. doi: 10. 117/1 .9781 1778861177 1976465.45
Lattanzi, S., Lavastida, T., Lu, K., and Moseley, B. A framework for parallelizing hierarchical clustering meth- ods. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2019, Würzburg, Germany, September 16-20, 2019, Proceed- ings, Part I, pp. 73-89. Springer, 2020.
Xie, Y. and Shekhar, S. Significant dbscan towards statisti- cally robust clustering. In Proceedings of the 16th Inter- national Symposium on Spatial and Temporal Databases, pp. 31-40, 2019.
Yoshida, Y. and Ito, S. Average sensitivity of euclidean k-clustering. Advances in Neural Information Processing Systems, 35:32487-32499 2022.
Lin, G., Nagarajan, C., Rajaraman, R., and Williamson, D. A general approach for incremental approximation and hierarchical clustering. SIAM Journal Computing, 39 (8):3633-3669, 2010.
McQuitty, L. L. Elementary linkage analysis for isolating orthogonal and oblique types and typal relevancies. Edu- cational and psychological measurement, 1722):27-2229 1957.
McSherry, and Talwar, K. Mechanism design via dif- ferential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pp. 94- 103. IEEE, 2007.
Monti, S., Tamayo, P., Mesirov, J., and Golub, T. Consensus clustering: resampling-baad based method for class discov- ery and visualization of gene expression microarray data. Machine learning, 52:91-118, 2003.
Moseley, B. and Wang. J. R. Approximation bounds for hi- erarchical clustering: Average linkage, bisecting k-means, and local search. Journal of Machine Learning Research, 24(1): 24(1):1-36, 2023.
Murai, S. and Yoshida, Y. Sensitivity analysis of central- ities on unweighted networks. The world wide web conference, pp. 1332-1342, 2019.
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., al. Scikit-learn: Machine learning in python. the Journal of machine Learning research, 12:2825-2833 2011.
Peng, P. and Yoshida, Y. Average sensitivity of spectral clustering. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1132-1140, 2020)
Su, D., Cao, J., Li, N., Bertino, E., and Jin, H. Differentially private k-means clustering. In Proceedings of the sixth ACM conference on data and application security and privacy, pp. 26 26-37, 2016.

---

Average Sensitivity of Hierarchical k-Median Clustering
A. Further Related Work
Statistically Robust Clustering. Several studies evaluate algorithm robustness from statistical perspective. For instance,
The works (Xie Shekhar, 2019; Henelius al., 2016) assess robustness using statistical measures, (Xie & Shekhar, 2019) employs Monte Carlo methods to eliminate randomness, reducing "chance patterns" or false positives generated by stochastic processes, thereby enhancing the reliability and robustness of clustering results. Similarly, (Henelius et al., 2016) identifies core clusters by finding the largest set of data points with co-occurrence probability of at least multiple iterations of the same clustering experiment. Additionally, (Monti et al., 2003) introduces consensus clustering, which uses resampling techniques to evaluate cluster stability across repeated iterations. It is important to note that these algorithms evaluate robustness from a statistical perspective, ensuring that their output retains most of the dataset, which differs from our study.
across
B. A Agglomerative Hierarchical Clustering
A common class of approaches for computing hierarchical clusterings are agglomerative linkage algorithms (Ackermann et al., 2014; Großwendt et al., 2019). A hierarchical clustering can be computed in a bottom-up fashion, where pairs of clusters are merged successively. Agglomerative linkage procedures do exactly that, with the choice of clusters to be merged at every step determined by a linkage function. This linkage function maps all possible pairs of disjoint clusters onto R+, and the algorithm chooses the pair that minimizes this value.
Before introducing the linkage functions, let's define the distance between points in cluster. We denote the cost of merging two clusters A and B as COST(A, B). The linkage functions interested in are:
Single Linkage. This linkage function measures the minimum distance between pairs of points from two clusters.
The single linkage function is defined as:
COST(A, (a.6)EAXB
min DIST(a, b).
This means that the cost of merging two clusters and B is the minimum distance between any pair of points (a, b),
where a E and E B.
Complete Linkage. This linkage function considers the maximum distance between pairs of points from two clusters. Formally, it is defined as:
COST(A, max DIST(a, b).
(a,))EAXB
In this case, the cost of merging two clusters and B is the maximum distance between any pair of points (a, b),
where a E and E B.
Ward's Method. This linkage function minimizes the total within-cluster variance. The cost of merging two clusters A and B is defined as the increase in the total within-cluster variance after merging. Formally, it is defined as
B))
Σ lla - MAUB|l AEAUB
Σ |10 MAll
Σ
1|b
PB 11
where A. PB. and (Auu are the centroids clusters A, B, and the merged cluster A U B, respectively. This means that the cost of merging two clusters the increase in the sum of squared deviations from the cluster centroids.
Average Linkage. This linkage function measures the average distance between pairs of points from two clusters. Formally, it is defined as:
CO,
ΣΣ DIST(a,
BEA
In this case, the cost of merging two clusters A and B is the average distance between all pairs of points (a, b), where and b B.
12

---

Average Sensitivity of Hierarchical k-Median Clustering
Algorithm 3 AGGLOMERATIVE ALGORITHM
Input: X finite set of input points from Rd
Set C|x = [[=} x e }
2 for i x 11--1,.. 1,.... do
find distinct clusters A, B&C C++1 minimizing COST(AUB C = (C++ (A,B) {AUB)
5 end
Output: Return clustering Ci...., G|X
The general algorithm flow of the Agglomerative Clustering Algorithm is shown in Algorithm 3. The algorithm flow is the same for these classic linkage hierarchical clustering methods, with the only difference being the calculation of cost during the cluster merging process; the other steps remain identical.
The general algorithm flow of the Agglomerative Clustering Algorithm is illustrated in Algorithm 3. The steps are the same except for the calculation of COST during the cluster merging process.
C. Supplementary Preliminaries
C.1. Exponential Mechanism
The exponential mechanism (McSherry Talwar, 2007; Dwork al., 2014) commonly used algorithm in the design of differential privacy, and it is also very useful for designing algorithms with low average sensitivity. Its main idea is to introduce special randomness when selecting candidates, making the selection process more robust.
In detail, the exponential mechanism aims to select a high-scoring candidate. Given a dataset æ, a real number À >> 0, candidate E is selected with a probability proportional to e ='(z,r//A, where u(..-) the utility score associated with dataset and candidate. We formalize this statement using the following lemma.
Lemma C.1 (Utility of the Exponential Mechanism (McSherry & Talwar, 2007; Dwork et al., 2014)). Let À > 0, we use the exponential mechanism M (-) to select candidate y" E for a given dataset x. Then for any > we have
Pr|u(zrr*) OPT X [ + 505t
where OPT minteR u(x,r).
C.2. Hierarchically Well Separated Tree and CLNSS Algorithm.
We will next explain how to construct 2-RHST. First, us examine the properties of 2-RHST.
Construction of 2-RHST. We now describe the construction of 2-RHST, which involves embedding the dataset into restricted hierarchical structure based quadtree. Let Dmax and Diin represent the maximum and minimum Euclidean distances, respectively, between any two points in the set P. Let A Dass, Sttrting with a d-dimensional cube of side Dun
length A, the space recursively divided into 2d smaller subcubes. Each subcube, with side length halved at each level, connects its parent with an edge length proportional to Avd/2 where i denotes the level. This process continues until the side length is reduced 1, which point each subcube contains exactly point. The construction of the 2-RHST tree, denoted CONSTRUCT2RHST(?2 is presented in Algorithm 4.
The CLNSS algorithm starts by applying a random shift to the dataset P, where the shift is uniformly sampled from A]4 Then invokes the above CONSTRUCT2RHST on the shifted points to obtain a 2- 2-RHST T and then invokes Algorithm on to find the nested sequence cluster sets. The Algorithm uses a greedy method to find centers and the corresponding clustering. The final algorithm described in Algorithm
13

---

Average Sensitivity of Hicrarchical k-Median Clustering
Algorithm 4 CONSTRUCT2RHISTC)) >Construction of 2-RHST
Input: Set points P Initialize: Construct a d-dimensional cube with side length A, where A Dus and the cube contains the entire point set Dais
P ( (O......,
7 for i =1=1,... 1ari=1..., do
Recursively divide each cube along the midpoint of each dimension, generating 2 subcubes per division.
Update the side length of each subcube to A if the subcube contains points from the point set P; otherwise, delete the subcube. The remaining subcubes that contain points are treated as child nodes of their parent node.
Set the weight between each newly generated node and its parent node to A va
Output: 2-RHST tree
Algorithm 5 THE CLNSS ALGORITHM
Input: Set points P, distance ratio A
Apply a random shift to each point P. where the shift uniformly drawn from [0, A] Run Algorithm 4 on the shifted points build 2-RHST tree T.
Invoke Algorithm 1 on T to produce a nested sequence of cluster sets. Output: A nested sequence of cluster sets
D. Deferred Lemmas and Proofs from Section 3
D.1. Analysis of Algorithm 2: Proof of Theorem 3.1
D.1.1. PROOF OF THEOREM 3.1: SENSITIVITY
Lemma D.1 (From (Kumabe & Yoshida, 2022)). Let D(---) denote either the earth mover's distance or the total variation distance. Let ALG be randomized algorithm. Suppose there is a parameter X (resp., X₂) used in ALG the instance P (resp. P.), sampled from the uniform distribution over [B, (1 B) (resp., [B,, (1 a.) B,)). Let M be upper bound of D(ALG(P), ALG())) Then for any > O. we have
D(AIG(P))AAG(PP)))
n
(1+a)B
a Σ
(AI.G())) ALG(P(O)
di
M
1+a B6)
a:Bn
JB
n
a
B
Lemma D.1 be used to bound the average sensitivity when the parameter e required by the algorithm corresponds two similar distributions.
Proof of Lemma 3.6. Case 1. If
T((P.p)
-P(((
Σ
Σ exp
exp
PEP
PEP())
then we can get
-T()) )
dss
Σ (1I)
-TT9(P(()))
[Pp)
Σ exp
Σ exp
1= DE P(ù)
P(9
3ad
-1(00)ppii...
exp
exp
(=1 P(P)))
Σ exp
-Tiu(P() 3
p)
exp
(P() pp
p())
PEr
14

---

Average Sensitivity of Hierarchical k-Median Clustering
(p(( m²
(p(0
exp
eep
Σ exp PEP(O)
Σ exp PEP
(P(G) .p)
PCP
X
=0().
Case 2. If
-T(P.p)
(T() .p)
Σ exp PEP
exp
PEP
then we can get
-T()
Epepin exp
-T(0) (p)
exp
(11) =
Σ exp pEP()
-T()) pp)
E exp PEP
-
1=1 zEP(
Inn
<0
The final inequality follows from Lemma 3.5 and the fact that
Σ
aa-b/ 2
Σ
IA
B
DEADE
aEAbEB
By combining the two cases, we can conclude that
Inn
(1I) S 0
Proof of Lemma 3.7. We first establish an inequality.
2
B
7
B
i=1
8 8.1()
p100,=10
2
6lnn n E T (P.ā.)
8 8. (P.
6lnn
61n(n-1 - 1)
i=1
s-1(1) (p()),z(")) sx(1)
2 n
Inn
(P,5)))
max
71
E
(P,5))
Inn
In(n - 1)
c T())
p(i) x (1)
Inn
E T (P. In n
max
0,
T ((P,E)
In(n - 1)
For the first inequality we have
5-1() (p(), xz(")
In
max 0,
C T (P, 2+)
Inn
In(n 1)
8. T()) (p()) (p()),((() (1)
2
In n T (P,
E-T(P, In(n - 1)
In(n 1)
1=1
15

---

Average Sensitivity of Hierarchical k-Median Clustering
4
((P,5.) - (P() xxpp())x="))) xz!")
n. T (P,E))
4
- =(P, T(x ,((1
-
n T (P)
4
T(x ;3) + T 34)
n T (P,
o )
For the second incquality we have
E T())
(1()) x((1)
Ian
8. T (P, x4))
max
0,
T
(P,
In(n - 1)
In n
e T())) ((()) ((())
e T()) (())) 21(0)
2
In
max
0,
T TP)
In(n 1 1)
Inn
1=1
E (. (p((), -.() (8)
E.7() (pl)) as(")
2
n
Inn
11
E
TP
In(n 1)
In
2
In
In(n -1]
Inn
i=1
2
n lnn
2 n 0(1) 0
In(n 1) _
n
alon Here, In(n-1) obtain
n is decreasing function, and its value is less than when >> 10. Combining the two inequalities above,
8
B(i)
S
0 n
12
1.1.2. PROOF OF THEOREM 3.1: TIME COMPLEXITY
The time complexity of the algorithm can be analyzed in two parts.
First, we consider the cost of constructing the 2-RHST. In the 2-RHST tree partitioning, each point belongs to exactly one node at each layer, and each layer partitions each node precisely once. Consequently, each point divided at most (dd) times. Given n points, the time complexity for this partitioning process is O(ndA).
Next, analyze the time complexity of hierarchical clustering. At each layer, selecting the center using the exponential mechanism incurs time complexity of Onn?). Since this process is repeated times, the overall clustering complexity is Onn)).
Combining these two components, the total time complexity of the algorithm is:
O A + n²).
is important to note that the time and space complexity of Algorithm 2 remain the same as in the original CLNSS version (Algorithm 1).
16

---

Average Sensitivity of Hierarchical k-Median Clustering
D.2. Proof of Corollary 3.2
Combining Theorem 3.1 and a technique from (Cohen-Addad et al., 2021), are ready to give the proof of Corollary 3.2.
Proof of Corollary 3.2. First, note that the cost of any valid solution is bounded below by and above by dAn. Let k1, .2...., Km be the sequence such that Kę is the largest number of centers such that the optimal k-mmdiin cost least 2', here log(dAn). Thus, according to Theorem 3.1, we have
COSTT(P, Sk,, A.) OPT(P,k)
COST SK. 1s) OP)(P,,))
E
max iefm]
S m max E RE(m)
O log A (1+
Now, observe that for any and any & with ky < k < 1 we have COST Sk. k) O(COSTr(P, (K. Sk:-1: since COSTr(P, Sk, k)) is non-increasing and we have OPT(P,K) S OPT(P, kt) by the choice of the kū This implies that
k(-1)
K), =0 OPT(P,k)
(COSTT(P,S., - OPT(P,k:
This completes the proof.
E. Proof of Lemma 4.2
Now, we present the proof of Lemma 4.2.
Proof. For simplicity, assume the number of clusters k: is 2. Consider pair of adjacent 2-dimensional datasets and X', where X' obtained by removing point from X. The first three layers of their RHST trees and the subtrees containing the first two selected centers are shown in Fig. 6. In both of these RHST trees, subtrees to 16 each contain (2(n) points.
center,
center
15 16
5
10
12
14
15
(a)
(b)
Figure 6. Fig. 6a is the clustering of the 2-RHST constructed from the original dataset when & = 2. while Fig, 6b is the clustering of the 2-RHST after deleting a single point, also with 2.
Assume that in the first RHST tree, point chosen as the center in subtree 5 has the minimum COST, while points in subtree 11 and subtree 15 chosen as centers have the second and third smallest COST, with a difference of less than & from the minimum. And, the COST of points chosen as centers from other subtrees is somewhat higher. Then, after deleting any point in subtree 5, the first two centers will change to points in subtree 11 and subtree 15, as shown in Fig, 6. Note that such examples are easy to construct. Thus the average sensitivity on the above graph least Q(n) 92()) 1(n)..
F. More on Experiments
Synthetic Datasets
We will now provide additional details on the data generation settings used in the experiment.
(1) Specific instances: we first generate synthetic data as described in Lemma 4.1 and Lemma 4.2.
17

---

Average Sensitivity of Hierarchical k-Median Clustering
In the experiments comparing our algorithm with the CLNSS algorithm and single linkage on these datasets, we set the value of 1, k to 2, and the dataset sizes ranged from 50 300 in increments of 50. Specifically, we generated two types of datasets: In Fig. 2a, the data points start from the coordinate origin and are distributed along random line with progressively increasing distance intervals, while in Fig. 2b, the data points are concentrated at a position in the Euclidean space corresponding to the third-layer nodes of the RHST tree, with settings identical to those described in the lemmas.
(2) Random datasets: these experiments Fig. 3, takes the values 1, 10, and 1000, with the dataset size fixed at 500 points. We conducted hierarchical clustering experiments, as shown in Fig. 3, on regression dataset generated using scikit-learn (Pedregosa et al., 2011). The results of the experiments on synthetic datasets were averaged over 50 independent trials. Since our algorithm is stochastic, each trial was repeated 10 times compute the average.
Real Datasets Table Table 1 summarizes the real datasets used in the experiments. It lists the dataset names along with their
Dataset
n
d
clusters
Iris
150
Wine
178
13
Wholesale
440
6
Diabetes
442
10
2
WDBC
569
30
2
Digits
1797
64
10
Yeast
2417
24
10
Table Summary of the datasets used in the experiments. Here, represents the size of the dataset, denotes its original dimensionality, and clusters indicate the number of classifications in the dataset.
respective sizes (n2), original dimensionalities (d), and the number of clusters. For high-dimensional datasets (e.g.. Digits and Yeast), dimensionality reduction was performed prior analysis.
Averege
Aucrogp
Delete number
Odlete number (b) 6
Delete number
Dalete number
(a) k =
(c) k
(d) 12
Figure 7. Results for different values of on the Wine dataset. Our algorithm exhibits lower average sensitivity across all values of & in the graph, whereas other algorithms (except for single linkage) perform better only for specific values of k.
We also evaluated the performance of the algorithm on the same dataset for different values of & (see Fig. 7). Fig. 7 shows that the average sensitivity of our algorithm for certain values of is quite small. Additionally, we can see complete linkage, Ward's method, and the CLNSS algorithm exhibit low average sensitivity only for specific values of k.
The appendix also includes the average sensitivity for certain datasets with respect to given value of k (Fig. 8). Since the Yeast dataset is larger, we chose higher value of l to evaluate the average sensitivity. Additionally, we provide the k-median cost for a continuous range of k values across the three datasets (Fig. 9).
G. Low Average Sensitivity of Single Linkage on Well-Clusterable Datasets
We introduce the following definition of well-clusterable datasets.
Definition G.1 (Well-clusterable datasets). Let m I n be an integer. Let P be a set of points, and let (Ci,..., Cm ) be a partition of P into m clusters. Let d, represent the maximum weight of edges in the minimum spanning tree (MST) of cluster Cr and let di = min DIST y) denote the minimum distance between clusters C2 and Cj-
18

---

Average Sensitivity of Hierarchical M-Median Clustering
Iris
Wine
Yeast
pee LeTME Enge Irage
Average Sensitivity
oetERe Pnogge with
Average Sensitivity
Average Sensitivity
196
3M6
Delete number
Delete number
Delete number
(a) Iris
(b) Wine
(c) Yeast
Figure Results on real- world data sets. The æ-axis represents the deleted points number and the y-axis represents the corresponding average sensitivity, Here, i is tixed: Iris ls = 4, Wine ls = 4, Yeast ls = 12.
Iris k-median cost
Wine k-median cost
Yeast k-median cost
CURSS Aur
700
80
8.03
1.0
Car (0am20000
CUCC Jorthh
3.00
CLYSS sgecee
Lmaage
150
Coppuet poane
Forage
2.03
10 13 11
10 20 22 24 20
30
10 12 M 18 22 20 24 26 20 20
20 22 24 25 Clustering number
20 15 M 24
Clustering number
Clustering number
(a) Iris
(b) Wine
(c) Yeast
Figure 9. Results on real-world data sets. The z-axis represents the centers, and the y-axis represents the k-median cost corresponding to the centers. On the Iris dataset, our algorithm gradually outperforms the single linkage algorithm as increases and performs similarly to other algorithms. On the Wine dataset, our algorithm closely matches the performance of CLNSS and single linkage. On the WDBC dataset, only the single linkage algorithm exhibits poor performance.
We say P is a well-clusterable dataset if the distance between any two clusters C₁ and Cj satisfies:
dig > 2 max(d, dz), Vi f.
We provide the following guarantee for single linkage clustering well-clusterable datasets: the single linkage clustering exhibits small average sensitivity for k-clustering if m is small and k < m.
Lemma G.2. Let P be well-clusterable dataset. Then for S k < m, the sensitivity of the k-clustering result of single linkage is bounded by 2(m - k) + 1, which is at most 2m, where m is specified in Definition G.I.
Proof. Let Pet P -CI...... C. x,, ..., } be the data obtained by deleting vertex from C. We need to measure the difference in the single linkage k- t-clustering results between P and Pa.
First, consider the case when h: = m. Note that the process of single linkage is essentially the same as Kruskal's algorithm for constructing the MST, and since di,5 > max (d,, dz), no clusters C; and Cj (with * j) will be merged before are clustered separately. Therefore, the single linkage k-clustering result of P is (Ci,..., C.. ......,,,,., For P if a leaf in the MST of C. deleting it will not affect d, x is not leaf in the MST of C, deleting will split the original MST into several trees. We then consider connecting these trees in arbitrary way to form new spanning tree for C.. By the triangle inequality, the newly added edges will not exceed 2d, and thus will be less than di,j for any j + i. Therefore, the clustering result for P' is [Ci, G. I...., ).,,, and the sensitivity of the k-clustering is 1.
. On Ci....,
For = m - 1,.... 1, this is equivalent to performing m - additional single linkage merges starting from the k-clustering result. Since in each single linkage merge, the inter-cluster distance is affected by only two vertices, and deleting other vertices will not increase the clterer distance between clusters, the single linkage merge will not be affected as long as
19

---

Average Sensitivity of Hierarchical k-Median Clustering
Dataset
E
min samples
Wholesale
0.1
Diabetes
0.6
Digits
0.5
Yeast
0.5
3
Table Parameter settings of DBSCAN algorithm various datasets, including details of the and min_samples parameters for each dataset. The parameter defines the neighborhood range (neighborhood radius) and determines whether points considered neighbors, while min samples specifies the minimum number of neighbors required for point to be classified as a core point, thus controlling the density of the cluster.
the deleted point x: is not one of these two points. Thus, the average sensitivity can be bounded as follows:
1 x n 2(m k) + 7
2(m k)) S 2(m k) + 1,
where the first term 1 x n-2(mm-) k) corresponds to deleting vertices that do not affect the single linkage merge, and the second term n 2(m-kk) accounts for deleting vertices that do affect the merge.
m
Many real datasets closely resemble well-clusterable ones To further validate the clustering structure, we applied the DBSCAN algorithm², classic density-based clustering method. We chose DBSCAN over the original labels because the dataset contains outliers, which cause the clusters defined by the labels to be poorly connected. As density-based algorithm, DBSCAN is better suited to handle such cases, as it preserves the inherent structure of the clusters.
To use DBSCAN, two parameters must be set: E and min mii_ssmples. ε defines the neighborhood radius and determines whether points are considered neighbors, while min nampses specifies the minimum number of neighbors required for a core point, thereby controlling the density of the clusters. DBSCAN begins by examining each
point to be classified point in the dataset. If point has enough neighboring points within its e-radius (i.e., least min mimpsees neighbors), is point, and cluster is formed. Points that within the e-radius of point but do not themselves have enough neighbors are classified as border points.
designated
We use the output clustering of the DBSCAN algorithm to calculate the max-intra distance d, and the inter-cluster distance d as defined in Definition G.I.
164
(a) In the Iris dataset, the DBSCAN parameters are set to e 0.25 and min_samples = 3.
(b) In the Wine dataset, the DBSCAN parameters are set to 1.5 and min-samples 3.
(c) the WDBC dataset, the DBSCAN parameters are set to min_samples 3.
and
Figure 10. The r-axis represents the number of clusters, while the y-axis corresponds to the Euclidean distance. MaxIntra denotes d. while MinInter represents the minimum inter-cluster distance among di,, values adjacent to d, Experiments show that these dataset exhibit a strong clustering structure, i.e. there large gap between MaxIntra and MinInter, which explains why single linkage achieves lower average sensitivity such datasets.
The experimental results in Fig. 10 confirm our hypothesis that these real-world datasets (Iris, Wine and WDBC) exhibit strong cluster structure, i.c. closely resemble well-clusterable datasets. Thus, single linkage exhibits lower sensitivity. Other
Note that we do not use DBSCAN for preprocessing the data; it is only used to verify whether the real-world dataset is well-clusterable. Other clustering methods also be employed assess the clusterability property. For the evaluation of algorithms, we apply clustering method and other baselines directly to the original dataset.
20

---

Average Sensitivity of Hierarchical k-Median Clustering
datasets exhibit similar properties, however, due to variations in the number of well-defined clusters across datasets and the difficulty of visualizing large datasets in graphs, provide the settings Table 2 for reproducibility, allowing readers to verify the results themselves.
21


Reviews:
[{"review_id": "je17oZiXSR", "reviewer": "Reviewer_mMdj", "summary": "Hierarchical clustering is a widely used method for unsupervised learning with numerous applications. However, in the application of modern algorithms, the datasets studied are usually large and dynamic. If the hierarchical clustering is sensitive to small perturbations of the dataset, the usability of the algorithm will be greatly reduced.\n\nThis paper focuses on the hierarchical K-median clustering problem, which bridges hierarchical and centroid-based clustering while offering theoretical appeal, practical utility, and improved interpretability. We analyze the average sensitivity of algorithms for this problem by measuring the expected change in the output when a random data point is deleted. We propose an efficient algorithm for hierarchical \n-median clustering and theoretically prove its low average sensitivity and high clustering quality. Additionally, we show that single linkage clustering and a deterministic variant of the CLNSS algorithm exhibit high average sensitivity, making them less stable. Finally, we validate the robustness and effectiveness of our algorithm through experiments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your reviews. We summarize your questions and provide our responses as follows:\n\n**References:**\n\n**R1: More discussions to Differential Privacy (DP) algorithms; Can we reduce one problem to another? For example if we split the privacy budget among $k$ layers, and apply exponential mechanism to them does it give us similar bounds?**\n\nIndeed, it is known that if an algorithm is $\\beta$-differentially private, then its average sensitivity is at most $\\beta$ (Varma & Yoshida, 2021). However, the reverse does not hold, as DP requires a bound on the worst-case sensitivity, whereas we can only bound sensitivity on average (i.e., under random deletions of points). \n\nIt is unclear whether splitting the privacy budget across $k$ layers would yield a DP algorithm with similar bounds. Below, we highlight key obstacles in extending our result to the DP setting. Ensuring DP requires bounding the worst-case sensitivity, which in turn demands a non-trivial upper bound on the maximum cost of a deleted point to its assigned center, beyond the trivial bound of  $d\\Lambda$. Unfortunately, we are unable to obtain such a bound. Instead, our analysis only gives a bound on average sensitivity— for instance, Lemmas D.2 and D.3 are based on the expected cost of a deleted point rather than the worst-case scenario.\n\nIn future revisions, we will expand the discussion in the related work section to further explore the connection between DP and average sensitivity.\n\n**Q1: Can the methods here be applied to \"flat\" $k$-clusterings?**\n\nPlease note that flat k-clustering is a sub-problem of hierarchical Euclidean k-median problem, in fact our algorithm solves the problem for all k at the same time. \n\nThus, the methods can be applied to the flat k-clustering, but since our definition is stronger, so the results corresponding to average sensitivity of flat k-clustering might be slightly worse. In fact, Yoshida & Ito (2022) gave an approach for “flat” k-median clustering (and other Euclidean clustering), introducing a coreset-based method to achieve low average sensitivity. They showed that for the Euclidean $k$-median clustering algorithm with an $\\alpha$-approximation, a coreset can be constructed with an average sensitivity of $\\tilde{O}(\\frac{dk^2}{\\epsilon^3 n})$, yielding a clustering result that is a $(1+\\epsilon)\\alpha$-approximation with high probability.\n\nHowever, their notion of average sensitivity is defined with respect to total variation distance, thus their result is not completely comparable to ours. If we convert TV distance to our earth mover’s distance (EMD), which roughly involves multiplying by n, the resulting bound is $\\tilde{O}(\\frac{dk^2}{\\epsilon^3})$. (Recall that our sensitivity bound is $O(k\\ln n/\\epsilon)$ and the approximation ratio is $d \\log\\Lambda (1+\\epsilon)^k$).\n\n**Q2: The cost function seems insensitivity to relative differences among points. For example, if I take a cluster in the $k$ clusters and move it farther away the constructed tree still seems to be the same . I wonder if you have any opinion about what this means if we use the traditional cost functions for $k$-median.**\n\nIn our definition, the $k$-median cost at each layer $k$ follows the traditional cost function for $k$-median. Intuitively, if a cluster in the optimal $k$-clustering is moved farther away, the same set of $k$  clusters should still be identifiable in the resulting dataset.\n\nHowever, our hierarchical clustering cost function is sensitive to the structure of the tree. Specifically, at any fixed layer $k$, moving a cluster (say,  $A$) farther away can significantly impact the clustering at layer  $k-1$. For example, in the original dataset, the algorithm might merge clusters $A$ and $B$, but after moving $A$ away, it may instead merge  $B$ with another cluster, $C$. This change in merging order can lead to structural differences in the hierarchy.\n\n**Q3: The paper starts with constructing the $2$-RHST tree. The hierarchical clustering then builds on the tree only and ignores the original datasets. Intuitively why do we choose the $2$-RHST tree? Are there other tree embeddings that can work for this problem?**\n\nAs noted in the CLNSS paper, standard embedding techniques allow all points in the dataset to be embedded into a $2$-RHST with only a small distortion. Intuitively, the $2$-RHST effectively preserves the hierarchical structure of the original dataset and provides a natural way to construct a hierarchical clustering tree. This is achieved through a top-down approach that recursively partitions the point set based on distance.\n\nThere are other tree embedding approaches for flat  $k$ -clustering. For example, Balcan et al. (2017) (Differentially Private Clustering in High-Dimensional Euclidean Spaces) introduced a tree partitioning method. However, it is unclear to us whether these tree embedding methods can be directly applied to the hierarchical  $k$ -median problem.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I've checked the argument for the approximation bounds and it seems to make sense.", "experimental_designs_or_analyses": "The experiments seem well-designed.", "relation_to_broader_scientific_literature": "The paper is closely related to the recent advances in hierarchical K-median, including tree-based agglomerative clustering methods and approximation to the optimal solution. The definition of robustness, measured by perturbation of one point, and the exponential mechanism closely related to the field of Differential Privacy.", "essential_references_not_discussed": "The authors have done a great job citing and discussing related papers. However, I think there should be a more extensive discussion on the algorithm's inherent connection to Differential Privacy (DP) algorithms; as the definition of perturbation by one point is exactly that of neighboring datasets in DP, and exponential mechanism is a universally applied DP mechanism. In that sense, can we reduce one of these problems to another? For example if we split the privacy budget among K layers, and apply exponential mechanism to them does it give us similar bounds?", "other_strengths_and_weaknesses": "Weakness: the new algorithm design is relatively simple: to introduce exponential mechanism to the existing 2-RHST tree based clustering algorithm. This incurs an additional $(1+\\epsilon)^k$ factor cost in the approximation ratio, which could be a lot if K is big. The results share a lot of similarities with differential privacy problems, hence not very surprising.", "other_comments_or_suggestions": "See questions for authors.", "questions_for_authors": "1. Can the methods here be applied to \"flat\" K-clusterings? I suppose the cost function's definition must change then because there is no path.\n2. The cost function seems insensitivity to relative differences among points. For example, if I take a cluster in the K clusters and move it farther away the constructed tree still seems to be the same (although some merges might change their orders). I wonder if you have any opinion about what this means if we use the traditional cost functions for K-median (sum of distances to closest center).\n3. The paper starts with constructing the 2-RHST tree. The hierarchical clustering then builds on the tree only and ignores the original datasets. Intuitively why do we choose the 2-RHST tree? Are there other tree embeddings that can work for this problem?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0HXFx0c7DD", "reviewer": "Reviewer_F12p", "summary": "This study provides an innovative solution that enhances both the interpretability and robustness of hierarchical clustering techniques. The study shows that classical methods have high sensitivity on specific datasets, and validates the robustness of the new algorithm through experiments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We will address your concerns as follows:\n\n**Weaknesses:**\n\n**W1: Computational Complexity: $O(n^3)$ time complexity limits scalability to large-scale datasets.**\n\nWe noticed that this weakness is similar to Q1. Please refer to Q1 for further details.\n\n**W2: Experimental Bias: Reliance on DBSCAN for defining “well-clusterable” real data may introduce preprocessing bias.**\n\n Please note that we do not use DBSCAN for preprocessing the data; it is only used to verify whether the real-world dataset is well-clusterable. Other clustering methods can also be employed to assess the clusterability property.\n\nFor the evaluation of our algorithms, we apply our clustering method and other baselines directly to the original dataset.\n\n**Q1: The algorithm has $O(n)^3$ time complexity. Have you considered sampling-based optimizations for large-scale data?**\n\nOne of the primary reasons for the  $O(n^3)$  time complexity is that the algorithm involves $n$ iterations, and in each iteration, we sequentially compute the $k$-median cost for $n$ possibilities and sample from the distribution underlying the exponential mechanism. It is challenging to optimize this process through sampling. While importance sampling could potentially help identify significant points, we require the information for all points to construct the hierarchical tree. Other sampling approaches might help, but we are not aware of any that provide significant improvements.Instead,we focused on parallelization in our experiments to enhance the algorithm’s efficiency.\n\n**Q2: How to design adaptive strategies for $\\epsilon$ (e.g., dynamically adjusting based on data distribution) instead of manual tuning?**\n\nThe choice of the  $\\epsilon$  parameter largely depends on the specific requirements of the problem. It should be set to balance the trade-off between the approximation ratio and average sensitivity, depending on the desired outcome. For instance, in practice, one could use a geometric search to find an appropriate $\\epsilon$  that satisfies the target accuracy or achieves the desired sensitivity.\n\n**Q3: Can this approach extend to non-Euclidean metric spaces (e.g., graph data)?**\n\nIndeed, the hierarchical Euclidean  $k$ -median can be generalized to metric spaces, and there are tree embedding approaches for general metric spaces. Thus, we believe it is possible to extend our approach to non-Euclidean metric spaces.\n\nHowever, for graph data, it is unclear how to effectively utilize the $2$-RHST tree or similar tree embeddings, as graph data typically do not contain explicit distance information or may not satisfy the triangle inequality.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "This paper specifies that several agglomeritive clustering, including single linkage clustering and a variant of the CLNSS algorithm are unstable in the face of data perturbations, and points out that some other methods that consider stability are based on the identification and processing of anomalies. The authors argue that even this consideration is somewhat one-sided and propose a method based on the exponential mechanism that has a better average sensitivity.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths: \n- Theoretical Rigor: Formal proofs for sensitivity bounds and approximation ratios. \n- Comprehensive Experiments: Validation on synthetic and real datasets aligns theory with practice. \n- Innovative Comparison: Systematic analysis of classical methods’ limitations (e.g., Single Linkage). \n\nWeaknesses: \n- Computational Complexity: $O(n^3 )$ time complexity limits scalability to large-scale datasets. \n- Experimental Bias: Reliance on DBSCAN for defining “well-clusterable” real data may introduce preprocessing bias.", "other_comments_or_suggestions": "No", "questions_for_authors": "- The algorithm has $(O(n^3)$ time complexity. Have you considered sampling-based optimizations for large-scale data?  \n- How to design adaptive strategies for $\\varepsilon$ (e.g., dynamically adjusting based on data distribution) instead of manual tuning?  \n- Can this approach extend to non-Euclidean metric spaces (e.g., graph data)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tC4hxYaqZu", "reviewer": "Reviewer_7WCS", "summary": "This paper studies the hierarchical $k$-median problem in the setting of average sensitivity, which is a measure of how much an algorithm's output changes when the dataset undergoes small perturbations. The paper's first contribution is algorithmic, and it proposes an efficient algorithm for the hierarchical $k$-median problem, with rigorous theoretical guarantees with respect to the average sensitivity and the expected cost of the returned solution. At a technical level, their algorithm combines the CLNSS algorithm [Cohen-Addad et al., 2021] with an exponential mechanism. The paper's second contribution is 2 results on the worst-case average sensitivity of (i) single linkage and (ii) the CLNSS algorithm. The paper's third contribution is an experimental evaluation of their proposed algorithm, which they compare against a number of different HC algorithms on a variety of synthetic instances and datasets from the Scikit-learn repo and UCI ML repo. As a final small result, they show that if the data points are well-clustered, then single linkage has provably much lower average sensitivity.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your suggestion. We fixed the typos in the updated manuscript. We will address your concerns as follows:  \n\n**Claims And Evidence:**\n\n**C1: The experimental section does contain some claims which are not supported by the presented evidence.**\n\nWe appreciate your careful review and will revise the experimental section accordingly. \n\n**Experimental Designs Or Analyses:**\n\n**E1: The one issue I found are the experiments corresponding to Figure 2. Why are single linkage and CLNSS the only algorithms that are compared on the synthetic instances? Furthermore, Fig 2a and Fig 2b evaluate different synthetic instances. I would expect all methods to be evaluated on the synthetic data, similar to what is done in the experiments on real-world data.**\n\nWe sincerely appreciate your feedback and will carefully consider your suggestions. The two datasets in Fig. 2 were specifically chosen as challenging instances based on Lemma 4.1 and Lemma 4.2 to evaluate the theoretical lower bounds of the single linkage and CLNSS algorithms. We initially thought it might not be particularly insightful to include other methods in this context.\n\nHowever, we will evaluate the performance of other methods on these two datasets in the revised version to provide a more comprehensive comparison.\n\n**Weaknesses:**\n\n**W1: The main weakness in my opinion is the lack of novelty in the result. Currently, the result seems like a fairly straightforward application of the exponential mechanism in the CLNSS algorithm - not much other technical novelty is needed.**\n\nWe noticed that this weakness is similar to Q2. We have provided a detailed response in Q2.  \n\n**W2: The write-up could be improved. For example, the main text refers to the appendix a lot, requiring the reader to go back and forth to check the correctness of the result. As a suggested improvement, I would instead move most of the theorem/lemma statements that are needed into the main text, and instead move all the proof environments to the appendix.**\n\nThank you for your feedback. We will move most of the theorem and lemma statements into the main text and shift the proofs to the appendix as suggested. \n\n\n**Q1: In Theorem 3.1, is the dependence on $k$ necessariy in the approximation factor and average sensitivity bounds? For low $k$, this result is quite strong, however, as $k$ approaches $O(n)$ the guarantees become much worse.**\n\nThank you for raising this important point. We agree with your observation that as $k$ becomes large, our guarantees do indeed weaken. While it is unclear whether the dependency on $k$ in the utility is strictly necessary, we believe that the dependency on average sensitivity is essential. Since hierarchical clustering is constructed from top to bottom, it is intuitive that the number of misclassified points will accumulate, leading to a dependency on the layer $k$ in the sensitivity bound.\n\nFor the utility part, we feel that our analysis might be somewhat conservative. The accuracy loss occurs by a $(1 + \\epsilon)$ factor at each layer in our induction approach, leading to a  $(1 + \\epsilon)^k$ factor. There may be an opportunity to refine the analysis to mitigate the exponential dependence on $k$, which we see as an interesting future direction.\n\nFinally, we note that in our experiments (Fig. 4 & Fig. 9), the approximation ratio does not increase exponentially, suggesting that there is potential for further improvement in our approximation ratio.\n\n**Q2: Could you please elaborate on the main technical novelty of the result? As mentioned above, it currently seems that the main result seems like an application of the exponential mechanism to CLNSS. Are there any significant difficulties that need to be overcome? Or can the result be applied directly?**\n\nThank you for your thoughtful comments. Indeed, we have applied the exponential mechanism based on the CLNSS algorithm. While the use of the exponential mechanism to stabilize algorithms is not new (it has appeared in the differential privacy literature, for example), its recursive application to derive sensitivity bounds for hierarchical clustering is novel.\n\nOne main difficulty is in bounding the aggregated error after applying the exponential mechanism at each level. For instance, at each $k$, there is an optimal $k$-median solution $\\textup{OPT}(k)$, but the algorithm can only provide a local optimum. Specifically, given the current  $k-1$ clustering $\\mathrm{Alg}(k-1)$, the algorithm selects a new center, resulting in a $k$-clustering $\\mathrm{Alg}(k)$. The exponential mechanism can only provide a bound on the error between $\\mathrm{Alg}(k)$  and $\\mathrm{OPT}_k'$, the optimal $k$-clustering given $\\mathrm{Alg}(k-1)$. Relating this error bound to the error bound between $\\mathrm{Alg}(k)$ and $\\mathrm{OPT}(k)$ is a key challenge.\n\nWe address this challenge by carefully leveraging the properties of the $2$-RHST and using an inductive approach. This forms one of the novel aspects of our analysis.", "claims_and_evidence": "The main theoretical results/claims are supported by proofs. I checked these proofs, and did not find any errors.\n\nThe experimental section does contain some claims which are not supported by the presented evidence. In particular, in the second to last paragraph it is stated that \"(...) Fig. 5 shows that our algorithm ($k=4$) outperformls traditional linkage-based algorithms and the CLNSS algorithm (Recall that it achives lower clustering costs than average linkage, single linkage, and the CLNSS algorithm, as seen in Figs. 4 and 9).\" However, this claim seems overly broad. For example, on the iris dataset, average linkage outperforms the proposed method both with respect to the average sensitivity and with respect to the clustering cost. On the wine dataset, average linkage achieves much better cost.\n\nFurther on in the experimental section, it is mentioned that \"our algorithm consistently maintains lower average sensitivity across different values of $k$, whereas other algorithms (...) perform well only for certain $k$ values.\". Again, this claim is slightly exaggerated, as there are a number of algorithms (e.g., average linkage) where the average sensitivity is also consistent for different values of $k$.", "methods_and_evaluation_criteria": "Yes, the experimental setup is sufficiently good in terms of what benchmark datasets are used, and what algorithms are compared against.", "theoretical_claims": "Yes I did, no issues found.", "experimental_designs_or_analyses": "The one issue I found are the experiments corresponding to Figure 2. Why are single linkage and CLNSS the only algorithms that are compared on the synthetic instances? Furthermore, Fig 2a and Fig 2b evaluate different synthetic instances. I would expect all methods to be evaluated on the synthetic data, similar to what is done in the experiments on real-world data.", "relation_to_broader_scientific_literature": "The paper makes clear contributions to the broader literature on clustering robustness and algorithmic stability, also studied in works by Peng and Yoshida (2020), Varma & Yoshida (2021), and Yoshida & Ito (2022) who have studied the average sensitivity for various clustering and graph-theoretic problems. The authors generalise and strengthen the previous CLNSS algorithm by integrating the exponential mechanism [McSherry & Talwar, 2007] for differential privacy to systematically control the average sensitivity in hierarchical clustering. Therefore one could see this work as a bridge between literature on hierarchical clustering (e.g., Dasgupta, 2016; Moseley & Wang, 2023) and robustness/differential privacy (Imola et al., 2023; Cohen-Addad et al., 2021, 2022).", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "S1) The proposed algorithm has good theoretical guarantees. In particular, the average sensitivity bound is significantly better than some of the worst case bound on popular algorithms (single linkage for example). To the best of my knowledge, this is the first such result, making it interesting.\n\nS2) I think the results on the lower bound (and upper bound for well-clustered data) are quite nice and insightful. This sheds light on when these types of algorithms should or shouldn't be used if a user is interested in average sensitivity.\n\nW1) The main weakness in my opinion is the lack of novelty in the result. Currently, the result seems like a fairly straightforward application of the exponential mechanism in the CLNSS algorithm - not much other technical novelty is needed.\n\nW2) The write-up could be improved. For example, the main text refers to the appendix a lot, requiring the reader to go back and forth to check the correctness of the result. As a suggested improvement, I would instead move most of the theorem/lemma statements that are needed into the main text, and instead move all the proof environments to the appendix.", "other_comments_or_suggestions": "1. line 067, right column: \"agglomeritive\" --> should be \"agglomeration\".\n\n2. line 423, right column: \"our our\" --> should be \"our\".\n\n3. Equations that exceed the column width, e.g., in Corollary 3.2, on lines 235--242, left column, on lines 240 -- 245 in the right column, and on lines 362 in the left column.\n\n3. $P^{(i)}$ is defined again in Section 3, whereas it was already introduced in the preliminary section.", "questions_for_authors": "1.) In Theorem 3.1, is the dependence on $k$ necessariy in the approximation factor and average sensitivity bounds? For low $k$, this result is quite strong, however, as $k$ approaches $O(n)$ the guarantees become much worse.\n\n2.) Could you please elaborate on the main technical novelty of the result? As mentioned above, it currently seems that the main result seems like an application of the exponential mechanism to CLNSS. Are there any significant difficulties that need to be overcome? Or can the result be applied directly?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: All three reviewers recommend acceptance (weak accept). They agree that the paper addresses an interesting problem, hierarchical  k-median clustering under average sensitivity, and offers both novel theoretical insights and practical experiments. In particular, the reviewers commend (1) the theoretical analysis, which provides nontrivial average-sensitivity bounds and approximation guarantees, (2) the clarity of proofs, and (3) the empirical comparisons demonstrating the proposed algorithm’s robustness relative to standard linkage methods and a deterministic variant of CLNSS.

There were some concerns on novelty, but the merits outweigh the concerns in my opinion.
Decision: Accept (poster)