为匹配空间设计可计算的几何核函数，解决离散结构上的核方法难题。
Heat and Matérn Kernels on Matchings
- 基于对称性构建匹配空间的平稳核，引入热核与Matérn核以控制平滑性
- 提出新型子指数算法，用球多项式加速核计算，避免超指数开销
- 发现匹配与系统发育树间映射的局限性，揭示开放问题
将核方法应用于匹配结构面临其离散、非欧几里得性质带来的挑战。本文建立了一个原则性的框架，用于构造尊重匹配空间自然几何的几何核。首先，我们完整刻画了平稳核——即尊重该空间内在对称性的核。由于平稳核类过于宽泛，我们特别关注热核与Matérn核族，通过引入适当的光滑性归纳偏置来补充平稳性。尽管这些核族成功将流行的欧氏核推广至匹配空间，但其直接评估会产生禁止性的超指数计算成本。为此，我们提出并分析了一种新颖的子指数算法，利用球多项式实现高效核计算。最后，受匹配与系统发育树之间已知双射关系（生物学中关键数据模态）的启发，我们探索该框架能否无缝迁移至树空间，揭示了新的负结果，并指出了一个重要的开放问题。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。