EUVIMEDEUVIMED entdecken
Crossref

Acyclic Graph Pattern Counting under Local Differential Privacy

Yihua Hu, Kuncan Wang, Wei Dong

Proceedings of the ACM on Management of Data · 18.05.2026 · 4 (3) · 1-26

DOI: 10.1145/3802006 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Yihua Hu und 2 weiteren Autor:innen. Die Arbeit nennt 55 Literaturangaben. Gefördert von: NTU-NAP Startup Grant, Singapore Ministry of Education Tier 1 Grant, Cyber Security Agency of Singapore under the National Cybersecurity R&D Programme and the CyberSG R&D Programme Office.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 k edges, we achieve an additive error of Õ (√ Nd ( G ) k ), where N is the number of nodes and d ( G ) is the maximum degree of the input graph G . Experiments on real-world graph datasets across multiple types of acyclic patterns demonstrate that our mechanisms achieve up to 46-2600× improvement in utility and 300-650× reduction in communication cost compared to the baseline methods.

Förderung

  • NTU-NAP Startup Grant
  • Singapore Ministry of Education Tier 1 Grant
  • Cyber Security Agency of Singapore under the National Cybersecurity R&D Programme and the CyberSG R&D Programme Office

Zitieren

APA

Hu, Y., Wang, K., & Dong, W. (2026). Acyclic Graph Pattern Counting under Local Differential Privacy. Proceedings of the ACM on Management of Data, 4(3), 1-26. https://doi.org/10.1145/3802006

Vancouver

Hu Y, Wang K, Dong W. Acyclic Graph Pattern Counting under Local Differential Privacy. Proceedings of the ACM on Management of Data. 2026;4(3):1-26. doi:10.1145/3802006

BibTeX
@article{Hu2026,
  author = {Hu, Yihua and Wang, Kuncan and Dong, Wei},
  title = {Acyclic Graph Pattern Counting under Local Differential Privacy},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {3},
  pages = {1--26},
  doi = {10.1145/3802006}
}
Kostenlos starten →