Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose a novel bandit sampler, addressing the limitations of the previous work, for graph neural networks. The previous work utilized EXP3 which as known issues with low probabilities (variance can be really high) and leads to small learning rate. The regret bound was given in terms of a static oracle instead of a dynamic one. Also, the plays are considered in the oblivious adversary setting. 
These issues are addressed in the current work by rethinking the reward function. Experimental results are shown on a wide variety of datasets as well as GNN architectures to validate the proposed algorithm.


main_review: The paper is clearly written to highlight the issues with the previous approach and the novel contributions of this work and validation via experiments.

Pros:

(A) Fixes the issues with the BanditSampler algorithm especially with regard to dynamic regret and numerical instability issues.
(B) Improvements on some of the datasets such as Chameleon and Squirrel datasets shows significant improvements in performance. 

Cons/Questions:

(1) The main contribution seems to be rethinking the reward function and the rest follows by incorporating this into the BanditSampler algorithm previously introduced. 
(2) How about replacing the EXP3 with an implicit version such as EXP3-IX for exploration? Will that fix the numerical issues? 
(3) In some of the datasets, the improvement in performance is negligible. Can we hypothesize on which graphs would the proposed approach work better than others? Also, which is the unsampled version in the Table 2? If it is Vanilla GCN, it seems that the full averaging is worse than the sampled version but  Figure 3 shows an improvement over the sample size 'k'. So, it there an optimal selection of 'k'?  
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose Thanos, a bandit-based approach for subsampling graph neighbourhoods, to be used as context for graph neural network predictions. It improves on the prior art (BanditSampler) by proposing trading off increased reward bias for less variance. This allows the authors to reduce numerical optimisation issues, achieve competitive benchmarking performance, as well as explicitly take into account the GNN training dynamics in their theoretical analysis, demonstrating near-optimal regret (with an added ln T factor).
main_review: While I found the paper very information dense and hard to follow (the lack of illustrative figures up to page 7 proved quite telling here), I was left convinced by the authors' proposed method, both in terms of claimed theoretical benefits and empirical outperformance. The baseline comparisons are relevant and demonstrate meaningful returns on strong benchmarks. All in all, the method has potential for becoming an important direction for graph subsamplers, making it relevant for a substantial amount of GNN researchers and industrial appliers of the technology.

I must stress that I am not an expert on bandits, and hence am taking most of the theoretical results at face value. My review score is primarily based on the model's empirical performance and choice of comparisons performed, and the final assessment should ideally be combined with feedback from a domain expert. 

From my view, the authors build up on a previous NeurIPS paper, extend it significantly from the theory side, and then show a few expected results on standard benchmarks, which illustrate its utility for graph representation learning researchers. I think that such improvements are very useful, and therefore I suggest (weak) acceptance, and would be happy to see this paper at the conference. But the paper's key contributions are not on graph representation learning (my area of expertise) and therefore I cannot give a high confidence score. In either case I would strongly recommend the authors to revise the clarity of their method (ideally by adding more figures earlier on), and making it more accessible to non-domain-experts.

Minor typo: 'Dyanmic policy' in Table 1.
limitations_and_societal_impact: No concerns.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper tackles the high variance issues of the existing sampling methods, which approximate the full-graph training of GNNs. The proposed method is built upon existing work that treats GNN neighbor sampling as a multi-armed bandit problem. The authors design a novel biased reward function to reduce variance and avoid numerical instability. The proposed reward function leads to a more meaningful notion of regret directly connected to sampling approximation error. Based on that, the authors prove that the regret of the proposed algorithm is near-optimal and demonstrate the fast convergence of the sampling approximation error. Empirical results verify that the proposed algorithm, Thanos, has improved variance estimates and performance across benchmarks over BanditSampler and others.
main_review: ----------Strengths----------

(1) This work is built upon the bandit formulation of GNN sampling proposed by Liu et al. [1]. With a detailed analysis of the limitations of BanditSampler in [1] in Section 2.3, the authors propose a newly-designed reward function to address the issues. The proposed algorithm differs from the BanditSampler as it has near-optimal regret while accounting for the GNN training dynamics.

(2) The proposed algorithm, Thanos, is theoretically motivated and justified. Thanos is near-optimal, which is theoretically supported by the regret bound (Theorem 3 in the paper). Moreover, we can verify its improvement over BanditSampler in terms of sampling approximation error and final performance.

(3) Overall, the paper is well written and reasonably polished. The motivations, formulations, and theoretical analysis are presented in detail within the paper. As a small suggestion, it might be a good idea to spend a little more space on the fundamental idea of the multi-armed bandit formulation of neighbor sampling in the introduction for readers who have not heard of it before.

(4) I think the proposed algorithm and theoretical analysis are novel and valuable contributions to the multi-armed bandit problem of GNN sampling. The thoughtful analysis of the limitations of BanditSampler and the proposed solution advanced the state of the art of GNN sampling problem.

----------Weaknesses----------

(1) The authors have justified the improvement of Thanos over BanditSampler empirically. However, the empirical comparisons with other well-known sampling methods, including ClusterGCN [2] and GraphSAINT [3], are a bit insufficient, especially on models other than GCN.

(2) Moreover, I recommend the authors provide some analysis of the efficiency of the proposed algorithm in terms of both theoretical time/space complexities and empirical evaluations.

----------Overall----------

Overall, this work is an interesting and important improvement over the BanditSampler in [1]. The theoretical drawbacks of BanditSampler are fixed, and the authors prove the worst-case regret is near-optimal under mild conditions. Hence, I recommend acceptance.

----------References----------

[1] Liu, Z., Wu, Z., Zhang, Z., Zhou, J., Yang, S., Song, L. and Qi, Y., 2020. Bandit Samplers for Training Graph Neural Networks. Advances in Neural Information Processing Systems, 33.

[2] Chiang, W.L., Liu, X., Si, S., Li, Y., Bengio, S. and Hsieh, C.J., 2019, July. Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (pp. 257-266).

[3] Zeng, H., Zhou, H., Srivastava, A., Kannan, R. and Prasanna, V., 2019. Graphsaint: Graph sampling based inductive learning method. arXiv preprint arXiv:1907.04931.
limitations_and_societal_impact: The potential negative social impact of the work is not presented in the paper. Although the reviewer does not foresee any potential negative impacts, the authors are encouraged to add such discussions if space permits.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes an adaptive neighbor sampling method for graph neural networks applied to large graphs. This method is based on Rexp3, an adversarial bandit algorithm. Central to it is a novel reward, which unlike previous work induces a biased sampler, which is shown to have a near optimal regret. Even though it is biased, this sampler makes up for it by having better numerical stability, requiring less unrealistic assumption for the bound, and having provably faster convergence to variance reduction of the estimator.

Empirically, the paper confirms that the behavior of the proposed method matches theoretical predictions and performs better than a more naive bandit approach on a toy graph problem and Cora. Large scale experiments are then conducted on several standard benchmarks where the proposed methods appears to outperform baselines.
main_review: This paper tackles a relatively specific problem in GNNs: it upgrades an existing Bandit component by simply proposing a new reward scheme. This reward scheme is very well motivated -- this is perhaps the strongest part of the paper -- and as far as I know is entirely novel.

Empirically, it is also very valuable that the predictions made by looking at the theory are verified. One problem there is that it seems all these experiments are run with only one seed; it is important to use multiple runs to be able to make stronger quantitative statements.

In terms of benchmark datasets, while it seems correct that this method beats its baselines, the magnitude of improvement seems fairly limited. I am also a bit surprised by the small magnitude of the standard deviation (assuming this is what is reported in Table 2), and since the number of seeds is not specified, it's not clear to me that the improvement is statistically significant in some cases.

The paper was fairly well written and easy to understand, although it felt very dense and with some proof-reading it seems possible to improve clarity.

In terms of significance, this paper offers a well motivated improvement to GNNs, which improves performance on benchmarks somewhat. It shows that the desire for unbiasedness in samplers may be unnecessary, and that previously proposed methods are not robust to certain issues. While I think this paper is unlikely to have a large impact, it may help in practice and offers an interesting direction for future work on this problem.

Comments:
- This might be a flaw in all samplers, I'm not familiar enough with the literature to know, but is it possible that considering only the variance of the embedding estimator causes learning issues? The backward pass is not considered, which possibly induces undesireable bias in the model, as some neighbors may have a small forward pass contribution but require a large credit assignment.
- l.74 "Recursive neighborhood expansion will cover a large portion of the graph if the graph is dense or scale-free even within a few layers." I'm not sure I understand what is being claimed here. Is this a computational argument or a variance argument? I understand that error will compound after several layers, but computationally there is no two-hop query of neighbours/no graph recursion.
- l.117 "especially in the case that the neighbors" -> "especially when neighbors"
- l.120 "to choose quite small temperature" -> "to choose a quite small temperature"
- l.138 "independent with" -> "independent from"
- l.145 This was a bit hard to parse: "we are the first to explicitly account for training dynamic in deriving reward variation and further regret bound in non-oblivious setting, and without this consideration no meaningful bound can possibly exist" I'd suggest writing e.g. "we are the first to explicitly account for training dynamics when deriving the reward variation and the improved regret bound. Without this consideration that we are in the non-oblivious setting, no meaningful bound can possibly exist".
limitations_and_societal_impact: There are no mentions of potential negative societal impacts, but this is fairly abstract work. As an exercise, the authors may want to situate the impact of large scale graph neural networks on society.
review_title: null

Meta-review: This paper proposes a novel bandit algorithm for sampling neighbourhoods for GNNs. The reviewers agreed that the work was of good quality, significance and originality. Some reviewers noted, and the authors are encouraged to take on board, that the current write up is quite dense and exposition could be improved by addressing this.
Decision: Accept (Poster)