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

Task- and answer-centered evaluation can leave evolving agent-state correctness unobserved, while the coupling between evolving agent states and graph topology remains underexplored. This survey frames agent evolution as dynamic graph transformation, synthesizes existing methods into four patterns, maps nine dynamic-graph-learning subfields to agent capabilities, and discusses graph-aware evaluation and governance.

  • Problem

    Self-evolving-agent evaluation remains largely task- or answer-centered, leaving activated support graphs and evolving-state correctness unobserved.

    Source: §I · p. 2, E. Open Challenges · p. 15

  • Method

    The survey represents memories, tools, skills, workflows, and inter-agent relations as typed graph structures updated through schema-constrained rewrites.

    Source: §I · pp. 1–2

  • Results

    The synthesis identifies four graph-transformation patterns, maps nine dynamic-graph-learning subfields to agent capabilities, and extends the structural view to graph-aware evaluation and governance.

    Source: §I · p. 2

  • Takeaways & Limitations

    Dynamic graph methods are positioned as reusable infrastructure for controllable agent evolution.

    Source: §VI · p. 16

    DELSUCC requires controlled randomness and complete provenance/replay logs, and measures empirical behavioral equivalence rather than certified distributional unlearning.

    Source: C. Privacy and Deletion in Evolving… · p. 14

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

This survey frames self-evolving agents as dynamic graph transformations, connecting evolving agent state and topology. It organizes existing methods, links dynamic graph learning to agent capabilities, and extends the structural perspective to evaluation and governance.

Introduction

  • Long-running agents evolve memories, capabilities, workflows, and relations, while existing graph-agent and self-evolving-agent surveys leave their structural coupling and changing topology underexplored [7],,, [10].Agent states change through interaction, feedback, and environmental drift; persistent updates can propagate through dependencies over time.Source: §I · p. 1
  • The survey formalizes agent evolution as dynamic graph transformation, encoding states as typed nodes, edges, and subgraphs updated through dependency-aware, schema-constrained rewrites.Temporal attributes track evolving evidence, while rewrites model activation, propagation, and rollback.Source: §I · pp. 1–2
  • It organizes existing self-evolving-agent works into four graph-transformation patterns: node/feature evolution, edge/topology evolution, subgraph activation, and cross-component co-evolution.The survey covers 46 dynamic-graph-based agent works under this taxonomy.Source: §I · p. 2
  • The survey maps nine dynamic-graph-learning families to agent capabilities, including prediction, activation, generation, diagnosis, rollback, and governance.It positions dynamic graph learning as reusable infrastructure for designing, adapting, diagnosing, and governing self-evolving agents.Source: §I · p. 2
  • It discusses five graph-aware evaluation and governance protocols: leakage-free temporal evaluation, privacy and deletion checking, safety monitoring, rollback analysis, and audit.These complement task- or answer-centered evaluation, which can miss stale-memory reliance, unsafe propagation, and persistent untraceable changes.Source: §I · p. 2
  • The survey outlines six open challenges for reliable, auditable, and controllable self-evolving agents under its dynamic-graph framing.Its scope is the dynamic-graph perspective on self-evolving agents, rather than broad reviews of agent systems or general dynamic graph learning.Source: §I · pp. 2–3

II. PRELIMINARIES · III. AGENT EVOLUTION AS DYNAMIC GRAPH TRANSFORMATION · A. Node and Feature Evolution

The paper models self-evolving agent state as a dynamic graph transformed by schema-constrained rewrites, then organizes agent evolution into four graph-transformation patterns. Node and feature evolution treats persistent changes to memories, tools, skills, and agent states as typed node updates.

II. PRELIMINARIES

  • The preliminaries model agent state over time as a graph of typed memories, tools, skills, and agents, with relations and attributes that condition future actions.The graph may represent continuous-time, discrete-time, heterogeneous, or text-attributed data; activated support subgraphs inform action selection without necessarily changing state.Source: §II · p. 3
  • Typed rewrites cover node or edge insertion and deletion, feature updates, and dependency cascades; DPO conditions reject inadmissible proposals and support audit and rollback.Accepted rewrites are logged with matches and affected subgraphs, while subgraph activation is read-only; temporal property graphs and DPO rule engines offer implementation routes.Source: §II · p. 3

III. AGENT EVOLUTION AS DYNAMIC GRAPH TRANSFORMATION

  • The survey groups 46 representative methods into node/feature evolution, edge/topology evolution, subgraph activation, and cross-component co-evolution.Fig. 2 groups the methods into four branches, and Table I projects them into rewrite patterns.Source: §III · p. 3

A. Node and Feature Evolution

  • Node and feature evolution unifies localized memory, tool, skill, and agent-state changes as typed node transformations, including insertion, revision, merging, and removal.Its DPO-style schemas describe insertion, deletion, feature update, and merge; merging archives source nodes rather than identifying them, and deletion must address incident edges.Source: A. Node and Feature Evolution · pp. 3–4
  • Memory evolution maps new observations to insertion, consolidation to merging, and correction, decay, or invalidation to feature updates or deletion.Relation-centric memory graphs link memories to entities, events, tasks, and provenance, as in Zep [33]; consolidation-centric systems organize histories into time-aware levels, as in TiMem [32].Source: A. Node and Feature Evolution · p. 4
  • Skill acquisition and revision map to node insertion, feature updates, or merging, while skill provenance and dependencies enable targeted revalidation.The survey distinguishes graph-structured skill retrieval and maintenance [61], [62] from experience-driven skill acquisition, –.Source: A. Node and Feature Evolution · p. 4
  • Tool profiles and usage records can be modeled as evolving nodes, while agent participation and collaboration protocols update agent attributes and relations.SEARL [63] updates tool-graph memory from execution feedback; DyLAN adapts active agents and communication relations during collaboration.Source: A. Node and Feature Evolution · pp. 4–5
  • A key gap is estimating which downstream components need revalidation after a local update without requiring global revalidation.The proposed direction is to model updates as time-stamped events and propagate their influence through dependency and provenance structures.Source: A. Node and Feature Evolution · p. 5

B. Edge and Topology Evolution

This section treats changes to workflow, communication, and skill–tool relations as dynamic graph transformations: topology evolves through edits to execution, communication, or dependency edges, making affected components and consistency checks explicit.

DPO Rule Schemas for A.2

  • LINK, UNLINK, REWIRE, and EDGEFEATUREUPDATE represent edge insertion, deletion, redirection, and attribute revision, with downstream references kept consistent.These schemas make structural changes explicit and support dependency checks and targeted revalidation after topology updates.Source: B. Edge and Topology Evolution · pp. 5–6

Workflow Optimization

  • Workflow optimization searches agent workflows and architectures, –[69],, or constructs task-dependent execution graphs, [66].DynTaskMAS uses a dynamic task graph to decompose tasks, preserve dependencies, and enable asynchronous parallel execution.Source: B. Edge and Topology Evolution · p. 5

Multi-agent Communication

  • Multi-agent communication methods construct, route, or adapt task-context-, role-, or robustness-dependent structures, –, –[74],,, [79]–, while pruning or sparsifying redundant, costly, unsafe, or low-utility agents or links,,,, [78].Source: B. Edge and Topology Evolution · p. 5

Skill–Tool Dependencies

  • Skill–tool dependency methods maintain prerequisite, compatibility, invocation, and ownership relations among skills, tools, and parent agents [61], [64], [111].SkillOps [61] maintains a hierarchical skill ecosystem graph, while NaviAgent [64] updates toolchain selection from execution feedback; dependency changes can trigger targeted revalidation.Source: B. Edge and Topology Evolution · p. 6

Open Gaps

  • Existing methods rarely validate whether edited edges are redundant, safety-critical, or necessary, risking undetected breaks to dependent skills, workflows, provenance, or coordination.The open challenge is impact-aware, reversible maintenance using temporal edit events, propagated effects, and versioned edge histories for monitoring and rollback.Source: B. Edge and Topology Evolution · p. 6

C. Subgraph Activation

Subgraph activation selects a task-specific support subgraph from persistent agent state without changing that state. This framing makes transient evidence and execution choices inspectable and highlights the need to evaluate activation decisions, not only final task success.

C. Subgraph Activation

  • Subgraph activation selects a relevance-conditioned support subgraph for a task as a read-only operation, not a persistent graph rewrite.The task and activation policy determine the selected match; auditability lets evidence use, tool routing, and team selection be inspected without mistaking them for persistent learning.Source: C. Subgraph Activation · p. 6
  • Activation policies score task-relevant memories, tools, skills, or agents, then expand selected anchors into a limited task-time context [15], [82].The activated view changes while the persistent graph remains unchanged; retrieval, workflow-fragment selection, and communication-neighborhood activation can share this interface.Source: C. Subgraph Activation · p. 6
  • Memory activation treats graph-based evidence expansion [33], [82] and memory-store retrieval [3],, as transient evidence selection, not committed memory updates.ToG-3 [82] iteratively refines a query-specific support graph through multi-agent context retrieval and expansion; recording selected evidence as Gact(t) makes missing, stale, or overly broad retrieval diagnosable.Source: C. Subgraph Activation · p. 6
  • Execution activation selects task-specific agents or communication structures, [15],, or executable skills, modules, and workflow steps,,.ARG-Designer provides a query-conditioned collaboration graph, while DyFlow illustrates workflow-oriented activation; writing selected structure back as persistent state instead belongs to A.1, A.2, or A.4.Source: C. Subgraph Activation · pp. 6–7
  • Benchmarks,, – mostly measure final task success, rarely whether agents activated the right memories, tools, skills, agents, or workflow fragments.Suggested graph-based measures include support-subgraph precision, required-evidence coverage, minimality, and temporal validity; dynamic graph methods, may provide signals, but activation-specific metrics remain a challenge.Source: C. Subgraph Activation · p. 7

D. Cross-Component Co-Evolution

This section models cross-component agent evolution as typed cascades of graph rewrites, linking local triggers to affected components and revalidation or rollback targets. It emphasizes propagation control and the open problem of estimating downstream scope without unnecessary repair.

Cascade Rewrite Schema for A.4

  • A.4 models cross-component evolution as timestamped, typed cascades of dependent DPO rewrites, linking triggers to affected subgraphs and revalidation or rollback targets.The cascade spans at least two component types, and at least one later rewrite depends on or conflicts with an earlier rewrite.Source: D. Cross-Component Co-Evolution · p. 7

Cross-Component Cascade Rewrites

  • Task feedback can propagate into reusable skills or expertise [31], while capability signals can co-adapt roles and collaboration topology [85]–; TacoMAS [86] pairs fast expertise updates with slower topology edits.Feedback-driven methods [128], can also be mapped as cascades when their artifacts are materialized and reused to update dependent components.Source: D. Cross-Component Co-Evolution · p. 7

Safety-Triggered Propagation

  • Safety anomalies, including unsafe tool use or API drift, can trigger downstream revalidation or rollback; GUARDIAN detects hallucination and error propagation in temporal multi-agent graphs.Dependency or provenance edges can identify the affected subgraph for localized repair rather than global retraining or broad manual inspection.Source: D. Cross-Component Co-Evolution · pp. 7–8

Open Gaps

  • Methods rarely expose the full cascade trace, leaving affected-scope estimation open: agents must check dependent skills, workflows, and teams enough to prevent silent regressions without unnecessary global repair, [41].A changed tool contract may require tracing downstream through skills that call it, workflows that contain those skills, and teams that depend on those workflows.Source: D. Cross-Component Co-Evolution · p. 8

E. Putting the Four Rewrite Branches Together · IV. DYNAMIC GRAPH LEARNING AS AGENT INFRASTRUCTURE · A. Dynamic Graph Representation Learning

The paper frames agent evolution as graph rewriting across persistent state updates, relation changes, temporary support activation, and cross-component cascades. It then positions dynamic graph learning as reusable infrastructure, with time-aware representations supporting agent maintenance while persistent changes remain subject to rewrite validation.

E. Putting the Four Rewrite Branches Together

  • The four rewrite branches cover persistent component-state updates, relation rewiring, temporary task-time support activation, and cascades across component types.They differ by trigger, operator, affected scope, and persistence or propagation pattern; a single agent system may span multiple branches.Source: E. Putting the Four Rewrite Branches… · p. 8
  • Together, A.1–A.4 provide a common language for comparing methods and locating where validation, rollback, and governance should apply.Table I maps representative mechanisms to their triggers, rewrite operators, affected scopes, and persistence levels.Source: E. Putting the Four Rewrite Branches… · p. 8

IV. DYNAMIC GRAPH LEARNING AS AGENT INFRASTRUCTURE

  • The infrastructure mapping organizes dynamic graph learning into nine families, relating each to agent capabilities, required adaptations, and naive failure modes.The families are dynamic graph representation, text-attributed graph representation, graph generation, temporal continual learning, out-of-distribution generalization, temporal knowledge graph reasoning, anomaly detection, unlearning, and temporal GNN explanation.Source: §IV · p. 8

A. Dynamic Graph Representation Learning

  • Time-aware graph representations can address stale memories, context-sensitive skill reliability, and invalid workflow edges through validity, reliability, risk, and cascade-alert tasks.The subsection groups representation methods by temporal granularity: continuous-time dynamic graphs (CTDG) and discrete-time dynamic graphs (DTDG).Source: A. Dynamic Graph Representation Learning · p. 8
  • CTDG encoders model irregular events for online prediction, whereas DTDG encoders use graph snapshots for periodic diagnosis and maintenance,, –,,,,, –.Agent events may include memory writes, tool calls, workflow edits, and messages; snapshot maintenance can operate at session, round, or deployment level.Source: A. Dynamic Graph Representation Learning · p. 8
  • For agent graphs, temporal encoders turn typed events into bounded activation or maintenance signals; persistent graph changes still require rewrite validation.CTDG outputs can guide memory support or tool routing, while DTDG outputs can support drift tracking and workflow comparison.Source: A. Dynamic Graph Representation Learning · p. 9
  • A GitHub maintenance example uses typed execution traces to score candidate skill-tool or workflow edges for routing, without directly committing new dependencies.The example proposes candidate-edge ranking and post-drift recovery for evaluation; persistent dependency updates still require rewrite validation.Source: A. Dynamic Graph Representation Learning · p. 9

B. Dynamic Text-Attributed Graph Representation

Dynamic Text-Attributed Graphs treat text as part of evolving agent state, coupling semantic content with temporal events and graph structure. For agent graphs, selective re-encoding can refresh affected representations while preserving unrelated embeddings.

B. Dynamic Text-Attributed Graph Representation

  • DyTAGs represent evolving memories, tools, skills, and agents with textual attributes whose changes can alter retrieval, activation, and update decisions.Memory text may include observations, policies, and summaries; tool, skill, and agent text may include API descriptions, code, contracts, or role specifications.Source: B. Dynamic Text-Attributed Graph… · p. 9
  • MoMent aligns textual, temporal, and structural modalities into node representations using modality-specific encoders, a learnable fusion function, and an alignment objective.For agent graphs, these modalities correspond to node text, temporal update history, and structural connections.Source: B. Dynamic Text-Attributed Graph… · pp. 9–10
  • Selective re-encoding refreshes affected node text representations and incident edge features after rewrites, while leaving unrelated text embeddings untouched.Changes to semantic content, temporal validity, or downstream dependencies can trigger refreshes; DyTAG modules provide bounded retrieval, activation, and edge-validity signals.Source: B. Dynamic Text-Attributed Graph… · p. 10
  • In the branch-change example, a DyTAG encoder ranks stale and current branch memories using text, pre-decision metadata events, and graph connections to select the active memory for the PR workflow.Persistent memory correction still requires a validated rewrite; proposed evaluation includes stale-memory activation rate and wrong-base PR calls, using only metadata or PR outcomes observed before the decision time.Source: B. Dynamic Text-Attributed Graph… · p. 10

C. Dynamic Graph Generation · D. Temporal Graph Continual Learning

Dynamic graph generation proposes schema-valid workflow or topology changes for validation before commitment, while temporal graph continual learning preserves important agent capabilities as new events arrive.

C. Dynamic Graph Generation

  • Generation methods cover temporal structures and text-attributed graphs, proposing candidate subgraphs or rewrite traces that runtime validation must approve before persistent state changes.They support workflow and topology synthesis, counterfactual repair planning, and simulation of future evolution traces.Source: C. Dynamic Graph Generation · pp. 10–11
  • TIGGER can be adapted to generate rewrite traces that satisfy tool-signature and provenance constraints, favor likely and useful changes, and avoid unnecessary rewrites.Selected traces remain proposals and require explicit rewrite validation before activation, repair, or commitment.Source: C. Dynamic Graph Generation · pp. 10–11
  • A GitHub maintenance example proposes adding repository metadata before a pull-request call, then checks required arguments, branch constraints, and provenance.Suggested evaluation measures include valid-proposal rate, PR completion, and invalid-tool-call reduction.Source: C. Dynamic Graph Generation · p. 11

D. Temporal Graph Continual Learning

  • Temporal graph continual learning addresses stability and plasticity through replay-based or parameter-based methods, retaining dependency subgraphs whose loss could break downstream behavior.Examples include rare skills, user-specific memories, prerequisite tools, and validation traces.Source: D. Temporal Graph Continual Learning · p. 11
  • LTF replays selected historical agent subgraphs while adapting to new temporal events, with dependency-aware retention weighting rare skills, prerequisite tools, user-specific memories, and safety-critical provenance.The result is a more stable encoder or replay policy for activation and retrieval, not a direct rewrite of agent state.Source: D. Temporal Graph Continual Learning · p. 11
  • For a rare release-branch skill, replaying its supporting memories, CI requirements, and hotfix traces aims to preserve activation while the agent learns new tools and repository patterns.Suggested evaluation includes rare-skill Recall@k, release-branch PR recovery, and routine-task performance across epochs.Source: D. Temporal Graph Continual Learning · p. 11

E. Out-of-Distribution Generalization on Dynamic Graphs · F. Temporal Knowledge Graph Reasoning

The sections frame dynamic-graph OOD robustness as maintaining valid agent-state choices under structural and temporal shifts, and temporal knowledge graph reasoning as retrieving time-valid evidence paths for agent decisions.

E. Out-of-Distribution Generalization on Dynamic Graphs

  • Dynamic-graph OOD methods use spatio-temporal invariance, or environment-aware modeling, to address shifts in agent graphs and deployment conditions.Relevant environments can include deployment epochs, tool versions, organizations, user cohorts, and task families.Source: E. Out-of-Distribution Generalization… · p. 11
  • Environment-aware learning reduces worst-case risk across deployment environments and produces robustness-aware scores for activation, routing, or update proposals under shift.These scores can help select tools that remain valid after tool-version changes, but persistent graph changes still require validation.Source: E. Out-of-Distribution Generalization… · pp. 11–12
  • Under a held-out organization’s new policy, a maintenance agent should replace an invalid open_pr route with required policy, CI, and code-owner checks.Evaluation can measure policy-compliant routing, rejected-PR reduction, and PR completion, with training and testing split by organization or policy regime.Source: E. Out-of-Distribution Generalization… · p. 12

F. Temporal Knowledge Graph Reasoning

  • Temporal knowledge graph methods include path-based reasoning, neural temporal reasoning, –, and LLM-assisted reasoning [188]– for timestamped agent-state evidence.Such evidence can include memories, corrections, tool outcomes, and workflow revisions.Source: F. Temporal Knowledge Graph Reasoning · p. 12
  • xERTE can adapt to agent graphs by activating time-valid evidence chains from graph state and interaction history rather than retrieving isolated top-ranked memories.The resulting support subgraph can ground memory QA, dependency tracing, or delayed-failure diagnosis while reducing stale evidence and temporal leakage.Source: F. Temporal Knowledge Graph Reasoning · p. 12
  • For a hotfix branch query, temporal path reasoning links policy and release-series metadata to the valid branch release/1.x before the PR tool is called.Suggested evaluation measures temporal QA accuracy, path-level temporal validity, and evidence-path precision.Source: F. Temporal Knowledge Graph Reasoning · p. 12

G. Anomaly Detection on Dynamic Graphs · H. Dynamic Graph Unlearning · I. Explanation for Temporal GNNs

The section frames dynamic graph learning as support for detecting unsafe agent behavior, removing deleted influence, and explaining agent decisions. Its methods provide evidence and signals, while validated, localized, auditable graph transformations govern persistent state changes.

G. Anomaly Detection on Dynamic Graphs

  • Dynamic graph anomaly detection can flag abnormal agent traces as early warnings for unsafe rewrites, prompt-injection propagation, tool misuse, and multi-agent collusion.Detectors may be supervised, semi-supervised, or unsupervised/self-supervised; labeled deployments can train incident-aware detectors, while open-ended agents need self-supervised monitoring.Source: G. Anomaly Detection on Dynamic Graphs · p. 12
  • TADDY and SLADE can be adapted to score rewrites by type, timing, task phase, dependency context, and provenance, then alert, quarantine, or request review.Calibration by rewrite type and task phase helps avoid mistaking benign bursts such as memory consolidation for unsafe escalation.Source: G. Anomaly Detection on Dynamic Graphs · p. 12

H. Dynamic Graph Unlearning

  • Dynamic graph unlearning must remove event influence, not just delete the original node or edge, and pair influence removal with versioned provenance rollback.Both deterministic descendants in G(t) and residual influence in learned parameters must be addressed.Source: H. Dynamic Graph Unlearning · p. 12
  • Parameter-level unlearning alone is insufficient: provenance-linked artifacts such as summaries and execution subgraphs must be regenerated, invalidated, or reverted, with validation to protect retained memories and shared skills.The output includes an unlearning scope and required model or representation updates.Source: H. Dynamic Graph Unlearning · p. 13

I. Explanation for Temporal GNNs

  • TGNNExplainer can support agent audits by returning a minimal, temporally ordered event history and local subgraph context that preserves a decision.Explanations may include affected subgraphs, provenance edges, retrieved memories, tool observations, or review traces, and can support rollback checks or be stored as audit artifacts.Source: §I · p. 13
  • DGL methods may guide activation, repair, deletion, and audit, but only validated, localized, auditable outputs should affect Gact(t) or be committed as typed rewrites in G(t).DGL should provide proposal and evidence signals; it should not directly mutate the persistent agent graph.Source: §I · p. 13

V. GRAPH-AWARE EVALUATION AND GOVERNANCE · A. Graph-Aware Evaluation

Graph-aware evaluation addresses the gap between end-task success and whether an agent relied on valid evolving state and made controlled graph updates. It proposes support-subgraph accuracy and rewrite locality, used as primary metrics when benchmarks expose the needed instrumentation and otherwise treated as diagnostics.

V. GRAPH-AWARE EVALUATION AND GOVERNANCE

  • End-task success can conceal stale or future evidence and harmful state updates, while existing benchmarks rarely test temporal validity, locality, reversibility, and auditability.The section frames graph-aware protocols as a complement to answer-level evaluation.Source: §V · p. 13

A. Graph-Aware Evaluation

  • Support-subgraph accuracy (M1) scores whether activated evidence is relevant and temporally valid by its best Dice overlap with an acceptable gold support subgraph.It applies to time-aware retrieval, planning, skill activation, and tool selection.Source: A. Graph-Aware Evaluation · p. 13
  • M1 favors compact evidence use, can penalize activating several valid chains, and can extend from node overlap to edge- or path-level overlap when relational support is labeled.This precision-oriented design helps distinguish valid reasoning from overly broad activation or reliance on leaked context.Source: A. Graph-Aware Evaluation · p. 13
  • Counterfactual rewrite locality (M2) tests whether a state update fixes target behavior while preserving unrelated behavior, complementing target-task success.Locality probes can check whether outputs such as tool choices remain equivalent under deterministic decoding and controlled tool execution.Source: A. Graph-Aware Evaluation · p. 14
  • High locality alone does not establish a successful repair, while low locality signals harmful side effects; edit size and touched-element counts are only diagnostics when probes are unavailable.Affected-set F1 is optional when gold affected elements are annotated.Source: A. Graph-Aware Evaluation · p. 14
  • Benchmarks need logged support subgraphs, rewrite traces, and locality probes to compare agents’ evidence use and graph side effects; without these, graph-level counts remain diagnostics.M1 additionally requires labels, and existing interactive traces need further instrumentation to derive graph-level records and before/after locality probes.Source: A. Graph-Aware Evaluation · p. 14

B. Leakage-Free Temporal Protocols · C. Privacy and Deletion in Evolving Agent Graphs · D. Safety, Rollback, and Audit

These sections define graph-aware governance protocols for leakage-free evaluation, deletion of private influence, and safety review through rollback and faithful audits. They complement task-success measures by examining whether an agent’s evolving state and decisions can be trusted.

B. Leakage-Free Temporal Protocols

  • Chronological cutoffs and decision-time state prevent future information from inflating self-evolution gains.Train on G(Ttrain) and O[0,Ttrain], then evaluate at time t using only G(t−) and O[0,t); rebuild split-specific indexes and summaries, sample negative tool edges from pre-t data, and calibrate reliability without future calls.Source: B. Leakage-Free Temporal Protocols · p. 14

C. Privacy and Deletion in Evolving Agent Graphs

  • Deletion evaluation must test whether revoked evidence still influences derived skills, workflows, routing policies, or post-deletion decisions, extending graph unlearning – to agent behavior.Deletion Success compares post-deletion decisions with counterfactual replay without the request and its deterministic descendants, using a task-specific equivalence predicate.Source: C. Privacy and Deletion in Evolving… · p. 14
  • DELSUCC measures empirical behavioral equivalence, not certified unlearning, and can be overly optimistic when provenance or replay is incomplete.It requires controlled randomness; when replay or provenance is incomplete, assess descendant invalidation logs, cached-embedding removal, privacy probes, and retained-task utility.Source: C. Privacy and Deletion in Evolving… · p. 14

D. Safety, Rollback, and Audit

  • Structural safety failures can arise from unsafe memories activating tools, dependency edges bypassing checks, or communication paths amplifying harmful instructions, which benchmarks –, do not trace to persistent evidence or rewrites.Graph-aware governance combines precommit admissibility checks, anomaly detection, and rollback through cascade analysis.Source: D. Safety, Rollback, and Audit · p. 14
  • Audit faithfulness tests explanations by masking cited evidence during replay while preserving executable graph structure, such as control-flow nodes.Masking is a replay-time operation, not a committed deletion.Source: D. Safety, Rollback, and Audit · p. 15
  • AUDITFAITH tests whether masking cited evidence changes an activation or rewrite decision, but should be paired with explanation size, support precision, or sufficiency checks.This necessity-side test builds on static and temporal GNN explanation,,; report a score only when replay and executable masking are supported, otherwise retain explanations as qualitative audit artifacts.Source: D. Safety, Rollback, and Audit · p. 15
  • A governance checklist covers valid support subgraphs, localized rewrites, leakage-free splits, deletion of derived influence, and faithful audits, distinguishing agents with identical task success.These criteria assess properties that answer-only metrics cannot reveal.Source: D. Safety, Rollback, and Audit · p. 15

E. Open Challenges · VI. CONCLUSION

The paper frames self-evolving agents as dynamic graph transformations and identifies six graph-level challenges for reliable, controllable evolution. It presents dynamic graph learning as conceptual infrastructure, while noting that its mapping has not been empirically evaluated.

E. Open Challenges

  • Graph-aware benchmarks should assess whether supporting agent states are temporally valid, locally updated, and auditable, not only whether outputs are correct.Relevant signals include activated support graphs, valid-time evidence, provenance paths, and rewrite histories.Source: E. Open Challenges · p. 15
  • Memory lifecycle management must trace inherited influence, detect staleness, and selectively maintain derived states under limited compute budgets [216].Routing should determine which memory subgraphs are worth retrieving, refreshing, or maintaining.Source: E. Open Challenges · p. 15
  • Tool-graph updates require provenance-aware downstream validation so changed tools and edges remain executable, authorized, and compatible with dependent workflows [50], [64], [61], [86].Policy or deployment shifts can invalidate a semantically plausible task–tool or skill–tool edge.Source: E. Open Challenges · p. 15
  • Skill usability must be evaluated structurally, because text-similar skills can be unusable when required tools or other dependencies are unavailable.Skill activation should check whether the surrounding dependency subgraph can support execution as libraries grow.Source: E. Open Challenges · p. 15
  • Workflow self-repair should predict and bound topology cascades across execution and collaboration, while preserving graph regions that should remain stable.Changes to workflow steps can affect roles, communication edges, dependency order, and tool or skill invocation.Source: E. Open Challenges · pp. 15–16
  • Multi-agent safety governance should trace harmful influence along propagation paths and block, review, or roll back the nodes and edges that carry it.Failures may be far removed from their source after influence spreads through communication edges or shared memories.Source: E. Open Challenges · p. 16

VI. CONCLUSION

  • The survey unifies graph-native and graph-transformable agent methods in four transformation patterns, connects them to nine dynamic graph learning families, and proposes five graph-aware evaluation and governance protocols.It also identifies six open challenges and frames these connections as a structural lens for governable agent evolution.Source: §VI · p. 16
  • The survey is not exhaustive, and its conceptual mapping of dynamic graph learning to agent evolution lacks empirical evaluation.Some graph-based and non-graph self-evolving-agent methods may be omitted or only briefly mentioned; empirical assessment is left for future work.Source: §VI · p. 16

Related papers

Loading 2608.18104v1…