  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.
