PTWalker: Cache-Efficient Random Walks via Alternating Dual-Subgraph Walker Updating.

Random walks on graphs are essential for various applications such as network analysis, recommendation systems, and graph embedding. However, existing frameworks for random walks face challenges in efficiently managing and updating walkers, especially for applications involving random walks with probabilistic termination (RWPT). These challenges arise from inefficient walker updating due to the random distribution of edge cuts in current graph partition strategies and the high management and storage costs associated with the walker array-based management strategy. This paper presents a novel cache-efficient random walk framework called PTWalker, specifically designed for RWPT. Unlike existing frameworks that update only one walk step per iteration, PTWalker sets out to have the majority of walkers updated at least two steps per iteration. This is achieved through an inventive alternating dual-subgraph walk updating scheme, which involves dividing the graph into two sets of subgraphs with maximized edge cuts between them. These subgraph sets are then loaded into the cache for walk updating in an alternating manner, prompting most walkers to transition to the other subgraph set and update additional steps. Besides, a thread-level walker pool management strategy is designed to reduce management and storage costs for walkers. Experimental results demonstrate that PTWalker outperforms state-of-the-art random walk systems, achieving a speedup ranging from 0.18× to 8.65×.

Recommended citation: Shuai Lin, Rui Wang, Zaigui zhang, Long Deng, Wenzhe Zhu, Yongkun Li, Yinlong Xu. "PTWalker: Cache-Efficient Random Walks via Alternating Dual-Subgraph Walker Updating." The 54th International Conference on Parallel Processing (ICPP 2025), San Diego, CA, September 8 -11, 2025.