Can Language Models Solve Graph Problems in Natural Language?

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. NLGraph 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: * 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. * Advanced prompting fails in more complex tasks. * LLM are not robust to spurious correlation. They also propose two simple prompts to enhance the LLM in easy graph reasoning task.

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. * 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. * 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.

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?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The authors discuss limitations comprehensively in the supplementary material, partly as future work.

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.

Strengths

### originality The 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. ### quality 1. The discussion about the limitations of the work (in the appendix) clearly states the scope of applicability of their finding. 2. The experiments are well-designed, especially the ones demonstrating the brittleness of LLMs. ### clarity: The paper is well-organized, clearly written, and easy to follow. ### significance The 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: 1. 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. ### Significance: 1. 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. 2. 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.

Questions

1. 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? 2. How are the exemplars selected? How does the performance vary with the selection? Does is show high or low variance? 3. In the zero-shot case, when there is not way to ensure the proper output formatting, how do you perform automated evaluation?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The limitations discussed in the appendix are satisfactory. However, the authors should provide a reference to this discussion in the main paper.

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.

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. 2. 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. 3. The paper is clear and well-organized.

Weaknesses

I only have several minor concerns/questions about this paper as follows: 1. 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. 2. 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. 3. 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. References: [1]PAL: Program-aided Language Models. [2]Program of Thoughts Prompting.

Questions

See above.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

4 excellent

Limitations

The authors adequately addressed the limitations in the Appendix.

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: 1. LLMs do possess preliminary graph reasoning abilities. 2. The benefit of advanced prompting methods diminishes with complex problems. 3. Learning from examples did not happen on complex graph reasoning problems. 4. LLMs are (un)surprisingly brittle to spurious correlations in problem settings. To 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.

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. 2. 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. 3. 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.

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.

Questions

None

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

None

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.

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. 2. 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.

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? 2. 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? 3. 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?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

Yes, the authors have adequately addressed the limitations.

Thank you for the clarifications

Thank you for answering my questions and for providing clarifications. I have no further questions.