Bingo: Radix-based Bias Factorization for Random Walk on Dynamic Graphs

Abstract

Random walks are a primary means for extracting information from large-scale graphs. While most real-world graphs are inherently dynamic, state-of-the-art random walk engines failed to efficiently support such a critical use case. This paper takes the initiative to build a general random walk engine for dynamically changing graphs with two key principles: (i) This system should support both low-latency streaming updates and high-throughput batched updates. (ii) This system should achieve fast sampling speed while maintaining acceptable space consumption to support dynamic graph updates. Upholding both standards, we introduce Bingo, a GPU-based random walk engine for dynamically changing graphs. First, we propose a novel radix-based bias factorization algorithm to support constant time sampling complexity while supporting fast streaming updates. Second, we present a group-adaption design to reduce space consumption dramatically. Third, we incorporate GPU-aware designs to support high-throughput batched graph updates on massively parallel platforms. Together, Bingo outperforms existing efforts across various applications, settings, and datasets, achieving up to a 271.11x speedup compared to the state-of-the-art efforts.

17 pages, Published in EuroSys'25

References in corpus (8)

• A Comprehensive Survey on Graph Neural Networks
• DeepWalk: Online Learning of Social Representations
• Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks
• Random Walks: A Review of Algorithms and Applications
• ConsisRec: Enhancing GNN for Social Recommendation via Consistent Neighbor Aggregation
• C-SAW: A Framework for Graph Sampling and Random Walk on GPUs
• Scalable Graph Neural Network Training: The Case for Sampling
• LightRW: FPGA Accelerated Graph Dynamic Random Walks