Local fair pagerank improves ranking fairness with faster computation
Locally Fair PageRank: Mean-Field Approximation and One-Step Refinement
Social and Information Networks
Summary
PageRank is a way to rank nodes in networks but can unfairly favor certain groups. The authors develop a fast method to approximate Locally Fair PageRank, which adjusts rankings to be fairer for different groups without slow repeated calculations. Their approach groups similar nodes together to estimate scores quickly and refines these estimates using one step of the fairness calculation. Experiments show the method produces rankings close to exact results while running much faster.
What this means in practice
- •For data engineers: Calculate fair node rankings efficiently on large real-world networks to reduce bias without extensive computational costs.
- •For social network analysts: Produce fairer influence scores for individuals or groups in social networks while enabling large-scale analysis by avoiding iterative computations.
Authors
Mukesh Kumar, Gaurav Dixit, Akrati Saxena
Abstract
Graph-based ranking methods such as PageRank can amplify structural disparities in networks, motivating fairness-aware ranking mechanisms for sensitive groups. Locally Fair PageRank (LFPR) enforces fairness through local propagation, but exact computation requires repeated iterations until convergence, limiting scalability on large graphs. We develop a scalable analytical framework for approximating Neighborhood Locally Fair PageRank and Uniform Locally Fair PageRank. By introducing a group-aware heterogeneous mean-field representation, the framework aggregates structurally similar nodes into degree classes and derives closed-form approximations of stationary LFPR scores, avoiding repeated propagation over the fairness-aware transition matrix. We develop a One-Step Refinement (ORF) mechanism that applies the fairness-aware propagation operator once to the mean-field estimate, incorporating node-specific neighborhood information without iterative convergence. The fluctuation analysis characterizes degree-dependent variability around the mean-field solution and shows that the coefficient of variation decreases with increasing in-degree. The mean-field approximation reduces the computational cost of exact LFPR from iterative graph-scale propagation to linear-time node-level estimation, while ORF requires one graph traversal. Experiments on six real-world networks show strong agreement with exact LFPR scores and rankings, preservation of group-level fairness, and substantial runtime reductions. The mean-field approximation reduces complexity to $\mathcal{O}(n)$, while ORF improves accuracy with $\mathcal{O}(m+n)$.