Cycle Counting under Local Differential Privacy for Degeneracy-bounded Graphs

We propose an algorithm for counting the number of cycles under local differential privacy for degeneracy-bounded input graphs. Numerous studies have focused on counting the number of triangles under the privacy notion, demonstrating that the expected \(\ell_2\)-error of these algorithms is \(\Omega(n^{1.5})\), where \(n\) is the number of nodes in the graph. When parameterized by the number of cycles of length four (\(C_4\)), the best existing triangle counting algorithm has an error of \(O(n^{1.5} + \sqrt{C_4}) = O(n^2)\). In this paper, we introduce an algorithm with an expected \(\ell_2\)-error of \(O(\delta^{1.5} n^{0.5} + \delta^{0.5} d_{\max}^{0.5} n^{0.5})\), where \(\delta\) is the degeneracy and \(d_{\max}\) is the maximum degree of the graph. For degeneracy-bounded graphs (\(\delta \in \Theta(1)\)) commonly found in practical social networks, our algorithm achieves an expected \(\ell_2\)-error of \(O(d_{\max}^{0.5} n^{0.5}) = O(n)\). Our algorithm's core idea is a precise count of triangles following a preprocessing step that approximately sorts the degree of all nodes. This approach can be extended to approximate the number of cycles of length \(k\), maintaining a similar \(\ell_2\)-error, namely $O(\delta^{(k-2)/2} d_{\max}^{0.5} n^{(k-2)/2} + \delta^{k/2} n^{(k-2)/2})$ or $O(d_{\max}^{0.5} n^{(k-2)/2}) = O(n^{(k-1)/2})$ for degeneracy-bounded graphs.