Random Walk Kernel

The most well-studied family of graph kernels is probably the random walk kernels which quantify the similarity between a pair of graphs based on the number of common walks in the two graphs [KTI03], [GartnerFW03], [MaheUA+04], [BOSchonauer+05], [VSKB10], [SB15].

Kernels belonging to this family have concentrated mainly on counting matching walks in the two input graphs. There are several variations of random walk kernels. The \(k\)-step random walk kernel compares random walks up to length \(k\) in the two graphs. The most widely-used kernel from this family is the geometric random walk kernel [GartnerFW03] which compares walks up to infinity assigning a weight \(\lambda^k\) (\(\lambda < 1\)) to walks of length \(k\) in order to ensure convergence of the corresponding geometric series. We next give the formal definition of the geometric random walk kernel. Given two node-labeled graphs \(G_i=(V_i,E_i)\) and \(G_j=(V_j,E_j)\), their direct product \(G_\times=(V_\times,E_\times)\) is a graph with vertex set:

\begin{equation} V_{\times} = \{(v_i,v_j) : v_i \in V_i \wedge v_j \in V_j \wedge \ell(v_i) = \ell(v_j) \} \end{equation}

and edge set:

\begin{equation} E_{\times} = \{\{(v_i,v_j),(u_i,u_j)\} : \{v_i,u_i\} \in E_i \wedge \{v_j,u_j\} \in E_j\} \end{equation}

Performing a random walk on \(G_{\times}\) is equivalent to performing a simultaneous random walk on \(G_i\) and \(G_j\). The geometric random walk kernel counts common walks (of potentially infinite length) in two graphs and is defined as follows.

Definition: Geometric Random Walk Kernel

Let \(G_i\) and \(G_j\) be two graphs, let \(A_\times\) denote the adjacency matrix of their product graph \(G_\times\), and let \(V_\times\) denote the vertex set of the product graph \(G_\times\).

Then, the geometric random walk kernel is defined as

\begin{equation} K_{\times}^{\infty}(G_i,G_j) = \sum_{p,q=1}^{|V_{\times}|} \Big[ \sum_{l=0}^{\infty} \lambda^l A_{\times}^l \Big]_{pq} = e^T(I - \lambda A_{\times})^{-1} e \end{equation}

where \(I\) is the identity matrix, \(e\) is the all-ones vector, and \(\lambda\) is a positive, real-valued weight. The geometric random walk kernel converges only if \(\lambda < \frac{1}{\lambda_\times}\) where \(\lambda_\times\) is the largest eigenvalue of \(A_{\times}\).

Direct computation of the geometric random walk kernel requires \(\mathcal{O}(n^6)\) time. The computational complexity of the method severely limits its applicability to real-world applications. To account for this, Vishwanathan et al. proposed in [VSKB10] four efficient methods to compute random walk graph kernels which generally reduce the computational complexity from \(\mathcal{O}(n^6)\) to \(\mathcal{O}(n^3)\). Mahé et al. proposed in [MaheUA+04] some other extensions of random walk kernels. Specifically, they proposed a label enrichment approach which increases specificity and in most cases also reduces computational complexity. They also employed a second order Markov random walk to deal with the problem of “tottering”. Sugiyama and Borgwardt focused in [SB15] on a different problem of random walk kernels, a phenomenon referred to as “halting”.

Next follow two implementations of this kernel (one for unlabeled graphs and one for graphs with discrete node labels)

RandomWalk([n_jobs, normalize, verbose, ...])	The random walk kernel class.
RandomWalkLabeled([n_jobs, normalize, ...])	The labeled random walk kernel class.

Bibliography

[BOSchonauer+05]

Karsten M. Borgwardt, Cheng Soon Ong, Stefan Schönauer, S.V.N. Vishwanathan, Alex J. Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(suppl 1):i47–i56, 2005.

[GartnerFW03] (1,2)

Thomas Gärtner, Peter Flach, and Stefan Wrobel. On Graph Kernels: Hardness Results and Efficient Alternatives. In Learning Theory and Kernel Machines, 129–143. 2003.

[KTI03]

Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. Marginalized Kernels Between Labeled Graphs. In Proceedings of the 20th Conference in Machine Learning, 321–328. 2003.

[MaheUA+04] (1,2)

Pierre Mahé, Nobuhisa Ueda, Tatsuya Akutsu, Jean-Luc Perret, and Jean-Philippe Vert. Extensions of marginalized graph kernels. In Proceedings of the 21st International Conference on Machine Learning, 70. 2004.

[SB15] (1,2)

Mahito Sugiyama and Karsten M. Borgwardt. Halting in Random Walk Kernels. In Advances in Neural Information Processing Systems, 1639–1647. 2015.

[VSKB10] (1,2)

S.V.N. Vishwanathan, Nicol N. Schraudolph, Risi Kondor, and Karsten M. Borgwardt. Graph Kernels. The Journal of Machine Learning Research, 11:1201–1242, 2010.