Shervashidze, Nino; Schweitzer, Pascal; van Leeuwen, Erik Jan; Mehlhorn, Kurt; Borgwardt, Karsten M. Weisfeiler-Lehman graph kernels. (English) Zbl 1280.68194 J. Mach. Learn. Res. 12, 2539-2561 (2011). Summary: 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. Cited in 51 Documents MSC: 68T05 Learning and adaptive systems in artificial intelligence 62H30 Classification and discrimination; cluster analysis (statistical aspects) 05C90 Applications of graph theory Keywords:graph kernels PDFBibTeX XMLCite \textit{N. Shervashidze} et al., J. Mach. Learn. Res. 12, 2539--2561 (2011; Zbl 1280.68194) Full Text: Link