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

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

## Key facts

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

## Placed in

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

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [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)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Qwen Technical Report](https://mlsanity.com/paper/2309.16609/) (2023)
- [GLM: General Language Model Pretraining with Autoregressive Blank Infilling](https://mlsanity.com/paper/2103.10360/) (2021)
- [Heterogeneous Graph Attention Network](https://mlsanity.com/paper/1903.07293/) (2019)
- [Unifying Large Language Models and Knowledge Graphs: A Roadmap](https://mlsanity.com/paper/2306.08302/) (2023)
- [MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding](https://mlsanity.com/paper/2002.01680/) (2020)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)
- [MT-Bench-101: A Fine-Grained Benchmark for Evaluating Large Language Models in Multi-Turn Dialogues](https://mlsanity.com/paper/2402.14762/) (2024)
- [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)
- [GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability](https://mlsanity.com/paper/2403.04483/) (2024)
- [VisionGraph: Leveraging Large Multimodal Models for Graph Theory Problems in Visual Context](https://mlsanity.com/paper/2405.04950/) (2024)
- [Exploring the Potential of Large Language Models in Graph Generation](https://mlsanity.com/paper/2403.14358/) (2024)

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

- [GraphInsight: Unlocking Insights in Large Language Models for Graph Structure Understanding](https://mlsanity.com/paper/2409.03258/) (2024)
- [Rewarding Graph Reasoning Process makes LLMs more Generalized Reasoners](https://mlsanity.com/paper/2503.00845/) (2025)
- [GraphThought: Graph Combinatorial Optimization with Thought Generation](https://mlsanity.com/paper/2502.11607/) (2025)
- [GraphCogent: Mitigating LLMs' Working Memory Constraints via Multi-Agent Collaboration in Complex Graph Understanding](https://mlsanity.com/paper/2508.12379/) (2025)
- [KG-LLM-Bench: A Scalable Benchmark for Evaluating LLM Reasoning on Textualized Knowledge Graphs](https://mlsanity.com/paper/2504.07087/) (2025)
- [Graph Linearization Methods for Reasoning on Graphs with Large Language Models](https://mlsanity.com/paper/2410.19494/) (2024)
- [Exposing Weaknesses of Large Reasoning Models through Graph Algorithm Problems](https://mlsanity.com/paper/2602.06319/) (2026)
- [AlgBench: To What Extent Do Large Reasoning Models Understand Algorithms?](https://mlsanity.com/paper/2601.04996/) (2026)
- [LoReC: Rethinking Large Language Models for Graph Data Analysis](https://mlsanity.com/paper/2604.17897/) (2026)
- [GraphInfer-Bench: Benchmarking LLM's Inference Capability on Graphs](https://mlsanity.com/paper/2606.11562/) (2026)
- [ClosureBench: A Constructive Benchmark for Compositional Graph Reasoning](https://mlsanity.com/paper/2608.18242/) (2026)
- [GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs](https://mlsanity.com/paper/2609.12265/) (2026)
- [PetriBench: Benchmarking LLM Reasoning over Dynamic State Spaces](https://mlsanity.com/paper/2609.19883/) (2026)

## 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