- 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 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 -DP mechanism to it which is sent to a shuffler which shuffles the messages of the nodes (this kind of shuffling is known to improve privacy) and then forwards them to a central server which estimates the count of 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 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
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 even beyond 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.
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 A be the adjacency matrix, and let W=A2 be the common-neighbor matrix. The underlying identities are simply
Thus, even closed-walk counts can be computed entirely from W, while odd closed-walk counts retain an additional factor of A. We call this remaining factor the seam.
This distinction matters in the shuffle model because W is a sum of vertex-local contributions: W=∑vavav⊤, where av is the adjacency row held by vertex v. Such sums can be estimated using shuffle aggregation. The remaining factor of A 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 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) 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) 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+N1, A+M, and W+N2.
Expanding tr((W+N1)(A+M)(W+N2)) 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). 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.