Protecting the relationships an AI search system can reveal

What can an outsider learn from an AI assistant that answers questions about documents they cannot inspect? If the assistant connects information through a knowledge graph, its answers can reveal not just individual facts but a network of relationships.

A November 6 arXiv preprint by Jie Fu, Yuan Hong, Yue Ning and Wendy Hui Wang proposes RelGuard, a defense that changes relationship information before documents enter such a system. Its experiments show substantially reduced recovery of relationship meanings, but also illustrate the cost: protecting information can make legitimate answers worse. The findings are preprint results, not established deployment guarantees.

Why relationships need their own protection

Graph retrieval-augmented generation, or GraphRAG, represents entities and their relationships in a graph, then retrieves connected evidence to help a language model answer questions. A relationship can be written as a three-part statement: Alice, works for, Company B.

That statement contains two potentially sensitive disclosures. Connectivity reveals that Alice and Company B are linked. Relationship semantics reveals what the link means: employment rather than investment or founding.

The researchers consider an attacker who already knows the entities’ identities but not their relationships. The attacker can ask questions, read answers and adapt subsequent queries, without accessing the documents, index or model internals. The evaluation targets relationships directly touching a chosen entity, rather than reconstruction of an entire graph.

Change the evidence before indexing

RelGuard works in four stages. First, a language model extracts directed entity–relationship–entity statements and records their occurrences. Equivalent expressions are grouped so that repeated mentions receive the same treatment.

Second, it generates possible replacement relationships using only the ordered types of the two entities. A person-to-organization pair might support employment, founding or investment relationships. Crucially, the candidate pool must not depend on the private relationship being protected. Otherwise, the available replacements could themselves disclose information.

Third, a randomized procedure chooses a replacement or a deletion outcome. Relationships closer to the original in a fixed text-embedding representation receive greater weight. A privacy parameter, epsilon, controls how strongly sampling favors higher-scoring outcomes; smaller values make the distribution flatter. A separate parameter controls deletion’s weight.

Finally, RelGuard reconstructs the documents. It replaces surviving relationship expressions consistently and deletes every sentence containing a relationship selected for removal. If a sentence expresses several relationships, deleting any one removes the whole sentence. GraphRAG then indexes this altered corpus once for subsequent queries.

This is not simply a refusal instruction. It changes the evidence available to the assistant—and replacements can turn originally correct statements into incorrect ones.

What the mathematical guarantee covers

The paper defines “relation differential privacy,” which bounds how much output probabilities can change when one relationship predicate is exchanged for another. The bound depends on their embedding-based distance: nearby meanings receive tighter protection than distant ones.

Its scope matters. The document-level comparison holds entity pairs, relationship slots, occurrence mappings and all other text fixed. Candidate pools and other mechanism settings must also remain fixed across compared inputs. Reconstruction must use the masked document and sampled replacements without consulting the original relationship expressions.

The guarantee therefore does not compare arbitrary documents, hide entity identities or establish conventional edge-existence privacy between graphs with different original edge sets. Deletion empirically reduces connectivity recovery, but that result should not be confused with a broader mathematical guarantee about whether an original edge existed.

Stronger protection, with measurable losses

The experiments used HotpotQA and 2WikiMultiHopQA documents with LightRAG, PathRAG and HippoRAG 2. The authors tested two targeted reconstruction attacks, GRASP and GraphSteal, reporting means over three trials. Their main defense comparison used GPT-4o-mini as the answer generator.

At epsilon five, RelGuard produced the lowest relationship-recovery F1 in all 12 system–dataset–attack combinations. F1 combines precision and recall; lower attack F1 indicates less successful recovery. RelGuard’s scores were 26.98–44.35 percentage points below the strongest competing defense in each setting. It also achieved the lowest connectivity-recovery F1 in 11 of 12 combinations.

Those gains did not come with universally better answers. Question-answering F1 fell by 2.98–8.97 percentage points relative to undefended systems, and generally remained below existing defenses. For HippoRAG 2 on 2WikiMultiHopQA, it dropped from 70.50 to 61.53.

The remaining boundary

The experiments cover two benchmarks and two targeted attacks, not every deployment or adversary. Relationship matching also relies on a language-model judge, while the formal protection depends on the specified extraction, alignment and reconstruction conditions.

RelGuard demonstrates a concrete trade-off: limiting what a retrieval system knows can limit what an attacker recovers. But the altered evidence can also mislead legitimate answers. A useful privacy assessment must track both outcomes, rather than treating a formal label or a lower attack score as sufficient.