Explanation-Guided Fairness Testing through Genetic Algorithm

1 INTRODUCTION

• Individual fairness concerns whether similar individuals receive similar decisions, and fairness is presented as critical to trusted AI systems.The introduction distinguishes individual fairness from group fairness and says this work focuses on individual fairness.Source: §1 · p. 1
• Prior methods are limited by costly symbolic execution, unguided or semi-guided searches with low discriminatory-sample success, and gradient requirements unavailable for black-box models.The paper identifies SG, THEMIS, AEQUITAS, and MT-NLP in connection with the search limitations, and ADF with the gradient requirement.Source: §1 · p. 1
• ExpGA uses interpretable-method explanations to select seeds that can yield discriminatory samples after slight feature changes, then uses GA fitness optimization to search for more.It requires only model prediction probabilities, allowing use with black-box models.Source: §1 · p. 2
• The evaluation compares ExpGA with AEQUITAS, SG, ADF, and MT-NLP across five training models, three tabular benchmarks, and two text benchmarks.The tabular benchmarks are handled by AEQUITAS, SG, and ADF, while MT-NLP is used for the text benchmarks.Source: §1 · p. 2
• On tabular datasets, ExpGA takes less than 0.2s per discriminatory sample at a 49% average success rate; on text datasets, it is five times more efficient and twice more effective than MT-NLP.The paper also reports that ExpGA outperforms four state-of-the-art approaches overall and is more stable across models.Source: §1 · p. 2

2.1 Individual Discrimination

• Individual discrimination occurs when a pair of samples differs on protected-attribute-related features and receives different classifier decisions.The section illustrates this with samples differing only in sex, a feature related to gender, that receive different classes.Source: §2.1 · p. 2

2.2 Locally Interpretable Method

• A local interpreter explains one sample’s prediction by returning a ranked set of features according to their importance to that decision.The interpreter takes a test sample and its classification result as input.Source: §2.2 · p. 2

2.3 Genetic Algorithm

• A genetic algorithm iteratively searches candidate solutions using selection, crossover, and mutation, with fitness guiding selection.Crossover exchanges parent gene fragments, while mutation randomly changes some fragments and can enhance solution diversity.Source: §2.3 · pp. 2–3

2.4 Problem Definition

• Given a black-box model, training dataset, feature space, and protected attributes, the problem is to efficiently detect individual discriminatory samples without model-internal knowledge.The paper seeks to improve fairness by adding discovered samples to the training data and retraining.Source: §2.4 · p. 3

3 METHODOLOGY

• ExpGA takes a dataset and its trained model, selects seeds with an interpretable method, then uses GA selection, crossover, and mutation to generate discriminatory samples.The selected seeds are described as more likely than other samples to yield discriminatory samples after slight feature changes.Source: §3 · p. 3
• The examples cover tabular records and text paragraphs, both represented as feature vectors; a feature is a value in tabular data and a word in text.The examples are drawn from a census income dataset and an IMDB movie-comment sentiment dataset.Source: §3 · p. 3, Figure 3 · p. 3

3.1 Initialization Phase

• Initialization identifies sensitive words, generates explanations, and selects samples whose sensitive words rank highly as seeds for later GA search.The method assumes non-sensitive words dominate classification in non-discriminatory samples, while sensitive words rank relatively high in discriminatory samples.Source: §3.1 · p. 3, §3.1.2 · p. 4

3.1.1 Preprocessing.

• Preprocessing uses a knowledge graph to connect words to protected attributes, helping identify indirect terms such as “master” as gender-related.The graph uses relations such as IsA and RelatedTo and expands similar words; a word connected by an accessible path to an attribute is treated as sensitive.Source: §3.1.1 · pp. 3–4, Figure 4 · p. 4

3.1.2 Explanation Generation.

• Explanation generation ranks features by their importance scores and checks sensitive-word ranks against threshold 𝜖 when selecting seed candidates.The highest rank number among the sample’s sensitive words is checked against the threshold.Source: §3.1.3 · p. 4

3.1.3 Construction of Seed Sample Set.

• Seed construction trades seed quantity against quality: a larger 𝜖 selects more seeds but can admit lower-ranked sensitive words, while a smaller 𝜖 yields fewer, higher-quality seeds.The initialization algorithm takes the dataset, protected attributes, classifier, interpreter, target seed count, and 𝜖, and outputs a seed set.Source: §3.1.3 · p. 4

3.2 Optimization Phase

• Each user-set iteration applies selection, crossover, and mutation to the seed-based population, then checks candidates for discriminatory label differences.A candidate is discriminatory when replacing its sensitive word with its paired alternatives yields different predicted labels.Source: §3.2 · p. 4, §3.2.4 · p. 6

3.2.1 Construction of Initial Population.

• For tabular data, all seeds enter the initial population; for text, each seed yields 20 synonym-replaced samples plus itself.Text replacements use non-sensitive words with similar meanings computed using GloVe.Source: §3.2.1 · p. 5

3.2.2 Selection.

• Selection assigns higher-fitness samples greater selection probability, with fitness measuring the prediction-probability gap between opposite-sensitive-word variants.The selected population has the same sample size as the current population.Source: §3.2.2 · p. 5

3.2.3 Crossover and Mutation.

• Crossover exchanges randomly selected sample fragments, while mutation replaces non-sensitive words with similar words to expand the search space.Mutation may use same-category replacements for categorical words, synonyms for text, or other numeric values.Source: §3.2.3 · pp. 5–6

4 EVALUATION

• The evaluation asks about detection performance on tabular and text data and whether generated discriminatory samples improve fairness through retraining.It uses five public benchmarks: Census Income, German Credit, Bank Marketing, IMDB, and SST.Source: §4 · p. 6, §4.1.1 · p. 6

4.1.1 Datasets.

• The benchmarks comprise three tabular datasets and two text datasets, covering income, credit, bank marketing, and movie-review classification tasks.The datasets identify protected attributes including gender, age, race, and country.Source: §4.1.1 · p. 6

4.1.2 Baseline Approaches.

• Tabular comparisons use AEQUITAS [40], SG, and ADF; text comparisons use MT-NLP.Experiments average 30 runs on tabular data; MT-NLP is compared using its published results because its source code is unavailable.Source: §4.1.2 · pp. 6–7

4.1.3 Trained Models and Interpreters.

• The evaluation trains SVM, Random Forest, and MLP models for tabular datasets and CNN and Logistic Regression models for text datasets.LIME is used for tabular datasets and SHAP for text datasets by default.Source: §4.1.3 · p. 7

4.1.4 Measurement Metrics.

• Detection is measured using DSS, average time per discriminatory sample, and SUR, the success rate of generating discriminatory samples.Smaller DSS and larger SUR indicate better performance; SUR divides detected discriminatory samples by generated testing samples.Source: §4.1.4 · p. 7

4.1.5 Parameters Setting.

• The seed threshold ε is set using the 20th-ranked sample among 100 randomly selected samples, targeting about 20% as seeds.Crossover and mutation rates are configured from experimental experience.Source: §4.1.5 · p. 7

4.2 Performance on Tabular Datasets

• ExpGA significantly outperforms the baselines on TSN, with crossover and mutation generating more testing samples while avoiding localized search.The authors attribute the larger search space to these GA operators.Source: §4.2 · p. 8
• ExpGA generates about 4 times as many discriminatory samples as ADF; on Census with gender protected, its DSS is 0.03s versus 2s for AEQUITAS and 4.13s for SG.The 0.03s figure is the time to generate a discriminatory sample.Source: §4.2 · p. 8
• ExpGA has the best SUR on most datasets, but on Bank its 57.90% trails SG's 68.63% within one hour; after two hours, ExpGA surpasses SG.The authors attribute the exception to ExpGA not reaching a stable SUR within the one-hour period.Source: §4.2 · p. 8
• ExpGA's performance is more stable across MLP, RF, and SVM models, unlike AEQUITAS on Bank and SG on Census Income, which show marked model-dependent results.AEQUITAS's Bank SUR is 0.13% with SVM versus values sometimes reaching 63.16% with MLP and RF; SG's DSN reaches zero with SVM on Census Income.Source: §4.2 · p. 8
• Without GA, SUR stays at or below 6% and DSS is six times higher than with GA, while fitness-guided search generates discriminatory candidates.The GA comparison keeps seed exploration the same.Source: §4.2 · p. 9
• AEQUITAS's random global search is inefficient, SG can sometimes outperform ExpGA but uses time-consuming symbolic execution, and ADF's gradient requirement limits its practical availability.The authors describe ADF as a possible choice for white-box deep learning models.Source: §4.2 · p. 9
• ExpGA's generated samples cover a larger area than those of the other approaches, and statistical tests find its DSS significantly smaller than theirs.The diversity comparison uses 1,000 randomly selected discriminatory samples per approach on MLP, projected to two dimensions with PCA; all reported p-values are 0 and effect sizes are below 0.29.Source: Figure 7 · p. 8, §4.2 · p. 9
• Across tabular datasets, ExpGA outperformed three baseline approaches in efficiency and effectiveness, detecting a discriminatory sample in under 0.2s on average with about 49% success, and its performance was more stable across diverse models.Source: §4.2 · p. 9

4.3 Performance on Text Datasets

• ExpGA's DSS and SUR on text datasets are worse than on tabular datasets because text substitutions are limited to synonyms to preserve syntax and semantics.The finite synonym choices also yield a smaller DSN on text datasets than on tabular datasets.Source: §4.3 · p. 9
• Detection takes longer on IMDB than SST; the authors attribute this to IMDB samples being ten times longer on average, increasing the detection space and iteration time.Source: §4.3 · p. 9
• ExpGA is at least five times more efficient and twice as effective as MT-NLP on text datasets.On IMDB, ExpGA has smaller TSN but about five times smaller DSS and at least twice the SUR of MT-NLP.Source: §4.3 · p. 9

4.4 Fairness Improvement through Retraining

• The retraining experiment reserves discriminatory samples for both training and testing; tabular retraining uses 10% of the original dataset, while text percentages are based on generated-sample counts.The authors use half of generated discriminatory samples for retraining and the remainder for testing.Source: §4.4 · p. 10
• Table 9 reports model accuracy and ExpGA performance before and after retraining, with DSS and SUR improvements compared against their pre-retraining values.Normal Sample Testing Accuracy measures accuracy on normal samples; Discriminatory Sample Testing Percentage measures accuracy on discriminatory ground-truth samples.Source: §4.4 · p. 10, Table 9 · p. 10
• After retraining, ExpGA's SUR drops by an average of 56%, up to 94.26% on SST, and its DSS indicates longer detection times.For example, in SST with country protected, about three hours of searching finds only 18 discriminatory samples.Source: §4.4 · p. 10
• After retraining with augmented data, more than 97% of the original discriminatory samples are not biased to the new models, while normal-sample testing accuracy remains nearly unchanged.The procedure retains generated discriminatory samples in the dataset, retrains the model, and re-runs ExpGA; the evaluation uses held-out generated samples as discriminatory ground truth.Source: §4.4 · pp. 9–10, Table 9 · p. 10

5.1 Threats to Internal Validity

• Imperfect LIME or SHAP explanations may omit or mismatch sensitive features, affecting the quality of ExpGA's seed samples.The authors plan to explore additional interpretable methods.Source: §5.1 · pp. 10–11
• Retraining with ExpGA-detected discriminatory samples improved model fairness, but the authors do not claim it eliminates the fairness issue.They identify considering fairness during data preparation and model training as a future direction.Source: §5.1 · p. 11

5.2 Threats to External Validity

• Evaluation on five baseline benchmark datasets does not establish performance on other datasets or protected attributes.Source: §5.2 · p. 11
• The prior knowledge graph covers only a limited set of protected attributes, so other domains require extending it.Source: §5.2 · p. 11

Fairness Testing

• THEMIS uses random test-case generation; AEQUITAS searches directionally, while SG uses LIME perturbations and symbolic execution to generate test inputs.The cited work describes AEQUITAS's directional search as limiting coverage across diverse sample distributions.Source: §6 · p. 11
• ADF requires model gradients and is designed for DNNs, whereas ExpGA uses explanation results to identify high-quality seed samples.Both SG and ExpGA leverage interpretable methods, but ExpGA uses explanations for seed selection.Source: §6 · p. 11
• Fair-SMOTE addresses group fairness by generating data for underrepresented subgroups and removing biased training samples; this paper focuses on individual fairness.Source: §6 · p. 11

Interpretable Methods

• LIME represents feature importance with weights from a local linear model; SHAP uses feature-value kernels and game-theoretic constraints, while LORE uses genetic algorithms and decision-tree rules.Another cited method approximates local decision boundaries with multiple linear models and chooses the most accurate interpretation.Source: §6 · p. 11

Fairness Testing

• ExpGA is characterized as a lightweight, model-agnostic individual fairness testing method for diverse and large-scale scenarios.Source: §6 · p. 11

• ExpGA combines explanation results and a genetic algorithm to detect discriminatory samples efficiently and effectively, while handling black-box models.Experiments report faster detection with higher success rates than four state-of-the-art methods on text and tabular benchmarks.Source: §7 · p. 11
• Retraining tested models with ExpGA-generated discriminatory samples substantially improves their fairness.Source: §7 · p. 11