Graph kernel: Difference between revisions

Revision as of 23:40, 6 February 2014

Revision as of 07:59, 13 April 2014

Line 25:

as kernels ''on'' graphs, i.e. similarity functions between the nodes of a single graph, with the [[World Wide Web]] [[hyperlink]] graph as a suggested application. Vishwanathan ''et al.'' instead defined kernels ''between'' graphs.<ref name="Vishwanathan"/>

An example of a kernel between graphs is the '''random walk kernel''', 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 -- i.e. the number of path pairs that are similar with the paths in the pair coming from the two different graphs. 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"/>

==References==