Research map / Large language models / Agents, code and math
Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models
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 ProGraph, a 512-problem benchmark testing whether LLMs can solve graph analysis tasks by writing code against six Python graph libraries, plus LLM4Graph datasets (crawled API docs and about 29K auto-generated code QA pairs) that improve closed models via RAG and open models via fine-tuning.
Problem
Existing LLM graph benchmarks require reasoning over adjacency lists in prompts, which limits graphs to a few dozen nodes and relies on step-by-step reasoning. The paper asks whether LLMs can instead analyze graphs of practical scale by programming with external graph APIs, as human experts do.
Approach
Shift graph analysis evaluation from direct in-prompt reasoning to API-based programming: the benchmark requires executable code using NetworkX, igraph, CDlib, graspologic, Little Ball of Fur and Karate Club, and the training data pairs API documentation with back-instructed code, with Doc+Code CoT answers that first name the APIs.
Key results
- The best base model, Claude 3 Opus, reaches 34.7% overall accuracy and GPT-4o 36.3% without RAG; with RAG, GPT-4 turbo and Claude 3 Opus reach up to 46.2% (Claude 3 Opus RAG 7).
- Fine-tuning Deepseek Coder on Doc+Code raises overall accuracy from 24.2% to 46.6%, and Llama 3 from 11.7% to 44.9%.
- GPT-4o judgments show 98.9% self-consistency and 97.5% human consistency on the 512 problems.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add RAG with 7 retrieved APIs (ablation) | Claude 3 Opus · ProGraph overall | accuracy: 34.7 -> 46.2 | Helped |
| add RAG with 5 retrieved APIs (ablation) | GPT-4 turbo · ProGraph overall | accuracy: 31.2 -> 39.6 | Helped |
| add RAG with 5 retrieved APIs (ablation) | GPT-4o · ProGraph overall | accuracy: 36.3 -> 42.6 | Helped |
| add RAG with 5 retrieved APIs (ablation) | Gemini 1.5 Pro · ProGraph overall | accuracy: 24.8 -> 37.3 | Helped |
| fine-tune on Code dataset (ablation) | Llama 3 · ProGraph overall | accuracy: 11.7 -> 43.8 | Helped |
| fine-tune on Doc+Code dataset and use two-step retrieval (ablation) | Llama 3 · ProGraph overall | accuracy: 11.7 -> 44.9 | Helped |
| fine-tune on Code dataset (ablation) | Deepseek Coder · ProGraph overall | accuracy: 24.2 -> 43.1 | Helped |
| fine-tune on Doc+Code dataset and use two-step retrieval (ablation) | Deepseek Coder · ProGraph overall | accuracy: 24.2 -> 46.6 | Helped |
| add RAG with 3 retrieved APIs to the Code Only model (ablation) | Llama 3 · ProGraph overall | accuracy: 43.8 -> 31.6 | Hurt |
| add RAG with 3 retrieved APIs to the Code Only model (ablation) | Deepseek Coder · ProGraph overall | accuracy: 43.1 -> 33.2 | Hurt |
| increase retrieved API count from 3 to 5 (ablation) | GPT-4 turbo · ProGraph overall | accuracy: 36.2 -> 39.6 | Helped |
| increase retrieved API count from 5 to 7 (ablation) | GPT-4 turbo · ProGraph overall | accuracy: 39.6 -> 39.1 | Hurt |
Surprising findings
- Adding RAG to the fine-tuned open-source models did not improve accuracy and often degraded it, which the authors attribute to small models' limited long-context handling.
- Fine-tuned small models strongly outperform RAG-enhanced large closed models on graph embedding tasks.
Limitations
- The hand-crafted benchmark has only 512 problems and covers a core subset of graph analysis tasks.
- Automated GPT-4o evaluation may vary across model versions, and multi-turn task solving is not considered.
- Training data involves only single-API problems, while the benchmark includes multi-API hard problems.
Experimental setup
Datasets: LLM4Graph document dataset LLM4Graph Code (QA) LLM4Graph Doc+Code (QA)
Benchmarks: ProGraph
Metrics: pass rate accuracy
Baselines: GPT-3.5 GPT-4 turbo GPT-4o Claude 3 Haiku Claude 3 Sonnet Claude 3 Opus Gemini 1.0 Pro Gemini 1.5 Pro Llama-3-8B-Instruct Deepseek-Coder-7B-Instruct-v1.5
Builds on: chain-of-thought retrieval-augmented generation back-instruction
Closest papers by meaning
- How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension (ICLR 2025 · similarity 0.94)
- Talk like a Graph: Encoding Graphs for Large Language Models (ICLR 2024 · similarity 0.93)
- GraphArena: Evaluating and Exploring Large Language Models on Graph Computation (ICLR 2025 · similarity 0.91)
- LoReC: Rethinking Large Language Models for Graph Data Analysis (NeurIPS 2026 · similarity 0.91)
- Attention Mechanisms Perspective: Exploring LLM Processing of Graph-Structured Data (ICML 2025 · similarity 0.90)
- LLaGA: Large Language and Graph Assistant (ICML 2024 · 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.