Uncovering Discrimination Clusters: Quantifying and Explaining Systematic Fairness Violations

1. Problem Statement

Current fairness verification and testing methods for Deep Neural Networks (DNNs) primarily focus on Individual Fairness (IF). IF posits that similar individuals (differing only in protected attributes like race or gender) should receive similar outcomes. Existing tools typically search for 2-discriminant instances (pairs of inputs where one is treated favorably and the other unfavorably).

The authors argue that this binary, pairwise approach has significant limitations:

• Misses Systematic Patterns: It fails to capture broader, clustered patterns of discrimination where a group of similar individuals receives a wide variety of arbitrary outcomes based solely on protected attributes.
• Lack of Severity Quantification: Finding a single counterexample does not quantify the degree of arbitrariness or the scale of the bias.
• Inadequate Explanations: Existing explanation methods (e.g., LIME, differential debugging) focus on single instances or global approximations, failing to explain the root causes of clusters of discriminatory behavior.

The paper introduces the concept of Discrimination Clustering, aiming to identify regions in the input space where small perturbations in protected attributes lead to $k$-significantly distinct clusters of outcomes ($2 \le k \le K$), revealing high levels of arbitrariness in decision-making.

2. Methodology: HYFAIR Framework

The authors propose HYFAIR, a hybrid framework that combines formal symbolic analysis with randomized search to detect, quantify, and explain discrimination clusters. The workflow consists of three main phases:

A. Formal Verification (Certifying 2-Fairness)

• Goal: To either mathematically prove the absence of individual discrimination or find a "seed" counterexample (a 2-discriminant instance).
• Technique: The DNN is encoded as a Mixed-Integer Linear Program (MILP).
• Mechanism: Two copies of the DNN are analyzed simultaneously. The solver checks if there exist inputs with identical non-protected features but different protected attributes that yield outputs differing by more than a threshold $\epsilon$ (set to 0.05).
• Advantage: Unlike SMT-based approaches (e.g., FAIRIFY), the MILP formulation is shown to be more efficient at finding diverse counterexamples, particularly near the boundaries of safe and unsafe regions.

B. Randomized Search (Quantifying $k$-Discrimination)

• Goal: Starting from a seed counterexample, characterize the maximum extent of discrimination ($k$) in the local neighborhood.
• Technique: The system performs a local search to find a set of $K$ inputs (sharing non-protected features, varying protected features) that maximize the number of distinct output clusters.
• Algorithms:
  • Random Walk (RW): Baseline random exploration.
  • Simulated Annealing (SA): Uses a probabilistic acceptance criterion to escape local optima and find higher $k$ values.
  • SA + KNN: A hybrid approach incorporating K-Nearest Neighbors to guide the search toward dense regions of discrimination.
• Outcome: The search identifies the maximum $k$ (the number of distinct outcome clusters) achievable within a specific input neighborhood, quantifying the severity of the bias.

C. Debugging and Explanation

• Goal: Explain why the model exhibits $k$-discrimination in specific regions.
• Technique:
  1. Local Perturbation: Generate a neighborhood of samples around the high-$k$ instances.
  2. Labeling: Classify samples into "High-$k$" (highly discriminatory) and "Low-$k$" (benign) based on a percentile threshold.
  3. Decision Tree Learning: Train a decision tree on these labeled samples to synthesize logical predicates (rules) over non-protected attributes.
  4. Validation: Verify that negating these rules reduces the $k$-discrimination, ensuring the rules are causal drivers of the bias.
• Output: Interpretable, decision-tree-style artifacts that define hyper-rectangular regions in the input space where the model behaves arbitrarily.

3. Key Contributions

1. Novel Fairness Notion ($k$-Discriminant): Generalizes individual fairness to quantify the severity of bias by measuring the number of distinct outcome clusters ($k$) generated by protected attribute variations.
2. Hybrid Framework (HYFAIR): Integrates MILP-based formal verification (for certification and seeding) with Simulated Annealing-based randomized search (for quantification) to overcome the scalability limits of pure formal methods and the incompleteness of pure testing.
3. Explainable AI for Clusters: A novel method using decision trees to explain the root causes of clusters of discriminatory instances, rather than single points.
4. Mitigation Strategy: Demonstrates how the generated logical rules can be used as "guardrails" to constrain model behavior or guide retraining to reduce discrimination.

4. Experimental Results

The authors evaluated HYFAIR on 20 DNN benchmarks (using Adult Census and Bank Marketing datasets) against state-of-the-art baselines (FAIRIFY for verification, LIME for explanation).

• RQ1 (Verification Efficiency): HYFAIR (MILP) significantly outperformed FAIRIFY (SMT).
  • Found 85% more individual discrimination (ID) instances within the same timeout.
  • Found the first ID instance 90% faster.
  • Generated counterexamples from diverse regions of the input space, whereas SMT often produced clustered, similar counterexamples.
• RQ2 (Search Performance): Simulated Annealing (SA) was the most effective search strategy.
  • Identified maximum $k$-discrimination in 94% of cases compared to other strategies.
  • Discovered the first max-$k$ instance faster than Random Walk or SA+KNN.
• RQ3 (Explanation Quality): HYFAIR's explanations were superior to LIME.
  • Robustness: HYFAIR explanations showed higher robustness (lower change in $k$ when features were perturbed) in 78% of cases.
  • Coverage: HYFAIR covered a significantly larger volume of the input space (generality) compared to LIME's point-based explanations.
  • Succinctness: Provided simpler, more interpretable rules.
• RQ4 (Mitigation):
  • Applying the derived decision tree rules as guardrails reduced the success rate of reproducing fairness bugs by ~50% (e.g., from 87.7% to 36.3% on the AC2 benchmark).
  • Simple retraining alone often failed to reduce $k$-discrimination and sometimes increased it, highlighting the need for targeted rule-based interventions.

5. Significance and Conclusion

This paper shifts the paradigm of fairness analysis from detecting isolated "bugs" (pairwise violations) to uncovering systematic patterns of arbitrariness.

• Theoretical Impact: It provides a rigorous mathematical foundation for $k$-discrimination, acknowledging that fairness is rarely binary and that high-stakes decisions often exhibit clustered, arbitrary outcomes.
• Practical Impact: HYFAIR offers a practical tool for developers to not only find fairness violations but to understand the conditions under which they occur and how to fix them. The ability to generate interpretable rules allows for immediate deployment of guardrails or targeted data augmentation.
• Limitations: The current approach assumes a finite set of protected groups and does not yet handle intersectional fairness (combinations of multiple protected attributes) natively, though it can be applied iteratively. It also relies on rule-of-thumb constraints to ensure counterfactual realism.

In summary, HYFAIR represents a significant advancement in algorithmic fairness, moving beyond simple verification to provide a comprehensive toolkit for quantifying, explaining, and mitigating complex, clustered discrimination in deep learning systems.