Graphs Don't Stay Secret: Practical Subgraph Reconstruction Attacks on Defended Graph RAG

Technical Summary: Graphs Don't Stay Secret: Practical Subgraph Reconstruction Attacks on Defended Graph RAG

Problem Statement
Graph-based Retrieval-Augmented Generation (Graph RAG) enhances Large Language Model (LLM) reasoning by retrieving structured subgraphs from knowledge bases (KBs) rather than unstructured text chunks. While this improves global and compositional reasoning, it introduces a critical, under-studied threat: adversaries can reconstruct these structured subgraphs to exfiltrate proprietary knowledge assets (e.g., organizational ontologies, schema) and sensitive private data (e.g., employee roles, patient diagnoses).

Existing data extraction attacks against RAG systems largely fail in defended Graph RAG deployments. Prior methods rely on "repeat and list" prompting or jailbreak techniques that explicitly request context disclosure. In Graph RAG, these approaches trigger safety refusals or induce the LLM to paraphrase/summarize the retrieved content. This paraphrasing corrupts the precise entity-relation triples required for graph reconstruction, causing prior attacks to fail at recovering relation types and maintaining instance-level fidelity. The paper identifies three specific failure modes in defended settings: (1) explicit exfiltration intent triggers refusals; (2) safety-induced paraphrasing breaks relation type accuracy; and (3) fixed query templates quickly saturate, yielding diminishing returns.

Methodology: GRASP
To address these challenges, the authors propose GRASP (Graph RAG Reconstruction Attack for Subgraph Profiling), a closed-box, multi-turn attack designed to reconstruct a targeted one-hop subgraph from a defended Graph RAG system. GRASP operates without access to the internal retriever, embedding model, or KB schema, relying solely on the standard API.

GRASP is built on three core design principles derived from the failure analysis of prior attacks:

1. Task Reframing (Intent Evasion): Instead of explicitly asking to "dump" or "list" the graph, GRASP reframes the extraction as a legitimate, constrained relation-processing task. The attack prompts the LLM to act as a specialized assistant extracting relations from retrieved context tables, thereby bypassing safety filters that block overt data exfiltration.
2. Instance-Grounded Extraction (Fidelity): To counter safety-induced paraphrasing and hallucinations, GRASP enforces a strict output format requiring relation quadruples: (ID, SRC_ENTITY, REL_TYPE, DST_ENTITY). Crucially, it introduces a per-record ID for each relation instance. This ID acts as a delimiter, forcing the model to trace each extracted relation back to a specific record in the retrieved context. This mechanism significantly reduces the mixing of entities and relations (hallucinations) and preserves the exact lexical form of relation types.
3. Adaptive Discovery (Diversity): To overcome retrieval saturation and query budgets, GRASP employs a Discovery-Aware Prompt Scheduler. This scheduler manages a set of goal-driven diversity templates:
   • Context-frame drift: Shifts retrieval focus using domain-specific anchors to uncover new relations.
   • Type expand: Exploits known relation types to find missed instances.
   • Type explore: Targets unseen relation types to expand structural coverage.
   • Residual extract: Performs a conservative sweep for remaining high-confidence relations.
     The scheduler adaptively selects templates based on the momentum of new discoveries (using Exponential Moving Averages) and a Good-Turing novelty estimate to stop when marginal gains are negligible.

Key Contributions

• Failure Analysis: The paper provides a systematic analysis of why prior RAG extraction attacks fail against Graph RAG, identifying that explicit intent triggers refusals and paraphrasing destroys relation fidelity.
• GRASP Attack: Introduction of a novel attack that achieves high-fidelity subgraph reconstruction in defended settings by reframing the task, enforcing instance grounding, and using adaptive scheduling.
• Empirical Validation: Demonstration that GRASP achieves up to 82.9% F1 (RType) in reconstructing typed relations across two real-world datasets (Enron emails, HealthCareMagic dialogues) and four safety-aligned LLMs (GPT-4o-mini, GPT-5-mini, Claude Haiku 4.5, Qwen3), whereas prior baselines often fail to recover relation types entirely.
• Defense Evaluation: A systematic evaluation of existing defenses (prompt-based, decoding-time, runtime monitoring) and the proposal of two lightweight context-construction defenses: ID Alignment (collapsing instance IDs to induce mixing) and Decoy (injecting misleading endpoint columns).

Results

• Attack Performance: GRASP significantly outperforms baselines. While baselines like "repeat context" or jailbreak prompts achieve near-zero F1 for typed relations (RType) under safe prompts, GRASP maintains high precision and recall. For instance, on the Enron dataset with GPT-4o-mini, GRASP achieved 65.6% F1 (RType), compared to <1% for most baselines.
• Robustness: The attack transfers effectively across different Graph RAG frameworks (GraphRAG, LightRAG, nano-GraphRAG) and remains effective even with strict query budgets (as low as 3 queries) and unknown target entities (via a two-stage discovery approach).
• Defense Efficacy:
  • Baseline Defenses: Standard safe prompts, summarization defenses, and even runtime intent screening (e.g., Bedrock Guardrails) reduce but do not eliminate the threat. For example, Bedrock blocked 61.3% of queries but left 47.1% F1 reconstruction capability.
  • Proposed Defenses: The authors' ID Alignment and Decoy defenses are highly effective. When combined with a safe prompt, they reduce GRASP's F1 to the mid-teens (e.g., 14.8% for Qwen3) while preserving benign QA utility (measured by Rouge-L F1). However, the paper notes that residual extraction risk persists even under layered defenses.

Significance and Claims
The paper claims that targeted subgraph reconstruction is a concrete confidentiality risk in Graph RAG systems, even when protected by standard safety prompts. It argues that the "structured leakage" of Graph RAG is distinct from text leakage, as it exposes organization-specific ontologies and relational assets that are highly valuable for intellectual property theft and privacy inference.

The authors modestly claim that while their proposed defenses (ID Alignment and Decoy) substantially reduce reconstruction fidelity, they do not eliminate the threat entirely. The paper concludes that current intent-based blocking and runtime monitoring are insufficient to prevent Graph RAG extraction, necessitating threat-specific safeguards that disrupt the structural integrity of the retrieved context itself. The work serves as a call to action for the development of stronger, Graph RAG-specific mitigation strategies beyond simple prompt engineering.