Query-Efficient Agentic Graph Extraction Attacks on GraphRAG Systems

AI summary

Overview

Research area: AI security and privacy, specifically black-box data extraction attacks against Graph-based Retrieval-Augmented Generation (GraphRAG) systems.

Technical level: Intermediate. The paper assumes familiarity with retrieval-augmented generation, knowledge graphs, and basic adversarial querying, but the core mechanism (adaptive exploration/exploitation under a query budget) is explained concretely.

One-sentence scope: The paper formalizes a budget-constrained black-box attack in which an adversary reconstructs the hidden entity–relation graph of a GraphRAG system, and proposes AGEA (Agentic Graph Extraction Attack), which recovers up to 90% of entities and relationships while maintaining high precision.

What This Paper Is About

GraphRAG systems build knowledge graphs over document collections and use them for multi-hop reasoning, but prior work only showed that individual retrieved subgraphs could leak. This paper asks whether an adaptive adversary can systematically reconstruct a large, coherent portion of the hidden graph under a fixed query budget, using only black-box queries and responses. The authors propose AGEA, an agentic framework that plans queries to maximize newly recovered graph structure per query while filtering out hallucinated or spurious entities and relations.

Key Contributions

1. Problem formulation. The authors identify and formalize graph-level extraction attacks: an adversary with only black-box query access aims to reconstruct the underlying entity–relation graph of a GraphRAG system under a budgeted setting, with query efficiency as the central objective.
2. AGEA framework. They propose AGEA, described as the first agentic graph extraction attack framework for GraphRAG, combining novelty-guided exploration–exploitation, persistent graph and query memory modules, and a two-stage extraction pipeline (lightweight regex discovery plus LLM-based filtering).
3. Extensive empirical evaluation. Experiments across medical, agriculture, and literary (novel) datasets on Microsoft GraphRAG (M-GraphRAG) and LightRAG show AGEA consistently outperforming baselines under identical query budgets, recovering up to 90% of nodes and edges with high precision.
4. Ablations and scalability analysis. The paper isolates the contributions of the adaptive query strategy, the filtering module, the LLM backbone, and the universal extraction command, and tests scalability from 466 to 8,259 nodes.

Main Findings

• Best final leakage and precision at T = 1000. On M-GraphRAG's Medical graph, AGEA reaches Leak(N) 87.09, Leak(E) 80.16, Prec(N) 87.09, Prec(E) 61.18, versus the strongest baseline TGTB at 76.99 / 56.04 / 61.68 / 24.53. On M-GraphRAG's Agriculture graph, AGEA reaches 84.67 / 84.13 / 93.08 / 76.81, versus TGTB at 75.63 / 63.79 / 53.07 / 20.91.
• Strongest results on LightRAG. On LightRAG's Medical graph, AGEA reaches Leak(N) 96.42, Leak(E) 95.90, Prec(N) 98.34, Prec(E) 97.97, versus the best baseline PIDE at 83.92 / 73.93 / 76.09 / 74.93. On LightRAG's Agriculture graph, AGEA reaches 88.05 / 87.11 / 98.11 / 96.65, versus PIDE at 73.17 / 52.95 / 56.06 / 46.53.
• Edge recovery is the main bottleneck for prior attacks. The authors report that many baselines extract nodes but miss relations, and that AGEA substantially narrows this node–edge gap. AGEA's gains are described as largest on the Agriculture dataset, where baseline precision drops sharply.
• The strongest baseline varies by system. PIDE is strongest in LightRAG and TGTB in M-GraphRAG, which the authors interpret as evidence that different GraphRAG constructions expose different attack surfaces. Results are comparable only within each system because LightRAG and M-GraphRAG build different internal graphs from the same corpus.
• Adaptive querying matters most. Ablating to Explore-only on Medical (M-GraphRAG) drops to L(N) 23.77 / L(E) 10.67 / P(N) 67.60 / P(E) 32.05, a change of ΔL̄ = -66.41 and ΔP̄ = -24.31. Exploit-only reaches L(N) 83.98 / L(E) 75.40 but with P(N) 50.78 / P(E) 59.68 (ΔP̄ = -18.91), showing high leakage with degraded precision.
• Filtering trades a little leakage for precision. Removing the filter yields L(N) 88.53 / L(E) 80.80 (ΔL̄ = +1.04) but P(N) 70.58 / P(E) 59.83 (ΔP̄ = -8.93), indicating the filter prunes plausible but hallucinated entities.
• Backbone choice affects relation faithfulness. Qwen gives L(N) 83.14 / L(E) 75.45 / P(N) 73.44 / P(E) 23.19 (ΔP̄ = -25.82) and GPT-4o-mini gives 82.61 / 75.41 / 76.19 / 51.54 (ΔP̄ = -10.27), both below the DeepSeek default.
• Structured extraction commands help. On Medical with 250 queries, the proposed command reaches L(N) 62.34 / L(E) 46.62 / P(N) 92.87 / P(E) 69.21, versus command-v1 at 44.27 / 26.82 / 77.63 / 54.25 and command-v2 at 48.29 / 34.32 / 93.12 / 81.24. The paper reports average leakage improvements of +18.84 and +13.17 relative to v1 and v2, and notes that v2 attains higher average precision (ΔP̄ = +6.14) while extracting substantially less structure.
• Scalability degrades with graph size but remains non-trivial. Leakage stays high on small graphs (Novel 9 with 466 nodes and 603 edges, T = 400: M-GraphRAG 80.90 / 78.11 / 80.50 / 62.30; LightRAG 94.44 / 92.64 / 98.78 / 95.17) but drops on the full Novel graph of 20 books (8,259 nodes, 9,966 edges, T = 2,000: M-GraphRAG 60.71 / 52.56 / 71.40 / 57.33; LightRAG 71.36 / 68.70 / 98.23 / 97.44).
• Literary corpora are harder. The paper states that the Novel collections show higher entity/relationship diversity and weaker repetition than domain-specific corpora, increasing extraction difficulty under limited T.

Methodology in Plain English

The attacker never sees the GraphRAG system's internals, its graph, or the retriever, and never observes the retrieved subgraph directly. It only submits queries and reads the free-text responses.

AGEA runs a closed loop with four parts. A query generator writes the next query, conditioned on what has been extracted so far and on the history of past queries and responses. A graph extraction–filter module parses the response into candidate entities and relations. Two memory modules persist state: a graph memory holding the extracted graph, and a query memory holding recent interactions and mode-selection statistics.

The generator alternates between two modes. In explore mode it writes broad, diverse queries to surface new entity and relation types. In exploit mode it targets a specific entity, preferably a high-degree hub, to densify that neighborhood. Mode selection uses a novelty-aware epsilon-greedy policy: exploration happens with probability ε(t), which starts at 0.3 and decays by 0.98 per turn down to a floor of 0.05. Otherwise, the policy compares the average novelty over the last 5 turns against a threshold τ(t); if recent novelty is below the threshold, it explores to escape redundancy, and otherwise it exploits. The threshold scales with the decaying ε, so the policy becomes more exploitation-oriented over time.

The extraction pipeline has two stages. Stage A (Discovery) applies regex-based parsing to pull candidate entities and relations out of the response, using a "universal extraction command" appended to each query that asks the victim LLM to format its output structurally. This stage is deterministic and cheap, so novelty can be computed on every turn without extra LLM calls. Stage B (Filtering) uses an LLM graph filter agent to compare candidates against the existing filtered graph, merge duplicates, verify that entities and relations are explicitly supported by the response, and reject structurally implausible items such as sudden degree spikes that could indicate a "hallucinated hub." Only denoised candidates are committed to the filtered graph.

Every query is followed by the universal extraction command, and the query is sent to the victim GraphRAG system. The authors use GPT-4o-mini for query generation and extraction parsing, DeepSeek-V3.1 as the victim query model, and text-embedding-3-large for retrieval embeddings, accessed through Azure OpenAI APIs. Retrieval uses top_k=10 for both entities and relations, with local search in M-GraphRAG and hybrid search in LightRAG.

Evaluation compares against four black-box RAG extraction baselines under identical query budgets: TGTB and PIDE (fixed-query prompt injection) and CopyBreakRAG and IKEA (adaptive, multi-turn). Leakage is measured as the fraction of ground-truth nodes or edges recovered, and precision as the fraction of extracted nodes or edges that are correct.

Why This Matters

Impact on research. The paper shifts the privacy analysis of RAG from chunk- and document-level leakage to graph-level reconstruction, arguing that a reconstructed knowledge graph is a reusable, queryable artifact that exposes sensitive associations even without verbatim text disclosure. It also provides a query-efficiency framing that prior extraction attacks did not center.

Real-world applications affected:

• Healthcare knowledge systems. The Medical dataset covers clinical guidelines spanning diseases, treatments, and procedures; a leaked graph exposes relations among conditions and treatments.
• Agricultural advisory systems. The Agriculture dataset covers practices, crops, and technologies, where leaked relations could reveal proprietary agronomic knowledge.
• Enterprise and organizational knowledge bases. Reconstructed entity–relation graphs can surface organizational ties and communications structure, which the paper cites as examples of sensitive associations.
• Proprietary graph assets more broadly. The authors treat each constructed KG as a protected asset, relevant to any organization shipping a GraphRAG product over private corpora.
• Downstream inference and linkage. The paper notes that a recovered relational graph can enable linkage and targeted inference even without long verbatim disclosures.

Industry relevance. Any vendor deploying M-GraphRAG, LightRAG, or similar graph-augmented retrieval over proprietary documents inherits this attack surface. The finding that the strongest baseline differs between the two systems suggests that defenses and risk assessments need to be system-specific, and the paper explicitly points to retrieval-time filtering, response sanitization, and traversal-aware monitoring as candidate mitigations. The code is released at https://github.com/shuashua0608/AGEA.

Future Directions

1. Measure attribute leakage. The current study recovers structure (entities and relations), not the textual attributes and descriptions attached to them.
2. Test more GraphRAG variants and construction choices. The authors note that extraction behavior may vary with the victim's graph-construction pipeline, retrieval design, and corpus quality, and call for broader architecture and output-control coverage.
3. Develop and evaluate defenses. The paper proposes retrieval-time filtering, response sanitization, and traversal-aware monitoring, but explicitly does not model deployment-time defenses such as query monitoring, rate limiting, query rewriting, or adaptive detection of multi-turn extraction, leaving defense-aware attack–defense dynamics open.
4. Build standardized graph-leakage benchmarks and reporting protocols. The authors argue these would improve reproducibility and support safer GraphRAG systems, and note that graph-level privacy risks likely extend beyond text-only GraphRAG into areas such as evidence-intensive fact-checking and multimodal reasoning.

Target Audience

Security and privacy researchers working on RAG and LLM systems; GraphRAG and knowledge-graph engineers who need to understand the leakage surface of structured retrieval; practitioners deploying graph-augmented retrieval over proprietary corpora who are weighing defenses; and graduate students or advanced undergraduates already comfortable with retrieval-augmented generation, knowledge graphs, and adversarial evaluation who want a concrete, reproducible case study in budget-constrained extraction attacks.

Authors’ abstract

Graph-based retrieval-augmented generation (GraphRAG) systems construct knowledge graphs over document collections to support multi-hop reasoning. While prior work shows that GraphRAG responses may leak retrieved subgraphs, the feasibility of query-efficient reconstruction of the hidden graph structure remains unexplored under realistic query budgets. We study a budget-constrained black-box setting where an adversary adaptively queries the system to steal its latent entity-relation graph. We propose AGEA (Agentic Graph Extraction Attack), a framework that leverages a novelty-guided exploration-exploitation strategy, external graph memory modules, and a two-stage graph extraction pipeline combining lightweight discovery with LLM-based filtering. We evaluate AGEA on medical, agriculture, and literary datasets across Microsoft-GraphRAG and LightRAG systems. Under identical query budgets, AGEA significantly outperforms prior attack baselines, recovering up to 90% of entities and relationships while maintaining high precision. These results demonstrate that modern GraphRAG systems are highly vulnerable to structured, agentic extraction attacks, even under strict query limits. The code is available at https://github.com/shuashua0608/AGEA.