# Partial Optimality in Cubic Correlation Clustering

arXiv: https://arxiv.org/abs/2302.04694 · HTML: https://mlsanity.com/paper/2302.04694/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 27 references that are in the map.
- First posted on arXiv 9 Feb 2023.

## Builds on (most cited first, 3 of 3)

- [Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds](https://mlsanity.com/paper/2111.10699/) (2021)
- [Higher-order Segmentation via Multicuts](https://mlsanity.com/paper/1305.6387/) (2013)
- [Combinatorial persistency criteria for multicut and max-cut](https://mlsanity.com/paper/1812.01426/) (2018)

## Built on by (most cited first, 3 of 3)

- [Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better](https://mlsanity.com/paper/2404.16131/) (2024)
- [Partial Optimality in Cubic Correlation Clustering for General Graphs](https://mlsanity.com/paper/2510.20431/) (2025)
- [Partial Optimality in the Preordering Problem](https://mlsanity.com/paper/2602.17346/) (2026)

## Abstract (arXiv)

The higher-order correlation clustering problem is an expressive model, and recently, local search heuristics have been proposed for several applications. Certifying optimality, however, is NP-hard and practically hampered already by the complexity of the problem statement. Here, we focus on establishing partial optimality conditions for the special case of complete graphs and cubic objective functions. In addition, we define and implement algorithms for testing these conditions and examine their effect numerically, on two datasets.