# Efficient Edge Rewiring Strategies for Enhancing PageRank Fairness

arXiv: https://arxiv.org/abs/2602.02512 · HTML: https://mlsanity.com/paper/2602.02512/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 89 references that are in the map.
- First posted on arXiv 23 Jan 2026.

## Builds on (most cited first, 30 of 36)

- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [A comparative study of fairness-enhancing interventions in machine learning](https://mlsanity.com/paper/1802.04422/) (2018)
- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [Scalable Graph Neural Networks via Bidirectional Propagation](https://mlsanity.com/paper/2010.15421/) (2020)
- [DiffWire: Inductive Graph Rewiring via the Lov'asz Bound](https://mlsanity.com/paper/2206.07369/) (2022)
- [Fairness in Graph Mining: A Survey](https://mlsanity.com/paper/2204.09888/) (2022)
- [FairDrop: Biased Edge Dropout for Enhancing Fairness in Graph Representation Learning](https://mlsanity.com/paper/2104.14210/) (2021)
- [Fairness in Rankings and Recommendations: An Overview](https://mlsanity.com/paper/2104.05994/) (2021)
- [SNAP: A General Purpose Network Analysis and Graph Mining Library](https://mlsanity.com/paper/1606.07550/) (2016)
- [PageRank beyond the Web](https://mlsanity.com/paper/1407.5107/) (2014)
- [Fighting Fire with Fire: Using Antidote Data to Improve Polarization and Fairness of Recommender Systems](https://mlsanity.com/paper/1812.01504/) (2018)
- [Fairness in Semi-supervised Learning: Unlabeled Data Help to Reduce Discrimination](https://mlsanity.com/paper/2009.12040/) (2020)
- [Group-Fairness in Influence Maximization](https://mlsanity.com/paper/1903.00967/) (2019)
- [Fast and Accurate Anomaly Detection in Dynamic Graphs with a Two-Pronged Approach](https://mlsanity.com/paper/2011.13085/) (2020)
- [Improving Recommendation Fairness via Data Augmentation](https://mlsanity.com/paper/2302.06333/) (2023)
- [Scalable Graph Embeddings via Sparse Transpose Proximities](https://mlsanity.com/paper/1905.07245/) (2019)
- [On the Fairness of Time-Critical Influence Maximization in Social Networks](https://mlsanity.com/paper/1905.06618/) (2019)
- [Gaps in Information Access in Social Networks](https://mlsanity.com/paper/1903.02047/) (2019)
- [DISCO: Comprehensive and Explainable Disinformation Detection](https://mlsanity.com/paper/2203.04928/) (2022)
- [FairSample: Training Fair and Accurate Graph Convolutional Neural Networks Efficiently](https://mlsanity.com/paper/2401.14702/) (2024)
- [Inequality and Inequity in Network-based Ranking and Recommendation Algorithms](https://mlsanity.com/paper/2110.00072/) (2021)
- [RePBubLik: Reducing the Polarized Bubble Radius with Link Insertions](https://mlsanity.com/paper/2101.04751/) (2021)
- [Rewiring What-to-Watch-Next Recommendations to Reduce Radicalization Pathways](https://mlsanity.com/paper/2202.00640/) (2022)
- [Fairness Rising from the Ranks: HITS and PageRank on Homophilic Networks](https://mlsanity.com/paper/2402.13787/) (2024)
- [Reducing Access Disparities in Networks using Edge Augmentation](https://mlsanity.com/paper/2209.07616/) (2022)
- [Fast Generation of Random Spanning Trees and the Effective Resistance Metric](https://mlsanity.com/paper/1501.00267/) (2015)
- [Graph Tikhonov Regularization and Interpolation via Random Spanning Forests](https://mlsanity.com/paper/2011.10450/) (2020)
- [A Unified Seeding Framework](https://mlsanity.com/paper/2011.08946/) (2020)
- [Maximizing Fair Content Spread via Edge Suggestion in Social Networks](https://mlsanity.com/paper/2207.07704/) (2022)

## Built on by (most cited first, 1 of 1)

- [What Makes a Desired Graph for Relational Deep Learning?](https://mlsanity.com/paper/2606.08491/) (2026)

## Abstract (arXiv)

We study the notion of unfairness in social networks, where a group such as females in a male-dominated industry are disadvantaged in access to important information, e.g. job posts, due to their less favorable positions in the network. We investigate a well-established network-based formulation of fairness called PageRank fairness, which refers to a fair allocation of the PageRank weights among distinct groups. Our goal is to enhance the PageRank fairness by modifying the underlying network structure. More precisely, we study the problem of maximizing PageRank fairness with respect to a disadvantaged group, when we are permitted to rewire a fixed number of edges in the network. Building on a greedy approach, we leverage techniques from fast sampling of rooted spanning forests to devise an effective linear-time algorithm for this problem. To evaluate the accuracy and performance of our proposed algorithm, we conduct a large set of experiments on various real-world network data. Our experiments demonstrate that the proposed algorithm significantly outperforms the existing ones. Our algorithm is capable of generating accurate solutions for networks of million nodes in just a few minutes.