Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors present a novel graph neural bandit approach to tackle the problem of estimating the reward corresponding to the selection of options for users based on their contextual information. Differently from previous works, they adopt a graph structure among users to exploit the correlations existing among them. The authors propose and analyse a new algorithm theoretically. Finally, they apply their methods to real-world settings and show the superior performance of what has been presented w.r.t. state-of-the-art algorithms.
strength_and_weaknesses: The topic and the methodology proposed are for sure of value to the ICLR community. I have concerns mainly about two points.
1) The presentation of the paper is poor. Before considering it for publication, I think that the authors should revise the structure of the paper and to better present the elements composing the proposed approach.
2) The paper is not self-contained. Indeed, while it is clear that the proofs cannot be included in the main paper, most of the details about the experimental setting are left in the appendix. This also holds for some parts of the description of the methodology (pseudocode). My concern is that the paper requires the appendix to be fully understood.

Moreover, I think that the authors should provide statistical significance for the experiments they provided.

Details:
- please add a formal definition of what you call volume (before Equation 1)
- check the punctuation of the formulas 
- please add a more complete definition of the \Lambda^*_i,t matrix. For instance, is it changing over time?
- The presentation of the user graphs is not clear. In my opinion, you should have presented a general definition for a graph and subsequently instantiate it for your exploitation and exploration graphs. I suggest rethinking this paragraph.
- Is the function \Psi^{(1)} known? It is mentioned in the following part of the paper, but it should require a discussion just after its definition. The same holds with \Psi^{(2)}.
- there are minor grammar errors (in -> at, missing 'the')
- Overall, the presentation of the problem formulation can be improved. I think that all the elements required for further discussion are present, but the order and the comments provided may be unclear to a generic ML researcher who is reading the paper, while an expert of the bandit setting is able to understand even if they are presented poorly.
- Remark 3.1: do we also have some bounds on the loss we might incur in terms of accuracy or the bias we are introducing with this approach?
- Remark 3.2: even in this case, it might be interesting to understand if there is a factor in terms of regret implied by this choice.
- I think that deferring the details about the algorithm to the appendix would make the paper non-self-contained. Maybe the complexity of the description of the proposed algorithm requires more space to include all the material, therefore, I suggest evaluating the possibility of sending the paper to a venue where there is no constraint on the page length.
- It seems that the experiments are provided without confidence intervals/standard deviation bounds. I think that the significance of the results can be assessed only if they are explicitly added to the figures.
- The details about the experimental setting are provided in the appendix. I think that the authors should also distribute the code corresponding to their method.

------------------------------------------------------------------------------
After rebuttal: I think that the paper is of interest but should be accepted only if the authors are able to make it self-contained. I raised my score, assuming that the authors can implement all the improvements cited in the rebuttal.

After the second rebuttal response: I think that the quality of the paper presentation has been improved during the discussion. I raised further my score.
clarity,_quality,_novelty_and_reproducibility: The presented approach is novel.
The paper requires some rethinking of the structure.
The authors did not mention anything about the availability of the code corresponding to the experiments they run.
summary_of_the_review: The topic is interesting, and the developed approach is novel, but some concerns about the presentation and self-completeness of the main paper make it not yet ready for publication.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a novel framework named Graph Neural Bandits (GNB) to model the fine-grained user collaborative effects where they model the user correlation by the user graph. A GNN-based model is proposed to achieve adaptive exploration. They also show an O(\sqrt{T\log(Tn)}) regret upper bound of the GNB algorithm. Extensive experiments show the efficiency of GNB compared with state-of-the-art algorithms.
strength_and_weaknesses: Strength:

1. The idea of using the user graph to model the fine-grained user collaborative effects is new. The proposed framework GNB is also novel.

2. The regret bound illustrated in this paper is sharper than the existing results. They remove the term $d$ and reduce $\sqrt{n}$ to $\sqrt{\log(n)}$.

Weakness:

1. I’m confused about the term $d$ in the regret bound. Can you give more explanation about how to remove the term $d$ in the analysis?

2. The regret theorem requires $m > \Omega(poly(T))$, which might be very large when round $T$ is sufficiently large.

3. Can you give more explanations about the exploration user graph? How about estimating the potential gain based only on a single user and arm?

4. The experimental results in the MovieLens dataset and Yelp dataset seem not to converge. Maybe the algorithm needs to run more rounds to show the convergence.

5. It will be better if the author could discuss more the comparison between the linear algorithm and neural architecture algorithm, and the comparison between the algorithm considering user collaboration and the algorithm considering no user collaboration. 
clarity,_quality,_novelty_and_reproducibility: The contribution of this work is important since it is the first to analyze the fine-grained user collaboration. The GNB framework proposed in this paper is also novel. This paper is also technically solid and well-organized.
summary_of_the_review: This paper proposes a novel framework named GNB to model fine-grained user collaboration. It also gives a sharper regret bound of the GNB algorithm compared with existing results. It will be better if the author could give more discussions about the experiments.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new model called Graph Neural Bandits (GNB) to leverage the collaborative nature among users empowered by graph neural networks (GNNs). Instead of estimating clusters of users, the method models the “fine-grained” collaborative effects through estimated user graphs in terms of exploitation and exploration individually. Based on EE networks, the paper utilizes separate GNN-based models for exploitation and adaptive exploration respectively. Theoretical analysis and experimental results on multiple real data sets in comparison with state-of-the-art baselines are provided to demonstrate the effectiveness of the proposed framework. 
strength_and_weaknesses: Although the motivation of this paper is well and the idea of the proposed framework is well defined, However, I have the following concerns about its learning process, running and space complexity. 

I feel that its complexity seems to be very high, which will hinder its real application. 
1.	This paper tries to model the fine-grained collaborative effects of individual users and the arms. This motivation is straightforward, however, it may make the scale of the network be larger significantly. In a real online recommendation system, there would be several billions of requests from millions of different users. These users are evolving as the time. If we try to model the individual user in the bandit setting, the network should be larger extremely, which may highlight the sparsity problem of the data. Is it necessary to model the individual user after taken the large n into consideration? On the other hand, if we have a small number of users for an application scenario, the data may enough for the exploitation. In this situation, the advantage of exploration is relatively limited. 
2.	In the learning framework, the method will construct two graphs continuously. The space and running time complexity should be considered. I feel the complexity would be larger significantly to obtain the fine-grained reward improvement. So I suggest to compare the complexity except cumulative reward. 
3.	Although the learning framework is clear, the convergence of the exploration and exploitation GNN should be given. These two GNN are dependent. Does the structure of exploitation gnn have effect on the convergence of exploration gnn and vice versa? Will the prediction of the exploration gnn be smaller as the increase of the data? 

clarity,_quality,_novelty_and_reproducibility: The proposed problem and the learning process are relatively novel.
The paper is well written.
The code is supplied by authors.
summary_of_the_review: see detailed Strength And Weaknesses section.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Summary

This paper introduces Graph Neural Bandits (GNB) in the context of personalized recommendation. Specifically, the authors leverage graph neural networks to learn users’ “coarse-grained” collaborative instead of “fine-grained” for bandits optimization. All in all, the proposed method shows good performance across nine algorithms/baselines on various datasets and the authors also provide the theoretical analysis for regret upper bound of complexity.

strength_and_weaknesses: Some strengths:

1. The paper tackles an interesting bandits problem by formulating the exploitation and exploration via graph neural networks. The paper has extensive experiments.
2. The proposed method seems to perform consistently across datasets according to Section 5 Experiments and Appendix B. 
3. The paper is straightforward and easy to follow
4. It’s also good that the authors provided source code for reproducibility.


Some of my concerns/suggestions for improvements: 

1. In my opinion, the contribution is limited as the paper is developed based on [1, 2], which made the contribution is incremental. It seems to me that the contribution is narrow down to instead of using exploitation and exploration neural networks [1], the authors constructed exploitation and exploration graph neural networks (GNNs) to solve the problem. Specifically, those graphs are weighed graphs in which each edge weight is an exploitation/exploration score. 
2. Figure 2 shows cumulative regrets on four datasets: two from recommendation and two from classification. While they all show good results, it’s not trivial to understand why the ‘curves’ have much difference for the two recommendation datasets (i.e., almost linear) compared to the two classification datasets. Section 5.2 should give more detailed explanation and analyses. Why this method focuses particularly to personalized recommendation? Can it be generalized to other tasks?
3. While the authors provided multiple remarks and theoretical analyses on the complexity, I believe it would be better if the authors could also provide the run time of GNB and all the baselines. This is for us to have an overview if we should use the proposed method, or a single-bandit setting such as [1] is good enough, given that they all have similar bound. Moreover, I believe it could also give the readers a benchmark given the resources in Appendix I.
4. Figure 7 (Cumulative regrets for different exploration coefficients alpha) and Figure 8 (Figure 8: Cumulative regrets for different neighborhood hops k) show similar results. Thus, should we also study the relationships between alpha and k? 
5. Also, according to Figure 8 and Appendix B.7, learning with 1-hop is good enough, and larger k (k=2,3) could potentially lead to over-smoothing problem. With this observation, it leads to a question that do we really need to build graphs for exploitation and exploration dilemma in the context of personalized recommendation? Building large-scale graphs in practice are also expensive even if we can use user neighbourhood approximation such as Appendix B.4. Please give more explanation/discussion.

Minor:

1. I think the title should be more specific towards recommendation instead of only “Graph Neural Bandits”
2. Appendix H Technical Lemmas is redundant in my opinion


Overall, I am personally a bit concerned about the paper’s novelty (i.e., contribution). 

[1] Ee-net: Exploitation-exploration neural networks in contextual bandits. ICLR 2022.

[2] Neural collaborative filtering bandits via meta learning. ArXiv 2022.

clarity,_quality,_novelty_and_reproducibility: In my opinion, the contribution is limited as the paper is developed based on [1, 2], which made the contribution is incremental. It seems to me that the contribution is narrow down to instead of using exploitation and exploration neural networks [1], the authors constructed exploitation and exploration graph neural networks (GNNs) to solve the problem. Please see my comments/concerns in the Strength And Weaknesses section.

[1] Ee-net: Exploitation-exploration neural networks in contextual bandits. ICLR 2022.

[2] Neural collaborative filtering bandits via meta learning. ArXiv 2022.
summary_of_the_review: Overall, I am personally a bit concerned about the paper’s novelty (i.e., contribution). The authors did great job about the experiments and theoretical analyses, but some minor parts could be improved. 

=====

Increase my score from 3 to 6 after the rebuttal
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors present a novel Graph Neural Bandit (GNB) method to model the fine-grained user collaborative effects where the user correlation is formulated on the user graph.  A GNN-based bandit algorithm is proposed to achieve adaptive exploration. The authors proved an $O(\sqrt{T\log(Tn}) $ regret bound of the proposed algorithm. Experiments on real-world data showed its efficiency compared with state-of-the-art algorithms.

There are multi-round extensive discussions between authors and reviewers. The reviewers all agree that the setting is interesting and proposed GNN-based bandit algorithm is novel. The reviewers raised several concerns.  While some concerns are resolved and reviewers increased scores for that, the following concerns are remaining: 1. space and time complexity are high, which may prevent the algorithm to be applied in practice; 2. the 'linear-like' regret curves are hard to explain; 3. the design and advantage of k-hop for information propagation are unclear. The authors are encouraged to improve the paper according.
justification_for_why_not_higher_score: There are multi-round extensive discussions between authors and reviewers. The overall rating increased from 4.25 to 5.75 during the discussion period. There are some remaining concerns such as 1. space and time complexity are high, which may prevent the algorithm to be applied in practice; 2. the 'linear-like' regret curves are hard to explain; 3. the design and advantage of k-hop for information propagation are unclear. Others concerns are mostly resolved and reviewers increased scores accordingly.
Decision: Reject