FenixWalk：面向异构架构的大规模动态图自适应采样
arXiv:2611.04683v1 公告类型：新 基础摘要：随机游走是图分析的基础，但在大型动态图上高效执行仍具挑战。现有方法需在采样效率、更新开销和内存消耗之间权衡。为吞吐量优化的采样结构往往带来显著的内存开销和高昂的维护成本，而轻量级方案在高度数顶点或权重分布偏斜时又可能面临较高的采样延迟。这些挑战在异构CPU-GPU平台上尤为突出：主机内存容量充足，但GPU内存限制了可从并行加速中获益的图数据量。我们提出了FenixWalk，一个面向大规模动态图的内存高效随机游走系统，将统一的原地采样与选择性GPU加速相结合。核心上，FenixWalk采用原地Fenwick表示，无需复制边级权重存储即可支持拒绝采样和逆变换采样。该表示使拒绝采样具备期望O(1)的权重查询时间，并支持O(log d)的前缀采样与更新。为高效利用异构硬件，FenixWalk将完整图及其采样结构保留在主机内存，同时将频繁重用的顶点本地采样器有选择地放置在GPU上。通过传输紧凑的游走器状态而非反复迁移图分区，该系统减少了跨设备通信，并有效利用了有限的GPU内存。在大型真实世界图及代表性随机游走工作负载上的实验表明，FenixWalk相较于现有随机游走系统实现了平均2.06倍至400.57倍的加速。