Revisiting Layer-wise Sampling in Fast Training for Graph Convolutional Networks
Authors: Yifan Chen
Tianning Xu
Dilek Hakkani-Tur
Di Jin
Yun Yang
Ruoqing Zhu
Venue: ICLR 2022 Submitted (2022)
Keywords: GCN
efficient GCN
sampling

Abstract: To accelerate the training of graph convolutional networks (GCN), many sampling-based methods have been developed for approximating the embedding aggregation. Among them, a layer-wise approach recursively performs importance sampling to select neighbors jointly for existing nodes in each layer. This paper revisits the approach from a matrix approximation perspective. We identify two issues in the existing layer-wise sampling methods: sub-optimal sampling probabilities and the approximation bias induced by sampling without replacement. We thus propose remedies to address these issues. The improvements are demonstrated by extensive analyses and experiments on common benchmarks.

Under review as a conference paper at ICLR 2022
REVISITING LAYER-WISE SAMPLING IN FAST TRAIN- ING FOR GRAPH CONVOLUTIONAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
To accelerate the training of graph convolutional networks (GCNs), many sampling-hasee based methods have been developed for approximating the embedding aggregation. Among them, a layer-wise approach recursively performs impor- tance sampling to select neighbors jointly for existing nodes in each layer. This paper revisits the approach from a matrix approximation perspective. We identify two issues in the existing layer-wise sampling methods: sub-optimal sampling probabilities and the approximation bias induced by sampling without replace- ment. We thus propose remedies to address these issues. The improvements are demonstrated by extensive analyses and experiments on common benchmarks.
INTRODUCTION
Graph Convolutional Networks (Kipf Welling, 2017) are popular methods for learning the rep- resentation of nodes. However, it is computationally challenging to train GCN over large-scale graphs due to the inter-dependence of nodes in a graph. In the mini-batch training for an L-layer GCN, the computation of embeddings involves not only the batch nodes but also batch nodes' L- hop neighbors, which is known as the phenomenon of "neighbor explosion" (Zeng et al.) 2019) or "neighbor expansion" (Chen al., [2018a] Huang al.) 2018). To alleviate such computation is- sue for large graphs, sampling-bast based methods are proposed to accelerate the training and reduce the memory cost. These upproaches can be categorized as node-wise sampling approaches (Hamilton
et al.
2017, et al. 2018a), subgraph sampling approaches (Zeng et al.
2019:
Chiang et al.,
2019
Cong et al. 2020), and layer-wise sampling approaches (Chen et al. 2018b Huang et al,,
2018
Zou et al. (019). We focus on layer-wise sampling in this work, which enjoys the efficincyy
and variance reduction by sampling columns of renormalized Laplacian matrix in each layer.
This paper is study of the existing sampling schemes in layer-wise sampling methods. We identify two potential drawbacks in the common practice for layer-wise sampling (Chen et al.] 2018b Zou et al. 2019). First, the current sampling probabilities used are sub-optimal since core assump- tion in FastGCN and LADIES does not hold in many common graph benchmarks, such as Reddit (Hamilton et al. 2017) and OGB(Hu et al. 2020). Secondly, the previous implementations of the layer-wise sampling methods slightly deviate from their theoretical results, and introduce bias in the estimation due the usage of sampling without replacement. Realizing the two issues, we ac- cordingly propose the remedies with new sampling probabilities and a debiasing algorithm. The improvements of the proposed methods are demonstrated by extensive experiments evaluating the matrix approximation error and prediction accuracy on large-scale benchmarks along with some theoretical analyses.
To the best of our knowledge, our result is the first to recognize and resolve the issues with the default assumption and the practical implementation of layer-wis sampling methods for GCN. Once these sub-optimal practices are addressed, we observe that the GCN models consistently converge faster in training and usually enjoy a higher prediction accuracy. We believe the proposed methods can more generally improve the training for GCN as well, e.g., the same strategy can allow node-wise sampling methods to adopt sampling without replacement and further improve the approximation accuracy. Moreover, our discussion the bias induced by sampling without replacement is not limited to GCN, and the debiasing algorithm we develop can contribute to other sampling-bar based machine learning models beyond layer-wise sampling.

---

Under review as a conference paper at ICLR 2022
1.1 BACKGROUND AND RELATED WORK
GCN Graph Convolutional Networks (GCNs, Kipt & Welling (2017) effectively incorporate the technique of convolution filter into the graph domain (Wu et al. 2020, Bronstein al. 2017).
Viewed as an approximation for the spectral graph convolutions (Bruna et al.] 2014 Defferrard
jet eetal, al. 2016), GCN has achieved great success in learning tasks such as node classification and
link prediction, with applications ranging from recommender systems (Ying et al. 20188) traffic prediction (Cui et al. 2019; Rahimi et al. 2018), and knowledge graphs (Schlichtkrull et al. 2018
Sampling Based GCN Training To name few of sampling schemes, GraphSAGE (Hamilton jet al. 2017)) first introduces the "node-wise" neighbor sampling scheme, where a fixed number of neighbors are uniformly and independently sampled for each node in every layer. To reduce variance in node-wise sampling training, VR-GCN (Chen et al. 2018a) applies a control variate approach with historical activation. Instead of sampling for each node, "layer-wise" sampling is more efficient approach: joint sampling scheme for all the existing nodes in each layer so that these nodes can share the sampled neighboring node. FastGCN (Chen al. 201 first introduces this scheme with importance sampling. AS-GCN (Huang et al. 2018) proposes an alternative sampling probability for layer-wise sampling by approximating the hidden layer in the sampling procedure. Then et al. (2019) propose layer-dependent importance sampling scheme (LADIES) to further reduce the variance in training. This alleviates the issue of empty rows in sampled adjacency matrix for FastGCN. For the "subgraph" approach, ClusterGCN (Chiang et al. (019) samples a dense subgraph associated with the batch nodes by graph clustering algorithm; GraphSAINT (Zeng et al.) 2019) introduces normalization and variance reduction in subgraph sampling.
NOTATIONS AND PRELIMINARIES
2.1 GRAPH CONVOLUTIONAL NETWORKS
The GCN architecture for semi- supirsupe node classification is introduced by Kipf & Welling 2017). Suppose we have an undirected graph g (V, where V is the set of n nodes and & is the set of edges. Denote node in V as Us where i E [m] is the index of nodes in the graph and 2,.,,... [n] denotes the set 2 ...,,,,,, n]. Each node 2 E V is associated with feature vector x; E IR" and a label vector y4 E R7. Though we can observe the feature of every node in V and every edge in E, i.e. the n X n adjacency matrix A, we only able to observe the label of partial nodes Virains satisfying Virain C V. Thus, we need to predict the labels for the rest nodes in V\Vtrain and it becomes supervupd learning task. A graph convolution layer is defined as:
((+1)= = PH WWO
H = OZ
(1)
where a is an activation function and P is obtained from applying normalization to the graph adja- cency matrix A; H (1) is the embedding matrix of the graph nodes in the I-th layer, and ( is the parameter matrix of the same layer. In particular, H (0) is the n x p feature matrix. For mini- batch training, the training loss for an L-layer GCN is defined as [Daatehl Eo,Evoeteh E(yi, 2 ( where é the loss function, batch nodes Voatch a subset of Verain at each iteration. 2 is the i-th row in z 2 1 denotes the cardinality of a set.
In this paper, we set P = =D- 1)D-1/2, where δ is a diagonal matrix with D 1+ 1, Aij- The matrix P is constructed as renormalized Laplacian matrix to help alleviate overfitting and exploding/vamishhnn
gradients issues (Kipf & Welling 2017). which is used by Kipf & &Welling (017): Chen et al. (201 Say: Cong et al. (2020).
2.2 LAYER-WISS WISE SAMPLING
To address "neighbor explosion" issue for graph neural networks, sampling methods are integrated into the stochastic training. Motivated by the idea to approximate the matrix ( in (I. Fast- GCN (Chen et al., 2018b) applies an importance-sampling- based strategy. Instead of individually sampling neighbors for each node in the I-th layer, they sample a set of s neighbors s(1) from V with importance sampling probability p., where pi x Σラ= Pj and E, Pt 1. For the (2 - 1)-th layer,
2

---

Under review as a conference paper at ICLR 2022
FastGCN
LADIES
LADIES+fIat
-+- LADIES ddeiisedebaased
debiased
Error (Frob Norm)
Reddit
ogbn-arxiv
ogbn-proteins
ogbn-mag
ogbn- ogbn-products
10'
10
10
10a
10'
1000
2000
1000
2000
1000
2000
1000
2000
1030
2000
sampled nodes
Figure 1: Compare matrix approximation error for layer-wise sampling methods. The matrix ap- samptingllæ proximation enror is measured by || Z 1... The error curve of the original LADIES method shows an abnormal U-shape on ogbn-arxiv and ogbn-mag datasets.
they naturally 1(1-1) S(0), LADIES (Zo et al. 2019) improves the importance sampling probability as
p x Σ oj ENTO ja Vie [n]
In this case, s(1) the nodes sampled for the I-th layer are guaranteed be within the neighborhood of v()) The whole procedure can be concluded by diagonal matrix ( Raxa and selection matrix Q(1) RRixn, which defined as
where A/O = (e,evoWWVv)) and Σ, =
2
11, j j= 0,
$0
(SL 0.
j j= clse,
else
where 10 km are the indices of rows selected in the 1-th layer. The forward prop- agation with layer-wise sampling can thus be equivalently represented as ( Q((+)) H"W() ())) = To ())), where ((+1) the approximation of the em- bedding matrix for layer
EXPERIMENTAL SETUP
In advance of the formal introduction to the the issues and the corresponding remedies in Section and Section we state the basic setups of the main experiments and datasets as they appear multiple times across the paper. Details about GCN model training are deferred the according sections.
Main experiments. To study the influence of the aforementioned issues we evaluate the matrix approximation error (c.f. Figure [ of different methods and consider as a new metric reflect the performance of the sampling strategy on approximating the original mini-batch training in one-step propagation. Since the updates of parameters in the training not involved in the simple metric above, in Section 6 we further evaluate the prediction accuracy testing sets of both intermediate models during training and final outputs, using the metrics Table
Benchmarks. Empirical experiments are conducted on 5 datasets (see details at Table 2 in Ap- pendix B Reddit (Hamilton al. (017). ogbn-arxiv, ogbn-proteins, ogbn-mag and producss (Hu al. 2020). Reddit traditional large graph dataset used by Chen et al.) (2018b); Zou et al. 2019); Chen et al. (2018a) Cong et al. (2020): Zeng et al. (2019). Ogbn-arxiv,
and ogbn-products are Open Graph Benchmarks (OGB) proposed by Hu et al. (2020). Compared to traditional datasets, our selected OGB data have larger volume (up to million-node scale) with more challenging data split. The metrics in Table follow the choices of recent works and the recommen- dation by (Hu et al. 2020
4 RECONSIDER IMPORTANCE SAMPLING PROBABILITIES
The efficiency of laser-wise sampling comes from sampling, and the choice of sampling probabili- ties impacts the prediction accuracy of GCNs, To minimize the variance (for the sake of notational
3

---

Under review as a conference paper at ICLR 2022
Layer 1
Layer
Layer 3
Norm rows HW
10
300
100
200
50
100
0-
0.4
0.6
0.2
0.4
0.6
ogbn-arxiv: Norm of columns in
Figure 2: Fit g ~ Bo + 31 on ogbn-arxiv data. The orange solid line denotes the fitted regression line. All pairs of (x, y) collected from repeated experiments and after the convergence of models. Details of experimental setups, results for other data are deferred to Appendix C..
brevity, from now we omit the superscript (1) when the objects are from the same layer)
E @PQSHW QPHW 1r
Zou et al. (2019) show that the optimal sampling probability p; for node i satisfies (also see Ap- pendix D for a derivation from a perspective of approximate matrix multiplication)
Pi x (H rall [|Qpli] II.
where for matrix A, Aμ and A il respectively represent the i-th row column of matrix A.
4.1 CURRENT APPROXIMATION STRATEGIES AND THEIR LIMITATIONS
The optimal sampling probabilities discussed above are usually unavailable during the mini-batch training. W and H keep changing in the training and even worse we only have access to part of the matrix HW in each batch. To approximate the optimal sampling probability, previous works de- velop two different strategies, 1) approximating the hidden activation HW, or 2) sampling without the information from HW.
representatives of the former strategy is AS-GCN (Huang et al. 2018), which linearly approximate HW by node features. This strategy improves the accuracy of efficient GCN, while the estimation of hidden activation causes considerable overall training time, which in practice is "even longer than vanilla GCN" (Zeng et al. 2019). Another issue of this strategy is that the approximation must be updated during the training procedure. This dependence between sampling and training renders it impossible save training time by preparing sampling results advance of the training.
Instead, the second strategy, the theme of our paper, allows the decoupling of sampling and training, and has been adopted by FastGCN (Chen al. 2018b) and LADIES (Zou et al. 2019). To proceed without the information from HW, FasIGCN (resp. LADIES) assumes (HW) Aill |
(resp. |[@ []), and sets their sampling probabilities as pt x
|| (resp. !!)P)
find this assumption is too strong. To test it, conduct linear regres- sion (1) Bo + Biæ for different layers separately (1 1,2,3), 3), where each (0) is the la norm of one row in (!() and each is the norm of corresponding column in P. The result of ogbn-arxiv is presented in Figure 2 For layer I to layer the intercepts (with stand error) of 4.014(++0.008 and 19. 19.722 respectively, which are much larger than zero with the statistical significance; however, the according slopes 31 's are at a smaller scale: -0.154(#0..00 negative with statistical significance. Such evidence shows that the relation between (H)) and || is pretty unstable and might be even negatively correlated. This violates the assumption that (HWW) x |[] Similar patterns are also observed on the other datasets (See Appendix C33
Vi E in]. However,
the regression lines are 13364(=0.000
4.468 4.46((+0.021) and 2. 1 0.069). Note that 31 for layer I is even
4.2 PROPOSED SAMPLING PROBABILITIES
As analyzed above, the sampling probabilities LADIES are sub-optimal due to the failure their assumption. To address this issue, we instead admit that have prior knowledge of H W. and
4

---

Under review as a conference paper at ICLR 2022
tend to assume uniform distribution of (W |e sampling probabilities:
Il's. With this belief we propose the following
P: x ||QP!I]
Vi E [n].
(3)
Compared to the sampling probabilities of LADIES Equation (2). our proposed sampling proba- bilities 8 are more conservative. From a matrix approximation perspective, rewrite the target matrix product as QPIHW. and only aim to approximate the known part QPI. turns out that assuming the uniform distribution of the norms of rows in HW can help improve both the variance of the matrix approximation and the prediction accuracy of GCNs. We empirically justify our sam- pling probabilities in the next section and Section 6 is presented in Section 4.4
The theoretical analysis of the new probability
4.3 EVALUATION ON MATRIX APPROXIMATION ERROR
To further justify our proposed sampling probability, we consider the following 1-layer matrix ap- proximation error, which evaluates the propagation approximation to the embedding aggregation of full-batch.
(1) batch sampling || = ||Q batch PH ( - Q batch PSH (0) (())..
-Z(1)
sompling are the embedding at the bottom layer for the whole batch (using all avaiable neighbors without sampling) and for certain sampling method; S is the sampling matrix; Qaatch's 's 0, diagonal entries indicate if node is in the batch; || ||F denotes the Frobenius norm of a matrix. The experiments are repeated 200 times, in which we regenerate the batch nodes (shared by all sampling methods) and the sampling matrix for each method. The batch size is fixed as 512 and the numbers of sampled neighbors are 256, 512, 768, 1024, 2536, and 2048. (()) is fixed and inherited from the trained model reported in Section G
where batch batth and 2(1)
It is not surprising to observe that in Figure [ the result of our proposed sampling probabilities (denoted as "LAIDES+flat", blue solid line) is consistently better than that of the original LADIES method (black dashed line) and of FastGCN (black solid line) on every dataset. This supports the new sampling probability in Equation The discussion of the other (debiased) methods this figure is deferred to Section 5
4.4 THEORETICAL ANALYSIS OF THE NEW PROBABILITIES
Whether our choice of probabilities can outperform the previous ones depends on the distribution of the norms of rows in HW. When HWWw)) (n) is not proportional the corresponding & norm of column (+), our proposed probabilities can benefit the approximate matrix multiplication task more than the assuming relation of proportionality. We find the common long-tail distribution of numbers suffices to exert the strengths of the new probabilities, which can be concluded as the following assumption:
To simplify the notation we denote B == QP and C == HW, where P is an n-by-n matrix as defined above. Let m be the number of non-zero columns B, and define C1
Assumption 1.
(E [//)) 2 1. There also exists constant C2 2 1 such that ||[C1/// S ||C <
[BIB../m
C2l C2I/CCll Assume C 2
With the assumption above, show the variance of the approximation with our proposed probabil- ities is smaller than the variance of LADIES by the following lemma.
Lemma 1. We denote the sampling matrix with our probabilities in Equation as S1, and denote
the sampling matrix with probabilities of LADIES in Equation as So- If Assumption 7 holds, then we have
E BS -BC < BS - BC
The proof is provided in Appendix
Remark. Assumption is related to the uniformity in the distributions of [[ [I's and [[ We tentatively discuss the implication of the assumption in Appendix We remark the assumption
5

---

Under review as a conference paper at ICLR 2022
indicates it is unrealistic that the new probabilities outperform the ones in LADIES, distri- butions of datasets can vary. Nevertheless, as shown Section 6 it can be an effective attempt to improve the prediction accuracy of LADIES by simply adopting the conservative sampling scheme.
DEBIAS SAMPLING WITHOUT REPLACEMENT
The theoretical results derived by Chen et al. (201 8b You et al. 2019) guarantee their methods are unbiased approximations of the embedding aggregations GCN training, with an independent and identically distributed (i.i.d.) sub-sample assumption. However, biases are induced in the imple- mentations due to the usage of sampling without replacement. As illustrated by the U-shape curves of ogbn-arxiv and ogbn-mag datasets in Figure [ in the long the matrix approximation error of LADIES even increases with the number of sub-samples. The trend indicates the existence of biases since given unbiased estimation, the matrix approximation error is expected to decrease with more sub-samples used. In particular, such bias is more significant in sparse graphs with small average degrees. In the following subsections, we analyze the implementation of sampling without replacement in LADIES to demonstrate the origin of the bias, and propose new correction method dcbias the estimation while keep using sampling without replacement.
Remark. We insist on the usage of sampling without replacement because it does diminish the vari- ance of the estimation. This practice indeed works for mode-wise sampling methods adopting simple random sampling (SRS, sampling with all-equal probabilities). Specifically, assuming m items are uniformly sampled without replacement from a population of size n, using the same formula for estimation as in sampling with replacement is still unbiased and enjoys the reduction of variance by a finite population correction (FPC) factor 12m
Lohr 2019
Section 2.3).
5.1 WEIGHTED RANDOM SAMPLING WITHOUT REPLACEMENT
We first introduce the implementation and necessary notations of non-uniform sampling without replacement applied in FastGCN and LADIES. Given set V [n|] representing the indices of items (matrices the layer-wise sampling setting) [x and associated sampling probabilities {p:)._, i, the algorithm
be stated as sequential procedure named weighted random sampling
(WRS) (Efraimidis & Spirakis| 2006, Algorithm D). Specifically, aside from the set S₃ of & previ- m Sn 0), the k + 1-th random index 14+1 sampled from the set V V-S,, Sy of the rest n k indices with probabilities
ously sampled indices (0
Pi = Pi,
(0)
Vi E V = [n],
(K) P EjeV Pj
P
4k [m - 1),iE C SS.
In the implementation of previous layer-wise sampling methods, the formula used to estimate the target Σ X; is displayed (after adapted the notations in this subsection) follows:
X //tn//Paap
(4)
which is derived under the sampling with replacement assumption. With the notations introduced, now able analyze the effect of directly using Equation (4) while the WRS algorithm is performed. The expectation a certain summand X X will be
X 11
X
PiNta
Fx
=
Σ
X
(5)
Eiev- S, sEV-
P1a11
PTR1a
where Fx is the o-algebra generated by the random indices inside the corresponding set Sj. Vk =
(M))
Ple+s Liev-a Pi is Fe-measurable. The expectation is in general unequal to the target Σn X, for A > O. except for some extreme conditions such as all-equal p. 's. The bias in each summand (except for the first term with & = 0) accumulates and results in the ultimate bias in the given estimation.
0, m - 1, and the second equation holds because

---

Under review as a conference paper at ICLR 2022
5.2 A REMEDY TO ATTAIN UNBIASED ESTIMATION
The bias induced by the sequential WRS algorithm has been extensively analyzed by many other studies, especially the ones on stochastic gradient estimators (Liang al. 2018 Liu et al. 2019 Kool et al,, 2019). Given a sequence of random indices sampled through WRS, as far as we know
there are two genres to assign coefficients to summands Equation (4). Both of the two methods
relate to the stochastic sum-and-samea estimator (Liang et al. 2018 Liu ct al. 2019). which can be
derived from Equation (5) Using the fact X1,
DiEv-s, P: = [iEv Xi}, a stochastic
Pix11
sum-and-sample estimator of Ei=1 X, can be immediately constructed as
X Ak = 0, mm 1.
M = Σ X; JE
(6)
Plan
(The proof of unbiasedness is brief and provided by Kool al 2019 Appendix C.I).) To minimize the variance, Liang et al. (2018; :::8:::: Liu et allal.22000 (2019) develop the first genre to focus on the last estimator Im and propose methods pick the initial
1 random indices. Kool et al. (019 Theorem 4) turn to the second genre which utilize Rao- Blackwellization (Casella & Robert 1996) of IIm
In fast training for GCN, both of the two genres somewhat inefficient from practitioner's perspective. The first genre works well when _issm-, Ps is close to 1, otherwise the last term in
Im Xiy+1, will brings in large variance and reduce the sample efficiency; for the second genre, Pixl1
the time cost perform Rao- Blekkwellllliiiionnn (Kool et al., 2019) extremely high (O(2")) even with approximation by numerical integration) and conllicts with the purpose of fast training. To overcome the issues of the two existing genres, we propose an iterative method fully utilize each estimator I with acceptable runtime to decide the coefficients for each term in Equation
Conceptually, we recursively perform the weighted averaging below:
Zo = 0, Z++1 (1 ax+1) Z + ax++1 II Vk- 0, 0,
1,
X1 is unbiased and the where 0:411 is constant decided by k. When 01 1, 1 II, pr, unbiasedness of Z., can be obtained by induction as each H is unbiased as well. For the choice of 0*+1'ss 's. we intentionally specify 01++1 (n- motivated by the preference that if all p are 1/n, the output coefficients of the algorithm will be all 1/m, the same as the ones in an SRS setting.
In practice, suffices for the debiasing algorithm to find the coefficients for each X2-1, which can be obtained in advance of the final computation of Z.. We, therefore, adapt the preceding recursive estimation iterative updates of coefficients, and conclude the procedure in Algorithm in Appendix A The time complexity of Algorithm [ is O(m²), as in iteration k + 1 we update the coefficients for the first
random indices sampled. The time complexity is comparable to the one of embedding aggregation in layer-wis wise sampling, shown in Appendix D
5.3 EFFECTS OF DEBIASING
As an immediate result, our proposed debiasing method can significantly improve the matrix ap- proximation error in single step of embedding aggregation. In Figure D we observe in all the five datasets, the debiased variant of LADIES has smaller error, and its error ordinarily drops with the number of sub-samples. When combining the debiasing with the new probabilities raised in Section 2.2] the effect of debiasing is significant only when the graphs (ogbn-arxiv and ogbn-mag) are sparse and when the sub-sample sizes are large enough. We have the following conjectures for this phenomenon. The insignificant improvement is caused by the flat distribution of our proposed probabilities, as the debiasing procedure will maintain the estimation if the sampling probabilities all-equal. For sparse graphs, however, the number of sampled columns (m) is comparable the neighborhood size of the batch nodes (n), and as the biases accumulate the effect of the debiasing algorithm emerges.
We further comment that debiasing is not a panacea for GCN accuracy, and the results in Fig- ure cannot fully predict the corresponding GCN accuracy. Conceptually, the columns sampled are
7

---

Under review as a conference paper at ICLR 2022
Table 1: Summary of prediction accuracy different datasets. The accuracy is reported in the form of percentage (%).
Reddit
ogbn-arxiv
oghn-proteins
oghn-products
ogbn-mag
Full-batch
93.8110.18
66.39:10.25
65.71
68.3320.16
29.60:10.27
Node-wise (2)
92.1340.27
64.51+0.30
65.76++..18
68.71400007
29.05+10.45
Node-wise (10)
94.41110.07
66.47:10.19
66.3411.10
69.37=0.20
29.54:10.27
VR-GCN (2)
94.62110.04
67.49:10.25
67.4511.022
70.9011.28
28.99110.0
VR-GCN (10)
94.36:10.05
66.50-10.33
66.3911006
69.8110.31
29.66:10.68
GraphSAINT
89.47++0.83
60.58+00.2
66.33+0.07
6..77+1.04
24.77+00.88
FastGCN
44.46.12.30
25.44:10.82
$2.4411.88
26.98.10.42
7.1310048
FastGCN (2)
60.31110.70
30.23:11.10
1..80
31.58:1.770
5.85:10.57
LADIES
73.86.10.17
60.95
68. 68.28
52.97.1.111
24.79110.48
w/ flat
90.04+0.11
62.76++0.26
68.26+0.06
62
27.30++.227
w/ debiased
86.73+0.36
61.55++0.40
68.87#0.099
55.92+:.92
25.74+0.80
flat & debiased
89.34+0.40
61.90+t0.33
67. 07.64
62.57=0.22
27.41=0.228
LADIES (2)
88.34410.11
64.01-10.39
68. 18.1710.110
65.2410.40
28.59:10.39
w/ flat
93.64:10.19
66.56:11.84
10.0070
68.47:1..25
29.58:10.19
w/ debiased
92.75++0.22
65.93:40.27
19.14
67.184:022
30.08
w/ flat & debiased
93.59:10.09
66.22:10.10
67.75
68.49:00.06
29.8810.34
mainly decided by the sampling probabilities, and debiasing procedure solely adjusts the weights for different columns. This adjustment partially overlaps with the updates of the parameters W 's)ss in GCN, and therefore the improvement of debiasing to the GCN accuracy will be limited. We claim debiasing should be considered as means to save some parameter updates, more than tech- nique designed to improve the GCN accuracy. We will empirically verify the effect of debiasing in the next section.
EXPERIMENTS
In this section, we empirically evaluate the performance of each method on five node prediction datasets: Reddit, ogbn-arxiv, ogbn-proteins, ogbn-mag, ogbn-products (See Table D We denote "LADIES+flat", "LADIES+debiased" and LLADDIES-fattkdebissee" respectively of LADIES with the improvements from Section 4 from Section 5 and from both. We compare methods to the original GCN with mini-batch stochastic training (denoted by full-batch), two layer-wise sampling methods: FastGCN and LADIES. Apart from that, we also implement the other common fast GCN training methods, including GraphSAGE (Hamilton et al. 2017) (vanilla node- (Chen wise sampling while keep using the GCN architecture), VR-GCN (Chen et al. sampling method GraphSAINT (Zeng al. 2019).
the variants
2018a and subgraph
For the training settings, we use 2-layer GCN for each task with an ADAM optimizer of learning rate 0.001. (Due limited computational resources, full-batch method and node-wise sampling methods require much more GPU memory even when = 3.) The number of hidden variables is 256 and the batch size is 512. For layer-wise sampling methods, we adopt both the classical setting that in each layer the numbers of columns sampled are equal to the batch size 512, and an "increasing" setting (denoted with (2)) that twice nodes will be sampled in the next layer. For the node-wise sampling methods, we combine the settings in the original papers of GraphSAGE (Hamilton et al., (017)) VR-GCN (Chen et al. 2018a) that we separately set the number of neighbors per node as 2 (denoted with (2)) and 10 (denoted with (10)). For the subgraph sampling method GraphSAINT (Zeng et al. 2019), the subgraph size is by default equal to the batch size. The experiment results are reported in Table I with the means and associated
have to the shallow GCN since the
standard deviations based on 5 runs. More details of the settings are deferred to Appendix C.1
6.1 TRAJECTORIES OF MODEL CONVERGENCE
We first compare the convergence rates of different methods. The results on Reddit, ogbn-proteins, and ogon-products are shown in Figure 3 and the results on other datasets are deferred to Figure in Appendix C.2 due limited space.
8

---

Under review as a conference paper at ICLR 2022
Full-berch FastGGN
LADIES
LABNES-debaasg
Node wise
GraghSiIT
LAZ
LADIES debiddeaased
VR-GCN
Reddit
ogion-proteins
ogbn-pproducts
3.9
0.-
Meste 30-
2
0.-
Index
Figure 3: Metrics in each epoch. The layer-wise sampling methods follow the "increasing" setting (denoted with (2) in Table I); for the node-wise sampling methods, the number of neighbors
In Figure 3 (and Figure we observe LADIES (the green curve) tends to move fast at the beginning of training while slow down after the first stage. In contrast, the debiased variants of LADIES have convergence patterns similar to the outstanding while time-consuming methods Full-batch and VR- GCN, and seem to accelerate the training of LADIES at the local convergence stage. Figure also demonstrates that most cases, "LADIES+debiased" converges slower than "LADIES+flat which indicates that regarding convergence, the effect of debiasing is not important choosing a proper sampling scheme. This observation matches our analysis Section [5.3 that debiasing can save some turns of parameter updates and sampling probabilities decide the overall quality of the approximation to embedding aggregations.
6.2 PREDICTION ACCURACY
The prediction accuracy test sets of different datasets is reported in Table We observe the new sampling probabilities and the debiasing algorithm show consistent improvement over exist- ing layer-wise sampling methods, FastGCN and LADIES. In addition, the experiments further ver- ifyy the previous observation that the two remedies we apply have the overlapping effect, which implied in Figure | and Figure that (when sub-sample size is small) the improvement of "LADIES=flat+debiase"
over its ablation method "LADIES+flat" is insignificant. As for the four benchmark methods, the full-batch method and two node-wise sampling methods have outstanding performance the accuracy, as they benefit from the vast amount of computation. The graph- SAINT method demonstrates a tendency to perform well on the dataset with a high average degree, such ogbn-proteins We comment that when the amount of computation is controlled, layer- laser-wise sampling can enjoy similar prediction accuracy to node-wise sampling, as shown in Table
We close this section with remark on the seemingly strange phenomenon that some efficient GCNs aim to mimic the original full-batch GCN while having a higher prediction accuracy on some datasets. We speculate the reason behind this phenomenon is that good approximation can recover the principal components in the original embedding matrix, and also restrain the noise via the sparse / low-rank structure. A similar observation (Sanyal al.) 2018) is found in Convolutional Neural Networks (CNN) as well, that applying low-rank regularizer, such as SVD, to the representation of the intermediate layers can improve the prediction errors of the CNN models.
CONCLUSION
We carefully analyze layer- wise sampling in this work and make two improvements to current layer- wise sampling models. We first show that conservative choice of sampling probabilities outper- forms the existing ones. The latter probabilities assume the L2 norm of embedding is proportional to the norm of the corresponding column of the renormalized Laplacian matrix, which is usually too strong in practice. We further propose a new correction method to debias the estimation in layer-wise sampling through iterative updates of coefficients for columns sampled. The empirical experiments justify our proposed method and show that our method achieves high accuracy close to the SOTA node-wise sampling method, VR-GCN.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geomet- ric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18 42,
2017.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and deep locally connected networks graphs. In 2nd International Conference Learning Representations, ICLR 2014, 2014.
George Casella and Christian P Robert. Rao-blackwelllsstioon of sampling schemes. Biometrika, 83 (1):81-94, 1996.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. International Conference on Machine Learning, pp. 942-950.. PMLR, 2018a.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018b.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 257-266 2019.
Weilin Cong, Rana Forsati, Mahmut Kandemir, and Mehrdad Mahdavi. Minimal variance sampling with provable guarantees for fast training of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1393- 1403, 2020.
Zhiyong Cui, Kristian Henrickson, Ruimin Kc, and Yinhai Wang. Traffic graph convolutional recur- rent neural network: deep learning framework for network-scale traffic learning and forecast- ing. IEEE Transactions Intelligent Transportation Systems, (((11):8833444 2019.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS, 2016.
Petros Drineas, Ravi Kannan, and Michael Mahoney. Fast monte carlo algorithms for matrices Approximating matrix multiplication. SIAM Journal Computing, 36(1):132-157, 2006.
Pavlos S Efraimidis and Paul G Spirakis. Weighted random sampling with a reservoir. Information Processing Letters, 97(5):181-185, 2006.
William L Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. NIPS, 2017.
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. Neural Information Processing Systems (NeurIPS), 2020.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. Advances in Neural Information Processing Systems, 31:4558 4567, 2018.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26. 2017, Conference Track Proceedings. OpenReview.net, 2017. https::::
Wouter Kool, Herke van Hoof, and Max Welling. Estimating gradients for discrete random variables by sampling without replacement. In International Conference on Learning Representationss 2019.
10

---

Under review as a conference paper at ICLR 2022
Chen Liang, Mohammad Norouzi, Jonathan Berant, Quoc Le, and Ni Lao. Memory augmented policy optimization for program synthesis and semantic parsing. In Proceedings of the 32nd International Conference Neural Information Processing Systems, pp. 10015-10027, 2018.
Runjing Liu, Jeffrey Regier, Nilesh Tripuraneni, Michael Jordan, and Jon Mcauliffe. Rao-
blackwellized stochastic gradients for discrete distributions. In International Conference on Ma- chine Learning, pp. 4023-4031. PMLR, 2019.
Sharon L Lohr. Sampling: design and analysis. Chapman and Hall/CRC, 2019.
Afshin Rahimi, Trevor Cohn, and Timothy Baldwin. Semi-supervised user geolocation via graph convolutional networks. In Iryna Gurevych and Yusuke Miyao (eds.), Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics, ACL 2018, Melbourne, Aus- tralia, July 15-20, 2018, Volume 1: Long Papers, pp. 2009-2019, Association for Computa- tional Linguistics, 2018, doi: 10.18653/1//18-111877 URL https: ftcEp:::www... wwwpww/wwwwww.....////////...... org/
anthology/P18- 11877
Amartya Sanyal, Varun Kanade, Philip HS Torr, and Puneet K. Dokania. Robustness via deep low- rank representations. arXiv preprint (001:/8800070000 2018.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European semantic web conference, pp. 593-607. Springer, 2018.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 2020.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Dula Mining, 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 Learning Representations, 2019.
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, 2019.
A ALGORITHM TO SPECIFY THE COEFFICIENTS FOR DEBIASING
The algorithm described in Section 5.2 is provided in this section.
Algorithm 1: Iterative updates of coefficients to construct the ultimate debiased estimator Zm
Input: probabilities {p random indices {I++1
1m-1 1m=) generated by WRS with {p.)
Output: length m coefficient vector Initialize the vector / = O E IR sum of probabilities ps = 0:
for 1: <- 0 to m do
Bkk a(1 ps /P
for j - to
end B = (1-a) a
ps ps PIa11:
end
return 3;
11

---

Under review as a conference paper at ICLR 2022
Table 2: Summary of datasets. Each undirected edge is counted once. Each node in ogbn- beone-nrtein
has 112 binary labels. "D." refers to the average degree of the graph. "Feat" refers to the number of
features. "Split Ratio" refers the ratio of training/validationn validation//est data.
Dataset
Nodes
Edges
D.
Feat.
Classes
Tasks
Split Ratio
Metric
Reddit
232,965
11,606,919
50
602
41
66/10/24
Fl-score
ogbn-arxiv
160,343
1,166,243
13.7
128
40
54/18/28
Accuracy
ogbn-proteins
132,534
39,561,252
597.0
binary
112
65/16/19
ROC-AUC
ognb-mag
736,389
5,396,336
7.3
128
349
85/9/6
Accuracy
oghn-products
2,449.029
61,859,140 140
50.5
100
47
8/2/90
Accuracy
B INFORMATION OF DATASETS
Table summaries the information of datasets used in our experiments.
C ADDITIONAL EXPERIMENT DETAILS
C.I ADDITIONAL DETAILS ON EXPERIMENTAL SETUPS
In this section, we describe the additional details of experiment setups for Section 6 All the models are implemented by Pytorch. We use one Tesla V100 SXM2 32GB GPU with 10 CPU threads to train the models in Section 6 Our implementation of Full-batch method, FastGCN, LADIES are adapted from the codes by Zou et al. (2019): our implementation of vanilla node-wise sampling, VR-GCN, GraphSAINT is adapted from the codes by Cong al. (2020). For the vanilla node-wise sampling method, there are several variants of structures Ying et al. (2018) while we fix the model structure as GCN in our experiments for fair comparison. We use ELU the activation function in the convolutional layer for all the models: ELU((r) = x for x > O, ELU(() = exp(x) - for S O. We choose dropout rate 0.2, which means 20 percents of units are randomly dropped during the training. Validation and testing are performed with Full-batch inference (using all pos- sible neighbors) on validation and testing nodes. Note that some existing Pytorch implementations of GCNs involve several ad-hoc tricks, such as now-normalizing sampled Laplacian matrix. For the accuracy evaluation experiments in Section [6 we stop training when the validation Fl score does not increase for 200 batches. For a fair comparison, we remove certain tricks in our experiments, such as normalization of each rows in the sampled Laplacian matrix in layer-wise sampling. Such trick may help in the practice but it might not be compatible some other methods and is out of the focus of our study. We use the metrics in Table 2 to evaluate the accuracy of each method. Concretely, Reddit is multi-class classification task and Aaklearn.metriss. fl score". For OGB data, we use the built-in evaluator function in module ogb by Hu al. (2020).
the Miero-F1 score with function
C.2 ADDITIONAL RESULTS ON MODEL CONVERGENCE
The convergence results on ogbn-arxiv and ogbn-mag are provided in Figure 4 The setting of each model is the same as in Figure 3
C.3 ADDITIONAL REGRESSION EXPERIMENTS
For the regression experiments in Section we train 3-layer GCN without sampling, i.e., full- batch SGD training, with 256 hidden variables per layer. The batch size is 512. Early stopping check the as-
training policy applied. We also remark that these experiments are conducted sumption of importance sampling, rather than pursuing SOTA performance. When we finish training the model, the norms of rows HW are extracted through a full-batch inference with all training
nodes. Hence, we only record the pairs (z(") yy''s for sampled nodes in regression, where indicates the index of the sampled nodes in the 1-th layer.
Figure is supplementary to Figure 2 The assumption: || (HW):a) x ||P|||] does not hold on all of these datasets. We do not have the regression result on the ogbn-produs dataset since the training of 3-layer GCN fails due the memory limitation.
12

---

Under review as a conference paper at ICLR 2022
Full-batch FastGCN
LADIES
LADIES+debiased
Node-wise
GraphSAINT
Lflt
LADIES debb-daassed
VR-GCN
ogbn-arxiv
ogbn-mag
0.7
0.6-
Metric on validation Sec
0.5-
0.20
0.4
0.15
Ww
0.05
Index of opochs
Index opochs
Figure 4: Metrics in each epoch.
Layer 1
Layer
Layer 3
Norm rows HW
400
200
200
200
100
100
100
0-
0.00
0.75
0.25
1.00
0.00
0.25
0.50
0.75
reddit: Norm of columns in P
Layer 1
Layer
Layer 3
Norm of rows in HW
400
75
50
200
0
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
agbn-proteins: Norm columns in
Layer 1
Layer
Layer 3
Norm of rows in HW
100
300
10-
200
100
0-
0.2
0.4
0.6
0.2
0.4
0.6
0.2
0.4
0.6
ogbn-mag: Norm columns in
Figure 5: Regression Reddit, ogbn- ogbn-protein protein, ogbn-mag datasets. SGD.
GCN is trained with full-batch
13

---

Under review as a conference paper at ICLR 2022
C.4
DISTRIBUTIONS OF THE NORM OF Rows / COLUMNS RELATED MATRICES
reddit
Frequency
0.04
0.020
0.015
6-
0.05
0.01
0.00
0.00
10
0.000
0.25
0.50
0.75
1.00
40
60
80
100
20
40
60
80
20
40
100
Norm Cols
Norm of HW:
Norm of
HW:
Norm of
HW:
ogbn-arxiv
Relative frequency
2.5
0.8
2.0
1.5
0.04
0.4
0.10
1.-
0.02
0.5
0.2
0.0
Norm of Cols in P
Norm of rows HW: lay-1
Narm of rows in HW: lay-2
Narm of rows HW: lay-3
ogbn-proteins
Relative Frequency
0.06
0.008
15-
10
2-
1-
3.6
4.4
100
200
Norm Cols in
Narm of rows HW: lay-1
Narm of rows HW: lay-2
Narm of rows HW: lay-3
ogbn-mag
Relative Frequency
0.03
0.4
9.01
0.0
0.00
0.00
0.2
0.4
0.6
60
Norm Cols
Norm rows HW: lay-1
Norm rows HW: lay-2
Norm of rows HW: lay-3
Figure 6: Distribution of |||||| and [I(HW) [;;] for Reddit, ogbn-arxiv, ogbn- booneir and ogbn-mag.
Figure demonstrates the distribution || and (I(HW) Aayl (layer 1, 2, 3) for Reddit, ogbn- arxiv, ogbn-protein and ogbn-mag datasets. The [| ((HW) Il' are obtained from the experiment
in Section C.3
The outliers larger than the 99.9% quantile small than the 0.1 % quantile
removed.
As shown in the histograms, analysis regarding Assumption T tends to hold generally these datasets. For the norms of columns in P (as replacement for QP for clarity), we observe there some columns with large norms far beyond the average. Those columns contribute lot the quadratic mean, which results in a huge C₁ in Assumption[] In contrast, the norms of rows in W concentrate around their average, inducing small C2. Those facts together with Assumption D and Lemma [ in the main paper explain why our proposed sampling probabilities are more proper for some real datasets.
D TIME COMPLEXITY ANALYSIS
We analyze the complexity of vanilla node-wise sampling and layer-wise sampling in this section. The analysis is adapted from the work by Zou et al. (2019), ) but we show lighter bound for layer- the propagation formulas for sampling based GCN
wise sampling. For / such that 0 < can be formulated as:
(1+
p(0 H (
14

---

Under review as a conference paper at ICLR 2022
where H 7 E R' p() E R W E RPx,, In particular, for LADIES, P(()
LADIES = ((+1))
Table 3: The time complexity for computation for L-layer GCN training by layer-wise sampling and node-wise sampling. The first column refers the matrix operation type, nodes aggregation or linear transformation.
Layer-wise (scpL)
Node-wise O p)
Nodes Aggregation
Lincar Transformation
(ssp'L)
O(sb 1-1 p²)
For simplicity, we suppose that the number of hidden variables in each layer is fixed as p, the same the dimension of (0),, The batch size and the numbers of nodes sampled in each layer equal are set all equal to a fixed constant s. We assume the number of sampled neighbors per node in node-wise sampling is b. We denote the maximal degree of all the nodes in the graph as c. The computational cost of the propagation comes from two parts: the linear transformation, a dense matrix product, ((() and the node aggregation, a sparse matrix product, P(U) (()). The time complexity is summarized in Table 3 We additionally comment although the time cost of two parts both linearly depend the number of nodes involved (number of non-zero elements in 1))+ ), the node aggregation part usually dominates since the sparse matrix product involved is less efficient than the dense matrix product involved modern computer.
The linear transformation, ( is dense matrix production. The cost depends on the shape of two matrices, and is given O(spp") LADIES fixes as 8 for each layer, so O(sup)) (spp)). For node-wise sampling 81 sb6-1, since number of node exponentially grows. Thus by summation over all the layers, we have the results in the second row in Table
The node aggregation, po ( (() is sparse matrix production, since p(() is sparse. For simplicity, denote (9) (1() C E R**P, Thus the time complexity of this sparse matrix production becomes ((nz(())p) where (nz)(f)) is the number of non-zero entries in p(), For layer-wise sampling, since we sample nodes for each layer and each node has at most neighbors, so (P) < sc. For node-wise sampling, since each node has b neighbors and the neighbors are shared by all the nodes in each layer, (2) bsi sb=+1-1, By summation over all the layers, we attain the results in the first row of Table 3
E RESULTS IN APPROXIMATE MATRIX MULTIPLICATION
In this section, we revisit approximate matrix multiplication to derive the previous layer-wise sam- pling methods. Specifically, the sampling matrix S used in FasIGCN and LADIES can be decom- posed as S IIIT", where II E Raxd is sub-sampling sketching matrix defined follows:
Definition E.1 (Sub-sampling sketching matrix). Consider discrete distribution which draws i with probability pa > 0, vi [n). For a random matrix II E Raxd II has i.i.d. columns and each column IT)) can randomly be Táp, e, with probability pi, where es is the i-th column of the n-by-n identity matrix In, then II is called sub-sampling sketching matrix with sub-sampling probabilities {
With this definition, we introduce result in AMM to construct the sub-sampling sketching matrix, which coincides with the conclusion in FastGCN and LADIES.
xn, C Baxne, the number of sub sub-sampled columns d 2 such that I S d < n. and the sub-sampling probabilities {p.) are such that Et_P. Pi = 1 and such that for a quality coefficient E (0, 1]
Theorem E. (Theorem (Drineas et al.) 2006)). Suppose B R
|
p: 2 3
Vi E [n]. BI
Construct a sub-sampling sketching matrix II E Raxd with sub- sobb-ampling probabilities {pr) in Definition E.1 and let B C. be an approximation BC. Let 8 (0, and n
15

---

Under review as a conference paper at ICLR 2022
1 (88))oo((1/)) Then with probability least 1 -
11² B
|BC BUN CII < 3d
The theorem is closely related Lemma 1 in Appendix of LADIES, which studies the 2 For the choice of sub-sampling probabilities, Equation (7) reproduces the conclusion in FastGCN and LADIES, when respectively take B P and QP
Remark.
variance E BC - B
F PROOF OF LEMMA 1 AND SOME REMARKS
To prove Lemma in the main paper, we first adapt a technical lemma (Zou al. 2019 Lemma 1), which relates the sampling matrix to the variance (expectation of squared Frobenius norm) of the approximate matrix multiplication.
Lemma F.1 (Adapted from Lemma [Zou et al., 2019 Given two matrices
x" and C' E Iaxxn for any E [n] define the positive probabilities pi such that Ei= = 1. We further
require the probubility p; 0 if and only if the corresponding column B row C₁g is all-zero. The sub-sampling sketching matrix II Raxd is generated accordingly. Let III it holds that
Es [|CSC
BC
1 d
Σ fpp Pi
B
BC
where d is the number of samples.
With the lemma above, the proof of Lemma in the main paper is provided as follows.
Proof. Recall the notation in Lemma I in the main paper is simplified as B == QP.C= : HW. As the union of neighbors of nodes in cannot and we accordingly define an Q 2-maasurable matrix L as in Lemma F. We have
all the nodes,
columns B are all-zero.
E BS - BC = EQQ Es,
(I C
BC
Q)]
= EQQ
Σ E.POS0
B 1
||C
BC
Pi
where the second equation holds as we apply Lemma to the inner expectation in the right-hand (Equation in the main paper) into the preceding
side of the first line. Plugging Pt x |||||| probabilities p s. we reach
Be (Cispoo
[B(|l]
Σ
Exp
B ||C]
EQ
[I]
BC
BBB BC
- EQ
B
B
1 ā
BQ [[
As computed by Zou al. (2019), the variance of LADIES is similarly given as
BS&C B
1
EQQ
Σ
Σ
|| / - EQQ [[[CC||]]
d
Consequently, prove the lemma it suffices show that
1)
Σ B(b1))))
(
Σ (I
Σ Pp
B
Σ pp
B
<
(9)
16

---

Under review as a conference paper at ICLR 2022
and the inequality above follows with Assumption 1 Specifically, plugging the inequality C2 C2l|C||B// /, Vi [n] in the left-hand-side ahove, have
||Ciy]12=
Σ E:py 20
B
Σ
B Gall
1
C2
|
m
C2 B
ml
C
n
C1
mm
B
in which the last equation comes from the definition C1
To close the proof, we
(E: | l/m)"
utilize the inequality C2 | s |||
and bound ml m||CI| by nO2 Eipco
Cly l
Finally
we attain Equation (9) with the core assumption
C1 2 C7
Remark. In Assumption we indeed implicitly assume |B]l]|ss follow a long-tail distribution that most norms are around the average while few columns have large norms. The high non- uniformity makes the average of squared norms much larger than the square of averaged norms. For |[C]gll's, 's, considering the normalization techniques (such as batch or layer normalization) to stabilize the scale of the parameters, they tend to not vary widely, which implies small C2. The numerical experiments on the comparison of approximation error (see Figure I and the histograms of the norms in trained models shown in Figure 6 further validate the assumption. Based on the empirical analysis above, we claim the assumption mild and tends hold at least for some datasets.
G SUPPLEMENTARY EXPERIMENTS OF REBUTTAL REVISION
G.1 SUPPLEMENTARY REGRESSION EXPERIMENTS
we also present the regression results in Figure and F for 3-layer GCN with our LADIES flattdebaattebiass sampler and LADIES sampler respectively Both of them have 512 nodes sampled at each layer and keep other hyper-parameters the same as regression experiments. The regression results in the following figures show similar patterns to Figures and
In addition to the regression experiments Section 4.1 and Appendix C33
G.2 SAMPLING TIME AND TRAINING TIME
We compare the sampling time per batch for 1-layer GCN with layer-wise sampling methods (Fast- GCN, LADIES, and our proposed methods) and GraphSAGE. The time is presented in milliseconds. The batch size is 512, and the number of sampled nodes is 512 or 1024. The average sampling time (followed by standard deviation) over 200 batches is presented in Table We note that the sampling time may involve some overhead costs. For example, the input Laplacian matrix is Scipy- spipe--p matrix on the CPU, while in sampling, it is converted to a Py ToTroh--parse-matrii
By Table 4 we conclude that the cost of debiasing algorithm is acceptable. Moreover, since the debiasing only depends on the number of nodes sampled, its time cost will be dwarfed by sam- pling on very large graphs. For example, sampling 512 nodes, the average batch sampling time for "LADIES", "LADIES + debiased", "LADIES + flat + debiased", are 8.3 + 0.1, 11.7 + 0.2, 11.7 + 0.5 respectively on ogbn-arxiv while 83.4 + 1.3 and 83.7 = 0.8 and 83.5 + 0.6 respectively on ogbn-products data. We remark that the node-wise sampling takes significantly longer time because individually sampling from each row in the re-normalized Laplacian matrix (stored as a sparse matrix in implementation) leads to a large overhead cost.
We present the training time per batch for 2-layer and 3-layer GCNs with different methods in Ta- 5lnd (ablees
The time is presented in millisecond and averaged over 1 110 batches, where we discard the first 20 and the last 20 out of 150 total batches to disregard potential warm-up time for GPU. The other settings are kept the same Table [ We note that the timing on GPU is sensitive to the hardware and has a relatively large standard deviation.
experiments of accuracy evaluation in
As presented in 5 and 6 our proposed methods have similar training time with LADIES due to the same propagation scheme of GCN with layer-wise sampling strategy. The VR- generally shows superiority in prediction accuracy (see Table []. However, it also takes a significantly longer time in training since its propagation involves using and updating historical activation.
17

---

Under review as a conference paper at ICLR 2022
Layer
Layer 2
Layer 3
Row norm of HW
100
100
50
50
0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
reddit: Column norm of P
Layer
Layer 2
Layer 3
Row norm of HW
7.5
75
100
5.0
50
25
2.5
0
0.2
0.4
0.6
0.2
0.4
0.6
0.2
0.4
ogbn-arxiv: Column norm of
Layer
Layer 2
Layer 3
Row norm of HW
75
5
50
100
4
25
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.5
ogbn- proteins: Column norm of
Layer
Layer 2
Layer 3
Row norm of HW
150
10
5
50
20
0
0.2 0.4
0.6
0.2
0.4
0.6
0.2
0.4
0.6
ogbn-mag: Column norm of P
Figure 7: Regression on Reddit, ogbn-arxiv, ogbn-protein, ogbn-mag datasets. GCN is trained by LADIES flat + debias sampler. The fitted regression line is in orange color.
18

---

Under review as a conference paper at ICLR 2022
Layer
Layer 2
Layer 3
Row norm HW
40
50
50
20
25
25
0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
reddit: Column norm of P
Layer
Layer 2
Layer 3
Row norm of HW
10.0
200
7.5
5.0
100
100
2.5
0.2
0.4
0.6
0.2
0.4
0.6
0.2
0.4
ogbn-arxiv: Column norm of
Layer
Layer 2
Layer 3
Row norm of HW
100
150
6
100
5
50
50
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.5
ogbn-proteing Column norm of
Layer
Layer 2
Layer 3
Row norm HW
150
100
100
0
0.2
0.4
0.6
0.2
0.4
0.6
0.2
0.4
0.6
ogbn-mag: Column norm of P
Figure 8: Regression on Reddit, ogbn-arxiv, ogbn-protein, ogbn-mag datasets, GCN is trained by LADIES. The fitted regression line is in orange color.
19

---

Under review as a conference paper at ICLR 2022
Table 4: Average sampling time (in milliseconds) per batch for layer-wise methods and vanilla node- wise method (GraphSAGE)). 512 and 1024 (followed with the dataset name) indicate the number of node sampled for one layer. The "T" and "d" in "LADIES+f+d" denotes "flat" and "debiased" respectively.
PastGCN
LADIES
LADIES+I
LADIES+
LADIES+f+d
Node-wise
Reddit (512)
10.6 + 0.9
10.9 0.3
10.0= 0.2
13.1 0.3
13.1 0.4
632.5 4.3
Reddit (1024)
10.0 =
11.8 1.4
10.4
0.4
16.1
637.0 4.2
arxiv (512)
0.1
8.3
7.8
11.7 0.2
11.7
585.2 + 3.6
arxiv (1024)
6.1
9.7
9.0
17.2 0.3
16.5 0.3
585.6 + 3,1
mag (512)
16.8 16.
0.1
24.5
30.0
27.8
1084.3 +: 1.7
mag (1024)
= 0.2
0.2
27.7
0.2
3.19
=
proteins (512)
11.11
0.3
0.2
0.26
12.6
830.9 + 5.3
proteins (1024)
8.9
12.4
11. = 0.1
0.2
18.0
804.2 + 4.6
products (512)
54.8 0.7
1.3
80.3 = 0.4
83.7 0.8
0.6
2795.4 + 4.7
products (1024)
57.1 0.5
78.7 0.7
0.6
85.4
2737.7 + 4.8.
Table 5: Average training time (in milliseconds) per batch for a 2-layer GCN.
Reddit
ogbn-arxiv
ugbn-mag
ogbn-proteins
ogbn-products
Full-batch
372
65.2
72.3 8.25
1702 1 67.0
77.8
FastGCN
9.47 + 1.21
2.11
23.3 6.27
8.50 + 1.22
7.43 + 1.04
FastGCN (2)
9.47 + 1.25
5.09
20.8 5.71
8.76 1 1.06
8.34 : 1.11
LADIES
7.95 + 1.03
1.25
16.7 4.54
8.69 1.11
10.3 + 1.24
flat
7.86 + 1.04
1.30
26.1 6.54
+.00
8.03 + 1.07
dehiased
7.86+.111
3..1
5.67
8.21 +
8.44 +
w/ flat & debiased
8.01 1.09
2..59
20.5
9.06 1.6
8.11 + 1.09
LADIES (2)
2.00
22.7 6.05
8.83
11.2 1 1.35
flat
8.70 1.13
2..1
10.3 5.65
13.1 + 1.52
debiased
8.75 1.15
1.94
1 14.6
8,54
w/ flat & debiased
8.12 1.13
3.60
13.3 4..5
12.5
8.50 + 1.15
Node-wise (2)
8.13 1.12
3.64
9.50
8.34 1 1.21
Node-wise (10)
11.3 1.33-1.05 1.05
1..7
10.3 5.60
11.7 1.31
VR-GCN
153 17.3
86.8
106 12.4
42.7
88.5 2.51
VR-GCN (10)
302 23.9
1.4
175 - 15.1
15.1
360 45.6
402 - 65.3
GraphSAINT
8.23 + 1.14
23.1
2
8.34
8.26 + 1.11
Table 6: Average training time (in milliseconds) per batch for 3-layer GCN.
Reddit
ogbn-arxiv
ogbn-mag
ogbn-proteins
ogbn-products
Full-batch
1042.8 = 30.1
148 5.8
352.1 = 11.5
3312.3 = 82.1
4490.7 102.6
FastGCN
16.9 + 6.3
30.8 4.3
19 4.8
13 1.3
8.9 + 1.0
FasIGCN (2)
9.6
4.6
18.9
9.8
9.4 1.1
LADIES
10.6 + 1.3
27.6
19.9 + 4.8
11.11.3
8.9 1.0
w/ flat
3.9
1.41
9.9 1.0
w/ debiased
10.1
3014.1
5.5
10.6
10.6
& debiased
9.7
3..1
1.3
1..9
9.3
LADIES (2)
1.2
2914.1
1.12
10.5
1.1
w/ flat
1..1
2772+3.77
2
1044
1..1
w/ debiased
1..3
2.17+3.11
23.3
10.5
1.3
flat & debiased
1.1
2.4
24.8
1..5+
9.9 19+1111
Node-wise (2)
10.9
27
4.3
1..5
11.5
Node-wise (10)
77.8 17.8112
3.39
52,4 52.4
24.6 + 1.1
50.4 1.I
VR-GCN (2)
379.7 23.6
154.1
218.7 + 16.7
428.9 +
473.6 + 69.7
VR-GCN (10)
858.1 1232
224.9 17.8
488.1 34.7
1618.7 67.3
2075 112.8
GraphSAINT
9.5 1.1
22.6 - 3.2
21.2 5.6
11.2 1
10.5 1.0
20

---

Under review as a conference paper at ICLR 2022
G.3 FINER VISUALIZATION OF FIGURE AND AND FIGURE
To better differentiate the distinct sampling-based methods in Figure 3 and Figure 4
we provide
Figure group the methods of the same type by the same color and demonstrate the trajectories of model convergence. We also provide Figure to only compare the layer-wise sampling methods (FastGCN, LADIES, LADIES LeDiES+debiasd, LADIES+fattddeisss
Full-batch FastGCN
LADIES
LADIES +debiased LADIES-flat+deblased
Node-wise VR-GCN
GraphSAINT
LADIES+1lat
Reddit
ogbn-arxiv
ogbn-proteins
0.7
Metric dev set
0.9
0.7
0.8
0.5
0.7-
0.4
0.6
0.5
0.2
0.4
0.4
10a
10
10a
10a
10a
102
ogbn-products
ogbn-mag
Metric on dev set
0.8
0.25
0.20
0.6
0.15
0.4
0.10
0.05
0.00
10a
10
10a
10"
10a
10a
Index of epochs
Index of epochs
Figure 9: Metrics in each epoch.
FastGCN
LADIES
LADIES+flat
LADIES+debiased
LADiES++lat+debbiseed
Reddit
ogbn-arxiv
ogbn-proteins
Metric dev set
0.6
0.7
0.8
0.4
0.6
0.5
0.2
0.4
10a
10a
10a
10a
10a
10a
102
ogbn-products
ogbn-mag
Metric on dev set
0.8
0.25
0.6
0.15
0.4
0.10
0.05
0.2
0.00
10a
10a
10a
109
10a
10a
Index of epochs
Index of epochs
Figure 10: Metrics in each epoch.
21


Reviews:
[{"review_id": "zlWv9I_dWjH", "reviewer": "Reviewer_YZaF", "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": "Strength:\n\nThe summary of related work is good and clear. The authors provide theoretically analysis which can be verified by their experiments.\n\nWeakness&Advice:\n\n1. Need citations after “the phenomenon of ‘neighbor explosion’ ”.\n\n2. What is the running time of your method compared to the existing layer-wise sampling methods and baseline methods?\n\n3. What is the regression result of your proposed sampling method with regard to $H^{(l)}W^{(l)}$\n\n4. The visualization in Figure 3 needs to be improved. The font size is too small and the curves are messy.", "summary_of_the_paper": "The authors propose remedies to address sub-optimal sampling probabilities and the approximation bias induced by sampling without replacement  issues in layer-wise sampling methods of GNNs.", "summary_of_the_review": "The novelty and difference with existing works need to be emphasized. I'll consider raise my score if the authors can address my concerns properly.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "gG47PkpwLLU", "reviewer": "Reviewer_cNek", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n\n(1) This paper is the first to address the issue of strong assumption, which induces a sub-optimal solution.\n\n(2) Overall, the paper is well written. In particular, the Notations and Preliminaries section is well discussed. \n\n(3) This paper provides comprehensive experiments to show the effectiveness of the proposed learning schemes. \n\n**Weakness**\n\n(1) The time complexity is an important issue of sampling schemes of graph neural networks. However, there is no empirical study of the efficiency of the proposed method.\n\n(2) What's the main intuition behind the sampling probabilities in Equation (3)?\n\n", "summary_of_the_paper": "This paper revisits layer-wise sampling methods of graph neural networks by addressing issues such as sub-optimal sampling probabilities and the approximation bias due to the usage of sampling without replacement. This paper also presents a new metric to evaluate the performance of the sampling strategy. Through comprehensive experiments, the authors validate the effectiveness of their proposed methods.", "summary_of_the_review": "Overall, I vote for accepting. The paper well presents their proposed method with motivation.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Q8s3p80WP0y", "reviewer": "Reviewer_xS1Y", "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": "## Strengths:\nOverall, the presentation of this paper is clear. The experiments on the large-scale dataset look comprehensive.\n\n## Weaknesses:\n### 1. The theoretical contribution is limited.\nThis paper proposes a  sampling probability construction that abandons the hidden embedding matrix $H$ and the parameter matrix $W$. The core theoretical contribution is to prove that such construction has a better variance than that of `LADIES`. However, this result is weak:\n- Limited scope: Lemma 1 only prove the new sampling probability is better than that of `LADIES`. The superiority of new sampling probability over the other layer-wise sampling method, such as FastGCN and AS-GCN, is still unclear. It’s hard to say the new sampling probability is superior to the other layer-wise sampling methods from the theoretical perspective.\n- Strong assumption: To complete this proof, the authors give a very strong assumption (Assumption 1) without any justification of the existence and rationality.  There is no in-depth discussion about why and when this assumption is held in practice. For instance, Since the assumption ($C_1/C_2^2 \\leq 1$) is highly related to $HW$,  does this assumption still hold during the training process? Therefore, such a strong assumption makes Lemma  1 impractical and its theoretical value to the real application is limited.\n\n\n### 2. The experimental results are weak.\n- The important layer-wise baseline `ASGCN` is missing.\n\n- On Reddit dataset, the results of several baselines are significantly lower than the results in the existing literature. For example, the original F1-score of `GraphSAINT` is  0.966, while in this paper, the F1-score is only 0.8947. I guess this inconsistency may due to the different data splitting. However, the author doesn’t give the details of the data splitting setting, nor gives the reason why does not use the public splitting.\n\n-  As shown in Table 2, this paper only applies the new sampling probability and debiasing method to `LADIES` and observes an improvement. However, even with such a new sampling probability and debiasing approach, the performance is still worse than the other baselines.  Additionally, in Figure 3, the curve of  `LADIES+flat+debiased` is lower than that of other baselines. It’s hard to say the new method is better than that of other methods.\n\n-  There is no time comparison,  especially the sampling time comparison,  across different methods. Since the debiasing operation may introduce the additional computation overhead, I’m curious about such overhead in practice.\n\n\n### 3. Minor issue\n- In Figure 1, why `FastGCN` achieves a better approximation on `ogbn-proteins` than `LADIES`?\n- In my understanding, the sampling probability and sampling method are two core parts of a layer-wise sampling method. Therefore, it is improper to treat the new approach as the extension of `LADIES` and use the notation `+flat+debiased` to represent the new approach.\n\n## Reference:\n[`FastGCN`] FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling\n\n[`ASGCN`] Adaptive Sampling Towards Fast Graph Representation\n\n[`LADIES`] Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks\n\n[`GraphSAINT`] GraphSAINT: Graph Sampling Based Inductive Learning Method\n", "summary_of_the_paper": "This paper introduced a new layer-wise sampling probability as well as a new debiasing sampling algorithm to obtain a better approximation accuracy.", "summary_of_the_review": "Overall, I think that this paper is not ready to be accepted. The details are elaborated in main review.", "strength_and_weaknesses": "", "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": "0bwEBaHLv3K", "reviewer": "Reviewer_Rhqb", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Highlights:\n- Paper proposes uniform distribution over nodes in the batch when training\n  - Looks at the empirical Frobenius norm (matrix approximation error) of the difference between a non-sampling and sampling batch for the first layer outputs. Empirical results show a reduction when using uniform distribution.\n  - Applies regression analysis between the $\\ell_2$ norm of one row $i$ in $\\boldsymbol{H}^{(l)}\\boldsymbol{W}^{(l)}$ and corresponding column $i$ in $\\boldsymbol{P}$ for different layers $l$. Empirical observation of instability and potential negative correlation demonstrates that the LADIES assumption of $||(HW)_{[i]}|| \\propto ||P^{[i]}||$ is violated.\n  - Theoretical analysis is adapted from LADIES (Zou et al. 2019) result. Assumption here is when the assumption in LADIES is not met ( $||\\boldsymbol{H}\\boldsymbol{W}_{(i)}|| \\not\\propto$ corresponding $\\ell_2$ norm of column $(\\boldsymbol{Q}\\boldsymbol{P})^{(i)}$), then the proposed method will work well. \n\n- Paper proposes algorithm to reduce bias\n  - Provides analysis of non-uniform sampling without replacement in FastGCN and LADIES\n  - Gives simple recursive weighted average adjustment to sampling without replacement and runtime complexity\n\nStrength:\n- Empirical observations and analyses are interesting\n- Results show improvement in prediction accuracy\n\nWeakness:\n- Theoretical analysis needs more rigor\n- Analysis and comments as it relates to network structure would be helpful\n- Dataset dependent and limited\n- Incremental improvement to LADIES\n\nMisc:\n\n- Section 4.1: second paragraph, second line, \"improves\"\n- Section 4.4: extra $||$ in line 4\n- The way the citations are applied can be improved (Section 1: first paragraph, first sentence)\n\n", "summary_of_the_paper": "This paper studies existing sampling schemes employed in training graph neural network architectures (e.g., FastGCN [Chen et al.] and LADIES [Zon et al.]) that are improvements to graph convolutional networks (GCN) [Kipf & Welling 2017] from a matrix approximation perspective (looking a Frobenius norm).  The paper focuses on layer-wise sampling (cf. node and subgraph sampling) and observes that there are two drawbacks in common practice layer-wise sampling. First drawback is current probabilities (probability distributions) used for sampling are sub-optimal. The reason the paper gives is that a core assumption made by certain GCN schemes such as FastGCN and LADIES do not hold in datasets such as Reddit and OGB. Second drawback is the implementations of these schemes slightly deviate from their respective theoretical results. The implementations use sampling without replacement, and thus introduces bias.  To this, the paper presents new sampling probabilities (uniform proposal distribution), and an algorithm to reduce the bias. With these adjustments, training of GCN converges faster and potentially leads to higher prediction accuracy (for node prediction). Theoretical analysis is presented and experiments are conducted on common benchmarks (Reddit, ogbn-{arxiv,proteins,products,mag}).\n", "summary_of_the_review": "Although the paper presents interesting empirical observations and analysis, mainly, it is dataset centric. The theoretical justification of uniform distribution is weak -- again, using uniform distribution comes down to data dependency.\n", "strength_and_weaknesses": "", "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": {}}]

Author rebuttal:

Meta-review: The reviewers think the proposed method is well motivated and interesting. However, the novelty needs to be improved. At the moment, the paper seems to be a minor improvement over existing works.
Decision: Reject