Publication Type

Journal Article

Version

acceptedVersion

Publication Date

11-2023

Abstract

Graph label propagation (LP) is a core component in many downstream applications such as fraud detection, recommendation and image segmentation. In this paper, we propose GLP, a GPU-based framework to enable efficient LP processing on large-scale graphs. By investigating the data processing pipeline in a large e-commerce platform, we have identified two key challenges on integrating GPU-accelerated LP processing to the pipeline: (1) programmability for evolving application logics; (2) demand for real-time performance. Motivated by these challenges, we offer a set of expressive APIs that data engineers can customize and deploy efficient LP algorithms on GPUs with ease. To achieve better performance, we propose novel GPU-centric optimizations by leveraging the community as well as power-law properties of large graphs. Further, we significantly reduce the expensive data transfer cost between CPUs and GPUs by enabling LP processing on compressed graphs. Extensive experiments have confirmed the effectiveness of our proposed approaches over the state-of-the-art GPU methods. Furthermore, our proposed solution supports a real billion-scale graph workload for fraud detection and achieves 13.2× speedup to the current in-house solution running on a high-end multicore machine with compressed graphs.

Keywords

GPU computing, graph, label propagation

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Research Areas

Data Science and Engineering

Publication

IEEE Transactions on Knowledge and Data Engineering

First Page

1

Last Page

14

ISSN

1041-4347

Identifier

10.1109/TKDE.2023.3336329

Publisher

Institute of Electrical and Electronics Engineers

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1109/TKDE.2023.3336329

Download

Share

COinS