{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:03Z","timestamp":1779174783173,"version":"3.51.4"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:p>\n            Cohesive multipartite subgraphs (CMS) in heterogeneous information networks (HINs) uncover closely connected vertex groups of multiple types, enhancing real applications like community search and anomaly detection. However, existing works for HINs pay less attention to searching CMS. In this paper, we leverage well-established concepts of meta-path and densest subgraph to propose a novel CMS model called the densest\n            <jats:italic>P<\/jats:italic>\n            -partite subgraph. Given a multipartite subgraph of an HIN induced by\n            <jats:italic>i<\/jats:italic>\n            =|\n            <jats:italic>P<\/jats:italic>\n            | types of vertices defined in a query meta-path P (i.e., a\n            <jats:italic>P<\/jats:italic>\n            -partite subgraph), we devise a novel density function which is the number of the instances of\n            <jats:italic>P<\/jats:italic>\n            over the geometric mean of the sizes of\n            <jats:italic>i<\/jats:italic>\n            different types of vertex sets in the subgraph. A\n            <jats:italic>P<\/jats:italic>\n            -partite subgraph with the highest density serves as the optimum result. To find the densest\n            <jats:italic>P<\/jats:italic>\n            -partite subgraph in an HIN with\n            <jats:italic>n<\/jats:italic>\n            vertices, we first design an exact algorithm with a runtime cost equivalent to solving \u0398(|M|) instances of the min-cut problem where |M|=\n            <jats:italic>O<\/jats:italic>\n            ((\n            <jats:italic>n\/i<\/jats:italic>\n            )\n            <jats:sup>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sup>\n            ). Then, we attempt a more efficient approximation algorithm that achieves a ratio of 1\/\n            <jats:italic>i<\/jats:italic>\n            but still incurs the cost of solving \u0398(|M|) instances of our proposed peeling problem. Both approaches struggle with scalability due to \u0398(|M|). To overcome this bottleneck, we improve the exact algorithm with novel pruning rules that non-trivially reduce the number of min-cut problem instances to solve to\n            <jats:italic>O<\/jats:italic>\n            (|M|). Empirically, 70-90% instances are pruned, making the improved exact algorithm significantly faster than the approximation algorithm. Extensive experiments on real datasets demonstrate the effectiveness of the proposed model and the efficiency of our algorithms.\n          <\/jats:p>","DOI":"10.14778\/3636218.3636226","type":"journal-article","created":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T17:04:07Z","timestamp":1709658247000},"page":"699-711","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Densest Multipartite Subgraph Search in Heterogeneous Information Networks"],"prefix":"10.14778","volume":"17","author":[{"given":"Lu","family":"Chen","sequence":"first","affiliation":[{"name":"Swinburne University of Technology, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chengfei","family":"Liu","sequence":"additional","affiliation":[{"name":"Swinburne University of Technology, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rui","family":"Zhou","sequence":"additional","affiliation":[{"name":"Swinburne University of Technology, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kewen","family":"Liao","sequence":"additional","affiliation":[{"name":"Australian Catholic University, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiajie","family":"Xu","sequence":"additional","affiliation":[{"name":"Soochow University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianxin","family":"Li","sequence":"additional","affiliation":[{"name":"Deakin University, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,3,5]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Approximation Algorithms for Combinatorial Optimization: Third International Workshop, APPROX 2000 Saarbr\u00fccken, Germany, September 5--8, 2000 Proceedings. Springer, 84--95","author":"Charikar Moses","year":"2003","unstructured":"Moses Charikar. 2003. Greedy approximation algorithms for finding dense components in a graph. In Approximation Algorithms for Combinatorial Optimization: Third International Workshop, APPROX 2000 Saarbr\u00fccken, Germany, September 5--8, 2000 Proceedings. Springer, 84--95."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","unstructured":"Chandra Chekuri Kent Quanrud and Manuel R. Torres. [n. d.]. Densest Subgraph: Supermodularity Iterative Peeling and Flow. 1531--1555. 10.1137\/1.9781611977073.64","DOI":"10.1137\/1.9781611977073.64"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00017"},{"key":"e_1_2_1_4_1","volume-title":"Technical Report: Densest Multipartite Subgraph Search in Heterogeneous Information Networks. https:\/\/github.com\/S1mpleCod\/DPPS","author":"Chen Lu","year":"2023","unstructured":"Lu Chen, Chengfei Liu, Rui Zhou, Kewen Liao, Jiajie Xu, and Jianxin Li. 2023. Technical Report: Densest Multipartite Subgraph Search in Heterogeneous Information Networks. https:\/\/github.com\/S1mpleCod\/DPPS"},{"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.1006\/jagm.2001.1199"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476258"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380756"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342645"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218003"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.2987019"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.01.010"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00072"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401969"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551795"},{"key":"e_1_2_1_17_1","unstructured":"Ravi Kannan and V. Vinay. 1999. Analyzing the structure of large graphs. In manuscript."},{"key":"e_1_2_1_18_1","unstructured":"librahu. 2019. HIN-Datasets-for-Recommendation-and-Network-Embedding. https:\/\/github.com\/librahu\/HIN-Datasets-for-Recommendation-and-Network-Embedding"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313522"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00072"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397234"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517837"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/IJCNN55064.2022.9892291"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3510548.3519368"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384327"},{"key":"e_1_2_1_26_1","volume-title":"Fractional programming. European journal of operational research 12, 4","author":"Schaible Siegfried","year":"1983","unstructured":"Siegfried Schaible and Toshidide Ibaraki. 1983. Fractional programming. European journal of operational research 12, 4 (1983), 325--338."},{"key":"e_1_2_1_27_1","unstructured":"Dhara Shah Sushil Prasad and Danial Aghajarian. 2019. Finding densest subgraph in a bi-partite graph. (2019)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.2297920"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","unstructured":"Charalampos Tsourakakis. 2015. The K-Clique Densest Subgraph Problem. In Proceedings of the 24th International Conference on World Wide Web (Florence Italy) (WWW '15). International World Wide Web Conferences Steering Committee Republic and Canton of Geneva CHE 1122--1132. 10.1145\/2736277.2741098","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339497"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00063"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00083"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517847"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407846"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3636218.3636226","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T17:06:14Z","timestamp":1709658374000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3636218.3636226"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["10.14778\/3636218.3636226"],"URL":"https:\/\/doi.org\/10.14778\/3636218.3636226","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,12]]},"assertion":[{"value":"2024-03-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}