Can Language Models Solve Graph Problems in Natural Language?
Authors: Heng Wang
Shangbin Feng
Tianxing He
Zhaoxuan Tan
Xiaochuang Han
Yulia Tsvetkov
Venue: NeurIPS 2023 spotlight (2023)
Keywords: large language models
graph reasoning
structured reasoning

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.

Can Language Models Solve Graph Problems in Natural Language?
Heng Wang" 1, Shanghin Feng" Tianxing He?, Zhaoxuan Tan Xiaochuang Han', Yulia Tsvetkoy? Xi''a an Jiaotong University Universitty of Washington Univvrsity of Notre Dame wh22132105540stu. xjtu. edu. en, shangbin@cs washington. edu
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-ther af-tt these tasks with structure impli- cations, whether LLMs could explicitly process textual descriptions of graphs and structures, map them grounded conceptual spaces, and perform structured opera- tions remains underexplored. To this end, we propose NL.Graph (Natural Language Graph), a comprehensive benchmark of graph-based problem solving designed in natural language. NI NI.Graph contains 29,370 problems, covering eight graph reasoning tasks with varying complexity from simple tasks such as connectivity and shortest path 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) uuruurrriyy brittle in the face of spurious correlations graph and problem settings. We then propose Build-a-Graph Prompting and Algorithmic Prompting, two instruction-bart based approaches to enhance L.MS solving natural language graph problems. Build-a-Grey Grapph 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 setup with language models remains an open research question. The GL.rr benchmark and evaluation code are available at htps://github.com/Arrte http:/hhhw....oo/tttuee//ll//aaa
Introduction
Originally designed for textual data, large language models (LLMs) are increasingly leveraged for tasks beyond language processing. In robotics and planning. LLMs are adopted to guide agents through structured environments (Huang et al., 2022 Andreas 2022]. In theory-of-mind reasoning, LLMs are required maintain and update local and global graphs that reflect the beliefs of different characters [Adhikari et al. 2020 Ammanabrolu and Riedl 2021]. In structured commonsense reasoning, LLMs are expected to generate graph-based action plans to achieve objectives with diversified prerequisites [Tanoon et al,, 2019 Madaan et al.) 2022]. In multi-hop question answering,
LLMs implicitly find connections and paths among a vast network of entities and concepts (Creswell et al. 2023). Together these works demonstrate that LLMs are widely adopted for tasks with implicir graphical structures while achieving preliminary success. However, underlying yet crucial question remains underexplored: Can LLMs reason with graphs? More concretely, are LLMs capable of mapping textual descriptions of graphs and structures grounded conceptual spaces and solving
equal contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

graph algorithm problems explicitly with natural language? The answer to this question has profound implications for large language model applications with implicit graphs and structures, the reasoning ability of L.MSs in advanced and graph- settings, and more.
To this end, we propose the Natural Language Graph (NI.Graph) benchmark, comprehensive testbed of graph and structured reasoning designed for language models and in natural language. NLGraph contains a total of 29,370 problems, covering eight graph reasoning tasks with varying complexity from intuitively simple tasks such as connectivity, cycle, and shortest path to more complex problems such as topological sort, maximum flow, bipartite graph matching, Hamilton path, and simulating graph neural networks. We control for problem difficulty through generated graph size, network sparsity, numeric range, and more, presenting easy, medium, and hard subsets in each distinct graph reasoning task to enable fine- tie-grrined analysis. In addition to using exact match accuracy as standard metric, we also design several partial credit solutions for various graph reasoning tasks.
With the NI.Graph benchmark, we evaluate whether various large language models [Brown et al. 2020 Ouyang et al., [022] Bubeck et al. [2023] could perform graph-based reasoning and whether different prompting techniques [Brown et al. 2020, Wei el al. 2022 Kojima et al. [022 Zhou et al.
2023 Wang et al. 2023] improve the graph reasoning abilities of large language models. Extensive experiments on the NLGraph benchmark demonstrate that:
1. LLMs do possess preliminary graph reasoning abilities. Specifically, large language models demonstrate an impressive level of performance that is 37.33% to 57.82% above the random baseline on simple graph reasoning tasks such connectivity, cycle, and shortest path. With chain-of-thought prompting, I.LMs could generate intermediate steps that are sound and accurate while further improving task performance.
2. The benefit of advanced prompting methods diminishes with complex problems. On one hand, chain-of of----o-ttthho -houutttt [Wei et al., 2202], least-to-moss most (Zhou et al. 2023], , and self-consisteng
[aang et al. 2023] successfully enhance the graph reasoning abilities of L.LMs on simple tasks such as cycle and shortest path. On the other hand, these approaches are mostly ineffective, even counterproductive in certain settings, on more complex graph reasoning problems such as topological sort and Hamilton path.
3. Learning from examples did not happen on complex graph reasoning problems. While in-context learning is widely credited for teaching LLMs to learn from examples [Brown et al., 2020), , its benefit on more advanced graph reasoning tasks is unclear: Few-shot in-context learning fails to improve over zero-shot prompting across multiple tasks, while increasing the number of exemplars may even be counterproductive for tasks such as Hamilton path.
LLMs are (un)surprisingly brittle to spurious correlations in problem settings. We find that in two special cases in the connectivity task (chain and clique). LLMs perform much worse than the general dataset with performance drop of more than 40% across various settings. This indicates that large language models are implicitly relying on certain spurious correlations (for example, use node mention frequency to determine connectivity). falling short performing robust structured reasoning in graph-based contexts.
To improve large language models as better graph reasoners, we propose two instruction-based prompting approaches to better elicit the graph reasoning abilities of large language models. Build- a-Graph prompting encourages LLMs to map the textual descriptions of graphs and structures to grounded conceptual spaces (atel and Pavlick, [022]] before tackling the specific problem through a one-sentence instruction, while Algorithmic prompting instructs LLMSs to revisit the algorithmic steps for a given task before learning from in-context exemplars. Experiments demonstrate that build- a-graph and algorithmic prompting successfully empower L.LMs to better tackle graph reasoning problems, resulting in 3.07% to 16.85% performance gains across multiple tasks, while the most complicated graph reasoning problems remain an open research question.
2 The NL.Graph Benchmark
To examine whether language models are capable of reasoning with graphs and structures, we curate and propose the Natural Language Graph (NLGraph) benchmark. Specifically, we first employ a random graph generator to generate graphs and structures while controlling for the network size, graph sparsity, and more. We then adopt the generated graphs as bases to synthetically generate problems for eight brsph reasoning tasks with varying algorithmic difficulties. We control for
2

---

Connectvityy
Tepologiceiaan
Determine ifthere a path between two nodess the graph that (i))
unddoweted graph, (ijl meera that nodel and node; are connected with undireeted edge.
undiieectdd greph, the numberad berl
In clive led graphh with nodes
means that node and node
numberedd from to 4 node o should be verted before node
edge between and node with weight
edge
The nodiss are numberre from to and the edges are B.4 (BS) (1.) (2.5) 12:0
Geaple (1.2) (54)
4.
@ Give the shonest path from node to node 4.
there betwoen and Lodde
Q Can all the nodes be visite?? Give the solution
Q there a eycle this gruph?
Aipurtte deoph Marching
job applicac
jobe
directed graphs the nothes are
from to burberrd from
job applicntt
an undi mettdd graph l& means that
divectedd groph, nodes are numbened from every node
numbered from the odges
interested
rodal and node are connected with an undiracted edge.
of jobs. Each can only applicant and sop icant can be appointed for only one Job
The modes are numbered from to and the adges are (42) (144 14 (0,1) 11.2 (A.3) (2.3)
undirected
capacity
Sinbeddinge node
edge from mode O mode 2 with
The
capurity
Apalican O interessud in jab 4,
there path that path:
graph that
convollaton each
capacity 4.
an edge from node 2 mode 3 with
Q What is the maddmum flow from noci to noce 3?
remiber of applicants find the job they are mnrrssed in
Q Find an assignment of jebs to appy icents such
miaimum
anjecent oodes must be connected with wigen.
every
nodll's enniandiingg apdated by the sum of its meig iooss amiardding..
Q What's the embeddinng of each node after one layer of simple graph conselution leyer?
Figure I: Overview of the GL.Graph Benchmark, featuring eight tasks with varying complexity. We show an intuitive figure representing each task along with the example natural language prompts being passed to the L.LMs.
problem difficulty within each of the eight tasks, resulting in easy, medium, and hard subsets in each graph reasoning task to enable difficulty scaling and fine-grained analysis.
2.1 Random Graph Generator
We first employ general-purpose purpose random graph generator to generate base graphs while using the number of nodes and graph density to control for complexity. Formally, to generate a graph g = EV where V and & denote the set of nodes and edges, we specify the number of nodes n, thus V {11, 122 ....... ] and | = n. We then specify the edge probability p such that all the edges are generated according to P(e.j E E) = p. where eij is an edge from e; to ey. The edges could be directed or undirected depending on the task. We use varying n and p values to control for the complexity of the random graph structure. Building top of these generated base graphs, we also adopt graph edits and other difficulty control factors tailored for each task.
2.2 Tasks
Armed with the general-purge pprppse random graph generator, we adapt the synthetically generated graphs to eight graph reasoning tasks with varying complexity and describe the problem setups in natural language. Specifically, we first generate easy, medium, and hard subsets of base graphs for each task by controlling for node amount and graph sparsity. We then adapt or edit the base graphs for each task and design queries accordingly. We present an overview of the NLGraph benchmark with specific natural language instructions in Figure
Connectivity In an undirected graph G = (V, E}. two nodes u and are connected if there exists a sequence of edges from node u to node v E. We randomly select two nodes the base graphs u, E V to ask whether node and node are connected with true/false question. We retain a balanced set of questions where half of the node pairs are connected and the other half are not connected by discarding additional questions.
Task 1:
Task 2: Cycle In an undirected graph G = E), a cycle is a non-empty trail (e1, e2........ en) with node sequence (v), U2, Un,, 0n We present undirected graph = (V,E) to ask whether there exists a cycle through true/false questions. We retain base graphs without cycles as the False subset, while we randomly add edges to these base graphs to generate graphs with cycles as the True subset. We retain a balanced set of cyclic and noncyclic graphs in the dataset.
Task 3: Topological Sort A topological sort of a directed graph is linear ordering of its nodes such that for every directed edge (u, v) from node u to node comes before in the ordering.
3

---

Subset
Connect.
Cycle
Topo. Sort
Shortest Path
Max. Flow
Bipartite Graph
Hamilton Path
GNNs
# EASY
352 730
150/300
180/ 360
180 360
150 /30
300 300/600
1500/ 300
100 200
SPEC.
o: 5-10
n: 5-10
5-10
1e: 5-10
5-10
6-20
5-10 /
n: 5-8
MEDIUM
1,200/ 88,50
600/ 1,800
150/ 1,350
SPEC.
mi 1 11-25
11-25
mt: 11-25
/
# HHRDD
680 000/7.000
400 2,000
200 1,200
200 1,200
200 / 1,200
210 1,260
200 /00/
140 / 880
SPEC.
12: 26-35
26-35
12: 26-35
1 11:20
vi: 11-20
17-33
ze: 11-20
9-15
Table 1: Statistics of the NLGraph benchmark. We use A / B to indicate that there are A and B problems the standard and extended set of NI.Graph. SPEC. denotes difficulty specifications.
The task is to find a valid topological sort given a directed graph and there could be multiple valid solutions. We ask LLMs to generate valid topological sort for the given directed graph and employ an external program to examine its correctness.
Task 4: Shortest Path The shortest path between two nodes the path with the sum of edge weights minimized. Given undirected graph G = (V, EJ. positive weight w for each edge, and two nodes u and v, the task to find the shortest path between node u and node v and its corresponding path length. We filter the generated base graphs by specifying that the number of nodes on the correct shortest path is as least E, where f is chosen from min to max for each question to sever an additional difficulty control measure. We adopt two metrics; exact match, where the LLM solution is a valid path and optimal, and partial credit, where the L.M solution is valid and is the rank,-th shortest among all the possible paths (i.e. the number of shorter paths plus one). The partial credit score for each problem can be formulated as PC = 1/rank,,
Task 5: Maximum Flow Let G = {V,E) }} be a network with two nodes s, s,t E V being the source and the sink. Each edge is associated with a capacity the maximum amount of flow that can pass through the edge. We ask LLMs to generate a plan to route as much flow as possible from the source to the sink. We evaluate in both exact match with the optimal plan and partial credit for this
t//s, if t S where is the flow value 0,, if under the optimal plan, and l is the flow value of the solution generated by LLMs.
task, where partial credit can be formulated as PC
Task 6: Bipartite Graph Matching In an undirected graph G EV,E), a matching is set of edges without common nodes. A bipartite graph is graph whose nodes can be divided into two disjoint sets U and V, and in each set no nodes are adjacent to each other. Given a bipartite graph, the task is to find the matching that maximizes the number of edges. We use an external program to evaluate whether the solution generated by L.MSs is valid and optimal.
Task 7: Hamilton Path In an undirected graph, a Hamilton path is a path that visits every node exactly once. Given undirected graph g EV.E), the task is to find a valid Hamilton path. We filter generated base graphs to ensure that at least one valid Hamilton path exists and use an external program to evaluate the LLM solution.
Task 8: Graph Neural Networks Given an undirected graph G (V, E. and two-dimension node embedding x; for each node, the task is to perform layers of message passing, i.e. to update the node embedding with the sum of all the neighbors' embeddings. Formally, x!
(f+1)
EjEN, x5 where Nú denotes the neighborhood of node and (f) denotes the f-th layer. We use an exact match with the correct node embeddings and two types of partial credits for this task. Specifically, the first partial credit is the percentage of the nodes whose embedding is correct (PC), and the second is the average of all the values' relative errors for the standard answer (RE). The relative error is formulated as RE = the value in the standard answer, averaged across all embedding dimensions.
max(a.y) where z is the value generated by LLMs and is
je-v|
2.3 Benchmark Statistics
Using the above methodology, we generate the NLGraph benchmark with 5,902 problems in standard version and 29,370 problems in an extended version. Intuitively easier tasks, including connectivity, cycle, and topological sort problems, are further divided into easy, medium, and hard subsets based on graph size, sparsity, among other difficulty control factors. More algorithmically advanced tasks, including shortest path, maximum flow, bipartite graph matching, Hamilton path,

---

Counectivity
Cycle
Shortest Path
Method
Easy
Medium
Hard
Avg.
Easy
Medium
Hard
Avg-
Easy
Hard
Easy (PC)
Hard (PC)
RANDOM
50,00
50.00
50.00
50.00
50.00
50.00
50.00
50.00
6.07
6.69
14.73
13.81
17.81
ZERO-SHOT
83,81
72.75
63.38
71.31
50,00
50.00
50.00
50.00
29,40
21.00
46,00
26.76
30.79
PEW-SHOT
93.75
83.83
76.61
84.73
80,00
70.00
61.00
70.33
31,11
26.00
49.19
35.73
35.51
COT
94.32
82.
77.21
84.57
84.67
63.33
53.25
66.75
63.89
29.50
76.84
35.79
51.51
0-COT
68.53
55.33
57.67
49.00
54.00
CC
93.18
84.50
82.79
86.82
82.00
63.67
53.50
66.39
68.89
29.00
80.25
38.47
54.15
Table 2: Model performance on the connectivity, cycle, and shortest path tasks. PC denotes partial credit. Large language models with CoT CoT+SC prompting greatly outperforms the random baseline by 37.33% to 57.82%, indicating that LLMs have preliminary graph reasoning abilities.
and graph neural networks problems, are divided into easy and hard subsets. We present benchmark statistics in [able Accuracy (whether the true/false answer is correct, whether the proposed solution is valid) is the default evaluation metric, while tasks 4, task 5, and task 8 have additional partial-credit metrics aforementioned. We envision NLGraph as a comprehensive testbed for graph and structured reasoning for large language models.
Experimental Settings
Based on the NLGraph benchmark, aim to investigate whether language models can solve graph algorithm problems in natural language by evaluating large language models and different prompting approaches.
Baselines We adopt a wide range of prompting approaches as baselines. Specifically, zero-shot prompting (ZERO-SHOT), few-shot in-context learning (FEW-SHOT) [Brown et al. 2020], chain-of- thought prompting (CoT) [Wei et al.] 2022 zero-shot sfain-of-thoughe (0-CoT) Kojima et al. 2022], least-to-most (L.TM) [Zhou et al. 2023), , and self-consistency (SC) [Wang et al. 2023 are leveraged to tackle various graph reasoning tasks in the NL.Graph benchmark.
We also adopt a RANDOM baseline: for true/false questions such as connectivity and cycle, we use RANDOM to denote a baseline that randomly selects an answer from true and false with an expected accuracy of 50%; For the shortest path task, RANDOM denotes a baseline that randomly selects valid path between the query node pair. For the maximum flow task, RANDOM denotes a baseline that randomly selects a value between and the sum of all the edges' capacities. The performance comparison between different prompting techniques and the RANDOM baseline could indicate whether LLMs are capable of performing graph reasoning instead of giving randomly generated answers.
Models and Settings We use TEXT-DAVINCI-OOS also evaluate three additional LLMs (GPT-3.5- 3.5 TUTUBB, CODE-DAVINCES DAVINCI--02, and GPT-4), presenting 0; For
the default large language model, while
results in Appendix E For all baselines except self-consistency, we set temperature self-consistency prompting, we sample five chain-of-thought responses with temperature т = 0.7. For few-shot prompting techniques (i.e., FEW-SHOT, COT, LTM, and CoT+SC), the input prompt includes h exemplars selected from the extended version before the problem of interest. For the connectivity task and cycle task, we set A to 4, for the GNN task, we set l to 1 due to the context size limit, while for other tasks k is 5. We evaluate LLMs and various prompting techniques on the standard set of NL.raph due to monetary costs, while we encourage future research to leverage the extended version for enhanced evaluation.
4 Results
4.1
LLMs Have (Preliminary) Graph Reasoning Abilities
We first find that on intuitively simple graph reasoning tasks, large language models achieve impressive performance and demonstrate preliminary graph reasoning abilities. As demonstrated in Table 2 LLM performance on the connectivity, cycle, and shortest path tasks is significantly better than the R RANDMM baseline, indicating that L.LMs are not giving random answers and they do have preliminary graph reasoning abilities. the first two tasks with true/false questions, L.LM performance is 37.33% to 57.82% higher than random with COT or CoT+SC prompting. The performance is also impressive
5

---

75
20
Arc
50
51.7
54.4
50.5
37.8
easy
15.3
12.0
10.0
casy
4.0
2ero-shot fow-shat
D.CoT
CoT
CC
LTM
zero-shat
fow-shat
O-CaT
CaT
CoT+5C
20
med kum
hard
Acc
2.5
2.0
0.0
0.9
0.2
zero-shot few-shat
D-CoT
CoT
CoT+
LTM
zero-shot
few-shot
O-CoT
CoT
Col++9C
topological sort
maximum flow
Figure 2: (left) Model performance the topological sort task. COT, LTM, and self-consistency are mostly ineffective on this problem. (right) Model performance on the maximum flow task. FEW-SHOT prompting outperforms CoT+SC prompting on both easy and hard subsets, suggesting that LLMs fall short of generating valid intermediate steps to solve the more complex graph reasoning problem. Together these results demonstrate that advanced prompting ineffective for advanced graph reasoning.
in the ZERO-SHOP setting, the accuracy is 33.81% % and 23.33% higher on the connectivity and shortest path task than random even without any exemplars and chain-of-the of-thought reasoning. Though the shortest path is intuitively harder than the first two true/false tasks since it requires generating the specific shortest path in the response, L.LM combined with CoT and COT+SC achieves an accuracy 22.81% % to 62.83% higher than RANDOM. Together these results demonstrate that large language models do possess preliminary abilities to process graphs and structures in input texts.
4.2 Mixed Results with Advanced Prompting
Table shows that advanced prompting tech- niques such as chain-of-thought [Wei et al.
Method
PC (t)
Acc (t)
RE (4)
2022] and self-consistency (Wang et al.] [2023] simple
ZERO-SHOT
13.61
0.00
20.04
successfully improve performance graph reasoning tasks. For the task of simu- lating graph neural networks (Table 33, chain- of-thought also significantly improves model performance. However, these approaches can be ineffective, even counterproductive on more complex graph reasoning tasks. From the results on the topological sort and maximum flow task (Figure observe that COT, CoT+SC, and LTM prompting generally underperform FEW- SHOT prompting. We believe this may be be- cause LLMS fail to learn the correct way to generate intermediate steps in the face of complex graph reasoning tasks. This casts doubt on the generalizability of CoT, LTM, and self-consistency to more advanced graph reasoning problems.
FEW-SHOT
20.04
0.00
37.83
COT
64.55
31.00
14.34
0-COT
13.85
0.00
44.55
CoT+SC 63.92
28.00
13.28
Table 3: Model performance on the task of simu- lating graph neural networks. PC and RE are two partial credit metrics introduced $2.2 Chain- of-thought prompting significantly improves the model performance across all metrics.
4.3 In-Context Learning Can be Counterproductive
Although in-context learning is widely attributed to teaching LLMs to learn from in-context ex- emplars [Brown et al. 2020], we observe that few-shot in in-context learning fails to improve LLM performance over complex graph reasoning problems. For tasks such Hamilton path and bipar- tite graph matching (Figure 3), zero-shot prompting generally outperforms few-shot learning with in-context exemplars. The results suggest that L.LMs fail learn from the in-context exemplars when the problem involves hundreds of graph-based reasoning steps. In-context exemplars might even distract large language models, evident in that few-shot learning underperforms zero-shot learning by 1.00% to 10.48% Hamilton path and bipartite graph matching. We further study the correlation between the number of exemplars and model performance on the Hamilton path task. As illustrated in Figure when the number of exemplars increases, model performance is not trending up, and the performance consistently lower than zero-shot prompting. These results further suggest that in conoetext learning could be counterproductive in complex structured reasoning.

---

hard
hard
46.7
45.0
48.3
47.0
40
40.0
34.7
40
27.6
20-
20.0
17.5
14.7
20
E7.1
8.5
114
zero-Shot
tew-shot
0-CaT
CoT
CoT+SC
zero-shat
Tew-shot
D-CoT
GoT
COT+SC
Hamilton path
bipartite graph matching
Figure 3: (left) Model performance the Hamilton path task. ZERO-SHOT prompting consistently outperforms all other prompting techniques. (right) Model performance on the bipartite graph matching task. The effect of in-context learning and advanced prompting is also mostly marginal in this complex graph reasoning problem. Together these results demonstrate that in-context learning can be counterproductiive in advanced graph reasoning problems.
Dataset
ZERO-SHOT
FEW-SHOT
COTT
0-CoT
COT+SC
Avg.
GENERAL
74.67
83.33
85.33
66.00
82.67
78.40
CHAIN
51.67 (-23.00)
45.00 (-35.33)
40.83 (-44.00)
92.50 (+26.50)
44.17 (-38.50)
54.83 (-23.57)
CLIQUE
60.83 (-13.84)
73.33 (-10.00) 85.00 (-0.33)
52.50 (-13.50)
83.33 (+0.66)
71.00 (-7.40)
Table 4: Model performance the chain and clique subset of the connectivity task. Large language models indeed rely on spurious correlations in problem settings, evident the reduced performance on the two special cases compared to the general connectivity task.
4.4 LLMs are (Un)surprisingly Brittle
easy
hard
Although large language models achieved per- formance that is significantly better than random on simple graph reasoning tasks ($4.1). we hy- pothesize that LLMs may be able to reach the correct answer by leveraging certain spurious correlations. For example, task, since nodes with higher degrees are more frequently mentioned and they more likely to be connected, LLMs might just be counting node mentions instead of actually finding paths. To this end, we design two special cases (chain and clique) for the connectivity task that the exact opposite of the spurious correlation.
2
12
exemplar
the connectivity
Figure 4: Model performance the Hamilton path task with an increasing amount of exemplars. When more in-context exemplars are introduced, model performance is not trending up and is con- sistently lower than zero-shot prompting in both difficulty settings.
Chain We firstly generate a graph with components, where each components is chain. Formally, G = (V.E) E can be divided into subgraphs G1, G2. ..., Gx. where subgraph G; consists of chain of nodes and edges U1,, ea, U22 62,; Cst, Gst.- We then randomly select query node pairs that are at the two ends of chain, i.e. un and vat,- These nodes only have degree of one but they are actually connected through the chain structure. We curate a chain dataset with 120 examples.
Clique We first generate graph with & densely connected subgraphs. Formally, G = E) can be divided into subgraphs G2....... Ge. where subgraph G, is generated by the random graph generator (.2. with high edge probability p {0.7, 1.0]. We then randomly select query node pairs with each pair in two different densely connected subgraphs, G; and 9j (i ( j). These nodes are associated with a large number of edges and thus are frequently mentioned in the natural language prompt, but they belong to two different subgraphs and are not connected. We curate clique dataset with 220 examples.
We evaluate LLMs with different prompting approaches on the two special cases and compare performances with the general connectivity task in Table LLM performs much worse than ordinary

---

Standard Prompting
Build-a-Graph Prompting
Algorithmic Prompting
We can use a Death-Fint Search (DFS) alponiten to Rid the shortest path between two given nodes undiracted graph
<in context exemplar> undirected graph, the nodes numbered
The idea to start nop tfe nodes and usr DFS to explore all its aujarent nodes At each node jebu can keep track of the distance it takes maach that nade from the stacting node
edges
an edge between node O and node 4 with weight
Clace you have cuploced the agiacent noder pay can Backtrack and pick the mode which har thee sthrttstt distance to mach the destintionn node
<in contoxt exemplar>
Let's consirec a geach with the nodess and
in undirected graph, the nodes numbered from to en edge between node 0 and node with weight 4,
siges frrst
edges
nin-cctteet exemplar>
Give shortest path from node
undirected graph, nodes are numbered from
node 2.
0 to 4, and the edges are:
edge between mode 0 and node with
A the paths from node 0 to 2 are:
an edge between node and node with weight 4,,
weight
0.32 with total wiight of + 4
Give the shortest path from node 0 node
an edge between node 0 and node with
0.1.2
total weight 3
9]
paths from
node
weight 3.
0,4.22
total weight of
0,3, with total weight of
The weight of path 0,32 is the smallest so
0.1.2.2 with total weight of 4 2
Q Give shortest path from to node
the shortest path from node D to node t
0,4.3.2 a total weight 4f + 1 The weight of 0,3,2 the smallest, the shortest path from node to noda 0.3,2 with total weight of
0.3.2 with total weght of
Figure 5: Overview of Build-a-Grapp a-Grrph prompting and Algorithmic prompting. aiming to make LLMs better at reasoning with graphs by encouraging conceptual grounding and algorithmic reflection. Red underline indicates our proposed instructions while green background indicates LLMs' generation.
cases with performance drop of more than 40% across various settings. This suggests that LLMs are indeed (un)surprisingly vulnerable to spurious correlations in structured reasoning.
5 Making Language Models Better Graph Reasoners
5.1 Methodology
We propose two instruction- prompting techniques that improve the graph reasoning ability of LLMs, which can be used together with in-context learning and chain-of-thought prompting.
Braph- Prompting (BAG) We hypothesize that it might be helpful map the textual descriptions of graphs to grounded conceptual spaces [Patel et al. 202T] before tackling the specific problem, i.e. visualizing the graph structure on implicit mental sketchpad. To this end, we propose to use instruction- bbased prompting by appending "Ler's construct a graph with the nodes and edges first." after the textual description of the graph explicitly given. We envision this straightforward instruction would provide LLMs with the buffer zone to digest graph information, map them to grounded conceptual spaces, and better prepare for the incoming query.
Algorithmic Prompting We hypothesize that in order to generate sound and accurate solutions. LLMs would benefit from revisiting and reciting the relevant algorithm for given task (Sun et al. 2023). To this end, we propose to first prepend the algorithm details before the in-context examples by adding "We use Depth-First Search (DFS) algorithm ... for the shortest path task. We similarly provide the algorithm descriptions of other graph reasoning tasks in their respective prompts. We envision algorithmic prompting as empowering LLMs with general understanding of how to solve the problem before actually solving it.
We illustrate our proposed build-a- graph prompting and algorithmic prompting in Figure In the following, we use these two approaches together with chain-of- thouhh prompting and evaluate on three representative tasks in the NLGraph benchmark with varying difficulties.
5.2 Results
Table 5 shows the results of our proposed prompting methods on three representative tasks with varying complexity. On the two easier tasks, cycle and shortest path, our instruction-basse prompting methods resulted in a 3.07% to 16.85% performance gain across the two tasks. However, on the more complex task, Hamilton path, the two natural language instructions are largely ineffective. The result suggests that the two simple instruction- based prompting techniques successfully improve LLMSs graph reasoning abilities on relatively casy graph reasoning tasks, while how to make LLMs better
8

---

Cycle
Shortest Path
Hamillon Path
Method
Easy
Medium
Hard
Avg.
Hard
Easy (PC)
Hard (PC)
Avg.
Easy
Hard
Avg.
COT
84.67
63.33
53.25
66.75
63.89
29.50
76.84
35.79
51.51
40.00
8,00
24.00
CoT-BAG
86.00
69.33
62.00
72.44
67.78
33.50
79.20
42.56
55.76
38.67
6.00
22.34
COT ALGORITTM
77.33
74.00
64.00
71.78
63.89
28.00
76.06
38.70
51.66
36.67
7,50
22.09
Table 5: Model performance the connectivity, cycle, and shortest path tasks with our proposed BAG and ALGORITIM prompting. On the two easier tasks, cycle and shortest path, our instruction- based prompting techniques resulted in 3.07% to 16.85% performance gain across the two tasks. More complex graph reasoning tasks such as Hamilton path remain an open research question.
at reasoning on complex graph reasoning problems remains an open research question. We further explore different variants of the instructions Appendix [D] The NI.Graph benchmark also empowers the evaluation of future instructions and solutions towards making LLMs better graph reasoners.
6 Related Work
LLMs for tasks with implicit graphical structures. Previous works explored the use of LLMs on tasks with implicit graph structures: Huang et al. [022] find that LLMs have the ability to ground high-level tasks (e.g. "make breakfast") to a set of actionable steps (e.g. "open fridge") in structured synthetic environments. Vaalmekam et al. [2022 explore the possibility of using LLMs for vevironmenss/Vllmeeeann
commonsense planning. In theory-of-mind reasoning, Adhikari et al. 2020), Ammanabrolu and Riedl [2021), Sclar et al. [2033 maintain and update structured world representations as the world state change to operate in interactive and situated environments. In structured commonsense reasoning, where LLMs are given a natural language input and then asked to generate a graph such as an event graph Tandon et al., 2019], a reasoning gaaaph [Madaan et al., [021] or an argument explanation graph (Saha et al. 2021], Madaan et al. [2022] find that code language model (CODEX) with tasks framed as code generation tasks outperforms other strong LMs. In multi-hop question answering or knowledge probing, LLMs implicitly find connections and paths among vast network of entities and concepts [Creswell et al. 2023] Yuu et al. 2022 Zhang et al.] 2022a He et al.) 2021]. Recently, Chen et al. [2023] explore the potential of LLMs on the graph node classification task. Together these works demonstrate that LLMs are increasingly adopted for tasks and settings with implicit graphs and structures, while whether LLMs are robust at graph reasoning remains underexplored and may hinder the progress of these structure-aware applications. In this work, we propose the NL.Graph benchmark as a comprehensive testbed towards evaluating the graph reasoning abilities of large language models.
LLMs for few-shot reasoning. There is long line of work on evaluating LLMs' reasoning ability in in-context learning setting, including arithmetic reasoning, logical reasoning, common sense reasoning, and more. Particularly, simple math problem datasets such as AQUA Ling et al. [2017),
GSM8K [Cobbe al. [022]. 1, and SVAMP (Patel et al. 2021] are used for evaluating arithmetic
reasoning Yueya et al.] 2023 Touvron et al.) 2023, Shi et al. 2023 WWlleck et al. 2221]
developed NaturalProofs, multi- dataset for studying mathematical reasoning in natural language. while Welleck et al. [2022) study LLMs' ability to generate the next step in mathematical
proof and generate full proofs. LLMs have also been evaluated on logical reasoning tasks, including symbolic tasks like Coin Flip and Last Letter Concatenation [Wei et al., 2022] and Logic Grid Puzzle on the BIG-BENCH (Srivastava et al. 2023). Commonsense reasoning datasets (Talmor et al.. 2019 Geva et al.] 2021] are also proposed to evaluate large language models. Most relevant to our work, various proposals evaluate and augment the algorithm reasoning abilities of large language models
are explored [Zhou et al. 2022 Lee and Kim, 2023 Zelikman et al. [023] Liu et al. 2023] In this work, we focus on evaluating and enhancing LLMs on graph-base based reasoning and algorithmic tasks inspired by the increasing usage of LLMs in tasks with implicit graphs and structures.
7 Conclusion
In this work, we investigate whether LLMs are capable of explicit graph reasoning, i.e., solving graph algorithm problems in natural language, across various problem categories and prompting techniques. To this end, we curate the NI Graph benchmark, a comprehensive test bed of graph-based reasoning in natural language, with 29,370 problems covering eight tasks with varying complexity. By evaluating

---

LLMs and prompting approaches on the NLGraph benchmark, we find that 1) LLMs do possess preliminary graph reasoning abilities, 2) the benefit of advanced prompting and in-context learning may diminish on complex reasoning tasks, while 3) LLMSs are brittle to spurious correlations in problem settings. We then propose Build-a-Graph and Algorithmic Prompting, two simple instruction- based approaches that bring notable performance gains across multiple tasks. Improving LLMM'' graph reasoning abilities on complex and nuanced graph reasoning tasks remains an open research question, and we encourage future work to develop upon our proposed NLGraph benchmark.
Acknowledgements
We would like thank the reviewers, the area chair, Jiacheng Liu, Minnan Luo, and members of the UW NLP Group for their comments and feedback. This material is funded by the DARPA Grant under Contract No. HR001 120C0124. We also gratefully acknowledge support from NSF CAREER Grant No. IIS2142739, the Alfred P. Sloan Foundation Fellowship, and NSF grant No. ISS2203097. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily state or reflect those of the United States Government or any agency thereof.
References
Wenlong Huang, Pieter Abbeel, Deepak Pathak, and Igor Mordatch. Language models as zero-shot planners: Extracting actionable knowledge for embodied agents. In International Conference on Machine Learning, pages 91 18-9147. PMLR, 2022.
Jacob Andreas. Language models as agent models. Findings the
the Association for Computational Linguistics: EMNLP 2022, pages 5769-5779, Abu Dhabi, United Arab Emirates, December 2022, Association for Computational Linguisties. URI. httptpsse/cccaaaaoooooo.oooooo/e 2022
f madiings-emnlp 423
Ashutosh Adhikari, Xingdi Yuan, Mare-Alexandre Côté, Mikuláš Zelinka, Marc-Antoine Rondeau, Romain Laroche, Pascal Poupart, Jian Tang, Adam Trischler, and Will Hamilton. Learning dynamic belief graphs to generalize on text-based games. Advances in Neural Information Processing Systems, 33:3045-3057,, 2020.
Prithviraj Ammanabrolu and Mark Riedl. Learning knowledge graph-based world models of textual environments. In A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL https:://pperrviiii fforumiid=2244 1e6
Niket Tandon, Bhavana Dalvi, Keisuke Sakaguchi, Peter Clark, and Antoine Bosselut. WIQA: A dataset for "what if..." reasoning over procedural text. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLPP) pages 6076-6085 Hong Kong, China, November 2019. Association for Computational Linguisties. doi: 10.19169//// URL htttss//acclatthlleee org
org/D19- /D19//1991111 1629
Aman Madaan, Shuyan Zhou, Uri Alon, Yiming Yang, and Graham Neubig. Language models of code are few-shot commonsense learners. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 1384-1403, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. URL https://acllanbbot
org/2022. emneemmmmmmm -aammnlpm......m mwin.ainn... 90
Antonia Creswell, Murray Shanahan, and Irina Higgins. Selection-infereneee Exploiting large language models for interpretable logical reasoning. In The Eleventh International Conference on Learning Representations, 2023. URL /tttl:://///:eereeeee eview..eiww..o wttp://w......ooo.....a...eeeee.
A4
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et Language models are few-shot learners. Advances in neural information processing systems, 13:1 2020.
10

---

Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang. Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35: 27730-27744, 2022.
Sébastien Bubeck, Varun Chandrasckaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4, arXiv preprint arXiv: 120..122.. 2023.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoc Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL httpt:ttopsesre/////eee/ wwt./eee///oiicco LViQIMeBB_J
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors. Advances in Neural Information Processing Systems, 2022. URL https://openreviiet www.:nnee/oormmmmm 22BBb5y0yFf
Denny Zhou, Nathanael Schärli, Hou, Jason Wei, Nathan Scales, Xuezhi Wang. Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoe V Le, and Ed H. Chi. Least-to-most prompting enables complex reasoning large language models. In The Eleventh International Conference on Learning Representations, 2023. URL. htt.htttts///eeeeeeee evieennrrviee..mmm nett/forumm2dd-W270098888
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2023. URL
htttps://openrevieu
Roma Patel and Ellie Pavlick. Mapping language models to grounded conceptual spaces. In International Conference on Learning Representations, 2022. URL https: net/
Arkil Patel, Satwik Bhattamishra, and Navin Goyal. Are NLP models really able solve simple math word problems? In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2080-2094, Online, June 2021. Association for Computational Linguistics. doi: 10. 10.18653/v1/20211 -naacl-mail 168. URL htt.:/ttts///caaatttttto
org/ 2021 www.aaalllaaaa -main. 168
Zhiqing Sun, Xuezhi Wang, Yi Tay, Yiming Yang. and Denny Zhou. Recitation-augmennee language models. In The Eleventh International Conference on Learning Representations, 2023. URL
httpp:://ppenrevie: net htt/://ormmddddoooee
NI]
Karthik Valmeekam, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati. Large language models still can't plan (a benchmark for LLMs on planning and reasoning about change). In NewrlPS 2022 Foundation Models for Decision Making Workshop, 2022. URL
https://openrevier. wtt.riiwwwweeeeeeeeeeeeeeeeeeeee fott://ormmidd=uu-----
Melanie Sclar, Sachin Kumar, Peter West, Alane Suhr, Yejin Choi, and Yulia Tsvetkov. Minding language models' (lack of) theory of mind: plug-and-play multi-character belief tracker. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 13960-13980, Toronto, Canada, July 2023. Association for Computational Linguistics. doi:
1o8.. 780. URL
org/2023
acl Min-long.78 780
Aman Madaan, Dheeraj Rajagopal, Niket Tandon, Yiming Yang, and Eduard Hovy. Could you give me a hint generating inference graphs for defeasible reasoning. Findings of the Association for Computational Linguistics: ACI-IJCNLP 2021, pages 5138-5147, Online, August 2021.
Association for Computational Linguistics. doi: 10. 18653//11/2222 http://////....nnnnnaaaealllelle findings-acl4456 JRL.https
//aclanthology org/
org/2021 2021. windings--sait acl 456

---

Swarnadeep Saha, Prateck Yadav, Lisa Bauer, and Mohit Bansal. ExplaGraphs: An explanation graph generation task for structured commonsense reasoning. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 7716-7744 Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguisties. doi: 10. 18.18653/ v1/2021 172002.emmll-mman..6000 URL http:/tt//calaaatooolooooo
wwgg///..eeeeeeeeeeee wew.:emmmpppmm....m. 609
Xinyan Velocity Yu, Sewon Min, Luke Zettlemoyer, and Hannaneh Hajishirzi. Crepe: Open-domain question answering with false presuppositions. arXiv preprint arXiv:2211.172577 2022. URL
https://arxiv.orgg
2211. 17257
Xikun Zhang, Antoine Bosselut, Michihiro Yasunaga, Hongyu Ren, Percy Liang, Christopher D Manning, and Jure Leskovee. GreaseLM: Graph REASoning enhanced language models. In International Conference on Learning Representations, 2022a. URL net/fforun1dd441e86644pj
Tianxing He, Kyunghyun Cho, and James Glass. An empirical study on few-shot knowledge probing for pretrained language models, 2021.
Zhikai Chen, Haitao Mao, Hang Li, Wei Jin, Hongzhi Wen, Xiaochi Wei, Shuaiqiang Wang, Dawei Yin, Wenqi Fan, Hui Liu, et al. Exploring the potential of large language models (Ilm)) in learning on graphs. arXiv preprint arXiv:2307.00 03393, 2023.
Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom. Program induction by rationale gen- eration: Learning to solve and explain algebraic word problems. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 158-167, Vancouver, Canada, July 2017. Association for Computational Linguistics. doi: 10.18653//1/P17-1000 1015. /RL//ttts::/cclaattoo// wtt.a//ttooooooooo//----o-. owtpp17-1//1111111111
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 10. 14168, 2021.
Joy He- Yueya, Gabriel Poesia, Rose E Wang, and Noah D Goodman. Solving math word problems by combining language models with symbolic solvers. arXiv preprint arXiv:2304.09/00 2023.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. / 13971, 2023.
Freda Shi, Xinyun Chen, Kanishka Misra, Nathan Scales, David Dohan, Ed H Chi, Nathanael Schärli, and Denny Zhou. Large language models can be easily distracted by irrelevant context. In International Conference on Machine Learning, pages 31210-310 312277 PMLR, 2023.
Sean Welleck, Jiacheng I. Liu, Ronan Le Bras, Hannaneh Hajishirzi, Yejin Choi, and Kyunghyun Cho. Naturalproofs: Mathematical theorem proving in natural language. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1), 2021. URL Jdxaiiiaarada
httpp:///pearreview..e
Sean Welleck, Jiacheng Liu, Ximing Lu, Hannanch Hajishirzi, and Yejin Choi. Naturalprover: Grounded mathematical proof generation with language models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL http:////ppppaaeee..ea/aaa//a//p
Aarohi Srivastava, Abhinay Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam Brown, Adam Santoro, Aditya Gupta, Adrià Garriga- et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. Transactions on Machine Learning Research, 2023.
Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. CommonsenseQA:: question answering challenge targeting commonsense knowledge. In Proceedings of the 2019 Conference of the North American Chupter of the Association for Computational Linguistics: Human Language Technologies. Volume 1 (Long and Short Pupers), pages 4149-4158 Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10.1 8653/v1/N19 1421. URL httpss //aclanthology org/ 1421
12

---

Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant. Did Aristotle Use a Laptop? A Question Answering Benchmark with Implicit Reasoning Strategies. Transactions of the Association for Computational Linguistics (TACIL), 2021.
Hattie Zhou, Azade Nova, Hugo Larochelle, Aaron Courville, Behnam Neyshabur, and Hanie Sedghi. Teaching algorithmic reasoning via in-context learning. arXiv preprint 1..iv:22211.00666. 2022.
Soochan Lee and Gunhee Kim. Recursion of thought: divide-and-com andide-and-oonueer approach to multi- context reasoning with language models. In Findings the Association for Computational Linguistics: ACL 2023, pages 623-658, Toronto, Canada, July 2023, Association for Computational org. 2023
Linguistics. doi: 10. (6653////022.ffnniingg findings-acI.40
URL
Eric Zelikman, Qian Huang, Gabriel Poesia, Noah D Goodman, and Nick Haber. Parsel: A (de- compositional framework for algorithmic reasoning with language models. arXiv preprint arXiv:2212.10561 2023.
Chenxiao Liu, Shuai Lu, Weizhu Chen, Daxin Jiang, Alexey Svyatkovskiy, Shengyu Fu, Neel Sundaresan, and Nan Duan. Code execution with pre-trained language models. In Findings of the Association for Computational Linguistics: ACL 2023, pages 4984-4999, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10. 18653/v1/2023 indings-acl.308. URL https://aclantholoogy org.oo////// 2023. aindings-acl... 308
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205. 00.5500006. 01068, 2022b.
13

---

A
Discussion
NLP tasks and graph tasks alignment. Originally designed for processing language, LLMs increasingly adopted for NLP tasks with structural implications. For instance, structured common- sense reasoning is similar to topological sort in that they both need to find solution satisfying diversified constraints between entities. In the belief state graph in theory-of-ming [Adhikari et al.
determine the connectivity of nodes, which corresponds to the connectivity task. In multi-hop question answering [Creswell et al. [023). LLMs implicitly find connections and paths among vast network of entities and concepts, which resembles the shortest path task and connectivity task. However, we acknowledge that not all graph reason- ing tasks in the NLGraph benchmark are clearly aligned with certain applications. thus advanced graph reasoning tasks in the NLGraph benchmark could also be viewed as test of language model reasoning ability.
2020 Ammanabrolu and Riedi 2021], the final task
The NLGraph benchmark envisioned as reasoning benchmark. In addition to evaluating graph reasoning abilities, the NLGraph benchmark can also be viewed as structural benchmark to evaluate language model reasoning. While ample LM reasoning datasets exist [Cobbe et al.] [222]] Patel et al. 2021 Talmor a 2019 it is difficult to avoid train-test overlap since problems such as grade school math [Cobbe et al. 2021] and commonsense reasoning [Talmor et al. 2019 might be readily available in pretraining corpora, making it less convincing for evaluating reasoning abilities. On the contrary, the synthetic graph reasoning problems and their answers are highly unlikely to have exact matches in the training corpora, which makes NLGraph more robust benchmark towards evaluating language model reasoning.
Fine-tuning to clicit graph reasoning abilities. To further study the graphical thinking abilities of LLMs, we envision fine-tuning as a possible direction for future work. We plan to fine-tune language models the chain-of- of-thought reasoning process towards graph-baser baah-based tasks both single- and multi-task settings to see if fine-tuning might lead to enhanced graph reasoning abilities.
B Limitations
Tasks in NLGraph benchmark are not complete. While we have incorporated eight graph reasoning tasks with varying complexity in the NLGraph benchmark, there are many more important graph algorithms that test different levels of graph reasoning abilities. It might also be interesting to see how LLMs perform on other graph tasks such finding the Eulerian path, the minimum spanning tree, and the cut-edge.
Language models that we evaluate are not complete. We only consider four black-box LLMs, TEXT-DAVINCI-ONS CODE- DADE-DAVVNCI-002 3PT-3.5-TURBO, and GPT-4 in our experiments. Since will make the NLGraph benchmark publicly available, we leave it to future work evaluating the graph reasoning abilities of other open-source LLMs.
Limited dataset size. Due to monetary costs, we only evaluate LLMs on the standard version of the NLGraph benchmark which has 5,902 problems throughout the paper. We believe evaluating LLMs on the extended version of the NL.Graph benchmark, with 5x more problems, may bring stronger proof the findings we present.
Methods for improving graph reasoning abilities. The two prompting methods we present are simple instruction-based approaches, which work easy graph reasoning problems to varying extents. However, on more complex graph reasoning problems, as the overall graph reasoning abilities of LLMs are limited, the instruction-based methods seem have only marginal effects. In future work, we hope to investigate methods such as asking LLMs to generate and execute code, or simulating steps of algorithmic solutions while maintaining the state variables.
C NLGraph Details
In Table we provide the details of the NI.Graph benchmark including edge probabilities and specific values of parameters mentioned in 2.2
14

---

Subset
Connect.
Cycle
Topo Sort
Shortest Path
Maximum Flow
Bipartite Graph
Hamilion Path
GNNs
14;
1-30
0.540.7
04,06
MEDrUM
033 0.7, 1.0
m: 1-4
0,3, 0.5.
pr 03.07
ye 0.3.0.
1-20
Table 6: Details of the NLGraph benchmark, denotes the edge probability, Other characters have the same meaning mentioned in
Shortest Path
Method
Easy
Hard
Easy (PC)
Hard (PC)
BAG BAG-DOT
67.78
33.50
79.20
42.56
65.00
29.00
75.55
37.18
ALGORITUMIC-DOT
66.67
31.00
78.27
39.68
INSTRUCTION #1
66.22
32.50
78.18
40.32
INSTRUCTION #2
67.78
28.50
77.32
37.06
INSTRUCTION #3
67.78
30.50
79.56
37.89
Table 7: The results of variants of instructions on the shortest path task. The BAG prompting approach achieves the best performance across three of the four settings.
D Analysis
Instruction variants To further study the effect of BAG prompting and ALGORITIIMIC prompting. we replace the instructions with only sequence dots (...) equal to the number characters in the instruction. This is to investigate whether the improved performance is attributed the natural language instructions or simply increased computation. We also replace the BAG prompting with three other instructions not directly related to graph problems, specifically, Let's think step by step (INSTRUCTION 1), Examine each detail carefully (INSTRUCTION 2), Think it through systematically (INSTRUCTION 3). As illustrated in Table 7 the BAG prompting method generally outperforms the instruction variants, indicating the effectiveness of this method.
Graph definition variants We study how replacing the abstract descriptions of graphs with real- world objects would impact model performance. Specifically, for the shortest path task, change all the "node"s into "sity"s, "edge"s into "road"s, and "weight"s into "distance"s 's. As shown in Table 9 the model performance improves on the easy subset but drops on the hard subset. While language models are indeed sensitive to the specific instantiations of the graph description, the results are mixed as to which is casier or harder.
medium
hard
100
84.67
63.33
53.25
exemplar
40
medium
62.00
52.67
49.75
20
40
4
7
52.25
# node
Figure 6: Model performance for the shortest path task with different numbers of nodes on the shortest path. The per- formance steadily drops when the path length increases.
Figure 7: Model performance for the ey- cle task with varied exemplar difficulty. When the in-context exemplars are based on more difficult problems, the perfor- mance becomes worse.
15

---

Cycle Medium
Shortest Path
Hamilton Path
Method
Easy
Hard
Easy
Hard
Easy (PC)
Hard (PC)
Easy
Hard
RANDOM
50.00
50.00
50.00
50.00
50.00
6,07
6.69
0.00
0,00
FEW-SHOT
58.00
50.00
49.75
39.44
28.50
55.10
37.63
36.67
7,00
COT
60.67
66.83
69.00
41.11
45.00
50.00
12.00
CoT+SC
59.33
52.67
53.75
42.22
49.26
34.00
5.00
Table 8: The results CODE-DADE DODE-DAVICII-02 on the cycle, shortest path, and Hamilton path task.
Shortest Path
Method
Easy
Hard
Easy (PC)
Hard (PC)
RANDOM
50.00
50.00
6.07
6.69
ZERO-SHIOT
29.40
14.00
47.53
20.13
FEW-STIOT
41.11
20.50
58.78
29.28
COT
73.33
28.00
82.57
35.50
0-CoT
6.67
2.00
65,40
51.95
CoT+SC
72.78
27.00
83.50
35.19
Table 9: Model performance when graph descriptions are changed into cities, roads, and distances on the shortest path task.
LLMs are brittle to problem scales For the shortest path task, study the correlation between model performance and the number nodes on the optimal shortest path. We group problems by the shortest path length and present results in Figure for the CoT approach, which shows that the accuracy steadily drops when the number nodes on the shortest path increases. While the reasoning process towards finding the shortest paths stays the same for optimal solutions with varying lengths, large language models are not robust to changes in graph scales and problem settings.
In-context exemplars and test difficulty We investigate the model performance when the in- context exemplars and test difficulty vary. For the cycle task, write -fain-of-thought solutions for problems selected from the medium and hard subsets, and evaluate TEXT-DAV DEXT-DAVINCI-00: on the eycle task with the two prompts. We present the results in Figure 7 The performance drops when the exemplar difficulty increases, indicating that LLM struggles to learn from exemplars with more difficulty.
Partial credit for the maximum flow task We provide partial credit for the maximum flow task in Table 10 The performance generally has the same trend as the results provided in Figure 2 Though on the hard subsets, the performance of CoT is the highest, we believe this is more like guessing, as when CoT combined with celf-consistency, the performance drops signifi- cantly.
Method
Easy
Hard
ZERO-SHOT
25.65
10.37
FEW-SHOT
24.83
12.37
COT
16.99
22.07
O-CoT
17.41
7.04
COT+SC 9.88
8.62
Table 10: Partial credit for the maximum flow task.
E
Additional Large Language Models
E.1
CODE-DAVINCI-002 Results
We evaluate CODE-DAVINCI-OOS on cycle, shortest path, and Hamilton path. The results are provided in Table g The findings are mostly similar to TEXT-DAVINCI-003: language models are preliminary graph reasoners on easy tasks while the benefit of in-context learning and advanced prompting is limited on more complex problems. However, in the CoT and CoT+SC settings, CODE-DAVINCE 002 generates too many tokens before reaching the final answer, so we do not present the results in Table g
16

---

E.2 OPT Results
We fine-tune OPT-2.7B [Zhang et al. 2022b and evaluate the model on the NLGraph benchmark. We randomly divide the standard version of the NLGraph benchmark into 4902 training problems and 1. 1,000 test problems. We generate zero-shot solutions for the training problems, combine the solutions with the problems, and attain nine corpus of text (i.e. one for each task and one that concatenating all the text). We then fine-tune OPT on the nine corpus separately. However, we find that fine-tuning did not elicit the graph reasoning abilities of OPT-2. BB: the generated text is mostly meaningless, falling short of answering questions and following formats. We leave future work on fine-tuning larger language models to elicit graph reasoning abilities due to our limitations in computational resources.
E.3 Qualitative Analaysis with GPT-3.5-TURBO and GPT-4
Due to monetary costs, we only conduct qualitative analysis on GPT-3.5-TURBO and GPT-4 with 19 representative problems across the eight tasks. We provide the results in Table [1 Table 12 Table 13 Table 14 Table 15 Results demonstrate that while GPT-4 does present better graph reasoning abi abilities, it is still far from being robust reasoner towards graph-based problems.
17

---

Table 11: Results of GPT-3.5 3.7-3.5-TUBBO and GPT-4 on 19 cases (#1 to #6 example) through the eight tasks. We omitted the CoT in-context exemplars in the table.
Question
GPT- 3.RRTURRO
GPT-4
Determine there a path between two nodes the
directly connected to node 5, but we can follow the path: 4->0-2652-255, so the answer is yes.
Node
Node only connected node which does not have any connections to the other nodes in the graph. Node the connected block consisting of nodes I, 2, 5, and 6. Node and node are block, so the answer no.
graph. Note that (i.) means that node and node j
connected with an undirected edge, Graph: (0,4) (1.3)
(1,2) (1.6) (2.6) (3,5) (5.6) Q: Is there a path between node 4 and node 5?
X
the same connected
Determine if there is a path hetween two nodes in the
Node 6 is connected to node O, node connected node 3. We can fol- low the path: 6-20=>3, the answer yes.
A: Node 6 is connected to node 2, node 2 is connected to node 3. can follow the path: 6-22-23, the answer is yes.
gruph. Note that (i.) means that node and node
connected with an undirected edge. Graph: (0,3)
(0,11) (0.8) (0.6) (0.1) (1,10) (1.3) (1.5)
(2,0) (2.3) (2.5) (2.9) (2.8 (2.7) (2.6) (2,13)
(3,11) (3.8) (3,7) (4.12) (5,10) (5.9) (5.8) (5.7) (5.6)
(7.13) (8,10) (8,1 (8)13) (9,10) (9,11) (9,13) (10, (10,13)
(6,10) (6.9) (1) (6.8) (7.10) (7.1
Q: Is there a path between node 6 and node
undirected graph, (i.)) means that node and node j are connected with an undirected edge. The nodes are numhered from O in 7, and the edges are: (2,4) (0.3)
The edges (1,2), (2.4), (4,0), (0.3),
The edges (1,0), (1.2), (1,5), (6.5), (5,7) do not form cycle. However, the edges (1,0), (1.2), (2,4) do form cyele. So yes, there eycle in this graph. X
(3,1) form cycle, so yes. there eycle in this graph. X
(5,7) (1.5) (6,5) (1,0)
Q: Is there a cycle in this graph?
In undirected gruph. (i.)) means that node and node j are connected with an undirected edge. The nodes are numbered from 7, and edges are: (1.7) (0.6)
The edges (0,6), (6,4), (4.5), (5,7), (7.1), (1.0) form cycle, so yes, there is cycle in this graph. X
The edges (1,7), (7.2), (2,0), (0.1) form cycle, so yes, there is a cycle in this graph.
(1.3) (4,5) (1.0) (0.4) (0,2) (7.2)
Q: Is there a cycle in this graph?
In an undirected graph, the nodes are numbered from to S, and the edges are: An edge between node and node 0 with weight 2, An edge between node 0 and node 4 with weight An edge between node
All the paths from node 3 to node
All the paths from node 3 node are: 3,2.0 with a total weight of + = 3.1.2,0 with a total weight of +
are: 3.2,0 with total weight of 2
2= 3,2,4.100 with a total weight
of 4
3,2,4,0 with total weight of 3 = 3,1,4. with 3,12200
3,4,0 with total weight of 3 1 4, 3,4,2,0 with total weight 3
node 2 with weight 4, An edge between node and
node 3
weight 4, An edge between node
total weight with total weight of 44 + 2= 10, 3,5,2,0 with total weight of 2
with total weight of 2 2 3,5,00 3.5.4.0 with a total weight of 2+ 5.
node I with weight 4, An edge between node 2 and
node 3 with weight 1, An edge between node and
node 5 with weight An edge between node and
= 3,5,4,0 with total weight of +++++ 55 The weight of puth 3,2,0 and 3,5,4.0
node 4 with weight 3. An edge between node and
The weight of path 3.2.0 is the small- est, so the shortest path from node to node i 3,2.0 with total weight of 3. V/
node 3 with weight 2, An edge between node and
smallest, so the shortest path from node 3 to node O either 3,2.0 or 3,5.4.0. both with total weight of X
node 4 with weight An edge between node 4 and node with weight
Q: Give the shortest path from node 3 to node O.
undirected graph, nodes are numbered from to 4, and the edges are: An edge between node and node O with weight 1, An edge between node 2 and node O with weight An edge between node and node I with weight 1. An edge between node I and weight An edge between node
the paths from node 3 to node are: 3,2,1 with a total weight of 3 6, 3,2,0,1 with a total weight of 1
the paths from 3 to node
are: 3,2,1 with total weight of
3 6, 3,2.0. with a total weight of 3 1 =55.
3,2,1.0,1 with
total weight of 3 1 + + 1 6. 3,2,0,1.4.1
The weight of path 3,2,0.1 is the smallest, so the shortest path from node 3 to node is 3,2,0,1 with to- tal weight 5f V
node 2
total weight 1 ++1+++ 1 = 5. The weight of path 3,2,0,1 the smallest, so the shortest path from nade to node is 3,2,0,1 with total weight 3f X
node with weight 3.
Q: Give the shortest path from node 3 to node 1.
18

---

Table 12: Results of GPT-3. OPT-3.5-TURBO and GPT-4 on 19 cases (#7 to #9 example ) through the eight
tasks. We omitted the CoT in-context exemplars in the table.
Question
GPT- TURRO
GPT-4
In an undirected graph, the nodes are numbered from to 6, and the edges An edge between node and
All the paths from node 2 to node
All the paths from mode 2 to node
2,0,3 with total weight of
2,0,3 with total weight of I
node 2 with weight 1, An edge between node 3 and
5, with a total weight of
2.1.3 with a total weight of +
node 0
weight 4, An edge between node and
=, 2,4.3
total weight of
=., 2,10,3 with total weight
node 0 with weight 2. An edge
between node 4 and
3 2 5. The weight of puth 2,0,3
4.4 10, 2,1,6,3 with a total weight 2 2 ++++ 4 2,4.3 with total weight of 3
node 0 with weight 3, An edge between node and
the smallest, so the shortest path
node I with weight An edge
between node and between node 2 and
from node node 3 2,0,3 with
2,4,0,3 with total weight 3 3- 3-3+4= 2,41.. weight 3+ 33=
node 6 with weight 2. An edge
total weight of 5. X
node 1 with weight An edge
between node and
with
node I with weight 3, An edge
between node 4 and
2,4,1.0,3 with total weight of 3 4 4= 14, 2,4.1.666, with total weight of 3 + 3+ 2+4 12, 2.5.0.3
node 1 with weight 3, An edge
between node and
node 6 with weight 2, An edge
between node and
node 5 with weight 4, An edge
between node 2 and
with a total weight of 4 2,5,4,3 with total weight 4 2 11. 2,5,4,0,3 with a total weight of 5 3
node with weight An edge
between node and
node 2 with weight 2. An edge between node 3 and
node 5 with weight 1, An edge
between node and
1,, 2,5,411, with total weight of 4 5 3 15, 2,5,6,3 with total weight of 4 +4= 14, 2,6,1,3 with total weight of 2 + 3 =7 2,6,1,0,3 with total weight 2,6,5,0,3 with total weight of + ++2+ 4= 13, 2,6,,,3 with total weight of 2 5 == 14.
node 3 with weight 2. An edge
between node 3 and
node 6 with weight 4, An edge between node 4 and
node 5 with weight An edge between node 4 and
node 6 with weight 1, An edge between node 6 and node with weight
2+++4++
Q: Give the shortest path from node 2 to node 3,
The weight of paths 2,0,3, 2.1.3, and 2,4.3 the smallest. So. there three shortest paths from mode 2 to node 3, which are 2,0,3; 2,1,3; and 2,4.3. each with total weight of S. x
In a directed graph with S nodes numbered from 0 to 4: node should be visited before node
This is not possible as there is cycle between nodes D, and 4. Node cannot be visited before nodes 0, and 4, and nodes 0, I, and 4 cannot he visited hefore node Thereforee, it not possible to visit all the nodes in this graph. X
Since nodes are required to be vis- ited before node 2 and node node and node can visited first. Since visiting node 4 requires visiting node first, node 2 is visited, node can be visited. Since visiting node O requires visiting node 2, node 4 first, after node 2 and node are visited, node O can be visited. Since visiting node requires visiting node 2. node 4 first, after node 2 and node are visited, node I can be visited. So the solution is: 2,3,4.0,1
node should be visited before node
node 2 should be visited before node 0
node should visited hefore node
node 4 should be visited before node 0
Q: Can all the nodes be visited? Give the solution.
In a directed graph with nodes numbered from to
This graph has cycle, which means it is not possible to visit all nodes in valid order. Specifically, there is cycle between nodes 1, and which cannot be resolved bused on the given constraints. X
no nodes required ited before node 4, node 4 can be visited first, Since visiting node and node 3 requires visiting node first, after node 4 is visited, node be visited. Since
node 0 should be visited before node 1
node should be visited before node 2
node should he visited before node
node 3 should be visited before node 2 node should be visited before node
and node iting node I requires visiting node node first, after node are visited, node I can be vis- ited. Since visiting node 2 requires visiting node I and node 3 first, after node I and node 3 are visited, node can be visited. So solution is: 4,0.3.1.2. M
node 4 should be visited before node 0
node should he visited before mode
and
Q: Can all the nodes be visited? Give the solution.
19

---

Table 13: Results of GPT-3.5-TURBS and GPT-4 on 19 cases (#10 to #12 example through the eight tasks. We omitted the COT in-context exemplars in the table.
Question
GPT-3.5 1.r1-3,5-uue 3,5-TO
GPT-4
In a directed graph with nodes numbered from 0 to
Since no nodes are required to be vis- ited before node 3 and node node and node can he visited first. Since visiting node 0 requires visiting node 3 first, after node 3 is visited, node can be visited. Since visiting node requires visiting node O, node 2, node first, after node 0, node 2, and node are visited, node can be visited. Since visiting node 5 requires visit- ing node O, node first, after node D and node are visited, node can be visited. Since visiting node re- quires visiting node 4, node first, after node 4 and node are visited, node can be visited. So the solution is: 1,,,
Since no nodes are required to be vis- ited before node 3 and node 4, mode and node can be visited first. Since visiting node 0 requires visiting node and node 4 first, after node 3 and node are visited, node can ited. Since visiting node 5 requires visiting node 0 and node first, after node and node 3 visited, node can be visited. Since visiting node requires visiting uade node 2, and node 3 first, node 2 must be visited before node 1. Since visiting node requires visiting node 4 and node first, after node 4 and node 5 are visited. node can be visited. Now, since node D node 2, and node 3 have been visited, node I can be vis- ited. So the solution is: 3,4,0,5.2.1.
node should be visited before node 5
node should he visited before node
node should be visited before node
node 3 should be visited before node 0
node should he visited before node
node 3 should be visited before node
node should be visited before node 0
node should be visited before node
node should be visited before node 2
Q: Can all the nodes be visited? Give the solution
In a directed graph, the nodes are numbered from O to 5, and the edges ure: an edge from node to node with capacity 4.
There is no path from node 4 to node D so the maximum flow from node node O. X
From the source (node 4), we can send unit of flow to node 3, and units of flow to node S.
an edge from node to node O with capacity 9,
unit of flow arrives at node 3, then we send unit flow from node to node I.
an edge from node 2 to node with capacity
an edge from node 3 to node I with capacity 4. capacity an edge from node 4 to node 5 with capacity 2.
an edge from node to node
units of arrive at node then we can send 2 units of flow from node to node O.
an edge from node to node I with capacity 4.
an edge from node to node (1 with capacity
unit of flow arrives node then we can send I unit of flow from node node O.
Q: What is the maximum flow from node 4 to node 0?
The total unit of flow arrives at node 3. So the maximum flow from node to node 0 is 3.
In a directed graph, the nodes are numbered from 0 to 7, and the edges are: an edge from node to node with capacity I,
From the source (node 2). we can send units of flow to node 7, and units of flow node 1.
From the source (node 2). we can send units of flow to node and units of flow to node 7.
an edge from node to node 7 with capacity 10, an edge from node to node with capacity
8 units of flow arrive at node 7, then we can send 5 units of flow from node to node 6, and 3 units of flow from node to node 5,
units of flow arrive at node then we can send 9 units of flow from node to node 3.
an edge from node 2 to node 7 with capacity 8,
an edge from node to node 1 with capacity 9.
units of flow arrive at node 7, then send 8 units of flow from node to node 5, and 5 units of flow from node to node
an edge from node to node 6 with capacity 10,
units of flow arrive node then we cun send 9 units of flow from node node
un edge from node 3 to node 4 with capacity 7.
an edge from node to node with capacity
an edge from node 5 to mode 3 with capacity 7.
units of flow arrive at node 6, then we can send unit flow from node node 4. units of flow arrive at node 3, then we send 7 units of flow from node to node 4.
8 units of flow arrive at node 5, then we can send 7 units of flow from node to node and unit of flow from node 5 to node
an edge from node to node with capacity 9, an edge from node to node 4 with capacity
an edge from node 7 to node 5 with capacity 8,
an edge from node 7 node 6 with
14 units flow arrive node then we can send 14 units of flow from node to node
Q: What is the maximum flow from node 2 to node
total unit of flow arrives at node 4 8. So the maximum flow from node to node 4 is 8. V
The total unit of flow arrives at node
14. So the maximum flow from node to mode 4 is 14. X
20

---

Table 14: Results of GPT-3.5 and GPT-4 on 19 cases (#13 to #16 example through the eight tasks. We omitted the COT in-context exemplars in the table.
Question
GPT-3,5 TURBO
GPT-4
In a directed graph, the nodes are numbered from 0 to 7, and the edges are: an edge from node to node
There is no path from node I to node 6 this graph, so the maximum flow from node to node 6 is X
From the source (node 1), we can send units of flow to node 7, and units of flow node 2. units of flow arrive at node 7, then we can send units of flow from node 7 to node 4, and units of flow from node node 1.4 units of flow arrive at node 4, then we flow from node 4 to node D. 3 units of flow arrive node then send 3 units of flow from mode 0 to node 3 units flow arrive at node 2. then we can send units of flow from node to node 4. 3 units of flow arrive at node 4, then send units of flow from node 4 to nade 0, 3
with capacity 9.
un edge from node 0 to node 3 with capacity 7.
an edge from node to node 7 with capacity
an edge from node to node 2 with capacity 3.
an edge from node to node 7 with capacity 7.
an edge from node to node 4 with capacity
send units of
an edge from node 3 to node 5 with capacity 7,
an edge from node to node 1 with
an edge from node 4 to node 0 with capacity 3.
an edge from node to node 7 with capacity 5,
an edge from node 6 to node 5 with capacity 6.
an edge from node to node 7 with capacity 6. an edge from node to node 0 with
an edge from mode 7 to node 4 with capacity 4, an edge from node to node
capacity
of flow arrive at node 0, then we can send 3 units of flow from node 0 to node
Q: What is the maximum flow from node I to node 6?
The total unit of flow arrives at node is 6. So the maximum flow from node node 6 is 6. X
In undirected gruph. (i.)) meuns that node and node j are connected with an undirected edge. The nodes are numbered from 6, and the edges are: (4.3) (6,5) (3,0) (2.4) (1. (1,0) (5,2) (4,0) (2.3) (0,2) (6.2) Q: Is there path in this graph that visits every node exactly once? If yes, give the path. Note that path, adjacent nodes must be connected with edges.
No, there is puth that visits every node exactly once. This graph con- tains two disconnected components: 0, 0,1,2.3,4 and 5,6. It is not possible to visit all nodes in a single path be- cause there no edge connecting the two components. X
Yes. We start node As node is connected with node 0, and node is not visited, we can then visit node O. As node O is connected with node I. and node I is not visited, we then visit node 1. As node 1 is connected with node 5, and node 5 is visited, we can then visit node As node 5 is connected with node 6, and node is not visited, we can then visit node 6. As node 6 is connected with node 2, and node 2 is not visited, we can then visit node As node is connected with node 4, and node 4 not visited, we can then visit node 4. The path can he: 3, O, 1, 6, 2, 4.
In undirected graph. (i.) means that node i and node j are connected with an undirected edge. The nodes are numbered from 4, and the edges are: (1.3) (1,2) (4,3) (2.0) (0.4) (0.1)
No, there is no path in this graph that visits every node exactly once. This because node has degree mean- ing it is connected to two other nodes. In order visit every node exactly once, we would need to start and end at node 1. but once we leave node 1, cannot return to it without visit- ing another node twice. Therefore, it impossible find path that visits every node exactly once in this graph. x
Yes. We can start node O. As node 0 connected with node I, and node not visited, we can then visit node 1. As node is connected with node 3, and mode 3 is not visited, can then visit node 3, As node 3 is connected with node 4, and node visited, can then visit node 4. As node 4 is connected with node 2, and node then visit node 2. The path can be: 0,1,3,4,2, X
Q: Is there path this graph that visits every node exactly once? If yes, give the path. Note that in path, adjacent nodes must be connected with edges.
visited, can
There are 4 job applicunts numbered from (1 to and 2 jobs numbered from 0 to I. Each applicant is interested in some of the jobs. Each job can only accept one applicant and job upplicant can be appointed for only one job.
Applicant O is interested in job j.
Applicant O is interested in job 0.job
1.
Applicant is interested in job 0.
Applicant is interested in job 0.
Applicunt 2 is interested in job 0. job
Applicant 2 is interested in job 0, job
1.
Applicant 0 is interested in jub 1. Applicant interested job
Applicant 3 is interested in job job 1.
Applicant 3 is interested in job j.job
Applicant 0 is interested in job 0. Applicant 2 is interested in joh Applicant interested in job
We can make the following assign-
We can make the following assign- ments:
ments:
applicunt O: job 1
applicunt O: job 0
Applicant 3 is interested in job 0. Applicant interested in job
applicant 2: job 0
applicunt I:- (no job available)
applicant 3: job 1
applicant 2: job 1
Q: Find an assignment of jobs to applicants in such that the maximum number of applicants find the job they
applicants can find the job they are
applicunt 3: - (no job available)
interested in. X
applicants can find the job they are interested in.
interested in.
21

---

Table 15: Results of GPT-3.5-TURBO and GPT-4 on 19 cases (#17 to #19 example through the eight tasks. We omitted the COT in-context exemplars in the table.
Question
GPT-3,5-TURB0
GPT-4
There are 5 job applicants numbered from 0 to 4, and jobs numbered from 0 to S. Each applicant is interested in some of the johs. Fach job only accept applicant and job upplicant can be appointed for only one joh.
Applicant 0 is interested in job 2. job
Applicant 0 is interested in job 2. job 3. job 4. job 5. Applicant is inter- ested in joh 0. Applicant is inter- ested in job 3. Applicant is inter- Applicant
3. job 4. job 5. Applicant 1 is inter-
ested in joh 0. Applicant is inter-
ested in job 3. Applicant is inter- Applicant
inter- ested in job 0, job 2. job 4, job 5. We can make the following assignments: applicant 0: job 5 applicant 1: job
ested job
ested job
inter-
Applicant O is interested in job 3,
ested in job 0, job 2. 4, job 5. We can make the following assignments: applicant O: job 3 applicant 1: job
Applicant interested in job 5. Applicant 4 is inter-
ested in job4. 4.
Applicant 3 is interested in job 0. Applicant is interested in job
applicant 2: job 3 applicunt 3: job 0
applicant 4: job 4 3 applicants can find the job they are interested in. X
applicant job 2 applicants can
Applicant is interested in jub 0.
find job they are interested X
Applicant interested joh Applicant 0 is interested in job 4. Applicant is interested in joh 0. Applicant interested in job Applicant 2 is interested in job 3.
Q: Find assignment jobs to applicants such that the maximum number of applicunts find the job they are interested in.
an undirected graph, the nodes are numbered from 0 5. and every node has an embedding. (i.)) means that node and node j are connected with an undirected edge.
Layer I: node sum embeddings of node node 5. [0.1] [0.1] [0.2].
Layer 1:
node O: sum of embeddings of node
1, node 5, [0,1] + [0,1]= [0.2]. node I: of embeddings of node
node I: sum of emheddings of node
Embeddiings:
0. nude 4, node 5. [1.1] + [0.0] +
0. node 4, node 5, [1.1] + [0.0] +
node O: [1.1]
[0,1] [1,2].
[0,]] [1.2]
node I: [0.
node 2: sum of embeddings of node
node 2: sum of embeddings of node
node 2: [1.0]
4. [0.0]= [0.0].
4. [0000]= [0.0].
node 3: [1.1]
node 3: sum of embeddings of node
node 3: of embeddings of node
node 4: [0.0]
4. [0.00] =
[0.0].
4. [0.0] = [0.0].
node 5: [0.1]
node 4: sum of embeddings of node
node 4: sum of embeddings of node
The edges are: (5.0) (1.5) (4.3)
node node 3, [1,2] + [1.0]+ [0.0] [2.2]. node 5: sum of embeddings of node
1, 2, node 3, [0,1]+ [1.0] [1.1]
In a simple graph convolution layer, each node's em-
[2.2].
bedding updated by the sum of its neighbors' embed-
node S: sum of embeddings of node
dings.
D. node [0,2] + [1,2] = [1,4].
O, node 1, [1,1] + [0,1] [1.2].
Q: What's the embedding of each node after one layer of simple graph convolution layer?
So the answer is:
So the answer is:
node 0: [0.2]
node 0: [0,2]
node I: [1,2]
node 1: [1,2]
node 2: [0.0]
node 2: [0.0]
node 3: [0,0]
node 3: [0.0]
node 4: [2.2]
node 4: [2.2]
node 5: [1.44] X
node 5: [1.2] /
In undirected graph, the nodes are numbered from to 7, and every node has an embedding, (.j) means that node and node j are connected with undirected edge.
Layer I: node O: sum of embeddings of node 3, node 4, node 6, [1.1] + [1.]] [1.0]=[.2]]
Layer I: node 0: sum of embedding
of node 3, node 4, node 6, [1,1] + [1.1] [1,0] = [3.2]]
node 1: sum of embeddings of node
node 1: sum of embeddings of node
Embeddings::
4. [1.1]= [1.1].
5. node 4, [0.0] [1,1] [allj=[]] [1.1]_
node 0: [0.1]
node 2: sum of embeddings of node
node 2: sum of embeddings of node
node 1: [1.1]
3. node 5, node 6. [1.1] + [0.0] +
5, node 3, node 6. [0.0] + [1.1] +
node 2: [1.0]
[1.0] [2.1]
[1.0] = [2.1].
node 3: [1.1]
node 3: sum of embeddings of node
node 3: sum of embeddings of node node 2. node node 6, [0.1] [1.0] [0.0] +
node 4: [1.1]
0. node 2, node node 6, [0.
node 5: [0,0]
[1,1] [0.0] + [1.0] = [2,2].
node 6: [1.0]
node 4; sum of embeddings of node
node 4: sum of embeddings of node D node node [0.1] [1,1]
node 7: [1.0]
D. node node 5, [3.2] [1.1]
The edges are: (4.0) (6.0) (5.1) (1.4) (5.2) (2.3)
[0.0] = [4.3].
[0.0] = [1.2].
(2,6) (3.6) (5.4) (7.5)
node 5: sum of embeddings of node
node 5: sum of embeddings of node
In a simple graph convolation layer, each node's em-
2. node 3. node 4, mode 7. [2.1] +
1. node 2. node 3, mode 4, node 7,
hedding updated hy the sum its neighhors" embed-
[2.2] + [4.3] + [1.6].
[1,1] + [1.0] [1.1] [1.1] [1.0] [5.3].
dings.
node 6: sum of embeddings of mode
Q: What's the embedding of each node after one layer
D. node 2, node 3, [3.2] + [1,1] +
node 6: sum of emheddings of node
of simple graph convolution layer?
[1.0] [5.3]]
O. node 2, node node [0.1] [1.0] + [1.1] + [1.0] = [3.2].
node 7: sum of embeddings of node
5. 19,666] = 19.6].
node 7: sum embeddings of node
So the answer is:
5. [0.0]] = [0.0].
node 0: [3.2]
So the answer is:
node 1: [1.1]
node 0: [3.2]
node 2: [2.1]
node 1: [1.1]
node 3: [2.2]
node 2: [2.1]
node 4: [4.3]
node 3: [2.
node 5: [9.6]
node 4: [1,2]
node 6: [5.3]
node 5: [5.3]
node 7: [9.6] X
node 6: [3.2]
node 7: [0.0] X
22


Reviews:
[{"review_id": "auzgG9qISy", "reviewer": "Reviewer_7jfe", "summary": "This paper evaluates and studies the performance of state-of-the-art LLMs on graph reasoning-based tasks. For this, the authors construct a testbed of graph and structured reasoning tasks, comprising of 29K problems on 8 graph reasoning tasks such as topological sorting and max flow. Each task has three subsets based on problem difficulty and the default metric is exact match accuracy. The comprehensive evaluation conducted by the authors shows that LLMs perform well on graph reasoning tasks but advanced-prompting algorithms such as CoT, L2M, Self-Consistency based COT, etc. do not yield performance improvements on complex tasks. The authors also show that the LLMs evaluated (mainly text-davinci-003, but also others from OpenAI) are brittle to spurious correlations in the problem settings. Finally, the authors propose two very simple, domain-specific prompting methods, named Build-a-Graph and Algorithmic Prompting, which improves upon zero-shot performance of text-davcinci-003 on the tasks.", "questions": "1. From Appendix E, it appears that GPT-4 is considerably more capable than GPT-3.4-Turbo. A number of other works have found GPT-4 to show considerably higher performance, thereby hitting the thresholds of practical utility. Can you comment on any of this behavior wrt the graph reasoning tasks?\n2. I am surprised that zero-shot is the best performing method in Figure 2 (right, max-flow task). Similarly, I am finding it hard to understand why CoT underperforms zero-shot. How much time was spent iterating on CoT? Can you comment of this exact trend holding on for GPT-4 as well?\n3. To arrive at the Build-a-Graph and Algorithmic prompting methods, how many negative prompts did you iterate through? It is clear that domain specific contextual knowledge is being leveraged by LLMs to solve this task, but I am interested in the meta-question of how did you arrive these methods?", "limitations": "Yes, the authors have adequately addressed the limitations.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. Comprehensive and Interesting: I really like this work. This is primarily an evaluation paper, and the authors do a great job of conducting a systematic and comprehensive study of LLM performance on graph reasoning tasks. \n2. A Useful Resource for the Community: A number of reasoning problems could be reduced to implicit reasoning over graphs and the proposed benchmark, NLGraph will help the research community evaluate LLMs on such reasoning problems.", "weaknesses": "1. Lack of Systematic Comparisons between LLMs: Although I am empathetic to the plight of researchers conducting research on black-box models, only through an API, I feel the work would have been more valuable had the researchers also focused on a comparison between 3 generations of LLMs: GPT-3, GPT-3.5 and GPT-4. It would have enumerated a few things: the impact of instruction finetuning since the chat models are more aggressively instruction finetuned, the gains in performance across these models and the impact of advanced prompting with scale/model generation. The qualitative analysis in Appendix E on 19 problems is insufficient in ascertaining any of the performance jumps.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive feedback and helpful suggestions!\n\n> Lack of Systematic Comparisons between LLMs\n\nWe believe it is interesting to see how more recent LMs (e.g., GPT-4) perform on the NLGraph benchmark. However, due to the budget we had and as we will make the NLGraph benchmark publicly available, we leave it for future work. \n\n> From Appendix E, it appears that GPT-4 is considerably more capable than GPT-3.4-Turbo. A number of other works have found GPT-4 to show considerably higher performance, thereby hitting the thresholds of practical utility. Can you comment on any of this behavior wrt the graph reasoning tasks?\n\nAccording to the experiments we did, GPT-4 is indeed more capable than GPT-3.5-turbo. However, it still fails in some easy cases such as case 3 in Table 11, which humans can easily solve, and in many difficult cases, indicating it only possesses preliminary graph reasoning abilities.\n\n> I am surprised that zero-shot is the best performing method in Figure 2 (right, max-flow task). Similarly, I am finding it hard to understand why CoT underperforms zero-shot. How much time was spent iterating on CoT? Can you comment of this exact trend holding on for GPT-4 as well?\n\nWe have tried several versions of CoT on a small subset of the problems and finally choose the form that performs the best.\n\nProblems such as max-flow are rather difficult, even for humans. A human struggles to solve a max-flow task with about ten nodes, even when some exemplars are given.  Due to the difficulty, LLMs fail to learn the correct way to generate intermediate steps or learn from in-context exemplars.The extra text in CoT might be hard for the model to grasp and does not provide a positive impact. We believe the trend still holds on for GPT-4, though it needs experiments to finally prove this.\n\n> To arrive at the Build-a-Graph and Algorithmic prompting methods, how many negative prompts did you iterate through? It is clear that domain specific contextual knowledge is being leveraged by LLMs to solve this task, but I am interested in the meta-question of how did you arrive these methods?\n\nWe first come up with a set of prompting methods that intuitively help solve graph reasoning problems, and then test them.  Build-a-Graph and Algorithmic prompting methods work the best. Other methods such as asking LMs to answer some simple questions about the graph property before answering the true question do not work well. We also try variants of our prompting methods and provide the results in Table 7 in the appendix.\n"}, {"review_id": "1lgEKudA2B", "reviewer": "Reviewer_moU8", "summary": "This work tried to answer the question, \"Are LLMs capable of mapping textual descriptions of graphs and structures to grounded conceptual spaces and solving graph algorithm problems explicitly with natural language?\" The answer to this question has profound implications for large language model applications with implicit graphs and structures, the reasoning ability of LLMs in advanced and graph-based settings, and more. This paper proposes the Natural Language Graph (NLGraph) benchmark, a comprehensive testbed of graphs and structured reasoning designed for language models and in natural language. Extensive experiments on the NLGraph benchmark demonstrate that:\n1. LLMs do possess preliminary graph reasoning abilities.\n2. The benefit of advanced prompting methods diminishes with complex problems.\n3. Learning from examples did not happen on complex graph reasoning problems.\n4. LLMs are (un)surprisingly brittle to spurious correlations in problem settings.\n\nTo improve large language models as better graph reasoners, this work proposes two instruction-based prompting approaches to better elicit the graph reasoning abilities of large language models. Build-a-Graph prompting encourages LLMs to map the textual descriptions of graphs and structures to grounded conceptual spaces before tackling the specific problem through a one-sentence instruction, while Algorithmic prompting instructs LLMs to revisit the algorithmic steps for a given task before learning from in-context exemplars. \n\n\n", "questions": "None", "limitations": "None", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The motivation of this work is to answer the question, \"Are LLMs capable of mapping textual descriptions of graphs and structures to grounded conceptual spaces and solving graph algorithm problems explicitly with natural language?\" is very interesting.\n\n2. The extensive experiments are comprehensive. Experiments demonstrate that build-a-graph and algorithmic prompting successfully empower LLMs to better tackle graph reasoning problems, resulting in 3.07% to 16.85% performance gains across multiple tasks.\n\n3. This paper provides the Natural Language Graph (NLGraph) benchmark, a comprehensive testbed of graphs and structured reasoning designed for language models and in natural language.\n\n\n", "weaknesses": "This work is mainly on testing different prompt engineering strategies and in-context learning results. If we can include more LLM fine-tuning results, it will be of great help.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and positive feedback! \n\n> If we can include more LLM fine-tuning results, it will be of great help.\n\nIt would be valuable and interesting to see LLM fine-tuning results, but it is too expensive to fine-tune LLMs such as GPT-3. As we will make the NLGraph benchmark publicly available, we leave it for future work. "}, {"review_id": "alWbjdXDEs", "reviewer": "Reviewer_E2y1", "summary": "This paper investigates whether large language models (LLMs) are able to solve graph algorithm problems in natural language. A benchmark NLGraph contains 29,370 problems, covering 8 graph reasoning tasks with varying complexity from simple tasks such as connectivity, cycle, and shortest path to more complex problems such as topological sort, maximum flow, bipartite graph matching, Hamilton path, and simulating graph neural networks. Various prompting techniques have been applied to evaluate the capabilities of LLMs for performing complex reasoning on graphs. Several valuable insights are provided based on the experimental results and analyses. Two prompting techniques Build-a-Graph and Algorithmic Prompting are further introduced for enhancing graph reasoning.", "questions": "See above.", "limitations": "The authors adequately addressed the limitations in the Appendix.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. The proposed NLGraph benchmark is comprehensive, covering intuitively simple to more sophisticated tasks. Also, as the benchmark is synthetic, answers are unlikely to appear in the pretraining corpus of LLMs, making it a more robust benchmark for evaluating complex reasoning with LLMs. I think it would be a challenging and valuable testbed for evaluating the graph reasoning abilities of large language models.\n2. Extensive experiments and analyses are conducted on the proposed benchmark. Specifically, results of text-davinci-003 model with various prompting techniques (e.g. Chain-of-Thoughts, Least-to-Most, Self-Consistency) are reported.  Such results and analyses help the research community to better understand the capabilities/behavior of LLMs for graph reasoning or even complex reasoning. The four key phenomenons summarized in the paper are quite counter-intuitive and thought-provoking.\n3. The paper is clear and well-organized.\n", "weaknesses": "I only have several minor concerns/questions about this paper as follows:\n1. Using a programming style of prompting techniques (e.g. PAL[1], PoT[2]) for solving these graph reasoning tasks is more intuitive. It could potentially address the problem of generating too many tokens of code-davinci-002.  \n2. Except for the results of text-davinici-003, only part of the results of code-davinci-002 are reported (i.e. cycle, shortest path, and hamilton path).  For GPT-3.5-turbo and GPT4, only 19 tasks across 8 tasks are provided. I am not sure the four key findings listed are universal for the LLMs. It would be interesting to know the overall performance of other LLMs on the benchmark. It would shed light on this problem.  \n3. It seems to me that including the Graph Neural Networks (GNNs) task is not well-motivated. Why do we want the LLM to perform graph convolution on a two-dimension node embedding? We already have an efficient way to calculate it even for node embeddings that have hundreds or thousands of dimensions. If the LLM can use tools (e.g. calculator, python interpreter), why do we want it to perform large number calculations itself? Similarly, LLMs can write the code of different GNNs to perform message propagation.\n\n\nReferences:\n\n[1]PAL: Program-aided Language Models. \n\n[2]Program of Thoughts Prompting. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful and constructive feedback! \n\n> Using a programming style of prompting techniques (e.g. PAL[1], PoT[2]) for solving these graph reasoning tasks is more intuitive. It could potentially address the problem of generating too many tokens of code-davinci-002.\n\nYes, this is a very good point! Though we have considered a programming style of prompting techniques, our concern is that LLMs are trained on a large amount of text including codes for solving these graph problems, thus they could easily recite the codes to solve the problems. The evaluation results might not truly reflect reasoning ability. Anyway, this can be a good follow-up work based on the released dataset in our work.\n\n> Except for the results of text-davinici-003, only part of the results of code-davinci-002 are reported (i.e. cycle, shortest path, and hamilton path). For GPT-3.5-turbo and GPT4, only 19 tasks across 8 tasks are provided. I am not sure the four key findings listed are universal for the LLMs. It would be interesting to know the overall performance of other LLMs on the benchmark. It would shed light on this problem.\n\nIt will certainly be interesting to see how more recent LLMs (e.g., GPT-4) perform on the NLGraph benchmark. However, due to monetary costs and as we will make the NLGraph benchmark publicly available, we leave it for future work. \n\n> It seems to me that including the Graph Neural Networks (GNNs) task is not well-motivated. Why do we want the LLM to perform graph convolution on a two-dimension node embedding? We already have an efficient way to calculate it even for node embeddings that have hundreds or thousands of dimensions. If the LLM can use tools (e.g. calculator, python interpreter), why do we want it to perform large number calculations itself? Similarly, LLMs can write the code of different GNNs to perform message propagation.\n\nThe main purpose of the GNN task is to evaluate LLMs' graph reasoning (propagation of information) abilities instead of utilizing LLMs to perform GNN operations in real use. As the GNN task requires LMs to consider relations in the graph and perform arithmetic operations simultaneously, we consider it as a good task for evaluating graph reasoning abilities."}, {"review_id": "vExkDkhuaV", "reviewer": "Reviewer_U4cj", "summary": "The paper curates a benchmark dataset called NLGraph that contains 8 types of graph reasoning problems. Given that various previous works have used LLMs to solve real-world tasks that implicitly require some form of simple graph reasoning, this dataset aims to isolate and analyze the ability of LLMs to graph reasoning problems. The paper tests various existing prompting strategies and also proposes two new strategies specifically useful for solving graph reasoning problems. The newly proposed strategies are evaluated on the proposed NLGraph dataset and are shown to improve the reasoning performance.", "questions": "\n1. Line 160 states how the easier tasks were further subdivided into easy, medium, and hard. How are the more algorithmically challenging tasks categorized (Line 162)? Does it make sense to use the number of valid solutions for categorizing difficulty?\n2. How are the exemplars selected? How does the performance vary with the selection? Does is show high or low variance?\n3. In the zero-shot case, when there is not way to ensure the proper output formatting, how do you perform automated evaluation? ", "limitations": "The limitations discussed in the appendix are satisfactory. However, the authors should provide a reference to this discussion in the main paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "### originality\nThe paper is the first to curate a dataset aimed at isolating the graph reasoning abilities of LLMs in the abstract. This is complementary to all the works that use LLMs to solve tasks that implicitly require graph reasoning, and thus can provide valuable insights that can be useful in real applications.\n### quality\n1. The discussion about the limitations of the work (in the appendix) clearly states the scope of applicability of their finding.\n2. The experiments are well-designed, especially the ones demonstrating the brittleness of LLMs.\n### clarity:\nThe paper is well-organized, clearly written, and easy to follow.\n### significance\nThe curated dataset and the experimental setup proposed in the paper can be a good starting point for further exploration of the graph reasoning abilities of LLMs, making this work useful for the community.", "weaknesses": "### quality: \n1. The performance of the model depends heavily on how the prompts are constructed. While Figure 1 shows the instructions used in the prompts clearly, to ensure reproducibility, the complete prompts for more complex strategies like COT should be provided. \n### Significance: \n1. The motivation behind choosing the eight specific graph reasoning tasks is lacking. The ultimate goal of performing graph reasoning using LLMs is to use it to solve simple real-world tasks where graph reasoning is required. Given this motivation, the authors should provide additional justification for picking the reasoning tasks used in the paper.\n2. For the findings to apply to real-world data, the proposed prompting strategies should be tested with graphs that have real-world semantics associated with notes and edges. For example, representing nodes as numbers might allow the model to easily decouple the inherent meaning of the nodes from the meaning in the context of the given graph. This might not be an easy task if the nodes were a set of words, phrases, or actions. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for acknowledging our novel contributions as well as raising valuable questions.\n\n> The performance of the model depends heavily on how the prompts are constructed. While Figure 1 shows the instructions used in the prompts clearly, to ensure reproducibility, the complete prompts for more complex strategies like COT should be provided.\n\nWe will include all prompts in the appendix of the final version. Here we give a CoT example of the topological sort task:\n\nIn a directed graph with 5 nodes numbered from 0 to 4:\n\nnode 0 should be visited before node 4\n\nnode 0 should be visited before node 1\n\nnode 2 should be visited before node 1\n\nnode 3 should be visited before node 2\n\nQ: Can all the nodes be visited? Give the solution.\n\nA: Since no nodes are required to be visited before node 0 and node 3, node 0 and node 3 can be visited first.\nSince visiting node 4 requires visiting node 0 first, after node 0 is visited, node 4 can be visited.\n\nSince visiting node 2 requires visiting node 3 first, after node 3 is visited, node 2 can be visited.\n\nSince visiting node 1 requires visiting node 0, node 2 first, after node 0 and node 2 are visited, node 1 can be visited. So the solution is: 0,3,4,2,1.\n\n> The motivation behind choosing the eight specific graph reasoning tasks is lacking. The ultimate goal of performing graph reasoning using LLMs is to use it to solve simple real-world tasks where graph reasoning is required. Given this motivation, the authors should provide additional justification for picking the reasoning tasks used in the paper.\n\nWe discussed NLP tasks and graph tasks alignment in section A in the appendix. We will incorporate more of it in the final version given the additional page.\n\n> For the findings to apply to real-world data, the proposed prompting strategies should be tested with graphs that have real-world semantics associated with notes and edges. For example, representing nodes as numbers might allow the model to easily decouple the inherent meaning of the nodes from the meaning in the context of the given graph. This might not be an easy task if the nodes were a set of words, phrases, or actions. \n\nThanks for your suggestion. It  is certainly a good point while our work is an initial study on this topic. Nevertheless, we provide the results of changing “node”s to “city”s, “edge”s to “roads”, and “weight”s to “distance”s in the shortest path task in Table 9.\n\n> Line 160 states how the easier tasks were further subdivided into easy, medium, and hard. How are the more algorithmically challenging tasks categorized (Line 162)? Does it make sense to use the number of valid solutions for categorizing difficulty?\n\nMore algorithmically challenging tasks are divided into easy and hard subsets.\n\n> How are the exemplars selected? How does the performance vary with the selection? Does is show high or low variance?\n\nWe selected exemplars according to the empirical performances on each task. The specific process is similar to the experiments in Figure 7 in the appendix. The performance varies when the exemplars are selected from different difficulties. Specifically, the performance drops when the exemplar difficulty increases.\n\n> In the zero-shot case, when there is not way to ensure the proper output formatting, how do you perform automated evaluation?\n\nThough zero-shot setting does not ensure that all the output is in the same format, there are a limited number of patterns in the LLM response. We use these patterns to automatedly evaluate. For instance, in the cycle task, “there is no cycle”, “there is a cycle” and “which creates a cycle” appear in all the output, while no output contains two or more of the three patterns, so we just match the phrases in the output to get the results. We will publicly release the LLM responses and our code to make automated evaluations upon acceptance.\n\n> The limitations discussed in the appendix are satisfactory. However, the authors should provide a reference to this discussion in the main paper.\n\nThank you for your suggestion. We have added a reference to the limitation discussion in the revised paper."}, {"review_id": "bdkd8X8Mtq", "reviewer": "Reviewer_EhYM", "summary": "The applications of Large Language Models (LLMs) have been extended beyond natural language, covering more complex tasks that might have an implicit graph structure, such as planning for robots. This work introduces a benchmark named Natural Language Graph (NLGraph) to examine the explicit graph reasoning of advanced LLMs.\n\nNLGraph contains eight basic graph reasoning task, varying from easy (connectivity, cycle, topological, ...) to hard (maximum flow, Hamilton path, ...). Based on NLGraph, this work has several findings:\n\n* Current LLM (text-davinci-003) shows preliminary graph reasoning abilities. It achieves much better results than random guess in the easy task, for example, connectivity and cycle.\n* Advanced prompting fails in more complex tasks.\n* LLM are not robust to spurious correlation.\n\nThey also propose two simple prompts to enhance the LLM in easy graph reasoning task.", "questions": "What is the correspondence between, train, main, and test splits provided in the supplementary material and the standard and extended set in the text?", "limitations": "The authors discuss limitations comprehensively in the supplementary material, partly as future work.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "* This paper is well-motivated and finely written. As large language models (LLMs) grow increasingly proficient, we are in need of novel, challenging benchmarks to thoroughly assess their capabilities. The graph structure exemplifies data structures that are prevalent in real life.\n* This benchmark is fairly comprehensive, encompassing the eight fundamental types of graph problems. It also forms subsets of varying difficulty levels by manipulating factors such as the number of nodes and density.\n* The findings are both intriguing and illuminating. For instance, the revelation that current advanced prompt strategies cannot generalize to complex tasks could potentially motivate research into exploring innovative techniques.", "weaknesses": "The evaluations are only conducted on text-davinci-003, therefore, some conclusions may be limited to this model.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and positive feedback!\n\n> The evaluations are only conducted on text-davinci-003, therefore, some conclusions may be limited to this model.\n\nWhile we evaluate text-davinci-003 on the whole dataset, we also provide the results of code-davinci-002 on several tasks in the NLGraph benchmark, which show similar trends. Moreover, we give qualitative analysis results of GPT-3.5-turbo and GPT-4 in the appendix. As we will make the NLGraph benchmark publicly available, we hope future work will further explore other LMs on the NLGraph benchmark.\n\n> What is the correspondence between, train, main, and test splits provided in the supplementary material and the standard and extended set in the text?\n\nMain splits are split into train splits and test splits. The supplementary material only contains the standard set in the text, which we use to run all the experiments. We will make the extended set publicly available after the anonymity period."}]

Author rebuttal:
We would like to express our sincere gratitude to the reviewers for providing us with valuable feedback. These constructive comments have been instrumental in improving the quality of our work. We are glad that our efforts have been well-received by the reviewers, and we are confident that their insightful feedback will further enhance the impact of our paper. With their guidance, we have outlined clear plans to incorporate their suggestions in the camera-ready version of the paper, and we are excited to present an even stronger final version.

Meta-review: This paper presents a comprehensive evaluation of Large Language Models (LLMs) on graph reasoning tasks. The authors construct a testbed of graph and structured reasoning tasks, NLGraph (29,370 problems, covering eight graph reasoning tasks), and evaluate the performance of LLMs on these tasks. The reviewers commend the authors for their systematic and comprehensive study, and agree that the proposed benchmark will be a valuable resource for the research community. The reviewers also appreciate the authors' efforts in proposing two simple, domain-specific prompting methods, Build-a-Graph and Algorithmic Prompting, which improve upon zero-shot performance of LLMs on the tasks.

However, the reviewers also pointed out some areas for improvement. One reviewer suggested that the work would have been more valuable if the authors had also focused on a comparison between different generations of LLMs. Also, one reviewer questioned the inclusion of the Graph Neural Networks (GNNs) task and suggested using a programming style of prompting techniques for solving these graph reasoning tasks.

Despite these minor concerns, the reviewers agree that the paper is technically strong, with novel ideas on at least one area.
Decision: Accept (spotlight)