Abstract
Graph-backed assistants increasingly write user utterances into a provenance-tagged knowledge-graph memory and later retrieve k-hop neighborhoods to ground responses. Because the retrieval surface is multi-user and append-only, an edge written by one session can enter the context of another. This boundary is neither model memorization nor document-RAG leakage; it is a retrieval-control problem that existing benchmarks do not isolate. We introduce GraphMemShield , a benchmark and audit suite for cross-session leakage in dynamic KG memories, packaging a JSONL trace schema, gray- and black-box leakage probes, a response-leakage scorer, and four policy baselines: global retrieval, owner-only isolation, label filtering, and bounded provenance-aware sharing. Two structural results frame the suite. First, we prove that any policy with cross-session QA accuracy a must expose at least ⌈ a N cs /ρ⌉ victim-owned determining edges; a retrieval-time budget guard attains this bound to within 1.06× on a structured workload (the enterprise bank). Second, we apply the standard private-selection lower bound to show that post-retrieval answer-level ε-DP cannot match the deterministic guard’s utility in the small-margin regime our graph-memory workloads exhibit empirically: our DP-GraphQA mechanism lands at 0.15–0.18 accuracy at usable ε on these workloads because measured margins are only 0.54–1.24. The operational rule is therefore to bound exposure before unsafe cross-session edges enter the context, and add post-retrieval DP only when the application can pay the margin cost. Keywords: Knowledge-graph memory, Cross-session leakage, Provenance, Graph-augmented retrieval, Privacy auditing, Session linkage, Bounded sharing