Graph-structured data arise in wide applications, such as computer vision, bioinformatics,
and social networks. Quantifying similarities among graphs is a fundamental problem. In this
paper, we develop a framework for computing graph kernels, based on return probabilities
of random walks. The advantages of our proposed kernels are that they can effectively
exploit various node attributes, while being scalable to large datasets. We conduct extensive
graph classification experiments to evaluate our graph kernels. The experimental results …

… For a connected graph G, the random walk defined on it can be considered as a irreducible
Markov chain. We define a probability vector π as πi = … Since the sum and multiplication of
positive definite kernels are still positive definite, we conclude that (16a) are positive definite. …