On the Price of Differential Privacy for Hierarchical Clustering

Authors: Chengyuan Deng, Jie Gao, Jalaj Upadhyay, Chen Wang, Samson Zhou
Primary area: alignment, fairness, safety, privacy, and societal considerations
Keywords: Hierarchical clustering, differential privacy, sparsest cut

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.

Decision: accept (poster)
Reviewer scores: 6, 6, 8

Reviews and discussion:
<thread>
creation date:
1730391790227

thread_type:
official_review

<thread_object>
creator: reviewer_8hdn

<content>
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.

While 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.

First, 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)$.

As 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. 

Finally, 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.

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.

- **(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.

- **(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].

- **(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.

- **(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.

- **(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.



[1] Shortest Paths and Distances with Differential Privacy: https://arxiv.org/abs/1511.04631

[2] Minimum spanning tree release under differential privacy constraints: https://arxiv.org/abs/1801.06423

[3] Near-Universally-Optimal Differentially Private Minimum Spanning Trees: https://arxiv.org/abs/2404.15035

[4] Faster Private Minimum Spanning Trees: https://arxiv.org/abs/2408.06997

[5] Graph-based clustering under differential privacy: https://arxiv.org/abs/1803.03831

questions:
Please comment an the above weaknesses (especially important ones).
</content>
</thread_object>

</thread>
<thread>
creation date:
1730692971191

thread_type:
official_review

<thread_object>
creator: reviewer_qt5t

<content>
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)$
multiplicative approximation.

strengths:
1. Despite the complicated problem setting and technical components, this paper has a clear presentation.
2. 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?

questions:
Please see above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730733138651

thread_type:
official_review

<thread_object>
creator: reviewer_ibaf

<content>
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.

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.

The 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.

The 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.

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?

Is 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.

For 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732173409499

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We thank the reviewers for their insightful questions and valuable feedback. We also appreciate the positive comments on the paper, including:

- The proposed algorithm is simpler and much more efficient than that in prior work. (Reviewer ibaF)
- The multiplicative error is not too high for the graphs with edge weights of at least 1, which is also a nice result and improvement over prior work. (Reviewer ibaF)
- The reduction to balanced cut is an interesting new result. (Reviewer ibaF)
- Despite the complicated problem setting and technical components, this paper has a clear presentation. (Reviewer qT5t)
- 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/\varepsilon)$ and a new lower bound of $\Omega(1/\log^2 n \, \varepsilon)$ for balanced sparsest cuts in the weight-level DP model. (Reviewer qT5t)
- These findings offer valuable insights into the comparison between edge-level and weight-level differential privacy models. (Reviewer qT5t)
- The lower bound proofing technique is novel. (Reviewer qT5t)
- The paper addresses a significant and complex topic that holds potential benefits for the community. (Reviewer 8Hdn)
- The work is well written, well organized and, based on my level of reading, presents a sound approach to the problem. (Reviewer 8Hdn)
- The core concept is clearly presented, and the technical contributions do not look trivial to me. (Reviewer 8Hdn)
- 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. (Reviewer 8Hdn)

We have uploaded an updated version of the manuscript, which incorporates the reviewers' feedback, with changes marked in **red**. Specifically, we have added:
- Additional experiments comparing to more baselines, in particular, linkage-based approaches.
- Informal intuition on central concepts such as HC, Dasgupta’s objective, and sparsest cut, prior to their formal definition in the subsequent text to make the paper more accessible to the general audience.
- Discussion on additional related works, such as minimum spanning trees under weight-level DP.
- An additional discussion about the performance of our algorithm on graphs with minimum weights less than $1$.

We believe these revisions have strengthened the overall paper and we look forward to further feedback. We provide specific detailed responses to individual reviewer comments below.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper considers Hierarchical clustering (with Dasgupta's objective) in the weight Differential Privacy framework. Here the underlying graph topology is known and the weights need to be protected (in the sense of DP). While the weight-privacy model has been studied before, it is something that could be justified more directly in the paper. The algorithm is simpler compared to prior work and the authors show why the unit-weight assumption is crucial, in that otherwise very strong lower bounds can be constructed. There are also some empirical results. There remain open questions about tightness of the results within the unit-weight DP setting, but these may well be difficult questions and suitable for future work.