2. *Centroid Condition*. Given a fixed partition PQ, a vector quantizer Q is optimal, if each code vector Yj is the centroid of region Rj , that is

$$Y_{j}=\arg\operatorname*{min}_{Y\in{\mathcal{X}}_{\Gamma}}\mathbb{E}\left[d\left(X,Y\right)\mid X\in{\mathcal{R}}_{j}\right]$$

for all Y ∈ XΓ and all j ∈ J . A proof is given in Section B.2, Theorem 4.

Note that Yj with

$$Y_{j}=\arg\operatorname*{min}_{Y\in{\mathcal{X}}_{\Gamma}}\mathbb{E}\left[d\left(X,Y\right)\mid X\in{\mathcal{R}}_{j}\right]$$

is called a *centroid* of region Rj . The centroids may not be unique. This also holds for squared metrics induced by some optimal assignment kernel, which are the counterparts of squared Euclidean distances.

## 4.4 Graph Quantizer Design

Since the distribution P = PXΓ
of the observable graphs is usually unknown, the expected distortion D(C) can neither be computed nor be minimized directly.

Instead, we design (estimate) an optimal quantizer from empirical data. For vectors, prominent methods for designing an optimal quantizer are k-means and simple competitive learning. Both methods, k-means and simple competitive learning have been extended for designing graph quantizers in the context of prototype based clustering. To derive consistency results for k-means and simple competitive learning in the domain of graphs, we consider estimators based on empirical distortions and on stochastic approximation.

Estimators based on Empirical Distortion Measures. In order to derive consistency results, we restrict the set of feasible codebooks to a compact
subspace
$${\mathcal{W}}\subset{\mathcal{X}}_{\Gamma}^{k}=\underbrace{{\mathcal{X}}_{\Gamma}\times\cdot\cdot\times{\mathcal{X}}_{\Gamma}}_{\mathrm{k-times}}$$
of the topological space X
k
Γ
. The problem of designing an optimal quantizer for
graphs is then of the form
$$\operatorname*{min}_{{\mathcal{C}}\in{\mathcal{W}}}\quad D({\mathcal{C}})=\sum_{j=1}^{k}\int_{{\mathcal{R}}_{j}}d(X,Y)d P(X).$$
where the minimum is taken over the compact set W rather than X
k Γ
. Let 1. D∗ be the set of minimal values of the expected distortion D(C),
2. W∗ = *{C ∈ W* : D(C) = D∗} be the set of true (optimal) codebooks, and 3. W∗
ε = *{C ∈ W* : D(C) ≤ D∗ + ε} be the set of approximate solutions.