Communication Cost Reduction for Subgraph Counting under Local Differential Privacy via Hash Functions
Authors: Quentin Hillebrand
Vorapong Suppakitpaisarn
Tetsuo Shibuya
Venue: Accepted by TMLR ()

Abstract: We suggest the use of hash functions to cut down the communication costs when counting subgraphs under edge local differential privacy. While various algorithms exist for computing graph statistics --- including the count of subgraphs --- under the edge local differential privacy, many suffer with high communication costs, making them less efficient for large graphs. Though data compression is a typical approach in differential privacy, its application in local differential privacy requires a form of compression that every node can reproduce. In our study, we introduce linear congruence hashing. Leveraging amplification by sub-sampling, with a sampling size of $s$, our method can cut communication costs by a factor of $s^2$, albeit at the cost of increasing variance in the published graph statistic by a factor of $s$. The experimental results indicate that, when matched for communication costs, our method achieves a reduction in the $\ell_2$-error by up to 1000 times for triangle counts and by up to $10^3$ times for 4-cycles counts compared to the performance of leading algorithms.

Published in Transactions on Machine Learning Research (08/2025)
Communication Cost Reduction for Subgraph Counting under Local Differential Privacy via Hash Functions
Quentin Hillebrand The University of Tokyo
Vorapong Suppakitpaisarn The University of Tokyo
worappngg@l..ss.utookooo.....
Tetsuo Shibuya The University of Tokyo
tshibuyaa@hhh @hgc.jp
Reviewed on OpenReview: https: // optpevveew.....w...mmo. net/ forum? id= N1J236mppp
Abstract
We suggest the use of hash functions to cut down the communication costs when counting triangle and other subgraphs under edge local diffcrential privacy. While various algorithms exist for computing graph statistics - including the count of subgraphs - under the edge local differential privacy, many suffer with high communication costs, making them less efficient for large graphs. Though data compression a typical approach in differential privacy, its application in local differential privacy requires form of compression that every node can reproduce. In our study, we introduce linear congruence hashing. Leveraging amplification by sub-sampling, with sampling size of s, our method can cut communication costs by a factor of 82, albeit at the cost of increasing variance in the published graph statistic by a factor of s. The experimental results indicate that, when matched for communication costs, our method achicves a reduction in the fa-error by up 1000 times for triangle counts and by up to 10 times for 4-cycles counts compared to the performance of leading algorithms.
1 Introduction
Differential privacy Dwork 2006 Dwork et al. 2014) has emerged as a benchmark for protecting user data.
To meet this standard, necessary obfuscate the publication results. This can be achieved by adding small noise (Dwork al., 2006) or altering the publication outcomes with small probability (McSherry & Talwar 2007
In differential privacy, it is typically assumed that there is a complete dataset available. After statistical analyses are done, obfuscation is applied to the results. However, there can be leaks of user information during the data collection or storage phases. To address these concerns, a variant of differential privacy, termed local differential privacy (Cormode al. 2018 Evfimievski et al. 2003), has been introduced. Here, rather than starting with full datasct, cach user is prompted disguise their data before sharing it. As result, the received dataset is not perfect. Numerous studies, like those referenced in Li al. (2020); Asi et al. (2022), have aimed to extract accurate statistical insights from these imperfect datasets. The local differential privacy has been practically employed by several companies to guarantec the privacy of their users' information. Those companies include Apple, Microsoft, and Google (Differential Privacy Team,
Apple 2017
Ding et al. 2017 Erlingsson et. al. 2014).
Many studics on local differential privacy focus on tabular datasots, but there is also significant rescarch dedicated to publishing graph statistics (Sajadmanesh Gatica-Perez 2021 Ye et al., 2020).. For graph- based inputs, such social networks, the prevalent privacy standard is edge local differential privacy QQin

---

Published in Transactions on Machine Learning Research (08/2025)
et al. 2017 In this framework, users are asked to share disguised version of their adjacency vectors. These vectors are bit sequences which show mutual connections within the network. For instance, in a social network comprising n users, user would provide their adjacency vector, denoted as a, = [ai,1..... di,n] E {0, 1 Here, dz,j = 1 implics that users V and by are connected, while 0z.j = 0 mcans there is no connection between them.
One widely adopted method for obfuscation is the randomized response (Warner 1965 Mangat, 1994 Wang
et al. 2016 In this approach, users are prompted to invert each bit in their adjacency vector, denoted aid based on a specific probability. However, while the method is straightforward, its application to real-world social networks presents challenges. Typically, in practical social networks, an individual may have at most & few thousand friends, implying that the majority of Oi,j values are zeroes. When employing the randomized response technique and flipping each bit of at based on the designated probability, a significant number of zero bits get inverted to one. This phenomenon can distort the resulting graph statistics considcrably (Mukherjee & Suppakitpaisarn 2023 Mohamod et al. 2022..
Beyond the publication of full graphs via randomized response, there is growing interest in subgraph counting queries under local differential privacy. The challenge was first highlighted by [lmola et al. (2021).
who proposed two key algorithms for k-star and triangle counting. Building on k-star counting, Hillebrand
et al. (023) later introduced an unbiased and refined algorithm. For triangle counting, several notable contributions include Imola et al. (0022a), which addressed the communication cost, Liu et al.
(002
2024b
which delved into scenarios where users have access to a 2-hop graph view, and Eden et al.
20023 which
studies the lower bound of the additive error. For larger subgraphs, He et al. (2024) gave local differentially
private algorithm to count butterflics bipartite graphs, Betzer et al. (2024) gave algorithm to count the number of walks under the privacy notion, Hillebrand et al. (2025) proposed an algorithm to count odd-length cycles on degeneracy-bounde count any graphlet of size k. Moving to the shuffle model, Imola et al (002b)) gave algorithms for triangle and 4-cycle counting. To conclude, Dhulipala et al. (2022) gave an approximation method for identifying the densest subgraph, rooted in locally adjustable algorithmss
graphs, and (Suppakitpaisarn et al. (2025) devised an algorithm to
Most of the works mentioned in the previous paragraph use the two-step mechanism (lmola et al 2021; 2022a b). In this mechanism, users are required to download the adjacency vectors of all other participants. They then compute graph statistics locally using their genuine adjacency vector and the obfuscated vectors of their peers. Although this technique substantially increases the accuracy for various graph statistics, such as the count of triangles, it comes with the drawback of demanding a vast amount of data download. Each user incurs a communication cost of ((??). Given that the user count, n, can reach several billion in real-world scenarios, this download demand not affordable for most.
Instead of using adjacency vectors, users might consider exchanging adjacency lists. This approach involves each user transmitting and receiving only list of adjacent node pairs. If we assume that user can have limited, constant number of friends, then the bit-download requirement for the original graph becomes O(nlogn), n). However, given the surge in edge count to @(n²) due to the randomized response, the com- munication cost associated with downloading the obfuscated adjacency list shoots up to O(n² log This means that, post-obfuscation, the adjacency list fails to offer any communication efficiency benefits over the adjacency vector.
There are several techniques proposed to reduce the communication cost for the two-step mechanism such the asymmetric randomized response (Imola et al. 2022a). the
randomized response Hi- dano & Murakami 2024).. the nogree-prescrving exponential mechanism (Adhikari et al. 2020). or tochnique based on the compressive sensing (Li et al. 2011). However, we strongly believe that the communication cost could be further reduced both in theory and practice.
1.1 Our Contributions
To mitigate the communication overhead, we suggest employing a compression technique on the adjacency vector or list prior to its transmission to the central server.
2

---

Published in Transactions on Machine Learning Research (08/2025)
One madoon
Results froun hoshing function
represeniation
Input Graph
each group
0
0
0
Step 2.1: Grouping
Stap 2.2:
Randomly Select
de
Representative
(Algorihmm 2)
(Algorithm
4/
4x
Step I: Degree Sharing (Algorithm
Stop 2.3: Randomized
Response (Algorithm
5.1. 3.3, = 3.2....
Published Information #1
Stop 3.1: Subgraph Counting (Algorithms
Al Lapi 102, [3
Lap, = 12.1,
+ Laps 10.5. [4], Lap,
Estimated number subgraphs associated each node
0
Published Information
Small fraction
3.2: Agaregate all numbers
bits are flipped.
(Algarithm 3)
Only Hipped publishhd..
1025
Directly obtained from Published Information
heii indices
Published Information 82
the information within the green box represents the data published by users. By the umplification-by-sitt www.bb----bb--spinnneee theorem, the randomized response in Step 2.3 has a bit-flip probability reduced by approximately a factor of 8 relative to the standard randomized response. This helps reducing the error we have in our proposed algorithm.
Figure 1: Overview of our mechanism, GroupRR:
The concept of database compression is not novel within the realm of differential privacy. Numerous mecha- nisms have been developed to enhance the precision of statistics derived from tabular data through database compression using sampling. One of the most prominent among these is the SmalIDB algorithm (Blum et al. 2013). There have also been initiatives that harness the Kronecker graph to refine the accuracy of published graph statistics (Paul et al. 2020
On the contrary, implementing database compression for the two-step mechanism under edge local differ- ential privacy poses greater challenges. Imagine we compress the adjacency list ..., Gi,n]' down "il.::.-.,,,.c... with < n, via sampling, and then disseminate this compressed list to all users. When other users utilize this compressed list for local calculations in the second step, they must be able to replicate the sampling outcome. We therefore need function which can be replicated with small communication cost. This requirement inspired our proposition to utilize línear congruence hashing (Thomson 1958 1960) for the sampling process.
Rotenberg,
Our proposal outlined Figure 1 Using linear congruence hashing, we can evenly partition the node set {Ui...., } into m subsets. Let us denote these subsets SI,..., each having size of s. The index Ge corresponding to the only value from the group sent to the server, is derived from S, with uniform probability of 1/s. Since all data is transmitted from the users with probability of 1/s, we can leverage the theorem on amplification by sub-sampling (Balle et al. 2018) to diminish the bit-flipping probability in the randomized response mechanism by a factor of 1/s. Consequently, the count of non-zero entries in the bit vector [dt.cr...., di,em'' is roughly m/s, which is approximately equal to n/s?. By employing a sampling size of 8, the communication overhead can be reduced by a factor of s2.
While our publication's variance might increase by up to a factor of s for certain graph statistics, our experimental results demonstrate that, for fixed download cost, algorithm can reduce the Ey-error in triangle counts by a factor of 1000.
A valid inquiry might be whether we would obtain a comparable outcome by deterministically choosing the same disjoint sets S for every user v2. While this approach could simplify the algorithm by elimi- nating the need for hash functions, our findings indicate that deterministic set selection leads to a significant variance in the estimations during the mechanism's second step. Hence, using the linear congruence hashing is vital for compression.
3

---

Published in Transactions on Machine Learning Research (08/2025)
The main contribution present in the article is the first purely local differential private mechanism for graph statistics that leverages amplification by sub-sampling. Additionally, we demonstrate the generality of the mechanism and its efficiency as it performs better than state of the art by several orders of magnitudes for several triangle and other subgraph counting tasks.
1.2 Related Works
Hashing functions have been utilized in the domain of differential privacy by Wang et al. (2017) to develop binary local hashing (BLH) and optimal local hashing (OLH) for frequency estimation under local differential privacy. However, the work focuses on tabular information, while our work focuses on graph information. The proposed algorithm totally different because of the difference data structure and privacy definition. Additionally, while the previous method use hash functions to compress user data, they do not support amplification by sub-sampling, which is feature of our proposed method. Thus, our compression rate is larger than the previous work.
A recent study on communication reduction in local differential privacy (Liu et al., 2024a successfully simulated any randomizer for local differential privacy using only (e)) communication bits. However, similar to BLH and OLH methods, their approach depends on the characteristics of labular data and traditional local differential privacy, making it inapplicable to our scenario where edge-local differential privacy is employed.
2
Preliminaries
2.1
Hash functions
Hash functions (Knuhh 1997) map keys from specified key space designated hash space. In this paper, unless mentioned differently, the key space is represented by [J0, n 1|] and the hash space by [[0, m 1l].
We consider a hashing scheme called linear congruence hashing Thomson 1958 Rotenberg. 1960 in this paper. The scheme can be defined as H = (ha.bla E [| p - 1]). E [00 p T]} when p is a prime number greater than n and hx)x(x) = ((ax + b) mod p) mod m. Notice that, for all a, and ke E [[0, m - -1]] we have k} < 2 In other words, the number of key in a given bin either
a
S [x (x)
or [m m
2.2 Edge Local Differential Privacy
Let the set of users be (UI...., }. Each user us has own adjacency list a, = [or.1..... on,l' E {0,1) 1)" where 0r,j = if Uz} E E and az,, = otherwise. For any a af E {0, 1)", let d(a,, af) be the liddistance between the two vectors. To define the privacy notion, we first give the following definition:
Definition 1 (Local differentially private query). Let > 0. A randomized query R is said to be e-edge locally differentially private for node if, for any pair of adjacency lists a, and d' where la, all I and for any possible set of outcomes S, we have that
Pr(R(as) E SS e Pr(R(()) E S].
Then, the definition of the edge local differential privacy as follows:
Definition 2 (Edge local differential privacy Qin al. (2017)). An algorithm A is defined as cedge locally differentially private if, for any user and for any possible set of queries RI,..., R2 which A posed to user i, where each query R2 is edee locally differentially private (for < j S k), the condition El + ... + is satisfied.
In this setting, represents the degree of privacy protection and is termed the privacy budget. A lower privacy budget value indicates a stricter privacy limitation on published data. Each user possesses an adjacency list denoted by ag Before transmitting the result to the central server, they apply the randomized function R. Subsoquently, the central server aggrogates this data using the aggregator A. According to Definition 2, if a mechanism M is e-edge differentially private, significant information of a, cannot be obtained from R(a;) once it is transferred and stored the central server.
4

---

Published in Transactions on Machine Learning Research (08/2025)
One of the most important properties of the edge local differential privacy is the composition theorem. Theorem 1 (Composition Theorem (Dwork et al., 2010 Let Mi....,Mp be edge local differentially privale mechanism with privacy budget , Ep. Then, the mechanism or..... Mi is (e) t..... -p)- local differentially private.
2.3 Basic Mechanisms
Hou et al. 2023 Among them, the edge local Laplacian mechanism (Hillebrand et al., 2023 is an approach to offer privacy when we request each user to give real numbers to the aggregator. The Laplacian mechanism can be defined as in the following definition. It can be shown that the mechanism s-edge local differential private.
Numcrous mechanisms have been suggested to meet Definition 2 [Li ct al. 2022
Definition 3 (Edge Local Laplacian Mechanism (Hillebrand et al. 2023 For f: {0, [0, + R, the global sensitivity of f is A = max [[[(a) - f(a')li. For & > O,
be a random variable drawn from
d(a.e')=1
Lap(e/Ay). The edge local Laplacian mechanism for with privacy budget e is the mechanism for which the randomized function R is defined as f(a) +.
When request users to send vector of bits (such as the whole adjacency vector) to the aggregator, the edge local Laplacian mechanism is not the most suitable. Instead, frequently used method is the randomized
response Warner 1965
Mangat
1994
Wang et al. 2016 as detailed in the following definition.
Wang et al. 20160). For >> 0, the randomized response with privacy budget & is a mechanism which the randomized function R: {0, 1]" 4
Definition 4 (Randomized Response (Warner
1965
Mangat 1994;
{0, 1) function such that R(a........ as,n)) = (RR(a,.))..... RR(a,,n)) where
if ai =1
((RR(aL,)) 1)
Ite
(1)
if aij = 0.
T+ee
2.4 Smooth Sensitivity (Nissim et al., 2007
The traditional Laplacian mechanism adjusts noise based on the global sensitivity, which is determined from the worst possible outcome for selected function. It does not consider the specific adjacency list. Therefore, in certain situations, the global sensitivity might be much greater than the function's changes due to slight update in the real adjacency list. Noticing this, Nissim et al. (2007) created a mechanism where the noise relates to the smooth sensitivity, which varies depending on the instance. Before we define smooth sensitivity, we first need to explain local sensitivity and sensitivity a distance k.
Definition 5 (Local Sensitivity). For f {0, R, the local sensitivity of f on a E 10, is LSy(a) max [[((a) faa')l1 a':d(a,0')
The local sensitivity of on 13" measures the largest change in due to single edge alteration when starting with the adjacency list a. The sensitivity of at distance k expands on this idea by looking at the changes resulting from a single alteration in the adjacency lists that are within k modifications from a. Definition 6 (Sensitivity at Distance k). For f 10,13" + R, the sensitivity of f at distance k at a is (a) = max (ay(
d'=
We are now ready to define the smooth sensitivity. Definition (Smooth Sensitivity). For f a function and B 0, the 3-smooth sensitivity of f at a is () max e (a)
We are now ready to define the mechanism basod on the smooth scnsitivity. It shown that the mechanism is s-edge local differential private.
Definition (Smooth Sensitivity Mechanism). Let y and h(2) be a probability distribution proportional to 1/(1 + {=]?). We will denote Zy the random variable drawn from h. For 0 and the smooth
5

---

Published in Transactions on Machine Learning Research (08/2025)
sensitivity mechanism for f, denoted by M, is a mechanism with the randomized function R(a) f(a) + 41 $ S.e/7 (a) Zz.
This result was later improved in Yamamoto & Shibuya (0023) who proved that R(a) could be changed to f(a) + 27 //////11)) (a) Zy.
The mechanism operales effectively for all values of 7 > 1. Nonetheless, it is important to highlight that when y I 3, we do not know way to calculate the variance of the random variable Zy. Consequently, we will adopt 7 = 4 for this article, where the variance of Zy is one.
3 Previous Mechanism
Let suppose the the original graph is G EV when V= =
Un) is set of nodes or users and E C ((,,v) u, E V) is set of edges relationships. We can publish G using the randomized response mechanism defined in the previous section. Given that d'.= RR((t,) obtained from the randomized response, we can define a graph G' = , E') with its adjacency matrix given by A' = (d()))
One can determine the number of subgraphs in G' by counting them; however, this method introduces a significant error (Imola (C((C)
et al. 2022a). Specifically, the error magnitude O becomes prohibitive decreases, particularly when aiming for higher levels of privacy.
g² + /o which is large in relation to and
3.1 Two-Step Mechanism
To mitigate the error, Imola (2021) introduced a two-step mechanism release the count of triangles. A tuple of three nodes, represented as (14, Uy (2) where i > h is triangle if (u, vj}: {or, (x , (1g, 0g) E. We denote the set of triangles in G by Ac. Furthermore, for tuples in Ag where the initial element is ua we denote them A, We have that | = Σ|A
The first step, represented by Mi, involves releasing the obscured graph G' = EV, produced by the randomized response. In the second step, represented by M2, every user v, provides an estimated value for Ail that is based on both the real adjacency vector a; and the distorted graph G Let A = {(v) uk) {or, u/}, (u,, { E E, (uj, vk E E", and > The randomized funtion of M2, represented as R2, aligns with what is used in the edge local Laplacian mechanism. Specifically, users are asked to add Laplacian noise into f(a)). The mechanism's aggregator then sums the outcomes derived from these randomized functions.
k}. Consider function f defined as f(a:) [A
The two-step mechanism can significantly increase the precision of the triangle counting. However, it has a large variance. Consider i > j > & such that uy uy,, veh, (o,, {ve, vx E and {0,,8k] & E. If, by the randomized response, {u,, vx E', that would contribute two to the number of triangles. When the input graph has a large number of C4, the variance becomes large. The authors of al. (2022a) propose technique called four-cycle trick to reduce the variance. Define A {(e,,", uk) E A {0r, v& G'). Instead of having f(;:) = [A], they use fa::) |A For the rest of the article, we will use ARROne to denote the version of ARR that uses this 4-cycle trick.
3.2 Communication Cost
In many real-world social networks, each user is typically connected a constant number of other users (Barabási 2013). This means the number of connections (or 'ones' in the adjacency list a;) is lot fewer than n. So, instead of sending their entire adjacency list to the aggregator, user e; can just share the list of those directly connected to them. This approach reduces the communication cost from n bits down to @(logn).
However, when using randomized response mechanisms, every bit in ag has a constant probability of being flipped. The resulting adjacency list a' will have roughly O(n) ones. So, the communication saviiiiooo-siinggggg technique mentioned earlier will not work here.

---

Published in Transactions on Machine Learning Research (08/2025)
parameters of the hashing functions (Line and 3 Algorithm
noisy degree (Line of Algorithm obfuscated edges (Line Algorithm 2)
Server
User
aggregated obfuscated graph (Line of Algorithm 2)
noisy degrees of other users (Line of Algorithm 1)
local unbiased count noise (Line of Algorithm
Figure 2: Details of the interactions between each user and the server during the execution of our mechanism
The situation gets more difficult with the two-step mechanism discussed earlier. In this approach, each user needs to access the entire distorted graph A'. The user e camnot choose to access only the edge {ey, us such that (2, vy). fe, 2 E E as that will reveal the existence of those two edges. This means they have to download the whole distorted graph, which requires about ((n²) bits. Such a cost becomes unrealistic for social networks with millions of nodes.
The four-cycle trick mentioned in the previous section can help reducing the communication cost. As a triangle (uj, Uk) A" only if [R E F', user about whether {ug, 3 E' or not when {2r, v&} & E'. Still, we think that the savings from the trick are not substantial enough to make the two-step method viable for big graphs.
calculate | without accessing the information
4 Our Mechanism: Group Randomized Response
In this section, introduce mechanism designed for publishing graphs in distributed environment under the edge local differential privacy. We have termed this approach the group randomized response (GroupRR). The mechanism is a three-step process:
1. Degree Sharing Step: In this step, each user shares their degree protected by the local Laplacian mechanism.
Group Randomized Response Step: In this step, a sampled adjacency list is published by each user. First, nodes and edges are categorized into groups using the linear congruence hashing function. Then, one value is sampled from each group and only this value is obfuscated and sent the central server.
Counting Step: Subgraphs are counted based on the information from the represontatives. Then, each user shares the number of subgraphs protected by the local Laplacian mechanism.
Figure [ provides an overview of the various steps of the mechanism, while Figure emphasizes the commu- nication between users and the central server.
Thanks to the sampling created by the formation groups, this mechanism achieves a notably reduced communication cost. Moreover, the privacy budget amplification from sampling (Balle al.] [2018) fur- ther decreases the probabilities of bit-flipping during the randomized response phase, further reducing the communication cost.
4.1 Degree Sharing Step
During this step, each user i calculates the count of their connections, specifically d, = [ <i: (i,)) E E)I We call d, low degree in this paper. They then share the low degree using the local Laplacian mechanism

---

Published in Transactions on Machine Learning Research (08/2025)
with the privacy budget of Eu- The shared count, denoted by d,, will be used only for adjusting bias in the fourth step. If there are lot of users (n is large), any errors from this count are minor even if a large Laplacian noise is added. Thus, we can choose relatively small value for so. This step is described as in Algorithm
Function DegreeSharing
Input: Graph = (V, b), privacy budget Eo
Output:
Estimated degree d, of each user
[User Calculate and send d; + d; + ) to the central server
Algorithm 1: The first step of our proposed method, degree sharing step
4.2 Group Randomized Response Step
The goal of this step is to publish an obfuscated adjacency list in a communication efficient way. Our solution is form random groups of edges that are of similar sizes. It crucial that this randomization can be reproduced, and that the division is easily shareable among all participants. To achieve such a grouping that meets these criteria, that grouping is done, one value is sampled per group. This value is then obfuscated with the randomized response mechanism and broadcasted. This step is described in Algorithm P
employ the linear congruence hashing, which is discussed in Section 2 Once
At Line of the algorithm, the central server calculates p E N, which represents the smallest prime number greater than n, the graph's size. Then, at Line 3, for each node &s when E [] nl], the server randomly generates two values: 6, from the range [[1.p- 1[] and Φ; from the range [[0. - 1[]. These values act as coelficients for the linear congruence hashing. After generating these coefficients, the server shares them, along with p, with all users.
Recall the definition of hap in Section Let E N be a parameter called sampling size which will be the size of each group, m be an integer such that m = [p/s], and let h₂(j) = ha. (i) = ((0,-j j +x) mod p) mod m. At Line 4, each user v classifies the set of users {v1,... vn into m disjoint groups, denoted by S.,...., The group S can be defined as {u, hz( = t}. By the property of the linear congruence hashing, we have that 1 < | S s. To make sure that all the sets have size s, we add a dummy element to all Sr, with size 1. There is edge between i; and the dummy node.
At Line 5, we then choose representative for each group, S.,- Every member of the group has equal probability of being selected, which is 1/s. Let us call the chosen member from group S as Ve., When is chosen from the group containing k, we will employ the notation (,,,,(k) == aie, for convenience. Only the value of the representative edge ag., is published via the randomized response mechanism, and the actual selected index et is not shared. We introduce this quantity only to simplify the description and analysis of the algorithm.
It should be emphasized that even though the hashing cocfficients are determined by the central server, this does not pose privacy risk. This is because the hashing functions are employed to form groups that are intentionally public. The privacy-sensitive element is the representative value chosen for each group, and the selection of these representatives does not involve the hash functions.
Each user then sends the values 0i.er...,, 0s,e, to the aggregator using the randomized response mechanism with a privacy budget of e' In(1 + s(eft- It notcworthy that this privacy budget, e', considcrably greater than the ει budget used in the traditional method. This results in much smaller probability of flipping bits in the adjacency vector.
The obfuscated values sent from v to the central system are denoted as ............ ............ d'......,d'a. E (0, The aggregator then releases these values, making them available for each user in the mechanism's final step. In the earlier approach, users had to know the list of vy such that df., = 1. Now, they only need to know the list of t such that d'c, = This significant reduces the number of bits users have to download from the central server. We will conduct the analysis on the number of bits which each user needs to download in the next section.
8

---

Published in Transactions on Machine Learning Research (08/2025)
To ensure that each edge is published only once, each user only publishes connections with users who have smaller index than their own. To enforce this condition, in Line 6, we assign d',c, to zero when is greater than i.
Function GroupRandomizzeRRspppsss
Input: Graph G = EV, sampling size 8, privacy budget E1
Output: The grouped and obfuscated adjacency list (d'.e,)...,, d.c.. for each user
[Server] Calculate and broadcast, the smallest prime number larger than
[Server] For all i nl, randomly select and broadcast (0,, 6,) from [1. - 1] x [0,p- pp-1]
[User Recall the definition of ha,b Section 2 Let m be an integer such that m [p/s], and let
h+(i) he (j) ((0, j Φz) mod p) mod m. For each & [,, Sat {oy h₂(5) = (];
[User Choose randomly Ve, from the set Si,t
[User i] For all E [1, ml, if e i, ai,e, 0;
[User Perform the randomized response with privacy budget e' = In + s(cfi 1)) on (0s,0110... ai.om)) )- The result. (d'.e,,.... d.ccm) is then broadcasted to all users (We note that only d/,,, for all S i m is published. The index q is not.);
Algorithm 2: The second step of our proposed method, group randomized response step
4.3 Counting Step
The final step of our method is outlined in Algorithm 3 In Lines 2-3, we update the value of af,c, to arec, = Wi d'.,, -, In the next section, we will show that this adjustment effectively removes the bias in our subgraph counting. We then use the value ārc, to estimate the number of subgraphs associated with each node. The calculation method varies depending on the specific subgraph. In Line 4 of the algorithm, modify this line to calculate other graph
detail the process for triangle counting. However, statistics. Following this, in Line 5, we apply either the local Laplacian mechanism the smooth sensitivity mechanism to obfuscate the result from Line 4 before sending it to the central server. At Line 6, the central server aggregates the results received from all users and publishes the summation as the final counting result..
It crucial to understand that we not assume the degree d, is public. Rather, we utilize an estimation of d,, referred to as d,, which is disclosed in the initial step of our mechanism, for the calculation of o Line 2 of the algorithm.
Function Counting
Input: Graph = (V, E), grouped and obfuscated adjacency list (ak af...)) ), privacy budget
E2, estimated degree d, of each user.
Output: The est.dd number of triangles in the graph
[User i] Calculate ō; = - -ー ms-1 m-I: wi
s''+1 ma-1.
e- m-
[User For < t m, calculate ăz,e, = wi de ōz
[User Let W, = k): :j < l < and (v, vy). (o,, mx E). Calculate |
Σ āg,h(())
(i.))E;
[User Obfuscate the value of | using the local Laclacian mechanism or the smooth sensitivity mechanism with privacy budget 62. Then, submit the result to the central server;
[Server] Publish the number of triangle as E, |
Algorithm 3: The third step of method, counting step, when it is used for publishing the number of triangles

---

Lemma 1 (Amplification by Sub-Sampling under Edge Differential Privacy Balle et al. 2018)): ). Let > 0, and define m = [n/s]- Consider a randomized sampling function S {0, 1 - {0, 1) pm such that, given E {0,1}", the output Slai...., = (aq....,am, where each de is determined as Published in Transactions on Machine Learning Research (08/2025)
5 Theoretical Analysis of Our Mechanism
5.1 Privacy
We begin by analyzing the privacy guarantees of the group randomized response step (Step 2) in the following lemma. This analysis leverages the amplification by subsampling technique (Balle el al. 2018), defined as follows:
an input
follows:
For each S. < m, the output de is sampled uniformly at random from the i-th block of size i.e., from indices {(i - 1)8 1, ,,...,üs is}. That is, for each j E {(i - 1)8 1.....,.g) ,is,, we have af = =aj aj with probability 1/s.
For i = m, let the final block be {(m - 1)s + I,...., n), which may contain fewer than elements. Then, for each j E {(m - 1)s 1, 1,..., m), we have d'm = aj with probability 1/8, and d' = 0 with probability
Let M be randomized algorithm satisfying the following privocy guarantee: for all a, {0, 13"h such that
la à $ 1, and for all set S,
Pr[M(a) E S
S Pr(M(a) ES
Se.
(2)
Them, for the composed mechanism M o S it holds that for all a, à E {0, 10, such that Ja - al s 1, and for all set S,
Pr(M(S(a)) S
(3)
Pr(M(S(a)) ES
where Es is given by E, in (1+
The amplification by sub-sampling technique was originally proposed in the context of central differential privacy, where each a, represents sensitive information of user i. It has not been previously applied to either local differential privacy graph statistics. The assumption in (2) requires that M satisfies e'-differential privacy, and the conclusion in (3) shows that the composed mechanism achieves e,-differential privacy due to the sampling. To the best of our knowledge, we are the first to apply amplification by sub-sampling in the setting of local differential privacy and graph statistics. We consider this application to be one of the main contributions of our work.
The privacy guarantee of the group randomized response step (Step 2) of our algorithm follows from Lemmal 1
Lemma The privacy budget of the group randomized response step is E1.
Proof. We begin by observing that the computation of (dr,q....,, di..... in Lines 4-6 of Algorithm 2 can be viewed as a sampling procedure S, as described in Lemma [ followed by a reordering step, which does not affect the privacy guarantees of the mechanism. The randomized response mechanism applied in Line 7 satisfies the privacy bound given in (2). Consequently, the overall procedure in Algorithm 2 which composes sampling with randomized response, satisfics equation (3), thereby ensuring e,-odge local differcntial privacy
defined in Definition 5 Substituting e' In(1 + s(e 1)) into the expression for In(1 + = we conclude that e, = and the privacy budget of the group randomized response step is E1.
We provide the following example to illustrate how this amplification is achieved.
Example Consider the publication of node vy 's adjacency list using the group randomized response. We will analyze two cases: (1) vp is connected to none of the n other nodes, and (2) vo is connected only to
10

---

Published in Transactions on Machine Learning Research (08/2025)
Vi. Additionally, since the groups created by the hashing functions public information and independent of the privale adjacency list, we assume that is is in So,t for both cases.
Let and p2 represent the probabilities that d',,,= =1 in scenarios (1) and (2), respectively, when using the randomized response mechanism with a privacy budget e'. In case (1), ai,, is never equal to 1, as no nodes are connected to vg- By the property of randomized respoonee pt Itee". In case (2); di,e, equal to only when is selected as the representative of group Su.t (note that this information is not disclosed). Thus,
di,e, =1 with probability : We have P2 p==-1 Iter' + Itee' We then derive that = = (6'-1) By selting ει such that e' = privacy, with 2 /s/s, demonstruting the privacy budget amplification.
s-1 1
1)), we oblain 12 = This shows that we achieve e -idifeerential
The final result of privacy analysis is shown in the following theorem:
Theorem 2. The privacy budget of our mechanism Eg + E1 + 82.
Proof. We directly obtain this result from Lemma and the composition theorem (Thcorem
5.2 Expected Value of 0z
In the subsequent theorem, we discuss the expected value of ai,., The theorem reveals that when estimate from the counting phase is a linear composition of ar,ces it remains unbiased. The triangle count estimation in Algorithm 3 is an example of these estimations.
In the following, we will restrict our analysis to the values of (K,,, where j > k. This does not pose any limitation, as aj can always be estimated using either (g, or (g.aadd) Therefore, for the remainder of this section, will assume that j k.
Recall that d, denotes the number of connections between u, and nodes with smaller indices, which we refer to as the low degree of 0z-
Define
Pp. = Pr(ag,,,(8) = aj,k = =1},
which evaluates to
1
Pp. 8
ms
8
Let
P/.. = PrId = aj,b = 1],
which is given by the randomized response mechanism as
1 - Ppd 1 Ex"
Pp. It
Poá
Similarly, define
8
d;
Pa.: = Pr(aj,,,()) = 1| Og1 =
1
and let.
Pbo = Pr(al,n,(4) =1 |aju 0],
which satisfies
+ 1 Patt
P1. I It Pa,i
1 1 ee
In the next lemma, we show a properly of w; and o; calculated in Algorithm 3 From now, denote E by dg.
pL. Lemma 3. For all i, Wi = F/,, 1 Po, and 0; py Pla

---

Published in Transactions on Machine Learning Research (08/2025)
Proof. We have
1
Ppp. Pa,i
(pp.)
Pa.i)
-1
1
1-1
Simplifying the expression gives
6"
+
ms8
=: Wi.
P/p.i
Pn,
e
17
On the other hand, we obtain
Ph.s
8 1-1
di
+
7118
8
Eld.])
ms
=: Ci.
P/n Vaa.
ms
6 - m
me
e -
778
We are now ready the proof the main theorem of this subsection. Theorem 3. For all j,k nh, the expected value of (z,,y(h) equals ag,k-
Proof. When ajsb 0, the expected value of āz,h; (k) is given by
E [āg,b((R) ag,k = 0] = (w) - -,,) Pa, o, (1 - (1-Pag) = W/ Pas - -0 0=0=000 =
Similarly, when 03Ah 1, we have
E [1,,)(+)) agAA 1] (w) - -r,)= -Pp.s -0, (1 ---p))) W/ ppp -o =
5.3 Variance of as,c.
The previous section demonstrated that our mechanism gives no bias for cerlain specific publications. In this subsection, show that the variance of our mechanism is also quite minimal.
We use the following lemmas in the analysis.
Lemma For any j. k. P (a' (22ns(s) = =1) 214+
Proof. We have On the other hand,
Pr (0,,,(K)= =1 aj,a =0] -P'a,s = oj
Wj
Pr d (2))(()) = =1 agi = = =Pps =
1 1
Wj
In Lemma and later, we work under the assumption that d, < m 23 n/s. This assumption is reasonable for large class of graphs as the maximum degree can often be inherently limited by physical or practical consider graph representing physical interactions over the past two weeks
constraints. For instance, relevant in contexts such as epidemic modeling the number of interactions any individual can have is bounded and cannot approach the size of the global population. Another example is the case of Facebook that imposes user Chandler (2012). Additionally, given that the objective of this article
hard cap of 5,000 friends is to mitigale the increase in communication overhead caused by privacy measures, this assumption aligns well with our intended use-case. Notably, should d, exceed m, the communication cost associated with our method actually becomes lower than that of the corresponding non-private algorithm. To better under the consequence on the accuracy when that assumption is violated, we conducted experiments on power-law graphs in Section 7.1.5
12

---

Published in Transactions on Machine Learning Research (08/2025)
Lemma 5. For all i such that dj < m, w, = ( and o, = 0 - (
Proof. From the relation e' = 1n(1 + s(e - 1)), it follows that
o -1 s(st - 1).
Therefore, we obtain
2 + s(c 1) s(EF) 1)
wi
0
m7
ec
Moreover, under the assumption that d; < m, we have
1 0 < e -1 m +
1
1
1
m - + +111
0
s(e51 - 1)
m 1 e
eci -
We consider the variance of the variable (K,) in the next theorem.
Theorem 4. For all j such that dj m, the variance of (z0,(K) is O -pe +
Proof. We begin by analyzing the variance of the binary variable (,)) Since it takes values in {0, 1}, we apply Lemma 4 to obtain
=1]) Var (ohAA,c))) = Pr [cb,,,0)) -1] (1- (1-Pripe (r(ch,,,11 = = (
(00)s t
(1 (1-
ajit +
1 1
<
Wj
wi
Wj
Next, using Lemma we bound the variance of the estimator (g,n,(k) follows:
Var (k) (k)) Var (wrdhnn(s) +o.) Var (dsn,(2)) + Var (ōs) S wyy(1 + +o,) +
8
2
ms
c
Therefore, we conclude, using the assumption that for all j, dy < m and Lemma that
Var (k),,,()) =0 ( 1)2 + n²E0 1
It follows from Theorem 5 and subsequent theorems that the variance component associated with e domi- nates the component associated with Eg. The de-deneddnnt term scales as 1/n² and is therefore negligible on large networks. Under a fixed privacy budget e = en + é1 + E2, this suggests setting &o & & to minimize vari- ance. On the other hand, the sensitivity of the counting step and the error introduced at Line 5 (Laplace or smooth sensitivity)-can be large for certain networks; accordingly, we recommend choosing E ss 52.
In Section 5.5
will elaborate that (H,,,K) cut the communication cost by factor of s2 in contrast to
using the direct randomized response results d' Given that the variance of a',, is known to be 11)
the previous thcorem suggests that, while we manage decrease the communication cost by factor of s2 this is at the expense of amplifying the variance by a factor of s. In the upcoming section, we will demonstrate that, for set communication cost, this mechanism yields considerably reduced variance.
13

---

Published in Transactions on Machine Learning Research (08/2025)
5.4 Covariance of Variables
In situations where the goal is to sum up specific estimatons, like in subgraph counting, covariance emerges between these estimators. The size of this covariance is addressed in the subsequent theorem.
Theorem 5. Assume de < for all i. The covoriance of the estimators (j,,((M) and ag Ng(()) in o (mteri-))) when j j and k, k' <j. Otherwise, the covariance of the two estimators is zero.
Proof. When j H j', the two estimators computed from disjoint sets of random variables and are therefore independent.
When j j', the estimators (1k))(1)) and (k)) are identical if k and k' fall into the same bin, i.e., hy(k) = hk')). We denote this event by C which occurs with probability
Pr (3)
--1
As a result, for k, < <j
Cov (1),, = w/ Cov (0) = w/ (B(Ghnnas)
[obancwss)
We consider the conditional expectations E ( 1 1 k,k'
and E (o clul
Recall from the previous section that
dj + aj.k
1
Pr [1),,)())) =
Multiplying both sides by ms-1 yiclds ms-2
ms Pr (R) s ms
dj
mi 1
8-1 dj Dj,k
0j.
+
aj.h
ms
s(ms 2)
ms 2
ms
Let Pı= = Pr (2),(()) = = (()
cli) R,K
Then,
Pjk
d 0.. Oj.k''
ms Pr [a),n(8) =1]
Pk
- 2
2
It follows that
Pr [obn,,)) = and ((,,, =
Ph: e²
1 1- Pk x PW ex' +1
ee' -1
+ 1- Pk
k.k'
ex +1 ex¹ +11
e +1
ms 1
IE (d)),,(1)) E [obinstass
ms
Hence, for s s23 (which is always satisfied in practice),
Pr
(()))
E
(o),, (0) - E (R)) E [obin,cws] 5
k.k'
Thus,
Cov (āz,n, (,,,()))) < w/ (hs clib Pr (c())
14

---

Published in Transactions on Machine Learning Research (08/2025)
Let pzz = Pr (g) = =1 c(
R,Kk Then,
-- d 0j ajæ
pk
< Pr [a),)s(k) =1] Pr (ash)(0)) =1]
8
8
m88
It follows that
E [aahnn (1),,
(( k,kk
S B (1),,1(3) +I [dginssnn]
Using Lemma
4 and Pr (ckk)) Ts obtain
ms w/ + [zz))= =0 n((éil 1)2
8-1 1
g²
Cov (35h,000)) 52
When 8 < n, the covariance the previous theorem is significantly smaller than the variance calculated in Theorem 4 While the variance of the summation includes more covariance terms than variance terms, we will demonstrate in the next section that the contribution from the covariance terms is not substantially larger than the that of the variance terms in Theorem 4
5.5 Communication Cost
The final aspect will examine regarding the mechanism's efficiency is the communication needed for graph aggregation and distribution to each user. We will particularly look at two metrics: the "download cost" (the average number of bits the server transmits to each user) and the "upload cost" (the average number of bits each user sends to the server). Our analysis will offer approximate values under the assumption that the graph is sparse, meaning the number of edges (l is much less than the square of the number of vertices ([V)2).
From our discussion in the previous section, it is evident that the majority of the upload cost arises from the randomized response step, while the download cost primarily stems from the counting step. Therefore, in this analysis, we will disregard the costs associated with the other steps. Theorem 6. The upload cost of user vi in our mechanism O ( log 4
Proof- Recall that, in the randomized response step, each v. submits binary vector (a/,e..-.... :......... deaml e {0, 10"h where set (t dh,,, = 1} S m... If entrics in the vector are equal to one, the communication cost is L logom & E log(n/s).
n/s. To reduce communication cost, the user may instead transmit only the index
We now analyze the expected value of l. Since each as is sampled into the vector with probability 1/s, and noting that e²' -1= s(e - 1), we obtain:
Ee'
1 d + 8²( 11) (n - d,) = =0 ddg
1
E(A- = 1+ 65'
d, + 1 o² (n - di)
8 1)
7
Next, we consider the download cost for our mechanism.
Corollary 1. The download cost for all users is O (log
(6
Proof. Since each user must download information from all other users, the total download cost is
Σo log 11 (7)
( dg
s -
); o (log
(")
n
E
n²
11)) ))
2 - 1)
8
where |E| E. di is the total number of edges.
15

---

Published in Transactions on Machine Learning Research (08/2025)
When E = (n), the upload cost is ( log n)) and the download cost is logn) Recall that the com- munication cost in the two-step mechanism (nn²). Therefore, our technique reduces the communication cost by factor of s².
6 Use Case: Triangle Counting
While our GroupRR mechanism is applicable to the counting of various subgraphs, the majority of prior work work-such as Imola al. (2021 2022a]; Eden al. (2023) has focused specifically on triangle counting under local differential privacy. To facilitate direct comparison with these existing approaches, we also focus triangle counting in this scction.
In Subsection 6.
analyse the estimation loss introduced by our mechanism, excluding the effect of Line 5 in the counting step of Algorithm 3 where noise is added via either the smooth sensitivity or local Laplace mechanism. In Subsection 6.2 we propose an algorithmic refinement aimed at further reducing this estimation loss for triangle counting. Finally, Subsections 6.3 and 6.4 are devoted to analyzing the noise contribution introduced the final step of the algorithm.
6.1 Sensitivity and Loss of Our Mechanism
In the counting step of our mechanism, each user es estimates A when A; = ((ui, Uj, uk) : k < j < &, (y), {v,, Je {Uy, v&} E E}. The number of triangles in the graph G, denoted by A then the (g,,,(K) added with the sum of all Aa]- The estimation of | in our mechanism is A == (A.))
Σ
Laplacian noise when the variable (A,,,() (k) is defined in the previous section. The variance of our mechanism without the noise in the final step of our mechanism is shown in the subsequent theorem.
Theorem 7. Let S2, C4, and W4 denote the number two-stars, four-cycles, and walks of length four in (g,n((K) is bounded by
the graph G, respectivcly. Then, the variance of the estimator Σ,
o (
(S2 Ca Ca+ $ n .W.))
(e51 - 1)2
Proof.
The variance of the estimator E; Σ (k,) can be decomposed into the following three J.N.tiJiiieEE
components:
Variance of individual terms: From Theorem 4 have Var (ā),,,())) (,-ー))))) As there S2 such terms (one for cach two-star), the total contribution from the variances is
o (
S. (e5l (051- 1)2
Covariance due repeated terms: term (g, may appear multiple times in the summation if there exist i, > > k such that {i,s), (i, k), (i.j). (i, E. Such configurations correspond to four-cycles, of which there at most Ca. From Theorem 4 cach such repeated term contributes
to the total covariance, yielding a contribution bounded by -リp
8 Cs o ((0-))) 11-1 )
Covariance between distinct terms: Dependencies may also arise between distinct terms az., and (K)) if there exist. > k and it j. k'' such that the edge sets (i.j), (i,k), (f.1), (1, E
16

---

E. These configurations correspond to walks of length four involving shared center nodes. There are at most W4 such configurations, and each contributes O 11e to the total covariance, resulting in an overall contribution of Published in Transactions on Machine Learning Research (08/2025)
o
82 . W4 n((es 1)2
Combining all three components, we conclude that the total variance is
o (101 8 - 1)2 (52+ Ca+ n
W.)
6.2 Further Optimization for Triangle Counting: Central Server Sampling
We believe that the variance detailed in Theorem is comparatively minimal. Nevertheless, specifically for triangle counting, this variance can be further reduced through a method we have termed "central server sampling." The specifics of this technique will be outlined this subsection.
6.2.1 Modification
Remember that through the GroupRR mechanism, the server acquires the set E. {t d',c, = 1] from user U; following the group randomized response step. This set is then shared with all users at the start of the counting step. As identified in the prior subsection, this approach not only leads to significant communication substantial covariance in triangle counting. To address these issucs, we suggest (. from & independently, and then distributing the subset g(6) to user uy An element in & is independently selected for inclusion in <(() with a constant probability, which we denote Plc- The central server sampling is described in Algorithm 4
costs but also contributes
generating subsets E(L) ,,
Function CentralSampling
Input: For all user j, the grouped and obfuscated adjacency list (........... d'...,.,.,,.. obtained from the randomized response step, central server sampling probability pc
Output: For all user i,j, the grouped and obfuscated adjacency list for user j, which user i will use for counting the number of triangles in the counting step, (a ..., (.em)
[Server] For each i, 0 0 if d/y 0. If alya, 1, 1, 0j.c 1 with probability Pe, and 0 0 with probability 1 1- 1-Mo-i
(4)
Ma-i
[Server] Send (0),0 .... j,.n user i.
(1)
Algorithm 4: Central Server Sampling: This process is exccuted between Step 3 and 4 of the GroupRR mechanism
Let (0) (K)y()) {0, 13 is random variable indicating if hyykk) E The user vs believe that there is an edge {oy, vx in the graph G if (2)
(M) 1. We have that IE (2)
(N) Me [obSA)(00] for all i, k.
Recall the variables wa and o; defined in the previous section. We define (),,(10) wt (j,h((k) ō.. Theorem 8. The variable (1)
(k) is an unbiased estimation of ajkk-
Proof. By the definitions and Theorem we have
E[a (1))
Pe Ela (10 [(o.]
Bld [[ōo]] aj,
17

---

Published in Transactions on Machine Learning Research (08/2025)
From the previous theorem, our unbiased estimation of the number of triangles under this modification is (6)
then |
( (R) added by the Laplacian noise or the noise from the smooth sensitivity
Σ
mechanism.
6.2.2 Variance of the Modified Mechanism
We first consider the variance of (0) Theorem 9. Var (1) (m) = 11
(k) in the subsequent theorem.
Proof. Since (K) is a binomial random variable, Lemma implies
Var (o (1)))(s)) = Pr a (M) = . (1 Pr
(0)
=1]
a (h)
Pr (2),)((k)) = 1] (1 - Me Pr (<),,10)== = 11)
1
S Me Pr (2)))(())) 1 $ Mc Wj
Then, by Lemma 5
we have
Var (7.00
wp Me
Var (c) (oihs()s) + Var (ā:) S
1
1 +
$2
(.))
Hec Wj
n
Therefore,
8² n2ed
Var (6
(05h)(0))=
(e(
+
At first glance, when contrasting this outcome with the findings in Theorem 4 it might appear that employ- ing central server sampling amplifies the variance of the estimations, potentially diminishing their utility. However, it is important to recognize that for a communiattion cost reduction by 1/Me times. Additionally, in the same way the four-cycle trick in Section 3 the central server sampling can reduce the covariance stated in Theorem | In particular, it significantly reduces the covariance for the graph with lot of walks with length four (or graph with large number of W1).
Theorem 10. The covariance of (6)
(k,((k) and a (i')
(yye) is (s/(er) - 1) when = i 1l and k = k,,
1)))) when j j= J', # i' and < and O (s2 (pen/e 1)))) when j = j', and (s22/(((e 1annn-133 (0(0//nnn111>>
k,k' <j. It is equal to zero in other cases.
Proof. When i the two estimators are based disjoint sets of variables, and the server sampling step is conducted independently for each group. Therefore, the estimators are independent.
and (1') i + i,, and k, k' <j, the sampling steps for ((6)) (M) (,,)(K)) are independent. Hence, by When j j',
Theorem 5
Cov (6 (K))
(00) (())))))) < Cov (āg,n, ann, = ni(ei 1)
52
Similarly, when j j', i 8 and k = W,, Theorem gives
Cov (1) Shagpp (1h,00) < Var (a).k, =0 (
(e0t 1)
18

---

Published in Transactions on Machine Learning Research (08/2025)
Next, consider the case when = j', i= i', and l. W j. We distinguish two subcases depending whether hy(kk) hy(k). Let c denote the event that h₃(k) = h2 (k'). By Theorem
a (nn E
Var (a(t) (x)
=0 Mo(ee - 1)2
k,kk
In the case (k) * (k'), we obtain from the proof of Theorem that
IP E.
E (0
(9) (1))
k,k'
(3) a
(1))
a (1h) $
Therefore,
Cov (ala (o)
(,,
SP (P(())))
PP
(3)
E
(1) I 1
s² ( Men(efi 1)2
=0
Using the previous two theorems, will quantify the variance of the triangle counting algorithm performed using GroupRR and central server sampling. We describe in the next theorem this variance prior to the addition of the Laplacian noise in the final step of the mechanism.
Theorem 11. Let S2, S3, C4, and W4 be the number of two-star, three-star, four-cycle, and the walk with length four in G. The variance of estimator for triangle counting using
the GroupRR and central server sampling technique, denoled by Σ ( ( E D (ideornss (,,, is
0 (M (S2 + CoCs + Mad Med W4 ;,5s))
Proof. The variance
Σ
Σ
(k))
can be eeeoomoosed into four components:
Variance of individual terms:
Σ
Σ
Var (1)
(R)))(R))
j.k
By Theorem 0 we have
Var (760 (athh,(s))= =0
8
peles1 - 11}
Since there at most S2 such terms in total, the overall contribution 0
3:82 (e
Covariance from repeated index pairs {i, k]: This arises from the covariance between à (1)
j.A, (l)
and (i") (k) for i, j > k such that {us, Vi {us, vk}. {uy, Uz}, and {ur, 2x are all in E. By
Theorem 10 the covariance bounded by O
[--1-13 and the number of such co-occurrences is
a
at most C4. Hence, this part contributes 0
s.C, fe1-1y
19

---

Published in Transactions on Machine Learning Research (08/2025)
3. Covariance across different * i': This refers to terms a (,) and a(1))
(ig(())) where i * i' and there cxist i > j, k and i' > j.k' such that {us, tyt, fez, h, fuy, 1y (uy, E E. Each such occurrence contributes at most O (
and the total number of such cases is bounded by 3 W.
W4; leading to total contribution of O
m(e-1-1)3
4. Covariance within the same i: This arises from pairs a (M) and (0) (e)) for fixed i and j, where i j and the edge set contains (u, uy). (ur, uk frr, okr) E E. Each such pair contributes most
0 - ) and there are most S3 such cases, giving a total contribution of O (Men(ef--133)
x²
,2,83
Let us compare the variance derived from the GroupRR as outlined in Theorem 7 with that obtained from GroupRR combined with central server sampling, as detailed in Theorem II particularly for graphs with numerous walks of length four. In such scenarios, the term Wa becomes the dominant factor the variances of both methods. We find that the constant associated with this dominant term is identical in both variances. This observation suggests that while achicving similar level of variance, can also reduce the download cost by factor of 1/pe-
6.3 Smooth Sensitivity for Triangle Counting
We calculate the sensitivity at distance k (defined in Definition 6 for the triangle counting. First, let consider the local sensitivity (defined in Definition 5 for the adjacency vector a' E =0, (denoted by (a)() As previously discussed, the maximum change in the count
Σ
a (hy( when one bit of al
is updated is no more than
UBis(d') max )
Σ A:af=1
(0) (h2
Σ
(4) k)
A:a
When a is the adjacent vector of user i and d; is the number of ones in the vector, the number of ones in the vector with la - a,l is not more than ULss((a;) (a:) k-w, Hence, the sensitivity at k of the vector das denoted by (a,) is no more than O (UBBss()) + ky A411). Combining with Theorem 11 we obtain that:
Theorem 12. When using the smooth sensilivily mechanism, the variance of our eslimalor is O
(UBLs(a) + ( + P (S2 + HcC1+ P- W + #5))).
6.4 Clipping for Triangle Counting
Although the smooth sensitivity mechanism discussed the previous subsection provides accurate results, calculating the sensitivity U (1,((a;) can be cine-ccnsuning in large networks. In such cases, we opt for the local Laplacian mochanism (Definition 3
Let f 13 + IR be defined as f(a')
Σ
(.)) representing the value we intend to publish
j.ka -
for user i. Recall that the magnitude of the Laplacian noise added by the mechanism is determined by the max
global sensitivity A a''a":'a'="" (f(a') - f(a"). Given that (1) (K,,(K) wi, find that AS S n w4.
We can use n wi as the magnitude of the Laplacian noise. However, w, is to large that the noise can dominate the information we intend to publish. To have better bound for the sensitivity, we employ the ideas of double clipping in Imola al. (2022a). Although we use some idcas from the paper, as our mechanism different from theirs, we attain a better sensitivity by a different mathematical analysis. Our double counting algorithm is follows:
20

---

Published in Transactions on Machine Learning Research (08/2025)
1. Degree Clipping: Recall that d, is the estimation for the degree of e published in the first step of our mechanism. Let d; = d, + eo In 21
2. Noisy Triangle Clipping: Let Var represent the maximum variance of a single edge estimator, Cov the maximum covariance between two edge estimators, and define b; - d; + (d, Var + df Cov). E a(t) (,yy(a)) where { denotes the contribution of node j' to |A,). During
Let 1-
(.A)EW.(E(AAA)
the calculation of | in Line of Algorithm 4, if there exists a j' such that | pair (5, E W, such that (11) until A I
> b, we select
(k) = wi o, and update the value to O. This process is repeated
The clipping process described above ensures that the contribution of any edge (i,j") to the publication of [ does not exceed b; < n wi. As result, the sensitivity of the publication of | is b;, allowing us to set the Laplacian noise to this value.
While the clipping process allows us have a smaller noise the final step of our mechanism, the process can incur bias our publication. We give a thcoretical result for this clipping technique in the following theorem.
Theorem 13.
The clipping process incur no bias with probability at least 1 - B. The variance of our m- (S2 + McCs + W ()))
estimalor by the clipping process is 0 E
o
We use the following 2 lemmas our analysis.
Lemma 6. The probability that remove some edges in the degree clipping is smaller than 3/2.
Proof. We remove edges when d; d d, + eo In This indicates that d, d, Eo In 3. meaning the magnitude of the Laplacian noise added during the degroe-sharing step is greater than Eo In with a probability smaller than 8/2.
2 g. This occurs
While we consider the degree clipping in the previous lemma, consider the noisy triangle clipping in the subsequent lemma.
Lemma 7. The probability that we update some (1) a in the noisy triangle clipping is not greater than 3/2.
(1)
Proof. By the degree clipping and the definition of W., the number of terms in the summation
Σ
(,h,(K)
is at most d, From Theorem have that
Bla E (Ayy()) ajK {0, 1}.
Therefore,
E
Σ
(
(K),
< dd.
(
Since the summation contains at most d, terms, its variance can be bounded by
Var
Σ
(1) (2,
S de Var di Cov.
We notice that, in Imola al. 2022aa edges are removed match with de if d, de. However, that process can be skipped, because clip the sensitivity the noisy triangle process anyway.
21

---

Published in Transactions on Machine Learning Research (08/2025)
Using the bounds the expectation and variance, conchude that
B
Pr b.
We are now ready to prove Theorem
13
Proof of Theorem 13 From Lemmas 6 and union bound, obtain that the clipping has effect and incur no bias with probability at most 3/2. The variance of the Laplacian noise added by the node os is bf / Therefore, the final step of our mechanism increases the variance by Σ, b2/22.
In most practical cases, we have that b-= =0 (Velei-
Based that result, in all our experiments, the
failure probability 3 was set to 10-3
A as is smaller than the value used in One might wonder why we do not set the value of by to max
y'
the current clipping process. However, this is not feasible because max [A)")] contains sensitive information, 8'
and we cannot determine the noise parameter of our mechanism based on such private data.
In contrast, the variance and covariance required for the computation of the clipping parameter b, can be computed using n, 8 and d, With the exception of d4, all those are public information. Concerning d, it can be bounded with high probability by and d, to obtain bound on b;. Note that in the rare case that de > d,, the clipping mechanism still guaranties the privacy protection.
7 Experiments
In this section, we assess our method, GroupRR, in comparison to the leading commuicationn-onstraiinn graph publishing technique, ARR, as detailed in Imola et al. (2022a). As Imola et al. (2022a) has proven itself to be a more accurate algorithm than the rest of the state of the art, we restrict ourself to the comparison with this algorithm. We focus on the task of counting triangles in Subscction 7.1 and the task of counting 4-cycles in Subsection 7.2 All the code used for these experiments can be accessed at the following address http:///thtcooccooeeeeeerottttaa
7.1 Triangle Counting
In this subsection, we compare the triangle counting algorithm described in earlier sections with the leading- edge algorithm named ARROne from Imola et al. (2022a Among the various algorithms discussed in the paper, our analysis focuses on the one that utilizes the 4-cycle trick, which has been shown to yield the highest performance.
Our experiments primarily utilized the Wikipedia Article Networks dataset (Leskovec al. 2010b a). which contains 7,115 nodes and 100,762 edges, and the Facebook dataset (Leskovec & Mcauley 2012). which contains 4,039 nodes and 88,234 edges. We chose these two graphs to illustrate two different types of social networks. The Facebook graph represents network with many clusters, while the Wikipedia graph exemplifies networks centered around a few key nodes. Additionally, to prove that our methods scales to larger graph, we also used the Google+ dataset (Leskovec & Mcauley 2012 that constructed from Google circles. It contains 107,614 nodes and 13,673,453 edges.
PIt is important note, mentioned in Appendix I of Imola et 2022a that the original version of the algorithm underestimates the scusitivity. Consequently, we have adjusted the scnsitivity calculations used in evaluations. Specifically, in our modified version, the contribution of edge (1,,9)) the count by user in is defined as lk 0z 1, 1,6, m.) e M,, and i)) instead of (ik a,k I, (1y. v.. ) Mi, and j < ())-
22

---

Published in Transactions on Machine Learning Research (08/2025)
Wikipedia Article Network
niean ume
alputttee
Gooeptth C33
1
Goupiti 0SS
Atlliiee
10
Gooplti <xp
IPP
3P
37
331
(b) Facebook
Graghit
Gm kont
1811
dovelood cook
Figure 3: Comparative analysis of relative error between our algorithm and ARR across diffcrent download and upload costs applied to the Wikipedia Article Network and the Facebook graphs, assuming privacy budget of e = 1. The values of the parameter used for these experiments vary from to 26 for the Wikipedia Article Network, and from to 21 for Facebook, resulting in values of He varying from 1 to 16, 384 and from to 8, 192 respectively. The term 'CS in the legend stands for our central server sampling method
To conduct experiments on graphs of different sizes from the original, we generated extracted graphs by randomly selecting nodes to match the desired size and then examining the subgraph induced by these nodes. We have verified that selecting random subgraphs does not alter the graph topology of cither graphs with respect to the subgraph counting problem.
The focus of our experiments is on assessing accuracy, measured by relative error, as we adjust various parameters. These parameters include download cost, upload cost, graph size, and privacy budget. The results presented are averages calculated from 10 separate simulation runs for each set of parameters. All experiments are comparisons between the following three methods: (1) The leading-edge method detailed in Imola et al. (022aa) (2) Our GroupRR mechanism enhanced by the central server sampling and the clipping method (Subsection 6.4 (3) Our GroupRR mechanism enhanced by the central server sampling and the
smooth sensitivity (Subsection
6.3
7.1.1 Error Analysis for Various Download Costs
Figure 3 illustrates that algorithm outperforms the leading-odge algorithm across all download costs. When the download cost is minimal, the enhancement in relative error can be substantial as 1000-fold reduction. As the cost of communication goes down, the difference in performance between our method and the one described in Imola et al. (002aa) becomes more noticeable.
Parameters selection for GroupRR Recall that the download cost of the randomized response algo- rithm is approximately en?, for some constant с depending on the privacy budget e. Suppose our budget for the download cost. is M; then we aim to reduce the cost by factor of n² = cn2 /M. As discussed in the
23

---

Published in Transactions on Machine Learning Research (08/2025)
previous section, for GROUPRR with central server sampling, this reduction factor is given by p pe/ where Pe and 8 are tunable parameters in GRoUPRR. To achieve the desired reduction, set (1/p² 1//3
and (μ²) (10) Under this setting, the S2 term in the error bound (as described in Theorem scales as (4*)- 2/3, while the C4 term scales as (1*)-1/3.
Paramcters selection for ARROne On the other hand, in the context of ARROne, where j represents the sampling rate of the mechanism, the reduction download costs amounts μ², We hence set μ to Vμ². By that, the S2 factor in the error term scales with 1/n², and the C₁ factor scales with 1/vp"" This scaling behavior highlights that our algorithm proves more effective at lower communication costs compared to the method proposed in Imola et al. )022a
When the download cost reaches its maximum - a scenario that occurs when no sampling is implemented our mechanism and the leading mechanism exhibit similar performance, This outcome is anticipated, as in this scenario, both approaches essentially align with each other and with the classical local differential privacy-based triangle counting algorithm, as described in Imola et al. (2021).
The experimental findings also reveal that, across all the download cost budgets we considered, the smooth sensitivity method consistently outperforms the clipping method.
Algorithm
Groupitit CSS dib
101
AltROne
10P
relatre
10-1
10
10P
10*
download
Figure 4: Comparative analysis of relative error between our algorithm and ARR across different download costs applied to the Google+ graph, assuming privacy budget of = 1. The values of the parameter used for this experiment vary from 1 to 32, resulting in values of Pe varying from I to 32, 768. The term 'CSS' in the legend stands for our central server sampling method.
Figure illustrates that the performance of method compares to the state of the art becomes better the size of the graph increases. Indeed, as the download cost needs to be reduced by larger factor to keep the same communication, the gap in relative errors becomes bigger. For this experience we only used the clipping version of our algorithm as smooth sensitivity is slow for large graphs.
7.1.2 Error Analysis for Upload Costs
Throughout this section, we fix the downlood-reduutton target p² 1/1000. As discussed in Section 7.1.1 this choice corresponds to GroupRR parameters = 10 and PC 1/10. For ARRONE, set 1/31.6 (i.c., a Rs 0.03166.
Figure 3 demonstrates that our approach has enhanced the relative errors in counting across all ranges of upload cost budgets. Notably, the smaller the budget, the more significant the improvement we observe. For the lowest upload cost budget in this experiment, we have achieved an enhancement in relative error by up to factor of 1000. It is also evident that the smooth sensitivity method exhibits superior performance compared to the clipping method in this context.
24

---

Published in Transactions on Machine Learning Research (08/2025)
7.1.3 Error Analysis for Various Graph Sizes and Privacy Budgets
(a) Wikipedia Article Network
algociliu
GaaupiB smooth
algorithm
GroupRR CSS
dlp
10
GaagRR CSS stanch
ATMR2h
Gromalife CS8 dip
10H
10P
Dbatbe are5
108
10P
10P
1000
2000
3000
4000
5000
0000
2000
0.35
1.80
(b) Facebook
olgontchm GrompR CSS smonth
10
algocitian
Grou CSS + sootth
Grouphilt
GromPR CSS 4 dlp
AltiKChe
10a
ARROOs
102
102
10-
101
10-1
10
500
1000
1500
2503
2000
3000
3500
1003
0.25
0.50
0.75
2.00
1.25
1.00
1.76
2,00
Comparing the relative error between our algorithm and the state-of-the-ard approach (left plots) across different graph sizes (n), derived from the Wikipedia Article Network and Facebook graphs with s = 1 (right plots) under varying privacy budgets. In both experiments, we maintain a download reduction setting of 4² = 1000. Note that in the legend, *CS'' represents our contral server sampling mothod.
Figure 5:
Figure 5 shows that our algorithm improves the current state-of-the-art across a wide array of parameters. In these experiments, we tested various graph sizes and privacy budgets, observing similar trends for both algorithms. Notably, even though the performance gap between the two algorithms appears to expand the privacy budget increases, the difference in performance consistently remains around three orders of magnitude, irrespective of the graph size.
7.1.4 Runtime for Various Graph Sizes
Figure 0 presents the execution times for the state-of-the-art ARR algorithm, compared to two variants of our GroupRR algorithm: one with clipping and another with smooth sensitivity, across different graph sizes. The results indicate that GroupRR with smooth scnsitivity incurs significantly longer execution times, whereas GroupRR with clipping shows running limes comparable to ARR. This discrepancy in performance can be attributed to their asymptotic complexities: both ARR and GroupRR with clipping operate in O (d) whereas the complexity for GroupRR with smooth sensitivity O (nm). The graphs, plotted on a logarithmic scale, do not form perfect straight lines, reflecting that in our model for generating graphs of varying sizes, the average degree does not scale proportionally with graph size n.
25

---

Published in Transactions on Machine Learning Research (08/2025)
(a) Wikipedia Article Network
(b) Facebook
10
alporithm
alguciiiio
Grouplift CSS smooth
GrcopRR + emooth
GroupRR
GropRR CSS clip
--...
AltDOne
10P
10
runtie 51
108
107
201
10P
10P
1000
2000
3000
1000
3000
0000
7000
300 1000
2500 3000 3500
1000
Figure 6: Comparison on runtime between our algorithm and the leading edge algorithm for various graph sizes generated from the Wikipedia Article Network and Facebook graphs with e = and a download cost reduction of 1000. In the legend, the abbreviation *CSS* denotes our central server sampling method.
This experiment demonstrates the balance between speed and accuracy required when choosing between our two methods. GroupRR with clipping offers good accuracy with an execution time comparable to state-of- the-art methods. Conversely, GroupRR with smooth sensitivity prioritizes accuracy but at the expense of execution speed. This trade-off becomes particularly significant when dmaz, the maximum degree, small relative to the number of users
7.1.5 Error Analysis on Power-law Graphs
107
relativ oror
algarithm GrouRR
GrapRR CSS dip
ARROOe
10
300
630
800
1000
1330
1.00
Figure 7: Comparative analysis of relative error between algorithm and ARR across different graph sizes synthetically generated power-law graphs, assuming privacy budget of s 1. For this experiment, we set the parameter to 5. The term 'CSS' in the legend stands for our central server sampling method.
Figure 7 shows the relative error of our algorithms as well as the statc-of-the-art ARROne for various graph sizes. Each graph randomly samples such that the degree distribution follows a power law of exponent 2. This means that the expected number of nodes with degree d is proportional to d=2
26

---

Published in Transactions on Machine Learning Research (08/2025)
Consequently, the graph's maximum degree is approximately one-third of the number of nodes. Even in this regime-whee the bounded-degree condition d, < R n/s required for our theoretical guarantees is violated our algorithms still outperform the state-of-the-art ARRONE.
7.2 4-cycles Counting
To validate the versatility of our framework, extended experiments to include counting cycles of length 4, or 4-cycles, ulilizing the same framework employed in our triangle counting methodology. This method is described in Eden et al. (2023), Hillebrand et al. (2025) and Suppakitpaisarn et al. (2025). The number of 4-cycles that include edges (i, and (i, (") can be estimated by Eg ()((j"))) 1") and the number of 4-cycle that the node i participates is given by Er,, E, a(1 ((),"))
Given the larger size of the subgraphs of interest, we opted use smaller graphs for our experiments effectively manage complexity and computational demands. To establish the robustness and applicability of our results, conducted our 4-cycles counting experiments
specific graphs. The first is the Twitter Interaction Network for the US Congress (Fink et al.) 2023). which represents Twitter interactions of the 117th United States Congress, comprising 475 nodes and 13,289 edges. The second graph is the email- core network (Leskovec et al. 2007 Yin et al.) 2017): derived from email interactions among members of a major European research institution, containing 1005 nodes and 25,571 edges. These selections allow us provide substantive evidence of the generality of our findings across different types of networks.
We assessed accuracy using the fe-error computed as
Σ (+. x)p, where is the ground truth and át is
the estimated value obtained in trial 1 S S 10.
emall
congress Twitter
10-9
10
olgeetthn GoouplER
10
dowmload rost
dewnked roet
Figure Comparison on fz-error between our algorithm and ARR for various sampling factors on the Twitter Interaction Network for the US Congress and the email-Eu-core network with =
The experimental outcomes are displayed in Figure S It is evident that the error patterns are consistent across both datasets. With either method, regardless of the sampling factor used, the error is greater in the email-F.U-core dataset. This aligns with expectations since the ee-error a property that tends increase with the graph's size.
Nonetheless, the rate at which the discrepancy between the two methods grows is the same across both datasets. When the full dataset is used-i.a i.e., without any communcatiio reduction the performance of ARR and GroupRR is comparable and aligns with that of the standard algorithm without communication constraints [Imola et al., 2021). However, as shown in the graphs, under a sampling factor of 100, the error associated with ARR increases by approximately a factor of 10x relative to GroupRR. According to Theorem 4 the f2-error estimating single edge scales lincarly with the sampling factor for GroupRR, but quadratically (i.e., s?) for ARR. Since each 4-cycle estimation involves two edge estimates, the overall fa-error scales 2 for GroupRR and 4 for ARR. This implies theoretical error gap of s2 10a between
27

---

Published in Transactions on Machine Learning Research (08/2025)
the two methods. The observed reduction of this gap to 10 is attributed to the fact that, in the absence of sampling, ARR achieves slightly better accuracy than GroupRR.
8 Conclusion
Our work introduces a private graph publishing mechanism that provides unbiased estimations of all graph edges while maintaining low communication costs. The effectiveness of this method stems from integrating two key components: the application of linear congruence hashing to achieve uniform edge partitions and the amplification of budget efficiency through sampling within each group. This synergy leads to a significant reduction download costs, quantifiable as factor of O(s²), where s represents the size of the groups.
We then demonstrated its utility in accurately estimating the count of triangles and 4-cycles. Furthermore, we elaborated on the application of smooth sensitivity to these problems, ensuring that the resulting estimations remain unbiased. Our experiments have demonstrated that these methods offer substantial improvements in precision over existing state-of-the-ar approaches for the countings.
Our future work focused on enhancing the scalability of subgraph counting under local differential privacy. We have observed that the computation time required for each user in all mechanisms proposed to date is considerable. This computation time often increases for mechanisms involving multiple steps. Our aim is explore how sampling methods not only improve precision but also significantly boost the scalability of the counting process.
9 Acknowledgments
Quentin Hillebrand is partially supported by KAKENHI Grant 20H05965, and by JST SPRING Grant Number JPMJSP2108. Vorapong Suppakitpaisarn is partially supported by KAKENHI Grant 21 and 23H04377. Tetsuo Shibuya is partially supported by KAKENHI Grant 20H05967, 21H05052, and 23H03345. The authors wish to express their thanks to the anonymous reviewers whose valuable feedback greatly enhanced the quality this paper.
References
Maneesh Babu Adhikari, Vorapong Suppakitpaisar,, Arinjita Paul, and C Pandu Rangan. Two-stage frame- work for accurate and differentially private network information publication. In CSoNet 2020, pp. 267 279, 2020.
Hilal Asi, Vitaly Feldman, and Kunal Talwar. Optimal algorithms for mean estimation under local differential privacy. In JCML 2022, pp. 0046-105,, 2022.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in Neural Information. Processing Systems, 31, 2018.
Albert-László Barabási. Network science. Philosophical Thansactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 371 (11(6))))200120377 2013.
Louis Betzer, Vorapong Suppakitpaisarn, and Quentin Hillebrand. Publishing number of walks and Katz centrality under local differential privacy. In UAI 2024, 2024.
Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to noninteractive database privacy. Journal of the ACM (JACM), 60(2):1 25, 2013.
Stephanic Chandler.
What to do when your facebook profile is maxed out URL http:///auhhorrtyyulllshin cot.a//caoococccccaaeeea
friends, 2012.
Graham Cormode, Somesh Jha, Tejas Kulkarni, Ninghui Li, Divesh Srivastava, and Tianhao Wang. Privacy at scale: Local differential privacy in practice. In SIGMOD 2018, pp. 1655-1658, 2018.
28

---

Published in Transactions on Machine Learning Research (08/2025)
Laxman Dhulipala, Quanquan C Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, and Shangdi Yu. Dif- ferential privacy from locally adjustable graph algorithms: k-core decomposition, low out-degree ordering, and densest subgraphs. In FOCS 2022, pp. 754 765, 2022.
Differential Privacy Team, Apple. Learning with privacy at scale, 2017.
Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. Adoances in Newral Information Processing Systems, 30, 2017.
Cynthia Dwork. Differential privacy. Tn ICALP 2006, pp. 1-12, 2006.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In TCC 2006, pp. 265 284, 2006.
Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In FOCS 2010, pp- 51-60, 2010.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, 933-4):211-407, 2014.
Talya Eden, Quanquan C Liu, Sofya Raskhodnikova, and Adam Smith. Triangle counting with local edge differential privacy. In ICALP 2023, volume 261, pp. 52, 2023.
Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy- preserving ordinal response. In CCS 2014, pp. 1054-1067, 2014.
Alexandre Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant. Limiling privacy breaches in privacy preserving data mining. In PODS 2003, pp.
2003.
Christian G Fink, Kelly Fullin, Guillermo Gutierrez, Nathan Omodt, Sydney Zinnecker, Gina Sprint, and Scan McCulloch. A centrality mcasure for quantifying spread on weighted, directed networks. Physica A, 2023.
Yizhang He, Kai Wang, Wenjie Zhang, Xuemin Lin, Wei Ni, and Ying Zhang. Butterfly counting over bipartite graphs with local differential privacy. In ICDE 2024, pp. 2351-2364, 2024.
Seira Hidano and Takao Murakami. Degree-preserving randomized response for graph neural networks under local differential privacy. Transactions on Data Privacy, 17(2):89- 1111899-111111 2024.
Quentin Hillebrand, Vorapong Suppakitpaisarn, and Tetsuo Shibuya. Unbiased locally private estimator for polynomials of laplacian variables. Tn SIGKDD 2023, pp. 741-751, 2023.
Quentin Hillebrand, Vorapong Suppakitpaisarı, and Tetsuo Shibuya. Cycle Counting Under Local Differ- ential Privacy for Degeneracy-Boudder Graphs. In STACS 2025, pp. 49:1-49:22, 2025.
Lihe Hou, Weiwei Ni, Sen Zhang, Nan Fu, and Dongyue Zhang. WdI-SCAN: Clustering decentralized social graphs with local differential privacy. Computers Security, 125:103036, 2023.
Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. Locally differentially private analysis of graph statistics. In USENIX Security 2021, 983-1000, 2021.
Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. Commuicctiin--fficeenn triangle counting under local differential privacy. In USENIX Security 2022, pp. 537-554, 2022a.
Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. Differentially private triangle and 4-cycle counting the shuffle model. Tn CCS 2022, pp. 1519, 2022b.
Donald E. Knuth. The art of computer programming, volume 3: Sorting and searching, 1997.
Jure Leskovec and Julian Mcauley. Learning to discover social circles in ego networks. Advonces in neural information processing systems, 25, 2012.
29

---

Published in Transactions on Machine Learning Research (08/2025)
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diam- eters. ACM transactions on Knowledge Discovery from Data (TKDD), 1(1):2ees, 2007.
Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. Predicting positive and negative links in online social networks. In WWW 2010, pp. 641-650, 2010a.
Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. Signed networks in social media. In CHI 2010, pp. 1361-1370, 2010b.
Mengchu Li, Tom Berrett, and Yi Yu. Network change point localisation under local differential privacy. Advances in Neural Information Processing Systems, 35:15013 11026, 2022.
Yang Li, Zhenjie Zhang, Marianne Winslett, and Yin Yang. Compressive mechanism: Utilizing sparse representation differential privacy. In WPES 2011, pp. 177-182, 2011.
Zitao Li, Tianhao Wang, Milan Lopuhaä Zwakenberg, Ninghui Li, and Boris Skoric. Estimating numerical distributions under local differential privacy. In SIGMOD 2020, pp.
2020.
Yanxiao Liu, Wei-Ning Chen, Ayler Orgür, and Cheuk Ting Li. Universal exact compression of differentially private mechanisms. arXiv preprint 2i5:2405.22782 2024a.
Yuhan Liu, Suyun Zhao, Yixuan Liu, Dan Zhao, Hong Chen, and Cuiping Li. Collecting triangle counts IEEE, 2022.
with edge relationship local differential privacy. In ICDE 2022, pp.
Yuhan Liu, Tianhao Wang, Yixuan Liu, Hong Chen, and Cuiping Li. Edge-protected triangle count estima- tion under relationship local differential privacy. IEEE Transactions on Knowledge and Data Engineering, 2024b.
Naurang S. Mangat. An improved randomized response strategy. Journal of the Royal Statistical Society: Series B (Methodological), 56(1):93-95, 1994.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In FOCS 2007, pp. 94 103. IEEE, 2007.
Mohamed S Mohamed, Dung Nguyen, Anil Vullikanti, and Ravi Tandon. Differentially private community detection for stochastic block models. In ICML 2022, pp. 15858-15894 2022.
Sayan Mukherjee and Vorapong Suppakitpaisam.. Robustness for spectral clustering of general graphs under local differential privacy. orXiv preprint arXiv:2309. 068677, 2023.
Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In STOC 2007, pp- 75 84, 2007.
Arinjita Paul, Vorapong Suppakitpaisaru, Mitali Bafna, and C Pandu Rangan. Improving accuracy of differentially private kronecker social networks via graph clustering. In ISNCC 2020, pp. 1-6. IEEE, 2020.
Zhan Qin, Ting Yu, Yin Yang, Issa Khalil, Xiaokui Xiao, and Kui Ren. Generating synthetic decentralized social graphs with local differential privacy. In CCS 2017, pp. 125-438, 2017.
A Rotenberg. A new pseudo-random number generator. Journal of the ACM (JACM), 7(1):5 77, 1960.
Sina. Sajadmanesh and Daniel Gatica-Perez. Locally private graph neural networks. In CCS 2021, pp. 2130-2145. 2021.
Vorapong Suppakitpaisarn, Donlapark Ponnoprat, Nicha Hirankarn, and Quentin Hillebrand. Counting graphlets of size k under local differential privacy. In AISTATS 2025, 2025.
WE Thomson. A modified congruence method of generating pseudo-random numbers. The Computer Journal, 1(2):83-88 83, 1958.
Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. Locally differentially private protocols for frequency estimation. In USENIX Securily 2017, pp. 729 729-745, 2017.
30

---

Published in Transactions on Machine Learning Research (08/2025)
Yue Wang, Xintao Wu, and Donghui Hu. Using randomized response for differential privacy preserving data collection. In EDBT/ICDT Workshops, 2016.
Stanley L. Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistionl Association, 60(309):633 69, 1965.
Akito Yamamoto and Tetsuo Shibuya. Privacy-presevingg genomic statistical analysis under local differential privacy, In DBSec 2023, pp. 40 48. Springer, 2023.
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 Transactions on Knowledge and Data Engineering, 34(10):4905 1949905--20,,,,, 2020.
Hao Yin, Austin R Benson, Jure Leskovee, and David F Gleich. Local higher-order graph clustering. In SIGKDD 2017, pp. 555-564, 2017.
31


Reviews:
[{"review_id": "IPI0aWgf5q", "reviewer": "Reviewer_e61A", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. The core contribution is a mechanism that reduces communication costs by a factor of $s^2$ using linear congruence hashing and sub-sampling, which is a major bottleneck in prior ELDP-based subgraph counting methods.\n\n2. The method achieves amplification of privacy guarantees due to subsampling, which allows for lower bit-flipping probabilities in the randomized response mechanism. \n\n3. The proposed estimator is shown to be unbiased, meaning it correctly estimates subgraph counts in expectation despite local randomization and compression.\n\n4. Empirical results show that for fixed communication cost, the proposed method achieves up to 1000x lower ℓ2-error in triangle counting compared to state-of-the-art approaches.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose a novel approach to efficiently compute subgraph statistics, such as triangle and 4-cycle counts, under edge local differential privacy by introducing a technique called Group Randomized Response (GroupRR). This mechanism leverages linear congruence hashing to partition users into reproducible groups and sample one representative edge per group, which is then privatized using a randomized response mechanism. This sampling strategy enables privacy amplification while significantly reducing communication overhead by a factor of s^2, with only a linear increase in variance. The method is shown to be unbiased, scalable, and generalizable to various subgraph counting tasks, outperforming previous state-of-the-art algorithms by up to three orders of magnitude in terms of ℓ2-error when communication cost is held constant.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Increased Estimation Variance. I can easily see that there is a trade-off between communication cost and variance: while communication cost is reduced by a factor of $s^2$, variance increases. So, a critical question is how to select the best s? I think the authors need to give some theoretical results and discussions. \n\n2. Parameter Sensitivity. The performance depends heavily on careful tuning of the sampling size s, privacy budget split $(\\epsilon_0, \\epsilon_1, \\epsilon_2)$, and hashing parameters but it does not offer clear guidance or adaptive strategies for selecting these parameters in practice.\n\n3. While smooth sensitivity offers improved utility, its computation can be expensive, especially when $\\gamma$ must be large to control variance.", "broader_impact_concerns": "na", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "eLsDqlZaSW", "reviewer": "Reviewer_mqCD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The task of subgraph counting is a fundamental one and the setting of edge local DP is likewise textbook. The focus on communication cost is proportionate to its importance. The pseudocode and Section 4 in general do a good job of conveying to the reader (a) the main ideas of the proposed local protocol and (b) basic intuition about why the proposal might work.\n\nI would have liked more advanced intuition. Client i makes a guess about whether a triangle i,j,k is present (or subgraph more generally) based on a noisy version of the indicator of (j,k)'s presence *that is diluted* via subsampling; how does the scaling and shifting of noisy sums compensate for the fact that client i could get a noisy version of the wrong bit?\n\nA key hyperparameter in the new algorithm is s, the target size of each group that the hash function divides nodes into. However, the experimental section does not spell out the exact values of s used. (I know that Section 7.1.1 contains a formula but it superficially appears circular---$\\mu^\\*$ is defined in terms of $s^2$ but then $s$ is set in terms of $\\mu^\\*$--- which confuses the reader.)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this submission, the authors propose a way to perform subgraph counting subject to edge local differential privacy. Prior approaches relied upon a naive use of randomized response: each bit in a client's adjacency list is flipped with probability $1/\\exp(\\varepsilon)$. This has the effect of being both noisy and costly in terms of communication.\n\nThe submission utilizes subsampling to improve both. Specifically, the central server sends a linear congruence hash function to each client. The client uses the hash to essentially color the indices of their adjacency list then, for every color, they choose a random index of that color and apply randomized response to the value at that index. The fact that an adversary cannot see which entry was sampled is used to minimize the noise in the entry itself.\n\nTo count triangles in their neighborhood, a client re-scales and shifts the bits received from other clients. They communicate this count to the server via the Laplace or smooth sensitivity mechanism. Experiments reveal that the new work dominates the prior work's tradeoff between error and epsilon and the tradeoff between error and download cost. Running time however is worsened.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above.\n\nAlso,\n- Make it a bit clearer early on that you will focus on triangle counting instead of leaving the goal as the generic-sounding \"subgraph counting.\"\n- Consider renaming \"the clipping method\" to \"the global sensitivity method\", to better parallel \"smooth sensitivity\" (or just Laplace mechanism!)\n- Please clarify the difference between \"ARR\" and \"ARROne.\"", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KwEooM5N3H", "reviewer": "Reviewer_1AKE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n - the paper is very well written, with formal definitions and details that made most of the statements clear and easy to follow\n - it attacks and important problem, and provides (in reasonable cases) clear advantages to state-of-the-art\n - the advantages are not just theoretical (the main results), but also sees to work much better in practice on a couple of examples.  \n\nWeakness:  \n - the main results seem to leverage on the assumption that all nodes have degree bounded by n/s where s is the size of the sample.  This is stated as reasonable without describing or citing justification.  My understanding is that while this may be true on average, or in some cases, it is not in other cases as well.  (e.g., Elon apparently has over 200 million followers on Twitter/X).  While this assumption is stated in main theorems, I think it should be discussed more clearly in the intro, and authors should add more discussion on when it holds, and what could be done if it does not hold.  \n  - A few proofs could have explained steps a bit better.  Namely in proof of Theorem 4, it would have been useful, immediately below the last offset equation, to remind the reader than Lemma 5 and the m < n/s assumption are being used.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers important problems in subgraph counting (including the number of triangles which is a key graph statistics, the clustering coefficient) under differential privacy.  The model is each user knows its edges, we are asked to compute global statistics.  Under Local Differential Privacy, the users do not share their data in the raw (typically add Laplacian noise to it) to even ensure privacy from the global entity computing the stats.  \n\nThis paper provides a new protocol for these tasks.  It is multiple round, involving the users (vertices) sending noising information to central node, the central node adding additional global noise, and sending tasks back to users to compute statistics, and sending them back to be compiled globally.  The main result uses linear congruence hashing to deliver sampled estimates in a way that under certain settings provides much better bounds on the estimates in theory, and in practice.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have on additional question:\n\nQuestions:  \n  - Some of the communication consequences are directly from the degree < m < n/s assumption.  Can these be replaced by average case bounds if it is true in average?  For instance this seems to be the case in Corollary 1.  Can this idea be used generally to remove this strong degree assumption?  \n\n\nRegardless of the above weaknesses (and question), I think the paper is valuable.  With a few small changes I think it's worth publishing.  It's on an interesting relevant topic, and it is generally very well written.  To get my final support for the paper, please respond (and update the paper as/if needed) the weaknesses and Question.", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)