Counting Subgraphs under Shuffle Differential Privacy

To understand the complex structures and relationships in graph data while safeguarding personal privacy, subgraph counting under differential privacy (DP) has received a lot of attention recently. The problem is particularly important in a distributed setting, where each node holds only its local neighboring information and the analyst is untrusted. In the literature, two DP models are tailored for this scenario, known as local DP and shuffle DP, whereas the latter is equipped with a trusted shuffler that random shuffles the messages before handing them to the analyst. Since the shuffler introduces no additional privacy risk, any local DP protocol automatically satisfies shuffle DP, and the key question is whether shuffle DP can offer any improvement, especially for utility. While positive results have been obtained for a number of basic problems, such as basic counting, frequency estimation, and distinct count, it still remains elusive if this is the case for any graph problem. In this paper, we advance the understanding of this question by presenting new shuffle DP protocols for counting various subgraphs, including triangles, 4-cycles, and 3-hop paths, which improve upon the existing local DP and shuffle DP protocols, both asymptotically and concretely.