# Investigating the Effect of k-NN Preprocessing on Developing Graph Neural Networks: A Fairness-Based Perspective

arXiv: https://arxiv.org/abs/2609.33416 · HTML: https://mlsanity.com/paper/2609.33416/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 19 references that are in the map.
- First posted on arXiv 27 Sep 2026.

## Builds on (most cited first, 10 of 10)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications](https://mlsanity.com/paper/1709.07604/) (2017)
- [Learning Fair Representations for Recommendation: A Graph-based Perspective](https://mlsanity.com/paper/2102.09140/) (2021)
- [FNNC: Achieving Fairness through Neural Networks](https://mlsanity.com/paper/1811.00247/) (2018)
- [Challenges and Opportunities in Deep Reinforcement Learning with Graph Neural Networks: A Comprehensive review of Algorithms and Applications](https://mlsanity.com/paper/2206.07922/) (2022)
- [Fair Attribute Completion on Graph with Missing Attributes](https://mlsanity.com/paper/2302.12977/) (2023)
- [Optimizing k in kNN Graphs with Graph Learning Perspective](https://mlsanity.com/paper/2401.08245/) (2024)

## Abstract (arXiv)

In this paper, a methodology to design fair graph convolutional neural networks (GCNs) is developed and tested over several application data sets. The graphs that are used as inputs to the network are constructed by a k-nearest neighbor-based preprocessing procedure, while fairness issues are considered in terms of the equalized odds criterion. To effectively incorporate the above heterogenous information, the equalized odds criterion is directly embedded into the model's optimization objective through an additional fairness-driven loss functional term. The proposed methodology investigates how varying the neighborhood size in the k-NN algorithm during graph construction influences both the classification performance and the fairness of the resulting models. Extensive experimentation is conducted on three real-world tabular datasets with known biases, evaluating the interplay between graph structure and fairness enforcement. The results demonstrate that the choice of the value of the parameter k critically impacts the performance trends, either steadily improving or peaking at intermediate values depending on dataset characteristics, while the application of fairness constraints significantly mitigates disparities in false positive and false negative rates across groups defined by the protected variable at hand, without incurring major sacrifices in overall accuracy. This study highlights the importance of jointly optimizing the graph construction process and fairness objectives in GCN-based learning, providing a systematic approach toward building more equitable and effective graph-based models.