Differentially Private Cycle Counting: Local Lower Bounds and Shuffle Estimators

The shuffle model of differential privacy can improve aggregate statistics, but its benefits for graph pattern counting remain unclear. We identify an algebraic parity split for cycles. Let $A$ be the adjacency matrix of an $n$-vertex graph and $W=A^2$ its matrix of length-two walk counts. Even closed-walk counts satisfy $\mathrm{tr}(A^{2m})=\mathrm{tr}(W^m)$, whereas odd counts satisfy $\mathrm{tr}(A^{2m+1})=\mathrm{tr}(W^{m}A)$ and retain one factor of $A$. This distinction motivates our estimators, but does not by itself characterize shuffle amplification. For every fixed odd $k$ and $n^{-1/2}\le \epsilon \le {\epsilon }_0$, with ${\epsilon }_0>0$ a small constant (and $\epsilon \ge \sqrt{\log n/n}$ if $k=3$), we give an unbiased shuffle estimator of $\mathrm{tr}(A^k)$ with dense-graph root mean squared error (RMSE) ${\Theta }_k(n^{k-1}/\epsilon )$. Correcting walks that repeat vertices gives a simple-cycle estimator with $O_k(n^{k-1}/\epsilon )$ RMSE, and the same ${\Theta }_k$ rate when $\epsilon \sqrt{n}\to \infty$; for $C_5$, the rate is $\Theta (n^4/\epsilon )$ throughout this range. We also prove an $\Omega (n^{k-1}/\epsilon )$ lower bound for every fixed $k\ge 3$ in the non-interactive per-edge local model, where each edge has its own pure $\epsilon$-DP channel. For $C_5$, on the dense random graphs that witness this bound and for $\epsilon \ge n^{-1/4}$, suppose the analyzer also receives $W$ with Gaussian noise. Noise of order $\tilde{\Theta }(n/\epsilon )$ per entry is then a threshold: above it the bound still holds, and well below it spectral deflation, which removes the top eigencomponent, beats the bound. With a provably private multi-message release of $W$, deflation reaches RMSE $\tilde{O}(n^{3.5}/\epsilon )$ on these graphs. This $(\epsilon ,\delta )$ shuffle protocol improves on the per-edge lower bound by $\tilde{\Theta }(\sqrt{n})$ on that family, which is not a worst-case separation from the full local model.