{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T19:06:44Z","timestamp":1779131204302,"version":"3.51.4"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["2245792"],"award-info":[{"award-number":["2245792"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,18]]},"abstract":"<jats:p>\n                    The densest subgraph discovery (DSD) problem is a fundamental task in graph mining with applications in social networks, bioinformatics, graph databases, and systems engineering. Given a graph\n                    <jats:italic toggle=\"yes\">G<\/jats:italic>\n                    = (\n                    <jats:italic toggle=\"yes\">V, E<\/jats:italic>\n                    ) and an integer\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    ? 2, the goal is to find a vertex subset\n                    <jats:italic toggle=\"yes\">D<\/jats:italic>\n                    ?\n                    <jats:italic toggle=\"yes\">V<\/jats:italic>\n                    whose induced subgraph\n                    <jats:italic toggle=\"yes\">G<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">D<\/jats:italic>\n                    ) maximizes the\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -clique density, defined as the number of\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -cliques per vertex. Larger values of\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    capture higher-order connectivity patterns beyond edges, enabling the discovery of more cohesive structures. We present a GPU-accelerated framework that integrates a warp-level\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -clique enumeration algorithm along with clique-core\u2013based pruning and edge pruning techniques to reduce the search space, followed by parallel connected component decomposition to split the pruned graph into independent smaller subproblems. The exact solution is then obtained by formulating DSD on each connected component as a maximum flow problem and solving it using a highly parallel vertex-centric push\u2013relabel algorithm, enhanced with tight upper and lower density bounds and compact, GPU-friendly data structures. Experiments on a diverse set of real-world and synthetic graphs show substantial speedups over the state-of-the-art CPU implementation, while producing identical solutions.\n                  <\/jats:p>","DOI":"10.1145\/3802023","type":"journal-article","created":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:19:16Z","timestamp":1779128356000},"page":"1-25","source":"Crossref","is-referenced-by-count":0,"title":["Bound-Tightened Densest Subgraph Discovery on GPU"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-7073-7257","authenticated-orcid":false,"given":"Wajid","family":"Manzoor","sequence":"first","affiliation":[{"name":"Rowan University, Glassboro, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9563-6129","authenticated-orcid":false,"given":"Ke","family":"Fan","sequence":"additional","affiliation":[{"name":"Temple University, Philadelphia, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-7188-3603","authenticated-orcid":false,"given":"Muhammad","family":"Shaheer","sequence":"additional","affiliation":[{"name":"Rowan University, Glassboro, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3573-7446","authenticated-orcid":false,"given":"Guimu","family":"Guo","sequence":"additional","affiliation":[{"name":"Rowan University, Glassboro, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jnca.2015.11.016"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/3705829.3705831"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.66"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970240309X"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342645"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl244"},{"key":"e_1_2_1_9_1","unstructured":"Andrew V. Goldberg. 1984. Finding a Maximum Density Subgraph. Technical Report UCB\/CSD-84-171. University of California Berkeley."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"key":"e_1_2_1_11_1","volume-title":"Inequalities (2 ed.)","author":"Hardy Godfrey H","unstructured":"Godfrey H Hardy, John E Littlewood, and George P\u00f3lya. 1952. Inequalities (2 ed.). Cambridge University Press."},{"key":"e_1_2_1_12_1","unstructured":"Kuan-Hsun Hsieh et al. 2024. Engineering a Workload-Balanced Push-Relabel Algorithm for Massive Graphs on GPUs. arXiv preprint arXiv:2404.00270 (2024)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_49"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3653298"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability","volume":"561","author":"R\u00e9nyi Alfr\u00e9d","year":"1961","unstructured":"Alfr\u00e9d R\u00e9nyi. 1961. On measures of entropy and information. Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics (1961), 547-561."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12683-3_31"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2016.7752211"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2010.5470882"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741130"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487581"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.110"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448930"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802023","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:27:03Z","timestamp":1779128823000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3802023"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,18]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5,18]]}},"alternative-id":["10.1145\/3802023"],"URL":"https:\/\/doi.org\/10.1145\/3802023","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,18]]}}}