SQALER: Scaling Question Answering by Decoupling Multi-Hop and Logical Reasoning
This addresses the problem of scaling knowledge graph question answering for AI systems, offering a novel approach that is not incremental.
The paper tackles the scalability issue in reasoning over knowledge graphs by decoupling multi-hop and logical reasoning, enabling linear scaling with relation types rather than edges. It achieves state-of-the-art results on WebQuestionsSP and solves the MetaQA dataset, with orders of magnitude better scalability.
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.