Learning to Efficiently Propagate for Reasoning on Knowledge Graphs
Path-based methods are more appealing solutions than embedding methods for
knowledge graph reasoning, due to their interpretability and generalization
ability to unseen graphs. However, path-based methods usually suffer from the
problem of scalability, as the time complexity grows exponentially w.r.t. the
length of paths. While recent methods compute reasoning paths with the
Bellman-Ford algorithm in polynomial time, the time and memory cost remains
very high, as they need to propagate through all the nodes and edges in the
graph. In this paper, we propose A*Net, an efficient model for path-based
reasoning on knowledge graphs. Inspired by the classical A* algorithm for
shortest path problems, our A*Net prioritizes important nodes and edges at each
propagation step, to reduce the time and memory footprint. Unlike the classical
A* algorithm that uses a heuristic function, we propose to learn the priority
function for each node to capture the complex semantics in knowledge graphs.
The priority function and the propagation steps are jointly optimized through
backpropagation. Experiments on both transductive and inductive knowledge graph
reasoning benchmarks show that A*Net achieves competitive performance with
existing state-of-the-art path-based methods, and meanwhile reduces the number
of messages, the time and the memory cost up to 7.2$\times$, 3.4$\times$ and
4.9$\times$ respectively.