{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T19:07:12Z","timestamp":1779131232383,"version":"3.51.4"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"NTU-NAP Startup Grant","award":["024584-00001"],"award-info":[{"award-number":["024584-00001"]}]},{"name":"Singapore Ministry of Education Tier 1 Grant","award":["RG19\\\/25"],"award-info":[{"award-number":["RG19\\\/25"]}]},{"name":"Cyber Security Agency of Singapore under the National Cybersecurity R&D Programme and the CyberSG R&D Programme Office","award":["CRPO-GC3-NTU-001"],"award-info":[{"award-number":["CRPO-GC3-NTU-001"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,18]]},"abstract":"<jats:p>\n                    Graph pattern counting serves as a cornerstone of network analysis with extensive real-world applications. Its integration with local differential privacy (LDP) has gained growing attention for protecting sensitive graph information in decentralized settings. However, existing LDP frameworks are largely ad hoc, offering solutions only for specific patterns such as triangles and stars. A general mechanism for counting arbitrary graph patterns, even for the subclass of acyclic patterns, has remained an open problem. To fill this gap, we present the first general solution for counting arbitrary acyclic patterns under LDP. We identify and tackle two fundamental challenges: generalizing pattern construction from distributed data and eliminating node duplication during the construction. To address the first challenge, we propose an LDP-tailored recursive subpattern counting framework that incrementally builds patterns across multiple communication rounds. For the second challenge, we apply a random marking technique that restricts each node to a unique position in the pattern during computation. Our mechanism achieves strong utility guarantees: for any acyclic graph pattern with\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    edges, we achieve an additive error of \u00d5 (\u221a\n                    <jats:italic toggle=\"yes\">Nd<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">G<\/jats:italic>\n                    )\n                    <jats:sup>\n                      <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    <\/jats:sup>\n                    ), where\n                    <jats:italic toggle=\"yes\">N<\/jats:italic>\n                    is the number of nodes and\n                    <jats:italic toggle=\"yes\">d<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">G<\/jats:italic>\n                    ) is the maximum degree of the input graph\n                    <jats:italic toggle=\"yes\">G<\/jats:italic>\n                    . Experiments on real-world graph datasets across multiple types of acyclic patterns demonstrate that our mechanisms achieve up to 46-2600\u00d7 improvement in utility and 300-650\u00d7 reduction in communication cost compared to the baseline methods.\n                  <\/jats:p>","DOI":"10.1145\/3802006","type":"journal-article","created":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:19:16Z","timestamp":1779128356000},"page":"1-26","source":"Crossref","is-referenced-by-count":0,"title":["Acyclic Graph Pattern Counting under Local Differential Privacy"],"prefix":"10.1145","volume":"4","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":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-4756-5938","authenticated-orcid":false,"given":"Kuncan","family":"Wang","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433496"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_4_1","volume-title":"The 40th Conference on Uncertainty in Artificial Intelligence.","author":"Betzer Louis","year":"2024","unstructured":"Louis Betzer, Vorapong Suppakitpaisarn, and Quentin Hillebrand. 2024. Publishing number of walks and katz centrality under local differential privacy. In The 40th Conference on Uncertainty in Artificial Intelligence."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422449"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3133982"},{"key":"e_1_2_1_7_1","volume-title":"Private and Continual Release of Statistics. ACM Transactions on Information and System Security","author":"Hubert Chan T.-H.","year":"2011","unstructured":"T.-H. Hubert Chan, Elaine Shi, and Dawn Song. 2011. Private and Continual Release of Statistics. ACM Transactions on Information and System Security (2011)."},{"key":"e_1_2_1_8_1","article-title":"Des valeurs moyennes","volume":"12","author":"Chebyshev Pafnutii Lvovich","year":"1867","unstructured":"Pafnutii Lvovich Chebyshev. 1867. Des valeurs moyennes. J. Math. Pures Appl, Vol. 12, 2 ( 1867), 177-184.","journal-title":"J. Math. Pures Appl"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465304"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3197390"},{"key":"e_1_2_1_11_1","volume-title":"Theory of evolutionary computation: Recent developments in discrete optimization","author":"Doerr Benjamin","unstructured":"Benjamin Doerr. 2019. Probabilistic tools for the analysis of randomized optimization heuristics. In Theory of evolutionary computation: Recent developments in discrete optimization. Springer, 1-87."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654931"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517844"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3697831"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP46215.2023.10179466"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452813"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524143"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_1_19_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_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560567"},{"key":"e_1_2_1_21_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_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703427203"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0163-9"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382783"},{"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.1109\/ICDE60146.2024.00186"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725348"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3769808"},{"key":"e_1_2_1_29_1","unstructured":"Yihua Hu Kuncan Wang and Wei Dong. 2026. Acyclic Graph Pattern Counting under Local Differential Privacy [Full Version]. (2026). https:\/\/drive.google.com\/drive\/folders\/1L_4OA9tuXksSGel6iqcZxpzarLNc4-k8?usp=sharing"},{"key":"e_1_2_1_30_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_31_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. 2022a. 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_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560659"},{"key":"e_1_2_1_33_1","volume-title":"Subgraphs and network motifs in geometric networks. Physical Review E\u2014Statistical, Nonlinear, and Soft Matter Physics","author":"Itzkovitz Shalev","year":"2005","unstructured":"Shalev Itzkovitz and Uri Alon. 2005. Subgraphs and network motifs in geometric networks. Physical Review E\u2014Statistical, Nonlinear, and Soft Matter Physics, Vol. 71, 2 (2005), 026117."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3177733"},{"key":"e_1_2_1_35_1","volume-title":"Number of paths in a graph. arXiv preprint arXiv:2209.08840","author":"Joki\u0107 Ivan","year":"2022","unstructured":"Ivan Joki\u0107 and Piet Van Mieghem. 2022. Number of paths in a graph. arXiv preprint arXiv:2209.08840 (2022)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402749"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756090"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_26"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289026"},{"key":"e_1_2_1_40_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_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956972"},{"key":"e_1_2_1_42_1","first-page":"824","volume-title":"Science","volume":"298","author":"Milo Ron","year":"2002","unstructured":"Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. 2002. Network motifs: simple building blocks of complex networks. Science, Vol. 298, 5594 (2002), 824-827."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2009.22"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250803"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03607"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3319535.3354253"},{"key":"e_1_2_1_48_1","volume-title":"Counting Graphlets of Size  under Local Differential Privacy. arXiv preprint arXiv:2505.12954","author":"Suppakitpaisarn Vorapong","year":"2025","unstructured":"Vorapong Suppakitpaisarn, Donlapark Ponnoprat, Nicha Hirankarn, and Quentin Hillebrand. 2025. Counting Graphlets of Size under Local Differential Privacy. arXiv preprint arXiv:2505.12954 (2025)."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1965.10480775"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM51629.2021.00182"},{"key":"e_1_2_1_51_1","first-page":"82","article-title":"Algorithms for acyclic database schemes","volume":"81","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. 1981. Algorithms for acyclic database schemes. In VLDB, Vol. 81. 82-94.","journal-title":"VLDB"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3047124"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00204"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737785"},{"key":"e_1_2_1_55_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\/3802006","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:30:42Z","timestamp":1779129042000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3802006"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,18]]},"references-count":55,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5,18]]}},"alternative-id":["10.1145\/3802006"],"URL":"https:\/\/doi.org\/10.1145\/3802006","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,18]]}}}