A Fixed-Parameter Tractable GA for Data Clustering

Clustering is the process of grouping similar data points into distinct clusters. Graph theoretic techniques for data clustering attempt to find the most efficient way to convert a precomputed similarity graph into a cluster graph, which is a collection of disjoint cliques. In contrast, most existing evolutionary approaches to clustering are based on partitioning data points according to feature vectors. In this paper we present an evolutionary algorithm for tackling data clustering from the graph theoretic perspective. In particular, we adapt a genetic algorithm (the SubPopGA) that maintains a population of solved subgraphs to solve the NP-hard k-Cluster Deletion and k-Cluster Vertex Deletion problems. This adaptation is nontrivial, as it requires modifying the technique to work on induced subgraphs and designing a novel template parent mechanism for uniform crossover. We prove that the resulting SubPopGA has a fixed-parameter tractable running time on both problems. Given an arbitrary graph on n vertices and m edges, we prove that it solves k-Cluster Deletion in O(n34k + mn2 log n) generations in expectation, and the k-Cluster Vertex Deletion problem in O(n35k + n3 log n) in expectation. We also present results from a number of computational experiments that measure the running time of the SubPopGA on real-world biological data sets coming from protein-protein interaction networks.