Deepening the IDA* algorithm for knowledge graph reasoning through neural network architecture

Abstract Inferring missing links in Knowledge Graphs (KGs) is a key evaluation task for KG reasoning, which aims to find relations for a given entity pair. Existing research often employs the IDA* (Iterative Deepening A*) algorithm for the path discovery task owing to its efficiency and accuracy. However, it relies on heuristics to set cost functions and is also difficult to utilize useful context information in the search process. In this paper, we propose the Deep-IDA* framework which applies neural networks and reinforcement learning (RL) to empower the IDA* algorithm to tackle the path discovery problem in KG reasoning. We model KG reasoning as a Markov Decision Process (MDP) and divide our Deep-IDA* framework and the resulting path into two parts: path-finding and path-reasoning. For path-finding, we propose a policy network to model the cost from the source to a candidate location. In this process, we employ the GCN (Graph Convolutional Network) to embed the observable sub-track, then employ the LSTM (Long Short-Term Memory) to record the historical trajectory, and introduce the attention to utilize the context information, and finally form policy. For path-reasoning with the searched candidate paths passed from the former process, we employ a value network to estimate the cost from the candidate to the destination entity, using the GNN (Graph Neural Networks) to learn a message-passing algorithm that solves the path inference problem, and using the GRU (Gated Recurrent Unit) to update the historical information. Finally, the actor-learner algorithm is utilized to minimize the sum of the losses of the two parts. Experiment results on three datasets demonstrate the effectiveness and efficiency of our framework.