GraphRAG relations get a privacy budget: RelGuard cuts relation-recovery F1 by 26.98 to 44.35 points
Synopsis
GraphRAG links information across documents through entity relations, but black-box queries can also be used to reconstruct the knowledge graph, leaking whether entities are connected and what those relations mean. RelGuard rewrites source documents before indexing: it generates candidate relations from entity types, then uses an exponential mechanism to sample a replacement predicate or delete each relation, with a relation-level differential privacy guarantee. Across LightRAG, PathRAG and HippoRAG 2, two datasets and two reconstruction attacks, its relation-recovery F1 is 26.98 to 44.35 percentage points below the strongest baseline, while the extra question-answering F1 loss is 0.59 to 4.78 points in most settings.
Interpretation
RelGuard protects relation privacy along two dimensions, whether a connection exists between an entity pair and what that connection means, by rewriting source documents before GraphRAG builds its index rather than restricting wording at answer time. Earlier GraphRAG defenses reduce leakage by modifying generation instructions or retrieved context, including Abstractive, ID Alignment, Decoy and Protective Prompt, and these methods provide no formal privacy guarantee. Across the 12 system-dataset-attack combinations formed by LightRAG, PathRAG and HippoRAG 2 with 2WikiMultiHopQA and HotpotQA, RelGuard has the lowest relation-recovery F1, 26.98 to 44.35 percentage points below the strongest baseline; its connection-recovery F1 is lowest in 11 of the 12 combinations.
The rewrite runs in four steps: extract canonical entity-relation triples from the document, generate a candidate predicate pool from the subject and object entity types, sample a replacement predicate or a null outcome for each relation, and reconstruct the document from the sampled outcomes. Relation differential privacy (relation-DP) calibrates output indistinguishability by the semantic distance between predicate embeddings and treats relation removal as an output with a fixed distance, so semantically close replacements face a tighter bound than distant ones. Perturbation uses the exponential mechanism, candidate pools are generated by a large language model from ordered entity-type pairs, and relation predicates are encoded with nli-roberta-base-v2; experiments run on a single NVIDIA A100 with 40 GB of memory and report the mean over three trials.
Perspective
The evaluation covers three document-based GraphRAG systems, LightRAG, PathRAG and HippoRAG 2, on 2WikiMultiHopQA and HotpotQA, under GRASP and targeted GraphSteal, with GPT-4o-mini as the victim generator and Gemini-2.5-Flash results reported in the appendix. The threat model assumes an adversary who knows the identities of entities appearing in the document but not the relations among them, and who has only black-box access; document poisoning and system compromise are outside its scope.
The privacy guarantee compares relation assignments on fixed, aligned entity pairs rather than inputs with different original edge sets. Smaller privacy budgets lower connection and relation recovery but also lower question-answering F1; for HippoRAG 2 on 2WikiMultiHopQA, dropping the budget from 10 to 0.1 lowers QA F1 from 62.99 to 52.75. Raising the candidate pool from 5 to 20 raises both QA F1 and relation-recovery F1, while connection recovery peaks at 86.34 for 15 candidates and then declines slightly.