AgentGL: Towards Agentic Graph Learning with LLMs via Reinforcement Learning

1. Problem Statement

The paper addresses a critical gap in current Large Language Model (LLM) applications: while Agentic frameworks (using iterative retrieval and tool use) have improved LLM performance on unstructured text, they fail to leverage the topological dependencies inherent in real-world data.

• Context: Many domains (citation networks, social platforms, e-commerce) are represented as Text-Attributed Graphs (TAGs), where meaning arises from the interplay between node text and graph structure.
• Limitations of Existing Methods:
  • Traditional GNNs: Model structure well but struggle with rich textual semantics.
  • GraphLLMs: Integrate LLMs with graphs but rely on static context extracted once at inference, preventing adaptive exploration.
  • GraphRAG: Reconstructs knowledge graphs from text, often losing native topological correlations and being costly to build.
• Core Challenge: How to enable an LLM agent to autonomously navigate a graph, accumulate structural evidence, and iteratively refine its search trajectory without ground-truth search trajectories (long-horizon policy optimization).

2. Methodology: AgentGL Framework

The authors propose AgentGL, the first Reinforcement Learning (RL)-driven framework for Agentic Graph Learning (AGL). It reframes graph learning as an interleaved process of topology-aware navigation and LLM-based reasoning.

A. Graph-Native Search Tools (GNS)

The agent is equipped with a suite of tools to explore the graph at different scales:

1. $\tau_{1HOP}$ & $\tau_{2HOP}$ (Neighborhood Search): Retrieves local neighbors (1-hop and 2-hop), balancing common neighbors and exclusive ones to capture local structural dependencies.
2. $\tau_{SS}$ (Structure Salience Search): Uses precomputed PageRank (PPR) scores to retrieve globally salient nodes, acting as a structural prior for macro-level reasoning.
3. $\tau_{DENSE}$ (Graph Dense Search): Retrieves nodes based on semantic similarity (embedding cosine similarity), bridging disconnected nodes via latent semantic correlations.

B. Two-Stage RL Training Strategy

To balance accuracy and efficiency, AgentGL employs a two-stage training process optimized via Graph-Conditioned Curriculum Learning (GCCL):

Stage 1: Graph-Native Policy Bootstrapping (GNSPB)

• Goal: Teach the agent to effectively use all available tools.
• Mechanism: Uses a composite reward function:
  • $r_{ACC}$: Task accuracy (node classification/link prediction).
  • $r_{FMT}$: Enforces strict adherence to a machine-parsable "think-act-observe" format.
  • $r_{COV}$: Coverage Reward encourages the agent to try all distinct tool types early in training to prevent "mode collapse" (relying on a single tool).
• Algorithms: Optimized using GRPO (Group Relative Policy Optimization) or REINFORCE++.

Stage 2: Mitigating Search Overuse (MSO)

• Goal: Optimize efficiency by reducing redundant searches while maintaining accuracy ("Think more, Search less").
• Mechanism: Introduces Search-Constrained Thinking:
  • Retrospective Termination Trigger (RTT): After each tool call, the model is forced to explicitly evaluate if the current evidence is sufficient before searching again.
  • Cognitive Density Regularization (CDR): Penalizes sparse reasoning; forces the model to generate dense reasoning blocks analyzing evidence before making further search decisions.
  • Reward Transition: The coverage reward ($r_{COV}$) is removed, and a depth reward ($r_{depth}$) is added to incentivize deep reasoning over redundant retrieval.

C. Graph-Conditioned Curriculum Learning (GCCL)

Instead of random sampling, training difficulty is dynamically adjusted based on graph properties:

• Node Classification: Difficulty is scored using a combination of local homophily (Wilson Lower Bound) and node degree. Easy samples are high-degree, homophilous hubs; hard samples are low-degree, heterophilous outliers.
• Link Prediction: Difficulty is scored based on the consistency between semantic similarity and the existence of a link. Easy samples are high-similarity positive pairs or low-similarity negative pairs; hard samples are ambiguous cases.

3. Key Contributions

1. New Paradigm (AGL): Defines Agentic Graph Learning as a unified framework combining graph structure, text semantics, and agentic decision-making.
2. AgentGL Framework: The first RL-driven system for AGL that synergizes structural perception, strategic reasoning, and policy learning without step-wise supervision.
3. Innovative Mechanisms:
   • Graph-Native Tools: A multi-scale exploration toolkit (Local/Global, Structure/Semantics).
   • Search-Constrained Thinking: A novel mechanism to balance exploration and exploitation, preventing search overuse.
   • GCCL: A curriculum strategy that uses intrinsic graph properties to stabilize long-horizon RL training.

4. Experimental Results

The authors evaluated AgentGL on 7 Text-Attributed Graph (TAG) datasets (Citation, Amazon, Social) across Node Classification (NC) and Link Prediction (LP) tasks, using Qwen2.5-3B/7B backbones.

• Performance Gains:
  • Node Classification: Absolute improvement of up to 17.5% over strong baselines (GraphLLMs, GraphRAG, GNNs).
  • Link Prediction: Absolute improvement of up to 28.4%.
  • Zero-Shot Transfer: AgentGL demonstrated superior robustness in zero-shot settings (e.g., +24.4% on NC, +22.4% on LP), outperforming static context methods which struggle with distribution shifts.
• Efficiency: The two-stage training reduced tool calls by approximately 17.5% while improving accuracy, proving that "less search" (when guided by deep reasoning) yields better results.
• Ablation Studies: Confirmed that both training stages (Bootstrapping and Overuse Mitigation) are essential; removing either leads to performance drops or inefficient search behaviors. The GCCL component was shown to stabilize training and accelerate convergence.

5. Significance

• Beyond Static Context: AgentGL demonstrates that dynamic, topology-aware reasoning is superior to static context injection (GraphRAG/GraphLLM) for complex graph tasks.
• Autonomous Graph Navigation: It proves that LLMs can learn to navigate complex relational environments autonomously, making decisions on where to look and when to stop, rather than just processing pre-extracted text.
• Scalability: The framework scales effectively with model size (3B to 7B), with larger models showing better generalization of tool-use policies.
• Future Direction: This work opens a new frontier for applying agentic AI to structured data, suggesting that future graph learning systems should prioritize adaptive exploration over static representation learning.

In conclusion, AgentGL successfully bridges the gap between LLM reasoning capabilities and the structural complexity of real-world graphs, offering a robust, efficient, and high-performing solution for graph reasoning tasks.