# Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 44 references that are in the map.
- First posted on arXiv 2 Mar 2021.

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

- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [Improving fairness in machine learning systems: What do industry practitioners need?](https://mlsanity.com/paper/1812.05239/) (2018)
- [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)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [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)
- [Probabilistic Fair Clustering](https://mlsanity.com/paper/2006.10916/) (2020)
- [An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization](https://mlsanity.com/paper/1406.2951/) (2014)
- [A Pairwise Fair and Community-preserving Approach to k-Center Clustering](https://mlsanity.com/paper/2007.07384/) (2020)
- [Distributional Individual Fairness in Clustering](https://mlsanity.com/paper/2006.12589/) (2020)
- [A Lottery Model for Center-type Problems With Outliers](https://mlsanity.com/paper/1710.00287/) (2017)
- [Semi-crowdsourced Clustering with Deep Generative Models](https://mlsanity.com/paper/1810.11971/) (2018)
- [Generalized Center Problems with Outliers](https://mlsanity.com/paper/1805.02217/) (2018)

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

- [Fair Clustering Under a Bounded Cost](https://mlsanity.com/paper/2106.07239/) (2021)
- [A New Notion of Individually Fair Clustering: α-Equitable k-Center](https://mlsanity.com/paper/2106.05423/) (2021)
- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)
- [Individual Preference Stability for Clustering](https://mlsanity.com/paper/2207.03600/) (2022)
- [FAL-CUR: Fair Active Learning using Uncertainty and Representativeness on Fair Clustering](https://mlsanity.com/paper/2209.12756/) (2022)
- [Efficient Algorithms For Fair Clustering with a New Fairness Notion](https://mlsanity.com/paper/2109.00708/) (2021)
- [Semi-FairVAE: Semi-supervised Fair Representation Learning with Adversarial Variational Autoencoder](https://mlsanity.com/paper/2204.00536/) (2022)
- [Constant Approximation for Individual Preference Stable Clustering](https://mlsanity.com/paper/2309.16840/) (2023)
- [Near-Optimal Algorithms for Constrained k-Center Clustering with Instance-level Background Knowledge](https://mlsanity.com/paper/2401.12533/) (2024)
- [Fair Clustering: A Causal Perspective](https://mlsanity.com/paper/2312.09061/) (2023)
- [Scalable Algorithms for Individual Preference Stable Clustering](https://mlsanity.com/paper/2403.10365/) (2024)
- [Fair Clustering: Critique, Caveats, and Future Directions](https://mlsanity.com/paper/2406.15960/) (2024)
- [Approximation Algorithm for Constrained k-Center Clustering: A Local Search Approach](https://mlsanity.com/paper/2601.11883/) (2026)
- [A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering](https://mlsanity.com/paper/2405.10378/) (2024)
- [FairAD: Computationally Efficient Fair Graph Clustering via Algebraic Distance](https://mlsanity.com/paper/2510.27136/) (2025)
- [SubQuad: Near-Quadratic-Free Structure Inference with Distribution-Balanced Objectives in Adaptive Receptor framework](https://mlsanity.com/paper/2602.17330/) (2026)
- [Avoiding Structural Failure Modes in Tabular Fair SSL: Online Primal-Dual Allocation under Confidence Gating](https://mlsanity.com/paper/2605.16446/) (2026)

## Abstract (arXiv)

Metric clustering is fundamental in areas ranging from Combinatorial Optimization and Data Mining, to Machine Learning and Operations Research. However, in a variety of situations we may have additional requirements or knowledge, distinct from the underlying metric, regarding which pairs of points should be clustered together. To capture and analyze such scenarios, we introduce a novel family of stochastic pairwise constraints, which we incorporate into several essential clustering objectives (radius/median/means). Moreover, we demonstrate that these constraints can succinctly model an intriguing collection of applications, including among others Individual Fairness in clustering and Must-link constraints in semi-supervised learning. Our main result consists of a general framework that yields approximation algorithms with provable guarantees for important clustering objectives, while at the same time producing solutions that respect the stochastic pairwise constraints. Furthermore, for certain objectives we devise improved results in the case of Must-link constraints, which are also the best possible from a theoretical perspective. Finally, we present experimental evidence that validates the effectiveness of our algorithms.