# SMORE: Knowledge Graph Completion and Multi-hop Reasoning in Massive Knowledge Graphs

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 47 references that are in the map.
- First posted on arXiv 28 Oct 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (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)
- [The Web as a Knowledge-base for Answering Complex Questions](https://mlsanity.com/paper/1803.06643/) (2018)
- [QA-GNN: Reasoning with Language Models and Knowledge Graphs for Question Answering](https://mlsanity.com/paper/2104.06378/) (2021)
- [Modeling polypharmacy side effects with graph convolutional networks](https://mlsanity.com/paper/1802.00543/) (2018)
- [KagNet: Knowledge-Aware Graph Networks for Commonsense Reasoning](https://mlsanity.com/paper/1909.02151/) (2019)
- [PullNet: Open Domain Question Answering with Iterative Retrieval on Knowledge Bases and Text](https://mlsanity.com/paper/1904.09537/) (2019)
- [Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings](https://mlsanity.com/paper/2002.05969/) (2020)
- [Open Domain Question Answering Using Early Fusion of Knowledge Bases and Text](https://mlsanity.com/paper/1809.00782/) (2018)
- [DKN: Deep Knowledge-Aware Network for News Recommendation](https://mlsanity.com/paper/1801.08284/) (2018)
- [Beta Embeddings for Multi-Hop Logical Reasoning in Knowledge Graphs](https://mlsanity.com/paper/2010.11465/) (2020)
- [Scalable Multi-Hop Relational Reasoning for Knowledge-Aware Question Answering](https://mlsanity.com/paper/2005.00646/) (2020)
- [Embedding Logical Queries on Knowledge Graphs](https://mlsanity.com/paper/1806.01445/) (2018)
- [PyTorch-BigGraph: A Large-scale Graph Embedding System](https://mlsanity.com/paper/1903.12287/) (2019)
- [Knowledge-aware Graph Neural Networks with Label Smoothness Regularization for Recommender Systems](https://mlsanity.com/paper/1905.04413/) (2019)
- [Complex Query Answering with Neural Link Predictors](https://mlsanity.com/paper/2011.03459/) (2020)
- [GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings](https://mlsanity.com/paper/2106.05609/) (2021)
- [ConE: Cone Embeddings for Multi-Hop Reasoning over Knowledge Graphs](https://mlsanity.com/paper/2110.13715/) (2021)
- [Graph-Based Reasoning over Heterogeneous External Knowledge for Commonsense Question Answering](https://mlsanity.com/paper/1909.05311/) (2019)
- [DGL-KE: Training Knowledge Graph Embeddings at Scale](https://mlsanity.com/paper/2004.08532/) (2020)
- [Traversing Knowledge Graphs in Vector Space](https://mlsanity.com/paper/1506.01094/) (2015)
- [Dual Graph Attention Networks for Deep Latent Representation of Multifaceted Social Effects in Recommender Systems](https://mlsanity.com/paper/1903.10433/) (2019)
- [GraphVite: A High-Performance CPU-GPU Hybrid System for Node Embedding](https://mlsanity.com/paper/1903.00757/) (2019)
- [Chains of Reasoning over Entities, Relations, and Text using Recurrent Neural Networks](https://mlsanity.com/paper/1607.01426/) (2016)
- [Marius: Learning Massive Graph Embeddings on a Single Machine](https://mlsanity.com/paper/2101.08358/) (2021)

## Built on by (most cited first, 17 of 17)

- [Knowledge Graphs: Opportunities and Challenges](https://mlsanity.com/paper/2303.13948/) (2023)
- [Mask and Reason: Pre-Training Knowledge Graph Transformers for Complex Logical Queries](https://mlsanity.com/paper/2208.07638/) (2022)
- [Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases](https://mlsanity.com/paper/2303.14617/) (2023)
- [Logical Message Passing Networks with One-hop Inference on Atomic Formulas](https://mlsanity.com/paper/2301.08859/) (2023)
- [GammaE: Gamma Embeddings for Logical Queries on Knowledge Graphs](https://mlsanity.com/paper/2210.15578/) (2022)
- [Wasserstein-Fisher-Rao Embedding: Logical Query Embeddings with Local Comparison and Global Transport](https://mlsanity.com/paper/2305.04034/) (2023)
- [Representation Learning on Hyper-Relational and Numeric Knowledge Graphs with Transformers](https://mlsanity.com/paper/2305.18256/) (2023)
- [Sequential Query Encoding For Complex Query Answering on Knowledge Graphs](https://mlsanity.com/paper/2302.13114/) (2023)
- [Top Ten Challenges Towards Agentic Neural Graph Databases](https://mlsanity.com/paper/2501.14224/) (2025)
- [Knowledge Graph Reasoning over Entities and Numerical Values](https://mlsanity.com/paper/2306.01399/) (2023)
- [LitCQD: Multi-Hop Reasoning in Incomplete Knowledge Graphs with Numeric Literals](https://mlsanity.com/paper/2304.14742/) (2023)
- [Knowledge Graphs Querying](https://mlsanity.com/paper/2305.14485/) (2023)
- [Conditional Logical Message Passing Transformer for Complex Query Answering](https://mlsanity.com/paper/2402.12954/) (2024)
- [NGDB-Zoo: Towards Efficient and Scalable Neural Graph Databases Training](https://mlsanity.com/paper/2602.21597/) (2026)
- [KGCompiler: Deep Learning Compilation Optimization for Knowledge Graph Complex Logical Query Answering](https://mlsanity.com/paper/2503.02172/) (2025)
- [Efficient and Scalable Neural Symbolic Search for Knowledge Graph Complex Query Answering](https://mlsanity.com/paper/2505.08155/) (2025)
- [Interactive Query Answering on Knowledge Graphs with Soft Entity Constraints](https://mlsanity.com/paper/2508.13663/) (2025)

## Abstract (arXiv)

Knowledge graphs (KGs) capture knowledge in the form of head--relation--tail triples and are a crucial component in many AI systems. There are two important reasoning tasks on KGs: (1) single-hop knowledge graph completion, which involves predicting individual links in the KG; and (2), multi-hop reasoning, where the goal is to predict which KG entities satisfy a given logical query. Embedding-based methods solve both tasks by first computing an embedding for each entity and relation, then using them to form predictions. However, existing scalable KG embedding frameworks only support single-hop knowledge graph completion and cannot be applied to the more challenging multi-hop reasoning task. Here we present Scalable Multi-hOp REasoning (SMORE), the first general framework for both single-hop and multi-hop reasoning in KGs. Using a single machine SMORE can perform multi-hop reasoning in Freebase KG (86M entities, 338M edges), which is 1,500x larger than previously considered KGs. The key to SMORE's runtime performance is a novel bidirectional rejection sampling that achieves a square root reduction of the complexity of online training data generation. Furthermore, SMORE exploits asynchronous scheduling, overlapping CPU-based data sampling, GPU-based embedding computation, and frequent CPU--GPU IO. SMORE increases throughput (i.e., training speed) over prior multi-hop KG frameworks by 2.2x with minimal GPU memory requirements (2GB for training 400-dim embeddings on 86M-node Freebase) and achieves near linear speed-up with the number of GPUs. Moreover, on the simpler single-hop knowledge graph completion task SMORE achieves comparable or even better runtime performance to state-of-the-art frameworks on both single GPU and multi-GPU settings.