Bandit Samplers for Training Graph Neural Networks

Ziqi Liu, Zhengwei Wu, Zhiqiang Zhang, Jun Zhou, Shuang Yang, Le Song, Yuan Qi

Introduction

Training Graph Neural Networks (GNNs) on large graphs is computationally expensive due to the "neighbor explosion" problem. Computing the representation of a single node requires aggregating information from its neighbors, its neighbors' neighbors, and so on. In dense graphs, this leads to massive memory and computation costs.

To mitigate this, researchers use sampling to pick only a subset of neighbors. The gold standard is importance sampling, which minimizes the variance of gradient estimates. However, calculating the mathematically optimal sampling distribution requires knowing the hidden embeddings and attention weights of all neighbors beforehand. This creates a catch-22: you must process all neighbors to know how to sample a few of them. Furthermore, in models like Graph Attention Networks (GATs), these weights are learned and constantly changing during training. Existing methods settle for suboptimal approximations that assume fixed weights, making them ineffective for attentive GNNs.

This paper introduces a novel approach that frames neighborhood sampling as an adversarial multi-armed bandit problem, allowing the sampler to dynamically learn an optimal, variance-reduced sampling distribution during training.

Methodology: Sampling as a Bandit Problem

The authors reframe the search for the optimal sampling distribution as an adversarial bandit problem. Instead of calculating the intractable optimal distribution at every step, they maintain a nonparametric estimate of the sampler and update it based on partial feedback.

  • Arms: The neighbors available to sample.
  • Reward: The negative derivative of the sampling variance (i.e., how much a sampled neighbor helps reduce the variance of the estimator).
  • Exploration vs. Exploitation: The algorithm balances exploring new neighbors to estimate their variance contribution and exploiting neighbors known to minimize variance.

They propose two specific algorithms:

  1. GNN-BS (Multi-Armed Bandit): Uses the EXP3 algorithm to pick one neighbor at a time, repeating the process $k$ times to build a sample.
  2. GNN-BS.M (MAB with Multiple Plays): A more mathematically rigorous version using EXP3.M and dependent rounding (DepRound) to select a combinatorial set of $k$ distinct neighbors all at once.

Crucially, they introduce a mathematical workaround to approximate normalized attention weights using only the sampled subset, allowing the bandit framework to work seamlessly with attentive GNNs.

Key Insights

  • The optimal sampler is a moving target: Because node embeddings and attention weights update at every training step, the optimal sampling distribution is constantly shifting. Adversarial bandits are perfectly suited for this scenario because they do not assume a fixed reward distribution.
  • Partial knowledge is enough: You don't need to evaluate every neighbor to improve your sampling. By treating variance reduction as a "reward," the model iteratively pushes its sampling distribution toward the optimum using only the neighbors it actually sampled.
  • Theoretical Guarantees: The authors mathematically prove that the variance of their bandit sampler asymptotically approaches the true, intractable optimal variance within a factor of 3.

Key Results

The authors evaluate their methods on five standard benchmark graph datasets: Cora, Pubmed, PPI, Reddit, and Flickr.

Superior Accuracy on GCNs

On a standard GCN architecture, GNN-BS outperformed state-of-the-art sampling methods (GraphSAGE, FastGCN, GraphSAINT, etc.). For example, on the dense PPI dataset, GCN-BS achieved a Micro F1 score of 0.905, significantly outperforming GraphSAINT (0.787) and FastGCN (0.502).

Micro F1 scores for GCN models across datasets

Unlocking Attentive GNNs

When applied to GAT architectures, the bandit samplers (GAT-BS and GAT-BS.M) significantly outperformed existing methods that struggle with learned weights. On PPI, GAT-BS scored 0.841 compared to GraphSAINT-GAT's 0.789.

Faster Convergence

Empirical plots show that the bandit samplers converge in fewer epochs and with much tighter variance bands than uniform or fixed importance sampling approaches.

Validation Micro F1 over epochs showing faster convergence and tighter variance

Limitations and Future Work

  • Node-wise vs. Layer-wise: The current mathematical derivation is based on node-wise sampling (sampling neighbors for each specific node). Extending this framework to layer-wise sampling (sampling a pool of nodes for the entire layer at once) is left as future work.
  • Bandit Frameworks: While the authors utilized an adversarial bandit setting, exploring other bandit formulations could yield further improvements.
  • Theoretical Rigor of GNN-BS: Applying standard MAB (GNN-BS) to select $k$ neighbors involves sampling with replacement, which is less theoretically rigorous than GNN-BS.M. However, both perform very similarly in practice.

Summary updated

Abstract

Several sampling algorithms with variance reduction have been proposed for accelerating the training of Graph Convolution Networks (GCNs). However, due to the intractable computation of optimal sampling distribution, these sampling algorithms are suboptimal for GCNs and are not applicable to more general graph neural networks (GNNs) where the message aggregator contains learned weights rather than fixed weights, such as Graph Attention Networks (GAT). The fundamental reason is that the embeddings of the neighbors or learned weights involved in the optimal sampling distribution are \emph{changing} during the training and \emph{not known a priori}, but only \emph{partially observed} when sampled, thus making the derivation of an optimal variance reduced samplers non-trivial. In this paper, we formulate the optimization of the sampling variance as an adversary bandit problem, where the rewards are related to the node embeddings and learned weights, and can vary constantly. Thus a good sampler needs to acquire variance information about more neighbors (exploration) while at the same time optimizing the immediate sampling variance (exploit). We theoretically show that our algorithm asymptotically approaches the optimal variance within a factor of 3. We show the efficiency and effectiveness of our approach on multiple datasets.
BibTeX
@inproceedings{liu2020bandit,
  author = {Ziqi Liu and Zhengwei Wu and Zhiqiang Zhang and Jun Zhou and Shuang Yang and Le Song and Yuan Qi},
  title = {{Bandit Samplers for Training Graph Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=AgL2xDbrQfH},
}
Figure