Efficient and Effective Biclique Counting with Local Differential Privacy
Proceedings of the ACM on Management of Data · 02.04.2026 · 4 (1) · 1-24
DOI: 10.1145/3786642 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 07.04.2026. Verfasst von Yizhang He und 5 weiteren Autor:innen. Die Arbeit nennt 50 Literaturangaben.
Abstract (Originalsprache)
Counting ( p , q )-bicliques in bipartite graphs is essential for uncovering dense substructures and higher-order patterns. However, releasing biclique counts can reveal private connections of users. To address this, we study ( p , q )-biclique counting under edge local differential privacy, where each vertex protects its one-hop neighbor relationships from an untrusted data curator. The Naive algorithm applies randomized responses to the adjacency matrix and produces an overly dense graph where ( p , q )-biclique structures are disrupted, resulting in highly biased estimates. To produce unbiased estimates, we propose a one-round algorithm that enumerates all motifs with p upper and q lower vertices, which leverages motif transformation probabilities to correct for perturbation-induced bias. To improve data utility and reduce the impact of Laplace noise, we propose a novel Multi-round Common Neighbor (MRCN) algorithm. MRCN estimates the number of common neighbors for each p -tuple (or q -tuple) and applies moment-based correction to recover unbiased ( p , q )-biclique counts. Notably, MRCN avoids explicit enumeration of all ( p , q )-motifs, offering better scalability for general p and q . We further boost performance with variance-reduction techniques such as multi-center optimization and refined noisy graph construction, and enhance scalability through layer-based pruning and vertex sampling. Extensive experiments on real-world datasets confirm the effectiveness and efficiency of our approaches.
Zitieren
APA
He, Y., Zhang, W., Wang, K., Lin, X., Zhang, Y., & Ni, W. (2026). Efficient and Effective Biclique Counting with Local Differential Privacy. Proceedings of the ACM on Management of Data, 4(1), 1-24. https://doi.org/10.1145/3786642
Vancouver
He Y, Zhang W, Wang K, Lin X, Zhang Y, Ni W. Efficient and Effective Biclique Counting with Local Differential Privacy. Proceedings of the ACM on Management of Data. 2026;4(1):1-24. doi:10.1145/3786642
BibTeX
@article{He2026,
author = {He, Yizhang and Zhang, Wenjie and Wang, Kai and Lin, Xuemin and Zhang, Ying and Ni, Wei},
title = {Efficient and Effective Biclique Counting with Local Differential Privacy},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {1},
pages = {1--24},
doi = {10.1145/3786642}
}
EUVIMED