EUVIMEDEUVIMED entdecken
Crossref

Efficient and Effective Biclique Counting with Local Differential Privacy

Yizhang He, Wenjie Zhang, Kai Wang, Xuemin Lin, Ying Zhang, Wei Ni

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →