提出三元团聚类的部分最优判定方法，可高效验证解的最优性。
Partial Optimality in Cubic Correlation Clustering for General Graphs
- 基于三元团设计局部最优性判定算法
- 在两个数据集上验证了算法有效性
- 适合需要严格优化保证的研究者
对于图 $G$ 及其团的代价，高阶相关聚类问题旨在寻找一种聚类方式，使所有节点同属一个簇的团的代价总和最小。针对这一NP难问题，已有局部搜索启发式方法被应用于实际场景。本文研究三元团相关聚类（即最多3个节点的团）的部分最优性条件，定义并实现了相应的判定算法，并在两个数据集上进行了数值实验，验证了其有效性。
原文摘要 · Abstract (English)
The higher-order correlation clustering problem for a graph $G$ and costs associated with cliques of $G$ consists in finding a clustering of $G$ so as to minimize the sum of the costs of those cliques whose nodes all belong to the same cluster. To tackle this NP-hard problem in practice, local search heuristics have been proposed and studied in the context of applications. Here, we establish partial optimality conditions for cubic correlation clustering, i.e., for the special case of at most 3-cliques. We define and implement algorithms for deciding these conditions and examine their effectiveness numerically, on two data sets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。