# Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 58 references that are in the map.
- First posted on arXiv 8 May 2021.

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

- [Fairness in Machine Learning: A Survey](https://mlsanity.com/paper/2010.04053/) (2020)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Guarantees for Spectral Clustering with Fairness Constraints](https://mlsanity.com/paper/1901.08668/) (2019)
- [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019)
- [Individual Fairness for k-Clustering](https://mlsanity.com/paper/2002.06742/) (2020)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Clustering without Over-Representation](https://mlsanity.com/paper/1905.12753/) (2019)
- [On the cost of essentially fair clusterings](https://mlsanity.com/paper/1811.10319/) (2018)
- [Achieving Optimal Misclassification Proportion in Stochastic Block Model](https://mlsanity.com/paper/1505.03772/) (2015)
- [Layer aggregation and reducibility of multilayer interconnected networks](https://mlsanity.com/paper/1405.0425/) (2014)
- [Covariate-assisted spectral clustering](https://mlsanity.com/paper/1411.2158/) (2014)
- [Probabilistic Fair Clustering](https://mlsanity.com/paper/2006.10916/) (2020)
- [Consistency of Spectral Hypergraph Partitioning under Planted Partition Model](https://mlsanity.com/paper/1505.01582/) (2015)
- [Detecting Overlapping Communities in Networks Using Spectral Methods](https://mlsanity.com/paper/1412.3432/) (2014)
- [A simple SVD algorithm for finding hidden partitions](https://mlsanity.com/paper/1404.3918/) (2014)
- [Distributional Individual Fairness in Clustering](https://mlsanity.com/paper/2006.12589/) (2020)
- [Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques](https://mlsanity.com/paper/1602.06516/) (2016)
- [Compressive Spectral Clustering](https://mlsanity.com/paper/1602.02018/) (2016)
- [Fair Coresets and Streaming Algorithms for Fair k-Means Clustering](https://mlsanity.com/paper/1812.10854/) (2018)
- [KFC: A Scalable Approximation Algorithm for k-center Fair Clustering](https://mlsanity.com/paper/2010.13949/) (2020)
- [A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models](https://mlsanity.com/paper/1411.1469/) (2014)

## Built on by (most cited first, 10 of 10)

- [Scalable Spectral Clustering with Group Fairness Constraints](https://mlsanity.com/paper/2210.16435/) (2022)
- [Doubly Constrained Fair Clustering](https://mlsanity.com/paper/2305.19475/) (2023)
- [Towards Cohesion-Fairness Harmony: Contrastive Regularization in Individual Fair Graph Clustering](https://mlsanity.com/paper/2402.10756/) (2024)
- [Spectral Normalized-Cut Graph Partitioning with Fairness Constraints](https://mlsanity.com/paper/2307.12065/) (2023)
- [A Note on Bias to Complete](https://mlsanity.com/paper/2402.11710/) (2024)
- [A Semidefinite Relaxation Approach for Fair Graph Clustering](https://mlsanity.com/paper/2410.15233/) (2024)
- [Estimating Fair Graphs from Graph-Stationary Data](https://mlsanity.com/paper/2510.07536/) (2025)
- [A Deep Latent Factor Graph Clustering with Fairness-Utility Trade-off Perspective](https://mlsanity.com/paper/2510.23507/) (2025)
- [Incorporating Fairness in Neighborhood Graphs for Fair Spectral Clustering](https://mlsanity.com/paper/2512.09810/) (2025)
- [Fairness-Aware Network Embeddings: Methods, Applications, and Challenges](https://mlsanity.com/paper/2608.19381/) (2026)

## Abstract (arXiv)

Spectral clustering is popular among practitioners and theoreticians alike. While performance guarantees for spectral clustering are well understood, recent studies have focused on enforcing ``fairness'' in clusters, requiring them to be ``balanced'' with respect to a categorical sensitive node attribute (e.g. the race distribution in clusters must match the race distribution in the population). In this paper, we consider a setting where sensitive attributes indirectly manifest in an auxiliary textitrepresentation graph rather than being directly observed. This graph specifies node pairs that can represent each other with respect to sensitive attributes and is observed in addition to the usual textitsimilarity graph. Our goal is to find clusters in the similarity graph while respecting a new individual-level fairness constraint encoded by the representation graph. We develop variants of unnormalized and normalized spectral clustering for this task and analyze their performance under a fair planted partition model induced by the representation graph. This model uses both the cluster membership of the nodes and the structure of the representation graph to generate random similarity graphs. To the best of our knowledge, these are the first consistency results for constrained spectral clustering under an individual-level fairness constraint. Numerical results corroborate our theoretical findings.