# Graph Neural Network Bandits

arXiv: https://arxiv.org/abs/2207.06456 · HTML: https://mlsanity.com/paper/2207.06456/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 53 references that are in the map.
- First posted on arXiv 13 Jul 2022.

## Builds on (most cited first, 30 of 30)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Automatic chemical design using a data-driven continuous representation of molecules](https://mlsanity.com/paper/1610.02415/) (2016)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Junction Tree Variational Autoencoder for Molecular Graph Generation](https://mlsanity.com/paper/1802.04364/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels](https://mlsanity.com/paper/1905.13192/) (2019)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Neural Tangents: Fast and Easy Infinite Neural Networks in Python](https://mlsanity.com/paper/1912.02803/) (2019)
- [High Dimensional Bayesian Optimisation and Bandits via Additive Models](https://mlsanity.com/paper/1503.01673/) (2015)
- [Neural Thompson Sampling](https://mlsanity.com/paper/2010.00827/) (2020)
- [Accelerating Bayesian Optimization for Biological Sequence Design with Denoising Autoencoders](https://mlsanity.com/paper/2203.12742/) (2022)
- [Learning with invariances in random features and kernel models](https://mlsanity.com/paper/2102.13219/) (2021)
- [Deep Equals Shallow for ReLU Networks in Kernel Regimes](https://mlsanity.com/paper/2009.14397/) (2020)
- [ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendations](https://mlsanity.com/paper/1908.01425/) (2019)
- [High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groups](https://mlsanity.com/paper/1802.07028/) (2018)
- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Information-Theoretic Confidence Bounds for Reinforcement Learning](https://mlsanity.com/paper/1911.09724/) (2019)
- [Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration](https://mlsanity.com/paper/1304.5350/) (2013)
- [Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation](https://mlsanity.com/paper/1610.07379/) (2016)
- [Neural Contextual Bandits without Regret](https://mlsanity.com/paper/2107.03144/) (2021)
- [Batched Neural Bandits](https://mlsanity.com/paper/2102.13028/) (2021)
- [A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits](https://mlsanity.com/paper/2202.01850/) (2022)

## Built on by (most cited first, 10 of 10)

- [Use Your INSTINCT: INSTruction optimization for LLMs usIng Neural bandits Coupled with Transformers](https://mlsanity.com/paper/2310.02905/) (2023)
- [Generalizing Bayesian Optimization with Decision-theoretic Entropies](https://mlsanity.com/paper/2210.01383/) (2022)
- [PolicySim: An LLM-Based Agent Social Simulation Sandbox for Proactive Policy Optimization](https://mlsanity.com/paper/2603.19649/) (2026)
- [Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits](https://mlsanity.com/paper/2502.19006/) (2025)
- [Neural Exploitation and Exploration of Contextual Bandits](https://mlsanity.com/paper/2305.03784/) (2023)
- [Sample-efficient Bayesian Optimisation Using Known Invariances](https://mlsanity.com/paper/2410.16972/) (2024)
- [Online Clustering of Dueling Bandits](https://mlsanity.com/paper/2502.02079/) (2025)
- [Neural-BO: A Black-box Optimization Algorithm using Deep Neural Networks](https://mlsanity.com/paper/2303.01682/) (2023)
- [Online Network Source Optimization with Graph-Kernel MAB](https://mlsanity.com/paper/2307.03641/) (2023)
- [Graph Neural Thompson Sampling](https://mlsanity.com/paper/2406.10686/) (2024)

## Abstract (arXiv)

We consider the bandit optimization problem with the reward function defined over graph-structured data. This problem has important applications in molecule design and drug discovery, where the reward is naturally invariant to graph permutations. The key challenges in this setting are scaling to large domains, and to graphs with many nodes. We resolve these challenges by embedding the permutation invariance into our model. In particular, we show that graph neural networks (GNNs) can be used to estimate the reward function, assuming it resides in the Reproducing Kernel Hilbert Space of a permutation-invariant additive kernel. By establishing a novel connection between such kernels and the graph neural tangent kernel (GNTK), we introduce the first GNN confidence bound and use it to design a phased-elimination algorithm with sublinear regret. Our regret bound depends on the GNTK's maximum information gain, which we also provide a bound for. While the reward function depends on all N node features, our guarantees are independent of the number of graph nodes N. Empirically, our approach exhibits competitive performance and scales well on graph-structured domains.