Overview
Production Readiness
0.4
Novelty Score
0.6
Cost Impact Score
0.6
Citation Count
0
Why It Matters For Business
Graph-structured retrieval can leak reusable entity-relation graphs with surprisingly few queries; operators should treat structured retrieval as a privacy risk and add monitoring, response filtering, or query limits.
Summary TLDR
This paper shows an attacker can reconstruct large parts of a GraphRAG system's hidden knowledge graph using a small number of queries. The authors introduce AGEA: an agentic loop that alternates novelty-driven exploration and targeted exploitation, keeps a graph memory, and filters LLM-extracted entities/edges before committing them. On two GraphRAG systems and several domains, AGEA recovers much more graph structure per query than prior attacks (e.g., up to ≈90% node/edge recovery on medium graphs with 1,000 queries), while keeping high precision. The attack relies on eliciting structured outputs and LLM-based filtering, and it weakens as graphs grow much larger or when victims restrict or
Problem Statement
Can a black-box attacker, limited to a fixed number of queries, reconstruct the internal entity–relation graph used by GraphRAG systems? The difficulty is noisy, mixed-format responses, no direct graph access, and a strict query budget that forces a trade-off between exploring new areas and exploiting known hubs.
Main Contribution
Formalize budgeted, black-box graph-level extraction attacks against GraphRAG systems.
Propose AGEA: an agentic, novelty-guided explore/exploit attacker with graph memory and a two-stage (regex discovery + LLM filtering) extraction pipeline.
Extensive evaluation on Medical, Agriculture, and Novel corpora across Microsoft GraphRAG and LightRAG showing large gains in node/edge recovery under fixed query budgets.
Key Findings
AGEA recovers a very large fraction of nodes and edges under 1,000 queries on medium graphs.
On LightRAG AGEA achieves even higher coverage and precision.
Two-stage extraction (fast regex discovery + LLM filtering) preserves precision while enabling novelty scoring.
Adaptive explore/exploit query policy matters: pure exploration or pure exploitation performs worse.
Attack effectiveness drops on very large, diverse graphs under fixed budgets.
Results
Leak(N)
Leak(E)
Prec(N)/Prec(E)
Leak(N)
Who Should Care
What To Try In 7 Days
Run a red-team extraction using a novelty-driven agent to measure your system's structured leakage under realistic query budgets.
Enable structured-output controls: block or sanitize machine-readable entity/relation lists in LLM responses.
Add retrieval-time checks or rate limits on repeated hub-focused queries and log novelty-like metrics to detect agentic probing.
Agent Features
Memory
- Graph memory (filtered and raw)
- Query memory (recent queries/responses)
Planning
- LoRA
- Degree-based hub selection for exploitation
Tool Use
- LLM as query generator
- LLM as graph filter agent
- Regex parser for fast discovery
Frameworks
- Closed-loop agent that alternates query generation and filtering
Is Agentic
true
Architectures
- LLM-based query generator
- Two-stage extraction pipeline (discovery + LLM filter)
- External graph memory modules
Optimization Features
Token Efficiency
- Regex discovery to avoid extra LLM calls
Reproducibility
Data Available
Open Source Status
- partial
Risks & Boundaries
Limitations
- Relies on the victim producing machine-structured outputs; output-restriction policies can blunt the attack.
- Does not model active deployment defenses like query rewriting, monitoring, or rate-limiting.
- Effectiveness declines on very large, diverse graphs when query budget is small.
When Not To Use
- If the target system enforces strict output formatting or forbids structured extraction commands.
- When deployment includes effective traversal-aware monitoring or strict rate limits.
- For extremely large graphs with tiny budgets where only partial, noisy leakage is acceptable.
Failure Modes
- Hallucinated hubs: LLM filter may miss widespread spurious connections if prompts are too lenient.
- Backbone sensitivity: different LLMs produce large precision differences for relations.
- Elicitation blocked: victim policies that refuse structured extraction break the discovery regex step.
Core Entities
Models
- GPT-4o-mini
- DeepSeek-V3.1
- text-embedding-3-large
Metrics
- Leakage Rate (nodes)
- Leakage Rate (edges)
- Precision (nodes)
- Precision (edges)
- Degree-weighted leakage
- PageRank-weighted leakage
Datasets
- Medical (NCCN guidelines)
- Agriculture (Reclaiming Our Food)
- Novel (20 Project Gutenberg books)
- Novel 9 (subgraph)
- Novel 13 (subgraph)
Benchmarks
- GraphRAG-Bench