FairRARI: A Plug and Play Framework for Fairness-Aware PageRank

PageRank (PR) is a fundamental algorithm in graph machine learning tasks. Owing to the increasing importance of algorithmic fairness, we consider the problem of computing PR vectors subject to various group-fairness criteria based on sensitive attributes of the vertices. At present, principled algorithms for this problem are lacking - some cannot guarantee that a target fairness level is achieved, while others do not feature optimality guarantees. In order to overcome these shortcomings, we put forth a unified in-processing convex optimization framework, termed FairRARI, for tackling different group-fairness criteria in a ``plug and play'' fashion. Leveraging a variational formulation of PR, the framework computes fair PR vectors by solving a strongly convex optimization problem with fairness constraints, thereby ensuring that a target fairness level is achieved. We further introduce three different fairness criteria which can be efficiently tackled using FairRARI to compute fair PR vectors with the same asymptotic time-complexity as the original PR algorithm. Extensive experiments on real-world datasets showcase that FairRARI outperforms existing methods in terms of utility, while achieving the desired fairness levels across multiple vertex groups; thereby highlighting its effectiveness.

PageRank is a foundational algorithm for identifying important nodes in large social networks. The algorithm allocates each node an importance score by performing random walks. However, the results can amplify structural biases in the network to marginalise specific demographic subgroups. Existing solutions frequently fall short, either failing to meet fairness targets or sacrificing far more accuracy than necessary to achieve them. To address this, we developed FairRARI, a "plug and play" framework designed to bake fairness directly into the algorithmic process. It allows developers to set specific fairness goals - such as ensuring different demographic groups get equal visibility - and uses a rigorous mathematical approach to guarantee those goals are actually met. FairRARI outperforms previous methods by satisfying fairness without sacrificing speed or excessive utility relative to the standard PageRank algorithm, thereby ensuring that the importance scores remain useful while becoming significantly more just.