Halting in Random Walk Kernels
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 λ k (λ < 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 naïve 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.
-weak review-The paper contains a theoretical proof of existence of the phenomenon of halting in geometric random kernels and anextended experimental section that both supports the theoretical results and furthermore has surprising implications on kernel selection in practical contexts. The paper is very well written and never displays any lack of clarity. The math is sound and only draws from rather basic concepts. The paper contains two main contributions: First, the authors provide a mathematical proof that halting can occur in geometric random walk kernels (which had previously been conjectured) by showing that certain kernel parameter choices lead the geometric random walk kernel to degrade into a simple topology-unaware kernel that is a superposition of a vertex label histogram kernel and a vertex-edge label histogram kernel. Secondly, the authors study the effect of halting empirically. For a variety of popular graph classification benchmark datasets, the authors observe halting to occur and are able to quantify its effects. The authors also arrive at a set of practical suggestions wrt reasonable use cases of geometric random walk kernels.Major Comments The paper is very tidy and contains straight-forward reasoning. The main theoretical insight of the authors seems to have been the idea to study the (straight-forward) theoretical relationship between geometric random walk kernels and label histogram kernels. While the theoretical insights are rather trivial, the paper shines particularly in the experimental section: The authors very carefully compare and contrast the effects of kernel selection wrt naive graph kernels, k-step random walk kernels and geometric random walk kernels. In particular, they convincingly conclude that it is in general wise in practice to select a k-step random walk kernel instead of a geometric kernel, even though the latter may naively seem more powerful. It would be nice to shed more light on why Gaussian RBF kernels on label histograms perform so favourably wrt sophisticated kernels.Minor issues Thm 1 proof: "relationship(s) hold(s)" p. 8 last sentence "a (the) fixed-length random walk kernel "The paper contains novel contributions, in particular a simple proof of a conjecture relevant to the ML community. The authors clearly show that their results effect and guide kernel selection in empirical contexts. Therefore, I propose to accept the paper for publication without further hesitation.