# Reasoning of Large Language Models over Knowledge Graphs with Super-Relations

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 7 of its 36 references that are in the map.
- First posted on arXiv 28 Mar 2025.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 7 of 7)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [GNN-RAG: Graph Neural Retrieval for Large Language Model Reasoning](https://mlsanity.com/paper/2405.20139/) (2024)
- [Large-scale Simple Question Answering with Memory Networks](https://mlsanity.com/paper/1506.02075/) (2015)
- [KG-Agent: An Efficient Autonomous Agent Framework for Complex Reasoning over Knowledge Graph](https://mlsanity.com/paper/2402.11163/) (2024)
- [Think-on-Graph 2.0: Deep and Faithful Large Language Model Reasoning with Knowledge-guided Retrieval Augmented Generation](https://mlsanity.com/paper/2407.10805/) (2024)

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

- [AnyMAC: Cascading Flexible Multi-Agent Collaboration via Next-Agent Prediction](https://mlsanity.com/paper/2506.17784/) (2025)
- [VistaWise: Building Cost-Effective Agent with Cross-Modal Knowledge Graph for Minecraft](https://mlsanity.com/paper/2508.18722/) (2025)
- [Diagnosing and Addressing Pitfalls in KG-RAG Datasets: Toward More Reliable Benchmarking](https://mlsanity.com/paper/2505.23495/) (2025)
- [GraphRAFT: Retrieval Augmented Fine-Tuning for Knowledge Graphs on Graph Databases](https://mlsanity.com/paper/2504.05478/) (2025)
- [Efficient and Transferable Agentic Knowledge Graph RAG via Reinforcement Learning](https://mlsanity.com/paper/2509.26383/) (2025)
- [Search-on-Graph: Iterative Informed Navigation for Large Language Model Reasoning on Knowledge Graphs](https://mlsanity.com/paper/2510.08825/) (2025)
- [Temporal Reasoning with Large Language Models Augmented by Evolving Knowledge Graphs](https://mlsanity.com/paper/2509.15464/) (2025)
- [RJE: A Retrieval-Judgment-Exploration Framework for Efficient Knowledge Graph Question Answering with LLMs](https://mlsanity.com/paper/2510.01257/) (2025)
- [TinyGraphEstimator: Adapting Lightweight Language Models for Graph Structure Inference](https://mlsanity.com/paper/2510.08808/) (2025)
- [ProgRAG: Hallucination-Resistant Progressive Retrieval and Reasoning over Knowledge Graphs](https://mlsanity.com/paper/2511.10240/) (2025)
- [Code-on-Graph: Iterative Programmatic Reasoning via Large Language Models on Knowledge Graphs](https://mlsanity.com/paper/2606.03705/) (2026)
- [Towards Open-World Retrieval-Augmented Generation on Knowledge Graph: A Multi-Agent Collaboration Framework](https://mlsanity.com/paper/2509.01238/) (2025)
- [Explore-on-Graph: Incentivizing Autonomous Exploration of Large Language Models on Knowledge Graphs with Path-refined Reward Modeling](https://mlsanity.com/paper/2602.21728/) (2026)
- [TARS: MinMax Token-Adaptive Preference Strategy for Hallucination Reduction in MLLMs](https://mlsanity.com/paper/2507.21584/) (2025)
- [TITAN: Graph-Executable Reasoning for Cyber Threat Intelligence](https://mlsanity.com/paper/2510.14670/) (2025)
- [Separate the Wheat from the Chaff: Winnowing Down Divergent Views in Retrieval Augmented Generation](https://mlsanity.com/paper/2511.04700/) (2025)
- [LogosKG: Hardware-Optimized Scalable and Interpretable Knowledge Graph Retrieval](https://mlsanity.com/paper/2604.18913/) (2026)
- [STEM: Structure-Tracing Evidence Mining for Knowledge Graphs-Driven Retrieval-Augmented Generation](https://mlsanity.com/paper/2604.22282/) (2026)
- [AGE: Adaptive-masking for Graph Embedding in Graph Retrieval-Augmented Generation](https://mlsanity.com/paper/2607.00052/) (2026)
- [TRIAGE: Trustworthy Retrieval Instrumentation And Graph Evaluation](https://mlsanity.com/paper/2607.03447/) (2026)
- [Cognition on Graph: Navigating Massive Knowledge Space via Cognitive Cycles and Bidirectional Graph-Text Synergy](https://mlsanity.com/paper/2609.12791/) (2026)

## Abstract (arXiv)

While large language models (LLMs) have made significant progress in processing and reasoning over knowledge graphs, current methods suffer from a high non-retrieval rate. This limitation reduces the accuracy of answering questions based on these graphs. Our analysis reveals that the combination of greedy search and forward reasoning is a major contributor to this issue. To overcome these challenges, we introduce the concept of super-relations, which enables both forward and backward reasoning by summarizing and connecting various relational paths within the graph. This holistic approach not only expands the search space, but also significantly improves retrieval efficiency. In this paper, we propose the ReKnoS framework, which aims to Reason over Knowledge Graphs with Super-Relations. Our framework's key advantages include the inclusion of multiple relation paths through super-relations, enhanced forward and backward reasoning capabilities, and increased efficiency in querying LLMs. These enhancements collectively lead to a substantial improvement in the successful retrieval rate and overall reasoning performance. We conduct extensive experiments on nine real-world datasets to evaluate ReKnoS, and the results demonstrate the superior performance of ReKnoS over existing state-of-the-art baselines, with an average accuracy gain of 2.92%.