acceptodds
Under review as a conference paper at ICLR 2027

Differentially Private Hierarchical Clustering for Well-Clusterable Graphs

Abstract

We present *Noisy-Degree Hierarchy*, a pure edge-differentially private algorithm for hierarchical clustering on well-clusterable graphs. It constructs a full hierarchy from noisy vertex degrees, without recovering the clusters, in time. Under the spectral well-clusterability conditions of Manghiuc and Sun (2021), it achieves an approximation to Dasgupta's cost with high probability, provided that the minimum weighted degree is at least one and . Here is the number of clusters, and is the st smallest eigenvalue of the input graph's normalized Laplacian. The private algorithm builds on our simpler non-private *Degree-Ordered Hierarchy*, whose approximation improves the previous bound under the same conditions. With additional degree-regularity and conductance assumptions, the private approximation factor improves to . We also prove an lower bound on disjoint regular expanders that matches this dependence on for fixed, sufficiently small . Experiments on synthetic and real-world graphs demonstrate the private algorithm's utility and efficiency.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Differential privacy, Graph clustering, Hierarchical Clustering

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_tKtSOpenReview ↗
Rating
3(−1)
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper provides a locally differentially private algorithm for clustering well-clustered graphs. For the hierarchical clustering with k clusters, it gives an approximation ratio of O(k6/λk+12ϵ)O(k^6 / \lambda_{k+1}^2 \epsilon) when λk+1\lambda_{k + 1} is the (k+1)(k + 1)-st smallest eigenvalue and ϵ\epsilon is the privacy lost.

Critical strengths

S1: Hierarchical clustering for well-clustered graphs under local differential privacy is a very important problem.

S2: The result of this paper is quite strong. There are many works addressed clustering under local differential privacy, but I think that this works have much better results that previous works I know.

S3: The algorithm is also quite efficient with running time almost linear. It is quite interesting that the authors only use the noisy degree to obtain that good approximation ratio.

Critical weaknesses

W1: I wonder why the authors do not compare their algorithm with the result of applying a hierarchical clustering to randomized response results. I know that randomized response can be poor in theory, but might provide quite good results in graphs with moderate size. I may decrease my evaluation based on the answer to this weakness.

W2: I think the authors miss many citations on clustering under LDP. I wonder why they do not include these works in their papers.

  • Jonathan Hehir, Aleksandra Slavkovic, and Xiaoyue Niu. 2022. Consistent Spectral Clustering of Network Block Models under Local Differential Privacy. Journal of Privacy and Confidentiality 12, 2 (2022).
  • Nan Fu, Weiwei Ni, Sen Zhang, Lihe Hou, and Dongyue Zhang. 2023. GC-NLDP: A graph clustering algorithm with local differential privacy. Computers & Security 124 (2023), 102967.
  • Sayan Mukherjee and Vorapong Suppakitpaisarn. 2025. Local Differential Privacy-Preserving Spectral Clustering for General Graphs. Transactions on Machine Learning Research (2025).
  • Yexin Zhang, Zhongtian Ma, Qiaosheng Zhang, and Zhen Wang. 2026. Private Community Detection in the Weighted Stochastic Block Model. Neurocomputing 697 (2026), 134153.
Questions for authors

See weaknesses.

4 comments
AuthorsOpenReview ↗

Response to Reviewer tKtS

Thank you for your careful review and helpful comments.

W1. Randomized-response baseline. Thank you for suggesting this comparison. We have added Randomized Response + AverageLinkage, with results in Appendix G.2 and implementation details in Appendix G.3. The baseline independently flips each unordered adjacency bit with probability 1/(1+eϵ)1/(1+e^\epsilon) and applies the same AverageLinkage routine used in the main evaluation. Both methods use pure edge-DP at ϵ=1\epsilon=1, and we score both trees on the original graphs. On inputs with roughly 1000–15001000–1500 vertices, Noisy-Degree Hierarchy reduces the median paired Dasgupta cost by 41.041.0\\% on the nonuniform SBM, 35.535.5\\% on Email-Eu-core, and 54.554.5\\% on Political Blogs (Table 4(b)). At this privacy budget, randomized response turns about 2727\\% of nonedges into edges in expectation, which helps explain the gap on these sparse inputs.

W2. Related work on private clustering. We have added and discussed all four suggested references in §1.2. Hehir et al. (2022) study spectral community recovery for SBMs and degree-corrected SBMs under local edge privacy. Fu et al. (2023) study clustering from locally held star graphs under node-LDP. Mukherjee and Suppakitpaisarn (2025) analyze spectral clustering after randomized response on general graphs. We discuss Zhang et al. (2026) alongside work on approximate edge-DP, since they study exact community recovery in weighted SBMs under (ϵ,δ)(\epsilon,\delta)-edge DP. These works study flat clustering or community recovery. Our utility guarantee concerns the Dasgupta cost of a full hierarchy. To make the connection to local privacy explicit, Appendix F.2 gives a one-round local implementation in which each vertex sends one noisy degree. It provides pure ϵ\epsilon-edge DP for the complete message transcript and produces the same tree distribution as Algorithm 2, hence the same utility guarantees.

Thank you very much for your reply. Unfortunately, after checking the new experimental results, it turns out that the proposed algorithm does not significantly improve over the randomized response. Although the improvement is significant in four selected real graphs, the authors do not explain or discuss where the improvement comes from. So, we do not know the reasons. The new results are also not completed since the authors did not run the experiments across the most important parameter of ε\varepsilon. They just set ε\varepsilon to one, which can be the value that randomized response does not do very well.

By the above reason, I would like to decrease the score of this paper to 2.

AuthorsOpenReview ↗

Follow-up Response to Reviewer tKtS

Thank you for the follow-up. We have extended the experiments to six privacy budgets, ϵ∈0.25,0.5,1,2,4,8\epsilon\in\\{0.25,0.5,1,2,4,8\\}, updated Table 4(b), and expanded the explanation in Appendix G.3.

At ϵ∈0.25,0.5,1,2\epsilon\in\\{0.25,0.5,1,2\\}, Noisy-Degree Hierarchy achieves lower Dasgupta costs on all three datasets, with median paired reductions of 21.321.3\\%–54.554.5\\% relative to Randomized Response + AverageLinkage. These show a substantial utility improvement over the baseline across these privacy budgets, rather than only at ϵ=1\epsilon=1. At ϵ=4\epsilon=4, the baseline has slightly lower cost on Email alone; at ϵ=8\epsilon=8, it has lower cost on all three datasets.

This pattern can be understood through the randomized-response flip probability, p=1/(1+eϵ)p=1/(1+e^\epsilon). For ϵ≤1\epsilon\le1, this probability is at least approximately 26.926.9\\%, whereas at ϵ=8\epsilon=8, it is approximately 0.03350.0335\\%.

On sparse graphs, there are far more nonedges than edges, so the higher flip probabilities at smaller privacy budgets introduce many spurious edges. AverageLinkage then constructs its hierarchy from this perturbed graph, whereas our Noisy-Degree Hierarchy retains useful degree information. At large ϵ\epsilon, little noise is added, so the comparison is close to that between our non-private degree-based hierarchy and AverageLinkage. So Randomized Response + AverageLinkage overtakes our method at larger privacy budgets.

Overall, our advantage at smaller budgets, together with the smaller increase in cost as ϵ\epsilon decreases across the tested range, suggests that our algorithm incurs less privacy-induced utility loss than Randomized Response.

Thank you very much for the additional experiment. With the additional experiments I still find the paper to be borderline, since the authors did not add a discussion why their algorithms work only on three real-graph datasets.

Reviewer_xHsLOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies hierarchical clustering, and in particular Dasgupta's objective, in the presence of differential privacy under the additional assumption that the graph is "well-clusterable" in a particular spectral sense (as defined by Lemma 2.2). They prove an upper bound that is polynomial in the factors defining this clusterability and 1/ϵ1/\epsilon (the privacy parameter), and which in fact polynomially improves over previous non-private algorithms. Their algorithm is quite simple, and runs in basically linear time: they simply sort the nodes by degrees, and build the hierarchy / tree by adding each node in order with a new root. In other words, the hierarchy is just the node of highest degree, then the two nodes of highest degree, then the three nodes of highest degree, etc. They can make this private just by adding noise to the degrees and then bucketing. They have experiments using graphs from a stochastic block model, where they show that their algorithm is better than a previous DP algorithm that is not specialized to the well-clusterable case.

Overall, this is a reasonably strong result, but there are issues with the writing and with the interestingness of the result.

Critical strengths
  • The problem is interesting
  • The algorithm is simple, fast, and practical
Critical weaknesses

Writing: Some of the discussion of the DP model and results is incorrect, or at a minimum misleading. In particular, they emphasize a few times that they are using edge-DP, and they distinguish this from merely weight-DP (see the bottom of page 1). Throughout, they say that they are giving an edge-DP algorithm. But edge-DP means that one edge is added or removed, and so in particular is not used in settings where weights can make a huge difference (like clustering, cuts, or shortest paths). Their actual definition (in Section 2.2) is not edge-DP, it is weight-DP! It is precisely saying that the ℓ1\ell_1-difference in the weight vectors is bounded by one, which is weight-DP (see, e.g., Sealfon's famous paper on APSP under privacy). This is quite worrying to me, since it seems to indicate that the authors either do not understand DP or have not read the related literature.

As a more minor writing issue, the theorems are written in a very strange way. If you look at Theorem 1.2, it depends on k, but k has not been defined! It's hidden inside of Lemma 2.2, but that lemma is of the form "Let k be an integer, if some condition is satisfied, then other nice things happen". So in Theorem 1.2, what is k? The smallest value for which the condition of Lemma 2.2 holds? The largest? It's kind of clear that they would want it to be the smallest such k, but they don't say this anywhere.

The result: The quantitative results are reasonably impressive, in that the bounds seem reasonable. But when I think about this a little more, it seems a little odd. The non-private algorithm is extremely simple, and depends only on degrees: it does not look at the graph structure at all. The authors phrase this as a selling point (since it's very fast), but I find it somewhat weird. For example, think about what happens when the graph is extremely well-clustered, something like k disjoint complete graphs. Then by only looking at degrees this algorithm is not going to find clusters at all, so the fact that it performs well on Dasgupta's objective just means that anything would work well on this graph. And the hierarchical clustering tree it produces is always just a path (with one leaf hanging off of each node), which obviously will almost never correspond to any "true" hierarchical clustering.

So while I have no reason to doubt their results as stated, my interpretation of it is actually that the well-clusterability assumption is a weird match for hierarchical clustering, not that their algorithm is actually finding good clusters. In retrospect, this feels intuitive to me. There is a long list of highly important and influential research studying clustering for well-clusterable graphs, which is motivated by the idea that while of course it would be great to work on general graphs, you probably only want to do clustering on graphs where there actually is a reasonable clustering, so it makes sense to focus on those kinds of graphs. But note that this is a clear mismatch now: they are trying to solve hierarchical clustering, but their assumption is that the graph has a good clustering (not a hierarchical clustering). And if we just assume that there is a good clustering, then (like the disjoint complete graphs shows) there is not necessarily a good hierarchical clustering. One would instead like to assume that the graph is "well-hierarchically clusterable" (whatever that means), and use that to design algorithms which actually find something like this hierarchical clustering.

Inn other words, while the math seems correct to me, it feels like they're basically "abusing the model" to give a result that is mathematically true but doesn't actually have a ton of meaning. They found an assumption and objective which let them prove their theorems, but there seems to be a mismatch between them. I would sugget either changing the objective, or changing the assumption. As it is, I just can't imagine this being useful in practice since it never gives any kind of "true" hierarchy, and in theory it's interesting more as an exploration of how single-level clusterability interacts with hierarchical clustering than as an actually interesting algorithm.

Questions for authors
  • Why are you calling this edge-DP? Are there any other papers that call this edge-DP, when it so clearly matches the definition of weight-DP from Sealfon and other papers?
  • Why does it make sense to assume clusterability rather than hierarchical clusterability when thinking about hierarchical clustering?
5 comments
AuthorsOpenReview ↗

Response to Reviewer xHsL

Thank you for your careful review and helpful comments.

1. Privacy model. We agree that the term “edge-DP” alone can be ambiguous for weighted graphs. Our guarantee is pure DP under unit ℓ1\ell_1 adjacency on the weights of all unordered vertex pairs. The vertex set is public, and a zero weight denotes an absent edge. Thus adjacent inputs may have different edge sets. On unweighted graphs, adjacency is exactly single-edge insertion or deletion. On weighted graphs, inserting or deleting an edge of weight at most one is a single neighboring change. Deleting an edge of weight a>1a>1 is covered by group privacy at parameter ⌈a⌉ϵ\lceil a\rceil\epsilon.

Imola et al. (ICML 2023, §3.2) use the term edge differential privacy for this type of weighted adjacency in hierarchical clustering, and Eliáš et al. (SODA 2020, Definition 3.2) use the same ℓ1\ell_1 adjacency in their work on cut approximation. Sealfon (PODS 2016) also uses an ℓ1\ell_1 bound, with the graph topology fixed and public. We have clarified in §2.2 that the distinction concerns whether edge presence is public. This is also the distinction relevant to our comparison with the public-topology upper bound of Deng et al. (ICLR 2025).

2. The role of kk. The revised text before Theorem 1.2 clarifies that kk bounds the number of parts in the decomposition guaranteed by Lemma 2.2, under its stated conditions. The algorithm takes neither kk nor a partition as input. If several values qualify, one can use the smallest resulting bound by minimizing k6/λk+12k^6/\lambda_{k+1}^2 over those values.

3. Why assume single-level clusterability? In practice, the evidence for communities can be strongest at one scale, while an analyst still wants a summary at several scales. In a university web graph, pages and subsites within each university can form local communities. A hierarchy then lets us ask whether links between universities group them by city, state or province, country, or continent. Thelwall (2002, Journal of Documentation), for example, found that interlinking among UK university websites decreased with geographic distance. In an organizational communication graph, teams can form local communities, while coarser groupings can reveal which teams work together across departments. In health care, the Dartmouth Atlas groups local hospital service areas into larger referral regions based on where patients travel for specialized care. These examples illustrate why a hierarchy is useful even when a single partition is the most defensible assumption about the input. Agreement with geographic or organizational labels is a separate empirical question.

There is also a theoretical precedent. Dasgupta (STOC 2016, §3.3.1) showed that in an assortative planted-partition model with a common between-block probability, every minimizer of the expected cost contains each planted block as a subtree. The order in which those blocks are merged is unconstrained. The hierarchical stochastic block model of Cohen-Addad et al. (JACM 2019, §5) includes this case by assigning the same probability to every merge above the blocks. We follow the deterministic setting of Manghiuc and Sun (NeurIPS 2021) and Laenen et al. (ICML 2023). Expansion within the parts gives a lower bound on the cost of every hierarchy, which lets us analyze the tree constructed from noisy degrees under pure DP.

The disjoint-clique example illustrates a limitation of degree information. Degrees alone cannot identify the clique memberships, yet an optimum keeps each clique in its own subtree, and a uniformly relabeled tree on kk cliques of size ss has expected approximation ratio (ks+1)/(s+1)=Θ(k)(ks+1)/(s+1)=\Theta(k). Our assumptions also allow unequal cluster sizes and degree scales. Appendix E gives a two-cluster family on which our algorithm achieves an O(1/ϵ)O(1/\epsilon) expected approximation on every labeling, while any graph-independent hierarchy incurs an expected ratio of Ω(n)\Omega(\sqrt n) on some labeling.

Thanks for your response. I am going to keep my score as it is.

  • I still do not understand what you are saying about your privacy definition. You say "We have clarified in §2.2 that the distinction concerns whether edge presence is public". But with your weight-privacy definition, this doesn't make any sense -- the edge presence is public! In particular, since weights can be zero, the input graph can always be the complete graph. I suppose that this could affect your running time, since your running time bounds are a function of mm (the actual number of edges). But from a privacy point of view this is irrelevant -- the weights are what is private, not the topology.

  • I am not particularly concerned with the practical issues of whether assuming single-level clusterability is reasonable, as I am not a practitioner. I still think that there is a mismatch between the assumption and the problem, which is what lets your algorithm get good performance even when it is obviously doing the wrong thing. As I said, I think that this is in part an indictment of Dasgupta's objective, since it allows for obviously wrong hierarchical clusterings even when there is an obviously right clustering. I keep coming back to the feeling that you are "abusing the model" (as I said in my review) -- this algorithm seems to me like it is obviously not building the right hierarchical clusterings, since it is by construction not even trying to figure out a hierarchy (it just greedily adds nodes by degree). So there is something in either the objective or the input assumption that is allowing this kind of abuse. And while it's interesting to see that such a mismatch in assumption and objective can cause trivial algorithms to look good, it's not (in my opinion) an ICLR paper.

AuthorsOpenReview ↗

Follow-up Response to Reviewer xHsL

Thank you for the follow-up.

1. Privacy definition. We agree that our weighted model is equivalent to ℓ1\ell_1 weight privacy on a public complete graph with zero weights allowed. The public set is (V2)\binom V2, and the private weight vector determines its positive-weight support. By “edge presence” we meant membership in that support.

We can illustrate the definition with an example. Let G′G' have edge set EE, with an edge u,v\\{u,v\\} of weight 0<wG′(u,v)≤10<w_{G'}(u,v)\le1. Let GG be obtained by deleting this edge, leaving all other edges and weights unchanged. Its edge set is therefore E∖u,vE\setminus\\{\\{u,v\\}\\}. Writing wG(u,v)=0w_G(u,v)=0 denotes the absence of this edge; it does not make the actual edge set public. These two graphs are adjacent under our definition, so their output distributions must satisfy the DP bound. This is a natural weighted extension of standard edge DP, reducing exactly to single-edge addition or deletion on unweighted graphs.

From an algorithm-design perspective, the algorithm cannot treat the actual edge set as public. For example, Deng et al. (2025, §3) perturb the weights of existing edges while retaining the edge set, then construct a hierarchy from the perturbed graph. This is compatible with their public-topology model. Under our definition, however, releasing such a perturbed graph would reveal whether u,v\\{u,v\\} is present and violate DP. Thus, the distinction concerns the privacy guarantee, not merely the running time.

2. Structural assumptions and the objective. We agree that Dasgupta’s cost captures one aspect of hierarchy quality. A simple objective cannot be expected to capture every criterion one might care about, including agreement with a planted hierarchy or usefulness for a particular downstream task. Dasgupta’s cost penalizes separating highly similar vertices high in the tree. Its exact optima preserve each clique as a subtree on a union of disjoint cliques. A uniformly relabeled tree on kk cliques of size s≥2s\ge2 has expected approximation ratio (ks+1)/(s+1)=Θ(k)(ks+1)/(s+1)=\Theta(k). An O(k)O(k) guarantee can therefore permit trees that mix cliques, and a degree-only algorithm has no information about clique membership when all degrees are equal.

The approximation guarantee is substantive even with two clusters. On the weighted two-expander family in Appendix E, any graph-independent hierarchy has expected approximation ratio Ω(n)\Omega(\sqrt n) for some labeling. Our algorithm achieves an O(1/ϵ)O(1/\epsilon) expected approximation for every labeling. More generally, the connection between the global degree profile and a lower bound on the cost of every hierarchy improves the non-private approximation from O(k22/λk+110)O(k^{22}/\lambda_{k+1}^{10}) to O(k6/λk+12)O(k^6/\lambda_{k+1}^2) under the same spectral assumptions. Under pure DP, our O(k/ϵ)O(k/\epsilon) bound in the stated degree-regular regime matches the worst-case Ω(k)\Omega(k) lower bound in its dependence on kk for fixed sufficiently small ϵ\epsilon. That lower bound applies even to algorithms with access to the full graph. These results quantify what one level of cluster structure can buy for cost minimization under privacy. Recovery of a prescribed hierarchy requires a separate guarantee.

Reviewer_B4VLOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies hierarchical clustering under pure differential privacy on well-clusterable graphs. The proposed algorithm, Noisy-Degree Hierarchy first adds noise to vertex degrees for privacy then groups vertices into degree buckets. It then builds balanced trees within the buckets, and finally merges them in decreasing degree order. The non-private analysis improves upon the approximation factor of prior work from O(k22/λk+110)O(k^{22}/\lambda_{k+1}^{10}) to O(k6/λk+12)O(k^6/\lambda_{k+1}^2) under the same assumptions, whereas the private algorithm incurs an additional O(1/ϵ)O(1/\epsilon) (due to noisy degrees). The authors also show improvement to O(k/ϵ)O(k/\epsilon) under additional assumptions of degree ratios and inner conductance and an Ω(k)\Omega(k) lower bound. Experiments are provided that evaluate cost and runtime on synthetic and real datasets.

Critical strengths

The paper offers a useful simplification, improved bounds, and a fast private construction. The algorithm builds a hierarchy from degrees alone, without finding the hidden clusters. This allows the full privacy budget to be used for the degree release. The cluster structure is used only in the analysis, which involves three main steps. They use expansion to bound each cluster's internal degree profile in terms of its optimal cost. The expander decomposition relates global degrees to internal degrees, and then a merging inequality combines the cluster profiles at a loss of at most kk (an upper bound on the number of clusters in the decomposition). This results in improved approximation without privacy. For the private algorithm, the analysis accounts for noisy degrees by bounding the cost using the true degree profile and the total absolute noise.

Critical weaknesses

The non-private result builds on several known tools which is also mentioned in the work. The degree profile appears in Kapralov et al.(2025), the decomposition comes from Laenen et al.(2023), and the dependence on inner conductance follows from Manghiuc and Sun(2021). Hence I view the contributions here as a useful combination with a better analysis.

For the private version, it's not clear why the authors don't discuss directly sorting the noisy degrees without bucketing. This would involve simply privatizing the degrees, sorting the noisy values, and then joining vertices one at a time. I have not carefully followed through their proofs in Appendix A, but at a high level it seems like this should work and provide the same asymptotic bounds. This makes the benefit of bucketing unclear (except for possibly producing shallower trees), and the experiments do not explore this comparison. Also, the appendix describes using greedy modularity instead of the approximate sparsest cuts described by Imola et al.(2023), and it is unclear whether this is a fair replacement.

Questions for authors

These are basically what was highlighted in the weakness sections but more concretely -

  1. What benefit does bucketing provide over directly sorting noisy degrees and how sensitive are the results to β\beta?
  2. How does the greedy-modularity implementation relate to Imola et al.'s SparseCut baseline?
2 comments
AuthorsOpenReview ↗

Response to Reviewer B4VL

Thank you for your careful review and helpful comments.

1. Non-private contribution. We agree that the result builds on the degree profile of Kapralov et al. and the decomposition and conductance tools from prior work. The new step is to relate the degree profile of the whole graph to the optimal hierarchical clustering cost using expansion within the parts and a pointwise bound on how much of each vertex’s degree lies outside its part (Theorem 3.3). This yields an O(k6/λk+12)O(k^6/\lambda_{k+1}^2) approximation by sorting degrees, improving the previous O(k22/λk+110)O(k^{22}/\lambda_{k+1}^{10}) bound under the same spectral assumptions.

2. Direct sorting and the bucket base. Your intuition is correct. Proposition F.1 in the revision shows that directly sorting noisy degrees gives pure ϵ\epsilon-edge DP, the same O(m+nlog⁡n)O(m+n\log n) running time, and the same asymptotic approximation factors. The benefit of bucketing is a shallower tree. Direct sorting gives a caterpillar of height n−1n-1. With rr occupied buckets and largest bucket size smax⁡s_{\max}, the bucketed tree has height at most r−1+⌈log⁡2smax⁡⌉r-1+\lceil\log_2 s_{\max}\rceil.

Appendix G.4 now includes a paired comparison at ϵ=1\epsilon=1 on 2020 uniform and 2020 nonuniform SBM graphs, each with 10001000 vertices and five noise draws per graph. Both methods used the same noisy degrees within each pair. At β=2\beta=2, median tree heights were 1313 on the uniform SBM and 1515 on the nonuniform SBM, compared with 999999 for direct sorting. Median paired cost ratios (bucketing divided by direct sorting) were 1.0611.061 and 0.9490.949, respectively. The depth reduction was substantial in both settings, and the cost advantage depended on the setting.

Appendix G.4 separately varies β∈1.25,1.5,2,3,4\beta\in\\{1.25,1.5,2,3,4\\} using matched noisy degrees. Across the nonuniform SBM, Email-Eu-core, and Political Blogs, median costs for β∈1.25,1.5,2\beta\in\\{1.25,1.5,2\\} were within 1010\\% of the default β=2\beta=2. At β=4\beta=4, median costs were 1313\\% to 2323\\% higher across these inputs.

3. Imola et al.’s SparseCut baseline. Both the synthetic- and real-data drivers in Imola et al.’s public implementation use greedy modularity to split the sanitized graph recursively. We follow their experimental implementation, and checks against the upstream functions yielded materially similar results with our adaptations. Appendix D.1 now identifies the upstream code and clarifies that the approximation guarantee in Imola et al. relies on an approximate sparsest-cut oracle.

Reviewer_B4VLOpenReview ↗

Response to the rebuttal

I thank the authors for their reply. I wasn't aware the public implementation used greedy modularity, thanks for pointing it out, in which case I don't object to the comparisons. As a theory focused work, considering the results and the scope studied, I am not sure if they meet the bar for ICLR. But nevertheless, I maintain my positive evaluation of the work as they obtain improvements for a well motivated problem. I maintain my score.

Reviewer_xHvvOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work studies the problem of hierarchical clustering of vertices in a graph in the edge-DP model. The output of the work is an implicit clustering: instead of output describing which vertices belong to which clusters, it releases a full binary clustering tree T. The leaves are the vertices, and each internal node represents a group of vertices which are the leaves of its subtree rooted at itself. The proposed work tries to produce a tree with low Dasgupta cost. The main method first estimates noisy degrees of all vertices, grouping vertices on buckets of noisy degrees. From these, it constructs a balanced tree for each bucket and merges the trees by their degree ordering. The authors establish rigorous bounds on two regimes: spectral well-clusterability, where the smallest kk eigenvalues are small; and degree-regular clusters, where vertices of the same clusters have similar degrees and few inter-cluster edges.

Critical strengths
  • The private algorithm is based on only noisy degrees of vertices, and no other topological information
  • Rigorous bounds on several regimes of input graphs: especially the improvements on the well-clusterable graphs and the matching lower bound in the degree-regular regime.
Critical weaknesses
  • The objective is selected for the convenience of the proof, and is not a common objective for graph clustering/partitioning. And there is no implication that a good Dasgupta cost makes good graph clustering.
  • The SBM graph model has ground-truth clusters, and while the paper uses SBM for evaluation, there are no analyses on how they compare to the output, theoretically or empirically.
  • The theoretical and experimental settings strongly favor the analyses: degree regularity helps the degree-based algorithms and their theoretical bounds, and setting the intra-cluster edge probabilities in SBM are quite distinct makes the expected degrees of the clusters differ substantially.
Questions for authors

Please respond how you plan to address the weaknesses.

1 comment
AuthorsOpenReview ↗

Response to Reviewer xHvv

Thank you for your careful review and helpful comments.

1. Choice of objective. Dasgupta introduced this cost at STOC 2016 to give similarity-based hierarchical clustering an explicit objective for the entire tree. Single and average linkage specify how to choose each successive merge. A tree-level objective provides a common criterion for comparing their outputs and measuring the utility loss due to privacy. The objective has since inspired a substantial body of theoretical and empirical work. On the theoretical side, Cohen-Addad et al., in Hierarchical Clustering: Objective Functions and Algorithms (JACM 2019), showed that Dasgupta’s cost satisfies an admissibility criterion under which a natural ground-truth hierarchy is optimal.

Laenen et al. (ICML 2023) developed approximation algorithms for this objective on well-clustered graphs and benchmarked them on synthetic and real-world data. The cost has also been used to evaluate hierarchies on citation and political-blog networks (Zügner et al., ICLR 2022) and to infer cell-type hierarchies from single-cell RNA sequencing data (Gilad and Sharan, 2026). Our work builds on this literature by studying how well the same objective can be approximated under pure edge differential privacy.

2. Relation to the planted partition. Appendix F.3 of the revision gives a precise connection. In an assortative SBM with a common between-block probability, a binary tree minimizes the expected Dasgupta cost exactly when every planted block forms a subtree. This characterization concerns the population objective. Our approximation guarantee concerns the cost on the observed graph, and recovery of its planted labels is a separate question.

To assess recovery empirically, we ran a separate diagnostic on 2020 fresh graphs from each SBM setting, with five 200200-vertex blocks and five private runs per graph. We cut each tree into five groups by repeatedly splitting its largest remaining subtree. At ϵ=1\epsilon=1, the median adjusted Rand index for Noisy-Degree Hierarchy was 0.0260.026 on the nonuniform SBM and approximately zero on the uniform SBM with expected external degree 22. Non-private AverageLinkage reached 0.8390.839 on the latter. This limitation is consistent with the information available to the algorithm. For example, relabeling a union of equal-sized dd-regular expanders changes the planted partition while leaving the entire labeled degree vector unchanged.

3. Role of degree assumptions. The main spectral guarantee in Theorem 3.5 requires neither within-cluster degree regularity nor separation between the degree ranges of different clusters. Bounding the within-cluster degree ratio gives the sharper guarantee in Corollary 3.6. We agree that the original nonuniform SBM provides a useful degree signal. To test performance without that signal, Appendix G.2 now evaluates uniform SBMs in which all blocks have identical expected degrees. At ϵ=1\epsilon=1, the median paired cost ratios relative to Imola-DP were 1.0061.006, 1.0221.022, and 1.0371.037 for expected external degrees 22, 44, and 88, respectively (Table 4(a)). Thus the two methods have comparable cost on these uniform SBMs, and our method is faster at every graph size tested in Section 5.2. On Email-Eu-core and Political Blogs, Table 1 reports median cost reductions of 39.839.8\\% and 54.154.1\\% relative to Imola-DP.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Response to all reviewers

We thank all reviewers for their time and effort. We have submitted a revised version of the paper addressing the reviewers’ comments. Apart from minor changes in the main sections, we have extended Appendix E and added new Appendices F and G.

Dear reviewers,

If you believe the authors have addressed your questions, please respond to the rebuttal.

Best, AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.