IAM  Incremental Arithmetic Mean. The elementary incremental subgradient method randomly chooses a sample graph Xtfrom ST at each iteration t and updates the estimates y t ∈ Y
t of the vector representations of a sample mean according to the formula

$$y^{t+1}=y^{t}-\eta^{t}\left(y^{t}-x^{t}\right),$$

where η tis the step size and (x t, y t) is an optimal alignment.

As a special case of the incremental subgradient algorithm, the incremental arithmetic mean method emulates the incremental calculation of the standard sample mean. First the order of the sample graphs from ST is randomly permuted. Then a sample mean is estimates according to the formula

$$y^{\perp}=x^{\perp}$$
1
$$\begin{array}{r l r l}{{\boldsymbol{y}}^{i}}&{{}={\cfrac{i-1}{i}}\,{\boldsymbol{y}}^{i-1}+{\cfrac{1}{i}}\,{\boldsymbol{x}}^{i}}&{}&{{}{\mathrm{~for~}}1<i\leq N}\end{array}$$

where xi, y i−1are optimal alignments for all 1 < i ≤ N. The graph Y represented by the vector y N is an approximation of a sample mean of ST . In general, Y is not an optimal solution of problem (P). This procedure is inspired by Theorem 1.3 and requires only one iteration through the sample. The IAM
method requires m − 1 distance calculations for approximating a sample mean.

The solution quality depends on the order of selecting the sample graphs from ST .

## 3.3 The K-Means Algorithm For Graphs

Having a graph metric and a concept of sample mean, we are now in the position, to extend the k-means algorithm to structure spaces XT over some Euclidean space X . We assume that D is a distance metric induced by an Euclidean metric on X . Now suppose that ST = {X1*, . . . , X*N } is a training sample of N graphs drawn from XT . We replace the standard cluster objective J by

$$J_{T}\left(M,\mathcal{Y}_{T}\,|\,\mathcal{S}_{T}\right)=\sum_{j=1}^{k}\sum_{i=1}^{N}m_{i j}D\left(X_{i},Y_{j}\right){}^{2},$$

where YT = {Y1*, . . . , Y*k} is a set of k centroids from XT and M = (mij ) is a membership matrix dening a partition of the set ST .

Given a membership matrix M, the cluster objective JT (. |M, X) is no longer dierentiable as a function of the centroids YT . But as shown in [14, 15],
the objective JT (. |M, X) is locally Lipschitz and therefore dierentiable as a function of YT for almost all graphs. The k centroids that minimize the cluster objective JT (. |M, XT ) are the structural versions of the sample mean

$$Y_{j}=\arg\operatorname*{min}_{Y\in{\mathcal{X}}_{\mathcal{T}}}F(Y)={\frac{1}{2}}\sum_{i=1}^{N}m_{i j}D\left(X_{i},Y\right)^{2}.$$
