Statistical and Machine Learning Approaches for Network Analysis

8.3 Random Walk Graph Kernels

The idea of random walk graph kernels is to perform random walks on two graphs and compare the resulting label sequences. They can be seen as kernels on label sequences marginalized with respect to these random walks, and thus are also called marginalized graph kernels. Specific kernels differ in their random walk model and the kernels used to compare vertex and edge labels. Random walk kernels include label sequence kernels [58,28], marginalized graph kernels [27], and geometric graph kernels [65].

8.3.1 Definition

A random walk on a graph G (Fig. 8.2) starts in vertex x₁ V with probability p_s, goes from x_i−1 to x_i with transitional probability p_t conditional on x_i−1, and ends with probability p_q. A random walk instance x = x₁ x_l has probability

(8.6)

Default choices are , for a small constant 0 < c ≤ 1, and, , where is the degree of . The random walk x