Incremental Contribution

We appreciate your points on the potentially incremental contributions of the paper and questioning the need for LLMs to modify graphs. Regarding your first point, the transition from static to dynamic graph algorithms is not a minor incremental step but represents a fundamental shift in approach. In algorithms research, dynamic graph problems constitute an entirely separate field due to their complexity and distinct challenges [1], demonstrating that converting a static problem into a dynamic one is not a minor incremental step. In fact, arguably the bigger worry with our paper is that we are only scratching the surface of exploring LLMs’ abilities of dynamic graph understanding, not in its scope being too incremental.

Regarding your second point on whether or not we need LLMs to modify graphs, you’re of course correct in that code libraries provide efficient and reliable implementations for many graph tasks, let alone modification tasks, in a few lines of code. However, there is already a growing literature that looks at LLMs' intrinsic reasoning abilities on graphs (e.g., [2] and [3]), and as the literature explains, they are not advocating for replacing these established tools with large language models (LLMs) for practical graph tasks. Instead, they aim to evaluate LLMs’ reasoning capabilities within the context of graph tasks as a way to better understand and quantify their strengths and limitations in multi-step reasoning scenarios.

We recognize a critical gap in the existing literature, where prior work has largely focused on basic static graph properties. Therefore, we add to this literature in a qualitatively new way by introducing the concept of graph modification as a more dynamic, multi-step reasoning challenge. This approach aligns with the broader goal of assessing and advancing LLMs’ ability to handle evolving, structured data representations, which is critical for dynamic domains such as social networks, where connections are frequently added or removed, and evolving knowledge bases, which must accommodate new or outdated information.

More Interesting Graph Modification Tasks

We appreciate your suggestion of exploring more advanced graph modification tasks involving target property optimization (e.g., minimizing changes to disconnect a graph or achieving a specific number of connected components). While such tasks indeed represent intriguing extensions of graph modification, our focus in this work is to rigorously assess fundamental and interpretable capabilities in graph reasoning and dynamic graph manipulation. These foundational tasks are critical prerequisites for enabling LLMs to handle more complex scenarios such as target property optimization. We cannot reasonably evaluate more difficult scenarios when LLMs struggle to perform basic and atomic graph manipulations. Extending our methods to property-specific graph modifications, as suggested, is an exciting future direction, but it falls outside the scope of this work, which aims to establish a baseline for understanding and improving LLMs' abilities to perform graph modifications through foundational tasks.

More Important Information Needed

We have added Section 4.3 in the new version of our paper, which details the total number of questions in GraphModQA (468,750 ), and how this number is derived.

In Sections 4.1 and 5.2, we briefly mention how we sample the size and edge density of each graph. For readability, we consolidate this information, as well as other implementation details, in Section A.2 in the Appendix, which also includes our decoding temperature of zero, our only model hyper-parameter.

Regarding the forms of the prompts we use, we have added Section A.9 which includes Figures 33 to 38. These figures illustrate examples of input prompts and model outputs corresponding to zero-shot prompting, CoT prompting, and MAP prompting.

[1] Eppstein, David, Zvi Galil, and Giuseppe F. Italiano. "Dynamic graph algorithms." Algorithms and theory of computation handbook 1 (1999): 9-1.

[2] Fatemi, Bahare, Jonathan Halcrow, and Bryan Perozzi. "Talk like a graph: Encoding graphs for large language models." arXiv preprint arXiv:2310.04560 (2023).

[3] Wang, Heng, et al. "Can language models solve graph problems in natural language?." Advances in Neural Information Processing Systems 36 (2024).

The motivation of this dataset is mainly from the dynamic graphs. However, dynamic graphs in the real world have various evolution patterns and rules rather than randomly adding or deleting edges and nodes. It's unclear whether the modification queries of the proposed datasets are related to some real-world graph evolution properties. Moreover, I believe "dynamic graph reasoning" is more likely to predict the future graph structure rather than modify graph structure given human instructions. So the relationship between "graph modification" and "dynamic graph reasoning" is unconvincing to me. I will keep my score.

Dear reviewer 2ZNt,

We appreciate the response. It seems that there is some disagreement as to the definition of “dynamic graph reasoning”. We believe that we can clear this up by first defining what prior work defines as (static) “graph reasoning”, and then we can use this definition to define “dynamic graph reasoning”. The below explanation has been clarified in the newest version of the paper.

Firstly, we would like to mention that prior work, namely [1] and [2], pose the question of if LLMs can reason on static graphs. The authors of these papers define "reasoning" in this sense as the ability of these LLMs to perform static graph algorithms (e.g connectivity, shortest path, etc.). A static graph algorithm takes in a static graph and outputs some property of the input graph. Therefore, the authors of [1] and [2] test the "graph reasoning" abilities of LLMs by evaluating if they are able to perform these static graph algorithms.

From the talk we previously linked to above [3] and from extensive literature on the topic [4], a dynamic graph algorithm is composed of two parts:

1. “[A] data structure that maintains information about a graph while it is modified through local operations such as edge or vertex insertions or deletions.”
2. The ability to efficiently return properties of the updated graphs without recalculating from scratch after each modification.

In our paper, we pose the question of if LLMs can reason on dynamic graphs. In order for an LLM to be able to reason on dynamic graphs, they must be able to do both of the above (accurately maintaining a data structure that undergoes a series of modifications, and efficiently return dynamic properties by leveraging precomputed information that is maintained during updates). As we show in our paper, LLMs struggle greatly on the first point, since they struggle with accurately maintaining one of the most commonly used data structures for representing graphs, the adjacency matrix, as the structure undergoes several key atomic modification operations. Therefore, graph modifications are inextricably linked with the ability to perform dynamic graph algorithms, and by staying consistent with definitions offered by prior work, the ability to perform dynamic graph algorithms can be similarly defined as "dynamic graph reasoning”.

Understanding if LLMs can predict future graph structure and understand various evolutionary patterns found in dynamic graphs is certainly an interesting area of research, but we consider these problems to be out of scope, as we instead focus on the ability of LLMs to perform local operations.

We hope that this clarifies the relationship between “graph modification” and “dynamic graph reasoning”.

[1] Fatemi, Bahare, Jonathan Halcrow, and Bryan Perozzi. "Talk like a graph: Encoding graphs for large language models." arXiv preprint arXiv:2310.04560 (2023).

[2] Wang, Heng, et al. "Can language models solve graph problems in natural language?." Advances in Neural Information Processing Systems 36 (2024).

[3] https://simons.berkeley.edu/news/dynamic-graph-algorithms-what-we-know-what-we-dont

[4] Eppstein, David, Zvi Galil, and Giuseppe F. Italiano. "Dynamic graph algorithms." Algorithms and theory of computation handbook 1 (1999): 9-1.

Organization Issues

We thank the reviewer with pointing out issues with the first paper's organization. As a result, in the new version of the paper, we include Section A.9 that illustrates the form of questions involving zero shot prompting, CoT prompting, and MAP prompting respectively, as well as real model outputs to these prompts. In addition, we include Algorithm 6, which details how the dataset was constructed.

Lack of Experimental Analysis

We’ve added further analysis to Section A.6 in the Appendix, where we analyze the performance of all models across all final questions and encoding types.

For further analysis, we have also added Section A.7, where we perform an additional ablation study that investigates how varying edge density and graph size impact model performance. Furthermore, we added Section A.8, which details the different errors all benchmarks made on the Add Edge, Remove Edge, Add Node, and Remove Node modifications on the Print Graph task using the Adjacency Matrix encoder (our toughest task).

Lack of CoT Understanding

Regarding your point on our lack of understanding of CoT prompting, we mentioned previously in Section 4.2.3 that CoT prompting involves “including a list of examples that each demonstrate the reasoning process step-by-step”. Additionally, in Section 5.3.1 we previously mentioned that we provide “examples of detailed reasoning in the prompt”, similarly to how CoT prompting is defined in [1] who first introduced and defined CoT prompting as few-shot prompting that consists of triples: <input, chain of thought, output>. In addition, Figure 37 in Section A.9 in our new paper illustrates how we use CoT prompting.

Real-world Applications

Thank you for highlighting this key point regarding the relationship between modifying graphs and real-world applications. In the fourth paragraph of the introduction, we previously describe how graph modifications play a central role in dynamic domains such as social networks, where connections are frequently added or removed, and evolving knowledge bases, which must accommodate new or outdated information.

Furthermore, structured data in tables is prevalent across applications like recommendation systems, supply chain management, and relational databases. Graphs are the simplest instantiation of such structured data, with the adjacency matrix effectively functioning as a 2D table of 0s and 1s indicating binary relationships. Therefore, modifying and reasoning on tabular structured data is at least as hard as modifying and reasoning on a graph, making graphs a natural testbed for evaluating how LLMs handle and update structured information.

By focusing on graph modifications, our work provides a benchmark to assess and improve LLMs’ capabilities for tasks that demand precise manipulation and reasoning on evolving data structures, which are critical for real-world applications.

We agree that in this paper, we show that current LLMs have achieved high performance on both the Incident List and Coauthorship encodings, and we would consider graph reasoning problems that use these encodings to be “solved” problems. However, LLMs struggle significantly on the Adjacency Matrix, especially during node removal operations. The Adjacency Matrix encoding requires the LLM to handle dense numerical representations that are both explicit and inherently structured, unlike the more descriptive and naturalistic formats of the Incident List or Coauthorship encodings. In these latter encodings, relationships are expressed through natural language, allowing the model to rely on linguistic patterns and explicit textual cues to infer and modify relationships. By contrast, the adjacency matrix demands that the model infer connections through numerical indexing alone.

[1] Wei, Jason, et al. "Chain-of-thought prompting elicits reasoning in large language models." Advances in neural information processing systems 35 (2022): 24824-24837.

Dear Reviewer p6sQ,

In your original comment, you mentioned that "illustrat[ing] how the modified graphs are important for real-world applications or have a connection with other tasks...needs further experiments to enhance". Below, we will show how graph modification is important for real-world applications, and why further experiments are not needed to illustrate this relationship. The below explanation has been clarified in the newest version of the paper.

Firstly, we would like to mention that prior work, namely [1] and [2], pose the question of if LLMs can reason on static graphs. The authors of these papers define "reasoning" in this sense as the ability of these LLMs to perform static graph algorithms (e.g connectivity, shortest path, etc.). A static graph algorithm takes in a static graph and outputs some property of the input graph. Therefore, the authors of [1] and [2] test the "graph reasoning" abilities of LLMs by evaluating if they are able to perform these static graph algorithms.

Please refer to this Simons Institute talk by Monika Henzinger [3] that defines a “dynamic graph algorithm”. These algorithms are connected to a myriad of real-world applications, including:

• Social networks: Efficiently updating user connections in platforms like Twitter or Facebook as edges (relationships) and nodes (users) are added or removed.
• Telecommunication networks: Rapidly reconfiguring connections to maintain communication paths when nodes or links fail.
• Dynamic routing in transportation: Managing and updating routes in real-time based on traffic conditions, road closures, or new infrastructure.

From the talk and from extensive literature on the topic, a dynamic graph algorithm is composed of two parts:

1. “[A] data structure that maintains information about a graph while it is modified through local operations such as edge or vertex insertions or deletions.”
2. The ability to efficiently return properties of the updated graphs without recalculating from scratch after each modification.

In our paper, we pose the question of if LLMs can reason on dynamic graphs. In order for an LLM to be able to reason on dynamic graphs, they must be able to do both of the above (accurately maintaining a data structure that undergoes a series of modifications, and efficiently return dynamic properties). As we show in our paper, LLMs struggle greatly on the first point, since they struggle with accurately maintaining one of the most commonly used data structures for representing graphs, the adjacency matrix, as the structure undergoes several key atomic modification operations. Therefore, graph modifications are inextricably linked with the ability to perform dynamic graph algorithms, which are used in a myriad of real world applications, firmly establishing the relationship between graph modifications and real-world applications as well as connections with other tasks.

At this point of the review process, we would appreciate actionable and constructive feedback. Reviewer p6sQ, could you clarify the following question:

"Given how we have already "illustrate[d] how the modified graphs are important for real-world applications or have a connection with other tasks" using the definition of dynamic graph algorithms, what exact additional experiments would you like us to perform, and how would these experiments add further clarity on the relationship between graph modification and real-world applications?"

[1] Fatemi, Bahare, Jonathan Halcrow, and Bryan Perozzi. "Talk like a graph: Encoding graphs for large language models." arXiv preprint arXiv:2310.04560 (2023).

[2] Wang, Heng, et al. "Can language models solve graph problems in natural language?." Advances in Neural Information Processing Systems 36 (2024).

[3] https://simons.berkeley.edu/news/dynamic-graph-algorithms-what-we-know-what-we-dont

Lack of Evidence on Graph Primitive Performance

Regarding your point on the lack of empirical evidence on the performance across model generations on basic graph primitives, Table 1 in [1], the paper that we cite as inspiring our work, shows the weak performance on older models (particularly those from the PaLM family) on basic graph primitives (e.g Node Count, Node Degree, etc.). In addition, in Tables 1 and 2 in the Appendix of our paper, we show that current SOTA methods clearly outperform older models on basic graph primitives. In Table 2, we evaluate Palm 2-L on the adjacency matrix encoding, and show that SOTA LLMs strongly outperform Palm 2-L on basic graph primitives on this encoding.

Motivation of GraphModQA

In the introduction, particularly in the fourth paragraph, we justify GraphModQA as a benchmark by highlighting its unique requirements compared to GraphQA. GraphModQA tasks involve iterative graph modifications, such as adding or removing nodes or edges, followed by reasoning about the resulting graph structure. Successfully solving these tasks demands precise state tracking and manipulation of an evolving internal graph representation. Unlike GraphQA, where models reason over static graphs with fixed structures, GraphModQA introduces a compounding challenge: each modification dynamically alters the graph, requiring the model to not only update its representation accurately but also maintain consistency across a sequence of interdependent operations, creating a more complex reasoning landscape. Furthermore, GraphModQA combines the inherent difficulty of dynamic state maintenance with high-level reasoning about the final modified graph, making it significantly more rigorous in evaluating a model's capability to handle evolving graph structures. We have made additions to this paragraph in our new version of the paper in order to make these points clearer.

Arbitrariness of Modification Types

Regarding your point on the justification of the modification types, please firstly refer to the following paper [2]. Here is an excerpt from this paper that justifies our modification types:

“(static) graphs and networks involve the following entities: V (a set of nodes), E (a set of edges), f (map vertices to numbers), and g (map edges to numbers). A dynamic graph is obtained when any of these four entities changes over time. Thus, there are four basic kinds of dynamic graphs.

• In a node-dynamic graph or digraph, the set V varies with time. Thus, some nodes may be added or removed. When nodes are removed, the edges (or arcs) incident with them are also eliminated.

• In an edge-dynamic (or arc-dynamic) graph or digraph, the set E varies with time. Thus, edges may be added or deleted from the graph or digraph.

• In a node weighted dynamic graph, the function f varies with time; thus, the weights on the nodes also change.

• In an edge or arc weighted dynamic graph or digraph, the function g varies with time.

• In fully weighted dynamic graph, both functions f and g may vary with time.

All combinations of the above types can occur.”

Therefore, in dynamic graphs, “nodes may be added or removed”, and “edges may be added or deleted”, which is why we chose these atomic graph modification operations.

In addition, please refer to this Simons Institute talk by Monika Henzinger [3] that defines a “dynamic graph algorithm” as “a data structure that maintains information about a graph while it is modified through local operations such as edge or vertex insertions or deletions.” Therefore, in order to modify a graph, one can either add edges, remove edges, add nodes, or remove nodes, which again are all modification operations that we analyze in our paper.

Choice of 250 Graphs

We first chose 250 graphs to get a comprehensive dataset while keeping monetary costs in mind, as 250 graphs created over 400k examples (as explained in Section 4.3), which lead to over 1.6 million independent evaluations across all four benchmark models. Secondly, through statistical analysis and the statistical significance table we add below, we were able to show statistical significance of performance improvements with MAP prompting using 250 graphs.

Lack of Ablation Studies

In Section A.7, we include an ablation study where we investigate the effect of edge density and the number of nodes in the graph on performance, finding that both variables can significantly alter performance depending on both the modification type and the number of modifications to be performed. We will evaluate the other LLMs in the final version of the paper.

[1] Fatemi, Bahare, Jonathan Halcrow, and Bryan Perozzi. "Talk like a graph: Encoding graphs for large language models." arXiv preprint arXiv:2310.04560 (2023).

[2] Harary, Frank, and Gopal Gupta. "Dynamic graph models." Mathematical and Computer Modelling 25.7 (1997): 79-87.

[3] https://simons.berkeley.edu/news/dynamic-graph-algorithms-what-we-know-what-we-dont

Model Selection Criteria

We selected GPT-4o-mini, Llama 3.1 405B, Claude 3.5 Sonnet, and o1-mini because they represent the latest advancements in LLMs, covering a spectrum of architectures and model sizes. All four LLMs achieve high performance across many benchmarks, including LiveBench [4].

Presentation Issues

Thank you for pointing out these issues with our presentation. In the new version of our paper, all figures have increased readability.

Lack of Error Analysis

We thank the reviewer for suggesting this addition. We added Section A.8, which details the different errors all benchmarks made on the Add Edge, Remove Edge, Add Node, and Remove Node modifications on the Print Graph task using the Adjacency Matrix encoder (our toughest task). On edge-related modifications, we find that models make interesting hallucinations when modifying indices, as they tend to incorrectly modify adjacent indices as well that weren’t specified in the prompt. On Add Node, while Claude 3.5 Sonnet and Llama 3.1 405B tend to perform well, o1-mini and GPT 4o-mini often return objects that are not mathematically valid matrices, and in our analysis these objects mostly take the form of a list of rows with inconsistent column counts. On Remove Node, all models struggle significantly, and return a matrix whose internal connections deviate substantially from the solution matrix.

Question 4

These baselines are from [1], and as such, they are among the most recent graph-focused LLM evaluations. As we stated in the Related Works section, these baselines benefit from their straightforward and fundamental nature compared to other graph-focused LLM evaluations.

[4] White, Colin, et al. "Livebench: A challenging, contamination-free llm benchmark." arXiv preprint arXiv:2406.19314 (2024).

Presentation

We appreciate the reviewer's point regarding the presentation of the paper. Firstly, we have uploaded a new paper that includes clearer figures. Regarding your point on the lack of clear tables to compare the performance across different LLMs on GraphModQA, we don’t include these tables because we want to explicitly show how performance changes as a function of modification length. For the Print Graph task, Figures 2 show the performance of o1-mini, Claude 3.5 Sonnet, Llama 3.1 405B, and GPT-4o-mini respectively on the adjacency matrix encoding, and Figures 11-24 in Section A.6 of the Appendix compare the performance of all four benchmark LLMs across other final questions and graph encodings. Additionally, Section A.6 includes further analysis on the results of these experiments.

Lack of Showcasing of GraphModQA

We appreciate the feedback regarding the presentation of the GraphModQA benchmark. The new version of the paper provides a more comprehensive illustration of the benchmark. Specifically, we have added Section 4.3, which details the total number of questions in GraphModQA (468,750 ), and how this number is derived.

Examples of Questions:

Regarding the forms of individual questions, we have added Section A.9 which includes Figures 33 to 38. These figures illustrate examples of input prompts and model outputs corresponding to zero-shot prompting, CoT prompting, and MAP prompting.

Unclear motivation

Thank you for highlighting this. The first important point to make is that you’re of course correct in that tools like PyG and NetworkX provide efficient and reliable implementations for many graph tasks, let alone modification tasks, in a single function call. However, there is already a growing literature that looks at LLMs' intrinsic reasoning abilities on graphs (e.g., [1] and [2]), and as the literature explains, they are not advocating for replacing these established tools with large language models (LLMs) for practical graph tasks. Instead, they aim to evaluate LLMs’ reasoning capabilities within the context of graph tasks as a way to better understand and quantify their strengths and limitations in multi-step reasoning scenarios.

We recognize a critical gap in the existing literature, where prior work has largely focused on basic static graph properties. Therefore, we add to this literature in a qualitatively new way by introducing the concept of graph modification as a more dynamic, multi-step reasoning challenge. This approach aligns with the broader goal of assessing and advancing LLMs’ ability to handle evolving, structured data representations, which is critical for domains like social network analysis and real-time decision-making in dynamic systems.

Lack of novelty of MAP prompting

Regarding your point on the similarity between MAP prompting and CoT prompting, there have been several different iterations of CoT. [3] first introduced CoT prompting by defining it as few-shot prompting consisting of triples: <input, chain of thought, output>. Our proposed MAP prompting, on the other hand, simply appends the phrase “For each operation, write out the entire resulting graph.” to the prompt. Therefore, MAP prompting is distinct and purpose-built for dynamic graph reasoning tasks, and does not center around CoT prompting.

Another iteration of CoT, Zero-shot-CoT [4], simply appends the phrase “Let’s think step by step.” to the prompt. While similar to MAP prompting in the sense that both encourage intermediate reasoning steps and involve appending simple phrases, MAP prompting differs from Zero-shot-CoT by requiring the explicit generation and output of the intermediate graph at each step of the reasoning process. This explicit instruction focusing on graph state tracking ensures that the model maintains a consistent internal representation of the evolving graph, which is particularly critical for tasks involving multiple dynamic modifications. Therefore, MAP prompting introduces a novel approach tailored to dynamic graph reasoning.

[1] Fatemi, Bahare, Jonathan Halcrow, and Bryan Perozzi. "Talk like a graph: Encoding graphs for large language models." arXiv preprint arXiv:2310.04560 (2023).

[2] Wang, Heng, et al. "Can language models solve graph problems in natural language?." Advances in Neural Information Processing Systems 36 (2024).

[3] Wei, Jason, et al. "Chain-of-thought prompting elicits reasoning in large language models." Advances in neural information processing systems 35 (2022): 24824-24837.

[4] Kojima, Takeshi, et al. "Large language models are zero-shot reasoners." Advances in neural information processing systems 35 (2022): 22199-22213.