Graph Reasoning with Large Language Models via Pseudo-code Prompting

• URL: http://arxiv.org/abs/2409.17906v1
• Date: Thu, 26 Sep 2024 14:52:40 GMT
• Title: Graph Reasoning with Large Language Models via Pseudo-code Prompting
• Authors: Konstantinos Skianis, Giannis Nikolentzos, Michalis Vazirgiannis,
• Abstract summary: This paper investigates whether prompting via pseudo-code instructions can improve the performance of large language models (LLMs) in solving graph problems. Our experiments demonstrate that using pseudo-code instructions generally improves the performance of all considered LLMs.
• Score: 25.469214467011362
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large language models (LLMs) have recently achieved remarkable success in various reasoning tasks in the field of natural language processing. This success of LLMs has also motivated their use in graph-related tasks. Among others, recent work has explored whether LLMs can solve graph problems such as counting the number of connected components of a graph or computing the shortest path distance between two nodes. Although LLMs possess preliminary graph reasoning abilities, they might still struggle to solve some seemingly simple problems. In this paper, we investigate whether prompting via pseudo-code instructions can improve the performance of LLMs in solving graph problems. Our experiments demonstrate that using pseudo-code instructions generally improves the performance of all considered LLMs. The graphs, pseudo-code prompts, and evaluation code are publicly available.

Related papers

• Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models [90.98855064914379]
  We introduce ProGraph, a benchmark for large language models (LLMs) to process graphs. Our findings reveal that the performance of current LLMs is unsatisfactory, with the best model achieving only 36% accuracy. 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)
• CodeGraph: Enhancing Graph Reasoning of LLMs with Code [43.79249671845997]
  We introduce CodeGraph, a method that encodes graph problem solutions as code. We show that CodeGraph can boost performance on graph reasoning tasks inside large language models by 1.3% to 58.6%.
  arXiv  Detail & Related papers  (2024-08-25T15:27:21Z)
• Revisiting the Graph Reasoning Ability of Large Language Models: Case Studies in Translation, Connectivity and Shortest Path [53.71787069694794]
  We focus on the graph reasoning ability of Large Language Models (LLMs) We revisit the ability of LLMs on three fundamental graph tasks: graph description translation, graph connectivity, and the shortest-path problem. Our findings suggest that LLMs can fail to understand graph structures through text descriptions and exhibit varying performance for all these fundamental tasks.
  arXiv  Detail & Related papers  (2024-08-18T16:26:39Z)
• Can LLM Graph Reasoning Generalize beyond Pattern Memorization? [46.93972334344908]
  We evaluate whether large language models (LLMs) can go beyond semantic, numeric, structural, reasoning patterns in the synthetic training data and improve utility on real-world graph-based tasks. We find that while post-training alignment is most promising for real-world tasks, empowering LLM graph reasoning to go beyond pattern remains an open research question.
  arXiv  Detail & Related papers  (2024-06-23T02:59:15Z)
• Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs [60.71360240206726]
  Large language models (LLMs) suffer from hallucinations, especially on knowledge-intensive tasks. Existing works propose to augment LLMs with individual text units retrieved from external knowledge corpora. We propose a framework called Graph Chain-of-thought (Graph-CoT) to augment LLMs with graphs by encouraging LLMs to reason on the graph iteratively.
  arXiv  Detail & Related papers  (2024-04-10T15:41:53Z)
• Can LLMs perform structured graph reasoning? [4.676784872259775]
  Pretrained Large Language Models (LLMs) have demonstrated various reasoning capabilities through language-based prompts alone. We design various graph reasoning tasks as a proxy to semi-structured tasks in this paper. We benchmark 5 different instruct-finetuned LLMs (GPT-4, GPT-3.5, Claude-2, Llama-2 and Palm-2) on the aforementioned tasks.
  arXiv  Detail & Related papers  (2024-02-02T09:45:33Z)
• Can Language Models Solve Graph Problems in Natural Language? [51.28850846990929]
  Large language models (LLMs) are increasingly adopted for a variety of tasks with implicit graphical structures. We propose NLGraph, a benchmark of graph-based problem solving simulating in natural language.
  arXiv  Detail & Related papers  (2023-05-17T08:29:21Z)
• PAL: Program-aided Language Models [112.94785609781503]
  We present Program-Aided Language models (PaL) to understand natural language problems. PaL offloads the solution step to a programmatic runtime such as a Python interpreter. We set new state-of-the-art results in all 12 benchmarks.
  arXiv  Detail & Related papers  (2022-11-18T18:56:13Z)

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.