Can Language Models Solve Graph Problems in Natural Language?
By Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, Yulia Tsvetkov. Neural Information Processing Systems, 2023
380 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence
View Paper: https://www.semanticscholar.org/paper/df2beaae63e4d68ef8e762bcd4704c9f11f856d9
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
Citations in the corpus
- Language is All a Graph Needs (2023, background): “Wang et al. (2023a) and Chen et al. (2023b) both explore using natural language with LLM for graph problems, with (Wang et al., 2023a) focusing on mathematical problems on small graphs while (Chen et al., 2023b) concentrating on node classification in Text-Attributed Graphs (TAGs) (Hu et al., 2020).”
- Graph Retrieval-Augmented Generation: A Survey (2024, neutral): “We illustrate this process with an example in Figure 5, with detailed introductions provided below.”
- Large Language Models on Graphs: A Comprehensive Survey (2023, methodology): “[124]–[126] do confirm that LLMs can answer easier questions such as connectivity, neighbor identification, and graph size counting but fail to answer more complex questions such as cycle detection and Hamiltonian pathfinding.”
- G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering (2024, neutral): “Surrounding this question, develop an educational tour through the knowledge graph, highlighting interesting facts and connections in an engaging way. classification [8], or answering simple questions on small or synthetic graphs [44, 31].”
- Exploring the Potential of Large Language Models (LLMs)in Learning on Graphs (2023, methodology): “Specifically, we first consider inputting the whole graph into the LLMs.”
- ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution (2024, positive): “This paper introduces the general concept of Language Hyper-Heuristics (LHH) to advance beyond preliminary attempts in individual COP settings.”