FlowWalker: A Memory-Efficient and High-Performance GPU-Based Dynamic Graph Random Walk Framework
Proceedings of the VLDB Endowment · 2024-04 · 17 (8) · 1788-1801
DOI: 10.14778/3659437.3659438 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 31.05.2024. Verfasst von Junyi Mei und 11 weiteren Autor:innen. Die Arbeit wurde bisher 13-mal zitiert (Crossref) und nennt 53 Literaturangaben.
Abstract (Originalsprache)
Dynamic graph random walk (DGRW) emerges as a practical tool for capturing structural relations within a graph. Effectively executing DGRW on GPU presents certain challenges. First, existing sampling methods demand a pre-processing buffer, causing substantial space complexity. Moreover, the power-law distribution of graph vertex degrees introduces workload imbalance issues, rendering DGRW embarrassed to parallelize. In this paper, we propose FlowWalker, a GPU-based dynamic graph random walk framework. FlowWalker implements an efficient parallel sampling method to fully exploit the GPU parallelism and reduce space complexity. Moreover, it employs a sampler-centric paradigm alongside a dynamic scheduling strategy to handle the huge amounts of walking queries. FlowWalker stands as a memory-efficient framework that requires no auxiliary data structures in GPU global memory. We examine the performance of FlowWalker extensively on ten datasets, and experiment results show that FlowWalker achieves up to 752.2×, 72.1×, and 16.4× speedup compared with existing CPU, GPU, and FPGA random walk frameworks, respectively. Case study shows that FlowWalker diminishes random walk time from 35% to 3% in a pipeline of ByteDance friend recommendation GNN training.
Zitieren
APA
Mei, J., Sun, S., Li, C., Xu, C., Chen, C., Liu, Y., Wang, J., Zhao, C., Hou, X., Guo, M., He, B., & Cong, X. (2024). FlowWalker: A Memory-Efficient and High-Performance GPU-Based Dynamic Graph Random Walk Framework. Proceedings of the VLDB Endowment, 17(8), 1788-1801. https://doi.org/10.14778/3659437.3659438
Vancouver
Mei J, Sun S, Li C, Xu C, Chen C, Liu Y, et al. FlowWalker: A Memory-Efficient and High-Performance GPU-Based Dynamic Graph Random Walk Framework. Proceedings of the VLDB Endowment. 2024;17(8):1788-1801. doi:10.14778/3659437.3659438
BibTeX
@article{Mei2024,
author = {Mei, Junyi and Sun, Shixuan and Li, Chao and Xu, Cheng and Chen, Cheng and Liu, Yibo and Wang, Jing and Zhao, Cheng and Hou, Xiaofeng and Guo, Minyi and He, Bingsheng and Cong, Xiaoliang},
title = {FlowWalker: A Memory-Efficient and High-Performance GPU-Based Dynamic Graph Random Walk Framework},
journal = {Proceedings of the VLDB Endowment},
year = {2024},
volume = {17},
number = {8},
pages = {1788--1801},
doi = {10.14778/3659437.3659438}
}
EUVIMED