FairSHAP: Preprocessing for Fairness Through Attribution-Based Data Augmentation

1. Problem Statement

Machine learning models often perpetuate societal biases, particularly in high-stakes domains like healthcare, finance, and criminal justice. Existing fairness mitigation strategies generally fall into three categories: preprocessing, in-processing, and post-processing. However, current preprocessing methods suffer from two critical limitations:

1. Lack of Interpretability: They often modify data without transparently identifying which features are responsible for the bias, leading to "fairwashing" (deceptive explanations) or arbitrary data loss.
2. Focus on Group Fairness Only: Most methods optimize for group-level metrics (e.g., Demographic Parity) while neglecting individual fairness. This can lead to individual arbitrariness, where individuals with similar profiles receive different predictions based solely on sensitive attributes.

The paper argues that individual and group fairness are not contradictory but are manifestations of the same underlying principles. Therefore, a method that targets individual-level bias using interpretable mechanisms can simultaneously improve group-level fairness.

2. Methodology: FairSHAP

FairSHAP is a novel preprocessing framework that leverages Shapley values (from cooperative game theory) to identify and modify fairness-critical features in the training data. It operates as a model-agnostic, attribution-based data augmentation technique.

Core Workflow

The method follows a two-stage process (illustrated in Figure 1 of the paper):

1. Instance-Level Matching:

   • The dataset is split into privileged ($A=1$) and unprivileged ($A=0$) groups based on the sensitive attribute.
   • A nearest-neighbor matching (or optimal transport) procedure aligns instances between the two groups. Crucially, this matching enforces label consistency (e.g., positive instances in one group are matched only with positive instances in the other) to ensure fair comparison.

2. Attribution-Based Modification:

   • For each instance in the target group, the method computes Shapley values ($\phi_k$) to quantify the marginal contribution of each feature to the model's prediction, specifically regarding the Discriminative Risk (DR).
   • Discriminative Risk (DR) is defined as the absolute difference in model predictions for an individual if their sensitive attribute were flipped: $L_{DR} = |f(\check{x}, A=0) - f(\check{x}, A=1)|$.
   • Features with Shapley values exceeding a threshold $T$ are identified as fairness-critical.
   • These critical feature values are replaced with the corresponding values from the matched reference instance in the other sensitive group.
   • This process is applied bidirectionally (targeting both groups) to create an augmented, fairness-improved dataset ($D_{new}$).

Theoretical Foundation

The paper provides rigorous theoretical guarantees:

• Theorem 3.1 (Instance-wise DR Reduction): Replacing fairness-critical features reduces the individual Discriminative Risk by at least the sum of their Shapley values (minus an interaction residual term).
• Proposition 3.2: Under local matching (where the distance between matched instances $\epsilon$ is small), the interaction residual term is bounded by a second-order term ($O(\epsilon^2)$), ensuring the Shapley attribution dominates the reduction.
• Theorem 3.3 & 3.4: A uniform reduction in individual DR mathematically bounds the reduction in group-level Demographic Parity (DP), proving that improving individual fairness inherently improves group fairness.

3. Key Contributions

1. Novel Framework: Introduction of FairSHAP, the first preprocessing method that explicitly combines Shapley value attribution with instance-level matching to target individual fairness.
2. Interpretability & Transparency: Unlike "black-box" preprocessing, FairSHAP identifies exactly which features cause bias, providing actionable insights into the sources of unfairness.
3. Minimal Data Perturbation: The method selectively modifies only features with high Shapley contributions, preserving data fidelity (measured by Wasserstein distance) far better than methods like Correlation Remover (which modifies >95% of data).
4. Dual Improvement: It achieves simultaneous improvements in individual fairness (DR) and group fairness (DP, Equality of Opportunity) without requiring test-set adjustments or significant accuracy loss.

4. Experimental Results

The authors evaluated FairSHAP on five tabular datasets: German Credit, COMPAS, Adult, Census Income KDD, and Default Credit.

• Performance Metrics:

  • DR Reduction: FairSHAP reduced Discriminative Risk by up to 80% (German Credit) and 40% (COMPAS) compared to baselines.
  • Group Fairness: It consistently improved Demographic Parity (DP) and Equality of Opportunity (EO) across all datasets.
  • Accuracy: In several cases (e.g., COMPAS, Census Income), accuracy increased after applying FairSHAP. In others, the drop was negligible.
  • Data Fidelity: FairSHAP maintained the highest data fidelity (lowest Wasserstein distance) among all methods, modifying significantly fewer data points than baselines like DIR or CR.

• Comparative Analysis:

  • vs. Remove Sensitive Attribute (RSA): RSA fails to address proxy bias; FairSHAP outperforms it.
  • vs. Disparate Impact Remover (DIR) & Correlation Remover (CR): While CR reduces DR, it requires massive data modification (>95%) and degrades DP/EO. FairSHAP achieves better fairness metrics with minimal edits and does not require transforming the test set.

• Ablation Studies:

  • Removing the Shapley component (random replacement) or the matching component resulted in significantly lower fairness improvements, confirming that both attribution and matching are essential.

5. Significance

• Bridging the Gap: FairSHAP successfully bridges the gap between interpretability and fairness, moving beyond "fairwashing" by providing a transparent rationale for data modifications.
• Practical Deployment: As a preprocessing technique, it is model-agnostic and integrates seamlessly into existing ML pipelines. It does not require retraining the model architecture or modifying the inference process.
• Theoretical Rigor: The paper moves beyond empirical observation by providing mathematical proofs that reducing individual bias via Shapley values guarantees a reduction in group-level statistical disparities.
• Future Impact: By demonstrating that individual fairness is a principled path to group fairness, FairSHAP offers a new paradigm for developing accountable and equitable AI systems in high-stakes domains.

Code Availability: The implementation is open-source at https://github.com/ZhuMuMu0216/FairSHAP.