IGLU: Efficient GCN Training via Lazy Updates
Authors: S Deepak Narayanan
Aditya Sinha
Prateek Jain
Purushottam Kar
SUNDARARAJAN SELLAMANICKAM
Venue: ICLR 2022 Poster (2022)
Keywords: Graph convolutional networks
Graph neural networks
Optimization
Lazy updates

Abstract: Training multi-layer Graph Convolution Networks (GCN) using standard SGD techniques scales poorly as each descent step ends up updating node embeddings for a large portion of the graph. Recent attempts to remedy this sub-sample the graph that reduces compute but introduce additional variance and may offer suboptimal performance. This paper develops the IGLU method that caches intermediate computations at various GCN layers thus enabling lazy updates that significantly reduce the compute cost of descent. IGLU introduces bounded bias into the gradients but nevertheless converges to a first-order saddle point under standard assumptions such as objective smoothness. Benchmark experiments show that IGLU offers up to 1.2% better accuracy despite requiring up to 88% less compute.

Published as a conference paper at ICLR 2022
IGLU: EFFICIENT GCN TRAINING VIA LAZY UP- DATES
S Deepak Narayanan" & Aditya Sinha
Prateek Jain
Microsoft Research India
Microsoft Research India
[sdeepaknarayanani adi aaityaasi nha28 @gma com
p ja ininng n@goog 1
Purushottam Kar
Sundararajan Sellamanickam
IIT Kanpur & Microsoft Research India purushot@cse. witk.
Microsoft Research India
esrajan@miccoom com
ABSTRACT
Training multi-layer Graph Convolution Networks (GCN) using standard SGD techniques scales poorly each descent step ends up updating node embeddings for a large portion of the graph. Recent attempls to remedy this sub-sample the graph that reduce compute but introduce additional variance and may offer suboptimal performance. This paper develops the IGLU method that caches intermediate computations various GCN layers thus enabling lazy updates that significantly reduce the compute cost of descent. IGLU introduces bounded bias into the gradients but nevertheless converges to first-order saddle point under standard assumptions such as objective smoothness. Benchmark experiments show that IGLU offers up to 1.2% better accuracy despite requiring up 88% less compute.
INTRODUCTION
The Graph Convolution Network (GCN) model an effective graph representation learning technique. Its ability to exploit network topology offers superior performance in several applications such as node classification (Kipf& & Welling 2017). recommendation systems (Ying et al. 2020) and program repair (Yasunaga & Liang 2020). However, training multi-layer GCNs on large and dense graphs remains challenging due to the very aggregation operation that enables GCNs to adapt to graph topology- -a node's output layer embedding depends on embeddings of its neighbors in the previous layer which recursively depend on embeddings of their neighbors in the previous layer, and so on. Even in GCNs with 2-3 layers, this prompts back propagation on loss terms for a small mini-batch of nodes to update a large multi-hop neighborhood causing mini-batch SGD techniques to scale poorly,
Efforts to overcome this problem try to limit the number of nodes that receive updates as a result of mack-propagation step ShepChhing et al. (2019); Hamilton al, (2017); Zeng et al. (2020). This is done either by sub-sampling the neighborhood or clustering (it important to note the distinction between nodes sampled to create mini-bated and neighborhood sampling done limit the neighborhood of the mini-batch that receives updates). Variance reduction techniques Chen et al. (2018a) attempt to reduce the additional variance introduced by neighborhood sampling. However, these techniques often require heavy subsampling in large graphs resulting in poor accuracy due to insufficient aggregation. They also do not guarantee unbiased learning rigorous convergence guarantees. See Section 2 for a more detailed discussion on the state-of-the-an in GCN training.
This paper presents IGLU, an efficient technique for training GCNs based on lazy updates. An analysis of the gradient structure in GCNs reveals the most expensive component of the back-propagation step initiated node be (re- ecomptation of forward-pass embeddings for its vast multi-hop neighborhood. Based on this observation, IGLU performs significantly reduced complexity using intermediate computations that are cached regular intervals.
Our Contributions:
with
Authors contributed equally
Now at ETH Zurich
Now at Google Research India

---

Published as a conference paper at ICLR 2022
This completely avoids neighborhood sampling and is stark departure from the state-of of-the-art. IGLU is architecture-agnosee and can be readily implemented on a wide range of GCN architectures. Avoiding neighborhood sampling also allows IGLÜ to completely avoid variance artifacts and offer provable convergence to a first-order stationary point under standard assumptions. In experiments, IGLU offered superior accuracies and accelerated convergence range of benchmark datasets.
2
RELATED WORKS
2014 Defferrard et al. 2016 Kipf& & Welling 2017) introduced the GCN architecture for transductive learning on graphs. Later works extended to inductive settings and explored architectural variants such as the GIN (Xu et al.
(Bruna et al.
2019). Much effort has focused on speeding-up GCN training.
Sampling Based Approaches:
The neighborkood sampling strategy e.g. GraphSAGE (Hamilton) et al.] (017) limits compute by restricting back prooppropgattion updates to a sub-sampled neighborhood of a node. Layer sampling strategies such as FastGCN (Chen et al., 20186), LADIES (oou et al., 2019) and ASGCN (Huang et al. 2018) instead sample nodes at each GCN layer using importance sampling to reduce variance and improve connectivity among sampled nodes. FastGCN uses the same sampling distribution for all layers and struggles to maintain connectivity unless large batch-sizes are used. LADIES uses a per-layer distribution conditioned on nodes sampled for the succeeding layer. ASGCN uses linear model jointly infer node importance weights. Recent works such as Cluster-GCN (Chiang et al., 2019) and GraphSAINT (Zeng et al.) 2020) propose subgraph sampling creating mini-batches out of subgraphs and restricting Sack-propagation to nodes within the subgraph. To avoid losing too many edges, large mini-batch sizes are used. Cluster-GCN, performs graph clustering and chooses multiple clusters per mini-batch (reinserting any edges cutting across clusters in mini- batch) whereas GraphSAINT samples large subgraphs directly using random walks.
Bias and Variance: Sampling techniques introduce bias as non-linear activations in the GCN architecture make it difficult to offer unbiased estimates of the loss function. Zeng et al. (2020) offer unbiased estimates if ooneaiieasss are discarded. Sampling techniques also face increased variance for which variance-reduction techniques have been proposed such as VR-GCN (Chen et al., 2018a), MVS-GNV (Cong et al., 2020) and AS-GCN (Huang et al. 2018). VR-GCN samples nodes at each layer whose embeddings are updated and uses stale embeddings for the rest, offering variance elimination in the limit under suitable conditions. MVS-GN) handles variance due to mini-batch The Bandit Sampler (Liu et al. 2020) formulates variance reduction as an adversarial bandit problem.
creation by performing importance weighted sampling to construct
Other Approaches: Recent approaches decouple propagation from prediction pre- pre-processing step e.g. PPRGo (Bojchevski et al. 2020), APPNP (Klicpera et al. 2019)) and SIGN (Frasca et al. 2020). APPNP makes use of the relationship between the GCNs and PageRank to construct improved propagation schemes via personalized PageRank. PPRGo extends APPNP by approximating the dense propagation matrix via the push-flow algorithm. SIGN proposes inception style pre-computation of graph convolutional filters to speed up training and inference. GNNAutoScale (Fey et al. (021) builds on VR-GCN and makes use of historical embeddings for scaling GNN training large graphs
IGLU in Context of Related Work: IGLU avoids neighborhood sampling entirely and instead speeds-up learning using stale computations. Intermediate computations are cached and lazily updated at regular intervals e.g. once per epoch. We note that IGLU's caching is distinct and much more aggressive (e-g. lasting an entire epoch) than the internal caching performed by popular frameworks such TensorFlow and PyTorch (where caches last only a single iteration). Refreshing these caches bulk offers IGLU economies of scale. IGLU incurs no sampling variance but incurs bias due to the use of stale computations. Fortunately, this bias is provably bounded, and can be made arbitrarily small by adjusting the step length and refresh frequency of the stale computations.
3 IGLU: EFFICIENT GCN TRAINING VIA LAZY UPDATES
Problem Statement: Consider the problem of learning GCN architecture on an undirected graph G(V,E) with each of the N nodes endowed with an initial feature vector x E IRdo E V. X e R denotes the matrix of these initial features stacked together. (ii)) C V denotes the set of neighbors of node i. A denotes the (normalized) adjacency matrix of the graph. A multi-layer GCN
2

---

Published as a conference paper at ICLR 2022
architecture uses parameterized function at each layer to construct node's embedding for the next layer using embeddings of that node as well as those of its neighbors. Specifically
x 1(x .j (()) F*),
where E* denotes the parameters of k-th layer. For example, classical GCN layer is given by
x =a Σ AA JEE
where F. is simply the matrix W E RRds-1xds and dz is the embedding dimensionality at the hth layer. IGLU supports more involved architectures including residual connections, virtual nodes, layer normalization, batch normalization, etc (see Appendix A.5). We will use E* to collectively refer to all parameters of the hthh layer e.g. offset and scale parameters in a layer norm operation, etc. X E Raxd= will denote the matrix of hth layer embeddings stacked together, giving us the handy shorthand X f(x*=1, ). Given a K K-layer GCN and multi-label/muule class task with C labels/classes, a fully-connected layer WK+1 R and activation functions such as sigmoid or softmax are used to get predictions that are fed into the task loss. IGLU does not require the task loss to decompose over the classes. The convergence proofs only require a smooth training objective.
Neighborhood Explosion: To understand the reasons behind neighborhood explosion and the high cost of mini-batch based SGD training, consider a toy univariate regression problem with unidimensional features and 2-yeyer GCN with sigmoidal activation i.e. K = 2 and C 1 1= do
d1 = dz. This GCN is parameterized by w w², w E IR and offers the output i/s - w o (z7) where
=² = Ejev Ayjux) E TR. turn, we have xr) = a (=/) where 2 = EE'ev Agp E R and
J. R are the initial features of the nodes. Given task loss l R R RR e.g. least squares,
denoting E f' (U) vi) gives
al( V1) Owl
0y.
027
Σ Anju Oxy Dwl
dz3 Ow
jEV
E. . wo o2?))
Σ Anjwadd( jeV
Aspag j'EV
The nesting of the summations is conspicuous and indicates the neighborhood explosion: when seeking gradients in a K-layer GCN on a graph with average degree m, up to an m neighborhood of node may be involved in the baok-propagation update initiated that node. Note that the above expression involves terms such as o (=(2)) (z²))) Since the values of =?, etc change whenever the model i.e. {w², w², w receives updates, for a fresh mini-batch of nodes, terms such as o' d'(22), (z need to be computed afresh if the gradient is to be computed exactly. Performing these computations amounts to doing forward pass operations that frequently involve large neighborhood of the nodes of the mini-batch. Sampling strategies try to limit this cost by directly restricting the neighborhood over which such forward passes are computed. However, this introduces both bias and variance into the gradient updates as discussed in Section 2 IGLU instead lazily updates various incomplete gradient (defined below) and node embedding terms that participate in the gradient expression. This completely eliminates sampling variance but introduces a bias due to the use of stale terms. However, this bias provably bounded and can be made arbitrarily small by adjusting the step length and frequency of refreshing these terms.
Lazy Updates for GCN Training: Consider arbitrary GCN architecture with the following structure: for some parameterized layer functions we have X = f(x= where E* denotes the collection of all parameters of the hth layer e.g. weight matrices, offset and scale parameters used in layer norm operations, etc. X E R denotes the matrix of htth layer embeddings stacked together and X E Nxoo are the initial features. For a K K-layer GCN task with C' labels/classes, a fully-connected layer W +1 E dd xC is used to offer predictions y, = -WWK+1)Txx x E RCC We use the shorthand Y E N to denote the matrix where the predicted outputs ÿ; for all the nodes are stacked. We assume a task loss function É R x RC x R., and use the abbreviation E, {(i: y.). The loss function need not decompose over the classes and can thus be assumed to include activations such as softmax that are applied over the predictions ý;, Let L = Σiev le denote the training objective. The convergence proofs assume that L is smooth.
mulli-label/mullticlaaa
3

---

Published as a conference paper at ICLR 2022
X
att1
X
Layer Norm
ReLU
x
at
Graph Conv
R
Dropout
at11
X
KEU
Niighoushand Sampling Layer Sampling
Sakgrrah-Samplee
X = / fF*),, at= a(altauutt
GraphSAINT
(a)
(b)
(c)
Figure I: Fig [ ()) highlights the distinction between existing sampling-base based approaches that may introduce bias and variance. IGLU completely sidesteps these issues and is able to execute GCN back poopppropgattion steps on the full graph owing its use of lazy updates which offer no sampling variance and provably bounded hias. [b) summarizes the quantities useful for IGLU's updates. IGLU is architecture-agnosti and be readily used with wide range of architectures. Fig [ gives an example layer architecture used by GraphSAINT.
Motivation: We define the the loss derivative matrix G = [gtel E RNNC with Jic == 86_, As the proof of Lemma
Bgic
[ (see Appendix Ch shows, the loss derivative with respect to parameters E at Σ3 E (Eiev Ece(c] 9ic
any layer has the form
BC TE
Disc ax
Note that the partial UE
i2
8x derivatives Dg can be computed for any node using only embeddings of its neighbors in the (A- 11 layer i.e. x thus avoiding any neighborhood explosion. This means that neighborhood explosion must be happening while computing the terms encapsulated in the round brackets. Let us formally
recognize these terms as incomplete gradients. The notation
aP denotes the partial derivative of aQ R
P w...t Q while keeping R fixed i.e. treated as constant.
Definition 1. For any layer k S K, define its incomplete task gradient to be a =aa E Nxd,
0o = a(G O Y) ox* ip
ΣΣΣ iEV CE
Ojic ox
Jie
iv
The following lemma completely characterizes the loss gradients and also shows that the incomplete gradient terms a k E [K] can be efficiently computed using a recursive formulation that also does not involve any neighborhood explosion.
Lemma 1. The following results hold whenever the task loss L is differentiable:
1. For the final fully-connected layer we have kw = ( G as well as for any k E [K]
oc
ac a(a"axt) ag aa = -iev Exe o
ox
and any parameter E in the t layer, DE
agk
2. For the final layer, we have K = G(WK+I)T as well as for any h < K, we have ax!#1
k
Bia +ox
i.e. at Eiev Edeti
k+1,
8X*
axt 1p
8x
Lemma establishes a recursive definition of the incomplete gradients using terms such as axx that
concern just single layer. Thus, computing a² for any E [K] does not involve any neighborhood explosion since only the immediate neighbors of a node need be consulted. Lemma] I also shows that if a are computed and frozen, the loss derivatives 8C only involve additional computation of DE
8x terms such as "g which yet again involve single layer and do not cause neighborhood explosion. This motivates lazy updates a x values in order accelerate back-propagation. However, performing lazy updates to both & x offers suboptimal performance. Hence IGLU adopts two variants described in Algorithms and 2 The backprop varian keeps embeddings X stale for
"The backprop variant is named so since updates model parameters in the order back- propppropggttion would have updated them i.c. W followed by F2K F,K F .... whereas the inverted variant performs updates in the reverse order i.c. starting from F!! F²² all the way W+1
4

---

Published as a conference paper at ICLR 2022
entire epoch but performs eager updates to a². The inverted variant the other hand keeps the incomplete gradients a² stale for an entire epoch but performs eager updates to X
Algorithm 1 IGLU: backprop order
Algorithm IGLU: inverted order
Input: GCN G, initial features X task loss
Input: GCN G. initial features X task loss L
1: Initialize model parameters E*, k E [K], W
1: Initialize model parameters E* E [K], W
2: while not converged do
2: Do an initial forward pass to compute X [K]
3: Do forward pass compute X for all l
3: while not converged
[K] as well as Y
4: Compute Y, G and a" for all [K] using
4: Compute G then SWX+T using Lemma and update W <- W 7/ aw
Lemma (2)
5:
for l: = 1... do D2
Compute a using G, Wx+1 Lemmaa 1 (2)
6:
Compute DE using a ,x Lemma (1)
6:
for k K...
7:
ac Update b²t + E't 11 ag
7:
Compute agE using a X Lemma (I)
82
8:
Update X t- s(x k-1--, E²)
8:
Update 1t + 1b
ac
9:
end for
ag
10: Compute aw using Lemma (1) and use
9: Update at using a ++1 using Lemma
update WK+1 WK+1 ? "WW 11: end while
10: end for
end while
SGD Implementation: Update steps in the algorithms (steps 4, 8 in Algorithm I and steps 7, 10 in Algorithm 2 are described as a single gradient step over the entire graph to simplify exposition - in practice, these steps implemented using mini-batch SGD. A mini-batch of nodes is sampled and task gradients are computed w.r.t Ls Eies & alone instead of C.
Contribution: As noted in Section 2 IGLU uses caching in a manner fundamentally different from frameworks such as PyTorch TensorFlow which short-lived caches and compute exact gradients unlike IGLU that computes gradients faster but with bounded bias. Moreover, unlike techniques such as VR-GCN that cache only node embeddings. IGLU instead offers two variants and the variant that uses inverted order of updates (A (Algorithm 2 and caches incomplete gradients usually outperforms the backprop variant of IGLU (Algorithm I that caches node embeddings.
Theoretical Analysis: Conditioned on the stale parameters (either a or X depending on which variant being executed), the gradients used by IGLU to perform model updates (steps 4, 8 in Algorithm aad steps 7, 10 in Algorithm 2 do not have any sampling bias. However, the staleness itself training bias. However, by controlling the step length and the frequency with which the stale parameters are updated, this bias can be provably controlled resulting in guaranteed convergence to first-order stationary point. The detailed statement and proof are presented in Appendix
Theorem (IGLU Convergence (Informal)). Suppose the task objective has (1)-Lipschitz gradients and IGLU is executed with small enough step lengths for model updates (steps 4, 8 in Algorithm 7 and steps 7, 10 in Algorithm D then within iterations, IGLU ensures:
| 0 (1/T²) if update steps are carried out on the entire graph a full-batch
2.
VCL < 0 11/ (I/VT) if update steps carried out using mini-batch SGD.
This result holds under minimal assumptions of objective smoothness and boundedness that are standard Chen et al. (201 8a): Cong et al. (2020), yet offers convergence rates comparable to those offered by standard batc- SGD. However, whereas works such as (Chen et al. 2018a) assume bounds on the sup-norm i.c. Loo norm of the gradients, Theorem only requires an Le norm bound. Note that objective smoothness requires the architecture to use smooth activation functions. However, IGLU offers similar performance whether using non-smooth activations e.g. ReLU or smooth ones e.g. GELU (see Appendix [B.7) as is also observed by other works (Hendrycks & Gimpel 2020).
4 EMPIRICAL EVALUATION
IGLU compared to state-of-the (SOTA) baselines several node classification benchmarks in terms of test accuracy and convergence rate. The inverted order of updates was used for IGLU as was found to offer superior performance in ablation studies.
5

---

Published as a conference paper at ICLR 2022
Datasets and Tasks:
The following five benchmark tasks were used:
(I) Reddit (Hamilton et al. : predicting the communities to which different posts belong,
(2) PPI-Large (Hamilton et al. 2017): classifying protein functions in biological protein protein
interaction graphs,
(3) Flickr (Zeng al. 2020): image categorization based descriptions and other properties,
(4) OGBN-Arxiv (Hu et al. 22200] predicting paper-paper associations, and
(5) OGBN-Proteins (Hu al. (200): categorizing meaningful associations between proteins.
splits and metrics were used in a manner consistent with the original release of the datasets: specifically ROC-AUC was used for
and micro-F1 for all other datasets. Dataset descriptions and statistics are presented in Appendix B The graphs in these tasks varied significantly in terms of size (from 56K nodes PPI-Large to 232K nodes in Reddit), density (from average degree 13 in OGBN-Arxiv to 597 in OGBN-Proteins) and number of edges (from 800K to 39 Million). They require diverse information to be captured and a variety of multi-label and multi-class node classification problems to be solved thus offering extensive evaluation.
Baselines: IGLU was compared to state-of-the-art algorithms, namely- GCN (Kipf & Welling 2017 J.
GraphSAGE (Hamilton et al. 2017). VR-GCN (Chen et al., (018a), Cluster-GCh (Chiang et al. 2019) and GraphSAINT (Zeng et al. 2020) (using the Random Walk Sampler which was reported by the authors to have the best performance). The mini-batched implementation of GCN provided by GraphSAGE authors was used since the implementation released by (Kipf & Welling 2017) gave run
time errois on all datasets. GraphSAGE and VRGCN address the neighborhood explosion problem by sampling neighborhood subsets, whereas ClusterGCN and GraphSAINT are subgraph sampling techniques. Thus, our baselines include neighbor sampling, layer-wise sampling, subgraph sampling and no- somaanl methods. We recall that IGLU does not require any node/subgraph sampling. IGLU was implemented in TensorFlow and compared with TensorFlow implementations of the baselines released by the authors. Due to lack of space, comparisons with the following additional baselines is provided in Appendix B.2 LADIES (Zou et al. 2019), L2-GCN (You et al. 2020). AS-GCN (Huang et al. 2018). MVS-GNN (Cong et al.) 2020). FastGCN (Chen et al. 2018b), SIGN (Frasca et al. 2020 PPRGo (Bojchevski et al. 2020) and Bandit Sampler (Liu et al. 2020
Architecture: We note that all baseline methods propose specific network architecture along with their proposed training strategy. These architectures augment the standard GCN architecture (Kipf & Welling, 2017) e.g. using multiple non-linear layers within each GCN layer, normalization and concatenation layers, all of which can help improve performance. IGLU being architecture- agnostic can be readily used with all these architectures. However, for the experiments, the network architectures proposed by VR-GCN and GraphSAINT was used with IGLU owing to their consistent performance across datasets as demonstrated by (Chen et al., 2018 Zeng et al. 2020). Both architectures were considered and results for the best architecture are reported for each dataset.
Detailed Setup. The supervised inductive learning setting was considered for all five datasets as it is more general than the transductive setting that assumes availability of the entire graph during training. The inductive setting also aligns with real-world applications where graphs can grow over time (Hamilton et al.] 2017). Experiments on PPI-Large, Reddit and Flickr used 2 Layer GCNs for all methods whereas OGBN-Proteins and OGBN-Arxin used 3 Layer GCNs for all methods as prescribed in the original benchmark (Hu et al. 2020). Further details are provided in Appendix A.
Model Selection and Hyperparameter Tuning. Model selection was done for all methods based on their validation set performance. Each experiment was run five times with mean and standard deviation in test performance reported in Tuble[alooe with training times. Although the embedding dimension varies across datasets, they same for all methods for any dataset. For IGLU, GraphSAGE and VR-GCN, an exhaustive grid search was done over general hyperparameters such as batch size, learning rate and dropout rate (Srivastava al. 2014). In addition, method-specific hyperparameter sweeps were also carried out that are detailed in Appendix A.4
4.1 RESULTS
For IGLU, the VR-GCN architecture performed better for Reddit and OGBN-Arxiv datasets while the GraphSAINT architecture performed better the remaining three datasets. All baselines were extensively tuned on the datasets and their performance reported in their respective publications was either replicated closely or else improved. Test accuracies reported in Table and convergence

---

Published as a conference paper at ICLR 2022
Table Accuracy of IGLU compared SOTA algorithms. The metric is ROC-AUC for Proteins and Micro-F1 F1 for the others. IGLU is the only method with accuracy within 0.2% of the best accuracy on each dataset with significant speedups in training across datasets. On PaI-Large, IGLU is ~ 8x faster than VR-GCN, the most accurate baseline. * denotes speedup in initial convergence based on high validation score of 0.955. denotes no absolute gain. denotes runtime error.
Algorithm
PPI-Large
Reddit
Flickr
Proteins
Arxiv
GCN
0.614 + 0.004
0.931 + 0.001
0.493 + 0.002
0.615 + 0.004
0.657 + 0.002
GraphSAGE
0.736 + 0.006
0.954 + 0.002
0.501 = 0.013
0.759 + 0.008
0.682 + 0.002
VR-GCN
0,975 + 0.007
0.964 + 0.001
0.483 + 0.002
0.752 + 0.002
0.701 + 0.006
Cluster-GCN
0.899 + 0.004
0.962 + 0.004
0.481 + 0.005
I|
0.706 + 0.004
GraphSAINT
0.956 + 0.003
0.966 + 0.003
0.510 + 0.001
0.764 + 0.009
0.712 + 0.006
IGLU
0.987 1 0.004
0.964 1 0.001
0.515 1 0.001
0.784 1 0.004
0.718 1 0.001
Abs. Gain
0.012
0.005
0.020
0.006
% Speedup
88.12
8.1"
44.74
11.05
13.94
PPI-Large
Reddit
Flickr
1.0
0.9
0.96
0.50
Micro-F1
0.7
0.8
Micro-F1
0.94
Micro-F1
0.45
0.6
0.40
0.5
20
60
80
0.88
20
0.35
Wall Clock Timels)
Wall Clock Time(s)
Wall Clock Timels)
OGB OGB N-Proteins
0.75
OGBN-Arxiv
0.70
0.8
GCN
GraphSAGE
ROC AUC
0.7
Micro-F
0.60
VRGEN
GraphSAINT
0.55
ClusterGCN
0.6
0.50
IGLU
0.45
0.5
20
40
60
80
100
0.40
10
20
30
40
Wall Clock Timels)
Wall Clock Time(s)
Figure 2: Wall Clock Time vs Validation Accuracy on different datasets for various methods.
IGLU offers significant improvements in convergence rate over baselines across diverse datasets.
plots are shown in Figure? 2 Additionally, I reports the absolute accuracy gain of IGLU over the best baseline. The % speedup offered by IGLU is computed as follows: let the highest validation score obtained by the best baseline be v1 and Ł be the time taken to reach that score. Let the time taken by IGLU to reach U1 be 1z. Then,
4 11-6, 100
% Speedup
The wall clock training time in Figure is strictly the optimization time for each method and excludes method -ethoo--peecific overheads such as precpeccsss,ng sampling and sub-graph creation that other baselines incur. This is actually a disadvantage to IGI.U since its overheads are much smaller. The various time and memory overheads incurred by all methods are summarized in Appendix A.2 and memory requirements for IGLU are discussed in Appendix A.3
Performance on Test Set and Speedup Obtained: Table I establishes that IGLU significantly outperforms the baselines on PPI-Large. Flickr, OGBN-Proteins and OGBN-Arxiv and is competitive with best baselines on Reddit. On PPI-Large, IGLU improves accuracy upon the best baseline (VRGCN) by over 1.2% while providing speedups of upto 88%. i.e., IGLU is about 8x faster to train than VR-GCN. On OGBN-Prrotcin IGLU improves accuracy upon the best baseline (GraphSAINT) by over 2.6% while providing speedup of 11%. On Flickr, IGLU offers 0.98% improvement in
7

---

Published as a conference paper at ICLR 2022
IGLU Validation ROC AUC vs Epoch: OGBN-Proteins
IGLU Validation Micro-F1 Epoch: Reddlt
0.85
0.80
0.90
0.75
0.70
0.65
0.80
0.40
0.75
0.55
Inverted
Inverted Backprop
Barkprop
50
75
1.00
125
150
175
200
10
15
20
25
Epoch
Epoch
(a)
(b)
Figure 3: Effect of backprop and inverted order of updates in IGLU on Reddit and OGBN--Proeei datasets. The inverted order of updates offers more stability and faster convergence. It notable that techniques such as VR-GCN use stale node embeddings that correspond to the backprop variant.
aceuracy while simultaneously offering upto 45% speedup over the previous state-of-ther method GraphSAINT. Similarly on Arxiv, IGLU provides 0.84% accuracy improvement over the best baseline GraphSAINT while offering nearly 14% speedup. On Reddit, an 8.1% speedup was observed in convergence to a high validation score of 0.955 while the final performance is within standard Proteins and OGBN-ArA: datasets were originally
deviation of the best baseline. The benchmarked in the transductive setting, with the entire graph information made available during training. However, we consider the more challenging inductive setting yet IGLU outperforms the best transductive baseline by over 0.7% for Proteins while matching the best transductive baseline for Arxiv (Hu et al. 2020p. It is important to note that OGBN-Proteing is an atypical dataset because the graph highly dense. Because of this, basclines such as ClusterGCN and GraphS that drop lot of edges while creating subgraphs show deterioration in performance. ClusterGCN encounters into a runtime error on this dataset (denoted by in the table), while GraphSAINT requires a very large subgraph size to achieve reasonable performance.
Convergence Analysis: Figure 2 shows that IGLU converges faster to higher validation score than other baselines. For PPI-Large, while Cluster-GCN and VR-GCN show promising convergence in the initial stages of training. they stagnate a much lower validation score the end whereas IGL.U able to improve consistently and converge much higher validation score. For Reddit, IGLU's final validation score marginally lower than GraphS AINT but IGLU offers rapid convergence in the early stages of training. For OGBN-Protein Flickr and OGBN-Arxiv, IGLU demonstrates substantial improvement in both convergence and the final performance on the test set.
4.2 ABLATION STUDIES
Effeet of the Order of Updates. IGLU offers the flexibility using either the backprop order of updates the inverted order of updates as mentioned in Section 3 Ablations were performed on the Reddit and OGBN-Proteiin datasets to analyse the effect of the different orders of updates. Figure B offers epoch-wise convergence for the same and shows that the inverted order of updates offers faster and more stable convergence in the early stages of training although both variants eventually converge similar validation scores. It is notable that keeping node embeddings stale (backprop order) offered inferior performance since techniques such as VR-GCN (Chen et al.) |01 Sa) that also keep node embeddings stale. IGLU offers the superior alternative of keeping incomplete gradients stale instead.
Analysis of Degrees of Staleness. The effect of frequency of updates to the incomplete gradients (a*) on the performance and convergence of IGLU was analyzed. This ablation was conducted keeping all the other hyperparameters fixed. In the default setting, a values were updated only once per epoch (referred to as frequency 1). Two other update schemes were also considered: a) update the a values every two epochs (referred to frequency 0.5), and b) update the k values twice within an epoch (referred to as frequency 2). To clarify, a values are the most fresh with update frequency and most stale with update frequency 0.5. This ablation study performed on the PPI-Large dataset and each variant was trained for 200 epochs. (able(]summarr and Figure plots the convergence of these variants. Figure 4b shows that PPI-Large, the default
the results doing model selection
8

---

Published as a conference paper at ICLR 2022
IGLU Train
Validation
0.6
Frequeecy-] Frequonccy
0.9
0.5
0.8
0.4
0.7
0.3
0.2
(Debbut) Frequency
0.1
0.4
(a)
(b)
Figure Update frequency vs Accuracy. Experiments conducted on Prr-Large. expected, refreshing the at too frequently or too infrequently affect both performance and convergence.
update frequency I has the best convergence on the validation set, followed by update frequency 0.5. Both update frequency 1 and 0.5 massively outperform update frequency Figure shows that IGLU with update frequency has the lowest training loss but poor validation performance, indicating overfitting to the training dataset. We observe from this ablation that updating embeddings prematurely can cause unstable training resulting in convergence to a suboptimal solution. However, refreshing the at values frequently enough can delay convergence to good solution.
Table 2: Accuracy vs different update frequency on PPI-Large.
Update Frequency
Train Micro-F1
Validation Micro-F1
Test Micro-Fi
0,5
0.947
0.899
0.916
0.970
0.947
0.961
2
0.960
0.708
0.726
Additional Ablations and Experiments: Due to lack of space, the following additional ablations and experiments are described in the appendices: a) Ablation on degrees of staleness for the backprop order of updates in Appendix [B.8] b) Experiments demonstrating IGLU'' scalability deeper net- works and larger datasets Appendices B.3 and (Bespeecccc,lllll Beeeeeeee and c) Experiments demonstrating
IGLU's applicability and architecture-agnostic nature Appendices B.5 and B.6
5 DISCUSSION AND FUTURE WORK
This paper introduced IGLU, novel method for training GCN architectures that uses biased gradients based on cached intermediate computations speed up training significantly. The gradient bias is shown to be provably bounded so overall convergence is still effective (see Theorem IGLUU' performance was validated on several datasets where it significantly outperformed SOTA methods in terms of accuracy and convergence speed. Ablation studies confirmed that IGLU is robust to its few hyperparameters enabling a near-optimal choice. Exploring other possible variants IGLU, in particular reducing variance due to mini-batch SGD, sampling nodes to further speed-up updates, and exploring alternate staleness schedules are interesting future directions. On a theoretical side, would be interesting characterize properties of datasets and loss functions that influence the effect of lazy updates on convergence. Having such property would allow practitioners to decide whether execute IGLU with lazier updates else reduce the amount of staleness. Exploring application- and architecture-specifi variants of IGLU is also an interesting direction.
REPRODUCIBILITY STATEMENT
Efforts have been made to ensure that results reported in this paper reproducible.
Theoretical Clarity: Section 3 discusses the problem setup and preliminaries and describes the proposed algorithm. Detailed proofs are provided in Appendix []due lack of space.

---

Published as a conference paper at ICLR 2022
Experimental Reproducibility: Section and Appendices A and contain information needed to reproduce the empirical results, namely datasets statistics and data source, data pre-pri proccessinnng implementation details for IGLU and the baselines including architectures, hyperparameter search spaces and the best hyperparameters corresponding to the results reported in the paper.
Code Release: An implementation of IGLU can be found at the following URL
https:/ http:///hhuu...oom///eeeaaaaaaaa
ETHICS STATEMENT
This paper presents IGLU, novel technique to train GCN architectures on large graphs that outper- forms state of the art techniques in terms of prediction accuracy and convergence speed. The paper does not explore any sensitive applications and the experiments focus primarily publicly available benchmarks of scientific (e.g. PPI) and bibliographic (e.g. ArXiv) nature do not involve any user studies human experimentation.
ACKNOWLEDGMENTS
The authors are thankful to the reviewers for discussions that helped improve the content and presentation of the paper.
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg. Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: A System for Large-Scale Machine Learning. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16), 2016.
Aleksandar Bojchevski, Johannes Klicpera, Bryan Perazzi, Amol Kapoor, Martin Blais, Benedek Rózemberezki, Michal Lukasik, and Stephan Günnemann. Scaling graph neural networks with approximate pagerank. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining (KDD), 2020.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In Yoshua Bengio and Yann LeCun (eds.), Proceedings of the 2nd International Conference on Learning Representations (ICLR), 2014.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic Training of Graph Convolutional Networks with Vari- ance Reduction. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning (ICML), 2018a.
Jie Chen, Tengfei Ma, and Cao Xiao. FastCCN: Fast Learning with Graph Convolutional Networks via Importance Sampling. In Proceedings of the 6th International Conference on Learning Representations (ICLR), 2018b.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and Deep Graph Convolutional Networks. In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), 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 (KDD), 2020.
10

---

Published as a conference paper at ICLR 2022
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal Neighbourhood Aggregation for Graph Nets. In Proceedings of the 34th Advances in Neural Information Processing Systems (NeurIPS), 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. In Proceedings of the 30th Advances in Neural Information Processing Systems (NIPS), 2016.
Matthias Fey, Jan E. Lenssen, Frank Weichert, and Jure Leskovec. Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning (ICML), 2021.
Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. In International Conference on Machine Learning (ICML) 2020 Workshop on Graph Represenlation Learning and Beyond, 2020.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive Representation Learning Large Graphs. In Proceedings of the 31 Advances in Neural Information Processing Systems (NIPS), 2017.
Dan Hendrycks and Kevin Gimpel. Gaussian Error Linear Units (GELUs), 2020. arXiv:1606.08415 [cs.LG].
Weihua Hu, Matthias Fey, Marinka Zimik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Proceedings of the 34th Advances in Neural Information Processing Systems (NeurIPS), 2020.
Wenbing Huang. Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive Sampling Towards Fast Graph Representation Learning. In Proceedings of the 32nd Advances in Neural Information Processing Systems (NeurIPS), 2018.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference Learning Representations, (ICL.), 2015.
Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks. In Proceedings of the 5th International Conference on Learning Representations (ICLR), 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then Propagate: Graph Neural Networks meet Personalized PageRank. In Proceedings of the 7th International Conference on Learning Representations (ICLR), 2019.
Ziqi Liu, Zhengwei Wu, Zhigiang Zhang. Jun Zhou, Shuang Yang, Le Song, and Yuan Qi. Bandit samplers for training graph neural networks. Proceedings of the 34th Advances in Neural Information Processing Systems (NeurIPS), 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang. Zach De Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, nigh-peeffrmance deep learning library, 2019.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In Proceedings of the 8th International Conference on Learning Representations (ICLR), 2020.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(56), 2014.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph Attention Networks. In Proceedings of the 6th International Conference on Learning Representations (ICLR), 2018.
11

---

Published as a conference paper at ICLR 2022
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Networks? In Proceedings of the 7th International Conference on Learning Representations (ICLR), 2019.
Michihiro Yasunaga and Percy Liang. Graph-based, Self-Supervised Program Repair from Diagnostic Feedback. In Proceedings of the 37th International Conference on Machine Learning (ICML), 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 & Data Mining (KDD), 2020.
Yuning You. Tianlong Chen, Zhangyang Wang, and Yang Shen. L2-GCN: Layer- Wise and Learned Efficient Training of Graph Convolutional Networks. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattem Recognition (CVPR), 2020.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- SAINT: Graph Sampling Based Inductive Learning Method. In Proceedings of the 8th International Conference on Learning Representations (ICLR), 2020.
Difan Zou, Ziniu Hu, Yewen Wang. Song Jiang, Yizhou Sun, and Quanquan Gu. Layer- Importance Sampling for Training Deep and Large Graph Convolutional Networks. In Proceedings of the 33rd Advances in Neural Information Processing Systems (NeurIPS), 2019.
APPENDIX
This appendix is segmented into three key parts.
1. Section A discusses additional implementation details. In particular, method-specific over- heads are discussed in detail and detailed hyper-parameter settings for IGLU and the main baselines reported in Table | are provided. A key outcome of this analysis is that IGLU has the least overheads as compared the other methods. We also provide the methodology for incorporating architectural modifications into IGLJU, provide a detailed comparison with caching based methods and provide a more detailed descriptions of the algorithms mentioned in the main paper.
2. Section B reports dataset statistics, provides comparisons with additional baselines (not included the main paper due to lack of space) and provides experiments on scaling to deeper models and larger graphs as mentioned in Section 4.2 in the main paper. It also provides experiments for the applicability of IGLU across settings and architectures, using smooth activation functions, continued ablation degrees of staleness and optimization on the train set. The key outcome of this discussion is that IGLU scales well to deeper models and larger datasets, and continues to give performance boosts with state-of-the-ar even when compared to these additional baselines. Experimental evidence also demonstrates IGLU's ability to generalize casily to different setting and architecture, perform equivalently with smooth activation functions and achieve lower training losses faster compared to all the baselines across datasets.
3. Section Section[_givee gives detailed proofs of Lemma [and the convergence rates offered by IGLU. It is shown that under standard assumptions such as objective smoothness, IGLU able to offer both the standard rate of convergence common for SGD-style algorithms, as well as fast rate if full-batch GD is performed.
A ADDITIONAL. IMPLEMENTATION DETAILS
We recall from Section that the wall-clock time reported in Figure 2 consists of strictly the optimization time for each method and excludes method-specifee overheads. This was actually disadvantage for IGLU since its overheads are relatively mild. This section demonstrates that other baselines incur much more significant overheads whereas IGLU does not suffer from these large
12

---

Published as a conference paper at ICLR 2022
overheads.
When included, it further improves the speedups that IGLU provides over baseline methods.
A.1 HARDWARE
We implement IGLU in TensorFlow 1.15.2 and perform all experiments on an NVIDIA V100 GPU (32 GB Memory) and Intel Xeon CPU processor (2.6 GHz). We ensure that all baselines are experimented with the exact same hardware.
A.2 TIME AND MEMORY OVERHEADS FOR VARIOUS METHODS
We consider three main types of overheads that are incurred by different methods. This includes pre- pr--preessingg overhead that is one-time. recurring overheads and additional memory overhead. We describe each of the overheads in the context of the respective methods below.
1. GraphSAGE- GraphS recursively samples neighbors at each layer for every minibatch. This is done on-the-fly and contributes to significant sampling overhead. Since this overhead is incurred for every minibatch, we categorize this under recurring overhead. We aggregate this overhead across minibatches during training. GraphSAGE does not incur preprocessing or additional memory overheads.
2. VRGCN Similar to GraphSAGE, VRGCN also recursively samples neighbors at each layer for every minibatch on-the-fly. We again aggregate this overhead across all minibatches during training. VRGCN also stores the stale/historical embeddings that are learnt for every node at every layer. This is an additional overhead of O (NKd), where K is the number of layers, N is the number of nodes in the graph and d x ExE[K] d2 is the average embedding dimensionality across layers.
3. ClusterGCN ClusterGCN creates subgraphs and uses them minibatches for training. For the creation of these subgraphs, ClusterGCN performs graph clustering using the highly optimized METIS too This overhead is a one-time overhead since graph clustering is done before training and the same subgraphs are (re-)used during the whole training process. We categorize this under preprocessing overhead. ClusterGCN does not incur any recurring or additional memory overheads.
4. GraphSAINT GraphSAINT, similar to ClusterGCN creates subgraphs to be used as mini- batches for training. We categorize this minibatch creation as the preprocessing overhead for GraphSAINT. However, unlike ClusterGCN, GraphSAINT also periodically creates new subgraphs on-the-fly. We categorize this overhead incurred in creating new subgraphs as recurring overhead. GraphSAINT does not incur any additional memory overheads.
5. IGLU IGLU creates mini-batches only once using subsets of nodes with their full neigh- borhood information which is then reused throughout the training process. In addition this, IGLU requires initial values of both the incomplete gradients a and the X embeddings (Step 3 and first part of Step in Algorithm| [ and Step and Step 4 in Algorithm 2 before optimization commence. We categorize these two overheads mini-batch creation and initializations a "s s and X embeddings as IGLU's preprocessing overhead and note that IGLU does not have any recurring overheads. IGLU does incur an additional memory overhead since it needs to store the incomplete gradients " in the inverted variant and the embeddings X* in the backprop variant. However, note that the memory occupied by X for a layer k is the same as that occupied by a for that layer (see Definition 1.. Thus, for both its variants, IGLU incurs an additional memory overhead of O (N Kd). where K is the number of layers, N is the number of nodes in the graph and d = ERE[K] dy is the average embedding dimensionality across layers.
Tables and 4 report the overheads incurred by different methods the OGBN-Protein and Reddit datasets (the largest datasets in terms of edges and nodes respectively). ClusterGCN runs into a runtime error on the Proteins dataset (denoted by ll in the table). N/A stands for Not Applicable in the tables. In the tables, specifically for IGLU, pre-processing time is the sum of initialization time
http:/ httt:://1aaree aros. dtc. umn hetm..dddggkhooeeeeeeeeee wtw.ettttttmemmeiimemeeam down
13

---

Published as a conference paper at ICLR 2022
Table 3: OGBN-Proteins: Overheads of different methods. IGLU does not have any recurring overhead while VRGCN, GraphSAGE and GraphSAINT all suffer from heavy recurring overheads. ClusterGCN runs into runtime error on this dataset (denoted by ll). GraphSAINT incurs an overhead that is 2x the overhead incurred by IGLU, while GraphS AGE and VRGCN incur upto 4.7x and ~ 7.8x the overhead incurred by IGLU respectively. For the last row, denotes initialization time, MB denotes minibatch time and T denotes total preprocessing time. Please refer to Discussion on OGBN Proteins at Section A.2 for more details.
Method
Preprocessing (One-time)
Recurring
Additional Memory
GraphSAGE
N/A N/A
276.8s
N/A
VRGCN
465.0s
O (NKd)
ClusterGCN
II
II
GraphSAINT
22.1s
101.0s
N/A
IGLU
34.0s (1) + 25.0s (MB) = 59.0s (T)
N/A
(NKd)
Table 4: Reddit: Overheads of different methods. IGLU and GraphSAINT do not have any recurring overhead for this dataset while VRGCN and GraphSAGE incur heavy recurring overheads. ClusterGCNN suffers from heavy preprocessing overhead incurred due to clustering. this case, IGLU incurs an overhead that is marginally higher (~ 1.4x) than that of GraphSAINT, while VRGCN, GraphSAGE and ClusterGCN incur as much as ~ 2.1x, ~ 4.5x and ~ 5.8 the overhead incurred by IGLU respectively. For the last line, denotes initialization time, MB denotes minibatch time and
T denotes total preprocessing time. Please refer to Discussion on Reddit at Section A.2 for more details.
Method
Preprocessing (One-time)
Recurring
Additional Memory
GraphSAGE
N/A
41.7s
N/A
VRGCN
N/A
19.2s
O (NKd)
ClusterGCN
54.0s
N/A
N/A
GraphSAINT
6.7s
N/A
N/A
IGLU
3.5s (1) + 5.7s (MB)= 9.2s (T)
N/A
(NKa)
required to pre-compute a X and mini-batch creation time. We also report the individual overhead for both initialization and mini-batch creation for IGLU. The total pre- processsin time for IGLU is denoted by T, overheads incurred for initialization by I and overheads incurred for mini-batch creation by MB.
For IGLU, the minibatch creation code is currently implemented in Python, while GraphSAINT uses a highly optimized C++ implementation. Specifically for the Reddit dataset, the number of subgraphs that GraphSAINT samples initially is sufficient and it does not incur any recurring overhead. However, on Proteins, GraphSAINT samples 200 subgraphs every 18 epochs, once the initially sampled subgraphs are used, leading to sizeable recurring overhead.
Discussion OGBN Proteins: Figure 5 summarizes the total overheads for all the methods. On the OGBN-Proteins dataset, IGLU incurs ~ 2x less overhead than GraphSAINT, the best baseline, while incurring as much as ~ 7.8x less overhead than VRGCN and 4.7x less overhead than GraphSAGE It is also important to note that these overheads are often quite significant as compared to the optimization time for the methods and can add to the overall experimentation time. For experiments on the OGBN-Proteins dataset, VRGCN's total overheads equal 46.25% of its optimization time, GraphSAINTT' overheads equal 19.63% of its optimization time, GraphSAGE's overhead equal 9.52% of its optimization time. However IGLU's total overheads equal only 5.59 % of its optimization time which is the lowest out of all methods. Upon re- re-computng the speedup provided by IGLU using the formula defined in equation (I) but this time with overheads included, it was observed that IGLU offered an improved speedup of 16.88% % (the speedup was only 11.05% when considering only optimization time).
14

---

Published as a conference paper at ICLR 2022
Total Overheads for Different Methods (Lower the better)
10a
ClusterGCN
GraphSAGE
GraphSAINT
10a
IGLU
Time
104
10a
Proteins
Reddit
Dataset
Figure 5: Total Overheads in Wall Clock Time (Log Scale) for the different methods on OGBN- Proteins and Reddit dataset. ClusterGCN runs into runtime error on the OGBN-Proteits dataset and hence has not been included in the plot. IGLU frequently offers least total overhead compared to the other methods and hence significantly lower overall experimentation time. Please refer to section A.2 for details.
Table 5: URL's and commit numbers to run baseline codes
Method
URL
Commit
GCN
gihhuh.com/villlameeifCiinppppp/
aOfdef
GraphSAGE
a0fdef
VRGCN
guthuub.com/luummm//ooohssttc
gen
da7b78
ClusterGCN
0c
AS-GCN
github..om//uunggu///SSCCCCC
5436ecd
L2-GCN
githuh.com/VIIA--Goun/LLZZC gen
687fbae
MVS-GNN
a29c2c5
LADIES
guthubbcoom/ccbbl///AADDDD
c10b526
FastGCN
b8e6e64
SIGN
httts//sstttbbboom///wwttteeetet
42a230c
PPRGo
https//ggttbb.com///UUUUMMM/PPP pytorch https://tthhh..cookkaiii////g//
c92c32e
BanditSampler
a2415a9
Discussion Reddit: On the Reddit dataset, IGLU incurs upto 2.1x less overhead than VRGCN and upto ~ 4.5x less overhead than GraphSAGE. However, IGLU incurs marginally higher overhead (~ 1.4x) than GraphSAINT. This be attributed to the non-optimized minibatch creation routine currently used by IGLU compared to highly optimized and parallelized implementation in C++ used by GraphS This is immediate avenue for future work. Nevertheless, VRGCN's total overhead equals 15,41 % of its optimization time, GraphSAINTE overhead equals 43.41 % of its optimization time, GraphSAGE's overhead equals 31.25% of its optimization time, ClusterGCN's overhead equals 41.02% of its optimization time while IGLU's overhead equals 44.09% of its optimization time. Whereas the relative overheads incurred by IGLU and GraphSAINT in comparison to optimization time may seem high for this dataset, this is because the actual optimization times for these methods are rather small, being just 15.43 and 20.86 seconds for GraphSAINT and IGLU respectively in comparison to the other methods such as VRGCN, ClusterGCN and GraphS whose optimization times are 124s, 131s and 133s respectively, almost an order magnitude larger than that of IGLU.
A.3 MEMORY ANALYSIS FOR IGLU
While IGLU requires storing stale variables which have additional memory costs, for most scenarios with real world graphs, saving these stale representations on modern GPUs are quite reasonable. We provide examples of additional memory usage required for two of the large datasets
15

---

Published as a conference paper at ICLR 2022
Reddit and Proteins in Table 6 and we observe that IGLU requires only 150MB and 260MB of additional GPU memory. Even for a graph with million nodes, the additional memory required would only be ~ 2.86GB which easily fit modern GPUs. For even larger graphs. CPU-GPU interfacing can be used. CPU and GPU interfacing for data movement is a common practice in training machine learning models and hence potential method mitigate the issue of limited memory availability in settings with large datasets. This has been explored by many works for dealing with large datasets the context of GCNs, such VR-GCN (Chen et al. 201 for storing historical activations in main memory (CPU). Such an interfacing is an immediate avenue of future work for IGLU.
Table 6: Additional Memory Overheads incurred by IGLU on Large datasets
Dutaset
# of Train Nodes
Embeedding Dumensious
Number of Layers
Memory Per Layer
Total GPU Memory
Reddit
155k
128
150MB
Proteins
90k
256
85MB
260MB
Million Sized Graph
IM
256
0,95GB
2.86GB
We observe that IGLU enjoys significant speedups and improvements in training cost across datasets as compared to the baselines as a result of using stale variables. Additionally, since IGLU requires training just single layer at a time, there is scope for further reduction in memory usage by using only the variables required for the current layer and by re-using the computation graphs across layers, and therefore making IGLU even less memory expensive.
A.4 HYPERPARAMETER CONFIGUR FOR IGLU AND BASELINES
summarrzes the source URLs and commit stamps using which baseline methods were obtained for experiments. The Adam optimizer Kingma & Ba (0015) was used to train IGLU and all the baselines until convergence for each of the datasets. A grid search was performed over the other hyper- prper-parametes for each baseline which are summarized below:
1. GraphSAGE: Learning Rate {0.01, 0.001), Batch Size - [512, 1024, 2048), Neighbor- hood Sampling Size (25, 10, 5), Aggregator- (Mean, Concat)
2. VRGCN Batch Size (512, 1000, 2048), Degree {1, 5, 10), Method (CV, CVD), Dropout- [0, 0.2, 0.5}
3. ClusterGCN Learning Rate- (0.01, 0.001, 0.005), Lambda- (-1, 1, 1e-4), Number of Clusters - [5, 50, 500, 1000, 1500, 5000). Batch Size [1, 5, 50, 100, 500), Dropout (0,
0.1, 0.3, 0.5)
4. GraphSAINT-RW Aggregator [Mean. Concat), Normalization (Norm, Bias), Depth {2, 3, 4), Root Nodes | 11250, 2000, 3000, 4500, 6000), Dropout- 10.0, 0.2, 0.5)
5. IGLU: Learning Rate (0.01, 0.001) } with learning rate decay schemes, Batch Size (512, 2048, 4096, 10000), Dropout (0.0, 0.2, 0.5, 0.7)
A.5 INCORPORATING RESIDUAL CONNECTIONS, BATCH NORMALIZATION AND VIRTUAL NODES IN IGLU
General-purpor techniques such as BatchNorm and skip/residual connections, and GCN-specific advancements such as bi-level aggregation using virtual nodes offer performance boosts. The current implementation of IGLU already incorporates normalizations descrihed in Sections and Below we demonstrate how all these aforementioned architectural variations can be incorporated into IGLU with minimal changes to Lemma D part 2. Remaining guarantees such those offered by Lemma part 1 and Theorem 2 remain unaltered but for changes to constants.
Incorporating BatchNorm into IGLU: As pointed out in Section 3, IGLU assumes general form of the architecture, specifically
= .jj (0 (.)
where f includes the aggregation operation such as using the graph Laplacian, weight matrices and any non-linearity. This naturally allows operations such as normalizations (LayerNorm, BatchNorm
16

---

Published as a conference paper at ICLR 2022
etc) to be carried out. For instance, the f function for BatchNorm with standard GCN would look like the following
2
Σ
JEV
2 2 1
V L +
x T 2 B*
where denotes non-linearity like the sigmoid, I E xde is diagonal matrix and B Rdd is a vector, and 4 V E R are vectors containing the dimension-wist -wiee mean and variance values over a mini-hatch (division while computing / is performed element-wise). The parameter E is taken to collect parameters contained in all the above operations i.e. E [W* r " in the above example u Vi are computed using samples in a mini-batch itself). Downstream calculations in and Lemma continue hold with no changes.
Definition I
Incorporating Virtual Nodes into IGLU: Virtual nodes can also be seamlessly incorporated simply by re-parameterizing the layer-wise parameter E* We are referring to (Pei 2020) [Pei et al ICLR 2020] for this discussion. Let R be the set of relations and let No, denote graph neighborhood and latent-space neighborhood functions respectively. concrete example is given below to illustrate how virtual nodes can be incorporated. We note that operations like BatchNorm etc can be additionally incorporated and alternate aggregation operations c.g. concatenation can be used instead.
(krr) g
Σ JEN,(()
[(i))=r
(Low-level aggregation)
(krr)
Σ
x x-1
S;
(EN
T(())=
Σ
(k.r)
+ +8; (kir))
m
gi
(High-level aggregation)
R
PER
x = (W*))m!))
(Non-linear transform)
where 7 denotes the relationship indicator, Ai denotes the graph edge weight between nodes and j and Tiy denotes their geometric similarity in latent space. Note that g; (ktr) s corresponds to
embeddings of the virtual nodes in the above example. To implement the above, the parameter E* can be taken collect the learnable parameters contained in all the above operations i.e. E
Lkk L W in the above example. Downstream calculations in Definition and Lemma continue to hold as is with no changes.
Incorporating Skip/Residual Connections into IGLU: 3 does not directly allow skip connections but they can be incorporated readily with no change to Definition I and minor changes to Lemma I Let us introduce the notation & - denote direct forward (skip) connection directed from layer & to some layer m > k. In purely feed-forward style architecture, we would only have connections of the form & + k + 1. The following gives simple example GCN with a connection that skips two layers, specifically (I- 2) + k.
The architecture style presented in Section
x = f .j E (i) UN(();; F²)) x
where f includes the aggregation operation with the graph Laplacian, the transformation weight matrix and any non-linen non-lincar.ty. Definition Caciioonnnneee Ineds changes incorporate such architectures. Part 1 of Lemma also needs no changes to address such cases. Part needs a simple modification as shown below
17

---

Published as a conference paper at ICLR 2022
Lemma (Lemma adapted to skip connections). For the final layer, we continue have (i.e. change) a G(WK+t)) For any k < K, we have a - >
Dia
8X4
axi i.e. a = -m:k-m EiEv Ede Big ax. 3P
Note that as per the convention established in the paper, Emck-tm that while taking the derivatives, a values fixed (treated constant) for all > & such that + m. This "conditioning" is important since am also indirectly depends on X if m > k.
0(a"
implies
8x* all am st. R-om
Proof of Lemma 1.2 adapted to skip connections: We consider two cases yet again and use Definition that tells us that
Diic
= Dic cEV OXK iP
Case 1 (A: K): Since this the top-most layer and there are no connections going ahead let alone skipping ahead, the analysis of this case remains unchanged and continues to yield a G(WK+I]]
Case 2 (k < K): Using Definition I and incorporating all layers to which layer k has direct or skip connection gives us
DDic 0
dm
0xi ox
SpP = ΣΣ
ΣΣΣ
Σ
Jic
axm
1EV cE[]
mik-am EV nE
LcV 1=1
Rearranging the terms gives us
Jtp = EE ΣΣ
dm
Oijic 0xm
ΣΣΣ mik-m LEV q=1
0xm
Iic
ox
ox
m LEV 41
iEV cE|C]
where we simply used Definition in the second step. However, the resulting term simply gives us which conditions on, treats constant, the term a
o Em Oxa"
ax jn
all ar s.t. k-+m
m according to our notation convention. This finishes the proof of part for all > & such that k - 2 adapted to skip connections.
A.6 COMPARISON OF IGLU WITH VR-GCN, MVS-GNN AND GNNAUTOSCALE
We highlight the key difference between IGLU and earlier works that cache intermediate results for speeding up GNN training below.
A.6.1 VRGCN v/s IGLU
1. Update of Cached Variables: VR-GCN (Chen et al. 2018a) caches only historical embed- dings, and while processing single mini-batch these historical embeddings are updated for sampled subset of the nodes. In contrast IGLU does not update any intermediate results after processing each mini-batch. These are updated only once per epoch, after all parameters for individual layers have been updated.
2. Update of Model Parameters: VR-GCN's backpropagation step involves update of model parameters of all layers after each mini-batch. In contrast IGLU updates parameters of only a single layer at a time.
3. Variance due to Sampling: VR-GCN incurs additional variance due to neighborhood sampling which is then reduced by utilizing historical embeddings for some nodes and by computing exact embeddings for the others. IGLU does incur such variance since IGLU uses all the neighbors.
A.6.2 MVS-GNN v/s IGLU
MVS-GNN (Cong et al. 2020 another work that caches historical embeddings. It follows a nested training strategy wherein firstly large batch of nodes sampled and mini-batches further
18

---

Published as a conference paper at ICLR 2022
created from this large batch for training. MVS-GNN handles variance due to this mini-batch creation by performing importance weighted sampling to construct mini-batches.
1. Update of Cached Variables and Variance due to Sampling: Building upon VR-GCN, to reduce the variance in embeddings due to its sampling of nodes at different layers, MVS-GNN caches only embeddings and uses historical embeddings for some nodes and recompute the embeddings for the others. Similar to VR-GCN, these historical embeddings are updated as and when they are part of the mini-batch used for training. As discussed above, IGLU does not incur such variance since IGLU uses all the neighbors.
2. Update of Model Parameters: Update of model parameters in MVS-GNN is similar to that of VR-GCN, where backpropagation step involves update of model parameters of all layers for each mini-batch. As described already, IGLU updates parameters of only a single layer time.
A.6.3 GNNAUTOSCALE V/S IGLU
GNNAutoScale (Fey et al. 2021 extends the idea of caching historical embeddings from VR-GCN and provides scalable solution.
1. Update of intermediate representations and model parameters: While processing minibatch of nodes, GNNAutoScalle computes the embeddings for these nodes at each layer while using historical emheddings for the immediate neighhors outside the current minibatch. After processing each mini-batch, GNNAutoScale updates the historical embeddings for nodes considered in the mini-batch. Similar VR-GCN and MVS-GNN, GNNAutoScale updates all parameters at all layers while processing mini-batch of nodes. In contrast IGLU does not update intermediate results (intermediate representations Algorithm and incomplete gradients in Algorithm 2) after processing each minibatch. In fact, these are updated only once per epoch, after all parameters for individual layers have been updated.
2. Partitioning: GNNAutoScale relies the METIS clustering algorithm for creating mini- batches that minimize inter-connectivity across batches. This is done to minimize access to historical embeddings and reduce staleness. This algorithm tends bring similar nodes together, potentially resulting in the distributions of clusters being different from the original dataset. This may lead to biased estimates of the full gradients while training using mini- batch SGD as discussed in Section 3.2, Page 5 of Cluster- (Chiang et al. 2019). IGLU does not rely on such algorithms since it's parameter updates are concerned with only a single layer and also avoids potential additional bias.
Similarity of IGLU with GNNAutoScale: Both of the methods avoid a neighborhood sampling step, thereby avoiding additional variance due to neighborhood sampling and making use of all the edges in the graph. Both IGLU and GNeeutoScale propose methods to reduce the neighborhood explosion problem, although in fundamentally different manners. GNNAutoScale does by pruning the computation graph by using historical embeddings for neighbors across different layers. IGLU on the other hand restricts the parameter updates to a single layer at a time by analyzing the gradient structure of GNNs therefore alleviating the neighborhood explosion problem.
A.6.4 SUMMARY OF IGLU's TECHNICAL NOVELTY AND CONTRAST WITH CACHING BASED RELATED WORKS
To summarize, IGLU is fundamentally different from these methods that cache historical embeddings in that it changes the entire training procedure of GCNs in contrast with the aforementioned caching based methods follows:
The above methods still follow standard SGD style training of GCNs in that they update the model parameters at all the layers after each mini-batch. This is very different from IGLU's parameter updates that concern only a single layer while processing mini-batch.
IGLU can cache either incomplete gradients or embeddings which is different from the other approaches that cache only embeddings. This provides alternate approaches for training GCNs and we demonstrate empirically that caching incomplete gradients, in fact, offers superior performance and convergence.
19

---

Published as a conference paper at ICLR 2022
Unlike GeNAutoScale and VR-GCN that update some of the historical embeddings after each mini-batch is processed, IGLU's caching is much more aggressive and the stale variables are updated only once per epoch, after all parameters for all layers have been updated.
Theoretically, we provide good convergence rates and bounded bias even while using stale gradients, which has not been discussed in any prior works.
These are the key technical novelties of our proposed method and they are a consequence of a careful understanding of the gradient structure of GCN's themselves.
A.6.5 EMPIRICAL COMPARISON WITH GNNAUTOSCALE
We provide an empirical comparison of IGLU with GNNAutoScale and summarize the results in Table 7 and Figure 6 It is important to note that the best results for GNNAutoScale as reported by the authors in the paper, correspond to varying hyperparameters such as number of GNN layers and different embedding dimensions across methods, datasets and architectures. However, for the experiments covered the main paper, we use layer settings for PPI-Large, Flickr and Reddit and layer settings for OGBN-Arxiv and DGBN-Protein datasets consistently for IGLU and the baseline methods, as motivated by literature. We also ensure that the embedding dimensions are uniform across IGLU and the basclines. Therefore, to ensure fair comparison, experiments with these parameters for GNNAutoScale set to values that are consistent with our experiments for IGLU and the baselines. We train GNNAutoScale with three variants, namely GCN, GCNII (Chen et al. 2020) and PNA (Corso et al.) 2020) and report the results for each of the variant. We also note here that GNNAutoScale was implemented in PyTorch (Paszke et al., 2019) while IGLU was implemented in TensorFlow (Abadi et al. 2016). While this makes a wall wall-clock time comparison unsuitable discussed in Appendix B.2, we still provide a wall-clock time comparison for completeness. We also include the best performance numbers for GNNAutoScale on these datasets (as reported by the authors in Table 5, Page of the GNNAutoScale paper) across different architectures. Note that we do not provide comparisons on the DGBN-Proteil dataset since we ran into errors while trying to incorporate the dataset into the official implementation of GNNAutoScale.
perform additional
Results: Figure provides convergence plots comparing IGLU with the different architectures of GNNAutoScale and summaiies the test performance on PPI-Large, Flickr, Reddit and OGBN- Arxiv (transductive) datasets. From the table, we observe that IGLU offers competitive performance compared to the GCN variant of GAS for the majority of the datasets. We also observe from Figure 6 that IGLU offers significant improvements in training time with rapid early convergence on the validation set. We note that more complex architectures such as GCNII and PNA offer improvements in performance to GNNAutoScale. IGLU being architecture agnostic be incorporated with these architectures for further improvements in performance. We leave this as an avenue for future work.
A.7 DETAILED DESCRIPTION OF ALGORITHMS AND 2
We present Algorithms and again below (as Algorithms
3 and respectively) with details of cach
step.
IGLU: backprop order Algorithm 3 iimplements the IGLU algorithm in its backprop variant. Node embeddings X k [K] are calculated and kept stale. They are not updated even when model
parameters ER, k E [K] get updated during the epoch. On the other hand, the incomplete task gradients " k E [K] are kept refreshed using the recursive formulae given in Lemma For sake of simplicity, the algorithm been presented with staleness duration of one epoch i.e. X are refreshed at the beginning of each epoch. Variants employing shorter or longer duration of staleness can be also explored simply by updating X k E [K] say twice in an epoch or else once every two epochs.
IGLU: inverted order Algorithm 4 jimplements the IGLU algorithm in its inverted variant. Incom- plete task gradients a A E [K] are calculated once at the beginning of every epoch and kept stale. They are not updated even when node embeddings X & E [ get updated during the epoch. On the other hand, the node embeddings X k E [K] are kept refreshed. For sake of simplicity, the algorithm been presented with staleness duration of one epoch i.c. a are refreshed at the beginning of each epoch. Variants employing shorter longer durations of staleness can be also explored
20

---

Published as a conference paper at ICLR 2022
Table 7: Test Accuracy of IGLU compared GNNAutoScale. * We perform experiments using GNNeutoScale in setting identical to IGLU with 2-layer models on PPI-Large, Reddit and Flickr datasets and 3-layer models on OGBN-Arxiv dataset (transductive) and report the performance. For completeness, we also include the best results from GNNAutoScale for comparison. We were unable to perform experiments with GNNAutoScale on the Proteins dataset, and hence omit it for comparison. We observe that IGLU performs competitively with GNNAutoScale for models like GCN on most of the datasets. IGLU being architecture agnostic can be further combined with varied architectures like GCNII and PNA to obtain gains offered by these architecture.
Algorithm
PPI-Large
Reddit
Flickr
Arxiv (Trans)
Our Experiments*
GAS-GCN
0.983
0.954
0.533
0.710
GAS-GCNII
0.969
0.964
0.539
0.724
GAS-PNA
0.917
0,970
0.555
0.714
Best Results: GNNAutoScale, (From Table Page 9)
GAS-GCN
0.989
0.954
0.540
0.716
GAS-GCNII
0.995
0.967
0.562
0.730
GAS-PNA
0.994
0.971
0.566
0.725
IGLU
0.987 0.004
0.964 + 0.001
0.515 0.001
0.719 + 0.002
PPI-Large
Reddit
1.0
0.9
0.8
0.8
Micro-F1
Micro
0.6
0.6
0.5
0.4
0.4
0.3
0.2
20
5.0
12.5
15.0
17.5
Time(s)
Clock Timels)
Flickr
OGBi-Arxiv
0.7
0.5
Micro-F1
0.4
Micro-F1
0.5
0.3
0.4
(GCN)
GNNAutoScale (GCNII)
0,3
GNNAuto (PNA)
0.2
IGLU
0.1
0.1
1.0
25 Wall Clock Time(s)
15
20
30
35
40
Wall Clock Time(s)
Figure 6: Wall Clock Time vs Validation Accuracy on different datasets as compared to GN- NAutoScale. We perform experiments using GNNAutoScale setting identical to IGLU with 2-layer models on PPI-Large, Reddit and Flickr datasets and 3-layer models on OGBN-Arxiv dataset and report the performance. IGLU offers competitive performance and faster convergence across the datasets.
simply by updating A say twice in an epoch or else once every two epochs. This has been explored in Section 4.2 (see paragraph on "Analysis of Degrees of Staleness.") ").
21

---

Published as a conference paper at ICLR 2022
Algorithm 3 IGLU: backprop order
Input: GCN G, initial features X task loss 1: Initialize model parameters E k E [K], W w
2: for epoch = 1, 1 2....... do
3: for k == 1... do
4: Refresh X + 1(X 1X* will be kept stale till next epoch
5: end for
6:
KK
//redictioon
7:
DL.
l/The loss derivative matrix
NxC
8: Compute BWK+ t (
M/sing Lemma here
9: Update W K +1 t WK+ OWRTI
10: Refresh a K -- G(WK+I)T
//Using Lemma 2 here
for k K ...22d do Compute
8C
o(a
//siing Lemma
here
DET
gE
13:
Update E t E 8C
8F
Refresh a=11 Bla
14:
//Using Lemma
1 2 here
0X
15:
end for
end for
Algorithm 4 IGLU: inverted order
Input: GCN 9, initial features X task loss
1: Initialize model parameters E & [K], WK+1
2: for k == 1.... K do
3: X + [( E*)
I/Do an initial forward pass
4: end for
5: for epoch 1,2, 1......de do
6: Y X kkk
//Predictoon l/The loss derivative matrix
7: G
Jite NxC
//se Lemma 1.2 to refresh a [K].
8:
Refresh a K t (WK+)
9:
for = K do
10:
Refresh ax
ax
a
11:
end for
WThese a k [K] for k = 1=.... K..KKo do
will now be kept stale till next epoch
12:
13:
dc Compute DE
o(a*
l/using Lemma 1 1 here
dg
14:
Update E + E
0E 15: Refresh X t f(X k- k-1, bb
end for
ac 17: Compute aw k+ +
//ssing Lemma
1 1 here
18:
Update W WK+1
0C ΦWK+T
19:
end for
A.8
VALIDATION PERFORMANCE AT A MINI-BATCH LEVEL
The performance analysis in the main paper was plotted at coarse granularity of an epoch. We refer to an epoch as one iteration of steps 18 (both inclusive) in Algorithm For a finer analysis of IGLU's performance the OGBN-Proteins dataset, we measure the Validation ROC-AUC at the gramularity of mini-batch As mentioned the "SGD Implementation' paragraph in Page 5 below the algorithm description in the main paper, steps 14 and 18 in Algorithm 4 are implemented using mini-batel SGD. Recall that OGBN-Proteins used layer GCN. For the proteins dataset we have ~ 170 for training. We update the parameters for each layer using all the mini-batches
22

---

Published as a conference paper at ICLR 2022
from the layer closest to the input to the layer closest to the output as detailed in Algorithm 4 To generate predictions, we compute partial forward passes after the parameters each layer is updated. We plot the validation ROC-AUC as the first epoch progresses in Figure 7 We observe that when the layer closest to the input is trained (Layer in the figure), IGLU has an ROC-AUC close to 0.5 on the validation set. Subsequently once the second layer (Layer 2 in the figure) is trained, we observe that the validation ROC-AUC improves from around ~ 0.51 to ~ 0.57 and finally once the layer closest the output trained (Layer 3 in the figure). the ROC-AUC progresses quickly to high validation ROC-AUC of ~ 0.81. In the figure in the main paper the high validation score reflects the result at the end of the first epoch. Training the GCN using total of 510 minibatches (~ 170 per layer) approximately takes 5 seconds as depicted in Figure 2 in the main paper.
OGBN Protein:: Layer-wise Validation Micro-F1 Minibatch Count, Egoch
Layer
Layer
0.75
Layer
Validation Micro-FI
0.70
0.65
0.55
0.50
100
200
300
400 500
Minibatch Count
Figure 7: Fine-grained Validation ROC-AUC for IGLU on the Proteins Dataset for Epoch 1. We depict the value of Validation ROC AUC at the granularity of minibatch for the first epoch. We observe that the Validation ROC-AUC begins with a value close to 0.5 and quickly reaches an ROC-AUC of 0.81 by the end of the first epoch. As mentioned in the text, Proteins uses 3 layer GCN and each layer processes ~ 170 mini-batches.
B DATASET STATISTICS AND ADDITIONAL EXPERIMENTAL RESULTS
B.1 DATASET STATISTICS
Table provides details on the benchmark node classification datasets used the experiments. The following five benchmark datasets were used to empirically demonstrate the effectiveness of IGLU: predicting the communities to which different posts belong in Reddi (Hamilton et al. 2017), classifying protein functions across various biological protein-protein interaction graphs in PPI-Large (Hamilton et al. 2017), categorizing types of images based on descriptions and common properties Flick (Zeng al. 2020), predicting paper-paper associations in OGBN-Arxi et al. 2020) and categorizing meaningful associations between proteins in OGBN-Protein al. 2020
(Hu
B.2 COMPARISON WITH ADDITIONAL BASELINES
In addition to the baselines mentioned Table Table compares IGLU to LADIES Zou et al. 2019), L2-GCN You et al. 2020), AS-GCN (Huang et al. 2018). MVS- GNN COog et al. 2020). FasIGCN (Chen al. 201 8b). SIGN (Frasca et al. 2020), PPRGo (Bojchevski al. 2020) and Bandit Sampler's (Liu et al. 2020) performance on the test set. However, wall-clock time comparison with
http://snap.stanford.cco http://wwww.to.llid..rprpapapppp
http::/gg...aallooall////ssspppp Google Drive Link
23

---

Published as a conference paper at ICLR 2022
Table 8: Datasets used in experiments along with their statisties. MC refers to a multi-class
problem, whereas ML refers to a multi-label problem.
Dataset
# Nodes
Edges
Avg. Degree
Features
# Classes
Train/Val/Test
PPI-Targe
56944
818716
14
50
121 (MI.)
0.79/0. 11/0/10
Reddit
232965
11606919
60
602
41 (MC)
0.66/0. 10/0.24
Flickr
89250
899756
10
500
7 (MC)
0.5/0.25/0.25
OGBN-Proteins
132534
39561252
597
8
112 (MI.)
0.65/0. 16/0. 19
OGBN-Arxiv 169343
1166243
13
128
40 (MC)
0.54/0.18/0..
these methods is not provided since the author implementations of LADIES, L2GCN, MVS-GNN and SIGN are in Py PyToch (Paszke et al. 2019) which has been shown to be less efficient than Tensorflow (Chiagg al., 2019; Abadi et | [0166] for GCN applications. Also, the official AS-GCN, FastGCN and Bandit Sampler implementations released by the authors were for 2 layer models only, whereas some datasets such as Proteins and Arxiv require 3 layer models for experimentation. Attempts to generalize the code to a 3 layer model ran into runtime errors, hence the missing results are denoted by ** in Table and these methods are not considered for a timing analysis. MVS-GNN also runs into runtime eπror the Proteins dataset denoted by II. IGLU continues to significantly outperform all additional baselines on all the datasets.
Table 9: Performance Test Set for IGLU compared to additional algorithms. The metric is ROC-AUC for Proteins and Micro-F1 for the others IGLU still retains the state-of-the-art results across all datasets even when compared to these new baselines. MVS-GNN ran into runtime error on the Proteins dataset (denoted by II). AS-GCN, FastGCN and BanditSampler run into a runtime error on datasets that require more than two layers (denoted by **). Please refer to section B.2 for details.
Algorithm
PPI-Large
Reddit
Flickr
Proteins
Arxiv
LADIES
0.548 1 0.011
0.923 = 0.008
0.488 1 0.012
0.636 1 0.011
0.667 1 0.002
L2GCN
0.923 + 0.008
0.938 = 0.001
0.485 + 0.001
0.531 + 0.001
0.656 + 0.004
ASGCN
0.687 0.001
0.958 = 0.001
0.504 0.002
** II
**
MVS-GNN
0.880 = 0.001
0.950 0.001
0.507 = 0.002
0.695 + 0.003
FastGCN
0.513 0.032
0.924
0.001
0.504 = 0.001
**
**
SIGN
0.970 = 0.003
0.966
0.003
0.510 0.001
0.665 + 0.008
0.649 + 0.003
PPRGo
0.626 + 0.002
0,946
0.001
0.501 + 0.001
0.659 + 0.006
0.678 + 0.003
BanditSampler
0.905 + 0.003
0.957 = 0.000
0.513 = 0.001
IGLU
0.987 + 0.004
0.964 0.001
0.515 + 0.001
0.784 + 0.004 0.718 + 0.001
Table 10: Per epoch time (in seconds) for different methods as the number of layers increase into runtime
the OGBN-Proteins dataset. ClusterGCN VRGCN ran into a runtime error for 4 layer model (denoted by Il). IGLU and GraphS A INT scale almost linearly with the number of layers. It should be noted that these times strictly include only optimization time. GraphSAINT has much lower per-epoch time than IGLU because of the large sizes of subgraphs per batch (~~ 10000 nodes), while IGLU uses minibatches of size of 512. This results in far less gradient updates within an epoch for GraphS AINT when compared with IGLU, resulting much smaller per-epoch time but requiring more epochs overall. Please refer section B.3.1 for details.
on this dataset noted earlier.
Number of Layers
Method
3
4
GraphSAGE
2.6
14.5
163.1
VR-GCN
2.3
21.5
I|
GraphSAINT
0.45
0.61
0.76
IGLU
2.97
5.27
6.99
24

---

Published as a conference paper at ICLR 2022
Table 11: Test Performance (ROC-AUC) Best Validation for different methods the number of layers increase on the OGBN-Proteins Dataset. Results are reported for single run but trends were observed to remain consistent across repeated runs. VRGCN ran into runtime error for 4 layers (denoted by Il). IGLU offers steady increase in performance as the number of layers increase, as well as state-of-the-art performance throughout. GraphSAGE shows a decrease in performance on moving from 3 to 4 layers while GraphSAINT shows only marginal increase in performance. Please refer to section B.3.2 for details.
Number of Layers
Method
3
4
GraphSAGE
0.755
0.759
0.742
VR-GCN
0.732
0.749
II
GraphSAINT
0.752
0.764
0.767
IGLU
0.768
0.783
0.794
Test Convergence AUC (Higher better)
0.800
VR-GCN
0.775
GraphSAGE
GraphSAINT
0.750
IGLU
0.725
AUC
0.700
0.675
0.650
Layers
Figure 8: Test Convergence AUC plots across different number of layers on the OGBN-Proteins dataset. IGLU has consistently higher AUTC values compared to the other baselines, demonstrating increased stability, faster convergence and better generalization. GraphS AGE suffers from neighbor- hood explosion problem and the training became very slow as noted earlier. This results a decrease in the AUTC while going from 3 to 4 layers. GraphSAGFF AUTCC for 4 layers is only 0.313, and is thus not visible in the plot. VRGCN also suffers from the neighborhood explosion problem and runs into runtime errors for 4 layer model. ClusterGCN runs into runtime error for the OGBN- OGBN-Proteins for all 2, and layers and is therefore not present in this analysis. Please refer to Section B.3.2 for details.
B.3 TIMING ANALYSIS FOR SCALING TO MORE LAYERS
To compare the scalability and performance of different algorithms for deeper models, models with 2, and 4 layers were trained for IGLU and the baseline methods. IGLU was observed to offer per-epoch time that scaled roughly linearly with the number of layers as well as offer the highest gain in test performance the number of layers was increased.
B.3.1 PER EPOCH TRAINING TIME
Unlike neighbor sampling methods like VRGCN and GraphSAGE, IGLU does not suffer from the neighborhood explosion problem as the number of layers increases, since IGLU updates involve only single layer at any given time. We note that GraphSAINT and ClusterGCN also do not suffer from the neighborhood explosion problem directly since they both operate by creating GCNs on subgraphs. However, these methods may be compelled to select large subgraphs or else suffer from poor convergence. To demonstrate IGLU's effectiveness in solving the neighborhood explosion problem, the per-epoch training times summarized function of the number of layers in Table
25

---

Published as a conference paper at ICLR 2022
10 on the Proteins dataset. A comparison with ClusterGCN could not be provided since it ran into runtime errors on this dataset. In Table while going from to 4 layers, GraphSAINT was observed to require 1.6x more time per epoch while IGLU required 2.3x more time per epoch, with both methods scaling almost linearly with respect to number of layers as expected. However, GraphS AGE suffered 62x increase in time taken per epoch in this case, suffering from the neighborhood explosion problem. VRGCN ran into a run-time error for the 4 layer setting (denoted by in Table I0.. Nevertheless, even while going from 2 layers layers, VRGCN and GraphSAGE are clearly seen to suffer from the neighborhood explosion problem, resulting in an increase in training time per epoch of almost 9.4x and 5.6x respectively.
We note that the times for GraphSAINT in Table I0 are significantly smaller than those of IGLU even though earlier discussion reported IGLU as having the fastest convergence. However, there is no contradiction GraphSAINT operates with very large subgraphs, with each subgraph having almost 10 of the nodes of the entire training graph (~~ 10000 nodes in minibatch), while IGLU operates with minibatches of size 512, resulting in IGLU performing lot more gradient updates within an epoch, as compared with GraphSAINT, Consequently, IGLU also takes fewer epochs to converge to better solution than GraphSAINT, thus compensating for the differences in time taken per epoch.
B.3.2 TEST CONVERGENCE AUC
This section explores the effect of increasing the number of layers on convergence rate, optimization time, and final accuracy, when scaling to larger number of layers. To jointly estimate the efficiency of a method in terms of wall clock time and test performance achieved, the area under the test convergence plots (AUTC) for various methods was computed. A method that converged rapidly and that too to better performance levels would have a higher AUTC than a method that converges to suboptimal values else converges very slowly. To fairly time all methods, each method was offered time that was triple of the time it took the best method to reach its highest validation score. Defining the cut-off time this way ensures that methods that may not have rapid early convergence still get a fair chance to improve by having better final performance, while also simultaneously penalizing methods that may have rapid early convergence but poor final performance. We rescale the wall clock time to be between 0 and 1, where 0 refers to the start of training while refers to the cut-off time.
Figure g summarizes the AUTC values. IGLU consistently obtains higher AUC values than all methods for all number of layers demonstrating its stability, rapid convergence during early phases of training and ability to generalize better as compared to other baselines. GraphS AGE suffered from neighborhood explosion leading to increased training times and hence decreased AUC values as the number of layers increase. VR-GCN also suffered from the same issue, and additionally ran into a run-time error for 4 layer models.
Results:
Test Performance with Increasing Layers: Table IT summarizes the final test performances for different methods, across different number of layers. The performance for some methods is inconsis- tent as the depth increases whereas IGLU consistently outperforms all the baselines in this case as well with gains in performance technique to train deeper GCN models.
increase the number of layers hence making it attractive
B.4 SCALABILITY TO LARGER DATASETS: OGBN PRODUCTS
To demonstrate the ability of IGLU scale to very large datasets, we performed experiments on the OGBN-Product, dataset (Hu et al. 2020). one of the largest datasets in the OGB collection, with its statistics summarized in Table
Table 12: Statistics for the OGB-Products datasets. MC refers to a multi-class problem, whereas ML refers to multi-label problem.
Dataset
# Nodes
# Edges
Avg. Degree
# Features
# Classes
Train/Val/Test 0.08/0.02/0.90
2,449,029
61,859,140
50.5
100
47 (MC)
To demonstrate scalability, we conducted experiments in the transductive setup since this setup involves using the full graph. In addition, this was the original setup in which the dataset was
26

---

Published as a conference paper at ICLR 2022
Table 13: Performance on the OGBN-Products Test Set for IGLU compared to baseline algo- rithms. IGLU outperforms all the baseline methods on this significantly large dataset as well.
Algorithm
Test Micro-F1
GCN
0.760 = 0.002
GraphSAGE
0.787 + 0.004
ClusterGCN
0.790 = 0.003
GraphSAINT
0.791 = 0.002
SIGN (3,3,0)
0.771 + 0.001
SIGN (5,3,0)
0.776 = 0.001
IGLU
0.793 0.003
benchmarked, therefore allowing for a direct comparison with the baselines (results taken from Table 4 in OGB (Hu et al., (020)) and Table 6 in SIGN (Frasca et al., 2020)). We summarize the performance results in the Table reporting Micro-FI as the metric. We however do not provide timing comparisons with the baseline methods since IGLU is implemented in TensorFlow while the baselines in the original benchmark Hu et al. (2020) are implemented PyTorch. This therefore renders direct comparison of wall-clock time unsuitable. Please refer Appendix B.2 for more details.
We observe that IGLU is able to scale to the OGBN-Products dataset with 2.4 million nodes and outperforms all of the baseline methods.
B.5 APPLICABILITY OF IGLU IN THE TRANSDUCTIVE SETTING: OGBN-ARXIV AND OGBN-PROTEINS
In addition to the results in the inductive setting reported in the main paper, we perform additional ex- periments the OGBN-Arxiv and OGBN-Proteins dataset in the transductive setting to demonstrate IGLU's applicability across inductive and transductive tasks and compare the performance of IGLU that of transductive baseline methods Table 14 (results taken from OGB (Hu al. 2020h).
Table 14:
Comparison of IGLU's Test performance with the baseline methods in the trans- ductive setting on the OGBN-Arxiv and OGBN- datasets. The metric is Micro-F1 for OGBN-Arxiv and ROC-AUC for OGBN-Proteins.
Algorithm
OGBN-Arxiv
OGBN-Proteins
GCN
0.7174 1 0.0029 0.7251 0.0035
GraphSAGE
0.7149 + 0.0027
0.7768 + 0.0020
IGLU
0.7193 + 0.0018
0.7840 0.006T
We observe that even in the transductive setting, IGLU outperforms the baseline methods on both the OGBN-Arxiv and OGBN-Protein datasets.
B.6 ARCHITECTURE AGNOSTIC NATURE OF IGLU
To demonstrate the applicability of IGLU to a wide-variety of architectures, we perform experiments on IGLU with Graph Attention Networks (GAT) (Veličković et al., 2018). GCN (Kipf Welling 2017) and GraphSAGE (Hamilton et al., 2017) based architectures and summarize the results for the same in Table [5] and 16 respectvivy as compared to these baseline methods. We use the Cora, Citeseer and Pubmed datasets as originally used in Veličkovié et al. (2018) for comparison with the GAT based architecture and the OGBN-Arxiv dataset for comparison with GCN and GraphSAGE based architectures (baseline results originally reported in (Hu et al.) 2020)).
We observe that the IGLU+GAT, IGLU+GCN and IGLU+GraphS outperforms the baseline methods across datasets, thereby demonstrating the architecture agnostic nature of IGLU.
27

---

Published as a conference paper at ICLR 2022
Table 16: Comparison of IGLU's test perfor- mance with GCN and GraphSAGE architec- tures with the baseline methods on the OGBN- Arxiv dataset.
Table 15: Comparison of IGLU +GAT's test performance with the baseline GAT on differ- ent datasets.
Algorithm
Cora
Citeseer
Pubmed
Algorithm
OGBN Arxiv
GAT
0.823
0.007 0.711 0.006
0.786 1 0.004
GCN
0.7174 0.0029
0.0029 0.7149 0.0027
GraphSAGE
IGLU GAT 0.829 + 0.044
0,717 + 0.005
0.787 + 0.002
GGLU+GCN
0.7187 0.0014
IGLU GraphSAGE
0.7155 0.0032
B.7 EXPERIMENTS USING SMOOTH ACTIVATION FUNCTION: GELU
To understand the effect of using non-smooth smooth activation functions IGLU, we perform experiments using the GELU (Hendrycks & Gimpel 2020) activation function which is a smooth function and in-line with the objective smoothness assumptions made in Theorem 2
1 j erf(x//2)) 2
GELU(x) ( S σ) = r2) = r
We compare the performance of IGLU using ReI.U and GELU all the 5 datasets in the main paper and summarize the results in Table 17
Table 17: Effect of Non-smooth vs Smooth activation functions: Test Performance of IGLU on different datasets using ReLU and GELU activation functions. Metries are the same for the datasets as reported in Table of the main paper. Results reported are averaged over five different runs.
Dataset
ReLU
GELU
PaI-L
0.987 + 0.004
0.987 0.000
Reddit
0.964 + 0.001
0.962 + 0.000
Flickr
0.515 0.001
0.516 0.001
Proteins
0.784 + 0.004
0.782 + 0.002
Arxiv
0.718 + 0.001
0.720 0.002
We observe that IGLU is able to enjoy very similar performance across both GELU and ReLU as activation functions, thereby justifying the practicality of our smoothness assumptions.
B.8 ANALYSIS ON DEGREE OF STALENESS: BACKPROP ORDER OF UPDATES
To understand the effect of more frequent updates in the backprop variant, performed additional experiments using the backprop variant on the PPI-Large dataset and varied the frequency of updates, the results of which are reported in Table 18 for a single run. We fix the hyperparameters and train for 200 epochs.
Table 18: Accuracy different update frequeney PPI-Large: Backprop Order
Update Frequency
Train Micro-F1
Validation Micro-Fl
Test Micro-FI
0.5
0.761
0.739
0.756
0.805
0.778
0.796
0.794
0.769
0.784
We observe that more frequent updates help stabilize training better. We also observe that update frequencies and perform competitively, and both significantly outperform update frequency 0.5.
However note that with higher update frequency, incur additional computational cost since we need to re-compute embeddings more frequently. We believe that both improved stability and competitive performance be attributed the fresher embeddings, which otherwise kept stale
28

---

Published as a conference paper at ICLR 2022
within epoch in this order of updates. The experiment with frequency 0.5 has slower convergence and comparatively poor performance as expected.
B.9 CONVERGENCE TRAIN Loss vs WALL CLOCK TIME
PPI-Large
Reddit
Flickr
0.6
1.8
Train Loss
1.6
1.0
1.4
0.2
0.5
0.0
20
60
100
0.0
1.0
Wall Clock Time
Wall Clock Time
Wall Clock Time
N-
OGBN-Arziv
3.0
Train Loss
Gra PAGGE
0.4
2.0
GraphSAINT
ClusterGCN
0.3
1.0
0.2
40
60
100
10
30
50
60
Wall Clock Time
Wall Clock Time
Figure 9: Training Loss curves of different methods the benchmark datasets against Wall clock time.
Figure D provides train loss curves for all datasets and methods in Table IGLU is able to achieve lower training loss faster compared to all the baselines across datasets.
C THEORETICAL PROOFS
In this section we provide formal restatement of Theorem aa well as its proof. We also provide the proof of Lemma 1 below.
C.I PROOF LEMMA
Proof of Lemma We consider the two parts of Lemma separately and consider cases while proving each part. For each part, Case pertains to the final layer and Case 2 considers intermediate layers.
Clarification about some Notation in the statements of Definition 1 and Lemma 1: The notation
GIGYY
is meant to denote the partial derivative w.r.t X but while keeping G fixed i.e. treated
OXE
as a constant or being "cconditooned upon" (indeed both G and Y depend on .p but the definition keeps G fixed while taking derivatives). Similarly, in Lemma 1 part 1, a is fixed (treated constant) in the derivative in the definition Oc/OE* and in part 2, k+1 fixed (treated as a constant) in the derivative in the definition of f
Recalling some Notation for sake of completeness: We recall that x is the k-th layer embedding of node i. y; is the C-dimensional ground-truth label vector for node and ý; is the C-dimensional predicted score vector for node i. K total number of layers in the GCN. L, denotes the loss on the i-th node and L denotes the total loss summed over all nodes. dş is the embedding dimensionality after the k-th layer.
Proof of Lemma 1.1 We analyze cases
29

---

Published as a conference paper at ICLR 2022
Case 1 (k: K i.. final layer):
Recall that the predictions for node i are obtained
(WK+1)7 =KK Thus we have
dc ΣΣ
Oc, Dise
OWK+T
Die OW*+T
OEV
SC, = Dic by definition. If we let we K+1 denote the e-th column of the de C matrix WK++1 Now, Bfie then clear that the depends only on w k+ and x Thus, we have
Jisc
Ditc ow e = (x T
OWK+I
where e, is the e-th canonical vector in C-dimensions with 1 the c-th coordinate and 0 everywhere else. This gives us
OC
Ex
Die e (
OWK+1
NVV
CE|C]
Case 2 (k < K iee intermediate layers): We recall that X stacks all k-th layer embeddings as an N de matrix and X f(X*-1; E*) where E* denotes parameters (weights, offsets, scales) of the k-th layer. Thus we have
ac d
Oc Düsc Oieo 0
ΣΣ CEVOE
As before, ac 8ie Iie by definition and have
Obic
ΣΣ
de
Oie 0x
i2
FF
oxk OF ip
JEV pm
This gives us
dc OE
de
Oiee 0x
dR
ax OE
a(a @ X*) aE
= ΣΣ
Jic ΣΣ CE(C]
0Xk DE
NEV
JEV
jEV p=1
where used the definition of a in the second step and used "conditional" notation get the
third step. We reiterate that 0 implies that & fixed (treated as a constant) while taking the derivative. This "conditioning" is critical since a also depends on E* This concludes the proof.
BF a
Proof of Lemma 1.2: We consider cases yet again and Definition that tells us that
age
a Σ
Die
OX jp
iEV CE(C)
Case (k: K): Since 0 (WK+1) K know that die depends only x and wK-1 where
ag. as before, w K+ is the c-th column the matrix WKI This gives us 8x if í + j and K+I
Büc w K if i = j where wike is the (p, c)-th entry of the matrix WK+1 (or in other words, the BX pc
p-th coordinate of the vector wK+1,, This tells us that
ΣΣ
Σ
ip =
Dic axk
Oje
pet
iEV CE|O]
cE|C]
which gives us K G(W
Case 2 (k < K): By Definition we have
- =
Ohe
=Σ Jie
des1 Oynn
0x
Jie ox
=
0x oxk ip
cE|C
iEV c
lEV q=1
30

---

Published as a conference paper at ICLR 2022
Rearranging the terms gives
A411 ΣΣ
0x OxP 3p
0x 0x JP
ΣE
Tiee ax
k+1 iq
Dic (EVCE(C)
JEV 9=1
q=1
where we simply used Definition in the second step. However, the resulting term simply 0(a ox
which conditions on, treats constant, the term a according to notation convention. This finishes the proof of part 2.
ax Jp al-1
C.2 STATEMENT OF CONVERGENCE GUARANTEE
The rate for full-batch updates, as derived below, is O (++ This fast rate offered by full-batch updates is asymptotically superior to the O rate offered by mini-batch SGD updates. This is due to the additional variance due to mini-batch construction that mini-batch SGD variants have to incur.
Theorem (IGLU Convergence (Final)). Suppose the lask loss function L has H H-soooth and architecture that offers bounded gradients and Lipschitz gradients as quantified below, then if IGLU in its inverted variant (Algorithm ( executed with step length n and a staleness count of T updates per layer in steps 7, 10 in Algorithm 2 then within T iterations, we must have.
1. |V212 s s (1/73) if model update steps are carried out on the entire graph in full-batoh with step length n O (1/T3) and (1).
2. V2 < so (1/VT) if model update steps are curried out using mini-batch SGD with step length 7) (1/VT) and O (T
It is curious that the above result predicts that when using mini-batch SGD, non-trivial amount of staleness (r = O (r)) as per the above result) may be optimal and premature refreshing of embeeddings/nccoplette gradients may suboptimal as was also seen in experiments reported in Table and and Figure 4 Our overall proof strategy is the following
1. Step 1: Analyze how lazy updates in IGLU affect model gradients
2. Step 2: Bound the bias in model gradients in terms of staleness due to the lazy updates
3. Step 3: Using various properties such as smoothness and boundedness of gradients, obtain
upper bound for the bias in the gradients in terms of number of iterations since last update
4. Step 4: Use the above establish the convergence guarantee
We will show the results for the variant of IGLU that uses the inverted order of updates as given in Algorithm 2 A similar proof technique will also work for the variant that uses the backprop order of updates. Also, to avoid clutter, will from hereon assume that normalized total loss function is used for training i.e. L = N Eiey l where = [V] is the number of nodes in the training graph.
C.3 STEP 1: PARTIAL STALENESS AND ITS EFFECT ON MODEL GRADIENTS
A peculiarity of the inverted order of updates is that the embeddings X*, k E [K] are never stale in this variant. To see this, we use simple inductive argument. The base case of X is obvious - is never stale since it is never meant to be updated. For the inductive case, notice how, the moment any parameter E is updated in step of Algorithm (whether by mini- batch SGD or by full-batch GD), immediately thereafter in step 8 of the algorithm, X is updated using the current value of x and E* Since by induction & never has a stale value, this shows that X is never stale either, completing the inductive argument.
31

---

Published as a conference paper at ICLR 2022
This has an interesting consequence: by Lemma we have
DC
xx") 1
(notice the addi-
DE
a+
a xx*
tional 1/N term since we are using normalized total loss function now). However, as
OE
is completely defined given E* a and X and by the above argument, X never has stale value. This shows that the only source of staleness in 0c is the staleness values of the incomplete ag
sc task gradient a², Similarly, it is easy see that the only source of staleness in JWRFT (XK)TG the staleness
The above argument is easily mirrored for the backprop order of updates where an inductive argument similar to the one used to argue above that X values are never stale in the inverted update variant, would show that the incomplete task gradient a values never stale in the backprop variant and the only source of staleness in ac would then be the staleness in the X values.
C.4 STEP 2: RELATING THE BIAS IN MODEL GRADIENTS TO STALENESS
The above argument allows us bound the bias in model gradients as a result of lazy updates. To avoid clutter, we will present the arguments with respect to the E parameter. Similar arguments would hold for the WK+ parameter as well. Let ā" aaah denote the stale and actual values of the incomplete task gradient relevant to E Let
dc DE
a(a" be the stale gradients used by BE a
IGLU in its inverted variant to update E* and similarly let
Dc ox be the true gradient 8F
DE
a
that could have been used had there been no staleness.
We will abuse notation and let the vectorized forms of these incomplete task gradients be denoted by the same symbols i.e. we stretch the matrix ax E R Nxxx xdy into a long vector denoted also by a E N-d, Let dim dim(E*) denote the number of dimensions in the model parameter E (recall that E can be a stand-in for weight matrices, layer norm parameters etc used in layer A of the GCN). Similarly, we let 3p E (Rdim(E") .j E [N],p E [dx] denote the vectorized form of the gradient ax and let t E R N.d, x xdim(E*) denote the matrix with all these vectors Zj,, stacked up.
aE
As per the above notation, it is easy to see that the vectorized form of the model gradient is given by
dc
) t Eddim B*)
O
N
The 1/N term appears since using normalized total loss function. This also tells that
V(a+ (Z+((T) - a+)
l k
m (7h)
ac
(2)
OE
0E 1
N
N
where mmax (Z*) is the largest singular value of the matrix Z
STEP 3: SMOOTHNESS AND BOUNDED GRADIENTS TO BOUND GRADIENT BIAS C.5
The above discussion shows how to bound the bias in gradients in terms of staleness in the in- complete task gradients. However, to utilize this relation, we assume that the loss function L is H-smooth which is a standard assumption in literature. We will also assume that the network offers bounded gradients. Specifically. for all values of model parameters Ek k [K], W K+ we have
|G||2 1
xx D
ac og
1
ax*+1 ox*
12" | < B. For sake of simplicity, will also assume the
same bound on parameters e.g.
[ S B. Assuming bounded gradients and bounded parameters also standard in literature. However, whereas works such as Chen et al. (2018a) assume bounds on the sup-norm i.c. Loo norm of the gradients, our proofs only require an Le norm bound.
We will now show that the model parameters Et k E [K], W undergo gradient updates to their new values E* A [K], WK+1 and the amount of travel is bounded by 0... A E*
then we have |at - S I where a* l are the incomplete task gradients corresponding to
32

---

Published as a conference paper at ICLR 2022
respectively old and new model parameter values and depends various quantities such the smoothness parameter and the number of layers in the network.
Lemma (par 2) tells us that for the final layer, we have a G(W well for any
k < K, we have a a(a*+ (xa++ox****
We analyze this using inductive argument.
oX
a++
1. Case 1: h K (Base Case): In this case we have
a a = =(( G(WR+I)T
=G G) + G(WK+1- WK+1
Now, the travel condition tells us that - WK+1 r. boundedness tells us that
WK+1 G 2:
- B. Also, since the loss function is H-smooth, the task gradients are
2
H H-Lipschitz which implies along with the travel condition that G G
S H Put
together this tells us that
a a 11, SH
telling us that IN S (H
2. Case 2: k < K (Inductive Case): In this case, let X and X denote the embeddings with respect to the old and new parameters respectively. Then we have
at a a(ātt 2 x
a(a 2 x
0x*
0X*
a++1
a++
0 X
aa o X
0
0X*
a++1
(P)
+ 0(a k+1 +1 o {
aaa o X
08*
0X
a++1
(Q)
x++1 S Je+1 r and bounded gradients tells us la k+1
By induction we have
S B giving us [l(P)]l2 S T2+1 To analyze the term [I(Q)]l recall that have X f(X*; F*+1) and since the overall task loss is H smooth, must be the function f. Abusing notation to let H denote the Lipschitz constant of the network gives us 8+
0x++1 0x*
x S r. Then we have
0(X++1)
0x
0xk (X"; ;x
08
=xxx;; ENt1) (x F+tl)++ ( f( ( - f'(x;; Fh+11
(M)
(N)
Applying smoothness, we have |[(M)]| S H2 as well as |[(N]l, S H rr. Together
with bounded gradients that gives us |a ++1 ||, < B, we have [1(2)]2 S BH(H + 1) T.. Together, we have
a a+
B(H 1) 1++1) rr
telling that J S B(H + Te+1))
The above tells us that in Algorithm 2 suppose the parameter update steps ie. step and step 10 executed by effecting mini-batch SGD steps else full-batch GD steps each time, with
33

---

Published as a conference paper at ICLR 2022
step length 17, then the amount of travel in any model parameter is bounded above by TnB i.e. 6 E S TyB and so on. Now, incomplete task gradients a are updated only after model parameters for all layers have been updated once and the algorithm loops back to step 6. Thus, Lipschitzness of the gradients tells us that the staleness in the incomplete task gradients, for any E [K], upper bounded by
| -o--aall
a²112 S Tm- IB,
ax 12
where we take I max45K Is for sake of simplicity. Now, since
I B gradients
0B*
bounded, we have maxx (Z*) S N. dgB. Then, combining with the result in Equation 2 gives us
dC O
S TM IB2dg
OF
2
Taking in contributions of gradients of all layers and the final classifier layer gives us the bias in the total gradient using triangle inequality
VC VVc-vcl S
dC
dc
dC
OC ØWK+I
S.. IB2 dmax (K + 1),
OE
O
aWK+I
KE(K]
where dmax = maxkek da is the maximum embedding dimensionality of any layer.
C.6 STEP 4 (I): CONVERGENCE GUARANTEE (MINI-BATCH SGD)
Let us analyze convergence in the case when updates are made using mini-batch SGD steps 7, 10 of Algorithm 2 The discussion above establishes an upper bound on the absolute bias in the gradients. However, our proofs later require a relative bound which we tackle now. Let us decide to set the step length 77 1 for some constant C > 0 that will be decided later and also set some value á
CVT
Then two cases arise
1. Case 1: The relative gradient bias is large i.e. om d3 (K + 1) Φ. || In this case we are actually done since we get
1B2dmas K +1)
V C1 S T.
CVT
i.e. we are already at an approximate first-order stationary point.
2. Case 2: The relative gradient bias is small i.c. тn- 1B2 dymn K + 1) < Φ. /L In this case we satisfy the relative bias bound required by Lemma (part 2) with Φ.
This shows that either Case happens in which means that Lemma 5 (part 2) keeps getting its prerequisites satisfied. If Case does not happen for T steps, then Lemma (part 2) assures that will arrive a point where
done else Case keeps applying which
2C(L" L*) + Ho²/C
E
S
(1 (1-6) VVT
where L L are respectively the initial and optimal values of the loss function which recall --smooth and o² is the variance due to mini-batch creation and we set 17 = CVT Setting
C = 2 2
tells us that within 7' steps, either we will achieve
2r 12 max (K + (C) L()
HHOT
or else we will achieve
20 /2 - L
|
E
(1- TTVT
34

---

Published as a conference paper at ICLR 2022
Setting T T (00--))11Pdds// (K+1)
VOSH<H
balances the two quantities in terms of their dependence
on T (module absolute constants such as Ø). Note that expected, the quantities 1, B, dmax K increase, the above limit on goes down i.e. we are able to perform fewer and fewer updates to the model parameters before refresh is required. This concludes the proof of Theorem for the second case.
C.7 STEP (II): CONVERGENCE GUARANTEE FRULL-BATTC GD)
In this case similarly have either the relative gradient bias to be too large in which case get
|V S Tn IB drmax K 1)
or else we satisfy the relative bias bound required by Lemma 5 (part 1) with ó = Φ. This shows that either Case happens in which case we are done or else Case 2 keeps applying which means that Lemma 5 (part keeps getting its prerequisites satisfied. If Case does not happen for T steps, then
Lemma (part 1) assures us that we will arrive at point where
2( L')
|V <
11(1 Φ)T
2( C*)
In this case, for given value of setting 1) iterations, we must achieve
gives us that within T
[1 [1-0)+ 11 dl (K+1)*T
I CI2 (2T(C -L") (K + +1)
T
In this case, it is prudent to set r = O (1) so as to not deteriorate the convergence rate. This concludes the proof of Theorem 4 for the first case.
C.8 GENERIC CONVERGENCE RESULTS
Lemma 5 (First-order Stationarity with a Smooth Objective). Let f θ - RR be an H-smooth objective over model parameters 0 E θ that is being optimized using gradient oracle and the following update for step length yy:
g 0 80-17 -n
Let be an optimal point i.e. 0* E arg minaee f().. Then, the following results hold depending on the nature of the gradient oracle:
1. If non-stochastic gradient oracle with bounded bias is used iee for some 6 E (0, for all t, we have g' = f0') + A where |A'll S 8 || ((t)) (0'))l Il and if the step length satisfies (1-8)
7) S 22(1+62) then for any T 0, for some S T must have
| = 2( (()))
n(1 8)T
2. If stochastic gradient oracle is used with bounded bias i.e. for some 8 E (0, for all t, we have E [' f0') + where - |
V (0') 1l2) as well as bounded variance i.e. for all t. we have E ll ( - A 11 < o² and if the step length
satisfies S 2555. as well as CVT for some C 0, then for any T 112
(1-6)
for some < T we must have
2C(f(00) f(0)) + Ho²/C
(1-8)V7
35

---

Published as a conference paper at ICLR 2022
Proof (of Lemma 5 To prove the first part, notice that smoothness of the objective gives
H | 0¹ 1
f(0 - f(0)) + (V 0 8¹) +
Since we used the update 0²+1 = 0- - g' and we have g' = V A', the above gives us
H1p² ||
5(0 - f(0') - n. (VS(0'), ".0(00))''>> g²>
= r(0') - 4 (V V + A + H1P²
(|VJ((0) + A111))
2
-(0') 7 | || - 7 (V)(0)) At) + Hn²
(IV + A' (1
2
Now, the Mauchy-Schwann inequality along with the bound on the bias gives us -1 (VS(0') A S
n98 [[ well [V + A12 - 2(1 + 62) VV Using these gives us
1( - [(0) 711 - d 71 + 8²) ||V/(0)))
S f(0') n11 -) 6) ||
2H(1+02) Reorganizing, taking a telescopic sum over all t. using f(OT-1) s(0") and making an averaging argument tells that since we set, for any T >> O, must be the case that for some t - T, we have
since we chose 1) S (1-5)
2(f(0)) f())))
|
7i1 - 8)T
This proves the first part. For the second part, we yet again invoke smoothness to get
+10 < (0') + (Q'())) 0 0¹)
H
| 1111-60 0¹ 1|2
Since we used the update 0 0¹ 1) g", , the above gives us
1( s f(0)) 77 (Vi(0',, g¹) + 2n² ||g"]]
=f(0') - 77 (Vi('', Hn² (|V + 1 V.(00) - A
- -H1? (v) +A' A', - v - A')
Taking conditional expectations on both sides gives
Hn² 2
E [1 |0|| < f(0') 7 f 112 n (V
(IV + 112
+ +0²)
Now, the Bauchy-Schwarz. inequality along with the bound on the bias gives us - (V) A') < v98 (0=)( well as (0*) 112 2(1 + 52) [[V) Using these and applying
total expectation gives us
Hn² + 2
E [ +1 }]]
< E [f()])] 711 - nH (1+ + 8²))
E ||
o²
< E [f(0']] 71 - 6)
Hn²
E v
02
2
2
where the second step follows since we set 17 - 2= Reorganizing, taking a telescopic sum
(1-8)
over all I, using 1(0 > s(0*) and making an averaging argument tells us that for any T > must be the case that for some t < T. we have
(() f(0))
Hno
E
11l - 8)T
1-8
However, since we also took care set 17 CVT we get
(C( + HO2 /C
E
[1
(1- (1-8)VT
which proves the second part and finishes the proof.
36


Reviews:
[{"review_id": "yufYaTDYden", "reviewer": "Reviewer_jiPr", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Overall, IGLU represents a novel method for achieving efficient GNN training. IGLU's idea is quite different from the common scalable GNN training methods, such as GraphSAGE and ClusterGCN.\nThe authors provide theories to show that the bias of IGLU is bounded.\nThe experimental results are promising as well.\n\nMain questions:\n1. The overall algorithms are still vague for me. I can understand the main results that we can use the previous layer's embeddings to approximate the exact backpropagated gradients. \nI appreciate the authors presenting Algorithm 1 and 2 as well. However, the exact computation is vague. For example, in the algorithms it said things like \"Compute G\", \"using Lemma 1 (1)\", but it's unclear how they are used.\n\n2. The evaluation setup is not rigorous. In Table 1, different GNN architectures are used to produce the results, which makes things unclear how much gain IGLU training is offering. \nI believe to show that IGLU is really model agnostic, at least one set of experiments should be made, where everything about GNN architecture is fixed, but only the training algorithms vary. \nFor example, you may refer to the paper \"Design Space for Graph Neural Networks\" on rigorously comparing different GNN design options.\nI believe only with rigorous controlled experiments, the results in Table 1 Figure 2 can assure the readers of the effectiveness of IGLU.\n\n3. In Table 1, the percentage of speedup is quite significant. Could the authors explain how they are computed? What is the baseline speed?\n\n4. Could the authors explain the rationale for IGLU outperforming full-batch GNN training? I believe full-batch training can offer exact gradients.\n\n5. In Figure 2, the results on \"OGBN-Proteins\" seem suspicious. It seems that without training, IGLU can already achieve much higher ROC AUC over other methods. I hope the authors explain the reasons behind it.\n\n\n", "summary_of_the_paper": "This paper introduces a new method, IGLU, that caches intermediate computations at various GCN layers.\nThis enables IGLU to perform lazy updates that do not require updating a large number of node embeddings during descent and offers much faster convergence without significantly biasing the gradients.\n\nOverall, this paper represents a novel solution towards efficient GNN training.", "summary_of_the_review": "Overall, I like the technical contributions made in this paper.\nMy concerns are:\n1. The algorithms are not clearly described, making it hard to understand the implementation of IGLU\n2. The evaluation setup is not rigorous, making the claims on the effectiveness of IGLU questionable", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "bpkUzSJ8XEG", "reviewer": "Reviewer_tDRJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Strengths\n* I like the idea of holding some variables constant in gradients and using stale computations to speed up computations. Somehow similar ideas have previously been used to, e.g., speed up the convergence of SGD (1) and SGLD (2).\n* Strong empirical results show that IGLU scales well and achieves SOTA.\n* The authors provide a convergence analysis of IGLU.\n\n# Weaknesses\n* In practice, many tricks are used in conjunction with GNNs. Some examples are long-range residual connections, BatchNorm, and virtual nodes. These are especially important to train deeper networks. It is not clear how IGLU could incorporate such tricks. Can the authors elaborate?\n\n\n1: https://proceedings.neurips.cc/paper/2013/file/ac1dd209cbcc5e5d1c6e28598e8cbbe8-Paper.pdf\n\n2: https://proceedings.neurips.cc/paper/2016/file/9b698eb3105bd82528f23d0c92dedfc0-Paper.pdf\n\n\n\n", "summary_of_the_paper": "The work proposes IGLU, an algorithm to scale-up GNNs using stale computations instead of traditional neighborhood sampling.\nIGLU has bounded bias if the loss and activation functions are smooth. Results on large-scale benchmarks show IGLU achieves SOTA and scales better than previous methods.", "summary_of_the_review": "I appreciate the use of stale gradients to speed-up backward computations in GNNs. In principle, the IGLU is architecture-agnostic and can be applied to many GNNs. Therefore, I am more inclined to acceptance than rejection.", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QA3fsPADZaK", "reviewer": "Reviewer_mKbp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The scalability issue of GNNs is challenging and an important research topic. IGLU is simple and the motivation is clear and intuitive.\n2. Compared to strong baselines, IGLU has better empirical performance in both accuracy and training time.\n3. Under certain assumptions, IGLU has non-trivial convergence guarantees, which is an advantage against baseline approaches.\n\n\nWeaknesses:\n1. Caching intermediate results to speed up GNN training has appeared in multiple prior works. The main difference is that this paper considers two variants: cache embeddings or gradients. However, I still think the technical novelty of IGLU is not significant. \n2. The GNNAutoScale method of Fey et al. uses similar ideas and make uses of stale embeddings to scale up the training of GNNs. From their experimental results, GNNAutoScale achieves much better performance compared to GraphSAITNT, Cluster-GCN, etc.  So, I think the authors should provides a more detailed discussion on the difference and connection between IGLU and GNNAutoScale. Moreover, empirical comparison between them would make the results more complete and convincing.\n", "summary_of_the_paper": "This paper studies tries to tackle the scalability challenge of training GNNs on large graphs. The authors propose IGLU, an architecture-agnostic method. IGLU caches intermediate computations and uses a lazy update strategy. Convergence analysis on IGLU is provided and empirical results show that IGLU has better performance than baselines such as GraphSAINT, Cluster-GCN, VR-GCN.\n", "summary_of_the_review": "Overall, this paper has some insights on tackling the scalability challenge training GNNs on large graphs. And IGLU is an effective method for scaling up GNN training and shows better empirical performance compared to well-known techniques. On the downside, the technical novelty is not significant. Moreover, I think authors should provide a more detailed comparison between IGLU and GNNAutoScale. ", "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": {}}]

Author rebuttal:

Meta-review: Overall the paper present the idea of caching and using stale information to update instead of sub sampling for speeding up graph convolution neural network. Reviewers liked the idea but also there were concerns about experimental comparisons.  In the rebuttal the authors did provide more evidence of comparison with other caching based and other relevant baselines. Overall the importance of scaling up GCNN and empirical results helped the paper cross the high bar.
Decision: Accept (Poster)