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

Emmanouil Kariotakis; Aritra Konar

cs.LGFeb 9, 2026

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

Authors: Emmanouil Kariotakis, Aritra Konar

Organizations: Department of Electrical Engineering (ESAT-STADIUS), KU Leuven, Kasteelpark Arenberg 10, 3001 Leuven, Belgium.

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1 : Standard PageRank (PR) and fair PR vectors under $\phi$ -fairness ( Tsioutsiouliklis et al., 2021 ) with two vertex groups (red/blue) on the PolBooks dataset. Vertex size is proportional to the PR score produced by each method. Black circles indicate vertices with zero PR score. The standard PR vector (a) assigns $\phi^{\text{red}}_{\mathrm{o}}\!=\!0.47$ of the total PR mass to the red group. The target for the fair PR vectors is $\phi^{\text{red}}\!=\!0.9$ of total mass for the red group. While both fair PR vectors in (b) and (c) attain this target, $37/49\approx 75\%$ of blue vertices in (b) are set to zero, while $0\%$ of the blue vertices suffer such an undesirable outcome for FairRARI (c).

Panel of Figure 2 — Figure 2 : Comparing Fair PR solutions of prior methods and FairRARI (Ours), on different datasets for $\phi$ -sum-fairness with $2$ groups. The figures showcase the TV utility of each solution for different fairness levels $\phi$ (lower the better). Vertical dotted lines: $\phi_{\mathrm{o}}$ .

Panel of Figure 3 — Figure 3 : Comparing Fair PR solutions of prior methods and FairRARI (Ours), on different datasets for $\phi$ -sum-fairness with $2$ groups. The figures showcase the Kendall Tau coefficient of each solution for different fairness levels $\phi$ (higher the better). Vertical dotted lines: $\phi_{\mathrm{o}}$ .

Figure 4 : Showcasing the TV of the FairRARI solutions for different fairness levels

\phi

, on Twitch datasets with

4

groups. The dashed lines represent the post-processing solution for each dataset.

Panel of Figure 5 — Figure 5 : Showcasing the TV of FairRARI and Post-Processing solutions on the $\boldsymbol{\phi}$ -sum + $\boldsymbol{\alpha}$ -min-fair problem.

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset		$n$	$m$	$K$	$n_{i}$	$n_{i}/n$	$\boldsymbol{\phi}_{\mathrm{o}}$
PolBooks	UnDirected	$92$	$374$	$2$	$(43,49)$	$(0.47,0.53)$	$(0.47,0.53)$
PolBlogs	Directed	$1222$	$16717$	$2$	$(586,636)$	$(0.48,0.52)$	$(0.25,0.75)$
Erdos	UnDirected	$6927$	$8472$	$2$	$(57,6870)$	$(0.01,0.99)$	$(0.01,0.99)$
TwitchPTBR- $2$	UnDirected	$1912$	$31299$	$2$	$(661,1251)$	$(0.35,0.65)$	$(0.34,0.66)$
TwitchRU- $2$	UnDirected	$4385$	$37304$	$2$	$(1075,3310)$	$(0.25,0.75)$	$(0.25,0.75)$
TwitchES- $2$	UnDirected	$4648$	$59382$	$2$	$(1360,3288)$	$(0.29,0.71)$	$(0.30,0.70)$

Appendix

Table 1 : Full summary of dataset statistics: number of vertices (

n

), number of edges (

m

), number of groups (

K

), size of each group (

n_{i}

), group-wise vertex proportions in the graph (

n_{i}/n

), and fairness values of original PR (

\boldsymbol{\phi}_{\mathrm{o}}

)

	PolBlogs ( $\gamma=0$ )	PolBlogs ( $\gamma=0.15$ )	PolBlogs ( $\gamma=0.85$ )
Error	0.0183	0.0118	0.0019
MAE	$10\times 10^{-7}$	$9\times 10^{-7}$	$2\times 10^{-7}$

Appendix

Table 2 : Time-reversibility test on PolBlogs dataset for different

\gamma

values.

	Slashdot ( $\gamma=0$ )	Slashdot ( $\gamma=0.15$ )	Slashdot ( $\gamma=0.85$ )
Error	0.0007	0.0006	0.0002
MAE	$6\times 10^{-11}$	$4\times 10^{-11}$	$3\times 10^{-11}$

Appendix

Table 3 : Time-reversibility test on Slashdot dataset for different

\gamma

values.

Panel of Figure 6 — Figure 6 : Percentage of increase in time over original PR for each one of the implementations, for the $\boldsymbol{\phi}$ -sum-fairness problem.

Panel of Figure 7 — Figure 7 : Percentage of increase in time over original PR for FairRARI, for the $\boldsymbol{\alpha}$ -min-fairness problem.

Panel of Figure 8 — Figure 8 : Percentage of increase in time over original PR for FairRARI, for the $\boldsymbol{\phi}$ -sum + $\boldsymbol{\alpha}$ -min-fairness problem.

Panel of Figure 9 — Figure 9 : Extra experiments similar to Fig. 2 . Comparing Fair PageRank solutions of prior methods and FairRARI (Ours), on the rest of datasets with $2$ groups. It is evident that our algorithm outperforms the existing approaches. For various values of $\phi$ , FairRARI consistently yields a significantly lower TV, very close the lower bound obtained via the post-processing method, indicating that the allocation of fair PR scores is much closer to that of the original PR.

Panel of Figure 10 — Figure 10 : Extra experiments similar to Fig. 3 . Comparing Fair PageRank solutions of prior methods and FairRARI (Ours), on the rest of datasets with $2$ groups. It is evident that our algorithm outperforms the existing approaches. For various values of $\phi$ , FairRARI consistently yields a significantly higher Kendall Tau values, indicating that the resulting ranking is much closer to that of the original PR.

Panel of Figure 11 — Figure 11 : Utility Loss in terms of $\lVert\mathbf{p}_{\mathrm{o}}-\mathbf{p}_{\mathrm{F}}\rVert^{2}_{2}$ , as defined in prior methods. The vertical dotted line represents the $\phi_{\mathrm{o}}$ value of the original PR. It is evident that our algorithm outperforms the existing approaches in terms of this utility loss as well. For various values of $\phi$ , FairRARI consistently yields a significantly lower loss, very close the lower bound obtained via the post-processing method, indicating that the allocation of fair PR scores is much closer to that of the original PR.

Panel of Figure 12 — Figure 12 : Showcasing $\phi$ -Precision of prior methods and FairRARI across top- $x\%$ intervals. The horizontal dotted lines represent the target fairness value $\phi$ . As $x\%$ increases, all methods attain $\phi$ . However, the $\phi$ -Precision of FairRARI is generally close to $\phi$ across varying $x\%$ , demonstrating stable performance. In contrast, the prior methods often deviate sharply from the desired $\phi$ value, either overshooting or undershooting the target before attaining $\phi$ , at a much larger $x\%$ .

Panel of Figure 13 — Figure 13 : For the Twitch datasets with $4$ groups, showcasing the min (dash-dot lines) and the max (dashed lines) value (across the different groups) of $\phi$ -Precision for FairRARI across top- $x\%$ intervals. The horizontal dotted lines represent the target fairness value.

Panel of Figure 14 — Figure 14 : Comparing the Fairness Violation in the $2$ groups case - making clear the unsuitability of FairWalk, CrossWalk, FairGD and AdaptGD in our setting. Except for the Blogs dataset, FairWalk, CrossWalk, FairGD, and AdaptGD produce the same fairness violation values on all remaining datasets.

Panel of Figure 15 — Figure 15 : Comparing the Fairness Violation in the $4$ groups case - making clear the unsuitability of FairWalk and CrossWalk, in the multiple groups case, as well.

Figure 16 : Showcasing the values of the Kendall Tau coefficient the FairRARI solutions for different fairness levels

\phi

, on Twitch datasets with

4

groups. The dashed lines represent the post-processing solution for each dataset.

Panel of Figure 17 — Figure 17 : Showcasing the performance of the FairRARI solutions on the $\boldsymbol{\alpha}$ -min-fair problem, on different datasets with $2$ groups. Top: The minimum score assigned to the vertices in group $\mathcal{A}$ , for different $\alpha$ values. Bottom: PoF paid for different values $\alpha$ . The diagonal dotted line represents the identity line and the vertical one the $\alpha_{\mathrm{o}}$ .

Panel of Figure 18 — Figure 18 : Showcasing the performance, in terms of TV, of the FairRARI and Post-Processing solutions on the $\boldsymbol{\phi}$ -sum + $\boldsymbol{\alpha}$ -min-fair problem, on different datasets with $2$ groups.

Panel of Figure 19 — Figure 19 : Showcasing the performance, in terms of Kendall Tau coefficient, of the FairRARI and Post-Processing solutions on the $\boldsymbol{\phi}$ -sum + $\boldsymbol{\alpha}$ -min-fair problem, on different datasets with $2$ groups.

Explore similar work

Fairness in Link Prediction Beyond Demographic Parity: A Reproducibility Study
Aug 10, 2026Valentijn Oldenburg, Floris de Kam, Stef de Wildt +1Algorithmic Fairness Disparities
University of Amsterdam
Operationalizing Individual Fairness via Gradient Descent and Bradley-Terry Models
May 22, 2026Conlan Olson, Linjun Zhang, Zhun Deng +1Algorithmic Fairness Algorithmic Cores
Columbia University · Rutgers University · UNC Chapel Hill +1
A Rank Graduation metric for Algorithmic fairness
Sep 30, 2026Dalia Atif, Paolo GiudiciAlgorithmic Fairness Credit Risk Prediction

Aug 10, 2026, cs.LGJ/K move · Enter open · S save

Fairness in Link Prediction Beyond Demographic Parity: A Reproducibility Study

Valentijn Oldenburg, Floris de Kam, Stef de Wildt, Jarno Nilson Balk

University of Amsterdam

Algorithmic Fairness Disparities Zero-Shot Link Prediction Reproducibility

Open paper AskPDF arXiv

In fair ranked link prediction, demographic parity (

Δ_\mathrm{DP}

) is a common fairness metric. Yet, Mattos et al. (2025) argue that it fails to detect exposure bias because it ignores where links appear in the ranking. In this study, we reproduce this claim by showing that

Δ_\mathrm{DP}

can indicate aggregate parity even when some subgroup-pair links are systematically ranked lower than others. The proposed rank-aware Normalized Discounted KL-divergence (NDKL), however, does detect such disparities. We also reproduce the effectiveness of MORAL, a post-processing method that improves exposure-based fairness while maintaining competitive utility. Beyond reproduction, we assess robustness using synthetic homophily settings, categorical sensitive attributes, and additional fairness and utility metrics, including subgroup-pair-adapted Attention-Weighted Rank Fairness (AWRF). Overall, our results show that exposure-based metrics uncover biases hidden by

Δ_\mathrm{DP}

and that MORAL reduces these biases with minimal utility loss across diverse settings and datasets. We release a corrected, reproducible implementation at https://github.com/Floris93100/reproducing-MORAL.

Abstract

Explore similar work

Fairness in Link Prediction Beyond Demographic Parity: A Reproducibility Study

Operationalizing Individual Fairness via Gradient Descent and Bradley-Terry Models

A Rank Graduation metric for Algorithmic fairness