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:
- 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.
- 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).
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.
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