de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Weisfeiler-Lehman Graph Kernels

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons84919

Shervashidze,  N
Max Planck Institute for Biological Cybernetics, Max Planck Society;
Former Research Group Machine Learning and Computational Biology, Max Planck Institute for Biological Cybernetics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons75313

Borgwardt,  M
Max Planck Institute for Biological Cybernetics, Max Planck Society;
Former Research Group Machine Learning and Computational Biology, Max Planck Institute for Biological Cybernetics, Max Planck Society;

Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Shervashidze, N., Schweitzer, P., van Leeuwen, E., Mehlhorn, K., & Borgwardt, M. (2011). Weisfeiler-Lehman Graph Kernels. The Journal of Machine Learning Research, 12, 2539-2561.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0013-BA34-D
Abstract
In this article, we propose a family of efficient kernels for large graphs with discrete node labels. Key to our method is a rapid feature extraction scheme based on the Weisfeiler-Lehman test of isomorphism on graphs. It maps the original graph to a sequence of graphs, whose node attributes capture topological and label information. A family of kernels can be defined based on this Weisfeiler-Lehman sequence of graphs, including a highly efficient kernel comparing subtree-like patterns. Its runtime scales only linearly in the number of edges of the graphs and the length of the Weisfeiler-Lehman graph sequence. In our experimental evaluation, our kernels outperform state-of-the-art graph kernels on several graph classification benchmark data sets in terms of accuracy and runtime. Our kernels open the door to large-scale applications of graph kernels in various disciplines such as computational biology and social network analysis.