Knowledge Graph Embeddings (KGEs) are dense representations of entities and relations of a knowledge graph (KG) in a continuous vector space. In this paper, we present a preliminary analysis showing that KGEs can be substantially compressed by using only binary instead of continuous features, replacing costly floating point storage by a more space-efficient bitwise storage, while retaining the representational power.
Knowledge Graph Embeddings (KGEs) are dense representations of entities and relations in knowledge graphs, where each entity and relation is represented by a vector in a continuous vector space. They are used for various in knowledge graph tasks, such as link prediction, entity classification, for helping in knowledge-graph related tasks such as entity linking and disambiguation, but also as knowledge representations in other downstream tasks, such as recommender systems. [1,2] While the scalability of KGE methods has been identified as a challenge [3,4], most papers looking into scalability take the angle of scaling up the training process, i.e., being able to learn a representation for a (large) knowledge graph with reasonable time and memory usage. What has been overlooked so far is the size of the resulting embedding, which is also an important consideration for downstream tasks. Using KGEs in downstream applications requires loading and processing those within the application, which may be hindered by the sheer size of the embedding, especially when computing resources are limited.
To illustrate the issue of KGE size, we use the well-known knowledge graph DBpedia [5], whose latest release contain 7.62 million entities. 1 Both the most common implementation of word2vec [6] in the gensim library [7], which is used by RDF2vec [8], as well as the PyTorch library [9], which underlies embedding frameworks like DGL-KE [4] and PyKEEN [10], use 32 bit floating point values for representing embeddings by default. 2,3 Embedding DBpedia with 200 dimensions would thus yield a 6GB large KGE model. 4In this paper, we propose to use binary instead of continuous embeddings, i.e., embeddings that only use the values 0 and 1 for each dimension. By doing so, the size of embeddings can be reduced by a factor of 32 (using only 1 bit per entity and dimension instead of 32). In the example above, we could thus store a 200 dimensional binary embedding using less than 200MB.
The proposed approach is not limited to a single KGE method. Instead, we propose to binarize an already trained KGE. In experiments with the DLCC node classification benchmark, eleven different embedding methods, and different binarization methods, we show that the loss in accuracy of using binary embeddings is rather small, but allows for a drastic reduction of storage size. Especially for embeddings that are already computed for popular large-scale knowledge graphs [11], binarization can reduce the data volume and downstream processing load.
In this paper, we utilize two approaches for binarizing knowledge graph embeddings: a simple dimension-based baseline, and an autoencoder-based approach adapted from [12].
Given that π£ππ(π) is the embedding vector of an entity π, we first compute the average vector π£ππ as
where π£ππ(π) π is the i-th element of π£ππ(π). With that average vector, we can obtain a binary vector ππ£ππ from π£ππ(π) as
In other words: every floating point value lower than the average for that dimension is represented by a 0, all others are represented by a 1.
Autoencoders are, in their simplest form, three-layer neural networks trained for dimensionality reduction [13]. Between an input and an output layer, they have a (smaller) code layer. They are trained by presenting instances of a dataset both as input and output (i.e., the input and output being identical), and thereby learning to minimize the reconstruction error. [12] propose to use a heavyside step function as an activation function π πΈ βΆ R β {0, 1}, which only outputs the values 0 and 1. Specifically, they use of the Heaviside step function β, defined as
With that, the output of πΈ(π₯) is a binary vector. For further optimizing computations, they propose to align the dimensionality of the code layer to CPU register widths, such as 64, 128, and 256 bits. In this paper, we use their implementation 5 for binarizing knowledge graph embeddings.
In order to evaluate the quality of binarized embeddings, we use the DBpedia portion of DLCC [14]. For our experiments, we use the DBpedia embeddings also used in the paper [1], which are available online 6 . As embedding methods, we use four flavors of RDF2Vec [15,16] and two flavors (Norms L1 and L2) of TransE [17] embeddings are exploited, as well as ComplEx [18], DistMult [19], RESCAL [20], RotatE [21], and TransR [22]. Table 1 shows the average file sizes achieved with the different binarization methods. The standard storage method uses an uncompressed TXT variant (i.e., storing the value "0" or "1" in one byte), which can yield a compression factor up to 14. The .VEC format, which is supported by the autoencoder implementation used in this paper [12], actually stores each eight single embedding values in one byte (i.e., multiple embedding dimensions are stored in one long integer). With this method, a compression factor of almost 50 can be achieved, leading to an embedding originally stored in 1.6 GB now only occupying 33 MB.
DLCC has three sizes of problems for each task; here, we only present the results for largest problem size (5,000 examples per task). The full results are available online 7 ; the results for the smaller groups (500 and 50 examples, resp.) are comparable to those on the largest task group.
Table 2 shows the results on the DLCC entity classification dataset. The average losses in accuracy are not very large, with the the baseline performing better than the smaller autoencoders. This makes us assume that the original embeddings capture the required information for the tasks at hand already at a very coarse level, i.e., it is sufficient to know that a vector value for an entity at a particulary dimension is high or low, but it is not necessary to know how low it actually is. Moreover, we observe the largest losses for ComplEx and DistMult, which are both tensor factorization methods, whereas RDF2vec SG has the smallest loss, compared to the uncompressed variant. Therefore, we conclude that binarization is not equally effective for each model, but that there are differences by model family.
Furthermore, we can observe that the binarization has a smaller impact than the choice of the embedding variant: even the binarized versions of RDF2vec SG OA yield superior results to the original, i.e., non binarized embeddings of most other embedding methods.
In this paper, we have shown two strategies for reducing the size of a KGE model, one simple baseline using dimension-wise binarization, and an approach based on neural autoencoders. A promising preliminary evaluation on the DLCC entity classification benchmark shows that the size of embeddings can be drastically reduced at a comparatively low loss in downstream classification performance.
While the focus of this paper has been on optimizing the storage, we have not yet looked into possible gains in computation time for downstream processing, i.e., at inference time. For example, [12] have proposed processing binary vectors with logical bitwise operators, which could also yield significant performance gains over floating point operations. This is a promising, but yet underexplored area. Moreover, a comparison of binarizing classically trained embeddings with directly trained binary embeddings would be intriguing, especially for cases where no pre-trained embeddings exist.
So far, we have only looked into tasks involving single entities, as defined in the gEval and DLCC benchmarks. The transfer to another popular usage of knowledge graph embeddings, i.e., link prediction and triple scoring, has not yet been investigated. Except for the B-CP approach [23], there are, to the best of our knowledge, no methods for exploiting binary knowledge graph embeddings for link prediction. In particular, since B-CP directly learns the embeddings, there are no studies on binarizing existing embeddings for link prediction.
In summary, the results have shown that binary knowledge graph embeddings can be an appealing alternative to the widely used floating point representations, allowing a drastic reduction of storage space while, at the same time, leading to only marginal loss in downstream performance.