  Graph Neural Networks (GNNs) have received significant attention recently,
but training them at a large scale remains a challenge. Mini-batch training
coupled with sampling is used to alleviate this challenge. However, existing
approaches either suffer from the neighborhood explosion phenomenon or have
poor performance. To address these issues, we propose a new sampling algorithm
called LAyer-neighBOR sampling (LABOR). It is designed to be a direct
replacement for Neighbor Sampling (NS) with the same fanout hyperparameter
while sampling up to 7 times fewer vertices, without sacrificing quality. By
design, the variance of the estimator of each vertex matches NS from the point
of view of a single vertex. Moreover, under the same vertex sampling budget
constraints, LABOR converges faster than existing layer sampling approaches and
can use up to 112 times larger batch sizes compared to NS.
