as shown in Table 2 was chosen by compromising a satisfactory classication accuracy against the silhouette index. For each data set 5 runs of each algorithm were performed and the best cluster result selected.

Table 2 summarizes the results. The rst observation to be made is that the solution quality of std and elk is comparable with respect to error, classication accuracy, and silhouette index. Deviations are due to the non-uniqueness of the sample mean and the approximation errors of the graduated assignment algorithm. The second observation to be made from Table 2 is that elk outperforms std with respect to computation time on the letter, grec, and ngerprint data set. On the molecule data set, std and elk have comparable speed performance. Remarkably, elk requires slightly more distance calculations than std.

Contrasting the silhouette index and the dimensionality of the data to the speedup factor gained by elk, we make the following observation: First, the silhouette index for the letter, grec, and ngerprint data set are roughly comparable and indicate a cluster structure in the data, whereas the silhouette index for the molecule data set indicates almost no compact and homogeneous cluster structure. Second, the dimensionality of the vector representations is largest for molecule graphs, moderate for grec graphs, and relatively low for letter and ngerprint graphs. Thus, the speedup factor of elk and gvr apparently decreases with increasing dimensionality and decreasing cluster structure. This behavior is in line with ndings in high-dimensional vector spaces [5]. According to [20],
there will be little or no acceleration in high dimensions if there is no underlying structure in the data. This view is also supported by theoretical results from computational geometry [12].

## 5.4 Speedup Vs. Number K Of Centroids

In this experiment we investigate how the speedup factor of elk depends on the number k of centroids. For this, we restricted to subsets of the letter and ngerprint data sets. We selected 200 graphs uniformly distributed over the four classes A, E, F, and H. From the ngerprint data set we compiled a subset of 300 graphs uniformly distributed over all three classes. For each chosen number k of centroids 10 runs of each algorithm were conducted and the average of all performance measures was taken. The number k is shown in Table 3 for letter graphs and Table 4 for ngerprints graphs.

From the results shown in Table 3 and 4, we see that the speedup factor slowly increases with increasing number k of centroids. The results conrm that std and elk perform comparable with respect to solution quality for varying k. As an aside, all k-means algorithms for graphs exhibit a well-behaved performance in the sense that subgradient methods applied to the nonsmooth cluster objective JT indeed minimize JT in a reasonable way as shown by the decreasing error for increasing k.