Graph kernel: Difference between revisions
Removed some dated material and trimmed sentence. |
m added some earlier work on kernels between graphs |
||
| Line 23: | Line 23: | ||
|url=http://people.cs.uchicago.edu/~risi/papers/diffusion-kernels.pdf |
|url=http://people.cs.uchicago.edu/~risi/papers/diffusion-kernels.pdf |
||
}}</ref> |
}}</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. |
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, Gaertner ''et al.''<ref>{{cite conference |
||
|title=On graph kernels: Hardness results and efficient alternatives |
|||
|author1=Thomas Gaertner |
|||
|author2=Peter Flach |
|||
|author3=Stefan Wrobel |
|||
|conference=Proc. the 16th Annual Conference on Computational Learning Theory (COLT) and the 7th Kernel Workshop |
|||
|year=2003 |
|||
|url=https://link.springer.com/chapter/10.1007/978-3-540-45167-9_11 |
|||
}}</ref> |
|||
and Kashima ''et al.''<ref>{{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|url=http://linkinghub.elsevier.com/retrieve/pii/S1574013717301429|journal=Computer Science Review|volume=27|pages=88–111|doi=10.1016/j.cosrev.2017.11.002}}</ref> described the history of graph kernels and their evolution over two decades. |
|||
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"/> |
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"/> |
||
Revision as of 02:48, 2 August 2018
In structure mining, a domain of learning on structured data objects in machine learning, a graph kernel is a kernel function that computes an inner product on graphs.[1] 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[2]), and in 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 John Lafferty[4] 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, Gaertner 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.
An example of a kernel between graphs is the random walk kernel, which conceptually performs random walks on two graphs simultaneously, then counts the number of paths that were produced by both walks. This is equivalent to doing random walks on the direct product of the pair of graphs, and from this, a kernel can be derived that can be efficiently computed.[1]
References
- ^ a b c d S.V. N. Vishwanathan; Nicol N. Schraudolph; Risi Kondor; Karsten M. Borgwardt (2010). "Graph kernels" (PDF). Journal of Machine Learning Research. 11: 1201–1242.
- ^ L. Ralaivola; S. J. Swamidass; S. Hiroto; P. Baldi (2005). "Graph kernels for chemical informatics". Neural Networks. 18: 1093–1110. doi:10.1016/j.neunet.2005.07.009.
- ^ Haussler, David (1999). Convolution Kernels on Discrete Structures.
- ^ Risi Imre Kondor; John Lafferty (2002). Diffusion Kernels on Graphs and Other Discrete Input Spaces (PDF). Proc. Int'l Conf. on Machine Learning (ICML).
- ^ Thomas Gaertner; Peter 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.
- ^ Hisashi Kashima; Koji Tsuda; Akihiro Inokuchi (2003). Marginalized kernels between labeled graphs (PDF). Proc. the 20th International Conference on Machine Learning (ICML).
- ^ Ghosh, Swarnendu; Das, Nibaran; Gonçalves, Teresa; Quaresma, Paulo; Kundu, Mahantapas. "The journey of graph kernels through two decades". Computer Science Review. 27: 88–111. doi:10.1016/j.cosrev.2017.11.002.
See also
- Tree kernel, as special case of non-cyclic graphs
- Molecule mining, as special case of small multi-label graphs
 | This computer science article is a stub. You can help Wikipedia by expanding it. |