Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited

• URL: http://arxiv.org/abs/2205.10914v1
• Date: Sun, 22 May 2022 19:41:25 GMT
• Title: Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited
• Abstract summary: We study walk-based node refinement methods and formally relate them to several widely-used techniques. We show that classical random walk kernels with only minor modifications regarding definition and computation are as expressive as the widely-used Weisfeiler-Leman subtree kernel. We verify experimentally that walk-based kernels reach or even surpass the accuracy of Weisfeiler-Leman kernels in real-world classification tasks.
• Score: 4.30226515682283
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Random walk kernels have been introduced in seminal work on graph learning and were later largely superseded by kernels based on the Weisfeiler-Leman test for graph isomorphism. We give a unified view on both classes of graph kernels. We study walk-based node refinement methods and formally relate them to several widely-used techniques, including Morgan's algorithm for molecule canonization and the Weisfeiler-Leman test. We define corresponding walk-based kernels on nodes that allow fine-grained parameterized neighborhood comparison, reach Weisfeiler-Leman expressiveness, and are computed using the kernel trick. From this we show that classical random walk kernels with only minor modifications regarding definition and computation are as expressive as the widely-used Weisfeiler-Leman subtree kernel but support non-strict neighborhood comparison. We verify experimentally that walk-based kernels reach or even surpass the accuracy of Weisfeiler-Leman kernels in real-world classification tasks.

Related papers

• Heat and Matérn Kernels on Matchings [5.790383107634059]
  kernel methods to matchings is challenging due to their discrete, non-Euclidean nature.<n>We develop a principled framework for constructing kernels that respect the natural geometry of the space of matchings.
  arXiv  Detail & Related papers  (2026-04-15T18:38:29Z)
• Metric Graph Kernels via the Tropical Torelli Map [0.0]
  We propose new graph kernels grounded in the study of metric graphs via tropical algebraic geometry.<n>Our graph kernels are based on the geometry and topology of the underlying metric space.<n> Empirically, our kernels outperform existing methods in label-free settings.
  arXiv  Detail & Related papers  (2025-05-17T20:00:50Z)
• Feature maps for the Laplacian kernel and its generalizations [3.671202973761375]
  Unlike the Gaussian kernel, the Laplacian kernel is not separable. We provide random features for the Laplacian kernel and its two generalizations. We demonstrate the efficacy of these random feature maps on real datasets.
  arXiv  Detail & Related papers  (2025-02-21T16:36:20Z)
• Spectral Truncation Kernels: Noncommutativity in $C^*$-algebraic Kernel Machines [12.11705128358537]
  We propose a new class of positive definite kernels based on the spectral truncation. We show that it is a governing factor leading to performance enhancement. We also propose a deep learning perspective to increase the representation capacity of spectral truncation kernels.
  arXiv  Detail & Related papers  (2024-05-28T04:47:12Z)
• On the Approximation of Kernel functions [0.0]
  The paper addresses approximations of the kernel itself. For the Hilbert Gauss kernel on the unit cube, the paper establishes an upper bound of the associated eigenfunctions. This improvement confirms low rank approximation methods such as the Nystr"om method.
  arXiv  Detail & Related papers  (2024-03-11T13:50:07Z)
• Structural Kernel Search via Bayesian Optimization and Symbolical Optimal Transport [5.1672267755831705]
  For Gaussian processes, selecting the kernel is a crucial task, often done manually by the expert. We propose a novel, efficient search method through a general, structured kernel space.
  arXiv  Detail & Related papers  (2022-10-21T09:30:21Z)
• A Unified Framework for Implicit Sinkhorn Differentiation [58.56866763433335]
  We propose an algorithm that obtains analytical gradients of a Sinkhorn layer via implicit differentiation. We show that it is computationally more efficient, particularly when resources like GPU memory are scarce.
  arXiv  Detail & Related papers  (2022-05-13T14:45:31Z)
• Meta-Learning Hypothesis Spaces for Sequential Decision-making [79.73213540203389]
  We propose to meta-learn a kernel from offline data (Meta-KeL) Under mild conditions, we guarantee that our estimated RKHS yields valid confidence sets. We also empirically evaluate the effectiveness of our approach on a Bayesian optimization task.
  arXiv  Detail & Related papers  (2022-02-01T17:46:51Z)
• Graph Filtration Kernels [3.325932244741268]
  We propose a family of graph kernels that incorporate existence intervals of features. We show that using Weisfeiler-Lehman labels over certain filtrations strictly increases the expressive power over the ordinary Weisfeiler-Lehman procedure.
  arXiv  Detail & Related papers  (2021-10-22T15:51:10Z)
• Fast Sketching of Polynomial Kernels of Polynomial Degree [61.83993156683605]
  kernel is especially important as other kernels can often be approximated by the kernel via a Taylor series expansion. Recent techniques in sketching reduce the dependence in the running time on the degree oblivious $q$ of the kernel. We give a new sketch which greatly improves upon this running time, by removing the dependence on $q$ in the leading order term.
  arXiv  Detail & Related papers  (2021-08-21T02:14:55Z)
• Kernel Continual Learning [117.79080100313722]
  kernel continual learning is a simple but effective variant of continual learning to tackle catastrophic forgetting. episodic memory unit stores a subset of samples for each task to learn task-specific classifiers based on kernel ridge regression. variational random features to learn a data-driven kernel for each task.
  arXiv  Detail & Related papers  (2021-07-12T22:09:30Z)
• Kernel Identification Through Transformers [54.3795894579111]
  Kernel selection plays a central role in determining the performance of Gaussian Process (GP) models. This work addresses the challenge of constructing custom kernel functions for high-dimensional GP regression models. We introduce a novel approach named KITT: Kernel Identification Through Transformers.
  arXiv  Detail & Related papers  (2021-06-15T14:32:38Z)
• MetaKernel: Learning Variational Random Features with Limited Labels [120.90737681252594]
  Few-shot learning deals with the fundamental and challenging problem of learning from a few annotated samples, while being able to generalize well on new tasks. We propose meta-learning kernels with random Fourier features for few-shot learning, we call Meta Kernel.
  arXiv  Detail & Related papers  (2021-05-08T21:24:09Z)
• Generalized vec trick for fast learning of pairwise kernel models [3.867363075280544]
  We present a comprehensive review of pairwise kernels, that have been proposed for incorporating prior knowledge about the relationship between the objects. We show how all the reviewed kernels can be expressed as sums of Kronecker products, allowing the use of generalized vec trick for speeding up their computation.
  arXiv  Detail & Related papers  (2020-09-02T13:27:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.