A*Net: A Scalable Path-based Reasoning Approach for Knowledge Graphs
This addresses the problem of inefficient reasoning on large knowledge graphs for AI researchers, offering a scalable path-based method that is incremental in improving efficiency.
The paper tackles the scalability issue of path-based reasoning on knowledge graphs by introducing A*Net, which uses a learned priority function to select only 10% of nodes and edges per iteration, achieving competitive performance and faster convergence on large-scale datasets.
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.