acceptodds
Under review as a conference paper at ICLR 2027

Node-Private Learning from Multi-Attribution Data via Stable Contribution Bounding

Abstract

We study node-level differential privacy for multi-attribution learning, where each example involves several users. A standard pipeline caps each user's contributions and then runs an example-level private learner on the selected examples. Removing one user can change which other examples are selected, and this recourse, not the cap, determines the privacy of the pipeline. For deterministic structure-only selectors, bounded recourse is necessary and sufficient to transfer example-level privacy to node-level privacy, and exact contribution bounding can have recourse linear in the dataset size even at degree two. We give a stable selector, based on quadratic regularization and feasible rounding, that retains a constant fraction of the feasible optimum with a privacy factor growing at most as the square root of the dataset size, and structural classes on which the factor is independent of the size. Population-risk guarantees and experiments on public attribution structures show when the reduced privacy noise outweighs the loss of training examples.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Differential Privacy, Node-level DP, Stability, Contribution Bounding

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_nfZAOpenReview ↗
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 kk 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 δ=10−5\delta=10^{-5} 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 n\sqrt{n}, how practical is the method for very large datasets without additional structural assumptions?
  • Why did the authors choose δ=10−5\delta=10^{-5} for all datasets? Since some datasets are very large, shouldn't δ\delta be chosen based on the number of users? How would the method perform with stricter privacy budgets (e.g. ϵ=1\epsilon = 1)?
  • 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
AuthorsOpenReview ↗

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/Mt_N/M, where MM is the retained size. When N=Θ(n)N=\Theta(n) and a constant fraction of the nn examples is retained, the general bound tN=O~(rNk)t_N=\tilde O(r\sqrt{Nk}) gives a privacy contribution O~(drkεn).\tilde O\left(\frac{\sqrt d r\sqrt k}{\varepsilon\sqrt n}\right).

Under Theorem 24's conditions, this and the statistical term of order 1/n1/\sqrt 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.

Attribution sizeAccuracy at 10,000 usersAccuracy at approximately 3 million users
r=2r=250.76±4.62%50.76\pm4.62\%82.25±1.05%82.25\pm1.05\%
r=3r=348.63±4.82%48.63\pm4.82\%72.60±3.88%72.60\pm3.88\%

These are means and one standard error over five trials, with k=5k=5, λ=1\lambda=1, and (ε,δ)=(4,10−5)(\varepsilon,\delta)=(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=2r=2 and 2–4 points behind for r=3r=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 10510^5 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\bar\rho=1 proved in Proposition 7(i). It applies when each example contains at most one user whose degree exceeds the contribution cap kk. 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)(\varepsilon,\delta)=(4,10^{-8}).

Attribution structureGain over direct learning
Ask Ubuntu+2.96±0.52+2.96\pm0.52percentage points
Math Stack Exchange+4.20±0.48+4.20\pm0.48percentage points
Stack Overflow+0.55±0.28+0.55\pm0.28percentage points
DBLP−0.02±0.01-0.02\pm0.01percentage points

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\delta=10^{-8} and ε∈0.5,1,2,4\varepsilon\in\\{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\delta=10^{-8} are as follows.

Attribution structureε=0.5\varepsilon=0.5ε=1\varepsilon=1ε=2\varepsilon=2ε=4\varepsilon=4
Ask Ubuntu+2.62±0.18+2.62\pm0.18+4.16±0.53+4.16\pm0.53+3.38±0.49+3.38\pm0.49+1.89±0.31+1.89\pm0.31
Math Stack Exchange+9.21±1.02+9.21\pm1.02+14.78±1.38+14.78\pm1.38+12.67±1.49+12.67\pm1.49+7.33±0.77+7.33\pm0.77
Stack Overflow+14.77±1.45+14.77\pm1.45+5.72±0.83+5.72\pm0.83+2.28±0.44+2.28\pm0.44+0.40±0.21+0.40\pm0.21
DBLP−1.97±0.36-1.97\pm0.36−0.47±0.12-0.47\pm0.12−0.09±0.02-0.09\pm0.02−0.07±0.05-0.07\pm0.05

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\delta\in\\{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\epsilon_{\rm opt}=10^{-6}. Following Remark 6, we increase the fractional response bound by 22Nϵopt/λ2\sqrt{2N\epsilon_{\rm opt}/\lambda} before rounding. The comparisons in W2 evaluate the selector in closed form.

For learning, we use a public gradient tolerance τ=10−9\tau=10^{-9}. Strong convexity bounds the distance to the exact minimizer by τ/κ\tau/\kappa, so we add 2τ/κ2\tau/\kappa 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.

Thank you for the detailed response and additional experiments. I am satisfied with the rebuttal and have increased my rating from 3 to 4.

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

The paper considers the problem of querying a hypergraph consisting of examples (hyperedges annotated with the values being queried) shared by users (nodes) under user-level differential privacy. Previous work considered the 'fixed-graph privacy' model, where two hypergraphs are considered adjacent if their nodes and hyperedges are the same, but the values of edges incident on one node can change between the two. This work considers 'node-level privacy', where two hypergraphs are adjacent if they differ by the addition/removal of one node (including its incident hyperedges). The authors consider a two-phase framework, where a selector first selects a subset of the hypergraph in which the degree of each node is bounded by kk. A learner then takes this subset and runs a differentially private query on the values in the remaining hyperedges. The learner only needs to satisfy group privacy guarantees corresponding to the degree bound, so most of the work in terms of optimizing the privacy-utility tradeoff is in designing the selector.

The authors first show arbitrarily selectors can have high sensitivity, even in low-degree graphs. In particular, they demonstrate that for the cycle graph with odd cycle length, under the constraint of choosing at most one edge per node, any (potentially fractional) selector which chooses a maximum matching has sensitivity Ω(∣E∣)\Omega(|E|) to the removal/addition of an edge. This is despite the degree of the graph being 2, and the arity of the hyperedges being 2. This means even though we are adding/removing 1 node and 2 edges, the overall privacy guarantee of the selector + learner can be proportional to ∣E∣|E|, even if the learner has an example-level 1-DP guarantee.

The authors then propose a selector that has low sensitivity and good utility, allowing the overall selector + learner pipeline to maintain privacy proportional to the degree bound kk. The idea is that the problem of selecting as many hyperedges as possible can be written as a linear program with objection ∑eye\sum_e y_e, where yey_e is an indicator for an edge being included or not in the selector's output, and a constraint ∑e:v∈eye≤k\sum_{e: v \in e} y_e \leq k. The authors add a regularizer to get λ∥y∥2+∑eye\lambda \|y\|^2 + \sum_e y_e. This makes the objective strongly convex, and the optimal solution for the graph with a node removed is within object value at most kk of the optimal solution with the node added, so strong convexity implies an upper bound on the distance between the optimal solutions for the two graphs.

The authors also propose a stable way to round the solution to this convex program. In particular, they first sample each edge with probability 0 or 1, then randomly sort all edges and each node only keeps the first kk sampled edges it has, and then any edge that was rejected by any of its nodes is discarded. They show that they can couple the randomness in this process across two adjacent graphs, such that with high probability this rounding procedure is also stable.

Strong convexity implies ℓ2\ell_2-sensitivity bounds independent of the dataset size, but the implied ℓ1\ell_1 still grows with the square root of the dataset size. This is an improvement over the cycle graph which demonstrates high-utility selectors can have sensitivity linear in the dataset size, but still not ideal. The authors additionally prove with additional structural assumptions on the graph, this dataset size dependence can be removed.

The paper concludes with a discussion of how to convert stability to user-level privacy including excess loss bounds for completeness, and experiments comparing their methods to "direct" methods which use the whole dataset on logistic regression and mean estimation benchmarks, showing their methods meaningfully improve over this baseline.

Critical strengths
  • The paper solves a problem under a much stricter privacy model (node-level rather than fixed-graph privacy). Making the privacy model stricter is important, as the more lax fixed-graph privacy is convenient for designing algorithms, but may be subject to attacks which have not yet been developed and which node-level privacy would prevent. The stricter privacy model is also much more technically challenging. Fixed-graph allows for a simple greedy algorithm as the selector, and its privacy analysis is trivial/enforced by definition of the algorithm. Node-level privacy requires a much more involved analysis, and requires a two-stage algorithm (solving a regularized LP and then rounding) where each of the stages needs to be analyzed carefully. Overall the jump from fixed-graph to node-level privacy is both very meaningful in terms of qualitative practical improvements and in terms of the theoretical work needed.
  • The paper has comprehensive results which will make it easier for both theoreticians and practitioners to adapt the results in the paper. For example, the discussion in Section 4.3 gives a way to improve upon the N\sqrt{N} dependence in the main results, Section 5 lays out how to apply the selector-learner framework to acheive group privacy, and the experiments in Section 6 show how different factors such as dataset size and degree bounds can affect the results empirically.
Critical weaknesses

None.

Questions for authors

None.

2 comments
AuthorsOpenReview ↗

Response to Reviewer NaUJ

We thank the reviewer for the careful reading and positive assessment. We appreciate the recognition of the distinction between fixed-graph and node-level privacy and of the stability analysis needed to control changes in the selected data. In response to the other reviews, we have clarified the experimental calibration and added comparisons using a proved uniform response bound, stricter privacy budgets, and explicit optimization-error accounting. The original algorithm and theoretical results are unchanged.

Thanks for following up. I am happy to maintain my score.

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

This paper studies node-private learning from data in which each example is attributed to multiple users. It identifies selection recourse as the key factor in transferring example-level privacy to node privacy and proposes regularized contribution bounding with feasible randomized rounding. The paper provides stability and retention guarantees, structural refinements, and learning experiments using synthetic contents on synthetic and public attribution structures.

Critical strengths
  1. The paper clearly establishes why a contribution cap alone is insufficient for node-private learning. Its instability constructions and exact characterization of pure-privacy transfer for deterministic structure-only selectors identify selection recourse as the relevant quantity for guarantees uniform over downstream learners, providing a principled foundation for designing contribution-bounding pipelines.
  2. The proposed method jointly addresses stability, feasibility, and data retention through regularized optimization and randomized rounding. The structural refinements further identify settings in which the privacy factor is independent of dataset size and maximum degree, giving the framework meaningful scope beyond its general worst-case bound.
Critical weaknesses
  1. The main empirical utility gains rely on the structural calibration parameters, but these parameters have not been consistently verified on the relevant input classes. The authors explicitly acknowledged this limitation, and in the main real structure experiments, the utility produced by conservative calibration was lower than that from direct learning. Therefore, the experiments have not been able to prove that the reported gains can be achieved under fully reasonable node-level privacy guarantees, which limits the practical evidence support for the proposed process.
  2. When the example content depends on the attribution structure, the learning evidence is still limited. The main utility guarantee assumes that the content is independent and identically distributed from the structure, while the experiments on the public structure used synthetic content that conforms to this assumption. Although Appendix D.4 provides a distribution shift extension, it does not control this difference, and still requires the selected example conditions to be independent. Therefore, it is unclear whether the utility gains can continue to persist when the contribution degree affects the sample representativeness and the shared user examples are statistically related.
Questions for authors
  1. Can the authors use consistent certified structural response boundaries on representative attribution structures and adopt privacy calibration that considers the limited optimization error simultaneously to demonstrate end-to-end utility advantages?
  2. Will the utility gains persist when features or labels depend on user activities or shared attribution? Using real example content or controlled, structure-dependent synthetic data for experiments will help evaluate the resulting selection bias.
  3. Is the dependence of the general pursuit boundary on the dataset size necessary when only a constant proportion is required to be retained? The lower bound is for the exact selector, so clarifying the best stability that an approximate selector can achieve will help evaluate the strength of the proposed trade-off.
1 comment
AuthorsOpenReview ↗

Response to Reviewer 9gnv

W1/Q1: Learning gains with a proved privacy bound

We have added experiments using the uniform response bound ρˉ=1\bar\rho=1 already proved in Proposition 7(i). It applies when each example contains at most one user whose degree exceeds the contribution cap kk. This condition is preserved under user deletion, so Corollary 6 provides the node-DP calibration throughout this class.

For each public benchmark, we form a substructure satisfying this condition and compare our original regularized method with direct learning on that same substructure. At (ε,δ)=(4,10−8)(\varepsilon,\delta)=(4,10^{-8}), the results are:

Attribution structureRegularized methodDirect learningGain over direct learning
Ask Ubuntu88.74%85.78%+2.96±0.52+2.96\pm0.52
Math Stack Exchange89.42%85.22%+4.20±0.48+4.20\pm0.48
Stack Overflow90.30%89.76%+0.55±0.28+0.55\pm0.28
DBLP90.22%90.24%−0.02±0.01-0.02\pm0.01

Accuracies are means over ten paired trials; gains are percentage-point differences with one standard error. The method improves on direct learning on Ask Ubuntu and Math Stack Exchange, with a smaller gain on Stack Overflow and essentially equal accuracy on DBLP.

We evaluate the selector in closed form and include the learner's finite optimization error in the privacy calibration for both methods. Appendix E.6 gives the experimental and calibration details.

The updated PDF includes these results, with additions shown in blue. The updated supplementary code includes the files needed to reproduce all tables and figures in the paper.

W2/Q2: Contents that depend on attribution

We have added two experiments on the Math Stack Exchange substructure, using the same methods and privacy calibration as in W1/Q1.

First, we let the label rule vary with user activity, so contribution bounding can change the composition of the training set. Evaluation uses the benchmark's original activity mixture. Across four levels of this shift, the regularized method retains a 2.6–3.0 percentage-point advantage over direct learning.

Second, we generate each example's features from its users' latent attributes plus independent noise. Examples sharing users are then dependent. Across four noise levels, the regularized method retains a 3.1–4.5-point advantage.

The gains therefore persist in both settings. Each comparison uses ten paired trials; Appendix E.7 gives the content models and results.

Q3: Dataset-size dependence and approximate selection

Approximate selection permits constant recourse on the odd-cycle instances used in Theorem 1 and Corollary 2. We have added the following example.

On the deletion-closed class of simple graphs of maximum degree two, with k=1k=1, assign each edge an independent uniform random number in [0,1][0,1], called its priority. Retain an edge when its priority is lowest at both endpoints. This retains at least 23OPTLP\tfrac23\mathrm{OPT}_{\mathrm{LP}} in expectation.

Under shared priorities, every vertex deletion changes at most three selected edges. Thus approximate selection has constant recourse on the same odd cycles C2m+1C_{2m+1} where every exact selector has a deletion with expected recourse at least mm. Appendix B.1.1 states this claim and gives its proof.

For our regularized method, fix 0<λ≤10<\lambda\le1, attribution bound rr, and cap kk. Lemma 15 gives expected retention of at least OPTLP/(8r)\mathrm{OPT}_{\mathrm{LP}}/(8r), improving to

OPTLP/8\mathrm{OPT}_{\mathrm{LP}}/8 when k≥6ln⁡(2r)k\ge6\ln(2r). Corollary 10 gives coupled recourse tN=O(r(Nk+log⁡(1/η)))t_N=O\left(r\left(\sqrt{Nk}+\log(1/\eta)\right)\right)

with probability at least 1−η1-\eta. Here NN is a public example-count bound. Its square-root dependence enters through ∥z∥1≤N∥z∥2\|z\|_1\le\sqrt N\|z\|_2 when converting fractional stability into a recourse bound. Increasing λ\lambda with NN improves the bound but sacrifices a uniform constant retention fraction: even with slack constraints, the weights fall to 1/λ1/\lambda once λ>1\lambda>1.

On the two classes in Proposition 7, the same method has rounded recourse O(r2k+rlog⁡(1/η))O(r^2k+r\log(1/\eta)), independent of dataset size and maximum degree, with the retention guarantees above. Whether the size dependence can be removed for the regularized optimizer, or for another selector retaining a constant fraction of the optimum, on arbitrary structures of bounded attribution size remains open.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Author Response and Summary of Updates

We thank the reviewers for their careful reading and constructive questions. Our paper studies how to make contribution bounding compatible with node-level privacy. Deleting one user can change which other examples are retained, and our analysis controls these changes to establish privacy. The algorithm and original theoretical results remain unchanged.

We have added comparisons on substructures of four public benchmarks that satisfy Proposition 7(i). These use a proved uniform response bound and account for finite optimization error. The results show gains over direct learning on Ask Ubuntu and Math Stack Exchange, with a smaller gain on Stack Overflow and essentially equal accuracy on DBLP. Additional experiments examine contents that depend on attribution and smaller privacy budgets.

We have also extended the synthetic experiments to six and ten million users using the general privacy bound. We observe higher accuracy at larger sample sizes and gains over direct learning on the more concentrated instances. Appendices E.6–E.10 give the experimental details. The updated PDF includes the new results, with additions shown in blue, and the supplementary code includes the files needed to reproduce all tables and figures in the paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.