Research map / Graph learning / Graph algorithms and clustering
RetGK: Graph Kernels based on Return Probabilities of Random Walks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use return-probability node features with RetGK_I rather than WL | Graph classification · COLLAB | accuracy: 74.8(0.2) -> 81.0(0.3) | Helped |
| Use approximate tensor embeddings (RetGK_II) rather than the Hilbert-space kernel (RetGK_I) (ablation) | RetGK · COLLAB | accuracy: 81.0(0.3) -> 80.6(0.3) | No clear effect |
| Use Monte Carlo return-probability estimates rather than exact features (ablation) | RetGK_II · REDDIT-BINARY | accuracy: 91.6(0.2) -> 90.8(0.2) | Hurt |
| Use Monte Carlo return-probability estimates for kernel computation (ablation) | RetGK_II · Non-attributed graph datasets (total time) | runtime: 17m14s -> 6m9s | Helped |
| Use RetGK_II instead of the strongest reported baseline | Graph classification · Synthie | accuracy: 80.3(1.4) -> 96.2(0.3) | Helped |
| Use RetGK_II rather than RetGK_I (ablation) | RetGK · BZR | accuracy: 86.4(1.2) -> 87.1(0.7) | No clear effect |
| Use RetGK_II rather than RetGK_I (ablation) | RetGK · PROTEINS with both discrete and continuous attributes | accuracy: 78.0(0.3) -> 77.3(0.5) | Hurt |
Closest papers by meaning
- Taming graph kernels with random features (ICML 2023 · similarity 0.90)
- General Graph Random Features (ICLR 2024 · similarity 0.90)
- Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited (NeurIPS 2022 · similarity 0.89)
- Computationally-efficient Graph Modeling with Refined Graph Random Features (ICML 2026 · similarity 0.89)
- From Theory to Practice: Rethinking Green and Martin Kernels for Unleashing Graph Transformers (ICML 2025 · similarity 0.87)
- Manifold Random Features (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.