EXACT: Scalable Graph Neural Networks Training via Extreme Activation Compression
Authors: Zirui Liu
Kaixiong Zhou
Fan Yang
Li Li
Rui Chen
Xia Hu
Venue: ICLR 2022 Poster (2022)
Keywords: graph neural networks
scalable GNN training
quantization
random projection

Abstract: Training Graph Neural Networks (GNNs) on large graphs is a fundamental challenge due to the high memory usage, which is mainly occupied by activations (e.g., node embeddings). Previous works usually focus on reducing the number of nodes retained in memory.
In parallel, unlike what has been developed for other types of neural networks, training with compressed activation maps is less explored for GNNs. This extension is notoriously difficult to implement due to the miss of necessary tools in common graph learning packages. To unleash the potential of this direction, we provide {  an} optimized GPU implementation which supports training GNNs with compressed activations. Based on the implementation, we propose a memory-efficient framework called ``EXACT'', which for the first time demonstrate the potential and evaluate the feasibility of training GNNs with compressed activations. We systematically analyze the trade-off among the memory saving, time overhead, and accuracy drop. In practice, EXACT can reduce the memory footprint of activations by up to $32\times$ with $0.2$-$0.5\%$ accuracy drop and $10$-$25\%$ time overhead across different models and datasets. We implement EXACT as an extension for Pytorch Geometric and Pytorch. In practice, for Pytorch Geometric, EXACT can trim down the hardware requirement of training a three-layer full-batch GraphSAGE on \textit{ogbn-products} from a 48GB GPU to a 12GB GPU.

Published as a conference paper at ICLR 2022
EXACT: SCALABLE GRAPH NEURAL NETWORKS TRAINING VIA EXTREME ACTIVATION COMPRESSION
Zirui Liu', Kaixiong Zhou', Fan Yang', Li Li", Rui Chen²r, and Xia Hu Rice University, *Samsung Research America
(z1105, kaixiong zhou, 1y19, xia. chue@riceeede [1i. fil,, ccenn 1 [@samsung.com com
ABSTRACT
Training Graph Neural Networks (GNNs) on large graphs is fundamental chal- lenge due to the high memory usage, which is mainly occupied by activations (e.g., node embeddings). Previous works usually focus reducing the num- ber of nodes retained in memory. In parallel, unlike what has been developed for other types of neural networks, training with compressed activation maps is less explored for GNNs. This extension is notoriously difficult to implement due to the lack of necessary tools in common graph learning packages. To leash the potential of this direction, we provide an optimized GPU implementa- tion which supports training GNNs with compressed activations. Based on the implementation, we propose a memory--fficient framework called "EXACT", which for the first time demonstrates the potential and evaluates the feasibil- ity of training GNNs with compressed activations. We systematically analyze the trade-off among the memory saving, time overhead, and accuracy drop. In practice, EXACT can reduce the memory footprint of activations by up to 32x with 0.2-0.5% accuracy drop and 10-25% time overhead across different mod- els and datasets. We implement EXACT ric and Pytorch. In practice, for Pytorch Geometric, EXACT can trim down the hardware requirement of training three-layer full-batch GraphSAGE on ogbn-products from a 48GB GPU to a 12GB GPU. The code is available at https://githon com wwtmm/aariiitooooo Exactt....
extension for Pytorch Geomet-
INTRODUCTION
Despite Graph Neural Networks (GNNs) have achieved great success across different graph-related tasks, training GNNs large graphs is long-standing challenge due its extensive memory requirement (Kipf & Welling 2017: Zhang & Chen 2018 Cai et al. (2021b). The extensive memory consumption of GNN stems from its recursive neighborhood aggregation scheme, where each node aggregates the embeddings of its neighbors to update its new embedding at each layer. Thus, training an L-layer GNN requires storing all layers' intermediate node embeddings in GPU memory for computing the gradients, and this typically adds several times more memory than holding the node feature matrix (see Algorithm [ for detailed analysis). Hence, storing these node embeddings the major memory bottleneck for training GNNs on large graphs.
Most of the existing works towards this problem can be roughly divided into two categories. First, some works propose to train GNNs with sampled subgraphs instead of the whole graph at each step. this way, only node embeddings that are present the current subgraph will retained in memory (Chiang al. 2019: Hamilton al. 2017: Zeng et al. 2020 Zou et al., 2019 Chen ct al. 20188: Huang et al. 2018). Second, another line of works tries to decouple the neighborhood aggregation from prediction, either preprocessing step (Wu al. 2019 Klicpera et al.) 2018 Yu et al. 2020) or post-processing step (Huang et al. 2020). where the model is simplified as the Multi-Layer Perceptron (MLP) that can be trained with mini-batch data.
"Corresponding Author

---

Published as a conference paper at ICLR 2022
In parallel, another orthogonal direction is to store only the compressed node embeddings (i.e., acti- vations) in memory for computing the gradients. Recent works propose to quantize the activations in lower numerical precision (e.g., using 8-bit integer) during the forward pass (Chakrabarti & Mose- ley 2019 Fu et al. 2020] Chen et al. 2021a Evans & Aamodt 2021). This framework successfully trims down the memory requirement for training Convolutional Neural Networks (CNNs) by large margin, at the cost of additional time overhead and loss of accuracy. Ideally, the real-world usage requires that the training method should achieve a balanced trade-off among the following three as- pects: 1. Space. It should enable to train GNNs on large graphs using off-the-shelf hardwares, such as GPUs and CPUs; 2. Speed. The time overhead should be acceptable, ideally as small as possible; 3. Model Performance. The loss of accuracy should be acceptable, ideally as small as possible.
Although storing the compressed activations successfully saves the memory for CNNs, up to our knowledge, there is no existing work that extends this direction to GNNs and evaluates the men- tioned trade-off to analyze its feasibility. Despite the extension is conceptually straightforward, this direction is less-explored since it can be notoriously difficult to implement to fully leverage hardware potentials. This dilemma stems from the fact that the necessary tools for supporting this direction usually missing in common graph learning packages. For example, operations in popular graph learning packages only support casting tensors down to 8-bit integer on GPUs, significantly limiting the memory saving potential (Paszke et al. 2019 Fey & Lenssen 2019; Wang al., 2019). As result, previous GNN quantization works either emulate inference- time quantization via "simulated quantization" " (Tailor et al. 2021 Zhao al.) 2020), or are impractical to use GPUs for accelerating (Feng et al. 2020). To unleash the potential of this direction, we provide a space-efficient GPU im- plementation for supporting common operations in GNNs with compressed activations. Equipped with our implementation, this paper asks: To what extent can we compress the activations with both acceptable loss in accuracy and time overhead for scalable GNN training?
To answer the open question, we first explore two different types of compression methods. One "quantization" that compresses the activations into lower numerical precision. The other one called "random projection" (Achlioptas) 2001) that projects the activations into a low-dimensional space. Both these two simple strategies can achieve ncar-lossless accuracy at a non-trivial com- pression ratio. For example, the loss in accuracy is negligible (0.2%) even under the vanilla 2-bit quantization. However, we cannot further push forward the memory saving by these two methods, e.g., we cannot use numerical precision below 1-bit. Considering that the real- world graphs often contain hundreds of millions of nodes, our main goal is to trim down the memory consumption to the maximum extent among the three aspects, long as the other two are acceptable. We then nat- urally explore the direction of combining random projection and quantization, dubbed "EXACT", to aggressively maximize the memory saving. EXACT essentially applies random projection and quantization sequentially for compressing activations. Despite the superior memory saving, another following question is whether the combination brings significantly worse model performance and larger time overhead? Following the questions, we make three major contributions as follows:
We provide a space-efficient GPU implementation for training GNNs with compressed activations as an extension for Pytorch. Based on our implementation, we are the first one training GNNs with compressed activations and demonstrating its potential for real-world usage. EXACT can complement the existing studies, it can be integrated with most of existing solutions.
We propose EXACT, a simple-yet-effective framework which applies random projection and quantization sequentially on activations for scalable GNN training. We theoretically and experi- mentally show that applying random projection and quantization sequentially has "interaction" effect. Namely, from the model performance aspect, after random projection, applying quantiza- tion only has a limited impact the model performance. From the time aspect, EXACT runs comparably or even faster than quantization only.
Despite the simplicity, EXACT achieves non-trivial memory saving with both acceptable time overhead and loss in accuracy: EXACT can reduce the memory footprint of activations by up to 32x with roughly 0.5% loss in accuracy and 10 25% time overhead across models and datasets. We implement EXACT as an extension for Pytorch Geometric and Pytorch. For Pytorch Geometric, EXACT trims down the hardware requirement of training a fatl-batch GraphSAGE (Hamilton al. 2017) on oghn-products (Hu et al. 2020) from 48GB GPU to 12GB GPU.
2

---

Published as a conference paper at ICLR 2022
2 THE MEMORY CONSUMPTION OF GNNS
Background. Let g = (V,E) be an undirected graph with V = (01, mny) and & = (e1,-.. .e...,eeee -GEE) being the set of nodes and edges, respectively. Let X E R vixd be the node fea- ture matrix of the whole graph. The graph structure can be represented by an adjacency matrix A E M where A., = (v,, 1;)) & else A.,j = 0. In this work, we are mostly in- terested in the task of node classification, where the goal is to learn the representation h2 for all v E such that the label y, can be easily predicted. To obtain such a representation, GNNs follow the neighborhood aggregation scheme. Specifically, GNNs recursively update the representation of a node by aggregating the representations of its neighbors. Formally, the 7th layer of a GNN can
be written as h (1+1)_ UPDATE h 1 (uEN()) MsG ( (oOP,hh where h! is the representa-
tion of node v at the 1th layer. (v) denotes the neighboring nodes of node v, not including v itself. The full table of notations can be found in Appendix Table For node v, messages from its neighbors are calculated by the message functionMsG((). Then these messages using a permutation-invariie UPDATE(-). For example, the Graph Convolutional Network (GCN) (Kipf & Welling 2017) layer can be defined as
aggregated aggregation function D The aggregated features at v are updated by
H ReL.(AA(H!
where O is the node embedding matrix consisting of all nodes' embeddings at the h layer and O = x. ( is the weight matrix of the zth GCN layer. A = D AD 1 is the normalized adjacency matrix, where D is the degree matrix of A + J. We note that Á is usually stored using the sparse matrix format. For GCN layers, the message and the aggrega- tion function are fused into a Sparse-Dense Matrix Multiplication (SPMM D operation. Namely, AH SPMM A, H (4) (.)). Thus, the computation graph of Equation | can be written as
H (1+1) = ReLU SPMM Á, MM H (1) e )
(2)
where -M) is the normal Dense-Dense Matrix Multiplication. Equation 2 resembles how GCNs are implemented in popular packages (Fey & Lenssen 2019 Wang et al. 2019).
Here we analyze the memory consumption for the forward pass of GCN since most of the memory occupied during the forward pass. For the memory usage of the backward pass, a detailed analysis is given in Appendix C Specifically, for an I. layer GCN, suppose the hidden dimensions of layer 0, O..... I are the same, which are denoted as D. The forward pass of GCN layers is shown in Appendix C Algorithm ! For layer I, it saves the following four variables in memory. (1) the weight matrix e e DxD whose shape is independent to the graph size and is generally negligible. (2) the normalized adjacency matrix Á (in CSR format) whose space complexity is O(VV] + [E)) Note that it only needs to store one Å in memory which can be accessed by different layers. Thus, the memory consumption of Á is independent of the number of layers and is not the main memory bot- tleneck. (3) the intermediate result (() MM (U), (()) E RR|V For an L layer GCN, storing (J( .............. ((L-1)} has a DL space complexity, which is the main memory bottleneck. (4) the node embedding matrix ( E R R For an L layer GCN, storing (#) (L-11) has DL space complexity, which is also a main memory bottleneck. In this paper, we use the term "activation maps" to encompass H, J, and activation maps of other commonly used layers/operations such as BatchNorm, ReLU and Dropout.
METHODOLOGY
From the above analysis, the memory consumption of GCNs can be sigmificantly reduced by stor- ing only the compressed activations. As shown in Figure T due to the simplicity and small time overhead of quantization (Section 33T] and random projection (Section (32)) we first explore these two methods for compressing the activations of GNNs. We show that these two simple methods can
We note that the output of SPMM(-.) a dense matrix.
3

---

Published as a conference paper at ICLR 2022
Forward Pass
Ruldhddee
Forward Piss
Uicenaia Racavdd Inaver
Trav
Backword
Unnta doslli Menoes)
Moners
Papetie
H
Eccwacd
beconact
Excnico
Dackancs
V.KO
V
A
A
Prlectes
jmh
A
H
(a) GCN layers with quantized activations.
(b) GCN layers with randomly projected activations.
Figure 1:
The training procedure of GCN layers, where only compressed activations are stored in memory. For illustration convenience, ReLU is ignored. During the forward pass, each layer's accurate activations (H()) used to compute those for the subsequent layer. Then the accurate activations will be compressed into the compressed activations HIINT and H which overwrites the the accurate activations and is retained in the memory. During the backward pass, we recover the compressed activations back to decompressed activation ( ()) ) for computing the gradient.
bring moderate compression ratios with negligible loss in accuracy. However, the highest compres- sion rates of these two methods are limited by either hardwares or the accuracy drop. Motivated by GNNs endless demand on memory, we then explore the direction of combining quantization with random projection into one framework termed "EXACT" to aggressively maximize the memory saving (Section B.3). We show that random projection and quantization have "interaction" effect. That is, from the model performance aspect, after random projection, applying quantization only has limited impact on the model performance. From the time aspect, EXACT runs comparably or even faster than quantization only.
3.1 STORING QUANTIZED ACTIVATIONS
Inspired by ActNN (Chen et al., 2021a), shown Figure la we first explore the direction of compressing activation maps in lower numerical precision. Specifically, during the forward pass, each layer's s accurate activations (e.g., J! and (()) is used to compute those for the subsequent layer. Then the accurate activations will be quantized into the compressed activations (e.g., H and _!l with lower numerical precision, which overwrite the accurate activations and are retained in the memory. During the backward pass, we dequantize the compressed activations back full- precision (e.g., (1) and f("). Then the gradients are computed based on the dequantized acti- vations. We note that all operations (e.g., MM and SPMM are done in full-precision since most of the GPUs do not support operands with bit-width other than full-precision and half half-precision. For convenience, we use the term "precision" to present "numerical precision" in the following of this paper. Below we introduce the technical details of (de)quantization.
Specifically, each node embedding vector ( will be quantized and stored using b- bit integers. Let B 2b 1 be the number of quantization bins. The integer quantization can be expressed as
(!)
h
h FeeT
Quant(h!))
B7.
(1)
where - min(h!)) is the zero-point, n!!h max h min (1()) 3 is the range for h!!". and
L-7 is the stochastic rounding operation (Courbariaux et al. 2015). H in Figure la the matrix containing quantized (t) During the backward pass, each h will be dequantized as
R Dequant (h. r
((() ( / Z(
(4)
( in Figure is the matrix containing all dequantizzd embeddings (00) The following proposi- tion characterizes the effect of quantization, which is adopted from Chen et al. (022a).
4

---

with the Published as a conference paper at ICLR 2022
The above quantization and dequantization unbiased operations, ie.. B(h 1 G[Dequant(Quuuu Quant (h. ]]] = h.g and Var(h ( D
Proposition 1 (Details in Appendix E
6
From the unbiased nature of quantization illustrated in Proposition D the calculated gradient is also unbiased. The approach imposes extra noise (i.e., the variance term in Proposition 1 to the gradient during the backward pass. From Proposition [ the noise effect is rnveseelycoorelaan number quantization bins B. To evaluate how the noise affects the model performance, we train three popular GNN models, namely, GCN, GraphSAGE, and GAT, the ogbn-arxiv dataset (Hu cet al. 2020) with different precisions (Table T. The detailed experiment setting is elaborated in Appendix G.2 Here we emphasize that all these three models trained with full-batch data.
Table 1: The accuracy of GCN, GraphSAGE, and GAT trained on the ogbn-arxiv dataset with compressed activations storing in different precision. All results are averaged over ten random trials.
Model GCN
FP32 (Baseline)
INT8
INT4
INT2
INTI
72.07=0.16
72.06=0.29
71.96=0.26
71.93+0.20
01.68 71.34:0.24
GraphSAGE GAT
71.85
71.83=0.15
71.85=0.27
71.58:0.22
72.3540.12
72.39=0.14
72.3420.12
72.3540.12
72.17-0.12
Observations. For all three models, the loss in accuracy is negligible (Rs 0.2%) even using the vanilla 2-bit quantization. In contrast, for CNNs, adopting the vanilla INTI or INT2 quantization will cause a significant accuracy drop (usually > 5%) (Chen et al. 2021a 2020a). This observation be explained by the following mechanism. We show in Appendix E.4 that the approximation error will compound layer-by-laye during the backward pass. The layer-depth GNNs is much smaller than CNNs due to the over-smoothing problem, and hence GNNs much more noise- tolerant than CNNs. Our observation suggests that in practical scenarios, there is no need for an expensive sophisticated quantization approach (e.g., mixed precision quantization) as considered in previous works (Chen et al. 2021a Fu et al. 2020).
3.2 STORING RANDOMLY PROJECTED ACTIVATIONS
Here we explore the direction of random projection. The key idea is to project the activation maps into a low- diw-eimeniionll space that keeps the original information much possible. In this way, similar to the framework in Section 3.I we only need to store the dimension reduced activation maps in memory. Figure 1b illustrates the workflow of GCN layers. During the forward pass, each layer's accurate activations (e.g., 1) are used to compute those for the subsequent layer. Then the accurate activations will be projected into low-dimensional space, which can be expressed as:
(P(h h:!) 1.!RR. R.
Vign
where R E DxR is random matrix (R < D) which satisfies E[RRT] = H
V
pmjj
the matrix containing all projected node embeddings hope-- In this paper. R is set as the normalized Rademacher random matrix (Achlioptas) (001)) due its low sampling cost (detailed introduction
Appendix D). After projection, we store only H (1) in memory, and hence the compression ratio pmj
D During the backward pass, the projected node embeddings are inversely transformed by
( IRP (!) (pec)
h 1po
(1)
R
(6)
where IRP(-) is the inverse projection operation. ( H RR E V is the recovered
(1) proj
activation map containing all a The following proposition shows the effect of random projection.
Proposition 2 (Proof in Appendix Ep The above RP and IRP are unbiased operations, i.e.
E( (1) = (RIP = H H For each (1) in H we have Var(h D
( 1
From the unbiased nature of random projection given in Proposition the calculated gradient also unbiased. The approach here also only imposes extra variance to the calculated gradient, where the variance linearly seales with the & ratio. To quantitatively study the effect of the extra variance in scenarios of practical interest, we follow the same setting in Section 3.1 and show the performance
5

---

Published as a conference paper at ICLR 2022
Table 2: The test accuracy of GCN, GraphSAGE, and GAT trained on the ogbn-arxiv dataset with randomly projected activations. All results are averaged over ten random trials.
Model
Full- Dimension (Baseline)
= 2
=4 4
D =8
16
GCN
12.07=0.16 71.85=0.24 72.35=0.12
71.87=0.15
71.72+0. 18
71.71#0.22
71.55+0013
GraphSAGE GAT
71.58=0.28
71.46=0.28
71.29=0.25
71.13+0.28
72.18=0.14
72.15+0.10
72.02+0.12
71.89=0.12
of GCN, GraphSAGE, and GAT trained on the ogbn-arxiv dataset with different D ratios in Table
2
Observations. We make main observations: (1) For all three models, the loss in accuracy tends to range from negligible (+= 0.2%) to moderate (+e 0.5%) when & s 8. (2) Under the same compression ratio, the quantization better than random projection terms of the loss in accuracy (e.g., compare the D 16 result in Table with the INT2 result in Table R
3.3 EXACT: COMBINING RANDOM PROJECTION AND QUANTIZATION
We experimentally show that GNNs are noise-tolerant to inaccurate activations compressed by quan- tization and random projection. However, the highest compression ratio of these two methods is limited. The precision cannot be less than 1-bit for quantization and D. cannot surpass eight for random projection due to large accuracy drop. However, GNNs' demand since real-world graphs can contain hundreds of millions of nodes and the graph size is ever grow- ing. Motivated by this fact, we try further push forward the memory saving as long as the loss of accuracy and the time overhead are both acceptable. We explore the direction of combining these two methods into one framework termed "EXACT" to maximize the memory saving. Specifically, we compress the activations and store only h = Quant(RP(h." )) in memory during the forward pass. During the backward pass, the node embedding is recovered as h IRP(Dequant (h. )). EXACT can achieve a superior compression ratio, e.g., the compression ratio of EXACT is roughly 128x if D and the precision is INT2. R
memory is endless
However, one practical question whether the variance will explode, leading to significantly worse performance when applying random projection and quantization sequentially. Here we try answer the above question both theoretically and experimentally. Below we first theoretically show that after applying random projection, the quantization range of projected node embeddings is bounded.
Proposition 3 (Proof in Appendix E} For each projected node embedding h Ugend
(!)
= RP(h!)) =
(1) R. for Ve >> 0, by choosing =|hh,) (2)
1|11!"112// 2ln(2R/e) we have P( S 8) 2 1
From Proposition after projection, the maximal absolute value among weights in to is bounded. (1)
Following the fact that the quantization range Feprej max ( } min yoo
(1) S 2 h 1
(I)
Tygeo is also bounded. Recall that the variance of quantization scales with Applying random projection and quantization sequentially will not lead to the variance explosion.
(1)
"pros!
(Proposition
B
We also experimentally visualize the in- finity norm of projected embeddings in Appendix E Figure 4 The infinity norm of pro-
GCN (Full Batch)
D: 35
Hor TorAnaary Ng
72.0
jected embeddings may be even less than those of original embeddings when R is larger than threshold (R = 0.5D in Figure 4. Thus, the extra variance is expected to be dominated by random projection, and hence the loss in ac- curacy is largely determined by the D ratio. We also experimentally investigate the effect of EXACT by plotting the test accuracy against each quantization precision and the D ratio.
71.8
Dok
72.6
hadiic:
7144
71.2-
INT4
DP92
Quantzatio
Figure 2: The performance of EXACT is mainly determined by the R D ratio of random projection.
Due to the page limit, we only present one representative result in Figure 2 namely, training GCNs on ogbn-arxiv with EXACT. More similar results be found in Appendix [.1 Here we do not

---

Published as a conference paper at ICLR 2022
consider INTI precision since its model performance drop is already near 0.5%. We summarize two main observations. First, the performance of EXACT is largely determined by the D ratio of R
random projection. Second, when R < 8, the loss in accuracy generally ranges from R 0.2% to R 0.5%, regardless of the quantization precision.
System Implementation. In EXACT, each operation (e.g,, SPMM, ReLU, and BatchNorm) is re- implemented with different configurations using CUDA kernels. For example. BatchNorm only sup- ports quantization, while random projection is not applicable to it. Since Pytorch only supports precision down to INT8, we convert quantized tensors into bit-streams by CUDA kernels to maxi- mize the memory saving. The configuration and implementation details are given in Appendix F
4 RELATED WORK AND DISCUSSION
Due to the page limit, we briefly review and discuss the relationship between existing works and EXACT. A more comprehensive discussion can be found in Appendix B Existing works can be roughly divided into scalable/effcient GNN inference and scalable GNN training according to the problem they try to solve. Almost all previous GNN quantization works try to solve the first problem, which much simpler than the second problem that EXACT tries address. Specifically, most of them try to enable the usage of low precision integer arithmetic during inference (Tailor et al., 202T Zhao et al. 2020) by simulating the quantization effect, which may even increase the memory consumption during training. Feng et al. (2020) tries to address the second problem by proposing a heterogeneous quantization framework which assigns different bits to node embeddings in each layer. However, this framework is impractical on off-the-shell hardwares. For scalable GNN training methods, EXACT is orthogonal to most of them, including distributed training (Zheng et al. 2020bb Jia et al.] 2020 Zhu et al., 2019 Wan et al. 202I), subgraph sampling (Hamilton et al. 2017 Zeng ct al. 2020; Chiang et al. 2019). and historical embedding- based methods (Fey et al. 2021
We
discuss the potential benefit of integrating EXACT with them in Appendix B
5 EXPERIMENTS
The experiments are designed to answer the following research questions. RQ1: How effective is EXACT in terms of model performance different compression rates (Section 5. ? RQ2: Is the training process of deeper GNNs also robust to the noise introduced by EXACT (Section 5.1 RQ3: How sensitive is EXACT to its key hyperparameters (Appendix I.4 ? RQ4: What the running time overhead of EXACT (Section 5.2 RQ5: Is the convergence speed of GNNs impacted by EXACT (Appendix L RQ6: To what extent can EXACT reduce the hardware requirement for training GNNs on large graphs (Section 5
Datasets and Models. To evaluate the scalability of EXACT, we adopt five common large-scale graph benchmark datasets from different domains. Namely, Reddit, Flickr, Yclp, ogbn-arxiv, and ogbn-products. We evaluate EXACT under both the mini-batch training and full-batch training set- tings. In the mini-batch training setting, we integrate EXACT with two ofate-of-the-an -art subgraph sampling methods, namely Cluster-GCN (Chiang et al. 2019) and GraphSAINT (Zeng et al. (2020). In the full-batch training setting, we integrate EXACT with three popular models, including two commonly used shallow models, namely GCN (Kipf & Welling 2017) and GraphSAGE (Hamilton) al. 2017). and one deep model GCNII (Chen et al. 2020b). To avoid confusions, GCN, Graph- SAGE, and GCNII are both trained with the whole graph at each step. For fair comparison, we use the mean aggregator for GGE, Cluster-GCN, and GraphSAINT throughout the paper. Details about the hyperparameters of models and datasets can be found in Appendix G.
Hyperparameter Settings. From Section 3.3 we show that the performance of EXACT is largely determined by the 22 ratio of random projection, and the model performance drop with INT2 quan- tization is negligible. Thus. to balance the accuracy drop and memory saving ratio, we adopt INT2 precision with different D ratios for EXACT. Specifically, EXACT (INT2) indicates that it only applies 2-bit quantization to the activation maps of all applicable operations (see Table 8). EX- ACT(RP+NN2)) indicates that it applies random projection followed by 2-bit quantization to the activations of all applicable operations. We perform a grid search for R ratio from (2, 4, 8). De-
D tailed R configuration for EXACT(RP+INT2) can be found in Table 12
7

---

Published as a conference paper at ICLR 2022
Table 3: Comparison on the test accuracy/Fl-miern and memory saving on five datasets. The hard- ware here is a single RTX 3090 (24GB). "Act Mem." is the memory (MB) occupied by activation maps. "OOM" indicates the out-of-memory error. Bold faces indicate that the loss in accuracy is negligible (<x 0.2%) or the result is better compared to the baseline. Underline numbers indicate that the loss in accuracy moderate ( 0.5%). All reported results are averaged over ten random trials.
DodEs
25K
19K
TIK
18%
23M 61 9M1 oghe- productt
* cllee
11.M
<SOK
79M Yolp
12M
Moddi
Mathel
Reddz
Pürker
oyhi-
Men.
Fl-niom
Men.
Mem
Choder- OCN
EXACTIINT)
Baseline
95.58
9562-0
145/1xx)
2
#141-3147
(150
16.51100
6M8--111 14
63.0 15
29:311
417.3%)
7KA2-0 26
7H 7847760.4 40
(.40)
95.5240077
LA (10.44))
20.313021
09
23
30.3k)
77.8569228 26
(26X)
Gragi- SAINT
EXACTINTE)
Braciin
05
66 66-07781
4431113
7861144
633K 63
0377:1114
4.317
3SSTER
71.00 10:30
71.N66 15
(1.00
78
S1STIXI
EXACTARF-INTT
55.9000066
(12.2.)5)
50.550017
63 19
(...2)))))
71.4430.15 15
(2x))
78 28.900041
(1.5
Brscling
95399
1029 (1X0
53.663114
576.8
40.2 27
(19)
CCN
EXACTINTS:
(72
(0
48.30 34
72.440:21
EXACTIRP INT2
95.900008
67.45
22.90:3122
(2.50
39.5ee11 55
427 (16x)
21.076016
30.2 (24.3-)
Gragg-
SAGR
EXACT/RF-INT
EXACTIONTE
Braching
96,000055
9634
15.55
7L.7 (21.3k)
49.00.3
(2..23
01
61 61.5001112 12
690 (0.33)
466.5 (15x)
71.7140 35
71,3356.20 26
7L85
(12.99
30.5 (26.5k)
196,211
7887680013
TX 78
OUM
1144
572
Biseiig
5550
003
00M
21
[4409]11
OCNI
EXACTINTSS
96.6 10.06
4455
(15-915
64.9900
2316
72.88 10:45
899 (10+3
EXACTIRP INTZ
565L:0009
(29.6)
53.9689155
(BL.X)
6401-1111
1649
73.07
451.2 451.2 (1Ex)
Tranin theoateet iqpeet
Trurrr booughght (gpodheg
16
OCN
OCN
GraRBACE Rucdit
ogbu-arxiv
Yelp
Training throughput comparison on a single RTX 3090 (24GB) GPU (higher is bet- ter). The time overhead of EXACT is roughly 12% 25%. We diseuss about swapping and gradient checkpointing in Appendix 1.2
Figure 3:
5.1 TRADE-OFF BETWEEN SPACE AND MODEL PERFORMANCE
To answer RQ1 and RQ2, we first analyze the trade-off between the model performance and mem- ory saving. Table 3 summarizes the model performance and the memory footprint of the activation maps. Besides the memory usage of activation maps, a detailed analysis about the overall memory saving ratio is provided in Appendix H We make two main observations.
First, EXACT aggressively reduces the memory footprint with < 0.5% loss in accuracy. From Table EXACT (INT2) reduces the memory footprint of activation maps from 7x to 16x, with negligible loss in accuracy (~ 0.2%) in almost all experiments. EXACT (RP+INT2) generally reduces the memory footprint activation maps from 10x to 32x, and the loss in accuracy tends to range from lossless (0.0%) to moderate (== 0.5%) Although EXACT can aggressively compress the memory usage of activations associated with MM and SPMM by up to 128x, the compression ratio for other operations usually cannot surpass 32x (e.g., the activation maps of ReL.U and Dropout take exact one bit to store, see Appendix F). As a result, the overall compress ratio is pulled down. We show in Appendix H that the measured compression ratio is consistent with the theoretical one.
Second, the training process of deeper models is also robust to extremely compressed acti- vations. As we analyzed in Appendix(E.] the vanilla quantization and random projection obtain unreasonable good performance might because the commonly used GNNs shallow. Thus, one open question is that, to what extent can deeper GNNs robust to extremely compressed activation maps (RQ2)? The ablation study of GCNII in Table tries to experimentally answer this question. The training process of deeper GNNs (up to 16-layer, see Table [7] is also robust to the noise intro- duced by the extremely compressed activations, with up 32x less memory footprint of activation maps. We note that building deeper GNNs is still an open direction due to the over-smoothing and the extensive memory consumption problem (Oono & Suzuki, 2019 Li et al.) 2021 Chen et al. 2020b). From the practical usage perspective, our GCNII ablation study indicates that EXACT may enable to train deeper GNNs on large graphs with minimal loss in performance.
Bl
The regular training raises O0M error. The result is obtained using the automated mixed-precision training forch.euda.amp).
8

---

Published as a conference paper at ICLR 2022
D To answer RQ3, we present the sensitivity study of EXACT (RP+INT2) to nt ratio in Appendix L.4
In general, the model performance drop of EXACT (RP+INT2) increases with the D π
ratio. In
summary, when & πr 8, the loss in accuracy of EXACT (RP+INT2) is S 0.5% in roughly two-third of experiments and 1% almost all experiments.
5.2 TRADE-OFFS BETWEEN SPACE AND SPEED
To answer RQ4, we compare the training throughput of EXACT with the baseline using a single RTX 3090 (24GB) GPU. Figure 3 shows the results among EXACT with different configurations and the baseline (see Table for detailed package information). We make two main observations.
First, the overhead of EXACT (LNT2) is roughly 12% ~ 25% The overhead of EXACT (INT2) comes entirely from quantization. We note that EXACT (INT2) adopts vanilla integer quantization with negligible loss in accuracy, which has the lowest overhead among all quantization methods. So- phisticated quantization strategies (e.g., mixed precision quantization and non-uniform quantization) further increase the time overhead, because they require an extra search process to find precision or
quantization step for each layer/sample (Chakrabarti & Moseley 2019 Fu et al. 2020
Chen al.
2021a). From Figure 3 the overhead of EXACT is roughly 12%
25%.
Second, the running speed of EXACT (RP+INT2) is comparable even faster than quantiza- tion only. The above counter-intuitive observation can be explained by the following mechanism. Although random projection introduces two extra matrix multiplication operations, the total num- ber of elements to be quantized is R that quantization the main bottleneck, compared to EXACT (INT2), EXACT (RP+INT2) achieves roughly twice overall compression ratios with a comparable or even smaller time overhead.
D times less than directly quantizing the activations. Considering
RQ4 focuses on the actual running speed measured by the hardware throughput. Here we inves- tigate the convergence speed from the optimization perspective (RQ5). To answer RQ5, due to the page limit, we present the training curve of models trained on Reddit dataset with EXACT in Appendix 1.3 The converge speed here is measured by the number of epochs it takes reach certain validation accuracy. In summary, the convergence speed of EXACT is slightly slower than the baseline, with limited impact on final accuracy.
5.3 ABLATION STUDIES
Train full-batch GraphSAGE on ogbn-producee using a GPU with 11GB memory.
Table shows that EXACT reduces the memory foot- print of activation maps by up to x2x. However, as an- alyzed in Appendix [ besides the activation maps, in- put data (ineluding feature matrices adjacency matrix A, and labels), activation gradients also occupy mem- ory in the full-batch training. For ogbn-produee the input data occupies 4.7GB (see Appendix HH.. From the OGB leader-board, training a full-batch GraphS re- quires GPUs with at least 48GB memory. We note that EXACT can be integrated with AMP (see Appendix (RP+INT2) with 1 π7 = 4, we successfully train full-batch GraphSAGE on ogbn-products on single GTX 1080 Ti with 11GB memory, with moderate loss (== 0.5%) in accuracy (Table 4h.
Table 4: The test accuracy of full-batch GraphSAGE trained oghn-products using a single GTX 1080 Ti (11GB).
Methods AMP
Accuracy OOM 78.28=0,18
EXACTIRP+INT2) AMP
F to further squeeze out the memory. To answer RQ6, by integrating AMP and EXACT
CONCLUSION AND FUTURE WORK
In this paper, we propose EXACT, a simple-yat-effecttve framework for training GNNs with com- pressed activations. We demonstrate the potential of EXACT for the real-world usage by system- atically evaluating the trade-off among the memory-saving, time overhead, and accuracy drop. We show that EXACT is orthogonal most of the existing solutions and discuss how EXACT can be integrated with them in Appendix [ Future work includes (1) evaluating EXACT under multi-GPL settings for distributed training: (2) combining EXACT with historical embedding-based methods; (3) combining EXACT with memory-efficient training systems, such as swapping.

---

Published as a conference paper at ICLR 2022
7 ACKNOWLEDGEMENT
We would like to thank all the anonymous reviewers for their valuable suggestions. Thank all the members of Samsung Research America advertisement intelligence team for your feedback, and everyone who has provided their generous feedback on this work. This work is, in part, supported by NSF LIS-1550744 The views and conclusions contained in this paper those of the authors and should not be interpreted as representing any funding agencies.
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. Tensorflow: A system for large- scale machine learning. In 12th {USENIX} symposium on operating systems design and imple- 2016.
mentation ({OSDI) 16), pp.
Dimitris Achlioptas. catabase-friiende random projections. In Proceedings of the twentieth ACM SIGMOD-SIGACT.SIGAART symposium on Principles of database systems, pp. 274 281-281, 2001.
Friedrich L Bauer. Computational graphs and rounding error. SIAM Journal on Numerical Analysis, 11(1):87-96, 1974.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311, 2018.
Chen Cai, Dingkang Wang, and Yusu Wang. Graph coarsening with neural networks. arXiv preprint 102.v:2102.011300 2021a.
Tianle Cai, Shengjie Luo, Keyulu Xu, Di He, Tie-yan Liu, and Liwei Wang. Graphnorm: A prin- cipled approach to accelerating graph neural network training. In International Conference on Machine Learning. pp. 1204-1215. PMLR, 2021b.
Ayan Chakrabarti and Benjamin Moseley. Backprop with approximate activations for memory- efficient network training. Advances in Neural Information Processing Systems, 32:2429-2453 2019.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In International conference on machine learning. PMLR, 2017.
Jianfei Chen, Yu Gai, Zhewei Yao, Michael W Mahoney, and Joseph E Gonzalez. A statistical framework for www-bitwidth training of deep neural networks. arXiv preprint arXiv:2010.1422 2020a.
Jianfei Chen, Lianmin Zheng, Zhewei Yao, Dequan Wang, Ion Stoica, Michael W Mahoney, and
Joseph E Gonzalez. Acton: Reducing training memory footprint via 2-bit activation compressed training. In International Conference on Machine Learning. PMLR, 2021a.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. arXiv preprint 1001. 2018.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph con- volutional networks. In International Conference on Machine Learning, pp. 1725-1735. PMLR, 2020b.
Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. A unified lottery ticket hypothesis for graph neural networks. In International Conference on Machine Learning, pp. 1695-17066 PMLR, 2021b.
Tianqi Chen, Bing Xu, Chiyuan Zhang, and Carlos Guestrin. Training deep nets with sublinear memory cos6, arXiv preprint arXiv:1604.0617 2016.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 257-266, 2019.
10

---

Published as a conference paper at ICLR 2022
Matthieu Courbariaux, Yoshua Bengio, and networks with binary weights during propagations. In Advances in neural information processing systems. pp. 3123-3131, 2015.
David. Binaryconnect: Training deep neural
David Evans and Tor Aamodt. AC-GC: Lossy activation compression with guaranteed con- vergence. In Thirty-Fiiph Fiith Conference Nearal Information Processing Systems, 2021. URL
https:///pen
ew, .ee wtt.reewweee/ootm/ieeiee
R David Evans, Lufei Liu, and Tor M Aamodt. Jpeg-act: accelerating deep learning via transform- based lossy compression. In 2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA), pp. 860-873 873. IEEE, 2020.
Boyuan Feng. Yuke Wang, Xu Li, Shu Yang, Xueqiao Peng, and Yufei Ding. Sgquant: Squeezing the last bit on graph neural networks with specialized quantization. In 2020 IEEE 32nd International Conference on Tools with Artificial Intelligence (ICTAI). pp. 1044-1052. IEEE, 2020.
Matthias Fey and Jan Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Matthias Fey, Jan E Lenssen, Frank Weichert, and Jure Leskovec. Gnnautoscale: Scalable and pressive graph neural networks via historical embeddings. International conference on machine learning, 2021.
Fangcheng Fu, Yuzheng Hu, Yihan He, Jiawei Jiang, Yingxia Shao, Ce Zhang, and Bin Cui. Don't waste your bits! squeeze activations and gradients for deep neural networks via tinyscript. In International Conference on Machine Learning, pp. 3304-3314. PMLR, 2020.
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025-1033 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00687 2020.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin R Benson. Combining label propagation and simple models out-performs graph neural networks. In International Conference on Learning Representations, 2020.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. Advances in Neural Information Processing Systems, 2018
Paras Jain, Ajay Jain, Aniruddha Nrusimha, Amir Gholami, Pieter Abbeel, Kurt Keutzer, Ion Stoica, and Joseph E Gonzalez. Checkmate: Breaking the memory wall with optimal tensor rematerial- ization. arXiv preprint 19X00:19/0 2019.
Zhihao Jia, Sina Lin, Mingyu Gao, Matei Zaharia, and Alex Aiken. Improving the accuracy, scala- bility, and performance graph neural networks with roc. Proceedings of Machine Learning and Systems, 2:1 2:187-198, 2020.
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irreg- ular graphs. SIAM Journal on scientific Computing, 20(1):359- 392,, 1998.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization, arXiv preprint arXiv:1412.6980, 2014.
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2017. URL https://
openreview net www.:oooon.dddsSSSeeeee.
Marisa Kirisame, Steven Lyubomirsky, Altan Haan, Jennifer Brennan, Mike He, Jared Roesch, Tianqi Chen, and Zachary Tatlock. Dynamic tensor rematerialization. arXiv preprint arXiv:2006.09611 09666, 2020.
11

---

Published as a conference paper at ICLR 2022
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2018.
Guohao Li, Matthias Müller, Bernard Ghanem, and Vladlen Koltun. Training graph neural networks with 1000 layers. arXiv preprint arXiv:2106.0747 2021.
Jiayu Li, Tianyun Zhang, Hao Tian, Shengmin Jin, Makan Fardad, and Reza Zafarani. Sgen: A graph sparsifier based graph convolutional networks. In Pacific-Asia Conference Knowledge Discovery and Data Mining, pp. 275-287 Springer, 2020.
Elan Sopher Markowitz, Keshav Balasubramanian, Mehrnoosh Mirtaheri, Sami Bryan Perozzi, Greg Ver Steeg, and Aram Galstyan. Graph traversal with tensor functionals: A aeea--lgorithm for scalable learning. In International Conference Learning Representations, 2021. URL
Chen Meng, Minmin Sun, Jun Yang, Minghui Qiu, and Yang Gu. Training deeper models by gpu memory optimization on tensorflow. In Proc. of MI. Systems Workshop in NIPS, 2017.
Paulius Micikevicius, Sharan Narang, Jonah Alben, Gregory Diamos, Erich Elsen, David Garcia, Boris Ginsburg. Michael Houston, Olcksii Kuchaiev, Ganesh Venkatesh, et al. Mixed precision training. arXiv preprint arXiv: 2017.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. arXiv preprint arXiv:1905.10994 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32: 1026-8037, 2019.
Aashaka Shah, Chao- Yuan Wu, Jayashree Mohan, Vijay Chidambaram, and Philipp Krähenbühl. Memory optimization for deep networks. arXiv preprint arXiv:2010.14550 2020.
Daniel Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM
Journal on Computing, 40(6):111311266, 2011.
Shyam Anil Tailor, Javier Fernandez-Maquuee and Nicholas Donald Lane. Degree-quant: Quantization-aware training for graph neural networks. In International Conference Learning Representations, 2021. URL htR/:/aaa//peeeeeeeee...cc wootee////oiiaaoioooo Bat.r//eeee.eeeeeeeee..tttttaaaa
Dingwen Tao, Sheng Di, Zizhong Chen, and Franck Cappello. Significantly improving lossy com- pression for scientific data sets based on multidimensional prediction and error-controlled quanti- zation. In 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp- 1129-1133 IEEE, 2017.
Jiannan Tian, Sheng Di, Kai Zhao, Cody Rivera, Megan Hickman Fulp, Robert Underwood, Sian Jin, Xin Liang, Jon Calhoun, Dingwen Tao, et al. Cusz: An efficient gpu-based based grou-bounded lossy compression framework for scientific data. arXiv preprint MxXiv2207.00922 2020.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2017.
Cheng Wan, Youjie Li, Ang Li, Nam Sung Kim, and Yingyan Lin. BNS-GCN: Efficient full-graph training of graph convolutional networks with partition-parallae parallelism and random boundary node sampling. In Fifth Conference on Machine Learning and Systems, 2021.
Cheng Wan, Youjie Li, Cameron R. Wolfe, Anastasios Kyrillidis, Nam Sung Kim, and Yingyan Lin. PipeGCN: Efficient full-graph training of graph convolutional networks with pipelined feature communication. In International Conference on Learning Representations, 2022. URL http:: //openreviess net//formm http://rrrumntttksass////iiii
12

---

Published as a conference paper at ICLR 2022
Minjie Wang. Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centrie, highly-performant package for graph neural networks. arXiv preprint Xivi: arXiv: 1909.09999... 2019.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning. pp- 6861-6871. PMLR, 2019.
Lingfan Yu, Jiajun Shen, Jinyang Li, and Adam Lerer. Scalable graph neural networks for hetero- geneous graphs. arXiv preprint arXiv:2011.09679 2020.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. In International Conference Learning Representations, 2020. URL https: //tp///////e/e.eeee.eeoeoo net forum BJeediie--BBBBHE--
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in Neural Information Processing Systems, 31:5165-5175, 2018.
Yiren Zhao, Duo Wang, Daniel Bates, Robert Mullins, Mateja Jamnik, and Pietro Lio. Learned low precision graph neural networks. arXiv preprint arXiv:2009.099 09232, 2020.
Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. In International Conference Machine Learning, pp- 11458-1144 1468. PMLR, 2020a.
Da Zheng, Chao Ma, Minjie Wang, Jinjing Zhou, Qidong Su, Xiang Song. Quan Gan, Zheng Zhang, and George Karypis. Distdgl: distributed graph neural network training for billion-scale graphs. In 2020 JEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3), pp. 36 44. IEEF, 2020b.
Rong Zhu, Kun Zhao, Hongxia Yang. Wei Lin, Chang Zhou, Baole Ai, Yong Li, and Jingren Zhou. Aligraph: a comprehensive graph neural network platform. arXiv preprint arXiv:1902.088. 2019.
Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Layer-dependent importance sampling for training deep and large graph convolutional networks. arXiv preprint arXiv:1911.07323. 2019.
13

---

Published as a conference paper at ICLR 2022
A
NOTATIONS
Table 5: Table of Notations.
Notations
Description
The numher of nodes
The number edges
A
R
The adjacency matrix, which is stored in sparse matrix format The normalized adjacency matrix, which is stored in sparse matrix format
A E
X
The input feature matrix
The uncompressed node embedding at the 1th layer corresponding to node v The uncompressed node embedding matrix at the 1 layer (each row is node embedding It.
( D h (Q) Mee
The node embedding dimension
The quantized node embedding the 1 layer corresponding node
H INT To
The quantized node embedding matrix at the 5 layer (cach row is a h
The quantization range, where r3 = max (h. (1) min (h.
The bit-width. In this paper, b must be chosen from 21,2,4,8, 32}
The randomly projected node embedding at the ( layer corresponding to node V
H tt
The randomly projected node embedding matrix the 1 layer (each row is h h
proj R
The dimension projected node embeddings
The recovered node embedding at the 1 layer corresponding node
(either compressed by quantization random projection)
The recovered node embedding matrix at the 1 layer (each row is a h
Var(h) (t))
The variance of the vector h, where Var(h) = E/h ht] (E(h) (B(h))
Ih
The 2-norm of vector h, where |/||2 vh hTT
The infinity norm of vector h, where /1]loc max h
B RELATED WORK AND DISCUSSION
Due to the page limit, we discuss the relationship between EXACT and existing works in detail here. GNN is notoriously inefficient and non-scalable during both the training and inference phase. Pre- vious works can be divided into two categories according to the problem they try to solve, Namely, scalable/efficieet GNN inference and scalable GNN training. Below we introduce and discuss the relationship between them and EXACT.
B. SCALABLE/E GNN INFERENCE
Scalable GNN inference is an orthogonal direction the problem that EXACT tries to address. Be- low we introduces two popular directions for scalable GNN inference. Namely, GNN quantization and graph sparsification.
GNN Quantization. Most of the previous GNN quantization works focus on enabling the usage of low precision integer arithmetic during inference. Specifically, Tailorr et al. (2021) proposes a Quan- tization Aware Training method tailored for GNNs, which emulates inference-time quantization during the training phase. Zhhoo et al. (000)) proposes to jointly search the quantization bit-width and GNN architectures. Note that both of them do not actually convert the node embeddings into lower numerical precision during training. Instead, they use full precision data type simulate the effect of real quantization. |Fng et al. (2020) proposes a heterogeneous quantization framework which assigns different bits to node embeddings in each layer while maintaining the weights at full precision. However, due to the mismatch in operands' bit-width, it is impractical to use in general purpose hardwares, such as CPUs and GPUs.
Graph Sparsification. The adjacency matrices are usually stored sparse matrices. When hard- wares perform SPMM, the sparse matrix format leads to random memory accesses and limited data reuse due to its irregular structure. Thus, GNNs have higher inference latency than other neural networks, Graph sparsification can alleviate the issue by removing redundant edges from original graphs. iZheng et al. (2020a) proposes leamiig-baseed graph sparsification method which removes
14

---

Published as a conference paper at ICLR 2022
potentially task-irrelevant edges from input graphs Li et al. (2020) formulates the graph sparsifica- tion problem as an optimization objective which can be solved by alternating direction method of
multipliers (ADMM). Chen et al. (202Ib) proposes to co-simplify the input graph and GNN model by extending the iterative magnitude pruning to graph areas.
B.2 SCALABLE GNN TRAINING
In this subsection, we introduce previous works that try to train GNNs on large graphs. We conclude that EXACT are parallel to most of the previous works.
Subgraph Sampling/Mini-Bai Batch Training. As we introduced in the main body, most of the pre- vious scalable GNN training methods fall into this category. The key idea is to train GNNs with sampled subgraphs instead of the whole graph at each step. In this way, only node embeddings that are present in the current subgraph will be retained in memory. Based on this idea, various sampling techniques have been proposed, including the node-wise sampling (Hamilton et al. Chen et al., 2017; Markowitz et al., 202T), layer-wise sampling (Zou et al. 2019 Huang et al. 2018), and subgraph sampling (Chiang et al., 2019; Zeng et al., 2020). Generally, methods in this category are orthogonal to EXACT, and they can certainly be combined. Similar to EXACT, subgraph sampling also introduce the gradient noise during the training process. How- ever, the gradient noise does not necessarily result in the model performance drop. In contrast, many previous works experimentally show that subgraph sampling based methods may even yield better performance than the whole graph training (Zeng et al. 2020 Hu et al., 2020). Our experi- ment results also exhibit a similar phenomenon that EXACT may achieve better performance than the original one. This observation can be explained by the regularization effect introduced by the gradient noise (Hu et al. 2020
2017
al. 2018
In this paper, we show in experiments that EXACT can be combined with subgraph-sampling based methods with only limited accuracy drop. From the practical usage perspective, EXACT can enlarge the maximal subgraph size for subgraph wraining-based method. As a result, the error introduced by EXACT can be compensated by using larger subgraphs, which previously cannot fit into GPUs. We leave it as one future direction.
GNNAutoScale (Fey al., 2021). GNNAutoScale follows the idea of utilizing historical embed- dings from prior training iterations (Fey et al. 2021). Specifically, it stores historical embedding for each node as an offline storage CPU memory. At each training step, it first samples a mini- batch of nodes. Then for out-of-mini-hatee nodes, GNNAutoScale swaps their historical embed- dings from CPU memory to GPU memory and utilizes their non-trainable historical embeddings for propagation. In this way, only the node embeddings inside the current mini-batch and those of their direct I-hop neighbors are retained in memory. The time overhead of GNNAutoScale is mainly from the swapping step. EXACT is orthogonal to GNNAutoScale. It would be interesting to store node embeddings compressed by EXACT as historical embeddings for GNNAutoScale. Considering that quantization is more time-efficeent compared to swapping, the time overhead of GNNAutoScale can be greatly reduced since the time cost of swapping scales with the total number of bits to be swapped.
Distributed Training. Unlike the data in other domains, the graph data cannot be trivially divided into mini-batches due to its connectivity between samples. The graph distributed training methods require to split the graph into mini-batches that minimizes the communication overhead. Specifi- cally, AliGraph (Zhu et al. 2019) is a distributed GNN framework on CPU platforms, which does not support GPUs acceleration. ROC (Jia al., 2020) learns to optimize the graph partitioning by predicting the execution time of performing GNN operation on an input subgraph. PipeGCN (Wan al., 2022) proposes train GNNs with stale features and stale feature gradients under the distributed training setting. Both BNS- RCN- (Wan et al. 202T) and DistDGI. (Zheng et al., 2020b) leverage METIS (Karypis Kumar 1998) to performance the graph partitioning to minimize the communication cost. However,
main drawback of applying METIS is that the ahead-of-trainie overhead of METIS is relatively large on huge graphs. EXACT is also orthogonal to the distributed training methods and can be used to decrease the hardware requirements. It would be interesting to investigate the trade-off among the accuracy drop and the memory saving of EXACT under multi- GPU settings.
Memory efficient training system. Gradient checkpointing (Chen et al. 2016 Jain et al. 2019; Kirisame al. 2020 Shah al. 2020) trades computation for memory by dropping some of the
15

---

Published as a conference paper at ICLR 2022
Algorithm 1: Forward Pass the 1 GCN layer
Input: H (e the total number of layers
Output: H0+1)
ctx + f /+ the context which saves tensors for backward
J (M( (
Add H and @ to ctx used for MM.backward
H < (A J())
Add (in CSR format) and J to ctx
/+ used for SPWMbbccwwrr
+/
if * L then
Add 1 (1i(t))) to ctx () used for Rel.U.backward
HU+1) = Rel.U(H((())
end
return H(+1)
activations in the forward pass and recomputing them in the backward pass. Swapping (Meng et al., 2017) utilizes the huge amount available CPU memory by swapping tensors between CPU and GPU. EXACT is also parallel to both the gradient checkpointing and swapping. As result, EXACT can be combined with them to further squeeze out the memory, at the cost of larger time overhead.
Other Activation Compression Techniques. JPEG-ACT [Evan et al. 2020) extends the widely- used JPEG method to compress the activations. Cusz is a prediction beasdettio--beeedd lossy compression method with GPU support (Tian et al. 2020 Tao et all 2017). Both of them can be applied to compress the activations GNNs. However, one practical problem is that they have hyperparam- which hard to tune. For example, in JPEG-ACT, there is hyperparameter controls the space/accuracy trade-off. This problem can be alleviated by incorporating one recent proposed method AC-GC (Evans & Aamodt, 22021). Given a preset allowable increase in loss, AC-GC can automatically find the hyperparameter such that the compression rate can adapt to the preset training conditions. We note that EXACT and AC-GC approaches the problem from different perspective. For EXACT, we value the compression rate more than the accuracy drop. Namely, given a preset memory budget, we try to fit the model with acceptable accuracy drop. For AC-GC, they value the accuracy change more than the compression rate in the sense that the compression rate is adapted to the given allowable accuracy drop.
C ANALYZING THE MEMORY CONSUMPTION OF GCNS
Generally, each training step contains forward pass phase and backward pass phase. During the forward pass, activation maps of each operation are kept in memory for computing the gradients. During the backward pass, the weight gradients and activation gradients calculated and stored in memory. For weight gradients, their memory usage is negligible since they share the same shape with model weights. For activation gradients, their memory usage is dynamic and will eventually be cleared to zero. In standard deep learning libraries, activation gradients will be deleted as soon as their reference counting becomes zero (Paszke et al. 2019 Abadi al.) (016)). Thus, storing activation maps take up most of the memory. The memory usage of activation maps in GCN layers are given in Algorithm
D RANDOM PROJECTION
In this paper, we use the normalized Rademacher random matrix (Achlioptas) 2001 for projecting the activation maps. Specifically, for D R normalized Rademacher random matrix R, each element in R is i.i.d. sampled from the following distribution:
1
+1, with probability
I R
2'
Ri
x
(7)
1
1, with probability
2
16

---

Published as a conference paper at ICLR 2022
where V is the normalize factor such that E[RR'] = I. From above, we can see that the sampling cost of the normalized Rademacher random matrix is relatively low since sampling from Bernoulli distribution is much cheaper than sampling from Gaussian distribution.
E
THEORY
E.1 PROOF OF PROPOSITION
Proposition 1 (Details in Appendix
The above quantization and dequantization unbiased operations, ie., Elh+") [1] ([Dequant(Quainn (h (1) ))] h.0 and Var(h
Dir
6."
Proposition is adopted from the theoretical analysis in ActNN (Chen et al.
2021 a
For complete-
ness, prove it here with more details. The conclusion of (h h
follows from the fact that
the stochastic rounding is an unbiased operation (Courbariaux et al. 2013). Specifically, scalar h, the stochastic rounding can be expressed as
[h], with probability h [h],
[ = [A], with probability 1 - (h [A]),
(8)
where [-] is the ceil operation and |.] is the floor operation. First, have B[[ h because
[ [h (h [A]] [h](1 h [h])
(following the fact that [h] - [4] = 1)
Hence,
(1)
E(h(1]
T1 B
E[L
h
BI. + 2 = h
Tv
h
z(!) 1
Regarding the variance, let h Uniform(0, 1). we have.
B = (h). hh)). Suppose Vi, h4 [4,] =
Var(h!)) [r! B²
Var(( = B:h h] (E((T) ((B())
10
12 [hal) 1 h4 + [h,]) h2
11
(2) (2 h1 - 1hh1 [hg] h2)
(substitute [h1] with [hr] + 1)
132
[r 1012
(a 0²)
(substitute [ha] with hy σ))
B²
By taking expectation w.r.t. on the both side, have Var(h!
11DD) 6
E.2 PROOF OF PROPOSITION
Proposition 2 (Proof in Appendix
E The above RP and IRP are unbiased operations, i.e.,
( ((IPP(RP(HH
H For each (()) in A))), we have Var(h. D
We can get [ (] B[H RR H ("0), H
EIRP(RP(H ())
(()) directly following the fact that
Regarding the variance, let P = RRT E DXD, For the sake of notation convenience, we ignore the subscript and superscript in this subsection. Namely, we the notation represent h!!) and
17

---

Published as a conference paper at ICLR 2022
the notation h to represent h Also, assume the shapes of h and h are both 1 D in this subsection. We have
Var(h) = Var(hP)
= hE|PP 1h hh
Next, will characterize the distribution of PPT. Recall that P= RR thus,
P.j
where each 0zj = V I H
with equal probability. Thus,
[PP
kig Σ
P
Pj Pj.m
D
R
R
Σ
Oi.k km.k) )
Σ a).kmm)))
From Equation 9 it is easy to show that [PP is diagonal matrix. Namely, Vi * j. we have E[PPT kj following the fact that each os are independent and R[as,g) = 0. For elements on the diagonal, we have
EPP
kis
E
P
P.m
P
R
E
ai
R
E
aiaaai 121
Qj 0m, )
miti 1=1
R
B[(ai,,0m. ) 11+2
Σ
m
p.a:p<a
+
B((ak_k0m,k))
mafi
D
1 +
(10)
R
Let = (hi,.--hup hD), we have
Var(h)
hE PP hh
1
D-1
=h
h hh.
1 D
D
D
D
h
R
1=1
1=1
D
111
(II)
R
18

---

Published as a conference paper at ICLR 2022
E.3 PROOF OF PROPOSITION
Proposition 3 (Proof in Appendix E For each projected node embedding h Nupros = RP(h!
(1)
(1) for Ve O, by choosing = || 1 2ln(2R/c) we have P(Ilhoppll S 5) 2 1 -
(1)
(1)
For the normalized Rademacher random matrix R R we have Rig + | with equal
VR
probability. Let h = (hi,... ... hp) and hape = ("1,"..,,d) Since hepp = h R. we have 01 EE= aghi, where a; - - VR with equal probability.
First, we have the following inequality:
Ele E
II i=1
Eie Ro,
etVRh,
Rh, + +
D cosh tv Rh;
II
II
2
D Pna
(following the fact that cosh x S e 22
e
e 1
(12)
For notation convenience, we use the notation "C" to represent the node embedding norm ||
(1
112-
For Vs, q > 0, according to Chernoff bound, we have:
P((s| 2 8) 2P(u; s)
= 2u: 2 E!5)
< 2 B[equu]
(by Chernoff bound)
egs
yRai 6x
Ele
sRt
2
(by setting g
C
e C2
_2g
< 2c
222
(by Equation 12
(13)
Note that Equation 13 holds for Vs P([ud 2 s) < c Also, R
0. Given specific e, by setting CV
(2R(2/cc)
have
R
P(
1100 S)
II
P([u5 S s)
i=1
(1 P([uel 2 s))
e )n
2 (1
R
> 1-6
Here we also experimentally verify Proposition 3 by visualizing the infinity norm of projected node embeddings Figure 4 To avoid creating confusions, 2 = 1 in Figure 4 means we apply the random projection with D on the activation maps. We can observe that In general, the infinity norm increases with the compression ratio π2- However, we note that the infinity norm of projected embeddings may less than those of original embeddings when R is larger than threshold. This sug- gests that when R is below a certain threshold, quantizing projected embeddings only have limited influence model performance. This claim also verified in the main body of this paper.
19

---

Published as a conference paper at ICLR 2022
20000
Dyfed
12000
D/R-2
D
Dri orginal
10000
Dff-1
Frequency
Frequency
orginsl
12500
8000
10000
6200
4000
1200
2500
05.
2.
30
The infinity norm of projected embeddings
The infinity norm projected embeddings
Figure 4: The histogram of the projected node embeddings" infinity norm at MM (the left figure) and SPMM (the right figure) operation of the first GCN layer.
E.4 THE COMPOUND EFFECT OF APPROXIMATION ERRORS
In this subsection, we analyze why GNNs can tolerate the extremely compressed activations. From the numerical analysis (Bauer 1974). the jacobian matrix (gradient) between two tensors can be viewed as sum over all "paths" connecting these two tensors. Moreover, the architecture of GNNs is considerably shallower than CNNs and transformers. Informally, for GNNs, the key intuition is that these paths are significantly "shorter" compared to those of CNNs. As result, the approxima- tion error (i.e., the variance from quantization) along the path is hard to get accumulated.
We adopt Theorem 3 in ActNN (Chen et al., 2021a) to make the above statement more rigorous. Let É(m) be the compressed context (either by quantization, random projection, or quamtized random projection). Let (@(") and V ()) be the gradient of @ and H respectively. Ve(") and ( are the calculated gradient using the compressed context, respectively. Further, we use the notation G(l-mm) H (m)) (()) to represent the variance introduced by utilizing the compressed context (m)) Specifically, for layer GNN, we have
Var(vo Var(Vo +
E Var Var(G (l-m) (m ((m)) ( {HI(m))
(!!l
(14)
where Var(-IVH is the conditional variance, and Var(V( is the variance is from the mini- batch sampling variance. The key insights from Equation are two folds. First, since the variances introduced by compressed contexts at different layers will accumulate, it suggests that the noise introduced by the compressed context is relatively small for shallow models. Considering that most of GNNs usually less than four layers, this may explain iy the loss in accuracy negligible when using the vanilla INT2 quantization and a relatively large π ratio. Second, under the subgraph training setting, the extra variance introduced by quantization can be compensated when using larger batch size (i.e., the size of subgraph in the graph learning).
In Table D evaluate GNNs under the full-batch setting. Therefore, in addition the reason of mentioned shallower architecture, it is also possible that the activation compressed training benefits from the large batch size, which leads effect of the batch size, below we present the ablation studies of two representative sampling based methods with much smaller batch size. Namely, GraphSAINT (Table(G) and Stusttr-GGNN (Table 77). For the baseline, we use the same hyperparameters reported in the corresponding paper. We make two main observations. First, INT2 quantization works under a much smaller batch size. Namely, for both Cluster-GCN and GraphSAINT, the accuracy drop is negligible even when the sampled subgraph contains only ze 500 nodes. This observation implies that the activations of GNNs can be aggressively compressed regardless of the batch size. Second, using much smaller batch size in general will lead to an accuracy drop. However, for Yelp. a much smaller batch size may even improve the performance.
much smoother gradient. To quantitatively study the
20

---

Published as a conference paper at ICLR 2022
Table 6: The ablation study of the effect of batch size GraphSAINT. Here "Small BS" means smaller batch size. For GraphSAINT, INT2 quantization also works under the smaller batch size.
Batch
Dataset
Method
Walk Length
Root
Accuracy (%) Fl-micro
Size
Baseline
2
6000
12,000
51.11 + 0.28
Flickr
Small BS
500
500
47.67 0.42
Small BS w./
1
500
500
48.33 0.29
INT2 quantization
Baseline
4
2000
8,000
96,02 0,08
Reddit
Small BS
1
500
500
93.73 + 0.14
Small BS w./
500
500
93.72 0.10
INT2 quantization
Baseline
2
1250
2,500
63.78 0.12
Yelp
Small BS
1
500
500
64.05 0.14
Small BS
500
500
64.01 0.12
w./NNT2 quantization
Table 7: The ablation study of the effect of batch size Cluster-GCN, Here "Small BS" means smaller batch size. For Cluster-GCN, INT2 quantization also works under the smaller batch size.
#clusters per batch
Batch
Dataset
Method
#partitions
Accuracy (%) / Fl-micro
Size
Baseline
1000
30
2,680
49.61 = 0.47 50.01 + 0.30
Flickr
Small BS
1000
446
Small BS w./
1000
5
446
49.99 = 0.28
INT2 quantization
Baseline
1500
20
3,100
95.62+0.10 95.30 # 0.13
Reddit
Small BS
1500
3
465
Small BS w./
1500
3
465
95.29 + 0.07
INT2 quantization
Baseline
5000
20
2,870
63.98 # 0.14
Yelp
Small BS
5000
3
430
63.91 = 0.14
Small BS
5000
430
63.69 + 0.23
w/NN quantization
Table 8: The Operation configurations of EXACT.
Operations
Quantization?
Random Projection?
Extra Errors?
Linear (MM )
SPMM
SPMM.MEAN
SPMM MAX
SPMM MIN
BatchNorm
X
ReLU
(fixed 1 bit)
X
X
Dropout
(fixed bit)
X
F SYSTEM IMPLEMENTATION OF EXACT
F.1 INDIVIDUAL LAYERS CONFIGURATIONS OF EXACT
The operation configurations shown in Table For all graph convolution operations, EXACT can apply both the quantization and random projection to their saved activation maps. In EXACT, the SPMM and its variants (i.e., SPMM MAX, SPMM MEAN and SPMM MTN are implemented based
21

---

Published as a conference paper at ICLR 2022
on those provided in Pytorch Sparse] with extra supporting for compressing activation maps by quantization and random projection.
For BatchNorm layers, found that quantizating its saved activation maps only impact model per- formance a little, which is experimentally verified in the experiments. However, we experimentally found that randomly projecting its saved activation maps will lead to divergence. We note that this observation is consistent with previous finding that BatchNorm is very sensitive to noise (Micikevi- cius al. 2017). Hence, EXACT only apply the quantization to BatchNorm layers.
Regarding ReLU operations, we have = ReLU(@)) = æ æ1=>0 and Vy Vylæ>0- Hence, ReLUU operations only need to store 1=50 in the context for the backward pass, which takes single bit per element to store, without introducing any errors. Since standard deep learning framework only support down INT8 precision, here we convert the mask matrix into bit-stream and fuse this process into the CUDA kernel of forwwrd to minimize the time overhead.
Regarding Dropout operations, let p be the dropout probability. During the training process, we have
1
1
y Dropout(2,2) p) 1 æg.
Væ
1-p Vyg.
(15)
1 is the normal- where g ~ Bernoulli(1 p) is binary vector sharing the same shape æ. T-p
ization factor such that Ely] æc Similarly, Dropout Operations also only need store g in the context for the backward pass, which takes a single bit per element to store, without introducing any errors. Similarly, convert ! into bit-stream and fuse this process into the CUDA kernel of Frowoud to minimize the time overhead..
To be clear, "fixed bit" in T means the activation maps ReLU and Dropout operations take only bit per element to store. And the bit-width of all other operations can be adjusted.
F.2 IMPLEMENTATION DETAILS
We provide simple API for converting modules in Pytorch Geometric and Pytorch to its corre- sponding version in EXACT. For example, replacing forch.geometrr. CC..Coooonvv with exact. GCNConv and replacing torch. dropout with exact. dropout. Currently, EXACT only support Pytorch Geometric and Pytorch. In future we will try to integrate EXACT with other popular graph learning packages, such as DGL.
nn. GCNConv
Following ActNN (Chen et al.) 2021a), to obtain the highest compression ratio, the quantization range - and the zero point t are stored in the 6 data type The quantization and de- quantization modules are both implemented using CUDA kernels. We note that Pytorch only support data types down to INT8. To obtain highest compression ratio, the quantized data is compressed into bit streams such that it can be decoded later during the dequantization process.
All CUDA kernels in EXACT support both full-precision and half-precision (i.e., bfloat16 and float 16). Thus, EXACT can also be integrated with the automated mixed precision training, i.e., AMP to further decrease the memory consumption.
G EXPERIMENT SETTINGS
G.1 DATASETS, FRAMEWORKS, AND HARDWARES
We give the detailed statistics and the download URLs for all datasets used in our experiments in Table TO We follow the standard data splits and all datasets are directly downloaded from Pytorch Geometric the protocol of OGB (Hu et al. 2020). We implement all models based on Pytorch and Pytorch Geometric. Almost all experiments are done on a single NVIDIA GeForce RTX 3090 with 24GB GPU memory. During our experiments, we found that the version of Pytorch, Pytorch Sparse, and Pytorch Scatter can significantly impact the running speed of the baseline. Here we list the details of our used packages in all experiments in Table 9
htttps//ggihuub..o///s wtt.o////ssssssyyoooooooooo 1s/pytorch spanse/blobmmasterrorchh sparse/matmul..py
htt.://ooorr....ooo.oofo.ffoooe fenssorb
22

---

Published as a conference paper at ICLR 2022
Table 9: Package configurations of our experiments.
Package CUDA
Version
11.1
pytorch sparse
0.6.12
pytorch. scatter
2.0.8
1.7.2
pytorch
1.9.0
OGB
1.3.1
Table 10: Dataset Statisties.
Dataset
Task
Nodes
Edges
Features
Classes
Label Rates
Reddi
multi-class
232,965
11,606,919
602
41
65.86%
Flickr
multi-class
89,250
449,878
500
50.00%
Yelp
multi-label
716,847
6,977,409
300
100
75.00%
ogbn-arxiv
multi-class
169,343
1,157,799
128
40
53.70%
oghn-products
10
multi-class
2,449,029
61,859,076
100
47
8.03%
G.2 MODEL HYPERPARAMETER CONHGURRATON OF TABLE AND TABLE
Table 11: Training configuration of Full-Batch GCN, GraphSAGE, and GAT Table and Table
Training
Architecture
Model
Learnnng Rates
Gradient Clipping
Epochs
Dropout
BatchNorm
Layers
Dimension
Heads
GCN
0.01
300
0.5
0.0
Yes
128
GraphSAGE
0.0
GAT
0.002
2000.
0.75
0.0
Yes
128
3
We adopt three popular GNNs. Namely, GCN (Kipf & Welling 2017). GraphSAGE (Hamilton et al., 2017). and GAT (Veličković et al. 2017)) in Table | and Table 2 We follow the hyperparameter configurations and codebases provided on the OGB (Hu et al. 2020) leader-board. Specifically, the hyperparameter configuration given in Table [] The optimizer is Adam (Kingma Ba 2014) for GCN and GraphSAGE, while the optimizer RMSprop for GAT. All methods terminate after a fixed number of epochs. We report the test accuracy associated with the highest validation score. The "Gradient Clipping" in Table TT indicate the maximum norm for gradients. "Gradient Clipping= 0.0" means we do not clip the gradients in that experiment.
G.3 HYPERPARAMETER CONFIGURATIONS OF EXACT (RP+INT2)
The EXACT (RP+INT2) has only one hyperparameter, namely, D The configuration of EXACT R
(RP+INT2) can be found in Table I2
G.4 MODEL HYPERPARAMETER CONHGURATIONS IN SECTION 5
The optimizer used in all experiments in Section 5 is Adam (Kinmma & Ba 2014). We use the default hyperparameters for Adam optimizer, except for the learning rate. All methods terminate after fixed number of epochs. We report the test accuracy/F --miioo associated with the highest validation score. Regarding Reddit, Flickr, and Yelp dataset, we follow the hyperparameter configurations reported in the respective papers as closely possible. We clips the gradient during training. The "Gradient Clipping" below tables indicate the maximum norm for gradients. "Gradient Clipping= 0.0" means we do not clip the gradients in that experiment.
http:://wweteeeeeerreeddddddddlr httffftorch geometric.datasets Reddit http:///www....momm.......eeeolp htt.ee/e.......o..ooooiooooooooe
htmlttorch hww.:ttocccgeoommttiii....... geometric. ciamettric.aatastt.Fiiii.. Frickr geometric.datase Yelp
hhttps:/ogb.sttaforr haaaaf/rrecddldcsssooooopppppnnr www.aa/saaaaacalooooooooooooaann
23

---

Published as a conference paper at ICLR 2022
Table 12: The D R
configuration of EXACT (RP+INT2) in Table
ogbn- arxiv
ogbn-
Reddit
Flickr
Yelp
products
Cluster-GCN
8
8
4
2
GraphSAINT
8
GCN
8
8
8
GraphS AGE
4
GCNII 8
8
2
8
Regarding ogbn-arxiv and ogbn-products dataset, we follow the hyperparameter configurations and codebases provided on the OGB (Hu et al. 2020) leader-board. Please refer to the OGB website for more details. Table T3 and Table 14 summarize the hyperparameter configuration of Cluster-GCN) and GraphSAINT, respectively. Table [5] Table I6] and Table 17 summarize the hyperparameter configuration of full-Batch GCN, full-Batch GraphSAGE, and full-batch GCNII, respectively.
Table 13: Training configuration of Cluster-GCN in Table
Cluster Sampler
Training
Archtecture
Datasct
#Cluster por batch
Learning Rates
Gradient Clipping
Hidden
Apurtitions
Epochs
Drapout
BatchNorm
Layers
Dimension
Reddit
1500
20
0.01
0.1
0.5
Yes
128
Flickr
1000
30
0.01
0.2
0.5
Yes
256
Yelp
5000
20
0.01
0.1
0.5
Yes
512
ogbn-
products
15000
32
0.001
0.5
0.0
No
256
Table 14: Training configuration GraphSAINT in Table
WandomWaik Sampler
Training
Archtecture
Dataset
Learning Rates
Gradient Clipping
Hidden
length
Epachs
Drupout
BatchNorm
Layers
Dimension
Reddat
2000
Flickkr
6000
0.01
15
0.2
0.5
Yes
256
Yelp
ogba-
arxiv
ogbn-
20000
products
Table 15: Training configuration of Full-Batch GCN in Table
Training
Archtecture
Dataset
Leaming Rates
Fpachs
Dropout
Clipping
RatchNorm
Layers
Dimension
Hidden
Rediit
0.01
400
0.5
Yes
2
256
Flickr
0.01
400
0.3
Yes
2
256
Yelp
0.01
500
0.1
0.5
Yos
2
512
agbn-
0.01
500
0.5
0.5
Yes
3
128
arxiv
Table 16: Training configuration of Full-Batch GraphSAGE in Table
Training
Archtecture
Dataset
Learning Rates
Epuchs
Dropout
Gradient Clipping
BatchNorm
Layers
Dimension
Hidden
Redidit
0.01
400
0.5
0.5
Yes
256
Flickr
0.5
256
Yelp
0.01
500
0.1
0.5
Yes
512
ogbn-
0.01
500
0.5
0.5
Yes
128
arxiv
ogbn-
0.002
500
0.5
0.5
No
256
products
24

---

Published as a conference paper at ICLR 2022
Table 17: Training configuration Full-Batch GCNII in Table 3
Training
Archtecture
Dataset
Learingg Rates
Gradient Clipping
Hiddeen
Epachs
Dropout
BatchNorm
Layers
Dimension
Rediit
0.01
400
0.5
0.5
Yes
4
256
Flickr
0.01
400
0.5
0.5
Yes
8
256
Yelp
0.01
500
0.1
0.5
Yes
4
512
egbn-
0.001
1000
0.1
0.1
Yes
16
256
ariv
H ANALYZING THE MEMORY USAGE
H.1 ANALYZING THE MEMORY USAGE
We use torch. cuda www.mmemoommmoooo. -loccated for the memory measurement. As we mentioned in Table "Act Mem." " is the memory occupied by activation maps. Besides activation maps, the model, optimizer, input data, weight gradients, and activation gradients also occupy GPU memory- We will analyze each of them below. First, the memory occupied by the model, optimizer, and weight gradients is negligible because the number of parameters in most of GNNs very small. Second, the memory occupied by the input data depends on the graph size and often cannot be compressed. This part can take up a lot of memory when the graph is large. Third, the memory occupied by activation gradients is dynamic and hard to estimate, since these tensors are temporarily stored GPUs. For standard deep learning library, they will be deleted as soon as their reference counting becomes zero (Abadi et al., 2016 Paszke et al, 2019). EXACT cannot compress activation gradients. However, the memory occupied by activation gradients can be compressed using AMP, because activation gradients are stored in f data type under AMP, As illustrated in Appendix [2 we note that our EXACT framework can be integrated with AMP.
The memory usage of the model weights plus optimizer is about 2MB. Since activation gradients are dynamic and hard to analyze, here we report the peak memory usage during the backward pass, which encompass the activation gradients and other intermediate variables. For the memory usage of the input data, activation maps, and the peak memory usage during the backward pass, we provided detailed analysis in Table 18] We can observe that the memory usage is mainly occupied by activation maps. For GCNII, the memory usage is dominated by the activation maps. This is because need to store all layers' activation maps during the forward pass. In contrast, during the backward pass, there is usually only one layer' activation gradients are kept in memory.
The detailed analysis about the memory usage of input data, activation maps, and peak memory usage during the backward pass. "Data Mem" is the memory usage of input data (including the input feature matrix X, adjacency matrices A, and labels ). "Act Mem" is the memory usage of activation maps. "Peak BWD Mem" is the peak memory usage during the backward pass. "Ratio (%)" here equals
Table 18:
Act Mem
Data Mem-+Aad Act Men Memn+Peauk Peak BWD Mem
<phes
opln.
Pest Men
Tara
Peak Mari
Bao
Art
Peak:
Art
Plat Man
(a)
Dira
Peak Mer.
1010
3.2
15.5
3-1
3:3
2013
12
4.1
11.
A8.2
157
GCN
1164
11C3
316
43.9
1564
6434
71.
175
126-4
K2.3
719
1164
1827
(96
45.0
208
547
184
15.5
1563
6036
2011
61.2
178.7
786.2
192
58.1
4811
28895
6176
ALL
97.5
H.2 OVERALL COMPRESSION RATIO
The overall memory compression ratio shown in Table 19 We observe that (1) for shallow GNN models, the overall memory compression ratio ranges from 1.5x to 4x. (2) for GCNII, the overall memory compression ratio ranges from 4x to 18x. We note that we store the graph structure data (e.g., node ID and edge ID) in torch.Long data type, which can safely cast to torch. data type to save the memory. Our implementation supports for using Intch. as the data type for the graph structure data. However, for a fair comparison, we do not utilize this feature.
25

---

Published as a conference paper at ICLR 2022
Table 19: The detailed analysis for the overall memory compression ratio. Below the equation means "Data Mem" + "Act Mem" + "Peak BWD Mem" = "Overall Mem". EXACT can only compress the memory usage of activation maps.
Mede
Matted
Redde
mikr
Wil
prolats
Bustee
434185433:573
OCN
EDAATT (MP-INTT)
EXACT (NT2)
2 (2.00)
(1
Sed (2:20a)
Sisdei2//0///220 (230c)
60--22e11 Se1M (2777))
TEx EXALT (INT))
(1a8he)
31.247 2420 12.1
2e (2.300)
S7e40 (2477)))
EXACT (20 (NT2)
12000
51.203 442hw035 11 Sead
5 be b4222
26.74 26.7 43 Jartes 13,
57428 155055 (1300s)
OCN
EXACT (INT2)
22 8-3
(6-100 11.50 1,56x)
29 (2.0ba)
1544 (15-2000 23xx
1157445-5-1120 1253312444 lext
IICACT (RP-INT))
(1.3))
204-17 111 k21kk)
37574915-87 786 (7
Graph
SACE
EXAUT (INT))
INT2)
1808
3003 (160))
3-18 14415 (2 Dhe
15iza0ane201 <he (3 330
176
10010000002 (2893)
45114572461 2.39-
12331 (2.77))
Toullin
200 7807
1586 167
175 015--1115---4-1117755
OCNI
EXACT (INT2)
1155 355- 193-1135 (Ul)))
20x3
(344-2235-112
17534455-1544 15485-114 156.61111111111115555555
H.3 ANALYZING THE MEMORY COMPRESSION RATIO
Below we analyze the compress ratio in Table 3 We take a three-layer, 128-dimensional GCNs
trained on ogbn-arxiv for example. The computational graph of the baseline in Table is:
Total bits =M(MM) + (SPMM)) + 32( + O(ReL.U) + 8(Drooout) +
(the first layer)
32(MM) + (2(MMMM) + 32(BN) + O(ReI.U) + 8(Dropout) +
(the second layer)
32(MM) + 32(MPMM) (the third layer)
Hence the baseline costs totally 240 bit per element. The first MM in the first layer does not cost extra bits because its activation map is exactly the input feature matrix X, which has been stored in GPU memory (recall that we need to first move the input data to GPU memory before training). Pytorch will save this part of memory via the "pass by reference" mechanism. The official ReLU operation in Pytorch does not need the extra space for saving activation maps (they can reuse the activation maps saved by the previous layer via passing by reference). Regarding Dropout operation, Pytorch stores the mask matrix using UINTS data type, which costs 8 bit per element.
The computational graph of "EXACT (INT2)" in Table 3 is:
Total bits (MM) + (SPMM + 2.25 + 1 (ReLU) + 1 (Dropout) + (the first layer)
2.25 + (SPMM) + 2.25(BN) (BN) + I(ReLU) + l(Dropout) + (the second layer)
(MM) + (SPMM)) (the third layer)
The 2.25 bit of MM , SPMM, and BN is from 2 (quantized activation maps) 0.125 (the zero point tensor) 0.125 (the range tensor), where 0. 0.5 details). Also for EXACT, for ReLU since the exact activation maps of previous operation is replaced by the compressed one. Hence in EXACT, the 1-bit masks of ReLU and Dropout is converted into bit-streams using CUDA kernels, which cost 1 bit per element to store.
16 (the bit-width of bffoat16)
'288 (the dimension is 128) (See Appendix F.2 for
cannot leverage the "pass by reference" mechanism to save memory
Hence the "EXACT (INT2)" costs totally 22 bit per element. And the theoretical compression ratio is 210 = 10.9. The empirical compression ratio in Table may have a small gap with the theoretical one. This because the attributes of the sparse tensor (adjacency matrix) in pytorch sparse lazily initialized, i.e., it may be generated during the forward pass and be account for the memory of activation maps.
22
The computational graph of "EXACT (RP+INT2)" with D 8 (see Table 12 in Table 3 is:
R
Total bits =0.) + 0.28 + 2.25(BBN) + (ReLU) + (Dropout) +
(the first layer)
0. (MM4) + (SPMM) + 2.25 + 1 (ReLLU) + 1 (Dropoutt + (the second layer)
0. 0.28 + (.28())MM) (the third layer)
The 0.28 bit of MM and SPMM is from 2010
8x125 0.28125.
16
We note that EXACT
821
does not apply random projection for BatchNorm layers (see Appendix F.2 Hence the "EXACT
26

---

Published as a conference paper at ICLR 2022
(RP+INT2)" costs totally 10.18 bit per element. And the theoretical compression ratio is 23.57. Again, there exists gap between the empirical compression ratio and the theoretical one because the lazy initialization mechanism, the existence of temporary tensors, and the neglect of the memory usage these random projection matrices.
240
10.18
We emphasize that the compression ratio also depends on the number of input features of the dataset. (because the mentioned "input feature matrix X is passed by reference" mechanism). For the above example, the number of input features and the hidden dimension are both 128 and hence it is easy to be analyzed. Hence, the theoretical compression ratio may vary for different datasets.
I ADDITIONAL EXPERIMENT RESULTS
1.1 MORE RESULTS ON ACCURACY AGAINST THE PRECISION AND D R
To support the claim that "the performance of EXACT is mainly determined by the D random projection", present more results the test accuracy against the precision and zl ratio here. In Figure || we show the results of two models trained with EXACT using full-batch data on the ogbn-arxxt dataset. In Figure 6 we show the results of two models trained with EXACT using mini-batch data on Yelp dataset.
H ratio of
GCN (Full-Barca)
GraphSAGE (Full-Daathh)
72.0
73.0
71.6
71.8
DVR
D
71.8
7144
BVR
73.6
71.2
71.4
71.0
IN72
INT4
INT3
1912
I112
ITT
2415
2P32
Quaniiaaiio Precition
Oucorizotion Precision
D Figure 5: The performance of EXACT is mainly determined by the It ratio of random projection. The dataset here ogbn-arxiv. All reported results are averaged over ten random trials.
GraphSAINT (Ydl)
ClastrGCN (Solp)
638
64.0
D-R
63.6
D-R
634
INT2
INT4
INTS
IN12
INT4
Figure 6: The performance of EXACT is mainly determined by the R ratio of random projection. The dataset here is Yelp. All reported results are averaged over ten random trials.
1.2 COMPARISON AGAINST SWAPPING AND GRADIENT CHECKPOINTING
We also compare EXACT against the naive swapping and the naive gradient checkpointing. Both swapping and gradient checkpointing are lossless compression, so they do not have any accuracy drop. Below we present and discuss about their trade-off among the space and speed.
For swapping, we simply offload all activation maps to CPU memory. Thus, it can achieve the highest compression ratio for activation maps. However, its running time overhead is roughly 50%- 80%, which is often unacceptable.
For gradient checkpointing, we utilize torch. ut illiss,.. checkpoint to insert checkpoints at each GNN layer. For the time overhead, as shown in Figure 3, it is comparable to EXACT. We present the memory usage of activations in Table 20 In summary, its time overhead is comparable to EXACT, however, the memory compression ratio of activations 1.7 ~ 2.3x, which is not large enough. Thus, still cannot train the GCNII on Yelp dataset using RTX 3090 (24GB) GPU.
27

---

Published as a conference paper at ICLR 2022
Table 20: The memory usage (MB) of activation maps with the gradient checkpointing. "OOM" means out-of out-of-memory. In general, the compression ratio of activation maps are 1.7 ~ 2.3x.
ogbn- arxiv
Model
Yelp
Reddit
GCN
425
4493
722
GraphSAGE
424
3913
1030
GCNII
6236
0OM
3366
GapASAGE
4.0-
Dlact Lo alS we
963-
9.0
05.0
300
200 Fancle
20
05
Epocks
Specia
Figure 7: Validation Accuracy on Reddit dataset using EXACT with different configurations.
1.3 THE TRAINING CURVES OF EXACT
From the optimization theory, common convergence speed bounds (measured by the number of it- erations) in stochastic optimization improve with smaller gradient variance (Bottou et al. 2018)) EXACT essentially trades the gradient variance in return for reduced memory. Here we experimen- tally examine how EXACT affects the convergence speed. Figure 7 shows the training curves of GNNs trained with EXACT using different configurations on Reddit dataset. We make two main observations. First, EXACT with smaller f typically converges faster per iteration. This is consis-
tent with the mentioned optimization theory. Second, when increasing the R ratio, the difference in the convergence speed is very small, where the convergence speed is measured by the gap in valida- tion accuracy between consecutive epochs. In practical scenarios, EXACT hence only have limited impact on the model performance.
1.4 HYPERPARAMETER SENSITIVITY EXPERIMENT
As we analyzed in the main body, INT2 is a suitable precision and we only vary the D ratio for EXACT. In this section, we investigate the sensitivity of EXACT (RP+INT2) to the D
Ri ratio. Table shows the configuration of EXACT (RP+INT2) in the experiment in the main body. Here present comprehensive hyperparameter sensitivity study for EXACT. Specifically, the sensitivity studies of EXACT with GraphSAINT, ClusterGCN, GCN, GraphSAGE, and GCNII
12
shown in Figure 8 Figure 9 Figure Io Figure II and Figure [2] respectively. Here we summarize some key observations. First, the model performance drop generally increases with the 2 ratio. Second, when H 8, the loss in accuracy of EXACT (RP+INT2) is below 0.5% on two third of experiments. To be concrete, in Table 3 we totally adopt 22 combinations of different datasets and models. As shown in Table 3 and Table g for of the 22 experiments, the loss of accuracy is below or near 0.5% when dt 8. Third, when D excepting for two experiments. Namely, ClusterGCN with ggoonpproducts and GraphSAINT with ogbn-products.
π 8, the loss in accuracy is below 1% in almost all experiments,
1.5 COMPARISON BETWEEN EXACT AND SAMPLING METHODS
I.5.1 COMPARE EXACT TO SAMPLING METHODS UNDER FIXED MEMORY BUDGET
As examined in Table 3 EXACT and subgraph sampling methods are orthogonal and can be applied over each others. Here we present an ablation study comparing EXACT to subgraph sampling methods in a standalone way. We note that EXACT only focus saving the memory for activations. In contrast, subgraph sampling methods can simultaneously reduce the memory of the input data, activations, and activation gradients since they directly reduce the number of node embeddings
28

---

Published as a conference paper at ICLR 2022
GraphSAINT (Plickr)
GruphSAINT (Reddit)
96.0
51.00
Ted: Aceaneyy
Test Aeetrrerr
95.9
50.75
lodie
13B +/s
111-
50.50
DB -4
1MM
95.7
JK
The D ratoo
The D.R ratio
GraphSAINT (Yelp)
GraphSAINT (ogbn products)
63.8
79.0
Text Accuscy
78.5
63.6
modi::
330 --3
311-15
63.4
77.5
734
63.2
The D.R ratio
The D.R ratio
Figure 8: The sensitivity study of EXACT (RP+INT2) to the D ratio, where the model is Graph- SAINT. All reported results are averaged over ten random trials.
π
ClusterGCN (Flickr)
ClusterGCN (Reddit)
95.6
Text Accuncy (P6)
69.75
Acstrry
95.5
49.50
49.25
D.B 3
95.4
DB -4
3R
DB
95.3
381
The raioo
The D.R ratio
ClusterGCN (ogbn-produccs)
ChsstrGCN (Yelp)
64.00
Jist Arcsieyy (%6
Text Accuncy
63.75
78
63.50
hooline
Dik -1
63.25
D
76
DR
The DJR miio
The DJR miie
Figure 9: The sensitivity study of EXACT (RP+INT2) to the D ratio, where the model is Clus- terGCN. All reported results are averaged over ten random trials.
retained in the memory. Hence compared to subgraph sampling methods, one limitation of EXACT is that the overall memory saving ratio of EXACT often cannot surpass that of sampling methods.
Under the full-batch setting, one way further improve the overall memory saving ratio is corporate the graph compression methods with EXACT, such as the graph sparsification (Spielman Srivastava] 20 and graph coarsening (Cai et al. 2021a). However, it is beyond the scope of this paper. For fair comparison, we control the batch size of subgraph subgraph sampling methods such that their activation memory usage equals to that of EXACT (INT2). For both EXACT(NT22) and (XACT(RP+INT2), we quote the "GraphSAGE" results from Table 3 For GraphSAINT and Cluster-GCI GCN, we tune their batch size such that they have the same activation memory usage as EXACT (INT2). The results shown in Table 21 We make two main observations. First, for Reddit and Flickr, full batch training with EXACT outperforms the two sampling methods. For Yelp, subgraph sampling methods better than full batch training with EXACT. However, note
29

---

Published as a conference paper at ICLR 2022
GCN (Flickr)
GCN (Reddii)
1st Accuracy (lo)
53.0
95:375
95.350
52.5
52.6
95.300
The DJR ratio
The LMR rasio
GCN (Yelp)
GCN (ogbn arkiv)
40.5
72.2
Test Accusay (N))
72.0
40.0
71.8
330 --3
J11-1
71.6
3BL-
39.5
71.4
The D.R. ratio
The D.R ratio
Figure 10: The sensitivity study of EXACT (RP+INT2) to the D All reported results are averaged over ten random trials.
B ratio, where the model is GCN.
GrphSAGE (Fliekr)
GraphSAGE (Reddit)
52.2
Accumeyy (%)
52.0
D
DR-2
DR-1
96 96.40
51.8
96.35
DBB
51.6
GraphSAGE (Yelp)
GraphSAGE (oabn-arxiv)
62.25
72.00
Test Aceussy (5))
62.00
71.75
61.75
baciiz
71.50
bedee
71.25
61.25
DS5
The ratio
The DJR miio
Figure 11: The sensitivity study of EXACT (RP+INT2) to the & ratio, where the model is Graph- SAGE. All reported results are averaged over ten random trials.
that this gap is not from EXACT. As shown in Table without EXACT, the F1-micro of full batch GraphSAGE is 62.05%. which is much lower than that of subgraph sampling methods. Also, from Table 6, one interesting observation is that for Yelp, a much smaller batch size (As 500) may even further improve the F1-micro of GraphSAINT from 63.20% to 64.05%.
In summary, subgraph sampling methods may outperform the full batch training on some datasets (e.g., Yelp). In this case, think full batch training with EXACT cannot outperform subgraph sampling methods. If this is not the case, as shown Table 2T] full batch training with EXACT can outperform subgraph sampling methods under fixed activation memory usage.
30

---

Published as a conference paper at ICLR 2022
GCNI (Flickr)
GCNI (Reddi))
55.0
96.7
1st Aceuracy (G)
$4.5
96.6
51.0
Test
96.5
111-
30
53.5
38
96.4
JK
The DVR ratio
The D.R. ratio
GCNI (Yelp)
D/K-6
D/R -d
64.5
Teat Accuracy
64.0
63.5
The DVR ratio
Figure 12:
The sensitivity study of EXACT (RP+INT2) to the 1 All reported results are averaged over ten random trials.
R ratio, where the model is GCNII.
The ablation study of comparing GraphSAINT and Cluster-GCN to EXACT under fixed memory budget for activations. For convenience, in this table, the activation memory usage of of full batch w./ EXACT (INT2), GraphSAINT, and Cluster-GCN are the same. And the activation memory usage EXACT (RP+INT2) is lower than EXACT (INT2).
Table 21:
Dataset
Method
Accuracy (%) /Fl-micoo
GraphSAINT
50.30 0.16
Cluster-GCN
49.98 + 0.15
Flickr
Full Batch
51.97 0.20
w./ EXACT (INT2)
Full Batch
51.83 0.21
w./ EXACT (RP+INT2)
GraphSAINT
96.18 0.03
Cluster-GCN
96.03 0.05
Reddit
Full Batch
96.40 + 0.05
w./ EXACT (INT22
Full Batch
96.34 0.03
EXACT (RP+INT2)
GraphSAINT
63.20 + 0.19
Cluster-GCN
63.26 + 0.14
Yelp
Full Batch
61.95 + 0.12
w./ EXACT (INT2)
Full Batch
61.59 + 0.12
w./ EXACT (RP+INT2)
1.5.2 ENLARGING THE BATCH SIZE OF SAMPLING METHODS WITH EXACT
Here we present a case study of scaling up the batch size of GraphSAINT with EXACT on the ogbn-products dataset. As shown in Table 14] the batch size of GraphSAINT (number of nodes in the sampled subgraphs) is controlled by the "Wllk length" and "Roots", and roughly equals "Walk "Roots" (Zeng et al.) 2020). For ogbn-products, we tripled the batch size by changing "Roots" from 20, 000 to 30, 000. All other hyperparameters are left unchanged. The results are shown in Table 22 We observe that EXACT may improve the accuracy when using larger batch size. We note that EXACT can scale up the batch size to more than 3x larger. However, we found that if we further scale up the batch size 4x, there is accuracy drop compared to the baseline
31

---

Published as a conference paper at ICLR 2022
Table 22: The test accuracy of GraphSAINT the ogbn-products. All reported results are averaged over ten random trials.
Method
Test Accuracy (%)
GraphSAINT
79.03 =0.23
GraphSAINT + EXACT (INT2) 3x batch size
79.16 0024
GraphSAINT EXACT (RP+INT2) w./3x x batch size
78.54 =0.41
with the original batch size, regardless applying EXACT or not. This consistent with previous finding that larger batch size does not always lead to better performance for oghn-products (Zeng et at. al. 2020 Hu et al. 2020). We quote the sentences from the OGB paper (Hu et al. (020) to explain this counter-intuitive observation. "The recent mini-batch-basse GNNs give promising results, even slightly outperforming the full-batch version of GraphSAGE that does not fit into ordinary GPU memory. The improved performance noise and edge dropout." (Hu et al. 2020).
be attributed to the regularization effects of mini-batch
In summary, in the ogbn-products ablation study, utilize EXACT to triple the batch size of GraphSAINT, which may even improve the accuracy over the original one. Moreover, from our experiments, the 3x larger batch size performs the best oghn-products. Thus, for some datasets, there exist an optimal batch size for subgraph sampling methods. Since this optimal batch size may be beyond the capacity of the hardware, the meaning of EXACT is to enlarge the "search space" for finding this optimal batch size.
32


Reviews:
[{"review_id": "mokB9MCAJZ2", "reviewer": "Reviewer_FTNh", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 first work that explores the compressed activation in GNN training.\n2. Provide comprehensive empirical evaluation and theoretical analysis of the trade-off among memory consumption, accuracy loss, and time overhead\n3. Impressive results\n\nWeaknesses:\nThere is no major weakness of this paper, but adding more comparisons against other techniques would be great. \n1. Adding experiments to compare EXACT with other memory-saving techniques (e.g., gradient checkpointing, swapping)\n2. Adding experiments to compare EXACT with sampling approaches given a fixed memory budget. Maybe you have to choose slightly different settings of different approaches due to their different memory requirements.\n", "summary_of_the_paper": "This paper explores the training of GNN with compressed activation maps. It provides an optimized GPU implementation and comprehensively studies the trade-off among the memory saving, time overhead, and accuracy drop. \nExperimental results show that the proposed framework can reduce the memory footprint of activations by up to 32x with only 0.2-0.5% accuracy drop and 10-25% time overhead.", "summary_of_the_review": "This paper explores a novel direction and gets impressive results. I strongly recommend accepting this paper.", "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": "ae2_I-LtSEH", "reviewer": "Reviewer_eNSi", "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": "Limited memory capacity of GPUs impose severe constraints on the model/dataset size of GNNs that can be trained. That said, this paper tackles an important problem. On the positive side, the proposed technique is simple and based on proven ideas for tensor compression such as quantization and random projection. It was a pleasant surprise that those simple techniques work well to reduce the activation size with acceptable accuracy drops and computational overhead. Evaluation demonstrates promising results, which backed by solid theoretical analysis. The paper is well written.\n\nHowever, I still have several questions and concerns as follows:\n\n* *Overall Memory Savings* - It's a bit misleading to report memory savings just for activations (Table 3). The bottomline number should be overall memory savings including other objects such as input data. Also, in Section 5.3, the authors claim EXACT reduces the memory usage in training GraphSAGE on obgn-products to fit in 11GB. However, a sizable portion of memory savings come from AMP, which is orthogonal to EXACT. The authors should separately report memory savings of EXACT from those of AMP (and other techniques, if any).\n\n* *Scalability* - How effective would EXACT be if node-wise or layer-wise sampling methods were used in a mini-batch setting?  Would input data may take a dominant portion of memory usage once the activation map shrinks after aggregation? Also, how scalable would EXACT be for larger (e.g., billion-scale) datasets and/or deeper GNNs?\n\n* *Design Rationale* - EXACT applies random projection first, followed by quantization during the forward pass. What if we switch the order? Is there any convincing reason why RP-followed-by-quantization is preferred over quantization-followed-by-RP?\n\n* *Insight into Activation Compression* - The GNNs in this work are very resilient to activation compression with quite small accuracy loss regardless of their depths. Can you provide some insight into why GNNs are so robust against this somewhat extreme compression of activations?\n\nNits:\n\n* (Section 5) \"it applies the random projection *following by* a 2-bit quantization\" -> followed by \n* (Section 5.2) \"*From Table 3*, the overhead of EXACT (INT2) is roughly 12% ∼ 25%.\" -> \"From Figure 3, ...\"\n", "summary_of_the_paper": "This paper proposes EXACT, a framework for training GNNs with compressed activations with two methods: quantization and random projection. The primary design objective of EXACT is to trim down the memory consumption in GNN training while maintaining acceptable training speed and accuracy. EXACT achieves significant memory savings with 0.2-0.5% accuracy drop and 10-25% slowdown of training throughput across five models and five graph datasets.", "summary_of_the_review": "This paper introduces a simple yet effective technique to reduce the memory usage in GNN training, which demonstrates promising results. However, I still several questions/concerns for evaluation metric, scalability, design rationale, and key insight. I'd ask the authors to address them in their rebuttal.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "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": "LxuKeDYIJdX", "reviewer": "Reviewer_2GtZ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**:\n- I think the work is solving an important problem -- although I would note that we have existing works in this area, which solve the problem pretty well.\n- The results are good, especially when considering quantization only.\n- The authors did a good job choosing datasets -- they go up to OGB-products, which is nice.\n- The choice of models is good -- and I appreciate that the authors included GCNII to evaluate how their method scales with depth. I'd be delighted if they added GAT as well, though :-) -- that's really part of the reason we want their method!\n\n**Weaknesses:**\n- I am not entirely sure what the benefit of this approach is compared to sampling or historical embedding approaches is. Could you explain what is the benefit of this approach over others?\n- It's not really clear what the benefit of random projections are, given that they cause significant accuracy degradation. I am aware that they do improve the compression ratio, but I would argue that in most cases there's little incentive to use it.\n-If we consider just quantization, then there is little novelty to this work I would argue: I am not sure what is novel over the Chakrabati paper at NeurIPS 2019 is. I am aware that they focused on CNNs, but there is little reason to believe that their method would not work for GNNs.\n\nIn fact, I did actually implement the Chakrabati method myself for GNNs -- and unsurprisingly it does work. I never wrote up the results (!) or studied it too carefully. It's useful that this paper has done that though. I am unsurprised it is effective down to 1-bit integer by the way -- the gradients are much \"smoother\" for GNNs than for CNNs, as the effective batch size is very large.\n\n- There is an interesting work that was accepted to NeurIPS this year that you should compare to: \"AC-GC: Lossy Activation Compression with Guaranteed Convergence\"; they look at CNNs and Transformers, but there's no reason why you can't apply their technique to graphs as far as I can tell.\n\nIt is unfortunate that my review seems rather negative. I actually don't have a particularly negative view of the paper: I just have many questions (and unfortunately, they are related to novelty). I don't think that they're unanswerable, and I consider myself to be pretty reasonable at rebuttal if you can present new evidence / answer some questions.\n\nI would make the case that novelty is not the absolute most important thing -- but I am a little skeptical of the contributions to the literature presented by this work. However, the work is likely to be of good use to practitioners -- it's not difficult to implement many parts of this, and the results do seem impressive.", "summary_of_the_paper": "This work attempts to train GNN models with reduced memory requirements. Normally when training, we need to store activations for calculating the gradients on the backwards pass, and we typically keep these at full (32-bit) precision. This work argues that we don't need to do this, and instead we can significantly reduce the memory footprint at training time by keeping low precision activations for the backwards pass. They use two approaches for this: quantization, and random projections", "summary_of_the_review": "I am leaning towards a reject for now, but I am happy to be convinced. I am aware of how crushing it can be to authors to read these things -- and I would like to say that I think the work has strong value to the community -- but it is not necessarily a strong piece of novel research. \n\nPost rebuttal:\n\nI am not convinced that my original view has changed regarding novelty. I strongly recommend that the AC rejects the paper since I do not believe the research contribution is sufficient.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: There are numerous known methods for memory reduction used in CNNs.
This paper takes two such---quantization (Q) and random projection (RP)---and applies them to GNNs.  This is a novelty, but I agree with the reviewers: on its own this novelty would not be "surprising" enough to report at ICLR.  

The paper further goes to show empirically that these methods, when applied to a reasonable set of datasets, do indeed produce their predicted memory reductions (unsurprising) with a small ($\approx 0.5\%$) drop in accuracy (surprising, in the sense of not being something one could predict without doing the experiment).

All of the above is in one sense "just engineering", with only a small inventive step.  Any real-world deployment of GNNs would, if an army of engineers were available, naturally implement quantization and RP in order to see what kind of improvements they might make.  This would be just two more hyperparameters (R,B) to add to the sweep, and the deployment would vary them until the required accuracy was achieved in the minimum time (OOM is a red herring - one would vary batch size, other compression, or ship values to CPU in order to make progress).

However, "simply adding two more hyperparameters" is a significant increase in the deployment burden, which is where the paper's third contribution comes in: the theoretical analysis of the effects of the two processes, with straightforward but nonobvious calculations of the effect on gradient variance of the two processes, and, usefully, their interaction.  The value of this theory is twofold: first, it gives us new tools to analyse such processes; and second, it allows us to be much more judicious in the selection of these hyperparameters.

In all, the reviewers' objection of no great novelty in porting ideas from CNN  to GNN is sustained; but the authors' claim as to the value of the theory is sustained, and no reviewer provides prior art to dispute the novelty of the theory calculations.

The revised paper has already expanded the key sections in Appendix E, and added welcome experiments which strengthen the paper.  I would encourage a final copy (and certainly the poster presentation) to emphasize some of the insights over the raw experimental numbers.  As the authors hint, those numbers are subject to vagaries of what PyTorch happens to implement, while the underlying analyses are a little longer lasting.

Some other comments: 

A lot of discussion time was spent on the question of whether 0.5% is negligible.  This is entirely application dependent, and is part of the hyperparameter/architecture tuning process.

  - the extra time overhead of swapping "can go up to 80%, which is not feasible in practice".
  Not so: if choosing between OOM or 1.8x slowdown, I will of course choose the latter.
  - "for a fair comparison, we do not change any hyperparameters"
  Again, not relevant: in a real application (which is where this paper contributes), we of course change the learning rate when batch size changes.
  - "the accuracy drop of sampling may be greater than EXACT"
  Again, whether that drop is too much depends entirely on the actual application.  

And please do take a look at typos/grammar/English etc.
Decision: Accept (Poster)