General graph matching methods often suffer from the lack of mathematical structure in the space of graphs. Using kernel functions to evaluate structural graph similarity allows us to formulate the graph matching problem in an implicitly existing vector space and to apply well-known methods for pattern analysis. In this paper we propose a novel convolution graph kernel. Our kernel function differs from other graph kernels mainly in that it is closely related to error-tolerant graph edit distance and can therefore be applied to attributed graphs of various kinds. The proposed kernel function is evaluated on two graph datasets. It turns out that our method is generally more accurate than a standard edit distance based nearest-neighbor classifier, an edit distance based kernel variant, and a random walk graph kernel.