{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:14:30Z","timestamp":1779174870904,"version":"3.51.4"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:p>Maximal bicliques are effective to reveal meaningful information hidden in bipartite graphs. Maximal biclique enumeration (MBE) is challenging since the number of the maximal bicliques grows exponentially w.r.t. the number of vertices in a bipartite graph in the worst case. However, a large bipartite graph is usually very sparse, which is against the worst case and may lead to fast MBE algorithms. The uncharted opportunity is taking advantage of the sparsity to substantially improve the MBE efficiency for large sparse bipartite graphs. We observe that for a large sparse bipartite graph, a vertex<jats:italic>u<\/jats:italic>may converge to a few vertices in the same vertex set as<jats:italic>u<\/jats:italic>via its neighbours, which reveals that the enumeration scope for a vertex could be very small. Based on this observation, we propose novel concepts: unilateral coreness for individual vertices, unilateral order for each vertex set and unilateral convergence (\u03b6) for a large sparse bipartite graph, \u03b6 could be a few thousand for a large sparse bipartite graph with hundreds of million edges. Using the unilateral order, every vertex with \u03c4 unilateral coreness only needs to check at most 2<jats:sup>\u03c4<\/jats:sup>combinations so that all maximal bicliques can be enumerated and \u03c4 is bounded by \u03b6, which leads to a novel MBE algorithm running in<jats:italic>O<\/jats:italic><jats:sup>*<\/jats:sup>(2<jats:sup>\u03b6<\/jats:sup>). We then propose a batch-pivots technique to eliminate all enumerations resulting in non-maximal bicliques, which guarantees that every maximal biclique is reported in<jats:italic>O<\/jats:italic>(\u03b6<jats:italic>e<\/jats:italic>)-delay, where<jats:italic>e<\/jats:italic>is the number of edges. We devise novel data structures that allow storing subgraphs at omissible space for further speeding up MBE. Extensive experiments are conducted on synthetic and real large datasets to justify that our proposed algorithm is faster and more scalable than the existing algorithms.<\/jats:p>","DOI":"10.14778\/3529337.3529341","type":"journal-article","created":{"date-parts":[[2022,6,22]],"date-time":"2022-06-22T22:23:05Z","timestamp":1655936585000},"page":"1559-1571","source":"Crossref","is-referenced-by-count":53,"title":["Efficient maximal biclique enumeration for large sparse bipartite graphs"],"prefix":"10.14778","volume":"15","author":[{"given":"Lu","family":"Chen","sequence":"first","affiliation":[{"name":"Swinburne University of Technology, Melbourne, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chengfei","family":"Liu","sequence":"additional","affiliation":[{"name":"Swinburne University of Technology, Melbourne, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rui","family":"Zhou","sequence":"additional","affiliation":[{"name":"Swinburne University of Technology, Melbourne, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiajie","family":"Xu","sequence":"additional","affiliation":[{"name":"Soochow University, Suzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianxin","family":"Li","sequence":"additional","affiliation":[{"name":"Deakin University, Melbourne, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,6,22]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"https:\/\/github.com\/ddervs\/MBEA Online","year":"2021","unstructured":"2017. https:\/\/github.com\/ddervs\/MBEA Online ; accessed 12 December 2021 . 2017. https:\/\/github.com\/ddervs\/MBEA Online; accessed 12 December 2021."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2020\/492"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(00)00083-9"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkg340"},{"key":"e_1_2_1_5_1","volume-title":"Cohesive subgraph computation over large sparse graphs: algorithms, data structures, and programming techniques","author":"Chang Lijun","unstructured":"Lijun Chang and Lu Qin . 2018. Cohesive subgraph computation over large sparse graphs: algorithms, data structures, and programming techniques . Springer . Lijun Chang and Lu Qin. 2018. Cohesive subgraph computation over large sparse graphs: algorithms, data structures, and programming techniques. Springer."},{"key":"e_1_2_1_6_1","volume-title":"Frontiers in Algorithmics","author":"Chen Hao","unstructured":"Hao Chen and Tian Liu . 2017. Maximum Edge Bicliques in Tree Convex Bipartite Graphs . In Frontiers in Algorithmics , Mingyu Xiao and Frances Rosamond (Eds.). Springer International Publishing , Cham , 47--55. Hao Chen and Tian Liu. 2017. Maximum Edge Bicliques in Tree Convex Bipartite Graphs. In Frontiers in Algorithmics, Mingyu Xiao and Frances Rosamond (Eds.). Springer International Publishing, Cham, 47--55."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00017"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3231751.3231755"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","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. ACM 248--260. 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. ACM 248--260.","DOI":"10.1145\/3448016.3459241"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403114"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.02.001"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Apurba Das and Srikanta Tirthapura. 2019. Shared-Memory Parallel Maximal Biclique Enumeration. In HiPC. 34--43. 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_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1199"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792228228"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342645"},{"key":"e_1_2_1_16_1","volume-title":"Computers and Intractability","author":"Garey Michael R","unstructured":"Michael R Garey and David S Johnson . 1990. Computers and Intractability ; A Guide to the Theory of NP-Completeness . Michael R Garey and David S Johnson. 1990. Computers and Intractability; A Guide to the Theory of NP-Completeness."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.10.010"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2020.04.034"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(99)00040-7"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"J\u00e9r\u00f4me Kunegis. 2013. KONECT - The Koblenz Network Collection. In WWW. 1343--1350. J\u00e9r\u00f4me Kunegis. 2013. KONECT - The Koblenz Network Collection. In WWW. 1343--1350.","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.78.016108"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl020"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190660"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00120"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2019.00147"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212622"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313522"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11823728.42"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397234"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49192-8.46"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/WI.2004.10154"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9486-x"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-39219-2.10"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974348.36"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.06.015"},{"key":"e_1_2_1_37_1","volume-title":"Fimi","volume":"126","author":"Uno Takeaki","year":"2004","unstructured":"Takeaki Uno , Masashi Kiyomi , and Hiroki Arimura . 2004 . LCM ver. 2: Efficient Mining Algorithms for Frequent\/Closed\/Maximal Itemsets . In Fimi , Vol. 126 . Takeaki Uno, Masashi Kiyomi, and Hiroki Arimura. 2004. LCM ver. 2: Efficient Mining Algorithms for Frequent\/Closed\/Maximal Itemsets. In Fimi, Vol. 126."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-13-S18-A10"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339497"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00063"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00015"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447702"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457407"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITB.2007.897575"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22321-1_37"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972726.27"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-15-110"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.93"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2018.03.010"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3529337.3529341","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,27]],"date-time":"2024-09-27T15:02:51Z","timestamp":1727449371000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3529337.3529341"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4]]},"references-count":49,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["10.14778\/3529337.3529341"],"URL":"https:\/\/doi.org\/10.14778\/3529337.3529341","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,4]]}}}