Zero-shot Graph Reasoning via Retrieval Augmented Framework with LLM s (2025)

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.

## introduction graph reasoning plays a pivotal role in modeling and understanding complex systems across numerous domains @xcite . graphs naturally represent entities and their interrelations in areas such as social networks, transportation systems, biological networks, and communication infrastructures. graph reasoning tasks like determining connectivity, detecting cycles, and finding the shortest path are not only central to theoretical computer science but also have practical implications in network optimization, anomaly detection, decision support systems, etc @xcite . however, addressing these tasks requires a deep understanding of graph topology combined with pre-figure 1 : a schematic representation of the grraf concept. when a user asks a graph reasoning question, the llm generates code to query the target graph stored in a graph database, retrieves the answer, and presents it as the response. an error feedback loop is integrated into grraf to prompt the llm to refine the code whenever execution or time-out errors occur. cise computational procedures, underscoring the critical challenge of developing efficient graph reasoning methods in contemporary machine learning research @xcite . large language models (llms) have demonstrated an impressive capacity for multi-step reasoning, which enables them to interpret complex graphrelated questions expressed in natural language and generate human-readable responses @xcite . several recent studies have leveraged llms to tackle graph reasoning problems by converting graph structures into textual representations or latent embeddings through graph neural networks (gnns), thereby exploiting the powerful natural language reasoning capabilities of llms @xcite @xcite @xcite @xcite . however, even when advanced prompting techniques are employed, these methods tend to perform poorly on fundamental graph reasoning tasks, such as evaluating connectivity or identifying the shortest path, with average accuracies ranging from 20% to 60%. alternative approaches that achieve higher accuracy typically either require extensive finetuning-which results in poor performance on out-of-domain questions @xcite -or rely on predefined algorithms as input, thereby limiting their ability to address unseen tasks @xcite . to address these limitations, we introduce a training-free and zero-shot method, the graph reasoning via retrieval augmented framework (gr-raf), that leverages retrieval-augmented generation (rag) @xcite alongside the code-writing capabilities of large language models. in grraf, the target graph is stored in a graph database, and the llm is prompted to generate appropriate queries, written as code, that extract the desired answer by retrieving relevant information from the database. this strategy harnesses the llm's robust reasoning ability and its proficiency in generating executable code, thereby achieving high accuracy on a range of graph reasoning tasks without requiring additional finetuning or predefined algorithms. in addition, we incorporate an error feedback loop combined with a time-out mechanism to ensure that the llm produces correct queries in a time-efficient manner. furthermore, since accurate code reliably yields the correct answer regardless of the graph's size, grraf can easily scale for polynomial problems to accommodate larger graphs without a drop in accuracy. in grraf, we use neo4j, an interactive graph database, and networkx, a python library for graphs. grraf accepts the target graph as either plain text or data already stored in neo4j, specified in the prompt by the graph file name. in the former case, the prompt must specify if neo4j or networkx is to be used. the llm then must either create code to insert the graph specified in the prompt to neo4j or to a networkx graph object. grraf offers a fully automated, end-to-end framework for handling graph-reasoning problems written entirely in text. by leveraging the world knowledge encoded in llms, it generates correct code and returns accurate answers automatically for a wide range of graph-reasoning tasks expressed as natural-language questions. in addition, grraf establishes a foundation for future work on real-world structured relational-inference problems-ranging from knowledge-graph com-pletion to molecular analysis-that are naturally represented as graph-structured data. an llm user could potentially accomplish the same by directly prompting the llm to create python or neo4j queries for the task on hand. our approach offers the benefits of graph reading and loading, the execution of the code with the error-feedback loop, and the fallback approach. experimental results demonstrate that grraf achieves 100% accuracy on many graph reasoning tasks, outperforming state-of-the-art benchmarks. moreover, grraf is applicable to large graphs containing up to 10,000 nodes, maintaining 100% accuracy with no increase in token cost. although grraf only achieves 86.5% accuracy on subgraph matching, it still outperforms other stateof-the-art methods. our contributions are listed below. the proposed method achieves state-of-the-art accuracy and demonstrates exceptional scalability, being the first to handle large graphs effectively without significant degradation in accuracy or substantial cost increases. all implementations and datasets are available in https://github.com/hanklee97121/grraf/ tree/main . ## method in this section, we explain how grraf integrates rag to address graph reasoning questions and retrieve accurate answers. the entire workflow of grraf is demonstrated in figure 2 . a graph reasoning question, denoted as q, consists of two components: a graph g and a user prompt p . the graph g represents the target graph associated with q and is stored either in neo4j or as a networkx graph object (code written by an llm and executed by an agent). the prompt p contains a graph-specific question regarding g (e.g., "does node 2 connect to node 5?" or "what is the shortest path from node 5 to node 8?"). to enhance code generation by the language model, we initially input p into the llm, requesting it to refine the prompt, clarify the format, and eliminate redundant information. the resulting refined prompt is denoted as p ′ . then, the llm is prompted to generate a generic code template c that addresses p ′ without incorporating graphspecific details. for example, if p ′ states "find the shortest path from node 3 to node 5," the template c encapsulates a generic shortest path algorithm that does not include the specific node identifiers. additionally, we extract the schema s (comprising of node properties and edge properties) from the graph database using a hard-coded procedure. this schema ensures that the llm-generated code utilizes correct variable names. subsequently, we provide p ′ , c, and s to the llm and instruct it to generate the final code c ′ that produces an answer a corresponding to p ′ . an error feedback loop is incorporated into this process. if an error arises during the execution of c ′ , the error message, along with c ′ , is supplied back to the llm, prompting it to produce a revised version of the code. to promote the generation of time-efficient code, given that multiple algorithms with varying time complexities may be applicable, we integrate a time-out mechanism within the error feedback loop. specifically, a time limit t is imposed on the execution of c ′ . if the execution time exceeds t, the process is halted, and the llm is asked to modify c ′ so that it runs faster. if the feedback loop iterates more than n times, the system reverts to using the original question q as a prompt to directly obtain the answer a from the llm. this forced exit is designed to prevent perpetual itera-tions when addressing computationally intractable np-hard problems (e.g., substructure matching on large graphs), where no modification of c ′ can reduce the execution time below the threshold t. in the final step, the answer a is provided to the llm to generate a reader-friendly natural language response a 0 that addresses the graph reasoning question q. an example of solving a graph reasoning question with grraf is demonstrated in figure 3 . ## conclusion in this work, we introduced grraf, a novel framework that integrates rag with the code-writing prowess of llms to address graph reasoning questions. our approach, which operates without additional training or reliance on predefined algorithms, leverages a graph database to store target graphs and employs an error feedback loop with a time-out mechanism to ensure the generation of correct and efficient code queries. comprehensive experiments on the graphinstruct dataset and two extra tasks (indegree and outdegree) demonstrate that grraf outperforms existing state-of-the-art benchmarks, achieving 100% accuracy on a majority of graph reasoning tasks while effectively scaling to graphs containing up to 10,000 nodes without incurring extra token costs. these findings underscore the potential of combining retrieval-based techniques with llm-driven code generation for solving complex graph reasoning problems. future work could explore extending this framework to dynamic graph scenarios and additional reasoning tasks, further enhancing its applicability and robustness.