Counting Graphlets of Size $k$ under Local Differential Privacy

Donlapark Ponnoprat; Nicha Hirankarn; Quentin Hillebrand; Vorapong Suppakitpaisarn

REVIEW 1 major objections 6 minor 24 references

Counting Graphlets of Size $k$ under Local Differential Privacy

T0 review · 1 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper shows that counting any k-node graphlet under edge local differential privacy can be done by a non-interactive randomized-response algorithm with expected ℓ2 error O(n^{k−1}), and that matching lower bounds make this…

desk verdict A solid upper bound and matching non-interactive lower bound for k-node graphlet counting under edge LDP, but the any-algorithm lower bound for cycles is not established as written due to an overcounting error in Eq. (2). read the letter →

arxiv 2505.12954 v1 pith:TA4KBNCD submitted 2025-05-19 cs.SI cs.CCcs.DS

Vorapong Suppakitpaisarn , Donlapark Ponnoprat , Nicha Hirankarn , Quentin Hillebrand This is my paper · ORCID

classification cs.SIcs.CCcs.DS

keywords graphletcountinglocaldifferentialprivacyedgerandomizedresponsesubgraphexpectedl2errorlowerboundsk-clique

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper attacks the problem of counting graphlets—small subgraphs of a fixed size k—when each user in a network obfuscates their own adjacency information before sending it to a server. The central claim is that a non-interactive algorithm based on randomized response can count any k-node graphlet with expected ℓ2 error O($n^{{k−1}}$), where n is the number of nodes. The paper also proves matching lower bounds: for a constructed class of graphs and graphlets, any non-interactive algorithm must pay Ω($n^{{k−1}}$), and for k-cycles any algorithm at all must pay Ω($n^{{k−1.5}}$). If correct, this makes the debiased randomized-response estimator asymptotically optimal among non-interactive edge-local-differential-privacy mechanisms and shows exactly how much accuracy is lost as graphlets grow by one node.

What carries the argument

The load-bearing object is the automorphism-corrected tuple estimator $\tilde G_k(G) = \frac{1}{A(\mathcal G)} \sum_{W \in D} \prod_{\{u_i,u_j\} \in E(\mathcal G)} \hat a_{\ell_i,\ell_j}$, where $A(\mathcal G)$ is the number of automorphisms of the target graphlet, $D$ is the set of ordered $k$-tuples of distinct vertices, and $\hat a_{i,j} = \frac{e^\epsilon+1}{e^\epsilon-1}\tilde a_{i,j} - \frac{1}{e^\epsilon-1}$ is the debiased randomized-response bit. The variance analysis works by bounding the number of tuple pairs whose products share a randomized bit, yielding at most $O(n^{2k-2})$ nonzero covariance pairs. The lower bounds run through two reductions: a gadget in which the $k$-clique count is exactly $(n/3)^{k-3}$ times the triangle count of a smaller graph, and a cycle-counting gadget whose $k$-cycle count is expressed as a function of the number of present matching edges, which is then fed through a known sum-of-bits lower bound for local differential privacy.

What would settle it

Take the Section 5 construction with $n=6$ or $n=8$, enumerate all $k$-cycles in $G_x$ for every bit vector $x$, and check whether the difference $C_k(G_x)-C_k(G_{x'})$ equals exactly $(|x|-|x'|)C_1$ plus the higher binomial terms predicted by equation (2) with $C_1=\Theta(n^{k-2})$. Any mismatch falsifies Lemma 5.1 and with it the $\Omega(n^{k-1.5})$ lower bound.

Watch

Extended reading notes

Core claim

The paper's central result is Theorem 3.4: for any graphlet $\mathcal G$ with $k$ nodes, the estimator produced by debiasing randomized-response edge bits and summing products of those bits over all ordered $k$-tuples of distinct vertices, divided by the number of automorphisms of $\mathcal G$, is unbiased and has expected $\ell_2$ error $O(n^{k-1})$. This is matched by Theorem 4.1, which constructs a class of graphs where counting $k$-cliques forces $\Omega(n^{k-1})$ error for every non-interactive edge-local-differentially-private algorithm, and by Theorem 5.3, which shows that counting $k$-cycles forces $\Omega(n^{k-1.5})$ error for any edge-local-differentially-private algorithm. Read together, the three theorems establish that the estimator is worst-case optimal among non-interactive mechanisms and quantify the privacy cost of moving from triangles to larger graphlets.

Load-bearing premise

The Section 5 lower bound assumes that the number of $k$-cycles in its gadget graph is given exactly by $C_k(G_0) + \sum_{p=1}^{|x|} \binom{|x|}{p} C_p$ with $C_1 = \Theta(n^{k-2})$; if this decomposition is not exact, the reduction from cycle counting to privately estimating a sum of bits collapses.

Editorial extensions

If this is right

For every fixed $k$, the expected $\ell_2$ error of the released graphlet count grows like $n^{k-1}$, so each extra node in the graphlet multiplies the worst-case error by roughly $n$.
No non-interactive edge-local-differentially-private mechanism can asymptotically beat this on the constructed clique instances, so the debiased estimator is worst-case optimal for non-interactive protocols.
Even interactive protocols suffer $\Omega(n^{k-1.5})$ error on $k$-cycles, showing that interactivity alone does not remove the privacy cost of large graphlets.
On the tested 4-cycle instances, the algorithm's root-mean-square error is up to 36 times smaller than plain randomized response at $n=100$, and the reported advantage grows with $n$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The matching non-interactive lower bound is proven on cliques and the any-algorithm lower bound on cycles, so the paper does not settle whether every $k$-node graphlet shape inherits the same worst-case floor; special shapes may admit smaller error.
Because the server-side cost is $O(n^k)$ while the variance target is $O(n^{2k-2})$, a sampling scheme that evaluates the estimator on a random subset of $k$-tuples could plausibly cut the runtime without changing the leading error rate, as long as the sampled covariance structure stays within the same budget.
Treating $\epsilon$ as a constant hides how the error depends on the privacy budget; deriving the $\epsilon$-dependence of the upper and lower bounds would let practitioners choose between the debiased estimator and releasing a fully obfuscated graph.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: the paper is worth reading for the upper bound in Section 3; the any-algorithm lower bound in Section 5 is not correct as written, though likely fixable. The stress-test note points to the right spot.

The new result that matters is a non-interactive epsilon-edge-LDP algorithm that estimates the number of any k-node graphlet with expected L2 error O(n^{k-1}), plus a matching Omega(n^{k-1}) lower bound for non-interactive algorithms on k-cliques. The algorithm is a clean generalization of Eden et al.'s unbiased randomized response estimator; normalizing by the automorphism count is the right move. The variance analysis in Section 3 is basically sound. Lemma 3.3 has some garbled notation, but the covariance bound O(n^{2k-2}) is correct, so the upper bound stands. The non-interactive lower bound via the triangle gadget from Eden et al. is a credible reduction; the appendix proof is terse, but the key step (K_k count is (n/3)^{k-3} times the triangle count) checks out.

The soft spot is Section 5. C_p is defined as the number of cycles that include all edges of a fixed p-subset E_p of the matching edges. Under that literal definition, the term C(|x|,p)C_p overcounts every cycle that uses more than p matching edges, so Eq. (2) is not a valid partition. If the intended definition is cycles whose intersection with the matching is exactly E_p, then Eq. (2) works and Lemma 5.1 goes through, but then C_1 = Theta(n^{k-2}) still needs an actual derivation instead of a one-line assertion. As written, Theorem 5.3 rests on an unproven decomposition. This looks repairable, and the result may be true, but a referee should insist on the fix.

Minor issues: Theorem 4.1 writes 'Let n = k*n/3', overloading n in a confusing way; Lemma 3.3 has indexing typos; the experiments are tiny (n <= 100, epsilon 1 and 5), though the authors acknowledge this and the code is public. Citations to the relevant triangle and interactivity lower bounds look appropriate.

Bottom line: send it to referees. The upper bound and non-interactive lower bound are solid; Section 5 needs a corrected definition and a real proof of C_1 before that claim can be relied on.

Referee Report

1 major / 6 minor

Summary. The paper proposes a non-interactive, edge-local differentially private algorithm that estimates the number of occurrences of any k-node graphlet in an n-node graph, and proves an O(n^{k-1}) upper bound on the expected L2 error. It also proves a matching Omega(n^{k-1}) lower bound for non-interactive algorithms on a specific family of graphs, and an Omega(n^{k-1.5}) lower bound for all edge-LDP algorithms when the graphlet is a k-cycle. The upper bound is established through an unbiased estimator based on randomized response and automorphism normalization; the lower bounds use reductions to prior triangle-counting and sum-of-bits lower bounds. Experimental results on synthetic graphs compare the algorithm against classical randomized response.

Significance. If all three results hold, the paper substantially generalizes the triangle-counting LDP bounds of Eden et al. to arbitrary graphlets and settles the worst-case L2 error of non-interactive algorithms. The upper-bound construction is clean and directly useful: the automorphism-based unbiased estimator is a natural generalization of the triangle estimator, and the variance analysis via dependence counting is sound in spirit. The paper also ships code and gives reproducible synthetic experiments, which strengthens its practical claims. However, the significance is conditional on the Section 5 lower bound being repaired, since the current definition of C_p in Eq. (2) breaks the reduction.

major comments (1)

[Section 5, Eq. (2) and Lemma 5.1] The definition of C_p as "the number of k-cycles in G_x that include all edges in E_p" is ambiguous, and under the literal reading (cycles containing E_p as a subset) Eq. (2) is false: a k-cycle that uses q>p matching edges is counted once for every p-subset of its matching edges, so the right-hand side of Eq. (2) overcounts as soon as |x| >= 2. Because Lemma 5.1 and Theorem 5.3 rely entirely on the exactness of Eq. (2), the Omega(n^{k-1.5}) lower bound is not established as written. The fix is to define C_p as the number of k-cycles whose intersection with E_x^0 is exactly E_p (or to replace Eq. (2) by an inclusion-exclusion identity that accounts for cycles using more than p matching edges), and then to give a rigorous proof of Lemma 5.1, including a derivation of C_1 = Theta(n^{k-2}). As currently written, the proof of Lemma 5.1 is a single line and the asserted count C_1 = Theta(n^{k-2}) is not justified.

minor comments (6)

[Section 4 and Appendix 8] The variable n is used both for the size of each partition U, Y, W_p and for the total number of nodes in G^{mu,upsilon}_k(X); the statement "Let n = k*n/3" in Theorem 4.1 (and Theorem 8.4) is self-contradictory. The scaling argument in the lower-bound proof is correct only if one distinguishes N = k*n/3 (total nodes) from the part size n. Please introduce a separate symbol for the total number of nodes and restate the theorem, the proof, and the reduction accordingly.
[Lemma 3.3 proof] The proof of Lemma 3.3 uses the letter k both for the graphlet size and for the size of the union set in the double sum, resulting in expressions such as sum_{k=k}^{2k-2} and binomial coefficients with inconsistent arguments. This makes the proof hard to follow; the union size should be denoted by a fresh symbol (e.g., s).
[Section 4 informal proof] The informal argument in Section 4 says that if a K_k estimator existed, "we could divide the result by (n/3)^{k-3}" to get a triangle estimator; this assumes the estimator is linear in the triangle count. The formal reduction in Appendix 8 uses the more careful construction h(C), so the main text should refer to that construction instead of stating the naive division argument.
[Section 4 and Appendix, minor typos] There are several typographical issues: "We have k set of nodes" should be "We have k sets of nodes"; Lemma 8.2 states "The number of k-clique in the graph G^{mu,upsilon}(X)" where it should refer to G^{mu,upsilon}_k(X); and in the abstract and some equations the Omega and O symbols appear with stray spaces.
[Section 6 experiments] The experimental section reports RMSE computed over ten runs but does not report variability across independent repetitions of the experiment, so it is unclear how stable the reported improvements are. The claim "up to 36 times smaller" is based on a single setting (n=100, stochastic block model, epsilon=1) and should be stated as such. Additionally, randomized response is a weak baseline; since no specialized graphlet-counting LDP baseline exists, this comparison should be framed as a sanity check rather than evidence of practical superiority.
[Section 2.3 and checklist] The checklist in Section 2(a) answers "Not applicable" with the justification that the results apply to the general case and require no specific assumptions; however, the lower-bound theorems in Sections 4 and 5 do rely on specific graph classes (the gadget graphs and the cycle-counting graphs). The checklist should acknowledge these assumptions.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: estimate and lower bounds are built from first-principles algebra, automorphism counting, and external lower bounds.

full rationale

The paper's central contribution is the non-interactive estimator in Algorithm 1. Its unbiasedness is derived directly from independence of the randomized-response variables and from the automorphism identity G(G)=W(G,G)/A(G) (Lemma 3.1 and Lemma 3.2). The variance bound is a combinatorial covariance count over tuples (Lemma 3.3 and Theorem 3.4), not a repackaged input or a fitted constant. The lower bounds are reductions to independent, externally authored results: Section 4 reduces K_k-counting in the gadget to the triangle-counting lower bound of Eden et al. (ICALP 2023), and Section 5 reduces C_k-counting to the sum-of-bits lower bound of Joseph et al. (FOCS 2019). Neither load-bearing lower bound is a self-citation: Eden et al. and Joseph et al. share no authors with this paper. The self-citations appearing in the related-work and contextual passages (Hillebrand et al., Betzer et al.) are not used to justify the main theorems. No parameter is fitted to a subset of data and then renamed a prediction, and no quantity is defined in terms of the quantity it is used to derive. There is one notable mathematical concern in Section 5: the decomposition f(|x|)=C_k(G_0)+\sum_p C(|x|,p)C_p is asserted with C_p defined as the number of k-cycles 'that include all edges in E_p', which can double-count cycles containing more than one matching edge. That issue is a proof gap or an ambiguity in a definition, not a circularity: correcting it by redefining C_p as cycles using exactly a fixed edge set would preserve the reduction. Because the alleged circularity patterns are absent, the appropriate finding is no significant circularity; the manuscript is self-contained against external benchmarks for both the upper and lower bounds.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No free parameters are fitted. The algorithm depends only on the standard randomized response mechanism; the lower bounds are built on two external lower-bound theorems (Eden et al. for triangles, Joseph et al. for sum of bits). The analysis treats k and ε as constants and counts non-induced subgraphs. No new entities are postulated.

assumptions (6)

standard math Randomized response with flip probability 1/(1+e^ε) is ε-edge LDP (Definition 4).
Used in Algorithm 1 to obfuscate adjacency vectors; the privacy guarantee of the whole algorithm rests on this standard mechanism.
standard math The adjusted estimator \hat a_{ij} = (e^ε+1)/(e^ε-1)\tilde a_{ij} - 1/(e^ε-1) is unbiased, i.e. E[\hat a_{ij}] = a_{ij}.
A two-line expectation calculation from the randomized response probabilities; it is the basis of Lemma 3.2.
domain assumption Eden et al. non-interactive triangle-counting lower bound: any non-interactive ε-edge LDP triangle counter has expected L2 error Ω(n^2) on their gadget class (Theorem 8.1).
Used as the black-box starting point for the non-interactive lower bound for K_k counting in Section 4.
domain assumption Joseph et al. lower bound: no LDP algorithm can estimate the sum of n bits with expected L2 error o(√n) (Theorem 5.2).
Used as the black-box starting point for the any-algorithm lower bound for cycle counting in Section 5.
domain assumption k is a fixed constant independent of n, and ε is treated as constant.
The variance bounds use O(k^2)=O(1), and the paper states in Section 7 that ε is treated as a constant in the asymptotic results.
domain assumption Graphlet count is defined as non-induced subgraph count, not induced subgraph count.
Section 2.1 defines the count as subgraphs (V',E') ⊆ G isomorphic to G; the algorithm and lower bounds count non-induced copies, which differs from the common 'graphlet' convention in network science.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Counting Graphlets of Size $k$ under Local Differential Privacy." pith.science (2026). https://pith.science/paper/TA4KBNCD

@misc{pith2026250512954,
  author       = {Pith},
  title        = {Pith review of: Counting Graphlets of Size $k$ under Local Differential Privacy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TA4KBNCD}},
  note         = {Machine review of arXiv:2505.12954}
}

abstract

The problem of counting subgraphs or graphlets under local differential privacy is an important challenge that has attracted significant attention from researchers. However, much of the existing work focuses on small graphlets like triangles or $k$-stars. In this paper, we propose a non-interactive, locally differentially private algorithm capable of counting graphlets of any size $k$. When $n$ is the number of nodes in the input graph, we show that the expected $\ell_2$ error of our algorithm is $O(n^{k - 1})$. Additionally, we prove that there exists a class of input graphs and graphlets of size $k$ for which any non-interactive counting algorithm incurs an expected $\ell_2$ error of $\Omega(n^{k - 1})$, demonstrating the optimality of our result. Furthermore, we establish that for certain input graphs and graphlets, any locally differentially private algorithm must have an expected $\ell_2$ error of $\Omega(n^{k - 1.5})$. Our experimental results show that our algorithm is more accurate than the classical randomized response method.

Figures

Figures reproduced from arXiv: 2505.12954 by the authors.

**Figure 2.** We found that our algorithm significantly [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Relative root mean square error of our Algo [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: (a) Computation time of our Algorithm 1 as a function of the number of nodes (b) Standard deviation of our results for graphs derived from the stochastic block model when the privacy budget is set to one. Next, we address the computation time of our algorithm, which r…

**Figure 5.** Figure 5: Gadget used in [Eden et al., 2023] for showing the lower bound in [PITH_FULL_IMAGE:figures/full_fig_p013_5.png]

**Figure 6.** Figure 6: The gadget we use to show the lower bound of [PITH_FULL_IMAGE:figures/full_fig_p015_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

[1]

[Yes, we outline the setting and the algorithm in Sections 2 and 3.] (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm

For all models and algorithms presented, check if you include: (a) A clear description of the mathematical set- ting, assumptions, algorithm, and/or model. [Yes, we outline the setting and the algorithm in Sections 2 and 3.] (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm. [Yes, we analyze the privacy of our al...

work page
[2]

[Not applicable

For any theoretical claim, check if you include: (a) Statements of the full set of assumptions of all theoretical results. [Not applicable. Our algorithm and lower bounds apply to the gen- eral case, so no specific assumptions are re- quired.] (b) Complete proofs of all theoretical results. [Yes. We provide the proofs for all theoret- ical results in Sect...

work page
[3]

For all figures and tables that present empirical results, check if you include: (a) The code, data, and instructions needed to reproduce the main experimental results (ei- ther in the supplemental material or as a URL). [Yes. We provide the code and the instructions as a supplemental material. The data is synthesized from the code.] (b) All the training ...

work page
[4]

[Not Applicable

If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include: (a) Citations of the creator If your work uses ex- isting assets. [Not Applicable. We do not use any existing asset in this work.] (b) The license information of the assets, if ap- plicable. [Not Applicable. We do not use any existing asset ...

work page
[5]

Counting Graphlets of Size k under Local Differential Privacy

If you used crowdsourcing or conducted research with human subjects, check if you include: (a) The full text of instructions given to partici- pants and screenshots. [Not Applicable. We do not conduct any experiment with human subjects.] (b) Descriptions of potential participant risks, with links to Institutional Review Board (IRB) approvals if applicable...

work page 2023
[6]

Let the sets of nodes in each partition be U = {u1,...,u n/3}, Y = {y1,...,y n/3}, and W ={w1,...,w n/3}

The graph is a tripartite graph. Let the sets of nodes in each partition be U = {u1,...,u n/3}, Y = {y1,...,y n/3}, and W ={w1,...,w n/3}

work page
[7]

For each pair i,j , there is an edge between ui andyj if Xi,j = 1; otherwise, there is no edge between them

work page
[8]

For each i, there is an edge between ui andwj for all j ifµi = 1; otherwise, there is no edge between them

work page

Show all 24 references

[9]

We illustrate the gadget in Figure 5

For each i, there is an edge between yi andwj for all j ifυi = 1; otherwise, there is no edge between them. We illustrate the gadget in Figure 5. Figure 5: Gadget used in [Eden et al., 2023] for showing the lower bound in ℓ2-error of estimating the number of triangles. Countin...

2023
[10]

The node then sends the result Lv(av) to a central server

Each node v applies an ϵ-differential privacy algorithm, denoted byLv (referred to as a randomizer), to its adjacency vector av. The node then sends the result Lv(av) to a central server
[11]

Let us now recall the graph Gµ,υ(X)

The central server applies an aggregator functionA to the collected results from all randomizers and outputs A (⟨Lv(av)⟩v∈V ) as the final result. Let us now recall the graph Gµ,υ(X). For a node ui, we denote its adjacency vector in the graph as aui(µ,υ, X). Given any vectors ...

2023
[12]

The node then sends the results to the central server

For each ui∈ U, the node ui applies the algorithm Lui to the adjacency vectors aui(0, X) and aui(1, X). The node then sends the results to the central server. Let these results be Lui(0) and Lui(1). Since the node publishes two results, this process is 2 ϵ-differentially private
[13]

The node then sends the results to the central server

For each yi∈ Y , the node yi applies the algorithm Lyi to the adjacency vectors ayi(0, X) and ayi(1, X). The node then sends the results to the central server. Let these results be Lyi(0) and Lyi(1). Since the node publishes two results, this process is 2 ϵ-differentially private
[14]

Then, the user sends the result to the central server

Then, for all graphs in SX ={Gµ(1),υ(1) (X),...,G µ(N),υ(N) (X)}: (a) Each user wi first applies the randomized algorithm Lwi to its adjacency vector awi(µ(1),υ (1), X),..., awi(µ(N),υ (N), X). Then, the user sends the result to the central server. Note that all edges incident...

2023
[15]

Vorapong Suppakitpaisarn1, Donlapark Ponnoprat 1, Nicha Hirankarn, Quentin Hillebrand Graph Gµ,υ k (X) For eachGµ,υ(X), we construct the graph Gµ,υ k (X) by the following steps:

(3) 8.2 Our Construction We define our construction in this subsection. Vorapong Suppakitpaisarn1, Donlapark Ponnoprat 1, Nicha Hirankarn, Quentin Hillebrand Graph Gµ,υ k (X) For eachGµ,υ(X), we construct the graph Gµ,υ k (X) by the following steps:
[16]

All of the sets have size n/3

We have k set of nodes U, Y, W1,..., Wk−2. All of the sets have size n/3. Let U ={u1,..., un/3}, Y = {y1,..., yn/3}, and Wp ={wp,1,..., wp,n/3} for all 1 ≤ p≤ k− 2. The number of nodes in the graph, denoted by n, is then equal to k·n/3
[17]

We have{ui, yj}∈ E if Xi,j = 1
[18]

We have{ui, wp,j}∈ E for all p,j if µi = 1
[19]

We have{wp,i, wq,j}∈ E for all i, j, and p̸=q
[20]

Our gadget is shown as in Figure 6

We have{yi, wp,j}∈ E for all p,j if υi = 1. Our gadget is shown as in Figure 6. Figure 6: The gadget we use to show the lower bound of ℓ2-error when counting K4. By the construction, we obtain the following lemma. Lemma 8.2. LetK3(Gµ,υ(X)) be the number of triangles in the gra...
[21]

The node then sends the result Lv(av) to a central server

Each node v applies an ϵ-differential privacy algorithm, denoted by Lv (referred to as a randomizer), to its adjacency vector av. The node then sends the result Lv(av) to a central server
[22]

Counting Graphlets of Size k under Local Differential Privacy Let us now recall the graph Gµ,υ(X)

The central server applies an aggregator functionA to the collected results from all randomizers and outputs A (⟨Lv(av)⟩v) as the final result. Counting Graphlets of Size k under Local Differential Privacy Let us now recall the graph Gµ,υ(X). For a node ui ∈ U, we denote its a...
[23]

It can then compute Lui(µi, X) according to the construction C

For each ui∈U, given µi, the user possesses sufficient information to construct the adjacency vector of the node ui∈ U. It can then compute Lui(µi, X) according to the construction C. In the construction h(C), we haveLui(µi, X) = Lui(µi, X). Similarly, the node yi∈Y returnsLyi...
[24]

The server then estimates the number of triangles as A(⟨Lv(a)⟩v) = A (⟨Lv(av)⟩v)/(n/3)k−3

The central server calculate Lwi,j(µ,υ ) for all i andj. The server then estimates the number of triangles as A(⟨Lv(a)⟩v) = A (⟨Lv(av)⟩v)/(n/3)k−3. By the construction, we obtain the following lemma. Lemma 8.3. Given µ,υ, and X. Let C be a non-interactive ϵ-edge differentially...

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [1]

[Yes, we outline the setting and the algorithm in Sections 2 and 3.] (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm

For all models and algorithms presented, check if you include: (a) A clear description of the mathematical set- ting, assumptions, algorithm, and/or model. [Yes, we outline the setting and the algorithm in Sections 2 and 3.] (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm. [Yes, we analyze the privacy of our al...

work page

[2] [2]

[Not applicable

For any theoretical claim, check if you include: (a) Statements of the full set of assumptions of all theoretical results. [Not applicable. Our algorithm and lower bounds apply to the gen- eral case, so no specific assumptions are re- quired.] (b) Complete proofs of all theoretical results. [Yes. We provide the proofs for all theoret- ical results in Sect...

work page

[3] [3]

For all figures and tables that present empirical results, check if you include: (a) The code, data, and instructions needed to reproduce the main experimental results (ei- ther in the supplemental material or as a URL). [Yes. We provide the code and the instructions as a supplemental material. The data is synthesized from the code.] (b) All the training ...

work page

[4] [4]

[Not Applicable

If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include: (a) Citations of the creator If your work uses ex- isting assets. [Not Applicable. We do not use any existing asset in this work.] (b) The license information of the assets, if ap- plicable. [Not Applicable. We do not use any existing asset ...

work page

[5] [5]

Counting Graphlets of Size k under Local Differential Privacy

If you used crowdsourcing or conducted research with human subjects, check if you include: (a) The full text of instructions given to partici- pants and screenshots. [Not Applicable. We do not conduct any experiment with human subjects.] (b) Descriptions of potential participant risks, with links to Institutional Review Board (IRB) approvals if applicable...

work page 2023

[6] [6]

Let the sets of nodes in each partition be U = {u1,...,u n/3}, Y = {y1,...,y n/3}, and W ={w1,...,w n/3}

The graph is a tripartite graph. Let the sets of nodes in each partition be U = {u1,...,u n/3}, Y = {y1,...,y n/3}, and W ={w1,...,w n/3}

work page

[7] [7]

For each pair i,j , there is an edge between ui andyj if Xi,j = 1; otherwise, there is no edge between them

work page

[8] [8]

For each i, there is an edge between ui andwj for all j ifµi = 1; otherwise, there is no edge between them

work page