Improved Approximation for Fair Correlation Clustering

• URL: http://arxiv.org/abs/2206.05050v1
• Date: Thu, 9 Jun 2022 03:07:57 GMT
• Title: Improved Approximation for Fair Correlation Clustering
• Authors: Sara Ahmadian and Maryam Negahbani
• Abstract summary: Correlation clustering is a ubiquitous paradigm in unsupervised machine learning where addressing unfairness is a major challenge. Motivated by this, we study Fair Correlation Clustering where the data points may belong to different protected groups. Our paper significantly generalizes and improves on the quality guarantees of previous work of Ahmadi et al. and Ahmadian et al.
• Score: 4.629694186457133
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Correlation clustering is a ubiquitous paradigm in unsupervised machine learning where addressing unfairness is a major challenge. Motivated by this, we study Fair Correlation Clustering where the data points may belong to different protected groups and the goal is to ensure fair representation of all groups across clusters. Our paper significantly generalizes and improves on the quality guarantees of previous work of Ahmadi et al. and Ahmadian et al. as follows. - We allow the user to specify an arbitrary upper bound on the representation of each group in a cluster. - Our algorithm allows individuals to have multiple protected features and ensure fairness simultaneously across them all. - We prove guarantees for clustering quality and fairness in this general setting. Furthermore, this improves on the results for the special cases studied in previous work. Our experiments on real-world data demonstrate that our clustering quality compared to the optimal solution is much better than what our theoretical result suggests.

Related papers

• Uniting contrastive and generative learning for event sequences models [51.547576949425604]
  This study investigates the integration of two self-supervised learning techniques - instance-wise contrastive learning and a generative approach based on restoring masked events in latent space. Experiments conducted on several public datasets, focusing on sequence classification and next-event type prediction, show that the integrated method achieves superior performance compared to individual approaches.
  arXiv  Detail & Related papers  (2024-08-19T13:47:17Z)
• Robust Fair Clustering with Group Membership Uncertainty Sets [31.29773979737976]
  We study the canonical fair clustering problem where each cluster is constrained to have close to population-level representation of each group. We introduce a simple noise model that requires a small number of parameters to be given by the decision maker. We present an algorithm for fair clustering with provable emphrobustness guarantees.
  arXiv  Detail & Related papers  (2024-06-02T03:11:31Z)
• Fair Labeled Clustering [28.297893914525517]
  We consider the downstream application of clustering and how group fairness should be ensured for such a setting. We provide algorithms for such problems and show that in contrast to their NP-hard counterparts in group fair clustering, they permit efficient solutions. We also consider a well-motivated alternative setting where the decision-maker is free to assign labels to the clusters regardless of the centers' positions in the metric space.
  arXiv  Detail & Related papers  (2022-05-28T07:07:12Z)
• Repairing Regressors for Fair Binary Classification at Any Decision Threshold [8.322348511450366]
  We show that we can increase fair performance across all thresholds at once. We introduce a formal measure of Distributional Parity, which captures the degree of similarity in the distributions of classifications for different protected groups. Our main result is to put forward a novel post-processing algorithm based on optimal transport, which provably maximizes Distributional Parity.
  arXiv  Detail & Related papers  (2022-03-14T20:53:35Z)
• Efficient Algorithms For Fair Clustering with a New Fairness Notion [5.21410307583181]
  We revisit the problem of fair clustering, first introduced by Chierichetti et al. Existing solutions to fair clustering are either not scalable or do not achieve an optimal trade-off between clustering objective and fairness. We propose a new notion of fairness, which we call $tau$-fair fairness, that strictly generalizes the balance property and enables a fine-grained efficiency vs. fairness trade-off.
  arXiv  Detail & Related papers  (2021-09-02T04:52:49Z)
• You Never Cluster Alone [150.94921340034688]
  We extend the mainstream contrastive learning paradigm to a cluster-level scheme, where all the data subjected to the same cluster contribute to a unified representation. We define a set of categorical variables as clustering assignment confidence, which links the instance-level learning track with the cluster-level one. By reparametrizing the assignment variables, TCC is trained end-to-end, requiring no alternating steps.
  arXiv  Detail & Related papers  (2021-06-03T14:59:59Z)
• Deep Fair Discriminative Clustering [24.237000220172906]
  We study a general notion of group-level fairness for binary and multi-state protected status variables (PSVs) We propose a refinement learning algorithm to combine the clustering goal with the fairness objective to learn fair clusters adaptively. Our framework shows promising results for novel clustering tasks including flexible fairness constraints, multi-state PSVs and predictive clustering.
  arXiv  Detail & Related papers  (2021-05-28T23:50:48Z)
• MultiFair: Multi-Group Fairness in Machine Learning [52.24956510371455]
  We study multi-group fairness in machine learning (MultiFair) We propose a generic end-to-end algorithmic framework to solve it. Our proposed framework is generalizable to many different settings.
  arXiv  Detail & Related papers  (2021-05-24T02:30:22Z)
• Fair Hierarchical Clustering [92.03780518164108]
  We define a notion of fairness that mitigates over-representation in traditional clustering. We show that our algorithms can find a fair hierarchical clustering, with only a negligible loss in the objective.
  arXiv  Detail & Related papers  (2020-06-18T01:05:11Z)
• Learning to Cluster Faces via Confidence and Connectivity Estimation [136.5291151775236]
  We propose a fully learnable clustering framework without requiring a large number of overlapped subgraphs. Our method significantly improves clustering accuracy and thus performance of the recognition models trained on top, yet it is an order of magnitude more efficient than existing supervised methods.
  arXiv  Detail & Related papers  (2020-04-01T13:39:37Z)
• Robust Optimization for Fairness with Noisy Protected Groups [85.13255550021495]
  We study the consequences of naively relying on noisy protected group labels. We introduce two new approaches using robust optimization. We show that the robust approaches achieve better true group fairness guarantees than the naive approach.
  arXiv  Detail & Related papers  (2020-02-21T14:58:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.