Heat and Matérn Kernels on Matchings

• URL: http://arxiv.org/abs/2604.14331v1
• Date: Wed, 15 Apr 2026 18:38:29 GMT
• Title: Heat and Matérn Kernels on Matchings
• Abstract summary: 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.
• Score: 5.790383107634059
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Applying kernel methods to matchings is challenging due to their discrete, non-Euclidean nature. In this paper, we develop a principled framework for constructing geometric kernels that respect the natural geometry of the space of matchings. To this end, we first provide a complete characterization of stationary kernels, i.e. kernels that respect the inherent symmetries of this space. Because the class of stationary kernels is too broad, we specifically focus on the heat and Matérn kernel families, adding an appropriate inductive bias of smoothness to stationarity. While these families successfully extend widely popular Euclidean kernels to matchings, evaluating them naively incurs a prohibitive super-exponential computational cost. To overcome this difficulty, we introduce and analyze a novel, sub-exponential algorithm leveraging zonal polynomials for efficient kernel evaluation. Finally, motivated by the known bijective correspondence between matchings and phylogenetic trees-a crucial data modality in biology-we explore whether our framework can be seamlessly transferred to the space of trees, establishing novel negative results and identifying a significant open problem.

Related papers

• Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel [55.82768375605861]
  We establish a generalization bound for gradient flow that aligns with the classical Rademacher complexity for kernel methods.<n>Unlike static kernels such as NTK, the LPK captures the entire training trajectory, adapting to both data and optimization dynamics.
  arXiv  Detail & Related papers  (2025-06-12T23:17:09Z)
• Learning to Embed Distributions via Maximum Kernel Entropy [0.0]
  Emprimiical data can often be considered as samples from a set of probability distributions.<n> Kernel methods have emerged as a natural approach for learning to classify these distributions.<n>We propose a novel objective for the unsupervised learning of data-dependent distribution kernel.
  arXiv  Detail & Related papers  (2024-08-01T13:34:19Z)
• Optimal Kernel Choice for Score Function-based Causal Discovery [92.65034439889872]
  We propose a kernel selection method within the generalized score function that automatically selects the optimal kernel that best fits the data. We conduct experiments on both synthetic data and real-world benchmarks, and the results demonstrate that our proposed method outperforms kernel selection methods.
  arXiv  Detail & Related papers  (2024-07-14T09:32:20Z)
• HeNCler: Node Clustering in Heterophilous Graphs via Learned Asymmetric Similarity [48.62389920549271]
  HeNCler learns a similarity graph by optimizing a clustering-specific objective based on weighted kernel singular value decomposition.<n>Our approach enables spectral clustering on an asymmetric similarity graph, providing flexibility for both directed and undirected graphs.
  arXiv  Detail & Related papers  (2024-05-27T11:04:05Z)
• 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)
• Interpolation with the polynomial kernels [5.8720142291102135]
  kernels are widely used in machine learning and they are one of the default choices to develop kernel-based regression models. They are rarely used and considered in numerical analysis due to their lack of strict positive definiteness. This paper is devoted to establish some initial results for the study of these kernels, and their related algorithms.
  arXiv  Detail & Related papers  (2022-12-15T08:30:23Z)
• Isotropic Gaussian Processes on Finite Spaces of Graphs [71.26737403006778]
  We propose a principled way to define Gaussian process priors on various sets of unweighted graphs. We go further to consider sets of equivalence classes of unweighted graphs and define the appropriate versions of priors thereon. Inspired by applications in chemistry, we illustrate the proposed techniques on a real molecular property prediction task in the small data regime.
  arXiv  Detail & Related papers  (2022-11-03T10:18:17Z)
• Stationary Kernels and Gaussian Processes on Lie Groups and their Homogeneous Spaces I: the compact case [43.877478563933316]
  In to symmetries is one of the most fundamental forms of prior information one can consider. In this work, we develop constructive and practical techniques for building stationary Gaussian processes on a very large class of non-Euclidean spaces.
  arXiv  Detail & Related papers  (2022-08-31T16:40:40Z)
• On the Benefits of Large Learning Rates for Kernel Methods [110.03020563291788]
  We show that a phenomenon can be precisely characterized in the context of kernel methods. We consider the minimization of a quadratic objective in a separable Hilbert space, and show that with early stopping, the choice of learning rate influences the spectral decomposition of the obtained solution.
  arXiv  Detail & Related papers  (2022-02-28T13:01:04Z)
• 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)
• Hida-Mat\'ern Kernel [8.594140167290098]
  We present the class of Hida-Mat'ern kernels, which is the canonical family of covariance functions over the entire space of stationary Gauss-Markov Processes. We show how to represent such processes as state space models using only the kernel and its derivatives. We also show how exploiting special properties of the state space representation enables improved numerical stability in addition to further reductions of computational complexity.
  arXiv  Detail & Related papers  (2021-07-15T03:25:10Z)
• A Note on Optimizing Distributions using Kernel Mean Embeddings [94.96262888797257]
  Kernel mean embeddings represent probability measures by their infinite-dimensional mean embeddings in a reproducing kernel Hilbert space. We show that when the kernel is characteristic, distributions with a kernel sum-of-squares density are dense. We provide algorithms to optimize such distributions in the finite-sample setting.
  arXiv  Detail & Related papers  (2021-06-18T08:33:45Z)
• Strong Uniform Consistency with Rates for Kernel Density Estimators with General Kernels on Manifolds [11.927892660941643]
  We show how to handle kernel density estimation with intricate kernels not designed by the user. The isotropic kernels considered in this paper are different from the kernels in the Vapnik-Chervonenkis class that are frequently considered in statistics society.
  arXiv  Detail & Related papers  (2020-07-13T14:36:06Z)

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.