  Reasoning on large-scale knowledge graphs has been long dominated by
embedding methods. While path-based methods possess the inductive capacity that
embeddings lack, their scalability is limited by the exponential number of
paths. Here we present A*Net, a scalable path-based method for knowledge graph
reasoning. Inspired by the A* algorithm for shortest path problems, our A*Net
learns a priority function to select important nodes and edges at each
iteration, to reduce time and memory footprint for both training and inference.
The ratio of selected nodes and edges can be specified to trade off between
performance and efficiency. 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, while merely
visiting 10% nodes and 10% edges at each iteration. On a million-scale dataset
ogbl-wikikg2, A*Net not only achieves a new state-of-the-art result, but also
converges faster than embedding methods. A*Net is the first path-based method
for knowledge graph reasoning at such scale.
