Bandit Samplers for Training Graph Neural Networks

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.

Cited by in corpus (8)

• Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification
• Sampling methods for efficient training of graph convolutional networks: A survey
• FairSample: Training Fair and Accurate Graph Convolutional Neural Networks Efficiently
• Graph Coordinates and Conventional Neural Networks -- An Alternative for Graph Neural Networks
• A Biased Graph Neural Network Sampler with Near-Optimal Regret
• Graph Belief Propagation Networks
• On the Importance of Sampling in Training GCNs: Tighter Analysis and Variance Reduction
• Global Neighbor Sampling for Mixed CPU-GPU Training on Giant Graphs