Less is More: Learning Graph Tasks with Just LLMs

• URL: http://arxiv.org/abs/2508.10115v1
• Date: Wed, 13 Aug 2025 18:21:05 GMT
• Title: Less is More: Learning Graph Tasks with Just LLMs
• Authors: Sola Shirai, Kavitha Srinivas, Julian Dolby, Michael Katz, Horst Samulowitz, Shirin Sohrabi,
• Abstract summary: We show that even small LLMs can learn to solve graph tasks by training them with instructive chain-of-thought solutions.<n>This training generalizes, without specialized graph encoders, to new tasks and graph structures.
• Score: 22.38454720682463
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: For large language models (LLMs), reasoning over graphs could help solve many problems. Prior work has tried to improve LLM graph reasoning by examining how best to serialize graphs as text and by combining GNNs and LLMs. However, the merits of such approaches remain unclear, so we empirically answer the following research questions: (1) Can LLMs learn to solve fundamental graph tasks without specialized graph encoding models?, (2) Can LLMs generalize learned solutions to unseen graph structures or tasks?, and (3) What are the merits of competing approaches to learn graph tasks? We show that even small LLMs can learn to solve graph tasks by training them with instructive chain-of-thought solutions, and this training generalizes, without specialized graph encoders, to new tasks and graph structures.

Related papers

• Graph-Grounded LLMs: Leveraging Graphical Function Calling to Minimize LLM Hallucinations [8.07547612687425]
  Graphs are integral to a wide range of applications, including motion planning for autonomous vehicles, social networks, scene understanding, and knowledge graphs.<n>We propose Graph-Grounded LLMs, a system that improves LLM performance on graph-related tasks by integrating a graph library through function calls.<n>We demonstrate significant reductions in hallucinations and improved mathematical accuracy in solving graph-based problems, as evidenced by the performance on the NLGraph benchmark.
  arXiv  Detail & Related papers  (2025-03-13T22:57:28Z)
• What Do LLMs Need to Understand Graphs: A Survey of Parametric Representation of Graphs [69.48708136448694]
  Large language models (LLMs) are reorganizing in the AI community for their expected reasoning and inference abilities.<n>We believe this kind of parametric representation of graphs, graph laws, can be a solution for making LLMs understand graph data as the input.
  arXiv  Detail & Related papers  (2024-10-16T00:01:31Z)
• 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)<n>We revisit the ability of LLMs on three fundamental graph tasks: graph description translation, graph connectivity, and the shortest-path problem.<n>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)
• Can Graph Learning Improve Planning in LLM-based Agents? [61.47027387839096]
  Task planning in language agents is emerging as an important research topic alongside the development of large language models (LLMs) In this paper, we explore graph learning-based methods for task planning, a direction that is to the prevalent focus on prompt design. Our interest in graph learning stems from a theoretical discovery: the biases of attention and auto-regressive loss impede LLMs' ability to effectively navigate decision-making on graphs.
  arXiv  Detail & Related papers  (2024-05-29T14:26:24Z)
• Can Graph Descriptive Order Affect Solving Graph Problems with LLMs? [38.1577036285387]
  Large language models (LLMs) have achieved significant success in reasoning tasks, including mathematical reasoning and logical deduction.<n>Previous studies have explored LLMs' graph reasoning abilities through various techniques.<n>A critical factor has been mostly overlooked: the prompt sequential order in which graph descriptions are presented to the models.
  arXiv  Detail & Related papers  (2024-02-11T09:46:24Z)
• Integrating Graphs with Large Language Models: Methods and Prospects [68.37584693537555]
  Large language models (LLMs) have emerged as frontrunners, showcasing unparalleled prowess in diverse applications. Merging the capabilities of LLMs with graph-structured data has been a topic of keen interest. This paper bifurcates such integrations into two predominant categories.
  arXiv  Detail & Related papers  (2023-10-09T07:59:34Z)
• 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)

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.