Crypto-Assisted Graph Degree Sequence Release under Local Differential Privacy
ACM Transactions on the Web · 31.05.2026 · 20 (2) · 1-23
DOI: 10.1145/3799795 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on the Web, online erschienen am 14.04.2026. Verfasst von Xiaojian Zhang und 4 weiteren Autor:innen. Die Arbeit nennt 30 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Natural Science Outstanding Youth Science Foundation Project of Henan Province, Basic Research Special Projects of Key Research Projects in Higher Education Institutes in Henan Province.
Abstract (Originalsprache)
Given a graph G defined in a domain \(\mathcal {G}\) , we investigate locally differentially private mechanisms to release a degree sequence on \(\mathcal {G}\) that accurately approximates the actual degree distribution. Existing solutions for this problem mostly use graph projection techniques based on edge deletion process, using a threshold parameter \(\theta\) to bound node degrees. However, this approach presents a fundamental trade-off in threshold parameter selection. While large \(\theta\) values introduce substantial noise in the released degree sequence, small \(\theta\) values result in more edges removed than necessary. Furthermore, \(\theta\) selection leads to an excessive communication cost. To remedy existing solutions’ deficiencies, we present CADR-LDP, an efficient framework incorporating encryption techniques and differentially private mechanisms to release the degree sequence. In CADR-LDP, we first use the crypto-assisted Optimal- \(\theta\) -Selection method to select the optimal parameter with a low communication cost. Then, we use the LPEA-LOW method to add some edges for each node with the edge addition process in local projection. LPEA-LOW prioritizes the projection with low-degree nodes, which can retain more edges for such nodes and reduce the projection error. Theoretical analysis shows that CADR-LDP satisfies \(\epsilon\) -node local differential privacy. The experimental results on eight graph datasets show that our solution outperforms existing methods.
Förderung
- National Natural Science Foundation of China
- Natural Science Outstanding Youth Science Foundation Project of Henan Province
- Basic Research Special Projects of Key Research Projects in Higher Education Institutes in Henan Province
- Humanities and Social Sciences Research Projects of the Ministry of Education
Zitieren
APA
Zhang, X., Wang, J., Chen, K., Zhao, P., & Bai, H. (2026). Crypto-Assisted Graph Degree Sequence Release under Local Differential Privacy. ACM Transactions on the Web, 20(2), 1-23. https://doi.org/10.1145/3799795
Vancouver
Zhang X, Wang J, Chen K, Zhao P, Bai H. Crypto-Assisted Graph Degree Sequence Release under Local Differential Privacy. ACM Transactions on the Web. 2026;20(2):1-23. doi:10.1145/3799795
BibTeX
@article{Zhang2026,
author = {Zhang, Xiaojian and Wang, Junqing and Chen, Kerui and Zhao, Peiyuan and Bai, Huiyuan},
title = {Crypto-Assisted Graph Degree Sequence Release under Local Differential Privacy},
journal = {ACM Transactions on the Web},
year = {2026},
volume = {20},
number = {2},
pages = {1--23},
doi = {10.1145/3799795}
}
EUVIMED