Demographic Parity in Unsupervised Clustering

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2282 papers365 conceptsfrozen 2026-10-04

Traditional clustering algorithms like $k$-means or spectral clustering are designed to find "natural" groupings in data by minimizing spatial distance or maximizing edge density. However, because real-world data often reflects historical or systemic biases, these "natural" groups frequently result in demographic segregation. If a bank clusters its customers to determine loan eligibility, a standard algorithm might inadvertently create clusters that are highly correlated with race or gender, even if those attributes aren't explicitly used as features.

Researchers are developing a new class of "fair" clustering algorithms that treat demographic balance not as a byproduct, but as a fundamental constraint of the optimization problem.

The Geometry of Fairness

The core challenge in fair clustering is the tension between spatial proximity and demographic parity. In a standard $k$-median problem, we want to pick $k$ centers to minimize the distance from every point to its nearest center. In a fair version, we add a constraint: every cluster must approximately reflect the demographic proportions of the entire dataset.

Eric Granger, Imtiaz Masud Ziko, and colleagues in Clustering with Fairness Constraints: A Flexible and Scalable Approach frame this as a variational problem. Instead of a hard "all-or-nothing" constraint, they use a Kullback-Leibler (KL) divergence penalty. This allows the algorithm to "nudge" points into different clusters to achieve balance, providing a tunable knob to trade off clustering quality for demographic representation.

Enforcing Parity in Graphs

When data is represented as a graph—such as a social network or a set of student relationships—fairness becomes a matter of partitioning nodes without creating "echo chambers." Standard spectral clustering works by finding the eigenvectors of a graph's Laplacian matrix, which essentially identifies the "weakest links" to cut.

Matthäus Kleindessner and Jamie Morgenstern showed in Guarantees for Spectral Clustering with Fairness Constraints that this can be solved by adding linear constraints to the cluster indicator matrix. By requiring that the ratio of sensitive groups in each cluster matches the global distribution, they transform the problem into a constrained optimization that can still be solved with spectral methods.

More recently, Sadra Sabouri proposed a Semidefinite Relaxation (SDP) approach for graph clustering. This method ensures that the assignment of a node to a cluster is mathematically uncorrelated with its sensitive demographic attributes, effectively "blinding" the algorithm to those features while it searches for dense communities.

Scaling to Millions of Points

Early fair clustering algorithms were computationally expensive, often requiring complex quadratic programming. To make these ideas practical for large-scale systems like recommendation engines, researchers have focused on speed.

In Scalable Fair Clustering, authors introduced a near-linear time algorithm that embeds data into tree structures (Hierarchically Well-Separated Trees). By decomposing the problem top-down, they scaled fair $k$-median clustering to datasets with millions of points. Similarly, Francesco Tonin recently developed an ADMM-based approach that avoids expensive eigendecompositions, achieving speedups of up to 54x over previous fair spectral methods.

Beyond Simple Groups: Intersectionality and Individual Fairness

Real-world fairness is rarely about a single attribute like "gender." It is often intersectional, involving combinations like "Black women" or "elderly veterans." Jack Fitzsimons and Michael A. Osborne addressed this in Intersectionality: Multiple Group Fairness in Expectation Constraints by applying post-training updates to model leaves, ensuring that expected outcomes are equalized across all intersecting demographic subgroups.

While most work focuses on group fairness (proportional representation), Kamesh Munagala and Govind S. Sankar have pushed toward individual fairness. In Individual Fairness in Graph Decomposition, they argue that nodes at similar distances in a graph should have a similar probability of being separated into different clusters. This ensures that the algorithm doesn't just meet a "quota" for a group, but treats similar individuals equitably.

Generative and Bayesian Perspectives

Moving away from pure optimization, some researchers are building fairness directly into the data-generation process. Abhisek Chakraborty and colleagues developed the Hierarchical Fair-Dirichlet Process (HFDP). This Bayesian framework uses a "lifted" prior to ensure that as the model discovers clusters, it is statistically forced to keep them demographically balanced. This approach is particularly robust when demographic labels are noisy or the number of clusters is unknown.

Papers in this version

Showing 60 of 282 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 142 papers
  2. Version 1 · 2026-10-04 · 282 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_demographic_representation_bias_demograp_6c98f114,
  title = {demographic representation bias (demographic bias in clustering)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/demographic-representation-bias-demographic-bias-in-clustering/rdr_6c98f11479a54cf080b0df021ecdc77f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_demographic_parity_in_unsupervised_clust_6c98f114_v1,
  title = {Demographic Parity in Unsupervised Clustering},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/demographic-parity-in-unsupervised-clustering/rdr_6c98f11479a54cf080b0df021ecdc77f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}