  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.
