Content deleted Content added
Gklambauer (talk | contribs) m Added reference; |
m →Example Kernels: internal link |
||
| (36 intermediate revisions by 22 users not shown) | |||
Line 1:
{{About|machine learning|the graph-theoretical notion|Glossary of graph theory}}
In [[
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 |
|author2=Nicol N. Schraudolph▼
|author3=Risi Kondor▼
|journal=[[Journal of Machine Learning Research]]▼
|volume=11▼
|year=2010▼
}}</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]], as [[molecule kernel]]s<ref name="Ralaivola2005">{{cite journal | author =L. Ralaivola, S. J. Swamidass, S. Hiroto and P. Baldi| title =Graph kernels for chemical informatics | journal = Neural Networks | year = 2005 | volume = 18 | pages = 1093-1110 | url = http://www.sciencedirect.com/science/article/pii/S0893608005001693}}</ref> in [[chemoinformatics]] , and in [[social network analysis]].<ref name="Vishwanathan"/>
|title=Diffusion Kernels on Graphs and Other Discrete Input Spaces
|author1=Risi Imre Kondor
Line 23 ⟶ 12:
|url=http://people.cs.uchicago.edu/~risi/papers/diffusion-kernels.pdf
}}</ref>
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.
|title=On graph kernels: Hardness results and efficient alternatives
|author1=Thomas Gärtner
|conference=Proc. the 16th Annual Conference on Computational Learning Theory (COLT) and the 7th Kernel Workshop
|doi=10.1007/978-3-540-45167-9_11
and Kashima ''et al.''<ref name="Kashima">{{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
}}</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|journal=Computer Science Review|volume=27|pages=88–111|doi=10.1016/j.cosrev.2017.11.002|year=2018}}</ref> described the history of graph kernels and their evolution over two decades.
==Applications==
An example of a kernel between graphs is the '''random walk kernel''', 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"/>▼
The marginalized graph kernel has been shown to allow accurate predictions of the atomization energy of small organic molecules.<ref>{{cite journal
|title=Prediction of atomization energy using graph kernel and active learning
|author1=Yu-Hang Tang
|author2=Wibe A. de Jong
|issue=4
|pages=044107
|year=2019
|doi=10.1063/1.5078640
|pmid=30709286
|arxiv=1810.07310
|bibcode=2019JChPh.150d4107T
}}</ref>
==Example Kernels==
▲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"/>
Another examples is the '''Weisfeiler-Leman 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-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]], as special case of non-cyclic graphs
* [[Molecule mining]], as special case of small multi-label graphs
==References==
Line 33 ⟶ 66:
[[Category:Kernel methods for machine learning]]
{{machine-learning-stub}}
| |||