{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:58:27Z","timestamp":1781326707338,"version":"3.54.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP220103731"],"award-info":[{"award-number":["DP220103731"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,12,4]]},"abstract":"<jats:p>Efficiently counting bicliques in large bipartite graphs is a fundamental problem with applications in network analysis, bioinformatics, and social sciences. However, existing exact algorithms do not scale well to large graphs, and current approximation algorithms lack formal accuracy guarantees. In this paper, we present the first approximation algorithm for the (p,q)-biclique counting problem that offers formal accuracy guarantees. Our approach introduces a novel sampling framework, termed BC-Shadow, which refines the sample space using edge-oriented techniques to strategically balance computational costs across algorithmic stages. This refinement increases the density of bicliques in the sample space, reducing the number of samples required for accurate estimation. Our algorithm adaptively determines the number of successful samples that are needed to satisfy predefined error and failure probability, enabling real-time adjustment to graph properties. We further enhance sampling efficiency with a new sampling structure, named zstar, which establishes a one-to-one correspondence with (p,q)-bicliques, eliminating redundancies and improving accuracy. Comprehensive theoretical analyses confirm the algorithm's accuracy and running time guarantees, while extensive experiments on large real-world datasets demonstrate its scalability and effectiveness.<\/jats:p>","DOI":"10.1145\/3769791","type":"journal-article","created":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:32:13Z","timestamp":1764995533000},"page":"1-26","source":"Crossref","is-referenced-by-count":0,"title":["Estimating Biclique Counts with Accuracy Guarantees"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7838-6079","authenticated-orcid":false,"given":"Rashmika","family":"Gamage","sequence":"first","affiliation":[{"name":"The University of Sydney, Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6830-3900","authenticated-orcid":false,"given":"Lijun","family":"Chang","sequence":"additional","affiliation":[{"name":"The University of Sydney, Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2020\/492"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Anna Arpaci-Dusseau Zixiang Zhou and Xuhao Chen. 2024. Accurate and Fast Approximate Graph Pattern Mining at Scale. arXiv:2405.03488 [cs.PF]","DOI":"10.14778\/3705829.3705831"},{"key":"e_1_2_1_3_1","first-page":"163","volume-title":"Science","volume":"353","author":"Benson Austin R.","year":"2016","unstructured":"Austin R. Benson, David F. Gleich, and Jure Leskovec. 2016. Higher-order organization of complex networks. Science, Vol. 353, 6295 (2016), 163-166."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-8733(96)00301-2"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.48786\/edbt.2025.61"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3682032"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3459241"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529341"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492471"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186125"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2756836"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001814"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Shweta Jain and C. Seshadhri. 2016. A Fast and Provable Method for Estimating Clique Counts Using Turifmmodebackslashelsetextbackslashfi'an's Theorem. arXiv (Nov. 2016).","DOI":"10.1145\/3038912.3052636"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3336191.3371839"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 2020 World Wide Web Conference (WWW). 1966-1976","author":"Jain Shweta","year":"2020","unstructured":"Shweta Jain and Comandur Seshadhri. 2020b. Provably and Efficiently Approximating Near-cliques using the Tur\u00e1n Shadow: PEANUTS. In Proceedings of the 2020 World Wide Web Conference (WWW). 1966-1976."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741101"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2007.04.006"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407843"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397234"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00681-6"},{"key":"e_1_2_1_21_1","volume-title":"Patient Diet Recommendation System Using K Clique and Deep Learning Classifiers. In Conference Proceedings. 121-130","author":"Manoharan Samuel","year":"2020","unstructured":"Samuel Manoharan and Sathesh Ammaiappan. 2020. Patient Diet Recommendation System Using K Clique and Deep Learning Classifiers. In Conference Proceedings. 121-130."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783385"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2024.3441864"},{"key":"e_1_2_1_24_1","first-page":"3","volume-title":"Higher-order Network Representation Learning. Companion Proceedings of the WWW Conference","author":"Rossi Ryan","year":"2018","unstructured":"Ryan Rossi, Nesreen Ahmed, and Eunyee Koh. 2018. Higher-order Network Representation Learning. Companion Proceedings of the WWW Conference (2018), 3-4."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220097"},{"key":"e_1_2_1_26_1","first-page":"504","article-title":"Peeling Bipartite Networks for Dense Subgraph Discovery","author":"Sariyuce Ahmet Erdem","year":"2018","unstructured":"Ahmet Erdem Sariyuce and Ali Pinar. 2018. Peeling Bipartite Networks for Dense Subgraph Discovery. In WSDM. 504-512.","journal-title":"WSDM."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13673-018-0161-6"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639262"},{"key":"e_1_2_1_29_1","volume-title":"Discovering Hierarchy of Bipartite Graphs with Cohesive Subgraphs. ICDE","author":"Wang Kai","year":"2022","unstructured":"Kai Wang, Wenjie Zhang, Xuemin Lin, Ying Zhang, and Shunyang Li. 2022. Discovering Hierarchy of Bipartite Graphs with Cohesive Subgraphs. ICDE (2022), 2291-2305."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489497"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517838"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551854"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3709666"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588932"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3314643"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.97.052306"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3206351"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769791","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:45:09Z","timestamp":1781325909000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769791"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":37,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,4]]}},"alternative-id":["10.1145\/3769791"],"URL":"https:\/\/doi.org\/10.1145\/3769791","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]}}}