PaperlayerView exact revision on arXiv

Source-linked AI summary

AgentGL: Towards Agentic Graph Learning with LLMs via Reinforcement Learning

Yuanfu Sun, Kang Li, Dongzhe Fan, Jiajin Liu, Qiaoyu Tan

arXiv:2604.05846v2cs.CL

TL;DR

Agentic systems largely treat external information as unstructured text, leaving graph topology underused in relational data. AgentGL addresses this gap by combining topology-aware graph navigation, LLM reasoning, and reinforcement learning, and reports improvements of up to 17.5% in node classification and 28.4% in link prediction over GraphLLM and GraphRAG baselines.

  • Problem

    Existing agentic frameworks mainly operate on unstructured text and overlook relational structures in Text-Attributed Graphs.

  • Method

    AgentGL combines graph-native multi-scale search, search-constrained thinking, and graph-conditioned curriculum RL for topology-aware graph reasoning.

  • Results

    AgentGL achieves the best average performance across backbones, with absolute gains of up to 17.5% on node classification and 28.4% on link prediction.

  • Takeaways & Limitations

    AGL provides a framework for LLM agents to autonomously navigate and reason over complex relational environments.

  • Takeaways & Limitations

    AgentGL currently supports text-attributed rather than multimodal-attributed graphs, and extending it to denser graphs remains future work.

Abstract

from arXiv · show

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.

1 Introduction

Existing agentic systems retrieve and reason over unstructured text, leaving relational structure underused in graph data. AgentGL introduces agentic graph learning by combining topology-aware exploration, LLM reasoning, and reinforcement learning.

  • Motivation: Agentic frameworks mainly operate on unstructured text, overlooking relational dependencies in Text-Attributed Graphs.This limits their ability to use structural evidence alongside textual content.
  • Challenges: AGL requires navigation across multi-scale evidence while learning long-horizon policies without ground-truth search trajectories.Agents must balance local and broader structural exploration while avoiding redundant regions.
  • AgentGL: AgentGL formulates graph learning as an RL-optimized agentic decision-making process.It is presented as the first RL-driven AGL framework.
  • AgentGL: AgentGL combines graph-native search tools, search-constrained thinking, and graph-conditioned curriculum RL for adaptive topology-aware policies.The tools support multi-scale exploration, while the training strategy targets stable long-horizon learning without step-wise supervision.
  • Agentic Graph Learning: AGL treats graph learning as an interleaved process of topology-aware exploration and LLM-based reasoning.The formulation unifies graph structure, text semantics, and agentic decision-making.
  • Results: 17.5% and 28.4% are the maximum absolute accuracy improvements reported for node classification and link prediction, respectively.The evaluation spans multiple TAG benchmarks, graph tasks, and LLM backbones against GraphLLM and GraphRAG baselines.

2 Related Work

Prior graph-learning approaches connect LLMs with graph information through textualized structures, graph representations, or retrieval, but existing methods remain limited in adaptivity or optimization.

  • Graph Learning with LLMs: One line of work textualizes local graph structures into natural-language descriptions for LLM reasoning and contextualized representations.This approach focuses on converting local structural information into text.
  • Graph Learning with LLMs: Another line injects graph tokens or structure-aware embeddings into prompts for graph instruction tuning.These methods encode graph information as prompt-level representations.
  • GraphRAG: GraphRAG methods retrieve evidence from graph-structured data but often reconstruct synthetic graphs from flat corpora.The supplied passage also notes limitations in their task scope.
  • Agentic Graph Learning: GraphCoT targets graph QA and GraphSearch targets graph learning, yet both rely on heuristic prompting with limited optimization.The passage characterizes these approaches as often yielding suboptimal solutions.

3 Problem Statement

The paper studies agentic graph learning on Text-Attributed Graphs, where predictions for nodes or node pairs are grounded in graph-derived evidence. It formalizes this process as sequential policy-driven interaction with graph-native search tools.

  • Setting: A Text-Attributed Graph is represented as G = (V, A, T), with nodes, an adjacency matrix, and node texts.Here, V is the node set, A is the adjacency matrix, and T contains node texts.
  • Tasks: The study focuses on node classification and link prediction, predicting a label for a node or node pair using graph-derived evidence.The target instance may be a node v or a node pair (u, v).
  • Sequential Decision Process: AGL is formulated as a sequential decision process in which a policy selects graph-native search tools or ANSWER actions.The resulting trajectory accumulates evidence and produces a final prediction while optimizing expected reward.

4 Methodology

AgentGL trains an LLM to navigate Text-Attributed Graphs with graph-native search tools, then optimize search efficiency while preserving reasoning accuracy. Its methodology combines multi-scale retrieval, reinforcement learning, search-constrained thinking, and graph-conditioned curriculum learning.

  • Graph-Native Search Policy Bootstrapping: AgentGL uses graph-native tools for multi-scale evidence retrieval, including 1-hop, 2-hop, structure-salience, and graph-dense searches.These tools cover local versus global exploration and structural versus semantic evidence.
  • Graph-Native Search Policy Bootstrapping: AgentGL optimizes tool use with reinforcement learning and composite rewards for format adherence, task accuracy, and graph-native search coverage.The framework instantiates critic-free GRPO and REINFORCE++ optimization algorithms, while coverage rewards encourage early exploration of the available tools.
  • Graph-Native Search Policy Bootstrapping: The agent follows a reason–act–observe loop in which each action selects a graph-search tool and textual query, retrieves structural evidence, and appends the interaction to its history.Rollouts terminate when the agent outputs an answer or exhausts the search budget.
  • Less is More: Mitigating Search Overuse: Search-constrained thinking minimizes redundant retrieval by optimizing search cost within the accuracy-preserving solution space and encouraging retrospective evidence checks.Cognitive density regularization penalizes sparse post-retrieval reasoning so that fewer searches reflect deeper evidence processing.
  • Graph-Conditioned Curriculum Learning: Graph-conditioned curriculum learning orders training from easier to harder instances using graph-derived structural and semantic difficulty signals.For node classification, the curriculum uses neighbor-label consistency and degree-based scoring to progress from structurally prominent hubs to ambiguous, heterophilous cases.

5 Experiments

Experiments evaluate AgentGL across diverse TAG datasets, tasks, baselines, LLM backbones, and ablations. AgentGL consistently improves predictive performance while curriculum and multi-stage training improve search efficiency, convergence, and accuracy.

  • Experimental Setup: Experiments cover 7 TAG datasets across 3 domains, 13 baselines, five baseline categories, and two LLM backbones.Training uses OGB-Arxiv and OGB-Products, with evaluation spanning in-domain and zero-shot transfer settings.
  • Overall Performance: AgentGL achieves the best overall performance across tasks and domains, outperforming baselines in both in-domain and zero-shot evaluations.With Qwen7B, average gains reach 12.7% for in-domain NC, 24.4% for zero-shot NC, 26.3% for in-domain LP, and 22.4% for zero-shot LP.
  • Overall Performance: Static GraphRAG and GraphLLM context stuffing is consistently outperformed by AgentGL’s interleaved graph searching and reasoning.The reported pattern suggests greater robustness under distribution shifts through adaptive evidence acquisition and suppression of irrelevant context.
  • Overall Performance: Scaling from 3B to 7B improves NC by 9.0% in-domain and 11.8% zero-shot, and LP by 5.6% in-domain and 8.7% zero-shot.The improvement is especially pronounced for zero-shot transfer, where larger backbones better learn and generalize tool-use policies.
  • Multi-Stage Training: Omitting either RL training stage causes simultaneous efficiency and performance declines, whereas combining both stages reduces tool calls by about 17.5% and improves NC accuracy by 2.4%.GNSPB alone maintains relatively strong performance but nearly exhausts search budgets; MSO alone can collapse toward zero-search behavior.
  • Component-wise Ablations: RTT and CDR jointly reduce converged search cost by approximately 22% while improving accuracy by 3%, and λr = 0.5 gives optimal performance.GCCL accelerates reward convergence, stabilizes search frequency, and improves accuracy by approximately 0.65%.

6 Conclusion

AgentGL reframes graph learning as interleaved topology-aware exploration and LLM reasoning, outperforming strong GraphLLM and GraphRAG baselines across backbones and benchmarks.

  • AgentGL is an RL-driven framework that interleaves topology-aware exploration with LLM-based reasoning for graph learning.
  • AgentGL achieves the best average performance across all evaluated LLM backbones and benchmark settings.
  • 17.5% absolute gain is achieved on node classification, while 28.4% absolute gain is achieved on link prediction.

7 Limitations

AgentGL is currently limited to text-attributed graphs and faces additional design and scalability questions concerning training-stage allocation, inference-time tool usage, and denser graphs.

  • AgentGL currently supports text-attributed graphs but not multimodal-attributed graphs.This limits applicability when nodes contain richer modal information.
  • Stable performance in the MSO stage depends on carefully allocating data between the two training stages.
  • The effect of the MSO stage on inference-time tool-use distributions remains open for investigation.
  • Extending AgentGL to denser graphs remains a potential direction for future exploration.

A.1 Dataset Details

The evaluation covers seven text-attributed graph benchmarks across citation, e-commerce, and social domains, using node classification and link prediction tasks with controlled preprocessing and splits.

  • Seven TAG benchmarks span citation networks, e-commerce product graphs, and social networks.Each node has natural-language text, while edges encode native relational structures.
  • The evaluation uses node classification and link prediction as its two classical graph-learning problems.Node classification combines multi-hop structural cues with node text, while link prediction tests relational reasoning and neighborhood consistency under sparse supervision.
  • Data splits: OGB-Arxiv and OGB-Products use 3,000 sampled training nodes and 1,000 sampled test nodes for node classification.Arxiv-2023 retains its original split with test subsampling.
  • Data splits: Reddit is converted from a multimodal graph into a TAG by removing image attributes and retaining textual fields.
  • Preprocessing: Qwen2.5-72B-Instruct generates concise rewrites of node attributes for AgentGL and all baselines.The shared preprocessing controls context length and maintains the same input budget for comparison.

A.2 More Related Work: GraphRAG vs. AGL

GraphRAG uses graphs as retrieval scaffolds for text generation, whereas AGL treats native graph structure as the primary task environment for graph learning and reasoning.

  • GraphRAG: GraphRAG-style methods use graphs to select and organize textual evidence for open-ended question answering or long-form generation.
  • AGL: AGL treats the graph as the primary problem instance rather than as an external knowledge base.
  • AGL: AGL targets graph-native tasks whose correctness depends on structural signals such as neighborhood composition and multi-hop dependencies.Examples include node classification and link prediction.
  • AGL: AGL agents interact through graph-native operators that return nodes’ text attributes and terminate with a discrete task output.

A.3 Implementation Details

The experiments standardize baseline implementations and constrain standard agentic search to the input graph, while AgentGL uses graph-native tools within an RL training setup. The setup specifies retrieval, rollout, optimization, encoding, and reward details for node classification and link prediction.

  • Baseline configurations: GraphRAG, GraphLLM, and GNN baselines follow their original configurations or the multi-dataset transfer protocol specified by LLaGA.GraphRAG indices use subsampled TAG nodes and original node text attributes; standard agentic baselines replace online search with graph-restricted search.
  • AgentGL configuration: AgentGL trains with graph-native search tools that return at most 5 nodes per call for node classification and append their text attributes to the model context.Training uses Open-RLHF, 16 rollouts per prompt, batch sizes of 128 and 32, a learning rate of 2e-6, and a maximum sequence length of 1600.
  • Reward design: The reward combines exact-match classification accuracy with trajectory-format constraints and penalties for missing, invalid, leaked, or overly verbose answers.Stage 1 additionally rewards distinct graph-native tools, while Stage 2 rewards cognitive-density compliance using a 100-token segment threshold.
  • Task-specific configuration: For link prediction, the implementation changes the number of evidence nodes returned by each graph-native search tool while retaining the core search setup.The 1-hop and 2-hop neighborhood tools still return up to 5 nodes per call.

A.4 Additional Experiments

Additional experiments examine training variance, neighborhood-size sensitivity, and qualitative graph-native reasoning, alongside the standardized prompt and algorithm specification. They show modest overall variance, higher variance for smaller backbones, and improved node-classification accuracy through K=5 before a drop at K=7.

  • Variance analysis: Training variance is modest across node classification and link prediction, but smaller backbones are more sensitive to sampling and policy-optimization stochasticity.The difference is especially noticeable on Amazon-Photo, where 3B variants show higher variance across both tasks.
  • Sensitivity analysis: 68.9% on OGB-Arxiv and 59.9% on Amazon-Photo are achieved at K=5, the best results in the reported neighborhood-size sensitivity analysis.Increasing K from 1 to 5 consistently improves accuracy, whereas K=7 causes a slight drop on both datasets.
  • Qualitative analysis: A qualitative Amazon node-classification rollout forms a hypothesis from anchor text and verifies it with 1-hop, 2-hop, and PageRank evidence.The example illustrates evidence aggregation over multiple graph scales to reduce ambiguity before the final label.
  • Prompt design: The standardized prompts specify task instructions, search pools, output constraints, and dataset-specific placeholders while keeping the action interface invariant.Templates cover node classification and link prediction, including labels, relation descriptions, and per-pool Top-K limits.
  • Training algorithm: Algorithm 1 initializes graph-native tools, reference-policy and curriculum parameters, then produces an optimized policy through rollout and GRPO or R++ updates.The action space includes 1-hop, 2-hop, similarity, and dense-neighborhood search tools, plus ANSWER.
  • Supplementary materials: The supplementary figures provide Reddit-specific inserts, core prompt templates, dataset relation descriptions, and per-pool search-limit specifications for the evaluated tasks.Figures 4 and 5 additionally show node-classification and link-prediction reasoning cases involving graph-native retrieval.
Loading 2604.05846v2…