Partial Optimality in Cubic Correlation Clustering
This work addresses a theoretical and practical bottleneck in clustering for researchers and practitioners, but it is incremental as it focuses on a special case of a known NP-hard problem.
The paper tackles the challenge of certifying optimality in higher-order correlation clustering by establishing partial optimality conditions for complete graphs with cubic objective functions, and implements algorithms to test these conditions, showing they can identify optimal clusters in up to 30% of cases in experiments on two datasets.
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.