研究了具有加权图的相关聚类问题，在此问题下，通过加权边标记为相似或不相似，通过最小化不同意向量的 l_p 规范的目标函数，提供了一个近似算法。

Aug, 2021

本文主要研究了查询效率，使用类似于计算距离的相似度度量，通过提出新的算法实现了更加高效的相关聚类，能够在给定预算内使用不同的查询方式获得与最优解相差不大的结果，并且针对算法进行了实验研究。

Feb, 2020

本文研究了相关聚类问题在每个相似边和不相似边权重符合一定假设下的近似算法，并给出了此问题渐近匹配的线性规划完整性间隙。

Aug, 2021

本文提供了第一个问题的非平凡近似算法，来解决最小化每个子群组的最大不一致数的最小化最大相关聚类问题，并对 multicut 问题得出了相应的结果。

Jun, 2019

本文研究了用于相关聚类问题的并行算法，其中每个不同实体的每对实体都标记为相似或不相似，旨在将实体分成簇以最小化与标签的不一致性，提出了首个多项式对数深度并行算法，并使用比 3 更好的逼近比计算 (2.4 +ϵ) 逼近解，可以将其转换为 (m1.5) 时间顺序算法和带有 (m1.5) 总内存的多项式对数轮次亚线性内存计算算法。

Jul, 2023

本研究提出了更快的近似算法，避免了其最佳逼近算法所依赖的不切实际的线性规划放宽，为两个经过充分研究的特殊情况 —— 聚簇编辑和聚簇删除提供了更快、更实用、更高效的线性规划算法及极具可扩展性的组合技术，包括聚簇删除的第一个组合逼近算法，实际应用中，我们的算法产生了近乎与质量最佳算法相匹配的近似解，同时适用于数量级更大的问题。

Nov, 2021

本文聚焦于 Correlation Clustering functional，它结合了数据点之间的正面和负面亲和性。文章的贡献包括两个方面，一是提供了该函数的理论分析；二是提出了新的优化算法，能够处理无法使用现有方法解决的大规模问题（>100K 变量）。通过对该函数的理论分析，发现该函数具备概率生成解释的能力，并且合理地解释了其内在的 “模型选择” 能力。此外，文章还探索了该函数和 well-known Potts 能量最小化之间的类比，这为我们提出了几种新的优化算法，这些算法利用函数的内在 “模型选择” 能力，可以自动恢复基础聚类数。与此同时，文章还介绍了两种新的应用领域：无监督人脸识别和通过粗略边界描绘实现的交互式多对象分割。

Dec, 2011

LambdaCC 和 MotifCC 是两种变体的相关聚类问题，应用于网络分析和社区检测，我们提出了两种非平凡的逼近算法来解决该问题，其中我们提出了两个算法来改善先前的逼近结果，同时还研究了在构造两个簇的限制下的逼近结果，其中 MotifCC 应用于超图设置。

Sep, 2018

本文提出了一种基于大规模并行计算 (MPC) 的算法，用于解决相关聚类问题。该算法的主要目标是利用签名图对图进行分区以最小化争议数量。在实验中，该算法同时试图减少节点内存的使用率。我们的算法是第一个在亚线性存储器中运行且使用有限的 MPC 轮数可以证明近似计算聚类问题方法的一种。

Jun, 2021

本研究提出了一种新的 min-max 图割算法 ——Min Max s-t Cut，同时探讨了基于局部目标的方法，针对最大不同数，给出了最大总权重的最小化问题的一个 O (√n) 近似算法，局部无序最小化问题的一个简单的 7 - 近似算法，以及最小总权重的最大化问题的一个更好的 1/(2+ε) 近似算法。

Apr, 2017