Efficient and Effective Biclique Counting with Local Differential Privacy

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.