  Knowledge Graph Question Answering (KGQA) involves retrieving entities as
answers from a Knowledge Graph (KG) using natural language queries. The
challenge is to learn to reason over question-relevant KG facts that traverse
KG entities and lead to the question answers. To facilitate reasoning, the
question is decoded into instructions, which are dense question representations
used to guide the KG traversals. However, if the derived instructions do not
exactly match the underlying KG information, they may lead to reasoning under
irrelevant context. Our method, termed ReaRev, introduces a new way to KGQA
reasoning with respect to both instruction decoding and execution. To improve
instruction decoding, we perform reasoning in an adaptive manner, where
KG-aware information is used to iteratively update the initial instructions. To
improve instruction execution, we emulate breadth-first search (BFS) with graph
neural networks (GNNs). The BFS strategy treats the instructions as a set and
allows our method to decide on their execution order on the fly. Experimental
results on three KGQA benchmarks demonstrate the ReaRev's effectiveness
compared with previous state-of-the-art, especially when the KG is incomplete
or when we tackle complex questions. Our code is publicly available at
https://github.com/cmavro/ReaRev_KGQA.
