EUVIMEDEUVIMED entdecken
Crossref

FlowWalker: A Memory-Efficient and High-Performance GPU-Based Dynamic Graph Random Walk Framework

Junyi Mei, Shixuan Sun, Chao Li, Cheng Xu, Cheng Chen, Yibo Liu, Jing Wang, Cheng Zhao, Xiaofeng Hou, Minyi Guo, Bingsheng He, Xiaoliang Cong

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →