# How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 54 references that are in the map.
- First posted on arXiv 4 Oct 2024.

## Builds on (most cited first, 30 of 31)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Parameterized Explainer for Graph Neural Network](https://mlsanity.com/paper/2011.04573/) (2020)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Exploring the Potential of Large Language Models (LLMs) in Learning on Graphs](https://mlsanity.com/paper/2307.03393/) (2023)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [GraphGPT: Graph Instruction Tuning for Large Language Models](https://mlsanity.com/paper/2310.13023/) (2023)
- [Language is All a Graph Needs](https://mlsanity.com/paper/2308.07134/) (2023)
- [GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking](https://mlsanity.com/paper/2305.15066/) (2023)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [LLaGA: Large Language and Graph Assistant](https://mlsanity.com/paper/2402.08170/) (2024)
- [Talk like a Graph: Encoding Graphs for Large Language Models](https://mlsanity.com/paper/2310.04560/) (2023)
- [MolCA: Molecular Graph-Language Modeling with Cross-Modal Projector and Uni-Modal Adapter](https://mlsanity.com/paper/2310.12798/) (2023)
- [Let Your Graph Do the Talking: Encoding Structured Data for LLMs](https://mlsanity.com/paper/2402.05862/) (2024)
- [GraphText: Graph Reasoning in Text Space](https://mlsanity.com/paper/2310.01089/) (2023)
- [GraphLLM: Boosting Graph Reasoning Ability of Large Language Model](https://mlsanity.com/paper/2310.05845/) (2023)
- [Evaluating Explainability for Graph Neural Networks](https://mlsanity.com/paper/2208.09339/) (2022)
- [InstructMol: Multi-Modal Integration for Building a Versatile and Reliable Molecular Assistant in Drug Discovery](https://mlsanity.com/paper/2311.16208/) (2023)
- [A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests](https://mlsanity.com/paper/2302.07090/) (2023)
- [GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability](https://mlsanity.com/paper/2403.04483/) (2024)
- [Can LLMs Effectively Leverage Graph Structural Information through Prompts, and Why?](https://mlsanity.com/paper/2309.16595/) (2023)
- [Simulation of Graph Algorithms with Looped Transformers](https://mlsanity.com/paper/2402.01107/) (2024)
- [Graph-oriented Instruction Tuning of Large Language Models for Generic Graph Mining](https://mlsanity.com/paper/2403.04780/) (2024)
- [CLARE: A Semi-supervised Community Detection Algorithm](https://mlsanity.com/paper/2210.08274/) (2022)

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

- [A Survey of Context Engineering for Large Language Models](https://mlsanity.com/paper/2507.13334/) (2025)
- [Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought](https://mlsanity.com/paper/2505.12514/) (2025)
- [When Do LLMs Help With Node Classification? A Comprehensive Analysis](https://mlsanity.com/paper/2502.00829/) (2025)
- [Exploring Graph Learning Tasks with Pure LLMs: A Comprehensive Benchmark and Investigation](https://mlsanity.com/paper/2502.18771/) (2025)
- [GCoder: Improving Large Language Model for Generalized Graph Problem Solving](https://mlsanity.com/paper/2410.19084/) (2024)
- [Model Generalization on Text Attribute Graphs: Principles with Large Language Models](https://mlsanity.com/paper/2502.11836/) (2025)
- [KG-LLM-Bench: A Scalable Benchmark for Evaluating LLM Reasoning on Textualized Knowledge Graphs](https://mlsanity.com/paper/2504.07087/) (2025)
- [Reasoning by Exploration: A Unified Approach to Retrieval and Generation over Graphs](https://mlsanity.com/paper/2510.07484/) (2025)
- [Large Language Models Meet Text-Attributed Graphs: A Survey of Integration Frameworks and Applications](https://mlsanity.com/paper/2510.21131/) (2025)
- [Actions Speak Louder than Prompts: A Large-Scale Study of LLMs for Graph Inference](https://mlsanity.com/paper/2509.18487/) (2025)
- [Benefits and Pitfalls of Reinforcement Learning for Language Model Planning: A Theoretical Perspective](https://mlsanity.com/paper/2509.22613/) (2025)
- [LLMTM: Benchmarking and Optimizing LLMs for Temporal Motif Analysis in Dynamic Graphs](https://mlsanity.com/paper/2512.22266/) (2025)
- [GNN-as-Judge: Unleashing the Power of LLMs for Graph Learning with GNN Feedback](https://mlsanity.com/paper/2604.08553/) (2026)
- [Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More](https://mlsanity.com/paper/2503.10542/) (2025)
- [Uncovering Graph Reasoning in Decoder-only Transformers with Circuit Tracing](https://mlsanity.com/paper/2509.20336/) (2025)
- [Damba-ST: Domain-Adaptive Mamba for Efficient Urban Spatio-Temporal Prediction](https://mlsanity.com/paper/2506.18939/) (2025)
- [GnnXemplar: Exemplars to Explanations -- Natural Language Rules for Global GNN Interpretability](https://mlsanity.com/paper/2509.18376/) (2025)
- [GraphScout: Empowering Large Language Models with Intrinsic Exploration Ability for Agentic Graph Reasoning](https://mlsanity.com/paper/2603.01410/) (2026)
- [Revisiting Graph-Tokenizing Large Language Models: A Systematic Evaluation of Graph Token Understanding](https://mlsanity.com/paper/2605.03514/) (2026)
- [PrefixAgent: An LLM-Powered Design Framework for Efficient Prefix Adder Optimization](https://mlsanity.com/paper/2507.06127/) (2025)
- [GraphGhost: Tracing Structures Behind Large Language Models](https://mlsanity.com/paper/2510.08613/) (2025)
- [Graph Property Inference in Small Language Models: Effects of Representation and Reasoning Strategy](https://mlsanity.com/paper/2603.06635/) (2026)
- [LoReC: Rethinking Large Language Models for Graph Data Analysis](https://mlsanity.com/paper/2604.17897/) (2026)
- [Evaluating LLMs on Large-Scale Graph Property Estimation via Random Walks](https://mlsanity.com/paper/2605.01484/) (2026)
- [A Unified Graph Language Model for Multi-Domain Multi-Task Graph Alignment Instruction Tuning](https://mlsanity.com/paper/2605.12197/) (2026)
- [GraphARC: A Comprehensive Benchmark for Graph-Based Abstract Reasoning](https://mlsanity.com/paper/2605.31031/) (2026)
- [Beyond the Golden Teacher: Enhancing Graph Learning through LLM-GNN Co-teaching](https://mlsanity.com/paper/2606.11583/) (2026)
- [AdaSTORM: Scaling LLM Reasoning on Dynamic Graphs via Adaptive Spatio-Temporal Multi-Agent Collaboration](https://mlsanity.com/paper/2606.16328/) (2026)
- [ReMem: Rethinking Perception and Memory in Long-Context Recommendation Agents](https://mlsanity.com/paper/2609.37311/) (2026)
- [GraphCert: Bootstrap Agentic Graph Reasoning with Certified Evidence Rubrics](https://mlsanity.com/paper/2609.38798/) (2026)

## Abstract (arXiv)

Benchmarking the capabilities and limitations of large language models (LLMs) in graph-related tasks is becoming an increasingly popular and crucial area of research. Recent studies have shown that LLMs exhibit a preliminary ability to understand graph structures and node features. However, the potential of LLMs in graph pattern mining remains largely unexplored. This is a key component in fields such as computational chemistry, biology, and social network analysis. To bridge this gap, this work introduces a comprehensive benchmark to assess LLMs' capabilities in graph pattern tasks. We have developed a benchmark that evaluates whether LLMs can understand graph patterns based on either terminological or topological descriptions. Additionally, our benchmark tests the LLMs' capacity to autonomously discover graph patterns from data. The benchmark encompasses both synthetic and real datasets, and a variety of models, with a total of 11 tasks and 7 models. Our experimental framework is designed for easy expansion to accommodate new models and datasets. Our findings reveal that: (1) LLMs have preliminary abilities to understand graph patterns, with O1-mini outperforming in the majority of tasks; (2) Formatting input data to align with the knowledge acquired during pretraining can enhance performance; (3) The strategies employed by LLMs may differ from those used in conventional algorithms.