Timezone: »

 
Poster
Graph Neural Network Bandits
Parnian Kassraie · Andreas Krause · Ilija Bogunovic

Wed Nov 30 02:00 PM -- 04:00 PM (PST) @ Hall J #243
in Poster Session 4 »
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. Perhaps surprisingly, even though 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.
Keywords: graph neural networks · regret bounds · Bandit optimization · Kernels
[ Paper]  [ Slides]  [ Poster]  [ OpenReview] 

Author Information

Parnian Kassraie (ETH Zurich)
Parnian Kassraie

I am a Ph.D. student at the Department of Computer Science at ETH Zurich, advised by [Andreas Krause](https://las.inf.ethz.ch/krausea). I am part of the [Institute for Machine Learning](https://ml.inf.ethz.ch/) and associated with the [ETH AI Center](https://ai.ethz.ch/). The primary focus of my research is in the foundations of Reinforcement Learning. I joined ETH as a Direct Doctorate student and in Spring 2021 completed my M.Sc. under the supervision of Andreas Krause and [Fanny Yang](http://fanny-yang.de/), with a thesis on Contextual Neural Bandits. Before ETH, I studied at the Sharif University of Technology where I earned a dual B.Sc. in Electrical Engineering and Computer Science.

Andreas Krause (ETH Zurich)
Ilija Bogunovic (University College London (UCL))

More from the Same Authors