# Heat and Mat'ern Kernels on Matchings

arXiv: https://arxiv.org/abs/2604.14331 · HTML: https://mlsanity.com/paper/2604.14331/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 39 references that are in the map.
- First posted on arXiv 15 Apr 2026.

## Builds on (most cited first, 9 of 9)

- [Mat'ern Gaussian processes on Riemannian manifolds](https://mlsanity.com/paper/2006.10160/) (2020)
- [Mat'ern Gaussian Processes on Graphs](https://mlsanity.com/paper/2010.15538/) (2020)
- [Geodesic Exponential Kernels: When Curvature and Linearity Conflict](https://mlsanity.com/paper/1411.0296/) (2014)
- [Stationary Kernels and Gaussian Processes on Lie Groups and their Homogeneous Spaces I: the compact case](https://mlsanity.com/paper/2208.14960/) (2022)
- [Stationary Kernels and Gaussian Processes on Lie Groups and their Homogeneous Spaces II: non-compact symmetric spaces](https://mlsanity.com/paper/2301.13088/) (2023)
- [The GeometricKernels Package: Heat and Mat'ern Kernels for Geometric Learning on Manifolds, Meshes, and Graphs](https://mlsanity.com/paper/2407.08086/) (2024)
- [Isotropic Gaussian Processes on Finite Spaces of Graphs](https://mlsanity.com/paper/2211.01689/) (2022)
- [Invariant kernels on Riemannian symmetric spaces: a harmonic-analytic approach](https://mlsanity.com/paper/2310.19270/) (2023)
- [Omnipresent Yet Overlooked: Heat Kernels in Combinatorial Bayesian Optimization](https://mlsanity.com/paper/2510.26633/) (2025)

## Abstract (arXiv)

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'ern 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.