Expeditious Generation of Knowledge Graph Embeddings

Abstract: Knowledge Graph Embedding methods aim at representing entities and relations in a knowledge base as points or vectors in a continuous vector space. Several approaches using embeddings have shown promising results on tasks such as link prediction, entity recommendation, question answering, and triplet classification. However, only a few methods can compute low-dimensional embeddings of very large knowledge bases without needing state-of-the-art computational resources. In this paper, we propose KG2Vec, a simple and fast approach to Knowledge Graph Embedding based on the skip-gram model. Instead of using a predefined scoring function, we learn it relying on Long Short-Term Memories. We show that our embeddings achieve results comparable with the most scalable approaches on knowledge graph completion as well as on a new metric. Yet, KG2Vec can embed large graphs in lesser time by processing more than 250 million triples in less than 7 hours on common hardware.

Recently, the number of public datasets in the Linked Data cloud has significantly grown to almost 10 thousands. At the time of writing, at least four of these datasets contain more than one billion triples each. This huge amount of available data has become a fertile ground for Machine Learning and Data Mining algorithms. Today, applications of machine-learning techniques comprise a broad variety of research areas related to Linked Data, such as Link Discovery, Named Entity Recognition, and Structured Question Answering. The field of Knowledge Graph Embedding (KGE) has emerged in the Machine Learning community during the last five years. The underlying concept of KGE is that in a knowledge base, each entity and relation can be regarded as a vector in a continuous space. The generated vector representations can be used by algorithms employing machine learning, deep learning, or statistical relational learning to accomplish a given task. Several KGE approaches have already shown promising results on tasks such as link prediction, entity recommendation, question answering, and triplet classification BIBREF0 , BIBREF1 , BIBREF2 , BIBREF3 . Moreover, Distributional Semantics techniques (e.g., Word2Vec or Doc2Vec) are relatively new in the Semantic Web community. The RDF2Vec approaches BIBREF4 , BIBREF5 are examples of pioneering research and to date, they represent the only option for learning embeddings on a large knowledge graph without the need for state-of-the-art hardware. To this end, we devise the KG2Vec approach, which comprises skip-gram techniques for creating embeddings on large knowledge graphs in a feasible time but still maintaining the quality of state-of-the-art embeddings. Our evaluation shows that KG2Vec achieves a vector quality comparable to the most scalable approaches and can process more than 250 million triples in less than 7 hours on a machine with suboptimal performances.
An early effort to automatically generate features from structured knowledge was proposed in BIBREF6 . RESCAL BIBREF7 is a relational-learning algorithm based on Tensor Factorization using Alternating Least-Squares which has showed to scale to large RDF datasets such as YAGO BIBREF8 and reach good results in the tasks of link prediction, entity resolution, or collective classification BIBREF9 . Manifold approaches which rely on translations have been implemented so far BIBREF10 , BIBREF11 , BIBREF12 , BIBREF2 , BIBREF13 , BIBREF0 . TransE is the first method where relationships are interpreted as translations operating on the low-dimensional embeddings of the entities BIBREF10 . On the other hand, TransH models a relation as a hyperplane together with a translation operation on it BIBREF11 . TransA explores embedding methods for entities and relations belonging to two different knowledge graphs finding the optimal loss function BIBREF12 , whilst PTransE relies on paths to build the final vectors BIBREF1 . The algorithms TransR and CTransR proposed in BIBREF2 aim at building entity and relation embeddings in separate entity space and relation spaces, so as to learn embeddings through projected translations in the relation space; an extension of this algorithm makes use of rules to learn embeddings BIBREF13 . An effort to jointly embed structured and unstructured data (such as text) was proposed in BIBREF14 . The idea behind the DistMult approach is to consider entities as low-dimensional vectors learned from a neural network and relations as bilinear and/or linear mapping functions BIBREF15 . TransG, a generative model address the issue of multiple relation semantics of a relation, has showed to go beyond state-of-the-art results BIBREF0 . ComplEx is based on latent factorization and, with the use of complex-valued embeddings, it facilitates composition and handles a large variety of binary relations BIBREF16 . The fastText algorithm was meant for word embeddings, however BIBREF17 showed that a simple bag-of-words can generate surprisingly good KGEs.
The field of KGE has considerably grown during the last two years, earning a spot also in the Semantic Web community. In 2016, BIBREF3 proposed HolE, which relies on holographic models of associative memory by employing circular correlation to create compositional representations. HolE can capture rich interactions by using correlation as the compositional operator but it simultaneously remains efficient to compute, easy to train, and scalable to large datasets. In the same year, BIBREF4 presented RDF2Vec which uses language modeling approaches for unsupervised feature extraction from sequences of words and adapts them to RDF graphs. After generating sequences by leveraging local information from graph substructures by random walks, RDF2Vec learns latent numerical representations of entities in RDF graphs. The algorithm has been extended in order to reduce the computational time and the biased regarded the random walking BIBREF5 . More recently, BIBREF18 exploited the Global Vectors algorithm to compute embeddings from the co-occurrence matrix of entities and relations without generating the random walks. In following research, the authors refer to their algorithm as KGloVe.
This study addresses the following research questions:
Formally, let $t = (s,p,o)$ be a triple containing a subject, a predicate, and an object in a knowledge base $K$ . For any triple, $(s,p,o) \subseteq E \times R \times (E \cap L)$ , where $E$ is the set of all entities, $R$ is the set of all relations, and $L$ is the set of all literals (i.e., string or numerical values). A representation function $F$ defined as 
$$F : (E \cap R \cap L) \rightarrow \mathbb {R}^d$$   (Eq. 7) 
assigns a vector of dimensionality $d$ to an entity, a relation, or a literal. However, some approaches consider only the vector representations of entities or subjects (i.e, $\lbrace s \in E : \exists (s, p, o) \in K \rbrace $ ). For instance, in approaches based on Tensor Factorization, given a relation, its subjects and objects are processed and transformed into sparse matrices; all the matrices are then combined into a tensor whose depth is the number of relations. For the final embedding, current approaches rely on dimensionality reduction to decrease the overall complexity BIBREF9 , BIBREF12 , BIBREF2 . The reduction is performed through an embedding map $\Phi : \mathbb {R}^d \rightarrow \mathbb {R}^k$ , which is a homomorphism that maps the initial vector space into a smaller, reduced space. The positive value $k < d$ is called the rank of the embedding. Note that each dimension of the reduced common space does not necessarily have an explicit connection with a particular relation. Dimensionality reduction methods include Principal Component Analysis techniques BIBREF9 and generative statistical models such as Latent Dirichlet Allocation BIBREF19 , BIBREF20 .
Existing KGE approaches based on the skip-gram model such as RDF2Vec BIBREF4 submit paths built using random walks to a Word2Vec algorithm. Instead, we preprocess the input knowledge base by converting each triple into a small sentence of three words. Our method is faster as it allows us to avoid the path generation step. The generated text corpus is thus processed by the skip-gram model as follows.
We adapt the skip-gram model BIBREF21 to deal with our small sequences of length three. In this work, we only consider URIs and discard literals, therefore we compute a vector for each element $u \in E \cap R$ . Considering a triple as a sequence of three URIs $T = \lbrace u_s, u_p, u_o$ }, the aim is to maximize the average log probability 
$$\frac{1}{3} \sum _{u \in T} \sum _{u^{\prime } \in T \setminus u} \log p(u | u^{\prime })$$   (Eq. 9) 
which means, in other words, to adopt a context window of 2, since the sequence size is always $|T|=3$ . The probability above is theoretically defined as: 
$$p(u | u^{\prime }) = \frac{\exp ( {v^O_{u}}^{\top } v^I_{u^{\prime }} )}{\sum _{x \in E \cap R} \exp ( {v^O_{x}}^{\top } v^I_{u^{\prime }} )}$$   (Eq. 10) 
where $v^I_x$ and $v^O_x$ are respectively the input and output vector representations of a URI $x$ . We imply a negative sampling of 5, i.e. 5 words are randomly selected to have an output of 0 and consequently update the weights.
Several methods have been proposed to evaluate word embeddings. The most common ones are based on analogies BIBREF22 , BIBREF23 , where word vectors are summed up together, e.g.: 
$$v["queen"] \approx v["king"] + v["woman"] - v["man"]$$   (Eq. 13) 
An analogy where the approximation above is satisfied within a certain threshold can thus predict hidden relationships among words, which in our environment means to predict new links among entities BIBREF4 . The analogy-based score function for a given triple $(\bar{s},\bar{p},\bar{o})$ is defined as follows. 
$$score(\bar{s},\bar{p},\bar{o}) = \frac{1}{\left|\lbrace  (s,\bar{p},o) \in K \rbrace  \right|} \sum _{(s,\bar{p},o) \in K} {
{\left\lbrace \begin{array}{ll}
1 & \text{if } \left\Vert v_{\bar{s}} + v_o - v_s - v_{\bar{o}} \right\Vert \le \epsilon \\
0 & \text{otherwise}
\end{array}\right.}
}$$   (Eq. 14) 
where $\epsilon $ is an arbitrarily small positive value. In words, given a predicate $\bar{p}$ , we select all triples where it occurs. For each triple, we compute the relation vector as the difference between the object and the subject vectors. We then count a match whenever the vector sum of subject $\bar{s}$ and relation is close to object $\bar{o}$ within a radius $\epsilon $ . The score is equal to the rate of matches over the number of selected triples.
We evaluate the scoring function above against a neural network based on Long Short-Term Memories (LSTM). The neural network takes a sequence of embeddings as input, namely $v_s, v_p, v_o$ for a triple $(s,p,o) \in K$ . A dense hidden layer of the same size of the embeddings is connected to a single output neuron with sigmoid activation, which returns a value between 0 and 1. The negative triples are generated using two strategies, i.e. for each triple in the training set (1) randomly extract a relation and its two nodes or (2) corrupt the subject or the object. We use the Adam optimizer and 100 epochs of training.
As recently highlighted by several members of the ML and NLP communities, KGEs are rarely evaluated on downstream tasks different from link prediction (also known as knowledge base completion). Achieving high performances on link prediction does not necessarily mean that the generated embeddings are good, since the inference task is often carried out in combination with an external algorithm such as a neural network or a scoring function. The complexity is thus approach-dependent and distributed between the latent structure in the vector model and the parameters (if any) of the inference algorithm. For instance, a translational model such as TransE BIBREF10 would likely feature very complex embeddings, since in most approaches the inference function is a simple addition. On the other hand, we may find less structure in a tensor factorization model such as RESCAL BIBREF7 , as the inference is performed by a feed-forward neural network which extrapolates the hidden semantics layer by layer.
In this paper, we introduce two metrics inspired by The Identity of Indiscernibles BIBREF24 to gain insights over the distributional quality of the learned embeddings. The more characteristics two entities share, the more similar they are and so should be their vector representations. Considering the set of characteristics $C_K(s)=\lbrace (p_1,o_1),\dots ,(p_m,o_m)\rbrace $ of a subject $s$ in a triple, we can define a metric that expresses the similarity among two entities $e_1,e_2$ as the Jaccard index between their sets of characteristics $C_K(e_1)$ and $C_K(e_2)$ . Given a set of entities $\tilde{E}$ and their $N$ nearest neighbours in the vector space, the overall Neighbour Similarity Test (NST) metric is defined as: 
$$ 
NST(\tilde{E},N,K) = \frac{1}{N \vert \tilde{E} \vert } \sum _{e \in \tilde{E}} \sum _{j=1}^N \frac{\vert C_K(e) \cap C_K(n_j^{(e)}) \vert }{\vert C_K(e) \cup C_K(n_j^{(e)}) \vert }$$   (Eq. 19) 
where $n_j^{(e)}$ is the $j$ th nearest neighbour of $e$ in the vector space.
The second metric is the Type and Category Test (TCT), based on the assumption that two entities which share types and categories should be close in the vector space. This assumption is suggested by the human bias for which rdf:type and dct:subject would be predicates with a higher weight than the others. Although this does not happen, we compute it for a mere sake of comparison with the NST metric. The TCT formula is equal to Equation 19 except for sets $C_K(e)$ , which are replaced by sets of types and categories $TC_K(e)$ .
We implemented KG2Vec in Python 2.7 using the Gensim and Keras libraries with Theano environment. Source code, datasets, and vectors obtained are available online. All experiments were carried out on an Ubuntu 16.04 server with 128 GB RAM and 40 CPUs.
The dataset used in the experiments are described in Table 1 . The AKSW-bib dataset – employed for the link prediction evaluation – was created using information from people and projects on the AKSW.org website and bibliographical data from Bibsonomy. We built a model on top of the English 2015-10 version of the DBpedia knowledge graph BIBREF25 ; Figure 1 shows a 3-dimensional plot of selected entities. For the English DBpedia 2016-04 dataset, we built two models. In the first, we set a threshold to embed only the entities occurring at least 5 times in the dataset; we chose this setting to be aligned to the related works' models. In the second model, all 36 million entities in DBpedia are associated a vector. More insights about the first model can be found in the next two subsections, while the resource consumption for creating the second model can be seen in Figure 3 .
In this study, we aim at generating embeddings at a high rate while preserving accuracy. In Table 1 , we already showed that our simple pipeline can achieve a rate of almost $11,000$ triples per second on a large dataset such as DBpedia 2016-04. In Table 2 , we compare KG2Vec with three other scalable approaches for embedding knowledge bases. We selected the best settings of RDF2Vec and KGloVe according to their respective articles, since both algorithms had already been successfully evaluated on DBpedia BIBREF4 , BIBREF18 . We also tried to compute fastText embeddings on our machine, however we had to halt the process after three days. As the goal of our investigation is efficiency, we discarded any other KGE approach that would have needed more than three days of computation to deliver the final model BIBREF18 .
RDF2Vec has shown to be the most expensive in terms of disk space consumed, as the created random walks amounted to $\sim $ 300 GB of text. Moreover, we could not measure the runtime for the first phase of KGloVe, i.e. the calculation of the Personalized PageRank values of DBpedia entities. In fact, the authors used pre-computed entity ranks from BIBREF26 and the KGloVe source code does not feature a PageRank algorithm. We estimated the runtime comparing their hardware specs with ours. Despite being unable to reproduce any experiments from the other three approaches, we managed to evaluate their embeddings by downloading the pretrained models and creating a KG2Vec embedding model of the same DBpedia dataset there employed.
For the link prediction task, we partition the dataset into training and test set with a ratio of 9:1. In Table 3 , we show preliminary results between the different strategies on the AKSW-bib dataset using KG2Vec embeddings. As can be seen, our LSTM-based scoring function significantly outperforms the analogy-based one in both settings. According to the Hits@10 accuracy we obtained, corrupting triples to generate negative examples is the better strategy. This first insight can foster new research on optimizing a scoring function for KGE approaches based on distributional semantics.
Computing the NST and TCT distributional quality metrics on the entire DBpedia dataset is time-demanding, since for each entity, the model and the graph need to be queried for the $N$ nearest neighbours and their respective sets. However, we approximate the final value by tracing the partial values of NST and TCT over time. In other words, at each iteration $i$ , we compute the metrics over $\tilde{E}_i = \lbrace e_1, \dots , e_i\rbrace $ . Figure 2 shows the partial TCT value on the most important 10,000 entities for $N=\lbrace 1,10\rbrace $ according to the ranks computed by BIBREF26 . Here, KG2Vec maintains a higher index than the other two approaches, despite these are steadily increasing after the $\sim 2,000$ th entity. We interpret the lower TCT for the top $2,000$ entities as noise produced by the fact that these nodes are hyperconnected to the rest of the graph, therefore it is hard for them to remain close to their type peers. In Figures 2 and 3 , the TCT and NST metrics respectively are computed on 10,000 random entities. In both cases, the values for the two settings of all approaches stabilize after around $1,000$ entities, however we clearly see that RDF2Vec embeddings achieve the highest distributional quality by type and category. The higher number of occurrences per entity in the huge corpus of random walks in RDF2Vec might be the reason of this result for rarer entities.
In Figure 3 , we show the CPU, Memory, and disk consumption for KG2Vec on the larger model of DBpedia 2016-04. All three subphases of the algorithm are visible in the plot. For 2.7 hours, tokens are counted; then, the learning proceeds for 7.7 hours; finally in the last 2.3 hours, the model is saved.
We presented a fast approach for generating KGEs dubbed KG2Vec. We conclude that the skip-gram model, if trained directly on triples as small sentences of length three, significantly gains in runtime while preserving a decent vector quality. Moreover, the KG2Vec embeddings have shown higher distributional quality for the most important entities in the graph according to PageRank. As a future work, we plan to extend the link prediction evaluation to other benchmarks by using analogies and our LSTM-based scoring function over the embedding models of the approaches here compared.

Figure and table captions:
Fig. 1 A selection of DBpedia resources along with their vectors in 3 dimensions obtained using Principal Component Analysis. Blue points are resources, whilst red points are classes. As can be seen, resources follow the distributional hypothesis.
Table 1 Details and runtimes for the generation of KG2Vec embeddings on two datasets.
Table 2 Runtime comparison of the single phases. Those with (*) are estimated runtimes.
Table 3 Filtered Hits@10 values on link prediction on AKSW-bib using different strategies.
Fig. 2 Partial TCT value on DBpedia 2016-04 for the top 10,000 entities. 0 2000 4000 6000 8000 10000 Iteration
Fig. 4 Partial NST value on DBpedia 2016-04 for 10,000 random entities. 0 2 4 6 8 10 12 14
Fig. 5 CPU, Memory, and disk consumption for KG2Vec on the larger model of DBpedia 2016-04.

Questions about this paper:
What is the new metric?
How long do other state-of-the-art models take to process the same amount of data?

Answers:
Neighbour Similarity Test (NST) and Type and Category Test (TCT)
between 12 hours and 96 hours