利用结构感知的图表示方法和自适应锚图学习技术进行多视图聚类

《Digital Signal Processing》：Harnessing structure-aware graph representation and adaptive anchor graph learning for multi-view clustering

多视图聚类通过整合互补信息提升聚类性能，但现有方法难以同时建模全局拓扑和局部相似性，且锚点选择静态无法适应动态数据分布。本文提出SAGA2G框架，融合结构感知图表示和自适应锚点图学习，通过统一目标函数平衡全局与局部结构建模，采用动态锚点优化策略提升数据表达能力，并设计高效交替优化算法实现线性时间复杂度与稳定收敛。实验表明SAGA2G在八大数据集上显著优于现有方法。

　　

李晓然|刘金雷

烟台大学计算机与控制工程学院，中国烟台 264005

摘要

多视图聚类（MVC）旨在通过有效整合来自多个数据源的互补信息来提高聚类性能。然而，当前的方法往往无法完全模拟多视图数据的整体拓扑特征和局部相似性连接。此外，自适应学习与数据内在结构相一致的代表性锚点也是传统基于锚点的多视图聚类（AMVC）技术面临的另一个挑战。为了解决上述问题，我们提出了一种新的MVC框架，该框架结合了结构感知的图表示和自适应锚点图学习（SAGA²G）。具体来说，SAGA²G方法通过利用基于锚点的全局重构来保留邻域结构特征和拓扑一致性，从而实现对多级结构的统一建模。同时，我们开发了一种动态锚点优化方法，该方法通过自动调整锚点分布与底层聚类结构的对齐来提高数据的表达能力。此外，我们采用了一种高效的交替优化算法来解决所提出的方法，并对其理论时间复杂度和收敛性进行了保证。最后，在八个基准数据集上进行的广泛实验表明，SAGA²G显著优于现有的最先进技术。

引言

聚类在数据挖掘、模式识别和机器学习等领域得到了广泛应用[1]、[2]、[3]、[4]。通过发现数据中的潜在结构，聚类不仅降低了数据的维度，还对数据进行了有效的分析和可视化。聚类是一种无监督学习技术，其主要目标是将数据集划分为不同的组或簇。这一过程确保来自同一簇的样本之间具有更多相似性，而来自不同簇的样本则显示出更显著的差异。目前，大多数聚类技术（包括传统的k-means[5]、子空间聚类[6]、谱聚类[7]和图聚类[8]）通常假设数据来自单一视图。当处理来自单一来源的数据时，这些单视图聚类技术表现令人满意。但随着信息技术的快速发展，数据收集技术的多样性不断增加，收集到的数据呈现出越来越多的多源异构特征。这种来自不同来源或模态的数据被称为多视图数据[9]、[10]、[11]。

通过彻底研究视图之间的互补性和一致性，MVC方法与单视图聚类方法[12]、[13]相比显著提高了聚类性能。在多视图数据中，不同的视图通常从不同角度反映了数据的结构信息。例如，图像数据可以从像素、纹理和形状等多个角度进行特征描述。文本数据可以从词频、主题和情感等多个角度进行分析。因此，合理整合这些信息能够提供更全面和精确的数据分布描述[14]。通过充分利用多个视图之间的相关性，MVC不仅可以保留每个视图的关键特征，还可以利用不同视角之间的协同作用来显著提高对复杂数据的适应能力。

现有的MVC方法主要包括多视图子空间聚类（MVSC）[15]、[16]、多视图图聚类（MVGC）[17]、非负矩阵分解（NMF）[19]等。其中，MVSC通过在统一的低维子空间中联合学习所有视图的特征表示而取得了显著的成功。例如，Cai等人[20]提出了一种联合平滑机制，该机制同时捕捉了视图之间的共享结构和独特差异，从而增强了子空间表示的鲁棒性。多视图图的构建通常依赖于在MVGC中对样本关系一致性的建模。Liang等人[21]明确地对视图之间的共同和特定图结构进行了建模，显著提高了模型表示复杂跨视图变化的能力。同时，基于NMF的多视图聚类通过利用共同的基础矩阵或基于概念分解的统一表示来提取视图之间的共享结构。Khan等人[22]利用概念分解框架来描述数据的多流形结构。随后，他们的团队将概念分解扩展到不完整的多视图场景，并提出了一种互补的不完整加权概念分解方法[23]。尽管这些方法在各种应用场景中表现良好，但当应用于大规模数据集（如拥有数亿个节点的社会网络[24]）时，它们的计算效率和内存消耗成为了主要瓶颈。

为了解决大规模数据上MVC的计算和存储瓶颈，提出了基于锚点的多视图聚类（AMVC）。AMVC通过考虑样本和锚点m之间的关系（n ? m），而不是所有样本点之间的关系[25]，大大降低了计算和存储成本。此外，AMVC还可以避免传统MVC技术由于高维数据和大规模样本而导致的计算瓶颈。

然而，AMVC方法仍存在几个关键限制。首先，大多数现有方法通常依赖于随机采样或固定策略来选择锚点。这种静态选择机制无法适应不同数据分布的动态特性。在处理复杂或高维数据时，固定的锚点选择策略无法准确捕捉底层结构，导致锚点无法有效表示数据的关键特征。其次，尽管锚点机制显著降低了计算和存储成本并提高了整体效率，但其固有的压缩近似可能会削弱表示能力。如果模型不能同时捕捉局部相似性和全局拓扑，局部细节可能会被过度平滑，而整体结构则无法得到充分建模，最终降低聚类性能。图1将我们的方法与传统的AMVC方法进行了比较。

为了解决上述问题，我们提出了一种名为SAGA²G的新MVC方法，该方法结合了结构感知的图表示和自适应锚点图学习。SAGA²G的框架如图2所示。本文的主要贡献总结如下：(1)

受到现有MVC方法在同时建模全局拓扑和局部相似性方面的困难以及锚点选择方法缺乏适应性的启发，我们提出了一种新的联合学习框架来解决这些问题。该框架将全局结构表示、局部结构表示和自适应锚点学习整合到一个统一的目标函数中，如方程（10）所示。

(2)

为了全面描述多级结构属性，SAGA²G提出了一种统一的结构感知建模策略。该策略引入了基于锚点的全球重构策略和局部相似性维护约束，如方程（2）和方程（8）所示。通过在统一目标中联合建模全局几何结构和局部邻域关系，模型有效地平衡了全局一致性和局部多样性。联合约束在优化过程中相互完善，引导锚点表示向同时满足这两个方面的结构收敛，从而实现了捕捉多级结构信息的能力。

(3)

针对传统静态锚点选择无法适应复杂数据分布的问题，引入了一种可学习的自适应锚点图优化策略。SAGA²G利用预定义的簇指示矩阵W作为先验知识来指导多视图锚点和共识子空间表示的学习，如方程（9）所示。该矩阵W提供了关于数据底层簇结构的初始信息，帮助模型在学习过程中更好地捕捉不同视图之间的关系和数据的内在结构。

(4)

首先，在第4.1节中，我们从理论上分析了SAGA²G的时间复杂度。通过详细推导，我们证明了该方法与样本数量相关的线性复杂度。其次，在第4.2节中，我们对算法进行了收敛性分析，并证明了SAGA²G算法在合理条件下可以收敛到稳定解。这些分析结果为算法的稳定性和有效性提供了理论支持。

(5)

我们在八个基准数据集上进行了彻底的实验，并将SAGA²G与多种最先进的MVC方法进行了比较，如表3所示。实验结果表明，SAGA²G在聚类性能方面显著优于现有方法，验证了其在不同数据场景中的有效性。

本文的后续部分结构如下。第2节我们对全局和局部结构表示以及AMVC进行了全面概述。第3节探讨了SAGA²G的开发和基本技术，并介绍了数学公式和优化算法。第4节分析了SAGA²G的计算复杂度和收敛性。第5节展示了实验结果，并将我们的方法与不同数据集上的各种经典算法进行了比较。最后，第6节总结了我们的研究成果。

相关工作

相关工作

在本节中，我们介绍了全局和局部结构以及AMVC的相关工作。为方便起见，提供了符号表，如表1所示。

提出的方法

在本节中，我们介绍了提出的SAGA²G方法。首先，从三个方面介绍了该方法。其次，给出了SAGA²G的总体目标函数。最后，给出了SAGA²G的优化过程和算法。

计算复杂度分析

提出的SAGA²G方法采用交替迭代策略来顺序更新锚点矩阵A^(l)、锚点图矩阵Z和锚点簇质心矩阵B^(l)。在每一轮迭代中，更新A^(l)的过程主要涉及矩阵乘法和矩阵求逆操作，其计算复杂度为$O\left((dm+m^{2}n+m^3)v\right)$，其中$d={\sum }_{l=1}^v$。随后，更新Z涉及一个QP问题，该过程的计算复杂度为

实验结果

在本节中，我们从聚类性能、计算效率、参数敏感性和收敛性等方面评估了SAGA²G，并将其与七种最先进的MVC算法进行了比较。实验是在八个广泛使用的数据集上进行的。

结论与未来工作

本文提出了一种新的MVC方法SAGA²G，该方法利用结构感知的图表示和自适应锚点图学习。该方法增强了多视图数据的结构建模能力，并优化了锚点选择策略，使锚点分布能够更有效地与数据的底层簇结构对齐。

SAGA²G相对于现有方法的优势在于其对全局和局部结构的协同建模

CRediT作者贡献声明

李晓然：撰写-原始草稿准备、数据管理、软件开发、验证、监督、形式分析。刘金雷：概念化、方法论、项目管理、撰写-审阅和编辑、资金获取。

利益冲突声明

作者声明他们没有已知的竞争财务利益或个人关系可能影响本文报告的工作。