一句话：提出歧视聚类概念，并用符号验证与随机搜索结合的 HyFair 检测、量化并解释系统性公平性违规。
个体公平性检查仅在受保护属性上不同的输入对是否导致显著不同结果，但只能揭示孤立不公平实例，难以刻画影响子群体的聚类歧视。本文提出歧视聚类概念：寻找输入空间中受保护特征的小扰动使输出分裂为 k 个显著不同簇的局部区域，以量化仅由受保护属性导致的任意处理。作者提出 HyFair，混合 SMT/MILP 符号分析与随机搜索：符号分析证明个体公平性，随机搜索发现符号方法难以处理的严重歧视簇；对高 k-歧视输入生成决策树式解释。实验表明 HyFair 优于现有公平性验证与局部解释方法，并在部分基准发现显著歧视聚类。
Fairness in algorithmic decision-making is often framed in terms of individual fairness, which requires that similar individuals receive similar outcomes. A system violates individual fairness if there exists a pair of inputs differing only in protected attributes (such as race or gender) that lead to significantly different outcomes—for example, one favorable and the other unfavorable. While this notion highlights isolated instances of unfairness, it fails to capture broader patterns of clustered discrimination that may affect entire subgroups.We introduce and motivate the concept of discrimination clustering, a generalization of individual fairness violations. Rather than detecting single counterfactual disparities, we seek to uncover regions of the input space where small perturbations in protected features lead to k-significantly distinct clusters of outcomes. That is, for a given input, we identify a local neighborhood—differing only in protected attributes—whose members’ outputs separate into many distinct clusters. These clusters reveal significant arbitrariness in treatment solely based on protected attributes, exposing patterns of algorithmic bias that elude pairwise fairness checks.We present HyFair, a hybrid technique that combines formal symbolic analysis (via SMT and MILP solvers) to certify individual fairness with randomized search to discover discriminatory clusters. This combination enables both formal guarantees— when no counterexamples exist—and the detection of severe violations that are computationally challenging for symbolic methods alone. Given a set of inputs exhibiting high k-discrimination, we further introduce a novel explanation method that generates interpretable, decision-tree-style artifacts.Our experiments show that HyFair outperforms state-of-the-art fairness verification and local explanation methods. It reveals that some benchmarks exhibit substantial discrimination clustering, while others show limited or no disparities with respect to protected attributes. It also provides intuitive explanations that support understanding and mitigation of unfairness.
@inproceedings{paperbot9285,
title = {Uncovering Discrimination Clusters: Quantifying and Explaining Systematic Fairness Violations},
author = {Ranit D. Akash and Ashish Kumar and Verya Monjezi and Ashutosh Trivedi and Gang Tan and Saeid Tizpaz-Niari},
booktitle = {ASE},
year = {2025},
doi = {10.1109/ase63991.2025.00141}
}