The quantity Nt j denotes the number of elements from the training sets that are quantized by code graph Y
t j
.

As for vectors, a drawback of k-means for graphs is that it is a local optimization technique for which existing consistency theorems are inapplicable, because Theorem 1 assumes global instead of local minimizers of the empirical distortion as estimators.

Estimators based on Stochastic Optimization. Suppose that W = X
k Γ
.

Stochastic optimization methods directly minimize the expected distortion

$$\begin{array}{r}{D\left({\mathcal{C}}\right)=\sum_{j=1}^{k}\int_{{\mathcal{R}}_{j}}d\left(X,Y_{j}\right)d\,P(X)}\\ {=\sum_{j=1}^{k}\int_{{\mathcal{X}}_{T}}\operatorname*{min}_{1\leq j\leq k}d\left(X,Y_{j}\right)d\,P(X),}\end{array}$$

using a training set S = {X1*, . . . , X*N } of N independent graphs Xi drawn from XΓ . We assume that the loss function

$$L(X,{\mathcal{C}})=\operatorname*{min}_{1\leq j\leq k}\,d\left(X,Y_{j}\right)$$

is generalized-differentiable, hence L(X, C) is differentiable almost everywhere.

Example 10. If he graph distortion d(·|·) is generalized differentiable, then the loss function L(X, C) is also generalized differentiable by calculus of generalized differentiable functions. This holds for graph distortions of Example 8 and 9.

Since the interchange of integral and generalized gradient remains valid for generalized differentiable loss functions, that is
∂D(C) = EX [∂L(X, C)]
under mild assumptions (see [11, 27]), we can minimize the expected distortion D(C) according to the following *stochastic generalized gradient* (SGG) method:

$\downarrow$ ). 
yt+1 = yt + ηt (xt − yt), (4)
where xt is a vector representation of input pattern Xt ∈ S, which is optimally aligned to vector representation yt of a code graph Yt closest to Xt. The random elements st = xt − yt ∈ St are vector representations of stochastic generalized gradients St, i.e. random variables defined on the probability space
(XΓ , ΣXΓ
, PXΓ
)
∞ such that

$$\mathbb{E}\left[S_{t}\left|\,{\mathcal{C}}_{0},\ldots,{\mathcal{C}}_{t}\right|\right]\in\partial D\left({\mathcal{C}}\right).$$
$\left(5\right)$. 
E [St | C0*, . . . ,* Ct] ∈ ∂D (C). (5)
We consider the following conditions for almost sure convergence of stochastic optimization: