Vector quantization(VQ) is a lossy data compression technique from signal
processing for which simple competitive learning is one standard method to
quantize patterns from the input space. Extending competitive learning VQ to
the domain of graphs results in competitive learning for quantizing input
graphs. In this contribution, we propose an accelerated version of competitive
learning graph quantization (GQ) without trading computational time against
solution quality. For this, we lift graphs locally to vectors in order to avoid
unnecessary calculations of intractable graph distances.

This paper extends k-means algorithms from the Euclidean domain to the domain
of graphs. To recompute the centroids, we apply subgradient methods for solving
the optimization-based formulation of the sample mean of graphs. To accelerate
the k-means algorithm for graphs without trading computational time against
solution quality, we avoid unnecessary graph distance calculations by
exploiting the triangle inequality of the underlying distance metric following
Elkan's k-means algorithm proposed in \cite{Elkan03}.