{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T16:06:25Z","timestamp":1786637185656,"version":"3.56.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"name":"NTU\u2013NAP Startup Grant","award":["24584-00001"],"award-info":[{"award-number":["24584-00001"]}]},{"DOI":"10.13039\/501100001459","name":"Singapore Ministry of Education","doi-asserted-by":"crossref","award":["RG19\/25"],"award-info":[{"award-number":["RG19\/25"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,12,4]]},"abstract":"<jats:p>Differential privacy (DP) has been widely adopted to protect sensitive information in graph analytics. While edge-DP, which protects privacy at the edge level, has been extensively studied, node-DP, offering stronger protection for entire nodes and their incident edges, remains largely underexplored due to its technical challenges. A natural way to bridge this gap is to develop a general framework for reducing node-DP graph analytical tasks to edge-DP ones, enabling the reuse of existing edge-DP mechanisms. A straightforward solution based on group privacy divides the privacy budget by a given degree upper bound, but this leads to poor utility when the bound is set conservatively large to accommodate worst-case inputs. To address this, we propose node-to-edge (N2E), a general framework that reduces any node-DP graph analytical task to an edge-DP one, with the error dependency on the graph's true maximum degree. N2E introduces two novel techniques: a distance-preserving clipping mechanism that bounds edge distance between neighboring graphs after clipping, and the first node-DP mechanism for maximum degree approximation, enabling tight, privacy-preserving clipping thresholds. By instantiating N2E with existing edge-DP mechanisms, we obtain the first node-DP solutions for tasks such as maximum degree estimation. For edge counting, our method theoretically matches the error of the state-of-the-art, which is provably optimal, and significantly outperforms existing approaches for degree distribution estimation. Experimental results demonstrate that our framework achieves up to a 2.5x reduction in error for edge counting and up to an 80x reduction for degree distribution estimation.<\/jats:p>","DOI":"10.1145\/3769808","type":"journal-article","created":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:32:13Z","timestamp":1764995533000},"page":"1-26","source":"Crossref","is-referenced-by-count":3,"title":["N2E: A General Framework to Reduce Node-Differential Privacy to Edge-Differential Privacy for Graph Analytics"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-2948-8340","authenticated-orcid":false,"given":"Yihua","family":"Hu","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-7864-610X","authenticated-orcid":false,"given":"Hao","family":"Ding","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0394-4125","authenticated-orcid":false,"given":"Wei","family":"Dong","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.80"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422449"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch184"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465304"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274608"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2926745"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-38906-1_23"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.94"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654931"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517844"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3697831"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589268"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452813"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524143"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588669"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536467"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_2_1_20_1","first-page":"52","volume-title":"50th International Colloquium on Automata, Languages, and Programming (ICALP","author":"Eden Talya","year":"2023","unstructured":"Talya Eden, Quanquan C Liu, Sofya Raskhodnikova, and Adam Smith. 2023. Triangle Counting with Local Edge Differential Privacy. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 52-1."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.52202\/068431-1297"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560567"},{"key":"e_1_2_1_23_1","volume-title":"International Conference on Artificial Intelligence and Statistics. PMLR, 11581-11597","author":"Farhadi Alireza","year":"2022","unstructured":"Alireza Farhadi, MohammadTaghi Hajiaghayi, and Elaine Shi. 2022. Differentially private densest subgraph. In International Conference on Artificial Intelligence and Statistics. PMLR, 11581-11597."},{"key":"e_1_2_1_24_1","volume-title":"Differentially Private Algorithms for Graphs Under Continual Observation. In 29th Annual European Symposium on Algorithms (ESA","author":"Fichtenberger Hendrik","year":"2021","unstructured":"Hendrik Fichtenberger, Monika Henzinger, and Wolfgang Ost. 2021. Differentially Private Algorithms for Graphs Under Continual Observation. In 29th Annual European Symposium on Algorithms (ESA 2021). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.11"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725348"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Yihua Hu Hao Ding and Wei Dong. 2025. N2E: A General Framework to Reduce Node-Differential Privacy to Edge-Differential Privacy for Graph Analytics [Full Version]. (2025). https:\/\/drive.google.com\/drive\/folders\/1T9SLrU9z406RdMaWKPg3KP6aWEJOo73B?usp=sharing","DOI":"10.1145\/3769808"},{"key":"e_1_2_1_28_1","unstructured":"Ziyue Huang Yuting Liang and Ke Yi. 2021. Instance-optimal Mean Estimation Under Differential Privacy. In NeurIPS."},{"key":"e_1_2_1_29_1","first-page":"983","volume-title":"Locally Differentially Private Analysis of Graph Statistics. In 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). USENIX Association, 983-1000."},{"key":"e_1_2_1_30_1","first-page":"537","volume-title":"31st USENIX Security Symposium (USENIX Security 22)","author":"Imola Jacob","year":"2022","unstructured":"Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. 2022. Communication-Efficient Triangle Counting under Local Differential Privacy. In 31st USENIX Security Symposium (USENIX Security 22). USENIX Association, Boston, MA, 537-554."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3177733"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402749"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_26"},{"key":"e_1_2_1_34_1","volume-title":"SNAP: Stanford network analysis project.","author":"Leskovec Jure","year":"2014","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP: Stanford network analysis project."},{"key":"e_1_2_1_35_1","volume-title":"PGB: Benchmarking Differentially Private Synthetic Graph Generation Algorithms. arXiv preprint arXiv:2408.02928","author":"Liu Shang","year":"2024","unstructured":"Shang Liu, Hao Du, Yang Cao, Bo Yan, Jinfei Liu, and Masatoshi Yoshikawa. 2024a. PGB: Benchmarking Differentially Private Synthetic Graph Generation Algorithms. arXiv preprint arXiv:2408.02928 (2024)."},{"key":"e_1_2_1_36_1","volume-title":"Unleash the Power of Ellipsis: Accuracy-enhanced Sparse Vector Technique with Exponential Noise. arXiv preprint arXiv:2407.20068","author":"Liu Yuhan","year":"2024","unstructured":"Yuhan Liu, Sheng Wang, Yixuan Liu, Feifei Li, and Hong Chen. 2024b. Unleash the Power of Ellipsis: Accuracy-enhanced Sparse Vector Technique with Exponential Noise. arXiv preprint arXiv:2407.20068 (2024)."},{"key":"e_1_2_1_37_1","first-page":"1987","article-title":"Ibm ilog cplex optimization studio","volume":"12","author":"User's Manual CPLEX","year":"1987","unstructured":"CPLEX User's Manual. 1987. Ibm ilog cplex optimization studio. Version, Vol. 12, 1987-2018 (1987), 1.","journal-title":"Version"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2009.22"},{"key":"e_1_2_1_39_1","volume-title":"International Conference on Machine Learning. PMLR, 8140-8151","author":"Nguyen Dung","year":"2021","unstructured":"Dung Nguyen and Anil Vullikanti. 2021. Differentially private densest subgraph detection. In International Conference on Machine Learning. PMLR, 8140-8151."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250803"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556576"},{"key":"e_1_2_1_42_1","first-page":"3223","volume-title":"32nd USENIX Security Symposium (USENIX Security 23)","author":"Sajadmanesh Sina","year":"2023","unstructured":"Sina Sajadmanesh, Ali Shahin Shamsabadi, Aur\u00e9lien Bellet, and Daniel Gatica-Perez. 2023. {GAP}: Differentially private graph neural networks with aggregation perturbation. In 32nd USENIX Security Symposium (USENIX Security 23). 3223-3240."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2068816.2068825"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902291"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM51629.2021.00182"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737785"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM50108.2020.00184"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973440.68"},{"key":"e_1_2_1_49_1","first-page":"4543","volume-title":"31st USENIX Security Symposium (USENIX Security 22)","author":"Zhang Zhikun","year":"2022","unstructured":"Zhikun Zhang, Min Chen, Michael Backes, Yun Shen, and Yang Zhang. 2022. Inference attacks against graph neural networks. In 31st USENIX Security Symposium (USENIX Security 22). 4543-4560."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769808","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:44:48Z","timestamp":1781325888000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769808"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":49,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,4]]}},"alternative-id":["10.1145\/3769808"],"URL":"https:\/\/doi.org\/10.1145\/3769808","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]}}}