Structure Selection for Fairness-Constrained Differentially Private Data Synthesis
Naeim Ghahramanpour, Mostafa Milani · 2026
Read Structure Selection for Fairness-Constrained Differentially Private Data Synthesis by Naeim Ghahramanpour, Mostafa Milani (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-12112.txt.
Introduction
Ghahramanpour and Milani add fairness limits to private synthetic data. Standard tools copy every pattern in the source data, even false links between sensitive traits and outcomes. Their PrivCI method enforces set independence rules at the measurement step. A greedy spanning tree checks feasibility while it picks which marginals to privatize. A fitted model then rebuilds data that fits those noisy counts. On fairness benchmarks, PrivCI beat prior methods on fidelity and accuracy while honoring the rules.
Catalog record
| CREATOR | Naeim Ghahramanpour, Mostafa Milani |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40486 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.12112
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Structure Selection for Fairness-Constrained Differentially Private Data Synthesis Naeim Ghahramanpour, Mostafa Milani Abstract Differential privacy (DP) enables safe data release, with synthetic data generation emerging as a common approach in recent years. Yet standard synthesizers preserve all dependencies in the data, including spurious correlations between sensitive attributes and outcomes. In fairness-critical settings, this reproduces unwanted bias. A principled remedy is to enforce conditional independence (CI) constraints, which encode domain knowledge or legal requirements that outcomes be independent of sensitive attributes once admissible factors are accounted for. DP synthesis typically proceeds in two phases: (i) a measurement step that privatizes selected marginals, often structured via maximum spanning trees (MSTs), and (ii) a reconstruction step that fits a probabilistic model consistent with the noisy marginals. We propose PrivCI , which enforces CI during the measurement step via a CI-aware greedy MST algorithm that integrates feasibility checks into Kruskal’s construction under the exponential mechanism, improving accuracy over competing methods. Experiments on standard fairness benchmarks show that PrivCI achieves stronger fidelity and predictive accuracy than prior baselines while satisfying the specified CI constraints. I Introduction Differential Privacy (DP) [ 10 , 11 ] has emerged as the de facto standard for rigorous privacy guarantees in data analysis and machine learning. A prominent instantiation is DP synthetic data generation [ 15 , 12 , 25 , 23 ] , where one learns a noisy approximation of the data distribution under DP and samples artificial records from it, enabling broad downstream analysis from a single privacy-protected artifact. While DP synthetic data enables broad downstream analysis, it is designed to preserve the statistical structure of the original dataset—up to controlled noise. Consequently, synthetic data also inherits the biases present in the source data. Real-world datasets often encode historical inequities or sampling artifacts, which can give rise to spurious correlations —statistical dependencies that do not reflect true causal relationships in the domain [ 36 , 18 , 33 , 31 ] . In fairness-critical settings, these correlations may link protected attributes to outcomes in undesirable ways. For example, in hiring data, applicants from certain groups may have historically received fewer callbacks despite comparable qualifications [ 3 ] , creating an association between sensitive attributes and hiring outcomes that does not reflect admissible decision criteria. When DP synthesizers preserve such patterns, they can replicate unfair dependencies in the released synthetic data, undermining both fairness and the validity of downstream analyses. Importantly, DP provides guarantees about individual privacy—not about which dependencies should or should not be preserved. Consequently, a synthesizer that faithfully captures the data distribution may also preserve spurious or policy-prohibited correlations. A principled way to control which dependencies are retained is to encode domain or legal requirements as conditional independence (CI) constraints . A CI constraint X\perp Y\mid Z formalizes the requirement that outcomes Y be independent of sensitive attributes X once admissible factors Z are accounted for. In the hiring example, this can be expressed as \texttt{Gender}\!\perp\!\texttt{Outcome}\mid\texttt{Qualifications} , ensuring that decisions are driven by qualifications rather than gender. In this work, we study the problem of differentially private data synthesis under conditional independence (CI) constraints . Our goal is to enforce CI requirements within the DP synthesis pipeline, rather than applying post-hoc repair to already synthesized data. Integrating structural constraints directly into the private measurement process is crucial: DP mechanisms allocate privacy budget to estimate and preserve dependencies, and if some dependencies are policy-prohibited, preserving them and later correcting them can waste privacy budget and amplify distortion. Most DP synthesizers for structured tabular data follow a two-stage measurement–reconstruction paradigm [ 15 , 23 , 25 ] . In the measurement stage, the algorithm privately estimates a collection of low-dimensional statistics (e.g., marginals or dependency scores). In the reconstruction stage, it fits a joint distribution consistent with these noisy measurements and samples synthetic records. This modular decomposition enables efficient privacy accounting and scalability to moderate dimensions. Within this framework, MST [ 23 ] and PrivatePGM [ 25 ] form a widely used backbone. MST selects a dependency tree by privately ranking candidate edges using the exponential mechanism, and PrivatePGM reconstructs a graphical model from the selected marginals. However, standard MST-based pipelines optimize purely for dependency strength and do not account for structural constraints such as CI requirements. As a result, they may allocate privacy budget to dependencies that violate policy or fairness specifications. To formalize such structural constraints, we adopt a fairness-oriented partition of attributes that is standard in causal and fairness-aware modeling [ 29 , 37 , 33 ] . Let V denote the full set of attributes in the dataset. We divide V into four roles: protected attributes S (e.g., gender or race), outcome attributes O (e.g., hiring decision or credit risk), admissible attributes A (variables through which dependence between S and O is considered legitimate), and optionally inadmissible attributes I (remaining covariates), so that V=S\cup O\cup A\cup I . The distinction between admissible and inadmissible attributes captures a common policy intuition: some pathways from S to O may be acceptable because they operate through relevant qualifications (e.g., education, experience, or test scores), whereas other pathways reflect direct or proxy discrimination and should be eliminated. For instance, in hiring, Qualifications may be treated as admissible, while variables that act as proxies for protected status—such as ZipCode , Neighborhood , or prior Employer in settings where it encodes segregation effects—may be considered inadmissible mediators. Admissible variables therefore represent factors through which dependence is permitted, while inadmissible variables represent channels through which protected-to-outcome influence is not allowed. A fairness requirement is then expressed as a conditional independence (CI) constraint of the form O\perp S\mid A, which requires that once admissible factors are fixed, the outcome be statistically independent of the protected attributes. In graphical models, CI constraints correspond to separation properties [ 20 ] : O\perp S\mid A holds if A separates S and O in the graph. In a tree-structured dependency model, this reduces to a structural requirement: any path connecting a node in S to a node in O must pass through at least one node in A . Equivalently, in the graph induced by V\setminus A , there must be no path between S and O . We propose PrivCI , a DP synthesis framework that enforces CI constraints structurally during the measurement stage . PrivCI modifies the Kruskal-style maximum spanning tree construction in MST by treating the CI requirement as a feasibility constraint during edge selection. At each iteration, a candidate edge is considered admissible only if (i) it preserves acyclicity and (ii) its addition does not introduce an S – O path in the graph induced by V\setminus A . Equivalently, we require that A separates S and O in the learned tree. Edges that would violate this separation condition are excluded. Among the remaining feasible edges, selection proceeds privately via the exponential mechanism. The resulting algorithm is a greedy, CI-aware marginal selection procedure that retains the privacy accounting and composition properties of the underlying MST pipeline, while ensuring that the learned dependency structure satisfies the specified fairness constraint. Our approach emphasizes practical utility under DP budgets while structurally enforcing CI during marginal selection. We focus on empirical performance and fairness outcomes across