mlsanityData to 7 Oct 2026

GraCoRe: Benchmarking Graph Comprehension and Complex Reasoning in Large Language Models

arXiv 2407.02936 ↗First posted 3 Jul 2024cs.AI cs.CLcited by 13

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

Abstract (arXiv)

Evaluating the graph comprehension and reasoning abilities of Large Language Models (LLMs) is challenging and often incomplete. Existing benchmarks focus primarily on pure graph understanding, lacking a comprehensive evaluation across all graph types and detailed capability definitions. This paper presents GraCoRe, a benchmark for systematically assessing LLMs' graph comprehension and reasoning. GraCoRe uses a three-tier hierarchical taxonomy to categorize and test models on pure graph and heterogeneous graphs, subdividing capabilities into 10 distinct areas tested through 19 tasks. Our benchmark includes 11 datasets with 5,140 graphs of varying complexity. We evaluate four closed-source and eight open-source LLMs, conducting thorough analyses from both ability and task perspectives. Key findings reveal that OpenAI o1 model has amazing comprehension and reasoning capabilities, semantic enrichment enhances reasoning performance, node ordering impacts task success, and the ability to process longer texts does not necessarily improve graph comprehension or reasoning.GraCoRe is open-sourced at https://github.com/ZIKEYUAN/GraCoRe

Key facts. Cited by 13 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 17 of its 23 references that are in the map. First posted on arXiv 3 Jul 2024.

Builds on

17 of 23 references.

Closest ancestors · 2

Same direction, newest first

  1. 2024GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability7 Mar
  2. 2023Can Language Models Solve Graph Problems in Natural Language?17 May

Other references · 15

  1. 2020Language Models are Few-Shot Learnerscited by 32,199
  2. 2023GPT-4 Technical Reportcited by 18,132
  3. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 12,865
  4. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  5. 2017Inductive Representation Learning on Large Graphscited by 6,284
  6. 2023Qwen Technical Reportcited by 3,273
  7. 2021GLM: General Language Model Pretraining with Autoregressive Blank Infillingcited by 1,026
  8. 2019Heterogeneous Graph Attention Networkcited by 732
  9. 2023Unifying Large Language Models and Knowledge Graphs: A Roadmapcited by 663
  10. 2020MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embeddingcited by 304
  11. 2024MT-Bench-101: A Fine-Grained Benchmark for Evaluating Large Language Models in Multi-Turn Dialoguescited by 247
  12. 2023GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarkingcited by 209
3 more
  1. 2023Large Language Models on Graphs: A Comprehensive Surveycited by 190
  2. 2024VisionGraph: Leveraging Large Multimodal Models for Graph Theory Problems in Visual Contextcited by 29
  3. 2024Exploring the Potential of Large Language Models in Graph Generationcited by 15

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 4; 2026: 7.

13 papers.

Sort:

By area:

  1. 2024GraphInsight: Unlocking Insights in Large Language Models for Graph Structure Understandingcited by 18
  2. 2025Rewarding Graph Reasoning Process makes LLMs more Generalized Reasonerscited by 10
  3. 2025GraphThought: Graph Combinatorial Optimization with Thought Generationcited by 9
  4. 2025GraphCogent: Mitigating LLMs' Working Memory Constraints via Multi-Agent Collaboration in Complex Graph Understandingcited by 9
  5. 2025KG-LLM-Bench: A Scalable Benchmark for Evaluating LLM Reasoning on Textualized Knowledge Graphscited by 6
  6. 2024Graph Linearization Methods for Reasoning on Graphs with Large Language Modelscited by 5
  7. 2026Exposing Weaknesses of Large Reasoning Models through Graph Algorithm Problemscited by 3
  8. 2026AlgBench: To What Extent Do Large Reasoning Models Understand Algorithms?cited by 1
  9. 2026LoReC: Rethinking Large Language Models for Graph Data Analysiscited by 0
  10. 2026GraphInfer-Bench: Benchmarking LLM's Inference Capability on Graphscited by 0
  11. 2026ClosureBench: A Constructive Benchmark for Compositional Graph Reasoningcited by 0
  12. 2026GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMscited by 0
1 more
  1. 2026PetriBench: Benchmarking LLM Reasoning over Dynamic State Spacescited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2023Evaluating Large Language Models on Graphs: Performance Insights and Comparative Analysis
  2. 2026Unified Multi-Dimensional Benchmark for Complex Graph Reasoning in Large Language Models
  3. 2024Revisiting the Graph Reasoning Ability of Large Language Models: Case Studies in Translation, Connectivity and Shortest Path
  4. 2024Can LLM Graph Reasoning Generalize beyond Pattern Memorization?
  5. 2024GUNDAM: Aligning Large Language Models with Graph Understanding
  6. 2025Rethinking and Benchmarking Large Language Models for Graph Reasoning
  7. 2023GraphLLM: Boosting Graph Reasoning Ability of Large Language Model
  8. 2024Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs