Perfectly Parallel Fairness Certification of Neural Networks

Caterina Urban, Maria Christakis, Valentin Wüstholz, Fuyuan ZhangarXiv 2019 · arXiv

TL;DR

Researchers have developed LIBRA, a tool that uses perfectly parallel static analysis to formally certify the "causal fairness" of neural networks. Unlike previous methods that were limited to tiny toy models, this approach scales to larger networks and provides definite guarantees—or a precise quantification of bias if certification fails.

What Problem Does This Paper Address?

As machine learning (ML) models increasingly automate life-altering decisions in healthcare, criminal justice, and finance, the risk of these models inheriting or amplifying societal biases grows. A model might appear fair on the surface but rely on "latent variables"—like using a ZIP code as a proxy for race.

While empirical testing can detect some bias, it cannot prove a model is truly fair across its entire input space. Formal verification aims to provide these "fairness proofs," but existing techniques have struggled with scalability, often failing to analyze networks with more than a few neurons. The authors tackle the challenge of creating a scalable, formal framework for certifying causal fairness: the property that a model's output remains unchanged even if sensitive input features (like gender or race) are varied.

Methods

The authors propose a framework based on abstract interpretation, a theory for approximating the behavior of computer programs. Their approach uses a two-stage "divide and conquer" strategy:

  1. Forward Pre-analysis (Partitioning): The tool uses a "cheap" abstract domain (like Boxes or DeepPoly) to split the massive input space into smaller, independent partitions. It groups these partitions based on abstract activation patterns—essentially identifying which neurons (specifically ReLUs) are "on" or "off" for a given region.
  2. Backward Analysis (Certification): For each partition, LIBRA performs a highly precise backward analysis using disjunctive polyhedra. This step determines exactly which input regions lead to which classifications. Because each partition is independent, this step is "perfectly parallel," meaning it can be distributed across as many CPU cores as available.

The system is designed to be sound (it never falsely claims a biased model is fair) and, in practice, exact for networks using piecewise-linear activations like ReLUs. It also features a "pay-as-you-go" configuration, allowing users to set a budget for how much of the input space they want to analyze based on available time and compute power.

Fig. 1. Small, constructed example of trained feed-forward neural network for credit approval.

Datasets

The researchers evaluated LIBRA using several popular datasets frequently cited in fairness literature:

  • German Credit Data: Used to classify creditworthiness.
  • ProPublica’s COMPAS Data: Used to predict recidivism risk.
  • Adult Census Data: Used to predict yearly income.
  • Japanese Credit Screening Data: Another credit-related classification task.

They pre-processed these datasets to create "fair" versions and "biased" versions (where bias was intentionally injected) to test the tool's detection capabilities.

Key Insights and Ideas

  • Causal Fairness as a Global Property: Unlike "local robustness" (which checks if a model is stable around a single point), causal fairness must be evaluated across the entire input space.
  • The Sparsity of Activation Patterns: A key "aha" moment is the observation that while a network could theoretically have $2^n$ activation patterns (where $n$ is the number of neurons), only a tiny fraction are actually reachable. By focusing on these reachable "abstract" patterns, LIBRA avoids an exponential explosion in complexity.
  • Configurable Scalability: The introduction of bounds $U$ (maximum unknown neurons per partition) and $L$ (minimum partition size) allows the tool to adapt to different hardware and time constraints, making formal verification more practical for real-world engineering workflows.

Key Results

  • Bias Detection: LIBRA successfully detected seeded biases in the German Credit and COMPAS models, often finding that biased models were three times more likely to exhibit discriminatory behavior than their "fair" counterparts.
  • Significant Scaling: The tool successfully analyzed networks with up to 32 hidden layers and 40 nodes per layer (over 1,200 neurons total). This represents a massive leap over prior formal methods that were limited to just two hidden neurons.
  • Effective Parallelization: The researchers demonstrated that the analysis scales efficiently across multiple CPUs. For example, using 12 CPUs significantly reduced analysis time compared to 4 CPUs, particularly for more precise abstract domains.
  • Precision vs. Speed: They found that using more sophisticated domains like symbolic or deeppoly for the forward pass often reduced overall time because they could prove fairness for larger regions more quickly, avoiding expensive backward passes.

Limitations and Future Work

  • Activation Functions: While the analysis is exact for piecewise-linear functions (ReLU, Leaky ReLU), it becomes an over-approximation (losing exactness) for smooth functions like Sigmoid or Tanh.
  • Input Space Complexity: For very large input spaces or extremely complex models, the tool may still time out or exclude regions from analysis if the budget is too low.
  • Future Directions: The authors plan to automate parameter tuning (like the bound $U$) and explore "repairing" networks by using the tool's output to identify and eliminate specific biased regions. They also aim to integrate probabilistic guarantees for regions that cannot be fully certified.

Summary updated

Abstract

Recently, there is growing concern that machine-learning models, which currently assist or even automate decision making, reproduce, and in the worst case reinforce, bias of the training data. The development of tools and techniques for certifying fairness of these models or describing their biased behavior is, therefore, critical. In this paper, we propose a perfectly parallel static analysis for certifying causal fairness of feed-forward neural networks used for classification of tabular data. When certification succeeds, our approach provides definite guarantees, otherwise, it describes and quantifies the biased behavior. We design the analysis to be sound, in practice also exact, and configurable in terms of scalability and precision, thereby enabling pay-as-you-go certification. We implement our approach in an open-source tool and demonstrate its effectiveness on models trained with popular datasets.
BibTeX
@misc{urban2019perfectly,
  author = {Caterina Urban and Maria Christakis and Valentin Wüstholz and Fuyuan Zhang},
  title = {{Perfectly Parallel Fairness Certification of Neural Networks}},
  year = {2019},
  eprint = {1912.02499},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1912.02499},
}
Figure