Partial Optimality in Cubic Correlation Clustering for General Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917036513296384 |
|---|---|
| author | Stein, David Andres, Bjoern Di Gregorio, Silvia |
| author_facet | Stein, David Andres, Bjoern Di Gregorio, Silvia |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_20431 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Partial Optimality in Cubic Correlation Clustering for General Graphs Stein, David Andres, Bjoern Di Gregorio, Silvia Discrete Mathematics Machine Learning 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. |
| title | Partial Optimality in Cubic Correlation Clustering for General Graphs |
| topic | Discrete Mathematics Machine Learning |
| url | https://arxiv.org/abs/2510.20431 |