Traversing Knowledge Graphs in Vector Space

Introduction

Broad-coverage knowledge bases such as Freebase [Bollacker et al. (2008] support a rich array of reasoning and question answering applications, but they are known to suffer from incomplete coverage [Min et al. (2013]. For example, as of May 2015, Freebase has an entity Tad Lincoln (Abraham Lincoln’s son), but does not have his ethnicity. An elegant solution to incompleteness is using vector space representations: Controlling the dimensionality of the vector space forces generalization to new facts [Nickel et al. (2011, Nickel et al. (2012, Socher et al. (2013, Riedel et al. (2013, Neelakantan et al. (2015]. In the example, we would hope to infer Tad’s ethnicity from the ethnicity of his parents.

However, what is missing from these vector space models is the original strength of knowledge bases: the ability to support compositional queries [Ullman (1985]. For example, we might ask what the ethnicity of Abraham Lincoln’s daughter would be. This can be formulated as a path query on the knowledge graph, and we would like a method that can answer this efficiently, while generalizing over missing facts and even missing or hypothetical entities (Abraham Lincoln did not in fact have a daughter).

In this paper, we present a scheme to answer path queries on knowledge bases by “compositionalizing” a broad class of vector space models that have been used for knowledge base completion (see Figure 1). At a high level, we interpret the base vector space model as implementing a soft edge traversal operator. This operator can then be recursively applied to predict paths. Our interpretation suggests a new compositional training objective that encourages better modeling of paths. Our technique is applicable to a broad class of composable models that includes the bilinear model [Nickel et al. (2011] and TransE [Bordes et al. (2013].

We have two key empirical findings: First, we show that compositional training enables us to answer path queries up to at least length 5 by substantially reducing cascading errors present in the base vector space model. Second, we find that somewhat surprisingly, compositional training also improves upon state-of-the-art performance for knowledge base completion, which is a special case of answering unit length path queries. Therefore, compositional training can also be seen as a new form of structural regularization for existing models.

Task

We now give a formal definition of the task of answering path queries on a knowledge base. Let $\mathcal{E}$ be a set of entities and $\mathcal{R}$ be a set of binary relations. A knowledge graph $\mathcal{G}$ is defined as a set of triples of the form $\left(s,r,t\right)$ where $s,t\in\mathcal{E}$ and $r\in\mathcal{R}$. An example of a triple in Freebase is $(\texttt{{tad\_lincoln}},\texttt{{parents}},\texttt{{abraham\_lincoln}})$.

A path query $q$ consists of an initial anchor entity, $s$, followed by a sequence of relations to be traversed, $p=(r_{1},\ldots,r_{k})$. The answer or denotation of the query, ${\llbracket q\rrbracket}$, is the set of all entities that can be reached from $s$ by traversing $p$. Formally, this can be defined recursively:

For example, tad_lincoln/parents/location is a query $q$ that asks: “Where did Tad Lincoln’s parents live?”.

For evaluation (see Section 5 for details), we define the set of candidate answers to a query $\mathcal{C}(q)$ as the set of all entities that “type match”, namely those that participate in the final relation of $q$ at least once; and let $\mathcal{N}(q)$ be the incorrect answers:

Knowledge base completion (KBC) is the task of predicting whether a given edge $(s,r,t)$ belongs in the graph or not. This can be formulated as a path query $q=s/r$ with candidate answer $t$.

Compositionalization

In this section, we show how to compositionalize existing KBC models to answer path queries. We start with a motivating example in Section 3.1, then present the general technique in Section 3.2. This suggests a new compositional training objective, described in Section 3.3. Finally, we illustrate the technique for several more models in Section 3.4, which we use in our experiments.

To motivate our compositionalization technique, take $d=|\mathcal{E}|$ and suppose $W_{r}$ is the adjacency matrix for relation $r$ and entity vector $x_{e}$ is the indicator vector with a 1 in the entry corresponding to entity $e$. Then, to answer a path query $q=s/r_{1}/\ldots/r_{k}$, we would then compute

It is easy to verify that the score counts the number of unique paths between $s$ and $t$ following relations $r_{1}/\ldots/r_{k}$. Hence, any $t$ with positive score is a correct answer (${\llbracket q\rrbracket}=\{t:\text{score}(q,t)>0\}$).

2 General technique

The strategy used to extend the bilinear model of (5) to the compositional model in (6) can be applied to any composable model: namely, one that has a scoring function of the form:

We can now define the vector denotation of a query ${\llbracket q\rrbracket}_{\text{V}}$ analogous to the definition of ${\llbracket q\rrbracket}$ in (1) and (2):

The score function for a compositionalized model is then

3 Compositional training

The score function in (10) naturally suggests a new compositional training objective. Let $\{(q_{i},t_{i})\}_{i=1}^{N}$ denote a set of path query training examples with path lengths ranging from 1 to $L$. We minimize the following max-margin objective:

where the parameters are the membership operator, the traversal operators, and the entity vectors:

This objective encourages the construction of “set vectors”: because there are path queries of different lengths and types, the model must learn to produce an accurate set vector ${\llbracket q\rrbracket}_{\text{V}}$ after any sequence of traversals. Another perspective is that each traversal operator is trained such that its transformation preserves information in the set vector which might be needed in subsequent traversal steps.

In contrast, previously proposed training objectives for knowledge base completion only train on queries of path length 1. We will refer to this special case as single-edge training.

In Section 5, we show that compositional training leads to substantially better results for both path query answering and knowledge base completion. In Section 6, we provide insight into why.

4 Other composable models

The TransE model of ?) uses the scoring function

where $x_{s}$, $w_{r}$ and $x_{t}$ are all $d$-dimensional vectors.

In this case, the model can be expressed using membership operator

We visualize the compositional TransE model in Figure 2.

Bilinear-Diag.

The Bilinear-Diag model of ?) is a special case of the bilinear model with the relation matrices constrained to be diagonal. Alternatively, the model can be viewed as a variant of TransE with multiplicative interactions between entity and relation vectors.

Not all models can be compositionalized.

It is important to point out that some models are not naturally composable—for example, the latent feature model of ?) and the neural tensor network of ?). These approaches have scoring functions which combine $s$, $r$ and $t$ in a way that does not involve an intermediate vector representing $s/r$ alone without $t$, so they do not decompose according to (7).

5 Implementation

We use AdaGrad [Duchi et al. (2010] to optimize $J(\Theta)$, which is in general non-convex. Initialization scale, mini-batch size and step size were cross-validated for all models. We initialize all parameters with i.i.d. Gaussians of variance 0.1 in every entry, use a mini-batch size of 300 examples, and a step size in $[0.001,0.1]$ (chosen via cross-validation) for all of the models. For each example $q$, we sample 10 negative entities $t^{\prime}\in\mathcal{N}(q)$. During training, all of the entity vectors are constrained to lie on the unit ball, and we clipped the gradients to the median of the observed gradients if the update exceeded 3 times the median.

We first train on path queries of length 1 until convergence and then train on all path queries until convergence. This guarantees that the model masters basic edges before composing them to form paths. When training on path queries, we explicitly parameterize inverse relations. For the bilinear model, we initialize $W_{r^{-1}}$ with $W_{r}^{\top}$. For TransE, we initialize $w_{r^{-1}}$ with $-w_{r}$. For Bilinear-Diag, we found initializing $w_{r^{-1}}$ with the exact inverse $1/w_{r}$ is numerically unstable, so we instead randomly initialize $w_{r^{-1}}$ with i.i.d Gaussians of variance 0.1 in every entry. Additionally, for the bilinear model, we replaced the sum over $\mathcal{N}(q_{i})$ in the objective with a max since it yielded slightly higher accuracy. Our models are implemented using Theano [Bastien et al. (2012, Bergstra et al. (2010].

Datasets

In Section 4.1, we describe two standard knowledge base completion datasets. These consist of single-edge queries, so we call them base datasets. In Section 4.2, we generate path query datasets from these base datasets.

Our experiments are conducted using the subsets of WordNet and Freebase from ?). The statistics of these datasets and their splits are given in Table 1.

The WordNet and Freebase subsets exhibit substantial differences that can influence model performance. The Freebase subset is almost bipartite with most of the edges taking the form $(s,r,t)$ for some person $s$, relation $r$ and property $t$. In WordNet, both the source and target entities are arbitrary words.

Both the raw WordNet and Freebase contain many relations that are almost perfectly correlated with an inverse relation. For example, WordNet contains both has_part and part_of, and Freebase contains both parents and children. At test time, a query on an edge $(s,r,t)$ is easy to answer if the inverse triple $(t,r^{-1},s)$ was observed in the training set. Following ?), we account for this by excluding such “trivial” queries from the test set.

2 Path query datasets

Given a base knowledge graph, we generate path queries by performing random walks on the graph. If we view compositional training as a form of regularization, this approach allows us to generate extremely large amounts of auxiliary training data. The procedure is given below.

Perform a random walk beginning at entity $s$ and continuing $L$ steps.

At step $i$ of the walk, choose a relation $r_{i}$ uniformly from the set of relations incident on the current entity $e$.

Choose the next entity uniformly from the set of entities reachable via $r_{i}$.

Output a query-answer pair, $(q,t)$, where $q=s/r_{1}/\cdots/r_{L}$ and $t$ is the final entity of the random walk.

Main results

We evaluate the models derived in Section 3 on two tasks: path query answering and knowledge base completion. On both tasks, we show that the compositional training strategy proposed in Section 3.3 leads to substantial performance gains over standard single-edge training. We also compare directly against the KBC results of ?), demonstrating that previously inferior models now match or outperform state-of-the-art models after compositional training.

Numerous metrics have been used to evaluate knowledge base queries, including hits at 10 (percentage of correct answers ranked in the top 10) and mean rank. We evaluate on hits at 10, as well as a normalized version of mean rank, mean quantile, which better accounts for the total number of candidates. For a query $q$, the quantile of a correct answer $t$ is the fraction of incorrect answers ranked after $t$:

The quantile ranges from 0 to 1, with 1 being optimal. Mean quantile is then defined to be the average quantile score over all examples in the dataset. To illustrate why normalization is important, consider a set of queries on the relation gender. A model that predicts the incorrect gender on every query would receive a mean rank of 2 (since there are only 2 candidate answers), which is fairly good in absolute terms, whereas the mean quantile would be 0, rightfully penalizing the model.

As a final note, several of the queries in the Freebase path dataset are “type-match trivial” in the sense that all of the type matching candidates $\mathcal{C}(q)$ are correct answers to the query. In this case, mean quantile is undefined and we exclude such queries from evaluation.

Overview.

The upper half of Table 2 shows that compositional training improves path querying performance across all models and metrics on both datasets, reducing error by up to $76.2\%$.

The lower half of Table 2 shows that surprisingly, compositional training also improves performance on knowledge base completion across almost all models, metrics and datasets. On WordNet, TransE benefits the most, with a $43.3\%$ reduction in error. On Freebase, Bilinear benefits the most, with a $38.8\%$ reduction in error.

In terms of mean quantile, the best overall model is TransE (Comp). In terms of hits at 10, the best model on WordNet is Bilinear (Comp), while the best model on Freebase is TransE (Comp).

Deduction and Induction.

Performance on the deduction subset of the dataset is disappointingly low for models trained with single-edge training: they struggle to answer path queries even when all edges in the path query have been seen at training time. Compositional training dramatically reduces these errors, sometimes doubling mean quantile. In Section 6, we analyze how this might be possible. After compositional training, performance on the harder induction subset is also much stronger. Even when edges are missing along a path, the models are able to infer them.

Interpretable queries.

Although our path datasets consists of random queries, both datasets contain a large number of useful, interpretable queries. Results on a few illustrative examples are shown in Table 4.

Comparison with ?).

Here, we measure performance on the KBC task in terms of the accuracy metric of ?). This evaluation involves sampled negatives, and is hence noisier than mean quantile, but makes our results directly comparable to ?). Our results show that previously inferior models such as the bilinear model can outperform state-of-the-art models after compositional training.

?) proposed parametrizing each entity vector as the average of vectors of words in the entity ($w_{\texttt{{tad\_lincoln}}}=\frac{1}{2}(w_{\texttt{{tad}}}+w_{\texttt{{lincoln}}})$, and pretraining these word vectors using the method of ?). Table 5 reports results when using this approach in conjunction with compositional training. We initialized all models with word vectors from ?). We found that compositionally trained models outperform the neural tensor network (NTN) on WordNet, while being only slightly behind on Freebase. (We did not use word vectors in any of our other experiments.)

When the strategy of averaging word vectors to form entity vectors is not applied, our compositional models are significantly better on WordNet and slightly better on Freebase. It is worth noting that in many domains, entity names are not lexically meaningful, so word vector averaging is not always meaningful.

Analysis

In this section, we try to understand why compositional training is effective. For concreteness, everything is described in terms of the bilinear model. We will refer to the compositionally trained model as Comp, and the model trained with single-edge training as Single.

It is tempting to think that if Single has accurately modeled individual edges in a graph, it should accurately model the paths that result from those edges. This intuition turns out to be incorrect, as revealed by Single’s relatively weak performance on the path query dataset. We hypothesize that this is due to cascading errors along the path. For a given edge $\left(s,r,t\right)$ on the path, single-edge training encourages $x_{t}$ to be closer to $x_{s}^{\top}W_{r}$ than any other incorrect $x_{t^{\prime}}$. However, once this is achieved by a margin of $1$, it does not push $x_{t}$ any closer to $x_{s}^{\top}W_{r}$. The remaining discrepancy is noise which gets added at each step of path traversal. This is illustrated schematically in Figure 2.

To observe this phenomenon empirically, we examine how well a model handles each intermediate step of a path query. We can do this by measuring the reconstruction quality (RQ) of the set vector produced after each traversal operation. Since each intermediate stage is itself a valid path query, we define RQ to be the average quantile over all entities that belong in ${\llbracket q\rrbracket}$:

When all entities in ${\llbracket q\rrbracket}$ are ranked above all incorrect entities, RQ is 1. In Figure 3, we illustrate how RQ changes over the course of a query.

2 Why does compositional training improve knowledge base completion?

Table 2 reveals that Comp also performs better on the single-edge task of knowledge base completion. This is somewhat surprising, since Single is trained on a training set which distributionally matches the test set, whereas Comp is not. However, Comp’s better performance on path queries suggests that there must be another factor at play. At a high level, training on paths must be providing some form of structural regularization which reduces cascading errors. Indeed, paths in a knowledge graph have proven to be important features for predicting the existence of single edges [Lao et al. (2011, Neelakantan et al. (2015]. For example, consider the following Horn clause:

which states that if $x$ has a parent with location $z$, then $x$ has place of birth $z$. The body of the Horn clause expresses a path from $x$ to $z$. If Comp models the path better, then it should be better able to use that knowledge to infer the head of the Horn clause.

More generally, consider Horn clauses of the form $p\Rightarrow r$, where $p=r_{1}/\ldots/r_{k}$ is a path type and $r$ is the relation being predicted. Let us focus on Horn clauses with high precision as defined by:

where ${\llbracket p\rrbracket}$ is the set of entity pairs connected by $p$, and similarly for ${\llbracket r\rrbracket}$.

Intuitively, one way for the model to implicitly learn and exploit such a Horn clause would be to satisfy the following two criteria:

The model should ensure a consistent spatial relationship between entity pairs that are related by the path type $p$; that is, keeping $x_{s}^{\top}W_{r_{1}}\ldots W_{r_{k}}$ close to $x_{t}$ for all valid $\left(s,t\right)$ pairs.

The model’s representation of the path type $p$ and relation $r$ should capture that spatial relationship; that is, $x_{s}^{\top}W_{r_{1}}\ldots W_{r_{k}}\approx x_{t}$ implies $x_{s}^{\top}W_{r}\approx x_{t}$, or simply $W_{r_{1}}\ldots W_{r_{k}}\approx W_{r}$.

We have already seen empirically that Single does not meet criterion 1, because cascading errors cause it to put incorrect entity vectors $x_{t^{\prime}}$ closer to $x_{s}^{\top}W_{r_{1}}\ldots W_{r_{k}}$ than the correct entity. Comp mitigates these errors.

If Comp is better at capturing the correlation between $p$ and $r$, then we would expect that when $\text{prec}(p)$ is high, compositional training should shrink $\text{dist}(p,r)$ more. To confirm this hypothesis, we enumerated over all 676 possible paths of length 2 (including inverted relations), and examined the proportional reduction in $\text{dist}(p,r)$ caused by compositional training,

Figure 4 shows that higher precision paths indeed correspond to larger reductions in $\text{dist}(p,r)$.

Related work

Many models have been proposed for knowledge base completion, including those reviewed in Section 3.4 [Nickel et al. (2011, Bordes et al. (2013, Yang et al. (2015, Socher et al. (2013]. ?) demonstrated that KBC models can improve the quality of relation extraction by serving as graph-based priors. ?) showed that such models can be also be directly used for open-domain relation extraction. Our compositional training technique is an orthogonal improvement that could help any composable model.

Distributional compositional semantics.

Previous works have explored compositional vector space representations in the context of logic and sentence interpretation. In ?), a matrix is associated with each word of a sentence, and can be used to recursively modify the meaning of nearby constituents. ?) explored the ability of tensors to simulate logical calculi. ?) showed that recursive neural networks can learn to distinguish important semantic relations. ?) found that compositional models were powerful enough to describe and retrieve images.

We demonstrate that compositional representations are also useful in the context of knowledge base querying and completion. In the aforementioned work, compositional models produce vectors which represent truth values, sentiment or image features. In our approach, vectors represent sets of entities constituting the denotation of a knowledge base query.

Path modeling.

Numerous methods have been proposed to leverage path information for knowledge base completion and question answering. ?) proposed combining low-rank models with sparse path features. ?) used random walks as features and ?) extended this approach by using vector space similarity to govern random walk probabilities. ?) addressed the problem of path sparsity by embedding paths using a recurrent neural network. ?) sampled random walks on social networks as training examples, with a different goal to classify nodes in the network. ?) embed paths as a sum of relation vectors for question answering. Our approach is unique in modeling the denotation of each intermediate step of a path query, and using this information to regularize the spatial arrangement of entity vectors.

Discussion

We introduced the task of answering path queries on an incomplete knowledge base, and presented a general technique for compositionalizing a broad class of vector space models. Our experiments show that compositional training leads to state-of-the-art performance on both path query answering and knowledge base completion.

There are several key ideas from this paper: regularization by augmenting the dataset with paths, representing sets as low-dimensional vectors in a context-sensitive way, and performing function composition using vectors. We believe these three could all have greater applicability in the development of vector space models for knowledge representation and inference.

Our code, data, and experiments are available on the CodaLab platform at https://www.codalab.org/worksheets/0xfcace41fdeec45f3bc6ddf31107b829f.

Acknowledgments

We would like to thank Gabor Angeli for fruitful discussions and the anonymous reviewers for their valuable feedback. We gratefully acknowledge the support of the Google Natural Language Understanding Focused Program and the National Science Foundation Graduate Research Fellowship under Grant No. DGE-114747.

References