FCA improves fair clustering by optimizing utility and fairness.
problem Balancing fairness and utility in clustering.
method FCA alternates between aligning data and optimizing cluster centers in an aligned space.
result FCA achieves a superior trade-off between fairness and utility.
Proposes individual fairness for clustering, making data points prefer their own cluster.
problem No fair clustering for clustering data points.
method Introduces a new fairness notion for clustering and studies its feasibility and heuristics.
result Individual fairness for clustering is NP-hard in general but feasible for one-dimensional data.
FBC clusters data fairly without needing cluster count.
problem Fairness in clustering groups of different sensitive groups.
method Developed a Bayesian model-based clustering method with a fair prior and efficient MCMC algorithm.
result Reasonably infers the number of clusters and achieves a fair utility trade-off.
A clustering may be considered as fair on pre-specified sensitive attributes if the proportions of sensitive attribute groups in each cluster reflect that in the dataset. In this paper, we consider the task of fair clustering for scenarios involving multiple multi-valued or numeric sensitive attributes. We propose a fa…
Improves clustering fairness by learning fair clusters adaptively.
problem Fairness in deep clustering, especially for protected status variables.
method Formulates group-level fairness as ILP, integrates into discriminative deep clustering, refines learning algorithm.
result Consistently outperforms fair clustering algorithms on real-world datasets.
Algorithm identifies intended fairness constraints from expert demonstrations for fair clustering.
problem Fair clustering challenges due to incomplete fairness constraints.
method Algorithm identifies fairness metric from expert demonstrations and generates clusters.
result Algorithm identifies and generates fair clusters from limited expert demonstrations.
New model for fair clustering ensures balanced representation of protected attributes.
problem Ensuring fair representation in clustering for protected attributes.
method Model-based formulation of fair clustering, balancing protected attributes across clusters.
result Demonstrates improved fairness in clustering through a new model.
The paper explores fair clustering, a niche area in machine learning.
problem Fairness in clustering remains underexplored despite its importance.
method Assesses existing work and proposes new directions for fair clustering.
result Widening normative principles and knowledge of downstream processes can enhance fair clustering research.
Fair HAC algorithms ensure clustering fairness across protected groups.
problem Ensuring clustering fairness in HAC algorithms when datasets contain biases.
method Proposes fair algorithms for HAC that enforce fairness constraints regardless of distance linkage criteria.
result Our fair HAC algorithms find fairer clusterings compared to vanilla HAC and other fair clustering approaches.
Proposes FMC for fair clustering with independent parameters.
problem Finding clusters with balanced sensitive attribute proportions.
method Model-based clustering using finite mixture model with mini-batch learning.
result FMC scales up easily and can handle non-metric data.
New clustering method considers causal fairness to avoid bias.
problem Clustering algorithms can unintentionally propagate unfair disparities.
method Integrates causal fairness metrics into clustering algorithms.
result Demonstrates efficacy on datasets with known unfair biases.
The paper extends fairness to hierarchical clustering, finding efficient algorithms with minimal loss.
problem Ensuring fairness in hierarchical clustering where data is recursively partitioned.
method Extending fairness to hierarchical clustering, developing simple, efficient algorithms for various objectives.
result Simple, efficient algorithms for fair hierarchical clustering with only a negligible loss in objective.
A new algorithm COVA-FC improves subgroup-fair clustering efficiency.
problem Challenges in making cluster assignments independent of sensitive attributes in subgroups.
method Defining a subgroup-fairness gap, deriving a covariance-based surrogate, and introducing a continuous relaxation for efficient optimization.
result COVA-FC achieves competitive cost-fairness trade-offs and improves computational efficiency.
This paper introduces individual fairness in clustering using f-divergence.
problem Ensuring fair clustering by treating similar individuals similarly.
method Uses f-divergence to measure statistical similarity and assigns individuals to probability distributions over cluster centers. result Provides an algorithm with provable approximation guarantee for clustering with individual fairness constraints.
New clustering method ensures fairness and community preservation.
problem Fairness in clustering, especially for data points representing people.
method Developed an approach to extend k-center algorithms to satisfy pairwise fairness and community preservation. result Reasonable approximations of optimal clustering can be achieved while maintaining fairness.
The paper introduces group-representative clustering to ensure fair representation of different groups in clusters.
problem Ensuring fair representation of different groups in clusters.
method Developed a new clustering approach called group-representative clustering, which parallels fairness notions in classification.
result Presented approximation algorithms for group representative k-median clustering and evaluated on real-world data. In this paper, we study correlation clustering under fairness constraints. Fair variants of k-median and k-center clustering have been studied recently, and approximation algorithms using a notion called fairlet decomposition have been proposed. We obtain approximation algorithms for fair correlation clustering und…
We study the question of fair clustering under the {\em disparate impact} doctrine, where each protected class must have approximately equal representation in every cluster. We formulate the fair clustering problem under both the k-center and the k-median objectives, and show that even with two protected classes th…
New approach for fair graph clustering using semidefinite relaxation.
problem Ensuring equitable representation in network analysis.
method Semidefinite relaxation approach for NP-hard optimization problem.
result Optimal accuracy-fairness trade-off achieved.
We propose a general variational framework of fair clustering, which integrates an original Kullback-Leibler (KL) fairness term with a large class of clustering objectives, including prototype or graph based. Fundamentally different from the existing combinatorial and spectral solutions, our variational multi-term appr…
New algorithm speeds up fair clustering by 12x.
problem Achieving fair clustering in scalable algorithms.
method s-FairSC algorithm incorporating nullspace projection and Hotelling's deflation.
result s-FairSC is 12x faster and maintains fairness.
Consistent spectral clustering with fairness constraints on representation graphs.
problem Finding balanced clusters in similarity graphs with fairness constraints.
method Developed variants of unnormalized and normalized spectral clustering for fair planted partitions.
result Consistency results for constrained spectral clustering under fair planted partitions.
Develops a fair clustering algorithm for datasets with outliers.
problem Fair clustering with outliers in datasets.
method Solves a linear program to identify and exclude outliers, then applies a rounding algorithm to find fair centers.
result Guaranteed approximation of fair radius and clustering cost.
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 proportional…
Fair k-means algorithm ensures equitable costs for different groups.
problem K-means clustering can result in biased outcomes for subgroups of data.
method Presented a fair k-means objective and algorithm (Fair-Lloyd) to choose cluster centers that provide equitable costs for different groups.
result Fair-Lloyd algorithm ensures all groups have equal costs in the output k-clustering, with negligible increase in running time.
Probabilistic fair clustering tackles uncertain group membership.
problem Fair clustering with imperfect group membership.
method Probabilistic algorithms for metric graphs and metric membership.
result Approximation ratio guarantees for fair clustering.
Fair clustering under the disparate impact doctrine requires that population of each protected group should be approximately equal in every cluster. Previous work investigated a difficult-to-scale pre-processing step for k-center and k-median style algorithms for the special case of this problem when the number of …
Framework achieves fairness in predictions using partially known causal graph over clusters of variables.
problem Achieving fairness in algorithmic decisions when causal graph knowledge is limited.
method Leverages a causal graph over clusters of variables to train a prediction model, reducing interventional distribution discrepancies.
result Framework strikes a better balance between fairness and accuracy than existing approaches under limited causal graph knowledge.
We give a local search based algorithm for k-median and k-means (and more generally for any k-clustering with ℓp norm cost function) from the perspective of individual fairness. More precisely, for a point x in a point set P of size n, let r(x) be the minimum radius such that the ball of radius $r(x…
A new framework improves fairness in clustering and Wasserstein Barycenter problems.
problem Fair clustering in datasets with multiple groups.
method Relax and Merge framework for (1+4ρ+O(ε))-approximate solutions. result Improved approximation guarantees for fairness constraints.
The paper clusters group fairness metrics and visualizes them using PCA.
problem Measuring discrimination against socio-demographic groups using multiple metrics.
method Empirical observation and PCA visualization of fairness metrics.
result Group fairness metrics cluster into two or three main clusters.
New approach to fairness in machine learning models using conformal prediction.
problem Fairness in machine learning models' downstream decision-making.
method Theoretical derivation and empirical evaluation of label-clustered conformal prediction.
result Label-clustered conformal prediction often provides a favorable balance between utility and substantive fairness.
We consider the problem of diversity enhancing clustering, i.e, developing clustering methods which produce clusters that favour diversity with respect to a set of protected attributes such as race, sex, age, etc. In the context of fair clustering, diversity plays a major role when fairness is understood as demographic…
We extend the fair machine learning literature by considering the problem of proportional centroid clustering in a metric context. For clustering n points with k centers, we define fairness as proportionality to mean that any n/k points are entitled to form their own cluster if there is another center that is clo…
A new algorithm balances fairness in clustering to avoid discrimination.
problem Clustering data can unfairly discriminate against different demographic groups.
method Designing a stochastic alternating balance fair k-means algorithm (SAfairKM) that alternates between k-means updates and group swap updates.
result The algorithm efficiently constructs well-spread and high-quality Pareto fronts on synthetic and real datasets.
In this paper we study the problem of correlation clustering under fairness constraints. In the classic correlation clustering problem, we are given a complete graph where each edge is labeled positive or negative. The goal is to obtain a clustering of the vertices that minimizes disagreements -- the number of negative…
Improved approximation for socially fair clustering with ℓp-objective.
problem Finding a set of centers minimizing the maximum distance to all points in each group.
method Introduced a strengthened LP relaxation with an integrality gap of Θ(loglogℓlogℓ). result Improved approximation algorithm with (eO(p)loglogℓlogℓ)-approximation. In a recent work, [19] studied the following "fair" variants of classical clustering problems such as k-means and k-median: given a set of n data points in Rd and a binary type associated to each data point, the goal is to cluster the points while ensuring that the proportion of each type in each clus…
In data summarization we want to choose k prototypes in order to summarize a data set. We study a setting where the data set comprises several demographic groups and we are restricted to choose ki prototypes belonging to group i. A common approach to the problem without the fairness constraint is to optimize a c…
Meta clustering categorizes learners for collaborative learning.
problem Filtering out unqualified collaborators in collaborative learning.
method Select-Exchange-Cluster (SEC) method to classify learners by their supervised functions.
result SEC can cluster learners into accurate collaboration sets and enhance single-learner performance.
Though there is a growing body of literature on fairness for supervised learning, the problem of incorporating fairness into unsupervised learning has been less well-studied. This paper studies fairness in the context of principal component analysis (PCA). We first present a definition of fairness for dimensionality re…
Machine learning algorithms have been increasingly deployed in critical automated decision-making systems that directly affect human lives. When these algorithms are only trained to minimize the training/test error, they could suffer from systematic discrimination against individuals based on their sensitive attributes…
Paper proposes a method to detect fair communities in graphs considering demographic attributes.
problem Inconsistent community detection violates fairness constraints for nodes with demographic attributes.
method Develops an ℓ1-regularized pseudo-likelihood approach for fair graphical model selection. result The method ensures demographic groups are fairly represented within detected communities.
A new method uses model gradients to improve fairness without relying on demographic data.
problem Algorithmic fairness issues due to missing demographic information and complex interactions.
method Learning a graph of gradients to identify and improve group fairness robustly to noise.
result Significantly improves fairness without sacrificing overall accuracy.
BIND removes background noise from binary matrices, improving detection accuracy and fairness.
problem Real data often violates the i.i.d assumption for binary matrix entries, leading to inaccurate detection.
method BIND optimizes detection by estimating row- and column-wise mixture distributions and eliminating background noise.
result BIND effectively removes background noise and increases detection accuracy and fairness.
Clust-PSI-PFL uses PSI to improve accuracy and fairness in federated learning.
problem Non-IID data biases federated learning performance.
method Clust-PSI-PFL uses clustering and PSI to form homogeneous groups of clients.
result Clust-PSI-PFL delivers up to 18% higher global accuracy and improves client fairness.
New method for fair influence maximization in social networks.
problem Maximizing influence while ensuring fairness across sensitive attributes.
method Co-training an auto-encoder and discriminator to create fair graph embeddings.
result Our method reduces disparity while maintaining competitive influence maximization performance.
FWC creates fair synthetic samples for machine learning tasks.
problem Addressing biases in machine learning models for fair decision-making.
method FWC uses an efficient majority minimization algorithm to minimize Wasserstein distance while enforcing demographic parity.
result FWC achieves a competitive fairness-utility tradeoff and reduces biases in predictions from large language models.