Research map / Graph learning / Graph self-supervised learning
How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces a benchmark testing whether LLMs understand graph patterns from terminology-based, topology-based, and data-driven descriptions across synthetic and real-world graphs, finding O1-mini strongest on most tasks.
Problem
Whether large language models can comprehend, edit, detect, and autonomously mine graph patterns (primitive motifs, k-cores, frequent subgraphs, discriminative patterns) is largely unexplored.
Approach
A multi-task benchmark that categorizes graph pattern descriptions into terminology-based, topology-based, and data-driven types, evaluated with prompting on synthetic and real-world graphs, plus a Transformer expressiveness argument that Transformers can simulate LOCAL/message-passing algorithms over edge-list inputs.
Key results
- O1-mini achieves the highest average accuracy (0.86) and diversity (0.78) on terminology-based pattern translation among the tested models.
- Claude reaches 96% isomorphic-mapping accuracy with edge-comparison algorithms while O1-mini uses degree counting for 89% of samples and gets only about 30% accuracy.
- For discriminative pattern learning on BA-2motif, O1-mini reaches 0.72 classification accuracy despite a discriminative pattern ratio of only 0.08.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use O1-mini rather than the other evaluated models | Pattern translation · Pattern translation | average accuracy: 0.83 -> 0.86 | Helped |
| Use terminology-based rather than topology-based pattern descriptions (ablation) | GPT-4 · Benzene | F1 score: 0.71 -> 0.88 | Helped |
| Use terminology-based rather than topology-based pattern descriptions (ablation) | GPT-4 · R-CO | F1 score: 0.64 -> 0.73 | Helped |
| Combine terminology-based and topology-based descriptions (ablation) | GPT-4 · Benzene | F1 score: 0.88 -> 0.89 | No clear effect |
| Combine terminology-based and topology-based descriptions (ablation) | GPT-4 · R-CO | F1 score: 0.73 -> 0.71 | Hurt |
| Use edge-list rather than adjacency-list format | Discriminative pattern learning · BA-2motif | classification accuracy | Helped |
| Use adjacency-list rather than edge-list format | 3-core detection · 3-core detection | precision | Helped |
| Use terminology-based rather than topology-based descriptions | LLMs · Pattern detection | F1 score | Helped |
Surprising findings
- O1-mini achieves 0.72 classification accuracy despite a discriminative pattern ratio of only 0.08, showing the ratio does not linearly track accuracy.
- Terminology-based descriptions outperform topology-based descriptions for pattern detection, suggesting LLMs leverage internal knowledge of pattern names.
Limitations
- Evaluation on sampled subsets (e.g., 250/50 instances per scale) due to API cost, and discrimination sampling was limited.
- Only closed API models plus Mixtral and Llama evaluated; results depend on temperature-0 prompting.
- Real-world experiments use limited samples, so the classification numbers may be noisy.
Experimental setup
Datasets: BA-2motif MUTAG ogbg-molhiv ogbg-bbbp IMDB-BINARY IMDB-MULTI ENZYMES Fingerprint Benzene Alkane-Carbonyl Fluoride-Carbonyl
Benchmarks: GraphPattern benchmark (pattern translation, graph modification, pattern detection, isomorphic mapping, k-core detection MUTAG ogbg-molhiv ogbg-bbbp IMDB-BINARY IMDB-MULTI ENZYMES Fingerprint Benzene Alkane-Carbonyl Fluoride-Carbonyl
Metrics: accuracy diversity score success rate F1 score precision discriminative pattern ratio
Baselines: GPT-4 GPT-4o Mixtral Llama Gemini Claude
Builds on: NLGraph GraphInstruct BA-2motif
Closest papers by meaning
- Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models (NeurIPS 2024 · similarity 0.94)
- Attention Mechanisms Perspective: Exploring LLM Processing of Graph-Structured Data (ICML 2025 · similarity 0.91)
- GraphArena: Evaluating and Exploring Large Language Models on Graph Computation (ICLR 2025 · similarity 0.91)
- Talk like a Graph: Encoding Graphs for Large Language Models (ICLR 2024 · similarity 0.91)
- LoReC: Rethinking Large Language Models for Graph Data Analysis (NeurIPS 2026 · similarity 0.91)
- Beyond Graphs: Can Large Language Models Comprehend Hypergraphs? (ICLR 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.