arXiv CS open access

Subgraph Counting with Local Node Differential Privacy

Sofya Raskhodnikova et al. · arxiv_cs

arXiv CS · Papers

We study the problem of approximately counting subgraphs under local node differential privacy (LNDP), a recently introduced model that enforces strong privacy guarantees in analyses of distributed social networks. We design a noninteractive $(\varepsilon,0)$-LNDP algorithm that, given any public $k

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Subgraph Counting with Local Node Differential Privacy∗ Sofya Raskhodnikova†

Adam Smith†

Connor Wagaman†

Anatoly Zavyalov†

arXiv:2610.22278v1 [cs.DS] 15 Oct 2026

October 15, 2026

Abstract We study the problem of approximately counting subgraphs under local node differential privacy (LNDP), a recently introduced model that enforces strong privacy guarantees in analyses of distributed social networks. We design a noninteractive (ε, 0)LNDP algorithm that, given any public k-node template graph H, counts occurrences 1 of H in a sensitive undirected n-node graph with additive error O(nk− 2 /εk−1 ), for any constant k. We complement this algorithm with a lower bound showing that every noninteractive (ε, δ)-LNDP algorithm for counting copies of any k-node template graph 1 with maximum degree greater than 1 must have error Ω(nk− 2 ). Thus, our algorithm achieves optimal error for counting constant-size subgraphs, up to poly(1/ε) factors. Our results substantially expand the types of network statistics known to be approximable under LNDP: prior work considered only functions of the degree distribution. In addition, our lower bound yields the first known poly(n) gap between central and local node differential privacy when accuracy is required for all input graphs. Previous separations either only involved poly(1/ε) factors or only applied to promise problems.

∗ †

To appear at the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2027. Boston University, {sofya,ads22,wagaman,zavyalov}@bu.edu.

Contents 1 Introduction 1.1 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Our Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Algorithm for Subgraph Counting . . . . . . . . . . . . . . . . . . . . 1.2.2 Lower Bound for Subgraph Counting . . . . . . . . . . . . . . . . . . 1.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 4 5 6 6 9 10

2 Preliminaries 2.1 Local Node Differential Privacy . . . . . . . . . . . . . . . . . . . . . . . . .

10 10

3 Algorithm for Subgraph Counting with LNDP⋆

4 Error Required for Subgraph Counting with LNDP⋆ 4.1 Inner Product Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Query Graphs and Their Properties . . . . . . . . . . . . . . . . . . . . . . . 4.3 Reduction from Inner Product Queries to Subgraph Counting . . . . . . . .

15 16 17 18

References

Appendix

A Background on Differential Privacy

B Error Required for Private Inner Product Queries

Introduction

Graphs are a natural representation for sensitive relational data: social networks, contact networks, and networks of sexual relationships all encode information about interactions between individuals. Such sensitive graphs are often distributed, with each node knowing only its own connections and no central authority holding the whole graph. Accurate aggregate information about these datasets is highly valuable—for example, to epidemiologists seeking to understand the spread of an illness, big tech companies working to improve a messaging platform, and governments implementing public health efforts. However, these benefits come with serious privacy risks: releasing the graph structure directly can reveal sensitive relationships between individuals [BDK07]; moreover, even releasing aggregate summaries of graph structure can leak private information about the individuals and relationships represented in the graph [JM09]. Differential privacy (DP) [DMNS16] provides a widely used framework for reasoning about how to balance these privacy and accuracy concerns. The local model of differential privacy [EGS03; KLNRS11] adapts this framework to a decentralized setting where each party randomizes its own data before sharing it. The noisy data can then be aggregated by an untrusted server without any impact on the privacy guarantees. This approach’s convenience and explainability, among other factors, have led to industry deployments of the local model [EPK14; BEM+17; DKY17; App23] and extensive theoretical study (see Section 1.3). When working with graph data, there are two natural privacy notions. Edge privacy roughly hides the existence of a particular edge, while node privacy roughly hides a node’s entire edge set. Both are well-motivated: edge differential privacy (which has been studied extensively in the local model under the name LEDP—see Section 1.3) makes sense when individuals corresponds to edges, whereas node privacy is well-suited to settings where individuals map to nodes whose entire neighborhoods are sensitive, as in networks of disease transmissions or sexual relationships [HNGKTS26]. For the latter, edge privacy still allows an analyst to approximate each node’s number of partners, while node privacy hides the count entirely. The dual considerations of node privacy and decentralization motivate the recently introduced local node differential privacy (LNDP) [RSWZ26]. In the noninteractive LNDP setting, denoted LNDP⋆ , each node runs a local randomizer on its edge list using both public and local randomness, and then releases the output. As formalized in Definition 2.6, an algorithm is (ε, δ)-LNDP⋆ if the randomizers’ joint output distribution is (ε, δ)-indistinguishable for every pair of node-neighboring input graphs. (Two graphs are node neighbors if one can be obtained from the other by rewiring a single node, that is, changing its edge set arbitrarily.) While [RSWZ26] also present an interactive formulation, their work focuses on the noninteractive setting; this focus mirrors standard local DP, where all industry deployments and almost all theoretical work are noninteractive. They study the error required for estimating functions of a graph’s degree distribution but leave estimating other functions of the input graph, such as subgraph counts, open. We study subgraph counting under LNDP⋆ . Given a template graph H and an input graph G, the goal is to count the number of copies of H in G. Subgraph counts are among 3

Privacy guarantee Central model

Edge DP

Node DP

Θε,δ nk−1

Θε,δ nk−2 [NRS07]

Noninteractive local model

Θε,δ n

k−1 †

[ELRS25; SPHH25]

[KNRS13; CZ13]

1 Θε,δ nk− 2 Our work

Table 1: Additive error for counting noninduced k-node subgraphs in n-node graphs for fixed k. All algorithms are (ε, 0)-DP in the respective models, and lower bounds hold for ε ≤ 1 1 and δ ≤ 1000 . The notation Θε,δ (·) hides dependence on privacy parameters ε, δ. † LEDP lower bounds are only known for cliques and cycles, not general subgraphs. Interactive LEDP algorithms for subgraph counting have the same worst-case dependence on n (but, in some cases, better dependence on ε) [IMC21; HSS25]. the most fundamental graph statistics. They measure the frequency of small structural patterns, such as triangles, paths, stars, and cliques, and are widely used in network analysis as summaries of local connectivity and higher-order structure. For example, triangle counts are closely related to clustering coefficients and community structure, stars capture degree heterogeneity, and counts of larger motifs are used to identify functional organization in social, biological, and communication networks [WS98; MSIKCA02; BGL16]. On a theoretical level, subgraph counts characterize graph limits and the graphon statistical model (e.g., [Lov12]). At the same time, subgraph counts are particularly challenging under node privacy. Changing the edges incident to one node can create or destroy many copies of a small pattern (e.g., rewiring a single node can change the number of instances of a k-node subgraph by Θ(nk−1 )). Moreover, in the local model no party can directly inspect the global structure of the graph to find these copies.

1.1

Our Results

We study the additive error required for counting the number of occurrences of a k-node template graph H in an undirected n-node graph under LNDP⋆ . Our results are summarized in Table 1. Let #H(G) denote the number of noninduced,1 unlabeled copies of H in G (Definition 2.1). We give an LNDP⋆ algorithm for computing #H(G) with the following error guarantee. (As is standard, the notation Ok (·) indicates that the suppressed constant may depend on k.) Theorem 1.1 (Algorithm for subgraph counting; Theorem 3.1, informal). Fix integer k ∈ N, k-node template graph H, and ε ∈ (0, 1]. Let VC(H) denote the size of the minimum vertex 1

Our algorithm can be easily adapted to instead count induced subgraphs, with the same Ok (nk− 2 /εk−1 ) error guarantee.

cover of H. There is an (ε, 0)-LNDP⋆ algorithm Asub that, for all n-node input graphs G, counts copies of H in G with additive error ! ! 1 1 nk− 2 nk− 2 E Asub (G) − #H(G) = Ok VC(H) = Ok . ε εk−1 Note that VC(H) is between 1 and k − 1, depending on the template graph H, giving the last equality. Since the subgraph count #H(G) can be as large as Ω(nk ), our algorithm has additive error that, for dense graphs, is vanishing on the scale of the statistic being approximated. Our algorithms greatly expand the types of network statistics known to be approximable under LNDP: prior work [RSWZ26] considered only functions of the degree distribution. The only connected subgraphs whose counts fall into that category are k-stars; the counts of k-cliques, k-cycles, and other interesting subgraphs require the simultaneous consideration of several nodes. In Section 4, we show this additive error is optimal for constant k, up to poly(1/ε) factors. 1 Theorem 1.2 (Error required for subgraph counting). For every ε ∈ (0, 1], δ ∈ [0, 200 ], template graph H on k ∈ N nodes with maximum degree greater than 1, and sufficiently large n ∈ N, if A is (ε, δ)-LNDP⋆ and E A(G) − #H(G) ≤ α(n) for every n-node graph G, 1 then α(n) = Ωk nk− 2 .

In combination, Theorems 1.1 and 1.2 pin down the dependence on n in the error of LNDP⋆ 1 algorithms for estimating counts of a k-node template graph to Θk (nk− 2 ). Interestingly, while a factor of n separates subgraph counting under the central and local variants of edge √ DP, there is only a n gap between the accuracies achievable under central and local node DP—see Table 1. Previously, the only bounds for subgraph counting in the local model were for LEDP [ELRS25; SPHH25]; generalizing the techniques used in those works only yields trivial bounds for our setting. LEDP lower bounds are only known for restricted classes of subgraphs, namely cliques and cycles [ELRS25; SPHH25]. Our LNDP⋆ lower bounds are tight and apply to arbitrary template graphs√of maximum degree greater than 1. Additionally, our lower bound establishes the first Ω( n) separation between local and central node DP for general graph problems. While [RSWZ26] gave local-central separations, they either involved only poly(1/ε) factors or only applied to promise problems, in which the accuracy guarantee holds for a restricted class of inputs graphs (with privacy holding for all graphs). Our lower bounds are also more general than the analogous results for edge privacy and provide new insights into the relationship between the local and central models.

1.2

Our Techniques

We now describe the techniques behind our LNDP⋆ algorithm and additive-error lower bounds for counting subgraphs. 5

1.2.1

Algorithm for Subgraph Counting

In the setting of local edge differential privacy (LEDP), optimal noninteractive algorithms for subgraph counting work by releasing the graph’s entire adjacency matrix via randomized response on each entry with parameter ε, and postprocessing the result [ELRS25]. This technique breaks down under the constraint of node privacy since rewiring a single node can change Θ(n) edges (i.e., bits in the adjacency matrix); consequently, releasing the adjacency ⋆ matrix √ with an (ε, δ)-LNDP guarantee requires running randomized response with parameter O(ε/ n) on each bit. Such an approach yields an algorithm that counts k-node subgraphs with additive error Ω(nk ), which is trivial. We devise a different approach for our algorithm. It relies heavily on public randomness, which is used to partition the node set into n/k blocks of k nodes, each corresponding to a single candidate copy of the template graph H. Within each block, the relevant nodes report, via randomized response with debiasing, whether the edges required by their assigned positions in H are present. Postprocessing multiplies these reports to obtain a noisy indicator for the candidate copy, and then rescales and averages the indicators over all blocks to obtain a final estimate for the subgraph count. This random partitioning-based design has two key properties that are essential to our algorithm’s (optimal) error guarantees. The first feature, reduced sensitivity, emerges because rewiring a single node can affect only the k reports from its own block. Randomized response with parameter ε/k thus suffices for node privacy, which keeps the privacy error small. The second feature is that, after rescaling, the noisy indicators we extract from each of the blocks are unbiased, low-variance estimators of the total subgraph count. Partitioning the nodes, as opposed to sampling blocks with replacement, makes the accuracy analysis delicate since the block indicators are no longer independent. Nevertheless, we show through a second-moment calculation that the correlations between these indicators are mild, so the sampling error is low. Averaging the n/k rescaled signals yields an unbiased estimate with two sources of additive k− 12 k− 12 k error: sampling contributes Ok n , and privacy noise contributes Ok n /ε . In fact, for each block it suffices to obtain reports only from nodes in a vertex cover of H, improving the dependence from εk to εVC(H) and giving the error stated in Theorem 1.1. 1.2.2

Lower Bound for Subgraph Counting

Our lower bound (Theorem 1.2) is proven via a reduction from accurately answering inner product queries under differential privacy in the central model. Given a secret dataset ⃗x ∈ {0, 1}n , an inner product query (or linear query) on ⃗x is specified by a vector ⃗a ∈ {0, 1}n , and maps ⃗x to the answer p = ⟨⃗x, ⃗a⟩. A seminal result in privacy [DN03; DMT07] demonstrates that algorithms that answer a set of Θ(n) inner product queries ⃗a(1) , . . . , ⃗a(q) to within error √ roughly n can be used to reconstruct an overwhelming majority of ⃗x. Such algorithms, of course, are not differentially private even for modest privacy parameters. Our reduction shows that if A is an LNDP⋆ algorithm with additive error α for H-counting (i.e., estimating #H(G)) on n-node graphs, then it can be used to construct a DP algorithm 6

v(2,1)

v(2,i′ ) v(2,n)

v(3,1) v(3,2) .. U3 . v(3,n)

{v(1,i) , v(2,j) } ∈ E for all j if xi = 1

U2 and U3 form complete bipartite graph

v(1,1) v(1,i)

v(1,n)

{v(1,i) , v(3,j) } ∈ E for all j if ai = 1

Figure 1: The query graph (Definition 4.4) for H = K3 . Red edges depend on the sensitive vector ⃗x; dashed edges depend on the query vector ⃗a; the remaining edges are fixed. k−1 B in the central model with additive error O(α/n ) for answering inner product queries. √ k−1/2 Thus, if α ≤ cn , then B achieves error O( n), which contradicts DP for sufficiently small constant c > 0. We now describe the main ideas behind our reduction. Algorithm B in our reduction makes two calls to A on graphs that depend on ⃗x but not on the queries. The algorithm then answers all inner product queries by postprocessing the outputs of these calls. For each inner product query ⃗a, it combines these stored values to emulate the output of A on a query graph whose subgraph count reflects the unknown inner product value, without explicitly running A on each query graph. The query graph corresponding to ⃗a embeds ⟨⃗x, ⃗a⟩ in its edges. For our reduction to work, the query graph must satisfy three requirements:

R1: A single bit change in ⃗x must correspond to a rewiring of a constant number of nodes, so that neighboring datasets in the inner product problem correspond to graphs at constant node distance. R2: An error of α in the subgraph count must translate to an error of O(α/nk−1 ) in the estimate for the inner product query. R3: Each node whose neighborhood depends on the sensitive vector ⃗x must have one of two possible neighborhoods in each of the q query graphs, so that two runs of this node’s randomizer suffice to release the relevant information about these neighborhoods. We give the following construction of the query graph satisfying these requirements. Suppose w.l.o.g. that node 1 in H is connected to nodes 2 and 3. The query graph for an inner product query ⃗a has kn nodes, equipartitioned into k parts U1 , . . . , Uk , each corresponding to a node of H; edges of H correspond to complete bipartite graphs between the respective parts, except for the edges from U1 which encode the input: the i’th node of U1 connects to all nodes in U2 iff xi = 1, and to all nodes in U3 iff ai = 1. Note that a change in a single bit of ⃗x corresponds to rewiring a node in U1 (thereby satisfying requirement R1), which can change the subgraph count in the query graph by Θ(nk−1 ). Figure 1 depicts the query graph when H is a triangle. 7

n3 ⟨⃗x, ⃗a⟩

U3 n n2 ∥⃗x∥

n2 ⟨⃗x2,⃗a⟩

∥⃗a∥ U3

n 2

Figure 2: Four types of copies of H = C4 in the query graph, along with their counts. While variants of the query graph have appeared before (see [ELRS25; SPHH25]), our construction is novel in several ways: it embeds an inner-product query rather than a similar but meaningfully different “outer-product” query, encodes the secret vector ⃗x differently, and applies to arbitrary template graphs with maximum degree greater than 1, rather than just cliques and cycles. A central difficulty is in satisfying requirement R2. In the special case that H is a k-clique, every copy of H must use exactly one node in each part of the query graph, leading to a subgraph count of nk−1 ⟨⃗x, ⃗a⟩. Thus, dividing an estimate for the subgraph count by nk−1 yields an estimate for ⟨⃗x, ⃗a⟩, with the error similarly scaling down by a factor of nk−1 . However, the general case is more involved: for example, when H is a 4-cycle, Figure 2 shows that copies of H may use multiple nodes from one part, with the subgraph count depending on ∥⃗x∥ and ∥⃗a∥ rather than just ⟨⃗x, ⃗a⟩. We resolve this difficulty by building the query graph from the concatenated vectors ⃗x◦ = ⃗x ◦ (⃗1 − ⃗x) and ⃗a◦ = ⃗a ◦ ⃗0, which satisfy ∥⃗x◦ ∥ = n, ∥⃗a◦ ∥ = ∥⃗a∥, and ⟨⃗x◦ , ⃗a◦ ⟩ = ⟨⃗x, ⃗a⟩. Since the weights of both ⃗x◦ and ⃗a◦ are known, the H-count of G[⃗x◦ , ⃗a◦ ] is a function g(·) of just one private unknown ⟨⃗x, ⃗a⟩. A single bit change in ⃗x now rewires two nodes of the query graph, which still satisfies requirement R1. As we show, g(·) is a quickly increasing function of ⟨⃗x, ⃗a⟩ with a discrete derivative of ∂⟨⃗∂g = Ω(nk−1 ), allowing us to invert it to obtain an x,⃗a⟩ estimate for ⟨⃗x, ⃗a⟩.2 Then, given an estimate d with error α for the subgraph count, returning k−1 g −1 (d) as our estimate for ⟨⃗x, ⃗a⟩ gives an error of |g −1 (d) − ⟨⃗x, ⃗a⟩ | ≲ α/ ∂⟨⃗∂g = O α/n . x,⃗a⟩ ⋆ Requirement R3 lets√us avoid calling LNDP algorithm A for each of the q query graphs, which would result in a n blowup in privacy parameters. We circumvent this by adapting the “mix-and-match” technique [ELRS25] to our reduction from inner product queries. The idea is that all nodes in the query graphs whose neighbors depend on the sensitive vector ⃗x—namely, those in U1 and U2 —have at most two views across all query graphs. The neighborhood of each node in U2 is the same for all query graphs, whereas each node v(1,i) in U1 has one of two possible neighborhoods, determined by the bit ai of the inner product query. To obtain the information that B needs from each node in U1 and U2 , we run the randomizers assigned to each node by A on the two query graphs where ⃗a is set to ⃗0 and ⃗1, and cache the two reports from each node. All other nodes have no access to the information pertaining to the 2

Since g is only defined on the integers, instead of the derivative we use the finite difference ∆g(b) = g(b + 1) − g(b). See Section 4 for details.

secret vector ⃗x, so we can run randomizers on them multiple times as part of postprocessing with no privacy loss. By appropriately matching the reports from different nodes so that they are what each node would report in the true query graph for a given query, we can simulate each of the q runs of A with only two private calls to A.

1.3

Related Work

DP for graph data was first investigated by [NRS07], who gave edge-private algorithms for triangle counting and estimating the cost of the minimum spanning tree. General private subgraph counts were first studied by [KRSY14] (strengthening [RHMS09], who studied the problem under a relaxation of DP), in the central model under edge privacy. Node DP. The first node-private algorithms were for subgraph counts and appeared in [BBDS13; CZ13; KNRS13], after node privacy was formulated by [HLMJ09]. Subsequent work developed node-private algorithms for degree distributions via Lipschitz extensions [RS16b] and projections [DLL16], as well as for practical triangle counting [DZBJ18], graphon and Erdős-Rényi parameter estimation [BCSZ18; SU21], counting connected components [KRST23; JSW24], and node privacy under continual observation [JSW24]. More recent work used sum-of-squares methods for node-private graphon estimation and edge-density estimation in random graph models [CDdHLS24; CDHS24]. Generic, exponential-time private algorithms with accuracy based on a function’s down-sensitivity have also been applied to node privacy [FDY22; LRSS25]. Node-private methods have also been applied to epidemiological data [HNGKTS26]. Closest to our setting, [RSWZ26] introduced local node differential privacy and studied noninteractive and interactive algorithms for releasing functions of a graph’s degree list. See [RS16a] for a survey of graph privacy. (Vanilla) Local DP. Local randomization algorithms [War65; EGS03] predate the introduction of DP, but were later recognized as mechanisms satisfying this definition [DMNS16; MS06]. The (interactive) local model of DP was formalized and studied systematically by [KLNRS11]. Lower bounds for bit summation in this model were established by [BNO08]. A large body of subsequent work has developed the statistical and information-theoretic foundations of local privacy, including general lower-bound techniques and tight characterizations for basic estimation tasks (e.g., [DJW13]). Interactivity in the local model was systematically studied by [JMNR19], who formalized several notions of interactivity and showed that, for hypothesis testing, noninteractive randomized response is optimal even among interactive protocols. Local DP also saw several large-scale deployments, including RAPPOR [EPK14], Prochlo [BEM+17], Microsoft telemetry [DKY17], and Apple’s method for identifying popular image locations [App23]. While some works [KLNRS11; BNO08; JMNR19] have dealt with the interactive setting, many—including ours—focus on the noninteractive setting (e.g., [DJW13; BS15; BNS19; ENU20; CGKM21; FMRT25; CGS26; AFRS26]).

Local Edge DP. With the exception of [RSWZ26], all prior work on local privacy for graphs considered the weaker notion of local edge differential privacy (LEDP). The model was introduced by [QYYKXR17], who studied the generation of synthetic graphs, and was formally defined for the noninteractive and interactive settings in [IMC21] and [ELRS25], respectively. Subsequent work investigated the estimation of graph statistics, including triangle and k-star counts [IMC21; IMC22; ELRS25], k-core decomposition and densest subgraph computation [DLRSSY22; MPSL25], and more general subgraph counting problems [SPHH25]. Several works established lower bounds for these tasks. In particular, [ELRS25] introduced the “mix-and-match” technique, obtaining lower bounds for triangle counting, and [SPHH25] extended this approach to complete subgraphs. Most recently, [HSS25] established optimal error bounds for triangle counting in constant-degeneracy graphs.

1.4

Organization

Section 2 formalizes the subgraph-counting problem and gives background on differential privacy and the LNDP⋆ model. Section 3 presents our LNDP⋆ algorithm for subgraph counting (Algorithm 1), along with its error guarantees in Theorem 3.1. Section 4 gives our lower bound on the error required for subgraph counting under LNDP⋆ (Theorem 1.2), establishing the optimality of our algorithm’s error.

Preliminaries

We let [n] denote {1, . . . , n}. Additionally, for an undirected graph G on node set [n], the set Ni (G) denotes the neighborhood of node i ∈ [n] in G. We are interested in counting the number of unlabeled, noninduced instances of some template graph H in an undirected input graph G, under LNDP⋆ . (The number of labeled instances in G is a factor of |Aut(H)| larger than the number of unlabeled instances, where we let |Aut(H)| denote the number of automorphisms of H.) Definition 2.1 (Subgraph counting). Let H = (V (H), E(H)) be an undirected graph on k nodes, and n ∈ N. An unlabeled, noninduced subgraph count query on graphs with vertex set [n] is specified by H and maps an undirected input graph G on vertex set [n] to the number of unlabeled copies of H in G. In other words, using ,→ to denote an injection, it returns #H(G) =

2.1

1 φ : V (H) ,→ V (G) : ∀{u, v} ∈ E(H), {φ(u), φ(v)} ∈ E(G) |Aut(H)|

Local Node Differential Privacy

We now recall the definitions of DP and LNDP⋆ (see Appendix A for additional background). Node neighbors and differential privacy. Differential privacy is defined with respect to neighboring datasets, which differ in the data of a single individual. In the tabular setting, 10

two datasets x, x′ ∈ X n are neighbors if they differ in one entry. We focus on node privacy for graphs: graphs G and G′ on node set [n] are node neighbors, denoted G ∼ G′ , if one can be obtained from the other by rewiring a single node, i.e., by changing only the edges incident to some node i ∈ [n]. More generally, G and G′ are at node distance k if one can be obtained from the other by rewiring k nodes. Definition 2.2 ((ε, δ)-indistinguishability). Let ε > 0 and δ ∈ [0, 1]. Two distributions P, Q over outcome space Y are (ε, δ)-indistinguishable, denoted P ≈ε,δ Q, if for all Y ⊆ Y, P (Y ) ≤ eε Q(Y ) + δ

and

Q(Y ) ≤ eε P (Y ) + δ.

We write R1 ≈ε,δ R2 for random variables R1 and R2 with (ε, δ)-indistinguishable distributions. Definition 2.3 (Differential privacy (DP) [DMNS16]). Let ε > 0 and δ ∈ [0, 1]. A randomized algorithm A : U ∗ → Y is (ε, δ)-DP if A(x) ≈ε,δ A(x′ ) for every pair of neighboring inputs x, x′ ∈ U ∗ . Many DP algorithms in the local model are built from the randomized response primitive of [War65], which was shown by [DMNS16] to satisfy (ε, 0)-DP. Definition 2.4 (Randomized response). Given ε > 0, let RRε : {0, 1} → {0, 1}, called randomized response, be the (ε, 0)-DP algorithm that, on input b ∈ {0, 1}, returns b with ε probability eεe+1 , and 1 − b with probability eε1+1 . The standard method for debiasing randomized response is analyzed, e.g., in [ELRS25]. ε

Fact 2.5. Given output X = RRε (b), the debiased estimate Y = X(eeε+1)−1 has expectation −1 eε 1 E[Y ] = b. Moreover, Var(Y ) = (eε −1)2 , which is Θ ε2 for ε ≤ 1. LNDP⋆ . Following the convention in [RSWZ26], we use LNDP⋆ to denote noninteractive LNDP. In the LNDP⋆ setting, each node runs a local randomizer on its edge list and releases the result. (Local randomizers can depend on public randomness.) These noisy releases are then postprocessed to obtain a final result. LNDP⋆ requires that the joint distributions over all nodes’ reports be (ε, δ)-indistinguishable on node-neighboring input graphs, for all strings ρ of public randomness. Definition 2.6 (LNDP⋆ [RSWZ26]). Let ε > 0, δ ∈ [0, 1], and n ∈ N. An algorithm A is (ε, δ)-LNDP⋆ if there exist (i) a distribution Φ over strings ρ (public randomness), (ii) local randomizers R1,ρ , . . . , Rn,ρ (depending on ρ), and (iii) a postprocessing algorithm P such that 1. (Locality and noninteractivity) for all graphs G onnode set [n], the algorithm A can be represented as P R1,ρ (N1 (G)), . . . , Rn,ρ (Nn (G)) , where ρ ∼ Φ and node i runs a randomizer Ri,ρ on its neighborhood Ni (G), and 2. (Node privacy) For all node-neighboring graphs G and G′ on node set [n] and all settings of public randomness ρ, the distributions of vectors of outputs released by the ⃗ ρ (G) ≈ε,δ R ⃗ ρ (G) = ⃗ ρ (G′ ), where R randomizers are (ε, δ)-indistinguishable—that is, R ⃗ ρ is (ε, δ)-DP under R1,ρ (N1 (G)), . . . , Rn,ρ (Nn (G)) . Equivalently, for all ρ, the map R the node-neighboring relation. 11

Algorithm for Subgraph Counting with LNDP⋆

In this section we present our LNDP⋆ algorithm for counting the number of unlabeled instances of a k-node template graph H in an n-node graph G. Our algorithm (separately) handles counting induced and noninduced copies of H. For a template graph H = ([k], E(H)), let VC(H) ∈ [k] denote the size of the minimum vertex cover of H. Theorem 3.1 (Subgraph counting). Let Asub be Algorithm 1 with parameters ε ∈ (0, 1], k, n ∈ N, and undirected template graph H on node set [k]. Then Asub is (ε, 0)-LNDP⋆ and, for all graphs G on node set [n], satisfies ! √ VC(H) ! k− 12 1 k! VC(H) n E Asub (G) − #H(G) = O · nk− 2 · = Ok . |Aut(H)| ε εk−1 Algorithm 1 can be modified to instead count induced copies of H. The resulting error guarantee is the same, except VC(H) is replaced by k − 1. Algorithm overview. At a high level, we first randomly partition the node set into blocks of k nodes. For each block, we randomly assign each node to a node in H, and have each node in a minimum vertex cover C of H use randomized response to release a debiased version of a noisy bit indicating whether its edge set matches that of its assigned node in H. Multiplying these debiased values yields a noisy indicator for whether H appears in the subgraph induced by the block (for a random labeling of nodes in the block). Finally, we sum these noisy k! indicators and scale up by |Aut(H)| to obtain an unbiased estimate for the total number · n−1 k−1 of unlabeled occurrences of H in G. In our algorithm, we use the following notation. For a sequence I = (v1 , . . . , vk ) of nodes in [n], define the indicator variable MatchI,H = 1 iff for every neighbor j of i in H, the pair i {vi , vj } forms an edge in G. Proof of Theorem 3.1. Assume, without loss of generality, that n is divisible by k so that the step on Line 2 is well defined; otherwise, add dummy nodes to G to ensure k divides n. (Privacy.) Fix a random permutation P and a pair of node-neighboring graphs G and G′ , where i∗ is the rewired node. By Definition 2.6, to prove that the algorithm is (ε, 0)-LNDP⋆ , (j) it suffices to show that releasing the vector of node outputs Yi i∈C,j∈[n/k] is (ε, 0)-DP. This (j) vector is a function only of the sequence MatchPi ,H i∈C,j∈[n/k] . The only output-producing (j)

nodes that may have different values of MatchPi ,H for G and G′ are the VC(H) nodes in the (j) sequence P (j) containing i∗ . Thus, MatchPi ,H i∈C,j∈[n/k] has ℓ1 sensitivity at most VC(H), so by group privacy the algorithm that releases each bit of this vector via debiased randomized response with parameter ε′ (as on Line 5) is (ε, 0)-DP. (Accuracy.) Let T denote the number of unlabeled copies of H in G, and define the Q (j) indicator S (j) = i∈C MatchPi ,H ; that is, S (j) = 1 iff the specified labeling embeds H as a 12

Algorithm 1 Asub for counting occurrences of template graph H. Parameters: Privacy parameter ε ∈ (0, 1]; k, n ∈ N; template graph H on node set [k]. Input: Graph G on vertex set [n]. Output: Subgraph count estimate Tb. 1: Let ε′ = ε/VC(H), and let C ⊆ [k] be a minimum-size vertex cover of H. 2: Use public randomness to select a uniformly random permutation P of [n], divided into sequences P (1) , . . . , P (n/k) of size k. Local randomization: (j) (j) 3: for each sequence P (j) = (v1 , . . . , vk ) do 4: for each i ∈ C do ′ (j) (j) ′ X ·(eε +1)−1 (j) (j) (j) 5: Node vi releases Yi ← i eε′ −1 , where Xi ← RRε MatchiP ,H . ▷ Yi(j) is a debiased version of Xi(j) . Aggregation (post-processing): b(j) ← Q Y (j) . 6: For each sequence P (j) , set S i∈C i P n−1 k! b b(j) 7: return T ← |Aut(H)| · k−1 · j∈[n/k] S . subgraph of the graph induced by P (j) . We first show that Tb is an unbiased estimator of T . For each j ∈ [n/k], E[S (j) ] = Pr[S (j) = 1] =

T |Aut(H)| , n · k! k

(1)

since S (j) = 1 if one of the T copies of H lands in P (j) and the right labeling is chosen. From (j) the debiasing on Line 5 and mutual independence of the Yi for fixed permutation P , we Q (j) have E[Sb(j) | P ] = i∈C E[Yi | P ] = E[S (j) | P ], so E[Sb(j) ] = E[S (j) ] by the law of total expectation. By the definition of Tb on Line 7 and linearity of expectation, X k! n − 1 k! n − 1 n T |Aut(H)| (j) E[Tb] = · E[Sb ] = · · n · = T. |Aut(H)| k−1 |Aut(H)| k − 1 k k k! j∈[n/k]

We next bound the algorithm’s additive error. The error arises from two sources: randomized response(privacy error) and random permutation sampling (sampling error). Let P k! Te = |Aut(H)| · n−1 · j∈[n/k] S (j) . By the triangle inequality, the error can be bounded as: k−1 E Tb − T ≤ E Tb − Te + E Te − T . | {z } | {z } privacy error

(2)

sampling error

Bounding the privacy error E Tb − Te . We first bound the expected privacy error, conditioned on the public permutation P ; since this bound is independent of P , taking 13

expectation over P yields the same bound unconditionally. For each j ∈ [n/k], let ∆j := Sb(j) − S (j) . To analyze the privacy error, we take advantage of the fact that, conditioned on P , all ∆j ’s are independent (because local randomizers perform randomized response independently) and also, by the properties of the debiasing step (see Fact 2.5), have expectation 0. By linearity of conditional expectation, h i i k! n−1 h X b e E T −T |P = E ∆j P . (3) |Aut(H)| k − 1 j∈[n/k]

To bound the expectation in (3), we apply Jensen’s inequality and then use the fact that, conditioned on P , the ∆j ’s are independent and have mean zero: h X i s h X 2 i s X E ∆j P ≤ E E[∆2j | P ]. (4) ∆j P = j∈[n/k]

j∈[n/k]

(5)

using respectively, in the final line of (5), independence of the randomized-response noise added by different nodes within the block, Fact 2.5, and ε′ = ε/VC(H). (n−1)k−1 ≤ (k−1)! gives Combining (3) to (5) and then using n−1 k−1 r VC(H) ! k! n−1 n VC(H) ·O |Aut(H)| k − 1 k ε √ VC(H) ! 1 VC(H) k =O · nk− 2 · . |Aut(H)| ε

h i E Tb − Te | P ≤

(6)

By the law of total expectation, taking expectation over P gives the same bound unconditionally. Bounding the sampling error E Te − T . We start by applying Jensen’s inequality and then using the fact that E[Te] = T : q q q 2 2 e e e E T −T =E (T − T ) ≤ E (T − T ) = Var(Te). (7) P To bound Var(Te), we represent Te as Te = Sp , where S := j∈[n/k] S (j) and p := |Aut(H)| . k!(n−1 k−1 ) The summands S (j) in the expression for S are not independent. Nevertheless, since their pairwise correlation is fairly weak, one can still bound Var(S) = E[S 2 ] − E[S]2 . By (1), we 14

] = nk · Tn · |Aut(H)| = T p. Now we expand the second moment: k! (k ) X X X X (j) 2 E[S 2 ] = E ( S ) = E[S (j) ] + E[S (i) S (j) ] = T p + Pr[S (i) = S (j) = 1].

get E[S] = E[

j∈[n/k] S

(j)

j∈[n/k]

i̸=j

The last sum has nk ( nk − 1) terms. Blocks P (i) and P (j) in the partition are vertex-disjoint, so both S (i) and S (j) can be 1 only if the two blocks sample two vertex-disjoint copies of H in G. Let D be the number of ordered pairs of vertex-disjoint copies of H. Then D ≤ T 2 , and X

|Aut(H)|2 n(n − k) |Aut(H)|2 2 n−k−1 ≤ T · D k2 (k!)2 nk n−k (k!)2 n−1 k k−1 k−1 2 k−1 n−1 Y k k k−1 2 2 2 1+ = p · n−k−1 = p · =p 1+O . n − k − r n k−1 r=1

Pr[S (i) = S (j) = 1] =

i̸=j

2 2 2 − T 2 p2 = T p + O k Tn p . Therefore, Var(S) = E[S ] − E[S] ≤ T p + T p 1 + O kn nk k!nk−1 To bound Var(Te), recall that Te = Sp . Using T = O( |Aut(H)| ) and p1 = O( |Aut(H)| ), we get

2 2

2 2 2k−1 Var(S) T k T k! · n Var(Te) = ≤ +O =O . p2 p n |Aut(H)|2 Substituting the expression for Var(Te) into (7) gives us ! √ q 1 k! · nk− 2 . E Te − T ≤ Var(Te) = O |Aut(H)| Bounding the overall error E Tb − T . Substituting the bounds on privacy and sampling √ √ error into (2) yields nearly the same bound as in (6), except that k changes to k!: √ VC(H) ! 1 k! VC(H) E Tb − T = O · nk− 2 · . |Aut(H)| ε This completes the proof of Theorem 3.1.

Error Required for Subgraph Counting with LNDP⋆ 1

In this section we prove Theorem 1.2, showing a lower bound of Ωk (nk− 2 ) on the additive error required by LNDP⋆ algorithms for counting k-node subgraphs H with maximum degree greater than 1. We describe inner product queries and the properties of our main reduction in Section 4.1, our method for encoding an inner product query on a secret dataset as a query graph in Section 4.2, and provide our main reduction from inner-product queries in the central model to H-counting under LNDP⋆ in Section 4.3. 15

4.1

Inner Product Queries

An inner product query on dataset ⃗x ∈ {0, 1}n is specified by a vector ⃗a ∈ {0, 1}n , and maps ⃗x to the answer p = ⟨⃗x, ⃗a⟩. The problem InnerProducts(n, q) is to answer q inner product queries ⃗a(1) , . . . , ⃗a(q) ∈ {0, 1}n on dataset ⃗x ∈ {0, 1}n . We consider algorithms that answer inner product queries with the guarantee that, with high probability, all but a γ-fraction of their answers are accurate. Definition 4.1 (Inner product accuracy). Let α, γ > 0 and n, q ∈ N. A randomized algorithm B is (α, γ)-accurate for InnerProducts(n,q) if, for all queries ⃗a(1) , . . . , ⃗a(q) ∈ {0, 1}n and all datasets ⃗x ∈ {0, 1}n , algorithm B ⃗x, ⃗a(j) j∈[q] outputs answers p(1) , . . . , p(q) ∈ R such that h i 99 , Pr i ∈ [q] : p(i) − ⃗a(i) , ⃗x > α ≤ γ · q ≥ coins of B 100 99 i.e., with probability at least 100 , all but a γ-fraction of answers p(i) satisfy p(i) − a(i) , ⃗x

≤ α.

An algorithm for InnerProducts is (ε, δ)-DP if, for every fixed set of query vectors and all vectors ⃗x and ⃗x′ that differ in one bit, the output distributions of the algorithm are (ε, δ)-indistinguishable. A slight adaptation of the reconstruction attacks of [DN03], as reanalyzed in [DMT07], gives the following impossibility result (see Appendix B for a proof sketch). Lemma 4.2 (Inner product lower bound, based on [DN03], [DMT07, Theorem 23]). There exist algorithm B is √ c1 ,1c2 > 0 such that, for sufficiently large n ∈ N, if a randomized 1 (c1 n, 100 )-accurate for InnerProducts(n, c2 n), then B is not (4, 25 )-DP. Key reduction. We prove our lower bound by reducing from inner product queries in the central model to accurate subgraph counting under LNDP⋆ . Lemma 4.3 (Inner products via subgraph counts). Let α > 0 and k, n, q ∈ N with n ≥ 5k k . 1 Let H be a k-node graph with maximum degree greater than 1. Suppose there is a (1, 200 )⋆ LNDP algorithm A that, for every 2kn-node graph G, counts the number of copies of H in G with error E

[|A(G) − #H(G)|] ≤ (2n)k−1 · 9 · 10−6 · α = Ok (α · nk−1 ).

coins of A

(8)

1 1 Then there is a central-model (4, 25 )-DP algorithm B that is (α, 100 )-accurate for InnerProducts(n, q).

Lemmas 4.2 and 4.3 immediately allow us to prove Theorem 1.2. Proof of Theorem 1.2. Let c1 and c2 be the constants from Lemma 4.2 and let n′ ∈ N suf1 ficiently large with n′ ≥ 5k k . Let n = 2kn′ , and suppose that A is a (1, 200 )-LNDP⋆ algorithm that, for graphs G on 2kn′ nodes, counts copies√ of H with expected error −6 ′ E[|A(G) − #H(G)|] = α, where α ≤ (2n′ )k−1 4.3 √ · 9 1· 10 (c1 n ). Applying Lemma 1 ′ gives an algorithm B that is (4, 25 )-DP and (c1 n , 100 )-accurate for InnerProducts(n′ , c2 n′ ). 1 However, by Lemma 4.2, B cannot be (4, 25 )-DP, which is a contradiction. Thus, we must √ k− 21 ′ k−1 −6 ′ have α > (2n ) · 9 · 10 (c1 n ) = Ωk (n ), as desired. 16

The rest of this section is devoted to proving Lemma 4.3.

4.2

Query Graphs and Their Properties

We now describe how to encode a secret dataset and inner product query as a query graph. Let H = ([k], E(H)) be an undirected graph on node set [k] with maximum degree greater than 1. W.l.o.g. assume {{1, 2}, {1, 3}} ⊆ E(H), i.e., node 1 is adjacent to nodes 2 and 3, which can be achieved by relabeling nodes since dmax (H) > 1. A query graph when H is a triangle is depicted in Figure 1. Definition 4.4 (Query graph). Fix a secret dataset ⃗x = (x1 , . . . , xn ) ∈ {0, 1}n and an inner product query ⃗a = (a1 , . . . , an ) ∈ {0, 1}n . The query graph G[⃗x, ⃗a] has N := kn nodes partitioned into sets U1 , . . . , Uk of size n, with nodes in Us denoted v(s,1) , . . . , v(s,n) . We add edges only between parts Us , Ut with {s, t} ∈ E(H), as follows: • For each i ∈ [n], add edges from v(1,i) to all of U2 iff xi = 1, and to all of U3 iff ai = 1. • For every other pair {s, t} ∈ E(H), form a complete bipartite graph on parts Us and Ut . As outlined in Section 1.2.2, the query graph has several important properties (slightly abbreviated here): R1: A single bit change in ⃗x corresponds to a rewiring of one node in U1 . R2: An error of α in the subgraph count #H(G[⃗x, ⃗a]) translates to an error of O(α/nk−1 ) in the estimate for the inner product query ⟨⃗x, ⃗a⟩. R3: For every fixed ⃗x, each node in U1 and U2 has two possible neighborhoods in the query graphs G[⃗x, ⃗a] : ⃗a ∈ {0, 1}n , namely its neighborhoods in G[⃗x, ⃗0] and G[⃗x, ⃗1]. While R1 and R3 are immediate, showing R2 requires more work, which we now describe. To understand the number of copies of H in the query graph, we first classify the vertices in U1 according to how they connect to U2 and U3 . Partition U1 into subsets U111 , U110 , U101 , U100 denoting the nodes v(1,i) with (xi , ai ) equal to (1, 1), (1, 0), (0, 1) and (0, 0), respectively. The nodes in each subset have the same neighborhoods in U2 ∪ U3 : nodes in U111 connect to both U2 and U3 , nodes in U110 connect to U2 but not U3 , nodes in U101 connect to U3 but not U2 , and nodes in U100 connect to neither. Their sizes are |U111 | = ⟨⃗x, ⃗a⟩ |U101 | = ∥⃗a∥ − ⟨⃗x, ⃗a⟩

|U110 | = ∥⃗x∥ − ⟨⃗x, ⃗a⟩ |U100 | = n − ∥⃗x∥ − ∥⃗a∥ + ⟨⃗x, ⃗a⟩ .

(9)

Since all nodes in a fixed Us for s ≥ 2 have identical neighborhoods and so do the nodes in a fixed part of U1 (using the partition above), the number of copies of H in the query graph G[⃗x, ⃗a] depends solely on n and the sizes of the subsets in (9), which in turn depend only on p = ⟨⃗x, ⃗a⟩ , wx = ∥⃗x∥, and wa = ∥⃗a∥. This motivates the H-counting function, which lets us study how the subgraph count changes with ⟨⃗x, ⃗a⟩ while the weights of ⃗x and ⃗a stay fixed. 17

Definition 4.5 (H-counting function). Fix ⃗x = (x1 , . . . , xn ) ∈ {0, 1}n and ⃗a = (a1 , . . . , an ) ∈ {0, 1}n . Define the H-counting function fH (p, wx , wa ) := #H(G[⃗x, ⃗a]) to be the number of copies of H in the query graph for any ⃗x and ⃗a such that p = ⟨⃗x, ⃗a⟩, wx = ∥⃗x∥, and wa = ∥⃗a∥. Furthermore, define the forward difference ∆p fH (p, wx , wa ) := fH (p + 1, wx , wa ) − fH (p, wx , wa ). In the following lemma we lower bound the forward difference of fH with respect to p. As we show subsequently, this bound ensures that even an approximate version of fH ⟨⃗x, ⃗a⟩ , ∥⃗x∥, ∥⃗a∥ reveals the approximate value of ⟨⃗x, ⃗a⟩ when ∥⃗x∥ and ∥⃗a∥ are publicly known. We say a triple (p, wx , wa ) ∈ {0, . . . , n}3 is feasible if there exist ⃗x, ⃗a ∈ {0, 1}n such that p = ⟨⃗x, ⃗a⟩ , wx = ∥⃗x∥, and wa = ∥⃗a∥ (i.e., if wx + wa − n ≤ p ≤ min{wx , wa }). Lemma 4.6 (Forward difference bound). For every feasible (p, wx , wa ), if (p + 1, wx , wa ) is 9 k−1 also feasible and n ≥ 10k k , then ∆p fH (p, wx , wa ) ≥ 10 n . Proof of Lemma 4.6. Let ⃗x and ⃗a be such that p = ⟨⃗x, ⃗a⟩, wx = ∥⃗x∥, and wa = ∥⃗a∥, and let G := G[⃗x, ⃗a]. Since (p + 1, wx , wa ) is feasible, there exist u+ := v(1,i) ∈ U110 and u− := v(1,j) ∈ U101 for some i, j ∈ [n]. Let G′ := G[⃗x′ , ⃗a′ ], where ⃗a′ agrees with ⃗a except that a′i = 1 and a′j = 0. Then ∥⃗a′ ∥ = ∥⃗a∥ and ⟨⃗x, ⃗a′ ⟩ = p + 1, so #H(G′ ) = fH (p + 1, wx , wa ). Let A be the set of copies in G′ but not G, and let B be the set of copies in G but not G′ . By definition of G and G′ , every copy in A uses an edge between u+ and U3 , and every copy in B uses an edge between u− and U3 . Write the disjoint union B = B1 ⊔ B2 , where B1 is the set of copies in B that contain u+ . Then, ∆p fH (p, wx , wa ) = #H(G′ ) − #H(G) = |A| − |B| = (|A| − |B2 |) − |B1 |. It suffices to show |B1 | ≤ k k nk−2 and |A| − |B2 | ≥ nk−1 , which, combined with n ≥ 10k k , proves the lemma. Bounding |B1 |. There are k choices for the nodes in H assigned to each of u− and u+ and (kn)k−2 choices for the remaining k − 2 nodes in H, giving |B1 | ≤ k 2 (kn)k−2 ≤ k k nk−2 . Bounding |A| − |B2 |. For c ∈ B2 , let ψ(c) be the copy obtained by replacing u− with u+ . This gives a copy in G′ that is not in G, so ψ maps B2 to A and is injective (one can replace u+ back with u− ), so |ψ(B2 )| = |B2 |. There are nk−1 copies of H in A mapping node 1 of H to u+ and each node s ≥ 2 to Us . Each such copy is not in ψ(B2 ), as it has an edge between u+ and U2 , whereas u− has no neighbors in U2 . This gives |A| − |B2 | = |A \ ψ(B2 )| ≥ nk−1 , as desired.

4.3

Reduction from Inner Product Queries to Subgraph Counting

In this section, we describe and analyze the reduction from inner product queries to subgraph counting, proving Lemma 4.3. Figure 3 illustrates the structure of the reduction in Algorithm 2, which was described informally in the introduction. Rather than directly working with the 18

secret dataset ⃗x ∈ {0, 1}n and inner product query ⃗a(ℓ) ∈ {0, 1}n , our reduction applies the query graph construction and the H-counting function to the concatenations ⃗x◦ := ⃗x ◦ (⃗1 − ⃗x) (ℓ) (ℓ) and ⃗a◦ := ⃗a(ℓ) ◦ ⃗0 of length 2n. Note that ∥⃗x◦ ∥ = n and ∥⃗a◦ ∥ = ∥⃗a(ℓ) ∥ are publicly known (ℓ) (although ⃗x is private), and ⟨⃗x◦ , ⃗a◦ ⟩ = ⟨⃗x, ⃗a(ℓ) ⟩. This results in just one private unknown (ℓ) ⟨⃗x◦ , ⃗a◦ ⟩, which our reduction estimates. The algorithm accesses the secret vector ⃗x by making two calls to the randomizers of the LNDP⋆ algorithm A—one on G[⃗x◦ , ⃗0] and one on G[⃗x◦ , ⃗1]—to obtain the necessary views of nodes to reconstruct an output of A on every query graph. To answer each inner product query ⃗a(ℓ) , the reduction uses the MixAndMatch subroutine (Algorithm 3), which postprocesses the obtained randomizer reports to obtain an estimate (ℓ) (ℓ) d(ℓ) ∼ A(G[⃗x◦ , ⃗a◦ ]) of the subgraph count on G[⃗x◦ , ⃗a◦ ] without actually making another (ℓ) call to A. Then, using the publicly known weights ∥⃗x◦ ∥ = n and ∥⃗a◦ ∥, the reduction (ℓ) (ℓ) constructs the function gℓ (·) = fH (·, ∥⃗x◦ ∥, ∥⃗a◦ ∥) = fH (·, n, ∥⃗a◦ ∥), which depends only on (ℓ) the inner product ⟨⃗x◦ , ⃗a◦ ⟩ = ⃗x, ⃗a(ℓ) . Since d(ℓ) is an estimate of the count of copies of H, the algorithm finds the value pb(ℓ) minimizing |gℓ (b p(ℓ) ) − d(ℓ) |, which it outputs as an estimate for the inner product. ⃗a(1) ⃗a(2) · · · Algorithm 2 ⃗ R G[⃗x◦ ,⃗0] ⃗x

⃗x◦

⃗ R G[⃗x◦ ,⃗1]

(1)

R1 R2 .. . R2kn R1 R2 .. . R2kn

⃗a◦

(2)

⃗a◦

Mix-and-Match (Algorithm 3)

···

⃗a(q) (q)

⃗a◦

···

d(1) p̂(1)

p̂(1) p̂(2)

···

p̂(q)

Figure 3: An outline of the reduction of Lemma 4.3. The secret vector ⃗x is accessed by the randomizers run on the query graphs G[⃗x◦ , ⃗0] and G[⃗x◦ , ⃗1]; the remaining computations are post-processing. We first show that each call to the mix-and-match subroutine produces output that faithfully simulates a call to A on the appropriate query graph G[⃗x◦ , ⃗a◦ ] (Lemma 4.7). We then use this result to analyze the full reduction, in the proof of Lemma 4.3. ⃗ P), ρ, Lemma 4.7 (Mix–and–match). Consider Algorithm 3 with parameters n, H, A = (R, and inputs ⃗a and Report. The returned value d satisfies d ∼ A(G[⃗x, ⃗a]). 19

Algorithm 2 Reduction from inner-product queries to H-counting. Parameters: Dimension n ∈ N, number of queries q ∈ N, graph H = ([k], E(H)), ⃗ P) for graphs on node set [2kn] using randomizers H-counting algorithm A = (R, ⃗ ρ = (Rv,ρ )v∈[2kn] , public randomness distribution Φ, and post-processing algorithm P. R Input: Dataset ⃗x ∈ {0, 1}n , queries ⃗a(1) , . . . , ⃗a(q) ∈ {0, 1}n . Output: Estimates pb(1) , . . . , pb(q) of ⃗x, ⃗a(1) , . . . , ⃗x, ⃗a(q) , respectively. 1: Draw and fix ρ ∼ Φ. (ℓ) 2: Let ⃗ x◦ ← ⃗x ◦ (⃗1 − ⃗x), and ⃗a◦ ← ⃗a(ℓ) ◦ ⃗0 for each ℓ ∈ [q]. ▷ ∥⃗x◦ ∥ = n, ∥⃗a(ℓ) a(ℓ) ∥ are public. ◦ ∥ = ∥⃗ 3: for each c ∈ {0, 1} do ⃗ ⃗ 4: (Report[v, c])v∈[2kn] ← Rρ G[⃗x◦ , c · 12n ] . ▷ Query secret dataset ⃗x. 5: Let Report denote the vector of the 4kn outputs produced on Line 4. 6: for each ℓ ∈ [q] do (ℓ)

d(ℓ) ← MixAndMatch 2n, H, A, ρ, ⃗a◦ , Report .

8: 9:

Define gℓ ( · ) ← fH ( · , n, ∥⃗a(ℓ) ∥). pb(ℓ) ← arg minp∈{0,...,∥⃗a(ℓ) ∥} gℓ (p) − d(ℓ) .

▷ MixAndMatch is defined in Alg. 3.

10: return p b(1) , . . . , pb(q) .

Algorithm 3 MixAndMatch Parameters: number of nodes n ∈ N, graph H = ([k], E(H)), H-counting algorithm ⃗ P) for graphs on node set [kn] using randomizers R ⃗ = (Ri,ρ )i∈[kn] , post-processing A = (R, algorithm P, public randomness ρ. Input: Query ⃗a = (a1 , . . . , an ) ∈ {0, 1}n , vector Report from randomizers run on G[⃗x, ⃗a]. Output: Estimate d of #H(G[⃗x, ⃗a]). 1: for each i ∈ [n] do 2: for each s ∈ {1, 2} do 3: r(v(s,i) ) ← Report[v(s,i) , ai ]. for each s ∈ {3, . . . , k} do r(v(s,i) ) ← Rv(s,i) ,ρ Nv(s,i) (G[⃗0, ⃗a]) . 6: return d ← P (r(v))v∈[kn] . 4: 5:

▷ d ∼ A(G[⃗x, ⃗a]) by Lemma 4.7.

Proof of Lemma 4.7. By Definition 2.6, it suffices to show that, for all nodes v(s,i) ∈ [kn], we have r(v(s,i) ) ∼ Rv(s,i) ,ρ (Nv(s,i) (G[⃗x, ⃗a])), which we show by considering each part Us . For s ∈ {1, 2}: Note that (ai · ⃗1)i = ai , so by Definition 4.4, the neighborhood of node v(s,i) is equal in G1 := G[⃗x, ai · ⃗1] and G2 := G[⃗x, ⃗a]. Thus, due to Line 3 of Algorithm 3 and Line 4 of Algorithm 2, r(v(s,i) ) = Report[v(s,i) , ai · ⃗1] ∼ Rv(s,i) ,ρ (Nv(s,i) (G1 )) = Rv(s,i) ,ρ (Nv(s,i) (G2 )). For s ∈ {3, . . . , k}: By construction, for s ∈ {3, . . . , k}, the edge list Nv(s,i) (G[⃗x, ⃗a]) is 20

independent of ⃗x. Therefore, by Line 5 of Algorithm 3, we have r(v(s,i) ) ∼ Rv(s,i) ,ρ (Nv(s,i) (G[⃗0, ⃗a])) = Rv(s,i) ,ρ (Nv(s,i) (G[⃗x, ⃗a])) . We now complete the analysis of the reduction by proving Lemma 4.3. 1 Proof of Lemma 4.3. Let A be a (1, 200 )-LNDP⋆ algorithm that achieves the stated error. By Definition 2.6, it is specified by a distribution Φ over public randomness strings ρ, ⃗ ρ , and postprocessing algorithm P. We separately show that algorithm B randomizers R 1 1 given by Algorithm 2 is (4, 25 )-DP, and that it is (α, 100 )-accurate for InnerProducts(n, q). (Privacy.) The secret vector ⃗x is accessed on Line 4 of Algorithm 2, where it is queried a total of |{⃗0, ⃗1}| = 2 times. Changing one bit of ⃗x changes two bits of ⃗x◦ , so for neighboring datasets ⃗x, ⃗x′ , the corresponding query graphs G[⃗x◦ , ⃗c], G[⃗x′◦ , ⃗c] are at node distance 2. Since 1 A is (1, 200 )-LNDP⋆ , applying its node-privacy guarantee twice shows that each output of ⃗ ρ (G[⃗x◦ , ⃗c]) is (2, 1+e )-DP. By composition (Lemma A.4) and since 2 · 1+e ≤ 1 , Algorithm 2 R 200 200 25 1 satisfies (4, 25 )-DP. (Accuracy.) The following claim establishes the error of a single estimate pb(ℓ) :

Claim 4.8. Fix ⃗a ∈ {⃗a(1), . . . , ⃗a(q) }, and let d ∼ A(G[⃗x◦ , ⃗a◦ ]). As on Line 9 of Algorithm 2, set pb = arg minp∈{0,...,∥⃗a∥} |g(p) − d|. Then E[|b p − ⟨⃗x, ⃗a⟩|] ≤ 2 · 10−5 · α. Proof of Claim 4.8. Let p = ⟨⃗x, ⃗a⟩ and wa = ∥⃗a◦ ∥ = ∥⃗a∥. Since ∥⃗x◦ ∥ = n and ⟨⃗x◦ , ⃗a◦ ⟩ = ⟨⃗x, ⃗a⟩, we have g(p) := fH (p, n, wa ) = #H(G[⃗x◦ , ⃗a◦ ]). Let eH := d − g(p) be the additive error of A on G[⃗x◦ , ⃗a◦ ]. By summing the forward differences of fH using Lemma 4.6 (with 2n ≥ 10k k ) and using the definition of p̂, we have 9 (2n)k−1 · |p̂ − p| ≤ |g(p̂) − g(p)| ≤ |g(p̂) − d| + |g(p) − d| ≤ 2|g(p) − d| ≤ 2|eH |. 10 Rearranging, taking expectations, and using the assumption on E[|eH |] in (8) gives E[|p̂ − p|] ≤

20 20 E[|eH |] ≤ · (2n)k−1 · 9 · 10−6 · α ≤ 2 · 10−5 · α. k−1 9 · (2n) 9 · (2n)k−1

To finish the proof of Lemma 4.3, let Xℓ = |b p(ℓ) − ⃗x, ⃗a(ℓ) | for all ℓ ∈ [q], and define Y = |{ℓ ∈ [q] : Xℓ > α}|. Using Claim 4.8 and applying Markov’s inequality to each Xℓ and Y gives Pr[Xℓ > α] ≤ 2 · 10−5 for all ℓ ∈ [q], so that h q i 2 · 10−5 · q 1 ≤ Pr Y > = 2 · 10−3 < . 100 q/100 100 99 That is, with probability at least 100 , we have {ℓ ∈ [q] : pb(ℓ) − ⃗a(ℓ) , ⃗x 1 (α, 100 )-accurate for InnerProducts(n, q), completing the proof.

q > α} ≤ 100 , so B is

References [AFRS26]

Maryam Aliakbarpour, Alireza Fallah, Swaha Roy, and Ria Stevens. “HighProbability Bounds For Heterogeneous Local Differential Privacy”. In: AISTATS. 2026. url: https://doi.org/10.48550/arXiv.2510.11895 (cited on p. 9).

[App23]

Apple. Learning Iconic Scenes with Differential Privacy. Online article, Apple Machine Learning Research. Published July 21, 2023. 2023. url: https : / / machinelearning . apple . com / research / scenes - differential - privacy (cited on pp. 3, 9).

[BBDS13]

Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. “Differentially private data analysis of social networks via restricted sensitivity”. In: ITCS. 2013. doi: 10.1145/2422436.2422449. url: https://doi.org/10.1145/2422436. 2422449 (cited on p. 9).

[BCSZ18]

Christian Borgs, Jennifer T. Chayes, Adam D. Smith, and Ilias Zadik. “Revealing Network Structure, Confidentially: Improved Rates for Node-Private Graphon Estimation”. In: FOCS. 2018. doi: 10.1109/FOCS.2018.00057 (cited on p. 9).

[BDK07]

Lars Backstrom, Cynthia Dwork, and Jon M. Kleinberg. “Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography”. In: WWW. 2007. doi: 10.1145/1242572.1242598. url: https://doi. org/10.1145/1242572.1242598 (cited on p. 3).

[BEM+17]

Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnés, and Bernhard Seefeld. “Prochlo: Strong Privacy for Analytics in the Crowd”. In: SOSP. 2017. doi: 10.1145/3132747.3132769. url: https://doi.org/10.1145/3132747.3132769 (cited on pp. 3, 9).

[BGL16]

Austin R. Benson, David F. Gleich, and Jure Leskovec. “Higher-Order Organization of Complex Networks”. In: Science (2016) (cited on p. 4).

[BNO08]

Amos Beimel, Kobbi Nissim, and Eran Omri. “Distributed Private Data Analysis: Simultaneously Solving How and What”. In: CRYPTO. 2008. doi: 10.1007/9783-540-85174-5_25. url: https://doi.org/10.1007/978-3-540-85174-5_25 (cited on p. 9).

[BNS19]

Mark Bun, Jelani Nelson, and Uri Stemmer. “Heavy Hitters and the Structure of Local Privacy”. In: ACM Trans. Algorithms (2019). doi: 10.1145/3344722. url: https://doi.org/10.1145/3344722 (cited on p. 9).

[BS15]

Raef Bassily and Adam D. Smith. “Local, Private, Efficient Protocols for Succinct Histograms”. In: STOC. 2015. doi: 10.1145/2746539.2746632. url: https: //doi.org/10.1145/2746539.2746632 (cited on p. 9).

[CDdHLS24]

Hongjie Chen, Jingqiu Ding, Tommaso d’Orsi, Yiding Hua, Chih-Hung Liu, and David Steurer. “Private Graphon Estimation via Sum-of-Squares”. In: STOC. 2024. doi: 10.1145/3618260.3649643. url: https://doi.org/10.1145/3618260. 3649643 (cited on p. 9).

[CDHS24]

Hongjie Chen, Jingqiu Ding, Yiding Hua, and David Steurer. “Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust”. In: NeurIPS. 2024. url: http://papers.nips.cc/paper_files/paper/2024/hash/ a51937290b8ada2dc1404ce4f9fe2c9d - Abstract - Conference . html (cited on p. 9).

[CGKM21]

Lijie Chen, Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. “On Distributed Differential Privacy and Counting Distinct Elements”. In: ITCS. 2021. doi: 10. 4230/LIPICS.ITCS.2021.56. url: https://doi.org/10.4230/LIPIcs.ITCS. 2021.56 (cited on p. 9).

[CGS26]

Clément L. Canonne, Abigail Gentle, and Vikrant Singhal. “Uniformity Testing Under User-Level Local Privacy”. In: ITCS. 2026. doi: 10.4230/LIPIcs.ITCS. 2026.33. url: https://drops.dagstuhl.de/entities/document/10.4230/ LIPIcs.ITCS.2026.33 (cited on p. 9).

[CZ13]

Shixi Chen and Shuigeng Zhou. “Recursive mechanism: towards node differential privacy and unrestricted joins”. In: SIGMOD. 2013. doi: 10 . 1145 / 2463676 . 2465304. url: https://doi.org/10.1145/2463676.2465304 (cited on pp. 4, 9).

[DJW13]

John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. “Local Privacy and Statistical Minimax Rates”. In: FOCS. 2013. doi: 10.1109/FOCS.2013.53. url: https://doi.org/10.1109/FOCS.2013.53 (cited on p. 9).

[DKMMN06]

Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. “Our Data, Ourselves: Privacy Via Distributed Noise Generation”. In: EUROCRYPT. 2006. doi: 10.1007/11761679_29. url: https://doi.org/10. 1007/11761679_29 (cited on p. 27).

[DKY17]

Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. “Collecting Telemetry Data Privately”. In: NeurIPS. 2017. url: https://proceedings.neurips.cc/ paper/2017/hash/253614bbac999b38b5b60cae531c4969-Abstract.html (cited on pp. 3, 9).

[DL09]

Cynthia Dwork and Jing Lei. “Differential privacy and robust statistics”. In: STOC. 2009. doi: 10.1145/1536414.1536466. url: https://doi.org/10.1145/ 1536414.1536466 (cited on p. 27).

[DLL16]

Wei-Yen Day, Ninghui Li, and Min Lyu. “Publishing Graph Degree Distribution with Node Differential Privacy”. In: SIGMOD. 2016. doi: 10.1145/2882903. 2926745. url: https://doi.org/10.1145/2882903.2926745 (cited on p. 9).

[DLRSSY22]

Laxman Dhulipala, Quanquan C. Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, and Shangdi Yu. “Differential privacy from locally adjustable graph algorithms: k-Core decomposition, low out-degree ordering, and densest subgraphs”. In: FOCS. 2022. doi: 10.1109/FOCS54457.2022.00077 (cited on p. 10).

[DMNS16]

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. “Calibrating Noise to Sensitivity in Private Data Analysis”. In: J. Priv. Confidentiality (2016). doi: 10.29012/jpc.v7i3.405. url: https://doi.org/10.29012/jpc.v7i3.405 (cited on pp. 3, 9, 11, 27).

[DMT07]

Cynthia Dwork, Frank McSherry, and Kunal Talwar. “The price of privacy and the limits of LP decoding”. In: STOC. 2007. doi: 10.1145/1250790.1250804. url: https://doi.org/10.1145/1250790.1250804 (cited on pp. 6, 16, 28).

[DN03]

Irit Dinur and Kobbi Nissim. “Revealing information while preserving privacy”. In: PODS. 2003. doi: 10.1145/773153.773173. url: https://doi.org/10.1145/ 773153.773173 (cited on pp. 6, 16, 28).

[DRV10]

Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. “Boosting and Differential Privacy”. In: FOCS. 2010. doi: 10.1109/FOCS.2010.12. url: https://doi.org/ 10.1109/FOCS.2010.12 (cited on p. 27).

[DZBJ18]

Xiaofeng Ding, Xiaodong Zhang, Zhifeng Bao, and Hai Jin. “Privacy-Preserving Triangle Counting in Large Graphs”. In: Proceedings of the 27th ACM International Conference on Information and Knowledge Management, CIKM 2018, Torino, Italy, October 22-26, 2018. 2018. doi: 10.1145/3269206.3271736. url: https: //doi.org/10.1145/3269206.3271736 (cited on p. 9).

[EGS03]

Alexandre Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant. “Limiting privacy breaches in privacy preserving data mining”. In: PODS. 2003. doi: 10. 1145/773153.773174. url: https://doi.org/10.1145/773153.773174 (cited on pp. 3, 9).

[ELRS25]

Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova, and Adam D. Smith. “Triangle Counting With Local Edge Differential Privacy”. In: Random Struct. Algorithms (2025). doi: 10.1002/RSA.70002. url: https://doi.org/10.1002/rsa.70002 (cited on pp. 4–6, 8, 10, 11).

[ENU20]

Alexander Edmonds, Aleksandar Nikolov, and Jonathan R. Ullman. “The power of factorization mechanisms in local and central differential privacy”. In: STOC. 2020. doi: 10.1145/3357713.3384297. url: https://doi.org/10.1145/3357713. 3384297 (cited on p. 9).

[EPK14]

Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. “RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response”. In: CCS. 2014. doi: 10.1145/ 2660267.2660348. url: https://doi.org/10.1145/2660267.2660348 (cited on pp. 3, 9).

[FDY22]

Juanru Fang, Wei Dong, and Ke Yi. “Shifted Inverse: A General Mechanism for Monotonic Functions under User Differential Privacy”. In: ACM CCS. 2022. doi: 10.1145/3548606.3560567. url: https://doi.org/10.1145/3548606.3560567 (cited on p. 9).

[FMRT25]

Vitaly Feldman, Audra McMillan, Guy N. Rothblum, and Kunal Talwar. “Local Pan-privacy for Federated Analytics”. In: ICML. 2025. url: https : / / proceedings.mlr.press/v267/feldman25a.html (cited on p. 9).

[HLMJ09]

Michael Hay, Chao Li, Gerome Miklau, and David D. Jensen. “Accurate Estimation of the Degree Distribution of Private Networks”. In: ICDM, IEEE International Conference on Data Mining. 2009. doi: 10.1109/ICDM.2009.11. url: https: //doi.org/10.1109/ICDM.2009.11 (cited on p. 9).

[HNGKTS26]

Shlomi Hod, Debanuj Nayak, Jason R. Gantenberg, Iden Kalemaj, Thomas A. Trikalinos, and Adam D. Smith. “Differentially Private Modeling of Disease Transmission within Human Contact Networks”. In: CoRR (2026). doi: 10.48550/ ARXIV . 2604 . 07493. url: https : / / doi . org / 10 . 48550 / arXiv . 2604 . 07493 (cited on pp. 3, 9).

[HSS25]

Quentin Hillebrand, Vorapong Suppakitpaisarn, and Tetsuo Shibuya. “Cycle Counting Under Local Differential Privacy for Degeneracy-Bounded Graphs”. In: STACS. 2025. doi: 10.4230/LIPICS.STACS.2025.49. url: https://doi.org/ 10.4230/LIPIcs.STACS.2025.49 (cited on pp. 4, 10).

[IMC21]

Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. “Locally Differentially Private Analysis of Graph Statistics”. In: USENIX. 2021. url: https://www. usenix.org/conference/usenixsecurity21/presentation/imola (cited on pp. 4, 10).

[IMC22]

Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. “Communication-Efficient Triangle Counting under Local Differential Privacy”. In: USENIX. 2022. url: https : / / www . usenix . org / conference / usenixsecurity22 / presentation / imola (cited on p. 10).

[JM09]

Carter Jernigan and Behram F. T. Mistree. “Gaydar: Facebook Friendships Expose Sexual Orientation”. In: First Monday (2009). url: https://doi.org/10.5210/ fm.v14i10.2611 (cited on p. 3).

[JMNR19]

Matthew Joseph, Jieming Mao, Seth Neel, and Aaron Roth. “The Role of Interactivity in Local Differential Privacy”. In: FOCS. 2019. doi: 10.1109/FOCS.2019. 00015. url: https://doi.org/10.1109/FOCS.2019.00015 (cited on p. 9).

[JSW24]

Palak Jain, Adam Smith, and Connor Wagaman. “Time-Aware Projections: Truly Node-Private Graph Statistics under Continual Observation”. In: Oakland IEEE S&P. 2024. doi: 10.1109/SP54263.2024.00196. url: https://doi.org/10. 1109/SP54263.2024.00196 (cited on p. 9).

[KLNRS11]

Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. “What Can We Learn Privately?” In: SIAM J. Comput. (2011). doi: 10.1137/090756090. url: https://doi.org/10.1137/090756090 (cited on pp. 3, 9).

[KNRS13]

Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. “Analyzing Graphs with Node Differential Privacy”. In: TCC. 2013. doi: 10.1007/978- 3- 642- 36594- 2_26. url: https://doi.org/10.1007/978- 3642-36594-2_26 (cited on pp. 4, 9).

[KRST23]

Iden Kalemaj, Sofya Raskhodnikova, Adam D. Smith, and Charalampos E. Tsourakakis. “Node-Differentially Private Estimation of the Number of Connected Components”. In: PODS. 2023. doi: 10.1145/3584372.3588671. url: https://doi.org/10.1145/3584372.3588671 (cited on p. 9).

[KRSY14]

Vishesh Karwa, Sofya Raskhodnikova, Adam D. Smith, and Grigory Yaroslavtsev. “Private Analysis of Graph Structure”. In: ACM Transactions on Database Systems (2014). doi: 10.1145/2611523 (cited on p. 9).

[Lov12]

László Lovász. Large Networks and Graph Limits. 2012. doi: 10.1090/coll/060 (cited on p. 4).

[LRSS25]

Ephraim Linder, Sofya Raskhodnikova, Adam Smith, and Thomas Steinke. “Privately Evaluating Untrusted Black-Box Functions”. In: STOC. 2025. doi: 10. 1145/3717823.3718247. url: https://doi.org/10.1145/3717823.3718247 (cited on p. 9).

[MPSL25]

Pranay Mundra, Charalampos Papamanthou, Julian Shun, and Quanquan C. Liu. “Practical and Accurate Local Edge Differentially Private Graph Algorithms”. In: Proc. VLDB Endow. (2025). url: https://www.vldb.org/pvldb/vol18/p4199mundra.pdf (cited on p. 10).

[MS06]

Nina Mishra and Mark Sandler. “Privacy via pseudorandom sketches”. In: PODS. 2006. doi: 10 . 1145 / 1142351 . 1142373. url: https : / / doi . org / 10 . 1145 / 1142351.1142373 (cited on p. 9).

[MSIKCA02]

Ron Milo, Shalev Shen-Orr, Shai Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. “Network Motifs: Simple Building Blocks of Complex Networks”. In: Science (2002) (cited on p. 4).

[NRS07]

Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. “Smooth sensitivity and sampling in private data analysis”. In: STOC. 2007. doi: 10.1145/1250790. 1250803. url: https://doi.org/10.1145/1250790.1250803 (cited on pp. 4, 9).

[QYYKXR17]

Zhan Qin, Ting Yu, Yin Yang, Issa Khalil, Xiaokui Xiao, and Kui Ren. “Generating Synthetic Decentralized Social Graphs with Local Differential Privacy”. In: ACM CCS. 2017. doi: 10.1145/3133956.3134086. url: https://doi.org/10.1145/ 3133956.3134086 (cited on p. 10).

[RHMS09]

Vibhor Rastogi, Michael Hay, Gerome Miklau, and Dan Suciu. “Relationship privacy: output perturbation for queries with joins”. In: PODS. 2009. doi: 10. 1145/1559795.1559812. url: https://doi.org/10.1145/1559795.1559812 (cited on p. 9).

[RS16a]

Sofya Raskhodnikova and Adam D. Smith. “Differentially Private Analysis of Graphs”. In: Encyclopedia of Algorithms. 2016. doi: 10.1007/978-1-4939-28644_549 (cited on p. 9).

[RS16b]

Sofya Raskhodnikova and Adam D. Smith. “Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism”. In: FOCS. 2016. doi: 10.1109/FOCS.2016.60. url: https://arxiv.org/pdf/1504.07912.pdf (cited on p. 9).

[RSWZ26]

Sofya Raskhodnikova, Adam D. Smith, Connor Wagaman, and Anatoly Zavyalov. “Local Node Differential Privacy”. In: FOCS. 2026. doi: 10.48550/ARXIV.2602. 15802. url: https://doi.org/10.48550/arXiv.2602.15802 (cited on pp. 3, 5, 9–11).

[SPHH25]

Vorapong Suppakitpaisarn, Donlapark Ponnoprat, Nicha Hirankarn, and Quentin Hillebrand. “Counting Graphlets of Size k under Local Differential Privacy”. In: AISTATS. 2025. url: https://proceedings.mlr.press/v258/suppakitpaisarn25a. html (cited on pp. 4, 5, 8, 10).

[SU21]

Adam Sealfon and Jonathan R. Ullman. “Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy”. In: J. Priv. Confidentiality (2021). doi: 10.29012/JPC.745. url: https://doi.org/10.29012/jpc.745 (cited on p. 9).

[War65]

Stanley L. Warner. “Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias”. In: Journal of the American Statistical Association (1965). url: http://www.jstor.org/stable/2283137 (cited on pp. 9, 11).

[WS98]

Duncan J. Watts and Steven H. Strogatz. “Collective Dynamics of ‘Small-World’ Networks”. In: Nature (1998) (cited on p. 4).

Appendix A

Background on Differential Privacy

This section collects useful background on differential privacy, including common mechanisms and standard properties of the definition. A common way to release a function’s value under differential privacy is to use noise scaled to its sensitivity. Definition A.1 (Sensitivity). Let k ∈ N and f : X → Rk be a function. Let p ∈ {1, 2}. The ℓp -sensitivity of f , denoted by ∆p , is defined as ∆p = maxx∼y ∥f (x) − f (y)∥p . Lemma A.2 (Laplace mechanism [DMNS16]). Let k ∈ N and ε > 0 and f : X n → Rk be a function with ℓ1 -sensitivity ∆1 . The Laplace mechanism is defined as A(x) = f (x) + (Z1 , . . . , Zk ), where the Zi ∼ Lap(∆1 /ε) are independent for all i ∈ [k]. The Laplace mechanism is (ε, 0)-DP. Differential privacy is robust to postprocessing (i.e., the application of an arbitrary randomized algorithm to the output of a differentially private algorithm), and its parameters degrade gracefully under composition. Lemma A.3 (DP is robust to postprocessing [DMNS16]). Let M : U ∗ → Y be a randomized algorithm that is (ε, δ)-DP. Let f : Y → Z be a randomized function. Then f ◦ M : U ∗ → Z is (ε, δ)-DP. Lemma A.4 (Basic composition [DL09; DRV10; DKMMN06]). Let ε1 , ε2 > 0 and δ1 , δ2 ∈ [0, 1). Let A1 : U ∗ → Y be an (ε1 , δ1 )-DP algorithm and let A2 : U ∗ ×Y → Z be an (ε2 , δ2 )-DP algorithm. Then for all x ∈ U ∗ , algorithm A2 (x, A1 (x)) is (ε1 + ε2 , δ1 + δ2 )-DP.

Error Required for Private Inner Product Queries

We provide a proof sketch of Lemma 4.2, restated below for convenience.

Lemma 4.2 (Inner product lower bound, based on [DN03], [DMT07, Theorem 23]). There exist algorithm B is √ c1 ,1c2 > 0 such that, for sufficiently large n ∈ N, if a randomized 1 (c1 n, 100 )-accurate for InnerProducts(n, c2 n), then B is not (4, 25 )-DP. queries a ∈ {±1}n Proof sketch of Lemma 4.2. [DMT07, Theorem 23] considers inner product√ and shows that, for sufficiently large n, there exist m = Θ(n) and α = Ω( n) such that the following holds with probability at least 1 − e−cn for some constant c > 0. If an algorithm B answers at least a 45 fraction of uniformly random inner product queries with additive error 99 at most α, then there is an efficient attacker A that reconstructs at least a 100 fraction of the n bits of a uniformly random input x ∈ {0, 1} from the outputs of B alone. Since no adversary 99 can reconstruct a 100 fraction of the bits in a uniformly random input based only on the 1 outputs of a (4, 25 )-DP algorithm, Lemma 4.2 follows. Translating from the [DMT07] setting of a ∈ {±1}n to our setting of a ∈ {0, 1}n only introduces a factor of 2 in the α term.

Subgraph Counting with Local Node Differential Privacy

Analyze & explore related research in Conceptio

Related documents