Robust Privacy-Preserving Triangle Counting under Edge Local Differential Privacy
Proceedings of the ACM on Management of Data · 17.06.2025 · 3 (3) · 1-26
DOI: 10.1145/3725348 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.06.2025. Verfasst von Yizhang He und 5 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 51 Literaturangaben.
Abstract (Originalsprache)
Counting the number of triangles in a graph is a fundamental task and has been extensively studied recently. In real-world applications, continuously releasing the triangle count of a graph poses a significant privacy risk for users. To protect sensitive edge information from a central server, we study the problem of estimating the number of triangles under edge local differential privacy (edge LDP). Existing approaches adopt a multi-round computing scheme, allowing the vertices to perform local triangle counting using the noisy graph constructed in the previous round. However, these algorithms not only restrict the noisy graph that can be downloaded to each vertex, but also have coarse upper bounds for the scale of noise added to the estimates. In this paper, we propose a vertex-centric triangle counting algorithm under edge LDP, which improves data utility by leveraging a larger part of the noisy adjacency matrix. Our approach fully exploits the local graph structure to obtain refined estimates of per-vertex triangle counts. We also devise tight bounds for global sensitivities to not only comply with privacy requirements but also control the scale of added noise. Furthermore, we perform a rigorous analysis of the L2 loss of our unbiased estimators and design optimizations for allocating the privacy budget to minimize L2 loss based on the input graph. Extensive experiments on 12 datasets validate the effectiveness and efficiency of our proposed algorithms.
Zitieren
APA
He, Y., Wang, K., Zhang, W., Lin, X., Zhang, Y., & Ni, W. (2025). Robust Privacy-Preserving Triangle Counting under Edge Local Differential Privacy. Proceedings of the ACM on Management of Data, 3(3), 1-26. https://doi.org/10.1145/3725348
Vancouver
He Y, Wang K, Zhang W, Lin X, Zhang Y, Ni W. Robust Privacy-Preserving Triangle Counting under Edge Local Differential Privacy. Proceedings of the ACM on Management of Data. 2025;3(3):1-26. doi:10.1145/3725348
BibTeX
@article{He2025,
author = {He, Yizhang and Wang, Kai and Zhang, Wenjie and Lin, Xuemin and Zhang, Ying and Ni, Wei},
title = {Robust Privacy-Preserving Triangle Counting under Edge Local Differential Privacy},
journal = {Proceedings of the ACM on Management of Data},
year = {2025},
volume = {3},
number = {3},
pages = {1--26},
doi = {10.1145/3725348}
}
EUVIMED