C-SAW: a framework for graph sampling and random walk on GPUs

Many applications require to learn, mine, analyze and visualize large-scale graphs. These graphs are often too large to be addressed efficiently using conventional graph processing technologies. Fortunately, recent research efforts find out graph sampling and random walk, which significantly reduce the size of original graphs, can benefit the tasks of learning, mining, analyzing and visualizing large graphs by capturing the desirable graph properties. This paper introduces C-SAW, the first framework that accelerates Sampling and Random Walk framework on GPUs. Particularly, C-SAW makes three contributions: First, our framework provides a generic API which allows users to implement a wide range of sampling and random walk algorithms with ease. Second, offloading this framework on GPU, we introduce warp-centric parallel selection, and two novel optimizations for collision migration. Third, towards supporting graphs that exceed the GPU memory capacity, we introduce efficient data transfer optimizations for out-of-memory and multi-GPU sampling, such as workload-aware scheduling and batched multi-instance sampling. Taken together, our framework constantly outperforms the state of the art projects in addition to the capability of supporting a wide range of sampling and random walk algorithms. Bias criterion # of neighbors (NeighborSize) Per layer Per vertex 1 > 1 Constant Variable Unbiased Simple random walk, metropolis hasting random walk, random walk with Jump, random walk with restart Unbiased neighbor sampling Forest fire sampling, Snowball sampling Biased Static Biased random walk Layer sampling Biased neighbor sampling Dynamic Multi-dimensional random walk, Node2vec

TABLE I: The design space of traversal based sampling and random walk algorithms.

sampling and random walk algorithms. Taken together, C-SAW significantly outperforms the state of the art systems that support either part of sampling or random walk algorithms. The contributions of this paper are as follows:

• We propose a generic framework which allows end users to express a large family of sampling and random walk algorithms with ease (Section III).

• We implement efficient GPU sampling with novel techniques. Our techniques parallelize the vertex selection on GPUs, with efficient algorithm and system optimizations for vertex collision migration (Section IV).

• We propose asynchronous designs for sampling and random walk, which optimizes the data transfer efficiency for graphs that exceed the GPU memory capacity. We further scale C-SAW to multiple GPUs (Section V).