Sketch-GNN: Scalable Graph Neural Networks with Sublinear Training Complexity
Authors: Mucong Ding
Tahseen Rabbani
Bang An
Evan Z Wang
Furong Huang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Neural Networks
Scalability
Tensor Sketch
Sublinear Complexity

Abstract: Graph Neural Networks (GNNs) are widely applied to graph learning problems such as node classification. When scaling up the underlying graphs of GNNs to a larger size, we are forced to either train on the complete graph and keep the full graph adjacency and node embeddings in memory (which is often infeasible) or mini-batch sample the graph (which results in exponentially growing computational complexities with respect to the number of GNN layers). Various sampling-based and historical-embedding-based methods are proposed to avoid this exponential growth of complexities. However, none of these solutions eliminates the linear dependence on graph size. This paper proposes a sketch-based algorithm whose training time and memory grow sublinearly with respect to graph size by training GNNs atop a few compact sketches of graph adjacency and node embeddings. Based on polynomial tensor-sketch (PTS) theory, our framework provides a novel protocol for sketching non-linear activations and graph convolution matrices in GNNs, as opposed to existing methods that sketch linear weights or gradients in neural networks. In addition, we develop a locality-sensitive hashing (LSH) technique that can be trained to improve the quality of sketches. Experiments on large-graph benchmarks demonstrate the scalability and competitive performance of our Sketch-GNNs versus their full-size GNN counterparts.

Sketch-GNN: Scalable Graph Neural Networks with Sublinear Training Complexity
Mucong Ding, Tahseen Rabbani, Bang An, Evan Z. Wang, Furong Huang
Department of Computer Science, University of Maryland (mcding, trabbani, bangan, furongh) @ ed.umd.edu
Abstract
Graph Neural Networks (GNNs) are widely applied graph learning problems such as node classification. When scaling up the underlying graphs of GNNs to a larger size, we are forced to either train on the complete graph and keep the full graph adjacency and node embeddings in memory (which is often infeasible) mini-batch sample the graph (which results in exponentially growing computational complexities with respect to the number of GNN layers). Various sampling masseing-bbsedd and wawrrical-emeedding--eae growth of complexities. However, none of these solutions eliminates the linear dependence on graph size. This paper proposes a sketch-basee algorithm whose training time and memory grow sublinearly with respect to graph size by training GNNs atop a few compact sketches of graph adjacency and node embeddings. Based polynomial tensor-sketch (PTS) theory, our framework provides novel protocol for sketching non-linear activations and graph convolution matrices in GNNs, opposed existing methods that sketch linear weights gradients in neural networks. In addition, we develop locality sensitive hashing (LSH) technique that can be trained improve the quality of sketches. Experiments on barge-graph, benchmarks demonstrate the scalability and competitive performance of our Sketch-GNNs versus their full-size GNN counterparts.
methods are proposed to avoid this exponential
Introduction
Graph Neural Networks (GNNs) have achieved state-of-the-ar graph learning in numerous applica- tions, including classification [27], clustering [3], recommendation systems [43], social networks [16] and more, through representation learning of target nodes using information aggregated from neigh- borhoods in the graph. The manner which GNNs utilize graph topology. however, makes challenging to scale learning larger graphs deeper models with desirable computational and memory efficiency. Full-batch training that stores the Laplacian of the complete graph suffers from memory complexity of O(m ndI. d² d))
n-node, m-edge graph with node features of dimension d when employing an L-layer graph convolutional network (GCN). This linear memory complexity dependence large graphs with millions of nodes or more. As an example, the MAG240M-LSS dataset [21] is node classification benchmark with over 240 million nodes that takes over 202 GB of GPU memory when fully loaded.
and the limited memory capacity of GPUs make it difficult to train
To address the memory constraints, two major lines of research are proposed: (1) Sampling based approaches [18, 11, 12, 14, 45] based on the idea of implementing message passing only between based techniques, such as GNNAutoSeale [17] and VQ-GNN [15]), which maintain the expressive power of GNNs on sampled subgraphs using historical embeddings. However, all of these methods require the number of mini-
the neighbors within sampled mini-batch; (2) cistorical-embeddee
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

batches to be proportional to the size of the graph for fixed memory consumption. In other words, they significantly increase computational time complexity in exchange for memory efficiency when scaling up to large graphs. For example, training 4-layer GCN with just 333K parameters (1.3 MB) for 500 epochs on ogbn-papers can take more than 2 days on a powerful AWS p4d.24x large instance [21].
We seek to achieve efficient training of GNNs with time and memory complexities sublinear in graph size without significant accuracy degradation. Despite the difficulty of this goal, it should be achievable given that (1) the number of learnable parameters in GNNs is independent of the graph size, and (2) training may not require traversal of all local neighborhoods on graph but rather only the most representative ones (thus sublinear in graph size) as some neighborhoods may be very similar. In addition, commonly-used GNNs are typically small and shallow with limited model capacity and expressive power, indicating that a modest proportion of data may suffice.
This paper presents Sketch-GNN, a framework for training GNNs with sublinear time and memory complexity with respect to graph size. Using the idea of sketching, which maps high-dimensional data structures to a lower dimension through entry hashing, we sketch the n X n adjacency matrix and the n X d node feature matrix to a few e and d sketches respectively before training, where e is the sketch dimension. While most existing literature focuses on sketching linear weights or gradients, we introduce a method for sketching non-linear activation units using polynomial tensor sketch theory [19]. This preserves prediction accuracy while avoiding the need to "unsketch" back to the original high dimensional graph-node space n. thereby eliminating the dependence of training complexity on the underlying graph size n. Moreover, we propose to learn and update the sketches in an online manner using learnable locality-sensitive hashing (LSH) [9]. This reduces the performance loss by adaptively enhancing the sketch quality while incurring minor overhead sublinear in the graph size. In practice, we find that the sketch-ratio c/n required to maintain "full-graph" model performance drops as n increases;
result, our Sketch-GNN enjoys sublinear training scalability,
Skeich-GNN applies sketching techniques to GNNs to achieve training complexity sublinear the data size. This is fundamentally different from the few existing works which sketch the weights or gradients [30, 13, 26, 29, 37] to reduce the memory footprint of the model and speed up optimization. To the best of our knowledge, Sketch- is the first sub-linear complexity training algorithm for GNNs, based on I.H and tensor sketching. The sublinear efficiency obtained applies to various types of GNNs, including GCN [27] and GraphSAGE [18]. Compared to the data compression approach [22, 23], which compresses the input graph to a smaller one with fewer nodes and edges before training, our Sketch-GNi GNNN is advantageous since it does not suffer from an extremely long preprocessing time (which renders the training speedups meaningless) and performs much better across GNN types/architectures.
The remainder of this paper is organized as follows. Section 2 summarizes the notions and prelimi- naries of GNNs and sketching. Section 3 describes how to approximate the GNN operations on the full graph topology with sketches. Section 3.3 introduces potential drawbacks of using fixed sketches and develops algorithms for updating sketches using learnable LSHs. In Section 4, we compare our approach to the graph compression approach and other GNN scalability methods. In Section 5, we report the performance and efficiency of Sketch-GNNs as well as several proof-of- oofoo-ff-concptt and ablation experiments. Finally, Section 6 concludes this paper with a summary of limitations, future directions, and broader impacts.
2 Preliminaries
Basic Notations. Consider a graph with n nodes and m edges. Connectivity is given by the adjacency matrix A E {0, 1)"x" x and features on nodes are represented by the matrix X E Raxd, where is the number of features. Given a matrix C, let Ct,,. C..,, and C.,, denote its (i. (ith) entry, i-th row, and j-th column, respectively. @ denotes the dlement-wise (Hadamard) product, whereas O represents the k-th order element-wise power. || || is the symbol for the Frobenius norm. Tn E R denotes the identity matrix, whereas 1, E I is the vector whose elements are all ones. Med represents the element-wise median over set of matrices. Superscripts are used to indicate multiple instances of the same kind of variable; for instance, x!) E d are the node representations on layer l.
Unified Framework of GNNs. A Graph Neural Nenwork (GNN) layer receives the node representa- tion of the preceding layer X e gaxd input and outputs new representation ((+1) Bxd

---

where X = ( E Raxd are the input features. Although GNNs are designed following different guiding principles, such as neighborhood aggregation (GraphSAGE), spatial convolution (GCN). self-attention (GAT), and Weisfeiler-Lehhmal (WL.) alignment (GIN [44]), the great majority of
GNNs can be interpreted as performing message passing on node features, followed by feature transformation and an activation function. The update rule of these GNNs can be summarized as [15]
x = (E, (())xW)().))))
(1)
Where C(9) E IR denotes the g-th convolution matrix that defines the message passing operator, q E Z,4 is index of convolution, (-) is some choice of nonlinear activation function, and W((a) e Rd xdx+1 denotes the learnable linear weight matrix for the 1-th layer and g-th filter. GNNs under this paradigm differ from each other by their choice of convolution matrices C(a), which can be either fixed (GCN and GraphSAGE) or learnable (GAT). In Appendix A, we re-formulate number of well-known GNNs under this framework. Unless otherwise specified, we assume q = and d di for every layer E [L. for notational convenience.
Count Sketch and Tensor Sketch. (1) Count sketch [7, 41] is an efficient dimensionality re- duction method that projects an n-dimensional vector u into a smaller c-dimensional space us- ing random hash table h : [n]] + [c] and a binary Rademacher variable s : [n] - [+1}, where [n] .n.....n.. Count sketch is defined as CS(u); = Σng)= s()) which is linear transformation of u. i.e., CS(u) Ru. Here, R R2x denotes the so-called count sketch matrix, which has exactly one non-zero element per column. (2) Tensor sketch [32] is proposed as generalization of count sketch the tensor product of vectors. Given z I and an order k. consider a k number of i..d. hash tables (("),...,,b) ......
[n]] [c] and i..d.
binary Rademacher variables s(1) ,...,, s(R), [m] - {+1}. Tensor sketch also projects vector R" into RR and is defined (2) = =5<==)===<)>-- Ench.--))= (i)) ..)......))))))).. g0x)
(ū)) 2j. where h(1, ... jik) = (11) +.... +........)))) (ix)) mod c. By definition, a tensor sketch of order k = 1 degenerates to count sketch; TS,(-) = CS()). ). (3) We define count sketch of matrix U E Rdxn as the count sketch each row vector individually, i.c., CS(U) E gdxe where [CS(U)],, = CS. The tensor sketch of matrix is defined in the same way. Pham and Pagh [32] devise fast computation of tensor sketch of U E _dxn (sketch dimension c and order k) using count sketches and the Fast Fourier Transform (FFT):
(U) = FFT (O* FFT((S(P))(T)
(2)
where (-)) is the count sketch with hash function (x)) and Rademacher variable s(P), F.T(.) and FFT FFT (.) are the FFT and its inverse applied to each row of a matrix.
Locality Sensitive Hashing. The definition of count sketch and tensor sketch is based on hash table(s) that only requires a data independent uniformity, i.c., with high probability the hash-buckets of similar size. In contrast, locality sensitive hashing (LSH) is hashing scheme that uses locality hash function H gd - [c] to ensure that nearby vectors are hashed into the same bucket (out of buckets in total) with high probability while distant ones not. SimHash achieves the locality property by employing random projections [8]. Given a random matrix P E Re/2xd SimHash defines locality-sensitive hash function
(u) arg max ([Pu || -Pul),
where -] denotes concatenation of two vectors and arg max returns the index of the largest element. SimHash is efficient for large batches of vectors [1]. In this paper, we apply a learnable version of SimHash that is proposed by Chen et al. [9]. in which the projection matrix P is updated using gradient descent; see Section 3.3 for details.
3 Sketch-GNN Framework via Polynomial Tensor Sketch
Problem and Insights. We intend to develop "sketched counterpart" of GNNs, where training based solely on (dimensionality-rduuedd compact sketches of the convolution and node feature matrices, the sizes of which can be set independently of the graph size In each layer, Sketch-GNN
3

---

receives some sketches of the convolution matrix C' and node representation matrix X² and outputs some sketches of the node representations X x(++1, As result, the memory and time complexities are inherently independent of n. The bottleneck of this problem estimating the nonlinear activated product a ((I), where W is the learnable weight of the I-th layer.
Before considering the nonlinear activation, as a first step, we approximate the linear product C using dimensionality reduction techniques such as random projections and low-rank decompositions. As a direct corollary of the (distributional) Donson--Lindenstruue (JL) lemma [25], there exists projection matrix R E gex" such that (x(O)( s (CR') (RX(0 [15]. Tensor sketch one of the techniques that can achieve the JL bound [2]: for error bound, see Lemma I in Appendix B.
Count sketch offers a good estimation of a matrix product, C CS(C)CS While tensor sketch can be used to approximate the power of matrix product, i.e., (CX x TS (C ((X" where (.) @k is the k-th order element-wiss power. If we combine the estimators of element-wise powers of C((W), we can approximate the (element-wis)) activation (+) on (()) This technique known as polynomial tensor sketch (PTS) and is discussed in [19]. In this paper, we apply PTS to sketch the message passing of GNNs, including the nonlinear activations.
3.1 Sketch-GNN: Approximated Update Rules
Polynomial Tensor Sketch. Our goal is to approximate the update rule of GNNs (Eq. (1)) in each power series, and then approximate the
layer. We first expand the clement-wise non-linearity powers using count/tensor sketch, i.e.,
= =o(xx(00) Σ Ck (CX(W(1))) @k
Ck (S,(C) TSx ((x (O))
k=1
(4)
where the A: term always evaluates zero ((0) O. In Eq. (4), coefficients ea are introduced to enable learning or data-driven selection of the weights when combing the terms of different order k. This allows for the approximation of a variety of nonlinear activation functions, such as sigmoid and ReLU, The error of this approximation relies on the precise estimation of the coefficients {c To identify the coefficients, Han et al. [19] design a coreset-based regression algorithm, which requires at least Onn) additional time and memory. Since the coefficients {cx Y that achieve the best performance for the classification tasks do not necessarily approximate known activation, we propose learning the coefficients {cx ) k= to optimize the classification loss directly using gradient descent with simple L2 regularization. Experiments indicate that the learned coefficients can approximate the sigmoid activation with relative errors comparable to those of the coreset-based method; see Fig. Ia in Section 5.
Approximated Update Rules. The remaining step is to approximate the operations of GNNs using PTS (Eq. (4)) on sketches of convolution matrix C' and node representation matrix X(), Consider r pairwise-independent count sketches (cS (-))= with sketch dimension c, associated with hash tables (,......, (r( and binary Rademacher variables .11),..., s(r), defined prior to training an T-layer Sketch-GNN. Using these hash tables and Rademacher variables, we may also construct tensor sketches (- up to the maximum order r.
In Sketch-GNN, sketches of node representations (instead of the O(n) standard representation) are propagated between layers. To get rid of the dependence on n,, we count sketch both sides of Eq. (4)
S sl++kkk' = CS(K') ((x(+))T)) =e CS(K)
TS ())
( TS
(TS)
(TS)(C)T)
(5)
11) FFF -1
FFT (W (WW))) s ((L.
where ((++1,4)) CS(K)) ((X(+1))) E Raxe is the transpose of column-wise count sketch of x(+1), and the superseripts of 5x
s((11,)) indicate that it is the k'thh count sketch of ((+1) (i.c.,

---

sketched by CS(() In the second line of Eq. (5), we can move the matrix, ( multiplied on the left to TSx(C) out of the count sketch function (.), since the operation of row-wise count sketch CS (-) is equivalent to multiplying the associated count sketch matrix R(k)) on the right, i.e., for any U R=*=, CS(R) (U) = U UR((") In the third line of Eq. (5), we denote the "two-sided sketch" of the convolution matrix as (( Cs (TT) E Roxe and expand the tensor sketch TS ((X(((( using the FFT-based formula (Eq. (2)).
Eq. (5) is the (recursive) update rule of Sketch-GNN, which approximates the operation of the original GNN and learns the sketches of representations. Looking the both ends of Eq. (5), obtain formula that approximates the sketches of ( using the sketches of X and C, with learnable weights W(() E Raxd and coefficients {cg E -- practice, to mitigate the error accumulation when propagating through multiple layers, we employ skip- coipeconnections across layers in Sketch-GNNs (Eq. (5) and their full-size GNN counterparts. The forward-pas -aaaaddpassssaa and backward- propagation between the input sketches (.Kk)
J Jk= and the sketches of the final layer representations (S(T.)))r k=1 take (c)) time and memory (see Section 3.3 for complexity details).
3.2 Error Bound on Estimated Representation
Based on Lemma I and the results in [19], establish error bound on the estimated final layer representation (L)) for GCN; see Appendix for the proof and discussions.
Theorem 1. For Sketch-GNN with L layers, the estimated final layer representation
((L) = ( re(k) ((T 1 k 1,... .r}, where the sketches are recursively computed us- ing Eq. (5). For p()) = max w P (2 + 3"),, "1,,,,X00''),, (')'", it holds that E(II XI) S I (1 2/(1 + cx0) /nrl()) 1, where X1I) > O is the smallest singular value of the matrix 7 E Rnnxxr and 7:,k& is the vectorization of ((00o Moreover. if (c()01)2 /nr(()) 1 holds true for every layer, the relative error is (LL(n/)) which is proportional to the depth of the model, and inversely proportional to the sketch ratio (c/n).
Remarks. Despite the fact that in Theorem I the error bound grows for smaller sketch ratios c/n, observe in experiments that the sketch-ratio required for competitive performance decreases as n increases; see Section 5. As for the number of independent sketches r, we know from Lemma 1 that the dependence of on is r M(30og, 2) which is negligible when is not too small; thus, in practice r = 3 is used.
The theoretical framework may not completely correspond to reality. Experimentally, the coefficients Ho ) with the highest performance do not necessarily approximate known activation. We defer the challenging problem of bounding the error of sketches and coefficients learned by gradients to future studies. Although the error bound in expectation, we do not train over different sketches per iteration due to the instability caused by randomness. Instead, we introduce learnable locality sensitive hashing (LSH) in the next section to counteract the approximation limitations caused by the fixed number of sketches.
3.3 A Practical Implementation: Learning Sketches using LSH
Motivations of Learnable Sketches. In Section 3, we apply polynomial tensor sketch (PTS) to approximate the operations of GNNs on sketches of the convolution and feature matrices. Nonetheless, the pre-computed sketches are fixed during training, resulting in two major drawbacks: (1) The performance is limited by the quality of the initial sketches. For example, if the randomly-genrraue hash tables ( have unevenly distributed buckets, there will be more hash collisions and consequently worse sketch representations. The performance will suffer because only sketches are used in training. (2) More importantly, when multiple Sketch-GNN layers are stacked, the input representation (") changes during training (starting from the second layer). Fixed hash tables are not tailored to the "changing" hidden representations.
We seek method for efficiently constructing high-quality hash tables tailored for each hidden embedding. Locality sensitive hashing (LSH) is suitable tool since it is data-dependent and
5

---

preserves data similarity by hashing similar vectors into the same bucket. This can significantly improve the quality of sketches by reducing the errors due to hash collisions.
Combining LSH with Sketching. At the time of sketching, the hash table h(() [rx] + [c] is
replaced with an LSH function H(k) Rd - [c]. for any A E [r]. Specifically, in the I-th layer of
Sketch-GNN, we hash the i-th node to the (1)) (1) (xx >-th bucket for every E [r|], where x!! is the
embedding vector of node i. As a result, we define a data-dependent hash table
haak (1) = ( (x!!)
(6)
that can be used for computing the sketches of X and S s(l.K.k". This LSH-based sketching can be directly applied to sketch the fixed convolution matrix and the input feature matrix. If SimHash is used, i.c., / (u) = arg max ([p(k) u || pp(k) u] (Eq. (3)), an additional O(ner(log c + d)) computational overhead is introduced to hash the nodes for the hash tables during preprocessing:
see Appendix F more information. SimHash(es) are implemented as simple matrix multiplications that are practically very fast.
In order to employ LSH-based hash functions customized to each layer to sketch the hidden repre- sentations of Sketch-GNN (i.e., I ...... L - 1), we face two major challenges: (1) Unless we explicitly unsketch in each layer, the estimated hidden representations ( .. - be accessed and used to compute the hash tables. However, unsketching any hidden representation,
L
1) cannot
k 1...... r requires O(n) memory and time. We need to come up with an efficient algorithm that updates the hash tables without having to unsketch the complete representation. (2) It's unclear how to change the underlying hash table of sketch across layers
i.e., x Med ((() s( s(l.k)
without unsketching to the n-dimensional space, even if we know the most up-to-date hash tables suited to each layer.
The challenge (2), i.e., changing the underlying hash table of across layers, can be solved by maintaining sparse x e matrix ((l.k) == R((ik) ( (R(++1)))T for each & E [r]. which only requires Ocrr) memory and time overhead; see Appendix C for more information and detailed discussions. We focus on challenge (1) for the remainder of this section.
Online Learning of Sketches. To learn hash table tailored for a hidden layer using LSH without unsketching, we develop efficient algorithm to update the LSH function using only size- [ subset of the length-n unsketched representations, where B denotes a subset of nodes we select. This algorithm, which we term online learning of sketches, is made up of two key parts: (Part 1) select subset of nodes B C [n] to effectively update the hash table, and (Part 2) update the LSH function H()) with triplet loss computed using this subset.
(I) Selection of subset B: Because model parameters are updated slowly during neural network training, the data-dependent LSH hash tables also changes slowly (this behavior was detailed in [9]). The amount of updates to the hash table drops very fast along with training, empirically verified in Fig. lb (left) in Section 5. Based on this insight, we only need to update small fraction of the hash table during training. To identify this subset B E [n] of nodes, gradient signals can be used. Intuitively, node representation vector hashed into the wrong bucket will be aggregated with distant vectors and lead to larger errors and subsequently larger gradient signals. Specifically, we propose finding the candidate set B of nodes by taking the union of the several buckets with the largest gradients, i.e., B = {i h(..k) (i) = arg max, [S
x (s(( 1ss for some k.). The memory and overhead required to update the entries in in the hash table O(BI).
(2) Update of LSH fimction: In order to update the projection matrix P that defines SimHash (K)) Rd + [c] (Eq. (3)), instead of the O(n) full triplet loss introduced by [9], we consider a sampled version of the triplet loss on the candidate set B with O(IBI) complexity, namely
L(H,P+,P-) max 0, Σ (U.))P cos( (( (u), H(w))) Emu.eer cos(H(()) H(b)) + to (7)
where P+ ((X,.. X, I i.j E B, (X,., X,,)) > t+} and P_ {(X,, 1, x, | i,j E
B, (X X..)) < } are the similar and dissimilar node-pairs in the subset B; L. > 1_ and > 0 are hyper-parameters. This triplet loss L(H, P_) is used to update P using gradient descent, as described in 19), with a Bld + }B() overhead. Experimental validation of this LSH update mechanism can be found in Fig. lb in Section

---

Avoiding ((n) in Loss Evaluation. We can estimate the final layer representation using the sketches (5( 1k= i.e, X Med ( s(,,k) k 1 .r and compute the losses of all nodes for node classification (or some node pairs for link prediction). However, the complexity of loss evaluation is ( proportional to the number of ground- labels. In order avoid (()) complexity completely, rather than un-sketching the node representation for all labeled nodes, we employ the locality sensitive hashing (LSH) technique again for loss calculation so that only a subset of node losses are evaluated based on a set of hash tables. Specifically, we construct an LSH hash table for each class in a node classification problem, which indexes all of the labeled nodes of this class and can be utilized to choose the nodes with poor predictions by leveraging the locality property. This technique, introduced in [10], is known as sparse forward-pass and propppppagattion and we defer the descriptions to Appendix C.
One-time Preprocessing, If the convolution matrix C is fixed (GCN, GraphSAGE), the "two-sided | s(l.kkk)) cs (k') (TS)(C))) E Iee is the same in each layer and may be denoted as s(k.k) In addition, all of the y² sketches of i.., {(.(t,)) E R He= can be computed during the preprocessing phase. If the convolution matrix C' is sparse (which is true for most GNNs following Eq. (1) on sparse graph), we can use the sparse matrix representations for the sketches ([s(),
sketch"
and the total memory taken by the y² sketches is O(r=c(m/n)) where (2m//n) is the average node degree (see Appendix F for details). We also need to compute the r count sketches of the input node feature matrix X (O) i.e., { (5() |T=1 during preprocessing, which requires (rred) memory in total. In this regard, we have substituted the input data with compact graph-size independent sketches (i.e., (c) memory). Although the preprocessing time required to compute these sketches is ((),, it is a one-time cost prior to training, and it is widely known that sketching is practically very fast.
Complexities of Sketch-GCN. The theoretical complexities of Sketch-GNN is summarized as follows, where for simplicity we assume bounded maximum node degree, i.e., m O(n). (1) Training Complexity: (Ia) Forward and backward propagation: O(Lerd(log()) + d m/n)) = O(e) time and (Lr(ced + rm/n)) O(c) memory. (Ib) Hash and sketch update: O(Lr(c- +
(Bld)) = Occ) time and memory. (2) Preprocessing: O(r(rm + n + c)) O(z) time and (m/nd))m//)) Lal(n d)) = (n)) memory (the same as a standard GCN). We defer a detailed summary of the theoretical complexities of Sketch-GNN to Appendix F.
(c)) memory. (3) Inference: ((L((m + nd)) (n) time and 0(m +
We generalize Sketch-GNN to more GNN models in Appendix D and the pseudo-code which outlines the complete workflow of Sketch-GNN can be find in Appendix E.
4 Related Work
Towards sublinear GNNs. Nearly all existing scalable methods focus on mini-batching the large graph and resolving the memory bottleneck of GNNs, without reducing the epoch training time. Few recent work focus on graph compression [22, 24] can also achieve sublinear training time by coarsening (e.g., using [31]) the graph during preprocessing or condensing the graph with dataset condensation techniques like gradient-matching [46], so that we can train GNNs on the coarsened/condenseed graph with fewer nodes and edges. Nevertheless, these strategies suffer from two issues: (1) Although graph coarsening/condensatiio is one-time cost, the memory and time overheads are often worse than (n)) and can be prohibitively large on graphs with over 100K nodes. Even the fastest graph coarsening algorithm used by [22] takes more than 68 minutes to process the 2ode Reddit graph [45]. The long preprocessing time renders any training speedups meaningless. (2) The test performance of model trained on the coarsened graph highly depends on the GNN type. For graph condensation, if we do not carefully choose the GNN architecture used during condensation, the test performance of downstream GNNs can suffer from 9.5% accuracy drop on the Cora graph [23]. For graph coarsening, although the performance of [22] on GCN is good, significant performance degradations are observed on GraphSAGE and GAT; see Section 5.
Other scalable methods for GNNs can be categorized into four classes, all of them still require linear training complexities. (A) On a large sparse graph with n nodes and edges, the "full-graph" training of a I--layer GCN with d-dimensional (hidden) features per layer requires O(m + +dd. T.) memory and OmdLL + ndf L) epoch time. (B) Sampling-basee based methods sample bini-batches from
7

---

the complete graph following three schemes: (I) node-wisely sample subset of neighbors in each layer to reduce the neighborhood size; (2) layer-wisely sample set of nodes independently in each layer; (3) subgraph-wiser sample subgraph directly and simply forward-pan wrward-pass and back- propagate on that subgraph. (B.1) GraphSAAH [18] samples r neighhors for each node while ignoring messages from other neighbors. O(br²) nodes are sampled in a mini-batch (where b is the mini-batch size), and the epoch time is (ndrr"); therefore, GraphSAGE is impractical for deep GNNs on a large graph. FastGCN [12] and LADIES [48] are layer-sampling methods that apply importance sampling to reduce variance. (B.2) The subgraph-wise scheme has the best performance and is most prevalent. Cluster- [14] partitions the graph into many densely connected subgraphs and samples a subset of subgraphs (with edges between subgraphs added back) for training per iteration. GraphSAINT [45] samples a set of nodes and uses the induced subgraph for mini-bated training. Both Cluster-GCN and GraphSAINT require ((mdI. + nnL epoch time, which is the same as "full-graph" training, although Cluster-GCN also needs (m) pre-processing time. (C) Apart from sampling strategies, cestoricaleembeddiig-.. -hased methods propose mitigating sampling errors and improving performance using some stored embeddings. GNNAutoScale [17] keeps snapshot of all embeddings in CPU memory, leading to a large ((dL) memory overhead. VQ-GNN [15] maintains vector quantized data structure for the historical embeddings, whose size is independent of n. (D) Linearized GNNs [42, 4, 33] replace the message passing operation in each layer with a
one-time message passing during preprocessing. They are practically efficient, but the theoretical complexities remain (n)). Linearized models usually over-simplify the corresponding GNN and limit its expressive power.
We defer discussion of more scalable GNN papers and the broad literature of sketching and LHS for neural networks to Appendix G.
5 Experiments
10-10
Corcict
(ammingg(h..... Rge uma)
10-16
Loatted GD (Ours)
Taylor
0:70-
H.mmmingg
Relaive
20-20
0.10
0.04
10-25
6/2
10
0.04
0.10
2
10
15
20
25
Skesch Rutio (c/s))
Epoch
Epoch
Error of PTS
(b) Learnable LSH
Figure Figure 1a Relative emrrr when applying polynomial tensor sketch (PTS) to the nonlinear unit (C)W) following Eq. (4), The datasct used is Cora [34]. a is the sigmoid activation. We set r = 5 and test on GCN with fixed W La E ddd The coefficients {cx (c=)
be computed by coreset regression [19] (blue). by a Taylor expansion of ( (orange). or learned from gradient descent proposed by us (green). Figure 1b The left plot shows the Hamming distance changes of the hash table in the 2nd layer during the training of 2-layer Sketch-GCNN where the hash table is constructed from the unsketched representation (1) using SimHash. The right plot shows the Hamming distances between the hash table learned using our algorithm and the hash table constructed directly from (1)
Table 1: Performance of Sketch GCN in comparison to Graph Condensation [23] and Graph Coarsening [22] on Cora and Citeseer with 2-1ayer GCNs.
Table 2: Performance across GNN architectures in comparison to Graph Condensation [23] on Cora with sketch ratio c/n = 0.026.
Renchmark
Coea
Citroeer
Propraszocing
Archiiectues
GNN Model
GCN
Andilecture
OCN
"Full-Gingh" (onacle)
8119 .023
.7191 + .0115
"Pull Graphi (ocacle)
NA
.8199 4: 6022
.7981 1: 0053
Sketch Ratio (e/ra).
0.013
0,026
0:009
0,018
Cuaraming
3121 .0094
6518
.061
5218 + .019
5008 + 0015
GCand
Gupp
.066 0967
7004 + 0051
7018
8200
0057
OCond
7071
0013
.502
0075
7052 1. 0120
7000
1. DUST
Sketch BiNc (ours)
8012 -. .0004
.033
0001
7091 1. .000
7114 1. 0099
StardsCNN (ours)
N/A 8005 + 0071
7 0121
In this section, we evaluate the proposed Sketch-GNN algorithm and compare it with the (oracle) "full-graph" training baseline, a graph-coarsening based approach (Coarsening (22]) and a dataset condensation based approach (GCond (23]) which enjoy sublinear training time, and other scalable
8

---

Table 3: Performance of Sketch-GNN in comparison to Graph Coarsening [22] oghn-arxiv.
Betchmark
GNN Model
GCN
GrgASAGE
GAT
"rull-Ginph" (orncte)
7174 (012M
730P + A017
T6533 /0115
Sketch Katio (c/e)
0.1
0.2
0.4
0.1
0.2
9.4
0.1
0.2
0.4
Gonnening
4606 0001
6065
.0010
.6822
00d5
5264 4. 0251
5906 + 0131
.9000
0001
5177
.0088
5916
0027
4307 # 0011
Sketch-GNN
0067
A029 .0144
.003
0056
.7088
.010
0115
0064
Table 4: Performance of Sketch-GNN versus SGC [42], GraphSAINT [45], and VQ-GNN [15].
Beschmark
cpli-aratr
Rodii
ogha prodect
SGC
6044 d: .0006
9164
0011
55633 4. .0220
GNN Madd
GCN
GmpISAGE
GAT
GCN
GrybSAACE
GAT
OCN
CappESGGE
GAT
"Full-Craphi (onack))
7174 0029
.7100 .027
7253 0045
0OM
COM
0OM
00M
00M
00M
GripSAINNT VQ-GNN
00G7
DG81
R00T
7012
0042
7821
0049
Ratto (o/v)
0.3
Sketch (ours)
0094
11800 00144
0.9455
0003
.753 0005
.T7U2 (000
.7768 0073
methods including: sampling-basel method (GraphSAINT [45]), historical-embeddiin based method (VQ-GNN [15], and linearized GNN (SGC [42]). We test on two small graph benchmarks including Cora, Citeseer and several large graph benchmarks including ogbn-arxiv (169K nodes, 1.2M edges), Reddit (233K nodes, 11.6M edges), and ogbn-products (2.4M nodes, 61.9M edges) from [20, 45]. See Appendix H for the implementation details.
Proof-of-Concept Experiments: (1) Errors of gradient-learned PTS coefficients: In Fig. la, we train the PTS coefficients to approximate the iigmoid-activated a (CXW) to evaluate its ap- proximation power to the ground -toun activation. The relative errors are comparable those of the coreset-based method. (2) Slow-change phenomenon of LSH hash tables: In Fig. lb (left), we count the changes of the hash table constructed from an unsketched hidden representation for each epoch, characterized by the Hamming distances between consecutive updates. The changes drop rapidly as training progresses, indicating that apart from the beginning of training, the hash codes of most nodes do not change at each update. (3) Sampled triplet loss for learnable LSH: In Fig. 1b (right), we verify the effectiveness of our update mechanism for LSH hash functions as the learned hash table gradually approaches the "ground truth", i.e., the hash table constructed from the unsketched hidden representation.
Performance of Sketch-GNNs. We first compare the performance of Skerch-GNN with the other sublinear training methods, i.e., graph coarsening [22] and graph condensation [23] under various sketch ratios to understand how their performance is affected by the memory bottleneck. Since graph condensation (GCond) requires learning the condensed graph from scratch and cannot be sealed to large graphs with a large sketch ratio [23], we first compare with GCond and Coarsening
the two small graphs using a 2-layer GCN in Table 1. We see GCond and Sketch- GNN can outperform graph coarsening by a large margin and can roughly match the full-graph training performance. However, GCond suffers from a processing time that is longer than the training time (see below) and generalizes poorly across GNN architectures. In Table 2, we compare the performance of Sketch-GNI GNN and GCond across two GNN architectures (GCN and GraphSAGE). While graph condensation (GCond) relies "reference architecture" during condensation. Sketch-GNN does not require preprocessing, and the sublinear complexity is granted by sketching "on the fly". In Table 2, we see the performance of GCond is significantly degraded when generalized across architectures, while Sketch-GNNs' performance is always close to that of full-graph training.
In Table 3, we report the test accuracy of both approaches on ogbn-arxiv, with a 3-layer GCN, GraphSAGE, or GAT as the backbone and a sketch ratio of 0.1, 0.2, or 0.4. We see there are significant performance degradations when applying Coarsening to GraphSAGE and GAT, even under sketch ratio 0.4, indicating that Coarsening may be compatible only with specific GNNs (GCN and APPNP explained in [22]). In contrast, the performance drops of Sketch-GNi are always small across all architectures, even when the sketch ratio is 0.1. Therefore, our approach generalizes to more GNN architectures and consistently outperforms the Coarsening method.
We move on to compare Sketch-GNN with linearized GNNs (SGC), sampling-based (GraphSAINT), and
(VQ-GNN) methods. In Table 4, we report the performance of
9

---

SGC, the "full-graphe training (oracle), GraphSAINT and VQ-GNN with mini- batch size 50K (their performance is not affected by the choice of mini-batch size if it is not too small), and Sketch- GNN with appropriate sketch ratios (0.4 on oghn-arxiv, 0.3 on Reddit, and 0.2 on oghn-product). From Table 4, we confirm that, with an appropriate sketch ratio, the performance of Sketch-GNN is usually close to the "full-graph" oracle and competitive with the other scalable approaches. The needed sketch ratio e/n for Sketch-GNN to achieve competitive performance reduces as graph size grows. This further illustrates that, as previously indicated, the required training complexities (to get acceptable performance) are sublinear to the graph size.
Efficiency of Sketch-GNNs. For efficiency measures, we are interested in the comparison to Coarsening and GCond, since these two approaches achieve sublinear training time the cost of some preprocessing overheads. Firstly, we want to address that both Coarsening and GCond suffer from an extremely long preprocessing time. On oghn-arxiv, Coarsening and GCond require 358 and 494 seconds on average, respectively, to compress the original graph. In contrast, our Sketch-GNN sketch the input graph "on the fly" and does not suffer from preprocessing overhead. On oghn- arxiv with learning rate of 0.001, full-graph training of GCN for 300 epochs is more than enough for convergence, which only takes 96 seconds on average. The preprocessing time of Coarsening and GCond is much longer than the convergence time of full-graph training, which renders their training speedups meaningless. However, Sketch-GNN often requires more training memory than Coarsening and GCond to maintain the copies of sketches and additional data structures, although these memory overheads are small, c.g., only 16.6 MB more than Coarsening on ogbn-arxit baxiiv with sketch ratio c/n 0.1. All three sublinear methods (Corasening, GCond, Sketch-GNN) lead to denser adjacency/convolution matrix and thus increased memory per node. However, this overhead is small for Sketch GNN because although sketched the adjacency, its sparsity is still preserved to some extent, as sketching is a amearr/mltiilinee operation.
Ablation Studies: (1) Dependence of sketch dimension con graph size Although the theoretical approximation error increases under smaller sketch ratio c/'n, we observe competitive experimental results with smaller c/n,, especially on large graphs. In practice, the sketch ratio required to maintain "full- holl-graph" model performance decreases with n. (2) Learned Sketches versus Fixed Sketches. We find that learned sketches can improve the performance of all models and on all datasets. Under sketch-ratio c/n = 0.2, the Sketch-GCN with learned sketches achieves O. 7004 = 0.0096 accuracy on ogbn-arxiv while fixed randomized sketches degrade performance 0.6649 + 0.0106.
6 Conclusion
We present Sketch-GNN, a kketch-based GNN training framework with sublinear training time and memory complexities. Our main contributions are (1) approximating nonlinear operations in GNNs using polynomial tensor sketch (PTS) and (2) updating sketches using learnable locality-sensitive hashing (LSH). Our novel framework has the potential to be applied other architectures and applications where the amount of data makes training even simple models impractical. The major limitation of Sketch-GNN is that the sketched nonlinear activations are less expressive than the original activation functions, and the accumulated error of sketching makes it challenging to sketch much deeper GNNs. We expect future research to tackle the above-mentioned issues and apply the proposed neural network sketching techniques to other types of data and neural networks. Considering broader impacts, we view our work mainly as a methodological and theoretical contribution, and there is no obviously foresecable negative social impact.
Acknowledgments and Disclosure of Funding
This work is supported by National Science Foundation NSF-IIS-FAI program, DOD-ONR-Office of Naval Research, AAD-DARRA-Deefene Advanced Research Projects Agency Guaranteeing AI Robustness against Deception (GARD), Adobe, Capital One, JP Morgan faculty fellowships, and NSF DGE-1632976.
References
[1] Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. Practical and optimal Ish for angular distance. Advances in neural information processing
10

---

systems, 28, 2015.
[2] Haim Avron, Huy Nguyen, and David Woodruff. Subspace embeddings for the polynomial kernel. Advances in neural information processing systems, 27, 2014.
[3] Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In International Conference on Machine Learning, pages 874-883, PMLR, 2020.
[4] Alcksandar Bojchevski. Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemherezki, Michal Lukasik, and Stephan Günnemann. Scaling graph neural networks with approximate pagerank. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2464-24747 2020.
[5] Daniele Calandriello, Alessandro Lazaric, loannis Koutis, and Michal Valko. Improved large- scale graph learning through ridge spectral sparsification. In International Conference on Machine Learning, pages 688-697. PMLR, 2018.
[6] Sarath Chandar, Sungjin Ahn, Hugo Larochelle, Pascal Vincent, Gerald Tesauro, and Yoshua Bengio. Hierarchical memory networks, arXiv preprint arXiv:1605.07427, 2016.
[7] Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming, pages 693-703 Springer, 2002.
[8] Moses S Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 380-388, 2002.
[9] Beidi Chen, Zichang Liu, Binghui Peng. Zhaozhuo Xu, Jonathan Lingjie Li, Tri Dao, Zhao Song, Anshumali Shrivastava, and Christopher Re. Mongoose: A learnable Ish framework for efficient neural network training. International Conference on Learning Representations, 2020.
[10] Beidi Chen, Tharun Medini, James Farwell, Charlie Tai, Anshumali Shrivastava, al. Slide: In defense of smart algorithms over hardware acceleration for large-scale deep learning systems. Proceedings of Machine Learning and Systems, 2:291-306, 2020.
[11] Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In International Conference on Machine Learning, pages 942-950, PMLR, 2018.
[12] Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In International Conference Learning Representations, 2018.
[13] Wenlin Chen, James Wilson, Stephen Tyree, Kilian Weinberger, and Yixin Chen. Compressing neural networks with the hashing trick. In International conference on machine learning, pages 2285-228 2294. PMLR, 2015.
[14] 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 Knowledge Discovery & Data Mining, pages 257-266, 2019.
[15] Mucong Ding, Kezhi Kong, Jingling Li, Chen Zhu, John Dickerson, Furong Huang, and Tom Goldstein. Vg-gnn: A universal framework scale up graph neural networks using vector quantization. Advances in Neural Information Processing Systems, 34, 2021.
[16] Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The World Wide Weh Conference, pages 417-426, 2019.
[17] Matthias Fey, Jan E Lenssen, Frank Weichert, and Jure Leskovec. Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings. In International Conference on Machine Learning, pages 3294-3304. PMLR, 2021.
11

---

[18] 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, pages 1025-1035, 2017.
[19] Insu Han, Haim Avron, and Jinwoo Shin. Polynomial tensor sketch for element- wise function of low-rank matrix. In International Conference on Machine Learning, pages 9994.3993. PMLR, 2020.
[20] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 18-22118-21333 2020.
[21] Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. Ogb-lsc: A large-scale challenge for machine learning on graphs. In Thirty-fifth Conference Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
[22] Zengfeng Huang. Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou. Scaling up graph neural networks via graph coarsening. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 684, 2021.
[23] Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. Graph con- densation for graph neural networks. In International Conference on Learning Representations, 2021.
[24] Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. Graph con- densation for graph neural networks. In International Conference on Learning Representations, 2022.
[25] William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. Contemporary Mathematics, 26( 26(189-206)1, 1984.
[26] Shiva Prasad Kasiviswanathan, Nina Narodytska, and Hongxia Jin. Network approximation using tensor sketching. In International Joint Conference on Artificial Intelligence, pages 2319-2325, 2018.
[27] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[28] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In International Conference on Learning Representations, 2019.
[29] Yibo Lin, Zhao Song, and Lin F Yang. Towards a theoretical understanding of hashing- neural nets. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 127-137. PMLR, 2019.
[30] 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, 2021.
[31] Andreas Loukas Graph reduction with spectral and cut guarantees. Journal of Machine Learning Research, 20:1-42, 2019.
[32] Ninh Pham and Rasmus Pagh. Fast and scalable polynomial kemels via explicit feature maps. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 2399-477,0 2013.
[33] Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004. / 198, 2020.
[34] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008.
12

---

[35] Yang Shi and Animashree Anandkumar. Higher-orde order count sketch: Dimensionality reduction that retains efficient tensor operations. In 2020 Data Compression Conference (DCC), pages 394-394, IEFE, 2020.
[36] Ryan Spring and Anshumali Shrivastava. Scalable and sustainable deep learning via randomized hashing. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 445-454, 2017.
[37] Ryan Spring, Anastasios Kyrillidis, Vijai Mohan, and Anshumali Shrivastava. Compressing gradient optimizers via count-sketches. In International Conference on Machine Learning, PMLR, 2019.
pages 9946-5955
[38] Rakshith Srinivasa, Cao Xiao, Lucas Glass, Justin Romberg, and Jimeng Sun. Fast graph attention networks using effective resistance based graph sparsification. arXiv preprint arXiv:2006.0873 2020.
[39] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[40] Yining Wang, Hsiao- Yu Tung. Alexander J Smola, and Anima Anandkumar. Fast and guaranteed tensor decomposition via sketching. Advances in neural information processing systems, 28, 2015.
[41] Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg. Feature hashing for large scale multitask learning. In Proceedings of the 26th annual international conference on machine learning, pages 1113-1120, 2009.
[42] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning. pages 6861-688 6871. PMLR, 2019.
[43] Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph neural networks in recom- mender systems: survey. ACM Computing Surveys (CSUR), 2020.
[44] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2018.
[45] Hanqing Zeng. Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2019.
[46] Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. In International Conference on Learning Representations, 2020.
[47] 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 Muchine Leurning, pages 11458-1 1468. PMLR, 2020.
[48] Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang. Yizhou Sun, and Quanquan Gu. Layer- dependent importance sampling for training deep and large graph convolutional networks. Advances in Neural Information Processing Systems, 32:1 12:11249-11259, 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Section 1.
(b) Did you describe the limitations of your work? [Yes] Currently, our work has two major limitations: (1) our theoretical assumptions and results may not perfectly correspond to the reality; see the theoretical remarks in Section 3, and (2) our implementation is not fully-optimized with the more advanced libraries; see the efficiency discussions in Section 5.
13

---

(c) Did you discuss any potential negative societal impacts of your work? [Yes] We see our work as a theoretical and methodological contribution toward more resource-efficien graph representation learning. Our methodological advances may enable larger-scale network analysis for societal good. However, progress in graph embedding learning may potentially inspire other hostile social network studies, such as monitoring fine- grained user interactions.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? YYss]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Lemma 1 and Theorem
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix B.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes) See Appendix H.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix H.
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Section 5.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix H.
4. If you are using existing assets (e.g., code, data, models) or curating/rrelesing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] See Appendix H.
(b) Did you mention the license of the assets? [Yes] See Appendix H.
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [No]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [No]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "w6cggOTWIgI", "reviewer": "Reviewer_9WyJ", "summary": "Scaling GNNs to large graphs is an important area of research. This paper proposes Sketch-GNN, which uses polynomial tensor sketch (PTS) and local sensitive hashing (LSH) to sketch the graph convolution operations in GNNs with sublinear training complexity. To be specific, PTS is used to estimate the non-linear GNN update rule, and LSH is used as a data-dependent method for learnable sketches.\n\nExperiments on several graph datasets (ogbn-arxiv, Reddit and ogbn-product) proves the low memory and training time complexity of the proposed sketch-GNN method, which could achieve comparable performance with respect to other strong benchmarks including GraphSAINT and VQ-GNN. Ablation tests over sketching ratio c are also provided.", "questions": "Based on my understanding, sketch-GNN achieve sublinear training complexity because the sketch ratio c/n decreases as the graph size n increases. Therefore, as mentioned in the second bullet point in weakness, it would be great to see more empirical results that could support sublinear complexity.", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n* This paper is well-written, and provides a nice way to incorporate tensor sketch and LSH into GNNs, which might inspire future work in this area. \n\n* Some adaptations are incorporated to boost the performance of the proposed algorithm, including learnable coefficients for the non-linear activation function and data-dependent hashing with learnable LSH. \n\n\nWeakness:\n\n* As shown in table2 and table3, GraphSAINT uses comparable train memory (but longer epoch time), and could achieve better performance than sketch-GNN on average. So is the proposed sketch-GNN method good enough as an alternative for GraphSAINT?\n\n* As mentioned in line 398-399, the needed sketch ratio c/n for sketch-GNN to achieve competitive performance reduces as graph size grows. However, only 1 sketch ratio are reported for each graph dataset. It would be nice to see results from multiple sketch ratios for each dataset to confirm this statement. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "pydIITMp3Yl", "reviewer": "Reviewer_HVXV", "summary": "Authors tackle the problem of scalability of GNNs to very large graphs. They propose Sketch-GNN method that approximates computation of a typical message-passing GNN in time that is sublinear of the number of nodes. This is achieved by “compressing” the graph (i.e., its adjacency matrix, or generally a convolution matrix, and the node feature matrix) by using Count Sketch and devising an approximation to a GNN layer computation, that is built on Polynomial Tensor Sketch with Locality Sensitive Hashing. Their approach is applied to multiple GNN kernels: GCN, GAT, and GraphSAGE. On 3 datasets (ogbn-arxiv, ogbn-product, and Reddit) Sketch-GNN shows strong classification performance competitive with VQ-GNN, however GraphSAINT is comparable or better. In terms of run-time efficiency, Sketch-GNN significantly improved over compared models on the evaluated medium-sized datasets.", "questions": "1. Have you empirically tested the effect of choice of the number of sketches $r$ on the prediction performance and computation time & memory? Appears all experiments are done with $r=3$. For sketch ratio $c / n = 0.1$ the lower bound $3^{log_c n}$ is closer to 4 for all tested graph sizes.\n2. Sketch-GNN with GAT kernel is more expensive than GCN as the convolution matrix is not shared across layers. To how much longer computation time and increased memory footprint does this translate?\n3. For efficiency experiments presented in Table 1, authors used sketch ratio $c / n = 0.1$ which may be an optimistic scenario. What does the efficiency comparison looks like with settings as used in the prediction performance comparison in Table 3, where higher sketch ratios are used?\n4. Is this approach applicable to link prediction tasks? Would that necessitate potentially expensive un-sketching of node representations?\n5. As mentioned above under \"weaknesses\", could Sketch-GNN scale to datasets such as MAG240M-LSC? What graph size do you estimate as a practical limit on current hardware?\n6. Have you considered a combination of subgraph sampling methods (e.g., GraphSAINT) and Sketch-GNN?", "limitations": "Method limitations are not explicitly discussed, nor any potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- Motivation: This paper tackles an important problem, scaling GNNs to graphs of millions or billions of nodes has clear industrial applications.\n- Clarity: The paper is very well written and easy to follow.\n- Correctness: I have read through and believe the method derivation to be correct, however I do not have a deep expertise in sketch and LSH methodology.\n- Originality: The proposed method achieves similar goal to VQ-GNN but by different means. It builds on existing Polynomial Tensor Sketch and Locality Sensitive Hashing, devising online learning of Sketches such that the whole stack of GNN layers is trainable without realizing explicit representation of all N nodes.\n\n### Weaknesses\n- Limitation: Authors do not perform experiments on MAG240M-LSC (contains ~240M nodes). I believe their approach would still not scale to graphs with hundreds of millions of nodes, as the sketch ratio would need to be very low, which may not be practical. I would like to see a discussion from the authors on this point.\n- Achieved prediction performance is comparable or lower to GraphSAINT – a sampling-based approach; compared to VQ-GNN the prediction performance appears to be equivalent.\n\n### Minor comments:\n- A diagram illustration would further improve readability of the paper.\n- Typos: line 131: “sorely” -> “solely”?; line 234: “ldots” command\n\nIn summary, the proposed method is a valuable contribution, albeit its practical limitations should be further discussed in the Experiments section and Conclusion. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "bFyF9mpRJ1Y", "reviewer": "Reviewer_wwt9", "summary": "Training GNNs on large graphs is a long standing challenge. This work proposes a sketch-based algorithm whose training time and memory grow sublinearly with respect to graph size by training. Specifically, the author provides a novel protocol for sketching non-linear activations and graph convolution matrices in GNNs. The author further utilizes LSH for improving the quality of sketches.", "questions": "See above", "limitations": "See above", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. To the best of my knowledge, the sketing method proprosed in this paper is novel. I really like the idea of propagating the sketches instead of merely storing sketched activations in the forward pass.\n\n2. The proposed techinique can be applied to different kinds of GNNs.\n\n3. The theoretical analysis is correct and insightful, although I would like to note that it has a gap to the empirical results.\n\nWeaknesses\n\n1. I suggest the author tone down the claim \"Sketch-GNN is the first sketch-based training algorithm for GNNs\" and discuss the difference to the similar work EXACT [1]. \nIn fact, [1] already applied the random projection-based sketching to the node embeddings. \nIf you take a close look to Fig. 1 in [1], the main difference of sketching between this work and [1] are: \n(1) SketchGNN applied the sketch during the forward pass and propagate the sketched node embeddings layer-by-layer, while the sketching in [1] only affect the backward pass since it use the original note embeddings for propagation during the forward pass. \n(2) SketchGNN and EXACT sketch the note embedding along different axis.\n[1] estimates $CXW$ as $CXW\\approx C(XW)R_1R_1^T$, where $R_1\\in\\mathbb{R}^{d\\times r}$ is the sketching matrix with $c\\leq d$.\nFor Sketch-GNN, it estimates $CXW$ as $CXW\\approx CR_2R_2^T(XW)$, where $R_2\\in\\mathbb{R}^{c\\times n}$.\nHowever, [1] cannot accerlate the training process because they cannot propagate the sketched embeddings like SketchGNN.\nIf I was wrong, I would be more than happy be corrected.\n\n2. Based on the weak1, I checked the performance gap between [1] and this work, I found that [1] has much less accuracy drop (e.g., SKetchGNN has >1% accuracy drop on the ogbn-arxiv, while [1] is less than 0.5%). My guess is that because this work introduces errors and gets accumulated as it passes layer-by-layer during the forward pass. Theorem 1 in this work is actually indirect to the optimization process in the sense that it does not charactize the gradient dynamics. In fact if you apply any sketching technique during the forward pass, then the gradient is provably biased [2] (see Eq. 11 in [2] and its surrounding explanation).\nSo I suggest discussing the gradient bias into the theoretical analysis, which is not very hard to do, but will improve the soundness of this work.\n\n3. The overall algorithm is too complicated in the sense that it has at least four additional hyperparameters. (1) The truncation order of the power series for appoximating the activation function. (2) sketch ratio $c/n$. (3) the subset size $B$ for LSH. (4) The update intervel $T_{LSH} $for LSH. Too many additional hyperparameters highly limit the practical usage of the method because the cost of extra hyperparameter tuning grows exponentially.\n\n4. (important) What do you mean by \"train memory\" in Table 1? From L368, it seems to be the peak memory usage during training. I checked the codebase which is based on PyG. I believe the reported data is wrong in the sense that the full-batch GNN baseline on ogbn-arxiv should roughly requires 1G+ memory (roughly 700MB for activations) to train [3].\n\n5. What do you mean by \"epoch time\"? Is it the time for training one epoch? For GraphSAINT and VQ-GNN, each epoch contains serveral iterations while the full graph counterpart only have one iteration per epoch. Could you make this part more clear? Also, what is the epoch time of SketchGNN versus GraphSAINT/VQ-GNN on ogbn-products?\n\n6. The authors do not discuss about the compatibility of BatchNorm and Dropout. I believe them can be applied to the sketched note embeddings. \nHowever, I do not think they are useful in this case, especially for Dropout because sketched embeddings are denser compared to the original one.\n\n7. One last question is about the activations. \nI pretty like the idea of overcoming the non-linearity by approximating the activation function as a power series. Besides Sigmoid, could the author do an ablation study for approximating ReLU function using learned coefficents (since we almost do not use Sigmoid as the activation function in GNNs)?\n\ntypos: L234 ldots.\n\nAt last, I would like to say I like the idea of this paper and I think the idea is elegant. If my questions are discussed properly, I will raise my score.\n-----Update----\nAfter reading the rebuttal, most of my questions are addressed accordingly. I would like to raise my score to 7.\n\n[1] EXACT: SCALABLE GRAPH NEURAL NETWORKS TRAINING VIA EXTREME ACTIVATION COMPRESSION\n\n[2] Faster Neural Network Training with Approximate\nTensor Operations\n\n[3] GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9K5bQvtERNS", "reviewer": "Reviewer_Cdzo", "summary": "The authors propose a method to train graph neural networks more efficiently and hence make them amenable to large-sized graphs. \nThe main idea is to use hash maps on the graph nodes. More specifically, the authors propose to map the convolution matrices (n X n )and the feature matrix ( n X d ) to c hash buckets. Following this, the proposed algorithm only needs to access the c-dimensional sketched convolutional matrices and feature vectors, this leading to sub-linear complexity. The authors first present a framework based on count sketch and tensor sketches and derive feature update equations that only depend on the sketched data. However, using these updates in a straight-forward manner leads to instability during training. To address this, the authors propose to use locality sensitive hashing (LSH) and develop a practical algorithm for sketching based GNN training. The proposed algorithm then studies for its efficiency and performance across a few different datasets and baseline comparisons are provided. \nOn average, the proposed algorithm seems to perform better compared to the one other sub-linear time baseline algorithm in terms of efficiency and performance. In terms of efficiency, the algorithm outperforms other non sub-linear algorithms and also has similar performance. ", "questions": "I have already listed some suggestions in the \"weaknesses\" section above. Apart from those I have the following questions/ suggestion:\n\n1. Section D.2 also warrants a more mathematical discussion. It would be great to see the equations for how the sketched attention coefficients are computed. \n\n", "limitations": "The authors have discussed the limitations of their work. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The presented algorithm is interesting and the usage of LSH in the context of GNNs is novel. Although the presented ideas are based mainly on existing work on using LSH for deep learning ([8] and [9]), the present work differentiates itself by applying those ideas to develop a framework to train graph neural networks. \n\n2. Sub-linear complexity is particularly attractive and the presented results show that the proposed algorithm is good at taking advantage of the redundancy across graph nodes by using hash maps. The advantages of the algorithm in terms of efficiency and training are clearly shown in the experiments provided. \n\n3. The paper is technically sound and has a good flow of ideas. \n\nWeaknesses: \n\n1. One of my main concerns is the presentation of the paper. In my opinion, the main contribution of the paper is a discussion of how LSH can be used to train GNNs (as opposed to using tensor sketching, which has been allocated a lot of real estate in the paper). On many occasions, the details of the main algorithm are deferred to the appendix. For example, the paper would greatly benefit from having Algorithm 1 in the main body. In my opinion, this algorithm and the other details presented in section C are more important than the presented error bounds in section 3.2 (which could have been in the appendix instead). \n\n2. My second concern is regarding some of the experimental results: \n      a. In Fig 1a, why were the weights chosen to be identity matrices? More elaborate experiments with the learnt weights will make these \n          results more compelling. \n      b. Table 1. should include results for GAT as well. In general, GATs are more likely to face complexity issues while training because of \n           the expensive attention operation. I am curious to see the effect of the proposed algorithm on GATs. \n\n3. Another observation is that on many occasions, the authors use verbal explanation of techniques rather than equations and a mathematical presentation. For example, lines 252-265 might be better explained using a series of equations. The same can be said about most other \"subsections\" presented in Section 3.3. \n\nIn general, the paper need some restructuring to address the following points:\na. provide more details of the actual algorithm in the main paper (especially for 'online learning of sketches' and 'avoiding O(n) in loss evaluation'\nb. The presented error bounds are not very informative and could be moved to the appendix.\n \n4. The paper could include more references for related work, given that the field of sampling and sketching for graph neural networks is quite well-studied. See for example: \n[1] Calandriello, Daniele, et al. \"Improved large-scale graph learning through ridge spectral sparsification.\" International Conference on Machine Learning. PMLR, 2018.\n[2] Zheng, Cheng, et al. \"Robust graph representation learning via neural sparsification.\" International Conference on Machine Learning. PMLR, 2020.\n[3] Srinivasa, Rakshith S., et al. \"Fast graph attention networks using effective resistance based graph sparsification.\" arXiv preprint arXiv:2006.08796 (2020).\n\n\n    ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept