Chromatic Correlation Clustering, Revisited
Abstract
Chromatic Correlation Clustering (CCC) (introduced by Bonchi et al. [6]) is a natural generalization of the celebrated Correlation Clustering (CC) problem, introduced by Bonchi et al. [6]. It models objects with categorical pairwise relationships by an edge-colored graph, and has many applications in data mining, social networks and bioinformatics. We show that there exists a $2.5$-approximation to the CCC problem based on a Linear Programming (LP) approach, thus improving the best-known approximation ratio of 3 achieved by Klodt et al. [21] . We also present an efficient heuristic algorithm for CCC leveraging a greedy clustering strategy, and conduct extensive experiments to demonstrate the effectiveness and efficiency of our proposed algorithm.
Cite
Text
Xiu et al. "Chromatic Correlation Clustering, Revisited." Neural Information Processing Systems, 2022.Markdown
[Xiu et al. "Chromatic Correlation Clustering, Revisited." Neural Information Processing Systems, 2022.](https://mlanthology.org/neurips/2022/xiu2022neurips-chromatic/)BibTeX
@inproceedings{xiu2022neurips-chromatic,
title = {{Chromatic Correlation Clustering, Revisited}},
author = {Xiu, Qing and Han, Kai and Tang, Jing and Cui, Shuang and Huang, He},
booktitle = {Neural Information Processing Systems},
year = {2022},
url = {https://mlanthology.org/neurips/2022/xiu2022neurips-chromatic/}
}