Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: 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.
strength_and_weaknesses: **Strengths:**
- 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'.

- 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.

- The problem addressed is understudied, and the solution presented seems novel.

**Weaknesses:**
- 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.

- 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.

- 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.
clarity,_quality,_novelty_and_reproducibility: **Clarity:**
Section 3 was, as mentioned above, a pleasure to read. The writing and mathematics were clear, accessible, and flowed well. The first two sections did a sufficient job of identifying key issues (e.g., compressing graph structure/features vs. weights) as well as identifying related approaches drawn from the graph literature outside of GNNs. Section 4 was less clear and suffered from a lack of messaging and poor plots.

**Quality:**
The core mechanism presented is sound, well-motivated, and clever. While there are a few generality questions, the work as-presented seems solid and the results (while limited) clearly show the method succeeds at its intended purpose.

**Novelty:**
The proxy graph constructed here is, as far as I am aware, novel. In addition, I consider the whole approach of the paper (using a smaller, synthetic, derived graph instead of attempting to compress the graph and features themselves) to be a useful shift in perspective. I believe both provide something to the community.

**Reproducibility:**
The method seems to be described in sufficient detail to be replicated without issue. I especially appreciated section 3.3's summary and listing 1. A companion code repository would be appreciated in the un-anonimzed final version, as the algorithm does not seem onerous to implement for the public.
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a new problem of serving (test-time/deploy-phase inference) of a trained GNNs efficiently. 
Many 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. 
The 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. 

Each training nodes must be mapped one of these virtual nodes. The mapping is learnf by weighted K-means of the tranining nodes. 
Propagation paths within the virtual nodes are also solved by a simple Frobenius norm minimization. 

The 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. 

strength_and_weaknesses: (+) the proposed problem is interesting, practically useful, and new to the community (At the reviewer's knowledge)

(+) the manuscript is well structured, easy to read, no logical jumps. 

(+) the proposed solutions are simple and reasonable. 

(+) experimental results. 

(-) 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. 

(-) preferably, compare with quantization methods. 


clarity,_quality,_novelty_and_reproducibility: I enjoyed the paper reviewering. 
The manuscript is highly easy-to-read. The problem is stated clearly, proposes solutions step by step. 

The huge trainng graph is problematic to deploy the trained GNN for not-so-powefull machines in the wild. 
The manuscript identifies this problem and derives technically sound solutions. 
The numbers in the experimental results strongly support the claims. 

Perferably, comparison with quantizqation methods will make the paper even stronger. They may be orthogonal to the proposed method, but it is not easy in general to deploy two approaches at the same time. 

The only concern is that the GNN reseraches broaden so much that I cannot follow all of its aspecets. Thus there is always a possibility that some prior works raised the similar questions in the past, though the reviewer is not aware of. 

Some questions

* How can we deal with grpahs with multi-type edges? for example, bond types in atomic molecular graphs, like/list/buy  relations of user-item purchase records. 
* The representations of the virtual nodes are confinedin the same space with the training node features. I guess this is due to the formulation of  Eq.(4). Is there a possibility that we can reduce the number of virtual nodes further, by allowing the virtual node features to have a larger dimensionality (>d) to augment its "Informative"-ness? 

summary_of_the_review: This paper proposes a new and pracitically valuable question of reducing the computational burden of GNNs. 
The idea is to compress the huge training graph into a smaller virtual node graph, by solving two simple optimization problems. 
The rationale is clear, proposed optimization problems seems reasonable. 
Strong experimental results support the goodness of the proposd problem and the solution.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
strength_and_weaknesses: Strength
1. The setting for online GNN inference is described clearly.
2. The two algorithms for feature vector and graph structure compression make sense. 
3. The empirical results are strong, having much higher accuracy than other methods at the same compression rate.

Weakness
1. 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.

2. 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.

3. 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.

clarity,_quality,_novelty_and_reproducibility: Clarity and quality need to be improved;
Novelty moderate;
Reproducibility unclear as code link is not provided. 

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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 

strength_and_weaknesses: Strengths:
- 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. 
- The paper introduces the virtual node set, which decouples the memory consumption of serving GNN from the training node features.
- Promising accuracy improvements in comparison to alternative baseline methods. 
	
Weaknesses:
- 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. 
- 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. 
- 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)? 

clarity,_quality,_novelty_and_reproducibility: Clarity
- The problem setup and motivation are clear. The paper also provides details about its methodology. 

Quality
- The writing quality of this paper overall is pretty decent and is easy to follow. 

Novelty
- The paper has good discussions in the introduction and related work about its novelty.  Although compression has been an extensively studied topic, compressing the feature vectors for GNN with virtual node sets appears to be novel. 

Reproducibility
- The paper does not provide many details about its implementation and hyperparameter settings for most of its configurations, which creates difficulties reproducing its results. 

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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposed a neat and clear strategy to compress the graph for serving GCNN model during inference. The idea is to create a small graph with significantly less no of nodes such that GCNN with node embedding trained on original graph can directly be used on the new graph with modified node embedding and the same inference algorithm.  This is a clear possibility and does solve a very real problem of reducing the churn during inference. 

The experiments are rigorous with all the interesting baselines. The fact that a clean method outperforms significantly many principled ideas is amazing. 
justification_for_why_not_higher_score: The fundamental idea of compression by reducing the no of nodes is quite common. 
justification_for_why_not_lower_score:  The confident reviewers were very excited about the paper. The proposal is simple and seems quite effective.
Decision: Accept: notable-top-25%