Principal Fairness: Removing Bias via Projections
This addresses fairness in data analysis for domains like social networks or recommendation systems, but it is incremental as it builds on existing bias reduction research.
The paper tackles bias reduction in algorithmic data analysis by introducing a method using random projections in a fair subspace, applied to the densest subgraph problem, achieving an almost optimal fair dense subgraph with theoretical and empirical results, including a polynomial-time algorithm with a matching approximation bound under computational hardness assumptions.
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.