Multi-Hop Knowledge Graph Reasoning with Reward Shaping

By Xi Victoria Lin, Richard Socher, Caiming Xiong. Conference on Empirical Methods in Natural Language Processing, 2018

406 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/7a941148d8c5865749801b2f9f67f9ad1fba1d25

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Semantic Evaluation for Text-to-SQL with Distilled Test Suite (2020, background): “Since these two conditions hold in many execution environments, our framework might potentially be applied to other logical forms, such as λ-DCS (Liang, 2013), knowledge graphs (Lin et al., 2018), and python code snippets (Yin et al.”
Knowledge Aware Conversation Generation with Explainable Reasoning over Augmented Graphs (2019, background): “…symbolic models (Das et al., 2017a; Lao et al., 2011), embedding-based neural models (Bordes et al., 2013; Wang et al., 2014), and models in unifying embedding and path-based technology (Das et al., 2018; Lin et al., 2018; Xiong et al., 2017), which can predict missing links for completion of KG.”
Neural, symbolic and neural-symbolic reasoning on knowledge graphs (2021, methodology): “:3) arraga et al., 2015) improve the ef ﬁ ciency of AMIE RLvLR (Omran et al., 2018) reduce the search space by the embedding technique RuLES (Ho et al., 2018) leverage the embedding technique to measure the quality of the rules Neural-Symbolic Reasoning Symbolic-driven Neural Reasoning KALE (Guo et ”
Learning Attention-based Embeddings for Relation Prediction in Knowledge Graphs (2019, methodology): “To evaluate our proposed method, we use ﬁve benchmark datasets: WN18RR (Dettmers et al., 2018), FB15k-237 (Toutanova et al., 2015), NELL-995 (Xiong et al., 2017), Uniﬁed Medical Language Systems (UMLS) (Kok and Domin-gos, 2007) and Alyawarra Kinship (Lin et al., 2018).”
LEGO: Latent Execution-Guided Reasoning for Multi-Hop Question Answering on Knowledge Graphs (2021, methodology): “…et al., 2016; Dong et al., 2015; Miller et al., 2016) aim to retrieve information from the KG using RL agent (Xiong et al., 2017; Qiu et al., 2020a; Lin et al., 2018; Das et al., 2018) or graph nets (Sun et al., 2018a; 2019a; Xiong et al., 2019), however, these methods rely on heuristics, e.g. ,…”
Improving Multi-hop Knowledge Base Question Answering by Learning Intermediate Supervision Signals (2021, positive): “[3, 22] conducted multi-hop reasoning on a graph under the reinforcement learning setting and treated every reasoning step as an edge transition on the graph.”
A Comprehensive Survey on Automatic Knowledge Graph Construction (2023, methodology): “[260] devised a soft reward shaping function based on the vector spaces of relations and entities, while Li et al.”
Do Transformers Really Perform Bad for Graph Representation? (2021, background): “The attention mechanism needs to estimate correlations for each node pair (vi, vj), and we believe the edges connecting them should be considered in the correlation as in [33, 48].”
Reinforcement Knowledge Graph Reasoning for Explainable Recommendation (2019, methodology): “At the same time, researchers have also explored RL in KG settings for other tasks such as question answering (QA) [3, 14, 29], which formulates multi-hop reasoning as a sequential decision making problem.”
A Survey of Knowledge Graph Reasoning on Graph Types: Static, Dynamic, and Multi-Modal (2022, background): “After that, MultiHop [117] designs a soft reward mechanism instead of only relying on binary rewards, as well as the dropout action, which enables more effective path exploration.”
Language Generation with Multi-hop Reasoning on Commonsense Knowledge Graph (2020, methodology): “…structure has been demonstrated to be an effective approach for query answering over incomplete knowledge graphs (Das et al., 2018; Chen et al., 2018; Lin et al., 2018), multi-hop question answering (Bauer et al., 2018; Cao et al., 2019; Qiu et al., 2019) 2019; Moon et al., 2019; Liu et al., 2019).”
Avoiding Reasoning Shortcuts: Adversarial Evaluation, Training, and Model Development for Multi-Hop QA (2019, background): “Earlier attempts in multi-hop QA focused on reasoning about the relations in a knowledge base (Jain, 2016; Zhou et al., 2018; Lin et al., 2018) or tables (Yin et al., 2015).”
Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction (2021, methodology): “While these methods can produce interpretable paths, they suffer from extremely sparse rewards and require careful engineering of the reward function [38] or the search strategy [50].”
Do Transformers Really Perform Badly for Graph Representation? (2021, background): “The attention mechanism needs to estimate correlations for each node pair ( v i , v j ) , and we believe the edges connecting them should be considered in the correlation as in [34, 47].”
Explore, Propose, and Assemble: An Interpretable Model for Multi-Hop Reading Comprehension (2019, neutral): “Earlier attempts in multi-hop MRC focused on reasoning about the relations in a knowledge base (Jain, 2016; Zhou et al., 2018; Lin et al., 2018) or tables (Yin et al., 2015).”
A Survey on Knowledge Graphs: Representation, Acquisition, and Applications (2020, methodology): “Diversity − 1 |F | ∑|F | i=1 cos (p,pi) MINERVA [73] (et, es, rq, eq) {(et, r, v)} I {et = eq} ht = LSTM (ht−1, [at−1; ot]) Multi-Hop [74] (et, (es, rq)) {( r′, e′ ) | ( et, r ′, e′ ) ∈ G } γ + (1− γ) frq (es, eT ) ht = LSTM (ht−1, at−1)”
Transfer Learning in Deep Reinforcement Learning: A Survey (2020, methodology): “Examples include learning from expert demonstrations for Spoken Dialogue Systems [154], VQA [152]; or reward shaping for Sequence Generation [155], Spoken Dialogue Systems [80], QA [81], [156], and Image Caption [153], or transferring policies for Structured Prediction [157] and VQA [158].”