Research map / Large language models / Reasoning and chain of thought
GraphChain: Large Language Models for Large-scale Graph Analysis via Tool Chaining
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.
Proposes GraphChain, an RL-trained (PPO) LLM agent that analyzes large graphs by chaining NetworkX-based tools, with progressive graph distillation rewards and a structure-aware test-time adapter driven by spectral fingerprints.
Problem
LLMs cannot load large graphs into context and single-step tool calls on textually described graphs lead to reasoning hallucination; the paper targets scalable, adaptive LLM-driven graph analysis.
Approach
Treat graph exploration as an MDP where a Qwen2.5-7B agent sequentially invokes NetworkX tools that keep large graph state in memory and return short summaries; rewards favor reducing a Graph Description Length while keeping task relevance, and a lightweight adapter maps Laplacian singular values to a soft prompt for test-time adaptation.
Key results
- GraphChain (Qwen2.5-7B, LoRA) reaches 84.7% average accuracy vs 70.2% for GraphForge (8B) and 59.4% for GPT-4o, reported as a 20.7% relative improvement.
- Transfer trained only on Financial Network: STTA-equipped model drops less on unseen domains than without STTA (e.g., Citation 79.2 vs 75.1).
- Reduced-toolset variant (50% of Centrality and Community tools removed) averages 79.8%, still above GraphForge.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GraphChain instead of ToolGen | Financial Network reasoning · Financial Network | accuracy: 75.8 ± 1.1 -> 81.5 ± 2.2 | Helped |
| Use GraphChain instead of GraphForge | Chemical Molecule reasoning · Chemical Molecule | accuracy: 70.9 ± 5.4 -> 81.1 ± 0.7 | Helped |
| Use GraphChain instead of GraphForge | Social Network reasoning · Social Network | accuracy: 80.4 ± 4.2 -> 89.6 ± 2.0 | Helped |
| Use GraphChain instead of Claude-4-Sonnet | Citation Graph reasoning · Citation Graph | accuracy: 77.5 ± 1.4 -> 83.6 ± 2.6 | Helped |
| Use GraphChain instead of GraphForge | Traffic Network reasoning · Traffic Network | accuracy: 73.5 ± 3.1 -> 84.1 ± 0.3 | Helped |
| Add structure-aware test-time adaptation (ablation) | GraphChain transferred from Financial Network · Social Network, Citation Graph, and Traffic Network | accuracy: +2.6%, +5.9%, and +3.5% | Helped |
| Add progressive graph distillation (ablation) | GraphChain · Graph reasoning scenarios | accuracy | Helped |
| Add structure-aware test-time adaptation (ablation) | GraphChain · Graph reasoning scenarios | accuracy | Helped |
| Remove 50% of Centrality and Community Detection tools (ablation) | GraphChain · Average across five graph scenarios | accuracy: 84.7±1.8 -> 79.8±2.4 | Hurt |
| Increase the base model size from Qwen2.5-3B to Qwen2.5-14B (ablation) | GraphChain · Financial Network, Chemical Molecule, Social Network, and Traffic Network | accuracy | Helped |
| Increase the base model size from Qwen2.5-3B to Qwen2.5-14B (ablation) | GraphChain · Citation Graph | accuracy: 74.4% -> 83.2% | Mixed |
Surprising findings
- Claude-4-Sonnet and GPT-4.1 underperform on the Traffic network relative to other domains, and Gemini-2.5-Flash scores only 33.9% average despite strong chemical-domain results.
- A 3B Qwen2.5 variant drops to 56.9% on the chemical domain, below the 7B model by about 24 points.
Limitations
- Focuses on static graphs; dynamic or temporal graphs need adaptation.
- Tool library of 45 NetworkX functions may be insufficient for specialized domains.
- Baseline evaluation uses subgraphs under 100 nodes, while the scalability claim rests on a separate experiment with limited reported detail.
Experimental setup
Datasets: Cora CiteSeer PubMed Facebook Twitter QM9 METR-LA Elliptic
Benchmarks: Financial Network (Elliptic) Chemical Molecule (QM9) Social Network (Facebook/Twitter) Citation Graph (Cora/CiteSeer/PubMed) Traffic Network (METR-LA)
Metrics: accuracy
Baselines: Claude-3-Sonnet GPT-3.5-turbo Claude-3-Haiku Claude-3-Opus GraphWiz NLGraph GPT-4o Claude-4-Sonnet GPT-4.1 Gemini-2.5-Flash Graph-ToolFormer GraphForge
Builds on: GraphForge Graph-ToolFormer PPO NetworkX Information Bottleneck
Closest papers by meaning
- GraphArena: Evaluating and Exploring Large Language Models on Graph Computation (ICLR 2025 · similarity 0.89)
- LoReC: Rethinking Large Language Models for Graph Data Analysis (NeurIPS 2026 · similarity 0.88)
- Attention Mechanisms Perspective: Exploring LLM Processing of Graph-Structured Data (ICML 2025 · similarity 0.88)
- $\texttt{G1}$: Teaching LLMs to Reason on Graphs with Reinforcement Learning (NeurIPS 2025 · similarity 0.88)
- Talk like a Graph: Encoding Graphs for Large Language Models (ICLR 2024 · similarity 0.88)
- Large Language Model Meets Graph Neural Network in Knowledge Distillation (AAAI 2025 · similarity 0.88)
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.