GraphChain: Large Language Models for Large-scale Graph Analysis via Tool Chaining

Chunyu Wei (Renmin University of China) · Wenji Hu (Renmin University of China) · Xingjia Hao (Guangxi University) · Xin Wang (University of California, Santa Barbara) · Yifan Yang (Beijing Jiaotong University) · Yunhai Wang (Shandong University) · Yang Tian (Guangxi University) · Yueguo Chen (Renmin University of China)

diverse graph structuresdynamic sequencesfrozen llm policygraph spectral propertiesgraphchainintermediate state compressionprogressive graph distillationreinforcement learningself-supervised adaptersoft promptsspecialized toolsstructure-aware test-time adaptationtask relevancetool sequences

Large Language Models (LLMs) face significant limitations when applied to large-scale graphs, struggling with context constraints and inflexible reasoning. We introduce GraphChain, a novel framework enabling LLMs to analyze large graphs by orchestrating dynamic sequences of specialized tools, mimicking human exploratory processes. GraphChain incorporates two core technical contributions: (1) Progressive Graph Distillation, a reinforcement learning approach that learns to generate tool sequences balancing task relevance and intermediate state compression, thereby overcoming LLM context limitations. (2) Structure-aware Test-Time Adaptation (STTA), a mechanism using a lightweight, self-supervised adapter conditioned on graph spectral properties to efficiently adapt a frozen LLM policy to diverse graph structures via soft prompts without retraining. Experiments show GraphChain significantly outperforms prior methods, enabling scalable and adaptive LLM-driven graph analysis.