  This paper addresses the problem of learning fair Graph Neural Networks
(GNNs) under missing protected attributes. GNNs have achieved state-of-the-art
results in many relevant tasks where decisions might disproportionately impact
specific communities. However, existing work on fair GNNs assumes that either
protected attributes are fully-observed or that the missing data imputation is
fair. In practice, biases in the imputation will be propagated to the model
outcomes, leading them to overestimate the fairness of their predictions. We
address this challenge by proposing Better Fair than Sorry (BFtS), a fair
missing data imputation model for protected attributes used by fair GNNs. The
key design principle behind BFtS is that imputations should approximate the
worst-case scenario for the fair GNN -- i.e. when optimizing fairness is the
hardest. We implement this idea using a 3-player adversarial scheme where two
adversaries collaborate against the fair GNN. Experiments using synthetic and
real datasets show that BFtS often achieves a better fairness $\times$ accuracy
trade-off than existing alternatives.
