Differentially private synthetic data generators promise that the released table reveals almost nothing about any single person in the source data. Differential privacy (DP) is a guarantee that the output distribution barely changes when one unit of data is added or removed. In practice these generators treat that unit as one row. Real sensitive tables are dirty. The same patient appears three times under slightly different spellings, cells are missing, and values contradict each other. When one person occupies several rows, a row-level guarantee at privacy level $\epsilon$ protects that person only at roughly $k\epsilon$, where $k$ is the number of their duplicates. The fix seems obvious: deduplicate and repair first, then synthesize. This proposal argues that the obvious fix is also unsafe. Standard cleaning steps have unbounded influence. A single person's record can bridge two otherwise separate clusters and merge them. It can also tip a majority vote that rewrites a cell in hundreds of other people's rows. The DP noise that the synthesizer adds downstream is calibrated to none of this.
The proposal is to design cleaning operators whose influence is provably bounded. Removing one person's records from the raw data then changes only a bounded number of rows in the cleaned, one-row-per-entity table. That bound can be passed directly to a marginal-based synthesizer such as AIM as its sensitivity. The result would be an end-to-end generator from dirty data with a guarantee stated per person rather than per row. The claim is testable in three ways. One can prove the bound for specific entity-resolution and repair rules. One can measure the utility cost of bounding influence. And one can audit empirically whether naive pipelines leak more than their stated $\epsilon$.
Core Claim
The two literatures have each assumed away the other's problem. Unified cleaning systems treat deduplication, repair and imputation as one coupled process. They assume unrestricted access to the raw data. HoloClean does this through probabilistic inference over a factor graph whose variables are dirty cells. REPLACE does it through declarative merges plus denial-constraint deletions. Rock does it through logic rules with embedded machine-learning predicates. The coupling these systems exploit is exactly what makes their outputs sensitive to single records: transitive merges and global statistics used to fix local cells.
DP synthesizers make the opposite assumption, that the input is already clean. AIM selects low-dimensional marginals (counts over small groups of columns), measures them with noise, and fits a graphical model to the noisy counts. MargNet, from Benchmarking Differentially Private Tabular Data Synthesis Algorithms, trains a small neural network to match noisy 2-way marginals.
The one paper that brings imperfect data into DP synthesis is Differentially Private Data Generation with Missing Data. It handles only missing cells, and it keeps the row as the privacy unit. It even shows that random missingness acts like subsampling and tightens privacy: $\epsilon=1$ on the observed data corresponds to about $0.44$ on Adult with 50% values missing completely at random. Duplicates push in the opposite direction, and that paper does not address them.
We make the claim precise with one definition. A cleaning map $C$ takes a raw table to an entity table with one row per inferred real-world entity. Call $C$ $c$-stable if, for any two raw tables $D$ and $D'$ that differ by all the records of one person,
$$|C(D)\,\triangle\,C(D')| \le c,$$
where $\triangle$ counts entity rows present in one output but not the other; a modified row counts twice. If $C$ is $c$-stable, then every marginal count on $C(D)$ changes by at most $c$ when a person is added or removed. Running AIM with noise scaled to sensitivity $c$ therefore gives $\epsilon$-DP per person for the whole pipeline, and composition handles any budget spent inside cleaning. The research question is whether useful deduplication and repair can be $c$-stable with small $c$, and how much cleaning accuracy that costs.
Research Program
The first component is stable entity resolution. Ordinary deduplication builds a match graph, with an edge wherever two records look alike, and takes connected components. This has unbounded influence, because one bridging record can fuse two large clusters. We will study three restrictions:
- capping each record's number of match edges at $\Delta$, using a data-independent tie-breaking order;
- capping cluster size at $m$, splitting larger components by a fixed deterministic rule;
- replacing transitive closure with bounded-radius clustering around seed records.
For each, we aim to prove a stability constant of the form $c = O(\Delta)$. A person's records touch at most $\Delta$ edges each, so removing them can split or perturb only the clusters those edges reach. We will also show where the argument fails. Deterministic capping must not depend on other people's records in a way that lets one record cascade through the tie-breaking. We treat this as an open technical point, not an assumption. The matching predicate itself can be any fixed similarity function or learned classifier trained on public or held-out data, in the spirit of the classifier-predicates of Parallel Discrepancy Detection and Incremental Detection. Stability depends only on how match edges are aggregated.
The second component is stable repair and imputation. HoloClean-style repair combines two kinds of evidence. Constraint and co-occurrence evidence pooled across the whole table is the source of cross-person influence. Evidence local to an entity, such as conflicting duplicate values, carries no cross-person influence. We split the two:
- Conflicts within an entity cluster are resolved using only that cluster's records. This touches only that entity's row.
- Evidence across entities is replaced by statistics measured under DP: co-occurrence counts for columns linked by functional dependencies, charged to the privacy budget. This makes the repair a post-processing of noisy statistics plus local data, which adds nothing to $c$.
Missing cells are imputed the same way. This extends the budget-reuse idea of the missing-data paper (its KaminoI model imputes with its own partially trained DP model) from missingness to conflicts and duplicates.
The third component is budget splitting between cleaning statistics and synthesis marginals. AIM already selects which marginals to measure with an exponential mechanism, which picks an option with probability weighted by a noisy quality score. We will let the same selection step choose between measuring a synthesis marginal and a repair statistic. The DP statistics that guide cleaning then compete for budget with synthesis on a shared scale. MargNet will be the second generator, because constraint-coupled columns produce the dense correlations under which the benchmarking paper shows AIM's graphical model degrades.
Baselines
The naive reference point is AIM run directly on the dirty table at row-level $\epsilon$. It is what practitioners do today. It will be run with AIM's published configuration and the same marginal workload as all other methods. Its reported $\epsilon$ is a row-level guarantee. We will report both its utility and its effective per-person $\epsilon$, measured by the audit described below. Beating it means matching its utility while giving a valid per-person guarantee.
The group-privacy baseline runs AIM on the dirty table at $\epsilon/k_{\max}$, where $k_{\max}$ bounds duplicates per person. This baseline is formally valid only if $k_{\max}$ is known, so we give it the true value from our controlled corruptions, which is an advantage it would not have in practice. It is the strongest valid competitor that uses no cleaning. Our method beats it if, at equal per-person $\epsilon$, workload error is lower by more than the seed-to-seed spread across five runs.
The strongest existing combination is clean-then-synthesize. Deduplication by transitive closure plus HoloClean repair runs non-privately, and AIM (or MargNet) then runs on the result at $\epsilon$. On Hospital, HoloClean reports precision of about 90% and recall of about 76% (HoloClean), so this pipeline gets the best available cleaning. Its privacy claim is unsupported, because cleaning sensitivity is ignored. It therefore serves as a utility ceiling for "good cleaning, no stability cost." We will also audit its leakage. We do not need to beat its utility. The target is to come within a stated margin while passing the audit it fails.
An oracle runs AIM on the ground-truth clean entity table at $\epsilon$ and bounds everything from above. For context on generator strength: AIM reports an average 1.6x lower workload error than prior mechanisms across its benchmarks, including Adult (AIM). MargNet reports fidelity error 0.121 against AIM's 0.163 on Gauss50 at $\epsilon=10$ (Benchmarking Differentially Private Tabular Data Synthesis Algorithms). No reported result was found on Lacuna for AIM's absolute workload error on Adult, or on any dataset containing duplicates, so all absolute numbers will come from our own reruns.
Two ablations isolate the key ingredient:
- stable entity resolution with ordinary global-majority repair;
- ordinary transitive deduplication with stable repair.
Each should fail the audit on the attack that targets the unstable half.
Why not just…?
Why not just clean non-privately, then run AIM? Because the guarantee is then about the wrong object. AIM's noise protects against changing one row of the cleaned table. Changing one person in the raw table can change many cleaned rows, through a bridging merge or a tipped majority repair. The missing-data paper already notes that preprocessing before DP synthesis is "privacy-expensive" when done honestly. The cheap version is not honest. Our audit will build neighbor pairs where the target record bridges two clusters or controls an FD-majority. It will then estimate how well an attacker can tell the two synthetic outputs apart. A measured distinguishing advantage above what $\epsilon$ allows settles the question.
Why not just bound contributions per person and use group privacy? This is the real threat. If duplicates per person are few and known, dividing $\epsilon$ by $k_{\max}$ may cost less than any cleaning. Two things weaken it. First, $k_{\max}$ is unknown without entity resolution, and the heavy tail of duplicates forces a large divisor. Second, conflicting and missing cells remain unrepaired and are learned as real population modes. Our controlled corruptions vary the duplicate distribution from light to heavy-tailed. If group privacy wins at light duplication, we will report the crossover point rather than claim a uniform win.
Why not just synthesize from the dirty table and clean the synthetic output? Post-processing preserves DP, but only row-level DP, so duplicated people remain under-protected. The generator has also already fit the errors. In addition, AIM's error bounds assume the released table matches its measured marginals, and deleting or rewriting tuples afterward breaks that assumption. We run this baseline anyway, since it is cheap. We report its constraint-violation rate and workload error next to its audited per-person $\epsilon$.
Why not just extend adaptive recourse from the missing-data paper? Its models drop or impute cells attribute by attribute. They have no notion of entities, so they cannot change the privacy unit. We reuse its central idea, that imputation should spend budget already allocated rather than a separate preprocessing budget, inside our repair step.
Proposed Experiments
We need ground-truth entities, so the core experiments use controlled corruption of Adult and Bank, the standard DP synthesis tables used by both AIM and the missing-data paper. Each true individual is duplicated a random number of times, with the number drawn from a light or a heavy-tailed distribution. Duplicates get typos and field-level conflicts. Missing cells are injected under missing-completely-at-random, missing-at-random and missing-not-at-random mechanisms, and we plant functional-dependency violations. Real dirty data comes from Hospital, which has known FD violations and a gold repair, and from the House relational set of 12K tuples used in the discrepancy-detection work. Evaluation on these uses whatever entity labels they provide.
Metrics fall into four groups:
- Synthesis quality: average error on workloads of 3-way marginals (AIM's evaluation style), and downstream classifier accuracy when training on synthetic data and testing on real held-out data.
- Constraint quality: the rate at which synthetic tuples violate the denial constraints.
- Cleaning quality: entity-resolution F1 and repair precision/recall before synthesis.
- Privacy: the empirical per-person $\epsilon$ lower bound from the distinguishing audit.
Privacy budgets span $\epsilon \in \{0.5, 1, 3, 10\}$, with five seeds.
Three checks are decisive. First, the audit must show that naive AIM and clean-then-AIM exceed their stated $\epsilon$ on bridging and duplicate-heavy targets, while our pipeline stays within its bound. If naive pipelines pass the audit, the motivating danger is smaller than argued. Second, at equal per-person $\epsilon$, our pipeline must beat the group-privacy baseline under heavy-tailed duplication, and we will locate the regime where it does not. Third, sweeping the degree cap $\Delta$ must trace a curve that trades cleaning accuracy against noise scale. Its optimum should sit at small $\Delta$. A large optimal $\Delta$ would mean stability is too expensive to be worth it.
References
- HoloClean: Holistic Data Repairs with Probabilistic Inference
- REPLACE: A Logical Framework for Combining Collective Entity Resolution and Repairing
- Rock: Cleaning Data with both ML and Logic Rules
- AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data
- Benchmarking Differentially Private Tabular Data Synthesis Algorithms
- Differentially Private Data Generation with Missing Data
- Parallel Discrepancy Detection and Incremental Detection