Research map / Learning theory and algorithms / Optimal transport

Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs

NeurIPS 2026 · Learning theory and algorithms › Optimal transport · approach: Sinkhorn and entropic OT algorithms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes GenusSink, approximate generalized Sinkhorn with shortest-path costs on bounded-genus graphs using separator-based S-GFI data structures, achieving near-linear time and memory.

Problem

Sinkhorn optimal transport with geodesic (shortest-path) costs requires materializing an n x n cost/kernel matrix, giving quadratic time and memory, which is prohibitive for large graph-discretized manifolds and meshes.

Approach

Builds a separator-tree data structure (S-GFI) that multiplies generalized distance matrices in near-linear time, uses bounded-genus-to-low-treewidth metric embeddings to make the approach applicable, and plugs it into Sinkhorn iterations for near-linear pre-processing, iteration, plan querying, and memory.

Key results

• On pseudo-genus graphs GenusSink matches the dense geodesic full-kernel Sinkhorn to numerical precision while being significantly faster at larger scales, while most approximate baselines show a clear accuracy gap.
• On Thingi10K meshes GenusSink remains essentially exact (near-zero OT-cost error vs dense reference) while avoiding dense kernel materialization.
• In the Bronx EMS deployment with 60 ambulances, GenusSink achieves 12.5 minutes mean response time for high-severity calls vs 13.4-14.5 minutes for approximation baselines.

Limitations

• Restricted to bounded genus graphs; extension to minor-free graphs is future work.
• Practical implementation uses separator heuristics and random sampling rather than the theoretical embedding, and the depth hyperparameter h is set to small values.
• Theoretical guarantees for general f rely on cordiality or Fourier-feature approximations, with the approximate case not fully analyzed.

Experimental setup

Datasets: Thingi10K NYC EMS incident dispatch data JEMSS simulator Bronx configuration

Benchmarks: Thingi10K meshes (28 meshes, 2771-12472 vertices) dumbbell and pseudo-genus graphs Bronx EMS road graph (33,363 nodes)

Metrics: OT cost absolute error vs dense reference wall-clock runtime EMS mean and upper-tail response time

Baselines: dense geodesic full-kernel Sinkhorn Greenkhorn Screenkhorn Sparse Sinkhorn Geodesic heat kernel Ambient LinearSinkhorn Geodesic Nyström

Builds on: Sinkhorn algorithm Greenkhorn graph field integrators treewidth-based metric embedding for bounded genus graphs cordial functions

Closest papers by meaning

• Tree-Sliced Wasserstein Distance: A Geometric Perspective (ICML 2025 · similarity 0.86)
• Fast Tree-Field Integrators: From Low Displacement Rank to Topological Transformers (NeurIPS 2024 · similarity 0.85)
• Tree-Sliced Wasserstein Distance with Nonlinear Projection (ICML 2025 · similarity 0.84)
• Bridging Arbitrary and Tree Metrics via Differentiable Gromov Hyperbolicity (NeurIPS 2025 · similarity 0.84)
• Distance-Based Tree-Sliced Wasserstein Distance (ICLR 2025 · similarity 0.83)
• Accelerating Sinkhorn algorithm with sparse Newton iterations (ICLR 2024 · similarity 0.83)