Accelerating k-Core Decomposition by a GPU


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

39th IEEE International Conference on Data Engineering, ICDE 2023, California, United States Of America, 3 - 07 April 2023, vol.2023-April, pp.1818-1831 identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 2023-April
  • Doi Number: 10.1109/icde55515.2023.00142
  • City: California
  • Country: United States Of America
  • Page Numbers: pp.1818-1831
  • Keywords: GPU, graph, h-index, k-core
  • TED University Affiliated: Yes

Abstract

The k-core of a graph is the largest induced sub-graph 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: (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, 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. Our source code is released at https://github.com/akhlaqueak/KCoreGPU.