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.
| Author(s): | Shervashidze, N. and Schweitzer, P. and van Leeuwen, EJ. and Mehlhorn, K. and Borgwardt, M. |
| Links: | |
| Journal: | Journal of Machine Learning Research |
| Volume: | 12 |
| Pages: | 2539--2561 |
| Year: | 2011 |
| Month: | September |
| Day: | 0 |
| BibTeX Type: | Article (article) |
| Digital: | 0 |
| Electronic Archiving: | grant_archive |
BibTeX
@article{ShervashidzeSvMB2011,
title = {Weisfeiler-Lehman Graph Kernels },
journal = {Journal of Machine Learning Research},
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. },
volume = {12},
pages = {2539--2561},
month = sep,
year = {2011},
author = {Shervashidze, N. and Schweitzer, P. and van Leeuwen, EJ. and Mehlhorn, K. and Borgwardt, M.},
month_numeric = {9}
}