Differentially Private GraphRAG: Protecting Relation Connectivity and Semantics

Jie Fu; Yuan Hong; Yue Ning; Wendy Hui Wang

cs.CRNov 6, 2026

Differentially Private GraphRAG: Protecting Relation Connectivity and Semantics

Authors: Jie Fu, Yuan Hong, Yue Ning, Wendy Hui Wang

Organizations: Stevens Institute of Technology, Hoboken, NJ, USA · University of Connecticut, Storrs, CT, USA

Abstract

Graph Retrieval-Augmented Generation (GraphRAG) connects information across documents through entity relationships to support relational reasoning. However, black-box access to GraphRAG systems can enable adversaries to reconstruct knowledge graphs and recover both structural connectivity between entities and the semantics of their relationships. Existing defenses lack formal privacy guarantees and provide limited protection against such reconstruction attacks. We propose RelGuard, the first differentially private framework for GraphRAG, which provides formal privacy guarantees by mitigating connectivity leakage and protecting relations and their semantic meaning through relation removal. We formalize relation differential privacy (relation-DP), which bounds the distinguishability of mechanism outputs according to the semantic distance between alternative relations while accounting for relation removal. Building on this definition, we develop a four-step defense mechanism that sanitizes source documents before GraphRAG indexing by perturbing relation predicates or removing their associated connectivity using the exponential mechanism. Experiments across three GraphRAG systems and two targeted reconstruction attacks demonstrate that RelGuard provides stronger protection against reconstruction attacks than four existing defense mechanisms while better preserving downstream utility.

Figures & tables

Victim	Defense	2WikiMultiHopQA					HotpotQA
		GRASP		GraphSteal		QA F1 $\uparrow$	GRASP		GraphSteal		QA F1 $\uparrow$
		Conn. F1 $\downarrow$	Rel. F1 $\downarrow$	Conn. F1 $\downarrow$	Rel. F1 $\downarrow$	QA F1 $\uparrow$	Conn. F1 $\downarrow$	Rel. F1 $\downarrow$	Conn. F1 $\downarrow$	Rel. F1 $\downarrow$	QA F1 $\uparrow$
LightRAG	no-defense	89.63	84.26	89.14	85.54	49.48	83.78	75.97	90.31	80.98	61.47
	Abstractive	88.76	83.33	89.72	85.13	46.37	82.81	75.80	89.51	80.65	60.41
	ID Alignment	87.28	83.36	89.33	85.88	46.53	83.40	75.32	90.70	80.04	60.24
	Decoy	85.57	80.06	82.57	77.87	49.09	80.56	74.07	78.99	73.26	61.23

Table 1. Performance of RelGuard and defense baselines (

\epsilon=5

, GPT-4o-mini). We use GRASP and targeted GraphSteal to measure the privacy leakage of connectivity and relation. Bold values mark the lowest recovery F1 for each system, dataset, attack, and metric, and the highest QA F1 for each system and dataset.

Victim	Config	2WikiMultiHopQA					HotpotQA
		GRASP		GraphSteal		QA F1 $\uparrow$	GRASP		GraphSteal		QA F1 $\uparrow$
		Conn. F1 $\downarrow$	Rel. F1 $\downarrow$	Conn. F1 $\downarrow$	Rel. F1 $\downarrow$	QA F1 $\uparrow$	Conn. F1 $\downarrow$	Rel. F1 $\downarrow$	Conn. F1 $\downarrow$	Rel. F1 $\downarrow$	QA F1 $\uparrow$
HippoRAG 2	no-DP	76.99	68.51	75.71	69.93	70.50	70.92	62.48	78.37	67.21	71.91
	$\epsilon=10$	76.39	20.14	74.47	29.70	62.99	55.35	19.31	71.77	30.99	67.45
	$\epsilon=5$	69.75	19.61	69.60	25.81	61.53	45.03	13.63	63.42	23.47	67.25
	$\epsilon=1$	59.39	18.12	54.08	21.79	53.40	44.82	11.37	62.67	21.71	64.90

Table 2. Relation privacy leakage and QA utility of RelGuard under different privacy budgets (GPT-4o-mini).

$\epsilon$	Conn. F1 $\downarrow$		Rel. F1 $\downarrow$		QA F1 $\uparrow$
$\epsilon$	w/o null	w/ null	w/o null	w/ null	w/o null	w/ null
1	89.84	65.45	48.39	28.71	46.97	45.17
5	86.56	83.30	45.39	40.94	47.52	44.85

Table 3. Null-candidate ablation on 2WikiMultiHopQA with LightRAG under GRASP.

Panel of Figure 3 — Figure 3. Sensitivity analysis.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 4 — Figure 4. Prompt for entity and relation extraction.

Panel of Figure 5 — Figure 5. Prompt for type-conditioned candidate generation.

Victim	Config	2WikiMultiHopQA					HotpotQA
		GRASP		GraphSteal		QA F1 $\uparrow$	GRASP		GraphSteal		QA F1 $\uparrow$
		Conn. F1 $\downarrow$	Rel. F1 $\downarrow$	Conn. F1 $\downarrow$	Rel. F1 $\downarrow$	QA F1 $\uparrow$	Conn. F1 $\downarrow$	Rel. F1 $\downarrow$	Conn. F1 $\downarrow$	Rel. F1 $\downarrow$	QA F1 $\uparrow$
HippoRAG 2	no-DP	76.83	71.50	85.43	77.71	65.10	75.95	68.51	72.72	61.95	75.62
	$\epsilon=10$	76.61	18.52	75.89	19.73	57.53	70.71	23.47	71.23	28.11	70.03
	$\epsilon=5$	74.59	13.21	73.80	16.74	55.31	66.13	16.95	63.19	19.68	64.06
	$\epsilon=1$	55.43	11.53	56.50	14.98	53.62	61.34	16.71	61.54	18.87	66.63

Appendix

Table 4. Privacy–utility trade-off of RelGuard with Gemini-2.5-Flash.

Privacy-Preserving RAG

See all 15 papers

GraphSteal: Structural Knowledge Stealing from Graph RAG via Traversal Reconstruction
May 27, 2026Jinze Gu, Qinghua Mao, Xi Lin +1Model Extraction Attacks Graph Retrieval-Augmented Generation
School of Computer Science, Shanghai Jiao Tong University
Private Retrieval Augmented Generation via Random Projection
Oct 15, 2026Dixi Yao, Tahseen Rabbani, Tian LiRandom Projection Privacy-Preserving RAG
University of Chicago
Graph Reconstruction from Differentially Private GNN Explanations
May 5, 2026Rishi Raj Sahoo, Jyotirmaya Shivottam, Subhankar MishraData Leakage Differential Privacy
National Institute of Science Education and Research (NISER), Bhubaneswar, India · Homi Bhabha National Institute, Mumbai, India

May 27, 2026J/K move · Enter open · S save

GraphSteal: Structural Knowledge Stealing from Graph RAG via Traversal Reconstruction

Jinze Gu, Qinghua Mao, Xi Lin, Jun Wu

School of Computer Science, Shanghai Jiao Tong University

Model Extraction Attacks Graph Retrieval-Augmented Generation RAG Security

Open paper AskPDF 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.

Abstract

Privacy-Preserving RAG

Explore similar work

GraphSteal: Structural Knowledge Stealing from Graph RAG via Traversal Reconstruction

Private Retrieval Augmented Generation via Random Projection

Graph Reconstruction from Differentially Private GNN Explanations