{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:14:29Z","timestamp":1779174869555,"version":"3.51.4"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Key Research and Development Program of China","award":["2020AAA0108503"],"award-info":[{"award-number":["2020AAA0108503"]}]},{"name":"NSFC Grants","award":["U2241211 62072034 U1809206"],"award-info":[{"award-number":["U2241211 62072034 U1809206"]}]},{"name":"CCF-Huawei Populus Grove Fund"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,6,13]]},"abstract":"<jats:p>Finding cohesive subgraphs from a bipartite graph is a fundamental operator in bipartite graph analysis. In this paper, we focus on the problem of mining cohesive subgraphs from a bipartite graph that satisfy a hereditary property. Here a cohesive subgraph meets the hereditary property if all of its subgraphs satisfy the same property as itself. We show that several important cohesive subgraph models, such as maximal biclique and maximal k-biplex, satisfy the hereditary property. The problem of enumerating all maximal hereditary subgraphs was known to be NP-hard. To solve this problem, we first propose a novel and general pivot-based enumeration framework to efficiently enumerate all maximal hereditary subgraphs in a bipartite graph. Then, based on our general framework, we develop a new pivot-based algorithm with several pruning techniques to enumerate all maximal bicliques. We prove that the worst-case time complexity of our pivot-based maximal biclique enumeration algorithm is O(m x 2n\/2 ) (or O(m\\times 1.414^n)) which is near optimal since there exist up to O(2n\/2 ) maximal bicliques in a bipartite graph with n vertices and m edges. Moreover, we also show that our algorithm can achieve polynomial-delay time complexity with a slight modification. Third, on the basis of our general framework, we also devise a novel pivot-based algorithm with several non-trivial pruning techniques to enumerate maximal k-biplexes in a bipartite graph. Finally, we conduct extensive experiments using 11 real-world bipartite graphs to evaluate the proposed algorithms. The results show that our pivot-based solutions can achieve one order of magnitude (three orders of magnitude) faster than the state-of-the-art maximal biclique enumeration algorithms (maximal k-biplex enumeration algorithms).<\/jats:p>","DOI":"10.1145\/3589283","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:26:45Z","timestamp":1687292805000},"page":"1-26","source":"Crossref","is-referenced-by-count":16,"title":["Hereditary Cohesive Subgraphs Enumeration on Bipartite Graphs: The Power of Pivot-based Approaches"],"prefix":"10.1145","volume":"1","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\/0000-0003-0982-341X","authenticated-orcid":false,"given":"Xiaowei","family":"Ye","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\/0009-0001-1839-8788","authenticated-orcid":false,"given":"Weipeng","family":"Zhang","sequence":"additional","affiliation":[{"name":"Tencent Technology (Shenzhen) Company Limited, 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":[[2023,6,20]]},"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. 3558--3564.","DOI":"10.24963\/ijcai.2020\/492"},{"key":"e_1_2_2_2_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_2_3_1","unstructured":"Rachel Behar and Sara Cohen. 2018. Finding All Maximal Connected s-Cliques in Social Networks. In EDBT. 61--72."},{"key":"e_1_2_2_4_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_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkg340"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2015.04.001"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9632-8"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529341"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.04.003"},{"key":"e_1_2_2_11_1","first-page":"1","article-title":"Sublinear-Space Bounded-Delay Enumeration for Massive Network Analytics","volume":"55","author":"Conte Alessio","year":"2016","unstructured":"Alessio Conte, Roberto Grossi, Andrea Marino, and Luca Versari. 2016. Sublinear-Space Bounded-Delay Enumeration for Massive Network Analytics: Maximal Cliques. In ICALP, Vol. 55. 148:1--148:15.","journal-title":"Maximal Cliques. In ICALP"},{"key":"e_1_2_2_12_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_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.02.001"},{"key":"e_1_2_2_14_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_2_15_1","first-page":"403","article-title":"Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time","volume":"6506","author":"Eppstein David","year":"2010","unstructured":"David Eppstein, Maarten L\u00f6 ffler, and Darren Strash. 2010. Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time. In ISAAC, Vol. 6506. 403--414.","journal-title":"ISAAC"},{"key":"e_1_2_2_16_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_2_17_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_2_18_1","volume-title":"Alex Beutel, Neil Shah, Kijung Shin, and Christos Faloutsos.","author":"Hooi Bryan","year":"2016","unstructured":"Bryan Hooi, Hyun Ah Song, Alex Beutel, Neil Shah, Kijung Shin, and Christos Faloutsos. 2016. FRAUDAR: Bounding Graph Fraud in the Face of Camouflage. In KDD. 895--904."},{"key":"e_1_2_2_19_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_2_20_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.78.016108"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"e_1_2_2_22_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_2_23_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl020"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190660"},{"key":"e_1_2_2_25_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_2_26_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1970-125-1"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00606-9"},{"key":"e_1_2_2_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_2_29_1","first-page":"33","article-title":"Effective Pruning Techniques for Mining Quasi-Cliques","volume":"5212","author":"Liu Guimei","year":"2008","unstructured":"Guimei Liu and Limsoon Wong. 2008. Effective Pruning Techniques for Mining Quasi-Cliques. In ECML\/PKDD, Vol. 5212. 33--49.","journal-title":"ECML\/PKDD"},{"key":"e_1_2_2_30_1","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_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760024"},{"key":"e_1_2_2_32_1","first-page":"569","article-title":"Summarizing Online User Reviews Using Bicliques","volume":"9587","author":"Muhammad Azam Sheikh","year":"2016","unstructured":"Azam Sheikh Muhammad, Peter Damaschke, and Olof Mogren. 2016. Summarizing Online User Reviews Using Bicliques. In SOFSEM, Vol. 9587. 569--579.","journal-title":"SOFSEM"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.11.016"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00333-0"},{"key":"e_1_2_2_35_1","doi-asserted-by":"crossref","unstructured":"Jian Pei Daxin Jiang and Aidong Zhang. 2005. On mining cross-graph quasi-cliques. In KDD. 228--238.","DOI":"10.1145\/1081870.1081898"},{"key":"e_1_2_2_36_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_2_37_1","first-page":"109","article-title":"Bicliques in Graphs I","volume":"20","author":"Prisner Erich","year":"2000","unstructured":"Erich Prisner. 2000. Bicliques in Graphs I: Bounds on Their Number. Comb., Vol. 20, 1 (2000), 109--117.","journal-title":"Bounds on Their Number. Comb."},{"key":"e_1_2_2_38_1","volume-title":"Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning. 539--550","author":"Rymon Ron","year":"1992","unstructured":"Ron Rymon. 1992. Search through Systematic Set Enumeration. In Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning. 539--550."},{"key":"e_1_2_2_39_1","doi-asserted-by":"crossref","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.","DOI":"10.1137\/1.9781611974348.36"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1656479.1656483"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.06.015"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-13-S18-A10"},{"key":"e_1_2_2_43_1","doi-asserted-by":"crossref","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.","DOI":"10.1109\/ICDM.2018.00072"},{"key":"e_1_2_2_44_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_2_45_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_2_46_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_2_47_1","volume-title":"Maximum k-Biplex Search on Bipartite Graphs: A Symmetric-BK Branching Approach. CoRR","author":"Yu Kaiqiang","year":"2022","unstructured":"Kaiqiang Yu and Cheng Long. 2022. Maximum k-Biplex Search on Bipartite Graphs: A Symmetric-BK Branching Approach. CoRR, Vol. abs\/2208.13207 (2022)."},{"key":"e_1_2_2_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_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2021.3077071"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-15-110"},{"key":"e_1_2_2_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_2_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. io","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\/3589283","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589283","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:54Z","timestamp":1750182534000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589283"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,13]]}},"alternative-id":["10.1145\/3589283"],"URL":"https:\/\/doi.org\/10.1145\/3589283","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}