We present a family of four novel methods for embedding knowledge graphs into real-valued tensors that capture the ordered relations found in RDF. Unlike many previous models, these can easily use prior background knowledge from users or existing knowledge graphs. We demonstrate our models on the task of predicting new facts on eight different knowledge graphs, achieving a 5% to 50% improvement over existing systems. Through experiments, we derived recommendations for selecting the best model based on knowledge graph characteristics. We also give a provably-convergent, linear tensor factorization algorithm.
Knowledge graphs are increasingly important due to their effectiveness in supporting a wide range of applications. While immensely useful in their current state, much work remains to be done to detect and correct errors they contain and add missing relations. Representation learning [2] provides a way to augment or reduce reliance on manually constructed ontology axioms and rules by using knowledge graph instances to discover common patterns and then use them to suggest changes to the graph. One popular approach is based on learning how to embed the entities and relations in a graph into a real-valued vector space, allowing the entities and relations to be represented by dense, real-valued vectors. There is considerable interest in understanding how graph embeddings can be used to augment knowledge graphs [11,19].
Current state-of-the-art systems compute embeddings to support a specific task,
which might be link ranking (aka link recommendation), or fact prediction (Table 1).
Link ranking tries to augment the graph by recommending relations that could hold
between a subject–object pair assuming (
Embedding entities and relations into a vector space has been shown to achieve good results. Tensor–based approaches like RESCAL [14] jointly learn the latent representation of entities and relations by factorizing the tensor representation of the knowledge graph. This can be further improved by imposing constraints on the factors, such Tasks Alternate terminology Definition Example
Input: Given relation r and entity ei. (ei,r, ?) Link ranking Link prediction Output: Rank possible entities ej (ranking) Link recommendation – or –
Input: Given entity pair ei and ej. (ei,?, ej)
Output: Rank possible relations, r Fact prediction Link classification Input: triple (aka fact), ei, r, and ej. Input: Is the Statue of Liberty located in Germany? (classification) Fact classification Output: 0 (No) or 1 (Yes) Output: 0 (No)
Table 1. We focus on a binary classification fact prediction task rather than link ranking
Input: Where is Statue of Liberty located?
Output: (
However, these models do not exploit the similarity among relations when
computing embeddings nor have they studied the role that relation similarities have on
regularizing and constraining the relation embeddings and the subsequent effect on fact
prediction. We addresses these deficiencies and make four contributions: we (
Our approach for similarity-driven knowledge graph embedding relies on learning entity and relation embedding such that when “combined” (multiplied), the result is a close approximation of the original facts and relation occurrences observed in the graph.
We augment the learning process with a relational similarity matrix that provides a holistic judgment of how similar pairs of relations are, adding addtional constraints to the learned embeddings.
We represent a multi-relational knowledge graph of Nr binary relations among Ne entities by the order-3 tensor X of dimension Ne Ne Nr where each Ne Ne is an adjacency matrix for relation k (called slice) has values of 1 when the ith entity (ei) is connected to the jth entity (ej ) with relation k, else 0. This binary tensor is often very large and sparse. Our goal is to construct dense, informative p-dimensional embedding for entities and relations. We represent the collection of p-dimensional entity embeddings by A of size Ne p, a compact order-3 tensor R of size p p Nr, and the similarity matrix by C of size Nr Nr (symbols are same as described in [18]).
Our objective is to reconstruct each of the k relation slices of X as the product Xk
A
RkA| : Here both A and A are matrices: each row is the embedding of an entity. By changing the exact form of A—that is, the number of different entity matrices, or the different ways to index A—we can then arrive at different models, each encapsulating both mathematical and philosophical differences. In this extended abstract, we describe just one of the four models, with full details on all available at [18]. We examine the case of having only a single entity embedding matrix, represented as A—that is, A = A = A. This results in a quadratic reconstruction problem, as we approximate Xk ARkA|: We also examine the case of having two separate entity embedding matrices, represented as A1 and A2. This results in a reconstruction problem that is linear in the entity embeddings, as we approximate Xk A1RkA2|:
We learn A, and R by minimizing the augmented reconstruction loss
(
z }| { min f (A; R) + g(A; R) + fs(A; R; C) :
A;Rreco|nstr{ucztion}loss knowle|dge-dir{eczted enr}ichment
The first term of (
Computing relational similarity matrix C. We can view a knowledge graph’s nodes and edges as representing a flow of information, with subjects and objects acting as information producers and consumers, respectively. Tensor factorization captures this interaction [14]. Relations that occur on more of the same entities are more likely to have some notion of being similar. Each element of the Nr Nr matrix C represents the similarity between a pair of relations, i.e., slices X i and X j , and is computed using the following equation for all pairs of relations (1 i; j Nr): (Symmetric)
Ci;j = j(S(Xi) [ O(Xi)) \ (S(Xj ) [ O(Xj ))j
j(S(Xi) [ O(Xi)) [ (S(Xj ) [ O(Xj ))j
(
We measure relation similarity using the overlap in the entities observed with each
relation. In addition to computing similarity matrices based on relation symmetry using
Eq. 3, we support four additional measures: (
The QC model: Quadratic+Constraint. The QC model casts the decomposition of
the order-3 tensor X into a compact relational tensor R and quadratic entity matrix A
and solve the following problem.
(
min f (A; Rk) + g(A; Rk) + fLag(R; C) A;Rk f (A; Rk) = 12 XjjXk
ARkAT jj2F k g(A; Rk) = 12 ajjAjj2F + 12 r Pk jjRkjj2F fLag =
XX i j ij (1 jjRi
Rj jj2F + Cij ): Here A is a n p matrix where each row represents the entity embeddings and Rk is a p p matrix representing the embedding for the kth relation capturing the interaction between the entities. The first term f forces the reconstruction to be similar to the original tensor and the second regularizes the unknown A and Rk to avoid overfitting.
The flag term represents the model’s knowledge-directed enrichment component. In order to incorporate similarity constraints, we solve the dual objective for a constraint in Eq. 8 such that relations with high similarity are near one another. We convert a constraint problem into an unconstrained problem via Lagrange multipliers ij . jjRi
Rj jj2F = 1
Cij ; 1 i; j n: Computing Factor Matrices, A, Rk and Lagrange Multipliers ij . We compute the unknown factor matrices using the Adam optimization [8] stochastic gradient descent extension. Each unknown is updated in the alternative fashion, in which each parameter is updated while treating the others as constants. The model’s unknown parameters in A and Rk are updated with different learning rates. We empirically found that the error value of the objective function decreases after few iterations. Taking the partial derivative of the Eq. 4 with respect to A and equating to zero, we obtain the update rule for A. Since we are indirectly constraining the embeddings of A through slices of the compact relation tensor R, we obtain the same update rule for A as in RESCAL. By equating the partial derivatives of Eq. 4 with respect to the unknowns Rk and ij to 0, we obtain updates for Rk and ij as describe in the [18].
Kinship 104 26 10,686 102.75 0.98798 UMLS 135 49 6,752 50.01 0.37048 FB15-237 14,541 237 310,116 21.32 0.00147 DB10k 4,397 140 10,000 2.27 0.00052 FrameNet 22,298 16 62,344 2.79 0.00013 WN18 40,943 18 151,442 3.70 0.00009 FB13 81,061 13 360,517 4.45 0.00005 WN18RR 40,943 11 93,003 2.27 0.00005
Table 2. Statistics of the eight datasets used in evaluation experiments 3
We evaluated the performance of the entity and relation embeddings on the fact prediction task, which distinguishes correct from incorrect triples, and compared the results with state-of-the-art tensor decomposition models RESCAL and NN-RESCAL, and two popular neural-based benchmarks, DistMult (which considers relation embedding matrices to be diagonal) and ComplEx (which represents entities and relation in complex vector space). Here we present results only for the tensor-based models; additional evaluation data and comparisons with neural-based models are in [18].
Datasets. Table 3 summarizes the key statistics of the datasets: the number of entities (Ne), relations (Nr) and facts (non-zero entries in the tensor), the average degree of entities across all relations (the ratio of facts to entities) and the graph density (the number of facts divided by square of the number of entities). A smaller average degree or graph density indicates that the knowledge graph is sparser.
We used eight datasets in our evaluation, including both previous graph-embedding
benchmarks and new ones. They include (
Tensor creation, parameter selection and performance metric. We created a 0-1 tensor for each dataset, as described in [18]. If entity s has relation r with entity o, then the value of the (s, r, o) entry in the tensor is set to 1, otherwise it is set to 0. Each of the created tensors is used to generate a slice-similarity matrix using Eq. 3. We fix the parameters for different datasets using coordinate descent, changing only one hyperparameter at a time and always making a change from the best configuration of hyperpa
Previous tensor factorization models RESCAL 93.24 88.53 62.13 65.37 61.27 82.54 66.63 92.56 NN-RESCAL 92.19 88.37 83.93 79.13 81.72 82.6 68.49 93.03
Linear/Quadratic Regularized/Constrained tensor factorization models LR 93.99 88.22 81.86 80.07 80.79 78.11 69.15 90.00 QR 93.89 88.11 84.41 79.12 80.47 82.34 66.73 93.07 LC 92.87 84.71 80.18 75.79 80.67 73.64 66.46 81.88 F QC 93.84 86.17 91.07 85.15 81.69 86.24 72.62 86.47 rameters found so far. The latent dimension is equal to the number of relations. We use the same performance metric as RESCAL on three samples: stratified-uniform (sampling 60% correct and 40% incorrect from each relation), stratified-weighted (sampling 60% correct and 40% incorrect from the public dataset with few relations are mentioned more frequently then other), and balanced-weighted (dataset mentioned in [20]).
Results and discussion. In this section we analyze and the results of our models, which include a quantitative comparison with other tensor-based models and the impact of knowledge graph sparsity on the models. Table 3 has the AUC performance of our models which range from 5% to 50%.
The Kinship and UMLS datasets have a significantly higher graph density compared to the others, as shown in Table 3. Combining this observation with the results in Table 3, we notice that graphs with lower density result in larger performance variability across both the baseline systems and our models. This suggests that when learning knowledge graph embeddings on dense graphs, basic tensor methods like RESCAL can give acceptable performance, but that for lower density graphs, different embedding learning mechanisms may be better. Focusing on the datasets with lower graph density, we see that while the LC and LR models often matched or surpassed RESCAL, they achieved comparable or lower performance compared to their corresponding quadratic models (QC and QR). This is due to the fact that the distinction of the subject and object made by A1 and A2 embeddings tends not to hold in many of the standard datasets. That is, objects can behave as subjects (and vice versa), as in the WN18 dataset. Hence the distinction between the subject and the object may not always be needed.
The performance difference between the quadratic and linear versions is high for WN18 and FB13, though the difference is relatively small for DB10k. This is largely because the DBpedia dataset includes many datatype properties, i.e., properties whose values are literals rather than entities.
In most cases, non-negative RESCAL outperforms the linear models. The QC model significantly outperforms RESCAL and performs relatively better compared to our other three models, emphasizing the importance of the flexible penalization that the Lagrange multipliers provide. Compared to all others, the QC model performs better in most of the cases, since the Lagrange multiplier introduces flexibility in penalizing the latent relational embeddings while learning. We also did significance tests using a Wilcoxon signed-rank test for all algorithms and datasets at significance level of 1% and found the QC model to perform better compared to the others. In summary, both the quadratic and linear models are important depending on the data, with the QC model performing the best overall and the Linear models performing comparably.
Effect of similarity encoding. Figure 3 shows the relative changes in performance of each similarity metric compared to RESCAL, grouped by how we encode the knowledge. The gray boxes show the percent change of the two RESCAL versions. Most encoding approaches perform well, but the encoding can yield a significant performance gain for certain datasets. In DB10 (top left) using LR the agency and symmetric encodings give poor performance. Changing the encoding to transitivity or reverse transitivity yields a large performance gain. On the other hand, for WN18RR both transitivity and reverse transitivity with the LR model perform poorly. The LC model performs similarly for all kinds of encoding. Moreover, QC performs consistently well compared to all the baselines without being affected by the similarity encoding. While we find that different kinds of similarity encoding methods can, and do, influence performance, we see the effect of how that knowledge is encoded in these datasets. For example, whether an encoding uses a symmetric or transitive approach may be less important than whether or not accurate knowledge is encoded at all. The knowledge enrichment that the encoding provides can result in effective model generalization beyond what simple, knowledge-poor regularizations, like Frobenius norm regularization, give.
We described a new framework for learning knowledge-enriched entity and relation embeddings and four readily obtainable models that generalize existing efforts and demonstrate significant improvements over both state-of-the-art tensor decomposition and neural-based translation models. We motivated and empirically explored different methods for encoding prior knowledge into the tensor factorization algorithm, finding that using transitive relationship chains resulted in the highest overall performance. We further characterized the conditions under which each model performed well and concluded the QC model is typically the best choice. Finally, we proved in [18] that the LR model has the desirable property of convergence.
Our future work will use the KGFP framework for fact prediction in three different
scenarios: (