PaperlayerView exact revision on arXiv

Source-linked AI summary

Traversing Knowledge Graphs in Vector Space

Kelvin Guu, John Miller, Percy Liang

arXiv:1506.01094v2cs.CLcs.AIcs.DBstat.ML

TL;DR

Knowledge graphs contain missing facts that disrupt compositional path queries, and existing vector-space completion models can accumulate cascading errors when applied recursively. The paper compositionalizes a broad class of these models and introduces compositional training, which improves path querying and knowledge-base completion. The authors report state-of-the-art performance on both tasks, with path-query error reductions up to 76.2% and completion error reductions up to 43.3%.

  • Problem

    Knowledge graphs have incomplete coverage, while vector-space completion models lack reliable support for compositional path queries over multiple relations.

  • Method

    The paper recursively applies base models’ soft edge-traversal operators and trains them compositionally on paths.

  • Results

    Compositional training improves path querying across models and metrics, reducing error by up to 76.2%, and improves knowledge-base completion with error reductions up to 43.3%.

  • Takeaways & Limitations

    Compositional training provides structural regularization and yields state-of-the-art performance on both path-query answering and knowledge-base completion.

  • Takeaways & Limitations

    The technique does not apply naturally to models whose scoring functions lack an intermediate vector for the partial traversal, such as latent feature and neural tensor network models.

Abstract

from arXiv · show

Path queries on a knowledge graph can be used to answer compositional questions such as "What languages are spoken by people living in Lisbon?". However, knowledge graphs often have missing facts (edges) which disrupts path queries. Recent models for knowledge base completion impute missing facts by embedding knowledge graphs in vector spaces. We show that these models can be recursively applied to answer path queries, but that they suffer from cascading errors. This motivates a new "compositional" training objective, which dramatically improves all models' ability to answer path queries, in some cases more than doubling accuracy. On a standard knowledge base completion task, we also demonstrate that compositional training acts as a novel form of structural regularization, reliably improving performance across all base models (reducing errors by up to 43%) and achieving new state-of-the-art results.

1 Introduction

Knowledge bases contain missing facts, motivating vector-space generalization, but existing models lack compositional path-query support. The paper compositionalizes broad classes of these models and introduces training that reduces cascading errors while improving knowledge-base completion.

  • Motivation: Knowledge bases such as Freebase have incomplete coverage, so vector-space representations are used to generalize to missing facts.The paper illustrates inferring Tad Lincoln’s ethnicity from his parents’ ethnicity.
  • Motivation: Existing vector-space models lack compositional queries that traverse multiple relations, including queries involving missing or hypothetical entities.The paper frames these questions as path queries requiring efficient answers.
  • Approach: The proposed scheme interprets base vector-space models as soft edge-traversal operators that can be recursively applied to predict paths.Figure 1 represents entity sets as real vectors and traverses edges through vector-to-vector transformations.
  • Approach: The compositionalization technique applies to a broad class of composable models, including the bilinear model and TransE.
  • Findings: Compositional training answers path queries up to at least length 5 by substantially reducing cascading errors.
  • Findings: Compositional training also improves knowledge-base completion, acting as a form of structural regularization for existing models.

2 Task

A path query starts from an anchor entity and traverses an ordered relation sequence to return reachable entities. Evaluation ranks answers among type-matching candidates, while knowledge-base completion is the one-relation special case of this task.

  • Knowledge graph: A knowledge graph is a set of triples (s, r, t), with entities as subjects and targets connected by binary relations.The paper gives (tad lincoln, parents, abraham lincoln) as an example.
  • Path queries: A path query consists of an anchor entity followed by a sequence of relations, and its answer is the set of entities reachable by traversing that sequence.The example tad lincoln/parents/location asks where Tad Lincoln’s parents lived.
  • Path queries: Appending relation r extends a query’s denotation with every target t connected by r from an entity already in the denotation.
  • Evaluation: Candidate answers are entities that participate in the query’s final relation at least once, while N(q) contains the incorrect candidates.
  • Knowledge-base completion: Knowledge-base completion predicts whether an edge (s, r, t) belongs in the graph, equivalent to a one-relation path query with candidate t.

3 Compositionalization

The paper compositionalizes vector-space knowledge-base completion models by interpreting them as recursive traversal and membership operators. A compositional training objective preserves path information, improving path-query answering and knowledge-base completion, although only naturally composable models support the technique.

  • General technique: Compositionalization interprets a base vector-space model as a traversal operator that can be recursively applied to answer path queries.The general framework uses traversal operators T_r and a membership operator M to score query-answer pairs.
  • Bilinear example: In the bilinear model, path-query scores count paths by sequentially multiplying relation operators between the starting and candidate entity vectors.With adjacency matrices and indicator vectors, positive scores identify correct answers.
  • Empirical findings: Compositional training improves both path-query answering and knowledge-base completion.Knowledge-base completion is the special case of answering unit-length path queries.
  • Other composable models: TransE uses additive traversal, Tr(xs) = xs + wr, to compose relation vectors across a path.The paper also evaluates Bilinear-Diag, a bilinear model whose relation matrices are constrained to be diagonal.
  • Scope boundary: Models whose scoring functions lack an intermediate representation for s/r alone, including the latent feature model and neural tensor network, cannot be naturally compositionalized.Their scoring functions combine source, relation, and target without decomposing into traversal and membership operators.

4 Datasets

Experiments use WordNet and Freebase subsets, with base datasets of single-edge queries and path-query datasets generated through random walks. The datasets differ structurally, and test construction excludes queries answerable from observed inverse edges or already seen during training.

  • Datasets: The experiments use WordNet and Freebase subsets from Socher et al. (2013), including base and generated path-query datasets.Dataset statistics and splits are reported in Table 1.
  • Dataset structure: Freebase is almost bipartite, with most edges linking a person to a property, whereas WordNet connects arbitrary words as source and target entities.These structural differences can influence model performance.
  • Evaluation filtering: The evaluation excludes trivial test queries whose inverse triple was observed in the training set.Both datasets contain relations strongly correlated with inverse relations, such as has part/part of and parents/children.
  • Path-query generation: Training path queries are generated by uniformly sampling a path length and starting entity, then performing a random walk through uniformly selected incident relations and reachable entities.Each generated example contains a relation sequence q = s/r1/· · · /rL and the walk’s final entity t.
  • Dataset construction: The procedure adds all training edges directly instead of sampling paths of length 1.A separate path-query test set is generated from the full graph and removes queries that appeared in training.

5 Main results

Compositional training substantially improves path-query answering and also strengthens knowledge base completion across models, while evaluations distinguish deduction, induction, and interpretable queries.

  • Overview: Compositional training improves path-query performance across all models and metrics on both datasets, reducing error by up to 76.2%.Table 2 compares single-edge training with compositional training using mean quantile, hits at 10, and percentage error reduction.
  • Knowledge base completion: 43.3% error reduction is achieved by TransE on WordNet, while Bilinear achieves a 38.8% reduction on Freebase for knowledge base completion.These are the largest reported benefits for the respective datasets.
  • Knowledge base completion: TransE (COMP) is best overall by mean quantile, while Bilinear (COMP) leads WordNet and TransE (COMP) leads Freebase on hits at 10.The best model depends on both the metric and dataset.
  • Deduction and Induction: Compositional training dramatically reduces deduction errors and also substantially strengthens performance on the harder induction subset.Single-edge models struggle even when all path edges were seen during training; compositional training sometimes doubles mean quantile.
  • Interpretable queries: On selected interpretable queries, Bilinear COMP outperforms Bilinear SINGLE for the parents/religion and type-of query examples.The reported mean-quantile values are 97.1 versus 81.9 for parents/religion and 79.4 versus 72.8 for the type-of path.

6 Analysis

The analysis attributes weak path-query performance to cascading traversal errors and explains how compositional training reduces them. It also links the improvement in knowledge base completion to structural regularization that better captures path–relation correlations.

  • Cascading errors: Single-edge training leaves residual noise after an edge is modeled, and that noise accumulates at each traversal step.The model stops pushing the correct target closer once it exceeds an incorrect target by the margin, leaving discrepancy that compounds along paths.
  • Cascading errors: RQ measures how well the entity set produced after each traversal ranks all correct entities above incorrect ones.RQ equals 1 when every entity in the query denotation is ranked above every incorrect entity.
  • Training objective: An added ℓ2 closeness term did not improve SINGLE on either path queries or single-edge evaluation across λ values from 0.001 to 100.This comparison motivates compositional training as a more effective approach to cascading errors.
  • Structural regularization: COMP improves knowledge base completion because path training provides structural regularization that reduces cascading errors and captures useful path–relation correlations.The analysis connects this effect to the role of paths as features for predicting single-edge existence.
  • Cascading errors: Compositional training substantially reduces path-query degradation as path length increases, producing more accurate top-five entity sets than SINGLE.The reported comparison concerns the query sequence ending in place of birth^-1/profession.
  • Structural regularization: Higher-precision paths yield larger reductions in dist(p, r) after compositional training, supporting better alignment between path types and predicted relations.The analysis examines all 676 length-two paths, including inverted relations.

7 Related work

The related work spans vector-space knowledge base completion, compositional semantics, and path-based reasoning. The paper distinguishes its approach by modeling intermediate query denotations and using them to regularize entity-vector geometry.

  • Knowledge base completion: Prior knowledge base completion models use vector-space representations to predict missing graph edges and support relation-extraction applications.The cited work includes bilinear, translational, and related low-rank models.
  • Distributional compositional semantics: Earlier compositional semantics work used vector representations for logic, sentence interpretation, semantic relations, and image retrieval.These approaches include recursive constituent modeling, tensor-based logical calculi, and recurrent neural networks.
  • Distributional compositional semantics: The paper applies compositional representations to knowledge base querying and completion, with vectors representing sets of entities in query denotations.This differs from prior uses in which vectors represented truth values, sentiment, or image features.
  • Path modeling: Path-based methods have used sparse path features, random walks, vector-space similarities, recurrent networks, and sums of relation vectors.The cited methods target knowledge base completion, question answering, or network-node classification.
  • Path modeling: This approach uniquely models each intermediate path-query denotation and uses that information to regularize entity-vector arrangements.The distinction is stated in comparison with prior path-embedding and random-walk methods.

8 Discussion

The paper introduces path-query answering on incomplete knowledge bases and a general compositionalization technique for vector-space models. It reports state-of-the-art performance on both path-query answering and knowledge base completion, while identifying broader ideas for vector-space knowledge representation and inference.

  • Contributions: The paper introduces path-query answering on incomplete knowledge bases and a general technique for compositionalizing a broad class of vector-space models.The contribution targets both querying and completion.
  • Results: Compositional training achieves state-of-the-art performance on both path-query answering and knowledge base completion.This is the paper’s overall experimental conclusion.
  • Implications: The paper identifies path-based dataset augmentation, context-sensitive low-dimensional set vectors, and vector-based function composition as broadly applicable ideas.The stated potential scope is vector-space models for knowledge representation and inference.
  • Reproducibility: The authors provide code, data, and experiments through the CodaLab platform.The discussion section points readers to the hosted reproducibility materials.
Loading 1506.01094v2…