Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the embedding compression problem related to GNNs and graph representation. A two-stage method is proposed to generate the compressed embeddings: firstly, it encodes each node into its composite code with hashing; secondly, it uses a MLP module to decode the embedding for the node. Experiments are performed to evaluate the compression effect with both pretrained graph embeddings and node classification task with GraphSage. 
main_review: W1. The proposed method is straightforward, whose technical novelty is kind of limited given the recent works on embedding compression, e.g., [1], [2], [3].

[1] Learning to Hash with Graph Neural Networks for Recommender Systems. Tan et. al., the Web Conf 2020

[2] Differentiable Product Quantization for End-to-End Embedding Compression. Chen et. al. ICML 2020

[3] GHashing: Semantic Graph Hashing for Approximate Similarity Search in Graph Databases. , Qin et. al., KDD 2020

W2. The experiments studies are insufficient, many of the related works are missing from the evaluation, which is hard to support the paper's claimed contribution.

W3. The paper claims that the memory consumption is a bottleneck while training GNNs or graph representation models. Unfortunately, this claim is not true. In fact, the embedding table only needs to be partially loaded to GPU RAM during the training process. We would suggest the author to make reference to [4] for memory efficient implementation of their work.
 
[4] DGL-KE: training knowledge graph embeddings at scale, Zheng et. al., SIGIR 2020
summary_of_the_review: This paper works on the embedding compression problem for GNNs and graph representation models. However, the major limitations on technical novelty and experimental studies make it unlike to be a quality publication.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this work, the authors propose a hashing-based node embedding compression approach, which utilizes the random projection hashing method to generate a code vector for each node using auxiliary information such as the input graph adjacency matrix. The proposed method is memory-efficient in the training procedures of Graph Neural Networks (GNN) models. Experiments also demonstrate that the proposed method outperforms other coding schemes in both the embedding reconstruction task and node classification task.


main_review: Strength
1. The proposed method significantly reduces the memory cost when training the GNN models by adopting the random projection hashing approach.
2. Experiments on embedding reconstruction and node classification tasks demonstrate the proposed method outperforms the prior embedding compression method based on a random coding scheme.
3. The compressed embedding generated from the proposed method achieves a small loss compared to the raw embedding on the node classification task, which indicates that the proposed method solves the performance degradation problem to a certain extent. 

Weakness
1. The first concern is whether the proposed method still works on other graph representation learning models. In this work, the authors only used GraphSAGE with different aggregators in the evaluation. It would be great if the authors could discuss and include more graph representation learning models in the experimental section, such as GIN [1], deeper GNNs (e.g., [2], [3]), and graph representation learning models with greater expressive power than GraphSAGE (e.g., [4], [5]). 
2. Second, the experimental section only considers the node classification task, and I wonder if the compressed embedding generated from the proposed method still achieves good performance on other tasks, such as structural role prediction and link prediction?
3. Next, the authors use the adjacency matrix of the input graph as the auxiliary information in the paper. I wonder if other matrices related to graph structure can also be used as the input auxiliary information? For example, is it possible to use a higher-order adjacency matrix (i.e., $A^{k}$) to encode more global graph structure information?
4. Finally, it would be great if the authors could discuss about how to select the code cardinality $c$ and the code length $m$.


[1] Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2018). How powerful are graph neural networks?. arXiv preprint arXiv:1810.00826.

[2] Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K. I., & Jegelka, S. (2018, July). Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning (pp. 5453-5462). PMLR.

[3] Li, G., Muller, M., Thabet, A., & Ghanem, B. (2019). Deepgcns: Can gcns go as deep as cnns?. In Proceedings of the IEEE/CVF International Conference on Computer Vision (pp. 9267-9276).

[4] You, J., Gomes-Selman, J., Ying, R., & Leskovec, J. (2021). Identity-aware graph neural networks. arXiv preprint arXiv:2101.10320.

[5] Li, P., Wang, Y., Wang, H., & Leskovec, J. (2020). Distance encoding: Design provably more powerful neural networks for graph representation learning. arXiv preprint arXiv:2009.00142.
summary_of_the_review: In this work, the authors develop a hashing-based node embedding compression method, which significantly reduces the memory cost in the embedding learning procedure. The proposed method also outperforms the prior random coding based embedding compression method in the experiments. However, the experiments in this paper only utilized GraphSAGE as the graph representation learning model and considered the node classification task. It would be great if the authors could discuss and include more graph representation learning models and more graph related tasks in the experimental section. In addition, I wonder if the authors could discuss about the selection of input auxiliary information?
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper presents a vertex embedding method with good scalability to large graphs. 
The proposed method is based on locally-sensitive hashing and compositional coding: a memory-efficient binary representation of each vertex is constructed from a hashing technique and then, when needed, a decoder creates real vector embeddings of the vertices via compositional coding from a pool of codebooks. The encoding is constructed from prior knowledge and requires no training. Conversely, the decoder is trainable and can be learned end-to-end. The experiments show improved performance. A negative note is that some parts are unclear to me.
main_review: ## Positive aspects:

- The proposed method appears simple and effective. It relies on the well-established technique of locally-sensitive hashing and compositional coding. 
- The memory efficiency of the method makes it broadly applicable to large-scale graphs.
- The LSH encoding is constructed from prior knowledge (like vertex connectivity) or pre-trained embeddings, therefore it allows exploiting already available information.
- The method can be trained end-to-end together with all subsequent layers.
- The experiments show that there is only a limited loss in performance with respect to the uncompressed baseline, and substantial improvement with respect to ALONE.

## Negative aspects:

The only negative aspect I see concerns unclear parts that I detail right below.

1. In my opinion, the proposed "full" method (which appears to be the main method proposed by the authors, because it is employed in all the experiments) seems to be more similar to the "learn" baseline by Shu and Nakayama, than to ALONE, both in terms of trainable components and performance. While the improvements over ALONE are evident, a little comparison is provided against the "learn" method. For example, since both methods have learnable codebooks, it is unclear to me what is the additional training phase mentioned at the end of Section 2. Is it associated with the training of the encoder in "learn"? I also would like to see explicit comments on whether there are substantial methodological differences or improvement in efficiency for which one would choose the proposed method rather than "learn" one.
2. I could not find specified whether or not the three methods (ALONE, "learn" and the proposed "full") are set with the same hyperparameters. 
3. I think it would be great to also see whether or not there is any computational overhead associated with the three methods, and that the practitioner should be aware of.
4. The second part of the section Implementations about the word sampling requires more clarity. The methods are trained to embed the same subset of words or the words are sampled independently? The test set of 5k words is the same for the three methods?
5. When the auxiliary information matrix is constructed from the adjacency matrix, it seems to me that the test set results in a set of the most connected vertices because words are selected based on their frequency. Secondly, the auxiliary information for not high-frequency words is very sparse. I wonder if it is possible that the observed good performance is biased toward this specific test set. Could you comment on this?

summary_of_the_review: The method displays clear advantages over ALONE, and has the potential to be applicable in a wide range of problems, especially, large-scale ones.
Although the methodological contribution is little, the method appears simple and effective. 
However, given the mentioned unclear part, I tend to recommend a weak accept. I am confident the authors can clarify the raised doubts and I am happy to increase my score, if appropriate.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this paper, the authors present a general and scalable approach to obtain shallow embeddings of many entities. The authors achieve this by first mapping each entity into a code vector using LSH, and then learning a neural decoder on top of the code vectors to reconstruct the original embeddings/adjacency matrix. The authors then apply their approach to node classification problems, where node features are unavailable (the authors ended up artificially removing node features from existing OGB datasets). The superior performance is demonstrated over the random code vector baseline.
main_review: Strength
- The paper is well-written and easy to follow.
- Proposed approach can directly hash the adjacency matrix (no need to have the learned embeddings).

Weakness
- The main technical novelty seems the direct hashing of the adjacency matrix, which is graph specific. When pre-trained embeddings are given, the learning-based approach (Shu & Nakayama, 2017) seems sufficient.
- The evaluation is mainly made on the node classification benchmark. Many node classification benchmarks for GNNs are actually associated with features. In fact, in node classification, I would say that rich features are often available (so that the prediction can be based on the given features), and people often use graph information to regularize the prediction. 

Suggestion:
In many link prediction tasks (knowledge graph completion, recommender systems), the node features are often unavailable, and the primary learning signal comes from the edge connectivity information. There, the primary approach is to train shallow embeddings, and the key bottleneck is the storage of embedding for each node (especially for an industrial-scale large graph). I'd be much more impressed if you could demonstrate that your approach works well under the link prediction tasks.
summary_of_the_review: Overall, this paper is well-written, but the technical contribution is not sufficient, and the empirical evaluation should be done on a more practically-relevant task of link prediction.
review_title: null

Meta-review: This paper studies the embedding compression problem related to GNNs and graph representation. A two-stage method is proposed to generate the compressed embeddings: firstly, it encodes each node into its composite code with hashing; secondly, it uses a MLP module to decode the embedding for the node. Experiments are performed to evaluate the compression effect with both pretrained graph embeddings and node classification tasks with GraphSage.

The paper considers hashing/compressing the rows/columns of adjacency matrices and using the compressed rows of the adjacency matrices as node features. The adjacency matrices are  intrinsically redundant. Therefore, it is unclear whether the achieved compression rate is significant, especially when applied to settings with known node features. 

Some reviewers pointed out existing methods on learning-to-hash methods, which train a GNN-based encoder to compress the hidden representation/embedding, are relevant. Although the authors claim that in their scenario, the goal is to efficiently compress the input feature/embedding without any embedding/encoder pre-training step, it is unclear how the proposed method compares with the learning-to-hash methods when considering the adjacency matrices as the auxiliary information. 

The dependence on the number of nodes is also a concern in terms of scalability, as we know the bottleneck of scalability in GNNs is the number of nodes. 

The authors use the adjacency matrix of the input graph as the auxiliary information in the paper, which only considers local structure information. The reviewers are curious whether this approach would work for tasks in which global graph structure information is required. 

On a minor note, the reviewers also think that the paper would be stronger if the authors provide more principled guidance on how to select the code cardinality c and the code length m.
Decision: Reject