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

arXiv: https://arxiv.org/abs/2506.18019 · HTML: https://mlsanity.com/paper/2506.18019/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Placed in Web, search, and research agents, one of 16 directions in LLM agents and tool use.
- Builds on 188 of its 242 references that are in the map.
- First posted on arXiv 22 Jun 2025.

## Placed in

- LLM agents and tool use / [Web, search, and research agents](https://mlsanity.com/agents/web-search-and-research-agents/)

## Builds on (most cited first, 30 of 188)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [A Survey on Large Language Model based Autonomous Agents](https://mlsanity.com/paper/2308.11432/) (2023)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [From Local to Global: A Graph RAG Approach to Query-Focused Summarization](https://mlsanity.com/paper/2404.16130/) (2024)
- [Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning](https://mlsanity.com/paper/2503.09516/) (2025)
- [τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains](https://mlsanity.com/paper/2406.12045/) (2024)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [AgentBench: Evaluating LLMs as Agents](https://mlsanity.com/paper/2308.03688/) (2023)
- [A Survey on Evaluation of Large Language Models](https://mlsanity.com/paper/2307.03109/) (2023)
- [A-MEM: Agentic Memory for LLM Agents](https://mlsanity.com/paper/2502.12110/) (2025)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [ExpeL: LLM Agents Are Experiential Learners](https://mlsanity.com/paper/2308.10144/) (2023)
- [Large Language Model based Multi-Agents: A Survey of Progress and Challenges](https://mlsanity.com/paper/2402.01680/) (2024)
- [A Survey on Knowledge Graphs: Representation, Acquisition and Applications](https://mlsanity.com/paper/2002.00388/) (2020)
- [A Survey on the Memory Mechanism of Large Language Model based Agents](https://mlsanity.com/paper/2404.13501/) (2024)
- [API-Bank: A Comprehensive Benchmark for Tool-Augmented LLMs](https://mlsanity.com/paper/2304.08244/) (2023)
- [Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models](https://mlsanity.com/paper/2310.04406/) (2023)
- [A Brief Survey of Deep Reinforcement Learning](https://mlsanity.com/paper/1708.05866/) (2017)
- [A Survey on RAG Meeting LLMs: Towards Retrieval-Augmented Large Language Models](https://mlsanity.com/paper/2405.06211/) (2024)
- [GraphMAE: Self-Supervised Masked Graph Autoencoders](https://mlsanity.com/paper/2205.10803/) (2022)
- [Multi-Agent Collaboration Mechanisms: A Survey of LLMs](https://mlsanity.com/paper/2501.06322/) (2025)
- [Understanding the planning of LLM agents: A survey](https://mlsanity.com/paper/2402.02716/) (2024)

## Built on by (most cited first, 23 of 23)

- [Code as Agent Harness](https://mlsanity.com/paper/2605.18747/) (2026)
- [A Survey of Agent Memory in the Second Half: Towards Self-Evolving and Long-Horizon Agents](https://mlsanity.com/paper/2602.06052/) (2026)
- [Graph-based Agent Memory: Taxonomy, Techniques, and Applications](https://mlsanity.com/paper/2602.05665/) (2026)
- [Youtu-GraphRAG: Vertically Unified Agents for Graph Retrieval-Augmented Complex Reasoning](https://mlsanity.com/paper/2508.19855/) (2025)
- [RAG-Anything: All-in-One RAG Framework](https://mlsanity.com/paper/2510.12323/) (2025)
- [AgentGuardian: Learning Access Control Policies to Govern AI Agent Behavior](https://mlsanity.com/paper/2601.10440/) (2026)
- [CARD: Towards Conditional Design of Multi-agent Topological Structures](https://mlsanity.com/paper/2603.01089/) (2026)
- [UFO3: Weaving the Digital Agent Galaxy](https://mlsanity.com/paper/2511.11332/) (2025)
- [Securing Multi-Agent Systems Against Corruptions via Node Contribution Backpropagation](https://mlsanity.com/paper/2510.19420/) (2025)
- [Mixture of Sequence: Theme-Aware Mixture-of-Experts for Long-Sequence Recommendation](https://mlsanity.com/paper/2604.20858/) (2026)
- [MOC: Multi-Order Communication in LLM-based Multi-Agent Systems](https://mlsanity.com/paper/2606.02359/) (2026)
- [RubricsTree: Scalable and Evolving Open-Ended Evaluation of Personal Health Agents across Health Memory and Medical Skills](https://mlsanity.com/paper/2606.18203/) (2026)
- [Self-Evolving Agents as Dynamic Graph Transformation: A Survey and New Perspective](https://mlsanity.com/paper/2608.18104/) (2026)
- [Think Locally, Explain Globally: Graph-Guided LLM Investigations via Local Reasoning and Belief Propagation](https://mlsanity.com/paper/2601.17915/) (2026)
- [Graph Engineering in the Era of LLM Agents: From Individual Intelligence to System Intelligence](https://mlsanity.com/paper/2608.21156/) (2026)
- [PRAXIS: Integrating Program Analysis with Observability for Root-Cause Analysis](https://mlsanity.com/paper/2512.22113/) (2025)
- [The Semantic Lifecycle in Embodied AI: Acquisition, Representation and Storage via Foundation Models](https://mlsanity.com/paper/2601.08876/) (2026)
- [Beyond Individual Mimicry: Constructing Human-Like Social network with Graph-Augmented LLM Agents](https://mlsanity.com/paper/2605.12512/) (2026)
- [Toward User Preference Alignment in LLM Recommendation via Explicit Context Feedback](https://mlsanity.com/paper/2605.29141/) (2026)
- [Multi-Agent Agentic Graph Learning via Structural Signatures](https://mlsanity.com/paper/2609.09565/) (2026)
- [Towards a Declarative Agentic Layer for Intelligent Agents in MCP-Based Server Ecosystems](https://mlsanity.com/paper/2601.17435/) (2026)
- [LLMs+Graphs: Toward Graph-Native, Synergistic AI Systems](https://mlsanity.com/paper/2606.11560/) (2026)
- [Towards Self-Evolving Agents: A Human-Inspired Adaptive Exploration-Exploitation Framework for Genetic Network Programming](https://mlsanity.com/paper/2607.11913/) (2026)

## Abstract (arXiv)

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.