{'fraction_non_alphanumeric': 0.047452567073889305, 'fraction_numerical': 0.015319951290411282, 'mean_word_length': 4.037198258804907, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Multi-Relational Link Prediction with Bilinear Models

We study bilinear embedding models for the task of multi-relational link prediction and knowledge graph completion. Bilinear models belong to the most basic models for this task, they are comparably efficient to train and use, and they can provide good prediction performance. The main goal of this paper is to explore the expressiveness of and the connections between various bilinear models proposed in the literature. In particular, a substantial number of models can be represented as bilinear models with certain additional constraints enforced on the embeddings. We explore whether or not these constraints lead to universal models, which can in principle represent every set of relations, and whether or not there are subsumption relationships between various models. We report results of an independent experimental study that evaluates recent bilinear models in a common experimental setup. Finally, we provide evidence that relation-level ensembles of multiple bilinear models can achieve state-of-the art prediction performance.


Introduction
Multi-relational link prediction is the task of predicting missing links in an edge-labeled graph. We focus and use the terminology of knowledge base completion throughout. Largescale knowledge bases (KB) such as DBPedia (Lehmann et al. 2015) or YAGO (Rebele et al. 2016) contain millions of entities and facts, but they are nevertheless far from being complete . Given a set of entities (vertices) and relations (edge labels) that hold between these entities, the goal of multi-relational link prediction (Bordes et al. 2013) is to determine whether or not some entity e 1 links to some entity e 2 via a relation R, i.e., whether the fact R(e 1 , e 2 ) is true.
Embedding models have recently received considerable attention for knowledge base completion tasks (Bordes et al. 2013;Nickel, Rosasco, and Poggio 2016;Trouillon et al. 2016a). Such models embed both entities and relations in a low-dimensional latent space such that the structure of the knowledge base is (largely) maintained. The embeddings are subsequently used to predict missing facts or to detect erroneous facts.
The perhaps most basic class of embedding models is given by bilinear models. Such models predict a "score" for each fact R(e 1 , e 2 ) by computing a weighted sum-where the weights depend on R-of the pairwise interactions of the entity embeddings of e 1 and e 2 . The scores are used to rank (pairs of) entities according to their predicted truthfulness. Bilinear models are comparably efficient to train and use and they can provide good prediction performance (Trouillon and Nickel 2017).
A large number of bilinear models has been proposed in the literature, including RESCAL (Nickel, Tresp, and Kriegel 2011), TransE (Bordes et al. 2013), DIST-MULT (Yang et al. 2014), HolE (Nickel, Rosasco, and Poggio 2016), and ComplEx (Trouillon et al. 2016a). There is, however, little work on the expressiveness of and the connections between various bilinear models. In this paper, we argue that all of the aforementioned models can be seen as bilinear models subject to certain constraints. We study whether and under which conditions each model is universal in that it can represent every possible set of relation instances (or, more precisely, entity rankings). We also explore the size of the embeddings needed for universality and derive upper bounds for the embedding size needed to obtain embeddings consistent with a given dataset. We establish a number of subsumption relationships between various models by giving explicit constructions on how to transform instances of one model to instances of another model (sometimes with a different embedding size). A summary of our results is given in Tab. 1.
We report on an independent experimental study that compared various bilinear models on standard datasets in a common experimental setup. We found that the relative performance among the models is highly relation-dependent. We thus propose a simple relation-level ensemble of multiple bilinear models, which-according to our experimentssignificantly and consistently improved prediction performance over individual models. In fact, we found that the ensemble performed competitively to the state-of-the-art embedding approaches, whether or not they are bilinear.

Multi-Relational Link Prediction
Let E and R be a set of entities and relation names. A knowledge base K ⊆ E × R × E is a collection of triples (i, k, j) where i, j, and k refer to subject, object and relation, resp. We denote by K = |R| ≥ 1 and N = |E| ≥ 2 the number of entities and relations, resp. We represent knowledge base K via a binary tensor X ∈ {0, 1} N ×N ×K , where x ijk = 1 if and only if (i, k, j) ∈ K. By convention, vectors a i refer to rows of matrix A (as a column vector) and scalars a ij to individual entries. Given dimensionalities r and r ′ , we denote by e i,r the i-th standard basis vector, by 0 r the zero vector, and by 0 r×r ′ the zero matrix of the respective shape. Finally, let diag (·) refer to a block-diagonal matrix built from the arguments (a vector or a list of matrices).

Preliminaries
A score-based ranking model is a model m that associates a score s m k (i, j) ∈ R with each subject-relation-object triple. Denote by S m k ∈ R N ×N the corresponding scoring matrix for relation k, i.e., [S m k ] ij = s m k (i, j). Denote by S m ∈ R N ×N ×K the scoring tensor of m, i.e., the tensor with frontal slices S m (k) = S m k . We are ultimately interested in rankings, not in scores. In particular, score-based models are used to rank (pairs of) entities by their predicted truthfulness, given a query of form R(i, ?), R(?, j), or R(?, ?). Generally, a result with a higher score is considered more likely to be correct. We say that an N × N matrix is a ranking matrix if all its entries are in 1, 2, . . . , N 2 and whenever there is any entry with value s > 1, there is at least one other entry with value s − 1. Denote by π(S) the unique ranking matrix associated with scoring matrix S, where π ij (S) def = [π(S)] ij is the dense rank of s ij in the multiset of the entries of S. For every pair of tuples In a slight abuse of notation, we overload π to also apply to tensors, sets of matrices, and sets of tensors. In particular, the ranking tensor π(S) for a score tensor S is the N × N × K tensor produced from S by replacing every frontal slice S (k) with π(S (k) ). Moreover, for any set X, set π(X) = { π(x) : x ∈ X }. Observe that π(R N ×N ) corresponds to the set of all possible ranking matrices, π(R N ×N ×K ) to all possible ranking tensors, and that π(−P ) = P for any ranking matrix (or ranking tensor) P .

Bilinear Models
Bilinear models are models whose scoring function s k (i, j) has form a T i R k a j , where a i , a j ∈ R r and R k ∈ R r×r are model parameters and are referred to as the embeddings of entities i and j as well as relation k, resp. We refer to r ∈ N as the size of the model.
In this paper, we consider bilinear models as well as models that can be represented as bilinear models with an at most linear increase in model size. Although some of the model considered here may not "look" bilinear at first glance, we show that they are closely related to bilinear models. We denote throughout the set of all models of type t (and of size r) and by M t (M t r ).
RESCAL (Nickel, Tresp, and Kriegel 2011). An unconstrained bilinear model. Each model m ∈ M RESCAL r is parameterized by an entity matrix A ∈ R N ×r and K relation matrices R 1 , . . . , R K ∈ R r×r . We have s m k (i, j) = a T i R k a j . RESCAL can be seen as an extension of the low-rank matrix factorization methods prominent in recommender systems to more then one relation.
DISTMULT (Yang et al. 2014). Each model m ∈ M DISTMULT r is parameterized by an entity matrix A ∈ R N ×r and a relation matrix R ∈ R K×r . We have DISTMULT can be seen as a variant of RESCAL that puts a diagonality constraint on the relation matrices. Due to this constraint, it can only model symmetric relations. The model is equivalent to the INDSCAL tensor decomposition (Carroll and Chang 1970).
HolE (Nickel, Rosasco, and Poggio 2016). Each model m ∈ M HolE r is parameterized by an entity matrix A ∈ R N ×r and a relation matrix R ∈ R K×r . We have , where ⋆ refers to the circular correlation between a i and a j , i.e., (a i ⋆ a j ) k = r t=1 a it a j((k+t−2 mod r)+1) . The idea of using circular convolution relates to associative memory (Nickel, Rosasco, and Poggio 2016). Hayashi and Shimbo (2017) provide an alternative viewpoint in terms of ComplEx, discussed next.
ComplEx (Trouillon et al. 2016a). Each model m ∈ M ComplEx r is parameterized by an entity matrix A ∈ C N ×r and a relation matrix R ∈ C N ×r . We have , where Re(·) extracts the real part of a complex number. ComplEx is superficially related to DISTMULT but uses complex-valued parameter matrices. Note that a T i diag (r k ) a j is not guaranteed to be real. TransE (Bordes et al. 2013). Each model m ∈ M TransE r is parameterized by an entity matrix A ∈ R N ×r and an relation matrix R ∈ R K×r . We have 1 . In contrast to the models presented above, TransE is a translation-based model, not a factorization-based model. The use of translations-i.e., differences between entity embeddings-is inspired by Word2Vec's word analogy results (Mikolov et al. 2013). Note that TransE can also be used with L 1 norm instead of L 2 ; we focus on the L 2 variant given above throughout.

Subsumption and Expressiveness
For a given class M t r of models, denote by M t r = { S m : m ∈ M t r } the set of scoring tensors that the model class can represent. Let M t = ∪ r∈N + M t r . Note that π(M t r ) and π(M t ) denote the set of ranking tensors that can be represented by M t r and M t , respectively.

Subsumption
We first explore subsumption relationships between different model classes as well as the the size of the entity representations needed for a subsumption to hold. We assume throughout that the number N ≥ 2 of entities and the number K ≥ 1 of relations are arbitrary but fixed. We say that class M t2 subsumes class M t1 whenever π(M t1 ) ⊆ π(M t2 ). In other words, M t2 is at least as expressive in terms of rankings as M t1 . If π(M t1 ) ⊂ π(M t2 ), we say that M t2 strictly subsumes M t1 , indicating that M t2 is strictly more expressive than M t1 . Note that it is good when M t2 is more expressive than M t1 because M t2 can in principle express more rankings. It can also be problematic, however, because efficient training and the avoidance of overfitting become more challenging.
We first show subsumption by specifying an explicit model transformation, then strictness via a counterexample.
Proof. Fix some r ∈ N + . Pick any TransE model m T ∈ M TransE r , denote by A ∈ R N ×r and R ∈ R K×r the corresponding parameter matrices, and by S mT the scoring tensor. We show that π(S mT ) ∈ π(M RESCAL 2r+1 ). We do this by explicitly constructing a corresponding RESCAL model m R ∈ M RESCAL 2r+1 by specifying its parameters A ′ ∈ R N ×(2r+1) and R ′ k ∈ R (2r+1)×(2r+1) . Setting we can now verify 2 that , which implies that m T and m R agree on the ranking for each relation, i.e., π(S mT ) = π(S mR ). Since m R ∈ M RESCAL 2r+1 , we obtain π(S mT ) ∈ π(M RESCAL 2r+1 ) as claimed. The proof above shows that TransE can be viewed as a bilinear model with the constraints specified in Eq. (1).
Theorem 2. M TransE does not subsume M RESCAL r for any r ≥ 2.
2 A more detailed derivation can be found in the online appendix.
Note that the theorem implies that there are RESCAL models with r = 2 that cannot be expressed with any TransE model, no matter how large its size.
Nickel, Rosasco, and Poggio (2016) argued that HolE can be viewed as a compressed version of RESCAL and implicitly established the subsumption relationship to RESCAL. We present their argument formally below. Proof. From the definition of HolE, we rewrite Recently, Hayashi and Shimbo (2017)

Universality
We say that class M t is universal if π(M t ) = π(R N ×N ×K ), i.e., any ranking tensor can be expressed. As with subsumption, universality does by no means imply that a model class is suitable for use in practice. If a model class is not universal, however, care must be taken because certain relations cannot be modeled.
A direct consequence of Th. 2 is: We establish the universality of RESCAL, HolE, and ComplEx next.
Proof. Pick any ranking tensor P ∈ π(R N ×N ×K ). Consider the model m ∈ M RESCAL N with parameterization A = I N and R k = −P (k) . Then S m k = AR k A T = −P (k) and thus S m = −P. Using the fact that π(−P) = P, we conclude that P ∈ π(M RESCAL N ).
Note that models in M RESCAL N have very large embeddings. It is more involved to establish whether or not M RESCAL r is universal for some r < N . We approach this question below and show that r needs to be linear in N to obtain universality.
Theorem 6. M RESCAL ⌊N/32−1⌋ is not universal. The proof (given below) makes use of the notion of rounding rank (Neumann, Gemulla, and Miettinen 2016). Given a rounding threshold τ ∈ R, denote by the rounding function. We apply round τ to matrices and tensors by rounding element-wise. In particular, when A ∈ R m×n is any real-valued matrix, then round τ (A) is the m × n binary matrix with [round τ (A)] ij = round τ (a ij ). We assume τ = 1/2 unless explicitly stated otherwise and write round for round 1/2 .
Definition 1. For τ ∈ R, the rounding rank w.r.t. τ of a binary matrix B ∈ { 0, 1 } m×n is given by Given a Boolean matrix B, say that a scoring matrix S is The rounding rank can be interpreted as the minimum rank of a scoring matrix that is consistent with B. Neumann, Gemulla, and Miettinen (2016) proved that the rounding rank differs by at most 1 for different choices of τ and that it is connected to the sign rank (Alon, Moran, and Yehudayoff 2016). The rounding rank can be much smaller than the matrix rank in practice, which partially explains the the success of bilinear models.
Proof (of Th. 6). Alon, Frankl, and Rödl (1985) showed that there exist Boolean matrices in { 0, 1 } N ×N with rounding rank at least N/32 for every N . Pick any such matrix B. The proof is by contradiction. Consider K = 1 and suppose there exists a scoring matrix S ∈ M RESCAL ⌊N/32−1⌋ that satisfies Eq. (2). Observe that S has rank at most ⌊N/32 − 1⌋ because it is defined by a product involving a ⌊N/32 − 1⌋ × ⌊N/32 − 1⌋ matrix. But this implies that rrank(B) ≤ N/32 − 1, a contradiction.
Note that the proof implies that there exists ranking tensors with just two distinct ranks that cannot be expressed by M RESCAL ⌊N/32−1⌋ . Since RESCAL is an unconstrained bilinear model, we can generalize to other model classes.  Finally, since DISTMULT's relation matrix is diagonal and thus symmetric, DISTMULT cannot model asymmetric relations.
Theorem 8. M DISTMULT is not universal.

Consistent Ranking
Suppose we are given an N × N × K Boolean tensor B and we look for a ranking tensor P that is consistent with B in each frontal slice, i.e., p ijk < p i ′ j ′ k whenever b ijk = 1 and b i ′ j ′ k = 0. In this section, we establish upper bounds on the size 3 that various bilinear models need to express a ranking that is consistent with B, i.e., which ranks 1s above 0s. Here we think of B as the correct completed KB; there is no hope for a model class not consistent with B to recover the correct KB.
Note that even if a model class is not universal, it may still contain consistent models for all Boolean tensors. This is not the case for DISTMULT and TransE, however. In particular, since DISTMULT produces symmetric scoring matrices, DISTMULT does not contain models consistent with any Boolean tensor that has an asymmetric frontal slice. For TransE, the proof of Th. 2 implies that TransE does not contain models for Boolean tensors with both 0s and 1s on the main diagonal of any of its frontal slices.
Theorem 9. There exists Boolean tensors B such that no ranking tensor in π(M DISTMULT ) is consistent with B. Theorem 10. There exists Boolean tensors B such that no ranking tensor in π(M TransE ) is consistent with B.
For RESCAL, which is universal, we can make use of the rounding-rank decomposition to obtain a tighter bound than the one implied by its universality.
Theorem 11. For any boolean tensor B, π(M RESCAL r ) contains a ranking tensor consistent with B if Proof. The case r ≥ N follows from Th. 6. Denote by r k the rounding rank of slice B k of B; we explicitly construct a consistent RESCAL model with r = 2 k r k (as asserted). To do so, pick any L k , Q k ∈ R N ×r k that form a rounding-rank decomposition of B k , i.e., for which B k = round(L k Q T k ). (By the definition of rounding rank, such matrices always exist.) Now set We can now verify that round(AR k A T ) = B k , which implies consistency.
Theorem 12. For any Boolean tensor B, π(M ComplEx r ) contains a ranking tensor consistent with B if Proof. The case r ≥ KN follows directly from Th. 7. To obtain r ≥ 2 K k=1 rrank(B k ), define r k , L k , and Q k as in the proof of Th. 11, and set S k = L k Q T k . Then there exist matrices A k ∈ C N ×2r k and D k ∈ C 2r k ×2r k , with D k being diagonal, such that (0 2r1×2r1 , . . . , D k , . . . , 0 2rK ×2rK ) and observe that S k = Re(AR k A * ).
As a corollary of the above theorem, we have:

Training and Relation-Level Ensemble
We have seen that various prior models can be interpreted as a bilinear models subject to certain constraints. In other words, they are diverse with respect to their expressivity. So far, we did not touch on how to select a suitable model for a given dataset and from a given model class. In this section, we briefly discuss model training in a margin-based framework. We then propose a simple relation-level ensemble that combines multiple individual models. The rationale behind using an ensemble is that whether a model class can represent well or be trained well on a relation depends on properties of that relation. The ensemble thus aims to pick the best model (or a combination of models) for each relation.

Margin-Based Training
We assume throughout that we are given a set of positive triples T + ⊂ E × R × E, but no negative evidence. This is a common scenario in practice. To deal with the absence of negative evidence, ranking-based frameworks aim to produce a model that ranks triples in T + higher than other triples. A common approach (Bordes et al. 2013;Nickel, Rosasco, and Poggio 2016) is to define a set of "negative" triples for each positive triple (i, k, j) ∈ T + by perturbing subject or object: This approach corresponds to a local closed-world assumption (Dong et al. 2014). We now briefly summarize a common margin-based framework for training (Bordes et al. 2013). There are a number of alternatives, including logistic loss (Riedel et al. 2013) and negative log-likelihood (Trouillon et al. 2016a). Margin-based frameworks often lead to faster training times in practice because they focus on "informative" pairs of positive and negative triples, i.e., they ignore parts of the data that are already more or less wellrepresented by the model. In particular, we minimize where 0 ≤ γ ∈ R + is a margin hyperparameter, [x] + = max(0, x), and f depends on the model being trained. For all models but HolE, we set f (i, k, j) = s m k (i, j). For HolE, we set f (i, k, j) = σ(s m k (i, j)), where σ denotes the logistic function, as suggested by the authors. In our experimental study, we also consider an additional L 2 regularization term over the model parameters. The models can be fit using stochastic gradient descent (SGD) as in (Bordes et al. 2013;Lin et al. 2015b). The computational cost per SGD step of RESCAL is O(r 2 ), of HolE O(r log n), and of all other models O(r).

Relation-Level Ensemble
The simplest way of combining multiple models is to construct an ensemble at the model level (Krompaß and Tresp  Test  WN18  40,943  18 141,442  5,000  5,000  FB15K 14,951 1,345 483,142  50,000 59,071 2015). Our experimental study suggests that the relative performance of different models is relation-dependent, however. A more promising approach is therefore to combine models at the relation level. To the best of our knowledge, this simple approach has not been explored previously. Our ensemble is based on stacking. A meta learner is used to combine the ranking matrices produced by the individual models such that some accuracy measure is maximized. Here we use logistic regression. To do so, we construct for each relation a dataset that contains all of its positive triples as well as an equal amount of negative triples obtained by randomly perturbing each positive triple following the same strategy as in training individual models. For logistic regression, we use rescaled scores of the individual models as features and the positive/negative class label as response variable. Rescaling accounts for the variety in range of scores of different models; we rescale each feature linearly into range

Experiments
We conducted an experimental study on two real-world datasets, which are commonly used in prior work on KB completion. The primary goal of our study was to provide independent evidence for the performance of various bilinear models under the margin-based ranking framework. We also evaluated relation-level ensembles of such models and compared the results to prior results reported in the literature (for bilinear and other models).

Experimental Setup
All datasets, experimental results, and source code will be made publicly available.
Data. We used the WN18 (Bordes et al. 2014) and FB15K (Bordes et al. 2013) datasets, which were extracted from WordNet (Miller 1995) and Freebase (Bollacker et al. 2008), respectively. WordNet contains words and their relationships. Freebase contains various facts across a large number of relations. The two datasets are presplit into a training set, a validation set, and a test set. Table 2 summarizes the key statistics.
Methods and training. We considered RESCAL (R), HolE (H), and TransE (T) in our experimental study. We reimplemented each method in C++, partly using the Intel Math Kernel Library. We trained each model in the marginbased ranking framework using Adagrad (Duchi, Hazan, and Singer 2011). In each step, we sampled a positive triple at random and obtained a negative triple by randomly perturbing subject or object. Sampling was done without replacement and we did not use mini-batches. When using the same hyperparameters, our implementation provided similar or better fits than the original implementations provided by the authors. Note that our study was limited in that we considered only one particular training method; no conclusions can be drawn about other training methods. We focused on margin-based ranking because it led to much faster training times, making this study more feasible. We used LIBLIN-EAR for logistic regression.
Evaluation. We evaluated model performance for the tasks of entity ranking and triple classification on the test data. In entity ranking, we rank entities for queries of the form R(?, e) or R(e, ?). Our evaluation closely follows Bordes et al. (2013), and we report mean reciprocal rank (MRR), HITS@10, and mean rank (MR) in the filtered setting, i.e., predictions that correspond to tuples in the training or validation datasets were discarded. In triple classification, we are given a triple (i, k, j) and are asked to classify it as positive or negative; we proceed as Socher et al. (2013) to produce the set of tuples to classify. To perform classification, we determined a score threshold σ k for each relation and model; scores larger than σ k were classified positive, else negative. We used optimal thresholds with respect to the validation set.

Results
Entity ranking. Our results are summarized in Tab. 4. Detailed results can be found in Tab. 6, where we measured HITS@10 per relation category and per argument to be predicted as in (Bordes et al. 2013).
For the individual models, our results indicate that model performance depends on the relation category. No single model always performed best across all categories. HolE   and TransE generally performed better than RESCAL; here constraints help. The relation-level ensembles generally improved performance w.r.t. HITS@10 and MRR. Performance of MR was not improved, however, mainly because this metric is sensitive to low-ranked triples (which existed in HolE and RESCAL predictions). Note that adding RESCAL to the ensemble was helpful. Finally, the ensemble of RESCAL, TransE, and HolE performed best w.r.t. HITS@10 on all relation categories and for both datasets.
In Tab. 5, we compare to some recent results reported in the literature. Note that training methods were different than the one used in our study for some of these models, and that some models are not bilinear. Nevertheless, a direct comparison indicates that a relation-level ensemble of multiple bilinear models is competitive to the state-of-the-art.
Triple classification. Tab. 7 summarizes the HITS@10 performance of each individual model and various relationlevel ensembles for triple classification on FB15k. The results are generally in line with the results for entity ranking. A notable exception is that RESCAL outperforms HolE here; we conjecture that this is due to HolE's high MR on this dataset.