Efficient Edge Rewiring Strategies for Enhancing PageRank Fairness

• URL: http://arxiv.org/abs/2602.02512v1
• Date: Fri, 23 Jan 2026 05:07:36 GMT
• Title: Efficient Edge Rewiring Strategies for Enhancing PageRank Fairness
• Abstract summary: We investigate a well-established network-based formulation of fairness called PageRank fairness.<n>Our goal is to enhance the PageRank fairness by modifying the underlying network structure.<n>Building on a greedy approach, we leverage techniques from fast sampling of rooted spanning forests to devise an effective linear-time algorithm.
• Score: 21.370208622364597
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: 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.

Related papers

• Fairness-aware PageRank via Edge Reweighting [16.39169684970624]
  With the rising importance of AI, the question of fairness in link-analysis has gained traction.<n>We present a new approach for incorporating probabilities by reweighting transition in the underlying transition matrix.<n>We formulate of achieving fair probabilities by seeking to minimize the fairness loss.
  arXiv  Detail & Related papers  (2025-12-08T21:27:03Z)
• An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks [8.319127681936815]
  We propose a method for identifying $k$ polarized communities.<n>We introduce a novel optimization objective that avoids size-imbalanced solutions.<n> Experiments on real-world and synthetic datasets demonstrate that our method consistently outperforms state-of-the-art baselines in solution quality.
  arXiv  Detail & Related papers  (2025-02-04T10:22:01Z)
• Bi-discriminator Domain Adversarial Neural Networks with Class-Level Gradient Alignment [87.8301166955305]
  We propose a novel bi-discriminator domain adversarial neural network with class-level gradient alignment. BACG resorts to gradient signals and second-order probability estimation for better alignment of domain distributions. In addition, inspired by contrastive learning, we develop a memory bank-based variant, i.e. Fast-BACG, which can greatly shorten the training process.
  arXiv  Detail & Related papers  (2023-10-21T09:53:17Z)
• The Cascaded Forward Algorithm for Neural Network Training [61.06444586991505]
  We propose a new learning framework for neural networks, namely Cascaded Forward (CaFo) algorithm, which does not rely on BP optimization as that in FF. Unlike FF, our framework directly outputs label distributions at each cascaded block, which does not require generation of additional negative samples. In our framework each block can be trained independently, so it can be easily deployed into parallel acceleration systems.
  arXiv  Detail & Related papers  (2023-03-17T02:01:11Z)
• Large-Scale Sequential Learning for Recommender and Engineering Systems [91.3755431537592]
  In this thesis, we focus on the design of an automatic algorithms that provide personalized ranking by adapting to the current conditions. For the former, we propose novel algorithm called SAROS that take into account both kinds of feedback for learning over the sequence of interactions. The proposed idea of taking into account the neighbour lines shows statistically significant results in comparison with the initial approach for faults detection in power grid.
  arXiv  Detail & Related papers  (2022-05-13T21:09:41Z)
• Unsupervised Domain-adaptive Hash for Networks [81.49184987430333]
  Domain-adaptive hash learning has enjoyed considerable success in the computer vision community. We develop an unsupervised domain-adaptive hash learning method for networks, dubbed UDAH.
  arXiv  Detail & Related papers  (2021-08-20T12:09:38Z)
• Coarse to Fine: Domain Adaptive Crowd Counting via Adversarial Scoring Network [58.05473757538834]
  This paper proposes a novel adversarial scoring network (ASNet) to bridge the gap across domains from coarse to fine granularity. Three sets of migration experiments show that the proposed methods achieve state-of-the-art counting performance.
  arXiv  Detail & Related papers  (2021-07-27T14:47:24Z)
• FaiR-N: Fair and Robust Neural Networks for Structured Data [10.14835182649819]
  We present a novel formulation for training neural networks that considers the distance of data points to the decision boundary. We show that training with this loss yields more fair and robust neural networks with similar accuracies to models trained without it.
  arXiv  Detail & Related papers  (2020-10-13T01:53:15Z)
• Fitting the Search Space of Weight-sharing NAS with Graph Convolutional Networks [100.14670789581811]
  We train a graph convolutional network to fit the performance of sampled sub-networks. With this strategy, we achieve a higher rank correlation coefficient in the selected set of candidates.
  arXiv  Detail & Related papers  (2020-04-17T19:12:39Z)
• Collaborative Training of Balanced Random Forests for Open Set Domain Adaptation [24.953392909304203]
  We introduce a collaborative training algorithm of balanced random forests with convolutional neural networks for domain adaptation tasks. By collaboratively optimizing the information gain of the labeled source data as well as the entropy of unlabeled target data distributions, the proposed CoBRF algorithm achieves significantly better performance than the state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-02-10T10:43:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.