- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper proposes DIVER, a query strategy for extracting knowledge from black-box GraphRAG systems under a limited query budget. The main idea is to avoid repeatedly querying nodes whose neighborhoods contain a lot of overlapping information. DIVER uses BNRR and neighborhood query history to decide which entities to query next. Experiments on three datasets show that DIVER performs better than the baselines considered by the paper in terms of entity and edge recovery.
Critical strengths
- The main intuition is clear and reasonable: repeatedly querying highly connected nodes can be inefficient when their neighborhoods contain substantial redundancy.
- The method is relatively simple and easy to understand.
Critical weaknesses
- The paper discusses several recent graph reconstruction attacks, but does not compare against them experimentally. This makes it difficult to tell how DIVER compares with the strongest existing approaches.
- The attacker appears to control an additional instruction given to the response-generation model, rather than only the user's query. The authors should clarify whether DIVER still works when only the user query can be controlled.
Questions for authors
Clarification requests
- Why are the graph reconstruction methods discussed in the related work not included in the main comparison?
- Does DIVER require control over the response-generation instruction, or can it work when the attacker controls only the user query? Suggestions for future work
- Test DIVER on other GraphRAG implementations and LLMs.
- Study whether BNRR can reliably predict the amount of new information obtained by a query.
5 comments
Response to Reviewer qamS (2/3)
W2 & Q2: Regarding attacker control over the user query only
We appreciate your careful attention to the threat model.
DIVER does not require it. DIVER only decides which entity to ask about next and needs no access to the system prompt. In the submission, we separated retrieval and generation inputs so that retrieval is driven solely by the natural-language question our strategy selects, which isolates query allocation from retrieval noise caused by output instructions (Sec. 2.2). This was a choice for controlled evaluation, not a requirement of the method.
To verify this, we kept the operator's default GraphRAG system prompt and sent a single user message to both retrieval and generation, on G05 (mean ± SD over three 50-slot runs):
| Single user message | Method | Node R (%) | Node F1 (%) | Edge R (%) | Edge F1 (%) | Top-50 entities |
|---|---|---|---|---|---|---|
| Question + record request in the same message | DIVER | 20.47 ± 2.94 | 33.87 ± 3.97 | 15.33 ± 2.59 | 26.51 ± 3.87 | 43.3 ± 1.5 |
| Question + record request in the same message | AGEA | 14.32 ± 1.35 | 25.03 ± 2.05 | 11.77 ± 1.49 | 20.99 ± 2.39 | 35.0 ± 2.0 |
| Ordinary question only | DIVER | 16.77 ± 1.25 | 27.66 ± 1.78 | 6.56 ± 0.47 | 10.74 ± 0.74 | 44.7 ± 0.6 |
| Ordinary question only | AGEA | 14.94 ± 0.52 | 25.22 ± 0.63 | 5.93 ± 0.20 | 9.72 ± 0.27 | 43.3 ± 3.5 |
These results answer the question directly: DIVER does not need the response-generation instruction.
- Entities. With ordinary questions alone, DIVER still reaches about 45 of the 50 most structurally important entities, as many as when records are requested. Identifying the important entities of the index therefore requires only the user query.
- Links. Writing the record request into the same user message, which any user can do, more than doubles edge recall over ordinary questions. The separate instruction channel of the submitted setup is not needed for this level of recovery.
- Strategy. DIVER exceeds AGEA in recall and F1 under both user messages. The benefit of its query allocation therefore carries over unchanged to the weaker, query-only threat model.
Q3: Regarding other GraphRAG implementations and LLMs
Thank you for this suggestion for broader evaluation.
The submission already varies the target along several axes: three domains with different graph structure (Novel, Medical, Agriculture) and graph-size scaling from G05 to G10 (App. A.6). To extend this to the LLM dimension, we tested DeepSeek-V4-Flash and Qwen3.7-Flash as both answering model and question writer on G05 (Structured Record Response, one 50-slot run per pairing):
| Question writer | Answering model | Node P (%) | Node R (%) | Node F1 (%) | Edge P (%) | Edge R (%) | Edge F1 (%) |
|---|---|---|---|---|---|---|---|
| DeepSeek | DeepSeek | 99.89 | 17.78 | 30.19 | 99.37 | 13.09 | 23.13 |
| DeepSeek | Qwen | 98.22 | 19.86 | 33.04 | 94.43 | 14.66 | 25.38 |
| Qwen | DeepSeek | 99.91 | 22.47 | 36.68 | 97.96 | 18.03 | 30.46 |
| Qwen | Qwen | 99.42 | 20.50 | 34.00 | 90.66 | 15.43 | 26.37 |
Recovery stays at the same level, and is often higher, when the answering model, the writer, or both come from a different family. DIVER is therefore not tied to one LLM. Because DIVER interacts only through questions and answers and works on the attacker-side recovered graph, it does not depend on the GraphRAG implementation. In line with your suggestion, the revised PDF notes extending the evaluation to other implementations such as LightRAG as future work (App. A.11).
Response to Reviewer qamS (3/3)
Q4: Regarding whether BNRR reliably predicts the new information obtained by a query
Thank you for your expertise in this question.
We designed BNRR as a ranking signal for rank admission and validated it that way in the submission. In the controlled branch experiment of App. A.1, three policies start from identical graph states on Novel:
| Selection strategy | High-diversity (BNRR) | Degree-only | Low-diversity |
|---|---|---|---|
| New indexed edges per query | 25.69 | 23.81 | 19.69 |
| Edge overlap with observed graph (%) | 30.46 | 36.13 | 37.57 |
To examine individual queries, we compared pairs of entities at saved graph states that share the same observed degree and prior exposure but differ in pre-query BNRR. Saved states come from three DIVER trajectories per dataset (seeds 42–44), frozen after rounds 20, 40, 60 and 80. Each anchor is evaluated with two independent full writer–GraphRAG queries, and yield counts previously unrecovered directed pairs that match the index (App. A.1, Fig. 5).
| Domain | Matched pairs | New pairs per query, higher BNRR | New pairs per query, lower BNRR |
|---|---|---|---|
| Novel | 42 | 16.62 | 11.63 |
| Medical | 48 | 15.39 | 14.59 |
Read together, the comparisons show both what BNRR predicts and where it applies.
- Beyond degree. With degree and query history held fixed, the entity with higher BNRR returns more new relations per query on both Novel and Medical. On Novel the difference is about 43% (16.62 vs. 11.63). BNRR therefore predicts the amount of new information beyond what degree already captures.
- Where it applies. Since BNRR =
√(d·e)withe ∈ [1, d], it always lies in[√d, d], so an entity's BNRR is a lower bound on its degree. The matched pairs in Fig. 5 reach pre-query BNRR of about 19 on Novel and 15 on Medical, so they include entities with large neighborhoods, where redundancy among neighbors can differ substantially. This is the regime BNRR is designed for. With only two or three neighbors, there are at most a few possible links among them, the range[√d, d]is narrow, and BNRR reduces to degree by construction. BNRR therefore adds ranking information once neighborhoods are large enough for redundancy to vary. - At the pool level. In the frozen-state experiment, ranking the whole candidate pool by BNRR yields the most new edges and the least overlap, so the per-pair signal also turns into a better allocation of queries.
BNRR is used to rank candidates, and these results show that it ranks reliably in the regime where the ranking matters.
Revisions in the updated PDF (new text in blue):
- W1 & Q1: App. A.10 adds the comparison with GraphSteal (Table 14, Obs. 18), and App. B describes its implementation. Sec. 4.1 points to this comparison.
- W2 & Q2: App. A.9 reports the single-user-message and ordinary-question settings (Table 12, Obs. 17). Sec. 2.2 now states that DIVER requires control only over the question.
- Q3: App. A.11 reports the cross-family victim and query-writer models (Table 15, Obs. 19) and notes the extension to other implementations such as LightRAG as future work.
- Q4: App. A.1 adds the matched-pair comparison at equal observed degree and exposure (Fig. 5), and Sec. 3.1 points to it.
Thank you again sincerely for your time, efforts, and thoughtful feedback. We have incorporated your helpful comments in the revised manuscript. We would be glad to address any further comments or questions you may have.
Response to Reviewer qamS (1/3)
Dear Reviewer qamS,
Thank you for your expertise and thoughtful suggestions. We are glad you found the intuition clear and the method easy to follow. We answer each question below.
W1 & Q1: Regarding the comparison with graph reconstruction attacks in the related work
Thank you for your expertise in this line of work.
We chose baselines according to the object each method recovers. The main comparison already includes AGEA, which matches our budgeted graph-recovery setting most closely, and GRASP, a graph reconstruction attack discussed in our related work, adapted to whole-graph recovery (Table 1, App. B); its precision exceeds 98% on all three datasets while recall stays below 5%. Among the other methods in App. E, RAGCrawler targets coverage of the underlying text corpus rather than the indexed graph. GraphSteal's untargeted method recovers the indexed graph, which makes it a direct comparison.
To complete the picture, we implemented GraphSteal's untargeted method and evaluated it with DIVER and AGEA on G05 under the same index, answering model, Structured Record Response interface and 50-slot budget (mean ± SD over seeds 42–44). The last column counts recovered entities among the 50 most structurally important entities in the index.
Taken together, the three graph reconstruction attacks show how much the choice of the next entity matters.
Neither traversal order nor observed degree identifies which entities still hold unrecovered relations. DIVER's estimate of remaining potential, which combines neighborhood redundancy with neighbor-propagated query history, is what directs the same budget toward the important parts of the graph.