专题解读 | 图结构公平性

1. 图结构公平性的基本概念

图卷积网络（GNN）在图上的半监督学习任务（如节点分类）上取得了成功。但最近的研究表明，GNN对不同结构下节点的预测表现存在明显偏差，比如GNN通常在具有丰富邻居信息的高度节点上表现良好，但在低度节点上表现较差。GNN对于图结构的明显偏好被认为是「图结构公平性」，由于这种图结构的公平性暂时缺乏理论上的解释，导致其在一定程度上影响到了GNN在现实场景中的应用。

2. 论文介绍

本文将介绍2篇有关结构公平性的论文，并对图结构公平性这一问题进行简要探讨。

2.1 GRAPHPATCHER：通过测试时增强来缓解图神经网络的度偏差（NIPS 2023）

Motivation

最近的研究表明，图神经网络 (GNN) 对节点度表现出强烈的偏见，现有的研究通过派生指定的 GNN 架构或专门针对低度节点的训练策略来解决此问题。虽然这些方法很有效，但它们无意中创建了一种人为的分布不均场景，其中模型在训练期间主要甚至只观察低度节点，导致 GNN 原本表现良好的高度节点的性能下降。鉴于此，其提出了一个测试时增强框架，即 GRAPHPATCHER，以增强任何 GNN 在低度节点上的测试时泛化。具体而言，首先通过采样的方式，逐渐移除目标节点周围的邻居节点，然后利用GRAPHPATCHER 迭代生成虚拟节点以修补这些人造的低度节点，并通过原有的预测来监督这一过程。通过这种方案，GRAPHPATCHER 不仅学会了如何增强低度节点（当邻域严重损坏时），而且还保留了 GNN 在高度节点上（当损坏程度较低时）的原有卓越性能。

Observation

1）将节点按照度大小进行分组后，分类的准确率随着度增大呈现上升趋势。

2）此前方法往往以牺牲高度节点上的预测准确率为代价，来提高低度节点上的准确率。

Method

本文提出的图补丁模型十分简明，即通过一个补丁网络在使用原GNN在进行图上推理时，针对目标节点生成虚拟邻居节点，使得最终分类性能提升。

流程图展示了该补丁网络在Test-time时的训练过程：1）首先在原始的ego-graph中不断地以随机采样的方式丢弃掉目标节点的邻居节点，得到不同阶段的corrupted ego-graph；2）然后通过补丁网络为节点生成虚拟邻居节点，使得corrupted ego-graph的阶段能够进行回退；3）为了监督补丁网络训练，使得其生成的虚拟邻居能够提供真实有效的信息，本文将对齐 「修复后目标节点预测KL散度」 与 「上一阶段中目标节点KL散度」设置为优化目标。

Experiment

本文在常用的节点分类数据集上进行实验，并按照degree分组进行性能测试，结果表明该模型能够在不严重损害高度节点的预测性能的同时，提高在低度节点上的预测准确率。

为了说明该方法能够应用于任意方法预训练得到的GNN，所以也在自监督模型上进行了测试

Comments

本文方法不算复杂，优化过程也采用的是迭代的方式，并没有其他更加精妙的设计，但也有可取指出：1）在测试时场景下，由于缺乏标签信息，可以通过KL对齐的方式来进行监督训练；2）利用正反互逆的过程，来逐步构建起高度节点和低度节点之间的联系。

2.1 图神经网络中的标签位置偏差（NIPS 2023）

Motivation

此前研究已经通过实验发现了GNN往往在高度节点上表现好，低度节点上表现较差，然而这种实验性的观察并不能得出，节点的度是影响图结构公平性的本质诱因，这一结论，本文提出了一个新的结构偏差——标签位置偏差，并通过实验的方式发现，这种标签位置偏差更能反应GNN对图结构的偏见。

Proposed new metric

本文提出的标签位置偏差本质上是指：距离带标签节点“更近”的节点往往获得更好的预测准确性，并基于这一理念提出了衡量标签位置偏差的度量指标，标签接近度分数（LPS）：

其中为矩阵Personalized PageRank矩阵，用来指示带标签的节点。如果把看做是节点和节点之间的节点接近度，不难发现，对于每个测试节点，其 LPS 表示其与所有标记节点节点的节点接近值总和。

Observation

为了验证本文提出的标签接近度分数（Label Proximity Score）优于此前的一些结构公平性度量指标：节点度（Degree），到带标签节点最短路径距离（Shortest Path Distance），本文进行了一些简单的CaseStudy，即按照不同的公平性度量指标进行分组后，统计各组的预测准确率，可以明显观察到：

1）标签位置偏差在所有 GNN 模型和数据集中都很普遍。

2）虽然度数和最短路径距离 (SPD) 可以在一定程度上反映不同的性能，这表明具有较高度数和较短 SPD 的节点往往表现更好，但这些趋势缺乏一致性，不能完全反映标签位置偏差。

3）标签接近分数 (LPS) 在所有数据集和模型中始终表现出与性能差异的强相关性。

4）仅依赖于图结构的标签传播（LP）表现出更强的标签位置偏差。

Method

本文任务导致图结构不公平的本质在于不同节点的LPS值存在差异，为了解决这一问题，本文提出使用图结构学习的方式来学习一个新的图结构来代替原图结构，使得在新的图结构下，不同节点之间的LPS尽可能接近，于是提出以下优化目标：

为了解决上述带约束的优化问题，本文使用增广拉格朗日法将其转换为下面优化问题：

对于的梯度可得：

利用对偶上升法进行迭代求解：

Theory

1） 不带约束的原始优化目标的最优解本质上就是APPNP算法中的message passing矩阵。

2）带约束的原始优化目标的最优解，会使得所有节点受到带标签节点的影响分数总和保持一致。其中节点对节点的影响分数指的是，节点的下一层表征对节点的表征的各维度微分之和。这一点很好理解，因为上面提到过了LPS用的是APPNP作为权重矩阵，所以通过APPNP与特征之间的的微分建立起了联系

Improvement

之前提出的优化方法会导致学到的结构是一个dense矩阵，这对于大图来说会带来不可承受的计算资源损耗，为了降低该方法的复杂度，采用了正则进行约束：

并通过块坐标下降法来进行迭代优化，得到近似解：

Experiment

本文首先在常用图分类数据集上进行实验，表明其方法在一般图分类任务上的的优越性。

本文采用公平性研究中常用的指标来进行，模型对于不同结构分组的公平性

Comments

本文提出了一个新的用于衡量图结构公平性的指标LPS，相比于此前工作中常用的度公平性，该指标可能更接近与结构公平性的本质原因。从某种意义上来讲，高度节点由于存在更多的边，所以往往会更”靠近“带标签的节点，有更高的LPS，低度节点正好相反。但这篇文章提出的解决方法是重新学习一个图结构，感觉会有点小题大作之意，可能采用GraphPatcher中的做法，通过对原图结构进行修补的解决方法更为合适。

3. 总结

图结构公平性这一概念的提出源于研究者发现GNN对于低度节点预测性能往往不如对高度节点的预测性能，所以此前针对这一问题的研究主要都是关注于GNN的度公平性问题。针对GNN表现出来的度公平性偏差，一种可能的解释是GNN往往需要利用到待预测节点丰富的邻域信息来帮助提高预测性能，而低度节点缺乏丰富的邻域信息，导致GNN在这些节点上预测性能下降。一系列针对改进GNN度公平性的工作层出不穷，介绍的第一篇论文GRAPHPATCHER即是其中之一，这些工作大体可以分为三类：1）针对数据，比如为低度节点补充有效的领域信息（如：SAILOR，GRADE，GRAPHPATCHER等）；2）针对模型，比如在训练时人造低度节点（对高度节点进行邻域采样），对齐GNN在高度节点和低度节点上的表现（如：TUNEUP，Tail-GNN等）；3）同时针对数据和模型。

然而图结构公平性并不仅仅局限于度公平性，介绍的第二篇论文就提出了一个新的概念：标签位置偏差。这一概念的核心思想在于，作者认为距离带标注节点（训练集）"更近"的节点往往会有更好的预测表现，并给予这一思想提出了用于度量目标节点与带标注节点集合合成距离的指标，标签相近分数（Label Proximity Score, LPS）。实验表明，相比于节点的度，当使用标签相近分数作为衡量指标时，结构公平性的现象更加明显，这表明LPS可能更有效。这一新概念的提出为图结构公平性这一研究问题开辟了新的视角，然而相比节点的度，LPS是否是结构公平性更加本质的诱因，LPS的理论依据是什么，以及如何利用这一指标更好的指导模型设计，这些都还有待探索。