{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T10:07:07Z","timestamp":1775815627008,"version":"3.50.1"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,10]]},"abstract":"<jats:p>\n            In this paper, we study the problem of (\n            <jats:italic>p<\/jats:italic>\n            , q)-biclique counting and enumeration for large sparse bipartite graphs. Given a bipartite\n            <jats:italic>G<\/jats:italic>\n            = (\n            <jats:italic>U, V<\/jats:italic>\n            , E), and two integer parameters\n            <jats:italic>p<\/jats:italic>\n            and q, we aim to efficiently count and enumerate all (p, q)-bicliques in\n            <jats:italic>G<\/jats:italic>\n            , where a (p, q)-biclique\n            <jats:italic>B<\/jats:italic>\n            (\n            <jats:italic>L, R<\/jats:italic>\n            ) is a complete subgraph of\n            <jats:italic>G<\/jats:italic>\n            with\n            <jats:italic>L<\/jats:italic>\n            \u2286\n            <jats:italic>U, R<\/jats:italic>\n            \u2286\n            <jats:italic>V<\/jats:italic>\n            , |L| = p, and |R| = q. The problem of (p, q)-biclique counting and enumeration has many applications, such as graph neural network information aggregation, densest subgraph detection, and cohesive subgroup analysis, etc. Despite the wide range of applications, to the best of our knowledge, we note that there is no efficient and scalable solution to this problem in the literature.\n          <\/jats:p>\n          <jats:p>\n            This problem is computationally challenging, due to the worst-case exponential number of (p, q)-bicliques. In this paper, we propose a competitive branch-and-bound baseline method, namely BCList, which explores the search space in a depth-first manner, together with a variety of pruning techniques. Although BCList offers a useful computation framework to our problem, its worst-case time complexity is exponential to\n            <jats:italic>p + q.<\/jats:italic>\n            To alleviate this, we propose an advanced approach, called BCList++. Particularly, BCList++ applies a layer based exploring strategy to enumerate (\n            <jats:italic>p, q<\/jats:italic>\n            )-bicliques by anchoring the search on either\n            <jats:italic>U<\/jats:italic>\n            or\n            <jats:italic>V<\/jats:italic>\n            only, which has a worst-case time complexity exponential to either\n            <jats:italic>p<\/jats:italic>\n            or\n            <jats:italic>q<\/jats:italic>\n            only. Consequently, a vital task is to choose a layer with the least computation cost. To this end, we develop a cost model, which is built upon an unbiased estimator for the density of 2-hop graph induced by\n            <jats:italic>U<\/jats:italic>\n            or\n            <jats:italic>V.<\/jats:italic>\n            To improve computation efficiency, BCList++ exploits pre-allocated arrays and vertex labeling techniques such that the frequent subgraph creating operations can be substituted by array element switching operations. We conduct extensive experiments on 16 real-life datasets, and the experimental results demonstrate that BCList++ significantly outperforms the baseline methods by up to 3 orders of magnitude. We show via a case study that (p, q)-bicliques optimize the efficiency of graph neural networks.\n          <\/jats:p>","DOI":"10.14778\/3489496.3489497","type":"journal-article","created":{"date-parts":[[2022,2,5]],"date-time":"2022-02-05T00:28:36Z","timestamp":1644020916000},"page":"141-153","source":"Crossref","is-referenced-by-count":33,"title":["(p,q)-biclique counting and enumeration for large sparse bipartite graphs"],"prefix":"10.14778","volume":"15","author":[{"given":"Jianye","family":"Yang","sequence":"first","affiliation":[{"name":"Guangzhou University, Guangzhou, China"}]},{"given":"Yun","family":"Peng","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney, Australia"}]}],"member":"320","published-online":{"date-parts":[[2022,2,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/3491440.3491932"},{"key":"e_1_2_1_2_1","volume":"201","author":"Benson A. R.","unstructured":"A. R. Benson , D. F. Gleich , and J. Leskovec. 201 6. Higher-order organization of complex networks. Science (2016), 163--166. A. R. Benson, D. F. Gleich, and J. Leskovec. 2016. Higher-order organization of complex networks. Science (2016), 163--166.","journal-title":"J. Leskovec."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"S. P. Borgatti and M. G. Everett. 1997. Network analysis of 2-mode data. Social networks (1997) 243--269.  S. P. Borgatti and M. G. Everett. 1997. Network analysis of 2-mode data. Social networks (1997) 243--269.","DOI":"10.1016\/S0378-8733(96)00301-2"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3459241"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3483529.3483688"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186125"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557051"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3133130"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90121-X"},{"key":"e_1_2_1_11_1","volume":"201","author":"Feng Q.","unstructured":"Q. Feng , S. Li , Z. Zhou , and J. Wang. 201 7. Parameterized algorithms for edge biclique and related problems. Theoretical Computer Science (2017). Q. Feng, S. Li, Z. Zhou, and J. Wang. 2017. Parameterized algorithms for edge biclique and related problems. Theoretical Computer Science (2017).","journal-title":"J. Wang."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0904"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218003"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3294771.3294869"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939747"},{"key":"e_1_2_1_16_1","unstructured":"Zhihao Jia Sina Lin Rex Ying Jiaxuan You Jure Leskovec and Alex Aiken. 2020. Redundancy-Free Computation for Graph Neural Networks. In SIGKDD.  Zhihao Jia Sina Lin Rex Ying Jiaxuan You Jure Leskovec and Alex Aiken. 2020. Redundancy-Free Computation for Graph Neural Networks. In SIGKDD."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159729"},{"key":"e_1_2_1_18_1","volume-title":"Basic notions for the analysis of large two-mode networks. Social networks","author":"Latapy M.","year":"2008","unstructured":"M. Latapy , C. Magnien , and N. Del Vecchio . 2008. Basic notions for the analysis of large two-mode networks. Social networks ( 2008 ), 31--48. M. Latapy, C. Magnien, and N. Del Vecchio. 2008. Basic notions for the analysis of large two-mode networks. Social networks (2008), 31--48."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190660"},{"key":"e_1_2_1_20_1","volume-title":"Approximately Counting Butterflies in Large Bipartite Graph Streams. TKDE","author":"Li Rundong","year":"2021","unstructured":"Rundong Li , Pinghui Wang , Peng Jia , Xiangliang Zhang , Junzhou Zhao , Jing Tao , Ye Yuan , and Xiaohong Guan . 2021. Approximately Counting Butterflies in Large Bipartite Graph Streams. TKDE ( 2021 ), 1--1. Rundong Li, Pinghui Wang, Peng Jia, Xiangliang Zhang, Junzhou Zhao, Jing Tao, Ye Yuan, and Xiaohong Guan. 2021. Approximately Counting Butterflies in Large Bipartite Graph Streams. TKDE (2021), 1--1."},{"key":"e_1_2_1_21_1","volume":"200","author":"Lind Pedro G.","unstructured":"Pedro G. Lind , Marta C. G., and Hans J. Herrmann. 200 5. Cycles and clustering in bipartite networks. Physical Review E (2005), 814--818. Pedro G. Lind, Marta C. G., and Hans J. Herrmann. 2005. Cycles and clustering in bipartite networks. Physical Review E (2005), 814--818.","journal-title":"Hans J. Herrmann."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313522"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397234"},{"key":"e_1_2_1_24_1","volume-title":"Efficient maintenance for maximal bicliques in bipartite graph streams. WWWJ","author":"Ma Ziyi","year":"2021","unstructured":"Ziyi Ma , Yuling Liu , Yikun Hu , Jianye Yang , Chubo Liu , and Huadong Dai . 2021. Efficient maintenance for maximal bicliques in bipartite graph streams. WWWJ ( 2021 ). Ziyi Ma, Yuling Liu, Yikun Hu, Jianye Yang, Chubo Liu, and Huadong Dai. 2021. Efficient maintenance for maximal bicliques in bipartite graph streams. WWWJ (2021)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Kazuhisa Makino and Takeaki Uno. 2004. New algorithms for enumerating all maximal cliques. In Algorithm Theory-SWAT. 260--272.  Kazuhisa Makino and Takeaki Uno. 2004. New algorithms for enumerating all maximal cliques. In Algorithm Theory-SWAT. 260--272.","DOI":"10.1007\/978-3-540-27810-8_23"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783385"},{"key":"e_1_2_1_27_1","volume-title":"Triadic closure in two-mode networks: Redefining the global and local clustering coefficients. Social Networks","author":"Opsahl T.","year":"2013","unstructured":"T. Opsahl . 2013. Triadic closure in two-mode networks: Redefining the global and local clustering coefficients. Social Networks ( 2013 ), 159--167. T. Opsahl. 2013. Triadic closure in two-mode networks: Redefining the global and local clustering coefficients. Social Networks (2013), 159--167."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"G. Palla I. Der\u00e9nyi I. Farkas and T. Vicsek. 2005. Uncovering the overlapping community structure of complex networks in nature and society. Nature (2005) 814--818.  G. Palla I. Der\u00e9nyi I. Farkas and T. Vicsek. 2005. Uncovering the overlapping community structure of complex networks in nature and society. Nature (2005) 814--818.","DOI":"10.1038\/nature03607"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"M. J. Sanderson A. C. Driskell R. H. Ree O. Eulenstein and S. Langley. 2003. Obtaining maximal concatenated phylogenetic data sets from large sequence databases. Molecular biology and evolution (2003) 1036--1042.  M. J. Sanderson A. C. Driskell R. H. Ree O. Eulenstein and S. Langley. 2003. Obtaining maximal concatenated phylogenetic data sets from large sequence databases. Molecular biology and evolution (2003) 1036--1042.","DOI":"10.1093\/molbev\/msg115"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220097"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741640"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 2016 SIAM International Conference on Data Mining. 315--323","author":"Shaham E.","unstructured":"E. Shaham , H. Yu , and X. Li . 2016. On finding the maximum edge biclique in a bipartite graph: a subspace clustering approach . In Proceedings of the 2016 SIAM International Conference on Data Mining. 315--323 . E. Shaham, H. Yu, and X. Li. 2016. On finding the maximum edge biclique in a bipartite graph: a subspace clustering approach. In Proceedings of the 2016 SIAM International Conference on Data Mining. 315--323."},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"S. Shahinpour S. Shirvani Z. Ertem and S. Butenko. 2017. Scale reduction techniques for computing maximum induced bicliques. Algorithms (2017).  S. Shahinpour S. Shirvani Z. Ertem and S. Butenko. 2017. Scale reduction techniques for computing maximum induced bicliques. Algorithms (2017).","DOI":"10.3390\/a10040113"},{"key":"e_1_2_1_34_1","volume-title":"sGrapp: Butterfly Approximation in Streaming Graphs. arXiv preprint arXiv:2101.12334","author":"Sheshbolouki A.","year":"2021","unstructured":"A. Sheshbolouki and M. T. \u00d6zsu . 2021. sGrapp: Butterfly Approximation in Streaming Graphs. arXiv preprint arXiv:2101.12334 ( 2021 ). A. Sheshbolouki and M. T. \u00d6zsu. 2021. sGrapp: Butterfly Approximation in Streaming Graphs. arXiv preprint arXiv:2101.12334 (2021)."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401962"},{"key":"e_1_2_1_36_1","volume-title":"Progress in Informatics","author":"Takeaki UNO","year":"2012","unstructured":"UNO Takeaki . 2012. Implementation issues of clique enumeration algorithm. Special issue: Theoretical computer science and discrete mathematics , Progress in Informatics ( 2012 ), 25--30. UNO Takeaki. 2012. Implementation issues of clique enumeration algorithm. Special issue: Theoretical computer science and discrete mathematics, Progress in Informatics (2012), 25--30."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_2_1_38_1","unstructured":"P. Velickovic G. Cucurull A. Casanova A. Romero P. Lio and Y. Bengio. 2017. IGraph attention networks. In ICLR.  P. Velickovic G. Cucurull A. Casanova A. Romero P. Lio and Y. Bengio. 2017. IGraph attention networks. In ICLR."},{"key":"e_1_2_1_39_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.  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_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.Congress.2014.13"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148170.1148257"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339497"},{"key":"e_1_2_1_43_1","volume-title":"Efficient bitruss decomposition for large-scale bipartite graphs","author":"Wang Kai","unstructured":"Kai Wang , Xuemin Lin , Lu Qin , Wenjie Zhang , and Ying Zhang . 2020. Efficient bitruss decomposition for large-scale bipartite graphs . In ICDE. IEEE , 661--672. Kai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang, and Ying Zhang. 2020. Efficient bitruss decomposition for large-scale bipartite graphs. In ICDE. IEEE, 661--672."},{"key":"e_1_2_1_44_1","volume-title":"Towards efficient solutions of bitruss decomposition for large-scale bipartite graphs. VLDBJ","author":"Wang Kai","year":"2021","unstructured":"Kai Wang , Xuemin Lin , Lu Qin , Wenjie Zhang , and Ying Zhang . 2021. Towards efficient solutions of bitruss decomposition for large-scale bipartite graphs. VLDBJ ( 2021 ), 1--24. Kai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang, and Ying Zhang. 2021. Towards efficient solutions of bitruss decomposition for large-scale bipartite graphs. VLDBJ (2021), 1--24."},{"key":"e_1_2_1_45_1","volume-title":"Efficient and Effective Community Search on Large-scale Bipartite Graphs","author":"Wang Kai","unstructured":"Kai Wang , Zhang Wenjie , Xuemin Lin , Ying Zhang , Lu Qin , and Yuting Zhang . 2021. Efficient and Effective Community Search on Large-scale Bipartite Graphs . In ICDE. IEEE , 85--96. Kai Wang, Zhang Wenjie, Xuemin Lin, Ying Zhang, Lu Qin, and Yuting Zhang. 2021. Efficient and Effective Community Search on Large-scale Bipartite Graphs. In ICDE. IEEE, 85--96."},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Jianye Yang Yun Peng and Wenjie Zhang. 2021. (p q)-biclique counting and enumeration for large sparse bipartite graphs. https:\/\/github.com\/Jianye1hnu\/bclist_vldb\/blob\/main\/bclist_full.pdf  Jianye Yang Yun Peng and Wenjie Zhang. 2021. (p q)-biclique counting and enumeration for large sparse bipartite graphs. https:\/\/github.com\/Jianye1hnu\/bclist_vldb\/blob\/main\/bclist_full.pdf","DOI":"10.14778\/3489496.3489497"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447702"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/3327345.3327389"},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Yun Zhang C. A. Phillips G. L. Rogers E. J. Baker E. J. Chesler and M. 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 (2014) 1--18.  Yun Zhang C. A. Phillips G. L. Rogers E. J. Baker E. J. Chesler and M. 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 (2014) 1--18.","DOI":"10.1186\/1471-2105-15-110"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3489496.3489497","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:10:54Z","timestamp":1672225854000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3489496.3489497"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["10.14778\/3489496.3489497"],"URL":"https:\/\/doi.org\/10.14778\/3489496.3489497","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,10]]}}}