How Graphs Empower AI Agents: Taxonomy, Advances, and Future Opportunities

Overview

Recent review on Graphs and AI Agents proposes a classification framework to organize research progress, discussing the role of graph technology in core functions of AI agents such as planning, execution, memory, and multi‑agent coordination.

Key Topics

Graph methodology: using graphs for data organization and knowledge extraction.

AI agent methodology: large language model (LLM) based foundation models and reinforcement learning (RL) paradigms constitute core AI agent processes.

AI agents for graphs: agents' strong capabilities in graph modeling and learning, e.g., graph annotation, synthesis, understanding.

Graphs for AI agents: role and potential of graph and graph learning in enhancing agent core functions.

Representative applications.

Challenges and future opportunities.

1. Graphs for Agent Planning

Task Reasoning

Knowledge graph assisted reasoning: use knowledge graphs (KG) to assist AI agents in task reasoning by extracting multi‑hop subgraph information, enhancing understanding. Representative methods include QA‑GNN, ToG, KG‑CoT, RoG, MindMap, and PoG.

Structured reasoning: organize LLM agents' intermediate thought processes in tree or graph structures to improve efficiency and accuracy. Representative methods include ToT, RATT, GoT, Graph of Thoughts, and RwG.

Task Decomposition

Task Dependency Graph (TDG): decompose complex tasks into sub‑tasks and build a dependency graph. Representative methods: DAG‑Plan, LGC‑MARL, VillagerAgent, DynTaskMAS, Plan‑over‑Graph.

Planning methods: leverage LLM reasoning and GNN to optimize sub‑task execution paths. Representative methods: AgentKit, DAG‑Plan, FGRL.

2. Task Decision Search

State Space Graph (SSG): construct a state‑space graph and apply algorithms such as Monte Carlo Tree Search (MCTS) for efficient decision search. Representative methods: MCTS, PromptAgent, LATS, M‑MCTS, MENS‑DTRL, MCGS, GBOP, CMCGS.

Optimization methods: introduce memory mechanisms, evolutionary algorithms, and graph structure optimization to improve search efficiency and decision quality.

3. Graphs for Agent Execution

Tool usage: graph techniques help agents manage and invoke many tools efficiently by building tool graphs and optimizing call paths, reducing token consumption and improving accuracy.

Environment interaction: graphs enhance agents' understanding and interaction with environments through heuristic and learned relational modeling; scene graphs and dynamic learning provide richer environmental information.

4. Graphs for Agent Memory Management

Memory Organization

Knowledge Graphs (KG): constructing KGs allows agents to store knowledge and experience in a structured form for retrieval and reasoning. Systems include AriGraph, IKG, Graphusion, MemGraph, Mind Map, StructuralMemory, DAMCS, GraphRAG, and KG‑Retriever.

Memory Retrieval

Graph retrieval methods: combine semantic similarity and graph metrics to design customized retrievers, improving accuracy and efficiency. Examples: G‑Retriever, GFM‑RAG, SubgraphRAG, LightRAG, GRAG, PathRAG.

Memory Maintenance

Dynamic update and maintenance: methods focus on dynamically updating graph‑based memory to adapt to new experiences. Examples: A‑MEM (dynamic indexing), Zep (time‑aware hierarchical KG), HippoRAG, LightRAG (incremental updates), KG‑Agent (LLM‑driven updates), InstructRAG (RL‑based maintenance).

5. Graphs for Multi‑Agent Coordination

Coordination Message Passing

Task dependency: use TDG to optimize message passing, e.g., FLOW‑GNN, LGC‑MARL.

Task allocation: optimize information exchange via allocation graphs, e.g., RandStructure2Vec, MAGNNET.

Environment‑specific relations: model agent relations based on environment characteristics, e.g., GRL, MAGNNETO, GraphComm, MAGI.

Coordination Topology Optimization

Edge importance measurement: learn latent edge weights via attention or parameterized mechanisms, e.g., DICG, G2ANet.

Graph auto‑encoder optimization: predict edges between agent nodes, e.g., G‑Designer, GNN‑VAE.

Reinforcement learning: optimize edges with reward functions, e.g., HGRL, GPTSwarm.

For more details, see the repository https://github.com/YuanchenBei/Awesome-Graphs-Meet-Agents and the arXiv paper https://arxiv.org/pdf/2506.18019.