Large-scale graph label propagation on GPUs

• Main Authors: YE, Chang, LI, Yuchen, HE, Bingsheng, LI, Zhao, SUN, Jianling
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2023
• Subjects: GPU computing; graph; label propagation; Databases and Information Systems; Numerical Analysis and Scientific Computing
• Online Access: https://ink.library.smu.edu.sg/sis_research/8468; https://ink.library.smu.edu.sg/context/sis_research/article/9471/viewcontent/Large_scaleGraphLabel_av.pdf
• Institution: Singapore Management University

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.