  Graph kernels have recently emerged as a promising approach for tackling the
graph similarity and learning tasks at the same time. In this paper, we propose
a general framework for designing graph kernels. The proposed framework
capitalizes on the well-known message passing scheme on graphs. The kernels
derived from the framework consist of two components. The first component is a
kernel between vertices, while the second component is a kernel between graphs.
The main idea behind the proposed framework is that the representations of the
vertices are implicitly updated using an iterative procedure. Then, these
representations serve as the building blocks of a kernel that compares pairs of
graphs. We derive four instances of the proposed framework, and show through
extensive experiments that these instances are competitive with
state-of-the-art methods in various tasks.
