Spectral clustering and semi-supervised learning using evolving similarity graphs

• We describe a spectral graph clustering method that aims to optimise a graph structure.
• The initial population is constructed using nearest neighbour graphs, defining a new way to convert a matrix to a one dimensional chromosome.
• We focus on evolving similarity graphs by applying fitness functions, based on clustering criteria.
• The proposed method is generic as it can be applied to all problems that can be modeled as graphs.

Spectral graph clustering has become very popular in recent years, due to the simplicity of its implementation as well as the performance of the method, in comparison with other popular ones. In this article, we propose a novel spectral graph clustering method that makes use of genetic algorithms, in order to optimise the structure of a graph and achieve better clustering results. We focus on evolving the constructed similarity graphs, by applying a fitness function (also called objective function), based on some of the most commonly used clustering criteria. The construction of the initial population is based on nearest neighbour graphs, some variants of them and some arbitrary ones, represented as matrices. Each one of these matrices is transformed properly in order to form a chromosome and be used in the evolutionary process. The algorithm's performance greatly depends on the way that the initial population is created, as suggested by the various techniques that have been examined for the purposes of this article. The most important advantage of the proposed method is its generic nature, as it can be applied to several problems, that can be modeled as graphs, including clustering, dimensionality reduction and classification problems. Experiments have been conducted on a traditional dances dataset and on other various multidimensional datasets, using evaluation methods based on both internal and external clustering criteria, in order to examine the performance of the proposed algorithm, providing promising results.

Figure optionsDownload as PowerPoint slide