[2110.14890] SMORE: Knowledge Graph Completion and Multi-hop Reasoning in Massive Knowledge Graphs

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.

SMORE: K NOWLEDGE G RAPH C OMPLETION AND M ULTI - HOP R EASONING IN M ASSIVE K NOWLEDGE G RAPHS Hongyu Ren 1 * Hanjun Dai 2 * Bo Dai 2 Xinyun Chen 3 Denny Zhou 2 Jure Leskovec 1 Dale Schuurmans 2 A BSTRACT Knowledge graphs (KGs) capture knowledge in the form of head–relation–tail triples and are a crucial component arXiv:2110.14890v2 [cs.LG] 1 Nov…

related reading

• [2303.13948] Knowledge Graphs: Opportunities and Challengesarxiv.org
• [2005.11401] Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasksarxiv.org
• [2201.11903] Chain of Thought Prompting Elicits Reasoning in Large Language Modelsarxiv.org
• [2106.09685] LoRA: Low-Rank Adaptation of Large Language Modelsarxiv.org
• [2605.15156] MeMo: Memory as a Modelarxiv.org
• 2502.11089arxiv.org
• [2603.07146] Fine-Grained Table Retrieval Through the Lens of Complex Queriesarxiv.org
• [2003.02320] Knowledge Graphsarxiv.org
• [2604.18002] Neural Garbage Collection: Learning to Forget while Learning to Reasonarxiv.org
• [2508.21038] On the Theoretical Limitations of Embedding-Based Retrievalarxiv.org
• [2603.23516] MSA: Memory Sparse Attention for Efficient End-to-End Memory Model Scaling to 100M Tokensarxiv.org
• [2002.08909] REALM: Retrieval-Augmented Language Model Pre-Trainingarxiv.org