# RetGK: Graph Kernels based on Return Probabilities of Random Walks

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Sep 2018.

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

- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels](https://mlsanity.com/paper/2104.02995/) (2021)
- [On Structural Expressive Power of Graph Transformers](https://mlsanity.com/paper/2305.13987/) (2023)
- [Stable Vectorization of Multiparameter Persistent Homology using Signed Barcodes as Measures](https://mlsanity.com/paper/2306.03801/) (2023)
- [Facilitating Graph Neural Networks with Random Walk on Simplicial Complexes](https://mlsanity.com/paper/2310.19285/) (2023)
- [Boosting Graph Structure Learning with Dummy Nodes](https://mlsanity.com/paper/2206.08561/) (2022)
- [Euler Characteristic Tools For Topological Data Analysis](https://mlsanity.com/paper/2303.14040/) (2023)
- [Node Proximity Is All You Need: Unified Structural and Positional Node and Graph Embedding](https://mlsanity.com/paper/2102.13582/) (2021)
- [Improving the Expressiveness of K-hop Message-Passing GNNs by Injecting Contextualized Substructure Information](https://mlsanity.com/paper/2406.19244/) (2024)
- [Micro and Macro Level Graph Modeling for Graph Variational Auto-Encoders](https://mlsanity.com/paper/2210.16844/) (2022)
- [A Framework for Fast and Stable Representations of Multiparameter Persistent Homology Decompositions](https://mlsanity.com/paper/2306.11170/) (2023)
- [Descriptive Kernel Convolution Network with Improved Random Walk Kernel](https://mlsanity.com/paper/2402.06087/) (2024)
- [Fast Attributed Graph Embedding via Density of States](https://mlsanity.com/paper/2110.05228/) (2021)
- [A Closed-Form Persistence-Landmark Pipeline for Certified Point-Cloud and Graph Classification](https://mlsanity.com/paper/2605.02836/) (2026)
- [Supervised Contrastive Learning with Structure Inference for Graph Classification](https://mlsanity.com/paper/2203.07691/) (2022)
- [A Closed-Form Adaptive-Landmark Kernel for Certified Point-Cloud and Graph Classification](https://mlsanity.com/paper/2605.04046/) (2026)
- [Optimisation of Spectral Wavelets for Persistence-based Graph Classification](https://mlsanity.com/paper/2101.05201/) (2021)
- [The PWLR Graph Representation: A Persistent Weisfeiler-Lehman scheme with Random Walks for Graph Classification](https://mlsanity.com/paper/2208.13427/) (2022)
- [A Regularized Wasserstein Framework for Graph Kernels](https://mlsanity.com/paper/2110.02554/) (2021)
- [Multi-scale Wasserstein Shortest-path Graph Kernels for Graph Classification](https://mlsanity.com/paper/2206.00979/) (2022)
- [Discrete transforms of quantized persistence diagrams](https://mlsanity.com/paper/2312.17093/) (2023)
- [Exploring Consistency in Graph Representations:from Graph Kernels to Graph Neural Networks](https://mlsanity.com/paper/2410.23748/) (2024)
- [Graph Self-Supervised Learning with Learnable Structural and Positional Encodings](https://mlsanity.com/paper/2502.16233/) (2025)
- [Generating the Graph Gestalt: Kernel-Regularized Graph Representation Learning](https://mlsanity.com/paper/2106.15239/) (2021)
- [A Multi-scale Graph Signature for Persistence Diagrams based on Return Probabilities of Random Walks](https://mlsanity.com/paper/2209.14264/) (2022)
- [GNN-LoFI: a Novel Graph Neural Network through Localized Feature-based Histogram Intersection](https://mlsanity.com/paper/2401.09193/) (2024)
- [Deep Hierarchical Graph Alignment Kernels](https://mlsanity.com/paper/2405.05545/) (2024)
- [LGRPool: Hierarchical Graph Pooling Via Local-Global Regularisation](https://mlsanity.com/paper/2504.08530/) (2025)
- [Disentangled Graph Representation Based on Substructure-Aware Graph Optimal Matching Kernel Convolutional Networks](https://mlsanity.com/paper/2504.16360/) (2025)

## Abstract (arXiv)

Graph-structured data arise in wide applications, such as computer vision, bioinformatics, and social networks. Quantifying similarities among graphs is a fundamental problem. In this paper, we develop a framework for computing graph kernels, based on return probabilities of random walks. The advantages of our proposed kernels are that they can effectively exploit various node attributes, while being scalable to large datasets. We conduct extensive graph classification experiments to evaluate our graph kernels. The experimental results show that our graph kernels significantly outperform existing state-of-the-art approaches in both accuracy and computational efficiency.