  Multi-hop reasoning (MHR) is a process in artificial intelligence and natural
language processing where a system needs to make multiple inferential steps to
arrive at a conclusion or answer. In the context of knowledge graphs or
databases, it involves traversing multiple linked entities and relationships to
understand complex queries or perform tasks requiring a deeper understanding.
Multi-hop reasoning is a critical function in various applications, including
question answering, knowledge base completion, and link prediction. It has
garnered significant interest in artificial intelligence, machine learning, and
graph analytics.
  This paper focuses on optimizing MHR for time efficiency on large-scale
graphs, diverging from the traditional emphasis on accuracy which is an
orthogonal goal. We introduce a novel parallel algorithm that harnesses
domain-specific learned embeddings to efficiently identify the top K paths
between vertices in a knowledge graph to find the best answers to a three-hop
query. Our contributions are: (1) We present a new parallel algorithm to
enhance MHR performance, scalability and efficiency. (2) We demonstrate the
algorithm's superior performance on leading-edge Intel and AMD architectures
through empirical results.
  We showcase the algorithm's practicality through a case study on identifying
academic affiliations of potential Turing Award laureates in Deep Learning,
highlighting its capability to handle intricate entity relationships. This
demonstrates the potential of our approach to enabling high-performance MHR,
useful to navigate the growing complexity of modern knowledge graphs.
