让网页排名算法在保证公平性的同时保持高效，适用于敏感属性分组场景。
FairRARI: A Plug and Play Framework for Fairness-Aware PageRank
- 基于变分公式构建凸优化框架，插件式实现多种公平性约束
- 在真实数据集上同时提升排名效用与公平性，优于现有方法
- 无需改变原算法复杂度，适合需公平性保障的图学习应用
PageRank（PR）是图机器学习中的基础算法。随着算法公平性的重要性日益凸显，本文研究如何在考虑顶点敏感属性的前提下，计算满足各类群体公平性标准的PR向量。当前缺乏严谨的求解方法：部分方法无法确保达到目标公平水平，另一些则无最优性保障。为此，我们提出统一的内处理凸优化框架FairRARI，以“即插即用”方式应对不同群体公平性要求。通过利用PR的变分形式，该框架将公平PR向量的计算转化为带公平性约束的强凸优化问题，确保达成目标公平水平。我们进一步引入三种可高效求解的公平性准则，使用FairRARI计算公平PR向量的渐近时间复杂度与原始PR算法相同。在多个真实数据集上的实验表明，FairRARI在保持高效的同时，在多个顶点分组中均实现了期望的公平性水平，并显著提升了排名效用，验证了其有效性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。