Uncovering Discrimination Clusters: Quantifying and Explaining Systematic Fairness Violations

• URL: http://arxiv.org/abs/2512.23769v1
• Date: Mon, 29 Dec 2025 06:44:07 GMT
• Title: Uncovering Discrimination Clusters: Quantifying and Explaining Systematic Fairness Violations
• Authors: Ranit Debnath Akash, Ashish Kumar, Verya Monjezi, Ashutosh Trivedi, Gang, Tan, Saeid Tizpaz-Niari,
• Abstract summary: We introduce and motivate the concept of discrimination clustering.<n>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.<n>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.
• Score: 9.31821136819172
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 systematic or 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 that help expose 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-unfairness, we introduce a novel explanation method to generate interpretable, decision-tree-style artifacts. Our experiments demonstrate that HyFair outperforms state-of-the-art fairness verification and local explanation methods.

Related papers

• Individual Fairness In Strategic Classification [7.903744240517792]
  Strategic classification, where individuals modify their features to influence machine learning (ML) decisions, presents critical fairness challenges.<n>We analyze threshold-based classifiers and prove that deterministic thresholds violate individual fairness.<n>We introduce conditions under which a randomized classifier ensures individual fairness and leverage these conditions to find an optimal and individually fair randomized classifier.<n> Experiments on real-world datasets confirm that our method effectively mitigates unfairness and improves the fairness-accuracy trade-off.
  arXiv  Detail & Related papers  (2026-02-04T22:09:18Z)
• Fairness-Aware Grouping for Continuous Sensitive Variables: Application for Debiasing Face Analysis with respect to Skin Tone [3.3298048942057523]
  We propose a fairness-based grouping approach for continuous (possibly multidimensional) sensitive attributes.<n>By grouping data according to observed levels of discrimination, our method identifies the partition that maximizes a novel criterion.<n>We validate the proposed approach using multiple synthetic datasets and demonstrate its robustness under changing population distributions.
  arXiv  Detail & Related papers  (2025-07-15T12:21:52Z)
• Fair Correlation Clustering in Forests [8.810926150873991]
  A clustering is said to be fair, if each cluster has the same distribution of manifestations of a sensitive attribute as the whole input set. This is motivated by various applications where the objects to be clustered have sensitive attributes that should not be over- or underrepresented. We consider restricted graph classes which allow us to characterize the distributions of sensitive attributes for which this form of fairness is tractable.
  arXiv  Detail & Related papers  (2023-02-22T11:27:06Z)
• Practical Approaches for Fair Learning with Multitype and Multivariate Sensitive Attributes [70.6326967720747]
  It is important to guarantee that machine learning algorithms deployed in the real world do not result in unfairness or unintended social consequences. We introduce FairCOCCO, a fairness measure built on cross-covariance operators on reproducing kernel Hilbert Spaces. We empirically demonstrate consistent improvements against state-of-the-art techniques in balancing predictive power and fairness on real-world datasets.
  arXiv  Detail & Related papers  (2022-11-11T11:28:46Z)
• Fairness via Adversarial Attribute Neighbourhood Robust Learning [49.93775302674591]
  We propose a principled underlineRobust underlineAdversarial underlineAttribute underlineNeighbourhood (RAAN) loss to debias the classification head.
  arXiv  Detail & Related papers  (2022-10-12T23:39:28Z)
• Measuring Fairness of Text Classifiers via Prediction Sensitivity [63.56554964580627]
  ACCUMULATED PREDICTION SENSITIVITY measures fairness in machine learning models based on the model's prediction sensitivity to perturbations in input features. We show that the metric can be theoretically linked with a specific notion of group fairness (statistical parity) and individual fairness.
  arXiv  Detail & Related papers  (2022-03-16T15:00:33Z)
• Resolving label uncertainty with implicit posterior models [71.62113762278963]
  We propose a method for jointly inferring labels across a collection of data samples. By implicitly assuming the existence of a generative model for which a differentiable predictor is the posterior, we derive a training objective that allows learning under weak beliefs.
  arXiv  Detail & Related papers  (2022-02-28T18:09:44Z)
• Fair Group-Shared Representations with Normalizing Flows [68.29997072804537]
  We develop a fair representation learning algorithm which is able to map individuals belonging to different groups in a single group. We show experimentally that our methodology is competitive with other fair representation learning algorithms.
  arXiv  Detail & Related papers  (2022-01-17T10:49:49Z)
• MultiFair: Multi-Group Fairness in Machine Learning [52.24956510371455]
  We study multi-group fairness in machine learning (MultiFair) We propose a generic end-to-end algorithmic framework to solve it. Our proposed framework is generalizable to many different settings.
  arXiv  Detail & Related papers  (2021-05-24T02:30:22Z)
• Protecting Individual Interests across Clusters: Spectral Clustering with Guarantees [20.350342151402963]
  We propose an individual fairness criterion for clustering a graph $mathcalG$ that requires each cluster to contain an adequate number of members connected to the individual. We devise a spectral clustering algorithm to find fair clusters under a given representation graph.
  arXiv  Detail & Related papers  (2021-05-08T15:03:25Z)
• A Pairwise Fair and Community-preserving Approach to k-Center Clustering [34.386585230600716]
  Clustering is a foundational problem in machine learning with numerous applications. We define two new types of fairness in the clustering setting, pairwise fairness and community preservation.
  arXiv  Detail & Related papers  (2020-07-14T22:32:27Z)
• Distributional Individual Fairness in Clustering [7.303841123034983]
  We introduce a framework for assigning individuals, embedded in a metric space, to probability distributions over a bounded number of cluster centers. We provide an algorithm for clustering with $p$-norm objective and individual fairness constraints with provable approximation guarantee.
  arXiv  Detail & Related papers  (2020-06-22T20:02:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.