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

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.