  Graph neural networks (GNN) have recently emerged as a vehicle for applying
deep network architectures to graph and relational data. However, given the
increasing size of industrial datasets, in many practical situations the
message passing computations required for sharing information across GNN layers
are no longer scalable. Although various sampling methods have been introduced
to approximate full-graph training within a tractable budget, there remain
unresolved complications such as high variances and limited theoretical
guarantees. To address these issues, we build upon existing work and treat GNN
neighbor sampling as a multi-armed bandit problem but with a newly-designed
reward function that introduces some degree of bias designed to reduce variance
and avoid unstable, possibly-unbounded pay outs. And unlike prior bandit-GNN
use cases, the resulting policy leads to near-optimal regret while accounting
for the GNN training dynamics introduced by SGD. From a practical standpoint,
this translates into lower variance estimates and competitive or superior test
accuracy across several benchmarks.
