Graph kernel

{{About|machine learning|the graph-theoretical notion|Glossary of graph theory}}

In structure mining, a graph kernel is a kernel function that computes an inner product on graphs.{{cite journal|title=Graph kernels|author1=S.V. N. Vishwanathan|author2=Nicol N. Schraudolph|author3=Risi Kondor|author4=Karsten M. Borgwardt|author4-link=Karsten Borgwardt|journal=Journal of Machine Learning Research|volume=11|pages=1201–1242|year=2010|url=http://jmlr.csail.mit.edu/papers/volume11/vishwanathan10a/vishwanathan10a.pdf}}

Graph kernels can be intuitively understood as functions measuring the similarity of pairs of graphs. They allow kernelized learning algorithms such as support vector machines to work directly on graphs, without having to do feature extraction to transform them to fixed-length, real-valued feature vectors. They find applications in bioinformatics, in chemoinformatics (as a type of molecule kernels{{cite journal |author1=L. Ralaivola |author2=S. J. Swamidass |author3=H. Saigo |author4=P. Baldi |title=Graph kernels for chemical informatics |journal=Neural Networks |year=2005 |volume=18 |issue=8 |pages=1093–1110 |doi=10.1016/j.neunet.2005.07.009|pmid=16157471 }}), and in social network analysis.

Concepts of graph kernels have been around since the 1999, when D. Haussler{{Cite book|title=Convolution Kernels on Discrete Structures|last=Haussler|first=David|date=1999|citeseerx = 10.1.1.110.638}} introduced convolutional kernels on discrete structures. The term graph kernels was more officially coined in 2002 by R. I. Kondor and J. Lafferty{{cite conference

|title=Diffusion Kernels on Graphs and Other Discrete Input Spaces

|author1=Risi Imre Kondor

|author2=John Lafferty

|conference=Proc. Int'l Conf. on Machine Learning (ICML)

|year=2002

|url=http://people.cs.uchicago.edu/~risi/papers/diffusion-kernels.pdf

}}

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. In 2003, Gärtner et al.{{cite conference

|title=On graph kernels: Hardness results and efficient alternatives

|author1=Thomas Gärtner

|author2=Peter A. Flach

|author3=Stefan Wrobel

|conference=Proc. the 16th Annual Conference on Computational Learning Theory (COLT) and the 7th Kernel Workshop

|year=2003

|doi=10.1007/978-3-540-45167-9_11

}}

and Kashima et al.{{cite conference

|title=Marginalized kernels between labeled graphs

|author1=Hisashi Kashima

|author2=Koji Tsuda

|author3=Akihiro Inokuchi

|conference=Proc. the 20th International Conference on Machine Learning (ICML)

|year=2003

|url=http://www.aaai.org/Papers/ICML/2003/ICML03-044.pdf

}}

defined kernels between graphs. In 2010, Vishwanathan et al. gave their unified framework. In 2018, Ghosh et al. {{Cite journal|last=Ghosh|first=Swarnendu|last2=Das|first2=Nibaran|last3=Gonçalves|first3=Teresa|last4=Quaresma|first4=Paulo|last5=Kundu|first5=Mahantapas|title=The journey of graph kernels through two decades|journal=Computer Science Review|volume=27|pages=88–111|doi=10.1016/j.cosrev.2017.11.002|year=2018}} described the history of graph kernels and their evolution over two decades.