Chromatic Correlation Clustering, Revisited

Qing Xiu · Kai Han · Jing Tang · Shuang Cui · He Huang

[ Abstract ]
[ Poster [ OpenReview
Spotlight presentation: Lightning Talks 1B-2
Tue 6 Dec 9:30 a.m. PST — 9:45 a.m. PST


Chromatic Correlation Clustering (CCC) (introduced by Bonchi et al. [6]) is a natural generalization of the celebrated Correlation Clustering (CC) problem. 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. [25]. 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.

Chat is not available.