Faster approximate subgraph counts with privacy
Authors: Dung Nguyen
Mahantesh M Halappanavar
Venkatesh Srinivasan
Anil Vullikanti
Venue: NeurIPS 2023 poster (2023)
Keywords: differential privacy
subgraph counting
smooth sensitivity
local sensitivity

Abstract: One of the most common problems studied in the context of differential privacy for graph data is counting the number of non-induced embeddings of a subgraph in a given graph. 
These counts have very high global sensitivity. Therefore, adding noise based on powerful alternative techniques, such as smooth sensitivity and higher-order local sensitivity have been shown to give significantly better accuracy. 
However, all these alternatives to global sensitivity become computationally very expensive, and to date efficient polynomial time algorithms are known only for few selected subgraphs, such as triangles, $k$-triangles, and $k$-stars.
In this paper, we show that good approximations to these sensitivity metrics can be still used to get private algorithms.
Using this approach, we much faster algorithms for privately counting the number of triangles in real-world social networks, which can be easily parallelized.
We also give a private polynomial time algorithm for counting any constant size subgraph using less noise than the global sensitivity; we show this can be improved significantly for counting paths in special classes of graphs.

Faster approximate subgraph counts with privacy
Dung Nguyen
Mahantesh Halappanavar
Department Computer Science and UVA Biocomplexity Institute and Initiative University of Virginia, USA dungn@virginia. edu
Data Sciences and Machine Intelligence Group Pacific Northwest National Laboratory, USA
hala@pnnl. .gov
Venkatesh Srinivasan
Anil Vullikanti
Department Mathematics and Computer Science Santa Clara University, USA verinivasan4@scu.cm
Department of Computer Science and UVA Biocomplexity Institute and Initiative University of Virginia, USA veakuar@rirginia.cem
Abstract
One of the most common problems studied in the context of differential privacy for graph data counting the number of non-induced embeddings of subgraph given graph. These counts have very high global sensitivity. Therefore, adding noise based on powerful alternative techniques, such smooth sensitivity and higher-order local sensitivity have been shown to give significantly better accuracy. However, all these alternatives to global sensitivity become computationally very expensive, and to date efficient polynomial time algorithms are known only for few selected subgraphs, such as triangles, k-triangles, and k-stars. In this paper, we show that good approximations to these sensitivity metrics can be still used to get private algorithms. Using this approach, we much faster algorithms for privately counting the number of triangles in real-world social networks, which can be easily parallelized. We also give a private polynomial time algorithm for counting any constant size subgraph using less noise than the global sensitivity; show this can be improved significantly for counting paths in special classes of graphs.
Introduction
The notion of Differential Privacy (DP) [12 has emerged the facto standard notion for supporting queries on private and sensitive data. DP ensures that changes in private data have limited statistical influence (measured by the privacy budget 8) on the output of queries, without needing any attack model, which is one of the reasons of its popularity. Networked abstractions are commonly used in a number of applications, such as public health, social networks, and finance. Such datasets are usually sensitive, and maintaining privacy is an important concern. Within the context of network/graph data, two privacy models have been considered in most prior work, namely, edge and node privacy. There has been lot of interest in developing private algorithms for number of network problems, such as community detection (2 9 g 22). and counting small subgraphs (e.g..
stars and triangles [25] 36 23 31).
However, efficient private algorithms with good accuracy are known for many graph problems, including counting small subgraphs. One of the main challenges is that graph problems often have very high global sensitivity (the maximum change in the output function due to the change in one edge/vertex (see Section 3), in contrast to many statistical and machine learning queries. As result, DP algorithms based on global sensitivity (which can usually computed quite easily for privacy many problems) do not give good accuracy bounds, in general. For instance, in the edge-pn edge-privacy
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

model, the global sensitivity of #triangles in graph G EV can be as high as n - 2, where n = [V.. making the added noise too large in many instances. A number of novel alternatives to global sensitivity have been proposed, e.g., smooth, restricted and multi-level local sensitivity, and ladder functions [36 23 31, which add significantly lower level of noise than mechanisms based on global sensitivity.
However, all these alternative notions of sensitivity are computationally much more challenging, and none of the current graph DP algorithms for subgraph counting scale to even moderate size net- works. Even the simplest problem of counting #triangles privately takes min {m max, d(u). M (n)) time [23] where m = [E d(u) is the degree of node v E V. and M (n) is the time for multiplying two n X n matrices, which super-quadratic, in general. This a sharp contrast with the significant advances in non- con-private graph mining where complex network properties such as clique counts can be computed using provably-efficiem and practical algorithms [35] 20 19. For few other subgraphs, such as k-cliques and h-triangles (see [36 23 for definitions), private algorithms using noise lower than the global sensitivity are known, but the worst case running time can still be O(n²) [66 How- ever, for most subgraph counting problems, private algorithms which use alternatives to global sensitivity, and have time comparable to the non-private algorithms, are known.
A main tool for subgraph counting and other graph mining tasks in massive networks are sampling based approximation algorithms, e-g., (2]: however, these haven't 't been used in the context of private graph algorithms. In this paper, we take the first steps in this direction. Our main contributions are:
We show that for a query f(G), we can get private algorithm by adding noise that scales with an approximation to the smooth sensitivity to an approximation to f(G) (Theorem T]. This result opens the door to improving efficiency of private algorithms using approximation techniques that have been very useful in non-private graph analytics. As an illustration, we use this result to obtain a quasilinear time private algorithm for counting #triangles under edge privacy (Theorem 2 for graphs which satisfy a stronger transitivity property (see Definition (5). Our algorithm adapts the diamond sampling technique of [2] for approximate triangle counting, and can also be parallelized easily. No parallel algorithms have been developed for private subgraph counting so far.
Extending the approach of [23] we design a private higher-order local sensitivity approach for subgraph counting, which gives privacy even when the higher-order local sensitivities are estimated approximately (Theorem 7. This yields the first private algorithm to count the number of embeddings of any subgraph with é edges in time On using less noise than global sensitivity. For the specific case of paths with é edges, we develop an algorithm that gives a very close approximation to the higher-order sensitivity in time (hd,, t, ()))) where d and are the degeneracy and treewidth of G. respectively (defined later). Thus, for paths. the rumning time does not grow as Onn)) for graphs with bounded degeneracy and treewidth. These properties have been used extensively in developing efficient a algorithms for subgraph counting and other graph mining tasks, e.g., haven't 't been used for private algorithms.
but, they
We experimentally evaluate our algorithm for counting #triangles (Section 6). We show that our algorithm for estimating the smooth sensitivity has very good approximation factor, and significantly better running time than the exact algorithm. Using approximate smooth sensitivity for counting #triangles gives good accuracy even for fairly low values, suggesting that using approximate smooth sensitivity does not compromise performance. Our algorithm also has good scaling, and is the first private algorithm for counting #triangles which has been run on networks with over 2 million edges. We note that many details, including proofs are presented in the Supplementary Material (SM).
2 Related Work
The area of DP graph algorithms is quite large and active. There has been a lot of work on DP algorithms for many basic graph problems, such as community detection, subgraph counting, finding
small cuts, and releasing synthetic graphs [25] 28, 30 B3 16 3 [5] There is some work on graph algorithms under local DP, e.g., [16), but most of the prior work has been for global DP (as defined in Section 3. and is our focus in this work. We refer to 27 for recent survey on private graph algorithms. For brevity, we only discuss prior work on private subgraph counting that is directly related to our paper, and in the DPge-DP model. We omit the discussion on private estimation of edge
2

---

Privacy model
Runtime
Global Sensitivity
0(1)
Ladder function [10]
(c, 5)
O (atrrxx mul. of size n)
Recursive mechanism
(c,0)
Omm)
Restricted Sensitivity [3
(c,0)
Omm
Blackbox Transformation 4]
(c,
(non-privvte # alg.)
(Exact) Smooth Sensitivity [23
(c,0)
O (matrix mul. of size n)
Our method
(e,
Om log" n) for (C, A)- with constant C, A
Table 1:
Summary of the characteristics of differentially private #triangle counting algorithms in the edge- privacy model (the other works mentioned here consider other subgraphs also, but we only focus on the runtime of counting #triangles). The runtime of Blackbox Transformation 4 includes the calculation of an approximated triangle counts, while all others assume the true counts are given. The runtime of our method is reported with 8 = Qn 2) and constant 7 (see Corollary I.
density and degree distribution, which has been studied more extensively, e.g., 14, and results for node-DP (55), which is less studied.
As mentioned earlier, global sensitivity, denoted by GS(J) for a graph metric f(G) (defined in Section 3 is high for many subgraph counting problems. Adding noise based on GS(F) leads to
low accuracy, while noise based on just LSy, the local sensitivity, need not be private [31]. Nissim
et al. (3T) develop the notion of smooth sensitivity (G) = max (G) --
where d(G, G²) is the swap distance between graphs G and G", and show that adding noise based on S7, (G) is private. However, smooth sensitivity becomes computationally much more challenging, since its definition involves considering local sensitivity at distance for all t, which doesn't 't seem like a polynomial time computation. Nissim al. (31 develop polynomial time algorithms for computing the smooth sensitivity exactly for counting #triangles, which was improved slightly to M(n) (23), where (n) is the matrix multiplication time. Polynomial time smooth sensitivity bounds were also shown for small number of other subgraphs. but no polynomial time algorithms are known beyond that. Interestingly, no hardness bounds are known for smooth sensitivity; the existing hardness bounds, e.g., [23] 36) only give hardness for computing local sensitivity at distance t. In order to handle other subgraph counts, Karwa et al. [3] develop different technique technique (12). and use it for private counts of k-cliques. Zhang et al. (36) develop the technique of ladder functions to handle other kinds of subgraphs, and use it to privately count #k- #kc-cliques in the graph in time O(nT(n)), where T(n) is the time needed to count #k-cllques non-privately. A few other techniques, such as inverse sensitivity [1 and proplse-tes--ellesee [22 are known. However, private algorithms for counting most subgraphs including paths and trees are not known. The recent work of 4 is related, but only considers approximation in the queries, but not in sensitivity. As a result, our methods give significantly higher efficiency. We also note that Blocki et al. [4] develop a black-box approach to make certain approximation algorithms differentially private. However, their work requires the function being computed to have "small" global sensitivity.
involving local sensitivity of local sensitivity (motivated by the propose-test-releee
The difficulty of subgraph counting with DP has motivated work in slight variations of the DP model. Rastogi et al. 34 consider the problems of releasing more general subgraph counts. However, they consider relaxed version of edge-DP, called (edge) adversarial privacy, that uses Bayesian attacker. Chen et al. 7 design a different approach that gives lower bounds for general subgraph counts through a linear program to form a recursive strategy. But, as mentioned in [36), their method suffers from a bias between the true query answer and the lower bound, in exchange for less noise. [32] presents different approach based on iterative refinement that estimates counts by degree, and can be implemented in time O(max,, deg(v))$m)
There have been studies on subgraph counting (including triangle counting) under other privacy models: the node-DP model [25] [0), and the shuffle model [18]. We note that our analysis of approximate smooth sensitivity holds for other privacy models as well, and we expect this could be used for improved private queries for other problems. However, the specific technique using diamond sampling for faster triangle counting only holds in the edge-DP model. Fundamentally new ideas are needed for extending this technique to node-DP and others. For a more comprehensive review of recent development on subgraph counting with privacy, we refer readers to (27].
3

---

3 Preliminaries
A non-induced embedding of a graph И = (VH, into a graph G = (V,E) is a mapping & VH + V such that (ø(u), o(t)) E E' whenever (u, v) E Σs. We use fH(G) to denote the number non-induced embeddings of a H in G. We drop the subscript H when it is clear from the context. Let = VHr| and n = M.. A denotes the adjacency matrix of graph G. Let (i) and (i) denote the set of neighbors and non-neighbors of node i V. respectively; let d(i) [i))) and d(i) = n - d(i). Let dmaz= = max d(v) denote the maximum degree.
Differential privacy graphs. Let G denote set of graphs
fixed set V of nodes. For graph G E g. we use VG) and E(G) to denote the set of nodes and edges of G. respectively. In this paper, will focus the notion of edge privacy []. where all graphs G g have fixed set of nodes ( = V, and two graphs G. G' E G are considered neighbors, i.e., G ~ G', if they differ in exactly one edge, i.e., |E(G) E(G')) 1.
Definition 1. A (randomized) algorithm M G - is (c, -.-iiferrenn private if for all subsets S C R of its output space, and for all G, G' E g, with G ~ G', we have Pr(M(G) E S] I e Pr([M(G)) S) + 01 37.
Problem statement: subgraph counting with edge differential privacy. Given a family of graphs on a set V of vertices, a subgraph H, and parameters c, ō, construct an (c, differrretil private mechanism Mfn 9 + 2", such that [M (G) J (G)l is minimized.
We discuss the notions of sensitivity mostly using the notation from 23 31 with slight changes. Let (G) maxg'~G (f(G) - [(G)) denote the local sensitivity of f: we also use (S))
to denote this. GS(f) maxç LS)) denotes the global sensitivity. The local sensitivity of
function f on graph G at distance is defined as ( (G) = maxd(G,G')s! (S)
Definition 2. (Smooth bound on L.S (II)) For 3 > O, a function S: D - RR+ is B-smooth upper bound on LS₁ it satisfies the following conditions: for all x E D"; S(x) 2 LS)(x)) and (2) for all x y E D": S(x) S S(y))
(G) maxg (LS(F(G") -Bd(G,G') is the smallest function satisfying Definition 2 and is referred as the 8-smooth sensitivity of f at G. Using the local sensitivity distance the smooth sensitivity can be written as Si.e = -..... -t (S()) (G).
Definition 3. (Admissible Noise Distribution) (37] A probability distribution B.d given by density function is (a, -)dadiissie if. for a = 8), 33 = ;8c,8), the following conditions hold all A Id and X E I satisfying |||||| S a and X S 3, and for all measurable C IR4; (1) Sliding properly: Prz (Z E S) S e0/2 Prz [Z
A] + 8/2, and (2) Dilation property:
Przza[Z E S] S 20 Prz=n IZ E E² S 6/2.
An important example of an admissible noise distribution is the Laplace mechanism Lap(A) proba- bility density function is l((z)= = 1x -1=//A
Lemma 1. (Calibrating noise to Smooth Sensitivity (II
Let Z be random variable sampled from an (a, -)dddiisseee noise. Let Sj.9 be the 3-smooth upper bound on the local sensitivity of f. Then algorithm A(x) = f(x) + St,(# Z is (e, ddiiferrrttt private. a
Definition 4. (An (a, 6) apprroxximtai to a function f). f is said to be an (a, 6) approximation to a function f if for any imput x, with probability at least 1 8, we have (1 - fx) f(x) <
(1+a)f(z))
Social networks generally have the property that nodes have high clustering coefficient, which the fraction of pairs of neighbors of node which are connected. We consider more restricted notion here. We refer to a path with r edges as an r-path. We say a 2-path i, k is "closed" if (i, k) E, i.e., i, k form triangle in G.
Definition 5. ((C, (C),aaa-sssstii graph) A graph is said to be (C, -trrnsiiev for any vertex j e V and edge (i,j) F, we have: if deg(i) > A, then C fruction of all the 2-paths starting with i,j are closed.

---

4 Approximate smooth sensitivity and fast private triangle counting
We first show that can ensure privacy even if the smooth sensitivity $j is estimated approxi- mately; we then extend it to show that this works when f f(G) and $7,3 both are estimated approxi- mately.
Definition 6. 51,8 is said to be a yuuper approximation of the smooth sensitivity Sj,3 of function if (D) I (D)) S , (D) for any dataset D. S4,8 said to be (7,88 ) approximation of the smooth sensitivity 51 of function f if S f, is "-upper approximation for any dataset D with probability at least 8.2
We observe below that calibrating noise using a (7,8") -approxiiaiiiion of the smooth sensitivity gives us privacy. We assume f is a real valued function, since we are focused on graph statistics.
Lemma 2. (Lemmal 12) Let S5,9 be a (7, 8') aaprrxxmmatinn to S7 "T,s.for for y 3
lm(2/8) Then,
16c
A(D) (DD Lap( 25ra(D)) is (e, e1 -differrretlllll private.
Approximate Smooth Sensitivity for Approximate Query. We now show that approximate smooth sensitivity can be used even when f()) is computed approximately, which becomes a bit more challenging.
Let Ay be (a1, 81) approximation of a function (query) f for small constant a1 1/2. Let $y.9 be (2, d2p-up approximation $7.3. We will show that we can utilize Ay and $y,8 to calculate differentially private version of the function f.
For the purpose of privacy analysis, we define the functions gy: 8y, and Sg, as below. Those functions may not be computed efficiently. However, they are only used for the analysis, and the actual algorithm does not compute them. The actual computation (Algorithm 3) will only utilize A and $y to output the differentially private version of f. We follow some of the analysiss of [4] to prove our privacy guarantees below. We share (with (4] the same process of proving that S (D) is smooth-upper bound of the local sensitivity (Smooth Sensitivity) of gr- The main difference is our analyses has to take into account the newly defined function sy sy-which is bounded variant of the Approximate Smooth Sensitivity ($,,3, which approximates Sj.e), while [4] uses the global sensitivity GS, of f. As we can see in Lemma 13 the second condition requires (D) S e Sgy (D') for any pair of neighbor datasets D D'. While GS, remains unchanged both D and D', D Sy, may have different values for D and D' which makes it more difficult to analyze Sgy- We also have to take
into account the small probability 82 that (y.)(D) & {S (,,,)))),)))))))) that will add up in the 8- part of (c, 6)-DP of the final output.
Definition 7. Let , be an ( aaprrxximaaiion of f. We define functions 9j and 8 as: s (D) if (1 = A₂ s (1 -1- (n) (1
51
(L))))((D),
91
5
81 (DD(D) 5f (D),
(2)
e St, S e e),
Let Sg, (D) 4 (D) + (D)
Lemma 3. (Lemmal) 13) Given 9f. s,, and S, defined above, Sg is a 3'-smooth upper bound of the local sensitivity of 9f. where 8 2 4a, + 3 and a < 1/2.
In order prove that Sn is a f -mmoth upper bound of the local sensitivity of gy, we have to prove the two conditions: I.5,,, (D) < Sgr (D), and S,y (D) < e Sy for any pair of neighbor datasets D ~ D'. The full proof is in Lemma 13 in the SM. Theorem Ibelow summarizes our result.
Theorem 1. (Theorem 4 Let A be (a1, 61) approxixxnntaoonn to f. S5 be a (7, -upper Then, A(D) AD
4e approximation Sj.0. for 7 B mn2 0i In(2/55.
Lop( San (D) (c, e12+1 + 28, + 282) diffferrentlllllyy private.
5

---

4.1 Application: fast private triangle counting
In this section, we study the problem of computing fa(G), the number of triangles in a graph G),,V), by fast approximation of its smooth sensitivity. Recall the def- initions of local sensitivity at distance t, denoted by [,5 (G), defined in Section 3
We denote the local and smooth sensitivity of fa(G) by LS (G) and (G,)(G).
Let ai Ene(M) Au-Ask denote the number of common neighbors of nodes and j in a graph and bij = ΣkE( Ask @ Azk denote the number of nodes that are neighbors of i or j but not both. Then it has been shown that LS (G)
maxi, (1) where cig (4) min (ii + (+min(t.bb)) -0- 2) (Claim 3.13 of (31
2
We can rewrite this as L a (G) min(max. (aes + by + $) maxx Oij dittt, n- 2, max,,j aaj + 1 2).
2) min(m. ddegl)
2
The bottleneck in computing _ (G) (and S (G)) is estimating à max,, aij- We adapt the diamond sampling technique of [2) for this task. By doing that, we can quickly calculate LS (G) min( m
Figure 1:
Paths (i, J)
deg(t) +egg(i) + +. à at ?
2) The core idea in diamond sampling is to find a "diamond" (a 4-cycle) of the form (i, o, k) obtained by the intersection of two "wedges" (a 2-path) (i,, o. and (i, shown in Figure 1 Since any pair (f, is part of a? diamonds, the probability of selecting such a diamond is proportional to a.y. This idea is formalized in Algorithm 4 Let W be the matrix W deg(k) deg(i) for all (ks i) E E, and 0 for all other entries.
and (1,
represent
wedges formed nodes
by f.j
2
We first note that if à 0, it must be the 2-path i, J. then azj 2 1. Therefore, if à = 0, we can determine (s(() A (G) exactly in time ((m). Therefore, assume that à > 1 in the rest of this section.
that G has paths of length > for if there is
Even though Algorithm 4 can quickly estimate the quantity max of within specific bound, can only do so with the number of iterations that is sufficiently large-which its exact threshold is unknown without the access the dataset and the value of interest (max aty) itself (see Lemma 15) We overcome this issue with the following idca. First, we propose some estimation T of max at and an instance of Algorithm 4 with the number of iterations computed from Second, we compare the estimation of max at; returned by Algorithm 4 with T to determine we over- or under-estimate Third, we adjust accordingly and repeat the process until we find good value of r.
Algorithm 2 Algorithm to compute SA, (G) Input: G(E, V), 8, 6,7
Algorithm 1 I estimation Input: G(E,V V) Output: 7: < maxij oij
Output: (G)
1: T Algorithm G
1: k :== 0, Th = n², 0
2: while TRUE do
2: T = T
3: Calculate s
3o n [|
3: 0 .27-1
0*Th s)
4: x = Algorithm
4
c max (log, (1/ + 2, 1202)
5: if' maxx Tzj
Th then
5: Calculate 8 = 30 log W|
6: = Algorithm G.s)
6: TK+1 := 7
7:
k= k
7: a2 max,; m.y
8:
else
1-0
8: Calculate LS (G), I..., log (n)/3, using
9: Return Tk
10: end if
9: Return max (n)/a e LS (1) (G)
11:
end while
We implement Algorithm I based this idea. In the algorithm, we first set its largest possible value (n²) knowing that we are over-estimating 7 (T > max maxo))) We note that by over- estimating Algorithm (line 6) may not have enough iterations to guarantee the convergence of max.;; to max ały. Note that in the output of Algorithm 4 for any j, Tij is approximation of a?). We

---

determine if we are truly over-estimating T by applying Corollary B (in the SM), comparing the estimation max.y Baj from Algorithm 4 in line 6 to (3/2)r. The proof utilizes an idea that even though max zi may not converge to max aiy and we may not determine it directly, max zij can converge to r once we under-estimate T (i.e., T < max aty) and that we can check this convergence easily. Corollary 3 states that when max Zij < (3/2)T, max d; < 37 which means we should lower We keep running Algorithm 4 and reducing T by 3/4 /4 in each iteration until the estimation of max Wit lies above (3/2)r. By Corollary 3 we show that when it happens, T& S max aty that guarantees the convergence of max Zij to max dzy- Lemma shows that when the algorithm outputs The w.h.p., the true value of interest max ai is within Tu and 4Tk-
Lemma 4, (Lemma 18 in SM) Let Tk be the output of Algorithm With probability at least
1 - 1/n Tk < maxi; di < 4rk-
Algorithm 2 calculates an approximation of max dig for the Approximated Smooth Sensitivity with any y (which is required for Differential Privacy with an arbitrary e). Since is guaranteed to
be close to the true value of max d² (within a constant factor of 4), we run the last instance of Algorithm
with with some constant 0, which is derived from the target approximation factor y. Lemma 5
shows that the estimation output by Algorithm the true value. Following that, Theorem 2 guarantees that the quantity output by Algorithm 2 is
4 in line falls within the range of (1 - 0, 8,1 + 0 of
(7, 8) -ppper approximation to Smooth Sensitivity , of the triangle count graph G.
Lemma 5. (Lemma 19 in SM) With probability at least 1 - 8 in Algorithm max,j Lij
|W
(1 0, + 0) maxij dig-
Theorem 2. (Theorem in SM) Suppose max;; Oij > O. Algorithm 2 outpuas 5 which
(7,, uupper approxmiation Sa,s(G), in O log (+) [|[] log m log
m
time.
maxs; o2
Proof. (Sketch) Algorithm has a run-time of ks log m)) where s' O ([ elo n/ (02T) as it executes Algorithm with varying = s' and k is the number of search steps. Since at the end of the search 7k maxij of//4 /4 w.h.p., we know that k O(log max.y "t,
In the first step, start with To n and reduce Ts by factor of 3/4 after each step. The total running time will be W[I] x log clog
4n²
+ (1 (3/4) +... (3)4)-*> O [[W]]leloo m log Finally, maxes "
Algorithm 2 has a run-time of O log., (26)|[W]1, y log en log
log + taking into account the
m
maxis of
time required to compute W (0(m) and (G)) (O(log (n)/3 + n)) and substituting the values of and f as deseribed in the Algorithm.
Corollary 1. Suppose max.; aij > Gs (C, A) -ttraniitvvve (as in Definition 5. and 8 2 n22 Then, for any parameter 7 > 0. Algorithm 3 outputs Sa,s(G), which is a (7, -uppper approxmation to S4. Sa,a(G), in O(m max(1/C² ,A)) log m n/ min(7 1/4) + n) time.
min()*,1/4). Next, for any node i and j E Nr. we have max,y, 1 a.y S m A}: if deg(j) > A, it must be the case that at least C-fraction of the paths i, k for k E N2 are closed, which means degli)
Proof. Since
2+T+1 7dt for < << 1/V2, we have 2-
deg(i)
aij 2 C. -deg(í), and so max;ry agz fore, I|WII maxx; at
deg(s)
di if deg(i) I A, we have mux,yy auy A. There- degl))xdeg(i)
E Eiev(o) max,,, ans ΣjEN, max, Oege Eiev(c) Ejen, (axxxtt,,00 2m max( 7z, A2), the Corollary follows.
EiEv(o) EjEN, muxe, az
deg(s)
deg(i)
L
5 Higher-order local sensitivity and improved bounds for path counting
As mentioned earlier in Section 2 Karwa et al. 23 develop different technique involving local sensitivity of the local sensitivity, and use it for private counts of k-cliques, since it seems hard to
7

---

rs
Exaples of compact subgraphs and anchor edges in the algorithm for computing higher-order sensitivity of paths: (Iefft) D {r1, 74), edges (r1,11), (r2,72). (13,7') and (r4,74) are external anchor edges, while (rs;76) is an internal anchor edge. Nodes and the starting and ending nodes of the path; (Middle) D = {m,, r2, r3), and (ri, rí), re), (r3, r4) are external anchor edges, while (rs, r/)) is an internal anchor edge. Node s is the starting node of the path, and the path ends at some other node, not in this compact subgraph: (Right) D = (2,, ra. edges (f), (r2,12), (ra, (r).rs)
Figure 2:
and (ra, are external anchor edges, while (ks) and (ra, rá) are internal anchor edges. Paths pass through this compact subgraph, without starting ending in it.
estimate smooth sensitivity for such subgraphs. We generalize it, and develop multi-level local sensitivity approach, extending [23], for privately counting the number of copies of any subgraph Hı; as in the case of smooth sensitivity, we show that this also works with approximate queries.
Let denote the number of edges in H. Our main idea involves finding private bounds for higher- order local sensitivity. Let L [i.j] iij E V} denote all possible pairs of nodes in V. For subgraph H, and subset C {{i,}] : 1.j V] of pairs of nodes, let fH S) denote the number of embeddings of H in the graph G(V, EUS), which contain all the edges corresponding to pairs of nodes in S. For the subscript H when it is clear from the context. Let (G) = s f fG, S); note that (C) = (G). It can be seen that (+)) & (()+ which the basis for considering higher-order local sensitivity for subgraph counting. However, careful analysis of the privacy bounds becomes involved. Our approach is described in Algorithm 5 the supplementary material, and the main result is summarized below.
0, fH 0) is the number of embeddings of H in G. We drop
Theorem 3. Let g (G) = (G) + gl 1n + (G) (tp(g(t+"(())e))) for k = 1-1..... as computed Algorithm Then, (0)) (G) is an ((km + 1)e2, 82 + (km + 22) estimate of S(G).
The above result, and the definition of (G) implies that for any subgraph with l edges, the higher-order local sensitivity approach can be run in time Onn²²). This can be improved further for paths and trees, summarized below.
Lemma 6. Private counting for a graph H with constant i number of edges using higher-order local sensitivity (Algorithm 5) has running time O(n²)), When H is path or tree with & edges, Algorithm 5 has rumning time (nf+1))
Higher-order local sensitivity with approximate queries. We show that our method works even if we have very good approximation ((x) to f(x) instead of the exact value (Theorem 7 in the supplementary material). This allows us to use f(x)) instead of f(x) in Algorithm
Improved bounds for path counting in graphs with bounded degeneracy and treewidth. We say that G has degeneracy d, if the nodes can be ordered so that each node has at most d neighbors with higher index [13]. Informally, G' has treewidth if it has recursive balanced separators of size t; see [IT for details. There has been lot of work showing that non non-private algorithms for subgraph counting can be done efficiently when G has either of these parameters bounded, e.g., [3 IT. We show that G has degeneracy d and treewidth i, then the higher-order local sensitivity paths of length & can be computed in time ((h(d, t,, k)))))(n)), where hdd, f, k) is independent of n; thus the running time does not scale as *²
Our algorithm and analysis summarized in Section B in the supplementary material (Theorem Recall that the goal is to compute (G) max S). We summarize the main ideas here. We show that feasible solution, which involves fixing subset S of pairs of nodes, can be viewed a tuple of at most & disjoint subgraphs (H, D:), referred to k-compact subgraphs. This is

---

Network
Description
#nodes
#edges
#triangles
Oregon-1
AS peering information-Oreeon route-views
10,670
22,002
17.145
ca-HepTTh
Collaboration network-Arxiv High Energy Physics
9,877
51,971
28,339
ca-GrQe
Collaboration network-Arxi General Relativity
5,242
14,496
48,620
Oregon-2
AS peering information-Oreg route-views
10,900
31.h180
82,857
ca-CondMat
Collaboration network-Arxiv Condensed Matter
23,133
186,936
173,361
loc-Brighkkite
Brightkite location based online social network
58,228
428,156
494,728
com-Amazon
Amazon product network
334,863
925,872
667,129
email-Enron
Email communication network- Enron
36,692
367,662
727,044
ca-AstroPh
Collaboration network-Arxiv Astro Physics
18,772
198,110
1.35 x 106
com-DBLP
DBLP collaboration network
317,080
2,099,732
2.22 X 106
loc-Gowalla
Gowalla location based online social network
196,591
950,327
2.27 106
ca-HepPh
Collaboration network-Arxiv High Energy Physics
12,008
237,010
3.36 106
Table 2: Statistics of tested networks.
defined to be subgraph which satisfies the following conditions (Figure (1) - F()) for some node and subset F()) = fei,..., c.) where G. is the k-hop graph starting at node only restricted to higher degeneracy order nodes than v, (2) the k-hop neighborhood is expanded as edges in pP() (referred
time, and (3) D is subset of vertices in H, and is referred to as the set of connectors. The compact subgraphs are connected via edges between connector nodes.
internal anchor edges) are added,
We show that paths using edges from (which contribute to the count f(G, S)) can be viewed to consist of segments within these compact subgraphs, passing through internal anchor edges, well as edges between connectors (which are also from S). We guess the number of path segments between connectors within factor of of compact subgraphs with the corresponding approximate counts. We show that the number of such tuples is (h(dd, ())))y(n)) and existence of given tuple can be determined in similar time.
1/olo n))) for constant c, which allows to search for tuple
Experimental Results
We evaluate algorithm for privately computing #triangles using approximate smooth sensitivity (Algorithm 2). compared with the exact version of smooth sensitivity and other baselines.
Datasets. We consider different real-world networks from [26] as inputs. The networks have have sizes range from 10K - 300K nodes, with one the largest ones having over 2 million edges. Statistics of the networks are presented in Table Due space limit, we only present the results for some selected networks here. The full results are presented the SM.
Infrastructure. All algorithms are implemented in C++ and OpenMP framework for parallelization. We ran our experiments on system with 48-core Intel(R) Xeon(R) Gold 6248R CPU 3.00GHz and 1.5TB RAM and limit the number of parallel threads in all experiments to 40.
Baselines. We implement two baseline methods: the exact smooth sensitivity of triangle count to
calibrate Laplacian noise (denoted our experiment as Karwa et al.) 23 and using the ladder function method (Zhang al.) (36).
Metries for evaluating performance. For each input network G, we calculate following metrics: Accuracy of the private triangle counts, defined as TRIANGLE COUNT RELATIVE ERROR
|M (G)) where Mf. is the tested private mechanism to output fa (G).
(a(G)
Speedup of Algorithm 2 which compares its running time with the time required for [36 23
SPEEDUP Runtime of haseline algorithm on G7 (Figure 5).
Runtime our aigorithm on
Approximation error of Algorithm for estimating smooth sensitivity, defined as SENSITIVITY
A APROXIMATTOON ERROR = ((GG)-S,(C) 4)..
Sz(G)
Parameters. test our algorithms at different privacy budgets (21-3.-2.110.11) and fixed j = 10-6 We report the average accuracy and runtime of five (5) repeats of the private triangle count via approximate smooth sensitivity experiments due to the randomness used the algorithm. For the exact calculation, calculate the smooth sensitivity once and re-sample the noise in each since

---

the exact calculation of the sensitivity is deterministic and does not change for each setting, We use the true counts of triangles of the networks as reported by (26]
Croar
Droper
4.00
1.00
10011
0.0
Figure 3: Triangle Count Relative Error, show- ing the accuracy the private triangle count with noise calibrated by (1) our approximate smooth sensitivity (Algorithmß) _ (2) the exact smooth sen- sitivity (Karwa et al.), and (3) the ladder function (Zhang et al.)
Figure 4: Error factor in approximate smooth sen- sitivity output by Algorithm ( (relative to the exact smooth sensitivity) on selected networks. Dotted lines indicate the theoretical upper bound factor e (guaranteed by Theorem 2
Experimental Results. The results show that our algorithm can achieve similar levels of accuracy to the exact calculation while being several orders of magintude faster. Figure 3 shows that when using approximate smooth sensitivity, the private triangle counts reach the accuracy of using the exact cal- culation of the smooth sensitivity across different privacy budgets in all but two networks (Oregon and Oregon 2). In these two networks, the smooth sensitivities are relatively large in comparison with the triangle counts, which makes the noise fluctuate more for the approximate estimate (see Figure 8
Seeo Dt
Spnoho
2
Figure 5: Speedup of Algorithm 2 over the exact smooth sensitivity (Karwa et al.), and the ladder Figure 4 shows that all approximate smooth sensitivid fitgeiirrehwttim Shitle' Attaa /estee///dtte smooth sensitivities. Noter that approximate smooth sensitivities are always larger than the true smooth sensitivity. It important since a lower value may expose the privacy due an inadequate noise magnitude. In general, a smaller value of (higher privacy guarantee) requires a more accurate estimation of the sensitivity. It is illustrated in Figure 4 as the approximate smooth sensitivity is close to the exact smooth sensitivity in all networks at = 0.125 = 0.25.
FigureJJshows that approximation algorithm is orders of magnitude faster than the exact algorithm. In large graphs (Amazon, DBLP, Gowalla), the speedup may reach 1, 000-fold. Generally, lower e requires smaller approximation factor (7), which in turn requires larger number of iterations to reduce the error in approximation. The majority of tested networks have speedup factors between 10 and 100-fold across all privacy budgets c.
7 Conclusions and future work
We give significant improvement in the running time for privately counting the number of embeddings of constant size subgraphs a graph, without using noise based on global sensitivity. Despite a lot of work private subgraph counting, efficient algorithms were not known for many subgraphs. Our results for triangles show significant benefits of our approach, by improving on the runtime over all prior private algorithms. Our approach of using approximations to sensitivity metrics opens the possibility of using other techniques from graph sampling and sketching to obtain more efficient algorithms. For general subgraphs, our focus here has been theoretical bounds using multi-level local sensitivity combined with approximate queries. Developing efficient and practical algorithms for these problems is a good direction for future work.
10

---

Acknowledgments and Disclosure of Funding
This work was partially supported in part by the following grants: National Science Foundation Grants CCF-19 18656 (Expeditions), DAC-1916805 (CINES), IIS-1955797, and CNS-2317193, VDH Grant PV-BII VDH COVID-19 Modeling Program VDH-21-50100135, DTRA subcontract/ARA S-D00189- 35-T000--VAA NIH 2R01GM1097 18 18-07, CDC MIND cooperative agreement U01 CO1CK000589, and the U.S. DOE Exascale Computing Project's (ECP) (17-SC-20-SC) ExaGraph codesign center at Pacific Northwest National Laboratory.
References
[1] Hilal Asi and John C. Duchi. mustance-optimalle in differential privacy via approximate inverse sensitivity mechanisms. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS 20, Red Hook, NY, USA, 2020. Curran Associates Inc.
[2] Grey Ballard, Tamara Kolda, Ali Pinar, and C Seshadhri. Diamond sampling for approximate maximum all all-pairs not-product (mad) search. In 2015 IEEE International Conference Data Mining, pages 10-20. IEEE, 2015.
[3] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. Differentially private data analysis of social networks via restricted sensitivity. In Proceedings of the 4th Conference Innovations in T'eooreical Computer Science, ITCS '13, page 87-96, New York, NY, USA, 2013. Association for Computing Machinery.
[4] Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee, and Samson Zhou. How to make your approximation algorithm private: A black-box differentially-prine privvate transformation for tunable approximation algorithms of functions with low sensitivity. arXiv preprint arXiv:2210.03831/ 2022.
[5] Marco Bressan. Faster subgraph counting in sparse graphs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Schloss Dugstuhl--eeinniz-zenn fuer Informatik, 2019.
[6] Marco Bressan and Mare Roth. Exact and approximate pattern counting in degenerate graphs: New algorithms. hardness results, and complexity dichotomies. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 276 276-285, IEEE, 2022.
[7] Shixi Chen and Shuigeng Zhou, Recursive mechanism: Towards node differential privacy and unrestricted joins. In Proceedings of the 2013 ACM SIGMOD International Conference New York, NY, USA, 2013. Association
Management of Data, SIGMOD 113, page 653-6634
for Computing Machinery.
[8] Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fant Nikos Parotsidis, and Jakub M Tarnawski. Near-optimal correlation clustering with privacy. Advances in Neural Information Processing Systems, 11-33702-337155 2022.
[9] Laxman Dhulipala, Quanquan C Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, and Shangdi Yu. Diffcrential privacy from locally adjustable graph algorithms: k-core decomposi- tion, low out-degree ordering, and densest subgraphs. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 754-765. IEEE, 2022.
[10] Xiaofeng Ding, Xiaodong Zhang, Zhifeng Bao, and Hai Jin. ing in large graphs. In Proceedings of the 27th ACM international conference information and knowledge management, pages 1283-1292, 2018
triangle count-
[11] Rodney G Downey and Michael R Fellows. Fundamentals of parameterized complexity, volume 4. Springer, 2013.
[12] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Founda- tions and Trends@ in Theoretical Computer Science, (13-4):211-407 2014.
[13] David Eppstein, Maarten Löffler, and Darren Strash. Listing all maximal cliques in sparse graphs in near-optimal time. arXiv preprint 4rX1v.1006.5440, 2010. 2010.

---

[14] Michael Hay, Chao Li, Gerome Miklau, and David Jensen. Accurate estimation of the degree distribution of private networks. In 2009 Ninth IEEE International Conference on Data Mining. pages 169-178, 2009.
[15] Jonathan Hehir, Aleksandra Slavkovic, and Xiaoyue Niu, Consistency of privacy-preserving spectral clustering under the stochastic block model. arXiv preprint arXiv:210S. 2021.
[16] Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. Locally differentially private analysis of graph statistics. In 30th USENIX Symposium on Security, 2021.
[17] Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. {Communication-Efficiie triangle counting under local differential privacy. In 31st USENIX Security Symposium (USENIX Security 22), pages 537-554, 2022.
[18] Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. Differentially private subgraph counting in the shuffle model. arXiv preprint 2Xiv:2205.001429 2022.
[19] Shweta Jain and C Seshadhri. A fast and provable method for estimating clique counts using turán's ' theorem. In Proceedings of the 26th international conference on world wide web, pages 441 0191 2017.
[20] Madhav Jha, C Seshadhri, and Ali Pinar. Path sampling: A fast and provable method for estimating 4-vertex subgraph counts. In Proceedings of the 24th international conference on world wide web, pages 495-505, 2015.
[21] Tianxi Ji, Changqing Luo, Yifan Guo, Jinlong Ji, Weixian Liao, and Pan Li. Differentially private community detection in attributed social networks. In Asian Conference Machine Learning, pages 16-31. PMLR, 2019.
[22] Tianxi Ji, Changqing Luo, Yifan Guo, Qianlong Wang, Lixing Yu, and Pan Li. Community detection in online social networks: A differentially private and parsimonious approach. IEEE transactions on computational social systems, 7(1):151-163, 2020.
[23] Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, and Grigory Yaroslavtsev. Private analysis of graph structure. ACM Transactions on Database Systems (TODS), 39(3):1-33, 2014.
[24] Shiva P Kasiviswanathan and Adam Smith. On the' semantics' of differential privacy: A bayesian formulation. Journal of Privacy and Confidentiality, 6(1), 2014.
[25] Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Analyz- ing graphs with node differential privacy. In Proceedings of the 10th Theory of Cryptography Conference on Theory of Cryptography, TCC' 13, pages 457-476, Berlin, Heidelberg, 2013. Springer- Springer-Verlag.
[26] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http::///nap.ssaaa..eo.
edt/data, June 2014.
[27] Yang Li, Michael Purcell, Thierry Rakotoarivelo, David Smith, Thilina Ranbaduge, and Kee Siong Ng. Private graph data release: A survey. ACM Comput. Surv., jan 2023. Just Accepted.
[28] Yvonne Mülle, Chris Clifton, and Klemens Böhm. Privacy-integrated graph clustering through differential privacy. In EDBT/ICDT Workshops, volume 157, 2015.
[29] Dung Nguyen and Anil Vullikanti. Differentially private densest subgraph detection. In 38th International Conference on Machine Learning (ICML). PMLR, July 2021.
[30] Hiep H Nguyen, Abdessamad Imine, and Michaël Rusinowitch. Detecting communities under differential privacy. In Proceedings of the 2016 ACM on Workshop on Privacy in the Electronic Society, pages 83-93, 2016.
[31] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thitty-ninth annual ACM symposium on Theory of computing, pages 75-84, 2007.
12

---

[32] Davide Proserpio, Sharon Goldberg, and Frank McSherry. Calibrating data to sensitivity in private data analysis. Proceedings of the VLDB Endowment, 7(8), 2014.
[33] Zhan Qin, Ting Yu, Yin Yang, Issa Khalil, Xiaokui Xiao, and Kui Ren. Generating synthetic decentralized social graphs with local differential privacy. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 425 4388, 2017.
[34] Vibhor Rastogi, Michael Hay, Gerome Miklau, and Dan Suciu. Relationship privacy: Output perturbation for queries with joins. In Proceedings of the Twenty-Eightl ACM SIGMOD- SIGACT-SIGART Symposium on Principles of Database Systems, PODS '09, page 107-116, New York, NY, USA, 2009. Association for Computing Machinery.
[35] Jessica Shi, Laxman Dhulipala, and Julian Shun. Parallel clique counting and peeling algorithms. In SIAM Conference on Applied and Computational Discrete Algorithmss (ACDA21), pages 135 146. SIAM, 2021.
[36] Jun Zhang, Graham Cormode, Cecilia M. Procopiue, Divesh Srivastava, and Xiaokui Xiao. Private release of graph statistics using ladder functions. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, SIGMOD 15, page 731-745, New York, NY, USA, 2015, Association for Computing Machinery.
13

---

A Differential Privacy with high probability
Following [24], we define Indistinguishability and Point-wise Indistinguishabiityy as follows:
Definition 8. Two random variables X, Y having the same support are (e, -)-iidddstiinnuihhbble if for all set O S (upp(X),
S Pr[X S Pr(Y E + ó and Pr(Y E O < e Pr\Y +
Definition 9. Two random variables X, Y are point-wise (c, -ndiiiindsstinnuuhhhbbll with probability at least 5 over a drawn from either X or Y, we have:
Pr|Y a| S Pr[X - a) S Pr(Y =
The following lemma allows us to interpret a mechanism that is e-differentially private with probability least 1 (c,8) ddiffferrte private.
Lemma 7. (Lemma 3.3 of (24)) If X,Y point-wise (e, indistiiiiistt then they are (e, 6)- indistinguishable.
We extend the definition of (e, iiiiiniiiiinn by allowing some small error probability 8': Definition 10. Two random variables X, Y having the same Support are (e, ö, ( -indistinguishhbbl if for all set O S Supp(X), with probability at least 1 8 over drawn from either X or Y, we have:
Pr[X e O] e" Pr(Y E +] and Pr[Y E 0] ee E +
The following lemma allows us to interpret a mechanism that (c, diffferrnttl private with probability least 1 - 5' (c, d'fferrrrrentialll private.
Lemma 8. If X, Y are (c, 6, 8") -nniistiinnuiihabbliit then they are (c, 5 + 8') indisttinguishable
Proof. Our proof is insired by 24
We define the set Bad as follow:
Bad (0: E 0J P e o Pr(y E E Pr\Y 0]+
Since X, Y are (c, (i...,)liinisiinnuihhblllll Pr[X Bad] < 8. We have:
Pr[X e OJ S Pr[X e 0 Bad + + e Bad se E Bad] +8+0 8' Se E0 5
Similarly for Y, we have Pr[Y E c <e Pr[X 0] 8 8' and the Lemma follows.
B Missing proofs of Section
Approximate Smooth Sensitivity for exact queries
When calculate 7-approximation of the smooth sensitivity $7.3. i.e., Sy.9 is bounded approximation of S with probability 1, we can substitute $7.3 by Sy to calibrate the noise directly, although with bit larger effective constant 3' = + 7, which in turn will make the noise bit larger. Lemma formalizes the equivalence of Sj and $3.8 in this case.
Lemma 9. If $5,9 is a y-approximattin of the smooth sensitivity Sj.9. then Sy is a 8 smoohhhh sensitivity of 3' B +%
14

---

Proof. By definition of $1,9 and 55 it follows that S1,((D) (0 2 LS)(D) for all z.
Second, for all D D' E D have: (D,) S e a (D) ert (ra()) S e (D,) the lemma follows from Definition 2
s
In the case when we can only calculate (7, "aapproximaaioon of the smooth sensitivity, i.e., S is a 7-approximation of $i,3 with probability at least 1 - 8', Lemmaa 9
cannot be directly applied.
Similar to [1], we use the formalism of admissible noise, to prove we can use $y.9 to calibrate an (a, 8) adddisiieee noise with appropriate values of a and / to deliver the privacy guarantee. In Lemma 10, we analyze the output of such a mechanism on an arbitrary pair of neighbors D and D'. We condition our analysis on the events of success of Sy.9 on both D and D' (with probability at least 1 1 28"). The failure probability (at most 28') will then add up to the 8-part of the final (e, ()DP guarantee.
Lemma 10. Let h be (a, (a-d"sdaimsssbblee noise. Let S5.8 be a (r, 8') (aa'''aaapoximmation to S1 where
8 = 3' n. Then, A(D) f(D) (r Z is (e, 11 + 28' differentiallly private, where Z ~ h.
Proof. We prove that with probability at least 1- - 28', A(D) is (c, 8) diffferrentll private, and by applying Lemma g the Lemma follows.
Let & be the event that (D) S (),((D) S (D): we have Pr[E] 2 8'. Similarly, let E' be the event that (D') < (D,(DD) S <D') for a fixed neighbor D' of D; we have
Pr(E"] 2 1 - 8,, and Pr[E
28'. We will condition on & E.E.
Let C IR Let N(D) = St.(D)) and define S = S-f(D) NDD) S² = SS + 1(D) ((D) S-f(D')
N(D)
NDD
S3 = S2 N(D) N(D')
N(D) S-f(D")
We observe that A(D E S and only if E St. Similarly, A(D') E if and only if E S3. We have
Pr(A(D) E|] = Pr|Z E 81 S // Pr EE + S(D) -
+ 06/2
N(D)
In N(D)
e2 S2) + 5/2 c Pr Z Exep
+ +
N(D')
er E 53] + 2282 + 6/2 = e PP(AADD) E S] + (ee/2 + 1
where the first inequality is because of Sliding Property and - - s(D') -(D) S(D))
$ (I(D) - S(D') Sa,
N(D) = =a (1,)(D)
SD(D)
which satisfies the condition for the Sliding Property, and the second inequality is because of Dilation Property and (e(
N(D) N(D) = In (r.e(D) (
(D) I In e S-(D')
)
Inc s
which satisfies the condition for the Dilation Property.
Lemma specializes Lemma 10 by using Laplacian noise. We note that this is a generalization of 31'ss s analysis of Laplacian noise. We introduce parameter l to control the magnitude of the I Laplacian noise, while '31's analysis fixed it to 1. This design gives us the flexibility to choose the values of a and B given fixed targets of & and 8. When A = 1/2, our design yields the same results as (31].
15

---

Lemma 11. Let
2 ke and B log(2/8) for any constamt k 0, then Lap(2k) is an (ax, B)-
admissible noise.
Proof. For som real-valued random variable Y, let ps PY( be the least solution Pr(Y ps] 8. We will solve the
Let 8' 8/2. Let Z Lap(2k). follows that / Exponentiaa(1(((33) value of ps (lZ)) as: - e (12))) = 1 1 8' or ps (lZ)) log[2/8)
26
Substituting ps (12)) the formula of B, we have:
2h
3
log( (2/5)
hee
ps ((2)
We first prove the Sliding property of Lap(2k). It is equivalent to prove that In( (A(e-A)
h(z) S c/2 for
any A a and h(z) is the PDF of Lap(2k). For the distribution Lap(2k), h(z) 1 1111/22))
We have:
((z+A4)
(exp(-Ia+ (l/(k))
In
= In
h(z)
exp(-l=l/(2k))
1
(12) -
2a + A
2k
A
2h
- Ke
2k:
We next prove the Dilation property of Lap(2k), or prove that In( <)((=)) S e/2 with probability
at least - 8/2. In the first case, setting 0, we have h(e>2) < h(z). and that In( <h(e² 2)
S
h(=)
S P&r (1Z Since |2| ~ Erponentia((1((22) the median of the distribution of |Z| is 1n(2)
T/(2k]
2 (n(k)). With 5 1, have 8' 1/2 and therefore ps ([Z)) 2 median(IZ) 21n 2ln(2),.
follows that In( e>A(e=z)
Ie
h(=)
In the second case, < 0. We consider the ratio A((=z),
h(z)
h(e²2)
exp( be // (2k))
h(z)
exp(
- |x1/(2k) (2k))
|2|| (1 e^))
cxp
2k
|
S exp
2k A1
We then have In
A
S A+
|ENA
|
Consider the event G [2: |2| < ps (IZ)). Under
h(z)
2k
2k
G. have |
S
ps
(121)
p
Under Pr[G] 1- 88/2, which completes the
proof for the Dilation property of T.pp (2).
16

---

Finally, we apply Laplacian noise with appropriate parameters to provide a concrete mechanism using Approximate Smooth Sensitivity $4,3 to guarantee (e, 6).P.
Lemma 12. (Lemma 2 Let S5,8 be a (7, "rp'""-appxximmation to Sj.9 for 7 =
16c
Then,
[n(2/o)
1 5 - 2d'-difeerelntially private. A(D) (DD) Lay( 23 25))l is (e, 2
Proof. Set k using Lemma with a kc 4c, and = 3 - im(2/5)
2k Then, In(2/8)
from Lemma 11 the Lap(2k) 2k) = Lap(8) distribution is (a, -ddmissiis By Lemma 10 A(D) =
S(D) + StalD) 7 = S(D) + S),( Lap(8) f(D) + Lap(28),s(D)/e) is (e, + + 28
differentially private and the corollary follows.
Approximate Smooth Sensitivity for Approximate queries
Definition 11. (Definition 7
We define functions 9, and s as:
91
(1- (1=
(3)
8f
if {),(()), e))),((D) (
(4)
Let Sg, (D) 401gg(D) + (D)
Algorithm 3 Fast algorithm using Approximate Smooth Sensitivity for Approximate Query A,
Input: f, c,
Output: (c /2 + diffeeiiferenntilly private estimaton of query f
1: B ;= 4a [Tog(2/8]
2: 81 02 = 8/2
3: Calculate the (7, 82) -upper approximate smooth sensitivity (G))
4: Calculate the (a1, 61 approxxmate f (G)
5: Return (G) 8a1 485) Lap(1)
Lemma 13 proves that Soy is -mmmoohhh upper bound of the local sensitivity of gy, i.e. we have to prove the Two conditions:
LSy, (D) < (D), and
Sg, e Sg, (D') for any pair of neighbor datasets D D'..
where LSy, (D) maz (D) gf() or the local sensitivity of gj at D.
Lemma 13. (Lemma 3) Given 9,, sy, and Sg, defined above, Sy, is 3' smooth upper bound of the local sensitivity of 91, where 3' > 4aq + 7 + B and a₁ < 1/2.
17

---

Proof. We now prove the two conditions. We first start with proving Sg, is an upper bound on the local sensitivity LSS,, of gs:
LS (D) =
max
D':D'>D
max
[()++a:)(()) - (1 - a1)
D':D'=
max oillf(D)+ +I - f(D'Il
D':D'~D
< (0n((D)+211,(())
S (D) (D)+
S,
The first inequality uses Definition and the fifth uses the facts, f(D) < D) DD), and LD) (D) (as S (D) is upper bound on LD) For the second condition, we need prove that for any pair D', the values of Sg on them do not differ by more than multiplicative factor of eº with 3 = 4a1 + + + 3.
Sg, (D) = (D)
S 4an (l](+
S (o([++aa(((()+++ss))))))) +2,))
+ (D)
1-0 (r( 2(2a))))) (1) (D())
S 40
4ag) s (D))
s 401(1+ 4a1gg ((( (D')
s
c² Sz, (D')
We note that 8y, 9y, and S, are all hypothetical functions, which we may not calculate directly. We need to connect the statement above (S,, is a Smooth Sensitivity of gj) to the functions we can compute (A, and Sy.s). Again, we define hypothetical mechanism A' that takes D as its input. By the definition of A' and the properties of admissible noise, A' is (c, 5'--DP Instead of A', we can only calculate A. by replacing 9/ and s by A, and $,.9 respectively. Next, argue that A and A' are, in fact, not too different. Lemma 14 conditions on the probability that A and A' are the same and prove that the privacy guarantee of A' the same with of A in such condition. The failure probabilities (of Ay and 5 in approximation of f and S,) will add up to the ó-part of the final (e, 6DP.
Lemma 14. Let h be (a, 8') addmissibee noise with B' 4a + + B. With A and S4,5 defined as above, Algoritium A(D) (D) 4a (D) ((() Z is (c. e-22 8 + 28, diffeeiifeyyttially private, where Z ~
Proof. We prove that with probability at least 28, 282, A(x) is (c, " 8) difffrrentiall private, and by applying Lemma the Lemma follows.
Let A'(D) (D) + Se z DD) + (D)2, Z, as we replace A and $5 by gs and @ 8y respectively. We note that the use of gf and 8 is only for the purpose of privacy bound analysis.
With 3' > 4aj + + 8, Lemma 3 shows that Sn is a 8 -moohh upper bound on the sensitivity of
gf. By Lemma 10 A'(D) (D) + Sut Z is (e, 1/2+18) -ddffferrnee private.
18

---

Since with probability at least 1 - 81, Ay(D) is gD and at least 1 - 62. Sy,s(D) (D is (D), with probability least 1 51 82, AD) has the same components as (D), hence they are identical.
For fixed neighbor D ~ D, we also have that A'( is identical with A'(D') with probability
at least 81 82. By Lemma g A(D), A(D") are (e, = 8, 26, + 262) 2b))-nndisinguuihaabt.
follows that AD) is (c.
+1 8 261 262) diiffrreniilll private.
2
Theorem (Theorem Let A be (01, 61) approximation to Sy,s be a (7, uuper approxima tion to S7.9. for B 1n(2/8) 01 In(2/8y- Then, A(D) Af(D) + Lap( 80n A
is (e, +16 8 261 + 28²) -iifedeifery private.
Proof.
Set k = 4, using Lemma 11 with a = ke = 4c, and 3 3 + + 4a =
32c
[m(2/8]
2 (m(2
Then, from Lemma 11 the Lap(2k) Lap(8) distribution (a, Jadmmmisisse.e.e By
14 A(D) = S(D) + Ste(D) 7 = S(D) + S1 Lap(8) = S(D) + Lap( 28, ( is
Lemma
(c,
+ 261 + 262) -iddiiffreeetlllly private and the Theorem follows.
C Missing proofs of Section
The main target of this section is to calculate an approximation of max azy. such that we can apply to approximate 7-approximation of SA,9 for any and B. There are three key components of the analysis:
Algorithm 4 uses diamond sampling to quickly calculate Zay that approximates a?; for every j.j. We use this algorithm as an important sub-routine in Algorithm and Lemma shows the utility of the algorithm. We note that due to the Lemma, the quality of each estimation Tij depends on the true value at ithelf-which unknown and is the value we are trying get. Hence, we cannot directly apply Algorithm to to get any appooopooinntiion of max diy as we need.
Algorithm [ usses multiple rounds of Algorithm 4 with increasing numbers of iterations. The main idea behind this process is that, with small number of iterations, Algorithm 4 executes very quickly and gives us a rough estimation Zij of ož for every i, We then check if the estimation is good enough. We know the estimation is considered good when max,y Diy < 3 Th x (some constants]. Corollary 3 will explain why. Finally, Lemma 18 concludes the utility of the output of the algorithm, such that after the last iteration k, Tk at most 4 times the value of max o?y-
Algorithm further improves the output of Algorithm I Now know roughly how large max?, is, but only within a factor of 4. We will run the final instance of Algorithm 4 with a special constant 0, which we use to control the approximation of the final estimation. is set by y-the approximation level required for a-approximation of the smooth sensitivity described by the previous section (which in turn is set by (c, 6)). Lemma 19 concludes the final utility of our estimation.
We define the norm of matrix A as follows: ||||| = 114|= 11 Σ. A..- Note that
|
degree d(i) ||A ll. d() ||1- A:l. The following concentration bound is shown in (2) for the
output of Algorithm
Lemma 15. Lemma of [2]. Fix 0 0 and error probability B. For any ag if the number of samples > log[2//1 (B/ then
Pr
Tzj
W
at
002
SB.
(5)
The following two lemmas and corollaries relate upper and lower bounds on the random variable maxi Iig output by Algorithm 4 to the quantity of interest, maxij ofy-
19

---

Algorithm 4 Fast estimation of (azz)² Input: G(V, F), Number iterations 8
Output: Fig that approximates aly. for all j
1: Let A be the adjacency matrix of G
2: for (k, i) E E do
3: Wa = d())d(()
4: end for
5:
6:
for 1or--,,.... do
7:
Sample (k: i) with probability Wai/ [/]/
8:
Sample j from N₁
9: Sample from N
10: Zut Aoj Aoj
end for
12:
Return x
Lemma states that if we choose constant that is close but larger than max aax then after running Algorithm 4
with s iterations, the maximum of Tzy is not larger than T x /some constants). Similarly, Lemma states that if we choose a constant T that close but smaller than max a.j: then after running Algorithm 4 with iterations, the maximum of Tay is not smaller than x (some constants).
With appropriate selections of the constants, Corollary 2 and 2 summarize the two lemmas and describe the condition in which we may find good value for They allow to observe the output of an instance of Algorithm Sammmmaand and compare the outcome with pre-determined value of 7. Depending on the sign of the comparision max Tij
|| 2 we can decide that if we are over-estimating (by Corollary under-estimating (by Corollary
The two lemmas and their corollaries below form the basis for Algorithm Ihhat finds an appropriate value of using binary search.
Lemma 16. For any such that maxi; dis < AT for some constant < X, there exists constant X such that with probability at least 1 poly(ns max.j zsl W| X'..
Proof. Consider any i.j. By Chernoff's bound,
(
Pr(me > (1 + 0')[[(el)] S exp
3
As B[ray]] = a [W]] we have that
0 0
Pr[my
> (1 + 0')a2,l s exp
Setting X' (2+0")a
we have:
X'T
1 1+ 0' ?
Therefore, we can lower bound 0' as follows:
XT
XT 0
0
N Ar
dt)
T(X' A)
since oz Ar.
20

---

Now, we substitute (1+ aa by A'::
WIl
02
Pr(mi
XT) - exp
3||l|
0
W log fan
exa
3 M W|1T
c 12
exp
0CT
T T² 2) at log
< exp
a eCT
7(M' - clog
exp
(X' - A)
S exp
clog
A02
n
A92
Selecting X > A.t (2-2)) 282
2 and taking the union bound on all pairs ij, the Lemma follows.
Corollary 2. With
3,0
1,
X z. with probability at least 1 1/n=-?, if
maxij Tij [W'll 3 then maxij o.j > T.
Lemma 17. For any such that maxij 2z) XT for some constant 0 then there exists
constant X" s (1 0)2 such that with probability least 1 poly(n)) mazaj mss [|ll
2 X²
Proof. Since maxij a > Ar, there exists pairs of nodes j' such that az > Ar. For such pairs
i'j', we have:
saaa
Pr ryy
(1
0)0ky
$ exp
3||
30 y clog
exp
3/2
a cggcclonn
exp
S exp
(-Aclogn) n) -cA
(1 (1-8)a3
Setting X" < (1 0)1, we have X" <
or A S (1 0)agy- Therefore
Pr 273 |W]| 7 s Pr प [W] <1 00 I cc Choosing e such that cA >
s
and taking the union bound over all pairs j'j the Lemma follows.
Corollary 3. With
3,
2. = 3. X"
3 2
with probability at least 1 1/n if
maxij Tiş [WIl < & then maxij d < 3T.
Lemma 18. (Lemma
+ Let is the output of Algorithm 7 with probability at least 1/n0-3,
Th < maxij at 4Tk.
Proof. Assume the Algorithm stops at step k. At step i: - 1, maxij Fij
<
2 Th-1, then by
3
Corollary 3 we have maxij of < 3 34 4 At step k. maxi Zij 3 Tk. then by
21

---

Corollary 2 we have maxij oij > Applying union bound on & steps, with probability at least 1 1/n have Tk < max4, di < 4rk, the Lemma follows.
Finally, in Algorithm 2 we postprocess the output of Algorithm to obtain an accurate estimate of max, dg and hence, smooth sensitivity (G),
Lemma 19. (Lemma With probability at least 1 in Algorithm 2 maxiy Zij IW'Il E (1 -0, -8,1 0) maxij azz.
Proof. We split all pairs ij into 2 sets {i' az < ) and the remaining pairs {8} that a > We will prove that the Algorithm will not output zyjr for any i'j'.
1)
For every j'j' such that dg < by Lemma 16 set À = 1, = _ since 2 1202 or c(A-1) 126 3, have max Fry [W
20
3 with probability at least 1/n=-2
Because max;j dij Tk 3T, by Lemma 17 set À = 3, X 2 since 2 2 cd > 3, have
maxij Fij || 3 with probability at least 1/n
Then with probability at least 1 1/2n" Algorithm
2 will not output any z
The remaining sets {i}} that a² By Lemma 15 vij
2ng ||II|
E (1 0, 1 0) Applying
47
the union bound on all pair ij and setting 2 log, (1/(26) + 2, the Lemma follows.
Theorem 5. (Theorem (G))
Sa,)(G) output by Algorithm is (7,5)) approxmiation to
Proof. From the result of Lemma 19 we have:
WIll
(1 0) max oi I max
(1 0) max di 1j
Multipling all terms by 1/(1 0). we have:
W
1 0
max a < maxx Fzy
S
max ij
s(1 0)
1 0
4)
1 A
max of <a² <
max dij
i)
ij
+
max aij <ā -
max a.j
0
max dij Sā <
27 max Oij
max dij Sa S e max Aij-
if
Therefore with probability at least 1 5, we have ( < LS (1) (G) S LL (G) and hence:
(G)
(C) < (G) s e (G,)
with probability at least 1- It follows that $A,0 (G) is (7, 8) upper approximation to (G)
Theorem 6. (Theorem
2 Suppose maxij dij > 0. Algorithm 2 has runtime of
log,, (26)
WIl log
22
maxiy 22
+ m +
n
22

---

Proof. Let m denote the number of edges in G. Then, computing W and |[W|| takes ((m) time and each sampling step requires (log m) time. However, we can perform the calculation of W and ||W|| once and reuse them for all Algorithms 44 1 and 2 Fach sampling step in Algorithm 4 takes Ollog m) time and there are iterations which results in the total cost of (sllog m).
Algorithm I has a run-time of (s's m)) where s' = Il ())))) as it executes Algorithm 4 with varying s s' and k is the number of search steps. Since at the end of the search Tk > max4, ařj/4 w.h.p., we know that k = (log max.; ). In the first step, we start
An²
with TO = n² and reduce The by a factor of 3/4 after each step. The total running time will be O(I]W]] log m x clog" x 2/2 (1 + (3/4) +... (3/4) =)= = (
[IW [|ze log log 82 maxi; 02
Finally, Algorithm 2 has a run-time of O log,, [2]]
log log
+ 772 + log + n
taking into
2
maxiy ol
account the time required to compute W (O(m)) and (G))(G) (O(log (n)/3 + n)) and substituting the values of and 9 as described the Algorithm.
D Details from Section
As mentioned earlier, Karwa al. [23 introduce the notion of local sensitivity of local sensitivity for private counting of k-cliques. In this work, we generalize this notion to multi-level local sensitivity. Recall that J(G, S) denotes the number of embeddings of fixed subgraph H in G that contains all pairs in S and f (G) max f(G, S). The following lemma is at the core of our approach as it relates local sensitivity to subgraph counting.
Lemma 20. For all l: 2 0 we have LS()(K)) < (G).
Proof. When = 0 we have LS()(0)) = LS(f) = ma - f(GG - (t,5)) = (ax)e. f(G, = (G)
When &: 2 1, we have (M) = (ax( that for each (i,j] E I., we have (0) - (i.5)) ( ((+1) and the statement follows. We have two cases.
- ((M (i, We argue below
Case 1. (i,j) & G: let S C L. |8| = k be subset such that f()) (G ( (i.j)) = f
Let T C L, [T] k be subset such that f(k T). By definition of T, we have S) < f(G T).. We have two sub-cases, depending on whether [i.j} & o {t.}} E S. First,
suppose [i.j] & S. This implies f(G (i.j), f(G, + f(G, (i,j)). and
(((())) - (G)) =
< (( ( 5 ) (G).
Next, suppose {i. E S. Then, f(C.)) ((.) 2f (i, (i, j), from the definition
of S. Since f(, T) is monotone with respect to the set of edges in the graph, we have f(G U
(i.j), 2 f(G, T), which implies f(G, 2 f(G. T). Combined with the earlier observation that
I(G,T) 2 S), we have /G, ((G This implies
|5 (GUii.))
= -ICGU..
(
Thus, when (1, & G. in either sub-case, we have
+(+t)))
Case 2. (i.5) E G: we have ( (i) (()()))) where G G (i.j). Repeating the argument in case for the graph G¹, we have (G) (i,j) ((h (G') S { f(k+t)(G))
-( (i,)) ( f() (..--iiji (i.j))
S
(G).
Lemma 21. (Lemma 4.4 of (23) Let B be an (E1, )-diferrentiall private algorithm such that
Pr[B(x)= 2 LS)(z)) > 1 - 82 for all x. Consider the algorithm A that runs B(x) obtain
23

---

an estimate LS of the local sensitivity and release both LS and a noisy estimate f: A(z) f(x) Lap( Lap(LS/ea)), where LS = B(x), and where Lap X) is a Laplace random variable with mean 0 and scale parameter X. Then A is (El + e2, ò1 + t 82)
Algorithm 5 Estimating higher-order private local sensitivity. Input: G, c, 6, subgraph H with & edges
Output: Private estimate /0)) for f(G)
1: Let km = f
2: for k == kim down do
3: g (G) (G) + g (k+ (G++)(() ln1 + (G)((
4: end for
5: return (G)
We now give the proof of correctness for Algorithm using Theorem
3
Proof of Theorem
(G) computed by Algorithm Proof. We prove by induction on k 2 that g (Phm (G)
5 is ((k 1)e2, 82 + (k: + (2)e= private estimate, and Pr(g (Kmm (G) 2 (
82.
The base case is k 1. Note that for kn. f, ((mm) S 1, since once l edges are fixed, either get a fixed subgraph, or it doesn't result in an embedding. Since LS( S f(kim), it follows that (Kmm (k)m)) is (e2, D)-DP estimate. Further, (r[g(km-1
[kmm Pr[Lap(f(km) /eal <
-f(hm) l [2] < 82, which proves the base case.
Next, consider k > 1. From Lemma 20 LS(J(Am-k)) < (kmm+++1) Since (l (ke2, 82 + 6 estimate, and Pr[g (km - k+1) > f(hm -kt1j] > 1 1- 82 (by induction), it follows from Lemma 21 that gllm -k) is an (Riez + e2, d2 + ke + = estimate. Also,
k+1) is an
(f)g((m-))) > (k [T] Pr[[.apgg(H.. (ktm))))/ > - -g(mm -k+1) In 1/82/e2] > 1 - 62, and the
inductive step follows.
L
Finally, we analyze the running time of Algorithm | Jusing Lemma
Proof of Lemma 6
Proof. Observe that S(G, S) can be computed in time (t--(()))), so that (k) can be estimated in time ((n2))). Therefore, the total running time for Algorithm 5 2
Improved time for paths of length &. We show that for paths with & edges, the running time can be actually improved from O(n2( to Onf*+), by keeping track of slightly more complicated information. For a subset S C L of pairs of nodes, let h(S)) denote the set of unique nodes in S. Let be function, such that for each u h(S), (u) specifies the position node has in the embedding of the path. Let f(G, S, the number of paths containing the edges in S, but with the additional constraint that the ordering with respect to π be satisfied. Then, we have (k)) (G) max (G, S,
Proof. (Sketch) Observe that fGG S, T) be computed in time 0(n(+111((9)) time, since this involves considering the nodes in the remaining positions of the path, other than those specified by
и. Further, (() (G) can be computed in (nf(+) time, since we can first guess the set h(S)) and the ordering π (instead of directly guessing |S| pairs of nodes), and then guess the remaining nodes. O
Theorem 7. Let B be an 61). private algorithm such that Pr(B(z) 2 LS(f. x)) >
1- 8g for all x. Let f(x) E [[]- LS(f.z) for all x. Consider the algorithm A that runs B(x) releases: A(x) = (T.S, f(x) + Tap( (.S)( where L.S = B(x), and where Lap(A) is a Laplace random variable with mean 0 and scale parameter X. Then A is (Ei + (3 E3)E2, (81 + 62) + DDP
be an approximation to f(x), with es small
enough that (xf(x)
24

---

Proof. The proof is modification of Lemma 4.4 of (23)). Define the following events
A(x) = (LS(J,)) = B(x), + Lap xa((
A(y) (LS(f.)) = Bly). + Lap Lap(La(f.))/eeee.mlll
Amiz (LS().)) = B(x), Lap(L[((,z)/ee))
Let Pa, Py and Pmiz correspond the distributions of these events.
We first compare (S) and P (S) for any subset S. Observe that (mie(S) Pr(6(z)SS] Since Po(S) Pr(B(y)
B is (EI, (E1, dDP we have Pr(B(v) E S] S eth Pr(B(z) E S] + ò1, which implies (S()) I e Pmin + 61.
Next, we compare Pmiz (S) and (S) for any subset S. Let F' denote the event B(x) LS({,))
LS( Then, Pense (S]F) Pr|Lap(s/aa)ES- f(y)
(S) Pr Po 2 exp(- - e2), where LS(S,)).
2
We have that the fraction
max[l(1+ cz)f(() (1 (1- (11-)))(( (1--))))
max[l(1 ca))f() f(x)) (1- (1-)))) ((v)x))))))))>))))((())))))))))) + (c)(
(1 + fa) + (cg/(a))
with probability - -
2
W 3 + C3, with probability 1 1- --11.
where the second inequality holds because [f(x)) - f(y)] S LS(J,)) S LS(J,z), with probability 1 - -1.
This implies P)(SIF)
(S 2 e (3+raae with probability 1 - 61. Equivalently, Pmize (S|FF S c(3+ss)ez (S(FF) + 81. Therefore, Pmiz (S) = Pmnin(S (S A F) + Pmir (S A F) S (x
61 + 62. Putting everything together, (S) S e Pmix (S) + 61 S +3++(3+))) P: (2)) +
82) d2-
E Estimating higher-order local sensitivity for path counts
Let H denote paths of length &. We assume the graph G has degeneracy d and treewidth t. We show that (G) = max (G, can be computed in time (ppoly(m) under these assumptions on G (i.e., in time smaller than O(n²))..
D). Let a denote a degeneracy ordering of the nodes in V. So node v has index (v). Let (v) = (v' : v' E N(v), (v') a(v) be the set of neighbors of e with index larger than a (v); by definition of degeneracy, it follows that [No(v)] < d for all v. Let v, be two nodes such that (v)) < ou)). Then, dist(v, u, o. K) denotes the length of the shortest path from e to u in a graph K, when restricted to nodes v' with o(v) o(v') < (u).
Let G(E) denote the graph induced by EU É. Let (o k. E) = {u dist(v, u, a, G(É) < k} be the set of nodes within k-hops of in the graph G(E), restricted to higher index nodes than v. Let (u', v')
(o, k, É) denote the graph induced by the subset No (v. k, É) of nodes. We say pair an internal anchor pair in Gv, k. É), if u',o' E No (U, k. E), and (u',e") & E(G, (v. k. E)) (i.e., (u', e²) is newly added edge); else, we say (u', u') is an external anchor pair with respect to (v, kt É). We will add internal anchor pairs sequentially. Let be the edge added in the ith step. and let F()) ee).
k-compact subgraph. We define (H, D) to be k-compact subgraph if
11 =Go(U, k. F(0) for some node e and subset F0) { }i}
* . <<h. k
25

---

F1
71
5 T5
r33
T3
r'3
Figure 6: (Left) D = (r1, T3, r3, edges (f1,r(), (r2,72), (r3, r'a) and (r4, r1) are external anchor edges, while (rs, r5)) is an internal anchor edge. Nodes 8 and t are the starting and ending nodes of the path; (Middle) D = {ri, T3) and (r1,r)), (r2,12), (r3, r')) are external anchor edges, while (rs. r5) is an internal anchor edge. Node s is the starting node of the path, and the path ends at some other node, not in this compact subgraph; (Right) D {r1. F2, F3, ra edges (71 r1)) (r2, r2), (r', r'4) and (Tı, r1) are external anchor edges, while (rs, r')) and (re. 76) are internal anchor edges. Paths pass through this compact subgraph, without starting ending in it.
The pair (ui v1) is internal anchor pair in Go k, 0). For each j 2.....e the pair ej = (uj, my) is an internal anchor pair in the graph Go(u, k. FÚ-1) (ei,-..,eg_1))
* D is a subset of vertices in H, and is referred to as the set of connectors.
Lemma 22. Let (H, D) be k-compact subgraph. Then H has O(kd") nodes and edges. and the tuple (H, D) can be described using Ok22d log d) bits.
Proof. (Sketch) We prove by induction on that Go k, F(i) has at most (i ( 1)d nodes and edges.
First observe that (v, k, 0) has at most d nodes and edges, since that all have index more than (v). We have = as the base case. Let (ui) < (vi).. Then Gr k. {ei)) will have at most 2dt more nodes, with at most d additional reachable nodes through e1- In the inductive step, G, (v, k, F(() = (e.,....,e;) has at most d nodes (through V/ assuming (u,) < o(v))) in addition to those in Gv ki p(i-1)..
The neighborhood of each node u e No k. F()) can be represented in l(dlot( bits. Therefore, the total number of bits needed to specify H is O(ka" d log(kd")) Okaak+ (kd )). D consists of at most & nodes from No (u, k, F()); therefore, D can be specified in O(k log kdd)) bits. Therefore, (H, D) can be specified in O(kak+1 log(kd*)) bits, which implies the number of distinct (H, D) pairs is at most exp(kd )og(k:d)))
Pairing of connector set. The connector set D {ri...., Te). .T,)) with e < k, represents nodes which have incident edges outside the compact subgraph H. We might have to consider three kinds of paths, corresponding to Figure
1. As in Figure 6 (Left), these start at node s in H, then pass through multiple anchor edges, and end at a node H. We partition D into two singletons and multiple pairs (D) ((+((1),,
(x(3)). (T.())). This corresponds to paths which leave H at node (1) and finally return at node Tn(e), with disjoint segments from (n(25)) to (x(2)+11 lying within H, for each j. We refer to the of such pairings as II2(D).
2. This corresponds to paths which start at a node 8 in H. then pass through multiple anchor edges, and don't return to node in H eventually (as in Fig- ure 6 (Middle)). We partition D into one singleton and multiple pairs ग (D) {(rx(1)) (F+(2), (s))))..., (F+(e-1), ("+t)). (.(e))) We refer to the of such pairings as 11, (D).
3. This corresponds to paths which only pass through nodes in H (as in Figure 6 (Right).. We partition D into multiple pairs To (D) ((*()))TT)))) Ta())..... (F+(e-1) ())))) We refer to the set of such pairings as Io (D).
26

---

Approximate counts corresponding to pairings. Note that for a given compact subgraph (H, D), there can be multiple pairings in [D()), I1 (D),II2(D)) For each such pairing. e.g..
E (T(D) = (((a())Tx(2)) (Ta(e-1), (x()) we can guess a set of tuples of numbers Num(n n, E) - {((Num(rr ( (x(252)), = 0.....))) where
( corresponds to the number of segments from (2)-))1) to (*(2)+2)) which are within H, and use some edges from E as internal anchor edges
The path segments counted in disjoint. In particular, this means that the internal anchor edges used in these counts are disjoint.
and those in
Num(r+(23+1)) "1)) (x())++))
The paths within a tuple ((Num(T=(25t))) (x()+))))))))))))))) = 0, 1..)..) contain all the internal anchor edges in E.
In order to reduce the information complexity, we only keep track of (x approximately as powers of (1 + p) for small E (0, 1); denote these ap- proximate counts (u (Num(Fa(t)) Tx(2)),.... "xr))))..,,,u(((((((e 1), (x))))). Num(T, E) denotes the set of approximate path counts which use the internal anchor edges F.. Similarly, approximate counts Num(ar, F.) be defined for r E (D) and π E (D). Let (T) = (T) U (D) U (T))
and the corresponding tuple of counts by
Let LA(H) denote the set of internal anchor edges in compact subgraph H. We refer to tuple II(D), Unen(D) Num IA(H)) an augmented compact subgraph with approximate counts.
Feasible solutions as tuple of augmented compact subgraph with approximate counts. We now observe that any feasible solution involving anchoring subset ((r, :r= lI....., of pairs of nodes can be viewed as set of at most & disjoint augmented compact subgraphs with approximate counts.
Lemma 23. Any feasible solution S {(rr)r) corresponds to a set of augmented compact subgraphs with approximate counts (H,,D, (DD,,, Urem(n) Num(TT,A(HH, (A(H:))), (He, De, Ii()))) Uzem(D) Num(T, IA(H))).
L,...,s). with |S| S k
for some E < k, such that for every j. (Hz, D)) consists of nodes with lower index than those in (Hy Dy) for < jr.
Proof. (Sketch) Consider the set of all paths P which are considered, i.e., those which use the edges from S. Let v be the node with the minimum index among those in P. Consider the graph Go kt 0). If any pair (ie.ja) E S is an internal anchor pair for Go (v, k, 9), define ej = (és. (this is added IA(H))) )); this is again repeated if there is another pair (e' which is an internal anchor pair for Go (t, e1). We stop, when we have subgraph H₁ such that no other pair in S is an internal anchor pair for Hy. If there is a path E P with one end point u E V(H,) and other end point outside H1, u will be added to D1. Finally, we construct pairings and associated approximate counts. a path has a segment p' from 71 Di to r2 E D₁ which is within H1, we would have (r1,72) as part of pairing, and the number of such segments will contribute to the associated counts. Thus compact subgraph (H1, D,, Uxemp))) Num(r: æ, TA(Hi))) can be constructed corresponding to the set P.
Next, consider the path segments we get once we delete all the segments in Hi. The next compact subgraph is constructed in similar manner.
Let S(G, a, k) denote the set of possible augmented compact subgraphs with approximate counts. From Lemma 23 it follows that any feasible solution is an element of Up S(G a))"
Lemma 24. The number feasible solutions is (eexpkk* g log(kd* (): )))
Proof. (Sketch) We first bound |S(G, a, k)). For each compact subgraph (H, D), the number of pairings [I[DD] is most &*, For each pairing II(D), there are O n possible approximate
27

---

such that for each j. counts. Therefore, |S(G, k)] (erpp(kd**) log(kd")) () log n)* using Lemma 22 The lemma follows since the number of feasible solutions is at most S) a, k))*.
Finding a tuple of disjoint augmented compact subgraphs with approximate counts in G. We now show that we can check in polynomial time if an augmented compact subgraph exists. Thus in time ([SS(G, o, k)) [poly(n), we can check which augmented compact subgraphs exist. For a given augmented compact subgraph, the total number of paths can be approximated, which allows us to find the one with the maximum number.
Lemma 25. Suppose we are given tuple MIs...,M,, Me, where (H Dj. D),D) (uum()) E H( for some S such that for every j. (H,, D2) consists of nodes with lower index than those in (Hz,Dz) for j < It is possible to find a set of nodes vi...., ue, sequence of ,..,,.... F(t),, connector sets Diy...,DD Dr, pairings IIDD).....,II H2 = =GG(Vy k. F()),, Dj c (V k, FL.)), and (x) Num(T, [A(H)) {Num(T)) x E I(D,)} in time O(poly(n))ay) (er(())))p((( d t log(kd")) ))) (kg nt)² (') ) if G has degeneracy and treewidth t.
edges Fr(1,, ,...,
Proof. (Sketch) We use ej denote color corresponding to My. For each node v, it is pos- sible to decide in time O(kd*) if can be colored by Cj. i... if there exist F(), Dj such that (G,(V, F()), Dj, 22,Unent UmET(D))) Num(Tr, TA(H)))) = Mj. If v has color cj. it has "conflicts" with C(u, ex) V(G, (u.KA k. FU))), i.e., we cannot have a node u E C(v, eς)) assigned color e. Our goal is to find nodes ....... Ee If G has treewidth 6, we can determine if such coloring can be done in time (ppoly(n) (n) )") time. The main idea for the dynamic program is the following.
such that Uj can be assigned color cj. and vy & C(e,, oj) for any j' # j.
Let T = (V.8) E) denote a tree decomposition of G. Each "node" U E V a subset of V. We construct an information set I(U) for each U E V, which will allow us to determine possible colors for each node v E U, in the following manner. I(U) consists of a set of possible colorings x of U. We consider only x which correspond to colorings in which each color appears at most once; x can be viewed as a coloring of the subgraph induced by all the nodes in the subtree of TT rooted at U. A coloring x specifies for each node u E U, and for each j. an indication of the following: (1) node is colored by cj. (2) node is not colored by cj. but color ej that can be assigned to it, (3) node is not colored by Cj. and, moreover, Cj cannot be assigned to u. This is because there exists some other node u' such that E C(u', C(). We don't keep track of node u' (otherwise we would end up needing n information), but instead specify the set F and position of u in the compact graph Go(u', k. F). The information set I(T) consists of all possible such colorings x; note that [(U) = yt.
We construct the information sets of all U E V in bottom-up manner. Suppose U has children U.. U2 E V. We construct I(U) from (U,) and I(U),, as described below. For each x' e I(U1), x" 7(U2), we construct a coloring x, if feasible, in the following manner. For each node u E U, and for each j:
1. If auc E U1 n U2, x is infeasible if the indicators for u in x' and x" are inconsistent
2. If u is contained only in U1, the indicator for u in x is kept to be the same as that in x': similarly if u is contained only in U2
3. If au of U1 U2, we check if (u) UU)) # 0. In this case, we choose an indicator for u in x that is consistent with the indicators for its neighbors in x' and x". It is also possible that we have inconsistencies, and in that case, x will not be feasible. If node E (N) nn, U2 is in the conflict set of some node with color cj. using the position of uy in the associated compact subgraph, we can determine if would also have a conflict, and so, at what position. Similarly, if there exists node U2 E N(u) n Uz. If there simultaneously exist #1 E Nu)) nú, U2 Nuu) n U2, both of which are conffict sets with respect to Cj. which induce inconsistent conflicts for node with respect to Cj. we would consider infeasible; if the conflicts induced by u1, U2 are consistent, we could keep that indication for node with respect to cj.
28

---

Once the information sets IU)) for all U E V are known, we can find a valid coloring in top-down manner.
given tuple M1,...; Mg, where = (H Dj. [())), ) Num x) I)) for some & I k such that for every j. (Hj. D2) consists of nodes with lower index than those in (Hy. for j
Lemma 26. Suppose
is possible to determine in O(k)) time if the M, 's are consistent, Le., if is possible find external anchor edges that consistent for the tuples.
Theorem 8. If G has degeneracy d and treewidth t, we can get a O(1 + 1/polylog(n)) factor upper bound on (G) in time (ppoly(n) (erppp d=+1 log(kd") ()((k)))) log n) (k.
F Additional Experiments
In this section, we present the complete set of experimental results for private triangle counting (Algorithm 2
on all the tested networks (12 networks given Table
0.3
0.2
0.1
Phivte Inangle Court Re! Ente
cu- HopTH
com Amazon
com CELP
omail Ereon
0.4
0.2
0.14
0.0-
loc- Coz-Bingtkiie
co-Gonall
Cregan-1
Oragon-2
0.14
0.3
0.2
epsilon
Approximation
Exoct
Figure Triangle Count Relative Error, showing the accuracy of the private triangle count with noise calibrated by (1) approximate smooth sensitivity (Algorithm) 2}, and (2) exact smooth sensitivity.
The ratlo of Smooch Sensibvity #4
0.01
0.00
ca-lepPh
Ioo-iingtklle
Oregon-10.
Dregin-____
Network
Figure The ratio of the smooth sensitivity over the actual count of triangles for all networks.
29

---

CondMAa
1000
100
10
Co-HopThh
com-Anazon
en orral-Erron
Speeduu
loo-Brighhkle
loo-Gowall
Oragon-1 G
Oregon-2_G.
1000
0.250
2.008:155
0.500
1.000
2,000,112 125
0.500
1.000
2.008 75
0.250
0.500
1.000
2.000
apailon
Figure 9: Speedup of Algorithm
2 (compared to the exact calculation) all networks.
ca-HepPhh
1.5
1.0
0.0
ca HeoTh
Doth: Amszzon
com-D6LP
emall Emron
2.0
Sensitiitty Approx.
1.0
0.5
loo-Gowall
Dregon-1_G.
Oregon-_GG.
2.0
1.5
0.5
0.0
epsilon
Enar
Figure 10: Sensitivity Approx. Error, showing the error of approximate smooth sensitivity output by Algorithm (relative to the exact smooth sensitivity) on all networks.
Figure showws that when approximate smooth sensitivity is used instead exact smooth sensitivity, the accuracy of the private triangle counts measured using the metric, Triangle Count Relative Error, are the same across different privacy budgets in all but two networks (Oregon and Oregon 2) (Figure 8). In these two networks, the smooth sensitivities are relatively large in comparison with the triangle counts, making the noise fluctuate much more for the approximate estimate. For the ca-HepPH dataset, the two outputs coincide.
30

---

Figure 8) shows the ratio of smooth sensitivity to actual triangle count for all datasets. Note that this ratio is large for the two datasets, Oregon and but small for all the other datasets.
Figure 9 shows the speed-up achieved using Algorithm 2 As seen in the figure, it is orders of magnitude faster than the exact algorithm on all the 12 datasets. In fact, large graphs (Amazon, DBLP, Gowalla), the speedup is as high as 1, 000-fold. Generally, a lower requires a smaller approximation factor (7), which in turn requires larger number of iterations reduce the error in approximation. To summarize, the majority of tested networks have speedup factors between 10 and 100-fold across all privacy budgets c.
Figure [0]shows that all approximate smooth sensitivities computed by Algorithm 2 are close to the exact smooth sensitivities. We measure this using the metric, Sensitivity Approx. Error. Approximate smooth sensitivities are always larger than the true smooth sensitivity. It is necessary since lower value may expose the privacy due inadequate noise magnitude. In general, smaller value of e (higher privacy guarantee) requires a more accurate estimation of the sensitivity. is illustrated in Figure I0 as the approximate smooth sensitivity is close the exact smooth sensitivity in all networks at e 0.125 or e = 0.25.
31


Reviews:
[{"review_id": "mfhBWJoIMh", "reviewer": "Reviewer_tb5J", "summary": "This paper provides an algorithm to approximately estimate the smooth sensitivity for counting triangles in a graph, while preserving edge-level differential privacy. Compared with the existing solution for smooth sensitivity, the proposed algorithm demonstrates efficiency improvement in terms of computation. \n", "questions": "See weaknesses.", "limitations": "Yes.", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Efficiently computing/estimating the smooth sensitivity for subgraph counting is a well-motivated problem. \n\n2. The idea of the proposed algorithm is intuitive and the analysis seem to be sound.", "weaknesses": "1. It would be better if the authors can provide a table comparing their method with existing solutions. The comparison should include time complexities, tasks (e.g., triangle counting, clique counting), sample complexities, and maybe utility guarantees. \n\n2. The original non-private and approximate algorithm for triangle counting (the diamond sampling [2]) and also the state-of-the-art solution(s) for approximate triangle counting without DP should be included for theoretical analysis and empirical evaluation. Including them would help the readers better understand the trade-offs between privacy and utility and between utility and efficiency.\n\n3. Some baselines are missing in the empirical evaluation. For example, the inverse sensitivity, propose-test-release, and ladder functions.\n\n4. The algorithms in Section 5 do not have empirical evaluations.\n\n5. A more detailed discussion on the parallelism is needed. How much does parallelism account for the efficiency improvement of the proposed solution?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "W1.It would be better if the authors can provide a table comparing their method with existing solutions. The comparison should include time complexities, tasks (e.g., triangle counting, clique counting), sample complexities, and maybe utility guarantees.\n\n*Response:* Thanks for the suggestion. \nWe will add such a table which will compare the time complexities for different subgraphs, such as triangles, $k$-stars and $k$-cliques, summarizing the references mentioned in our related work, and the recent survey of (Li et al., ACM Computing Surveys, 2023).\nWe note that only the time complexity is mentioned in these papers, e.g., for triangle counting, our result in Theorem 2 is smaller than $O(m\\cdot polylog(m))$, compared to $O(m\\max_v d(v))$.\nTherefore, we will focus on the time complexity in the table.\n\n    \nW2. The original non-private and approximate algorithm for triangle counting (the diamond sampling [2]) and also the state-of-the-art solution(s) for approximate triangle counting without DP should be included for theoretical analysis and empirical evaluation. Including them would help the readers better understand the trade-offs between privacy and utility and between utility and efficiency.\n\n*Response:*\nOur results in Section 6 show the error with respect to the $True Count_{\\Delta}$---please see the metric {\\em Triangle Count Relative Error} $=\\frac{|Private Count_{\\Delta} - True Count_{\\Delta}|}{True Count_{\\Delta}}$ and Figure 3 in Section 6.\nWe will also show the error with respect to diamond sampling in the final version, as suggested.\nWe note that since the diamond sampling paper would also incur some error due to sampling, it is quite likely that the Triangle Count Relative Error would reduce if we compare with the diamond sampling result, instead of $True Count_{\\Delta}$.\n\n\nW3. Some baselines are missing in the empirical evaluation. For example, the inverse sensitivity, propose-test-release, and ladder functions.\n\n*Response.*\nOf the methods mentioned here, a result for triangle counting is known only using ladder functions (Zhang et al., 2015).\nWe will add this method to the empirical evaluation section in the final paper.\n\nW4. The algorithms in Section 5 do not have empirical evaluations.\n\n*Response.*\nThe algorithms in Section 5 are quite involved, and we present this more from a theoretical perspective.  They demonstrate the power of using multi-level local sensitivity when combined with approximate queries. These are the first such results.\nWe expect more efficient algorithms in future work.\nWe note that for most subgraph counting problems, the best theoretical bounds are much worse, and no practical evaluations are known for them.\nFor instance, a simple implementation of the smooth sensitivity result of Nissim et al. for counting subgraphs could take $O(n^{\\log{n}})$ time, but they show a better bound of $O(m\\max_v d(v))$ for triangles; similarly, the ladder function technique of (Zhang et al., 2015) is potentially relevant for any subgraphs (if suitable ladder functions can be constructed), but they give practical algorithms only for $k$-stars and $k$-cliques.\n\nW5. A more detailed discussion on the parallelism is needed. How much does parallelism account for the efficiency improvement of the proposed solution?\n\n*Response.* As in the diamond sampling paper, our method can be easily parallelized. In short, the heaviest computing task is in Algorithm 4 (i.e., estimate $a_{ij}^2$) with high accuracy (i.e, with a large number of iterations s). Lines 5-10 of that algorithm can be easily parallelized to sample s values concurrently with a very slim chance of occuring race conditions.\nWe will elaborate on this in the final version.\n"}, {"review_id": "tXS1iD7e2p", "reviewer": "Reviewer_hrky", "summary": "This paper extends the study of local sensitivity and smooth sensitivity for the problem of subgraph counting. Previous work has identified local sensitivity and its derivates like smooth sensitivity as a tool to calibrate noise to the given input instead of global sensitivity. However, this comes with two challenges: it is often not easy to get a good bound on local sensitivity in a computationally efficient way, and local sensitivity itself can exploit privacy (which lead to the notion of smoothed sensitivity, a DP version of local sensitivity). In this submission, the authors study how an approximation of the smooth sensitivity and higher-order local sensitivity can be used privately to release an approximation of subgraphs counts, in particular triangles, paths and arbitrary constant-size graphs.\n\nFor triangle count, they show that one can release an approximation in $O(polylog(m+n))$ time plus the time needed to approximate the triangle count non-privately, by leveraging a fast estimation scheme for the smooth sensitivity and a diamond sampling technique from non-private algorithms. For general graphs, they extend the existing first and second order analysis of local sensitiviy for triangles and cliques to the $\\ell$th order for graphs $H$ with $\\ell$ edges. They derive that one can compute an approximation of the $\\ell$th order local sensitivity and use it to release the count of copies of $H$ in the input graph in $O(n^{2\\ell})$ time for arbitrary $G$ and in time $O(n^{\\ell+1})$ if $H$ is tree. In an experiment section, they show that for several datasets of size xxK to xxxK nodes, their DP approximation algorithm for counting triangles provides one to three order of magnitude speedup, while the approximation is significantly less than a magnitude worse compared to the baseline based on exact smooth sensitivity.\n\nOverall, this paper is a nice step into a directon that I think is promising to overcome the issue with global sensitivity on graphs. The theoretical bounds on running time are not practical, but they generalize from specific instances or classes of graphs to arbitrary graphs. This is often a first step into understanding a problem better. The experiments show that the approach can also improve the state of the art where the problem is already better understood in general, i.e., in the case of triangles.", "questions": "-", "limitations": "-", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper provides general utility bounds for counting arbitrary subgraphs that are much more tailored to the actual input than approaches based on global sensitivity.\n* The experiments indicate that algorithms also performs better in practice.", "weaknesses": "* The bound for general graphs and paths is impractical, as the degree of the running time polynomial scales linearly with the size of $H$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "W1. The bound for general graphs and paths is impractical, as the degree of the running time polynomial scales linearly with the size of $H$.\n\n*Response.* We completely agree with the reviewer's assessment about the practicality of the result for general subgraphs $H$.\nHowever, we note that from a theoretical perspective, this is still significantly better than previous results.\nFor instance, a simple implementation of the smooth sensitivity result of (Nissim et al., 2007) and (Karwa et al., 2014) for counting subgraphs could take $O(n^{\\log{n}})$ time for constant size subgraphs $H$, in the worst case, and they show efficient results only for two classes of subgraphs.\nSimilarly, the technique of (Zhang et al., 2015), is potentially relevant for any subgraphs, but no efficient algorithms are presented for general subgraphs. \n\nTherefore, our results for general graphs and paths are more from a theoretical perspective. \nThey demonstrate the power of using multi-level local sensitivity when combined with approximate queries and these are the first such results.\n\n"}, {"review_id": "Lcg428MtUf", "reviewer": "Reviewer_Bhh2", "summary": "The paper focuses on the problem of counting the number of non-induced embeddings of a subgraph while ensuring differential privacy. The objective is to develop efficient DP algorithms for subgraph counting that outperform previous approaches in terms of running time.\n\nTo accomplish this goal, the authors give a method that leverages approximate smooth sensitivity as a substitute for global sensitivity in privacy mechanisms. This approach proves effective in accurately estimating smooth sensitivity for tasks such as triangle counting and path counting.\n\nIn addition, the paper presents experimental results for triangle counting using real-world data. These experiments demonstrate that the algorithm's estimation outcomes closely align with the accurate values.", "questions": "For the DP algorithms given in the paper, the output A(D) is an approximation of the quantity that we want to compute (e.g., the number of triangles). But the approximation ratio of A(D) is never mentioned, i.e. what is the multiplicative error and what is the additive error? Furthermore, how could you compare these algorithms to previous algorithms in terms of approximation ratios?\n\nWhat is the state-of-the-art of running times of the DP algorithms for counting subgraphs with ell edges? \n\nWhy the experiments are only for triangles? What about paths or other subgraphs?", "limitations": "See \"Weaknesses\".", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem of counting the number of subgraphs is an important question in the graph differential privacy community. \n\nThe idea of using approximate smooth sensitivity to improve the running times of current algorithms is somehow natural and interesting. \n", "weaknesses": "The running time of the DP algorithm for (arbitrary) subgraphs with $\\ell$ edges is $O(n^{2\\ell})$, which is still quite inefficient. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "W1. The running time of the DP algorithm for (arbitrary) subgraphs with edges is $O(n^{2l})$, which is still quite inefficient.\n\n*Response.* We completely agree with the reviewer's assessment about the practicality of the result for general subgraphs $H$.\nHowever, we note that from a theoretical perspective, this is still significantly better than previous results.\nPlease see the response to W1 from Reviewer hrky for all the details.\n\nQ1. For the DP algorithms given in the paper, the output A(D) is an approximation of the quantity that we want to compute (e.g., the number of triangles). But the approximation ratio of A(D) is never mentioned, i.e. what is the multiplicative error and what is the additive error? Furthermore, how could you compare these algorithms to previous algorithms in terms of approximation ratios?\n\n*Response*. Thanks for the question.\nWe will elaborate on this in the paper.\nFor the triangle counting problem, the approximation $A(D)$ is obtained from the diamond sampling result of (Ballard et al., 2015), and their error terms are specified in Lemma 3 and Theorem 4 of their paper (these depend on on the \\#samples).\nTheorem 2 in our paper gives the precise approximation ratio for triangle counting---this includes both the multiplicative and additive factors. \nWe will discuss this better, to contrast the error terms from those in (Ballard et al., 2015).\nIn our experiments, we show the exact error.\nWe will also add a comparison to the diamond sampling method, as also mentioned in W2 by Reviewer tb5j.\nWe will consider the Triangle Count Relative Error and the time complexity in our comparison.\nFurther, as mentioned in the response to W3 of reviewer tb5j, we will also add a comparison with the ladder function based method of Zhang et al., 2015.\n\n\nQ2.What is the state-of-the-art of running times of the DP algorithms for counting subgraphs with ell edges?\n\n*Response*. As mentioned in the response to W1 from Reviewer hrky,\nprecise bounds have been considered for very few subgraph problems. \nIn particular, for $k$-stars, the best running time is $O(m\\log{n})$, and the best running time for $k$-triangles is $O(m\\max_v d(v))$.\nFor general subgraphs, prior papers do specify any efficient algorithms, and direct implementations of the smooth sensitivity technique would take $O(n^{\\log{n}})$ time. \nWe will elaborate on this in the Related Work section of the final version.\n\n\n\nQ3.Why the experiments are only for triangles? What about paths or other subgraphs?\n\n*Response.* The results for paths and general subgraphs are presented from a theoretical perspective and the algorithms are quite involved. The results show how to use multi-level local sensitivity with approximation.\nThey improve on the previous best known results, but are still quite impractical and more efficient algorithms are needed for empirical evaluation, as mentioned in the response to W1 from Reviewer hrky.\nWe will clarify this in the final version.\n"}, {"review_id": "y3asYiX5Rs", "reviewer": "Reviewer_LedL", "summary": "The paper considers the problem of releasing information about graphs (specifically, subgraph counts) under differential privacy.  This has been a widely studied problem, due to the challenging nature of ensuring that the noise added is bounded.  Many techniques (e.g., smooth sensitivity) have been developed within the privacy community motivated by such graph problems.  A particular concern is the computational cost: many techniques have a high polynomial or exponential cost, rendering them impractical -- and more costly than their non-private counterparts.  The present paper studies how approximation can adopted, in two ways: applying approximation to the sensitivity calculations, and to the quantity of interest.  In some ways, it is perhaps not surprising that bounds can be obtained by tolerating approximation, a common technique in randomized algorithms.  Recent work has started to look at the intersection of approximation and privacy (e.g., in the case of quantile computations, https://arxiv.org/abs/2201.03380), so it is natural to apply it here.  Specific results are shown for triangles, paths and trees, as subgraphs of particular interest.    ", "questions": "Lemma 2 seems like it should be obvious: if we have an estimate of the smooth sensitivity that is always bigger except with probability delta', then we should be able to directly use this to add noise based on the estimate, and only incur delta' additional \"failure probability\" in the (eps, delta)-differential privacy bounds.  But the proof in the supplementary material works through a longer argument adapting the original proof of smooth sensitivity.  Can you comment on whether the intuitive argument above is valid. \n\nIn Defn 5, wouldn't it be quicker to say that g_f is A_f(D) clipped to the range [ (1-alpha)f(D), (1+alpha)f(D) ]?  And similarly for s_f.\n\nTheorem 2, the dependence should be on log(1/(2 delta)) ?  ", "limitations": "No limitations around societal impact. \nThe paper could discuss more the limitations of the approach and future work -- Section 7 is very brief on this topic. ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "These are fundamental questions about the effect of privacy -- motivated by practical concerns, but perhaps contributing more to out theoretical understanding of whether we can obtain private counterparts of exact or approximate algorithms for subgraph counting.  The paper opens up the question of using approximation in different ways in the private algorithm design, and focuses attention on the computational cost of the algorithms, whereas prior work has looked primarily at the accuracy. \n\nThe technical details (in full in the supplemental material) is detailed and challenging in places, although making use of standard probability tools (e.g., Chernoff bounds).   ", "weaknesses": "The paper takes great pains to cite recent work by Blocki et al [4] which as far as I can tell is currently an unpublished technical report.  It summarizes the difference as studying approximate sensitivity.  Still, I think it would be useful to provide more contrast.  For instance, the empirical study compares against the original work on smooth sensitivity from 2007.  Many papers relevant to private triangle counting have come since then.  In particular, it would be instructive to also compare against the black-box approach of Blocki et al to see where it falls on these axes. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "W1. The paper takes great pains to cite recent work by Blocki et al [4] which as far as I can tell is currently an unpublished technical report. It summarizes the difference as studying approximate sensitivity. Still, I think it would be useful to provide more contrast. For instance, the empirical study compares against the original work on smooth sensitivity from 2007. Many papers relevant to private triangle counting have come since then. In particular, it would be instructive to also compare against the black-box approach of Blocki et al to see where it falls on these axes.\n\n*Response.* To the best of our knowledge, and as per section 3.2.1.1 of the survey by (Li et al., ACM Computing Surveys, 2023), there are very few recent papers which have considered private subgraph counting problems, or even triangle counting in the edge differential privacy model.\nThe survey by Li et al. mentions two other papers relevant to triangle counting, in addition to the ones we cite in our paper.\nThe first, (Chen et al., SIGMOD 2013) develops a recursive strategy.\nHowever, as noted in the criticism of this work in (Zhang et al., 2015), their methods ``release a lower bound on the result, whose global sensitivity is relatively low. This method suffers from a bias between the\ntrue query answer and the lower bound, in exchange for less noise''.\nThe second paper by (Proserpio et al., 2014) presents a different approach which estimates counts by degree, which can be implemented in time $O((\\max_v deg(v))^3 m)$.\nWe will discuss all these papers, but note that our result improves on all of them.\nThere are some other papers on subgraph counting (including triangle counting) under the node differential privacy model, e.g., (Kasiviswanathan, et al., 2013) and (Ding et al., 2021).\nSimilarly, there are ither works, such as (Imola et al., 2022) on subgraph counting in the shuffle model.\nWe haven't considered a comparison with these results, because the privacy model is different.\n\nQ1. Lemma 2 seems like it should be obvious: if we have an estimate of the smooth sensitivity that is always bigger except with probability delta', then we should be able to directly use this to add noise based on the estimate, and only incur delta' additional \"failure probability\" in the (eps, delta)-differential privacy bounds. But the proof in the supplementary material works through a longer argument adapting the original proof of smooth sensitivity. Can you comment on whether the intuitive argument above is valid.\n\n*Response.* Actually, this argument will fail the Dilation Property (at the end of Lemma 10): $S_{f,\\beta} (D)/S_{f,\\beta} (D')$ will be unbounded.\n Formally, let $\\tilde{S}$ be an approximation of the $\\beta$-smooth sensitivity $S^*$ such that $\\tilde{S}(D) > S^*(D)$ with probability $1 - \\delta$ for any dataset $D$. We can see that the Dilation Property (at the end of Lemma 10) does not go through, since the ratio $\\frac{\\tilde{S}(D)}{\\tilde{S}(D')}$ is unbounded, hence we cannot use $\\tilde{S}$ for noise calibration. \n\nQ2. In Defn 5, wouldn't it be quicker to say that $g_f$ is $A_f(D)$ clipped to the range $[ (1-alpha)f(D), (1+alpha)f(D) ]$? And similarly for $s_f$.\n\n*Response.* Yes, that is correct.\nWe used this notation to keep it consistent with Blocki et al., but will clarify this in the paper.\n\nQ3. Theorem 2, the dependence should be on $\\log(1/(2 \\delta))$ ?\n\n*Response.* Yes. It is a good catch, and we will fix this.\nThe numerator involves a factor of c, which is set to $\\log (1/(2\\delta))$ in Algorithm 2.\n\n\n"}]

Author rebuttal:

Meta-review: This paper studies private subgraph counting using approximation algorithms for the quantity and its sensitivity. The main contribution is a simple (in hindsight) way to use these approximation to release a private approximation. The authors show that this general approach leads to better algorithms for some common problems on graphs.
The paper received detailed reviews and an active discussion phase. The reviewers largely agreed that the paper is above bar for this conference and I am happy to recommend acceptance. I encourage the authors to incorporate all reviewer feedback in the final version of the paper.
Decision: Accept (poster)