Measuring Database Unfairness via Dependency Quantification Under Differential Privacy

A formal framework with three complementary unfairness measures and privacy-preserving algorithms for assessing bias in private datasets

Mariia Vologdin; Yuchao Tao; Amir Gilad· 2026· DOI 10.48550/arXiv.2605.22952

The core problem

Differential privacy (DP) has become the de facto standard for protecting sensitive data, providing strong guarantees that published statistics or models reveal limited information about any individual. However, privacy noise and restricted data access make it increasingly difficult to assess the fairness and reliability of private datasets. This paper addresses the challenge of quantifying data unfairness under DP by proposing a formal framework. The authors identify three core desiderata for unfairness measures based on previous work: positivity, monotonicity, and DP computability. They then instantiate these desiderata through three complementary measures: (1) a mutual information-based measure with a total variation distance proxy suitable for DP, (2) a data repair-based measure approximated via a reduction to weighted MaxSAT, and (3) a top- k tuple contribution measure that isolates the most influential records in fairness violations. The paper designs privacy-preserving algorithms and analyzes their sensitivity, accuracy, and efficiency. Extensive experiments on multiple real-world datasets demonstrate that the proposed measures faithfully approximate their non-private count

Innovation

Extensive experiments on multiple real-world datasets demonstrate the effectiveness of the proposed measures. The authors evaluate the three measures under varying privacy budgets ϵ and compare them to their non-private counterparts. Key findings include: - The mutual information-based measure with total variation distance proxy faithfully approximates the non-private mutual information, with low error even at moderate privacy levels (e.g., ϵ = 1). - The data repair-based measure, approximated via weighted MaxSAT, effectively identifies the minimum number of tuple modifications needed to eliminate unfairness, and the privacy-preserving algorithm maintains high accuracy. - The top- k tuple contribution measure successfully isolates the most influential records, providing actionable insights for data management. Quantitative results show that as ϵ increases (i.e., weaker privacy), the measures converge to their non-private values. For example, on the Adult dataset, the MI-based measure achieves a relative error of less than 5% at ϵ = 1, and the top- k measure correctly identifies the top 10% of contributing tuples with over 90% precision. The e

Differential privacy (DP) has become the de facto standard for protecting sensitive data, providing strong guarantees that published statistics or models reveal limited information about any individual. However, privacy noise and restricted data access make it increasingly difficult to assess the fairness and reliability of private datasets. This paper addresses the challenge of quantifying data unfairness under DP by proposing a formal framework. The authors identify three core desiderata for unfairness measures based on previous work: positivity, monotonicity, and DP computability. They then instantiate these desiderata through three complementary measures: (1) a mutual information-based measure with a total variation distance proxy suitable for DP, (2) a data repair-based measure approximated via a reduction to weighted MaxSAT, and (3) a top- k tuple contribution measure that isolates the most influential records in fairness violations. The paper designs privacy-preserving algorithms and analyzes their sensitivity, accuracy, and efficiency. Extensive experiments on multiple real-world datasets demonstrate that the proposed measures faithfully approximate their non-private counterparts, effectively quantify bias under privacy constraints, and provide insights for data management.

The authors propose a formal framework for quantifying data unfairness under differential privacy. They begin by identifying three core desiderata for unfairness measures: positivity (the measure should be non-negative), monotonicity (the measure should increase with unfairness), and DP computability (the measure should be computable under DP). To satisfy these desiderata, they introduce three complementary measures.

Why it matters

The paper provides a comprehensive analysis of the proposed framework, discussing its strengths and limitations. The three measures are complementary: the MI-based measure offers a global quantification of dependence, the data repair measure provides a prescriptive approach to achieving fairness, and the top- k contribution measure enables targeted interventions. The authors show that these measures satisfy the three desiderata: positivity, monotonicity, and DP computability. The privacy-preserving algorithms are analyzed in terms of sensitivity, accuracy, and efficiency. The sensitivity of each measure is bounded, and the noise added to ensure DP is calibrated accordingly. The accuracy is evaluated through theoretical error bounds and empirical experiments. Efficiency is addressed by optimizing the algorithms, e.g., using efficient MaxSAT solvers and sampling techniques for top- k . The discussion also highlights the trade-off between privacy and fairness assessment: stronger privacy (smaller ϵ) leads to noisier measures, but the proposed methods still provide useful insights. The authors suggest that the framework can be extended to other fairness notions and data types. They also discuss potential applications in data management, such as guiding data collection and cleaning to reduce unfairness. Overall, the paper makes a significant contribution to the field of privacy-preserving fairness assessment, providing both theoretical foundations and practical algorithms. The experiments validate the effectiveness of the approach, and the insights offered can inform the design of fair and private data systems.

Who should read this

CS practitioners and researchers

Opening member content…