Heat and Mat\'ern Kernels on Matchings

arXiv cs.LG / 4/17/2026

📰 NewsModels & Research

共有:

Key Points

The paper proposes a principled framework for building geometric kernel methods for matchings by respecting the inherent non-Euclidean geometry of the matching space.
It characterizes stationary kernels for matchings in a way that captures the space’s natural symmetries, then narrows to heat and Matérn kernel families with an added smoothness inductive bias.
Although these kernels extend popular Euclidean kernel families to matchings, naive evaluation is computationally intractable due to a super-exponential cost.
To enable practical use, the authors develop and analyze a new sub-exponential evaluation algorithm based on zonal polynomials.
The work further investigates transferring the framework from matchings to phylogenetic trees (via a known bijection), reporting novel negative results and outlining a significant open problem.

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\'{e}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.