Knowledge Graphs are a widely used formalism for representing knowledge in the Web of Data. We focus on the problem of predicting missing links in large knowledge graphs, so to discover new facts about the world. Recently, representation learning models that embed entities and predicates in continuous vector spaces achieved new state-of-the-art results on this problem. A major limitation in these models is that the training process, which consists in learning the optimal entity and predicate embeddings for a given knowledge graph, can be very computationally expensive: it may even require days of computations for large knowledge graphs. In this work, by leveraging adaptive learning rates, we propose a principled method for reducing the training time by an order of magnitude, while learning more accurate link prediction models. Furthermore, we employ the proposed training method for evaluating a set of novel and scalable models. Our evaluations show significant improvements over state-of-the-art link prediction methods on the WORDNET and FREEBASE datasets.
Knowledge Graphs (KGs) are graph-structured Knowledge Bases (KBs), where
factual knowledge about the world is represented in the form of relationships between
entities. They are widely used for representing relational knowledge in a variety of
domains, such as citation networks and protein interaction networks. An example of their
widespread adoption is the Linked Open Data (LOD) Cloud, a set of interlinked KGs
such as Freebase [
Despite their large size, many KGs are still largely incomplete. For example
consider Freebase 2, a core element in the Google Knowledge Vault project [
In this work we focus on the problem of completing missing links in large KGs, so to
discover new facts about the world. In the literature, this problem is referred to as link
prediction or knowledge graph completion, and has received a considerable attention
over the last years [
Recently, representation learning [
The embeddings of all entities and predicates in the KG are learned jointly: the learning process consists in minimizing a global loss functional considering the whole KG, by back-propagating the loss to the embeddings 3. As a consequence, the learned entity and predicate embeddings retain global, structural information about the whole KG, and can be used to serve several kinds of applications. In link prediction, the confidence of each candidate edge can be measured as a function of the embeddings of its source entity, its target entity, and its predicate.
A major limitation in embedding models proposed so far, however, is that the
learning procedure (i.e. learning the optimal embeddings of all entities and predicates in the
KG) can be very time-consuming: it is based on an incremental optimization algorithm
that may require days of computation to converge for large KGs [
In this work, we propose a novel principled method for significantly reducing the learning time in embedding models, based on adaptive per-parameter learning rates. Furthermore, we employ the proposed training method for evaluating a variety of novel embedding models: our evaluations achieves new state-of-the-art link prediction results on the WORDNET and FREEBASE datasets. 2
RDF Graphs The most widely used formalism for representing knowledge graphs is the W3C Resource Description Framework (RDF) 4, a recommended standard for representing knowledge on the Web. An RDF KB, also referred to as RDF graph, is a set of RDF triples in the form hs; p; oi, where s, p and o respectively denote the subject, the predicate and the object of the triple: s and o are entities, and p is a relation type. Each triple hs; p; oi describes a statement, which is interpreted as “A relationship p holds between entities s and o”.
Example 2.1 (Shakespeare). The statement “William Shakespeare is an author who wrote Othello and the tragedy Hamlet” can be expressed by the following RDF triples: hShakespeare; hShakespeare; hShakespeare; hHamlet; profession; author; author; genre;
3 In natural language processing, a similar procedure is used by the word2vec model [
An RDF graph can be viewed as a labeled directed multigraph, where each entity is a vertex, and each RDF triple is represented by a directed edge whose label is a predicate, and emanating from its subject vertex to its object vertex. In RDF KBs, the Open-World Assumption holds: a missing triple does not mean that the corresponding statement is false, but rather that its truth value is unknown (it cannot be observed). In the following, given an RDF graph G, we denote as EG the set of all entities occurring as subjects or objects in G, and as RG the set of all predicates occurring in G: EG = fs j 9hs; p; oi 2 Gg [ fo j 9hs; p; oi 2 Gg;
RG = fp j 9hs; p; oi 2 Gg: For instance, in the case of the RDF graph shown in Ex. 2.1, the sets EG and RG are the following: EG = fAuthor; Shakespeare; Hamlet; Othello; Tragedyg and RG = fprofession; author; genreg.
Furthermore, we denote as SG = EG RG EG the space of possible triples of G, i.e. the set of all triples that can be created by using the entities and predicates in G (note that G SG). We refer to all triples in G as observed triples, and to all triples in SG n G as unobserved triples.
Energy-Based Models Embedding models for KGs can be described in terms of
Energy-Based Models (EBMs) [
A fundamental component in an EBM is a scalar-valued energy function (or
scoring function) E ( ), parametrized by , which associates a scalar energy value to the
configuration of a set of variables. The energy of a configuration of a set of variables is
inversely proportional to its probability: more likely configurations are associated with
lower energy values, while less likely configurations are associated with higher energy
values. Several tractable methods have been proposed for learning the parameters of an
energy function [
2 where is the parameter space, and L( ) is a loss functional which measures the quality of the energy function E ( ) on the data D. Intuitively, the loss functional L( ) assigns a lower loss to energy functions that associate a lower energy (corresponding to a higher probability) to correct answers, and higher energy (corresponding to a lower probability value) to all other incorrect answers.
Energy-Based Models for RDF Graphs As discussed in [
Consider the RDF graph shown in Ex. 2.1. In such a graph, we prefer learning an energy-based model that assigns a lower energy (a higher probability value) to the triple hOthello; genre; Tragedyi, which is unobserved but represents the true statement “Othello is a Tragedy”, and a higher energy (a lower probability value) to other unobserved triples, for example hHamlet; genre; Authori. 3
Several EBMs have been proposed in the literature for addressing the problem of link
prediction in KGs [
Formally, let G be an RDF graph. For each entity x 2 EG, embedding models learn
a continuous vector representation ex 2 Rk, with k 2 N, called the embedding vector
of x. Similarly, for each predicate p 2 RG, embedding models learn an operation on the
embedding vector space, characterized by a set of embedding parameters. This can be
an empty set of parameters, as in the Unstructured model proposed in [
The distributed representations of all entities and predicates in G are then used for defining an energy distribution E : SG ! R over the space of possible triples of G. In particular, the energy E(hs; p; oi) of a triple hs; p; oi is defined as a function of the distributed representations of its subject s, its predicate p and its object o.
In Tab. 1, we report the energy functions adopted by several models proposed in the
literature. For each model, we report the number of parameters needed for storing the
distributed representations of all entities and predicates: ne = jEGj denotes the number
of entities in the KG, nr = jRGj denotes the number of predicates, and k; d 2 N
are user-defined hyper-parameters. In general, if the number of parameters in a model
grows super-linearly with the number of entities and predicates in the KG, it becomes
increasingly harder for the model to scale to very large and Web-scale KGs.
The Translating Embeddings model Among the models outlined in Tab. 1, the
recently proposed Translating Embeddings model (TransE) [
The TransE model is very simple. In TransE, each entity x 2 EG is represented by its embedding vector ex 2 Rk, and each predicate p 2 RG is represented by a (vector) translation operation ep 2 Rk. The energy of a triple hs; p; oi is given by the L1 or L2 distance between (es + ep) and eo:
E(hs; p; oi) = k(es + ep)
eokf1;2g:
In TransE, all the embedding and translation vectors are learned jointly from the KG by
using Stochastic Gradient Descent, as discussed in Sect. 4. The number of parameters
needed by the TransE model for storing all the embedding and translation vectors is
(nek + nrk), a quantity that grows linearly with ne and nr. For such a reason, TransE
can potentially scale to very large and highly-relational KGs [
A New Set of Embedding Models In the following, we propose a set of variants of the
TransE model, which preserve its scalability properties. Let d(x; y) be a dissimilarity
function, from the following set: d(x; y) 2 fkx yk1; kx yk2; xT yg, i.e. chosen
from the L1 and L2 distance, and the negative inner product. We propose the following
embedding models, where each is defined by the corresponding energy function E( ):
– TransE : E(hs; p; oi) = d(es + ep; eo);
– TransE+ : E(hs; p; oi) = d(es + ep;1; eo + ep;2);
– ScalE : E(hs; p; oi) = d(es ep; eo);
– ScalE+ : E(hs; p; oi) = d(es ep;1; eo ep;2);
where es; eo 2 Rk are the embedding vectors of the entities appearing as the subject s
and the object o; ep; 2 Rk are the embedding parameters of the predicate p, denoting
either a translation or a scaling vector; and denotes the Hadamard (element-wise)
product, corresponding to the vector scaling operation. The energy function in TransE
is the same used in [
E (y~) + fCompute the gradient of the lossg fCompute the update to model parameters (embeddings)g fUpdate the model parametersg improve the performance on the validation set. The TransE+ model generalizes TransE by also translating the object embedding vector eo.
The ScalE and ScalE+ models are similar to the previous two models, but replace the vector translation with a scaling operation. The rationale behind ScalE and ScalE+ is the following: scaling the embedding vector of an entity can be seen as weighting the (latent) features of such an entity in the embedding vector space.
All proposed models share the same advantages as the TransE model: (i) the required number of parameters is O (nek + nrk), which grows linearly with ne and nr, and (ii) the energy function and its gradient w.r.t. the embedding of entities and predicates can be computed very efficiently, using element-wise vector operations. 4
In [
During the learning process, unobserved triples are randomly generated by means of a corruption process, which replaces either the subject or the object of each observed triple with another entity in G. More formally, given an observed triple y 2 G, let CG(y) denote the set of all corrupted triples obtained by replacing either its subject or object with another entity in G:
CG(hs; p; oi) = fhs~; p; oi j s~ 2 EGg [ fhs; p; o~i j o~ 2 EGg: The embeddings of all entities and predicates in the KG, which compose the model parameters, can be learned by minimizing a margin-based ranking loss. More formally, learning the optimal model parameters ^, corresponding to all the entity and predicate embeddings, is equivalent to solving the following constrained minimization problem: minimize
2 subject to
X y2G
X y~2CG(y) 8x 2 EG : kexk = 1; + E (y)
E (y~) + (1) where [x]+ = maxf0; xg, and 0 is a hyper-parameter referred to as margin. The objective function in Eq. 1 (corresponding to the loss functional L( ) discussed in Sect. 2) enforces the energy of observed triples to be lower than the energy of unobserved triples. The constraints in the optimization problem prevent the training process to trivially solve the problem by increasing the entity embedding norms. Stochastic Gradient Descent In the literature, the constrained loss minimization problem in Eq. 1 is solved using Stochastic Gradient Descent (SGD) in mini-batch mode, as summarized in Alg. 1. On each iteration, the algorithm samples a batch of triples from the knowledge graph G. Batches are obtained by first randomly permuting all triples in G, partitioning them into nb batches of the same size, and then iterating over such batches. A single pass over all triples in G is called an epoch. Then, for each triple y in the batch, the algorithm generates a corrupted triple y~ uniformly sampled from CG(y): this leads to a set T of observed/corrupted pairs of triples hy; y~i. The observed/corrupted triple pairs are used for computing the gradient of the objective (loss) function in Eq. 1 w.r.t. the current model parameters . Finally, is updated in the steepest descent direction of the objective function. This procedure is repeated until convergence.
The main drawback of SGD is that it requires an initial, careful tuning of the global
learning rate , which is then used for updating all model parameters, regardless of their
peculiarities. However, if an entity x 2 EG occurs in a limited number of triples in G,
the corresponding embedding vector ex 2 Rk will be updated less often, and it will
require a much longer time to be learned. For such a reason, SGD may be very
timeconsuming and slow to converge. For instance, it was reported in [
A possible solution to this problem consists in associating smaller learning rates to parameters updated more often, such as the embedding vectors of entities appearing more frequently, and larger learning rates to parameters updated less often. Adaptive Learning Rates In order to reduce the time required for learning all entity and predicate embeddings, in this work we propose leveraging Adaptive Per-Parameter Learning Rates. While SGD uses a global, fixed learning rate for updating all parameters, we propose relying on methods for estimating the optimal learning rate for each parameter, while still being tractable for learning very large models.
We consider two highly-scalable criteria for selecting the optimal learning rates,
namely the Momentum method [
Momentum Method The idea behind this method is to accelerate the progress along dimensions where the sign of the gradient does not change, while slowing the progress along dimensions where the sign of the gradient continues to change. The new update rule is defined as follows: t t 1 mgt; where
m 2 R is a user-defined hyper-parameter. AdaGrad This method is based on the idea that the learning rate of each parameter should grow with the inverse of gradient magnitudes. The update rule in AdaGrad is: t
a
qPt
j=1 gj2
gt;
where a 2 R is a user-defined hyper-parameter. AdaGrad adds nearly no complexity,
it has very strong convergence guarantees [
This section is organized as follows. In Sect. 5.1 we describe experimental settings, datasets and evaluation metrics. In Sect. 5.2, we show that adaptive learning rates sensibly improve both the efficiency of the learning process, and the predictive accuracy of embedding models. In Sect. 5.3, we empirically evaluate the novel embedding models proposed in Sect. 3, by training them using adaptive learning rates. 5.1
Experimental Settings
Link Prediction In these experiments, we used the metrics proposed in [
Metric
Unstructured [
RESCAL [
SE [
LFM [
In the FILTERED setting, corrupted triples that exist in either the training, validation
or test set were removed before computing the rank of each triple. In both settings, a
lower MEAN RANK is better, while a higher HITS@10 is better.
Learning Time For comparing Momentum and AdaGrad with SGD on the task of
solving the optimization problem in Eq. 1, we empirically evaluated such methods on
the task of learning the parameters in TransE on WN18 and FB15K, using the optimal
hyper-parameter settings reported in [
Momentum: rate m 2 G , decay rate 2 G .
For each possible combination of optimization method and hyper-parameter values, we performed an evaluation consisting in 10 learning tasks, each using a different random initialization of the model parameters.
Fig. 1 shows the behavior of the loss functional for each of the optimization
methods, using the best hyper-parameter settings selected after 100 training epochs. We can
immediately observe that, for both WORDNET (WN18) and FREEBASE (FB15K),
AdaGrad (with rate a = 0:1) yields sensibly lower values of the loss functional than
SGD and Momentum, even after very few iterations (< 10 epochs). The duration of
each epoch was similar in all methods: each epoch took approx. 1.6 seconds in
WORDNET (WN18), and approx. 4.6 seconds in FREEBASE (FB15K) on a single i7 CPU.
Quality of Learned Models We also measured the quality of models learned by
AdaGrad, in terms of the MEAN RANK and HITS@10 metrics, in comparison with SGD.
For this purpose, we trained TransE using AdaGrad (instead of SGD) with a = 0:1 for
100 epochs, denoted as TransEA, and compared it with results obtained with TransE
from the literature on Link Prediction tasks on the WORDNET and FREEBASE datasets.
Hyper-parameters were selected according to the performance on the validation set,
using the same grids of hyper-parameters used for TransE in [
Evaluation of the Proposed Embedding Models
In this section, we evaluate the embedding models inspired by TransE and proposed
in Sect. 3: ScalE, TransE+ and ScalE+. Model hyper-parameters were selected
according to the performance on the validation set. In the following experiments, we
considered a wider grid of hyper-parameters: in particular, we selected the
embedding vector dimension k in f20; 50; 100; 200; 300g, the dissimilarity function d(x; y)
in fkx yk1; kx yk2; xT yg, and the margin in f1; 2; 5; 10g. All models were
trained using AdaGrad, with a = 0:1, for only 100 epochs. The reduced training time
enabled us to experiment with a wider range of hyper-parameters in comparison with
related works in literature [
Results are summarized in Tab. 4. We can see that, despite their very different
geometric interpretations, all of the embedding models proposed in Sect. 3 achieve
sensibly higher results in terms of HITS@10 in comparison with every other link prediction
models outlined in Sect. 3. An explanation is that both TransE [
In each experiment, the proposed models ScalE and ScalE+ always improve over
TransE in terms of HITS@10. We can clearly see that, by leveraging: (i) Adaptive
learning rates, and (ii) The proposed embedding models ScalE and ScalE+, we were
able to achieve a record 95.5% HITS@10 on WORDNET, and a 73.0% HITS@10 on
FREEBASE. These results are sensibly higher than state-of-the-art results reported in
[
A significantly lower training time – from days, as reported by [
We focused on the problem of link prediction in Knowledge Graphs. Recently,
embedding models like the TransE [
In this paper, we proposed a method for sensibly reducing the learning time in embedding models based on adaptive learning rate selection, and proposed a set of new models with interesting scalability properties. We extensively evaluated the proposed methods in several experiments on real world large datasets. Our results show a significant improvement over state-of-the-art link prediction methods, while significantly reducing the required training time by an order of magnitude.
The contributions in this paper sensibly improve both the effectiveness and applicability of embedding models on large and Web-scale KGs. Source code and datasets for reproducing the empirical evaluations discussed in this paper are available on-line 5.