Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better

Graph clustering is a fundamental task in graph mining where the goal is to partition nodes of a graph into disjoint clusters that have dense internal connections but are only sparsely connected to the rest of the graph. This has a wide variety of applications which include detecting communities in social networks [Fortunato, 2010], identifying related genes in biological networks based on gene expression profiles [Ben-Dor et al., 1999], and finding groups of pixels in an image that belong to the same object [Shi and Malik, 2000]. An idealized notion of a cluster in a graph is a set of nodes that is completely connected internally (i.e., a clique) while being completely disconnected from the rest of the graph. Cluster graph modification problems [Shamir et al., 2004] are a class of graph clustering objectives that seek to edit the edges in a graph as little as possible in order to achieve this idealized structure. One widely studied problem is correlation clustering [Bansal et al., 2004], which can be cast as adding or deleting a minimum number of edges to convert a graph into a disjoint union of cliques. This problem is also known as cluster editing.