Fairness Invariants: A Relational Approach to Explaining and Mitigating Fairness Bugs

Motivation

• Individual fairness is relational: explaining a disparity requires comparing similar inputs that differ in protected attributes, but existing local explanations address single decisions and do not pinpoint discriminatory logic.The paper identifies both insufficient localization of discriminatory outcomes and a lack of compact, precise characterizations to guide mitigation.Source: §1 · p. 2

Approach

• REMI adapts loop-invariant synthesis by learning bidirectional constraints on original-counterfactual pairs, requiring both inputs to receive the same outcome for fairness to hold.Pairs are labeled fair when the model treats them identically and unfair when their outcomes differ; three alignment techniques structure the relational data.Source: §1 · p. 2

Contributions

• REMI infers discriminatory rules from aligned relational data and uses them as guardrails to selectively block or relabel unfair predictions without model retraining.The framework is presented as a data-driven approach to infer fairness invariants and automatically detect, localize, explain, and mitigate individual fairness bugs.Source: §1 · pp. 2–3

Experiments

• More than 83% of ground-truth fairness bugs were localized, compared with AFT, while neural-network guardrails reduced discriminatory decisions by at least 40%, up to 70%, outperforming retraining-based mitigation [24].Horizontal extension outperformed the baseline and other alignment methods; C4.5Tree, FIGS, and CART outperformed other rule-inference methods.Source: §1 · p. 3

Overview

• Individual fairness is relational: a decision is discriminatory when changing only protected attributes and logically dependent attributes changes the program’s outcome.The overview notes that explaining a single input, such as with local explanation methods, is insufficient for this paired comparison.Source: §2 · p. 3

B. Relational dataset construction and curation

• DCNE labels original points with pairwise fairness labels, DCVE adds counterfactuals as separately labeled instances, and DCHE concatenates differing original-counterfactual features.All three retain the relational fair (+) or unfair (−) label; DCVE doubles training instances, while DCHE exposes interactions between paired values.Source: §2 · p. 4

C. Interpretable learning and rule extraction

• Tree-based explainers partition curated features by relational labels and extract if–then rules from leaves with many unfair samples; those rules can defer unsafe cases to human review.The learner uses non-protected attributes, and for DCHE their counterfactual counterparts, so the rules describe where the program is unfair.Source: §2 · p. 4

Overview Example

• Across 30,000 hiring applicants, REMI found 2,250 ethnicity-counterfactual pairs with flipped hiring decisions, in an example where ethnicity causally affects college rank upstream.The remaining 27,750 pairs were labeled fair with respect to ethnicity.Source: §2 · pp. 4–5

Which curation scheme best enables discrimination localization?

• Up to 2,234 of 2,250 individual discriminatory instances were localized using DCNE, with accuracy around 0.99 and precision close to 0.99.Source: §2 · p. 5

Which interpretable learner is the best at identifying discriminatory regions?

• 2,237 IDIs were localized by C4.5Tree, which outperformed the other six tree-based and interpretable algorithms compared with DCNE fixed.Source: §2 · p. 5

How does our approach perform to pinpoint the root cause of the fairness bug?

• 97 relational rules cover 98% of the considered discriminatory instances, including a rule that captures 301 of 2,250 IDIs (13.4%).The example rule links a narrow college-rank and experience range with counterfactual ethnicity and college-rank values, recovering the ethnicity-to-college-rank-to-hiring pathway.Source: §2 · p. 5

How to Mitigate Unfairness

• 2,250 discriminatory instances fell to 2 after REMI applied learned rules as guardrails, while preserving similar classification metrics.Naively replacing the program with an unconstrained decision tree trained on counterfactual labels increased fairness bugs to 2,430 on unseen samples.Source: §2 · p. 5

• A DPuT maps individual inputs to binary decisions, and an outcome flip after changing protected attributes (and logically dependent attributes) constitutes counterfactual unfairness [23].Source: §3 · pp. 5–6
• The relational dataset labels original-counterfactual pairs as fair when their outcomes agree and unfair when they disagree, shifting explanation from individual decisions to pair-level labels.Source: §3 · p. 6
• Counterfactual inputs change protected attributes while preserving non-protected attributes except when logical consistency requires dependent attributes to change.Source: §3 · p. 6
• The goal is an interpretable decision-tree-based model that predicts pair labels and identifies disagreement regions using non-protected attributes.The learner partitions the feature space to distinguish agreement from disagreement.Source: §3 · pp. 6–7
• Rules for disagreement regions become guardrails that withhold decisions for human review or relabel them to restore pair consistency, while aiming to limit residual unfairness, unnecessary blocks, and utility loss.Source: §3 · p. 7

4.1 Counterfactual Generation and Finding Discriminatory Instances

• REMI identifies an individual discriminatory instance (IDI) when an original and protected-attribute counterfactual receive different outcomes.For symbolic programs, it flips the protected attribute and updates dependent non-protected attributes; for data-driven programs, it uses Themis, ExpGA, and LIMI to find and merge IDIs.Source: §4.1 · p. 7

4.2 Curating Relational Dataset

• REMI labels pairs with matching outcomes as fair (+) and pairs with differing outcomes as discriminatory (−), then curates the relational dataset for supervised classification.The curation operator is one of DCNE, DCVE, or DCHE.Source: §4.2 · p. 8

4.2.1 Approach 1: Dataset curation with no extension (DCNE).

• DCNE retains each original instance and its pair’s relational label, dropping the original outcome label and counterfactual features to avoid potentially unsound feature combinations.This is particularly important for black-box programs, where counterfactual validity cannot be verified.Source: §4.2.1 · p. 8, §4.2 · p. 8

4.2.2 Approach 2: Dataset Curation With Vertical Extension (DCVE). 𝑖)

• DCVE treats the original and counterfactual as separate rows with the same relational label, doubling dataset size to help distinguish fair from unfair pairs.Both rows are labeled according to whether their pair is fair or discriminatory.Source: §4.2.2 · p. 8

4.2.3 Approach 3: Dataset Curation With Horizontal Extension (DCHE).

• DCHE merges each original-counterfactual pair into one row, retaining differing feature values, dropping identical features, and labeling the row with the pair’s relational label.The method aims to give the classifier information from both original and counterfactual values.Source: §4.2.3 · pp. 8–9

4.3 Interpretable Learning and Synthesizing the explanation

• REMI trains a leaf-limited interpretable model to classify fair versus unfair pairs, then turns paths to discriminatory leaves into rules localizing attribute ranges associated with discrimination.Rule confidence measures the fraction of captured instances that are IDIs, while coverage measures the fraction of all true IDIs captured by the rule.Source: §4.3 · p. 10

4.4 Mitigation via Guardrail

• At prediction time, the guardrail checks whether an input matches any discriminatory rule and denies output for matches, abstaining from decisions that could lead to discrimination.Source: §4.4 · p. 10

5 Experiments

• The experiments cover six symbolic programs with diverse discriminatory scenarios and 20 DNNs trained on Adult Census or Bank Marketing data.The symbolic programs include hiring, recidivism, and additive-scoring scenarios; the DNN benchmarks are black-box feed-forward networks with ReLU activations.Source: §5 · pp. 10–11

5.1 RQ1. Effectiveness of Relational Dataset Curation

• Relational dataset curation outperformed the baselines in 80% of cases, with horizontal and no-extension alignments similarly effective at explaining individual discrimination.The three proposed curation techniques localized the most IDIs in about 83% of cases; AFT performed better on PG5.Source: Table 2 · p. 12, §5.1 · p. 13

5.2 RQ2. Performance of Interpretable Algorithms in Inferring Fairness Invariants

• C4.5, FIGS, and CART were the most effective interpretable learners, achieving top-tier fairness-invariant performance in 83% of benchmarks.XGB and GBC were computationally efficient but lacked the inherent interpretability needed for precise bug localization.Source: §5.2 · p. 13, Table 3 · p. 14

5.3 RQ3. Various Characteristics of the Relational Explanation Models.

• REMI outperformed the state-of-the-art technique AFT in 83% of cases and identified all discrimination regions from symbolic programs in more than 66% of cases.In PG1, the extracted rule captures the ethnicity-to-college-rank-to-hiring pathway. Coverage was 100% in PG2, PG3, and PG4, versus 53% in PG5.Source: §5.3 · p. 15

5.4 RQ4. Performance of Bias Mitigation via Fairness Invariant Guardrails

• Guardrails reduced discriminatory instances in all tested cases, including from 2,250 to 2 in one case and to zero in four of six cases.Performance metrics remained close to those of the original programs; some benign points were falsely flagged where discriminatory and non-discriminatory inputs were difficult to separate.Source: Table 5 · p. 16, §5.4 · p. 16

5.5 RQ5. Generalization of Remi to Black-Box Neural Networks (DNNs).

• REMI reduced individual discriminatory instances in black-box DNNs by at least 40% and up to 84%, with extracted rules achieving 0.83–0.88 confidence and 41–84% discrimination coverage.The reported results span Adult Census and Bank Marketing models; rule extraction results cover 12 Adult Census DNN benchmarks.Source: §5.5 · pp. 16, 18, Table 6 · p. 16, Table 7 · p. 17

Runtime and Performance Overhead

• The full symbolic REMI pipeline takes under 120 seconds per program; for DNNs, IDI discovery is capped at 3,600 seconds and remaining stages take under 30 seconds per model.The discussion notes there is no single ablation table: RQ1 varies data alignment with CART fixed, while RQ2 varies interpretable learners with curation fixed.Source: §6 · p. 18

Limitation

• REMI is a post-processing guardrail compatible with any classifier, but it audits sampled regions rather than proving global fairness and cannot capture regions absent from IDI-finding data.If IDI finding discovers none, REMI cannot proceed, though that does not guarantee fairness; natural-language and vision applications would require domain-specific counterfactual generators and semantic-validity filters.Source: §6 · pp. 18–19

Threats to Validity

• Experiments use repeated runs with averages and standard deviations, fixed seeds, 20 DNNs and diverse symbolic programs, and once-generated fixed symbolic datasets to address validity threats.The discussion acknowledges seed dependency and says hyperparameter choices follow established standards.Source: §6 · p. 19

Validity of Counterfactual Inputs

• Counterfactuals flip protected attributes within valid domains and update causally dependent features using symbolic benchmark logic or DNN dataset constraints, but unknown dependencies may yield invalid DNN inputs.Source: §6 · p. 19

Validity of Explanations

• REMI explanations are assessed through rule impurity, confidence, coverage, ground-truth symbolic logic, and guardrail mitigation, but DNN explanations can only be validated indirectly.In symbolic settings, interpretability maps discriminatory logic to non-protected-feature regions, supporting generalization beyond point violations and serving as a check against ground-truth logic.Source: §6 · p. 19

Concrete Examples of Fairness Violations, Rules, and Mitigation

• In a COMPAS-like PG2 example, {age ≤20.5 ∧ priors_count ≤3.5} captured and guardrail-eliminated all 206 sex-flip IDIs among 6,908 sampled individuals.PG2 encodes a simplified recidivism scoring rule (Listing from).Source: §6 · p. 19

Fairness Testing

• IDI testing uses black-box tools [24] or white-box generators [46], while group fairness has also been extensively studied [10] [14] [15].This work followed the causal fairness definition for individual testing [27] and focused on discovering discriminatory inputs at scale [4] [24] [45]. Many tools can provide IDIs for REMI’s first stage when the DPuT matches their target model.Source: §7 · p. 20

Formal Methods

• Formal fairness work includes FairSquare’s probabilistic volume-based verification, John et al.’s certification of standard ML architectures [30], and Fairify’s SMT translation of neural networks [11].Source: §7 · p. 20

Explainable-AI and Interpretability

• LIME, SHAP [42], and DiCE [48] explain models or decisions, while FairLay-ML and Parfait-ML address fairness debugging or configuration; REMI uses interpretable models to explain unfairness causes.Source: §7 · p. 20

Bias Mitigation

• Prior post-processing methods [20] [21] [28] modify black-box decision logic; REMI instead uses explanation-derived guardrails for symbolic and data-driven black-box software.Source: §7 · p. 20

8 Conclusion and Future Work

• REMI transforms counterfactual pairs into a relational dataset and uses interpretable rule-based explainers to localize discriminatory regions.The resulting fairness invariants explain discrimination’s root cause and provide real-time guardrails as a mitigation strategy.Source: §8 · p. 20
• Across symbolic, scoring, and deep neural network programs, REMI outperforms state-of-the-art baselines.Source: §8 · p. 20
• Future work will extend the relational framework to unstructured domains, such as natural language.Source: §8 · p. 20