# Incorporating Fairness in Neighborhood Graphs for Fair Spectral Clustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 53 references that are in the map.
- First posted on arXiv 10 Dec 2025.

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

- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [Guarantees for Spectral Clustering with Fairness Constraints](https://mlsanity.com/paper/1901.08668/) (2019)
- [FairDrop: Biased Edge Dropout for Enhancing Fairness in Graph Representation Learning](https://mlsanity.com/paper/2104.14210/) (2021)
- [Algorithmic Fairness Datasets: the Story so Far](https://mlsanity.com/paper/2202.01711/) (2022)
- [On the cost of essentially fair clusterings](https://mlsanity.com/paper/1811.10319/) (2018)
- [Fairness in Risk Assessment Instruments: Post-Processing to Achieve Counterfactual Equalized Odds](https://mlsanity.com/paper/2009.02841/) (2020)
- [Robust Graph Learning from Noisy Data](https://mlsanity.com/paper/1812.06673/) (2018)
- [Structured Graph Learning for Scalable Subspace Clustering: From Single-view to Multi-view](https://mlsanity.com/paper/2102.07943/) (2021)
- [Fair Hierarchical Clustering](https://mlsanity.com/paper/2006.10221/) (2020)
- [Fair Representation: Guaranteeing Approximate Multiple Group Fairness for Unknown Tasks](https://mlsanity.com/paper/2109.00545/) (2021)
- [Scalable Spectral Clustering with Group Fairness Constraints](https://mlsanity.com/paper/2210.16435/) (2022)
- [CDC: A Simple Framework for Complex Data Clustering](https://mlsanity.com/paper/2403.03670/) (2024)
- [Fair Algorithms for Hierarchical Agglomerative Clustering](https://mlsanity.com/paper/2005.03197/) (2020)
- [Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions](https://mlsanity.com/paper/2105.03714/) (2021)
- [A Stochastic Alternating Balance k-Means Algorithm for Fair Clustering](https://mlsanity.com/paper/2105.14172/) (2021)
- [Fair Clustering with Multiple Colors](https://mlsanity.com/paper/2002.07892/) (2020)
- [Generalized Disparate Impact for Configurable Fairness Solutions in ML](https://mlsanity.com/paper/2305.18504/) (2023)
- [Data mining for censored time-to-event data: A Bayesian network model for predicting cardiovascular risk from electronic health record data](https://mlsanity.com/paper/1404.2189/) (2014)

## Abstract (arXiv)

Graph clustering plays a pivotal role in unsupervised learning methods like spectral clustering, yet traditional methods for graph clustering often perpetuate bias through unfair graph constructions that may underrepresent some groups. The current research introduces novel approaches for constructing fair k-nearest neighbor (kNN) and fair epsilon-neighborhood graphs that proactively enforce demographic parity during graph formation. By incorporating fairness constraints at the earliest stage of neighborhood selection steps, our approaches incorporate proportional representation of sensitive features into the local graph structure while maintaining geometric consistency.Our work addresses a critical gap in pre-processing for fair spectral clustering, demonstrating that topological fairness in graph construction is essential for achieving equitable clustering outcomes. Widely used graph construction methods like kNN and epsilon-neighborhood graphs propagate edge based disparate impact on sensitive groups, leading to biased clustering results. Providing representation of each sensitive group in the neighborhood of every node leads to fairer spectral clustering results because the topological features of the graph naturally reflect equitable group ratios. This research fills an essential shortcoming in fair unsupervised learning, by illustrating how topological fairness in graph construction inherently facilitates fairer spectral clustering results without the need for changes to the clustering algorithm itself. Thorough experiments on three synthetic datasets, seven real-world tabular datasets, and three real-world image datasets prove that our fair graph construction methods surpass the current baselines in graph clustering tasks.