Cycle Counting Under Local Differential Privacy for Degeneracy-Bounded Graphs

Hillebrand, Quentin; Suppakitpaisarn, Vorapong; Shibuya, Tetsuo

doi:10.4230/LIPIcs.STACS.2025.49

Cycle Counting Under Local Differential Privacy for Degeneracy-Bounded Graphs

Quentin Hillebrand

The University of Tokyo, Japan Vorapong Suppakitpaisarn

The University of Tokyo, Japan Tetsuo Shibuya

The University of Tokyo, Japan

Abstract

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.

Keywords and phrases:

Differential privacy, triangle counting, degeneracy, arboricity, graph theory, parameterized accuracy

Funding:

Quentin Hillebrand: partially supported by KAKENHI Grant 20H05965, and by JST SPRING Grant Number JPMJSP2108.

Vorapong Suppakitpaisarn: partially supported by KAKENHI Grant 21H05845 and 23H04377.

Tetsuo Shibuya: partially supported by KAKENHI Grant 20H05967, 21H05052, and 23H03345.

Copyright and License:

2012 ACM Subject Classification:

Security and privacy

\rightarrow

Privacy-preserving protocols ; Theory of computation

\rightarrow

Graph algorithms analysis

Acknowledgements:

The authors wish to express their thanks to the anonymous reviewers whose valuable feedback greatly enhanced the quality of this paper.

DOI:

10.4230/LIPIcs.STACS.2025.49

Event:

42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Editors:

Olaf Beyersdorff, Michał Pilipczuk, Elaine Pimentel, and Nguyễn Kim Thắng

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

In recent years, differential privacy [13, 15] has become the gold standard for providing strong privacy guarantees while enabling meaningful data analysis. Differential privacy ensures that the output of a computation does not significantly change when any single individual’s data is modified, thus safeguarding individual privacy. While much of the initial work in differential privacy focused on traditional tabular data [14, 26], there is increasing interest in extending these privacy guarantees to graph data [31, 35], which presents its own unique set of challenges.

Differential privacy has evolved into numerous variants to accommodate different scenarios, as detailed in [8]. Of particular interest to us is the concept of local differential privacy [7, 17]. This variant is unique in that it does not rely on the assumption of a trusted central server. Instead, users must obfuscate their private data before sharing it with an untrusted computing entity. In the context of graph data, the most commonly adopted notion is edge local differential privacy [29], where the sensitive information of each user pertains to their connections with others.

A widely used obfuscation method is randomized response [33, 32]. In this approach, users invert each bit of their adjacency vector with a certain probability. The server then collects this distorted information to construct an obfuscated graph. Although it is possible to publish various graph statistics from the obfuscated graph, the resulting information tends to be imprecise. Algorithms specifically designed to publish particular statistics typically yield more accurate and useful graph information.

Table 1: Upper and lower bounds of the expected

\ell_{2}

-error for triangle and

k

-cycle counting under the local differential privacy. “Interactive” refers to a scenario in which multiple rounds of communication between the server and the clients are permitted.

	Upper Bound	Lower Bound
Triangle	$O(n^{2})$ ([22], general graphs)	$\Omega(n^{1.5})$ (non-interactive) [24]
	$O(d_{\mathrm{max}}^{1.5}n^{0.5})$ ([16], general graphs)	$\Omega(n^{1.5})$ (interactive) [16]
	$O(d_{\mathrm{max}}^{0.5}n^{0.5})$ (this work, degeneracy-bounded graph)	$\Omega(n^{2})$ (non-interactive) [16]
Odd length	$O\left(n^{k-1}\right)$ (folklore, general graphs)
cycles $C_{k}$	$O\left(n^{(k-1)/2}\right)$ (this work, degeneracy-bounded graph)

One graph statistic frequently considered by researchers in local differential privacy is the number of subgraphs [22, 20]. Specifically, many studies have focused on the publication of triangle counts [22, 23, 20, 16]. Theoretical analysis results on the $\ell_{2}$ -error are summarized in Table 1. Unfortunately, to date, when $n$ is the number of nodes and $d_{\max}$ is the maximum degree of the input graphs, the best algorithm has an expected $\ell_{2}$ -error of $O(n^{2})$ or $O(d_{\max}^{1.5}n^{0.5})$ . We believe that this error is too large for many applications and should be improved. On the other hand, it has been shown that for all locally differentially private algorithms, there exists a class of graphs where the $\ell_{2}$ -error is $\Omega(n^{1.5})$ [16]. This lower bound implies that the expected $\ell_{2}$ -error cannot be significantly improved.

1.1 Our Contribution

This motivates us to consider a specific class of graphs. In this paper, we specifically focus on graphs with bounded degeneracy, as most social graphs exhibit degeneracy values that are substantially smaller than both the number of vertices and the maximum degree. The table in the Appendix of [12] provides statistics on a diverse range of graphs, detailing the number of nodes, degeneracy, and maximum degree. As shown in the paper, for sufficiently large graphs, degeneracy is consistently at least an order of magnitude smaller than the maximum degree, and in some instances, several orders of magnitude smaller.

Additionally, several synthetic graph models commonly considered realistic naturally produce graphs with low degeneracy. Examples include preferential attachment graphs [1] and bounded expansion graphs [27].

Degeneracy is particularly significant in parameterizing the complexity of subgraph counting algorithms, as demonstrated in [6, 2, 5]. Given the relationship between computational complexity and estimation error in triangle counting algorithms, degeneracy is an important parameter for characterizing accuracy.

Let the graph degeneracy be $\delta$ . We propose a locally differentially private algorithm with an expected $\ell_{2}$ -error of $O\left(\delta^{1.5}n^{0.5}+\delta^{0.5}d_{\max}^{0.5}n^{0.5}\right)$ . When the graph degeneracy is bounded ( $\delta=O(1)$ ), the expected $\ell_{2}$ -error becomes $O(d_{\max}^{0.5}n^{0.5})=O(n)$ . This result implies that our expected error for the degeneracy-bounded graphs can be smaller than the lower bound for general graphs.

We also extend our results to count the number of cycles with odd lengths in degeneracy-bounded graphs. To our knowledge, there are only two local differentially private algorithms proposed for counting subgraphs of more than three nodes. The first algorithm [24] is designed to count the number of four-length cycles but operates within the shuffle model, which is weaker than the original local differential privacy model. The second algorithm counts the number of walks of length $k$ [3]. This field has limited work due to the significant noise introduced to ensure user privacy, which accumulates as the subgraph size increases. This accumulation results in unacceptable errors for differential privacy in larger subgraphs. For instance, while the expected $\ell_{2}$ -error from triangle counting algorithms based on randomized response is $O(n^{2})$ [24], the expected $\ell_{2}$ -error for similar algorithms estimating the number of $C_{k}$ is as high as $O(n^{k-1})$ . In other words, the error increases by a factor of $n$ with each increment in cycle length.

In this work, we propose an algorithm that significantly reduces the expected $\ell_{2}$ -error to $O(n^{(k-1)/2})$ in degeneracy-bounded graphs. We believe that this error is much smaller than the actual number of cycles in most graphs. Consequently, our algorithm is the first to publish a meaningful number of large cycles under local differential privacy.

1.2 Technical Overview

In this section, we provide an overview of the technical concepts behind our triangle counting algorithm. The algorithm for counting odd-length cycles, for $k\geq 5$ , extends these ideas but requires a more intricate and detailed analysis.

Let the input graph be $G=(V=\{\nu_{1},\dots,\nu_{n}\},E)$ . In prior work [22], they apply a randomized response mechanism that flips each bit in the adjacency matrix with a certain probability. Let the resulting graph after applying the randomized response be $G^{\prime}=(V,E^{\prime})$ . In the local differential privacy setting, each node $\nu_{i}$ knows whether it is connected to another node $\nu_{j}$ (where $\nu_{j}\neq\nu_{i}$ ) if $\{\nu_{i},\nu_{j}\}\in E$ . For the triangle counting method, node $\nu_{i}$ considers $(\nu_{i},\nu_{j},\nu_{\kappa})$ as a triangle if $\{\nu_{i},\nu_{j}\}\in E$ , $\{\nu_{i},\nu_{\kappa}\}\in E$ , and $\{\nu_{j},\nu_{\kappa}\}\in E^{\prime}$ . Define $e_{i,j,\kappa}=1$ if node $\nu_{i}$ considers $(\nu_{i},\nu_{j},\nu_{\kappa})$ as a triangle, otherwise set $e_{i,j,\kappa}=0$ . Define $S_{i}=\{(j,\kappa):\{\nu_{i},\nu_{j}\},\{\nu_{i},\nu_{\kappa}\}\in E\text{ and% }j<\kappa\}$ . The estimated number of triangles for node $\nu_{i}$ , reported by the user, is $\tilde{t}_{i}=\sum\limits_{(j,\kappa)\in S_{i}}e_{i,j,\kappa}$ . The total estimated number of triangles in the graph is then $\tilde{f}_{\Delta}(G)=\frac{1}{3}\sum_{i}\tilde{t}_{i}=\frac{1}{3}\sum_{i}\sum% _{(j,\kappa)\in S_{i}}e_{i,j,\kappa},$ where dividing by three corrects for the fact that each triangle is counted once by each of the three users forming it (i.e., triple-counted), ensuring each triangle is counted only once.

The $\ell_{2}$ -error of the estimated triangle count $\tilde{f}_{\Delta}(G)$ mostly arises from the variance in the estimation. A significant portion of this variance comes from the covariance between pairs of variables in the summation $\frac{1}{3}\sum\limits_{i}\sum\limits_{(j,\kappa)\in S_{i}}e_{i,j,\kappa}$ . Two variables, $e_{i,j,\kappa}$ and $e_{i^{\prime},j^{\prime},\kappa^{\prime}}$ , are dependent if $(j,\kappa)=(j^{\prime},\kappa^{\prime})$ . The number of dependent pairs in the counting process is equivalent to the number of tuples $(\nu_{i},\nu_{j},\nu_{i^{\prime}},\nu_{\kappa})$ such that $(j,\kappa)\in S_{i}\cap S_{i^{\prime}}$ , which corresponds to the number of 4-cycles in the input graph $G$ . Therefore, the squared $\ell_{2}$ -error is approximately proportional to the number of 4-cycles in the graph, which is $O(n^{4})$ .

Let us assume that the indices of all users are predetermined and publicly known before the counting process begins. Define $S^{\prime}_{i}=\{(j,\kappa):\{\nu_{i},\nu_{j}\},\{\nu_{i},\nu_{\kappa}\}\in E% \text{ and }j<i<\kappa\}$ . If node $i$ only considers the pairs $(j,\kappa)$ within $S^{\prime}_{i}$ , then each triangle is counted exactly once. The estimated number of triangles, $\hat{f}_{\Delta}(G)$ , can be calculated as $\hat{f}_{\Delta}(G)=\sum_{i}\hat{t}_{i}$ , where $\hat{t}_{i}=\sum\limits_{(j,\kappa)\in S^{\prime}_{i}}e_{i,j,\kappa}$ . In this counting method, the number of dependent variable pairs is at most the number of 4-cycles that contain the three nodes $\nu_{i},\nu_{j},\nu_{\kappa}$ with $j<i<\kappa$ .

Let $\delta$ represent the degeneracy of the input graph $G$ , and for each $\nu\in V$ , let $d(\nu)$ denote the degree of $\nu$ . Assume that the degrees of all nodes are publicly known, and the nodes are indexed in non-decreasing order of their degree, i.e., if $i>j$ , then $d(\nu_{i})\leq d(\nu_{j})$ . Referring to the bound established by Chiba and Nishizeki [6], which states that $\sum\limits_{(\nu_{i},\nu_{j})\in E}\min(d_{i},d_{j})\leq O(\delta\cdot|E|)$ , we demonstrate in this paper that the number of such cycles is $O(\delta^{3}n)$ . Consequently, the squared $\ell_{2}$ -error is reduced from $O(n^{4})$ in previous work to $O(\delta^{3}n)$ .

However, we cannot assume that the degrees of all nodes are publicly known, as this information is sensitive. To address this issue, we use local Laplacian queries, allowing each user to publish a noisy version of their degree. Let the noisy degree of $\nu\in V$ be denoted as $\tilde{d}(\nu)$ . We then assign indices to users based on these noisy degrees, such that if $i>j$ , then $\tilde{d}(\nu_{i})\leq\tilde{d}(\nu_{j})$ . Afterward, we run the protocol described in the previous paragraph. We show that even with noisy degrees, the expected number of such cycles remains bounded by $O(\delta^{3}n)$ .

In summary, our mechanism involves two steps. First, users publish their noisy degrees using the local Laplacian mechanism, and the server assigns indexes based on these noisy values. In the second step, using the results of randomized response, each user $\nu_{i}$ estimates the number of triangles $(\nu_{i},\nu_{j},\nu_{\kappa})$ where $j<i<\kappa$ . This method significantly reduces the number of dependent triangle pairs in degeneracy-bounded graphs, which in turn lowers the variance of the estimation.

1.3 Related Works

The field of graph data mining under local differential privacy is relatively new. In contrast, differential privacy has been studied for many years by various researchers, including works like [18, 28]. According to [22], local differential privacy typically only hides edges or relationships, except in special cases like [36]. Differential privacy, on the other hand, can hide whether an individual or node is part of a social network, as shown in [19, 30]. Therefore, while both edge and node differential privacy exist, node differential privacy does not apply in the context of local differential privacy.

Recent works have proposed methods to estimate the densest subgraph, $k$ -core decomposition, and degeneracy under local differential privacy [10, 9, 11]. However, since we are focused on estimating different graph statistics in graphs, we do not use or extend the ideas from these works. Instead, the estimation of degeneracy can be used to approximate the $\ell_{2}$ -error of our algorithm.

2 Preliminaries

2.1 Notations

For $V=\{\nu_{1},\ldots,\nu_{n}\}$ a set of vertices and $E\subseteq V^{2}$ a set of edges, we denote by $G=(V,E)$ the graph on $V$ . We consider simple undirected graphs, meaning that for $\nu,\nu^{\prime}\in V$ , $(\nu,\nu)\not\in E$ and $(\nu,\nu^{\prime})\in E\implies(\nu^{\prime},\nu)\in E$ . We denote by $n=|V|$ the size of the graph and $m=|E|$ its number of edges.

For each $i\in[1,n]$ , we introduce $a_{i}=[a_{i,1},\ldots,a_{i,n}]$ , the adjacency list of user $\nu_{i}$ , where for any $j\in[1,n]$ , $a_{i,j}=1$ if the edge $(\nu_{i},\nu_{j})$ is in $E$ and $a_{i,j}=0$ otherwise. Additionally, we introduce $d_{i}$ , the degree of node $\nu_{i}$ , which corresponds to the number of edges incident to $\nu_{i}$ .

We call a path of length $k\in\mathbb{N}$ , denoted $P_{k}$ , any tuple $(\nu_{l_{1}},\ldots,\nu_{l_{k}})$ such that, for all $i\in[1,k]$ , $(\nu_{l_{i}},\nu_{l_{i+1}})\in E$ , and, for all $i\neq j$ , $\nu_{l_{i}}\neq\nu_{l_{j}}$ . We also use $\#P_{k}(G)$ to refer to the number of paths of length $k$ in $G$ . Similarly, a cycle of length $k\in\mathbb{N}$ , or $C_{k}$ , is a tuple $(\nu_{l_{1}},\ldots,\nu_{l_{k}})$ that forms a path and satisfies $(\nu_{l_{k}},\nu_{l_{1}})\in E$ . We will also use $\#C_{k}(G)$ to refer to the number of cycles of length $k$ in $G$ .

2.2 Edge Local Differential Privacy

We say that two adjacency lists $a$ and $a^{\prime}$ are neighboring if they differ by one bit, i.e. if we can go from one to the other by adding or removing an edge to node $\nu_{i}$ . If $a^{\prime}$ is a neighbor of $a$ , we write that $a\sim a^{\prime}$ . The notion of edge local differential privacy is as follows:

Definition 1 ( $\varepsilon$ -edge local differentially private query).

Let $\varepsilon>0$ . A randomized algorithm $\mathcal{R}$ is a $\varepsilon$ -edge local differentially private query on the node $\nu_{i}$ if, for all neighboring bit strings $a\sim a^{\prime}$ , and for all $S$ , it holds that

\mathbb{P}\left[\mathcal{R}(a)\in S\right]\leq e^{\varepsilon}\mathbb{P}\left[% \mathcal{R}(a^{\prime})\in S\right].

Definition 2 ( $\varepsilon$ -edge local differentially private algorithm [29]).

Let $\mathcal{A}$ be an algorithm that generates multiple randomized queries for each user, has each user apply these queries to their adjacency vector, and then estimates some graph statistics based on the results. We say $\mathcal{A}$ is an $\varepsilon$ -edge local differentially private algorithm if, for all users $\nu_{i}$ and for all possible sets of queries $\mathcal{R}_{1},\dots,\mathcal{R}_{k}$ inquired to $\nu_{i}$ (where for each $1\leq j\leq k$ , $\mathcal{R}_{j}$ is an $\varepsilon_{j}$ -edge local differentially private query), it holds that $\varepsilon_{1}+\cdots+\varepsilon_{k}\leq\varepsilon$ .

2.3 Laplacian Query and Restricted Sensitivity

Next, we introduce queries that are $\varepsilon$ -edge local differentially private. We first consider a query which aims to give an estimate of a real number statistics of the adjacency vector.

Definition 3 (Edge local Laplacian query [21]).

For a function $f:\{0,1\}^{n}\rightarrow\mathbb{R}$ on adjacency lists, and $a\sim a^{\prime}$ denoting neighboring adjacency lists, the global sensitivity of $f$ is defined as $\Delta_{f}=\max\limits_{a\sim a^{\prime}}|f(a)-f(a^{\prime})|.$ For $\varepsilon>0$ , the query that outputs $f(a)+\textsc{Lap}(\Delta_{f}/\varepsilon)$ is $\varepsilon$ -edge local differentially private, where $\textsc{Lap}(b)$ represents noise drawn from the Laplacian distribution with parameter $b$ .

Global sensitivity in Definition 3 is designed to handle the worst-case scenario, which can lead to large amounts of noise being added to the data when using the Laplacian mechanism. However, if the data is known to belong to a specific set, restricted sensitivity allows us to adjust the noise according to the sensitivity within that set, resulting in more tailored and potentially lower noise levels.

Definition 4 (Restricted sensitivity (Definition 8 of [4])).

Let $a=(a_{1},\dots,a_{n}),a^{\prime}=(a^{\prime}_{1},\dots,a^{\prime}_{n})\in\{0,1% \}^{n}$ and $d(a,a^{\prime})$ be the Hamming distance between $a$ and $a^{\prime}$ . The restricted sensitivity of $f$ over a set of possible output $\mathcal{H}$ is

RS_{f}(\mathcal{H})=\max\limits_{a,a^{\prime}\in\mathcal{H}}\left(\frac{|f(a)-% f(a^{\prime})|}{d(a,a^{\prime})}\right).

We can use restricted sensitivity to publish data even if it is not initially in the set. To do this, we first need to define a projection method to map the data to the set. In this work, we will consider $\mathcal{H}_{d}$ , the class of adjacency list with a maximum degree of $d$ , for calculating restricted sensitivity. We assume that the order of all nodes is fixed, and if a node $\nu_{i}$ is adjacent to more than $d$ nodes, we retain only the first $d$ nodes according to this order. The map can be considered as an operation on each adjacency vector $a_{i}$ . We denote the mapping result on $a_{i}$ as $\mu_{d}(a_{i})$ .

Definition 5 (Edge local Laplacian query with restricted sensitivity on $\mathcal{H}_{d}$ [4]).

For any $f$ queried to a user $i$ , the query that answers $f(\mu(a_{i}))+\textsc{Lap}(3\cdot RS_{f}(\mathcal{H}_{d})/\varepsilon)$ is called edge local Laplacian query with restricted sensitivity on $\mathcal{H}_{d}$ , and provides $\varepsilon$ -edge local differential privacy.

2.4 Unbiased Randomized Response

In this subsection, we consider the randomized response query, which aims to publish an obfuscated adjacency vector.

Definition 6 (Randomized response query [33, 32]).

For $\varepsilon>0$ , the randomized response mechanism takes an adjacency list $a=(a_{1},\dots,a_{n})$ as input and outputs an obfuscated list $\tilde{a}=(\tilde{a}_{1},\dots,\tilde{a}_{n})$ . For $i$ , the probability that $\tilde{a}_{i}$ is set to 1 is given by:

\mathbb{P}\left[\textsc{RR}(\tilde{a}_{i})=1\right]=\begin{cases}\frac{e^{% \varepsilon}}{1+e^{\varepsilon}}&\text{if }a_{i}=1\\ \frac{1}{1+e^{\varepsilon}}&\text{if }a_{i}=0.\end{cases}

With this definition, randomized response provides $\varepsilon$ -edge local differential privacy.

We can construct a graph $\tilde{G}$ based on the collection of obfuscated adjacency vectors obtained from all users. Using the statistics of the obfuscated graph $\tilde{G}$ , we can then publish various information, including the number of subgraphs [34, 22, 23, 20]. However, randomized response produces biased results, making it less suitable for counting queries. This bias can be fixed by the subsequent definition.

Definition 7 (Unbiased randomized response query [16]).

Let $\varepsilon>0$ and $\tilde{a}_{i}$ be the adjacency vector published through randomized response with budget $\varepsilon$ by user $\nu_{i}$ . Then, for all $(i,j)\in[1,n]^{2}$ ,

\hat{a}_{i,j}=\frac{e^{\varepsilon}+1}{e^{\varepsilon}-1}\tilde{a}_{i,j}-\frac% {1}{e^{\varepsilon}-1}

is an unbiased estimator of $a_{i,j}$ . Additionally, for $(i,j)\neq(i^{\prime},j^{\prime})$ , $\hat{a}_{i,j}$ is independent of $\hat{a}_{i^{\prime},j^{\prime}}$ , and $\text{Var}\left(\hat{a}_{i,j}\right)=\frac{e^{\varepsilon}}{(e^{\varepsilon}-1% )^{2}}$ . We refer to a query that publishes $\hat{a}_{i}$ as the unbiased randomized response query. This query is $\varepsilon$ -edge locally differentially private.

We can use the results from the unbiased randomized response query to calculate the number of subgraphs. For example, without privacy constraints, the number of triangles can be calculated as $\sum\limits_{i<j<k}a_{i,j}\cdot a_{j,k}\cdot a_{k,i}$ . To privately estimate the number of triangles, we use $\sum\limits_{i<j<k}\hat{a}_{i,j}\cdot\hat{a}_{j,k}\cdot\hat{a}_{k,i}$ . It is theoretically shown in [16] that the estimator $\sum\limits_{i<j<k}\hat{a}_{i,j}\cdot\hat{a}_{j,k}\cdot\hat{a}_{k,i}$ has a smaller $\ell_{2}$ -error compared to the estimator obtained from the randomized response query, $\sum\limits_{i<j<k}\tilde{a}_{i,j}\cdot\tilde{a}_{j,k}\cdot\tilde{a}_{k,i}$ .

2.5 Graph Arboricity and Degeneracy

Graph arboricity and degeneracy can be defined as follows:

Definition 8 (Arboricity).

The arboricity of a graph $G$ is the minimal number $\alpha(G)$ such that the edges of $G$ can be partitioned into $\alpha(G)$ forests.

Definition 9 (Degeneracy).

The degeneracy of a graph $G$ is the smallest number $\delta(G)$ such that any subgraph of $G$ , contains at least one node with induced degree at most $\delta(G)$ .

We observe that the variable $\delta$ is frequently used as a privacy parameter in differential privacy. However, since we do not consider that parameter in this paper, we choose to use $\delta$ to represent degeneracy, which is also a common convention. When the context is clear, we will drop the $G$ of the notation and simply write $\alpha$ and $\delta$ . The two quantities are linked by the following theorem.

Theorem 10 (equation 3 and lemma 2.2 of [37]).

In any graph $G$ , degeneracy and arboricity satisfy $\alpha\leq\delta\leq 2\alpha-1.$

The arboricity has previously been used outside of the differential private community to bound some graph statistics. A folklore useful result is that the number of edges in a graph is smaller than $\delta n$ . Another well known result is as follows:

Theorem 11 (Chiba-Nishizeki Bound [6]).

With $m=|E|$ and $d_{i}$ the degree of node $\nu_{i}$ , then

\sum\limits_{(\nu_{i},\nu_{j})\in E}\min{(d_{i},d_{j})}\leq m\alpha.

3 Node-Reordered Graphs and Their Properties

The first step of our mechanism is to order the vertices based on their estimated degree. The algorithm for this step is shown in Algorithm 1. At Line 2 of the algorithm, we privately publish the estimated degree. Under edge local differential privacy, the global sensitivity of the degree is 1. Therefore, we can use the Laplacian query (Definition 3) with noise scaled to $1/\varepsilon_{0}$ to publish the degree, where $\varepsilon_{0}$ is the privacy budget allocated to this step. We denote the estimated degree as $\tilde{d}_{i}=d_{i}+\text{Lap}\left(1/\varepsilon_{0}\right)$ .

Algorithm 1 Calculate a low degree ordering of a graph with respect to the estimated degree.

After publishing the estimated degrees, in Line 3, we assign an order $\phi$ to the nodes based on their degrees, which we refer to as a low degree ordering. For $G=(\{\nu_{1},\dots,\nu_{n}\},E)$ , we denote the reordered graph as $G^{\phi}=(V^{\phi},E^{\phi})$ , where $V^{\phi}=\{\eta_{i}\mid i\in[1,n]\}$ and $\nu_{i}=\eta_{\phi(i)}$ for all $i$ . The edge set $E^{\phi}$ is defined as $\{(\eta_{\phi(i)},\eta_{\phi(j)})\mid(\nu_{i},\nu_{j})\in E\}$ . We note that $G$ and $G^{\phi}$ are isomorphic, and thus have the same number of subgraphs. We denote by $d_{i}(G^{\phi})$ the degree of $\eta_{i}$ in $G^{\phi}$ and $d_{i}^{-}(G^{\phi})$ the number of neighbors of node $\eta_{i}$ in the set $\{\eta_{1},\dots,\eta_{i-1}\}$ .

Table 2: List of subgraphs analyzed in Section 3, including their representations and bounds on their counts in the graph produced by Algorithm 1. Oriented edges indicate directionality, with an arrow from

\nu_{j}

to

\nu_{i}

signifying that

j>i

. The bound on

S_{2}^{*}

aligns with the bound on

S_{2}

presented in [6], but it constitutes a distinct contribution as it is established for imperfectly ordered graphs. In contrast, the result on

C_{2k}^{*}

is entirely novel to this work and serves as the primary result of our proof.

Symbol	$S_{2}^{*}$	$P_{k}$	$C_{k}$	$C_{2k}^{*}$
Representation
Bound	$\displaystyle\mathcal{O}\left(\delta^{2}n\right)$	$\displaystyle\mathcal{O}\left(\delta^{\lceil\frac{k}{2}\rceil}n^{\lfloor\frac{% k}{2}\rfloor+1}\right)$	$\displaystyle\mathcal{O}\left(\delta^{\lceil\frac{k}{2}\rceil}n^{\lfloor\frac{% k}{2}\rfloor}\right)$ [25]	$\displaystyle\mathcal{O}\left(\delta^{k+1}n^{k-1}\right)$

In the remainder of this section, we analyze the properties of graphs produced by the reordering. Specifically, our focus is on bounding the frequency of certain substructures within the reordered graph. A summary of the results from this section is provided in Table 2.

Definition 12 (low star).

For $k\in\mathbb{N}^{*}$ , a low- $k$ -star is a subgraph consisting of a central node and $k$ neighboring nodes, where at least one of the neighboring nodes has an index smaller than that of the central node. We denote by $S_{k}^{*}(G)$ the number of such subgraphs contained in a graph $G$ .

Theorem 13.

$\mathbb{E}\left[S_{2}^{*}(G^{\phi})\right]\leq\mathcal{O}\left(\delta^{2}n\right)$ .

Proof.

Let $\mathcal{N}_{i}(G^{\phi})$ be the set of neighbors of $\eta_{i}$ in $G^{\phi}$ . We have that:

	$\displaystyle S_{2}^{*}(G^{\phi})$	$\displaystyle=\sum_{i=1}^{n}d_{i}^{-}(G^{\phi})(d_{i}(G^{\phi})-1)\leq\sum_{i=% 1}^{n}d_{i}(G^{\phi})\times d_{i}^{-}(G^{\phi})=\sum_{i=1}^{n}d_{i}(G^{\phi})% \sum_{\eta_{j}\in\mathcal{N}_{i}(G^{\phi})}\mathbbm{1}_{j<i}$
		$\displaystyle=\sum_{(\eta_{i},\eta_{j})\in E^{\phi}}d_{\max(i,j)}(G^{\phi})$

Let $\tau_{i}$ denote the noise added to the estimated degree of user $i$ . For each edge $(\eta_{i},\eta_{j})$ , their ranks can only be exchanged if the sum of the errors in both degree estimations exceeds the gap between the two degrees. Therefore, the quantity $d_{\max(i,j)}(G^{\phi})$ satisfies

d_{\max(i,j)}(G^{\phi})\leq\min(d_{i},d_{j})+|\tau_{i}|+|\tau_{j}|.

Using this inequality, we can rewrite the count of $S_{2}^{*}(G^{\phi})$ as

S_{2}^{*}(G^{\phi})\leq\sum\limits_{(\eta_{i},\eta_{j})\in E^{\phi}}\min{(d_{i% },d_{j})}+\sum\limits_{i=1}^{n}|\tau_{i}|d_{i}.

Since $\tau_{i}$ is sampled from $\textsc{Lap}(1/\varepsilon_{0})$ , we have that $|\tau_{i}|$ follows an exponential law of expectation $1/\varepsilon_{0}$ . Hence,

\mathbb{E}\left[S_{2}^{*}(G^{\phi})\right]\leq\sum\limits_{(\nu_{i},\nu_{j})% \in E^{\phi}}\min{(d_{i},d_{j})}+\frac{m}{\varepsilon_{0}}.

Since $G$ is isomorphic to $G^{\phi}$ , $\alpha(G)=\alpha(G^{\phi})$ and using Theorem 11 it follows that

\sum\limits_{(\nu_{i},\nu_{j})\in E^{\phi}}\min{(d_{i},d_{j})}\leq m\cdot% \alpha(G).

Since $m\leq n\delta$ and $\alpha(G)=O(\delta)$ , this gives $\mathbb{E}\left[S_{2}^{*}(G^{\phi})\right]\leq\mathcal{O}\left(\delta^{2}n\right)$ . $\hfill\blacktriangleleft$

In addition to the ordered stars we just discussed, arboricity can also be used to bound the number of paths and cycles in a graph, as demonstrated in the following lemma and theorem. Recall that $\#P_{k}(G)$ is the number of paths with length $k$ in the graph $G$ .

Lemma 14.

For any positive integer $k$ , $\#P_{2k}(G)=\mathcal{O}\left(\delta^{k}n^{k+1}\right),\#P_{2k+1}=\mathcal{O}% \left(\delta^{k+1}n^{k+1}\right)$ .

Proof.

We first consider $\#P_{2k+1}(G)$ . Let $f$ be a function that maps a path of length $2k+1$ to a tuple of $k+1$ edges, defined as $f(e_{1},\dots,e_{2k+1})=(e_{1},e_{3},\dots,e_{2k+1})$ . We observe that, for any tuple of $k+1$ edges denoted by $\mathcal{E}=(e^{\prime}_{1},\dots,e^{\prime}_{k+1})$ , $f^{-1}(\mathcal{E})$ is either a set containing one path or an empty set. There is at most one path that uses $e^{\prime}_{i}$ as the $(2i-1)$ -th edge of the path for all $i$ . Thus, we can conclude that the number of paths of length $2k+1$ is at most the number of sets of $k+1$ edges, which is $m^{k+1}=\mathcal{O}\left(\delta^{k+1}n^{k+1}\right)$ .

Next, let us consider $\#P_{2k}(G)$ . Let $f$ be a function that maps a path of length $2k$ to a tuple of $k$ edges, defined as $f(e_{1},\dots,e_{2k})=(e_{1},e_{3},\dots,e_{2k-1})$ . We observe that, for any tuple of $k$ edges denoted by $\mathcal{E}=(e^{\prime}_{1},\dots,e^{\prime}_{k})$ , $f^{-1}(\mathcal{E})$ is a set of size no larger than $n$ . There is at most one path of length $2k-1$ that uses $e^{\prime}_{i}$ as the $(2i-1)$ -th edge of the path, and there are at most $n$ possible ways to extend a path of length $2k-1$ to a path of length $k$ . Hence, $\#P_{2k}(G)\leq n\cdot m^{k}=\mathcal{O}\left(\delta^{k}n^{k+1}\right)$ . $\hfill\blacktriangleleft$

Recall that $\#C_{k}(G)$ is the number of cycles with size $k$ in the graph $G$ . We obtain the following theorem.

Theorem 15.

For any $k\geq 1$ , $\#C_{k+2}(G)\leq\frac{2}{k}\alpha(G)\#P_{k}(G)$ .

Proof.

Let us denote $\#P_{k}^{(i)}$ the number of paths of length $k$ that have node $\nu_{i}$ as an extremity and $\#C_{k}^{(i,j)}$ the number of cycles of length $k$ containing edge $(\nu_{i},\nu_{j})$ . Using these notations, we have $\#C_{k+2}=\frac{1}{k}\sum\limits_{(\nu_{i},\nu_{j})\in E}\#C_{k+2}^{(i,j)}$ . Consider the number $\#C_{k+2}^{(i,j)}$ . For a path of length $k$ that has a node $\nu_{i}$ as a terminal, there is at most one cycle of length $k+2$ which includes this path and the edge $(\nu_{i},\nu_{j})$ . Therefore, we conclude that $\#C_{k+2}^{(i,j)}\leq\#P_{k}^{(i)}$ . Similarly, we have $\#C_{k+2}^{(i,j)}\leq\#P_{k}^{(j)}$ . Hence,

\#C_{k+2}\leq\frac{1}{k}\sum\limits_{(\nu_{i},\nu_{j})\in E}\min{\left(\#P_{k}% ^{(i)},\#P_{k}^{(j)}\right)}.

For any function $h:E\rightarrow\{1,\dots,n\}$ such that for all $e=(\nu_{i},\nu_{j})\in E$ , $h(e)$ is equal to either $i$ or $j$ , $\min{\left(\#P_{k}^{(i)},\#P_{k}^{(j)}\right)}\leq\#P_{k}^{(h(\nu_{i},\nu_{j}))}$ . By definition of the arboricity, there exists a set of disjoint forests $\{F_{l}\}_{l=1,\ldots,\alpha(G)}$ such that $E=\bigcup_{l=1}^{\alpha(G)}F_{l}$ . By choosing a root for each tree of these forests, we can introduce a function $h$ such that each edge has its child node as an image. In this way, each node can only be the image of one edge per forest. This leads to

	$\displaystyle\#C_{k+2}$	$\displaystyle\leq$	$\displaystyle\frac{1}{k}\sum_{l=1}^{\alpha(G)}\sum_{(\nu_{i},\nu_{j})\in F_{l}% }\min{\left(\#P_{k}^{(i)},\#P_{k}^{(j)}\right)}\leq\frac{1}{k}\sum_{l=1}^{% \alpha(G)}\sum_{e\in F_{l}}\#P_{k}^{(h(e))}\leq\frac{1}{k}\sum_{l=1}^{\alpha(G% )}\sum_{i\in V}\#P_{k}^{(i)}$
		$\displaystyle=$	$\displaystyle\frac{2}{k}\alpha(G)\#P_{k}.$

The last step is justified by the fact that each path having two extremities, the sum of all the paths of length $k$ starting with node $\nu_{i}$ is twice the number of paths of length $k$ . $\hfill\blacktriangleleft$

Combining Lemma 14 and Theorem 15, we obtain the following corollary¹¹1We note that this result was independently established in [25] by a different proof. We are grateful to the anonymous reviewer for bringing this to our attention..

Corollary 16.

For $k\geq 1$ , $\#C_{2k+2}=\mathcal{O}\left(\delta^{k+1}n^{k+1}\right)$ and $\#C_{2k+1}=\mathcal{O}\left(\delta^{k+1}n^{k}\right)$ .

Next, we focus on the number of cycles of length $2k$ for any $k\geq 2$ , in which three consecutive vertices of the cycle exhibit monotonic ranks $C^{*}_{2k}$ , as illustrated in Table 2. Throughout the rest of this article, we will denote the count of such subgraphs in $G$ by $\#C_{2k}^{*}(G)$ , omitting $G$ from the notation when the context is clear. In the following theorem, for simplicity, we extend the notation by assuming $\#P_{-1}(G)=1$ and $\#P_{0}(G)=n$ for every graph $G$ .

Theorem 17.

For $k\geq 2$ , $\#C_{2k}^{*}(G)\leq 2\alpha(G)S_{2}^{*}(G)\#P_{2k-5}(G)$ .

Proof.

Let $\#C_{2k}^{*(i,j)}(G)$ represent the number of subgraphs in $G$ where three consecutive vertices exhibit monotonic ranks, with $(\nu_{i},\nu_{j})$ being the edge immediately following these consecutive vertices. Also, for $k\geq 2$ , let the number of paths of length $p$ with a low-2-star as one of its extremities be denoted as $\#P^{*}_{p}$ . Since we can construct at most one path included in $\#P^{*}_{p}$ where a low-2-star and a path of length $p-3$ are its extremities, we obtain the inequality $\#P^{*}_{p}\leq S_{2}^{*}\cdot\#P_{p-3}$ .

Let $C_{2k}^{*(i,j)}$ be a cycle which is counted in $\#C_{2k}^{*(i,j)}$ . Consider the path in $C_{2k}^{*(i,j)}$ of length $2k-2$ starting from $\nu_{i}$ that does not pass through $\nu_{j}$ and the other path in $C_{2k}^{*(i,j)}$ of the same length starting from $\nu_{j}$ that does not pass through $\nu_{i}$ . We observe that one extremity of the two paths is a low-2-star. Hence, $\#C_{2k}^{*(i,j)}\leq\min{\left(\#P_{2k-2}^{*(i)},\#P_{2k-2}^{*(j)}\right)}$ when $\#P_{p}^{*(i)}$ is the number of paths in the count of $\#P^{*}_{p}$ that have $\nu_{i}$ as an extremity. Using the same definition of $h$ as in the proof of Theorem 15, we have

	$\displaystyle\#C_{2k}^{*}(G)$	$\displaystyle\leq\sum_{(\nu_{i},\nu_{j})\in E}\#C_{2k}^{(i,j)}\leq\sum_{(\nu_% {i},\nu_{j})\in E}\min{\left(\#P_{2k-2}^{(i)},\#P_{2k-2}^{*(j)}\right)}$
		$\displaystyle\leq\sum_{l=1}^{\alpha(G)}\sum_{(\nu_{i},\nu_{j})\in F_{l}}\min{% \left(\#P_{2k-2}^{(i)},\#P_{2k-2}^{(j)}\right)}\leq\sum_{l=1}^{\alpha(G)}% \sum_{e\in F_{l}}\#P_{2k-2}^{*(h(e))}$
		$\displaystyle\leq\sum_{l=1}^{a(G)}\sum_{i\in V}\#P_{2k-2}^{(i)}\leq 2\alpha(G% )\#P_{2k-2}^{}\leq 2\alpha(G)S_{2}^{*}\#P_{2k-5}.\$

$\hfill\blacktriangleleft$ The next corollary follows Theorem 13, 17, and Lemma 14.

Corollary 18.

For $k\geq 2$ , $\mathbb{E}[C_{2k}^{*}(G^{\phi})]=\mathcal{O}\left(\delta^{k+1}n^{k-1}\right)$ .

The next corollary considers the number of edge sets in $G^{\phi}$ with specific properties.

Corollary 19.

For any $p\in\mathbb{N}$ , we consider edge sets $\mathsf{E}\subseteq E^{\phi}$ of size $2p$ such that 1) for some $c>0$ , there exists a set of cycles $C_{1},\dots,C_{c}$ in $G^{\phi}$ where $C_{1}\cup\dots\cup C_{c}=\mathsf{E}$ and $C_{i}\cap C_{j}=\emptyset$ for $i\neq j$ , and 2) at least one of $C_{1},\dots,C_{c}$ contains three consecutive vertices of monotonic index. The number of such edge sets is $\mathcal{O}\left(\delta^{p+1}n^{p-1}\right)$ .

Proof.

Consider a partition of $2p$ , denoted by $(p_{1},\dots,p_{c})$ , where $p_{1}+\cdots+p_{c}=2p$ . The number of such partitions is a function of $p$ and can be considered constant. We will demonstrate that the number of cycle sets $C_{1},\dots,C_{c}$ satisfying the conditions in the corollary statement, with $|C_{i}|=p_{i}$ , is at most $\mathcal{O}\left(\delta^{p+1}n^{p-1}\right)$ . Therefore, the number of cycle sets satisfying the corollary statement is no more than $\mathcal{O}\left(\delta^{p+1}n^{p-1}\right)$ .

To prove the bound, we will consider two cases: either all the cycles have even lengths, or at least two of them have odd lengths, given that the total number of edges is even.

If all the cycles are of even length, then, for some $q>0$ one of them is of length $2q$ and includes 3 consecutive vertices of monotonic index. By Corollary 18, there are $\mathcal{O}\left(\delta^{q+1}n^{q-1}\right)$ possibilities for this cycle. For the remaining cycles, Corollary 16 tells us that the number of admissible configurations is bounded by $\mathcal{O}\left(\delta^{p-q}n^{p-q}\right)$ . In total, this gives a $\mathcal{O}\left(\delta^{p+1}n^{p-1}\right)$ bound. If at least two cycles have odd lengths, say $2q+1$ and $2r+1$ , then by Corollary 16, the number of possible configurations for these cycles can be bounded by $\mathcal{O}\left(\delta^{q+1}n^{q}\right)$ for the first cycle and $\mathcal{O}\left(\delta^{r+1}n^{r}\right)$ for the second cycle, and $\mathcal{O}\left(\delta^{p-q-r-1}n^{p-q-r-1}\right)$ for the remaining cycles. Overall, this results in a bound of $\mathcal{O}\left(\delta^{p+1}n^{p-1}\right)$ . $\hfill\blacktriangleleft$

4 Triangle Counting Algorithm

We propose Algorithm 2 to count the number of triangles based on the ordering and properties discussed in the previous section. First, we execute Algorithm 1 at Line 2. Next, at Line 3, we use the randomized response query to obtain an obfuscated graph. From Lines 4 to 8, we employ the Laplacian query with restricted sensitivity on $\mathcal{H}_{d}$ (Definition 5) to estimate the number of triangles associated with User $i$ . Finally, at Line 9, we sum all the estimates and report the total as the estimated triangle count. We adopt the concept from [22] of distributing randomized response results to all nodes and having each node estimate its number of triangles. However, the other algorithmic ideas presented in this work are novel. In the following theorem, we demonstrate that our algorithm is differentially private.

Algorithm 2 Our algorithm for estimating the number of triangles in degeneracy-bounded graphs.

Theorem 20.

Algorithm 2 provides $(\varepsilon_{0}+\varepsilon_{1}+\varepsilon_{2})$ -edge local differential privacy.

Proof.

For all possible executions of Algorithm 2, it inquires three queries to all users. They are 1) the Laplacian query with privacy budget $\varepsilon_{0}$ inside the GetOrderingfunction at Line 2, 2) the unbiased randomized response query with privacy budget $\varepsilon_{1}$ at Line 3, and 3) the Laplacian query with restricted sensitivity on $\mathcal{H}_{d}$ at Lines 4-8.

To prove this theorem, we only need to show that the query at Lines 4-8 is $\varepsilon_{2}$ -edge local differentially private. The query aims to publish $f(a_{i}^{\phi})=\sum_{(j,k)\in S_{i}}\hat{a}^{\phi}_{j,k}$ . By the unbiased randomized response in Line 3, we have that, for any $j,k,j^{\prime},k^{\prime}$ , $|\hat{a}^{\phi}_{j,k}-\hat{a}^{\phi}_{j^{\prime},k^{\prime}}|\leq\frac{e^{% \varepsilon_{1}}+1}{e^{\varepsilon_{1}}-1}$ . It can be shown that, for $a_{i}^{\phi},a_{i}^{{}^{\prime}\phi}\in\mathcal{H}_{\hat{d}_{i}^{\phi}}$ (defined in Definition 5) such that $d(a_{i}^{\phi},a_{i}^{{}^{\prime}\phi})\leq\mathsf{d}$ , the number of different elements in the set $S_{i}$ obtained from $a_{i}^{\phi}$ , $a_{i}^{{}^{\prime}\phi}$ at Line 6 is at most $\mathsf{d}\cdot\hat{d}_{i}^{\phi}$ . Therefore, the restricted sensitivity of the function $f$ (denoted by $RS_{f}\left(\mathcal{H}_{\hat{d}_{i}^{\phi}}\right)$ in Definition 5) is not larger than $\mathsf{d}\cdot\hat{d}_{i}^{\phi}\cdot\frac{e^{\varepsilon_{1}}+1}{e^{% \varepsilon_{1}}-1}\cdot\frac{1}{\mathsf{d}}=\hat{d}_{i}^{\phi}\cdot\frac{e^{% \varepsilon_{1}}+1}{e^{\varepsilon_{1}}-1}$ . Hence, by Definition 5, the publication of $\tilde{t}_{i}$ at Line 8 is $\varepsilon_{2}$ -edge local differentially private. $\hfill\blacktriangleleft$

We now discuss the accuracy of our estimation and its relation with the parameter $\zeta$ appearing at Line 4 the algorithm. We will see that $\zeta$ controls the trade off between the bias and the accuracy. The smaller $\zeta$ is, the smaller the average noise gets, but the larger the probability of bias and its expected magnitude is.

In the following lemma, we discuss that the projection $\mu_{\hat{d}_{i}}^{\phi}$ applied at Line 5 changes the adjacency vector $a_{i}^{\phi}$ only with small probability.

Lemma 21.

For any $\zeta>0$ , with probability at least $1-\zeta$ , $|\tilde{d}_{i}-d_{i}|<(\ln{\frac{n}{\zeta}})/{\varepsilon_{0}}$ for all $i$ .

Proof.

Using the cumulative distribution function of the Laplacian random variable, we have $\mathbb{P}\left[|\tilde{d}_{i}-d_{i}|\geq\varepsilon_{0}\ln{\frac{n}{\zeta}}% \right]\leq\frac{\zeta}{n}$ . Thus, by taking this inequality for all $i\in[1,n]$ , and using the union bound, we obtain $\mathbb{P}\left[\exists i\in[1,n],|\tilde{d}_{i}-d_{i}|\geq\varepsilon_{0}\ln{% \frac{n}{\zeta}}\right]\leq\zeta$ . $\hfill\blacktriangleleft$

We show that our estimation has no bias with high probability in the subsequent theorem.

Theorem 22.

With probability at least $1-\zeta$ , algorithm 2 provides an unbiased estimate of the number of triangles in the graph, i.e. $\mathbb{E}\left[\hat{f}_{\triangle}(G)\right]=\#C_{3}(G).$

Proof.

As discussed in Definition 7, we have that $\mathbb{E}(\hat{a}_{j,k}^{\phi})=a_{j,k}^{\phi}$ . Using Lemma 21, with probability at least $1-\zeta$ , $\hat{d}^{\phi}_{i}$ is larger than $d^{\phi}_{i}$ for all $i\in[1,n]$ , and the function $\mu_{\hat{d}_{i}^{\phi}}$ has no effect. Consequently, $S_{i}$ precisely represents the set of forks centered on node $\nu_{i}$ , encompassing all possible triangles. Therefore, $\hat{t}_{i}$ is an unbiased estimate of the number of triangles $(\nu_{i},\nu_{j},\nu_{k})$ such that $j<i<k$ . Given that Laplace noise is centered and triangles can be decomposed accordingly, $\hat{f}_{\triangle}(G)$ is an unbiased estimation of $f_{\triangle}(G)$ . $\hfill\blacktriangleleft$

Corollary 23 ensures that even in the unlikely event of some clipping occurring, the resulting bias would still represent only a small fraction of the actual count.

Corollary 23.

The expected value of the bias of Algorithm 2 is bounded by $\mathcal{O}\left(\frac{\zeta}{\varepsilon_{0}n}\#C_{3}\right)$ .

Proof.

When the corrected estimated degree $\hat{d}^{\phi}_{i}$ is smaller than the actual degree $d_{i}$ , $d_{i}-\hat{d}^{\phi}_{i}$ edges are excluded. This exclusion introduces a bias because the potential triangles involving these excluded edges are not counted. For each user $i$ and their neighbor $j$ , let $t_{i}^{(j)}$ denote the number of triangles counted by user $i$ that involve the edge $(\nu_{i},\nu_{j})$ . We also define $t_{i}^{\text{max}}=\max_{j}t_{i}^{(j)}$ . Then, the maximum bias resulting from a single clipped edge can be bounded by $t_{i}^{\text{max}}$ .

The expected number of clipped edges for user $i$ is determined by evaluating the following integral, where $\beta=\frac{\ln(n/\zeta)}{\varepsilon_{0}}$ serves as the correction term for the degree:

\int_{-\infty}^{-\beta}\frac{\varepsilon_{0}}{2}e^{-\varepsilon_{0}|x|}(-x-% \beta)\,dx=-\frac{\varepsilon_{0}}{2}\left[\frac{x-\beta}{\varepsilon_{0}}e^{-% \varepsilon_{0}x}+\frac{1}{\varepsilon_{0}^{2}}e^{-\varepsilon_{0}x}\right]_{% \beta}^{\infty}=\frac{1}{2\varepsilon_{0}}e^{-\varepsilon_{0}\beta}=\frac{% \zeta}{2\varepsilon_{0}n}.

We obtain the final result by combining these elements and observing that $\sum_{i}t_{i}^{\text{max}}\leq\sum_{i,j}t_{i}^{(j)}\leq 2f_{\triangle}(G)$ . $\hfill\blacktriangleleft$

The accuracy of our estimation is demonstrated in the subsequent theorem.

Theorem 24.

When $\zeta\leq\varepsilon_{0}$ , the squared expected $\ell_{2}$ -error of algorithm 2 is bounded by

\mathcal{O}\left(\frac{\delta^{3}n}{\varepsilon_{1}^{2}}+\frac{\delta d_{max}n% }{\varepsilon_{1}^{2}\varepsilon_{2}^{2}}+\frac{n\ln^{2}(n/\zeta)}{\varepsilon% _{0}^{2}\varepsilon_{1}^{2}\varepsilon_{2}^{2}}\right).

Proof.

The squared $\ell_{2}$ -error can be decomposed into the square of the bias plus the variance. We have established in Corollary 23 that the bias of the algorithm is bounded by $\mathcal{O}\left(\frac{\zeta}{\varepsilon_{0}n}\#C_{3}\right)=\mathcal{O}\left% (\delta^{2}\right)$ . We will now focus on bounding the variance of the algorithm. This variance arises from two distinct sources: the randomized response query and the Laplacian query with restrictive sensitivity.

Regarding the noise introduced by the Laplacian query with restrictive sensitivity, its variance is simply the sum of the variances of each term, which is

\displaystyle 9\left(\frac{e^{\varepsilon_{1}}+1}{e^{\varepsilon_{1}}-1}\right% )^{2}\sum_{\nu_{i}\in V}\frac{\hat{d}_{i}^{2}}{\varepsilon_{2}^{2}}=\mathcal{O% }\left(\frac{\varepsilon_{0}^{2}\delta d_{max}n+n\ln^{2}(n/\zeta)}{\varepsilon% _{2}^{2}\varepsilon_{1}^{2}\varepsilon_{0}^{2}}\right).

Next, we consider the variance from the randomized response query. In the following equations, we use the notation $\mathcal{N}^{*}_{j,k}$ to denote the set of neighbors $\nu_{i}$ of both $\nu_{j}$ and $\nu_{k}$ such that $j<i<k$ . Note that by including one node from $\mathcal{N}^{*}_{j,k}$ along with $\nu_{j}$ and $\nu_{k}$ , a triple in $S^{*}_{2}$ is formed. Similarly, including two nodes from $\mathcal{N}^{*}_{j,k}$ along with $\nu_{j}$ and $\nu_{k}$ results in a quadruplet in $\#C^{*}_{4}$ . We also notice from Definition 7 that, for $(j,k)\neq(j^{\prime},k^{\prime})$ , $\hat{a}_{j,k}^{\phi}$ is independent to $\hat{a}_{j^{\prime},k^{\prime}}^{\phi}$ and $\text{Cov}\left(\hat{a}_{j,k}^{\phi},\hat{a}_{j^{\prime},k^{\prime}}^{\phi}% \right)=0$ . Hence,

	$\displaystyle\text{Var}\left(\sum_{\nu_{i}\in V^{\phi}}\sum_{(j,k)\in S_{i}}% \hat{a}^{\phi}_{j,k}\right)$	$\displaystyle=\sum_{(\nu_{j},\nu_{k})\in(V^{\phi})^{2}}\left[\sum_{\nu_{i}\in% \mathcal{N}^{}_{j,k}}\text{Var}\left(\hat{a}^{\phi}_{j,k}\right)+\!\sum_{\nu_% {i},\nu_{i^{\prime}}\in\mathcal{N}^{}_{j,k}}\text{Cov}\left(\hat{a}^{\phi}_{j% ,k},\hat{a}^{\phi}_{j,k}\right)\right]$
		$\displaystyle=\mathcal{O}\left((S^{}_{2}+\#C^{}_{4})/\varepsilon^{2}_{1}\right)$

By Theorem 13 and Collorary 18, $\text{Var}\left(\hat{f}(G)\right)=\mathcal{O}\left(\frac{\delta^{3}n}{% \varepsilon_{1}^{2}}+\frac{\delta d_{max}n}{\varepsilon_{1}^{2}\varepsilon_{2}% ^{2}}+\frac{n\ln^{2}(n/\zeta)}{\varepsilon_{0}^{2}\varepsilon_{1}^{2}% \varepsilon_{2}^{2}}\right)$ . $\hfill\blacktriangleleft$

In the previous work [16], the number of terms in the variance calculation is bounded by the number of cycles of length four, which is $\mathcal{O}\left({d^{3}_{\textrm{max}}}n\right)$ . We reduce that number to $\#C_{4}^{*}=\mathcal{O}\left(\delta^{3}n\right)$ using the GetOrderingfunction in Line 2 and by including only pairs $(j,k)$ such that $j<i<k$ . It is known that $\delta\leq d_{\max}$ and, in many practical graphs, the degeneracy is much smaller than the maximum degree.

5 Odd Length Cycle Counting

In this section, we will describe how to utilize low-degree ordering to accurately count odd-length cycles in graphs with bounded degeneracy. Some concepts are extended from the previous section. As shown in Algorithm 3, the algorithm for estimating the number of odd-length cycles is similar to Algorithm 2, except that the restricted sensitivity at Line 9 is larger, and at Line 8, we replace $\hat{a}^{\phi}_{i,j}$ with an estimate for the number of paths under specific constraints. We discuss the privacy of the algorithm in the subsequent theorem. The main challenge of the proof is to demonstrate that the Laplacian query under restricted sensitivity at Lines 5-9 is $\varepsilon_{2}$ -differentially private.

Algorithm 3 Our algorithm for estimating the number of odd-length cycles in degeneracy-bounded graphs.

Theorem 25.

Algorithm 3 provides $(\varepsilon_{0}+\varepsilon_{1}+\varepsilon_{2})$ -edge local differential privacy.

Proof.

We need to demonstrate that Lines 5-9 of the algorithm, involving the Laplacian query with restricted sensitivity on $\mathcal{H}_{\hat{d}_{i}^{\phi}}$ , ensure $\varepsilon_{2}$ -differential privacy. Following the arguments of Theorem 20, we assert that altering $\mathsf{d}$ entries of $a_{i,j}^{\phi}$ changes the set $S_{i}$ by at most $\mathsf{d}\cdot\hat{d}_{i}^{\phi}$ elements. A single element change in $S_{i}$ can alter the value of $\hat{c}_{i}$ by

\#\hat{P}_{k-2}^{(i)}(j,\kappa)=\sum\limits_{(l_{1},\ldots,l_{k-1})\in X_{k-2}% ^{(i)}(j,\kappa)}\prod\limits_{q\in[1,k-2]}\hat{a}^{\phi}_{l_{q},l_{q+1}}\leq% \left(\frac{e^{\varepsilon}+1}{e^{\varepsilon}-1}\right)^{2}\#\hat{P}_{k-4}.

Therefore, the restricted sensitivity of $\tilde{c}_{i}$ is $\mathsf{d}\cdot\hat{d}_{i}^{\phi}\left(\frac{e^{\varepsilon}+1}{e^{\varepsilon% }-1}\right)^{2}\#\hat{P}_{k-4}/\mathsf{d}=\hat{d}_{i}^{\phi}\left(\frac{e^{% \varepsilon}+1}{e^{\varepsilon}-1}\right)^{2}\#\hat{P}_{k-4}$ . Consequently, the publication of $\tilde{c}_{i}$ at Line 9 is $\varepsilon_{2}$ -differentially private. $\hfill\blacktriangleleft$

The bias of the algorithm is given in the following theorem.

Theorem 26.

With a probability of at least $1-\zeta$ , Algorithm 3 provides an unbiased estimate of the number of $k$ -cycles in any graph $G$ for any odd integer $k$ .

Proof.

Since we publish $\hat{a}^{\phi}_{l_{q},l_{q+1}}$ using the unbiased randomized response query, the publication is an unbiased estimation of $a^{\phi}_{l_{q},l_{q+1}}$ . Furthermore, as those estimators are independent from one another, for each $(j,\kappa)\in S_{i}$ and $\{l_{1},\ldots,l_{k-1}\}\in X_{k-2}^{(i)}(j,\kappa)$ , $\prod\limits_{q\in[1,k-2]}\hat{a}^{\phi}_{l_{q},l_{q+1}}$ is an unbiased estimate of $\prod\limits_{q\in[1,k-2]}a^{\phi}_{l_{q},l_{q+1}}$ . It results from this that $\#\hat{P}_{k-2}^{(i)}(j,\kappa)$ is an unbiased estimator of the number of paths between $j$ and $\kappa$ with length $k-2$ such that, for any three consecutive nodes $(\nu_{q},\nu_{r},\nu_{s})$ with monotonic ranks, the node $\nu_{i}$ has a lower rank that $\nu_{r}$ . We denote the number of such paths as $\#P_{k-2}^{(i)}(j,\kappa)$ .

Let us introduce $C_{k}^{(i)}=\sum_{(j,k)\in S_{i}}\#P_{k-2}^{(i)}(j,\kappa)$ . Assuming no clipping occurs, which happens with a probability of at least $1-\zeta$ , we have by linearity of expectation that both $\hat{c}_{i}$ and $\tilde{c}_{i}$ are unbiased estimators of $C_{k}^{(i)}$ . Therefore, all that remains to be proven is that the number of $k$ -cycles in $G$ is equal to $\sum_{\nu_{i}\in V^{\phi}}C_{k}^{(i)}$ . It is evident that for each element counted in $\sum_{\nu_{i}\in V^{\phi}}C_{k}^{(i)}$ , there is a corresponding cycle $(\nu_{i},l_{1},\ldots,l_{k-1})$ in $G^{\phi}$ and, also, in $G$ .

Conversely, consider a cycle of length $k$ in $G$ . Since it is also a cycle in $G^{\phi}$ , we can represent it in $G^{\phi}$ as $(\nu_{1},\ldots,\nu_{k})$ . Because the cycle is of odd length, there exist three consecutive nodes with a monotonic rank. Among all possible triplets, consider the one where the central node has the smallest rank, denoted as $(\nu_{j},\nu_{i},\nu_{\kappa})$ with $j<i<\kappa$ . Furthermore, let $j=l_{1}$ and $\kappa=l_{k-1}$ , and assign the indices of the other nodes in the cycle to $l_{2}$ through $l_{k-2}$ in the order they appear in the cycle. Thus, the cycle is counted in $\sum_{\nu_{i}\in V^{\phi}}C_{k}^{(i)}$ . Furthermore, if any other node in the cycle were chosen as $\nu_{i}$ , the remaining path would not be part of $X_{k-2}^{(i)}(j,\kappa)$ . This ensures that each cycle is counted exactly once in $\sum_{\nu_{i}\in V^{\phi}}C_{k}^{(i)}$ . $\hfill\blacktriangleleft$

Finally, the $\ell_{2}$ -error of Algorithm 3 is proven in the next theorem. The most challenging aspect of this theorem is to bound the covariance in the summation at Lines 8 and 10. We assert that any two dependent elements of $X_{k-2}^{(i)}(j,\kappa)$ can be considered as a set containing an even number of edges which forms multiple disjoint cycles with specific properties. Consequently, we can utilize our results from Corollary 19 to bound the number of such pairs. The proof of the theorem is given in the appendix of this paper.

Theorem 27.

When $\zeta\leq\varepsilon_{0}$ , the expected squared $\ell_{2}$ -error of algorithm 3 is bounded by

\mathcal{O}\left(\frac{\delta^{3}}{\varepsilon_{1}^{2}}\left(\frac{1}{% \varepsilon_{1}^{2}}+\delta\right)^{k-3}n^{k-2}+\frac{\delta^{k-2}d_{max}n^{k-% 2}}{\varepsilon_{2}^{2}\varepsilon_{1}^{4}}+\frac{\delta^{k-3}n^{k-2}\ln^{2}(n% /\zeta)}{\varepsilon_{2}^{2}\varepsilon_{1}^{4}\varepsilon_{0}^{2}}\right).

Before proving Theorem 27, we demonstrate the following lemma.

Lemma 28.

The expected value of the bias of Algorithm 3 is bounded by $\mathcal{O}\left(\frac{\zeta}{\varepsilon_{0}n}\#C_{k}\right)$ .

Proof.

We have already seen the proof of Corollary 23 that the expected value of the number of clipped edges for user $i$ was bounded by $\frac{\zeta}{2\varepsilon_{0}n}$ . We now have to bound the bias created by one edge removal, i.e. the maximal number of cycles one edge can part of.

With $c_{i}^{(j)}$ the number of cycles counted by $i$ that involve edge $(i,j)$ , the maximal bias for user $i$ is bounded by $\sum_{j}c_{i}^{(j)}$ , and the bias of the algorithm by $\frac{\zeta}{2\varepsilon_{0}n}\sum_{i,j}c_{i}^{(j)}\leq\mathcal{O}\left(\frac% {\zeta}{\varepsilon_{0}n}\#C_{k}\right)$ . $\hfill\blacktriangleleft$

Now, we are ready to prove Theorem 27.

Proof of Theorem 27.

The squared $\ell_{2}$ -error can be decomposed into the square of the bias plus the variance. In Lemma 28, we established that the bias of the algorithm is bounded by $\mathcal{O}\left(\frac{\zeta}{\varepsilon_{0}n}\#C_{k}\right)=\mathcal{O}\left% (\delta^{\frac{k+1}{2}}n^{\frac{k-3}{2}}\right)$ . We will now focus on bounding the variance of the algorithm.

Let the indicator variable $\mathbbm{1}_{(l_{1},\ldots,l_{p})}$ be 1 if the path $(\nu_{l_{1}},\ldots,\nu_{l_{p}})$ exists in $G^{\phi}$ , and 0 otherwise. We also denote the random variable $\prod_{q\in[1,p]}\hat{a}^{\phi}_{l_{q},l_{q+1}}$ by $Z_{(l_{1},\ldots,l_{p+1})}$ . Finally, we define $U_{(l_{1},\ldots,l_{p+1})}=Z_{(l_{1},\ldots,l_{p+1})}-\mathbbm{1}_{(l_{1},% \ldots,l_{p+1})}$ . This random variable $U_{(l_{1},\ldots,l_{p+1})}$ has the properties that $\mathbb{E}\left[U_{(l_{1},\ldots,l_{p+1})}\right]=0$ and $\text{Var}\left(U_{(l_{1},\ldots,l_{p+1})}\right)=\text{Var}\left(Z_{(l_{1},% \ldots,l_{p+1})}\right)$ .

Similar to the case with triangles, the variance of Algorithm 3 arises from both the unbiased randomized response query and the Laplacian query with restricted sensitivity.

Concerning the variance term coming from the randomized response, we have to compute the variance of

\hat{C}=\sum\limits_{\nu_{i}\in V}(\hat{c_{i}}-c_{i})=\sum\limits_{\nu_{i}\in V% }\sum\limits_{(j,\kappa)\in S_{i}}\sum\limits_{\{l_{1},\ldots,l_{k-1}\}\in X_{% k-2}^{(i)}(j,\kappa)}U_{(l_{1},\ldots,l_{k-1})}.

We have to take into account the term that comes from the sum of the variances of the $U$ as well as the one coming from the covariances between them.

To compute the sum of variances, we start with:

\text{Var}\left(U_{(l_{1},\ldots,l_{k-1})}\right)=\prod_{q\in[1,k-2]}\text{Var% }\left(\hat{a}^{\phi}_{l_{q},l_{q+1}}\right)=\mathcal{O}\left(\frac{1}{% \varepsilon_{1}^{2k-4}}\right).

Additionally, for each $i$ and $(j,\kappa)\in S_{i}$ , the cardinality of $X_{k-2}^{(i)}(j,\kappa)$ is bounded by $n^{k-3}$ , and the number of ways to choose $(i,j,\kappa)$ is bounded by $S_{2}^{*}$ , which is $\mathcal{O}\left(\delta^{2}n\right)$ by Theorem 13. This contributes a term in the variance from the sum of variances bounded by $\mathcal{O}\left(\delta^{2}n^{k-2}/\varepsilon_{1}^{2k-4}\right)$ .

To analyze the term arising from the covariances, we first examine the covariance between $U_{(l_{1},\ldots,l_{k-1})}$ and $U_{(l^{\prime}_{1},\ldots,l^{\prime}_{k-1})}$ . In the following equations, let $A$ be the set of edges that appear only in $(l_{1},\ldots,l_{k-1})$ or $(l^{\prime}_{1},\ldots,l^{\prime}_{k-1})$ , and let $B$ be the set of edges that appear in both. Recall that, for any $(i,j)$ $\mathbb{E}\left[\hat{a}^{\phi}_{i,j}\right]=0$ and $\mathbb{E}\left[\hat{a}^{\phi}_{i,j}\right]=\text{Var}\left(\hat{a}^{\phi}_{i,% j}\right)$ .

	$\displaystyle\text{Cov}\left(U_{(l_{1},\ldots,l_{k-1})},U_{(l^{\prime}_{1},% \ldots,l^{\prime}_{k-1})}\right)$
	$\displaystyle=\mathbb{E}\left[\prod_{q\in[1,k-2]}\hat{a}^{\phi}_{l_{q},l_{q+1}% }\prod_{q\in[1,k-2]}\hat{a}^{\phi}_{l^{\prime}_{q},l^{\prime}_{q+1}}\right]-% \mathbbm{1}_{(l_{1},\ldots,l_{k-1})}\mathbbm{1}_{(l^{\prime}_{1},\ldots,l^{% \prime}_{k-1})}$
	$\displaystyle=\prod_{(i,j)\in A}\mathbbm{1}_{(i,j)}\prod_{(i,j)\in B}\text{Var% }\left(a^{\phi}_{i,j}\right)-\prod_{q\in[1,k-2]}\mathbbm{1}_{(l_{q},l_{q+1})}% \mathbbm{1}_{(l^{\prime}_{q},l^{\prime}_{q+1})}.$

We observe that the covariance between $U_{(l_{1},\ldots,l_{k-1})}$ and $U_{(l^{\prime}_{1},\ldots,l^{\prime}_{k-1})}$ is zero if the paths $(\nu_{l_{1}},\ldots,\nu_{l_{k-1}})$ and $(\nu_{l^{\prime}_{1}},\ldots,\nu_{l^{\prime}_{k-1}})$ do not share at least one common edge or if the edges present in only one of the paths are not present in the original graph. Now consider the situation where the covariance is non-zero. We have that $|B|>0$ . Additionally, we will denote $\nu_{i}$ the node responsible for counting this instance of $U_{(l_{1},\ldots,l_{k-1})}$ and $\nu_{i^{\prime}}$ the one responsible for $U_{(l^{\prime}_{1},\ldots,l^{\prime}_{k-1})}$ .

Let $\mathsf{V}:=\{\nu_{i},\nu_{l_{1}},\dots,\nu_{l_{k-1}},\nu_{i^{\prime}},\nu_{l^% {\prime}_{1}},\dots,\nu_{l^{\prime}_{k-1}}\}$ , and let

\mathsf{E}:=\bigcup_{1\leq q\leq k-2}\{(\nu_{l_{q}},\nu_{l_{q+1}}),(\nu_{l^{% \prime}_{q}},\nu_{l^{\prime}_{q+1}})\}\cup\{(\nu_{l_{k-1}},\nu_{i}),(\nu_{i},% \nu_{l_{1}}),(\nu_{l^{\prime}_{k-1}},\nu_{i^{\prime}}),(\nu_{i},\nu_{l^{\prime% }_{1}})\}.

In other words, the set $\mathsf{E}$ consists of the edges in the paths $\{l_{1},\ldots,l_{k-1}\}$ and $\{l^{\prime}_{1},\ldots,l^{\prime}_{k-1}\}$ , along with the additional edges $(\nu_{l_{k-1}},\nu_{i})$ , $(\nu_{i},\nu_{l_{1}})$ , $(\nu_{l^{\prime}_{k-1}},\nu_{i^{\prime}})$ , and $(\nu_{i},\nu_{l^{\prime}_{1}})$ . Additionally, let

	$\displaystyle A^{\prime}$	$\displaystyle:=A\cup\{(\nu_{l_{k-1}},\nu_{i}),(\nu_{l^{\prime}_{k-1}},\nu_{i^{% \prime}})\mid(\nu_{l_{k-1}},\nu_{i})\neq(\nu_{l^{\prime}_{k-1}},\nu_{i^{\prime% }})\}$
		$\displaystyle\cup\{(\nu_{i},\nu_{l_{1}}),(\nu_{i^{\prime}},\nu_{l^{\prime}_{1}% })\mid(\nu_{i},\nu_{l_{1}})\neq(\nu_{i^{\prime}},\nu_{l^{\prime}_{1}})\}.$

Similarly, let

\displaystyle B^{\prime}

\displaystyle:=B\cup\{(\nu_{l_{k-1}},\nu_{i})\mid(\nu_{l_{k-1}},\nu_{i})=(\nu_% {l^{\prime}_{k-1}},\nu_{i^{\prime}})\}\cup\{(\nu_{i},\nu_{l_{1}})\mid(\nu_{i},% \nu_{l_{1}})=(\nu_{i^{\prime}},\nu_{l^{\prime}_{1}})\}.

In other words, the sets $A^{\prime}$ and $B^{\prime}$ are the sets $A$ and $B$ extended to include the additional edges $(\nu_{i},\nu_{l_{1}})$ , $(\nu_{l_{k-1}},\nu_{i})$ , $(\nu_{i^{\prime}},\nu_{l^{\prime}_{1}})$ , and $(\nu_{l^{\prime}_{k-1}},\nu_{i^{\prime}})$ .

We introduce $\mathbf{d}$ the difference between the cardinal of $B^{\prime}$ and $B$ , $\mathbf{d}:=|B^{\prime}|-|B|$ . Let $q\in[1,k-2]$ be the cardinality of $B$ . In this case, the covariance is $\mathcal{O}\left(1/\varepsilon_{1}^{2q}\right)$ . We have that $|A^{\prime}|+2|B^{\prime}|=2k$ , which gives $|A^{\prime}|=2k-2q-2\mathbf{d}$ .

In the next step, we will calculate the number of the pairs of paths with $|A^{\prime}|=2(k-q-\mathbf{d})$ . Let us consider the degree of each node in $(\mathsf{V},\mathsf{E})$ . It is clear that the degrees are neither greater than four nor less than two. A node has a degree of three only if one of the three edges incident to it belongs to $B^{\prime}$ and the other two to $A^{\prime}$ . A node has a degree of four if all four edges incident to it are in $A^{\prime}$ , and it has a degree of two if both edges incident to it are either in $A^{\prime}$ or in $B^{\prime}$ . Hence, if we consider the graph $(\mathsf{V},A^{\prime})$ , we have a graph of degree two or four, which is a union of multiple disjoint cycles.

Let the number of those disjoint cycles be $c$ and the size of those cycles be $r_{1},\dots r_{c}$ . We have that $\sum_{t=1}^{c}r_{t}=2k-2q-2\mathbf{d}$ , i.e. $(r_{1},\dots,r_{c})$ is a partition of $2k-2q-2\mathbf{d}$ . We know that the number of such partitions is bounded by a function of $k$ . Let suppose that the bound is $f(k)$ .

Let us give the number of $A^{\prime}$ with cycle size $(r_{1},\dots,r_{c})$ . We can use Corollary 16 to show that the number of such sets $A^{\prime}$ is $\mathcal{O}\left(\prod_{t=1}^{c}\delta^{r_{t}/2}n^{r_{t}/2}\right)=\mathcal{O}% \left(\delta^{k-q-\mathbf{d}}n^{k-q-\mathbf{d}}\right)$ . When $\mathbf{d}=0$ , we know that $\{\nu_{i},\nu_{j}\}$ and $\{\nu_{i},\nu_{k}\}$ are in $A^{\prime}$ . There are three consecutive nodes with monotonic ranks in the union of disjoint cycles $(\mathsf{V},A^{\prime})$ . Hence, we can use Corollary 19 to show that the number of such sets $A^{\prime}$ is bounded by $\mathcal{O}\left(\delta^{k-q+1}n^{k-q-1}\right)$ . By combining the two cases, we can conclude that the number of possible sets $A^{\prime}$ with cycle size $(r_{1},\dots,r_{c})$ is at most $\mathcal{O}\left(\delta^{k-q+1-\mathbf{d}}n^{k-q-1}\right)$ . The number of possible $A^{\prime}$ is then $f(k)\cdot\mathcal{O}\left(\delta^{k-q+1-\mathbf{d}}n^{k-q-1}\right)$ . As $k$ is a constant, the number is $\mathcal{O}\left(\delta^{k-q+1-\mathbf{d}}n^{k-q-1}\right)$ .

We then consider the number of configurations for $B^{\prime}$ , which consists of a union of disjoint paths. Let the number of paths be $c$ and their lengths be $r_{1},\dots,r_{c}$ . We have that $|r_{1}|+\dots+|r_{c}|=q$ , and $(r_{1},\dots,r_{c})$ forms a partition of $q$ . The number of possible partitions is bounded by a function of $k$ , denoted as $f(k)$ . Each part must begin and end in the node set $A^{\prime}$ , where $|A^{\prime}|\leq 2k$ . Therefore, the number of possible paths $r_{t}$ is at most $4k^{2}n^{r_{t}-1}$ , and the number of possible sets $B^{\prime}$ with the partition $(r_{1},\dots,r_{c})$ is at most $\prod_{t=1}^{c}4k^{2}n^{r_{t}-1}=\mathcal{O}\left(n^{q-1}\right)$ . Hence, the total number of possible sets $B^{\prime}$ is $f(k)\cdot\mathcal{O}\left(n^{q-1}\right)=\mathcal{O}\left(n^{q-1}\right)$ .

Consequently, for each set $A^{\prime}$ , the number of possible configurations for $B^{\prime}$ is at most $\mathcal{O}\left(n^{q-1}\right)$ . The number of pairs of paths $\{l_{1},\dots,l_{k-1}\}$ and $\{l^{\prime}_{1},\dots,l^{\prime}_{k-1}\}$ with $|A^{\prime}|=2(k-q-\mathbf{d})$ is then at most $\mathcal{O}\left(\delta^{k-q+1-\mathbf{d}}n^{k-q-1}\cdot n^{q-1}\right)=% \mathcal{O}\left(\delta^{k-q+1}n^{k-2}\right)$ . Each of these pairs contributes $\text{Var}\left(\hat{a}^{\phi}_{j,k}\right)^{2q}=\mathcal{O}\left(1/% \varepsilon_{1}^{2q}\right)$ to the covariance sum.

The covariance of $\hat{C}$ can then be calculated as follows:

\mathcal{O}\left(\sum_{q=1}^{k-2}\delta^{k-q+1}n^{k-2}\frac{1}{\varepsilon_{1}% ^{2q}}\right)=\mathcal{O}\left(\frac{n^{k-2}\delta^{3}}{\varepsilon_{1}^{2}}% \left(\delta+\frac{1}{\varepsilon_{1}^{2}}\right)^{k-3}\right).

Since this bound is larger than the one for the sum of variances, we can disregard the latter.

To compute the variance resulting from the Laplacian query with restricted sensitivity, we sum the variance of the Laplacian distribution for all nodes:

9\left(\frac{e^{\varepsilon}+1}{e^{\varepsilon}-1}\right)^{4}\mathbb{E}\left[% \#\hat{P}_{k-4}^{2}\right]\sum_{\nu_{i}\in V}\frac{\hat{d}_{i}^{2}}{% \varepsilon_{2}^{2}}=\mathcal{O}\left(\frac{\delta d_{max}n}{\varepsilon_{2}^{% 2}\varepsilon_{1}^{4}}+\frac{n\ln^{2}(n/\zeta)}{\varepsilon_{2}^{2}\varepsilon% _{1}^{4}\varepsilon_{0}^{2}}\right)\mathbb{E}\left[\#\hat{P}_{k-4}^{2}\right].

(1)

Let us now consider the expected value

\mathbb{E}\left[\#\hat{P}_{k-4}^{2}\right]=\mathbb{E}\left[\#\hat{P}_{k-4}% \right]^{2}+\text{Var}\left(\#\hat{P}_{k-4}\right)=\#P_{k-4}^{2}+\text{Var}% \left(\#\hat{P}_{k-4}\right).

(2)

By Lemma 14 and the fact that $k-4$ is an odd number, we have $\#P^{2}_{k-4}=\mathcal{O}\left(\delta^{k-3}n^{k-3}\right)$ . The variance can be decomposed into the sum of the variances of each path, which is bounded by $\mathcal{O}\left(n^{k-3}/\varepsilon_{1}^{2k-8}\right)$ , and the sum of covariances.

The covariance is non-zero only if at least two edges are shared between the two paths and all edges that appear only once exist in the original graph. As previously discussed, this forms a cycle structure, except for the path extremities that do not need to be connected. Recall the definitions of the sets $A$ and $B$ from the previous paragraph.

The set $A$ consists of two paths at the extremities and multiple disjoint cycles. Suppose the number of edges in $A$ is $2p$ , the number of edges in the two paths are $q_{1}$ and $q_{2}$ , and the number of disjoint cycles is $c$ , with the number of edges in these cycles being $r_{1},\dots,r_{c}$ . This gives us $2p=q_{1}+q_{2}+\sum_{i=1}^{c}r_{i}$ . In other words, $(q_{1},q_{2},r_{1},\dots,r_{c})$ forms a partition of $2p\leq 2k$ . The number of such partitions is bounded by a function of $k$ . Let the bound be $f(k)$ .

We now discuss the number of possible configurations of $A$ for the partition $(q_{1},q_{2},r_{1},\dots,r_{c})$ . From Lemma 14 and Corollary 16, the number of cycles of length $q$ is bounded by $\mathcal{O}\left(\delta^{q/2}n^{q/2}\right)$ , and the number of paths of length $q$ is bounded by $\mathcal{O}\left(\delta^{q/2}n^{q/2+1}\right)$ . Thus, the number of configurations for the partition $(q_{1},q_{2},r_{1},\dots,r_{c})$ is:

\mathcal{O}\left(\delta^{q_{1}/2}n^{q_{1}/2+1}\cdot\delta^{q_{2}/2}n^{q_{2}/2+% 1}\cdot\prod_{t=1}^{c}\delta^{r_{t}/2}n^{r_{t}/2}\right)=\mathcal{O}\left(% \delta^{p}n^{p+2}\right).

Hence, the number of possible configurations for $A$ with $2p$ edges is no more than $f(k)\cdot\mathcal{O}\left(\delta^{p}n^{p+2}\right)=\mathcal{O}\left(\delta^{p}% n^{p+2}\right)$ .

The number of edges in $B$ is $(2k-8-2p)/2=k-p-4$ . Using the previous argument when calculating the number of possible set $B^{\prime}$ , we obtain that the number of configurations for $B$ is $\mathcal{O}\left(n^{k-p-5}\right)$ . The number of configurations with $|A|=2p$ is then $\mathcal{O}\left(\delta^{p}n^{p+2}\cdot n^{k-p-5}\right)=\mathcal{O}\left(% \delta^{p}n^{k-3}\right)$ . Hence, the overall number of combinations is $\sum_{p=1}^{k-5}\mathcal{O}\left(\delta^{p}n^{k-3}\right)=\mathcal{O}\left(% \delta^{k-5}n^{k-3}\right)$ .

From the previous paragraph, we observe that the covariance term outweighs the sum of the variances, leading to $\text{Var}\left(\#\hat{P}_{k-4}\right)=\mathcal{O}\left(\delta^{k-5}n^{k-3}\right)$ . Additionally, when calculating $\mathbb{E}\left[\#\hat{P}^{2}_{k-4}\right]$ in (2), it is evident that $\#P^{2}_{k-4}$ dominates $\text{Var}\left(\#\hat{P}_{k-4}\right)$ , resulting in $\mathbb{E}\left[\#\hat{P}^{2}_{k-4}\right]=\mathcal{O}\left(\delta^{k-3}n^{k-3% }\right)$ . Substituting $\mathbb{E}\left[\#\hat{P}^{2}_{k-4}\right]$ with $\mathcal{O}\left(\delta^{k-3}n^{k-3}\right)$ in (1), we find that the variance from the Laplacian mechanism is bounded by

\mathcal{O}\left(\frac{\delta^{k-2}d_{max}n^{k-2}}{\varepsilon_{2}^{2}% \varepsilon_{1}^{4}}+\frac{\delta^{k-3}n^{k-2}\ln^{2}(n/\zeta)}{\varepsilon_{2% }^{2}\varepsilon_{1}^{4}\varepsilon_{0}^{2}}\right).

We obtain the theorem result by summing the variance from the unbiased randomized response query and the variance from the Laplacian query with restricted sensitivity. $\hfill\blacktriangleleft$

6 Conclusion

In this work, we introduced a private vertex ordering algorithm. The transformation on the graph induced by this ordering reduces the count of specific order-sensitive motifs while preserving the overall graph structure. Due to its reliance on the Laplacian mechanism, the algorithm performs well even in high-privacy settings, making it an excellent preprocessing step for subgraph counting queries.

Within this framework, we first propose a new triangle counting algorithm whose accuracy depends on the count of specific ordered subgraphs. By combining this algorithm with the ordering preprocessing step, we achieve an expected error of $\mathcal{O}\left(n\right)$ for graphs with bounded degeneracy, compared to the $\mathcal{O}\left(n^{2}\right)$ error seen in the current state of the art.

Subsequently, we extended the algorithm to address the more general case of odd-length cycle counting. We propose the first purely local differentially private counting algorithm specifically designed for cycles longer than triangles. Under the assumption of bounded degeneracy, the algorithm achieves an error of $\mathcal{O}\left(n^{(k-1)/2}\right)$ for cycles of length $k$ .

Due to the constraints of local differential privacy, it might be assumed that the range of tasks we can perform on graphs under this privacy notion is limited. However, in this work, we demonstrate that more precise information can be published under local differential privacy by restricting our inputs to certain types of graphs. We believe that parameterized algorithms under local differential privacy represent an intriguing research area that can contribute significantly to both algorithm design and information privacy.

One limitation of this method is that the relative error can become significantly large when the number of cycles is small (or even zero), even in cases where the graph’s degeneracy – and consequently the $\ell_{2}$ -error of our algorithm – is high. Identifying a class of graphs for which an algorithm with bounded relative error can be designed would be a direction for future research. Another question for future investigation is determining lower bounds for degeneracy-bounded graphs under the local differential privacy.

References

[1] Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286(5439):509–512, 1999.
[2] Suman K. Bera, Lior Gishboliner, Yevgeny Levanzov, C. Seshadhri, and Asaf Shapira. Counting subgraphs in degenerate graphs. ACM Journal of the ACM (JACM), 69(3):23:1–23:21, 2022. doi:10.1145/3520240.
[3] Louis Betzer, Vorapong Suppakitpaisarn, and Quentin Hillebrand. Publishing number of walks and katz centrality under local differential privacy. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024. URL: https://openreview.net/forum?id=76UkTmdmkB.
[4] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. Differentially private data analysis of social networks via restricted sensitivity. In Innovations in Theoretical Computer Science, ITCS ’13, Berkeley, CA, USA, January 9-12, 2013, pages 87–96. ACM, 2013. doi:10.1145/2422436.2422449.
[5] Marco Bressan. Faster algorithms for counting subgraphs in sparse graphs. Algorithmica, 83(8):2578–2605, 2021. doi:10.1007/s00453-021-00811-0.
[6] Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM J. Comput., 14(1):210–223, 1985. doi:10.1137/0214017.
[7] Graham Cormode, Somesh Jha, Tejas Kulkarni, Ninghui Li, Divesh Srivastava, and Tianhao Wang. Privacy at scale: Local differential privacy in practice. In Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018, pages 1655–1658. ACM, 2018. doi:10.1145/3183713.3197390.
[8] Damien Desfontaines and Balázs Pejó. Sok: Differential privacies. Proc. Priv. Enhancing Technol., 2020(2):288–313, 2020. doi:10.2478/popets-2020-0028.
[9] Laxman Dhulipala, George Z. Li, and Quanquan C. Liu. Near-optimal differentially private k-core decomposition. CoRR, abs/2312.07706, 2023. doi:10.48550/arXiv.2312.07706.
[10] Laxman Dhulipala, Quanquan C. Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, and Shangdi Yu. Differential privacy from locally adjustable graph algorithms: k-core decomposition, low out-degree ordering, and densest subgraphs. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 754–765. IEEE, 2022. doi:10.1109/FOCS54457.2022.00077.
[11] Michael Dinitz, Satyen Kale, Silvio Lattanzi, and Sergei Vassilvitskii. Improved differentially private densest subgraph: Local and purely additive. CoRR, abs/2308.10316, 2023. doi:10.48550/arXiv.2308.10316.
[12] Pål Grønås Drange, Patrick Greaves, Irene Muzi, and Felix Reidl. Computing complexity measures of degenerate graphs. In 18th International Symposium on Parameterized and Exact Computation, IPEC 2023, September 6-8, 2023, Amsterdam, The Netherlands, volume 285 of LIPIcs, pages 14:1–14:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.IPEC.2023.14.
[13] Cynthia Dwork. Differential privacy. In Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II, volume 4052 of Lecture Notes in Computer Science, pages 1–12. Springer, 2006. doi:10.1007/11787006_1.
[14] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings, volume 3876 of Lecture Notes in Computer Science, pages 265–284. Springer, 2006. doi:10.1007/11681878_14.
[15] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211–407, 2014. doi:10.1561/0400000042.
[16] Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova, and Adam D. Smith. Triangle counting with local edge differential privacy. In 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany, volume 261 of LIPIcs, pages 52:1–52:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.ICALP.2023.52.
[17] Alexandre V. Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant. Limiting privacy breaches in privacy preserving data mining. In Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 9-12, 2003, San Diego, CA, USA, pages 211–222. ACM, 2003. doi:10.1145/773153.773174.
[18] Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1106–1125. SIAM, 2010. doi:10.1137/1.9781611973075.90.
[19] Michael Hay, Chao Li, Gerome Miklau, and David D. Jensen. Accurate estimation of the degree distribution of private networks. In ICDM 2009, The Ninth IEEE International Conference on Data Mining, Miami, Florida, USA, 6-9 December 2009, pages 169–178. IEEE Computer Society, 2009. doi:10.1109/ICDM.2009.11.
[20] Quentin Hillebrand, Vorapong Suppakitpaisarn, and Tetsuo Shibuya. Communication cost reduction for subgraph counting under local differential privacy via hash functions. CoRR, abs/2312.07055, 2023. doi:10.48550/arXiv.2312.07055.
[21] Quentin Hillebrand, Vorapong Suppakitpaisarn, and Tetsuo Shibuya. Unbiased locally private estimator for polynomials of laplacian variables. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023, Long Beach, CA, USA, August 6-10, 2023, pages 741–751. ACM, 2023. doi:10.1145/3580305.3599537.
[22] Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. Locally differentially private analysis of graph statistics. In 30th USENIX Security Symposium, USENIX Security 2021, August 11-13, 2021, pages 983–1000. USENIX Association, 2021. URL: https://www.usenix.org/conference/usenixsecurity21/presentation/imola.
[23] Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. Communication-efficient triangle counting under local differential privacy. In 31st USENIX Security Symposium, USENIX Security 2022, Boston, MA, USA, August 10-12, 2022, pages 537–554. USENIX Association, 2022. URL: https://www.usenix.org/conference/usenixsecurity22/presentation/imola.
[24] Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. Differentially private triangle and 4-cycle counting in the shuffle model. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS 2022, Los Angeles, CA, USA, November 7-11, 2022, pages 1505–1519. ACM, 2022. doi:10.1145/3548606.3560659.
[25] George Manoussakis. Listing all fixed-length simple cycles in sparse graphs in optimal time. In Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Bordeaux, France, September 11-13, 2017, Proceedings, volume 10472 of Lecture Notes in Computer Science, pages 355–366. Springer, Springer, 2017. doi:10.1007/978-3-662-55751-8_28.
[26] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 94–103. IEEE Computer Society, 2007. doi:10.1109/FOCS.2007.41.
[27] Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. doi:10.1007/978-3-642-27875-4.
[28] Iyiola E. Olatunji, Thorben Funke, and Megha Khosla. Releasing graph neural networks with differential privacy guarantees. Trans. Mach. Learn. Res., 2023, 2023. URL: https://openreview.net/forum?id=wk8oXR0kFA.
[29] Zhan Qin, Ting Yu, Yin Yang, Issa Khalil, Xiaokui Xiao, and Kui Ren. Generating synthetic decentralized social graphs with local differential privacy. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30 - November 03, 2017, pages 425–438. ACM, 2017. doi:10.1145/3133956.3134086.
[30] Sofya Raskhodnikova and Adam D. Smith. Differentially private analysis of graphs. In Encyclopedia of Algorithms, pages 543–547. Springer, 2016. doi:10.1007/978-1-4939-2864-4_549.
[31] Sina Sajadmanesh and Daniel Gatica-Perez. Locally private graph neural networks. In CCS ’21: 2021 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, Republic of Korea, November 15 - 19, 2021, pages 2130–2145. ACM, 2021. doi:10.1145/3460120.3484565.
[32] Yue Wang, Xintao Wu, and Donghui Hu. Using randomized response for differential privacy preserving data collection. In Proceedings of the Workshops of the EDBT/ICDT 2016 Joint Conference, EDBT/ICDT Workshops 2016, Bordeaux, France, March 15, 2016, volume 1558 of CEUR Workshop Proceedings. CEUR-WS.org, 2016. URL: https://ceur-ws.org/Vol-1558/paper35.pdf.
[33] Stanley L. Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63–69, 1965.
[34] Qingqing Ye, Haibo Hu, Man Ho Au, Xiaofeng Meng, and Xiaokui Xiao. Towards locally differentially private generic graph metric estimation. In 36th IEEE International Conference on Data Engineering, ICDE 2020, Dallas, TX, USA, April 20-24, 2020, pages 1922–1925. IEEE, 2020. doi:10.1109/ICDE48307.2020.00204.
[35] Qingqing Ye, Haibo Hu, Man Ho Au, Xiaofeng Meng, and Xiaokui Xiao. LF-GDPR: A framework for estimating graph metrics with local differential privacy. IEEE Trans. Knowl. Data Eng., 34(10):4905–4920, 2022. doi:10.1109/TKDE.2020.3047124.
[36] Hailong Zhang, Sufian Latif, Raef Bassily, and Atanas Rountev. Differentially-private control-flow node coverage for software usage analysis. In 29th USENIX Security Symposium, USENIX Security 2020, August 12-14, 2020, pages 1021–1038. USENIX Association, 2020. URL: https://www.usenix.org/conference/usenixsecurity20/presentation/zhang-hailong.
[37] Xiao Zhou and Takao Nishizeki. Graph coloring algorithms. IEICE Transactions on Information and Systems, 83(3):407–417, 2000.

[bib.bib1] [1] Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286(5439):509–512, 1999.

[bib.bib2] [2] Suman K. Bera, Lior Gishboliner, Yevgeny Levanzov, C. Seshadhri, and Asaf Shapira. Counting subgraphs in degenerate graphs. ACM Journal of the ACM (JACM), 69(3):23:1–23:21, 2022. doi:10.1145/3520240.

[bib.bib3] [3] Louis Betzer, Vorapong Suppakitpaisarn, and Quentin Hillebrand. Publishing number of walks and katz centrality under local differential privacy. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024. URL: https://openreview.net/forum?id=76UkTmdmkB.

[bib.bib4] [4] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. Differentially private data analysis of social networks via restricted sensitivity. In Innovations in Theoretical Computer Science, ITCS ’13, Berkeley, CA, USA, January 9-12, 2013, pages 87–96. ACM, 2013. doi:10.1145/2422436.2422449.

[bib.bib5] [5] Marco Bressan. Faster algorithms for counting subgraphs in sparse graphs. Algorithmica, 83(8):2578–2605, 2021. doi:10.1007/s00453-021-00811-0.

[bib.bib6] [6] Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM J. Comput., 14(1):210–223, 1985. doi:10.1137/0214017.

[bib.bib7] [7] Graham Cormode, Somesh Jha, Tejas Kulkarni, Ninghui Li, Divesh Srivastava, and Tianhao Wang. Privacy at scale: Local differential privacy in practice. In Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018, pages 1655–1658. ACM, 2018. doi:10.1145/3183713.3197390.

[bib.bib8] [8] Damien Desfontaines and Balázs Pejó. Sok: Differential privacies. Proc. Priv. Enhancing Technol., 2020(2):288–313, 2020. doi:10.2478/popets-2020-0028.

[bib.bib9] [9] Laxman Dhulipala, George Z. Li, and Quanquan C. Liu. Near-optimal differentially private k-core decomposition. CoRR, abs/2312.07706, 2023. doi:10.48550/arXiv.2312.07706.

[bib.bib10] [10] Laxman Dhulipala, Quanquan C. Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, and Shangdi Yu. Differential privacy from locally adjustable graph algorithms: k-core decomposition, low out-degree ordering, and densest subgraphs. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 754–765. IEEE, 2022. doi:10.1109/FOCS54457.2022.00077.

[bib.bib11] [11] Michael Dinitz, Satyen Kale, Silvio Lattanzi, and Sergei Vassilvitskii. Improved differentially private densest subgraph: Local and purely additive. CoRR, abs/2308.10316, 2023. doi:10.48550/arXiv.2308.10316.

[bib.bib12] [12] Pål Grønås Drange, Patrick Greaves, Irene Muzi, and Felix Reidl. Computing complexity measures of degenerate graphs. In 18th International Symposium on Parameterized and Exact Computation, IPEC 2023, September 6-8, 2023, Amsterdam, The Netherlands, volume 285 of LIPIcs, pages 14:1–14:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.IPEC.2023.14.

[bib.bib13] [13] Cynthia Dwork. Differential privacy. In Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II, volume 4052 of Lecture Notes in Computer Science, pages 1–12. Springer, 2006. doi:10.1007/11787006_1.

[bib.bib14] [14] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings, volume 3876 of Lecture Notes in Computer Science, pages 265–284. Springer, 2006. doi:10.1007/11681878_14.

[bib.bib15] [15] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211–407, 2014. doi:10.1561/0400000042.

[bib.bib16] [16] Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova, and Adam D. Smith. Triangle counting with local edge differential privacy. In 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany, volume 261 of LIPIcs, pages 52:1–52:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.ICALP.2023.52.

[bib.bib17] [17] Alexandre V. Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant. Limiting privacy breaches in privacy preserving data mining. In Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 9-12, 2003, San Diego, CA, USA, pages 211–222. ACM, 2003. doi:10.1145/773153.773174.

[bib.bib18] [18] Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1106–1125. SIAM, 2010. doi:10.1137/1.9781611973075.90.

[bib.bib19] [19] Michael Hay, Chao Li, Gerome Miklau, and David D. Jensen. Accurate estimation of the degree distribution of private networks. In ICDM 2009, The Ninth IEEE International Conference on Data Mining, Miami, Florida, USA, 6-9 December 2009, pages 169–178. IEEE Computer Society, 2009. doi:10.1109/ICDM.2009.11.

[bib.bib20] [20] Quentin Hillebrand, Vorapong Suppakitpaisarn, and Tetsuo Shibuya. Communication cost reduction for subgraph counting under local differential privacy via hash functions. CoRR, abs/2312.07055, 2023. doi:10.48550/arXiv.2312.07055.

[bib.bib21] [21] Quentin Hillebrand, Vorapong Suppakitpaisarn, and Tetsuo Shibuya. Unbiased locally private estimator for polynomials of laplacian variables. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023, Long Beach, CA, USA, August 6-10, 2023, pages 741–751. ACM, 2023. doi:10.1145/3580305.3599537.

[bib.bib22] [22] Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. Locally differentially private analysis of graph statistics. In 30th USENIX Security Symposium, USENIX Security 2021, August 11-13, 2021, pages 983–1000. USENIX Association, 2021. URL: https://www.usenix.org/conference/usenixsecurity21/presentation/imola.

[bib.bib23] [23] Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. Communication-efficient triangle counting under local differential privacy. In 31st USENIX Security Symposium, USENIX Security 2022, Boston, MA, USA, August 10-12, 2022, pages 537–554. USENIX Association, 2022. URL: https://www.usenix.org/conference/usenixsecurity22/presentation/imola.

[bib.bib24] [24] Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. Differentially private triangle and 4-cycle counting in the shuffle model. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS 2022, Los Angeles, CA, USA, November 7-11, 2022, pages 1505–1519. ACM, 2022. doi:10.1145/3548606.3560659.

[bib.bib25] [25] George Manoussakis. Listing all fixed-length simple cycles in sparse graphs in optimal time. In Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Bordeaux, France, September 11-13, 2017, Proceedings, volume 10472 of Lecture Notes in Computer Science, pages 355–366. Springer, Springer, 2017. doi:10.1007/978-3-662-55751-8_28.

[bib.bib26] [26] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 94–103. IEEE Computer Society, 2007. doi:10.1109/FOCS.2007.41.

[bib.bib27] [27] Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. doi:10.1007/978-3-642-27875-4.

[bib.bib28] [28] Iyiola E. Olatunji, Thorben Funke, and Megha Khosla. Releasing graph neural networks with differential privacy guarantees. Trans. Mach. Learn. Res., 2023, 2023. URL: https://openreview.net/forum?id=wk8oXR0kFA.

[bib.bib29] [29] Zhan Qin, Ting Yu, Yin Yang, Issa Khalil, Xiaokui Xiao, and Kui Ren. Generating synthetic decentralized social graphs with local differential privacy. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30 - November 03, 2017, pages 425–438. ACM, 2017. doi:10.1145/3133956.3134086.

[bib.bib30] [30] Sofya Raskhodnikova and Adam D. Smith. Differentially private analysis of graphs. In Encyclopedia of Algorithms, pages 543–547. Springer, 2016. doi:10.1007/978-1-4939-2864-4_549.

[bib.bib31] [31] Sina Sajadmanesh and Daniel Gatica-Perez. Locally private graph neural networks. In CCS ’21: 2021 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, Republic of Korea, November 15 - 19, 2021, pages 2130–2145. ACM, 2021. doi:10.1145/3460120.3484565.

[bib.bib32] [32] Yue Wang, Xintao Wu, and Donghui Hu. Using randomized response for differential privacy preserving data collection. In Proceedings of the Workshops of the EDBT/ICDT 2016 Joint Conference, EDBT/ICDT Workshops 2016, Bordeaux, France, March 15, 2016, volume 1558 of CEUR Workshop Proceedings. CEUR-WS.org, 2016. URL: https://ceur-ws.org/Vol-1558/paper35.pdf.

[bib.bib33] [33] Stanley L. Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63–69, 1965.

[bib.bib34] [34] Qingqing Ye, Haibo Hu, Man Ho Au, Xiaofeng Meng, and Xiaokui Xiao. Towards locally differentially private generic graph metric estimation. In 36th IEEE International Conference on Data Engineering, ICDE 2020, Dallas, TX, USA, April 20-24, 2020, pages 1922–1925. IEEE, 2020. doi:10.1109/ICDE48307.2020.00204.

[bib.bib35] [35] Qingqing Ye, Haibo Hu, Man Ho Au, Xiaofeng Meng, and Xiaokui Xiao. LF-GDPR: A framework for estimating graph metrics with local differential privacy. IEEE Trans. Knowl. Data Eng., 34(10):4905–4920, 2022. doi:10.1109/TKDE.2020.3047124.

[bib.bib36] [36] Hailong Zhang, Sufian Latif, Raef Bassily, and Atanas Rountev. Differentially-private control-flow node coverage for software usage analysis. In 29th USENIX Security Symposium, USENIX Security 2020, August 12-14, 2020, pages 1021–1038. USENIX Association, 2020. URL: https://www.usenix.org/conference/usenixsecurity20/presentation/zhang-hailong.

[bib.bib37] [37] Xiao Zhou and Takao Nishizeki. Graph coloring algorithms. IEICE Transactions on Information and Systems, 83(3):407–417, 2000.

	$\displaystyle\#C_{2k}^{*}(G)$	$\displaystyle\leq\sum_{(\nu_{i},\nu_{j})\in E}\#C_{2k}^{(i,j)}\leq\sum_{(\nu_% {i},\nu_{j})\in E}\min{\left(\#P_{2k-2}^{(i)},\#P_{2k-2}^{*(j)}\right)}$
		$\displaystyle\leq\sum_{l=1}^{\alpha(G)}\sum_{(\nu_{i},\nu_{j})\in F_{l}}\min{% \left(\#P_{2k-2}^{(i)},\#P_{2k-2}^{(j)}\right)}\leq\sum_{l=1}^{\alpha(G)}% \sum_{e\in F_{l}}\#P_{2k-2}^{*(h(e))}$
		$\displaystyle\leq\sum_{l=1}^{a(G)}\sum_{i\in V}\#P_{2k-2}^{(i)}\leq 2\alpha(G% )\#P_{2k-2}^{}\leq 2\alpha(G)S_{2}^{*}\#P_{2k-5}.\$

Cycle Counting Under Local Differential Privacy for Degeneracy-Bounded Graphs

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Our Contribution

1.2 Technical Overview

1.3 Related Works

2 Preliminaries

2.1 Notations

2.2 Edge Local Differential Privacy

Definition 1 (ε-edge local differentially private query).

Definition 2 (ε-edge local differentially private algorithm [29]).

2.3 Laplacian Query and Restricted Sensitivity

Definition 3 (Edge local Laplacian query [21]).

Definition 4 (Restricted sensitivity (Definition 8 of [4])).

Definition 5 (Edge local Laplacian query with restricted sensitivity on ℋd [4]).

2.4 Unbiased Randomized Response

Definition 6 (Randomized response query [33, 32]).

Definition 7 (Unbiased randomized response query [16]).

2.5 Graph Arboricity and Degeneracy

Definition 8 (Arboricity).

Definition 9 (Degeneracy).

Theorem 10 (equation 3 and lemma 2.2 of [37]).

Theorem 11 (Chiba-Nishizeki Bound [6]).

3 Node-Reordered Graphs and Their Properties

Definition 12 (low star).

Theorem 13.

Proof.

Lemma 14.

Proof.

Theorem 15.

Proof.

Corollary 16.

Theorem 17.

Proof.

Corollary 18.

Corollary 19.

Proof.

4 Triangle Counting Algorithm

Theorem 20.

Proof.

Lemma 21.

Proof.

Theorem 22.

Proof.

Corollary 23.

Proof.

Theorem 24.

Proof.

5 Odd Length Cycle Counting

Theorem 25.

Proof.

Theorem 26.

Proof.

Theorem 27.

Lemma 28.

Proof.

Proof of Theorem 27.

6 Conclusion

References

Definition 1 ( $\varepsilon$ -edge local differentially private query).

Definition 2 ( $\varepsilon$ -edge local differentially private algorithm [29]).

Definition 5 (Edge local Laplacian query with restricted sensitivity on $\mathcal{H}_{d}$ [4]).