EMNLP Findings2025
Zero-shot Graph Reasoning via Retrieval Augmented Framework with LLMs
Hanqing Li, Sharika Mahadevan, Kiran Sheena Jyothi, Henry Liang, Diego Klabjan
Abstract
We propose a new, training-free method, Graph Reasoning via Retrieval Augmented Framework (GRRAF), that harnesses retrievalaugmented generation (RAG) alongside the code-generation capabilities of large language models (LLMs) to address a wide range of graph reasoning tasks. In GRRAF, the target graph is stored in a graph database, and the LLM is prompted to generate executable code queries that retrieve the necessary information. This approach circumvents the limitations of existing methods that require extensive finetuning or depend on predefined algorithms, and it incorporates an error feedback loop with a time-out mechanism to ensure both correctness and efficiency. Experimental evaluations on the GraphInstruct dataset reveal that GRRAF achieves 100% accuracy on most graph reasoning tasks, including cycle detection, bipartite graph checks, shortest path computation, and maximum flow, while maintaining consistent token costs regardless of graph sizes. Imperfect but still very high performance is observed on subgraph matching. Notably, GRRAF scales effectively to large graphs with up to 10,000 nodes.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering cites Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning
- G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering cites Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks
- Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning cites GreaseLM: Graph REASoning Enhanced Language Models
Cited by top-tier papers1
Builds on24
- Retrieval-Augmented Generation for Knowledge-Intensive NLP TasksPatrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni et al.NeurIPS 2020 · 19,162 citations
- Reasoning on Graphs: Faithful and Interpretable Large Language Model ReasoningLinhao Luo, Yuan-Fang Li, Gholamreza Haffari, Shirui PanICLR 2024 · 499 citations
- G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question AnsweringXiaoxin He, Yijun Tian, Yifei Sun, Nitesh V. Chawla et al.NeurIPS 2024 · 384 citations
- Knowledge Graph Prompting for Multi-Document Question AnsweringYu Wang, Nedim Lipka, Ryan A. Rossi, Alexa F. Siu et al.AAAI 2024 · 290 citations
- GreaseLM: Graph REASoning Enhanced Language ModelsXikun Zhang, Antoine Bosselut, Michihiro Yasunaga, Hongyu Ren et al.ICLR 2022 · 285 citations
Related papers
- Simple is Effective: The Roles of Graphs and Large Language Models in Knowledge-Graph-Based Retrieval-Augmented GenerationMufei Li, Siqi Miao, Pan LiICLR 2025
- GRIL: Knowledge Graph Retrieval-Integrated Learning with Large Language ModelsJialin Chen, Houyu Zhang, Seongjun Yun, Alejandro Mottini et al.EMNLP Findings 2025 · 3 citations
- GraphSkill: Documentation-Guided Agentic Hierarchical Retrieval-Augmented Coding for Complex Graph ReasoningFali Wang, Chenglin Weng, Xianren Zhang, Siyuan Hong et al.KDD 2026
- Reasoning by Exploration: A Unified Approach to Retrieval and Generation over GraphsHaoyu Han, Kai Guo, Harry Shomer, Yu Wang et al.WWW 2026 · 1 citation
- G-reasoner: Foundation Models for Unified Reasoning over Graph-structured KnowledgeLinhao Luo, Zicheng Zhao, Junnan Liu, Zhangchi Qiu et al.ICLR 2026 · 12 citations
