# Elkan'S K-Means For Graphs

Brijnesh J. Jain 1 and Klaus Obermayer 1 1Berlin Institute of Technology, Germany
{jbj|oby}@cs.tu-berlin.de Abstract. This paper extends k-means algorithms from the Euclidean domain to the domain of graphs. To recompute the centroids, we apply subgradient methods for solving the optimization-based formulation of the sample mean of graphs. To accelerate the k-means algorithm for graphs without trading computational time against solution quality, we avoid unnecessary graph distance calculations by exploiting the triangle inequality of the underlying distance metric following Elkan's k-means algorithm proposed in [5]. In experiments we show that the accelerated k-means algorithm are faster than the standard k-means algorithm for graphs provided there is a cluster structure in the data.

## 1 Introduction

The k-means algorithm is a popular clustering method because of its simplicity and speed. The algorithmic formulation of k-means as well as the solutions of its cluster objective presuppose the existence of a sample mean. Since the concept of sample mean is well-dened for vector spaces only, application of the k-means algorithm has been limited to patterns represented by feature vectors. But often, the objects we want to cluster have no natural representation as feature vectors and are more naturally represented by nite combinatorial structures such as, for example, point patterns, strings, trees, and graphs arising from diverse application areas like proteomics, chemoinformatics, and computer vision.

For combinatorial structures, pairwise clustering algorithms are one of the most widely used methods to partition a given sample of patterns, because they can be applied to patterns from any distance space without any additional mathematical structure. Related to k-means, the k-medoids algorithm is a well-known alternative that can also be applied to patterns from an arbitrary distance space.

The k-medoids algorithm operates like k-means, but replaces the concept of mean by the set median of a cluster [23]. With the emergence of the generalized median [18, 6] and sample mean of graphs [13, 14], variants of the k-means algorithm have been extended to the domain of graphs [13, 6, 14].

In an unmodied form, however, pairwise clustering, k-medoids as well as the extended k-means algorithm are slow in practice for large datasets of graphs. The main obstacle is that determining a graph distance is well known to be a graph matching problem of exponential complexity. But even if we resort to graph matching algorithms that approximate graph distances in polynomial time, application of clustering algorithms for large datasets of graphs is still hindered by their prohibitive computational time.