Zero-shot Graph Reasoning via Retrieval Augmented Framework with LLMs

2025/09/16 by Hanqing Li, Li, Hanqing, K. Jyothi +5
Computer Science · #Artificial Intelligence (cs.AI) #Computation and Language (cs.CL) #FOS: Computer and information sciences #Natural Language Processing Techniques #Semantic Web and Ontologies #Topic Modeling

paper · pdf · doi:10.48550/arxiv.2509.12743

openalex publication_date 2025/09/16 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28

Abstract

We propose a new, training-free method, Graph Reasoning via Retrieval Augmented Framework (GRRAF), that harnesses retrieval-augmented 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.

Citations

• LangGFM: A Large Language Model Alone Can be a Powerful Graph Foundation Model
• Scalable and Accurate Graph Reasoning with LLM-based Multi-Agents
• Graph Reasoning with Large Language Models via Pseudo-code Prompting
• Graph Retrieval-Augmented Generation: A Survey
• HybridRAG: Integrating Knowledge Graphs and Vector Retrieval Augmented Generation for Efficient Information Extraction
• GraphArena: Evaluating and Exploring Large Language Models on Graph Computation
• GNN-RAG: Graph Neural Retrieval for Large Language Model Reasoning
• From Local to Global: A Graph RAG Approach to Query-Focused Summarization
• Graph-Based Retriever Captures the Long Tail of Biomedical Knowledge
• LLM4DyG: Can Large Language Models Solve Spatial-Temporal Problems on Dynamic Graphs?
• Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning
• GraphText: Graph Reasoning in Text Space
• Knowledge Graph Prompting for Multi-Document Question Answering
• Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph
• Text-To-KG Alignment: Comparing Current Methods on Classification Tasks
• GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking
• StructGPT: A General Framework for Large Language Model to Reason over Structured Data
• Graph-ToolFormer: To Empower LLMs with Graph Reasoning Ability via Prompt Augmented by ChatGPT
• GrapeQA: GRaph Augmentation and Pruning to Enhance Question-Answering
• TIARA: Multi-grained Retrieval for Robust Question Answering over Large Knowledge Bases
• DecAF: Joint Decoding of Answers and Logical Forms for Question Answering over Knowledge Bases
• QA-GNN: Reasoning with Language Models and Knowledge Graphs for Question Answering
• Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks
• KagNet: Knowledge-Aware Graph Networks for Commonsense Reasoning
• A Comprehensive Survey on Graph Neural Networks
• The Graph Neural Network Model

Related

• GRAIL:Learning to Interact with Large Knowledge Graphs for Retrieval Augmented Reasoning
• Reasoning by Exploration: A Unified Approach to Retrieval and Generation over Graphs
• GraphRunner: A Multi-Stage Framework for Efficient and Accurate Graph-Based Retrieval
• AGRAG: Advanced Graph-based Retrieval-Augmented Generation for LLMs
• GLM-RAG: Graph Language Models for Graph-Based Retrieval-Augmented Generation