Graph Neural Network Bandits

Advanced search
Browse by:

Department | Year

UCL Theses | Latest

Deposit your research

Graph Neural Network Bandits

Kassraie, Parnian; Krause, Andreas; Bogunovic, Ilija; (2022) Graph Neural Network Bandits. In: Koyejo, S and Mohamed, S and Agarwal, A and Belgrave, D and Cho, K and Oh, A, (eds.) Advances in Neural Information Processing Systems 35, NEURIPS 2022. Neural Information Processing Systems (NIPS) Green open access

Preview

PDF
2207.06456v2.pdf - Accepted Version
Download (2MB) | Preview

Abstract

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* 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.

Type:	Proceedings paper
Title:	Graph Neural Network Bandits
Event:	36th Conference on Neural Information Processing Systems (NeurIPS)
Location:	ELECTR NETWORK
Dates:	28 Nov 2022 - 9 Dec 2022
Open access status:	An open access version is available from UCL Discovery
Publisher version:	https://openreview.net/forum?id=BWa5IUE3L4
Language:	English
Additional information:	This version is the version of record. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords:	Science & Technology, Technology, Computer Science, Artificial Intelligence, Computer Science, Information Systems, Computer Science
UCL classification:	UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Electronic and Electrical Eng
URI:	https://discovery.ucl.ac.uk/id/eprint/10198816