GraphArena: Evaluating and Exploring Large Language Models on Graph Computation

We appreciate the reviewer's informative and constructive feedback. We provide point-to-pint responses below.

W1: ...the impact of these findings on practitioners and researchers is not clear. I recommend adding a discussion section in / after Section 3.2 to elaborate on the main takeaways of this paper. For example, are the findings in Section 3.2 surprising? How should we interpret the results from Section 3? What should researchers do in the future?

The main takeaways of experimental findings are in the last two paragraphs of the introduction. We've highlighted them and added cross-references in the revision. Novel findings include:

• Even leading models like GPT-4o and Claude-3.5-Sonnet face challenges with graph computation and exhibit a propensity for hallucination. This issue is more pronounced with larger graphs, more complex tasks, and smaller models.

• Comparisons between LLMs and graph algorithms reveal that LLMs often resort to using greedy algorithms for addressing NP problems, yet they sometimes opt for more effective approximation algorithms.

• Strategies like instruction tuning can significantly enhance performance on small-scale polynomial tasks but shows limited effectiveness on large-scale NP problems, suggesting that fine-tuning alone does not easily impart inherent advanced reasoning capabilities, such as algorithmic planning and long-context reasoning.

We discussed future studies in the conclusion section:

Our findings suggest promising directions for future research, such as (1) exploring advanced finetuning techniques to enhance LLMs' code writing and algorithmic reasoning abilities, (2) developing more efficient approaches to scaling test-time compute and addressing hallucination, and (3) integrating external tools or encoder modules to better support LLMs in graph computation.

W2: Some experiments are not consistent. For example, SFT is only applied to Llama and Qwen, while coder is only applied to GPT and DeepSeek. Why not conducting all the proposed methods in Section 3.2 on all the models tested in Section 3.1?

Both code writing evaluation and instruction tuning are resource-intensive processes. Therefore, our strategy is to select representative LLMs to focus on.

We chose GPT-4o and DeepSeek-V2 as our code models because they were the top two performers on OpenAI's HumanEval, a well-regarded code generation benchmark, at the time of our experiments. By focusing on their performance, we aim to capture the current upper limits of how LLMs perform in code writing for graph task solving.

Fine-tuning LLMs demands significant resources, and our computational capacity only supports full-parameter fine-tuning of open-source models with fewer than 10 billion parameters. We chose Llama3-8b and Qwen2-7b because they were the leading LLMs of this scale on GSM8K, a well-known math benchmark, when we conducted our experiments. This suggests their superior math reasoning capabilities. We believe that fine-tuning these models will provide greater benefits and yield more valuable insights.

W3: While I appreciate the use of real graphs in GraphArena, the connection between the tasks, findings, and these real graphs is weak. I recommend (1) including examples that demonstrate the tasks in GraphArena are relevant to real-world graph tasks and

Thank you for your suggestion. We've revised our introduction section to better motivate the the use of real graphs, the selection tasks, how they connect to reasoning, and the corresponding experimental findings.

The tasks in Grapharena have significant applications across various fields, such as social network analysis (e.g., using common neighbor and maximum clique for community detection), bioinformatics (employing GED and MCS for molecular comparison and protein search), and operations research (utilizing shortest path and TSP for routing).

In GraphArena, we build a real-world scenario for each task and use realistic graphs to enhance the authenticity, like flight route planning for the Traveling Salesman Problem, marking a substantial improvement over previous benchmarks that relied on synthetic graphs. Examples for all tasks can be found in Tables 7-16 in the appendix.

(2) providing a stronger rationale for using LLMs to solve these tasks over traditional graph algorithms.

Given that not all NP-complete problems can be solved with algorithms providing exact solutions, leveraging LLMs to tackle these challenges can yield valuable insights. As shown in Figure 3, GPT-4o occasionally surpasses approximate algorithms, highlighting its potential as an alternative heuristic that complements existing approximation methods within the graph community. Additionally, using LLMs to solve these tasks has the potential to bridge the gap between classical algorithms and natural language inputs that are otherwise inaccessible. We've added these discussions in the revised related work section.

We appreciate the reviewer's informative and constructive feedback. Our responses will cover: (1) justification of the selected tasks, (2) discussion of neural algorithmic reasoning benchmarks and methods, (3) the overclaim regarding 'Improving' Graph Computation, (4) the contribution of rigorous path-based evaluation, and (5) other minor weaknesses and questions.

1. Justification of Selected Tasks

The paper’s main contributions are the inclusion of real-world graphs in its dataset and textual features in both the input and desired output. However, the paper does not clearly justify evaluating LLMs on these particular tasks over those in prior benchmarks exploring LLM graph reasoning.

Compared with prior benchmarks, we exclude some trivial polynomial-time tasks and include more challenging NP-complete tasks. We have:

• four polynomial-time tasks to test direct algorithmic reasoning, requiring models to accurately execute established algorithm procedures step-by-step.
• six NP-complete tasks to evaluate meta algorithmic planning, where models must analyze problem characteristics and select suitable algorithms to excute. For example, the Traveling Salesman Problem with fewer than 10 nodes can be solved through enumeration. However, as the number of nodes increases, more efficient algorithms like dynamic programming or approximated approaches should be considered. This requires a higher level of reasoning and strategic decision-making for the model, and is overlooked by prevous benchmark study.

Analogous to mathematics, polynomial-time tasks are akin to K-12 math problem, while NP-complete graph problems are more like Math Olympiad challenges. Currently, LLMs have shown the ability to solve Olympiad-level geometry and proof problems, even winning a silver medal in the recent IMO. Therefore, concentrating on these challenging tasks is crucial for understanding the limitations and potential of LLMs, providing valuable insights to guide future research in the field.

Additionally, we focus on well-known tasks with rich real-world applications. When asked "what are the top 10 NP-complete graph problems", Claude-3.5-Sonnet lists all six NP tasks we selected, considering that GED and MCS are variants of Subgraph Isomorphism. The polynomial tasks we selected are also widely recognized, with shortest path and graph diameter (multi-source shortest path) being two of the most classic algorithms in algorithm textbooks. These tasks have significant applications across various fields, including social network analysis (e.g., using common neighbor and maximum clique for community detection), bioinformatics (employing GED and MCS for molecular comparison and protein search), and operations research (utilizing shortest path and TSP for routing).

• In GraphArena, we create a real-world scenario for each task and use realistic graphs to enhance the authenticity, marking a substantial improvement over previous benchmarks that relied on synthetic graphs.

2. Discussion of Neural Algorithmic Reasoning Benchmarks and Methods

This paper would also benefit from justifying the exclusion of neural algorithmic reasoning literature (both GNN and LLM-based), particularly the recent papers, “Benchmarking ChatGPT on Algorithmic Reasoning” (McLeish et al. 2024) and “The CLRS-Text Algorithmic Reasoning Language Benchmark” (Markeeva et al. 2024).
The paper would benefit from a comparison with other recent works in LLM algorithmic reasoning, for example, Ge et al. 2024, “Transformers meet Neural Algorithmic Reasoners” (Bounsi et al. 2024), “Are Large Language Models Graph Algorithmic Reasoners?” (Taylor et al. 2024), and other recent works in the NAR field...

Thank you for providing these valuable references, we added the following paragraph in related work to discuss neural algorithmic reasoning.

The development of neural networks capable of performing algorithmic computations has the potential to bridge the gap between classical algorithms and inputs that are otherwise inaccessible (Veličković & Blundell, 2021; Bevilacqua et al., 2023). These networks also show potential as more efficient and effective alternatives to human-crafted heuristics for combinatorial optimization tasks (Bengio et al., 2021; Georgiev et al., 2024). This field has progressed through various approaches, including graph neural networks (Khalil et al., 2017; Veličković et al., 2020), reinforcement learning (Mazyavkina et al., 2021), LLMs (Fu et al., 2023; McLeish et al., 2024; Taylor et al., 2024), and GNN-LLM hybrid models (Bounsi et al., 2024; Perozzi et al., 2024). Benchmarks like CLRS (Veličković et al., 2022) and its text-based version (Markeeva et al., 2024) assess LLMs on a wide range of general algorithmic reasoning tasks, focusing on the breadth of reasoning. In contrast, GraphArena targets challenging graph computational problems that demand more advanced reasoning skills, emphasizing the depth of reasoning.

My concerns have been addressed thoroughly and I have updated my score.

While including the references I mentioned in my review is an improvement, the above paragraph does not quite address my original concern. The field of neural algorithmic reasoning is quite rich, and multiple benchmarks are already established (Veličković et al., 2022; McLeish et al., 2024; Taylor et al., 2024; Markeeva et al., 2024). I was mainly asking for a paragraph describing what your paper provides that is missing from these benchmarks. Please give a view of how your paper fills the gaps in the current NAR field (hint: neither McLeish et al., 2024 nor Taylor et al., 2024 involve reinforcement learning).

I would recommend that the above evaluation details be included in the camera-ready version of the work (preferably in the main text). It is rare for benchmarks in this space to evaluate answers as graphs, and this could serve as a model for future work as well.

2. Task Selection Criteria

Question #2: How are the polynomial-time and NP-complete tasks chosen...
Weakness #1: Why these specific tasks are chosen and how they represent real-world applications.

While there is no gold standard for task selection, we focus on two main criteria:

(1) well-known tasks with rich real-world applications. When asked "what are the top 10 NP-complete graph problems", Claude-3.5-Sonnet lists all six NP tasks we selected, noting that GED and MCS are variants of Subgraph Isomorphism. The polynomial tasks we selected are also widely recognized, with shortest path and graph diameter (multi-source shortest path) being two of the most classic algorithms found in algorithm textbooks.

• These tasks have significant applications across various fields, including social network analysis (e.g., using common neighbor and maximum clique for community detection), bioinformatics (employing GED and MCS for molecular comparison and protein search), and operations research (utilizing shortest path and TSP for routing).

• In GraphArena, we build a real-world scenario for each task and use realistic graphs to enhance the authenticity, like flight route planning for the TSP example mentioned earlier, marking a substantial improvement over previous benchmarks that relied on synthetic graphs.

(2) challenging tasks that assess multi-dimensional reasoning skills. Compared with previous studies, we exclude trivial polynomial-time tasks like node counting and edge existence that can be directly solved in one step, and instead include more NP tasks. Unlike polynomial tasks with fixed solutions, NP tasks generally offer multiple solution paths. The model must determine an appropriate algorithm (e.g., exhaustive enumeration or approximation) based on the problem's structure and scale, which requires more advanced reasoning capabilities and problem-solving skills.

Since not all NP-complete problems can be solved using algorithms that provide exact solutions, leveraging LLMs to address these challenges can offer valuable insights. As illustrated in Figure 3, GPT-4o occasionally outperforms approximate algorithms, demonstrating its potential to serve as an alternative heuristic that complements existing approximation methods in the graph community. Moreover, the search space for NP problems is generally much larger than that for polynomial-time problems. As a result, evaluating LLMs on these tasks provides a more thorough and comprehensive assessment of their reasoning capabilities.

Do they represent a balanced challenge across diverse graph properties (e.g., density, connectivity)?

The inclusion of five different graph sources (DBLP, Social Network, DBpedia, Openflights, and PubChemQC) greatly improve the diversity compared with previous benchmarks that work on systhetic graphs. We added the statistics of Density and Edge connecteivity as you suggested in the task statistics table 4. As we can see, different tasks has very different Density (range from 0.23 to 1) and edge connectivity (range from 0.26 to 8.46).

The following table compared GPT-4o's performance on our real-world graphs versus synthetic Erdős-Rényi graphs of similar scale. It also highlights the diversity and complexity of authentic graph structures we used.

import itertools

# Users and friendships
users = ["Gwendolyn Russell", "Ashley Boyd", "Thomas Perkins", "Matthew Bennett II", "Ian Soto"]
friendships = [("Gwendolyn Russell", "Thomas Perkins"),
               ("Ashley Boyd", "Thomas Perkins"),
               ("Thomas Perkins", "Ian Soto"),
               ("Thomas Perkins", "Matthew Bennett II")]

# Function to check if a subset is independent
def is_independent(subset, friendships):
    for u1, u2 in itertools.combinations(subset, 2):
        if (u1, u2) in friendships or (u2, u1) in friendships:
            return False
    return True

# Find the maximum independent set
max_independent_set = []
for r in range(1, len(users) + 1):
    for subset in itertools.combinations(users, r):
        if is_independent(subset, friendships):
            if len(subset) > len(max_independent_set):
                max_independent_set = subset

# Print the result
print(list(max_independent_set))

def maximum_independent_set(users, friendships):
    # Create a graph from the users and friendships
    graph = {user: set() for user in users}
    for u, v in friendships:
        graph[u].add(v)
        graph[v].add(u)
    
    # Sort nodes by degree (number of connections)
    sorted_users = sorted(graph, key=lambda x: len(graph[x]))
    
    # Initialize the independent set
    independent_set = set()
    
    # While there are nodes left in the graph
    while sorted_users:
        # Select the node with the smallest degree
        node = sorted_users.pop(0)
        
        # Add it to the independent set
        independent_set.add(node)
        
        # Remove the node and its neighbors from the graph
        neighbors = graph[node]
        for neighbor in neighbors:
            if neighbor in sorted_users:
                sorted_users.remove(neighbor)
        
        # Remove the node from the graph
        del graph[node]
    
    return list(independent_set)

# Define the users and friendships
users = [
    "Timothy Hall", "Brianna Morton", "David Walker", "Debra Cook", "Danielle Hoffman",
    "Patrick Ellis", "Jim Cruz", "Bryan Mcintosh", "Kevin Smith", "Stacy Lindsey",
    "Denise Gregory", "Jessica Hahn", "Michael Rogers", "Miguel Wilson", "Elizabeth Washington",
    "Pamela Rodriguez", "Caitlin Harris", "Craig Hall", "Denise Ponce", "Casey Martin"
]

friendships = [
    ("Timothy Hall", "Danielle Hoffman"), ("Timothy Hall", "Brianna Morton"), ("Timothy Hall", "Craig Hall"),
    ("Timothy Hall", "Michael Rogers"), ("Brianna Morton", "David Walker"), ("Brianna Morton", "Casey Martin"),
    ("David Walker", "Patrick Ellis"), ("Debra Cook", "Patrick Ellis"), ("Patrick Ellis", "Casey Martin"),
    ("Patrick Ellis", "Denise Ponce"), ("Patrick Ellis", "Jim Cruz"), ("Patrick Ellis", "Bryan Mcintosh"),
    ("Patrick Ellis", "Kevin Smith"), ("Patrick Ellis", "Stacy Lindsey"), ("Patrick Ellis", "Denise Gregory"),
    ("Patrick Ellis", "Jessica Hahn"), ("Patrick Ellis", "Michael Rogers"), ("Patrick Ellis", "Miguel Wilson"),
    ("Patrick Ellis", "Elizabeth Washington"), ("Patrick Ellis", "Pamela Rodriguez"), ("Patrick Ellis", "Caitlin Harris"),
    ("Jim Cruz", "Denise Gregory"), ("Jim Cruz", "Pamela Rodriguez")
]

# Find the maximum independent set
result = maximum_independent_set(users, friendships)
print(result)

We appreciate the reviewer’s detailed and constructive feedback. Our responses will cover: (1) the evaluation process, (2) the criteria for task selection, (3) the analysis of reasoning capabilies, (4) the rationale for setting different graph scales, and (5) the novelty compared with existing benchmarks.

1. The Evaluation Process

Question #1: Could you elaborate on how the categories (correct, suboptimal, hallucinatory, missing) are determined in a more complex, multi-step task like the Traveling Salesman Problem? How does the evaluation framework ensure consistent scoring across models?
Weakness #4: For the evaluation metrics (Feasibility, Hallucination...), there is no clear explanation of how these metrics are calculated.

Our evaluation consists of three systematic steps: path extraction, feasibility check, and optimality check. To illustrate, consider the following TSP problem:

You are required to solve the Travelling Salesman Problem for an undirected flight route network. Your objective is to determine the shortest possible route that visits each of the listed airports exactly once and returns to the starting point.
**Problem to Solve**
Airports to visit: VPY, AAE, BGA, YWB.
Travel distances (in kilometers) between each pair of airports: 
- VPY to YWB: 16285 
- VPY to AAE: 9488 
- VPY to BGA: 13255 
- AAE to YWB: 7807 
- AAE to BGA: 9332 
- BGA to YWB: 6575
Please calculate the shortest tour and format your answer as follows: [Airport A, Airport B, Airport C, ..., Airport A]

We conduct the following three-step evaluation:

• Step 1: Path Extraction. We use regular expressions to extract the proposed solution path from the LLM's response (a sequence of airports for TSP). If a valid path cannot be extracted (due to formatting issues, no response, etc.), the response is categorized as missing. In over 99% of cases, the route can be extracted.

• Step 2: Feasibility Check. We write scripts to verify if the extracted path adheres to the problem's basic requirements. For TSP, this means visiting each node exactly once and returning to the starting point. Failed routes are categorized as hallucinatory, such as:

  • [VPY, BGA, VPY, YWB, AAE, VPY] (repeated visits)

  • [VPY, BGA, YWB, AAE] (no return)

  • [VPY, BGA, YWB, VPY] (missing airport AAE)

• Step 3: Optimality Verification. For feasible paths, we compute the path score (e.g., total route length for TSP). This score is compared to the optimal solution obtained by exhausted search. If they match, the result is optimal; otherwise, it is suboptimal. Examples are:

  • [VPY, BGA, AAE, YWB, VPY] total distance = 46779 km, suboptimal

  • [VPY, AAE, YWB, BGA, VPY] total distance = 37125 km, optimal

Our evaluation ensures consistent scoring as the same process is applied to all LLMs. Each task has unique feasibility and optimality requirements, as outlined in Section 2.2 and Appendix A. We provided a more nuanced assessment compared to previous studies focusing mainly on correctness,. Even when all responses are suboptimal (common in NP problems), we can still rank LLMs based on their path score (e.g., route length in TSP).

Question #3: When using code generation to solve graph problems, how is the correctness of the generated code verified?

We prompt LLMs to write code that outputs the solution path. The generated code is executed to print the path. If the code fails, the response is marked as missing. Otherwise, we evaluate the printed path using the same process mentioned above.

We sincerely thank the reviewer for your supportive and constructive feedback.

I don't think the paper has any significant weaknesses. My only quibble is that while the graphs are drawn from the real-world, the questions themselves are not. But I think this is pretty minor, and shouldn't affect what ultimately seems like an interesting paper with a meaningful contribution. If the goal is to measure graph reasoning skills, then I think relying on artificial problems is perfectly acceptable.

We recognize the limitations of template-based question generation. However, when human experts or LLMs create and rewrite questions, they can inadvertently alter the underlying graph structure, leading to mismatched answers. These types of errors in question generation are difficult to detect.

Given our primary objective of evaluating LLMs' graph reasoning abilities, we chose to maintain consistent question formats in this study. We plan to explore greater question diversity in future research. We added a discussion of this in the revised conclusion.

Are there any performance trends across different graph domains (e.g., DBPedia vs PubChemQC)? I wonder if differences in how graphs are tokenized by the model influence performance.

It is an interesting problem. We explored three graph domains for the shortest path task: knowledge graphs (DBPedia), molecular graphs (PubChemQC), and synthetic graphs (Erdős–Rényi model). Here are the results:

Based on GPT-4o's performance, knowledge graphs seem to be more challenging than molecular and synthetic graphs. This suggests knowledge graphs may have more complex topological features. Indeed, calculating the shortest distance in knowledge graphs is a more well-defined task, as it involves quantifying the minimum number of hops between two knowledge entities.

Additionally, we examined the impact of three different graph tokenizers on GPT-4o's performance:

As observed, there is no universally optimal graph tokenizer. In our main experiments, we selected the edge list as our graph tokenizer because it appears to be the most stable option across various tasks and graph properties. Additionally, the edge list is the most widely used approach in prior studies, such as NLGraph and GraphWiz. In contrast, using an adjacency matrix to represent a sparse graph can introduce redundant information, which may negatively impact model performance.