Accelerating k-Core Decomposition on a GPU

Ahmad A., Yuan L., Yan D., Guo G., Chen J., Zhang C.

International Conference on Data Engineering, California, United States Of America, 3 - 07 April 2023, pp.1-12

  • Publication Type: Conference Paper / Full Text
  • City: California
  • Country: United States Of America
  • Page Numbers: pp.1-12
  • TED University Affiliated: Yes


The k-core of a graph is the largest induced

subgraph with minimum degree k. The problem of k-core

decomposition finds the k-cores of a graph for all valid values

of k, and it has many applications such as network analysis,

computational biology and graph visualization. Currently, there

are two types of parallel algorithms for k-core decomposition on

a big graph: (1) degree-based vertex peeling, and (2) iterative h-

index refinement. There is, however, few studies on accelerating

k-core decomposition using GPU. In this paper, we propose

a highly optimized peeling algorithm on a GPU for k-core

decomposition, and compare it with possible implementations

on top of think-like-a-vertex graph-parallel GPU systems as well

as existing serial and parallel k-core decomposition algorithms

on CPUs. Extensive experiments show that our GPU algorithm

is the overall winner in both time and space.