Elamur Research⌕
☰
home / papers / 2026 / Query-Efficient Agentic Graph Extraction Attacks on GraphRAG Systems

Query-Efficient Agentic Graph Extraction Attacks on GraphRAG Systems

Paper · 2026 · Shuhua Yang, Jiahao Zhang, Yilong Wang et al.

Summary

GraphRAG systems turn document collections into entity–relation knowledge graphs to support multi-hop reasoning. Earlier work showed that individual retrieved subgraphs can leak. This paper asks a harder question: can an attacker with only black-box access and a limited number of queries rebuild a large, coherent part of the hidden graph?

The authors frame this as a query-efficient graph extraction attack and propose AGEA (Agentic Graph Extraction Attack). AGEA is an iterative loop with four parts:

  • a query generator that switches between broad exploration, guided by graph-level novelty signals, and targeted exploitation around entities it has already found;
  • persistent Graph Memory and Query Memory modules;
  • a two-stage extraction module: fast regex-based discovery feeds a raw graph, and an LLM filter then commits only cleaned candidates to a filtered graph.

AGEA is tested on medical, agriculture, and literary (Novel) data against Microsoft-GraphRAG and LightRAG. With equal query budgets it beats earlier attacks, recovering up to 90% of entities and relations at high precision. The results show that structured retrieval opens a serious privacy risk, even when queries are strictly limited.

Key points

  • Threat model: strict black-box access. The attacker cannot see the retriever, the graph G, or the LLM parameters, and only receives query responses under a fixed budget T.
  • Separate graph states: keeping a raw graph and a filtered graph stops aggressive filtering from lowering novelty scores, which would otherwise stall exploration.
  • Victims and data: M-GraphRAG and LightRAG; public data including GraphRAG-Bench and Agriculture. One ablation uses the Medical dataset with a 250-query budget.
  • Scale effect: on the 20-book Novel corpus, leakage falls because the graph is larger and more diverse, but AGEA still recovers a non-trivial share. Precision is especially high on LightRAG.
  • Limitations: AGEA depends on the victim returning structured, parseable output, and deployed defenses such as rate limiting or response filtering are not modeled. Code is available at github.com/shuashua0608/AGEA.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Pennsylvania State UniversityState College · United States56 works · 5,360 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

Cite

Cite as Shuhua Yang, Jiahao Zhang, Yilong Wang, Dongwon Lee and Suhang Wang. 2026. Query-Efficient Agentic Graph Extraction Attacks on GraphRAG Systems. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.acl-long.727

@inproceedings{yang2026query,
  title = {{Query-Efficient Agentic Graph Extraction Attacks on GraphRAG Systems}},
  author = {Shuhua Yang, Jiahao Zhang, Yilong Wang, Dongwon Lee and Suhang Wang},
  booktitle = {Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2026},
  doi = {10.18653/v1/2026.acl-long.727},
  url = {https://doi.org/10.18653/v1/2026.acl-long.727}
}

References

50 references, 9 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Ali Al-Lawati and Suhang Wang. 2026. A systemic evaluation of multimodal rag privacy. arXiv preprint arXiv:2601.17644. — [arXiv:2601.17644](https://arxiv.org/abs/2601.17644) find
  2. Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. 2002. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235–256. find
  3. Harsh Chaudhari, Giorgio Severi, John Abascal, Matthew Jagielski, Christopher A Choquette-Choo, Milad Nasr, Cristina Nita-Rotaru, and Alina Oprea. 2024. Phantom: General trigger attacks on retrieval augmented language generation. arXiv preprint arXiv:2405.20485. find
  4. Stav Cohen, Ron Bitton, and Ben Nassi. 2024. Unleashing worms and extracting data: Escalating the outcome of attacks against rag-based inference in scale and severity using jailbreaking. arXiv preprint arXiv:2409.08045. — [arXiv:2409.08045](https://arxiv.org/abs/2409.08045) find
  5. Christian Di Maio, Cristian Cosci, Marco Maggini, Valentina Poggioni, and Stefano Melacci. 2024. Pirates of the rag: Adaptively attacking llms to leak knowledge bases. arXiv preprint arXiv:2412.18295. — [arXiv:2412.18295](https://arxiv.org/abs/2412.18295) find
  6. Darren Edge, Ha Trinh, Newman Cheng, Joshua Bradley, Alex Chao, Apurva Mody, Steven Truitt, Dasha Metropolitansky, Robert Osazuwa Ness, and Jonathan Larson. 2024. From local to global: A graph rag approach to query-focused summarization. arXiv preprint arXiv:2404.16130. find
  7. Zirui Guo, Lianghao Xia, Yanhua Yu, Tu Ao, and Chao Huang. 2024. Lightrag: Simple and fast retrieval-augmented generation. arXiv preprint arXiv:2410.05779.
  8. Jiashu He, Jinxuan Fan, Bowen Jiang, Ignacio Houine, Dan Roth, and Alejandro Ribeiro. 2025a. Self-give: Associative thinking from limited structured knowledge for enhanced large language model reasoning. arXiv preprint arXiv:2505.15062. find
  9. Xiaoxin He, Yijun Tian, Yifei Sun, Nitesh Chawla, Thomas Laurent, Yann LeCun, Xavier Bresson, and Bryan Hooi. 2024. G-retriever: Retrieval-augmented generation for textual graph understanding and question answering. Advances in Neural Information Processing Systems, 37:132876–132907.
  10. Yu He, Yifei Chen, Yiming Li, Shuo Shao, Leyi Qi, Boheng Li, Dacheng Tao, and Zhan Qin. 2025b. External data extraction attacks against retrieval-augmented large language models. arXiv preprint arXiv:2510.02964. — [arXiv:2510.02964](https://arxiv.org/abs/2510.02964) find
  11. Yiqian Huang, Shiqi Zhang, and Xiaokui Xiao. 2025. Ket-rag: A cost-efficient multi-granular indexing framework for graph-rag. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 2, pages 1003–1012. find
  12. Changyue Jiang, Xudong Pan, Geng Hong, Chenfu Bao, and Min Yang. 2025. Feedback-guided extraction of knowledge base from retrieval-augmented llm applications. arXiv preprint arXiv:2411.14110. — [arXiv:2411.14110](https://arxiv.org/abs/2411.14110) find
  13. Bernal Jimenez Gutierrez, Yiheng Shu, Yu Gu, Michihiro Yasunaga, and Yu Su. 2024. Hipporag: Neurobiologically inspired long-term memory for large language models. Advances in Neural Information Processing Systems, 37:59532–59569.
  14. Bowen Jin, Chulin Xie, Jiawei Zhang, Kashob Kumar Roy, Yu Zhang, Zheng Li, Ruirui Li, Xianfeng Tang, Suhang Wang, Yu Meng, and 1 others. 2024. Graph chain-of-thought: Augmenting large language models by reasoning on graphs. In Findings of the Association for Computational Linguistics: ACL 2024, page…
  15. Jiale Liu, Jiahao Zhang, and Suhang Wang. 2025. Exposing privacy risks in graph retrieval-augmented generation. arXiv preprint arXiv:2508.17222. find
  16. Jason Lucas, Adaku Uchendu, Michiharu Yamashita, Jooyoung Lee, Shaurya Rohatgi, and Dongwon Lee. 2023. Fighting fire with fire: The dual role of llms in crafting and detecting elusive disinformation. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 142… find
  17. Haitong Luo, Fali Wang, Weiyao Zhang, Xianren Zhang, Zhiwei Zhang, Tianxiang Zhao, Minhua Lin, Jiahao Zhang, Hui Liu, Xianfeng Tang, and 1 others. 2026. Graphs for llms: A survey of graph-assisted large language models. Authorea Preprints. find
  18. Linhao Luo, Zicheng Zhao, Gholamreza Haffari, Dinh Phung, Chen Gong, and Shirui Pan. 2025. Gfm-rag: graph foundation model for retrieval augmented generation. arXiv preprint arXiv:2502.01113. — [arXiv:2502.01113](https://arxiv.org/abs/2502.01113) find
  19. Costas Mavromatis and George Karypis. 2025. Gnn-rag: Graph neural retrieval for efficient large language model reasoning on knowledge graphs. In Findings of the Association for Computational Linguistics: ACL 2025, pages 16682–16699. find
  20. Junki Mori, Kazuya Kakizaki, Taiki Miyagawa, and Jun Sakuma. 2025. Differentially private synthetic text generation for retrieval-augmented generation (rag). arXiv preprint arXiv:2510.06719.
  21. Vinh Nguyen, Cuong Dang, Jiahao Zhang, Hoa Tran, Minh Tran, Trinh Chau, Thai Le, Lu Cheng, and Suhang Wang. 2026. Urag: A benchmark for uncertainty quantification in retrieval-augmented large language models. arXiv preprint arXiv:2603.19281. — [arXiv:2603.19281](https://arxiv.org/abs/2603.19281) find
  22. Zhenting Qi, Hanlin Zhang, Eric P Xing, Sham M Kakade, and Himabindu Lakkaraju. 2025. Follow my instruction and spill the beans: Scalable data extraction from retrieval-augmented generation systems. In The Thirteenth International Conference on Learning Representations. find
  23. Zhisheng Qi, Utkarsh Sahu, Li Ma, Haoyu Han, Ryan Rossi, Franck Dernoncourt, Mahantesh Halappanavar, Nesreen Ahmed, Yushun Dong, Yue Zhao, and 1 others. 2026. Benchmarking knowledge-extraction attack and defense on retrieval-augmented generation. arXiv preprint arXiv:2602.09319. — [arXiv:2602.09319](https://arxiv.org/abs/2602.09319) find
  24. Utkarsh Sahu, Zhisheng Qi, Mahantesh Halappanavar, Nedim Lipka, Ryan Rossi, Franck Dernoncourt, Yu Zhang, Yao Ma, and Yu Wang. 2026. Knowledge homophily in large language models. In Proceedings of the Nineteenth ACM International Conference on Web Search and Data Mining, pages 1216–1220. find
  25. Parth Sarthi, Salman Abdullah, Aditi Tuli, Shubh Khanna, Anna Goldie, and Christopher D Manning. 2024. Raptor: Recursive abstractive processing for tree-organized retrieval. In The Twelfth International Conference on Learning Representations.
  26. Saptarshi Sengupta, Shuhua Yang, Paul Kwong Yu, Fali Wang, and Suhang Wang. 2025. Biomol-mqa: A multi-modal question answering dataset for llm reasoning over bio-molecular interactions. arXiv preprint arXiv:2506.05766. — [arXiv:2506.05766](https://arxiv.org/abs/2506.05766) find
  27. Minkyoo Song, Jaehan Kim, Myungchul Kang, Hanna Kim, Seungwon Shin, and Sooel Son. 2026. Subgraph reconstruction attacks on graph rag deployments with practical defenses. arXiv preprint arXiv:2602.06495. — [arXiv:2602.06495](https://arxiv.org/abs/2602.06495) find
  28. Bo Wang, Weiyi He, Shenglai Zeng, Zhen Xiang, Yue Xing, Jiliang Tang, and Pengfei He. 2025a. Unveiling privacy risks in llm agent memory. arXiv preprint arXiv:2502.13172.
  29. Fali Wang, Jihai Chen, Shuhua Yang, Runxue Bao, Tianxiang Zhao, Zhiwei Zhang, Xianfeng Tang, Hui Liu, Qi He, and Suhang Wang. 2025b. Generalizing test-time compute-optimal scaling as an optimizable graph. arXiv preprint arXiv:2511.00086. — [arXiv:2511.00086](https://arxiv.org/abs/2511.00086) find
  30. Fali Wang, Chenglin Weng, Xianren Zhang, Siyuan Hong, Hui Liu, and Suhang Wang. 2026a. Graph-skill: Documentation-guided hierarchical retrieval-augmented coding for complex graph reasoning. arXiv preprint arXiv:2603.06620. — [arXiv:2603.06620](https://arxiv.org/abs/2603.06620) find
  31. Weijie Wang, Peizhuo Lv, Yan Wang, Rujie Dai, Guokun Xu, Qiujian Lv, Hangcheng Liu, Weiqing Huang, Wei Dong, and Jiaheng Zhang. 2026b. Making theft useless: Adulteration-based protection of proprietary knowledge graphs in graphrag systems. arXiv preprint arXiv:2601.00274. — [arXiv:2601.00274](https://arxiv.org/abs/2601.00274) find
  32. Yu Wang, Nedim Lipka, Ryan A Rossi, Alexa Siu, Ruiyi Zhang, and Tyler Derr. 2024. Knowledge graph prompting for multi-document question answering. In Proceedings of the AAAI conference on artificial intelligence, volume 38, pages 19206–19214. find
  33. Yuhao Wang, Wenjie Qu, Yanze Jiang, Lichen Liu, Yue Liu, Shengfang Zhai, Yinpeng Dong, and Jiaheng Zhang. 2025c. Silent leaks: Implicit knowledge extraction attack on rag systems through benign queries. find
  34. In ICML 2025 Workshop on Reliable and Responsible Foundation Models. find
  35. Zhishang Xiang, Chuanjie Wu, Qinggang Zhang, Shengyuan Chen, Zijin Hong, Xiao Huang, and Jinsong Su. 2025. When to use graphs in rag: A comprehensive analysis for graph retrieval-augmented generation. arXiv preprint arXiv:2506.05690. — [arXiv:2506.05690](https://arxiv.org/abs/2506.05690) find
  36. Yilin Xiao, Junnan Dong, Chuang Zhou, Su Dong, Qianwen Zhang, Di Yin, Xing Sun, and Xiao Huang. 2025. Graphrag-bench: Challenging domain-specific reasoning for evaluating graph retrieval-augmented generation. arXiv preprint arXiv:2506.02404. — [arXiv:2506.02404](https://arxiv.org/abs/2506.02404) find
  37. Wei Xiong, Hanze Dong, Chenlu Ye, Ziqi Wang, Han Zhong, Heng Ji, Nan Jiang, and Tong Zhang. 2023. Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint. arXiv preprint arXiv:2312.11456. find
  38. Rui Yang, Boming Yang, Xinjie Zhao, Fan Gao, Aosong Feng, Sixun Ouyang, Moritz Blum, Tianwei She, Yuang Jiang, Freddy Lecue, and 1 others. 2025. Graphusion: A rag framework for scientific knowledge graph construction with a global perspective. In Companion Proceedings of the ACM on Web Conference 20… find
  39. Yi Yang, Wen-tau Yih, and Christopher Meek. 2015. Wikiqa: A challenge dataset for open-domain question answering. In Proceedings of the 2015 conference on empirical methods in natural language processing, pages 2013–2018.
  40. Shenglai Zeng, Jiankun Zhang, Pengfei He, Yiding Liu, Yue Xing, Han Xu, Jie Ren, Yi Chang, Shuaiqiang Wang, Dawei Yin, and 1 others. 2024. The good and the bad: Exploring privacy issues in retrieval-augmented generation (rag). In Findings of the Association for Computational Linguistics ACL 2024, pa… find
  41. Delvin Ce Zhang, Suhan Cui, Zhelin Chu, Xianren Zhang, and Dongwon Lee. 2026a. Mever: Multimodal and explainable claim verification with graph-based evidence retrieval. In Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Pape… find
  42. Delvin Ce Zhang and Dongwon Lee. 2025. Correct: Context-and reference-augmented reasoning and prompting for fact-checking. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers… find
  43. Jiahao Zhang. 2024. Graph unlearning with efficient partial retraining. In Companion Proceedings of the ACM Web Conference 2024, pages 1218–1221. find
  44. Jiahao Zhang, Yilong Wang, and Suhang Wang. 2026b. Attack by unlearning: Unlearning-induced adversarial attacks on graph neural networks. arXiv preprint arXiv:2603.18570. — [arXiv:2603.18570](https://arxiv.org/abs/2603.18570) find
  45. Jiahao Zhang, Yilong Wang, Zhiwei Zhang, Xiaorui Liu, and Suhang Wang. 2026c. Unlearning inversion attacks for graph neural networks. In Proceedings of the Nineteenth ACM International Conference on Web Search and Data Mining, pages 934–945. find
  46. Liangliang Zhang, Zhuorui Jiang, Hongliang Chi, Haoyang Chen, Mohammed Elkoumy, Fali Wang, Qiong Wu, Zhengyi Zhou, Shirui Pan, Suhang Wang, and 1 others. 2025a. Diagnosing and addressing pitfalls in kg-rag datasets: Toward more reliable benchmarking. arXiv preprint arXiv:2505.23495. — [arXiv:2505.23495](https://arxiv.org/abs/2505.23495) find
  47. Qinggang Zhang, Shengyuan Chen, Yuanchen Bei, Zheng Yuan, Huachi Zhou, Zijin Hong, Hao Chen, Yilin Xiao, Chuang Zhou, Junnan Dong, and 1 others. 2025b. A survey of graph retrieval-augmented generation for customized large language models. arXiv preprint arXiv:2501.13958.
  48. Pengcheng Zhou, Yinglun Feng, and Zhongliang Yang. 2025a. Privacy-aware rag: Secure and isolated knowledge retrieval. arXiv preprint arXiv:2503.15548. — [arXiv:2503.15548](https://arxiv.org/abs/2503.15548) find
  49. Yingli Zhou, Yaodong Su, Youran Sun, Shu Wang, Taotao Wang, Runyuan He, Yongwei Zhang, Sicong Liang, Xilin Liu, Yuchi Ma, and 1 others. 2025b. In-depth analysis of graph-based rag in a unified framework. arXiv preprint arXiv:2503.04338. — [arXiv:2503.04338](https://arxiv.org/abs/2503.04338) find
  50. Xiangrong Zhu, Yuexiang Xie, Yi Liu, Yaliang Li, and Wei Hu. 2025. Knowledge graph-guided retrieval augmented generation. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers)… find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/yang-2026-query-efficient-agentic-graph-extraction/