{"ID":2834786,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.00705","arxiv_id":"2512.00705","title":"FlexiWalker: Extensible GPU Framework for Efficient Dynamic Random Walks with Runtime Adaptation","abstract":"Dynamic random walks are fundamental to various graph analysis applications, offering advantages by adapting to evolving graph properties. Their runtime-dependent transition probabilities break down the pre-computation strategy that underpins most existing CPU and GPU static random walk optimizations. This leaves practitioners suffering from suboptimal frameworks and having to write hand-tuned kernels that do not adapt to workload diversity. To handle this issue, we present FlexiWalker, the first GPU framework that delivers efficient, workload-generic support for dynamic random walks. Our design-space study shows that rejection sampling and reservoir sampling are more suitable than other sampling techniques under massive parallelism. Thus, we devise (i) new high-performance kernels for them that eliminate global reductions, redundant memory accesses, and random-number generation. Given the necessity of choosing the best-fitting sampling strategy at runtime, we adopt (ii) a lightweight first-order cost model that selects the faster kernel per node at runtime. To enhance usability, we introduce (iii) a compile-time component that automatically specializes user-supplied walk logic into optimized building blocks. On various dynamic random walk workloads with real-world graphs, FlexiWalker outperforms the best published CPU/GPU baselines by geometric means of 73.44x and 5.91x, respectively, while successfully executing workloads that prior systems cannot support. We open-source FlexiWalker in https://github.com/AIS-SNU/FlexiWalker.","short_abstract":"Dynamic random walks are fundamental to various graph analysis applications, offering advantages by adapting to evolving graph properties. Their runtime-dependent transition probabilities break down the pre-computation strategy that underpins most existing CPU and GPU static random walk optimizations. This leaves pract...","url_abs":"https://arxiv.org/abs/2512.00705","url_pdf":"https://arxiv.org/pdf/2512.00705v1","authors":"[\"Seongyeon Park\",\"Jaeyong Song\",\"Changmin Shin\",\"Sukjin Kim\",\"Junguk Hong\",\"Jinho Lee\"]","published":"2025-11-30T02:52:16Z","proceeding":"cs.DC","tasks":"[\"cs.DC\"]","methods":"[]","has_code":false,"code_links":[{"ID":606443,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_id":2834786,"paper_url":"https://arxiv.org/abs/2512.00705","paper_title":"FlexiWalker: Extensible GPU Framework for Efficient Dynamic Random Walks with Runtime Adaptation","repo_url":"https://github.com/AIS-SNU/FlexiWalker","is_official":false,"mentioned_in_paper":false,"mentioned_in_github":true,"github_stars":0}]}