PaperlayerView exact revision on arXiv

Source-linked AI summary

Self-Evolving Agents as Dynamic Graph Transformation: A Survey and New Perspective

Yuanyuan Xu, Wenjie Zhang, Yin Chen, Xuemin Lin, Ying Zhang

arXiv:2608.18104v1cs.AI

TL;DR

Existing surveys underexplore how self-evolving agent states and dynamic graph topologies interact. This survey frames agent evolution as dynamic graph transformation, organizes methods into four patterns, maps nine learning families to agent capabilities, and discusses graph-aware evaluation and governance.

  • Problem

    Existing graph-agent surveys treat graphs mainly as support structures, while self-evolving-agent surveys rarely address topology evolution and their coupling remains underexplored.

  • Method

    The survey models agent states as typed dynamic graphs updated by schema-constrained rewrites, then synthesizes four transformation patterns and maps nine dynamic-graph-learning subfields to agent capabilities.

  • Results

    The survey provides a common structural language for analyzing self-evolving-agent mechanisms and extends it with graph-aware evaluation and governance that complements end-task evaluation.

  • Takeaways & Limitations

    Dynamic graph methods are positioned as reusable infrastructure for discussing and governing controllable self-evolving agents.

Abstract

from arXiv · show

Large language model (LLM)-based agents are increasingly becoming self-evolving systems that persist across interactions, maintain memories, use tools, acquire skills, refine workflows, and coordinate with other agents. These capabilities make agent states structural and dynamic: entities, relations, attributes, dependencies, and execution structures change with new evidence, feedback, and environmental conditions. Existing graph-agent surveys typically treat graphs as support structures for agent functions rather than as evolving substrates, while self-evolving-agent surveys focus on agent-level mechanisms and rarely discuss graph topology evolution. Thus, the coupling between evolving agent state and dynamic graph topology remains underexplored. This survey connects these two research lines by framing \textit{agent evolution as dynamic graph transformation}. We model agent state as a dynamic graph, where memories, tools, skills, workflows, and inter-agent relations are represented as typed nodes, edges, and subgraphs updated through schema-constrained rewrites. Based on this formulation, we organize existing dynamic-graph-based methods for self-evolving agents into four taxonomies: node/feature evolution, edge/topology evolution, subgraph activation, and cross-component co-evolution. Building on this taxonomy, we propose dynamic graph learning as reusable infrastructure for self-evolving agents and map nine dynamic-graph-learning subfields to agent-evolution capabilities, discussing their adaptations and possible failure modes. Finally, we discuss five types of graph-aware evaluation and governance protocols from a dynamic-graph perspective, which complement end-task evaluation. The goal is to provide a compact structural lens for designing and governing self-evolving agents.

I. INTRODUCTION

The survey frames self-evolving agents as dynamic graph transformations because memories, capabilities, workflows, and relations change through interaction, feedback, and environmental drift. It bridges agent-evolution mechanisms, dynamic graph learning, and graph-aware governance through a shared structural perspective.

  • Motivation: Self-evolving agents persist across sessions, accumulate experience, and adapt memory, tools, skills, workflows, and inter-agent relations over time.Their states are non-stationary and structurally evolving under interaction, feedback, and environmental drift.
  • Motivation: Existing graph-agent and self-evolving-agent surveys largely treat graph functionality and agent adaptation as separate perspectives, leaving their coupling underexplored.Graph-agent surveys emphasize mostly static graph support, whereas self-evolving-agent surveys emphasize reflection, self-training, self-rewarding, and experience distillation.
  • Conceptual Framing: The survey formalizes agent evolution as dynamic graph transformation using typed nodes, edges, subgraphs, temporal attributes, and schema-constrained rewrites.These rewrites model activation, propagation, and rollback across evolving agent states.
  • Systematic Taxonomy: It organizes self-evolving agent methods into four graph-transformation patterns: node/feature evolution, edge/topology evolution, subgraph activation, and cross-component co-evolution.The taxonomy provides a shared formal space for dynamic-graph-based, graph-based, and graph-transformable agent methods.
  • Infrastructure, Evaluation, and Governance: The survey maps nine dynamic-graph-learning families to agent capabilities and proposes five graph-aware evaluation and governance protocols.The capabilities include prediction, activation, generation, diagnosis, rollback, and governance; the protocols address temporal evaluation, privacy and deletion, safety, rollback, and audit.

II. PRELIMINARIES

The preliminaries model a self-evolving agent’s state as a time-indexed dynamic graph whose typed nodes, edges, attributes, and labels can represent diverse graph types. They further make this graph operational by mapping agent components and actions to graph primitives and governing state changes through feedback-validated typed rewrites.

  • Dynamic Agent Graph: Agent state is represented as a dynamic graph with time-indexed nodes, edges, node attributes, edge attributes, and labels.The formulation uses V(t), E(t), X_V(t), X_E(t), and Y(t) to describe these components.
  • Dynamic Agent Graph: The formulation covers continuous-time, discrete-time, heterogeneous, and text-attributed dynamic graphs.These include CTDGs, DTDGs, DHGs, and DyTAGs.
  • Operational Agent Graph: Graph state is operational because it conditions future agent behavior, while actions may be responses, tool calls, workflow steps, or inter-agent messages.The graph matters insofar as its state influences subsequent agent actions.
  • Node Schema: A practical base schema uses four core node types: memory, tool, skill, and agent.Memory nodes represent stored knowledge, while subgraph activation selects relevant structure without committing a state change.
  • Rewrite Semantics: Candidate graph rewrites are accepted, rejected, or rolled back according to feedback from users, tools, or other agents.Rewrite operators are formalized as typed graph-transformation rules under the double-pushout formulation, using L ← K → R to specify matched, preserved, and replacement structure.

III. AGENT EVOLUTION AS DYNAMIC GRAPH TRANSFORMATION

This section organizes self-evolving-agent methods through dynamic graph and topology transformation patterns. It identifies four branches and projects 46 representative methods into rewrite patterns.

  • The methods are organized by four graph-transformation patterns: node/feature evolution, edge/topology evolution, subgraph activation, and cross-component co-evolution.
  • Fig. 2 groups 46 representative methods into the four branches.
  • Table I projects the methods into rewrite patterns.

A. Node and Feature Evolution

Node and feature evolution models localized updates to individual agent-state components as transformations over typed nodes and attributes. It encompasses adding, revising, merging, or removing memories, tools, skills, and agent states, supported by evidence for validation and rollback.

  • A. Node and Feature Evolution: Node and feature evolution captures localized changes to individual agent-state components represented as typed nodes and attributes.It corresponds to Branch A.1 in Fig. 2.
  • A. Node and Feature Evolution: Updates may insert, revise, merge, or remove memories, tools, skills, or agent states, with evidence supporting their justification, validation, or rollback.The abstraction treats component updates as transformations over typed structures.
  • A. Node and Feature Evolution: Related systems include Agent Memory Node methods TiMem, Zep, AriGraph, GAAMA, GAM, GSEM, and G-Memory.These systems are listed under agent memory-node evolution.
  • A. Node and Feature Evolution: Agent skill-node evolution is represented by SkillOps and GoS.Both systems are listed under agent skill-node methods.

A.1 Node & Feature Evolution

Node and feature evolution models memories, tools, skills, and agent states as typed graph objects updated through schema-constrained rewrites. These updates support insertion, attribute revision, archival consolidation, and deletion, but still lack calibrated validity and affected-scope tracking.

  • Typed node representations: Node evolution represents memories, tools, skills, and agent states as typed nodes with attributes encoding their evolving state.Tool nodes encode interfaces, schemas, constraints, and reliability; skill nodes encode scope, contracts, prerequisites, and validation status.
  • Dynamic node operations: Schema-constrained rewrites support observation insertion, attribute updates, archival consolidation, and deletion subject to graph-preservation conditions.INSERT creates vnew from contextual inputs, MERGE consolidates matched states while archiving source nodes, and DELETE requires removing incident edges or satisfying the dangling condition.
  • Memory evolution: Memory systems instantiate these operations by inserting observations, merging abstractions, and applying correction, decay, or quality revisions to evolving temporal structures.Zep builds a temporal knowledge graph for memories, entities, events, and provenance, while TiMem organizes interaction histories into time-aware memory levels.
  • Tools and skills: Tool and skill evolution organizes reusable capabilities and dependencies while using interaction feedback or experience to revise retrieval, acquisition, maintenance, and execution structures.SEARL maintains tool-graph memory that updates from execution feedback; other API-grounded methods can be represented through typed tool profiles and usage records.
  • Open gaps: A central gap is that node updates rarely record calibrated validity, evidence strength, or affected scope, so dependent skills, workflows, and team-selection policies may escape revalidation.The open problem is estimating which downstream components are affected after a node update.

B. Edge and Topology Evolution

Edge and topology evolution treats self-evolving agents as systems whose communication, dependency, memory-support, and workflow relations change over time. DPO-style graph transformations make these structural edits explicit while highlighting the need for downstream consistency and impact-aware validation.

  • Definition: Edge and topology evolution shifts attention from local component-state revision to changing dependency, communication, and execution relations.These changes reorganize memory support, tool–skill dependencies, workflow routing, and inter-agent coordination over time.
  • DPO Rule Schemas: Four typed DPO schemas represent topology edits: LINK, UNLINK, REWIRE, and EDGEFEATUREUPDATE.They respectively add, remove, replace, or update typed edges and their attributes while preserving the specified endpoints or edge identity.
  • Applications: Existing methods instantiate these transformations across agent communication, workflow, and skill–tool dependency relations.The surveyed mechanisms distinguish persistent communication-topology evolution from workflow rewriting and temporary team activation, while maintaining relations among skills, tools, prerequisites, compatibility, invocation, and parent agents.
  • Open Gaps: Topology editing remains weakly coupled to downstream validation, leaving redundant, safety-critical, or necessary-path edge changes insufficiently assessed.Undetected edits may break dependent skills, workflows, provenance chains, or coordination patterns, motivating impact-aware and reversible topology maintenance.

C. Subgraph Activation · D. Cross-Component Co-Evolution

The paper frames subgraph activation as read-only, relevance-conditioned selection for task-time reasoning or execution, while cross-component co-evolution models persistent updates propagated through dependencies. These formulations expose intermediate activation decisions and cascade scope as evaluation and governance targets beyond final task success.

  • C. Subgraph Activation: Subgraph activation selects a transient support subgraph from a persistent graph for task-time reasoning or execution.The central problem is relevance-conditioned selection among available states, relations, and components.
  • C. Subgraph Activation: The read-only activation schema selects Gact(t) ⊆ G(t) using task q and policy π without committing a persistent structural rewrite.This distinguishes task-time support selection from lasting graph evolution.
  • C. Subgraph Activation: Activation policies score candidate memories, tools, skills, or agents and expose limited context around selected anchors.If the selected structure is written back as a skill, workflow edge, or communication link, it belongs to A.1, A.2, or A.4 rather than A.3.
  • C. Subgraph Activation: Graph-based evaluation can measure whether agents activated appropriate support subgraphs through precision, required-evidence coverage, minimality, and temporal validity.Existing benchmarks mostly measure final task success and rarely test activation quality directly.
  • D. Cross-Component Co-Evolution: Cross-component co-evolution treats persistent system-level evolution as dependency-driven propagation after an initial local update.Revising memories, tools, or agent roles can affect dependent skills, workflows, communication, or team structures.
  • D. Cross-Component Co-Evolution: A trace belongs to A.4 when it spans ≥2 component types and later rewrites depend on or conflict with earlier rewrites.The affected subgraphs and dependency or conflict records support explicit revalidation and rollback targeting.
  • D. Cross-Component Co-Evolution: Cascade rewrites include feedback-to-capability propagation, capability or topology co-adaptation, and safety-triggered downstream revalidation.Anomalies can identify affected subgraphs for localized repair, while dependency or provenance edges determine downstream revalidation or possible rollback.
  • D. Cross-Component Co-Evolution: A major open gap is estimating affected scope because existing methods rarely expose the cascade trace connecting a trigger to downstream edits.Tool-contract changes should be traced through calling skills, containing workflows, and dependent teams.

E. Putting the Four Rewrite Branches Together · IV. DYNAMIC GRAPH LEARNING AS AGENT INFRASTRUCTURE

The paper unifies four graph-rewrite branches for self-evolving agents and uses dynamic graph learning as reusable infrastructure mapped to agent control points. Together, these views specify what changes, how it changes, whether changes persist, and how effects propagate.

  • E. Putting the Four Rewrite Branches Together: The four rewrite branches progress from local state changes to relation updates, read-only activation, and cross-component propagation.This progression connects component-state updates, relation rewrites, task-time support, and cross-component effects.
  • E. Putting the Four Rewrite Branches Together: A.1–A.4 cover persistent state maintenance, relation adaptation, task-time support activation, and control of cross-component cascades.The framework distinguishes what changes, how it changes, whether the change is persistent, and how effects propagate.
  • E. Putting the Four Rewrite Branches Together: Table I maps representative mechanisms to their triggers, rewrite operators, affected scopes, and persistence levels.This mapping provides a common language for comparing dynamic-graph-based agent methods and locating validation, rollback, and governance needs.
  • IV. DYNAMIC GRAPH LEARNING AS AGENT INFRASTRUCTURE: The graph-transformation interface exposes control points for support activation, dependency rewiring, cascade scoping, and rollback.These control points form the basis for mapping dynamic graph learning capabilities to self-evolving-agent operations.
  • IV. DYNAMIC GRAPH LEARNING AS AGENT INFRASTRUCTURE: Dynamic graph learning is positioned as reusable infrastructure for self-evolving agents through a capability mapping to the graph-transformation control points.The mapping follows dynamic-graph surveys and benchmarks cited in the paper.
  • IV. DYNAMIC GRAPH LEARNING AS AGENT INFRASTRUCTURE: The capability mapping organizes dynamic graph learning into nine DGL families.These families structure the proposed connection between dynamic graph learning and agent evolution.

A. Dynamic Graph Representation Learning … H. Dynamic Graph Unlearning

The paper maps eight dynamic-graph learning areas to self-evolving-agent capabilities, emphasizing time-aware representations, text–temporal–structural coevolution, constrained graph proposals, robust adaptation, temporal evidence, anomaly detection, and influence-aware unlearning. Across these areas, learned outputs guide activation, routing, inspection, or maintenance, while persistent graph changes require explicit rewrite validation or regeneration.

  • A. Dynamic Graph Representation Learning: Dynamic graph representation learning supports time-aware memory validity, tool and skill reliability, workflow-edge risk estimation, and early cascade alerts.CTDG encoders process irregular events for online predictions, whereas DTDG encoders summarize slower session- or deployment-level maintenance signals.
  • B. Dynamic Text-Attributed Graph Representation: Dynamic text-attributed graph encoders combine node text, temporal history, and graph structure to reduce activation of outdated but text-similar agent-state elements.Selective re-encoding is triggered when rewrites alter semantic content, temporal validity, or downstream dependencies; persistent correction still requires validated rewriting.
  • C. Dynamic Graph Generation: Dynamic graph generation proposes executable workflow or topology rewrite traces for repair, counterfactual planning, and future-evolution simulation without directly mutating persistent state.Candidates must satisfy constraints such as tool signatures and provenance, then undergo explicit rewrite validation before activation, repair, or commitment.
  • D. Temporal Graph Continual Learning: Temporal graph continual learning addresses stability–plasticity by retaining historical temporal subgraphs while adapting to new events, especially for rare or safety-critical capabilities.Dependency-aware replay gives higher weight to subgraphs containing rare skills, prerequisite tools, user-specific memories, or safety-critical provenance.
  • E. Out-of-Distribution Generalization on Dynamic Graphs: Dynamic graph OOD generalization supports valid activation and updating when node attributes, edges, and temporal interaction patterns shift across environments.Environment-aware objectives reduce worst-case deployment risk rather than optimizing only average in-distribution performance; outputs guide subgraph activation and rewrite inspection.
  • F. Temporal Knowledge Graph Reasoning: Temporal knowledge graph reasoning activates time-valid multi-hop evidence chains connecting current tasks to relevant memories, policies, tool states, and outcomes.This produces a temporally grounded support subgraph instead of relying on isolated text-similar memory retrieval.
  • G. Anomaly Detection on Dynamic Graphs: Dynamic graph anomaly detection provides early warnings for unsafe rewrites, prompt-injection propagation, tool misuse, and multi-agent collusion through rewrite- and task-phase-aware scoring.Calibration by rewrite type and task phase helps distinguish benign bursts, such as memory consolidation, from abnormal traces.
  • H. Dynamic Graph Unlearning: Dynamic graph unlearning removes event influence through deletion, rollback, and regeneration because deleted information can persist in summaries, embeddings, workflows, and routing policies.Parameter-level unlearning must be accompanied by invalidating, reverting, or recomputing provenance-linked artifacts and execution subgraphs.

I. Explanation for Temporal GNNs

Dynamic graph explanation makes temporal agent decisions auditable by producing compact evidence subgraphs for attribution, rollback, and accountability. Dynamic graph learning should guide graph transformations without directly mutating persistent agent state, which changes only through validated, localized, auditable outputs or typed rewrites.

  • Explanation for Temporal GNNs: Dynamic graph explanation supports audit and attribution by converting unclear temporal predictions into compact event-level evidence subgraphs.These explanations help operators understand memory activation, tool selection, skill revision, and workflow rewiring.
  • Explanation for Temporal GNNs: Existing dynamic graph explanation methods include temporal history explanation and causality-inspired spatiotemporal explanation.The section specifically discusses TGNNExplainer as a temporal prediction explanation method.
  • Explanation for Temporal GNNs: DGL should provide proposal and evidence signals, while dynamic graph transformation governs activation, rewriting, and rollback.DGL methods may guide activation, repair, deletion, and audit, but should not directly mutate the persistent agent graph.
  • Explanation for Temporal GNNs: Only validated, localized, and auditable outputs should affect Gact(t) or be committed as typed rewrites in G(t).This establishes a constrained interface between dynamic graph learning outputs and persistent agent-state updates.

V. GRAPH-AWARE EVALUATION AND GOVERNANCE

The section argues that evaluating self-evolving agents only by end-task success misses failures in the evolving agent state they read and update. Existing benchmarks expose parts of this problem but rarely assess whether evolving state is temporally valid, localized, or reversible.

  • Evaluation gap: End-task success is the usual evaluation criterion for self-evolving agents, despite failures arising from the evolving state they read and update.The passage identifies this mismatch as an evaluation and governance gap.
  • Evaluation gap: A correct final answer can still result from invalid agent state, including stale or future evidence.Outcome correctness therefore does not guarantee state validity.
  • Governance gap: Existing long-term-memory and tool-use benchmarks expose parts of the problem but rarely test temporal validity, localization, or reversibility of evolving agent state.The passage cites benchmarks,,,, and as partial coverage.

A. Graph-Aware Evaluation … E. Open Challenges

The paper proposes graph-aware evaluation and governance protocols that assess valid evidence use, controlled state updates, temporal validity, deletion of derived influence, safety, and audit faithfulness beyond answer-only success. It identifies observability, cascade control, and propagation-path governance as open requirements for reliable self-evolving agents.

  • A. Graph-Aware Evaluation: Graph-aware evaluation tests support-subgraph validity and rewrite locality, distinguishing correct reasoning and controlled updates from stale evidence or collateral graph damage.These checks require instrumentation exposing activated support subgraphs, rewrite traces, or locality probes.
  • A. Graph-Aware Evaluation: The evaluation framework complements task success with compact evidence-use scoring and counterfactual locality checks for unrelated behaviors.Compact support scoring can penalize overly broad activation, while locality alone cannot establish successful repair.
  • B. Leakage-Free Temporal Protocols: Leakage-free temporal evaluation trains on pre-cutoff graph and observation histories, then evaluates each decision using only state and observations available before that decision.Indexes, summaries, negative tool edges, and reliability calibration must be rebuilt or sampled without future information.
  • C. Privacy and Deletion in Evolving Agent Graphs: Privacy evaluation must verify removal of deleted evidence’s influence from derived skills, workflows, routing policies, and end-to-end agent behavior, not merely remove source nodes or edges.Counterfactual replay requires controlled randomness and complete provenance to distinguish residual influence from trajectory noise.
  • D. Safety, Rollback, and Audit: Graph-aware safety governance combines precommit admissibility checks, anomaly detection, cascade-based rollback, and audit evidence that explains reviewed activations or rewrites.Structural failures can propagate through memories, dependency edges, tools, and multi-agent communication paths.
  • D. Safety, Rollback, and Audit: Faithful audits should identify evidence whose masking changes the agent’s activation or rewrite decision, making explanations useful for review and rollback.The criterion is evaluated under deterministic decoding while preserving executable graph structure during replay-time masking.
  • E. Open Challenges: Open challenges require benchmarks to expose activated support graphs, valid-time evidence, provenance paths, and rewrite histories rather than observing only final answers.These signals should be observable independently of any single-agent implementation.
  • E. Open Challenges: Reliable workflow self-repair requires predicting and bounding topology cascades before commitment while governing harmful propagation paths across multi-agent collaboration structures.The goal is to control downstream role, edge, and execution-dependency changes without silently destabilizing collaboration topology.

VI. CONCLUSION

The paper frames self-evolving agents as dynamic graph transformations, providing a common structural lens for organizing existing methods. Its mapping from dynamic graph learning to agent evolution remains conceptual and lacks empirical evaluation.

  • Conclusion: The dynamic-graph perspective frames agent evolution as graph transformation and unifies graph-native and graph-transformable agent methods under a common language.This structural lens organizes existing self-evolving-agent work around changing graphs and topologies.
  • Conclusion: Existing self-evolving-agent mechanisms are organized into four graph-transformation patterns, including memory editing and workflow optimization.The passage identifies these patterns as a concrete organization of prior work based on dynamic graphs and topologies.
  • Conclusion: The mapping from dynamic graph learning to self-evolving agents is primarily conceptual, offering research insights and possible infrastructure designs without empirical evaluation.Empirical evaluation is explicitly left for future work.
Loading 2608.18104v1…