On the Price of Differential Privacy for Hierarchical Clustering
Authors: Chengyuan Deng
Jie Gao
Jalaj Upadhyay
Chen Wang
Samson Zhou
Venue: ICLR 2025 Poster (2025)
Keywords: Hierarchical clustering
differential privacy
sparsest cut
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Hierarchical clustering is a fundamental unsupervised machine learning task with the aim of organizing data into a hierarchy of clusters. Many applications of hierarchical clustering involve sensitive user information, therefore motivating recent studies on differentially private hierarchical clustering under the rigorous framework of Dasgupta's objective. However, it has been shown that any privacy-preserving algorithm under edge-level differential privacy necessarily suffers a large error. To capture practical applications of this problem, we focus on the weight privacy model, where each edge of the input graph is at least unit weight. We present a novel algorithm in the weight privacy model that shows significantly better approximation than known impossibility results in the edge-level DP setting. In particular, our algorithm achieves $O(\log^{1.5}n/\varepsilon)$ multiplicative error for $\varepsilon$-DP and runs in polynomial time, where $n$ is the size of the input graph, and the cost is never worse than the optimal additive error in existing work. We complement our algorithm by showing if the unit-weight constraint does not apply, the lower bound for weight-level DP hierarchical clustering is essentially the same as the edge-level DP, i.e. $\Omega(n^2/\varepsilon)$ additive error. As a result, we also obtain a new lower bound of $\tilde{\Omega}(1/\varepsilon)$ additive error for balanced sparsest cuts in the weight-level DP model, which may be of independent interest. Finally, we evaluate our algorithm on synthetic and real-world datasets. Our experimental results show that our algorithm performs well in terms of extra cost and has good scalability to large graphs.

Published as a conference paper at ICLR 2025
ON THE PRICE OF DIFFERENTIAL PRIVACY FOR HIERARCHICAL CLUSTERING
Chengyuan Deng
Jie Gao
Jalaj Upadhyay
Chen Wang"
Samson Zhou
ABSTRACT
Hierarchical clustering is a fundamental unsupervised machine learning task with the aim of organizing data into a hierarchy of clusters. Many applications hierarchical clustering involve sensitive user information, therefore motivating recent studies on differentially private hierarchical clustering under the rigorous framework of Dasgupta's 's objective. However, it has been shown that any privacy- preserving algorithm under edge-level differential privacy necessarily suffers a large error. To capture practical applications of this problem, weight privacy model, where each edge of the input graph is at least unit weight. We present novel algorithm in the weight privacy model that shows significantly better approximation than known impossibility results in the edge-level DP setting. In particular, our algorithm achieves O(log" 1.5 n/e) multiplicative error for s-DP and runs in polynomial time, where is the size of the input graph, and the cost is never worse than the optimal additive error in existing work. We complement our algorithm by showing if the unit-weight constraint does not apply, the lower bound for weight-level DP hierarchical clustering is essentially the same the edge-level DP, i.e. 22(n2/E) additive error. As a result, we also obtain a new lower bound of (11/e] additive error for balanced sparsest cuts in the weight-level DP model, which may be of independent interest. Finally, we evaluate our algorithm synthetic and real-world datasets. Our experimental results show that our algorithm performs well in terms of extra cost and has good scalability to large graphs.
focus on the
INTRODUCTION
Hicrarchical clustering is fundamental problem in unsupervised machine learning that has gained significant popularity since its introduction in 1963 (Ward Jr. 1963). In contrast to flat clusterings, such the popular k-means and k-median, which provide single partitioning of the input dataset, hierarchical clustering (HC) recursively partitions the dataset so that similar items are grouped together at lower levels of granularity while dissimilar items are separated as high as possible. The resulting output is binary tree-like structure called dendrogram, whose leaves represent the individual items and whose internal nodes represent cluster of the items in its subtree, thereby organizing the relationships within the dataset into hierarchical representation. Moreover, unlike flat clusterings that require the "correct" number clusters as input and which can be difficult to ascertain (Thorndike) 1953), hierarchical clustering simultaneously captures structure all levels of granularity and thus does not need to determine a fixed number of clusters. Consequently, hierarchical clustering has numerous applications in areas where data intrinsically is organized into hierarchical structure, such as biology and phylogenetics (Sneath & Sokal 1973; Sotiriou et al.) 2003). community detection (Leskovec al. 2020), finance (Tumminello et 2010). and image and text analysis (Steinbach et al. 2000).
Even though these applications involve datasets with sensitive information, there has been little work on srrvacy-presevvngg hierarchical clustering. Imola et al. (2023) recently initiated study on cnffferentially-prival approximation algorithms for hierarchical clustering measured using the objective introduced by Dasgupta (2016), which quantifies the HC cost based on how early similar nodes are split in the hierarchy. In particular, the cost is the sum the weights of all edges, multiplied
"Rttgers University, (cd751, 551555, jalaj. upadhyay) Brutgers.. edu Texas A&M University, ( (jh hwwwjwww13,, samsonzhoul @egmail com Herr, and throughout, use Ō() and 2() to hide polylogn terms.

---

Published as a conference paper at ICLR 2025
by the size of the smallest cluster that contains both endpoints of the edge. Imola al. (2023) considered edge-level differential privacy, where the edges of the input graph represent the sensitive information that the output of the hierarchical clustering algorithm should be somewhat insensitive to changes to a single edge of the similarity graph. Intuitively, this is quite difficult to guarantee, since many common hierarchical clustering algorithms, such as single-likkge average-linkage (Hastie) et al. (2009) are deterministic and thus can change drastically when single edge of the graph is changed. Indeed. Imola al. (2023) showed that any s-differentially private algorithm on graph with n vertices would produce a hierarchical clustering with Dasgupta's 's objective value S2 (n²/E) additively worse than the optimal clustering.
Such large eπror renders the corresponding hierarchical clustering useless in most practical sce- narios. Consider, for example, a dataset whose nonzero costs construct a graph that consists of /n disconnected instances of an expander graph with (log -)expanssion (Kowalski, 2019) and on vn vertices. We remark that each expander can incur a cost at most (yn)* log n under the Dasgupta objective, and so by clustering each of the /n expanders together, the optimal hierarchical clustering cost is at most 1.5 log n. On the other hand, if we have a single connected (log n) -e)exanader on n vertices, then it can be shown that any balanced cut at the top level of the dendrogram incurs must have (log r1) edges that cross the cut. Since it is known that there exists a balanced cut that is a constant-factor approximation to the optimal hierarchical clustering (Charikar & Chatziafratis, 2017] Roy & Pokutta 2017). it follows that the optimal cost in this case is 52(n² log nt). Hence, algorithms with additive error Q /sn will not be able to distinguish between these two cases.
In light of these shortcomings, it is natural to ask whether more meaningful accuracy-privat tradeoffs are possible under less stringent notions of differential privacy. Another common notion is weight-level differential privacy, which assumes that the graph topology and connectivity are public knowledge but edge weights are sensitive. Therefore, the private mechanism in this scenario bounds the probability of distinguishing two neighboring graphs with the same connectivity, but different weights, where a pair of neighboring graphs have weight vectors that differ by an l norm of 1. Weight-level differential privacy great fit for many application scenarios where the underlying network topology is often public, e.g., Internet topology or financial networks. However, the weights on such networks may represent information that closely tied to user behaviors and activities and should be protected. Hence, weight-level differential privacy has been studied for number of fundamental problems such as all-pairs shortest paths and range queries [odwin et al. (2024); Chen
et al. (023); Deng et al. (2023); Fan et al. (2022); Fan & Li (2022); (Sealfon (2016).
Our Results. In this paper, we provide a comprehensive treatment for hierarchical clustering under Dasgupta's 's objective function with weight-level DP. To overcome the strong barrier in the edge-DP model, we consider the weight-DP model with a simple and rather unassuming setting where all edges have minimum weight We show there exists an algorithm this setting that achieves Ollgg" 1.5 n/e) multiplicative approximation. As complement of the upper bound, we next show that, surprisingly, the 2(n²/a lower bound still holds in the weight-DP model without the assumption. Finally, as by-product of our HC results, we provide new lower bounds for weight-DP balanced sparsest cuts, which is a related problem where the objective is to partition a graph into two sets with a minimal "relative" number of crossing edges. Our results highlight the power and limitations of the weight-level DP model for HC and related problems. We now describe these results in more detail, starting with our new algorithm.
Result 1 (Informal Statement of Theorem 1.. There exists an e-weight DP algorithm that given a weighted, connected graph G of size n with weight on each edge at least 1, in polynomial time computes HC T that achieves an O( glooo " -multiplicative approximation for the optimal HC cost.
Our private algorithm gives roughly Ologg n)) -approximation to the optimal cost. In the HC literature,
considered be a "sweet spot" solution (see, e.g. Dasgupta (201)): Charikar& & Chatziatratis (2017): Roy & Pokutta (2017); Agarwal et al. (2022); Assadi et al. (022)) ). In practice, allows us to "adjust" to specific instances, and produce HC trees tailored to the actual optimal cost. Compared to the poly-time algorithm in Imola et al. (2023), which has
n [og(1/6] additive error for (s, 6)-DP, our algorithm achieves cDP and has much better
performance on the aforementioned ms-nyy expander example.
2

---

Published as a conference paper at ICLR 2025
We will discuss shortly why the natural assumption for weight-level DP is the "right notion" for many privacy applications to obtain low approximation error on HC. Here, we first show that from a technical point of view, the unit-weight assumption is necessary.
Result 2 (Informal Statement of Theorem 3). Any E-weight DP algorithm that outputs an HC tree under Dasgupta's 's cost must have an additive error Qf(" /s). even for graphs with optimal HC cost (nn/e).
Our lower bound for weight-level DP matches the lower bound of 52(n2/e) /e) for edge-level DP (Imola et al. (023). Thus, our result precludes any practical algorithms for general graphs for either weight or edge-level DP. We present the formal theorem and the proof in Appendix C As a result of the lower bound in Theorem 3] we also obtain new lower bound for balanced sparsest cut for weight-level DP.
Given a graph G and a constant any s-weight DP algorithu that outputs a y-balanced sparsest cut has to have (2 (olg"= n)) expected additive error the sparsity of G.
Result 3 (Informal Statement of Theorem 2)
We emphasize that Theorem? 2 does not follow trivially from known connections between balanced sparsest cut and hierarchical clustering. The reason is: (i) known results deal with only multiplicative approximation, and (ii) we need to worry about the privacy loss with repeated balanced sparsest cuts. As such, we used novel reduction to prove Theorem 2 which may be of independent interest.
Discussions for our privacy model. We discuss why our privacy model is natural and the contexts of its applications. For applications whose edge weights are not at least we can scale up all weights by the same factor, and the combinatorial structure of the solutions to the HC does not change (although the cost of HC is also scaled by the same factor). Therefore, one can assume by default that the minimum edge weight is 1 when neighboring graphs have f norm of edge weights at most 1. This assumption also makes sense as the definition of neighboring graphs in the differential privacy model typically assumes that the magnitude of change is at an "atomic" level.
Furthermore, the model captures a wide range of applications. For instance, consider the financial network where the edge weights capture the transaction interactions or amounts, and users would like to protect the transaction information. This scenario is captured exactly by our weight-DP model with unit weight assumption: (i) the topology is public to the network hosts, and (ii) the weight is at least one since each interaction contributes one and a reasonable transaction amount would be larger than one. Another application is clustering in music libraries, e.g., the iTuunes library. The iTunes library is a bipartite graph where music/artists are on one side and users are on the other side. We know the graph topology from the album brought by the users. However, the number of times user has interacted with a particular song is private information. Here, the interaction counter starts with 1 because a user has downloaded the album.
Finally, we note that our algorithm in Result is robust for graphs that do not satisfy the unit-weight condition. For graphs with minimum weights S 1, our algorithm could achieve O (log "n multiplicative approximation with s-weight DP. The discussion and formal analysis of this approxi- mation guarantee shown in Proposition E.I
are
we implement the weight-DP algorithm for hierarchical clustering and evaluate its performance with respect to Dasgupta's 's cost. We observe that our algorithm produces significantly lower cost than input perturbation consistently synthetic and real-world graphs. We further remark that our algorithm in Result is the first DP hierarchical clustering algorithm with reasonable implementations on general graphs. Previously, the algorithms in Imola et al. (2023) for general graphs either take exponential time (the c-DP algorithm) or use very complicated theoretical subroutines for which no implementation is known (the (e, 6DP algorithm). In contrast, our algorithm is practical based on favorable performance and good scalability. Our codes are publicly available the Anonymous Githut
Empirical evaluations. In correspondence to Result 1
1.1 OUR TECHNIQUES
The algorithm with unit weights. The most natural approach to consider for our privacy setting is input perturbation. Naively, we would try to add Laplacian noise of Lap(? ! to every edge weight to
3

---

Published as a conference paper at ICLR 2025
obtain graph G. Then, can perform recursive balanced sparsest cuts the G to obtain an HC tree T. The hope here is that on the balanced sparsest cut S since each edge has at least unit weights, the noise scales at most with the sparsity.
Unfortunately, the simple idea as above does not work: although the balanced sparsest cut on G remains a balanced sparse cut on G. the converse is not true. In particular, let (S, V \ S) be a cut with high sparsity in G, and suppose E(S, V \ SS are of unit weights; then, because of the Laplacian noise, the sparsity of S in G can be very small. The same issue also happens if we instead list all the possible cuts, add Lap( (e) noise to each entry (Óg the global sparsity of G), and output the sparsest cut therein. Here, since we have 2n many balanced cuts, some of the cuts could have very large deviations in the noisy vector, which again breaks the utility.
Our idea to handle the above issue is to take advantage of the unit unit-weight condition, and "amplify" the gap between sparse and non-sparse cuts in G. To this end, we can use a fairly simple trick: we artificially "bump up" the weight of each edge G by O (ogg) before adding the Laplacian noise. In this way, cuts with high sparsity will never get chance to become low from the Laplacian noise. Furthermore, because of the unit-weight assumption, the actual sparsest cut S will not be affected by too much due to the increased edge weights (at most an O( O(log logg)) factor). As such, we can perform recursive balanced sparsest cuts and get the desired algorithm.
The lower bound for HC in weight-level DP. Our lower bound is inspired by the E-DP hierarchical clustering lower bound in Imola et al. (2023) for edge-level DP; however, generalizing the lower bound to our privacy model requires non-trivial additional work. The hard instances in Imola et al. (2023) come from the family of random disjoint 5-cycles. It is well-known in the literature that to minimize Dasgupta's 's HC cost on disconnected graphs, an HC tree should avoid splitting any edges before the induced subgraph becomes connected. In particular, for the family of random 5-cycles, if the HC tree splits the cycle edges in the bottom layers of the tree, the induced cost is at most (n). On the other hand, if the HC tree starts with partitioning (2(n) edges in the cycles, the induced cost at least ((n²). The key lemma of Imola et al. (2023) shows that any algorithm that is e-DP has to, unfortunately, cut many of the cycle edges, which leads to the desired lower bound of ((n²).
For the weight-level privacy setting, we need to argue that the topology information revealed to the algorithm does not break the lower bound. This is not true at first glance: for any fixed collection of 5 cycles, if the algorithm knows the graph topology, it can simply avoid all the cycle edges while being c-DP. Our idea to overcome the challenge is to "embed" the family of random 5 cycles into a complete graph. In particular, parriioulii
can fix the graph topology as the complete graph and put "important weights" only on edges obtained by random 5 cycles. In this way, we essentially preserve the source of hardness: the algorithm cannot be private if it always avoids the edges with high weights.
Due to space limits, we defer the technical overview of the balanced sparsest cut lower bound to Appendix F
PRELIMINARIES
We use IR to denote the set of real numbers and 122 denote the set of non-negative real numbers. We use the notation = (V, E, w) to denote a graph on the vertex set V. edge set E,, and weight function V x V + R 2o- The edge between two vertices and is denoted by the tuple (u, v) and its weight is denoted by wi, v). For a set of vertices A, B S V, we denote by
wo(A, B)
Σ
w(u, v).
When the context is clear, we simplify it by writing w(A,, B). We now introduce Dasgupta's framework for hierarchical clustering.
Definition (Hierarchical clustering trees). Given a weighted graph G= (V, E, w) with n vertices representing data points and m edges with non-negative weights measuring the pairwise similarities, we say a rooted tree T is a hierarchical clustering tree (HC tree) if the leaf nodes correspond to vertices V. and the internal nodes represent the splits of the subsets of vertices.
Definition (Hierarchical Clustering under Dasgupta's Objective (Dsguutta 2016)). Given a weighted graph G = (V, w)) Dasgupta's HC objective is to minimize the cost of 7 prescribed as
4

---

Published as a conference paper at ICLR 2025
follows:
costa(T)=
Σ
w(u,o) 17|u V o/],
(u,0)EE
where Tlu V e] stands for the subtree rooted at the lowest common ancestor of and [T[u V e] the number of leaf nodes induced by T(u V v/. The clustering is represented by T, where each internal node induces cluster.
Prior works (Charikar & Chatziafratis 2017 Cohen-Addad et al. 2019; Dasgupta 2016) have established connection between the (balanced) sparsest cut problem (Definition 9) and hierarchical clustering problem. In short, as long as the graph has non-negative weights, an a-approximation of the sparsest cut balanced sparsest cut implies an -aaaaaaproxximal clustering. The formal statement of such an algorithm is given in Proposition A.6
algorithm for the hierarchical
variety of privacy models have been studied for graph-theoretic problems with differential privacy. The key difference lands on the definition of neighboring graphs, which determines the sensitive information to protected by DP. Towards this end, most problems are studied under one or several of the following three privacy models: node-level (Blocki et al. 20033] Kalemaj al. 2023
Kasiviswanathan et al. 2013, [Seaffon& & Ullman (021]. edge-level ( (Arora & Upadhyay 2019 Boocki
ct al. 2012; Dalirrooyfard et al. [024 Eliás et | 2020 Gupta al. 2012 Imola et al. 2023 Liu
et al. 2024) and weight-level (Chen et al.] 2023 Deng et al. 2023 Fan et al. 2022 Fan & 2022
Sealfon (016). The focus of this study the weight-level DP.
Definition 3 (Neighboring weights). For graph G EV, let w, w V x + R>o be two weight functions that map any (u, v) E E to non-negative real number, we say w, w are neighboring, denoted as w ~ w/ if: Σ (u,))E [w(u, v) - w w'(u, v) S 1.
Now we can formally define weight-differential privacy
graph G.
Definition 4 (Differential Privacy). An algorithm A is (s, 6DD on a graph G = (V, E). if for any neighboring weights w w' such that G" (V, E, w'), and any set of output C, holds that:
Pr[A(G) E CJ < e Pr(A(G") E CC]+
If 8 0, say e e-differentially private G.
More standard technical tools in differential privacy are deferred to Appendix A
3 PRIVATE ALGORITHM FOR HIERARCHICAL CLUSTERING
We start by formalizing our privacy model rooted in the weight-level DP that we believe more appropriate for hierarchical clustering. This model has two assumptions in addition neighboring weights, formally as below.
Definition 5 (Neighboring weights). For a graph = (V, and weight functions w, w' E. - R20 we say w. w/ are neighboring, denoted as ~ w' if: (1) G is connected component. (2) For any e E E, wi 2 1. (3) Eeer [[w(e) - w' (e)ll < 1.
We remark that the model in Definition 5 is natural extension of the weight-neighborring notion in Definition 3) as discussed Section I| Our main algorithm for HC under this model is as follows.
Theorem (Formalization of Result M There exists polynomial-tine s-weight DP algorithm for any 0, such that given weighted, connected graph G of size n with weight on each edge at least 1, outputs a balanced HC tree T such that the HC cost by T is at most O log OPTG, where OPT is the optimal HC cost of G under Dasgupta's objective.
A few remarks are in order. If exponential time is allowed, we can achieve O (logn) multiplicative
approximation or O n logn additive error. Furthermore, by using an algorithm that could privately evaluate the HC tree costs, we could augment our algorithm with the algorithm in Imola al. 2023 to obtain an (E, D)DP algorithm with a cost at most
min (o( log 6 nn/loo (1/6)
OPT + O log ny /lg (1/6) O log
OPT + O 2.2 log" i log (1/8))
5

---

Published as a conference paper at ICLR 2025
which strictly improves the bound of Imola et al. (2023). Finally, if the graph has minimum weight of (0, 1]. our algorithm could still achieve s-weight privacy with O log
E-ax >aapproximation error
(see Proposition E. for details). We refer keen readers to Apppeddix such discussions; the rest of this section is dedicated to proving Theorem
3.1 A POLYNOMIAL-TING DP ALGORITHM FOR BALANCED SPARSEST CUT
We prove Theorem by showing polynomial-time e-DP algorithm for the balanced sparsest problem with multiplicative error at most Ollog" (ollog"((n))))) (n)/s), under the weight-level privacy model following Definition 5 Our algorithm follows simple procedure. First, overlay the input graph G by adding extra additive weight of (log n/e). Second, add independent Laplace noise Lap(1/e) to every edge weight. Third, run a balanced sparsest cut algorithm (in the classical setting) on the perturbed graph and output the cut. Privacy of the mechanism is guaranteed by the Laplace mechanism used in the second step, also known as imput perturbation, and the first step ensures that, with high probability, all the edge weights are positive. Therefore, we are allowed to run any sparsest cut algorithm by the post- processsnnsing theorem (Proposition A.2) in the third step. The output cut has relatively small error because the magnitude the perturbation is also small.
We still have to specify algorithm to produce the balanced sparsest cut. It is known that relaxation of this problem admits an O Vlooo ni) approxximaaio when edge weights are non-negative.
Proposition 3.1 (Charikar & Chatziafratis (2017); Krauthgamer et al. (2009). rephrased). There exists an algorithm that given graph G (V, w) such that w(e) Z 0 for all e E E, returns an O(ylogn) n)) approximation to the bulanced sparsest cul problem in polynomial time, Here, is the size of the inpul graph.
Our algorithm is given as BBLAYCEDSSPARSESCCCT-DD and uses polynomial time. We remark that is possible to adapt our algorithm further improve the utility bound by a multiplicative O[vlog factor, by using an exponential -ime algorithm that returns the optimal value of the balanced sparsest cut, rather than the polynomial-tine algorithm in the third step of algorithm. However, the resulting algorithm would then also use exponential time.
An c-DP Algorithm for Balanced Sparsest Cut Input: Graph G = (V, E, w). IV| privacy parameter >> O.
BALANCEDSPARRSSTCUUTAA
1. Ve E F., add 10 log n/e to the edge weight w(e), denoted G' (V, F2, w/) 2. Ve E F,, add independent noise ~ Lap(11 /e) to w/ we)), denoted as G" (V, F, w").
3. Run the algorithm from Proposition 3.1 on G" and return the cut S.
Now we provide the analysis of BALANNCEDSPARRESCCCTT-DD Due to space limits, we defer some proofs Appendix D
Lemma 3.1. The BALANCEDSPARRESTCCTT.D algorithm is E-DP.
Next, show the proof of the multiplicative utility bound, captured by the lemma below.
Lemma 3.2. With high probability, for any gruph = (V, E, w) whose minimum weight is at least 1, the BALANCEDSPARSESCCU-- algorithm returns balanced cut in polynomial-tin -imm with at most Olog n/e./////////// n./c)-approximation to the sparsity of the balanced sparsest cut.
3.2 THE COMPLETE E-DP ALGORITHM FOR HIERARCHICAL CLUSTERING
We present the s-DP hierarchical clustering algorithm using the sDD balanced sparsest cut algorithm we discussed in the above section. As well-known in the literature, the sparsest algorithm is recursively called to construct an HC tree. The process, first proved by Dasgupta Dasgupta (2016). can be shown as follows.

---

Published as a conference paper at ICLR 2025
Recursive Sparsest Cut for Hierarchical Clustering Input: Graph G = (V, E, w)
MAKETREF:
If [ = 1, return leaf containing V. Otherwise,
Run the algorithm in Proposition 3.1 with input (G), let the output be S.
Let Gg be the induced subgraph by S, similarly Gg for S.
Run MAKETREE(Gs) and MAKETREE((g))
Now ready for the complete private algorithm for hierarchical clustering.
CIEBARCCHCC.....SSTERENDDDD::: An c-DP Algorithm for Hierarchical Clustering Input: Graph G' = (V, E, w). privacy parameter e > O.
Run Steps and 2 of BALANCEISPARSISSCCUTR graph be G"
with input G an let the perturbed
Run MAKETREE(G"))
For the purpose of private hierarchical clustering, since all in the vertex induced subgraphs of G" a function of G" we can apply the post-processing theorem (Proposition A.2) to show that the our algorithm remains s-DP. Note that this is how we avoid composition and any potential error blow-up therein.
Privacy guarantee
We have shown Multiplicative approximation guarantee of CIIERARCHHCA.CLLUSTRNNNCC by Claim D.I that G" has all edges with non-negative weights with high probability, there- fore the MAKETREE involving the balanced sparsest cut algorithm can proceed without viola- tions. For the multiplicative approximation on every partition, we can perform the analysis of Lemma 3.2 on each vertex- -ereux-iddued subgraph. There are at most ((n) internal nodes, so we can apply union bound to make Lemma 3.2 hold with high probability throughout the process of CAWHARRCCHCACCLLSEEENNN
This ensures we can run O(log" 1.5 "n/s) approximation on all internal nodes, and obtain the desired multiplicative approximation by Proposition A.6
EXPERIMENTAL EVALUATIONS
We implement our new algorithm HIERARCHICAL HITRARCCHCALCTLUSSTRINGGG imental results in this section. First, evaluate the performance of algorithm in terms of Dasgupta's 's objective on synthetic and real-world graphs. Next, we show our algorithm has favorable scalability with large graphs (n 1000).
and demonstrate the exper-
Datasets and baselines. Following sequence of previous works (Cohen-Addad et al. 2017 Abboud al. 2019 Manghiuc Sun 2021 Laenen al.) 2023), we generate two datasets of synthetic graphs
from the stochastic block model (SBM) and hierarchical SBM (HSBM), then we select real-world datasets: IRIS, WINE and BOSTON from the scikit-leam learn package (Pedregosa al.) 201I). Some basic statistics of the datasets used can be found in Table 2 Appendix H For baseline methods satisfying weight-DPP we first consider input perturbation, which adds (1p(1/e) random noise to each edge weight then applies the recursive sparsest cut algorithm the perturbed graph. Input perturbation a simple mechanism achieving DP but could possibly lead to O(n²) additive error to the Dasgupta's s cost in the worst case. Next, include single, average and complete linkage methods, which are widely used in practice for hierarchical clustering. We apply the same perturbation scheme as proposed algorithm for fair comparison. Finally, we include the non-private cost for completeness.
4.1 PERFORMANCE ON DASGUPTA'S COST
Synthetic graphs. For graphs from both SBM and HSBM, we give edge weights by sampling uniformly random between and 10. The results shown in this section are based on 10 different
7

---

Published as a conference paper at ICLR 2025
graphs generated by the same set of parameters where p = 0.7 (intra- probability) and q 0.1 (inter- probability). We provide results on wider range of parameters for SBM and HSBM in Appendix H. As for the choice of E, the privacy parameter, we test all algorithms on {0.01, 0.1, 0.5, 2J. Note that e > is already considered as a weak privacy guarantee.
Dasgupta's Cost on SBM Graphs
Dasgupta's s Cost on HSBM Graphs
Algaritim
Aggrithm
Single
300
Ingut Porturbation
Average Linkage
Input Perturbation
Averaga Linkage Complete Linkage
Non Private
Complete Linkage
420-
Non Private
275
D con.
250
Disqupta's Coo.
400-
225
200
175-
360
150
340
125
100
0.0001
0:1
0.5
1=1
0.01
F:0.1
2= 0.5
Privacy Parameter
Privacy Parameter
Figure Comparison of Dasgupta's 's cost on SBM graphs of size n 150 and k 5.
Figure 2: Comparison of Dasgupta's cost on HSBM graphs of size n 150 and
Our results are shown in Figure I for SBM graphs and Figure 2 for HSBM graphs. The color bars attain the average costs, normalized by a factor of 1000, while the error bars indicate the max and min values, due to the randomness in graph generation and sampling Laplace noise. We can observe that our algorithm outperforms all other baselines by a considerable margin, especially when is small. In addition, the cost of our algorithm is comparable to the non-private cost in some good runs. Note that SBM and HSBM graphs have well-clustered structures, therefore our algorithm has greater potential to perform well in practice when the input graph has underlying clustered pattern.
weal-world graphs. Next, we evaluate our algorithm on real-world datasets. For each of the listed dataset, the similarity graph is constructed via the Gaussian kernel, where the parameters are chosen according to the standard heuristic (Ng et al. 2001), with the details in Appendix H We use the same values for c.
Dangspta's Dost IRSS
1300
Desgupta's Cast on DOSTION
30009
Desgusta Dest MIKE
Pettrtatonn
Anrian 1M00er
Pistacn Lelogg
30000
1300
EX0
10000
Dong
+009
/0/ Fasemater
Figure 3: Comparison of Dasgupta's 's cost on real-world datasets: IRIS, WINE and BOSTON.
All results on different graphs are shown together Figure The reported cost takes the average of five runs. Similarly as the synthetic graphs, our algorithm outperforms the Input Perturbation method in terms of the additional cost by a large margin. FFiuure T, Figure 2 and Figure 3 collectively show that our algorithm produces consistently better results across the range of the privacy parameter.
An interesting observation is that contrary to many DP algorithms whose error is very sensitive with the choice of E, the error does not change drastically with various values of s. The reason is that, unlike conventional DP algorithms that release values, our algorithm releases the HC trees. The final cost is obtained by cost evaluation on the original graph. For the privately computed HC tree, even if we use a smaller e value, the combinatorial structure of the weights in the graph is relatively preserved by our algorithm. Therefore, the approximation error is less sensitive with the choice of
8

---

Published as a conference paper at ICLR 2025
4.2 PERFORMANCE ON SCALABILITY
Scalability is a major gap between theory and practice on the performance of DP algorithms. Here we compare the running time of our algorithm, input perturbation and the algorithm for general graphs proposed in (Imola et al. 2023) with our own implementation. Note that the results in (Imola et al. 2023) are targeting SBM graphs, hence not applicable to general graphs. fact, the algorithm for general graphs propopsed by (Imola et al. 2023) has exponential running time due to the exponential mechanism, therefore may break down even for 10.
Table I: Comparison Runtime (8) with n 6, 6,8,1
peiutt Aup.rriigeii
HC Algocithm
ARerARChiCAl CLUSTERING- (Our Algurithon)
0.007
0.008
0.016
Imola et al.
2023 (Our implemenizzion)
0.298
29.373
>2h
Perturbation
20 683
2292
3900
Non-pricate Algorithm
0.007
0.008
0.013
Figure
Runtime with scaling up 1500
We first test all discussed HC algorithms on cycle graph with n - 6, 8, 10. As shown in Table the DP algorithm in (Imola et al., 2023) requires huge amount of resources handle graph of size larger than 10. The rest three algorithms have relatively close running time. We further show in Figure 4 that our algorithm scales also similarly as the standard con-private algorithm. The graphs used in Figure are generated from SBM with 5 clusters and varying sizes of each cluster.
5 A LOWER BOUND FOR THE BALANCED SPARSEST CUT WITH WEIGHT-LEVEL PRIVACY
We show the lower bound for the s-DP balanced sparsest cut in the weight-level DP model follows.
Theorem 2 (Formalization of Re.ult For any e E (0, 26 any constant y and n sufficiently large, any e-weight DP algorithm for babaaccee sparsest cut has to have 9 lo expected additive ervor in sparsity, i.e., let S be the output cut, let dG be the optimal sparsity, and let (S) be the sparsity of S, we have that
E [[ba(S)] > ΦG + +00
Elog" n
Note that the output range of balanced sparsity can be low as in even the unweighted graphs. As such, the Di log log" is very significant in many instances. Furthermore, Theorem 2 implies lower bound of Q1 log ,, additive error for balanced min-cuts (see Remark for details).
We prove Theorem 2 in this section. begin with, we remind the readers of the notation: we use éG denote the minimum sparsity of G, and we use (S) denote the edge expansion of S in G. We also focus on the case when 7 = 1, as the analysis for other constants follows from the same argument. Our main technical lemma for the proof
follows.
Lemma 5.1. Let A be an e-DP algorithm that outputs a --bllanced sparsest cut with log expected additive error for some constant C E (0. In other words, given a graph G, outputs partition of vertices (S, V \ S) such that
C
E [Wo(S)) dG
glogg n
Then, construct s-DP algorithm A' that outputs HC tree T, such that for any input graph G = (V, E, w), there is
(cott S 0(1) OPT +2 n
for the same constant C used by algorithm A.

---

Published as a conference paper at ICLR 2025
Before showing the proof of Lemma 5.1
first show how to use Lemma 5.1 to prove Theorem 2
Using Lemma 5.7 prove Theorem 2 By Lemma 5.1 if there exists an algorithm A with C
log" expected additive error for 1/3-balanced sparsest cut, it implies an HC algorithm A' with an OPT 1201 for sufficiently small C. This forms contradiction with our family of graphs as in Theorem (on which the additive error should be at n² ) which means algorithm A for balanced sparsest cut cannot exist. Theorem 2 D
expected cost of O(1) OPT 2C n²
least
The reduction algorithm, A'. To prove Lemma 5.1 we first show the reduction algorithm below:
A reduction algorithm, A', from balanced sparsest cut to HC trees Input: A graph G EV, w); algorithm, A, that outputs 3/2 4-balanced sparsest cut with expected additive error most C Tog
Define level cut as the cut that happens with the distance é - to the root of the HC tree (the entire graph G).
Let Ge be the family of vertex-induced subgraphs in level f. Initialization G1 {G).
For 1: ::000
1. For each vertex-induced subgraph H E Ge
(a) If (H)) = 1. skip this set and go to the next H E Gzi
(b) Otherwise, run A on S with e Ion log n and obtain the partition of H + (SI,
c|H|
(c) Add the partition H - (Si, S2) the HC tree T:
(d) Add G[S,] and G[S²] to G-+1-
2. Increase 8 (6 + l 1) and proceed to the next level.
all the vertex-induced subgraphs are singleton, terminate and output T.
In other words, we run the recursive approximate balanced min-cut with A, and as we go deeper down in the tree, decrease the value of adaptively. We defer the detailed analysis to Aopppedixx F
CONCLUSION AND DISCUSSION
In this paper, we revisited the cost of computing hierarchical clustering under the constraints of edge- level differential privacy. Previous work by Imola et al. 2023 showed that lower bound of Q(n² /e) (matched by exponential mechanism) and they gave an upper bound of Ö(n². 2.5 (og((/8)/s) under (e, -differrretta privacy. We argued that such additive error is too pessimistic for many natural classes of graphs. To assuage this concern, we explored the price hierarchical clustering under weight-level differential privacy, where showed that 2(n 2 /E) additive error is unavoidable for any general graph, which is too high to be of any practical use.
In pursuit of understanding the least assumption much more practical bound under a very mild (and practical) assumption. particular, if the edge weights are least 1, we can design polynomial time e-differentially private algorithm that achieves a purely multiplicative ((1/E) approximation. Without privacy, getting an Ó(1) approximation is the ideal goal in the context of hierarchical clustering. Therefore, we show that there is little price of privacy for hierarchical clustering under an assumption that is satisfied by many downstream applications of hierarchical clustering. This is in contrast with what previous results suggested.
the input graph, we showed that could obtain
Limitation and open problems. Our positive results only provide a multiplicative approximation that is larger than the best possible approximation without privacy; however, it would be interesting to know we can reduce the multiplicative approximation and understand potential tradeoffs between the multiplicative and additive approximation. Another open question to follow work is HC with approximate privacy: with our privacy model, is it possible to get improved bounds if we focus on approximate DP instead?
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
Deng and Gao are supported by NSF ISS-2229876, DMS-2220271, DMS-2311064, CCF-2208663, CCF-21 18953. Jalaj would like to acknowledge funding through Decanal Research Grant and unrestricted gift from Google. Samson Zhou is supported in part by NSF CCF-2335411. The work was conducted in part while Samson Zhou was visiting the Simons Institute for the Theory of Computing as part of the Sublinear Algorithms program.
REFERENCES
Amir Abboud, Vincent Cohen-Addad, and Hussein Houdrougé. Subquadratic high-dimensional hierarchical clustering. Advances in Neural Information Processing Systems, 32:1 1580- 11590, 2019.
Arpit Agarwal, Sanjeev Khanna, Huan Li, and Prathamesh Patil. Sublinear algorithms for hierarchical clustering. Advances in Neural Information Processing Systems, 35:3417-3430, 2022.
Raman Arora and Jalaj Upadhyay. On differentially private graph sparsification and applications. Advances in Neural Information Processing Systems, 32: 12:13111113222 2019.
Sepehr Assadi, Vaggos Chatziafratis, Jakub Lacki. Vahab Mirrokni, and Chen Wang. Hierarchical clustering in graph streams: Single-pass algorithms and space lower bounds. In Po-Ling Loh and Maxim Raginsky (eds.), Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pp. 4643 PMLR, 2022.
Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The LinisonmLinddesttruss transform itself preserves differential privacy. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pp. 4p.410 410-419, IEEE, 2012.
Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. Differentially private data analysis of social networks via restricted sensitivity. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, pp. 87-96, 2013.
Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay, and Chen Wang. The discrepancy of shortest paths. Proceedings of the 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024), pp. 27:1-27:20, July 2024.
T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):1-24, 2011.
Moses Charikar and Vaggos Chatziafratis. Approximate hierarchical clustering via sparsest cut and spreading metrics. In Proceedings of the Twenty-Fighth Annual ACM-SIAM Symposium Discrete Algorithms, pp. 841-8888 -554. SIAM, 2017.
Justin Y Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Shyam Narayanan, Jelani Nelson, and Yinzhan Xu. Differentially private all-pairs shortest path distances: Improved algorithms and lower bounds. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 5040-5067. SIAM, 2023.
Vincent Cohen-Addad, Varun Kanade, and Frederik Mallmann-Tress Hierarchical clustering beyond the worst-case. Advances in Neural Information Processing Systems, 30:6202-6210, 2017.
Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn. and Claire Mathieu. Hierarchical clustering: Objective functions and algorithms. Journal of the ACM (JACM), 66(4):1-42 2019.
Mina Dalirrooyfard, Slobodan Mitrovic, and Yuriy Nevmyvaka. Nearly tight bounds for differentially private multiway cut. Advances in Neural Information Processing Systems, 36:24947-24965, 2024.
Sanjoy Dasgupta. A cost function for similarity based hierarchical clustering. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 118-127, 2016.
Chengyuan Deng, Jie Gao, Jalaj Upadhyay, and Chen Wang. Differentially private range query on shortest paths. In Algorithms and Data Structures Symposium, pp. 340-370. Springer, 2023.

---

Published as a conference paper at ICLR 2025
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, ((3-4):21-440,, 2014.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ily Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Serge Vaudenay (ed.), Advances in Cryptol- ogy- EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 June 1, 2006, Proceedings, volume 4004 of Lecture Notes in Computer Science, pp. 486-503. Springer, 2006.
Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In 2010 IEEE S1st Annual Symposium on Foundations of Computer Science, pp. 51-60. IEEE, 2010.
Cynthia Dwork, Frank MeSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. Journal of Privacy and Confidentiality, 7(3):17-51, 2016.
Marek Eliáš, Michael Kapralov, Janardhan Kulkarni, and Yin Tat Lee, Differentially private release of synthetic graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 560-578. SIAM, 2020.
Chenglin Fan and Ping Li. Distances release with differential privacy in tree and grid graph. In 2022 IEEE International Symposium on Information Theory (ISIT), pp. 2190-2195. IEEE, 2022.
Chenglin Fan, Ping Li, and Xiaoyun Li. Breaking the linear error barrier in differentially private graph distance release. arXiv preprint arXiv:2204. 14247, 2022.
Anupam Gupta, Aaron Roth, and Jonathan Ullman. Iterative constructions and private data release. In Theory of Cryptography: 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings 9, pp. 339-356. Springer, 2012.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction, volume 2. Springer, 2009.
Richard Hladík and Jakub Tetek. Near-universally--opinn differentially private minimum spanning trees. CORR, abs/2404. 15035, 2024. doi: 1048550/ARXXV224444 org/10. 08000485504440 arwiv 2404. 15035
CRR.http::///t /ooi
Jacob Imola, Alessandro Epasto, Mohammad Mahdian, Vincent Cohen-Addad, and Vahab Mir- rokni. Differentially private hierarchical clustering with provable approximation guarantees. In International Conference on Machine Learning, pp. 14353 14375. PMLR, 2023.
Iden Kalemaj, Sofya Raskhodnikova, Adam Smith, and Charalampos E Tsourakakis. Node- differentially private estimation of the number of connected components. In Proceedings of the 42nd ACM SIGMOD- SIGACCT-ITTIIA Symposium Principles of Database Systems, pp. 183-194, 2023.
Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Analyz- ing graphs with node differential privacy. In Proceedings of the 10th Theory of Cryptography Conference on Theory of Cryptography, pp. 457-476 Springer, 2013.
Aashish Kolluri, Teodora Baluta, and Prateck Saxena. Private hicrarchical clustering in federated networks. In Yongdae Kim, Jong Kim, Giovanni Vigna, and Elaine Shi (eds.), CCS '21: 202 ACM SIGSAC Conference Computer and Communications Security, Virtual Event, Republic of Korea, November 15 19, 2021, pp. 2342-2360. ACM, 2021, doi: 2414444400200.448443883
URL https::/t//oooooo http://ooooorgg////////// 114./ 00005//44002000 3484822
Emmanuel Kowalski. An introduction to expander graphs. Société mathématique de France Paris, 2019.
Robert Krauthgamer, Joseph Naor, and Roy Schwartz. Partitioning graphs into balanced components. In Proceedings of the twentieth annual ACM-SIAM Symposium on Discrete Algorithms. pp. 942- 949. SIAM, 2009.
12

---

Published as a conference paper at ICLR 2025
Steinar Laenen, Bogdan Adrian Manghiue, and He Sun. Nearly-optimal hierarchical clustering for well-clustered graphs. In International Conference on Machine Learning, pp. 18209-18249. PMLR. 2023.
Jure Leskovec, Anand Rajaraman, and Jeffrey David Ullman. Mining of Massive Data Sets. Cam- bridge university press, 2020.
Jingeheng Liu, Jalaj Upadhyay, and Zongrui Zou. Optimal bounds on private graph approximation. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp- 1019-1049. SIAM, 2024.
Boggan-Adrian Manghiuc and He Sun. Hierarchical clustering: O(1 apppppppooinn for well- clustered graphs. In Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS 21), volume 34, pp. 9278-9289, 2021.
Benjamin Moseley and Joshua R. Wang. Approximation bounds for hierarchical clustering: Average linkage, bisecting k-means, and local search. J. Mach. Learn. Res., 24:1:1-1:36, 2023. URL https: jmlr. org/
balgg/paaee papers v24 111018118000000000 html
Andrew Y. Ng, Michael I. Jordan, and Yair Weiss. On spectral clustering: analysis and algorithm. In Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic, NIPS' 01, pp. 849 856, Cambridge, MA, USA, 2001. MIT Press.
Rasmus Pagh and Lukas Retschmeier. Faster private minimum spanning trees. CoRR, abs/2408.06997, 2024. doi: 10:48350ARXXV.2408.0000
URL htt.s::///oi.org/1....666
2408. 06997
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake Vanderplas, Alexandre Passos, David Couraapeau, Matthieu Brucher, Matthieu Perrot, and Édouard Duchesnay. Scikit-leam: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2833 2011.
Rafael Pinot. Minimum spanning tree release under differential privacy constraints. arXiv preprint 2018.
Ryan M. Rogers, Salil P. Vadhan, Aaron Roth, and Jonathan R. Ullman. Privacy odometers and filters: Pay-as-you-go composition. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp. 1921-1929, 2016.
Aurko Roy and Sebastian Pokutta. Hierarchical clustering via spreading metrics. J. Mach. Leurn. Res., 18:88:1-88:35, 2017.
Adam Sealfon. Shortest paths and distances with differential privacy. In Proceedings of the 35th ACM SIGMOD-SIGACTTSSIG Symposium on Principles of Database Systems, pp. 29 41, 2016.
Adam Sealfon and Jonathan R. Ullman. Efficiently estimating Erdōs-Rényi graphs with node differential privacy. J. Priv. Confidentiality, 11(1), 2021.
Peter H. A. Sneath and Robert R. Sokal. Numerical Taxonomy: The Principles and Practice of Numerical Classification. W. Freeman, 1973.
Christos Sotiriou, Sock- Ying Neo, Lisa M McShane, Edward L Korn, Philip M Long, Amir Jazaeri, Philippe Martiat, Steve B Fox, Adrian I. Harris, and Edison T Liu. Breast cancer classification and prognosis based on gene expression profiles from a population- National Academy of Sciences, 100(1 (MM))))1330 10393 103988, 2003.
study. Proceedings of the
Michael Steinbach, George Karypis, and Vipin Kumar. comparison of document clustering techniques. Technical report, University of Minnesota, 2000.
Robert I. Thorndike. Who belongs in the family? Psychometrika, 18(4):267-276, 1953.
13

---

Published as a conference paper at ICLR 2025
Michele Tumminello, Fabrizio Lillo, and Rosario N Mantegna. Correlation, hierarchies, and networks in financial markets. Journal of Economic Behavior & Organization, 75(1):40-58, 2010.
Martin Wainwright. Iligh-dimensional Statistics: A Non-Asymptotic Viewpoint, volume 48. Cam- bridge University Press, 2019.
Joe H Ward Jr. Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association, (8(301):236-22 244, 1963.
Qian Xiao, Rui Chen, and Kian-Lee Tan. Differentially private network data release via structural inference. In Sofus A. Macskassy, Claudia Perlich, Jure Leskovec, Wei Wang, and Rayid Ghani (eds.), The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '4, New York, NY, USA - August 24 27, 2014, pp. 911-920. ACM, 2014. doi: 10.1 10.1145/2623330.262555 2623644. URL https: doi org/
14

---

Published as a conference paper at ICLR 2025
A PRELIMINARIES AND KNOWN RESULTS
We introduce a few standard techniques in differential privacy and probability: Laplace mechanism, post-proces post-procsssing theorem, sum of Laplace random variables, composition theorem, etc.
Definition 6 (Laplace distribution). We say a zero-mean random variable X follows the Laplace distribution with parameter b (denoted by X ~ Lap(6)) if the probability density function of X follows
1
[
p(x) = (zp
= 2b
exp
Definition (Sensitivity). Let p the ee-siiiitvvity of the function f is defined as
1. For any function f X R defined over domain space X,
A fN
max [lf(w) - ((w')lpp
Here, ||0||p- (Ei=)
[ is the -n-norm of the vector RRd.
Based on Laplace distribution, we can now define Laplace mechanism standard DP mechanism that adds noise sampled from Laplace distribution with scale dependent on the f--sensitivity of the function. The formal definition follows.
Definition (Laplace mechanism). For any function f : + R* the Laplace mechanism input w E X' samples vi,..., Y2 independently from Lap Ar1 and outputs
Mc(f) = f(w) + (Yi,...,YE)
Proposition A.1 (Laplace mechanism Dwork al. (2016). The Laplace mechanism Mc(f) is e-differentially private.
Proposition A.2 (Post-processing theorem Dwork & Roth 20144). Let M : Rdh + Rd be an (e, o)-differentially private mechanism and let g Rd - Rda be an arbitrary function. Then, the function o M Rdd - dadaa is also (z, 5)-differentially private.
Proposition A.3 (Sum of Laplace random variables, Chan et al. (2011): Wainwright (2019)). Let [X A be a collection of independent random variables such that X; Lap(b.) for all I S m.
Then, for 2 v2,5 by and 0 < X < 2v/r"² for b = max, {bb}.
X2
Pr
Σ
X 2 X
2 exp
8u2
The following propositions characterize the composition of multiple differentially private algorithms.
Proposition A.4 (Composition theorem Dwork al. 2006 2016); |Rogers et al. (2016)). Let {A,)} be l algorithms with (Ej, D)-DP guarantees for j E k.. Furthermore, ler A be a function of the outputs of A2, ", with possible dependent calls and adaptively chosen parameters. Then, A (Ei E,, D)- algorithm.
Proposition A.5 (Strong composition theorem Dwork et al. 20100). For any 8, 2 0 and 8' > 0, the adaptive composition of (e, difffediiferentiaally private algorithms (s', k6 + 8¹) diifffeerettialll private for
/ 2k Im(1/8") - ke(e -).
Furthermore, if E 10 and 8' O, the composition of e-differentially private mechanism (eff8)-differentially private for
e' e'=8. 8k log( g
We now the definition of sparsest cut.
15

---

Published as a conference paper at ICLR 2025
Definition 9 (Sparsest Cut). Given weighted graph G (V, E, w) with |V| n, let S C V be a subset of vertices and |S] I n/2. Then the cut induced by , 5*) such that S arg minsgv w(S.S) is the sparsest cut of G, where $ = V S. S.
SS]
(0("",5") also known as the sparsity of the graph. For the convenience of The optimal value of og = 1841
notation, we also (5) w(S..)
to denote the sparsity of S in G, also known edge expansion.
[S|
We say the output is an (a,, (0, -))ppppoximmation of the sparsest cut if m((.8) if [S] y for some 7 E 1 2) the cut (5, S) is called 7-balaacedd sparsest cut. Similarly, one can define 7-balanced min-cut by S* arg min (S, 5) where |S| = 'yn for some 7 E [_ 2).
31 a &G + 3. Further,
The statement below formally connects (balanced) sparsest cut with hierarchical clustering with Dasgupta's 's cost.
Proposition A.6 (Charikar & Chatziafratis (2017); Dasgupta 2016)). Let T be an IIC tree that is obtained by recursively performing a-approximate 1/ 3/3-balanced sparsest cut on the vertex-induced subgraphs. Then, T gives an ((a)) approximatin the optimal Dasgupta's HC cost.
B ADDITIONAL RELATED WORK
We provide discussion about additional related work in hierarchical clustering and similar DP graph problems.
Hierarchical clustering with differential privacy. Obtaining differentially private algorithms for HC is a recent direction, and there are only few works before Imola et al. (2023). To the best of our knowledge, Xiao et al. 2014) the first work to investigate HC with privacy constraints. However, their work does not consider the optimization of objective functions. Kolluri et al. (2021) studied the differentially private algorithms under maximization variant of Dasgupta's objective, and their results are not directly comparable with ours (or those of Imola et al. (2023)). Outside the regime of Dasgupta's 's objective, the Moseley-Wang objective (Moseley & Wang (2023)) considered as the dual of Dasgupta's objective. Although there is no dedicated work for DP algorithms for the Mansley-Waaggaae
Moseley- Wang objective, it known that recursive random cuts result 1/3-approximation for the objective, which, in turn, is also a DP algorithm due to the independence of the graph topology and weights.
Minimum spanning trees with differential privacy. Another closely related graph problem that has been studied through the lens of privacy is the minimum spanning trees (MST), In this problem, the goal is to release set of edges that form a tree and span all vertices. For this problem, line work by |Sealfon| (2016); Pinot 20:8): Hladik & Tetek (2024): Pagh & Retschmeier (2024) have shown that the tight error bound for the weight-neighhorinng case is O(n log n/e) for e-DP algorithms. HHadík & Tetek 2004)); Pagh & Retschmeier (2024) further considered the aspect of universal optimality and running time. Moreover, these works also considered e-DP algorithms for neighboring graphs with too norm of the weights differs by at most 1, and obtained tight additive error bounds of On log n/e). We note that the results on MST cannot be directly compared to our results: on high level, the error induced by privacy mechanisms for the MST problem is easier to handle since the noises across edges do not accumulate.
C A LOWER BOUND FOR HIERARCHICAL CLUSTERING WITH WEIGHT-DP
Weight-differential privacy is different notion than edge-differential privacy. Thus, is not clear how the srivacy-utilityy trade-off for hierarchical clustering differs across two privacy models (e.g. Chen al. (2023); Sealfon (2016)). Specifically, the lower bound of Q(n2 /E) for the edge-level DP does not rule out a better additive eтror for the weight-level DP model. In this section, we show that the Q(n² /E) lower bound can be extended to the weight-level DP model.
Theorem 3 (Formalization of Result For any (0, 10) and sufficiently large, there exists a graph G of size n such that the optimal HC cost is (nn/E), and any e-weight DP algorithm for hierarchical clustering must have HC cost Q(n2
16

---

Published as a conference paper at ICLR 2025
Our hard family of graphs. We now construct family of the hard instances. The starting point of our lower bound is a similar construction in Imola et al. (202)). In particular, Imolaa et al. (2023) used hard family of instances as random disjoint cycles. Since operate with the weight-level DP, the graph topology is known, and we can no longer use the disjointness the cycles. Nevertheless, on all edges that are not part of the 5 cycles. In this way, a low-cost algorithm still has to avoid cutting any cycle edges on the first levels of the HC tree - property that tension with the privacy guarantee. The description of the hard family is as follows.
can still exploit this structural property by putting extremely small weights
=) A hard family of graphs for hierarchical clustering with weight-level DP
Topology: Let G = (V, B) be complete graph.
Edge weights:
Sample collection of 5 cycles uniformly at random, and this subgraph C3-
2. For each (u, u) E E. let wru,, u) = W with W = 20 e
Otherwise, for each (u, v) & E(Cs), let w(,, o) -
For the clarity of presentation, we first formally define the notions of the family and the collection of the trees with cost at most for each graph G' therein.
Definition 10 (Imola et al. Imola al. 2023), rephrased), Let Gn,s be the family of random disjoint 5-cycles where edges carry weights I. For each G E 9n.5, we define B(G,r) r) = {7 c7Sta(7) S r be the family of HC trees such that the induced cost for T on G is at most r. We call B(G,r) r) the collection of the trees of cost at most r for G.
A key technical lemma of Imola et al. [mola et al. 2023) is that, if an algorithm is e-DP, then the HC algorithm has to "incorrectly" cut many edges in the first partition. As a result, for many instances in the family of 5-cycles, their collections of trees of cost most Onn²) are disjoint.
Proposition C.1 (Imola et al. [mooaa al. (2023), rephrased). There exists a family of graphs
Fn,s S 9n,5 such that |n,s| 2 2n/5 and for any G, G' E Fn,5, B(G, 400
n² ((',,
n² 0.
300
Recall that our hard family of D(n,e), we have & < 1/20 in Theorem 3 we always have w(u, v) for edges (u, v) E E(Cs). We also prove that the optimal HC cost G is at most O
Lemma C.1. Fix any instance G obtained by s),,s), The optimal IIC cost of G is at most a.
Proof. Recall that we use T denote the optimal and OPT G denote the optimal cost of Dasgupta's HC on G. Let us construct tree T such that cost (T) < C m; and by definition of the optimal tree, we will have OPT I costo (T) S C. 2
The construction of the tree T is simple: we keep dividing the vertices into groups of disjoint 5-cycles until the internal node contains 5 vertices. an internal node x contains exactly vertices, we construct the subtree induced by z by removing one vertex at each level. In this way, we can have valid binary HC tree T.
We can now partition the HC cost of T as follows.
costo (T)
Σ (cC))
w(u, v) |T V e||
Σ
w(u, v) [T v vel.
(v.r))((C))
Note that for each 5 cycle, we pay cost of at most W. -100 + + 19W. summing over all the n/5 such cycles, we have that
Therefore,
Σ
w(u,w) w) |T V w)
n
19W
19m
W.
5
5
((C))
17

---

Published as a conference paper at ICLR 2025
On the other hand, note that each edge (u, v) can induce cost of most wou, u) Therefore, summing up at most n² /2 such (u, v)) edges, we have that
Σ
w(u, u) [T Voll
n²
1 n 2
(B.))E
Using W
20c and <
20 we have costo (7)
19n W +
O as desired.
now show technical lemma that would "reduce" the collection of the low-cost trees for G weight-neiighorring model to the edge-neighboring model.
Lemma C.2. Fix any < 1. Let C5. C32 E 9n,5 be two random disjoint 5-cycles, and let Üs and Ö₁ be the cycles with weight each cycle 1 Let G, G' be two graphs obtained by D(m,, 5) from Cs
n² W) (B",,, 400 and C. BB, 400
W) # 0, then B(Cs,
n²
WW WW) (BC( 300 W) # 0.
400
Proof. Recall that, for graph and > 0, ((G,r) == (T] costa(7) S is the family of HC
trees T such that the induced cost for T on G' is at most r. We prove the lemma by showing that
400 for any HC tree T, T B(G, =² W), then T E B(Cs, n²
400 W) Note that this will give us W)), which will lead to n² W) (and resp. B(G', n²² W) C B B(C), 400
n² BiG, 400 W) S B(Cs, 400
400
the desired result.
Fix an HC tree T E B(G, "²
W). We partition the HC cost and lower bound it with coste, (T):
costa(T)=
Σ
w(u v) |7|u v +
Σ w(u, v) [T oll
((CO)
(u,))EE(C))
cost (T)
E
w(u, v) [o] cost (T),
(L.))
where the last equality is because w(u, v) 0 in G. Since T B(G, W), we have that c7sta(7) < a²
W. This implies that coste, (7) I costa (T) < n²
W as desired. D
400
a00
We are now ready to prove Theorem 3 for the weight-level DP lower bound.
The proof basically follows the standard packing argument in Imola al. Imola et al. (2023) once we have (rrolishhd[Lemmn ; we provide a detailed proof for the purpose of completeness. Define Fk. as the family of graphs Dnn, E) such that the corresponding 5-cycles are from Fn,s. Note that in the neighboring graphs G, G' E FK.,, the change of weights (in L₁ metric) are most 2Wn. Therefore, we can use the same group privacy argument as in Imola et al. Imola et al. (2023) to obtain an algorithm A that is 2=Wn--rrve n-private on the graphs in the family FR,,- As such, fix any G, G' E Fk,, Then
Proof of Theorem 3
n² Pr A(C)) B(G', 400 w)) 2 exp ( (-2eWn) Pr (A(G') B(G',
n²
w))
400
Suppose, for the sake of contradiction; there is an algorithm which has an expected cost "?.W at most 1200 That is, for E [costo (A(G") &
Markov inequality then implies that S.. Therefore, have that
n².w 1200
Pr(costo 2 n'.
400
Pr A(G) E BIG,, nT
2
400 W)) 2 exp (-2eWW))
2n/5
On the other hand, by the contrapositive of Lemma C.2 we know that if B(Os,
n² W) W)n x² 400
400
a² W) 0. there is B(G, 400
n 400 W) 0. As such, we can get that [ > 2n/5 and
for every pair of graph G, G. B(G, TOO W) i B(G" Too W) 0. Therefore, we can apply the standard union-bound argument and show the contradiction argument as follows.
x²
x²
= Σ Pr (AIG) E B(G,, G'EFK.
n
W))
(by disjointness of the balls)
400
18

---

Published as a conference paper at ICLR 2025
E
2n/5
2a/5 1.
2d/5
G'EFRn
As such, we must have that |costo (A(G')
x2.W
(((2))
proving Theorem
1200
D PROOFS FOR THE ALGORITHM IN SECTION
D.1 PROOF OF LEMMA 3.1
Proof. The privacy guarantee follows from Step 2, where we are applying input perturbation. Each independent edge weight has sensitivity corresponding to data publishing, therefore adding noise of Lap(1/e) suffices for c-DP (Proposition A.
D.2 PROOF OF LEMMA 3.2
Proof. First that the SDP algorithm runs on graphs with positive edge weights. By the following claim we show this can be satisfied in BALANCEDSPARSISSCCUTDD with high probability.
Claim D.1. For G (V, E, w") defined in BALANCEDSPAARIISICU--DDD with high probability, it holds for any edge E E that w" 2 0.
Proof. Let Lap(1/e). Then we have:
Pr(X S -0 (ogn/s)= S 10 =
By the union bound, all edge weights are non-negative with high probability.
Claim D.J
We now continue with the proof. The multiplicative factor of O(log n/e) comes in two parts. The algorithm in Proposition 3.1 contributes an Ooooo factor, thus it suffices to show that the perturbation in step 2 leads to (log /pe))aaprooi Suppose the optimal cut of G is S such that ΦG
S(S.S) Let S" be the optimal sparsest cut on G". We have
|
War (S" S
Wor (S
(by the definition of sparsest cut of G")
1S"
|S]
War (5, + ΣK X;
(by construction)
|S|
()) + 10k log
Σt X;
log + X
dG
S
S
where k is the number of edges involved in the cut (S, S), and (X.) are independent random variables such that X; ~ (/E)). Recall the definition of our privacy model, we have w(e) 2 1 for Ve E E. then & I (S, Applying Proposition A.3 we have:
(-80k (-x0
(-
800 log n/63.
Pr
X,
80k log n/s
< 2 exp
110
8k
That is, [3T Σ
1
X;
10 10 (w
10 log
dG holds with high probability. It follows that:
E|ST
WG (S",
10k log
+ Σ 1== X
200g logn
S ΦG +
$6
O(log n/e) &G,
I
as desired.
Lemma 3.2
E MORE DISCUSSIONS ON THE APPROXIMATION FOR THEOREM
We discuss other forms of approximation for the algorithm in Theorem In Section we discussed that compared to additive errors. the multiplicative approximation better captures clusterability for hierarchical clustering. Nevertheless, we provide some analysis for the additive error of our algorithms.
19

---

Published as a conference paper at ICLR 2025
E. BLENDING ALGORIHTM WITH MULTIPLICATIVE AND ADDITIVE ERRORS
Note that in our privacy models, the algorithms in Imola et al. 2023 remain private. When OPTG onn2/ log 0.5 n)) (OPTc o(n² 2.5 log 0.5 n2) for poly-time algorithms), our algorithm is strictly better than the algorithm Imola al. (2023). On the other hand, the algorithms Imola et al. (2023) become more competitive when OPT becomes large. As such, a natural question is whether we could "adjust to" the algorithms based on the input instance and output with the one with the smaller error.
Running different algorithms in parallel and outputting the one with the smaller error is a standard trick in approximation algorithms. Nevertheless, for differentially private algorithm, we need to make sure that the selection between different algorithms retains privacy. For our purpose, even if we obtain HC tree T from a private algorithm, some privacy loss will incur after we evaluate the HC cost on the original graph G. As such, we would need an E-DP algorithm that could return the cost of HC tree.
We present such an algorithm this section and show that we could indeed get smaller error among the additive and multiplicative algorithms (albeit with small loss). Our main lemma for the private evaluation of the HC cost is as follows.
Lemma E.1. There exist s-weight DP algorithms such that given a weighted, connected graph G of size with weight each edge least I and an HC tree T, with high probability, in polynomial time computes number costa (T) such that
costa (7) & cTSta(T) S costa(7) + O( log
8
where (T) is the true (Dasgupta's 's HC objective) cost Tf G.
Proof. The algorithm is simply as follows.
Compute the cost tree T on G.
Add Laplace noise with Lap( to the output cost.
For privacy, we claim that the sensitivity of the function (T) is most for weight--niighooring graphs. Such claim has been shown in Imola et al. (2023) (for the edge-neighboring model), and we give the statement and proof for the purpose completeness.
Claim E.2. Let G (V, E) be graph and w and w' be neighhoring weights as prescribed by Definition 3 Then, for any fixed HC tree T, there is
Icosta, (T) costs. un (T) Sn,
(T)
where costo, (.) and costg, (-) are the (Dasgupta's 's HC objective) costs T under u and w', respectively.
Proof.
The difference in Dasgupta's costs can be bounded follows.
(cost,, (T) - costg, (T)==
Σ (M
w(u, v) 17 Vell- Σ
u'(u,u).I7te V
(u,o)E
Σ (w(u,w) w) w w'(u, v)) [u v]
(w(u, v) w'(u, v)] IT w]]
(u.F)EE
E a:l < Σ, |ai| for real numbers)
20

---

Published as a conference paper at ICLR 2025
Σ lu(u, w (u, v)l
(1,F)E (T I n since the root contains at most n vertices)
< n,
(by the weight-neighboring definition)
claimed.
Claim E.2
As such, by Proposition A. the algorithm is c-DP. Finally, for approximation guarantees, note that by the concentration of Laplace distribution, we have that
Pr additive enror 10 nlogn
1
exp(-10 log - n2
E
which is as desired.
Lemma E.
Using Lemma E. we could perform the "outputting the algorithm with the smaller error", and obtain the following result.
Lemma E.3. There exist a (e, -'-weight DP algorithm such that given a weighted, connected graph G of size with weight each edge least for any (0, 1), in polynomial time outputs HC tree T whose cost is as most
min {or lon 8
n//o (1/6)
OPT + O(" 10 log " /oo (1/6) O( OPT + 0(" 00"""""0"""" log" n nlgs (l/6(())))
(1/61)
where OPT is the optimal HC cost of G under Dasgupta's 's objective.
Proof. The lemma follows by running both our algorithm and the algorithm in Imola (2023), evaluating their cost privately with the algorithm of Lemma E. and outputting the HC tree with the smaller cost. Let be the resulting HC tree from our algorithm and T' be the resulting HC tree from the algorithm in Imola et al.
(202)). For the purpose of privacy, the parameter input (note that the only part we need perform approximate
for each algorithm is 8 =0(-
llo/1/// 1/6)
DP is the algorithm of Imola et al. (2023) Since the final algorithm is only a function of T. T CT) (T'), the privacy guarantee follows from the composition (Proposition A.5 and post-processing (Proposition A.2). Finally, the approximation guarantees follow from the respective error of the algorithms plus the additive error during the private cost evaluation in Lemma F.
Note that the condition of E (0.1) is just for the conciseness of the statement. For E > 1, we could similarly use the composition in (nPopoosition A.5, albeit there will be an additional E (ef 1) term. We omit the details for the cleanness of the presentation.
E.2 EXPONENTIAL-TIME ALGORITIIMS
We now show that if we are allowed to use exponential time, we can get stronger bounds for the multiplicative error than that of Theorem and we obtain an additive error of most O QQn"" log as in Imola et al. (003)). These algorithms are not practical; nonetheless, they highlight the extent of approximation can get for c-DP algorithms.
The formal statement is given as follows.
Lemma E.4. There exist e-weight DP algorithmms such that given a weighted, connected graph G of size n with weight on each edge at least 1, in exponential time outputs an HC tree T whose cost is at most
logn min for Log
OPT + 0 n logg
OPT + O n² loo n
where OPT the optimal HC cost of G under Dasgupta's 's objective.
Proof. The algorithm could be obtained by the algorithm from Imola et al. Imola et al. (2023). our CIERARRHHCALLLLSTEENN -D in Theorem I] and the private evaluation algorithm Lemma E. As such, we only sketch the proofs, and leave the full proof as exercise for keen readers.
21

---

Published as a conference paper at ICLR 2025
For the algorithm with O log multiplicative error, in the following manner: on step of BALANCEDSPARSESTCCUS HIERARCHICALCLUSTENNN instead of running the approx- imation algorithm in Proposition 3.1 use 2" time enumerate all cuts, and output the cut S with the lowest sparsity. With minor modification of the analysis of Theorem 1, it is easy to see that the output cut is an ( log multiplicatiive approximation of the 1/3 1/3-balanced sparsest cut. As such, we can use Proposition A.6 obtaín the desired approximation guarantee for HC.
For the algorithm with O logn) additive error, we can run the exponential mechanism as in Imola al. Imola et al. (2023). Finally, with the same argument of Lemma E.3
both algorithms and their private cost evaluation with parameter e/4, and use composition (Proposition A.5) and post-processing (Proposition A.2) to obtain the desired statement.
E.3 APPROXIMATION GUARANTEES GRAPHS WITH WEIGHTS
In this section, we discuss the implication of our algorithm on graphs with weights less than 1. We show that the approximation guarantee of WAA.CCCCCCCCSSSERIINNCCCC and for any graph with the minimum weight least a, we could achieve O approximation.
is fairly robust,
log "-muliiplicative a.
Proposition E.1. The algorithm CIERARCHHCALLCLUSTTRRNNCC more, given a weighted, connected graph G of size n with weight on each edge at least a, HIBRARCHICALCLUSSTRRNG
is e-weight DP. Further-
outputs HC tree T such that the HC cost by T is most OPTo, where OPT is the optimal HC cost of G under Dasgupta's 's objective.
0
log "n
Proving Proposition E. would require a repetition of all the steps we did in Theorem I Therefore, we provide proof sketch on why the lemma true. The privacy guarantee of Proposition E. follows directly from Lemma 3.1] and the approximation guarantee is based on the following lemma.
Lemma E.5. With high probability, for any graph G (V, w) whose minimum weight is least o, the BALANCEDSPARSESTCCTT. algorithu return a balanced cut in polynomial-tin time with at most O log multiplicaaiive approximation to the sparsity of the balanced sparsest cut.
a-E
Proof. The proof of Lemma E.5 follows by the same argument of the proof of Lemma 3.2 (as in Appendix 1..2 with slight modifications. In particular, by the same argument, optimal sparsest cut S of G, and suppose there are edges in the cut. Let X, be the random variable for the Laplacian noise added on the i-th edge of the cut (S, [S]), we could again show that
let S be the the
WG (S" S""
log + X;
òG
8""
Furthermore, by the argument with concentration inequalities, we have that
10 10.kllogg
X₁ <
S
E|S]
Note that by the condition of w(e 2 a for all F, we have that h < w8(3))) As such, we have that
WGn (S" S"")
n < ΦG + 200g log
Ollog
a.e = PG.
S
a
Finally, as in the proof of Lemma 3.2 an extra factor of OVllogn) n) induced by Proposition 3.1 which gives the desired lemma statement.
The multiplicative approximation bound of Proposition E. then follows from the same argument as the proof of Theorem 1 by losing factor of O(1/a).
22

---

Published as a conference paper at ICLR 2025
E.4 E-DP POLYNOMIAL-TIME ALGORITHM WITH O log
ADDITIVE ERROR
We now give a polynomial-time E-DP algorithm that gives O(vn) multiplicative approximation with O(" log" ") additive error. We note that the approximation guarantee of this algorithm is strictly worse than the algorithm Lmmma E.3 Nevertheless, the algorithm pure DP, and does not need to call the algorithm in Imola et al. (2023) (note that it is unclear how the poly-time algorithm in Imola et al. (023) could be implemented). As such, we believe the algorithm has its own ad advantage for certain scenarios.
Lemma E.6. Given a weighted, connected graph G of size n with weight on each edge at least 1, for any 0, the HC tree T computed by CHERARCHICALCLUSSERNSS
in Section 3.2 cost at most (T) Σ ((Vlog OPTs + O(" log' log'"") "), where OPT is the optimal HC cost of G under Dasgupta's objective.
The key notion we need to prove Lemma i. the optimal balanced tree balance We now formally define the notion and analyze its properties.
Definition 11. We say an HC tree Thalance is balanced tree if every internal node is 1 1/3-balanced partition, i.e., for any partition H + (S, H 8) in Thalance, there is min [1S), | [S) 2 !il
3
We use Thalance to denote the optimal tree among the balanced tree, i.e., costa (Thalance) costa (aotG((Tann (Thulance) for any balanced tree Toulance.
By Proposition A.6. we can immediately observe that the tree The balance achieves an O opp)-opproinnttion to the optimal HC tree T
Observation E.1. Let Thalance be the optimal tree among balanced trees G. Then, we have costa (Tbalance) I ((1) OPT
Observation E. is true simply because the tree we obtained by the recursive balanced sparsest cut is a balanced tree. We now use balanced trees as a 'bridge' between the costs on and the perturbed graph G"
Lemma E.7. Let Toatance be any balanced HC tree as defined by Definition 11 and let G" be the graph obtained by steps I and 2 of B/BALANCEDSSARSSSTCTT... Then, with high probability, have that
cost CosteG(Tuune (Tbaianne) costo (Thaiance) I costg" (Tnaaaance) + O n loo
Proof. We prove the first inequality by showing that with high probability, w"(u, is essentially the same proof as Claim D.I we can show that with probability at least 1 - 1/n1" there is w" (u, v) 2 w(u, v) for all edges (u, v) e E. Therefore, the cost of the same tree Thalance on G" cannot be lower than the cost of Tallance on G.
(u, v) > w(u v). This
For the second inequality, we first observe that by step 1, the additive error on each edge 10log We now show that with high probability, the additive error on all edges by the Laplacian noise is at most 10 Again, this is by the same calculation as in Claim D.1 as follows. Let X,,, ~ Lap(1/E) be the random variable for the Laplacian noise on (u, v). we have
Pr(Xu.v 2 10 S e- 1000loo =n 10
and we can apply a union bound over all edges to get that with high probability, wig (u, v) S 20 20 n for all (u, v) E E.
wG (u, v) +
We now bound the additive error for Toalance from G" G. In the same way as the proof Lemma 5.1 we define level cut as the cut that happens with the distance & - to the root of the HC tree. Let
H (S, 5) be a partition in Thalance of level we first observe that
(# of edges in ê-level partition H + (S, H 8)) < 2 1))
since bigger partition reduces size by at least a factor of Therefore, we can upper-bound the cost of Thalance G as
cost (Thalance)
23

---

Published as a conference paper at ICLR 2025
Σ
won (S, H -)- [H]
- (S, 8) indused nodes in T
E
E
WGn (S, H - [H]
Em1 H ( H S)
induced by nodes T
Σ
E
Wan (u, v) |H]
H (S (s.))EE(S.H)53)
induced by nodes in level
Σ
E
walu, v) +
20 20
|
H H induced by nodes (UN))E((S on level F
(by the relationship between wa(u, v) and war (u, v))
Wc(S, H S)+ 20
2 (2e( [H|
Σ (S
1=1
induced by nodes in on level
(by the bound the number of edges in the partition)
Σ
wo H 5) [
1=1 H HS induced by modes in level &
20n log
Enn
Σ
| ( 2((-))
2
E
H (8, S) on level E
induced
20n² log
2 (220111
<costa (aiii(TThun [balance)
28-1
(3
E=1
(H)) S n and there are 2 partitions on level
3 log + O0
<costg (Tbalance)
E 2 2 2 0())
E
as desired.
Finalizing the proof of Lemma E.6 in HIERARCHICALCLUSTERNN
We run OVVlog n) -approximate balanced sparsest cut G" In the end, the algorithm produces tree T such that
costo (T) S 0((v logn) costa" (T (G")) ((Voogg) costo" (Toilnne))
where (G" the optimal HC tree on G". Since both and Thatance are balanced trees, we have costa(T) s costa" (T)
(using the first inequality Lemma E.7
< 0( log costg (Thatance)
O n log n
0 1ogg)) (costa( Thulanne))
(using the second inequality of Lemma E.7
<O(Vlogn) costa (Tratunce) + O n2 loo 1.5
desired by the lemma statement.
Lemma E.6
24

---

Published as a conference paper at ICLR 2025
F THE ANALYSIS OF THE LOWER BOUND IN [SECTION 5
In this section, we provide the analysis of the reduction for the balanced sparsest cut lower bound.
High-level technical overview. The balanced sparsest cut lower bound. The connection between the balanced sparsest cut and hierarchical clustering is well-known in the literature. Therefore, natural idea to prove lower bounds for e-DP balanced sparsest cuts through a reduction argument from E- DP hierarchical clustering.
There are two technical challenges to formalizing the above idea. The first challenge is that existing results between balanced sparsest cuts and HC focus multiplicative error, while we need to show lower bound with additive error. This would require us to open the black box of the existing technical lemmas, and
white-box adaptation of the "charging" argument of Charikar & Chatziafratis (2017). The second, and perhaps the bigger challenge, is the loss of privacy in the process. To obtain the HC tree, we need to run the e-DP algorithm for the balanced sparsest subgraphs, which requires repeated queries for up to (()) times. As such, by the strong composition theorem, we need lose a factor of yn on the additive error, and we can only obtain an HC algorithm for (s, 8) appprxximaee DP- for which we can only prove lower bounds for very small
on vertex-induced
Our idea to tackle this issue to use more restrictive privacy parameters as we go down the HC tree with the balanced sparsest cuts. For the cuts on level (from the root), we run the DP balanced sparsest cut algorithm with & scaling with the size of the current partition, i.e., when we run the algorithm on H, we use Eн = [H| e (we use H for the number of vertices in H). Since we have
Σn | on each level, the privacy loss on this particular level most E. Furthermore, since the depth of the HC tree T can be at most O(logn) due to balanced cuts, the privacy loss is at most Ollog n), which can be handled by rescaling.
n
The final missing piece here is the impact of changed e in the additive error. Since we decrease the parameter E, the additive error increases. Nevertheless, we can show that on each partition, the blow-up is roughly O (( Therefore, if we sum up the partitions of a level, the additive error is bounded by O n²
As such, we can again use the fact that the HC tree is balanced to obtain the
total additive error of O (onn) and the extra cost can again be handled by rescaling of e.
The privacy analysis. We first show that the reduction algorithm is e-DP. The formal statement is as follows.
Lemma F.1. The reduction algorithm that oulputs the hierarchical clustering T satisfies e-D..
Proof. First, note that we adaptively provide a privacy budget in Step 1(b); however, it should be noted that H is computed using a private mechanism, so this choice in the reduction is -rrracc-reeevvinggg as long as the total privacy budget is at most e. The final output HC tree T is a function only depending on the internal balanced sparsest cuts. In other words, T is function of the algorithms (.A, ) where A, is the algorithm .A induced on the internal node j. and is the total number of internal nodes. Let =(k) be the privacy parameter of the cut internal node k. By Proposition A.4 the reduction algorithm satisfies DP with parameter
Eyrs
Σ E(k) J=1
Σ
CH
Emax E,
2 2 n
8=1
on level (E (0
where lmnx is the maximum level of the HC tree, and the last equation is due to En level (t & for every level L.
Since the tree always balancee, the number of levels is at most loga/2 n S 2 log n levels. As such, we have that the privacy parameters satisfies 2lgg Lmax E S as desired.
AAthhough we did not include a proof for the HC lower bounds with (s, 6)-DP, it appears the proof in Appendix would still work for 5 1/2
25

---

Published as a conference paper at ICLR 2025
The utility analysis. We now proceed to the utility analysis of the reduction algorithm. To this end, we first show that the balanced sparsest cut guarantee would lead to balanced min-cut guarantees, and the latter is easier work with.
C additive error for some constant Claim F22 Let (S, V () be 3 3-bulanced sparsest cul with elog"
C' E (0, 1). Then, S is an (2, C let (Sman, V \5min) be the / 1/3-balanced min-cua of G, we have that
2: log" approximation of the 1 1/3-balanced min-cut. In other words,
Cn
w(s \ S w(Smin V Smin)
2e log"
Proof. Let Seporse be the -ballanced sparsest cut of G. By the guarantee of A, we have that
w( (Sspapae V Saparse)
C
(8, V 18)
+
[S]
(by the property of .A)
Saperse
E log"
2
w( Smin V Smin
|S| +
|||
(by the definition of the sparsest cut)
Smmin
log" 2
Cn
2 w w(Smin V gmin) +
S 2 and
||| S
2: log 2
S Toaee
n
as desired.
Let the output of A' on the input graph G be A'(G) T. Using the expression of the cost function as stated eq (1), the expected cost of T
[costa (7)
Σ
S2)
H (S1, S2)
Linduced by nodes
Σ
( S2) [H]
(by linearity of expectation)
(SI.
induced by nodes in T
Σ
2 2.w(S w(Smin (.HHHHHHHHH Smin) |
(S1. S2) induced by nodes T
Smin is the balanced min-cut for vertex-induced graph H)
Σ
C.
1
H
|
22H
log² n
(S1. $2) induced by nodes in T level
(by the property of the algorithm A and Claim F2
Note that in the last term, have induced subgraph H.
| Tog"
opposed
log Toga since operating the vertex-
We now analyze the two cost terms respectively. We first bound the summation of the former term. Lemma F.3. Let be the tree obtained by recursive 1 //3-balanced cut whose cuts are represented by H + (S1, S2). Furthermore, let (Smán, V(H) \ Smin) be the bulanced min-cuts of V (H). Then, we have that
Σ
2 wi Sminn V(H) Smin) | S O
H (S1. Sa) induced by nodes
The proof of Lemma F.3 requires a white-box adaptation of the charging argument used by Charikar & Chatziafratis (017) (see also, e.g. Agarwal et al. (2022): Assadi et al. (2022)). The idea is
26

---

Published as a conference paper at ICLR 2025
almost identical to Charikar and Chatziafratis Charikar & Chatziafratis (2017), but the argument is considerably involved. As such, we postpone the proof to Appendix G
We now analyze the summation
H log n
Σ
C
[
2
(S Ss) induced nodes in T
for the additive eπror. The main lemma for this term is follows.
Lemma F.4. Let be the tree obtained by recursive 1/3-balanced cut whose cuts are represented
by H > (S1. S2). Then, we have that
Σ
Σ
C.
H log n1
| S C
n²
2
E=
H (S1. S2)
induced by nodes T ?
Proof. Note that at level E, the cost at most
Σ
C
2
s.t.
Σ
[ n.
2
log n
level (e
H level
By plugging our choice of Eh
|
we have that
2 n
2
n
H
C
2n log
H
Σ
2
log"
2
H
log n
H level
H level (E
Cn
Σ
elog n
H. on level 1)
Cn²
(since Σn Ht on level - 1) [H] n)
Elog n
Finally, we get the tree T using 1/3-balanced cuts. As such, there are at most log3/2 S log levels. Therefore, the total cost induced by the summation in Lemma F.4 is at most
Σ
C
H
| S 2logn e elog n E
Cn2
20 n²
2
log"
H - (S1. S2) by T
on level
as desired.
Wrapping up the proof of Lemma 5.1, By Lemma F. more, by Lemma F33 and Lemma H.4] we know that
the reduction algorithm c-D.. Further-
E [costa(7]] (()) 2C n²
as desired by the lemma statement.
Remark F.5. In the proof Lemma 5.1 we essentially embedded a reduction from balanced sparsest cut to balanced min-cut. Using the same argument, we could argue that for balanced min-cut, the additive error for any e-DP algorithm is at least Q [ The result essentially follows from
log=
Lemmas F3 and F4 and omit the repetition write the proof.
27

---

Published as a conference paper at ICLR 2025
G THE PROOF OF LEMMA F.3
We provide the proof Lemma F3 in this section. To begin with, we first recap the lemma statement as follows.
Lemma F.3. Let T be the tree obtained by recursive 1/3-balanced cut whose cuts represented by H + (S1, S2). Furthermore, let (SH V(H) \ $H be the balanced min-cuts of (H). Then, we have that
Σ
2 WSS V(H) SH [H] S ((1) OPT
H + St) induced by andes in T
To prove the lemma, need to white-box analysis of the charging argument for sparsest cuts and balanced min-cuts as in Charikar and Chatziafratis Charikar Chatziafratis (2017) (see also, e.g.
Agarwal et al. AAgaraa et al. (2022) and Assadi et al. [Assadi et al. (2022). ). In particular, consider any HC tree 7 and any edge uu 0) E E, they use the following notion of 'cost footprint' to lower
bound the optimal cost.
Definition 12 (Edge cost footprint). Let G (V, w) be weighted undirected graph, and let T be an HC tree of G. For any edge (u, v) E E and integer t 2 1, we say the cost footprint of edge (u, u) E E in T of size t, denoted as edge-cost?>(1, v)), is as follows:
(wu o), if (u, v) crosses any pair of maximal clusters of size at most t in T; 0, otherwise.
coge-cost+
Intuitively, the notion of edge-costy ((u, u)) captures the "levels" where edge (u, v) would pay non-7ero costs. To elaborate, consider an edge (u, v) E F. Before the edge is split, it pays no cost. After the edge is split, and suppose the size of the cluster on which (u, v) is split is then (u, v) pays exactly a cost of s w(u, v) to the cost. In Definition 12 note that for any t 2 8, we will have ooge--oott v)) = 0. On the other hand, for any S 8 1, since the two clusters that are induced by the edge split of (u, v) are of size at most (s - 1). we have edge-costy ((u, e)) = (u, v) for t E [0, s - 1]. Therefore, the summation En edge-coste ((u, u)) exactly characterizes the cost contribution for (u, v) the HC objective. More formally, this structural property is characterized as follows.
Lemma G.1 (Charikar and Chatziafratis Charikar Chatziatratis (017)). cf. Assadi et al. (0222)
For any graph G (V, w) and any of its HC tree T, there is
cost (7)
Σ I=U (u,D)E
edge-cost( ((u,
At first glance, working with the notion of edge cost footprint appears make things more com- plicated. The advantage of using such notion is that it allows us to 'charge' the cost of the tree into 'balanced' partitions. In particular, the following technical statements shown by Charikar and Chatziafratis Charikar & Chatziafratis (2017) and Assadi et al. Assadi et al, (2022).
Claim G.2 (Charikar and Chatziafratis Charikar & Chatziafratis (2017), cf. Assadi et al. (2022)
Consider the notion of edge cost footprint as defined in Definition 12 we have
edge-cost? 21/3 ((u, v)) 3
edge-cost/ ((u, u)).
1= (U,))E
I=0 (,,U)E
The reason for us to work with the value 2t is that, as we will see later, we can charge the cost of 1 3--balanced min-cuts to the summation, which gives us way to control the cost obtained by the HC tree obtained by recursive approximate 1/3 1/3-balance 3-balanced min cut.
Another technical advantage of working with the edge cost footprint is that "decompose" the cost into unit terms, and the terms of summation does not have to be "synchronized" with the terms summing over. The technical claim is as follows.
28

---

Published as a conference paper at ICLR 2025
Claim G.3 (Charikar and Chatziafratis Charikar & Chatziafratis (2017). cf. AAsadi et al. (2022)) Let T be any HC tree of G. Furthermore, consider any function F(u,
,, v, t) in the summation
[8I
Σ
Σ
F(u,u,t).
(S1-8a
1= (u.))EE(H)
induced by nodes T level
Then, each u', o' and l' (and the corresponding term F appear most once in the summation.
Note that challenge for to bound the term
Σ
2 2-w(S (mmin V(H) 5min). [H]
(SL. Sc) induced by nodes
in Lemma F.3 is that the weights w(Smin V(H) \ Smin) and the term we are summing over (H (21,52) are very different from each other. With Claim G.2 and Claim G.3| we can proceed
by i). first bound each term of w V(H) \ Smin). H by function of edge-costy (u. 8) for some and (u, v) in the optimal HC tree T": and ii). handle the summation with Claim G.3 to upper-bound the term.
We now show the main lemma that allows us to 'charge' the cost of balanced cuts to the edge cost footprints of the optimal tree. Although this lemma inherently implied in Charikar & Chatziafratis (2017); Assadi et al. (022), we include the proof here for completeness.
Lemma G.4. Les G = (V, Fr, w) be a weighted undirected graph, and let T be the optimal HC tree of G. Furthermore, let H C G be any pertex-induced subgraph of G. and
* let H + (Smain V(H) \
gmin) be the split on H induced by --bllanced min-cut.
let +T (S1, be the split on H induced by any -balancedd cut.
Then, we have that
||| w(Smin V(H) Smin) 23.1811-
Σ
edge cost: 20112 ((u,
(E())
Σ
cose-cost?!!!! 2/1133 ((u, v)).
t= S2 +1 (U,))
Proof. The proof follows essentially from the argument in previous works Charikar Chatziafratis (2017); Assadi et al. (2022). Let Si, Sü. ...., St be the maximal clusters of size most $ [S] and with non-empty intersection with H. Observe that we can form new clusters A = Ujet, a Sj H and B Sj n H, such that
A J B contains entire vertices in clusters U,53. In other words, IA U TB = =k]] and
max[[A], B < 3
Therefore, write that
H mmm V(H) \ 5min)
< H w(A, B)
(by the definition of 1/3-balanced min-cut) edge-cost?!!! ((u, r))
< Σ
(LL))
(by the fact that every split edges has be level most & [H] edge-cost? 2| 1/3 ((u, v)). (a,0)
< 3 |11
Σ
(by the fact that H + (S1, S2) is a balanced cut)
29

---

Published as a conference paper at ICLR 2025
Finally, for the second inequality in the lemma statement, note that for any (u, and any t' there is edge-costy- ((u, v)) 2 edge-cost?- ((u, v)), which gives us the desired statement.
Finalizing the proof of Lemma F.3 Lemma F3 now follows from the combination of Lemmas G.] and G.4 and Claim G.2 and G.3. To claborate, we now now bound the cost as follows.
Σ
2 (Smmm V(H) \ (mmnn) |
H + (S,.5)) S2)
induced by modes T
Σ
edge-cost ( 21111/((( ((u, u))
(by Lemma G.4
H (81, S2)
t= Sal+1 (a,))E(())
induced by nodes
6
Σ
cose-cost ///0sttt//3( v))
(by Claim G.3 since the summations are disjoint)
1=0 (u,))EE
< 18
edge-costy ((u, v))
(by Claim G.2
t=0 [u
< 18 costa = 18 OPTo,
(by Lemma G.
as desired by the lemma statement.
Lemma F3
30

---

Published as a conference paper at ICLR 2025
H ADDITIONAL DETAILS ON EXPERIMENTS
All of our experiments are implemented on a Macbook Pro with M2 CPU. In this section, we provide missing details on the dataset, pre-processing parameters and more experimental results.
H. MORE DETAILS ON DATASETS
We first provide the basic statisties of the datasets used in the paper. The number of edges of SBM and HSBM are the average of all generated graphs.
Table 2: Datasets used for experiments
Synthetic
Real-world
Dataset
SBM
Hierarchical SBM
IRIS
WINE
BOSTON
Size
150
150
150
178
506
Edges
2614
4005
4851
11830
95566
# Clusters
5
3
5
The similarity graph of each real-world dataset is constructed by Gaussian kernel, according to the standard heuristic. The parameter is selected as 0.65 for WINE and BOSTON, and 5 for IRIS.
H.2 MORE RESULTS ON SYNTHETIC DATA
The synthetic graphs we use in Section have five clusters (k 5) with sizes of {20, 20, 30, 30, 50) for each cluster. Here we demonstrate more experiment results on SBM graphs with other values of k and sizes each cluster. give details together with the illustrations.
We start with & = 6 SBM graphs, but in two different scenarios: the graphs can have clusters of the same size of various sizes. We set the privacy parameters same as before. The intra probabiibbbilltyy is 0.7 (p 0.7) and inter- inter-probabll probability is 0.1 (q 0.1). Similarly as before, perturbation significantly on all choices of e. Further, the cost given by our algorithm approaches the cost in the non-private setting. The details are shown in Figure and Figure 6
algorithm outperforms input
Dasgupta's Cost Graphs with
Dasgupta's Graphs with k-6
300000
320000
Dur Algorithm Input Perturbation
Our Algorihmm
Inout Perturbittio
Non Private
Non Privata
Deggett's Cost
200000
260000
Desgietars
280000
240000
220000
200000
200000
0.00
0-5
2-0.3 Prisacy Paratteeer
Prisacy Parameter
Figure 5: Comparison of Dasgupta's 's cost on SBM graphs of size 180 and 6. Each cluster has the same size of 30.
Figure 6: Comparison of Dasgupta's cost on HSBM graphs of size 180 and k = 6. Clusters have different sizes: 10.20.30.30.40.50.
With the chosen parameters the SBM graphs are well-clustered. In the next set of results we weaken the cluster pattern by reducing p to half. Other settings follow as above.
and Figure 8 move to k 8 with weaker cluster patterns. Observation follows immediately that our algorithm still produces favorable results consistently. Up to this point, we have tested synthetic graphs and clustering pattern vary, these additional experiment results show that our algorithm can generate private hierarchical clustering with much lower cost comparing the input perturbation. Further, if
As shown in Figure 7
diversity of settings where the number of clusters, cluster sizes
31

---

Published as a conference paper at ICLR 2025
Dasgupta's Cost Graphs with
Dasgupta's Graphs k-8
200000
370030
Our Aigoithi
Our Algeritim
190000
Input Perturbation
Incut Pei ourtuaaation
Non Prwvte
Private
180000
350000
Dengh ette CoP
160000
390000
150000
320000
310000
120000
300000
0.00.0
0.
2.5
c#2
0.0000
c=
E.0.0.
2.6
6+2
Privay Parameter
Privary Parameter
Figure 7: Comparison of Dasgupta's cost on SBM graphs of size 160 and 8. Each cluster has the size of 20.
Figure 8: Comparison of Dasgupta's cost on HSBM graphs of size 200 and & = Clusters have different sizes: 10,10020020033333,,04,,0
the input graph has a well-clustered structure, our algorithm is even comparable to the non- non-private algorithm in terms Dasgupta's 's cost.
32


Reviews:
[{"review_id": "n0Z83ixTIl", "reviewer": "Reviewer_ibaF", "summary": "The paper proposes several results furthering hierarchical clustering with differential privacy. The notion of privacy is weighted differential privacy, where the graph topology is public, and the weights of the edges are private. First, an efficient algorithm obtaining a \\frac{n}{\\epsilon} \\log n approximation ratio for graphs in which the minimum edge weight is at least 1 is proposed. The authors show that in the worst case, the \\omega(n^2 / \\epsilon) additive error lower bound from previous work still holds for the weaker notion of weighted DP. They make the interesting observation that the lower bound carries over to DP balanced cut via a reduction. Finally, they run experiments showing that the proposed mechanism is indeed feasible.", "questions": "Can you develop a lower bound family of graphs on a fixed topology which all have edge weights above 1, and incur at least the stated multiplicative error?\n\nIs it possible to obtain a stand-alone utility theorem for the proposed algorithm, which interpolates between \\log n / \\epsilon multiplicative error and n^2 / \\epsilon additive error for graphs with edge weights at least 1 vs. arbitrary graphs? You might have to \"unpackage\" Proposition A.6 so that it can handle additive error.\n\nFor the experiments, what is the smallest value of epsilon for which the utility of the proposed algorithm becomes \"bad\"? What is the value of epsilon such that the utility approaches the optimal cost? Consider increasing the range of epsilons used in the plots.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed algorithm is simpler and much more efficient than that in prior work. The multiplicative error is not too high for the graphs with edge weight at least 1, which is also a nice result and improvement over prior work. The reduction to balanced cut is an interesting new result.", "weaknesses": "The lower bound in a way misses the spirit of the proposed algorithm: It shows that there are adversarial graphs (with edge weights possibly zero) which require additive \\Omega(n^2 / \\epsilon) noise, but the upper bound applies to graphs whose edge weights are all at least 1. As these types of graphs are central to obtaining the upper bound, it would be more interesting to see what the lower bound is for graphs which also satisfy this property.\n\nThe utility of the proposed algorithm for graphs whose edge weights are close to zero is currently undefined, meaning the algorithm is not robust for graphs which fall even a little outside the constraints. This can be reconciled somewhat by combining this algorithm with previous work, but then the efficiency improvements do not hold.\n\nThe experiments look interesting, though there is an unexplained phenomenon that the proposed algorithm barely shows any sensitivity to epsilon: it achieves nearly the same error on both the minimum \\epsilon = 0.1 and maximum \\epsilon = 2.0 tested. This is surprising, since typically epsilon dramatically affects the performance of any private algorithm, and typically as \\epsilon becomes large, the cost should approach the cost of the best tree. Neither of these things is happening in the current plots; I think they should be double-checked.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "m35m0QU6oH", "reviewer": "Reviewer_qT5t", "summary": "This paper studies the challenge of achieving differential privacy in hierarchical clustering, under a model that assumes edge weights as sensitive information. The authors successfully show there exists an algorithm in this setting that achieves $O(\\log^{1.5} n/\\epsilon)$\nmultiplicative approximation.", "questions": "Please see above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 4, "strengths": "1. Despite the complicated problem setting and technical components, this paper has a clear presentation.\n2. In addition to establishing an upper bound, the authors also derive a matching lower bound that aligns with previous work, which presents an additive error of $\\Omega(n^2/ \\epsilon)$ and  a new lower bound of $\\Omega(1/ \\log ^{2}n \\epsilon)$  for balanced sparsest cuts in the weight-level DP model. These findings offer valuable insights into the comparison between edge-level and weight-level differential privacy models.  The lower bound proofing technique is novel.", "weaknesses": "Currently, I do not see the reason why in the input graph G adding an extra additive weight of $ 10 \\log \\frac{n}{\\epsilon} $ would be necessary, can the authors give some comments on this?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "dmtgbWUSa0", "reviewer": "Reviewer_8Hdn", "summary": "This paper addresses the challenge of performing hierarchical clustering (HC) on a graph while ensuring differential privacy (DP). Traditional approaches to differentially private clustering on graphs, particularly under edge-level DP, have recently been shown to incur high errors, which limits their practicality. To improve upon this, the paper proposes an alternative approach using weight-level DP, where only the edge weights (not the topology) represent sensitive information.\n\nWhile weight-level DP is less commonly studied than edge-level DP, it is not entirely novel. Previous works have defined neighboring graphs under weight-level DP by assuming identical topologies but allowing edge weight differences up to an $\\ell_1$ norm of 1. In this study, the standard weight-DP definition is adapted by adding a unit-weight assumption, requiring all edges to have weights of at least 1. For clarity, this adapted model will be referred to as “weight-DP-bis”. This adjustment enables significantly more practical error bounds, which are leveraged in the main contributions.\n\nFirst, the paper introduces a polynomial-time algorithm that achieves an approximation of $O(\\log^{1.5} n / \\epsilon) $ for hierarchical clustering under the $\\epsilon$-weight-DP-bis model. The paper further justifies the unit-weight assumption in weight-DP-bis by demonstrating that without it, an HC algorithm that satisfies $\\epsilon$-weight-level DP must incur an additive error of at least $\\Omega(n^2 / \\epsilon)$.\n\nAs an additional contribution, new lower bounds are established for balanced sparsest cuts under weight-level DP, which may have implications for broader applications beyond HC. \n\nFinally, empirical results support the algorithm’s effectiveness on both synthetic and real datasets, showing performance close to non-private benchmarks and scalability across a range of graph sizes.", "questions": "Please comment an the above weaknesses (especially important ones).", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper addresses a significant and complex topic that holds potential benefits for the community. The work is well written, well organized and, based on my level of reading, presents a sound approach to the problem. The core concept is clearly presented, and the technical contributions do not look trivial to me. Overall, the presentation and flow of ideas make the paper engaging and accessible (with a small criticism that I provide below), providing a very nice reading experience.", "weaknesses": "I have a few points that could be regarded as potential areas for improvement or clarification in the paper. Please note that these comments are based on my understanding of the material, and they reflect my personal perspective. I do not claim to be a specialist specifically in hierarchical clustering (HC). It is possible that I have misunderstood some aspects, and I am certainly open to revisiting my viewpoint during the discussion phase if necessary.\n\n- **(Minor)**: First, while the paper is quite well written, it may benefit from being more accessible to a general audience. Specifically, it would be helpful to provide brief reminders of key graph-theoretical concepts earlier in the paper. Some concepts, such as sparsest cuts, are not introduced in the main body, while others, such as HC and Dasgupta’s cost, are defined only on page 5. Given that the introduction spans four pages, it may help readers unfamiliar with these concepts to have them presented earlier or concisely defined within the introduction itself to avoid missing key discussions in the first half of the paper. Additionally, the introduction could be shortened to accommodate these clarifications.\n\n- **(Important)**: Second, while I understand that the unit-weight assumption offers better error bounds from a technical standpoint, it may fundamentally modify the problem. Specifically, assuming the $\\ell_1$ norm of differences is less than 1 and simultaneously that each edge has a minimum weight of 1, means that two graphs are neighboring only if their weight functions differ on a single edge. As I see it, this implicitly combines aspects of both the $\\ell_1$ and $\\ell_0$ norms in the privacy definition. The paper may benefit from contextualizing this adapted definition with practical scenarios beyond the initial one presented in [1] (and paraphrased on line 77), as these may no longer directly apply. Additionally, there are existing variations in weight-level DP definitions that might be interesting to discuss in the paper, where the $\\ell_1$ norm is that replaced with the $\\ell_\\infty$ norm. Relevant references include [2,3,4,5].\n\n- **(Important)**: Third, it seems that the paper does not compare to a closely related problem: computing minimum spanning trees under weight-level DP. This problem has been studied under both $\\ell_1$ and $\\ell_\\infty$ norms in [1,2,3]. I believe that this line of work is relevant to this paper because, as far as I understand, computing a weighted minimum spanning tree can be closely related to the single linkage HC algorithm. Existing studies on this problem provide upper and lower bounds that may be highly relevant here, even if the metric used (e.g., not explicitly Dasgupta's cost) differs. For instance, [1,3] provide matching upper and lower bounds of $\\Theta(n^2 / \\epsilon)$ for the additive error in minimum spanning tree computation under weight-level DP with $\\ell_1$ norm, which seems related to Theorem 3 in this paper. It think it would be nice if the paper could discuss this connection and, if relevant, compare these results. Similarly [2] adapts the initial definition to use an $\\ell_\\infty$ norm and shows that, similar results hold in the $\\ell_\\infty$ model, but can be circumvented by forcing the $\\ell_\\infty$ norm to be smaller than $\\frac{1}{\\vert E \\vert}$ in the privacy definition. This scheme seems similar to the idea of modifying the neighborhood definition to obtain better errors, but as pointed out in [3], this can be considered as being an alchemical fix.\n\n- **(Medium)**: Finally, the experimental section could be strengthened by including more comparisons to existing methods or baselines. Currently, it appears that the only baseline comparison is with iterative sparsest cut after input perturbation. It might be beneficial to consider additional comparisons, such as those in Imola (2023), which compares against single and average linkage.\n\n- **(Minor)**: A brief stylistic note: while this is a personal preference, I would suggest avoiding exclamation points in scientific writing, as seen in lines 160 and 200. A more neutral tone may be more fitting for a formal context.\n\n\n\n[1] Shortest Paths and Distances with Differential Privacy: https://arxiv.org/abs/1511.04631\n\n[2] Minimum spanning tree release under differential privacy constraints: https://arxiv.org/abs/1801.06423\n\n[3] Near-Universally-Optimal Differentially Private Minimum Spanning Trees: https://arxiv.org/abs/2404.15035\n\n[4] Faster Private Minimum Spanning Trees: https://arxiv.org/abs/2408.06997\n\n[5] Graph-based clustering under differential privacy: https://arxiv.org/abs/1803.03831", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)