🤖 machine learning

A Geometric Theory of Robust Fairness Audits

This paper introduces a geometric framework to analyze and quantify the robustness of neighborhood-based fairness audits against feature perturbations, establishing conditions for stability and proposing a new metric called "audit volatility" to measure their sensitivity.

Original authors: Binita Maity

Published 2026-08-26

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Binita Maity

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the modern world, algorithms increasingly make decisions that shape human lives, from approving loans and diagnosing illnesses to determining parole eligibility. As these systems grow more powerful, society has developed a critical need to ensure they treat people fairly. One major approach to checking for fairness focuses on the idea that similar individuals should receive similar outcomes. To test this, auditors often look at a person's data and compare their result to the results of their closest neighbors in the data set. If two people are nearly identical in their characteristics but receive vastly different scores, the system is flagged as potentially unfair. This method, known as a neighborhood-based audit, has become a standard tool for evaluating machine learning models because it is flexible and can spot localized injustices that broad statistics might miss.

However, a new concern has emerged regarding the reliability of these audits themselves. The process of finding a person's "neighbors" depends on the precise position of data points in a mathematical space. In the real world, data is rarely perfect; it contains small errors, missing values, or slight variations caused by how information was recorded or cleaned. These tiny shifts can nudge a person just enough to change who their nearest neighbors are. If the neighbors change, the fairness score changes, even if the underlying model's prediction for that person remains exactly the same. This raises a troubling question: is a finding of unfairness a genuine flaw in the system, or is it merely an artifact of a shaky measurement process?

Researchers at the Indian Institute of Technology, Gandhinagar, have developed a new way to understand this problem. They treated the auditing process not just as a statistical check, but as a geometric one, mapping out exactly how small changes in data affect the stability of these neighbor groups. Their work establishes that the stability of a fairness audit depends entirely on how clearly separated a person's neighbors are from everyone else in the data set. They found that if a person's neighbors are distinctly closer to them than any other non-neighbors, the audit result will remain steady even if the data is slightly disturbed. But if the neighbors are crowded together with the rest of the population, even a tiny nudge can swap them out, causing the fairness score to swing wildly.

The team introduced a concept they call "audit volatility" to measure how much a fairness score is expected to fluctuate when the data is subjected to repeated, small disturbances. By testing their theory on real-world data sets involving income, bank marketing, and criminal justice records, they confirmed that the geometry of the data is the primary driver of stability. In data sets where individuals are clearly grouped with their true peers, the audits remained robust and consistent. In contrast, data sets where individuals were more mixed together showed high volatility, meaning the fairness verdicts were highly sensitive to minor data shifts. The researchers demonstrated that the choice of how to average the results also matters; using methods that are less sensitive to extreme values can further reduce this instability.

Crucially, the study shows that the unpredictability of fairness audits is not a mystery but a calculable geometric property. The researchers proved that the amount of change in a fairness score is directly tied to the number of neighbors that get swapped out during a perturbation. They found that the maximum change in distance between any two points is limited by the size of the disturbance, and this limit dictates how much the local neighborhood can shift. When they applied these findings to standard data sets, the observed behavior matched their predictions perfectly. The audits were most stable in regions where the "local separation margin"—the gap between a person's closest neighbors and the next closest group—was large.

This work shifts the focus from simply building better models to understanding the reliability of the tools used to measure them. It suggests that before declaring a system unfair, auditors must first verify that the neighborhood structure is stable enough to support such a conclusion. If the data geometry is too loose, the audit itself becomes an unreliable instrument, unable to distinguish between genuine bias and random noise. The researchers provide a framework for calculating exactly how much confidence one can place in a fairness assessment based on the underlying data structure. By quantifying this vulnerability, they offer a way to design more robust auditing procedures that can withstand the inevitable imperfections of real-world data, ensuring that the judgment of fairness is as solid as the data it rests upon.

Technical Summary: A Geometric Theory of Robust Fairness Audits

Problem Statement

Neighborhood-based fairness audits are a standard method for evaluating individual fairness in algorithmic decision-making. These audits operate on the premise that similar individuals (defined by proximity in feature space) should receive similar predictions. Typically, this is implemented by comparing an individual's prediction against those of their $k$ -nearest neighbors (k-NN).

While widely used for their model-agnostic nature and ability to detect localized unfairness, the robustness of the auditing procedure itself has been largely overlooked. Existing literature focuses on making prediction models robust to adversarial perturbations, but assumes the auditing mechanism is stable. In practice, however, minor perturbations in feature space—caused by noise, preprocessing, normalization, or missing values—can alter nearest-neighbor relationships. This "neighborhood replacement" can lead to significantly different fairness assessments for the exact same model, making it difficult to distinguish genuine unfairness from audit instability. There is currently no theoretical framework explaining when these audits remain stable under feature perturbations or how geometric changes propagate to audit outcomes.

Methodology

The author proposes a unified geometric framework to analyze the robustness of neighborhood-based fairness audits under bounded feature space perturbations.

1. Formalization of Audits

The framework models a local fairness audit as a two-step process:

Pairwise Fairness Evaluation: A function $g$ evaluates the fairness relationship between an individual $x_i$ and its neighbors $x_j \in N_k(i)$ .
Aggregation: An operator $\Phi$ aggregates these pairwise scores into a single local audit score $A_i(X)$ .

The author restricts their analysis to Lipschitz aggregation operators (Definition 1). This class includes arithmetic means, weighted means, trimmed means, and robust M-estimators, ensuring the framework applies to a broad range of existing auditing methods (e.g., consistency-based audits, FaiTH).

2. Geometric Perturbation Model

The analysis assumes a fixed prediction model $f$ and a dataset $X$ embedded in a metric space $(M, d)$ . A perturbed dataset $X'$ is defined as an $\epsilon$ -bounded geometric perturbation if the distance between any original point $x_i$ and its perturbed version $x'_i$ is at most $\epsilon$ .

The core geometric concept introduced is the Local Separation Margin ( $\gamma_i$ ), defined as the difference between the distance to the farthest neighbor and the distance to the nearest non-neighbor:
$\gamma_i = \min_{x_j \notin N_k(i)} d(x_i, x_j) - \max_{x_j \in N_k(i)} d(x_i, x_j)$

3. Theoretical Derivation

The paper establishes a chain of stability guarantees:

Distance Stability: Bounded perturbations ( $\epsilon$ ) result in pairwise distance changes of at most $2\epsilon$ (Lemma 1).
Margin Reduction: The local separation margin decreases by at most $4\epsilon$ (Lemma 2).
Neighborhood Invariance: If the original separation margin $\gamma_i > 4\epsilon$ , the set of $k$ -nearest neighbors remains invariant (Theorem 3).
Audit Stability: When neighborhoods change, the deviation in the audit score is bounded by the Lipschitz constant of the aggregation operator ( $L_\Phi$ ), the maximum pairwise score ( $M$ ), and the size of the neighborhood replacement set ( $|R_i|$ ) (Theorem 6).
Audit Volatility: The author introduces Audit Volatility ( $\kappa$ ), defined as the expected variation of the audit score under repeated stochastic perturbations. They prove that volatility is bounded by the expected size of the neighborhood replacement set (Theorem 8).

Key Contributions

Problem Formulation: The paper shifts the focus of robustness in fair machine learning from the prediction model to the reliability of the auditing procedure itself.
Unified Framework: It provides a geometric abstraction for neighborhood-based audits as Lipschitz aggregations, unifying various existing methods under a single theoretical umbrella.
Robustness Guarantees: The author derives deterministic, probabilistic, and expected robustness guarantees. They identify the local separation margin as a sufficient geometric certificate for neighborhood preservation and neighborhood replacement as the fundamental mechanism driving audit instability.
Quantitative Measure: The introduction of Audit Volatility offers a quantitative measure for the expected sensitivity of fairness audits under repeated perturbations.

Experimental Results

The theoretical framework was validated on three benchmark datasets: Adult Income, Bank Marketing, and COMPAS.

Geometric Stability: Experiments confirmed that observed pairwise distance distortions and reductions in separation margins remained well below the theoretical upper bounds of $2\epsilon$ and $4\epsilon$ , respectively.
Neighborhood Preservation: The Neighborhood Preservation Rate (NPR) decreased monotonically as the perturbation radius increased. Datasets with larger intrinsic separation margins (Adult, Bank) maintained higher stability compared to COMPAS.
Audit Instability Mechanism: Results demonstrated a strong correlation between the amount of neighborhood replacement and audit volatility. Across different perturbation models (uniform, Gaussian, sparse), audit volatility was primarily determined by the extent of neighborhood replacement, supporting the distribution-independent nature of the theory.
Aggregation Sensitivity: Comparing different aggregation operators (arithmetic mean, trimmed mean, median, worst neighbor) showed that operators with lower Lipschitz constants (e.g., trimmed mean, median) yielded lower audit volatility, confirming that aggregation sensitivity is a key determinant of robustness.
Dataset Geometry: The experiments verified that datasets with larger local separation margins exhibited significantly lower neighborhood replacement and audit volatility, approaching zero for well-separated neighborhoods.

Significance and Claims

The paper claims to provide the first theoretical framework for analyzing the stability of local fairness audits under feature space perturbations. Its primary significance lies in:

Diagnosing Instability: It identifies that audit instability is not merely a result of model sensitivity but is fundamentally driven by the geometric fragility of local neighborhoods (specifically, the replacement of neighbors).
Predictive Power: The framework allows practitioners to predict audit stability based on the dataset's geometric properties (separation margins) and the choice of aggregation operator, rather than relying solely on empirical observation.
Measurement Reliability: By treating fairness as a measurement problem, the work complements existing efforts in responsible AI by offering tools to quantify and mitigate the unreliability introduced by data preprocessing and noise in fairness assessments.

The author concludes that neighborhood replacement is the key geometric mechanism governing audit stability and that the proposed framework establishes a principled foundation for designing more robust neighborhood-based fairness auditing methods.