pith. sign in

arxiv: 2605.28645 · v1 · pith:SVZG3D37new · submitted 2026-05-27 · 💻 cs.CR · cs.CL

GraphSteal: Structural Knowledge Stealing from Graph RAG via Traversal Reconstruction

Jinze Gu , Qinghua Mao , Xi Lin , Jun Wu This is my paper

Pith reviewed 2026-06-29 11:38 UTC · model grok-4.3

classification 💻 cs.CR cs.CL
keywords Graph RAGknowledge graphprivacy attackreconstructionblack-box attackstructural privacytraversal
0
0 comments X

The pith

An adversary can reconstruct over 90 percent of a Graph RAG knowledge graph via adaptive black-box queries.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Graph RAG systems integrate knowledge graphs into retrieval, which creates a new way for attackers to steal the underlying structure. The paper shows that targeted queries can extract enough evidence to rebuild entities, relations, and multi-hop connections. Two complementary search methods handle local node details and broader topology inference. Tests in generic and healthcare settings recover most of the original graph with high accuracy. Existing protections do little to stop the process.

Core claim

Graph RAG systems can be turned into structural oracles. Adaptive black-box interactions allow an adversary to reconstruct substantial portions of the hidden knowledge graph. Depth-Wise Heuristic Search extracts fine-grained node attributes by recursively expanding entity-centered evidence. Breadth-Wise Diffusion Search infers graph topology by propagating across relation-induced neighborhoods. Experiments recover over 90 percent of the original knowledge graph in generic and healthcare scenarios.

What carries the argument

The structure-oriented reconstruction framework that recovers targeted graphs from local and global perspectives using Depth-Wise Heuristic Search for node attributes and Breadth-Wise Diffusion Search for topology.

Load-bearing premise

Adaptive black-box queries will reliably draw out enough relational evidence for high-fidelity reconstruction without the system applying effective structural defenses.

What would settle it

A test in which a Graph RAG system with structural defenses limits reconstruction to well below 90 percent accuracy under the same query strategy.

Figures

Figures reproduced from arXiv: 2605.28645 by Jinze Gu, Jun Wu, Qinghua Mao, Xi Lin.

Figure 1
Figure 1. Figure 1: Adversarial queries exploit the retriever–LLM [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The attacker begins with an adversarial prompt to retrieve the neighborhood of an anchor node (node 1). [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Attack efficiency across traversal strategies (BFS, DFS, RW) on MIMIC and FreeBase. [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Attack efficiency across graphs of different [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 6
Figure 6. Figure 6: Overall effectiveness of the proposed methods. [PITH_FULL_IMAGE:figures/full_fig_p008_6.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper introduces GraphSteal, a structure-oriented reconstruction attack on black-box Graph RAG systems. It employs Depth-Wise Heuristic Search to recursively extract fine-grained node attributes and Breadth-Wise Diffusion Search to infer topology via relation-induced neighborhoods. The central claim is that these adaptive queries enable recovery of over 90% of the original knowledge graph (including entities, relations, and structural dependencies) in both generic and healthcare scenarios, while existing guardrails offer limited protection.

Significance. If the empirical results hold under realistic LLM summarization, the work identifies a previously under-explored privacy attack surface in Graph RAG pipelines. It supplies concrete, query-adaptive methods that achieve high-fidelity structural extraction and evaluates their effectiveness against deployed systems, which could motivate new structural privacy defenses in retrieval-augmented architectures.

major comments (2)
  1. [Abstract] Abstract: the central quantitative claim of >90% recovery is load-bearing for the contribution, yet the abstract (and the provided description of the framework) supplies no experimental details, baselines, error bars, dataset descriptions, or ablation studies. Without these, the fidelity of the reconstruction cannot be assessed.
  2. [Framework description] Framework (Depth-Wise Heuristic Search and Breadth-Wise Diffusion Search): the reconstruction success assumes Graph RAG responses return detailed, structured relational evidence (explicit entity-relation lists or raw triples). No analysis is given of how LLM-based summarization over retrieved subgraphs—which is standard in Graph RAG—could omit, condense, or distort topology and attributes, directly degrading reconstruction below the reported threshold.
minor comments (1)
  1. [Abstract] Abstract: 'guradrails' is a typo and should read 'guardrails'.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on the abstract and framework description. We provide point-by-point responses below and will revise the manuscript to address the concerns.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central quantitative claim of >90% recovery is load-bearing for the contribution, yet the abstract (and the provided description of the framework) supplies no experimental details, baselines, error bars, dataset descriptions, or ablation studies. Without these, the fidelity of the reconstruction cannot be assessed.

    Authors: Abstracts are constrained by length and conventionally omit detailed experimental parameters such as error bars and ablations, which appear in Sections 4 and 5. To improve clarity we will add a concise sentence to the abstract noting the two evaluation scenarios (generic and healthcare) and the primary recovery metric. Full baselines, statistical details, and ablations will remain in the experimental sections. revision: partial

  2. Referee: [Framework description] Framework (Depth-Wise Heuristic Search and Breadth-Wise Diffusion Search): the reconstruction success assumes Graph RAG responses return detailed, structured relational evidence (explicit entity-relation lists or raw triples). No analysis is given of how LLM-based summarization over retrieved subgraphs—which is standard in Graph RAG—could omit, condense, or distort topology and attributes, directly degrading reconstruction below the reported threshold.

    Authors: All reported results were obtained from representative Graph RAG pipelines that apply standard LLM summarization to retrieved subgraphs. The >90% recovery figures therefore already reflect performance under realistic summarization. We will insert a short clarifying paragraph in the framework section stating that the attack was evaluated end-to-end on such systems and briefly discussing how more aggressive summarization could affect fidelity. revision: yes

Circularity Check

0 steps flagged

No circularity: empirical attack framework with no derivations or self-referential reductions

full rationale

The paper presents an attack method (Depth-Wise Heuristic Search and Breadth-Wise Diffusion Search) and reports experimental recovery rates >90% on Graph RAG systems. No equations, fitted parameters, uniqueness theorems, or self-citations appear in the abstract or described framework. The central claim rests on black-box query interactions and empirical results rather than any reduction to inputs by construction. This matches the default expectation of no significant circularity for an empirical security paper.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Paper relies on standard assumptions of black-box query access and the existence of entity-relation structure in Graph RAG; no free parameters, axioms, or invented entities are stated in the abstract.

pith-pipeline@v0.9.1-grok · 5741 in / 978 out tokens · 35332 ms · 2026-06-29T11:38:07.014875+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

3 extracted references · 2 canonical work pages

  1. [1]

    Available online at: https://physionet

    Mimic-iv.PhysioNet. Available online at: https://physionet. org/content/mimiciv/1.0/(accessed August 23, 2021), pages 49–55. Jooyoung Lee, Thai Le, Jinghui Chen, and Dongwon Lee. 2023. Do language models plagiarize? In Proceedings of the ACM Web Conference 2023, pages 3637–3647. Jiale Liu, Jiahao Zhang, and Suhang Wang. 2025. Ex- posing privacy risks in g...

    work page arXiv 2021

  2. [2]

    InFindings of the Association for Computational Linguistics ACL 2024, pages 2862–2883

    Direct evaluation of chain-of-thought in multi- hop reasoning with knowledge graphs. InFindings of the Association for Computational Linguistics ACL 2024, pages 2862–2883. Shirui Pan, Linhao Luo, Yufei Wang, Chen Chen, Ji- apu Wang, and Xindong Wu. 2024. Unifying large language models and knowledge graphs: A roadmap. IEEE Transactions on Knowledge and Dat...

    2024

  3. [3]

    Retrieval Augmentation Reduces Hal- lucination in Conversation,

    Rascal: Calculation of graph similarity using maximum common edge subgraphs.The Computer Journal, 45(6):631–644. Kurt Shuster, Spencer Poff, Moya Chen, Douwe Kiela, and Jason Weston. 2021. Retrieval augmentation reduces hallucination in conversation.arXiv preprint arXiv:2104.07567. Jiashuo Sun, Chengjin Xu, Lumingyuan Tang, Saizhuo Wang, Chen Lin, Yeyun G...

    work page arXiv 2021