Link-analysis algorithms, such as PageRank, are instrumental in understanding the structural dynamics of networks by evaluating the importance of individual vertices based on their connectivity. Recently, with the rising importance of responsible AI, the question of fairness in link-analysis algorithms has gained traction. In this paper, we present a new approach for incorporating group fairness into the PageRank algorithm by reweighting the transition probabilities in the underlying transition matrix. We formulate the problem of achieving fair PageRank by seeking to minimize the fairness loss, which is the difference between the original group-wise PageRank distribution and a target PageRank distribution. We further define a group-adapted fairness notion, which accounts for group homophily by considering random walks with group-biased restart for each group. Since the fairness loss is non-convex, we propose an efficient projected gradient-descent method for computing locally-optimal edge weights. Unlike earlier approaches, we do not recommend adding new edges to the network, nor do we adjust the restart vector. Instead, we keep the topology of the underlying network unchanged and only modify the relative importance of existing edges. We empirically compare our approach with state-of-the-art baselines and demonstrate the efficacy of our method, where very small changes in the transition matrix lead to significant improvement in the fairness of the PageRank algorithm.

翻译：链接分析算法（如PageRank）通过评估节点基于连接性的重要性，对理解网络结构动态至关重要。近年来，随着负责任人工智能的重要性日益凸显，链接分析算法的公平性问题受到广泛关注。本文提出一种通过重加权底层转移矩阵中的转移概率，将群体公平性融入PageRank算法的新方法。我们将实现公平PageRank的问题形式化为最小化公平性损失，即原始群体间PageRank分布与目标PageRank分布之间的差异。进一步定义了一种群体适应性公平性概念，通过考虑每个群体具有群体偏置重启的随机游走，以纳入群体同质性因素。由于公平性损失具有非凸性，我们提出一种高效的投影梯度下降法来计算局部最优的边权重。与早期方法不同，我们既不建议向网络添加新边，也不调整重启向量，而是保持底层网络拓扑不变，仅修改现有边的相对重要性。我们通过实证将本方法与前沿基线进行比较，证明了方法的有效性：转移矩阵中极微小的调整即可显著提升PageRank算法的公平性。