PaperlayerView exact revision on arXiv

Source-linked AI summary

Graphs Meet AI Agents: Taxonomy, Progress, and Future Opportunities

Yuanchen Bei, Weizhi Zhang, Siwen Wang, Weizhi Chen, Sheng Zhou, Hao Chen, Yong Li, Jiajun Bu, Shirui Pan, Yizhou Yu, Irwin King, Fakhri Karray, Philip S. Yu

arXiv:2506.18019v3cs.AI

TL;DR

Complex AI-agent tasks require planning, execution, memory, and coordination over intricate information and interactions, motivating structured representations. This survey develops a systematic taxonomy of graphs for these agent functionalities and of agents advancing graph learning, then reviews applications, challenges, and opportunities. It identifies graph-empowered agents as a basis for addressing increasingly complex task information, while noting that graph-centric benchmarks remain lacking for emerging scenarios.

  • Problem

    AI agents need reliable planning, execution, memory, and coordination, but a systematic review of how graphs support these functionalities has been absent.

  • Method

    The survey organizes graph techniques around agent planning, execution, memory, and multi-agent coordination, while also examining agents for graph annotation, synthesis, and understanding.

  • Results

    The survey synthesizes applications, open questions, challenges, and future opportunities across graph-empowered agent functionalities and reciprocal graph-learning advances.

  • Takeaways & Limitations

    Graphs offer a structured paradigm for supporting next-generation agents facing increasingly complex and messy task information.

Abstract

from arXiv · show

AI agents have experienced a paradigm shift, from early dominance by reinforcement learning (RL) to the rise of agents powered by large language models (LLMs), and now further advancing towards a synergistic fusion of RL and LLM capabilities. This progression has endowed AI agents with increasingly strong abilities. Despite these advances, to accomplish complex real-world tasks, agents are required to plan and execute effectively, maintain reliable memory, and coordinate smoothly with other agents. Achieving these capabilities involves contending with ever-present intricate information, operations, and interactions. In light of this challenge, data structurization can play a promising role by transforming intricate and disorganized data into well-structured forms that agents can more effectively understand and process. In this context, graphs, with their natural advantage in organizing, managing, and harnessing intricate data relationships, present a powerful data paradigm for structurization to support the capabilities demanded by advanced AI agents. To this end, this survey presents a first systematic review of how graphs can empower AI agents. Specifically, we explore the integration of graph techniques with core agent functionalities, highlight notable applications, and identify prospective avenues for future research. By comprehensively surveying this burgeoning intersection, we hope to inspire the development of next-generation AI agents equipped to tackle increasingly sophisticated challenges with graphs. Related resources are collected and continuously updated for the community in the Github link.

I. INTRODUCTION

AI agents have progressed from RL-based systems to LLM-powered and increasingly integrated RL–LLM architectures, but complex tasks still require reliable planning, execution, memory, and coordination amid disorganized information. This survey presents a systematic graph-centered taxonomy of these capabilities, reciprocal graph-learning advances, applications, challenges, and future opportunities.

  • Complex real-world tasks require agents to plan, execute with external tools, maintain memory, and coordinate with other agents despite intricate information, operations, and interactions.
  • Graphs organize entities and their explicit or implicit relationships into structures that can be customized for specific environments, tasks, operators, and applications.
  • Its taxonomy spans graph organization and knowledge extraction, AI-agent paradigms, agents for graph annotation and synthesis, graphs for agent functionalities, applications, and future opportunities.
  • Existing surveys address graphs in reinforcement learning or LLM enhancement, whereas this work targets the previously absent systematic review of graphs across AI-agent functionalities.
  • The survey provides a first systematic review of how graph techniques support agent planning, execution, memory, and multi-agent coordination while agents can advance graph learning.
  • The paper further synthesizes meaningful applications, key challenges, and future research opportunities for graph-empowered agents.

II. PRELIMINARIES

The preliminaries define AI agents as goal-directed models and distinguish RL-based agents from newer LLM agents with memory and tool use. They describe RL as interaction-driven sequential decision-making and explain why its feedback, simulation, and reward structure fit agent learning.

  • A. AI Agents: An AI agent perceives its environment and makes autonomous decisions to achieve specific goals; traditional agents are mainly optimized through reinforcement learning.
  • A. AI Agents: LLM agents extend perception and task planning with memory mechanisms and external tool usage, while RL and LLM technologies are increasingly merging.
  • B. Reinforcement Learning: Reinforcement learning learns through actions, observations, consequences, and scalar rewards or penalties to optimize sequential decisions for long-term return.
  • B. Reinforcement Learning: RL suits agents because its interaction-feedback loop reflects continuous perceive-act cycles and supports learning from experience without heavy reliance on labeled datasets.
  • B. Reinforcement Learning: Fast simulators let RL agents accumulate experience through self-play or exploration, while reward design directly encodes task objectives for customized learning strategies.

C. Large Language Models

LLMs provide versatile foundations for agents, while graphs organize complex information and operators into structures that support agent functionalities and graph learning. The survey frames this relationship through a taxonomy spanning agent planning and broader graph-agent integration.

  • C. Large Language Models: LLMs can serve as agent foundation models across tasks because their language understanding, generation, tool use, and memory-management abilities support varied scenarios without costly task-specific retraining.
  • C. Large Language Models: Graphs organize entities and relationships into structured representations, while graph learning extracts knowledge by aggregating information across nodes and their neighborhoods.
  • C. Large Language Models: Graph organization can support task planning through subtask dependency graphs, memory through graph structures, and multi-agent communication through graph topologies.
  • C. Large Language Models: The survey’s taxonomy covers graph support for planning, execution, memory, and multi-agent coordination, alongside the reciprocal use of agents to strengthen graph learning.
  • C. Large Language Models: Planning uses graphs to organize task reasoning, arrange task decomposition, and construct efficient task-decision search processes.

A. Task Reasoning

Graph structures enhance LLM-agent task reasoning by supplying external knowledge and organizing intermediate thoughts into trees or more general graphs. These approaches support multi-hop retrieval, multiple reasoning paths, and structured evaluation.

  • A. Task Reasoning: Knowledge-graph-assisted reasoning augments agents with multi-hop subgraph information from auxiliary knowledge graphs, whose nodes represent entities or concepts and whose edges represent relationships.
  • A. Task Reasoning: QA-GNN combines language models with auxiliary knowledge graphs through relevance scoring and graph neural-network updates to address structured reasoning tasks.
  • A. Task Reasoning: ToG and KG-CoT use knowledge-graph retrieval-augmented generation to extract prompt entities and retrieve relevant graph information for LLM-agent reasoning,.
  • A. Task Reasoning: Structure-enhanced reasoning organizes intermediate thinking with trees or graphs, enabling agents to explore multiple reasoning paths and evaluate current states globally.

B. Task Decomposition

Task decomposition represents subtasks and their dependencies as task dependency graphs, typically directed acyclic graphs. Agents then plan execution paths over these structures using LLMs, reinforcement learning, or graph neural networks, while state-space graphs support decision search.

  • B. Task Decomposition: A task dependency graph represents decomposed subtasks as nodes and execution dependencies as directed edges, typically forming a directed acyclic graph to avoid dead loops.
  • B. Task Decomposition: TDGs can be built by using LLM reasoning to infer implicit subtask dependencies or by directly constructing graphs from explicit subtask relationships.
  • B. Task Decomposition: Planning over a TDG identifies connected acyclic paths or subgraphs and sequentially invokes subtasks, using LLMs, reinforcement learning, or GNNs.
  • B. Task Decomposition: Task-decision searching models states and transitions as a state-space graph, making sequential decisions through graph-structured state changes.
  • B. Task Decomposition: MCTS organizes states and actions hierarchically to explore possible decisions efficiently, while recent methods add memory or evolutionary search to improve online performance or interpretability –.
  • B. Task Decomposition: Execution follows planning and involves tool usage and environment interaction, with graphs organizing tool schedules and agent-environment relationships.
  • B. Task Decomposition: Graph-based tool organization can represent an agent as a DAG whose nodes are functions and whose edges encode information flow, supporting management of many tools.

B. Environment Interaction

Graphs model relationships among agents and environmental entities to support perception and interaction. Although heuristic relationships are widely used, their limited generalization motivates learning-based methods that adapt relationship weights or embeddings across environments.

  • B. Environment Interaction: Graphs model connectivity, spatial proximity, and interaction dependencies among agents and environmental entities, while scene graphs encode objects and their spatial or semantic relationships.
  • B. Environment Interaction: Heuristic-based relationships rely on manually defined prior knowledge and are widely used, but they struggle to generalize across environments.
  • B. Environment Interaction: RL agents use environment graphs to represent relationships in settings including urban driving, warehouse scheduling, communication networks, and online advertising.
  • B. Environment Interaction: Scene graphs provide structured environmental representations that complement LLM reasoning and improve environmental understanding for agents operating in situated environments,.
  • B. Environment Interaction: Learning-based methods initialize relationships and then adapt relationship weights or node embeddings with learnable parameters, Transformers, or GATs.

V. GRAPHS FOR AGENT MEMORY

Graphs organize agent memory as interconnected knowledge and experiences, supporting retrieval, maintenance, and richer relational understanding. Recent approaches use structured, hierarchical, and graph-specific retrieval mechanisms to improve memory usefulness and efficiency.

  • Graph-structured memory represents knowledge and experiences as interconnected information, helping agents uncover latent associations and improve execution over extended periods.The organization is motivated by relational and contextual memory models.
  • Knowledge graphs, atomic facts, summarized notes, and hierarchical representations provide increasingly structured ways to organize agents’ long-term memory.Hierarchical systems can preserve low-level details, high-level summaries, and selectively share relevant information with teammates.
  • Graph-based retrieval augments similarity search by targeting informative knowledge subgraphs through semantic similarity, graph metrics, or triple-scoring mechanisms.These designs focus on improving the accuracy of retrieved knowledge that guides agent decisions.
  • Efficiency-oriented retrieval methods reduce processing costs through divide-and-conquer search or flow-based pruning while aiming to preserve retrieval quality.GRAG targets linear-time subgraph retrieval, while PathRAG reduces latency while maintaining recall.

C. Memory Maintenance

Graph-based agent memory must evolve with new experiences and interactions rather than merely organize static knowledge. Dynamic and hierarchical graph architectures update contextual representations, track progress, and preserve long-term relationships.

  • C. Memory Maintenance: Dynamic graph memory addresses the need to continuously update memory representations and graph topologies as agents encounter new experiences and interactions.
  • C. Memory Maintenance: A-MEM dynamically indexes and links memories, while AriGraph separates episodic observations from semantic knowledge to refine contextual memory over time.
  • C. Memory Maintenance: Hierarchical dynamic memories organize experience and goal nodes across levels, enabling journey tracking and long-term progress summaries.DAMCS uses lower-level experience nodes and higher-level long-term goal nodes.
  • C. Memory Maintenance: Multi-agent coordination models agents as graph nodes and communication paths as edges, using task- and environment-specific relationships to support information exchange.
  • C. Memory Maintenance: Task-dependency graphs coordinate agents assigned to subtasks, enabling message passing and graph-based optimization of collaborative workflows.FLOW-GNN and LGC-MARL apply graph learning or graph-based multi-agent reinforcement learning to these workflows.
  • C. Memory Maintenance: Task-allocation relationships connect agents with task-representing nodes when explicit inter-subtask dependencies are unavailable.

2) Environment-Specific Relationship:

Environment-specific coordination graphs model agent relationships according to the characteristics of a particular setting. Because prior relationships are often unavailable, methods learn or optimize communication topologies using edge selection, graph auto-encoders, or reinforcement learning.

  • 2) Environment-Specific Relationship:: Environment-specific coordination graphs represent agents as nodes and construct relationships according to the characteristics of the target environment.
  • 2) Environment-Specific Relationship:: Existing applications model interactions for traffic, games, urban driving, and heterogeneous robotics, tailoring graph communication to distinct environments.
  • B. Coordination Topology Optimization: Because real-world settings often lack prior relationships, coordination methods must learn or optimize communication topologies for each multi-agent scenario.
  • B. Coordination Topology Optimization: Edge-importance methods initialize dense or rule-based graphs and retain useful connections through attention, importance scores, or learnable edge weights.
  • B. Coordination Topology Optimization: Graph auto-encoder methods learn node representations and predict high-confidence links to construct communication topologies.
  • B. Coordination Topology Optimization: Reinforcement-learning methods optimize whether communication edges exist through reward-guided topology updates, balancing modeling effectiveness, overhead, and efficiency.

VII. AGENTS FOR GRAPH LEARNING

AI agents can support graph learning in two broad areas: graph annotation and synthesis, and graph understanding. RL agents learn adaptive annotation or graph-modeling strategies, while LLM agents generate, reason over, and coordinate graph-processing workflows.

  • VII. AGENTS FOR GRAPH LEARNING: Agents contribute to graph learning through graph annotation and synthesis as well as graph understanding tasks.This reciprocal direction complements using graphs to empower agent capabilities.
  • A. Graph Annotation and Synthesis: Graph annotation uses reinforcement learning to formulate label querying and correction as decision-making, enabling policies that select informative annotations.GPA models active learning on graphs as a Markov decision process and can transfer a learned policy across source graphs.
  • A. Graph Annotation and Synthesis: LLM agents synthesize graphs from textual prompts, simulated interactions, causal reasoning, iterative feedback, or coordinated specialized roles.GraphMaster uses manager, perception, enhancement, and evaluation agents for graph-data synthesis.
  • Graph Understanding: RL agents adapt graph-learning mechanisms, such as determining node-specific aggregation depth instead of relying on fixed modeling logic.Policy-GNN uses reinforcement learning to choose the number of aggregations for each node.
  • Graph Understanding: LLM agents process text-described graph information for downstream tasks, using graph-to-token transformations, supervised tuning, and reasoning-oriented training.
  • Graph Understanding: Multi-agent LLM systems divide graph modeling into specialized subtasks such as data processing, architecture selection, and graph-task execution.

VIII. APPLICATIONS

Graph techniques support scientific, embodied, game, and information-retrieval agents by structuring domain knowledge, environments, strategic interactions, and evidence-gathering processes.

  • Scientific Computing: Graph learning connects scientific knowledge with agents and models structured molecular or protein data for scientific discovery and bioinformatics analysis.The survey describes ontology knowledge graphs for interdisciplinary discovery and hypothesis generation, alongside graph learning aligned with domain structures.
  • Embodied AI: Scene graphs provide structured environment representations that improve embodied agents’ scene understanding and guide navigation or LLM-based planning.Reported examples use GNN embeddings for reinforcement-learning navigation and scene-graph-guided semantic search with plan refinement.
  • Game AI: Response graphs model strategic interactions in games and reveal connections between different game types.Their value follows from representing interactions among players, characters, and environments.
  • Agentic Information Retrieval: Graph-based retrieval agents interactively explore knowledge graphs to retrieve information, reason over evidence, and refine search after failures.Reward signals can encourage effective queries, iterative evidence gathering, and decisions about when to invoke external knowledge.

E. Industrial and Automation Systems

Industrial and automation agents require scalable, dynamically evolvable, and robust systems, while graph-agent research still faces fragmented evaluation and unresolved privacy and security challenges.

  • Industrial and Automation Systems: Industrial agent systems target warehousing, manufacturing scheduling, and related applications, with scalability, dynamic evolvability, and robustness as key capabilities.These capabilities are framed within Industry 4.0 and IoT-driven automated production.
  • Benchmarking Evaluation: Graph-agent benchmarks remain difficult to compare because task definitions and evaluation data differ across existing resources.The survey calls for future benchmarks that jointly evaluate graph-based models, LLMs, and RL in complex multi-agent settings.
  • Privacy and Security: Graph organization links agents and external tools for message sharing, but communication involving private information creates data-privacy requirements.The survey identifies privacy-preserving communication between private-domain agents as a future direction.
  • Privacy and Security: Agent communication topologies must defend against adversarial attacks while maintaining communication effectiveness.This frames security as a joint requirement on graph structure and communication mechanisms.

D. Multimodal Agents

Multimodal agents need to integrate heterogeneous information streams, while graph learning offers structures for aligning modality entities and enriching secure agent–data interaction.

  • D. Multimodal Agents: Graph learning can abstract and connect text, vision, speech, environmental, and object information for multimodal agents.The survey presents graph techniques as a way to align modality entities across external-world observations and environmental states.
  • E. Model Context Protocol: MCP provides a unified, structured, and secure standard for LLM agents to exchange context with external data, tools, and services.Graph learning is proposed as an enhancement to this structured interaction framework.
  • E. Model Context Protocol: Graph learning can integrate heterogeneous sources into a unified knowledge graph and uncover relationships that enrich MCP-accessible context.The proposed benefit is more comprehensive and accurate context for model problem-solving.
  • E. Model Context Protocol: Graph learning can model agent behavior and preferences to recommend suitable tools and data sources through MCP.This is presented as a way to improve tool-location efficiency and agent productivity.
  • X. CONCLUSION: The survey reviews graph techniques across planning, execution, memory, and multi-agent coordination while identifying applications and future opportunities.Its scope covers the intersection of graph techniques and AI agents and aims to support agents facing complex, messy task information.
Loading 2506.18019v3…