{"id":"658b8300-ae9c-4cb5-bdd2-035ec5e0afe7","arxiv_id":"2505.12954","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An edge-local differentially private algorithm counts arbitrary k-node graphlets with expected L2 error O(n^{k-1}), matching lower bounds for non-interactive methods and a Ω(n^{k-1.5}) bound for all methods.","lead":"This paper gives a privacy-preserving algorithm for counting small subgraph patterns in a network, with error that grows polynomially in the network size. It also proves this error is essentially the best any such private method can achieve, and that allowing interaction does not help much for cycle counts.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (2) in Section 5 misdefines C_p: 'include all edges in E_p' double-counts cycles with multiple matching edges, so Lemma 5.1 and Theorem 5.3 rest on an unproven decomposition.","rationale":"The paper's central non-interactive result (Algorithm 1 with O(n^{k-1}) error and the matching Ω(n^{k-1}) non-interactive lower bound in Section 4) appears sound: the unbiased estimator, the variance calculation via Lemma 3.3, and the reduction from K_k counting to triangle counting are all internally consistent, modulo notation overloads. The reader's weakest-assumption identification is correct: Section 5's any-algorithm lower bound rests on Lemma 5.1, and the proof of Lemma 5.1 is not rigorous as written. My analysis shows the problem is more specific than a missing derivation: under the paper's stated definition of C_p ('include all edges in E_p'), Eq. (2) is false because it double-counts cycles that contain more than p matching edges. The lower-bound argument can be repaired by redefining C_p as the exact number of cycles whose set of matching edges is precisely E_p; with that definition, the partition is exact, C_p depends only on p by symmetry, and C_1=Θ(n^{k-2}) holds by a straightforward counting argument. The fact that the fix is simple, and that the upper bound and Section 4 lower bound are unaffected, means the appropriate verdict remains conditional rather than reject. I therefore agree with the reader's CONDITIONAL verdict and recommend no change. The concrete brute-force test on small n,k would settle whether the authors intended the exact definition and whether Eq. (2) can be certified after a one-line clarification.","tokens_in":18683,"tokens_out":26913,"duration_ms":269063,"concrete_test":"Fix small parameters, e.g., n=8, k=4. For every x∈{0,1}^4, build G_x and brute-force enumerate all 4-cycles to obtain C_4(G_x). Then compute the right-hand side of Eq. (2) using the paper's literal definition of C_p: for one fixed p-subset E_p of E_x^0 (any such subset, by symmetry), count all cycles containing all edges of E_p, and multiply by C(|x|,p). Sum over p. Compare with C_4(G_x); if they differ for any x with |x|≥2, the decomposition as stated is false. Then recompute with C_p redefined as the number of cycles whose intersection with E_x^0 is exactly E_p, and verify equality for all x. This distinguishes a genuine combinatorial error from an ambiguous but repairable definition.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The any-algorithm lower bound (Theorem 5.3) depends on Lemma 5.1, which uses the decomposition f(|x|)=C_k(G_0)+Σ_{p=1}^{|x|} C(|x|,p)C_p (Eq. 2). But C_p is defined as 'the number of k-cycles in G_x that include all edges in E_p'—i.e., cycles containing E_p as a subset. Under that literal definition, the term C(|x|,p)C_p counts each cycle with q>p matching edges once for every p-subset of its matching-edge set, so Eq. (2) overcounts as soon as |x|≥2. The subsequent identity in Lemma 5.1, C_k(G_x)-C_k(G_{x'})=(|x|-|x'|)C_1+..., is therefore not valid as written. If C_p were instead defined as the number of cycles whose intersection with E_x^0 is exactly E_p, Eq. (2) would be a correct partition of cycles by their matching-edge usage, and the 'all edges are identical' symmetry would make C_p depend only on p; but the text never makes this exactness explicit. Additionally, C_1=Θ(n^{k-2}) is asserted without a counting derivation. Because the reduction from cycle counting to sum-of-bits estimation in Theorem 5.3 relies entirely on the exactness of Eq. (2), the Ω(n^{k-1.5}) lower bound is not established by the manuscript as written. The issue is repairable by redefining C_p, but the current text is internally inconsistent.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":18988,"tokens_out":12062,"duration_ms":116046,"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":[{"comment":"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.","section":"Section 5, Eq. (2) and Lemma 5.1"}],"minor_comments":[{"comment":"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.","section":"Section 4 and Appendix 8"},{"comment":"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":"Lemma 3.3 proof"},{"comment":"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":"Section 4 informal proof"},{"comment":"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":"Section 4 and Appendix, minor typos"},{"comment":"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":"Section 6 experiments"},{"comment":"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.","section":"Section 2.3 and checklist"}],"recommendation":"major_revision","confidential_remarks":"The main gap is localized to Section 5 and appears repairable, so I recommend major revision rather than rejection. The authors should be asked to fix the definition of C_p, provide a rigorous proof of Lemma 5.1 including the C_1 = Theta(n^{k-2}) count, and clean up the n/N notation in Section 4. No concerns about novelty or attribution; the paper extends known triangle-counting bounds in a natural way and the upper-bound algorithm is a clean contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nMinor 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.\n\nBottom 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.","headline":"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).","tokens_in":19560,"tokens_out":7188,"would_cite":true,"duration_ms":81243,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["graphlet counting","local differential privacy","edge local differential privacy","randomized response","subgraph counting","expected l2 error","privacy lower bounds","k-clique counting"],"falsifier":"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.","tokens_in":18460,"feed_emoji":"🔐","tokens_out":10682,"duration_ms":97499,"temperature":0.7,"pith_summary":"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.","feed_headline":"Count any k-node graphlet privately at optimal error","feed_subtitle":"A randomized-response estimator matches the proven lower bound, so no non-interactive private scheme can do better.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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$."],"supporting_citations":[{"why":"It supplies the debiased randomized-response estimator and the triangle-counting gadget that the clique lower-bound proof reduces from.","marker":"[Eden et al., 2023]"},{"why":"It supplies the sum-of-bits lower bound under local differential privacy that the cycle-counting lower-bound proof reduces to.","marker":"[Joseph et al., 2019]"},{"why":"It introduces randomized response, the mechanism whose edge queries the algorithm is built on.","marker":"[Warner, 1965]"},{"why":"It defines edge local differential privacy and the composition rule the algorithm's privacy guarantee follows.","marker":"[Qin et al., 2017]"},{"why":"It provides the earlier non-interactive triangle-counting algorithm whose error rate this paper generalizes to arbitrary $k$-node graphlets.","marker":"[Imola et al., 2021]"}],"fun_headline_variants":["Private graphlet counting: optimal for any k","Any-size graphlet counting with local DP, optimally","Local DP: count k-graphlets with worst-case optimal error","Optimal private counting for graphlets of any size k","Privacy-proof counting of any k-graphlet"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Private graphlet counting: optimal for any k","Any-size graphlet counting with local DP, optimally","Local DP: count k-graphlets with worst-case optimal error","Optimal private counting for graphlets of any size k","Privacy-proof counting of any k-graphlet"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00019,"raw_usage":{"total_tokens":1334,"prompt_tokens":937,"completion_tokens":397,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":553,"completion_tokens_details":{"reasoning_tokens":319}},"tokens_in":553,"tokens_out":397,"duration_ms":4179,"temperature":1.0,"reasoning_tokens":319,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:26:05.194787+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}