{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:21:40Z","timestamp":1768108900042,"version":"3.49.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSFC Grants","award":["U2241211, 62072034, U1809206"],"award-info":[{"award-number":["U2241211, 62072034, U1809206"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>\n            A k-biplex is an induced subgraph of a bipartite graph which requires every vertex on the one side disconnecting at most k vertices on the other side. Enumerating all maximal k-biplexes in a bipartite graph is a fundamental operator in bipartite graph analysis and finds applications in various domains, including community detection, online recommendation, and fraud detection in finance networks. The state-of-the-art solutions for maximal k-biplex enumeration suffer from efficiency issues as k increases (k \u2265 2), with the time complexity of O(m 2\n            <jats:sup>n<\/jats:sup>\n            ), where n (m) denotes the number of vertices (edges) in the bipartite graph. To address this issue, we propose two theoretically and practically efficient enumeration algorithms based on novel branching techniques. Specifically, we first devise a new branching rule as a fundamental component. Building upon this, we then develop a novel branch-and-bound enumeration algorithm to efficiently enumerate maximal k-biplexes. We prove that our algorithm achieves a worst-case time complexity of O(m\u03b1\n            <jats:sub>k<\/jats:sub>\n            <jats:sup>n<\/jats:sup>\n            ), where \u03b1\n            <jats:sub>k<\/jats:sub>\n            &lt; 2, thus significantly improving the time complexity compared to previous algorithms. To enhance the performance, we further propose an improved enumeration algorithm based on a novel pivot-based branching rule. Theoretical analysis reveals that our improved algorithm has a time complexity of O(m\u03b2\n            <jats:sub>k<\/jats:sub>\n            <jats:sup>n<\/jats:sup>\n            ), where \u03b2\n            <jats:sub>k<\/jats:sub>\n            is strictly less than \u03b1\n            <jats:sub>k<\/jats:sub>\n            . In addition, we also present several non-trivial optimization techniques, including graph reduction, upper-bounds based pruning, and ordering-based optimization, to further improve the efficiency of our algorithms. Finally, we conduct extensive experiments on 6 large real-world bipartite graphs to evaluate the efficiency and scalability of the proposed solutions. The results demonstrate that our improved algorithm achieves up to 5 orders of magnitude faster than the state-of-the-art solutions.\n          <\/jats:p>","DOI":"10.1145\/3654938","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-26","source":"Crossref","is-referenced-by-count":6,"title":["Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee"],"prefix":"10.1145","volume":"2","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"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5808-3131","authenticated-orcid":false,"given":"Meihao","family":"Liao","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5275-7983","authenticated-orcid":false,"given":"Yu-Xuan","family":"Qiu","sequence":"additional","affiliation":[{"name":"Shenzhen University, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Aman Abidi Rui Zhou Lu Chen and Chengfei Liu. 2020. Pivot-based Maximal Biclique Enumeration. In IJCAI. 3558--3564.","DOI":"10.24963\/ijcai.2020\/492"},{"key":"e_1_2_1_2_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_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00026-N"},{"key":"e_1_2_1_4_1","volume-title":"cs.DS\/0310049","author":"Batagelj Vladimir","year":"2003","unstructured":"Vladimir Batagelj and Matjaz Zaversnik. 2003. An O(m) Algorithm for Cores Decomposition of Networks. CoRR, Vol. cs.DS\/0310049 (2003)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Devora Berlowitz Sara Cohen and Benny Kimelfeld. 2015. Efficient Enumeration of Maximal k-Plexes. In SIGMOD. 431--444.","DOI":"10.1145\/2723372.2746478"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","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.","DOI":"10.1145\/2488388.2488400"},{"key":"e_1_2_1_7_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_8_1","doi-asserted-by":"crossref","unstructured":"Dongbo Bu Yi Zhao Lun Cai Hong Xue Xiaopeng Zhu Hongchao Lu Jingfen Zhang Shiwei Sun Lunjiang Ling Nan Zhang et al. 2003. Topological structure analysis of the protein--protein interaction network in budding yeast. Nucleic acids research Vol. 31 9 (2003) 2443--2450.","DOI":"10.1093\/nar\/gkg340"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2015.04.001"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529341"},{"key":"e_1_2_1_11_1","volume-title":"Branch and bound algorithms-principles and examples. Department of Computer Science","author":"Clausen Jens","unstructured":"Jens Clausen. 1999. Branch and bound algorithms-principles and examples. Department of Computer Science, University of Copenhagen (1999), 1--30."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.04.003"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Alessio Conte Donatella Firmani Caterina Mordente Maurizio Patrignani and Riccardo Torlone. 2017. Fast Enumeration of Large k-Plexes. In SIGKDD. 115--124.","DOI":"10.1145\/3097983.3098031"},{"key":"e_1_2_1_14_1","volume-title":"Daniele De Sensi, Roberto Grossi, Andrea Marino, and Luca Versari.","author":"Conte Alessio","year":"2018","unstructured":"Alessio Conte, Tiziano De Matteis, Daniele De Sensi, Roberto Grossi, Andrea Marino, and Luca Versari. 2018. D2K: Scalable Community Detection in Massive Networks via Small-Diameter k-Plexes. In KDD. 1272--1281."},{"key":"e_1_2_1_15_1","unstructured":"Qiangqiang Dai Rong-Hua Li Hongchao Qin Meihao Liao and Guoren Wang. 2022. Scaling Up Maximal k-plex Enumeration. In CIKM. 345--354."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589283"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.02.001"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Apurba Das and Srikanta Tirthapura. 2019. Shared-Memory Parallel Maximal Biclique Enumeration. In HiPC. 34--43.","DOI":"10.1109\/HiPC.2019.00016"},{"key":"e_1_2_1_19_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\u00fccc \u00fcktuncc, and \u00dcmit V cC ataly\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_20_1","volume-title":"Fomin and Dieter Kratsch","author":"Fedor","year":"2010","unstructured":"Fedor V. Fomin and Dieter Kratsch. 2010. Exact Exponential Algorithms. Springer."},{"key":"e_1_2_1_21_1","volume-title":"Sebastian Raubach, and Thomas Seidl.","author":"Stephan G\u00fc","year":"2011","unstructured":"Stephan G\u00fc nnemann, Emmanuel M\u00fc ller, Sebastian Raubach, and Thomas Seidl. 2011. Flexible Fault Tolerant Subspace Clustering for Data with Missing Values. In ICDM. 231--240."},{"key":"e_1_2_1_22_1","first-page":"28","article-title":"Preliminary Results on Mixed Integer Programming for Searching Maximum Quasi-Bicliques and Large Dense Biclusters","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.","journal-title":"ICFCA"},{"key":"e_1_2_1_23_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_24_1","volume-title":"Doig","author":"Land Ailsa H.","year":"2010","unstructured":"Ailsa H. Land and Alison G. Doig. 2010. An Automatic Method for Solving Discrete Programming Problems. In 50 Years of Integer Programming 1958--2008 - From the Early Years to the State-of-the-Art. 105--132."},{"key":"e_1_2_1_25_1","volume-title":"Biclique communities. Physical review E","author":"Lehmann Sune","year":"2008","unstructured":"Sune Lehmann, Martin Schwartz, and Lars Kai Hansen. 2008. Biclique communities. Physical review E, Vol. 78, 1 (2008), 016108."},{"key":"e_1_2_1_26_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_27_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl020"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190660"},{"key":"e_1_2_1_29_1","first-page":"3335","article-title":"I\/O-Efficient Algorithms for Degeneracy Computation on Massive Networks","volume":"34","author":"Li Rong-Hua","year":"2022","unstructured":"Rong-Hua Li, Qiushuo Song, Xiaokui Xiao, Lu Qin, Guoren Wang, Jeffrey Xu Yu, and Rui Mao. 2022. I\/O-Efficient Algorithms for Degeneracy Computation on Massive Networks. IEEE Trans. Knowl. Data Eng., Vol. 34, 7 (2022), 3335--3348.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1970-125-1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00606-9"},{"key":"e_1_2_1_32_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_33_1","first-page":"255","article-title":"Quasi-bicliques","volume":"5092","author":"Liu Xiaowen","year":"2008","unstructured":"Xiaowen Liu, Jinyan Li, and Lusheng Wang. 2008. Quasi-bicliques: Complexity and Binding Pairs. In COCOON, Vol. 5092. 255--264.","journal-title":"Complexity and Binding Pairs. In COCOON"},{"key":"e_1_2_1_34_1","unstructured":"Fragkiskos D. Malliaros Apostolos N. Papadopoulos and Michalis Vazirgiannis. 2016. Core Decomposition in Graphs: Concepts Algorithms and Applications. In EDBT. 720--721."},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Ardian Kristanto Poernomo and Vivekanand Gopalkrishnan. 2009. Towards efficient mining of proportional fault-tolerant frequent itemsets. In KDD. 697--706.","DOI":"10.1145\/1557019.1557097"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl060"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1978.9989883"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1656479.1656483"},{"key":"e_1_2_1_39_1","volume-title":"Exact biclustering algorithm for the analysis of large gene expression data sets. BMC bioinformatics","author":"Voggenreiter Oliver","year":"2012","unstructured":"Oliver Voggenreiter, Stefan Bleuler, and Wilhelm Gruissem. 2012. Exact biclustering algorithm for the analysis of large gene expression data sets. BMC bioinformatics, Vol. 13, Suppl 18 (2012), A10."},{"key":"e_1_2_1_40_1","volume-title":"Reinders","author":"Wang Jun","year":"2006","unstructured":"Jun Wang, Arjen P. de Vries, and Marcel J. T. Reinders. 2006. Unifying user-based and item-based collaborative filtering approaches by similarity fusion. In SIGIR. 501--508."},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","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.","DOI":"10.1109\/ICDE48307.2020.00063"},{"key":"e_1_2_1_42_1","first-page":"409","article-title":"Near Optimal Solutions for Maximum Quasi-bicliques","volume":"6196","author":"Wang Lusheng","year":"2010","unstructured":"Lusheng Wang. 2010. Near Optimal Solutions for Maximum Quasi-bicliques. In COCOON, Vol. 6196. 409--418.","journal-title":"COCOON"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2017.03.003"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Zhengren Wang Yi Zhou Mingyu Xiao and Bakhadyr Khoussainov. 2022. Listing Maximal k-Plexes in Large Real-World Graphs. In WWW. 1517--1527.","DOI":"10.1145\/3485447.3512198"},{"key":"e_1_2_1_45_1","volume-title":"PAKDD","author":"Wu Bin","unstructured":"Bin Wu and Xin Pei. 2007. A Parallel Algorithm for Enumerating All the Maximal k-Plexes. In PAKDD, Vol. 4819. Springer, 476--483."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210022"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588729"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Kaiqiang Yu Cheng Long Shengxin Liu and Da Yan. 2022. Efficient Algorithms for Maximal k-Biplex Enumeration. In SIGMOD. 860--873.","DOI":"10.1145\/3514221.3517847"},{"key":"e_1_2_1_49_1","first-page":"824","article-title":"On Efficient Large Maximal Biplex Discovery","volume":"35","author":"Yu Kaiqiang","year":"2023","unstructured":"Kaiqiang Yu, Cheng Long, Deepak P, and Tanmoy Chakraborty. 2023. On Efficient Large Maximal Biplex Discovery. IEEE Trans. Knowl. Data Eng., Vol. 35, 1 (2023), 824--829.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"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":"crossref","unstructured":"Yi Zhou Jingwei Xu Zhenyu Guo Mingyu Xiao and Yan Jin. 2020. Enumerating Maximal k-Plexes with Worst-Case Time Guarantee. In AAAI. 2442--2449.","DOI":"10.1609\/aaai.v34i03.5625"},{"key":"e_1_2_1_52_1","first-page":"218","article-title":"Bitruss Decomposition of Bipartite Graphs","volume":"9643","author":"Zou Zhaonian","year":"2016","unstructured":"Zhaonian Zou. 2016. Bitruss Decomposition of Bipartite Graphs. In DASFAA, Vol. 9643. 218--233.","journal-title":"DASFAA"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654938","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654938","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:37:10Z","timestamp":1755787030000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654938"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654938"],"URL":"https:\/\/doi.org\/10.1145\/3654938","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}