EUVIMEDObjevte EUVIMED
Crossref

Bound-Tightened Densest Subgraph Discovery on GPU

Wajid Manzoor, Ke Fan, Muhammad Shaheer, Guimu Guo

Proceedings of the ACM on Management of Data · 2026-05-18 · 4 (3) · 1-25

DOI: 10.1145/3802023 ↗

At a glance

Journal article in Proceedings of the ACM on Management of Data, published online on 2026-05-18. Written by Wajid Manzoor and 3 co-authors. 22 references. Funded by: NSF.

AbstraktBibliografické údajeCiteRelated studies

Abstract (original language)

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.

Funding

  • NSF

Cite

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}
}
Start for free →