Algorithm 3 (K-Means Algorithm for Structure Spaces)

01 choose initial centroids Y1, . . . , Yk ∈ XT
02 repeat 03 assign each X ∈ ST to its closest centroid YX = arg minY ∈YT D(*X, Y* )
2 04 recompute each Y ∈ YT as a sample mean of all graphs from C(Y )
05 until some termination criterion is satised
Hence, we can easily extend Algorithm 1 to minimize the cluster objective JT .

Algorithm 3 describes the basic procedure of the k-means algorithm for structure spaces independent of the particular choice of method to minimize the objective F of a sample mean. Similarly as for vectors, C(Y ) denotes the cluster associated with centroid Y ∈ YT .

In each iteration of the structural version of k-means requires kN distance calculations to assign each pattern graph to a centroid and at least additional O(N) distance calculations for recomputing the centroids using the incremental arithmetic mean subgradient method. This gives a total of at least O(kN + N)
distance calculations in each iteration of Algorithm 3.

## 4 Elkan'S K-Means For Graphs

In this section we extend Elkan's k-means [5] from vectors to graphs.

Frequent evaluation of NP-hard graph distances dominates the computational cost of k-means for graphs. Accelerating k-means therefore aims at reducing the number of graph distance calculations. In [5], Elkan suggested an accelerated formulation of the standard k-means algorithm for vectors exploiting the triangle inequality of the underlying distance metric. Since the distance function D on XT induced by an Euclidean metric is also a metric [16], we can transfer Elkan's k-Means acceleration from Euclidean spaces to T -spaces.

To extend Elkan's k-Means acceleration to T -spaces, we assume that X ∈ ST
is a pattern graph and Y, Y 0 ∈ YT are centroids. As before, by YX we denote the centroid the pattern graph X is assigned to. Elkan's acceleration is based on two observations:
1. From the triangle inequality of a metric follows

$$u(X)\leq\frac{1}{2}D\left(Y_{X},Y\right)\;\Rightarrow\;D\left(X,Y_{X}\right)\leq D\left(X,Y\right),\tag{1}$$
where $u(X)\geq D\left(X,Y_{X}\right)$ denotes an upper bound of the distance $D\left(X,Y_{X}\right)$. 2. We have 
$$u(X)\leq l(X,Y)\;\Rightarrow\;D\left(X,Y_{X}\right)\leq D\left(X,Y\right),\tag{2}$$  where $l(X,Y)\leq D\left(X,Y\right)$ denotes a lower bound of the distance $D\left(X,Y\right)$.  