Graph kernel: Difference between revisions

Revision as of 20:22, 21 November 2020

Revision as of 21:23, 21 November 2020

Line 1:

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

In [[structure mining]], a ___domain of learning on structured data objects in [[machine learning]], a '''graph kernel''' is a [[Positive-definite kernel|kernel function]] that computes an [[inner product space|inner product]] on [[Graph (abstract data type)|graphs]].<ref name="Vishwanathan">{{cite journal|title=Graph kernels|author1=S.V. N. Vishwanathan|author2=Nicol N. Schraudolph|author3=Risi Kondor|author4=Karsten M. 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}}</ref>

|title=Graph kernels

|author1=S.V. N. Vishwanathan

|author2=Nicol N. Schraudolph

|author3=Risi Kondor

|author4=Karsten M. 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

}}</ref>

Graph kernels can be intuitively understood as functions measuring the similarity of pairs of graphs. They allow [[Kernel trick|kernelized]] learning algorithms such as [[support vector machine]]s to work directly on graphs, without having to do [[feature extraction]] to transform them to fixed-length, real-valued [[feature vector]]s. They find applications in [[bioinformatics]], in [[chemoinformatics]] (as a type of [[molecule kernel]]s<ref name="Ralaivola2005">{{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 }}</ref>), and in [[social network analysis]].<ref name="Vishwanathan"/>