Fusion Moves for Correlation Clustering

Thorsten Beier, Fred A. Hamprecht, Jorg H. Kappes; The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015, pp. 3507-3516


Correlation clustering, or multicut partitioning, is widely used in image segmentation for partitioning an undirected graph or image with positive and negative edge weights such that the sum of cut edge weights is minimized. Due to its NP-hardness, exact solvers do not scale and approximative solvers often give unsatisfactory results. We investigate scalable methods for correlation clustering. To this end we define fusion moves for the correlation clustering problem. Our algorithm iteratively fuses the current and a proposed partitioning which monotonously improves the partitioning and maintains a valid partitioning at all times. Furthermore, it scales to larger datasets, gives near optimal solutions, and at the same time shows a good anytime performance.

Related Material

author = {Beier, Thorsten and Hamprecht, Fred A. and Kappes, Jorg H.},
title = {Fusion Moves for Correlation Clustering},
booktitle = {The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)},
month = {June},
year = {2015}