# Graph kernel

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Graph_kernel
> Markdown URL: https://mediated.wiki/source/Graph_kernel.md
> Source: https://en.wikipedia.org/wiki/Graph_kernel
> Source revision: 1303510078
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

This article is about machine learning. For the graph-theoretical notion, see [Glossary of graph theory](/source/Glossary_of_graph_theory).

In [structure mining](/source/Structure_mining), a **graph kernel** is a [kernel function](/source/Positive-definite_kernel) that computes an [inner product](/source/Inner_product_space) on [graphs](/source/Graph_(abstract_data_type)).[1] Graph kernels can be intuitively understood as functions measuring the similarity of pairs of graphs. They allow [kernelized](/source/Kernel_trick) learning algorithms such as [support vector machines](/source/Support_vector_machine) to work directly on graphs, without having to do [feature extraction](/source/Feature_extraction) to transform them to fixed-length, real-valued [feature vectors](/source/Feature_vector). They find applications in [bioinformatics](/source/Bioinformatics), in [chemoinformatics](/source/Chemoinformatics) (as a type of [molecule kernels](/source/Molecule_kernel)[2]), and in [social network analysis](/source/Social_network_analysis).[1]

Concepts of graph kernels have been around since the 1999, when D. Haussler[3] introduced convolutional kernels on discrete structures. The term graph kernels was more officially coined in 2002 by R. I. Kondor and [J. Lafferty](/source/John_D._Lafferty)[4] as kernels *on* graphs, i.e. similarity functions between the nodes of a single graph, with the [World Wide Web](/source/World_Wide_Web) [hyperlink](/source/Hyperlink) graph as a suggested application. In 2003, Gärtner *et al.*[5] and Kashima *et al.*[6] defined kernels *between* graphs. In 2010, Vishwanathan *et al.* gave their unified framework.[1] In 2018, Ghosh et al. [7] described the history of graph kernels and their evolution over two decades.

## Applications

The marginalized graph kernel has been shown to allow accurate predictions of the atomization energy of small organic molecules.[8]

## Example Kernels

An example of a kernel between graphs is the **random walk kernel**,[5][6] which conceptually performs [random walks](/source/Random_walk) on two graphs simultaneously, then counts the number of [paths](/source/Path_(graph_theory)) that were produced by *both* walks. This is equivalent to doing random walks on the [direct product](/source/Tensor_product_of_graphs) of the pair of graphs, and from this, a kernel can be derived that can be efficiently computed.[1]

Another examples is the **Weisfeiler-Leman graph kernel**[9] which computes multiple rounds of the [Weisfeiler-Leman algorithm](/source/Weisfeiler-Leman_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-Leman kernel in theory has an infinite dimension as the number of possible colors assigned by the Weisfeiler-Leman algorithm is infinite. By restricting to the colors that occur in both graphs, the computation is still feasible.

## See also

- [Tree kernel](/source/Tree_kernel), as special case of non-cyclic graphs

- [Molecule mining](/source/Molecule_mining), as special case of small multi-label graphs

## References

1. ^ [***a***](#cite_ref-Vishwanathan_1-0) [***b***](#cite_ref-Vishwanathan_1-1) [***c***](#cite_ref-Vishwanathan_1-2) [***d***](#cite_ref-Vishwanathan_1-3) S.V. N. Vishwanathan; Nicol N. Schraudolph; Risi Kondor; [Karsten M. Borgwardt](/source/Karsten_Borgwardt) (2010). ["Graph kernels"](http://jmlr.csail.mit.edu/papers/volume11/vishwanathan10a/vishwanathan10a.pdf) (PDF). *[Journal of Machine Learning Research](/source/Journal_of_Machine_Learning_Research)*. **11**: 1201–1242.

1. **[^](#cite_ref-Ralaivola2005_2-0)** L. Ralaivola; S. J. Swamidass; H. Saigo; P. Baldi (2005). "Graph kernels for chemical informatics". *Neural Networks*. **18** (8): 1093–1110. [doi](/source/Doi_(identifier)):[10.1016/j.neunet.2005.07.009](https://doi.org/10.1016%2Fj.neunet.2005.07.009). [PMID](/source/PMID_(identifier)) [16157471](https://pubmed.ncbi.nlm.nih.gov/16157471).

1. **[^](#cite_ref-3)** Haussler, David (1999). *Convolution Kernels on Discrete Structures*. [CiteSeerX](/source/CiteSeerX_(identifier)) [10.1.1.110.638](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.110.638).

1. **[^](#cite_ref-4)** Risi Imre Kondor; John Lafferty (2002). [*Diffusion Kernels on Graphs and Other Discrete Input Spaces*](http://people.cs.uchicago.edu/~risi/papers/diffusion-kernels.pdf) (PDF). Proc. Int'l Conf. on Machine Learning (ICML).

1. ^ [***a***](#cite_ref-Gaertner_5-0) [***b***](#cite_ref-Gaertner_5-1) Thomas Gärtner; Peter A. Flach; Stefan Wrobel (2003). *On graph kernels: Hardness results and efficient alternatives*. Proc. the 16th Annual Conference on Computational Learning Theory (COLT) and the 7th Kernel Workshop. [doi](/source/Doi_(identifier)):[10.1007/978-3-540-45167-9_11](https://doi.org/10.1007%2F978-3-540-45167-9_11).

1. ^ [***a***](#cite_ref-Kashima_6-0) [***b***](#cite_ref-Kashima_6-1) Hisashi Kashima; Koji Tsuda; Akihiro Inokuchi (2003). [*Marginalized kernels between labeled graphs*](http://www.aaai.org/Papers/ICML/2003/ICML03-044.pdf) (PDF). Proc. the 20th International Conference on Machine Learning (ICML).

1. **[^](#cite_ref-7)** Ghosh, Swarnendu; Das, Nibaran; Gonçalves, Teresa; Quaresma, Paulo; Kundu, Mahantapas (2018). "The journey of graph kernels through two decades". *Computer Science Review*. **27**: 88–111. [doi](/source/Doi_(identifier)):[10.1016/j.cosrev.2017.11.002](https://doi.org/10.1016%2Fj.cosrev.2017.11.002).

1. **[^](#cite_ref-8)** Yu-Hang Tang; Wibe A. de Jong (2019). "Prediction of atomization energy using graph kernel and active learning". *The Journal of Chemical Physics*. **150** (4): 044107. [arXiv](/source/ArXiv_(identifier)):[1810.07310](https://arxiv.org/abs/1810.07310). [Bibcode](/source/Bibcode_(identifier)):[2019JChPh.150d4107T](https://ui.adsabs.harvard.edu/abs/2019JChPh.150d4107T). [doi](/source/Doi_(identifier)):[10.1063/1.5078640](https://doi.org/10.1063%2F1.5078640). [PMID](/source/PMID_(identifier)) [30709286](https://pubmed.ncbi.nlm.nih.gov/30709286).

1. **[^](#cite_ref-9)** Shervashidze, Nino, et al. "Weisfeiler-lehman graph kernels." Journal of Machine Learning Research 12.9 (2011).

This machine learning–related article is a stub. You can help Wikipedia by adding missing information.

- [v](https://en.wikipedia.org/wiki/Template:Machine-learning-stub)
- [t](/source/Template_talk%3AMachine-learning-stub)
- [e](https://en.wikipedia.org/wiki/Special:EditPage/Template:Machine-learning-stub)

---
Adapted from the Wikipedia article [Graph kernel](https://en.wikipedia.org/wiki/Graph_kernel) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Graph_kernel?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.