# Algorithmic Fairness Verification with Graphical Models

arXiv: https://arxiv.org/abs/2109.09447 · HTML: https://mlsanity.com/paper/2109.09447/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 46 references that are in the map.
- First posted on arXiv 20 Sep 2021.

## Builds on (most cited first, 13 of 13)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Towards A Rigorous Science of Interpretable Machine Learning](https://mlsanity.com/paper/1702.08608/) (2017)
- [Counterfactual Fairness](https://mlsanity.com/paper/1703.06856/) (2017)
- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [On Fairness and Calibration](https://mlsanity.com/paper/1709.02012/) (2017)
- [AI Fairness 360: An Extensible Toolkit for Detecting, Understanding, and Mitigating Unwanted Algorithmic Bias](https://mlsanity.com/paper/1810.01943/) (2018)
- [Fair Inference On Outcomes](https://mlsanity.com/paper/1705.10378/) (2017)
- [Poisoning Attacks on Algorithmic Fairness](https://mlsanity.com/paper/2004.07401/) (2020)
- [Verifying Individual Fairness in Machine Learning Models](https://mlsanity.com/paper/2006.11737/) (2020)
- [On the relation between accuracy and fairness in binary classification](https://mlsanity.com/paper/1505.05723/) (2015)
- [Probabilistic Verification of Fairness Properties via Concentration](https://mlsanity.com/paper/1812.02573/) (2018)
- [Justicia: A Stochastic SAT Approach to Formally Verify Fairness](https://mlsanity.com/paper/2009.06516/) (2020)

## Built on by (most cited first, 16 of 16)

- [Monitoring Algorithmic Fairness](https://mlsanity.com/paper/2305.15979/) (2023)
- [How Biased are Your Features?: Computing Fairness Influence Functions with Global Sensitivity Analysis](https://mlsanity.com/paper/2206.00667/) (2022)
- [Monitoring Algorithmic Fairness under Partial Observations](https://mlsanity.com/paper/2308.00341/) (2023)
- [Active Fourier Auditor for Estimating Distributional Properties of ML Models](https://mlsanity.com/paper/2410.08111/) (2024)
- [Robust ML Auditing using Prior Knowledge](https://mlsanity.com/paper/2505.04796/) (2025)
- [Certifying Fairness of Probabilistic Circuits](https://mlsanity.com/paper/2212.02474/) (2022)
- [Towards Regulatable AI Systems: Technical Gaps and Policy Opportunities](https://mlsanity.com/paper/2306.12609/) (2023)
- [An Information-Flow Perspective on Algorithmic Fairness](https://mlsanity.com/paper/2312.10128/) (2023)
- [Abstract Interpretation-Based Feature Importance for SVMs](https://mlsanity.com/paper/2210.12456/) (2022)
- [Sublinear Algorithms for Wasserstein and Total Variation Distances: Applications to Fairness and Privacy Auditing](https://mlsanity.com/paper/2503.07775/) (2025)
- [Language Models That Walk the Talk: A Framework for Formal Fairness Certificates](https://mlsanity.com/paper/2505.12767/) (2025)
- [Monitoring of Static Fairness](https://mlsanity.com/paper/2507.03048/) (2025)
- [Algorithmic Fairness: A Runtime Perspective](https://mlsanity.com/paper/2507.20711/) (2025)
- [The Fair Game: Auditing & Debiasing AI Algorithms Over Time](https://mlsanity.com/paper/2508.06443/) (2025)
- [Wasserstein projection distance for fairness testing of regression models](https://mlsanity.com/paper/2510.04114/) (2025)
- [Quantifying Sensitivity for Tree Ensembles: A symbolic and compositional approach](https://mlsanity.com/paper/2605.13830/) (2026)

## Abstract (arXiv)

In recent years, machine learning (ML) algorithms have been deployed in safety-critical and high-stake decision-making, where the fairness of algorithms is of paramount importance. Fairness in ML centers on detecting bias towards certain demographic populations induced by an ML classifier and proposes algorithmic solutions to mitigate the bias with respect to different fairness definitions. To this end, several fairness verifiers have been proposed that compute the bias in the prediction of an ML classifier--essentially beyond a finite dataset--given the probability distribution of input features. In the context of verifying linear classifiers, existing fairness verifiers are limited by accuracy due to imprecise modeling of correlations among features and scalability due to restrictive formulations of the classifiers as SSAT/SMT formulas or by sampling. In this paper, we propose an efficient fairness verifier, called FVGM, that encodes the correlations among features as a Bayesian network. In contrast to existing verifiers, FVGM proposes a stochastic subset-sum based approach for verifying linear classifiers. Experimentally, we show that FVGM leads to an accurate and scalable assessment for more diverse families of fairness-enhancing algorithms, fairness attacks, and group/causal fairness metrics than the state-of-the-art fairness verifiers. We also demonstrate that FVGM facilitates the computation of fairness influence functions as a stepping stone to detect the source of bias induced by subsets of features.