# Generalizing Weisfeiler-Lehman Kernels to Subgraphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 38 references that are in the map.
- First posted on arXiv 3 Dec 2024.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness](https://mlsanity.com/paper/2110.03753/) (2021)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [Wasserstein Weisfeiler-Lehman Graph Kernels](https://mlsanity.com/paper/1906.01277/) (2019)
- [Subgraph Neural Networks](https://mlsanity.com/paper/2006.10538/) (2020)
- [Question Answering with Subgraph Embeddings](https://mlsanity.com/paper/1406.3676/) (2014)
- [subgraph2vec: Learning Distributed Representations of Rooted Sub-graphs from Large Graphs](https://mlsanity.com/paper/1606.08928/) (2016)
- [SHINE: SubHypergraph Inductive Neural nEtwork](https://mlsanity.com/paper/2210.07309/) (2022)
- [Translating Subgraphs to Nodes Makes Simple GNNs Strong and Efficient for Subgraph Representation Learning](https://mlsanity.com/paper/2204.04510/) (2022)
- [Position-Aware Subgraph Neural Networks with Data-Efficient Learning](https://mlsanity.com/paper/2211.00572/) (2022)
- [Stochastic Subgraph Neighborhood Pooling for Subgraph Classification](https://mlsanity.com/paper/2304.08556/) (2023)
- [Models and Benchmarks for Representation Learning of Partially Observed Subgraphs](https://mlsanity.com/paper/2209.00508/) (2022)
- [TimeGraphs: Graph-based Temporal Reasoning](https://mlsanity.com/paper/2401.03134/) (2024)

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

- [SlepNet: Spectral Subgraph Representation Learning for Neural Dynamics](https://mlsanity.com/paper/2506.16602/) (2025)

## Abstract (arXiv)

Subgraph representation learning has been effective in solving various real-world problems. However, current graph neural networks (GNNs) produce suboptimal results for subgraph-level tasks due to their inability to capture complex interactions within and between subgraphs. To provide a more expressive and efficient alternative, we propose WLKS, a Weisfeiler-Lehman (WL) kernel generalized for subgraphs by applying the WL algorithm on induced k-hop neighborhoods. We combine kernels across different k-hop levels to capture richer structural information that is not fully encoded in existing models. Our approach can balance expressiveness and efficiency by eliminating the need for neighborhood sampling. In experiments on eight real-world and synthetic benchmarks, WLKS significantly outperforms leading approaches on five datasets while reducing training time, ranging from 0.01x to 0.25x compared to the state-of-the-art.