EUVIMEDEUVIMED entdecken
Crossref

Bound-Tightened Densest Subgraph Discovery on GPU

Wajid Manzoor, Ke Fan, Muhammad Shaheer, Guimu Guo

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →