一种用于对称双随机聚类的快速低秩双因素建模

《Neurocomputing》：A fast low-rank two-factor formulation for symmetric doubly stochastic clustering

　　

摘要 双随机相似矩阵有助于平衡图聚类中的节点度，但其直接公式化需要稠密的变量。单因子表示，其中和，将存储降至，但变量的更新仍然存在自耦合。我们提出DSD2F方法，用替代，并对两个因子之间的差异进行惩罚。每个块采用单位步长投影缩放梯度试探步，并以投影梯度步作为回退方案，而行和乘子通过闭式KKT关系进行更新。该方法保持存储量，同时解耦了因子更新。在10个基准数据集上，与DCD、SDSGC和RMSL的主要对比中，DSD2F的平均RI排名最低，且在6个数据集上取得最高RI。在与DCD、LoRD和B-LoRD匹配的匹配低秩协议下，DSD2F在RI方面保持竞争力，并在所有10个数据集上取得最低的平均求解时间。

引言 双随机相似矩阵常用于平衡聚类中的图结构。对于具有行和列单位和非负的矩阵，极端的度变异可以被减少，从而使图更易于划分。这一思想与双随机矩阵和矩阵标度的经典工作密切相关[1],[2]。它也已用于谱聚类[3]，最近更被应用于图构建、几何和统计聚类[4],[5],[6]。

主要难点在于计算方面。许多双随机图学习模型优化显式的矩阵，受非负性、随机性、对称性以及有时进一步的结构约束[7],[8],[9],[10]。一个近期的例子是SDSGC（结构化双随机基于图的聚类）[11]，它学习一个显式的双随机图以及谱嵌入。尽管此类图变量保持直接可解释性，但它们必须在优化期间被存储和更新。由此产生的内存和计算成本在大图上变得相当大，相同的问题也出现在鲁棒、基于距离和多视角扩展中[6],[9],[12]。

低秩分解提供了一种自然的降低成本的方式。DCD（数据-簇-数据）[13],[14]，例如，将相似性表示为，其中和。存储从降至，且因子矩阵具有与非负分解相关的聚类解释[15]。缺点是出现在的两侧。因此其更新是自耦合的，现有求解器通常使用代理函数和乘法MM（最大化最小化）步骤[13],[14]。

最近，Lyu等人[16]从核均值松弛的角度提出了LoRD（低秩双随机聚类），以及其块正则化扩展B-LoRD。LoRD保留了低秩、非负和双随机结构，同时松弛了正交性。B-LoRD进一步使用弗罗贝尼乌斯范数正则化项来促进块对角结构。两者均保留单因子对称表示并使用投影梯度优化。

我们的公式化关注不同的问题：它将分解拆分为两个耦合因子，从而使主因子更新可以分离。具体来说，我们使用并对添加惩罚。存储阶仍保持为，但两个因子可以作为独立块进行更新。每个块首先使用单位步长投影缩放梯度试探步；如果试探被拒绝，则改为执行标准的投影梯度步。行和约束的乘子通过定理2中推导的KKT关系进行更新。

所得方法称为DSD2F（带两因子的双随机分解）。与SDSGC[11]不同，它不优化完整的图变量。相对于DCD[13],[14]，它保留低秩表示，同时避免了主因子更新中的直接自耦合。主要贡献总结如下：

- 我们提出了一种两因子低秩公式化，用于双随机聚类。二次惩罚促进因子一致性和近似对称性，同时保留存储量并允许独立块更新。
- 我们开发了一种增广拉格朗日算法，结合单位步长投影缩放梯度试探与投影梯度回退步。行和乘子通过KKT条件推导的关系进行闭式更新。
- 在10个基准数据集上的实验表明，DSD2F在与DCD、SDSGC和RMSL（互易多层子空间学习）[17]的主要对比中取得最低的平均RI排名，并在6个数据集上获得最佳RI。在与DCD、LoRD和B-LoRD的匹配低秩协议下，DSD2F在RI方面保持竞争力，并在所有10个数据集上取得最低的平均求解时间。

我们使用表示非负矩阵集合，使用表示单位矩阵。我们使用表示所需维度的全1向量和全0向量或矩阵。表示向量的欧几里得范数和矩阵的谱范数，而和分别表示弗罗贝尼乌斯范数和内积。诸如的矩阵不等式按元素理解，而表示半正定性。此外，表示非负正交上的逐元素投影，是其指标函数，收集方阵的对角线元素，表示哈达玛积。

部分摘录

直接双随机图学习 在聚类中，双随机矩阵既用于归一化，也作为图学习中的显式约束。一个常见的可行集为

其中是非负、对称和行随机的；由对称性，它也是列随机的。几种近期方法将这样一个矩阵与聚类变量或额外的图正则化项一起学习[7],[8],[9],[10],[11]。例如，SDSGC[11]求解

其中是成对距离矩阵，是相关的图拉普拉斯，是

模型动机 约束在构造上给出对称非负相似性，但它也在目标和约束中将因子与自身耦合。这就是DCD更新通常从代理而非直接块最小化获得的原因。

我们改用分解

因子分开更新并通过二次惩罚关联。中间对不必对称；惩罚则减小与之间的差距。存储保持为，且每个因子

优化算法 我们依次更新两个因子。投影矩阵公式用作试探点。每个试探在单位步长处评估一次。如果它未通过充分下降检验，则算法执行标准投影梯度步，步长为利普希茨步长。乘子随后使用定理2中的KKT关系更新。在本节中，

对于固定的和，令

我们将（10）中与固定：

实验 我们从数值行为、聚类准确性和运行时间三个方面评估DSD2F。主要对比使用以下基线：

- DCD[13],[14]，单因子低秩双随机分解方法；
- SDSGC[11]，全矩阵双随机图学习方法；
- RMSL[17]，

结论 我们提出了DSD2F，一种用于对称双随机聚类的两因子公式化。通过将替换为并对因子差异进行惩罚，模型保留了存储量并实现了独立块更新。每个因子块采用单位步长投影缩放梯度试探与投影梯度回退步，行和乘子通过KKT关系闭式更新。对于固定的和，分析给出了每次扫描的下降界和渐近正则性。在10个基准数据集上，DSD2F具有

CRediT作者贡献声明 Xunrui Wu：撰写——初稿，验证，软件，形式分析，数据管理。Enliang Hu：撰写——审阅与编辑，监督，资金获取，形式分析，概念化。Ouyang Wei：监督，方法学，形式分析。Junqing Li：方法学，数据管理。Haolong You：验证，软件。

生成式人工智能及AI辅助技术在写作过程中的声明 在撰写本文过程中，作者使用了一种AI工具来提高英文文本的清晰度和可读性。作者根据需要审阅和编辑了AI辅助的文本，并对文章内容承担全部责任。

利益冲突声明 作者声明，他们没有已知的竞争性财务利益或个人关系可能影响本文所述工作的报道。

Xunrui Wu 目前在云南师范大学数学学院攻读硕士学位，昆明，中国。她的研究兴趣包括基于图的聚类、低秩矩阵分解和数值优化。

Xunrui Wu|Enliang Hu|Ouyang Wei|Junqing Li|Haolong You 云南师范大学数学学院，昆明650500，中国