Serving Graph Compression for Graph Neural Networks
Authors: Si Si
Felix Yu
Ankit Singh Rawat
Cho-Jui Hsieh
Sanjiv Kumar
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Model compression
Graph Neural Networks

Abstract: Serving a GNN model online is challenging --- in many applications when testing nodes are connected to training nodes, one has to propagate information from training nodes to testing nodes to achieve the best performance, and storing the whole training set (including training graph and node features) during inference stage is prohibitive for large-scale problems. In this paper, we study graph compression to reduce the storage requirement for GNN in serving. Given a GNN model to be served, we propose to construct a compressed graph with  a smaller number of nodes. In serving time, one just needs to replace the original training set graph by this compressed graph, without the need of changing the actual GNN model and the forward pass. We carefully analyze the error in the forward pass and derive simple ways to construct the compressed graph to minimize the approximation error. Experimental results on semi-supervised node classification demonstrate that the proposed method can significantly reduce the serving space requirement for GNN inference.

Published as a conference paper at ICLR 2023
SERVING GRAPH COMPRESSION FOR GRAPH NEURAL NETWORKS
Si Si', Felix Ankit Singh Rawat', Cho-Jui "aiihh,,anjii Kumar'
l Google Research
University of California, Los Angeles
(s (sisidaisy, felixyu, ankitsrawat, (chohsieh| aucla.cs.ent
ABSTRACT
Serving a GNN model online is challenging - in many applications when testing nodes are connected training nodes, one has propagate information from train- ing nodes to testing nodes to achieve the best performance, and storing the whole training set (including training graph and node features) during inference stage is prohibitive for large-scale problems. In this paper, we study graph compression to reduce the storage requirement for GNN in serving. Given GNN model be served, we propose to construct compressed graph with smaller number of nodes. In serving time, one just needs to replace the original training set graph by this compressed graph, without the need of changing the actual GNN model and the forward pass. We carefully analyze the error in the forward pass and derive simple ways to construct the compressed graph to minimize the approximation error. Experimental results on semi-supervian node classification demonstrate that the proposed method can significantly reduce the serving space requirement for GNN inference.
INTRODUCTION
Graph Neural Networks (GNNs) (Kipf & Welling. 2016) have been widely used for graph- applications, such as node property predictions (Kipf & Welling, 2016), link predictions (Zhang & Chen, 2018), and recommendation (Wu et al., 2020). Given a graph that encodes relationships between pairs of entities, the graph convolution operation in GNN iteratively refines entity representations by aggregating features from neighbors, which enables information to propagate through the graph and boosts the performance on uncertain nodes.
has been well recognized that GNN training on large-scale input graphs challenging, and many scalable training methods have been proposed (Hamilton et al., 2017; Chiang et al., 2019; Chen et al., 2018a; Zeng et al., 2019). However, the problem of how to efficiently serve a GNN model in online applications remain unsolved. In fact, for applications when testing nodes connected with the training nodes, such as semi-supervised node classification, serving a GNN very challenging and has hindered the deployment of GNN in real world. To conduct predictions on batch of incoming lesting nodes, GNN has to propagate information not only within the testing nodes but also from training nodes testing nodes, which implies that the serving system needs store graph and node features in memory. Unfortunately, it is almost impossible to store the training graph and node features in many real systems such as embedded and low fow-resource devices. For example, for the Reddit dataset with more than 150k training nodes, it needs 370.7MB storage for the training node features, 86.0MB for the graph, and only 7.6MB for the GNN model itself. Table we break down the serving space requirements for four public datasets (with statistics in the experiment section) with GNN model size, training graph space, and training node features size. From this table, we can that the space bottleneck is the training graph and node features. We define the problem of reducing the size of training graph and node features as serving graph compression for GNNs.
Unfortunately, naively discarding all large portion of training nodes will significantly hurt the inference performance, since GNN has extracted very powerful node representations of training nodes, and propagating those information testing nodes is crucial for prediction. Figure illustrates

---

Published as a conference paper at ICLR 2023
Table Model size and serving space of several GNN models,
Datasets
Model size
Training graph size
Training feature size
Total serving size
Arxiv
1.4MB
5.9MB
46.5MB
53.8MB
Reddit
7.6MB
86.0MB
370.7MB
464.3MB
Product
4.8MB
87,2MB
78.6MB
170.6MB
Amazon2M
3.0MB
485.4MB
684.0MB
1.17GB
this problem, where show that when discarding some part of training data, the performance of GNN will significantly reduce even on a standard node classification task.
Although the problem of serving graph compression has not been formally studied before, at the first glance the problem seems be solvable by adopting existing approaches. The first approach one can eas- ily come up with is to treat training node features as weight matrix and apply existing model compres- sion techniques such as sparse or low-rank approx- imation (Han et al., 2015; Frankle & Carbin, 2018; Sainath et al., 2013; Chen et al., 2018b). However, existing model compression methods are not able to exploit graph information, and we will show in the experiments that they tend perform poorly for serv- ing graph compression. Another straightforward idea core-set selection prob- is to treat the problem lem, where many algorithms have been developed to select subset of important samples from massive data (Mirzasoleiman et al., 2020; Wang et al., 2018; Zhao et al.. 2020). However, core-set selection meth- ods are trying to obtain small subset such that the model trained on the subset still achieves reasonable performance, and this goal is different from serving compression. For example, Jin et al. (2021) showed it's possible to extract a small synthesized graph for training, but they still require the whole training set in the inference phase to achieve good performance.
rondem drooping sccuracy
0.93
0.33
0.55
randon rodes
u.ash gmip
0.90
Figure 1: Random nodes dropping rate vs.
accuracy on Reddit dataset. The red line is the accuracy of inference using the entire graph and features; purple line is the accuracy of inference without graph; blue line accuracy for randomly dropping nodes in the graph with different dropping rate.
In this paper, we propose simple and effective method for GNN serving graph compression via virtual nodes graph (VNG). Given GNN model to be served online, our method aims to construct a small set of virtual nodes, with artificially designed node features and adjacency matrix, to replace the original training graph. Without changing the model and the forward pass, users can just replace the original training set by the small representative requirement with small loss in testing accuracy. To construct the set of virtual nodes, we decompose the error of forward propagation into (1) the propagation error from training node features to testing nodes and (2) the propagation error from training to training nodes. Interestingly, the error in (1) can be bounded by a weighted kmeans objective, while the error in (2) can be minimized by solving a low-rank least-square problem to preserve consistency within a certain space constraint. These together lead to simple yet effective GNN serving graph compression that is easy to use in practice.
in the serving time reduce the space
Our work makes the following contributions:
To the best of our knowledge, this is the first work on the serving graph compression problem for GNN models, addressing the bottleneck when applying GNN in real world applications.
By analyzing the error in forward propagation, we design a simple yet effective algorithm to construct a small virtual node set to replace the original huge training set for model serving.
We show on multiple datasets that the proposed method significantly outperforms alternative ways of compressing the serving graph.
2 RELATED WORK
Graph Neural Networks In this paper, we focus on GNN problems when there is graph connect- ing entities of training and testing instances, including many important applications such as node classification, edge classification and recommendation systems. Note that there's 's another application of GNNs where each instance is a graph and we aim to predict properties of a new instance (graph), such as for molecular property prediction (Gilmer et al., 2017; Wu et al., 2018). Since in those applications training and testing graphs (instances) are disjoint and there is no need to store training graphs for serving, they are out of the scope of this paper.
2

---

Published as a conference paper at ICLR 2023
Many improvements have been made GNNs in recent years. Based on the graph convolution operation, many different designs of graph neural networks have been proposed to achieve better performance (Veličković et al., 2017: Shi et al., 2020: Li et al., 2021; Chen et al., 2020; Xie et al., 2020; Chien et al., 2021). Also, although training GNNs with large networks is difficult, many scalable training algorithms have been developed (Hamilton et al., 2017; Chen et al., 201 20; 2017; Chiang et al., 2019; Zeng et al., 2019). In contrast to previous works, we study the inference phase of GNN which has been overlooked in the literature. In the serving phase of GNN, it requires storing both GNN model weights and training data (including node features and training graph) to achieve the best performance, since connections from training to testing nodes are crucial for feature propagation. Since the size of training data is often more than 40x larger than GNN model weights, we focus on shrinking the size of training data in this paper. Existing works on compressing GNNs focus on reducing or quantizing the model weights (Tailor et al., 2020; Yang et al., 2020; Kim et al., 2021), which is orthogonal to our work. Another recent work (Chen et al., 2021) tried to prune both model weights and graph by removing some edges. However, they do not reduce the size of training features so the serving space requirement will not be significantly reduced.
Model compression Since the training feature matrix dominates the serving space, a straight- forward method is to apply existing model compression techniques, such as pruning or low-rank approximation (Han et al., 2015; Frankle & Carbin, 2018; Sainath et al., 2013; Chen et al., 2018b), to the training feature matrix. However, we find those methods are not very effective in practice (see our experiments). This is because that standard compression methods to not consider feature matrix and graph jointly, and they do not really focus on reducing the forward pass error in GNN inference. Another commonly used compression method is quantization (Gholami et al., 2021). However, quantization is orthogonal to our method since we can also apply quantization after getting the virtual representative nodes with our method.
Coreset selection and Dataset distillation Since the bottleneck of GNN serving space is training data, it may seen natural to apply coreset selection or dataset distillation methods here. Various coreset selection algorithms, including k-median (Har-Peled & Mazumdar, 2004), mixture models (Lucic et al., 2017), low-rank approximation (Cohen et al., 2017). and gradient matching methods (Mirza- soleiman et al., 2020), are designed to select subset of essential samples to expedite training. On the other hand, dataset distillation methods (Wang et al., 2018; Zhao et al., 2020; Cui et al., 2022) create a small set of synthetic data that enables models trained on the synthetic dataset to achieve comparable performance to those trained on the original set. However, these methods do not utilize the graph information. Furthermore, these methods are designed to select a coreset for efficient training, while our goal is to select coreset to compress the serving space requirement. We will compare with some standard coreset selection methods the experiments to demonstrate that they are not effective for our task. Further, although several recent works try to select coresets for graph data (Jin et al., 2021; Zhang et al., 2021), they still focus on selecting a coreset for training while utilizing the full training set in the inference phase. It's nontrivial to apply them for inference speed up since the connections between testing nodes and core-set nodes are not well defined.
Graph Coarsening Graph coarsening is widely used in the scalable graph clustering, with the aim to reduce the size of the graph or form some supernodes in the graph to represent the original graph (Liu et al., 2018; Chevalier & Safro, 2009). Most of them are trying preserve some unsupervised properties of the graph, such as adjacency matrix or normalized Laplacian (Spielman & Teng, 2011; Bravo Hermsdorff & Gunderson, 2019). Graph coarsening method do not consider either model or the node features, and thus are not as effective for our task.
3 PROPOSED METHOD
3.1 PROBLEM DEFINITION
For simplicity, we will consider the canonical graph convolutional network (GCN) model (Kipf & Welling, 2016), but our method can also handle other GNN architectures. In the training phase, we given the training graph G (V, E) with n | vertices and |E] edges. The corresponding training adjacency matrix, denoted as Atrstr E _ is a sparse matrix with (Aer,tr)i * 0 if and only if there is edge between node and node j. and the value of (Aer,tr )ij denotes the weight of the edge. Note that standard GNN models usually conduct row normalization to the binary adjacency matrix and we directly assume Atrar is the normalized matrix here. Each node in the training graph is associated with d-dimensional feature x; Rdd and use Xxr E Rand denote the
3

---

Published as a conference paper at ICLR 2023
feature matrix. We use X, to denote the i-th row of matrix X, following this notation we have (Xtr)i- Fy. Starting with X = Xtr, an T-layer GCN propagates node features layer-by-layer:
( Am ((000) x(++1) =z( o......, L.
(1)
where ( is the feature matrix at the ê-th layer, W(O is the weight matrix of fully connected layer, and a is nonlinear activation (usually beiment-wise ReLU). Atr, is the graph convolution
operation, which obtains a new representation of each node by weighted average of its neighbors.
After L GCN layers, each node will obtain its final layer representation X(E), which will be associated with a loss function depending on the final task. A canonical application for GCN is semi-supervised node classification. In this application, each labeled node is associated with an observed label yı, and we can use the standard cross-entropy loss to train the model. After training, we obtain the model weights W = " W(L-))
In this paper, we focus the serving phase of the GNN models. Depending on different scenarios, testing nodes can come one-by-one, batch-by-batch, or all together. For simplicity, we assume conducting GCN inference on single node with feature æ E IR and its connection to training nodes is represented by E R". In this case, GNN will conduct the following forward propagation to obtain node features
= Atrer a
0 x
W
[x(et)) x((t1)
= o(
(0+1) (((+1 (2
) x (0) = I.
(2)
where ā is the constant depending how the GNN deals with the diagonal entries' Note that this can be easily generalized to cases with larger batch size m, where x will be replaced by an m-by-d feature matrix; a will become an m-by-n matrix representing the connections between testing and training nodes, and ā will become the adjacency matrix between testing nodes.
We have demonstrated in Figure 1 that including training graph and node features in the serving phase is necessary. Intuitively, intermediate features for training nodes are very informative and propagating those information to testing nodes will significantly boost the performance. Also note that in (2) we assume there is no information flow from testing to training (0 in the top-right corner of joint adjacency matrix). This is because training nodes already have good features obtained in the training phase, so there is no need to propagate testing features to training nodes. This is adopted in several real GNN implementations (Chiang et al., 2019) and we found that setting the top-right corner of A as or a. have similar performance in practice.
As evidenced from (2), the serving phase of GNN requires storing model weights W, training node features Xtr and training graph Atr,tr. Storing Xtr and Atr,tr requires O(nd) and O(1g)) space respectively, and both of these are much larger than the size of W which consists of L -sized matrices, with the corresponding storage requirement being independent of n. Taking standard Reddit dataset as example, there are n = 153, 932 training samples and d = 602 features, X 's size is 370.7MB, Atr,er's 's size is 86.0MB, and W is only 7.6MB size.
Accordingly, for GNNs, we define the task of reducing the space requirement for serving by primarily compressing X., and Aer,tr the serving graph compression problem.
3.2 THE VIRTUAL NODE GRAPH (VNG) METHOO
We propose the virtual node graph (VNG) method in this section. The main idea is to replace training nodes by a small number of e virtual (VR) nodes, with c & n. Let X E Rexd be the features and Aur.ur E e be the adjacency matrix of the VR nodes, we aim to obtain those matrices by minimizing the forward propagation error. With the training nodes replaced by VR nodes, the graph convolution operation (first equation of (2)) will be replaced by
z (E-1)
Apr, aur
X (E) ( ((
(3)
2 (e-1))
Note that aur in (3) represents the connection from node u to the VR nodes, which cannot be a fixed vector since it will depend on the the original (the connections between node v and training nodes).
Can be 0 depending on the implementation, while some others methods add small constants diagonal.
4

---

Published as a conference paper at ICLR 2023
We thus assume each original training node is represented by of the VR nodes, and the mapping is defined as т {l....,n] n + (l....c) c). We thus have
aur a 11,
where II E {0. 1 jaxe is the assignment matrix of the bipartite graph between training nodes and VR nodes. Specifically,
a 0/1 matrix with I = 1 if and only if x (i) = =..
With these setups, VR nodes will involve in two computations when computing the features for given node w: 1) The propagation from VR nodes to v 2) The propagation between VR nodes which will impact testing nodes in the next GNN layer. In the following, we will consider these two parts separately: in Sec 3.2.1 wc consider 1) to obtain a solution for and Xur, and in 3.2.2 we consider the 2) to obtain solution for Aur,er- We show with this two-step decomposition, all the components can be solved by simple closed form solutions which leads to an efficient and easy-to-imp casy-to-implement algorithm. Although the solution can be potentially improved by solving the whole problem jointly, we leave it to the future work.
3.2.1 PROPAGATION FROM VIRTUAL REPRESENTATIVE NODES TO TESTING NODES
Propagation from VR nodes node is the bottom row of the forward propagation in (3) and (2), where we want the resulting (f+1) to have minimal error. Therefore we want to have ax((0 W(() x fr
agr X (2) W(() alix or W(O which can be achieved if ax
aTIx(!) or
Since the testing nodes are unseen in the compression phase, we hope the compressed model to at least preserve the latent embedding when given every training node. If v is the i-th training node, then (Atr,t)).. Therefore, based on the spirit of empirical risk minimization, aim construct the II matrix to minimize the following averaged square error:
Σ
(Attr,))) (Aer,or); [I
Σ xE(m]
I1
Σ
(x (Aer,a)) )xx))))))
<E(m]
JEim]
Σ ie)n]
Σ jE(n]
(Aentr) (x!)) - (x(())()))1
-E JE(n)
E iE(m)
(Amntr )ir (x!)) - (x (X(2))())) 113
(6)
Let 73 (Airttr)) being the column sum of Arrtr, finding the VR nodes' features x!! and mapping x--) then equivalent to the weighted kmeans objective, with weight Ny for training node j.
As we aim to minimize the error for all layers, we can bound the sum of (6) over all layers. If we define the concatenation of features from all layers as
X,r = [x[e (0) ..... x!! x!!-"),,
(7)
since the weights are independent to layers, we can lower bound the sum of loss over layers per (6): Σ [E(()] Ene(nl [I(Atr,tr) X (6) (Ax,,..)
Eje(al ")]1(X.r))- (Xur) (8)
As the right hand side is equivalent to the weighted kmeans objective on X we can apply the well-known EM-style weighted kmeans algorithm to (approximately) optimize the upper bound, where it iteratively updates the cluster centers X,r and the cluster assignment л. After running weighted kmeans, will obtain the assignment nr,, and the cluster centers are weighted average of training features within each cluster, so ideally we would like VR nodes' features at layer é to be
2y
if T()) = i
FXX() where Fig ( 09
Eg Uq
otherwise.
Intuitively, E can be viewed as edges from training nodes to VR nodes, where each training node is only linked to one VR node. Since we only have freedom to assign the input features for virtual representative nodes, we set x = Ex(")) and since beyond first layer the features are computed by propagating previous layers feature with Avr,rr we will discuss how to assign Agr,rr to best preserve this property for other layers. Note that we assume all layers share the same II, which means each virtual node in different layers correspond to the same set of training nodes. Having different II for each layer requires different A ur or for each layer, significantly increasing the space complexity.
5

---

Published as a conference paper at ICLR 2023
3.2.2 PROPAGATION BETWEEN VIRTUAL REPRESENTATIV NODES
Note that the E' matrix obtained by weighted kmeans captures the transformation from training nodes to virtual nodes, and we have enforced (9) in the input layer. We will then study how to set the propagation among VR nodes or equivalently define the matrix Avr,r such that it preserves the property of (9) for other layers.
Towards this, assume that X!P EX!" holds at layer f. We then want make that conducting a graph convolution on both VR nodes and training nodes will preserve this relationship, i.e., (10)
Aur,er = Ex se EA
where the left hand side is the propagation of VR nodes and the right hand side is the propagation of original training nodes, with an additional projection operator to map the features back to VR nodes.
Note that we want the above approximation hold for all layers & [0, L 2]. Thus, summing the approximation error for each layer leads to the following optimization problem:
A Aer,or = arg ming ||EEX
Kerllf.
(11)
where X is defined in (7). Note that (11) can be easily solved by a standard least square solver. However, this will lead to dense x matrix, which leads to storage bottleneck when c is large. Therefore, we propose to obtain a low-rank solution of (11) by requiring H to have a rank at most < kt Such low-rank matrix can then be stored with only (cc)) memory overhead. With the rank constraint our optimization problem to solve for A takes the form:
Avr,rr = arg minH |IP - QII s.t. rank(H)= S k;
(12)
where P = EX and Q Er We now present closed-form optimal solution for (12).
Theorem Assume P V2 p and Q UQIaVa are the thin-SVD of P and Q, respectively. Then the solution of (12) is (QV,), E where (-)x denotes the rank-k truncated SVD of matrix.
The proof is deferred to the appendix. With this closed form solution, it is straightforward solve (12). Note that the closed form solution requires to compute the thin-SVD of P and Q. These are c-by-d matrices where es the number of virtual nodes and d is the hidden dimension size (sum all layers). As d is usually small (e.g., less than 3, 000 in all our cases) and the complexity of SVD is Ommnn(c, 2 max(c. d)), thin-SVD will be efficient (see Appendix C for details). In practice, this can be done within minutes on standard CPU, even without GPU. Note that it is necessary to store rank-k matrix A in factorized form realize the aforementioned O(ck) storage cost during inference, and our closed form solution in the above theorem naturally provide such a factorization.
3.3 OVERALL ALGORITIMM
Here we summarize the proposed Virtual Node Graph (VNG) algorithm from Section 3.2. Given the original GNN model and training data, we will first compute the collection of training node features before graph convolution X,, [x][) ....Xer x((-1)) For general GNN, these are features before one-hop propagation or mathematically, left-multiplying with the adjacency matrix. We then compute the column sum of the Agr,tr to get f7 ): subsequently we run weighted kmeans on X,, using these weights (cf. (8)). Given the clustering assignment obtained from the weighted kmeans,
X
we form an F. matrix based on (9) and set features for VR nodes as x!!) F.X(()) We then solve (12) with P = EX,,r tr and Q = -.Aer,tr-.err to obtain Agr,or (stored in the factorized form). At the inference time, the forward propagation is conducted by (2), where we only store virtual nodes instead of training nodes. The algorithm reduces the space complexity from the original O(n + [8] + nd) to Occk + od), where c < n is the number virtual representative nodes and a low-rank factor in (12). Please see Algorithm for the description of the algorithm.
4 EXPERIMENTAL RESULTS
To evaluate the performance of the proposed compression algorithm, we conduct experiments on four real datasets:

---

Published as a conference paper at ICLR 2023
Algorithm 1 The Virtual Node Graph (VNG) algorithm
Input: Training adjacency matrix Atr,tr and features Xtr, GNN weights W, number of virtual nodes rank of virtual adjacency matrix k.
1: Compute X,, = [x[r ..... ...... x(4-1) by GNN forward pass with training data Ar, and Xtr.
2: Compute weights "/ = E,, (Aertrr)) for all
3: π + weighted kmeans(2 (Xtr. c, (x))=1).
4: Get E matrix based on (4).
5: Compute X,r = tr (Xrr fr is the raw feature for training nodes).
6: Solve Avr,r based on (12).
Output: Aer and X
Table 2: The statistics of Arxiv, Reddit, Product, and Amazon2M datasets.
Datasets
#Training Nodes
#Validate Nodes
#Labels
#Features
Serving size
Arxav 90,941
29,799
40
128
$244BB
Reddit 153,932
456. MBB
Product
196.613
39,323
47
100
165.8MB
Amazon22
1,709.97
739,032
47
100
1,77BB
Arxiv: A multi-class node classification dataset used for predicting the category of a paper. We use the same dataset and partition in (Hu et al., 2020).
Reddit: A multi-class node classification dataset used for predicting the communities of online
posts. We use the same dataset and partition as in (Chiang et al., 2019).
Product: A multi-class classification dataset that is similar to Amazon2M, with key difference
that based on a different preprocessing and split by Hu et al. (2020).
Amazon2M: A multi-class classification dataset, where the graph has products co-purchase history, data features have each product's information, and the label is the category of the product. We use the same dataset and partition in (Chiang et al., 2019).
All above datasets are publicly available and are commonly used for benchmarking the performance of GNNs on node classification tasks. The statistics of these datasets are summarized in Table 2. As this is the first paper considering the serving graph compression problem for GNN, we mainly compare method against standard model compression methods (for compressing training node features) and core-set selection methods (selecting a subset of nodes for serving). Specifically, we include the following methods in the comparison:
Sparsifying the training nodes' features by sorting the values and removing small values in the features. For this method, the connection graph does not change. The serving space is controlled by the pruning ratio.
Sparse:
SVD: Performing SVD over the training nodes' features save the serving space. The serving space is controlled by the rank used in performing low-rank approximation via SVD. Also, note that the original graph remains unchanged for this method.
Random: Randomly selecting some training nodes and their corresponding subgraph.
Degree: Selecting the training nodes by sorting the degree of training nodes and picking the nodes
with the highest degrees.
Kmeans: Performing kmeans over the training nodes features, and selecting the training nodes
closest to the kmeans centroids.
VNG (our proposed method): Constructing the virtual nodes graph which much smaller than the original graph based on the GNN forward pass reconstruct error (cf. Algorithm 1).
We use the vanilla GCN architecture used in Chiang et al. (2019) to test the above methods. Note that the proposed compression algorithm can also be used for other GNN architectures, such as GraphSage Hamilton et al. (2017) (see Appendix E). We use ClusterGCN's tensorflow implementation for GCN model training. As for architecture, on all datasets, we consider 4-layer GCN model with hidden dimensions 512, 256, 512, and 400 for Product, Arxiv, Reddit, and Amazon2M, respectively. and the mean aggregator from Hamilton al. (2017). To test each model, we first train GCN model and freeze the model, then we run each method to generate compressed graph for efficient
https: thub. com www./ooow/oooooooooooooooooooooo resea rch rwtpggogi/eeeoooeooooooooooooroa reseerceah www.rreerrr/tteeeeattaaaea cluster_gen
7

---

Published as a conference paper at ICLR 2023
inference the new testing nodes. The process of graph compression and subsequent inference with the compressed graph does not involve retraining the GCN model.
Here consider two settings of inference. The first setting is batch inference, where given a batch of testing nodes at a time, with their node features and intervonnections. The connection from the testing nodes to the training nodes are also given. This is the typical setting for GNN model inference. The second setting is single node inference, where we assume the testing nodes appear one-by-one in an on-line fashion. In this setting, we only know the testing node features and the connections from this testing node to the training nodes. 4.1 BATCH INFERENCE SETTING
As explained previously, in the batch inference setting, we assume the testing data become available in batches. Since the edges connecting training nodes testing nodes and the connections among testing nodes are given, each testing node's features will be updated using the information from the training nodes and other testing nodes. We show the compression results in Table 3, where the graph size (including nodes' features and adjacency graph size) is shown in brackets following the accuracy. We construct the compressed graph with only %% and 5% of the total number of training nodes for our method. Note that Kmeans, Degree, and Random generate the graphs that have the same number of nodes as VNG.
From Table 3, we observe that our method is able to achieve very high compression rate for the serving space - 37.5x on Arxiv, 41. Ix on Reddit, and 69. Ix on Product. Other methods will suffer from significant performance loss when using such compression rate. Note that Sparse and SVD both operate on nodes' features, while maintaining the original adjacency graph. Thus, the compressed graph is still large the original graph. Random is not aware of the information in the graph and features. Kmeans only uses node features and is not aware of adjacency graph information. Degree considers adjacency graph and does not take features into consideration. Therefore, all the methods except ours consider either adjacency graph or node features, but not both. Furthermore, these methods are model agnostic the GNN model itself does not play role in the compression. In contrast, our method considers all three factors: adjacency graph, node features, and GNN model; consequently, performing better than other baselines.
Besides reducing the inference serving size, VNG can also speed up the inference. The detailed discussions and results about inference speed of VNG can be found in Table in the appendix. Also in Appendix A, we conduct an ablation study to show different variations of our method such as replacing weighted kmeans with vanilla kmeans or choosing different ranks during low-rant step.
4.2 SINGLE NODE INFERENCE SETTING
In the single node inference setting, each testing node appears one-by-one. Unlike the batch setting, no connections among testing nodes are given. Therefore, how to effectively utilize the information from training data becomes even more crucial. We compare our method with all the baselines in this setting and present the results in Table 4. Since our method able to better utilize the information of training graph and features, the accuracy gap between our method and baselines becomes larger.
4.3 TRADEOFF BETWEEN COMPRESSION RATE AND ACCURACY
In this subsection, we vary the compression methods in a wider range to demonstrate the tradeoff between compression ratio and accuracy. We consider the single node inference setting and plot the accuracy under different compression rates for each method in Figure 2. On each dataset, we increase the compression rate of VNG until its accuracy is within 1 1% of the full model, and show the performance of other methods under the same compression rate. It can be casily observed that our method significantly outperforms other methods also in this high-accuracy regime. The actual numbers for the accuracy and model size can be found in Table 9 in the appendix.
5 CONCLUSION
Although GNNs achieve promising performance handling graph data, they require storing training graph and features to perform inference, leading to a high serving space requirement. In this paper, propose novel method for serving graph compression, where we replace the training features and graph by a small set of virtual nodes. The features and adjacency matrix of virtual nodes are designed to minimize the forward propagation error of GNN and can be simply adapted to any GNN
8

---

Published as a conference paper at ICLR 2023
Table 3: Accuracy% (Size) four datasets for batch setting where test data appears in batches. The brackets next to accuracy show the compressed graph size including both adjacency matrix and node features. 'Full" corresponds to using the original adjacency graph and nodes features. For 'Random', 'Degree', "Kmeans', 'VNG', we show the results under different compression rates in the 'Node Compression rate' column-1 or 5% means the compressed graph contains 1% or 5% of the total number of nodes of the original graph. *For Amazon2M the number of nodes in the compressed
graph is 0. % 0.5% of the original graph.
Model
Node Compression rate
Arxiv
Reddit
Product
Amazon2M
Full
69.94 (52.4MB)
94.85 (456.7MB)
87.51 (165.8MB)
89.15 (GB)
SVD
58.69 (8.IMB)
88.35 (104,5MB)
40.82 (91,IMB)
68.08 (512. MMB
Sparse
56.90 (6.0MB)
68.27 (93.4MBB
64.75 (88.7MB)
66.45 (486. I IMB)
1%
58.32 (2.3MB)
71.23 (11.2MB)
70,26 (2.5MBB
17.80 (2.1MB)
Random
5%
62.85 (12.0MB)
77.91 (57.5MB)
74.57 (13.7MB)
77.98 (10.4MB)
1%
63.63 (3,2MB)
76.00 (15.5MB)
73.81 (3.8MB)
78.99 (2.8MB)
Degree
5%
66.42 (14.8MB)
86.62 (78.1MB)
79.36 (24.5MB)
81.71 (38.4MB)
1%
58.09 (2.4MBB
71.93 (MT.4MB)
69.73 (2.5MBB
77.15 (2.IMB)
Kmeans
5%
61.93 (12.0MB)
80.31 (60.3MB)
72.83 (14.3MB)
78.33 (21.0B)
1%
67.07 (L.4MB)
90.51 (11.IMB)
83.11 (2.4MB)
83.12 (2. IMB)
VNG (ours)
5%
68.64 (7.0MB)
91.00 (55 6MB)
85.60 (1L8MB)
84.23 (10.2MB)
Table 4: Accuracy% % (Size) on four datasets for single setting where testing data appears one-by-one setting. In the brackets next to accuracy, we show the compressed graph size including both adjacency matrix and node features. 'Full' corresponds to using the original adjacency graph and nodes features. For 'Random', 'Degree', 'Kmeans', 'VNG', we show the results under different compression rates in the 'Node Compression rate' column- % or 5% means the compressed graph contains I % or 5% of the total number of nodes of the original graph. *For Amazon2M, #nodes in the compressed graph
0.1% or 0.5% of original graph.
Model
Node Compression rate
Arxiv
Reddit
Product
Amazon2M
Full
68.35 (52.4MB)
92.75 (456.7MB)
86.95 (165.8MB)
87.79 (I.1GGB)
SVD
55.37 (8.MMB)
81.46 (104,5MB)
39.64 (91.IMB)
54.72 (512.7MB)
Sparse
51.54 (6.0MB)
54.55 (93.4MB)
60.81 (88.7MB)
61.32 (486. IMB)
1%
52.71(2.3MBB)
56.62 (1 1.MBB)
66.15 (2.3MBB
61.01 (2.1MB)
Random
5%
58.57 (12.0MB)
69.22 (57.5MB)
71.18 (13.7MB)
61.34 (10,4MB)
1%
60.58 (3.2MB)
62.58 )
7013 (3.8MB)
63.53 (2.8MB)
Degree
5%
63.95 (14,8MB)
77.18 (78. IMB)
76.77 (24.5MB)
67. 74 (38.4MB)
1%
52.51 (2.4MB)
57.42 (11.4MB)
65.57 (2.5MB)
60.99 (2.IMB))
Kmeans
5%
57.75 (12.0MB)
67.5 (60.3MB)
69.31 (14.3MB)
61.94 (21.0MB)
1%
66.73 (L.4MB)
90.51 (ILIMB)
83.04 (2.4MB)
82.53 (2. (MB)
VNG (ours)
5%
67.84 (7.0MB)
91.40 (55.6MB)
85.08 (118MB)
84.26 (10.2MB)
Reddit
Product
88
300
oecuracy
Accuracy
recuracy
3.0
Full
Bandom
Random
Full
Rull
Random
Kmeans
Kineans
Kmeara
360
Degrea
Degree
VNG
VNG
VNG
130 0M
666
ol0
613
314
650
3.4
6:00
650
nodes compression ratio
nodes compression ratin
nodes compression ratio
Figure 2: Comparisons of graph compression for GCN inference methods (single node inference setting). The x-axis shows the node compression ratio. The y-axis shows the accuracy of the node classification tasks. The graph sizes for Sparse and SVD are too large and they cannot realize the compression ratios considered in the figure.
structure. Our empirical results demonstrate that the proposed method can significantly reduce the GNN serving size while maintaining a reasonable predictive performance. As one of the limitations of our method, it may suffer from higher performance loss if a larger compression rate (c.g.. 50x) is desired, but it is possible to further improve by combining it with pruning quantization approaches.

---

Published as a conference paper at ICLR 2023
REFERENCES
Gecia Bravo Hermsdorff and Lee Gunderson. A unifying framework for sparsification and coarsening. Advances Neural Information Processing Systems, 32, 2019.
graph
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. arXiv preprint arXiv:1710.10566 2017.
Jie Chen, Tengfci Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling, arXiv preprint arXiv:1801.10247, 2018a.
Patrick Chen, Si, Yang Li, Ciprian Chelba, and Cho-Jui Hsieh. Groupreduce: Block-wise low-rank approximation for neural language model shrinking. Advances in Neural Information Processing Systems, 31, 2018b.
Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. A unified lottery ticket hypothesis for graph neural networks. International Conference on Machine Learning, pp- 1695-1706. PMLR, 2021.
Yu Chen, Lingfei Wu, and Mohammed Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. Advances in Neural Information Processing Systems, 33: 19314-19326, 2020.
Cédric Chevalier and Ilya Safro. Comparison of coarsening schemes for multilevel graph partitioning. In International Conference Learning and Intelligent Optimization, pp. 191-205. Springer, 2009.
Wei-Lin Chiang, Xuanqing Liu, Si Si. Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 257-266, 2019.
Eli Chien, Wei-Cheng Chang, Cho-Jui Hsich, Hsiang-Fu Fu Yu, Jiong Zhang, Olgica Milenkovic, and Inderjit Dhillon. Node feature extraction by selff-upprvised multi-scale neighborhood prediction. arXiv preprint 1Xxx:2111.00000 2021.
Michael Cohen, Cameron Musco, and Christopher Musco. Input sparsity time low-rank approxima- tion via ridge leverage score sampling. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1758-1777. SIAM, 2017.
Justin Cui, Ruochen Wang, Si Si, and Cho-Jui Hsich. De-bench: Dataset condensation benchmark. arXiv preprint arX1v:2007.09633,, 2022.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint arXiv: arXiv:/803.00 /803.03035., 2018.
Amir Gholami, Schoon Kim, Zhen Dong. Zhewei Yao, Michael W Mahoney, and Kurt Keutzer. A survey of quantization methods for efficient neural network inference. arXiv preprint 1xXiv:2/03.1362: 2021.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263-1272. PMLR, 2017.
William L. Hamilton, Rex Ying, and Jure Leskovee. Inductive representation learning on large graphs In Advances in Neural Information Processing Systems, 2017.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffiman coding. arXiv preprint arXiv:1510.00149, 2015.
Sariel Har- Peled and Soham Mazumdar. On coresets for k-means and k-median clustering, In Proceedings of the shitty-sixth annual ACM symposium on Theory of computing, pp. 290-300, 2004.
10

---

Published as a conference paper at ICLR 2023
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 wwXh::2005.00687 2020.
Wei Jin, Lingxia Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. Graph condensation for graph neural networks. arXiv preprint 1rXiv:2110.075800 2021.
Junghun Kim, Jinhong Jung, and U Kang. Compressing deep graph convolution network with multi-staged knowledge distillation. Plos one, 16(8))+026118, 2021.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks.
arXiv preprint arXiv: arXi: /0//6/60990002. 2016.
Guohao Li, Matthias Müller, Bernard Ghanem, and Vladlen Koltun. Training graph neural networks with 1000 layers. In International conference on machine learning, pp. 6437-6449. PMLR, 2021.
Yike Liu, Tara Safavi, Abhilash Dighe, and Danai Koutra. Graph summarization methods and applications: A survey. ACM computing surveys (CSUR), 51(3):1-34, 2018.
Mario Lucic, Matthew Faulkner, Andreas Krause, and Dan Feldman. Training gaussian mixture
models at scale via coresets. The Journal of Machine Learning Research, 18(1):58855509, 2017.
Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovee. Coresets for data-efficient training of machine learning models. In International Conference on Machine Learning, pp. 6960. PMLR, 2020.
Tara N Sainath, Brian Kingsbury, Vikas Sindhwani, Ebru Arisoy, and Bhuvana Ramabhadran. Low- rank matrix factorization for deep neural network training with high-dimensional output targets. In 2013 IEEE international conference on acoustics, speech and signal processing, pp. 6655-6659) IEEE, 2013.
Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjin Wang, and Yu Sun. Masked label prediction: Unified message passing model for semi-supervised classification. arXiv preprint arXiv:2009.03500 035009 2020.
Daniel A Spielman and Shang-Hua Teng. Spectral sparsification of graphs. SIAM Journal on Computing, 40(4):981-1025, 2011.
Shyam A Tailor, Javier Fernandez-Marques, and Nicholas D Lane. Degree-quant: Quantization-aware
training for graph neural networks. arXiv preprint arXiv:2008.05000 2020.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710. 170.1000,, 2017.
Tongzhou Wang. Jun-Jann Zhu, Antonio Torralba, and Alexei A Efros. Dataset distillation. arXiv preprint ar 1rxiv:1811.109 2018
Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph neural networks in recommender systems: survey. ACM Computing Surveys (CSUR), 2020.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learning. Chemical science, 92):513-5300 2018.
Yiqing Xie, Sha Li, Carl Yang. Raymond Chi Wing Wong, and Jiawei Han. When do gnns work: Understanding and improving neighborhood aggregation. In IJCAI International Joint Conference on Artificial Intelligence, 2020.
Yiding Yang. Jiayan Qiu, Mingli Song, Dacheng Tao, and Xinchao Wang. Distilling knowledge from graph convolutional networks. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 7074-7083, 2020.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. arXiv preprint arXiv:/907.044 2019.
11

---

Published as a conference paper at ICLR 2023
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks, arXiv preprint arXiv:1802.09691, 2018.
Wentao Zhang, Zhi Yang, Yexin Wang, Yu Shen, Yang Li, Liang Wang, and Bin Cui. Grain: Improving data efficiency of graph neural networks via diversified influence maximization. arXiv preprint arXiv:2208.000 00219, 2021.
Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. arXiv preprint wxXi:2206.05522, 2020.
12


Reviews:
[{"review_id": "zRGGORS76P", "reviewer": "Reviewer_LGG4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of reducing the memory consumption of serving GNN models. In particular, it identifies that some GNN models require node features in the training set data to make accurate predictions, which can add significant memory pressure. To mitigate this issue, the paper introduces VNG, a method that replaces some training nodes with a small set of so-called virtual nodes. By doing so, the total amount of memory consumption for serving GNN is reduced. Evaluation of GCN and several datasets show that the proposed methods can lead to higher accuracy than alternative methods. \n", "summary_of_the_review": "Despite there being some concerns about the evaluation of the proposed methods, I'm overall positive about the paper because of the identification of the challenges of serving GNN models and the promising results of achieving a high compression ratio while obtaining better accuracy than alternative methods. ", "strength_and_weaknesses": "Strengths:\n- The paper makes some interesting observations that when serving GNN models, nodes in the training sets may still be required, which leads to increased memory consumption. \n- The paper introduces the virtual node set, which decouples the memory consumption of serving GNN from the training node features.\n- Promising accuracy improvements in comparison to alternative baseline methods. \n\t\nWeaknesses:\n- Despite claiming memory is a major bottleneck in GNN serving, most datasets evaluated in this paper are rather small scale, with <500MB of memory consumption except Amazon 2M (<1.2GB), which are much smaller than the DRAM capacity. Also, it does not seem like all training features need to be loaded into DRAM at once, e.g., by loading the testing nodes and their neighbors or by loading a subset of training nodes on the fly, the memory usage can also be reduced. \n- Despite showing accuracy improvement in comparison to baselines created by the authors, the absolute accuracy drop in comparison to the uncompressed GNN is still large. For example, the accuracy drop is around 5 points for Amazon 2M. In practice, it is unclear whether such a huge accuracy drop can justify the compression ratio. Also, would other methods perform better than the proposed method at a higher accuracy target? One suggestion is to decrease the compression ratio to find a configuration that leads to similar or at least within <1% of accuracy loss compared with the uncompressed GNN and then reports the compression ratio the proposed method can achieve. Furthermore, it would be interesting to report under different compression ratios, how the proposed method compares with other alternatives. \n- Lack of comparison with quantization methods. The authors compared many methods, such as pruning and SVD. However, from the reviewer's perspective, one straightforward and also effective compression method is just to quantize the feature vectors,  e.g., basic quantization schemes using an INT8 symmetric quantizer. Would that lead to better accuracy than the proposed method (e.g., at 25% of compression ratio)? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "wcXJea0F2SA", "reviewer": "Reviewer_afao", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes to compress the graph and node features when serving the online inference of GNN. The scenario is that new nodes come with their connections to existing nodes, and output vectors of the new nodes need to be computed. The authors use a k-means based algorithm to compress the feature vectors, and an SVD-based algorithm to compress the graph structure. Empirical results show that the proposed method yields higher accuracy than other baselines.", "summary_of_the_review": "The paper considers compressing graph data for GNN inference. However, the application scenarios need to be further justified and the performance loss is significant. Moreover, experiments can be improved.", "strength_and_weaknesses": "Strength\n1. The setting for online GNN inference is described clearly.\n2. The two algorithms for feature vector and graph structure compression make sense. \n3. The empirical results are strong, having much higher accuracy than other methods at the same compression rate.\n\nWeakness\n1. The applications of online GNN inference are unclear. It would help if the authors could elaborate more on applications that use online GNN inference. My doubt is that the case of adding new nodes may be less common than adding/removing edges between existing nodes. For example, for recommendation and social networks, most of the nodes (e.g., users, products) may be already there but the edges experience constant changes due to user interaction. Also, in some business applications (e.g. PinSAGE), all embeddings in the graph are recomputed periodically.\n\n2. Compression yields obvious accuracy loss in the experiments. This may be unacceptable for applications such as recommendation because even marginal accuracy loss is important to revenue. Using out-of-core solutions (e.g., storing some data on SSD) may be more favorable to avoid accuracy loss.\n\n3. Experiments and presentations need to be improved. (1) Include some large graphs (e.g., MAG-240M and Papers100M) in the experiments, which helps to justify the need of compression; (2) Report the time used to compress the graphs (although analysis show that the complexity is low); (3) Adapt some graph coarsening methods (I think the task may be challenging but the results are good to have). For presentation, (1) Include the size of each dataset in Table 2; (2) Plot Figure 2 to make the axis and legends clearer; (3) On page 3, the authors mention that coreset selection has been used in training, what are the difficulties of adapting these methods for inference? Simply stating that these methods do not consider inference is not enough.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "WSZg3SXCfan", "reviewer": "Reviewer_t66n", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In order to support GNN inference via a served, pre-trained model, the authors present a method for constructing a small, auxiliary graph data structure which can act as a proxy for the features and structure of a larger training graph. This behaves similarly to compressing a training graph and allows a smaller chunk of data to be passed to inference clients.", "summary_of_the_review": "Overall, the method is clever and interesting. The paper does a good job of laying it out clearly for the reader, and the results are enough to convince me it works. There are some rough edges (generality, problem definition, evaluation) that could use improvement, but they don't seem bad enough to invalidate any of the main takeaways.", "strength_and_weaknesses": "**Strengths:**\n- The mechanism presented in the paper is mathematically clever, clean, and (after being explained) intuitive. Instead of attempting to brute-force the solution via direct graph/feature compression (which has extensive literature and could certainly have been applied, albeit with worse results I'd expect), they came up with a mechanism that synergizes with the behavior of GCNs. It's to their credit that the method can be accurately described as 'optimizing for GCN loss under space constraints' instead of 'optimizing for space and hoping for the best'.\n\n- The paper is incredibly well-structured. The pieces flow well from each other, and reading Section 3 was a surprisingly pleasant experience. The mathematics are accessible and clear.\n\n- The problem addressed is understudied, and the solution presented seems novel.\n\n**Weaknesses:**\n- The solution depends heavily on the formulation of the GNN model used. I suspect that the method can be generalized to other GNNs (perhaps with less mathematical simplicity), but the fact remains that it's tied to one incarnation as presented in this paper.\n\n- The problem setup is a bit artificial. While I understand the reason for using existing, widely-used datasets and classification tasks, I'm not convinced (as one who does not serve GNNs for inference as my day job) that the examples chosen are representative of the datasets and learning problems facing GNN serving. The authors don't seem to provide much support to the contrary, so it begs the question whether the choices are oversimplifying or skewing the results.\n\n- The evaluation was a bit underwhelming compared to the rest of the paper. The writing was poorer and confusing in places, key pieces of information were hard to find, the graph are not particularly readable, and the parameter sweeps were undermotivated and narrow. I suspect some of this could be fixed prior to publication, but the differences between sections 3 and 4 were palpable in the current version. Also, I noticed a distinct lack of computational performance information (the single comment at the end of section 3.2 was all I could find), which is a bit concerning in a paper which is trading compute for space.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NjBy4G6Ll0", "reviewer": "Reviewer_f4pk", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new problem of serving (test-time/deploy-phase inference) of a trained GNNs efficiently. \nMany GNN papers work on a semi-supervised node classification task. In that semi-supervised node classification scenarios, the trained GNN must retrain the huge memory load ot the entire training graphs to perform message passing of test nodes/edges. \nThe goal of this paper to reduce this test-time computatonal load in the test time infernece by compressing the training data nodes into a smaller set of virtual nodes. This is a practically valuable problem to tackle, but first introduced by this paper. \n\nEach training nodes must be mapped one of these virtual nodes. The mapping is learnf by weighted K-means of the tranining nodes. \nPropagation paths within the virtual nodes are also solved by a simple Frobenius norm minimization. \n\nThe experimental results show that the proposed method outperfroms naive methods for reducing test-time computatonl load in terms of the accuracy deteriorations from the \"full\" test prediction. \n", "summary_of_the_review": "This paper proposes a new and pracitically valuable question of reducing the computational burden of GNNs. \nThe idea is to compress the huge training graph into a smaller virtual node graph, by solving two simple optimization problems. \nThe rationale is clear, proposed optimization problems seems reasonable. \nStrong experimental results support the goodness of the proposd problem and the solution. ", "strength_and_weaknesses": "(+) the proposed problem is interesting, practically useful, and new to the community (At the reviewer's knowledge)\n\n(+) the manuscript is well structured, easy to read, no logical jumps. \n\n(+) the proposed solutions are simple and reasonable. \n\n(+) experimental results. \n\n(-) Tecnnical novely of the proposed solutions are not high: but this is a minor problem since the main virtue of the manuscript is the proposal of a new problem. \n\n(-) preferably, compare with quantization methods. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%