# Graph Quantization

Brijnesh J. Jain 1 and Klaus Obermayer 1 1Berlin Institute of Technology, Germany
{jbj|oby}@cs.tu-berlin.de Abstract. 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.

## 1 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 arXiv:1001.0921v1 [cs.AI] 6 Jan 2010