Multicalibration in Fair Link Prediction

In this work, we expand the multicalibration fairness metric to graph-structured data. Machine learning models, including graph neural networks (GNNs), have been demonstrated to generate unfair results when trained on data containing biases towards certain demographic groups. Consequently, several fairness enhancing methods have been proposed to deal with such biases in the model predictions. To evaluate the performance of these methods, metrics such as demographic parity and equalized odds have been proposed, which aim to ensure equal treatment across groups. However, these metrics do not take into consideration the diverse underlying distribution of the data across the different demographic groups. Hence, fairness is only achieved at the cost of utility. Multicalibration, on the other hand, aims to generate calibrated predictions for each group, thereby providing much stronger fairness guarantees. However, multicalibration is only defined for tabular data. Consequently, in this work, we provide a novel formulation of multicalibration fairness metric for graph-structured data, specifically for the task of link prediction. We demonstrate that the existing fairness enhancing methods are unable to achieve multicalibration, which leads us to define a simple quadratic program-based postprocessing method. Experiments across several real-world datasets demonstrate the effectiveness of our method, consistently outperforming the existing approaches. Our method is model agnostic and can seamlessly adapt to scenarios with single or multiple sensitive attributes.