Efficient and Effective Biclique Counting with Local Differential Privacy
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.
No keywords indexed for this article. Browse by subject →
Cynthia Dwork, Aaron Roth
Yizhang He, KAI WANG, Wenjie Zhang et al.
- Published
- Apr 02, 2026
- Vol/Issue
- 4(1)
- Pages
- 1-24
You May Also Like
Reham Omar, Ishika Dhall · 2023
43 citations
Ziniu Wu, Parimarjan Negi · 2023
39 citations
Jianyang Gao, Cheng Long · 2024
39 citations
Liana Patel, Peter Kraft · 2024
37 citations
Jiayao Zhang, Qiheng Sun · 2023
34 citations