Graph Neural Network Bandits
Authors: Parnian Kassraie
Andreas Krause
Ilija Bogunovic
Venue: NeurIPS 2022 Accept (2022)
Keywords: Bandit optimization
Kernels
Graph Neural Networks
Regret bounds

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

Graph Neural Network Bandits
Parnian Kassraie ETH Zurich pkassraieGethz.cd
Andreas Krause ETH Zurich krauseaßethz.co ch
Ilija Bogunovic University College London i bogunovic@ucll ac
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 large domains, and 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 permutation-invarian additive kernel. By establishing novel connection between such kernels and the graph neural tangent kernel (GNTK), we introduce the first GNN confidence bound and use design thased-eliminationn 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 all N node features, guarantees are independent of the number of graph nodes N. Empirically, our approach exhibits competitive performance and scales well on graph-structured domains.
Introduction
Contemporary bandit optimization approaches consider problems on large continuous domains and have successfully been applied to a significant number of machine learning and real-world applications, e.g., in mobile health, environmental monitoring, economics, and hyperparameter tuning, to name a few. The main idea behind them is to exploit the correlations between the rewards of "similar" actions. This in turn, has resulted in increasingly rich models of reward functions (e.g., in linear and kernelized bandits [37, 12]), including several recent attempts to harness deep neural networks for bandit tasks (see, e.g, [45, 291). A vast majority of previous works only focus standard input domains and obtaining theoretical regret bounds.
Learning graph-structured data, such molecules or biological graph representations, requires designing sequential methods that can effectively exploit the structure of graphs. Consequently, graph neural networks (GNNs) have received attention as rapidly expanding class of machine learning models. They deem remarkably well-suited for prediction tasks in applications such as designing novel materials [20], drug discovery [22], structure- baset protein function prediction [16], etc. This rises the question of how to bridge the gap, and design bandit optimization algorithms on graph- structured data that can exploit the power of graph neural networks to approximate graph reward.
In this paper, we consider bandit optimization over graphs and propose to employ graph neural net- works with one convolutional layer to estimate the unknown reward. To scale to large graph domains (both in the number of graphs and number of nodes), we propose practical structural assumptions to model the reward function. In particular, We show a novel connection between such kernels and the graph neural tangent kernel (GNTK) that we define in Section 3. Our main result are GNN confidence bounds that can be readily used sequential decision making algorithms to achieve sublinear regret bounds (see Section 4.3).
propose use permutation invariant additive kernels.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Related Work. Our work extends the rich toolbox of methods for kernelized bandits and Bayesian optimization (BO) that work under the norm bounded Reproducing Kernel Hilbert Space assumption [37, 14, 42, 12]). The majority of these methods are designed for general Euclidean domains and rely on kernelized confidence sets to select which action to query next. The exception [43], that consider the spectral setting in which the reward function is a linear combination of the eigenvectors of the graph Laplacian and the bandit problem is defined over nodes of a single graph. In contrast, our focus is on optimizing over graph domains (i.e., set of graphs), and constructing confidence sets that can quantify the uncertainty of graph neural networks estimates.
This work contributes to the literature on neural bandits, in which fully- mully-connected [45, 44, 19], or a single hidden layer convolutional network [25] used to estimate the reward function. These works provide sublinear cumulative regret bounds in their respective settings, however, when applied directly to graph features (as we demonstrate in Section 4.3), these approaches do not scale well with the number of graph nodes.
Due to its important applications in molecule design, sequential optimization on graphs has recently received considerable attention. For example, in [28], the authors propose a kernel to capture similarities between graphs, and at every step, select the next graph through a kernelized random walk. Other works (e.g.. [17, 18, 23, 38]) encode graph representations to the (continuous) latent space of variational autoencoder and perform BO the latent space. While practically relevant for discovering novel molecules with optimized properties, these approaches lack theoretical guarantees and deem computationally demanding.
A primary focus in our work is on embedding the natural structure of the data, i.e., permutation invariance, into the reward model. This is inspired by the works of [6, 32] that consider invariances in kernel-based supervised learning. Consequently, the graph neural tangent kernel plays an integral role in our theoretical analysis. Du et al. [15] provide recursive expression for the tangent kernel of a GNN, without showing that the obtained expression is the limiting tangent kernel as defined in Jacot et al. [21] (i.e., as in Eq. (3)). In contrast, we analyze the learning dynamics of the GNN and properties of the GNTK by exploiting the connection between the structure of graph neural network and that of a neural network (in Section 3). We recover that the graph neural tangent kernel also encodes additivity. Additive models for bandit optimization have been previously studied in [24] and [35], however, these works only focus on Fuclidean domains and standard base kernels.
Finally, we build upon the recent literature on elimination- based algorithms that make use of maximum variance reduction sampling [13, 8, 7, 9, 40, 30). One of our proposed algorithms, GNN-PE, employss a phased elimination strategy together with our GNN confidence sets.
Main Contributions. We introduce bandit problem over graphs and propose to capture prior knowledge by modeling the unknown reward function using a permutation invariant additive kernel. We establish a key connection between such kernel assumptions and the graph neural tangent kernll (Proposition 3.2). By exploiting this connection, we provide novel statistical confidence bounds for the graph neural network estimator (Theorem 4.2). We further prove that a phased elimination algorithm that uses our GNN-confidence bounds (GNN-PE) achieves sublinear regret (Theorem 4.3). Importantly, our regret bound scales favorably with the number of graphs and is independent of the number of graph nodes (see Table 1). Finally, we empirically demonstrate that our algorithm consistently outperforms baselines across range of problem instances.
2 Problem Statement
We consider a bandit problem where the learner aims to optimize an unknown reward function via sequential interactions with a stochastic environment. At every time step E {1...., .7, the learner selects a graph G, from a graph domain G and observes a noisy reward y/ = (G. + es, where f - IR is the reward function and & is i.i.d. zero-mean sub-Gaussian noise with known variance proxy 2 Over a time horizon T, the learner seeks a small cumulative regret R = F f"")
where G E arg max f (G). The aim is to attain regret that is sublinear in T, meaning that RT/T + 0 as T + oo, which implies convergence to the optimal graph. As an example application, consider drug or material design, where molecules may be represented with graph structures (e.g.. from SMILES representations (1J) and the reward (C) can correspond to an unknown molecular property of interest, e.g., atomization energy. Evaluating such properties typically requires running
2

---

costly simulations or experiments with noisy outcomes. To identify the most promising candidate, e.g., the molecule with the highest atomization energy, molecules are sequentially recommended for testing and the goal is to find the optimal molecule with the least number of evaluations.
Graph Domain. We assume that the domain 9 is finite set of undirected graphs with N nodes." Without exploiting structure, standard bandit algorithms (c.g., [3]) cannot generalize across graphs, and their regret linearly depends on [ To capture the structure,
consider reward functions de- pending on features associated with the graph nodes. Similar to Du et al. [15], we associate each node j E [N] with a feature vector hG. R. for every graph G E G. We use he = (hG.)) IR- to denote the concatenated vector of all node features, and [(₃) as the neighborhood of node j. including itself. We define the aggregated node feature has = ZieN()) hG. Eient) ha..lle as
the normalized sum of the neighboring nodes' features. Similarly, hG E RR.d denotes the aggregated features, stacked across all nodes. Lastly, we let Px be the group of all permutations of length N, and use c G to denote permuted graph, where permutation c E PN is a bijective mapping from {I, (I,...,.N. ] onto itself. Permuting the nodes of graph G produces permuted feature vector hoo == (hc.,(6)) and the same holds for the aggregated features h.GG.
Reward Model. Practical graph optimization problems, such as drug discovery and materials optimization often do not depend on how the graphs' nodes in the dataset are ordered. We incorporate this structural prior into modeling the reward function, and consider functions that are invariant to node permutations. We assume that f* depends on the graph only through the aggregated node features and gives the same reward for all permutations of graph, i.e., (e G) = (G), for any G E 9 and e E PN. To guarantee such an invariance, we assume that the reward belongs to the reproducing kernel Hilbert space (RKHS) corresponding to permutation invariant kernel
i G')
1
Σ c.c'EPN
(hhoc,ee..))
|PN
where & can be any kernel defined on graph representations hgg This assumption further restricts the hypothesis space to permutation invariant functions defined on Nd-dimensional vector repre- sentations of graphs. This is due to the reproducing property of the RKHS which allows us to write f(G) = (f. ()) = (f, ke(c G)-)) = ffcc G). To make progress when optimizing over graphs with large number of nodes N, we assume that & decomposes additively over node features, i.e.,
N
k(ha, hay)
Σ
k0)
(ha., h)rs).
N
J=1
Thereby, we obtain an additive graph kernel that is invariant to node permutations:
N
G(G = PPN2
1
Σ CCEEPN
1 N
Σ
R (ha.os) ha)))))
(1)
For an arbitrary choice of k,05,, calculating i requires costly sum over (NI)² operands, since [PN] = N!. In Section 3, we select a base kernel for which the sum can be reduced to N2 terms. We are now in a position to state our main assumption. We assume that f belongs to the RKHS of and has BB-bounded RKHS norm. The norm boundedd RKHS regularity assumption is typical in the kernelized and neural bandits literature [37, 12, 45, 25J. Note that Eq. (1) only puts a structural prior on the kernel function, i.e., it describes the generic form of an additive permutation invariant graph kernel. Specifying the base kernels k ((i) determines the representation power of k. The smoother the base kernels are, the less complex the RKHS of l will be. In Section 3, we set the base kernels k() such that k becomes the expressive graph neural tangent kernel.
3 Graph Neural Networks
Graph neural networks are effective models for learning complex functions defined on graphs. As in Du et al. [15], we consider graph networks that have a single graph convolutional layer and L
'This assumption is for ease of exposition. Graphs with fewer than N nodes can be treated by adding auxiliary nodes with no features that are disconnected from the rest of the graph.
3

---

fully-com connected ReLU layers of equal width m. Such network fcNx(G; g - R may be recursively defined as follows:
(ha.)) = Waah
V 2
(hG.)))
W (f (has)) IR"", 11,,
m
(2)
1 (2W(L+1) rrtuu (11D)) [c)x(G;0)= = N
where 0 == (W jigh+1 is initialized randomly with standard normal i.id. entries, and reltu (ar) == max(0, x). The network operates on aggregated node features hGG, as typical in Graph Convolutional Networks [27]. For convenience, we assume that initialization fcNN 0") = for all G E G. similar to [25, 45]. This assumption can be fulfilled without loss of generality, with a similar treatment as in [25, Appendix B.2].
Embedded Invariances. In this work, we use graph neural networks to estimate the unknown reward function f*. This choice is motivated by the expressiveness of the GNN, the fact that scales well with graph size, and particularly due to the invariances embedded in its structure. We observe that the graph neural network fGNN is invariant to node permutations, i.e., for all G' and E PN.
JONN (G: 0) fCNN(C- G;
The key step to show this property is proving that fGNN can be expressed as an additive model of T-layer fully-connected ReLU networks,
1 N (nx(ha.::0))
fGNN ()
where fNN has similar recursive definition as fGNN (see Equation A.1). The above properties are formalized in Lemma A.1 and Lemma A.2.
Lazy (NTK) Regime. We initialize and train feNN in the well-known lazy regime [11]. In this initialization regime, when the width m large, training with gradient descent using a small learning rate causes little change in the network's parameters. Let 9CNN(G, 0) VefeNN O) denote the gradient of the network. It can be shown that during training, for all G E G, the network remains close to (aNN(G. 0²) + JỘNN (G, (0 0²), that is, its first order approximation around initialization parameters 0 Training this linearized model with a squared error loss is equivalent to
kernel regression with a tangent kernel kaNN (G, G') := geNx (G; 0*) 9GN 09). For networks of finite width, this kernel function is random since depends on the random network parameters at initialization. We show in Proposition 1, that in the infinite width limit, the tangent kernel converges deterministic kernel. This proposition introduces the Graph Neural Tangent Kernel as the limiting kernel, and links it to the Neural Tangent Kernel ([21), also defined in Appendix A). Proposition 3.1. Consider any two graphs G and G' with nodes and d-dimensional node features. In the infinite width limit, the tangent kernel KGNN(G, (a /mm converges to a deterministic kernel,
KGNN (G, (G,G')= lim KANN (G, G')/m. m-+00
(3)
which we refer to as the Graph Neural Tangent Kernel (GNTK). Moreover,
N
KGNN (G,G")
Σ
(4)
N
3-1'=1
where KNN : gd-1 x gd-1
the Neural Tangent Kernel.
The proof is given in Appendix A.I. We note that hG.; lies on the d-dimensional sphere, since the aggregated node features are normalized. The NTK is bounded by for any two points on the sphere [5]. Therefore, Proposition 3.1 implies that the GNTK is also bounded, i.e., kGNx (G, G') < for any G, G" E G. This proposition yields a kernel which captures the behaviour of the lazy GNN. While defined graphs with Nd dimensional representations, the effective input domain of this

---

kernel is d-dimensional. This advantage directly stems from the additive construction of the GNTK. The next proposition uncovers the embedded structure of the GNTK by showing a novel connection between the GNTK and k, the permutation invariant additive kernel from Eq. (1). The proof is presented in Appendix A.
Proposition 3.2. Consider from Eq. (1), where for every S S N the base kernel k() is set to be equal to İNN.
G(G,G")
E
KNN ( (())))))
PN
N
c
Then the permutation invariant additive kernel and the GNTK are identical, for all G, G' E G.
E(G,G") KGNN (G, G').
This result implies that ÀINN inherits the favorable properties of the permutation invariant additive kernel class. Hence, functions residing in HGNN, the RKHS of kGNNN are additive, invariant to node permutations, and act G' through its aggregated node features. While analytical tool, this kernel can be of independent interest in kernel methods over graph domains. In particular, calculating KGNN requires significantly fewer operations compared to a kernel & with an arbitrary choice of k0O), for which calculating k(G, G") requires super-exponentially many operations in (See Eq. (1)). In contrast, due to the decomposition in Eq, (4), calculating KONN only costs quadratic number of summations.
the GNTK as
4
GNN Bandits
The bandit literature is rich with algorithms that effectively balance exploration and exploitation to achieve sublinear regret. Two components are common in kernelized bandit optimization algorithms. The maximum information gain, for characterizing the worst-case complexity of the learning problem [37, 24, 12, 40]; and confidence sets, for quantifying the learner's s uncertainty [4, 39, 36, 12, 31]. Our first main result is an upper bound for the maximum information gain when the hypothesis space HONN (Theorem 4. I). We then propose valid confidence sets that utilize GNNs in Theorem 4.2. These theorems may be of independent interest, as they can be used towards bounding the regret for a variety of bandit algorithms on graphs. Lastly, we introduce the GNN-PE algorithm, together with its regret guarantee.
4.1 Information Gain
In bandit tasks, the learner seeks actions that give large reward while, at the same time, provide information about the unknown reward function. The speed of learning about f* is commonly quantified via the maximum information gain. Assume that the learner chooses a sequence of actions (G GT) and observes noisy rewards, where the noise is i.i.d. and drawn from a zero-mean Lub-Gaussian distribution with a variance proxy X. The information gain of this sequence calculated via the GNTK
Gr....,,, log del((r - KGNNTT)
with the kernel matrix KGNNTT = [KONN(G, Gy)lasST. The maximum information gain (MIG) [37] is then defined as:
TGNN,
max "Gi, (G GT)
(5)
Yt:GEE
In Section 4.3, we express regret bounds in terms of this quantity, as common in kernelized and neural bandits. In Theorem 4.1 we obtain data-independent bound on the MIG. The proof is given in Appendix B.
Theorem 4.1 (GNTK Information Gain Bound). Suppose the observation noise is i...d., and drawn from a zero-mean sub- Gaussian distribution, and the input domain is G. Then the maximum informa- tion gain associated with KGNN is bounded by
INNN = "T log T).
5

---

We observe that the obtained MIG bound does nor depend on N the number of nodes in the graphs. To highlight this advantage, we compare Theorem 4.1 to the equivalent bound for the vanilla neural tangent kernel which ignores the graph structure. We consider the neural tangent kernel that operates on graphs through the Ned-dimensional vector of aggregated node features hc.
hG ha N N
KNN (G, ANN
(6)
For NNN the maximum information gain scales as 'NN,T = O(T(Nd-11//44og) //N/////// T), where N appears in the exponent [25]. This results in poor scalability with graph size in the bandit optimization task, as we further demonstrate Section 4.3. Table summarizes this comparison.
4.2 Confidence Sets
Quantifying the uncertainty over the reward helps the learner guide exploration and balance it against exploitation. Confidence sets are an integral tool for uncertainty quantification. Conditioned on the history H = (Gi, Mi)ics, for any E G, the (G 6) defines an interval to which f (G) belongs with a high probability such that,
P PVVG 9:
(G) f
C.-((G 2 -
An approach common to the kernelized bandit literature is to construct sets of the form C. (G, 8) = (G) + [G)) where B, depends on the confidence level 5. The center of the interval, char- acterized by (--1(-), is the estimate of the reward, and the width 3,0,-1()). reflects the uncertainty, In this work, we utilize GNNs for construction of such sets. To this end, train a graph neural network to estimate the reward. We use the gradient of this network at initialization to approximate
the uncertainty over the reward, in [45]. Let JGNN(GS o(2) be the GNN trained with gradient descent for steps and by using learning rate 1) on the loss
(()) = + Σ (foNN(G. 0) - vi) + mA| 001
iS!
where À is the regularization coefficient, and 8 the network parameters at initialization. We propose confidence sets of the form
C-I(G, (G) (,,,-1 (G)):
where the center and width of the set are calculated via,
(G) = (cNN((;)))) (,1),
JeNN (G; 08) 1
(C, 0t ( (G; -1 gGNN (G; 0²) Vm
(8)
GG) =
(NI-
Σ
Vm
Here 9GNN (G:NNGG;O (G; = VefeNN 09) denotes the gradient at initialization. Moreover, we use Ao Amin (GNN)= > 0 to denote the minimum eigenvalue of the kernel matrix calculated for the entire domain, i.e., KGNN= [KONN(G, G')]a. Theorem 4.2 shows that this construction gives valid confidence intervals, i.e., satisfies Eq. (7), when the reward function lies in HGNN and has bounded RKHS norm.
Theorem 4.2 (GNN Confidence Bound), Set E (0, 1). Suppose f E HKCNN with bounded norm IIf I < B. Assume that the random sequences (Gi)isi and (G)ist are statistically independent. Let the width m = poly (t, L, B, [G], A, A, .log(N/6)) learning rate = (mmm + mA) -1 with some universal constant C, and 2 1. Then for all graphs G E G. with probability of at least 1 8.
If" ( & (,rr-1(G),
where 1 and ōz-1 are defined in Eq. (8) and
8 2B
V 2 2
The ">" notation in Theorem 4.2 omits the terms that vanish with I, i.e. are o(1). An exact version of the theorem without the aforementioned approximations is given in Appendix C.I.

---

Setting
MIG Bound, YT
Cumulative Regret (Phased Elimination)
Neural
T Nu
log No T)
T 2Na-1 2Nd
log Ida T
Graph Neural
o " log T)
Ô
T 22
log 24 T)
Table 1: Summary of main bounds for the NN and GNN approaches. Here T denotes the bandit horizon, N the number of nodes each graph, and the dimension of node features. The GNN guarantees are independent of N.
4.3 Bandit Optimization with Graph Neural Networks
The developed confidence sets can be used to assist the learner with controlling the growth of regret. In this section, we give a concrete example on how our GNN confidence sets (Equation 8) can be used by algorithm to solve bandit optimization tasks on graphs.
We introduce Phasedd Elimination (GNN-PE; see Algorithm 1) that consists of episodes of pure exploration over set of plausible maximizer graphs, similar to [7. 30). Each episode is followed by an elimination step, that makes use of GNN confidence bounds shrink the set of plausible maximizers. More formally, at step during an episode the learner selects actions via Ge.t arg max (G), where Ge the set of graphs that might maximize f" according to the learner's s current knowledge. Once the episode is over after Te steps, the set Ge is updated to contain graphs that still have a chance being a maximizer according to the confidence bounds [ūe,T, (G) + 8T. T. (G)] where T. and T. are only computed based the points within episode e.
Theorem 4.3 shows that GNN-PE incurs sublinear control over the cumulative regret. We provide the proof in Appendix C. We use Ó--) notation to hide polylog(T)) (T") factors.
Theorem 4.3. Set 8 (0, 1). Suppose f HREEN with a bounded norm [I I S B. Let the
width m = poly (t, L, B, [g). X, \ (og(N/6)) learning rate n = C + mA) with some
universal constant C, and J 2 1. Then with probability at least 1 5, GNN-PE satisfies
RT - O (B+
/ log (0166)
We can observe the benefit of working with graph neural network by comparing the bound in Theorem 4.3 with the regret for a structure -agnostic algorithm. Recall ANN the vanilla NTK, defined over the concatenated feature vectors (Equation 6). For the sake of this comparison, geometric structure and assume that f" E HNN. Swapping out KGNN for KNN, and respectively the GNN with an NN defined in Eq. (A.1), obtain NN-PE, the neural network counterpart of GNN-PE. This algorithm accepts Nd-dimensional input vectors as actions. Similar to Theorem 4.3,
ignore the
we can show that NN-PE can satisfy guarantee of (2T(2Nd-1)/2)) log" 1/2Nd T) for the regret. This bound suggests that as N grows, finding the optimal graph can become more challenging for the learner. Working with AGNN to encode the structure of the bandit problem, and consequently using the GNN to solve it, removes the dependency on N the exponent. This result summarized in Table 1.
We provide some intuition on why working with permutation invariant model is beneficial for bandit optimization on graphs. Confidence sets which are constructed for member of HNN are larger, and result in sub-optimal action selection. Further, training the neural network is more challenging task, since permutation invariance the data. This results in less accurate reward estimates. We refer the reader to Appendix A.3 for more rigorous discussion. There we compare HGNN and HNN, the hypothesis spaces corresponding to the two models, through the Mercer decomposition of their kernels.
hard coded in the network architecture and has be learned from
5 Experiments
We create synthetic datasets which may be of independent interest and can be used for evaluating and benchmarking machine learning algorithms on graph domains. Each dataset is constructed from finite graph domain together with reward function. The domains generated randomly and
7

---

differ in properties of the member graphs that influence the problem complexity, e.g., number of nodes and edge density. Each domain Gp.N consists of Erdós Rénéi random graphs, where each graph has N nodes, and between each two nodes there exists an edge with probability p. The node features are i.i.d. d 10 dimensional standard Gaussian vectors. We choose N E (5. 20, 100), p E {0.05, 0.2, 0.95). and thereby sample total of 9 different domains each containing 10000 graphs. For instance, 55. denotes the domain with sparse and small graphs, while 90.95.100 is the domain of dense graphs with many nodes. For every domain, we sample random reward function f: Gp.N + IR that is invariant to node permutations. We use GO, KGNN) as a prior, and sample f from its posterior GP. The posterior is calculated using small random dataset (G,, V6 Wsssss, where ya are drawn independently from (000 1) and G2 are randomly chosen from gp.N. The corresponding f(G)) |G, E Gp.N
dataset is then Dp.N
Experiment Setup. Every performance curve the paper shows an average over 20 runs of the corresponding bandit problem, each with a different action set sampled from 9p.N- The shaded areas in all figures show the standard error across runs. In all experiments, the reward is observed with a zero-mean Gaussian noise of variance o 10-2 We always set width m 2048 and layers L = 2, for every type of network architecture. Four algorithms appear in our experiments. In addition to our main algorithm GNN-PE, we introduce GNN-UCB, which selects actions via G = arg max m (G) + 3 the classic UCB policy based on the GNN confidence sets. The pseudo-code is given in Appendix D.3. NN-UCB, introduced by [45], is the neural counterpart of GNN-UCB, and NN-PE as discussed in Section 4.3. To configure these algorithms, we only tune A and Be. and do by using the simplest dataset Do.0s.5. We find that the algorithms sensitive to domain configuration and work for all D3,N out of the box. Therefore, the same values for À and 33 are used across all experiments. We include the complete result of our hyperparameter search in Figure 5.
not
Lazy training. We initialize the graph neural networks (and the NNs) in the lazy regime as described in Eq. (2) (and Eq. A.I). Training a network in this regime with gradient descent causes little change in the weights. Consequently, it is challenging to effectively train lazy network in practice. Therefore, the stopping criterion for gradient descent plays a crucial role in achieving sublinear regret. Inaccurate estimation of the reward function disturbs the balance of exploration and exploitation, and leads the learner to poor optima. To prevent this issue, we devise a stopping criterion that depends on the history H₁-1, such that, as t grows, the network is often trained for more gradient descent steps J. This criterion can be employed by any neural bandit algorithm and may be of independent practical interest. The details of training with gradient descent, stopping and batching are given in Appendix D.2.
Regret Experiments. We assess the performance of the algorithms on bandit optimiza- tion tasks over different domains. In Figure 1, we show the inference cumulative regret Ri- = ErsT (G') maxges (G), for which we select graph domains with N 20 nodes and edge probability
0.2. Figure 6 shows the regret for all dataset configurations. To verify scalability with [g], we run the algorithms on action sets of increasing size [G] E {200, 500, 1000). Figure 1 presents the results: GNN-PE consistently outperforms the other methods. It is evident that the algorithms built with GNN confidence sets find the optimal graph, regardless of the size of the do- main. The GNN algorithms exhibit competitive performance, and attain sublinear regret for all dataset configurations. The neural methods however, may fail to scale and find the optima in limited time.
Scalability with Graph Size. In Section 4.3, we argue that using a neural network which takes ha E Nd as the input, causes the regret to grow with (( The additive structure of the GNN, however, allows the learner work on a d-dimensional domain, independent of graph size. Figure 2 reflects this behaviour. Fixing = 0.2, and | = 200, we run the algorithm over domains with two graph sizes N E {20, 100}. GNN-PE achieves sublinear regret in both cases, and manages to find global maxima within roughly the same number of steps. This is in contrast to NN-PE, which more affected by increasing graph size. A similar comparison for all configurations and algorithms is plotted in Figure 7, and the same behaviour is observed across all settings: the performance of GNN methods scales well with N, while this is not the case for NN methods.
Effect of Graph Density, As a final observation, we discuss the effect of edge density. Consider a complete graph G with (2) edges. The neighborhoods are symmetric and the aggregated node fea- tures hG, are identical for all i < N. Permutations on this graph will not change the output of either fGNN or fNN. Therefore, we expect that for dense graphs, i.e., large values of p. using a permutation invariant model comes with fewer benefits for the learner. This is opposed to when the graph is sparse
8

---

lgi 200
lg 500
ig 1000
15.0
12.5
2.0
3
1.5
2
5.0
1
2.5
0.0
100
200
300
400
500
100
200
300
400
500
0
200
400
600
800
1000
GNN-PE
GNN-UCB
NN-PE
NN-UCB
Figure 1: Regret Ry over time horizon of 500 and 1000 steps with N and p = 0.2. GNN-PE
consistently outperforms other algorithms and scales well with size of the action set g])
GNN-UCB
NN-UCB
1.0
1
0.0
100
100
200
300
400
500
100
200
300
400
500
GNI-PE---E
GNNNFE - 100
... NN-PE 100
0.05
p-
p- 0.95
Figure 2: Increasing N has little effect on GNN-PE.
Figure 3: Increasing the edge density of the graphs reduces the performance gap between GNN-UCB and NN-UCB.
and the neighhorhoods are asymmetric. To verify this conjecture, we fix N = 20, |6| | = 200, and run the algorithm domains with graphs of different edge probability {0.05, 0.2, 0.95). Figure shows that while GNN-UCB always achieves sublinear regret, it takes longer to find the optima when the graphs are more dense. NN-UCB however, improves the edge probability p grows, since, roughly put, the graphs in the domain are becoming invariant to permutations. Therefore Figure confirms that the performance gap between the two method reduced for graphs that are more dense. In Figure 8, we plot the effect of graph density for other dataset configurations and bandit algorithms. This behaviour is observed predominantly for the UCB algorithms.
Conclusion
We analyze the use of graph neural networks in bandit optimization tasks over large graph domains. The main takeaway is that encoding the natural structure of the environment into the model, reduces the complexity of the task for the learner. By selecting a kernel that embeds invariances, we introduce structure into the algorithm in principled manner. Importantly, we propose key structural assump- tions on the graph reward function and establish a novel connection between additive permutation invariant kernels and the GNTK. We construct valid graph neural network confidence sets, and use to build GNN bandit algorithm that achieves sublinear regret. While all node features contribute to the graph's 's reward, our bounds are independent of the number of nodes. This result holds for GNNs with single convolutional layer and graphs with node feature representation. An immediate next step is to generalize this approach other more complex graph neural network architectures and representa- tions (e.g.. by including information about graph edges) and investigating their effectiveness for bandit optimization. Our analysis opens up two avenues of future research. The proposed kernel and the graph confidence sets may be used in other algorithms for sequential rrcisiin-makinn tasks graphs.

---

Additionally, our approach of embedding the environment's permutation invariant structure into the algorithm may inspire further work on structured bandit optimization presence of invariances.
Acknowledgments and Disclosure of Funding
We thank Jonas Rothfuss for his valuable suggestions regarding the experiments. We acknowledge Deepak Narayanan's 's effort on earlier version of the code. We thank Nicolas Emmenegger and Scott Sussex for their thorough feedback, and lastly, we thank Alex Hägele for fruitful discussions regarding the writing. This research was supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and Innovation Program Grant agreement no. 815943.
References
[1] Eric Anderson, Gilman D Veith, and David Weininger. SMILES, line notation and computer- ized interpreter for chemical structures. US Environmental Protection Agency, Environmental Research Laboratory, 1987.
[2] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with infinitely wide neural net. Advances in Neural Information Processing Systems, 2019.
[3] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 2002.
[4] Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in Neural Information Processing Systems, 2008.
[5] Alberto Bietti and Francis Bach. Deep equals shallow for ReLU networks in kernel regimes, In International Conference on Learning Representations, 2021.
[6] Alberto Bietti, Luca Venturi, and Joan Bruna. On the sample complexity of learning under geometric stability. Advances in Neural Information Processing Systems, 2021.
[7] Iliaa Bogunovic and Andreas Krause. Misspecified Gaussian process bandit optimization. In Advances in Neural Information Processing Systems, 2021.
Iijaa Bogunovic, Jonathan Scarlett, Andreas Krause, and Volkan Cevher. Truncated variance reduction: A unified approach to Bayesian optimization and level-set estimation. In Advances in Neural Information Processing Systems, 2016.
[9] Ilija Bogunovic, Zihan Li, Andreas Krause, and Jonathan Scarlett. A robust phased elimination algorithm for cnnuption-toleraan Gaussian process bandits. In Advances Neural Information Processing Systems, 2022.
[10] Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in Neural Information Processing Systems, 2019.
[11] Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable program- ming. Advances in Neural Information Processing Systems, 2019.
[12] Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In International Conference Machine Learning. 2017.
[13] Emile Contal, David Buffoni, Alexandre Robicquet, and Nicolas Vayatis. Parallel gaussian process optimization with upper confidence bound and pure exploration. In Joint European Conference on Machine Learning and Knowledge Discovery Databases. Springer, 2013.
[14] Nando De, Alex Smola, and Masrour Zoghi. Exponential regret bounds for Gaussian process bandits with deterministic observations. In International Conference on Machine Learning, 2012.
10

---

[15] Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos. Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. Advances in Neural Information Processing Systems, 2019.
[16] Vladimir Gligorijević, P Douglas Renfrew, Tomasz Kosciolek, Julia Koehler Leman, Daniel Berenberg, Tommi Vatanen, Chris Chandler, Bryn C Taylor, lan M Fisk, Hera Vlamakis, et al. Structure-based protein function prediction using graph convolutional networks. Nature communications, 2021.
[17] Rafael
Jennifer N Wei, David Duvenaud, José Miguel Hernández-Lobate Benjamín Sánchez-Lengeling, Dennis Sheberla, Jorge Aguilera-pparrauuire. Timothy D Hirzel, Ryan Adams, and Alán Aspuru-Guzik, Automatic chemical design using a data-driven continuous representation of molecules. ACS central science, 2018.
[18] Ryan-Rhys Griffiths and José Miguel Hernnddez- Constrained Bayesian optimization for automatic chemical design using variational autoencoders. Chemical science, 2020.
[19] Quanquan Gu, Amin Karbasi, Khashayar Khosravi, Vahab Mirrokni, and Dongruo Zhou. Batched neural bandits. arXiv preprint arXiv:2102.13028 2021.
[20] Kai Guo and Markus Buehler. A semi-supervised approach to architected materials design using graph neural networks. Extreme Mechanics Letters, 2020.
[21] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems, 2018.
[22] Dejun Jiang, Zhenxing Wu, Chang- Yu Hsieh, Guangyong Chen, Ben Liao, Zhe Wang. Chao Shen, Dongsheng Cao, Jian Wu, and Tingjun Hou. Could graph neural networks learn better molecular representation for drug discovery? a comparison study of descriptor-basee and graph-based models. Journal of cheminformatics, 2021.
[23] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction variational autoencoder for molecular graph generation. In International Conference on Machine Learning, 2018.
[24] Kirthevasan Kandasamy, Jeff Schneider, and Barnaáss Póczos. High dimensional Bayesian optimisation and bandits via additive models. International Conference on Machine Learning. PMLR, 2015.
[25] Parnian Kassraie and Andreas Krause. Neural contextual bandits without regret. In International Conference on Artificial Intelligence and Statistics, 2022.
[26] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Interna- fional Conference on Learning Representations, 2015.
[27] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[28] Ksenia Korovina, Sailun Xu, Kirthevasan Kandasamy, Willie Neiswanger. Barnabas Poczos, Jeff Schneider, and Eric Xing. Chembo: Bayesian optimization of small organic molecules with synthesizable recommendations. In International Conference on Artificial Intelligence and Statistics, 2020.
[29] Andreas Krause and Cheng Ong. Contextual Gaussian process bandit optimization. In Advances in Neural Information Processing Systems, 2011.
[30] Zihan Li and Jonathan Scarlett. Gaussian process bandit optimization with few batches. In International Conference on Artificial Intelligence and Statistics. PMLR, 2022.
[31] Xiuyuan Lu and Benjamin Van Roy. Information-theorede confidence bounds for reinforcement learning. Advances Neural Information Processing Systems, 2019.
[32] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random features and kernel models. CoRR, 2021.

---

[33] Roman Novak, Lechao Xiao, Jiri Hron, Jachoon Lee, Alexander A. Alemi, Jascha Sohl- Dickstein, and Samuel Schoenholz. Neural tangents: Fast and easy infinite neural networks in Python. In International Conference on Learning Representations, 2020.
[34] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary Viiioo, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch, 2017.
[35] Paul Rolland, Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher. High-dimensional Bayesian optimization via additive models with overlapping groups. In International Conference on Artificial Intelligence and Statisticx, 2018.
[36] Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 2014.
[37] Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process opti- mization the bandit setting: No regret and experimental design. In International Conference on Machine Learning, 2010.
[38] Samuel Stanton, Wesley Maddox, Nate Gruver, Phillip Maffettone, Emily Delaney, Peyton Greenside, and Andrew Gordon Wilson. Accelcrating Bayesian optimization for biological se- quence design with denoising autoencoders. In International Conference on Machine Learning. 2022.
[39] William Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 1933.
[40] Sattar Vakili, Nacime Bouziani, Sepehr Jalali, Alberto Bernacchia, and Da shan Shiu. Optimal order simple regret for gaussian process bandits. In Advances in Neural Information Processing Systems, 2021.
[41] Sattar Vakili, Kia Khezeli, and Victor Picheny, On information gain and regret bounds in Gaussian process bandits. In International Conference on Artificial Intelligence and Statistics, 2021.
[42] Michal Valko, Nathan Korda, Rémi Munos, Ilias Flaounas, and Nello Cristianini. Finite-time analysis of kernelised contextual bandits. In Conference on Uncertainty in Artificial Intelligence, 2013.
[43] Michal Valko, Rémi Munos, Branislav Kveton, and Tomáš Kocák. Spectral bandits for smooth graph functions. In International Conference on Machine Learning. 2014.
[44] Weitong ZHANG, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural Thompson Sampling. In International Conference on Learning Representations, 2021.
[45] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with JCB-based exploration. In International Conference on Machine Learning, 2020.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We often refer to the Theorem or section number when making claim about the contribution of the paper.
(b) Did you describe the limitations of your work? [Yes] Section explains the theoretical setting for which our result is valid. Any remaining assumption is stated in the theorem statements.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] The impact is primarily theoretical.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Section explains the theoretical setting for which our result is valid. Section 3 and Section spell out the scope of our algorithm. Any remaining assumption stated in the theorem statements.
(b) Did you include complete proofs of all theoretical results? [Yes] Appendix A contains the proof to Proposition 3.1 and Proposition 3.2. Appendix B present the proof of Theorem 4.1, and lastly Appendix C the proof to Theorem 4.2 and Theorem 4.3.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as a URL)? [Yes] Appendix D.2 includes the practical details and the instructions required to produce the results. We use random synthetic data which we generate ourselves, instruction create similar random datasets is also given.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] This is covered in Section and Appendix D.2.
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] All experiments are for 20 random seeds. All plots report the standard error across the runs.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] About hour per CPU core on 100 internal cluster nodes.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We use the Neural Tangents and PyTorch libraries. Both cited.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you'le 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "hCJihWQ5B_T", "reviewer": "Reviewer_FKpp", "summary": "This paper contributes to the bandits literature wirh GNNs as reward functions: \n * \"In this paper, we consider bandit optimization over graphs and propose to employ graph neural\nnetworks to estimate the unknown reward. \"\n* \"Without exploiting structure, standard bandit algorithms (e.g., [3]) cannot generalize across graphs\"\n* \"Consider functions that are invariant to node permutations\"\n* \"In this work, we use graph neural networks to estimate the unknown reward function f∗. \"\n\n·GNNs can be seen as averaged NNs each one taking as input its aggregation. \nBroadly speaking, we have that the \"average of local aggregations leads to the global one\". This is consistent with an averaged readout. \n\nMain result: \n\"Our main result are GNN confidence bounds that can be readily used in sequential\ndecision-making algorithms to achieve sublinear regret bounds \"\n\nGNN confidence bounds: \n* Independence of N in the MIG bounds. Using GNNs vs NNs\n* Gain wrt to structure-agnostic bandits. \n\nExperiments.\n* Comparison with NNs. A nice way of checking up the impact of MIG bounds. \n* With dense graphs, they obtain a similar performance for both GNNs and NNs, There is a nice explanation for this in terms of message passing: similar averaged aggregations for all nodes. GNNs suffer from over-smoothing. ", "questions": "* How the bandit optimization leads to a better understanding of the GNNs?\n* As the variance in eq. 8 is defined wrt to the initial gradient, it seems that the bound is very large, please clarify. \n* How the performance of the GNNs decays with more layers? ", "limitations": "Suggestions for improvement. It shoulod be very interesting to use all this theory for better understanding how GNNs decay in performance (beyond the dense case) and how to take rewiring decisions. For instance, the sequence of graphs could be different strategies of rewiring or different rewiring degrees and bandits could obtain the optimal parameterization and the MIG and confidence bounds. ", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Stengths.\n* Mostly for the bandits literature, theorerical insights in using GNNs as permutation invariant reward functions. \n* Theoretical insignt in how to improve bandits in structural domains. \n\nWeaknesses.\n* No insights in common problems in GNNs: over-smoothing, over-squashing etc. As commented above, with dense graphs we have that GNNs and NNs bandits have a similar performance. This line of analyisis is more interesting. \n* Limited interest or impact but in the bandits area. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "E6zokZlFnm0", "reviewer": "Reviewer_uFWG", "summary": "In this paper, the authors address the bandit optimization problem with the reward function defined over graph domains. \nGiven that in applications such as molecule design and drug discovery the reward is naturally invariant to graph permutations and to be able to scale to large graph domains, the authors consider the permutation invariance in their model. Authors, extend the methods for kernelized bandits that rely on kernelized confidence sets, to optimization over graph domains and constructing confidence sets that can quantify the uncertainty of graph neural networks (GNNs) estimates. To be more precise, authors proposed a permutation invariant additive kernel, and established a connection between such kernels and the graph neural tangent kernel that are introduced in this work. Establishing this connection led to the following main contributions:\n i - establishing an upper bound for maximum information gain.\nii- constructing valid confidence sets that utilize GNNs.\niii- Leveraging the GNN-confidence bounds to propose an algorithm namely, GNN-PE (GNN-Phase Elimination) to achieve sublinear regret. \n\n\n", "questions": "This paper was assigned to me very recently. Unfortunately I did not get the chance to read the supplementary document in full, but I tried to skim through the supplementary document to verify some of the results.\n\n- In proposition 3.1. authors show that in the infinite width limit, the tangent kernel converges to a deterministic kernel that is the graph neural tangent kernel. How limiting this condition is? Do the conditions on $m$ in the statement of theorems 4.2. and 4.3. obey this condition and the connection between the GNTK and the  permutation invariant additive kernel holds?\nAlso, in the statement of the proposition 3.1. I believe it should be \"the tangent kernel $\\tilde{k}_{GNN}$ as opposed to $k_{NN}$.\n- In section 5, the numerical experiments show that the GNN-based techniques are superior to NN based methods. Is this because the GNTK inherits the properties of the permutation invariant additive kernel and this is not the case for NTK? \n\n- I suggest the authors, also highlight the limitations of the proposed method. \n\nMinor comments: \nPlease improve the figures in section 5, for example add labels.\nTypo: line 534, \"tangent\".\n\n ", "limitations": "The paper is more toward theoretical extension of bandit problem to the graph domain. However, authors did not clearly explain if there are limitations to their results and the assumptions they made to derive the main results. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "-The novelty of the paper lies in establishing a connection between the permutation invariant additive kernels and the graph neural tangent kernel (GNTK) that authors introduced in this work. In addition authors linked the GNTK to neural tangent kernel (NTK). These results are shown in propositions 3.1 and 3.2. and are the basis for the main contributions of the paper. Leveraging the notion of GNTK, the authors calculate the information gain of a sequence of actions and the maximum information gain (MIG). Also, they obtained a bound for MIG that does not depend on N that is the number of nodes in the graph. In addition, authors proposed valid confidence sets for GNN and employ them to develop an algorithm to solve the bandit optimization tasks on graphs.\n-Authors provided proofs to the discussed theorems and propositions in the supplementary document. \n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-8TuxAg5aCB", "reviewer": "Reviewer_yqgD", "summary": "This paper considers the bandit optimization problem over graph data. The key challenge is shown to be the permutation-invariance of the model, and the authors propose to use a permutation-invariant additive kernel on graphs nodes to represent the unknown reward function. The kernel is shown to be the limit of the GNNs in the NTK regime.\nThe achieved maximum information gain is independent of the number of nodes in the graphs (Theorem 4.1). They also study confidence sets over graph data and propose GNNs to achieve them (Theorem 4.2). Then, they use these results to get a regret bound using the GNN-PE algorithm (Theorem 4.3.). This regret is again independent of the number of nodes. The paper is then concluded with some experiments.\n", "questions": "\n\nI think this is an interesting/good paper. I just have some comments for the authors:\n\n\n\nMajor comments:\n\n(0) Line 174-181 -- it is claimed that computing the invariant kernel with the average over all permutations is not feasible, and using GNNs can help alleviate this calculation to the feasible sum $O(N^2)$. This looks to be a \"frustration of purpose\" because you just want to use the kernel $\\bar k$ for your analysis, and in practice, GNNs are used. So why showing that an easier computation is feasible is a contribution? (Please correct me if this is not true).  In my opinion, Proposition 3.1 and Proposition 3.2 are some great observations, not contributions because the proofs are just changes in the order of summation, etc.\n\n(1) Can you find concrete graph functions that can be approximated with those balls in the RKHS norm (with explicit radii)? For example, node degrees, paths, functions of them, etc. I know those spaces are common in the kernel theory, but here for graphs, it is not that clear how they relate to graph properties. \n\n\n\n\n\n\nMinor comments:\n\n(0) Line 104 -- the used notation is a bit unconventional; I suggest using $S_n$ for the symmetric group and $\\sigma$ for a permutation, which is more standard.\n\n(1) Line 528 -- please add space before \"consider\"\n\n", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\npros:\n\n(1) well-motivated problem, having solid theoretical results\n\n(2) including supporting experiments \n\n(3) the paper is very well-written\n\n\n\ncons:\n\n\n(1) having no example about the ball in RKHS norm (see below)\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept