Can Language Models Solve Graph Problems in Natural Language?
- URL: http://arxiv.org/abs/2305.10037v3
- Date: Sat, 6 Jan 2024 01:01:38 GMT
- Title: Can Language Models Solve Graph Problems in Natural Language?
- Authors: Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han,
Yulia Tsvetkov
- Abstract summary: 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.
- Score: 51.28850846990929
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Large language models (LLMs) are increasingly adopted for a variety of tasks
with implicit graphical structures, such as planning in robotics, multi-hop
question answering or knowledge probing, structured commonsense reasoning, and
more. While LLMs have advanced the state-of-the-art on these tasks with
structure implications, whether LLMs could explicitly process textual
descriptions of graphs and structures, map them to grounded conceptual spaces,
and perform structured operations remains underexplored. To this end, we
propose NLGraph (Natural Language Graph), a comprehensive benchmark of
graph-based problem solving designed in natural language. NLGraph contains
29,370 problems, covering eight graph reasoning tasks with varying complexity
from simple tasks such as connectivity and shortest path up to complex problems
such as maximum flow and simulating graph neural networks. We evaluate LLMs
(GPT-3/4) with various prompting approaches on the NLGraph benchmark and find
that 1) language models do demonstrate preliminary graph reasoning abilities,
2) the benefit of advanced prompting and in-context learning diminishes on more
complex graph problems, while 3) LLMs are also (un)surprisingly brittle in the
face of spurious correlations in graph and problem settings. We then propose
Build-a-Graph Prompting and Algorithmic Prompting, two instruction-based
approaches to enhance LLMs in solving natural language graph problems.
Build-a-Graph and Algorithmic prompting improve the performance of LLMs on
NLGraph by 3.07% to 16.85% across multiple tasks and settings, while how to
solve the most complicated graph reasoning tasks in our setup with language
models remains an open research question. The NLGraph benchmark and evaluation
code are available at https://github.com/Arthur-Heng/NLGraph.
Related papers
- GraphArena: Benchmarking Large Language Models on Graph Computational Problems [25.72820021030033]
"arms race" of Large Language Models (LLMs) demands novel, challenging, and diverse benchmarks to examine their progresses.
We introduce GraphArena, a benchmarking tool to evaluate models on graph computational problems using million-scale real-world graphs.
arXiv Detail & Related papers (2024-06-29T09:19:23Z) - Parameter-Efficient Tuning Large Language Models for Graph Representation Learning [62.26278815157628]
We introduce Graph-aware.
Efficient Fine-Tuning - GPEFT, a novel approach for efficient graph representation learning.
We use a graph neural network (GNN) to encode structural information from neighboring nodes into a graph prompt.
We validate our approach through comprehensive experiments conducted on 8 different text-rich graphs, observing an average improvement of 2% in hit@1 and Mean Reciprocal Rank (MRR) in link prediction evaluations.
arXiv Detail & Related papers (2024-04-28T18:36:59Z) - 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) - 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) - Large Language Models on Graphs: A Comprehensive Survey [81.7684686396014]
We provide a systematic review of scenarios and techniques related to large language models on graphs.
We first summarize potential scenarios of adopting LLMs on graphs into three categories, namely pure graphs, text-attributed graphs, and text-paired graphs.
We discuss the real-world applications of such methods and summarize open-source codes and benchmark datasets.
arXiv Detail & Related papers (2023-12-05T14:14:27Z) - 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) - Talk like a Graph: Encoding Graphs for Large Language Models [15.652881653332194]
We study the first comprehensive study of encoding graph-structured data as text for consumption by large language models (LLMs)
We show that LLM performance on graph reasoning tasks varies on three fundamental levels: (1) the graph encoding method, (2) the nature of the graph task itself, and (3) interestingly, the very structure of the graph considered.
arXiv Detail & Related papers (2023-10-06T19:55:21Z) - GraphText: Graph Reasoning in Text Space [32.00258972022153]
GraphText is a framework that translates graphs into natural language.
GraphText can achieve on par with, or even surpassing, the performance of supervised-trained graph neural networks.
It paves the way for interactive graph reasoning, allowing both humans and LLMs to communicate with the model seamlessly using natural language.
arXiv Detail & Related papers (2023-10-02T11:03:57Z) - Graph-ToolFormer: To Empower LLMs with Graph Reasoning Ability via
Prompt Augmented by ChatGPT [10.879701971582502]
We aim to develop a large language model (LLM) with the reasoning ability on complex graph data.
Inspired by the latest ChatGPT and Toolformer models, we propose the Graph-ToolFormer framework to teach LLMs themselves with prompts augmented by ChatGPT to use external graph reasoning API tools.
arXiv Detail & Related papers (2023-04-10T05:25:54Z)
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.