DSpar: An Embarrassingly Simple Strategy for Efficient GNN training and inference via Degree-based Sparsification
Authors: Zirui Liu
Kaixiong Zhou
Zhimeng Jiang
Li Li
Rui Chen
Soo-Hyun Choi
Xia Hu
Venue: Accepted by TMLR ()

Abstract: Running Graph Neural Networks (GNNs) on large graphs suffers from notoriously inefficiency.  This is attributed to the sparse graph-based operations, which is hard to be accelerated by community hardware, e.g., GPUs and CPUs. One potential solution is to  ``sketch'' the original graph by removing unimportant edges, then both the training and inference process are executed on the sparsified graph with improved efficiency. Traditional graph sparsification work calculates the edge importance score, i.e., effective resistance, from graph topology with theoretical guarantee. However, estimating effective resistance is even more expensive than training GNNs itself. Later, learning-based sparsification methods propose to learn the edge importance from data, but with significant overhead due to the extra learning process. Thus, both of them introduce significant ahead-of-training overhead. In this paper, we experimentally and theoretically prove that effective resistance can be approximated using only the node degree information and achieve similar node presentations on graph with/without sparsification. Based on this finding, we propose DSpar, to sparsify the graph once before training based on only the node degree information with negligible ahead-of-training overhead. In practice, for the training phase, DSpar achieves up to $5.9\times$ faster than baseline with almost no accuracy drop. For the inference phase, DSpar reduces up to $90\%$ latency.

Published in Transactions on Machine Learning Research (07/2023)
DSpar An Embarrassingly Simple Strategy for Efficient GNN Training and Inference via Degree-Based Sparsification
Zirui Liu', Kaixiong Zhou', Zhimeng Jiang?, Li Li Rui Chen Soo-Hyun Choi', Xia Hu!
(Zkru, Kaiziong, Thou, Xia. HawaHurrriiieeeeee edu, {zhimengi] Sthimengj@ttmma.... @toma. edu, (liBI, rui.chenl, sh9. sht.chot)00aamasteeeoe teamsaggmmmgggcom
Rice Universily, 2 Teras A&M University, 3 "Sumsung Electronics America
Reviewed on OpenReview: https: openreview. net/ formm? id= SaVEXPuug
Abstract
Running graph neural networks (GNNs) on large graphs suffers from notoriously inefficiency. This is attributed to the sparse graph- based operations, which hard to be accelerated by community hardware, e-g., GPUs and CPUs. One potential solution is to "sketch" the original graph by removing unimportant edges, then both the training and inference processes are executed on the sparsified graph with improved efficiency. Traditional graph sparsification work calculates the edge importance score, i.e., effective resistance, from graph topology with theoretical guarantee. However, estimating effective resistance is even more expensive than training GNNs itself. Later, learning based sparsification methods propose to learn the edge importance from data, but with significant overhead due the extra learning process. Thus, both of them introduce significant ahead-of-training overhead. In this paper, experimentally and theoretically prove that effective resistance can be approximated using only the node degree information and achieve similar node presentations on graphs with/without sparsification. Based on this finding, we propose DSpar to sparsify the graph once before training based on only the node degree information with negligible ahcad-of- training overhead. In practice, the training phase, DSpar is 1.1 ~ 5.9x faster than the baselines on different datasets and models with almost no accuracy drop. For the inference phase, DSpar reduces 30% 90% latency. The code is available https: /tte:///gtttt..tt com/ varai-Otoko/DSe
1 Introduction
Graph neural networks (GNNs) have achieved great success in representation learning on graphs from various
domains, including social networks (Hamilton al. 2017 Liu ct al.) 2023a Jiang et al. 2022). biology (Hu)
et al. 2020), and recommendation system (Ying al. 2018 Liu al. 2023b Zha et al. 2023 Wang et al.
2020 Despite their effectiveness, GNNs are notoriously known for being inefficient. Specifically, GNNs are characterized by their alternating sequence of aggregation and update phases. During the aggregation phase, each node gathers information from its neighboring nodes in a layer-by-layer manner, using sparse matrix-based operations as described Fey & Lenssen (2019); Wang et al. (2019). Then, the update phase, each node updates
representation basod on the aggregated messages via dense based operations Fey & Lenssen (2019); Wang et al. (2019). In Figure 1 SpMM and MatMul are the sparse and dense operations in the aggregation and update phases, respectively. Our profiling results indicate that the aggregation phase may take up to 90% of the total training time, and similar pattern can be observed in the inference process.
The execution time of sparse operation is proportional to the number of edges in the graph. So intuitively, one straightforward way to accelerate the process to sparsify the graph by removing unimportant edges. Thus, previous work tries to produce "sketch" of the input graph by removing unimportant edges once before training, then using the sparsified graph for both the training and inference process. These works can be

---

Published in Transactions on Machine Learning Research (07/2023)
roughly divided into two streams of works. The first stream of work proposes to remove edges according to their theoretical importance score, which is calculated based on the graph topology (Spielman & Srivastava 2011). Albeit the good theoretical properties, obtaining the theoretical importance score (i.e., effective resistance) is even more expensive than training GNNs itself. The Second stream of work trics to learn the edge importance from data (Zheng et al. 2020al Chen et al. 2021 Li al. 2020 However, learning drop edges introduces another training process for identifying redundant edges, which introduces significant ahead-of-training overhead. Thus up our knowledge, no prior discussion was placed on how to accurately sparsify the graph with little time overhead for fast GNN training and/or inference. In view of such, this paper raises the question:
Can we sparsify the graph once before training with little overhead, whvile achieving similar model performance with less training and inference time?
This paper makes an attempt in providing positive answer to the above question. We experimentally and theoretically prove that the traditional edge importance score, i.e, effective resistance, can be efficiently approximated by using only the node degree information. Based our theoretical analysis, we propose Degree-based Sparsification (DSpar) ). Specifically, We first down-sampling edges based on only the node degree before training. Then we use the sparsified graph for both training and inference. As a result, the training and inference processes are both accelerated since computations are executed on a sparsified graph. We theoretically show that the node embeddings learned on the graph sparsified by DSpar are good approximations of those learned on the original graphs. Our main contributions are outlined below:
We design DSpar, highly-efficient algorithm to sub-sample the edges based on only the degree information before training. We theoretically prove that GNNs could learn expressive node repre- sentations on graphs sparsified by DSpar.
DSpar sparsifies the graph once before training, and the sparsified graph can be used for both training and inference with improved efficiency. DSpar allows to run GNNs faster in wall-clock time. For the training phase, DSpar achieves 1.1 ~ 5.9x faster than baseline with almost no accuracy drop. For the inference phase, DSpar reduces 30% ~ 90% latency compared to the baseline.
We implement DSpar as ready-to-use extension for Pytorch Geometric and Pytorch, which supports parallel sampling of edges from large graphs (Appendix A
2 Preliminary Analysis
Let g EV,E) be an undirected graph with V (v.,... (p)) and & (ei,... ,Cg)) being the set of nodes and edges, respectively. Let X E RIVidd be the node feature matrix. E g|V|I[V| is the graph adjacency matrix, where Aij
100
Poncelage lime (%)
80
time
if (v,, uz) E else A,, = 0. Ā D- + I)D-1 the nor- malized adjacency matrix, where D is the degree matrix of A I. GNNs recursively update the em- bedding of node by aggregating embeddings of its neighbors. For example, the forward pass of the 7ch Graph Convolutional Network (GCN) layer Kipf & Welling (017) can be defined as: ( ReLU(AA (O)).
40
SpMM
20
oghn proteins
Reddit
ogba products
Figure 1: The time profiling of two-layer GCNs different datasets. SpMM in the aggregation phase may take 70% ~ 90% of the total time.
(1)
where H E RVV xd is the node embedding matrix consisting node embedding h for all v E V at the tth layer and ()) X. ( is the weight matrix of the th GCN layer. In practice, A often stored in the sparse matrix format, e.g.; compressed sparse row (CSR) Fey & Lenssen (011)). From the implementation aspect, the computation of Equation can be described as:
2

---

Published in Transactions on Machine Learning Research (07 (07/202) 2022)
H = ReLU SpMM A, MatMul(H )(0) )
(2a)
where -p is Sparsc-Dense Matrix Multiplication and (atMul(;.)) is the Dense Matrix Multiplication. Unlike normal dense matrix, the elements is randomly distributed in the sparse malrix. Thus sparse opera- tions, such as SpMM have many random memory accesses and are much slower than the dense counter-pan Han et al. (2016). To get a sense of the scale, we show in Figure that for GCNs, SpMM may take roughly 70% ~ 90% of the total training time.
3 Fast Graph Sparsification
As analyzed, the sparse operations the main efficiency bottleneck for running GNNs. For sparse operations, the computation is only executed non-zero entries. To improve the efficiency, we propose to reduce the number of non-zero entries in the adjacency matrix by removing unimportant edges.
3.1 Sampling-base base graph sparsification
To improve the training efficiency while minimizing the impact of compression, we sparsify the graphs by removing unimportant edges. We sparsify the graph once before training. Thus, the training and inference processes are both accelerated since the computation done on sparsified graphs. Below we introduce how sparsify the graph in an unbiased and efficient way.
Algorithm 1: Sampling-based Graph Sparsification Spielman & Srivastava (2011)
Input: 9 = (V, sampling probability {pe) number of samples to draw Q. Output: the sparsified weighted graph G' (V,E)) with edge weights {we)aes'
E' (}+
for j -= do
Sample an edge e e~& & with replacement according to Pe if e & E' then
5
Add to with weight we Qp. end else
A
+- we + An,
Qp.
end
10 end
11
return G' = (V'8') with edge weights Jeeg
The process of graph sparsification is shown in Algorithm 1 First, given graph g = (V,E), for each edge (vi uy) E E, we need to decide the probability Pe that will be sampled (Eees Pe = 1). Then need to decide the number of samples to draw Q, which implicitly controls the sparsity of the sparsified graph G'. The sparsified adjacency matrix A' E RM of g' can be constructed as A = w. (line and line 8) if e = (c,, vy) E E' else Al., = We note that A' is an unbiased estimation of A, i.c., E[A' = A. To see this,
A Qpe
A
B[A = E
Σ 1.
Σ k=1
L Que
= Aij.
k=1
where 1e represents the event that the edge e = (vi, vz) being sampled and we have [[[1]] Pe-
It is sfrright-forward to see that |8'| = O(Q). Intuitively, the approximation error will diminish if Q approaches infinity, resulting in denser g'. The challenge is how to choose good {pelees such that we can set. Q small possible under the given error.
3

---

Published in Transactions on Machine Learning Research (07/2023)
In theory, Spielman & Srivastava (0011 shows that G' is an accurate approximation of the imput graph g if we set Pe in proportional to the effective resistance RS for each edge e. In spectral graph theory, the effective resistance Rg is often used as the distance measure between two nodes by encoding the global topology of the graph (o.g., the cluster structure) Lovász 11933 Specifically, for each edge e = (u, v), the effective
resistance Rg defined as
R₂ -X - Xx) L (X -x,,,
(3)
where I --I----A-- is the normalized graph laplacian matrix and L+ is the psudo-inverse of L. the elementary unit vector with coordinate I at position u. When the sampling probability pe
Xr E R is in proportional to Re, Spielman & Srivastava (211 shows that the sample complexity of Q is O [ log M where e a constant which controls the approximation error.
e²
Despite the good theoretical properties, estimating the effective resistance Re is non-trivial because (1) it requires approximating the pseudoinverse of the graph laplacian matrix, which is very time consuming for large graphs. (2) it is hard to parallelize the calculation for cach edge e.
Albeit. Algorithm [ is well-established,, up to our knowledge, there is no previous work investigating its usage for GNNs. This is because even estimating Re is extremely time consumiin, which counteracts the accelcration effects of graph sparsification.
In the next subsection, we will discuss how to approximate the effective resistance efficiently.
3.2 Efficiently approximating effective resistance
Here we introduce how we approximate the effective resistance of each edge using only its local information (o.g.: the node degroe). Spocifically, the following Theorem shows that for any edge e (u, v), its effective resistance Rg bounded by 2, + z,, which can be easily calculated since it only involves the node degrees.
Theorem 1 (Corollary 3.3 in Lovász (1993)). For all e =(u, v) E E, we have [ ) S R. S d 2);,
where a (a S 2) is the smallest non-zero eigenvalue of L = D AD-
In Spectral graph theory, a indicates the connec- tivity of a graph and the bound tight for well- connected graphs. Informally, the intuition is that for large graphs with cluster structures, the random walk is hard to escape from the local cluster since most of the edges are pointing to nodes within the same cluster. Thus, the local information dominates the information flow on the whole graph. From The- orem [ instead of setting Pe x Re: we propose to du + d, for edge = (u.v).
1.50%
1.25%
Percentage
1.00%
0.75%
0.50%
0.25%
0.00%
0%
20%
40%
60%
80%
100%
The Relative Error (p. P-P/Pp
set ple x 1
Figure 2: The histogram of the distribution of Pe-p for all edges in Reddit datasct.
Experimental Analysis. In Figure the distribution of Pe-'''l for Reddit dataset, where Pe x R2 and ple J. + J. We note that obtaining exact Re is impractical on large graphs since it is very time consuming. To get a sense, even the previous state-of-the-art approximation method still need 248 seconds for estimating Re. In contrast, calculating 1 + 4. for all edge = (u, consumes only 0.6 second on the same hardware. Experimentally, by setting Pe x J. + J. for each edge (u, applying Algorithm I to GNNs has negligible effects on the model accuracy (see Table D]. but significantly accclerates both the training and inference processes.
display
Po
Theoretical Analysis. Here we theoretically analyze why our begree-based sampling prorduces a good approximation of the original graph. Formally, we have the following Theorem:
Theorem 2 (Proof in Appendix B Given an input gruph G = (V,E), let A be the associated adjacency
matria and a be the smallest non-zero eigenvalue of L. Given an error parameter e, Tf we set Q O [V] log VV
4

---

Published in Transactions on Machine Learning Research (07/2023)
and for each edge (u,e) v),, set Pe d + d,, Algorithm produces sparsified graph g' (V",E') A', for any vector x E IR , we have
with
(1 (1- Σ (a - Au. S O (u,U)EE
Σ (u,z)EE'
(aa- - xx) A., & (1+ Σ (Ix - -xp) xz0) Au,e (u,F)EE
(4)
Informally, Equation suggests that the regree-based sampling preserves the graph spectral information, i.e., the eigenvalues of the normalized Laplacian matrix. Specifically, let Å A2... laly = 0 be the eigenvalue
of C associated with G, and X X2- ... X/ 0 be the eigenvalues of L' associated with the sparsified g' given by Algorithm
1 we have:
(1 - M4 S X 51 3 9M.
(5)
Here we defer the mathematical details of Equation 5 to Appendix B According to the graph theory, small (large) eigenvalues indicate the global clustering (local smoothness) structure of the graphs (Zhang et al. 2019). Thus if the eigenvalues are similar, then most of the graph properties will be preserved, e.g., cluster structures and Cheeger constant (West et al. 2001 Later we experimentally show that both the largest and smallest eigenvalues are persevered by DSpar (Section 5.2.2). In the next Section, we show that preserving spectral information is crucial for maintaining the quality of node representations.
3.3 Why degree-based sparsification works for GNNs?
Here we analyze why the sparsification works for GNNs theoretically. High-levelly speaking, the reason there is a term "Convolutional"
the name of GCN that GCN learn node representation by extracting the spectral information of the graph. According to Theorem 2 degree-based sampling preserves the spectrum (e.g,, eigenvalues) of the input graph. Thus, the learned node representation should be similar.
Here we analyze the behaviour of GCNs with sparsi- fied graph for simplicity. We note that our analysis can be applied to other GNNs. Let g be the origi- nal graph and g' be the graph sparsified by degree- based sampling. Specifically, let H!!) and H'l) be the node embeddings learned on the original graph G and sparsified graph G' 1-th layer of GCNs, respectively. Let Åι and be the largest and the smallest non-zero cigenvalue of the original C re- spectively. We have:
Relative Frubenius Norm Error against E (Cora)
0,25
||A0 Ir
0.20
0.15
0.10
0.1
0.15
0.2
0.25
0.3
0.3
0.4
0.45
05
0.6
0.7
0.8 0.9
1.0
Theorem (Proof in Appendix B
Figure 3: The relative Frobenius norm error against on Cora datasct.
H (1+1) H
(6)
The above Theorem shows that our proposed degree-based spectral sparsification leads to good approxima- tions of node embeddings learned on the original graphs, especially for well-connected graph.
Experimental Analysis: Here we experimentally validate whether our proposed degree-based spect sparsification leads to good approximations of node embeddings learned on the original graphs. Specifically, we evaluate the same GNN on two graphs, the original and the sparsifiod graph. To get sense on scale,
in Figure 3 we plot the relative Frobenius norm error [+++) H'++D against the error term for Cora [H
dataset (Sen et al. 2008), where the model is a two-layer GCN with hidden size 32, In summary, we observe for small (I 0.35), the relative Frobenius norm error is about 5% 10%. Then the error will grow rapidly 30% when 1.0. Thus the error acceptable when a proper is selected. Later we experimentally show that the model accuracy drop is negligible even with very aggressive
5

---

Published in Transactions on Machine Learning Research (07/ (07/2023)
4 Related Works and Discussion
Subgraph-based GNN training. The key idea of this line of work is to train GNNs with sampled subgraphs to reduce the number of nodes retained in memory. Based on this idea, various sampling techniques have been proposed, including the node-wise sampling Hamilton et al. (2017); Chen et al. (2017) layer-wise sampling Huang ct al. (2018): Zou et al. (2019), and subgraph sampling Chiang et al. (2019) Zeng et al. (2020). Similar to DSpar, subgraph- based methods also introduce the error during the training process. However, the key difference is that subgraph- based methods generate several subgraphs before training, and use different subgraphs at each training step. In contrast, DSpar only outputs one sparsified graph and uses it for both training and inference. Thus, methods in this category orthogonal to DSpar We experimentally show that DSpar can be integrated with subgraph-sampling based methods to achieve better efficiency without loss of accuracy.
System-level Acceleration. This research line can be roughly divided into two categories. First, some works propose distributed GNNs training systems, which focus on minimizing the communication cost among hardware (Zheng al. 2020b Wan et al., 2022b a). Second, another research line optimizes the memory access pattern of sparse operations via coalescing the memory access and fusing consecutive operations
(Zhang et al. 2022 Huang et al. 2020 Rahman et al. 2021 Wang et al. 2021 We note that our work is orthogonal to system-level acceleration methods.
Approximation. Some works try to replace the expensive sparse operations with their cheaper approxi-
mated versions [Narayanan et al.] 2022 Liu et al. 2022a by 2023c Wang et al. 2022). For example, Liu versions.
ct al.
2022a replaces the original SpMM operations with their mester-but-inaconee
Graph Sparsification. Graph sparsification provides a "sketch" of the input graph by removing redundant edges. Traditional graph sparsification uses efficient resistance as the importance score for removing the edges Spielman & Srivastava (2011). However, as we analyzed, these methods are not practical on large graphs. Then another research line tries to learn the edge importance score. Specifically, Zheng et al. (2020a) proposes a learning-baan based graph sparsification method which removes potentially task-irrelevant edges from input graphs Li et al. (2020) formulates the graph sparsification problem as an optimization objective which can be solved by alternating direction method of multiplicrs (ADMM). Chen et al. (2021) proposes to co- simplify the input graph and GNN model by extending the iterative magnitude pruning to graph areas. However, we note that these learning-basee sparsification methods have extra training process, and thus introduces siguificant ahead--f-training overhead. Moreover, learning-based methods are not scalable since it need to assign each edge an extra trainable mask variable, which is extremely expensive for large graphs.
4.1 Comparison to other sampler using node degree information
GraphSAINT edge sampler. Both the edge sampler in GraphSAINT and DSpar assign Pe Here we would like to highlight three key difference between them.
1 + 1.
First, they generate subgraphs differently. The edge sampler in GraphSAINT is used to build node-induced subgraph (Zeng et al. 2020). Namely, it first selects a subset of anchor nodes using the edge sampler and including all the edges that connect those nodes. In other words, the induced subgraph may contain edges that are not sampled. In contrast, the graph sparsified by DSpar can be viewed as edge-induced subgraph. Namely, DSpar first selects a subset of edges from the original graph and includes only those nodes that are endpoints of the selected odges.
Second, they are exccuted differently. One key difference between DSpar and the graph sampler (c.g., edge sampler and PastGCN sampler (Chen et al. 2018)) is that DSpar only sparsify the graph once before training. In contrast, the graph sampler generates different subgraphs at each training step.
1 in GraphSAINT edge sampler is Third, they are derived differently and thus are used differently. 1 + d. obtained by debiasing node embeddings in the sampled subgraph (Zeng et al., 2020). We note that this bias term stems from using the node-induced subgraph. In contrast, DSpar is derived following the traditional spectral graph theory, which mainly focuses on providing one weight sketch of the original graph.
6

---

Published in Transactions on Machine Learning Research (07/2023)
The FastGCN sampler Chen et al. (2018) shares some similarities with the DSpar method, as both techniques employ node degree information. However, they utilize this information in significantly different ways. Specifically, for a given batch of nodes, FastGCN samples neighbors for each in-batch node with a probability proportional to the square of the node degree. In contrast, DSpar uses node degree to subsample edges with a probability proportional to +., +. for any edge e in the graph.
This difference in sampling strategies leads distinct outcomes. In FastGCN, a neighbor with a higher degree has greater chance of being sampled for given node. Conversely, in the DSpar method, an edge is less likely to be sampled if the degrees of its endpoints are large. Moreover, FastGCN sampler is developed for selecting neighbors for a given node, which cannot be directly extended to the arca of graph sparsification.
4.2 Limitations
Here we would like to briefly discuss the limitation of our work. First, unlike previous thcoretical pioneer on GNN generalization eLi al. 2022 Zhang et al. 2023), Theorem 3 is not directly related to the generalization of GNNs trained on sparsified graphs. However, we would like to note that our main theoretical result (Theorem 2 is derived without making any assumptions. Obtaining a meaningful generalization bound for GNNs without any assumptions highly challenging. We leave it as a futurr work. Thus, the gencralization of GNNs trained on large graphs is only experimentally verified.
5 Experiment
We verify the effectiveness of our proposed framework through answering the following research questions:
How effective is the proposed DSpar in terms of model accuracy and efficiency compared to the random sparsification? What is the sampling time overhead of DSpar ?
Q1:
Q2: How effective is DSpar in terms of the preserved spectral information, i.e., eigenvalues?
Q3: How efficient is DSpar compared to the baseline during inference?
Q4: How sensitive is DSpar to its key hyperparameters?
5.1
Experimental Settings
We first introduce the applied baselines and datasets. Then we introduce the evaluation metrics for mea- suring the speed, and accuracy, respectively. Finally, we introduce the hyperparameter settings for DSpar Following previous works Fey et al. (202T); Hu et al. (2020); Duan et al. (2022) we focus on the transductive node classification, which is also the most common task in large-scale graph benchmarks.
5.1.1 Datasets and Baselines
To evaluate DSpar, adopt four common large scale graph benchmark datasets from different domains, namely, Reddit Hamilton et al. (2017), Yelp Zeng et al. (2020), ogbn-araiv Hu et al. (2020), ogbn-proteins Hu et al. (2020) and ogbn-products Hu et al. (2020). We evaluate DSpar under both the mini-batch training and full-batch training settings. For the mini-batch training setting, we integrate DSpar with the state-of-the-art subgraph sampling methods, i.e., GraphSAINT ZZeg et al. (2020). When integrating DSpar with subgraph sampling methods, we first sparsify the input graph by Algorithm [ and then sample subgraphs from the sparsifted graph. For the full-batch training setting, integrate DSpar with three popular models: two commonly used shallow models, namely, GCN Kipf & Welling (2017) and GraphSAGE Hamilton et al. (2017), and one deep model GCNII Chen et al. (2020). To avoid creating confusion, GCN, GraphS
and GCNII are all trained with the whole graph at each step. For a fair comparison, we use the mean aggregator for GraphSAGE and GraphSAINT throughout the paper. Details about the hyperparameters are in Appendix
We compare DSpar with random sparsification ("random" in Table D. where each edge has equal probability to be removed. We note that we only compare to the random sparsification mainly because (1) learning- based
7

---

Published in Transactions on Machine Learning Research (07/2023)
Table 1: Comparison of test accuracy (t) and training throughput (f) on five datasets. Gray cells indicate the accuracy drop is negligible (=s 0.3%) or the result is better compared the baseline. The hardware here is a single NVIDIA A40 (48GB). All reported results are averaged over ten random trials
modes
BOOK
FIRK
189K
FEZK
244M 61 PM opôn products
elgus
11.0M
7.9M
1.2M
29 19.501
Model
Methods
Rodkit
Yelp
opón
ogtn-
Arg.
Tiooushput
(spoci./s)
Thouughut (spoda/s)
Throsghput (epoch/s)
ROC-
Throughou
(epoch/s)
Thoouglput (epoch/s)
Are.
Spoedup
Graph- SAINT
Baselme
+randomm
08.02200.0
94. 06.16
5.31
5.30
03 06
51.781011
0.72
0.50
71 01002:0.2 23
71 20.00000220
12.54
13.15
75.54
70, 00.0
0,30
0.51
P500E00 24
78 0.
0.53
0.19
10.45
0.0
L,0x
1.4x
+ +18per
06:11-0.0
3.76
(1.1
63,91+0
6.79 (1.18)
71 40-000000
1881 (1.1x)
75 +5.0++9900
0.01 (2x)
9897--935
0.32 (1.7x)
10.04
1.4x
05.39-0.011
1.33
00.22:0-11
21 17
15
0.50
0.
GCN
+random
21.10
13.33800111
1,55
1000
TiSper
05:35-0.0
16.71 (2.2x)
11001+018
(1.3x)
21.2240:25
3901 (1.1x)
92.05+033
22.03 (5 8K1
0000
1.88 (3.8x)
10.20
2.8%
Graple
Rusiin
St. 16.1000001
1.33
3.00
V1 26:0.221
32.25
3.51
16.75-0.11
D.A
0.0
L,0%
SAGE
sunlun
94.97:0.04
10:29
02 21
4.79
71 26:40.32
38.53
76.88 0:1
21,92
74.05=00222
1.67
13.39
2,6x
(blll butch)
DSpur
9.97 (2.3x]
15
4.81
14.34
(3.1x)
76.71
1:07 (2.6x)
10.12
Baselsse
2.20
S402100.1
72 27
2.13
70.7911112
1.78
0.0
GCNI
05.60-0.03
4.06
63 09+000001 11
0.97
72 72:20+00355
2.16
78885
9.74
10.50
2.5x
+ DSpaa
90000
3,99 (1.8x)
0.09 (1.2%)
72.0851151
2:22 (1.3x)
74.0640611
10.38 (5.9k)
10.02
2.5x
sparsification introduces significant ahead-of-training overhead because it requires extra learning process to identify unimportant edges. Moreover, learning- based methods are not scalable since it need to assign each edge an extra trainable mask variable, which is extremely expensive for large graphs Chen et al. (2021). (2) estimating effective resistance for all edges in large graphs is not practical.
5.1.2 Evaluation metrics
We comprehensively investigate the practical usefulness of our proposed method by evaluating the trade-off between the speed and accuracy. Specifically,
Speed: Based on FLOPs, SpMM is theoretically much faster than Matmul. However, this is not true in practice due to the random memory access pattern of SpMM, which cannot be efficiently accelerated on CPUs and GPUs Han et al. (016). To evaluate the practical usage of our method, we measure the actual running speed on the off-the-shell hardwares. For Training speed, we measure the hardware throughput on GPUs (epoch/s). For Inference speed, we measure the latency on GPUs (ms). For Ahead-of-trainin overhead, we measure the wall clock time (s).
Accuracy: Following Hu et al. (2020]; Zeng et al. 2020)) we use the test accuracy for evaluating performance on Reddit, ogbn-arzic, and ogbn-producls datasets. The Fl-micro is used for Yelp dataset. The ROC-AUC is used for pro-eprot dataset.
5.1.3 Hyperparameter Settings
For graph sparsification, the hyperparameter is the number of trials Q in Algorithm D According to Theorem 2 we set Q [ og 101 where e controls the sparsity and the approximation errors. We alter the value of to see how it affects the accuracy drop. Specifically, we vary from 0.3 to 1.5.
5.2 Accuracy versus Training Efficiency (Table
5.2.1 The training efficiency
To answer Q1, summarize the training throughput and the accuracy of different methods in Table [ We also report the model performance under random sparsification, i,e,, "random" in Table [ For fair comparison, we control the number of removed edges roughly the same for both DSpar and random sparsification. In this way, they should have the same acceleration effect. We show the sparsification effect of DSpar in Table 2 The ofraiing. overhead of DSpar is given in Table 3 We also show how is the optimization process affected by DSpar Figure We observe:
Regardless of subgraph training (i.c., GraphSAINT) or full graph training (i.e., GCN, GraphSAGE, and GCNIT), the accuracy drop of applying DSpar over baselines is negligible (* 0.3%) across
8

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Table 2: The effect of DSpar [Algorithm]] D which removes 2 25 ~ 95% edges for different datasets, according to graph statistics. When applying DSpar over subgraph sampling methods, the sparsity may need to be decreased to guarantee the accuracy since subgraph sampling methods also introduce extra error.
Graph Sparsification Rate (=
ogbn-
ogbn-
ogbn- products
Dataset
Reddit
Yelp
arriv
proteins
Graph- SAINT 82.1%
73.5%
26.7%
93.1%
31.9%
GCN 82.1%
73.5%
26.7%
95.0%
79.4%
Graph- SAGE 82.1%
73.5%
26.7%
95.0%
79.4%
GCNII 82.1%
73.5%
26.7%
95.0%
Table 3: Ahead-offtrainnng overhead (sampling time) of DSpar
Graph Sparsification Rate
Sampling
Dataset
(=
(8'1)
(%)
time (s)
Reddit
82.1
2.05
Yelp
73.5
1.62
ogbn-arzic
26.7
1.4
ogbn-proteins
95.0
1.5
ogbn-products
79.4
11.0
different models and datasets. This can be explained by Theorem 3 that GNNs still learn expressive node representation on graphs sparsified by DSpar.. As we mentioned at the beginning of Section 5.2 we compare the model accuracy drop of DSpar and random sparsification under the same speedup. Interestingly, for Yelp and ogbn-proteins, random sparsification performs almost the same compared DSpar However, the accuracy drop of random sparsification is much larger on other datasets, especially ogbr-producls. We hypothesize this might because for Yelp and ogbn-proteins, the node features are more important to the model accuracy compared to the edge connectivity.
DSpar can significantly reduce the training time of GNNs with even better accuracy. As shown in Table [ summarize the training throughput (epoch/s) and speedup over baseline a single NVIDIA A40 GPU. Notably, DSpar achieves non-trivial tradc-off between accuracy and efficiency. Namely, in average DSpar brings R 2.5x speedup for full-graph training and 1.4x speedup for mini-batch training, with almost no accuracy drop or even better accuracy. The better accuracy can be explained by the fact that removing edges may impose regularization effect during training Rong al. (2019).
@ DSpar removes ~ 25% ~ 95% edges across different datasets, with negligible ahead-of- time overhead. As shown in Table 2 we summarize the sparsification effect of DSpar According to Theorem [ and Theorem 3 Q in Algorithm shoull be scale with the graph connectivity, measure by the ratio of largest eigenvalue \j to the smallest non-zero eigenvalue of the graph Laplacian matrix. In control the sparsify through directly tuning with Q = [o] When applying DSpar over subgraph sampling methods, the sparsity may need to be decreased to guarantee the accuracy since subgraph sampling methods also introduce extra error. For the ahead-of-training overhead, i... the running time of Algorithm [ is reported in Table 3 We note that we provide an optimized sampler for sampling edges in large graphs, details are elaborated in Appendix A We summarize that the overhead is negligible compared the acceleration effect of graph sparsification.
practice, we absorb the term of into c. Specifically;
O DSpar almost has the same convergence behaviour compared to the bascline. We investigate the convergence speed of DSpar, where the convergence speed is measured by the gap in training loss wet consecutive epochs. Figure 4 summarizes the training curves of GNNs trained with different
9

---

Published in Transactions on Machine Learning Research (07 2023)
(Rodlit)
GraphSAGE (Reddit)
(Reddit)
2.0
2,0
2.0
Trinig Lave
1.5
Traning Love
1.5
Training Lave
1.5
1.0
1,0
1.0
100
2000 Epocht
500
400
100
200 Epoche
100
403
160
2000 Epurchx
300
400
GCN (ogbo-arxiv)
GraphSAGE (ogbn-arxiv)
GCNI (oghn-arxiv)
2.5
2.5
Dipir
2.0
Tisting Leve
2.0
Toining Lose
Toining
1.5
3.5
1.0
100
2001
300
400
500
100
200
500
4001
500
400
1000
Epochs
Epochs
Epucla
Figure 4: Training loss on Reddit and ogbn-arriv dataset with different methods.
methods Reddit and oghn-arzäu dataset. We observe that DSpar almost has the same convergence behaviour compared to the baseline. This is consistent with our theoretical analysis that DSpar leads to good approximations of node embeddings learned on the original graphs.
5.2.2 Can DSpar preserves the graph spectral information, i.e., eigenvalues?
Top 200 cipenealucs of C on ophisandiv
eigens on
Buiisen 200 eigemalues of C uchovansiv
Bottom 200 eigenvalues of 2 on Reddit
D sandum
180-
80
Roanne thee PM
Erve
D8per
18ppr
DSper rataken
1-5
cendars
40
1.-
Singttr Volie Index
100
150
200
50
Siapela: Value Iados
130
150
203
Singudar Valua Insiex
Stngdoo
150
A Figure 5: The relative error of the top and bottom eigenvalue of L, i.e. A
sparsified by different methods.
As we analyzed, preserving graph spectral information is crucial for learning meaningful representations on graphs. To answer Q2, we calculate the relative error of the eigenvalue of the graph Laplacian matrix C almost impossible to calculate
on ogbn-arriv and Reddit dataset, respectively. We note that all of the eigenvalues of a large graph. As we mentioned, small (large) eigenvalues indicate the global clustering (local smoothness) structure of the graphs. Thus in Figure 5, we instead calculate the top-200 and bottom-200 eigenvalues of L corresponding to the original graph and sparsified graph, respectively. We observe:
@ DSpar preserves most of the key eigenvalues. Specifically, observe that for both ogbn-arziv and Reddit dataset, DSpar significantly outperforms the random sparsification in terms of the relative error of cigenvalues. For the top 200 cigenvalucs, which indicate the global clustering structure, DSpar provides an accurate approximation. That means the cluster structure is well-preserved by DSpar However for the bottom 200 eigenvalues, which indicate the local smoothness, DSpar has 5 40% relative errors for these bottom cigenvalues. contrast, random sparsification almost has 100% relative error, i.c., failing to preserve this part of information. Our analysis also partially explains why GNNs learned on graph with random sparsification have much worse performance these two datasets.
10

---

Published in Transactions on Machine Learning Research (07 (072))
200
T8003
Buadine
115
1165
33.4
314
12
07.0
76.1
OCKGOM
AO ogfn-proteins
GONI
Redlit
Figure 6: Inference latency comparison on single NVIDIA A40 (48GB) GPU (lower is better). "OОM" means out-of-memory. Compared to the baseline, DSpar reduce R 30% ~ 90% inforence latency.
5.2.3 The Inference efficiency
For GraphSAINT, the subgraph sampling is only applied to the training process. Thus, they do not affect the inference latency of GNNs. To answer Q3, Figure i compares the inference latency of different models on the original graph and the graph sparsified by DSpar. We observe that
According to Figure 6. DSpar reduces s 30% ~ 90% inference latency. Notably, on Yelp datasct, DSpar reduces only 30% inference latency, although removes more than 70% edges (Table 2 This is mainly because for Yelp dataset, graph-based operations account for a relatively small percentage of the total time compared to other datasets. For other datasets, we observe that DSpar significantly reduces up to x 90% inference latency.
GCN (Redii)
GraphSAGE (Rodhi0
97
95-
Tox. No
Tos. Nourayy (N)
96
94
Dipa
D5psz
92
nndem
poken
Tandkr
Dasclinz
Bracline
27.1
66.1
12.1
$5.1
02.3
94.9
27.1
56.1
82.1
89.1
92.8
94.9
27.1
66.1
82.1
69.1
92.6
94.
Graph Spassit(h))
Graph Spanityho
Gauph Sparsil(3
Figure 7: Accuracy versus the graph sparsity on Reddit dataset. Here the graph sparsity equals the percent- age of removed edges. All results are averaged over ten random trials.
5.3 Hyperparameter sensitivity analysis
As we analyzed, DSpar has only one hyperparameter, namely, the number of trial Q for controlling the graph sparsity. In this subsec- tion, to answer Q4, we explore the sensitivity of hyperparameters Q for DSpar As we mentioned, we set Q log IV according to Theorem 3 where e controls the approximation error. We alter the
GraphS (ogbn- (rodd---rduts))
75
DSper
Random
76
Accuracy
74
value of from 0.3 to 1.5 to check the relationship between the graph sparsity and the accuracy drop. As shown in Figure 7 the accuracy drop becomes larger when edges are being removed. This is consis- tent with the theoretical analysis in Section 3.3 that have larger approximation errors when the graph sparsity is high. In addition to studying dense graphs like Reddit, we also performed a sparsification experiment on a large sparse graph, specifically gobn-products, us- ing GraphSAGE. We observe that in this case, the accuracy drop of random sparsification and DSpar is more significant. This is mainly because proouuts is much sparser than Reddit, making it more sensitive edge removal. We also observe that DSpar significantly outperforms the random baseline, which is consistent
87.8
90.9
93.0
94.4
Graph Spansit(h))
Figure 8: Accuracy versus the graph sparsity on ogbn-products.
11

---

Published in Transactions on Machine Learning Research (07/2023)
with the theoretical analysis. Furthermore, when remove roughly 95% of edges in Reddit dataset, the accuracy drop is roughly 0.8 ~ 1.2% for different models, which is still acceptable when considering a 95% sparsity. In practice, suggest selecting Q Vilog [V] according to the accuracy drop and the efficiency constraint by adjusting
6 Conclusions and Future work
We propose DSpar simple-yet-effectiee framework for training GNNs with compressed tensors, which can be plugged into most of the existing solutions to save memory. We demonstrate the potential of DSpar for the practical usage by systematically evaluating the trade-off among the memory-saving, time overhead, and accuracy drop. Future work includes (1) evaluating DSpar under the distributed training setting; (2) exploring other types of graph sparsification methods.
References
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In International conference on machine learning. PMLR, 2017.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. aiv preprint NSW:1181111244 2018.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pp. 1725 1735. PMLR, 2020.
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-1706. PMLR, 2021.
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.
Keyu Duan, Zirui Liu, Peihao Wang, Wenqing Zheng, Kaixiong Zhou, Tianlong Chen, Xia Hu, and Zhangyang Wang. A comprehensive study on large-scale graph training: Benchmarking and rethinking, In siitt Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Mamifolds, 2019.
Matthias Fey, Jan E. Lenssen, Frank Weichert, and Jure Leskovec. Gnnautoscale: Scalable and expressive
graph neural networks via historical embeddings. In International conference machine learning, 2021.
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference Neural Information Processing Systems, pp. 1025- 1035, 2017.
Song Han, Xingyu Liu, Huizi Mao, Jing Pu, Ardavan Pedram, Mark A Horowitz, and William Dally. Eic: Efficient. inference engine compressed deep neural network. ACM SIGARCH Compuler Archilecture News, 44(3):243 254, 2016.
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 N:Xi::2005.00681 2020.
Guyue Huang, Guohao Dai, Yu Wang, and Huazhong Yang. Ge-spmm: General-purpor sparse matrix- matrix multiplication on gpus for graph neural networks. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1-12. TEFE, 2020.
12

---

Published in Transactions on Machine Learning Research (07/2023)
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph repre- sentation learning. In Advances in Newral Information Processing Systems, 2018.
Zhimeng Jiang, Xiaotian Han, Chao Fan, Zirui Liu, Na Zou, Ali Mostafavi, and Xia Hu. Fmp: Toward fair graph message passing against topology bias. arXiv preprint wrXim:222..44887 2022.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017. URL https://openrerrioo net/forumiid o SJU4ayYgT
Hongkang Li, Meng Wang, Sijia Liu, Pin-Yu Chen, and Jinjun Xiong. Generalization guarantee of training graph convolutional networks with graph topology sampling. In International Conference on Machine Learning, pp. 13014 13011. PMLR, 2022.
Jiayu Li, Tianyun Zhang, Hao Tian, Shengmin Jin, Makan Fardad, and Reza Zafarani. Sgen: A graph sparsifier based on graph convolutional networks. In Pacific-Ass Asia Conference on Knowledge Discovery and Data Mining, pp. 275-287. Springer, 2020.
Zirui Liu, Shengyuan Chen, Kaixiong Zhou, Daochen Zha, Xiao Huang, and Xia Hu. Rsc: Accelerating graph neural networks training via randomized sparse computations. arXiv preprint 0rXiv:2210.10737, 2022a.
Zirui Liu, Kaixiong Zhou, Fan Yang, Li Li, Rui Chen, and Xia Hu. Exact: Scalable graph neural networks training via extreme activation compression. In International Conference on Learning Representations, 2022b. URL htttps://ppenrviieee net/foruuriddvvaaaagg, _
Zirui Liu, Zhimeng Jiang, Shaochen Zhong, Kaixiong Zhou, Li Li, Rui Chen, Soo-Hyun Choi, and Xia Hu. Editable graph neural network for node classifications. arXiv preprint ar arXi::2305.1553 15522, 2023a.
Zirui Liu, Qingquan Song, Li Li, Soo-Hyun Choi, Rui Chen, and Xia Hu. Pin:: pruning based multi-size embedding for recommender systems. Fronliers in Big Dala, 6:1195742, 2023b.
Zirui Liu, Guanchu Wang, Shaochen Zhong, Zhaozhuo Xu, Daochen Zha, Ruixiang Tang, Zhimeng Jiang, Kaixiong Zhou, Vipin Chaudhary, Shuai Xu, et al. Winner-takoall column row sampling for memory efficient adaptation of language model. arXie preprint Xiv::22305. 15265, 2023c.
László Lovász. Random walks on graphs. Combinatorics, Paul erdos is eighty, 2(1-46):4, 1993.
S Deepak Narayanan, Aditya Sinha, Prateek Jain, Purushottam Kar, and SUNDARARAJAN SELLA- MANICKAM. Iglu: Efficient GCN training via lazy updates. In International Conference Learning Representations, 2022. URL https://openreviae
net net:/Eorum2id-5kQ1111111
Md Khaledur Rahman, Majedul Haque Sujon, and Ariful Azad. Fusedmm: A unified sddmm-spmm kernel for graph embedding and graph neural networks. In 2021 IEEE International Parallel and Distributed Processing Symposium (TPDPS), pp. 256 266. TEFE, 2021.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional 2019.
networks on node classification. arXie preprint
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Rliassi-Rad. Collec- live classification in network data. AT magazine, 29())3 10999993--00 2008.
Daniel A Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. STAM Journal on Computing, 40(6):1913-199)) 2011.
Cheng Wan, Youjie Li, Ang Li, Nam Sung Kim, and Yingyan Lin. Bns-gen: Efficient full-graph training of graph convolutional networks with nartition-parallliia and random boundary node sampling. Proceedings of Machine Learning and Systems, 4:673 4:673-693, 2022a.
13

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Cheng Wan, Youjie Li, Cameron R. Wolfe, Anastasios Kyrillidis,, Nam Sung Kim, and Yingyan Lin. Pipegen: Efficient full-graph training of graph convolutional networks with pipelined feature communication. arXiv preprint orXie:2203.10430 2022b.
Guanchu Wang, Zirui Liu, Zhimeng Jiang, Ninghao Liu, Na Zou, and Xia Hu. Towards memory efficient training via dual activation precision. orv preprint or Xrx:22200..0 187, 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-centric, highly-performant package for graph neural networks. arXiv preprinl arXiv: 1at:1999.0130 2019.
Bing-Hsiang Wang, Xia Hu, Haifeng Jin, Qingquan Song, Xiaotian Han, and Zirui Liu. Autorec: An automated recommender system. In Proceedings of the 14th ACM Conference Recommender Systems, pp. 582-584, 2020.
Yuke Wang, Boyuan Feng, and Yufei Ding. Te-gnn: Accelerating sparse graph neural network computation via dense tensor core gpus. arXiv preprint Xrx:2:2112 02052, 2021.
Douglas Brent West al. Introduction graph theory, volume Prentice hall Upper Saddle River, 2001.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery 8 Data Mining, pp. 974-983, 2018.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Raigopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. In International Conference on Learning Representa- tions, 2020. URL
Daochen Zha, Louis Feng, Liang Luo, Bhargav Bhushanam, Zirui Liu, Yusuo Hu, Jade Nie, Yuzhen Huang, Yuandong Tian, Arun Kejariwal, et al. Pre-train and search: Efficient embedding table sharding with pre-trained neural cost models. Proceedings of Machine Learning and Systems, 5, 2023.
Hengrui Zhang, Zhongming Yu, Guohao Dai, Guyue Huang, Yufei Ding, Yuan Xie, and Yu Wang. Under- standing gun computational graph: A coordinated computation, io, and memory perspective. Proceedings of Machine Learning and Systems, 4:467-484, 2022.
Jie Zhang, Yuxiao Dong, Yan Wang, Jie Tang, and Ming Ding, Prone: Fast and scalable werw represen- 2019.
tation learning. In IJCAI, volume 19, pp.
Shuai Zhang, Meng Wang, Pin-Yu Chen, Sijia Liu, Songtao Lu, and Miao Liu. Joint edge-model sparse learning is provably efficient for graph neural networks. In The Eleventh International Conference on Learning Representations, 2023. URL httts:://penreviiie http::///pppreeeeeeeee///oooooop
CVF.
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 on Machine Learning, pp. 11458 11468. 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 JEFE/ACM 10th Workshop on Irregular Applications: Archilectures and Algorithms (IA3), pp. 36-44. IEEE, 2020b.
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. or Xio preprinl or
2019.
14

---

Published in Transactions on Machine Learning Research (07 (07/202) /023)
A Implementations
We use CPUs for sparsifying graph using Algorithm ! which because the whole graph may exceed the GPU memory. We emphasize that Algorithm sparsifies the graph by sampling with replacement (linc 3). Thus, the sampling process can be easily paralleled. In practice,lo avoid the numerical precision problem for graphs with more than 224 edges | we use torch.double the precision for the probability tensor {peJees, which is not supported for most of the built-in sampling methods in Pytorch. Thus, implement Algorithm | in C++ and parallel it base OpenMP. We build it extension for Pytorch, which can be called using Pytorch API.
B Theory
B.1 Proof of Theorem 2
Theorem (Proof in Appendix B Given on imput graph G = (V,E), let A be the associated adjacency
matria and a be the smallest non-zero eigenvalue of C. Given an error parameter e, If we set Q = O [ log IV
and for each edge e = (u, v), we set + a Algorithm produces sparsified graph G' = (V', E¹) with A', for any vector V we have
R
(1 (1-5) Σ (o) S (O,
Σ (a,v)EE'
(ot A S 51++ Σ (u,D)EE
(wt (ux) 22,))
(4)
Proof- Below first introduce the necessary concepts and tools for deriving Theorem 2 be the signed eege-x incidence matrix, given by
Let B E R
if o is edge e's head, B((,,) = { if v is edge e's lail, otherwise.
(7)
Let W RlEXXEE be a diagnoral matrix such that We. A.. Then we define the projection matrix II II W BC B W We note that have the following properties Spielman Srivastava (2011):
II is a diagonal projection matrix,
|| 11,e.
IIII II.
Il,e AgRe.
Let S E RIE be the diagonal random matrix representing the sampling process in Algorithm such that
##f times e is sampled)
S
(8)
Qpe
Then we have the following Lemma:
Lemma 1 (Lemma 4 in Spielman & Srivastava. 2011 the sampling process such that
Let S be the diagonal random matrir representing
ISSI
Sc,
Then
Yx E RI (1- Lx T L'x < (1 + c) Lx.
(9)
where L B CBBBi matria
is the normalized Laplacian matrix and L' = B W SW B is the sparsified Laplacian
!https:/ http:////wwwaattttoooommmm/////e
15

---

Published in Transactions on Machine Learning Research (07/2023)
Sampling Q edges from 9 corresponds to sampling Q columns from II, write
IIIII =
Σ Seelll ee
(10)
##of times e sampled)
II. IT
(11)
Qpe
11.e IT.
(#of times sampled)
1e
(12)
Q
Pe VPe
Q
y:
(13)
1=1
where y1 UQ are drawn independently with replacement from the distribution
ILe VPc.
y
with probability pe-
(14)
Recall that according to Theorem 1 know that for any edge = (u, we have 1 전 S Rs <
d + } Let Pe and p'e be the sampling probability for edge e proportional to R. and J_, + d.
respectively. Let S and S' be the random matrix with Pe and ph. respectively. Let y and y be the distribution defined above associated with Pe and pee respectively. Then
P'e
2
aRe
Pe 2
a
(15)
Σ
Re 2 Ex=
(E, du de
For the norm of y, we have:
1
Ee Re R. = Σ Re R -
13y123
[T
IT2
Pe
Pe
E,6
Re
We note that we have Ee Rs = |
from the definition of effective resistance Spielman & Srivastava
2011
Then we have
III 12
2
11.
2
2 (1) 1)
1/'1113
1 <
(16)
P'b
a
Pe
a
Q
IIS IIII
E
y.u."
T Ey'y L'
(17)
Q
Lemma 2 (Lemma in Spielman Srivastava (2011))
Let p be the probabilily distribution over Ω E RM
such that ||y||2 M and Eyy
1, we have
Q
log Q Q 1),
y:v: Eyy 1l2 < min(CM
(18)
i=1
where C is an absolute constant.
By Taking Q lo M//e, have
16

---

Published in Transactions on Machine Learning Research (07 (07/2023)
EIs' III S a²
(19)
By Lemma this completes the proof of the theorem.
B.2 Derive Equation (5)
By Courant-Fischee Theorem, we know that the i-th eigenvalue of L satisfies
x Le
A min
max K Kidim (K) =i FEK x
(20)
where dim(K) is the number of lincarly independent vectors that form a basis for K.
Similarly, for L', the i-th eigenvalue X can be expressed as:
x T LL'x
X =
min
max mE K
(21)
Kidim
x x
Now, by Theorem 2 we know that for any æ. we have
(1 - Lo (1+ )xx Lx,
(22)
Let K; be any subspace with dimension i. Then, for any vector x E K,, we have:
x La (1
L' LL' I (1
Cx
(23)
x x
1 x
c'' achieves maximum at x', now we have x
Suppose
L'
x. L'
max x #t
(24)
x T x
T xx'
(1 + E x¹ Lx
(25)
xr' xx
La
$ (1+ max
(26)
Ke x x
By applying the similar technique on the left side of the inequality, we have (1 - 9) max Combine the left side and right side inequality together, we have:
LL'e
maX x
Lx x.
x
L'' S (1 (1+
T La
(1
max #EK,
max K
max #EK, x
(27)
x
Tx
Please note that the above inequality holds for any subspace K; with dimension i. Let K; be the subspace that achieves the minimum in the Courant-Fische Fischer theorem for eigenvalue x in Equation 20 We have
T L' S (1 + S max L (1 + S):,
max KEK,
(28)
x x
0 øe x x
17

---

(1+ Published in Transactions on Machine Learning Research (07 (0722)23)
Now by definition of the minimum, we know that
X. LL
x: T L'
max ØEK: T x
2
min ( KE)==
max
X
(29)
x x
By connecting the above two inequality together, we have
X S (1+ a
(30)
Similarly, by applying the same technique on the left side, we can obtain
(1- S
(31)
By connecting the above inoquality together, we obtain
(1 - 5 J
(32)
B.3 Proof of Theorem 3
Theorem 3 the direct extension of Theorem 2 to GNN area. In this proof, aim to establish bound on the difference between the activations of two GCNs with different Laplacian matrices. We compute the Frobenius norm of the difference between these activations and derive an upper bound by applying the triangle inequality and the properties of the matrix 2-norm.
Theorem (Proof in Appendix B
HH H H
H H
(6)
Proof. First, by the defination of GCN, we have
( ReLU(((I "O))
(33)
H1(+1) = ReLU -
(34)
Then we have
H - H1(0-)/| < [[(c H (
$ = (0
(35)
The above inequality directly from the fact that for any two matrix X and Y, have |XY |F S |X||||||| I ||||||
By definition 2-norm, we have
|1 |1C- 2')12= [1)l=
sup x [C L') x1
(36)
Suppose the above supremum is achieved at mo, then
18

---

Published in Transactions on Machine Learning Research (07 2023)
(C - 22) 2 Lao 3b L'
$ 2i T Lang
(1
) Lav
(From Theorem
(37)
a
m Lav
sup - x Lx
=1
A1
(38)
By combining the above inequality and Equation
35
we have
((++))
H
H
= A1
(39)
C Experimental Settings
C.1 Software and Hardware Descriptions
Table 4: Package configurations of our experiments.
Package
Version
CUDA
11.1
pytorch sparse
0.6.12
pytorch_scatter scatter
2.0.8
pytorch geometric
1.7.2
pytorch OGB
1.9.0
1.3.1
All experiments are conducted on a server with four NVIDIA 3090 GPUs, four AMD EPYC 7282 CPUs, and 252GB host memory. We implement all models based on Pytorch and Pytorch Geometric. 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
C.2 Statistics of benchmark datasets
We give the detailed statistics and URLs for all datasets used in our experiments Table 5 We follow the standard data splits and all datasets are directly downloaded from Pytorch Geometric or the protocol of OGB Hu et al, (2020).
Table 5: Dataset Statistics.
Dataset
Nodes
Edges
Feat
Classes
Label Rates
Reddit
232,965
11,606,919
602
41
65.86%
Yelp
716,847
6,977,409
300
100
75.00%
ogin-arziv
169,343
1,157,799
128
40
53.70%
ogbn-proteins
169,343
1,157,799
128
40
53.70%
ogbn-products
2,449,029
61,859,076
100
47
8.03%
19

---

Published in Transactions on Machine Learning Research (07 (07/2023)
C.3 Hyperparameter Settings
Regarding Reddit, and Yelp datasel, we follow the hyperparaneter configurations reported in the respective papers as closely as possible. Following Fey et al. (2021). we clips the gradient during training. The "Gradient Clipping" in below tables indicate the maximum norm for gradients. "Gradient Clipping= 0.0" means we do not clip the gradients in that experiment. Regarding ggbn-arziv and pubn-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 summarizes the hyperparameter configuration of GraphSAINT. Table Table 7 and Table 8 summarize the hyperparameter configuration of full-Batte -al--Batch GCN, full-Batch GraphSAGE, and full-batch GCNIT, respectively.
Table 6: Configuration of Full-Batch GCN.
Training
Archtecture
Dataset
Learning Rates
Gradient Clipping
Hidden
Epochs
Dropout
BatchNorm
Layers
Dimension
Reddit
0.01
400
0.5
0.5
Yes
2
256
Yclp
0.01
500
0.1
0.5
Yes
2
512
ogbn-
0.01
1000
0.5
0.0
No
3
256
proteins
ogbn-
0.01
500
0.5
0.5
Yes
3
128
arviv
Table 7: Configuration of Full-Batch GraphSAGE.
Training
Archtecture
Dataset
Learning Rates
Gradient Clipping
Hidden
Epochs
Dropout
BatchNorm
Layers
Dimension
Reddit
0.01
400
0.5
0.5
Yes
2
256
Yelp
0.01
500
0.1
0.5
Yes
2
512
ogbn-
0.01
500
0.5
0.5
Yes
3
128
arriv
ogbn-
0.01
1000
0.5
0.0
No
3
256
proteins
ogbn-
0.002
500
0.5
0.5
No
3
256
products
Table 8: Configuration of Full-Batch GCNII.
Training
Archtecture
Dataset
Learning Rates
Gradient Clipping
Hidden
Epochs
Dropout
BatchNorm
Layers
Dimension
Reddit
0.01
400
0.5
0.5
Yes
4
256
Yclp
0.01
500
0.1
0.5
Yes
4
512
ogbn-
0.01
1000
0.5
0.0
No
4
256
proteins
ogbn-
0.001
1000
0.1
0.1
Yes
16
256
arriv
20

---

Published in Transactions on Machine Learning Research (07/202) 2023)
Table 9: Training configuration of GraphSAINT.
RandomWalk Sampler
Training
Archtecture
Dataset
Learning Rates
Gradient Clipping
Hidden
Walk length
Roots
Epochs
Dropout
BatchNorm
Layers
Dimension
Reddit
2000
0.5
Yelp
2
1250
0.01
0.1
0.5
Yes
2
512
ogbn-
3
10000
0.01
0.5
0.5
Yes
3
256
araio
ogbn-
proteins
3
10000
0.01
120
0.5
0.0
No
3
256
oybn-
3
20000
0.01
20
0.3
0.0
No
3
256
products
21


Reviews:
[{"review_id": "YyqmTQ0vtY", "reviewer": "Reviewer_t4jW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper provides a simple method with solid theoretical analysis and experimental results showing that the proposed method accelerates GCN training and inference at almost no cost of accuracy.\nHowever, the main results shown in Table 1 indicate that the tasks evaluated are not very sensitive to sparsification, as even random sampling achieves similar results. In Figure 7, the results of random sparsification only drops by around 3% even at 94.9% sparsity. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces DSpar, a novel graph sparsification method that approximates effective resistance using only node degree information, significantly reducing ahead-of-training overhead. The authors experimentally and theoretically demonstrate that this approach results in similar node representations on sparsified and non-sparsified graphs. DSpar leads to up to 5.9x faster training and up to 90% reduced latency during inference, while maintaining accuracy, addressing the inefficiencies of running Graph Neural Networks (GNNs) on large graphs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Is there a benchmark that is more sensitive to edge sparsification? At least with more significant drops with random sparsification at sparsity 94.9%.\n\n2. Compare with other graph sparsification methods in the experiments. Currently only random sparsification is compared. It would be good to understand the difference with other algorithms.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "bdv2XIuDPg", "reviewer": "Reviewer_VvH3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The authors' algorithms are backed by some theoretical guarantees, and although simple, they are highly effective.\n\n2. The experiments are meticulously conducted and provide comprehensive information for reproducibility.\n\nWeakness\"\n\n1. My main concern is that the theoretical support is not strong enough, because there is no analysis of generalization, and the difficulties in deriving the relevant proofs are not adequately explained. 2. Here are some recent works providing generalization analysis for GNN sparsification, see [1] & [2], which may inspire the authors to strengthen their theoretical contributions. \n\n[1] Hongkang Li, et al. \"Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling.\" In International Conference on Machine Learning, pp. 13014-13051. PMLR, 2022.\n\n[2] Shuai Zhang, et al. \"Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks.\" In The Eleventh International Conference on Learning Representations.\n\n2. I believe [3] adopts a comparable approach that utilizes degree information to identify crucial nodes, which is similar to the technique outlined in this paper. It would be helpful if the authors could provide a comparison between their method and [3].\n\n[3] Jie Chen, et al. \"FastGCN: Fast learning with graph convolutional networks via importance sampling.\" In International Conference on Learning Representations. International Conference on Learning Representations, ICLR, 2018.\n\n3. This paper lacks numerical experiments to justify the tightness and accuracy of the theoretical bound. As a result, it is challenging to validate the theoretical contributions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper borrows the idea from an existing work (Spielman & Srivastave 2011) to design a graph sparsification algorithm, DSpar, to sub-sample the edges based on the degree information before training. This paper also proves the theoretical guarantees for using DSpar in reserving the expressiveness of the node representations on the graph.  The numerical experiments indicate that the proposed algorithm can attain up to 5.9 times faster than the baseline while maintaining comparable test accuracy. Moreover, during the inference stage, the algorithm can reduce 90% of the latency.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Please add corresponding experiments to justify current theoretical results, such as plotting $||H^{(l+1)}-H'^{(l+1)}||_F$ against $\\epsilon$, $\\lambda_1$, or $\\alpha$ to validate eqn. (6).\n\n2. A brief explanation of the technical challenges in deriving the theoretical results and a proof sketch should be added. Additionally, if required, more theoretical results can be included on generalization analysis or convergence analysis.\n\n3. I recommend that the authors revise Algorithm 1 to avoid creating confusion that this paper simply utilizes an existing algorithm. The current version could lead to such misunderstandings.\n\n4. Please include a comparison with FastGCN, see [3].\n\nQuestions:\n\n1. Can the author provide insight into why the citation network and the protein-protein interaction network differ in terms of graph sparsification rate?\n\n2. I would like more clarification regarding Figure 4 and the corresponding outcomes. I am thinking that the singular vector is more significant than the singular value.", "broader_impact_concerns": "I do not see any concerns about the ethical implication of this work. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "RswbNBcPGl", "reviewer": "Reviewer_rtCN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n+ The paper is clearly written. The ideas are well motivated, the theoretical analysis is mostly sound, and the empirical evaluation covers different aspects to help readers understand the effect of the algorithm. \n+ The proposed method is simple and can be efficiently performed in practice on large scale graphs. The algorithmic parameters are connected to spectral graph theory. The analysis exhibits some level of technical depth. \n+ The experiments are performed thoroughly on multiple standard benchmarks and on both training and inference. The performance gains seem reasonably high (1.4 - 2.8x speedup). \n\n\nWeaknesses\n\n- Issues in theoretical analysis: \n    - Proof of Theorem 2: The properties of the $\\Pi$ matrix seem a bit problematic. If $\\Pi$ is a diagonal matrix and $\\Pi \\Pi = \\Pi$, that means for each diagonal element, we have $\\Pi_{e,e}^2 = \\Pi_{e,e}$, which means $\\Pi_{e,e} = 1$ or $0$. This doesn’t sound correct. Is there a typo?\n    - Proof of Theorem 2: How do you derive the last inequality (the bound on $||y||^2_2$) in (16)? When we plug in the expression of (14), it seems there would be some $\\sum_e R_e$ term appearing in the $||y||^2_2$ expression (due to normalization of all $p_e$ to 1). How do you proceed to the bound of $|\\mathcal{V}|-1$?\n    - Derivation of (5) in Appendix B.2: It seems to me that the process to go from (21) to (22) is via assigning $x$ as the k-th eigenvector of the Laplacian $\\mathcal{L}$. However, for (22) to hold, wouldn’t it require that $\\mathcal{L}$ and $\\mathcal{L}’$ have the same eigenvectors? Otherwise, if $x^T\\mathcal{L}x=\\lambda_i$, we cannot derive $x^T\\mathcal{L}’x=\\lambda_i$ since some other vectors $x’\\neq x$ would correspond to $x’^T\\mathcal{L}’x'=\\lambda\\_i'$. \n- While the edge sampling probability $p_e$ is justified via spectral graph theory, the expression of $\\frac{1}{d_u}+\\frac{1}{d_v}$ also looks exactly the same as the sampling probability defined by the GraphSAINT edge sampler. There may be some deeper connections between DSpar and GraphSAINT in addition to the fact that one does sparsification and the other performs subgraph sampling. The authors should elaborate on this aspect. \n- The error due to the degree based sparsification highly depends on the graph structure. The theoretical bound on error / sampling complexity may not be practically good if the graph does not exhibit clear clustering structures. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents an algorithm to sparsify the input graph for GNNs in order to speedup the execution speed of model training and inference. The sparsification is operated on the global graph level based on importance edge sampling, where the importance score is inversely proportional to the degree of the end nodes. Though the degree-based sampling is simple, it is justified by spectral graph theory that such approximation preserves the spectrum of the original graph (highest and lowest eigenvalues of the graph Laplacian). The light-weight sparsification algorithm leads to low pre-processing overhead and thus speedup in end-to-end model execution. The overall model accuracy is well preserved on graphs with global clustering structure. \n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The following changes would be critical for me to consider the paper as above the acceptance threshold:\n* The fixes regarding the theoretical derivation of Theorem 2 and (5). Details have been elaborated in the “Weaknesses” section\n* From the idea / model design level, an in-depth comparison with the GraphSAINT edge sampler would be great. \n\nMinor issues:\n* Fig 4: should the x-axis be “Eigenvalue index” or “Singular value index”?\n", "broader_impact_concerns": "As far as I can see, there is little negative societal impact or ethical implication. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: There are a few additional issues that the authors should consider addressing before publication:
* Figure 2 is a bad visualization of a distribution - showing some kind of histogram would be a lot more informative
* Table 2 only shows sparsification rate and did not show latency improvement numbers (but the text refers to this table for latency improvement)
* In Section 3.3 it would be good to clarify that this is evaluating a single GNN on 2 graphs, the original vs the sparsified, rather than also training on these two types of graphs.
* Claiming “xxx% improvement” without quantifying the benchmark / model type is a bit misleading, I would suggest being scientific about it and avoid over-selling.

Decision: Accept (poster)