结构熵引导的图神经网络用于含分布外数据的半监督图分类

《Neurocomputing》：Structural entropy guided GNN for semi-supervised graph classification with out-of-distribution

　　

摘要

半监督图学习处理分布外（OOD）样本的研究已引起广泛关注，因为在现实世界的应用场景中，OOD情况十分普遍，尤其是当有标签图仅占整个数据集的极小部分时。然而，大多数现有方法主要聚焦于OOD检测。尽管已有少数方法被提出用于处理含OOD设置的半监督图分类问题，但它们往往因分布内（ID）与OOD样本之间的结构冗余和特征重叠而遭受性能下降。为了解决上述局限性并丰富方法学体系，本文提出了一种名为结构熵对比学习（SECL）的鲁棒方法，用于处理含OOD样本的图分类任务。具体而言，SECL首先构建一棵具有最小结构熵的编码树，以消除图中的冗余结构信息，生成能够区分ID与OOD样本的判别性特征表示。随后，采用对比学习策略，促进同一ID类别内样本的聚合，同时增强不同ID类别之间的分离性。与此同时，该策略进一步加强了ID与OOD样本之间的可分性，有效缓解了特征重叠的风险。在六个基准图数据集上进行的广泛实验表明，SECL显著减轻了OOD数据的不利影响，并在图分类任务上取得了优于现有最先进方法的性能。

引言

图是用于表示多样对象及其复杂关系的普遍数据结构[1]。作为图机器学习的核心任务之一，图分类旨在预测整个图的类别，随着其广泛应用而受到越来越多的关注。尽管近年来现有的图分类方法已取得显著进步，但其成功高度依赖于大规模有标签数据。然而在实际应用中，有标签图数据不仅获取成本高且耗费人力，还需要高质量的标注，例如社交网络中用户关系的人工标注以及生物网络中蛋白质-蛋白质相互作用[2]、[3]。

为缓解这些问题，半监督图学习因其图分类上的卓越性能而受到广泛关注。最近，HSE-OGC[4]构建了多个混合子空间，并在每个子空间中优化图结构，以有效利用无标签数据，利用子空间的多样性在半监督训练期间减少OOD干扰，同时提高从已标记到未标记的分布内样本的可靠标签信息传播。LCGNN[5]将对比学习扩展到半监督图分类场景，使用标签对比损失增强类内聚合和类间分离性，使得在有限标签下能够有效分类。PCL[6]在半监督框架中整合了伪标签生成与对比学习，通过识别可靠的负样本对替代传统分类损失来处理标签噪声，提高了在图数据集上的性能。

尽管半监督图分类取得了显著进展，但这些方法通常假设所有无标签数据都属于已知类别，而忽略了无标签图可能是分布外（OOD）样本这一事实[7]。在分子图药物发现中，有标签图（ID）指经湿实验验证的活性化合物（已知类别），而无标签图包括具有未注释的新颖分子骨架或官能团的新合成分子（OOD，未知类别）。在社交网络欺诈检测中（例如REDDIT-MULTI-12K），有标签图（ID）是标注为合法或欺诈的用户交互子图，而无标签子图包含具有未见过交互拓扑的新颖欺诈模式，偏离已知结构（OOD）。在计算机视觉图分类中（例如MNIST/CIFAR10超像素图），有标签图（ID）是已知类别手写数字或物体的超像素拓扑图，而无标签图包括模糊/遮挡目标或非目标物体的扭曲拓扑图（OOD）。在工业系统的带属性图分类中，有标签图（ID）是标注为正常或故障的设备运行子图，而无标签子图包含具有异常节点属性和标签集未覆盖的拓扑关联的新颖故障模式（OOD）。本质上，OOD样本来源于标签ID样本未覆盖的新颖结构或属性（例如扭曲拓扑、新图案），而ID样本符合目标类别在拓扑结构和节点属性上的已知分布，完全覆盖了标记训练集的特征。事实上，OOD在现实世界应用中广泛存在，尤其是当有标签图仅占整个数据集的极小部分时。例如，在药物发现中，无标签分子图可能包含未知类别的新活性化合物。在信息欺诈检测中，无标签数据可能包含伪装为已知类别的新颖结构。如果在图分类中忽视这些未知类别，如图1（a）所示，已知类别和未知类别的分布严重重叠，这可能导致性能低下，且OOD样本将被直接分类为已知类别。因此，在含OOD的半监督图分类中，准确分类已知类别同时检测未知类别已成为一项紧迫的挑战[4]。

针对含OOD样本的图数据，已提出大量方法，其中大多数聚焦于从数据集中检测OOD样本。对于含OOD的图分类，仅有少数研究被提出，包括UGNN[7]和SGOOD[8]。尽管这些现有工作为含OOD的图分类奠定了基础，但仍存在显著缺陷。这些局限性恰好反映在推动我们工作的两个关键问题上。原始图中存在冗余边和平凡节点属性，引入了冗余诱导的噪声，掩盖了核心的ID/OOD判别信号。虽然鲁棒学习方法利用降噪来减轻干扰并提升判别能力，但它们忽略了结构冗余与ID/OOD任务之间的内在联系，在去噪时未能保留关键特征。这种结构冗余严重掩盖了ID与OOD图之间的本质判别特征。另一方面，如图1（b）所示，已知类别和未知类别之间仍存在明显的分布重叠。同时，在半监督OOD场景中，稀缺的未知类别标签和固有的已知-未知特征相似性导致分布重叠，存在将OOD样本误分为已知类别的风险。这种普遍的特征重叠进一步削弱了ID与OOD样本之间的边界判别力。综上所述，这些挑战使得在图任务中准确区分已知类别与OOD样本同时保持高已知类别分类精度变得极其困难。

为丰富含OOD的半监督图分类并缓解上述两个问题，本文提出了一种基于结构熵和对比学习的新方法，用于含OOD的半监督图分类（SECL），如图1（c）所示，该方法在ID与OOD样本之间展现出更强的判别能力。首先，模型通过最小化原始图的结构熵生成一棵编码树，以减轻冗余信息的干扰，从而在提取核心特征的同时去除冗余信息。具体而言，编码树损失的设计受到信息论中最小冗余原理的启发，通过结构熵最小化构建的编码树天然满足结构熵的下界，其中MERGE操作贪心合并熵增最小的节点对以保留图结构的有序划分，而DROP操作将树压缩到固定高度同时最小化熵损失。这种双操作机制确保冗余结构信息被有效消除，同时不会丢弃ID与OOD样本之间的核心结构差异，从而为后续对比学习提供判别性和可分性的特征表示，并增强了所提方法的理论一致性。这使得模型能够集中于已知类别与OOD之间的核心差异。其次，为区分已知类别与OOD，该方法使用已知类别与OOD之间的对比学习，确保相同类别的表示一致，同时最大化不同类别（不同已知类别与OOD）之间的距离，从而将已知类别分布与OOD分布分离开来。最后，SECL通过两个模块的协作，最终实现了有效的无OOD干扰分类。

本文的贡献如下：

- 我们提出了一种名为SECL的新方法。我们探索了含OOD的半监督图分类问题，解决了现有半监督方法忽略无标签数据中OOD样本的关键缺陷，从而促进了图分类效率和准确性的提升。

- 所提模型利用原始图结构熵最小化生成编码树，有效减少了图中的冗余信息，同时提取了核心判别特征。此外，将OOD样本作为对比学习的负样本，确保类内表示一致并最大化类间距离，从而将已知类别的特征分布与OOD分离开来。

- 在六个图分类数据集上进行了广泛实验以验证所提SECL在不同设置下的有效性，确认了其能够在检测OOD样本的同时实现准确的已知类别分类的能力。

章节摘要

半监督图分类

半监督图分类近年来受到越来越多的关注。早期的半监督图分类方法[9]采用了标签传播的概念。例如，Zhu等人提出了图结构上的标签平滑假设[10]，该方法基于节点相似性将标签从少量有标签样本传播到无标签样本，从而对齐图数据的拓扑关系。这种方法将标签从少量……

预备知识与问题定义

我们首先定义关键符号以及含OOD的半监督图分类任务。

1) 数据集，其中有标签图和代表第个有标签样本，无标签图和代表第个无标签样本。

2) 对于，有标签数据集包含k个类别，记为，表示的标签。

3) 对于，无标签数据集包含个类别，表示的标签，且属于未知类别。由于OOD的存在，有。

4) 每个图由节点集、边集和……

方法

所提方法的总体框架如图2所示，包括图表示模块、编码树模块和对比学习模块。为有效提取图表示，图表示模块使用带有注意力池化的GAT编码器生成图表示。它首先通过自注意力机制对节点重要性进行加权，过滤掉重要性低的平凡节点，然后聚合节点特征以捕获全局结构框架和核心……

实验

在本节中，我们在六个公开数据集上进行实验，并与多种基线方法进行比较，包括基于图核的方法、基于GNN的方法以及半监督图分类方法，以验证所提方法的有效性。表2展示了六个数据集的详细统计信息，包括图的数量、类别数、已知类别数与未知类别数、标签比例及其他相关详细信息。

结论

本文提出了用于含OOD样本的半监督图分类的SECL方法，该方法在不依赖大量有标签数据的情况下实现了鲁棒且有效的性能。编码树基于结构熵构建，捕获了ID图结构的本质特征，同时避免了冗余信息。此外，通过对比学习缓解了ID与OOD样本之间的重叠。在公开数据集上的广泛实验证明了其优越的……

CRediT作者贡献声明

冯伟珂：写作——审阅与编辑，写作——初稿撰写。苏美红：写作——审阅与编辑。许雅玲：写作——审阅与编辑。李岩：写作——审阅与编辑。马阳：写作——审阅与编辑。

利益冲突声明

作者声明不存在可能影响本文工作的已知竞争性经济利益或个人关系。

致谢

本工作得到国家自然科学基金（编号62272336）和教育部人文社会科学研究项目（24YJCZH257）的支持。山西省基础研究计划（202303021221142）资助。

冯伟珂目前正在太原科技大学计算机科学与技术学院攻读硕士学位，研究方向为鲁棒学习和图机器学习。

冯伟珂 | 苏美红 | 许雅玲 | 李岩 | 马阳

太原科技大学计算机科学与技术学院，太原，030024，中国