本文档介绍了一项由Zhao Kang、Xuanting Xie、Bingheng Li和Erlin Pan共同完成的研究，这几位作者均来自University of Electronic Science and Technology of China。这项名为“CDC: A Simple Framework for Complex Data Clustering”的研究发表于*Journal of Latex Class Files, Vol. 14, No. 8, August 2021*，并于2025年1月9日更新了预印本版本（arXiv:2403.03670v2 [cs.LG]）。

本研究的核心学术领域是无监督学习，具体聚焦于数据聚类，特别是针对复杂数据的聚类问题。在当今数据驱动的数字时代，从多种来源、传感器或特征提取器收集的数据呈现出前所未有的复杂性和规模。这些数据表现为多视图数据（Multi-view data，从不同角度或来源描述同一对象）、非欧几里得数据（如图数据，包含拓扑结构）以及多关系数据等多种形式。传统的聚类方法通常独立地针对某一类特定挑战（例如仅处理多视图，或仅处理图结构）而设计，往往在解决一个问题的同时牺牲了处理其他类型数据的能力或效率。特别是在面对大规模（例如百万甚至亿级节点）数据时，许多现有方法（尤其是基于复杂图神经网络的方法）会因计算或内存的二次方复杂度而难以扩展。因此，研究团队旨在填补这一空白，提出一个既通用又高效的统一聚类框架。本研究的目标是开发一个名为CDC的框架，使其能够以线性复杂度高效处理不同类型的复杂数据（包括单视图/多视图、图/非图、小规模/大规模数据），并通过理论证明和实验验证其有效性，最终实现在超大规模（如1.11亿节点）图数据上的成功部署。

CDC框架的工作流程主要包含三个核心步骤：图滤波、锚点图学习和优化求解，最终进行谱聚类以获得聚类结果。

第一，图滤波。这是预处理步骤，旨在融合数据的原始特征和拓扑结构信息，生成更有利于聚类的平滑表示。对于非图数据，研究者首先利用5-近邻方法为每个视图构建邻接矩阵。对于给定的特征矩阵X和归一化后的图拉普拉斯矩阵L，通过求解一个优化问题（最小化表示与原始特征的差异同时保证图上的平滑性），并保留其一阶泰勒展开，得到了k阶图滤波公式：H = (I - ¹⁄₂ L)^k X。这里的k是一个非负整数，控制着特征聚合的深度和表示的平滑度。这一步骤的关键作用在于，它通过低通滤波滤除了数据中的高频噪声，同时保留了图的几何特征，并且将不同类型的数据（无论是否具有图结构）统一到了同一个基于图滤波的处理框架中。

第二，锚点图学习。这是CDC框架的核心创新，旨在以线性复杂度构建数据点之间的关系图。传统方法通常随机选择一部分样本作为锚点，然后构建数据点到这些锚点的二部图（锚点图）。然而，随机选择会带来结果的不稳定性，且锚点一旦选定便不再更新，可能导致次优解。CDC对此进行了两项关键改进：1）自适应锚点学习：不再固定锚点，而是将锚点矩阵B作为可优化变量，从数据中学习得到。2）相似性保持正则化项：引入了一个新颖的正则化项 α∥BH^⊤ - Z∥_F^2，强制要求学习到的锚点B与滤波后特征H的相似性（BH^⊤）与待求的锚点图Z保持一致。这保证了生成锚点的质量。对于单视图数据，其优化模型为最小化重构误差、相似性保持正则项以及图的正则项（β∥Z∥_F^2）。对于多视图场景，模型进一步引入了可学习的视图权重{λ_v}，以融合不同视图的信息，形成共识锚点图Z。该优化问题通过交替优化策略高效求解。

第三，优化求解与聚类。框架采用交替方向法迭代更新变量：1）固定其他变量，利用公式更新锚点图Z；2）固定Z和权重，通过求解西尔维斯特方程更新每个视图的锚点B^v；3）固定Z和B，通过求解一个标准二次规划问题更新视图权重λ_v。理论分析证明该优化过程能单调降低目标函数值并收敛。得到最优的共识锚点图Z后，由于其具有分组效应（相似节点的连接结构趋于一致），可以直接对其转置进行奇异值分解，然后对右奇异向量运行K-means算法，即可得到最终的聚类结果。整个流程（包括图滤波、优化和最后的SVD与K-means）在时间和空间上均具有线性复杂度，关键在于锚点数量m远小于样本数量n。

为了全面验证CDC框架的有效性、高效性和通用性，研究团队在14个不同类型的复杂数据集上进行了广泛的实验。这些数据集被分为四类进行测试：1）单视图图数据（如Citeseer, PubMed, Products, Papers100M）；2）多关系图数据（ACM, DBLP）；3）多属性图数据（AMAP, AMAC）；4）大规模多视图非图数据（YTF-31, YTF-400）。其中，Products和Papers100M（含1.11亿节点）属于超大规模图，用于测试可扩展性。研究将CDC与众多最先进的基线方法进行了比较，包括基于GNN的方法（如DGI, MVGRL, S3GC）、多视图聚类方法（如MvAGC, MCGC）以及可扩展的非图多视图聚类方法（如EOMSC-CA, FastMICE）。评估指标采用了聚类任务中标准的ACC（准确率）、NMI（标准化互信息）、ARI（调整兰德指数）和F1分数。

实验结果充分支持了CDC框架的优势。在单视图图数据上，CDC在Citeseer和PubMed上取得了最佳性能，在超大规模的Papers100M上与当前最先进的S3GC方法表现相当甚至略有优势，并且在运行时间上显著优于S3GC（在Papers100M上CDC耗时约4小时，而S3GC需要24小时）。在多视图图数据上，CDC的优势更加明显，在ACM、DBLP、AMAP和AMAC数据集上，其各项指标均大幅领先于其他对比方法，平均提升显著。在非图多视图数据（YTF-31和YTF-400）上，CDC同样取得了最佳或具有竞争力的结果，且运行效率更高。消融实验进一步证实了框架中两个关键组件的作用：移除相似性保持正则化项（SP）会导致性能平均下降约3%，且优化速度变慢；移除图滤波步骤（GF）则会导致性能急剧下降约10%。参数分析表明，相似性保持参数α比图正则化参数β对结果影响更大。此外，研究还对CDC在异配性图（连接节点通常属于不同类别）上的鲁棒性进行了测试，在Texas、Cornell等数据集上，CDC的表现超越了专门针对异配性设计的聚类方法，显示了其良好的泛化能力。

本研究的结论是，研究者成功提出了一个用于复杂数据聚类的简单而有效的统一框架CDC。该框架通过图滤波整合结构信息，通过带有相似性保持正则化的自适应锚点学习机制，以线性复杂度生成高质量的、有利于聚类的图表示。理论分析证明了滤波后特征能同时保持拓扑和属性相似性，且学到的锚点图具有分组效应。大量实验证明，CDC在多种类型（图/非图、单视图/多视图）和规模（从小规模到亿级节点）的数据集上均能取得优异且稳定的性能，同时在计算效率上具有显著优势。

本研究的价值体现在多个层面。在科学价值上，它首次提出了一个能够统一处理多种复杂数据类型的聚类框架，并通过理论分析为图滤波和锚点图学习的有效性提供了理论支撑，特别是相似性保持正则化项的提出是本研究的一个重要理论贡献。在应用价值上，CDC的线性复杂度使其能够处理Web规模的超大规模数据（如1.11亿节点的学术论文网络），这为在社交网络分析、推荐系统、生物信息学等需要处理海量关联数据的实际场景中部署高效的聚类算法提供了可能。其框架的简洁性和高效性也降低了实际应用的门槛。

本研究的亮点和重要发现包括：第一，方法的统一性与通用性：首次用一个框架同时解决了多视图、图结构、大规模等多个聚类领域的核心挑战。第二，核心算法创新：提出了“相似性保持正则化”来自适应地学习高质量锚点，从根本上改进了传统随机锚点方法的稳定性和性能上限。第三，卓越的可扩展性：理论分析和实验均证实了算法具有线性的时间和空间复杂度，并成功在目前聚类任务中最大规模的公开图数据集之一（Papers100M）上验证了其可行性。第四，坚实的理论保障：不仅提出了新方法，还通过定理严格证明了滤波表示能保留双空间相似性，以及所学锚点图具有聚类友好的分组效应。第五，全面的实验验证：在14个差异巨大的数据集上进行了充分测试，涵盖了几乎所有类型的复杂数据场景，结果具有强说服力。潜在的局限性在于，锚点生成步骤的复杂度与特征维度d的三次方相关，因此在处理极高维数据时可能效率受影响，但文中指出可通过降维技术作为预处理来解决。总体而言，这项工作因其简洁的设计、强大的性能、优秀的可扩展性以及扎实的理论基础，有望对聚类研究社区产生广泛影响，并具备很高的实际部署潜力。