# Learning subtree pattern importance for Weisfeiler-Lehmanbased graph kernels

arXiv: https://arxiv.org/abs/2106.04739 · HTML: https://mlsanity.com/paper/2106.04739/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 19 references that are in the map.
- First posted on arXiv 8 Jun 2021.

## Builds on (most cited first, 3 of 3)

- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Wasserstein Weisfeiler-Lehman Graph Kernels](https://mlsanity.com/paper/1906.01277/) (2019)
- [On Valid Optimal Assignment Kernels and Applications to Graph Classification](https://mlsanity.com/paper/1606.01141/) (2016)

## Built on by (most cited first, 8 of 8)

- [On a linear fused Gromov-Wasserstein distance for graph structured data](https://mlsanity.com/paper/2203.04711/) (2022)
- [Gradual Weisfeiler-Leman: Slow and Steady Wins the Race](https://mlsanity.com/paper/2209.09048/) (2022)
- [Wasserstein Gradient Flow over Variational Parameter Space for Variational Inference](https://mlsanity.com/paper/2310.16705/) (2023)
- [Moreau-Yoshida Variational Transport: A General Framework For Solving Regularized Distributional Optimization Problems](https://mlsanity.com/paper/2307.16358/) (2023)
- [Multiple Wasserstein Gradient Descent Algorithm for Multi-Objective Distributional Optimization](https://mlsanity.com/paper/2505.18765/) (2025)
- [Metric Distribution to Vector: Constructing Data Representation via Broad-Scale Discrepancies](https://mlsanity.com/paper/2210.00415/) (2022)
- [An Evolution Kernel Method for Graph Classification through Heat Diffusion Dynamics](https://mlsanity.com/paper/2306.14688/) (2023)
- [A dictionary learning framework for graphs via filters and optimal transport](https://mlsanity.com/paper/2609.05919/) (2026)

## Abstract (arXiv)

Graph is an usual representation of relational data, which are ubiquitous in manydomains such as molecules, biological and social networks. A popular approach to learningwith graph structured data is to make use of graph kernels, which measure the similaritybetween 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 ageneral kernel is the decoupling of kernel construction and learning process. For moleculargraphs, 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 inpractice. 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 [14]. 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.