# Certifying the Fairness of KNN in the Presence of Dataset Bias

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 50 references that are in the map.
- First posted on arXiv 17 Jul 2023.

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

- [Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embeddings](https://mlsanity.com/paper/1607.06520/) (2016)
- [Certified Robustness to Label-Flipping Attacks via Randomized Smoothing](https://mlsanity.com/paper/2002.03018/) (2020)
- [Learning Certified Individually Fair Representations](https://mlsanity.com/paper/2002.10312/) (2020)
- [Certified Robustness of Nearest Neighbors against Data Poisoning and Backdoor Attacks](https://mlsanity.com/paper/2012.03765/) (2020)
- [Probabilistic Verification of Fairness Properties via Concentration](https://mlsanity.com/paper/1812.02573/) (2018)
- [ReluDiff: Differential Verification of Deep Neural Networks](https://mlsanity.com/paper/2001.03662/) (2020)
- [NeuroDiff: Scalable Differential Verification of Neural Networks using Fine-Grained Approximation](https://mlsanity.com/paper/2009.09943/) (2020)
- [Certifying Robustness to Programmable Data Bias in Decision Trees](https://mlsanity.com/paper/2110.04363/) (2021)
- [DiffRNN: Differential Verification of Recurrent Neural Networks](https://mlsanity.com/paper/2007.10135/) (2020)
- [Mitigating Power Side Channels during Compilation](https://mlsanity.com/paper/1902.09099/) (2019)
- [Data-Driven Synthesis of Provably Sound Side Channel Analyses](https://mlsanity.com/paper/2102.06753/) (2021)
- [Modular Verification of Interrupt-Driven Software](https://mlsanity.com/paper/1709.10078/) (2017)
- [Certifying Data-Bias Robustness in Linear Regression](https://mlsanity.com/paper/2206.03575/) (2022)
- [Flow-Sensitive Composition of Thread-Modular Abstract Interpretation](https://mlsanity.com/paper/1709.10116/) (2017)
- [Eliminating Timing Side-Channel Leaks using Program Repair](https://mlsanity.com/paper/1806.02444/) (2018)
- [Abstract Interpretation under Speculative Execution](https://mlsanity.com/paper/1904.11170/) (2019)
- [Thread-Modular Static Analysis for Relaxed Memory Models](https://mlsanity.com/paper/1709.10077/) (2017)
- [Adversarial Symbolic Execution for Detecting Concurrency-Related Cache Timing Leaks](https://mlsanity.com/paper/1807.03280/) (2018)
- [Canonical Representations of k-Safety Hyperproperties](https://mlsanity.com/paper/2012.14586/) (2020)

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

- [FairQuant: Certifying and Quantifying Fairness of Deep Neural Networks](https://mlsanity.com/paper/2409.03220/) (2024)
- [FairSense: Long-Term Fairness Analysis of ML-Enabled Systems](https://mlsanity.com/paper/2501.01665/) (2025)
- [Correct-By-Construction: Certified Individual Fairness through Neural Network Training](https://mlsanity.com/paper/2508.15642/) (2025)
- [Uncovering Discrimination Clusters: Quantifying and Explaining Systematic Fairness Violations](https://mlsanity.com/paper/2512.23769/) (2025)
- [Analyzing Fairness of Neural Network Prediction via Counterfactual Dataset Generation](https://mlsanity.com/paper/2602.10457/) (2026)
- [Energy Shields for Fairness](https://mlsanity.com/paper/2605.24926/) (2026)
- [Fairness Invariants: A Relational Approach to Explaining and Mitigating Fairness Bugs](https://mlsanity.com/paper/2608.26209/) (2026)

## Abstract (arXiv)

We propose a method for certifying the fairness of the classification result of a widely used supervised learning algorithm, the k-nearest neighbors (KNN), under the assumption that the training data may have historical bias caused by systematic mislabeling of samples from a protected minority group. To the best of our knowledge, this is the first certification method for KNN based on three variants of the fairness definition: individual fairness, ε-fairness, and label-flipping fairness. We first define the fairness certification problem for KNN and then propose sound approximations of the complex arithmetic computations used in the state-of-the-art KNN algorithm. This is meant to lift the computation results from the concrete domain to an abstract domain, to reduce the computational cost. We show effectiveness of this abstract interpretation based technique through experimental evaluation on six datasets widely used in the fairness research literature. We also show that the method is accurate enough to obtain fairness certifications for a large number of test inputs, despite the presence of historical bias in the datasets.