{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T04:40:31Z","timestamp":1780634431001,"version":"3.54.1"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["316729\/2021-3"],"award-info":[{"award-number":["316729\/2021-3"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","award":["88881.189723\/2018-01"],"award-info":[{"award-number":["88881.189723\/2018-01"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,6,13]]},"abstract":"<jats:p>Many complex natural and technological systems are commonly modeled as count-weighted graphs, where nodes represent entities, edges model relationships between them, and edge weights define some counting statistics associated with each relationship. As graph data usually contain sensitive information about entities, preserving privacy when releasing this type of data becomes an important issue. In this context, differential privacy (DP) has become the de facto standard for data release under strong privacy guarantees. When dealing with DP for weighted graphs, most state-of-the-art works assume that the graph topology is known. However, in several real-world applications, the privacy of the graph topology also needs to be ensured. In this paper, we aim to bridge the gap between DP and count-weighted graph data release, considering both graph structure and edge weights as private information. We first adapt the weighted graph DP definition to take into account the privacy of the graph structure. We then develop two novel approaches to privately releasing count-weighted graphs under the notions of global and local DP. We also leverage the post-processing property of DP to improve the accuracy of the proposed techniques considering graph domain constraints. Experiments using real-world graph data demonstrate the superiority of our approaches in terms of utility over existing techniques, enabling subsequent computation of a variety of statistics on the released graph with high utility, in some cases comparable to the non-private results.<\/jats:p>","DOI":"10.1145\/3589299","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:26:45Z","timestamp":1687292805000},"page":"1-25","source":"Crossref","is-referenced-by-count":8,"title":["Global and Local Differentially Private Release of Count-Weighted Graphs"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0015-2261","authenticated-orcid":false,"given":"Felipe T.","family":"Brito","sequence":"first","affiliation":[{"name":"Universidade Federal do Cear\u00e1, Fortaleza, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6244-625X","authenticated-orcid":false,"given":"Victor A. E.","family":"Farias","sequence":"additional","affiliation":[{"name":"Universidade Federal do Cear\u00e1, Fortaleza, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-2069-8907","authenticated-orcid":false,"given":"Cheryl","family":"Flynn","sequence":"additional","affiliation":[{"name":"AT&amp;T Chief Data Office, Bedminster, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3529-7820","authenticated-orcid":false,"given":"Subhabrata","family":"Majumdar","sequence":"additional","affiliation":[{"name":"AI Risk and Vulnerability Alliance, Seattle, WA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8430-9421","authenticated-orcid":false,"given":"Javam C.","family":"Machado","sequence":"additional","affiliation":[{"name":"Universidade Federal do Cear\u00e1, Fortaleza, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7609-9217","authenticated-orcid":false,"given":"Divesh","family":"Srivastava","sequence":"additional","affiliation":[{"name":"AT&amp;T Chief Data Office, Bedminster, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422449"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0344-8"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2793862"},{"key":"e_1_2_2_4_1","volume-title":"ICML Workshop on Statistical Network Analysis. Springer, 1--13","author":"Clauset Aaron","year":"2006","unstructured":"Aaron Clauset, Cristopher Moore, and Mark EJ Newman. 2006. Structural inference of hierarchies in networks. In ICML Workshop on Statistical Network Analysis. Springer, 1--13."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274608"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2926745"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3269206.3271736"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.53"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.846400"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1314690.1314696"},{"key":"e_1_2_2_11_1","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Dwork Cynthia","unstructured":"Cynthia Dwork. 2006. Differential privacy. In International Colloquium on Automata, Languages, and Programming. Springer, 1--12."},{"key":"e_1_2_2_12_1","volume-title":"Theory of cryptography conference","author":"Dwork Cynthia","unstructured":"Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference. Springer, 265--284."},{"key":"e_1_2_2_13_1","volume-title":"Distances Release with Differential Privacy in Tree and Grid Graph. arXiv preprint arXiv:2204.12488","author":"Fan Chenglin","year":"2022","unstructured":"Chenglin Fan and Ping Li. 2022. Distances Release with Differential Privacy in Tree and Grid Graph. arXiv preprint arXiv:2204.12488 (2022)."},{"key":"e_1_2_2_14_1","volume-title":"Customer privacy. https:\/\/www.fcc.gov\/general\/customer-privacy. Online","author":"Federal Communications Commission","year":"2022","unstructured":"Federal Communications Commission. 2018. Customer privacy. https:\/\/www.fcc.gov\/general\/customer-privacy. Online; accessed 13 October 2022."},{"key":"e_1_2_2_15_1","volume-title":"Proceedings of the International AAAI Conference on Web and Social Media","volume":"10","author":"Ferrara Emilio","year":"2016","unstructured":"Emilio Ferrara, Onur Varol, Filippo Menczer, and Alessandro Flammini. 2016. Detection of promoted social media campaigns. In Proceedings of the International AAAI Conference on Web and Social Media, Vol. 10. 563--566."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSS.2018.2877045"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/09076828X"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-010-0002-8"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035940"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214088"},{"key":"e_1_2_2_21_1","doi-asserted-by":"crossref","unstructured":"W Keith Hastings. 1970. Monte Carlo sampling methods using Markov chains and their applications. (1970).","DOI":"10.2307\/2334940"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.11"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSM.2020.2982555"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-47436-2_15"},{"key":"e_1_2_2_25_1","volume-title":"30th USENIX Security Symposium (USENIX Security 21)","author":"Imola Jacob","year":"2021","unstructured":"Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. 2021. Locally differentially private analysis of graph statistics. In 30th USENIX Security Symposium (USENIX Security 21). 983--1000."},{"key":"e_1_2_2_26_1","volume-title":"Stochastic blockmodels and community structure in networks. Physical review E 83, 1","author":"Karrer Brian","year":"2011","unstructured":"Brian Karrer and Mark EJ Newman. 2011. Stochastic blockmodels and community structure in networks. Physical review E 83, 1 (2011), 016107."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402749"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_26"},{"key":"e_1_2_2_29_1","volume-title":"Proc. Ecol. inference conf","volume":"17","author":"Koutra Danai","year":"2011","unstructured":"Danai Koutra, Ankur Parikh, Aaditya Ramdas, and Jing Xiang. 2011. Algorithms for graph similarity and subgraph matching. In Proc. Ecol. inference conf, Vol. 17. Citeseer."},{"key":"e_1_2_2_30_1","volume-title":"Proceedings of the 2nd ACM international conference on High confidence networked systems. 49--56","author":"Ny Jerome Le","year":"2013","unstructured":"Jerome Le Ny and George J Pappas. 2013. Privacy-preserving release of aggregate dynamic models. In Proceedings of the 2nd ACM international conference on High confidence networked systems. 49--56."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1232722.1232727"},{"key":"e_1_2_2_32_1","volume-title":"Differential privacy for edge weights in social networks. Security and Communication Networks 2017","author":"Li Xiaoye","year":"2017","unstructured":"Xiaoye Li, Jing Yang, Zhenlong Sun, and Jianpei Zhang. 2017. Differential privacy for edge weights in social networks. Security and Communication Networks 2017 (2017)."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1151659.1159930"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.3390\/ijerph18094432"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0136497"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.66"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559850"},{"key":"e_1_2_2_38_1","volume-title":"Duff: A dataset-distance-based utility function family for the exponential mechanism. arXiv preprint arXiv:2010.04235","author":"Medina Andr\u00e9s Mu\u00f1oz","year":"2020","unstructured":"Andr\u00e9s Mu\u00f1oz Medina and Jenny Gillenwater. 2020. Duff: A dataset-distance-based utility function family for the exponential mechanism. arXiv preprint arXiv:2010.04235 (2020)."},{"key":"e_1_2_2_39_1","series-title":"SIAM review 45, 2","volume-title":"The structure and function of complex networks","author":"Newman Mark EJ","year":"2003","unstructured":"Mark EJ Newman. 2003. The structure and function of complex networks. SIAM review 45, 2 (2003), 167--256."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2808797.2809385"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.adhoc.2020.102303"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250803"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.6084\/m9.figshare.1164194"},{"key":"e_1_2_2_44_1","volume-title":"Graph-based clustering under differential privacy. arXiv preprint arXiv:1803.03831","author":"Pinot Rafael","year":"2018","unstructured":"Rafael Pinot, Anne Morvan, Florian Yger, C\u00e9dric Gouy-Pailler, and Jamal Atif. 2018. Graph-based clustering under differential privacy. arXiv preprint arXiv:1803.03831 (2018)."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91458-9_5"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134086"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2068816.2068825"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902291"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3319535.3354253"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/NaNA.2019.00067"},{"key":"e_1_2_2_51_1","volume-title":"Census Bureau Sets Key Parameters to Protect Privacy in 2020 Census Results. https:\/\/www.census.gov\/newsroom\/press-releases\/2021\/2020-census-key-parameters.html. Online","author":"United States Census Bureau. 2021.","year":"2023","unstructured":"United States Census Bureau. 2021. Census Bureau Sets Key Parameters to Protect Privacy in 2020 Census Results. https:\/\/www.census.gov\/newsroom\/press-releases\/2021\/2020-census-key-parameters.html. Online; accessed 10 January 2023."},{"key":"e_1_2_2_52_1","volume-title":"Early detection of promoted campaigns on social media. EPJ data science 6","author":"Varol Onur","year":"2017","unstructured":"Onur Varol, Emilio Ferrara, Filippo Menczer, and Alessandro Flammini. 2017. Early detection of promoted campaigns on social media. EPJ data science 6 (2017), 1--19."},{"key":"e_1_2_2_53_1","volume-title":"On Asymptotic Linear Convergence of Projected Gradient Descent for Constrained Least Squares. arXiv preprint arXiv:2112.11760","author":"Vu Trung","year":"2021","unstructured":"Trung Vu and Raviv Raich. 2021. On Asymptotic Linear Convergence of Projected Gradient Descent for Constrained Least Squares. arXiv preprint arXiv:2112.11760 (2021)."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11042-019-08092-0"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/2612167.2612168"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.2991062"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623642"},{"key":"e_1_2_2_58_1","volume-title":"Xiaofeng Meng, and Xiaokui Xiao.","author":"Ye Qingqing","year":"2020","unstructured":"Qingqing Ye, Haibo Hu, Man Ho Au, Xiaofeng Meng, and Xiaokui Xiao. 2020. LF-GDPR: A framework for estimating graph metrics with local differential privacy. IEEE Transactions on Knowledge and Data Engineering (2020)."},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00204"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737785"},{"key":"e_1_2_2_61_1","volume-title":"Bias and Variance of Post-processing in Differential Privacy. In Thirty-Fifth AAAI Conference on Artificial Intelligence. AAAI Press, 11177--11184","author":"Zhu Keyu","year":"2021","unstructured":"Keyu Zhu, Pascal Van Hentenryck, and Ferdinando Fioretto. 2021. Bias and Variance of Post-processing in Differential Privacy. In Thirty-Fifth AAAI Conference on Artificial Intelligence. AAAI Press, 11177--11184."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589299","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589299","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:13Z","timestamp":1750178773000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589299"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":61,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,13]]}},"alternative-id":["10.1145\/3589299"],"URL":"https:\/\/doi.org\/10.1145\/3589299","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}