Abstract
Persistent knowledge-graph (KG) memories are becoming a practical substrate for graph-backed assistants: they extract entities, relations, timestamps, and provenance from one session and later retrieve k-hop neighborhoods to ground another response. This creates a privacy boundary that is neither standard model memorization nor ordinary document-RAG leakage: the sensitive object is a live, multi-user, provenance-tagged graph. We introduce GraphMemShield, a reproducible audit and mitigation framework for this setting. It packages a set of scoped retrieval-risk invariants over a provenance-tagged graph history that bound cross-session exposure for provenance-aware guarded retrieval under adaptive multi-hop querying, and a separate scoped local-DP statement for a fixed-universe randomized-response mechanism with explicit composition and group-privacy accounting. The contribution is the explicit scope and the empirical audit, not a new privacy mechanism. The framework implements attacks for cross-session edge exposure, adaptive probing (including a degree-prioritized and an LLM-guided adaptive attacker), session linkage, temporal inference, and lexical plus semantic response leakage with a scorer ablation. We evaluate defenses based on provenance-aware bounded sharing, write-time randomized admission, and fixed-universe randomized response. Across five workloads — synthetic, Docker-backed, enterprise/health/finance, MultiWOZ 2.1, and Enron-style communication graphs — unguarded retrieval exposes victim-owned edges and sensitive response content. On the 2,304-edge enterprise benchmark, multi-hop retrieval increases unguarded leakage from 9.2±0.6 to 11.7±0.5 victim edges (10 seeds, 95% CI), and a full backend–retrieval–response pipeline leaks 11.8±0.6 edges and 7.9±0.7 sensitive terms without a guard. Bounded sharing makes the privacy–utility tradeoff explicit: increasing the per-pair budget from 0 to 10 raises non-sensitive utility retention from 0.0 to 0.614 while keeping unique victim leakage capped at three edges, and raises a downstream graph-QA accuracy from 0.00 to 0.71 while strict isolation gives 0.00. We further show that this guarantee depends on correct sensitivity provenance, propose three mitigation recipes (sticky labels, neighbor-shadow labeling, and majority-of-raters voting) that restore most of the bound under 50% corruption, and separate a non-DP edge-suppression heuristic from a fixed-universe randomized-response mechanism with explicit composition and full-graph-release scope accounting.