Conference Paper: “Applying Fairness Constraints on Graph Node Ranks Under Personalization Bias”

Emmanouil Krasanakis, Symeon Papadopoulos, and
Ioannis Kompatsiaris
International Conference on Complex Networks and
Their Applications, pp. 610-622. Springer, Cham, 2020


In this work, we address algorithmic fairness concerns that arise when graph nodes are ranked based on their structural relatedness to a personalized set of query ones. In particular, we aim to mitigate the disparate impact, i.e. the difference in average rank between nodes of a sensitive attribute compared to the rest, while also preserving node rank quality. To do this, we introduce a personalization editing mechanism whose parameters can be adjusted to help the ranking algorithm achieve a variety of trade-offs between fairness constraints and rank changes. In experiments across three real-world social graphs and two base ranking algorithms, our approach outperforms baseline and existing methods in uniformly mitigating disparate impact, even when personalization suffers from extreme bias. In particular, it achieves higher trade-offs between fairness and rank quality and manages to preserve most of node rank quality when a constrained amount of disparate impact is allowed.

Keywords: node ranking, personalized ranking, algorithmic fairness, disparate impact mitigation