acceptodds
Under review as a conference paper at ICLR 2027

Differentially Private Cycle Counting: Local Lower Bounds and Shuffle Estimators

Abstract

The shuffle model of differential privacy can improve aggregate statistics, but its benefits for graph pattern counting remain unclear. We identify an algebraic parity split for cycles. Let be the adjacency matrix of an -vertex graph and its matrix of length-two walk counts. Even closed-walk counts satisfy , whereas odd counts satisfy and retain one factor of . This distinction motivates our estimators, but does not by itself characterize shuffle amplification. For every fixed odd and , with a small constant (and if ), we give an unbiased shuffle estimator of with dense-graph root mean squared error (RMSE) . Correcting walks that repeat vertices gives a simple-cycle estimator with RMSE, and the same rate when ; for , the rate is throughout this range. We also prove an lower bound for every fixed in the non-interactive per-edge local model, where each edge has its own pure -DP channel. For , on the dense random graphs that witness this bound and for , suppose the analyzer also receives with Gaussian noise. Noise of order per entry is then a threshold: above it the bound still holds, and well below it spectral deflation, which removes the top eigencomponent, beats the bound. With a provably private multi-message release of , deflation reaches RMSE on these graphs. This shuffle protocol improves on the per-edge lower bound by on that family, which is not a worst-case separation from the full local model.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
differential privacy, shuffle model, graph statistics, subgraph counting, cycle counting, local differential privacy, lower bounds, privacy amplification by shuffling

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.80 over 5 reviews, above 27% of the others.
Reviewer_w78MOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper considers shuffle differential privacy for counting the number of kk cycles in a graph. We want to be private with respect to the edge neighboring relation where two neighboring graphs can differ in the existence of up to one edge. The users are the nodes, who I guess only sees their neighbors (but it is not very clear in the papers). Based on this input, they use an ε\varepsilon-DP mechanism to it which is sent to a shuffler which shuffles the messages of the nn nodes (this kind of shuffling is known to improve privacy) and then forwards them to a central server which estimates the count of kk cycles. The question raised in the paper is whether this kind of shuffling can improve the error in the estimates of the cycle counts.

Critical strengths

Questions about cycle counting are interesting both in the private and non-private setting

Critical weaknesses

The paper is heavily AI generated and it seems like no serious effort has been made to make it readable to humans. I don't mind AI generated proofs but in this day and age I think such papers are of little value without humans putting in a good amount of work to understand the content and improve the presentation.

E.g., already 'our contributions' contain a statement "We show that even traces factor through W=A2W=A^2 and odd ones do not" which I don't really know what means. Definition 3 is incomprehensible. For some interesting long deviations, one can go to page 15 and see if one can parse lemma 7. There is really no point in giving these examples, when the majority of the paper is like this, but including them for good measure.

Aside from this, there is no motivation in the paper for studying this model which is rather specific.

Questions for authors

None

3 comments

We thank the reviewer for taking the time to read our paper. We have extended and reorganized the exposition in the revised PDF, which is now available on OpenReview.

We would like to clarify the three examples mentioned in the review.

1. What does “even traces factor through the wedge matrix” mean?

Let AA be the adjacency matrix, and let W=A2W=A^2 be the common-neighbor matrix. The underlying identities are simply

  • For even k=2mk=2m, tr(Ak)=tr(Wm)\mathrm{tr}(A^k)=\mathrm{tr}(W^m).
  • For odd k=2m+1k=2m+1, tr(Ak)=tr(WmA)\mathrm{tr}(A^k)=\mathrm{tr}(W^mA).

Thus, even closed-walk counts can be computed entirely from WW, while odd closed-walk counts retain an additional factor of AA. We call this remaining factor the seam.

This distinction matters in the shuffle model because WW is a sum of vertex-local contributions: W=∑vavav⊤W=\sum_v a_va_v^\top, where ava_v is the adjacency row held by vertex vv. Such sums can be estimated using shuffle aggregation. The remaining factor of AA in the odd case creates a different estimation problem.

We now explain these identities directly in the introduction, including the distinction between closed walks and simple cycles.

2. Definition 3 and the restricted protocol class.

Definition 3 introduces a restricted class C\mathcal C to formulate our conjectures about the limitations of certain one-round shuffle protocols. It is not intended as a definition of the general shuffle model.

The class imposes three conditions: (i) changing one edge affects only O(1)O(1) atomic scalar-message inputs; (ii) users send messages in one non-interactive round using independent randomness; and (iii) the analyzer applies a fixed-degree polynomial to aggregate message sums.

For example, independently privatizing individual edge indicators satisfies the bounded-influence condition. By contrast, the pair-indexed wedge release used in our certified algorithm lies outside this class, since changing one edge can affect Θ(n)\Theta(n) wedge-message inputs.

We have moved the detailed class definition and associated conjectures to the appendix, with these examples and a discussion of their scope. The main algorithmic and privacy guarantees do not depend on the conjectures.

3. Lemma 7 and the error analysis.

Lemma 7 controls the nonlinear noise terms in our five-cycle estimator. The estimator uses three independent private releases, written as W+N1W+N_1, A+MA+M, and W+N2W+N_2.

Expanding tr((W+N1)(A+M)(W+N2))\mathrm{tr}((W+N_1)(A+M)(W+N_2)) produces seven error terms, corresponding to the seven nonempty subsets of the three noise blocks.

The key observation is that these terms are pairwise uncorrelated: for any two distinct terms, one can condition on a mean-zero noise block appearing in one term but not the other. Their variances can therefore be analyzed separately.

The leading contribution comes from the adjacency-noise term tr(WMW)\mathrm{tr}(WMW). Lemma 7 bounds the remaining quadratic and cubic terms, establishing the stated RMSE guarantee.

We have added a reading guide and reorganized the proof into explicit steps, making the independence argument and variance calculations easier to follow.

4. Motivation and scope.

Our setting is motivated by distributed graph analysis in which each vertex holds its own adjacency row and cannot share its raw neighborhood with a trusted curator. Cycle counts capture higher-order network structure and can serve as structural statistics in graph analysis and learning.

The shuffle model offers a different trust assumption from both central and local DP. Our main question is whether its anonymous aggregation can improve the accuracy of these graph statistics, particularly for odd cycles.

The revision explains the motivation earlier and distinguishes the independent per-edge local model, the general node-local model, and the shuffle protocols used in our results. It also states explicitly which comparisons establish a separation and which questions remain open.

5. Presentation and technical soundness.

We acknowledge the reviewer's concerns about the writing. The AI assistance used in preparing the manuscript was disclosed, and we take responsibility for the mathematical statements and their proofs. We have worked to make the technical arguments more accessible in the revision.

We would also appreciate clarification regarding the significant soundness concerns reflected in the review. The examples raised concern exposition, and the review does not identify a particular incorrect theorem, proof step, or counterexample. If the reviewer has a specific mathematical concern, we would welcome the opportunity to address it directly.

We hope the revised presentation and the explanations above help make the contributions and their technical scope clearer.

I stand by my initial evaluation. The authors have made several updates to the paper, and large parts of the paper seems to have been completely rewritten, but it still seems the paper is mainly AI generated without proper human moderation, and to be accepted more thorough work would be needed and a new review cycle. To take an example of one of the new updates, the fourth line of the abstract now reads "For fixed graphs with a dominant adjacency eigenvalue and controlled spectral tail, its conditional RMSE is O(n7/2/ε)O(n^{7/2}/\varepsilon) even beyond O(n)O(\sqrt{n}) secondary eigenvalues". I don't know what sentences like that means.

In terms of soundness, I put a low score, because I find the theorems, proofs, and ideas, nearly impossible to understand. There are tens of pages on unmotivated calculations with no intuition offered (e.g., have a look at page 29). The main point is that regardless of whether a paper like this is correct or wrong, it doesn't really add anything useful before the ideas are clearly explained.

Thank you for clarifying your concerns. We understand that the presentation of technical results can make their verification difficult.

Regarding the abstract sentence you quoted, an abstract necessarily summarizes technical assumptions in a compressed form, while their precise definitions belong in the main text. Here, the dominant eigenvalue and spectral tail conditions characterize the graphs on which our one-round estimator achieves its stated accuracy. Our two-round estimator, by contrast, achieves a worst-case guarantee without these spectral assumptions.

We have further revised the abstract to make this distinction clearer. We have also reorganized the main text to introduce the counting identities, algorithmic intuition, and principal proof arguments before the more detailed calculations.

The paper combines spectral graph methods, subgraph counting, and shuffle differential privacy, so some specialized terminology is unavoidable. Nevertheless, we agree that the central ideas should be accessible without following every technical calculation, and we have worked to improve the exposition accordingly.

We appreciate your feedback and the time you have spent reviewing our work.

Reviewer_6basOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Private subgraph counting is an important problem with applications to social science. This paper analyzes cycle counting under differential privacy. It analyzes the differences between even and odd cycle cases, utilizing common-neightbor matrix W=A^2 where A is the adjacency matrix. It reports improvement on Erdos-Renyi family graphs.

Critical strengths
  • It deals with an important problem in the community.
  • It is good that the authors explicitly mention restrictions of the per-edge lower bound.
  • Degenerate case analysis in 3.4 and independent release of factors in section 4 are very interesting.
Critical weaknesses
  1. Corollary 1

If I am correctly understand it, I think a simple non-interactive local algorithm where each vertex releases its degree with independent Laplace noise (\epsilon/2) and we just sum up all these to estimate N_5 should achieve O(n^3.5/\epsilon). The authors should compare their algorithm with this simple solution. It seems that there is no improvement over this simple baseline.

  1. Theorem 1

If I am correctly understand it, the RMSE bound by Fang & Yi 2025 would be O(n^2.5) instead of O(n^2.75), if sampling rate q=1.0. O(n^2.75) seems to be the case where q=1/\sqrt{d} where d is the maximum degree. I think the case dealt in this paper is q=1.

  1. Proposition 1

It seems that most claim in this propositions are mentioned in section 4.2 of: Azogagh et al, "GRAND : Graph Reconstruction from Potential Partial Adjacency and Neighborhood Data", KDD 2025. The authors at least cite this paper and should discuss the difference and what part is the authors' contribution.

  1. p16-17 The authors discusses that no choice of t, k does better. But the discussion before this sentence just mentions the upper bound of RMSE, so we cannot mention so, if I understand it correcltly.
Questions for authors
  1. Are there any reason to consider q=1/\sqrt{d} (see above) in theorem 1?
  2. What is the difference between Proposition 1 and the KDD 2025 paper mentioned above?
1 comment

We thank the reviewer for four observations. We have addressed these points in the revised PDF version, which is now available on OpenReview.

1. Corollary 1: the degree-only local baseline.

The reviewer is correct that degree information provides a simple and effective estimator on Erdős–Rényi graphs. We have included this baseline explicitly in the revision.

Each vertex releases its degree with independent Lap(2/ϵ)\mathrm{Lap}(2/\epsilon) noise. Since changing an edge affects two degrees, the joint release satisfies pure ϵ\epsilon-edge-DP. Let p^\widehat p be the clipped estimate of the edge density obtained by summing these reports. We then estimate the number of 5-cycles by

N^5deg=(n)510p^5.\widehat N_5^{\mathrm{deg}}=\frac{(n)_5}{10}\widehat p^5.

On G(n,p)G(n,p) with constant pp and n−1/4≤ϵ≤1n^{-1/4}\le\epsilon\le1, this estimator achieves RMSE O(n7/2/ϵ)O(n^{7/2}/\epsilon). We give the calculation in the revised appendix.

This observation clarifies the scope of Corollary 1. Our O~(n7/2/ϵ)\widetilde O(n^{7/2}/\epsilon) shuffle bound improves upon the Ω(n4/ϵ)\Omega(n^4/\epsilon) lower bound for independent per-edge local channels, but does not establish a separation from arbitrary node-local protocols. The revision now states this distinction explicitly.

There is also an important difference between a distribution-specific density estimator and estimating cycles on a fixed graph. Degree information alone does not generally determine the number of 5-cycles. For example, two disjoint cliques of size n/2n/2 and a complete balanced bipartite graph with a perfect matching removed are both (n/2−1)(n/2-1)-regular, but the latter has no odd cycles, whereas the former has Θ(n5)\Theta(n^5) 5-cycles. Our spectral result (Theorem 8) gives a conditional error guarantee for individual graphs satisfying its stated spectral conditions, rather than relying on an Erdős–Rényi generative model.

2. Theorem 1: the sampling rate in Fang–Yi (2025).

We agree with the reviewer. The previously quoted O~(n2.75)\widetilde O(n^{2.75}) RMSE corresponds to the communication-saving choice q=1/dq=1/\sqrt d, not to the full-communication setting q=1q=1.

At q=1q=1, Fang–Yi's published variance bound for C4C_4 is

+\frac{n^2d^2}{\epsilon^4}\right).$$ For $d=\Theta(n)$ and $\epsilon\ge n^{-1/2}$, this gives RMSE $\widetilde O(n^{5/2}/\epsilon)$. Theorem 1 and the related-work discussion now use this sharper benchmark and explain the communication tradeoff. We attribute this bound entirely to Fang–Yi; the purpose of Theorem 1 is to establish the even-cycle reference point for our study of longer odd cycles. **3. Proposition 1 and GRAND (KDD 2025).** Thank you for pointing out this connection. Azogagh et al. already describe the relevant co-square graph phenomenon in Section 4.2 of GRAND. We now cite their work directly in Proposition 1 and the related-work discussion. In particular, the base example $C_6$ versus $2K_3$ is not claimed as a new construction. We use it to explain why $W=A^2$ alone cannot determine odd closed-walk counts, and extend the example through dense blow-ups. This motivates the remaining adjacency factor in our odd-cycle estimators. The contribution of the paper lies in the privacy-aware factorization, its error analysis, and the spectral treatment of this remaining factor, rather than in the co-square example itself. **4. The claim concerning all choices of $t$ and $k$.** The reviewer is right that minimizing an upper-bound expression does not establish a lower bound on the actual error. We have therefore clarified Lemma 8 and Corollary 2. Under the stated privacy accounting, choosing $t=\Theta(n)$ and $k=\Theta(\epsilon^2n)$ gives a **certified upper bound** of $\widetilde O(n^{9/2}/\epsilon)$ for the analyzed pivot construction. The parameter calculation shows that our displayed bound cannot certify a better rate; it does not rule out a sharper analysis, different parameterization, or another pivot-based estimator. The comparison is now stated strictly as one between the proved error guarantees of two explicit constructions, without claiming optimality over all pivot-based methods. We appreciate these observations. They have helped us sharpen the comparisons with prior work and distinguish the guarantees that are proved from the broader questions that remain open. The revised PDF includes the detailed degree-only analysis, the corrected Fang–Yi comparison, the GRAND attribution, and the revised pivot-bound discussion.
Reviewer_YFspOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper talks about complexities that arise with the use of Differential Privacy(DP) in graphs. It mainly discusses the shuffle method of differential privacy in graphs, where each user/graph node applies a small amount of noise to their local message and a shuffler scrambles the messages before sending them to an analyst. This makes it an intermediate mode between local DP, where each node applies a large amount of noise locally before sending a message, and central DP, where a central trusted entity applies noise to each message instead of the individual nodes doing so. Cycle counting in graphs with shuffle DP is an active area of research. Cycle counting with even length cycles is fairly straightforward and is largely a solved problem since there are clear pairs, and the counting can be done based solely on the wedge matrix. Odd length cycles are a little more complex since one edge is left without a pair, and the authors refer to the edge as the seam. Counting odd length cycles requires information from the two nodes on both ends of the seam but this cannot be computed by either node individually because of the shuffle DP. The paper derives upper and lower bounds for the cycle counting with odd length cycles, and also points out a special case with 5-cycles where the lower bound can be beat by a factor of square root of n if certain constraints about the number of messages a node can possibly send are relaxed.

Critical strengths
  1. The paper is thorough in its mathematical findings, with each finding in the main text carefully supported by comprehensive proofs in the appendix.
  2. The authors include experiments to validate their theorems, which I think is not typical of theoretical papers, and I appreciate that.
Critical weaknesses
  1. The lower bound derivation is for a particular class of DP models(per-edge non-interactive local models), and this seems fairly narrow. The authors point this out explicitly, but it still seems like a point of concern for the impact of the findings on the broader class of DP models.
  2. While the authors include experiments, they don't show any plots or tables to corroborate their findings, which makes the experiment section somewhat questionable.

Some nitpicks:

  1. The paper is fairly hard to read currently. I would prefer the Related Work section to be after the introduction rather than just before the conclusion so the prose is easier to follow, but this is just my opinion and other people might disagree.
  2. I question the scope of the paper for ICLR. ICLR is mostly concerned with different subfields of Artificial Intelligence, and this reads more like a theoretical paper involving graphs and differential privacy, with no model learning involved.
Questions for authors
  1. The experiments use asymptotic noise with constants set to 1 to validate scaling exponents. Could the experiments be repeated with actual messages, even at a smaller scale? This would help with further validation of the theorems.
  2. It is unclear from the wording whether Corollary 1 deals with just local DP rather than shuffle-based DP. Could the authors clarify?
3 comments

Thank you for the thoughtful review and for recognizing the mathematical contributions and the value of the experiments. We have extended the results and clarified the comparisons in the revised manuscript.

1. Scope of the local lower bound.

The per-edge lower bound (Theorem 5) applies to independent edge-wise channels and yields an Ω(nk−1/ε)\Omega(n^{k-1}/\varepsilon) RMSE benchmark. To go beyond this restricted architecture, we have added Theorem 5A for arbitrary noninteractive node-local reports: a vertex may jointly randomize its entire adjacency row, subject to incident-edge privacy.

For every fixed odd kk, we establish an Ωk(nk−1)\Omega_k(n^{k-1}) worst-case RMSE lower bound; for k≥5k\geq 5, hard instances can be dense. The proof uses an odd-partite cycle gadget followed by a reconstruction argument.

Unlike Theorem 5, this extension does not claim a uniform 1/ε1/\varepsilon factor or a same-family separation against all row-local protocols. The revised introduction and comparison table distinguish these statements.

2. What Corollary 1 compares.

Corollary 1 concerns the shuffle-based rank-one estimator, not a local-only estimator. On the same dense random-graph priors, it gives an improvement by a factor of roughly n\sqrt{n} over the lower bound for independent per-edge local channels.

We now state explicitly that this is not a separation from arbitrary node-local protocols, which can exploit correlations and degree statistics within a row.

3. Experiments and actual messages.

Section 6 now includes a main-text comparison figure, with detailed tables and plots in Appendix D. We separate normalized asymptotic noise from privacy-calibrated aggregate Fang--Yi noise.

At n=257n=257, normalized noise favors the rank-one estimator by about 55--88 times, while the calibrated experiments do not show that advantage at the tested sizes. The revised manuscript reports both outcomes.

We also implemented a full one-round message-level simulation of the matched transcript, including per-user wedge contributions, negative-binomial noise, zero-sum count-masking messages, explicit shuffling and aggregation, private degree reports, and adjacency randomized response.

The following table compares the theoretical and observed standard deviations of the off-diagonal wedge noise, using ε=1\varepsilon=1 and δ=n−3\delta=n^{-3}.

nnTrialsTheoretical SDObserved SD
138238.36235.46
174286.97290.95

The observed standard deviations closely match the theoretical values. Every shuffled wedge aggregate also matched the independently generated data-plus-noise sum.

At these small sizes, the cycle estimators are noise-dominated. We therefore use this experiment to validate message generation and aggregation, rather than to claim improved finite-sample accuracy or empirically establish privacy.

Appendix D.2 contains the earlier message-aggregation pilot. The additional full-message implementation and results can be included in the next revision PDF.

4. Presentation and relevance.

We have shortened the longer discussions, moved a concise related-work comparison into the introduction, defined W=A2W=A^2 in the abstract, and brought the key experiment figure into the main text.

The introduction also explains that private cycle counts are structural statistics useful in graph analysis and graph learning. The contribution here is a privacy-preserving estimation method, rather than a graph-model training algorithm.

We hope these extensions clarify both what the shuffle improvement establishes and where its present limits lie.

I thank the authors for revising the paper and addressing my comments. However, I stick to my original decision since I question the scope of this paper for ICLR because there is no model learning aspect in the methodology itself, even though it might be useful for graph learning.

Thank you for considering our revision. We appreciate your recognition of the paper's technical soundness and the improvements made in response to your comments.

We understand your concern about the absence of a model-training component. We would like to note that the ICLR 2027 Call for Papers explicitly includes learning theory, learning on graphs, and privacy among its subject areas.

Our work develops privacy-preserving methods for estimating graph structural statistics, which are relevant to graph representation and learning. The methodological contribution concerns how these statistics can be computed under decentralized privacy constraints, rather than the design of a particular learning model.

The latest revision also extends our two-round shuffle protocol to every fixed odd cycle length k≥5k\ge 5, strengthening the generality of the theoretical results.

We hope this clarifies the connection to ICLR's broader research scope. Thank you again for your thoughtful feedback.

Reviewer_2gV1OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies kk-cycle counting under edge-DP in the local and shuffle models. In DP, shuffle model is weaker (in terms of privacy requirement) than local-DP but stronger than central-DP. It allows users to send randomized information through a trusted shuffler, which hides the identity of each sender before publishing. Therefore, a motivating question in the paper is whether shuffling can improve the accuracy of cycle counting over local DP. Prior work answers this positively only for triangles and 4-cycles (Imola et al., 2022; Fang & Yi, 2025). The paper observes that even closed walk counts can be written in terms of the common-neighbor matrix W=A2W=A^2, where A is the adjacency matrix. But odd ones cannot. The paper gives a shuffle estimator for every odd kk with dense-graph error O(nk−1/ε)O(n^{k-1}/\varepsilon). Note that here the error is RMSE. It also proves a matching Ω(nk−1/ε)\Omega(n^{k-1}/\varepsilon) lower bound, but only in a restricted local model where each edge is randomized independently. Finally, on a family of dense random graphs, it shows that a shuffle protocol combined with a spectral estimator beats this lower bound by a factor of roughly n\sqrt{n} for 5-cycles. The simulation results are consistent with the theoretical results.

Coming to the technique, the key observation is W=∑uauau⊤W=\sum_u a_ua_u^\top, where aua_u is user uu's adjacency vector, is a sum of per-user terms, so it can be released accurately through a shuffler (via the mechanism of Fang & Yi). For odd k=2m+1k=2m+1, however, tr⁡(Ak)=tr⁡(WmA)\operatorname{tr}(A^k)=\operatorname{tr}(W^mA) still contains one factor of AA, which the authors estimate with randomized response. Taking the trace of the product of independent noisy factors gives an unbiased estimate of tr⁡(Ak)\operatorname{tr}(A^k), but its error is dominated by the noise in AA, which keeps it at Θ(nk−1/ε)\Theta(n^{k-1}/\varepsilon). For the lower bound, the authors construct two random-graph distributions with edge densities differing by Θ(1/(εn))\Theta(1/(\varepsilon n)), which are nearly indistinguishable under per-edge randomization, whose expected cycle counts differ by Θ(nk−1/ε)\Theta(n^{k-1}/\varepsilon). For 5-cycles, the authors reduce the dependence on the noisy AA. On these random graphs, the dominant spectral part of tr⁡(A5)\operatorname{tr}(A^5) is estimated from the noisy WW, and only a smaller remainder is estimated using the noisy AA. This works when the noise in WW is well below roughly n/εn/\varepsilon per entry; for ε≥n−1/4\varepsilon\ge n^{-1/4}, the shuffle release achieves O~(n/ε)\widetilde O(\sqrt n/\varepsilon), giving the roughly n\sqrt n improvement.

Critical strengths
  • The problem is well motivated and natural. I think it is important to study cycle counting under edge-DP in the shuffle model.
  • I checked the analysis of the per-edge lower bound and the basic odd-cycle estimator, it appears technically sound.
  • I find the 5-cycle result interesting because it shows that accurate common-neighbor information can overcome the per-edge local lower bound on the random graphs used in its proof. And it is the next case beyond the triangles and 4-cycles studied in prior work, although the improvement is established only on a particular random-graph family. Also I like the conjecture.
Critical weaknesses

Major concerns

  • I am very confused by the many different settings. Why are they all necessary? I do not find a clear explanation. The lower bound concerns per-edge local protocols, the shuffle estimators use pair-indexed multi-message protocols, and the conjectures concern yet another class C\mathcal C. The 5-cycle improvement is further restricted to a particular random-graph family. Although these distinctions are stated, I had difficulty understanding which results can be compared and what they collectively establish about the benefit of shuffling.
  • The motivating question is not really answered. The paper asks whether shuffling improves cycle counting over local DP, but none of the results settles this. The lower bound does not cover standard row-local protocols. The 5-cycle improvement holds only on one family and only against per-edge protocols. The parity thesis that would explain the picture remains a conjecture.
  • Technical novelty. The basic estimator combines existing mechanisms, namely the wedge release of Fang & Yi (2025) and randomized response, with an algebraic factorization. The lower bound uses standard tools.

Other concerns

  • The reason for restricting the spectral result to 5-cycles is unclear. Does the same approach extend to longer odd cycles, or is there a specific obstacle? A short discussion would help clarify how general the technique is.

On paper writing

  • The motivation and intuition are thin in the introduction section.
  • I understand there may be reasons that the experiment section is organized with 3 paragraphs of words without a table or figure. But I strongly suggest the contents in A.10 should be moved to the experiment section, at least the figures. It is a pain to scroll back and forth to check the figures and see how they match with what is written in the main body. The super long paragraph in page 29 is another pain.
  • In the abstract, define mm.
  • Reduce the length of some paragraphs, and theorem statements.
Questions for authors
  • What motivates the definition of class C\mathcal C?
  • Why does the paper focus on dense graphs? What happens to the guarantees for sparse graphs?
5 comments
AuthorsOpenReview ↗

1.Clarifying the model comparisons and the benefit of shuffling

Clarifying the model comparisons and the benefit of shuffling

We thank the reviewer for the thoughtful review and for checking the basic estimator and lower-bound analysis. We agree that the different models need a clearer organizing principle. We have extended the analysis and made the comparison hierarchy explicit.

The central distinction is between a matched benchmark comparison and a general model separation. Our results establish the former and provide additional worst-case guarantees toward the latter:

  1. Independent per-edge local channels (Theorem 5). Each undirected edge passes through an independent pure-ε\varepsilon private channel. For fixed kk, every estimator from that product transcript has RMSE Ωk(nk−1/ε)\Omega_k(n^{k-1}/\varepsilon) on the stated dense product priors and privacy range. This benchmark captures separately privatized adjacency indicators, not arbitrary processing of a vertex's full row.

  2. General noninteractive node-local protocols (Theorem 5A). We extend the lower-bound analysis to reports computed jointly from each vertex's entire adjacency row. For every fixed odd k≥3k\ge3 and 0<ε≤10<\varepsilon\le1, an arbitrary-length noninteractive report, pure-ε\varepsilon private under one incident-edge change, still incurs worst-case RMSE Ωk(nk−1)\Omega_k(n^{k-1}). For odd k≥5k\ge5, the bound holds even on graphs with minimum degree Ω(n)\Omega(n). This theorem assumes neither independent edge channels nor bounded communication, although it does not obtain the additional 1/ε1/\varepsilon factor.

  3. Shuffle upper bounds for five-cycles. Theorem 8 analyzes a one-round wedge-based spectral estimator: it has conditional RMSE O~(n7/2/ε)\widetilde O(n^{7/2}/\varepsilon) on fixed graphs with a dominant eigenvalue and controlled spectral tail. The protocol is edge-private on every graph, though this sharper accuracy bound is instance-dependent. We also extend the same wedge framework by one adaptive shuffle round. Theorem 9 achieves RMSE O~(n7/2/ε)\widetilde O(n^{7/2}/\varepsilon) on every graph, with global (ε,δ)(\varepsilon,\delta)-edge-DP and O~(n2)\widetilde O(n^2) expected bits per vertex, for n−1/2≤ε≤1n^{-1/2}\le\varepsilon\le1 and δ=n−Θ(1)\delta=n^{-\Theta(1)}.

These statements give two concrete comparisons. Corollary 1 uses precisely the same two dense product priors for the one-round shuffle upper bound and the per-edge product-channel lower bound. For C5C_5, their RMSEs are O~(n7/2/ε)\widetilde O(n^{7/2}/\varepsilon) and Ω(n4/ε)\Omega(n^4/\varepsilon), respectively, a Ω~(n)\widetilde\Omega(\sqrt n) improvement against independent per-edge privatization. This comparison is distribution-matched, not a claim about all node-local methods.

Theorems 5A and 9 further give worst-case benchmarks for broader classes: Ω(n4)\Omega(n^4) for arbitrary noninteractive, pure-DP node-local reports, and O~(n7/2/ε)\widetilde O(n^{7/2}/\varepsilon) for a two-round, approximate-DP shuffle protocol. At constant ε\varepsilon, the rates differ polynomially. Because interactivity and privacy notions also differ, this does not by itself prove a fully matched separation between the entire local and shuffle models. We now distinguish that open question explicitly from the results proved here.

The restricted class C\mathcal C has a separate role: it formalizes an exploratory conjecture about one-round, bounded-influence scalar-message protocols. It is not the model assumed by Theorems 5, 5A, 8, or 9, and no proved guarantee depends on the conjecture. Our certified pair-indexed wedge release lies outside C\mathcal C because an edge change can affect Θ(n)\Theta(n) tagged scalar inputs. We explain this in the appendix and summarize the actual comparison classes together in the main text.

We hope this organization makes the answer to the motivating question more precise: shuffling demonstrably improves over the independent edge-channel benchmark on matched inputs, while the extended all-graph shuffle upper bound and general node-local lower bound provide further progress on the broader question.

We have just uploaded a revised version with complete proofs and a model-comparison table.

AuthorsOpenReview ↗

2. Technical contribution, longer odd cycles, sparse graphs, and presentation

We thank the reviewer for these suggestions. We build on Fang and Yi's wedge release and standard randomized response; our contribution lies in the privacy and error analysis for simple odd-cycle counts and the five-cycle extensions.

For general odd k=2m+1k=2m+1, the identity tr⁡(Ak)=tr⁡(WmA)\operatorname{tr}(A^k)=\operatorname{tr}(W^mA), where W=A2W=A^2, exposes a remaining bare-edge factor. Theorems 2–4 give a complete privacy ledger for independent wedge and edge releases, prove unbiasedness of the trace estimator, account for corrections from closed walks to simple cycles, and identify why the edge channel contributes the leading Θk(nk−1/ε)\Theta_k(n^{k-1}/\varepsilon) RMSE on dense graphs. The identity alone does not yield those privacy and error bounds.

The improved five-cycle analysis uses a further idea. Theorem 8 retains the leading spectral component and controls the discarded part through a deterministic spectral-tail quantity, so a single private wedge release suffices for O~(n7/2/ε)\widetilde O(n^{7/2}/\varepsilon) RMSE when that tail is small; no separately randomized adjacency release is needed. The perturbation analysis handles the noisy leading eigenpair and diagonal degree estimates.

Theorem 9 extends the wedge method to all graphs with two adaptive shuffle rounds. It uses an exact edge-linearization of the simple C5C_5 count: after the first private wedge release, the second round anonymously sums weighted edge indicators. Its privacy proof conditions on every first-round transcript, handles all bit-level messages, and composes the full transcripts of both rounds. These steps are proved in Lemmas 31–33. We also extend the lower-bound analysis to general noninteractive node-local reports through an odd-partite cycle gadget and a Fourier reconstruction argument (Theorem 5A).

Why is the sharper spectral bound focused on five-cycles?

The factorization and O~(nk−1/ε)\widetilde O(n^{k-1}/\varepsilon) upper bound extend to all fixed odd lengths (Theorem 4). The stronger rate is more delicate. For C5C_5, there is a particularly simple exact correction identity involving WW, degrees, and one edge indicator.

For k≥7k\ge7, converting closed walks to simple cycles introduces additional repeated-vertex image graphs and higher-order noisy products. For example, the Eulerian image C3∨Ck−3C_3\vee C_{k-3} contributes an all-noise term of order n(k−1)/2/εkn^{(k-1)/2}/\varepsilon^k, which is not lower order at ε=Θ(n−1/2)\varepsilon=\Theta(n^{-1/2}). An equally sharp spectral/simple-cycle analysis for longer odd lengths therefore needs additional control. This is a limitation of the current proof, not an impossibility claim.

Why dense graphs, and what about sparse graphs?

Dense graphs support the product-prior lower bound and make the basic estimator's leading noise terms comparable. Density alone does not guarantee many odd cycles—dense bipartite graphs are a simple example—so we avoid claiming a relative-error guarantee from density alone.

The privacy of our certified mechanisms holds on all graphs. Moreover, Theorem 9's O~(n7/2/ε)\widetilde O(n^{7/2}/\varepsilon) absolute RMSE bound also holds for sparse graphs, but need not be optimal there; for maximum degree dd, even the zero estimator has absolute error at most O(nd4)O(nd^4) for C5C_5. Degree-sensitive shuffle bounds remain an interesting direction.

What motivates the restricted class C\mathcal C?

It isolates a possible one-round "seam" barrier under bounded influence: an edge change is allowed to alter only O(1)O(1) tagged scalar-message inputs, and the analyzer uses sums followed by a fixed-degree polynomial.

This is an exploratory setting for the conjectures, not a model needed for the proved results. The certified pair-indexed wedge release is outside this class because one edge can change Θ(n)\Theta(n) scalar inputs; the two-round extension is outside it by interactivity. We now put the precise definition and conjectures in the appendix to keep the main narrative focused on proved bounds.

Presentation and experiments.

We have revised the presentation: W=A2W=A^2 is defined in the abstract; the introduction explains the model comparisons and the role of the wedge matrix; the main experiment section now includes the comparison figure, with shorter text and fuller diagnostics in the appendix.

We distinguish normalized-noise experiments (favoring rank-one estimation) from privacy-calibrated aggregate-noise tests (showing no advantage at the tested sizes).

The revised version with detailed discussion is now available on OpenReview, please have a check.

  • Thanks for the detailed clarifications. I see the paper is revised and many of my concerns are addressed. I think theorem 5A and 9 do strengthen the theoretical contributions and make the distinction clearer. I do not have time to check the correctness though.

  • I saw this recent paper: https://arxiv.org/abs/2611.05038. If I understand correctly, it achieves O(n3.5/ε5)O(n^{3.5}/\varepsilon^5) additive error for 5-cycle counting in the two-round local model. Does this affect the prospects for establishing a polynomial separation between the local and shuffle models?

  • More of curiosity, what fundamentally becomes the barrier for larger odd kk? Is this barrier formulated in other works on graph problems or combinatorics? I could suspect it is related to the "complex structures", but people do study this, e.g. for shortest path and cuts.

  • Based on your knowledge, has this separation been shown on other DP graph problems?

  • The revised paper now in my opinion is on the borderline. I still hope in the future, the message conveyed in the paper is more organized and clearer.

Reviewer_19Y4OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies if we can estimate the garph cycles more accurately in the DP shuffle model, compared to the local DP. The main idea is to formulate the count of close walks in a graph by the trace of a polynomial of the wedge matrix W=A2W = A^2. For odd-length cycles, the paper exploits the factor of AA in the polynomial, using spectral deflation to improve the error bound on the RMSE by a factor of n\sqrt{n} on a specific random-graph family of G(n,p)G(n, p). The main method isolates the contribution of the largest eigenvalue to the count, which might dominate the count in dense graphs regimes, handling it separately, while the rest can be privitized using standard noise injection. That separated contribution then can be estimated from a previously released components, without involving new noise.

Critical strengths

Prior work in graph algorithms in the shuffle model focuses on shorter length cycles (3, 4-cycles). This paper proposes a method for longer, odd-length cycles.

The estimation is unbiased, with transformation from closed walks to simple cycles.

The decomposition of the count into spectral components and handling different components differently is quite interesting.

Critical weaknesses

The theoretical bound tries to implies a shuffle model advantage over the local DP, but only applies to a restricted comparision:

  • The improved bound only applies to a specific graph family, not the worst case scenario (which the local DP bound applies to).
  • The locality unit of the assmued local DP model by this work is per-edge. The common graph local DP model uses node-locality and edge-privacy.
Questions for authors

Why did the author choose the unusual local DP model for graphs? And how does the result applies to a more commonly used local DP model for graph algorithms: node-locality, edge-privacy.

2 comments
AuthorsOpenReview ↗

On the graph-family restriction

Response to the concern about the graph-family restriction

We thank the reviewer for recognizing the soundness and technical interest of our spectral approach. We would like to clarify the scope of the improved error bound and explain how our analysis extends beyond the random-graph setting.

1. The one-round result applies beyond the specific random-graph family.

Our one-round spectral estimator (Theorem 8) achieves an RMSE of O~(n7/2/ε)\widetilde O(n^{7/2}/\varepsilon) for simple five-cycle counting under a deterministic spectral condition: the graph has a dominant adjacency eigenvalue and a controlled spectral tail.

Dense Erdős–Rényi graphs provide a natural example, but the analysis does not require the input to be sampled from that distribution. It also covers fixed graphs whose nonleading eigenvalues exceed the usual O(n)O(\sqrt n) scale, provided the spectral-tail condition holds.

2. The improved rate can also be obtained uniformly over all graphs.

We have extended the wedge-based approach to a two-round interactive multi-message shuffle protocol (Theorem 9). For every nn-vertex graph GG, the estimator satisfies

\le \widetilde O(n^{7/2}/\varepsilon).$$ The protocol provides global $(\varepsilon,\delta)$-edge differential privacy for $n^{-1/2}\le\varepsilon\le1$ and $\delta=n^{-\Theta(1)}$, using $\widetilde O(n^2)$ expected bits per vertex. **This bound holds for every graph, without any spectral, density, or distributional assumption.** The extension relies on an exact identity for simple five-cycles. Let $A$ denote the adjacency matrix, $W=A^2$, and $d_i=W_{ii}$. Then $$10N_5(G) = 2\sum_{i \lt j} A_{ij}(W^2)_{ij}$$ $$\qquad - 5\sum_{i \lt j} A_{ij}(d_i+d_j-2)W_{ij}.$$ This identity expresses the five-cycle count as a weighted sum of edge indicators, with coefficients determined by the wedge matrix and vertex degrees. The protocol uses the same private wedge-release primitive as our spectral estimator. In Round 1, the vertices privately release the wedge matrix and degrees. The analyzer broadcasts the resulting noisy quantities. In Round 2, the vertices use these publicly available coefficients to compute weighted edge contributions, which are aggregated through anonymous, Poisson-padded shuffle summation. The privacy analysis accounts for the dependence between rounds. Conditioned on any first-round transcript, all coefficients are fixed. By assigning every unordered pair to a unique endpoint, changing one edge affects only one virtual user's contribution at each bit level. The second-round shuffle mechanism is private for its entire transcript, and adaptive sequential composition establishes the overall $(\varepsilon,\delta)$-edge-DP guarantee. For accuracy, we directly bound the polynomial error introduced by the noisy wedge matrix. The leading contribution has order $O(n^3\sigma)$, where $\sigma=\widetilde O(\sqrt n/\varepsilon)$ is the wedge-noise scale. The remaining error terms, including the second-round aggregation noise, are within the claimed rate. Unlike the spectral analysis, this argument does not require eigenvalue concentration. The complete protocol, adaptive privacy proof, and uniform RMSE analysis are formalized in **Theorem 9 and Lemmas 31–33**. **We have uploaded a revised manuscript on OpenReview, containing the full statements, constructions, and proofs of these results.** In summary, our one-round estimator achieves the improved rate under a deterministic spectral condition, while its two-round extension obtains the same rate uniformly over all graphs. We hope this addresses the reviewer's concern about the applicability of the shuffle-model improvement.
AuthorsOpenReview ↗

On the local-DP model and comparison

We thank the reviewer for this question. The independent per-edge model was motivated by randomized-response-based graph estimators, where each edge is privatized separately and the analyzer receives the resulting product transcript. It provides a useful benchmark for understanding the statistical cost of independently perturbing edge indicators.

In this model, Theorem 5 proves an Ωk(nk−1/ε)\Omega_k(n^{k-1}/\varepsilon) lower bound for estimating simple kk-cycles, under its stated privacy-parameter regime and dense product priors. This lower bound applies to all estimators of the independent edge-channel transcript, not merely a particular unbiased plug-in formula.

The reviewer's distinction is important: the standard node-local, edge-private model is more general. Each vertex holds its entire adjacency row and may jointly randomize the incident-edge bits, with privacy protecting a change to one incident edge. For example, a vertex can release a noisy degree as one joint row statistic, rather than randomizing each incident edge independently. We have clarified this distinction in the model definitions and comparison of results.

Extension to the general node-local model.

We have extended our lower-bound analysis beyond independent edge channels. Theorem 5A states that, for every fixed odd k≥3k\ge3 and 0<ε≤10<\varepsilon\le1, any noninteractive node-local protocol with an arbitrary-length report per vertex, jointly computed from its entire adjacency row and satisfying pure ε\varepsilon-DP under one incident-edge change, has worst-case RMSE at least $ \Omega_k(n^{k-1}) $ for simple kk-cycle counting.

The result permits public randomness and arbitrary joint row processing, with independent private randomizers conditional on the public seed. For odd k≥5k\ge5, the same bound holds even on graphs with minimum degree at least n/(6k)n/(6k). No independent per-edge or communication restriction is imposed.

Main proof idea.

We construct a multipartite odd-cycle graph with two vertex sets U,VU,V containing a hidden binary edge matrix XX. Additional vertex sets form a path between UU and VV, and two gate vectors a,ba,b determine the connections to this path.

For odd kk, every simple kk-cycle traverses all parts, giving the exact identity

\qquad L=\Theta_k(n^{k-2}).$$ Thus, estimating cycle counts corresponds to answering bilinear queries about $X$. For a fixed hidden matrix, a constant number of alternative-completion reports per data-holding vertex can simulate the protocol for every choice of the public gates. Fourier reconstruction then converts an overly accurate cycle estimator into an accurate reconstruction of $X$. However, changing one entry of $X$ affects only four local randomizer invocations. By composition, their combined transcript is pure $4\varepsilon$-DP in each hidden bit, forcing constant reconstruction error per bit. Summing over $\Theta(n^2)$ bits yields the $\Omega_k(n^{k-1})$ lower bound. The dense-graph case follows by restricting to hidden matrices with sufficiently large row and column degrees. **Implications for the shuffle–local comparison.** The two local lower bounds serve complementary purposes. Theorem 5 gives the sharper $1/\varepsilon$ dependence for independent edge channels. On the **same dense product priors**, Corollary 1 compares their $\Omega(n^4/\varepsilon)$ RMSE with the $\widetilde O(n^{7/2}/\varepsilon)$ RMSE of our one-round shuffle estimator for five-cycles, giving a $\widetilde\Omega(\sqrt n)$ improvement. Theorem 5A applies to arbitrary noninteractive node-local reports and establishes an $\Omega(n^4)$ worst-case lower bound for five-cycles. Meanwhile, our two-round shuffle extension (Theorem 9) achieves $\widetilde O(n^{7/2}/\varepsilon)$ RMSE uniformly over all graphs. For constant $\varepsilon$, these rates differ polynomially. The latter comparison involves different assumptions on interactivity and pure versus approximate privacy, which we state explicitly. **We have uploaded a revised manuscript on OpenReview, including the full proof of Theorem 5A and a clearer comparison of the local and shuffle models.** We hope this extension addresses the reviewer's question about the standard node-local, edge-private setting.

Comments on the paper

1 comment
Area_Chair_YEAGOpenReview ↗

acknowledging rebuttal

Dear reviewers,

If you believe the authors have addressed your questions, please respond to the rebuttal.

Best, AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.