Content deleted Content added
Citation bot (talk | contribs) m Add: year, citeseerx, pmid, issue. Removed parameters. You can use this bot yourself. Report bugs here. | User-activated. |
Citation bot (talk | contribs) m Removed parameters. | You can use this bot yourself. Report bugs here. | User-activated. |
||
Line 13:
|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
Concepts of graph kernels have been around since the 1999, when D. Haussler<ref>{{Cite book|title=Convolution Kernels on Discrete Structures|last=Haussler|first=David|date=1999|citeseerx = 10.1.1.110.638}}</ref> introduced convolutional kernels on discrete structures. The term graph kernels was more officially coined in 2002 by R. I. Kondor and John Lafferty<ref>{{cite conference
Line 41:
|url=http://www.aaai.org/Papers/ICML/2003/ICML03-044.pdf
}}</ref>
defined kernels ''between'' graphs. In 2010, Vishwanathan ''et al.'' gave their unified framework.<ref name="Vishwanathan"/> In 2018, Ghosh et al. <ref>{{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
An example of a kernel between graphs is the '''random walk kernel'''<ref name="Gaertner"/><ref name="Kashima"/>, 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. 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"/>
| |||