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 aims at extending VQ to the quantization of graphs in a theoretically principled way in order to overcome practical limitations known in the context of prototype-based clustering of graphs. For this, we present the following results: (i) A proof of the necessary Lloyd-Max conditions for optimality of a graph quantizer, (ii) consistency statements for optimal graph quantizer design, and (iii) an accelerated version of competitive learning graph quantization. In order to achieve the proposed results, we present graphs as points in some orbifold. The orbifold framework will introduce sufficient mathematical structure to allow an extension of VQ to graph quantization in a theoretically sound way without discarding the relational information of the graphs. In doing so the proposed approach provides a template of how to link structural pattern recognition methods other than graph quantization to statistical pattern recognition.