Rethinking and Benchmarking Large Language Models for Graph Reasoning
This work addresses the need for better evaluation of LLMs in graph reasoning, which is important for researchers and practitioners in AI and graph analysis, though it is incremental in improving benchmarks and baselines.
The authors tackled the problem of evaluating large language models (LLMs) for graph reasoning by identifying issues with existing methods and benchmarks, and they constructed a more challenging benchmark called GraphAlgorithm with 239 problems and 3,041 test instances. They introduced a baseline method, Simple-RTC, which achieved near-perfect accuracy on existing benchmarks and significantly outperformed prior methods on GraphAlgorithm.
Large Language Models (LLMs) for Graph Reasoning have been extensively studied over the past two years, involving enabling LLMs to understand graph structures and reason on graphs to solve various graph problems, with graph algorithm problems being the most prevalent. Recent studies underscore the potential of LLMs in handling graph reasoning tasks, but their performance is underwhelming. In this work, we point out issues with existing methods and benchmarks, and rethink the direction that LLMs for graph reasoning should strive toward. We find that base models, e.g., GPT-4o-mini, are largely underestimated due to improper reasoning focus. Base models with reasoning focus redirected from replicating graph algorithms to designing them can easily solve most graph reasoning tasks in existing benchmarks. To truly evaluate the graph reasoning capabilities of LLMs, we construct a more challenging GraphAlgorithm benchmark, comprising 239 different graph problems and 3,041 test instances collected from 4 competition platforms. Finally, we introduce a simple and strong baseline Simple-Reasoning-Then-Coding (Simple-RTC)-which guides LLMs to design graph algorithms first and then code to address graph reasoning tasks. Simple-RTC achieves near-perfect accuracy on existing benchmarks and significantly outperforms GPT-4o-mini and all prior methods on the GraphAlgorithm benchmark. This strong baseline encourages further advancements in LLMs for Graph Reasoning in the future.