(LA)YER-NEIGH(BOR) SAMPLING: DEFUSING NEIGHBORHOOD EXPLOSION
Authors: Muhammed Fatih Balin
Umit Catalyurek
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph Neural Networks. Sampling

Abstract: Graph Neural Networks have recently received a significant attention, however, training them at a large scale still remains as a challenge. 
Minibatch training coupled with sampling is used to alleviate this challenge. 
However existing approaches either suffer from the neighborhood explosion phenomenon or does not have good performance. 
To deal with these issues, we propose a new sampling algorithm called LAyer-neighBOR sampling (LABOR). 
It is designed to be a direct replacement for Neighborhood Sampling with the same fanout hyperparameter while sampling much fewer vertices, without sacrificing quality.
By design, the variance of the estimator of each vertex matches Neighbor Sampling from the point of view from a single vertex.
In our experiments, we demonstrate the superiority of our approach when it comes to model convergence behaviour against Neighbor Sampling and also the other Layer Sampling approaches under the same limited vertex sampling budget constraints.

Under review as a conference paper at ICLR 2023
(LA)YER-NEIGH(BOR SAMPLING: NEIGHBORHOOD EXPLOSION IN GNNS
DEFUSING
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph Neural Networks have recently received significant attention, however, training them at large scale still remains a challenge. Minibatch training cou- pled with sampling is used to alleviate this challenge. Even so existing approaches either suffer from the neighhorhood explosion phenomenon or do not have good performance. To deal with these issues, we propose new sampling algorithm called Leyer-neighBOR sampling (LABOR). It is designed to be a direct replace- ment for Neighbor Sampling with the same fanout hyperparameter while sampling upto 7x fewer vertices, without sacrificing quality. By design, the variance of the estimator of each vertex matches Neighbor Sampling from the point of view of a single vertex. Moreover under the same vertex sampling budget constraints, LA- BOR converges faster than existing layer sampling approaches and use upto 112x larger batch size compared to Neighbor Sampling.
INTRODUCTION
Graph Neural Networks (GNN) Hamilton et al. (017) Kipf & Welling (201)) have become de facto models for representation learning graph structured data. Hence they have started being deployed in production systems (ing et al. all.)2200 (0188: Niu et al (020). These models iteratively update the node embeddings by passing messages along the direction of the edges the given graph with nonlincarities in between different layers. With / layers, the computed node embeddings contain information from the l-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 et al. (2022b)a). As in general Deep Neural Networks (DNN), it is more efficient to use minibatch training (Bertsekas) 1994) on GNNs, even though is a bit trickier in this case. The node embeddings in GNNs depend recursively are layers, this dependency spans the I-hop neighborhood of the node. Real world graphs usually have very small diameter and if is large, the (-hop neighborhood may very well span the entire graph, also known as the Neighborhood Explosion Phenomenon (NEP) (Zegg et al. 2020).
their set of neighbors' embeddings, so when there
To solve these issues, rescarchers proposed sampling subgraph of the (-hop neighborhood of the nodes in the batch. There are mainly three different approaches: Node-based, Layer-based and Subgraph- based methods. Node-based sampling methods (Hamilton et al.) |017] Chen et al.) 2018a Liu et al.) 2020 Zhang et al. 2021) sample independently and recursively for each node. It was noticed that node-based methods sample subgraphs that are too shallow, i.e., with a low ratio of number of edges to nodes. Thus layer- sampling methods were proposed (Chen et al. 2018b Zou et al., 2019 Huang al., [0118 Dong et 2021). 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., 20200] ZZng et al., 2021) do not use the recursive layer by layer sampling scheme used in the node- and baser- 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 Huang et al. 2018), while others, such as Chen et al. 2018a) Cong et al. (2021). cache the historical embeddings to reduce the variance of the computed approximate embeddings. There are methods sampling from vertex cache Dong et al. (021) filled with popular vertices. Most of these approuches are orthogonal to each other and they can be incorporated into other sampling algorithms.
et al. 2020 Zhang al. 202 I

---

Under review as a conference paper at ICLR 2023
Node-based sampling methods suffer the most from the NEP but they guarantee good approxima- tion for each embedding by ensuring each vertex gets neighbors which is the only hyperparameter of the sampling algorithm. Layer-based sampling methods do not suffer as much from the NEP because number of vertices sampled is a hyperparameter but they can not guarantee that each vertex approximation is good enough and also their hyperparameters nodes to sample at each layer depends highly on the graph structure (as the numbers in Table P show). Subgraph sampling methods usually have more bias than their node- and layer-based coun- terparts. Hence, in this paper, we focus on the node- and layer- based sampling methods and combine their advantages. The major contributions of this work can be listed follows:
hard reason with, number of
We propose a new sampling algorithm called LABOR, combining 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 into a reduction in computation, memory and communi- cation. Furthermore, LABOR has the same hyperparameters as neighbor sampling to use as a drop-in replacement and can speed up training by upto 2.6x.
We experimentally verify our findings, show that our proposed sampling algorithm LABOR outperforms both neighbor sampling and layer sampling approaches. LABOR can enjoy a batch-size of upto 112x larger than NS while sampling the same number of vertices.
2
BACKGROUND
Given a directed graph G (V. E). where V and E C V x V are vertex and edge sets respectively, (1 - 8) E E denotes an edge from a source vertex E V to a destination vertex E V. and Ats denotes the corresponding edge weight if provided. If we have a batch of seed vertices S c V, let us define (-hop neighborhood (S) for the incoming edges as follows:
Graph Neural Networks:
N(s) = [t((t + +) E E), (S)S) N(S) Uses N'(S) N(N
(1)
Let us also define the degree de of vertex s as dg = [N)() uniform edge weights, Al. 1, V(t + s) E E. Then, our goal is to estimate the following for each vertex & E S, where H1 ((("-)) is defined as the embedding of the vertex t at layer / - 1, and (II1) is the trainable weight matrix at layer 1 - 1, and is the nonlinear activation function (Hamilton al. 2017
I. To simplify the discussion, let's assume
- Σ H (1-1) ((-1), H = =Z de 117
Exact Stochastic Gradient Descent: If we have a node prediction task and V, S V is the set of training vertices, Ys, E Vi are the labels of the prediction task, and é is the loss function for the prediction task, then our goal is minimize the following loss function: 1 E.ev, [ys, Z!). [Vl
Replacing V in the loss function with S C V, for each iteration of gradient descent, we get stochastic gradient descent for GNNs. However with / layers, the computation dependency is on NS)),, which reaches large portion of the real world graphs, i.e. (S)) ze [VI, making each iteration costly both in terms of computation and memory.
Neighbor Sampling: Neighbor sampling approach was proposed by Hamilton et al. (0117) to
approximate z!! for each E S with subset of (S). Given fanout hyperparameter k, this subset is computed recursively by randomly picking & neighbors for each s E S from N(s) to form the next layer S¹ that is a subset of N (S). If d, I k. then the exact neighborhood N(ss) (s) is used. For the next layer, S is treated as the new set of seed vertices and this procedure is applied recursively.
Revisiting LADIES, Dependent Layer-based Sampling From now on, we will drop the layer notation and focus single layer and also ignore the nonlinearities. Let us define M, H.W as a shorthand notation. Then our goal is to approximate:
H1
Σ M
(3)
d
1-43
2

---

Under review as a conference paper at ICLR 2023
If assign probabilities Ti Vt ((S) and normalize it that EIEN(S) Te 1, then use sampling with replacement to sample T (S) with [T' n, where is the number of vertices to sample given as imput to the LADIES algorithm and T is a multiset possibly with multiple copies of the same vertices, and let d, = IT n [ss) which is the number of sampled vertices for given vertex 8, we get the following two possible estimators for each vertex E S:
H
1
E
M
(4)
nds (ETON(s)
EIETON(S)
Mr
H E ELETDA(S)
(5)
Note that H in Eq. 4 is the Thompson-Horvit. estimator and the H" in Eq. is the Hajek estimator. For a comparison between the two and how to get an even better estimator by combining them, see Khan & Ugander (202I). The formulation in the LADIES paper uses H but it proposes row- normalize the sampled adjacency matrix, meaning they use H" in their implementation. However, analysing the variance of the Chompson--orvitee estimator is simpler and its variance serves as an upper bound for the variance of the Hajek estimator when [M,] and ne are uncorrelated Khan & Ugander (202T); Dorfman (997), which we assume to be true in our case.
Var(H") Var(H))
1
T Σ
Var(My))
d.
Since do not have access the computed embeddings and simplify the analysis, we assume that (ar = from now on. One can see that Var(H,) is minimized when ग. = p, Vt + under the constraint Σm Tr S. pd, for some constant p E 00 1]. hence any deviation from uniformity increases the variance. The variance is also smaller the larger d, is. However, in theory and in practice, there is 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 werspectiveChhen Chen it is far from optimal in the case of nonlinearities and multiple layers. Even if there is a single layer, then the used loss functions are nonlinear. Moreover, the existence of nonlinearities in- between layers and the fact that there are multiple layers exacerbates this issue and necessitates that each vertex gets a 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, will show how all of these problems are addressed by our newly proposed poisson sampling framework and LABOR sampling.
(0022),
LABOR: LAYER NEIGHBOR SAMPLING
As mentioned previously, node-based sampling methods suffer from sampling too shallow sub- graphs leading to NEP in just a few hops (e.g,, see Table 2). Layer sampling methods Zou et al. (0019) attempt 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 sample in each layer. The original paper of 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 each layer Liu et al. (200)) Chen et al. (022). There no sys- tematic way to choose how many vertices to sample in each layer for the LADIES method, and since each 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 & Lenssen (2019).
We propose a new approach that combines the advantages of layer and neighbor sampling ap- proaches using a vertex-centric variance based framework, reducing the number of sampled vertices
3

---

Under review as a conference paper at ICLR 2023
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 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 good approximation.
3.1 LABOR SAMPLING
The design philosophy of LABOR Sampling is to create direct alternative to Neighbor Sampling while incorporating the advantages of layer sampling. In layer sampling, the main idea can be sum- marized as individual vertices making correlated decisions while sampling their neighbors, because in the end if a vertex is sampled, all edges t + 8, into the seed vertices (s E S) are added to the sampled subgraph. This can be interpreted vertices in S making collective decision whether to sample
The other thing keep in mind is that, the existing layer sampling methods use sampling with replacement when doing importance sampling with unequal probabilities, because is nontrivial to compute the inclusion probabilities in the without replacement case. The Hajek estimator in the without replacement case with equal probabilities becomes:
H" Σ ΣIETnN(S) m2
EIETAN(S)
Mr EIETNN(S) Ms)N(S) ELETNN(S) [N(S)
Re I
1
Σ M tETTN(s)
de
and it has the variance:
Var(H)) = d, - dg 1 d de
(8)
Keeping these two points in mind, we use Poisson Sampling and design LABOR sampling around do layer sampling using Poisson sampling (PLADIES). Given
it. First, let show how probabilities Ne E [0, 1], Vt E N(S) so that E N(S) मे = n, we include E ((S) in our sample T with probability N, by flipping coin for it, i.e., we sample Ta ~ UO. 1) and include t E T if r: S nt. In the end, F|[T|] = n and we can still use the Hajek estimator H" or the Horvitz Thomson estimator H2 to estimate H,. This way of doing layer sampling is unbiased by construction and achieves the same goal linear time in constrast to the quadratic time debiasing approach explained in Chen al. (002)). In this case, the variance becomes (Williams et al. 1998):
1 de
1
Var(H S Var(H,)
(9)
de
One can notice the existence of the minus term J.- and it enables the variance to converge to 0 if all
Te = 1 and we get the exact result. However, in the sampling with replacement case, the variance goes to only as the sample size goes to infinity.
This type of mimicking Layer Sampling with Poisson Sampling still has the disadvantage that d, varies wildly for different s. To overcome this and mimic Neighbor Sampling where E(d.] = min(d,, k), where & is a given fanout hyperparameter, we proceed as follows: for given > 0, Vt E (S) denoting unnormalized probabilities, for a given s, let us define c2 as the quantity satisfying the following equality if k < de, otherwise C. max n.
1
1 1 k d.
(10)
miin(1,cGTT dc ビー
d
Note that i - 1 is the variance when ne d, Vt N(s) that Ejd,] = k. Also note that:
d,
1 1 d, k d, h d, k d, k 1 1 kd,
<0
(11)
k d d k
d, 1
k
d
d
meaning that the variance target we set through Eq. i0 strictly better than Neighbor Sampling's variance in Eq. 8 and will result in F(d.)) 2 lt with strict equality in the uniform probability case.
4

---

Under review as a conference paper at ICLR 2023
Then each vertex S samples t with probability Cy To keep the collective decision making, we sample 7e ~ ((, 1), , vt E ((S) and vertex & samples vertex and only if S CaT Note that if we use uniform random variable for each edge Its instead of cach vertex Tt, and if uniformly initialized, then we get the same behaviour as Neighbor Sampling.
3.2 IMPORTANCE SAMPLING
Given the sampling procedure above, one wonders how different choices of क 2 will affect [7', the total number of unique vertices sampled. In our case, it is extremely easy to compute:
B|T
Σ LEN(S)
P(t
E (EN(S)
min(1, max
(12)
In particular, we need find x² 2 minimizing E[T]):
π arg min z
min(1, max
(13)
(EN(S)
Note that for any given 2 0, E|[T]] the same for any vector multiple æn, 2 Rt, meaning that the objective function is homogenous of degree 0.
3.3 COMPUTING e AND π²*
Note that C₂ was defined be the scalar satisfying the following equality involving the variance of the estimator of Hg:
1
1 dg
(14)
d b-
d
k
we rearrange the terms, we get:
d²
(15)
min(1 m.
k
(+
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 to any precision needed. But we opt to use the following iterative algorithm to compute it:
(0) = 0,
(0)
Σ
(16)
d2
I
(4)
((+1)
d2
Us
(() +
[-+ min(1,
c
2 ((+1)
Σ
Te
(17)
This iterative algorithm converges in most de steps and the convergence is exact and monotonic from below. One can also implement it in linear time ((de) if { |t + s} is sorted and making of precomputed prefix arrays. Note that c(TT) mcaning that is a function of the given probability vector æ. To compute π we use similar fixed point iteration as follows:
म (0) 1, Vt E (S) m. Te. (4) max Co (1) 2-28
((+1)
(18)
Thus, we alternate between computing c = c(T), meaning is computed with the current n. and updating the with the computed values. Each step of this iteration is guaranteed to lower the objective function value in Eq. until convergence to a fixed point, see the Appendix(A. A.I Modified formulation for given nonuniform weight matrix A,s is explained in the Appendix A.3
5

---

Under review as a conference paper at ICLR 2023
Table I: Datasets used in experiments, numbers of vertices, edges, avg. degree, features, sampling budget used, training, validation and test vertex split.
Dataset
[V]
E
E
# feats.
V3l 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 2 90
yelp flickr
717K
14.0M
19.52
300
200k
75 10 15
89.2K
900K
10.09
500
70k
50 25 25
3.4 CHOOSING HOW MANY NEIGHBORS SAMPLE
The variance of Poisson Sampling when म. = A is d. One might question why we are trying to match the variance of Neighbor Sampling and choose to use a fixed fanout for all the seed vertices. In the uniform probability case, if have already sampled some set of edges for all vertices in S, and want to sample one more edge, the question becomes which vertex in S should we sample the new edge for? Our answer to this question is the vertex s, whose variance would improve the most. currently vertex s has d, edges sampled, then sampling one more edge for would improve its variance from de a,
1 to l+d. a, Since the derivative of the variance with respect
to d, is monotonic, we are allowed to reason about the marginal improvements by comparing their derivatives, which is:
0 +
(19)
ddg
Notice that the derivative does not depend on the degree d. of the vertex 8 all, and the greater the magnitude of the derivative, the more improvement the variance of a vertex gets by sampling one more edge. Thus, choosing any vertex s with least number of edges sampled would work for us, that is: s = arg min dy' In light of this observation, one can see that optimal to sample an equal number of edges for each vertex in S. This is one of the reasons LADIES is not efficient with respect to the number of edges samples. On graphs with skewed degree distributions, it samples thousands of edges for some seed vertices, which contribute very small amounts to the variance of the estimator since it is already very close to
4 EXPERIMENTS
In this section, we empirically evaluate the performance of each method in the node-prediction set- ting on the following datasets: reddit (Hamilton et al.) 2017), products (Hu et al.) (020a)). yelp, flickr (Zeng et al. 2020). Details about these datasets are given in Table [ We compare LABOR variants LABOR-O LABOR-1 and LABOR-* where 0, 1, stand for the number of fixed point iter- ations applied to optimize 13 respectively, against NS (Neighbor Sampling), LADIES and PLADIES sampling methods, where PLADIES is the unbiased Poisson Sampling variant of LADIES intro- duced in Section 3.1 We do not include Fast-GCN in our comparisons as it is superseeded by the LADIES paper. The works of Liu al.] (2020) Zhang et al. (002)) Huang al. (2018); Cong al. 2021); Dong et al. (202I) are not included in the comparisons because they either take into account additional information such as historical embeddings or their magnitudes or they have different 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. We evaluate all the baselines on the GCN model in Eq. [2] with 3 layers. with 256 hidden dimension and residual skip connections enabled. We use the Adam optimizer (Kingma & Bal 2014) with 0.001 learning rate. We carried out our experiments using the DGL framework (Wang al.) (019)) with the Pytorch backend (Paszke et al. 2019 Experiments were repeated 100 times and averages are presented.
We will first show that despite the different number of sampled vertices, LABOR and NS training loss curves are almost the same in Section 4.1. with the same fanout and batch size hyperparameters. We will match the hyperparameters of LADIES with the number of vertices sampled on LABOR and
The code will be contributed the DGL. framework after the blind review process.

---

Under review as a conference paper at ICLR 2023
331
6.00
6.0
0.7
0.40
1.24
224
1.2
3.2
6-1
32-
0.38
1009
2000
2000
4230
1003
2000
3000
4002
$230
2003 3300
5632
3020
5006
Figure 1: The validation Fl-score and training loss curves on different datasets with same batch size. The soft edges represent the confidence interval. Number of sampled vertices and edges can be found in 2
see whose batches have better quality. Then, we will show what happens when different sampling algorithms are given the same budget and compare their vertex sampling efficiency in Section 4.2 Section 4.3 shows the reduction in the number of vertices sampled with each fixed point iteration.
4.1 COMPARISON AGAINST NEIGHBOR SAMPLING AND LADIES
In this experiment, we set the batch size to 1,000 and the fanout 10 for LABOR and NS methods to see the difference in the sizes of the sampled subgraphs and also whether convergence behaviour the same. Figure we can see that the convergence curves of both NS and LABOR variants are almost the same showing that sampling smaller subgraphs does not really affect the batch quality. Table 2 shows the difference of the sampled subgraph sizes in each layer. One can see that on reddit, LABOR-* samples 6.9x fewer vertices in the 3rd layer while keeping the same convergence behaviour. On the flickr dataset however, LABOR-* * samples only 1.3x fewer vertices. The amount of difference depends vertices S. If the neighbors 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 Neighbor Sampling and LABOR has to copy the whole neighborhood of a vertex with degree d, I 10. Thus for such graphs, it is expected that there is a small difference because for lot of the vertices, their whole neighborhood is copied. If we look at Table the average degree of the flickr graph is 10.09, and thus there is only small difference between LABOR and NS.
two factors. The first is the amount of overlap of neighbors among the
In Table 2 the number of sampled edges is another important metric to look at. We can see that LABOR-O reduces both the number of vertices and edges sampled. On the other hand, when im- portance 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 be- come nonuniform and it takes more edges per seed vertex to get a good approximation (see Eq. I0)
The hyperparameters of LADIES and PLADIES were picked to match LABOR-* * so that all methods have the same sampling budget in each layer (see Table 2). Figure [ shows that, in terms of loss curve, LADIES and PLADIES perform almost the same on all but there is big difference between the two in favor of PLADIES. We also that LABOR variants either match the quality of PLADIES on reddit or outperform it on products, yelp and flickr.
flickr dataset, in which case
Looking at Table 2 we can see that LABOR-0 has the best runtime performance across all datasets. This is both due to lack of the overhead of performing the fixed point iterations and also it samples the fewest edges, compared to the other LABOR variants. By design, all LABOR variants should have the same convergence curves, as seen in Figure Then, the decision of which variant to use depends one factor: feature access speed. If vertex features were stored slow storage medium
7

---

Under review as a conference paper at ICLR 2023
Table 2: Average number of vertices and edges sampled in different layers (All the numbers are in thousands, lower is better). Last column shows iteration<(miniaatcee)) per second (it/s) (higher is better). The hyperparameters of LADIES and PLADIES were picked to roughly match the number of vertices sampled by the LABOR- to get fair comparison. The convergence curves can be found in Figure The timing information was measured on an NVIDIA T4 GPU. Green stands for best, red stands for worst results, with a 5% cutoff.
Dataset
Algo.
V3
E3
V2
E2
VV
E1
Vo
it/s
PLADIES
24.0
2390
14.1
927
5.97
33.2
1.7
LADIES
25.3
2270
14.5
852
5.97
32.5
1.8
reddit
LABOR-* *
24.1
1070
13.7
435
6.03
26.9
4.1
LABOR-1 1
26.6
261
14.4
116
6.12
16.7
24.8
LABOR-0
35.8
177
17.8
67.1
6.77
9.64
37.6
NS
167
682
68.3
100
10.1
9.65
14.2
PLADIES
160
2380
51.2
293
9.68
11.7
4.1
LADIES
165
2230
51.8
270
9.68
11.5
4.2
products
LABOR-*
166
1250
51.8
167
9.78
10.6
6.2
LABOR-1
178
799
53.4
136
9.78
10.5
21.3
LABOR-0
237
615
62.4
99.6
10.1
9.89
32.5
NS
513
944
95.4
106
10.6
9.89
24.6
PLADIES
100
1300
29.5
183
6.16
6.90
5.1
LADIES
102
1280
29.7
182
6.17
6.90
5,3
yelp
LABOR- *
105
991
30.7
158
6.15
6.83
13.3
LABOR-1
109
447
31.0
96.1
6.18
6.76
27.3
LABOR-0
138
318
35.1
53.9
6.25
6.29
27.2
NS
188
392
42.5
54.8
6.32
6.27
23.0
PLADIES
55.2
309
24.9
84.7
6.23
6.89
10.2
LADIES
55.9
308
25.1
84.5
6.23
6.89
10.5
flickr
LABOR- *
56.6
308
25.6
84.7
6.29
6.95
20.3
LABOR-1
57.7
242
25.9
73.4
6.29
6.93
32.7
LABOR-0
65.9
219
29.1
51.9
6.37
6.71
33.3
NS
73.3
244
32.8
51.9
6.37
6.72
1
31.7
(such as, on host memory accessed PCI-E), then minimizing number of sampled vertices would become the highest priority. in which case, one should pick LABOR Depending the relative vertex feature access performance and the performance of the training processor, one can choose to use LABOR-j. the faster feature access, the lower the j.
4.2 EVALUATION OF VERTEX SAMPLING RFFICIENCY
In this experiment, we set a limit on 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/l column and can be found in Table [ Figure 2 displays the result vertex efficient the sampling method is, the larger
of this experiment. Table shows that the batch size it can use during training. Number of sampled vertices is not a function of the batch size for the LADIES algorithm so do include 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 this experiment that there can be upto 112x difference in batch sizes of LABOR-* and NS algorithms on the reddit dataset, which translates into faster convergence the training loss and validation F1 FI-score curves Figure show.
4.3 IMPORTANCE SAMPLING, NUMBER OF FIXED POINT ITERATIONS
In this section, look at the convergence behaviour of the fixed point iterations described in Sec- tion (3.3. Table Gable shows the number 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
8

---

Under review as a conference paper at ICLR 2023
1.31
1.81
0.0
335
6A6
6.5
6.0
1.43
0.5
0.30
1.5
1.0
2.-
1.41
0.6
1.4
12-
833
3.-
6.0
2009
4030
2005 $230
5602
Figure 2: Validation Fl-score and the training loss curves to evaluate vertex sampling efficiency under the same sampling budget. The batch size is chosen so that the # sampled vertices matches the vertex budget for each dataset and method and it given in Table 3
Table 3:
The batch sizes used in Figure These chosen such that in expectation, each method Having a larger batch-size speeds up convergence.
samples with the same budget given in Table [
Dataset
LABOR-*
LABOR-1
LABOR-0
NS
reddit
10100
8250
3850
products
7750
6000
2750
700
yelp
3700
3300
1950
1120
flickr
3600
3100
1400
800
until convergence, and convergence change in the objective function is less than 10-4 One can see that most of the reduction in the objective function [3 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 in the Appendix A.1
in most 15 iterations in practice before the relative
'able Number of vertices (in thousands) in 3rd layer w.r.t # fixed point iterations (its). denotes applying the fixed point iterations until convergence, i.c., LABOR-* * its stands for LABOR- etc.
Dataset
NS
its
its
3 its
oo
reddit
167
35.8
26.5
25.0
24.7
24.2
products
513
237
178
170
169
166
yelp
188
138
109
106
105
105
flickr
73.3
65.9
57.6
56.8
56.6
56.5
5 CONCLUSIONS
In this paper, we introduced LABOR sampling, a novel way to combine layer and neighbor sampling approaches using a vertex-variance centric framework. We then transform the sampling problem into an optimization problem where the constraint is to match neighbor sampling variance for each vertex while sampling the fewest number of vertices. We show how to minimize this new objective function via fixed-poimt iterations. On datasets with dense graphs like Reddit, show that approach can sample a subgraph with 7x fewer vertices without degrading the batch quality. We also show that compared to LADIES, LABOR converges faster with same sampling budget.

---

Under review as a conference paper at ICLR 2023
REFERENCES
D.P. Bertsekas. Incremental least squares methods and the extended kalman filter. In Proceedings of 1994 33rd IEEE Conference Decision and Control, volume 2, pp- 1211-1214 vol.2, 1994. doi: N0.1109/CDC.199 1994.499411666.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. 35th International Conference Machine Learning. ICML 2018, 3:1503- 1532, 2018a.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling. jan 20.
wttp:/ii..rr//b//////./// 1801 10224
Yifan Chen, Tianning Xu, Dilck Hakkami- Tur, Di Jin, Yun Yang, and Ruoqing Zhu. Calibrate and Debias Layer-wise Sampling for Graph Convolutional Networks. jun 2022. URL http:
//arxiv.orr// abs 2206 00583
Wei Lin Chiang, Yang Li, Xuanqing Liu, Samy Bengio, Si Si, and Cho Jui Hsieh. Cluster-GCN: 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, pp- 257-266. Association for Computing Machinery, jul 2019. doi: 10. 10.1145/3292500.3332 33333999
Avery Ching, Sergey Edunov, Maja Kabiljo, Dionysios Logothetis, and Sambavi Muthukrish- nan. One trillion edges: Graph processing at facebook-
Proc. VLDB Endow., 8(12):
1804-1815, aug 2015. doi: 10. (0.14778//8244332222444 14778/2824033 0ttp//882433222224777
URL https://doi http//ii.org/// org/10.g....ooo
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On the Importance of Sampling in Train- ing GCNs: Tighter Analysis and Variance Reduction. 2021. httl://t///xxxx.orr/////////
2263.02696
Alexander Rivens 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:2012.03822 2020.
Jialin Dong, Da Zheng, Lin F. Yang, and George Karypis. Global Neighbor Sampling for Mixed CPU-GPU Training on Giant Graphs. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 289-299, 2021,
doi: 10. 11114434447588344774777
Alan H Dorfman. The Hajek Estimator Revisited. (4):760-765, 1997. URL http://www:
asasrma http://ooceednngg/aaaaaaeeeee
11100_1100p0000 pdf
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric, 2019. URL
http://wwxw...../abbaaa/.aa/ wwwp//a........... 91t. 02428
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, Vishwanathan, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017. URL /ttps:://proceedggss.. hww.:eeeedddig.....eee.eee..eee. cc/ cc/ppaper/017//11le
C. R. Hoare. Algorithm 65: Find. Commun, 4CM3417)311-32,, jul 1961. doi: 10.1145/366622. 366647.
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- 10000-eeee(NNeuIIP):111111
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, pp. 2704- 2710, 2020b. doi: 10. (0.114/333664333388800
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. Advances in Neural Information Processing Systems, 2018- (eDseeem(Niis); 4558 4567, 2018.
10

---

Under review as a conference paper at ICLR 2023
Samir Khan and Johan Ugander. Adaptive normalization for IPW estimation. pp. 1-31, 2021. URL
http:// /ttt::///xxiv..o//// owg.oo////aa... abt/a/ass/111 07695
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2014, URL
https: /tapps://arxivv org/ /ttg/bs/////oo 11122... 6980
Thomas N. Kipf and Max Welling. Semi- Semi-supervised classification with graph convolutional net- works. 5th International Conference on Learning Representations, ICLR 2017- Conference Track Proceedings, pp. 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 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, pp. 3405-3415, 2020. doi: 10. 10.1145/3394486 3403393.
E Ohlsson. Sequential poisson sampling. Journal of Official Statistics-Stoccholmm- 14(2):199-162, 1998.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lever, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Ed- ward Yang. Zach Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In NeurlPS, 2019.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centri highly-performant package for graph neural networks, 2019. URL https::/aaxiv> org/ abs 9999.99.. 01315
Michael S Williams, Hans T Schreuder, and Gerardo H Terrazas. Poisson Sampling The Adjusted and Unadjusted Estimator Revisited. pp. 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. Proceed- ings of the ACM SIGKDD International Conference Knowledge Discovery and Data Mining, doi: 10.114//2119119332229
pp. 974-983, 2018.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- SAINT: Graph sampling based inductive learning method. In International Conference on Learn- ing Representations, 2020. httphhttt:///opmeee
net
Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kan- nan, Viktor Prasanna, Long Jin, and Ren Chen. Decoupling the depth and scope of graph neural networks. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL httpttttss///peee/////e netee/ewwweeeeeeeeeeeeeeeeeeeeee net/forum?
Qingru Zhang, David Wipf, Quan Gan, and Le Song. A Biased Graph Neural Network Sampler with Near-Optimal Regret. 12 2021. URL htttp://aaxxw..or////// wrtp:////aaab/...../
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 large scale. Proc. VLDB Endow., 15:1228-1244 2022a.
Da Zheng, Xiang Song, Chengru Yang, Dominique LaSalle, and George Karypis. Distributed hy- brid cpu 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, pp. 4582-4597 2022b.
11

---

Under review as a conference paper at ICLR 2023
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.
A
APPENDIX
A.1 FIXED POINT ITERATIONS
Given any π (0) > and one iteration to get (1) and one more iteration using c(T(1) then we have the following observation:
to get T(2),
(1) (0)
max Cs (7)
m Tt
t-
1
1 1
de
min 1, co ( (1))
dg k de
d min(1, c, (+(1)
d
min(1,c, (T((1) max ce (I(0)) |T( (0))
Now, note that for given E N(s,, max cy (T( 2 (T((1))) since {s¹ t 8'}.
This implies that maxt-ss Cy (x((0) (0) 2 cz(2 )T Note that for मं = ca(2 (0) YTT (0) 14 - 8,
we have (TT' 1 for any given Since max. (T())())) )=z 2 (1) (0) T 1I -
(0)
this let's us conclude that the (x(x(()) < 1, because the expression is monotonically increasing
with respect to any of the Tt. By induction, this means that ( S 1, > 1. Since .:()) (0) Te Ii max (x)())))) T. is monotonically decreasing. This means that the objective value in Eq. 13 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 as well.
The intuition behind the proof above is that after updating ' via Eqn. 18 the probability of each edge f + 8 TTC, goes up because the update takes the maximum over all possible This means each vertex gets higher quality estimators than the set variance target so we now have room to reduce the number of vertices sampled by choosing the appropriate increases the quality of the batch which in turn let's 's the C2 step to reduce the total number vertices sampled.
1. To summarize, update step
A.2 EXACTLY SAMPLING A FIXED NUMBER OF NEIGHIBRRS
One can easily resort to Sequential Poisson Sampling by Ohlsson (9988) if one wants d, = min(k, d.)) instead of E[d.] = min(k: k, d.) to get the exact same behaviour to Neighbor Sampling. Given тe. and Tt, we pick the d, = min(k, dg) smallest vertices t + with respect to x which can be computed in expected linear time by using the quickselect algorithm (Hoare) 1961)
A.3 EXTENSION TO THE WEIGHTED CASE
If the given adjacency matrix A has nonuniform weights, then we want the estimate the following:
A.S Σ - Ars
H.
(20)
where A.s = Ei-s Ats. If we have a probability over each edge Tes. V(t - 8) E E, then the variance becomes:
A2 min( 1
(a") < Var(nHl)) = (A.a)²
EAP
(21)
t-
12

---

Under review as a conference paper at ICLR 2023
In this case, we can still aim to reach the same variance target v i
d, any given custom
target Uy R+ by finding cs that satisfies the following equality:
A
ΣAie) 2-+3
(22)
(Ass)²
min(1,
(TT))
t=+
In this case, the objective function becomes:
= arg min
Σ (EN(S)
min (1, max C. t-3
(23)
x20
Optimizing the objective function above will result into minimizing the number of vertices sampled. Given any Tta > 0, (tt -> 8), then the fixed point iterations proposed for the non-weighted case in Eq. 18 can be modified follows:
(++1) max Cgr (T))) (3) A, 8) Ris
(24)
more principled way to choose Ug in the weighted case is by following the argument presented in Section 3.4 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 apply the same argument, then we get:
A2. min (1, COTTES)
vc(Cs) (Ano)2 )
Σ
-
- Ah.
6-+8
Oc. -1
L < 1]A43
Dc,
(Aoa)2
CRTTS
8-28
Eldal(ca) = Σ
min(1, (x7T))
[E(d.]
Σ 1-2
(CCTTe < 1JTts
C2
Then to compute the derivative of the variance with respect to the expected number of vertices sampled for given seed vertex s, which is "e|d,e
can use the chain rule and get:
-1 E,,,
Or. dr. dc. dE Oc, OE|d.] E,s, 1(C,TTs <l]Tes
(A.,)²
(25)
Then, what would do is choose constant C(k) function of the fanout parameter k and set Ov C(k) and solve for c.. C(k) would be negative quantity whose absolute value decreases
[F[d.]
as & increases. It would probably look like C(k) h=
for some constant C" > 0. We leave this
future work.
A.4 CONVERGENCE SPEED WITH RESPECT WALL TIME
In this section, we perform hyperparameter optimization on Neighbor Sampler and Labor Sampler so that the training converges to target validation accuracy as fast as possible.
leave LADIES out of this experiment because it is too slow can be seen in the last column of Table 2 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 commonly used when training on large datasets whose input features don't 't fit in the GPU memory. We use larger of the datasets have for this experiment, products and yelp. For
13

---

Under review as a conference paper at ICLR 2023
products
yelp
300
LABOR
300
LABOR
N5
GraphSAINT
250
250
Runtime (S)
200
Runtime
150
150
100
100
50
0
100
200
300
400
500
600
0 100
200
300
400
500
600
700
Run
Run
Figure 3: The runtimes to reach validation Fl-score of 91.5% products and 60% on yelp, belonging to runs tried by the HEBO hyperparameter tuner, sorted with respect to their runtimes. Having lower curve means that method is faster overall compared to the others. HEBO could not find any hyperparameter configuration to reach the set target on products, hence its curve left out.
products, the validation accuracy target set is 91.5%, and for yelp it is 60%. We tune the learning rate between [10-4, 10, the batch size between [210 2 and the fanout for each layer between [5, 25). We use the same model used in Section 4 For LABOR,
additionally tune the number importance sampling iterations between [0, 3] so that it can switch between LABOR-i and also a layer dependency boolean parameter that makes LABOR use the same random variates 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 al. (020),, the winning submission to the NeurIPS 2020 Black-Bo -ox Optimisation Challenge, to tune the parameters of the sampling algorithm with respect to runtime required to reach the target validation accuracy with timeout of 300 seconds, terminating the run if the configuration doesn't 't reach the target accuracy.
We let HEBO run overnight and collect the minimum runtimes required to achieve the target ac- curacies. For products, the fastest hyperparameter corresponding to 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 43.82s runtime had fanouts (15, 5, 21), batch size 12000, learning rate 0.0144.
For the Yelp dataset, the fastest hyperparameter corresponding to 41.60s runtime had fanouts (6, 5, 7), batch size 5400, learning rate 0.000748, used LABOR-I 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.
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 ogbn-products and yelp using the same model architecture. We used their edge sampler, the edge sampling budget between [2 215 and learning rate between [10-4 10-1]. We disabled batch normalization make it fair comparison with NS and LABOR since the models they using does not have batch normalization. We use HEBO to tune these hyperparameters to reach the set validation accuracy, and let it overnight. The results show that HEBO find any configuration of the hyperparameters reaching 91.5% accuracy on products faster than 1500 seconds. For the Yelp dataset, the fastest runtime reach 60% accuracy 92.2s, with edge sampling budget of 12500 and learning rate 0.0214.
able to
14


Reviews:
[{"review_id": "kimvA2CDCb", "reviewer": "Reviewer_3iA9", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper is about speeding up the GNN training with a new way for sampling which combines layer and neighbor sampling methods. ", "summary_of_the_review": "I think the paper is interesting.  Due to limited experiment results, I am not fully convinced by this method for speeding up GNNs training.", "strength_and_weaknesses": "Strength:\nThe paper is about how to perform sampling GNN training. The sampling method proposed seems a reasonable way to combine the layer and neighbor sampling methods.\n\nWeakness:\n\n1: The proposed method aims to replace NS using a variance reduction sampling and achieves better convergence. The question is whether NS achieves SOTA performance on the standard GNNs datasets?   \n\n2: My main concern is on the experiment part:\n\n1) The paper is about sampling method to speed up GNN training. However, there are no result on wall time for training GNNs.\n\n2) There is no accuracy reported for all the four datasets tested in the experiment part.\n\n3) No comparison with latest GNN fast training methods.  \n\n4) missing ablation studies. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Ar6SJeeI_3Z", "reviewer": "Reviewer_5q4F", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "", "summary_of_the_paper": "This paper proposed a new sampling  strategy: LABOR, which employs the Poisson Sampling to achieve a better sampling variance. Furthermore, it introduces a fanout hyperparameter $k$ and  delicate importance sampling probability to sample much fewer vertices without sacrificing quality. ", "summary_of_the_review": "This paper is about a new sampling strategy of the layer-wise sampling in the GNN training. The details are clear and the analysis of sampling parameters is OK. However, the contribution of this  modification  looks marginal and the experiments failed to demonstrate the superiority of the proposed method. I vote the rejection for this paper.  ", "strength_and_weaknesses": "## Strengths\n - Well organized and easy to follow. \n - Detailed analyze about the sampling probability with   fanout hyperparameter $k$. \n\n## Weakness\n - Technical contribution is limited. Principally, This paper follow the layer-wise sampling paradigm and replace the uniform sampling with the Poisson sampling. The paper also show that this sampling strategy can obtain a smaller sampling variance. This point seems a marginal improvement over the existing sampling framework. Concretely, except for the smaller sampling variance, I can not figure out the benefits of adopting this sampling strategy in the large-scale GNN training from the analysis in Section 3. From the theoretical perspective, would it improve the convergence speed  or reduce the memory cost, or other benefits? \n\n Since the efficient training \n - Lack of comparison with other layer-wise baselines. As mentioned in Introduction, there are several layer-wise sampling algorithms, such as AS-GCN[Huang et al., 2018] and GNS[Dong et al., 2021] (Both of them have released the source code.). However, this paper only make the comparison with LADIES. This is not sufficient  considering both studies have released source codes. \n\n - The experiments can not demonstrate the superiority of the proposed method. First, the paper only shows the training loss curve of all the methods. This is not sufficient since we can not get any cue about how the sampling strategy would affect the generalization ability unless the validation curves or the metrics on the test set are reported. Despite that, the improvement over the training loss is still very marginal and we can only observe its difference according to the zoom-in figure. \n \n - Moreover, to demonstrate the effectiveness of the proposed method. It's better to make such comparisons:  \n   - Vanilla GNN model with full-batch on the small data: to check the performance gain/drop of the proposed sampling method.\n   - Other kinds of sampling strategies, e.g. GraphSAINT [1] and ClusterGCN [2].\n\n\n\n [1] Zeng, Hanqing, et al. \"Graphsaint: Graph sampling based inductive learning method.\" arXiv preprint arXiv:1907.04931 (2019).\n\n [2] Chiang, Wei-Lin, et al. \"Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks.\" Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining. 2019.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6-w7_ur4WxE", "reviewer": "Reviewer_M7QF", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The authors present LABOR, a method that experimentally shows to be better than LABOR neighbor sampling and layer sampling approaches.", "summary_of_the_review": "It is an interesting paper with a great deal of theoretical justification. However, the fundaments rest on general assumptions whose usefulness needs to be assessed with experiments. But, as presented, these experiments are not conclusive enough to judge the pipeline benefits.", "strength_and_weaknesses": "Strengths:\n1. This work addresses the Neighborhood Explosion Phenomenon (NEP), the curse of dimensionality version of Graph Network Training.\nWeaknesses:\n1. The abstract states the method's superiority but not by how much or against what the method is compared.\n2. The same happens in the main body of the work: it is not clearly stated how much better is the proposed pipeline.\n3. The last point is important because the proposed method depends on a long series of assumptions and results that are true in general or valid in limit cases. Thus, the actual effectiveness of the method, which could be shown with experiments, is not indeed shown. Thus, it is challenging to state whether the method is suitable.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject