SQALER: Scaling Question Answering by Decoupling Multi-Hop and Logical Reasoning

• URL: http://arxiv.org/abs/2110.14266v1
• Date: Wed, 27 Oct 2021 08:40:16 GMT
• Title: SQALER: Scaling Question Answering by Decoupling Multi-Hop and Logical Reasoning
• Authors: Mattia Atzeni, Jasmina Bogojeska, Andreas Loukas
• Abstract summary: We show that multi-hop and more complex logical reasoning can be accomplished separately without losing expressive power. We propose an approach to multi-hop reasoning that scales linearly with the number of relation types in the graph. This produces a set of candidate solutions that can be provably refined to recover the solution to the original problem.
• Score: 34.015606782134206
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: State-of-the-art approaches to reasoning and question answering over knowledge graphs (KGs) usually scale with the number of edges and can only be applied effectively on small instance-dependent subgraphs. In this paper, we address this issue by showing that multi-hop and more complex logical reasoning can be accomplished separately without losing expressive power. Motivated by this insight, we propose an approach to multi-hop reasoning that scales linearly with the number of relation types in the graph, which is usually significantly smaller than the number of edges or nodes. This produces a set of candidate solutions that can be provably refined to recover the solution to the original problem. Our experiments on knowledge-based question answering show that our approach solves the multi-hop MetaQA dataset, achieves a new state-of-the-art on the more challenging WebQuestionsSP, is orders of magnitude more scalable than competitive approaches, and can achieve compositional generalization out of the training distribution.

Related papers

• Think Parallax: Solving Multi-Hop Problems via Multi-View Knowledge-Graph-Based Retrieval-Augmented Generation [2.8890464940342873]
  Large language models (LLMs) excel at language understanding but often hallucinate and struggle with multi-hop reasoning.<n>We propose ParallaxRAG, a framework that symmetrically decouples queries and graph triples into multi-view spaces.<n>Our results highlight multi-view head specialization as a principled direction for knowledge-grounded multi-hop reasoning.
  arXiv  Detail & Related papers  (2025-10-17T11:34:27Z)
• Divide by Question, Conquer by Agent: SPLIT-RAG with Question-Driven Graph Partitioning [62.640169289390535]
  SPLIT-RAG is a multi-agent RAG framework that addresses the limitations with question-driven semantic graph partitioning and collaborative subgraph retrieval.<n>The innovative framework first create Semantic Partitioning of Linked Information, then use the Type-Specialized knowledge base to achieve Multi-Agent RAG.<n>The attribute-aware graph segmentation manages to divide knowledge graphs into semantically coherent subgraphs, ensuring subgraphs align with different query types.<n>A hierarchical merging module resolves inconsistencies across subgraph-derived answers through logical verifications.
  arXiv  Detail & Related papers  (2025-05-20T06:44:34Z)
• Do Larger Language Models Imply Better Generalization? A Pretraining Scaling Law for Implicit Reasoning [89.17086632436363]
  We introduce a synthetic multihop reasoning environment designed to replicate the structure and distribution of real-world large-scale knowledge graphs.<n>Our reasoning task involves completing missing edges in the graph, which requires advanced multi-hop reasoning and mimics real-world reasoning scenarios.<n>To predict the optimal model size for a specific knowledge graph, we find an empirical scaling that linearly maps the knowledge graph search entropy to the optimal model size.
  arXiv  Detail & Related papers  (2025-04-04T17:57:22Z)
• Causal Graphs Meet Thoughts: Enhancing Complex Reasoning in Graph-Augmented LLMs [4.701165676405066]
  It is critical not only to retrieve relevant information but also to provide causal reasoning and explainability. This paper proposes a novel pipeline that filters large knowledge graphs to emphasize cause-effect edges. Experiments on medical question-answering tasks show consistent gains, with up to a 10% absolute improvement.
  arXiv  Detail & Related papers  (2025-01-24T19:31:06Z)
• Symmetry-preserving graph attention network to solve routing problems at multiple resolutions [1.9304772860080408]
  We introduce the first-ever completely equivariant model and training to solve problems. It is essential to capture the multiscale structure of the input graph. We propose a Multiresolution scheme in combination with Equi Graph Attention network (mEGAT) architecture.
  arXiv  Detail & Related papers  (2023-10-24T06:22:20Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Towards Graph-hop Retrieval and Reasoning in Complex Question Answering over Textual Database [15.837457557803507]
  Graph-Hop is a novel multi-chains and multi-hops retrieval and reasoning paradigm in complex question answering. We construct a new benchmark called ReasonGraphQA, which provides explicit and fine-grained evidence graphs for complex questions.
  arXiv  Detail & Related papers  (2023-05-23T16:28:42Z)
• Complexity-Based Prompting for Multi-Step Reasoning [72.0057198610614]
  We study the task of prompting large-scale language models to perform multi-step reasoning. A central question is which reasoning examples make the most effective prompts. We propose complexity-based prompting, a simple and effective example selection scheme for multi-step reasoning.
  arXiv  Detail & Related papers  (2022-10-03T05:33:27Z)
• PGX: A Multi-level GNN Explanation Framework Based on Separate Knowledge Distillation Processes [0.2005299372367689]
  We propose a multi-level GNN explanation framework based on an observation that GNN is a multimodal learning process of multiple components in graph data. The complexity of the original problem is relaxed by breaking into multiple sub-parts represented as a hierarchical structure. We also aim for personalized explanations as the framework can generate different results based on user preferences.
  arXiv  Detail & Related papers  (2022-08-05T10:14:48Z)
• LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation [6.316693022958222]
  We propose a reinforcement learning algorithm that learns how to navigate the space of possible subgraphs using an Euclidean subgraph embedding as its map. LeNSE identifies small subgraphs yielding solutions comparable to those found by running the embeddings on the entire graph, but at a fraction of the total run time.
  arXiv  Detail & Related papers  (2022-05-20T11:54:03Z)
• Modeling Multi-hop Question Answering as Single Sequence Prediction [88.72621430714985]
  We propose a simple generative approach (PathFid) that extends the task beyond just answer generation. PathFid explicitly models the reasoning process to resolve the answer for multi-hop questions. Our experiments demonstrate that PathFid leads to strong performance gains on two multi-hop QA datasets.
  arXiv  Detail & Related papers  (2022-05-18T21:57:59Z)
• Graph Neural Networks for Propositional Model Counting [1.0152838128195467]
  Graph Networks (GNNs) have been recently leveraged to solve logical reasoning tasks. We present an architecture based on the GNN framework for belief propagation (BP) of Kuch et al., extended with self-attentive GNN and trained to approximately solve the #SAT problem.
  arXiv  Detail & Related papers  (2022-05-09T17:03:13Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  We study a new subclass of POMDPs, whose latent states can be decoded by the most recent history of a short length $m$. In particular, in the rich-observation setting, we develop new algorithms using a novel "moment matching" approach with a sample complexity that scales exponentially. Our results show that a short-term memory suffices for reinforcement learning in these environments.
  arXiv  Detail & Related papers  (2022-02-08T16:39:57Z)
• Dynamic Semantic Graph Construction and Reasoning for Explainable Multi-hop Science Question Answering [50.546622625151926]
  We propose a new framework to exploit more valid facts while obtaining explainability for multi-hop QA. Our framework contains three new ideas: (a) tt AMR-SG, an AMR-based Semantic Graph, constructed by candidate fact AMRs to uncover any hop relations among question, answer and multiple facts, (b) a novel path-based fact analytics approach exploiting tt AMR-SG to extract active facts from a large fact pool to answer questions, and (c) a fact-level relation modeling leveraging graph convolution network (GCN) to guide the reasoning process.
  arXiv  Detail & Related papers  (2021-05-25T09:14:55Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.