Principal Fairness: Removing Bias via Projections

2019/05/31 by Aris Anagnostopoulos, Anagnostopoulos, Aris, Luca Becchetti +7 · 2 citations
Computer Science · Social Sciences · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Ethics and Social Impacts of AI #FOS: Computer and information sciences #Machine Learning (cs.LG) #Privacy-Preserving Technologies in Data

paper · pdf · doi:10.48550/arxiv.1905.13651

openalex publication_date 2019/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Reducing hidden bias in the data and ensuring fairness in algorithmic data analysis has recently received significant attention. We complement several recent papers in this line of research by introducing a general method to reduce bias in the data through random projections in a "fair" subspace. We apply this method to densest subgraph problem. For densest subgraph, our approach based on fair projections allows to recover both theoretically and empirically an almost optimal, fair, dense subgraph hidden in the input data. We also show that, under the small set expansion hypothesis, approximating this problem beyond a factor of 2 is NP-hard and we show a polynomial time algorithm with a matching approximation bound.

Citations

• Equality of Opportunity in Supervised Learning
• From Parity to Preference-based Notions of Fairness in Classification
• Fair k-Center Clustering for Data Summarization

Cited by

• Coresets for Clustering with Fairness Constraints
• Fairness in Clustering with Multiple Sensitive Attributes

Related

• Efficient Fair Principal Component Analysis
• Fair Densities via Boosting the Sufficient Statistics of Exponential Families
• Fair principal component analysis (PCA): minorization-maximization algorithms for Fair PCA, Fair Robust PCA and Fair Sparse PCA
• On the Fairness ROAD: Robust Optimization for Adversarial Debiasing
• Fairness-Aware Dense Subgraph Discovery