mlsanityData to 7 Oct 2026

Guarantees for Spectral Clustering with Fairness Constraints

arXiv 1901.08668 ↗First posted 24 Jan 2019stat.ML cs.DS cs.LGcited by 72

Not on the map. Why?

Abstract (arXiv)

Given the widespread popularity of spectral clustering (SC) for partitioning graph data, we study a version of constrained SC in which we try to incorporate the fairness notion proposed by Chierichetti et al. (2017). According to this notion, a clustering is fair if every demographic group is approximately proportionally represented in each cluster. To this end, we develop variants of both normalized and unnormalized constrained SC and show that they help find fairer clusterings on both synthetic and real data. We also provide a rigorous theoretical analysis of our algorithms on a natural variant of the stochastic block model, where h groups have strong inter-group connectivity, but also exhibit a "natural" clustering structure which is fair. We prove that our algorithms can recover this fair clustering with high probability.

Key facts. Cited by 72 papers in the map (data through 7 Oct 2026). First posted on arXiv 24 Jan 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 17; 2023: 15; 2024: 8; 2025: 14; 2026: 6.

72 papers.

Sort:

By area:

  1. 2022Fairness in Graph Mining: A Surveycited by 76
  2. 2022FairGRAPE: Fairness-aware GRAdient Pruning mEthod for Face Attribute Classificationcited by 30
  3. 2023Inductive Graph Unlearningcited by 30
  4. 2022RawlsGCN: Towards Rawlsian Difference Principle on Graph Convolutional Networkcited by 27
  5. 2021A Sociotechnical View of Algorithmic Fairnesscited by 24
  6. 2021Fair Clustering Under a Bounded Costcited by 21
  7. 2022Fairness Amidst Non-IID Graph Data: A Literature Reviewcited by 20
  8. 2022A Survey on Fairness for Machine Learning on Graphscited by 20
  9. 2022Deep Fair Clustering via Maximizing and Minimizing Mutual Information: Theory, Algorithm and Metriccited by 17
  10. 2022Scalable Spectral Clustering with Group Fairness Constraintscited by 16
  11. 2022Robust Fair Clustering: A Novel Fairness Attack and Defense Frameworkcited by 13
  12. 2023FairGen: Towards Fair Graph Generationcited by 12
38 more
  1. 2021Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitionscited by 10
  2. 2021Deep Fair Discriminative Clusteringcited by 10
  3. 2021A Stochastic Alternating Balance k-Means Algorithm for Fair Clusteringcited by 10
  4. 2021Fair Clustering Using Antidote Datacited by 10
  5. 2021Fairness-Aware Unsupervised Feature Selectioncited by 10
  6. 2022Graph Learning with Localized Neighborhood Fairnesscited by 10
  7. 2023Doubly Constrained Fair Clusteringcited by 9
  8. 2022Individual Preference Stability for Clusteringcited by 8
  9. 2023Proportionally Representative Clusteringcited by 8
  10. 2021Pairwise Fairness for Ordinal Regressioncited by 6
  11. 2022FAL-CUR: Fair Active Learning using Uncertainty and Representativeness on Fair Clusteringcited by 6
  12. 2023Fairness-aware Multi-view Clusteringcited by 6
  13. 2021Efficient Algorithms For Fair Clustering with a New Fairness Notioncited by 5
  14. 2021Fairness Degrading Adversarial Attacks Against Clustering Algorithmscited by 5
  15. 2022Emergent specialization from participation dynamics and multi-learner retrainingcited by 5
  16. 2023Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpointcited by 5
  17. 2024Fairness-Aware Estimation of Graphical Modelscited by 5
  18. 2021Feature-based Individual Fairness in k-Clusteringcited by 4
  19. 2022Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Costcited by 4
  20. 2024Towards Cohesion-Fairness Harmony: Contrastive Regularization in Individual Fair Graph Clusteringcited by 4
  21. 2021Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of Them All?cited by 3
  22. 2023A review of clustering models in educational data science towards fairness-aware learningcited by 3
  23. 2023Spectral Normalized-Cut Graph Partitioning with Fairness Constraintscited by 3
  24. 2023Fair Canonical Correlation Analysiscited by 3
  25. 2023A Unified Framework for Fair Spectral Clustering With Effective Graph Learningcited by 3
  26. 2024On Explaining Unfairness: An Overviewcited by 3
  27. 2022Measuring and mitigating voting access disparities: a study of race and polling locations in Florida and North Carolinacited by 1
  28. 2022Towards Auditing Unsupervised Learning Algorithms and Human Processes For Fairnesscited by 1
  29. 2023Fair Clustering via Hierarchical Fair-Dirichlet Processcited by 1
  30. 2023Dual Node and Edge Fairness-Aware Graph Partitioncited by 1
  31. 2023Sanitized Clustering against Confounding Biascited by 1
  32. 2023Fair Clustering: A Causal Perspectivecited by 1
  33. 2024Spectral Clustering of Categorical and Mixed-type Data via Extra Graph Nodescited by 1
  34. 2024Robust Fair Clustering with Group Membership Uncertainty Setscited by 1
  35. 2024Fair Clustering: Critique, Caveats, and Future Directionscited by 1
  36. 2025Fair Clustering via Alignmentcited by 1
  37. 2025A Computational Approach to Improving Fairness in K-means Clusteringcited by 1
  38. 2025Adversarial Fair Multi-View Clusteringcited by 1

50 most cited of 72 All 72 (JSON)