A Comparative Analysis of Graph Construction Methods for Fairness in Graph-Based Semi-Supervised Learning - Oliveira, Willian Dihanster Gomes de; Berton, Lilian (Anais do Encontro Nacional de Inteligência Artificial e Computacional (ENIAC); 2025: Anais do XXII Encontro Nacional de Inteligência Artificial e Computacional, 2025)
Graph-based semi-supervised learning (GSSL) relies on the quality of the input graph, often constructed from tabular data. We compare KNN, Mutual KNN (M-KNN), and Sequential KNN (S-KNN) on fairness benchmark datasets. While KNN achieves the highest AUC-ROC, M-KNN and S-KNN, which promote more balanced degree distributions, yield fairer outcomes as measured by Disparate Impact and Average Absolute Odds Difference, with only a small loss in AUC-ROC. Additionally, our analysis reveals that degree disparities between protected groups are linked to unfair outcomes, and that more balanced connectivity can mitigate these effects, highlighting the importance of fairness-aware graph construction in GSSL.