平衡 $k$-Cut 问题的紧凑连续松弛

NIPSMay, 2015

Tight Continuous Relaxation of the Balanced $k$-Cut Problem

Syama Sundar Rangapuram, Pramod Kaushik Mudrakarta, Matthias Hein

TL;DR本文提出了一种紧密的连续松弛方法用于解决图的平衡 k 切问题，以优化标准的归一化切，通过求解难以优化的比例和问题，进一步优化算法表现，实验比较证明该方法胜过现有的全部方法。

Abstract

spectral clustering as a relaxation of the normalized/ratio cut has become one of the standard graph-based clustering methods. Existing methods for the computation of multiple clusters, corresponding to a balance

spectral clustering normalized cut ratio cut continuous relaxation sum-of-ratios minimization

发现论文，激发创造

比率割聚类的最速下降算法收敛性

本研究提出了一种显式 - 隐式梯度流算法来解决松弛比率切问题，该算法通过实验证明了其在处理高维数据集，特别是两个月亮数据集中极具效率。

Apr, 2012

通过非启发式算法离散化谱聚类的松弛解

基于一阶优化算法，我们提出了第一个非启发式方法，将原始问题与离散化算法联系起来，从而更可靠地获得最终的离散解决方案，优于现有方法。

Oct, 2023

受约束的 1 - 谱聚类

本文拓展了经典的谱聚类方法，将不能链接和必须链接约束整合到了聚类中，并通过松弛优化问题获得了一种新的连续性方法，相比其他约束谱聚类方法，该方法能够保证满足所有约束条件并且可以快速处理大规模数据集。

May, 2015

通过最优输运实现任意尺寸约束的图割

通过提出一种基于正则化 Gromov-Wasserstein 问题的加速近端梯度下降算法，我们解决了图切割问题，并实现了稀疏解，相较于经典谱聚类算法，额外的复杂度仅为 O (log (n))，但效率更高。

Feb, 2024

一种新的带最近邻层次初始化的归一化切割求解器

我们提出了一种新颖的基于坐标下降法的 N-Cut 求解器，通过设计加速策略将时间复杂度从 O (n^3) 减少到 O (|E|)，并提出了一种高效的初始化方法，该求解器在多个基准数据集上取得了更大的 N-Cut 目标值和更好的聚类性能。

Nov, 2023

带公平约束的谱归一化 - 割图分割

我们提出了一种名为 FNM 的二阶段谱算法，通过在目标函数中添加公平性准则来获取更公平的谱节点嵌入，然后设计一个舍入方案从该公平嵌入中生成 k 个簇，从而在维持公平性的同时达到良好的分区质量。通过对九个基准数据集进行全面实验，我们证明了 FNM 相对于三种基准方法的卓越性能。

Jul, 2023

受限分数集程序及其在本地聚类和社区检测中的应用

本文提出了一种新的方法用于解决网络分析中的约束最小化问题，该方法基于一种紧密的弛豫 (relaxation) 方式，可取得比凸松弛法和谱松弛法更好的结果。

Jun, 2013

一步二分图切割：一种标准化的公式及其在可扩展子空间聚类中的应用

本文提出了一种新的一步二分图切割（OBCut）标准，可以在线性时间内强制执行归一化条件，并将其扩展到可扩展的子空间聚类方法中。实验表明，该方法在各种普通和大规模数据集上具有有效性和可扩展性。

May, 2023

潜在的随机步骤作为最大割、最小割和更多的松弛

基于非负矩阵分解的概率模型统一了节点聚类和图简化，提供了建模任意图结构的框架。通过将硬聚类放松为软聚类，我们的算法将潜在的困难聚类问题转化为易处理的问题。

Aug, 2023

通过放松张量范数实现更好的不可知聚类

基于平方和范数的 $k$-means 聚类的凸松弛算法及其学习算法，能够学习高斯混合物的均值。

Nov, 2017