  **A1**: The sequence $(\eta_{t})_{t\geq0}$ of step sizes satisfies  $$\eta_{t}>0,\quad\lim_{t\to\infty}\eta_{t}=0,\quad\sum_{t=1}^{\infty}\eta_{t}=\infty,\quad\sum_{t=1}^{\infty}\eta_{t}^{2}<\infty.$$ **A2**: The stochastic generalized gradients $(S_{t})_{t\geq0}$ satisfy (5). **A3**: The expected squared norm of stochastic generalized gradients $(S_{t})_{t\geq0}$ is bounded by 

$$\mathbb{E}\left|\left\|S_{t}\right\|^{2}\right|<+\infty.$$
The next result shows that the SGG method is a consistent estimator.

Theorem 2. Let Q = (X , Γ, π) be a Riemannian orbifold and let d(X, Y ) *be a* generalized differentiable metric on XΓ *. Suppose that assumptions* (A1) − (A3)
hold. Then the sequence (Ct)t≥0 generated by the SGG method converges almost surely to graphs satisfying necessary extremum conditions

$${\mathcal W}^{*}=\left\{{\mathcal C}\in{\mathcal W}\,:\,0\in\partial D({\mathcal C})\right\}.$$
_Besides the sequence $(D(\mathcal{C}_{t}))_{t\geq0}$ converges almost surely and we have_  $$\lim_{t\to\infty}D(\mathcal{C}_{t})\in D(\mathcal{W}^{*}).$$

The proof is a direct consequence of Ermoliev and Norkin's Theorem [11] applied on the lift ˜d (·|·) of d (·|·).

## 5 Remarks To Gq Using The Graph Edit Distance

In many applications, the graph edit distance is discontinuous. Examples include edit distances with constant non-zero deletion and/or insertion cost. A necessary
(but not sufficient) condition for the consistency results stated in Theorem 1 and 2 is that the underlying graph distortion is locally Lipschitz. Hence, both consistency results are inapplicable for discontinuous graph distortions. Let us consider both cases separately.

Estimators based on Empirical Distortion Measures. Estimators based on empirical distortion measures aim at approximating the expected distortion D(C)
by its empirical mean

$$\operatorname*{min}_{{\mathcal{C}}\in{\mathcal{W}}}\quad{\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).$$

As shown in [10], minimizing the empirical distortion is often meaningless, if the underlying graph edit distance function d (·|·) and thus DˆN (C) is discontinuous, even if the expectation D(C) may be continuously differentiable. Since the local solutions of DˆN (C) may have nothing in common with the local solutions of the original problem, estimators based on the empirical distortion DˆN (C) can be statistically inconsistent. Hence, minimizing DˆN (C) with underlying discontinuous graph edit distance using global or local optimization techniques like, for example, k-means lacks theoretical support.