
## Algorithm 1 (K-Means Algorithm For Euclidean Spaces)

01 choose initial centroids y1, . . . , yk ∈ X
02 repeat 03 assign each x ∈ S to its closest centroid yx = arg miny∈Y kx − yk 2 04 recompute each centroid y ∈ Y as the mean of all vectors from C(y)
05 until some termination criterion is satised
Suppose that we are given a training sample S = {x1*, . . . ,* xN } of N vectors drawn from the Euclidean space X . A partition P = {C1*, . . . ,* Ck} of S into k disjoint subsets (clusters) Ci ⊆ S is determined by a (N ×k)-membership matrix M = (mij ) satisfying the constraints

$$\sum_{j=1}^{k}m_{i j}=1$$ $$m_{i j}\in\{0,1\}$$
for all $i\in\{1,\ldots,N\}$  for all $i\in\{1,\ldots,N\},j\in\{1,\ldots,k\}$.  
The standard k-means clustering algorithm aims at nding k centroids Y =
{y1, . . . , yk*} ⊆ X* and a partition M = (mij ) of the set S such that the cluster objective

$$J\left({\boldsymbol{M}},{\mathcal{Y}}\left|{\mathcal{S}}\right.\right)={\frac{1}{m}}\sum_{j=1}^{k}\sum_{i=1}^{N}m_{i j}\left\|{\boldsymbol{x}}_{i}-{\boldsymbol{y}}_{j}\right\|^{2},$$

is minimized.

Suppose that we x an arbitrary membership matrix M. Then the cluster objective J(. |M, X) given M and X is dierentiable as a function of the centroids Y. The k centroids that minimize J(. |M, X) are the sample means

$$\mathbf{y}_{j}={\frac{1}{|{\mathcal{C}}_{j}|}}\sum_{i=1}^{N}m_{i j}\mathbf{x}_{i},$$

of the clusters Cj consisting of data points x ∈ S assigned to centroid yj . Since the k sample mean centroids together with the given membership matrix M yields a local minimum of the cluster objective J only, the challenging task of minimizing J consists in nding an optimal membership matrix. Since this problem is NP-complete [7], several heuristic algorithms have been devised. A
standard clustering heuristic that minimizes J is the k-means algorithm as outlined in Algorithm 1. The notation C(y) used in Algorithm 1 denotes the cluster associated with centroid y ∈ Y.

## 3 The K-Means Algorithm For Graphs

To extend k-means from the domain of feature vectors to the domain of graphs, two modications are necessary [13, 14]: First, we replace the Euclidean metric