  Graph representation learning has become a ubiquitous component in many
scenarios, ranging from social network analysis to energy forecasting in smart
grids. In several applications, ensuring the fairness of the node (or graph)
representations with respect to some protected attributes is crucial for their
correct deployment. Yet, fairness in graph deep learning remains
under-explored, with few solutions available. In particular, the tendency of
similar nodes to cluster on several real-world graphs (i.e., homophily) can
dramatically worsen the fairness of these procedures. In this paper, we propose
a novel biased edge dropout algorithm (FairDrop) to counter-act homophily and
improve fairness in graph representation learning. FairDrop can be plugged in
easily on many existing algorithms, is efficient, adaptable, and can be
combined with other fairness-inducing solutions. After describing the general
algorithm, we demonstrate its application on two benchmark tasks, specifically,
as a random walk model for producing node embeddings, and to a graph
convolutional network for link prediction. We prove that the proposed algorithm
can successfully improve the fairness of all models up to a small or negligible
drop in accuracy, and compares favourably with existing state-of-the-art
solutions. In an ablation study, we demonstrate that our algorithm can flexibly
interpolate between biasing towards fairness and an unbiased edge dropout.
Furthermore, to better evaluate the gains, we propose a new dyadic group
definition to measure the bias of a link prediction task when paired with
group-based fairness metrics. In particular, we extend the metric used to
measure the bias in the node embeddings to take into account the graph
structure.
