{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T10:07:10Z","timestamp":1775815630277,"version":"3.50.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T00:00:00Z","timestamp":1685059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"<jats:p>A (p,q)-biclique is a complete subgraph (X,Y) that |X|=p, |Y|=q. Counting (p,q)-bicliques in bipartite graphs is an important operator for many bipartite graph analysis applications. However, getting the count of (p,q)-bicliques for large p and q (e.g., p,q \u2265 10) is extremely difficult, because the number of (p,q)-bicliques increases exponentially with respect to p and q. The state-of-the-art algorithm for this problem is based on the (p,q)-biclique enumeration technique which is often costly due to the exponential blowup in the enumeration space of (p,q)-bicliques. To overcome this problem, we first propose a novel exact algorithm, called EPivoter, based on a newly-developed edge-pivoting technique. The striking feature of EPivoter is that it can count (p,q)-bicliques for all pairs of (p,q) using a combinatorial technique, instead of exhaustively enumerating all (p,q)-bicliques. Second, we propose a novel dynamic programming (DP) based h-zigzag sampling technique to provably approximate the count of the (p,q)-bicliques for all pairs of (p,q), where an h-zigzag is an ordered simple path in G with length 2h-1 (h = min{p,q}). We show that our DP-based sampling technique is very efficient. Third, to further improve the efficiency, we also propose a hybrid framework that integrates both the exact EPivoter algorithm and sampling-based algorithms. Extensive experiments on 7 real-world graphs show that our algorithms are several orders of magnitude faster than the state-of-the-art algorithm.<\/jats:p>","DOI":"10.1145\/3588932","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T17:42:05Z","timestamp":1685468525000},"page":"1-26","source":"Crossref","is-referenced-by-count":20,"title":["Efficient Biclique Counting in Large Bipartite Graphs"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0003-0982-341X","authenticated-orcid":false,"given":"Xiaowei","family":"Ye","sequence":"first","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}]},{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0001-8658-6599","authenticated-orcid":false,"given":"Rong-Hua","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}]},{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0002-8569-6558","authenticated-orcid":false,"given":"Qiangqiang","family":"Dai","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}]},{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0003-4364-0633","authenticated-orcid":false,"given":"Hongchao","family":"Qin","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}]},{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0002-0181-8379","authenticated-orcid":false,"given":"Guoren","family":"Wang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"crossref","unstructured":"Aman Abidi Rui Zhou Lu Chen and Chengfei Liu. 2020. Pivot-based Maximal Biclique Enumeration. In IJCAI.","DOI":"10.24963\/ijcai.2020\/492"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137651"},{"key":"e_1_2_2_3_1","doi-asserted-by":"crossref","unstructured":"Noga Alon Raphael Yuster and Uri Zwick. 1994. Color-coding: a new method for finding simple paths cycles and other small subgraphs within large graphs. In STOC.","DOI":"10.1145\/195058.195179"},{"key":"e_1_2_2_4_1","unstructured":"Anonymous authors. 2022. Efficient Biclique Counting in Large Bipartite Graphs. In Full version:. https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/anonymous.4open.science\/r\/biclique_counting"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186586"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342640"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529341"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_2_2_10_1","doi-asserted-by":"crossref","unstructured":"Maximilien Danisch Oana Balalau and Mauro Sozio. 2018. Listing k-cliques in Sparse Real-World Graphs. In WWW.","DOI":"10.1145\/3178876.3186125"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342645"},{"key":"e_1_2_2_12_1","doi-asserted-by":"crossref","unstructured":"Shweta Jain and C. Seshadhri. 2017. A Fast and Provable Method for Estimating Clique Counts Using Tur\u00e1 n's Theorem. In WWW.","DOI":"10.1145\/3038912.3052636"},{"key":"e_1_2_2_13_1","doi-asserted-by":"crossref","unstructured":"Shweta Jain and C. Seshadhri. 2020a. The Power of Pivoting for Exact Clique Counting. In WSDM.","DOI":"10.1145\/3336191.3371839"},{"key":"e_1_2_2_14_1","volume-title":"Shadow: PEANUTS. In WWW.","author":"Jain Shweta","year":"2020","unstructured":"Shweta Jain and C. Seshadhri. 2020b. Provably and Efficiently Approximating Near-cliques using the Tur\u00e1 n Shadow: PEANUTS. In WWW."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741101"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190660"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407843"},{"key":"e_1_2_2_18_1","volume-title":"Approximately Counting Butterflies in Large Bipartite Graph Streams","author":"Li Rundong","year":"2021","unstructured":"Rundong Li, Pinghui Wang, Peng Jia, Xiangliang Zhang, Junzhou Zhao, Jing Tao, Ye Yuan, and Xiaohong Guan. 2021. Approximately Counting Butterflies in Large Bipartite Graph Streams. IEEE Transactions on Knowledge and Data Engineering (2021), 1--1."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00606-9"},{"key":"e_1_2_2_20_1","volume-title":"Network Motifs: Simple Building Blocks of Complex Networks. Science","volume":"298","author":"Milo R.","year":"2010","unstructured":"R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D Chklovskii, and U. Alon. 2010. Network Motifs: Simple Building Blocks of Complex Networks. Science, Vol. 298, 5594 (2010), 763--764."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783385"},{"key":"e_1_2_2_22_1","unstructured":"Caixia Qin Mingxue Liao Yuanyuan Liang and Changwen Zheng. 2019. Efficient Algorithm for Maximal Biclique Enumeration on Bipartite Graphs. In ICNC-FSKD."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.2297929"},{"key":"e_1_2_2_24_1","volume-title":"Ahmet Erdem Sariy\u00fc ce, and Srikanta Tirthapura","author":"Sanei-Mehri Seyed-Vahid","year":"2018","unstructured":"Seyed-Vahid Sanei-Mehri, Ahmet Erdem Sariy\u00fc ce, and Srikanta Tirthapura. 2018. Butterfly Counting in Bipartite Networks. In KDD."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3495011"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401962"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.06.015"},{"key":"e_1_2_2_28_1","doi-asserted-by":"crossref","unstructured":"Charalampos E. Tsourakakis. 2015. The K-clique Densest Subgraph Problem. In WWW.","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_2_2_29_1","volume-title":"Rectangle Counting in Large Bipartite Graphs. In IEEE International Congress on Big Data.","author":"Wang Jia","year":"2014","unstructured":"Jia Wang, Ada Wai-Chee Fu, and James Cheng. 2014. Rectangle Counting in Large Bipartite Graphs. In IEEE International Congress on Big Data."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339497"},{"key":"e_1_2_2_31_1","volume-title":"Accelerated butterfly counting with vertex priority on bipartite graphs. The VLDB Journal","author":"Wang Kai","year":"2022","unstructured":"Kai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang, and Ying Zhang. 2022. Accelerated butterfly counting with vertex priority on bipartite graphs. The VLDB Journal (2022), 1--25."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3234567"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2756836"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489497"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447702"},{"key":"e_1_2_2_36_1","unstructured":"Xiaowei Ye Rong-Hua Li Qiangqiang Dai Hongzhi Chen and Guoren Wang. 2022. Lightning Fast and Space Efficient k-clique Counting. In WWW."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.97.052306"},{"key":"e_1_2_2_38_1","volume-title":"Jure Leskovec, and David F. Gleich.","author":"Yin Hao","year":"2017","unstructured":"Hao Yin, Austin R. Benson, Jure Leskovec, and David F. Gleich. 2017b. Local Higher-Order Graph Clustering. In KDD."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-15-110"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-15-110"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489502"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3588932","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/dl.acm.org\/doi\/pdf\/10.1145\/3588932","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:37Z","timestamp":1750178857000},"score":1,"resource":{"primary":{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3588932"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588932"],"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1145\/3588932","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}