- Rating
- 4(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies node-level differential privacy (DP) where each example is connected to several users in a hypergraph structure. Users are vertices and examples are hyperedges. The hypergraph structure is assumed to be public knowledge, while the actual data values are private. Existing methods select a subset of examples such that each user appears in at most selected examples, and then apply an example-level DP mechanism using group privacy to obtain privacy guarantees.
However, limiting how many examples each user appears in does not control how many other examples the selector changes when that user is removed, which is called the selector's recourse. The paper shows that exact contribution bounding method can be unstable, such that the privacy cost can grow linearly with the dataset size. Moreover, the paper introduces a stable selection method using quadratic regularization and feasible randomized rounding, such that the privacy factor grows at most as the square root of the dataset size.
Critical strengths
- The paper studies an interesting and important problem in node-level differential privacy.
- The paper shows that contribution bounding alone is not sufficient to control the privacy cost, since removing one user can change the selection of many other examples.
- The theoretical results are interesting, especially the characterization of stability in Theorem 9.
- The proposed method provides both stability and data retention guarantees.
Critical weaknesses
- The general stability bound scales as (O(\sqrt{n})), which can still result in a large privacy cost for large datasets.
- The strongest experimental results rely on empirical structural bounds that are not formally certified. Therefore, the privacy guarantees do not necessarily hold for these experiments.
- The experiments use for datasets containing millions of examples. This may be large depending on the number of users being protected.
- The experimental privacy calibration does not fully account for numerical optimization errors. The privacy guarantees are derived assuming that the optimization problem is solved exactly, but in practice numerical solvers return approximate solutions.
Questions for authors
- Since the general stability bound still depends on , how practical is the method for very large datasets without additional structural assumptions?
- Why did the authors choose for all datasets? Since some datasets are very large, shouldn't be chosen based on the number of users? How would the method perform with stricter privacy budgets (e.g. )?
- The paper discusses how approximate optimization affects the stability bounds. However, it is unclear whether these approximation errors are accounted for in the experimental privacy calibration. Can the authors clarify this?
2 comments
Thank you for the detailed response and additional experiments. I am satisfied with the rebuttal and have increased my rating from 3 to 4.
Response to Reviewer nfZA
W1/Q1:Learning with the general size-dependent bound
The square-root dependence of recourse does not imply that learning error grows with dataset size. The privacy term depends on tN/M, where M is the retained size. When N=Θ(n) and a constant fraction of the n examples is retained, the general bound tN=O~(rNk) gives a privacy contribution O~(εndrk).
Under Theorem 24's conditions, this and the statistical term of order 1/n decrease with dataset size when other parameters are fixed. Section 5.4 makes this explicit.
We evaluated two sizes of synthetic structures using general calibration, including finite optimization error in selection and learning.
These are means and one standard error over five trials, with k=5, λ=1, and (ε,δ)=(4,10−5). The recourse bound divided by mean retained size falls about twentyfold. Appendix E.9 gives the details.
We also extended these experiments to six and ten million users, with ten paired trials on each of twelve graph variants. At the same privacy budget, the pipeline improves on direct learning by approximately 12–18 percentage points on the eight variants where the busiest user contributes 3.6–4.8% of the examples. On the less concentrated ten-million-user instances, it is within one point of direct learning for r=2 and 2–4 points behind for r=3.
This pattern is consistent with the comparison in Section 5.4. Concentrated contributions increase the privacy cost of direct learning, while the pipeline benefits from retaining more examples as the dataset grows. On Table 8's concentrated structure with 105 examples, general calibration gives 67.7% accuracy versus 51.0% for direct learning. Appendix E.10 reports the larger experiments.
W2:Uniform structural calibration
We have added experiments using the uniform response bound ρˉ=1 proved in Proposition 7(i). It applies when each example contains at most one user whose degree exceeds the contribution cap k. This condition is preserved under user deletion, so Corollary 6 provides the node-DP calibration throughout this class.
We compare our regularized method with direct learning on the same benchmark substructures satisfying this condition, at (ε,δ)=(4,10−8).
These are ten-trial paired means with one standard error. We evaluate the selector in closed form and account for finite optimization error in both learners (Appendix E.6).
W3/Q2:Privacy budgets
We have extended the evaluation to δ=10−8 and ε∈0.5,1,2,4. This is below the reciprocal of the number of users on every benchmark.
For the full networks, using the structural response bounds assumed in Table 1, the accuracy gains over direct learning at δ=10−8 are as follows.
Entries are percentage-point differences over ten paired trials, with one standard error. The gains on the three thread datasets persist across the tested budgets. Appendix E.8 reports all accuracies for both structural and general calibration at δ∈10−5,10−8.
W4/Q3:Numerical optimization error
The new learning experiments account for finite optimization error in both selection and learning. The algorithm remains unchanged.
For iterative selection, we use a public objective-gap tolerance ϵopt=10−6. Following Remark 6, we increase the fractional response bound by 22Nϵopt/λ before rounding. The comparisons in W2 evaluate the selector in closed form.
For learning, we use a public gradient tolerance τ=10−9. Strong convexity bounds the distance to the exact minimizer by τ/κ, so we add 2τ/κ to the sensitivity for both the pipeline and direct learning. These tolerances are fixed across neighboring inputs, and the solvers run until they are met. Appendix E.9 gives the derivations and stopping rules.
The updated PDF shows additions in blue. The updated supplementary code reproduces all tables and figures in the paper.