# A*Net: A Scalable Path-based Reasoning Approach for Knowledge Graphs

arXiv: https://arxiv.org/abs/2206.04798 · HTML: https://mlsanity.com/paper/2206.04798/

## Key facts

- Cited by 49 papers in the map (data through 14 Oct 2026).
- Builds on 43 of its 62 references that are in the map.
- First posted on arXiv 7 Jun 2022.

## Builds on (most cited first, 30 of 43)

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Embedding Entities and Relations for Learning and Inference in Knowledge Bases](https://mlsanity.com/paper/1412.6575/) (2014)
- [Complex Embeddings for Simple Link Prediction](https://mlsanity.com/paper/1606.06357/) (2016)
- [RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space](https://mlsanity.com/paper/1902.10197/) (2019)
- [Convolutional 2D Knowledge Graph Embeddings](https://mlsanity.com/paper/1707.01476/) (2017)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Composition-based Multi-Relational Graph Convolutional Networks](https://mlsanity.com/paper/1911.03082/) (2019)
- [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](https://mlsanity.com/paper/2103.09430/) (2021)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning](https://mlsanity.com/paper/1707.06690/) (2017)
- [Inductive Relation Prediction by Subgraph Reasoning](https://mlsanity.com/paper/1911.06962/) (2019)
- [Low-Dimensional Hyperbolic Knowledge Graph Embeddings](https://mlsanity.com/paper/2005.00545/) (2020)
- [Adaptive Sampling Towards Fast Graph Representation Learning](https://mlsanity.com/paper/1809.05343/) (2018)
- [DRUM: End-To-End Differentiable Rule Mining On Knowledge Graphs](https://mlsanity.com/paper/1911.00055/) (2019)
- [Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning](https://mlsanity.com/paper/1711.05851/) (2017)
- [Learning Hierarchy-Aware Knowledge Graph Embeddings for Link Prediction](https://mlsanity.com/paper/1911.09419/) (2019)
- [RNNLogic: Learning Logic Rules for Reasoning on Knowledge Graphs](https://mlsanity.com/paper/2010.04029/) (2020)
- [Multi-Hop Knowledge Graph Reasoning with Reward Shaping](https://mlsanity.com/paper/1808.10568/) (2018)
- [Knowledge Graph Reasoning with Relational Digraph](https://mlsanity.com/paper/2108.06040/) (2021)
- [Scalable Graph Neural Networks via Bidirectional Propagation](https://mlsanity.com/paper/2010.15421/) (2020)
- [DGL-KE: Training Knowledge Graph Embeddings at Scale](https://mlsanity.com/paper/2004.08532/) (2020)
- [PairRE: Knowledge Graph Embeddings via Paired Relation Vectors](https://mlsanity.com/paper/2011.03798/) (2020)
- [Relational Message Passing for Knowledge Graph Completion](https://mlsanity.com/paper/2002.06757/) (2020)

## Built on by (most cited first, 30 of 49)

- [A Survey of Knowledge Graph Reasoning on Graph Types: Static, Dynamic, and Multimodal](https://mlsanity.com/paper/2212.05767/) (2022)
- [Towards Foundation Models for Knowledge Graph Reasoning](https://mlsanity.com/paper/2310.04562/) (2023)
- [A Prompt-Based Knowledge Graph Foundation Model for Universal In-Context Reasoning](https://mlsanity.com/paper/2410.12288/) (2024)
- [How Expressive are Knowledge Graph Foundation Models?](https://mlsanity.com/paper/2502.13339/) (2025)
- [A Foundation Model for Zero-shot Logical Query Reasoning](https://mlsanity.com/paper/2404.07198/) (2024)
- [LLM as Prompter: Low-resource Inductive Reasoning on Arbitrary Knowledge Graphs](https://mlsanity.com/paper/2402.11804/) (2024)
- [Combating Bilateral Edge Noise for Robust Link Prediction](https://mlsanity.com/paper/2311.01196/) (2023)
- [Link Prediction with Relational Hypergraphs](https://mlsanity.com/paper/2402.04062/) (2024)
- [Flock: A Knowledge Graph Foundation Model via Learning on Random Walks](https://mlsanity.com/paper/2510.01510/) (2025)
- [Understanding Expressivity of GNN in Rule Learning](https://mlsanity.com/paper/2303.12306/) (2023)
- [GraphOracle: Efficient Fully-Inductive Knowledge Graph Reasoning via Relation-Dependency Graphs](https://mlsanity.com/paper/2505.11125/) (2025)
- [HYPER: A Foundation Model for Inductive Link Prediction with Knowledge Hypergraphs](https://mlsanity.com/paper/2506.12362/) (2025)
- [Towards Graph Foundation Models: Training on Knowledge Graphs Enables Transferability to General Graphs](https://mlsanity.com/paper/2410.12609/) (2024)
- [KnowFormer: Revisiting Transformers for Knowledge Graph Reasoning](https://mlsanity.com/paper/2409.12865/) (2024)
- [Mixture of Length and Pruning Experts for Knowledge Graphs Reasoning](https://mlsanity.com/paper/2507.20498/) (2025)
- [River of No Return: Graph Percolation Embeddings for Efficient Knowledge Graph Reasoning](https://mlsanity.com/paper/2305.09974/) (2023)
- [DuetGraph: Coarse-to-Fine Knowledge Graph Reasoning with Dual-Pathway Global-Local Fusion](https://mlsanity.com/paper/2507.11229/) (2025)
- [Leveraging LLM-GNN Integration for Open-World Question Answering over Knowledge Graphs](https://mlsanity.com/paper/2604.13979/) (2026)
- [Faithful Differentiable Reasoning with Reshuffled Region-based Embeddings](https://mlsanity.com/paper/2406.09529/) (2024)
- [Towards Better Benchmark Datasets for Inductive Knowledge Graph Completion](https://mlsanity.com/paper/2406.11898/) (2024)
- [Expanding the Scope: Inductive Knowledge Graph Reasoning with Multi-Starting Progressive Propagation](https://mlsanity.com/paper/2407.10430/) (2024)
- [Talking to GDELT Through Knowledge Graphs](https://mlsanity.com/paper/2503.07584/) (2025)
- [Optimal Embedding Guided Negative Sample Generation for Knowledge Graph Link Prediction](https://mlsanity.com/paper/2504.03327/) (2025)
- [Beyond Completion: A Foundation Model for General Knowledge Graph Reasoning](https://mlsanity.com/paper/2505.21926/) (2025)
- [Geometric Structural Knowledge Graph Foundation Model](https://mlsanity.com/paper/2512.22931/) (2025)
- [Half a Link can Be Enough to Predict a Whole Link: Understanding Generalization in Knowledge Graph Foundation Models](https://mlsanity.com/paper/2606.18001/) (2026)
- [Reevaluation of Inductive Link Prediction](https://mlsanity.com/paper/2409.20130/) (2024)
- [From Primes to Paths: Enabling Fast Multi-Relational Graph Analysis](https://mlsanity.com/paper/2411.11149/) (2024)
- [Domain and Range Aware Synthetic Negatives Generation for Knowledge Graph Embedding Models](https://mlsanity.com/paper/2411.14858/) (2024)
- [S2DN: Learning to Denoise Unconvincing Knowledge for Inductive Knowledge Graph Completion](https://mlsanity.com/paper/2412.15822/) (2024)

## Abstract (arXiv)

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.