Bandit Samplers for Training Graph Neural Networks

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

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 changing during the training and not known a priori, but only 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.

Introduction

Graph Neural Networks (GNNs) are powerful tools for graph-structured data, but they suffer from a significant scaling issue known as "neighbor explosion." To compute a single node's representation, the model must aggregate information from its neighbors, whose own representations depend on their neighbors, and so on. In dense or deep graphs, this leads to an exponential growth in the number of nodes processed, quickly exhausting memory and compute resources.

Researchers typically address this by sampling a subset of neighbors. Ideally, one would use importance sampling to pick the most informative neighbors and minimize variance. However, a neighbor's "importance" depends on hidden features and model weights that change constantly during training. Because the full neighborhood isn't observable at every step, calculating the optimal sampling distribution in real-time is computationally impossible.

Methodology: Bandit Samplers

This paper proposes a novel perspective: Bandit Samplers. Instead of relying on static heuristics (like node degree), the authors formulate neighbor sampling as an adversarial multi-armed bandit (MAB) problem. This allows the sampler to adaptively learn the best distribution as the model evolves.

The Bandit Framework

  1. Arms: Each neighbor of a node is treated as an "arm."
  2. Actions: The sampler chooses which neighbors to "pull" (sample).
  3. Rewards: The reward is defined as the negative derivative of the sampling variance. Neighbors that help reduce the model's prediction error receive higher rewards.
  4. Exploration vs. Exploitation: The sampler must balance picking neighbors known to be useful (exploit) with checking others to see if they have become more relevant as weights shift (explore).

Two specific algorithms are introduced: GNN-BS, based on the classic EXP3 algorithm for sequential sampling, and GNN-BS.M, which uses EXP3.M and Dependent Rounding (DepRound) to sample a combinatorial set of $k$ neighbors simultaneously.

Key Results and Evaluation

The Bandit Samplers were evaluated on standard benchmarks including Cora, Pubmed, PPI, Reddit, and Flickr.

Convergence and Accuracy

Bandit Samplers consistently outperformed state-of-the-art methods like GraphSAGE, FastGCN, and LADIES. As shown in the convergence plots, the bandit approach reaches higher accuracy levels in fewer epochs and less wall-clock time.

Convergence curves showing Micro F1 on validation vs. Epoch for various datasets.

On the complex PPI dataset, GCN-BS achieved a Micro F1 score of 0.905, significantly higher than FastGCN (0.502) and S-GCN (0.744). The table below summarizes the performance gains across standard GCN architectures.

Comparison of Micro F1 scores for GCN-based methods across five benchmark datasets.

Universal Applicability

A major advantage of this approach is its universality. While previous importance-sampling methods were limited to GCNs, Bandit Samplers work effectively for Attentive GNNs (GAT), where weights are learned and even harder to sample optimally. The authors also reported top-tier performance on the OGB-proteins leaderboard at the time of submission.

Conclusion

By treating neighbor sampling as an adversarial bandit problem, this work provides a robust, adaptive framework for training GNNs. The method offers a theoretical guarantee, asymptotically approaching optimal variance within a factor of 3, while delivering superior empirical performance and faster convergence across diverse datasets. Future research may focus on extending these node-wise strategies to layer-wise sampling to further enhance scalability.

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 changing during the training and not known a priori, but only 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