Zero-shot Graph Reasoning via Retrieval Augmented Framework with LLMs

• URL: http://arxiv.org/abs/2509.12743v1
• Date: Tue, 16 Sep 2025 06:58:58 GMT
• Title: Zero-shot Graph Reasoning via Retrieval Augmented Framework with LLMs
• Authors: Hanqing Li, Kiran Sheena Jyothi, Henry Liang, Sharika Mahadevan, Diego Klabjan,
• Abstract summary: We propose a new, training-free method, Graph Reasoning via Retrieval Augmented Framework (GRRAF)<n> GRRAF harnesses retrieval-augmented generation (RAG) alongside the code-generation capabilities of large language models (LLMs) to address a wide range of graph reasoning tasks.<n> Experimental evaluations on the GraphInstruct dataset reveal that GRRAF achieves 100% accuracy on most graph reasoning tasks.
• Score: 15.558119182035995
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• ProGraph-R1: Progress-aware Reinforcement Learning for Graph Retrieval Augmented Generation [37.11787010202267]
  We propose ProGraph-R1, a progress-aware agentic framework for graph-based retrieval and multi-step reasoning.<n>ProGraph-R1 introduces a structure-aware hypergraph retrieval mechanism that jointly considers semantic relevance and graph connectivity.<n> Experiments on multi-hop question answering benchmarks demonstrate that ProGraph-R1 consistently improves reasoning accuracy and generation quality over existing GraphRAG methods.
  arXiv  Detail & Related papers  (2026-01-25T08:58:44Z)
• AutoGraph-R1: End-to-End Reinforcement Learning for Knowledge Graph Construction [60.51319139563509]
  We introduce AutoGraph-R1, the first framework to directly optimize KG construction for task performance using Reinforcement Learning (RL)<n>We design two novel, task-aware reward functions, one for graphs as knowledge carriers and another as knowledge indices.<n>Our work shows it is possible to close the loop between construction and application, shifting the paradigm from building intrinsically good'' graphs to building demonstrably useful'' ones.
  arXiv  Detail & Related papers  (2025-10-17T06:03:36Z)
• Enrich-on-Graph: Query-Graph Alignment for Complex Reasoning with LLM Enriching [61.824094419641575]
  Large Language Models (LLMs) struggle with hallucinations and factual errors in knowledge-intensive scenarios like knowledge graph question answering (KGQA)<n>We attribute this to the semantic gap between structured knowledge graphs (KGs) and unstructured queries, caused by inherent differences in their focuses and structures.<n>Existing methods usually employ resource-intensive, non-scalable reasoning on vanilla KGs, but overlook this gap.<n>We propose a flexible framework, Enrich-on-Graph (EoG), which leverages LLMs' prior knowledge to enrich KGs, bridge the semantic gap between graphs and queries.
  arXiv  Detail & Related papers  (2025-09-25T06:48:52Z)
• GRAIL:Learning to Interact with Large Knowledge Graphs for Retrieval Augmented Reasoning [13.481673780508215]
  GRAIL is a framework designed to interact with large-scale graphs for retrieval-augmented reasoning.<n>GRAIL achieves an average accuracy improvement of 21.01% and F1 improvement of 22.43% on knowledge graph question-answering datasets.
  arXiv  Detail & Related papers  (2025-08-07T15:34:41Z)
• GraphRunner: A Multi-Stage Framework for Efficient and Accurate Graph-Based Retrieval [3.792463570467098]
  GraphRunner is a novel graph-based retrieval framework that operates in three distinct stages: planning, verification, and execution.<n>It significantly reduces reasoning errors and detects hallucinations before execution.<n>Our evaluation using the GRBench dataset shows that GraphRunner consistently outperforms existing approaches.
  arXiv  Detail & Related papers  (2025-07-11T18:10:01Z)
• E^2GraphRAG: Streamlining Graph-based RAG for High Efficiency and Effectiveness [15.829377965705746]
  We propose E2GraphRAG, a streamlined graph-based RAG framework.<n>E2GraphRAG achieves up to 10 times faster indexing than GraphRAG and 100 times speedup over LightRAG in retrieval.
  arXiv  Detail & Related papers  (2025-05-30T05:27:40Z)
• Align-GRAG: Reasoning-Guided Dual Alignment for Graph Retrieval-Augmented Generation [75.9865035064794]
  Large language models (LLMs) have demonstrated remarkable capabilities, but still struggle with issues like hallucinations and outdated information.<n>Retrieval-augmented generation (RAG) addresses these issues by grounding LLM outputs in external knowledge with an Information Retrieval (IR) system.<n>We propose Align-GRAG, a novel reasoning-guided dual alignment framework in post-retrieval phrase.
  arXiv  Detail & Related papers  (2025-05-22T05:15:27Z)
• NodeRAG: Structuring Graph-based RAG with Heterogeneous Nodes [25.173078967881803]
  Retrieval-augmented generation (RAG) empowers large language models to access external and private corpus.<n>Current graph-based RAG approaches seldom prioritize the design of graph structures.<n>Inadequately designed graph not only impede the seamless integration of diverse graph algorithms but also result in workflow inconsistencies.<n>We propose NodeRAG, a graph-centric framework introducing heterogeneous graph structures.
  arXiv  Detail & Related papers  (2025-04-15T18:24:00Z)
• RGL: A Graph-Centric, Modular Framework for Efficient Retrieval-Augmented Generation on Graphs [58.10503898336799]
  We introduce the RAG-on-Graphs Library (RGL), a modular framework that seamlessly integrates the complete RAG pipeline.<n>RGL addresses key challenges by supporting a variety of graph formats and integrating optimized implementations for essential components.<n>Our evaluations demonstrate that RGL not only accelerates the prototyping process but also enhances the performance and applicability of graph-based RAG systems.
  arXiv  Detail & Related papers  (2025-03-25T03:21:48Z)
• Revisiting Graph Neural Networks on Graph-level Tasks: Comprehensive Experiments, Analysis, and Improvements [54.006506479865344]
  We propose a unified evaluation framework for graph-level Graph Neural Networks (GNNs)<n>This framework provides a standardized setting to evaluate GNNs across diverse datasets.<n>We also propose a novel GNN model with enhanced expressivity and generalization capabilities.
  arXiv  Detail & Related papers  (2025-01-01T08:48:53Z)
• Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models [88.4320775961431]
  We introduce ProGraph, a benchmark for large language models (LLMs) to process graphs.<n>Our findings reveal that the performance of current LLMs is unsatisfactory, with the best model achieving only 36% accuracy.<n>We propose LLM4Graph datasets, which include crawled documents and auto-generated codes based on 6 widely used graph libraries.
  arXiv  Detail & Related papers  (2024-09-29T11:38:45Z)
• G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering [61.93058781222079]
  We develop a flexible question-answering framework targeting real-world textual graphs. We introduce the first retrieval-augmented generation (RAG) approach for general textual graphs. G-Retriever performs RAG over a graph by formulating this task as a Prize-Collecting Steiner Tree optimization problem.
  arXiv  Detail & Related papers  (2024-02-12T13:13:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.