k-hop Fairness: Addressing Disparities in Graph Link Prediction Beyond First-Order Neighborhoods

该论文针对现有链接预测公平性方法仅关注一阶邻域（成对公平）而忽视不同距离节点间结构性偏见的局限，提出了基于$k$-hop 距离的公平性新范式，通过形式化定义与预处理及后处理策略，在基准实验中有效缓解了多层级结构偏见并实现了性能与公平性的良好权衡。

要点

这篇论文探讨了一个关于社交网络推荐（比如 LinkedIn 推荐好友，或者抖音推荐关注）中非常深刻的问题：算法如何做到真正的公平？

为了让你轻松理解，我们可以把整个研究过程想象成是在规划一座巨大的城市。

1. 背景：现有的“公平”有什么毛病？

想象一下，你是一家城市交通规划局的局长。你的任务是设计新的道路（链接预测），让市民（节点）能更好地连接起来。

• 现状：现在的城市里，人们喜欢和“同类”住在一起（比如喜欢摇滚的都住摇滚区，喜欢古典的都住古典区）。这叫同质性。
• 旧方案（成对公平 Dyadic Fairness）：以前的规划师认为，只要我强行在“摇滚区”和“古典区”之间修几条路，让两个区的人能互相串门，这就叫“公平”了。
• 问题所在：这篇论文的作者发现，这种“修路”方法有个大漏洞。
  • 如果你只在两个区已经比较热闹、容易修路的地方修路，那么这两个区里原本就住得离大路近的“富人”会更方便，而住在偏远角落、被隔离的“穷人”依然出不去。
  • 比喻：就像你在两个社区之间修了一座桥，但桥只修在两个社区最繁华的市中心。那些住在社区边缘、被隔离在深巷里的人，依然走不到桥边。旧的公平只看了“有没有路”，没看“谁真正能走到路上”。

2. 核心创新：k-hop 公平（多跳公平）

作者提出了一个新的概念，叫 k-hop 公平。

• 什么是 k-hop？
  • 1-hop：你的直接邻居（你隔壁的人）。
  • 2-hop：你邻居的邻居（你朋友的朋友）。
  • 3-hop：更远一点的朋友圈。
• 新观点：真正的公平，不能只看能不能直接连上，要看在这个距离范围内，每个人接触到的“不同种类的人”是否均衡。
  • 比喻：以前我们只关心“能不能直接走到对门”。现在我们要关心：“如果你走出家门，走 1 步、走 2 步、走 3 步，你遇到的邻居里，是不是既有摇滚迷也有古典迷？还是说，无论走多远，你周围全是摇滚迷？”
  • 如果一个人无论走多远（k-hop），周围全是同类，那他就是被结构性隔离的。我们的目标就是打破这种隔离，让每个人在“几步路”的范围内都能接触到多元的世界。

3. 他们做了什么？（两大法宝）

为了解决这个问题，作者发明了两套“魔法工具”：

法宝一：事前诊断（Pre-processing）—— 重新规划城市地基

• 做法：在算法开始工作之前，先检查城市的地图（图结构）。
• 比喻：就像在修路之前，先发现某些区域因为地形原因（结构偏差）导致很难修路。于是，规划师主动在那些被隔离的“死角”和“繁华区”之间强行加几条路（添加边），或者把某些路改一下。
• 目的：从根源上消除“死角”，让城市结构本身就更公平。

法宝二：事后修正（Post-processing）—— 智能导航调整

• 做法：让算法先按老办法推荐，然后人工介入，专门调整那些特定距离（比如 2 步或 3 步）的推荐结果。
• 比喻：导航软件已经给你规划好了路线，但发现它只把你引向繁华区。于是，导航软件说：“等等，为了公平，我要特意把你引向那个平时没人去的偏远角落，让你也能认识新朋友。”
• 优点：这种方法非常灵活，可以针对“走 2 步”不公平的情况单独修正，而不影响“走 1 步”的推荐质量。

4. 实验发现了什么？

作者在很多真实的数据集（比如政治博客网络、Facebook 好友网、学术合作网）上做了测试，发现了一些有趣的现象：

1. 偏见无处不在：不仅是你直接的朋友（1-hop）有偏见，你朋友的朋友（2-hop）、甚至更远的朋友圈（3-hop）里，偏见依然存在。
2. 牵一发而动全身：如果你试图修复"2 步距离”的偏见，可能会意外地改善"1 步”的偏见，但也可能让"3 步”的偏见变得更糟。就像推倒一块多米诺骨牌，影响会传导。
3. 新方法的胜利：作者提出的“事后修正”方法，能在不牺牲太多推荐准确度（AUC）的前提下，显著降低特定距离上的不公平。它就像是一个精准的“微调器”，哪里不平修哪里。

5. 总结：这对我们意味着什么？

这篇论文告诉我们，真正的公平不仅仅是“把两个群体连起来”，而是要确保每个人，无论他住在城市的哪个角落，无论他走几步路，都能平等地接触到多元化的世界。

• 以前的公平：只要两个群体之间有路，就是公平。（忽略了路边的穷人）
• 现在的公平：每个人在走出家门几步之内，都能感受到世界的多样性。（关注每个人的具体体验）

这就好比，以前我们觉得只要给所有人发了一张“城市通行证”就是公平；现在我们要确保，无论你是谁，你拿着这张通行证，都能真正走进城市的每一个角落，而不是被困在某个特定的街区里。

这项研究让未来的社交推荐、招聘推荐、甚至新闻推荐，能更细腻地照顾到那些容易被算法“遗忘”的角落，让技术真正服务于社会的包容性。

技术摘要

1. 问题背景 (Problem Statement)

核心问题：
现有的图链接预测（Link Prediction, LP）任务中，公平性研究主要局限于**成对公平性（Dyadic Fairness）**范式。

• 成对公平的局限性： 传统方法（如人口统计 parity, DP）关注的是预测的边是否在不同敏感属性组（如性别、种族）之间均匀分布。然而，这种方法存在两个主要缺陷：
  1. 掩盖隔离现象： 盲目促进组间连接可能导致模型只连接那些已经高度多样化的区域，而忽略了那些被隔离的节点群（即“信息孤岛”），从而加剧组内不平等。
  2. 忽视图结构位置： 它假设所有组间边是等价的，忽略了节点在图中的拓扑位置。例如，为一个已经拥有多样化邻域的节点添加一条组间边，与为一个孤立节点添加一条组间边，对公平性的贡献截然不同。

研究动机：
现实世界的图往往表现出强烈的同质性（Homophily），导致结构性偏见。现有的公平性指标未能捕捉到这种偏见在不同**跳数（Hop）**距离下的分布差异。工业界（如 LinkedIn）的推荐系统通常会根据距离（2-hop, 3-hop+）对建议进行分类，因此需要一种能评估特定距离下公平性的新框架。

---

2. 核心方法论 (Methodology)

本文提出了 k-hop 公平性（k-hop Fairness） 框架，将公平性评估从“边”的层面转移到“节点邻域”的层面，并针对特定的图距离 $k$ 进行定义和缓解。

2.1 核心定义

• k-hop 节点属性暴露 (k-hop Node Attribute Exposure): 定义 $f^{(k)}_s(v)$ 为节点 $v$ 在距离 $k$ 处与敏感属性为 $s$ 的节点建立连接的概率。
• k-hop 组间暴露 (k-hop Group Exposure): 将局部暴露聚合到组级别，$\phi^{(k)}_{s \to s'}$ 表示敏感组 $s$ 中的节点在距离 $k$ 处连接到组 $s'$ 的平均概率。
• k-hop 邻域公平性 (k-hop Neighborhood Fairness, $NF^{(k)}$): 衡量同一源组 $s$ 的节点在距离 $k$ 处对不同目标组 $s'$ 的暴露差异。
  $$NF^{(k)}(h) = \max_{s \in S} \max_{s_1 \neq s_2} | \phi^{(k)}_{s_1 \to s}(h) - \phi^{(k)}_{s_2 \to s}(h) |$$
  $NF^{(k)}$ 越小，表示在距离 $k$ 处的连接越公平。
• k-hop 结构偏差 (k-hop Structural Bias, $NB^{(k)}$): 当预测器 $h$ 替换为真实图的指示函数时，$NF^{(k)}$ 即为图本身在距离 $k$ 处的结构性偏差。

2.2 缓解策略 (Mitigation Strategies)

论文提出了两种模型无关（Model-agnostic）的缓解策略：

1. 后处理 (Post-processing):

   • 目标： 直接修正链接预测模型的输出概率矩阵 $P$。
   • 方法： 仅修改距离恰好为 $k$ 的节点对之间的预测分数。
   • 优化目标： 最小化 $NF^{(k)}(P') + \alpha \| U \odot \tilde{A}^{(k)} \|_F$。
     • 第一项：降低目标距离 $k$ 的公平性差距。
     • 第二项：正则化项，保持对原始预测的忠实度（Fidelity），防止过度修改。
   • 优势： 优化过程独立于图结构（$\tilde{A}^{(k)}$ 固定），计算高效，且不同 $k$ 值的优化互不干扰。

2. 预处理 (Pre-processing):

   • 目标： 修改图结构（邻接矩阵 $A$）以减少结构性偏差。
   • 方法： 通过添加边（Edge Addition）来优化图结构。
   • 优化目标： 最小化 $NB^{(k)}(A') + \alpha \| A' - A \|_F$。
   • 挑战与解决： 由于计算最短路径距离通常不可微，论文利用邻接矩阵的幂次（$A^k$）来近似编码 $k$ 步游走信息，从而构建可微的优化过程。

---

3. 主要贡献 (Key Contributions)

1. 提出 k-hop 公平性概念： 突破了传统成对公平的局限，引入基于节点 $k$ 跳邻域多样性的公平性评估框架。该框架适用于多值敏感属性、加权图和有向图。
2. 算法化度量与缓解： 提出了计算 $k$-hop 偏差和公平性的具体算法（复杂度为 $O(n^2)$），并设计了前处理和后处理的缓解算法，能够灵活应用于不同的链接预测场景。
3. 实证发现与验证：
   • 揭示了模型倾向于在不同 $k$ 跳距离上复现结构性偏见。
   • 发现不同跳数之间的结构偏差存在相互依赖性（例如，减少 2-hop 偏差可能会增加 3-hop 偏差）。
   • 证明了后处理方法在保持预测性能（AUC）的同时，能显著改善特定 $k$ 跳的公平性，且优于现有的公平性基线。

---

4. 实验结果 (Results)

实验在多个真实世界数据集（Polblogs, Facebook, Pokec, Citeseer）和合成数据上进行，对比了 Node2Vec, GCN, GraphSAGE 等标准模型以及 FairWalk, CrossWalk 等公平性基线。

• RQ1: 结构偏差与公平性的关系

  • 发现 $NB^{(k)}$（图的结构偏差）与 $NF^{(k)}$（预测器的公平性）高度相关。
  • 偏差在不同 $k$ 值下分布不均（例如 Polblogs 在 4-hop 处偏差显著），证明了单一聚合指标（如只关注 1-hop）的不足。

• RQ2: 不同跳数间的依赖性

  • 通过边添加（Pre-processing）实验发现，针对特定 $k$ 值优化偏差会级联影响其他跳数的偏差。
  • 这种影响可能是强化也可能是补偿，表明多偏差缓解需要针对特定数据的策略。

• RQ3: 后处理的有效性

  • 性能 - 公平性权衡：
    • 在 $k=1$ 时，后处理几乎不损失 AUC（因为训练边通常就是 1-hop，修改它们不影响测试集评估）。
    • 在 $k=2$ 时，由于现实图的高聚类性，2-hop 节点对常与测试边重叠，导致 AUC 下降较明显。
    • 在 $k \ge 3$ 时，由于测试边较少涉及长距离，性能损失较小，甚至有时因去除偏差噪声而提升 AUC。
  • 独立性优势： 后处理方法保证了优化特定 $k$ 值的公平性不会恶化其他 $k'$ 值的公平性（因为训练图中距离 $k$ 的节点对不影响距离 $k'$ 的指标），实现了模块化的权衡控制。
  • 对比基线： 现有的公平性基线（如 FairWalk）主要优化成对指标（DP/EO），未能有效降低 $k$-hop 偏差，甚至在某些情况下表现更差。

---

5. 意义与局限性 (Significance & Limitations)

意义：

• 理论创新： 重新定义了图链接预测中的公平性，从“边”转向“节点邻域结构”，为理解算法如何影响信息获取的结构性不平等提供了新视角。
• 实用价值： 提出的后处理方法无需重新训练模型，即可作为即插即用的模块，显著提升特定距离下的推荐公平性，特别适用于社交网络中不同层级的关系推荐场景。
• 诊断工具： $NB^{(k)}$ 指标可作为诊断工具，帮助识别图中哪些距离层级存在严重的结构性隔离。

局限性：

• 可扩展性： 计算精确的最短路径距离（BFS）在大规模图上成本较高（尽管使用了稀疏矩阵优化，复杂度仍为 $O(n^2)$）。未来可探索近似最短路径算法。
• 纯结构视角： 目前框架仅基于图拓扑结构，未考虑节点特征（Node Features）。结合特征信息的公平性研究是未来的互补方向。

总结：
这篇论文通过引入 k-hop 公平性，深刻揭示了传统成对公平性在图链接预测中的盲区，并提供了一套有效的理论框架和算法工具，使得我们能够更精细地控制和缓解不同网络距离下的结构性不平等。