Learning subtree pattern importance for Weisfeiler-Lehman based graph kernels

Dai Hai Nguyen*, Canh Hao Nguyen, Hiroshi Mamitsuka

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

5 Citations (Scopus)
15 Downloads (Pure)


Graph is an usual representation of relational data, which are ubiquitous in many domains such as molecules, biological and social networks. A popular approach to learning with graph structured data is to make use of graph kernels, which measure the similarity between graphs and are plugged into a kernel machine such as a support vector machine. Weisfeiler-Lehman (WL) based graph kernels, which employ WL labeling scheme to extract subtree patterns and perform node embedding, are demonstrated to achieve great performance while being efficiently computable. However, one of the main drawbacks of a general kernel is the decoupling of kernel construction and learning process. For molecular graphs, usual kernels such as WL subtree, based on substructures of the molecules, consider all available substructures having the same importance, which might not be suitable in practice. In this paper, we propose a method to learn the weights of subtree patterns in the framework of WWL kernels, the state of the art method for graph classification task (Togninalli et al., in: Advances in Neural Information Processing Systems, pp. 6439–6449, 2019). To overcome the computational issue on large scale data sets, we present an efficient learning algorithm and also derive a generalization gap bound to show its convergence. Finally, through experiments on synthetic and real-world data sets, we demonstrate the effectiveness of our proposed method for learning the weights of subtree patterns.

Original languageEnglish
Pages (from-to)1585-1607
Number of pages23
JournalMachine Learning
Issue number7
Early online date13 Jun 2021
Publication statusPublished - Jul 2021
MoE publication typeA1 Journal article-refereed


  • Graph kernel
  • Optimal transport
  • Weisfeiler Lehman scheme


Dive into the research topics of 'Learning subtree pattern importance for Weisfeiler-Lehman based graph kernels'. Together they form a unique fingerprint.

Cite this