{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,29]],"date-time":"2026-08-29T05:18:32Z","timestamp":1787980712896,"version":"build-2784847793"},"reference-count":44,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2026,8,27]],"date-time":"2026-08-27T00:00:00Z","timestamp":1787788800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>We study hierarchical spectral graph clustering under edge differential privacy (DP) through the lens of iterative eigenvector estimation on adjacency matrices. We propose a differentially private recursive spectral framework, where each binary partition is obtained via a rank-one noisy power method applied to induced adjacency sub-matrices. At each iteration, carefully calibrated Gaussian noise is injected into the matrix\u2013vector multiplication, ensuring (\u03b5,\u03b4)-edge DP under cumulative privacy accounting across both power iterations and recursive hierarchy levels while preserving the essential convergence properties of the classical power method. We provide a non-asymptotic analysis of the resulting noisy iterations, characterizing the trade-off between privacy and accuracy via explicit bounds on the eigenvector estimation error. In particular, we quantify how the noise variance, number of iterations, eigengap, and hierarchy depth jointly influence the accuracy of each recursive split and the overall clustering performance. Empirical evaluations on synthetic and real-world networks validate the theoretical predictions and demonstrate that the proposed method achieves strong multi-scale clustering performance under meaningful privacy budgets.<\/jats:p>","DOI":"10.3390\/e28090963","type":"journal-article","created":{"date-parts":[[2026,8,27]],"date-time":"2026-08-27T16:47:13Z","timestamp":1787849233000},"page":"963","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Differentially Private Hierarchical Spectral Clustering"],"prefix":"10.3390","volume":"28","author":[{"given":"Mohamed Seif","family":"Mohamed","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering, Princeton University, Princeton, NJ 08544, USA"},{"name":"Department of Computer Science and Engineering, Oakland University, Rochester, MI 48309, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrea J.","family":"Goldsmith","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, Princeton University, Princeton, NJ 08544, USA"},{"name":"Department of Electrical and Computer Engineering, Stony Brook University, Stony Brook, NY 11794, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2026,8,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","article-title":"Community detection in graphs","volume":"486","author":"Fortunato","year":"2010","journal-title":"Phys. Rep."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1159\/000067642","article-title":"Modeling of protein interaction networks","volume":"1","author":"Flammini","year":"2003","journal-title":"Complexus"},{"key":"ref_3","unstructured":"Guo, Z., Zhang, Z., Zhu, S., Chi, Y., and Gong, Y. (2009, January 6\u20139). Knowledge discovery from citation networks. Proceedings of the 9th IEEE International Conference on Data Mining, Miami, FL, USA."},{"key":"ref_4","first-page":"6446","article-title":"Community detection and stochastic block models: Recent developments","volume":"18","author":"Abbe","year":"2017","journal-title":"J. Mach. Learn. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"054305","DOI":"10.1103\/PhysRevE.107.054305","article-title":"Hierarchical community structure in networks","volume":"107","author":"Schaub","year":"2023","journal-title":"Phys. Rev. E"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1080\/01621459.1963.10500845","article-title":"Hierarchical grouping to optimize an objective function","volume":"58","author":"Ward","year":"1963","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","article-title":"Least squares quantization in PCM","volume":"28","author":"Lloyd","year":"1982","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_8","unstructured":"Suzuki, T. (2022). HCFormer: Unified Image Segmentation with Hierarchical Clustering. arXiv."},{"key":"ref_9","unstructured":"Tamkin, A., McCain, M., Handa, K., Durmus, E., Lovitt, L., Rathi, A., Huang, S., Mountfield, A., Hong, J., and Ritchie, S. (2024). Clio: Privacy-preserving insights into real-world ai use. arXiv."},{"key":"ref_10","unstructured":"Liu, D., Cohen, E., Ghazi, B., Kairouz, P., Kamath, P., Knop, A., Kumar, R., Manurangsi, P., Sealfon, A., and Yu, D. (2025). URANIA: Differentially Private Insights into AI Use. arXiv."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Everitt, B.S., Landau, S., Leese, M., and Stahl, D. (2011). Cluster Analysis, Wiley.","DOI":"10.1002\/9780470977811"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1145\/276305.276312","article-title":"CURE: An efficient clustering algorithm for large databases","volume":"27","author":"Guha","year":"1998","journal-title":"ACM Sigmod Rec."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1561\/0400000042","article-title":"The algorithmic foundations of differential privacy","volume":"9","author":"Dwork","year":"2014","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1146","DOI":"10.14778\/3402707.3402749","article-title":"Private analysis of graph structure","volume":"4","author":"Karwa","year":"2011","journal-title":"Proc. Vldb Endow."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/2611523","article-title":"Private analysis of graph structure","volume":"39","author":"Karwa","year":"2014","journal-title":"ACM Trans. Database Syst. (TODS)"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"68134","DOI":"10.52202\/075280-2980","article-title":"Private estimation algorithms for stochastic block models and mixture models","volume":"36","author":"Chen","year":"2023","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1109\/JSAIT.2024.3396400","article-title":"Differentially private sketch-and-solve for community detection via semidefinite programming","volume":"5","author":"Seif","year":"2024","journal-title":"IEEE J. Sel. Areas Inf. Theory (JSAIT)"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"8312","DOI":"10.1109\/TIFS.2025.3592556","article-title":"Differentially Private Online Community Detection for Censored Block Models: Algorithms and Fundamental Limits","volume":"20","author":"Seif","year":"2025","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"5176","DOI":"10.1109\/TNSE.2025.3646341","article-title":"On the Price of Differential Privacy for Spectral Clustering Over Stochastic Block Models","volume":"13","author":"Koskela","year":"2025","journal-title":"IEEE Trans. Netw. Sci. Eng."},{"key":"ref_20","unstructured":"Suppakitpaisarn, V., and Mukherjee, S. (2025). Locally Differentially Private Graph Clustering via the Power Iteration Method. arXiv."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Roy Chowdhury, A., Imola, J., and Chaudhuri, K. (2025, January 25\u201329). Robust Locally Differentially Private Graph Analysis. Proceedings of the 20th ACM Asia Conference on Computer and Communications Security, Hanoi, Vietnam.","DOI":"10.1145\/3708821.3736199"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Wang, Y., Wu, X., and Wu, L. (2013). Differential privacy preserving spectral graph analysis. Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining, Gold Coast, Australia, 14\u201317 April 2013, Springer.","DOI":"10.1007\/978-3-642-37456-2_28"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"22617","DOI":"10.52202\/068431-1643","article-title":"Differentially private graph learning via sensitivity-bounded personalized pagerank","volume":"35","author":"Epasto","year":"2022","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Nguyen, H.H., Imine, A., and Rusinowitch, M. (2016, January 24). Detecting communities under differential privacy. Proceedings of the 2016 ACM Workshop on Privacy in the Electronic Society, Vienna, Austria.","DOI":"10.1145\/2994620.2994624"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Qin, Z., Yu, T., Yang, Y., Khalil, I., Xiao, X., and Ren, K. (November, January 30). Generating synthetic decentralized social graphs with local differential privacy. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS), Dallas, TX, USA.","DOI":"10.1145\/3133956.3134086"},{"key":"ref_26","unstructured":"Imola, J., Murakami, T., and Chaudhuri, K. (2021, January 11\u201313). Locally Differentially Private Analysis of Graph Statistics. Proceedings of the 30th USENIX Symposium on Security, Virtual."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Blocki, J., Blum, A., Datta, A., and Sheffet, O. (2013, January 7\u201310). Differentially Private Data Analysis of Social Networks via Restricted Sensitivity. Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, Berkeley, CA, USA. ITCS\u201913.","DOI":"10.1145\/2422436.2422449"},{"key":"ref_28","first-page":"10-29012","article-title":"Consistent spectral clustering of network block models under local differential privacy","volume":"12","author":"Hehir","year":"2022","journal-title":"J. Priv. Confidentiality"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Cohen-Addad, V., Epasto, A., Lattanzi, S., Mirrokni, V., Munoz Medina, A., Saulpic, D., Schwiegelshohn, C., and Vassilvitskii, S. (2022, January 14\u201318). Scalable differentially private clustering via hierarchically separated trees. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Washington, DC, USA.","DOI":"10.1145\/3534678.3539409"},{"key":"ref_30","unstructured":"Seif, M., Nguyen, D., Vullikanti, A., and Tandon, R. (2022, January 17\u201323). Differentially private community detection for stochastic block models. Proceedings of the 2022 International Conference on Machine Learning (ICML), Baltimore, MD, USA."},{"key":"ref_31","unstructured":"Imola, J., Epasto, A., Mahdian, M., Cohen-Addad, V., and Mirrokni, V. (2023, January 23\u201329). Differentially private hierarchical clustering with provable approximation guarantees. Proceedings of the International Conference on Machine Learning (ICML), Honolulu, HI, USA."},{"key":"ref_32","first-page":"849","article-title":"On spectral clustering: Analysis and an algorithm","volume":"14","author":"Ng","year":"2001","journal-title":"Adv. Neural Inf. Process. Syst. (NeurIPS)"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","article-title":"A Tutorial on Spectral Clustering","volume":"17","year":"2007","journal-title":"Stat. Comput."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"McSherry, F. (2001, January 14\u201317). Spectral partitioning of random graphs. Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS), Las Vegas, NV, USA.","DOI":"10.1109\/SFCS.2001.959929"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1214\/14-AOS1274","article-title":"Consistency of spectral clustering in stochastic block models","volume":"43","author":"Lei","year":"2015","journal-title":"Ann. Stat."},{"key":"ref_36","first-page":"3120","article-title":"Regularized spectral clustering under the degree-corrected stochastic blockmodel","volume":"26","author":"Qin","year":"2013","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1002\/rsa.20713","article-title":"Concentration and regularization of random graphs","volume":"51","author":"Le","year":"2017","journal-title":"Random Struct. Algorithms"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"1452","DOI":"10.1214\/19-AOS1854","article-title":"Entrywise eigenvector analysis of random matrices with low expected rank","volume":"48","author":"Abbe","year":"2020","journal-title":"Ann. Stat."},{"key":"ref_39","unstructured":"Zhu, Y., Dong, J., and Wang, Y.X. (2022, January 28\u201330). Optimal accounting of differential privacy via characteristic function. Proceedings of the 2022 International Conference on Artificial Intelligence and Statistics, PMLR, Virtual."},{"key":"ref_40","first-page":"245","article-title":"Privacy Loss Classes: The Central Limit Theorem in Differential Privacy","volume":"2","author":"Sommer","year":"2019","journal-title":"Proc. Priv. Enhancing Technol."},{"key":"ref_41","first-page":"11631","article-title":"Numerical composition of differential privacy","volume":"34","author":"Gopi","year":"2021","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_42","unstructured":"Balle, B., and Wang, Y.X. (2018, January 10\u201315). Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. Proceedings of the 2018 International Conference on Machine Learning (ICML), PMLR, Stockholm, Sweden."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"7821","DOI":"10.1073\/pnas.122653799","article-title":"Community structure in social and biological networks","volume":"99","author":"Girvan","year":"2002","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_44","unstructured":"Cai, X., Huang, J., Bian, Y., and Church, K. (2021, January 3\u20137). Isotropy in the contextual embedding space: Clusters and manifolds. Proceedings of the 2021 International Conference on Learning Representations (ICLR), Virtual."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/28\/9\/963\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,29]],"date-time":"2026-08-29T04:39:24Z","timestamp":1787978364000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/28\/9\/963"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8,27]]},"references-count":44,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2026,9]]}},"alternative-id":["e28090963"],"URL":"https:\/\/doi.org\/10.3390\/e28090963","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,8,27]]}}}