AgentGL: Towards Agentic Graph Learning with LLMs via Reinforcement Learning
| Authors | Yuanfu Sun et al. |
| Year | 2026 |
| HF Upvotes | 8 |
| arXiv | 2604.05846 |
| Download | |
| HF Page | View on Hugging Face |
Abstract
Large Language Models (LLMs) increasingly rely on agentic capabilities-iterative retrieval, tool use, and decision-making-to overcome the limits of static, parametric knowledge. Yet existing agentic frameworks treat external information as unstructured text and fail to leverage the topological dependencies inherent in real-world data. To bridge this gap, we introduce Agentic Graph Learning (AGL), a paradigm that reframes graph learning as an interleaved process of topology-aware navigation and LLM-based inference. Specifically, we propose AgentGL, the first reinforcement learning (RL)-driven framework for AGL. AgentGL equips an LLM agent with graph-native tools for multi-scale exploration, regulates tool usage via search-constrained thinking to balance accuracy and efficiency, and employs a graph-conditioned curriculum RL strategy to stabilize long-horizon policy learning without step-wise supervision. Across diverse Text-Attributed Graph (TAG) benchmarks and multiple LLM backbones, AgentGL substantially outperforms strong GraphLLMs and GraphRAG baselines, achieving absolute improvements of up to 17.5% in node classification and 28.4% in link prediction. These results demonstrate that AGL is a promising frontier for enabling LLMs to autonomously navigate and reason over complex relational environments. The code is publicly available at https://github.com/sunyuanfu/AgentGL.
Engineering Breakdown
Plain English
AgentGL introduces a new framework that combines Large Language Models with graph-structured data through reinforcement learning, enabling LLM agents to navigate and reason over topological relationships in real-world data rather than treating all information as unstructured text. The key innovation is equipping LLM agents with graph-native tools for multi-scale exploration while using search-constrained thinking to balance accuracy and computational efficiency. Prior agentic frameworks failed to leverage the inherent structure and dependencies in graph-based data, limiting their ability to reason over interconnected information. AgentGL demonstrates how reinforcement learning can train agents to make better navigation decisions on graphs, effectively treating graph learning as an interleaved process of topology-aware exploration and LLM-based inference.
Core Technical Contribution
The paper's core contribution is formalizing Agentic Graph Learning (AGL) as a distinct paradigm that bridges the gap between traditional graph neural networks and modern LLM agents. Rather than using pre-trained graph representations or treating graphs as text descriptions, AgentGL develops a reinforcement learning framework where an LLM agent learns to navigate graph structures dynamically, making decisions about which nodes to explore and what information to retrieve based on the task. The framework introduces search-constrained thinking, a mechanism that regulates tool usage to prevent unbounded exploration while maintaining reasoning quality. This is fundamentally novel because it enables LLMs to achieve task-specific, topology-aware reasoning without requiring retraining of the language model itself—only the agent's navigation policy is learned through RL.
How It Works
AgentGL operates as follows: given a graph and a query task, the LLM agent begins with access to a set of graph-native tools (e.g., neighbor exploration, attribute retrieval, shortest-path finding) rather than raw graph data. The agent uses these tools to iteratively navigate the graph, building a context window of relevant nodes and relationships. At each step, the RL component computes a value function over possible actions (which node to visit next, which tool to use) based on the current task and exploration history. The search-constrained thinking module enforces a budget on tool calls and exploration depth, preventing exponential blowup in reasoning steps while maintaining task performance. The agent's policy is trained using policy gradient methods (likely PPO or similar) with rewards derived from downstream task performance (e.g., node classification accuracy, link prediction F1 scores). The inference pipeline integrates LLM reasoning with RL-selected navigation actions, allowing the agent to adaptively explore different graph neighborhoods based on the specific task structure.
Production Impact
For production systems, AgentGL enables LLM-powered graph reasoning without maintaining separate vector embeddings or pre-computed graph representations, which reduces storage overhead and enables real-time graph updates without retraining. Teams building recommendation systems, knowledge graph QA, fraud detection, or social network analysis could integrate this to allow LLMs to explore relationships directly rather than flattening graphs into text prompts. The search-constrained thinking mechanism directly addresses a critical production pain point: LLM token budgets are finite, so uncontrolled agent exploration quickly becomes prohibitively expensive. However, adoption requires: (1) RL fine-tuning infrastructure for each new domain, which demands task-specific reward signals and careful hyperparameter tuning; (2) graph storage systems that support efficient neighbor/attribute lookups at inference time (millisecond-scale latency); and (3) validation that the learned navigation policy generalizes to out-of-distribution graphs. The compute cost during training could be substantial since RL requires many rollouts, but inference-time cost scales with the learned policy's efficiency, potentially lower than greedy or exhaustive exploration baselines.
Limitations and When Not to Use This
AgentGL assumes that the graph structure is available and queryable at inference time, which is impractical for very large graphs (billions of nodes) where neighborhood lookups have high latency. The paper's abstract does not provide empirical results on scalability, generalization to new graph domains, or comparison against simpler baselines (e.g., standard GNNs fine-tuned for the same tasks), making it unclear whether the RL complexity is justified. The framework's performance likely depends heavily on the choice of available tools and reward signal design; poorly designed tools or sparse rewards could lead to ineffective navigation policies. Additionally, the paper does not discuss how to handle dynamic graphs where relationships change frequently, nor does it address the cold-start problem when deploying to a completely new graph domain without task labels for policy training.
Research Context
This work builds on two converging research directions: (1) agentic LLMs (e.g., ReAct, Toolformer, Gato) that combine language models with external tools and iterative decision-making, and (2) neural-symbolic graph reasoning which aims to combine learned representations with explicit structural reasoning. AgentGL extends prior graph neural network work (GCN, GraphSAGE, GAT) by making the exploration process learned and adaptive rather than fixed, similar to how neural architecture search optimized fixed design choices. The paper likely contributes to benchmarks in graph-based QA, node classification, or link prediction tasks, demonstrating that RL-driven navigation outperforms static graph encoding methods. This opens a research direction toward task-specific graph exploration policies, hybrid neuro-symbolic reasoning, and more efficient use of LLM inference tokens on structured data.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::