{'fraction_non_alphanumeric': 0.040256542403939756, 'fraction_numerical': 0.005039225791673825, 'mean_word_length': 4.2600903614457835, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 15, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Graph Quantization

Vector quantization(VQ) is a lossy data compression technique from signal processing, which is restricted to feature vectors and therefore inapplicable for combinatorial structures. This contribution presents a theoretical foundation of graph quantization (GQ) that extends VQ to the domain of attributed graphs. We present the necessary Lloyd-Max conditions for optimality of a graph quantizer and consistency results for optimal GQ design based on empirical distortion measures and stochastic optimization. These results statistically justify existing clustering algorithms in the domain of graphs. The proposed approach provides a template of how to link structural pattern recognition methods other than GQ to statistical pattern recognition.


Introduction
Vector quantization is a classical technique from signal processing suitable for lossy data compression, density estimation, and prototype-based clustering [7,14,30]. The problem of optimal vector quantizer design is to find a codebook consisting of a finite set of prototypes such that an expected distortion with respect to some (differentiable) distortion measure is minimized.
Since the probability distribution of the input patterns is usually unknown, vector quantizer design techniques use empirical data. Extensively studied design techniques are, for example, k-means and simple competitive learning. The kmeans algorithm is also commonly referred to as the Linde-Buzo-Gray (LBG) algorithm [24] the generalized Lloyd algorithm [25]. This algorithm is a local optimizer of the empirical sum-of-squared-error distortion without any global optimal or consistency guarantees. In contrast to k-means, competitive learning directly minimizes the expected distortion and is a consistent learner under very general conditions in the sense that it almost surely converges to a local optimal solution of the expected distortion.
One limitation of VQ is its restriction to patterns that are represented by vectors. For patterns that are more naturally represented by finite combinatorial structures, the theoretical framework of VQ as well its design techniques are no longer applicable. Examples of such structures include, for example, point patterns, strings, trees, and graphs arising from diverse application areas like proteomics, chemoinformatics, and computer vision.
To overcome this limitation, we generalize vector quantization to quantization of graphs. A number of graph quantizer design techniques for the purpose of prototype-based clustering have already been proposed. Examples include competitive learning algorithms in the domain of graphs [16][17][18][19][20]22] and k-means as well as k-medoids algorithms [12,13,19,20,23,28,29]. Related clustering method are presented in [3,26,31]. Due to a lack of an appropriate theoretical framework, all these graph quantizer design techniques (or clustering methods) have been developed in order to minimize an empirical distortion function without justifying whether the solutions found are statistically consistent estimators of the true but unknown solutions. In addition, it is unclear whether the nearest neighbor and centroid condition, which are also referred to as the Lloyd-Max conditions, are necessary conditions for optimality.
In this contribution, we propose graph quantization in a mathematically principled way as an extension of vector quantization, where we consider the graph edit distance as an underlying graph distortion measure. The key results of this contribution are consistency statements for estimators based on empirical distortion measures and estimators based on stochastic optimization. Furthermore, we prove that the Llyod-Max conditions are also necessary condition for optimal graph quantizers. In order to achieve the consistency results and the Lloyd-Max conditions, we isometrically embed -without loss of structural informationgraphs as points into some Riemannian orbifold. An orbifold is the quotient of a manifold by a finite group action and therefore generalizes the notion of manifold. Using orbifolds we can define geometric and analytic concept such as length, angle, derivative, gradient, and integral locally to a Euclidean space. This construction forms the basis for extending consistency results from Euclidean vector spaces to the domain of graphs.
The proposed approach has the following properties: First, it can be applied to finite combinatorial structures other than graphs like, for example, point patterns, sequences, trees, and hypergraphs. For the sake of concreteness, we restrict our attention exclusively to the domain of graphs. Second, for graphs consisting of a single vertex with feature vectors as attributes, graph quantization coincides with vector quantization. Third, the proposed consistency results justify some of the above referenced graph clustering methods as statistically consistent learners. Fourth, the underlying mathematical framework can be applied in order to link other structural pattern recognition methods that directly operate in the domain of graphs to methods from statistical pattern recognition.
The paper is organizes as follows. Section 2 describes the problem of graph quantizer design. Section 3 introduces Riemannian orbifolds. In Section 4, we extend VQ to GQ and present consistency result for GQ design techniques. Section 5 briefly discusses the case of general graph edit distance functions. Finally, Section 6 concludes.

The Problem of Graph Quantizer Design
This section aims at outlining the problem of extending VQ to the quantization of graphs.

Attributed Graphs
To begin with, we first describe the structures we want to quantize.
Let A be a set of attributes and let ε ∈ A be a distinguished element denoting the null or void element. An attributed graph is a tuple X = (V, α) consisting of a finite nonempty set V of vertices and an attribute function α : V × V → A. Elements of the set are the edges of X. By G A we denote the set of all attributed graphs with attributes from A. The vertex set of an attributed graph X is often referred to as V X and its attribute function as α X .
An alignment of a graph X is a graph X with V X ⊆ V X and for all i, j ∈ V X . Thus, we obtain an alignment of X by adding isolated vertices with null-attribute. The set V X \ V X is the set of aligned vertices. By A(X) we denote the (infinite) set of all alignments of X.
A pairwise alignment of graphs X and Y is a triple (φ, X , Y ) consisting of alignments X ∈ A(X) and Y ∈ A(Y ) together with a bijective mapping By A(X, Y ) we denote the set of all pairwise alignments between X and Y . Sometimes we briefly write φ instead of (φ, X , Y ).

The Graph Edit Distance
Fundamental for quantizing data is the notion of distortion. This section briefly introduces the graph edit distance functions as our choice of distortion measure. For a more detailed definition of the graph edit distance, we refer to [2]. In addition, we present an important graph metric based on a generalization of the concept of maximum common subgraph, which arises in various different guises as a common choice of proximity measure [1,5,6,15,32,33]. For sake of convenience, we assume that all distances are metrics.
Each pairwise alignment (φ, X , Y ) ∈ A(X, Y ) can be regarded as an edit path with cost where d A : A × A → R + is a distance function defined on the set A of attributes. Observe that deletion (insertion) of vertices also deletes (inserts) all edges the respective vertices are incident to.
The graph edit distance of X and Y is then defined as the edit path with minimal cost Note that the set A(X, Y ) of pairwise alignments is of infinite cardinality. But since d A (ε, ε) = 0, we actually take the minimum over a finite subset by ignoring all pairwise alignments that map aligned vertices with null-attributes onto each other. Next, we consider an important example of the graph edit distance based on a generalization of the concept of maximum common subgraph. We derive this graph metric from a similarity measure in the same way the Euclidean distance is derived from an inner product.
Suppose that k A : A × A → R with k A (·, ε) = 0 is a positive definite kernel. We measure the quality of a pairwise alignment φ ∈ A(X, Y ) by An optimal alignment kernel is a graph similarity measure of the form Note that k (·|·) is symmetric but indefinite as a pointwise maximizer of a set of positive definite kernels. The distance metric on G A induced by an optimal alignment kernel k (·|·) is defined by where l(X) = k(X, X) denotes the length of an attributed graph X. As shown in [23], d is indeed a metric and can be expressed as a graph edit distance.

The Problem of Graph Quantizer Design
Let (G A , d) be a graph distance space, where d (·|·) is a graph edit distance. Optimal graph quantization design aims at minimizing the expected distortion where Q : G A → C is a graph quantizer, C = {Y 1 , . . . , Y k } a codebook consisting of k code graphs, and P = P G A is a probability measure defined on some appropriate measurable space (G A , Σ G A ). As opposed to vector quantization, the following factors complicate designing an optimal graph quantizer in a statistically consistent way: 1. The graph distance d(X, Y ) is in general non-convex and non-differentiable. 2. Neither a well-defined addition on graphs nor the notion of derivative for functions on graphs is known.
To overcome these difficulties, we isometrically embed graphs as points into a Riemannian orbifold in order to apply methods that generalize gradient descent techniques and methods from stochastic optimization for non-convex and nondifferentiable distortion functions.

Riemannian Orbifolds
Orbifolds generalize the notion of manifold as locally being a quotient of R n by finite group actions. Consequently, learning on orbifolds generalizes learning on Euclidean spaces and Riemannian manifolds. This section introduces Riemannian orbifolds and their intrinsic metric structure. Proofs for new results are delegated to Section B.1. For all other proofs we refer to [4,21].

Riemannian Orbifolds
To keep the treatment simple, we assume that X = R n is the n-dimensional Euclidean vector space, and Γ is a permutation group acting on X . In a more general setting, however, we can assume that X is a Riemannian manifold, and Γ is a finite group of isometries acting effectively on X . The binary operation is a group action of Γ on X . For x ∈ X , the orbit of x is the set defined by The quotient set consisting of all all orbits carries the structure of a Riemannian orbifold. Its orbifold chart is the surjective continuous mapping that projects each point x to its orbit [x].
In the following, an orbifold is a triple Q = (X , Γ, π) consisting of an Euclidean space X , a permutation group Γ acting on X and its orbifold chart π. With Γ = {id} being the trivial permutation group consisting of the identity only, a manifold X is also an orbifold. In general, however, the underlying space X Γ of an orbifold is not a manifold. Thus, orbifolds generalize the notion of manifold. The points at which an orbifold X Γ is locally not homeomorphic to a manifold are its singular points. We call the elements of X Γ structures, since they represent combinatorial structures like attributed graphs. We use capital letters X, Y, Z, . . . to denote structures from X Γ and write, by abuse of notation, x ∈ X if π(x) = X. Each vector x ∈ X is a vector representation of structure X and the set X of all vector representation is the representation space of X Γ . Example 1. Let X = R 2 and let Γ be the group generated by reflections across the main-diagonal of the x-y-plane. Then Q = (X Γ , Γ, π) is a Riemannian orbifold with The singular points of X Γ are all structures X represented by vectors

The Riemannian Orbifold of Attributed Graphs
In this section, we show that attributes graphs can be identified with points in some Riemannian orbifold.
Riemannian orbifolds of attributed graphs arise by considering equivalence classes of matrices representing the same graph. To identify graphs with points in a Riemannian orbifold without loss of structural information, some technical assumptions and restrictions to simplify the mathematical treatment are necessary. For this, let (G A , d) be a graph distance space with graph edit distance d(·|·). Then we make the following assumptions: P1 There is a feature map Φ : A → H of the attributes into some finite dimensional Euclidean feature space H and a distance function d H : for all attributes a, a ∈ A. P2 All graphs are finite of bounded order n, where n is a sufficiently large number. Graphs X of order less than n, say m < n, are aligned to graphs X of order n by inserting p = n − m isolated vertices with null attribute ε.
Before discussing the impact of both assumptions for practical application, we first restate our first assumptions for graph metrics induced by optimal alignment kernels. By definition k A : A × A → R is a positive definite kernel corresponding to an inner product k A (x, y) = Φ(x), Φ(y) in some feature space H. Our first assumption requires that H is a finite dimensional Euclidean space and Φ(ε) = 0. Now let us consider the above assumptions in more detail. Both conditions do not effect the graph edit distance, provided an appropriate feature map for the attributes can be found. Restricting to finite dimensional Euclidean feature spaces H is necessary for deriving consistency results and for applying methods from stochastic optimization. Limiting the maximum size of the graphs to some arbitrarily large number n and aligning smaller graphs to graphs of oder n are purely technical assumptions to simplify mathematics. For machine learning problems, this limitation should have no practical impact, because neither the bound n needs to be specified explicitly nor an extension of all graphs to an identical order needs to be performed. When applying the theory, all we actually require is that the order of the graphs is bounded.
With both assumptions in mind, we construct the Riemannian orbifold of attributed graphs. Let X = H n×n be the set of all (n×n)-matrices with elements from feature space H. A graph X is completely specified by a representation matrix X = (x ij ) from X with elements The form of a representation matrix X of X is generally not unique and depends on how the vertices are arranged in the diagonal of X. Now suppose that Π n be the set of all (n × n)-permutation matrices. For each P ∈ Π n we define a mapping Then Γ = {γ P : P ∈ Π n } is a permutation group acting on X . Regarding an arbitrary matrix X as a representation of some graph X, then the orbit [X] consists of all possible matrices that can represent X. By identifying the orbits of X Γ with attributed graphs, the set G A of attributed graphs of bounded order n is a Riemannian orbifold.

Metric Structures
Let Q = (X , Γ, π) be an orbifold. We derive an intrinsic metric that enables us to do Riemannian geometry. In the case of a Riemannian orbifold of attributed graphs the intrinsic metric coincides with the graph metric of (2) induced by an optimal alignment kernel.
Any inner product ·, · on X gives rise to a maximizer of the form We call the kernel function k(·|·) optimal alignment kernel, induced by the inner product ·, · . Note that the maximizer of a set of positive definite kernels is an indefinite kernel in general. Since Γ is a group, we find that where y is an arbitrary but fixed vector representation of Y . In general, we have for all x ∈ X and y ∈ Y .
Example 2. Consider the Riemannian orbifold (X , Γ, π) of Example 1, where X = R 2 and Γ = {id, γ} is the group generated by reflections across the x-yplane. Suppose that x = (1, 2) is a vector representation of X and y = (3, 2) is a vector representation of Y . Then the optimal alignment kernel k (X, Y ) induced by the standard inner product of X is given by Evaluating the inner products yields Thus, we have k(X, Y ) = 8.
Example 3. Suppose that X and Y are attributed graphs where edges have attribute 1 and vertices have attribute 0. The optimal alignment kernel k (X, Y ) induced by the standard inner product of X is the number of edges of a maximum common subgraph of X and Y .
Example 4. More generally, if property P1 is satisfied, then any optimal alignment kernel on a bounded set of attributed graphs as defined in (1) is also an optimal assignment kernel of some Riemannian orbifold.
Suppose that X ∈ X Γ . Since k(X, X) = x, x for all x ∈ X, we can define the length of X by l(X) = k(X, X).
The optimal alignment kernel together with the length satisfies the Cauchy-Schwarz inequality |k(X, Y )| ≤ l(X) · l(Y ).
Since the Cauchy-Schwarz inequality is valid, the geometric interpretation of k(·|·) is that it computes the cosine of a well-defined angle between X and X provided they are normalized to length 1. Likewise, k(·|·) gives rise to a distance function defined by From the definition of k(·|·) follows that d is a metric. In addition, we have where · denotes the Euclidean norm induced by the inner product ·, · of the Euclidean space X .
Suppose that x = (1, 2) is a vector representation of X and y = (3, 2) is a vector representation of Y . Then the squared lengths of X and Y are l(X) 2 = 5 and l(Y ) 2 = 13. Since k(X, Y ) = 8 according to Example 2, the distance is Example 6. If properties P1 and P2 are satisfied, then the graph metric (2) coincides with the intrinsic orbifold metric (3).
Equation (3) states that d (·|·) is the length of a minimizing geodesic of X and Y and therefore an intrinsic metric, because it coincides with the infimum of the length of all admissible curves from X to Y . In addition, we find that the topology of X Γ induced by the metric d coincides with the quotient topology induced by the topology of the Euclidean space X .

Orbifold Functions
Suppose that Q = (X , Γ, π) is an orbifold. An orbifold function is a mapping The lift of f is a functionf : We say, an orbifold function f : X Γ → R is continuous (locally Lipschitz, differentiable, generalized differentiable) at X ∈ X Γ if its liftf is continuous (locally Lipschitz, differentiable, generalized differentiable) at some vector representation x ∈ X. The definition is independent of the choice of the vector representation that projects to X (see Section B.1, Prop. 1 -Prop. 4). For a definition of generalized differentiable functions and their basic properties we refer to Section A.
Example 7. Consider the Riemannian orbifold (X , Γ, π) of Example 1-5. The function for some Y ∈ X Γ is an orbifold function with lift where y ∈ Y . Analytical properties of f such as continuity and differentiability can be investigated using the liftf of f . For example, iff is differentiable at x ∈ X then it is also differentiable at γ(x) according to Prop. 3. Hence, differentiability of the orbifold function f is well-defined at X.

Gradients and Generalized Gradients of Orbifold Functions
We extend the notion of gradient and generalized gradient to differentiable and generalized differentiable orbifold functions.

Gradient of Differentiable Orbifold
Functions. Suppose that f : X Γ → R is differentiable at X ∈ X Γ . Then its liftf : X → R is differentiable at all vector representations that project to X. The gradient ∇f (X) of f at X is defined by the projection ∇f (X) = π ∇f (x) of the gradient ∇f (x) off at a vector representation x ∈ X. This definition is independent of the choice of the vector representation. We have for all γ ∈ Γ . This implies that the gradients off at x and γ(x) are vector representations of the same structure, namely the gradient ∇f (X) of the orbifold function f at X. Thus, the gradient of f at X is a well-defined structure pointing to the direction of steepest ascent (see Section B.1, Prop. 3).

Subdifferential of Generalized Differentiable Orbifold
Functions. Suppose that f : X Γ → R is generalized differentiable at X ∈ X Γ . Then its liftf : X → R is generalized differentiable at all vector representations that project to X. The subdifferential ∂f (X) of f at X is defined by the projection of the subdifferential ∂f (x) off at a vector representation x ∈ X. This definition is independent of the choice of the vector representation. We have for all γ ∈ Γ . This implies that the subdifferentials ∂f (x) ⊆ X and ∂f (γ(x)) ⊆ X are subsets that project to the same subset of X Γ , namely the subdifferential ∂f (X) (see Section B.1, Prop. 4). The properties of generalized differentiable function as listed in Section A carry over to generalized differentiable orbifold functions via their lifts. For example, a generalized differentiable orbifold function is locally Lipschitz and therefore differentiable almost everywhere.
is a graph edit distance. We can identify G A with a Riemannian orbifold Q = (X , Γ, π) and the graph edit distance d (·|·) with a distance function defined on X Γ . Suppose that the cost functions d φ (·|·) of the edit paths are continuously differentiable (generalized differentiable). Then the distance d (·|·) is generalized differentiable.

Integration on Orbifolds
Suppose that Q = (X , Γ, π) is a Riemannian orbifold with singular set S Q . In order to integrate orbifold functions f : X Γ → R by the Lebesgue integral, we need to construct an appropriate measurable space together with an orbifold measure. The measurable space is defined by the Borel set B(X Γ ) generated by the open sets of X Γ . From the orbifold measure we expect that it is compatible with the local Riemannian measures. In addition, we demand that the singular set S Q has measure 0. This is motivated by the following fact: The singular set is covered locally by the finite union of totally geodesic submanifolds, which has measure 0 relative to the local canonical Riemannian measure. Since the projection to the orbifold is distance decreasing, it is reasonable to ask for an orbifold measure that assigns measure 0 to the singular set S Q . Let B (X Γ \ S Q ) denote the Borel set generated by the open sets of X Γ \ S Q . Then there exists a complete canonical measure µ on the the Borel set B (X Γ \ S Q ) given by a unique volume form on X Γ \ S Q . The measure µ can be extended to a complete measure ν on the Borel set B(X Γ ) such that In particular, we have ν(A) = 0 for any subset A ⊆ S Q . For proofs we refer to [4].
In the following we write for the integral of an orbifold function f : U Γ → R defined on a measurable subset U Γ ⊆ X Γ . We tacitly assume that all integrals occurring in the following sections exist.

Graph Quantization
This section extends vector quantization to quantization of graphs.

The Basics
Suppose that Q = (X , Γ, π) is a Riemannian orbifold. A graph quantizer of size k is a mapping of the form Q : X Γ → C where C = {Y 1 , . . . , Y k } ⊆ X Γ is a finite set, called codebook. The elements Y j ∈ C are the code graphs. The graph quantizer Q partitions the input space such that their union covers X Γ . By P Q we denote the partition of Q consisting of all k regions R j . Suppose that J = {1, . . . , k}. The basic operation of a vector quantizer Q can be written as a composition Q = d Q • e Q of an encoder e Q : X Γ → J and a decoder d Q : J → C. The encoder assigns each input graph to a region via the index set J . The decoder maps indices of J referring to regions to code graphs.

Graph Quantizer Performance
We measure the performance of a graph quantizer Q by the expected distortion where X ∈ X Γ is a random variable with probability measure P = P X Γ representing the observable graphs to be quantized. The expectation E X is taken with respect to some probability space (X Γ , Σ X Γ , P X Γ ). The quantity d(X, Y ) measures the distortion of the random input graph X and code graph Y . Here we consider graph distortion measures that are graph edit distances. An example is the squared metric induced by an optimal alignment kernel Using the codebook and partition for the given quantizer Q, we can rewrite the expected distortion by

The Problem of Optimal Graph Quantizer Design
The problem of optimal graph quantizer design is stated as follows: Find a codebook C specifying the decoder d Q and a partition P Q specifying the encoder e Q such that the expected distortion D(Q) is minimized. The composite mapping Q = d Q • e Q of the resulting encoder and decoder is then an optimal graph quantizer.
An optimal graph quantizer satisfies the following necessary conditions, also known as the Lloyd-Max conditions: 1. Nearest Neighbor Condition. Given a fixed codebook C, a graph quantizer Q is optimal, if the code vector Q(X) of an input pattern X satisfies the nearest neighbor rule for all X ∈ X Γ , where ties are resolved according to some rule. A proof is given in Section B.2, Theorem 3.
2. Centroid Condition. Given a fixed partition P Q , a vector quantizer Q is optimal, if each code vector Y j is the centroid of region R j , that is for all Y ∈ X Γ and all j ∈ J . A proof is given in Section B.2, Theorem 4.
Note that Y j with is called a centroid of region R j . 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.

Graph Quantizer Design
Since the distribution P = P X Γ 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 W ⊂ X k Γ = X Γ × · · · × X Γ k-times of the topological space X k Γ . The problem of designing an optimal quantizer for graphs is then of the form where the minimum is taken over the compact set W rather than X k Γ . Let To design an optimal graph quantizer, we minimize the empirical distortion where C ∈ W and S = {X 1 , . . . , X N } is a training set consisting of N independent graphs X i drawn from X Γ . Let 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 The proof follows from [8] applied to the liftd 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 ) = min x∈X,y∈Y x − 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 where t > 0 is the iteration, x i ∈ X i and y t j ∈ Y t j are vector representations that are optimally aligned, 1 and Q t = q t ij is the matrix representation of the nearest neighbor quantizer Q t restricted to the training set S. The elements of Q t are of the form 1 Recall that two vector representations x ∈ X and y ∈ Y are optimally aligned if The quantity N t 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 using a training set S = {X 1 , . . . , X N } of N independent graphs X i drawn from X Γ . We assume that the loss function 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 under mild assumptions (see [11,27]), we can minimize the expected distortion D(C) according to the following stochastic generalized gradient (SGG) method: where x t is a vector representation of input pattern X t ∈ S, which is optimally aligned to vector representation y t of a code graph Y t closest to X t . The random elements s t = x t − y t ∈ S t are vector representations of stochastic generalized gradients S t , i.e. random variables defined on the probability space We consider the following conditions for almost sure convergence of stochastic optimization: A1 The sequence (η t ) t≥0 of step sizes satisfies A2 The stochastic generalized gradients (S t ) t≥0 satisfy (5). A3 The expected squared norm of stochastic generalized gradients (S t ) t≥0 is bounded by 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 (C t ) t≥0 generated by the SGG method converges almost surely to graphs satisfying necessary extremum conditions Besides the sequence (D(C t )) t≥0 converges almost surely and we have The proof is a direct consequence of Ermoliev and Norkin's Theorem [11] applied on the liftd (·|·) of d (·|·).

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 As shown in [10], minimizing the empirical distortion is often meaningless, if the underlying graph edit distance function d (·|·) and thusD N (C) is discontinuous, even if the expectation D(C) may be continuously differentiable. Since the local solutions ofD N (C) may have nothing in common with the local solutions of the original problem, estimators based on the empirical distortionD N (C) can be statistically inconsistent. Hence, minimizingD N (C) with underlying discontinuous graph edit distance using global or local optimization techniques like, for example, k-means lacks theoretical support.
Estimators based on Stochastic Optimization. The situation is better for estimators based on methods from stochastic optimization. For discontinuous graph edit distances d (·|·) the expected distortion can be minimized in a statistically consistent way, for example, by methods based on approximations of d (·|·) via averaged functions obtained by convolution with so-called mollifiers. For details, we refer to [9].

Conclusion
This contribution proposes a theoretical sound foundation of graph quantization generalizing the ideas of vector quantizations to the domain of attributed graph. We presented consistency results for graph quantizer design, where the underlying graph edit distances is generalized differentiable. As for vectors, estimators based on empirical distortion and stochastic optimization are statistically consistent. If the underlying distortion measure is a discontinuous graph edit distance, estimators based on empirical distortion measures lack theoretical justification. Thus, the proposed consistency results justify existing research on prototype-based clustering in the domain of graphs. In addition, we showed that the Lloyd-Max conditions are necessary conditions for optimality of GQ. The mathematical framework that enables us to derive consistency results are Riemannian orbifolds. Identifying graphs with points in a Riemannian orbifold provides us locally access to a Euclidean space. This in turn allows us to introduce geometrical and analytical concepts for extending vector quantization to the domain of graphs. The implication of this approach is that it provides us a template for consistently linking methods from structural pattern recognition other than GQ to statistical pattern recognition methods.
Next we show thatf is upper semicontinuous at x . Suppose that y i → x , g i ∈f c (y i ) for each i ∈ N, and g is an accumulation point of (g i ) i∈N . Then there is a i 0 ∈ N such that y i ∈ U δ (x ) for all i ≥ i 0 . From U δ (x ) = U δ (γ(x)) = γ (U δ (x)) follows that there are vector representations y i ∈ U δ (x) with γ(y i ) = y i for each i ≥ i 0 . From continuity of γ −1 follows that y i → x. By construction of ∂f follows that g i ∈ ∂f (y i ) = ∂f (γ (y i )) = γ ∂f (y i ) for each i ≥ i 0 . Hence, there are vector representations g i ∈ ∂f (y i ) with γ(g i ) = g i for each i ≥ i 0 . Sincef is upper semicontinuous at x, we find that g ∈ ∂f (x). Again by construction of ∂f follows that g = γ(g) ∈ γ ∂f (x) = ∂f (γ(x)) = ∂f (x ).
We define o (x , y , g ) = o • γ −1 (x , y , g ) = o(x, y, g) showing that o tends faster to zero than normy − x. This proves the subderivative property off at all vector representations projecting to X = π(x).
Putting all results together yields thatf is generalized differentiable at γ(x) for all γ ∈ Γ .

B.2 Lloyd-Max Necessary Conditions for Optimality
Due to the comparable nice analytical properties of Riemannian orbifolds, the proofs for the nearest neighbor and centroid condition of optimal graph quantizers are similar to their respective counterparts in vector quantization.
Theorem 3 (Nearest Neighbor Condition). Suppose that C is a fixed codebook. Any graph quantizer Q : X Γ → C with for all X ∈ X Γ , where ties are resolved according to some rule, has minimal expected distortion.
Proof. Suppose that Q : X Γ → C is a graph quantizer with arbitrary regions. Then we have d(X, Q (X)) ≥ min for all X ∈ X Γ . This implies D(Q ) = E X [d (X, Q (X))] ≥ E X [d (X, Q(X))] = D(Q).
Theorem 4 (Nearest Neighbor Condition). Suppose that P Q is a fixed partition and Q : X Γ → C a graph quantizer with codebook C satisfying for all Y ∈ X Γ and all j ∈ J . Then Q has minimal expected distortion.
Proof. Let P j = P (X ∈ R j ). Suppose that Q is a quantizer with partition {R 1 , . . . , R k } and arbitrary codebook C = {Y 1 , . . . , Y k }. Then we have