Spanning-Tree Slices of Graph Optimal Transport: Stretch Predicts Distortion

Many graph signals are probability measures over the nodes, epidemic prevalence, traffic density, diffusion states; and comparing them properly calls for optimal transport (OT) with the shortest-path ground metric. The exact distance is a min-cost flow on the edges, fast per pair but offering neither a vector representation for many-to-many comparison nor a closed-form training loss. We study a simple surrogate: slice the graph OT problem along \emph{spanning trees of the graph itself}. Every spanning tree $T$ satisfies $d_T\ge d_G$, so the closed-form tree-Wasserstein distance upper-bounds the exact graph-W$_1$; the minimum over all spanning trees is exact, and averaging over a random family of trees gives a metric whose distortion is controlled by the family's stretch. We turn this into (i) an \emph{empirical stretch diagnostic} the pair-averaged stretch of the sampled trees that predicts a tree family's distortion on a given graph without solving any OT problem, (ii) an exact $\ell_1$ embedding of the surrogate metric that turns all-pairs comparison of $N$ signals into $NK$ sparse linear maps plus cheap $\ell_1$ distances, and (iii) a convex, piecewise-linear, GPU-batchable loss for graph neural networks that output distributions over nodes. On five real networks (citation, road, airline; up to $2\cdot10^4$ nodes), random-root shortest-path trees (the family behind sliced Sobolev transport at $p=1$) reach Pearson correlation $0.91$--$0.99$ with the exact distance and $2$--$8\%$ median error after a scalar calibration, uniform spanning trees are markedly worse, and the measured stretch predicts the observed inflation. A GCN trained for epidemic source localization with the tree-sliced loss places its predictions closer to the true sources in graph distance than with cross-entropy, consistently over three independent runs; we also report a clear limitation: short-range transport is distorted markedly more than global transport by every tree family.