{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T20:47:13Z","timestamp":1775594833177,"version":"3.50.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"name":"Research Grants Council of the Hong Kong Special Administrative Region, China","award":["HKBU 12201923, C2003-23Y, CUHK 14217622, and 14206625"],"award-info":[{"award-number":["HKBU 12201923, C2003-23Y, CUHK 14217622, and 14206625"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,4,2]]},"abstract":"<jats:p>\n                    To identify dense subgraphs, many\n                    <jats:italic toggle=\"yes\">specific-subgraph algorithms<\/jats:italic>\n                    are developed for decomposition and maintenance on dynamic graphs. However, it suffers from two significant limitations. First, for each kind of subgraphs, it needs the development of specific maintenance algorithms, which is\n                    <jats:italic toggle=\"yes\">a costly effort.<\/jats:italic>\n                    This may also lead to\n                    <jats:italic toggle=\"yes\">potentially missing solutions<\/jats:italic>\n                    for an existing subgraph (e.g.,\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -nucleus maintenance). Second,\n                    <jats:italic toggle=\"yes\">no commonly useful properties and rules<\/jats:italic>\n                    can be derived from these quite different algorithms.\n                  <\/jats:p>\n                  <jats:p>\n                    To address these bottlenecks, we propose a unified framework for dense subgraph maintenance over dynamic bipartite graphs. We first give a definition of (\u03b1, \u03b2)-core as bi-core and formulate the problem of bi-core maintenance. To our best knowledge, we are the first to propose the maintenance equivalence of bi-core to other subgraphs, e.g.,\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -core,\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -truss, bi-truss, and\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -nucleus. To handle the update efficiently, we propose a novel index structure of bi-core and onion layers, which finely decomposes one (\u03b1, \u03b2)-core into different levels of layers. This theoretically improves state-of-the-art bi-core maintenance algorithms from\n                    <jats:italic toggle=\"yes\">unbounded<\/jats:italic>\n                    to\n                    <jats:italic toggle=\"yes\">bounded.<\/jats:italic>\n                    However, due to two search dimensions of (\u03b1, \u03b2)-cores w.r.t. parameters \u03b1 and \u03b2, it brings significant challenges for fast update. To tackle it, we develop a novel \u03baBCO-index for fast maintenance by adding\n                    <jats:italic toggle=\"yes\">a shortcut search of \u03ba-direction.<\/jats:italic>\n                    This reorganizes bi-core onion layers and reduces the space complexity from O(nd\n                    <jats:sub>max<\/jats:sub>\n                    ) to O(nk\n                    <jats:sub>max<\/jats:sub>\n                    ), where\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    is the size of vertices, and the cardinality of \u03ba-direction k\n                    <jats:sub>max<\/jats:sub>\n                    &lt;&lt; d\n                    <jats:sub>max<\/jats:sub>\n                    of the maximum degree holds in practice. Our proposed maintenance algorithms can handle a batch update of multiple edge insertions\/deletions simultaneously. Extensive results on large datasets demonstrate that our unified framework efficiently maintains several dense subgraphs and runs faster than state-of-the-art bi-core maintenance algorithms.\n                  <\/jats:p>","DOI":"10.1145\/3786618","type":"journal-article","created":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T17:54:13Z","timestamp":1775584453000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1615-6558","authenticated-orcid":false,"given":"Zitan","family":"Sun","sequence":"first","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-2390-7539","authenticated-orcid":false,"given":"Zihan","family":"Jia","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4673-2587","authenticated-orcid":false,"given":"Hong","family":"Cheng","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3650-0301","authenticated-orcid":false,"given":"Xin","family":"Huang","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9738-827X","authenticated-orcid":false,"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,7]]},"reference":[{"key":"e_1_2_1_1_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_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2015.04.001"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3617313"},{"key":"e_1_2_1_4_1","volume-title":"Locating pivotal connections: the K-Truss minimization and maximization problems. WWW","author":"Chen Chen","year":"2022","unstructured":"Chen Chen, Mengqi Zhang, Renjie Sun, Xiaoyang Wang, Weijie Zhu, and Xun Wang. 2022. Locating pivotal connections: the K-Truss minimization and maximization problems. WWW (2022), 899-926."},{"key":"e_1_2_1_5_1","first-page":"2544","volume-title":"Maximal Biclique Enumeration: A Prefix Tree Based Approach. In 40th IEEE International Conference on Data Engineering, ICDE 2024","author":"Chen Jiujian","year":"2024","unstructured":"Jiujian Chen, Kai Wang, Ronghua Li, Hongchao Qin, Xuemin Lin, and Guoren Wang. 2024. Maximal Biclique Enumeration: A Prefix Tree Based Approach. In 40th IEEE International Conference on Data Engineering, ICDE 2024, Utrecht, The Netherlands, May 13-16, 2024. IEEE, 2544-2556."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3696410.3714897"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings 28th International Conference on Extending Database Technology, EDBT 2025. 53-65","author":"Cheng Qihao","year":"2025","unstructured":"Qihao Cheng, Da Yan, Tianhao Wu, Lyuheng Yuan, Ji Cheng, Zhongyi Huang, and Yang Zhou. 2025. Efficient Enumeration of Large Maximal k-Plexes. In Proceedings 28th International Conference on Extending Database Technology, EDBT 2025. 53-65."},{"key":"e_1_2_1_8_1","volume-title":"Trusses: Cohesive Subgraphs for Social Network Analysis. Technical Report","author":"Cohen J.","year":"2008","unstructured":"J. Cohen. 2008. Trusses: Cohesive Subgraphs for Social Network Analysis. Technical Report. National Security Agency."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3677142"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings 27th International Conference on Extending Database Technology, EDBT 2024. 116-128","author":"Feng Qingshuai","year":"2024","unstructured":"Qingshuai Feng, You Peng, Wenjie Zhang, Xuemin Lin, and Ying Zhang. 2024. DSPC: Efficiently Answering Shortest Path Counting on Dynamic Graphs. In Proceedings 27th International Conference on Extending Database Technology, EDBT 2024. 116-128."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00202"},{"key":"e_1_2_1_12_1","first-page":"201","volume-title":"D-cores: Measuring Collaboration of Directed Graphs Based on Degeneracy. In 11th IEEE International Conference on Data Mining, ICDM","author":"Giatsidis Christos","year":"2011","unstructured":"Christos Giatsidis, Dimitrios M. Thilikos, and Michalis Vazirgiannis. 2011. D-cores: Measuring Collaboration of Directed Graphs Based on Degeneracy. In 11th IEEE International Conference on Data Mining, ICDM 2011. IEEE Computer Society, 201-210."},{"key":"e_1_2_1_13_1","first-page":"1311","article-title":"Querying k-truss community in large and dynamic graphs","author":"Huang Xin","year":"2014","unstructured":"Xin Huang, Hong Cheng, Lu Qin, Wentao Tian, and Jeffrey Xu Yu. 2014. Querying k-truss community in large and dynamic graphs. In SIGMOD. 1311-1322.","journal-title":"SIGMOD."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856323"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00649-y"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.12"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.158"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3659437.3659440"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529340"},{"key":"e_1_2_1_20_1","unstructured":"Fengnian Lin Boyu Ruan Junhao Gan and Lei Li. 2025. Efficient Bitruss Decomposition without Butterfly Enumeration. In SIGKDD."},{"key":"e_1_2_1_21_1","first-page":"97","article-title":"Efficient Community Search with Size Constraint","author":"Liu Boge","year":"2021","unstructured":"Boge Liu, Fan Zhang, Wenjie Zhang, Xuemin Lin, and Ying Zhang. 2021. Efficient Community Search with Size Constraint. In ICDE. 97-108.","journal-title":"ICDE."},{"key":"e_1_2_1_22_1","first-page":"909","volume-title":"39th IEEE International Conference on Data Engineering, ICDE","author":"Liu Qing","year":"2023","unstructured":"Qing Liu, Xuankun Liao, Xin Huang, Jianliang Xu, and Yunjun Gao. 2023. Distributed ((\u03b1) (\u03b2))-Core Decomposition over Bipartite Graphs. In 39th IEEE International Conference on Data Engineering, ICDE 2023. 909-921."},{"key":"e_1_2_1_23_1","first-page":"2183","article-title":"Truss-based Community Search over Large Directed Graphs","author":"Liu Qing","year":"2020","unstructured":"Qing Liu, Minjun Zhao, Xin Huang, Jianliang Xu, and Yunjun Gao. 2020. Truss-based Community Search over Large Directed Graphs. In SIGMOD. 2183-2197.","journal-title":"SIGMOD."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3617329"},{"key":"e_1_2_1_25_1","first-page":"81","volume-title":"DEXA 2024, Proceedings, Part I","volume":"14910","author":"Matsugu Shohei","year":"2024","unstructured":"Shohei Matsugu, Suomi Kobayashi, and Hiroaki Shiokawa. 2024. An Efficient Indexing Method for Dynamic Graph kNN. In Database and Expert Systems Applications - 35th International Conference, DEXA 2024, Proceedings, Part I, Vol. 14910. Springer, 81-89."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783385"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00139635"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589334.3645374"},{"key":"e_1_2_1_29_1","first-page":"2917","volume-title":"Counting Butterflies in Fully Dynamic Bipartite Graph Streams. In 40th IEEE International Conference on Data Engineering, ICDE","author":"Papadias Serafeim","year":"2024","unstructured":"Serafeim Papadias, Zoi Kaoudi, Varun Pandey, Jorge-Arnulfo Quian\u00e9-Ruiz, and Volker Markl. 2024. Counting Butterflies in Fully Dynamic Bipartite Graph Streams. In 40th IEEE International Conference on Data Engineering, ICDE 2024. 2917-2930."},{"key":"e_1_2_1_30_1","first-page":"353","article-title":"Mining Cross-Graph Quasi-Cliques in Gene Expression and Protein Interaction Data","author":"Pei Jian","year":"2005","unstructured":"Jian Pei, Daxin Jiang, and Aidong Zhang. 2005. Mining Cross-Graph Quasi-Cliques in Gene Expression and Protein Interaction Data. In ICDE. 353-354.","journal-title":"ICDE."},{"key":"e_1_2_1_31_1","volume-title":"Reps","author":"Ramalingam G.","year":"1996","unstructured":"G. Ramalingam and Thomas W. Reps. 1996. On the Computational Complexity of Dynamic Graph Problems. Theor. Comput. Sci. (1996), 233-277."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3446637"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741640"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1978.9989883"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3459637.3482324"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589278"},{"key":"e_1_2_1_37_1","first-page":"3270","volume-title":"Adaptive Truss Maximization on Large Graphs: A Minimum Cut Approach. In 40th IEEE International Conference on Data Engineering, ICDE","author":"Sun Zitan","year":"2024","unstructured":"Zitan Sun, Xin Huang, Chengzhi Piao, Cheng Long, and Jianliang Xu. 2024. Adaptive Truss Maximization on Large Graphs: A Minimum Cut Approach. In 40th IEEE International Conference on Data Engineering, ICDE 2024. 3270-3282."},{"key":"e_1_2_1_38_1","first-page":"354","volume-title":"Efficient Probabilistic Truss Indexing on Uncertain Graphs. In WWW '21: The Web Conference","author":"Sun Zitan","year":"2021","unstructured":"Zitan Sun, Xin Huang, Jianliang Xu, and Francesco Bonchi. 2021b. Efficient Probabilistic Truss Indexing on Uncertain Graphs. In WWW '21: The Web Conference 2021. 354-366."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3721428"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00658-5"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639262"},{"key":"e_1_2_1_44_1","first-page":"64","article-title":"Index-Based Optimal Algorithm for Computing K-Cores in Large Uncertain Graphs","author":"Yang Bohua","year":"2019","unstructured":"Bohua Yang, Dong Wen, Lu Qin, Ying Zhang, Lijun Chang, and Rong-Hua Li. 2019. Index-Based Optimal Algorithm for Computing K-Cores in Large Uncertain Graphs. In ICDE. 64-75.","journal-title":"ICDE."},{"key":"e_1_2_1_45_1","volume-title":"K-truss community most favorites query based on top-t. WWW","author":"Yang ZhiBang","year":"2022","unstructured":"ZhiBang Yang, Xiaoxue Li, Xu Zhang, Wensheng Luo, and Kenli Li. 2022. K-truss community most favorites query based on top-t. WWW (2022), 949-969."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588932"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl014"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3311398"},{"key":"e_1_2_1_49_1","first-page":"1024","article-title":"Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs","author":"Zhang Yikai","year":"2019","unstructured":"Yikai Zhang and Jeffrey Xu Yu. 2019. Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs. In SIGMOD. 1024-1041.","journal-title":"SIGMOD."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.93"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3332638"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448942"},{"key":"e_1_2_1_53_1","first-page":"4874","article-title":"Pivotal Relationship Identification","author":"Zhu Weijie","year":"2019","unstructured":"Weijie Zhu, Mengqi Zhang, Chen Chen, Xiaoyang Wang, Fan Zhang, and Xuemin Lin. 2019. Pivotal Relationship Identification: The K-Truss Minimization Problem. In IJCAI. 4874-4880.","journal-title":"The K-Truss Minimization Problem. In IJCAI."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3786618","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T19:54:54Z","timestamp":1775591694000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3786618"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,2]]},"references-count":53,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,4,2]]}},"alternative-id":["10.1145\/3786618"],"URL":"https:\/\/doi.org\/10.1145\/3786618","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,2]]}}}