Elamur Research⌕
☰
home / papers / 2025 / GraCoRe: Benchmarking Graph Comprehension and Complex Reasoning in Large Language Models

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

Paper · 2025 · Zike Yuan, Ming Liu, Hui Wang et al.

Summary

LLMs are increasingly applied to graph-structured data, but current benchmarks tend to cover only one graph family and are organized around isolated tasks rather than clearly defined abilities. GraCoRe fills this gap by measuring how well LLMs understand graphs and how well they reason over them. The authors propose a three-level taxonomy. At the top are two core abilities: understanding and reasoning. The middle level has four categories split by data type (pure versus heterogeneous graphs). The bottom level holds 10 fine-grained capabilities probed through 19 tasks, ranging from counting nodes and BFS traversal to path problems and node classification. Graphs are turned into text with rule-based prompts, and difficulty is controlled through graph size and sparsity. Experiments on 12 LLMs show that reasoning is the main weakness for most models, while OpenAI o1 performs strongly. Semantic context helps reasoning, sequential node naming beats random ordering, and longer context windows bring no clear gain. The resource gives a more precise diagnosis of where LLMs fail on graph data.

Key points

  • GraCoRe contains 11 datasets with 5,140 graphs. It covers both pure graphs (structure only) and heterogeneous graphs with rich semantics, such as movie and academic networks. The benchmark is released on GitHub (ZIKEYUAN/GraCoRe).
  • The evaluated models were four closed-source systems (including OpenAI o1, GPT-4o, GPT-4, and GPT-3.5) and eight open-source ones (for example LLama3, LLama2, Chatglm3, Chatglm2, Vicuna, and Qwen2).
  • Accuracy falls as node count grows, especially on average degree, shortest path, and Hamiltonian path tasks. Even o1 suffers on the reasoning tasks at larger scales.
  • In a test on ACMText, titles and abstracts were removed from the input. GPT-4 and GPT-4o still classified nodes well, GPT-3.5 dropped sharply, and open-source models changed little.
  • Ordering nodes sequentially instead of randomly improved results, most notably on path-reasoning tasks. The authors see this as a sign that models are poorly trained on randomly ordered graph descriptions.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Harbin Institute of TechnologyHarbin · China158 works · 28,841 citations🔬Peng Cheng LaboratoryShenzhen · China38 works · 2,504 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputer Vision and Pattern Recognition · 2,869 works

🧭 Topics 1Research subjects and languages the work is about.Reasoning · 1,426 works

Cite

Cite as Zike Yuan, Ming Liu, Hui Wang and Bing Qin. 2025. GraCoRe: Benchmarking Graph Comprehension and Complex Reasoning in Large Language Models. Proceedings of the 31st International Conference on Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{yuan2025gracore,
  title = {{GraCoRe: Benchmarking Graph Comprehension and Complex Reasoning in Large Language Models}},
  author = {Zike Yuan, Ming Liu, Hui Wang and Bing Qin},
  booktitle = {Proceedings of the 31st International Conference on Computational Linguistics},
  year = {2025},
  url = {https://aclanthology.org/2025.coling-main.531/}
}

References

27 references, 8 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. 2023. Gpt-4 technical report. arXiv preprint arXiv:2303.08774.
  2. Ge Bai, Jie Liu, Xingyuan Bu, Yancheng He, Jiaheng Liu, Zhanhui Zhou, Zhuoran Lin, Wenbo Su, Tiezheng Ge, Bo Zheng, et al. 2024. Mt-bench-101: A fine-grained benchmark for evaluating large language models in multi-turn dialogues. arXiv preprint arXiv:2402.14762.
  3. Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, et al. 2023. Qwen technical report. arXiv preprint arXiv:2309.16609.
  4. Xinyu Fu, Jiani Zhang, Ziqiao Meng, and Irwin King. 2020. Magnn: Metapath aggregated graph neural network for heterogeneous graph embedding. In Proceedings of the web conference 2020, pages 2331– 2341. find
  5. Jiayan Guo, Lun Du, Hengyu Liu, Mengyu Zhou, Xinyi He, and Shi Han. 2023. Gpt4graph: Can large language models understand graph structured data? an empirical evaluation and benchmarking. arXiv preprint arXiv:2305.15066. find
  6. Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. Advances in neural information processing systems, 30.
  7. Scott Beamer, Krste Asanović, and David Patterson. 2013. Direction-optimizing breadth-first search. Scientific Programming, 21(3-4):137–148. find
  8. Bowen Jin, Gang Liu, Chi Han, Meng Jiang, Heng Ji, and Jiawei Han. 2023. Large language models on graphs: A comprehensive survey. arXiv preprint arXiv:2312.02783. find
  9. Stephen P Borgatti and Martin G Everett. 2006. A graph-theoretic perspective on centrality. Social networks, 28(4):466–484. find
  10. Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907.
  11. Alfirna Rizqi Lahitani, Adhistya Erna Permanasari, and Noor Akhmad Setiawan. 2016. Cosine similarity to determine similarity measure: Study case in online essay assessment. In 2016 4th International conference on cyber and IT service management, pages 1–6. IEEE. find
  12. Yuhan Li, Zhixun Li, Peisong Wang, Jia Li, Xiangguo Sun, Hong Cheng, and Jeffrey Xu Yu. 2023. A survey of graph meets large language model: Progress and future directions. arXiv preprint arXiv:2311.12399. — [arXiv:2311.12399](https://arxiv.org/abs/2311.12399) find
  13. Yunxin Li, Baotian Hu, Haoyuan Shi, Wei Wang, Longyue Wang, and Min Zhang. 2024. Visiongraph: Leveraging large multimodal models for graph theory problems in visual context. arXiv preprint arXiv:2405.04950. — [arXiv:2405.04950](https://arxiv.org/abs/2405.04950) find
  14. Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. 2024. Can language models solve graph problems in natural language? Advances in Neural Information Processing Systems, 36. find
  15. Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. 2019. Heterogeneous graph attention network. In The world wide web conference, pages 2022–2032. find
  16. Yang Yao, Xin Wang, Zeyang Zhang, Yijian Qin, Ziwei Zhang, Xu Chu, Yuekui Yang, Wenwu Zhu, and Hong Mei. 2024. Exploring the potential of large language models in graph generation. arXiv preprint arXiv:2403.14358. — [arXiv:2403.14358](https://arxiv.org/abs/2403.14358) find
  17. Chang Liu and Bo Wu. 2023. Evaluating large language models on graphs: Performance insights and comparative analysis. arXiv preprint arXiv:2308.11224. — [arXiv:2308.11224](https://arxiv.org/abs/2308.11224) find
  18. Jifan Yu, Xiaozhi Wang, Shangqing Tu, Shulin Cao, Daniel Zhang-Li, Xin Lv, Hao Peng, Zijun Yao, Xiaohan Zhang, Hanming Li, et al. 2023. Kola: Carefully benchmarking world knowledge of large language models. arXiv preprint arXiv:2306.09296. — [arXiv:2306.09296](https://arxiv.org/abs/2306.09296) find
  19. Zihan Luo, Xiran Song, Hong Huang, Jianxun Lian, Chenhao Zhang, Jinqi Jiang, Xing Xie, and Hai Jin. 2024. Graphinstruct: Empowering large language models with graph understanding and reasoning capability. arXiv preprint arXiv:2403.04483. — [arXiv:2403.04483](https://arxiv.org/abs/2403.04483) find
  20. Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, et al. 2023. A survey of large language models. arXiv preprint arXiv:2303.18223.
  21. Shirui Pan, Linhao Luo, Yufei Wang, Chen Chen, Jiapu Wang, and Xindong Wu. Unifying large language models and knowledge graphs: A roadmap, 2023. arXiv preprint arXiv:2306.08302.
  22. SGOPAL Patro and Kishore Kumar Sahu. 2015. Normalization: A preprocessing stage. arXiv preprint arXiv:1503.06462. — [arXiv:1503.06462](https://arxiv.org/abs/1503.06462) find
  23. Bryan Perozzi, Bahare Fatemi, Dustin Zelle, Anton Tsitsulin, Mehran Kazemi, Rami Al-Rfou, and Jonathan Halcrow. 2024. Let your graph do the talking: Encoding structured data for llms. arXiv preprint arXiv:2402.05862. — [arXiv:2402.05862](https://arxiv.org/abs/2402.05862) find
  24. V Srinivasa Rao, K Srinivas, GN Sujini, and GN Sunand Kumar. 2014. Protein-protein interaction detection: methods and analysis. International journal of proteomics, 2014(1):147648. find
  25. Jiabin Tang, Yuhao Yang, Wei Wei, Lei Shi, Long Xia, Dawei Yin, and Chao Huang. 2024a. Higpt: Heterogeneous graph language model. arXiv preprint arXiv:2402.16024. — [arXiv:2402.16024](https://arxiv.org/abs/2402.16024) find
  26. Jianheng Tang, Qifan Zhang, Yuhan Li, and Jia Li. 2024b. Grapharena: Benchmarking large language models on graph computational problems. arXiv preprint arXiv:2407.00379. — [arXiv:2407.00379](https://arxiv.org/abs/2407.00379) find
  27. Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. 2023. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/yuan-2025-gracore-benchmarking-graph-comprehension-complex/