PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-Hop Knowledge Graph Reasoning with Reward Shaping

Xi Victoria Lin, Richard Socher, Caiming Xiong

arXiv:1808.10568v2cs.AIcs.CLcs.LG

TL;DR

The paper addresses false-negative rewards and spurious paths in RL-based multi-hop QA over incomplete knowledge graphs. It combines embedding-based soft reward shaping with randomized action dropout to improve reward estimation and path exploration. The approach improves over path-based methods on several benchmarks and is comparable to or better than embedding-based models, while remaining less effective for some relation types and leaving an RL-versus-embedding performance gap.

  • Problem

    Incomplete knowledge graphs cause false-negative rewards, while missing oracle paths allow spurious trajectories to mislead on-policy multi-hop QA.

  • Method

    The model uses pretrained one-hop KG embeddings for soft rewards on uncertain targets and randomly masks outgoing edges to force diverse path exploration.

  • Results

    The approach improves over state-of-the-art path-based models on four of five datasets and is consistently comparable or better than embedding-based approaches across five datasets.

  • Takeaways & Limitations

    More accurate environment representations and broader search-space exploration are important to performance in end-to-end RL-based KGQA.

  • Takeaways & Limitations

    The RL-based and embedding-based approaches still have a performance gap, and the method is less effective for the relation types represented in NELL-995.

Abstract

from arXiv · show

Multi-hop reasoning is an effective approach for query answering (QA) over incomplete knowledge graphs (KGs). The problem can be formulated in a reinforcement learning (RL) setup, where a policy-based agent sequentially extends its inference path until it reaches a target. However, in an incomplete KG environment, the agent receives low-quality rewards corrupted by false negatives in the training data, which harms generalization at test time. Furthermore, since no golden action sequence is used for training, the agent can be misled by spurious search trajectories that incidentally lead to the correct answer. We propose two modeling advances to address both issues: (1) we reduce the impact of false negative supervision by adopting a pretrained one-hop embedding model to estimate the reward of unobserved facts; (2) we counter the sensitivity to spurious paths of on-policy RL by forcing the agent to explore a diverse set of paths using randomly generated edge masks. Our approach significantly improves over existing path-based KGQA models on several benchmark datasets and is comparable or better than embedding-based models.

1 Introduction

Multi-hop KG reasoning uses sequential path search to infer missing facts, but incomplete training graphs create false-negative rewards and spurious paths. The paper addresses these challenges with embedding-based reward shaping and action dropout, improving path-based KGQA across benchmark datasets.

  • Motivation: Incomplete knowledge graphs omit relevant facts, motivating reasoning methods that infer missing links from existing entities and relations.Embedding models score potential triples, while multi-hop methods synthesize information across paths for more interpretable reasoning.
  • Walk-based QA: RL-based walk-based QA trains an agent to search from a source entity toward candidate answers without precomputed paths.MINERVA formulates multi-hop reasoning as sequential decision-making with REINFORCE.
  • Training challenges: Incomplete training graphs produce false-negative targets because correct answers may lack observed links and therefore receive no reward.Figure 2 tracks false negatives encountered during the first 20 training epochs on UMLS.
  • Training challenges: Without ground-truth paths, on-policy RL can favor spurious trajectories that reach correct answers incidentally and bias later action selection.REINFORCE reinforces high-reward actions from paths discovered early in training.
  • Proposed approach: The proposed model uses pretrained embeddings for soft rewards on uncertain targets and randomly masks outgoing edges to encourage diverse path exploration.Together, these innovations address false-negative supervision and sensitivity to spurious paths.

2 Approach

The approach combines knowledge-based reward shaping with action dropout to address false-negative rewards and spurious paths in walk-based KGQA. A policy searches the graph sequentially, receiving observed-answer rewards or pretrained embedding scores while randomly masking outgoing actions during sampling.

  • Walk-based QA: Walk-based QA models graph reasoning as an MDP in which an agent sequentially selects outgoing edges from a source entity until a target is reached.States include the current entity, source entity, and query relation; actions are outgoing edges plus a self-loop that acts as a stop action.
  • Knowledge-based reward shaping: Binary rewards treat unobserved correct answers like true negatives because incomplete training graphs omit relevant links.The default terminal reward is 1 for an observed correct target and 0 otherwise.
  • Knowledge-based reward shaping: Reward shaping assigns observed correct targets reward 1 and otherwise uses a pretrained embedding score f(es, rq, eT) for the destination entity.The embedding model estimates the likelihood of the unknown fact, and the reward-shaping model is kept fixed during training.
  • Action dropout: On-policy exploration can favor spurious paths because correct answers may be reached through paths irrelevant to the query relation.When spurious paths are more numerous, they may be found first and increasingly bias subsequent exploration.
  • Action dropout: Entities with larger in-degree or out-degree often exacerbate the spurious-path problem, while denser graphs generally require larger action-dropout rates.The reported experiments find a positive correlation between the optimal dropout rate and average node fan-out.
  • Action dropout: Action dropout randomly masks outgoing edges during REINFORCE sampling, encouraging exploration of diverse paths without changing the policy used for gradient computation.Mask entries are sampled as binary variables from a Bernoulli distribution with parameter 1 − α.

3 Related Work

Related work spans embedding-based one-hop modeling, symbolic multi-hop path reasoning, and reinforcement-learning approaches for sequential KG search. The paper connects embedding semantics and path-based symbolic reasoning while contrasting its action dropout with prior exploration and reward-sparsity methods.

  • Knowledge Graph Embeddings: Knowledge graph embeddings learn a fuzzy truth score for triples and can answer queries by returning entities with the highest scores.These one-hop models are simple and have achieved state-of-the-art KGQA performance, but they do not represent symbolic relation composition.
  • Connections to Prior Work: The paper presents reward shaping as a combination of embedding-based triple semantics with the symbolic reasoning capability of path-based methods.It contrasts this with ReinforceWalk’s value function, which is updated from search history, and with MINERVA’s entropy regularization.
  • Reinforcement Learning: MINERVA formulates KG query answering as end-to-end sequential search with REINFORCE and no precomputed paths.The agent starts from the source entity and searches the graph for candidate answers.
  • Reinforcement Learning: KG reasoning differs from many NLP reinforcement-learning tasks through large action spaces, unavailable golden paths, and usually shorter inference paths.Some KG entities have thousands of neighbors, while inference paths usually contain 2–5 steps.

4 Experiment Setup

The experiments evaluate KG query answering across five benchmark datasets, comparing embedding-based and multi-hop reasoning models under a shared protocol and implementation setup.

  • Baselines: The comparison includes DistMult, ComplEx, and ConvE embeddings alongside NTP-λ, NeuralLP, MINERVA, and two reward-shaped model variants.The proposed variants use ComplEx or ConvE as reward-shaping modules.
  • Decoding: Beam search returns unique entity predictions by assigning each entity the maximum score across paths that reach it.This avoids repetitions among beam-top paths and improves over directly outputting beam-top entities.
  • Implementation details: The study uses bidirectional KG links, shared train/dev/test splits, overlap removal, Xavier initialization, and a public implementation plan.Outgoing edges are capped using PageRank-selected neighbors to control GPU memory, and batch sizes stop at 512 under memory constraints.
  • Model configuration: Path-based models use a three-layer LSTM with hidden dimension 200, while entity and relation embeddings are size 200 across models.Hyperparameter search covers path lengths 2 and 3 and fan-out thresholds η of 256–512.
  • Evaluation protocol: Evaluation converts each test triple into a query, ranks candidate answers, removes other correct answers, and computes Hits@k and MRR.NELL-995 excludes test triples with unseen entities, following prior work.

5 Results

Across five datasets, the proposed approach is generally comparable to or better than embedding-based models, with gains driven especially by action dropout and effective path exploration. Results vary by dataset and relation type, and reward shaping can sometimes hurt.

  • 5.1 Model Comparison: Embedding-based models achieve the best overall metrics on UMLS, Kinship, FB15K237, and NELL-995, while prior path-based models show considerable gaps on Kinship and FB15k-237.The gaps are 9.1 and 14.2 absolute points on Kinship and FB15k-237, respectively.
  • 5.1 Model Comparison: Ours(ConvE) is consistently comparable or better than embedding-based approaches across all five datasets and improves prior path-based state of the art on UMLS, Kinship, and FB15k-237.The reported improvements are 4%, 9%, and 39%, respectively; no significant improvement is observed on WN18RR and NELL-995.
  • 5.1 Model Comparison: Reward-shaping modules perform similarly overall, and reward-shaping effectiveness is not determined solely by the module's dev-set accuracy.ComplEx can help reward shaping despite performing slightly worse than ConvE on its own; the relationship is left for future work.
  • 5.2 Ablation Study: Removing reward shaping or action dropout usually causes a significant dev-set performance drop, while WN18RR improves when ConvE reward shaping is removed.Removing action dropout generally has the greater impact, indicating that path-space exploration is important across datasets.
  • 5.3.1 Convergence Rate: Action dropout improves performance immediately on all datasets, while the full model often converges faster and to higher dev-set accuracy than either ablation.On FB15k-237, the full model continues improving after both ablations begin overfitting; on NELL995, −RS eventually reaches comparable performance.
  • 5.3.2 Path Diversity: Action dropout substantially increases path exploration, whereas reward shaping slightly reduces explored paths while guiding the agent away from noisy trajectories.The best-performing model is not generally the one exploring the largest number of paths, so path count and performance are not strictly positively correlated.
  • 5.3.3 Performance w.r.t. Relation Types: The proposed techniques improve query answering for both to-many and to-one relations, with larger gains generally on to-many relations.ConvE reward shaping hurts both relation types on WN18RR, while both techniques hurt to-many relations on NELL-995.
  • 5.3.4 Performance w.r.t. Seen Queries vs. Unseen Queries: The proposed enhancements improve performance on unseen queries in most cases, with action dropout generally more effective.On NELL-995, neither enhancement is effective over seen queries.

6 Conclusions

The paper introduces reward shaping and action dropout for end-to-end RL-based KGQA. It reports consistent improvements over several state-of-the-art multi-hop reasoning models, while noting that a performance gap with embedding-based approaches remains.

  • 6 Conclusions: The approach combines reward shaping with action dropout for end-to-end RL-based knowledge graph query answering.These are the paper’s two proposed modeling advances.
  • 6 Conclusions: The method improves over state-of-the-art multi-hop reasoning models consistently on several benchmark knowledge graphs.
  • 6 Conclusions: Reward shaping provides a more accurate environment representation, while action dropout enables more thorough exploration of the search space.The analysis identifies both factors as important to the performance boost.
  • 6 Conclusions: A performance gap between RL-based and embedding-based approaches for KGQA remains.

A.1 Model Robustness

Across five random-seed runs, ConvE and Ours(ConvE) show small variability on every dataset, indicating stable reported performance under fixed hyperparameters.

  • A.1 Model Robustness: Both ConvE and Ours(ConvE) have standard deviations below 0.01 on all datasets across five random seeds.All other hyperparameters were fixed for these runs.
  • A.1 Model Robustness: Table 6 reports test-set MRR×100 means and standard deviations for both models across all datasets.

A.2 Development Set Evaluation Using Complete KGs

Development-set MRR can be substantially lower than test-set MRR when incomplete split-specific graphs create false negatives for multi-answer queries. Recomputing with complete KGs raises metrics on four datasets, but complete-graph evaluation is diagnostic rather than suitable for hyperparameter search because of leakage risk.

  • A.2 Development Set Evaluation Using Complete KGs: Dev-set MRRs are significantly lower than test-set MRRs on UMLS, Kinship, and FB15k-237.The discrepancy is attributed to multi-answer queries whose answers are distributed across random train/dev/test splits.
  • A.2 Development Set Evaluation Using Complete KGs: Table 7 compares complete-KG dev-set MRR for Ours(ConvE) with models without reward shaping and action dropout.
  • A.2 Development Set Evaluation Using Complete KGs: Using complete KGs eliminates most false negatives during dev evaluation and increases performance metrics on four datasets to levels comparable with test-set metrics.The relative improvement correlates with average node fan-out.
  • A.2 Development Set Evaluation Using Complete KGs: Complete-KG results are intended to expose dataset peculiarities after hyperparameters are fixed, not to guide tuning.Hyperparameter search should hide test-set triples to avoid potential test-set leakage.

A.3 Action Dropout Rates Used for Different KGs

Action dropout should generally increase with KG connectivity, as measured by average node fan-out. Completely random sampling works reasonably on smaller KGs, whereas larger KGs require policy-guided sampling.

  • A.3 Action Dropout Rates Used for Different KGs: Larger action dropout rates are generally necessary for densely connected knowledge graphs.The optimal rate positively correlates with average node fan-out.
  • A.3 Action Dropout Rates Used for Different KGs: Completely random sampling causes a small but significant performance drop on UMLS and Kinship when the action dropout rate is 1.0.Random sampling nevertheless performs reasonably well on these smaller datasets.
  • A.3 Action Dropout Rates Used for Different KGs: Policy-guided sampling is necessary for the larger KGs FB15k237, WN18RR, and NELL-995.
  • A.3 Action Dropout Rates Used for Different KGs: Table 8 lists the action dropout rates used for all KG datasets in the experiments.
Loading 1808.10568v2…