冻结图聚类的选择性超图精炼

# 选择性超图细化用于冻结图聚类
来源：https://arxiv.org/html/2609.03265
作者：Zimo Si
单位：澳门大学理学院数学系
单位：中国澳门特别行政区
单位：邮箱：[email protected]

###### 摘要
现有的图聚类方法通常通过优化模型参数和节点表示来提升聚类性能。然而，对于已经训练并冻结的模型，如何进一步改进其聚类结果的有效方法仍然有限。我们研究了针对冻结图聚类的后处理方法。在检查点固定后，该过程不使用标签，也不更新模型参数、节点表示或原始图结构。相反，它利用属性超图来补充普通图难以表达的高阶关系，从而优化现有的聚类分配。由于全局超图细化可能同时带来性能提升和错误更新，我们提出了选择性超图细化方法。该方法从超图生成候选残差方向，并利用图结构、节点属性和匹配的零假设证据评估其可靠性。仅对有足够支持证据的节点进行更新，否则保留其原始分配。进一步分析表明，节点是否改变聚类由其原始分配间隔和细化方向强度共同决定。在可控的通用套件评估中，15个骨干-数据集单元中有13个具有正的平均宏增益，一个产生完全无操作，一个为负。单元等效宏增益为0.066个百分点（95%自举置信区间，[0.030, 0.107]个百分点），而平均仅有0.209%的硬分配发生了变化。更广泛的15组合原生接口评估产生了0.137个百分点的宏增益，平均变化比率为0.375%。这些结果表明，冻结的聚类输出在训练后仍保留有限但可测量的细化空间。其效果在不同骨干-数据集对上存在异质性，且更广的覆盖范围也增加了负迁移的风险。
关键词：图聚类；超图学习；冻结模型；无标签后处理；聚类分配；选择性细化

## 1 引言
现有的图聚类方法主要通过优化模型参数、节点表示或图结构来提高聚类性能。然而，进一步改进已经训练并冻结的模型的聚类输出仍然具有挑战性。因此，我们研究针对冻结图聚类的无标签后处理：即在不更新模型参数、节点表示或原始图结构的情况下，是否能够改进现有的聚类分配。

普通图主要描述节点之间的成对关系，而属性超图则可以补充由属性相似性诱导的高阶关联。对于冻结模型，此类信息无法再通过表示学习融入，只能用于优化现有的聚类输出。我们的实验揭示了通过超图细化仍有进一步改进的空间，但并非每次修改都是有益的。更广的细化覆盖范围可以触及更多潜在错误，但同时也会扰乱原本正确的分配。因此，关键问题在于应接受哪些候选细化以及干预应扩展到何种程度。

受此观察启发，我们提出了选择性超图细化方法。SHR使用属性超图在原生聚类坐标系中生成候选残差方向。然后，它通过结合图结构、节点属性和匹配的零假设证据来评估不同的细化状态（无需标签）。只有获得足够支持的修改才会被保留；否则，原始分配保持不变。我们进一步发现，在全局细化强度相同的情况下，不同节点在不同强度水平下改变其聚类分配。因此，我们定义了临界细化强度 η_crit，即节点首次改变其当前聚类分配所需的最小强度。

我们在多个图聚类骨干和数据集上评估了SHR。结果表明，在有限的细化覆盖下，聚合增益为正，同时存在显著的骨干-数据集异质性。修复-损害分析进一步表明，更广的覆盖范围为修复创造了更多机会，但也增加了负迁移的风险。然而，现有的无标签信号尚无法一致地区分有益和有害的细化。

本文的主要贡献如下：
1. 我们为冻结图聚类的无标签后处理制定了框架。在检查点固定后，模型参数、节点表示和原始图结构保持不变，仅优化现有的聚类分配。
2. 我们提出了选择性超图细化方法。该方法使用属性超图生成候选细化，并通过图结构、节点属性和匹配的零假设证据评估无标签的细化状态。当证据不足时，保留原始结果。
3. 我们刻画了细化覆盖范围与收益-风险行为之间的关系。临界强度分析解释了全局细化下的隐式节点选择。跨骨干的修复-损害实验进一步表明，更广的覆盖范围提供了更多修复机会，同时增加了负迁移的风险。

## 2 相关工作
### 2.1 图聚类与超图学习
现有的深度图聚类方法通常通过联合优化节点表示、图结构或聚类目标来提高聚类性能。它们的有效性在很大程度上依赖于训练期间模型参数和节点表示的持续更新。普通图中的边仅连接两个节点，而超边可以连接多个节点，从而表示高阶关联。因此，超图在图聚类和表示学习中得到日益广泛的应用。

HCN通过超图平滑和结构对齐学习聚类表示。HCN-PAI通过高阶传播填补缺失属性，并进一步优化聚类结果。JKHR联合学习共识核和超图正则化，以整合高阶结构信息。联合图-超图表示、高阶编码和多通道超图模型也被用于整合不同形式的关系信息。这些研究表明，高阶关系可以补充普通图结构，但大多数方法需要在训练期间重新学习节点表示、图结构或聚类空间。

相比之下，我们考虑的是已经训练完成并保持冻结的图聚类骨干。属性超图不参与新的表示学习，仅作为辅助信息用于优化现有的聚类分配。

### 2.2 训练后适应
对于已经训练好的图模型，测试时适应提供了一种无需重复整个训练过程即可提升性能的方法。现有的图测试时适应方法通常使用未标记的测试数据继续调整局部模型参数、节点表示或传播机制。例如，ASSESS在测试时通过自适应子图选择和原型监督来适应预训练模型。其他方法通过自监督低秩特征调整来适应测试图上的表示，以解决结构偏移问题。尽管TOTF采用了“训练一次然后冻结”的编码器设计，但它在冻结后仍然提取共享的跨视图信息并训练一个辅助图网络以完成聚类。

这些方法减少了重新训练完整模型的需求，但在测试或下游聚类过程中仍然改变模型表示、传播过程或决策边界。SHR施加了更严格的约束：检查点固定后，骨干网络、节点嵌入和原始图结构保持不变，所有后续操作仅作用于现有的聚类分配。

### 2.3 关系后处理
另一类工作不继续适应基础模型，而是利用额外的关系信息来后处理现有预测。在固定基础预测后，Correct and Smooth通过标记节点的残差传播和预测平滑来优化半监督节点分类结果。NLCS进一步引入了非线性和高阶关系建模，允许残差沿着更复杂的节点关系传播。图结构也被用于其他形式的预测后处理。HGPF针对预训练的异构GNN，在基础模型训练后添加一个辅助关系推理模块以改进分类。

这些研究表明，额外的关系信息可以进一步优化基础模型的预测。然而，它们主要关注监督或半监督节点分类，并且有些仍然依赖于标签或训练后参数优化。SHR则针对已经完成聚类的冻结模型。检查点固定后不使用标签，也不创建新的聚类空间。相反，一个辅助超图选择性地优化现有的聚类分配，当证据不足时则保留原始结果。

### 2.4 不确定性建模与状态平均
当多个候选模型或聚类状态都合理时，选择单一最优解会忽略模型选择带来的不确定性。贝叶斯模型平均通过加权多个候选模型来保留这种不确定性，这是一种经典方法。相关思想也被应用于聚类。聚类集成方法通过概率或结构模型整合多个基础聚类。使用超图重构的动态锚点方法进一步从基础聚类构建并优化共识结构。clusterBMA使用近似后验模型概率对多个无监督聚类结果进行加权，得到概率性的最终聚类分配。

与此同时，关于安全多视图聚类的研究表明，增加视图并不一定能提高聚类性能，并明确寻求防止因附加视图而导致的性能下降。这一关切与本文考虑的收益-风险问题密切相关，尽管这些方法仍通过端到端训练学习新的多视图聚类表示。

SHR借鉴了在几个合理候选者中保留不确定性的原则，而不是构建新的贝叶斯聚类模型。对于冻结的原生软聚类分配矩阵 Q_0，不同的细化状态代表不同的细化覆盖范围和强度。SHR根据无标签证据和每个状态的覆盖复杂度分配相对权重，同时包括保留 Q_0 不变的无操作状态。与上述通过整合多个聚类结果或重新估计共识聚类的贝叶斯聚类方法不同，SHR始终在原生聚类坐标系内优化 Q_0，不创建新的聚类空间。

## 3 预备知识
###### 定义 3.1（无监督图聚类）
考虑一个属性无向图 G=(V,E,X)，其中 V={v_1,...,v_N} 是节点集，E 是边集，X∈R^{N×F} 是节点属性矩阵，A∈{0,1}^{N×N} 是对应的邻接矩阵。无监督图聚类旨在不使用节点标签的情况下，基于图结构和节点属性将 N 个节点划分为 K 个聚类。

对于一个已经训练完成的图聚类模型，用 Z_0∈R^{N×d} 表示其冻结的节点表示，用 Q_0∈[0,1]^{N×K}, ∑_{k=1}^K Q_{0,ik}=1 表示其软聚类分配矩阵。其中，Q_{0,ik} 是节点 v_i 对聚类 k 的软分配。节点 v_i 当前的硬聚类分配为 a_i = arg max_k Q_{0,ik}。

###### 定义 3.2（属性超图）
不同于普通图中仅连接两个节点的边，超边可以同时连接多个节点。我们将属性超图定义为 H=(V, E_h)，其中 E_h={e_1,...,e_M} 是超边集。其节点-超边关联矩阵为 B∈{0,1}^{N×M}，B_{ij} = 1 若 v_i∈e_j，否则为 0。

遵循超图传播的标准归一化形式，令 W 表示超边权重矩阵，D_v 和 D_e 分别表示节点度和超边度矩阵。超图传播算子为 P_h = D_v^{-1/2} B W D_e^{-1} B^T D_v^{-1/2}。

节点度和超边度分别由 d(v_i) = ∑_{j=1}^M W_{jj} B_{ij} 和 δ(e_j) = ∑_{i=1}^N B_{ij} 给出，其中 D_v = diag(d(v_1),...,d(v_N))，D_e = diag(δ(e_1),...,δ(e_M))。

我们的实现假设...