GraphArena: Benchmarking Large Language Models on Graph Computational Problems
<|reference_start|>GraphArena: Benchmarking Large Language Models on Graph Computational Problems: 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.<|reference_end|>
@article{tang2024grapharena:,
    title={GraphArena: Benchmarking Large Language Models on Graph Computational
  Problems},
    author={Jianheng Tang, Qifan Zhang, Yuhan Li, Jia Li},
    journal={arXiv preprint arXiv:2407.00379},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.00379},
    primaryClass={cs.AI cs.CL}
}