Graph kernel: Difference between revisions

Revision as of 18:24, 8 June 2022

Revision as of 09:20, 9 October 2023

Line 53:

An example of a kernel between graphs is the '''random walk kernel''',<ref name="Gaertner"/><ref name="Kashima"/> which conceptually performs [[random walk]]s on two graphs simultaneously, then counts the number of [[Path (graph theory)|path]]s that were produced by ''both'' walks. This is equivalent to doing random walks on the [[Tensor product of graphs|direct product]] of the pair of graphs, and from this, a kernel can be derived that can be efficiently computed.<ref name="Vishwanathan"/>

Another examples is the '''Weisfeiler-LehmanLeman graph kernel'''<ref>Shervashidze, Nino, et al. "Weisfeiler-lehman graph kernels." Journal of Machine Learning Research 12.9 (2011).</ref> which computes multiple rounds of the Weisfeiler-LehmanLeman algorithm and then computes the similarity of two graphs as the inner product of the histogram vectors of both graphs. In those histogram vectors the kernel collects the number of times a color occurs in the graph in every iteration.

Note that the Weisfeiler-LehmanLeman kernel in theory has an infinite dimension as the number of possible colors assigned by the Weisfeiler-LehmanLeman algorithm is infinite. By restricting to the colors that occur in both graphs, the computation is still feasible.

==See also==