# Differentially Private Triangle and 4-Cycle Counting in the Shuffle Model

arXiv: https://arxiv.org/abs/2205.01429 · HTML: https://mlsanity.com/paper/2205.01429/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 May 2022.

## Built on by (most cited first, 5 of 5)

- [Deep Efficient Private Neighbor Generation for Subgraph Federated Learning](https://mlsanity.com/paper/2401.04336/) (2024)
- [Communication Cost Reduction for Subgraph Counting under Local Differential Privacy via Hash Functions](https://mlsanity.com/paper/2312.07055/) (2023)
- [HoGS: Homophily-Oriented Graph Synthesis for Local Differentially Private GNN Training](https://mlsanity.com/paper/2602.08762/) (2026)
- [Are Large Language Models Suitable for Graph Computation? Progress and Prospects](https://mlsanity.com/paper/2606.06865/) (2026)
- [Differentially Private Range Subgraph Counting](https://mlsanity.com/paper/2606.08179/) (2026)

## Abstract (arXiv)

Subgraph counting is fundamental for analyzing connection patterns or clustering tendencies in graph data. Recent studies have applied LDP (Local Differential Privacy) to subgraph counting to protect user privacy even against a data collector in social networks. However, existing local algorithms suffer from extremely large estimation errors or assume multi-round interaction between users and the data collector, which requires a lot of user effort and synchronization. In this paper, we focus on a one-round of interaction and propose accurate subgraph counting algorithms by introducing a recently studied shuffle model. We first propose a basic technique called wedge shuffling to send wedge information, the main component of several subgraphs, with small noise. Then we apply our wedge shuffling to counting triangles and 4-cycles -- basic subgraphs for analyzing clustering tendencies -- with several additional techniques. We also show upper bounds on the estimation error for each algorithm. We show through comprehensive experiments that our one-round shuffle algorithms significantly outperform the one-round local algorithms in terms of accuracy and achieve small estimation errors with a reasonable privacy budget, e.g., smaller than 1 in edge DP.