mlsanityData to 7 Oct 2026

RetGK: Graph Kernels based on Return Probabilities of Random Walks

arXiv 1809.02670 ↗First posted 7 Sep 2018stat.ML cs.LGcited by 32

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 7; 2023: 6; 2024: 5; 2025: 5; 2026: 2.

32 papers.

Sort:

  1. 2021Identity-aware Graph Neural Networkscited by 197
  2. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 176
  3. 2021Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernelscited by 19
  4. 2023On Structural Expressive Power of Graph Transformerscited by 19
  5. 2023Stable Vectorization of Multiparameter Persistent Homology using Signed Barcodes as Measurescited by 15
  6. 2023Facilitating Graph Neural Networks with Random Walk on Simplicial Complexescited by 14
  7. 2022Boosting Graph Structure Learning with Dummy Nodescited by 13
  8. 2023Euler Characteristic Tools For Topological Data Analysiscited by 13
  9. 2021Node Proximity Is All You Need: Unified Structural and Positional Node and Graph Embeddingcited by 9
  10. 2024Improving the Expressiveness of K-hop Message-Passing GNNs by Injecting Contextualized Substructure Informationcited by 9
  11. 2022Micro and Macro Level Graph Modeling for Graph Variational Auto-Encoderscited by 8
  12. 2023A Framework for Fast and Stable Representations of Multiparameter Persistent Homology Decompositionscited by 6
20 more
  1. 2024Descriptive Kernel Convolution Network with Improved Random Walk Kernelcited by 5
  2. 2021Fast Attributed Graph Embedding via Density of Statescited by 4
  3. 2022Supervised Contrastive Learning with Structure Inference for Graph Classificationcited by 3
  4. 2026A Closed-Form Persistence-Landmark Pipeline for Certified Point-Cloud and Graph Classificationcited by 3
  5. 2021Optimisation of Spectral Wavelets for Persistence-based Graph Classificationcited by 2
  6. 2022The PWLR Graph Representation: A Persistent Weisfeiler-Lehman scheme with Random Walks for Graph Classificationcited by 2
  7. 2026A Closed-Form Adaptive-Landmark Kernel for Certified Point-Cloud and Graph Classificationcited by 2
  8. 2021A Regularized Wasserstein Framework for Graph Kernelscited by 1
  9. 2022Multi-scale Wasserstein Shortest-path Graph Kernels for Graph Classificationcited by 1
  10. 2023Discrete transforms of quantized persistence diagramscited by 1
  11. 2024Exploring Consistency in Graph Representations:from Graph Kernels to Graph Neural Networkscited by 1
  12. 2025Graph Self-Supervised Learning with Learnable Structural and Positional Encodingscited by 1
  13. 2021Generating the Graph Gestalt: Kernel-Regularized Graph Representation Learningcited by 0
  14. 2022A Multi-scale Graph Signature for Persistence Diagrams based on Return Probabilities of Random Walkscited by 0
  15. 2024GNN-LoFI: a Novel Graph Neural Network through Localized Feature-based Histogram Intersectioncited by 0
  16. 2024Deep Hierarchical Graph Alignment Kernelscited by 0
  17. 2025LGRPool: Hierarchical Graph Pooling Via Local-Global Regularisationcited by 0
  18. 2025Disentangled Graph Representation Based on Substructure-Aware Graph Optimal Matching Kernel Convolutional Networkscited by 0
  19. 2025Simplifying Graph Kernels for Efficientcited by 0
  20. 2025Embedding networks with the random walk first return time distributioncited by 0