# GraphSteal: Structural Knowledge Stealing from Graph RAG via Traversal Reconstruction

arXiv: https://arxiv.org/abs/2605.28645 · HTML: https://mlsanity.com/paper/2605.28645/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge-graph and structured-knowledge RAG, one of 15 directions in Retrieval-augmented generation.
- Builds on 13 of its 27 references that are in the map.
- First posted on arXiv 27 May 2026.

## Placed in

- Retrieval-augmented generation / [Knowledge-graph and structured-knowledge RAG](https://mlsanity.com/rag/knowledge-graph-and-structured-knowledge-rag/)

## Builds on (most cited first, 13 of 13)

- [Extracting Training Data from Large Language Models](https://mlsanity.com/paper/2012.07805/) (2020)
- [Retrieval Augmentation Reduces Hallucination in Conversation](https://mlsanity.com/paper/2104.07567/) (2021)
- [Unifying Large Language Models and Knowledge Graphs: A Roadmap](https://mlsanity.com/paper/2306.08302/) (2023)
- [StructGPT: A General Framework for Large Language Model to Reason over Structured Data](https://mlsanity.com/paper/2305.09645/) (2023)
- [Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning](https://mlsanity.com/paper/2310.01061/) (2023)
- [Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph](https://mlsanity.com/paper/2307.07697/) (2023)
- [Knowledge Graph Prompting for Multi-Document Question Answering](https://mlsanity.com/paper/2308.11730/) (2023)
- [Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge Graphs](https://mlsanity.com/paper/2410.23875/) (2024)
- [Boosting Language Models Reasoning with Chain-of-Knowledge Prompting](https://mlsanity.com/paper/2306.06427/) (2023)
- [Follow My Instruction and Spill the Beans: Scalable Data Extraction from Retrieval-Augmented Generation Systems](https://mlsanity.com/paper/2402.17840/) (2024)
- [Generate-on-Graph: Treat LLM as both Agent and KG in Incomplete Knowledge Graph Question Answering](https://mlsanity.com/paper/2404.14741/) (2024)
- [Exploring Memorization in Fine-tuned Language Models](https://mlsanity.com/paper/2310.06714/) (2023)
- [Direct Evaluation of Chain-of-Thought in Multi-hop Reasoning with Knowledge Graphs](https://mlsanity.com/paper/2402.11199/) (2024)

## Built on by (most cited first, 1 of 1)

- [Seed-Anchored Budget-Bounded Graph Rendering for Question Answering on Industry-Standard Power-Grid Information and Exchange Models](https://mlsanity.com/paper/2609.02011/) (2026)

## Abstract (arXiv)

Retrieval-Augmented Generation (RAG) enhances LLMs by grounding generation in query-relevant external evidence. Beyond unstructured text corpora, Graph RAG integrates knowledge graphs into the retrieval pipeline, enabling LLMs to access entities, relations, and multi-hop dependencies encoded in structured knowledge. However, the same structured knowledge that empowers Graph RAG also creates a new privacy attack surface. We demonstrate that Graph RAG systems can be turned into structural oracles: through adaptive black-box interactions, an adversary can elicit sufficient relational evidence to reconstruct substantial portions of the hidden knowledge graph. We propose a structure-oriented reconstruction framework that recovers targeted graphs from both local and global perspectives. Specifically, Depth-Wise Heuristic Search extracts fine-grained node attributes by recursively expanding entity-centered evidence, while Breadth-Wise Diffusion Search infers graph topology by propagating across relation-induced neighborhoods. Experiments on generic and healthcare scenarios demonstrate that our method can recover over 90% of the original knowledge graph from representative Graph RAG systems, revealing sensitive entities, relations, and structural dependencies with high fidelity. Existing guradrails provide limited defense against our attack, highlighting the inherent difficulty of safeguarding structural privacy in Graph RAG pipelines.