A Biased Graph Neural Network Sampler with Near-Optimal Regret
Authors: Qingru Zhang
David Wipf
Quan Gan
Le Song
Venue: NeurIPS 2021 Poster (2021)
Keywords: Graph Neural Network
Neighbor Sampling
Multi-Armed Bandit

Abstract: Graph neural networks (GNN) have recently emerged as a vehicle for applying deep network architectures to graph and relational data.  However, given the increasing size of industrial datasets, in many practical situations, the message passing computations required for sharing information across GNN layers are no longer scalable. Although various sampling methods have been introduced to approximate full-graph training within a tractable budget, there remain unresolved complications such as high variances and limited theoretical guarantees.  To address these issues, we build upon existing work and treat GNN neighbor sampling as a multi-armed bandit problem but with a newly-designed reward function that introduces some degree of bias designed to reduce variance and avoid unstable, possibly-unbounded pay outs.  And unlike prior bandit-GNN use cases, the resulting policy leads to near-optimal regret while accounting for the GNN training dynamics introduced by SGD. From a practical standpoint, this translates into lower variance estimates and competitive or superior test accuracy across several benchmarks. 

A Biased Graph Neural Network Sampler with Near-Optimal Regret
Qingru Zhang
David Wipf
Quan Gan
Le Song 4.3
Georgia Institute of Technology
2 Amazon Shanghai AI Lab
3 Mohaamed bin Zayed University of Artificial Intelligence qingru. zhangggathhe edu, daviwipf@amazon com quagan@amazon. com, le. se.ong@mmzuai. ac.ae
Abstract
Graph neural networks (GNN) have recently emerged as vehicle for applying deep network architectures to graph and relational data. However, given the increasing size of industrial datasets, in many practical situations the message passing computations required for sharing information across GNN layers are no longer scalable. Although various sampling methods have been introduced approximate full-graph training within tractable budget, there remain unresolved complications such as high variances and limited theoretical guarantees. To address these issues, we build upon existing work and treat GNN neighbor sampling a multi-armed bandit problem but with a newly-designed reward function that introduces some degree of bias designed to reduce variance and avoid unstable, pay outs. And unlike prior bandit-GNe use cases, the resulting policy leads to near-optimal regret while accounting for the GNN training dynamics introduced by SGD. From a practical standpoint, this translates into lower variance estimates and competitive superior test accuracy across several benchmarks.
Introduction
Graph convolution networks (GCN) and Graph neural networks (GNN) in general 21 17 have recently become powerful tool for representation learning for graph structured data 6 2 33 These neural networks iteratively update the representation message passing operator which aggregate the embeddings of the neighbors of the node, followed by a non-linear transformation. After stacking multiple graph convolution layers, these models can learn node representations which can capture information from both immediate and distant neighbors.
node using a graph convolution operator or
GCNs and variants 33 have demonstrated the start-of-art performance in a diverse range of graph 15 23
learning prolems 17 3
However, they face significant computational challenges given the increasing sizes of modern industrial datasets. The multilayers of graph convolutions is equivalent recursively unfold the neighbor aggregation in top-down manner which will lead to an exponentially growing neighborhood size with respect to the number of layers. If the graph is dense and scale-free, the computation of embeddings will involve a large portion of the graph even with a few layers, which is intractable for large-scale graph 21 34
30
13
Several sampling methods have been proposed alleviate the exponentially growing neighborhood
sizes, including node-wise sampling 17. 24 layer-wise sampling B 37 20 and subgraph
sampling [10 35| [9]. However, the optimal sampler with minimum variance is function of the neighbors' embeddings unknown apriori before the sampling and only partially observable for those sampled neighbors. Most previous methods approximate the optimal sampler with static distribution
which cannot reduce variance properly. And most of existing approaches g 37
10
35
19
"oorrsponniig author. Work done during the internship Amazon Shanghai Al Lab.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

do not provide any asymptotic convergence guarantee on the sampling variance. We are therefore less likely be confident of their behavior as GNN models are applied to larger and larger graphs. Recently, Liu et al. [24] propose a novel formulation of neighbor sampling as a multi-armed bandit problem (MAB) and apply bandit algorithms to update sampler and reduce variance. Theoretically, they provide an asymptotic regret analysis on sampling variance. Empirically, this dynamic sampler named as BanditSampler is more flexible to capture the underlying dynamics of embeddings and exhibits promising performance in variety of datasets.
However, we will show in Section 2.3 that there are several critical issues related to the numerical stability and theoretical limitations of the BanditSampler [24]. First, the reward function designed is numerically unstable. Second, the bounded regret still can be regarded as linear function of training horizon T. Third, their analysis relies on two strong implicit assumptions, and does not account for the unavoidable dependency between embedding-dependdnt
dependent rewards and GNN training dynamics.
In this paper, we build upon the bandit formulation for GNN sampling and propose a newly-designel reward function that trades bias with variance. In Section [.1] we highlight that the proposed reward has the following crucial advantages: (i) It is numerically stable. (ii) It leads to more meaningful notion of regret directly connected to sampling approximation error, the expected error between aggregation from sampling and that from full neighborhood. (iii) Its variation can be formulated by GNN training dynamics. Then in Section 3.2 we clarify how the induced regret is connected to sampling approximation error and emphasize that the bounded variation of rewards is essential to derive a meaningful sublinear regret, i.e., a per-iteration regret that decays to zero as T becomes large. In that sense, we are the first to explicttly account for GNN training dynamic due to stochastic gradient descent (SGD) so as to establish a bounded variation of umbedding-deeendeer rewards, which we present in Section 3.3
Based on that, in Section 4 we prove our main result, namely, that the regret of the proposed algorithm as the order of (I'v In 2/3/ which is near-optimal and manifest that the sampling approximation error of our algorithm asymptotically converges to that of the optimal oracle with the near-fastest rate. Hence we name our algorithm as Thanos from "Thanos Has A Near-Optima. Sampler". Finally, empirical results in Section 3 demonstrate the improvement of Thanos over BanditSampler and others in terms of variance reduction and generalization performance.
2 Background
2.1 Graph Neural Networks and Neighbor Sampling
Graph Neural Networks. Given graph G (V,E), where V and & are node and edge sets respectively, the forward propagation of a GNN is formulated as h (1+1) = o(EiN, anch w())
for the node v E V at training iteration t. Here h E Id is the hidden embedding of node i at the layer/ L, (0) = x; is the node feature, and ar-) is the activation function. Additionally, N₂ is the neighbor set of node v, D, = -Wal is the degree of node v, and aes > 0 is the edge weight between node and i. And w/ dxd is the GNN weight matrix, learned by minimizing the stochastic loss ž with SGD. Finally, we denote x = h (!) as the weighted embedding, [D,] = {il 1 < D.). and for vector E do, we refer to its 2-norm as ||æe|]; for matrix W. its spectral norm is |[W]].
Neighbor Sampling. Recursive neighborhood expansion will cover a large portion of the graph if the graph is dense or scale-free even within a few layers. Therefore, we consider to neighbor sampling methods which samples A neighbors under the distribution Pt, to approximate ΣiEN. Zig with this
(!)
(!) subset S. We also call Pe.t the policy. For ease of notation, we simplify Pv, as Pt = l E NN); (1) pir is the probability of neighbor i to be sampled. We can then approximate p = Eie,, 20 with an unbiased estimator p( 1 Eies, 2!//Dr.. As it is unbiased, only the variance term Vp, (p!)) need to be considered when optimizing the policy Pt- Define the variance term when & = 1 as
V pp. Then following (29). Vp. (P!)) = V p.p/ with Vp. decomposes V V. V.- with V. ΣiEN, ||= (1) (2//1/// /P/,.c which is dependent on pt and thus refereed as the effective variance. And
V. 1EjEN. 2/,
(0) 12 is independent on the policy and therefore referred to as constant variance.

---

AS HIRE stop
Node-wlie neighbar samrlling
Arm
PAST MOR!
Updatic to minintie regret
Upddat to minimite varliance
PRA
Policy
Sumple 5, via Ph
Gambler's pollcy Ps:
Pull Arm (fs)
(a) Adversary Multi-Armed Bandit.
(b) Formulate neighbor sampling as a MAB problem.
Figure I: Fig. la visualizes the pipeline of adversary multi-armed bandit, in which, the reward is prior unknown, non-stationary and only partially observable for the pulled arms. It motivates us to formulate the neighbor sampling as MAB problem (Fig. lb
2.2 Formulate Neighbor Sampling as Multi-Armed Bandit
The optimal policy in terms of reducing the variance Vp, is given by P.., EIEN. |
(29
However, this expression is intractable to compute for the following reasons: (i) It is only after
sampling and forward propagation that we can observe (!))
(!) Zi,e" and zi,t changes with time along an
optimization trajectory with unknown dynamics. (ii) Zi, is only partially observable in that we cannot see the embeddings of the nodes we do not sample. While static policies [7 37 are capable of dealing with (ii), they are not equipped to handle (i) as required to approximate pf and reduce the sampling variance effectively. In contrast, adversarial MAB frameworks are capabable of addressing environments with unknown, non-stationary dynamics and partial observations alike (See Fig I.. The basic idea is that a hypothetical gambler must choose which of K slot machines to play (See Fig. Tap. For neighbor sampling, K is equal to the degree D. of root node At each time step, the gambler takes an action, meaning pulling an arm I, E [K] according to his policy and then receives reward rr, To maximize cumulative rewards, algorithm is applied update the policy based on the observed reward history {ri, T = ().
(1)
Liu et al. (24] formulate node-wise neighbor sampling as a MAB problem. Following the general strategy from Salehi et al. [29] designed reduce the variance of stochastic gradient descent, they apply an adversarial MAB to GNN neighbor sampling using the reward
Tiaa V pr., (p ||= /
which is the negative gradient of the effective variance w.r.t. the policy. Since Ve(pt) V Vo(ri) S
(p. př, pp. Ve())), maximizing this reward over a sequence of arm pulls, i.e., Σt= rT is more-or-less equivalent to minimizing an upper bound on Σ Ve(p.) - Ve(p,). The actual policy is then updated using one of two existing algorithms designed for adversarial bandits, namely Exp3 [ and Exp3.M [3I] Please see Appendix([]oor details. Finally, Liu et al. (24) prove that the resulting BanditSampler can asymptotically approach the optimal variance with factor of three:
(2) Critically however, this result relies on strong implicit assumptions, and does account for the unavoidable dependency between the reward distribution and GNN model training dynamics. We elaborate this and other weaknesses of the BanditSampler next.
Σ Ve(pi) S <3 3. Ve(p;) + 10/TDA (nDD//k)/>>
2.3 Limitation of BanditSampler
Updated by Exp3, BanditSampler as described sufficiently flexible to capture the embeddings' dynamics and give higher probability to ones with larger norm. And the dynamic policy endows it with promising performance on large datasets. Moreover, it can be applied not only GCN but GAT models 32). where a change with time as well. It is an advantage over previous sampling approaches. Even so, we still found several crucial drawbacks of the BanditSampler.
Numerical Instability Due the Pt, in the denominator of (T. the reward of BanditSampler suffers from numerical instability especially when the neighbors with small Pt, are sampled. From Fig. [a (in Appendix), we can observe that the rewards 11 of BanditSampler range between a large scale. Even though the mean of received rewards is around 2.5, the max of received rewards can attain 1800. This extremely heavy tail distribution forces us to choose a quite small temperature hyperparameter (Algorithm and in Appendix C), resulting in dramatic slowdown of the policy optimization. By
3

---

contrast, the reward proposed by us in the following section is more numerically stable (See Fig. 56 in Appendix) and possesses better practical interpretation (Fig. 2ch.
Limitation of Existing Regret and Rewards There are two types of regret analyses for bandit algo- rithms I AA:: (i) the weak regret with a static oracle given by R(T) = maxje [D,] (2tm [[[,,])) - Ei [()r,,)), which measures performance relative pulling the single best arm; and (ii) the worst- [.] (a.)
I
Σ Elr,,.). where the oracle can pull the best arm at each t. When the growth of the regret as function of T is sublinear, the policy is long-run average optimal, meaning the long-run average performance converges to that of the oracle. But from this perspective, the bound from 2 can actually function more like worst-case regret. To see this, note that the scale factor on the oracle variance is 3, which implies that once we sub- tract Ve (p()) from the upper bound, the effective regret satisfies R(T) I $2E Ve(pt) + O(VT). By substituting P into Ve, we obtain Ve(pt) = EiEN, Σ 1| Il| (ill which can be regarded as a constant lower bound given the converged variation of Zi,t (Lemma TT. Consequently, the regret is still linear about T. And linear worst-case regret cannot confirm the effectiveness of policy since uniform random guessing will also achieve linear regret.
case regret with a dynamic oracle given by R(T) Σi= maxje[D.) E[r
Crucial Implicit Assumptions There are two types of adversaries: if the current reward distribution is independent with the previous actions of the player, it is an oblivious adversary; otherwise, it is a non-oblivious adversary 77. GNN neighbor sampling is apparently non-oblivious setting but it is theoretically impossible to provide any meaningful guarantees the worst-case regret in the non-oblivious setting (beyond what can be achieved by random guessing) unless explicit assumptions made reward variation [4. BanditSampler [24] circumvents this issue by implicitly assuming bounded variation and oblivious setting (See Appendix H). but this cannot possibly be true since embedding deiiidenn rewards must depend training trajectory and previous sampling. In contrast, we are the first to explicitly account for training dynamic in deriving reward variation and further regres bound in non-oblivious setting, and without this consideration no meaningful bound can possibly exist.
3 Towards a More Meaningful Notion of Regret
To address the limitations of the BamditSa we need a new notion of regret and the corresponding reward upon which it is based. In this section we motivate new biased reward function, interpret the resulting regret that emerges, and then conclude by linking with the GCN training dynamics.
3.1 Rethinking the Reward
Consider the following bari-nar decomposition of approximation error:
_ 11 = =Ilm4 Erp!! + Vp. (p!")) & Bias( + Vp. (P..)
p. Prior work has emphasized the enforcement of zero bias as the starting point when constructing samplers; however, we will now argue that broader estimators that do introduce bias should be reconsidered for the following reasons: (i) Zero bias itself may not be especially necessary given that even an unbiased T will become biased for approximating (+11) once it is passed through the non-linear activation function. (ii) BanditSampler only tackles the variance reduction after enforcing zero bias in the bias-variance trade-off. However, it is not clear that the optimal approximation error must always be achieved via zero bias estimator, i.e., designing the reward to minimize the approximation error in aggregate could potentially perform better, even if the estimator involved is biased. (iii) Enforcing unbiased estimator induces other additional complications: the reward can become numerically unstable and hard to bound in the case of a non-oblivious adversary. And as previously argued, meaningful theoretical analysis must account for optimization dynamics that fall under the non-oblivious setting. Consequently, to address these drawbacks, we propose to trade
variance with bias by adopting the biased estimator: Pu. k
(!) D. Eies, Zi,t and redefine the reward:
(1)
Pi, = 2z (() (1)
(1) 2,00
z(0) = M D. uut D.
1 (1)
with
5.
(3)
JEN.
Equation 3 is derived by weighting the gradient of bias and variance w.r.t. Pı.t equally, which delegate to Appendix. Additionally, because of partial observability, we approximate z(1 with (.) We also noticed, due to the exponential function from the Exp3 algorithm (see line
Eies, z

---

6, Algorithm B). the negative rewards of some neighbors will shrink wi, considerably, which can adversely diminish their sampling probability making it hard sample these neighbors again. Consequently, to encourage the exploration on the neighbors with negative rewards, we add ReLU function over rewards (note that our theory from Section reward is then formulated as
4 will account for this change). The practical
Ti, = ReLU 22
(22 ()) Σ jes
1 1_00 " - - h
The intuition of (3) and by extension is that the neighbors whose weighted embeddings x are closer to 2 will be assigned larger rewards (See Fig. 2c). Namely, our reward will bias the policy towards neighbors that having contributed to the accurate approximation instead of ones with large norm as favored by BanditSampler. And in the case of large but rare weighted embeddings far from _ BanditSampler tends to frequently sample these large and rare embeddings, causing significant deviations. The empirical evidence is shown in Section 5.3
The reward S possesses following practical and theoretical advantages, which will be expanded more in next sections:
Since it is well bounded by Ti.a = | 12 - s ( I1, the proposed reward is more numerical stable as we show in Fig. (See Appendix).
It will incur a more meaningful notion of regret, meaning the regret defined by (3) is equivalent to the gap between the policy and the oracle w.r.t. approximation error.
The variation of reward (3) is tractable to bound as a function of training dynamics of GCN in non-
oblivious setting, leading to a provable sublinear regret as the order of (D, In D,) (T (TV/ //n /
which means the approximation error of policy asymptotically converges to the optimal oracle with a factor of one rather than three.
3.2 Interpreting the Resulting Regret
We focus on the worst-case regret in the following analysis. The regret defined by reward
3 is
directly connected to approximation error. More specifically, notice Ti, = -1 =!![|
|| 11. Since | 2 will be canceled out in R(T), have R(T) Σ (B I1.t =!!!!??
max)](DD]] [I| 2 and the latter is that of the optimal oracle. Consequently, the regret defined by (3) is the gap between the policy and the optimal oracle w.r.t. the approximation error.
(1) 1?). where the former term is the expected approximation error of the policy
Then clarify how to bound this regret. The worst-case regret is a more solid guarantee of optimality than the weak regret. Even though some policies can establish the best achievable weak regret O ((VT), their worst-case regret still be linear. This is because the gap between static and dynamic oracles can be linear function of ' if there is constraint on rewards. For example, consider the following worst-case scenario. Given three arms (i1, i2, ia). at every iteration, one of them will be assigned a reward of 3 while the others receive only 1. In that case, consistently pulling any arm will match the static oracle and any static oracle will have a linear gap with the dynamic oracle. Hence it is impossible to establish a sublinear worst-case regret unless additional assumptions are introduced on the variation of the rewards to bound the gap between static and dynamic oracles 4). Besbes et al. claim that the worst-case regret can be bounded as function of the variation budget:
Σ sup (.(D.]
E BlP E[Fa.]] S VT
(5)
where VT is called the variation budget. Then, Besbes et al. 4 derived the regret bound as RR(T) O(K In K. 22/33/2/3) for Rexp3. Hence, if the variation budget is a sublinear function of T the given environment, the worst-case regret will be sublinear as well.
To fix the theoretical drawbacks of BanditSampler, we first drop the assumption of oblivious adversary, ie. considering the dependence between rewards and previous sampling along the training horizon of GCN. Then to bound the variation budget, we account for GCN training dynamic in practically- meaningful setting (i.c. no unrealistic assumptions) as described next.
3.3 Accounting for the Training Dynamic of GCN
One of our theoretical contributions to study the dynamics of embeddings in the context of GNN training optimized by SGD. We present our assumptions as follows:
5

---

Lipschitz Continuous Activation Function: Va, y, - - Co and o(0) = 0.
Bounded Parameters: For any 1 S < and 0 S l < L - 1, 11,, / s Cs.
Bounded Gradients: For 1 t - T. EC, such that lIV VV w G - Cg.
Besides, given the graph 9 and its feature X, since oni is fixed in GCN, define C. max.ev DiEN, Og122i1- Define D = max D.,, A = max,,i Ovs. G = CoCoDA and
A wwx.gv/al 2,141 - 2,,el For SGD, we apply the learning rate schedule as Oz = 1/t. The above assumptions are reasonable. The bounded gradient is generally assumed in the non-convex/convex convergence analysis of SGD [25 28]. And the learning rate schedule is necessary for the analysis of SGD to decay its constant gradient variance [16]. Then we will bound Ai,, as a function of gradient norm and step size by recursively unfolding the neighbor aggregation.
Lemma 1 (Dynamic of Embedding). Based on our assumptions on GCN. for any E V at the layer I, we have:
| S Cr,
S C2,
(6)
where C= Gi GC--AC,COC, and C, = 3C?. Then, consider the training dynamics of GCN optimized by SGD, For any node i V at the layer we have
(1)
2/00
max EV
F1,+1
Lemma is obtained by recursively unfolding neighbor aggregations and training steps, and can be generally applied to any GCN in practical settings. Based on it, we can derive the variation budget of reward 3 and (4) as a function of Ai, in the non-oblivious setup.
Lemma 2 (Variation Budget). Given the learning rate schedule of SGD as az = 1/t and our assumptions the GCN training, for any T 2 2, any V, the variation of the expected reward in and 4 can be bounded as:
Σ B[ra,+1] Braa
S VT VT= C. In
Σ
B[ EFr.d] S VT C, In
(8)
where C. = 12 -
The derivation of Lemma is attributed to that our reward variation can be explicitly formulated as a function of embeddings' variation. In contrast, Pt. emerging in the denominator of ( incurs not only the numerically unstable reward but hardship to bound its variation. More specifically, pi is proportional to the summation of observed reward history of neighbor i, which is hard to bound due to the complication to explicitly keep track of overall sampling trajectory as well as its bilateral dependency with Pı.c- It is potentially why BanditSampler's 's regret (2) ignores the dependency between rewards and previous training/sampling steps. On the contrary, bound as a function embeddings' dynamic in practical non-oblivious setting, leading to a sublinear variation budget and further solid near-optimal worst-case regret as presented next.
rewards tractable to
Main Result: Thanos and Near-Optimal Regret
Algorithm 1 Thanos
1: Input: > 0, y E 10, G, fas
2: Initialize: For any E V. any i No, set P..1 1/D
3: for ( = 1,,,...,,
4: Reinitialize the policy every AT steps: Yu V. E No, Pi, 1//
5: Sample neighbors with and estimate Poe with the estimator p. D. Eies, Zi,1'
!1)
6: Forward GNN model and calculate the reward ri. according to (4)
7: Update the policy and optimize the model following [24] using 77, 7, and {ar)-
8: end for
Algorithm I presents the condensed version of our proposed algorithm. See Algorithm Ap- pendix B for the detailed version. Besides the trade-off between bias and variance, and exploration and exploitation, our proposed algorithm also accounts for third trade-off between remembering and forgetting: given the non-stationary reward distribution, while keeping track of more observations

---

can decrease the variance of reward estimation, the non-stationary environment implies that "old" information is potentially less relevant due to possible changes the underlying rewards. The changing rewards give incentive to dismiss old information, which in turn encourages exploration. Therefore, we apply Rexp3 algorithm to tackle the trade-off between remembering and forgetting by reinitializing the policy every AT steps (line 4 in Algorithm D.
Then, we present our main result: bounding the worst-case regret of the proposed algorithm:
T
T
R(T) =
Eirael
[r
ELEEN
t=1 TES,
where NE argmax CAN EIEN, E(rca), W k. Because we consider the non-oblivious ad- versary, E|rr is taken over the randomness rewards caused by the previous history randomized arm pulling. E [rr,a] is taken over the joint distribution of the action sequence S2,., ST).
Theorem 3 (Regret Bound), Consider Algorithm 7 the neighbor sampling algorithm for training GCN. Given either 3 or as reward function, we can bound its regret as
follows. Let AT = In In
and y =
- Co
min(1, v (ex)(C.)-1)D,, In),,, In(D./k) Given the variation budget in (8. for every T 2 DT 2 2, 2kC,T have the regret bound for either (4
R(T) S C(D, D.) (TVinT)
(10)
where C is a absolute constant independent with D, and T.
The obtained regret is as the order of (D, In (TV (ITVI)))/// According to Theorem in [4] the worst-case regret of any policy is lower bounded by O((DDV)))/37)) suggesting our algorithm near-optimal (with modest In T factor from optimal). In that sense, name our algorithm as Thanos from "Thanos Has A Near-Optimal Sampler."
The near-optimal regret from Theorem can be obtained due to the following reasons: (i) Our proposed reward leads to a more meaningful notion regret which directly connected to approxi- mation етror. (ii) Its variation budget is tractable to be formulated by the dynamic of embeddings. (iii) We explicitly study training dynamic of GCN bound embeddings' dynamic by recursively unfolding the neighbor aggregation and training steps in the practical setting.
As mentioned in Section 3.2 the regret based on rewards 33) is equivalent to approximation error The result of Theorem says the approximation error of Thanos asymptotically converges that of the optimal oracle with the near-fastest convergence rate. In the case of enforcing zero bias like BanditSampler, sampling variance is the exact approximation error. However, even if we ignore other mrentonly-mentionee limitations, its regret suggests the approximation error of their policy asymptotically converges to three (as opposed to one) times of the oracle's 's approximation error, so the regret is still linear. We compare the existing theoretical convergence guaratees in Table
Table I: Comparison of existing asymptotic convergence guarantees.
Dyanmic policy
Convergence smalysis
Theory accounts for practical training
Brand reward var- explicitly
Sublinear gap to optimul oracle
Stable ward/policy
Uniform policy BanditSampler Thanos
X
X
X
X X
X
X
/
5
Experiments
We describe the experiments to verify the effectiveness of Thanos and its improvement over Bandit- Sampler in term of sampling approximation error and final practical performance.
5.1 Illustrating Policy Differences via Synthetic Stochastic Block Model Data
As mentioned in Section
3.1 our reward will bias to sample the neighbors having contributed to
accurate approximation.
Fig. 2c is the visualization of this intuition: after setting &.,t (1,

---

0.8
0.85
6.8
0.7
6.0
0.6
0.75
25
17
0.70
-34
0.5
1-150
0
5.0
BanditSappier
0.4
0.60
200
4.00
600
800
200
400
600
800
(a) Average Pimm among Vi
Virain
(b) Test Accuracy
(c) Visualization of our reward
illustrate the policy difference and compare their practical performance via cSBM synthetic data. Fig. 2c plot our reward function after setting =(! = (1,
Figure 2: Figs. 2a and 2b
the reward inside the dashed circle is positive; otherwise negative. And the embeddings closer to u. will have larger rewards. In order to understand how this bias differentiates the policy of two samplers given different distribution of features and edges, we propose to use cSBM[14 [T] to generate synthetic graphs. We consider cSBM [4] with two classes, whose node set Vi and V/2 have 500 nodes. The node features are sampled from class-specific Gaussians N1, N2. We set feature size to 100, average degree 2d = 20, k 10, and μ 1, and we note that controls the difference between two Gaussian's ' mean [14. The average number inter-class and intra-class edges per node - X2 and d Ad respectively. Then, we scale down the node features of V by 0.1 to differentiate the distribution of feature norm and test the sampler's 's sensitivity to it. The configuration of training and samplers same as Section 5.4Jand listed in Appendix.
In the case of cSBMs, an ideal sampler should sample more intra-class neighbors than inter-class neighbors to get separalse embeddings and better classification. Thus, we inspect for each the i neighbors having the top-k highest sampling probability, and compute the ratio of intra-class
neighbors among them, i.e. Pintra Σ C.N.N. [(Vs = Uo) n (Pr.: is top-k) /))/ We report the average
of Pintra for V1 n Virain versus in Fig. 2a For the scaled community V1. Thanos will be biased to
sample more intra-class neighbors due the intuition explained by Fig. [c] leading more accurate approximation and improvement on test accuracy over BanditSampler as shown in Fig. Ba and 2b This claim holds true under different edge distributions (A E (0.5, 1.5)). We additionally report the results on unscaled V/2 for comparison in Appendix.
5.2
Evaluating the Sampling Approximation Error
Diference in Apprommattin Errer
0.65
GCN
6.2
GAT
0.60
0.0
0.55
-0.1
-0.2
Diterence
-0.2
0.45
2-0.50
250 500 750 1000 1250 1500
Iteaaion
lburation
Berraiio
(a) Comparison on cSBM data.
(b) GCN on CoraFull.
(c) GAT on CoraFuul.
Figure 3: Compare the approximation error between two samplers in cSBM synthetic graphs (Fig. 3a and
training of GCN (Fig. 3b) and GAT (Fig. 3c) on Cora. In Fig. 3b and 3c negative values indicate that Thanos has lower approximation
than BanditSampler.
We numerically compare the approximation error between two samplers in the training of GCN and GAT on Cora dataset from Kipf and Welling [2] as well as cSBM synthetic data in Section 5.1 At each iteration, given a batch nodes V,. at the top layer, we perform sampling with BanditSampler and Thanos respectively, getting two subgraphs Gb. and Goun. For Cora, we perform forward propagation on the original graph G as well as Ghs and Gour respectively with the same model
parameters (W(!) [e([)) and we get the accurate pl,tt of the first layer aggregation well as its
(!)
estimated values p!(t)) and (((orr) from both samplers. We compute dist,, Σ || |.,1
and distour = E.er, || -. ||. We set A: = 2, 0.1, 0.1 for Thanos, = 0.01 for BanditSampler (since its unstable rewards require smaller 17), ÅT 200, a, 0.001, = 2 and the dimension of hidden embeddings d = 16. Fig. plotss the mean and the standard deviation of Σ disto, with 10 trials. The mean curves of both GCN and GAT
Adiss DT -=| distour

---

below zero, suggesting Thanos establishes lower approximation enror in practice. For cSBM synthetic graphs, we follow the setting as Section S.T] compare two samplers under different edge distributions (A E (0.5, 1, 1.55) and directly plot E, distas (blue) and Σ, distour (red). From Fig. 3a we know
Thanos achieves quite lower approximation error and higher test accuracy (Fig. 2bb the setting of
less inter-edges (e.g. À= = 1 or 1.5) due to the intuition manifested by Fig. [c] whereas BanditSampler is biased to sample large-norm neighbors, resulting in high approximation error and degenerated performance. For small À 0.5, the almost-equal number of inter/intra edges will shift Mu,e to the unscaled community V22 Hence two samplers' approximation error are close.
5.3
Sensitivity to Embedding Norms
6500
4455
0.689
1420
0.585
0.574
20
4320
4202
4221 4222
6.568
9.675
0.56
0.570
4200
Tost
0.063
0.669
0.54
0.655
Band SSampae
Thanos
4000
Bard Sample
0.550
Samsle
(a) Times of sampling comupted nodes.
(b) Test Accuracy
(c) Test. Acc. vs, sample size
Figure 4: Fig. 4a plots the average number of times the corrunted/rescaled nodes were sampled per epoch by both samplers on corrupted CoraFull. And Fig- Abcompaees their corresponding test accuracy, suggesting the performance of BanditSampler will be degenerate by its sensitivity of embedding norm. Fig. shows the ablation study on sample size k with ogbn-arxiv.
Previously, we claim that BanditSampler will bias policy to the neighbors with large norm, potentially leading to severe deviation from f,, as well as a drop of performance. In this section, we present the evidence CoraFull [5) with corrupted features and demonstrate that algorithm resolves this issue. For CoraFull, we randomly corrupt 800 (roughly 5% of) training nodes by multiplying their features by 40. We both samplers 300 epochs with the corrupted CoraFull and count the total number of times that these corrupted nodes were sampled per epoch. We set k = 3, = 1, = 0.2 and the other hyperparameters the same as Section 5.4 We repeat 5 trials for each algorithm and report the average over epochs and trials. We also record the test accuracy with the best validation accuracy in each trial and report its mean across trials. From Fig. 4a we can tell BanditSampler biases to corrupted nodes, degenerating its performance more as shown in Fig. 4b
5.4 Accuracy Comparisons across Keal-World Benchmark Datasets
We conduct node classification experiments on several benchmark datasets with large graphs: ogbn- arxiv, ogbn-products (18), CoraFull, Chameleon [1] and Squirrel [27). The models include GCN and GAT. For GCN, we compare the test accuracy among Thanos, BanditSampler, GraphSage LADIES GraphSaint (35), ClusterGCN[I0 and vanilla GCN. For GAT, we compare test accuracy among Thanos, BanditSampler and vanilla GAT. The experimental setting is similar with Liu et al. 24 The dimension of hidden embedding d is 16 for Chameleon and Squirrel. 256 for the others. The number of layer fixed as 2. We set We searched the learning rate among {0.001, 0.002, 0.005, 0.01} and found 0.001 optimal. And we set the penalty weight of la regularization 0.0005 and dropout rate 0.1. We do grid search for sampling hyperparameters: 17, T, and AT and choose optimal ones for each. Their detailed settings and dataset split are listed in Appendix. Also we apply neighbor sampling for test nodes for all methods, which is consistent with prior LADIES and GraphSaint experiments, and is standard for scalability in practical setting. From Table 2 superior performance over BanditSampler for training GAT, and competitive or superior performance for training GCN.
for CoraFull; k = 5 for ogbn-arxin arxiv, Chameleon, Squirrel;
k 10 for
we can tell our algorithm achieves
5.5 Sample Size Ablation
To verify the sensitivity of Thanos w.r.t. sample size k; we compare the test accuracy between Thanos and BanditSampler as sample size k increases on Ogbn-arxiv. The other hyperparameter setting is the same as Section 5.4 We compare two samplers with 3, 5, 10, J: 15. The result from Fig. 4c suggests Thanos still exhibits mainfest improvement over BanditSampler as k increases.

---

Table 2: Test accuracy. 'x' means the program crashed after a few epochs due to the massive memory cost and segmentation fault TensorFlow. Bold indicates first; red second.
Test Accuracy
Methods
Chameleon
Squirrel
Ogbn-arxiv
CoraFull
Ogbn-products
Vanilla GCN
0.008(=0.021)
0.327(H0.023)
0.659
0.565(2000044)
GraphSage
0.009(=0.013)
0.385(+0.007)
0.554(20.004) 0.002)))
0.753(+0.002)
GCN
LADIES
0.547(=0.008)
0.33((+0.021)
0.651(=0.003)
0.564(=00001)
0.674(#0.004)
GraphSaint
0.525(=0.022)
0.352(10.007)
0.565(#0.002)
0.583(10.003)
0.746(10.005)
ClusterGCN
0.577(=00022)
0.391(10.015)
0.575(10.004)
0.390(10.005)
0.746(10.014)
BunditSampler
0.578(=0.016)
0.383(10.005)
0.652(1:00055)
0.555(10.009)
0.754(20.007)
Thanos
0.607(=0.012)
0.401(+0.013)
0.006)
0.574(+00010)
0.759
GAT
Vanilla GAT
0.558(=0.009)
0.339(00011)
0.519(+0.012) 0.682(#0.005)
X
BanditSampler
0.602(=0.005) 0.386(#0.006)
0.675(#0.002)
0.544(H0.0022
0.756(+0.001)
Thanos
0.600(=0.014) 0.412(10.003)
0..00(10.001)
0.559(10.011)
0.759(10.002)
6 Related Work
Hamilton et 17 initially proposed to uniformly sample subset for each root node. Many other methods extend this strategy, either by reducing variance [9], by redefining neighborhoods 34 36
[22], or by reweighting the policy with MAB [24] and reinforcement learning [26]. Layer-wise sampling further reduces the memory footprint by sampling fixed number of nodes for each layer.
Recent layer-wise sampling approaches include [8] and [37 that use importance sampling according to graph topology, well as [20] and 12] that also consider node features. Moreover, training GNNs with subgraph sampling involves taking random subgraphs from the original graph and apply them for each step. Chiang et al. [10] partitions the original graph into smaller subgraphs before training. Zeng et al. [35] and Hu et al. [9 samples subgraphs in an online fashion. However, most of them do not provide any convergence guarantee the sampling variance. We are therefore less likely to be confident of their behavior as GNN models are applied to larger and larger graphs.
Conclusion
In this paper, we build upon bandit formulation for GNN sampling and propose newly-designed reward function that introduce some degree bias to reduce variance and avoid numerical instability. Then, we study the dynamic of embeddings introduced by SGD so that bounding the variation of our rewards. Based on that, we prove our algorithm incurs a new-optimal regret. Besides, our algorithm named Thanos addresses another trade-off between remembering and forgetting caused by the non-stationary rewards by employing Rexp3 algorithm. The empirical results demonstrate the improvement of Thanos over BanditSampler in term of approximation error and test accuracy.
Acknowledgements
We would like thank Amazon Web Service for supporting the computational resources, Hanjun Dai for the extremely helpful discussion, and the anonymous reviewers for providing constructive feedback on our manuscript.
References
[1] P. Auer, N. Cesa-Bianchi Bianchi, Y. Freund, and R. F. Schapire The nonstochastic multiarmed bandit. problem. SIAM journal on computing, 32(1):48-77, 2002.
[2] P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzaler V. Zambaldi, M. Malinowski.
A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint /rXiv:/806.011 2018.
[3] R. v. d. Berg, T. N. Kipf, and M. Welling. Graph convolutional matrix completion. arXiv preprint arXiv: 02266,,,22,..... 2017.
[4] O. Besbes, Gur, and A. Zeevi. Stochastic multi-armedd bandit problem with non-stationn non-stationary rewards. In Advances in neural information processing systems, pages 199-207, 2014.
10

---

[5] A. Bojchevski and S. Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. arXiv preprint arXiv:1707.03811 2017.
[6] M. M. Bronstein, Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18 42, 2017.
[7] S. Bubeck and N. Cesa-Bianchi, Regret analysis of stochastic and nonstochastic multi-armed bandit problems. arXiv preprint arXiv:1204.572.. 2012.
[8] J. Chen, T. Ma, and C. Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. arXiv preprint 18X1vv880..1224: 2018.
[9] J. Chen, J. Zhu, and L. Song. Stochastic training of graph convolutional networks with variance reduction. In Proceedings of the 35th International Conference Machine Learning, pages 942-950, 950,550,22 2018.
[10] W.-L. Chiang, X. Liu, S. Si, Y. Li, S. Bengio, and C.-J. Hsich. Cluster-gen: 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, pages 257-266, 2019.
[11] E. Chien, J. Peng, P. Li, and O. Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations. https://openreview. net/forum, 2021.
[12] W. Cong, R. Forsati, M. Kandemir, and M. Mahdavi. Minimal variance sampling with provable guarantees for fast training graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 1393-1405, 2020.
[13] H. Dai, B. Dai, and L. Song. Discriminative embeddings of latent variable models for structured data. In International conference on machine learning, pages 2702-2711. PMLR, 2016.
[14] Y. Deshpande, S. Sen, A. Montanari, and Mossel. Contextual stochastic block mod- els. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gar- nett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL /tsttss:/prroeeett httpa///sssaapppssscc////////0/0 013300088822119136444333/0000000 Pspp pdf
[15] A. Fout, J. Byrd, Shariat, and A. Ben-Hur. Protein interface prediction using graph convo- lutional networks. In Advances in Neural Information Processing Systems, pages 6530-6539, 2017.
[16] R. Ge, S. M. Kakade, R. Kidambi, and P. Netrapalli. The step decay schedule: near optimal, geometrically decaying learning rate procedure for least squares. arXiv preprint ArXiv:1904. 12838, 2019.
[17] W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pages 1024-1034, 2017.
[18) W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00687 2020.
[19] Z. Hu, Y. Dong, K. Wang. and Y. Sun. Heterogeneous graph transformer. In Proceedings of The Web Conference 2020, pages 2704-2710, 2020.
[20] W. Huang, T. Zhang, Y. Rong, and J. Huang. Adaptive sampling towards fast graph repre- sentation learning. In Advances in neural information processing systems, pages 4558 4567, 2018.
[21] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
[22] A. Li, Z. Qin, R. Liu, Y. Yang, and D. Li. Spam review detection with graph convolutional networks. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pages 2703-2711 2019.

---

[23] Z. Liu, C. Chen, X. Yang, J. Zhou, X. Li, and L. Song. Heterogeneous graph neural networks for malicious account detection. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pages 2077-2085, 2018.
[24] Z. Liu, Z. Wu, Z. Zhang, J. Zhou, S. Yang. L. Song, and Y. Qi. Bandit samplers for training graph neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 12. 2020, virtual, 2020. URL https::/ htt.://aaccccsaaaaaa22227aaaaa.. Abstraatttbbtttttt.t..... html
cwwripsscc/ppper/22222
[25] Y. Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
[26] Oh, K. Cho, and J. Bruna. Advancing graphsage with data-driven node sampling. arXiv preprint 1rXiv:194. 2019.
[27] H. Pei, B. Wei, K. C.-C. Chang, Y. Lei, and B. Yang. Geom-gen: Geometric graph convolutional networks, arXiv preprint arXiv:2002.05288 2020.
[28] S. J. Reddi, A. Hefny, S. Sra, B. Poczos, and A. Smola. Stochastic variance reduction for nonconvex optimization. In International conference machine learning, pages 314-323. PMLR, 2016.
[29] F. Salehi, L. E. Celis, and P. Thiran. Stochastic optimization with bandit sampling. arXiv preprint arXiv: 1708. 02544,244444 2017.
[30] M. Schlichtkrull, N. Kipf. Bloem, R. Van Den Berg, Titov, and M. Welling. Modeling relational data with graph convolutional networks. In European semantic web conference, pages 593-607. Springer, 2018.
[31] T. Uchiya, A. Nakamura, and M. Kudo. Algorithms for adversarial bandit problems with multiple plays. In International Conference Algorithmic Learning Theory, pages 375-389. Springer, 2010.
[32] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention networks. arXiv preprint 17 10903, 2017.
[33] Z. Wu, S. Pan, Chen, G. Long, Zhang, and S. Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 2020.
[34] R. Ying, R. He, K. Chen, P. Eksombatchai, W. I. Hamilton, and J. Leskovec. Graph convolu- tional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 983- 2018.
[35] H. Zeng, H. Zhou, A. Srivastava, R. Kannan, and V. Prasanna. GraphSAINT: Graph sampling based inductive learning method. In International Conference Learning Representations, 2020. URL URL.ftttss://CCc htttep::///pperevieeee wwwpee/rwwiiie..eeffferreee tttt/fforum?ld-JBBppllttt
[36] C. Zhang, D. Song, C. Huang, A. Swami, and N. V. Chawla. Heterogeneous graph neural network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, page 793-803, 2019.
[37] D. Zou, Z. Hu, Y. Wang, S. Jiang, Y. Sun, and Q. Gu. Layer-dependent importance sampling for training deep and large graph convolutional networks. Advances in Neural Information Processing Systems, pages 11249-11259, 2019.
12


Reviews:
[{"review_id": "hez7MKKFxob", "reviewer": "Reviewer_rPqa", "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).", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\n\nI 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. \n\nFrom 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.\n\nMinor typo: 'Dyanmic policy' in Table 1.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No concerns.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "coKmQpFhWpZ", "reviewer": "Reviewer_sfqg", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "----------Strengths----------\n\n(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.\n\n(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.\n\n(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.\n\n(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.\n\n----------Weaknesses----------\n\n(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.\n\n(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.\n\n----------Overall----------\n\nOverall, 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.\n\n----------References----------\n\n[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.\n\n[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).\n\n[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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Q55FIV80QUP", "reviewer": "Reviewer_eLzM", "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.\n\nEmpirically, 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\n\nEmpirically, 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.\n\nIn 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.\n\nThe 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.\n\nIn 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.\n\nComments:\n- 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.\n- 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.\n- l.117 \"especially in the case that the neighbors\" -> \"especially when neighbors\"\n- l.120 \"to choose quite small temperature\" -> \"to choose a quite small temperature\"\n- l.138 \"independent with\" -> \"independent from\"\n- 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\".", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "N0NlOu7aV6S", "reviewer": "Reviewer_R9KQ", "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. \nThese 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.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper is clearly written to highlight the issues with the previous approach and the novel contributions of this work and validation via experiments.\n\nPros:\n\n(A) Fixes the issues with the BanditSampler algorithm especially with regard to dynamic regret and numerical instability issues.\n(B) Improvements on some of the datasets such as Chameleon and Squirrel datasets shows significant improvements in performance. \n\nCons/Questions:\n\n(1) The main contribution seems to be rethinking the reward function and the rest follows by incorporating this into the BanditSampler algorithm previously introduced. \n(2) How about replacing the EXP3 with an implicit version such as EXP3-IX for exploration? Will that fix the numerical issues? \n(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'?  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

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)