Source-linked AI summary
Operationalizing Individual Fairness with Pairwise Fair Representations
Preethi Lahoti, Krishna P. Gummadi, Gerhard Weikum
TL;DR
Operationalizing individual fairness is difficult because experts struggle to specify similarity metrics and compare people across groups without bias. PFR maps individual data records into a new representation using a sparse fairness graph that captures pairwise similarity among a subsample of training individuals. PFR is consistently best on individual fairness, while its AUC is competitive and typically within 2… of the best method.
Problem
Operationalizing individual fairness is difficult because experts struggle to specify similarity metrics and compare people across groups without bias.
Source: §1.1 · p. 1, §4.3.1 · p. 9Method
PFR maps individual data records into a new representation using a sparse fairness graph that captures pairwise similarity among a subsample of training individuals.
Source: §1.2 · p. 2Results
PFR is consistently best on individual fairness, while its AUC is competitive and typically within 2… of the best method.
Source: §4.6 · p. 12Takeaways & Limitations
Fairness judgments are needed during training, but not for previously unseen test individuals, supporting PFR’s practical viability.
Source: §4.6 · p. 12Human neighborhood-safety judgments may be biased in favor of African-American neighborhoods because residents tend to view their neighborhoods positively.
Source: §4.3.1 · p. 9
Abstract
from arXiv · showhide
We revisit the notion of individual fairness proposed by Dwork et al. A central challenge in operationalizing their approach is the difficulty in eliciting a human specification of a similarity metric. In this paper, we propose an operationalization of individual fairness that does not rely on a human specification of a distance metric. Instead, we propose novel approaches to elicit and leverage side-information on equally deserving individuals to counter subordination between social groups. We model this knowledge as a fairness graph, and learn a unified Pairwise Fair Representation (PFR) of the data that captures both data-driven similarity between individuals and the pairwise side-information in fairness graph. We elicit fairness judgments from a variety of sources, including human judgments for two real-world datasets on recidivism prediction (COMPAS) and violent neighborhood prediction (Crime & Communities). Our experiments show that the PFR model for operationalizing individual fairness is practically viable.
1. INTRODUCTION
Individual fairness asks that similar people receive similar outcomes, but specifying a task-specific similarity metric is difficult and can fail to capture subjective judgments about who deserves similar treatment. The paper proposes fairness graphs and Pairwise Fair Representations (PFR) to encode those judgments for downstream prediction.
1.1 Motivation
- Human experts find it difficult to specify quantitative similarity metrics or encode subjective judgments about who should be treated similarly across groups.Prior individual-fairness approaches that learn feature weights for assumed distance metrics simplify the original notion.Source: §1.1 · pp. 1–2
1.2 Approach
- The paper models judgments about equally deserving pairs as edges in a fairness graph, which may be partial, sparse, subjective, and noisy.The approach also proposes within-group rankings and cross-group quantile links when direct comparisons between groups are difficult.Source: §1.2 · p. 2
- PFR combines input-feature utility with pairwise fairness-graph information in a learned representation for downstream tasks.The representation can be applied to unseen individuals using their regular data attributes, without test-time human judgments.Source: §1.2 · p. 2
1.3 Contribution
- The contributions include fairness-graph construction methods, a graph-embedding representation learner, and experiments on synthetic data and COMPAS and Crime and Communities datasets.The real-world tasks are recidivism prediction and violent-neighborhood prediction.Source: §1.3 · p. 2
2. RELATED WORK
Related work spans group-fairness constraints and individual-fairness methods, with approaches often treating the two separately. Earlier individual-fairness work learns restricted distance metrics or derives similarity from task objectives, while PFR aims to encode both features and fairness-graph edges.
Group Fairness
- Group-fairness research targets parity-like outcomes, while individual fairness focuses on similar treatment for similarly qualified people.The paper notes that approaches enforcing group fairness have mostly ignored individual fairness, and vice versa.Source: §2 · pp. 2–3
Bridging Individual and Group Fairness
- Prior individual-fairness methods learn restricted distance metrics from data, while some use training or predicted labels to define similarity.The paper observes that societal fairness goals may conflict with learning objectives when labels are biased or features are missing.Source: §2 · p. 3
- The approach assumes experts can provide coarse-grained judgments informed by past societal unfairness and future societal goals.The authors state that constraining outcomes for cross-group pairs can achieve both individual and group fairness to a large degree.Source: §2 · p. 3
Learning Pairwise Fair Representations
- PFR learns representations that retain input information while bringing equally deserving individuals closer, and can represent individuals unseen during training.Its optimization relates to graph embedding, encoding both individual attributes and fairness-graph connections.Source: §2 · p. 3
3. MODEL
The model represents input records and protected-group membership, then turns judgments or within-group rankings into edges linking individuals considered equally deserving. For incomparable groups, it connects people in matching within-group quantiles.
3.1 Notation
- The input X contains N records and M attributes, Z is a lower-dimensional representation, and S denotes protected-group membership.The model permits more than two values for the protected attribute and combines multiple protected attributes into one when needed.Source: §3.1 · p. 3
3.2 From Distance Metric to Fairness Graph
- Fairness-graph construction addresses the difficulty of eliciting quantitative similarity metrics by using pairwise judgments, equivalence classes, or within-group rankings.Pairwise judgments may be available only for a sample of pairs.Source: §3.2 · p. 3
3.2.1 Fairness Graph for Comparable Individuals
- For comparable individuals, an edge can link sampled people judged similarly qualified or placed in the same equivalence class.Equivalence-class graphs identify equally deserving individuals and may be sparse when judgments cover only sampled representatives.Source: §3.2.1 · pp. 3–4
3.2.2 Fairness Graph for Incomparable Individuals
- For incomparable groups, the method ranks individuals within each group and links people who occupy the same quantile across groups.This avoids requiring direct cross-group judgments; the resulting graph can cover socially salient groups beyond legally protected categories and may be sparse.Source: §3.2.2 · p. 4
- A k-th quantile is defined by the value whose cumulative probability is k, with a technical adjustment needed for discrete variables.The passage notes that appropriate ceiling functions are omitted for discrete behavior.Source: §3.2.2 · p. 4
- The between-group quantile graph connects individuals from different groups whose scores lie in the same quantile; with two groups, it is bipartite.The text describes the graph as multipartite for multiple groups.Source: §3.2.2 · p. 4
3.3 Learning Pairwise Fair Representations
PFR learns a low-dimensional representation by balancing preservation of local input-space neighborhoods against closeness of fairness-graph-connected individuals. The linear model is optimized as an eigenvector problem, supports inference without new fairness judgments, and is presented experimentally only in its linear form.
3.3.1 Objective Function
- PFR learns a lower-dimensional representation that preserves input-space utility while incorporating pairwise fairness-graph information.The representation is intended for downstream tasks whose targets may be unknown during representation learning.Source: §3.3.1 · p. 4
- The input-space loss encourages nearby records among each record’s p nearest neighbors to remain close in the representation.Points outside those local neighborhoods are disregarded, relaxing the dimensionality-reduction problem.Source: §3.3.1 · p. 4
- The fairness-graph loss penalizes connected individuals when their learned representations are far apart, without requiring a distance metric for the graph.The combined objective weights input-space and fairness-graph losses with γ, and an orthonormality constraint prevents mapping all records to one point.Source: §3.3.1 · p. 5
3.3.2 Equivalence to Trace Optimization Problem
- Minimizing the pairwise weighted-distance loss is equivalent to minimizing a trace expression using the graph Laplacian.The derivation applies to either the input-space graph or fairness graph.Source: §3.3.2 · p. 5
3.3.3 Optimization Problem
- The linear optimization learns an M × D matrix V, maps records as z_i = V^T x_i, and imposes V^T V = I to eliminate trivial solutions.The columns of V are eigenvectors for the D smallest eigenvalues; γ is a regularization hyper-parameter.Source: §3.3.3 · p. 5
3.3.4 Inference
- For an unseen individual, PFR computes z_i = V^T x_i using the learned basis, without requiring fairness labels at inference.The fairness graph is needed during training to learn V.Source: §3.3.4 · p. 5
3.3.5 Kernelized Variants of PFR
- The paper restricts its reported results to linear PFR, though it describes a kernelized nonlinear generalization.The kernel variant uses Mercer kernels without computing φ(X) explicitly; its investigation is left for future work.Source: §3.3.5 · p. 5
4. EXPERIMENTS
Experiments compare fairness-enhancing methods on binary classification, examining learned representations and fairness outcomes, with additional analyses of hyperparameter robustness and fairness-graph label sensitivity.
4. EXPERIMENTS
- The experiments ask what learned representations look like and how the methods affect individual and group fairness.The questions are addressed in Subsections 4.2, 4.3.2, and 4.3.3.Source: §4 · pp. 5–6
- The experiments also examine the influence of the methods on a trade-off, although the passage does not specify its terms.Source: §4 · p. 6
- Additional analyses test robustness to γ and sensitivity to the number of labels in the fairness graph.These results are reported in Subsections 4.4 and 4.5.Source: §4 · p. 6
4.1 Experimental Setup
The setup compares representation-learning and post-processing fairness methods on downstream classification, using shared tuning procedures, three datasets, and utility, individual-fairness, and group-fairness measures.
4.1 Experimental Setup
- PFR, iFair, LFR, Hardt, and the original representation form the comparison set, with distinct fairness and accuracy objectives across methods.PFR optimizes individual fairness according to both W_F and W_X; the baselines differ in whether they target group fairness or protected-attribute obfuscation.Source: §4.1 · p. 6
- Augmented baselines receive fairness-graph judgments as training features, with missing judgments set to -1 and no such labels available at test time.At test time, PFR likewise uses only data attributes X.Source: §4.1 · p. 6
- Each method uses grid search with five-fold cross-validation, and reported results average ten runs on independent test sets.Each dataset is split into training and test sets, with the test set reserved for measuring performance after tuning.Source: §4.1 · p. 6
- The downstream task uses synthetic university-admission data and real-world Crime & Communities and COMPAS datasets.Representation-learning methods feed an out-of-the-box logistic regression classifier; Table 1 summarizes dataset statistics and settings.Source: §4.1 · p. 6, Table 1 · p. 6
- Utility is measured by AUC, individual fairness by consistency on W_X and W_F, and group fairness by error rates and positive-prediction rates.The reported group measures include per-group FPR and FNR; disparate impact concerns equal positive-prediction rates across groups.Source: §4.1 · p. 6
4.2 Experiments on Synthetic Data
Synthetic experiments compare PFR with other representations on utility, individual fairness, and group fairness. Across low- and high-dimensional data, PFR maps similarly deserving individuals close together while performing strongly on these measures.
4.2 Experiments on Synthetic Data
- The synthetic scenario assumes supplementary scores can be inflated for the more privileged group without increasing candidates’ ability, while adjusted candidates remain equally deserving.The data include group, academic-performance, and supplementary-performance features, with 600 training samples and 400 withheld test samples; experiments use three-feature and 203-feature versions.Source: §4.2 · p. 7
- A simulated fairness oracle labels sampled pairs as similar, and the fairness graph records those judgments as edges; baselines receive graph information as added binary features.The oracle compares prediction-probability quantiles from separate logistic-regression models for the two groups.Source: §4.2 · p. 7
4.2.1 Results on Synthetic Low Dimension Dataset
- In the low-dimensional representation, PFR brings deserving candidates from the two groups closer together than iFair+ or LFR+, while all three learned representations mix the groups.In the original data, the groups and their deserving candidates are relatively far apart.Source: §4.2.1 · p. 8
- PFR significantly outperforms competitors on consistency with respect to W_F and matches their W_X consistency while achieving better AUC and W_F consistency.The results describe the best achievable trade-off between utility and individual fairness.Source: §4.2.1 · p. 8
- PFR achieves the best AUC, even outperforming the original representation, as fairness edges help map deserving candidates across groups close together.The authors attribute the utility gain to addressing the groups’ different feature distributions.Source: §4.2.1 · p. 8
- PFR achieves well-balanced error rates with generally lower error, and its representation has nearly equal positive-prediction rates across groups.The authors report that its group-fairness performance is as good as Hardt’s, although PFR does not directly optimize group fairness.Source: §4.2.1 · p. 8, Figure 3 · p. 8
4.2.2 Results on Synthetic High Dimension Dataset
- LFR+’s apparent consistency advantage is degenerate on this dataset: it accepts virtually all individuals and has AUC around 0.55.The authors dismiss it as a real baseline for this dataset.Source: §4.2.2 · pp. 8–9
- In the high-dimensional data, PFR achieves the best consistency on W_F, similar consistency on W_X, and significantly better AUC than the other methods.It also achieves near-equal error rates and positive-prediction rates across groups, matching Hardt on group fairness.Source: §4.2.2 · p. 9, Figure 4 · p. 9, Figure 5 · p. 9
4.3 Experiments on Real-World Datasets
The real-world experiments construct fairness graphs from neighborhood reviews and within-group COMPAS risk rankings, then compare PFR with baselines on individual and group fairness. PFR improves fairness measures in different ways across the datasets, with trade-offs on Crime & Communities and strong group-fairness results on COMPAS.
4.3 Experiments on Real-World Datasets
- The experiments use violent-neighborhood prediction for Crime & Communities and re-arrest prediction for COMPAS, with majority-white communities and race, respectively, defining protected groups.Baselines receive elicited fairness labels as numerical input features.Source: §4.3 · p. 9, §4.3.1 · p. 10
4.3.1 Constructing the Fairness Graph W F
- For Crime & Communities, human fairness judgments come from aggregated 1-to-5-star neighborhood safety reviews, available for about 1,500 of 2,000 communities.The authors note the graph may favor African-American neighborhoods because residents tend to view their neighborhoods’ safety positively.Source: §4.3.1 · p. 9
- For COMPAS, the authors avoid cross-group comparisons by connecting individuals in the same risk quantile of their respective groups, using within-group decile rankings.This construction assumes corresponding quantiles represent equal deservingness regardless of true risk; the decile scores come from an undisclosed commercial algorithm.Source: §4.3.1 · p. 9
4.3.2 Results on Crime & Communities Dataset
- On Crime & Communities, PFR alone improves consistency with the fairness graph over the baseline, but this comes with lower utility and consistency with data-driven neighborhoods.The human pairwise input is in tension with the data-attributes input, so which source should take priority depends on application design.Source: §4.3.2 · p. 10, Figure 6 · p. 10
- PFR balances Crime & Communities group error rates comparably to Hardt+ and achieves near-equal positive prediction rates, outperforming the other methods.Hardt+ is designed specifically to equalize error rates through post-processing.Source: §4.3.2 · p. 10, Figure 7 · p. 10
4.3.3 Results on Compas Dataset
- On COMPAS, PFR performs similarly to other representation-learning methods in utility and individual fairness, while clearly outperforming them on group fairness.Its group-fairness performance is comparable to Hardt+, which targets equalized error rates through post-processing.Source: §4.3.3 · p. 10
4.4 Influence of PFR Hyper-Parameter γ
The experiments vary γ, which controls the relative influence of data-space neighborhoods and fairness-graph similarity in PFR. Increasing γ improves fairness-graph consistency, including on unseen samples; its utility trade-off depends on the alignment between fairness judgments and classifier labels.
4.4 Influence of PFR Hyper-Parameter γ
- γ controls the relative influence of input-space neighborhoods and fairness-graph similarity while other hyperparameters remain fixed at their main-experiment settings.The study varies γ across [0,1].Source: §4.4 · pp. 10–11
- Increasing γ improves fairness-graph consistency on all datasets, including for unseen test samples whose fairness labels were unavailable during training.The authors interpret this as PFR generalizing individual fairness to unseen data.Source: §4.4 · p. 11
- When fairness-graph pairs conflict with ground-truth labels, as in Crime and COMPAS, higher γ yields a substantial fairness gain for a small overall AUC loss.AUC falls slightly for the non-protected group but improves for the protected group; overall AUC remains high even at very high γ.Source: §4.4 · p. 11
- When fairness-graph pairs align with ground-truth labels, as in the synthetic data, increasing γ improves AUC for both protected and non-protected groups without a fairness-utility trade-off.The authors note the graph may improve utility by helping learn a similarity manifold in the input space.Source: §4.4 · p. 11
4.5 Sensitivity to Sparseness of Fairness Graph
The sparseness experiment varies how many training examples have fairness labels and evaluates fairness on withheld test pairs. Across datasets, more labels generally improve fairness-graph consistency, while utility is affected only mildly or can improve.
4.5 Sensitivity to Sparseness of Fairness Graph
- The study varies fairness-label availability across synthetic, Crime & Communities, and COMPAS data, using sampled training pairs or percentages of labeled training examples.For the real-world datasets, labeled training-data percentages range from 10% to 100% in 10-point steps.Source: §4.5 · p. 11
- Increasing the fraction of fairness labels improves fairness-graph consistency while hurting utility only mildly or sometimes improving it.Fairness is evaluated on withheld test pairs; test examples are not given fairness labels.Source: §4.5 · pp. 11–12
- With 0.17% of fairness labels, synthetic-data consistency reaches 90% and AUC reaches 95%; Crime & Communities needs about 30–40% of labels to approach full-graph results.For Crime & Communities, at 10% labels, consistency is 59% versus 68% for the full graph, with only mild AUC impact.Source: §4.5 · p. 12
- For COMPAS, even very sparse fairness graphs keep consistency within a few percent of the best result, while AUC varies only mildly as graph sparseness changes.The authors conclude PFR can benefit from a small amount of human judgment about equally deserving individuals.Source: §4.5 · p. 12
4.6 Discussion and Lessons
PFR balances individual fairness and utility when fairness judgments conflict with ground-truth labels, while also performing well on group fairness. Its results depend on the availability and quality of pairwise judgments, though performance degrades gracefully under sparse judgments.
Individual Fairness - Utility Trade-off
- PFR is consistently best on individual fairness and keeps AUC typically within 2 percentage points of the best result when balancing fairness and utility.The trade-off depends on conflict between fairness-graph edges and ground-truth labels; PFR performs best when compromise is unavoidable.Source: §4.6 · p. 12
Balancing Individual Fairness and Group Fairness
- Human fairness judgments help PFR approach Hardt et al. on group fairness by addressing historical subordination.Hardt et al. is specifically geared toward group fairness but disregards individual fairness.Source: §4.6 · p. 12
Data Representation
- Graph embedding incorporates pairwise judgments better than adding them as features, and PFR needs pairwise judgments only during training.Previously unseen test data at deployment has no pairwise judgments.Source: §4.6 · p. 12
Graph Sparseness
- Even a small number of pairwise judgments improves fairness, while performance degrades gracefully when judgments become extremely sparse.At extreme sparseness, PFR loses its advantage.Source: §4.6 · p. 12
Robustness
- PFR remains robust across input dimensionalities and insensitive to hyperparameter choices, although performance drops somewhat as dimensionality increases.It still outperforms other approaches in balancing fairness and utility as dimensionality increases.Source: §4.6 · p. 12
Limitations
- Strong fairness–utility conflict can force a trade-off, and sparse or noisy judgments have marginal influence; PFR also assumes high consensus among judges.If that consensus assumption is invalid, PFR loses its advantages and performs as poorly as, but no worse than, other methods.Source: §4.6 · p. 12
5. CONCLUSIONS
The paper proposes Pairwise Fair Representations, which use side-information about equally deserving individuals as a fairness-enhanced input to downstream machine-learning tasks. Experiments indicate that pairwise judgments benefit protected-group members, with high individual and group fairness and reasonably low utility loss.
5. CONCLUSIONS
- PFR operationalizes individual fairness by learning a fairness-enhanced representation from pairwise side-information about equally deserving individuals.The representation is designed as an input to downstream machine-learning tasks.Source: §5 · p. 12
- Experiments with synthetic and real-life datasets indicate that pairwise judgments benefit members of the protected group.Source: §5 · p. 12
- The experiments indicate high individual fairness and group fairness, with reasonably low loss in utility.The passage characterizes group fairness as near-equal error rates across groups.Source: §5 · p. 12