Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper is about using vector quantization to scale up GNN. The main idea is to use quantized representations combined with a low-rank projection of graph convolution matrix to avoid the "neighbor explosion" problem of GNNs. The proposed VQ-GNN is applied for node classification and link prediction, and shows comparable results.
main_review: 1) Although this paper is about scaling up the GNN training, the experiment is only on small-scale datasets, only one dataset for node classification and one for link prediction. It would be interesting to see larger scale experiments with nodes size in millions.

2) Seems this paper is about scaling up the training, it would be interesting to check the real training time vs accuracy. Why in table 4, per epoch time is faster than Cluster-GCN and GraphSAINT?   It seems to me that per epoch the proposed method will be slower as it needs additional time to update the codebook.

3) How is the performance w.r.t. number of layers? how about inductive and transductive settings?


limitations_and_societal_impact: NA
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents VQ-GNN: a scalable framework for training graph neural networks that approximates full-graph message passing with a memory of global notes that is updated during training. The authors derive approximate forward and backward passes and show that the network can preserve full-batch results while reducing computational and memory costs.
main_review: I think the general idea of approximating the general form of convolutional matrices with a low-rank decomposition is good. Is there a connection to the Reformer architecture (Kitaev, Kaiser et al 2020) and locality-sensity-hashing approximations to full attention matrices in Transformers?

The proposed method demonstrates substantial gains on link-prediction tasks relative to alternative scalable GNN training methods. The performance (accuracy / hits) is similar - and in some cases better - than the full-graph algorithm. Combined with the memory and training / inference speed gains, it makes for a compelling set of results.

I like the analysis of the fundamental scalability limitations of other ‘scalable’ GNN training algorithms. The highlight is the futility of managing the exponential receptive field dependence on the number of layers by dropping nodes or layers. In general the paper contains extensive theoretical results, and analyses of the method’s complexity relative to alternatives.

It would be useful to see some experimental analysis on codebook / minibatch size? For instance a plot of model performance / computational costs as a function of the minibatch or codebook size. Otherwise it’s not clear how sensitive the framework is to these factors.

It seems like a potentially important bit of experimental detail is added in the appendix [L641-646]:

“To mitigate the error induced by VQ in the high-dimensional space, we split feature vectors into small pieces. In practice, we find that when the dimension of each piece is 4, our algorithm generally works well. When the split dimension is 4 we have 32 separate branches each layer to do the VQ. These branches are independent and can be paralleled. At the end of each layer, separated feature vectors are concatenated together to restore the original hidden dimension, and the restored feature is input to the next layer

I found it a bit hard to understand this. Are the 4-dimensional vector pieces independently assigned to codebooks? If this is an important component then it would be useful to report some analysis in the paper. And the same for the other VQ-details: whitening and Lipshitz regularization. If the model is highly sensitive to these elements then that is a limitation. 
 
Overall, the proposed VQ-GNN framework is well motivated, well-executed and has promising results. Some additional analysis would be welcome, and potentially a restructuring so that some of the important practical details (product VQ etc) are made more apparent in the main body.

limitations_and_societal_impact: The authors have addressed the limitations around the tricks used to make the VQ work well. I think it is reasonable to explore these design choices in greater detail in future work. The authors briefly discuss societal risks relating to the use of large-scale GNNs in exploitative analysis of social networks.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 
The paper presents a vector quantization method to reduce the memory consumption of the convolutional operations for scalable GNNs. The method avoids subsampling nodes in the mini batches to prevent all the messages could be kept in the message passing operations. It quantizes the convolutional matrices leveraging the dimensionality reduction method. The approximated message passing with help of the quantization codewords is shown to have low relative error theoretically under certain conditions and have comparable accuracy with the original algorithm empirically.

main_review: Positive points:
1. The motivation and challenges are well-presented and related work seems to be adequate.
2. I like the idea of applying dimensionality reduction technique to quantize the feature and convolutional matrices in the GNNs. The experimental results seem convincing, though limited experiments are provided.

Comments:
1.	The notations and explanations are not very clear, especially in the ``approximated forward and backward message passing`` part of section 4.
2.	I would prefer to see more experiments and discussion on the hyperparameters selection and their affects to the algorithm such as the selection of the reduced dimension the mini-batch sizes, and the effect of different mini-batch sampling strategies.

During the rebuttal phase, the authors add additional experiments following the suggestions and I'm satisfied with the feedback and additional clarification given by the author. Considering the theoretical/experimental impact of the paper, I'd keep my rating towards marginal acceptance.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a technique to improve the scalability of GNNs for large graphs. In many existing works, neighbor nodes, GNN layers, or subgraphs are subsampled to reduce the burden on GPU memory. In this paper, instead of subsampling, the vector quantization (VQ) on the embedding vector of each node is introduced to reduce the memory and ensure scalability.
Technically, this paper develops a new approximation for message passing on codebook-represented graphs.
In theoretical evaluation, the paper shows that the prediction errors due to VQ can be upper-bounded by using Lipshitz regularization.
In the experimental evaluation, the generalization performance of the proposed VW method is comparable to existing scalable GNNs.
main_review: ## Originality: 
VQ + DNNs has already been studied in the famous VQ-VAE [29] paper and its followers. However, the combination of GNNs and VQ is new to me. Reducing the dimensionality of the embedding vectors is certainly a natural approach to memory compression. If there has been no previous attempt pursuing the scalability of GNNs in this direction, then I think this paper proposes a novel and valuable idea to the GNN community.

The discussion in Sec. 3 shows that if a good dimensionality reduction matrix R can be found, we can approximate well the node feature vectors. In this paper, VQ is chosen as one of the dimensionality reduction methods because it is a ''natural and widely-used method'', but are there any other ''natural and widely-used'' dimensionality reduction method choices? For example, if we don't need to use a fixed codebook, aren't PCA and FLDA also candidates?　
I expect more discussions on this issue to justify the choice of VQ. 

The appendix acknowledges that the quantized representation of Degree-Quant [35] improves the memory efficiency of GNNs, but [35] does not consider scalability and therefore does not conflict with the contribution of this paper. 
I'm not fully sure regarding this point. 
The main objective of both this paper and [35] is to reduce the memory burden of the computational device while avoiding subsampling. This paper and [35] try to achieve the same objective with different approaches: vector quantization in this paper and numerical quantization in [35]. Then these are not orthogonal, I think. 
It is very possible that I misunderstand the essences, and I would appreciate clarification on this point in the rebuttal discussion.

I think that the new algorithm for learning correctly on VQ codebook-represented graph mini-batches is a great job since it is technically non-trivial and the outcome seems reasonable. 

## Quality: 
Except for the details of some of the formulas, I find no major problems or concerns with the technical discussion in the main manuscript.

I did not follow the details of the proofs.

## Clarity:
In the left-hand side of equations (6.7), the lower halves of the vectors are omitted. 
What variables are being addressed here? Is it a variable that is not used in either the forward or backward calculations?

Table 3 is difficult to understand for me. 
In particular, the comparison of ``memory usage when the number of message passing is fixed'' What is the main message here? 
I read the paper several times, but in the end, I cannot figure it out. It's a concept I haven't seen in the context of many GNN papers, so unless you can explain it more clearly, I can't read any advantage of the proposed method from this table.

L302-303 ''We summarize the training and inference time........ in Table 3." should be Table 4. 

## Significance: 

The main weakness of this paper is that the experimental results.

The main purpose of this paper is, in my understanding, to propose a GNN technique with scalability to large graphs. However, Table 2 says that the memory usage of the proposed method is comparable to that of existing subsampling methods. This implies that there is no large graph dataset such that the proposed method is the first and the only solution for scalable GNNs. 

Another issue is the generalization performance. Unlike existing subsampling methods, the proposed method is unique in that it can retain all nodes and layers (L52-53). This paper examines the advantage of this characteristic in terms of numerical performance in Table 5. Among the four scalable GNNs, the proposed method obtains the highest performance in only one out of six cases. The best performer is NS-SAGE, which takes first place in three cases, and GraphSAINT is the runner-up, best in two cases.

This means that the proposed method does not show outstanding results or unique values among several solutions that provide scalability for GNNs.

So, why should we prepare a newly proposed method instead of using existing methods that have already been evaluated and implemented (e.g., GraphSAGE)? It is difficult to answer this question clearly, therefore it is difficult for me to recommend for acceptance in the current manuscript status.

In terms of computation time and time complexity, the proposed method is clearly superior to others (Table 2, 4). Therefore, I suggest that it would be better to focus on the point of fast computation rather than the general scalability.


(+) VQ for dimensionality reduction for GNN is (probably) new
(+) Approximate message passing for VQ codebook developed
(+) Theoretical guarantee for bounded prediction error
(-) More discussions for the choice of VQ dimensionality reduction are expected. 
(-) [35] is on the totally different lines of researchers, I'm not fully sure about that. 
(--) Experimental results for scalability and generalization are weak. 
(-) What is the main message of Table 3? 

## After feedbacks
I found the author feedbacks effectively resolve many of my misunderstandings and concerns. 
I raise my evaluations to 6, weak accept. Good luck!
limitations_and_societal_impact: Many VQ-related techniques are required to make the proposed method work satisfactorily. Discussed in Sec. 7.
review_title: null

Meta-review: 3 of 4 ratings were "accept". The concerns from the reviewer who gave the lowest rating (a 5) were not that clear to me through the extended  conversation with the authors, and I'm not swayed by their concerns.

The authors did extensive further experiments in response to the feedback, which reinforced their results.

Overall the believe the paper is a borderline-to-clear accept, given the novelty and performance.
Decision: Accept (Poster)