Embedding Compression with Hashing for Efficient Representation Learning in Graph
Authors: Chin-Chia Michael Yeh
Mengting Gu
Yan Zheng
Huiyuan Chen
Javid Ebrahimi
Zhongfang Zhuang
Junpeng Wang
Liang Wang
Wei Zhang
Venue: ICLR 2022 Submitted (2022)
Keywords: embedding compression
hashing
graph

Abstract: Graph neural networks (GNNs) are deep learning models designed specifically for graph data, and they typically rely on node features as the input node representation to the first layer. When applying such type of networks on graph without node feature, one can extract simple graph-based node features (e.g., number of degrees) or learn the input node representation (i.e., embeddings) when training the network. While the latter approach, which trains node embeddings, more likely leads to better performance, the number of parameters associated with the embeddings grows linearly with the number of nodes. It is therefore impractical to train the input node embeddings together with GNNs within graphics processing unit (GPU) memory in an end-to-end fashion when dealing with industrial scale graph data. Inspired by the embedding compression methods developed for natural language processing (NLP) models, we develop a node embedding compression method where each node is compactly represented with a bit vector instead of a float-point vector. The parameters utilized in the compression method can be trained together with GNNs. We show that the proposed node embedding compression method achieves superior performance compared to the alternatives.

Under review as a conference paper at ICLR 2021
EMBEDDING COMPRESSION WITH HASHING FOR EFFICIENT REPRESENTATION LEARNING IN GRAPH
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph neural networks (GNNs) are deep learning models designed specifically for graph data, and they typically rely on node features as the input node represen- tation to the first layer. When applying such type of networks on graph without node feature, one can extract simple graph-based node features (e.g., number of degrees) or learn the input node representation (i.e., embeddings) when training the network. While the latter approach, which trains node embeddings, more likely leads to better performance, the number of parameters associated with the embeddings grows linearly with the number of nodes. It is therefore impractical to train the input node embeddings together with GNNs within graphics process- ing unit (GPU) memory in an end-to-end fashion when dealing with industrial scale graph data. Inspired by the embedding compression methods developed for natural language processing (NLP) models, we develop a node embedding com- pression method where each node is compactly represented with a bit vector in- stead of a float-point vector. The parameters utilized in the compression method can be trained together with GNNs. We show that the proposed node embedding compression method achieves superior performance compared to the alternatives.
INTRODUCTION
Graph neural networks (GNNs) are representation learning methods for graph data. When a GNN model is applied on node classification problems, the model typically learns the node representation from input node features X and graph 9 where the node features X are used as the input node representation to the first layer of the model and the graph G dictates the propagation of information (Kipf & Welling 2016 Hamilton et al. 2017 Zhou et al. 2020p. However, the input node features X may not always be available for certain datasets. In order apply such type of model on graph without node features X, we could either 1) extract simple graph based node features (e.g.. number of degrees) from the graph g 2) embedding learning methods to learn the node embeddings as features X (Duong et al., 2019). While both approaches are valid, it has been shown that the second approach constantly outperforms the first one with noticeable margin (Duong al. 2019) and most recent methods learn the node embeddings jointly with the parameters of GNNs (He et al. 2017 2020 Wang et al. 2019).
Learning node features (or embedding) X for graph with small number of nodes may not be much of problem for common computer system. But, as the size of the embedding matrix X grows linearly with the number of nodes, scalability quickly becomes problem, especially when attempting to apply such method on industrial grade graph data. For example, if given graph has billion nodes, we set the dimension of the learned embedding to 64, and store the embedding X using single- format, the memory cost for the embedding layer alone 238 gigabytes, which is beyond the capability of common graphics processing unit (GPU). To solve the scalability issue, we adopt the embedding compression idea originally developed for natural language process-
precision floating-poin
ing (NLP) models (Suzuki & Nagata 2016 & Kobayashi 2020
Shu & Nakayama 2017 Svenstrup et al. 2017
Takase
Particularly, we study the ALONE method proposed by Takase & Kobayashi (2000) as it only
quires single stage of training unlike other methods. ALONE represents each word using a randomly generated compositional code vector; then decoder model, which can be trained end-to-end with

---

Under review as a conference paper at ICLR 2021
the downstream mode uncompresses the compositional code vector into floating tooting-poinnt vector. The bit size of the compositional code vector is parametrization by and m where cis the cardinality of each element in the code vector and is the length of the code vector. For example, if we set c = 4 and m = 6, one valid code vector is [2, 0, 3. 1, 0. 1] where the length of the vector is 6 and each element in the vector is within the set {0, 1, 2. The code vector can be converted of length m logg c by representing each element in the code vector as a binary number and concate- nating the resulting binary n Continuing the example, the code vector [2, 0, 3, 1, O, 1] can be compactly stored as [10 00 11 01 0001].
bit vector
GloVe, analogy
Glo similarity
rundom
random hrohing
boshing
Jeam
TaW
TEW
number of compressed entites
number of compressed entmes
metapathhvee, clustering
metapath2vec*** clustering
0.8
random
nandom
hasking gpre grannt)
hasting tramted
hashing
hashing (graph)
Jeam
kam
FUW
TBW
1ntam
number of compreseed untition
number of comproosred entitins
Figure 1: Three coding schemes are tested: 1) random coding/ALONE, 2) hashing- based coding/the proposed method, and 3) learning- based coding scheme with autoencoder. For GloVe embeddings, we apply the hashing-basee coding method on the pre-trained embedding. For metapa h vec and mettaptth22ect
embeddings, we apply the hashing-based coding method on either the pre- trained embedding or the adjacency matrix from the graph. The horizontal line labeled with "raw" shows the performance of the original embeddings' performance without any compression. The y- axis of each sub-figure is the performance measurement (the higher the better). See Section 3.1 for more details.
Using the same conversion trick, it only requires 48 bits to store each word with the parametrization (c = 64, m = 8, 8 log, 64 48 bits) used by Takase & Kobayashi (2020) in their experiments. The coding scheme can uniquely represent up to 2 words, which is way beyond the number of words (or sub-words) used conventional NLP models (Vaswani et al. 2017 7 Takase Okazaki 2019). However, generating the code vectors in a random fashion hinders the quality of the uncompressed embedding. One way to quickly benchmark an embedding compression method's capability is by evaluating the performance of reconstructed (or uncompressed)) pre-trained embeddings. As shown in Figure [ when the model compresses more and more embeddings, the performance of the recon- structed embeddings drops considerably when each entity is represented with randomly generated code vector following Takase & Kobayashi (2020) (see lines labeled as "random")) The phenomenon observed in our experiments with GloVe word embeddings (Pennington et al. 2014b) on both word analogy/similarity task and met
node embeddings (Dong
al. 70) on node clustering task.
In order to solve this performance degradation problem, instead of using randomly generated code vector to represent each entity, we adopt an efficient random projection hashing method to generate a code vector for each entity using auxiliary information such as the adjacency matrix associated with the graph g or the pre-trained embedding
The adopted random projection hashing method is
I For the experiments conducted by Takase & Kobayashi 2020), A ALONE's 's decoder model is trained together with transformer (Vaswani et al. 2017 Takase & Okazaki (019) on machine translation and summarization.
"hhe conversion mechanism is more space efficient when is set a power of 2.
We only apply the hashing-based coding method on the pre-trained embedding in experiments where the pre-trained embeddings are availahle (i.e., Section 5.T). For other experiments, we use the adjacency matrix provided by the associated graph G.
2

---

Under review as a conference paper at ICLR 2021
srccaltty-sensitve hashing (LSH) method (Charikar 2002) because it hashes entities with similar auxiliary information into similar code vectors. By referring once again to Figure [I the proposed method with hashing- based coding scheme (see lines labeled "hashing") outperformed the ran- dom coding scheme in all scenarios. Similar to ALONE, the proposed method does not introduce additional training stage since it is based random projection. On top of that, the memory footprint is identical to ALONE as the proposed method only replaces the coding scheme.
In additional to the proxy tasks of pre-trained embedding reconstruction, we also compare the ef- fectiveness of different coding schemes where the GNN model and the decoder model are trained together in an end-to-end fashion. Particularly, we trained the GraphSAGE model (Hamilton al., 2017) on three different node classification datasets. We choose to use the GraphSAGE model (Hamilton et al.) 2017) because it is one of the most scalable GNNs in the literature (Ying et al.) 2018). To show that the proposed method also benefits other GNNs/tasks, we present additional ex- periment results in Appendix [B.4]on more GNNs with link prediction task. The experimental results have confirmed the superb performance of the proposed hashing-basee based coding scheme comparing to the random coding scheme used in ALONE under the intended use scenario.
2 RELATED WORK
The embedding compression problem extensively studied for NLP models because of the memory cost associated with storing the embedding vectors, and one of the most popular strategy is param-
eter sharing (Suzuki & Nagatal 2016, (hhu Nakayama, 2017, [Svenstrup et al., 2017 Takase & Kobayashi 2020). For example. Suzuki & Nagata (2016) trains small set of sub- vectors shared by all words called "reference vectors" where each word embedding is constructed by concatenating different sub-vectors together. Both the shared sub-vecton and sub-vector assignments are opti- mized during the training time. The resulting compressed representation is capable of representing each word compactly, but the training process is memory costly as it still needs train the full embedding matrix to solve the sub-vector assignment problem. Therefore, the method proposed by Suzuki & Nagata (2016) is not suitable for large-scale data.
Shu & Nakayama (2017) trains a encoder-decoder model (i.e., autoencoder) where the encoder con- verts a pre-trained embedding into the corresponding compositional code representation and the decoder reconstructs the pre-trained embedding from the compositional code. Once the encoder and decoder are trained, all the pre-trained embeddings are converted to the compact compositional code representation using the encoder; then the decoder can be trained together with the down- stream models. Because the memory cost associated with the compositional code is much smaller than the raw embedding and the decoder is shared by all words, the method reduces the overall memory consumption associated with representing words. However, since it also requires training the embeddings prior to training the encoder-decoder, the training process still has high memory cost associated with the conventional embedding training similar to the previous work. In other words, the method proposed by Shu & Nakayama (017) is also not applicable extreme scale data.
Svenstrup et al. (2117) represents each word compactly with a unique integer and & floating point values where k is much smaller than the dimension of the embedding. To obtain the embedding from the compact representation of word, A hash functions are used to hash the word's associated unique [0, c) where is much smaller than the number of words. Next, & vectors extracted from a set of learnable "component vectors" based on the output of hash function. The final embedding of the word is generated by computing the weighted sum of the k vectors where the weights are based on the ie learnable floating -point values associated with the word. Similar to our work, Svenstrup al. (2017) also uses hash functions in their proposed method. But, the role of the hash function is different: Svenstrup et al. (2017) uses hash functions for reducing cardinality while we use hash functions to perform LSH. On top of that, as the learnable floating-point values are associated with each word in the method proposed by [Svenstrup et al. (2017), their method has its parameter size grown linearly with respect to the vocabulary size which makes the method not idcal for our application.
integer an integer in
The ALONE method proposed by Takase & Kobayashi (020) represents each word with a ran- domly generated compositional code, and the embedding obtained by inputting the compositional
"The hash function used by Svenstrup et al. 2017 is the hash function proposed by Carter & Wegman 1979) for hashing integers.
3

---

Under review as a conference paper at ICLR 2021
code to decoder where the number of learnable parameters in the decoder model is independent of the vocabulary size. The ALONE method checks all the requirements for our application; how- the performance suffers when the vocabulary size increases comparing to autoencoder-basee approach (Shu & Nakayamal 2017) as demonstrated in Figure (labeled as "learn"). In contrast, proposed method has similar performance comparing autoencoder- approach (Shu & Nakayama, 2017)) but does not require the additional training phases required by the method pro-
posed by Shu & Nakayama 2017).
METHOD
The proposed method consists of two stages: 1) encoding stage where each node's compositional code is generated with hashing-basse bbain method and 2) a decoding stage where the decoder is trained in end-to-end fashion together with the downstream model. Figure 2 shows example forward pass of the embedding construction process. The binary code is node compositional code gener- ated by the hashing-based method (Section 3.T.. After the binary code is converted integer code, the decoder model, which mostly includes m codebooks and a multilayer perceptron (MI.) as de- scribed in Section 3.2 generates the corresponding embedding. The memory cost storing both the compositional codes and the decoder is drastically lower than conventional embedding layer as
we shown in Section 5.2
codebooks (m-4)
c-4
codebook
lookup
Multlayer Perceptron
if the codebooks trainable
Integer
[2
embeoding
binary to integar
conversion
if Uhe codebooks are NOT trainable
Downstream Modal
binery code
[10 00 11 01]
Figure In this toy example, each codebook has 4 vectors (c and there are distinct codebooks (m = 4). There are two variants of the adopted decoder models: 1) light version where the codebooks are NOT trainable and 2) full version where the codebooks are trainable. Wo is trainable vector for rescaling the intermediate representation (see Section 3.2
3.1 HASHING-BASER CODING SCHEME
Algorithm [ outlines the random projection-basee based hashing method. The first input to our algorithm a matrix E Ruxd containing the auxiliary information each node where n is the number of nodes and d is the length of auxiliary vector associated with each node. When the adjacency matrix used as the auxiliary information, is equal to n, and it is preferred to store A as a sparse matrix storage (CRS) format all the operations other inputs include code cardinality c and code length m. These two inputs dictate the format (and the memory cost) of the output compositional code X. For each node's 's associated code vector, c controls the cardinality of each element in the code vector and controls the length of the code vector. The output is the resulting compositional codes X Baxm log. log, in binary format where each row contains node's associated code vector where m log, c is the number of bits required to store one code vector. We store X in binary format because binary format is more space efficient comparing to integer format. The binary code vector can reversed back to integer format before inputting it to the decoder.
in compressed
A are row-wise operations. The
In line the number of bits requires to store each code vector (i.e., m log, c) computed and stored in variable Nea-- In line 3, a Boolean matrix X of size n X пot is initialized for storing the resulting compositional codes. The default value for the matrix is False. From line 4 to 11, the compositional codes are generated bit-by-bit the outer loop and node-by-node the inner loops. Generating compositional codes in such order
memory efficient way to perform
4

---

Under review as a conference paper at ICLR 2021
Algorithm Encode with Random Projection
Input: auxiliary information A E IR= code cardinality code length m
Output: compositional code X Baxmlogg
function ENCODE(A, C, m)
2 Thu + m logg C
3 X + BETALLPALLEEBOEAAAAAAAYYYYY Nbn))
4
for i in [0, Tba) do
5
V <- GETRANDOM
6
U GETEMPTY
for j n)
8
U[] + DoTPRODUCT(Aji1I - GETMEDIAN(U)
9
10
for j in [0, n)) do
U[] > t then {(j i] + True
return X
random projection as it only needs to keep size d random vector in each iteration comparing the alternative order. If the inner loop (i.e,, line 7 to 8) is switched with the outer loop (i.c., line 4 to 11), it would require (i.e., matrix multiplication).
IR "ha matrix to store all the random vectors for random projection
In line 5, a random vector V Rd is generated; the vector V is used for performing random pro- jection. In line 6, an empty vector U E R" is initialized for storing the result of random projection. From line stored in U (i.e., U = AV). Here, the memory footprint could be further reduced if we only load few rows A during the loop instead of the entire A before the loop. Such optimization could be important as the size of A could be too large for systems with limited memory. In line 9, the median of U identified and stored to 11, using both the values in vector U and the threshold f, the binary code is generated for each node. Lastly, in line 12, the resulting compositional codes X are returned. The resulting X can be used for any downstream tasks.
each node's associated auxiliary vector is projected using the random vector V and
This the threshold for binarizing real values in U. From line 10
the median the threshold instead of the more commonly seen zero because it duces the number collisions in the resulting binary codo Reducing the number of collisions is important for our case because goal is to generate unique code vector to represent each node. To confirm whether using median as the threshold reduces the number of collisions, we have performed experiment using pre-trained met apath2ved node embeddings (Dong et al. (017a). We gen- erate the compositional codes with random projection-base hashing with either the median or zero the threshold. Then, count the number of collisions in the generated compositional codes. We repeat the experiment for 100 times under two different experimental settings (i.c.. 24 bits/32 bits). The experiment results are summarized in Figure 3 with histogram, setting the threshold to median instead of zero indeed reduces the number of collisions. We also repeat the experiments with aatapath2ve apath2vect+++ and G1 ove embeddings and the conclusion remains the same (see Ap- pendix B.1
Note,
bits
hashing zero Mashing-mediaa
hashing zero hashing-median median
number of collisions
66336
number of collistons
11656
Figure 3: The experiments are performed on metapath2vec for 100 times under two different bit length settings: 24 bits and 32 bits. The distribution of the 100 outcomes (i.e., number of collisions) for each method is shown in the figure. The number of collisions is lower for median threshold comparing to zero threshold.
'The threshold used the I.SH method proposed by Charikar 2002 zero.
5

---

Under review as a conference paper at ICLR 2021
The memory complexity of Algorithm | is (MM log2 d.f.ffnf.... n2f) where f is the number of bits required to store a poating--pom number. The nm log2 C term is the memory cost associated with storing X, the of term is the memory cost associated with storing V, and the nf term is the memory cost associated with storing U. Because f is usually less than m log2 e (i.e., based on hyper-parameters used in prior work and is usually less than or equal to n, the typical memory complexity of Algorithm | is O log, c). In other words, the memory complexity of Algorithm
the same as the output matrix X which shows how memory efficient Algorithm is. The time is O log, c) for the nested loop
complexity of Algorithm [
3.2 DECODER MODEL. DESIGN
We will use the example forward pass presented in Figure 2 to introduce the decoder design. The input to the decoder is the binary compositional codes generated from the bashing-based coding scheme introduced in Section 3.1 The input binary code is first converted to integers for using as indexes for retrieving the corresponding real vector from the codebooks. In our example, the binary vector [10, 00, 11, 01] is converted to integer vector [2, 0, 3, 1]. Each codebook is a Rexd, matrix where is the number of codes in the codebook (i.e., code cardinality) and de is the size of each real vector in the codebook. There are m codebooks in total where m is the code length (i.c., length of the code after being converted to integer vector from binary vector). Because the code length 4 in the example, there are 4 codebooks in Figure 2 Because the code cardinality is 4 (i.e., the number of possible values in the integer code), each codebook has real vectors.
From each codebook, a real number vector is retrieved based on each codebook's 's corresponding index. In our example, the vector corresponding to index (black) is retrieved from the first code- book, index O vector (green) is retrieved from the second codebook, index 3 vector (red) is retrieved from the third codebook, and the index vector (blue) is retrieved from the last codebook. The real vectors (i.e., the codebooks) can either be non-trainable random vectors trainable vectors. We refer to the former method as the light method, and the later method as the full method. The former method is lighter as the later method increases the number of trainable parameters by mcde. The full method is desired if the additional trainable parameters (i.e., memory cost) are allowed by the hardware. Note, despite the full method has higher memory cost, the number of trainable parameters still does not depend on the number of nodes in the graph.
Next, the retrieved real vectors are summed together. The summed vector is handled differently for the light and full method. As the codebooks are not trainable for light method, we compute the element-wise product between the summed vector and a trainable vector Wo E 12 to rescale each dimension of the summed vector following Takase & Kobayashi (2020). Such transformation not needed for the full method because the full method can capture this kind of transformation with the trainable parameters in the codebooks. The transformed vector is then fed to MLP with ReLU between linear layers. The output of the MIP is the embedding corresponding to the input compositional code, and the output embedding is fed to the downstream model.
If the number of neurons for the MLP is set to dm the number of layers for the MLP is set to and the dimension of the output embedding is set to de, the light method has med. non-trainable parameters (which can be stored outside of GPU memory) and de + dedm + (1 (1- (1-2)dl + dm trainable parameters. The full method has med + ded. + (1 2)dk, + de trainable parameters. Here, we assume is greater than or equal to 2. Note, the number of parameters does not grow with increasing number of nodes for both the light and full methods.
4 INTEGRATION WITH GRAPHSAGE MODEL
Figure shows how the proposed method is integrated with GraphSage model (Hamilton et al.) 2017 ). The figure depicts a forward pass during training. First, in step 0, batch of nodes is sampled. In step 1, for each node in the batch, number of neighboring nodes (i.e., first neighbors) are
'If preecssoe format is used for floating-poit numbers. f is 32 bit, and m log, e commonly set to a number larger than 32 bit in prior works (Shu & Nakayama 2017 Takase & Kobayashi (202)..
TThe median finding algorithm (Blum et al. 1973) in line 9 is ([n) which is the same as the inner loops
(i.c., line 7 to 8 and line 10 12.).

---

Under review as a conference paper at ICLR 2021
sampled. Because the example model shown in the figure has layers, the neighbors of neighbors (i.e.. second neighbors) are also sampled in step 2. Next, the binary codes associated with each node's first and second neighbors are retrieved in step 3 and decoded in step 4 using the system described in Section 3.2
D. batch of nodes
After the embeddings for both the first and second neighbors re- trieved, the second neighbor embeddings of each given first neigh- bor embedding are aggregated with functions like mean max in Aggregate 1 layer. Let's say H; contains the embeddings of neighboring nodes for given node i, the aggregate layer com- putes the output hū with AGGREGATE(H.). Next, in Layer 1, for each first neighbor node i, h4 and 2; (i.e., embedding for node i) concatenated and processed with linear layer plus non-linearity. The process of Layer 1 can be represented with aW - CONCATENATE((A, æ;)) where W is the weight associated with the linear layer and (-) is non-linearity like ReLU. Similar process is repeated in Aggregate erate the final representation of each node in the batch. Note, the concatenation step is omitted in Layer 2 because the node em- bedding of each node in the batch is not used in GraphSage model Hamillon al. 2017). The final prediction is computed by feeding the learned representation to the output (i.e., linear) layer. All the parameters in the model are learned end-to-end using the ground truth labels from the training data.
neightor
Neighbor Sampler
nodes
neighbor nodes 2. 1st and 2nd
Code
Lookup
1st and 2nd neighbor codes
Decoder
4. 1st and 2nd neighber embeddings
Aggragate
v
2 layer and Layer 2 to gen-
v
Aggregate
V
Layer
Dutput Layer
6. Prediction
5 EXPERIMENT
The proposed method be integrated with the GraphSage model. The Code Lookup is used look up the corresponding binary code for each input node. The Decoder is the system pre- sented in Figure 2 and con- verts the input binary codes to embeddings.
Figure- 4:
We perform two sets of experiments: 1) pre-trained embedding reconstruction and 2) training decoder with GraphSage model jointly. The first set of experiments reveals the difference be- tween different methods' compressing capability while the sec- ond set of experiments provides the performance measurement on the targeted application. All experiments are conducted in Python with PyTerch (Paszke et al.) 2019). The source code can be downloaded from: https: www. www.dropbox.com com/s/ 1mi ximggggghg www.t///eeeeeeeee...
5.1 PRE-TRAINED EMBEDDING RECONSTRUCTION
In this set of experiments, we compare the compression capability of different compression methods by testing the quality of the reconstructed embedding. The tested methods are the random coding (i.e., baseline method proposed by Takase & Kobayashi (2020)), the learning-based coding (i.e., autoencoder similar to the method proposed by (hhu & Nakayamal (2017)), and the hashing-base coding (i.e., the proposed method). When applying the hashing- based coding method on the graph dataset, we feed either the original pre-trained embedding (i.c., hashing (pre-trained) in Figure I or the adjacency matrix from the graph (i.e., hashing (graph) in Figure I into Algorithm We vary the number of compressed entities when testing different methods.
Dataset: Three sets of trained embeddings are used in these experiments: 1) the 300 dimension node embedding, and 3) the 128
GloVe word embedding, 2) the 128 dimension metapath2ver dimension metapath2vect node embedding. The G1 oVe embeddings are tested with word analogy and similarity tasks. The performance measurements for word analogy and similarity task are accuracy and Spearman's rho, respectively. The metapathhvvec/et hattteeettttteeeee beddings are tested with node clustering, and the performance measurement is normalized mutual information. Please see Appendix A.2 and Appendix A..3 for more details regarding the datasets.
em-
Implementation: We use the full decoding method in this set of experiments. To train the compres- sion method, we use mean squared error between the input embeddings and the reconstructed em- beddings as the loss function following Takase & Kobayashi (2020). The loss function is optimized
7

---

Under review as a conference paper at ICLR 2021
(Loshchilov & Hutter 2017) with the default hyper-parametee settings in PyTorch Paszze et al. 2019). Because we want to vary the numbers of compressed entities when comparing difterent methods, we need to sample from the available pre-trained embeddings. Similar to Takase & Kobayashi (2020), we sample based on the frequency Since different experiments use different numbers of compressed entities, we only evaluate with the same top 5k entities based on frequency similar to Takase & Kobayashi (2020), despite there are more than 5k reconstructed embeddings when the number of compressed entities is greater than 5k. In this way, we have the same test data across experiments with different numbers of compressed entities. The detailed hyper-parameter settings are shown in Appendix [A.4
with AdamW
Result: The experiment results are summarized in Figure ! Note, we use "random" to denote the baseline method (i.e., ALONE). When the number of compressed entities is low, the reconstructed embeddings from all compression methods perform similar to using the raw embeddings (i.e., the original pre-trained embeddings). As the number of compressed entities increases, the reconstructed embeddings" performance decreases. The decreasing performance is likely caused by the fact that the decoder model's size does not grow with the number of compressed entities. In other words, the compression ratio increases the number of compressed entities increases (see Table B in Ap- pendix [.2).. When comparing different compression methods, we can observe that the quality of the reconstructed embeddings from random coding method drops sharply comparing other meth- coding). It is surprising that the hashing-
ods (i.e., hashing- based coding and learning-bant coding method works as well as the learning-basee coding method even if the learning- basendd-aaddddee coding method uses additional parameters to learn the coding function. When we compare both variants of the proposed coding method (i.e., hashing with pre-trained and hashing with graph, i.e., adjacency matrix), the performance are very similar. This shows how the adjacency matrix from the graph is a valid choice for applying the proposed hashing-baat based coding method. We have also tested other settings of and m (see Appendix B.2);; the conclusion stays the same.
5.2 NODE CLASSIFICATION
To examine the difference between the compression methods in the intended setup, we perform node classification where the decoder is trained together with a GraphSAGE model (Hamilton et al. 2017 Because we assume there is node feature or pre-trained embedding available in exper- iment setup, the autoencoder-basse method proposed by [Shu & Nakayama (2017) is not applicable for this set of experiments. We compare the proposed hashing-based coding method (using adja- cency matrices and Algorithm [ to generate the code) with two baseline methods: random coding method and raw embedding method. The raw embedding method explicitly learns the embeddings together with the GraphSACE model. The raw baseline method can be treated as the upper bound in terms of accuracy because the embeddings are not compressed. the performance measurement is classification accuracy.
The experiments are performed on the ogbn-arxiv, agbn-mag, and from Open Graph Benchmark (Hu et al. 2020). As we are more interested in modeling attribute-less graphs, we discard the node features included in the datasets. We convert all the directed graphs to undirected graphs by making the adjacency matrix symmetry. Please see Appendix A.5 for more detailed information regarding the datasets.
Dataset:
datasets
Implementation: For the downstream model, we use the PyTorch implementation of the GraphSAGE model (Hamilton et al., 2017 Johnson et al., 2018). Because the node classification problem is multiclass classification problem, we use the cross entropy loss to train both the decoder and the Graph SAGE model together. The loss function is optimized with Adamw (Loshchilov &l Hutter 2017) with the default hyper-parameter settings in the GraphSAGE implementation (John- son et al. 2018). We perform the experiments using two different aggregators: mean pooling and max pooling. The detailed hyper-parameter settings are shown in Appendix A.6
Result: According to Table [ the proposed hashing-based coding method outperforms the random coding method (i.e., ALONE) in all tested scenarios which agrees with our findings presented in One possible reason for the random coding method's 's less impressive performance com- paring to the result reported on NLP tasks by Takase & Kobayashi (2020) related the number
Figure D
$Por GloVe, frequency means the times of a word occurs in the training data. For metapath.vec and met.aptthvvcct frequency means the times of node occurs in the sampled metapaths.
8

---

Under review as a conference paper at ICLR 2021
of entities compressed by the compression method. In NLP models, embeddings typically represent sub-words instead of words (Vaswani et al., (017). For example, the transformer model for machine translation adopted by Takase & Kobayashi (2020) has 32,000 sub-words, which is much smaller comparing to even the smallest tested graph dataset (i.e., oghn-arxiv with 168,390 nodes). other words, the proposed hashing-based based coding method is more effective for compressing larger set of entities comparing to the baseline random coding method.
The proposed method outperforms the baseline method (more results in Table 6). We use NC denote the non-compressed embedding learning method without compression, Rand to denote the random coding method (i.e., ALONE), and Hash to denote the proposed hashing coding method. The numbers presented in the table are classification accuracy.
Table I:
oghn-arxiv Rand
ogbn-mag Rand
oghn-products
Aggregator
NC
Hash
NC
Hash
NC
Rand
Hash
Mean pool
0.6228
0.6045
0.6259
0.3192
0.2989
0.3387
0.7486
0.6327
0.6414
Max pool
0,5884
0.4407
0.6034
0.3083
0,3050
0.3283
0.7294
0.6986
0,7156
In terms of memory usage, the compression method is capable of achieving a considerablely good compression ratio. For example, since the egbn-products dataset has 1.871,031 nodes, it requires 456.79 MB to store the raw embeddings in GPU memory. On the contrary. it only takes the pro- posed method 28.55 MB to store the binary codes in CPU memory, and the corresponding decoder model only costs 9.13 MB of GPU memory. The compression ratio is 43.75 for the the proposed method's less memory efficient setup (i.e., full model) if we only consider GPU memory usage. For the total memory usage, the compression ratio is 11.74 for the same setup. The complete memory cost breakdowns for each dataset/method are shown Appendix [B.3] We also repeat this set of experiments with other GraphSAGE aggregation function, other GNN architectures, and link pre- diction task. These additional results are presented in Table I0 and Table [1 with the experimental procedure described in paragraphs accompanying these two tables.
CONCLUSION
In this work, we proposed hashing-based coding scheme which generates compositional codes for compactly representing nodes in graph datasets. The proposed coding scheme outperforms the prior embedding compressing method which uses random coding scheme in almost all experiments. On top of that, the performance degradation coming from the lossy compression is minimal as demonstrated in our experiments. Because the proposed embedding compressing method drastically reduces the memory cost associated with embedding learning, it is possible to jointly train unique embeddings for all the nodes with GNN models on industrial scale graph datasets.
Potential Impact and Future Directions: Aside from GNNs, the proposed methods can also be combined with other kinds of models on tasks that require learning embeddings for a large set of entities. For example, it is common to have categorical features/variables with high cardinalities in transaction data, and embeddings are usually used to represent these categorical features (Du et al.) 2019 Yeh al. 2020a b). Therefore, the proposed method is well suited for building deep learning models for transaction data. Determining the most effective auxiliary information for generating the binary codes should be an interesting direction for transaction data-based fintech applications. The click-through rate prediction problem (Deng et al. 2021) is another interesting direction to ex- plore with our proposed lightweight embedding compression method as click-through rate datasets also contain categorical features with high cardinalities. As result, the proposed embedding com- pressing method could potentially address the scalability problems associated with high cardinalities categorical features in many real world applied machine learning problems. In addition to applying the method to different models/applications, it is also interesting to explore other types of auxiliary information from graphs (e.g., higher-orde order adjacency matrices) for the encoding stage because the codes generated from richer auxiliary information may provide more information for better embed- ding compression.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest, Robert Endre Tarjan, et al. Time bounds for selection. J. Comput. Syst. Sci., 7(4):448-461, 1973.
J Lawrence Carter and Mark N Wegman, Universal classes of hash functions. Journal of computer and system sciences, 18(2):133-154 1979.
Moses S Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pp. 380-388, 2002.
Alexis Conneau, Guillaume Lample, Mare' Aurelio Ranzato, Ludovic Denoyer, and Hervé Jégou. 2017a.
Word translation without parallel data. arXiv preprint arXiv:17100040887, 2017a
Alexis Conneau, Guillaume Lample, Marc' Aurelio Ranzato, Ludovic Denoyer, and Hervé Jégou.
Link for downloading word similarity tasks, 2017b. https://dl. www.ffaaiubifffiic..c.
Com
tar. gz
Wei Deng, Junwei Pan, Tian Zhou, Deguang Kong, Aaron Flores, and Guang Lin. Deeplight: Deep lightweight feature interactions for accelerating ctr predictions in ad serving. In Proceedings of the 14th ACM international conference on Web search and data mining, pp. 922-930, 2021.
Yuxiao Dong, Nitesh V Chawla, and Ananthram Swami. metapath2vec: Scalable representation learning for heterogeneous networks. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 135-144, 2017a
Yuxiao Dong, Nitesh V Chawla, and Ananthram Swami. Link for downloading files associated with metapath2vee, 2017b. https::/ericcoogyyx wwthyyww..i.t....... http://hhhh..ot/ettaaaaa/////e/e
html
Min Du, Robert Christensen, Wei Zhang, and Feifei Li. Peard: personalized restaurants recommen- dation from card payment transaction records. The World Wide Web Conference, pp. 2687- 2019.
Chi Thang Duong, Thanh Dat Hoang, Ha The Hien Dang, Quoe Viet Hung Nguyen, and Karl Aberer. On node features for graph neural networks. arXiv preprint arXiv: 088795, 2019.
Manaal Faruqui and Chris Dyer. Community evaluation and exchange of word vectors at wordvec- tors.org. In Proceedings of 52nd Annual Meeting of the Association for Computational Linguis- fies: System Demonstrations, pp. 19-24, 2014.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with PyTorrch Geometric. arXiv preprint arXiv: 2019.
William I. Hamilton, Rex Ying. and Jure Leskovec. Inductive representation learning on large graphs. arXiv preprint wwXiv:1706.022111 2017.
Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. Neural col- laborative filtering. In Proceedings of the 26th international conference world wide web, pp- 173-182, 2017.
Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. Lightgen: Simplifying and powering graph convolution network for recommendation. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, pp. 639-648, 2020.
Weihua Hu, Matthias Fey, Marinka Zimik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint wwX.x:20055006323 2020.
Ben Johnson, William L Hamilton, and Can Güney Aksakalli. pytorch-graphsage. github. www/bk///////. http://bi//otttrcc-grapapssseeee
https://
2018.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1609.02077 2016.
10

---

Under review as a conference paper at ICLR 2021
Guillaume Lample, Alexis Conneau, Ludovic Denoyer, and Marc' Aurelio Ranzato. Unsupervised machine translation using monolingual corpora only, arXiv preprint arXiv:1711.00443, 2017.
Stuart Lloyd. Least squares quantization in pem. IEEE transactions information theory, 28(2): 129-137, 1982.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint arXiv:171..0100, 2017.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed represen- tations of words and phrases and their compositionality. In Advances in neural information pro- cessing systems, pp- 3111-31111111 19, 2013a.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Google code archive for word2vee, 2013b. https://codes google com/ /rchhvvee///wwoo/veecc///
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32: 8026-8037, 2019.
Jeffrey Pennington, Richard Socher, and Christopher 1) Manning. Link for downloading Gl.Ve.6B 2014a. https: / //nlp:://np... stan
zip
Jeffrey Pennington, Richard Socher, and Christopher D) Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pp. 1532-1543, 2014b.
Raphael Shu and Hideki Nakayama. Compressing word embeddings via deep compositional code learning. arXiv preprint 17X1v.1711.01668 2017.
Jun Suzuki and Masaaki Nagata. Learning compact neural word embeddings by parameter space sharing. In Proceedings of the Twenty-Fifth International Joint Conference Artificial Intelli- gence, pp. 2056,2052,2 2016.
Dan Svenstrup, Jonas Meinertz Hansen, and Ole Winther. Hash embeddings for efficient word representations. arXiv preprint arXiv:1709.0393: 2017.
Sho Takase and Sosuke Kobayashi. All word embeddings from one embedding. arXiv preprint arXiv:2004.12073, 2020.
Sho Takase and Naoaki Okazaki. Positional encoding to control output sequence length. arXiv preprint arXiv:1904.07411 2019.
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Ametminer: extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 990 998, 2008
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is you need. Advances in neural information processing systems, pp. 5998-6008, 2017.
Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. Neural graph collaborative filtering. In Proceedings of the 42nd international ACM SIGIR conference Reseurch and development in Information Retrieval, pp. 165-174, 2019.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning. pp- 6861-6871. PMLR, 2019.
Keyulu Xu, Weihua Hu. Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural 2018.
networks? arXiv preprint

---

Under review as a conference paper at ICLR 2021
Chin-Chia Michael Yeh, Dhruv Gelda, Zhongfang Zhuang, Yan Zheng, Liang Gou, and Wei Zhang. Towards a flexible embedding learning framework. In 2020 International Conference on Data Mining Workshops (ICDMW), pp. 605-612. IEEE, 2020a.
Chin-Chia Michael Yeh, Zhongfang Zhuang, Yan Zheng, Liang Wang, Junpeng Wang, and Wei Zhang. Merchant category identification using credit card transactions. In 2020 IEEE Interna- tional Conference on Big Data (Big Data). pp. 1736-1744 IEEE, 2020b.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 974 983, 2018.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applica- tions. Al Open, 1:57-81, 2020.
A ADDITIONAL EXPERIMENT DETAILS
Here, we provide more details regarding the experiments we presented in the main text.
A.1 COMPARISON OF DIFFERENT THRESHOLDS FOR HASHING-BASED CODING
We have comparing the difference between different choice of thresholds when binarizing the real values into binary codes Section 3.J with an experiment. Here, we will describe the details of the experiment. The experiment dataset consists of the first 200,000 pre-trained met apat 2vec or weteaatth2eec-+++ node embeddings downloaded from the supplemental web page constructed by Dong et al. (2017a The dimension of the pre-trained embeddings is 128. Because we repeat the experiments 100 times, we generate 100 seeds to make sure both method use the same basis to perform random projection as the only difference between the two tested methods should be the threshold. In each experimental trial, we first use the seed to generated a random matrix V E R 1288*M Next, project the embedding matrix (i.e., the 200,000 128 embedding matrix) using V; then, we binarize the result matrix using either zero or the median of each row. With the binary codes prepared, count the number of coalitions for each method. Once all 100 trials done, the result is presented with histogram as shown in Figure
A.2 WORD ANALOGY AND SIMILARITY TASKS
The praited CloVe word embeddings are downloaded from the web page created by Pennington
ett al. (2014b ab. The word embeddings are trained using Wikipedia 2014 and Gigaword 5 dataset (total of 6B tokens).
Word analogy: We downloaded list of word analogy pairs from the repository of word2vec (Mikolov et al., 2013a The word analogy pairs are categorized into 14 categories, and the 14 categories are shown below. We also provide an example pair for each category.
capiaa-commmon-couniies;;; o htt.://coooocccttttttteteeeeeeer
Bangkok: Thailan
capital-world: Ankara: :A
currency: oaaa:yyaaaaaaeeeeacaaaaaaaao.aaa
city-in-state: httpa:ach...........ooooooooooo.
s
cheerfully impossible
grams-presen-pprticplee...
gramm--pas--ennsse
grama-plural::
12

---

Under review as a conference paper at ICLR 2021
gram9-plural play: :tt.:::::aaaiiaaaaaaaaaaa... vanishes
The experiment is performed as described by Mikolov et al. (2013a). Given a word embedding matrix X and word analogy pair (e.g., Athens Greece: Bangkok Bokkkkk Thailand),
first
prepare a query vector Q with [GGrece) query X with cosine similarity. The answer is only considered correct if the most similar word is Thailan land. The performance is measured in accuracy. We compute the accuracy for each category; then, report the average the 14 accuracy values the performance for word analogy.
X [Athens + X [BBaggkok). Next, we use Q to
Word similarity: Thirteen word similarity datasets are downloaded from the repository of MUSE (Conneau et al., 2017a b Lample al. 2017). Each dataset consists of list of paired words and their ground truth similarity scores. We list the 13 datasets below with two example pairs from each dataset.
MC-30: car stw.attmmmiieee.......eeeeeeeeee
MEN-TR-3k ott.::/:ew....................a.
RG-65: oeh.ahahheen..eo.........coeeee.
SIMLEX-999: 2gggahaee......iiaa......aaaaaaa
VERB-143; XBBB3Aasheeeepppceeeeeeeaaaaaaae
WS-353-REL: ors.55/..ooooorrraeeeaeeeeeaaee.
WS-353-SIM: htt.::/0w...irroo.......aa.aana.
YP-130: 00 http://mi....a.i....i.aaaaaaaaaa
The experiment is performed as described by Faruqui & Dyer (2014). First, the cosine similarity between word embeddings for each pair of words dataset is computed. Then, the order based on the cosine similarity is compared with the order based on the ground truth similarity scores. The comparison of orders are measured with Spearman's rho. The result Spearman's 's rhos from the 13 datasets are averaged and reported.
A.3 NODE CLUSTERING TASK
The pre-trained met metapah22ves embeddings, the pre-trained met met apat embeddings, the association between nodes (i.c., researchers), and the cluster labels (i.e., research area) are down- loaded from the web page created by Dong et al. 72 7 b). The node embeddings are trained with AMiner dataset (Tang et al. 2008). There are total of 246.678 labeled researchers from the down- loaded dataset. Each researcher is assigned with one of the 8 research areas listed below.
Computing Systems
Theoretical Computer Science
Computer Networks and Wireless Communication
Computer Graphics
Human Computer Interaction
Computational Linguistics
Computer Vision and Pattern Recognition
Databases and Information Systems
We use k k-means clustering algorithm (Lloyd) 1982) to cluster the embedding associated with each researcher; then, measure the clustering performance with normalized mutual information.
A.4
SETTING FOR SECTION 5.1
We use the following hyper--arameee settings for the decoders. For GloVe, we use / - 3, de dm = 512, de = 300, c = 2, and m = 128. For me hww.apattheeeeeetaaaaaaaaeee use [ 3, de d,m 512, de = 128, same across different coding schemes tested on the same dataset. We use different d, for different embeddings because the dimensionality of different pre-trained embeddings is different. The default
we 2, and m = 128. Note, the decoder design is the
13

---

Under review as a conference paper at ICLR 2021
nyper-parameter settings for AdamW (Loshchilov & Hutter, 2017) in PyTorch Paaskke al. 2019) are: learning rate = 0.001, 31 = 0.9. 32 = 0.999, and weight decay = 0.01. We train models for 1,024 epochs with batch size of 512.
A.5 NODE CLASSIFICATION TASK
In this section, provide more details regarding how we process the graph datasets used in Sec- tion 5.2 Given graph dataset, we first discarded the node features come with the dataset. Next, for all the directed graphs, convert them to undirected graphs. Although ogbn-mag dataset is a heterogeneous graph, we only use the citing relation between paper nodes the labels are as- sociated with paper nodes. Because we only use the structure of the graph (i.e., node features are discarded), we removed validation/test nodes that is not also presented in training data. In other words, the node classification experiment performed in semi-supervised learning settings where the validation/test nodes presented in the training data without their associated labels. After aforementioned process, the statistics associated with the datasets are presented in Table
Table The number of nodes in the training/validaationness set of each dataset.
training
validate
test
total
obgn-arxiv obgn-mag
90941
29431
48018
168390
629571
64481
41706
735758
obgn-products
195639
38483
1636909
1871031
A.6 HYPER-PARAMEN PARAMETER SETTING FOR SECTION 5.2
We use the following hyper-parameter settings for the decoders: / - 3, d. = dm = 512, d. = 64,
256, and m 16. We evaluated both light and full methods for the decoder, and reported the evaluation accuracy from the method with the best validation accuracy. We use the following hyper- parameter setting for the Graph model: number of layers 2, number of neurons 128, activation function = ReLU, and number of neighbors = 15. We use the following hyper-paramette settings for the AdamN optimizer (Loshchilov & Hutter, 2017]: learning rate 0.01, / 0.9, B2 = 0.999, and weight decay- = Ó. These settings are the default hyper-paranee settings from either the GraphSAGE implementation (Johnson et al. 2018 8) or PyTorch (Paszke et al. 2019). We train all models for 10 epochs with batch size of 256, and report the evaluation accuracy from the epoch with the best validation accuracy.
B ADDITIONAL EXPERIMENT RESULTS
Here, we provide additional experimental results which supplement Section
B. COMPARISON OF DIFFERENT THRESHOLDS FOR HASHING-BASED CODING
When we introduce our Washing-based coding method in Section 3.1 talk about how the choice of threshold could affect the number of collisions. Specifically, we compare our choice (which uses the median as the threshold) with the more commonly seen threshold of zero. We demonstrate that the median threshold has less collisions comparing to the zero threshold with the experiment presented in Figure 3 Here, we perform additional experiments use metapath2ves node embed- dings (Dong et al.] 2017a). The results for met metapat h2pcc++
summarized in Figure 5 and the conclusion is the same: using the median as the threshold for binarization has lower number of collisions comparing the zero threshold.
We also perform experiments on GloVe word embeddings. We use the 300 dimension variant downloaded from the web page created by Pennington et al. (2014b a). We perform the experiment under four different bit settings: 20 bits, 24 bits, 28 bits, and 32 bits, and the conclusion agrees with finding presented in Figure 3 and Figure
14

---

Under review as a conference paper at ICLR 2021
24 bits
32 bits
hashing-zero zero hashing-meddan
hashing-zee zero hashing- mngdinnininnnn
number collistons
102159
number of collisions
24535
Figure 5: The experiment is performed metapath2vect+ for 100 times under two differ- ent bit length settings: 24 bits and bits. The distribution the 100 outcomes (i.e., number of collisions) for each method is shown in the figure. The number of collisions is lower for median threshold comparing to zero threshold.
20 bits
bits
hashing-2ero hashing-medlan
hashing-rero bashing-median
number of cullisions
54946
sumber of collisions 32 bits
1040L
28 bits
bashing-serr hashing median
hashing-eero hashing median
mumber of collistons
1845
namber collistons
401
Figure 6: The experiment is performed for 100 times in four different scenarios with GloVe embedding: 1) 20 bit code, 2) 24 bit code, 3) 28 code, 4) 32 bit code. The distribution of 100 outcomes (i.e., number of collisions) for each method is shown in the figure. The number of collisions lower for median threshold comparing to zero threshold.
B.2 PRE-TRAINED EMBEDDING RECONSTRUCTION
To understand the relationship between the number of compressed entities and the compression ratio, we construct Table 3 to demonstrate how the compression ratio changes as the number of compressed entities is increased.
Table 3: Compression ratios for different numbers of compressed entities. The compression ratios of metaaatthha h2vec+ are omitted as the compression ratios are the same as metapatle h2ee..
# of Entities
5000
10000
25000
50000
100000
200000
GLoVe
2.65
5.11
11.60
20.09
31.69
44.55
netapsth2vec
1.34
2.57
5.73
9.72
14.91
20.34
Aside from the results presented in Figure proposed hashing-bart based coding method with the baseline random coding method under different settings of and m while varying the number of compressed entities. The results are presented in Table 4 The proposed hashing-based coding method almost always performs better than the baseline random coding method. The performance gap between the methods increases as the number of entity compressed by the compression method increases. Because the settings of e and m also controls the size of the decoder model, and m affect the compression ratio. T shows the compression ratio under different settings of c and m. Generally, settings with lower compression ratio have better performance as the potential information loss less. In the experiments, the bit size of the binary code is fixed to 128 bits. In other words, both (c 256, m = 16) and {c 2, m = 128} uses 128 bit binary codes. The e and m change the compression ratio by changing 16} setting, there will be 4,096 vectors total
perform additional experiments to compare the
the decoder size. When using the {c 256, stored in 16 codebooks. When using the {c = 2, m = 128} setting, there will be 256 vectors total stored in 2 codebooks. Because the (c 256, lower compression ratio), it usually is the setting that outperformed the other in terms of embedding quality. To select suitable setting for (c, m., we suggest the user compute the potential memory
16) setting has larger model (i.e.,
15

---

Under review as a conference paper at ICLR 2021
usage and compression ratio for different settings of {c, m), then select the with the lowest compression ratio while still meets the memory requirement.
Table 4: Experiment results on pre-trained embeddings with different settings of and We use random to denote the random coding method (i.e., ALONE), and hashing to denote the proposed hashing coding method.
of Entities
Embedding/Tase
m
Coding Method
5000
10000
50000
200000
random
0.5783
0.4443
0.0736
0.0048
2
128
hashing
0.5798
0.4898
0.3638
0.2878
random
0,5933
0,4603
0.0952
0.0066
4
64
hashing
0.6012
0.4873
0.3204
0.2943
GloVe (analogy)
random
0.6209
0.5359
0.1508
0.0134
16
32
hashing
0.6247
0.5001
0.3596
0.2596
random
0.6708
0.6534
0,4263
0,0837
16
hashing
0.6683
0.6693
0.4710
0,3138
random
0.5435
0.5172
0.3711
0.1056
2
128
hashing
0.5442
0.5392
0.5260
0,4110
random
0.5799
0.5484
0,4298
0.2218
4
64
hashing
0.5795
0.5232
0.4837
0.4098
GloVe (similarity)
random
0.5495
0,5814
0.4502
0.1620
16
32
hashing
0.5503
0.5302
0,4465
0.4301
random
0.5743
0.5671
0.5246
0,3613
256
16
hashing
0.5744
0.5744
0.5309
0.4346
random
0.7730
0.7636
0.7228
0.6026
2
128
hashing (pre-trained)
0.7731
0.7650
0.7562
0.7419
hashing (graph)
0.7787
0.7676
0.7468
0.7167
random
0.7720
0.7690
0.7271
0.6273
4
64
hashing (pre-trained)
0.7804
0.7697
0.7511
0.7509
hashing (graph)
0.7769
0.7719
0.7526
0.7167
metapath2vec
random
0.7763
0.7717
0.7366
0.6686
16
32
hashing (pre-trained)
0.7757
0.7668
0.7528
0.7403
hashing (graph)
0.7759
0.7786
0.7638
0.7418
random
0.7790
0.7814
0.7623
0.7263
256
16
hashing (pre-trained)
0.7793
0.7767
0.7735
0.7575
hashing (graph)
0.7806
0.7796
0.7601
0.7489
random
0.7549
0.7585
0.7163
0.5799
2
128
hashing (pre-trained)
0.7590
0.7567
0.7361
0.7264
hashing (graph)
0.7536
0.7497
0.7335
0.7013
random
0.7620
0,7480
0.7260
0.6126
4
64
hashing (pre-trained)
0.7614
0.7464
0.7380
0.7119
hashing (graph)
0.7593
0.7528
0.7396
0.7025
motapath2vect*
random
0.7549
0.7499
0.715I
0.6441
16
32
hashing (pre-trained)
0.7648
0.7516
0.7463
0.7312
hashing (graph)
0.7610
0.7561
0.7424
0,7270
random
0.7628
0.7640
0.7461
0.7055
256
16
hashing (pre-trained)
0.7601
0.7664
0.7495
0.7432
hashing (graph)
0.7656
0.7635
0.7471
0.7292
B.3 NODE CLASSIFICATION TASK
In this section, we provide additional results for different hyper-parane paramearreeter settings (i.e., different and m). The results are presented in Table 6 The proposed method outperforms the baseline random coding method in tested cases. The effect of e and m is similar to the conclusion draw from Table 4 and please refer Appendix B.2 for suggestion
how to select suitable setting of and m for different situations. We also provide the memory cost breakdowns for different datasets. We need to compute the memory breakdown for different datasets because the number of nodes in each dataset is different. The breakdowns are shown in Table 7 Table g, and Table | The unit for memory is megabyte (MB), and the column label "ratio" stands for "compression ratio".
16

---

Under review as a conference paper at ICLR 2021
Table 5: Compression ratios for different numbers of compressed entities with different settings of and m. The compression ratios of metapath2vec* are omitted as the compression ratios are the same as metapath2vec.
of Entities
Embedding
m
5000
10000
50000
200000
128
2,65
5.11
20.09
44.55
5.11
20.09
44.55
GloVe
16
32
2.15
4.18
17.09
40.60
256
16
0.59
1.18
5.53
18.11
128
1.34
2.57
9.72
20.34
1.34
2.57
9.72
20.34
metapath2vec
16
32
1.05
2.03
8.10
18.42
256
16
0.26
0.52
2.44
7.94
Table The proposed hashing-baan based coding outperforms the baseline random coding under differ- ent settings of and m. The compeesseeee is the embedding learning method without compres- sion. We use random to denote the random coding method (i.e., ALONE), and hashing to denote proposed hashing coding method.
Coding
Aggregator
c
TTL
Method
ogbn-arxiv
obgn-mag
obgn-products
non-compressed
0.6228
0.3192
0.7486
random
0,2200
0.1402
0.5669
2
128
hashing
0.4177
0.3366
0.6678
Mcan pool
random
0.2337
0.0312
0.5694
hashing
0.4233
0.3392
0.6739
random
0.4375
0,2519
0.6499
16
32
hashing
0.5130
0.3292
0.6960
random
0.6045
0.2989
0.6327
256
16
hashing
0.6259
0.3387
0.6414
non-compressed
0.5884
0.3083
0.7294
random
0.3802
0,2188
0.5386
2
128
hashing
0.4609
0.3138
0.6305
Max pool
random
0.3762
0.2299
0.5594
4
64
hashing
0.4906
0.3271
0.6381
random
0.5427
0.2544
0.6047
16
32
hashing
0.5845
0.3290
0.6393
random
0.4407
0.3050
0.6986
256
16
hashing
0.6034
0.3283
0.7156
In additional to the more standard mean and max aggregator, we also repeat the experiments with GraphSage model on non-standard attention aggregator. For this set of experiments, we use the following hyper-parameter settings for the decoders: 1 3, de = dm = 512, and de 64. We use validation data to tune the settings of and We use the following hyper- parameter setting for the GraphSAGE model: number of layers = 2, number of neurons = 128, activation function ReLU, and number of neighbors 15. We the following hyper-parameter settings for the Adamw optimizer (Loshchilov & Hutter 2017): learning rate 0.01, 3, = 0.9,
Table 7: The memory cost (MB) for models on ogbn-arxiv dataset.
CPU
GPU
CPU+GPU
Method
Binary Code
Decoder or Embedding
Decoder
Total
GNN
Total
Ratio
Total
Ratio
Raw
0.00
0.00
0.00
41.11
1.34
42.45
1.00
42.45
1.00
High-Light
2.57
8.00
10.57
1.13
1.34
2.46
17.22
13.03
3.26
Hash-Heavy
2.57
0.00
2.57
9.13
1.34
10.46
4.06
13.03
3.26
17

---

Under review as a conference paper at ICLR 2021
Table 8: The memory cost (MB) for models ogbn-mag dataset.
CPU
GPU
CPU+GPU
Method
Binary Code
Decoder or Embedding
Decoder
Total
GNN
Total
Ratio
Total
Ratio
Raw
0.00
0.00
0.00
179.63
1.64
181.27
1,00
181.27
1.00
Hash-Light Light
11.23
8.00
19.23
1.13
1.64
2.77
65,49
21.99
8.24
Hash-Heavy
11.23
0.00
11.23
9.13
1.64
10.77
16.83
21.99
8.24
Table 9: The memory cost (MB) for models ogbn-products dataset.
CPU
GPU
CPU+GPU
Method
Binary Code
Decoder or Embedding
Decoder
Total
GNN
Total
Ratio
Total
Ratio
Raw
0.00
0.00
0.00
456.79
1.35
458. 14
1.00
458.14
1.00
Hash-Light
28.55
8.00
36.55
1.13
1.35
2.47
185.34
39.02
11.74
Hash-Heavy
28.55
0.00
28.55
9.13
1.35
10.47
43.75
39.02
11.74
82 = 0.999, and weight decay 0. We train all models for 30 epochs with batch size of 256, and report the evaluation accuracy from the epoch with the best validation accuracy. The experiment result is presented in Table 10 The proposed compression method outperforms the ALONE method.
B.4 MORE GNNs AND LINK PREDICTION TASK
We also compare the proposed method with ALONE with other GNNs like Graph Convolutional Network (i.e., GCN) (Kipl & Welling 2016). Simplifying Graph Convolutional Network (i.e., SGC) (Wu et al.) (2019). and Graph I Isomorphi Network (i.e., GIN) et 2018). Although the learning process of these GNNs cannot benefit from the reduced memory provided by both ALONE and the proposed method this set of experi- ment still provides an additional test bed for comparing the two methods similar to the experiment presented in Section [.1 We use the following syper-parameter settings for the decoders: / = 3, de dm = 512, and de = 64. We use validation data to tune the settings of and m. For GCN, we
layered structure with hidden dimension of 128, self-loop, and skip connec- tion. For SGC and GIN, we also use a two layered structure with hidden dimension 128 with the other hyper parameter set to the default values in the PyG library (Fey & Lenssen 2019). We use the following hyper-parameter settings for the AdamW optimizer (Loshchilov & Hutter (017)): learning rate 0.001, 31 0.9, 82 0.999, and weight decay 0.00001. We train the network for 512 epochs.
In additional the node classification datasets, we also perform experiments on link prediction datasets (i.c., ogbl-collab and ogbl-ddi) from Open Graph Benchmark (Hu et al. 2020). The experi- ment result summarized in Table and it shows the proposed method almost always outperform- ing the ALONE method.
'GCN cannot benefit from both ALONE and the proposed method because all embeddings need to be decoded during the learning process at all time unlike the GraphSAGE model which only requires decoding embeddings associated with nodes the current batch.
18

---

Under review as a conference paper at ICLR 2021
Table 10: The proposed hashing-based coding outperforms the baseline random coding with GraphSage using non- non-standard attention aggregator. The non-compressed the embedding learn- ing method without compression. We use random to denote the random coding method (i.e., ALONE), and hashing to denote the proposed hashing coding method.
Coding Method
ogbn-arxiv
obgn-mag
obgn- pegn-products
raw random hashing
0.6063
0.3097
0.7918
0.5008
0.2691
0.5981
0.5662
0.3197
0.6758
Table 11: The proposed hashing-basce coding almost always outperforms the baseline random cod- ing with different GNNs for both node classification and link prediction. The non-compressed is the embedding learning method without compression. We use random to denote the random coding method (i.e., ALONE), and hashing denote the proposed hashing coding method.
performance
GraphSage (mean)
task
dataset
measure
NC
Rand
Hash
ogbn-arxiv
accuracy
0.6228
0.6045
0.6259
node
ogbn-mag
accuracy
0.3192
0.2989
0.3387
classification
ogbn-product
accuracy
0.7486
0.6327
0.6414
link
ogbl-collah
hits
0.2740
0.1966
0.1956
prediction
ogbl-ddi
hits 20
0.3277
0.3043
0.3429
performance
GCN
lask
dataset
measure
NC
Rand
Hash
ogbn-arxiv
accuracy
0.5251
0.4957
0.5437
node
ogbn-mag
accuracy
0.1815
0.1146
0.3466
classification
ggbn-products
accuracy
0.4719
0.3594
0.4914
link
ogbl-collah
hi
0.2316
0.1647
0.1898
prediction
ogbl-ddi
hits@20
0.3697
0.3399
0.3319
performance
SGC
task
dataset
mcasure
NC
Rand
Hash
ogbn-arxiv
accuracy
0.6690
0,5491
0.5809
node
classification
ogbn-mag
accuracy
0.3523
0.1839
0.3657
ogbu-products
accuracy
0.7686
0.3767
0.4966
link
ogbl-collah ogbl-ddi
hits
(l.5599
0.4790
0.5116
prediction
hits@20
0.4841
0.5575
0.5941
performance
GIN
task
dataset
measure
NC
Rand
Hash
ogbn-arxiv
accuracy
0.5546
0.3736
0.5263
node
classification
ogbu-mag
accuracy
0.2728
0.2011
0.3414
ogbn-products
accuracy
0.6423
0.4396
0.5706
link
ogbl-collab ogbl-ddi
hits@ 50
0.2614
0.2086
0.2475
prediction
hits
0.3216
0.3536
0.3876
19


Reviews:
[{"review_id": "cpdPjBcTC1U", "reviewer": "Reviewer_J5SK", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Strength\n- The paper is well-written and easy to follow.\n- Proposed approach can directly hash the adjacency matrix (no need to have the learned embeddings).\n\nWeakness\n- 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.\n- 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. \n\nSuggestion:\nIn 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_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.", "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.", "strength_and_weaknesses": "", "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": "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": "Qp2DqZi27yB", "reviewer": "Reviewer_hQPL", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "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].\n\n[1] Learning to Hash with Graph Neural Networks for Recommender Systems. Tan et. al., the Web Conf 2020\n\n[2] Differentiable Product Quantization for End-to-End Embedding Compression. Chen et. al. ICML 2020\n\n[3] GHashing: Semantic Graph Hashing for Approximate Similarity Search in Graph Databases. , Qin et. al., KDD 2020\n\nW2. 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.\n\nW3. 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.\n \n[4] DGL-KE: training knowledge graph embeddings at scale, Zheng et. al., SIGIR 2020", "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. ", "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.", "strength_and_weaknesses": "", "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": "AFGrsIo3Ac7", "reviewer": "Reviewer_u7vW", "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": "Strength\n1. The proposed method significantly reduces the memory cost when training the GNN models by adopting the random projection hashing approach.\n2. Experiments on embedding reconstruction and node classification tasks demonstrate the proposed method outperforms the prior embedding compression method based on a random coding scheme.\n3. 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. \n\nWeakness\n1. 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]). \n2. 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?\n3. 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?\n4. Finally, it would be great if the authors could discuss about how to select the code cardinality $c$ and the code length $m$.\n\n\n[1] Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2018). How powerful are graph neural networks?. arXiv preprint arXiv:1810.00826.\n\n[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.\n\n[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).\n\n[4] You, J., Gomes-Selman, J., Ying, R., & Leskovec, J. (2021). Identity-aware graph neural networks. arXiv preprint arXiv:2101.10320.\n\n[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_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.\n\n", "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?", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "4Xg3L93YBHf", "reviewer": "Reviewer_WEHB", "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": "## Positive aspects:\n\n- The proposed method appears simple and effective. It relies on the well-established technique of locally-sensitive hashing and compositional coding. \n- The memory efficiency of the method makes it broadly applicable to large-scale graphs.\n- The LSH encoding is constructed from prior knowledge (like vertex connectivity) or pre-trained embeddings, therefore it allows exploiting already available information.\n- The method can be trained end-to-end together with all subsequent layers.\n- 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.\n\n## Negative aspects:\n\nThe only negative aspect I see concerns unclear parts that I detail right below.\n\n1. 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.\n2. I could not find specified whether or not the three methods (ALONE, \"learn\" and the proposed \"full\") are set with the same hyperparameters. \n3. 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.\n4. 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?\n5. 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?\n", "summary_of_the_paper": "The paper presents a vertex embedding method with good scalability to large graphs. \nThe 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.", "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.\nAlthough the methodological contribution is little, the method appears simple and effective. \nHowever, 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.\n", "strength_and_weaknesses": "", "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": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

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