Foundations and Trends® in Machine Learning > Vol 13 > Issue 5-6

Graph Kernels: State-of-the-Art and Future Challenges

Karsten Borgwardt, ETH Zurich and Swiss Institute of Bioinformatics, Switzerland, karsten.borgwardt@bsse.ethz.ch Elisabetta Ghisu, ETH Zurich and Swiss Institute of Bioinformatics, Switzerland, elisabetta.ghisu@bsse.ethz.ch Felipe Llinares-López, ETH Zurich and Swiss Institute of Bioinformatics, Switzerland, felipe.llinares@bsse.ethz.ch Leslie O’Bray, ETH Zurich and Swiss Institute of Bioinformatics, Switzerland, leslie.obray@bsse.ethz.ch Bastian Rieck, ETH Zurich and Swiss Institute of Bioinformatics, Switzerland, bastian.rieck@bsse.ethz.ch
 
Suggested Citation
Karsten Borgwardt, Elisabetta Ghisu, Felipe Llinares-López, Leslie O’Bray and Bastian Rieck (2020), "Graph Kernels: State-of-the-Art and Future Challenges", Foundations and Trends® in Machine Learning: Vol. 13: No. 5-6, pp 531-712. http://dx.doi.org/10.1561/2200000076

Publication Date: 23 Dec 2020
© 2020 Karsten Borgwardt, Elisabetta Ghisu, Felipe Llinares-López, Leslie O’Bray and Bastian Rieck
 
Subjects
Kernel methods,  Classification and prediction,  Modeling and Analysis
 

Free Preview:

Download extract

Share

Download article
In this article:
1. Introduction
2. Background on graph comparison and kernel methods
3. Kernels for graph-structured data
4. Experimental evaluation of graph kernels
5. Discussion & future directions
6. Accompanying website
Glossary
References

Abstract

Graph-structured data are an integral part of many application domains, including chemoinformatics, computational biology, neuroimaging, and social network analysis. Over the last two decades, numerous graph kernels, i.e. kernel functions between graphs, have been proposed to solve the problem of assessing the similarity between graphs, thereby making it possible to perform predictions in both classification and regression settings. This manuscript provides a review of existing graph kernels, their applications, software plus data resources, and an empirical comparison of state-of-the-art graph kernels.

DOI:10.1561/2200000076
ISBN: 978-1-68083-770-4
196 pp. $99.00
Buy book (pb)
 
ISBN: 978-1-68083-771-1
196 pp. $280.00
Buy E-book (.pdf)
Table of contents:
1. Introduction
2. Background on graph comparison and kernel methods
3. Kernels for graph-structured data
4. Experimental evaluation of graph kernels
5. Discussion & future directions
6. Accompanying website
Glossary
References

Graph Kernels: State-of-the-Art and Future Challenges

Among the data structures commonly used in machine learning, graphs are arguably one of the most general. Graphs allow the modelling of complex objects, each of which can be annotated by metadata. Nonetheless, seemingly simple questions, such as determining whether two graphs are identical or whether one graph is contained in another graph, are remarkably hard to solve in practice. Machine learning methods operating on graphs must therefore grapple with the need to balance computational tractability with the ability to leverage as much of the information conveyed by each graph as possible. In the last 15 years, numerous graph kernels have been proposed to solve this problem, thereby making it possible to perform predictions in both classification and regression settings.

This monograph provides a review of existing graph kernels, their applications, software plus data resources, and an empirical comparison of state-of-the-art graph kernels. It is divided into two parts: the first part focuses on the theoretical description of common graph kernels; the second part focuses on a large-scale empirical evaluation of graph kernels, as well as a description of desirable properties and requirements for benchmark data sets. Finally, the authors outline the future trends and open challenges for graph kernels.

Written for every researcher, practitioner and student of machine learning, Graph Kernels provides a comprehensive and insightful survey of the various graph kernals available today. It gives the reader a detailed typology, and analysis of relevant graph kernels while exposing the relations between them and commenting on their applicability for specific data types. There is also a large-scale empirical evaluation of graph kernels.

 
MAL-076