Spectral Relaxations and Fair Densest Subgraphs

What is it about?

Reducing hidden bias in the data and ensuring fairness in algorithmic data analysis has recently received significant attention. In this paper, we address the problem of identifying a densest subgraph, while ensuring that none of one or more categorical attributes is disparately impacted.

Featured Image

Why is it important?

Enforcing fairness constraints makes this problem NP-hard, even in its approximation version. Despite such negative premises, we are able to provide approximation results in the case of binary attributes in two important cases. In particular, we are able to prove that a suitable spectral embedding allows recovery of an almost optimal, fair, dense subgraph, whenever one is present, a result that is further supported by experimental evidence. We also show a polynomial time, $2$-approximation algorithm, whenever the underlying graph is itself fair. We finally prove that, under the small set expansion hypothesis, this result is tight for fair graphs.

Perspectives