基于成对约束的对比半监督聚类在复杂网络中识别关键节点的方法

《Expert Systems with Applications》：Contrastive Semi-Supervised Clustering Based on Pairwise Constraint for Identifying Influential Nodes in Complex Networks

　　

• •
  一种半监督框架在标签有限的情况下识别关键节点。
• •
  成对约束将有限的标签信息与常规等价信息整合在一起。
• •
  常规等价性同时为约束和节点特征做出贡献。

引言

复杂网络用于建模现实世界系统中实体之间的相互关系，如交通系统、社交网络、万维网和蛋白质-蛋白质相互作用。识别关键节点——即占据关键位置并发挥核心作用的节点——对于理解并利用这些网络至关重要。该任务具有重要的实际应用价值，包括控制谣言或疾病的传播以及设计精准营销策略 Chen, Lü, Shang, Zhang, & Zhou (2012)。因此，大量研究工作致力于开发关键节点识别方法 Jingdong, Qizi, & Fanqi (2020)。

传统上，中心性度量方法，如度中心性、特征向量中心性、PageRank 和 K-shell 分解 Hu, Yang, Duo, & Zhu (2022); Kitsak et al. (2010)，被用于量化节点影响力，得分最高的节点被视为关键节点。然而，随着网络结构日益复杂，这些方法已被证明不再适用。因此，研究人员转向机器学习，通过利用复杂的节点关系和结构特征来识别关键节点 Zhao, Jia, Huang, Zhou, & Fang (2020a)。深度学习在其他领域的成功推动了针对此任务专门模型的发展 Bhattacharya, Nagwani, & Tripathi (2023); Yu, Wang, Fu, Chen, & Xie (2020); Zhang, Li, Wei, Liu, & Li (2022a)。其中，图神经网络（GNNs）由于其固有的处理图结构数据的能力而受到了广泛关注。例如，InfGCN Zhao, Jia, Zhou, & Zhang (2020b) 将邻接矩阵和四个经典结构特征整合到 GCN 中以学习节点表示；CGNN Zhang, Wang, Jin, Song, & Li (2022b) 通过收缩算法导出特征矩阵并输入 GNN 来区分关键节点和非关键节点；M-RCNN Ou, Guo, Xing, & Liu (2022) 采用三种低成本中心性度量，利用广度优先搜索裁剪固定大小的邻域，并通过三个独立矩阵编码多层次结构。然而，这些高级方法是有监督的，需要充足的标注数据进行训练。这带来了两个关键挑战：(1) 标签稀缺：许多现实网络中包含大量未标注节点；(2) 标注成本：人工标注往往代价高昂或不可行，因此需要能够在极少监督下运行的方法。虽然无监督方法提供了一种替代方案，但我们的初步实验表明，它们在关键节点识别方面的性能可能有限。为解决这些局限性，我们将关键节点识别视为半监督聚类任务，并提出一个在有限标注数据下运行的半监督图聚类框架。

半监督聚类通过融入有限的标签信息来提升聚类性能。一种常见的方法是使用成对约束，即必须链接（要求两个节点属于同一聚类）和不能链接（阻止共同聚类） Berahmand, Bahadori, Abadeh, Li, & Xu (2024); Chen, Tang, Zhang, & Feng (2022); Ren et al. (2019); Wang, Zou, Wang, Liu, & Yuan (2023)。直观地，已标注节点可以定义此类约束：具有相同标签的节点构成必须链接，而不同标签则意味着不能链接。然而，已标注节点的稀缺性限制了基于约束方法的影响力。一些研究通过利用结构相似度来丰富成对约束，如基于嵌入的距离 Fogel, Averbuch-Elor, Cohen-Or, & Goldberger (2019) 或邻居差异度量 Berahmand et al. (2024)。但这些方法往往难以准确区分关键节点。虽然关键节点通常表现出相似的结构特性，但它们可能位于网络的遥远区域，没有直接连接或重叠邻域。这种拓扑差距从根本上限制了传统相似度度量的适用性。

为解决上述问题，我们提出使用常规等价（RE）相似度为未标注节点构建成对约束，从而扩展约束集。我们利用 GCN 生成结构感知的节点嵌入，随后通过 k-means 将其聚类为关键节点和非关键节点。此外，我们设计了基于成对约束的对比学习损失，结合 Kullback-Leibler（KL）散度损失，以联合优化聚类。这产生了 PCGCN，一个对比式半监督图聚类框架，通过成对约束融入有限的标注数据和 RE 相似度，以识别复杂网络中的关键节点。我们的主要贡献如下：

• (1)
  我们提出了 PCGCN，一个用于关键节点识别的半监督深度聚类框架，从有限的节点标签和常规等价性构建成对约束。据我们所知，现有方法尚未在该类框架中整合这两种成对约束来源。
• (2)
  我们通过引入 RE 相似度来推断未标注节点之间的成对约束，从而缓解标签稀缺问题，在有限的标签约束之外提供额外的结构监督。
• (3)
  大量实验表明，PCGCN 通常比所采用的基于中心性和无监督/半监督比较方法具有更好的性能，同时与有监督方法保持竞争力。

章节摘要

相关工作

鉴于 PCGCN 是一个用于关键节点识别的半监督聚类模型，以下综述侧重于关键节点识别和图聚类（特别是半监督聚类）的相关研究。

关键节点识别。 节点影响力量化的演进从传统中心性度量方法，如度中心性、特征向量中心性、PageRank 和 K-shell Hu et al. (2022); Kitsak et al. (2010)，发展到机器学习

符号说明与问题描述

给定一个网络 G，其节点集为 $V={\left\{v_i\right\}}_{i=1}^n$，边集为 $E={\left\{e_{ij}\right\}}_{i,j=1}^n$，我们旨在通过半监督聚类识别关键节点，形式化为：$$\{C_{\text{inf}},C_{\text{noninf}}\}=f(G,{\left\{l_v\right\}}_{v\in V_L}|\mathbf{\Theta })$$其中 V_L?V 是一个小型已标注子集，l_v?∈?{0, 1} 表示节点标签，$r_1=|V_L|/|V|$ 表示标注比例。我们使用基于 GCN 的模型来近似 f，该模型融合了网络结构和有限的标签信息，并通过整合从标签信息和 RE 推导出的成对约束来估计 Θ。

方法

本节介绍所提出的 PCGCN 框架，如图 1 所示。PCGCN 由三个核心组件组成：(1) 特征构建模块，从网络拓扑构建节点特征以增强信息；(2) 图嵌入模块，通过 GCN 将节点特征与邻接矩阵整合以生成节点嵌入；(3) 聚类模块，基于学习到的嵌入将节点划分为关键节点或非关键节点类别。为实现

实验

本节对 PCGCN 在八个网络上的表现进行了全面评估和讨论。我们首先将 PCGCN 与 12 种基线方法进行比较（第 5.2 节），随后进行消融实验以评估其关键组件和不同节点特征配置的贡献（第 5.3 节）。然后我们进行关键参数和 RE 推导特征数量的敏感性分析，包括探索不同 r₂ 值下 RE 推导的成对约束的可靠性（

结论

本文提出了 PCGCN，一种基于成对约束的对比式半监督聚类框架，用于识别复杂网络中的关键节点。该框架首先构建包含 RE 相似度和节点度的节点特征。这些特征与网络结构一起由 GCN 处理以生成节点嵌入，随后用于区分关键节点和非关键节点。为增强

CRediT 作者贡献声明

Bing Sun：数据管理、软件、验证、方法论、写作 - 初稿。Yanmei Hu：概念化、资金获取、方法论、监督、软件、写作 - 初稿、写作 - 审阅与编辑。Jie Wei：软件、验证。Xianghui Liu：数据管理、验证。Xing Zhu：概念化、调查、监督。Xiaochuan Tang：概念化、监督、方法论。

利益冲突声明

作者声明他们没有已知的相互冲突的财务利益或人际关系，这些可能影响到本文所报告的工作。

Bing Sun|Yanmei Hu|Jie Wei|Xianghui Liu|Xing Zhu|Xiaochuan Tang