Densest Subgraph Discovery On The CPU

The Densest Subgraph Discovery (DSD) problem is a prevalent problem in the field of graph mining, aiming to find the cohesive subgraph. Given a graph �� = (��,��) and an integer �� ≥ 2, the goal is to find a vertex sub- set �� ⊆ �� whose induced subgraph �� (��) maximizes the ��-clique density, defined as the number of ��-cliques per vertex. Larger val- ues of �� capture higher-order connectivity patterns beyond edges, enabling the discovery of more cohesive structures. There have been many solutions to this problem. However, one avenue that other graph mining problems have gone down is parallel programming, which executes many commands simultaneously for more efficient programs. What we have done is applied parallel programming on the GPU to a DSD solution called CoreExact in a two-fold effort. This is done in hopes of both creating a more efficient solution to the DSD while also serving as further research and precedent for the efficacy of parallel programming using the GPU.