# GraphEval36K: Benchmarking Coding and Reasoning Capabilities of Large Language Models on Graph Datasets

arXiv: https://arxiv.org/abs/2406.16176 · HTML: https://mlsanity.com/paper/2406.16176/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 28 of its 71 references that are in the map.
- First posted on arXiv 23 Jun 2024.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 28 of 28)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context](https://mlsanity.com/paper/2403.05530/) (2024)
- [Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models](https://mlsanity.com/paper/2206.04615/) (2022)
- [Mixtral of Experts](https://mlsanity.com/paper/2401.04088/) (2024)
- [Gemini: A Family of Highly Capable Multimodal Models](https://mlsanity.com/paper/2312.11805/) (2023)
- [Selection-Inference: Exploiting Large Language Models for Interpretable Logical Reasoning](https://mlsanity.com/paper/2205.09712/) (2022)
- [ProofWriter: Generating Implications, Proofs, and Abductive Statements over Natural Language](https://mlsanity.com/paper/2012.13048/) (2020)
- [Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph](https://mlsanity.com/paper/2307.07697/) (2023)
- [GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking](https://mlsanity.com/paper/2305.15066/) (2023)
- [Large Language Models on Graphs: A Comprehensive Survey](https://mlsanity.com/paper/2312.02783/) (2023)
- [Talk like a Graph: Encoding Graphs for Large Language Models](https://mlsanity.com/paper/2310.04560/) (2023)
- [Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs](https://mlsanity.com/paper/2404.07103/) (2024)
- [GraphLLM: Boosting Graph Reasoning Ability of Large Language Model](https://mlsanity.com/paper/2310.05845/) (2023)
- [Graph Prompt Learning: A Comprehensive Survey and Beyond](https://mlsanity.com/paper/2311.16534/) (2023)
- [LLM4DyG: Can Large Language Models Solve Spatial-Temporal Problems on Dynamic Graphs?](https://mlsanity.com/paper/2310.17110/) (2023)
- [CodeScope: An Execution-based Multilingual Multitask Multidimensional Benchmark for Evaluating LLMs on Code Understanding and Generation](https://mlsanity.com/paper/2311.08588/) (2023)
- [Evaluating Large Language Models on Graphs: Performance Insights and Comparative Analysis](https://mlsanity.com/paper/2308.11224/) (2023)
- [Large Language Models Are Neurosymbolic Reasoners](https://mlsanity.com/paper/2401.09334/) (2024)
- [SymbolicAI: A framework for logic-based approaches combining generative models and solvers](https://mlsanity.com/paper/2402.00854/) (2024)
- [Leveraging Print Debugging to Improve Code Generation in Large Language Models](https://mlsanity.com/paper/2401.05319/) (2024)
- [Comparing large language models and human programmers for generating programming code](https://mlsanity.com/paper/2403.00894/) (2024)
- [CoRRPUS: Code-based Structured Prompting for Neurosymbolic Story Understanding](https://mlsanity.com/paper/2212.10754/) (2022)
- [Hybrid Graph: A Unified Graph Representation with Datasets and Benchmarks for Complex Graphs](https://mlsanity.com/paper/2306.05108/) (2023)

## Built on by (most cited first, 12 of 12)

- [GraphInsight: Unlocking Insights in Large Language Models for Graph Structure Understanding](https://mlsanity.com/paper/2409.03258/) (2024)
- [G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning](https://mlsanity.com/paper/2505.18499/) (2025)
- [GCoder: Improving Large Language Model for Generalized Graph Problem Solving](https://mlsanity.com/paper/2410.19084/) (2024)
- [Graph Linearization Methods for Reasoning on Graphs with Large Language Models](https://mlsanity.com/paper/2410.19494/) (2024)
- [New Bounds for Zarankiewicz Numbers via Reinforced LLM Evolutionary Search](https://mlsanity.com/paper/2605.01120/) (2026)
- [S-Path-RAG: Semantic-Aware Shortest-Path Retrieval Augmented Generation for Multi-Hop Knowledge Graph Question Answering](https://mlsanity.com/paper/2603.23512/) (2026)
- [Evaluating Relational Reasoning in LLMs with REL](https://mlsanity.com/paper/2604.12176/) (2026)
- [Improving LLMs' Generalized Reasoning Abilities by Graph Problems](https://mlsanity.com/paper/2507.17168/) (2025)
- [Zero-shot Graph Reasoning via Retrieval Augmented Framework with LLMs](https://mlsanity.com/paper/2509.12743/) (2025)
- [Learning Multimodal Embeddings for Traffic Accident Prediction and Causal Estimation](https://mlsanity.com/paper/2512.02920/) (2025)
- [Graph Evidence Is Not Enough: Diagnosing Native Decoder Use in Graph-Augmented LLMs](https://mlsanity.com/paper/2608.30437/) (2026)
- [GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs](https://mlsanity.com/paper/2609.12265/) (2026)

## Abstract (arXiv)

Large language models (LLMs) have achieved remarkable success in natural language processing (NLP), demonstrating significant capabilities in processing and understanding text data. However, recent studies have identified limitations in LLMs' ability to manipulate, program, and reason about structured data, especially graphs. We introduce GraphEval36K, the first comprehensive graph dataset, comprising 40 graph coding problems and 36,900 test cases to evaluate the ability of LLMs on graph problem-solving. Our dataset is categorized into eight primary and four sub-categories to ensure a thorough evaluation across different types of graphs. We benchmark ten LLMs, finding that private models outperform open-source ones, though the gap is narrowing. We also analyze the performance of LLMs across directed vs undirected graphs, different kinds of graph concepts, and network models. Furthermore, to improve the usability of our evaluation framework, we propose Structured Symbolic Decomposition (SSD), an instruction-based method designed to enhance LLM performance on complex graph tasks. Results show that SSD improves the average passing rate of GPT-4, GPT-4o, Gemini-Pro and Claude-3-Sonnet by 8.38%, 6.78%, 29.28% and 25.28%, respectively.