Layer-Neighbor Sampling --- Defusing Neighborhood Explosion in GNNs
Authors: Muhammed Fatih Balin
Umit Catalyurek
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph Neural Networks
Graph Sampling
GNN
Layer Sampling
Minibatch Training
TL;DR: Our approach combines the Layer and Neighbor Sampling approaches for efficient GNN training via sampling.

Abstract: Graph Neural Networks (GNNs) have received significant attention recently, but training them at a large scale remains a challenge.
Mini-batch training coupled with sampling is used to alleviate this challenge.
However, existing approaches either suffer from the neighborhood explosion phenomenon or have suboptimal performance. 
To address these issues, we propose a new sampling algorithm called LAyer-neighBOR sampling (LABOR). 
It is designed to be a direct replacement for Neighbor Sampling (NS) with the same fanout hyperparameter while sampling up to 7 times fewer vertices, without sacrificing quality.
By design, the variance of the estimator of each vertex matches NS from the point of view of a single vertex.
Moreover, under the same vertex sampling budget constraints, LABOR converges 
faster than existing layer sampling approaches and can use up to 112 times larger batch sizes compared to NS.

Layer-Neighbor Sampling - Defusing Neighborhood Explosion in GNNs
Muhammed Fatih Balm balin@gatech.edd edu
Ümit V. Çatalyürek umit@gatech. edu
Abstract
Graph Neural Networks (GNNs) have received significant attention recently, but training them at large scale remains challenge. Mini-batch training coupled with sampling is used to alleviate this challenge. However, existing approaches either suffer from the neighborhood explosion phenomenon or have suboptimal performance. To address these issues, we propose new sampling algorithm called LAyer-neighBOR sampling (LABOR). It is designed to direct replacement for Neighbor Sampling (NS) with the same fanout hyperparameter while sampling up to 7 times fewer vertices, without sacrificing quality. By design, the variance the estimator of each vertex matches NS from the point of view of single vertex. Morcover, under the same vertex sampling budget constraints, LABOR converges faster than existing layer sampling approaches and can up 1 112 times larger batch sizes compared to NS.
Introduction
Graph Neural Networks (GNN) (Hamilton et al., 2017 Kipf and Welling 2017 have become de facto models for representation learning on graph-structured data. Hence they have started being 2020]. These models iteratively
deployed in production systems (Ying et al. 2018 Niu update the node embeddings by passing messages along the direction of the edges in the given graph with nonlinearities between different layers. With layers, the computed node embeddings contain information from the I-hop neighborhood of the seed vertex.
In the production setting, the GNN models need to be trained on billion-scale graphs [Ching et al. 2015 Ying et al.] 2018). The training of these models takes hours to days even on distributed systems (Zheng 2202bb As in general Deep Neural Networks (DNN), it is more efficient to use mini-batch training [Brrtsekas) 1994) on GNNs, even though it is a bit trickier this case. The node embeddings in GNNs depend recursively on their set of neighbors' embeddings, so when there are layers, this dependency spans the (-hop neighborhood of the node. Real-world graphs usually have a very small diameter and if is large, the l-hop neighborhood may very well span the entire graph, also known as the Neighborhood Explosion Phenomenon (NEP) [Zegg et al. 2020).
To solve these issues, researchers proposed sampling subgraph of the I-hop neighborhood of the nodes in the batch. There are mainly three different approaches: Node- Layer-based and Subgraph-basee based methods. Node-based sampling methods [Hamilton et al., 2017 Chen al., 2018a Liu et al.] 2020 Zhang et af.) [021] sample independently and recursively for each node. was noticed that node-based methods sample subgraphs that too shallow, i.e., with a low ratio of number of edges to nodes. Thus layer-based sampling methods were proposed [Chen et al.) 2018b
Part of the GPU acceleration in this work was implemented during an internship at NVIDIA Corporation. i School of Computational Science and Engineering, Georgia Institute of Technology, Atlanta, GA, USA Ammaoon Web Services. This publication describes work performed at the Georgia Institute of Technology and is not associated with AWS.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Zou et al. 2019 Huang et al. 2018 Dong et al., [02T], where the sampling for the whole layer is
done collectively. On the other hand subgraph sampling methods [Chiang et al. 2019 Zeng et al.
2020 Hu et al. 2020b Zeng et al. 202 Fey et al. 2021 Shi et al. 2023 do not use the recursive layer by layer sampling scheme used in the node- and layer- sampling methods and instead tend to use the same subgraph for all of the layers. Some of these sampling methods take the magnitudes
of embeddings into account [Liu et al.
2020
Zhang et al. 2021, Huang et al. 2018), while others,
such as Chen et al. 2018 Cong et al.
Fey et al. [202]] Shi al. [2023] cache the historical embeddings to reduce the variance of the computed approximate embeddings. There are methods [222]] filled with popular vertices. Most of these approaches are orthogonal to each other and they can be incorporated into other sampling algorithms.
2021
of sampling from vertex cache Dong et al.
Node-based sampling methods suffer the most from the NEP but they guarantee good approximation for each embedding by ensuring each vertex gets l neighbors which is the only hyperparameter of the sampling algorithm. Layer-hased sampling methods do not suffer as much from the NEP because the number of vertices sampled is hyperparameter but they can not guarantee that each vertex approximation is good enough and also their hyperparameters are hard to reason with, the number of nodes to sample at each layer depends highly on the graph structure (as the numbers in Table 2 show). Moreover, Table 4 in Chen et al. [2023] shows that they can be extremely sensitive to the chosen hyperparameters and final task performance can differ by up to 15% between choosing a fixed number or doubling the number of sampled vertices at each layer. It is also unclear why one should settle with doubling; tripling, or quadrupling could potentially improve the performance of the final trained model even further. Subgraph sampling methods usually sample sparser subgraphs compared to their node- and layer-based counterparts. Hence, in this paper, we focus on the node- and baser- sampling methods and combine their advantages. The major contributions of this work can be listed as follows:
We propose the use of Poisson Sampling for GNNs, taking advantage of its lower variance and computational efficiency against sampling without replacement. Applying to the exist- ing layer sampling method LADIES, we get the superior PLADIES method outperforming the former by up to 2% in terms of Fl-score. Moreover, PLADIES is linear time, improving upon the recently proposed quadratic time debiasing technique in Chen et al. [2023).
We propose a new sampling algorithm called LABOR, combining the advantages of neighbor and layer sampling approaches using Poisson Sampling. LABOR correlates the sampling procedures of the given set of seed nodes so that the sampled vertices from different seeds have lot of overlap, resulting in 7 and 4x reduction in the number of vertices and edges sampled compared to NS, respectively. Furthermore, LABOR can sample up to 13x fewer edges compared to LADIES.
We experimentally verify our findings and show that our proposed sampling algorithm LABOR outperforms both neighbor and layer sampling approaches. LABOR can enjoy a batch size of up to 112x larger than NS while sampling the same number of vertices.
2
Background
Graph Neural Networks: Given a directed graph 9 = (V, E), where V and E C V x V are vertex and edge sets respectively, (I - 8) E E denotes an edge from a source vertex 1 E V to a destination vertex 8 E V. and Ass denotes the corresponding edge weight if provided. If we have a batch of seed vertices S V, let us define (-hop neighborhood (S) for the incoming edges as follows:
N(s) = [f](t + s) E.. NN(S Nss. = N(N
(1)
Let us also detine the degree de of vertex as d, [s)]. To simplify, let's assume uniform edge weights, Ars = 1, V(t + 8) E E. Then, our goal is to estimate the following for each vertex s E S, where 11!4-1) is defined as the embedding of the vertex at layer / - 1, and (I-1) is the trainable weight matrix at layer / - 1, and o is the nonlinear activation function [Hamilton et al. 2017|:
1 Σ H W = =
z
(2)
d 1-28
Exact Stochastic Gradient Descent: If we have a node prediction task and V, S V the set of training vertices, ye. s V2 are the labels of the prediction task, and E is the loss function for

---

the prediction task, then our goal is to minimize the following loss function: [V]] Replacing V in the loss function with S C Ve for each iteration of gradient descent, we get stochastic gradient descent for GNNs. However with layers, the computation dependency is on (5), which reaches large portion of the real world graphs, i.e. [S)( [V], making each iteration costly both in terms of computation and memory.
1 Σ E E(v.. Z.).
Neighbor Sampling: Neighbor sampling approach was proposed by Hamilton al.
2017 to
approximate - for each s E S with a subset of (S). Given fanout hyperparameter k, this subset is computed recursively by randomly picking k neighbors for each E 5 from (s) to form the next layer St that is a subset of N (S).. If d, S k, then the exact neighborhood (8) is used. For the next layer, S is treated the new set of seed vertices and this procedure applied recursively.
Revisiting LADIES, Dependent Layer- Sampling: From now on, we will drop the layer notation and focus single layer, and also ignore the nonlinearities. Let define M, H,W as a shorthand notation. Then our goal is to approximate:
H, = du Σ M
(3)
If we assign probabilities Te > 0, Vt E ((S) and normalize it so that EtEN(S) Th = 1, then sampling with replacement sample T (SS) with [T] n, where n is the number of vertices to sample given as input to the LADIES algorithm and T is a multi-set possibly with multiple copies of the same vertices, and let d, = (T n [s) which is the number of sampled vertices for a given vertex 8, we get the following two possible estimators for each vertex S:
H" ELETINNS) Te ΣIETHN(S) I
Me
M,
H ndg
(4a)
(4b)
Tt
(E)TI(()
Note that H in (4a) is the Thompson-Horvitz estimator and the H" in (4b) is the Hajek estimator. For comparison between the and how get even better estimator by combining them, see Khan and Ugander [2021]. The formulation in the LADIES paper uses H' but it proposes to row-normalize the sampled adjacency matrix, meaning they use H" in their implementation. However, analyzing the variance of the Thompson-Horviz estimator is simpler and its variance serves as an upper bound for the variance of the Hajek estimator when [Me and ne are uncorrelated (Khan and Ugander 2021 Dorfman 1997]. which we assume to be true in our case. Note that the variance analysis is simplified to be element-wise for all vectors involved.
1 d.
Var(Mr) T
Var(H") S Var(H)))
(5)
Since we do not have access to the computed embeddings and simplify the analysis, we assume that (Mr = 1 from now on. One can see that Var(H,) is minimized when म. = p. Vt - s under the constraint E Te pd,, for some constant p [0, 1], hence any deviation from uniformity increases the variance. The variance also smaller the larger de is. However, in theory and in practice, there is no guarantee that each vertex E S will get any neighbors in T, not to mention equal numbers of neighbors. Some vertices will have pretty good estimators with thousands of samples and very low variances, while others might not even get a single neighbor sampled. For this reason, we designed LABOR so that every vertex in S will sample enough neighbors in expectation.
While LADIES is optimal from an approximate matrix multiplication perspective [Chen et al. 2023), is far from optimal in the case of nonlinearities and multiple layers. Even if there is single layer, then the used loss functions are nonlinear. Moreover, the existence of nonlinearities in- in-between layers and the fact that there are multiple layers exacerbates this issue and necessitates that each vertex gets good enough estimator with low enough variance. Also, LADIES gives formulation using sampling with replacement instead of without replacement and that is sub-optimal from the variance perspective while its implementation uses sampling without replacement without taking care of the bias created thereby. In the next section, we will show how all of these problems are addressed by newly proposed Poisson sampling framework and LABOR sampling.
3

---

3 Proposed Layer Sampling Methods
Node-based sampling methods suffer from sampling too shallow subgraphs leading to NEP just a few hops (e.g., see 2 Layer sampling methods Zou et al. [2019] attempt to fix this by sampling a fixed number of vertices in each layer, however they can not ensure that the estimators for the vertices are of high quality, and it is hard to reason how to choose the number of vertices to sample in each layer. LADIES Zou et al. (2019) proposes using the same number for each layer while papers evaluating it found it is better to sample an increasing number of vertices in each layer Liu et al. [2020), Chen et al. 2023]. There is no systematic way to choose how many vertices to sample each layer for the LADIES method, and since cach graph has different density and connectivity structure, this choice highly depends on the graph in question. Therefore, due to its simplicity and high quality results, Neighbor Sampling currently seems to be the most popular sampling approach and there exists high quality implementations on both CPUs and GPUs in the popular GNN frameworks Wang et al. 2019) Fey and Lenssen [2019].
20e0),Chen
We propose new approach that combines the advantages of layer and neighbor sampling approaches using a vertex-centric variance-based framework, reducing the number of sampled vertices drastically while ensuring the training quality does not suffer and matches the quality of neighbor sampling. Another advantage of our method is that the user only needs to choose the batch size and the fanout hyperparameters as in the Neighbor Sampling approach, the algorithm itself then samples the minimum number of vertices in the later layers in an unbiased way while ensuring each vertex gets enough neighbors and a good approximation.
We achieve all the previously mentioned good properties with the help of Poisson Sampling, So, the next section will demonstrate applying Poisson Sampling to Layer Sampling. and then we will show how the advantages of Layer and Neighbor Sampling methods can be combined into LABOR while getting rid of their cons altogether.
3.1 Poisson Layer Sampling (PLADIES)
In layer sampling, the main idea can be summarized as individual vertices making correlated decisions while sampling their neighbors, because in the end if vertex is sampled, all edges into the seed vertices S, i.e., t + s, E S, are added to the sampled subgraph. This can be interpreted as vertices in S making a collective decision on whether to sample 4, or not.
The other thing to keep in mind is that the existing layer sampling methods use sampling with replacement when doing importance sampling with unequal probabilities, because it is nontrivial to compute the inclusion probabilities in the without replacement case. The Hajek estimator in the without replacement case with equal probabilities becomes:
Mr He I H" E EIETANNS We
EIETAN(S)
EIETANGS MSN(S)) EIETAN(S) [N(S
1
Σ M,
(6)
dg tETTN(s)
and it has the variance:
Var(H,) = d. d, 1
(7)
d. 1 d.
Let us show how one can do layer sampling using Poisson sampling (PLADIES). Given n E Z+ and unnormalized probabilities n. [0, oo), Vt E N(S), we can ensure that EiEN(S) Hi by finding a solution of E min(1, cT,) = n for c E R + in linear time and redefining कe < min cx,) so that n. E [o, 1]. Then we include t E N(S) in our sample T with probability n, by flipping coin for it, i.e., we sample rt (0, 1) and include E if r S Te. In the end, E|[T]] n and we can still use the Hajek estimator H" or the Horvitz Thomson estimator H', to estimate H Doing layer sampling this way is unbiased by construction and achieves the same goal linear time in contrast to the quadratic time debiasing approach explained in Chen et al. [2023). further discussion can be found in Appendix [..7 The variance then approximately becomes Williams et al. 1998. see Appendix A for derivation:
1 Σ
Var Var(H.) I Var(H()=
=
dc
d.
(8)
1-28

---

One can notice that the minus term d, enables the variance to converge to 0, if all = 1 and we get the exact result. However, in the sampling with replacement case, the variance goes to 0 only as the sample size goes to infinity.
3.2 LABOR: Layer Neighbor Sampling
The design philosophy of LABOR Sampling is to create direct alternative to Neighbor Sampling while incorporating the advantages of layer sampling. Mimicking Layer Sampling with Poisson Sampling in Section 3.1 still has the disadvantage that d, varies wildly for different 8. To overcome this and mimic Neighbor Sampling where Elda] = min(d,, k). where is given fanout hyperpa- rameter, proceed as follows: for given 0, Vt (S)) denoting unnormalized probabilities, for a given 8, let us define C, as the quantity satisfying the following equality if l < dg, otherwise Cs max+++ m2
(
dg k d.
Note that 1 J. is the variance when nΙ o, vt N(s) that Ejd.] = k. Also note that:
dg dg
d. k: d, k dg = 0
(10)
dg
de 1 k k(d, 1) dg 1 k:
meaning that the variance target we set through (9) is equal to Neighbor Sampling's variance in 7 after calibrating with d.-1
d_ Ohlsson 1998) and it will result in E[d,] 2 with strict equality in the uniform probability case. Then each vertex E S samples t + 8 with probability ca To keep the collective decision making, sample r, (0, 1), Vt E (S) and vertex samples vertex t if and only if r4 I Ce Note that we use uniform random variable for each edge rts instead of each vertex r4. and if is uniformly initialized, then get the same behavior Neighbor Sampling.
3.2.1 Importance Sampling
Given the sampling procedure above, one wonders how different choices of 2 0 will affect (T), the total number of unique vertices sampled. We can compute expected value as follows:
E[[T]]
Σ (EN(S)
Pt E T)
(11)
Σ (EN(S)
min(1, max t+3
In particular, we need to minimize E[[T]]:
n arg min #20
min(1, me max cx)
(12)
(EN(S)
Note that for any given æ 2 0. []] is the same for any vector multiple av, R+, meaning the objective function homogeneous degree O.
3.2.2 Computing and n²
c. was defined to be the scalar satisfying the following equality involving the variance of the estimator
of Hg:
1
1
1
(13)
min(1, (.
d,
k
d.
6-78
If we rearrange the terms, we get:
d?
Σ {-2
(14)
min 1, c.T.
k
5

---

One can see that the left-hand side of the equality is monotonically decreasing with respect to c₂ 2 0. Thus one can use binary search to find the e satisfying the above equality any precision needed. But we opt to use the following iterative algorithm to compute it:
Algorithm LABOR-i for uniform edge weights
k
1: Input: seed vertices S, # iters i, fanout k
(0)
0,
Cg
(0)
(15)
2: Output: sampled edges E' and weights A'
d
7
3: T < t ((S))
1
4: Cs d. e
(1+1)
(8) +
d3
(
min
(1.c.
5: _. + 1,,
6: while 0 do
(16)
7: for all E S do
(++1) Σ
(
2
1]
(17)
8: Solve (14) for c2
9: for all t E T do
10:
We 4 Ty max Cs
This iterative algorithm converges in at most dg steps and the convergence is exact and mono- tonic from below. One can also implement in linear time (d,) if {TT It s) is sorted and making use of precomputed prefix sum arrays. Note that c(T), meaning that is a function of the given probability vector т. To compute x¹, we use a similar fixed point iteration as follows:
11:
i
12: Y1 ~ U10,
13: E' +[]
14: A' [
15: for all E do
16: w #
17: forall e (()) do
18:
if S C then
19:
E'aappend w <- + m.n
S)
(0) = 1, vt E N(S): : T
(++1)_ (0) max Co (T (
20:
ai
8-88
21:
for all E (s) do
(18)
22: rf S C then
23:
A'apppend( min(L,c.
Thus, we alternate between computing c(Tr), meaning is computed with the current I,, and updating æ with the computed e values, see the lines 5-10 in Algorithm [ Each step of this it- eration is guaranteed to lower the objective function value in (12) until convergence to a fixed point, see Appendix A.3 Modified formulation for a given weight matrix A, is discussed Ap- pendix A.5 Finally, Algorithm I summarizes LABOR including the actual sampling (lines 17-19) and computation of the edge weights (lines 20-22) due to the use of importance sampling.
3.3 Choosing how many neighbors to sample
The variance of Poisson Sampling when म. = is 1. One might question why we are trying to match the variance of Neighbor Sampling and choose to use fixed fanout for all the seed vertices. In the uniform probability case, if we have already sampled some set of edges for the vertices in S, and want sample one more edge, then we should sample the new edge for the vertex s, whose variance would decrease the most. If vertex currently has d, sampled edges, then sampling one more edge for it would improve its variance from d. _ to 1td, J. Since the derivative of the variance
d,
k d.
with respect to d, is monotonic, derivatives, which is:
reason about the marginal improvements by comparing their
9 ( ad, d Notice that the derivative does not depend on the degree d, of the vertex at all, and the greater the magnitude of the derivative, the more the variance of a vertex improves by sampling one more edge. Thus, choosing any vertex s with least number of edges sampled would work for us, that is arg min dy. In light of this observation, one can see that it is optimal to sample an equal number of edges for each vertex in S. This one of the reasons LADIES is not efficient with respect to the number of edges it samples. On graphs with skewed degree distributions, it samples thousands of edges for some seed vertices, which contribute very small amounts the variance of the estimator since it is already very close to 0.
d -
1
(19)
de

---

3.4 Sampling fixed number of neighbors
To make LABOR-0 even more similar to Neighbor Sampling, one can easily resort to Sequential Poisson Sampling by Ohlsson [1998] if one wants d. min(k: dz) instead of F[d.]] = min (k. d.). Given Te, C2 and rt, we pick the de = min (A: d,) smallest vertices - with respect to _ which can be computed in expected linear time by using the quickselect algorithm (Hoare 1961
Table 1: Properties of the datasets used in experiments: numbers of vertices ((V), edges (EE)), avg. number of features, sampling budget used, training, validation and test vertex split.
degree v
Dataset
[V]
E
# feats.
|
budget
train val test (%)
[V]
reddit
233K
115M
493.56
602
60k
66 10 24
products
2.45M
61.9M
25.26
100
400k
8 8-2 2
yelp
717K
14.0M
19.52
300
200k
75- 10 15
flickr
89.2K
900K
10.09
500
70k
50- 25 25
4 Experiments
In this section, empirically evaluate the performance of each method in the node-prediction setting
on the following datasets: reddit [Hamilton et al.) 2017]. products [Hu et al. [020a]] yelp. flickr (Zeng
al., 2020). Details about these datasets are given in Table []] We compare our proposed LABOR
variants LABOR-0, LABOR-I and LABOR-*, where 0, 1, * stand for the number of fixed point
iterations applied to optimize (12) respectively, together with PLADIES (see Section 3.1 against
the baseline sampling methods: Neighbor Sampling (NS) and LADIES. We do not include Fast- GCN
in our comparisons as it is super-sceded by the LADIES paper. The works of Liu et al. (2020).
Zhang et al. [2021]. Huang et al. [2018). Cong et al. [202T], Dong et al. [2021] are not included
in the comparisons because they either take into account additional information such as historical
embeddings or their magnitudes they have an additional sampling structure such as a vertex cache
to sample from. Also the techniques in these papers are mostly orthogonal to the sampling problem and algorithms discussed in this paper, hence our proposed LABOR and PLADIES methods can be used together with them. However, we leave this investigation to future work.
We evaluate all the methods on the GCN model in (2) with 3 layers, with 256 hidden dimension and residual skip connections enabled. We use the Adam optimizer (Kingma and Ba 2014 with 0.001 learning rate. We implemented LABOR variants and PLADIES in DGL Wang et al. 2019 and carried out our experiments using DGL with the Pytorch backend [Paszke al. 22019) URLs are
provided in Appendix A.8 Experiments were repeated 100 times and averages are presented.
4.1 Baseline Comparison of Vertex/Edge Efficiency
LABOR comparison against NS: In this experiment, we set the batch size to 1,000 and the fanout k 10 for LABOR and NS methods to see the difference in the sizes of the sampled subgraphs and also how vertex/edge efficient they are. In Figure we can see that LABOR variants outperform NS in both vertex and edge efficiency metrics. Table 2 shows the difference of the sampled subgraph sizes each layer. One can see that on reddit, LABOR-* samples 6.9x fewer vertices in the 3rd layer leading much faster convergence in terms of cumulative number of sampled vertices. On the flickr dataset however, LABOR-* * samples only 1.3x fewer vertices. The amount difference depends on two factors. The first is the amount of overlap of neighbors among the vertices in S. If the neighbors of vertices in S did not overlap at all, then one obviously can not do better than NS. The second is the average degree of the graph. With fanout of 10, both NS and LABOR has copy the whole neighborhood of a vertex s with degree d, < 10. Thus for such graphs, it is expected that the difference will be insigmificant. The average degree of the flickr is 10.09 (Table []. and thus there is only a small difference between LABOR and NS.
parallel C++ implementation of this idea can found in dgl Fraapabolt.Layereeeihbbooo 'Our CUDA and C++ implementations are available in DGL starting with version 1.0 as dgl. dataloading LaborSampler and samplimnnnng wwattng..mmpl...mm cample_labors..
7

---

656
3.43
0.10
6.04
0.53
6.0
3.07
3.85
175
125
www. # sanoted vertoes
1:00
cumulatte rampled vertor
163
car.aba # unplevesionn
10b
CLT 1 ad HOTTRE
365
3.6
3.4
32-
6.4
1.0-
1.3
0.41
1.5
6.18
025
135
125
1.75
0.3
14
05
03
Cur.0ttv surteeed verdoo
1.00
OLPUBSTV WIRTERS vetto
sumple veriorr
6.66
3.32
6.60
3.88
0.5
0.95
6/00
0.92
3355
05
36
15
2.0
25
35
2
3.8
025
0.50
0.75
3.00
325
150
1.4
1.0
0.6
6:50
1.5
1.3
011
189
163
146
362
Figure 1: The validation Fl-score and training loss curves different datasets with same batch size. The x-axis stands for cumulative number of vertices and edges used during training, respectively. The soft edges represent the confidence interval. Number of sampled vertices and edges can be found in 2
As seen in Figure and Table LABOR-O reduces both the number of vertices and edges sampled. On the other hand, when importance sampling is enabled, the number of vertices sampled goes down while number of edges sampled goes up. This is because when importance sampling is used, inclusion probabilities become nonuniform and it takes more edges per seed vertex to get good approximation (see Equation 9 Thus, LABOR-0 leads the pack when it comes to edge efficiency.
The hyperparameters of LADIES and PLADIES were picked to match LABOR-* * so that all methods have the same vertex sampling budget in each layer (see T2 Figure [ shows that, LADIES and PLADIES perform almost identically in terms of convergence, on all but the flickr dataset where there is a big difference between the two in favor of PLADIES. We also see that LABOR variants outperform LADIES variants on products, yelp, and flickr in terms of vertex efficiency with the exception of reddit, where the best- pessoreerromnn algorithm is PLADIES proposed by us. Regarding edge efficiency, however, we see that LADIES variants are inefficient and all LABOR variants outperform LADIES variants across all the datasets by up to 13x.
Layer sampling algorithm comparison:
Comparing LABOR variants: Looking Table 2 we can see that LABOR-0 has the best runtime performance across all datasets. This is due to 1) sampling fewer edges, 2) not having the fixed point iteration overhead, compared to the other LABOR variants. By design, all LABOR variants should
8

---

Table 2: Average number of vertices and edges sampled in different layers (All the numbers are in thousands, lower better). Last two columns show iterations (mini-batches) per second (it/s) and test Fl-score, for both, higher is better. The hyperparameters of LADIES and PLADIES were picked to roughly match the number of vertices sampled by the LABOR- to get a fair comparison. The convergence curves be found in Figure The timing information was measured
NVIDIA
T4 GPU. Green stands for best, red stands for worst results, with a 5% cutoff.
Dataset
Algo.
[V
|
[V2|
|E'I
[V
|ED
|V
it/s
test F1-score
PLADIES
24
2390
14.1
927
6.0
33.2
1.7
96.21 1 0.06
LADIES
25
2270
14.5
852
6.0
32.5
1.8
96.20 + 0.05
reddit
LABOR-*
24
1070
13.7
435
6.0
26.9
4.1
96.23 = 0.05
LABOR-1
27
261
14.4
116
6.1
16.7
24,8
96.23 = 0.06
LABOR-0
36
177
17.8
67
6.8
9.6
37.6
96.25 + 0.05
NS
167
682
68.3
100
10.1
9.7
14.2
96.24 + 0.05
PLADIES
160
2380
51.2
293
9.7
11.7
4.1
78.44 + 0.24
LADIES
2230
51.8
9.7
11.5
78.59 + 0.22
products
LABOR-*
1250
51.8
9.8
10.6
78.59 +
LABOR-1
178
799
53.4
136
9.8
10.5
21.3
78.47 + 0.26
LABOR-0
237
615
62.4
100
10.1
9.9
32,5
78.76 + 0.26 0.26
NS
513
944
95.4
106
10.6
24.6
78.48 + 0.29
PLADIES
100
1300
29.5
183
6.2
6.9
5.1
61.55 1 0.87
LADIES
102
1280
29.7
182
6.2
5.3
61.89 + 0.66
yelp
LABOR-*
105
991
30.7
158
13.3
61.57 = 0.67
LABOR-1
109
447
31.0
96
6.2
6.8
27.3
61.71 + 0.70
LABOR-0
138
318
35.1
54
6.2
6.3
27.2
61.55 1 0.85
NS
188
392
42.5
55
6.3
6.3
23.0
61.50 + 0.66
PLADIES
55
309
24.9
85
6.2
6.9
10.2
51.52 + 0.26
LADIES
308
25.1
85
10.5
50.79 + 0.29
flickr
LABOR-*
25.6
85
20.3
51.67 +
LABOR-1
58
242
25.9
73
6.3
6.9
32.7
51.66 + 0.24
LABOR-O
66
219
29.1
52
6.4
6.7
33.3
51.65 + 0.26
NS
73
244
32.8
52
6.4
6.7
31.7
51.70 + 0.23
have the same convergence curves, as seen Appendix A.2 Figure Then, the decision of which variant to use depends on one factor: feature access speed. If vertex features were stored on a slow storage medium (such as, on host memory accessed over PCI-E), then minimizing number of sampled vertices would become the highest priority, in which case, one should pick LABOR- Depending on relative vertex feature access performance the performance the training processor, one can choose to use LABOR-j. the faster feature access, the lower the
4.2 LABOR vs NS under vertex sampling budgets
In this experiment, set a limit the number of sampled vertices and modify the batch size to match the given vertex budget. The budgets used were picked around the same magnitude with numbers in the Table 2 in the V/s column and can be found in Table Figure 2 displays the result of this experiment. Table 3 shows that the more vertex efficient the sampling method is, the larger batch size it can use during training. Number of sampled vertices for the LADIES algorithm so we do not include it in this comparison. All of the experiments were repeated 100 times and their averages were plotted, that is why our convergence plots are smooth and differences are clear. The most striking result in this experiment is that there can be up to 112x difference in batch sizes LABOR- and NS algorithms on the reddit dataset, which translates into faster convergence as the training loss and validation Fi-score curves in Figure show.
function of the batch size
4.3 Importance Sampling, Fixed Point Iterations
In this section, we look at the convergence behavior of the fixed point iterations described in Sec- tion 3.2.2 4ableessshoss the number of sampled vertices in the last layer with respect to the number of fixed point iterations applied. In this table, the * stands for applying the fixed point iterations until

---

3.17
6.00
0.00
0.50
3.11
3.65
0.4
0.40
0.47
6.000
3.5
0.00
1802
0.10
0.18
0.17
L3
02
0.6
3.8
1802 60p
1000
5062
1000
A0p 5000
1003
$200
Figure 2: Validation Fl-score and the training loss curves to evaluate vertex sampling efficiency under the sampling budget. The x-axis stands for the number of training iterations. The batch size is chosen so that the # sampled vertices matches the vertex budget for each dataset and method and it given Table
The batch sizes used in Figure 2 These were chosen such that in expectation, each method samples with the same budget given in Table Having larger batch-size speeds up convergence.
Table 3:
Table Number vertices (in thousands) in 3rd layer w.r.t # fixed point iterations (its). denotes applying the fixed point iterations until conver- gence, ie.. LABOR-* * its stands for LABOR-1 etc.
Dataset
LAB-
LAB-1
LAB-0
NS
Dataset
NS
0
3
reddit 10100
8250
3850
90
reddit
167
36
27
25
25
products
7750
6000
2750
700
products
513
237
178
170
169
166
yelp 3700
3300
1950
1120
yelp
188
138
109
106
105
105
flickr
3600
3100
1400
800
flickr
66
58
57
57
56
convergence, and convergence occurs in most 15 iterations in practice before the relative change in the objective function is less than 10-4, One see that most of the reduction in the objective function (12) occurs after the first iteration, and the remaining iterations have diminishing returns. Full convergence can save from 14% 33% depending on the dataset. The monotonically decreasing numbers provide empirical evidence for the presented proof Appendix A.3
Conclusions
In this paper, we introduced LABOR sampling, a novel way combine layer and neighbor sampling approaches using a vertex-varianee centric framework. We then transform the sampling problem into an optimization problem where the constraint is to match neighbor sampling variance while sampling the fewest number of vertices. We show how minimize this new objective function via fixed-point iterations. datasets with dense graphs like Reddit, we show that our approach can sample subgraph with 7x fewer vertices without degrading the batch quality. We also show that compared to LADIES, LABOR converges faster with same sampling budget.
each vertex
Acknowledgements
would like to thank Dominique LaSalle and Kaan Sancak for their feedback on the manuscript, and also Murat Güney for their helpful discussions and for enabling the GPU acceleration of this project during the author's time NVIDIA Corporation. This work was partially supported by the NSF grant CCF- 1C1-1911021.
10

---

References
D.P. Bertsekas. Incremental least squares methods and the extended kalman filter. In Proceedings of 1994 33rd IEEE Conference on Decision and Control, volume 2, pages 1211-1214 vol.2, 1994. doi: 11099/DD..199..111
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In In- lernational Conference on Learning Representations, 2022. URL httpss://ppenevviieee net/
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. 35th International Conference on Machine Learning. ICML 2018, 3:1503-1532, 201 8a.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling. jan 2018b. URL URL httpaaiwww....r//eaaaaaaaaa 10277
Yifan Chen, Tianning Xu, Dilek Hakkani Tur, Di Jin, Yun Yang. and Ruoqing Zhu. Calibrate and debias layer- sampling for graph convolutional networks. Transactions on Machine Learning Research, 2023. URL https::/
net/ htt///ormmmiii JyKKuuuouG
Wei Lin Chiang, Yang Li, Xuanqing Liu, Samy Bengio, Si Si, and Cho Jui Hsieh. Cluster-GCNt An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 257-266. Association for Computing Machinery, jul 2019. doi: 00.1145/2222500333309
Avery Ching, Sergey Edunov, Maja Kabiljo, Dionysios Logothetis, and Sambavi Muthukrishnan. One trillion edges: Graph processing at facebook-scale. Proc. VLDB Endow., 8(12): aug 2015. doi: 10.1477882222433222244777 URL htttp::/ddoi.ogg// 11ti//000..77//22200333 2824077
Weilin Cong, Morteza Ramezani, and Mchrdad Mahdavi. On the Importance of Sampling in Training GCNs: Tighter Analysis and Variance Reduction. 2021. URL URLhhtpp:// http://arxiv org www./oggg/////a/eeee.oooee ab03 02696
Alexander Cooen- Rivers, Wenlong Lyu, Rasul Tutunov, Zhi Wang, Antoine Grosnit, Ryan Rhys Griffiths, Hao Jianye, Jun Wang, and Haitham Bou Ammar. An empirical study of assumptions in bayesian optimisation. arXiv preprint arXiv:20/2.03826. 2020.
Jialin Dong, Da Zheng, Lin F. Yang, and George Karypis. Global Neighbor Sampling for Mixed CPU-GPU Training Giant Graphs. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 289-299, 2021. doi: 10.11457347544.44444377
Alan Dorfman. The Hajek Estimator Revisited, (4):760-765, 1997. URL http:ttt//ww.aaassmm htgp//rrceddnggg/ppprr////////// 130 pdf.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometrie, 2019.
URL ttttp:///ariiv wtg. httgg//b//190.. 0941//29880002888
Matthias Fey, Jan E. Lenssen, Frank Weichert, and Jure Leskovec. Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 3294-3304 PMLR, 18-28 28-24 Jul 2021. URL https:://proceeddnng mlr
html
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Guyon, U. Von Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems. volume 30. Cur- ran Associates, Inc., 2017. URL htttps://proceedinges http://iwwn..rre.eeeeeeeeeeeeeee pctpppapppp/21//fieel 366647. aa
.pdf
C. Hoare. Algorithm 65: Find. Commun. ACM, ((7):321-322,222)) jul 1961. doi: 10. 1461/4///662... org/10. 1115/1166652266666885

---

Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in Neural Information Processing Systems, 2020- 2020-Decem(Neur//S)) 1-34, 2020a.
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogeneous Graph Transformer. The Web Conference 2020 Proceedings of the World Wide Web Conference, WWW 2020, pages 2704-2710 10, 2020b.
doi: 10. 1..114///6642233380002
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. Advances in Neural Information Processing Systems, 2018- (--)ecem((Nip)) 4558 4567, 2018.
Samir Khan and Johan Ugander. Adaptive normalization for IPW estimation. pages 1-31, 2021. URL http://arxiv. wtt.ooo////////eeeoeooooee ats///bbs///00/ 07695
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2014. URL
bitts://arxiyy oraiiiiorrgaaae www./b//////oooooooo//..oo..ae// att/aa//////////////////////aa/a 1412.69999
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. 5th International Conference Leurning Representations, ICLR 2017 Conference Track Proceedings, pages 1-14, 2017.
Ziqi Liu, Zhengwei Wu, Zhiqiang Zhang, Jun Zhou, Shuang Yang, Le Song, and Yuan Qi. Bandit samplers for training graph neural networks. Advances in Neural Information Processing Systems, 2020-Decem, 2020.
Xichuan Niu, Bofang Li, Chenliang Li, Rong Xiao, Haochuan Sun, Hongbo Deng, and Zhenzhong Chen. A dual heterogeneous graph attention network to improve long-tail performance for shop search in e-commerce. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '20, page 3405-3415, 2020. doi: 10.1145/3394486. 3403393.
Ohlsson. Sequential poisson sampling. Journal of Official Statisties-Stockholm- 14(2):149-162, 1998.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang. Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performang deep learning library. In NeurIPS, 2019.
Zhihao Shi, Xize Liang, and Jie Wang. LMC: Fast training of GNNs via subgraph sampling with provable convergence. In The Eleventh International Conference Learning Representations, 2023. URL httpp:://peerreiiii www.weeeeeeeeeeeeeeeeeeeeeeeeeee
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma. Lingfan Yu, Yu Gai, Tianjun Xiao, Tong Hc, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centric, highly-performant package for graph neural networks, 2019. URL https: /ttp///axvvvv... org/ abs/ /aob//999....... 1909. 01315
Michael Williams, Hans T Schreuder, and Gerardo H Terrazas. Poisson Sampling The Adjusted and Unadjusted Estimator Revisited, page 12, 1998.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 974-983, 2018. doi: 10.1145/32198199.2299999
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- SAINT: Graph sampling based inductive learning method. International Conference on Learning Representations, 2020. httpp:///pennneeeee..eeee.
12

---

Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kannan, Viktor Prasanna, Long Jin, and Ren Chen. Decoupling the depth and scope of graph neural networks. In A. Beygelzimer, Y. Dauphin, P. Liang, and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. /tt.attpse///ppnneeeee...ee////e http://rrreiieeeeeeourmmmmmmmm net/forum?id dOMCHWYONZ!
Qingru Zhang, David Wipf, Quan Gan, and Le Song. A Biased Graph Neural Network Sampler with Near-Optimal Regret. (NeurIPS): 1-2, 2021. (Rttttt://aaxii wttpexiii..rgoo/oooooo a 01089
Che Zheng, Hongzhi Chen, Yuxuan Cheng, Zhezheng Song, Yifan Wu, Changji. Li, James Cheng, Han Yang, and Shuai Zhang. Bytegnn: Efficient graph neural network training at large scale. Proc. VLDB Endow. 15:1228-1244 2022a.
Da Zheng, Xiang Song, Chengru Yang, Dominique LaSalle, and George Karypis. Distributed hybrid epu and gpu training for graph neural networks on billion-scale heterogeneous graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4582-4591 2022b.
Difan Zou, Ziniu Hu, Yewen Wang. Song Jiang, Yizhou Sun, and Quanquan Gu. Layer-dependent importance sampling for training deep and large graph convolutional networks, Advances in Neural Information Processing Systems, 32(NeurIPS), 2019.
13

---

A Appendix
A.1 Derivation of Poisson Sampling variance
estimator. Note that we assume Var(M) 1, vt. Also, Var(1(ra Tel is the variance of the bernoulli trial with probability and equal to Te (1 Te).
Following a derivation of Equation (8) for the
Mt
H¹ = dg
Σ
1r. S Tpl
t-t
1
Mr 1 1[re S Tel
Var(H))) Var
da
Tt
Var(M))
Var(1 (rr me))
Var(Mr
Te Te))
(20)
Var(M))
(1 Te))
T
(1 - -
d t-
1
1)
d t-
T
d,
A.2 Baseline Comparison of Vertex/Edge Efficiency (cont.)
products
yol
6.06
3.11
6.05
6/8-
3.5
6.2
3.6
3.4
32-
334
1.2
3.0
538
1.4
1000
2006
3003
4220
2006
1002
2000
3000
4003
5200
1200
2003
3000
1006
5093
3000
2000
2003
1200
5006
Figure 3: The validation Fl-score and training loss curves on different datasets with same batch size. The soft edges represent the confidence interval. The x-axis stands for the number of training iterations. Number of sampled vertices and edges can be found in Table
Here, we show another version of Figure T Figure 3 We would like to point out that despite NS and LABOR variants sampling drastically
replacing the x-axis with the number of training iterations,
14

---

Table 5: The runtimes (ms) per iteration for the GATv2 model on NVIDIA A100 80GB corresponding The abbreviation OOM stands for an 'out-of-memory error, which occurs when an excessive number of edges are sampled.
Table 2
Dataset
LADIES
PLADIES
LABOR-
LABOR-1
LABOR-0
NS
reddit
OOM
0OM
266.6
69.8
51.9
155.1
products
0OM
0OM
224.8
154.6
138.7
218.5
yelp
278.0
278.9
169.2
96.6
83.2
99.5
flickr
96.6
100.3
79.8
65.0
61.1
66.2
different number of vertices/edges as shown in (up to 7x fewer vertices), their convergence behavior more or less the same, even indistinguishable on Yelp and Flickr.
A.3 Monotonic convergence proof of the fixed point iterations
Given any 7t 0 and one iteration to get (11) and one more iteration using e(T(1)) to get x(2)
then we have the following observation:
(0) max C. (T
=T
t+
1
min(1, cx (=( (1))
dg
d.
Σ d 1- c,
1
1
dg t-s min(1, c, (T(())) maxe=s Co (TT (1)))
Now, note that for given & E N(s), max,-1 (T(())) 2 (I since E { 1 + s'}.
)m This implies that maxt-ss Cer (I(1)) yT, (0) 2 (m) Note that for गí (T(T))))) (0)) (U) VI + 8,
have (TT' 1 for any given Since max eo (= )=(() > c=(z(()) ym (0) T/p VI 8,
(0)
this let's conclude that the ()(2(1)) < 1, because the expression is monotonically increasing
with respect to any of the By induction, this means that d < 1, > 1. Since T. = max:-1s (x(-1))) ne is monotonically decreasing. This means that the objective value in [2] is also monotonically decreasing and is clearly bounded from below by 0. Any monotonically decreasing sequence bounded from below has to converge, so our fixed point iteration procedure is convergent well.
(0)
The intuition behind the proof above that after updating æ via 18). the probability of each edge t ++ 8: TeCx goes up because the update takes the maximum c, over all possible s. This means each vertex gets higher quality estimators than the set variance target so we now have room reduce the number of vertices sampled by choosing the appropriate c, < 1. To summarize, update step increases the quality the batch which turn let's the e, step to reduce the total number vertices sampled.
A.4 GATv2 runtime performance
We utilize the GATv2 model Brody et al. 2022 and show the runtime performance of different
samplers in Table 5 All the hyperparameters were kept same as Section 4.1 and the number of attention heads was set to 8. The runtimes correlate with the [Ea] column in Table 2 the GATv2 model as the computation and memory requirements depend on the number of edges. That why the LADIES variants went out-of out-of-memory the reddit and products datasets.
A.5 Extension to the weighted case
If the given adjacency matrix A has nonuniform weights, then we want the estimate the following:
15

---

H,
1
E
A
(21)
A.s
where = Ats. If we have probability over each edge tts: v(t 8) E, then the variance becomes:
A
Var(H Var(nH)) (A.a)² min c,
Als)
(22)
In this case, we can still aim to reach the same variance target v, tob T, or any given custom target Us R+ by finding C that satisfies the following equality:
AP.
Σ Als)) = t-78
(23)
(Aoa)²
min(1, CTTTEA)
In this case, the objective function becomes:
arg min
Σ (EN(S)
min(1, max c.T..)
(24)
x20
Optimizing the objective funetion above will result into minimizing the number of vertices sampled. Given any Tts > 0. V(t + s), then the fixed point iterations proposed for the non noi-weeghted case in (18 can be modified follows:
(++1) max Cyt (TT( (0) (0)) V( - s): 1i8
(25)
2-08
A more principled way to choose in the weighted case is by following the argument presented in Section 3.3 There, the discussion revolves around the derivative of the variance with respect to the expected number of vertices sampled for a given seed vertex If we apply the same argument, then we get:
A2
vo(co) (Aus)3
Σ
Alr)
min (I,
1-+8
Or. -1
L|coTTe 1|A2
oc, (A
CuTTE
Eldd)(co) =
Σ
min(1, (oTTE)
dEdd]
1CTTTte
1|T
C2
Then to compute the derivative the variance with respect to the expected number of sampled vertices for given seed vertex 5, which is 8e, we can use the chain rule and get:
aEld]]
[A..)² E <1 dE[d.] dc, 0Eld,] Ex 1[coTtss 1|TTs
Or, ou dc.
(26)
Then, what one would do is to choose constant ((k) as a function of the fanout parameter & and set Su, C(k) and solve for c.. C(k) would be negative quantity whose absolute value decreases
BE[d
as l increases. It would probably look like C(k) for some constant C" We leave this as future work.
16

---

A.6 Convergence speed with respect to wall time
In this section, we perform hyperparameter optimization on Neighbor Sampler and Labor Sampler so that the training converges to a target validation accuracy as fast as possible. We leave LADIES out of this experiment because it is too slow can be seen in the last column of Table We ran this experiment on an A100 GPU and stored the input features on the main memory, which were accessed over the PCI-e directly during training by pinning their memory. This kind of training scenario is commonly used when training on large datasets whose input features don't 't fit in the GPU memory. have for this experiment, products and yelp. For products, the validation accuracy target we set is 91.5% 55, and for yelp it is 60%. We tune the learning rate between [10 4, 10- the batch size between [2 10 2 and the fanout for each layer between [5, 25 We use the same model used in Section 4 For LABOR, we additionally tune over the number of importance sampling iterations between [0, 3) so that it can switch between LABOR-i and also layer dependency boolean parameter that makes LABOR use the same random variates r for different layers when enabled, which has the effect of increasing the overlap of sampled vertices across layers. We use the state-of-the-art hyperparameter tuner HEBO [Cowen-Rivers et al. 2020). the winning submission to the NeurIPS 2020 Black-Box Optimization Challenge, tune the parameters of the sampling algorithm with respect to runtime required to reach the target validation accuracy with a timeout of 300 seconds, terminating the run the configuration doesn't reach the target accuracy.
We use larger of the two datasets
We let HEBO run overnight and collect the minimum runtimes required to achieve the target ac- curacies. For products, the fastest hyperparameter corresponding the 38.2s runtime had fanouts (18, 5, 25). batch size 10500, learning rate 0.0145, used LABOR-1, layer dependency False
For Neighbor Sampler, the fastest hyperparameter corresponding to 43.82s runtime had fanouts (15, 5, 21), batch size 12000, learning rate 0.0144.
For the Yelp dataset, the fastest hyperparameter corresponding to the 41.60s runtime had fanouts (6, 5, 7). batch size 5400, learning rate 0.000748, used LABOR-1 and layer dependency True.
For Neighbor Sampler, the fastest hyperparameter corresponding to the 47.40s runtime had fanouts (5, 6, 6). batch size 4600, learning rate 0.000931.
products
yelp
LABOA
LABCS
Grope
230
66
200-
Rurtme
4.50
150
130
30-
50
300 200
300
500
600
100
200
300
400
500
600
700
Figure 4: The runtimes to reach a validation Fl-score of 91.5% on products and 60% on yelp, belonging to runs tried by the HEBO hyperparameter tuner, sorted with respect their runtimes. Having lower curve means that a method is faster overall compared to the others. HEBO could not find any hyperparameter configuration to reach the set target on products, hence curve is left out.
These results clearly indicate that training with LABOR is faster compared to Neighbor Sampling when it comes to time to convergence.
We run the same experiment with GraphSAINT Zeng et al. 2020 using the DGL example code, both on
and yelp using the same model architecture. We used their edge sampler, the edge sampling budget between 12'0,215 25 and learning rate between [10-4, 10000. 'J. We disabled batch normalization to make it fair comparison with NS and LABOR since the models they are using does not have batch normalization. We use HEBO to tune these hyperparameters to reach the set validation accuracy, and it run overnight. The results show that HEBO was not able to find any configuration of the hyperparameters reaching 91.5% accuracy products faster than 1500 seconds.
17

---

For the Yelp dataset, the fastest runtime to reach 60% accuracy was 92.2s, with an edge sampling budget of 12500 and learning rate 0.0214.
A.7 Reducing debiased LADIES complexity from quadratic to linear time
Our proposed PLADIES algorithm in Section 3.1 is linear time and unbiased by construction via
the use of Poisson Sampling, which has the same comparative advantages sampling without replacement over sampling with replacement. However, LADIES authors Zou et al. [2019] formulate
their sampling framework via sampling with replacement while their implementation uses sampling
without replacement, without addressing the bias created thereby. Chen et al. (2023) concurrently
noticed the same bias issue as us, and proposed way to "de-bias" sampling without replacement by
computing actual sampling probabilities in quadratic time (Chen et al. 2023) Section 5.5).
When uses weighted sampling without replacement as in Chen probability is actually not the weights provided initially and Chen et al. [2023] proposes a way to compute the actual probabilities and way to de-bias them in quadratic time. There is convergence difference regarding PLADIES and the de-bias procedure proposed in Chen et al. 2023). only the
[2023] the sampling
computational complexity of sampling different. They also propose a way flatten the probabilities and these flattened probabilities can be fed to PLADIES as well. So the flattening approach Chen al. (2023) proposes is orthogonal to our work.
To give an example of why weighted sampling without replacement biased, consider the prob- abilities [0.7, 0.2, 0.1]. Now, if we want to sample 2 items without replacement, then notice that the probability of the first item, 0.7, more than times the rest of the items, 0.3. Thus, the first item needs to be sampled always. But even if we always sample the first item, the second item is going to be either 0.2 or 0.1, the probability of which one is going to be is [2/3, 1/3]. Thus, in the end, the probability of sampling individual items is [1, 2/3, 1/3]. However, these resulting probabilities are not linearly proportional to the probabilities we started with. Chen et al. 22033 fixes this in quadratic time. We propose to use Poisson Sampling instead. With Poisson sampling, we can have constant to adjust how many items we want to sample. We want 2 items in ex- pectation, so 0.7c + 0.2c 0.1c 2. But the solution is e the first item becomes 1 1.4, which is not possible. So, we need to solve for in the following equa- tion: m0.70. 1) + min(0.2c, 1) min(0.1c. 1) 2. The solution e = 10/3, and this can be found in linear time. The resulting probabilities become: min 1) = 1, min(0.2c, 1) = 2/3, m0..0, 1) 1/3. Because we use these adjusted probabilities during GNN aggregation, our method is unbiased, and faster than Chen et al. [2233 due to the drastic computational complexity difference (quadratic vs linear).
and the probability of sampling
A.8 Links the experimental code
Experiments in Section 4 can be reproduced http:://githhb..c//////////// tribution to DGL can be found in httpt::tttttthhhiee com/ http://hhhhhocooom/aaaaaagg/////
Our initial con-
18


Reviews:
[{"review_id": "SdDL1BP6fS", "reviewer": "Reviewer_gLfM", "summary": "This paper studies the problem of improving the efficiency of GNN training. It first points out that the node-based sampling methods that sample independently ad recursively for each node suffer the neighbor explosion problem (NEP), while the layer-based sampling methods that sample for the whole layer collectively cannot guarantee the approximation of each vertex would be good enough. \n\nTo address these issues, this paper proposes the LABOR sampler which combines the advantages of node and layer-based sampling using Poisson Sampling. The main idea is to conduct neighbor sampling by letting individual vertices make correlated decisions while sampling their neighbors, and introducing a hyperparameter on each node to afftect the expected number of the sampled neighbors. The sampling algorithm would optimize over the sampling probabilities and the newly introduced hyperparameter, s.t. can sample the minimum number of vertices in an unbiased way. Experiments show that LABOR can reduce the sampled nodes and edges, and thus enjoys better efficiency.", "questions": "Q1: For Fig. 1, what is the ``cumulative # sampled nodes/edges``? Is it linear to the number of training iterations?\n\nQ2: How would different fanouts affect the performance?\n\n", "limitations": "Please refer to \"Weakness\".", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The idea of letting the algorithm decide the minimum neighbors to be sampled makes sense and works well.\n2. According to the experimental results, the proposed method works well in reducing the sampled nodes and edges while maintaining the same-level performance as baselines.\n3. Code is provided in the supplementary.", "weaknesses": "1. It would be more clear if the authors can put the main algorithm in the main paper instead of in the supplementary.\n2. The authors only report the it/s (which can also indicates the run-time per iteration), it would be better if the authors can also report the total run-time or the number of training epochs needed to get converged. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the valuable feedback. For the camera-ready version, we will have one more page available. We can move the\nmain algorithm to the main paper as you suggest.\n\nAppendix A.4 has a figure where the x-axis is the number of training iterations. Appendix A.8 has a study about convergence with respect to wall time.\n\nAs for the Q1: It is indeed linear to the number of training iterations. The relationship is encoded in Table 2, $|V^3|$ and $|E^2|$\ncolumns. We plotted Figure 1 this way as the computational complexity of a training step is $O(|V^3| + |E^2|)$ for a 3-layer GNN model as the other\nlayers simply have less work. Also, some GPUs can be simply too fast, and the CPU bottlenecks in DGL can limit the empirical runtime improvements\ndespite LABOR sampling fewer vertices and edges. We captured the speed of an iteration in Table 1. However, on larger-scale datasets where training\ntakes longer and larger batch sizes are used, and more expensive GNN models such as GAT are used, the benefits start becoming more apparent even\nif the fastest GPUs are used for training. Runtime starts to follow the number of sampled vertices and edges in these cases. See Appendix A.6 and Table 5 in the supplementary material.\n\nFor Q2: Flickr dataset has an average degree of 10. If we increase the fanout, then all sampling methods in our experiments would start using the\nfull neighborhoods for almost all vertices. This would make all sampling methods give similar results. However, for other datasets where we have room\nto increase the fanout while still keeping things random, the difference between NS and LABOR and LABOR-i would grow even more. When it comes to the\ncomparison with LADIES variants, we simply chose their hyperparameters so that it equals LABOR-* when it comes to the number of sampled vertices (Table 2) and would expect a comparatively similar convergence behavior across different samplers to the current fanout (10 for each layer)\nexperiments. We will add an ablation study\nfor different fanout experiments in the camera-ready version, and if time permits for the discussion period."}, {"review_id": "BNYfJdP96e", "reviewer": "Reviewer_99pb", "summary": "This paper proposes a novel neighbor sampling (NS) method, called layer-neighbor sampling (LABOR), for training GNNs on large-scale graphs. Unlike the representative NS method, which samples neighbors for each node from a uniform distribution, LABOR samples neighbors for each node using Poisson sampling from a modified distribution. This modified distribution is optimized to match the variance of LABOR with that of NS for each single node. As a result, LABOR can reduce the number of sampled nodes by a large margin compared to NS. Experiments demonstrate the effectiveness of LABOR.", "questions": "1. Equation (8) appears problematic since the variance is independent of the number of sampled nodes, i.e., $\\tilde{d}_s$ or n. If I am wrong about this, please correct me. Considering Equation (8) is fundamental in their follow-up analysis, it is important to explain this.\n\n2. In the first row of Figure 2, the proposed method behaves strangely in the last figure (flickr). Is there any explanation for this phenomenon?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Originality: The proposed method is novel in applying Poisson sampling and its effort to optimize a modified distribution. \n\nQuality: This paper falls within the borderline category, and introducing some in-depth analyses could improve its quality.\n\nClarity: While some unexplained notations and problematic statements exist, this paper is generally easy to follow.\n\nSignificance: Neighborhood explosion is an important problem in GNNs. The proposed method serves as a complement to existing neighbor sampling methods. However, it appears that the computation and memory complexity of the proposed method still exhibits exponential growth with respect to the depth of GNNs.", "weaknesses": "1. Including complexity analysis can help readers to understand how much the proposed method improves over baselines.\n\n2. Wall-clock time is a crucial concern in the efficient training of GNNs. Since the proposed method introduces additional time overhead during neighbor sampling, it may not be advantageous in wall-clock time, despite its superiority in batch size.\n\n3. Baselines for comparison are somewhat old and not state-of-the-art. Introducing some state-of-the-art baselines for comparison may be more convincing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the valuable feedback.\n\nWhen it comes to computational complexity of sampling, let us note that we implemented all parts of LABOR using CUDA, fully parallelized. LABOR-0\nsampling runtime is very similar to or even faster than NS. When importance sampling is used, each iteration of optimizing sampling probabilities\ntakes linear time, basically an SpMV operation, which we accelerate using CUSparse. Our code is available in the supplementary material so you can\nverify our claims by looking at the code. The computational complexity of forward-backward pass is simply linear in the number of vertices and edges \nsampled, which are provided in Table 2.\n\nWall-clock time is simply proportional to the number of vertices and edges sampled if all algorithms are optimized as much as possible. Because\nwe did not have the time to optimize the LADIES variants as much as we did for our proposed sampled LABOR, we chose to scale the x-axis with the\ncumulative number of sampled vertices or edges in Figure 1 (linear to the number of training steps and numbers reported in Table 2 $|V^3|$ and \n$|E^2|$ columns) to make it as fair of a comparison as possible. A very optimized CUDA implementation for NS is already available in DGL and as you\ncan see LABOR is faster than NS even when it comes to iteration speed of training (Table 2 it/s column). Please see Appendix A.8 for a comparison focused on wall time to convergence.\n\nAs for the baselines, our appendix includes a preliminary comparison against the GraphSAINT method. When it comes to most of the other\nstate-of-the-art samplers, our method is simply orthogonal to them. \n\nPoisson sampling simply works by flipping unfair coins to determine whether an edge is sampled. If the probability to sample the edge $t \\to s$ is\n$\\pi_t$, then the expected number of sampled vertices for $s$ will be $\\sum_{t \\to s} \\pi_t$ and the expected number of sampled vertices for the \nwhole layer will be $n = \\sum_{t \\in N(S)} \\pi_t$. So the expected number of sampled vertices $n$ depends on the sum of values of $\\pi_t$ in this case.\n\nFigure 2, Flickr behavior is simply over fitting. In our experiments for Figure 2, we keep all hyperparameters the same except for the batch size.\nLABOR can afford to use a larger batch size as reported in Table 3 under the same vertex sampling budget but simply quickly over fits in this\nexperiment. Our goal was to show that one can either sample fewer vertices and converge in a similar behavior to NS (Section 4.1) or increase the\nbatch size and converge faster than NS (Section 4.2). We do not recommend people to use very large batch sizes for GNN training, we simply wanted\nto highlight the different behavior of sampling algorithms."}, {"review_id": "6IPiElHWTZ", "reviewer": "Reviewer_qFRg", "summary": "This paper improves the previous layer-wise importance sampling algorithm in GNN training by: 1) introduce poison sampling for debiasing; 2) it modifies the sampling importance by incorporating the probability of node-wise sampling, to make sure all nodes have similar neighbor nodes.\n\nIt shows that the variance of each sampled nodes is similar to that of node-wise sampling, while enjoying some benefits of efficiency of layer-wise sampling. It shows that with similar budget, the proposed method converges faster and more memory efficient.", "questions": "See the concerns in the weakness part.\n\n\nAlso, it seems that the pdf format of the submitted paper does not support selecting & searching text, which makes it hard to find some part in the paper. Better to correct this part.\n\nEven after reading the paper, I still think the title of this paper is a bit misleading and unclear. I recommend the authors to reconsider this title and highlight your contributions in the title.", "limitations": "No limitation provided in the main paper.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. It systemetically studeis the limitation of prior node-wise and layer-wise sampling methods, and introduce two remedy: 1) use poison sampling distribution for debiasing, and 2) add back node-wise sampling probability to reduce per-node variance.\n\n2. Results show improvement against LADIES baseline.", "weaknesses": "1. The only two baselines this paper use is neighborhood sampling and LADIES. It's better to include more sampling baselines including FastGCN, GraphSAINT, etc.\n\n2. The paper cites \"Calibrate and Debias Layer-wise Sampling for Graph Convolutional Networks\", which provides several improvement to LADIES. It seems that the problem this paper tries to solve has many similar part of this paper. It's very important to discuss the difference and add the method (flat & debias) of this paper into evaluation.\n\n3. Regarding training speed & time cost, it's better to include a comparison on total time required for the model to converge. Currently the paper only includes iteration/s, but not how many iterations are needed. It's better to show the total time.\n\n4. It's highly recommended to add a psudo-code to show how to implement the proposed LABOR, to make readers understand the method easily.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the valuable feedback. We will be responding to the weaknesses the reviewer pointed out below:\n\n1. FastGCN is superseded by LADIES because FastGCN doesn't even consider the recursive structure of sampling and the previous layer's sampled \nvertices. A preliminary comparison against GraphSAINT can be found in Appendix A.8. As for the other sampling methods, they are orthogonal. \n\n2. In the Calibrate and Debias paper, they propose a really expensive method to debias sampling with quadratic complexity. Our proposed Poisson\nsampling approach and PLADIES method simply have linear complexity and solve the same problem. We further propose a novel way to combine layer and neighbor sampling methods and call it Layer-Neighbor Sampling (LABOR).\n\n3. Appendix A.8 has a study focused on wall time to convergence and hyperparameter optimization. It shows that LABOR is faster than NS and GraphSAINT.\nAlso, Figure 1 is linear in the number of training iterations, and Figure 3 in Appendix A.4 has the x-axis as the number of training steps.\n\n4. Appendix has Algorithm 1 which shows a high-level pseudocode for LABOR. We will move it to the main paper for the camera-ready version as we will have 1 more page allowance.\n\nWe will correct the PDF issue about selecting and searching.\n\nWe will consider alternative titles, and we would be open to recommendations."}, {"review_id": "Mcm46KMaR5", "reviewer": "Reviewer_QdGo", "summary": "This paper proposes a new sampling algorithm called LAyer-neighBOR sampling (LABOR). The authors show the variance of the estimator is controlled. Experiments show this method is much more efficient in sampling and faster in convergence. ", "questions": "1. The proposed method allows a larger batch size. This can make convergence faster. However, a larger batch size may not lead to a better generalization. This makes the statement of a faster convergence weaker. ", "limitations": "There is no potential negative societal impact of this work.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written and clear.\n2. Some analysis is provided. The experiments on some large graph datasets verify the advantages of the proposed method.\n", "weaknesses": "1. Only variance reduction analysis is provided. Theoretical convergence analysis or generalization analysis is lacking.\n2. This paper mainly compares with LADIES, which is a work in 2019. I don't think it is still a state-of-the-art work about graph sampling that is appropriate for comparison. Some more recent works should be covered in experiments for comparison.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the valuable feedback.\n\nFor the first point, since LABOR is a combination of NS and LADIES methods, it wouldn't be hard to extend any proof for their \nconvergence to LABOR. We think that such a theoretical analysis wouldn't be the most interesting part of the paper as it is clear that LABOR should\nhave similar convergence guarantees compared to NS (verified empirically in our experimental section).\n\nFor the second point, we would like to refer the reviewer to read our main rebuttal. There, we explain why we chose our experimental\nsetting as is and chose to keep the discussion among the core sampling algorithms, on top of which many other sampling algorithms build.\n\nWhen it comes to your questions, one can either keep the batch size the same and converge at the same speed as NS (Section 4.1) or use the fact\nthat we sample the same number of vertices with a larger batch size and converge faster than NS (Section 4.2). Section 4.2 just demonstrates\nthe different trade-offs one can make when it comes to choosing hyperparameters. The user can simply choose whatever batch size they want, and LABOR\nwill always (can be proven mathematically easily) sample fewer vertices and edges compared to NS. We do not recommend using large batch sizes for GNN training, only wanted to highlight the different sampler behaviors under various conditions."}, {"review_id": "rNWqbXLgjP", "reviewer": "Reviewer_rBrD", "summary": "The paper proposes the LABOR sampling algorithm to address the NEP problem in GNN. LABOR combines layer sampling (LADIES), neighbor sampling (NS), and Poisson sampling. In contrast to prior works, LABOR calculates the sampling probabilities for importance sampling “iteratively” for each layer. Moreover, the Poisson sampling method (PLADIES) enhances the existing LADIES method by using “sampling without replacement” instead of “sampling with replacement.” Also, the authors derive the hidden layer variance of PLADIES and find that, under certain conditions, the variance can converge to 0, showing better convergence properties. Experiments show that LABOR has better sampling efficiency, using only 1/7 vertex to achieve the same F1-score as NS and using 112 times larger batch sizes during training.", "questions": "Figure 1 shows that the vertices efficiency of LADIES/PLADIES might be higher than LABOR in Reddit dataset. Why?", "limitations": "While the paper addresses an important topic, it has several issues that need to be addressed before publication:\n\n•\tLABOR outperforms NS in a graph with a high average degree (same as the assumption in the NEP problem), such as the Reddit dataset (average degree 493) shown in Table 2. However, when the average degree of the dataset is low (e.g., flickr: 10.09), the performance gap between LABOR and NS will be smaller.\n•\tLABOR is more often compared with NS in the paper, but LABOR is highly based on LADIES/layer sampling method. For example, the vertices efficiency only compared to NS in section 4.2, but Figure 1 shows that the vertices efficiency of LADIES/PLADIES might be higher than LABOR in Reddit dataset.\n•\tNeighbor Sampling (NS) is an important comparison subject in this paper, but it is not detailed in both Introduction and Background. The background simply states, “Neighbor Sampling: The neighbor sampling approach was proposed by Hamilton et al. [2017]” with a citation to GraphSage. Yet, section 3 describes that “Neighbor Sampling currently seems to be the most popular sampling approach.” The latter statement does not seem to refer to GraphSage.\n•\tThe paper needs to report the improvement in the total training time explicitly, as the abstract only mentions “7 times fewer vertices” and “use up to 112 times larger batch sizes compared to NS”.\n•\tTable 2 does not give detailed hyperparameter settings. For example, how were the hyperparameters obtained? what’s the range for hyperparameter sweeping? LADIES paper shows a 5 times total time difference by only adjusting hyperparameters – LADIES (64) and LADIES (512) on the Cora dataset. Moreover, details need to be provided in line241-242 and Figure2’s caption – “The hyperparameters of LADIES and PLADIES were picked to roughly match LABOR-”\n•\t“same sampling budget” needs to be defined more clearly in Table 2.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "•\tLABOR has a better estimator of sampling with lower variances than prior work LADIES, which might not have a vertex with its neighbor among all sampled vertices.\n•\tLABOR has better vertex/edge efficiency than NS. As a result, LABOR can reach the same F1-score by using fewer sampled vertices under the same hyperparameter settings.", "weaknesses": "The experimental evaluation is not sufficiently detailed.\n\nSome technical details are not clear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the valuable feedback.\n\nFor the question about why LADIES and PLADIES vertex efficiencies are higher than LABOR on reddit: Table 2 shows how many vertices and edges are\nsampled in each layer. We are interested in the $|V^3|$ and $|E^2|$ columns as they give the scale of the x-axis for Figure 1. As one can see,\nLADIES variants sample more than an order of magnitude larger number of edges. Reddit, having an average degree around 500, is a very dense graph.\nSo, LADIES variants sample a lot of edges, taking advantage of the denseness of reddit. LABOR, especially LABOR-0 not only tries to be vertex\nefficient, but also edge efficient as the number of sampled edges affects the runtime. So, LADIES variants outperform LABOR variants when it comes\nto vertex efficiency on the Reddit dataset. But even among LADIES variants, PLADIES that we propose is more vertex efficient. So one can say that\nour proposed methods still outperform existing baselines (PLADIES and LABOR vs LADIES and NS).\n\nFor the limitations:\n\n* It is true that when the average degree is low (10.09), and the fanout is 10, then the difference between NS and LABOR is not much. That is due to\nthe fact that at that point, more than half the nodes are using their full neighborhoods. (Sampling 10 random vertices out of $d_s \\leq 10$ vertices\nsimply results in using the full neighborhood.) This is a limitation of all sampling algorithms and we will make this clear in a revised version\nof our paper.\n\n* For Section 4.2, it was not clear to us how to include LADIES in the comparison. This is due to the fact that LADIES hyperparameters directly affect\nhow many vertices should be sampled in a layer. Thus, changing the batch size doesn't change how many vertices are sampled in the last layer. However,\nfor NS and LABOR, the expected number of sampled vertices in each layer is a monotonic function of the batch size and the fanout hyperparameters. So,\nit simply did not make sense to include LADIES variants in Section 4.2. Also, Section 4.1 already achieves the budget sampling comparison of LADIES \nand LABOR that Section 4.2 achieves for NS and LABOR. This is because we chose the hyperparameters of LADIES variants to match LABOR-* in Section 4.1.\nOne can verify this by looking at Table 2, $|V^3|$,  $|V^2|$, $|V^1|$ and $|V^0|$ columns. Note that other works comparing against LADIES simply\nchose a constant number of vertices to be sampled in each layer, and as a result, LADIES performed badly, but we chose to do as fair a comparison\nas we can.\n\n* We used Neighbor Sampling synonymously with the sampling approach proposed in the GraphSAGE paper.\nAll GNN frameworks present the sampling algorithm proposed in GraphSAGE as NeighborSampler. We are not trying to discredit the GraphSAGE paper at all,\nsimply use the more common name in the GNN frameworks. We will add more citations to GraphSAGE throughout the paper to make this more clear.\n\n* Appendix A.8 has a study on wall-time convergence and hyperparameter optimization, including a GraphSAINT variant. There, LABOR beats both NS\nand GraphSAINT when it comes to wall-time convergence.\n\n* Table 2 gives all the hyperparameters you need to replicate our LADIES experiments. NS and LABOR simply used a fanout value of 10 while LADIES\nhyperparameters were chosen to match LABOR-* . You can compare LABOR-* and LADIES along the $|V^3|$, $|V^2|$, $|V^1|$ columns to verify our claim.\nSimply using 64 or 512 vertices per layer for LADIES simply doesn't work well. That is why, LADIES accuracies in other papers are lacking. In our\npaper, one can clearly see that when you choose hyperparameters appropriately and fairly, the test accuracies of different sampling methods are\nequivalent. LADIES performs worse than other methods on the Flickr dataset, and this is due to the fact that original LADIES implementation is biased,\nusing sampling without replacement while the formulation in the paper is sampling with replacement. Since LADIES authors do not account for the bias \nintroduced in their implementation, it simply performs worse than the other unbiased sampling algorithms.\n\nIn the experiments, our goal was to keep everything equal except for what is being compared. In Section 4.1, we chose hyperparameters of different\nsamplers so that it is fair, and did not perform any hyperparameter tuning. From the reported test accuracies, you can see that the end result ended\nup being the same. For Section 4.2, we kept all hyperparameters equal except for the batch size to fit a given vertex sampling budget."}]

Author rebuttal:
We would like to thank all the reviewers for their valuable feedback.

Some reviewers question why we kept our main experimental evaluation to NS, LADIES and LABOR. Firstly, Appendix A.8 has
some comparison against GraphSAINT in terms of time taken to converge to a given 
accuracy target, and results shows that LABOR and NS outperform GraphSAINT. 
As the graph becomes 
larger and larger and the batch size stays fixed, we theorize that the following will happen: Subgraph sampling 
methods similar in construction to GraphSAINT sample vertices/edges independently, thus as the graph size tends to
infinity, the number of edges in the sampled subgraph will tend to 0. Hence, we think that GraphSAINT will not scale. 
Cluster-GCN method is a biased method since it creates clusters and samples vertices
belonging to the same cluster together. In this paper, our goal was to investigate unbiased sampling methods and also 
limit the problem space by assuming no knowledge of vertex embedding distribution so that we can focus the discussion 
on the main limitations of LADIES and NS. Also, we think that this kind of discussion can be left as future work as 
our main focus was non-subgraph sampling methods.

Another subgraph sampling method is SHADOW (Decoupling the Depth and Scope of Graph Neural Networks), which uses
a given sampler such as NS or any LABOR variant as the EXTRACT method and generates an $L$-hop neighborhood. Then,
they use the extracted subgraph and perform training with a model with more
than $L$ layers. Note that, even though it is a subgraph sampling method, it actually uses the $L$-hop neighborhood
of the given seed vertices, unlike GraphSAINT or Cluster-GCN. Also, since it is a meta method, meaning that EXTRACT
can be any sampler, it can actually be enhanced by the use of LABOR-0 instead of NS algorithm they use in their
experiments, enjoying the same benefits we show in our paper.

One can see that the GNN sampling literature has chosen NS as their de facto sampling algorithm, our goal is to change 
that to LABOR-0 (It is used as a direct drop-in) in this paper. Some example works, that we have cited in our paper,
almost explicitly using NS as their samplers:

* VR-GCN: Stochastic training of graph convolutional networks with variance reduction
* SHADOW: Decoupling the Depth and Scope of Graph Neural Networks
* GNS: Global Neighbor Sampling for Mixed CPU-GPU Training on Giant Graphs
* BS: Bandit samplers for training graph neural networks
* Thanos: A Biased Graph Neural Network Sampler with Near-Optimal Regret

All the papers above can be improved just by switching NS with LABOR-0, we are hoping that you are convinced, at this
point, that LABOR-0 outperforms NS in terms of efficiency while matching its quality.

Meta-review: Reviewers acknowledged the contributions in terms of algorithm designs and experiments. The proposed algorithm has been shown to outperform the LADIES baseline and the proposed LABOR method can be incorporated into other layer-wise graph sampling algorithms to gain potential improvements. 

During the rebuttal phase, the authors have well addressed the concern raised by a high-confidence review (Reviewer qFRg) regarding the clarity and the comparison to LADIES. 

One potential issue could be the lack of rigorous theoretical analysis. This may not be as important as the empirical performance improvements (Reivewer QdGo seems partially agree with this), but I still suggest the authors at least conduct the analyses and add them to the revision.

Overall, this is a good paper that develops a new sampling method in training large graph neural networks, which accelerates the convergence and saves the memory cost. I would like to accept this paper. The authors need to carefully revise the paper according to the reviewers' suggestions.
Decision: Accept (poster)