AdaptiveCore: Adaptive Parallel Core Decomposition Framework

doi:10.1109/TC.2025.3646191

AdaptiveCore: Adaptive Parallel Core Decomposition Framework

2025-12-19

0

PRE

AI

DOI：10.1109/TC.2025.3646191

Original

Original request for help

Save

Abstract

En 中文

Core decomposition is a widely used hierarchical analysis algorithm for large-scale graphs. It achieves this decomposition by iteratively peeling the vertices along with their adjacency edges off into different hierarchies. With the timeliness requirements of modern applications, many researchers have introduced accelerators, particularly GPUs, to improve the computational efficiency of graph algorithms. However, the empty, sparse, and numerous hierarchies in large graphs lead to inefficient computation and parallelism, not only including unnecessary searching for the hierarchy’s vertices, but also significant thread wastage when peeling off the adjacency edges of these vertices. In this paper, we propose an adaptive parallel framework for core decomposition, named <i>AdaptiveCore</i>. First, it improves vertex searching efficiency by adaptively skipping the empty hierarchies and reducing the search space. Moreover, it greatly improves thread utilization by adaptively allocating the available threads to peel off the adjacency edges. Comprehensive experiments show that, compared with the state-of-the-art works, the proposed framework achieves an average speedup of <inline-formula><tex-math notation="LaTeX">$7.1\times$</tex-math></inline-formula> on the GPU platform and up to <inline-formula><tex-math notation="LaTeX">$2.0\times$</tex-math></inline-formula> on the multi-core CPU platform.

Keywords:

Large-scale graph

parallel core decomposition

graph computing

GPU

AdaptiveCore: Adaptive Parallel Core Decomposition Framework

Abstract

Journal

Organization