发帖
雷达卡
核心思想
本文主要探讨了一种名为 RCAGL (Robust and Consistent Anchor Graph Learning) 的新方法，旨在解决现有基于锚点的多视图图聚类方法中的两大挑战：一是处理不同视图之间的不一致性和噪声的能力较弱；二是需要额外的后处理步骤来生成最终的聚类标签。
现有的多视图图聚类技术在整合来自不同视角的数据时，通常会直接学习一个共享的锚图或先独立学习每个视图的锚图然后合并。这些方法往往未能充分考虑每个视图特有的噪声和视图间的不一致性，导致生成的共识表示不够可靠。此外，大多数方法在完成锚图构建后，还需要借助如 k-means 等后处理算法来确定最终的聚类标签，这不仅增加了计算成本，还可能导致聚类效果受后处理随机性的影响。
针对上述问题，RCAGL 方法提出了两项创新策略：
- 显式分解视图信息：RCAGL 假设每个视图的锚图由两部分组成——一个所有视图共享的一致性部分，以及一个视图特有的噪声部分。这种方法能有效去除特定于某个视图的噪声，从而获得更加稳健的一致性表示。
- 直接生成聚类标签：通过向一致性锚图的拉普拉斯矩阵施加 k-连通性约束，RCAGL 能够确保优化后的图结构准确地反映预设的聚类数量。因此，最终的聚类标签可以直接从优化后的图结构中得出，无需任何后处理步骤。
目标函数
RCAGL 的整体目标函数设计用于同时实现数据重构、噪声分离及直接聚类，具体表达式如下（公式 7）：
\( \min_{C, D^{(p)}, A^{(p)}} \sum_{p=1}^{v} \left\| X^{(p)} - \frac{1}{2} A^{(p)} (C + D^{(p)}) \right\|_F^2 + \lambda \|D^{(p)}\|_F^2, \)
约束条件为：\( A^{(p)T} A^{(p)} = I, C \geq 0, C^T \mathbf{1} = \mathbf{1}, D^{(p)} \geq 0, D^{(p)T} \mathbf{1} = \mathbf{1}, \text{rank}(\Delta) = n + m - k. \)
该目标函数的关键组成部分包括：
- 数据重构项：\( \sum_{p=1}^{v} \left\| X^{(p)} - \frac{1}{2} A^{(p)} (C + D^{(p)}) \right\|_F^2 \)，确保每个视图的数据 \( X^{(p)} \) 可以被其相应的锚点矩阵 \( A^{(p)} \) 和锚图 \( (C + D^{(p)}) \) 准确重建。
- 噪声正则化项：\( \lambda \|D^{(p)}\|_F^2 \)，利用 Frobenius 范数限制视图特有部分 \( D^{(p)} \) 的规模，旨在将尽可能多的有效信息保留于一致性部分 \( C \) 中，而将不一致性和噪声隔离至 \( D^{(p)} \)。
- k-连通性约束：\( \text{rank}(\Delta) = n + m - k \)，其中 \( \Delta \) 是由增强图 \( G = [0, C^T; C, 0] \) 构建的归一化拉普拉斯矩阵。此约束确保最终的一致性图 \( C \) 恰好拥有 \( k \) 个连通分量，从而直接生成聚类标签。
此外，目标函数还包括若干约束条件，例如正交约束 \( A^{(p)T} A^{(p)} = I \) 保证学习到的锚点具备多样性；非负性和行和为 1 的约束（如 \( C \geq 0, C^T \mathbf{1} = \mathbf{1} \)）确保 \( C \) 和 \( D^{(p)} \) 的合理性和有效性。
表示一个有效的概率分布（即相似度矩阵）。为了便于优化，k-连通性约束被转化为一个迹最小化问题（公式14）：
\( \min \dots + \gamma \text{Tr}(R^T \Delta R), \quad \text{s.t. } R^T R = I_k \)
这里，\( R \) 是一个指示矩阵，而 \( \gamma \) 是一个足够大的常数。依据 Ky Fan 定理，当 \( \gamma \) 足够大时，该松弛问题的解与原始的秩约束问题的解等价。
目标函数的详细优化过程
这个非凸优化问题采用了交替优化（Alternating Optimization）策略来解决，即在每次迭代中固定其他变量，依次优化一个变量。
1. 锚点矩阵的优化
在固定 \( C \) 和 \( \{D^{(p)}\} \) 的情况下，目标函数简化为：
\( \min_{A^{(p)}} \sum_{p=1}^{v} \left\| X^{(p)} - \frac{1}{2} A^{(p)} (C + D^{(p)}) \right\|_F^2, \quad \text{s.t. } A^{(p)T} A^{(p)} = I \)
这个问题在每个视图 \( p \) 上是独立的。通过展开 F 范数并忽略常数项，问题可以转化为：
\( \max_{A^{(p)}} \text{Tr}(A^{(p)T} Q^{(p)}), \quad \text{s.t. } A^{(p)T} A^{(p)} = I \)
其中 \( Q^{(p)} = X^{(p)}(C + D^{(p)})^T \)。此问题的最优解可以通过对 \( Q^{(p)} \) 进行奇异值分解（SVD）来获得。
2. 视图特定噪声矩阵的优化
在固定 \( \{A^{(p)}\} \) 和 \( C \) 的情况下，目标函数简化为：
\( \min_{D^{(p)}} \sum_{p=1}^{v} \left\| X^{(p)} - \frac{1}{2} A^{(p)} (C + D^{(p)}) \right\|_F^2 + \lambda \|D^{(p)}\|_F^2, \quad \text{s.t. } D^{(p)} \geq 0, D^{(p)T} \mathbf{1} = \mathbf{1} \)
由于不同视图和不同样本的 \( D^{(p)} \) 的列是独立的，该问题可以分解为对每个 \( d_i^{(p)} \)（\( D^{(p)} \) 的第 \( i \) 列）的独立优化。通过求解一个带有单纯形约束的二次规划问题，可以得到 \( d_i^{(p)} \) 的闭式解。
3. 一致性锚图的优化
在固定 \( \{A^{(p)}\} \) 和 \( \{D^{(p)}\} \) 的情况下，目标函数简化为：
\( \min_{C} \sum_{p=1}^{v} \left\| X^{(p)} - \frac{1}{2} A^{(p)} (C + D^{(p)}) \right\|_F^2 + \gamma \text{Tr}(R^T \Delta R), \quad \text{s.t. } C \geq 0, C^T \mathbf{1} = \mathbf{1} \)
这部分的优化同样采用交替策略：
更新 \( R \)：固定 \( C \)，问题变为 \( \min_{R^T R = I_k} \text{Tr}(R^T \Delta R) \)。其最优解是 \( \Delta \) 的前 \( k \) 个特征向量组成的矩阵。
为了提高计算效率，作者巧妙地利用了\(\Delta\)的特殊结构，将其转换为一个广义奇异值分解问题（见公式17）。通过应用定理1，他们得出了最优解\(R_u = \frac{\sqrt{2}}{2} U_k, R_v = \frac{\sqrt{2}}{2} V_k\)。
接下来，固定\(R\)，利用拉普拉斯矩阵\(\Delta\)与图结构\(C\)之间的关系（见公式20-21），将迹项\(\text{Tr}(R^T \Delta R)\)展开为关于\(C\)元素的加权和。这一过程使得问题可以分解为对\(C\)每一列\(c_i\)的独立优化。每个子问题都是一个带有单纯形约束的二次规划，可以高效求解其闭式解。
主要贡献点
- 提出了一种新颖的鲁棒且一致的锚图学习方法（RCAGL）：该方法通过显式地将每个视图的锚图分解为一致性部分和视图特定噪声部分，能够有效捕捉跨视图的共同结构并过滤掉视图特定的噪声和不一致性，从而获得更可靠、更鲁棒的共识表示。
- 实现了无需后处理的直接聚类：通过对一致性锚图施加k-连通性（低秩）约束，RCAGL可以直接从优化后的图结构中生成最终的聚类标签，避免了传统方法中因后处理（如k-means）带来的性能不稳定性和额外计算开销。
- 设计了高效的优化算法：针对所提出的目标函数，设计了一个基于交替优化的高效算法。该算法能够有效处理大规模数据，并在多个基准数据集上的实验验证了RCAGL在聚类准确性、对噪声的鲁棒性以及可扩展性方面的优越性。
算法实现过程详解
根据论文中的Algorithm 1，RCAGL的完整实现步骤如下：
- 输入：多视图数据\(\{X^{(p)}\}_{p=1}^v\)，锚点数量\(m\)，聚类数\(k\)，正则化参数\(\lambda\)。
- 初始化：随机或通过启发式方法（如k-means）初始化一致性图\(C\)和各视图的噪声图\(\{D^{(p)}\}\)。
- 主循环（直到收敛）：
- 更新锚点\(\{A^{(p)}\}\)：对每个视图\(p\)，计算\(Q^{(p)} = X^{(p)}(C + D^{(p)})^T\)，然后对其进行SVD，得到最优的\(A^{(p)}\)。
- 更新噪声图\(\{D^{(p)}\}\)：对每个视图\(p\)和每个样本\(i\)，根据公式(12)计算其对应的\(d_i^{(p)}\)的闭式解。
- 内循环（直到\(C\)有恰好\(k\)个连通分量）：
- 更新一致性图\(C\)：利用当前的\(R\)和其他变量，根据公式(23)计算\(C\)每一列的闭式解。
- 更新拉普拉斯相关矩阵：根据新的\(C\)更新度矩阵\(H_u\)和\(H_v\)。
- 更新指示矩阵\(R\)：根据定理1，通过SVD计算新的\(R_u\)和\(R_v\)。
- 更新参数\(\gamma\)：根据当前拉普拉斯矩阵\(\Delta\)的特征值情况调整\(\gamma\)，以确保秩约束被满足。
- 输出：当外层循环收敛后，最终的一致性锚图\(C\)被送入Tarjan算法等连通分量检测算法，直接输出\(k\)个聚类标签。
论文存在的局限性分析
尽管RCAGL方法设计精巧且实验效果显著，但仍存在一些值得探讨的局限性：
- 超参数依赖：该方法引入了关键超参数\(\lambda\)（用于平衡重构与噪声分离）和锚点数量\(m\)。虽然论文的敏感性分析表明RCAGL对\(\lambda\)相对不敏感，但其性能仍然受到\(m\)的影响。如何为不同的数据集自适应地选择最优的\(m\)和\(\lambda\)仍然是一个开放问题，通常需要通过网格搜索等耗时的方式来确定。
- 锚点学习的初始化敏感性：尽管锚点\(A^{(p)}\)是在优化过程中学习的，但其初始值（以及\(C\)和\(D^{(p)}\)的初始值）可能会影响算法的收敛速度和最终性能。如果初始化不佳，算法可能陷入局部最优解。
- 对图结构的强假设：k-连通性约束是一个非常强的假设，它要求数据在低维嵌入空间中形成的图结构必须能被完美地划分为\(k\)个互不连通的子图。在真实世界数据中，由于数据分布的复杂性、噪声的存在或类别边界模糊，这种理想的图结构可能难以达到。此时，强约束可能会对数据重构和一致性学习产生负面影响。
- 适用场景的限制：论文主要关注完整多视图聚类（即每个样本在所有视图中都有特征）。然而，在实际应用中，经常会出现不完整多视图数据（即部分样本在某些视图中缺失特征）。RCAGL框架并未直接处理这种情况，其在不完整数据上的性能和适用性有待验证。
- 计算复杂度的细节：虽然论文声称其时间复杂度为线性（\(O(n)\)），但这建立在\(m, d, v, t \ll n\)的基础上。在实际应用中，如果这些参数接近或超过\(n\)，算法的实际运行时间可能会显著增加。
基于这一假设。其中，t 表示为了确保 k-连通性的内循环迭代次数。在一些复杂的数据库中，t 可能会显著增加，进而影响到总体性能。此外，每次内循环都需要执行一次 SVD（用于更新 R），对于特别大的 m 而言，这可能成为一个障碍。
总之，RCAGL 通过其独特的视角分解与直接聚类方法，在多视角聚类任务中取得了重要突破。不过，该方法对超参数、初始设置和最优图结构的依赖性，以及它处理缺失数据的能力，都是未来研究可以进一步探索和改善的地方。
京公网安备 11010802022788号
