Bound-Tightened Densest Subgraph Discovery on GPU
Proceedings of the ACM on Management of Data · 18.05.2026 · 4 (3) · 1-25
DOI: 10.1145/3802023 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Wajid Manzoor und 3 weiteren Autor:innen. Die Arbeit nennt 22 Literaturangaben. Gefördert von: NSF.
Abstract (Originalsprache)
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 G = ( V, E ) and an integer k ? 2, the goal is to find a vertex subset D ? V whose induced subgraph G ( D ) maximizes the k -clique density, defined as the number of k -cliques per vertex. Larger values of k 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 k -clique enumeration algorithm along with clique-core–based 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–relabel 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.
Förderung
- NSF
Zitieren
APA
Manzoor, W., Fan, K., Shaheer, M., & Guo, G. (2026). Bound-Tightened Densest Subgraph Discovery on GPU. Proceedings of the ACM on Management of Data, 4(3), 1-25. https://doi.org/10.1145/3802023
Vancouver
Manzoor W, Fan K, Shaheer M, Guo G. Bound-Tightened Densest Subgraph Discovery on GPU. Proceedings of the ACM on Management of Data. 2026;4(3):1-25. doi:10.1145/3802023
BibTeX
@article{Manzoor2026,
author = {Manzoor, Wajid and Fan, Ke and Shaheer, Muhammad and Guo, Guimu},
title = {Bound-Tightened Densest Subgraph Discovery on GPU},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {3},
pages = {1--25},
doi = {10.1145/3802023}
}
EUVIMED