{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T05:11:08Z","timestamp":1775538668259,"version":"3.50.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["62394332, 62402044, U2241211, and 62072034"],"award-info":[{"award-number":["62394332, 62402044, U2241211, and 62072034"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"China National Postdoctoral Program for Innovative Talents","award":["BX20240467"],"award-info":[{"award-number":["BX20240467"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,12,4]]},"abstract":"<jats:p>\n                    Identifying the maximum edge biclique in bipartite graphs, a complete bipartite subgraph with the largest number of edges, plays a crucial role in uncovering densely-connected communities and has significant applications in domains such as recommendation systems and biological network analysis. However, this problem is NP-hard, and existing methods face inefficiencies both in practice and theory. In this paper, we propose two novel algorithms with distinct branching strategies and provable time guarantees for solving the maximum edge biclique search problem. The first is a refined pivot-based branching algorithm that systematically exploits vertex adjacency relationships to bound the search for the maximum edge biclique, achieving a time complexity of\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">m<\/jats:italic>\n                    1.348\n                    <jats:sup>\n                      <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    <\/jats:sup>\n                    ). The second is a cover-based algorithm that uncovers a novel duality between maximal bicliques and minimal vertex covers in bipartite graphs, attaining a complexity of\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">m<\/jats:italic>\n                    1.381\n                    <jats:sup>\n                      <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    <\/jats:sup>\n                    ). To the best of our knowledge, these two algorithms achieve the best-known worst-case time complexities for this problem. Notably, while the cover-based algorithm has a marginally higher theoretical complexity, it typically provides superior practical performance on dense graphs due to its inherent pruning efficiency. To further enhance performance, we introduce advanced pruning techniques, including polynomial-time solvable graph cases, neighbor and non-neighbor constraint-based upper bounds, vertex cover constraint-driven upper bounds, heuristic prioritization, and an improved progressive bounding approach. Additionally, we propose a hybrid framework that deploys the pivot-based approach for sparse graph regions and the cover-based approach for dense regions, balancing efficiency across varying graph structures. Extensive experiments on 12 real-world bipartite graphs demonstrate that our hybrid framework outperforms the state-of-the-art baseline by up to four orders of magnitude and achieves speedups of several times to orders of magnitude over the pivot-based approach on dense graphs.\n                  <\/jats:p>","DOI":"10.1145\/3769833","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":["Theoretically and Practically Efficient Maximum Biclique Search"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8569-6558","authenticated-orcid":false,"given":"Qiangqiang","family":"Dai","sequence":"first","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}]},{"ORCID":"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:\/\/orcid.org\/0000-0002-5401-6222","authenticated-orcid":false,"given":"Lianpeng","family":"Qiao","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-4519-6227","authenticated-orcid":false,"given":"Donghang","family":"Cui","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}]},{"ORCID":"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":[[2025,12,5]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"3558","article-title":"Pivot-based Maximal Biclique Enumeration","author":"Abidi Aman","year":"2020","unstructured":"Aman Abidi, Rui Zhou, Lu Chen, and Chengfei Liu. 2020. Pivot-based Maximal Biclique Enumeration. In IJCAI. 3558-3564.","journal-title":"IJCAI."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.09.019"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSI.2007.907875"},{"key":"e_1_2_1_4_1","first-page":"196","article-title":"Collusion Detection in Online Rating Systems","volume":"7808","author":"Allahbakhsh Mohammad","year":"2013","unstructured":"Mohammad Allahbakhsh, Aleksandar Ignjatovic, Boualem Benatallah, Seyed-Mehdi-Reza Beheshti, Elisa Bertino, and Norman Foo. 2013. Collusion Detection in Online Rating Systems. In APWeb, Vol. 7808. 196-207.","journal-title":"APWeb"},{"key":"e_1_2_1_5_1","first-page":"119","article-title":"CopyCatch: stopping group attacks by spotting lockstep behavior in social networks","author":"Beutel Alex","year":"2013","unstructured":"Alex Beutel, Wanhong Xu, Venkatesan Guruswami, Christopher Palow, and Christos Faloutsos. 2013. CopyCatch: stopping group attacks by spotting lockstep behavior in social networks. In WWW. 119-130.","journal-title":"WWW."},{"key":"e_1_2_1_6_1","volume-title":"Graph structure in the web. Computer networks","author":"Broder Andrei","year":"2000","unstructured":"Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, Andrew Tomkins, and Janet Wiener. 2000. Graph structure in the web. Computer networks, Vol. 33, 1-6 (2000), 309-320."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkg340"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2015.04.001"},{"key":"e_1_2_1_9_1","first-page":"248","article-title":"Efficient exact algorithms for maximum balanced biclique search in bipartite graphs","author":"Chen Lu","year":"2021","unstructured":"Lu Chen, Chengfei Liu, Rui Zhou, Jiajie Xu, and Jianxin Li. 2021. Efficient exact algorithms for maximum balanced biclique search in bipartite graphs. In SIGMOD. 248-260.","journal-title":"SIGMOD."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529341"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589283"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654938"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.02.001"},{"key":"e_1_2_1_14_1","first-page":"34","article-title":"Shared-Memory Parallel Maximal Biclique Enumeration","author":"Das Apurba","year":"2019","unstructured":"Apurba Das and Srikanta Tirthapura. 2019. Shared-Memory Parallel Maximal Biclique Enumeration. In HiPC. 34-43.","journal-title":"HiPC."},{"key":"e_1_2_1_15_1","volume-title":"A comparative analysis of biclustering algorithms for gene expression data. Briefings in bioinformatics","author":"Eren Kemal","year":"2013","unstructured":"Kemal Eren, Mehmet Deveci, Onur K\u00fc\u00e7\u00fcktun\u00e7, and \u00dcmit V \u00c7ataly\u00fcrek. 2013. A comparative analysis of biclustering algorithms for gene expression data. Briefings in bioinformatics, Vol. 14, 3 (2013), 279-292."},{"key":"e_1_2_1_16_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA."},{"key":"e_1_2_1_17_1","first-page":"231","article-title":"Flexible Fault Tolerant Subspace Clustering for Data with Missing Values","author":"G\u00fcnnemann Stephan","year":"2011","unstructured":"Stephan G\u00fcnnemann, Emmanuel M\u00fcller, Sebastian Raubach, and Thomas Seidl. 2011. Flexible Fault Tolerant Subspace Clustering for Data with Missing Values. In ICDM. 231-240.","journal-title":"ICDM."},{"key":"e_1_2_1_18_1","first-page":"28","volume-title":"ICFCA","volume":"2378","author":"Ignatov Dmitry I.","year":"2019","unstructured":"Dmitry I. Ignatov. 2019. Preliminary Results on Mixed Integer Programming for Searching Maximum Quasi-Bicliques and Large Dense Biclusters. In ICFCA, Vol. 2378. 28-32."},{"key":"e_1_2_1_19_1","volume-title":"Trawling the web for emerging cyber-communities. Computer networks","author":"Kumar Ravi","year":"1999","unstructured":"Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew Tomkins. 1999. Trawling the web for emerging cyber-communities. Computer networks, Vol. 31, 11-16 (1999), 1481-1493."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.78.016108"},{"key":"e_1_2_1_21_1","first-page":"1","article-title":"The DBLP Computer Science Bibliography: Evolution, Research Issues, Perspectives","volume":"2476","author":"Ley Michael","year":"2002","unstructured":"Michael Ley. 2002. The DBLP Computer Science Bibliography: Evolution, Research Issues, Perspectives. In SPIRE, Vol. 2476. 1-10.","journal-title":"SPIRE"},{"key":"e_1_2_1_22_1","first-page":"939","article-title":"Combining MaxSAT reasoning and incremental upper bound for the maximum clique problem","author":"Li Chu-Min","year":"2013","unstructured":"Chu-Min Li, Zhiwen Fang, and Ke Xu. 2013. Combining MaxSAT reasoning and incremental upper bound for the maximum clique problem. In ICTAI. 939-946.","journal-title":"ICTAI."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v24i1.7536"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl020"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190660"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2020.104922"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00606-9"},{"key":"e_1_2_1_28_1","first-page":"437","article-title":"Efficient Mining of Large Maximal Bicliques","volume":"4081","author":"Liu Guimei","year":"2006","unstructured":"Guimei Liu, Kelvin Sim, and Jinyan Li. 2006. Efficient Mining of Large Maximal Bicliques. In DaWaK, Vol. 4081. 437-448.","journal-title":"DaWaK"},{"key":"e_1_2_1_29_1","first-page":"255","volume-title":"Quasi-bicliques: Complexity and Binding Pairs. In COCOON","volume":"5092","author":"Liu Xiaowen","year":"2008","unstructured":"Xiaowen Liu, Jinyan Li, and Lusheng Wang. 2008. Quasi-bicliques: Complexity and Binding Pairs. In COCOON 2008, Vol. 5092. 255-264."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397234"},{"key":"e_1_2_1_31_1","volume-title":"ICALP (LIPIcs","volume":"14","author":"Manurangsi Pasin","year":"2017","unstructured":"Pasin Manurangsi. 2017. Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis. In ICALP (LIPIcs, Vol. 80). 79:1-79:14."},{"key":"e_1_2_1_32_1","first-page":"226","article-title":"An exact branch and bound algorithm with symmetry breaking for the maximum balanced induced biclique problem","author":"McCreesh Ciaran","year":"2014","unstructured":"Ciaran McCreesh and Patrick Prosser. 2014. An exact branch and bound algorithm with symmetry breaking for the maximum balanced induced biclique problem. In CPAIOR. 226-234.","journal-title":"CPAIOR."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00333-0"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557097"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl060"},{"key":"e_1_2_1_36_1","first-page":"315","article-title":"On finding the maximum edge biclique in a bipartite graph: a subspace clustering approach","author":"Shaham Eran","year":"2016","unstructured":"Eran Shaham, Honghai Yu, and Xiaoli Li. 2016. On finding the maximum edge biclique in a bipartite graph: a subspace clustering approach. In SIAM. 315-323.","journal-title":"SIAM."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1656479.1656483"},{"key":"e_1_2_1_38_1","first-page":"132","article-title":"Finding Maximum Edge Biclique in Bipartite Networks by Integer Programming","author":"S\u00f6zdinler Melih","year":"2018","unstructured":"Melih S\u00f6zdinler and Can C. \u00d6zturan. 2018. Finding Maximum Edge Biclique in Bipartite Networks by Integer Programming. In CSE. 132-137.","journal-title":"CSE."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12872"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-13-S18-A10"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2019.1970"},{"key":"e_1_2_1_42_1","first-page":"567","article-title":"Deep Structure Learning for Fraud Detection","author":"Wang Haibo","year":"2018","unstructured":"Haibo Wang, Chuan Zhou, Jia Wu, Weizhen Dang, Xingquan Zhu, and Jilong Wang. 2018. Deep Structure Learning for Fraud Detection. In ICDM. 567-576.","journal-title":"ICDM."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148170.1148257"},{"key":"e_1_2_1_44_1","first-page":"661","article-title":"Efficient Bitruss Decomposition for Large-scale Bipartite Graphs","author":"Wang Kai","year":"2020","unstructured":"Kai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang, and Ying Zhang. 2020. Efficient Bitruss Decomposition for Large-scale Bipartite Graphs. In ICDE. 661-672.","journal-title":"ICDE."},{"key":"e_1_2_1_45_1","first-page":"498","article-title":"Efficient Personalized Maximum Biclique Search","author":"Wang Kai","year":"2022","unstructured":"Kai Wang, Wenjie Zhang, Xuemin Lin, Lu Qin, and Alexander Zhou. 2022. Efficient Personalized Maximum Biclique Search. In ICDE. 498-511.","journal-title":"ICDE."},{"key":"e_1_2_1_46_1","first-page":"409","volume-title":"COCOON","volume":"6196","author":"Wang Lusheng","year":"2010","unstructured":"Lusheng Wang. 2010. Near Optimal Solutions for Maximum Quasi-bicliques. In COCOON, Vol. 6196. 409-418."},{"key":"e_1_2_1_47_1","volume-title":"Tung","author":"Wang Nan","year":"2008","unstructured":"Nan Wang, Srinivasan Parthasarathy, Kian-Lee Tan, and Anthony K. H. Tung. 2008. CSV: visualizing and mining cohesive subgraphs. In SIGMOD, Jason Tsong-Li Wang (Ed.). 445-458."},{"key":"e_1_2_1_48_1","first-page":"860","article-title":"Efficient Algorithms for Maximal k-Biplex Enumeration","author":"Yu Kaiqiang","year":"2022","unstructured":"Kaiqiang Yu, Cheng Long, Shengxin Liu, and Da Yan. 2022. Efficient Algorithms for Maximal k-Biplex Enumeration. In SIGMOD. 860-873.","journal-title":"SIGMOD."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517137"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-15-110"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448942"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2018.09.017"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2018.03.010"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-32049-6_14"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769833","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T04:29:33Z","timestamp":1775536173000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769833"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":54,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,4]]}},"alternative-id":["10.1145\/3769833"],"URL":"https:\/\/doi.org\/10.1145\/3769833","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]}}}