标签噪声下基于标签集成视角的降低复杂度图节点分类

《Pattern Recognition》：Label ensemble perspective for reduced-complexity graph node classification under label noise

　　

•首次将噪声标签下的GNN学习问题框定为部分标签学习。•提出LEGNN：无需相似度计算的高效标签集成方法。•避免二次复杂度的可靠性估计和误差累积。•在大规模噪声图上展现强大的鲁棒性和可扩展性。引言图作为现实世界中普遍存在的数据形式，能够表示多种关系结构，例如社交网络[1]和交通系统[2]。图神经网络（GNNs）已成为捕获和分析图结构数据的强大工具，近年来引起了广泛关注[3]。GNNs通常采用消息传递机制，使节点能够通过聚合来自邻居节点的信息来迭代更新其表示[4]。该机制使GNNs在半监督节点分类任务[3]中表现出色，通过允许少量带标签节点将其知识传播给大量无标签节点来实现。传统的半监督节点分类方法通常假设带标签数据足够干净，即带标签节点被正确标注[6]。然而，在现实世界中，这种假设并不总是成立。例如，在推荐系统中使用的用户图，节点标签通常表示用户对产品的偏好。由于缺乏兴趣，一些用户可能会提交任意或重复的反馈，导致噪声节点标签。这些噪声标签已被证明会显著损害GNNs的性能[7]。标签噪声问题已在独立同分布（i.i.d.）数据（如图像）的背景下被广泛讨论，一种常用的解决方案是标签精炼策略[8]、[9]。该策略通常涉及一个两阶段迭代过程：在选定的高置信度标签上更新模型；基于模型预测精炼其他标签。虽然这种策略可以缓解i.i.d.数据上的标签噪声，但它无法为带标签噪声的半监督节点分类（NCLN）提供类似的好处。这是因为在图中只有有限数量的节点拥有标签，因此高置信度标签甚至更少。因此，选择足够可靠的标签进行训练变得更加具有挑战性。为了增强图数据上的标签精炼策略，主流工作将NCLN框定为可靠标签分配任务，在为无标签节点构建可靠的伪标签的同时精炼现有标签[5]。为了更准确地评估可靠性，这些方法依赖于从相似节点聚合标签信息。然而，它们在效率和效果上均存在局限性。首先，对于具有特征维度d的N个节点，为寻找相似节点而引入的成对相似度计算使算法的时间复杂度增加到O(d2N2)，使这些方法效率低下。其次，当噪声水平增加时，简单地鼓励标签聚合可能存在问题：一个节点可能与许多标签不准确的节点相似；直接使用这些错误信号实际上会引入进一步的噪声，最终导致不可靠的标签分配，如图1(a)所示。这一问题可在图1(b)中观察到，我们计算了伪标签的误差率：随着噪声率的增加，现有方法无法发现真实标签。这些错误标签被错误地假设为正确，随着迭代的进行会进一步传播和累积。为了解决这些问题，我们提出了标签集成图神经网络（LEGNN）方法，这是一种针对标签噪声的鲁棒GNN训练的低复杂度方法。LEGNN将NCLN重新表述为基于标签集成的部分标签学习（PLL）任务，其中它从每个节点的一组潜在正确标签中学习分类器[10]。基于这个想法，LEGNN旨在收集信息丰富的多个标签（图1(c)），而不是构建单一可靠标签，避免高复杂度的相似度计算和错误地将错误标签假设为正确的假设。具体而言，我们进行两个主要步骤：使用随机掩码引导邻居上下文，以及采用PLL策略进行模型训练。在引导步骤中，我们为每个节点应用随机邻居掩码并收集由此产生的预测标签作为一个高概率标签集。这很关键，因为标注不准确的邻居节点会显著影响目标节点的标签预测。通过采用这些随机掩码，我们减少了目标节点对任何特定邻居的依赖，从而多样化引导标签集。在模型训练步骤中，我们利用基于部分标签学习（PLL）的策略来聚合引导的标签信息以指导模型。此外，为了进一步抵消引导的高概率标签集中潜在的噪声，我们对称地收集预测概率最小的低概率标签集以提供负监督。我们的主要贡献总结如下：•我们研究了在半监督节点分类中针对标签噪声进行鲁棒GNN训练的挑战。先前的研究未能充分解决这一问题，效率较低且在噪声水平高的场景下性能严重下降。•我们首次将噪声标签节点分类问题框定为部分标签学习任务，并提出了一种带有标签集成的新框架LEGNN。与可靠标签分配方法相比，我们的集成设计利用引导样本的部分标签学习来指导模型训练，避免了对二次复杂度相似度计算进行可靠性评估的依赖，以及当此类评估不准确时出现的误差累积。•大量实验证明了该方法的有效性和高效性。它显示出在高噪声率下的性能下降较小，并且在具有超过十万个节点和一百万条边的数据集上表现出良好的可扩展性。章节摘要相关工作在本节中，我们回顾了处理i.i.d.数据和图结构数据中标签噪声的现有方法。问题形式化我们将图记为G=(V,E)，其中V={vi}i=1N表示N个节点的集合，E?V×V表示边集。X={xi}i=1N构成节点特征集合，其中xi是节点vi的特征。在NCLN的背景下，通常我们提供M个带标签节点VL={vil}i=1M及其噪声标签?L={?il}i=1M，其中?il是vil的噪声标签。我们问题的目标是基于G、X和?L训练一个鲁棒的GNN节点分类器fθ(?)以预测真实标签YU。方法在本节中，我们介绍所提出的LEGNN框架。本质上，LEGNN旨在解决激进的伪标签更新可能导致的有价值标签信息丢失问题。它通过从可靠标签分配转向高概率和低概率标签的对称集成来实现这一目标。此外，它在标签集成过程中采用邻居掩码来构建不同的邻居上下文，从而避免特定邻居的持续影响。实验在本节中，我们进行实验以回答以下研究问题：RQ1：所提出的方法是否在各种噪声设置和标签率下表现出鲁棒性？RQ2：所提出方法的可扩展性如何？RQ3：与使用复杂模块的方法相比，所提出方法是否涉及更低的计算成本？RQ4：构建这样的标签集可能会引入更多错误标签（或更多噪声）。然而，为什么这不会导致性能下降？RQ5：结论我们提出了LEGNN，一种从标签集成角度出发的图节点分类的低复杂度框架。LEGNN不是激进地过滤到单一"干净"伪标签，而是将来自掩码引导邻居上下文的多样化预测聚合到候选标签集中，并在该集合上优化部分标签目标。这种构建方式保留了严格过滤倾向于丢弃的合理真实标签，提高了质量。CRediT作者贡献声明Rui Zhao：撰写——审稿与编辑，撰写——初稿，可视化，验证，软件，方法学，调查，形式化分析，数据整理，概念构思。Bin Shi：撰写——审稿与编辑，监督，资金获取，形式化分析，概念构思。Zhiming Liang：可视化，验证，软件。Jianfei Ruan：撰写——审稿与编辑，方法学，概念构思。Kai Sun：撰写——审稿与编辑，监督。Bo Dong：监督，资源。利益冲突声明作者声明他们不存在任何可能影响本论文中报告的工作的已知竞争经济利益或个人关系。致谢本研究部分得到陕西省重点研发项目（编号2024PTZCK-89）以及中国国家自然科学基金（编号62406242、62672397和62476215）的支持。Rui Zhao|Bin Shi|Zhiming Liang|Jianfei Ruan|Kai Sun|Bo Dong|Lu Lin