Analogical Inference for Multi-Relational Embeddings

Introduction

Multi-relational embedding, or knowledge graph embedding, is the task of finding the latent representations of entities and relations for better inference over knowledge graphs. This problem has become increasingly important in recent machine learning due to the broad range of important applications of large-scale knowledge bases, such as Freebase (Bollacker et al., 2008), DBpedia (Auer et al., 2007) and Google’s Knowledge Graph (Singhal, 2012), including question-answering (Ferrucci et al., 2010), information retrieval (Dalton et al., 2014) and natural language processing (Gabrilovich & Markovitch, 2009).

A knowledge base (KB) typically stores factual information as subject-relation-object triplets. The collection of such triplets forms a directed graph whose nodes are entities and whose edges are the relations among entities. Real-world knowledge graph is both extremely large and highly incomplete by nature (Min et al., 2013). How can we use the observed triplets in an incomplete graph to induce the unobserved triples in the graph presents a tough challenge for machine learning research.

Various statistical relational learning methods (Getoor, 2007; Nickel et al., 2015) have been proposed for this task, among which vector-space embedding models are most particular due to their advantageous performance and scalability (Bordes et al., 2013). The key idea in those approaches is to find dimensionality reduced representations for both the entities and the relations, and hence force the models to generalize during the course of compression. Representative models of this kind include tensor factorization (Singhal, 2012; Nickel et al., 2011), neural tensor networks (Socher et al., 2013; Chen et al., 2013), translation-based models (Bordes et al., 2013; Wang et al., 2014; Lin et al., 2015b), bilinear models and its variants (Yang et al., 2014; Trouillon et al., 2016), pathwise methods (Guu et al., 2015), embeddings based on holographic representations (Nickel et al., 2016), and product graphs that utilizes additional site information for the predictions of unseen edges in a semi-supervised manner (Liu & Yang, 2015, 2016). Learning the embeddings of entities and relations can be viewed as a knowledge induction process, as those induced latent representations can be used to make inference about new triplets that have not been seen before.

Despite the substantial efforts and great successes so far in the research on multi-relational embedding, one important aspect is missing, i.e., to study the solutions of the problem from the analogical inference point of view, by which we mean to rigorously define the desirable analogical properties for multi-relational embedding of entities and relations, and to provide algorithmic solution for optimizing the embeddings w.r.t. the analogical properties. We argue that analogical inference is particularly desirable for knowledge base completion, since for instance if system $A$ (a subset of entities and relations) is analogous to system $B$ (another subset of entities and relations), then the unobserved triples in $B$ could be inferred by mirroring their counterparts in $A$. Figure 1 uses a toy example to illustrate the intuition, where system $A$ corresponds to the solar system with three concepts (entities), and system $B$ corresponds the atom system with another three concepts. An analogy exists between the two systems because $B$ is a “miniature” of $A$. As a result, knowing how the entities are related to each other in system $A$ allows us to make inference about how the entities are related to each other in system $B$ by analogy.

Although analogical reasoning was an active research topic in classic AI (artificial intelligence), early computational models mainly focused on non-differentiable rule-based reasoning (Gentner, 1983; Falkenhainer et al., 1989; Turney, 2008), which can hardly scale to very large KBs such as Freebase or Google’s Knowledge Graph. How to leverage the intuition of analogical reasoning via statistical inference for automated embedding of very large knowledge graphs has not been studied so far, to our knowledge.

It is worth mentioning that analogical structures have been observed in the output of several word/entity embedding models (Mikolov et al., 2013; Pennington et al., 2014). However, those observations stopped there as merely empirical observations. Can we mathematically formulate the desirable analogical structures and leverage them in our objective functions to improve multi-relational embedding? In this case, can we develop new algorithms for tractable inference for the embedding of very large knowledge graphs? These questions present a fundamental challenge which has not been addressed by existing work, and answering these questions are the main contributions we aim in this paper. We name this open challenge as the analogical inference problem, for the distinction from rule-based analogical reasoning in classic AI.

Our specific novel contributions are the following:

A new framework that, for the first time, explicitly models analogical structures in multi-relational embedding, and that improves the state-of-the-art performance on benchmark datasets;

The algorithmic solution for conducting analogical inference in a differentiable manner, whose implementation is as scalable as the fastest known relational embedding algorithms;

The theoretical insights on how our framework provides a unified view of several representative methods as its special (and restricted) cases, and why the generalization of such cases lead to the advantageous performance of our method as empirically observed.

The rest of this paper is organized as follows: §2 introduces related background where multi-relational embedding is formulated as linear maps. §3 describes our new optimization framework where the desirable analogical structures are rigorously defined by the the commutative property of linear maps. §4 offers an efficient algorithm for scalable inference by exploiting the special structures of commutative linear maps, §5 shows how our framework subsumes several representative approaches in a principled way, and §6 reports our experimental results, followed by the concluding remarks in §7.

Related Background

2 Relations as Linear Maps

We formulate each relation $r$ as a linear map that, for any given $(s,r,o)\in\mathcal{K}$, transforms the subject $s$ from its original position in the vector space to somewhere near the object $o$. In other words, we expect the latent representations for any valid $(s,r,o)$ to satisfy

The degree of satisfaction in the approximated form of (1) can be quantified using the inner product of $v_{s}^{\top}W_{r}$ and $v_{o}$. That is, we define a bilinear score function as:

Our goal is to learn $v$ and $W$ such that $\phi(s,r,o)$ gives high scores to valid triples, and low scores to the invalid ones. In contrast to some previous models (Bordes et al., 2013) where relations are modeled as additive translating operators, namely $v_{s}+w_{r}\approx v_{o}$, the multiplicative formulation in (1) offers a natural analogy to the first-order logic where each relation is treated as a predicate operator over input arguments (subject and object in our case). Clearly, the linear transformation defined by a matrix, a.k.a. a linear map, is a richer operator than the additive transformation defined by a vector. Multiplicative models are also found to substantially outperform additive models empirically (Nickel et al., 2011; Yang et al., 2014).

3 Normal Transformations

Instead of allowing arbitrary linear maps to be used for representing relations, a particular family of matrices has been studied for “well-behaved” linear maps. This family is named as the normal matrices.

A real matrix $A$ is normal if and only if $A^{\top}A=AA^{\top}$.

Normal matrices have nice theoretical properties which are often desirable form relational modeling, e.g., they are unitarily diagonalizable and hence can be conveniently analyzed by the spectral theorem (Dunford et al., 1971). Representative members of the normal family include:

Symmetric Matrices for which $W_{r}W_{r}^{\top}=W_{r}^{\top}W_{r}=W_{r}^{2}$. These includes all diagonal matrices and positive semi-definite matrices, and the symmetry implies $\phi(s,r,o)=\phi(o,r,s)$. They are suitable for modeling symmetric relations such as $is\_identical$.

Skew-/Anti-symmetric Matrices for which $W_{r}W_{r}^{\top}=W_{r}^{\top}W_{r}=-W_{r}^{2}$, which implies $\phi(s,r,o)=-\phi(o,r,s)$. These matrices are suitable for modeling asymmetric relations such as $is\_parent\_of$.

Rotation Matrices for which $W_{r}W_{r}^{\top}=W_{r}^{\top}W_{r}=I_{m}$, which suggests that the relation $r$ is invertible as $W_{r}^{-1}$ always exists. Rotation matrices are suitable for modeling 1-to-1 relationships (bijections).

Circulant Matrices (Gray et al., 2006), which have been implicitly used in recent work on holographic representations (Nickel et al., 2016). These matrices are usually related to the learning of latent representations in the Fourier domain (see §5 for more details).

Proposed Analogical Inference Framework

Analogical reasoning is known to play a central role in human induction about knowledge (Gentner, 1983; Minsky, 1988; Holyoak et al., 1996; Hofstadter, 2001). Here we provide a mathematical formulation of the analogical structures of interest in multi-relational embedding in a latent semantic space, to support algorithmic inference about the embeddings of entities and relations in a knowledge graph.

Consider the famous example in the word embedding literature (Mikolov et al., 2013; Pennington et al., 2014), for the following entities and relations among them:

“$man$ is to $king$ as $woman$ is to $queen$”

In an abstract notion we denote the entities by $a$ (as $man$) , $b$ (as $king$), $c$ (as $woman$) and $d$ (as $queen$), and the relations by $r$ (as $crown$) and $r^{\prime}$ (as $male\mapsto female$), respectively. These give us the subject-relation-object triplets as follows:

For multi-relational embeddings, $r$ and $r^{\prime}$ are members of $\mathcal{R}$ and are modeled as linear maps in our case.

The relational maps in (3) can be visualized using a commutative diagram (Adámek et al., 2004; Brown & Porter, 2006) from the Category Theory, as shown in Figure 2, where each node denotes an entity and each edge denotes a linear map that transforms one entity to the other. We also refer to such a diagram as a “parallelogram” to highlight its particular algebraic structureNotice that this is different from parallelograms in the geometric sense because each edge here is a linear map instead of the difference between two nodes in the vector space..

The parallelogram in Figure 2 represents a very basic analogical structure which could be informative for the inference about unknown facts (triplets). To get a sense about why analogies would help in the inference about unobserved facts, we notice that for entities $a,b,c,d$ which form an analogical structure in our example, the parallelogram structure is fully determined by symmetry. This means that if we know $a\stackrel{{\scriptstyle r}}{{\rightarrow}}b$ and $a\stackrel{{\scriptstyle r^{\prime}}}{{\rightarrow}}c$, then we can induce the remaining triplets of $c\stackrel{{\scriptstyle r}}{{\rightarrow}}d$ and $b\stackrel{{\scriptstyle r^{\prime}}}{{\rightarrow}}d$. In other words, understanding the relation between $man$ and $king$ helps us to fill up the unknown relation between $woman$ and $queen$.

Analogical structures are not limited to parallelograms, of course, though parallelograms often serve as the building blocks for more complex analogical structures. As an example, in Figure 1 of §1 we show a compound analogical structure in the form of a triangular prism, for mirroring the correspondent entities/relations between the atom system and the solar system. Formally define the desirable analogical structures in a computationally tractable objective for optimization is the key for solving our problem, which we will introduce next.

2 Commutative Constraint for Linear Maps

Although it is tempting to explore all potentially interesting parallelograms in the modeling of analogical structure, it is computationally intractable to examine the entire powerset of entities as the candidate space of analogical structures. A more reasonable strategy is to identify some desirable properties of the analogical structures we want to model, and use those properties as constraints for reducing the candidate space.

An desirable property of the linear maps we want is that all the directed paths with the same starting node and end node form the compositional equivalence. Denoting by “$\circ$” the composition operator between two relations, the parallelogram in Figure 2 contains two equivalent compositions as:

which means that $a$ is connected to $d$ via either path. We call this the commutativity property of the linear maps, which is a necessary condition for forming commutative parallelograms and therefore the corresponding analogical structures. Yet another example is given by Figure 1, where $sun$ can traverse to $charge$ along multiple alternative paths of length three, implying the commutativity of relations $surrounded\_by$, $made\_of$, $scale\_down$.

The composition of two relations (linear maps) is naturally implemented via matrix multiplication (Yang et al., 2014; Guu et al., 2015), hence equation (4) indicates

One may further require the commutative constraint (5) to be satisfied for any pair of relations in $\mathcal{R}$ because they may be simultaneously present in the same commutative parallelogram for certain subsets of entities. In this case, we say the relations in $\mathcal{R}$ form a commuting family.

3 The Optimization Objective

The generic goal for multi-relational embedding is to find entity and relation representations such that positive triples labeled as $y=+1$ receive higher score than the negative triples labeled as $y=-1$. This can be formulated as

To impose analogical structures among the representations, we in addition require the linear maps associated with relations to form a commuting family of normal matrices. This gives us the objective function for ANALOGY:

where constraints (8) and (9) are corresponding to the normality and commutativity requirements, respectively. Such a constrained optimization may appear to be computationally expensive at the first glance. In §4, however, we will recast it as a simple lightweight problem for which each SGD update can be carried out efficiently in $O(m)$ time.

Efficient Inference Algorithm

The constrained optimization (7) is computationally challenging due to the large number of model parameters in tensor $W$, the matrix normality constraints, and the quadratic number of pairwise commutative constraints in (9).

Interestingly, by exploiting the special properties of commuting normal matrices, we will show in Corollary 4.2.1 that ANALOGY can be alternatively solved via an another formulation of substantially lower complexity. Our findings are based on the following lemma and theorem:

(Wilkinson & Wilkinson, 1965) For any real normal matrix $A$, there exists a real orthogonal matrix $Q$ and a block-diagonal matrix $B$ such that $A=QBQ^{\top}$, where each diagonal block of $B$ is either (1) A real scalar, or (2) A 2-dimensional real matrix in the form of $\begin{bmatrix}x&-y\\ y&x\end{bmatrix}$, where both $x$, $y$ are real scalars.

The lemma suggests any real normal matrix can be block-diagonalized into an almost-diagonal canonical form.

If a set of real normal matrices $A_{1},A_{2},...$ form a commuting family, namely $A_{i}A_{j}=A_{j}A_{i}\ \forall i,j$, then they can be block-diagonalized by the same real orthogonal basis $Q$.

The theorem above implies that the set of dense relational matrices $\{W_{r}\}_{r\in\mathcal{R}}$, if mutually commutative, can always be simultaneously block-diagonalized into another set of sparse almost-diagonal matrices $\{B_{r}\}_{r\in\mathcal{R}}$.

For any given solution $(v^{*},W^{*})$ of optimization (7), there always exists an alternative set of embeddings $(u^{*},B^{*})$ such that $\phi_{v^{*},W^{*}}(s,r,o)\equiv\phi_{u^{*},B^{*}}(s,r,o)$, $\forall(s,r,o)$, and $(u^{*},B^{*})$ is given by the solution of:

where $\mathcal{B}^{n}_{m}$ denotes all $m\times m$ almost-diagonal matrices in Lemma 4.1 with $n<m$ real scalars on the diagonal.

With the commutative constraints, there must exist some orthogonal matrix $Q$, such that $W_{r}=QB_{r}Q^{\top}$, $B_{r}\in\mathcal{B}^{n}_{m}$, $\forall r\in\mathcal{R}$. We can plug-in these expressions into optimization (7) and let $u=vQ$, obtaining

In addition, it is not hard to verify that constraints (8) and (9) are automatically satisfied by exploiting the facts that $Q$ is orthogonal and $\mathcal{B}_{m}^{n}$ is a commutative normal family. ∎

Constraints (11) in the alternative optimization problem can be handled by simply binding together the coefficients within each of those $2\times 2$ blocks in $B_{r}$. Note that each $B_{r}$ consists of only $m$ free parameters, allowing the gradient w.r.t. any given triple to be efficiently evaluated in $O(m)$.

Unified View of Representative Methods

In the following we provide a unified view of several embedding models (Yang et al., 2014; Trouillon et al., 2016; Nickel et al., 2016), by showing that they are restricted versions under our framework, hence are implicitly imposing analogical properties. This explains their strong empirical performance as compared to other baselines (§6).

DistMult (Yang et al., 2014) embeds both entities and relations as vectors, and defines the score function as

where $\langle\cdot,\cdot,\cdot\rangle$ denotes the generalized inner product.

DistMult embeddings can be fully recovered by ANALOGY embeddings when $n=m$.

2 Complex Embeddings (ComplEx)

where $\overline{x}$ denotes the complex conjugate of $x$.

ComplEx embeddings of embedding size $m$ can be fully recovered by ANALOGY embeddings of embedding size $2m$ when $n=0$.

Let $\Re(x)$ and $\Im(x)$ be the real and imaginary parts of any complex vector $x$. We recast $\phi$ in (16) as

The corresponding $B_{r}$ is a block-diagonal matrix in $\mathcal{B}^{0}_{2m}$ with its $k$-th block given by $\begin{bmatrix}\Re(v_{r})_{k}&-\Im(v_{r})_{k}\\ \Im(v_{r})_{k}&\Re(v_{r})_{k}\\ \end{bmatrix}$. ∎

3 Holographic Embeddings (HolE)

HolE (Nickel et al., 2016) defines the score function as

where the association of $s$ and $o$ is implemented via circular correlation denoted by $\ast$. This formulation is motivated by the holographic reduced representation (Plate, 2003).

To relate HolE with ANALOGY, we rewrite (24) in a bilinear form with a circulant matrix $C(v_{r})$ in the middle

where entries of a circulant matrix are defined as

It is not hard to verify that circulant matrices are normal and commute (Gray et al., 2006), hence entity analogies are encouraged in HolE, for which optimization (7) reduces to an unconstrained problem as equalities (8) and (9) are automatically satisfied when all $W_{r}$’s are circulant.

The next proposition further reveals that HolE is equivalent to ComplEx with minor relaxation.

HolE embeddings can be equivalently obtained using the following score function

Hence the score function can be further recast as

Let $v_{s}^{\prime}=\overline{\mathfrak{F}(v_{s})},v_{o}^{\prime}=\overline{\mathfrak{F}(v_{o})}$ and $v_{r}^{\prime}=\frac{1}{m}\mathfrak{F}(v_{r})$, we obtain exactly the same score function as used in ComplEx

Experiments

We evaluate ANALOGY and the baselines over two benchmark datasets for multi-relational embedding released by previous work (Bordes et al., 2013), namely a subset of Freebase (FB15K) for generic facts and WordNet (WN18) for lexical relationships between words.

The dataset statistics are summarized in Table 1.

2 Baselines

We compare the performance of ANALOGY against a variety types of multi-relational embedding models developed in recent years. Those models can be categorized as:

Translation-based models where relations are modeled as translation operators in the embedding space, including TransE (Bordes et al., 2013) and its variants TransH (Wang et al., 2014), TransR (Lin et al., 2015b), TransD (Ji et al., 2015), STransE (Nguyen et al., 2016) and RTransE (Garcia-Duran et al., 2015).

Multi-relational latent factor models including LFM (Jenatton et al., 2012) and RESCAL (Nickel et al., 2011) based collective matrix factorization.

Models involving neural network components such as neural tensor networks (Socher et al., 2013) and PTransE-RNN (Lin et al., 2015b), where RNN stands for recurrent neural networks.

Pathwise models including three different variants of PTransE (Lin et al., 2015a) which extend TransE by explicitly taking into account indirect connections (relational paths) between entities.

Models subsumed under our proposed framework (§5), including DistMult (Yang et al., 2014) based simple multiplicative interactions, ComplEx (Trouillon et al., 2016) using complex coefficients and HolE (Nickel et al., 2016) based on holographic representations. Those models are implicitly leveraging analogical structures per our previous analysis.

Models enhanced by external side information. We use Node+LinkFeat (NLF) (Toutanova & Chen, 2015) as a representative example, which leverages textual mentions derived from the ClueWeb corpus.

3 Evaluation Metrics

Following the literature of multi-relational embedding, we use the conventional metrics of Hits@k and Mean Reciprocal Rank (MRR) which evaluate each system-produced ranked list for each test instance and average the scores over all ranked lists for the entire test set of instances.

The two metrics would be flawed for the negative instances created in the test phase as a ranked list may contain some positive instances in the training and validation sets (Bordes et al., 2013). A recommended remedy, which we followed, is to remove all training- and validation-set triples from all ranked lists during testing. We use “filt.” and “raw” to indicate the evaluation metrics with or without filtering, respectively.

In the first set of our experiments, we used on Hits@k with k=10, which has been reported for most methods in the literature. We also provide additional results of ANALOGY and a subset of representative baseline methods using MRR, Hits@1 and Hits@3, to enable the comparison with the methods whose published results are in those metrics.

4 Implementation Details

4.2 Asynchronous AdaGrad

Our C++ implementationCode available at https://github.com/quark0/ANALOGY. runs over a CPU, as ANALOGY only requires lightweight linear algebra routines. We use asynchronous stochastic gradient descent (SGD) for optimization, where the gradients with respect to different mini-batches are simultaneously evaluated in multiple threads, and the gradient updates for the shared model parameters are carried out without synchronization. Asynchronous SGD is highly efficient, and causes little performance drop when parameters associated with different mini-batches are mutually disjoint with a high probability (Recht et al., 2011). We adapt the learning rate based on historical gradients using AdaGrad (Duchi et al., 2011).

4.3 Creation of Negative Samples

Since only valid triples (positive instances) are explicitly given in the training set, invalid triples (negative instances) need to be artificially created. Specifically, for every positive example $(s,r,o)$, we generate three negative instances $(s^{\prime},r,o)$, $(s,r^{\prime},o)$, $(s,r,o^{\prime})$ by corrupting $s$, $r$, $o$ with random entities/relations $s^{\prime}\in\mathcal{E}$, $r^{\prime}\in\mathcal{R}$, $o^{\prime}\in\mathcal{E}$. The union of all positive and negative instances defines our data distribution $\mathcal{D}$ for SGD updates.

4.4 Model Selection

5 Results

Table 2 compares the Hits@10 score of ANALOGY with that of 23 competing methods using the published scores for these methods in the literature on the WN18 and FB15K datasets. For the methods not having both scores, the missing slots are indicated by “–”. The best score on each dataset is marked in the bold face; if the differences among the top second or third scores are not statistically significant from the top one, then these scores are also bold faced. We used one-sample proportion test (Yang & Liu, 1999) at the 5% p-value level for testing the statistical significancesNotice that proportion tests only apply to performance scores as proportions, including Hits@k, but are not applicable to non-proportional scores such as MRR. Hence we only conducted the proportion tests on the Hits@k scores..

Table 3 compares the methods (including ours) whose results in additional metrics are available. The usage of the bold faces is the same as those in Table 2.

In both tables, ANALOGY performs either the best or the 2nd best which is in the equivalent class with the best score in each case according statistical significance test. Specifically, on the harder FB15K dataset in Table 2, which has a very large number of relations, our model outperforms all baseline methods. These results provide a good evidence for the effective modeling of analogical structures in our approach. We are pleased to see in Table 3 that ANALOGY outperforms DistMult, ComplEx and HolE in all the metrics, as the latter three can be viewed as more constrained versions of our method (as discussed in (§5)). Furthermore, our assertion on HolE for being a special case of ComplEx (§5) is justified in the same table by the fact that the performance of HolE is dominated by ComplEx.

In Figure 3 we show the empirical scalability of ANALOGY, which not only completes one epoch in a few seconds on both datasets, but also scales linearly in the size of the embedding problem. As compared to single-threaded AdaGrad, our asynchronous AdaGrad over 16 CPU threads offers 11.4x and 8.3x speedup on FB15K and WN18, respectively, on a single commercial desktop.

Conclusion

We presented a novel framework for explicitly modeling analogical structures in multi-relational embedding, along with a differentiable objective function and a linear-time inference algorithm for large-scale embedding of knowledge graphs. The proposed approach obtains the state-of-the-art results on two popular benchmark datasets, outperforming a large number of strong baselines in most cases.

Although we only focused on the multi-relational inference for knowledge-base embedding, we believe that analogical structures exist in many other machine learning problems beyond the scope of this paper. We hope this work shed light on a broad range of important problems where scalable inference for analogical analysis would make an impact, such as machine translation and image captioning (both problems require modeling cross-domain analogies). We leave these interesting topics as our future work.

Acknowledgments

We thank the reviewers for their helpful comments. This work is supported in part by the National Science Foundation (NSF) under grant IIS-1546329.

References