Individual fairness in machine learning requires that similar individuals receive similar predictions. Most existing definitions are pairwise in nature, imposing a Lipschitz constraint that must hold either globally across all pairs of data instances or locally within specified neighborhoods. In practice, however, such pairwise constraints may be overly restrictive and may not directly identify which individuals receive locally inconsistent predictions. We study local predictive consistency as a node-level relaxation of pairwise individual fairness, where each prediction is compared with a similarity-weighted average of predictions in its local neighborhood. This yields an interpretable node-level fairness score and a corresponding regularized learning approach based on local residuals. Since graph-based individual fairness depends critically on the underlying similarity structure, we make the construction of the neighborhood graph explicit and discuss threshold selection through graph-coverage diagnostics. Our approach applies to binary classification, regression, and time-to-event prediction. We further compare this formulation with pairwise constraint-based approaches and analyze the resulting fairness--performance trade-offs.
Figures & tables
Figure 1: Performance–fairness operating points for binary classification as λ varies. Different regularization formulations attain different regions of the empirical fairness–performance space.
Figure 2: Performance–fairness operating points for regression as λ varies. Because the scale of λ is regularizer-dependent, comparisons are interpreted through achieved fairness levels rather than raw λ values.
Figure 3: Performance–fairness trade-offs for survival prediction. Rows correspond to datasets; columns report IBS, C-index, and violation rate VR(ε) for DeepSurv (log-risk) and DeepHazard with survival-function outputs as λ varies.
Table 2: Balanced accuracy and violation rates on the Adult dataset. For methods with a parameter λ (combinatorial Laplacian and URW), we report a balanced operating point selected from the λ grid such that the resulting violation rate at ε=0.005 is closest to that of SenSeI.
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
Task
Dataset / formulation
Coverage (%)
Isolated (%)
Classification
Adult
98.51
1.49
COMPAS
99.72
0.28
Regression
Employee Salary
99.80
0.20
Insurance
100.00
0.00
Survival
FLCHAIN – log-risk
90.79
9.21
FLCHAIN – survival curve
90.79
9.21
Appendix
Table 4: Graph coverage at the main operating threshold τ=5 . Coverage denotes the proportion of evaluation instances with at least one non-self comparison neighbor.
Figure 4: Race and Gender (GR) and Spouse (S) consistency as functions of the regularization strength λ on the Adult dataset (higher is better). Markers at λ=0 denote the unregularized model.
Figure 5: GR-consistency as a function of the regularization strength λ on the COMPAS dataset (higher is better). Markers at λ=0 denote the unregularized model.
Figure 6: Performance–fairness behavior under increasingly tail-sensitive local predictive-consistency aggregation on the Employee Salary regression dataset. Finite p uses the empirical p -norm, while p=∞ uses the log-sum-exp approximation in Eq. 29 . Greater tail sensitivity reduces high local-consistency violations more strongly under moderate-to-large regularization, at the cost of increased predictive error.
Formulation
Dataset
λ
C-index ↑
IBS ↓
IF mean ↓
Log-risk
ROSSI
0
0.5572±0.0498
0.4062±0.0796
4.6107±0.3593
Log-risk
ROSSI
10
0.6226±0.0375
0.3229±0.0540
0.0976±0.0080
Log-risk
ROSSI
100
0.6425±0.0376
0.3292±0.0553
0.0168±0.0041
Log-risk
WHAS
0
0.6688±0.0701
0.3004±0.0788
6.2926±0.6123
Log-risk
WHAS
10
0.5679±0.0634
0.2388±0.0255
0.2111±0.0332
Log-risk
WHAS
100
0.5433±0.0736
0.2476±0.0298
0.1456±0.0158
Appendix
Table 10: Multi-seed robustness results on the smaller survival datasets. Values are mean ± standard deviation over five random seeds.
Task / Dataset
Method
λ
Utility
Fairness ↓
Classification / Adult
Laplacian
30
AUC =0.8751
0.001002
URW-FKL
5
AUC =0.8771
0.012202
URW-RKL
5
AUC =0.8784
0.012263
Classification / COMPAS
Laplacian
3
AUC =0.6197
1.24×10−5
URW-FKL
10
AUC =0.6610
2.28×10−3
URW-RKL
10
AUC =0.6665
2.40×10−3
Appendix
Table 11: Representative operating points for URW and standard pairwise Laplacian regularization. Raw λ values should not be compared across methods because the regularization objectives have different scales.
Task
Method
λ
Utility
EdgeMeanAbs ↓
Adult
Baseline
0
AUC =0.8772
0.2622
URW-FKL
5
AUC =0.8771
0.2333
URW-RKL
5
AUC =0.8784
0.2332
Laplacian
0.1
AUC =0.8726
0.2302
Normalized Laplacian
1
AUC =0.8765
0.2354
Employee Salary
Baseline
0
RMSE =5251.79
0.08269
Appendix
Table 12: Comparison of URW, the standard Laplacian baseline, and the symmetric normalized-Laplacian baseline on representative classification, regression, and survival prediction tasks. Fairness is evaluated using the independent EdgeMeanAbs metric on a common held-out comparison graph. Higher AUC and C-index are better, while lower RMSE and EdgeMeanAbs are better.
Dataset
Method
λ
URW IF ↓
Mean consistency ↑
PCS ↑
BCC ↑
Adult
URW-FKL
0
0.07477
0.89285
0.91388
0.87104
URW-FKL
500
0.01385
0.94731
0.95578
0.93822
URW-RKL
0
0.10952
0.89285
0.91388
0.87104
URW-RKL
500
0.01665
0.94837
0.95788
0.94010
COMPAS
URW-FKL
0
0.10022
0.87970
0.90367
0.85198
URW-FKL
500
0.00023
0.99044
0.99307
0.98947
Appendix
Table 15: Comparison with Waller-style local consistency on Adult and COMPAS for k=5 and δ=0.5 . Higher mean consistency, PCS, and BCC indicate greater hard-label agreement with the local k -nearest neighborhood. The table reports the unregularized model and the strongest evaluated regularization level.
Dataset
Case
p^i
Waller consistency
URW IF percentile (%)
Adult
Waller-consistent / URW-high
0.9999
1.00
99.70
Adult
Waller-inconsistent / URW-low
0.0383
0.00
0.01
COMPAS
Waller-consistent / URW-high
0.9613
1.00
99.79
COMPAS
Waller-inconsistent / URW-low
0.2842
0.40
0.14
Appendix
Table 16: Representative instance-level disagreement between Waller-style hard-label consistency and the proposed probability-level diagnostic for k=5 . The cases are selected to illustrate the two possible directions of disagreement rather than to estimate their prevalence.
Figure 7: Sensitivity to neural network depth. We evaluate model performance and fairness across depths 1 , 2 , and 3 on the Employee Salary dataset. Predictive metrics (RMSE and R2 ) remain largely stable, and the mean individual fairness score exhibits consistent trends across architectures. These results indicate that the local predictive-consistency formulation is robust to network depth.
Algorithmic fairness studies how automated decisions distribute errors, opportunities, and harms across groups, and how to measure and reduce disparities.