Complex and Holographic Embeddings of Knowledge Graphs: A Comparison

Introduction

Embeddings of knowledge graphs have received significant attention due to their excellent performance for tasks like link prediction and entity resolution. In this short paper, we are providing a comparison of two state-of-the-art knowledge graph embeddings for which their equivalence has recently been established, i.e., ComplEx and HolE [Nickel, Rosasco, and Poggio, 2016; Trouillon et al., 2016; Hayashi and Shimbo, 2017]. First, we briefly review both models and discuss how their scoring functions are equivalent. We then analyze the discrepancy of results reported in the original articles, and show experimentally that they are likely due to the use of different loss functions. In further experiments, we evaluate the ability of both models to embed symmetric and antisymmetric patterns. Finally, we discuss advantages and disadvantages of both models and under which conditions one would be preferable to the other.

Equivalence of Complex and Holographic Embeddings

In this section, we will briefly review Holographic and Complex embeddings and discuss the equivalence of their scoring functions.

Let $\mathcal{G}=(\mathcal{E},\mathcal{R},\mathcal{T})$ be a knowledge graph, which consists of entities $\mathcal{E}$, relation types $\mathcal{R}$ and observed triples $\mathcal{T}\subseteq\mathcal{R}\times\mathcal{E}\times\mathcal{E}$. Furthermore, let $\mathcal{D}$ be a training set, which associates with each possible triple in $\mathcal{G}$ its truth values $y\in\{\pm 1\}$. That is, for a possible triple $(p,s,o)$ with $s,o\in\mathcal{E}$ and $p\in\mathcal{R}$ it holds that

For notational convenience, we define the trilinear product of three complex vectors as:

The circular correlation can be written with the discrete Fourier transform (DFT),

Complex Embeddings

Equivalence

The equivalence of HolE and ComplEx has recently been shown by Hayashi and Shimbo . In the following, we briefly discuss this equivalence of both models and how it can be derived. For completeness, a full proof similar to that of Hayashi and Shimbo is included in Appendix A.

First, to derive the connection between HolE and ComplEx, consider Parseval’s Theorem:

Using 1 as well as Equations 2 and 3, we can then rewrite the scoring function of HolE as:

Furthermore, both models have equal memory complexity, as the equivalent complex vectors are twice as small (see proof in Appendix A) but require twice as much memory as real-valued ones of same size—for a given floating-point precision. However, the complex formulation of the scoring function reduces the time complexity from $\mathcal{O}(K\log(K))$ (quasilinear) to $\mathcal{O}(K)$ (linear).

Loss Functions & Predictive Abilities

The experimental results of HolE and ComplEx as reported by Nickel, Rosasco, and Poggio and Trouillon et al. agreed on the WN18 data set, but diverged significantly on FB15K Bordes et al. —although both scoring function are equivalent. Since the main difference in the experimental settings was the use of different loss functions—i.e., margin loss versus logistic loss—we analyze in this section whether the discrepancy of results can be attributed to this fact. For this purpose, we implemented both loss functions for the complex representation $\phi^{c}$ within the same framework, and compared the results on the WN18 and FB15K data sets.

First, note that in both data sets, only positive training triples are provided. Negative examples are generated by corrupting the subject or object entity of each positive triple, as described in Bordes et al. . In the original HolE publication Nickel, Rosasco, and Poggio , a pairwise margin loss is optimized over each positive and its corrupted negative $(p,s^{\prime},o^{\prime})$:

where $\gamma$ is the margin hyperparameter, and $\sigma$ the standard logistic function. The entity embeddings are also constrained to unit norm : $||e_{i}||_{2}\leq 1$, for all $i\in\mathcal{E}$.

Whereas in Trouillon et al. , the generated negatives are merged into the training set $\mathcal{D}$ at each batch sampling, and the log-likelihood is optimized with $L^{2}$ regularization:

Optimization is conducted with stochastic gradient descent, AdaGrad Duchi, Hazan, and Singer , and early stopping, as described in Trouillon et al. . A single corrupted negative triple is generated for each positive training triple. The results are reported for the best validated models after grid-search on the following values: $K\in\{$10, 20, 50, 100, 150, 200$\}$, $\lambda\in\{$0.1, 0.03, 0.01, 0.003, 0.001, 0.0003, 0.0$\}$ for the log-likelihood loss, and $\gamma\in\{$0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0$\}$ for the max-margin loss. The raw and filtered mean reciprocal ranks (MRR), as well as the filtered hits at 1, 3 and 10 are reported in Table 1.

The margin loss results are consistent with the HolE ones originally reported in Nickel, Rosasco, and Poggio , which confirms the equivalence of the scoring functions, and supports the hypothesis that the loss was responsible for the difference in previously reported results. The log-likelihood results are also coherent, as one must note that the higher scores reported on FB15K in Trouillon et al. are due to the use of more than one generated negative sample for each positive training triple. Here, we generated a single negative sample for each positive one in order to keep the comparison fair between the two losses. The max-margin loss achieves a better raw MRR (rankings without removing the training samples) on both datasets, but much worse filtered metrics on FB15K, suggesting that this loss can be more prone to overfitting.

Scoring Function & Symmetry

The results in Section 3 suggest that the choice of scoring function, i.e., ComplEx or HolE, does not affect the predictive abilities of the model. An additional important question is whether one of the models—in practice—is better suited for modeling certain types of relations. In particular, for symmetric relations, HolE needs to learn embeddings for which the imaginary part after the DFT is close to zero. ComplEx, on the other hand, can learn such representations easily as it operates directly in the complex domain. The question whether this difference in models translates to differences in practice affects the learning of both symmetric and antisymmetric relations. Relations $p\in\mathcal{R}$ are symmetric when triples have the same truth value by permutation of the subject and object entities: $y_{pso}=y_{pos}$ for all $s,o\in\mathcal{E}$, whereas facts of antisymmetric relations $p$ have inverse truth values: $y_{pso}=-y_{pos}$. To evaluate this question experimentally, we reproduced the joint learning of synthetic symmetric and antisymmetric relations described in Trouillon et al. on both scoring functions. We used the log-likelihood loss as all negatives are observed.

We generated randomly a $50\times 50$ symmetric matrix, and a $50\times 50$ antisymmetric matrix. Jointly, they represent a $2\times 50\times 50$ tensor. To ensure that all test values are predictable, the upper triangular parts of the matrices are always kept in the training set, and the diagonals are unobserved. We conducted 5-fold cross-validation on the lower-triangular matrices, using the upper-triangular parts plus 3 folds for training, one fold for validation and one fold for testing. The regularization parameter $\lambda$ is validated among the same values as in the previous experiment.

Figure 1 shows the best cross-validated average precision (area under the precision-recall curve) for the two scoring functions for ranks ranging up to 50. Both models manage to perfectly model symmetry and antisymmetry. As the ComplEx model has twice has many parameters for a given rank, it reaches a perfect average precision with a twice smaller rank. This confirms that the representation of the scoring function does not affect the learning abilities of the models in practice.

Discussion

We have demonstrated that the scoring functions of the HolE and ComplEx models are directly proportional. This hence extends the existence property of the ComplEx model over all knowledge graphs Trouillon et al. to the HolE model. We also showed experimentally that the difference between the reported results of the two models was due to the use of different loss functions, and specifically that the log-likelihood loss can produce a large improvement of predictive performances over the more often used margin loss. We have also shown that Complex and Holographic embeddings can be trained equally well on symmetric and antisymmetric patterns. All these things being equal, an interesting question is then in which settings one of the two models is preferable. Complex embeddings have an advantage in terms of time complexity as they scale linearly with the embedding dimension, whereas Holographic embeddings scale quasilinearly. An advantage of Holographic embeddings however is that the embeddings remain strictly in the real domain, which makes it easier for them to be used in other real-valued machine learning models. In contrast, Complex embeddings can not easily be transformed to real-valued vectors and used without loss of information—i.e. the specific way the real and imaginary parts interact in algebraic operations. Complex-valued models in which Complex embeddings can be directly input are emerging in machine learning Trabelsi et al. ; Danihelka et al. , but this path is yet to be explored for other relational learning problems. Hence, if the task of interest is link prediction, Complex embeddings offer an improved runtime complexity in the order of $O(\log K)$. If the embeddings should be used in further machine learning models, e.g. for entity classification, Holographic embeddings provide better compatibility with existing real-valued methods.

Furthermore, while the choice of the loss is of little consequence on the WN18 dataset, our experiments showed that the log-likelihood loss performed significantly better on FB15K. While much research attention has been given to scoring functions in link prediction, little has been said about the losses, and the max-margin loss has been used in most of the existing work Bordes et al. ; Yang et al. ; Riedel et al. . An interesting direction of future work is therefore a more detailed study of loss functions for knowledge graph embeddings—especially in light of the highly skewed label distribution and the open-world assumption which are characteristic for knowledge graphs but unusual for standard machine learning settings.

Acknowledgments

This work was supported in part by the Association Nationale de la Recherche et de la Technologie through the CIFRE grant 2014/0121.

Appendix A Proof of Equivalence

In this section, we provide the full proof for the equivalence of both models. Note that a similar proof has recently been derived by Hayashi and Shimbo .

First, we derive a property of the DFT on real vectors $x$, showing that the resulting complex vector $\mathcal{F}(x)$ has a partially symmetric structure, for $j\in\{1,\ldots,K-1\}$:

Two special cases arise, the first one is $F(x)_{0}$, which is not concerned by the above symmetry property:

And the second one is $F(x)_{\frac{K}{2}}$ when $K$ is even:

References