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.
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.
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.
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.
The paper tackles fair correlation clustering with new algorithms and analysis.
problem Fair variants of correlation clustering under various constraints.
method Introducing a novel combinatorial optimization problem for fairlet decomposition.
result Approximation algorithms for fair correlation clustering under multiple fairness constraints.
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…
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…
The paper tackles fair correlation clustering with fairness constraints.
problem Minimizing disagreements while adhering to fairness constraints for clustering.
method Two variants of fairness constraints are considered: equal distribution and relative bounds. Approximation algorithms are developed for these constraints.
result Approximation algorithms for fair correlation clustering with theoretical guarantees and empirical validation.
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.
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.
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.
FairDrop improves fairness in graph representation learning by counteracting homophily.
problem Ensuring fairness in graph representation learning, especially in scenarios with protected attributes.
method Proposes a biased edge dropout algorithm (FairDrop) to counteract homophily and improve fairness.
result Successfully improves fairness in all models up to a small or negligible drop in accuracy.
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.
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.
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. Algorithm provides fair clustering guarantees for k-means and k-median.
problem Ensuring fair clustering guarantees for every point in a dataset.
method Local search algorithm for k-median and k-means, with individual fairness as a key metric. result Achieves fair clustering with a constant factor approximation of the optimal solution.
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 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.
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.
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.
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 …
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.
FairGP uses graph partitioning to make Graph Transformers fair and scalable.
problem Fairness issues in Graph Transformers, especially against sensitive features.
method Graph partitioning to minimize the influence of higher-order nodes and optimize attention mechanisms.
result FairGP improves fairness in Graph Transformers while reducing computational complexity.
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…
FATE framework attacks graph learning models to amplify bias deceptively.
problem Achieving poisoning attacks on graph learning models to exacerbate bias deceptively.
method Bi-level optimization problem and meta learning-based framework named FATE.
result FATE amplifies bias of graph neural networks while maintaining downstream task utility.
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.
FairDTD improves fairness in GNNs by distilling dual teacher knowledge, balancing utility and bias.
problem Bias in GNN predictions due to sensitive attributes.
method Dual-Teacher Distillation with a causal graph model, feature and structure teachers, and graph-level distillation.
result Achieves optimal fairness while preserving high model utility.
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…
Fairness-aware diffusion for graph neural networks
problem Fairness in graph neural networks
method Adapting diffusion process with fairness-aware modifications
result Improves fairness metrics with minimal additional cost
Post-processing corrects bias in ML systems without retraining.
problem Correcting bias in ML systems that are already in use.
method Proposes general post-processing algorithms for individual fairness based on graph Laplacian regularization.
result Empirically, post-processing algorithms correct individual biases in large-scale NLP models while preserving accuracy.
Paper tackles fairness issues in GNNs by proposing ELEGANT for certification.
problem Fairness issues in GNN predictions due to graph data perturbations.
method Proposes ELEGANT framework for certifying fairness of any GNN without assumptions or re-training.
result The fairness of any GNN backbone is impossible to be corrupted under certain perturbation budgets.