- 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 when is the -st smallest eigenvalue and 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
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 . They just set 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.
Follow-up Response to Reviewer tKtS
Thank you for the follow-up. We have extended the experiments to six privacy budgets, , updated Table 4(b), and expanded the explanation in Appendix G.3.
At , Noisy-Degree Hierarchy achieves lower Dasgupta costs on all three datasets, with median paired reductions of – relative to Randomized Response + AverageLinkage. These show a substantial utility improvement over the baseline across these privacy budgets, rather than only at . At , the baseline has slightly lower cost on Email alone; at , it has lower cost on all three datasets.
This pattern can be understood through the randomized-response flip probability, . For , this probability is at least approximately , whereas at , it is approximately .
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 , 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 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.
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ϵ) and applies the same AverageLinkage routine used in the main evaluation. Both methods use pure edge-DP at ϵ=1, and we score both trees on the original graphs. On inputs with roughly 1000–1500 vertices, Noisy-Degree Hierarchy reduces the median paired Dasgupta cost by 41.0 on the nonuniform SBM, 35.5 on Email-Eu-core, and 54.5 on Political Blogs (Table 4(b)). At this privacy budget, randomized response turns about 27 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 (ϵ,δ)-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 ϵ-edge DP for the complete message transcript and produces the same tree distribution as Algorithm 2, hence the same utility guarantees.