GraphArena: Evaluating and Exploring Large Language Models on Graph Computation
Authors: Jianheng Tang
Qifan Zhang
Yuhan Li
Nuo Chen
Jia Li
Venue: ICLR 2025 Poster (2025)
Keywords: Large Language Model Evaluation
Graph Algorithms
Primary area: learning on graphs and other geometries & topologies
TL;DR: This paper introduces GraphArena, a comprehensive benchmarking tool designed to assess and improve the reasoning capabilities of LLMs on graph computational problems.

Abstract: The ``arms race'' of Large Language Models (LLMs) demands new benchmarks to examine their progresses. In this paper, we introduce GraphArena, a benchmarking tool designed to evaluate LLMs on real-world graph computational problems. It offers a suite of four polynomial-time tasks (e.g., Shortest Distance) and six NP-complete challenges (e.g., Traveling Salesman Problem). GraphArena features a rigorous evaluation framework that classifies LLM outputs as correct, suboptimal (feasible but not optimal), hallucinatory (properly formatted but infeasible), or missing. Evaluation of over 10 LLMs reveals that even top-performing LLMs struggle with larger, more complex graph problems and exhibit hallucination issues. We further explore four potential solutions to address this issue and improve LLMs on graph computation, including chain-of-thought prompting, instruction tuning, code writing, and scaling test-time compute, each demonstrating unique strengths and limitations. GraphArena complements the existing LLM benchmarks and is open-sourced at https://github.com/squareRoot3/GraphArena.

Published as a conference paper at ICLR 2025
GRAPHARENA: EVALUATING AND EXPLORING LARGE LANGUAGE MODELS ON GRAPH COMPUTATION
Jianheng Tang, Qifan Zhang, Yuhan Li, Nuo Chen, Jia Li" Hong Kong University of Science and Technology (Guangzhou) j jtangff@connect .st.kk, jialee@ust.hk
ABSTRACT
The "arms race" of Large Language Models (LLMs) demands new benchmarks to examine their progresses. In this paper, we introduce GraphArena, benchmarking tool designed to evaluate LLMs on real-world graph computational problems. It offers a suite of four polynomial time tasks (e.g., Shortest Distance) and six NP- complete challenges (e.g.. Traveling Salesman Problem). GraphArena features a rigorous evaluation framework that classifies L.M outputs as correct, suboptimal (feasible but not optimal), hallucinatory (properly formatted but infeasible), or missing. Evaluation of over 10 LLMs reveals that even top-performing LLMs struggle with larger, more complex graph problems and exhibit hallucination issues. We further explore four potential solutions to address this issue and improve LLMs graph computation, including chain-of-thouge of-thouggt prompting, instruction tuning, code writing, and scaling test-time compute, each demonstrating unique strengths and limitations. GraphArena complements the existing LLM benchmarks and is open-sourced at hhttps://gite com/ /trm://suureeRttt/rraarrrrer
INTRODUCTION
Evaluating LLMs, especially their advanced reasoning capabilities, remains a significant long-term challenge. While standardized tests in fields like mathematics (Hendrycks et al. 202 I; Cobbe et al.
2021). medicine (Chen et al. 2023 Li et al. 2023a). and multi-task collections (Hendrycks et al.
2020 Srivastava et al. 2022) have become popular LLM benchmarks, concerns about data leakage in pretraining corpora (Aiyappa et al. 2023 Xu et al., 2024) raise questions about whether L.MMs genuinely reasoning or merely memorizing information. Crowd-sourced evaluations can address this issue but are typically expensive and tine-consuming (Zheng et al. 2023b) Chiang et al. 2024
Chang et al. 2024). Alternatively, evaluations using synthetic data, such as theorem proving Trinh
ct al.
2024 Xin el al. 2024), offer more rigorous assessments but often lack real-world relevance.
To balance factors such cost, novelty, complexity, diversity, and practical applicability in LLM evaluation, the research community has expanded its focus beyond text to include various modalities, such as vision (Lu et al. 2024). tabular (Sui et al. 2024). and spatiotemporal data (Lopez-Lira & Tang 2023). Among these modalities, graphs emerge ILMSs capabilities in several key areas: interpreting relational information or structured knowledge, processing non-sequential or non-Euclidean data, and generalizing across diverse structures or tasks. The potential graph-based based evaluations for LLMs has been recognized and explored in recent
particularly promising avenue for evaluating
literature (Perozzi al. 2024 Wang et al. 2023 Chen et al. 2024b).
In this paper, we benchmark LLMs on graph computational problems, which often require systematic traversal or search algorithms to solve. These problems serve
ideal testbed for evaluating the reasoning capabilities of LLMs (Li et al. 2024 Wei et al. 2024; Chen et al., 2024a). While several graph problem-solving benchmarks have been established, such NL.Graph (Wang et al. 2023) and GraphQA (Fatemi et al.) 2023), as well as algorithmic reasoning datasets like CLRS-Text (Markeeva al. 2024) and MAGMA (Taylor al., 2024), we identify several limitations in the existing landscape. First, these datasets are predominantly built on synthetic graphs, such as those generated by the Erdös-Rényi (ERDdS & R&wi 1959) models, which may not adequately reflect real- world diversity. Second, the tasks within these benchmarks are generally confined to basic structural
"oorreponningg author.

---

Published as a conference paper at ICLR 2025
understanding (e.g., connectivity checks) and algorithm execution (e.g.. breadth-first search). They largely overlook the assessment of higher-order reasoning skills, such as problem abstraction and simplification, strategy compariston and selection, etc. These capabilities are better demonstrated through solving more complex and open-ended tasks, such as NP-complete problems. Third, current evaluation methods typically rely string matching between the final answers and the responses, allowing models to succeed through guesswork rather than demonstrating genuine understanding of the underlying logic. Such methods lack a nuanced categorization of failure modes, limiting the depth of insights derived from the metrics.
To address these issues. we introduce GraphArena in Section 2 benchmarking tool designed to assess the reasoning capabilities of LLMs when tackling graph computational problems. Compared with previous graph benchmarks, three core improvements are introduced:
Realistic Graph Collection. Each problem in GraphArena features subgraph sampled from rich assortment of real-world graphs, including knowledge graphs, social networks, and molecular structures. Our sampling process is designed to preserve the original graph topology and attributes to capture real-world diversity. Additionally, each problem is contextualized within the real-world setting of the graph, offering more authentic and challenging evaluation environment.
Comprehensive Task Selection. Our benchmark presents more demanding graph tasks assess multi-dimensional reasoning skills. As shown in Figure it encompasses four polynomial-time challenges that test direct algorithmic reasoning, requiring models accurately execute algorithm procedures step-by-step. Moreover, it includes six NP-complete task that demand meta algorithmic planning, where models must analyze problem characteristics and select suitable algorithms to excute. This selection of diverse and well-known tasks ensures thorough evaluation of LLMs' abilities to perform both straightforward algorithm execution and strategic decision- maaoin..
Rigorous Path-based Evaluation. We propose a detailed evaluation protocol for each task to differentiate genuine problem-solvie from patter- guessing. LLMs must generate the entire solution path (or its components) within the graph that leads to the solution. Through a three-step process involving path extraction, feasibility check, and optimality verification, responses categorized as correct, suboptimal (feasible but not optimal), hallucinatory (properly formatted yet infeasible), or missing. This approach allows for a nuanced and accurate comparison among LLMs.
In our experiments, we extend the comparative analysis beyond LLMs by incorporating diverse set of baseline methods, including classical graph algorithms, graph neural networks, and Graph-LLM hybrid approaches. Additionally, we explore strategies beyond conventional prompt engineering to improve LLMs' performance in graph reasoning tasks. Our study seeks to address two key research questions:
To what degree can current LLMs solve graph computational problems? (Section After evaluating ten popular LLMs on 10,000 GraphArena problems, we find that LLMs perform signifi- cantly better on polynomial-time reasoning but struggle with meta algorithmic planning, which demands higher-level strategic think- ing. Even the most advanced LLMs such as GPT-4o and Claude-3.5-Sonnet, struggle with graph computations often producing hallucinatory outputs particulatil when handling larger graphs, more complex tasks, particularly with larger graphs and more complex tasks. For NP problems, these models typically default to greedy algorithms, though they sometimes utilize more effective approximation techniques. Despite their current limitations, our results highlight the potential of LLMs serve as alternative heuristics for NP tasks, complementing existing approximation methods.
tasks than on NP-complete ones. They excel in direct algorithmic
How can we further enhance LLMs on graph reasoning? (Section While previous benchmarks for graph problems have primarily focused on prompt engineering, we observe that chain-of-thoughh prompting exhibits limited effectiveness on GraphArena. To overcome this limitation, we explore several advanced approaches: (1) Instruction tuning on similar graph problems and solution paths enhances performance on small-scalc polynomial tasks. However. it proves less effective for large- scale NP problems, as fine-tume tne-tuning alone is insufficient to develop complex reasoning abilities, such as algorithmic planning and long-range reasoning. (2) Code generation and execution by LLMS show significant promise for solving large graphs and tackling more complex tasks, though some performance degradation is observed on small graphs. (3) Increasing test-time compute and allowing LLMs multiple attempts yield modest but consistent performance improvements. These findings underscore the need for innovative strategies to advance LLMs' graph reasoning capabilities.
2

---

Published as a conference paper at ICLR 2025
Local
Polynomial-Tie Time Problems
global
Common Neighbor
Shortest Distance
Connected Componenty
Graph Diameter
GraphArena
Graph Edit Distance
Travelling Salesman
OpenFlights
DBpedia
DBLP
PubChem
Maximum Common Subgraph.
Maximum Independent Set
Minimum Vertex Cover
Maximum Clique
No-Comllete Problems
Problem Generation
LLM Inference
Scorer
Small Graphs
Y reggined sobre the
undinettd asakenic ratwerk
Macimum Claqu Problen
Deepacek V2: [Claudiu, Danid Nicolo, Valentin]
Correct
Straight-forward Computation
Exhaustive
<Tack Dediilions
Enumeration
<Esample Denaastratioss
Problem Salve:
Authors netwock Clauda,
Daziel Nooda, Tabore, Valeedi
6PT-40: The Maximum Clique in given netwerk consiats of the following authors: [Donel, Nicola Volentin]
Direct Reasoning
Meta Planning
Research collaboration between
Subaptimal
these authers Claxdo and Nooll, Caudiu and Duie,, Claudia and
NP
V Valestn, Dasici and Nicala, Daniel and
Fablee. Dasiel and Valeene, Nicola
Valentn. Ntoah and Fablen.
Long-ronge Location
Heuristic Approximation
Mentify elique with the monimum
mumber of authers this networks.
8B: Clique:(Cludde (Cludiu, Nicolo,
Hallucinatory
Presmt yoontyourent enneer maiig format ithont, Aubertt, Authert. Authvef, ...
Large Graphs
Evaluation Framework
Reasoning Quadrants
Figure 1: Overview of the GraphArena benchmark.
BENCHMARK CONSTRUCTION
Figure provides an overview of our proposed GraphArena benchmark. In this section, we first discuss the collection and sampling methodologies for real-world graphs in Section 2.1] then offers detailed descriptions of 10 tasks within GraphArena and the problem generation process in Section Finally, Section 2.3 describes the evaluation framework score and compare LLMs' responses.
2.2
2.1 DATASET COLLECTION
GraphArena distinguishes itself from previous benchmarks by utilizing real-world graphs, offering richer diversity compared with synthetic ones. Graphs are collected from five sources: DBLP (Ley) 2002), academic collaboration network with over 1.3 million nodes (authors) and 5 million edges (collaborations); Social Network (Rossi & Ahmed, 2015). a composite graph combining Digg, Flixster, Lastfm, and Pokec data, totaling over 6 million nodes (users) and 40 million edges (friendships); DBpedia (Bizer et al., 2009). a knowledge graph subset (DBpedia IM (Xin et al., (022)) with over million nodes (entities) and 7 million edges (relationships): OpenFlights (OpenFlights).

---

Published as a conference paper at ICLR 2025
an airport network consisting of 3,390 nodes (airports) and 19,166 edges (flight routes) weighted by geographical distance; and PubChemQC (Nakata & Shimazaki 2017), containing 3.7 million molecular graphs from the PCQM4Mv2 Dataset (Hu et al.. 2021). where nodes represent atoms and edges represent chemical bonds. The detailed description of these datasets is in Appendix A
We employ random walk with restart strategy initiating from randomly selected nodes to sample subgraphs effectively. This enables us to identify the top-k most frequently visited nodes, forming local dense subgraphs that closely maintain the topological features of the original graphs. For the PubChemQC dataset, we sample molecular graphs directly by specified sizes. All graphs are treated as unweighted and undirected, except for OpenFlights which weighted.
2.2 TASK SELECTION
While there is no gold standard for task selection, we focused on well-known tasks with rich real- world applications, and challenging tasks that assess multi multi-diimnssonal reasoning skills. We consider four polynomial-time tasks to test direct algorithmic reasoning, requiring models to accurately execute established algorithm procedures step-by-step:
For graph G = {V; E with vertices v 122 V, the task involves identifying the subset 5 S V where each u E S is connected to both ii1 and 22. The objectives are to (1) identify these common neighbors, and (2) maximize their count. We utilize the DBLP academic collaboration graph for this task.
Common Neighbor:
Shortest Distance: In a graph 9 = EV,E}, determine the shortest path from node U1 to Ug. The goals are to (1) find a viable path (v1, M1, .,,, 22), and (2) minimize its hop count. We apply this task to the DBpedia knowledge graph.
Connected Component: In this task, the model identifies one representative node from each connected component within a graph. For a given graph 9 = {V,E), the objectives are to (1) identify set of vertices such that each is from distinct connected component, and (2) ensure that these vertices represent all possible connected components of the graph. This task is applied to the Social Network dataset.
The diameter of a graph is the maximum distance between any pair of nodes in the graph. Given a graph G = (V, E). this task entails finding (1) a shortest path between two arbitrary vertices and (2) ensuring it is the maximum possible among all shortest paths. This is performed using the DBpedia knowledge graph.
Graph Diameter:
Each task is briefly described by a keyword (Neighbor, Distance, Component, Diameter) to facilitate easy reference. We decompose each task into requirements, the first basic requirement and the second optimal requirement. We further consider six No-colpeete tasks to evaluate meta algorithmic planning, where models must analyze problem characteristics and select suitable algorithms to excute:
Maximum Clique Problem (MCP): Identify the largest complete subgraph, or clique, in a given graph 9 == ( sampled from DBLP. The task entails (1) finding a clique C V that feasible within the graph, and (2) ensuring that C is the largest among all possible cliques.
The descriptions for the remaining five tasks-Maximun Independent Set (MIS), Minimum Vertex Cover (MVC), Maximum Common Subgraph (MCS), Graph Edit Distance (GED), and Traveling Salesman Problem (TSP) are provided in Appendix B due space constraints.
Problem Generation: For each of the 10 tasks, we randomly sample 500 small and 500 large graphs to create two distinct subsets, yielding total of 10,000 graphs. For difficulty calibration, we use task-specific graph scales determined by each problem's 's computational complexity. For the Neighbor and Distance tasks, small graphs contain 4 to 19 nodes, while large graphs contain 20 to 50 nodes. For Component, Diameter, MCP, MIS, and MVC, small graphs have 4 to 14 nodes, and large graphs have 15 30 nodes. For MCS, GED and TSP, small graphs have 4 to 9 nodes and large graphs have 10 20 nodes. The ground truth of each problem is generated by corresponding exact algorithms.
After sampling graphs of the given size, we encode graph problems into text using templates, a common practice in previous benchmarks (Wang et al.) 2023 Chen et al. 2024a). An example of this encoding is shown in the bottom left of Figure [ The process begins with an introduction and definition of the task, followed by randomly selected example with the correct answer to demonstrate the problem-solving process and task requirements. Subsequently, the problem to be solved is presented with detailed graph information. While the graphs in each problem may not
4

---

Published as a conference paper at ICLR 2025
appear large, their text representation often results in problems containing up to 6,000 tokens, posing a long-contex challenge. Detailed statistics on graph sizes and problem lengths, along with examples for each task, provided in Table 4 and Appendix
2.3 EVALUATION PROCESS
We develope a fine-gra grained evaluation process to assess the reasoning process LLMs and prevent pattern-based guesses. For each task, LLMs are required to output the relevant graph component or path that contributes to the final answer, as highlighted by the green elements each graph shown in Figure 1 Our evaluation process consists of three steps: (1) Path Extraction: We use regular expressions to extract the proposed solution path from the LLM's response. If a valid path cannot be extracted due to formatting issues, lack of response, etc., the response is categorized as missing. (2) Feasibility Check: We employ scripts to verify whether the extracted path meets the basic requirements of the problem. Paths that fail this check are categorized as hallucinatory, (3) Optimality Verification: For feasible paths, we calculate a path score (e.g., total route length for TSP, and number of cliques for MCP). This score is then compared to the optimal solution obtained through exhaustive search. If they match, the result is optimal; otherwise, it is considered suboptimal.
For example, as shown in the bottom middle of Figure I Deepseek- V2 correctly identifies the maximum clique of four authors. In contrast, GPT-4o finds feasible but suboptimal clique with three nodes. Llama3-8b produces hallucinatory response, as the nodes chooses do not form a clique. If we were to evaluate only numerical results, in existing benchmarks, this error would be overlooked since it also leads to the correct number "4"
Metrics. Given the rarity of missing results in our experiments (less than 1% in most cases), our primary metrics are Accuracy (the proportion of correct answers), Feasibility (the proportion of both correct and sub-optimal answers), and Hallucination (the proportion of hallucinatory responses). We also introduce ranking- based metrics including for more comprehensive comparison between different LLMs, particularly useful when most responses suboptimal. These include Mean Reciprocal Rank (MRR), Top-1 Probability, and Top-3 Probability.
EXPERIMENTS
Experimental Setup. Our evaluation in GraphArena encompassed ten prominent LLMs, including both closed-source and open-source variants, well as single models and mix-of-experts architectures of varying scales. Closed-source models included the GPT-40-2024-088 mini-2024-07-118
2024-08-06 (OpenAl 2023), GPT-4o-
S.tude-3.5-somneee 20241e2222 (Anthropic 2024). and 4-M---plus (GLM 2024)
(whose smaller version is open-sourced). Open-source models include Llama3- 70b--------e 70b-instruct and Llama3-8b-instruct from Meta (AT@ Meta 2024), Owwen2.5-7bbiinsrrue from AliCloud (Bai et al. 2023), and Gemma-7b-1 from Google Cloud (7b it). We also evaluated two mix-of-expert LLMs: Deepseek-V2 (Bi al. (024) with 230 billion parameters (21 billion active) and Mixtral-7x8h (Jiang ct al. 2024) with 47 billion parameters (13 billion active). We utilized a low temperature setting 0. imposed no constraints on output length, and maintained other configurations default for all LLM models. The full- nall-parameter fine-tuning process was conducted with a learning rate of 0.0001, using a cosine learning rate scheduler with a warmup ratio of 0. and batch size of 4.
For closed-source LLMs and open-source models exceeding 10 billion parameters, we utilized the corresponding cloud-based services. Smaller open-source models were run on our local infrastructure equipped with four NVIDIA H800 PCIe 80GB GPUs. Given the computational demands and costs associated with LLM evaluation, we conducted a single run per model across the 10,000 problems in GrenhArena. Additionally, compared LLM performance against traditional graph algorithms, graph neural nenworks, and Graph-LLM hybrid models (Chen et al. 2024a Perozzi et al.) 2024) to provide a comprehensive assessment of LLMs' capabiliiiess in graph computation. For these models, we follow the original implementations and configurations. All problems, responses, and our codebase have been recorded and will be open-sourced facilitate reproducibilityy
5

---

Published as a conference paper at ICLR 2025
Table 1: Average rankings and performance of 10 LLMs 4 Polynomial-time and 6 NP-complete lasks across small and large graphs. All metrics excluding MRR are scaled to [0, 100]. Acc., Fea., and Hallu, represent Accuracy, Feasibility, and Hallucination probability, respectively. For all metrics except Hallucination, higher values indicate better performance. The best-performing open and closed-source models are highlighted bold.
Polynomial- Time Tasks (Small)
Polynomial- Time Tasks (Large)
LLM
MRR
Top-1
Top-3
Acc.
Fca.
Hallu.
MRR
Top-1
Top-3
Acc.
Fca.
Hallu.
Claude-3.5-sonne
0.87
84.3
86.2
82.2
86.5
13.4
0.72
67.2
71.7
58.7
70,5
29.5
GPT-4o
0.83
79.5
82.3
76.9
84.6
13.4
0.58
49.7
56.6
43.5
58.9
37.3
GPT-4o-mini
0.76
70.6
75.1
68.9
82.8
16.1
0.50
40.7
48.3
36.6
56.9
40.7
GI.M-4-plus
0.79
75.1
77.3
72.7
78.8
18.6
0.60
53.1
58.6
45.7
57.0
42.0
Llama3-706
0.68
63.2
66.3
61.2
71.9
27.3
0.47
37,0
44.3
31.6
49.3
49.0
Llama3-8b
0.37
29.2
30.8
28.5
44.5
53,9
0.21
10.8
12.6
9.4
18.9
78.2
Qwen2.5-72h
0.67
59.9
64.0
59.0
74.8
11.7
0.51
42.1
49.4
39.9
55.7
36.3
Deepseek-y2
0.60
53.1
56.9
51.4
64.2
35.0
0.39
29.0
35.7
24.7
37.9
Mixtral-7x8b
0.46
38.5
40.4
37.8
51.3
46.4
0.27
15.8
13.8
31.5
67.2
Gemma-7b
0.34
25.5
26.7
25.2
38.6
61.4
0.19
9.6
10.1
9.2
16.1
84.0
NP-Complete Tasks (Small)
NP-Complete Tasks (Large)
3.5-sonnet
0.65
57.5
65.7
47.8
74.4
25.5
0.46
32.7
48.4
7.2
51.9
47.0
GPT-4o
0.65
55.6
66.5
47.3
77.0
20.2
0.41
24.2
46.4
6.3
53.4
43.6
GPT-40-mini
0.56
46.5
72.4
25.5
12.8
24.9
3,3
39.7
GLM-4-plus
0.60
49.3
60.5
41.3
78.8
20.4
0.35
18.7
39.4
4.8
50.5
49.1
Llama3-70b
0.54
43,8
52.6
75.3
24.5
0.30
15.1
27.8
4.7
45.0
55.0
Llama3-8b
0.35
23.6
57.9
41.7
1.9
24.1
75.5
Qwcn2.5-72b
0.39
26.7
65.1
27.0
0.20
0.7
21.4
42.1
Deepseek-v2
0.52
40.1
51.1
33.7
74.1
24.5
0.29
14.8
27.7
3.1
40.9
58.1
Mixtral-xx8b
0.30
18.1
23,9
15.6
59.3
37.4
0.20
6.1
14.4
1.6
29.4
64.6
Gemma-76 7b
0.28
15.6
23.2
12.9
57.1
42.6
0.22
7.5
20.4
0.9
31.2
68.8
3.1
MAIN RESULTS
In Table we present the average performance of ten LLMs across four polynomial -ime and six NP-complete tasks on both small and large graphs. Claude-3.5 3-nnnt consistently ranks as the top performer across most metrics and settings, while Llama3-70b the leading open-source model. Performance generally declines for all LLMs as graph sizes increase and tasks transition from P to NP, significantly expanding solution space. Notably, LLMSs struggle considerably with NP-complete tasks large graphs, achieving less than 10% accuracy. This indicates that the most challenging scenarios in GraphArena still exceed the current capabilities of LLMs.
GraphArena also reveals significant performance disparity between LLMs of varying parameter sizes. For instance, in polynomial-time tasks, the gap between Llama3-700 and Llama3-8b is substantial 61.2% vs. 28.6% small graphs and 31.6% vs. 9.4% on large graphs This gap is significantly wider than in existing benchmarks, such as GSM8K (93.0% vs. 79.6%) and GPQA (39.5% 34.2%). A similar trend observed in the Qwen series. Interestingly, the performance gap between GPT-4o and GPT-4o-mini is not as large as one might expect given their difference in API pricing. Moreover, models with fewer parameters are more prone hallucination. with ratios of 78.2% for Llama3-8b and 84.0% for Gemma-7b, 7b, indicating that graph computation necessitate more advanced reasoning capabilities that larger LLMS are better equipped manage.
To closely examine model performance on individual tasks, we compare the feasibility and accuracy of five selected LLMs on each task in Figure 2 Results for the remaining five LLMs are presented in Figure g in Appendix C Model performance varies substantially across tasks, with tasks like Diameter, MCS, and MVC demonstrating notably low feasibility, indicating high hallucination rates.
Hallucination Impact. We illustrate the hallucination probability against varying node sizes for three selected tasks in Figure with results for the remaining seven tasks presented in Figures Jaaeeessanndd and 10 in Appendix C These plots reveal significant, nearly monotonic increase in hallucination ratio as node size grows from to 30. For example, in the Diameter task, GPT-4o's 's hallucination probability rises dramatically from 16% at node size of 5 more than 80% at node size of 30. This trend underscores that larger graph sizes, and their associated challenges in long-range multi-step reasoning, major contributors to hallucination.

---

Published as a conference paper at ICLR 2025
Clande-3.5 s.seemeet
DespseeloV2. V2
GPT-4o
Llamad Sb
Qwwen2.5-72b
Fcusibility on Small Graphs Diameter
Feasibility
Large Graphs
Diamçac
GEE
Neishbur
CED
ulboz
MCS
SP
MCS
MIS
SVC
MIs-
MVC
Accuracy Small Graphs
Accuracy Large Graphs
Dimmttt
Cannecial
Diamcaet
Conuaned
MC
MC
Dipazce
Neighbur
uhbor
MCS
MCS
MBS
MIS
MVC
Figure 2: Feasibility and accuracy comparison of five selected LLMs on each individual task. The
circles renresent nerformance levels. proeressine outward from 20% to 100% increments of 20%.
GPT-4o Random
GPT-4o vs Greedy
GPT-4o vs Approximated
MVC-casy
MIS-casy
GED-easy
TSP-easy
MVC-hard
MIS-hard
GED-hard
TSP-hard
Figure 3: The percentage of problems where GPT-4o wins, ties, loses against Random, Greedy, and Approximated algorithms.
0.2
64
06
28
1o
02
04
08.
10
62
0.5
0.5
Claude-3.5-somec,
Deepseck-V2
GPT-4o
Llama3-8b
Qwen2.5-72b
Connected
MIS
Diameter
Hallocination Probability
1.0
Hallucination Probability
1.0-
Hallucination Probahility
0.8
0.8
0.8
0.6
0.6
0.4
0.4
0.4
0.2
0.0
0.0
0.0
10
15
20
25
30
10
15
20
25
30
10
15
20
25
30
Graph Size
Graph Size
Graph Size
Figure 4: The influence of graph size on hallucination probability for the Maximum Independent Set, Graph Diameter, and Connected Component tasks.
Comparison with Graph Algorithms. problem using exact graph algorithms and evaluate LLMss accuracy against these optimal solutions. However, algorithms can take hours to find optimal solutions for some NP-complete tasks, we also compare LLMs with three suboptimal yet more efficient graph algorithms: (1) Random algorithms: randomly generate feasible solution; (2) Greedy algorithms: choose the best option at each step; and (3) Approximation algorithms: advanced graph algorithms with problem-speeeee speciffc heuristics or
GraphArena, we compute the ground truth for each
approximations that typically outperform greedy algorithms (Christofides 2022 Zeng et al. 2009
Bоppana & Halldórsson 1992 Bar- Yehuda & Even 1985).
Figure 3 illustrates the comparative performance of GPT-4o against Random, Greedy, and Approxi- mation algorithms four selected NP-complete tasks, showing the percentage of problems where
7

---

Published as a conference paper at ICLR 2025
Table Performance comparison of LLMs finetuned on graph problems (-SFT).
Task & Graph Scale
Polynomial (Small)
Polynomial (Large)
NP (Small)
NP (Large)
LLM
Acc.
Fca.
Hallu.
Acc.
Fea.
Hallu.
Acc.
Fea.
Hallu.
Acc.
Fea.
Hallu.
Llama3-8h
28.6
45.3
53.9
20.2
58.1
41.7
9.4
19.7
78.2
31.2
68.8
Llama3-8b-SFT
54.7
72.5
17.3
38.1
65.0
31.1
38.1
65.0
31.1
7.5
25.5
49.6
Qwen2-7b
20.4
33.6
62.9
9.7
17.8
73.4
21.5
65.0
33.6
1.5
29.8
68.2
Qwen2-7b-SFT
84.3
90.6
9.4
42.0
59.7
39.5
39.5
57.6
15.0
6.2
26.8
50.5
Table 3: Performance comparison of LLMs prompted to write and execute code (-Coder).
Task Graph Scale
Polynomial (Small)
Polynomial (Large)
NP (Small)
(Large)
LLM
Acc.
Fea.
Hallu.
Acc.
Fea.
Hallu.
Acc.
Fea.
Hallu.
Acc.
Fea.
Hallu.
GPT-4o
76.9
84.6
13,4
43,5
58.9
37.3
47.3
77.0
20.2
6.3
53.4
43.6
GPT-4o-Coder
62.7
71.7
18.9
51.1
62.0
23.0
46.5
77.4
16.8
7,9.
46.8
35.4
DeepSeck-V2
51.4
64.2
35.0
24.7
37.9
61.1
33.7
74.1
24.5
3.1
40.9
58.1
Seepeek-V2-Codee
60.9
69.7
16.7
38.0
44.6
31.4
31.2
63.1
24.4
3.5
23,4
37.5
GPT-4o wins, ties, or loses. Comprehensive results for all LLMs are summarized in Table S in Appendix C Our analysis reveals that GPT-4o consistently outperforms random solutions across most scenarios. When compared to greedy algorithms, GPT-4o demonstrates comparable performance on small-scale graphs but struggles with larger, more complex structures. Although GPT-4o rarely surpasses advanced approximation algorithms,, its occasional successes hint the potential of LLMs as alternative heuristics for No-complete tasks.
Comparison with Graph Neural Networks (GNNs). We conducted preliminary comparison with three types of graph neural networks (GNNs) GIN (Xu et al. 2019), GAT' (Veličković et al.) 2017). and GraphSAGE (Hamilton et al. (017)- detailed in Table 6 of Appendix C Our results indicate that Blaude-3.5-sonnee generally outperforms these GNNs when they lack task-specific architecture design. Beyond this comparison, LLMs offer unique advantages beyond raw performance metrics. Their ability to interpret and respond to natural language problem descriptions significantly enhances accessibility for non-expert users, and their adaptability allows them tackle new problem variations without explicit reprogramming.
Ceruraa
Craphiiaion
Comparison with Graph-LLM hybrid mod- els. We evaluated GraphArenaa against two types of graph-enhanced L.LMs: GraphWiz (Chen (et al., (0244a), Llama2-7b--base model fine- tuned for graph reasoning, and GraphToken (Per- ozzi al. 2024), hybrid model that uses Graph Isomorphism Network (GIN) as a graph tok- enizer for LLM. Graph Wiz performed poorly GraphArena (0.2% to 1.2% accuracy on small- scale tasks), primarily due to the lack of task overlap and differences in graph formats between GraphArena and the Graph training corpus. GraphToker generally performed between standalone GIN and Gemma-7b when fine-tuned on comparable training set. As shown in Figure it improved upon the original LLM backbone but underperformed compared the GIN encoder, with mutual benefits only observed in the large-scate Neighbor task. These results suggest that significant improvements are needed to fully leverage the strengths of both graph- models and L.MSs.
Small Graphs
Large Graphs
00% Corrra
Niighoe Didanees ConnoaalDanntte
Neighber Cotrattel Diancar
Figure 5: Performance comparison of Graph and its backbone LLM and GNN.
3.2 EXPLORING STRATEGIES TO ENHANCE LLMS ON GRAPH COMPUTATION
Several strategies have been proposed to mitigate hallucinations L.MS and boost reasoning capabilities (Bang et al., 2023 Ji et al. 2023 Zhang et al.) 2023 Wang et al., 2022), but their effectiveness in graph computation remains to be explored. this section, we consider the following four directions reduce hallucination and improve LLMs on graph problem-solving:
Chain-of- -haingof-Thought (CoT) Prompting, CoT prompting encourages models to generate intermediate
reasoning steps towards a conclusion (Wei et al. [022 Feng al. [2224] Merrill & Sabharwall 2023). We designed manually crafted examples for the Graph Diameter and Connected Component tasks, evaluating the impact of zero to four CoT examples. Figure demonstrates general improvement in
8

---

Published as a conference paper at ICLR 2025
Deepseck-V2 V2
GPT-4o
Llama3-8b
Mixtral-7x8b
Feasibility: Component
Accuracy: Component
casibility: Diameter
Accuracy: Diameter
1.0
1.0
1.0
1.0
0.8
0.8
0.6
0.6
0.6
0.4
0.4-
0.4
0.4
0.2
0.2-
0.2
0.2
0.0
0.0
0.0
0.0
2
3
0
Shots
Shots
Shots
Shots
Figure 6: The influence of thaou-ss with k-shot step-by-step demonstrations on the feasibility and accuracy model performance for the Graph Diameter and Connected Component tasks.
Connected
Diameler
Parallel
Parallel
Sequential
Sequential
1.0
1.0
0.8
Hallucination
0.8
0.8
Hallucination
0.8
Accuracy
Accuracy
0.6
0.6
0.6
0.6
0.4-
0.4
0.4
0.4
0.2
0.2
0.2
0.2
0.0
0.0
0.0
0.0
2
2
2
2
2
2
2
5
2
3
4
Attempts
Attempts
Attempts
Attempts
Figure 7: Performance comparison of GPT-4o-mini on three large-scale graph tasks using parallel and sequential test-time compute scaling techniques. The x-axis represents the number of attempts.
model accuracy. Deepscek-V2' performance significantly improves after adding one CoT example for the Component task. However, GPT-4o and Mixtral-7x8b show marginal improvements, and in some cases, performance degrades with more examples a phenomenon also observed in previous benchmarks (Wang et al. 20233 Fatemi et al. 2023). These results suggest that while CoT prompting helps reduce errors, remains insufficient resolve hallucinations.
Code Writing. LLMS often struggle with mathematical reasoning, which is crucial for solving complex graph problems. address this, we explored using external tools for computation. Inspired by the approach of writing code for math problem-solving (Gou et al.) (202)), we prompted LLMs, specifically GPT-4o and Deepseek-Cossee problems in GraphArena. Results in Table show that this code-writing approach effectively reduced hallucination rates, particularly on large graphs. For instance, Deepseek- Booeee-----ooe V2-Coder's hallucination rate for polynomial complexity tasks on large graphs decreased from 61.1 11.1% % 31.4%. However, observed some negative impacts on small graphs, likely due to errors in extracting graph information from text and challenges in code writing.
(Zhu et al. 2024). to write and exccute code for solving
Instruction Tuning. LLMs often hallucinate on long-tail knowledge with limited training data (Mallen al. 2023 Kandpal al. 2023), and graph problem-solving likely falls into this category. To provide more extensive data exposure, we fine-tuned Llama3-8b and Qwen2-7b on an additional 10,000 Graph Arena problems, using ground-truth solution paths supervision. As shown in Table 2 Llama3-8b-Sh demonstrates substantial improvements over its base model, with performance even comparable to Llama3-70b However, the improvement are more significant for small graphs and polynomial-time tasks, while long-context multi-step reasoning remains challenge.
Scaling Test-time Compute. Recent studies demonstrate that scaling L.MMs' test-time compute optimally can be more effective than scaling model parameters (OpenAl 2024 [hell et al. 2024). Graph computation problems with high complexity are particularly suitable for this approach, as they often require systematic search and are challenging to solve in a single attempt. We explore two methods for scaling test-time compute: (1) repeated sampling (Brown et al.] 20024, referred to as parallel, which generates multiple LLM answers and uses checker to identify the best one; and (2) progressive-ine prompting (Zheng et al.) (023a), labeled as sequential, which enables iterative interactions between checkers and I.IMMs, using previous answers and results hints to guide the

---

Published as a conference paper at ICLR 2025
model toward correct solutions. We apply these techniques to GPT--4omini on three large-scale graph tasks, with results shown in Figure 7 While the hallucination ratio decreases significantly with increasing attempts, accuracy improvements are limited to simpler tasks like Connected Component. This suggests that scaling test-time compute alone is insufficient for complex graph tasks due to the expansive search space involved.
4 RELATED WORK
LLM Evaluation. Early evaluations of text generation focused on fundamental skills, including similarity measures such as ROUGE (Lin 2004) and BL.UU (Papineni al., 2002) for machine translation. They also included inherent scores like Diversity (Li al. 2016) and Perplexity (Jelinek cct al. 1977) for open-domain conversations (Zhang et al. 2018 Li et al. 2017), and factual measures
such F-score and exact match for machine reading comprehension (Rajpurkar et al. 2016 Chen
2018) and question answering (Zhuang et al. [023 Kwiatkowski et al. 2019). Human preference
remains critical aspect of model evaluation (Zhngg et al.) 2023b] Li et al. 2023b Chiang et al.)
2024). ChatbotArena (Chiang et al. 2024) employs a pairwise comparison approach and leverages crowd-sourcing ensure task diversity.
Neural Algorithmic Reasoning. The creation of neural networks capable of executing algorithmic computations offers a promising bridge between classical algorithms and real-world data formats that defy traditional processing (Veličković & Blundell [021] BBevilaqqua et al. (023). Such networks further hold promise as replacements for numan-crafter heuristics in comb combinatorial optimization, potentially surpassing their efficiency or effectiveness (Bengio et al.] 2021 Georgiev et al., 2024).
This field has evolved through multiple methodological approaches: graph neural networks Khalil
et al. Veličkovi et al. 2020), reinforcement learning frameworks (Mazyavking Baazyakkina et al. 2021).
and L.LMs MMlLe et al. 2024]]
2024|/Taylor Taylor al. 2024 Fuu al. (023), as well as emerging architectures
combining GNNs and LLMs (Bounsi al. [2024] Perozzi al. 2024). Current evaluation paradigms
emphasize distinct reasoning dimensions: While benchmarks like CLRS (Veličković et al. 2022)
and its text-based adaptation (Markeeva et al. 2024) assess broad algorithmic mastery across diverse
tasks, GraphArena specifically probes the depth of reasoning in graph-structured computations.
LLM on Graphs. Compared with graph learning tasks such as node classification (Chen et al. 2024c
Tang et al. (023aa) and link prediction (Liu et al.] 2024 Tang et al.] (023b), graph computational problems pose more challenges for L.LMs as they require deeper understanding of structural
information and long-range multi-step reasoning (Luo et al. 2024] Wang et al., 2024: Chai et al.
Liu & Wu 2023: Zhang et al. 2024b). GraphQAA (Fatemi et al. (023) and NLGraph (Wang ct al. 2023) are two early benchmarks in this domain, locusing on basic graph problems using small-scale synthetic graphs VisionGraph (Li et al. 2024) and GITA (Wei et al. (024) introduce multimodal graph reasoning tasks that require LLMs to reason over both text and image modalities.
2023
Graph (Chen et al. (024a) introduces an cntructtionttning dataset to improve LLMs' graph reasoning capabilities.
5 CONCLUSION
This paper introduces GraphArena, a comprehensive benchmarking tool designed to assess the reasoning capabilities of LLMs on graph computational problems. Featuring realistic graph collection, carefully curated tasks, and a rigorous evaluation framework, GraphArena provides valuable insights into LLM assessment and further development. Our extensive evaluation of ten leading LLMs across 10,000 graph computational problems reveals persistent hallucination issues, particularly evident with larger graphs, complex tasks, and models with fewer parameters. To address these challenges, we investigated four potential solutions: chain-of-thoughh prompting, instruction tuning, code writing, and scaling test-time compute. Each approach demonstrated unique strengths and limitations in mitigating model hallucination and improving LLM performance on graph wuoblem-solving 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 scale test-time compute and address hallucination, and (3) integrating external tools or encoder modules to better support L.LMs in graph computation.
10

---

Published as a conference paper at ICLR 2025
Acknowledgement. This work supported by National Key Research and Development Pro- gram of China Grant No. 2023YFF0725100 and Guangzhou-HKUSSTOOG Joint Funding Scheme 2023A03J0673.
REFERENCES
Gemma 7b it. htts://ungiingfieeooogggg///emmm Accessed: 2024-05-25.
Meta. Llama 3 model card. Github, 2024.
Rachith Aiyappa, Jisun An. Haewoon Kwak, and Yong-yeol Ahn. Can we trust the evaluation on ChatGPT? In Anaclia Ovalle, Kai-Wei Chang, Ninareh Mehrabi, Yada Pruksachatkun, Aram Galystan, Jwala Dhamala, Apury Verma, Trista Cao, Anoop Kumar, and Rahul Gupta (eds.), Proceedings of the 3rd Workshop on Trustworthy Natural Language Processing (TrustNLPP 2023), pp. 47-54, Toronto, Canada, July 2023, Association for Computational Linguistics. doi: 10.18653. v1/2023. 1r2223.trustnlp-1.55
AI Anthropic. The claude model family: Opus, sonnet, haiku. Claude-3 Model Card, 2024.
Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, et al. Qwen technical report. arXiv preprint arXiv:2309. 2023.
Yejin Bang, Samuel Cahyawijaya, Nayeon Lee, Wenliang Dai, Dan Su, Bryan Wilie, Holy Lovenia, Ziwei Ji, Tiezheng Yu, Willy Chung, Quyet V. Do, Yan Xu, and Pascale Fung. multitask, multilingual, multimodal evaluation of chatgpt reasoning, hallucination, and interactivity. ArXiv, 02//232220402,, 2023.
Reuven Bar- Ychuda and Shimon Even. local-ratio theorem for approximating the weighted vertex cover problem. In North-Holland Mathematics Studies, volume 109, pp. 27-45, Elsevier, 1985.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour d'horizon. European Journal of Operational Research, 290(2):405 4211, 2021.
Beatrice Bevilacqua, Kyriacos Nikiforou, Borja Ibarz, Ioana Bica, Michela Paganini, Charles Blundell, Jovana Mitrovic, and Petar Veličković. Neural algorithmic reasoning with causal regularisation. In International Conference Machine Learning. pp. 2272-2288. PMLR, 2023.
Xiao Bi, Deli Chen, Guanting Chen, Shanhuang Chen, Damai Dai, Chengqi Deng, Honghui Ding, Kai Dong, Qiushi Du, Zhe Fu, al. Deepseek I1m: Scaling open-source language models with longtermism. arXiv preprint T.X.i:2241.02995 2024.
Christian Bizer, Jens Lehmann, Georgi Kobilarov, Sören Auer, Christian Becker, Richard Cyganiak, and Sebastian Hellmann. Dbpedia-a crystallization point for the web of data. Journal of web semantics, 7(3):154-165 2009.
Ravi Boppana and Magnús M Halldórsson. Approximating maximum independent sets by excluding subgraphs. BIT Numerical Mathematics, 32(2): 32(2):180-196, 1992.
Wilfried Bounsi, Borja Ibarz, Andrew Dudzik, Jessica B Hamrick, Larisa Markeeva, Alex Vitvitskyi, Razvan Pascanu, and Petar Veličković. Transformers meet neural algorithmic reasoners. arXiv preprint arXiv:2406.09555
2024.
Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21788 2024.
Ziwei Chai, Tianjic Zhang. Liang Wu. Kaiqiao Han, Xiaohai Hu, Xuanwen Huang, and Yang Yang. Graphllm: Boosting graph reasoning ability of large language model. arXiv preprint 100.0853 2023.
Yupeng Chang, Xu Wang, Jindong Wang, Yuan Wu, Linyi Yang, Kaijie Zhu, Hao Chen, Xiaoyuan Yi, Cunxiang Wang, Yidong Wang, et al. A survey on evaluation of large language models. ACM Transactions Intelligent Systems and Technology, 15(3):1-45, 2024.

---

Published as a conference paper at ICLR 2025
Danqi Chen. Neural reading comprehension and beyond. Stanford University, 2018.
Emma Chen, Aman Kansal, Julie Chen, Boyang Tom Jin, Julia Reisler, David E Kim, and Pranav Rajpurkar. Multimodal clinical benchmark for emergency care (mc-bec): A comprehensive benchmark for evaluating foundation models in emergency medicine. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36. pp.
Curran Associates, Inc., 2023.
Nuo Chen, Yuhan Li, Jianheng Tang. and Jia Li. Graphwiz: An instruction-followinng language model for graph problems. arXiv preprint arXiv:2402. 16029, 2024a.
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 (Ims) in learning graphs. ACM SIGKDD Explorations Newsletter, (5(2))42-66)) 61, 2024b.
Zhikai Chen, Haitao Mao, Hongzhi Wen, Haoyu Han, Wei Jin, Haiyang Zhang, Hui Liu, and Jiliang Tang. Label-free node classification on graphs with large language models (LLMs). In The Twelfth International Conference on Learning Representations, 2024c.
Wei-Lin Chiang, Lianmin Zheng, Ying Sheng, Anastasios Nikolas Angelopoulos, Tianle Li, Dacheng Li, Hao Zhang. Banghua Zhu, Michael Jordan, Joseph E Gonzalez, al. Chatbot arena: An open platform for evaluating Iims by human preference. arXiv preprint arXiv:2403.0m 132, 2024.
Nicos Christofides. Worst-case analysis of new heuristic for the travelling salesman problem. In Operations Research Forum, volume 3, pp. 20. Springer, 2022.
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 14168, 2021.
ERDdS and A R&wi. On random graphs I. Publ. math. debrecen, 6(290-297):18, 1959.
Bahare Fatemi, Jonathan Halerow, and Bryan Perozzi. Talk like a graph: Encoding graphs for large language models. In NeurlPS 2023 Workshop: New Frontiers in Graph Learning, 2023.
Guhao Feng, Bohang Zhang. Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: theoretical perspective. Advances in Neural Information Processing Systems, 36, 2024.
Yao Fu, Hao Peng, Litu Ou, Ashish Sabharwal, and Tushar Khot. Specializing smaller language models towards multi-step reasoning. In International Conference on Machine Learning, pp. 10421-10430. PMLR, 2023.
Dobrik Georgiev Georgiev, Danilo Numeroso, Davide Bacciu, and Pietro Liò. Neural algorithmic reasoning for combinatorial optimisation. In Learming on Graphs Conference, pp. 28-1. 1. PMLR, 2024.
Team GLM. Chatglm: A family of large language models from glm- 130b to glm-4 all tools, 2024.
Zhibin Gou, Zhihong Shao, Yeyun Gong, yelong shen, Yujiu Yang. Minlic Huang, Nan Duan, and Weizhu Chen. ToRA: A tool-integrated reasoning agent for mathematical problem solving. In The Twelfth International Conference on Learning Representations, 2024.
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017.
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. arXiv preprint arXiv:2009.00 03300, 2020.
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. In Vanschoren and S. Yeung (eds.), Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks, volume 1, 2021.
12

---

Published as a conference paper at ICLR 2025
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. Ogb-Isc: A large-scale challenge for machine learning on graphs. arXiv preprint rrXiv:2103.09430, 2021.
Fred Jelinek, Robert L Mercer, Lalit R Bahl, and James K Baker. Perplexity a measure of the difficulty of speech recognition tasks. The Journal of the Acoustical Suciety of America, 62(S1): S63-S63, 1977.
Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Ye Jin Bang. Andrea Madotto, and Pascale Fung. Survey of hallucination in natural language generation. ACM Computing Surveys, 2023.
Albert Q Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, et al. Mixtral of experts. arXiv preprint arXiv:2401.00 04088, 2024.
Nikhil Kandpal, Haikang Deng, Adam Roberts, Eric Wallace, and Colin Raffel. Large language models struggle to learn long-tail knowledge. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 15696-15707 PMLR, 23-29 Jul 2023.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstcin, Illia Polosukhin, Jacob Devlin, Kenton Lee, Kristina Toutanova, Llion Jones, Matthew Kelcey, Ming-We Wei Chang, Andrew M. Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov. Natural questions: A benchmark for question answering research. Transactions of the Association for Computational Linguistics, 7:452 466, 2019. doi: 10.1162/tact a 00276.
Michael Ley. The dblp computer science bibliography: Evolution, research issues, perspectives. In International symposium string processing and information retrieval, pp. 1-10. Springer, 2002.
Chunyuan Li, Cliff Wong, Sheng Zhang, Naoto Usuyama, Haotian Liu, Jianwei Yang, Tristan Naumann, Hoifung Poon, and Jianfeng Gao. Llava-med: Training large language-and-vision assistant for biomedicine in one day. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 28541- 28564. Curran Associates, Inc., 2023a.
Jiwei Li, Michel Galley, Chris Brockett, Jianfeng Gao, and Bill Dolan. A objective function for neural conversation models. In NAACL HLT 2016, The 2016 Conference of the North American Chupter of the Association for Computational Linguistics: Human Language Technologies, San Diego California, USA, June 12-17, 2016, pp. 110-119. The Association for Computational Linguistics, 2016.
Xuechen Li, Tianyi Zhang, Yann Dubois, Rohan Taori, Ishaan Gulrajani, Carlos Guestrin, Percy Liang, and Tatsunori B Hashimoto. Alpacaeval: An automatic evaluator of instruction-follovii models, 2023b.
Yanran Li, Hui Su, Xiaoyu Shen, Wenjie Li, Ziqiang Cao, and Shuzi Niu. DailyDialog: A manually labelled multi-turn dialogue dataset. In Greg Kondrak and Taro Watanabe (eds.), Proceedings of the Eighth International Joint Conference on Natural Language Processing ( (Volume 1: Long Papers), pp. 986-995, Taipei, Taiwan, November 2017. Asian Federation of Natural Language Processing.
Yunxin Li, Baotian Hu, Haoyuan Shi, Wei Wang, Longyue Wang, and Min Zhang. Visiongraph: Leveraging large multimodal models for graph theory problems in visual context. arXiv preprint arXiv:2405.0499 04950, 2024.
Chin-Yes Yew Lin. ROUGE: A package for automatic evaluation of summaries. In Text Summarization Branches Out, pp. 74-81, Barcelona, Spain, July 2004. Association for Computational Linguistics.
13

---

Published as a conference paper at ICLR 2025
Chang Liu and Bo Wu. Evaluating large language models on graphs: Performance insights and comparative analysis. arXiv preprint arXiv:2308. 2023.
Hao Liu, Jiarui Feng, Lecheng Kong, Ningyue Liang, Dacheng Tao, Yixin Chen, and Muhan Zhang. One for all: Towards training one graph model for all classification tasks. In The Twelfth International Conference Learning Representations, 2024.
Alejandro Lopez-Ling and Yuehua Tang. Can chatgpt forecast stock price movements? return predictability and large language models. arXiv preprint arXiv:2304.076111 2023.
Pan Lu, Hritik Bansal, Tony Xia, Jiacheng Liu, Chunyuan Li, Hannaneh Hajishirzi, Hao Cheng, Kai-Wei Chang, Michel Galley, and Jianfeng Gao. Mathvista: Evaluating mathematical reasoning of foundation models in visual contexts. In The Twelfth International Conference on Learning Representations, 2024.
Zihan Luo, Xiran Song, Hong Huang, Jianxun I Lian, Chenhao Zhang, Jinqi Jiang, Xing Xie, and Hai Jin. Graphinstruct: Empowering large language models with graph understanding and reasoning capability, arXiv preprint arXiv:2403.0444 2024.
Alex Mallen, Akari Asai, Victor Zhong, Rajarshi Das, Daniel Khashabi, and Hannaneh Hajishirzi. When not to trust language models: Investigating effectiveness of parametric and non-parametric memories. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Proceedings of the st Annual Meeting of the Association for Computational Linguistics ( (Volume 1: Long Papers), pp. 9802-9822, Toronto, Canada, July 2023. Association for Computational Linguisties. doi: 10. 1/tp:///1222..r act-0o033c---1
Larisa Markeeva, Sean McLeish, Borja Ibarz, Wilffied Bounsi, Olga Kozlova, Alex Vitvitskyi, Charles Blundell, Tom Goldstein, Avi Schwarzschild, and Petar Veličković. The clrs-text algorithmic reasoning language benchmark. arXiv preprint TrXiv:2400604229, 2024.
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: survey. Computers & Operations Research, 134: 105:005,00, 2021.
Sean McLeish, Avi Schwarzschild, and Tom Goldstein. Benchmarking chatgpt algorithmic reasoning. arXiv preprint arXiv:2404.03441, 2024.
William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. In The Twelfth International Conference on Leurning Representationss 2023.
Maho Nakata and Tomomi Shimazaki. Pubchemqe project: large-scale first-principles electronic structure database for data-driven chemistry. Journal of chemical information and modeling, 57(6): 1300-1308, 2017.
OpenAl. GPT-4 technical report. Arxiv, 2023.
OpenAl. Learning reason with 1lms. 2024.
OpenFlights. https://peenfihht.orrg.. Accessed: 2024-05-25.
Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: method for automatic evaluation of machine translation. In Proceedings of the 40th Annual Meeting of the Association forr Computational Linguistics, July 6-12, 2002, Philadelphia, PA, USA, pp. 311-318, ACL, 2002.
Bryan Perozzi, Bahare Fatemi, Dustin Zelle, Anton Tsitsulin, Mehran Kazemi, Rami Al-Rfou, and Jonathan Halcrow. Let your graph do the talking: Encoding structured data for 1lms. arXiv preprint arXiv:2402.05866 2024.
Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. SQuAD: 100,000+ questions for machine comprehension of text. In Jian Su, Kevin Duh, and Xavier Carreras (eds.), Proceedings of the 2016 Conference Empirical Methods in Natural Language Processing, pp. 1383-2392. Austin, Texas, November 2016. Association for Computational Linguistics. doi: 10.18653/v1/ D16- 1264.
14

---

Published as a conference paper at ICLR 2025
Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analyties and visualization. In AAAI, 2015.
Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling Ilm test-time compute optimally can more effective than scaling model parameters. arXiv preprint 220.:::22000033311.. 2024.
Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alone et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. arXiv preprint 2et.:2206.44615. 2022.
Yuan Sui, Mengyu Zhou, Mingjie Zhou, Shi Han, and Dongmei Zhang. Table meets Ilm: Can large language models understand structured table data? a benchmark and empirical study. In Proceedings of the 17th ACM International Conference on Web Search and Data Mining, pp- 645-654, 2024.
Jianheng Tang, Fengrui Hua, Ziqi Gao, Peilin Zhao, and Jia Li. Gadbench: Revisiting and benchmark- ing supervised graph anomaly detection. In Advances in Neural Information Processing Systems, volume 36, pp. 29628-296531 2023a.
Jianheng Tang, Kangfei Zhao, and Jia Li. A fused Gromov-Wassersee Wasserstein framework for unsupervised knowledge graph entity alignment. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Findings of the Association for Computational Linguistics: ACL 2023, pp. 3320-3334, Toronto, Canada, July 2023b. Association for Computational Linguistics.
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Arnetminer: extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 990-998, 2008.
Alexander K Taylor, Anthony Cuturrufo, Vishal Yathish, Mingyu Derek Ma, and Wei Wang. Are large-language models graph algorithmic reasoners? arXiv preprint arXiv:2410.22597, 2024.
Trieu H Trinh, Yuhuai Wu, Quoc V Le, He He, and Thang Luong. Solving olympiad geometry without human demonstrations. Nature, 625(7995):476-482. 2024.
Petar Veličković and Charles Blundell. Neural algorithmic reasoning. Patterns, 2(7), 2021.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2017.
Petar Veličković, Adrià Puigdomenech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell, and Charles Blundell. The clrs algorithmic reasoning benchmark. In International Conference on Machine Learning, pp. 22084-22102 PMLR, 2022.
Petar Veličkovié, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execution of graph algorithms. International Conference on Learning Representations, 2020. URL https://openreviiee nett/Forummid-SkkKOOFE..
Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov.
Can language models solve graph problems in natural language? In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Jianing Wang, Junda Wu, Yupeng Hou, Yao Liu, Ming Gao, and Julian McAuley. Instructgraph: Boosting large language models via graph-centric instruction tuning and preference alignment. arXiv preprint arXiv:2402.08788. 2024.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdh- ery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint 2rXiv:2203.11177 2022.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of thothtttht prompting elicits reasoning in large language models. Advances in Neural Information P Processing Systems, 35.24824-24837, 2022.
15

---

Published as a conference paper at ICLR 2025
Yanbin Wei, Shuai Fu, Weisen Jiang, Zejian Zhang, Zhixiong Zeng. Qi Wu, James Kwok, and Yu Zhang. Gita: Graph to visual and textual integration for vision-language graph reasoning. In The eiihth- Annual Conference on Neural Information Processing Systems, 2024.
Huajian Xin, Daya Guo, Zhihong Shao, Zhizhou Ren, Qihao Zhu, Bo Liu, Chong Ruan, Wenda Li, and Xiaodan Liang. Deepseek-prowee Advancing theorem proving in Ilms through large-scale synthetic data. arXiv preprint TrXXi:2405.143353 2024.
Kexuan Xin, Zequn Sun, Wen Hua, Wei Hu, Jianfeng Qu, and Xiaofang Zhou. Large-scale entity alignment via knowledge graph merging, partitioning and embedding. In Proceedings of the 31 ACM International Conference on Information Knowledge Management, pp. 2240-2249, 2022.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ICLR, 2019.
Ruijie Xu, Zengzhi Wang, Run-Ze Fan, and Pengfei Liu. Benchmarking benchmark leakage in large language models. arXiv preprint arXiv:2404. 18824, 2024.
Zhiping Zeng, Anthony KH Tung. Jianyong Wang. Jianhua Feng, and Lizhu Zhou. Comparing stars: On approximating graph edit distance. Proceedings of the VLDB Endowment, 2(1):25-36, 2009.
Bohang Zhang. Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, and Liwei Wang. Beyond weisfeiler- lehman: A quantitative framework for GNN expressiveness. In The Twelfth International Confer- ence on Learning Representations, 2024a.
Qifan Zhang, Xiaobin Hong, Jianheng Tang, Nuo Chen, Yuhan Li, Wenzhong Li, Jing Tang, and Jia Li. Geoder: Improving large language model for generalized graph problem solving, 2024b. URL https://arxix www.oss////a/ooooooo..ooooo. 24 10. 19084
Saizheng Zhang, Emily Dinan, Jack Urbanek, Arthur Szlam, Douwe Kiela, and Jason Weston. Personalizing dialogue agents: have a dog, do you have pets too? In Iryna Gurevych and Yusuke Miyao (eds.), Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume Long Papers), pp. 2204-2213, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10. 00.118633/11P18--1
Yue Zhang, Yafu Li, Leyang Cui, Deng Cai, Lemao Liu, Tingchen Fu, Xinting Huang, Enbo Zhao, Yu Zhang, Yulong Chen. et al. Siren's 's song in the ai ocean: A survey on hallucination in large language models. arXiv preprint arXiv:2309.01219, 2023.
Chuanyang Zheng, Zhengying Liu, Enze Xie, Zhenguo Li, and Li. Progressive-hin prompting improves reasoning in large language models. arXiv preprint arXiv:2304009797, 2023a.
Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, Hao Zhang, Joseph E Gonzalez, and lon Stoica. Judging llm-as-a-judge with mt-bench and chatbot arena. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36. pp. 46595 46623. Curran Associates, Inc., 2023b.
Qihao Zhu, Daya Guo, Zhihong Shao, Dejian Yang, Peiyi Wang, Runxin Xu, Y Wu, Yukun Li, Huazuo Gao, Shirong Ma, et al. Deepseek-coder--V: Breaking the barrier of closed-source models in code intelligence. arXiv preprint urXiv:2406. 1931, 2024.
Yuchen Zhuang, Yue Yu, Kuan Wang, Haotian Sun, and Chao Zhang. Toolqa: A dataset for Ilm question answering with external tools. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 501 17-501453 43, Curran Associates, Inc., 2023.
16

---

Published as a conference paper at ICLR 2025
A ADDITIONAL DATASET INFORMATION
As introduced in Section 2.1 problems in GraphArena is collected from five resources:
DBLP Ley 2002) is an academic database containing over million publications under the CCO 1.0 license. We use an undirected research collaboration graph for the period 2003-2018 from DBLP (Tang al. 2008). This graph consists of 1,354,852 nodes and 5,129,047 edges, with each node representing an author and each edge reflecting a collaboration that has occurred at least five times.
Social Network (Rossi & Ahmed 2015) is repository comprising over 70 different social networks under the CC BY-SA 3.0 License. We combine graphs from four large networks--igg. Flixster, Lastfm, and Pokec-to form a dataset of 6,118,795 nodes and 60,647,227 edges. Each node symbolizes a user, and each edge denotes a friendship connection. All user names are pseudonymized for privacy.
DBpedia (Bizer et al. 2009) extracts structured content from Wikipedia to form a comprehensive knowledge graph. We use DBpedialM (Xin et al., 2022), subset of the English version, which comprises 16130, nodes and 7.21 7,214,631 edges. Each node represents an entity, and each edge denotes a relationship, with all original textual content retained attributes. It is under the CC BY-SA 3.0 License.
Openftights (OpenF'lights provides data for over 10,000 airports and their connecting flight routes. We construct undirected graph where nodes are airports and edges are flight routes, weighted by the geographical distance between airports. We preserve the largest connected component in this graph, which consists of 3,390 nodes and 19, 166 edges. Subsequently, fully-connected graph by adding new edges for all node pairs, using the shortest distance as the weight. This dataset is available under the DbCL v1.0 License.
transform it into
PubChemQC (Nakata & Shimazaki, 2017) offers a quantum chemistry database detailing ground- state electronic structures. From the PCQM4Mv2 Datasct-parr of the OGB Large-Scale Challenge (Hu et al. )222) collected from PubChemQC-we incorporate 3,746,620 individual graphs. Each graph represents molecule, where nodes are atoms and edges chemical bonds, with atom types preserved as node attributes. It is under the CC BY 4.0 License.
B ADDITIONAL TASK INFORMATION
We complete the description of remaining NP-complete tasks not fully detailed in Section 2.2
Maximum Independent Set (MIS): Select the largest set of mutually nonadjacent nodes from graph G = EV The task is to (I) identify an independent set S C V, and (2) ensure that S is the largest among all feasible sets. This task is performed using the Social Network dataset.
Minimum Vertex Cover (MVC): Given graph G = {V.E), find subset of nodes S C V such that each edge in G has at least one endpoint in S. The Minimum Vertex Cover Problem to (1) find the vertex cover S and (2) ensure the size of S is minimum among all vertex covers of G. We explore this using the Social Network dataset.
Maximum Common Subgraph (MCS): Compare two graphs G and H. to find the largest common subgraph. The objectives are to (1) determine a node-induced common subgraph S between G and H. and (2) maximize the size of S. The PubChemQC dataset is used for this task.
Graph Edit Distance (GED): For two graphs G and H. determine the minimum edit distance via node mappings. This involves (I) establishing a node mapping that aligns with H. and (2) minimizing the edit operations required. These operations include adding or deleting an edge or isolated node, or relabeling a node. The PubChemQC dataset is utilized here.
Traveling Salesman Problem (TSP): Solve the TSP in weighted graph g = (V,E), where
w : + IR+ assigns a positive weight to each edge, representing the travel distance. The objectives are to (1) find a route P that visits each node exactly once and returns to the starting point, and (2) minimize the total travel distance. We utilize the OpenFlights dataset for this challenge. To ensure every pair of nodes is connected, thereby guarantecing feasible solution, convert the dataset into a complete graph by adding edges to represent the shortest possible distances between nodes that are not directly connected.
17

---

Published as a conference paper at ICLR 2025
Table 4 presents comprehensive statisties for each task in GraphArena, including the average and maximum number of nodes, edges, and text length (in characters). Tables [ provide detailed examples of prompts for each task. For the Connected Component and Graph Diameter tasks, chain-of-thought prompting with step-hy-step solution demonstrations is provided.
C ADDITIONAL EXPERIMENTAL RESULTS
offfers a feasibility and accuracy comparison of the remaining five LLMss on individual tasks, complementing the analysis in Figure Figures and T0 illustrate the influence of graph size on hallucination probability for the remaining seven tasks, complementing Figure 4 Table (lbbend the analysis in Figure 3 showing the percentage of problems where each of the 10 LLMs wins, ties, or loses against Random, Greedy, and Approximated graph algorithms.
Figure 8 offers
Comparison with graph neural networks (GNNs). Directly comparing GNNs and LLMs in GraphArena is challenging due to their fundamentally different paradigms. LLMs are multi-task, unsupervised models that process natural language inputs, while GNNs are typically task-specific, supervised models that operate on network data. For simplicity, we configured GNNs to directly predict the answer rather than generating the solution path or component. Although it is feasible to let GNNs generate detailed solutions, different tasks like GED and MCS would require specific architectural modifications. We compared three representative GNNs: Graph Isomorphism Network (GIN) (Xu et al., 2019), Graph Attention Network (GAT) (Veličković al.) 2017), and Graph Sample and Aggregate (GSAGE) (Hamilton et al. 2017). We generated an equivalent amount of training data for GNNs using the same framework GraphArena. Table shows the average accuracy for these
GNNs on Polynomial-time and NP-complete problems across small and large graphs. The results indicate that Claude-3.5-sonee demonstrates superior performance in most scenarios. While GNNs achieve the best results on large-scale NP-complete problems, recent studies have theoretically proved the limitations in GNNs' computational capabilities (Zhang et al. 2024a). For instance, message passing neural networks cannot even count triangles. Given the limitations, we posit that GNNs might be performing pattern- based regression rather than genuinely solving graph problems, In contrast, LLMs appear more aligned with true problem-solving
Comparison of different graph tokenizers. In Table we examined the performance of three graph tokenizers-EAde Edge List, Adjacency List, and Adjacency Matrix on GPT-4o across two selected tasks: Shortest Distance and TSP, both on small and large graphs. As shown in The Edge List tokenizer demonstrated relatively stable performance across various tasks, with feasibility and accuracy scores consistently higher than those of the Adjacency Matrix, particularly in the Shortest Distance tasks where it achieved 0.914 and 0.902 accuracy for small graphs, and 0.788 and 0.720 for large graphs Although the Adjacency List tokenizer slightly outperformed the Edge List in some instances, such in the TSP (Large) task with lower hallucination rate of 0.082, the Edge List remains the most stable option. Combined with its widespread use in prior studies like NI.Graph (Wang et al.) 2023) and GraphWiz (Chen al., 2024a), we use Edge List as our primary graph tokenizer for the main experiments, as shown in Tables 9 to I8 Conversely, the Adjacency Matrix often introduced redundant information, particularly in sparse graphs, leading to decreased performance, as evidenced by its 0.436 hallucination rate and 0.448 accuracy in the Shortest Distance (Large) task.
Comparison of Real-World and Synthetic Graphs. Table presents the evaluation of GPT-4o on two polynomial-time tasks: Common Neighbor and Shortest Distance. Our findings indicate that GPT-4o achieves notably higher accuracy and lower hallucination rates on synthetic Frdös-Rény graphs compared to real-world graphs of similar size. This disparity in performance suggests that synthetic graphs may fail to adequately represent the complex topological features and irregular structures found in real-world networks. Consequently, relying exclusively on synthetic benchmarks could lead to an overestimation of a model's generalization capabilities. This observation motivates us to incorporate samples from real- world networks into GraphArena.
18

---

Published as a conference paper at ICLR 2025
Table 4: Summary of task statistics in GraphArena, detailing the average and maximum values for
nodes (V), edges (E), text length (7") characters, graph density (D), and edge connectivity (EC)
across problem instances.
Problems
[V]
[V
E
Fi
[T]
[T
D
EC
Common Neighbor
19.4
50
68.6
409
4323.5
18014
0.44
1.37
Shortest Distance
19.6
50
36.8
209
5639.5
23731
0.28
0.61
Connected Component
13.5
30
14.4
1785.4
5503
0.26
Graph Diameter
13.4
30
22.0
128
3741.3
11783
0.31
1.16
Maximum Clique Problem
13.2
30
39.1
154
3025.0
7921
0.52
1.70
Maximum Independent Set
12.8
30
19.5
141
1902.8
6182
0.30
1.08
Minimum Vertex Cover
14.1
30
23.3
151
2178.4
6429
0.31
1.17
Maximum Common Subgraph
9.2
20
8.9
22
1025.1
1187
0.30
1.04
Graph Distance
9.4
20
9.2
23
1643.7
2142
0.29
1.03
Traveling Salesman Problem
9.5
20
50.6
190
1806.1
4741
1.00
8.46
Gemma-7b
GLM-4-plus
GPT-4o-mini
Llama3-8b
Mixtral-7x8b
Feasibility Small Graphs
Feasibility on Large Graphs
Diameter
Connected
Diameter
Connected
MCP
Distance
MCF
Distance
GE
Neighbor
GED
Neighbor
MCS
SP
MCS
SSP
Accuracy Small Graphs
Accuracy on Large Graphs
Diarneeer
Connected
Diameter
Cummetted
MCP
Distance
MCF
Distance
GED
Neighbor
GED
Neighbor
MCS
SSP
MCS
TSP
M
MVC
MIS
MVC
Figure 8: Feasibility and accuracy comparison of the remaining five LLMs in Figure 2 on each individual task.
19

---

Published as a conference paper at ICLR 2025
Table 5: The percentage of problems where LLM wins, ties, or loses against three types of classic
graph algorithms: Random, Greedy, and Approximated.
Travelling Sulesman Problem (Small)
Travelling Salesman Problem (Large)
Algorithm
Random
Greedy
Approximated
Random
Greedy
Approximated
LLM
win/tie/lose
winftic/lose
win/tie/lose
win'tic/lose
win/tic/lose
win/tic/lose
GPT-4o
76.2/15.288
18.8/36,2/55.
95.2/0.0/4.8
18.8/4 3/4.2/77.0
60.6/0.6/88.8 8
GPT-4o-mini
67.6/14.8/17.6
17.2/40.4/42.
12.4/29.4/53
70.6/0.0/29.4
0.6/0.0/99.4 4
0,0/0.0/100.0
Claude-3.5-somnel
77.4/15 8/6.8
24.6/52.2/23.2
17. 17.4/40,6/444 6/420
99.6
33.2/8 4/58
20.8/1.0/78.2
20.8/1 0/788.2
Llama3-70b
65.0/13.4/21.6
12.0/36.6/51.4
8.4/23. 8/67.8
78.6/0.0/21.4
1.4/0.0/98.6
0.6/0.099 .9990
Llama3-8b
47.0/13,6/39.4
12.2/1554/72.4
6.4/15.6/78.0
30.6/0.0/69.4
0.2/0.0/99.8
0.0/0.0/100.0
Qwen2.5-72b
1.6/2.8
14.6619
9.0/19.6/71
30.0/0.0/70.0
1.0/0. 1.0004/98..
0.8/0.0/99.2
Deepseck-v2
72.6/15.4/12.0
21.0/42.//7..
15.8/32.2/52.0
66.8/0.0/33.2
4.4/0,2/95..
2//000/97..8
Mixtral-7x8b
46.4/14.2/39.4
10.6/22.6/66.8
6.0/18.0/76.0
24.4/0.0/75.6
0.0/0.0/100.0
0.000.0/100.0
Gemma-7b
30.2/12.6/57.2
8.8/13.8/77.4
5.0/13.0/82.1
3.4/0.0/96.6
0.0/0.0/10.00
0.0/0.0/100.0
GI.M-4-plus
69.8/14.0/16.2
19.6/39.4/41.0
13,2/31.0/55..
1,/55.8
84.0/0.0/16.0
5.2/0.2/94.6
2.6/0.4997.0
Graph Edit Distance (Small)
Graph Edit Distance (Large)
GPT-4o
71.0/14.//4..4
35.0/49.2/15.8
12.4/30.8/56.8
94.6/1
49.6/18.28
14.2/3.8/62.
GPT-do-mini
57.2/12.2/30.6
30.2/37.8/322
10.6/28.4/6100
47.0008/52.2
29.4/10.2/60.4
25.4/3.0/71
Claude-3.5-some
72.2/12.6/15.2
41.0/43.2/55.8
13.0/33.6/33.4
82.470.8/16.8
52.4/13.2/34.4
35.6/5.4/59.0
Llama3-70b
69.6/14.8/15.6
41.2/30.0/28.8
10.6/32,0/57
80.0/0.8/19.2
41.8/10.6/47.
28,4/3.4/68.
Llama3-8b
14,2/5,2/80.6
10.8/6.2/83.0
3.0/7.2/89. 8
11.8/0.0/88.2
10.8/0.4/88.8
Qwen2.5-72h
64.0/10.0/26.0
37 2/33//3
11 0//2/3..6/54
20.8/0.2/79.0
14.0/3.2/82.5
10.8/1 8/87
Deepseek-v2
61.6/14.0/24.4
35.4/32.8/31.5
10.6/26 6/62.66
82.4/1.2/16.4
6/13.//411.
32.6/4.4/63.0
Mixtral-xx8b
37.8/12.4/49.8
07.6/21.4/61.0
6.0/11.482..
43. 93.6//1.255 6/1.2/55.
45.8/4
9.4/1.2/89.4
Gemma-7b
53.6/22.4/24.0
30.8/21 .0/4.22
3.6/6.4/90.0
1///334
/3.0/7.2/49.
25. 25.0/3.4/714
GLM-4-plus
72.2/16.0/11.8
38.0//6.8/15.2
14.2/28.6/57.2
94.0/0.8/5.2
52.0/21
87.6/6
Maximum Independent Set (Small)
Maximum Independent Set (Large)
GPT-4o
67.6/12.4/20.0
0.0163 8/36.2
2.2/64, 8/33.0
29.8/1.0/5 .0/69.2
0.0/5.4/94.6
0.4/8 0188.2/91.. .4
GPT-4o-mini
63.8/11.0/25.2
0.0/42.8/51
0.8/44.6/54.6
40.4/3.8/55.8
0.0/1.8/98.2
0.0/2.4/97.6
Claude-3.5
Sruude-3.5-somee
61.8/11.4/26.8
0.0/68.00 0/32.0
2/38.0/30.2
25.2//.0/73.8
0.0/7.8/92.2
0.8/8. ..8/8.8/904
1l0ma3-70b
02.4/21.4/16
0.0/36 8/63.2 .2
0.6/38.22 2/61.2
4/544
0.2/2.6/97.2
0.6/3.8/95.6
Llama3-8b
46.0/10.0/44.0
0.4/28.0/71.
1,4/29.2/69.4
14.2/0.4/85.4
0..9/.0//9.0
4//984
Qwen2.5-722
$2.0/21.8/26.2
0.0/3.8/66.2
0.6/5.0/94.4
39.0/4.2/56.
0.0/1.0/9..
0.4/1 8/97.8
Deepseek-v2
55.4/15.6/29.0
0.0/36.2/63.
1/8/37.4/61.. 8
12.2/0.66 2//22/66/87..
0.093.2/96.8
Mixtral-7x8b
44.0/16.2/39..
0.0/11 44
0.4/12.68 6/87./87..
28, 4/8.4/2.80 4/6888/88.8
0.2/0.8/99.0
0.6/0.6/98.8
Gemma-7h
26.6/5.6/67.8
0.0/21 2/78.
0.0/21 2/78./
6.000.094400
0.000.6/9944
0.0/0.6/99.4
GLM-4-plus
64.2/11.6/24.2
0.2/57 2/42..
2.2/58.8/39.0
34.450.4/65.2
0.0/3.8/96.2
0.6/5.4/94.0
Minimum Vertex Cover (Small)
Minimum Vertex Cover (Large)
GPT-4o
40.6/7.6/51.8
39 8/7 0/533
30.0/16.4/53
6/5536
19.0/1.2/79.8
13.6/2.6 13.6/2.6/83.8
12.0/3.8/8
D/3.8/84.2
GPT-4o-mini
34.6/3.2/62.2
27.4/8 2/64.4
25.4/9.6 9996666500
21.6/0.2/78.2
1..83.6/84..
11.4/6.2/82.4
Claude-3.5-sonnc
16.6/1.2/82.2
16.6/1 2/82.2
12.8/5.0 6/5.0/82.2
8.6/0.0/91.4
8.0/0.6/114
.A/L0/99..
1l0ma3-70h
41.006.0/530
40.077 A/52.6
32.0/14.4/53.
17.0/0.0/83.0
12.2/4.4/83..
2
Llama3-8b
38.8/966/51.
32.4/1 L8555,8
17.6/0.0/82.4
10.2/2.0/87.8
4/6.44
Qwen2.5-722
2.8/0.8/96.4
3.4/0.2/96.4
2.0/1. 6.9/6.6/96.4
1.6/0.0/9844
0.6/0.0/9944
0.6/0.0/99.4
Deepseek-v2
45.8/9.2/455 2/4.5
36.6/14.8/48.6
31 21.6/17.0/51.
29.01 8/69.2
10.6/8 4/81.
11.2/8.8/80.0
Mixtral-7x3b
28.2/11.4/604
15.4/20.4/6A
12,6/19.0/68, 4
21.2/0.8/78..
6.2/3.8/90.0
5.694.4/90.0
Gemma-7h
38.2/14.2/47.6
15.0/30.4/54.6
15.0/25.6/50
8/0.2/2//84.0
4.8/2.4/92.8
3.6/4.4/92.0
GI-M-4pllus
53.0/10.4/6666
31 31.2/20.4/8844
29.0/23.6/47.6
33.8/1 6//64.6
18.477.2/444
15.4/9.4/75.2
Table 6: Average accuracy (%) for three representative GNNs on Polynomial- and NP-complete problems across small and large graphs
Models
P (Small)
P (Large)
NP (Small)
NP (Large)
GIN
59.9
39.6
33.8
25.8
GAT
42.3
22.5
32.3
17.9
GSAGE
41.0
22.6
33.7
17.6
Tlude-3.5-sonner
82.2
58.7
47.8
7.2
20

---

Published as a conference paper at ICLR 2025
Table Performance comparison for different graph tokenizers on GPT-4o across tasks.
Tasks
Distance (Small)
Distance (Large)
TSP (Small)
TSP (Large)
Graph Tokenizer
Fea.
Hallu.
Acc.
Fea.
Hallu.
Acc.
Fea.
Hallu.
Acc.
Fea.
Hallu.
Acc.
Edge List
0.914
0,086
0.902
0.788
0.192
0.720
0.994
0.004
0.522
0.870
0.128
0.000
Adjacency List
0.898
0.102
0.894
0.808
0.166
0.774
0,990
0.006
0.288
0,918
0.082
0.000
Adjacency Matrix
0.842
0.158
0.780
0.546
0.436
0.448
0.940
0.058
0.318
0.806
0.012
0.016
Table 8: Performance comparison for GPT-4o on real-world and synthetic graphs.
Tasks
Neighbor (Small)
Neighbor (Large)
Distance (Small)
Distance (Large)
Graph Type
Fea.
Hallu.
Acc.
Fea.
Hallu.
Acc.
Fea.
Hallu.
Acc.
Fea.
Hallo.
Acc.
Real world Graphs
0.838
0.088
0.778
0.740
0.140
0.626
0.922
0.078
0.904
0.760
0.224
0.680
Erdös-Red Rényi Graphs
0.996
0.004
0,986
0.984
0.016
0.730
0.980
0.020
0.946
0.864
0.146
0.702
Claude-3.5-sonned
Deepseck-V2
GPT-4o
Llama3-8b
Qwen2.5-728
Hallucination Probability
1.04
MVC
Hallucination Probability
1.0
Neighbor
Hallucination Probability
1.0
Distance
Hallucination Probability
1.0
MCP
0.8
0.8
0.8
0.6-
0.6
0.6
0.4
0.4-
0.4
0.2
0.2
0.2-
0.2
0.0g
10 15 20
25
30
10
15
20
25
30
15
20
25
30
5
15 10
20
25
30
Graph Size
Gruph Size
Graph Size
Graph
Figure 9: The influence of graph size hallucination probability for the tasks of Distance, Neighbor, MCP, and MVC.
Claude-3 Claude-3.5ssonnel 5-sonnet
Deepseek-V2 V2
GPT-4o
Llama3-8b
Qwen2.5-722
MCS
TSP
GED
Hallucination Probubility
1.0
Hellucination Probability
1.0
Hallucination Probability
1.0
0.8-
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.0
0.0
0.0
10
15
20
5
10
15
20
10
15
20
Graph Size
Graph Size
Graph Size
Figure 10: The influence of graph size on hallucination probability for the tasks of GED, TSP, and MCS.
21

---

Published as a conference paper at ICLR 2025
Table 9: An example CoT prompting with step-by-step demonstrations on the Component task. CoT Prompts of the Connected Component Task. (1-shot)
You required to identify all connected components in the given social network and output one represen- tative node from each component.
Within a connected component, any node can reached from any other node through edges graph. Different connected components are isolated from each other.
**Exmpple**
Michelle Nelson, Kevin Brooks, Eric Davis, Toni Suarez, Teresa Hughes Friendship connections: Michelle Nelson to Teresa Hughes, Kevin Brooks to Eric Davis, Eric Davis to Toni Suarez
Names in the network:
The includes representative element from each connected component in the given social network: In this social network, we have the following names connections: Michelle Nelson, Kevin Brooks, Eric Davis, Toni Suarez, and Teresa Hughes. The connections are: Michelle Nelson to Teresa Hughes, Kevin Brooks to Eric Davis, and Eric Davis to Toni Suarez. From these connections, we can identify two isolated connected components. The first component includes Michelle Nelson and Teresa Hughes, and the second component includes Kevin Brooks, Eric Davis, and Toni Suarez. By selecting one representative node from each connected component, we have Teresa Hughes from the first component and Kevin Brooks from the second component. Therefore, the answer is [Teresa Hughes, Kevin Brooks].
**Problem to *
Names in the network: Michelle Nelson, Kevin Brooks, Eric Davis, Toni Suarez, Teresa Hughes Friendship connections: Michelle Nelson to Teresa Hughes, Kevin Brooks to Eric Davis, Eric Davis to Toni Suarez
Identify all connected components this network. Note that for each connected component, you should only output one of its nodes. Present your answer in the following format: [UserA, UserB, UserC, UserD, ...]
22

---

Published as a conference paper at ICLR 2025
Table 10: An example of CoT prompting with step-by-step demonstrations on the Diameter task. CoT Prompts the Graph Diameter Task. (I-shot)
You required calculate the diameter of an undirected knowledge graph.
The diameter a graph the maximum distance between any pair of nodes the graph. To compute this, you need to find the shortest path between all pairs of nodes and then determine the maximum length of these shortest paths.
"xxample**
Entities in this knowledge graph: SeincetMarne, MontereauFaall Vittorio De Sica, SaintFiacre SeineetMarne, France
The relationships between these entities follows: SeineetMarne is connected SaintFiacre Sei- via
neetMarne via the relationship department. SeineetMarne is connected MontereauFault relationship department. SeineetMarne connected to France via the relationship country. Montereau- Youne is connected to France via the relationship country. Vittorio De Sica is connected to France via the relationship deathPlace. SaintFiacre SeineetMarne connected to France via the relationship country.
To calculate the diameter this undirected knowledge graph, we first need to understand the connections and the structure of the graph. The entities and their relationships are as follows: SeineetMarne is connected to SaintFiacre SeineetMarne via the relationship 'department', Seineet is connected to MontereaulFuullymne via the relationship 'department', SeineetMarne is connected to France via the relationship "country', Montereaul Yonne connected to France via the relationship 'country', Vittorio De Sica is connected to France via the relationship 'deathPlace', and SaintFiacre SeinectMarne is connected to France via the relationship 'country'. The graph structure can be visualized as follows: SeineetMarne is connected SaintFiacre SeineetMarne, MontereauFaultYonnee and France. MontereauFault Yonne also connected to France, and France is connected Vittorio De Sica.
and SaintFiacre SeineetMarne By analyzing the shortest paths between pairs of nodes, we find that SeincerMaree to SaintFiacre SeineetMarne, SeincetMarne to MontercauFault Yonne, SeineetMame to France, MontercauFault Yonne to France, SaintFiacre MeineetMarne to France, and France to Vittorio De Sica all have direct connection with edge. The longest shortest paths are from SeineetMarne, MontereauFaull Yonne, and SaintFiacre SeineetMarne to Vittorio De Sica via France, each with 2 edges. Therefore, the diameter of this knowledge graph is 2, and one the paths that represent this diameter is [SeineetMarne, France, Vittorio De Sica).
* *Problem to *
Entities this knowledge graph: PlayStation Buzz! Junior: Jungle Party, Tekken (video game). Buzz!, PlayStation Network
The relationships between these entities are as follows:
PlayStation 2 is connected Tekken (video game) via the relationship computingPlatform. PlayStation is connected to Buzz! Junior: Jungle Party via the relationship computingPlatiorm. Buzz! Junior: Jungle Party is connected to Buzz! via the relationship series. Buzz! Junior: Jungle Party connected to PlayStation Network via the relationship computingPlatform. Tekken (video game) is connected to PlaySttaionn Network via the relationship computingPlatform.
Please determine the diameter network and output the corresponding path in following format:
[Entityl. I, Entity2.... .... EntityN].
23

---

Published as a conference paper at ICLR 2025
Table 11: An example of the Common Neighbor task.
Prompts of the Common Neighbor Task. (1-shot)
Your task is find the common neighbors of two nodes in an undirected academic network. In this network, nodes represent authors and edges represent research collaborations.
**Example**
Authors in the network: Manii-Francine Moens, Stefanie Brüninghaus, Henry Prakken, David W. Aha,
Kevin D. Ashley. Ronald Prescott Loui
Research collaborations between these authors: Marie-Francine Moens and Kevin D. Ashley, Marie- Francine Mocns and Stefanic Brüninghaus, Stefanic Brüninghaus and David W. Aha, Stefamic Brüninghaus and Henry Prakken, Stefanie Brüninghaus and Kevin D. Ashley, Stefanic Bräninghaus and Ronald Prescott Loui, Henry Prakken and Kevin D. Ashley, Henry Prakken and Ronald Prescott Loui, David W. Aha and Kevin Ashley, Kevin Ashley Ronald Prescot Loui. Common neighbors between Marie-Francine Moens and Stefanie Brüninghaus: [Kevin D. Ashley] **Problem to *olve
Authors in the network: Sang Lee, Hyoyoung Jang. Zenn Bien, Zeungnam Bien Research collaborations between these authors: Sang Wan Lee and Zeungnam Bien, Sang Wan Lee and Z. Zenn Bien, Sang Wan Lee and Hyoyoung Jang, Hyoyoung Jang and Zeungnam Bien, 7. Zenn Bien and Zeungnam Bien.
Please identify the common neighbors Sang Wan Lee and Hyoyoung Jang in this network. Present your answer in the following format: [AuthorA, AuthorB, AuthorC, AuthorD,...]
Table 12: An example of the Shortest Distance task.
Prompts of the Shortest Distance Task. (I-shot)
Your task is to identify the shortest path between two specified entities in an undirected knowledge graph, minimizing the number of hops.
**Exmplee**
Entities in this knowledge graph: Chordata, Animalia, Sloggett's vlei rat, Mammalia The relationships between these entities follows: Chordata connected Sloggett's 's vlei vlei rat via the relationship kingdom. Sloggett's vlei rat is connected to Mammalia via the relationship class.
relationship phylum. Animalia is connected to Sloggett's
One shortest path between Animalia and Sloggett's vlei rat is: [Animalia, Sloggett's vlei rat]
**Problem to *
Entities in this knowledge graph: United States, Post-hardcore, Head Wound City, Texas, Cody Votolato The relationships between these entitics United States connected Texas via the relationship country. United States is connected Cody Votolato via the relationship birthPlace. Post-hardcore is connected to Cody Votolato via the relationship genre. Head Wound City is connected to Cody Votolato via the relationship associatedMusicalAriii Texas connected to Cody Votolato via the relationship birthplace.
follows:
Please determine the shortest path between Texas and United States this Ketwork.Submi your answer in the format: [Entity I, Entity2.... .... EntityN], where Entityl and EntityN are the specified start and end entities, and Entity2 through EntityN-1 I are the intermediate entities on the shortest path.
24

---

Published as a conference paper at ICLR 2025
Table 13; An example of the Graph Edit Distance task.
Prompts of the GED Task. (1-shot)
You required to solve the Graph Edit Distance problem between molecules. Each edit operation (adding or deleting edge, adding or deleting an isolated node, or relabeling node) has an identity cost. Your objective to establish mapping between the atom IDs from Molecule A to Molecule B, ensuring that each ator ID in Molecule A corresponds to exactly one atom ID in Molecule B. The mapping corresponds the minimum edit cost between the two graphs.
** "Example**
Molecule A:
Atoms: N (atom 0), (atom 1), Si (atom 2), O (atom 3), O (atom 4).
Bonds: 0-1, 1-2, 2-3, 2-4.
Molecule B:
Atoms: F (atom 0). B (atom I), C (atom 2). N (atom 3), Br (atom 4).
Bonds: 0-1, 1-2, 1-4, 2-3.
One optimal node mapping: [3, 2, 1, 4].
Psorolemm to Solve*
You given the following molecules:
Molecule A:
Atoms: N (atom 0), C (atom 1), N (atom 2). F (atom 3).
Bonds; 0-1, 1-2, 1-3.
Molecule
Atoms: O (atom 0), C. (atom 1), F (atom 2), (atom 3).
Bonds: 0-1, 1-2, 1-3.
Represent the node mapping list of integers, where the position in the list corresponds the atom ID Molecule and the value at that position indicates the corresponding atom in Molecule B.
For instance, if atom O in Molecule A corresponds to atom in Molecule B, atom I in Molecule A corresponds atom in Moleculc B, and atom 2 remains unchanged, the mapping would be represented [1, 0, ...l.
25

---

Published as a conference paper at ICLR 2025
Table 14: An example of the Maximum Clique Problem.
Prompts of the MCP Task. (1-shot)
You are required to solve the Maximum Clique Problem for an undirected academic network. In this network, nodes represent authors and edges represent research collaborations. Your objective is find the largest subset nodes such that every pair of vertices in this subset connected by an edge.
"Example**
Authors in the network: Keng Peng Tee, Veit Hagenmeyer, Bartosz Käpernick, Karl Henrik Johansson, Darryl DeHaan, James B. Rawlings, Andreas Kugi, Knut Graichen, Tilman Utz, Christian Ebenbauer. Research collaborations between these authors: Keng Peng Tee and James B. Rawlings, Keng Peng Tee and Darryl DeHaan, Veit Hagenmeyer and Knut Graichen, Bartosz Käpernick and Andreas Kugi, Bartosz Käpernick and Knut Graichen, Karl Henrik Johansson and Christian Ebenbauer, Darryl DeHaan and Knut Graichen, Darryl DeHaan and Christian Ebenbauer. James B. Rawlings and Knut Graichen, James B. Rawlings and Christian Ebenbauer, Andreas Kugi and Knut Graichen, Knut Graichen and Tilman Utz. One Maximum Clique: [Knut Graichen, Bartosz Käpernick, Andreas Kugi].
**Problem to $o
Authors in the network: Manfred Schmidt-Schaus. David Sabel, Manfred Schmidt-Schauß, Guillem Godoy.
Research collaborations between these authors: Manfred Selmidt-Schausse and David Sabel, Manfred
Schmidt- Seanidt-Schhuss and Manfred Schmidt-Schall Manfred Schmidt- Sammitt-Schauss Guillem Godoy, David Sabel and Manfred Schaid, Manfred Schmidt-Schaur and Guillem Godoy.
Identify the clique with the maximum number of authors in this network. Present your answer in the following format: [AuthorA, AuthorB, AuthorC, AuthorD, ...].
Table 15: An example of the Maximum Common Subgraph Task. Prompts of the MCS Task. (I-shot)
You are required to solve the Maximum Common Subgraph problem. Your goal identify the common subgraph with the maximum number of atoms shared between the two molecules.
*Example***
Molecule A consists of 8 atoms with the following 9 bonds: 0-1, 0-6, 1-2, 1-2, 3-4, 3-7, 4-5, 5-6, 5-7. Molecule B consists of 7 atoms with the following bonds: 0-1, 1-2, 1-4, 2-3, 3-, 3-6, One max common subgraph: [2, 3, 4, 7, 6), [0. 2, 6].
**Problem to *
You given the following two molecules:
Molecule A consists of atoms with the following bonds: 0-1, 1-2, 2-3. Molecule consists of 4 atoms with the following bonds: 0-1, 1-2. 1-3.
Provide the indices of the atoms in the common subgraph for each molecule in the following format: [Node indices in molecular AJ, [Node indices in molecular BJ.
For example, if the common subgraph the subgraph of atom 1, 2, in molecule and the subgrah of atom 2, 3, in molecule B, you should answer: [1, 2, 31, 12, 3, 4).
26

---

Published as a conference paper at ICLR 2025
Table 16: An example of the Maximum Independent Set task.
Prompts of the MIS Task. (1-shot)
Your task is to solve Maximum Independent problem the given social network. this network, each node represents a user, and each edge represents a friendship connection. You need to identify the largest subset of users such that no two users in this subset are friends connected by an edge.
** "Exxmmpl***
Users in the network: Melinda Vaughan, Mary Thornton, Jeremiah Griffith, Lisa Anderson, Alfred Powell. Fiendship connections: Melinda Vaughan and Jeremiah Griffith, Mary Thornton and Jeremiah Griffith, Jeremiah Griflith and Lisa Anderson, Jeremiah Griffith and Alfred Powell. One Maximum Independent Set: [Melinda Vaughan, Lisa Anderson, Alfred Powell, Mary Thornton].
**Problem to *
Users in the network: William Lawson, Daniel Shelton, Michelle Lewis, Julie Hayes. Friendship connections: William Lawson and Daniel Shelton, William Lawson and Julie Hayes, Michelle Lewis and Julie Hayes.
Identify the Maximum Independent Set of this network and present your answer in the following format: [UserA, UserB, UserC, UserD,...] ...].
Table 17: An example of the Minimum Vertex Cover task.
Prompts of the MVC Task. (1-shot)
Your task is to solve the Minimum Vertex Cover problem in the given social network. In this network, each node represents user, and each edge represents a friendship connection. You need to identify the smallest subset of users such that every friendship connection has at least one user from this subset.
** **xample***
Users in the network: Julie Harris. David Torres. Vanessa Parker, Shawn Barnett, Karl Dean. Fiendship connections: Julie Harris and Vanessa Parker, Julie Harris and David Torres, Julie Harris and Shawn Barnett, Julie Harris and Karl Dean, David Torres and Vanessa Parker, David Torres and Shawn Barnett, David Torres and Karl Dean, Vanessa Parker and Shawn Barett, Shawn Barnett and Karl Dean. One Minimum Vertex Cover: [Julie Harris, David Torres, Shawn Barnett].
** **Problem to *
Users in the network: Pamela Haynes, Kyle Mcadows, Adam Nichols, Anna Lowery, Heather Dixon, Matthew Lee, Elizabeth Wood, Stephen Hess.
Friendship connections: Pamela Haynes and Stephen Hess, Kyle Meadows and Matthew Lee, Kyle Meadows and Stephen Hess, Kyle Meadows and Adam Nichols, Adam Nichols and Stephen Hess, Adam Nichols and Heather Dixon, Anna Lowery and Stephen Hess, Heather Dixon and Stephen Hess, Matthew Lee and Stephen Hess, Elizabeth Wood and Stephen Hess.
Identify the Minimum Vertex Cover of this network and present your answer in the following format: [UserA, UserB, UserC, .....
27

---

Published as a conference paper at ICLR 2025
Table 18: An example of the Traveling Salesman Problem.
Prompts of the TSP Task. (1-shot)
You are required to solve the Traveling 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.
* *Example**
Airports to visit: VPY, AAE, BGA, YWB.
Travel distances (in kilometers) between each pair of airports:
VPY YWB: 16285; VPY AAE: 9488; VPY BGA: 13255; AAE YWB: 7807; AAE BGA: 9332; BGA to YWB: 6575.
One shortest route: [VPY, AAE, YWB, BGA, VPYJ.
**Problem to So
Airports to visit: YNT, TEB, CFC, VIE, NSH, ROV.
Travel distances (in kilometers) between each pair of airports:
YNT to VIE: 7962; YNT to ROV: 6644; YNT to NSH: 6176: YNT to CFC: 18668; YNT to TEB: 12263;
TEB to VIE: 6987; TEB ROV: 8529; TEB NSH: 10389; TEB CFC: 8846; CFC to VIE: 10716;
CFC to ROV: 12244: CFC to NSH: 13193; to ROV: 1736; to NSH: 3406; NSH to ROV: 3000.
Please calculate the shortest tour and format your answer follows: [Airport A, Airport B, Airport C....
Airport A]
Identify the Minimum Vertex Cover of this network and present your answer in the following format: [UserA, UserB, UserC, .........].
28


Reviews:
[{"review_id": "4vXassxPoK", "reviewer": "Reviewer_Mrvi", "summary": "The paper introduces GraphArena, a benchmarking tool designed to evaluate LLMs on graph computation tasks.\nIt includes ten LLMs with polynomial-time and NP-complete graph problems. The authors claim to go beyond existing benchmarks by including real-world graph structures, introducing path-based evaluation criteria, and testing various improving-performance methods.", "questions": "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?\n2. How are the polynomial-time and NP-complete tasks chosen, and do they represent a balanced challenge across diverse graph properties (e.g., density, connectivity)?\n3. When using code generation to solve graph problems, how is the correctness of the generated code verified?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. It includes a diverse set of graph tasks, ranging from simple to complex. It provides a useful evaluation tool for understanding the reasoning capabilities of LLMs on graph problems.\n2. It also includes real-world graphs, which can help evaluate the models' performance on practical applications.\n3. The paper compares LLMs with traditional graph algorithms, providing insights into the strengths and weaknesses of LLMs in graph computation tasks.", "weaknesses": "1. The analysis is surface-level and lacks in-depth insights into the models' reasoning capabilities. I also have questions about the selected tasks, such as why these specific tasks are chosen and how they represent real-world applications.\n2. While the authors position GraphArena as an improvement over previous benchmarks, the degree of novelty in terms of task design and dataset is somewhat unclear. Could the authors provide a more detailed comparison with existing benchmarks?\n3. The definition of small/large graphs are different across tasks, which might introduce inconsistencies in the evaluation. It would be helpful to standardize the graph sizes for a fair comparison across tasks.\n4. For the evaluation metrics (Feasibility, Hallucination...), there is no clear explanation of how these metrics are calculated. \n5. The authors introduce System 1 and System 2 thinking to describe task complexity, but the connection is weak and lacks follow-through. This framing feels more like an afterthought without a clear motivation and in-depth analysis in the later sections.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "13GlLs9Hjr", "reviewer": "Reviewer_H9rP", "summary": "- The paper introduces GraphArena, a LLM benchmark for measuring graph reasoning. \n    - GraphArena is based on real world graphs, including knowledge graphs, social networks, and molecular structures\n    - The tasks constructed on these graphs capture a spectrum of different reasoning skills\n    - The authors introduce a path-specific evaluation methodology which allows for finegrained measurement of LLM responses\n- In addition to describing GraphArea, the paper compares the performance of different LLMs to a broad range of graph-based methods. \n- Finally, the authors explore a range of strategies to improve performance on GraphArea (finetuning, prompting, scaling test time compute).", "questions": "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.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- I think the benchmark is extremely well constructed. \n    - It is based on realistic data\n    - It has a spectrum of difficulty, so different researchers may focus on different subsets of samples/tasks based on the types of models they are studying\n    - Similarly, the evaluation protocol applied make sense, and section 2.3 does a good job of motivating it.\n- The experiments are rigorous and comprehensive. I think the exploration of methods for improving performance is well-done and rounds out the paper nicely.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "E7382B8EfE", "reviewer": "Reviewer_jb83", "summary": "This paper introduces GraphArena, a benchmark designed to evaluate large language models (LLMs) on a range of classical polynomial-time and NP-complete graph algorithms. GraphArena consists of four polynomial-time tasks and six NP-complete problems set on real-world graphs sampled from various domains.\nGraphArena categorizes LLM responses as correct, suboptimal, hallucinatory, or missing, and ranks overall model performance using mean reciprocal rank (MRR), top-1, and top-3 probability. The authors evaluate over ten LLMs on GraphArena and show that current SOTA models display significant limitations on the included graph reasoning tasks, especially on larger graphs. The study further examines four strategies to improve LLMs' graph reasoning abilities: chain-of-thought prompting, instruction tuning, code generation, and scaling test-time compute. Each approach yields improvements; fine-tuning models yields particularly significant improvements in accuracy, feasibility, and reducing hallucinations on both P and NP tasks for both small and large graphs.\nThis benchmark highlights the gap between current LLM capabilities and the demands of complex graph reasoning tasks, and contributes insight into the current understanding of LLMs' limitations and potential in graph-based reasoning.", "questions": "- In the appendix, several prompts are shown in which the size of the graph problem presented for CoT reasoning is larger than the query problem. How did you decide on the size of graph problem to use in CoT? Is it standard across all CoT prompts? If it was tuned, please describe the process\n- Is there further analysis of the types of errors that LLMs are prone to on this benchmark?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "The paper provides several NP-Complete algorithmic reasoning tasks: MCP, MIS, MVC, MCS, GED, and TSP, which are a novel inclusion in the space of benchmarking LLM performance on graph reasoning. The selected P and NP tasks offer a representative sample of graph reasoning operations. The paper does a great job of providing clear experimental results and thorough evaluation of the models on the included tasks. While the study is not the first to evaluate LLMs on real-world graph datasets, there is novelty in evaluating LLMs on complex reasoning tasks on real world graphs, especially with additional textual features.\n\nWhen considering the lack of breadth available in the peer-reviewed literature of benchmarks evaluating LLM performance on graphs published before July, this work provides novel insights into the SOTA algorithmic reasoning performance.", "weaknesses": "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. 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).\n\nClaim 3: The tasks in this benchmark seem to be structured as Input-Output (IO) problems. There is limited novelty in showing that fine-tuning improves reasoning improves performance on IO tasks, as shown in “Specializing smaller language models towards multistep reasoning” (Fu et al. 2023) and other prior works. The claim of “improving graph problem-solving” should be reduced unless the authors plan to provide additional experiments with other open-source LLMs that showcase novel findings, or can provide adequate justification for this claim.\n\nRigorous Path-based Evaluation: The authors mention they contribute a “rigorous, path-based evaluation”, but appear to be performing exact match accuracy and then a partial accuracy metric and integrated error analysis (Missing and Hallucination). These methods are used in “Can Language Models Solve Graph Problems in Natural Language?” (Wang et al. 2023). Multiple prior methods have required models to output a listing or mapping of node IDs as a response to a query, namely “Evaluating Large Language Models on Graphs: Performance Insights and Comparative Analysis” (Liu and Wu 2023), \"Can Graph Descriptive Order Affect Solving Graph Problems with LLMs?\" (Ge et al. 2024), and Wang et al. 2023 on shortest path queries.\n\nI would be willing to raise my score if the above issues are addressed.\n\nMinor Weaknesses:\n- Inclusion of synthetic graph results for the top performing LLMs would strengthen the claim that prior benchmarks fail to adequately stress test LLMs with diverse graphs\n- The paper should mention the strong likelihood of the real-world graph datasets being included in the pre-training datasets of many (if not all) of the models being evaluated.\n- 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 in the camera-ready version, as these papers cover a significant breadth of graph algorithmic reasoning tasks and methods for improving LLM algorithmic reasoning.\n- Table 2 has several misleading bold results:\n  - Lines 439-440: Qwen2-7b should be bolded for feasibility in NP small graphs\n  - Lines 441-442: GPT-4o-Coder should be bolded for Polynomial large graphs\n  - Lines 443-444: DeepSeek-V2 base should have bold text for accuracy in NP small graphs and feasibility in NP large graphs\n- Figure 6 reference links to figure 5 for some reason\n- The paper would benefit from providing a centralized list of all models evaluated and their settings, including any hyperparameter tuning", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Kspy9pTT7d", "reviewer": "Reviewer_8N9w", "summary": "The paper presents GraphArena, a benchmarking tool for evaluating LLMs on graph computational problems. GraphArena includes polynomial-time and NP-complete tasks and a detailed evaluation framework. The study tested over ten LLMs on 10,000 problems, finding that models often struggle with complex graphs and exhibit hallucination. It also explores some solutions: chain-of-thought prompting, instruction tuning, code writing, and scaling test-time compute.", "questions": "Q1: It is unclear how testing LLMs on graph computational problems is a good way to assess reasoning capabilities (L48). How is reasoning capability defined?\n\nQ2: What do \"intuitive thinking\" and \"conscious thinking\" mean for an LLM (L64)?\n\nQ3: What are these templates? (L214) Are graphs always encoded as an edge list (figure 1)? Can one use adjacency list or adjacency matrix to represent a graph in text?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1: It's great to see that GraphArena includes diverse real-life datasets, addressing the limitation of benchmarks that only use synthesized graphs.\n\nS2: The evaluation study is thorough, covering a broad spectrum of LLMs. The techniques proposed to enhance task performance are intriguing, and the results are valuable to the community.\n\nS3: The paper is well-written and easy to read.", "weaknesses": "### Major weaknesses\n\nW1: The discussion and motivation can be improved. This paper presents a useful and sound benchmark and conducts a comprehensive analysis, but 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?\n\nW2: 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?\n\nW3: 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 (2) providing a stronger rationale for using LLMs to solve these tasks over traditional graph algorithms.\n\n### Minor weaknesses\n\nM1: The many green boxes in the introduction makes this section hard to read. I recommend disabling the box highlighting or reducing citing redundant papers. For example \"(Li et al., 2023c; Jin et al., 2023; Perozzi et al., 2024; Wang et al., 2023; Chen et al., 2024b).\" => \"(e.g., Li et al., 2023c; Jin et al., 2023; Perozzi et al., 2024).\"\n\nM2: Figure 6 comes before Figure 5.\n\nM3: It is rather confusing to have SFT and coder in the same table, while COT and test-time compute in other different figures.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)