{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T15:20:38Z","timestamp":1777735238871,"version":"3.51.4"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:p>Bipartite graphs have been widely used to model the relationship between entities of different types, where vertices are partitioned into two disjoint sets\/sides. Finding dense subgraphs in a bipartite graph is of great significance and encompasses many applications. However, none of the existing dense bipartite subgraph models consider similarity between vertices from the same side, and as a result, the identified results may include vertices that are not similar to each other. In this paper, we formulate the notion of similar-biclique which is a special kind of biclique where all vertices from a designated side are similar to each other, and aim to enumerate all similar-bicliques. The naive approach of first enumerating all maximal bicliques and then extracting all maximal similar-bicliques from them is inefficient, as enumerating maximal bicliques is time consuming. We propose a backtracking algorithm MSBE to directly enumerate maximal similar-bicliques, and power it by vertex reduction and optimization techniques. Furthermore, we design a novel index structure to speed up a time-critical operation of MSBE, as well as to speed up vertex reduction. Efficient index construction algorithms are also developed. Extensive experiments on 17 bipartite graphs as well as case studies are conducted to demonstrate the effectiveness and efficiency of our model and algorithms.<\/jats:p>","DOI":"10.14778\/3551793.3551854","type":"journal-article","created":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T22:25:03Z","timestamp":1664490303000},"page":"3085-3097","source":"Crossref","is-referenced-by-count":16,"title":["Identifying similar-bicliques in bipartite graphs"],"prefix":"10.14778","volume":"15","author":[{"given":"Kai","family":"Yao","sequence":"first","affiliation":[{"name":"The University of Sydney, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lijun","family":"Chang","sequence":"additional","affiliation":[{"name":"The University of Sydney, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,9,29]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. full version: https:\/\/lijunchang.github.io\/pdf\/2022-msbe-tr.pdf.  [n.d.]. full version: https:\/\/lijunchang.github.io\/pdf\/2022-msbe-tr.pdf."},{"key":"e_1_2_1_2_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.  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_3_1","volume-title":"Friends and neighbors on the web. Social networks 25, 3","author":"Adamic Lada A","year":"2003","unstructured":"Lada A Adamic and Eytan Adar . 2003. Friends and neighbors on the web. Social networks 25, 3 ( 2003 ), 211--230. Lada A Adamic and Eytan Adar. 2003. Friends and neighbors on the web. Social networks 25, 3 (2003), 211--230."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2003.09.004"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37401-2_21"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2618795"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9632-8"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339724"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516688"},{"key":"e_1_2_1_11_1","volume-title":"Overmars","author":"de Berg Mark","year":"2008","unstructured":"Mark de Berg , Otfried Cheong , Marc J. van Kreveld , and Mark H . Overmars . 2008 . Computational geometry: algorithms and applications, 3 rd Edition. Springer . Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. 2008. Computational geometry: algorithms and applications, 3rd Edition. Springer.","edition":"3"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.2307\/1932409"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3133130"},{"key":"e_1_2_1_14_1","volume-title":"2018 IEEE International Conference on Service Operations and Logistics, and Informatics (SOLI). IEEE, 97--101","author":"Thi Thi Zin Radia","year":"2018","unstructured":"Radia EL BACHA and Thi Thi Zin . 2018 . Ranking of influential users based on user-tweet bipartite graph . In 2018 IEEE International Conference on Service Operations and Logistics, and Informatics (SOLI). IEEE, 97--101 . Radia EL BACHA and Thi Thi Zin. 2018. Ranking of influential users based on user-tweet bipartite graph. In 2018 IEEE International Conference on Service Operations and Logistics, and Informatics (SOLI). IEEE, 97--101."},{"key":"e_1_2_1_15_1","volume-title":"Arboricity and bipartite subgraph listing algorithms. Information processing letters 51, 4","author":"Eppstein David","year":"1994","unstructured":"David Eppstein . 1994. Arboricity and bipartite subgraph listing algorithms. Information processing letters 51, 4 ( 1994 ), 207--211. David Eppstein. 1994. Arboricity and bipartite subgraph listing algorithms. Information processing letters 51, 4 (1994), 207--211."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17517-6_36"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372923.3404783"},{"key":"e_1_2_1_18_1","unstructured":"Dorit S Hochbaum. 1996. Approximating covering and packing problems: set cover vertex cover independent set and related problems. In Approximation algorithms for NP-hard problems. 94--143.  Dorit S Hochbaum. 1996. Approximating covering and packing problems: set cover vertex cover independent set and related problems. In Approximation algorithms for NP-hard problems. 94--143."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939747"},{"key":"e_1_2_1_20_1","first-page":"241","article-title":"Distribution de la flore alpine dans le bassin des Dranses et dans quelques r\u00e9gions voisines","volume":"37","author":"Jaccard Paul","year":"1901","unstructured":"Paul Jaccard . 1901 . Distribution de la flore alpine dans le bassin des Dranses et dans quelques r\u00e9gions voisines . Bull Soc Vaudoise Sci Nat 37 (1901), 241 -- 272 . Paul Jaccard. 1901. Distribution de la flore alpine dans le bassin des Dranses et dans quelques r\u00e9gions voisines. Bull Soc Vaudoise Sci Nat 37 (1901), 241--272.","journal-title":"Bull Soc Vaudoise Sci Nat"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775126"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623632"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289026"},{"key":"e_1_2_1_24_1","volume-title":"Trawling the web for emerging cyber-communities. Computer networks 31, 11--16","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 31, 11--16 ( 1999 ), 1481--1493. Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew Tomkins. 1999. Trawling the web for emerging cyber-communities. Computer networks 31, 11--16 (1999), 1481--1493."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_26_1","volume-title":"Biclique communities. Physical review E 78, 1","author":"Lehmann Sune","year":"2008","unstructured":"Sune Lehmann , Martin Schwartz , and Lars Kai Hansen . 2008. Biclique communities. Physical review E 78, 1 ( 2008 ), 016108. Sune Lehmann, Martin Schwartz, and Lars Kai Hansen. 2008. Biclique communities. Physical review E 78, 1 (2008), 016108."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.73.026120"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/646491.694954"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11564126_18"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190660"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.20591"},{"key":"e_1_2_1_32_1","volume-title":"MatchSim: a novel similarity measure based on maximum neighborhood matching. Knowledge and information systems 32, 1","author":"Lin Zhenjiang","year":"2012","unstructured":"Zhenjiang Lin , Michael R Lyu , and Irwin King . 2012. MatchSim: a novel similarity measure based on maximum neighborhood matching. Knowledge and information systems 32, 1 ( 2012 ), 141--166. Zhenjiang Lin, Michael R Lyu, and Irwin King. 2012. MatchSim: a novel similarity measure based on maximum neighborhood matching. Knowledge and information systems 32, 1 (2012), 141--166."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/11823728_42"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69733-6_26"},{"key":"e_1_2_1_35_1","volume-title":"Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications 390, 6","author":"L\u00fc Linyuan","year":"2011","unstructured":"Linyuan L\u00fc and Tao Zhou . 2011. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications 390, 6 ( 2011 ), 1150--1170. Linyuan L\u00fc and Tao Zhou. 2011. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications 390, 6 (2011), 1150--1170."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397234"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27810-8_23"},{"key":"e_1_2_1_38_1","volume-title":"A survey of link prediction in complex networks. ACM computing surveys (CSUR) 49, 4","author":"Mart\u00ednez V\u00edctor","year":"2016","unstructured":"V\u00edctor Mart\u00ednez , Fernando Berzal , and Juan-Carlos Cubero . 2016. A survey of link prediction in complex networks. ACM computing surveys (CSUR) 49, 4 ( 2016 ), 1--33. V\u00edctor Mart\u00ednez, Fernando Berzal, and Juan-Carlos Cubero. 2016. A survey of link prediction in complex networks. ACM computing surveys (CSUR) 49, 4 (2016), 1--33."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/0604028"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00333-0"},{"key":"e_1_2_1_41_1","volume-title":"Automatic text processing: The transformation, analysis, and retrieval of. Reading: Addison-Wesley 169","author":"Salton Gerard","year":"1989","unstructured":"Gerard Salton . 1989. Automatic text processing: The transformation, analysis, and retrieval of. Reading: Addison-Wesley 169 ( 1989 ). Gerard Salton. 1989. Automatic text processing: The transformation, analysis, and retrieval of. Reading: Addison-Wesley 169 (1989)."},{"key":"e_1_2_1_42_1","volume-title":"Obtaining maximal concatenated phylogenetic data sets from large sequence databases. Molecular biology and evolution 20, 7","author":"Sanderson Michael J","year":"2003","unstructured":"Michael J Sanderson , Amy C Driskell , Richard H Ree , Oliver Eulenstein , and Sasha Langley . 2003. Obtaining maximal concatenated phylogenetic data sets from large sequence databases. Molecular biology and evolution 20, 7 ( 2003 ), 1036--1042. Michael J Sanderson, Amy C Driskell, Richard H Ree, Oliver Eulenstein, and Sasha Langley. 2003. Obtaining maximal concatenated phylogenetic data sets from large sequence databases. Molecular biology and evolution 20, 7 (2003), 1036--1042."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159678"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989399"},{"key":"e_1_2_1_45_1","volume-title":"A survey of collaborative filtering techniques. Advances in artificial intelligence 2009","author":"Su Xiaoyuan","year":"2009","unstructured":"Xiaoyuan Su and Taghi M Khoshgoftaar . 2009. A survey of collaborative filtering techniques. Advances in artificial intelligence 2009 ( 2009 ). Xiaoyuan Su and Taghi M Khoshgoftaar. 2009. A survey of collaborative filtering techniques. Advances in artificial intelligence 2009 (2009)."},{"key":"e_1_2_1_46_1","volume-title":"The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical computer science 363, 1","author":"Tomita Etsuji","year":"2006","unstructured":"Etsuji Tomita , Akira Tanaka , and Haruhisa Takahashi . 2006. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical computer science 363, 1 ( 2006 ), 28--42. Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. 2006. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical computer science 363, 1 (2006), 28--42."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457278"},{"key":"e_1_2_1_48_1","volume-title":"Fimi","volume":"126","author":"Uno Takeaki","year":"2004","unstructured":"Takeaki Uno , Masashi Kiyomi , Hiroki Arimura , 2004 . LCM ver. 2: Efficient mining algorithms for frequent\/closed\/maximal itemsets . In Fimi , Vol. 126 . Takeaki Uno, Masashi Kiyomi, Hiroki Arimura, et al. 2004. LCM ver. 2: Efficient mining algorithms for frequent\/closed\/maximal itemsets. In Fimi, Vol. 126."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148170.1148257"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2018.03.036"},{"key":"e_1_2_1_51_1","volume-title":"C-Rank: A link-based similarity measure for scientific literature databases. Information sciences 326","author":"Yoon Seok-Ho","year":"2016","unstructured":"Seok-Ho Yoon , Sang-Wook Kim , and Sunju Park . 2016. C-Rank: A link-based similarity measure for scientific literature databases. Information sciences 326 ( 2016 ), 25--40. Seok-Ho Yoon, Sang-Wook Kim, and Sunju Park. 2016. C-Rank: A link-based similarity measure for scientific literature databases. Information sciences 326 (2016), 25--40."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2021.3077071"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972726.27"},{"key":"e_1_2_1_54_1","volume-title":"On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types. BMC bioinformatics 15, 1","author":"Zhang Yun","year":"2014","unstructured":"Yun Zhang , Charles A Phillips , Gary L Rogers , Erich J Baker , Elissa J Chesler , and Michael A Langston . 2014. On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types. BMC bioinformatics 15, 1 ( 2014 ), 1--18. Yun Zhang, Charles A Phillips, Gary L Rogers, Erich J Baker, Elissa J Chesler, and Michael A Langston. 2014. On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types. BMC bioinformatics 15, 1 (2014), 1--18."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129183115500965"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646025"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-32049-6_14"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3551793.3551854","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:51:25Z","timestamp":1672224685000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3551793.3551854"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":57,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["10.14778\/3551793.3551854"],"URL":"https:\/\/doi.org\/10.14778\/3551793.3551854","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,7]]}}}