Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors propose a method to train graph neural networks more efficiently and hence make them amenable to large-sized graphs. 
The 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. 
On 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. 
strengths_and_weaknesses: Strengths:

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

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

3. The paper is technically sound and has a good flow of ideas. 

Weaknesses: 

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

2. My second concern is regarding some of the experimental results: 
      a. In Fig 1a, why were the weights chosen to be identity matrices? More elaborate experiments with the learnt weights will make these 
          results more compelling. 
      b. Table 1. should include results for GAT as well. In general, GATs are more likely to face complexity issues while training because of 
           the expensive attention operation. I am curious to see the effect of the proposed algorithm on GATs. 

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

In general, the paper need some restructuring to address the following points:
a. provide more details of the actual algorithm in the main paper (especially for 'online learning of sketches' and 'avoiding O(n) in loss evaluation'
b. The presented error bounds are not very informative and could be moved to the appendix.
 
4. 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: 
[1] Calandriello, Daniele, et al. "Improved large-scale graph learning through ridge spectral sparsification." International Conference on Machine Learning. PMLR, 2018.
[2] Zheng, Cheng, et al. "Robust graph representation learning via neural sparsification." International Conference on Machine Learning. PMLR, 2020.
[3] Srinivasa, Rakshith S., et al. "Fast graph attention networks using effective resistance based graph sparsification." arXiv preprint arXiv:2006.08796 (2020).


    
questions: I have already listed some suggestions in the "weaknesses" section above. Apart from those I have the following questions/ suggestion:

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


limitations: The authors have discussed the limitations of their work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

Experiments 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.
strengths_and_weaknesses: Strength:

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

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


Weakness:

* 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?

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

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:

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

2. The proposed techinique can be applied to different kinds of GNNs.

3. The theoretical analysis is correct and insightful, although I would like to note that it has a gap to the empirical results.

Weaknesses

1. 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]. 
In fact, [1] already applied the random projection-based sketching to the node embeddings. 
If you take a close look to Fig. 1 in [1], the main difference of sketching between this work and [1] are: 
(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. 
(2) SketchGNN and EXACT sketch the note embedding along different axis.
[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$.
For Sketch-GNN, it estimates $CXW$ as $CXW\approx CR_2R_2^T(XW)$, where $R_2\in\mathbb{R}^{c\times n}$.
However, [1] cannot accerlate the training process because they cannot propagate the sketched embeddings like SketchGNN.
If I was wrong, I would be more than happy be corrected.

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

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

4. (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].

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

6. The authors do not discuss about the compatibility of BatchNorm and Dropout. I believe them can be applied to the sketched note embeddings. 
However, I do not think they are useful in this case, especially for Dropout because sketched embeddings are denser compared to the original one.

7. One last question is about the activations. 
I 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)?

typos: L234 ldots.

At 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.
-----Update----
After reading the rebuttal, most of my questions are addressed accordingly. I would like to raise my score to 7.

[1] EXACT: SCALABLE GRAPH NEURAL NETWORKS TRAINING VIA EXTREME ACTIVATION COMPRESSION

[2] Faster Neural Network Training with Approximate
Tensor Operations

[3] GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings

questions: See above
limitations: See above
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: ### Strengths
- Motivation: This paper tackles an important problem, scaling GNNs to graphs of millions or billions of nodes has clear industrial applications.
- Clarity: The paper is very well written and easy to follow.
- 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.
- 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.

### Weaknesses
- 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.
- Achieved prediction performance is comparable or lower to GraphSAINT – a sampling-based approach; compared to VQ-GNN the prediction performance appears to be equivalent.

### Minor comments:
- A diagram illustration would further improve readability of the paper.
- Typos: line 131: “sorely” -> “solely”?; line 234: “ldots” command

In summary, the proposed method is a valuable contribution, albeit its practical limitations should be further discussed in the Experiments section and Conclusion. 
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.
2. 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?
3. 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?
4. Is this approach applicable to link prediction tasks? Would that necessitate potentially expensive un-sketching of node representations?
5. 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?
6. 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.
review_title: null

Meta-review: metareview: The authors propose the use of sketch GNN (based on compressing relevant matrices and sketching typical GNN operations via hashing) to enable better scaling of graph neural networks to very large graphs. The reviewers are all in favor of accepting the paper (with three accepts and one weak accept), and therefore I recommend its acceptance. I encourage the authors to take into account the reviewer comments, as they already indicated they will do during the rebuttal period, when preparing the camera ready version.
confidence: Certain
Decision: Accept