Differentially Private Range Subgraph Counting

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Differentially Private Range Subgraph Counting

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cryptography, security, privacy, cybersecurity

Differentially Private Range Subgraph Counting

Xian Chen * 1 Ruobing Bai * 1 Pan Peng 1

arXiv:2606.08179v1 [cs.DS] 6 Jun 2026

Abstract

of such occurrences. Subgraph counts serve as key graph statistics: for instance, triangles and k-stars are central to computing the clustering coefficient, which are widely used to evaluate social and recommendation networks, while counting four-cycles is particularly informative for capturing clustering behavior in bipartite graphs such as online dating and mentor-student networks.

Subgraph counting is a fundamental problem in graph analysis. Motivated by practical scenarios where graph analytics are performed on subgraphs induced by selected vertices – rather than on the entire graph – and by growing privacy concerns, we initiate the study of differentially private range subgraph counting (DPRSC). The goal is to privately count occurrences of a fixed pattern graph within induced subgraphs defined by multi-dimensional attribute ranges. Unlike classical point counting, subgraph counting is inherently nonlinear and exhibits high sensitivity: a single edge modification can affect many subgraph occurrences. We present the first efficient algorithms for DPRSC with small additive error. Our approach introduces a subgraph projection that reduces DPRSC to weighted orthogonal range counting, enabling the use of range trees and local sensitivity estimation to achieve accurate private query answering. We complement our algorithms with matching lower bounds, obtained by reducing reconstruction attacks to DPRSC and leveraging discrepancy theory. In particular, we show that any differentially private algorithm for DPRSC must incur additive error exponential in the dimension. Empirical evaluations demonstrate that our algorithms significantly outperform baseline methods in accuracy and runtime while maintaining strong privacy guarantees.

In many applications, beyond counting subgraphs in the entire graph, we are often interested in counting subgraphs within specific induced subgraphs determined by vertex attributes. For instance, in patient or social networks, analysts may wish to count patterns among individuals within certain age ranges or geographic regions. In financial networks, counting transaction patterns among entities with similar risk profiles or locations can help identify fraudulent activities or assess systemic risks. More generally, vertices often carry multidimensional attributes, and practitioners seek to issue repeated subgraph-counting queries restricted to vertices whose attributes fall within specified ranges. Motivated by these scenarios, we introduce the Range Subgraph Counting problem that combines classical subgraph counting with multidimensional range queries over vertex attributes. Definition 1.1 (Range Subgraph Counting (RSC)). Let G = (V, E) be an n-vertex undirected graph, where each vertex v ∈ V is associated with an attribute vector a(v) ∈ Rd . For a query range q = [ℓ1 , r1 ] × · · · × [ℓd , rd ], define Vq = {v ∈ V | ℓi ≤ ai (v) ≤ ri , i ∈ [d]}. Let Gq = G[Vq ] denote the subgraph of G induced by Vq . Let H be a fixed connected pattern graph with O(1) vertices and let Q be a set of query ranges. The goal is to return, for each query q ∈ Q, the number of occurrences of H in Gq .

1. Introduction Subgraph counting is essential for understanding the properties of a data graph and has been extensively studied (Chiba & Nishizeki, 1985; Alon et al., 1995; Björklund et al., 2014; Curticapean et al., 2017; Assadi et al., 2019; Fichtenberger et al., 2020). Given a host graph G = (V, E) and a pattern graph H, a subgraph of G that is isomorphic to H is called an occurrence of H. The goal is to compute the number

Note that vertex attributes may represent age, time or location, depending on the practical context. Additionally, an occurrence is only counted if all its vertices are contained within Vq . Prior work by Deng et al. (2023b) studied the 1dimensional version of this problem, focusing on optimizing the trade-off between space and query time.

* Equal contribution 1 School of Computer Science and Technology, University of Science and Technology of China, Hefei, China. Correspondence to: Pan Peng <[email protected]>.

Differential privacy perspective In this work, we study the range subgraph counting problem from the perspective of differential privacy (DP). DP enables meaningful statistical 1

Differentially Private Range Subgraph Counting

Q satisfies1 |Q| = O min(n2d , 2n ) .

analysis while ensuring that the presence or absence of any single individual’s data has a limited impact on the output (Dwork et al., 2006). We focus on edge DP. Two graphs G and G′ with the same node set V are said to be neighboring, denoted G ∼ G′ , if they differ by exactly one edge. (A stronger notion, known as node DP, has also been studied; see, e.g., (Blocki et al., 2013; Chen & Zhou, 2013; Kasiviswanathan et al., 2013).) Throughout this work, vertex attributes are assumed to be public.

Upper bound We give the first efficient algorithm for differentially private range subgraph counting (DPRSC) that achieves small additive error. Theorem 1.3 (Approximate DPRSC). For any ε > 0 and δ ∈ (0, 1), there exists a (ε, δ)-DP algorithm that, given a graph G = (V, E, a) with d-dimensional vertex attributes, a fixed pattern graph H, and a query set Q, outputs noisy answers feH (Gq ) which satisfy

Definition 1.2 (Edge DP (Nissim et al., 2007)). Let ε > 0 and δ ∈ [0, 1). A randomized algorithm A is (ε, δ)-DP if for all measurable events S in the output space of A and all neighboring graph G ∼ G′ ,

max fH (Gq ) − feH (Gq ) q∈Q ! p f f (G) · (ε + log(1/δ)) log(n|Q|) · log2d n HS H =O ε

Pr[A(G) ∈ S] ≤ eε Pr[A(G′ ) ∈ S] + δ. When δ = 0, we say that A satisfies pure DP (or ε-DP); when 0 < δ < 1, it satisfies approximate DP.

f f denotes the with probability at least 1 − n1 , where HS H output in Algorithm 4. Here, the hidden constants are of the form cO(d) for some universal constant c > 1.

Let fH (G) denote the number of occurrences of H in G. A fundamental property of DP implies that any edge-DP algorithm for subgraph counting must incur additive error proportional to the local sensitivity LSfH (G) with constant probability (Lindell, 2017). Classical DP mechanisms instead depend on the global sensitivity GSfH , which can be significantly larger. Various alternatives to global sensitivity – often via instance-dependent sensitivity bounds – have been proposed, e.g., smooth sensitivity, ladder functions, and private higher-order local sensitivity (Nissim et al., 2007; Zhang et al., 2015; Nguyen et al., 2023). While DP subgraph counting on the entire graph has been studied extensively, private algorithms for range subgraph counting have remained unexplored.

f f (G) can be viewed as an In the above, the quantity HS H approximation of LSfH (G) with an implicit dependence on poly(log(1/δ)/ε) (see (Nguyen et al., 2023)). In realf f (G) is often world graphs, which are typically sparse, HS H significantly smaller than GSfH . For instance, when H is f f (G) = a triangle, if ε and δ are constants, we have HS H LSfH (G) + O(1) ≤ dmax (G) + O(1) ≪ GSfH = n − 2 with constant probability, where dmax (G) represents the maximum degree of graph G (see Sections 3.2 to C.3 for f f (G) and GSf ). Note that the more discussions on HS H H number of triangles in many real-world graphs is significantly larger than n. Consequently, the additive error of our algorithm is substantially smaller than the true triangle count in such graphs.

The challenge in range subgraph counting is twofold. First, subgraph counts already exhibit high sensitivity, even without range restrictions. Second, range queries require answering subgraph counts over many induced subgraphs Gq , leading to increased algorithmic and privacy complexity that depends on the size of the query set Q. A naive approach – privately answering each query independently by adding Laplace noise – results in prohibitive error due to sensitivity scaling with |Vq | and privacy loss accumulating via composition. When |Q| = Θ(n2d ), the resulting error can overwhelm the true signal, even for simple patterns such as triangles. Moreover, range subgraph counting is inherently nonlinear, preventing the direct application of DP techniques developed for linear query workloads.

For pure DP, which provides a stronger privacy guarantee, we also √ obtain a corresponding additive error bound of O(

GSfH ·

log(n|Q|)·log3d n ) (see Theorem 3.3 for details). ε

We also provide the complexity analysis of the above algorithms in Section E.3. In particular, these algorithms run in polynomial time for d = O(log n/ log log n). Furthermore, when each dimension of the attributes takes fewer than n distinct values, our algorithms achieve improved additive error as well as better time and space complexity (see Section G.4 for details). In the special case where all vertices share the same attribute (so that the only non-trivial query corresponds to counting subgraphs in the entire graph G), our bounds are consistent with the results of Nguyen et al. (2023) for DP subgraph counting.

1.1. Our contribution

Note that the VC-dimension of Q is at most 2d. By Sauer’s Lemma, the number of distinct induced subgraphs that Q can gen P n 2d n erate is at most 2d i=0 i = O(min(n , 2 )) (Shalev-Shwartz & Ben-David, 2014).

Before stating our main results, we note that for any algorithm producing consistent outputs on identical induced subgraphs G[Vq ], we may safely assume that the query set 2

Differentially Private Range Subgraph Counting

additive error of Ω(nGSfH ) with constant probability (see Theorem H.16 for details). Since in Theorem 1.4, the exf f (G) is always less ponent of n multiplied in front of HS H than 1, this result provides a stronger lower bound than Theorem 1.4 when d is sufficiently large.

Lower bound We also establish a lower bound for the DPRSC problem as the dimension d varies. Theorem 1.4 (Lower Bound of DPRSC). For any pattern graph H, let A be an (ε, δ)-DP algorithm with constants ε > 0 and δ ∈ [0, 12 ) for the range subgraph counting problem with additive error η = maxq∈Q |fH (Gq ) − feH (Gq )| with a sufficiently large constant success probability. Assume that |Q| ≥ nc for any sufficiently small constant c > 0. Then there exist infinitely many n-vertex graphs G = (V, E, a) with d-dimensional vertex attributes and a corresponding query set Q such that

1.2. Technical overview A natural approach is to reduce range subgraph counting to a DP range point counting problem by embedding vertices into a Euclidean space, and then applying existing DP algorithms for orthogonal range counting (see, e.g., Dwork et al. (2015)). However, unlike point counting, subgraph counting is inherently nonlinear: the sum of occurrences of a pattern graph in two graphs is not necessarily equal to the number of occurrences in their union, and a single edge change can affect many subgraphs (e.g., one edge may participate in Θ(n) triangles), leading to high sensitivity.

f f (G)); • if d = O(1), then η = Ω(logd−1 n · HS H Ω(d) f • if d = O(log n), then η = 2 · HSfH (G); f f (G). • if d = Ω(log n), then η = nΩ(1) · HS H The above theorem follows directly as a corollary of the more general lower bound in Theorem 4.1, which additionally captures the dependence on |Q|. In particular, for the hard instances underlying Theorem 1.4, the quanf f (G) is, with high constant probability, close to tity HS H GSfH . In Section F.4, we further provide a lower bound f f (G)) for the case d = 1, under the additional Ω(log n· HS H assumption that δ = n−Ω(1) .

To address these challenges, we introduce a subgraph projection technique that maps each occurrence of the pattern graph H to a point in R2d based on vertex attributes, converting range subgraph counting into estimating weighted point counts over axis-aligned rectangles. The weight of each point corresponds to the number of occurrences associated with the underlying vertex tuple. A single edge can change the weights of all points projected by the subgraphs it is associated with. We organize these points using a range tree (Bentley & Saxe, 1978; Dwork et al., 2015) and add Laplace noise to node weights, allowing each query to be answered by aggregating a small number of tree nodes. This approach effectively leverages query correlations and substantially reduces noise. Finally, to further improve accuracy, we adapt the local sensitivity estimation technique of Nguyen et al. (2023) and incorporate it into the range tree, yielding smaller additive error.

The above results demonstrate the inevitable exponential dependence of the additive error on the dimension d for range subgraph counting when d = O(log n). In particular, when d is constant, the base of the corresponding exponential dependence is log n, which is consistent with our upper bounds, up to constant factors in the exponent. Experiments We experimentally test our DP algorithms for RSC on real network datasets in Section 5. Other extensions We also explore better upper and lower bounds of DPRSC in higher dimensions d in Section H.

To complement our algorithms, we establish lower bounds on the additive error for differentially private range subgraph counting via a reduction from the reconstruction attacks (RA) problem, inspired by the framework of Muthukrishnan & Nikolov (2012). Given an RA instance x, together with a point set P ⊆ Rd and a query set Q with non-empty common intersection, we construct a Θ(n)-vertex graph G(x) whose private edges encode the entries of x. Any DP algorithm for RSC on (G(x), Q) can then be transformed into a DP algorithm for RA.

We present a simple polynomial-time ε-DP algorithm p with an additive error O(n log(n|Q|)GSfH ) for any d and constant ε based on randomized response (see Theorem H.6). The algorithm achieves better additive error and time complexity than Theorem 1.3 and Theorem 3.3 for d = Ω(log n/ log log n). We further extend an approach in Eden et al. (2023) to obtain an instance-dependent error for any d and H (see Theorem H.7). For example, when H is a triangle and ε is a constant, our algorithm has an additive p 3 error O(log3 (n|Q|)n 2 + log(n|Q|) fC4 (G)), where C4 represents a 4-cycle. For many real-world graphs, the additive error is significantly better than the aforementioned randomized response method.

The lower bound follows from two key ingredients: (i) known lower bounds for DP reconstruction attacks, and (ii) the existence of point sets P and query families Q whose incidence matrices have large discrepancy (Theorem 2.10). Our main technical contribution shows that the discrepancy of a matrix associated with the RSC instance (G(x), Q) is larger by a factor of Θ(GSfH ) (Theorem 4.3). The proof relies on an approximate reduction and a careful classification

Moreover, when d is sufficiently large, we extend the technique in Eliáš et al. (2020) to prove that for any pattern graph H and any (ε, δ)-DP algorithm with constant ε and δ, there exist infinitely many n-vertex graphs that incur an 3

Differentially Private Range Subgraph Counting

of subgraphs according to the number of private edges they contain. Combining this discrepancy bound with standard connections between discrepancy and differential privacy completes the lower bound argument.

on input x ∈ X samples Y1 , . . . , Yk independently from GS Lap( ε f ) and outputs M (x) = f (x) + (Y1 , . . . , Yk ). The Laplace mechanism is ε-DP.

Due to space constraint, we defer the discussion of other related work to Section B.

2.1. Discrepancy and the point-query incidence matrix Definition 2.8. Given a point set P ⊆ Rd and a query set Q defined by m axis-parallel boxes B1 , B2 , . . . , Bm ⊆ Rd , let A ∈ Rm×n be an incidence matrix of the collection of the set {Bj ∩ P, j ∈ [m]} (i.e. a matrix whose rows are the indicator vectors of {Bj ∩ P, j ∈ [m]}).

2. Preliminaries Let G = (V, E, a) be an undirected graph with node set V of size |V | = n, edge set E of size |E| = m, and vertex attribute vector a : V → Rd . H = (VH , EH ) is a pattern graph with |VH | = h and |EH | = mH . A subgraph of G isomorphic to H is called an occurrence of H. We use fH (G) to represent the number of occurrences of H in G. Let Kn denote the complete P graph on n vertices. For x ∈ Rk , we denote ∥x∥1 = i∈[k] |xi | and ∥x∥∞ = maxi∈[k] |xi |.

Definition 2.9. For a matrix M ∈ Rm×n and a set C ⊆ {0, ±1}n , the discrepancy of the matrix M is defined as discC (M) = minχ∈C ∥Mχ∥∞ . For any α = Ω(1), let Cα be the set of all vectors χ ∈ {0, ±1}n satisfying ∥χ∥1 ≥ αn. We have following result, whose proof idea follows from Chazelle & Lvov (2001); Muthukrishnan & Nikolov (2012); Matoušek & Nikolov (2015) and we defer the proof to Section D.1.

Differential privacy The global sensitivity and local sensitivity of a function are defined as follows.

Lemma 2.10. For any m large enough, there exists a set of n = Θ(m) points P ⊆ Rd and a query set Q defined by m axis-parallel boxes B1 , B2 , . . . , Bm ⊆ Rd , such that these boxes have a non-empty common intersection and the following holds. Let A denote the incidence matrix of the collection of set {Bj ∩ P, j ∈ [m]}. For any α = Ω(1),

Definition 2.1 (Local Sensitivity (Nissim et al., 2007)). For any function f : X → Rk defined over a domain space X and any G ∈ X , the local sensitivity of the function f at input G is defined as LSf (G) = maxG′ :G∼G′ ∥f (G) − f (G′ )∥1 .

• if d = O(1), then discCα (A) = Ω(logd−1 n); • if d = O(log n), then discCα (A) = 2Ω(d) ; • if d = Ω(log n), then discCα (A) = nΩ(1) .

Definition 2.2 (Global Sensitivity (Dwork et al., 2006)). For any function f : X → Rk defined over a domain space X , the global sensitivity of the function f is defined as GSf = maxG∼G′ ∥f (G) − f (G′ )∥1 = maxG LSf (G).

3. The Upper Bound

We will make use of the following composition theorems of differential privacy.

Our approximate DP algorithm in Theorem 1.3 is based on a pure DP algorithm, which we introduce below.

Proposition 2.3 (Basic Composition Theorem (Dwork et al., 2006)). For any ε, δ > 0, the composition of k (ε, δ)differentially private algorithms is (kε, kδ)-differentially private.

3.1. The pure DP algorithm The high level description of the algorithm is as follows: (1) Find all occurrences of subgraph H in G and map each to a rank tuple (see below) in [n]2d . Project each occurrence into its rank tuple to obtain a weight vector w of length n2d (see Algorithm 1). (2) Treat the rank tuples weighted points in [n]2d and build a differentially private 2dD range tree over them (see Algorithm 2). (3) Answer each query by traversing the range tree and aggregating the noisy weights of the corresponding nodes (see Algorithm 3).

Proposition 2.4 (Advanced Composition Theorem (Kairouz et al., 2015)). For any ε, δ, δ ′ > 0, the composition ofpk (ε, δ)-differentially private algorithms is (kε2 /2 + ε 2k ln(1/δ ′ ), kδ + δ ′ )-differentially private. Laplace distribution and Laplace mechanism We now introduce the definitions of Laplace distribution and Laplace mechanism. Definition 2.5 (Laplace Distribution). We say a zero-mean random variable X follows the Laplace distribution with parameter b if the probability density function of X follows 1 − |x| Lap(b) = 2b e b .

Now we describe our algorithm in more detail. Subgraph counting projection Algorithm 1 takes as input an n-vertex graph G = (V, E, a). For each i ∈ [d], let Ai (V, a) be the set of the i-th attributes for all vertices in V . Let si (v) ∈ [n] represent the rank of ai (v) in Ai (V, a) for some vertex v, when the i-th attributes in Ai (V, a) are sorted in ascending order. Note that we have si (u) = si (v)

Fact 2.6. If Y ∼ Lap(b), then Pr[|Y | > tb] ≤ e−t . Definition 2.7 (Laplace Mechanism (Dwork et al., 2006)). For any function f : X → Rk , the Laplace mechanism 4

Differentially Private Range Subgraph Counting

Algorithm 1 P ROJ (G = (V, E, a), H) Counting Projection

Algorithm 2 T REE C ONST(w, ε′ ) ▷ DP Range Tree Construction 1: Input: Projection vector w, and privacy parameter ε′ . 2: Construct a 2dD range tree T1 according to Theorem C.5 using a set of points {(v, wv )}v∈[n]2d . 3: Create a noisy version Te1 by adding Laplace noise to the weights of nodes in all 1D range trees within T1 . Specifically, update the weight as weight = weight + Lap(1/ε′ ). 4: return Te1 .

▷ Subgraph

1: Input: An n-vertex graph G = (V, E, a). 2: For each i ∈ [d], sort the i-th attributes in Ai (V, a), and

then define the rank function si : V → [n]. 3: Initialize wv = 0, for any v ∈ [n]2d . 4: for all occurrences of subgraph H in G do 5: Compute w(si (ui ),si (vi ))d = w(si (ui ),si (vi ))d

+ 1, i=1 i=1 where ui (resp. vi ) be the vertex in this occurrence with the smallest (resp. largest) rank in dimension i. 6: return w.

Algorithm 3 PDP RSC(G, H, Q, ε) Subgraph Counting

▷ Pure DP Range

1: Input: An n-vertex graph G = (V, E, a), a pattern

graph H, a query set Q, and privacy parameter ε. 2: Set GSfH = fH (Kn ) − fH (Kn − e). 3: Set w = P ROJ(G, H) and JQ = ∅. 4: Set Te1 = T REE C ONST(w, GS

fH ·(⌈log n⌉+1)

5: for each query q ∈ Q do Qd 6: Determine i=1 [ℓi , ri ] according to Theorem 3.2.

Add the query result of Te1 (see Theorem C.6) using Qd the range i=1 ([ℓi , n] × [1, ri ]) to JQ . 8: return JQ . 7:

Figure 1. Schematic diagram of the 2dD range tree T1 for d = 1. The tree construction process recursively divides [n]2 into two equal parts, where each tree node in T1 is associated with a 1D range tree (e.g., T2 ), and each tree node in a 1D range tree stores the corresponding weight sum (see Section C.1 for more details).

Qd Query procedure For any query q = i=1 [ℓi , ri ] ∈ Q, we first apply the discretization described below to obtain a new query q ′ . Note that the ranges q and q ′ correspond to the same induced subgraph. For simplicity, we will use Qd q = i=1 [ℓi , ri ] to refer to the discretized query. Qd Definition 3.2 (Discretization). Let q = i=1 [ℓi , ri ] be a query. For each [li , ri ], we associate it with two vertices vℓi and vri , where vℓi = arg minv∈V,ai (v)≥ℓi ai (v) and vri = arg maxv∈V,ai (v)≤ri ai (v). The discretized query q ′ Qd is defined as i=1 [si (vℓi ), si (vri )].

if two vertices u and v have the same i-th attribute. Now we present the definition of the rank tuple of an occurrence. Definition 3.1 (Rank Tuple). The rank tuple of an occurrence H ′ = (V (H ′ ), E(H ′ )) is defined as a 2d-tuple (si (ui ), si (vi ))di=1 satisfying ui = arg minv∈V (H ′ ) si (v) and vi = arg maxv∈V (H ′ ) si (v) for all i ∈ [d]. For each occurrence of a subgraph H in G, it updates a weight vector w at the position corresponding to its rank tuple. Each position in w records the number of occurrences that share a specific rank tuple.

Qd For a discretized query q = i=1 [ℓi , ri ], we call the 2dD Qd range tree query with range i=1 ([ℓi , n] × [1, ri ]), which ensures that all subgraphs exactly falling within the range are counted in the answer.

DP range tree construction Algorithm 2 takes as input the project vector w from Algorithm 1. Then the algorithm treats each rank tuple v in [n]2d as a point with weight wv and utilizes a 2dD range tree (see Section C.1) to preprocess these points.

The complete algorithm is presented in Algorithm 3, with its analysis deferred to Section E.1. To improve time efficiency, the implementation of Algorithm 3 differs slightly from the pseudocode without affecting correctness (see Section E.3). As a result, we obtain the following theorem.

The schematic diagram of the 2dD range tree, with d = 1 as an example, is shown in Figure 1. In the 2dD range tree, each leaf node of every 1D range tree corresponds to a point in [n]2d , and its weight is set to the weight of the corresponding point. The weight of each internal node of every 1D range tree is set to the sum of the weights of its children. We add Laplace noise to the weights of nodes in all 1D range trees to ensure privacy.

Theorem 3.3 (Pure DPRSC). For any ε > 0, there exists an ε-DP algorithm that, given a graph G = (V, E, a) with d-dimensional vertex attributes, a fixed pattern graph H, and a query set Q, outputs noisy answers feH (Gq ) which satisfy maxq∈Q fH (Gq ) − feH (Gq ) = 5

Differentially Private Range Subgraph Counting

Algorithm 4 E STIMATE HS(G, H, ε′ , δ ′ ) ▷ Estimating private higher-order local sensitivity (Algorithm 5 in Nguyen et al. (2023))

Algorithm 5 ADP RSC (G, H, Q, ε,δ) mate DP Range Subgraph Counting

1: Input: An n-vertex graph G, a pattern graph H with

graph H with mH edges, a query set Q, and privacy parameters ε, δ. 2: Set ε′ and δ ′ such that ε = (mH + 1)ε′ and δ = ′ ′ ′ ′ max(2emH ε + mH eε + 1, mH e2ε + eε + 2)δ ′ . f f (G) = E STIMATE HS(G, H, ε′ , δ ′ ). 3: Set HS H 4: Set w = P ROJ(G, H) and JQ = ∅. ′ f f (G) · 5: Set δ ′′ = min(e−ε /8 , δ ′ ) and ε′′ = ε′ /(HS H p d ′′ (⌈log n⌉ + 1) · 2 2 ln(1/δ )). 6: Set Te1 = T REE C ONST (w, ε′′ ). 7: for each query q ∈ Q do Qd 8: Determine i=1 [ℓi , ri ] according to Theorem 3.2. 9: Add the query result of Te1 (see Theorem C.6) using Qd the range i=1 ([ℓi , n] × [1, ri ]) to JQ . 10: return JQ .

1: Input: An n-vertex graph G = (V, E, a), a pattern

mH edges, privacy parameters ε′ , δ ′ . (m ) f f H = f (mH ) (G). 2: Set HS H H 3: for k = mH − 1 down to 1 do ′ (k) (k+1) ) f f (G) = f (k) (G) + HS ff 4: Set HS (G) ln (1/δ + ′ H

(k+1)

ff Lap(HS H

′

(G)/ε ). (1)

f f (G) = HS f f (G). 5: return HS H H

√

GSfH ·

log(n|Q|)·log3d n ε

▷ Approxi-

, with probability ≥ 1 − n1 .

Here, the hidden constants are of the form cO(d) for some universal constant c > 1. 3.2. The approximate DP algorithm

(V, E, a) with d-dimensional vertex attributes and a corresponding query set Q, such that

Now we present our approximate DP algorithm. We begin by introducing some notation. Let S ⊆ V × V be a set of vertex pairs. Let fH (G, S) denote the number of occurrences of a fixed pattern graph H containing all edges in S in the graph (V (G), E(G) ∪ S). We de(k) fine fH (G) = max|S|=k fH (G, S). Note that we have

• if d = O(1), then η = Ω(logd−1 n̄ · GSfH ); • if d = O(log n̄), then η = 2Ω(d) GSfH ; • if d = Ω(log n̄), then η = n̄Ω(1) GSfH ; where n̄ = min(n, |Q|) can be arbitrarily large.

(1)

fH (G) = LSfH (G) by definition.

We prove Theorem 4.1 via a reduction from the reconstruction attacks (RA) problem to DPRSC, using techniques inspired by Muthukrishnan & Nikolov (2012). Moreover, the proof reveals that for the constructed hard instances, f f (G) is, with high the approximated local sensitivity HS H probability, within a constant factor of the global sensitivity GSfH . This directly implies Theorem 1.4, whose full proof is deferred to Section F.3.

The local sensitivity of w is estimated by iteratively adding noise to ensure privacy (see Algorithm 4). The approach is derived from Nguyen et al. (2023), whose method was originally designed to estimate subgraph counts but has been modified here to estimate the local sensitivity. The complete approximate DP algorithm is presented in Algorithm 5. It closely resembles the pure DP one (i.e. Algorithm 3), with the key difference being in the parameter settings. The algorithm adds noise in the range tree based on the private estimation of local sensitivity rather than global sensitivity. The analysis of this algorithm (i.e., proof of Theorem 1.3) and the implementation details are deferred to Sections E.2 and E.3, respectively.

In Section F.4, we further provide a lower bound of η = Ω(log n̄ · GSfH ) for the case d = 1, under the additional assumption that δ = n−Ω(1) . 4.1. The reduction We first introduce the reconstruction attacks problem and then reduce it to range subgraph counting.

4. The Lower Bound In this section, we prove the following theorem which presents a lower bound for DPRSC.

Definition 4.2 (Reconstruction Attacks (RA); (Dinur & Nissim, 2003)). Given a private vector x ∈ {0, 1}N , a reconstruction algorithm outputs a vector in {0, 1}N . The goal is to design an (ε, δ)-DP algorithm B minimizing ∥B(x) − x∥1 .

Theorem 4.1 (Lower Bound of DPRSC). For any pattern graph H, let A be an (ε, δ)-DP algorithm with constants ε > 0 and δ ∈ [0, 12 ) for the range subgraph counting problem with additive error η = maxq∈Q |fH (Gq ) − feH (Gq )| with a sufficiently large constant success probability.

From RA to RSC Let P ⊆ Rd be a point set of size n and let Q be a collection of m axis-parallel boxes B1 , . . . , Bm with a non-empty common intersection.

Then there exist infinitely many n-vertex graphs G = 6

Differentially Private Range Subgraph Counting (1)

···

(1)

pi · · ·

(1)

Table 1. Summary of real-world datasets used in our experiments (see (Newman, 2006; Cho et al., 2014; Rozemberczki et al., 2019)). Here n, m, davg , and dmax denote the number of nodes, edges, average degree, and maximum degree, respectively.

P (1)

(xpi = 1)

Dataset CA-Netscience Wiki-Squirrel WormNet-v3

W (Kn−2 )

(2) p1

···

(2) pi · · ·

(2) pn

n 379 5,201 16,347

m 914 198,353 762,822

davg 4.8 76.3 93.3

dmax 34 1,903 1,272

(2)

Figure 2. The construction of the graph G(x). P (1) and P (2) contain n vertices respectively, while W contain n − 2 vertices. We omit the edges from the set P (1) ∪ P (2) to W except those (1) (2) (1) incident to the vertices pi and pi (red edges). The vertices pi (2) and pi , together with those in W , induce a n-vertex clique.

Note that AH is fixed and depends only on K3n−2 and the query set Q, and is independent of the edge set of G(x). Let xH ∈ {0, 1}fH (K3n−2 ) be the indicator vector whose coordinates correspond to occurrences H ′ of H in K3n−2 , where (xH )H ′ = 1 if all edges of H ′ are present in G(x), and 0 otherwise. Then for each query q ∈ Q, the quantity (AH xH )q equals the number of occurrences of H in the induced subgraph (G(x))[Vq ].

Graph construction We construct a graph G(x) as follows. Create two copies of P , denoted P (1) and P (2) . For each p ∈ P , let p(1) ∈ P (1) and p(2) ∈ P (2) denote its copies. Let W be a set of n − 2 auxiliary vertices, all lying in the common intersection of the boxes in Q.

Let Cα,H denote the set of vectors χ = xH − x′H ∈ {0, ±1}fH (K3n−2 ) such that x − x′ ∈ Cα . The following lemma, proved in Section F.1, shows that AH inherits large discrepancy from the point-incidence matrix.

The vertex set of G(x) is V = P (1) ∪ P (2) ∪ W , so that |V | = 3n − 2 (see Figure 2). For each p ∈ P , we add an edge between p(1) and p(2) if and only if xp = 1. In addition, every vertex in P (1) ∪ P (2) is connected to every vertex in W , and W induces a clique.

Lemma 4.3. Let P ⊆ Rd be a set of n points, and let Q be a collection of m sets B1 , . . . , Bm ⊆ Rd with a non-empty common intersection. Let A be the incidence matrix of {Bj ∩ P : j ∈ [m]}. For any α = Ω(1) and any pattern graph H, if discCα (A) = ω(1), then discCα,H (AH ) = Ω(GSfH · discCα (A)), where GSfH denotes the global sensitivity of fH on n-vertex graphs.

The edges between p(1) and p(2) encode the private data x, while all other edges are public. Consequently, two vectors x, x′ are neighboring if and only if the corresponding graphs G(x) and G(x′ ) are neighboring.

Proof sketch of Theorem 4.1 Given the above reduction, we show that if there exists a DP algorithm for RSC whose additive error is asymptotically smaller than discCα,H (AH ), then this algorithm can be used to solve RA with small error (Theorem F.2). This contradicts known lower bounds for RA (Theorem F.3), and thus yields the desired lower bound for DPRSC. We defer the full argument to Section F.2.

Hard instance We begin with a point set of size n̄ and a query set Q from Theorem 2.10. We then add n − n̄ dummy points lying outside all boxes in Q to form P . Using this point set P and query set Q, we construct the graph G(x) as described above and use Q as the query set for the RSC problem. We denote the resulting instance by (G(x), Q), which completes the construction of the hard instance. 4.2. The analysis

5. Experiments

To prove the lower bound using the constructed instance (G(x), Q), we associate it with a matrix AH and show that this matrix has large discrepancy.

Now we present our experimental results. All algorithms were implemented in Python2 , and run on an Intel(R) Xeon(R) Platinum 8562Y Processor @ 2.80 GHZ with 768 GB RAM. We evaluated our methods on three real-world datasets, after removing self-loops and duplicate edges from each graph. Basic statistics for these datasets are summarized in Table 1. The edges are treated as sensitive data.

The matrix The matrix AH is defined with respect to the complete graph K3n−2 on vertex set V = P (1) ∪ P (2) ∪ W . It has |Q| rows and fH (K3n−2 ) columns. Each row corresponds to a query q ∈ Q, i.e., the induced subgraph K3n−2 [Vq ], and each column corresponds to an occurrence H ′ of the pattern H in K3n−2 . The entries are defined as ( 1, if E(H ′ ) ⊆ E(K3n−2 [Vq ]); (AH )q,H ′ = 0, otherwise.

Baseline There is no prior work on DP range subgraph counting. We construct two natural baselines for comparison. The first baseline PDP Comp answers each query 2 The corresponding codes and data are available at https: //github.com/Airleave/DPRSC.

Differentially Private Range Subgraph Counting

(a) Wiki-Squirrel

(b) Wiki-Squirrel

(a) Wiki-Squirrel

(b) Wiki-Squirrel

(d) WormNet-v3

Figure 4. Relative error vs. |Q|

Figure 3. Relative error vs. ε

(a) Wiki-Squirrel

(b) Wiki-Squirrel

(a) Wiki-Squirrel

(b) Wiki-Squirrel

(d) WormNet-v3

Figure 6. Total time

Figure 5. Query time and preprocessing time GS

·|Q|

independently by adding Laplace noise with scale fHε , using the basic composition theorem (Theorem 2.3). The second baseline ADP Comp improves upon this by applying Theorem E.5 and the advanced composition theorem (Theorem √ 2.4), adding Laplace noise with scale f HS

(G)·

Table 2. The performance guarantees of DP algorithms for counting occurrences of H. We assume that ε, δ, d are constants and e hides factors that are |Q| is a polynomial in n. The notation O(·) polylogarithmic in n. The additive errors hold with probability at least 1 − n1 and are given by Theorem 2.6, Theorems 1.3 and 3.3.

|Q| ln(1/δ)

Θ( fH ). We denote our pure DP algorithm ε (Algorithm 3) and approximate DP algorithm (Algorithm 5) by PDP RSC and ADP RSC, respectively. The comparison of different algorithms is provided in Table 2. Setting and metric All algorithms satisfy either ε-DP or (ε, δ)-DP. We set ε = 2.0, δ = 10−5 (which satisfies δ < n1 for all datasets considered), d = 1 and |Q| = ⌈n1.5 ⌉ by default. Each query q in Q is generated randomly and corresponds to an induced vertex set Vq with |Vq | = Θ(n). Experiments are conducted on three datasets, with H being a triangle, 2-star, or edge. Results for edge and CA-

Algorithm

Additive Error

PDP Comp ADP Comp PDP RSC ADP RSC

ε (ε,δ) ε (ε, δ)

e O(GS fH · |Q|) p e f O(HSfH (G) · |Q|) e O(GS fH ) e g O(HSf (G)) H

Netscience are deferred to Sections G.1 and G.2, respectively. For each vertex in these networks, we independently sample attributes from a standard normal distribution as a conservative (worst-case) evaluation; the rationale for 8

Differentially Private Range Subgraph Counting

this choice is provided in Section G.4. We also include additional experiments to complement the default setting: Results for d > 1, small-range queries and real attributes are provided in Sections G.2 to G.4, respectively. We mea-

consistently outperforms the baselines in total time when |Q| = Ω(n), and the advantage becomes increasingly pronounced as |Q| grows. Moreover, the advantage is more significant on larger datasets. Overall, when Q = Θ(n2 ), the total time is dominated by the total query time, yielding a speedup of 3 to 4 orders of magnitude.

|fe (G )−f (G )|

q q H H sure relative error as max(f , following standard H (Gq ),0.001n) practice (Imola et al., 2021). Each algorithm is run at least 20 times; we report mean relative error and runtime, with standard-deviation bands shown in figures. We define the query time as the time required to answer a single query, the total query time as the sum of the query times over all queries, and the total time as the sum of the preprocessing time and the total query time.

6. Conclusion In this paper, we study the DPRSC problem and present the first efficient algorithms achieving small additive error. We complement these results with lower bounds showing an exponential dependence on the attribute dimension, nearly matching our upper bounds.

Relative error vs. ε Figure 3 shows that our algorithms consistently outperform the baselines across all tested privacy parameter ε (smaller values of ε correspond to stronger privacy guarantees), achieving substantially lower mean error and variance. The approximate DP algorithm ADP RSC generally performs best on sparse graphs, except for 2stars on Wiki-Squirrel, where large dmax increases the local sensitivity and noise relative to PDP RSC, since f f (G) ≈ 2dmax for 2-stars (Section C.3). For trianHS H gles, ADP RSC is more sensitive to small ε since estimating f f requires iteratively adding noise related to ε and δ. HS H

A limitation of our work is that our current algorithms do not address settings in which attribute information is sensitive and must be protected. Combining our techniques with existing methods (e.g., (Dwork et al., 2015)) may yield upper and lower bounds in this setting. However, achieving general algorithms with optimal utility guarantees would likely require new ideas beyond our current approach. In addition, a gap remains between our upper and lower bounds in certain parameter regimes, leaving room for improvement in both analysis and algorithm design. Another interesting direction is to extend the RSC problem to more challenging settings, such as dynamic graphs where edges or attributes evolve over time, and alternative privacy models including local differential privacy and node-level differential privacy.

Relative error vs. |Q| As shown in Figure 4, our algorithms are largely insensitive to |Q|, whereas baseline errors increase quickly with |Q|. A minor exception occurs for very small |Q| < 2n in the ADP Comp vs. ADP RSC comparison, consistent with the theoretical bounds in Theorem 1.3. The performance gap grows as |Q| increases.

Acknowledgments

Runtime For runtime evaluation, we assume that the queries in Q are i.i.d. and uniformly sampled from all queries that produce distinct induced subgraphs. We evaluated the relationship between the total time and |Q| in Figure 6. |Q| ranges from 1 to Θ(n2 ), which corresponds to the full range of |Q| under our setting when d = 1. Since exhaustively evaluating all Θ(n2 ) queries is computationally prohibitive, we sample a sufficiently large number of queries from the distribution defined above. We continue sampling until the average query time converges, as measured by a small relative standard error (below 5%), and use the average query time and preprocessing time (shown in Figure 5) to estimate the total time. Given the substantial differences in query time between our algorithms and the baselines, the resulting estimation error is negligible. As shown in Figure 5, our algorithms significantly outperform the baselines in query time, achieving lower latency by 3 to 4 orders of magnitude at the cost of higher preprocessing time. Note that PDP comp requires no preprocessing. Here, the baselines compute exact counts of 2-stars using a straightforward implementation in O(m) time, while exact triangle counting is carried out using the widely adopted algorithm from Chiba & Nishizeki (1985). Figure 6 shows that our algorithm

This work is supported in part by NSFC Grant 62272431 and Quantum Science and Technology - National Science and Technology Major Project (Grant No. 2021ZD0302901).

Impact Statement This paper presents work whose goal is to advance the field of Machine Learning and Algorithmic Privacy. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.

References Alon, N., Yuster, R., and Zwick, U. Color-coding. Journal of the ACM (JACM), 42(4):844–856, 1995. Arora, R. and Upadhyay, J. On differentially private graph sparsification and applications. Advances in neural information processing systems, 32, 2019. Assadi, S., Kapralov, M., and Khanna, S. A simple sublineartime algorithm for counting arbitrary subgraphs via edge sampling. In Blum, A. (ed.), 10th Innovations in Theo9

Differentially Private Range Subgraph Counting

retical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pp. 6:1–6:20. Schloss Dagstuhl - LeibnizZentrum für Informatik, 2019.

Curticapean, R., Dell, H., and Marx, D. Homomorphisms are a good basis for counting small subgraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 210–223, 2017.

Azuma, K. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, Second Series, 19(3):357–367, 1967.

Dalirrooyfard, M., Mitrovic, S., and Nevmyvaka, Y. Nearly tight bounds for differentially private multiway cut. Advances in Neural Information Processing Systems, 36, 2024.

Bentley, J. L. and Saxe, J. B. Decomposable searching problems. 1978.

De, A. Lower bounds in differential privacy. In Theory of cryptography conference, pp. 321–338. Springer, 2012.

Björklund, A., Pagh, R., Williams, V. V., and Zwick, U. Listing triangles. In International Colloquium on Automata, Languages, and Programming, pp. 223–234. Springer, 2014.

Deng, C., Gao, J., Upadhyay, J., and Wang, C. Differentially private range query on shortest paths. In Algorithms and Data Structures Symposium, pp. 340–370. Springer, 2023a.

Blocki, J., Blum, A., Datta, A., and Sheffet, O. The johnsonlindenstrauss transform itself preserves differential privacy. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pp. 410–419. IEEE, 2012.

Deng, S., Lu, S., and Tao, Y. Space-query tradeoffs in range subgraph counting and listing. 255:6:1–6:25, 2023b. Dinur, I. and Nissim, K. Revealing information while preserving privacy. In Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp. 202–210, 2003.

Blocki, J., Blum, A., Datta, A., and Sheffet, O. Differentially private data analysis of social networks via restricted sensitivity. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pp. 87– 96, 2013.

Dwork, C., McSherry, F., Nissim, K., and Smith, A. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pp. 265–284. Springer, 2006.

Bollobás, B. and Scott, A. Discrepancy in graphs and hypergraphs. More Sets, Graphs and Numbers: A Salute to Vera Sós and András Hajnal, pp. 33–56, 2006.

Dwork, C., Naor, M., Pitassi, T., and Rothblum, G. N. Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium on Theory of computing, pp. 715–724, 2010.

Bun, M. M. New Separations in the Complexity of Differential Privacy. PhD thesis, 2016.

Dwork, C., Naor, M., Reingold, O., and Rothblum, G. N. Pure differential privacy for rectangle queries via private partitions. In International Conference on the Theory and Application of Cryptology and Information Security, pp. 735–751. Springer, 2015.

Chan, T.-H. H., Shi, E., and Song, D. Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):1–24, 2011. Chazelle, B. and Lvov, A. The discrepancy of boxes in higher dimension. Discrete & Computational Geometry, 25(4):519–524, 2001.

Eden, T., Liu, Q. C., Raskhodnikova, S., and Smith, A. Triangle counting with local edge differential privacy. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pp. 52–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2023.

Chen, S. and Zhou, S. Recursive mechanism: towards node differential privacy and unrestricted joins. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pp. 653–664, 2013.

Eliáš, M., Kapralov, M., Kulkarni, J., and Lee, Y. T. Differentially private release of synthetic graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 560–578. SIAM, 2020.

Chiba, N. and Nishizeki, T. Arboricity and subgraph listing algorithms. SIAM Journal on computing, 14(1):210–223, 1985.

Fichtenberger, H., Gao, M., and Peng, P. Sampling arbitrary subgraphs exactly uniformly in sublinear time. In Czumaj, A., Dawar, A., and Merelli, E. (eds.), 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken,

Cho, A., Shin, J., Hwang, S., Kim, C., Shim, H., Kim, H., Kim, H., and Lee, I. Wormnet v3: a network-assisted hypothesis-generating server for caenorhabditis elegans. Nucleic acids research, 42(W1):W76–W82, 2014. 10

Differentially Private Range Subgraph Counting

Germany (Virtual Conference), volume 168 of LIPIcs, pp. 45:1–45:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.

Lindell, Y. Tutorials on the Foundations of Cryptography. Springer, 2017. Matoušek, J. and Nikolov, A. Combinatorial discrepancy for boxes via the gamma 2 norm. In 31st International Symposium on Computational Geometry (SoCG 2015), pp. 1–15. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2015.

Fichtenberger, H., Henzinger, M., and Ost, L. Differentially private algorithms for graphs under continual observation. In Mutzel, P., Pagh, R., and Herman, G. (eds.), 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs, pp. 42:1–42:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.

Muthukrishnan, S. and Nikolov, A. Optimal private halfspace counting via discrepancy. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pp. 1285–1292, 2012.

Gupta, A., Ligett, K., McSherry, F., Roth, A., and Talwar, K. Differentially private combinatorial optimization. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pp. 1106–1125. SIAM, 2010.

Newman, M. E. Finding community structure in networks using the eigenvectors of matrices. Physical review E, 74 (3):036104, 2006. Nguyen, D., Halappanavar, M., Srinivasan, V., and Vullikanti, A. Faster approximate subgraph counts with privacy. Advances in Neural Information Processing Systems, 36, 2023.

Gupta, A., Roth, A., and Ullman, J. Iterative constructions and private data release. In Theory of Cryptography: 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings 9, pp. 339–356. Springer, 2012.

Nissim, K., Raskhodnikova, S., and Smith, A. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 75–84, 2007.

Imola, J., Murakami, T., and Chaudhuri, K. Locally differentially private analysis of graph statistics. In 30th USENIX security symposium (USENIX Security 21), pp. 983–1000, 2021.

Peng, P. and Xu, H. Differentially private synthetic graphs preserving triangle-motif cuts. In The Thirty Eighth Annual Conference on Learning Theory, pp. 4511–4564. PMLR, 2025.

Imola, J., Murakami, T., and Chaudhuri, K. Communicationefficient triangle counting under local differential privacy. In 31st USENIX security symposium (USENIX Security 22), pp. 537–554, 2022a.

Rozemberczki, B., Allen, C., and Sarkar, R. Multi-scale attributed node embedding, 2019.

Imola, J., Murakami, T., and Chaudhuri, K. Differentially private triangle and 4-cycle counting in the shuffle model. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pp. 1505–1519, 2022b.

Shalev-Shwartz, S. and Ben-David, S. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014. Wainwright, M. J. High-dimensional statistics: A nonasymptotic viewpoint, volume 48. Cambridge university press, 2019.

Kairouz, P., Oh, S., and Viswanath, P. The composition theorem for differential privacy. In International conference on machine learning, pp. 1376–1385. PMLR, 2015.

Warner, S. L. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American statistical association, 60(309):63–69, 1965.

Karwa, V., Raskhodnikova, S., Smith, A., and Yaroslavtsev, G. Private analysis of graph structure. Proceedings of the VLDB Endowment, 4(11):1146–1157, 2011.

Zhang, J., Cormode, G., Procopiuc, C. M., Srivastava, D., and Xiao, X. Private release of graph statistics using ladder functions. In Proceedings of the 2015 ACM SIGMOD international conference on management of data, pp. 731–745, 2015.

Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., and Smith, A. What can we learn privately? SIAM Journal on Computing, 40(3):793–826, 2011. Kasiviswanathan, S. P., Nissim, K., Raskhodnikova, S., and Smith, A. Analyzing graphs with node differential privacy. In Theory of Cryptography: 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings, pp. 457–476. Springer, 2013. 11

Differentially Private Range Subgraph Counting

A. Overview of the Appendix The appendix is organized as follows: • Section B: we provide the discussion of other related work. • Section C: we provide the supplementary tools used in the appendix. • Section D: we present the deferred proofs from Section 2. • Section E: we present the deferred proofs, analysis and implementation details from Section 3. • Section F: we present the deferred proofs and analysis from Section 4. • Section G: we present the deferred experiments and implementation details from Section 5. • Section H: we present better upper and lower bounds of DPRSC in higher dimensions d as extensions.

B. Other Related Work DP subgraph counting The DP subgraph counting problem is a topic that has been extensively studied, primarily for the entire graph G. Nissim et al. (2007) improved the utility guarantees for triangle counting in differential privacy by incorporating instance-dependent noise. Karwa et al. (2011) extended the smooth sensitivity approach to k-stars and proposed methods for computing local sensitivity to perform k-triangle counting. Kasiviswanathan et al. (2013) introduced a triangle counting algorithm under the node-DP framework. Zhang et al. (2015) developed ladder functions for various subgraph counting tasks. Nguyen et al. (2023) focused on optimizing runtime by calculating approximate smooth sensitivity for graphs with certain properties, achieving both privacy and utility while reducing time complexity. Additionally, several studies have examined subgraph counting under the local DP model, such as Imola et al. (2021; 2022a;b); Eden et al. (2023), while Fichtenberger et al. (2021) studied DP subgraph counting in dynamic model. DP range queries Muthukrishnan & Nikolov (2012) present algorithms for the halfspace range counting problem under differential privacy, achieving good approximate accuracy in terms of average squared error. Deng et al. (2023a) propose an algorithm for counting queries and bottleneck queries on shortest paths while ensuring differential privacy. A closer examination of their model reveals that they effectively address a range counting problem on a graph. A cut query on a graph is a specialized form of range counting, where the range space includes all possible cuts. The cut query problem is widely studied in the field of differential privacy, with significant research dedicated to it (Gupta et al., 2010; Blocki et al., 2012; Gupta et al., 2012; Arora & Upadhyay, 2019; Eliáš et al., 2020; Dalirrooyfard et al., 2024). DP lower bound DP lower bounds are often motivated by reconstruction attacks (Dinur & Nissim, 2003), which show that answering too many queries accurately can leak sensitive information about the dataset. Building on this technique, Muthukrishnan & Nikolov (2012) explore the connections between discrepancy theory and DP lower bound. In particular, they establish the first lower bound on the average squared error for the private range counting problem. Subsequent improvements in discrepancy results by Matoušek & Nikolov (2015) further strengthen the lower bound. Furthermore, based on the connections, Eliáš et al. (2020) studied the lower bound for DP synthetic graph generation to approximate all cuts, while Peng & Xu (2025) extended this to triangle-motif cuts. Their approaches heavily rely on the randomness inherent in Erdős–Rényi graphs, which limits its applicability to range subgraph counting for moderate d.

C. Supplementary Tools We will make use of the following post-processing property of differential privacy. Proposition C.1 (Post-processing Property (Dwork et al., 2006)). Let M : Rd1 → Rd2 be an (ε, δ)-differentially private mechanism and let h: Rd2 → Rd3 be an arbitrary function. Then, the function g ◦M : Rd1 → Rd3 is also (ε, δ)-differentially private.

The sum of multiple variables that follow the Laplace distribution satisfies the following properties. Lemma C.2 (Chan et al. (2011); Wainwright (2019)). Let {Xi } be a collection of independent random variables such that √ pP P 2 2ν 2 2 Xi ∼ Lap(bi ) for all 1 ≤ i ≤ m. Then, for ν ≥ for b = maxi {bi }, Pr [| i Xi | ≥ λ] ≤ i bi and 0 < λ < b √ 2 √ P λ2 2 · exp(− 8ν 2 ). Furthermore, if b = bi for any i ∈ [m] and m ≥ log β, we have Pr | i Xi | ≥ 2 2 · b m log β ≤ β . 12

Differentially Private Range Subgraph Counting

C.1. Definitions and properties of range tree A range tree is a binary tree structure designed for interval queries and summation. For clarity, we define the tree construction and query process to streamline the algorithm’s description. The construction of the range tree is based primarily on Bentley & Saxe (1978), with minor modifications. We begin by introducing the basic 1D range tree. Definition C.3 (1D Range Tree). Given a set of points P = {(xt , wt )}, where each point has an x-coordinate xt and a weight wt , the 1D range tree is constructed as follows: 1. Sort the points by x-coordinates, denoted as x1 , . . . , xn . 2. Begin building the tree recursively from the root node, where the interval spans from x1 to xn . 3. For a given interval xl , . . . , xr corresponding to a tree node p, set mid = ⌊ l+r 2 ⌋. Recursively construct the left child using points xl , . . . , xmid and the right child using points xmid+1 , . . . , xr . If the interval contains only one kind of coordinate, terminate the recursion and set the weight of the current tree node to the sum of the weights of the points at the coordinate. 4. During backtracking, sum the weights of the left child and the right child as the weight of the current tree node: node.weight = lef t.weight + right.weight. Definition C.4 (1D Range Tree Query). Given a query range [low, high], start at the root node of the 1D range tree T . 1. Start the recursive query from the root node of T . 2. For the current node, if node falls within the range [low, high], return p.weight. If low lies within the left child of p, recursively query the left subtree; if high1 lies within the right child, recursively query the right subtree. 3. When backtracking, sum the results of the left child and the right child and return them. Next, we introduce the kD Range Tree (k ≥ 2). Definition C.5 (kD Range Tree Construction). For a set of points P = ((xit )ki=1 , wt ) where each point has coordinates (xit )ki=1 and a weight wt , the kD range tree is constructed as follow: 1. Group the points by their first dimension, and sort each group by the first dimension, denoted as p1 , . . . , pn . 2. Construct the kD range tree T1 using p1 , . . . , pn in a similar approach to the 1D range tree, partitioning the first dimension. Note that each node of T1 contains an associated (k − 1)D range tree T2 for the second dimension, recursively. 3. For each node in T1 , take the points covered by that node, group them by their second dimension, sort them, and construct a corresponding (k − 1)D range tree T2 . Qk Definition C.6 (kD Range Tree Query). Given a k-dimensional query range i=1 [lowi , highi ] and kD range tree T1 : 1. Start the recursive query from the root node of T1 . Qk 2. For the current node, if node falls within the range [low1 , high1 ], perform a query i=2 [lowi , highi ] on T2 (call (k − 1)D tree query recursively). If low1 lies within the left child of node, recursively query the left subtree; if high1 lies within the right child, recursively query the right subtree. 3. When backtracking, sum the results of the left child and the right child and return them. We present construction and query time complexity of kD range tree for any k ≥ 1. Lemma C.7 (Construction Time). For any k ≥ 1, the runtime of kD range tree construction is O(n logk n). Lemma C.8 (Query Time). For any k ≥ 1, the runtime of kD range tree query is O(logk n). Based on the properties of the range tree, we can derive the following lemma. Lemma C.9. Let T denote a kD range tree constructed from a set of points P = {((xit )ki=1 , wt )}. If a k-dimensional query Qk range i=1 [lowi , highi ] satisfies lowi ≤ minx∈P xi or highi ≥ maxx∈P xi for all i ∈ [k], the query result is the sum of the weights of at most ⌈log n⌉k tree nodes. Proof. Note that the depth of the tree (i.e., the maximum number of nodes along the path from the root node to any node in the tree) in each dimension of the kD range tree is at most (⌈log n⌉ + 1) by Theorem C.5. For each i ∈ [k], consider the process of querying the range [lowi , highi ] on the (k − i + 1)D range trees. 13

Differentially Private Range Subgraph Counting

If lowi ≤ minx∈P xi and highi ≥ maxx∈P xi , only the root node of each (k −i+1)D range tree can be queried. Otherwise, the weight of the root node is not included in the sum. Moreover, when querying the left and right subtrees simultaneously on each (k − i + 1)D range tree, at least one of the subtrees will return after performing a query at its root node. Therefore, for each 1D range tree, at most ⌈log n⌉ tree nodes’ weights are summed; For each (k − i + 1)D range tree satisfying 2 ≤ i ≤ k, at most ⌈log n⌉ tree nodes will be queried. After aggregating the results over k dimensions, the query result is the sum of the weights of at most ⌈log n⌉k tree nodes. C.2. Tight bound on the global sensitivity of subgraph counting In Section 3, we used GSfH to denote the global sensitivity of subgraph counting. We present an exact method for computing the global sensitivity GSfH , from which we derive a simple and asymptotically tight bound. Table 3 summarizes the global sensitivity of common pattern graphs. Table 3. Global sensitivity GSfH of some common pattern graphs H

Pattern Graph

GSfH

Edge

Triangle

n−2 2 n−2 k−1 n−2

k-Star k-Clique

k−2

Definition C.10 (Automorphism Group). An automorphism of a graph G = (V, E) is a permutation σ of V such that (u, v) ∈ E if and only if (σ(u), σ(v)) ∈ E. The set of all automorphisms of G forms a group under composition, called the automorphism group of G, denoted by aut(G). Lemma C.11. For n-vertex graphs, given a pattern graph H, the global sensitivity GSfH is given by 2mH (h − 2)! n−2 GSfH = · = Θ nh−2 , h−2 |aut(H)| where the hidden constant depends only on h. Proof. Note that GSfH is actually the number of occurrences of H that contain a specific vertex pair (i, j) in the complete graph Kn . This equals the number of ways to choose and permute the remaining h − 2 vertices, multiplied by the number of ways to map an edge of H to (i, j), divided by |aut(H)| to account for symmetries. Since h − 1 ≤ mH ≤ h2 and 1 ≤ |aut(H)| ≤ h!, the expression for GSfH yields a tight bound up to constants depending only on h. Following analogous reasoning, we can obtain an upper bound for fH (G). Lemma C.12. For any n-vertex graph G, given a pattern graph H, it holds that n h! fH (G) ≤ fH (Kn ) = · = Θ nh , h |aut(H)| where the hidden constant depends only on h. f f (G) C.3. Discussions on the approximated local sensitivity HS H f f (G) for all H, and its value typically varies depending on H and G. For some H, There is no explicit upper bound on HS H f f (G) can be relatively easy to estimate, while for others, it presents more significant challenges. Nevertheless, our HS H results remain practically significant. For convenience, we use △ and ∗ to represent triangle and 2-star in the following lemmas, respectively. ′ )) ln (2/(βδ ′ )) f f (G) ≤ LSf (G) + ln (2/(βδ Lemma C.13. For any constant β ∈ (0, 1), it holds that HS ( + 1) ≤ dmax (G) + ′ ′ △

ln (2/(βδ ′ )) ln (2/(βδ ′ )) ( + 1) with probability at least 1 − β. ε′ ε′

△

Differentially Private Range Subgraph Counting

Proof. Karwa et al. (2011) provided a proof for the case of k-triangles. For clarity, we have rewritten the proof for triangles. (1)

(2)

(3)

If H is a triangle, then f∆ (G) = LSf△ (G) ≤ dmax (G), f∆ (G) ≤ 1, f∆ (G) ≤ 1. According to the algorithm Algorithm 4, it holds that ′

′

f (G) ≤f (2) (G) + ln (1/δ ) + |Lap(1/ε′ )| ≤ 1 + ln (1/δ ) + |Lap(1/ε′ )| HS f∆ ∆ ε′ ε′ ′ (2) (1) (2) f (G)/ε′ f f (G) =HS f (G) ≤ f (1) (G) + HS f (G) ln (1/δ ) + Lap HS HS f∆ f∆ f∆ ∆ ∆ ε′ ′ (2) (2) f f (G) ln (1/δ ) + Lap HS f f (G)/ε′ . ≤LSf△ (G) + HS ∆ ∆ ′ ε (2)

(2)

f f (G) ≤ We have HS ∆

ln (2/(βδ ′ )) ε′

′

)) ln (2/(βδ )) f f (G) ≤ LSf (G) + ln (2/(βδ + 1 and HS ( + 1) ≤ dmax (G) + △ △ ε′ ε′

ln (2/(βδ ′ )) ln (2/(βδ ′ )) ( + 1) with probability at least 1 − β by Theorem 2.6 and the union bound. ε′ ε′ ′

′

)) )) f f (G) ≤ LSf (G) + ln (1/(βδ Lemma C.14. For any constant β ∈ (0, 1), it holds that HS ≤ 2dmax (G) + ln (1/(βδ ∗ ∗ ε′ ε′ with probability at least 1 − β. (1) (2) f f (G) ≤ Proof. If H is a 2-star, then f∗ (G) = LSf∗ (G) ≤ 2dmax (G), f∗ (G) ≤ 1. According to Algorithm 4, HS ∗ ′ ′ ln (1/δ ′ ) ln )) ln (1/δ ) f f (G) ≤ LSf (G) + (1/(βδ LSf∗ (G) + ε′ + |Lap(1/ε′ )| ≤ 2dmax (G) + ε′ + |Lap(1/ε′ )|. We have HS ≤ ∆ ∗ ε′ ′

)) 2dmax (G) + ln (1/(βδ with probability at least 1 − β by Theorem 2.6. ε′

D. Deferred proofs from Section 2 D.1. Proof of Theorem 2.10 For a matrix A with n columns, and a set S ⊆ [n] we use A|S to denote the submatrix of A consisting of the columns corresponding to elements of S. We adopt the following definition and result from Muthukrishnan & Nikolov (2012), with notation slightly modified. Note that the set Cα for α = 1 is equivalent to the set {±1}n . Definition D.1. For any A ∈ Rm×n , we define herdiscCα (A) = max discCα (A|S ). S⊆[n]

Lemma D.2 (Lemma 5 in Muthukrishnan & Nikolov (2012)). Let f (s) = maxS⊆[n]:|S|≤s discCα (A|S ). Then discC1 (A) ≤ P∞ f ((1 − α)i n). i=0 The case for d = O(1) Let an anchored axis-parallel box denote an element of the form [0, b0 ] × · · · × [0, bd ]. By the main results in Matoušek & Nikolov (2015), we obtain the following lemma. Lemma D.3 (Matoušek & Nikolov (2015)). Let d = O(1). For any n large enough, there exists a set of n points in [n]d and n anchored axis-parallel boxes B1 , B2 , . . . , Bn such that the following holds. Let A denote the incidence matrix of the collection of set {Bj ∩ P, j ∈ [n]}. Then herdiscC1 (A) = Ω(logd−1 n). By an approach similar to that in Muthukrishnan & Nikolov (2012), we derive the following lemma. Lemma D.4. Let d = O(1). For any n large enough, there exists a set of n points P and n axis-parallel boxes B1 , B2 , . . . , Bn with a non-empty common intersection such that the following holds. Let A denote the incidence matrix of the collection of set {Bj ∩ P, j ∈ [n]}. Then for α = Ω(1), discCα (A) = Ω(logd−1 n). Proof. By Theorem D.3, for any n large enough, there exists a set of n points P ′ in [n]d and n anchored axis-parallel boxes B1 , B2 , . . . , Bn such that the incidence matrix B′ of {Bj ∩ P ′ , j ∈ [n]} has herdiscC1 (B′ ) = Ω(logd−1 n). Note that all boxes Bj contain the common point (0, 0, . . . , 0). Let S ∗ = arg maxS∈[n] discC1 (B′ |S ). Let P be the set of points corresponding to S ∗ , and augment P with additional points not contained in any of the boxes B1 , B2 , . . . , Bn , so that |P | = n. Let B denote the incidence matrix of {Bj ∩ P, j ∈ [n]}. Then we have discC1 (B) = discC1 (B′ |S ∗ ) = herdiscC1 (B′ ) = Ω(logd−1 n). Now we can prove the lemma. Assume for contradiction that all but finitely many n × n incidence matrices A of points and axis-parallel boxes with a non-empty common intersection have discrepancy discCα (A) = o(logd−1 n). We take any set 15

Differentially Private Range Subgraph Counting

of points P , axis-parallel boxes, and the corresponding incidence matrix B satisfying discC1 (B) = Ω(logd−1 n) from the previous construction. By augmenting additional points, any restriction B|S for S ⊆ P is also the incidence matrix of sets induced by points and axis-parallel boxes in the assumption, and thus we have discCα (B|S ) = o(logd−1 n). Plugging this bound into Theorem D.2, we get discC1 (B) = o(logd−1 n), a contradiction. The case for d = O(log n)/Ω(log n) A boolean point is a point in {0, 1}d . A boolean axis-parallel box is an element of {{0}, {1}, [0, 1]}d . By a probabilistic construction in Chazelle & Lvov (2001), we obtain the following lemma. Lemma D.5 (Chazelle & Lvov (2001)). Let d = Θ(log n). For any m large enough, there exists a set of n = Θ(m) boolean points and m boolean axis-parallel boxes B1 , B2 , . . . , Bm such that the following holds. Let A denote the incidence matrix of the collection of set {Bj ∩ P, j ∈ [m]}. Then herdiscC1 (A) = nΩ(1) . By a simple transformation and an approach similar to the proof of Theorem D.4, we derive the following lemma. Lemma D.6. For any m large enough, there exists a set of n = Θ(m) points P and m axis-parallel boxes B1 , B2 , . . . , Bm with a non-empty common intersection such that the following holds. Let A denote the incidence matrix of the collection of set {Bj ∩ P, j ∈ [m]}. Then for α = Ω(1), • if d = O(log n), then discCα (A) = 2Ω(d) ; • if d = Ω(log n), then discCα (A) = nΩ(1) . Proof. Let d = Θ(log n). By Theorem D.5, for any m large enough, there exists a set of n = Θ(m) boolean points ′ P ′ and m boolean axis-parallel boxes B1′ , B2′ , . . . , Bm such that the incidence matrix B′ of {Bj′ ∩ P ′ , j ∈ [m]} has ′ Ω(1) ′ ′ herdiscC1 (B ) = n . Replacing {0} and {1} in B1 , B2′ , . . . , Bm with the intervals [0, 0.5] and [0.5, 1], respectively, yields axis-parallel boxes B1 , B2 , . . . , Bm . This transformation preserves the containment of points within boxes, and thus leaves the incidence matrix B′ unchanged. Furthermore, all resulting boxes Bi contain the common point (0.5, 0.5, . . . , 0.5). Let S ∗ = arg maxS∈[n] discC1 (B′ |S ). Let P be the set of points corresponding to S ∗ , and augment P with additional points not contained in any of the boxes B1 , B2 , . . . , Bm , so that |P | = Θ(m). Let B denote the incidence matrix of {Bj ∩ P, j ∈ [m]}. Then we have discC1 (B) = discC1 (B′ |S ∗ ) = herdiscC1 (B′ ) = nΩ(1) . Then by an approach similar to the proof of Theorem D.4, we can prove that there are infinitely many m × n incidence matrices A of points and axis-parallel boxes with a non-empty common intersection have discrepancy discCα (A) = nΩ(1) . The case for d = Ω(log n) follows immediately from that for d = Θ(log n). We thus focus on the case for d = O(log n). Set n′ = Θ(2d ) so that the above conclusion can be applied to the cases for d = Θ(log n′ ). Let m′ be the number of boxes corresponding to n′ . Then we can add n − n′ points that are not contained in any boxes and m − m′ boxes that do not contain any points. Thus, we finish the proof of the case for d = O(log n). Combining Theorems D.4 and D.6, we complete the proof of Theorem 2.10.

E. Deferred Proofs and Analysis from Section 3 E.1. Proof of Theorem 3.3: The analysis of pure DP algorithm Privacy We now prove that Algorithm 3 is an ε-DP algorithm. Qd Lemma E.1. Let w be the weight vector generated by Algorithm 1. For any discretized query q = i=1 [ℓi , ri ], let Gq be the corresponding induced subgraph. The number of occurrences of H in Gq is equal to the sum of the weights of all rank Qd P tuples falling within the range i=1 ([ℓi , n] × [1, ri ]), i.e., fH (Gq ) = v∈Qd ([ℓi ,n]×[1,ri ]) wv . i=1

Proof. Let H ′ = (V (H ′ ), E(H ′ )) be an occurrence of H in G with rank tuple (si (ui ), si (vi ))di=1 . Then H ′ is in Gq if and only if the ranks of vertices in H ′ satisfy minv∈V (H ′ ) si (v) ≥ ℓi and maxv∈V (H ′ ) si (v) ≤ ri for all i ∈ [d]. The latter is equal to the condition that si (ui ) ≥ ℓi and si (vi ) ≤ ri for all i ∈ [d] by Theorem 3.1. By Algorithm 1, each such occurrence H ′ exactly increases the weight vector w by 1 at the position corresponding to its rank tuple. Therefore, the number of occurrences of H in Gq is equal to the sum of the weights of all rank tuples falling within the range Qd i=1 ([ℓi , n] × [1, ri ]). Lemma E.2. Algorithm 3 is ε-DP. 16

Differentially Private Range Subgraph Counting

Proof. We use w and w′ to denote the different weight vectors formed by two neighboring graphs G and G′ , respectively, where G and G′ differ by a single edge. By fixing H and treating w as a function of G, we can define the global sensitivity of w, denoted as GSw , by Theorem 2.2. Note that for any w, w′ , we have ∥w − w′ ∥1 = | ∥w∥1 − ∥w′ ∥1 |. This follows from the fact that the function w are monotonic, meaning that the addition of any edge does not reduce the number of occurrences of H at each component of w. Thus, we have GSw = max′ ∥w − w′ ∥1 = max′ |∥w∥1 − ∥w′ ∥1 | w,w

w,w

= max

wv −

v∈[n]2d

wv′

(1)

v∈[n]2d

= max′ |fH (G) − fH (G′ )| = GSfH ,

(2)

G∼G

where the penultimate equation follows from Theorem E.1 by setting the discretized query q = [1, n]2d . Let us revisit the individual dimensions of the 2dD range tree in the algorithm. For any (2d − i + 1)D range tree Ti in the 2dD range tree, where 1 ≤ i ≤ 2d, define the depth of each node in Ti as the number of nodes along the path from the root node of Ti to that node. Note that the depth of a node is at most (⌈log n⌉ + 1) by Theorem C.5. We now partition the nodes of the 2dD range tree T1 according to their depths. This partition thus consists of at most (⌈log n⌉ + 1) sets of nodes. For each node in each set, we recursively partition the nodes in its associated (2d − 1)D range tree. That is, in each recursive step, a node in the 2dD range tree is replaced by the nodes of its associated (2d − 1)D range tree. We continue this process until each set consists solely of nodes from 1D range trees. After aggregating the results over 2d dimensions, we obtain a partition consisting of θ sets of nodes with θ ≤ (⌈log n⌉ + 1)2d . For each node set in the partition, we concatenate the weights of the nodes in the set into a weight vector wi , resulting in a collection of weight vectors {wi }θi=1 . Note that for each wi ,P there exists a set Si ⊆ [n]2d associated with the node set, which is independent of the edges in G and satisfies ∥wi ∥1 = v∈Si wv . We can similarly define the global sensitivity of wi as GSwi . Let wi and wi′ be the weight vectors for neighboring graphs G and G′ , respectively. Then we have ∥wi − wi′ ∥1 = | ∥wi ∥1 − ∥wi′ ∥1 | and GSwi = max′ ∥wi − wi′ ∥1 = max′ |∥wi ∥1 − ∥wi′ ∥1 | wi ,wi

= max

wi ,wi

wv −

v∈Si

≤ max

wv′ = max

v∈Si

(wv − wv′ )

v∈Si

(wv − wv′ ) = GSw ,

(3)

v∈[n]2d

where the final inequality follows from the monotonicity of w and the final equation follows from Equation (1). Let wT = (wi )θi=1 denote the weight vector obtained by concatenating all wi . We can similarly define the global sensitivity Pθ of wT as GSwT . Then, we have GSwT ≤ i=1 GSwi ≤ (⌈log n⌉ + 1)2d GSw = (⌈log n⌉ + 1)2d GSfH , where the first two inequalities and the final equation follow from the monotonicity of wi , Equation (3), and Equation (2), respectively. GS

·(⌈log n⌉+1)2d

Therefore, according to the Laplace mechanism (Theorem 2.7), adding Laplace noise with scale fH ε to the e weights of nodes corresponding to each component of wT ensures that T1 achieves differential privacy. For each query, the range tree Te1 are reused. Therefore, Algorithm 3 maintains ε-DP based on the post-processing property (Theorem C.1). Utility we have the following lemma. Lemma E.3. For any ε > 0, the output of Algorithm 3 satisfies max fH (Gq ) − feH (Gq ) = O

GSfH ·

q∈Q

! p log(n|Q|) · log3d n ε

with probability at least 1 − n1 . Here, the hidden constants are of the form cO(d) for some universal constant c > 1. 17

Differentially Private Range Subgraph Counting

Proof. Let Pq = {pi }m i=1 with |Pq | = m denote the set of nodes in the 2dD range tree selected by a query q ∈ Q. Then we have m ≤ ⌈log n⌉2d by Theorem C.9. For any pi ∈ Pq , Let Ypi denote an independent random variable with Ypi ∼ Lap(GSfH · (⌈log n⌉ + 1)2d /ε). Let w(pi ) denote its weight and w(p e i ) denote the weight w(pi ) plus Laplace noise. Then the additive error |fH (Gq ) − feH (Gq )| satisfies ! p m m m 3d X X X GS · log(n|Q|) · log n f H fH (Gq ) − feH (Gq ) = w(pi ) − w(p e i) ≤ Ypi = O ε i=1 i=1 i=1 1 with a probability of at least 1 − n|Q| by Theorem C.2 which b = GSfH · (⌈log n⌉ + 1)2d /ε, m = ⌈log n⌉2d and β = 2n|Q|. By the union bound, we finish the proof.

Combining Theorem E.2 and Theorem E.3, we finish the proof of Theorem 3.3. The complexity analysis of the algorithm in Theorem 3.3 is presented in Section E.3. E.2. Proof of Theorem 1.3: The analysis of approximate DP algorithm (k)

f f (G) be the quantity computed at Step 4 of Algorithm 4. Then, the noisy estimate of LSf (G) is HS f f (G) = Let HS H H H (1)

f f (G). This follows from the fact that f (1) (G) = LSf (G), and the subsequent bias term at Step 4 of Algorithm 4 HS H H H ensures privacy. We have the following lemma from Nguyen et al. (2023). f f (G) is a (mH ε′ , δ ′ + mH eε′ δ ′ )-DP estimate of LSf (G); (2) Lemma E.4 (Nguyen et al. (2023)). It holds that (1) HS H

(k)

f f (G) ≥ f (k) (G)] ≥ 1 − δ ′ , for any k ∈ [mH − 1]. Pr[HS H H We also need the following lemma, the proof of which is based on the proof of Lemma 4.4 in Karwa et al. (2011). We extend the proof there to the case of a family of multidimensional functions so that it can be adapted to the problem we are addressing. Lemma E.5. Let F = {fi }ki=1 be a family of k functions, where fi : X → Rdi and LSF (x) = maxf ∈F LSf (x). Let B be an (ε1 , δ1 )-DP algorithm such that Pr[B(x) ≥ LSF (x)] > 1 − δ2 for all x. Consider the algorithm A that runs B(x) to f x of LSF (x), and releases both LS f x and a noisy estimate of F, i.e., obtain an estimate LS k p f x , fi (x) + Lapdi LS f x · 2 2k ln(1/δ ′ )/ε2 A(x) = LS , i=1

f x = B(x), δ ′ = min(e−ε2 /8 , δ2 ), and Lapdi (b) is a di -dimensional vector such that each element is independently where LS sampled from a Laplace distribution with mean 0 and scale parameter b. Then A is (ε1 +ε2 , max(δ1 +2eε1 δ2 , 2δ2 +eε2 δ1 ))DP. Proof. Given neighboring datasets x and x′ , consider the following algorithms: k p f x , fi (x) + Lapdi LS f x · 2 2k ln(1/δ ′ )/ε2 , A(x) = LS i=1 k p f x′ , fi (x′ ) + Lapdi LS f x′ · 2 2k ln(1/δ ′ )/ε2 A(x′ ) = LS , i=1

f x = B(x), LS f x′ = B(x′ ) and δ ′ = min(e−ε2 /8 , δ2 ). Without loss of generality, assume that LSF (x′ ) ≤ LSF (x). where LS Now, define the random variable k p f x , fi (x′ ) + Lapdi LS f x · 2 2k ln(1/δ ′ )/ε2 Amix = LS . i=1

Let px , px′ and pmix be the probability distributions of A(x), A(x′ ) and Amix , respectively. First, consider the difference f (either B(x′ ) or B(x)). Since B is (ε1 , δ1 )-DP and between A(x′ ) and Amix . They differ only in the initial estimate LS post-processing does not affect differential privacy, it follows that for every event E, px′ (E) ≤ eε1 pmix (E) + δ1 and pmix (E) ≤ eε1 px′ (E) + δ1 . 18

(4)

Differentially Private Range Subgraph Counting

f x ≥ LSF (x). By the precondition of the Then consider the difference between A(x) and Amix . Let F denote the events LS e lemma, Pr[B(x) ≥ LSF (x)] > 1 − δ2 , Pr[F ] > 1 − δ2 . Let X = {e x|x e ∈ X , LSF (e x) ≤ LSF (x)}. Note that x, x′ ∈ Xe. For any x e ∈ Xe and i ∈ [k], conditioned on F , the algorithm p f x · 2 2k ln(1/δ ′ )/ε2 Ai (e x) = fi (e x) + Lapdi LS p over Xe is (ε2 /(2 2k ln(1/δ ′ ))-DP. By applying the advanced composition theorem (Theorem 2.4), the algorithm (Ai (e x))ki=1 is (e ε, δ ′ )-DP, where δ ′ ≤ δ2 and εe = k ·

ε2 ε2 ε2 · + ≤ ε2 . ′ 2 8k ln(1/δ ) 2

It implies pmix (E|F ) ≤ eε2 px (E|F ) + δ2 and px (E|F ) ≤ eε2 pmix (E|F ) + δ2 . Since the probability of F is the same under both pmix and px , we can strengthen this to pmix (E ∩ F ) ≤ eε2 px (E ∩ F ) + δ2 and px (E ∩ F ) ≤ eε2 pmix (E ∩ F ) + δ2 . Note that Pr(F ) ≤ δ2 and thus pmix (E) ≤ pmix (E ∩ F ) + pmix (E ∩ F ) ≤ eε2 px (E ∩ F ) + δ2 + pmix (E ∩ F ) ≤ eε2 px (E) + 2δ2 .

(5)

By symmetry, we can obtain px (E) ≤ eε2 pmix (E) + 2δ2 .

(6)

Plugging the inequalities (4) into (5) and (6), we get px′ (E) ≤ eε1 +ε2 px (E) + 2eε1 δ2 + δ1 and px (E) ≤ eε1 +ε2 px′ (E) + eε2 δ1 + 2δ2 . Hence we prove A is (ε1 + ε2 , max(δ1 + 2eε1 δ2 , 2δ2 + eε2 δ1 ))-DP. Privacy We have the following lemma. Lemma E.6. Algorithm 5 is (ε, δ)-DP. Proof. We continue to use w as the vector output in Algorithm 1. We use w and w′ to denote the different weight vectors formed by neighboring graphs G and G′ , respectively. By fixing H and treating w as a function of G, we can define the local sensitivity of w, denoted as LSw (G), by Theorem 2.1. Then we have LSw (G) = max ∥w − w′ ∥1 = ′max |fH (G) − fH (G′ )| = LSfH (G) ′ ′ w

G :G ∼G

by a proof similar to Theorem E.2. Thus, if we get a noisy estimate of LSfH (G), we get a noisy estimate of LSw (G). Similar to the proof of Theorem E.2, we can obtain a collection of weight vectors {wi }θi=1 with θ ≤ (⌈log n⌉ + 1)2d . Let f f (G) for (mH ε′ , δ ′ + mH eε′ δ ′ )-DP at Step di denote the dimension of wi for all i ∈ [θ]. By Theorem E.4, we can get HS H 3 of Algorithm 5. Then, according to Theorem E.5, if we release  !!θ  p f f (G) · (⌈log n⌉ + 1)d · 2 2 ln(1/δ ′′ ) HS H f f (G), wi + Lapdi , A(G) = HS H ε′ i=1

′

where δ ′′ = min(e−ε /8 , δ ′ ), we can obtain a ((mH + 1)ε′ , max(2emH ε + mH eε + 1, mH e2ε + eε + 2)δ ′ )-DP estimate of ′ ′ ′ ′ w. Here, we set ε = (mH + 1)ε′ and δ = max(2emH ε + mH eε + 1, mH e2ε + eε + 2)δ ′ . Note that Algorithm 5 is actually a post-processing step of A(G). By the post-processing property (Theorem C.1), Algorithm 5 satisfies (ε, δ)-DP. 19

Differentially Private Range Subgraph Counting

Utility we have the following lemma. Lemma E.7. For any ε > 0 and δ ∈ (0, 1), the output of Algorithm 5 satisfies max fH (Gq ) − feH (Gq ) = O

f f (G) · HS H

q∈Q

! p (ε + log(1/δ)) log(n|Q|) · log2d n ε

with probability at least 1 − n1 . Here, the hidden constants are of the form cO(d) for some universal constant c > 1. Proof. Let Pq = {pi }m i=1 with |Pq | = m denote the set of nodes in the 2dD range tree selected by a query q ∈ Q. Then we have m ≤ ⌈log n⌉2d by Theorem C.9. For any pi ∈ Pq , let Ypi denote an independent random variable with p f f (G) · (⌈log n⌉ + 1)d · 2 2 ln(1/δ ′′ )/ε′ ), where ε′ and δ ′′ are defined in Algorithm 5. Let w(pi ) denote Ypi ∼ Lap(HS H its weight and w(p e i ) denote the weight w(pi ) plus Laplace noise. Then the additive error |fH (Gq ) − feH (Gq )| satisfies fH (Gq ) − feH (Gq ) =

m X i=1

w(pi ) −

m X

w(p e i) ≤

i=1

m X

Ypi

i=1

! log(1/δ ′′ ) log(n|Q|) · log2d n ε′ ! p f f (G) · (ε + log(1/δ)) log(n|Q|) · log2d n HS H ε

f f (G) · HS H

1 f f (G) · (⌈log n⌉ + 1)d · with probability at least 1 − n|Q| . The penultimate equation follows from the setting b = HS H p 2 2 ln(1/δ ′′ )/ε′ , m = ⌈log n⌉2d , and β = 2n|Q|, as supported by Theorem C.2. The final equation follows from ′ ′ ′ ′ ′ ε = (mH + 1)ε′ , δ = max(2emH ε + mH eε + 1, mH e2ε + eε + 2)δ ′ and δ ′′ = min(e−ε /8 , δ ′ ) defined in Algorithm 5. By the union bound, we finish the proof.

Combining Theorem E.6 and Theorem E.7, we finish the proof of Theorem 1.3. The complexity analysis of the algorithm in Theorem 1.3 is presented in Section E.3. E.3. The complexity analysis of the algorithms in Theorem 1.3 and Theorem 3.3 The algorithms in Theorem 1.3 and Theorem 3.3 correspond to Algorithm 3 and Algorithm 5, respectively. Before formally presenting the complexity analysis of these algorithms, we first provide the implementation details about the weight vector w and the range tree in these algorithms, which further reduce the time and space consumption both theoretically and in practice. Implementation details In practical networks, fH (G) may be significantly lower than the size of the weight vector w in Algorithm 1 (i.e., n2d ). This implies that most components in the weight vector w are 0. Thus, we maintain the non-zero components of w by a hash map to avoid materializing all of [n]2d and employ a dynamic update strategy to implement the range tree more efficiently. This strategy is based on the observation that the structure of the range tree in Algorithm 2 depends solely on n and d, rather than on the specific structure of G. Moreover, the Laplace noise added to the weight of each tree node is determined before the construction of the range tree in Algorithm 2. Therefore, we can assume that the entire range tree has already been constructed initially, with the weight of each node initialized to 0 and the corresponding Laplace noise added, although this is not actually the case. In other words, each node in the range tree is initially virtual. Then, each non-zero component in w, whose number is bounded by fH (G), is treated as a modification, incrementing the weight of the relevant tree nodes by 1. During this process, if a node is virtual and is about to be modified, it will be instantiated just before the modification. The process of instantiation includes generating the corresponding Laplace noise and setting the tree node’s weight to the noise value. Similarly, for any query, the weights of the relevant tree nodes need to be summed. If a queried tree node is virtual, it will be instantiated just before the query. 20

Differentially Private Range Subgraph Counting

Now we present the complexity analysis of the above algorithms. Let FH (G) denote the time required to list all occurrences of H in G. It is always polynomial since, for any H, all occurrences can be simply enumerated in O(nh ) time. In fact, for some specific H such as a triangle, FH (G) can be improved in sparse graphs (Chiba & Nishizeki, 1985). Theorem E.8. The algorithm in Theorem 3.3 (i.e., Algorithm 3) requires O(min(n2d , (fH (G) + |Q|) log2d n)) space and O(min(fH (G), (dn)2d ) log2d n + FH (G)) preprocessing time, and each query can be answered in O(log2d n) time. Here, the hidden constants are of the form cO(d) for some universal constant c > 1. Proof. We should decide whether to adopt a dynamic update strategy depending on the specific context. If so, the space used by Algorithm 3 actually depends on the number of tree nodes accessed during each modification or query, and this number also bounds the query time (see Theorem C.8). Therefore, Algorithm 3 requires O((fH (G) + |Q|) log2d n) space and O(fH (G) log2d n + FH (G)) preprocessing time by Theorem C.8 since the number of non-zero components of the weight vector w in Algorithm 1 can be bounded by fH (G). Note that querying the same induced subgraph multiple times does not incur additional space; therefore, we retain the previous assumption on Q in Section 1.1. Otherwise, since the number of nodes in a 1D range tree is at most (2n − 1), the maximum number of nodes in the 2dD range tree in Algorithm 1 is (2n − 1)2d , obtained by aggregating the results over the 2d dimensions. Therefore, Algorithm 3 requires O(n2d ) space and O((dn)2d log2d n + FH (G)) preprocessing time by Theorem C.7. Both cases require O(log2d n) query time Theorem C.8. By combining the two cases, the proof is complete. Theorem E.9. The algorithm in Theorem 1.3 (i.e., Algorithm 5) requires O(min(n2d , (fH (G) + |Q|) log2d n)) space and O(n2mH + min(fH (G), (dn)2d ) log2d n + FH (G)) preprocessing time, and each query can be answered in O(log2d n) time. Here, the hidden constants are of the form cO(d) for some universal constant c > 1. f f (G) Proof. The proof is similar to that of Theorem E.8. The only difference is that Algorithm 5 requires preprocessing HS H 2mH f (see Algorithm 4). By Lemma 6 in Nguyen et al. (2023), Algorithm 4 requires O(n ) time to preprocess HSfH (G). It is worth noting that the dynamic update strategy ensures that the above algorithms run in polynomial time for d = O(log n/ log log n). Although the time and space complexity scale exponentially with the dimension and the size of the pattern graph, this limitation reflects the inherent difficulty of range counting and subgraph counting, rather than being specific to our algorithms.

F. Deferred Proofs and Analysis from Section 4 F.1. Proof of Theorem 4.3 Note for each query q ∈ Q, the quantity (AH xH )q denotes the number of occurrences of H in the induced subgraph (G(x))[Vq ], i.e., (AH xH )q = fH ((G(x))[Vq ]).

(7)

For each χ = xH − x′H ∈ Cα,H , let qχ = arg maxq∈Q |(A(x − x′ ))q |. Then we have discCα,H (AH ) = min ∥AH χ∥∞ χ∈Cα,H

= min max |(AH χ)q | ≥ min χ∈Cα,H q∈Q

= =

χ∈Cα,H

(AH χ)qχ

min

(AH xH )qχ − (AH x′H )qχ

min

fH (G(x)) Vqχ − fH (G(x′ )) Vqχ ,

χ∈Cα,H χ=xH −x′H χ∈Cα,H χ=xH −x′H

where the last equation follows from Equation (7) and the others follow from the definitions. For any χ ∈ Cα,H and eχ,x denote the set of private edges in Gχ,x . For any Gχ,x , we x ∈ {0, 1}n , we use Gχ,x to denote (G(x))[Vqχ ] and let E 21

Differentially Private Range Subgraph Counting (i)

partition all occurrences of H in Gχ,x by the number of private edges that they contain. Specifically, let gH (Gχ,x ) denote the number of occurrences of H in Gχ,x containing exactly i private edges. Note that any occurrence of H in Gχ,x can P⌊ h2 ⌋ (i) contain at most h2 private edges. Then we have fH (Gχ,x ) = i=0 gH (Gχ,x ) for any Gχ,x . Therefore, it follows that h

discCα,H (AH ) ≥

We further partition

min

χ∈Cα,H χ=xH −x′H

|fH (Gχ,x ) − fH (Gχ,x′ )| =

P⌊ h2 ⌋

P⌊ h2 ⌋ (i) (i) i=0 gH (Gχ,x ) − i=0 gH (Gχ,x′ )

i=0

min

⌊2⌋ ⌊2⌋ X X (i) (i) gH (Gχ,x ) − gH (Gχ,x′ ) .

χ∈Cα,H χ=xH −x′H i=0

(8)

i=0

in Equation (8) into three parts, .i.e.,

⌊2⌋ ⌊2⌋ X X (i) (i) gH (Gχ,x ) − gH (Gχ,x′ ) h

(1) (1) (0) (0) = gH (Gχ,x ) − gH (Gχ,x′ ) + gH (Gχ,x ) − gH (Gχ,x′ ) +

⌊2⌋ ⌊2⌋ X X (i) (i) gH (Gχ,x ) − gH (Gχ,x′ ) i=2

i=2

 ⌊h 2⌋ X X (i) (i) (1) (1) (0) (0) gH (Gχ,x ) + gH (Gχ,x′ )  ≥ gH (Gχ,x ) − gH (Gχ,x′ ) − gH (Gχ,x ) − gH (Gχ,x′ ) −  

⌊h 2⌋

i=2

:=(I) − (II) − (III), where the last inequality follows from the inequality |a + b + c + d| ≥ |a| − |b| − |c| − |d|. In the following, we denote the above three terms by (I) (II) (III), and we bound them separately. (e)

Term (I) We denote by gH (Gχ,x ) the number of occurrences of H in Gχ,x containing exactly one private edge e ∈ (e) eχ,x . Then we have g (1) (Gχ,x ) = P eχ,x , it holds that E g (Gχ,x ) by definition. Note that for any e1 , e2 ∈ E

H e∈Eχ,x H (e1 ) (e2 ) gH (Gχ,x ) = gH (Gχ,x ) since all private edges are structurally symmetric in Gχ,x . Furthermore, once e is fixed, (e) gH (Gχ,x ) is determined solely by n and |Vqχ |, and is independent of any private information in Gχ,x . Without loss of (e) eχ,x . Observe that g H (n, |Vq |) ≥ GSf as each private edge, generality, let gH (Gχ,x ) = g H (n, |Vqχ |) for any e ∈ E χ H

together with the vertices in W , forms a n-vertex clique (see Figure 2). By combining the above properties, we can derive (1)

(1)

gH (Gχ,x ) − gH (Gχ,x′ ) =

(e)

gH (Gχ,x ) −

e∈Eχ,x

(e)

gH (Gχ,x′ )

e∈Eχ,x′

eχ,x · g H (n, |Vq |) − E eχ,x′ · g H (n, |Vq |) = E χ χ = (Ax)qχ · g H (n, |Vqχ |) − (Ax′ )qχ · g H (n, |Vqχ |) =g H (n, |Vqχ |) · (A(x − x′ ))qχ ≥GSfH · (A(x − x′ ))qχ ,

(9)

eχ,x | = (Ax) by definition. where the third equation follows from |E qχ (0)

Term (II) Observe that for any Gχ,x , the function gH (Gχ,x ) is independent of any private information in Gχ,x . Then it holds that (0)

(0)

gH (Gχ,x ) − gH (Gχ,x′ ) = 0. Term (III) We first prove the following claim. 22

(10)

Differentially Private Range Subgraph Counting (i)

Claim F.1. For any Gχ,x and 2 ≤ i ≤ ⌊ h2 ⌋, we have gH (Gχ,x ) = O(nh−i ). Proof. The number of occurrences of H in Gχ,x that contain exactly i private edges is equivalent to the following procedure: first, select i private edges and fix the 2i endpoints of these edges; then, determine thepositions of the remaining vertices in the occurrences of H. The number of ways to select i private edges is at most ni · miH · i! · 2i = O(ni ), while the number of ways to assign the remaining vertices is at most 3n−2−2i · (h − 2i)! = O(nh−2i ). Therefore, h−2i (i)

gH (Gχ,x ) ≤ O(ni ) · O(nh−2i ) = O(nh−i ). Then by Theorem F.1, we have   h ⌊h ⌊2⌋ ⌊h 2⌋ 2⌋ X X X (i) (i)   gH (Gχ,x ) + gH (Gχ,x′ ) = O(nh−i ) = O(nh−2 ). i=2

i=2

(11)

i=2

Substituting Inequality (9) and Equations (10) and (11) into Equation (8), we obtain discCα,H (AH ) ≥ =

min

GSfH · (A(x − x′ ))qχ − O nh−2

min

GSfH · (A(x − x′ ))qχ

χ∈Cα,H χ=xH −x′H χ∈Cα,H χ=xH −x′H

=GSfH · min (Aχ)qχ − O nh−2 χ∈Cα =GSfH · discCα (A) − O nh−2

− O nh−2

=Ω (GSfH · discCα (A)) . The antepenultimate equation follows from the definitions of Cα and Cα,H ; the penultimate equation follows from the definition of discCα (A); while the last equation follows from discCα (A) = ω(1) and GSfH = Θ(nh−2 ) (see Theorem C.11). F.2. Proof of Theorem 4.1 The following lemma shows a connection between discrepancy and the reconstruction algorithm, which is similar to Lemma 10 in Muthukrishnan & Nikolov (2012). Lemma F.2. For any x ∈ {0, 1}n , there is a deterministic (not necessarily efficient) algorithm A given an output y = M(x) of some mechanism M such that ∥y − AH xH ∥∞ < 21 discCα,H (AH ) satisfies ∥A(y) − x∥1 ≤ αn. Proof. Given y = M(x), the algorithm outputs an vector x′ ∈ {0, 1}n such that ∥y − AH x′H ∥ < 12 discCα,H (AH ). Note that such x′ exists, since x already satisfies the required properties. For the sake of contradiction, we assume that ∥x′ − x∥1 > αn. Then χ = x′H − xH belongs to Cα,H and therefore ∥AH χ∥∞ ≥ discCα,H (AH ). However, by the triangle inequality, we have ∥AH χ∥∞ ≤ ∥AH x′H − y∥∞ + ∥AH xH − y∥∞ < discCα,H (AH ) — a contradiction. We utilize the following lemma, a simplified version of the result in De (2012), as a lower bound for RA. This lemma shows that decoding most of the input from the output violates differential privacy. Lemma F.3 (Lemma 3.9 in Eden et al. (2023)). If B is an (ε, δ)-DP reconstruction algorithm for RA and x is uniformly distributed in {0, 1}N , then we have 1 −ε E[∥B(x) − x∥1 ] ≥ e − δ N, 2 where the expectation is taken over the randomness of both x and B. Finally, we finish the proof of Theorem 4.1. 23

Differentially Private Range Subgraph Counting

Proof of Theorem 4.1. We first establish that η = Ω(logd−1 n̄ · GSfH ) for d = O(1). Let A, AH , G(x), Q denote the corresponding matrices, graph, and query set, respectively, as defined earlier. Then it holds that discCα (A) = Ω(logd−1 n̄) for any constant α. By Theorem 4.3, it follows that discCα,H (AH ) = Ω(logd−1 n̄ · GSfH ). For the sake of contradiction, we assume that there exists an (ε, δ)-DP mechanism M(x) with constants ε > 0 and δ ∈ [0, 12 ) for RSC of (3n − 2)-vertex graph relaxed to protect n private edges, whose additive error is less than 12 discCα,H (AH ) with a sufficiently large constant probability β < 1. We apply M(x) to the instance (G(x), Q). By Theorem F.2, there is a deterministic (not necessarily efficient) algorithm A satisfying ∥A(M(x)) − x∥1 ≤ αn for any x ∈ {0, 1}n . Let B(x) = A(M(x)) denote the reconstruction algorithm for RA. By the post-processing property (Theorem C.1), the algorithm B(x) preserves (ε, δ)-DP. If x is uniformly distributed in {0, 1}n , we have E[∥B(x) − x∥1 ] ≤ (βα + (1 − β))n. We can always choose a sufficiently small constant α > 0 and a sufficiently large constant β < 1 such that E[∥B(x)−x∥1 ] < e−ε ( 21 − δ)n, which yields a contradiction with Theorem F.3. By appropriately rescaling and GSfH = Θ(nh−2 ) (see Theorem C.11), we can obtain the same lower bound for DPRSC of n-vertex graphs. Now consider the case for d = ω(1). The proofs for d = O(log n̄) and d = Ω(log n̄) follow by applying the same techniques as that for d = O(1). F.3. Proof of Theorem 1.4 f f (G(x)) = Θ(GSf ) with a The hard instances in Theorem 1.4 corresponds to the graph G(x). We first prove HS H H ′ f sufficiently large constant probability (1 − β ) < 1. It holds that HSfH (G(x)) = GSfH = 1 if mH = 1. Now we assume that mH ≥ 2. (1)

Note that the graph G(x) contains a n-vertex clique. Thus we have fH (G(x)) = LSfH (G(x)) = Θ(nh−2 ) = Θ(GSfH ) by an analysis similar to the proof of Theorem C.11. Once we determine at least 2 edges of G(x), we have determined at least 3 vertices in G(x). Therefore, based on an analysis similar to the proof of Theorem C.11, we can conclude that (k) fH (G(x)) = O(nh−3 ) for any 2 ≤ k ≤ mH . (k)

′

f f (G(x)) = O(nh−3 ) with probability (1 − (mH −k)β ) for any 2 ≤ k ≤ mH by induction. Then we can prove that HS mH −1 H (k)

(k+1)

f f (G(x)) satisfies the given condition, we can infer that HS ff When HS (G(x)) also satisfies the condition from H H f f (G(x)): Algorithm 4, Theorem 2.6, and the union bound. Finally, using the same approach, we derive the bound for HS H (1) ′ f f (G(x)) = Θ(GSf ) with probability (1 − β ). since f (G(x)) dominates the quantity, we have HS H H f f (G(x))) with n̄ = min(n, |Q|), and then substitute Now for d = O(1), we aim to establish that η = Ω(logd−1 n̄ · HS H |Q| ≥ nc for any sufficiently small constant c > 0. For the sake of contradiction, we assume that there exists an (ε, δ)-DP mechanism M(x) with constants ε > 0 and δ ∈ [0, 12 ) for RSC of (3n − 2)-vertex graph relaxed to protect n private edges, f f (G(x))) with a sufficiently large constant probability γ < 1. whose additive error is o(logd−1 n̄ · HS H By choosing a sufficiently small constant β ′ > 0 and applying the union bound, it holds that M(x) has an additive error less than 12 discCα,H (AH ) = Ω(logd−1 n̄ · GSfH ) with a sufficiently large constant probability β = γ − β ′ < 1. Then a contradiction can be derived through the same proof as Theorem 4.1. By appropriately rescaling, we can obtain the same lower bound for DPRSC of n-vertex graphs. Now consider the case for d = ω(1). The proofs for d = O(log n) and d = Ω(log n) follow by applying the same techniques as that for d = O(1). F.4. A lower bound for the case d = 1 By combining our approach with the method of Dwork et al. (2010), we obtain a lower bound for DPRSC with d = 1. When f f (G)) follows from the following |Q| ≥ nc for any sufficiently small constant c > 0, a similar lower bound Ω(log n · HS H theorem and the proof of Theorem 1.4. Theorem F.4. Let ε > 0 be a constant and δ = n−Ω(1) . For any pattern graph H, let A be an (ε, δ)-DP algorithm for the 24

Differentially Private Range Subgraph Counting

range subgraph counting problem with additive error η = maxq∈Q |fH (Gq ) − feH (Gq )| with probability at least 23 . Then there exist infinitely many n-vertex graphs G = (V, E, a) with 1-dimensional vertex attributes and a corresponding query set Q, such that η = Ω(log n̄ · GSfH ), where n̄ = min(n, |Q|) can be arbitrarily large. Proof. Let P denote a set of n̄ vertices, where the attribute of the i-th vertex is i for all i ∈ [n̄]. Let Q denote a set of n̄ intervals, where the i-th interval is [0, i] for all i ∈ [n̄]. We can always adjust the size of P by adding n − n̄ dummy points lying outside all boxes in Q, or adjust the size of Q by adding |Q| − n̄ dummy intervals not containing any points. Therefore, it suffices to analyze the case for |P | = n and |Q| = n̄. Note that all intervals in Q share a common intersection at 0. We construct an (3n − 2)-vertex graph G(x) based on P and Q as Section 4.1. Assume that δ ∈ [0, n−c ) for some small constant c > 0. Let k = c1 ln n̄ for a constant c1 ∈ (0, min(1,c) ). 2ε Let GSfH denote the global sensitivity of fH on n-vertex graphs. For the sake of contradiction, assume that there exists an (ε, δ)-DP algorithm A for RSC of (3n − 2)-vertex graph relaxed to protect n private edges. The algorithm achieves additive error at most c2 ln n̄ · GSfH with probability at least 32 , where c2 is a constant with c2 ∈ (0, c61 ). Without loss of generality, assume that n̄k is an integer. We sort the n̄ queries in Q by their right endpoints and partition them into n̄k phases, each consisting of k consecutive queries. For the s-th phase, we construct a vector x(s) ∈ {0, 1}n whose coordinates are indexed by r ∈ [n] such that ( 1, if r ∈ [n] ∩ [ks − k + 1, ks]; (s) xr = 0, otherwise. (s)

(s)

Let QL = {[0, r] | r ∈ [n] ∩ [1, ks − k]} and QR = {[0, r] | r ∈ [n] ∩ [ks, n̄]} denote the sets of all queries before and (s) (s) after the s-th phase, respectively. In particular, let qL and qR denote the interval [0, ks − k] and [0, ks], respectively. For any x ∈ {0, 1}n and q ∈ Q, we use Gx,q to denote (G(x))[Vq ] for simplicity. Similar to the proof of Theorem 4.3, for (i) any subgraph G′ of G(x), let gH (G′ ) denote the number of occurrences of H in G′ containing exactly i private edges. (0) For any s ∈ [ n̄k ] and x ∈ {0, 1}n , the output of A(x) matches the s-th phase if feH (Gx,q ) − gH (Gx,q ) < k2 GSfH for all (s) (0) (s) q ∈ QL and feH (Gx,q ) − gH (Gx,q ) ≥ k2 GSfH for all q ∈ QR . Then we have the following claim. Claim F.5. For any s ∈ [ n̄k ] and sufficiently large n̄, the output of A(x(s) ) matches the s-th phase with probability at least 2 3. Proof. By the definition of the algorithm A, we have fH (Gq ) − c2 ln n̄ · GSfH ≤ feH (Gx,q ) ≤ fH (Gq ) + c2 ln n̄ · GSfH for all q ∈ Q with probability at least 32 . (s)

(s)

Then for any s ∈ [ n̄k ] and all q1 ∈ QL , q2 ∈ QR , we have (0) (0) feH Gx(s) ,q2 − gH Gx(s) ,q2 − feH Gx(s) ,q1 − gH Gx(s) ,q1 (0) (0) ≥ fH Gx(s) ,q2 − gH Gx(s) ,q2 − c2 ln n̄ · GSfH − fH Gx(s) ,q1 − gH Gx(s) ,q1 + c2 ln n̄ · GSfH (0) (0) ≥ fH Gx(s) ,q(s) − gH Gx(s) ,q(s) − c2 ln n̄ · GSfH − fH Gx(s) ,q(s) − gH Gx(s) ,q(s) + c2 ln n̄ · GSfH R

⌊h 2⌋

X (i) X (i) gH Gx(s) ,q(s) − gH Gx(s) ,q(s) − 2c2 ln n̄ · GSfH R

i=1

(1) gH

⌊2⌋ X (1) (i) (i) Gx(s) ,q(s) − gH Gx(s) ,q(s) + gH Gx(s) ,q(s) − gH Gx(s) ,q(s) − 2c2 ln n̄ · GSfH R

≥kGSfH − 2c2 ln n̄ · GSfH >

i=2

2 kGSfH , 3 25

Differentially Private Range Subgraph Counting (0)

with probability at least 23 , where the second inequality follows from the monotonicity of fH (Gx(s) ,q ) − gH (Gx(s) ,q ) for P⌊ h2 ⌋ (i) ′ q ∈ Q by definition; the first equation follows from the fact that fH (G′ ) = i=0 gH (G ), and the penultimate inequality follows from an analysis similar to the proof of Theorem 4.3. This completes the proof since k (0) (0) feH (Gx(s) ,q ) − gH (Gx(s) ,q ) ≤ fH (Gx(s) ,q ) − gH (Gx(s) ,q ) + c2 ln n̄ · GSfH < GSfH , 6 k (0) (0) feH (Gx(s) ,q ) − gH (Gx(s) ,q ) ≥ fH (Gx(s) ,q ) − gH (Gx(s) ,q ) − c2 ln n̄ · GSfH > − GSfH 6 (s)

for any q ∈ QL . For any s, t ∈ [ n̄k ], let Es,t denote the event that the output of A(x(s) ) matches the t-th phase. By Theorem F.5, we have Pr[Es,s ] ≥ 32 for any s ∈ [ n̄k ]. By the definition of (ε, δ)-DP, it holds that e−ε (1 − e−2εk ) δ 1 − e−ε 2 1 − n̄−2c1 ε −c > n̄−2c1 ε − n̄ 3 eε − 1 2 n̄−c > n̄−2c1 ε − ε . 3 e −1

Pr[Es,t ] ≥e−2εk Pr[Et,t ] −

⌈ n̄ ⌉

2k for different t are disjoint, yet their total probability Fix an s ∈ [ n̄k ]. This yields a contradiction: the events {Es,2t−1 }t=1 n̄ ⌈ 2k ⌉

Pr[Es,2t−1 ] ≥ 3

t=1

1−c

n̄1−2c1 ε − en̄ε −1 2c1 ln n̄

is more than 1 for sufficiently large n̄. By appropriately rescaling, we can obtain the same lower bound for pure DPRSC of n-vertex graphs.

G. Deferred Experiments from Section 5 G.1. Deferred experiments when H is an edge In this subsection, we present the experimental results when H is an edge. Figures 7 to 10 report the relationship between the relative error and ε, the relationship between the relative error and |Q|, the query time and preprocessing time, and the total time, respectively. For edge counting, Algorithm 4 used in ADP comp and ADP RSC is meaningless since the global sensitivity is 1. In practice, we directly use GSfH = 1 and apply the advanced composition theorem (Theorem 2.4). The baselines require no preprocessing time for similar reasons and compute exact counts of edges using a straightforward implementation in O(m) time. The experimental results obtained are similar to those presented in Section 5.

(a) Wiki-Squirrel

(b) WormNet-v3

Figure 8. Relative error vs. |Q|

Figure 7. Relative error vs. ε

Differentially Private Range Subgraph Counting

(a) Wiki-Squirrel

(b) WormNet-v3

Figure 10. Total time

Figure 9. Query time and preprocessing time

G.2. Deferred experiments when d > 1 We report results for the case d > 1 on the relatively small CA-Netscience dataset in this subsection. Due to the increased computational cost, experiments on larger datasets become prohibitively expensive. We set |Q| = n2 and compare the cases for d = 1, 2 as shown in Figures 11 to 14. These figures show that both the additive error and the runtime of our algorithms increase significantly as d grows, with the observed scaling largely matching our theoretical analysis. While our algorithms no longer outperform the baselines on this dataset when d = 2, the behavior is consistent with our theoretical expectations: although our method improves the asymptotic dependence, its advantage only becomes apparent in regimes where n and |Q| are large. Additionally, we observe that our approximate DP algorithm exhibits a more pronounced advantage over the pure DP algorithm when d = 2, consistent with their different constant factors in the exponent with respect to d in Theorems 1.3 and 3.3. G.3. Deferred experiments for small-range queries p In this subsection, we report results for small-range queries with |Vq | = O( |Q|) on WormNet-v3, and show the additive error with respect to ε in Figure 15. We observe that our algorithms maintain a significant advantage over the baselines on small-range queries. Meanwhile, both the mean and variance of the relative error increase substantially for all methods, due to the reduced magnitude and higher variability of the true answers in this regime. G.4. Deferred implementation details and experiments for real attributes We note that in many real-world applications, attributes often exhibit significant redundancy, with many duplicate values along each dimension. In such cases, the effective domain size per attribute is small, which can, in fact, improve the performance of our algorithms. In contrast, the setting with independently sampled continuous attributes represents a more challenging regime, where the values in each attribute dimension are almost surely all distinct. Thus, the setting used in the main text can be viewed as a conservative (worst-case) evaluation of our algorithms. From a theoretical perspective, this observation can be made precise. The analysis of both the additive error and the time and space complexity can be refined to depend on the effective domain size of each attribute. In particular, the factor logO(d) n Qd can be replaced by ( i=1 (⌈log |Ai (V, a)|⌉ + 1))O(1) , where Ai (V, a) denotes the set of distinct values of the i-th attribute (as defined before Theorem 3.1). This refinement follows from the fact that the rank si (v) in Section 3 naturally takes values in [|Ai (V, a)|] rather than [n]. Consequently, the dependence on log n in the noise parameters of our algorithms can be replaced by (⌈log |Ai (V, a)|⌉ + 1), yielding improved bounds for both the additive error and the time and space complexity. In particular, by a minor adaptation of the proofs of Theorems 1.3 and E.9, we obtain the following corollary. A similar corollary can also be derived from Theorems 3.3 and E.8. Qd Qd Corollary G.1. Let L(V, a) = i=1 (⌈log |Ai (V, a)|⌉ + 1) and M (V, a) = i=1 (2|Ai (V, a)| − 1). For any ε > 0 and δ ∈ (0, 1), there exists a (ε, δ)-DP algorithm that, given a graph G = (V, E, a) with d-dimensional vertex attributes, a fixed pattern graph H, and a query set Q, outputs noisy answers feH (Gq ) which satisfy ! p f f (G) · (ε + log(1/δ)) log(n|Q|) · L2 (V, a) HS H max fH (Gq ) − feH (Gq ) = O q∈Q ε with probability at least 1 − n1 . The algorithm requires O(min(M 2 (V, a), (fH (G) + |Q|)L2 (V, a))) space and O(min(fH (G)L2 (V, a), M 2 (V, a) log2d M 2 (V, a)) + FH (G)) preprocessing time, and each query can be answered in 27

Differentially Private Range Subgraph Counting

(a) CA-Netscience

(b) CA-Netscience

Figure 11. Relative error vs. ε (d = 1)

(a) CA-Netscience

(b) CA-Netscience

Figure 12. Relative error vs. ε (d = 2)

(a) CA-Netscience

(b) CA-Netscience

Figure 13. Query time and preprocessing time (d = 1)

(a) CA-Netscience

(b) CA-Netscience

Figure 14. Query time and preprocessing time (d = 2)

(a) WormNet-v3

(b) WormNet-v3

O(L2 (V, a)) time. Here, the hidden constants are of the form cO(d) for some universal constant c > 1. 28

Differentially Private Range Subgraph Counting

(a) Wiki-Squirrel

(b) Wiki-Squirrel

Figure 16. Relative error vs. ε (real attributes)

(a) Wiki-Squirrel

(b) Wiki-Squirrel

Figure 17. Relative error vs. |Q| (real attributes)

(a) Wiki-Squirrel

(b) Wiki-Squirrel

Figure 18. Query time and preprocessing time (real attributes)

(a) Wiki-Squirrel

(b) Wiki-Squirrel

Figure 19. Total time (real attributes)

Due to the scarcity of suitable real-world graph datasets with attributes aligned with our setting, we conduct experiments on Wiki-Squirrel with real attributes satisfying |A1 (V, a)| = 2002. We present the results in Figures 16 to 19. These figures show that our algorithms remain significantly better than the baselines for real attributes. Moreover, due to the smaller effective domain size, our algorithms achieve substantially improved performance compared to the setting where attributes are independently sampled from a standard normal distribution, which is consistent with our theoretical analysis.

H. Extensions H.1. Randomized response method In this subsection, we show that by using the randomized response, we obtain polynomial-time DP algorithms for range subgraph counting. Let 1k denote the k-bit all-ones vector. Definition H.1 (Randomized Response, Kasiviswanathan et al. (2011); Warner (1965)). Given a privacy parameter ε > 0 29

Differentially Private Range Subgraph Counting

Algorithm 6 UB RR (x, ε)

▷ Unbiased Randomized Response

1: Input: A k-bit vector x and privacy parameter ε. (eε +1)RR(x,ε)−1k . 2: return eε −1

and a k-bit vector v, the algorithm RRε (v) outputs a k-bit vector, where for each i ∈ [k], bit i is vi with probability eεe+1 and 1 − vi otherwise. Lemma H.2. Randomized Response is an ε-DP. We apply a linear transformation to the output of randomized response and obtain an unbiased estimation of the input vector, which is described in Algorithm 6. Our subsequent algorithms mainly rely on the result of Algorithm 6. Lemma H.3. Algorithm 6 is a ε-DP and returns an unbiased estimate of the input vector x. Proof. By Theorem H.2 and the post-processing property (Theorem C.1), Algorithm 6 preserves ε-DP. Let y be the output of Algorithm 6. For each e ∈ E, note that ε xe e (eε + 1) eeε +1 + 1−x eε +1 − 1 (eε + 1)E[e xe ] − 1 E[ye ] = = = xe . eε − 1 eε − 1 That is, y is an unbiased estimate of x. H.1.1. The first bound n Let x ∈ {0, 1}( 2 ) be an indicator vector of E. Let HV be the set of all occurrences of H in the complete graph with vertex set V . For simplicity, we denote by V (H ′ ) and E(H ′ ) the vertex and edge sets of H ′ , respectively. Note that for each query q ∈ Q and the corresponding induced vertex set Vq , we have

fH (Gq ) =

xe .

(12)

H ′ ∈HVq e∈E(H ′ )

In Algorithm 7, we construct the noisy vector y = UB RR(x, ε). And we replace xe in Equation (12) with ye as the output of Algorithm 7. We will make use of the following lemma to analyze Algorithm 7. Definition H.4 (Martingale). A sequence of real-valued random variables Z0 , Z1 , . . . , Zt is a martingale with respect to a sequence of random variables ξ1 , . . . , ξt if for all i ∈ [t], it holds that E[Zi | ξ1 , . . . , ξi−1 ] = Zi−1 . Lemma H.5 (Azuma’s Inequality, Azuma (1967)). Let Z0 , . . . , Zt be a martingale satisfying |Zi − Zi−1 | ≤ ci for any i ∈ [t]. Then for any λ > 0,   −λ2  Pr[|Zt − Z0 | ≥ λ] ≤ 2 exp  P t 2 2 i=1 ci

Theorem H.6. For any ε > 0 , there exists a polynomial-time ε-DP algorithm that, given a graph G = (V, E, a), where the attribute of each vertex is a d-dimensional vector, a pattern graph H, a query set Q, outputs all range subgraph counting queries which satisfy ! p n log(n|Q|)GS f H max fH (Gq ) − feH (Gq ) = O q∈Q εm H with probability at least 1 − n1 . Proof. By Theorem H.3 and the post-processing property (Theorem C.1), the entire algorithm is also ε-DP. Then we analyze the additive error of Algorithm 7. We use A kε to denote the set of all subsets of A with size k. By Theorem H.3, let Ye = ye − xe with E[Ye ] = 0 and |Ye | ≤ eεe−1 ≤ O( 1ε ) for each e ∈ E. Note that for each induced 30

Differentially Private Range Subgraph Counting

Algorithm 7 RR RSC (G, H, Q, ε)

▷ Randomized Response for Range Subgraph Counting

1: Input: An n-vertex graph G = (V, E, a), a pattern graph H, a set of range queries Q, and privacy parameter ε. 2: Let x be an indicator vector of E and y = UB RR(x, ε). 3: for each query q ∈ Q do P Q 4: output feH (Gq ) = H ′ ∈HV e∈E(H ′ ) ye . q

subgraph Gq , we obtain  feH (Gq ) − fH (Gq ) =

(xe + Ye ) −

 H ′ ∈H

 Y

e∈E(H ′ )

mH X X

x e′ ,

e′ ∈E(H ′ )\S

)

i=1 H ′ ∈HVq S∈ E(H ′ ) e∈S

(

x e′

e′ ∈E(H ′ )\S

)

H ′ ∈HVq i=1 S∈ E(H ′ ) e∈S

xe 

e∈E(H ′ )

X (

where the second and third equations follow from the binomial expansion and rearranging the summation order, respectively. For each i ∈ [mH ], define X X Y Y wq,i = Ye x e′ . H ′ ∈HVq S∈ E(H ′ ) e∈S

(

e′ ∈E(H ′ )\S

)

Although wq,i is not a sum of independent random variables, we can still bound it by constructing an edge-exposure n martingale applying Theorem H.5. Fix an arbitrary order of 2 edges in the complete graph with vertex set V , i.e., e1 , e2 , . . . , e(n) . For any j ∈ n2 , let Ej denote the set consisting of the first j edges in this ordering, i.e., Ej = 2

{e1 , e2 , . . . , ej }. Assume that ej = (uj , vj ) and denote by HA,B the set of all occurrences H ′ of H in Kn whose vertex set satisfies A ⊆ V (H ′ ) ⊆ B. Let Xi,0 = 0, and define Xi,j = Xi,j−1 + Yej

H ′ ∈H{uj ,vj },Vq S∈ E(H ′ )\{ej } e∈S

(

i−1

)

x e′ .

e′ ∈E(H ′ )\{ej }\S

Note that Xi,0 , Xi,1 , . . . , Xi,(n) is a martingale satisfying |Xi,j − Xi,j−1 | ≤ O(GSfH /εi ) for any j ∈ 2

E Xi,j | Ye1 , Ye2 , . . . , Yej−1 X =Xi,j−1 + E Yej

H ′ ∈H{uj ,vj },Vq S∈ E(H ′ )\{ej } e∈S

(

i−1

)

x e′

e′ ∈E(H ′ )\S

=Xi,j−1 , and we have Xi,(n) = wq,i . By applying Theorem H.5, with probability at least 1 − nmH1 |Q| , we have 2

Xi,(n) − Xi,0 = |wq,i | ≤ O 2

! p n log(n|Q|)GSfH . εi

n 2

since

Differentially Private Range Subgraph Counting

Then, by the union bound, it holds that max fH (Gq ) − feH (Gq ) ≤ max q∈Q

q∈Q

mH X

wq,i ≤ max

i=1 mH X

q∈Q

mH X

|wq,i |

i=1

log(n|Q|)GSfH ≤ max O q∈Q εi i=1 ! p n log(n|Q|)GSfH =O εmH

with probability at least 1 − n1 . H.1.2. The second bound o(1)

For moderate |Q| (i.e., |Q| = 2n ), we extend the methods in Eden et al. (2023) and obtain an instance-dependent error for the private range subgraph counting problem. We sketch the analysis in this subsection and present the entire algorithm in Algorithm 8. Algorithm 8 RR IE (G, H, Q, ε)

▷ Randomized Response with Instance-dependent Error

1: Input: An n-vertex graph G = (V, E, a), a pattern graph H, a set of range queries Q, and privacy parameter ε. 2: Let t = ⌈18 ln(n|Q|)⌉. 3: Let x be an indicator vector of E and y(1) , y(2) , . . . , y(t) be t independent outputs of UB RR(x, εt ). 4: for each query q ∈ Q do 5: 6:

P Q (i) Initialize ze(i) = H ′ ∈HV e∈E(H ′ ) ye for any i ∈ [t]. q Output feH (Gq ) = mediani∈[t] ze(i) .

For any two sets A and B, define their symmetric difference as A△B = (A\B)∪(B \A). Given two graphs G1 = (V1 , E1 ) and G2 = (V2 , E2 ), their symmetric difference is defined as G1 △G2 = (V1 ∪ V2 , E1 △E2 ). We write G1 ∼ = G2 if graphs (i) G1 and G2 are isomorphic. For a fixed graph H and an integer i ∈ [mH ], let GH denote the class of graphs that can be obtained as the symmetric difference of two isomorphic copies H1 , H2 of H whose edge sets intersect in exactly i edges, (i) i.e., GH = { H1 △H2 | H1 , H2 ∼ = H, |E(H1 ) ∩ E(H2 )| = i }. Then we have the following theorem. Theorem H.7. For any ε > 0 , there exists a polynomial-time ε-DP algorithm that, given a graph G = (V, E, a), where the attribute of each vertex is a d-dimensional vector (d = no(1) ), a pattern graph H, a query set Q, outputs all range subgraph counting queries which satisfy   H −1 τ mH h mX X p i τ   max fH (Gq ) − feH (Gq ) = O  n2 + fH ′ (G) q∈Q ε ε (i) i=1 H ′ ∈GH

with probability at least 1 − n1 , where τ = log(n|Q|) ≤ O(d log n). Proof. We begin by analyzing the privacy guarantees of Algorithm 8. Let ε′ = εt . By Theorem H.3, releasing y (i) preserves ε′ -DP for each i ∈ [t]. By the basic composition theorem (Theorem 2.3), the entire algorithm preserves ε-DP. Now we analyze the additive error of Algorithm 8. We have the following claim. Claim H.8. For any q ∈ Q and i ∈ [t], we have  h 2

 n ze(i) − fH (Gq ) = O  ′mH + ε with probability at least 32 . 32

mX H −1 i=1

 1 ε′i

X p (i)

H ′ ∈GH

 fH ′ (G)

Differentially Private Range Subgraph Counting ′

′

e(i) = RR(x, ε′ ) and y(i) = ((eε + 1)e Proof. Fix any i ∈ [t] and q ∈ Q. Let x x(i) − 1(n) )/(eε − 1). For any e ∈ E, we 2 have ′ ′ i (eε′ + 1)2 h h i (eε′ + 1)2 eε eε 1 (i) = Var x e = = O Var ye(i) = ε′ , e (e − 1)2 (eε′ − 1)2 (eε′ + 1)2 (eε′ − 1)2 ε′2 since x ee is a Bernoulli variable. By Theorem H.3, it follows that E (i)

Let zH ′ =

ye(i)

h i h i2 1 1 (i) (i) 2 = Var ye + E ye =O + xe = O . 2 ′ ε ε′ 2

(13)

Q (i) (i) (i) eH ′ = e∈E(H ′ ) ye for any fixed occurrence H ′ . Thus, e∈E(H ′ ) xe and z

h i (i) E zeH ′ =

h i E ye(i) =

Y e∈E(H ′ )

(i)

x(i) e = zH ′ .

e∈E(H ′ )

Then we have h i h i 2 2 (i) (i) (i) Var zeH ′ = E zeH ′ − E zeH ′ =

ye(i)

(i) − zH ′ = O

e∈E(H ′ )

1 ε′2mH

(14)

Combining the above results, we obtain h i h i X (i) Var ze(i) = Var zeH ′ +

H ′ ∈HVq

H1 ,H2 ∈HVq

h i (i) Var zeH ′ +

= ≤

H1 ,H2 ∈HVq

h i (i) Var zeH ′ +

H1 ,H2 ∈HVq

fH (Gq ) ε′2mH nh

i h (i) (i) E zeH1 zeH2

H ′ ∈HVq

ii i h h h (i) (i) (i) (i) zeH2 − E zeH2 zeH1 − E zeH1

h i (i) (i) (i) (i) E zeH1 zeH2 − zH1 zH2

H ′ ∈HVq

ε′2mH

h i E ye(i)

H1 ,H2 ∈HVq e∈E(H1 )△E(H2 )

 h

 n =O  ′2mH + ε

mX H −1

i=1

mX H −1 i=1

1 ε′2i

(i) ye′

e′ ∈E(H1 )∩E(H2 )

H1 ,H2 ∈HVq e∈E(H1 )△E(H2 ) |E(H1 )∩E(H2 )|=i

 1 ε′2i

 fH ′ (G) .

(i)

H ′ ∈GH

The antepenultimate equation follows from Equation (14); the penultimate equation follows from Theorem C.12 and EquaP (i) (i) tion (13); while the last equation follows from the definition of GH . Note that E[e z (i) ] = H ′ ∈HV E[e zH ′ ] = fH (Gq ). By q Chebyshev’s Inequality, we finish the proof. By applying the standard median trick and setting the number of copies t = Θ(log(n|Q|)), we can amplify the success 1 probability to n|Q| without increasing the additive error. This completes the proof by the union bound. p P i+1 3−i (i) By Theorem C.11 and Theorem C.12, we have H ′ ∈G (i) fH ′ (G) = O(nh− 2 ) = O(n 2 GSfH ) since any H ′ ∈ GH H has at most (2h − i − 1) vertices for all i ∈ [mH − 1]. Thus, Theorem H.7 does not have a stronger dependence on n than Theorem Theorem H.6 for moderate d up to a factor of poly log n. We denote K1,k by a k-star and Ck by a k-cycle. Table 4 summarizes the additive error of Algorithm 8 for some common pattern graphs. 33

Differentially Private Range Subgraph Counting Table 4. The additive error of Algorithm 8 for some common pattern graphs H

Pattern Graph Triangle 3-Star 4-Cycle

Additive Error p 3 O ( τε )3 n 2 + τε fC4 (G) p p O (τε )3 n2 + τε nfK1,4 (G) + ( τε )2 n fK1,2 (G) p p O ( τε )4 n2 + τε fC6 (G) + ( τε )2 nfC4 (G)

H.2. The lower bound for sufficiently large d In this subsection, we extend the methods in Eliáš et al. (2020) to prove the lower bound for d ≥ n/2. For convenience, we reuse the notations x, xH , AH to denote the analogous vectors and matrix defined on n-vertex graphs. Their meanings here are independent of those in Section 4. n We consider an n-vertex graph G = (V, E) and a query set Q. Let x ∈ {0, 1}( 2 ) be an indicator vector of E. Let xH = fH (x) ∈ {0, 1}fH (Kn ) be an indicator vector, where each coordinate corresponds to an occurrence H ′ = (V ′ , E ′ ) of ′ H in the complete Q graph Kn with vertex set V , and the entry is 1 if all edges of H are present in G, and 0 otherwise, i.e., ′ (fH (x))H = e∈E ′ xe . We construct a matrix AH with |Q| rows, each corresponding to an induced subgraph Kn [Vq ] for a query q ∈ Q, and fH (Kn ) columns, each corresponding to an occurrence H ′ of H in Kn , such that

( (AH )q,H ′ =

1, if E(H ′ ) ⊆ E(Kn [Vq ]); 0, otherwise.

Note that AH is fixed and does not depend on the edge set of G. For each query q ∈ Q, the quantity (AH xH )q denotes the number of occurrences of H in the induced subgraph G[Vq ]. If the dimension d of the vertex attributes is at least n/2, we can set the i-th coordinate of the attributes of the (2i − 1)-th and (2i)-th vertices to −1 and 1, respectively, and set all other coordinates to 0 for all 1 ≤ i ≤ ⌈n/2⌉; then, by choosing the interval for the i-th dimension in a query to include −1 (resp. 1) or not, we can determine whether the (2i − 1)-th (resp. (2i)-th) vertex is included in the queried vertex set. Therefore, when d ≥ n/2, we can always construct the attributes of each vertex so that it is possible to query the induced subgraph of any subset of vertices. Hence there are 2n rows in the matrix AH . We use the following lemma to show that AH satisfies the following discrepancy property. Lemma H.9 (Lemma 6 in Bollobás & Scott (2006)). Let {ai , 1 ≤ i ≤ n} be a sequence of real numbers. Let ρi ∈ {0, 1} be i.i.d. Bernoulli( 21 ), for 1 ≤ i ≤ n. Then " E

n X i=1

# ρi ai

Pn i=1 |ai | ≥ √ . 8n

Lemma H.10. Let γ ∈ (0, 12 ] and σ ∈ [0, 1]. Let Cσ,γ be the set of all vectors χ = xH − x′H , where x and x′ are the indicator vectors of edges of graphs, denoted by G = (V, E) and G′ = (V, E ′ ), respectively, such that 1. ∥x − x′ ∥1 ≥ σγn2 ; 2. for each vertex v ∈ V , its degree lies in the interval [ γn 2 , 2γn]; 3. for each edge e ∈ E ∪ E ′ , the number of occurrences of H containing e lies in the interval [ √ Then for the matrix AH defined above, we have discCσ,γ (AH ) = Ω σn γ · LSfH (G) .

LSfH (G) , 2LSfH (G)]. 2

Proof. In the complete graph Kn with vertex set V , we denote by HA,B the set of all occurrences H ′ of H whose vertex set satisfies A ⊆ V (H ′ ) ⊆ B. Let V ′ ⊆ V be a random subset such that for each v ∈ V , the indicator variable ρv = 1v∈V ′ is i.i.d. Bernoulli( 21 ). For any given v ∈ V , denote N (v) the set of vertices adjacent to v by edges whose color is non-zero, i.e., N (v) = {w | (v, w) ∈ 34

Differentially Private Range Subgraph Counting

E△E ′ }. Not that |N (v)| ≤ 4γn. Let dH ′ (v) denote the degree of v in an occurrence H ′ , and we have   X χH ′  discCσ,γ (AH ) = min ∥AH χ∥∞ ≥ min E  χ∈Cσ,γ

χ∈Cσ,γ

H ′ ∈H∅,V ′



 = min

1  E

χ∈Cσ,γ h

ρv

v∈V

χH ′ 

H ′ ∈H{v},V ′





1 √ χH ′  E 8n v∈V H ′ ∈H{v},V ′   X X 1 X  χH ′  = min √ ρw E χ∈Cσ,γ h 8n dH ′ (v) v∈V H ′ ∈H{v,w},V ′ w∈N (v)∩V   X X ′ χ 1 H , ≥ min E √ χ∈Cσ,γ 16hn γ dH ′ (v) ′ ′ ≥ min

χ∈Cσ,γ h

(15)

H ∈H{v,w},V ′

(v,w)∈E△E

where the factor 1/h (resp. 1/dH ′ (v)) compensates for the fact that each χH ′ is counted h (resp. dH ′ (v)) times in the sum. The last and penultimate inequalities follow from Theorem H.9. Now, by our assumption on the properties of the graphs G and G′ , for each edge (u, v) ∈ E△E ′ , it holds that the occurrences LS (G) H ′ containing (u, v) are either in G or in G′ , but not both; and each edge belongs to at least fH2 occurrences of H. Therefore, we obtain   X X ′ χH ′ χ H = E E dH ′ (v) dH ′ (v) ′ ′ H ∈H{v,w},V ′

H ∈H{v,w},V ′

≥

1 h

Pr[H ′ ∈ V ′ ]

H ′ ∈H{v,w},V

|H{v,w},V | LSfH (G) ≥ , h−2 h2 h2h−1

(16)

where the penultimate inequality follows from the fact dH ′ (v) ≤ h. Substituting Equation (16) into Equation (15), we have discCσ,γ (AH ) ≥

LSfH (G) · |E△E ′ | LSfH (G) · σγn2 √ ≥ √ √ = Ω (σn γ · LSfH (G)) . 16h2 2h−1 n γ 16h2 2h−1 n γ

Let G(n, p) denote the distribution of Erdős–Rényi random graphs. For any graph G = (V, E) ∼ G(n, p), we use the following lemma to bound the number of occurrences of H in G containing each edge e ∈ E. 1/(2mH −2)

Lemma H.11. Let G = (V, E) be a graph generated from G(n, p). If p ≫ ((ln n)/n) mH = 1), with probability at least 1 − poly(1/n), the following properties (⋆) hold:

or H is an edge (i.e.,

1. for each vertex v ∈ V , its degree belongs to the interval [ γn 2 , 2γn]; 2. for each e ∈ E, the number of occurrences of H containing e belongs to the interval [ LSfH (G) = Θ(GSfH · pmH −1 ).

LSfH (G) , 2LSfH (G)] and 2

Proof. Item 1 in the properties (⋆) follows from the Chernoff bound. We now focus on Item 2. Note that when h = 2 and mH = 1 (i.e., H is an edge), it holds automatically since LSfH (G) = 1. Therefore, we assume h ≥ 3 and mH ≥ 2 in the following. Fix an edge e ∈ E. Let Xe denote the number of occurrences of H containing e in G. Fix an arbitrary 35

Differentially Private Range Subgraph Counting

ordering of the edges in {(u, v) | u, v ∈ V } \ {e}, denoted by e1 , e2 , . . . , e(n)−1 , and define the indicator random variable 2 Yi = 1ei ∈E for each i ∈ [ n2 − 1]. Let Z0 = E[Xe ] = GSfH · pmH −1 . For each i ∈ [ n2 − 1], let Zi = E[Xe |Y1 , . . . , Yi ]. Then Z(n)−1 = Xe and Z0 , . . . , Z(n)−1 is a martingale by the law of total expectation. 2

By an analysis similar to the proof of Theorem C.11, for each edge ei , if it shares an endpoint with e, then |Zi − Zi−1 | ≤ Θ(nh−3 ); otherwise, |Zi − Zi−1 | ≤ Θ(nh−4 ). By Theorem C.11 and Theorem H.5, if p ≫ ((ln n)/n)1/(2mH −2) , there exists a constant C > 0 such that    (ε · GSfH · pmH −1 )2  C · n2h−4 · p2mH −2   exp −  ≤ exp − 2n · n2h−6 + n2 · n2h−8 ≤ poly(1/n). P(n2 )−1 2 2 c i i=1 Then with probability at least 1 − poly(1/n), Xe belongs to the interval [(1 − ε)GSfH · pmH −1 , (1 + ε)GSfH · pmH −1 ] for some ε > 0. Note that LSfH (G) = maxe∈E Xe . By the union bound and choosing a suitable constant ε > 0, it holds that with LS (G) probability at least1 − poly(1/n), all the random variables Xe lie in the interval [ fH2 , 2LSfH (G)] and LSfH (G) = Θ GSfH · pmH −1 . By the union bound, with probability at least 1 − poly(1/n), the properties (⋆) are satisfied. The remaining proof largely follows directly from Eliáš et al. (2020), and we only need to make slight adjustments to adapt their proofs for our case. We sketch the proofs here for the sake of completeness. By an analysis similar to the proof of Theorem F.2, we obtain the following lemma. Lemma H.12. Let x be the indicator vector of the edge set of some graph G satisfying the properties (⋆) in Theorem H.11. There is a deterministic algorithm A given an output y = M(x) of some mechanism M such that ∥y − AH xH ∥∞ < 1 2 2 discCσ,γ (AH ) satisfies ∥A(y) − x∥1 ≤ σγn . The following lemmas on differential privacy will be useful in the subsequent proof. Lemma H.13 (Lemma 5.4 in Eliáš et al. (2020)). Let M be an (ε, δ)-differentially private mechanism and let Y be the probability distribution over the transcripts of M(x), where x is drawn from distribution X. Then for any γ > 0 and y ∼ Y , it holds that with probability 1 − δ ′ over i ∈ [n] and x ← X|Y =y , we have 2−ε−γ

Prx←X|Y =y [xi = 0 | x−i ] 1−p 1−p ≤ ≤ 2ε+γ , p Prx←X|Y =y [xi = 1 | x−i ] p −ε−γ

where x−i denotes the vector of all coordinates of x excluding xi and δ ′ = 2δ · 1+e 1−e−γ . Lemma H.14 (Lemma 2.1.2 in Bun (2016)). Let M : X → R be an (ε, δ)-differentially private mechanism, c ∈ N, and x, x′ ∈ X such that ∥x − x′ ∥1 ≤ c. Then, for every S ⊆ R, we have Pr[M(x) ∈ S] ≤ ecε Pr[M(x′ ) ∈ S] +

ecε − 1 δ. eε − 1

Now we prove the lower bound for ε = 1. Lemma H.15. Let G ∼ G(n, p), where p ∈ (0, 12 ], be a random graph. And we assume p ≫ ((ln n)/n)1/(2mH −2) unless H is an edge. Let M be a (1, δ)-DP mechanism that answers all range subgraph counting queries up to additive error α with probability β. Then α ≥ Ω(discCσ,γ (AH )), where γ = p, σ = Ω(1 − 9δ β ). −ε−10

Proof Sketch. We choose ε = 1 and ε′ = ε + 10. By Theorem H.13, this implies δ ′ = 2δ · 1+e 1−e−10 ≤ 3δ, then with probability 1 − δ ′ over i ∈ [n] and x ← X|Y =y , we have 2−ε

′

Prx←X|Y =y [xi = 0 | x−i ] ′ 1 − p 1−p ≤ ≤ 2ε . p Prx←X|Y =y [xi = 1 | x−i ] p 36

(17)

Differentially Private Range Subgraph Counting

Then we can prove the lemma by contradiction. That is, we assume that M has an additive error smaller than 12 discCσ,γ (AH ) with probability at least β. Then we can show that for each possible output y of the mechanism M, with probability greater than δ ′ , Equation (17) is violated. To do so, we only need to show that 1) with high probability, x is good in the sense that it satisfies the desired properties; and 2) conditioned on the event that x is good, the inequality (17) is violated with probability ′ ′ greater than δ ′ , if we set γ = p and σ = 2−ε −3 · (1 − 3δβ ), which leads to a contradiction. Part 2) follows from the same argument as those in the proof of Lemma 5.3 in (Eliáš et al., 2020). For part 1), we describe our changes. Formally, we define that x ∼ X|Y =y is good if ∥AH xH − y∥∞ < 12 discCσ,γ (AH ) and the properties (⋆) given in the statement of Theorem H.11 are satisfied. Note that the probability that x ∼ X|Y =y is good is at least (1 − poly(1/n)) · β by Theorem H.11. This then finishes the proof of the lemma. Finally, we finish the proof of the lower bound for d ≥ n/2. Theorem H.16. Let M be an (ε, δ)-DP mechanism and G ∼ G(n, p), where p ∈ (0, 21 ]. And we assume p ≫ ((ln n)/n)1/(2mH −2) unless H is an edge. If M answers all d-dimensional √ (d ≥ n/2) range subgraph counting queries 9δ about G up to an additive error α with probability at least β, then α = Ω( m(1 − c) · LSfH (G)), where c = ee−1 ε −1 β . √ √ Proof. Note that m = Θ(γn2 ). Then Θ(n γ) = Θ( m). Theorem H.15 together with Theorem H.10 imply that there is √ no (1, δ)-DP mechanism M whose error with probability at least β is below o( m(1 − 9δ β ) · LSfH (G)). √ Let us assume for contradiction, that there is an (ε, δ)-DP mechanism M(x) whose error is smaller than o( m(1 − c) · 9δ x −mH LSfH (G)) with probability β, where c = ee−1 fH (x). Let us consider a mechanism ε −1 · β . Note that fH ( ε ) = ε x e−1 mH ε M( ε ). By Theorem H.14, it is (1, eε −1 δ)-DP. Moreover, it has error ε

√ ·o

√ (1 − c) · LSfH (G) ≤ o m(1 − c) · LSfH (G) mH m

with probability at least β — a contradiction. When the parameters p, ε, δ in Theorem H.16 are constants, we show that any (ε, δ)-DP algorithm incurs an additive error of Ω(nGSfH ) by Theorem H.11.

Record · ID 267594 · SHA-256 351293e30547a724
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.