prototype-based clustering have already been proposed. Examples include competitive learning algorithms in the domain of graphs [16–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 information –
graphs 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.

## 2 The Problem Of Graph Quantizer Design

This section aims at outlining the problem of extending VQ to the quantization of graphs.