To design an optimal graph quantizer, we minimize the *empirical distortion*

$${\hat{D}}_{N}({\mathcal{C}})={\frac{1}{N}}\sum_{i=1}^{N}\operatorname*{min}_{j\in{\mathcal{J}}}d\left(X_{i},Y_{j}\right),$$

where *C ∈ W* and S = {X1*, . . . , X*N } is a training set consisting of N independent graphs Xi drawn from XΓ . Let 1. Dˆ ∗N be the set of minimal values of the empirical distortion DˆN (C),
2. W∗N = *{C ∈ W* : DˆN (C) = Dˆ ∗N } be the set of empirical codebooks, and 3. W∗Nε = *{C ∈ W* : DˆN (C) ≤ Dˆ ∗N + ε} be the set of approximate solutions.

The next result shows that estimators based on empirical distortions are consistent estimators.

Theorem 1. *Suppose that* Q = (X , Γ, π) is a Riemannian orbifold, d(*X, Y* ) is a locally Lipschitz metric on XΓ with integrable Lipschitz constant, and W ⊆ X k Γ
is compact. Then we have

$$\begin{array}{c}{{\operatorname*{lim}_{N\to\infty}\hat{D}_{N}^{*}\left(\omega\right)=D^{*}}}\\ {{\operatorname*{lim}_{N\to\infty}\mathcal{W}_{N}^{*}\left(\omega\right)=\mathcal{W}^{*}}}\\ {{\operatorname*{lim}_{N\to\infty}\mathcal{W}_{\epsilon N}^{*}\left(\omega\right)=\mathcal{W}_{\epsilon}^{*}}}\end{array}$$

almost surely.

The proof follows from [8] applied to the lift ˜d of distortion d. Examples of locally Lipschitz distance metrics on XΓ with integrable Lipschitz constants are metrics induced by an optimal alignment kernel

$$d(X,Y)=\operatorname*{min}_{\mathbf{x}\in X,\mathbf{y}\in Y}\|\mathbf{x}-\mathbf{y}\|$$
as well as $d(X,Y)^2$. 
K-Means. In order to extend the standard k-means method to graphs for constructing an empirical codebook, we use the following update rule

$${\mathbf{y}}_{j}^{t+1}={\frac{1}{N_{j}^{t}}}\sum_{i=1}^{N}q_{i j}^{t}{\mathbf{x}}_{i},$$

where t > 0 is the iteration, xi ∈ Xi and y t j ∈ Y
t j are vector representations that are optimally aligned,1 and Qt =q t ij is the matrix representation of the nearest neighbor quantizer Qtrestricted to the training set S. The elements of Qt are of the form

$$q_{i j}^{t}=\left\{\begin{array}{l l l}{{1}}&{{:}}&{{Q^{t}(X_{i})=Y_{j}^{t}}}\\ {{0}}&{{:}}&{{\mathrm{otherwise}}}\end{array}\right..$$

1 Recall that two vector representations x ∈ X and y ∈ Y are optimally aligned if kx − yk = d(X, Y )