Title: Zero-shot Graph Reasoning via Retrieval Augmented Framework with LLMs Show Chinese title

Title: 通过检索增强框架进行零样本图推理的大型语言模型方法

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. Show Chinese abstract

Abstract: 我们提出了一种新的、无需训练的方法，基于检索增强框架的图推理（GRRAF），该方法结合了检索增强生成（RAG）和大语言模型（LLM）的代码生成能力，以解决各种图推理任务。 在GRRAF中，目标图存储在一个图数据库中，LLM被提示生成可执行的代码查询来检索所需信息。 这种方法克服了现有方法需要大量微调或依赖预定义算法的局限性，并引入了一个带有超时机制的错误反馈循环，以确保正确性和效率。 在GraphInstruct数据集上的实验评估表明，GRRAF在大多数图推理任务中实现了100%的准确率，包括环检测、二分图检查、最短路径计算和最大流，同时无论图的大小如何，都保持一致的标记成本。 在子图匹配上表现出不完美但仍然非常高的性能。 值得注意的是，GRRAF能够有效地扩展到包含最多10,000个节点的大图。