有偏图观测的无偏图嵌入：学习节点表示，消除偏差，有效性证明，法国里昂

1423具有有偏图观测的无偏图嵌入王楠，林璐，李俊东，王洪宁{nw 6a，ll 5 fy，jl 6 qk，hw5x}@virginia.edu弗吉尼亚大学美国摘要图嵌入技术在实际机器学习任务中是关键的，这些任务对图结构数据进行操作，例如社会推荐和蛋白质结构建模。嵌入主要在节点级别上执行，用于学习每个节点的表示。 由于图的形成不可避免地受到某些敏感节点属性的影响，节点嵌入可能会继承这些敏感信息，并在下游任务中引入不期望的偏差。大多数现有的作品强加ad-hoc约束的节点嵌入，以限制其分布的无偏性/公平性，但妥协的效用所得到在本文中，我们提出了一个原则性的无偏图嵌入的新方法，通过学习节点嵌入，从一个潜在的无偏图，这是不受敏感节点属性。受这种新视角的启发，我们提出了两种互补的方法来发现这样的底层图，其目标是引入对嵌入效用的最小我们的理论依据和广泛的实验比较对国家的最先进的解决方案证明了我们提出的方法的有效性CCS概念• 计算方法学→机器学习;·应用计算→法律、社会和行为科学。关键词无偏图嵌入，敏感属性，无偏图ACM参考格式：王楠，林璐，李俊东，王洪宁2022年有偏图观测的无偏图嵌入 在ACMWeb Conference 2022（WWW '22）的会议记录中，2022年4月25日至29日，虚 拟 活 动 ， 法 国 里 昂 。 ACM ， 美 国 纽 约 州 纽 约 市 ， 11 页 。https://doi.org/10.1145/3485447.35121891介绍图嵌入是现代机器学习方法中不可或缺的构建块，这些方法对图结构数据进行操作[12，13，20，35，41]。 图嵌入方法将每个节点映射到低维嵌入向量，该低维嵌入向量反映来自给定图中所观察到的连接的节点的结构信息。前两位作者的贡献相等本 作 品 采 用 知 识 共 享 署 名 国 际 协 议 （ Creative Commons AttributionInternational）授权4.0许可证。WWW©2022版权归所有者/作者所有。ACM ISBN978-1-4503-9096-5/22/04。https://doi.org/10.1145/3485447.3512189然后采用这些节点嵌入来解决下游任务，例如社交网络中的朋友推荐（即， 链接预测）或电子商务平台中的用户兴趣预测（即，节点分类）[32，44]。然而，图中观察到的节点连接不可避免地受到某些敏感节点属性（例如，性别、年龄、种族、宗教等，用户）[36]，这是为了与-举行了许多高风险的现实世界的应用程序。如果没有适当的干预，学习的节点嵌入可能会继承不需要的敏感信息，并导致下游任务中的严重偏差和公平性问题[5，37]。例如，在社交网络推荐中，如果观察到具有相同性别的用户更频繁地连接，则所学习的嵌入可以记录这样的信息并且通过仅向具有相同性别身份的用户推荐朋友而导致性别偏见。 当应用于贷款申请[22]或刑事司法[4]等应用时，有偏见的节点嵌入可能会无意中偏袒或忽视一个人口统计群体，从而导致不公平待遇。此外，从数据隐私的角度来看，这也为节点嵌入的提取攻击提供了可能性[39]。 这些现实和道德问题为图嵌入方法设置了更高的标准，以学习有效和无偏见的嵌入。有丰富的文献在算法决策中实施无偏/公平性，特别是在经典分类问题中[8，17，48]。无偏图嵌入是近几年才开始引起人们关注的一个研究领域。 到目前为止，无偏图嵌入最流行的方法是向损失函数添加对抗正则化，这样就不能从学习的嵌入中预测敏感属性[1，5，11，26]。例如，在节点嵌入的基础上构建一个XML无法预测节点的敏感属性然而，这样的正则化只是去偏置节点嵌入的必要条件，并且它通常会损害嵌入的效用（一个简单的令人满意的解决方案是随机化嵌入）。除了这些基于正则化的解决方案之外，Fairwalk [37]将node2vec算法[13]中的随机游走策略修改为两个级别：当选择路径上的下一个节点时，它首先随机选择由敏感属性定义的组，然后从该组中随机采样可达节点。DeBayes [6]提出通过条件网络嵌入[ 18 ]中的先验函数来捕获敏感信息，使得学习的嵌入不会携带敏感信息。然而，Fairwalk和DeBayes都是基于特定的图嵌入方法;如何将它们推广到其他类型的图嵌入方法，如GAT [43]或SGC [46]并不明显。超越现有的无偏图嵌入paradigm，在本文中，我们提出了一个原则性的新框架的目的与理论的理由。我们的解决方案是从一个底层的无偏图中学习节点嵌入，1424WWW在不受敏感属性影响的情况下生成特别地，如Pfeiffer等人所建议的[36]，图的生成可以被视为两个阶段的过程。 在第一阶段中，节点仅基于全局图结构属性（诸如度分布、直径、边连通性、聚类系数等）彼此连接，从而得到不受节点属性影响的底层结构图 在第二阶段中，通过节点属性（包括敏感和非敏感属性）重新路由连接。例如，在社交网络中，相同年龄组的用户往往比不同年龄组的用户更有联系，导致最终观察到的图因年龄属性而有所偏差。因此，我们的去偏原则是过滤掉敏感属性对底层结构图的影响，从观察到的图中创建一个无偏图（只有非敏感属性或没有属性），然后在无偏图上进行嵌入学习。我们提出了两种替代方法来揭示从给定的学习节点嵌入图的无偏第一种是基于加权的方法，其利用在每个边缘上的重要性采样来重新加权基于图重构的损失函数，使得导出的损失如在无偏图上计算的那样。这形成了学习无偏节点嵌入的充分条件：当重构损失确实在相应的无偏图上定义时，所得到的节点嵌入是无偏的，因为无偏图与敏感属性无关。第二种方法是通过正则化，在正则化中，我们要求在有和没有敏感属性的情况下，从嵌入中生成两个节点之间的边的概率是相同的。相反，这形成了一个必要条件：当学习发生在无偏图上时，所得到的嵌入不应该区分是否有任何敏感属性参与了观察图的生成，即，预测的边缘生成应该独立于敏感属性。这两种方法是互补的，可以结合起来控制效用和无偏性之间的权衡。在三个数据集和多个骨干图嵌入模型上的实验证明了该框架的有效性。它实现了令人鼓舞的权衡之间的unbiasedness和效用的学习嵌入。 结果还表明，我们的方法的嵌入可以在下游应用中产生公平的预测。在第二节中，我们讨论了相关的工作。 我们在第三节中介绍了无偏图嵌入的概念和初步知识。我们在第4节中正式定义了底层的无偏图，并在第5节中提出了无偏图嵌入方法。我们评估建议的方法见第6节，结论见第7节。2相关工作图嵌入旨在将图节点映射到低维向量表示，使得原始图可以从这些节点嵌入重构。 传统的方法包括矩阵分解和谱聚类技术[3，31]。近年来，在用于学习节点嵌入的深度神经架构方面取得了许多成功的进展。 Deepwalk [35]和node 2 vec [13]利用基于skip-gram [28]的目标来恢复图上随机游走中的节点上下文。图卷积网络（GCN）通过以端到端的方式聚合由节点/边缘标签监督的邻居的特征来学习节点 这些技术广泛应用于朋友或内容推荐[25，47]，蛋白质结构预测[16]等等。最近关于无偏和公平图嵌入的努力主要集中在学习管道中的预处理，算法和后处理步骤预处理解决方案修改训练数据以减少敏感属性的泄漏[7]。费尔沃克[37]是一种典型的预处理方法，它通过给予每组相邻节点被选择的平等机会来修改图上随机游动的采样过程。然而，这种预处理可能会很好地改变数据分布，并导致训练模型的准确性和公平性较差。后处理方法采用鉴别器来校正学习的嵌入以满足特定的公平性约束[14]。然而，这种ad-hoc后校正与模型训练分离，这会严重降低模型的预测质量。我们的工作属于算法方法的范畴，它修改了学习目标，以防止节点嵌入的偏差。 最流行的算法解决方案是添加（对抗性）正则化作为约束来过滤敏感信息[1，5，10]。 组合公平性约束[5]是通过一组与图嵌入模型联合训练的敏感属性的鉴别器的组合来实现的。类似地，FairGNN [10]采用公平的去偏置，但专注于缺失敏感属性值的去偏置。 不同于基于正则化的方法。DeBayes [6]用一个有偏的先验重新表述了最大似然估计，该先验吸收了关于敏感属性的信息;但是该解决方案与特定的嵌入方法严重耦合，因此难以推广。 我们的方法不同于这些以前的作品，通过学习嵌入从一个底层的无偏图。 我们研究了给定图的生成，并在生成过程中消除了敏感属性的影响，以揭示一个无偏图的图嵌入。生成图模型[2，36]通过对以节点属性和图结构为条件的边的联合分布进行建模，关注图生成的统计过程。例如，属性图模型（AGM）[36]在两步图生成过程中联合建模图结构和节点属性。AGM首先利用结构生成图模型来计算基于给定图的结构属性的底层边缘概率。然后，它从观察到的图中学习边之间的属性相关性，并将它们与结构边概率相结合，以根据属性值对边进行采样。这个过程促使我们通过分离出敏感属性并仅以非敏感属性为条件来计算边缘概率来揭示底层无偏图。3预赛在本节中，我们首先介绍我们的符号和一般的图嵌入概念。由于偏见/公平性问题在涉及人类的预测任务中最明显，例如贷款申请或工作推荐，因此我们将使用用户相关图作为运行示例来讨论我们的无偏见图嵌入标准。但我们必须强调，这种设置只是为了说明具有有偏图观测的无偏图嵌入WWW1425S[客户端][客户端][客户端]（）下一页V→A（）A {}S {}（）∈EVEV ×V（）下一页G（V E A）一.M一L（）∈EMM（）下一页（|）（|））G（|）（）∈EMV∈V{（）|∈VP（C = a|0）uvM无偏图嵌入的概念;我们提出的解决方案可以应用于任何图形数据和选定的敏感属性，以避免学习嵌入中的偏差3.1符号让=、 、是具有一组N个节点的无向属性图 一组边和一组N个属性向量（每个节点一个属性向量）。我们使用u，v来表示节点u和节点v之间的边。每个节点上的属性数为K，并且= a1，a2，. . . ，aN，其中au是节点u的K维属性值向量。我们假设所有属性都是分类的，i是属性i的所有可能值的集合。 1例如，如果节点u是一个用户节点，第i个属性是gender，可能的值为 i = Female，Male，Unknown，则u i = Female表示u是女性。不失一般性，我们假设前m个属性是敏感的，并且au：m和aum：分别代表m个敏感属性和其余的非敏感属性在图嵌入学习的问题中，我们的目标是学习编码器ENC：Rd，其将每个节点u映射到d维嵌入向量zu=ENCu。我们专注于无监督嵌入设置，它不需要节点标签，嵌入是通过链接预测任务学习的。在这个任务中，定义了一个带有参数θ的评分函数sθzu，zv来预测给定图中节点u和节点v之间的边u，v学习节点嵌入和编码器的参数以及评分函数的损失由下式定义公平性度量只能评估预期下游任务的最终预测结果的公平性，但不能评估嵌入是否因敏感属性而有偏差或包含关于敏感属性的任何特别是，下游任务的公平性只是无偏嵌入学习的必要条件，而不是充分条件。逻辑是显而易见的：无偏嵌入可以导致公平的预测结果，因为不涉及敏感的属性信息;但是在一个任务中获得公平性并不意味着嵌入本身是无偏的，例如，这些嵌入仍然可能导致其他任务中的不公平结果，或者甚至通过其他方式获得公平结果，例如预测结果的后处理[45]。在第6节中，我们将使用敏感属性的预测准确性和最终任务的公平性度量来评估我们的无偏图嵌入方法的有效性。4属性在图生成中的作用在本节中，我们将讨论通过显式地对过程中节点属性的影响进行建模来生成观察图特别是，我们假设有一个潜在的结构图背后的观察图，其边缘分布是由全局图的结构属性，如度分布，直径，和聚类系数。中的属性将根据社交网络中的同质性等效应修改结构边缘分布，其中链接基于个体的属性相似性重新连接[23，27]。然后使用修改的边缘分布来生成观察图。（u，v）∈ELed <$e（sθ（zu，zv）），（1）形式上，设为结构生成图模型，并且ΘM为描述底层结构图的属性的参数集特别地，这组参数ΘM是其中ed de e是u，v上的每边缘损失函数。这种损失函数通常旨在最大化给定图中观察到的边的可能性，与未观察到边的节点对的负样本相比[13，29]。3.2无偏图嵌入给定一个节点u，我们认为它的嵌入zu对于属性i是无偏的，如果它独立于属性。先前的工作通过预测敏感属性值的能力来评估学习节点嵌入中的无偏性[5，6，33]。例如，他们首先使用相关的敏感属性值作为标签，在节点嵌入的子集上训练分类器 如果分类器不能正确地预测其余节点嵌入上的敏感属性值，则声称嵌入具有低偏差。 如果预测性能等于随机节点嵌入的预测性能，则学习的嵌入被认为是无偏的。事实上，这样的分类器经常被用作对抗方法中的判别器，其中分类器和嵌入是联合学习的：嵌入被推向分类器预测精度低的方向[5，26]。还有一些研究使用公平性度量，如人口均等或均等机会来定义学习嵌入的无偏性[6，14]。但我们需要澄清，1我们承认，在某些情况下，属性值是连续的，可以应用离散化技术。独立于中的节点属性。我们认为，将图中的可能边的集合表示为二元随机变量Euv，u，v的模型：即，事件Euv=1表示u，v。该模型基于ΘM为Euv分配概率，PMEuv=1 ΘM。因此，底层结构图M的边可以被认为是来自Bernoulli PMEuv=1ΘM的样本。有许多这样的结构模型，如Chung Lu模型[9]和Kronecker乘积图模型[24]。请注意，在生成结构图时不考虑节点现在，我们将属性纳入生成过程。 设Cai，aj我，j是指示随机采样的节点对的属性值组合的变量，其独立于ΘM。 注意，不同节点对实例化的C可以相同，因为不同节点可以具有相同的属性值。给定u和v上的相应属性值和结构参数ΘM，u和v之间的边的条件概率为PoEuv= 1 C=auv，ΘM，其中auv =au，av表示节点u和v上的属性值组合。根据贝叶斯Po（Euv= 1 |C=auv，ΘM）（2）=Po（C=auv|Euv=1，ΘM）Po（Euv=1|（ΘM）Po（C = auv|（ΘM）=PM（Euv=1|ΘM）Po（C=auv|Euv=1，ΘM），u∈V，v∈VWWWwang等人1426无偏图G=（V，E，A）结构图形M，ΘM→GM节点嵌入zuGGP（C）= a|Θ）uvMoM（|）（|）GGGG{（）|∈VG（）/（）∈Euvuv..EL（G.u，v.L（s（z，z））·E.˜∈VuG（V EA）[]u uPo（C = auv|（ΘM）因此，我们可以将等式（2）改写为：GG.R（埃德乌vuv.敏感的属性。 如果我们可以从学习节点嵌入，而不是从学习节点嵌入，则可以保证嵌入对于敏感属性是无偏的。具体地，用于生成G的边缘概率可以写为：Po（ Euv=1|C=auv ， ΘM ） =PM （ Euv=1|ΘM ） R（auv），（4）凡˜R（auv）Po（C=auv|Euv=1，ΘM），则εu∈V，εv∈V，（5）消除敏感属性图1：无偏图嵌入（UGE）的说明节点的颜色代表其属性的值，不同的线条样式表明在生成过程中观察到的边如何受到属性的影响其中Euv上的先验分布由结构模型指定PoEuv=1 ΘM=PMEuv=1ΘM，后验分布考虑了属性值组合的影响。因此，用于生成具有节点属性的观察图的边概率是对那些边概率的修改C一个i，一个j 我，j是不含敏感属性的属性值组合的随机变量，Pon表示用于生成k的分布。 我们将从嵌入学习的方法类命名为UGE，简单地表示无偏置我来植入。接下来，我们介绍两个UGE实例的第一种是UGE-W，它重新加权每边损耗，使得总损耗来自期望中的丢失第二种方法是UGE-R，它增加了一个正则化项来塑造嵌入，以满足那些直接从G中学习的特性。5.1 基于权重的UGE为了基于损失来构成损失，我们修改等式（1）中的损失函数。通过在每个边缘上重新加权损失项，由M和ΘM定义的结构图。重要的是要.（Rauv它们是生成过程的输入，而不是输出。因此，我们认为，Po（C=auv|Euv=1，ΘM）r表示在所有情况下LU GE−W（G）=（u，v）∈ELed <$e（sθ（zu，zv））R（auv）.（六）边，在边因此，对于其关联节点具有相同属性值组合的所有边，该属性值都是相同的为了简化符号，让我们定义一个函数，将属性值组合uv映射到概率比，该概率比通过以下方式将结构图修改为观察图：下面的定理表明，在期望中，这个新的损失等价于从G中学习n个元素的损失。定理5.1. 给定一个图，R<$a<$R a，u，v，LUGE−W（G）是一个无偏损失，与G有关。ProoF. 我们将G中的边缘观测的期望值取为：R（auv）Po（C=auv|Euv=1，ΘM），则nu∈V，nv∈V.UGE-W=ELed <$e（s（zu，zv））UV）（七）Po（Euv = 1 |C = auv，ΘM）= PM（Euv = 1 |ΘM）R（αuv）。（三）通过这种方式，我们通过以下方式显式地对节点属性的影响进行建模：R（auv），它修改了结构图分布PM（Euv=1 |ΘM），用于生成观测图G。（u，v）∈E=E∈V∈VR（auv）R（auv）R（auv）R（auv）5从无偏图在本节中，我们描述了我们提出的学习方法，=u∈V，v∈V=u∈V，v∈VLed <$e（s（zu，zv））R（auv）·Po（Euv = 1 |C =auv，ΘM）Led<$e（s（zu，zv））·Po（Euv=1|C=auv，ΘM）Σ无偏节点嵌入基于第4节中敏感属性影响的生成建模。简而言之，我们的目标是去除敏感属性并修改结构边缘=E（u，v）∈E勒埃德（s（zu，zv））。通过仅对非敏感属性进行条件化来确定概率。这给了我们一个无偏图的边概率，从中我们可以学习无偏的节点嵌入。 我们在图1中说明了这一原理。考虑一个没有敏感属性的世界，节点u的属性向量变成an = a m：，它只包括u中的非敏感属性。 我们将a=，a=，a =，a =表示为由a=，a= u和a=uv=（a=u，a=v）生成的相应的新图。证明了G是一个无影响的有偏自由图用“0”标记的步骤使用等式（3）和等式（4）。□UGE-W与重要性抽样的思想密切相关[21]，它分析了无偏图从给定的图中观 察 到 的 。唯一需要的在现有的图嵌入方法中部署UGE-W的一个重要步骤是计算权R（auv）/R （auv）。 为了估计R （auv ） ，我们需要考虑Po（C=auv）的估计|Euv=1，ΘM）和Po（C=auv|ΘM）。观察图G=（ V，E， A）阿杜属性向量au边沿变化删除添加敏感非敏感au，u∈ V{{Σ具有有偏图观测的无偏图嵌入WWW1427（）下一页..E.˜GG（|）（ouvuvuvMoL（G）−L（G）−P（P˜|（i，j）∈E<$I[aij=auv]）<$i∈V，j∈VI[aij=auv]。（其具有属性值组合UV。对于属性值组合相同的对=i∈V，j∈V，a<$ij=a<$uv估计为R（auv）=mi=1 R（auv[i]）。由于UGE-W只分配=+λQauv−Qauv.u∈V，v∈V通过对观测图的最大似然估计，我们sθ（zu，zv）中的分数作为代表边缘概率的代理有.（i，j）∈EI[aij=auv]由节点u和v的嵌入产生，即，高sθzu，zv表示u和v之间的边缘的高概率。我们可以（|）Po（C=auv|Euv=1，ΘM），（8）通过聚合节点对测量PoEuv=1C=auv，ΘM，相同的属性值组合来边缘化效果P（C = a |Θ）θi∈V，j∈VI[aij=auv].（九）并关注来自属性的影响，〇 uv M N21.一、类似地，我们可以通过下式估计R（auv）：˜ ˜Qauv=Nauvi∈V，j∈V，aij=auvsθ（zi，zj），（13）ouvC=auvEuv=，ΘM|、|,auv.˜˜UVMN2Po（Euv = 1 |C = auv，ΘM），Nauv是节点对的数量请注意，P（C=au v）的估计|Euv=1，ΘM）基于O翁克河类似地，P_o_v（E_u_v=1|C=auv，ΘM）可以由下式表示：EQauv，它可以通过对score进行聚合来获得，不幸的是，它来自隐式无偏图G，具有无意义的属性值组合。最后，我们使用无法观察但我们可以用以下方式近似：按非敏感属性值对节点对进行分组后，将Qauv和Qauv之间的距离作为正则化组合，感觉属性只对边缘进行检索，但不改变每组中的边的数目因此，在本发明中，˜˜（i，j）∈E<$Iaij=auv卢。GE−R（G）（u，v）∈E（十四）¨ ¨.[编辑]=Led <$e（sθ（zu，zv））+λQauv−Qauv2，PoP（C=auv|Euv=1，ΘM）=|（十二）|(12)i∈V，j∈V，a<$i j=a<$uvI[（i，j）∈E]|E˜|其中λ控制每边缘损耗与正则化与先前工作中采用的对抗性正则化相比，.I[（i，j）∈ E][1，5，11，26]，UGE-R在正则化.|E˜|由嵌入引起的所有以前基于正则化的=（i，j）∈EI[a<$ij=a<$uv].|E|方法将约束施加在各个边上。我们应该注意到正则化项在所有节点对上求和其复杂度为O（N3），并且计算成本很高。但在对于具有相同属性值组合的节点对，等式（8）-等式（11）仅需要计算一次，而不是针对每一对。这可以通过首先按节点对的属性值组合对节点对进行分组，然后在每个组中执行估计来完成。然而，当存在许多属性或属性可以采用许多唯一值时，估计可能变得不准确，因为将存在许多组并且每个组可能仅具有几个节点。 在这种情况下，我们可以在属性之间做出独立性假设。例如，通过假设它们是独立的，所有K个属性上的特定属性值组合的估计成为K个估计的乘积，每个属性一个。非敏感属性可以在实践中，我们可以通过仅抽样批次来添加正则化在模型更新期间的每次迭代中的节点对，并使用λ来补偿正则化的强度5.3 组合方法正如第1节所暗示的，UGE-W是无偏图嵌入的充分条件，因为它直接从无偏图中学习节点嵌入UGE-R是一个必要条件，因为它要求学习的嵌入满足无偏图的性质我们可以将它们结合起来，以权衡去偏效应和效用，LU GE−C（G）（15）这个假设与R其中，R（a_v）=1，且只有R（a_v）n ∈b_e.（u，v）∈ER（auv）.¨¨UVu∈V，v∈V预先计算的损失权重，基于它的优化将不增加任何图嵌入方法的复杂度5.2 基于正则化的UGE我们提出了UGE的另一种方法，它在损失函数中添加了一个正则化项，该损失函数可以推动嵌入满足无偏图所需的属性。具体地说，当节点嵌入是从嵌入学习，它们产生的边缘分布应该是相同的敏感属性和不敏感属性。 为了加强这一条件，我们需要规范体育与体育之间的差异，= 1 C=a，ΘP=1|C=auv，ΘM）从n个节点中导出。我们可以使用其中我们使用UGE C来表示组合方法。因此，U GE C 可以利用UGE-W和UGE-R的优势，在无偏性和无偏性之间实现更好的权衡。以及节点嵌入在下游任务中的效用6实验在本节中，我们研究了UGE在三个基准数据集上的经验表现，并与几个基线进行了比较。特别是，我们应用UGE五个普遍采用的骨干图嵌入模型，以显示其广泛的适用性。 为了评估去偏性1）（十）我们使用Q以表示近似的Po（C=a|Θ具有和不具有敏感属性的Led <$e（sθ（zu，zv））R（a））2，具有有偏图观测的无偏图嵌入WWW1428能，首先评估节点嵌入1429····×WWW表1：评估图数据集的统计Pokec-z统计Pokec-n MovieLens-1M节点数六十七七百九十六六十六，五百六十九九九九二边数八八二，七六五七二九，一百二十九一千二百零九密度0。000190。000160。01002通过它们预测敏感属性值的能力，其中较低的预测性能意味着较好的去偏置效果。然后使用特定于任务的度量来评估嵌入的效用此外，我们还将公平性度量应用于链路预测结果，以证明使用UGE嵌入来实现下游任务公平性的潜力6.1设置数据集。 我们使用三个公共的用户相关图数据集，Pokec-z，Pokec-n和MovieLens-1 M，其中用户与敏感属性相关联，以消除偏见。表1总结了这三个数据集的统计数据。 Pokec 2是斯洛伐克的一个在线社交网络，其中包含数百万用户的匿名数据。 基于用户所属的省份，我们使用了来自[ 10 ]的两个样本数据集Pokec-z和Pokec-n，这两个样本数据集分别由属于相应省份的两个主要地区的用户组成。在这两个数据集中，每个用户都有一组丰富的特征，如教育，工作领域，兴趣等; 并且我们将性别、地区和年龄作为（敏感）属性，其效果将在我们的评估中进行研究MovieLens-1 M3是一个流行的电影推荐基准，其中包含约100万用户对电影的评分[15]。在我们的实验中，我们构建了一个二分图，其中包括用户和电影节点和评级关系的边缘。数据集包括用户的性别、职业和年龄信息，我们将其视为待研究的敏感属性我们不考虑电影属性，因此在应用UGE时，只有用户属性被计算用于我们的去偏置目的。图嵌入模型。UGE是学习无偏节点嵌入的通用方法，可以应用于不同的图嵌入模型。我们评估其有效性的五个代表性的嵌入模型在监督设置与链接预测任务。 GCN [19]，GAT [42]，SGC[46]和node2vec [13]是深度学习模型，我们使用两个节点嵌入之间的点积来预测它们之间的边缘概率，并应用交叉熵损失进行训练。MF[30]将矩阵分解应用于邻接矩阵。 每个节点由一个用成对逻辑损失学习的嵌入向量表示[38]。基线。 我们考虑三个基线生成无偏的节点嵌入。（ 1 ）Fairwalk[37]基于node2vec，它通过将相邻节点与其敏感属性的值分组来修改随机行走生成的预处理Fairwalk不是随机跳转到邻居节点，而是首先跳转到一个组，然后从该组中采样一个节点，以生成随机游走。 我们将其扩展到GCN，GAT和SGC通过采样大小为1的随机游动来构建这些嵌入模型的相应的每边损失。（2）组成2https://snap.stanford.edu/data/soc-pokec.html3https://grouplens.org/datasets/movielens/1m/公平约束（CFC）[5]是一种算法方法，它通过联合训练敏感属性鉴别器的组合来向损失添加对抗正则化器。 我们将CFC应用于所有图嵌入模型，并调整正则化器的权重，其中较大的权重预计会导致偏差较小但效用较低的嵌入。（3）随机嵌入被认为是无偏基线。我们通过从[0，1]中均匀采样每个嵌入维度的值来生成随机嵌入。值得一提的是，最近的工作DeBayes [6]，它是基于条件网络嵌入（CNE）[18]，包括在有偏先验的敏感信息学习无偏节点嵌入。 我们没有包括它，因为它仅限于CNE，不能轻易推广到其他图嵌入模型。此外，我们发现DeBayes中的偏差先验计算不能扩展到大型图，其中产生的节点嵌入的效用接近随机。最初的论文[6]只对两个小的图数据集进行了实验，这些数据集的节点和边都小于4K和100K默认情况下，UGE遵循Fairwalk，在实验中分别对每个敏感属性进行去偏，而属性之间没有独立性。CFC如原始论文中所建议的那样联合消除所有敏感属性的偏差。4配置. 对于Pokec-z和Pokec-n数据集，我们应用GCN，GAT，SGC和node 2 vec作为嵌入模型，并在它们之上应用去偏置方法。 对于每个数据集，我们通过收集Npos等于其节点度的Npos相邻节点来构建每个节点的正例，并随机抽取Nne <$= 20Npos未连接节点作为负例。 对于每个节点，我们使用90%的正面和负面示例进行训练，其余10%用于测试。对于Movielens-1M，我们遵循常见的做法，并使用MF作为嵌入模型[5，37]。我们没有在这个数据集上评估Fairwalk，因为没有用户-用户连接，并且不能直接应用公平随机游走评级矩阵被二进制化以创建用于MF的二分用户-电影图。我们使用80%的评级用于培训，20%用于测试。对于所有数据集和嵌入模型，我们将节点嵌入大小设置为d=16。 我们在附录A中提供了关于模型实现和超参数调优的更多细节。在6.2节中，我们比较了不同基线嵌入的无偏性和效用 我们评估6.3节中嵌入的公平性。 我们在6.4节中研究了UGE和CFC中的无偏性-效用权衡。由于有大量的实验设置由不同的数据集、嵌入模型和基线组成，我们在每个部分报告了不同组合的结果，以最大限度地提高每个组件的覆盖率，并将其他结果纳入附录B。6.2无偏性与效用权衡我们首先比较了不同去偏方法的节点嵌入的无偏性。对于每个敏感属性，我们训练了一个逻辑分类器，其中80%的节点使用它们的嵌入作为特征，属性值作为标签。然后，我们使用分类器预测其余20%节点上的属性值，并使用Micro-F1评估性能。Micro-F1评分可用于衡量嵌入中偏倚的严重程度，即，较低4UGE可以通过去除无偏图中的一个或多个属性来消除单个属性或多个属性的偏置具有有偏图观测的无偏图嵌入WWW14300.6Random node2vec Fairwalk0.6CFCUGE-W UGE-R UGE-C0.60.40.40.40.20.20.2表2：Micro-F1在Pokec-z和Pokec-n上评估的无偏性粗体数字突出显示每行中的最佳数据集嵌入模型预测目标无去偏Fairwalk CFC UGE-W UGE-R UGE-C随机Pokec-zGAT性别（Micro-F1）区域（Micro-F1）0.62320.81970.61350.80800.58400.72170.61500.67840.60940.76600.57470.63560.49210.4966年龄（Micro-F1）0.05260.05220.04980.04310.05450.04290.0007Pokec-nnode2vec性别（Micro-F1）区域（Micro-F1）0.52410.86900.52910.85260.52410.84230.51870.81580.50950.69750.51580.63470.50780.4987年龄（Micro-F1）0.06260.05340.04260.03050.02940.01940.0002GCN（无去偏）GCN（有UGE-C）0.30.20.10.55 0.60关于性别的0.50.60.70.8区域上的Micro-F10.000.02零点零四Micro-F1老化(a) 以GAT为嵌入模型的Pokec-z图3：在Pokec-n上学习的嵌入的可视化。节点颜色表示节点的区域。0.51 0.520.53关于性别的0.6 0.8区域上的Micro-F10.000.020.04零点零六Micro-F1老化(b) 以node 2 vec为嵌入模型的Pokec-n随机MF CFC UGE-W UGE-RUGE-C测试集中的邻居节点和随机抽样的负节点。然后在此列表上使用预测边缘评估NDCG@100.40.30.20.10.00.5 0.60.7关于性别的0.40.30.20.10.00.040.060.080.10微F1占领0.40.30.20.10.00.30 0.350.40Micro-F1老化节点嵌入的概率 图2a和2b显示了与表2中的两个数据集和嵌入模型相对应的不同方法的嵌入的无偏性和效用。 图2c显示了使用MF作为嵌入模型的MovieLens-1 M上的结果。(c) MovieLens-1 M，MF作为嵌入模型图2：不同方法的效用（NDCG@10）和无偏性（Micro-F1）之间的权衡。随机嵌入给出最低的Micro-F1（绿线），并且无去偏置给出最佳的NDCG@10（蓝线）。一个理想的debi-asing方法应该位于左上角。得分意味着嵌入中的较低偏差随机嵌入预期具有最低的Micro-F1，而没有去偏置的嵌入应具有最高的Micro-F1。 我们在表2中显示了使用GAT作为基本嵌入模型的Pokec-z和使用node 2 vec作为基本嵌入模型的Pokec-n上的结果。从结果中，我们可以看到，UGE方法的嵌入总是对所有敏感属性和数据集的所有基线具有最小的偏差。这证实了从无偏图学习无偏嵌入此外，UGE-W和UGE-R相结合，UGE-C通常产生最好的去偏效果，这表明了两种方法的互补作用。除了无偏性之外，学习的嵌入在应用于下游任务时需要有效特别地，我们使用在链接预测任务上评估的NDCG@10来测量嵌入的效用。具体来说，对于每个目标节点，我们创建一个包含100个节点的候选列表，其中包括所有观察到的节点。在这些图中，不同的嵌入方法由图中的不同形状表示，并且我们使用不同的颜色来区分UGE-W、UGE-R和UGE-C。随机嵌入没有任何偏置，并提供最低的Micro-F1（绿线），而没有任何去偏置的嵌入给出最高的NDCG@10（蓝线）。为了实现最佳的效用无偏性权衡，理想的去偏方法应该将其自身定位在左上角。如图所示，在大多数情况下，基于UGE的方法在这两个矛盾的目标上实现了最令人鼓舞的权衡 UGE-C通常可以达到更好的去偏效果，而不会牺牲太多的效用。UGE-W和UGE-R保持高效用，但不如组合版本有效。CFC可以在嵌入中实现下降无偏性，但实用性严 重 受 损 （ 例 如 Pokec-z 和 MovieLens-1 M ） 。 不幸的是，Fairwalk并没有表现出明显的去偏置效应。为了进一步可视化UGE的去偏置效果，我们使用t-SNE将Pokec-n上的节点嵌入投影到图1中的2-D空间。3. 左边的图显示了通过GCN学习的嵌入，而没有去偏置，右边的图显示了通过在GCN上应用UGE-C来去偏置区域属性的去偏置嵌入。节点颜色表示区域值。在没有去偏置的情况下，嵌入被清楚地聚类以反映节点的区域 使用UGE-C，来自不同区域的嵌入被混合在一起，显示了从嵌入中去除区域信息的效果。随机GAT FairwalkCFCUGE-W UGE-R UGE-C0.30.30.20.20.10.1链接预测（NDCG@10）链接预测（NDCG@10）链接预测（NDCG@10）WWWwang等人1431随机Fairwalknode2vec CFCUGE-WUGE-RUGE-CUGE-CCFCGAT0.60.50.40.30.20.10.60.002 0.0040.006DP性别问题0.0 0.2 0.40.6道德操守办公室0.400.350.300.250.580.600.62关于性别的90.65 0.75 0.85区域上的Micro-F10.50.40.3图5：CFC和UGE-C在Pokec-z上的权衡比较，GAT作为嵌入模型。0.20.10.60.40.20.000.020.040.06零点零八DP区0.1 0.2 0.30.4EO区域本身已经可以实现有希望的去偏效果，我们期望UGE-R增加的正则化可以补充它，以获得更好的权衡。特别是，我们调整了CFC和 UGE-C 中 的 正 则 化 权 重 ， 并 绘 制 了 Micro-F1 （ x 轴 ） 与NDCG@10（y轴）来自图5中的结果嵌入。 重量值标记在每个点上，并在附录A中列出。结果是在Pokec-z上以GAT作为嵌入模型获得的，两个图分别对应于去偏性别和地区。0.000.050.100.150.20DP年龄0.2 0.4 0.6 0.81.0EO老化在Micro-F1测量的偏差程度相同的情况下，UGE-C的嵌入具有更高的实用性，如垂直方向所示。图4：在Pokec-n上使用node 2 vec作为嵌入模型的链接预测任务上评估的公平性度量6.3嵌入的高级公平性我们研究了去偏嵌入是否会导致下游任务的公平性。我们采用两个流行的指标-人口统计平价（DP）和均衡机会（EO），以评估嵌入的链接预测结果的公平性。 DP要求预测独立于敏感属性，通过敏感属性值的不同组合之间的预测率的最大差异来测量。 EO测量预测边缘的真阳性率（TPR）和敏感属性之间的独立性。 它由不同敏感属性值组合之间TPR的最大差异定义。对于DP和EO，较低的值表示更好的公平性。 我们使用[6]中DP和EO的精确公式，并使用sigmoid函数将一对节点的边缘得分转换为概率。我们展示了公平与， 图4中的实用程序，它们在Pokec-n中的