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
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∪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(∣R∣n2)
O(∣R∣⋅2nn!⋅T(n))
O(∣R∣+n)
O(M(n))
Explicit formula
O(∣Xn∣n!np(n))
O(∣R∣n)
O(p(n)2n)
O(n)
Our method
O(p(n)2n3)
O(∣R∣p(n)n3)
O(p(n)2n2)
O(p(n)n)
Table 1: Time and memory complexities for kernel evaluation using different algorithms for computing zonal spherical functions. Here, ∣R∣ denotes the size of the truncation partition set, p(n) is the number of integer partitions of n , and ∣Xn∣ 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 S2n . 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±0.08
131.98±2.43
–
–
–
–
Explicit formula
6.49±0.09
115.46±1.70
–
–
–
–
Our method
7.54±0.07
13.97±0.08
56.06±0.51
216.78±3.63
907.90±29.56
3639.62±73.28
Memory consumption (MB)
Proposition 1
33.7±0.4
34.1±0.1
–
–
–
–
Table 2: Wall-clock time (in seconds) and peak memory consumption (in MB) required to compute 100×100 covariance matrix using different methods for different values of n . Results are reported as mean ± standard deviation over 5 trials.
Figure 2: Laplacian eigenvalues λ2ρ versus the maximal part ρ1 , for all partitions ρ=(ρ1,…,ρs)⊢n .
Figure 3: Approximation quality of truncated kernels as a function of ∣R∣ . The x -axis represents the number of partitions ∣R∣ used in the truncation; the y -axis displays the relative L2 approximation error ∥k−kR∥L2(Xn×Xn)/∥k∥L2(Xn×Xn) (log scale). For each ∣R∣ , the set R is selected by the maximizing ρ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 ⇒ small tree distance
Small tree distance ⇒ 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 .
Figure 9: Additional results on approximation quality of truncated kernels as a function of ∣R∣ . The x -axis represents the number of partitions ∣R∣ used in the truncation; the y -axis displays the relative L2 approximation error ∥k−kR∥L2(X×X)/∥k∥L2(X×X) (log scale). For each ∣R∣ , the set R is selected by the heuristic maximizing ρ1 .
Figure 10: Laplacian eigenvalues λ2ρ versus various truncation heuristics, namely, maximal entry ρ1 , length s and minimal entry ρs , for all partitions ρ=(ρ1,…,ρs)⊢n .
Figure 11: Scatter plot of eigenvalue λ2ρ against log-scaled “spectral density” logΦ(λ2ρ)2d2ρ for base ν=2.5 , with and without degree correction (DC).
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× faster, and supports graph-free geometric analysis on high-dimensional images where nearest neighbors break down.
Jacob Bamberger, Adam Gosztolai, Pierre Vandergheynst +2
Department of Computer Science, University of Oxford, Oxford, UK · Institute of Artificial Intelligence, Medical University of Vienna, Vienna, Austria · EPFL, Lausanne, Switzerland +1
Balanced discrete optimal transport between n sources and n targets of unit mass is exactly the minimum-cost assignment problem-a bipartite perfect matching-and is therefore solvable exactly by industrial matching engines in milliseconds to seconds. We ask when the exact approach beats the standard approximate alternatives, entropic Sinkhorn and its accelerated variant Greenkhorn, and make the sparse-exact side certified by a textbook LP dual-feasibility clip. Three contributions. (i) Measurement: on dense 2-D instances, exact matching (Jonker-Volgenant) is faster and strictly more accurate than either approximate method throughout the moderate-n regime (0.01 s at n=500 to 11.5 s at n=8000); reaching a 1% quality target on the same hardware requires roughly 10-80 min for Greenkhorn (factors 4e2-6e4 over exact; plain Sinkhorn is 20-650x slower still), a rough power-law projection beyond the measured range. Greenkhorn's measured speedup over plain Sinkhorn is only 1.0-1.5x on most converged cells. (ii) A simple kNN-pool gap certificate: given a pool matching and its Blossom dual, a one-pass O(n^2) clip produces a dense-feasible lower bound; combined with the Sinkhorn dual potential (valid at every iterate, not just at convergence), the bound is valid on all 45 measured configurations and tightens monotonically with k. (iii) A multi-robot task-allocation sanity check where the discrete plan is the deliverable: per-round exact assignment costs 0.1-68 ms, while a Sinkhorn-plus-hardening pipeline costs 0.12-15.9 s and accumulates 6-27% extra travel over 15 rounds. The Sinkhorn family's large-n dense regime is acknowledged and left untouched. Code, data, and results under MIT: https://github.com/dimkadimon/OT-Blossom.
We study irrevocable maximum-cardinality matching in trees revealed by successive leaf attachments, with a known horizon and an exogenous growth law that is misspecified or unknown. For deterministic affine attachment forecasts with nonnegative degree reinforcement, the optimal threshold policy loses at most twice the cumulative expected conditional total-variation error relative to an online oracle knowing the actual growth law. This follows from a unit-span property of the Bellman continuation score and has no additional horizon factor. A four-vertex example attains the coefficient two for the specified deterministic policy, and a two-model argument gives a lower bound linear in the model-error budget for arbitrary policies under general misspecification. For uniform-preferential attachment, the local error has an exact expression through the leaf count. When its constant mixture parameter is unknown, we estimate it from the same growing tree and update the threshold policy at geometric times. A parameter-sensitivity bound for individual Bellman prices and uniform degree-moment estimates yield expected regret O(nlog2n), using O(n2logn) arithmetic operations and O(n) stored entries. The exact minimax rate remains open.
Marek Gałązka, Hanna Wdowicka
Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań, Poland · Department of Statistics, Poznań University of Economics and Business, Poznań, Poland