{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T19:01:14Z","timestamp":1774983674296,"version":"3.50.1"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T00:00:00Z","timestamp":1739145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62072138, 62472123"],"award-info":[{"award-number":["62072138, 62472123"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,2,10]]},"abstract":"<jats:p>Finding the maximum biclique in a bipartite graph is a fundamental graph analysis problem. Existing methods for maximum biclique search are not very efficient because they cannot effectively reduce the size of a bipartite graph composed of large bicliques that are loosely linked together because the graph reduction strategies adopted by these methods only consider local densities of vertices.<\/jats:p>\n                  <jats:p>This paper proposes a novel approach to maximum biclique search. The unique feature of this approach is building a linear-space data-driven index called BCviz that helps accurately identify subgraphs containing all bicliques with sizes no less than a certain threshold. The core technique of BCviz is determining a total order of vertices that can reveal both the local density and the connectivity of the vertices. Notably, our work is the first one to take connectivity into account in graph reduction. Interestingly, the total order of vertices entails BCviz an illustrative visualization of the distribution of cohesive subgraphs in the input graph.<\/jats:p>\n                  <jats:p>To deeply understand BCviz, we carry out a theoretical study on its properties and reveal how it enables more effective graph reduction. Based on BCviz, we propose an exact maximum biclique search algorithm that searches for results on much smaller subgraphs than any existing method does.<\/jats:p>\n                  <jats:p>In addition, we improve the efficiency of index construction by two techniques. One is approximating an edge's local density with an upper bound that can be derived in linear time. The other is a lightweight vertex ordering method called one-spot ordering which reduces unnecessary cohesion computations.<\/jats:p>\n                  <jats:p>Extensive experiments indicate that the proposed maximum biclique search methods based on BCviz and its variants outperform the state-of-the-art search-based methods by 2--3 orders of magnitude. Compared with the state-of-the-art index for maximum biclique search, the improved BCviz index can reduce the index size by 1--2 orders of magnitude and the index construction time by up to 2 orders of magnitude.<\/jats:p>","DOI":"10.1145\/3709666","type":"journal-article","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T15:45:06Z","timestamp":1739288706000},"page":"1-27","source":"Crossref","is-referenced-by-count":2,"title":["BCviz: A Linear-Space Index for Mining and Visualizing Cohesive Bipartite Subgraphs"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-8004-1313","authenticated-orcid":false,"given":"Jianxiong","family":"Ye","sequence":"first","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9475-8944","authenticated-orcid":false,"given":"Zhaonian","family":"Zou","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-8597-2082","authenticated-orcid":false,"given":"Dandan","family":"Liu","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-7063-3396","authenticated-orcid":false,"given":"Bin","family":"Yang","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-9196-4015","authenticated-orcid":false,"given":"Xudong","family":"Liu","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, China"}]}],"member":"320","published-online":{"date-parts":[[2025,2,11]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2020\/492"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687725"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSI.2007.907875"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2003.09.004"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-8733(96)00301-2"},{"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.1145\/2723372.2746486"},{"key":"e_1_2_2_8_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."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-023-00797-x"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3459241"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529341"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529341"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3467861.3467873"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00207"},{"key":"e_1_2_2_15_1","volume-title":"Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology (ISMB). 93--103","author":"Cheng Yizong","unstructured":"Yizong Cheng and George M. Church. 2000. Biclustering of Expression Data. In Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology (ISMB). 93--103."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589283"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1199"},{"key":"e_1_2_2_18_1","volume-title":"Madhav V Marathe, Aravind Srinivasan, Zoltan Toroczkai, and Nan Wang.","author":"Eubank Stephen","year":"2004","unstructured":"Stephen Eubank, Hasan Guclu, VS Anil Kumar, Madhav V Marathe, Aravind Srinivasan, Zoltan Toroczkai, and Nan Wang. 2004. Modelling disease outbreaks in realistic urban social networks. Nat., Vol. 429, 6988 (2004), 180--184."},{"key":"e_1_2_2_19_1","volume-title":"Informatica (Slovenia)","volume":"39","author":"Fang Gang","year":"2015","unstructured":"Gang Fang, Yue Wu, Ming Li, and Jia Chen. 2015. An Efficient Algorithm for Mining Frequent Closed Itemsets. Informatica (Slovenia), Vol. 39, 1 (2015)."},{"key":"e_1_2_2_20_1","volume-title":"Johnson","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0109047"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.70"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/30.1-2.81"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(99)00040-7"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1341531.1341550"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.78.016108"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273574"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45735-6_1"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl020"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/11564126_18"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2020.104922"},{"key":"e_1_2_2_32_1","volume-title":"Proceedings of the International World Wide Web Conference (WWW). 1130--1141","author":"Liu Boge","year":"2019","unstructured":"Boge Liu, Long Yuan, Xuemin Lin, Lu Qin, Wenjie Zhang, and Jingren Zhou. 2019. Efficient (a,(\u03b2))-core Computation: an Index-based Approach. In Proceedings of the International World Wide Web Conference (WWW). 1130--1141."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/11823728_42"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2003.1250919"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2006.10"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397234"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07046-9_16"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00333-0"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557097"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974348.36"},{"key":"e_1_2_2_41_1","volume-title":"Proceedings of the International Conference on Computational Science and Engineering (CSE). 132--137","author":"S\u00f6zdinler Melih","unstructured":"Melih S\u00f6zdinler and Can C. \u00d6zturan. 2018. Finding Maximum Edge Biclique in Bipartite Networks by Integer Programming. In Proceedings of the International Conference on Computational Science and Engineering (CSE). 132--137."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.51"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-13-S18-A10"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.3389\/fnins.2018.00156"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2018.00072"},{"key":"e_1_2_2_46_1","volume-title":"Proceedings of the International Conference on Research and Development in Information Retrieval (SIGIR). 501--508","author":"Wang Jun","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 Proceedings of the International Conference on Research and Development in Information Retrieval (SIGIR). 501--508."},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956779"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00042"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00217"},{"key":"e_1_2_2_50_1","volume-title":"Proceedings of the International Conference on Management of Data (SIGMOD).","author":"Wang Nan","unstructured":"Nan Wang, Srinivasan Parthasarathy, Kian-Lee Tan, and Anthony K. H. Tung. 2008. CSV: visualizing and mining cohesive subgraphs. In Proceedings of the International Conference on Management of Data (SIGMOD)."},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2017.12.012"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3538598.3538610"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-023-00786-0"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218213005002387"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588932"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517847"},{"key":"e_1_2_2_57_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_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517137"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-15-110"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247652"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2018.09.017"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2018.03.010"},{"key":"e_1_2_2_63_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\/10.1145\/3709666","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3709666","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:18:25Z","timestamp":1774981105000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709666"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,10]]},"references-count":63,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2,10]]}},"alternative-id":["10.1145\/3709666"],"URL":"https:\/\/doi.org\/10.1145\/3709666","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,10]]}}}