Partial Optimality in Cubic Correlation Clustering for General Graphs

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.