Elamur Research⌕
☰
home / papers / 2026 / Agent-based Substructure Counting under Local Differential Privacy

Agent-based Substructure Counting under Local Differential Privacy

Paper · 2026 · Yuting Zhang, Kai Wang, Wei Ni et al.

Summary

The paper addresses how to count small graph patterns such as triangles and k-stars with LLMs without exposing private edge information, for example contacts between patients. The authors are the first to frame this as LLM-based substructure counting under ε-edge local differential privacy (LDP). Their multi-agent framework, PSC, never gives the untrusted curator agent the edge list. It receives only the node set and the query. The task is split into node-level subtasks handled by node agents, each of which knows only its own neighbors. A separate privacy controller picks a DP mechanism and its parameters, so privacy does not depend on the LLM following instructions. The pipeline uses randomized response, graph projection to limit sensitivity, and the Laplace mechanism. This avoids the Naive baseline's reliance on an overly dense, lengthy noisy graph. On 6 real-world datasets, PSC cuts relative error by about two orders of magnitude on most tests. A non-DP variant also outperforms a single LLM.

Key points

  • The tasks covered are average degree, triangle counting and k-star counting (2-star, 3-star), all under ε-edge LDP. The design follows earlier two-round edge LDP algorithms by Imola et al.
  • The privacy budget is split three ways:
    • ε₁ goes to randomized response, which builds the noisy graph.
    • ε₂ goes to sensitivity optimization.
    • ε₃ goes to the Laplace-noised reports.
    • Giving too much of the budget to ε₁ increases error.
  • Without projection, global sensitivity for triangles is n − 2. Projection caps the maximum degree at a bound d̂max ≪ n, which shrinks the sensitivity accordingly. The ablation (Table 3) confirms the benefit: on the CU dataset, triangle error is 0.7939 with optimization versus 1.8654 without.
  • As motivation, the authors cite prior work in which plain LLM triangle counting on 20–30-node graphs reached only 7.21% accuracy.
  • The main limitation is LLM token limits, which make triangle counting difficult on graphs with more than 1,000 nodes. Extending the framework to other graph tasks remains an open problem.

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

🎓Shanghai Jiao Tong UniversityShanghai · China149 works · 16,161 citations🔬Data61Sydney · Australia16 works · 2,532 citations🎓UNSW SydneySydney · Australia34 works · 1,509 citations🏛️Commonwealth Scientific and Industrial Research OrganisationCanberra · Australia15 works · 1,898 citations

Also on the byline: Edith Cowan University · Zhejiang Gongshang University.

 Fields, topics and concepts

📚 Shelves 3The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksComputer Vision and Pattern Recognition · 2,869 works

Cite

Cite as Yuting Zhang, Kai Wang, Wei Ni, Ying Zhang and Wenjie Zhang. 2026. Agent-based Substructure Counting under Local Differential Privacy. 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.1032

@inproceedings{zhang2026agent,
  title = {{Agent-based Substructure Counting under Local Differential Privacy}},
  author = {Yuting Zhang, Kai Wang, Wei Ni, Ying Zhang and Wenjie Zhang},
  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.1032},
  url = {https://doi.org/10.18653/v1/2026.acl-long.1032}
}

References

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

  1. Ziwei Chai, Tianjie Zhang, Liang Wu, Kaiqiang Han, Xiaohai Hu, Xuanwen Huang, and Yang Yang. 2025. Graphllm: Boosting graph reasoning ability of large language model. IEEE Transactions on Big Data. find
  2. Nuo Chen, Yuhan Li, Jianheng Tang, and Jia Li. 2024. Graphwiz: An instruction-following language model for graph computational problems. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 353–364. find
  3. Debarati Das, Ishaan Gupta, Jaideep Srivastava, and Dongyeop Kang. 2023. Which modality should i use–text, motif, or image?: Understanding graphs with large language models. arXiv preprint arXiv:2311.09862. find
  4. DeepSeek AI. 2024. DeepSeek News API Documentation. Accessed: 9 June 2024. find
  5. Laxman Dhulipala, Quanquan C Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, and Shangdi Yu. 2022. Differential privacy from locally adjustable graph algorithms: k-core decomposition, low out-degree ordering, and densest subgraphs. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Sc… find
  6. Cynthia Dwork. 2006. Differential privacy. In International colloquium on automata, languages, and programming, pages 1–12. Springer. find
  7. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265–284. Springer. find
  8. Cynthia Dwork, Aaron Roth, and 1 others. 2014. The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407. find
  9. Talya Eden, Quanquan C Liu, Sofya Raskhodnikova, and Adam Smith. 2023. Triangle counting with local edge differential privacy. arXiv preprint arXiv:2305.02263. — [arXiv:2305.02263](https://arxiv.org/abs/2305.02263) find
  10. Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. 2023. Talk like a graph: Encoding graphs for large language models. arXiv preprint arXiv:2310.04560. find
  11. Dawei Gao, Zitao Li, Yuexiang Xie, Weirui Kuang, Liuyi Yao, Bingchen Qian, Zhijian Ma, Yue Cui, Haohao Luo, Shen Li, and 1 others. 2025. Agentscope 1.0: A developer-centric framework for building agentic applications. arXiv preprint arXiv:2508.16279. — [arXiv:2508.16279](https://arxiv.org/abs/2508.16279) find
  12. Yuyao Ge, Shenghua Liu, Baolong Bi, Yiwei Wang, Lingrui Mei, Wenjie Feng, Lizhe Chen, and Xueqi Cheng. 2024. Can graph descriptive order affect solving graph problems with llms? arXiv preprint arXiv:2402.07140.
  13. Jiayan Guo, Lun Du, Hengyu Liu, Mengyu Zhou, Xinyi He, and Shi Han. 2023. Gpt4graph: Can large language models understand graph structured data? an empirical evaluation and benchmarking. arXiv preprint arXiv:2305.15066. find
  14. Yizhang He, Kai Wang, Wenjie Zhang, Xuemin Lin, and Ying Zhang. 2024. Common neighborhood estimation over bipartite graphs under local differential privacy. Proceedings of the ACM on Management of Data, 2(6):1–26. find
  15. Yizhang He, Kai Wang, Wenjie Zhang, Xuemin Lin, Ying Zhang, and Wei Ni. 2025. Robust privacy-preserving triangle counting under edge local differential privacy. Proceedings of the ACM on Management of Data, 3(3):1–26. find
  16. Quentin Hillebrand, Vorapong Suppakitpaisarn, and Tetsuo Shibuya. 2023. Communication cost reduction for subgraph counting under local differential privacy via hash functions. arXiv preprint arXiv:2312.07055. — [arXiv:2312.07055](https://arxiv.org/abs/2312.07055) find
  17. Yuwei Hu, Runlin Lei, Xinyi Huang, Zhewei Wei, and Yongchao Liu. 2024. Scalable and accurate graph reasoning with llm-based multi-agents. arXiv preprint arXiv:2410.05130. — [arXiv:2410.05130](https://arxiv.org/abs/2410.05130) find
  18. Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. 2021. Locally differentially private analysis of graph statistics. In 30th USENIX security symposium (USENIX Security 21), pages 983–1000. find
  19. Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. 2022a. {Communication-Efficient} triangle counting under local differential privacy. In 31st USENIX security symposium (USENIX Security 22), pages 537–554. find
  20. Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. 2022b. Differentially private triangle and 4-cycle counting in the shuffle model. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pages 1505–1519. find
  21. Shunyang Li, Kai Wang, Wenjie Zhang, Xuemin Lin, and Yizhang He. 2025. Efficient bitruss decomposition on gpu. IEEE Transactions on Knowledge and Data Engineering. find
  22. Nelson F Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. 2023. Lost in the middle: How language models use long contexts. arXiv preprint arXiv:2307.03172.
  23. Shang Liu, Yang Cao, Takao Murakami, Jinfei Liu, and Masatoshi Yoshikawa. 2024. Cargo: Crypto-assisted differentially private triangle counting without trusted servers. In 2024 IEEE 40th International Conference on Data Engineering (ICDE), pages 1671–1684. IEEE. find
  24. Yuhan Liu, Suyun Zhao, Yixuan Liu, Dan Zhao, Hong Chen, and Cuiping Li. 2022. Collecting triangle counts with edge relationship local differential privacy. In 2022 IEEE 38th International Conference on Data Engineering (ICDE), pages 2008–2020. IEEE. find
  25. Zihan Luo, Xiran Song, Hong Huang, Jianxun Lian, Chenhao Zhang, Jinqi Jiang, and Xing Xie. 2024. Graphinstruct: Empowering large language models with graph understanding and reasoning capability. arXiv preprint arXiv:2403.04483. — [arXiv:2403.04483](https://arxiv.org/abs/2403.04483) find
  26. Tianzi Lv, Huanzhou Li, Zhangguo Tang, Fangzhou Fu, Jian Cao, and Jian Zhang. 2021. Publishing triangle counting histogram in social networks based on differential privacy. Security and Communication Networks, 2021(1):7206179. find
  27. Ly Nguyen and Yujun Yan. 2024. Evaluating the structural awareness of large language models on graphs: Can they count substructures? find
  28. OpenAI. 2024. Gpt-4o: Introducing gpt-4.1 \| openai. Accessed: 2024-06-10. find
  29. Bryan Perozzi, Bahare Fatemi, Dustin Zelle, Anton Tsitsulin, Mehran Kazemi, Rami Al-Rfou, and Jonathan Halcrow. 2024. Let your graph do the talking: Encoding structured data for llms. arXiv preprint arXiv:2402.05862. — [arXiv:2402.05862](https://arxiv.org/abs/2402.05862) find
  30. Aman Priyanshu, Supriti Vijay, Ayush Kumar, Rakshit Naidu, and Fatemehsadat Mireshghallah. 2023. Are chatbots ready for privacy-sensitive applications? an investigation into input regurgitation and prompt-induced sanitization. arXiv preprint arXiv:2305.15008. — [arXiv:2305.15008](https://arxiv.org/abs/2305.15008) find
  31. Zhan Qin, Ting Yu, Yin Yang, Issa Khalil, Xiaokui Xiao, and Kui Ren. 2017. Generating synthetic decentralized social graphs with local differential privacy. In Proceedings of the 2017 ACM SIGSAC conference on computer and communications security, pages 425–438. find
  32. Jianheng Tang, Qifan Zhang, Yuhan Li, and J Grapharena Li. 2025. Benchmarking large language models on graph computational problems. In International Conference on Learning Representations. find
  33. Xinyu Tang, Richard Shin, Huseyin A Inan, Andre Manoel, Fatemehsadat Mireshghallah, Zinan Lin, Sivakanth Gopi, Janardhan Kulkarni, and Robert Sim. 2023. Privacy-preserving in-context learning with differentially private few-shot generation. arXiv preprint arXiv:2309.11765. — [arXiv:2309.11765](https://arxiv.org/abs/2309.11765) find
  34. Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. 2023. Can language models solve graph problems in natural language? Advances in Neural Information Processing Systems, 36:30840–30861. find
  35. Haozhe Yin, Kai Wang, Wenjie Zhang, Ying Zhang, Ruijia Wu, and Xuemin Lin. 2024. Efficient computation of hyper-triangles on hypergraphs. Proc. VLDB Endow., 18(3):729–742. find
  36. Zike Yuan, Ming Liu, Hui Wang, and Bing Qin. 2024. Gracore: Benchmarking graph comprehension and complex reasoning in large language models. arXiv preprint arXiv:2407.02936.
  37. Jiawei Zhang. 2023. Graph-toolformer: To empower llms with graph reasoning ability via prompt augmented by chatgpt. arXiv preprint arXiv:2304.11116. find
  38. Yuting Zhang, Wei Ni, Kai Wang, Yizhang He, and Conggai Li. 2025. Truss decomposition under edge local differential privacy. In 2025 IEEE 41st International Conference on Data Engineering (ICDE), pages 2670–2683. IEEE. find
  39. Jianan Zhao, Le Zhuo, Yikang Shen, Meng Qu, Kai Liu, Michael Bronstein, Zhaocheng Zhu, and Jian Tang. 2023. Graphtext: Graph reasoning in text space. arXiv preprint arXiv:2310.01089. — [arXiv:2310.01089](https://arxiv.org/abs/2310.01089) find
  40. Andy Zhou, Kai Yan, Michal Shlapentokh-Rothman, Haohan Wang, and Yu-Xiong Wang. 2023. Language agent tree search unifies reasoning acting and planning in language models. arXiv preprint arXiv:2310.04406. find
  41. Stanley L Warner. 1965. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63–69. find
  42. Yanbin Wei, Shuai Fu, Weisen Jiang, Zejian Zhang, Zhixiong Zeng, Qi Wu, James Kwok, and Yu Zhang. 2024. Gita: Graph to visual and textual integration for vision-language graph reasoning. Advances in Neural Information Processing Systems, 37:44–72. find
  43. An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, and 1 others. 2025. Qwen3 technical report. arXiv preprint arXiv:2505.09388.
  44. Qingqing Ye, Haibo Hu, Man Ho Au, Xiaofeng Meng, and Xiaokui Xiao. 2020a. Lf-gdpr: A framework for estimating graph metrics with local differential privacy. IEEE Transactions on Knowledge and Data Engineering, 34(10):4905–4920. find
  45. Qingqing Ye, Haibo Hu, Man Ho Au, Xiaofeng Meng, and Xiaokui Xiao. 2020b. Towards locally differentially private generic graph metric estimation. In 2020 IEEE 36th International Conference on Data Engineering (ICDE), pages 1922–1925. IEEE. find
  46. Haozhe Yin, Kai Wang, Wenjie Zhang, Yizhang He, Ying Zhang, and Xuemin Lin. 2025. Motif counting in complex networks: A comprehensive survey. arXiv preprint arXiv:2503.19573. — [arXiv:2503.19573](https://arxiv.org/abs/2503.19573) find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/zhang-2026-agent-based-substructure-counting-under/