Accelerating Graph Sampling for Graph Machine Learning using GPUs
  Representation learning algorithms automatically learn the features of data.
Several representation learning algorithms for graph data, such as DeepWalk,
node2vec, and GraphSAGE, sample the graph to produce mini-batches that are
suitable for training a DNN. However, sampling time can be a significant
fraction of training time, and existing systems do not efficiently parallelize
sampling.
  Sampling is an embarrassingly parallel problem and may appear to lend itself
to GPU acceleration, but the irregularity of graphs makes it hard to use GPU
resources effectively. This paper presents NextDoor, a system designed to
effectively perform graph sampling on GPUs. NextDoor employs a new approach to
graph sampling that we call transit-parallelism, which allows load balancing
and caching of edges. NextDoor provides end-users with a high-level abstraction
for writing a variety of graph sampling algorithms. We implement several graph
sampling applications, and show that NextDoor runs them orders of magnitude
faster than existing systems.
