mlsanityData to 7 Oct 2026

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

arXiv 2406.16176 ↗First posted 23 Jun 2024cs.AI cs.CL cs.LGcited by 12

On the map: LLM reasoning → Knowledge- and tool-augmented reasoning

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.

Key facts. Cited by 12 papers in the map (data through 7 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.

Builds on

28 of 71 references.

Closest ancestors · 3

Same direction, newest first

  1. 2024Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs10 Apr
  2. 2023GraphLLM: Boosting Graph Reasoning Ability of Large Language Model9 Oct
  3. 2023Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph15 Jul

Other references · 25

  1. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  2. 2023GPT-4 Technical Reportcited by 18,132
  3. 2019RoBERTa: A Robustly Optimized BERT Pretraining Approachcited by 13,266
  4. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 12,865
  5. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  6. 2021Evaluating Large Language Models Trained on Codecited by 8,053
  7. 2024Gemini 1.5: Unlocking multimodal understanding across millions of tokens of contextcited by 3,175
  8. 2022Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language modelscited by 1,970
  9. 2024Mixtral of Expertscited by 1,785
  10. 2023Gemini: A Family of Highly Capable Multimodal Modelscited by 810
  11. 2022Selection-Inference: Exploiting Large Language Models for Interpretable Logical Reasoningcited by 331
  12. 2020ProofWriter: Generating Implications, Proofs, and Abductive Statements over Natural Languagecited by 309
13 more
  1. 2023GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarkingcited by 209
  2. 2023Large Language Models on Graphs: A Comprehensive Surveycited by 190
  3. 2023Talk like a Graph: Encoding Graphs for Large Language Modelscited by 175
  4. 2023Graph Prompt Learning: A Comprehensive Survey and Beyondcited by 61
  5. 2023LLM4DyG: Can Large Language Models Solve Spatial-Temporal Problems on Dynamic Graphs?cited by 40
  6. 2023CodeScope: An Execution-based Multilingual Multitask Multidimensional Benchmark for Evaluating LLMs on Code Understanding and Generationcited by 39
  7. 2023Evaluating Large Language Models on Graphs: Performance Insights and Comparative Analysiscited by 35
  8. 2024Large Language Models Are Neurosymbolic Reasonerscited by 31
  9. 2024Leveraging Print Debugging to Improve Code Generation in Large Language Modelscited by 15
  10. 2024SymbolicAI: A framework for logic-based approaches combining generative models and solverscited by 15
  11. 2024Comparing large language models and human programmers for generating programming codecited by 9
  12. 2022CoRRPUS: Code-based Structured Prompting for Neurosymbolic Story Understandingcited by 7
  13. 2023Hybrid Graph: A Unified Graph Representation with Datasets and Benchmarks for Complex Graphscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 4; 2026: 5.

12 papers.

  1. 2024GraphInsight: Unlocking Insights in Large Language Models for Graph Structure Understandingcited by 18
  2. 2025G1: Teaching LLMs to Reason on Graphs with Reinforcement Learningcited by 14
  3. 2024GCoder: Improving Large Language Model for Generalized Graph Problem Solvingcited by 11
  4. 2024Graph Linearization Methods for Reasoning on Graphs with Large Language Modelscited by 5
  5. 2026New Bounds for Zarankiewicz Numbers via Reinforced LLM Evolutionary Searchcited by 4
  6. 2026S-Path-RAG: Semantic-Aware Shortest-Path Retrieval Augmented Generation for Multi-Hop Knowledge Graph Question Answeringcited by 3
  7. 2026Evaluating Relational Reasoning in LLMs with RELcited by 2
  8. 2025Improving LLMs' Generalized Reasoning Abilities by Graph Problemscited by 1
  9. 2025Zero-shot Graph Reasoning via Retrieval Augmented Framework with LLMscited by 1
  10. 2025Learning Multimodal Embeddings for Traffic Accident Prediction and Causal Estimationcited by 0
  11. 2026Graph Evidence Is Not Enough: Diagnosing Native Decoder Use in Graph-Augmented LLMscited by 0
  12. 2026GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Exploring Graph Learning Tasks with Pure LLMs: A Comprehensive Benchmark and Investigation
  2. 2026Evaluating LLMs on Large-Scale Graph Property Estimation via Random Walks
  3. 2024GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability
  4. 2025Rethinking and Benchmarking Large Language Models for Graph Reasoning
  5. 2026Are Large Language Models Suitable for Graph Computation? Progress and Prospects
  6. 2024GUNDAM: Aligning Large Language Models with Graph Understanding
  7. 2026Teaching LLMs to See Graphs: Unifying Text and Structural Reasoning
  8. 2026Unified Multi-Dimensional Benchmark for Complex Graph Reasoning in Large Language Models