GraphChain: Large Language Models for Large-scale Graph Analysis via Tool Chaining
Authors: Chunyu Wei
Wenji Hu
Xingjia Hao
Xin Wang
Yifan Yang
Yunhai Wang
Yang Tian
Yueguo Chen
Venue: NeurIPS 2025 poster ()
Keywords: Large Language Model
Graph Analysis
Tool Learning
Primary area: deep_learning

Abstract: 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.

GraphChain: Large Language Models for Lcrge-scale Graph Analysis via Tool Chaining
Chunyu Wei', Wenji Hu', Xingjia Hao', Xin Wang', Yifan Yang', Yueguo Chen'
Yang Tian', Yunhai Wang
Renmin University of China, China Guanggi University, China
Beijing Jiaotong University, China
weicy1501 cloud. com, 2024000991 arruc edu. en, haoxingj ia@st. gxu. edu 0023103702@ruc edu, en, 23281027@bjtu edu edu. cn
chenyueguo@ruc edu, en, ytianegxu. edu, en, cloudseawang@mail.. com
Abstract
Large Language Models (LLMs) face significant limitations when applied to large- scale graphs, struggling with context constraints and inflexible reasoning. We present GraphChain, framework that enables LLMs to analyze complex graphs through dynamic sequences of specialized tools, mimicking human exploratory intelligence. Our approach introduces two key innovations: (1) Progressive Graph Distillation, reinforcement learning mechanism that generates optimized tool quences balancing task relevance with information compression, and (2) Structure- aware Test-Time Adaptation, which efficiently tailors tool selection strategies diverse graph topologies using spectral properties and lightweight adapters without costly retraining. Experiments show GraphChain significantly outperforms prior methods, enabling scalable and adaptive LLM-driven graph analysis.
Introduction
Graph-structured data represents fundamental paradigm across diverse domains, from social networks and molecular structures to knowledge bases and recommendation systems Wei et al. [2025] 2023b 2022d). While large language models (LLMs) have demonstrated remarkable reasoning capabilities, they encounter significant challenges when processing graph data.
Recent approaches to enhancing LLMs' graph processing capabilities have taken primary directions. The first attempts to adapt LLMs to directly process graph structures-eithee through tokenization natural language descriptions [Chai al. 2023 Wang et al. 2023b]. However, this approach faces Context Exhaustion: large-scale graphs with millions of nodes and edges cannot be effectively compressed within LLMs' context limitations, making computationally infeasible to load entire subgraphs into their context windows (Figure I left).
Recognizing these limitations, second direction draws inspiration from tool learning paradigms. Approaches like Graph-Toon ToolFormer [Zhang] 2023a] and GraphForge [Wang et al.) 2024c pioneered integrating specialized tools with LLMss for graph reasoning, enabling models call external graph processing functions. However, these methods primarily conceptualize tool learning as text generation, relying on single-step tool invocations with textually described graph structures. This approach leads to Reasoning Hallucination (Figure I] middle), as it places unrealistic demands on individual tools provide comprehensive functionality for complex graph analysis.
Corresponding author.
'The code is available in https//gthhbbbom//uuuuumu//CCCCn
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Large-scalt Complex Graph AASAAAAAANAACA
GraphChain
Simple Quistion: Whic account has the most
transactios the network?
loaded in memory parameter G
You going The graph
you can use the tool to analyce....
Gval Lod
Describing graphs in natural language Prompt::
fcently potental froud accounts.
need potential multiple steps:
The network contains 500,000 accounts
Account A connects to accounts C CD and with transacionn valass of $500, $300..
Complex Quastion:
Tool Call: capt>ffnnd_so wtwpeiinndddeeeeeeeeeeeeeeeeeeee (ycpple_occesss
Account connects..
donddy pocential faus sccounts.
Single-Tool Approach
Result [ctecte_]t0 11st]
Sequence length eaceeded
Tokenizing Graph Component
Prompt
loaded memory parameter the tool anslyre... Identily potinial flaud accounts.
going
Spucteed
Tool Call: caploritter [fetrcle [ist]. vel filtter (55" jeapt
Prompt:
Encader
Result (filtter Hist
X
transaction graph: grophi has network??
I need find potential finued accounts by analyzing dircllrr patters.
The froud accounts is
According to the andlysis there are following potential fraud account AK, CF, DO,
Account F has the most transactions
capi faniddiindeiii circul patternss())</ppp
Context Exhaustion
X Reasoning Hallacination
Graph analysis complete
Figure 1: Comparison of Graph Processing Approaches with LLMs. Left: Methods suffer from Context Exhaustion where large graphs exceed LLM context windows. Center: Single-tool approaches face Reasoning Hallucination with fixed, predefined tools. Right: Our GraphChain framework enables human-like exploratory analysis through sequential tools that progressively narrow focus in large-scale graphs.
Complex graph analysis parallels human exploration of unknown environments, Just as humans navigate unfamiliar territories through interactive, adaptive exploration- wwhere each step reveals in- formation that guides subsequent information gathering rather than comprehensive analysis in one operation. field researcher might first survey an area broadly before focusing on regions of interest; similarly, graph analysis benefits from incremental understanding built through sequential operations.
graph analysis requires progressive, sequential
Inspired by human exploratory cognition, we propose GraphChain, a novel framework enabling LLMs to process large-scale graphs through dynamic tool-chaining (Figure right). GraphChain decomposes complex graph problems into sequences of specialized operations, activating L.LMs' reasoning capabilities create, refine, and execute chains of graph processing tools. This approach allows progressive refinement and deeper exploration of graph structures, mimicking how human experts methodically investigate complex systems layer by layer.
The implementation of GraphChain addresses two significant technical challenges:
Informative Tool Sequence Generation requires determining optimal tool sequences for diverse analytical tasks, navigating exponentially growing space of possible combinations. Traditional approaches struggle with this challenge due to scarce labeled data for complex graph analysis.
2. Adaptive Graph Structure Sensing must address real-world graph data exhibiting distributional shifts and structural variations. Unlike natural data types, graph structures are heavily human- defined with domain-specific schemas, leading to severe distribution shifts across domains.
To generate informative tool sequences, we propose a progressive graph distillation training mecha- nism. Our key insight is that effective graph analysis mirrors human exploration: beginning broadly and systematically narrowing focus as relevant information emerges. This approach transforms the exponential tool-selection problem into principled information bottleneck optimization, iteratively refining both structural scope and representational complexity while preserving only task-critical information-sinn to how humans selectively attend relevant environmental cues.
For adapting to diverse graphs, we introduce a structure- test-time adaptation mechanism. We leverage the insight that graph topology fundamentally influences optimal analysis strategies, just as explorers adjust techniques for different terrains. Our lightweight adapter dynamically modifies tool selection policy based spectral properties capturing essential structural characteristics, enabling GraphChain to maintain effectiveness across diverse graphs while preserving efficiency.
Our main contributions include:

---

GraphChain, novel framework leveraging Graph-Oriented Reinforcement Learning with pro- gressive information distillation, enabling systematic exploration of large-scale graphs through interconnected tool sequences.
A structure-aware test-time adaptation mechanism that adjusts tool-chaining strategies based on graph topology, enabling efficient transfer to diverse graph structures without costly retraining.
Extensive experimentation demonstrating that GraphChain significantly outperforms existing methods by average of 20.7%, with exceptional scalability handling graphs up to 200,000 nodes while maintaining consistent performance.
2 Related Work
Tool Learning for LLMs Tool learning for LLMs encompasses tuning-free methods using prompt-
ing strategies like Shain-of-Thhughhe [Wei et al. 2022e], ReAct (Yao al.
2023] and DFSDT [Qi
et al. 2023), alongside approaches integrating tools into conversations [Chen et al. [2023] or em-
ploying structured selection via graphs (Liu et al., 2024], hierarchies (Du al.,) 2024 J. or intent
filtering [Fore et al.) 2024). Meanwhile, tuning-based methods directly adapt LLM parameters (Xu
et al. 2023] through behavior cloning with reinforcement learning [Qiao et al. 2024 Yu al.
2024]. fine-tuning specialized decision data [Qin et al. [2033]. frameworks for varying tool
complexities [Gao et al. 2024]. and self-verification mechanisms [Mekala et al. 2024].
Graph Processing with LLMs Recent work enhances LLMs for graph processing via: (1) Direct processing with text or visual graph descriptions [Wang al. 2023b Guo al. 2023] or specialized
token sequences (Chen et al. 2024b, Wang et al., [024b]; (2) Tool integration and agent-based
methods for external function calls Zhang 2023b)
multi-step reasoning (Gu et al. 2024]: (3)
GNN-LLM combinations using GNNs as encoders (Tang et al.) 2024a| or aligning representation
spaces
Su et al. 2022
Test-time Adaptation Traditional machine learning assumes identical training and testing distribu-
tions, but real-world deployments often encounter distribution shifts (Kulinski and Inouye| 2023) Test-Time Adaptation (TTÁ) addresses this challenge [Liang et al.] | Alfarra et [025]] For LLMs, adaptation techniques include test-time prompt tuning [Shu al. [0022] Ma al.) [022]] Curameter-Efficieee Fine-Tuning methods like adapters or LoRA et al. [022] for efficient updates (Shi et al. 2024b Muhtar al. 20224. and "test-time compute scaling with iterative refinement, search, or self-correction
Jaacch et al. 2024 Guo et al. 2025
Suzgun et al. 2025
Preliminaries and Problem Formulation
Graph Notation Let G = (V,E) represent graph, where V = {11, U2,............................. Un. is the set of n = [V] nodes and & C V/x is the set of m |E| edges. The adjacency matrix E {0, 1 (or Raxe for weighted graphs) has entries Ai (or edge weight) if (14, 13)) E, and 0 otherwise. Node features are represented by matrix X E _axd The degree matrix D is diagonal with D.,
Ej=1 Aij. and the normalized graph Laplacian is defined as L = I - D D-1/2 AP-AD-1// A node's neighborhood is (V()) {u E V (v, u) E}. and subgraph G" (V" g') consists of node subset V C V and edge subset EV" x V").
Graph Processing Tool Library We define a library of graph processing tools T (2.,T....., ].). which implemented based on functions from the NetworkX library and operate on tensor representations within the current memory state m. NetworkX is a widely open-source Python library that provides a comprehensive set of graph processing functions, including node and edge operations. graph property calculations, and advanced analytical tools. The tools in the library are based on 45 carefully selected NetworkX functions, with details provided in Appendix E The tools operate on tensor representations, typically containing the adjacency matrix A' and feature matrix X' for subgraph G' ("")")):
m (A' Ra X' Br''xd... ,...) where n' = =|2
(I)
hntps://netwokxx.orgg
3

---

Step
Step 2
Step N-1
Step N
Answer
Tool
Query
Task
Tool
Sramh RistiTi
mll
Tool
PlutetAing Success
Diatapiong baconse
Answer
Tool
Answer
PPO Optimization
Action
State
Reward
GraphChain
Training Phase
Large-scale Complex Graph
Ue Nxx
Lenglt
Adacter
Porrationn
Graph Signature
Query
Test- Time Adaption
Figure 2: (1) Training Phase: Progressive graph distillation where RL agent learns select tool sequences that iteratively reduce the memory state's ' (m) Graph Description Length (GDL) while maximizing task relevance. (2) Structure-aware iistTimm Adaptation: A lightweight adapter (A,)) tuned by minimizing chain length and KL divergence generates structure-specffic soft prompt Pg based on the graph's 's SVD-derived fingerprint zg-
A tool T takes the current memory state m and tool-specific parameters O as input, producing two outputs: (1) concise natural language summary of the execution outcome: (2) An updated memory state m'. Formally, the tool function is defined as: T (m, 0T) (d, dd)..).
This dual output mechanism allows framework to provide context- context-window: window-friendle summaries the LLM via d, while managing potentially large-scale intermediate graph data within m', mitigating context exhaustion when processing large graphs.
MDP Given analytical query Q and input graph G, model sequential graph exploration as a Markov Decision Process (MDP) M = (S, A, P. 7):
Sequential Graph Exploration
State Space S: State encapsulates query Q, graph reference, action history { de) and memory state m.-1.
Action Space A: Actions a, (1) select tool T with parameters or, or 'TERMINATE'.
Transition Dynamics Tool execution produces (de; m.) = T (m,-1, 0r), updating state 88+1 with new history and memory.
Reward Function R(st, de. St+1): Evaluates actions based on progress and task success.
Discount Factor 7 [0, 1]: Balances immediate future rewards.
The agent's policy <a(ar187) parameterized by 0, generates trajectory t {si, a1, $2, a2..... ST, ar} representing sequential tool interactions. To maximize performance, we optimize the expected reward:
VRa = Σ (TT()T = Eewng I(())
V log no (ar
(2)
4 Methodology
GraphChain addresses the challenges of applying LLMs to large-scale graph analysis by formulating problem as a sequential decision-making task solvable via reinforcement learning. Our approach centers on two core technical innovations: (1) Progressive Graph Distillation, which promotes informative yet compact state representations, and (2) Structure-aware Test- test-Time Adaptation, enabling dynamic adjustment to diverse graph topologies. Figure provides a conceptual overview.

---

4.1 Progressive Graph Distillation
Generating effective tool sequences for complex graph queries involves navigating an exponentially large action space. To provide denser learning signals and emulate human-liks analytical workflows that progress from coarse to fine, we introduce Progressive Graph Distillation.
This approach incentivizes the RI. agent to pursue hoth the query objective and manage the complexity of its memory state m. We train the agent prioritize tool sequences that systematically reduce m s data volume while retaining task-critical information, transforming exploration into a guided search characterized by iterative refinement. The aim is to progressively shrink step-by-step. eventually yielding compact final state my suitable for direct processing within the LLM's context window.
4.1.1 Quantifying Memory State Volume and Relevance
Implementing progressive distillation requires quantifying two key aspects of memory state m, each step t: its data volume and its relevance to query Q.
Graph Description Length (GDL(m,)): Drawing from the Minimum Description Length princi- plc, we introduce Graph Description Length to measure the data size needed to represent the current graph state. Assuming memory state m, contains subgraph G22 = (V2, E() with ni [ nodes and m/ | edges, plus node features X Ra/xdd, we define:
GDL(m,) = (structure) + L(features) R a,m, + ayynddy
Coefficients a, af 2 0 weight the relative contribution of structural versus feature information. Task Relevance (Rel (m, Q)): We employ an auxiliary LLM scorer to assess the utility of m, for answering query Q. Since m, may exceed the LLM's context limits, we use the concise description de produced by the executed tool. We estimate the task relevance by:
Rel(m,, 2) LLMScore(prompp(( Q, He, de)) [0,
where H, = {do: .o......,d... 11 the history of preceding descriptions.
4.1.2 Distillation-bssed Reward Shaping
We incorporate progressive distillation into the RL reward function RG = R(st. ae, $141). The reward structure provides feedback during exploration while assessing final task completion:
= wi Suuce + w2 f AGDL + wy FARel
ift < N
R.
(5)
Wadive CCvaluateTaskSureee TassSuccesss Q 88+1)
ift
where N is the final step index, and the intermediate reward components are:
Succ
[[ExecutionSucceess((:: $t41)): Binary reward for valid tool execution.
AGDL tanh (o GDL 1) GD-GDI.(m.) (-1, 1): Rewards reduction in relative GDL.
GDLAM.-)++c
f = Rel, 1e Rewards increase in estimated task relevance.
Weights W1, w2, wa balance the importance of execution success, volume reduction, and relevance gain. Weight Wsolve scales the final reward based on overall success in addressing query Q.
4.1.3 Information Bottleneck Perspective
Our progressive distillation mechanism aligns with the Information Bottleneck principle, advocating for representations that are maximally informative about a target while being maximally compressive of input. Our reward function operationalizes this trade-off by incentivizing high task relevance while rewarding reductions in state volume.
Let the input be X = (G. Q). containing task-relevane information Y AQ (the answer) and task-irrell irrelevate information IR, with the Markov structure (Y,IR) - X - m Assuming the relevance proxy Rel, positively correlates with the mutual information I(m;; Y) and the GDL serves as complexity measure encouraging smaller T(X: m,), optimizing policy with reward function R2 guides the generation of memory states m, that tend to minimize irrelevant information I [[IR; mY) while preserving relevant information I 1(m;; Y)).
Proposition 4.1.
5

---

Detailed proof is provided in Appendix A This proposition provides theoretical support for our distillation approach. By rewarding both relevance gain and volume reduction, the RL process steers the agent toward behaviors that effectively filter graph data reduuing the representational footprint of task-irrelevant components while preserving critical information.
4.1.4 Policy Optimization
To optimize the LLM agent's policy Te. we implement Proximal Policy Optimization (PPO), using Generalized Advantage Estimation (GAE) for improved stability:
N-t
ACAE (0, w)
E (7A)8 where 6, = Ro+1 + (va(1)))) - (s((s)
(6)
Here, À E [0. 1] is the GAE trace decay parameter, Vu is the learned value function, y is the discount factor, and R 1 the distillation aalllattio--warre aware reward.
Following the PPO-clip approach, we maximize a clipped surrogate objective based on trajectories sampled from policy ITg
CLU (0)
Σ min
Ta (s) TTl (as)
AGAE clip
To(ac(ss) Th, (asls))
e, 11 ACAE)
(7)
where Tee. is the old policy used for generating trajectories, and is the clipping hyperparameter.
4.2
Structure-aware Test-Time Adaptation
4.2.1
Graph Structural Fingerprinting
To provide global structural awareness for large-scale graphs, derive concise graph fingerprint. We compute the normalized graph Laplacian L = I- --D-1/22A AD- and consider its Singular Value Decomposition, = UEV". The smallest singular values σ, capture dominant, low-frequency components reflecting macroscopic graph properties. We define the structural fingerprint as: ZG (on, .1...., M ) E R ++
While full SVD is intractable for very large graphs, these M + smallest singular values (where M < N) can be computed efficiently using iterative algorithms, effectively distilling essential global topology into compact vector. We provide complexity analysis in Appendix G
4.2.2 Structure-Conddttionee Prompt Generation
STTA employs continuous adaptation mechanism through adapter network Ag, which maps the graph's 's structural fingerprint Zg to soft prompt Pa =A E 12 Xdumb;
This generated prompt is prepended to the standard embedding (t) of the agent's state, modifying the input to the frozen LLM policy: ILM G) (Pa: F (sx))] [Ap())); F(ss)].
The agent's action then sampled from the policy conditioned on this augmented input. During adaptation, only the smaller set of adapter parameters v are tuned, enabling efficient adaptation.
4.2.3 Self-Supervised Adaptation
Given the absence of ground-truth rewards for user query Q on unseen test graph Grest. STTA employs self-supervised strategy using auxiliary queries. We leverage general-purpose LLM to generate diverse auxiliary graph analysis queries relevant to Gies's structure.
For each auxiliary query, we perform rollouts using the frozen base policy conditioned on the graph- specific prompt, yielding trajectories. The adaptation objective balances planning efficiency and policy regularization:
N
LSTIAA (V) =
WI,N + WKL.
Σ
(RI(TT Gue)) Tong (-]s:))
(8)
The components of this objective are: (1) Chain Length (N₂) encouraging efficient planning, and (2) KL Divergence Regularization ensuring helpful but not drastic changes.

---

We minimize this objective using the REINFORCE algorithm, tuning Ay to generate prompts that enhance efficiency while maintaining fidelity learned behaviors, effectively adapting the frozen policy to Gles's specific structure.
5 Experiment
5.1 Experimental Setting
Graph Dataset. We evaluate GraphChain on five diverse graph datasets representing different real-world domains, illustrated in Table [
Table 1: Statistics of graph datasets used in experiments.
Scenario
Dataset
#Nodes
#Edges
#Features
Type
Description
Cora
2,708
10,556
1,433
Academic papers connected
Citation Graphs
CiteSeer
3,327
9,104
3,703
Directed
citation relationships Yang
PubMed
19,717
88,648
500
ct at. 20166
Facebook
4,039
88,234
Undirected Directed
Online interactions
Leskovee
Social Networks
Twitter
81,306
1,768,149
and Mcauley, 2012
Chemical Molecules
18.0/graph
~/7.3//raph
Undirected
Molocular structures with bonds
between atoms Wi 2018
Traffic Networks
METR-LA
207
1,515
Directed
Road networks with geographic constraints
Chen et al. 2020
Financial Networks
Elliptic
203,769
234,355
165
Directed
Transaction
networks
Weber
2019
st 2019
Instruction Data. We constructed two complementary datasets: (1) an SFT dataset comprising 9,986 (query, tool sequence, answer) triplets based on 45 carefully selected NetworkX functions, and (2) an RL dataset containing 3,000 expert-annotated (query, answer) pairs (600 per graph scenario). We allocated 500 pairs per scenario for training and 100 for testing, with domain experts crafting exemplary instruction templates to ensure ecological validity. See Appendix for details.
Baselines. We evaluated GraphChain against state-of of-the--rttttttt methods from two categories:
(1). For Text-Instruction methods, tested leading closed-source LLMs (ilaudd-seriees [An-
thropic 2024], CPT-series [OpenAT 2023). and GLM4-0520 [GLM, 2024)) using two-shot prompting with Chain-of-Thought reasoning, and reproduced specialized graph reasoning meth- ods (NLGraph [Wang et al. 2023a]. GraphWiz [Chen et al. 2024a
(2). For Tool-Instruction methods, we compared against recent tool-augmented approaches
Soraph-ToolForee ZZhng 2023a GraphForge [Wang et al., 2024c and ToolGen [Wang al. 2025]).
To ensure fair comparisons with existing baselines all requiring the entire graph the context window-we partitioned original graphs into subgraphs with fewer than 100 nodes for overall comparison. We use the same input for both baseline methods and GraphForge. our scalability experiment (Section 5.4). GraphChain maintains comparable performance even when scaling to graphs with approximately 200,000 nodes. Further details are provided in Appendix
Training Setup. We used two NVIDIA A800 GPUs with LoRA-based fine-tuning (rank 16, alpha=32) on the Qwen2.
model. Further details are provided Appendix C
5.2
Main Results
Table 2 presents performance comparisons of GraphChain against state-of- the-art baselines, with statistical significance confirmed by two-sample t-tests (p 0.05). Key insights include:
GraphChain substantially outperforms all baselines, achieving 84.7% average accuracy compared 70.2% for the best bascline (GraphForge), representing 20.7% relative improvement.
Among text-instruction baselines, GPT-4o with approximately 200B parameters demonstrates superior performance (59.4% average accuracy), confirming the applicability of scaling laws to graph reasoning tasks.

---

Table Performance comparison (accuracy %) across five real- world graph reasoning scenarios.
Text Instrnssttttion Methods
Model
Parameters
Financial Network
Chemical Molecale
Social Network
Citation Graph
Traffic Network
Average
B-Bonnes
2.3
6-7-3.5-turbo
~175B
230
18.2
Cladde33-Hall0
~208
12.2
38
$2.9
3.2
50.1 +
19.8 2.0
13.9 + 2.4
29.8
C1 Clande-3-pua
-137B
23.6 + 2.1
42.4 + 1.4
$1.9 + 1.3
36.7 3.1
43.4 3.3
39.6 2.2
GraphMiz
5244
61.5 335
68.0
38.4
52.3 2.9
Kl.rraph
~100
59,4+
1.8
$5.0+22
Claude-4-Bonad
58.2
62.9
61.7
77.5
32.
58.6
GPT-4.1
52.2 4:
63.4 1 2.6
61.4 2.3
70.0
55.5 3.1
61.7 2.2
25.1 +
67.3 1.6
28.1 2.1
24.1 +
24.9
33.
Tool-Instruetion Methods
Graph-7ool Former
GraphForge
63.5
70.9
80.4
63.4
73.5
70.2
ToolGeo
8B
75.8
$7.9 2.9
19.4 2.3
61.2 1.3
62.7 1 1.3
67.4 1.8
GraphCbain
81.5 2.2
81.1 1 0.7
89.6 1:
83.6 2.6
84.1 1:
84.7 1,8
improvement
wettedatien
Specialized graph reasoning approaches like GraphForge (70.2% average accuracy) significantly outperform the largest general-purposs LLMs.
GraphChain achieves these results with only 7B parameters, compared GraphForge's 8B and GPT-4o's 200B, demonstrating remarkable parameter efficiency.
5.3 Ablation Study
We introduced two variants: (1) w/o graph distillation, where the progressive graph distillation mechanism disabled; and (2) w/o test-time adaptation, where the Structure-aware Test-Time Adaptation (STTA) component is removed during inference. Figure reeveals several key insights:
First, GraphChain consistently outperforms GraphForge across all graph scenarios, demonstrating the superiority of our approach. Second, Removing either component leads to performance degra- dation, confirming that both play critical roles in enabling effective tool-chaining and structural understanding. Third, The performance drop is more severe when graph distillation is removed compared when disabling STTA, highlighting that progressive distillation is particularly crucial for graph analysis. Lastly, GraphChain without test-time adaptation still outperforms GraphForge in most scenarios, indicating that our multi-step tool-chaining approach with graph distillation inherently more effective than single-step tool invocation patterns.
Traffic Network
Traffic Network
GraphiPage GraphChain
wio graph distillation
adaptation
10.
Accuracy (26)
Accuracy
70
15
19
GPT-
Gappringe
11
Azcuracy (8)
Graph (#Node)
Complexity (e Tcol)
Financial Network
Financial Network
20
Accuracy (%0
Accuracy
GPI4
GraphForpe Cruph
Casphfage
Crsthchunn
Financial Network
Social Network
Ciation Graph
Traffic Network
120
200
200c
Graph Size (#Node)
Query Complexity (#Tool)
Figure 3: Impact of removing graph distillation or test-time adaptation.
Figure 4: Comparison with varying Graph Sizes and Query Complexity.

---

5,4 Scalability Analysis
We stratified our evaluation dataset based on graph size (node count) and reasoning complexity (tool sequence length) to assess how performance scales with these dimensions. Figure reeveals:
(1). As graph size increases, baselines exhibit significant performance degradation, with 4P declining more dramatically, demonstrating the limitations of text-instruction for larger graphs.
(2). GraphChain maintains its performance advantage consistently across all graph sizes tested, including graphs with up to 200,000 nodes. This exceptional scalability stems from representing memory states through concise natural language summaries rather than direct graph descriptions.
(3). While all methods perform well on simple queries (requiring 1-2 tool calls), performance disparities increase with query complexity. Both 4o and GraphForge show steep declines for queries requiring 4-5 tool calls, while GraphChain maintains higher accuracy, demonstrating superior capability for multi-step reasoning.
5.5 Transfer Learning Evaluation
To assess transfer capabilities, fine-tuned GraphChain exclusively Financial Network and evaluated on three unseen domains, comparing performance with and without the STTA module.
Table 3: Results (accuracy %) when training on Financial Network and testing on other domains.
Model
Social Network
Citation Graph
Network
GraphChain (in- no-domain)
89.6
83.6
84.1
GraphChain STTA
86.8 (-3.1%)
79.2 (-4.3%)
80.3 (-4.5%)
GrapbChain woo STTA
84.5 (-5.7%)
75.1 (-10.2%)
77.4 (-8.0%)
Results in demonsaattt GraphChain's 's strong transfer learning capabilities, with cross- dromsnn performance closely approaching in-domain results. The STTA mechanism substantially improves transfer performance, reducing accuracy drops by 2.6%, 5.9%, and 3.5% across the three target domains compared to the variant without STTA, confirming its effectiveness in adapting to diverse graph structures without domain-specific retraining.
5.6 Tool Chain Analysis
To understand how GraphChain adapts its exploration strategy across domains, we categorized tools into six functional clusters and analyzed their usage patterns.
Grggn Strvicee
Suzgraph Extraction
Parnirg
Centra by Hentzee
Commun by Derrction
Contectivit
Graph
AIL
LE-R4
16.5
15
19W4
12.5%
33,04
26.7%
1R.4%
27.6%
6.2%
31.4%
0%
10.%
1B
Figure 5: Distribution of tool types utilized by GraphChain across different graph domains.
Figure 5 reveals distinct exploration patterns adapted to each domain's 's characteristics. Path Planning tools dominate in Traffic Network (33.8%) and Financial Network (26.7%), reflecting the importance of traversal analysis. Social Network analysis relies on Centrality Measures (28.8%) and Community Detection (20.4%) aligning with the importance of influence and clustering, Citation Graph process- ing shows a more balanced distribution with significant usage of Connectivity tools (18.9%). These domain-spectie variations demonstrate GraphChain's ability to adaptively construct appropriate tool sequences on different graph scenarios.
Our framework is designed to be inherently robust to variations in the tool library. The core of GraphChain employs a reinforcement learning policy that learns to select optimal tool sequences from the available action space, rather than being hard-coded to specific tools. To empirically validate

---

this robustness, we conducted an additional experiment with reduced toolset (removing 50% of tools from Centrality and Community Detection categories). Table demonstratee that GraphChain maintains strong performance even with a reduced toolset, showcasing the adaptability of our RI. agent finding alternative tool sequences solve tasks.
Table 4: Robustness to Tool Library Composition (accuracy %).
Financial Network
Chemical Molecule
Social Network
Citation Graph
Traffic Network
Average
GraphForge (Baseline)
63.5.:3.5
70.91:5.4
80.414.22
6,4444,4
73,54:3.1
70.2-43.8
GraphChain (Full Toolsct)
81.1-0.7
836+2.6
GraphChoán (Reduced Toolset)
77.3
78
82.743.11
80.1+3.2
80.6:0.9
79.8422.4
5.7 Robustness Study
In order to validate the robustness of GraphChain, we evaluated GraphChain with different base models. The results are shown Table
Table 5: Performance with Different Base LLMs (accuracy %)
Financial Network
Chemical Molecule
Social Network
Citation Graph
Traffic Network
Base Model
Average
Qwen2.5-7B
70.5
81.1
90.4
79.0
82.0
80.6
Llama3.1-88 1-BB
69.3
81.7
93.7
82.5
81.7
81.8
GLM4-9B
70.2
78.9
93.8
79.7
79.9
80,5
The consistent superior results across different base models demonstrate the robustness and general applicability of our approach. We also conducted supplementary experiments using Qwen2.5 models of varying sizes (3B, 7B. and 14B). The Table show that GraphChain's 's performance improves with larger model sizes. Notably, even the smaller 3B model still maintain reasonable performance under our framework.
Table 6: Comparison of Base Models with Different Sizes (accuracy %)
Model Size
Financial Network
Chemical Molecule
Social Network
Citation Graph
Traffic Network
Owen2.5-3B
63.1%
56.9%
70.2%
74.4%
73.4%
Qwen2.5-7B
81.5%
81.1%
89.6%
83.6%
84.1%
Qwen2.5-14B
85.7%
85.4%
92.2%
83.2%
89.7%
Conclusions and Limitation
In this paper, introduced GraphChain, novel framework that enables LLMSs effectively process and reason over large-scale graph data through dynamic tool-chaining. By integrating progressive graph distillation with structure-aware test-time adaptation, GraphChain addresses the fundamental challenges of context exhaustion and reasoning hallucination that plague existing graph processing approaches. Our extensive experiments across diverse domains demonstrate that GraphChain significantly outperforms prior methods.
Our current implementation primarily focuses static graphs and may require adaptation for dynamic or temporal graph structures that evolve over time. The tool library used our experiments, though comprehensive, could be expanded to include more domain-specific operations for specialized applications. These limitations present valuable directions for future research.
Acknowledgments and Disclosure of Funding
This research was supported by NSFC 6N06625007 No.62132017 and No. No.U2433209), the Shandong Provincial Natural Science Foundation (No.ZQQ0221Q32), the Beijing Natural Science
10

---

Foundation (L247727), the Fundamental Research Funds for the Central Universities, the Research Funds of Renmin University China, and the Young Elite Scientists Sponsorship Program by CAST under contract No. 2022QNRC001. It was also supported by Big Data and Responsible Artificial Intelligence for National Governance, Renmin University of China
References
M. Alfarra, A. Correia, B. Ghanem, and C. Louizos. Test-time adaptation with source based auxiliary tasks. Transactions on Machine Learning Research, 2025.
A. Anthropic. The claude 3 model family: Opus, sonnet, haiku. In Claude-3 Model Card, 2024.
A. Barron, Rissanen, and B. Yu. The minimum description length principle coding and modeling. IEEE transactions on information theory, 44(6):2743-276)) 1998.
N. J. Beaudry and R. Renner. An intuitive proof of the data processing inequality, arXiv preprint arXiv:1107.0744 2011.
Z. Chai, T. Zhang, L. Wu, K. Han, X. Hu, X. Huang, and Y. Yang. Graphllm: Boosting graph reasoning ability of large language model. arXiv preprint arXiv:2310.05845, 2023.
N. Chen, Y. Li, J. Tang, and J. Li. Graphwiz: An instruction custructionffollowing language model for graph problems. CoRR, abs/2402. 16029, 2024a.
R. Chen, T. Zhao, A. K. Jaiswal, N. Shah, and Z. Wang. Llaga: Large language and graph assistant.
In International Conference on Machine Learning, pages 7809-7823, PMLR, 2024b.
W. Chen, L. Chen, Y. Xie, W. Cao, Y. Gao, and X. Feng. Multi-range attentive bicomponent graph convolutional network for traffic forecasting. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages
2020.
Z. Chen, K. Zhou, B. Zhang, Gong, W. X. Zhao, and J.-R. Wen. Chatcot: Tool-augmented chain- of-thhuugt reasoning on chat-based large language models. arXiv preprint 23X1::2305.14333 2023.
D. Das, Gupta, Srivastava, and D. Kang. Which modality should use-text, motif, or image?: Un- derstanding graphs with large language models. In Findings of the Association for Computational Linguistics: NAACL 2024, pages 503-519, 2024.
Y. Du, F. Wei, and H. Zhang. Anytool: Self-reflective, hierarchical agents for large-scale api calls. In International Conference on Machine Learning, pages 11812-11829 PMLR, 2024.
M. Fore, S. Singh, and D. Stamoulis. Geckopt: Llm system efficiency via intent-based tool selection. In Proceedings of the Great Lakes Symposium VLSI 2024, pages 353-354, 2024.
S. Gao, Z. Shi, M. Zhu, B. Fang, X. Xin, P. Ren, Z. Chen, J. Ma, and Z. Ren. Confucius: Iterative tool learning from introspection feedback by easy-to-difficult curriculum. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pages 18000-18036 2024.
V. Garg, S. Jegelka, and T. Jaakkola. Generalization and representational limits of graph neural networks. In International conference on machine learning, pages 1499-343.. PMLR, 2020.
T. GLM. Chatglm: A family of large language models from glm-130b to glm-4 all tools, 2024.
Y. Gu, Y. Shu, H. Yu, X. Liu, Y. Dong, J. Tang, J. Srinivasa, H. Latapie, and Y. Su. Middleware for 1mms: Tools are instrumental for language agents in complex environments. In Proceedings of the 2024 Conference Empirical Methods in Natural Language Processing, pages 7646-7663, 2024.
D. Guo. D. Yang, H. Zhang. J. Song, R. Zhang, R. Xu, Q. Zhu, S. Ma, P. Wang, X. Bi, al. Deepseck-rl: Incentivizing reasoning capability in 1lms via reinforcement learning. arXiv preprint arXiv:2501.1294 12948, 2025.
J. Guo, L. Du, H. Liu, M. Zhou, X. He, and S. Han. Gpt4graph: Can large language models understand graph structured data? an empirical evaluation and benchmarking. arXiv preprint arXiv:2305.75066, 2023,

---

E. J. Hu, Y. Shen, P. Wallis, Z. Allen-Zhu. Y. Li, S. Wang. L. Wang, W. Chen, et al. Lora: Low-rank adaptation of large language models. ICLR, 1(2):3, 2022.
T. Inaba, H. Kiyomaru, F. Cheng, and S. Kurohashi. Multitool-cot: Gpt-3 can use multiple external tools with chain of thought prompting. arXiv preprint arXivv2305./6686 2023.
A. Jaech, A. Kalai, A. Lerer, A. Richardson, El-Kishky, A. Low, A. Helyar, A. Madry, A. Beutel, A. Carney, et al. Openai ol system card. arXiv preprint arXi:22412.16720, 2024.
7. Jia, Y. Fan, C. Wei, and R. Yan. A spatial-temporal hypergraph based method for service recommendation in the mobile internet of mhings-enabled service platform. Adv. Eng. Informatics, 57:102038, 2023a.
Z. Jia, Y. Fan, J. Zhang, C. Wei, R. Yan, and X. Wu. Improving next location recommendation services with spatial-temporal multi-group contrastive learning. IEEE Trans. Serv. Comput., 16(5): 3467-3478, 2023b.
S. Kulinski and I. Inouye. Towards explaining distribution shifts, In International Conference on Machine Learning, pages 17931-17952. PMLR, 2023.
J. Leskovec and J. Mcauley. Learning to discover social circles in ego networks. Advances in neural information processing systems, 25, 2012.
X. Li. A review of prominent paradigms for Ilm-based agents: Tool use, planning (including rag), and feedback learning. In Proceedings of the 31st International Conference on Computational Linguistics, pages 9760-9779, 2025.
J. Liang, R. He, and T. Tan. A comprehensive survey on test-time adaptation under distribution shifts. International Journal of Computer Vision, 133(1):31-64, 2025.
Y. Liang, C. Wu, T. Song, W. Wu, Y. Xia, Y. Liu, Y. Ou, S. Lu, L. Ji, S. Mao, et al. Taskmatrix. ai: Completing tasks by connecting foundation models with millions of apis. Intelligent Computing, 3:0063, 2024.
X. Liu, Z. Peng, X. Yi, X. Xie, L. Xiang, Y. Liu, and D. Xu. Toolnet: Connecting large language models with massive tools via tool graph. arXiv preprint arXiv:2403.,m 00039, 2024.
L. Luo, Y.-. Li, G. Haffari, and S. Pan. Reasoning on graphs: Faithful and interpretable large language model reasoning. arXiv preprint arXiv:2310.01066 2023.
X. Ma, J. Zhang, S. Guo, and W. Xu. Swapprompt: Test-time prompt adaptation for vision-language models. Advances in Neural Information Processing Systems, 36:65252-65264 2023.
D. Mekala, J. Weston, J. Lanchantin, R. Raileanu, M. Lomeli, J. Shang, and J. Dwivedi- Yu. Toolveri- fier: Generalization to new tools via self-verification. In Findings of the Association for Computa- lional Linguistics: EMNLP 2024, pages 5026-5041, 2024.
D. Muhtar, Y. Shen, Y. Yang, X. Liu, Y. Lu, J. Liu, Y. Zhan, H. Sun, W. Deng, F. Sun, et al. Strea- madapter: Efficient test time adaptation from contextual streams. arXiv preprint arXiv:2411.09288 2024.
R. Nakano, J. Hilton, S. Balaji, Wu, Ouyang, C. Kim, C. Hesse, Jain, Kosaraju, W. Saunders, et al. Webgpt: Browser-assisted -uession-answering with human feedback. arXiv preprint 12.03:211..09333. 2021.
OpenAl. GPT-4 technical report. CoRR, abs/2303.08774 2023.
S. Qiao, H. Gui, C. Lv, Q. Jia, H. Chen, and N. Zhang. Making language models better tool learners with execution feedback. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 3550-3568, 2024.
Y. Qin, X. Wang, Z. Zhang, P. Xie, and W. Zhu. Graph neural architecture search under distribution shifts. In International Conference on Machine Learning, pages 18083-18095, PMLR, 2022.
12

---

Y. Qin. S. Liang, Y. Ye, K. Zhu, L. Yan, Y. Lu, Y. Lin, X. Cong, X. Tang, B. Qian, et al. Toolllm: Facil- itating large language models to master 16000+ real-world apis. arXiv preprint arXiv:2307.1678, 2023.
C. Qu, S. Dai, X. Wei, H. Cai, S. Wang. D. Yin, J. Xu, and J.-R. Wen. Tool learning with large language models: survey, Frontiers of Computer Science, 19(8):198343, 2025.
D. Ramasamy and U. Madhow. Compressive spectral embedding: sidestepping the svd. Advances in neural information processing systems, 28, 2015.
T. Schick, J. Dwivedi- Yu, R. Dessi, R. Raileanu, M. Lomeli, E. Hambro, L. Zettlemoyer, N. Cancedda, and T. Scialom. Toolformer: Language models can teach themselves use tools. Advances in Neural Information Processing Systems, 36:68539-685555 2023.
J. Schulman, P. Moritz, S. Levine, M. Jordan, and P. Abbeel. figh-dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv: 024388, 2015.
J. Schulman, F. Wolski, P. Dhariwal. A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1rXivv1707.00m 170.066377 2017.
Y. Shen, K. Song, X. Tan, D. Li, W. Lu, and Y. Zhuang. Hugginggpt: Solving ai tasks with chatgpt and its friends in hugging face. Advances in Neural Information Processing Systems, 36:38154-38180, 2023.
Y. Shen, K. Song, X. Tan, W. Zhang, K. Ren, S. Yuan, W. Lu, D. Li, and Y. Zhuang. Taskbench: Benchmarking large language models for task automation. Advances in Neural Information Processing Systems, 37:4540-45774 2024.
B. Shi, Y. Wang, F. Guo, B. Xu, H. Shen, and X. Cheng. Graph domain adaptation: Challenges, progress and prospects. arXiv preprint arXiv:2402.0080 2024a.
W. Shi, R. Xu, Y. Zhuang. Y. Yu, H. Sun, H. Wu, C. Yang, and M. D. Wang. Medadapter: Efficient test-time adaptation of large language models towards medical reasoning. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 22294-2233 2024b.
M. Shu, W. Nie. D.-A. Huang, Z. Yu, Goldstein, A. Anandkumar, and C. Xiao. Test-time prompt tuming for zero-shot generalization in vision-language models. Advances in Neural Information Processing Systems, 15:14274-14289, 2022.
Y. Song, W. Xiong, D. Zhu, W. Wu, H. Qian, M. Song, H. Huang, C. Li, K. Wang, R. Yao, et al. Restgpt: Connecting large language models with real-world restful apis. arXiv preprint arXiv:2306.088 06624, 2023.
B. Su, D. Du, Z. Yang, Y. Zhou, J. Li, A. Rao, H. Sun, Z. Lu, and J.-R. Wen. A molecular multimodal foundation model associating molecule graphs with natural language. arXiv preprint arXiv:2209.08 05481, 2484042,0,, 2022.
M. Suzgun, M. Yuksekgonul, F. Bianchi, D. Jurafsky, and J. Zou. Dynamic cheatsheet: Test-time learning with adaptive memory. arXiv preprint arXiv:2504.09952 2025.
Y. Tan, Z. Zhou, H. Lv, W. Liu, and C. Yang. Walklm: A uniform language model fine-tuning framework for attributed graph embedding. Advances in neural information processing systems, 16:1388-13325 2023.
J. Tang, Y. Yang, W. Wei, L. Shi, L. Su, S. Cheng, D. Yin, and C. Huang. Graphgpt: Graph instruction tuning for large language models. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 491-500, 2024a.
J. Tang, Y. Yang, W. Wei, L. Shi, L. Xia, D. Yin, and C. Huang. Higpt: Heterogeneous graph language model. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2842-2853, 2024b.
N. Tishby and Polani. Information theory of decisions and actions. In Perception-uction cycle: Models, architectures, and hardware, pages 601-636. Springer, 2010.
13

---

B. Wang. A proactive system for supporting users in interactions with large language models. In Proceedings of the 2024 Conference on Human Information Interaction and Retrieval, pages 1411-44,,22 2024.
D. Wang. Y. Zuo, F. Li, and J. Wu. Lims as zero-shot graph learners: Alignment of gnn representations with Ilm token embeddings. Advances in Neural Information Processing Systems, 11:5550-5973 2024a.
H. Wang, S. Feng, T. He, Z. Tan, X. Han, and Y. Tsvetkov. Can language models solve graph problems in natural language? In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023a.
H. Wang. S. Feng. T. He, Tan, X. Han, and Y. Tsvetkov. Can language models solve graph problems in natural language? Advances in Neural Information Processing Systems, 36:30840-30861, 2023b.
J. Wang. J. Wu, Y. Hou, Y. Liu, M. Gao, and McAuley. Instructgraph: Boosting large language mod- els via graph-centric instruction tuning and preference alignment. In Findings of the Association for Computational Linguistics ACL 2024, pages I 13492-13510, 2024b.
Q. Wang. Z. Gao, and R. Xu. Graph agent: Explicit reasoning agent for graphs. arXiv preprint 1rX14:2310.16421, 2023c.
R. Wang, S. Liang, Q. Chen, J. Zhang, and K. Qin. Graphttollinnstration:: Revolutionizing graph reasoning in Ilms through decomposed subtask instruction. arXiv preprint arXiv:2412.12152 2024c.
R. Wang, X. Han, Ji, S. Wang. T. Baldwin, and H. Li. Toolgen: Unified tool retrieval and calling via generation. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net, 2025.
M. Weber, G. Domeniconi, J. Chen, D. K. I. Weidele, C. Bellei, T. Robinson, and C. E. Leiserson. Anti-money laundering in bitcoin: Experimenting with graph convolutional networks for financial forensics. arXiv preprint arXiv: 02591, 2019.
C. Wei, B. Bai, K. Bai, and F. Wang. Gsl4rec: Session- recommendations with collective graph structure learning and next interaction prediction. In F. Laforest, R. Troncy, E. Simperl, D. Agarwal, A. Gionis, I. Herman, and L. Médini, editors, WWW '22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 29, 2022, pages 2120-2130. ACM, 2022a.
C. Wei, Y. Fan, and J. Zhang. High-order social graph neural network for service recommendation. IEFE Trans. Netw. Serv. Manag., 19(4):4615 4628, 2022b.
C. J. Liang. B. Bai, and D. Liu. Dynamic hypergraph learning for collaborative filtering. In M. A. Hasan and L. Xiong, editors, Proceedings of the 31 ACM International Conference on Information & Knowledge Management, Atlanta, GA, USA, October 17-21, 2022, pages 2108-2117. ACM, 2022c.
C. Wei, J. Liang, D. Liu, and F. Wang. Contrastive graph structure learning via information bottleneck for recommendation. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information P Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022d.
C. Wei, Y. Fan, and J. Zhang. Time-aware service recommendation with social-powered graph hierarchical attention network. IEEE Trans. Serv. Comput., 16(3):2229-22444 2023a.
C. Wei, J. Liang, D. Liu, Z. Dai, M. Li, and F, Wang. Meta graph learning for long-tail recommenda- tion. In A. K. Singh, Y. Sun, L. Akoglu, D. Gunopulos, X. Yan, R. Kumar, F. Ozcan, and J. Ye, editors, Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023, Long Beach, CA, USA, August 6-10, 2023, pages 2512-2522. ACM, 2023b.
14

---

C. Wei, Y. Wang, B. Bai. K. Ni, D. Brady, and L. Fang. Boosting graph contrastive learning via graph S. Sabato, and J. Scarlett,
contrastive saliency. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, editors, International Conference on Machine Learning, ICML, 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 36839-3688 PMLR, 2023c.
C. Wei, Y. Fan, Z. Jia, and J. Zhang. Cross-view graph alignment for mashup recommendation. IEEE Trans. Serv. Comput., 17(5):215122164 2024a.
C. Wei, Y. Fan, J. Zhang, Z. Jia, and R. Yan. Dynamic relation graph learning for time-aware service recommendation. IEEE Trans. Neww Serv. Manag. (1(2)1503-1111 2024b.
C. Wei, W. Hu, X. Hao, Y. Wang, Y. Chen, B. Bai, and F. Wang. Graph evidential learning for anomaly detection. In L. Antonie, J. Pei, X. Yu, F. Chierichetti, H. W. Lauw, Y. Sun, and S. Parthasarathy, editors, Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining, V.2, KDD 2025, Toronto ON, Canada, August 3-7, 2025, pages 3122-3133, ACM, 2025.
Wei, X. Wang. D. Schuurmans, M. Bosma, Xia, E. Chi, Q. V. Le, D. Zhou, et al. Chain-of-thougle prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824- 24837, 2022e.
R. J. Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8:229-256, 1992.
Z. Wu, B. Ramsundar, E. N. Feinherg, J. Gomes, C. Geniesse, A. S. Pappu, K. Leswing, and V. Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 9(2::113-530, 2018.
Q Xu, F. Hong, B. Li, C. Hu, Z. Chen, and J. Zhang. On the tool manipulation capability of open-source large language models. arXiv preprint arXiv:2305. 2023.
R. Yang, L. Song, Y. Li, S. Zhao, Y. Ge, X. Li, and Y. Shan. Gpt4tools: Teaching large language model to use tools via self-instruction. Advances in Neural Information Processing Systems, 36: 71995-72007, 2023.
Z. Yang. W. Cohen, and R. Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pages 40-48. PMLR, 2016.
Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Cao. React: Synergizing reasoning and acting in language models. In International Conference on Learning Representations (ICIR), 2023.
R. Ye, C. Zhang R. Wang, S. Xu, and Y. Zhang. Language is all a graph needs. In Findings of the Association for Computational Linguistics: EACL 2024, pages 1955-1973, 2024.
Y. Yu, Z. Wang, W. Ma, Z. Guo, Zhan, S. Wang, C. Wu, Z. Guo, and M. Zhang. Steptool: A step-grained reinforcement learning framework for tool learning in 1lms. arXiv preprint arXiv:2410.07745, 2024.
J. Zhang. Graph-toolformer: To empower Ilms with graph reasoning ability via prompt augmented by chatgpt. CoRR, abs/2304.1 1116, 2023a.
J. Zhang. Graph-toolformer: To empower Ilms with graph reasoning ability via prompt augmented by chatgpt. arXiv preprini 2rXiv:2304. /1116, 2023b.
K. Zhang, H. Zhang, G. J. Li, Z. Li, and Z. Jin. Toolcoder: Teach code generation models to use api search tools. arXiv preprini arXiv:2305.04032 2023.
X. Zhang, A. Bosselut, M. Yasunaga, H. Ren, P. Liang, C. D. Manning, and J. Leskovec. Greaselm: Graph reasoning enhanced language models for question answering. arXiv preprint arXiv:2201.08880, 2022.
15

---

X. Zhang, C. Wei, R. Yan, Y. Fan, and Z. Jia. Large language model ranker with graph reasoning for zero-shot recommendation. In M. Wand, K. Malinovská, Schmidhuber, and I. V. Tetko, editors, Artificial Neural Networks and Machine Learning- ICANN 2024 33rd International Conference on Artificial Neural Networks, Lugano, Switzerland, September 17-20, 2024, Proceedings, Part V, volume 15020 of Lecture Notes in Computer Science, pages 356-370. Springer, 2024a
X. Zhang, R. Yan, Y. Fan, J. Zhang, H. Yuan, and C. Wei. Cross-domate attention transfer network for recommendation. Adv. Eng. Informatics, 68: 103667, 2025.
Y. Zhang, H. Wang, S. Feng, Z. Tan, X. Han, T. He, and Y. Tsvetkov. Can Ilm graph reasoning generalize beyond pattern memorization? In Findings of the Association for Computational Linguistics: EMNLP 2024, pages 2289-2305, 2024b.
J. Zhao, M. Qu, C. Li, H. Yan, Q. Liu, R. Li, X. Xie, and J. Tang. Learning on large-scale text- attributed graphs via variational inference. arXiv preprint 2XXx:22100.1709, 2022.
Zhao, L. Zhuo, Y. Shen, M. Qu, Liu, M. Bronstein, Z. Zhu, and J. Tang. Graphtext: Graph reasoning in text space. arXiv preprint arXiv:2310.01089, 2023.
J. Zhao, H. Mostafa, M. Galkin, M. Bronstein, Z. Zhu, and J. Tang. Graphany: A foundation model for node classification on any graph. arXiv preprint arXiv:2405.20445 2024.
Y. Zhu, Y. Wang, H. Shi, and S. Tang. Efficient tuning and inference for large language models on textual graphs. In Proceedings of the Thirty-Third International Joint Conference Artificial Intelligence, pages 5734-5742, 2024.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Our abstract and introduction clearly claim our task (scope), contributions and
solutions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitation in Conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
17

---

Justification:
We provide all the proof in Appendix A
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide our code in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
18

---

Answer: [Yes]
Justification: We provide our code in the supplementary material. And we provide a github repository containing the code in https//gghhu..oommmmaaiccciililp
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https
ssicnlolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: In the Appendix [and
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We conduct two-sample t-tests, and p-value < 0.05 indicates that the improve- ments are statistically significant.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
19

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: In the Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://awrrp....p.p...../aaaaaaa
Answer: [Yes]
Justification:
This research conforms, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
In appendix H
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
20

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: Not Applicable.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
We cite the original papers or website links about the dataset and open-source codes.
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.papersstt
package should be provided. For popular datasets, paperswi thcode. cww/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
21

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Not Applicable.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Not Applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Not Applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
22

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: Not Applicable.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy fattps://neuripe::: /ttpaarrpp..cc//ooofeeeeeee////s for what should or should not be described.
23

---

A Proof of Proposition 4.1
We start with the fundamental assumptions:
1. The input X is generated from underlying factors including task-relevant information Y and iask-irrelevant information TR.
2. The process forms Markov chain: (Y, TR) - X -> my This signifies that the memory state m, is generated based on the input X, which itself is derived from the underlying factors (Y, IR).
3. The optimization objective derived from the reward function R2 (Eq, 5 encourages policies that produce trajectories where intermediate states m, have high task relevance Rel(m,, Q) and low complexity/volume GDL(mm))
4. Based on the proposition's 's statement, maximizing relevance correlates with maximizing IY; my). and minimizing GDL correlates with minimizing the overall information captured from the input, I [(X; m.).
According to the Data Processing Inequality (DPI) [Beaudry and Renner 2011] applied to the Markov chain (Y, /R) + X - m,, the information that the final representation m, retains about the initial factors (R) cannot exceed the information it retains about the intermediate variable X:
I((Y, IR); m.) S ((X;m.)
(9)
Now, we apply the chain rule for mutual information to the term on the left-hand side:
T((Y, RR); m.) (Y:m)) + [(TR; m:lV)
(10)
Here, T(Y; m.) represents the information that the memory state m, contains about the relevant variable Y. The term [[[:; m,lY) represents the additional information that m, contains about the irrelevant variable /R, given that the relevant information Y is already known. This term
quantifies the amount of irrelevant information captured by m, beyond what is already explained by its correlation with Y.
Substituting the expansion from Eq. into the DPI (Eq. 9), we obtain:
I I(Y; m²) ((RR; m. YY) s ((;m.)
(11)
Rearranging this inequality gives us an upper bound on the conditional mutual information involving the irrelevant component:
m./Y) s I(X; I(;; m.)
(12)
This inequality shows that the amount of irrelevant information retained in m, (conditioned on the relevant part Y) is upper-bounded by the difference between the total information m, captures from the input X and the useful information it captures about the target Y.
Now, let's consider the optimization objective implied by the progressive distillation reward function (Eq. 5). This objective aims to find a policy Te that maximizes the expected return. The reward structure encourages steps that increase relevance (proxy for I(Y; m))) and decrease GDL (proxy for I [X; my)). Thus, the optimization process implicitly seeks intermediate states m, that achieve a trade-off, aiming for:
* High I(Y; m.) (maximize information about the answer)
Low I(X; m²) (minimize total information stored, i.c., compress the input)
By striving to maximize [Y; m²) and minimize (XX; m.). the optimization process is effectively attempting to minimize the upper bound T(X; m.) - m(): found in Eq.
Minimizing this upper bound serves as a direct mechanism to suppress the amount of irrelevant information [IR mY\Y) contained in the memory state m,, Therefore, optimizing the distillation- aware reward function encourages the policy to generate representations that form an information bottleneck, preserving relkvntl information while actively discarding task-irrelevant information, quantified by the bound derived from the Data Processing Inequality.
24

---

Query:
Help me identiily the lergest simple cycle this transfer graph, and then determine which transactions within this cycle have amounts exceeding 1,000,000.
GraphChain' Analysis Process
Step
Thought:
darify type the graph multidgraph, faclitate subsequent cycle detection needs converted undirected graph which can complexity caused direction asues during tycle detection. to undirected function NetworkX library convert multidigrahh undirected graph.
Action.
<API>to (nddireeted(</AAP)))
Result:
The result is not dictionary object, but graph object named undircteedgrpph
Result Description:
undrectedgraph the undirected graph obtained after conversion, with the direction of edges removed to faciltate subsequent cycle detection operations. You can proceed with cydle detection and other operatioon ons on undirettedgraph; such as using other functions from NetworkX to process this graph. (The number of tokens the result exceeds the limit of the contest window at this point.)
Step 2
Thought
the simple cycles within the graph, simple function used for this purpose, which returns a simple cycles the graph, with each simple eycle represented as nodes.
After obtaining the undirected graph, it necessary
Actions
<API>simple, cycles </APP>>>
Result
The variable lorgestcydl
the of largest cycle where the cycle is represented as list of nodes.
Result Description:
largestrycle contains the largest cycle the graph represented
of nodes
You can proceed with further operations on largsttyyll,, such checking the weights the edges within the cydle
(The number of tokens the result exceeds the limit of the context window at this point)
Step 3
Thought:
For the largest sycle, is necessary to tally the weights of all edges within the cycle. The get edge datall function required to obtain the weight of each edge. Subsequently. each edge in the sycle hteatee over to determine whether its weight exceeds 1,000.000.
Action
<API>get_ aeee__dee_____ee datat)<//aP))
Result:
For largest sycle, necessary taily weights all edges the cycl. The get edge datail function requied obtain weight of wiight of edge 1,000,000 by feeraing through edge cycle
edge,
fitteeedges
stores the fittered
represented dictionary composed of target, weight.
You through fittredges output final
(The number of
the result
the
the context window, the input to large language model the form of text)
Step 4 ................................
Thought:
and fitered out the with weights exceeding 1,000,000, which fellows][[source" 248. "target" 963 weight": 6391000), I'source's "target" "weight" 0975610), ("source', 72, "target": 647. 'weight":
Through the first three steps, have successfully extracted the largest sycle
2402500), I'source', 31, "target": "weight" 1297921), ('source' 96, "target": "weight". 2553000)
Action
<API>Finise ih--aanee swer</APIS
Answer After analyzing the cycles in the given transfer graph. we identified the largest cycle and fittered based on weight. The results are as follows: The ist edges with weights exceeding 1,000,000 is If source"; 2449. "taget": 963, "weighe" 6393000, ('source" "target: 92, "weight" 8975610) "teget": q. "wiigtt: 2553000)).
("source") 72, "wrget": 647, "weight" 2402500) ('source" 31. "trget": 96, "weigh": 1297921). ("source"
Figure 6: A typical case of GraphChain on Financial Networks.
B Case Study
We present a case study in Figure 0 involving a transmission network from the Elliptic Dataset, comprising 11,896 nodes and 31, 155 edges exceeding the context processing capabilities of current LLMs. GraphChain demonstrates robust capability to systematically handle this task through series of tool invocations. The Progressive Graph Distillation mechanism enables iterative reduction of information complexity, focusing on the most salient features.
Due to context window limitations, we store intermediate processing results in memory rather than directly inputting them into the LLM. The model outputs detailed descriptions of current processing results and their usage methods to facilitate further analysis. Only when intermediate results' token count falls below the maximum context window limit are they directly input into the LLM, maximizing the model's advantages while minimizing limitations.
C Details of Experimental Setup
We provide comprehensive details on our experimental setup to ensure reproducibility. All experi- ments were conducted on NVIDIA A800 80GB GPUs, using LoRA-based fine-tuning (rank r=16, alpha=32) on the Qwen2. S--B-innstee instrructitoon model.
C.1 Training Configuration
Our training pipeline consisted of three main stages:
25

---

Table 7: Comparison baseline methods and their corresponding models for graph reasoning.
LLM Type
Open Source
Method
Base Model
X
Two-shot
Claude-series Anthropic
2024
X
Two-shot
GPT-series
OpenAl
2023
Text Instruction
NLGraph
Wang et al.
2023a
GPT-4-ture
GraphWiz
Chen et al.
2024a
Llama2- -1BB
X
Function Calling
8PT-3.5-turbo
O OpenAl 2023
X
Function Calling
GPT-4o (OpenAl
2023
Tool Instruction
X
Function Calling
GLM4-0522 [GLM 2024
Zhang
2023a
Ll Llama3-8B
GraphForge
WWng 2024c
L1 Llama3-89
Supervised Fine-Tuning (SFT) Stage: We used learning rate of 5 10-3 with 4% warmup and a cosine scheduler for 8 epochs. This initial phase established the model's ability to follow graph reasoning instructions.
Reinforcement Learning (RL) Stage: We implemented Proximal Policy Optimization (PPO) with step-level rewards, departing from traditional RL.FF approaches that apply rewards solely to the final step. Our implementation used:
Learning rate:
10-5
Batch size:
Initial KL. coefficient: 0.3
Loss coefficient (3): 0.15
GAE parameter (A): 0.95
Discountt factor (7): 0.99
Test-Time Adaptation Stage: For the structure-aware adaptation mechanism, we configured:
Learning rate: 0.01
Batch size:
C.2 Inference Settings
During inference, we used temperature of 0.7 and top-p value of 1.0, optimizing for balance between diversity and coherence in the generated tool chains.
Complete configuration files and scripts are available our code repository facilitate reproduction of our results.
D Baseline Implementation
To comprehensively evaluate GraphChain, implemented several state-of-the-art graph reasoning basclines spanning both Text-Instruction and Tool- Instruuntttttion paradigms. Table summarizes these baseline methods and their corresponding backbone models.
D.1 Text-Instruction Methods
For closed-source LLMs (Claude-series, GPT-series, and GLM4-0520), employed shot Chain -iii--ofoooooo Thought (CoT) prompting to stimulate structured reasoming, Table g illustrates our prompting approach with an example.
For specialized graph reasoning methods, we reproduced:
GraphWiz: We reimplemented using the Llama2-133 backbone with a learning rate of 2e-5 for epochs and maximum sequence length of 2048. During inference, temperature was set to 0 with maximum output tokens of 1024 to ensure stable generation.
26

---

Table 8: Example two-shot prompting used text-instruction baselines.
Prompt Template
You are Al assistant specialized graph reasoning. For each problem, first extract the graph structure, then solve the task step by step.
Example 1:
Input: Given weighted directed graph with edges: [(O, 2, (weight': 3}), (0, 3,
(weight': 73), (1, O, ('weight': 2}), (1, 4, ('weight'; 83), (2, 4,
(wweight': 1)), (3, 4, ('weight': 3})]. Find the shortest path from node to
node 4.
Reasoning: First, I'll extract the graph structure.
Graph: [(O, 2, (weiihh': 3}), (0, 3, ('weight': 7)), (1, 0, (weighh': 2}), (1, 4, ('weight': 8)), (2, 4, ('weight:; 1)), (3, 4, ('wiihht: 3})]
Now I'll find the shortest path from node 1 to node 4.
Direct path: 4 with weight
Indirect path: 1 + 0 2 + 4 with weight 2 3 + 1 =
Indirect path: 1 + 0 3 + 4 with weight 2 7 + 3 = 12
The shortest path is + 0 2 with total weight 6.
Answer: The shortest path from node 1 to node 4 is 1 0 2 with total weight 6.
Example 2:
Input: Given undirected graph with edges: [(o, 1), (0, 3) (1, 2), (1, 4), (2, 5), (3, 4), (4, 5)]. Determine if there exists a cycle in this graph.
Reasoning: Let me extract the graph structure.
Graph: [(O, 1), (0, 3), (1, 2), (1, 4), (2, 5), (3, 4), (4, 5)
To check for cycles, I'll trace possible paths:
Starting from node 0: 0 1
4 3
This forms cycle:
3
Answer: Yes, there exists cycle in the graph. Now solve the following problem:
Input: [Problem description]
NLGraph: Following the original implementation, we provided exemplars for connectivity and cycle tasks, and 5 exemplars for other tasks due to context size limitations. For fair comparison, we used the standardized test set across all experiments.
D.2 Inst-unstn Methods
We implemented augmeneddd approaches including:
Graph-ToolFormer: We reimplemented this approach based on the Llama3-8B model using LoRA (rank r=16, alpha=32) with learning rate of lc-5 and weight decay of le-2 for epochs. For generation, we used beam search with beams, top-k of 5, top-p of 0.95, and temperature of 0.7.
GraphForge: We implemented based on Llama3-88 BB using LoRA (rank r=16, alpha=32) with learning rate of 5e-5 for 5 epochs. Inference settings matched our GraphChain configuration with temperature of 0.7 and top-p of 1.0.
Function Calling: For closed-source models supporting function calling (GPT-3.C 3-9T-3.5tuure 5-turbo, GPT-4o, and -LM4-, we implemented the same graph processing functions used in GraphChain as external API tools, allowing these models to leverage structured tool invocation capabilities during inference.
baseline implementations were executed using same hardware setup as GraphChain: two NVIDIA A800 GPUs for fine-tuning and inference with open-source models. For closed-source models, we utilized their respective official API interfaces. To ensure fair comparison across all methods, we partitioned original graphs into subgraphs with fewer than 100 nodes for evaluation,
27

---

Table 9: NetworkX Functions Categorized by Graph Analysis Task
Category
NetworkX Functions
Basic Graph Properties
ww..umbe_ooo o__oddes (), G. number_off of _ed__dgeea G. washaasseee (n), G. G.has_ edge(u, (u, v), G. degrree O)
G.in_degree () G. out_degree((,
G. S.get_edge_datatu, v)
Centrality Metries
nx. www.beeeeeessseenttraiiityy
nx. www.ceeeeessccmrrallttt....)
nx. www.degree..enttralttt//////
nx. wt.eeaaaveccoor_cnntrrallyy.y...
nx.harroonicc_enntrralltyy)>)>>
nx. www.perrcolaatioon.cettrraalyyy
nx ww..second_orderr.cettaaaatttty
nx. ww..sugrraph.cetrraaityyy
Connectivity and Compo-
nx www.ssangly_ccmmetteecccooprpeee (),
nents
nx. nx. www.eally_ccnaatteecccooooonneee
m..arriiccllaiiooooootttt(t..t( nx. nx.bridges
nx. nx. xx.keellge_coomonnnttt>>>
nx. ox.k_nodee_compponettt)) nx. nx.node_commectivvtyy/ nx. nx.edge_.comectiittt()
Shortest Paths and Distances
nx. ww..ll.paars.hhorssss.aaaa. nx. nx. ww..al.ppas.shhrrttt.ptat...ee () nx. nx.di.jkstrappatt()) nx. ww.diiikstra.pathhleegghh mx.floyd_varshall()
Clustering and Communities
nx. av..vvrage.cluuseeringg))) nx. clustering(),
nx. ww..transitiivityy) nx. traaagless)
nx. www.abel_.rppggtttooocoomm..mm nx. nn..ouvain_coomunttie
Flow Algorithms
nx. nx. www.oo//oo.koLnggrrrrriiii..uuu
nx mx.dinic_min_cutt]
nx. ww.eddoodss_karr.ninn_ctt// (), www.mmmmmmmutttt....mmmmm
Cycle Detection
nx. www.sipple..cclless.nxx.ccccleee
Topological Sorting
nx. topological.sortt).
nx. ww..i.ddreectel.ccccl.....po.pp
nx all aall_ttopoloiicallortt.... nx. www.tooogicllleeerrrttoooooooeee generationn()
while separately testing GraphChain's scalability on full-sized graphs with up to 200,000 nodes in Section 5.4]
E
Graph Analysis Tool Library
To construct effective graph question-answering system, we selected 45 functions from the NetworkX library through a systematic review of graph analysis tasks prevalent in academic research and practical applications. Table 9 shows the complete list of selected functions. The selection process prioritized coverage of eight core dimensions of graph analytics:
Basic Graph Properties Functions providing structural metadata, including node/edge counts, degree distributions, and adjacency queries.
Centrality Metrics Measures for node influence, spanning degree centrality to advanced methods (eigenvector, percolation, and Katz centrality).
28

---

Connectivity and Components Tools for evaluating graph robustness, such as articulation points, bridges, and strongly/weakly connected components.
Shortest Paths and Distances Algorithms for unweighted and weighted paths, critical for routing and diffusion modeling.
Clustering and Communities Modular structure analysis via clustering coefficients and detection algorithms (e.g., label propagation, Louvain).
Flow Algorithms Maximum flow and minimum cut computations using multiple methodolo- gies (e.g., Edmonds-Karp).
Cycle Analysis Feedback loop identification in directed and undirected graphs.
Topological Sorting Dependency resolution for directed acyclic graphs (DAGs).
While not exhaustive, this set was carefully selected balance analytical breadth and computational efficiency, ensuring system responsiveness and interpretability. Future work may integrate domain- specific higher-order analytics, but this toolset is representative and sufficient for general-purpose graph analysis.
F
Data Construction
This section details the creation of datasets used for training and evaluating GraphChain, including fine-tuning data and graph datasets across five real-world scenarios.
F1 Fine-tuning Dataset
We constructed comprehensive and robust dataset for fine-tuning GraphChain through systematic, multi-faceted approach:
F1111 SFT Dataset Construction
We curated 45 commonly used APIs from the NetworkX library based relevance and usage frequency in graph-related tasks. ensure diverse instruction coverage, we employed ChatGPT to generate various instructions tailored these APIs. For each iteration, randomly sampled APIs and prompted ChatGPT to reverse-engineer instructions centered around them, ensuring comprehensive coverage across the API set.
To enhance practical relevance, human experts crafted three exemplar instructions for each subgroup within five distinct real-world graph scenarios. These expertly designed prompts served as high- quality references, grounding the dataset in realistic use cases.
Our structured prompting strategy guided ChatGPT to produce outputs in a standardized format:
(Thought:
...Action: ...)
Each action explicitly invoked API with required parameters (e.g.. G. gegg_edge_____eeeeeeee data (8, 0, default=None)). The outputs were fed into a code generator to produce executable code, which was then executed to obtain results formatted as:
("error": "...", "response": "..."}
These results were appended to the input for subsequent steps, creating a coherent action sequence. We introduced two auxiliary functions: finish->answer (signaling successful task completion) and Finish->gi Seat->-iveep__aaee and__aud_p__eeeeeeeeeee and_rsaard (allowing model reset and retry in cases of persistent errors).
Through this pipeline, generated 9,986 (instruction, solution path) pairs that encapsulate wide range of API-driven tasks reflecting the complexity of real-world graph- based problem-solving. Table II shows example from our SFT dataset.
F.1.2 RL Dataset Construction
For the reinforcement learning phase, we constructed a dataset with reward values for each step. We used GPT-4 to score each step based on three dimensions:
29

---

Table 10: The prompt template for constructing SFT dataset.
Category
Description
Dataset Name
Citation-Networkk txt
Dataset Type
MultiDirected Graph
Dataset Con-
The citation data between research papers. Directed edge to B means that paper A cites paper B. The graph construction operation is: = nx nx. ww..uutiiiii MultiDiGraph O,, G. G.ddd_ add__dee (paper1, paper2),
tent
where paper1 and paper2 research papers. String type is used to store nodes.
Task
Generate complex graph problem and its step-by-step solution process.
Output Type
JSON
Output Rules
(1) The output must be a JSON containing series of "from" and "value" as shown in the example, using English.
(2) Provide the user problem in "value" under "user", generate the
sponse in "value" under "assistant", and generate API return results in "value" under "function".
(3) The output can have only this JSON data with no additional informa- tion.
(4) Follow the format of the example but exclude the key name "exam- ple".
Special Atten-
In the "assistant" response, provide detailed thought processes without code, using NetworkX methods. Mark called APIs with <API>... </APPI,, e.g. <API>nx. (rfixx.dfs__. wft_ddfaaeeeeeedd.. eegeedggeegrrrrr (graph, cource=10)</APP) Format outputs as:
tion
Thought:
Action: <API>... </APPI>
When <API>...</AB> is encountered, provide "function" with fabri- cated API results:
{"error": "", "response": ""}
Continue this process until final result. Final "assistant" format should
be:
Thought:
Action: <APPFiinishh>aaswerr///
Answer:
Or:
Thought:
Action:
Design quirement
Re-
Design Q& A around the (API_NUM, APIs {API_AAINHNN [MP_]_AMM)... Focus collaboration between APIs, where later APIs utilize results from previous for further reasoning.
Whether the tool invocation the current step is valid Thought and API Effectiveness: The relevance of the tool selection to solving the query
API Correctness:
Graph Distillation: Whether the tool reduces the information content of the graph data
Table 12
shows the prompt template used for RL data construction.
Table
13
shows two examples from our RL dataset with corresponding evaluation scores.
F.2
Graph Dataset
We extracted subgraphs from existing real- world datasets to construct graph datasets for five scenarios, each corresponding different graph types:
Financial Networks: From the Elliptic dataset, containing Bitcoin transaction graphs
Chemical Molecules: From the QM9 dataset, including molecular structure graphs where atoms are nodes and chemical bonds edges
30

---

Table 11: Example of SFT data with step-by-step reasoning and API calls.
From
Value
User
How to identify the neighbor nodes node 15 and analyze the fund flow between these neighbor nodes? Begin!
Assistant
To identify the neighbor nodes of node 15 and analyze fund flow between them, we need to proceed step by step. First, obtain all direct neighbor nodes of node 15 and transaction information. Then analyze fund flow between these neighbors.
Thought:
Let's obtain neighbor nodes and transaction information using <API>graph. out_ odg__eees__aeee (15, data=True) </API> and
<API>graphe iiniiineediin edges (15, (ata=True)<<APP)) get all outgoing and incoming edge information.
Action: <API>graph out_edges (15, data-True)
Function
("error": "" "response": "Direct outgoing
transaction information of node 15: (15, 16, ('weight': 400.0, 'date': '2022-06-10'))
(15, 17, {'weight': 200.0, 'date": 2022-07-01'3)
Assistant
Thought: Continue by obtaining incoming transaction information.
Action: <API>graph. in_eedgeesssseeeeeeeeee (15, data=True)</PP>>>
Function
{"error": "" "response": "Direct incoming
information for node 15:
-100, 15, ('weight'; 880.0, O, 'date': 22022- 2022-05-20'3)
Assistant
Thought: Now we' ve identified neighbor nodes of 15 are 10, 16, and 17. Next, analyze fund flow between these neighbors using
<API>graph. subgraph [10, 16,
edgess (iaat==True</APP11
Action: <API>graph. <aPiggraph.eubgraap 16,
17]) edgee (dtters
Function
("error": "", "response": "(10, 16, ('weight':
300.0, 'date': (2022-06-05
(10, 17, {'weight': 100.0, 'date": '2022-06-15'3)
(16, 17, {'weight': 50.0, 'date': "2022-07-10"})")
Assistant
Thought: Based on this information, we can draw conclusions: Node 10 transferred 880 yuan node 15, 300 yuan node 16, and 100 yuan node 17. There is also fund flow between nodes 16 and 17, with node 16 transferring 50 yuan to node 17.
Action:
Answer: Node 10 only transferred 880 yuan node 15, but also transferred 300 yuan to node 16 and 100 yuan to node 17. There is also fund flow between nodes 16 and 17, specifically, node 16 transferred 50 yuan to node 17.
Social Networks: From the Facebook and Twitter datasets
Citation Graphs: From the Cora, CiteSeer, and PubMed datasets
Traffic Networks: From the METR-LA dataset
For simplicity, we simplified graph data as shown in Figure 7 Following Wang et al. [2024c), we prepared two versions of each graph to accommodate different baselines:
For text-instruction baselines, we restricted inputs no than 30 nodes and 300 edges due context length limitations
For tool-instruction baselines, limited inputs to more than 100 nodes and 1000 edges
31

---

Table 12: The prompt template for constructing the dataset.
Category
Description
Dataset Name
cash_flow_graph.gee
Dataset Type
MultiDirected graph with weights and dates
Dataset Con-
The fund transfer data of a specific group. Directed edge A-B means transferred funds to B. Graph construction:
tent
= nx. MwMMMiiiirrapphh O), G. weight=amount, date=transfer date=transsfe_datee) _atee),
( (sender, receiver,
where "sender" and "receiver" are the transfer participants, "amount" is the money amount, and "transfer_daa is the date. Integer type used for nodes.
Task
Judge the reasonableness of thought and API names based on three dimensions: (1) API Correctness: Whether the method exists networkX, accepts the specified parameters, and matches the dataset type.
(2) Thought and API Effectiveness: How directly and effectively this
step contributes to solving the user question.
(3) Graph Distillation: Whether the current thought and API can reduce
information content narrow search scope.
Output Type
json
Output Rules
(1) Output must be json data containing "apiResult" as shown in the example.
(2) Output can have only this json data with no additional information.
Special Atten- tion
Output "apiResult" should follow:
("api_Correctueet "" "abougttanndpp.Efffeeiieeesss "", "Graph_Distillation" ""}
This approach ensures fair comparison across all methods while allowing us evaluate GraphChain's scalability advantages with full-sized graphs in our main experiments.
G
Complexity Analysis of Structure-aware Test-Time Adaptation
This section analyzes the computational complexity of our Structure-aware Test-Time Adaptation (STTA) mechanism.
G.1
Graph Structural Fingerprinting
For a graph with N nodes and E edges, computing the M smallest singular values of the normalized Laplacian has:
Time complexity: O(E M Ther), where The is the number of iterations in the iterative SVD algorithm
Space complexity: O(N + E+NM)
We employ iterative methods (Lanczos algorithm or power iterations) instead of full SVD to efficiently compute only the needed singular values. Since M < N (typically M = -10 to 50), this computation remains efficient even for large graphs.
G.2 Structure-Condittooee Prompt Generation
The adapter network Ay that maps the structural fingerprint to soft prompts has:
Time complexity: O(M H + H Iap demb)
Space complexity: O(M И + H Lp demb)
32

---

Table 13: Examples from the RL dataset with evaluation scores.
Category
User Question
Thought and API
Input
Please analyze whether there is fund circulation flow the graph. and identify all nodes involved in the circulation flow. Additionally, please calculate the maximum amount funds involved these circulation paths. Begin!
We obtained the minimum fund flow from node to node and its corresponding maximum flow value X. This means that, after considering all possible flow paths, the maximum fund transfer amount the path from node node X.
the maximum
Additionally, we obtained the two sets that constitute the minimum cut, which helps us understand which nodes are involved in this maximum fund transfer process. The step list the names of nodes involved the circulation flow to display directly to the user. API: G. nodes
Output
API Correctness: 0.8, Thought and API Effectiveness: 0.9,
Graph Distillation: 0.0
Input
Please analyze whether there is fund circulation flow in the graph. and identify all nodes involved in circulation flow. Additionally, please calculate the maximum amount of funds involved in these circulation paths. Begin!
To complete this task, we need to proceed step by step. First, we need to determine whether there is fund circulation flow in the graph, which can achieved by calling
<API>nx. find, find_cycce (G) </API> to return a list of cycle edges if a cycle exists. Next, we need to identify all nodes involved in the circulation flow.
<API>nx. simple__cyclee (G) </API> can used to find all simple cycles (i.e. cycles that do not repeat any node) in the graph. Finally, for cach identified circulation path, need to calculate its maximum fund amount, which can done by traversing each edge the cycle and accumulating their weights. API: find_cyccee("
Output
API Correctness: 0.9, Thought and API Effectiveness: 0.95, Graph Distillation: 1.0
Where the hidden dimension, T.p is the prompt length, and demb the embedding dimension. This adapter is extremely lightweight (0.01%-0.1 of LLM parameters).
G.3 Self-Supervised Adaptation
The REINFORCE-basse adaptation using K auxiliary queries with R rollouts per query has:
Time complexity: O(K R- Ñ CLLM + K R- N CKL)
Space complexity: O(K R. N +16
Where N is the average chain length, CLLM the cost of an LLM forward pass, CKL L is the cost of computing KL divergence, and [b]] is the parameter count of the adapter.
G.4 Overall Efficiency
The total computational cost can be summarized as:
Crotal = OEE .IE.M- M T - O(K R R CLIM) + O(T O(T queryy N Nquery CLLM))
(13)
33

---

description
NetworkuD
A-16
segeletnde gerrammuut, datentrnnter.cco frander: "amount"
"wender "vecaver" sender
"ranefer, date" tranher
ope used store nodes when consructing graph.
Social Network
description
Name:Soo Socia- Networkktt kutel
Typesund ineesnndreette graph with weightt
Content The friendship data of social neework, Und rected edge Ar3 means that and fildss The seach consiructio operation
B rectmaphh))
Busts regeooaan usand, inteeeeeeiieeeeooonn.o.. accoo))
here user! "ucer" are users and inn action soore" the acdon score between them. The shing type used store nodes when consts cting graph
Traffic Network
description
Narm: Traffic_ Networkkr
Type Diicccdd graph with weights
Content The transportation cata beoween dites. Directed edge A-1B means that there direct route from city A city
The grach construction operation is
m-mou Grageii
sukpssiy cilp,, werg (esdittnaat
ciy! "sly2"
betwoen soing ope store consorucing graph.
Graph
description
Kamecchation..cm
traaph Graphisd
Type MunCCeeCCeeeedd grauphy
Content The sitaiion data betwoon research papers, Dirccted edge A-1B means that paper cites paper
The consirutioon operation
g mi nuMu
Bact prggpppprrl.peee (apprtt
enere "paper" and pappr2" research papers The dring type used stone nodes ween constructig grapt.
................................
description
Chemical Motecula.te
compound
Bastd enteammmm atoms, swaamennssssteest
utamn" "atend" are atams atringht strength the band between them. The string nodea when constructing the
Figure 7: Detailed Description of the Graph Datasets for the Five Scenarios.
Our approach efficient because: (1) graph fingerprinting is performed only once per graph; (2) adaptation requires few rollouts (typically K R 3); and (3) only the small adapter network needs updating.
34

---

H
Broader Impact
GraphChain's is ability process large-scale graphs efficiently could significantly enhance data analysis capabilities in critical domains such as financial fraud detection, healthcare networks, and social net- work analysis. By enabling more effective reasoning over complex interconnected data, GraphChain could help identify suspicious transaction patterns, improve epidemiological network analysis, and better understand information propagation in social networks. The framework's adaptability across diverse graph structures makes it particularly valuable for interdisciplinary research and applications where domain experts need to analyze graph data without specialized technical knowledge. Moreover, the reduced computational requirements of our approach compared to retraining models for each new graph domain could lead to more environmentally sustainable AI deployments by decreasing the energy consumption associated with large- scale model training. These advancements contribute to more accessible, efficient, and effective graph analytics tools that can address various societal challenges.
35


Reviews:
[{"review_id": "voskYF3zvZ", "reviewer": "Reviewer_kCSq", "summary": "This paper introduces GraphChain, which is a method to automatically call graph based API solutions to serve as the intermediate prompt to assist LLM in graph reasoning tasks. To enable the scalability of method to large scale graph, a progressive graph distillation module is proposed to compress graph to overcome the LLM context limitation issue. Besides, a self-supervised adapter is proposed in the test phase.", "questions": "See above cons. Besides,\n\nIn the introduction parts, the authors mentioned previous LLM methods for graph reasoning are usually suffered from hallucination issue. I am wondering how the proposed method can address/alleviate this issue?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Pros.\n1. The idea to adopt a reinforcement learning module to automatically select graph solution API and use it as LLM chain of thought prompt is interesting. The proposed progressive graph distillation module alleviates the common LLM issue on limited context length.\n\n2. The writing is clear and easy to follow. Motivations of designed modules are well explained.\n\n3. The experimental parts are solid and comprehensive.\n\nCons.\n\n1. How the proposed method compare to previous methods that also use graph API for LLM graph reasoning tasks? I understand the progressive graph distillation can alleviate the LLM context limitation issue. My question is besides this point, how the proposed method is different from existing methods?\n \n2. The selection pool of graph solution API seems important to proposed method. It would be interesting to understand whether some certain APIs are important for a specific task/domain. \n\n3. The computational complexity analysis and time cost for training the RL modules may be interesting to discuss and experiment.", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer kCSq\n\nWe sincerely thank the reviewer for the positive assessment and constructive feedback. We are pleased that the reviewer found our work \"excellent\" in quality and clarity, with \"solid and comprehensive\" experiments. We address each concern below:\n\n## **W1. Comparison with Previous Graph API Methods**\n\nWe appreciate this important question. While previous methods like Graph-ToolFormer and GraphForge pioneered graph API integration, **GraphChain introduces several fundamental innovations beyond progressive distillation**:\n\n**1. Dynamic Multi-Step Tool Chaining vs. Single-Step Invocation**: As illustrated in Figure 1 (middle vs. right), existing methods rely on single-step tool invocations with fixed functionality. In contrast, GraphChain generates dynamic sequences of tools that progressively refine analysis. For instance, in our case study (Appendix B, Figure 6), GraphChain executes 4 interconnected tools to analyze an 11,896-node financial network, while baseline methods would fail due to their single-step limitation.\n\n**2. Reinforcement Learning-based Tool Selection**: Unlike previous methods that use predefined tool selection rules, our RL formulation (Section 4.1) enables adaptive tool sequence generation based on task progress. This is evidenced in Table 2, where GraphChain achieves 84.7% average accuracy compared to GraphForge's 70.2%, representing a 20.7% relative improvement even on small graphs where context limitation is not the primary bottleneck.\n\n**3. Structure-aware Adaptation**: Our STTA mechanism (Section 4.2) dynamically adjusts tool selection strategies based on graph topology using spectral properties, which existing methods lack. Table 3 demonstrates this capability, showing only 3-5% performance drop when transferring across domains with STTA enabled, compared to 8-10% without it.\n\n## **W2. Domain-Specific API Importance Analysis**\n\nThis is an excellent suggestion. We conducted a detailed analysis of API usage patterns across domains, presented in Figure 5. Our findings reveal:\n\n- Traffic Networks heavily utilize Path Planning tools (33.8%)\n- Social Networks prioritize Centrality Measures (28.8%) and Community Detection (20.4%)\n- Citation Graphs show balanced usage with significant Connectivity tools (18.9%)\n\nThis adaptive selection emerges naturally from our reward function without explicit programming, demonstrating the effectiveness of our approach.\n\n## **W3. Computational Complexity and Training Cost**\n\nThank you for this suggestion. We provide a detailed complexity analysis:\n\n**Training Complexity**:\n- **SFT Stage**: $O(N × L × d)$ where $N$ is dataset size (9,986), $L$ is average sequence length (~400 tokens), $d$ is model dimension (4,096)\n- **RL Stage**: $O(K × T × C_{rollout})$ where $K$ is episodes (3,000), $T$ is average steps per episode (~5), $C_{rollout}$ includes LLM forward pass and tool execution\n- **Total training time**: ~18 hours on 2 NVIDIA A800 GPUs (SFT: 6 hours, RL: 12 hours)\n\nIn Appendix G, we also provide detailed complexity analysis of Structure-aware Test-Time Adaptation.\n\n## **Q1. Addressing Hallucination Issues**\n\nThis is a crucial point. GraphChain addresses hallucination through three key mechanisms:\n\n**1. Tool Execution Verification**: Each API call returns concrete, deterministic results stored in memory state $\\mathbf{m}_t$ (Section 3, Equation 1). Unlike text-only methods that may hallucinate graph properties, our tool outputs are grounded in actual graph computations. For example, when asked about shortest paths, the system executes `nx.dijkstra_path()` rather than generating potentially incorrect textual descriptions.\n\n**2. Progressive Distillation with Validation**: Our reward function (Equation 5) includes $\\hat{r}^{\\mathrm{Succ}}_t$ that validates successful tool execution. Failed or nonsensical tool calls receive negative rewards, training the model to avoid hallucinated operations. This creates a feedback loop that reinforces factually correct tool sequences.\n\n**3. Structured Action Space**: By constraining outputs to valid API calls with proper parameters, we eliminate free-form text generation where hallucinations typically occur. The model must select from a finite set of well-defined tools rather than generating arbitrary claims about graph properties.\n\nThese mechanisms collectively ensure that GraphChain's outputs are grounded in verifiable computations rather than potentially hallucinated text.\n\n## **Minor Correction**\n\nThank you for catching the typo in Figure 2. We will correct \"amswer\" to \"answer\" in the camera-ready version.\n\n---\n\nWe hope these clarifications address your concerns and demonstrate the significant contributions of GraphChain beyond existing methods. We greatly appreciate your thorough review and valuable suggestions for improving our work."}, {"review_id": "3tZ8EpIQvE", "reviewer": "Reviewer_DPRo", "summary": "This paper introduces a framework for large-scale graph analysis using LLMs through dynamic tool chaining. The core idea is to decompose complex graph reasoning tasks into sequential tool-based operations. The method includes two main designs: (1) Progressive Graph Distillation, a reinforcement learning mechanism to generate compact, relevant tool sequences; and (2) Structure-aware Test-Time Adaptation (STTA), which conditions tool selection on spectral fingerprints of the graph to enable efficient adaptation across domains. Experiments show performance gains over baselines in accuracy and scalability.", "questions": "1. How stable is the decomposition of graph reasoning into sequential tool calls across different graph types and task complexities? Is there evidence that the sequences are consistent or robust?\n\n2. Can the authors provide more detailed justification or analysis for how the Structure-Conditioned Prompt Generation meaningfully affects the LLM’s reasoning? Have alternative mechanisms been considered?\n\n3. Given the limited size of the expert-annotated RL dataset, how does the agent policy generalize across scenarios? Are there training dynamics, convergence curves, or rollout visualizations to support this?\n\n4. Most results focus on classification tasks. Has GraphChain been tested on other graph reasoning types such as link prediction, subgraph matching, or path-based queries?\n\n5. Why are more recent and larger datasets not included in the evaluation? And why are several recent LLM-based graph reasoning methods not compared?\n\n6. Can the authors more clearly define and categorize the tool library earlier in the paper (e.g., in Preliminaries)? Section 5.6 is informative but arrives late for comprehension.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper proposes a new formulation by combining reinforcement learning and tool-chaining for scalable graph reasoning with LLMs.\n\n2. The design of progressive distillation is conceptually sound, drawing parallels to human exploratory behavior.\n\n3. Experimental results indicate clear improvements over several baselines.\n\n4. The method exhibits promising scalability and transferability across domains, supported by ablations and tool usage analysis.\n\nWeaknesses:\n1. Context exhaustion and reasoning hallucination are not fully resolved. Although GraphChain aims to address these challenges via decomposition, splitting tasks into smaller operations doesn’t necessarily prevent memory overload or hallucination—especially in long reasoning chains. More direct evaluation of these issues would strengthen the claims.\n\n2. The paper lacks justification for how complex graph queries are reliably translated into tool sequences. It’s unclear how stable or generalizable these sequences are, or how sensitive they are to graph variations.\n\n3. Appending spectral graph embeddings to the input is an interesting idea, but it’s unclear if this actually helps the LLM reason better. The mechanism feels ad-hoc, and no ablations or analyses isolate its contribution.\n\n4. Limited details on RL training and policy behavior. The training data is relatively small, and the RL setup—especially reward shaping—is complex. Yet the paper provides little insight into training dynamics, stability, or convergence, making it hard to judge how well the agent learns.\n\n5. Most datasets are small and standard. More realistic and large-scale benchmarks (e.g., from Graph-CoT (https://arxiv.org/abs/2404.07103) or SNAP (https://snap.stanford.edu/data/) ) are missing, and tasks are limited mostly to classification. This restricts the generalizability of results.\n\n6. Only one LLM (Qwen2.5-7B) is evaluated, with no analysis of how model size impacts performance. More recent LLM-based graph reasoning baselines are also missing, which limits the fairness of comparisons.\n\n7. The paper assumes familiarity with the tool library, but doesn’t introduce it clearly upfront. This makes the method harder to understand, especially for readers unfamiliar with specific graph operations.", "was_revised": true, "final_justification": "Thanks to the authors for the very thorough rebuttal and the substantial new experiments. I’m raising my score. \nThe explanations on how GraphChain handles context exhaustion and reasoning hallucination are clearer now, and the extra evidence on tool sequence stability, STTA’s role, and RL training behavior addresses several of my earlier doubts. The added results on more setups also make the evaluation feel more solid. I still think there’s room to broaden dataset diversity and explore more task types, but the rebuttal has convinced me that the method is robust and generalizable to merit further discussion.", "rebuttal": "# Response to Reviewer DPRo\n\nWe sincerely thank the reviewer for the thorough review and constructive feedback. We value your positive assessment of our novel approach, conceptual rigor, and experimental advancements. Below, we address each concern with clarifications and additional evidence.\n\n## W1: Context exhaustion and reasoning hallucination are not fully resolved\n\nWe respectfully clarify that GraphChain fundamentally addresses these issues through our dual-output mechanism (Section 3, Preliminaries). Each tool produces: (1) a concise natural language summary $d$ for the LLM, and (2) an updated memory state $\\mathbf{m}'$ stored externally. This design ensures the LLM never directly processes large graph structures, effectively preventing context exhaustion.\n\nRegarding reasoning hallucination, our approach provides three key safeguards:\n\n1. **Tool Execution Verification**: Each API call returns concrete results stored in memory state $m_t$ (Equation 1), providing factual grounding. Unlike text-only methods that may hallucinate graph properties, our tool outputs are deterministic and verifiable.\n\n2. **Progressive Distillation with Validation**: The reward function (Equation 5) includes $\\hat{r}^{\\mathrm{Succ}}_t$ that validates successful tool execution. Failed or nonsensical tool calls receive negative rewards, training the model to avoid hallucinated operations.\n\n3. **Structured Action Space**: By constraining outputs to valid API calls with proper parameters, we eliminate free-form text generation where hallucinations typically occur.\n\nTo illustrate this, we implement a `GraphForge-MultiTool` baseline, which generates a fixed multi-step tool plan in a single pass and executes it without adaptation. As shown in the table below, this non-adaptive multi-tool approach provides only a marginal benefit over the original `GraphForge` and is substantially outperformed by `GraphChain`'s dynamic chaining.\n\n**Table R1: Comparison of Single-Step, Fixed Multi-Step, and Dynamic Chaining (Average Accuracy %)**\n\n|Method Type|Model|Description|**Average Accuracy**|\n|-|-|-|:-:|\n|Single-Step Tool|`GraphForge`|Original single-tool invocation|70.2|\n|Fixed Multi-Step|`GraphForge-MultiTool`|Generates a fixed chain of tools at once|76.9|\n|**Dynamic Chaining**|`GraphChain` (Ours)|**Adaptive, sequential tool chaining**|**84.7**|\n\n## W2 & Q1: Lack of justification for stable tool sequence generation\n\nOur experiments provide strong evidence for the stability and generalizability of generated tool sequences:\n\n**Domain-Adapted Stability**: Our **Tool Chain Analysis** (Section 5.6, Figure 5) demonstrates that GraphChain learns consistent, domain-specific strategies. For instance, it heavily utilizes \"Path Planning\" tools for Traffic Networks (33.8%), while prioritizing \"Centrality Measures\" (28.8%) for Social Networks. This shows the RL agent converges to stable, contextually appropriate policies rather than random sequences.\n\n**Robustness via Adaptation**: The **Structure-aware Test-Time Adaptation (STTA)** mechanism specifically handles graph variations. Our **Transfer Learning Evaluation** (Section 5.5, Table 3) shows that GraphChain with STTA maintains high accuracy in unseen domains (86.8% on Social Networks), proving its effectiveness in enhancing transfer capabilities.\n\nTo further validate robustness, we evaluated GraphChain with a **reduced toolset** (50% of centrality and clustering tools removed):\n\n**Table R2: Robustness to Tool Library Composition (Average Accuracy %)**\n\n|Model|Financial|Chemical|Social|Citation|Traffic|**Average**|\n|-|:-:|:-:|:-:|:-:|:-:|:-:|\n|`GraphForge` (Baseline)|63.5|70.9|80.4|63.4|73.5|70.2|\n|`GraphChain` (Full Toolset)|**81.5**|**81.1**|**89.6**|**83.6**|**84.1**|**84.7**|\n|`GraphChain` (Reduced Toolset)|77.3|78.4|82.7|80.1|80.6|79.8|\n\nThis degradation highlights our RL agent's adaptability in finding alternative tool paths even with limited resources.\n\n## W3 & Q2: Unclear contribution of spectral graph embeddings\n\nWe provide both empirical and theoretical justification for the STTA mechanism:\n\n**Empirical Evidence**: Our **Ablation Study** (Section 5.3, Figure 3) directly measures STTA's contribution. Moreover, in our transfer learning evaluation (Table 3), removing STTA results in significant accuracy drops.\n\n**Theoretical Justification**: As stated in Section 4.2.1, the smallest singular values of the graph Laplacian capture global, low-frequency structural properties. This provides the LLM policy with a concise \"summary\" of graph topology without processing the entire adjacency matrix—a principled approach to inject structural awareness.\n\nTo further validate this mechanism, we tested an alternative approach using textual structure descriptions:\n\n**Table R3: Comparison of Structure Injection Methods (Average Accuracy %)**\n\n|Model|Social Network|Citation Graph|Traffic Network|\n|-|:-:|:-:|:-:|\n|GraphChain (w/o STTA)|82.4|75.2|77.8|\n|GraphChain (Text-based structure)|84.0|76.4|79.2|\n|GraphChain (w/ STTA)|**89.6**|**83.6**|**84.1**|\n\nThe results show that spectral fingerprints are more effective than text-based structural descriptions.\n\n## W4 & Q3: Limited details on RL training and policy behavior\n\nOur RL approach generalizes well because: (1) extensive SFT pre-training (~10k examples) provides a strong starting policy, and (2) the distillation-based reward provides dense, structured signals.\n\n**Table R4: RL Training Dynamics (Average Reward Components)**\n\n| Episode | 250 | 500 | 750 | 1000 | 1250 | 1500 | 1750 | 2000 | 2250 | 2500 |\n|:-|:-|:-|:-|:-|:-|:-|:-|:-|:-|:-|\n| Reward (Success) | 1.61 | 2.34 | 2.58 | 2.75 | 2.72 | 2.89 | 3.03 | 2.88 | 2.90 | 2.98 |\n| Reward (ΔGDL) | -0.06 | 0.34 | 0.92 | 1.56 | 1.70 | 1.81 | 1.78 | 1.94 | 1.94 | 1.93 |\n| Reward (ΔRel) | -0.62 | 0.13 | 0.72 | 1.30 | 1.83 | 1.90 | 2.01 | 1.98 | 2.04 | 2.17 |\n| Average Reward | 0.38 | 1.18 | 1.97 | 2.78 | 3.02 | 3.20 | 3.25 | 3.35 | 3.37 | 3.41 |\n\nOur model exhibits smooth reward curves. The results reveal that the agent first learns to invoke tools successfully and only then discovers how to compress information via graph distillation. This progression of learning behaviors corroborates the effectiveness of our carefully designed reward function.\n\n## W5 & Q4: Limited dataset variety and missing recent benchmarks\n\nWe thank the reviewer for pushing for evaluation on larger and more diverse benchmarks.\n\n* **On Graph Scale**: We respectfully disagree that our datasets are uniformly small. The **Elliptic dataset contains over 200,000 nodes** (**Table 1**), making it a large-scale, real-world benchmark. Our **Scalability Analysis (Section 5.4, Figure 4)** explicitly evaluates on graphs of this size, demonstrating that `GraphChain`'s performance remains robust while baselines falter. Additionally, our social network datasets (Twitter and Facebook) are from SNAP.\n\n* **On Graph-COT**: We appreciate the suggestion but note that Graph-COT targets knowledge graph reasoning for graph-RAG scenarios, which differs from our focus on graph analysis tasks. \n\n* **On Task Diversity**: To demonstrate broader applicability, we conducted additional experiments on the **link prediction** task:\n\n**Table R5: Link Prediction Performance (AUC)**\n\n| Model | Cora | CiteSeer |\n|:-|:-:|:-:|\n| GPT-4o (CoT) | 72.4 | 69.4 |\n| GraphForge | 79.6 | 75.9 |\n| **GraphChain (Ours)** | **85.8** | **81.6** |\n\nThese results show that `GraphChain`'s structured reasoning process is effective for canonical graph tasks beyond classification.\n\n## W6 & Q5. Only one LLM evaluated and missing recent baselines\n\nTo address this concern, we evaluated GraphChain with different base models:\n\n**Table R6: Performance with Different Base LLMs (Average Accuracy %)**\n\n| Base Model | Financial | Chemical | Social | Citation | Traffic | Average |\n|-|:-:|:-:|:-:|:-:|:-:|:-:|\n| Qwen2.5-7B | 70.5 | 81.1 | 90.4 | 79.0 | 82.0 | 80.6 |\n| Llama3.1-8B | 69.3 | 81.7 | 93.7 | 82.5 | 81.7 | 81.8 |\n| GLM4-9B | 70.2 | 78.9 | 93.8 | 79.7 | 79.9 | 80.5 |\n\nThe consistent superior results across different base models demonstrate the robustness and general applicability of our approach.\n\nWe also conducted supplementary experiments using Qwen2.5 models of varying sizes (3B, 7B, and 14B).\n\n**Table R7: Comparison of Base Models with Different Sizes (Average Accuracy %)**\n\n| Model | Financial Network | Chemical Molecule | Social Network | Citation Graph | Traffic Network |\n|-|-|-|-|-|-|\n| Qwen2.5-3B  | 63.1% | 56.9% | 70.2% | 74.4% | 73.4% |\n| Qwen2.5-7B  | 81.5% | 81.1% | 89.6% | 83.6% | 84.1% |\n| Qwen2.5-14B | 85.7% | 85.4% | 92.2% | 83.2% | 89.7% |\n\nThe results show that `GraphChain`'s performance improves with larger model sizes. Notably, even the smaller 3B model still maintain reasonable performance under our framework.\n\nWe also compared against the most recent baselines:\n\n**Table R8: Comparison with Recent Methods (Average Accuracy %)**\n|Method|Financial|Chemical|Social|Citation|Traffic|\n|-|:-:|:-:|:-:|:-:|:-:|\n|**Text-Instruction Methods**|||||\n| Claude-4-Sonnet | 58.2 | 62.9 | 61.7 | 77.5 | 32.8 |\n| GPT-4.1 | 52.2 | 63.4 | 67.4 | 70.0 | 55.5 |\n| Gemini-2.5-Flash | 25.1 | 67.3 | 28.1 | 24.1 | 24.9 |\n| **Tool-Instruction Methods** |||||\n| ToolGen (ICLR'25) | 75.8 | 57.9 | 79.4 | 61.2 | 62.7 |\n| PIE (Arxiv'25) | 68.6 | 74.9 | 71.1 | 59.7 | 62.4 |\n| GraphChain | **81.5** | **81.1** | **89.6** | **83.6** | **84.1** |\n\n## W7 & Q6. Tool library not clearly introduced upfront\n\nThis is an excellent suggestion for improving the paper's clarity. In the revised version, we will move the high-level overview of the tool library categories into the **Preliminaries (Section 3)**. This will greatly improving readability.\n\nWe sincerely thank the reviewer for their valuable feedback, which has helped us strengthen our paper. We believe our responses address all concerns and demonstrate GraphChain's robustness, scalability, and superiority over existing methods."}, {"review_id": "WjXQ7X0274", "reviewer": "Reviewer_pP65", "summary": "This paper introduces a framework called GraphChain to enhance the capabilities of Large Language Models (LLMs) in processing large-scale graph data. In this paper, the authors propose two key approaches to allow for a more detailed and adaptive exploration of graph structures: Progressive Graph Distillation and Structure-aware Test-Time Adaptation. The framework significantly outperforms existing methods, achieving an average improvement of 20.7% in average. GraphChain demonstrates strong transfer learning capabilities, adapting effectively to new graph domains without domain-specific retraining. Overall, GraphChain provides a scalable and adaptive solution for LLM-driven graph analysis, addressing the challenges of context exhaustion and reasoning hallucination that are prevalent in existing graph processing approaches.", "questions": "1. How are the tools be selected? Are models robust to the tool selections?\n2. What would be the performances for text-instruction methods if they are allowed to use these tools?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n* The paper presents a well-structured approach to address the limitations of LLMs in graph analysis through the introduction of GraphChain. The use of Progressive Graph Distillation and Structure-aware Test-Time Adaptation is well-justified and supported by theoretical underpinnings.\n* Extensive experiments demonstrate the effectiveness of GraphChain, showing significant improvements over existing methods. The results are statistically significant, with a clear presentation of performance metrics across various datasets.\n\nWeakness:\n* There is a pre-defined set of tools needed, it is unclear how are these tools defined and selected. Will the models be robust to different selections/selections of tools?\n* Compared with previous tool approach, the major improvements come from multiple tool used. If the baselines such as graphsurge are using multiple tools in the reasoning steps, the improvements might be less.\n* The baselines seem to be outdated.", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer pP65\n\nWe sincerely thank the reviewer for their valuable time and insightful feedback. We are encouraged that the reviewer found our approach well-structured, our innovations well-justified, and our experiments extensive and significant. We appreciate the opportunity to address the weaknesses and questions raised.\n\n\n\n## W1 & Q1. Tool Definition and Selection Robustness\n\nWe thank the reviewer for highlighting this important aspect. The tool selection process was indeed systematic and principled.\n\n**Tool Selection Process:** As detailed in **Appendix E (Table 6)**, we carefully curated 45 functions from the NetworkX library through a comprehensive review of graph analysis tasks. Our selection ensures coverage across eight fundamental analytical dimensions: Basic Graph Properties, Centrality Metrics, Connectivity and Components, Shortest Paths, Clustering and Communities, Flow Algorithms, Cycle Detection, and Topological Sorting. This systematic approach ensures our toolset is both representative and grounded in established graph analysis practices.\n\n**Robustness to Tool Selection:** Our framework is designed to be inherently robust to variations in the tool library. The core of GraphChain employs a reinforcement learning policy that learns to select optimal tool sequences from the available action space, rather than being hard-coded to specific tools.\n\nTo empirically validate this robustness, we conducted an additional experiment with a **reduced toolset** (removing 50% of tools from Centrality and Community Detection categories):\n\n**Table R1: Robustness to Tool Library Composition (Average Accuracy %)**\n\n| Model | Financial | Chemical | Social | Citation | Traffic | **Average** |\n|-------|:---------:|:--------:|:------:|:--------:|:-------:|:-----------:|\n| GraphForge (Baseline) | 63.5±3.5 | 70.9±5.4 | 80.4±4.2 | 63.4±4.4 | 73.5±3.1 | 70.2±3.8 |\n| GraphChain (Full Toolset) | **81.5±2.2** | **81.1±0.7** | **89.6±2.0** | **83.6±2.6** | **84.1±0.3** | **84.7±1.8** |\n| GraphChain (Reduced Toolset) | 77.3±2.8 | 78.4±1.8 | 82.7±3.1 | 80.1±3.2 | 80.6±0.9 | 79.8±2.4 |\n\nThe results demonstrate that GraphChain maintains strong performance even with a reduced toolset, showcasing the adaptability of our RL agent in finding alternative tool sequences to solve tasks.\n\n\n## W2. Multi-Tool Usage Comparison\n\nWe appreciate this astute observation about the source of improvements. Indeed, the key innovation of GraphChain is not merely using multiple tools, but **how** it intelligently and adaptively chains them.\n\n**Key Distinction:** As described in Section 3 (Problem Formulation), GraphChain formulates tool selection as a Markov Decision Process, enabling dynamic, sequential reasoning where outputs from one tool guide subsequent selections. This fundamentally differs from existing approaches like GraphForge, which are architected for single-step tool invocation without stateful adaptation.\n\nTo address the reviewer's concern, we implemented a **GraphForge-MultiTool** baseline that generates fixed multi-step plans without adaptive refinement:\n\n**Table R2: Comparison of Tool Usage Strategies (Average Accuracy %)**\n\n| Method Type | Model | Description | **Average Accuracy** |\n|-------------|-------|-------------|:--------------------:|\n| Single-Step | GraphForge | Original single-tool invocation | 70.2±3.8 |\n| Fixed Multi-Step | GraphForge-MultiTool | Fixed chain of tools | 73.4±4.1 |\n| **Dynamic Chaining** | **GraphChain** | **Adaptive sequential chaining** | **84.7±1.8** |\n\nThis experiment confirms that GraphChain's significant performance gain stems from its sophisticated Progressive Graph Distillation mechanism (Section 4.1) and adaptive tool selection, not merely from using multiple tools.\n\n\n\n## W3. Baseline Selection\n\nWe respectfully do not entirely agree with your perspective and believe our baseline is robust. As detailed in **Appendix D (Table 4)**, our evaluation includes the models across both paradigms:\n\n**Text-Instruction Methods:**\n- **General-Purpose LLMs:** GPT-4o (200B params), Claude-3 series (Opus, Sonnet, Haiku)\n- **Specialized Graph Methods:** NLGraph (NeurIPS 2023), GraphWiz (KDD 2024)\n\n**Tool-Instruction Methods:**\n- **GraphForge** (KDD 2025): The lasted and powerful tool-based graph reasoning method\n- **Graph-ToolFormer** (2023): Seminal work in tool-augmented graph reasoning\n\nTo further validate our approach against the absolute latest models, we conducted additional experiments:\n\n**Table R3: Extended Comparison with Latest Models (Average Accuracy %)**\n\n| Model | Type | Financial | Chemical | Social | Citation | Traffic | Average |\n|-------|------|:---------:|:--------:|:------:|:--------:|:-------:|:-------:|\n| **Additional General-Purpose LLMs** |\n| Claude-3.5-Haiku | Text | 26.6 | 51.8 | 28.5 | 31.6 | 29.3 | 33.6 |\n| Claude-4-Sonnet | Text | 58.2 | 62.9 | 61.7 | 77.5 | 32.8 | 58.6 |\n| Claude-4-Opus | Text | 61.5 | 67.8 | 66.5 | 75.1 | 43.6 | 62.9 |\n| GPT-4.1 | Text | 52.2 | 63.4 | 67.4 | 70.0 | 55.5 | 61.7 |\n| Gemini-2.0-Flash | Text | 25.1 | 67.3 | 28.1 | 24.1 | 24.9 | 33.9 |\n| **Latest Tool-Based Methods** |\n| ToolGen (ICLR 2025) | Tool | 75.8 | 57.9 | 79.4 | 61.2 | 62.7 | 67.4 |\n| PIE (arXiv 2025) | Code-Gen | 68.6 | 74.9 | 71.1 | 59.7 | 62.4 | 67.3 |\n| **GraphChain (Ours)** | **Tool** | **81.5** | **81.1** | **89.6** | **83.6** | **84.1** | **84.7** |\n\nOur evaluation includes:\n1. **The newest Claude-4 series** (Sonnet and Opus), representing Anthropic's latest advances\n2. **GPT-4.1**, the most recent OpenAI model\n3. **Gemini-2.0-Flash**, Google's efficient model\n4. **ToolGen** (ICLR 2025), a cutting-edge general tool-use framework\n5. **PIE** (2025), a recent code-generation approach for graph reasoning\n\nGraphChain consistently outperforms all these latest approaches by significant margins (17.3% over the best baseline ToolGen, 21.8% over PIE). This comprehensive comparison confirms that our method represents a genuine advance over the current state-of-the-art, not merely an improvement over outdated baselines.\n\n\n## Q2. Performance of text-instruction methods with tools?\n\nWe sincerely thank the reviewer for raising this important question regarding the performance of text-instruction methods when integrated with the GraphChain toolset. To address this, we conducted supplementary experiments using two representative text-instruction methods: **GPT-4o** and **Claude-3-Opus**. The results are presented below:\n| Model                  | Financial Network | Chemical Molecule | Social Network | Citation Graph | Traffic Network |\n|------------------------|-------------------|-------------------|----------------|----------------|-----------------|\n| Claude-3-Opus          | 23.6%             | 42.4%             | 51.9%          | 36.7%          | 43.4%           |\n| GPT-4o                 | 57.5%             | 62.7%             | 65.2%          | 71.5%          | 43.4%           |\n| Claude-3-Opus (w/ Tools) | 30.4%           | 50.3%             | 64.9%          | 53.8%          | 63.1%           |\n| GPT-4o (w/ Tools)      | 71.5%             | 67.6%             | 74.4%          | 77.4%          | 55.9%           |\n| **GraphChain (Ours)** | **81.5%** | **81.1%** | **89.6%** | **83.6%** | **84.1%** |\n\nThe integration of the GraphChain toolset significantly improves the performance of text-instruction methods, demonstrating that tool invocation enhances their graph reasoning capabilities. However, GraphChain consistently outperforms both tool-augmented text-instruction methods across all datasets. This superiority stems from GraphChain's ability to optimize tool sequences through reinforcement learning and its structure-aware test-time adaptation (STTA) mechanism, which enables more efficient tool selection and combination.\n\nWe hope these clarifications address the reviewer's concerns and demonstrate the robustness and significance of our contributions. We would be happy to provide any additional information needed."}, {"review_id": "C5SNfmKYOP", "reviewer": "Reviewer_9MGr", "summary": "The paper introduces a framework named GraphChain to tackle the challenges large language models (LLMs) face in large-scale graph analysis, such as context exhaustion and reasoning hallucination. Concretely, it proposes a dynamic tool-chaining mechanism that mimics human exploratory reasoning. It leverages two core innovations: Progressive Graph Distillation for generating concise and relevant tool sequences, and Structure-aware Test-Time Adaptation for adapting to diverse graph topologies. The experimental results reveal that GraphChain significantly outperform baselines.\n\nFrom my perspective, The paper designs a three-stage graph understanding framework that transforms the usual \"subgraph sampling + direct LLM inference\" paradigm into \"subgraph sampling → Refining → LLM inference.\"", "questions": "1. Does the author leverage feature information during the training and evaluation process? If GraphChain primarily focuses on graph computational problems, it is recommended that the authors make this explicit in the paper to clarify the intended scope and highlight the method's strengths.", "limitations": "Yes, but the paper needs to further clarify its ability to process and utilize feature information.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Pros**\n1. **Progressive Refinement:** By supervising the refine step with PPO, the framework learns to select and chain graph-processing tools that maximize task relevance while minimizing unnecessary information.\n2. **Scalability to Large Graphs:** This pipeline enables LLMs to handle large-scale graphs with both structural and feature information, overcoming context-window limits.\n\n**Cons**\n\n1. **Manual Tool Library:** All subgraph-sampling and processing tools are hand-crafted; an end-to-end mechanism for automated subgraph selection would increase flexibility.\n2. **Structure-Only Evaluation:** Although the method formally incorporates node features and evaluates on multiple domains, all experiments and case studies focus on pure topological reasoning tasks, leaving its effectiveness on feature-rich and true cross-domain graph problems unverified.", "was_revised": true, "final_justification": "I have no further questions. My concerns have been addressed.", "rebuttal": "# Response to Reviewer 9MGr\n\nWe sincerely thank the reviewer for their thorough evaluation and constructive feedback. We are pleased that the reviewer recognizes our contributions in progressive refinement, scalability, and the significance of our approach. We address each concern below.\n\n## W1: Manual Tool Library\n\nWe appreciate the reviewer's suggestion about end-to-end automated subgraph selection. We would like to clarify that while our current implementation uses a curated set of 45 NetworkX functions (detailed in Appendix E, Table 6), this design choice was deliberate for several reasons:\n\n1. **Interpretability and Reliability**: The manual curation ensures that each tool in our library is well-tested, interpretable, and provides reliable outputs - crucial for practical deployment in domains like financial fraud detection and healthcare networks (as mentioned in our Broader Impact section, Appendix H).\n\n2. **Extensibility**: Our framework is designed to be extensible. As stated in Appendix E: \"Future work may integrate domain-specific or higher-order analytics, but this toolset is representative and sufficient for general-purpose graph analysis.\"\n\n3. **Learning Focus**: Our key innovation lies in learning optimal tool sequences through reinforcement learning, not in discovering new graph operations. The Progressive Graph Distillation mechanism (Section 4.1) learns to chain these tools effectively, which is orthogonal to the tool discovery problem.\n\nWe agree that automated tool discovery is an interesting future direction and will emphasize this more clearly in our revised limitations section.\n\n\n## W2: Structure-Only Evaluation\n\nWe appreciate the reviewer's observation and acknowledge that our evaluation primarily focuses on topological reasoning tasks. We believe this emphasis is both deliberate and justified:\n\n1. **Fundamental Challenge for LLMs**: The core difficulty for LLMs in graph analysis lies in understanding topological structures rather than processing features. LLMs are inherently designed for sequential processing, making non-Euclidean graph structures particularly challenging. In contrast, node features can be readily converted to text and processed naturally by LLMs. This is why we prioritize evaluating topological understanding - it represents the more fundamental challenge in LLM-based graph analysis.\n\n2. **Feature Integration in Our Framework**: While our evaluation emphasizes topology, our method fully supports feature-rich graphs. As shown in our formulation (Section 4.1.1, Equation 3), the Graph Description Length (GDL) explicitly includes a feature term $\\alpha_f n'_t d_f$ that quantifies feature information volume. When our Progressive Graph Distillation mechanism reduces the target region to fit within the context window, we input the complete graph description including all node and edge features to the LLM for reasoning. This is evident in our case study (Appendix B, Figure 6), where the final distilled state includes feature information for LLM processing.\n\n3. **Domain Diversity**: Our evaluation spans five diverse domains (Table 1): Financial Networks (165 features), Chemical Molecules (11 features), Social Networks, Citation Graphs (up to 3,703 features), and Traffic Networks. Each domain presents unique structural characteristics and feature types, demonstrating our method's cross-domain effectiveness.\n\nWe maintain that for graph analysis scenarios, especially with LLMs, topological reasoning represents the more challenging and thus more informative evaluation criterion. However, we acknowledge that demonstrating feature utilization more explicitly would strengthen our paper and will include such examples in our revision.\n\n\n\n## Q1: Feature Information Utilization\n\nYes, we leverage feature information throughout our training and evaluation process:\n\n1. **Architectural Support**: Our Progressive Graph Distillation mechanism, as formulated in Section 4.1.1, explicitly incorporates feature data. The Graph Description Length (GDL) metric in Equation 3 includes a specific term, $\\alpha_f n'_t d_f$, to quantify the information volume of node features, directly influencing the RL agent's reward and policy.\n\n2. **Practical Implementation**: During the distillation process, once the subgraph is reduced to fit the LLM's context window, we provide the complete graph representation including all node and edge features. This ensures that the final reasoning step has access to all relevant feature information.\n\n3. **Evaluation Datasets**: As shown in Table 1, our evaluation includes feature-rich graphs: Citation graphs with up to 3,703 features per node, Financial Networks with 165 transaction features, and Chemical Molecules with 11 atomic properties.\n\n4. **Scope Clarification**: We agree that explicitly stating our focus on graph computational problems would improve clarity. While our framework fully supports feature-rich graphs, our evaluation emphasizes topological reasoning as it represents the fundamental challenge for LLMs in graph analysis. We will make this scope more explicit in our revised manuscript to better highlight our method's strengths and intended applications.\n\n## Commitment to Revisions\n\nBased on your valuable feedback, we commit to:\n\n1. **Clarifying Feature Utilization**: We will add explicit examples in the main paper showing how GraphChain processes and utilizes node/edge features during the distillation and reasoning process.\n\n2. **Scope Statement**: We will include a clear statement about our primary focus on graph computational problems while emphasizing our framework's capability to handle feature-rich scenarios.\n\n3. **Future Directions**: We will expand our limitations section to discuss automated tool discovery as a promising future direction.\n\nWe believe these clarifications will strengthen our paper while maintaining its core contributions. Thank you again for your insightful review."}]

Author rebuttal:

Meta-review: (a) Scientific claims and findings
The paper proposes GraphChain, a framework that leverages LLM tool chaining to enable large-scale graph analysis tasks that exceed the context length or reasoning ability of LLMs.
Key claims:
- LLMs alone struggle with large-scale graph analysis due to memory and reasoning limits.
- GraphChain decomposes analysis into modular tool calls (e.g., traversal, subgraph querying, aggregation), chaining them to solve larger problems.
- Introduces a controller mechanism to orchestrate tool usage, ensuring correctness and scalability.
- Empirical results across tasks like graph traversal, centrality computation, community detection, and influence maximization show GraphChain outperforms naive prompting and direct LLM baselines.
(b) Strengths
- Novel problem formulation: Tackles the important challenge of scaling LLMs for graph analysis.
- Clear framework: Tool chaining approach is modular and generalizable.
- Strong empirical results: Outperforms LLM baselines across multiple graph tasks.
- Clarity: Well-written and easy to follow.
- Impact potential: Opens new research directions at the intersection of symbolic methods and LLM reasoning.

(c) Weaknesses 

- Incremental novelty: Tool chaining is a known idea; contribution lies in applying it to graph analysis.
- Evaluation scope: Lacks experiments on truly large graphs (industrial scale).
- Limited theoretical justification: Focused on framework design and experiments, not formal guarantees.

(d) Key reasons for decision (accept/reject)
- Tackles an important and underexplored problem (LLMs for graph analysis).
- Provides a clear, modular, and general framework (GraphChain).
- Strong empirical results across diverse graph tasks.
- High clarity and potential for impact.

(e) Discussion & rebuttal period

Reviewer points raised:
-Novelty concerns: Is GraphChain just applying tool chaining to graphs?
            - Author rebuttal: Argued that integrating tool orchestration into graph analysis is non-trivial; provided detailed explanation of controller design.
            - Effect: Somewhat alleviated novelty concerns.

- Scalability: Can GraphChain handle very large graphs?
              -Author rebuttal: Added clarifications and experiments on larger synthetic graphs.
              -Effect: Improved perception but reviewers still noted scope limitation.
-Theoretical grounding: Why no guarantees on correctness or complexity?
               -Author rebuttal: Emphasized focus on practical framework, not formal theory.
               - Effect: Reviewers accepted but kept in mind as limitation.

Outcome: Rebuttal was positively received, clarifying design choices and scalability.
Decision: Accept (poster)