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

2024/10/04 by Xinnan Dai, Dai, Xinnan, Haohao Qu +15 · 11 citations
Computer Science · #Advanced Graph Neural Networks #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Graph Theory and Algorithms #Machine Learning (cs.LG) #Topic Modeling

paper · pdf · doi:10.48550/arxiv.2410.05298

openalex publication_date 2024/10/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• LLMTM: Benchmarking and Optimizing LLMs for Temporal Motif Analysis in Dynamic Graphs
• Large Language Models Meet Text-Attributed Graphs: A Survey of Integration Frameworks and Applications
• Reasoning by Exploration: A Unified Approach to Retrieval and Generation over Graphs
• GraphGhost: Tracing Structures Behind Large Language Models
• Benefits and Pitfalls of Reinforcement Learning for Language Model Planning: A Theoretical Perspective
• Uncovering Graph Reasoning in Decoder-only Transformers with Circuit Tracing
• Actions Speak Louder than Prompts: A Large-Scale Study of LLMs for Graph Inference
• GnnXemplar: Exemplars to Explanations -- Natural Language Rules for Global GNN Interpretability
• AssemMate: Graph-Based LLM for Robotic Assembly Assistance
• CS-Agent: LLM-based Community Search via Dual-agent Collaboration
• PrefixAgent: An LLM-Powered Design Framework for Efficient Prefix Adder Optimization

Related

• Beyond Text: A Deep Dive into Large Language Models' Ability on Understanding Graph Data
• Graph Machine Learning in the Era of Large Language Models (LLMs)
• Graph Learning and Its Advancements on Large Language Models: A Holistic Survey
• GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking
• A Survey of Graph Meets Large Language Model: Progress and Future Directions