Graph kernel: Difference between revisions

Revision as of 19:18, 22 April 2021

Revision as of 19:19, 22 April 2021

Line 54:

Another examples is the '''Weisfeiler-Lehman 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-Lehman 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. For two isomorphic graphs, the kernel returns a maximal similarity since the two feature vectors are identical.

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

==See also==