Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper, the authors address the bandit optimization problem with the reward function defined over graph domains. 
Given 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:
 i - establishing an upper bound for maximum information gain.
ii- constructing valid confidence sets that utilize GNNs.
iii- Leveraging the GNN-confidence bounds to propose an algorithm namely, GNN-PE (GNN-Phase Elimination) to achieve sublinear regret. 



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.
-Authors provided proofs to the discussed theorems and propositions in the supplementary document. 




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.

- 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?
Also, in the statement of the proposition 3.1. I believe it should be "the tangent kernel $\tilde{k}_{GNN}$ as opposed to $k_{NN}$.
- 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? 

- I suggest the authors, also highlight the limitations of the proposed method. 

Minor comments: 
Please improve the figures in section 5, for example add labels.
Typo: line 534, "tangent".

 
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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
The 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.

strengths_and_weaknesses: 
pros:

(1) well-motivated problem, having solid theoretical results

(2) including supporting experiments 

(3) the paper is very well-written



cons:


(1) having no example about the ball in RKHS norm (see below)


questions: 

I think this is an interesting/good paper. I just have some comments for the authors:



Major comments:

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

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






Minor comments:

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

(1) Line 528 -- please add space before "consider"


limitations: N/A
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper contributes to the bandits literature wirh GNNs as reward functions: 
 * "In this paper, we consider bandit optimization over graphs and propose to employ graph neural
networks to estimate the unknown reward. "
* "Without exploiting structure, standard bandit algorithms (e.g., [3]) cannot generalize across graphs"
* "Consider functions that are invariant to node permutations"
* "In this work, we use graph neural networks to estimate the unknown reward function f∗. "

·GNNs can be seen as averaged NNs each one taking as input its aggregation. 
Broadly speaking, we have that the "average of local aggregations leads to the global one". This is consistent with an averaged readout. 

Main result: 
"Our main result are GNN confidence bounds that can be readily used in sequential
decision-making algorithms to achieve sublinear regret bounds "

GNN confidence bounds: 
* Independence of N in the MIG bounds. Using GNNs vs NNs
* Gain wrt to structure-agnostic bandits. 

Experiments.
* Comparison with NNs. A nice way of checking up the impact of MIG bounds. 
* 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. 
strengths_and_weaknesses: Stengths.
* Mostly for the bandits literature, theorerical insights in using GNNs as permutation invariant reward functions. 
* Theoretical insignt in how to improve bandits in structural domains. 

Weaknesses.
* 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. 
* Limited interest or impact but in the bandits area. 

questions: * How the bandit optimization leads to a better understanding of the GNNs?
* As the variance in eq. 8 is defined wrt to the initial gradient, it seems that the bound is very large, please clarify. 
* 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.
review_title: null

Meta-review: metareview: This paper studies a bandit optimization problem where the rewards are smooth on a graph. The authors show that GNNs can be used to estimate the reward functions and confidence bounds. This is then used to design a phased elimination algorithm. The reviewers agree that the paper is interesting and makes a significant contribution to the area -- I recommend its acceptance. 
confidence: Certain
Decision: Accept