  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.
