{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:18:09Z","timestamp":1778807889377,"version":"3.51.4"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,9]]},"abstract":"<jats:p>\n            We study the problem of privately releasing an approximate minimum spanning tree (MST). Given a graph G = (\n            <jats:italic toggle=\"yes\">V<\/jats:italic>\n            ,\n            <jats:italic toggle=\"yes\">E<\/jats:italic>\n            ,\n            <jats:bold>W<\/jats:bold>\n            ) where\n            <jats:italic toggle=\"yes\">V<\/jats:italic>\n            is a set of\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            vertices,\n            <jats:italic toggle=\"yes\">E<\/jats:italic>\n            is a set of\n            <jats:italic toggle=\"yes\">m<\/jats:italic>\n            undirected edges, and\n            <jats:bold>W<\/jats:bold>\n            \u2208 \u211d\n            <jats:sup>|E|<\/jats:sup>\n            is an edge-weight vector, our goal is to publish an approximate MST under\n            <jats:italic toggle=\"yes\">edge-weight<\/jats:italic>\n            differential privacy, as introduced by Sealfon in PODS 2016, where\n            <jats:italic toggle=\"yes\">V<\/jats:italic>\n            and\n            <jats:italic toggle=\"yes\">E<\/jats:italic>\n            are considered public and the weight vector is private. Our neighboring relation is \ud835\udcc1\n            <jats:sub>\u221e<\/jats:sub>\n            -distance on weights: for a sensitivity parameter \u0394\n            <jats:sub>\u221e<\/jats:sub>\n            , graphs G = (\n            <jats:italic toggle=\"yes\">V<\/jats:italic>\n            ,\n            <jats:italic toggle=\"yes\">E<\/jats:italic>\n            ,\n            <jats:bold>W<\/jats:bold>\n            ) and G' = (\n            <jats:italic toggle=\"yes\">V<\/jats:italic>\n            ,\n            <jats:italic toggle=\"yes\">E<\/jats:italic>\n            ,\n            <jats:bold>W<\/jats:bold>\n            ') are neighboring if ||\n            <jats:bold>W<\/jats:bold>\n            -\n            <jats:bold>W<\/jats:bold>\n            '||\n            <jats:sub>\u221e<\/jats:sub>\n            \u2264 \u0394\n            <jats:sub>\u221e<\/jats:sub>\n            ). Existing private MST algorithms face a trade-off, sacrificing either computational efficiency or accuracy. We show that it is possible to get the best of both worlds: With a suitable random perturbation of the input that does\n            <jats:italic toggle=\"yes\">not<\/jats:italic>\n            suffice to make the weight vector private, the result of\n            <jats:italic toggle=\"yes\">any<\/jats:italic>\n            non-private MST algorithm will be private and achieves a state-of-the-art error guarantee. Furthermore, by establishing a connection to\n            <jats:italic toggle=\"yes\">Private Top-k Selection<\/jats:italic>\n            [Steinke and Ullman, FOCS '17], we give the first privacy-utility trade-off lower bound for MST under approximate differential privacy, demonstrating that the error magnitude, ~O(n\n            <jats:sup>3\/2<\/jats:sup>\n            ), is optimal up to logarithmic factors. That is, our approach matches the time complexity of any non-private MST algorithm and at the same time achieves optimal error. We complement our theoretical treatment with experiments that confirm the practicality of our approach.\n          <\/jats:p>","DOI":"10.1145\/3725240","type":"journal-article","created":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T15:20:31Z","timestamp":1749482431000},"page":"1-26","source":"Crossref","is-referenced-by-count":2,"title":["Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1516-9306","authenticated-orcid":false,"given":"Rasmus","family":"Pagh","sequence":"first","affiliation":[{"name":"BARC, University of Copenhagen, Copenhagen, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2805-9939","authenticated-orcid":false,"given":"Lukas","family":"Retschmeier","sequence":"additional","affiliation":[{"name":"BARC, University of Copenhagen, Copenhagen, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2853-5034","authenticated-orcid":false,"given":"Hao","family":"Wu","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3149-7799","authenticated-orcid":false,"given":"Hanwen","family":"Zhang","sequence":"additional","affiliation":[{"name":"BARC, University of Copenhagen, Copenhagen, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2025,6,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Information Theory","author":"Ash R.B.","unstructured":"R.B. Ash. 1990. Information Theory. Dover Publications. 90045415 https:\/\/books.google.dk\/books?id=nJ3UmGvdUCoC"},{"key":"e_1_2_1_2_1","volume-title":"Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017","author":"Bateni Mohammad Hossein","year":"2017","unstructured":"Mohammad Hossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Raimondas Kiveris, Silvio Lattanzi, and Vahab S. Mirrokni. 2017. Affinity Clustering: Hierarchical Clustering at Scale. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4--9, 2017, Long Beach, CA, USA, Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, (Eds.). 6864-6874. https:\/\/proceedings.neurips.cc\/paper\/2017\/hash\/2e1b24a664f5e9c18f407b2f9c73e821-Abstract.html"},{"key":"e_1_2_1_3_1","first-page":"850","article-title":"A Differentially Private Guide for Graph Analytics","author":"Brito Felipe T","year":"2024","unstructured":"Felipe T Brito, Andr\u00e9 LC Mendon\u00e7a, and Javam C Machado. 2024. A Differentially Private Guide for Graph Analytics. In EDBT. 850-853.","journal-title":"EDBT."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--662--53641--4_24"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355562"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1968.1054142"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/JCSS.1997.1534"},{"key":"e_1_2_1_8_1","volume-title":"Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alch\u00e9-Buc","author":"Durfee David","year":"2019","unstructured":"David Durfee and Ryan M Rogers. 2019. Practical Differentially Private Top-k Selection with Pay-what-you-get Composition. In Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alch\u00e9-Buc, E. Fox, and R. Garnett, (Eds.), Vol. 32. Curran Associates, Inc. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2019\/file\/b139e104214a08ae3f2ebcce149cdf6e-Paper.pdf"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_2_1_11_1","volume-title":"Matroids and the greedy algorithm. Mathematical programming","author":"Edmonds Jack","year":"1971","unstructured":"Jack Edmonds. 1971. Matroids and the greedy algorithm. Mathematical programming, Vol. 1 (1971), 127-136."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5486\/PMD.1959.6.3-4.12"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 7th Python in Science Conference, Ga\u00ebl Varoquaux, Travis Vaught, and Jarrod Millman, (Eds.). Pasadena, CA USA, 11 - 15","author":"Hagberg Aric A.","unstructured":"Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. 2008. Exploring Network Structure, Dynamics, and Function using NetworkX. In Proceedings of the 7th Python in Science Conference, Ga\u00ebl Varoquaux, Travis Vaught, and Jarrod Millman, (Eds.). Pasadena, CA USA, 11 - 15."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.11"},{"key":"e_1_2_1_16_1","volume-title":"Near-Universally-Optimal Differentially Private Minimum Spanning Trees. Symposium on the Foundations of Responsible Computing (FORC)","author":"Hlad\u00edk Richard","year":"2025","unstructured":"Richard Hlad\u00edk and Jakub Tetek. 2025. Near-Universally-Optimal Differentially Private Minimum Spanning Trees. Symposium on the Foundations of Responsible Computing (FORC), (2025). arxiv:2404.15035 [cs.CR]"},{"key":"e_1_2_1_17_1","volume-title":"O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. (Z dopisu panu O. Boruvkovi) [On a certain problem of minimization]. Pr\u00e1ce moravsk\u00e9 p\u0159irodov\u011bdeck\u00e9 spole\u010dnosti","author":"Jarn\u00edk Vojtech","year":"1930","unstructured":"Vojtech Jarn\u00edk. 1930. O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. (Z dopisu panu O. Boruvkovi) [On a certain problem of minimization]. Pr\u00e1ce moravsk\u00e9 p\u0159irodov\u011bdeck\u00e9 spole\u010dnosti, Vol. 6 (1930), 57-63. https:\/\/dml.cz\/handle\/10338.dmlcz\/500726'show=full"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.139"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/201019.201022"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_26"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.3233\/IDA-2009-0382"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3569085"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.29012\/jpc.778"},{"key":"e_1_2_1_25_1","volume-title":"Advances in Neural Information Processing Systems","author":"McKenna Ryan","year":"2020","unstructured":"Ryan McKenna and Daniel R Sheldon. 2020. Permute-and-Flip: A new mechanism for differentially private selection. In Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, (Eds.), Vol. 33. Curran Associates, Inc., 193-203. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2020\/file\/01e00f2f4bfcbb7505cb641066f2859b-Paper.pdf"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.66"},{"key":"e_1_2_1_27_1","unstructured":"Tamara T. Mueller Dmitrii Usynin Johannes C. Paetzold Daniel Rueckert and Georgios Kaissis. 2022. SoK: Differential Privacy on Graph-Structured Data. arxiv:2203.09205 [cs.CR]"},{"key":"e_1_2_1_28_1","unstructured":"Esbj\u00f6rn Ohlsson. 1990. Sequential poisson sampling from a business register and its application to the Swedish consumer price index. Statistiska centralbyr\u00e5n."},{"key":"e_1_2_1_29_1","unstructured":"Rasmus Pagh and Lukas Retschmeier. 2024. Faster Private Minimum Spanning Trees. arxiv:2408.06997 [cs.DS] https:\/\/arxiv.org\/abs\/2408.06997"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2412.10130"},{"key":"e_1_2_1_31_1","unstructured":"Rafael Pinot. 2018. Minimum spanning tree release under differential privacy constraints. arXiv e-prints (Master Thesis) (2018). arxiv:1801.06423 [cs.CR]"},{"key":"e_1_2_1_32_1","first-page":"329","volume-title":"Conference on Uncertainty in Artificial Intelligence (UAI 2018),. Conference on Uncertaintly in Artificial Intelligence (UAI","author":"Pinot Rafael","year":"2018","unstructured":"Rafael Pinot, Anne Morvan, Florian Yger, Cedric Gouy-Pailler, and Jamal Atif. 2018. Graph-based Clustering under Differential Privacy. In Conference on Uncertainty in Artificial Intelligence (UAI 2018),. Conference on Uncertaintly in Artificial Intelligence (UAI 2018), Monterey, California, United States, 329-338. https:\/\/hal.science\/hal-02170699"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538--7305.1957.tb01515.x"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18--24","volume":"8681","author":"Qiao Gang","year":"2021","unstructured":"Gang Qiao, Weijie J. Su, and Li Zhang. 2021. Oneshot Differentially Private Top-k Selection. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18--24 July 2021, Virtual Event, (Proceedings of Machine Learning Research, Vol. 139), Marina Meila and Tong Zhang, (Eds.). PMLR, 8672-8681."},{"key":"e_1_2_1_35_1","volume-title":"A First Course in Probability (10 ed.). Pearson","author":"Ross Sheldon","unstructured":"Sheldon Ross. 2018. A First Course in Probability (10 ed.). Pearson, Upper Saddle River, NJ."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378--3758(96)00185--1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902291"},{"key":"e_1_2_1_38_1","volume-title":"Tight Lower Bounds for Differentially Private Selection. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017","author":"Steinke Thomas","year":"2017","unstructured":"Thomas Steinke and Jonathan R. Ullman. 2017. Tight Lower Bounds for Differentially Private Selection. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15--17, 2017, Chris Umans, (Ed.). IEEE Computer Society, Berkley, USA, 552-563."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--319--57048--8_7"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2320500"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022--2496(77)90026--8"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725240","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:18:05Z","timestamp":1755904685000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725240"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,9]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,9]]}},"alternative-id":["10.1145\/3725240"],"URL":"https:\/\/doi.org\/10.1145\/3725240","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,9]]}}}