# The Multiscale Laplacian Graph Kernel

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Mar 2016.

## Built on by (most cited first, 30 of 31)

- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [InfoGCL: Information-Aware Graph Contrastive Learning](https://mlsanity.com/paper/2110.15438/) (2021)
- [Prototypical Graph Contrastive Learning](https://mlsanity.com/paper/2106.09645/) (2021)
- [SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks](https://mlsanity.com/paper/2203.13913/) (2022)
- [GraphHD: Efficient graph classification using hyperdimensional computing](https://mlsanity.com/paper/2205.07826/) (2022)
- [Learning Graph Augmentations to Learn Graph Representations](https://mlsanity.com/paper/2201.09830/) (2022)
- [Learning Disentangled Textual Representations via Statistical Measures of Similarity](https://mlsanity.com/paper/2205.03589/) (2022)
- [The GeometricKernels Package: Heat and Mat'ern Kernels for Geometric Learning on Manifolds, Meshes, and Graphs](https://mlsanity.com/paper/2407.08086/) (2024)
- [Label Contrastive Coding based Graph Neural Network for Graph Classification](https://mlsanity.com/paper/2101.05486/) (2021)
- [Graphon based Clustering and Testing of Networks: Algorithms and Theory](https://mlsanity.com/paper/2110.02722/) (2021)
- [Learning Graph Representation by Aggregating Subgraphs via Mutual Information Maximization](https://mlsanity.com/paper/2103.13125/) (2021)
- [Learning Graphon Autoencoders for Generative Graph Modeling](https://mlsanity.com/paper/2105.14244/) (2021)
- [Computing Graph Descriptors on Edge Streams](https://mlsanity.com/paper/2109.01494/) (2021)
- [Graph Classification Gaussian Processes via Spectral Features](https://mlsanity.com/paper/2306.03770/) (2023)
- [EMP: Effective Multidimensional Persistence for Graph Representation Learning](https://mlsanity.com/paper/2401.13713/) (2024)
- [Improving Graph Machine Learning Performance Through Feature Augmentation Based on Network Control Theory](https://mlsanity.com/paper/2405.03706/) (2024)
- [Self-Supervised Graph Representation Learning via Topology Transformations](https://mlsanity.com/paper/2105.11689/) (2021)
- [Deep Graph-Level Clustering Using Pseudo-Label-Guided Mutual Information Maximization Network](https://mlsanity.com/paper/2302.02369/) (2023)
- [DisenSemi: Semi-supervised Graph Classification via Disentangled Representation Learning](https://mlsanity.com/paper/2407.14081/) (2024)
- [Minimax Lower Bounds of Kernel Discrepancy Estimation: MMD, HSIC, KSD](https://mlsanity.com/paper/2607.24235/) (2026)
- [Revisiting 2D Convolutional Neural Networks for Graph-based Applications](https://mlsanity.com/paper/2105.11016/) (2021)
- [Multi-scale Wasserstein Shortest-path Graph Kernels for Graph Classification](https://mlsanity.com/paper/2206.00979/) (2022)
- [Learning Attributed Graphlets: Predictive Graph Mining by Graphlets with Trainable Attribute](https://mlsanity.com/paper/2402.06932/) (2024)
- [A Temporal Graphlet Kernel for Classifying Dissemination in Evolving Networks](https://mlsanity.com/paper/2209.07332/) (2022)
- [HCL: Improving Graph Representation with Hierarchical Contrastive Learning](https://mlsanity.com/paper/2210.12020/) (2022)
- [Randomized Schur Complement Views for Graph Contrastive Learning](https://mlsanity.com/paper/2306.04004/) (2023)
- [Graph-level Protein Representation Learning by Structure Knowledge Refinement](https://mlsanity.com/paper/2401.02713/) (2024)
- [SPGNN: Recognizing Salient Subgraph Patterns via Enhanced Graph Convolution and Pooling](https://mlsanity.com/paper/2404.13655/) (2024)
- [Feature Construction Using Network Control Theory and Rank Encoding for Graph Machine Learning](https://mlsanity.com/paper/2507.15195/) (2025)
- [Explainable Graph Representation Learning via Graph Pattern Analysis](https://mlsanity.com/paper/2512.04530/) (2025)

## Abstract (arXiv)

Many real world graphs, such as the graphs of molecules, exhibit structure at multiple different scales, but most existing kernels between graphs are either purely local or purely global in character. In contrast, by building a hierarchy of nested subgraphs, the Multiscale Laplacian Graph kernels (MLG kernels) that we define in this paper can account for structure at a range of different scales. At the heart of the MLG construction is another new graph kernel, called the Feature Space Laplacian Graph kernel (FLG kernel), which has the property that it can lift a base kernel defined on the vertices of two graphs to a kernel between the graphs. The MLG kernel applies such FLG kernels to subgraphs recursively. To make the MLG kernel computationally feasible, we also introduce a randomized projection procedure, similar to the Nystr"om method, but for RKHS operators.