Agent-based Substructure Counting under Local Differential Privacy

Recent studies have demonstrated the ability of Large Language Models (LLMs) in processing various graph problems. Substructure counting remains challenging in both scalability and accuracy. Incorporating sensitive edge information into the input prompts also introduces significant privacy risks of exposing the private information of user connections in real-world applications. This paper, for the first time, studies substructure counting for LLMs under edge local differential privacy (LDP) in a multiagent framework. Unlike the Naive approach whose estimation relies entirely on overly dense noisy graphs, the proposed PSC framework decomposes substructure counting into node-level tasks distributed among node agents, and embeds the knowledge of distributed algorithms and DP frameworks in the curator agent and privacy controller, respectively. Thus, we can leverage the local neighboring information and reasoning capabilities of node agents to improve the estimation accuracy. Extensive experiments on 6 real-world datasets validate the effectiveness of PSC framework for substructure counting tasks under ε-edge LDP. Moreover, the non-DP version of PSC also demonstrated superior performance over a single LLM on standard substructure counting tasks. Graph problem: How many triangles among nodes 1-5? Malicious adversaries I'm node1, my neighbors are node 3, node 4 and node 5 I'm node 2, my neighbors are node 1 and node 4 I'm node 5, my neighbors are node 1 and node 3 Safely release query results Untrusted Curator Agent Local Differential Privacy Protection Cannot infer individual neighbor information