Heat and Matérn Kernels on Matchings

Dmitry Eremeev; Salem Said; Viacheslav Borovitskiy

cs.LGApr 15, 2026

Heat and Matérn Kernels on Matchings

Authors: Dmitry Eremeev, Salem Said, Viacheslav Borovitskiy

Organizations: University of Edinburgh

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.

Figures & tables

Panel of Figure 1 — Figure 1: If $x=\{\{1,2\},\{3,4\},\{5,6\},\{7,8\},\{9,10\}\}$ and $y=\{\{1,2\},\{3,5\},\{4,6\},\{7,9\},\{8,10\}\}$ , then the union $x\cup y$ forms the edge set of the disconnected graph shown here. It consists of two cycles of length four and one cycle of length two; thus, the generalized distance in this case is $d(x,y)=(2,2,1)$ .

	Precomputation time	Query time	Precomputation memory	Query memory
Proposition 1	$O\left(\|\mathcal{R}\|n^{2}\right)$	$O\left(\|\mathcal{R}\|\cdot 2^{n}n!\cdot T(n)\right)$	$O(\|\mathcal{R}\|+n)$	$O(M(n))$
Explicit formula	$O\left(\left\|\mathcal{X}_{n}\right\|\,n!np(n)\right)$	$O\left(\|\mathcal{R}\|n\right)$	$O(p(n)^{2}n)$	$O(n)$
Our method	$O\left(p(n)^{2}n^{3}\right)$	$O\left(\|\mathcal{R}\|\,p(n)\,n^{3}\right)$	$O(p(n)^{2}n^{2})$	$O(p(n)n)$

Table 1: Time and memory complexities for kernel evaluation using different algorithms for computing zonal spherical functions. Here,

|\mathcal{R}|

denotes the size of the truncation partition set,

p(n)

is the number of integer partitions of

n

, and

\left|\mathcal{X}_{n}\right|

is the number of matchings on

2n

elements.

T(n)

and

M(n)

stand for amortized time and memory complexities of computing value of character of

S_{2n}

. In practice, we use caching instead of full precomputation in both the “Explicit formula“ approach and in our method, making them more efficient than the theoretical analysis shows.

	$n=5$	$n=6$	$n=10$	$n=15$	$n=20$	$n=25$
Wall-clock time (seconds)
Proposition 1	$8.53\pm 0.08$	$131.98\pm 2.43$	–	–	–	–
Explicit formula	$6.49\pm 0.09$	$115.46\pm 1.70$	–	–	–	–
Our method	$7.54\pm 0.07$	$13.97\pm 0.08$	$56.06\pm 0.51$	$216.78\pm 3.63$	$907.90\pm 29.56$	$3639.62\pm 73.28$
Memory consumption (MB)
Proposition 1	$33.7\pm 0.4$	$34.1\pm 0.1$	–	–	–	–

Table 2: Wall-clock time (in seconds) and peak memory consumption (in MB) required to compute

100\times 100

covariance matrix using different methods for different values of

n

. Results are reported as mean

\pm

standard deviation over 5 trials.

Panel of Figure 2 — Figure 2: Laplacian eigenvalues $\lambda_{2\boldsymbol{\rho}}$ versus the maximal part $\rho_{1}$ , for all partitions $\boldsymbol{\rho}=(\rho_{1},\ldots,\rho_{s})\vdash n$ .

Panel of Figure 3 — Figure 3: Approximation quality of truncated kernels as a function of $|\mathcal{R}|$ . The $x$ -axis represents the number of partitions $|\mathcal{R}|$ used in the truncation; the $y$ -axis displays the relative $L^{2}$ approximation error $\left\lVert k-k_{\mathcal{R}}\right\rVert_{L^{2}(\mathcal{X}_{n}\times\mathcal{X}_{n})}/\left\lVert k\right\rVert_{L^{2}(\mathcal{X}_{n}\times\mathcal{X}_{n})}$ (log scale). For each $|\mathcal{R}|$ , the set $\mathcal{R}$ is selected by the maximizing $\rho_{1}$ .

Figure 4: Example of the inner node labeling procedure for a rooted phylogenetic tree, following the algorithm of Diaconis and Holmes (1998) . At each step, select a pair of nodes with the same parent such that both nodes are already labeled while their parent is not yet labeled. Among all such pairs, choose the pair containing the minimal label. Then, assign the next unused label to their parent node. The transition from (a) to (b) corresponds to the selection of the pair

\{1,5\}

(which contains

1

, the smallest label), and the assignment of label

6

to their parent. The transition from (b) to (c) selects

\{2,3\}

and assigns label

7

to their parent. The final transition from (c) to (d) selects the only remaining feasible pair,

\{4,6\}

, and labels their parent with

8

. The resulting matching is

\{\{1,5\},\,\{2,3\},\,\{4,6\},\,\{7,8\}\}

Figure 5: Illustration of the nearest neighbor interchange (NNI) operation. Starting from the tree in (a), where

A

B

, and

C

denote arbitrary subtrees, a single NNI move interchanges two adjacent subtrees around an internal edge. Figures (b) and (c) show the two distinct topologies that may be obtained from (a) by performing an NNI move at the indicated edge. Note that

R

does not need be the root of the entire tree—it may also be the root of a subtree.

Method	Small matching distance $\Rightarrow$ small tree distance	Small tree distance $\Rightarrow$ small matching distance
Bijection of Diaconis and Holmes (1998)	No (Prop. 6 )	No (Prop. 5 )
Embedding of Richman et al. (2026)	No (not invertible)	Yes (Prop. 7 )

Table 3: Comparison of known constructions relating matchings and phylogenetic trees.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 6: Example of two phylogenetic trees differing by a single NNI-move such that corresponding matchings have large distance in quotient Cayley graph. Specifically, x=[(1, 16), (2, 15), (3, 4), (5, 10), (6, 11), (7, 12), (8, 13), (9, 14)] and y=[(1, 2), (3, 4), (5, 11), (6, 12), (7, 13), (8, 14), (9, 15), (10, 16)]. This example also generalizes to larger

n

by inserting new leaves between

2

and

9

in the left tree.

Figure 7: Illustration for the proof of Proposition 6 .

Figure 8: Illustration for the proof of Proposition 7 .

Panel of Figure 9 — Figure 9: Additional results on approximation quality of truncated kernels as a function of $|\mathcal{R}|$ . The $x$ -axis represents the number of partitions $|\mathcal{R}|$ used in the truncation; the $y$ -axis displays the relative $L^{2}$ approximation error $\left\lVert k-k_{\mathcal{R}}\right\rVert_{L^{2}(\mathcal{X}\times\mathcal{X})}/\left\lVert k\right\rVert_{L^{2}(\mathcal{X}\times\mathcal{X})}$ (log scale). For each $|\mathcal{R}|$ , the set $\mathcal{R}$ is selected by the heuristic maximizing $\rho_{1}$ .

Panel of Figure 10 — Figure 10: Laplacian eigenvalues $\lambda_{2\boldsymbol{\rho}}$ versus various truncation heuristics, namely, maximal entry $\rho_{1}$ , length $s$ and minimal entry $\rho_{s}$ , for all partitions $\boldsymbol{\rho}=(\rho_{1},\ldots,\rho_{s})\vdash n$ .

Panel of Figure 11 — Figure 11: Scatter plot of eigenvalue $\lambda_{2\boldsymbol{\rho}}$ against log-scaled “spectral density” $\log\Phi(\lambda_{2\boldsymbol{\rho}})^{2}d_{2\boldsymbol{\rho}}$ for base $\nu=2.5$ , with and without degree correction (DC).

Kernel Methods

Kernel methods use similarity functions and reproducing kernel spaces to model nonlinear relationships, quantify uncertainty, and compare data.

See all 233 papers

Riemannian Metric Matching for Scalable Geometric Modeling of Distributions
Jun 12, 2026Jacob Bamberger, Adam Gosztolai, Pierre Vandergheynst +2Geometric Representation Learning Metric Learning
Department of Computer Science, University of Oxford, Oxford, UK · Institute of Artificial Intelligence, Medical University of Vienna, Vienna, Austria · EPFL, Lausanne, Switzerland +1
Exact Optimal Transport by Matching
Oct 2, 2026Dmitry KamenetskyOptimal Transport Combinatorial Optimization
Robust and Learned Online Matching in Growing Trees
Sep 30, 2026Marek Gałązka, Hanna WdowickaAdaptive Learning
Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań, Poland · Department of Statistics, Poznań University of Economics and Business, Poznań, Poland

Jun 12, 2026J/K move · Enter open · S save

Riemannian Metric Matching for Scalable Geometric Modeling of Distributions

Jacob Bamberger, Adam Gosztolai, Pierre Vandergheynst, Michael Bronstein+1

Department of Computer Science, University of Oxford, Oxford, UK · Institute of Artificial Intelligence, Medical University of Vienna, Vienna, Austria · EPFL, Lausanne, Switzerland+1

Geometric Representation Learning Metric Learning Riemannian Metric Learning Riemannian Geometry

Open paper AskPDF arXiv

High-dimensional datasets often concentrate near low-dimensional structures, but estimating their geometry from samples typically relies on graphs and kernels that scale poorly with dataset size and dimension. We propose Riemannian metric matching: a denoising probabilistic framework for learning the Riemannian geometry of data using neural networks. Specifically, we learn the carré du champ operator, which, using diffusion geometry, gives us access to the Riemannian geometry toolkit for downstream machine learning and statistical tasks. Our key observation is that the carré du champ operator can be formulated as a conditional expectation over random perturbations of the data, which can be exploited for sample-wise training and constant cost, amortized inference without explicit kernel construction. Empirically, metric matching rivals or improves the accuracy of

k

-NN-based diffusion geometry estimators, while enabling amortized inference that is up to

400\times

faster, and supports graph-free geometric analysis on high-dimensional images where nearest neighbors break down.

Abstract

Kernel Methods

Explore similar work

Riemannian Metric Matching for Scalable Geometric Modeling of Distributions

Exact Optimal Transport by Matching

Robust and Learned Online Matching in Growing Trees