DeepGemini: Verifying Dependency Fairness for Deep Neural Network

Xuan Xie, Fuyuan Zhang, Xinwen Hu, Lei MaAAAI 2023 · DOI

Abstract

DeepGemini is a formal verification framework that transforms the challenge of "dependency fairness" into a standard "safety property" problem. By utilizing a twin-network construction and an iterative refinement algorithm, it formally proves whether a model is biased and calculates a quantitative "fairness score" representing the percentage of the input space guaranteed to be fair. Evaluated on standard benchmarks, DeepGemini demonstrates superior scalability and precision compared to existing state-of-the-art methods.

Introduction

As Deep Neural Networks (DNNs) are increasingly deployed in high-stakes domains such as credit scoring and recidivism prediction, ensuring algorithmic fairness is critical. This paper focuses on dependency fairness: the requirement that a model's output remains invariant when only sensitive features (e.g., race, gender) are modified while keeping all other features constant.

Existing approaches generally fall into two categories: testing and certification. Testing methods can identify biased examples but offer no guarantees for the remaining input space. Certification methods, often based on abstract interpretation, provide guarantees but are frequently too conservative and fail to provide concrete counterexamples. DeepGemini bridges this gap by providing both concrete discriminatory samples and a rigorous lower bound on the fairness of the entire input region.

Methodology

1. Reduction to Safety Verification

The primary innovation of DeepGemini is the reduction of dependency fairness to a safety verification problem. The authors propose a twin-network construction ($N \oplus N'$), where the original model is paired with an identical copy.

Twin-network construction for dependency fairness verification.

In this setup, non-sensitive features are shared between both networks, while sensitive features are allowed to vary independently. If the outputs of $N$ and $N'$ differ for any valid input pair, a violation of dependency fairness is detected. This formulation allows the use of off-the-shelf SMT solvers, such as Marabou, to search for discriminatory samples.

2. Counterexample Guided Fairness Analysis (CEGFA)

To quantify fairness, DeepGemini employs an iterative refinement process called Counterexample Guided Fairness Analysis (CEGFA).

The DeepGemini iterative verification and refinement workflow.

The algorithm begins by considering the entire input space and querying the verifier to determine if the region is fair. If the verifier confirms fairness, the volume of that region is added to the total fairness score. If a discriminatory sample (counterexample) is found, the algorithm uses a refinement heuristic to split the region into smaller sub-regions, which are then processed recursively. The authors evaluated several refinement strategies, including Random, Saliency Map (SM), and Important Neuron (IN) based splitting.

Experimental Evaluation

The framework was evaluated using the UCI German Credit and ProPublica COMPAS datasets. DeepGemini successfully distinguished between "fair" and "biased" versions of models trained on these benchmarks.

Key Results

  • Quantitative Fairness: Unlike binary "fair/unfair" tools, DeepGemini provides a percentage-based fairness score. This allows for a more nuanced understanding of model behavior in industrial settings.
  • Scalability: DeepGemini significantly outperformed previous state-of-the-art tools like Libra. For instance, on a network with 150 neurons where Libra timed out, DeepGemini successfully provided a fairness score and identified biased regions.
  • Efficiency: Bias queries for smaller models were resolved in under a second. The tool consistently produced tighter fairness bounds than abstract interpretation methods.
  • Refinement Heuristics: Interestingly, the simple Random refinement strategy often performed as well as or better than complex gradient-based heuristics, suggesting that broad exploration is highly effective for fairness verification.

Conclusion and Future Work

DeepGemini provides a robust, scalable framework for the formal verification of dependency fairness. By providing a quantitative fairness score and concrete discriminatory samples, it offers a practical tool for developers to audit high-stakes DNNs. Future work may explore using the identified discriminatory samples for automated model retraining to mitigate detected biases.

Summary updated

BibTeX
@inproceedings{xie2023deepgemini,
  author = {Xuan Xie and Fuyuan Zhang and Xinwen Hu and Lei Ma},
  title = {{DeepGemini: Verifying Dependency Fairness for Deep Neural Network}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i12.26779},
}
Figure