  The "arms race" of Large Language Models (LLMs) demands novel, challenging,
and diverse benchmarks to faithfully examine their progresses. We introduce
GraphArena, a benchmarking tool designed to evaluate LLMs on graph
computational problems using million-scale real-world graphs from diverse
scenarios such as knowledge graphs, social networks, and molecular structures.
GraphArena offers a suite of 10 computational tasks, encompassing four
polynomial-time (e.g., Shortest Distance) and six NP-complete challenges (e.g.,
Travelling Salesman Problem). It features a rigorous evaluation framework that
classifies LLM outputs as correct, suboptimal (feasible but not optimal), or
hallucinatory (properly formatted but infeasible). Evaluation of 10 leading
LLMs, including GPT-4o and LLaMA3-70B-Instruct, reveals that even
top-performing models struggle with larger, more complex graph problems and
exhibit hallucination issues. Despite the application of strategies such as
chain-of-thought prompting, these issues remain unresolved. GraphArena
contributes a valuable supplement to the existing LLM benchmarks and is
open-sourced at https://github.com/squareRoot3/GraphArena.
