Partial Optimality in Cubic Correlation Clustering for General Graphs
This work addresses a specific combinatorial optimization problem for researchers in graph theory and clustering, but it is incremental as it focuses on a special case of an existing problem.
The paper tackles the NP-hard higher-order correlation clustering problem by establishing partial optimality conditions for cubic correlation clustering, and implements algorithms to decide these conditions, showing effectiveness on two datasets.
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.