On Multi-Relational Link Prediction with Bilinear Models

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. Large-scale knowledge bases (KB) such as DBPedia (?) or YAGO (?) 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 (?) 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 (?; ?; ?). 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 (?).

A large number of bilinear models has been proposed in the literature, including RESCAL (?), TransE (?), DISTMULT (?), HolE (?), and ComplEx (?). 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. 3.

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 experiments—significantly 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 $\mathcal{E}$ and $\mathcal{R}$ be a set of entities and relation names. A knowledge base $\mathcal{K}\subseteq\mathcal{E}\times\mathcal{R}\times\mathcal{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=\lvert\mathcal{R}\rvert\geq 1$ and $N=\lvert\mathcal{E}\rvert\geq 2$ the number of entities and relations, resp. We represent knowledge base $\mathcal{K}$ via a binary tensor $\mathbfcal{X}\in\{0,1\}^{N\times N\times K}$, where $x_{ijk}=1$ if and only if $(i,k,j)\in\mathcal{K}$. By convention, vectors ${\boldsymbol{a}}_{i}$ refer to rows of matrix ${\boldsymbol{A}}$ (as a column vector) and scalars $a_{ij}$ to individual entries. Given dimensionalities $r$ and $r^{\prime}$, we denote by ${\boldsymbol{e}}_{i,r}$ the $i$-th standard basis vector, by ${\boldsymbol{0}}_{r}$ the zero vector, and by ${\boldsymbol{0}}_{r\times r^{\prime}}$ the zero matrix of the respective shape. Finally, let $\operatorname{diag}\left(\cdot\right)$ refer to a block-diagonal matrix built from the arguments (a vector or a list of matrices).

2 Bilinear Models

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 can be seen as an extension of the low-rank matrix factorization methods prominent in recommender systems to more then one relation.

DISTMULT (?).

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 (?).

HolE (?).

where $\star$ refers to the circular correlation between ${\boldsymbol{a}}_{i}$ and ${\boldsymbol{a}}_{j}$, i.e., $({\boldsymbol{a}}_{i}\star{\boldsymbol{a}}_{j})_{k}=\sum_{t=1}^{r}a_{it}a_{j((k+t-2\mod r)+1)}$. The idea of using circular convolution relates to associative memory (?). ? (?) provide an alternative viewpoint in terms of ComplEx, discussed next.

ComplEx (?).

where $\operatorname{Re}(\cdot)$ extracts the real part of a complex number. ComplEx is superficially related to DISTMULT but uses complex-valued parameter matrices. Note that ${\boldsymbol{a}}_{i}^{T}\operatorname{diag}\left({\boldsymbol{r}}_{k}\right){\boldsymbol{a}}_{j}$ is not guaranteed to be real.

TransE (?).

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 (?). 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