基于平衡锚点低秩表示的多视图图聚类

《Signal Processing》：BALM: Balanced anchor-based low-rank multi-view graph clustering

　　

摘要

图聚类，尤其是以其代表性范式——谱聚类——为代表的方法，在大规模多视图场景中面临严重的计算瓶颈。尽管近期的锚点图方法通过用紧凑的基于锚点的表示来替代完整相似度图来提升可扩展性，但它们往往以牺牲聚类质量为代价来换取效率。其核心局限在于未能对图施加低秩结构，而低秩结构对于判别性聚类至关重要。由于其计算代价过高，这一性能提升属性在很大程度上被忽视了。为弥补这一空白，我们提出了一种新颖的方法，称为平衡锚点低秩多视图图聚类（BALM）。通过引入一种非凸核范数重构，BALM对学习的联合锚点图施加低秩约束，从而在保持线性复杂度的同时，使完整相似度矩阵具有低秩结构。该方法进一步集成了自动加权多视图图融合和快速谱聚类以实现直接聚类。因此，BALM在效率与性能之间实现了最优平衡：它在保持线性时间复杂度以确保可扩展性的同时，嵌入的低秩结构大幅提升了聚类性能。在大规模多视图基准数据集上的大量实验验证了BALM在有效性和效率上均优于最先进方法。

引言

图聚类[1]、[2]、[3]是无监督学习中的基本技术，它根据节点的连接模式将图的节点划分为不同的组。在各种图聚类方法中，谱聚类[4]、[5]、[6]已成为最受欢迎和有效的方法之一，被广泛应用于文本数据和交通视频分析等领域[7]、[8]、[9]。然而，由于图处理的高计算复杂度，其适用于大规模数据的能力受到严重限制；这一局限在谱聚类中尤为突出，因为它需要构建一个完整的n×n相似度矩阵并进行谱分析，两者的时间复杂度至少为??(n2)[10]、[11]（n表示数据样本数量），如此高的计算代价严重限制了谱聚类在大规模场景中的部署。

对此，研究人员开发了大量加速谱聚类策略[12]、[13]、[14]、[15]、[16]、[17]。一些方法采用采样技术构建锚点图，从而通过操作紧凑的图表示来降低图构建成本[18]、[19]；另一些方法则专注于通过特征值分解的高效近似来加速谱分析，例如经典的Nystr?m方法[20]、[21]。尽管这些技术在一定程度上缓解了计算负担，但它们本质上是为单视图数据设计的，无法直接推广到日益普遍的多视图设置中。

多视图数据[22]、[23]、[24]、[25]通过不同的来源或表示描述同一组对象，因此与单视图数据相比包含了更全面的信息[26]。鉴于传统的单视图聚类算法由于单一来源提供的信息受限而常常面临性能瓶颈，这一局限性促使了专门的多视图聚类方法的开发，这些方法通过有效利用多个视图之间的互补信息来提升性能。多视图图聚类[27]、[28]、[29]、[30]、[31]、[32]、[33]、[34]、[35]、[36]、[37]，尤其是多视图谱聚类，近年来在聚类性能方面取得了显著进展。

图结构化和基于网络的分析技术也被用于超越传统聚类的领域，以刻画复杂系统中的复杂依赖关系、同期关系和网络化共动模式[38]、[39]、[40]、[41]。与此同时，非线性机器学习预测器，包括神经网络和高斯过程，在多种应用领域的复杂和不规则数据建模中证明了其有效性[42]、[43]。尽管这些研究解决的是不同的分析任务，但它们与多视图图聚类共享一个共同目标：从复杂和异质的观测中揭示具有信息量的结构依赖关系。从这个更广泛的视角来看，紧凑的图表示提供了一种有前景的手段，可以在避免穷尽建模所有两两关系的同时保留主要的结构信息。

然而，当应用于大规模场景时，大多数现有的多视图图聚类方法仍然直接借用单视图领域的加速范式。这带来了一个关键缺陷：多视图模型本质上涉及更复杂的流程，如跨视图融合和视图权重学习以追求一致性图。许多配备现成加速方案的现有方法过度强调效率，却未能实现效率与聚类质量之间的良好平衡，尤其是在学习具有聚类判别性的联合图方面。特别是，多视图数据的异质性和互补性通常会导致不同视图的相似度图之间存在相当大的分歧。正如先前的多视图图聚类研究所验证的[44]、[45]，简单地聚合或拼接来自不同视图的图不仅无法提高聚类性能，反而往往导致性能下降。为应对这一问题，大多数现有方法试图从多个视图中学习一个编码多视图图内部聚类结构的联合图，该图通常被假设为低秩的[28]、[46]、[47]。为施加这一低秩约束，核范数作为秩函数的典型凸替代，经常被应用于学习的相似度矩阵。然而，计算核范数需要三次方时间复杂度，这使得在大规模数据上实现低秩图约束在计算上不可行。因此，如何在保证建模灵活性的同时实现良好的可扩展性仍然是大规模多视图图聚类中的一个开放问题。

为解决上述挑战，我们提出了一个名为平衡锚点低秩多视图图聚类（BALM）的新颖框架。与大多数仅关注降低计算复杂度的现有基于锚点的多视图方法不同，BALM通过在保持线性时间复杂度的同时引入低秩约束，在聚类性能和效率之间实现了理想的折中。具体而言，所提方法采用锚点图并开发了一种自动加权的多视图图融合机制，该机制在保持线性复杂度的同时联合学习一个具有自适应视图权重的一致性图。此外，通过引入核范数的非凸重构，BALM在锚点图上施加了一个专门的正则化器，以确保对应的完整相似度图具有低秩性质和更具判别性的聚类结构。这一操作也保持了线性计算复杂度，从而保证了联合图学习流程的效率。最后，聚类结果直接由基于学习的锚点图的快速谱聚类算法生成。

在BALM中，锚点图提供了这种可扩展的表示，而低秩正则化器控制了导出的一致性相似度图的复杂度。BALM的整个流程以线性时间复杂度运行。本文的主要贡献总结如下：

- 基于低秩相似度图增强谱分析这一共识，我们引入了一种非凸核范数重构，并设计了一种施加在联合锚点图上的新正则化器。在保持线性计算复杂度的前提下，我们的方法赋予了相应的完整相似度图低秩结构，从而提升了最终的聚类性能。
- 基于上述设计，我们提出了一个新的基于锚点的多视图谱聚类框架。该框架能够对联合锚点图进行自动加权学习，并通过该联合锚点图直接得到最终聚类结果，整个工作流程保持线性时间复杂度。
- 我们对所提方法进行了全面的理论分析，详细阐述了其计算复杂度、收敛行为及其与谱聚类的关系。此外，在多个真实大规模基准数据集上的大量实验结果表明，我们的方法具有优越的聚类性能和令人印象深刻的计算效率。

章节片段

**锚点图**

图聚类中数据样本的一种常见图表示是对称的n×n相似度矩阵（也称为亲和矩阵），其中每个元素量化了两个数据样本之间的成对相似度。如前所述，构建这样的完整图需要??(n2)的时间复杂度，而后续对该矩阵的操作不可避免地会带来相当大的计算开销。特别是，对完整大小的相似度矩阵进行谱分析需要??(...)。

**方法**

本节详细介绍了所提BALM框架及其交替优化策略。我们的方法从为每个视图构建数据样本与预选锚点之间的锚点图{??(??)}??_??=1开始，如预备知识中所概述的。

**计算复杂度分析**

对于由来自m个不同视图观测的n个数据样本组成的数据集，表示为{??(??)}??_??=1，BALM主要执行四个步骤，我们对每个步骤的计算复杂度进行了详细分析。

**实验**

本部分从多个方面评估了所提方法BALM的性能，包括聚类性能、运行时间、参数敏感性和收敛效率分析。

**结论**

本文提出了平衡锚点低秩多视图图聚类（BALM），这是一个可扩展的框架，旨在平衡大规模多视图谱聚类中的效率与性能。通过使用锚点图替代完整的多视图相似度矩阵，BALM避免了经典谱聚类中图构建和谱分解通常伴随的高计算代价。在BALM中，高效的自动加权图融合策略作为核心...

**CRediT作者贡献声明**

Ma Shuangxun：撰写—原稿，软件，方法学，形式分析。Qinghai Zheng：方法学，调查，数据整理。Tao Dai：软件，数据整理。Jian Sun：监督，方法学。

**利益冲突声明**

作者声明没有已知的竞争性经济利益或个人关系可能影响本文所报告的工作。

Ma Shuangxun | Qinghai Zheng | Tao Dai | Jian Sun