It's My Data Too: Private ML for Datasets with Multi-User Training Examples
Authors: Arun Ganesh
Ryan McKenna
Hugh Brendan McMahan
Adam Smith
Fan Wu
Venue: ICML 2025 poster (2025)
Keywords: differential privacy
multi-attribution
Primary area: social_aspects->privacy
TL;DR: We initiate a study of algorithms for model training with user-level differential privacy (DP), where each example is associated with multiple users

Abstract: We initiate a study of algorithms for model training with user-level differential privacy (DP), where each example may be attributed to multiple users, which we call the multi-attribution model. We first provide a carefully chosen definition of user-level DP under the multi-attribution model. Training in the multi-attribution model is facilitated by solving the contribution bounding problem, i.e. the problem of selecting a subset of the dataset for which each user is associated with a limited number of examples. We propose a greedy baseline algorithm for the contribution bounding problem. We then empirically study this algorithm for a synthetic logistic regression task and a transformer training task, including studying variants of this baseline algorithm that optimize the subset chosen using different techniques and criteria. We find that the baseline algorithm remains competitive with its variants in most settings, and build a better understanding of the practical importance of a bias-variance tradeoff inherent in solutions to the contribution bounding problem.

It's My Data Too: Private ML for Datasets with Multi-User Training Examples
Arun Ganesh Ryan McKenna' Brendan McMahan Adam Smith? Fan Wu
Abstract
ples and then using an example gradient in an algorithm like DP-SGD (this is exactly the DP- DP-FedSGD algorithm in- troduced in (McMahan et al., 2017)). However, without additional assumptions this approach only provides prov- able protections when an example's attributee is the sole person whose privacy is affected by leakage of that example; this is often untrue in practice. For example, a SMS or email message may contain privacy-sensitive information about both the sender and receivers, but might only be attributed to the sender in the single-attribution model.
We initiate study of algorithms for model training with user-level differential privacy (DP), where each example may be attributed to multiple users, which we call the mulli-attribution model. We first provide carefully chosen definition of user-level DP under the multi-attribution model. Training in the multi-attribution model is facili- tated by solving the contribution bounding prob- lem, iee the problem of selecting a subset the dataset for which each user is associated with a limited number of examples. We propose a greedy baseline algorithm for the contribution bounding problem. We then empirically study this algo- rithm for synthetic logistic regression task and a transformer training task, including studying vari- ants of this baseline algorithm that optimize the subset chosen using different techniques and cri- teria. We find that the baseline algorithm remains competitive with its variants in most settings, and build better understanding of the practical im- portance of a varianar tradeoff inherent in solutions to the contribution bounding problem.
Motivated by this gap, we propose and study the stronger and more flexible multi-attribution model: in addition to multiple examples being attributed to the same user, each ex- ample is potentially attributed to multiple users. This strictly generalizes the single-attribution model and extends to other practical settings not previously covered, but comes with number of algorithmic difficulties. First, even defining DP in the multi-attribution model requires extra care. Even with an appropriate definition, user-to eser-to-example reductions for algorithms like DP-FedSGD can't 't be directly applied to multi- autti-attribution data due to the overlap in users' data, and more nuanced data selection algorithms are required.
Figure 1 compares the attliiittribttoon setting we consider to other more standard settings, where training examples are formed from emails sent among different users (perhaps to train a language model or spam classifier).
1. Introduction
We study private model training with user-level differential privacy (DP) (Dwork et al., 2010), where each example is associated with multiple users (and in particular, might con- tain privacy-sensitive information for any or all associated users). This goes beyond previously-studied settings for user-level DP which (implicitly) adopt the antti-aattiittion model, where each example is attributed to a single user. This assumption greatly simplifies the problem, as it allows one to reduce to algorithms tailored to example-level DP, by c.g. computing the average gradient for each user's exam-
1.1. Our Contributions
Defining DP with multi-attribution: In Section 2, we pro- pose definition for DP with multiply attributed data, which we dub fixed-graph DP. In this model, we have hyper- graph where vertices represent users, and each hyperedge is associated with an example attributed to its vertices. Our definition protects against changing the content of examples associated with hyperedges adjacent to a single vertex. More precisely, our adjacency definition considers two datasets adjacent if they have the same hypergraph, but differ in (potentially) all of the data associated with a single vertex. We compare our approach to several alternatives, includ- ing generalization of node privacy to hypergraphs (Fang et al., 2022). Continuing with the example of email data, our approach allows a data curator to make statements to users like: "Even if every email you ever sent or received
'Equal contribution GGoogle Research, Seattle, USA "Boston University and Google DeepMind, Cambridge, USA UUniversity of Illinois, Champaign-Urbana. USA. Part of this work done while the author was an intern at Google Research.. Correspondence to: Arun Ganesh <arungancsh@ waapeesss@@gggg..oomom google.com>>.
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

It's My Data Too: Private ML for Datasets with Multi-User Training Examples
(a) Example-Level
(b) User-Level
(c) Multi-ttribution User-Level
(d) Multi-ttribution User-Level with Contribution Bounding km2
Examples
Users
Examples
Users
Examples
Users
Examples
From: To: Bob
From:
From: Bob
Alice
To: Bob
Alice
To: Bob
Alice
From: Alioa To: Bob, Carol
From: Alize
From: Alicn
From Alion To: Bob, Garol
Bob
To: Bob, Caral
Bob
To: Bob, Carol
Bob
From: Bob
From: Bob
From: Bob Dave
From: Bob
To:
Carol
Carol
Carol
From: Carol
From: To: Bob
To: Bob
To: Bob
To: Bob
Dave
Dave
Dave
From: Dave
From: Dave
From: Dave
From: Dave
To: Carol
To: Carol
To: Caral
To: Carol
Figure 1. Different approaches to DP modeling for a toy email dataset. Each training example is the text an email message. Viewing the dataset simply a flat list of messages, (a), naturally gives risc to example-level DP. This may be too weak of notion, the same "secret" might occur in multiple emails. In (b), each email attributed to the sender only, which leads to the standard (single-atthe (singlc-attribution) user-level DP notion. Again, this may not be sufficient if some secret from user Bob contained both in emails he sent and received (for example, suppose he receives a message from Alice "Hi Bob. I hope your recovery from surgery is going well."). "). To address this issue, in Section 2 we hypergraph model of the dataset, (c): We attribute each example the full of senders and receivers, leading to the hypergraph with nodes (users) V = (A, B, C, D) and edges (examples) V = (el (A, B}, e2 [A, B, C) === {B, D), eq = {C, B), es (D, C}). With this structure, in (d) we can apply our contribution bounding algorithms (Section 4) seleet subset of the training examples so that each user contributes at most k selected examples, for example selecting S {ei, ea, 6s } satisfics & = 2. After this pre-processing, user-level DP guarantees can be obtained using relatively standard ML infrastructure DP algorithms.
contained the same private information about you, that in- formation is protected. Someone with access to the trained model would learn (nearly) the same thing even if the text of every email you ever sent or received was replaced with completely different text before training."
in the contribution bounding problem:
Unique vs. duplicate examples: In Section 5.2 we study two variants of the greedy contribution bounding algorithm, which do or do not allow duplicate examples in S. Allowing duplicate examples gives a larger dataset with more uni- form contributions among users, reducing the DP noise but potentially introducing bias.
Contribution bounding algorithms: Because of the over- lap between data belonging to different users, we cannot use a user's average gradient as an example gradient in an algo- rithm like DP-SGD and immediately convert the resulting example-level DP guarantee into a user-level DP guarantec. Instead, we use contribution bounding: we find S, subset of the data which each user contributes most l examples to, and then train on S. Given the contribution bound, it is well-known how to derive privacy guarantees for DP-SGD run on S (see Section 3), so the overall procedure satisfies fixed-graph DP.
DP-SGD vs DP-MF: DP-MF is a variant of DP-SGD which adds correlated noise across iterations. For example-level DP, it is known that DP-MF with privacy amplification cap- tures DP-SGD with privacy amplification as a special case, and in turn Pareto dominates DP-SGD (Choquette-Choe et al., 2024). When moving to the multi- multi-attribution model, it is not obvious how to do amplification for general DP-MF, whereas known amplification guarantees for DP-SGD still apply. Hence, it is not immediate which of the two algo- rithms should be preferred. We empirically compare the two in Section 5.3.
While the single-atrribution model contribution bound- ing a trivial problem, in the multi-atribbtion model it is much more challenging. For example, maximizing [S] while satisfying the contribution bound requirement is straight- forward in the single-attribttion model, whereas in the multi-attribution model this is an NP-hard problem (see Appendix B). In Section 4, we propose greedy baseline al- gorithms for contribution bounding which are the basis of the studies in the rest of the paper.
Suboptimality of greedy algorithm: Due to the hardness of maximizing ,, a natural question is whether the greedy al- gorithm can be substantially improved on. For our research- scale datasets, in Section 5.4 we were able to solve an inte- ger linear program (ILP) for this problem and compare the greedy algorithm to the optimal solution found by the ILP.
Optimizing for bias: Our contribution bounding algorithm biases towards examples attributed to fewer users. In Sec- tion 5.5 we study how impactful this bias is on the test
Algorithmic choices: In Section we perform empirical evaluations to study a number of algorithmic design choices
2

---

It's My Data Too: Private ML for Datasets with Multi-User Training Examples
performance of our model, and variants of the greedy algo- rithm that attempt mitigate this bias.
sage is attributed-say, the sender and all the receivers of the message. For simplicity, we refer to the u E V users.
In real datasets, the data curator must choose how to perform this attribution. We discuss this choice below; for now, we take it as a given. The input to a DP algorithm M is thus an attributed data set D ((T1, EI)..... (Im, Em)).
1.2. Related work
How to best fit an algorithm like DP-SGD to user-level DP was well-studied in the single-attribution setting by Charles et al. (2024); Chua et al. (2024). They show user- to-example reductions generally outperform algorithms that sample/batch at the example-level. However these reduc- tions do not readily translate to the multi-attribution setting.
What notion of differential privacy makes sense for such data sets? We consider three notions here.
Edge-data (Example-level) DP. The simplest notion we consider is to change single training example (that is, the data associated with a single hyperedge in the graph), We say two datasets D, D' are edge-data adjacent if their associated hypergraphs are the same (that is, m = m'', and e, = c for all i E [m²), but differ by changing one example: 3y * x', for a single index j. The algorithm M is edge-data (e, Eiffffrrrnet private if, for all lige-data-adjaccee data sets D, D', we have MDD 22,5 M(D').
Outside learning contexts, the multi-attribution setting is analogous node-level DP for hypergraph queries (we discuss this connection in more detail in Section 2). Node- level DP for graphs has been studied extensively (Blocki et al.. 2013; Chen & Zhou, 2013; Kasiviswanathan et al., 2013; Borgs et al., 2015; Raskhodnikova & Smith, 20;b;;;; Day et al., 2016; Borgs et al., 2018; Sealfon & Ullman, 2021; Kalemaj et al., 2023; Jain et al., 2024) and more recently has also been studied in hypergraphs (Fang et al., 2022).
Edge-data differential privacy is exactly the standard notion of differential privacy, applied to the list of examples in the dataset. In the email context, it protects the text of a single email but provides little guarantee about information that is common to many of person's 's emails such as their religious beliefs politics. This formulation of DP ignores the hypergraph altogether; it corresponds to Example (a) from Figure 1.
2. Defining Privacy for Training Examples with Multiple Attribution
Given parameters E 2 and 8 e [o, 1]. we say two distri- butions P and Q on the same space (o-algebra) are (c indistinguishable if, for all events E,
P[E] s ex <QIE++ 8
and
QIE) S E PIE +
Fixed-graph (multi-attribution user-level) DP. In this paper, we consider much stronger guarantee, which we call fixed- differential privacy. Our primary motivation is to derive practical DP training algorithms for hypergraph- annotated datasets that nevertheless protect a person's 's con- tributions to the data set as a whole.
We denote this relation P r5,8 Q. Abusing notation slightly, given two random variables x, Y taking values in the same set, we write X Re.6 Y if their distributions satisfy the rela- tion. We say a mechanism (that is, randomized algorithm) M is (s, -iifferrennl private if for any pair of adjacent datasets D and D', we have M(D) R5,8 M(D). The definition of adjacency critically determines the "unit of pri- vacy", and hence the strength and meaning of the protection offered at a particular (s, d). In this section we consider dif- ferent definitions of DP that arise from different definitions of adjacency for datasets with multi-user training examples.
Definition 2.1. We say two datasets D, D' are fixed- hypergruph adjacent if their associated hypergraphs are the same and there indices such that & e,. That is, the examples involving one user (the v, where É e,) may differ arbitrarily, but all examples not involving that user are the same.
user u such that x; xy for all
For simplicity, we specialize to machine learning appli- cations with a training dataset consisting of examples (#I....,Im)) We associate with each training example I; additional metadata 6 (not directly used in training). Formally, each e; is subset of nodes (users) from some ground set V. We say the example z; is attributed to the nodes in eq. Letting É denote the list of e;'s ss we obtain a hypergraph (V, E), possibly with repeated hyperedges (that is, multiple 2; might be associated with the same subset C E.). For instance, in an email dataset, V could be a set of email addresses, account names, or other identifiers occurring in the data; each I; would be an email message, and e would be a set of identifiers in V to which the mes-
A randomized algorithm M is differentially private if, for all fixed hyperrrap adjacent data sets D, D', we have M(D) Re,6 M(D')
(E,
Auribution and the choice of the hypergraph. This definition of privacy separates the hypergraph (the attribution pattern) from the examples associated with hyperedges (the sub- stance of the training data). The definition allows flexibility in how attribution is performed, which in turn determines the hypergraph attached to the training examples and, crucially, the interpretation of the DP bound. For example, in the case of emails, we could choose to attribute each email only to the sender (single attribution), so that each set e, E F. has
3

---

It's My Data Too: Private ML for Datasets with Multi-User Training Examples
size 1. The resulting notion of DP corresponds directly to the typical application of user-level DP (e.g., McMahan et al. (2017)). Figure 1(b) illustrates this choice of hypergraph for an email setting.
On the choice to use fixed-graph DP: The algorithms in this paper satisfy fixed-graph DP. The main weakness of fixed-graph DP in comparison to node DP is that since ad- jacent datasets share the same hypergraph, implicitly the hypergraph is public information. Of course, in many con- texts the hypergraph itself is privacy-sensitive, and we do not advocate for publishing the hypergraph in practice. For example, the hypergraph might contain the fact that an in- dividual received an email from doctor who specializes in cancer treatment. This should be considered private in- formation, regardless of the contents of this email. In light of this weakness, we offer two main justifications for our choice:
However, for structured data like email, we can choose a hypergraph that leads to a much stronger' notion of privacy: by attributing it to the sender and all recipients as in Fig- ure I(c), we encode the possibility that the email contains sensitive information about any or all of these users?
Node privacy. Finally, one can consider third guarantee that is stronger still. Since we consider datasets where users correspond to nodes, a natural notion of differential privacy arises by defining adjacency based on the addition or removal of single node (see citations in Section 1.2).
First, protecting the contents of interactions is still a sub- stantial guarantee. For example, if the examples r; on hyperedges are the texts of emails, then the definition im- plies that the outputs would be (roughly) the same even if all the texts of Alice's emails were deleted from the data set. We additionally emphasize that fixed-graph DP in the nuuti--attibbuton setting is still a much stronger privacy pro- tection than privacy protections in the now- now-standard single- attribution setting, which may altogether ignore the fact that multiple users' privacy can be impacted by a single example.
Definition 2.2 (Fang et al. (2022)). We say two datasets D, D' are node-auljacent if there exists vertex u in V' such that D' = =[II,, ex) E D : u & ) (or vice-versa, with D and D' swapped). A randomized algorithm M is node (e, didfferrryll private if, for all node-adjacent data sets D' we have M(D Fe,8 M(D').
This definition implies that the hypergraphs differ by single node: that is, V' = V \ {u} and E' C E is the list of hyperedges (with repetitions) not including u.
Second, while fixed-graph DP technically allows the hyper- graph to be made public, we do not advocate for this and design algorithms that are unlikely to actually leak infor- mation about the hypergraph. In more detail, the specific algorithms we consider have a two-phase structure: they prune the hypergraph H without looking at the contents of the examples x; to obtain a subgraph H' that is "nice" (roughly, hypergraph with a known maximum degree). They then run an algorithm that processes the training ex- amples while ignoring the graph structure altogether. Since our uses of the graph structure and of the contents of exam- ples are largely decoupled, any violations of the stronger notion of node privacy (Definition 2.2), i.c. any information leaked about H, can only come from correlations between the graph structure and training examples. Indeed, the only counterexamples to node-privacy we know are extremely brittle.
Accurate node DP algorithms are hard to design. Even in the case of dyadic graphs (the "usual" graphs, in which each hyperedge connects exactly two nodes), most functions one would want to compute have extremely high worst-case sensitivity to the addition of single node. As result, considerable work has been devoted to designing node-DP algorithms that are accurate on "nice" graphs- for example, graphs with a given upper bound on nodes' degrees- -eet provide the worst-case privacy guarantee of Definition 2.2.
Much less is known about designing node-private algorithms for hypergraphs. Even for the simple task of counting the number of hyperedges in the graph, existing algorithms (Fang et al., 2022) are based on solving a linear program with a variable for each edge in the graph. Training a lan- guage model on examples associated with hyperedges re- quires solving gradient averaging-a a task mathematically similar to edge counting- -once for each training step and parameter in the model. Current algorithmic approaches would not scale even to modest model sizes.
At a technical level, using fxxe-graph DP allows us to sidestep the difficulties of designing truly node-private algo- rithms, which is that of bounding contributions in a stable or "insensitive" way. That is, unless substantial progress is made in the field of node DP for hypergraph data, we be- lieve fixed-graph DP allows the minimal slack in the privacy definition needed to design private ML algorithms without completely sacrificing utility.
'"Stronger" means the definition treats more datasets as adja- cent; the protection at a fixed (ε,8) is therefore higher.
"We assume throughout the paper a setting like training on emails where the metadata needed to define E is readily available. In other settings E may be challenging to materialize, e.g. when training on images containing faces that must be identified, In these settings it may be preferable to make additional assumptions and/or resort to the single-atribution model, but this is heyond the scope of this paper.
Our use of fixed- -rodggraph DP, rather than node DP, raises (at least) two open questions. First, is it possible get node- DP algorithms with similar accuracy and efficiency to the algorithms we consider? It would require significantly new
4

---

It's My Data Too: Private ML for Datasets with Multi-User Training Examples
3.1. Minibatch selection and privacy accounting
Algorithm 1 The DP DF algorithms
We now discuss existing privacy accounting results we can repurpose for the multi-attribution model. In each case we state an already-prov proven privacy guarantee that protects any set of examples in D that satisfy some property. To apply them to the multi-attribution setting, it then suffices to preprocess the graph dataset (V, E) into a "nice" graph dataset (V, E') such that sets of the form {er E EE= u E e.). i.e. the sets of edges all including one user u, all satisfy the desired property", which will be the foeus of Section 4.
Inputs: Dataset D, number of rounds T. batch size B, clip norm C, noise multiplier o, initial model lo, learning rate 7, correlation matrix C (for DP-SGD, C- D).
1: clip (v, C) v min(1,C//lvlly
2: for in [7] do
3: Sample a batch B, S DD of (expected) size B
4:
gi B ExEB, clip (V((0--;;x),C)
5:
z, (0,1)
6:
g: - gi + Co (C=
> z = (Z1, z2....)
B
7:
0; 4 1 - rg: (or another first-order update)
Poisson Sampling with DP-SGD: DP-SGD typically chooses a batch B, using Poisson sampling, where each example x; is independently included in B3 with probabil- ity p - B/|D| where B is a target batch size. Poisson sampling benefits from privacy amplification by sampling (Steinke, 2022), i.c. the randomness in the sampling ampli- fies the existing privacy guarantees. The example-level DP guarantee of this mechanism is well understood (Balle et al., 2018), and Charles et al. (2024) derive tight group-level (e, 8)D guarantees for this mechanism, i.e. guarantees assuming two adjacent datasets differ in at most & examples. To apply them to multi-attribution datasets it then suffices to bound the max degree as max [ee E E : u E e, = k. While DP-SGD's privacy guarantees have been studied in a number of other settings, this will be the main privacy ac- counting result we leverage for the rest of the paper. Since the privacy analysis is agnostic to how the noisy gradients are used, this analysis extends to e.g., DP-Adam and other variants.
8:
end for
algorithmic ideas. Second, do algorithms with the two- phase structure admit actionable attacks for realistic data sets? While we believe this is quite unlikely. it remains possible and, we hope future work either strengthens or refutes this belief by trying to attack our fixed-graph DP algorithms. More broadly, we hope this work will spur further investigations of both models.
3. Multi-attribution DP-SGD/DP-MF
DP-SGD (Song et al., 2013; Bassily et al., 2014) is canon- ical private learning algorithm which satisfies (e, 6DDD. In DP-SGD, given in Algorithm 1, in each round we sample batch B; of examples from the dataset D) and compute their gradients on the current model, clip the gradients to have bounded l fn-norm and add independent Gaussian noise to their average. We then use this as a noisy gradient in SGD, or another first-order method such as Adam.
Min Separation with DP-MF: There are several variants of DP-MF; in this work we restrict our focus to the banded matrix factorization (BandMF) mechanism (Choquette- Choo et al., 2024; McKenna, 2024). BandMF is charac- terized by b-banded strategy matrix C (Ci,j 0 for i- 2 b- 1) which determines the correlation structure; note that setting b = 1 gives independent noise / DP-SGD. BandMF's privacy analysis is easy when combined with a (k, b) mimiimmmm separation (min sep) batch selection proce- dure. For our purposes, given batches B,,.... Br, a set of examples satisfies (k, b)-min sep if examples in the set do not collectively appear more than once in any subsequence of consecutive b batches B,, B than k times total across BI...., Br. The ordering here is generally deterministic and hence this batch selection strat- egy does not enjoy amplification guarantees*. Assume C
DP-MF (matrix factorization) (Kairouz al., 2021; Denisov al., 2022; Choquette-Choed et al., 2022), also known DP- FTRL and also given in Algorithm 1, is a variant of DP-SGD in which the noise used in different rounds is correlated, so that some of the noise added in one round is cancelled out in subsequent rounds. The amount of cancellation is specified by a lower triangular noise correlating matrix C-1 E = which produces noise (C-1z); = Ejs; C7J3, in round i. The case C-1 = I retrieves the independent noise of DP-SGD. The noise correlating matrix C-1 is the inverse of the strategy matrix C; analysis of the strategy matrix is essential to choosing the correct noise multiplier o discussed next in Section 3. but C does not appear directly in the implementation of the algorithm.
................................ Be+b-1, and no more
"Note that other sets of examples may also satisfy the desired property, but this is immaterial to our desired fixed-graph DP guarantees.
'BandMF can additionally be combined with Poisson sampling to also benefit from privacy amplification, but doing so requires solving hard clustering problem and potentially discarding a large fraction of the data in the multi-attribution setting, so we do
These two mechanisms typically require selecting mini- batches in different ways and hence require different privacy analyses, which we discuss further below.
5

---

It's My Data Too: Private ML for Datasets with Multi-User Training Examples
has fixed column norm (wlog) I. Then if any pair of adjacent datasets differs only in a set of examples satisfying (ke b)- min sep, then DP-MF is Gaussian mechanism (whose privacy guarantees are computable via results in (Balle & Wang, 2018)) with noise multiplier a/vB /ii (Choquette-Choo et al., 2024). For fixed-graph DP, it then suffices if the sets of examples (er E E:: uuc E E each satisfy (k; b)-min sep.
terminate when either we take a pass over D without adding any examples (in which case the algorithm fails to find solution), or when S has length T B. We do not enforce a contribution bound requirement, but instead compute the contribution bound & (which is at most [&] post-hoe.
In Section 5 we will see that these baseline algorithms are already competitive, but there are many algorithmic choices one could make to further optimize the algorithm.
4. Contribution bounding algorithms
Given the results in Section 3, a natural algorithm for model training in the multi-attribution setting is to (i) compute a (multi-)subsett of examples S S D, such that S has at most k examples per user (or if using DP-MF, such that after forming batches from S, each user's examples satisfy (k:, b)- min sep), and then (ii) run DP-SGD/DP-MF on S. Under fixed-graph privacy, long
5. Empirical results
5.1. Experimental setup
We consider two tasks: training a small transformer on the arXiv dataset, and a synthetic logistic regression task.
generate S independently of the content of examples, we incur no privacy cost (in prac- tice, of course, the hypergraph structure should still be kept confidential). Once we've chosen S, privacy accounting and training have minimal differences from the same problem in the single-attribution setting, which well-understood. Hence, most of the challenge is choosing S. We refer to the problem of selecting S as the contribution bounding problem, and this problem will be the main focus of the remainder of the paper.
The arXiv dataset contains 1.9 million examples, each corresponding to a paper posted on arviv. For each paper i, we take the set of users e, to be authors of the paper, and the content of each example 2; to be the abstract of the paper. That is, we attribute each example the authors of the corresponding paper. We a train/test/validation split of
arxiv:
IM.
Logistic regression: results on arXiv are, we also experiment on synthetic logistic regression dataset.
To understand how generalizable our
A natural objective for the contribution bounding problem is to maximize (S], since the DP noise multiplier reduces with a larger dataset size and the DP noise usually has a large impact on utility. However, in Appendix B show that the problem of maximizing |S] under a contribution bound constraint is NP-hard. Given this hardness, we instead pro- pose a natural greedy algorithm with three variants. Due to space constraints, we give informal descriptions here and defer pseudocode to Appendix B.2. For each variant we first sort the dataset beforehand in increasing order of users per example.
Generation of the synthetic graph: Given the number of hyperedges |E), the expected users per example [[ee]] and expected examples per user da, we sample |E random hyperedges, either under a probabilistic regular graph model or a correlated sampling model that induces a more skewed distribution of examples per user. We defer details of the sampling procedures to Appendix C.I. We tried graph sizes E E {125k, 1M, AM.8M,, ), expected examples per user du (2, (2,4,8), fix B[[e[] = 2, and consider both regular and skewed graphs.
DP-SGD, no duplicates (Algorithm 2): We take a single pass over the dataset, adding each example (I,, e,) to S if no user in et has l examples in S already.
Generation of the synthetic logistic regression data: Each hyperedge has data x; = (zi, Ut) with features 2; E Rd (sampled from a multivariate normal) and label yı E {0, 1]. The groundtruth in the data generation process consists of two components: a universal base vector a which is shared across all samples, and a bias vector b scaled by the number of users |esl for each hyperedge. This recre- ates form of sampling bias present in the arXiv dataset; see Section 5.5 for more discussion. We sample yi ~ cermouli(sigmoiddf + lei|b, xx))). Further details about this procedure are deferred to Appendix C.I. We use a train/test/validatio split of 80%//0%//10%
DP-SGD, with duplicates (Algorithm 3): Alternatively, take multiple passes over the dataset, adding each ex- ample to S if no user in e has k examples in S already, and allowing duplicate examples to be added. We terminate after the first pass over D that doesn't add any examples.
DP-MF (Algorithm 4): We take multiple passes over the dataset. S is now a list, and we add each example (allowing duplicates) if after adding it, S split into batches of size B would not violate min sep of for any user's examples. We
Models, and training with DP: For arXiv, we fine-tune a pre-trained BERT-Timy model for the masked language modeling task (Devlin et al., 2019), using the default BERT
not consider this approach in this paper. For completeness we give a discussion of privacy amplification for BandMF Appendix A.
6

---

It's My Data Too: Private ML for Datasets with Multi-User Training Examples
DP-MF (syn)
DP-MF (real)
- k=2 (no dup)
- k=3 (no dup)
- k=4 (no dup)
greedy
random
DP-SGD (syn)
DP.SGD (real)
---- k-2 (dup)
k-3 (dup)
k-4 (dup)
random (low)
random (high)
(a) DP-SGD vs. DP-MF
(b) Effect of duplication
(c) Compare with random selection
3.6
3.6
test loss
3.4
3.4
3.2
3.2
3.2
3.0
2
2
24
2
2
2
2
2 E
2
2
2
2
2
2
2
E
6
Figure 2. Results the arXiv dataset. We plot the test loss function e.
-- no dup
dup
which includes 5 examples and still satisfies the bound k: = Since we have more examples the same contri- bution bound training on the duplicated dataset will require less noise for DP, but it may also be overly biased towards the hyperedge (B, C).
(a) regular graph
(b) skewed graph
0.66
tes accurney
0.66
In Figure 2(b) we plot the test loss for arXiv, comparing the two algorithms across a sweep of different contribution bounds. For the arXiv experiment, duplication consis- tently better than no duplication across all E and contribu- tion bound values, suggesting for this task noise reduction is much more important than bias reduction. In Figure 3 we do the same for the logistic regression experiment. Here we see threshold for the value, E", where duplication helps only at & < E". For smaller e, noise is larger and thus it is more important to reduce than bias. We observe a larger s* the skewed graph compared to regular graph. We believe this is because for a skewed graph, under fixed contribution bound & more users will have k examples than for the regular graph, so the size of the dataset under contribution bound k will be smaller and hence the DP noise needed will be larger. As a simple example, in a k-regular graph we can include all examples, but in a graph where half the users' degrees are 1 and the other half's are 2 1, we will need to remove constant fraction of the examples satisfy the contribution bound. We will revisit the Mariinain tradeoff in Section 5.5.
0.62
2-
22
2'
2
20
2
2
2
Figure 3. Impact of duplication in the regression task.
tokenizer and sequence length of 512. The training objective cross entropy loss for masked token prediction. We report the prediction loss of the final model on the test set & E 10-10 The pretrained checkpoint we
(22, (..,....,2)) 2,,, use as initialization has loss 4.955, far larger than that of any of the private models we train. Due to space constraints, further details of training are deferred to Appendix C.2. For the logistic regression task, we fit a linear model with weight w Rd and bias b E R. The training objective cross-entropy loss. We report the prediction accuracy of the final model (using threshold 0.5) on the test set at E (2-3,2) 3,-3,222, ,...., 263. 10-10.
5.2. Duplicates vs no duplicates
For DP-SGD we have two variants of the contribution bounding algorithm,
that allows duplicates and one that does not. Allowing duplicates allows to increase [S] while satisfying the same contribution bound, in turn reduc- ing the DP noise, but this comes at the cost of potentially increasing the sampling bias of S.
5.3. DP-SGD DP-MF
We next compare the DP-SGD and DP-MF noise addi- tion algorithms and their corresponding greedy contribution bounding algorithms (based on the previous section, for DP- SGD we focus on the contribution bounding algorithm that allows duplicates). Recall that in e.g. the example- DP setting, DP-SGD with privacy amplification and its privacy analysis is a special case of DP-MF with privacy amplifica- tion and its analysis (Choquette-Chne Chooo al., 2024). In the case, the set of known amplification results are limited (see Appendix A) and we believe it is an impor- tant open question to give tight amplification guarantees for
To understand the benefits and detriments of dupli- cation, as a simple example, suppose our users are {A, C,C, D) and our examples
associated with hyper- edges {(A), (A, B). (A,C), (B, C), (A, D)). If our contri- bution bound is k = 3, without duplicates we can get a dataset of size at most 4, since we have to discard one of the hyperedges including A. However, with duplicates we can use the dataset {(A), (A, B), (A, D), (B, (B,C))
7

---

It's My Data Too: Private ML for Datasets with Multi-User Training Examples
DP-SGD
DP-MF
non noon-riivate
im improved selection
-- random (high)
naive selection
random
large blas
du =
du
greedy
small bias
best degree
random (low)
0.65
0.65
(c) gredd vs randoo
125k
0.60
0.60
(a) impaci of the improved selection
subsets the sams size
0.66
accumny
0.66
0.50
0.50
0.64
22
2
0.64
0.62-
0.65
0.65
2a
2
2
2
2
2
2
2
[E] 8M
(b) best degree
(d) best degree at different blas level
0.60
0.60
2.50
2.50
0.55
22
2
0.55
22
degres
2.00
2.00
1.50
Figure 4. Comparing DP-SGD vs. DP-MF in regression.
1.50
2
2
user-Ievel DP-MF with example-level sampling (in both the single- and multi-attribution case). We emphasize that if we had tight guarantees, DP-SGD in the multi-attribution setting and its analysis would also be a special case of DP- MF and its analysis, and one could default to DP-MF in all settings. However, in absence of such tight guarantees, we are required to choose between DP-SGD with privacy ampliiication and DP-MF without privacy amplification.
Figure 5. Experiments on data bias in the regression task.
more uniformly across the examples, which would mitigate this bias. The improvement of DP-MF in (iii) can be ex- plained by the fact that high-privacy-loss events where a user contributes multiple times to the same batch are more frequent in this setting, but DP-MF's min sep condition avoids this possibility altogether.
In Figure 2(a) we compare the relative performance of DP- SGD and DP-MF at different E the arXiv dataset. We observe that DP-SGD outperforms DP-MF at all e. We addi- tionally observe that this holds even after we replace the real arXiv graph by a randomly generated regular hypergraph. We believe this is in part because our tuned parameters use a small number of iterations per epoch, which reduces the min sep b. DP-MF benefits from larger min sep (Choquette- Choo al., 2024) and hence the advantages of DP-MF are minimized in this setting.
5.4. Greedy vs ILP
We next study the suboptimality of the contribution bound- ing algorithm. We write and solve an integer linear program to find exact solutions for the contribution bounding prob- lem. For arXiv without duplicates, the greedy algorithm only selects R 1.3% fewer samples than the ILP, which translates to a negligible difference in test performance. This is evidence that the hardness of the contribution bound- ing problem mostly pathological, i.c. there is limited room to improve training by trying to tackle the underly- ing combinatorial optimization problem. With duplicates the ILP actually includes fewer distinct examples. We give details on the ILP and results in Appendix C.4.
In Figure 4 we compare DP-SGD and DP-MF's test accu- racy on logistic regression for different instantiations of the synthetic dataset. Across the various dimensions we ex- amined (graph structure and size, examples per user, and values), identify scenarios where DP-MF can have edge over DP-SGD. The advantage becomes more evident when: (i) is larger, (ii) the graph structure is more skewed (heterogeneous users), or (iii) when users on average at- tribute more samples. The improvement of DP-MF in (i) is due to amplification being weaker at higher and is consis- tent with comparisons in past work (Choquette- Choo al., 2024). We believe the improvement of DP-MF in (ii) is because skewed graphs lead to higher percentage of dupli- cates in S for our DP-SGD contribution bounding algorithm (which will only add these duplicates for users with few examples), which increases bias. The DP-MF contribution bounding algorithm does not enforce hard contribution bound, i.e. whatever duplicates it adds may be distributed
For DP-MF, we can again write an IIP, given in Ap- pendix C.4. However, this ILP requires many more variables than our ILP for DP-SGD, our solver did not finish in any of our empirical settings. It remains an interesting prob- lem to determine the suboptimality in practice of the greedy algorithm for the DP-MF contribution bounding problem.
5.5. Bias vs num examples
Any contribution bounding algorithm that aims to maximize |S] is likely to bias towards examples with fewer users. We first study the impact of this bias on training performance, and then study algorithms which attempt to mitigate this bias at the cost of including fewer examples.
8

---

It's My Data Too: Private ML for Datasets with Multi-User Training Examples
Our initial experiment involves selecting random sets of examples of the same size as the solution arrived by the greedy algorithm, disregarding the consideration for contribution bounding at all. That is. if S is the solution arrived at by the greedy algorithm, we sample a random subset of the dataset D of size |S], S". We then compare training on and S' using the same noise multiplier, even though S' might violate the contribution bound and thus not satisfy the same privacy guarantees. In this way, the only difference between the test performance after training S instead of S' is due to the bias in example selection. In addition to choosing S" by sampling a random subset of D as a whole, we consider sampling a random subset of examples which have S и (called "random (low)") or > u users (called "random (high)") where is the median of {leal : eg E E).
the bias all. In conjunction with the results in Section 5.2, this suggests that for transformer training reducing the DP noise should be the primary goal in contribution bounding.
A Acknowledgements
We are thankful to: Zachary Charles, for sharing preprocess- ing utilities for the arXiv dataset. Peter Kairouz for feed- back on an initial draft of this work. Vincent Cohen-Addad, Alessandro Epasto. Morteza Zadimoghaddam, Galen An- drew, and Amlan Chakraborty for discussions on scalable algorithms for contribution bounding. Thomas Steinke, for discussions on definitions of privacy for network data. The anonymous reviews for useful feedback on the initial sub- mission.
In Figure 2(c) and Figure 5(c) we compare the test perfor- mance of the greedy algorithm and different random selec- tion strategies. For arXiv, we see that the greedy algorithm performs noticeably worse than training on a random subset, with the increase in test loss comparable to decreasing the privacy parameter& by multiplicative factor of /2 more. A random subset of examples with u users achieves as good or better performance than random subset of all data, i.e. examples with more users tend to be higher quality. We observe similar comparisons for logistic regression, suggest- ing our bias term in the synthetic data generation captures the phenomenon of examples with more users being higher quality reasonably well.
Impact Statement
Since we are advocating for model training under stricter privacy definitions, we anticipate the societal impact of this paper (as with most other papers in preeevig machine learning) is strictly beneficial and does not need to be discussed in detail here.
References
Balle, B. and Wang. Y.-.. Improving the gaussian mecha- nism for differential privacy: Analytical calibration and optimal denoising, In International Conference on Ma- chine Learning, pp. 394 403, 2018
Because the impact of bias is significant, we consider variant of our greedy contribution bounding algorithm which mitigates the bias. Our algorithm splits the dataset into two groups, examples D, which have < u users and examples De which have > u users, for some u. Rather than take a pass over the whole dataset, we take a pass over examples in D. followed by 02 in De, alternating between the two. The choice of u, C1, C2 can be tuned to tradeoff average examples per user (i.e.. bias mitigation) and dataset size. We describe the tuning procedure in Appendix C.5. We then examine the learning outcome of these various datasets of different degrees and sizes.
Balle, B.,, Barthe, G., and Gaboardi, M. Privacy amplifica- tion by subsampling: Tight analyses via couplings and divergences. In Bengio, S., Wallach, H. M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Sys- tems 31: Annual Conference on Neural Information Pro- cessing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada, pp. 6280-6290, 2018.
Bassily, R., Smith, A., and Thakurta, A. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Proc. of the 2014 IEEE 55th Annual Symp. on Foundations of Computer Science (FOCS), pp. 464-473, 2014.
Experiments on logistic regression shows that carefully pick- ing a sweetspot in the degree-size tradeoff can lead non- negligible improvement compared to the naive greedy solu- tion. In Figure 5(a-b) we plot the improvement in test accu- racy due to optimizing this tradeoff, and the average degree of the dataset optimizing this tradeoff. As an additional com- parison, in Figure 5(d) we reproduce Figure 5(b) but after generating datasets with b's magnitude increased/decreased by 10x. In contrast, for arXiv we found that for the full range of spanned by our experiments, the tradeoff was op- timized by maximizing the dataset size, i.c. not mitigating
Berman, P. and Furer, M. Approximating maximum inde- pendent set in bounded degree graphs. In Proceedings of the Anmual ACM SIAM Symposium on Discrete Al- gorithms, Proceedings of the Annual ACM SIAM Sym- posium on Discrete Algorithms, pp. 365-371. Publ by ACM, 1994. ISBN 0898713293. Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms Conference date: 23-01-1994 Through 25-01-1994.
Blocki, J., Blum, A., Datta, A., and Sheffet, O. Differentially
9

---

It's My Data Too: Private ML for Datasets with Multi-User Training Examples
private data analysis of social networks via restricted sensitivity. In Kleinberg, R. D. (ed.), Innovations in Theoretical Computer Science, ITCS '13, Berkeley, CA, USA, January 9-12, 2013, pp. 87-96. ACM, 2013. doi: 10. 1145/2442443.242224442 URL. https:/ /doitoro//////oooooooooooo.oo.o. 24222442222222224494
Day, W. Li, N., and Lyu, M. Publishing graph degree distribution with node differential privacy. pp- 123-138, 2016. doi: 10.1 0A1144//882903.22277222
Denisov, S., McMahan, H. B.,, Rush, J., Smith, A., and Guha Thakurta, A. Improved differential privacy for sgd via optimal private linear operators on adaptive streams. Advances in Neural Information Processing Systems, 35: 5910-5924, 2022.
Borgs, C., Chayes, J. T., and Smith, A. D. Private graphon estimation for sparse graphs. In Cortes, C., Lawrence, N. D., Lee, D. D., Sugiyama, M., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp. 1369- 1377, 2015. URL. https://prrceeedngg
Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. BERT: Pre-training of deep bidirectional transformers for lan- guage understanding. In Burstein, J., Doran, C., and Solorio. T. (eds.). Proceedings of the 2019 Conference of the North American Chapter of the Association for Com- putational Linguistics: Human Language Technologies Volume I (Long and Short Papers), pp. 4171-41B 186, Min- neapolis, Minnesota, June 2019. Association for Compu- tational Linguistics. doi: 10. 10.18663/v1/N119-444 URL https: httss://acaaatthooag.ooo wwwployyy..ggNN99-14.4140
neurips. cc/ cc/papprr2015/hash/ htteee9333cllccccaaa22eeeee html.
Absttratt.
Borgs, C., Chayes, J. T., Smith, A. D., and Zadik, I. Reveal- ing network structure, confidentially: Improved rates for node-private graphon estimation. In FOCS, pp. 533-543, 2018. doi:
DP Team. Google's differential privacy libraries., 2022.
https: http://ggtttbhhcc. com/google/ di f.fferenttlll-rrivee.
Charles, Z., Ganesh, A., McKenna, R., McMahan, H. B., Mitchell, N., Pillutla, K., and Rush, K. Fine-tuning large language models with user-level differential privacy, 2024.
Dwork, C., Naor, M., Pitassi, T., Rothblum, G. N., and Yekhanin, S. Pan-private streaming algorithms. In ics, pp. 66 66-80,20 2010.
URL https: //axxvivvvv.//////// /bwpg//bb//400... 07737.
Fang, J., Dong, W., and Yi, K. Shifted inverse: A gen- eral mechanism for monotonic functions under user dif- ferential privacy. In Yin, H., Stavrou, A., Cremers, C., and Shi, E. (eds.), Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS 2022, Los Angeles, CA, USA, Novem- ber 7-11, 2022, pp. 1009-1022. ACM, 2022. doi: 10. 1 1145/3548606.35665677 URL https: //doi.or///////// 10. 1..11155358866 3560567.
Chen, S. and Zhou, S. Recursive mechanism: towards node differential privacy and unrestricted joins. In Ross, K. A., Srivastava, D., and Papadias, D. (eds.), Pro- ceedings of the ACM SIGMOD International Confer- ence on Management of Data, SIGMOD 2013, New York, NY, USA, June 22-27, 2013, pp. 653-664. ACM, 2013. doi: 10.1 10.145//463676224555004 URL https: //doi.orr///// 100
221.:/22466666..66666 2463344.
Google. Or-tools google optimization tools., 2024. https://github: com/ http://gogll////too//
Choquette-Choo, C. A., McMahan, H. B., Rush, K., and Thakurta, A. Multi-epoch matrix factorization mech- anisms for private machine learning. arXiv preprint arXiv:2211.065300 2022.
Jain, P., Smith, A. D., and Wagaman, C. Time-aware projec- tions: Truly node-private graph statistics under continual observation. In IEEE Symposium on Security and Privacy, SP 2024, pp. 127-145, 2024.
Choquette-Choo, C. A., Ganesh, A., McKenna, R., McMa- han, H. B., Rush, J., Guha Thakurta, A., and Xu, Z. (am- plified) banded matrix factorization: A unified approach to private training. Advances in Neural Information Pro- cessing Systems, 36, 2024.
Kairouz, P., McMahan. B.. Song. S., Thakkar, O., Thakurta, A., and Xu, Z. Practical and private (deep) learning without sampling shuffling. In ICML, 2021.
Kalemaj. I., Raskhodnikova, S., Smith, A. D., and Tsourakakis, C. E. Node-differentially private estima- tion of the number of connected components. In Geerts, F., Ngo, H. Q., and Sintos, S. (eds.), Proceedings of the 42nd ACM SIGMOD-SIGAN -SAAACAATTTIII Symposium on Principles of Database Systems, PODS 2023, Seat- tle, WA, USA, June 18-23, 2023, pp. 183-194, ACM,
Chua, L., Ghazi, B., Huang, Y., Kamath, P., Kumar, R., Liu, D., Manurangsi, P., Sinha, A., and Zhang, C. Mind the privacy unit! user-level differential privacy for language model fine-tuning. In First Conference on Language Modeling, 2024. URL hitps: http:::://peeeeeiie..... /pwp//eeee.....ece/e/ee net// forum? 2SD.
10

---

It's My Data Too: Private ML for Datasets with Multi-User Training Examples
2023. doi: 10.1445/35433223888671. URL https:
Steinke, T. Composition of differential privacy & privacy
amplification by subsampling. 2022. URL https:/
arxiv, org/abs /trgg/bbb/2200.0 2210. 00597.
Kasiviswanathan, S. P., Nissim, K., Raskhodnikova, S., and Smith, A. Analyzing graphs with node dif- ferential privacy, In Sahai, (ed.), Theory of Cryp- tography 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceed- ings, volume 7785 of Lecture Notes in Computer Sci- ence, pp. 457-476. Springer, 2013. doi: 10.1007/ 978-3-642-36699--2,, URL https:ttp//........ httess/ddoooooogo 1001007/9970
McKenna, R. Scaling up the banded matrix factorization mechanism for differentially private ml. arXiv preprinl arXiv:2405.15913. 2024.
McMahan, H. B., Ramage, D., Talwar, K., and Zhang, L. Learning differentially private recurrent language models. arXiv preprint wxXvv:710.00663, 2017.
Ponomareva, N., Hazimeh, H., Kurakin, A., Xu, Z., Denison, C.. McMahan, H. B., Vassilvitskii, S., Chien, S., and Thakurta, A. G. How to dp-fy ml: A practical guide to machine learning with differential privacy. Journal of Artificial Intelligence Research, 77:1113- 1201, July 2023. ISSN 1076-9757. doi: 1. 14649, URL http: //dx. org 10. 1613 // 1..r...164...
Raskhodnikova, S. and Smith, A. D. Lipschitz extensions for node-private graph statistics and the generalized ex- ponential mechanism. In Dinur, (ed.), IEEE 57th An- mual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pp. 495-504. IEEE Com- puter Society, 2016a. doi: (0.1109/FOCS,200 6.16. URL ht https: //ooi.
/t/./oi.ooo org. 1ttp:/.......//.11.1... 1109/F0CS..... /tt.://....22000 2.016.66 60.
Raskhodnikova, S. and Smith, A. D. Differentially private analysis of graphs. In Encyclopedia of Algorithmss, pp- 543-547. 2016b. doi: 10.1007/ URL httphhtt///// 10. 10.1007/9788 1-4939-2864--1 :ttpsi////iiieee ///oo..orrr org/
Sealfon, A. and Ullman, J. Efficiently estimat- ing erdos-renyi graphs with node differential privacy. Journal of Privacy and Confidential- ity, 11(1), 2021. doi: 10.29012//pe.745. URL.
https:  http:///wwn.pp.aaacooicieeaaaaaa org/index. httpiineeepppppppeeepeeppppppppe http://ppppaaaaticee///////////a
Song. S. Chaudhuri, K., and Sarwate, A. D. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pp. 245-248. IEEE, 2013.

---

It's My Data Too: Private ML for Datasets with Multi-User Training Examples
A. Poisson Sampling with DP-MF
Cyclic Poisson Sampling with DP-MF Recall BandMF is characterized by b-banded strategy matrix C (C., = 0 for i i-j b 1) which determines the correlation structure: setting gives independent noise DP-SGD, BandMF can be combined with Poisson sampling, and since BandMF generalizes DP-SGD, in the single-attribution setting this gives strict generalization of DP-SGD with Poisson sampling, L.e. this mechanism is never worse and often better (Choquette- Choo et al., 2024). However, the privacy guarantee of this mechanism requires a very specific minibatch sampling strategy. Specifically, we must partition our users into groups, for each group collect the subset of examples Do...., Do-1 only attributed to users in that group, then cyclically iterate through subsets and Poisson sample from each one (i.e. in round i, we subsample from Dj (mod 6)). This sampling strategy endows the mechanism with amplification guarantees, enabling it to Pareto-dominate DP-SGD and other variants of DP-ME. This sampling strategy is possible in our multi-attribution setting, and the noise multiplier required to satisfy (s, 6DD can readily be computed with the same function used for DP-SGD (DP Team, 2022; Choquette- Choquette-Choo& al., 2024). The main drawback of this approach (unique to the multi- attliiitttibtioonn setting) is that examples attributed to users belonging different groups discarded, which may comprise a large fraction of the dataset. Deciding how to partition the users to minimize the amount of discarded data is a generalization of the NP-hard k-cut problem, adding even more complexity to our contribution bounding strategy. So, we do not consider this approach in our work and leave an exploration the effectiveness of this approach in the multi-attribution setting to future work.
B. Deferred Details from Section 4
B.I. N.L.N--OR NP-Hardness of Contribution Bounding
Given independent set instance, is attributed to each user corresponding to the edges adjacent to the example's vertex. Setting k = 1, any solution to the contribution bounding problem corresponds to an independent set of the same size. Hence, the contribution bounding problem (when the objective is to maximize |SS)) is NP-hard even for k = 1, and e.g. even to approximate to within a constant factor, or if each example is attributed by at most 3 users (corresponding to independent set on bounded-degree graphs) (Berman & Furer, 1994).
create example for each vertex, and user for each edge. Each example
B.2. Pseudocode for Algorithms
Algorithm 2 Greedy contribution bounding algorithm for DP-SGD (without duplicates)
Inputs: Dataset with attribution graph G, contribution bound
1: Sort examples in D by increasing cardinality of corresponding edge in G.
2: S --0 ()
3: for example æ in D do
4: S {x} satisfies contribution bound for all users then
5:
S-
6: end if
7: end for
8: return S
12

---

It's My Data Too: Private ML for Datasets with Multi-User Training Examples
Algorithm 3 Greedy contribution bounding algorithm for DP-SGD (with duplicates)
Inputs: Dataset with attribution graph G, contribution bound
1: Sort examples in D by increasing cardinality of corresponding edge in G.
2: 5
empty multi-set
3: for example x in D (repeated) do
4: S {a) satisfies contribution bound for all users then
5:
5 S {z}
6: end if
7: No examples were added to S since the last time we processed x then
8: return S
9: end if
10: end for
Algorithm 4 Greedy contribution bounding algorithm for DP-MF
Inputs: Dataset with attribution graph G, iteeations T, batch size B, min sep parameter
1: Sort examples in D by increasing cardinality of corresponding edge in G.
2: S
--] |
D empty list
3: while [S] STB do
4: x next example in (repeated)
5: if UUSUU {a) satisfies b-min sep with batch size B then
6:
S {z}
7:
end if
8: if No examples added to S since the last time processed x then
9: return No solution found
10: end if
11: end while
12: return
C. Deferred Details and Results from Section 5
C.1. More Details on Synthetic Data Generation
For our synthetic hypergraphs, we use two sampling procedures. Recall we start with a target number of hyperedges |E} expected users per example Eijel] and expected examples per user du.
Probabilistic regular graph For this graph, we assign each edge to each of the m users with probability [E[le]] /.. This leads to binomial sampling process where the expected edge arity is E]]e]] desired. To improve over the computational efficiency of this binomial sampling, note that is large and E[[e[]/me m is very small, enabling us approximate this binomial distribution with Poisson distribution. Concretely, for each edge e, we: 1) Sample the edge arity ne from Poisson(E[[e]]] 2) Choose users uniformly at random from the total users. This two-step approach preserves the desired average edge arity of [[[e]] while being more efficient than the exact binomial sampling.
Skewed graph: this graph, we attribute edges to users in a sequential manner. After determining the number users and expected edge arity R[[e]], let (j) denote the current degree of user j. For the ith edge, we attribute to user j with probability E1 (1+4.0')) That is, users who already have edges attributed to them are slightly more likely to have future edges attributed to them as well, but we maintain that the average edge arity is Elje]] throughout. The parameter a controls the degree of skewness, with larger a leading to a more skewed graph. We set a = 1.5 our experiment. We present a histogram of the number of edges owned by users in Figure 6, confirming that the graph indeed highly skewed.
[lee][(1d,
13

---

It's My Data Too: Private ML for Datasets with Multi-User Training Examples
(log scale)
10
10
10
10a # Samples (log scale)
Figure 6. Histogram of the number of edges (or samples) owned by user for skewed graph with |E] 125k, d. Elle|] = 2.
Logistic regression data: Each hyperedge e associated with feature 24 E Id (sampled from multivariate normal) and label Yi (0, 1). The groundtruth in the data generation process consists of two components: universal base vector which is shared across all samples, and bias vector b. Both sampled from multivariate Gaussian distribution with covariance 2 such that the average squared f--norm of vector from this distribution is 1. For each example, features sampled randomly from the same multivariate Gaussian, and the label y/4 is thus obtained by randomly sampling from Bernoulli distribution, y/s Bernoulli (iigmoid( (a b |ea], = k1)). where sigmoid [2; k2) 1+oxp(-kpp denotes the sigmoid function with steepness parameter k1. We adopt
20 in all experiments.
To further control how strongly the bias b influences the labels (for the study in Section 5.5), we introduce scaling transformation that replaces a + lealb with 2 14E (a + kle.(b). The parameter k (defaulting to 1) amplifies or diminishes the effect of the bias term, so larger values of place more emphasis on b, while smaller values mitigate its impact.
C.2. More Details on Hyperparameter Tuning
We use Adam our optimizer. For all experiments we sweep over the following parameter choices:
Learning rate: 1 x 10-4,
4- 2 x 10 5 10 10_ 1,,,, x 10 3,- 10 10-3,5x 10-3
Clipping norm: 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01.
Batch size and number of iterations: We keep the product of these fixed. For experiments on arXiv, the fixed product is chosen 20, 480, 000 2 10 and we vary the batch size in 2 212 213 2 2,5 2 for experi- ments on linear regression, the fixed product is chosen as 10, 240, 000 = 2 10 and we vary the batch size in 210 211 212 213, 214 255.
For DP-MF, we sweep the min sep parameter from b = 2 to the smallest value for which Algorithm 4 fails to find solution, minus one.
We use the accounting procedures described in Section 3. We use zero-out (Ponomareva et al., 2023) variant of the adjacency definitions in Section 2 for accounting, although this only changes the a - e mapping and all our observations still hold for arbitrary replacement as well. For arXiv, to understand the behavior of these algorithms in practical setting with much more available compute (which usually leads to reduced noise; see Figure 1 of (Ponomareva et al., 2023) for more discussion), we employ a standard research practice of computing the noise multiplier assuming hypothetical batch size that is larger than the physical batch size used for training. Concretely, we adopt a hypothetical batch size of 218 for physical batch ranging from 23 to 26 and a hypothetical batch size 2 for physical batch ranging from 20 to 2 The practice of assuming larger batch/dataset sizes for accounting has been previously used by Charles et (2024).
C.3. More Details on Contribution Bounding for Different Graphs
We apply the greedy contribution bounding algorithm (Algorithm 3) to the synthetic graphs, varying in the graph structure, graph size, and expected examples per user. We present the size of the resulting contribution bounded datasets in Figure
14

---

It's My Data Too: Private ML for Datasets with Multi-User Training Examples
=E|= k=1
[E]=125K, k=2
Regular Skewed
Regular
80000
samples
40000
Skewed
58.1%
60000
60.2%
20000
40000
50.0%
41.8%
20000
43.3%
du=2
du=4
du=8
d,=2
du=4
du=8
|E|=1M, k=1
|E|=1M, k=2
400000
Regular Skewed
Regular Skewed
samples
300000
600000
200000
55.6%
400000
57.6%
# 100000
39.
200000
40.6%
32.1%
33.0%
0
0
2
d,=4
d,=8
d,=2
du=4
du=
Figure 7. Size of resulting datasets obtained via contribution bounding (Algorithm 3), contrasting a regular graph with skewed graph, across different graph size [i] (rows), contribution hounding parameter GELS (columns), and expected examples per user d. (groups within subtigure). The annotated percentages indicate proportion of retained dataset for the skewed graph relative to the regular graph.
[E| =M
300000
Regular Skewed
200000
50.0%
100000
42.9%
25.0%
d,=2
d,=4
du=8
Figure 8. The maximum feasible 6 when applying greedy contribution bounding for DP-MF (Algorithm 4) on regular vs. skewed graphs, across different expected examples per user dy.
The key takeaways are as follows. First all, skewness presents additional challenges the selection problem. Second, the negative impact of skewness gets amplified when: 1) data size increase (comparing vertically) or user owns samples (comparing horizontally in each subfigure).
Experiments on greedy contribution bounding for DP-MF (Algorithm 3), as presented in Figure 8, points to similar conclusions.
C.4. More Details on Greedy vs ILP Selection
While the contribution bounding problem is NP-hard even to approximate, for our research-scale datasets, we are able to formulate the contribution bounding problem as an integer linear program (ILP) and solve this ILP (for small values of k) to determine the suboptimality of the greedy algorithm. For DP-SGD, the contribution bounding problem is equivalent to the following IIPP:
max Σ 24
Vj:
Σ k.
Vi (0.1).
GER
E:fee
Here, each index represents an example and each index j represents a user, and x; is variable which is we include
15

---

It's My Data Too: Private ML for Datasets with Multi-User Training Examples
example in the subset S. The objective is to maximize the number of examples included, and the constraint Eijce, ii enforces that user j doesn't contribute more than & examples. If allowing duplicate examples, r; {0, } with the constraint I; Zzo.
replace
We solve the ILP using the open-source solver GLOP (Google, 2024) and compare the number of examples found by solving
the ILP and by our greedy algorithm (without duplicates). In Figure 9 we first compare the number of examples chosen by both methods when run on the arXiv dataset, without allowing duplication. Because our solver did not finish for 3, we only give results for the settings k 3.
Method
Contribution bound
Examples selected
Greedy
2
370019
ILP
2
374663
Greedy
3
475831
II.P
3
482128
Figure 9, Examples selected by greedy algorithm and ILP from the arXiv dataset.
We see that for both settings the greedy algorithm retrieves = 98.7% of the ILP solution value, suggesting the hardness of the combinatorial optimization problem has minimal impact in practice. In Figure 10 we show that this translates minimal degradation in the noise multiplier and test loss. For the noise multiplier, greedy achieves worst 1. 1.25% larger noise multiplier than the ILP solution at all values, and for the test loss the increase is at most .25%.
1.0125
1.0100
Ratio
1.0075
Ratio of noise multipliers
Ratio of test losses
1.0050
1.0025
1.0000
16
32
64
Epsilon
Figure 10. Ratio of the noise multiplier/test loss achieved by greedy versus II.P
When allowing duplicate examples, the ILP finds more examples, but fewer distinct examples as shown in Figure 11, leading to worse training outcomes. This is because the ILP can choose solutions which duplicate single-author examples many times, whereas the greedy algorithm will have to take pass over the entire dataset and try adding all examples before is allowed pick its first duplicate, which limits its ability to overselect examples with few authors.
Method
Contribution bound
Examples selected
Distinet examples selected
Greedy
2
442902
370019
II.P
2
462001
231335
Greedy
3
651409
475831
ILP
3
692943
231429
Figure Examples selected by greedy algorithm and ILP from the arXiv dataset when duplication allowed.
We also state an IL. for forming batches with (k: b--min sep for completeness. The II. as follows:
16

---

It's My Data Too: Private ML for Datasets with Multi-User Training Examples
3.3
10ck
150k
200k
250k
300k
3504
Dataset Size
Figure 12. The dataset size and average edge degree of the 80 datasets generated by bias-mitigatigg variant of Algorithm 2.
min
k
=+b-1
stt.j,
[T b b+b
Σ
Di, S I,
kjEe t=tt
Vj.
Ti,t S k.
e:fei EE[T]
Vt: Σ 24,t B,
Wi E (0,
The objective is to minimize the contribution bound k. Each example and time step has variable 24,1 which is if example is included in the f-th batch. The constraint Enjee Lv' Tg,t' I 1 says that user does not have more than one example attributed them in batches t b 1, i.c the b-min sep condition holds for these batches. The constraint Ensge, EiERT Fi S l ensures each user's contribution bound is at most kt The constraint Ee,er Fi.t B enforces that the t-th batch has exactly B examples.
C.5. Details Bias Num Examples Experiments
As described in Section 5.5, we consider variant of Algorithm 2 that splits the dataset into two groups, "small" examples D. which have < users and "large" examples D; which have users, for some The algorithm takes pass c₁ examples in D, followed by c2 in D,, alternating between the two.
For these experiments we fix contribution bound of 3. We sweep the threshold vr E (1,2,3,4) and consider e 1, 02 E (1, 10} and e₁ E {1, 2, .. 10), C2 = 1. This gives grid of 80 hyperparameter settings which each generate a dataset. We plot the 80 datasets' sizes and average edge degree (users per example) Figure 12. We observe that some datasets have both smaller dataset size and average edge degree than another dataset. Hence for training, we only consider datasets that not Pareto dominated in these dimensions. In other words, for the datasets do training on, the average degree is monotonically decreasing in their dataset size, and report either quantity alone as a proxy for point the tradeoff" curve between these two quantities.
17


Reviews:
[{"review_id": "PEBvL4jEXA", "reviewer": "Reviewer_z4vo", "summary": "The work describes how to apply two differentially private training methods for data in which more\nthan one individual can contribute to each data instance (i.e. email sender and receivers, or\nauthor set in a publication). The approach is based on building a subset of the dataset so as to\nupper bound the number of contributions (i.e. emails involved in, papers authored) each individual\nis involved in (as a configurable parameter). Several mostly greedy methods are used to find this\nsubset. Once this subset is available, existing DP training methods can be used. The subsetting\nmethod does not incur any privacy cost due to the paper's interpretation of an individuals'\ncontribution to a dataset: their relationships to instances are not private, only the instance\ncontents are (i.e. the contents of emails or papers are considered private but authorship or\nsender/receivers of emails are not).\n\nExperiments exemplify the method on arXiv paper abstracts with contribution defined by authorship.\nTo investigate some aspects of global authorship metrics, synthetic datasets where authorship is\ngenerated are also analyzed. First, the greedy subsetting methods are demonstrated to be relatively\nclose to the optimal by comparing them to solutions derived using integer programming. For the\nexperimental task, masked token prediction is used. A small BERT model is fine-tuned using two DP\nSGD methods with data drawn as per the proposed methodologies. A baseline without DP is also\nincluded. The experiments show mostly expected results with respect to the privacy parameter though\nalso shown is that both DP SGD methods have situations under which they perform better.\n\n## update after rebuttal\n\nDiscussion regarding edge/node privacy suggested there is a path towards acceptance if the paper\nbetter presents its limitations and consequences of those limitations both in terms of privacy and\nwhat sorts of ML methods the formalism can be applied to (i.e. not graph ML). I have raised my\nscore to weak reject. The bulk of my other objections, the levels of novelty and contributions,\nwill need to be evaluated by the AC for the final decision.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks to the reviewer for their feedback. We agree that broadly, there is much more work to be done to fully understand the multi-attribution model, and part of our goal with this work is to motivate future research into this setting. Below we respond to individual points we disagree with in the review:\n* W1: \n  * __“no claim is made about any suboptimality bounds”__: As mentioned in Appendix B.2, theoretically the problem is known to be hard to approximate to within large factors, even in some very simple settings. So while one could attempt to prove positive theoretical results, these would be overly pessimistic and not give meaningful guidance in practice. \n  * __Q1/“add baselines”__: We use the checkpoint available [here](https://github.com/google-research/bert) as our initialization, which achieves a test loss of 4.955 for arXiv, i.e. is not competitive with DP fine-tuning even at small epsilons. We will state this as a reference point for the empirical results in the revision. Since we introduce fixed-graph DP (and as we discuss in our response to reviewer gGTR, the node-graph DP algorithms are not readily applicable except in trivial settings), besides the not-fine-tuned checkpoint and some other baselines we already included in the paper, we do not feel there are obvious and meaningful baselines to compare our greedy baseline to. However, we are open to suggestions from the reviewer for other baselines to consider adding in the revision. \n* W2: \n  * We are glad the reviewer raised the question of appropriate DP formulations; in fact, one of the main goals for our paper is to provide a better framework for such discussions. Node-DP is not well known in the ML community currently, and hopefully our paper will provide a clear critique to simply applying example-level or user-level DP to settings where examples contain information from multiple users.\n  * At the same time, we also agree that the fixed-graph DP is not as strong as one ideally would want. We spent considerable time looking for ways to scale node-DP, and nevertheless this approach seems very far from being feasible for large-scale ML applications. Given the explosion of GenAI, there is a pressing need for practical approaches in this space that can be offered now.\n  * We do not advocate that _every_ algorithm that achieves fixed-graph-DP is appropriate for ML settings. Our algorithm carefully decouples the use of the graph from the use of the training data. This decoupling excludes the most obvious problematic algorithms (i.e., ones that publish the graph). In fact, despite considerable effort, we were unable to design any realistic attack to exploit our algorithms. At the same time, we also lack a fully satisfactory guarantee. (For example, one can prove statements assuming independence of the training data from the graph structure; but such independence does not hold in practice and we find it unsatisfactory.)\n  * Hence, we propose an approach here that is practical and provides significantly better privacy than the naive application of existing DP ML solutions. Equally importantly, we hope our work highlights the problem, and stimulates future research. We do not advocate for our approach as a complete solution, but feel it is a valuable starting point that already highlights nontrivial choices and phenomena. \n* W3:\n  * __On lacking novelty__: While our greedy algorithms are not very complicated, we believe the fixed-graph DP definition and the contribution bounding framework are meaningful contributions, and we believe our empirical results developing a better understanding of the greedy baseline raise and study non-trivial questions about contribution bounding.\n  * __On tailoring to multi-attribution__: While the greedy algorithm retrieves the trivial strategy maximizing |S| in the single-attribution case, most of our empirical results answer questions which do not make sense to ask in the single-attribution case (e.g. in the single-attribution case, there is no difference from the ILP, no bias towards examples with fewer users). Furthermore, designing a more complicated method tailored to the multi-attribution case is unnecessary if the greedy algorithm is competitive with strong baselines like the ILP solver, which our empirical results provide evidence for.", "claims_and_evidence": "Yes. Note that the paper seems to avoid claiming anything. Some speculation is done around the\nexperimental results but nothing one could object to. This is a weakness which I discuss further in\nthe weaknesses section.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "The paper makes no theoretical claims. There is a point about NP-hardness in the appendix but it\nis mostly a citation.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "The methodology's privacy arguments reduce to DP group privacy. Methods (graph building with\nattribution bounds) are simple enough that they are not based on any recent work. Experimentation\nuses DP-SGD and DP-MF training methods from private ML research.", "essential_references_not_discussed": "I did not check. The paper has sufficient weaknesses already.", "other_strengths_and_weaknesses": "Strengths:\n\n+ S1. Very well written introductory and background sections.\n\nWeaknesses:\n\n- W1. No take-aways or claims that can inform application of the methodology.\n\n  - Examples of suboptimality of the greedy methods shows trivial reduction of number of selected\n    nodes as compared to the optimal method but no claim is made about any suboptimality bounds. It\n    is not clear to what degree one can generalize the experimental observations.\n\n  - Impact of subsetting on masked model difficult to assess. No baseline is shown in Figure 2 to\n    demonstrate how much utility is lost due to either the proposed method or DP-SGD/MF.\n\n  - Suggestion G1. Perform sufficient experimentation to write some take-aways that generalize\n    them. If possible, prove conditions under which suboptimality can be bounded. Add baselines to\n    all experiments which should also help with take-aways. Include a Conclusions sections that\n    summarizes the main take-aways.\n\n- W2. Objectionable assumption about privacy in the setting. The \"Fixed-graph (multi-attribution\n  user-level) DP\" seems to make the assumption that attribution graph itself is not private. A\n  mechanism that outputs the graph adjacency in the plain (without the hyper-edge data xᵢ) would be\n  ε=0 DP. While user identities (i.e. email addresses) are not explicitly modeled, the disregard of\n  adjacency in the privacy calculus suggests that email sender/recipients or authorship are\n  not private/sensitive information.\n\n  The argument for why a recipient of an email should be considered a contributor is that the email\n  might be \"about\" them. A fact that someone is a recipient may have as much if not more\n  information about them than the content of the message.\n\n  Database pairs D, D' as per Definition 2.1 differ only in message/abstract contents. This is not\n  the difference one would expect due to the choice of an individual to participate in the dataset\n  or not. Under what circumstances is a user deciding or not to participate in an email/abstract\n  dataset but is not making the choice of being included or not, but instead is making the choice\n  of the email contents/abstracts being included or not? Including empty emails/abstracts for an\n  emails sent to/received by an individual who wishes not to participate would already be a\n  violation of their agency to consent.\n\n  - Suggestion G2. Either provide scenarios under which the privacy assumptions make sense (email\n    and authorship are not viable as per above discussion) or switch to the Node privacy setting.\n\n- W3. Limited novelty. The novelty in the \"multi-attribution\" setting (each instance may have had\n  contributions from more than 1 individual) doesn't seem to matter to the methodology. The same\n  identical arguments and method could have been used in the group privacy setting without\n  multi-attribution. The impact of multi-attribution is on how large the subgraphs can be as per\n  produced by the methods but those greedy methods do not seem to be tailored in any way to\n  multi-attribution.\n\n  - Suggestion G3. One option is to significantly expand on the take-aways to demonstrate how\n    viable subgraphs with k-bounded attribution are for DP-SGD/MF under a wide range of datasets,\n    tasks, models, etc. This would be more or less a paper focused on addressing W1 above.\n    Alternatively, alternate approaches or techniques that are specific to multi-attribution can be\n    presented and experimented with.", "other_comments_or_suggestions": "See Weaknesses section above for suggestions.\n\nComments\n\n- C1. It is difficult to connect how the synthetic dataset construction models aspects of the real\n  arXiv dataset. One thing that can help is to report quantitative metrics about both synthetic and\n  real, answering the question: the synthetic dataset with parameter choice $ p $ causes metric $ m\n  $ a function of $ p $ and on the real dataset, this metric is equal to $ m' $.\n\n- C2. Considering repeating experiments that feature non-determinism (even in the train split\n  picking) and demonstrate results alongside margins (under some chosen confidence). Many results\n  as plotted seem very close to each other, making it difficult to derive conclusions without\n  considerations of statistical confidence.\n\nSmall things:\n\n-\n\nSmallest things:\n\n- Several uses of \"natural\" in the first 2 paragraphs of Section 4 could be reworded to explain the\n  naturalness instead of assuming it is obvious.", "questions_for_authors": "- Q1. Did the BERT-Tiny model already have masked token prediction layers pre-trained? If so, how\n  did it perform the experimental task before fine-tuning on the arXiv abstracts?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VcAz8wjvvI", "reviewer": "Reviewer_gGTR", "summary": "The paper introduces a novel differential privacy (DP) definition for datasets with multi-user attribution, where each training example is associated with multiple users (e.g. emails attributed to both senders and recipients).\n\nTheir proposed adjacency definition, termed \"fixed-graph DP,\" protects the content of each edge (message) but not the graph structure. This approach enables the design of significantly more practical algorithms compared to the more conservative existing definition (Node DP, Fang et al., 2022).\n\nThe authors address the challenge of bounding user contributions through example selection (an NP-hard problem). They first propose a greedy algorithm and then attempt to improve it using linear programming techniques, though with limited practical impact.\n\nThe paper includes comprehensive experiments that demonstrate optimal strategies for both data selection and DP training algorithms, exploring the tradeoffs between bias and variance in the multi-attribution setting.\n\n## Post-rebuttal update\n\nI choose to maintain my high score. Although I agree that lack of formal protection of a graph structure is concerning, this paper is a first of its kind and proposes a new DP formulation - paving the way for the future work, which can address the issue.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks to the reviewer for their support of the paper. We want to respond to the two gaps raised by the reviewer.\n\n* Gap 1: We agree that the graph structure can be a privacy risk. We do not advocate that _every_ algorithm that achieves fixed-graph-DP is appropriate for ML settings, and do not advocate for actually publishing the graph in practice. While we do not formally protect the graph structure in a DP manner, as discussed at the end of Section 2, the structure of our algorithms (which discard the graph information during training) means they resist straightforward attacks (with non-pathological data). Part of our goal with this work is to invite future research on this problem, including designing attacks on our two-phase algorithms in practical settings.\n* Gap 2: We agree such a comparison could be useful. However, to the best of our knowledge, the only setting where batch gradient queries with node DP would be readily applicable and feasible at scale is when the hypergraph is already bounded-degree, in which case contribution bounding is a no-op and fixed-graph DP/the comparison are unnecessary. While reductions (by truncating some nodes) to bounded degree graphs are known, these reductions are only understood for “2-uniform” graphs (that is, the usual graphs, where edges involve only two nodes, as opposed to hypergraphs, which are the focus of our work).", "claims_and_evidence": "The paper presents a comprehensive body of work - they introduce a new, well-justified definition of privacy, develop methods to bound user contributions, and effectively apply existing privacy accounting techniques. All aspects of their approach are thoroughly proven as necessary.\n\nThe authors explore a good range of algorithmic design options to provide fixed-graph DP. Their investigation covers greedy algorithms, linear programming techniques, and variants that handle duplication and bias mitigation.\n\nThe experimental results effectively demonstrate the viability of their approach across different settings, showing performance on both synthetic and real-world datasets.\n\nOverall, I believe this is a very strong paper with a novel and highly relevant idea, backed by proper evidence and rigorous analysis.\n\nHowever, I note two significant gaps:\n\n1. The paper argues that the additional public data (the graph structure) poses minimal risk because it would be difficult for a practical attacker to exploit given the algorithm design. However, graph structure can often be highly sensitive information (including in their email example). More evidence is needed to support their claim that this doesn't undermine the privacy guarantees - otherwise, the provided guarantees may not be as meaningful as presented.\n\n2. The paper compares their approach to a stronger definition (Node DP), arguing that their definition relaxation allows for more practical algorithms. I would like to see a comparison on \"nice\" graphs - cases where Node DP has practical implementations - to better understand at what point fixed-graph DP becomes an essential tradeoff. This would help clarify when each approach is most appropriate.", "methods_and_evaluation_criteria": "The paper proposes a well-justified set of methods to address privacy in the multi-attribution setting.\n\nThe experimental methodology is sound, utilizing both synthetic data (allowing for controlled investigation of specific parameters) and real-world arXiv data (demonstrating practical applicability). The authors thoughtfully explore key algorithmic tradeoffs, particularly the balance between noise reduction and bias mitigation across different privacy budgets.\n\nAs noted previously, however, a more extensive comparison with node DP would significantly enhance the paper. While the authors convincingly argue for the theoretical advantages of their approach, empirical comparisons on graphs where node DP solutions are feasible would provide better context for understanding when fixed-graph DP becomes an essential tradeoff.", "theoretical_claims": "The paper introduces a new privacy definition (fixed-graph DP) that's well-formulated for the multi-attribution setting. The authors rigorously prove that their contribution bounding algorithms satisfy this definition and demonstrate how existing DP-SGD and DP-MF accounting techniques can be appropriately applied in this context.\n\nThe theoretical analysis is sound, properly establishing the properties of their algorithms while acknowledging computational limitations like the NP-hardness of the optimal solution.\n\nOverall, the theoretical foundation is solid and well-substantiated.", "experimental_designs_or_analyses": "See \"Methods And Evaluation Criteria\"", "relation_to_broader_scientific_literature": "The paper addresses a highly relevant question of providing DP guarantees on data simultaneously belonging to multiple users. Despite being common in many realistic and sensitive datasets (emails, messages, collaborative documents), the DP literature has lagged in providing appropriate guarantees for such scenarios.\n\nWhile user-level DP has been extensively studied, its application to multi-attribution settings remained largely unexplored. Fang et al. (2022) proposed Node DP to address this gap, but it had significant practical limitations. This paper makes a valuable contribution by introducing fixed-graph DP as a more practical alternative, bridging an important gap in the privacy literature.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Qhy2jnbSsB", "reviewer": "Reviewer_Eu7P", "summary": "The paper studies user-level differential privacy when each training sample can be attributed to multiple users, called multi-attribution model. It proposes a new privacy definition called fixed-graph DP,  where users are nodes and examples are hyperedges. And the neighboring database is defined as arbitrary changes to all examples associated with a single user, which is similar to node-dp in graph dp. \n\nTo apply DP-SGD, DP-MF type of algorithms, we need to select a subset of the dataset where each user contributes a limited number of examples. This is proposed as contribution bounding problem, which is NP-hard. The authors present a greedy algorithm for contribution bounding and empirically evaluate it. The paper compares DP-SGD and DP-MF, finding DP-SGD generally outperforms DP-MF in the multi-attribution setting due to privacy amplification challenges with DP-MF.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your support of the paper. We respond to a few points below:\n* __\"The greedy algorithms are somewhat simple.”__: We agree the algorithms are simple, and we have framed them as baselines to emphasize this. We note that our empirical results, which demonstrate the baseline algorithms are quite competitive, suggest developing much more complicated algorithms may be unnecessary in practice (but may still be an interesting research direction). We also agree that part of the goal of this paper is to encourage more work on the multi-attribution setting.\n* __“epsilon larger than 10 does not make too much sense. It is nearly non-private.”__: We agree that in practice epsilons larger than 10 may not give meaningful privacy guarantees. Our goal with studying large epsilons was mainly to extend our empirical understanding to low-noise regimes. We also note that e.g. an epsilon of 64 in one setting can correspond to a much smaller epsilon in a different setting with the same noise multiplier and batch size but e.g. a different dataset size or graph structure, so studying these low-noise regimes may provide useful insights even if one does not believe that the corresponding epsilon is meaningful in practice.\n* __“Potentially harming algorithmic fairness”__: This is an interesting point. Note that contribution bounding also makes the contributions of different users more uniform, so even without differential privacy one might expect contribution bounding to actually increase fairness in this dimension. One could summarize the impact on fairness as, contribution bounding favors examples with fewer users and users with fewer examples. We expect that whether this leads to an overall positive or negative impact on fairness will be highly subjective and context-dependent, depending on what properties of the dataset these quantities (examples per user and users per example) align with.", "claims_and_evidence": "I think there are two claims: 1) The authors proposed a new setting called this multi-attribution model. 2) the proposed greedy algorithm could be used for practical training. The first claim is interesting and practical. The second claim is evaluated based on experiments.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No theoretical proof.", "experimental_designs_or_analyses": "Yes. There are two tasks: training a small transformer on the arXiv dataset, and a synthetic logistic regression task. Both are relatively small scale, but I think it is convincing.", "relation_to_broader_scientific_literature": "This new problem setting multi-attribution model could potentially bring more study and research.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "Strengths: presentation is clear. Problem is interesting.\nWeaknesses: the greedy algorithms are somewhat simple and lack of theoretical novelty. I guess this problem would encourage more research in the future.", "other_comments_or_suggestions": "In those figures, I feel like epsilon larger than 10 does not make too much sense. It is nearly non-private.", "questions_for_authors": "I feel like favoring examples with fewer users could skew the model toward less active or less connected users, potentially harming algorithmic fairness. Do you have any insights or any thoughts on this?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UwcBHG1fWV", "reviewer": "Reviewer_FPm2", "summary": "This paper discusses the user-level privacy under the multi-attribution scenario, where each user is associated with multiple examples but also each example can be attributed to multiple users. It starts with defining the differential privacy used in this case as the fixed-graph DP. Then it goes to discuss how to use some of the known algorithms, DP-SGD and DP-MF for the purpose of multi-attribution data. The paper discusses methods to choose the set S which is a subset of the data where each user contributes at most k examples. This subset needs to be maximized while keeping this restriction.\n## update after rebuttal\nI keep my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your support of the paper, and for the editing suggestions which we plan to incorporate. Here we respond to some of the reviewer’s questions. As space permits, we will plan to include more detailed explanations along these lines in the revision:\n* __“X_i cannot be repeated in e_i”__: We believe this question is asking whether two different edges can have examples with the same content. Our definition does not restrict the values of different x_i, even in relation to each other. This is in line with other DP definitions such as example-level DP or user-level DP in the single attribution model, which do not make any assumptions on the contents of examples in relation to each other.\n* __“Doesn’t some e_i change when changing x_i”__: Here we are decoupling the edge (i.e. users associated with an example) and the content of the example. e.g. For edge-data adjacent datasets D, D’, in D Alice might send Bob the email “how was your surgery?” and in D’ Alice might send the email “are you free for lunch tomorrow?”. In both cases e_i = {Alice, Bob}, but the content x_i has changed (and for edge-data adjacency, the rest of the graph is unchanged).\n* __“duplicates allows for a larger dataset which reduces DP noise…”__: We apologize for not elaborating further in the paper. As a simple example, suppose our users are {A, B, C, D} and our examples are associated with hyperedges {{A}, {A, B}, {A, C}, {B, C}, {A, D}}. If we use k = 3, without duplicates we can get a dataset of size at most 4, since we have to discard one of the examples including A. However, with duplicates we can use the dataset, e.g. {{A}, {A, B}, {A, D}, {B, C}, {B, C}} which includes 5 examples and still satisfies the bound k = 3. That is, we can use duplication (equivalently, upweighting of some examples) to even out users’ contributions and make full use of each user’s allocation. \n* __“more users will have <k examples than for the regular graph and then the dataset will be smaller.”__: For simplicity let’s focus on 2-uniform graphs, i.e. the usual graphs where every edge has two users. Consider the 2-regular graph {{A, B}, {B, C}, {C, D}, {D, E}, {E, F}}. For contribution bound k = 2, by including all edges, every user saturates their contribution bound and we get 6 edges. In contrast, consider the graph {{A, B}, {B, C}, {C, A}, {A, D}, {B, E}, {C, F}}. The number of users/edges is the same, and the average degree is still 2, but half the users have degree 1 and half have degree 3. So under a contribution bound of 2, the best we can do is to include 4 edges (e.g. {{A, B}, {A, D}, {B, E}, {C, F}}. In short, some of the users don’t have enough edges to saturate their contribution bound, and others have too many edges and must discard some, so we can include fewer edges than if the graph were perfectly regular.", "claims_and_evidence": "The paper in general follows well and is understandable, however, some claims raise some questions. I list them below:\n- The claim that allowing duplicates allows for a larger dataset which reduces DP noise. I fail to understand why having duplicates leads to a larger dataset, as we would still have the same limit on contribution.\n- In section 5.2, the authors hypothesize that the skew in the graph is because k more users will have <k examples than for the regular graph and then the dataset will be smaller. Again, I fail to see why this is true.", "methods_and_evaluation_criteria": "The proposed methods and metrics give a clear idea of the advantages of the used method. Also, the comparison of the greedy algorithm with more sophisticated techniques offers a lot of value to the paper.", "theoretical_claims": "There are not really theoretical proofs in the paper as the paper empirically justifies and tests the proposed methods, as well as compares the different techniques.", "experimental_designs_or_analyses": "The experiments are sound and valid as far as I can tell, although I do have the questions I mentioned in the claims and evidence section.", "relation_to_broader_scientific_literature": "The problem at hand is a very important advancement in the literature as it discusses the important and natural extension of multi-attribution. In the real world, in many cases, such as the emails example in the paper, multiple users contributing to a single example needs to be taken into account along with the user-level privacy where a user contributes to multiple examples.", "essential_references_not_discussed": "One reference I found missing is Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., & Zhang, L. (2016, October). Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security (pp. 308-318).‏\nWhen discussing the DPSGD algorithm, it makes sense to cite this work.", "other_strengths_and_weaknesses": "One main strength of the paper is its originality and significance. I think this problem has a lot of important applications and this sheds a lot light on the important techniques that can be used.\nThe paper is generally also well written, although it has some typos which I list in the section below.", "other_comments_or_suggestions": "- In section 1.1: with multiple attributed data, not multiply\n- In section 5.1: considered both regular and skewed graphs, not consider\n- One suggestion is that it is weird that the first figure mentioned is 2(b) instead of 2(a), is there a reason these figures are not flipped?", "questions_for_authors": "I first have the two questions from the claims section, which I copy here:\n- The claim that allowing duplicates allows for a larger dataset which reduces DP noise. I fail to understand why having duplicates leads to a larger dataset, as we would still have the same limit on contribution.\n- In section 5.2, the authors hypothesize that the skew in the graph is because k more users will have <k examples than for the regular graph and then the dataset will be smaller. Again, I fail to see why this is true.\n\nAlso, I have some other questions:\n- In section 2, the definition of the attributed dataset, this seems like $x_i$ can not be repeated in $e_i$? Can you make this clearer whether it can?\n- Also same section when defining edge data DP, it is said that m=m' and $e_i=e'_i$ for all $i\\in [m]$ but differ in one $x_i$. But doesn't some $e_i$ change when changing $x_i$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper is about differential privacy in a setting where each piece of data is possibly attributed to multiple users. It argues that existing DP models for this setting do not scale to modern-ML level, and puts forward an alternative definition called fixed-graph DP. It shows that simple methods to select a subset of the data with bounded attributions (which facilitate DP) perform well empirically.


Reviewer discussion was mostly in consensus about content and substance, despite the wide range of scores. The strength of the paper is in addressing the important matter of new privacy definitions that strike a balance between privacy and feasibility in modern ML. Even if the specific definition given in the paper is not without its flaws, reviewers are hopeful it would spur more research and discussions in this direction, and this appears to be the authors' mindset as well. The weaknesses discussed were about the limited technical contribution of the paper - at the technical level, it only proposes a definition and tests some methods which the authors willingly concede are simple baselines (the contribution is in establishing that even simple baselines already perform well empirically). 


Another particular weakness discussed was the role the graph structure plays in the model, a point that the paper is somewhat vague about. It appears the paper's definition does not consider the graph structure public, yet does not formally protect it. Rather, the authors' "two-phase" methods remove the graph structure from the input to the downstream algorithm, which on the one hand limits applications since it precludes algorithms that rely on the explicit graph structure, but on the other hand does not formally protect the graph structure which could still leak through correlations with user data. Reviewers advise the authors to expand and clarify the discussion of this point in the final version of the paper, and to add a discussion of limitations this might create in applications to graph ML methods.


In the end, the overall opinion was positive about accepting this paper, ideally under a revision that addresses the points above.
Decision: Accept (poster)