Halting in Random Walk Kernels
Lists
Only you see this
Abstract
Random walk kernels measure graph similarity by counting matching walks in two graphs. In their most popular form of geometric random walk kernels, longer walks of length $k$ are downweighted by a factor of $\lambda^k$ ($\lambda < 1$) to ensure convergence of the corresponding geometric series. We know from the field of link prediction that this downweighting often leads to a phenomenon referred to as halting: Longer walks are downweighted so much that the similarity score is completely dominated by the comparison of walks of length 1. This is a naive kernel between edges and vertices. We theoretically show that halting may occur in geometric random walk kernels. We also empirically quantify its impact in simulated datasets and popular graph classification benchmark datasets. Our findings promise to be instrumental in future graph kernel development and applications of random walk kernels.
BibTeX
@inproceedings{sugiyama2015halting,
author = {Mahito Sugiyama and Karsten M. Borgwardt},
title = {{Halting in Random Walk Kernels}},
booktitle = {Advances in Neural Information Processing Systems},
year = {2015},
}| A survey on graph kernels | Appl. Netw. Sci · 2020 |
| Graph Kernels: A Survey | JAIR · 2021 |
| Taming graph kernels with random features | arXiv · 2023 |
| Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs | arXiv · 2024 |
| Graph Kernels: State-of-the-Art and Future Challenges | Found. Trends Mach. Learn · 2020 |
| Scalable Global Alignment Graph Kernel Using Random Features: From Node Embedding to Graph Embedding | arXiv · 2019 |