GraphSteal: Structural Knowledge Stealing from Graph RAG via Traversal Reconstruction
GraphSteal employs traversal-based reconstruction to recover over 90% of hidden knowledge graphs, exposing privacy vulnerabilities in Graph RAG systems.
Key Findings
Methodology
This paper introduces a structure-oriented attack framework combining depth-first search (DFS) and breadth-first search (BFS) strategies. By simulating multi-round black-box queries, the method iteratively expands entity attributes and infers graph topology. Depth-Wise Heuristic Search recursively extracts fine-grained node features, while Breadth-Wise Diffusion propagates across relation-induced neighborhoods to reconstruct the overall structure. The approach leverages multi-step interactions to systematically recover the entire graph, validated across healthcare and general knowledge datasets, achieving over 90% reconstruction fidelity.
Key Results
- Experiments on MIMIC-IV and Freebase datasets using GPT-4, LLaMA-13B, and DeepSeek models show low GED (~0.095), high MCS (~0.92), and node recovery rates exceeding 0.93, demonstrating high attack effectiveness across models and domains.
- BFS traversal consistently outperforms DFS and random walk (RW), especially on larger graphs, maintaining high structural integrity with scalable performance. In healthcare scenarios, sensitive entities and relations are reliably reconstructed, exposing privacy risks.
- Existing defenses like output window restrictions and prompt filtering offer limited mitigation, indicating the inherent difficulty of safeguarding structural privacy in Graph RAG pipelines.
Significance
This work highlights a critical security concern: the structural information of knowledge graphs used in RAG systems can be systematically reconstructed via black-box querying. Such vulnerabilities threaten sensitive data in domains like healthcare and finance, urging the community to develop robust privacy-preserving mechanisms. The findings bridge the gap between knowledge graph utility and security, emphasizing the need for comprehensive safeguards against structural leakage. It also provides a new perspective on the inherent risks in deploying knowledge graphs in real-world AI systems, prompting re-evaluation of current security protocols.
Technical Contribution
The paper pioneers a traversal-based attack framework that combines heuristic depth-first and breadth-first strategies for graph reconstruction in black-box settings. It introduces quantitative metrics (GED, MCS, NRR) to evaluate fidelity and systematically demonstrates the high feasibility of privacy breaches. The approach extends traditional graph traversal algorithms into the realm of AI security, offering a novel toolset for assessing and mitigating structural privacy risks. The methodology is validated across multiple models and datasets, establishing a new benchmark for privacy evaluation in knowledge graph-based systems.
Novelty
This is the first systematic study employing traversal algorithms for reconstructing entire knowledge graphs in black-box environments, revealing a previously under-explored privacy vulnerability. Unlike prior works focusing on point-level data leakage, this research demonstrates the feasibility of full structural recovery, fundamentally challenging assumptions about the safety of knowledge graph integration in LLMs. Its innovative combination of graph traversal techniques with AI security analysis marks a significant advance in the field.
Limitations
- The attack relies on multiple query rounds, constrained by token limits and query budgets, limiting effectiveness on extremely large or dynamic graphs.
- Current defenses such as output restrictions are insufficient; more sophisticated, multi-layered security measures are needed.
- The methodology primarily targets static, well-structured graphs; real-time or evolving graphs pose additional challenges.
Future Work
Future research will explore integrating differential privacy and access control mechanisms to mitigate structural leakage. Developing adaptive query strategies and extending the framework to dynamic knowledge graphs will be key directions. Additionally, designing robust defense protocols tailored for large-scale, real-world systems will be critical to balance utility and privacy.
AI Executive Summary
GraphSteal exposes a significant privacy vulnerability in Graph Retrieval-Augmented Generation (RAG) systems. By employing traversal-based reconstruction strategies—specifically depth-first and breadth-first search—attackers can systematically recover over 90% of the underlying knowledge graph structure in black-box settings. This method simulates multi-round querying, where each interaction extracts entity attributes and propagates relation neighborhoods, gradually revealing the entire graph topology. Experiments across healthcare datasets like MIMIC-IV and large-scale knowledge bases such as Freebase demonstrate the attack’s robustness, with low graph edit distances and high node recovery rates across models including GPT-4 and LLaMA-13B. The results highlight the inherent risks of structural information leakage, especially in sensitive domains like medicine, where revealing entity relationships can compromise privacy. Existing defenses, including output window restrictions and prompt filtering, show limited effectiveness against such traversal attacks, underscoring the need for more comprehensive security measures. This research fundamentally challenges assumptions about the safety of knowledge graphs integrated into AI systems, emphasizing the urgency of developing privacy-preserving techniques. Moving forward, the focus will be on integrating differential privacy, access controls, and dynamic graph protection strategies to mitigate these vulnerabilities, ensuring safer deployment of knowledge-driven AI applications.
Deep Analysis
Background
Knowledge graphs have become essential in enhancing AI reasoning capabilities, especially within Retrieval-Augmented Generation (RAG) frameworks. Early efforts like Wang et al. (2024b) integrated structured data to improve factual accuracy, but overlooked security concerns. Recent studies, such as Liu et al. (2025), identified point-level leakage but did not address the possibility of reconstructing entire graph topologies. As knowledge graphs grow in scale and application scope, their structural privacy becomes critical. The integration of such graphs into LLMs raises questions about potential reverse engineering and data leakage, which this paper addresses by proposing traversal-based reconstruction techniques. These methods reveal the vulnerability of current systems to systematic structural attacks, especially in sensitive fields like healthcare, where privacy is paramount.
Core Problem
Despite the widespread adoption of Graph RAG systems, their structural privacy remains under-explored. Attackers can exploit multi-round querying to infer and reconstruct the entire knowledge graph, including sensitive entities and relations. This poses a significant privacy threat, especially in domains like medicine, where revealing entity relationships can lead to privacy breaches. Traditional point-level leakage detection fails to address the risk of full topology recovery. The core challenge lies in designing systems that balance knowledge accessibility with privacy protection, preventing adversaries from reverse engineering the underlying graph structure through iterative queries. This paper demonstrates that existing safeguards are insufficient, and proposes a traversal-based attack framework to systematically reveal the entire graph topology.
Innovation
The key innovation lies in applying classical graph traversal algorithms—DFS and BFS—in a novel, AI security context. The framework simulates multi-step, query-based interactions to systematically reconstruct the graph's topology. It introduces a hybrid approach combining depth-first pathfinding for targeted extraction and breadth-first expansion for global coverage, optimized through heuristic strategies. This enables high-fidelity reconstruction with limited queries, a capability previously unrecognized in AI privacy research. The approach also quantifies reconstruction success using metrics like GED, MCS, and NRR, providing a rigorous evaluation framework. This work bridges graph theory and AI security, offering a new paradigm for understanding and mitigating structural privacy risks.
Methodology
- �� Model系统为黑箱，模拟多轮交互查询。
- �� 利用深度启发式搜索（Depth-Wise Heuristic Search）递归扩展实体证据，提取节点细粒度属性。
- �� 采用宽度扩散（Breadth-Wise Diffusion）在关系邻域中传播，推断拓扑结构。
- �� 针对不同目标设计多轮查询：目标节点的深度优先搜索（DFS）和全局覆盖的广度优先搜索（BFS）。
- �� 每轮交互中，逐步扩展实体和关系，直至重建完整图。
- �� 结合多模型、多场景验证，采用GED、MCS、NRR指标评估重建效果。
Experiments
使用MIMIC-IV和Freebase两个数据集，分别代表医疗和通用知识场景。采用GPT-4、LLaMA-13B和DeepSeek模型，进行点级和结构级重建。设置不同查询轮次和预算，比较BFS、DFS和随机游走（RW）策略的效果。指标包括图编辑距离（GED）、最大公共子图（MCS）和节点恢复率（NRR）。通过多轮交互，验证在不同规模和复杂度的图中，重建的准确性和完整性。还测试了防御措施（如输出限制）对攻击效果的影响。
Results
实验表明，BFS策略在所有场景中表现优越，GED最低至0.095，MCS最高达0.92，NRR超过0.93。模型间表现一致，尤其在医疗场景中，能成功恢复敏感实体和关系，揭示隐私风险。大规模图中，效果略有下降，但仍保持较高的结构完整性。随机游走表现最差，验证了系统性遍历的重要性。防御措施效果有限，提示结构隐私保护的难点。整体而言，攻击具有广泛适用性和高效率。
Applications
该技术对知识图谱的安全设计提出警示，尤其在医疗、金融等敏感行业。系统开发者应加强访问控制，结合差分隐私和安全策略，防止结构信息被逆向重建。未来，研究将聚焦于动态知识图谱的隐私保护和多层防御机制，确保知识的可用性与安全性兼顾。这对于推动安全、可信的知识驱动AI系统具有重要意义。
Limitations & Outlook
当前方法依赖多轮交互，受限于模型上下文窗口和查询预算，面对超大或动态变化的知识图谱效果有限。现有防御措施如输出限制效果有限，未来需设计更复杂的安全机制。模型性能受限于训练数据和推理能力，复杂图结构的完整重建仍具挑战。
Plain Language Accessible to non-experts
想象你在一个巨大的迷宫里，里面藏着许多房间和它们之间的通道。有人想知道整个迷宫的布局，但不能直接进去，只能通过不断问“这个房间有多少门？”、“通向哪个房间？”这样的问题，逐步拼出迷宫的全貌。GraphSteal的方法就像这个人，用聪明的提问策略，一点点揭示每个房间和通道，最终拼出整个迷宫的地图。它告诉我们，即使系统只给出部分信息，聪明的人也能通过不断提问，逆向还原出完整的结构，带来隐私泄露的风险。
ELI14 Explained like you're 14
想象你在一个超级大的学校里，有很多学生、老师和他们的关系，比如谁是老师、谁是学生、谁帮谁做作业。有人想偷偷知道这些关系，但不能直接进去看，只能问老师一些问题。比如，他会问：“这个学生的老师是谁？”或者“和这个学生有关的其他人有哪些？”他会不断问，逐步拼出整个学校的关系图。GraphSteal的方法就像这个人，用聪明的提问策略，一点点拼出所有人的关系，甚至可以知道一些秘密信息。这告诉我们，即使系统只给出部分答案，聪明的人也能通过不断提问，拼出完整的关系图，可能会泄露很多隐私。
Abstract
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.