Title: Can Language Models Solve Graph Problems in Natural Language?

Institute: Xi’an Jiaotong University, University of Washington

Authors: Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, Yulia Tsvetkov

Date: 2023.5.13

Link: 2305.10037v1.pdf (arxiv.org)

Introduction

This is the first attempt to use large language models to solve graph problems. The authors introduce NLGraph, a natural-language benchmark containing over a thousand basic graph problems, and draw several conclusions from experiments on GPT-3/4. At the end of the paper they propose two methods for improving how LLMs handle graph problems.

In summary, the contributions are:

• The first benchmark for handling graph problems in natural language, NLGraph

• Experiments on GPT-3/4 with measurements of LLM performance, yielding several regularities

• Two methods for improving performance

NLGraph

Put simply, this benchmark is a collection of graphs described in natural language, each paired with its answer.

Graph generation

Generate n nodes and connect each pair of nodes with probability p, so graph generation is controlled by n and p. Individual tasks impose additional constraints.

Tasks

NLGraph contains eight kinds of tasks:

• Connectivity: whether two nodes are connected

• Cycle detection: whether the graph contains a cycle

• Topological sort

• Shortest path

• Maximum flow

• Bipartite graph matching

• Hamiltonian path

• Simulating a graph neural network

Statistics

The basic version contains 5,902 examples; the extended version contains 29,370.

Experimental Setup

Baselines

The authors use a variety of prompts as baselines:

• ZERO-SHOT

• FEW-SHOT

• CoT

• 0-CoT

• least-to-most (LTM-2023): break a large problem into several subproblems and solve them one by one

• self-consistency (SC-2023): ask the same question in multiple ways and take the most consistent result

The authors also use random guessing as a baseline — for yes/no questions the baseline is 50%, and for shortest-path questions the baseline is whether a randomly chosen path is correct.

Models

TEXT-DAVINCI-003, GPT-3/4

Conclusions

LLMs have preliminary reasoning ability on graph problems

• On connectivity, cycle detection, and shortest path, LLM performance is markedly above Random, showing that the model is not answering at random and does possess preliminary reasoning ability.

• With CoT or CoT+SC prompting, accuracy exceeds the Random baseline by 37.33%–57.82%

• On connectivity and shortest path, ZERO-SHOT exceeds Random accuracy by 33.81% and 23.33% respectively

• On shortest path, CoT and CoT+SC exceed Random by 22.81%–62.83%

Advanced prompting is not necessarily beneficial

• Advanced prompts such as CoT and SC improve accuracy on most problems

• But on complex graph problems, advanced prompts such as CoT, CoT+SC, and LTM actually underperform Few-shot

• The authors attribute this to the LLM’s inability to generate a chain of thought for complex graph problems

In-context prompting can backfire

• On complex graph reasoning problems such as Hamiltonian path and bipartite matching, ZERO-SHOT outperforms Few-shot

• The reason may be that on complex problems the LLM cannot extract knowledge from the context, and the context instead dilutes its attention

LLMs are (un)surprisingly brittle

The heading means that the LLM may have misconstrued the reasoning process behind the question.

Although the LLM performs well, it may be arriving at correct answers by exploiting spurious correlations. For example, since higher-degree nodes are mentioned more often and are more likely to be connected, the language model may simply be counting node occurrences rather than actually searching for a path. In other words, on connectivity problems, nodes with especially high degree tend to be connected to one another, which may lead the model to assume that high-degree nodes are connected instead of verifying a path.

The authors therefore constructed two special datasets.

Chain

Split a graph into k parts, each an independent chain, and ask whether the head and tail nodes of each chain are connected. The head and tail have the lowest degree yet are in fact connected.

Clique

Build k dense, independent subgraphs. Pick two nodes from different subgraphs; because the subgraphs are dense, both nodes have high degree, but because the subgraphs are disjoint, the two nodes are not connected.

Unsurprisingly, LLM performance on these two datasets dropped by 40%, confirming the authors’ suspicion.

Two Methods for Improving Performance

Build-a-Graph Prompting (BAG)

The authors reason that mapping the textual description of the graph into an actual conceptual space may help, so they add the sentence “Let’s construct a graph with the nodes and edges first”.

Algorithmic Prompting

Hint that a specific algorithm can be used to solve the problem — for instance, telling the model to use DFS or BFS.

Result

On simple problems, the authors’ two methods improve performance by 3.07%–16.85%. On complex problems, however, there is no improvement.

Summary

Comparison with Talk Like a Graph: Encoding Graphs for Large Language Models

Since “Talk Like a Graph: Encoding Graphs for Large Language Models” is the more recent work, it is referred to below as “the latter”, while the present paper is “the former”.

Benchmark

The two papers’ benchmarks complement each other, with some overlap in problem types

On prompting

The latter adds an encoding component relative to the former

Their prompting differs: the former has LTM and SC prompts, while the latter has BAG prompting (COT-BAG). It is unclear why the latter dropped LTM and SC.

On experiments

• The latter adds the effect of model capacity on performance

• The latter adds the effect of graph shape

• On simple graph tasks, ZERO-SHOT beats ZERO-COT in both papers

• Both find that advanced prompting degrades LLM performance on complex graph tasks

• Both hold that “mapping the textual description of the graph into an actual conceptual space may help”, but the former merely adds the sentence “Let’s construct a graph with the nodes and edges first”, whereas the latter actually tests the LLM on real-world problems.

On novelty

• The former’s novelty lies in the dataset, the experimental design, and its pioneering nature

• The latter’s novelty lies in treating encoding as a variable

Questions

Solved

Since I read the latter first and had no prior knowledge of the former’s work, I raised several questions in my write-up of the latter; here are the answers.

• How well do LLMs handle shortest-path problems? Is the complexity the same as for cycle problems?

  • First, the two tasks are different in nature: one is about finding a correct path, the other is a True/False question

  • In this paper, shortest path and cycle detection are not equally hard. Cycle detection is classified as a basic problem with three difficulty levels, whereas shortest path is classified as an advanced problem with two difficulty levels.

Generated

• Following the latter, what other variables could be mined for experiments?

  • Language?

  • The number of nodes and edges, small graphs $\rightarrow$ large graphs

  • Representing graphs as adjacency matrices

• Classic tree-related problems seem to go unmentioned

  • Minimum spanning tree

  • Tree diameter

  • …

• Fine-tuning / LoRA